11.6.3 Register Allocation by Usage Counts

A slightly more sophisticated method for global register allocation is called usage counts. (This is a heuristic. A heuristic method is one that usually, but not always, makes things better.) In this method, registers are allocated first to the variables that are used the most.

Example 5

Consider the following loop:

	LOOP: X = 2 * E
	      Z = Y + X + 1
	      IF some condition THEN
	        Y = Z + Y
	        D = Y - 1
	      ELSE Z = X - Y
	        D = 2
	      ENDIF
	        X = Z + D
                Z = X
        ENDLOOP

Here, there are five references to X, and Z, five references to Y, three references to D, and one to E. Thus, if there are three registers, a reasonable approach would be to allocate X and Z to two of them, saving the third for local computations. The resulting code would be (something like):

	Load	X,R1 
	Load	Z,R2 
Loop:	Load	E,R3 
	Mult	#2,R3 
	Store	R3,X 
	Copy	R1,R3 
	Add	Y,R3
	Add	#1,R3
	Store   R3,Z
	IF some condition  THEN
 	  Copy  R2,R3
	  Add	Y,R3
          Store R3,Y
	  Load	Y,R3
	  Sub   #1,R3
	  Store R3,D
	ELSE Copy R1,R3
	  Sub	Y,R3
	  Store R3,Z
	  Load  #2,R3
    	  Store R3,D
        ENDIF
	  Copy  R2,R3
          Add   D,R3
          Store R3,X  
          Store R3,Z
{ENDLoop}

Send questions and comments to: Karen Lemone