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}