11.7 An Efficient Register Allocator and Code Generator

The following algorithm writes on each tree node of an expression tree the number of registers needed to compute the node. It assumes a computer model that keeps one of its operand in a register. Left-most leaves are assigned a "1", and right-most leaves are assigned a "0" to allocate registers (it could be reversed). Parent nodes are assigned the maximum of the values of both children. If the values are equal one more register is needed to store the result, so the parent node is assigned the (equal) value plus one.

 
 	Algorithm 
 	Label (Expression Node) 
 	
 	1. Node is a left-most leaf: Label   = 1
 	2. Node is a right-most leaf: Label   = 0
 	3. (Otherwise) 
 	    3(a)Label (Left(Node)
 	    3(b)Label (Right(Node)
 	    3(c)Label# (Node) = Max(Left Label# , Right Label#)
 	        or Left Label# + 1 if Left Label# = RightLabel#.

The algorithm is called with Label(root)

Using the tree labelled as above, we can write an effiecient code generation algorithm:

 
 
 	
 	Algorithm 
 	GenerateCode (Node) 
 	CASE Node is:
 
   		A leaf labeled 1 and a left leaf:
 		   (a) R = GetReg
 		   (b) Generate "Load Node, R"
 	        Labeled with a number greater than available registers:
 		   (a) Generate code for right child
 	           (b) Store the result in a temp
 	           (c) Generate code for the left child
                    (d) Apply node's  operator to (a) and (c)
 	        Has a right child that is a leaf:
 	           (a) Evaluate the left child
 	           (b) Apply node's operator to left child
                        result and leaf.
 	        Otherwise:
 		   (a) GenerateCode(Node with larger label). (Use either if
 	               labels are the same) Leave result in a register
 		   (b) GenerateCode (Other Node)
 	           (c )Apply node's  operation to registers holding
                        the two results.