register allocation

hi,


I'm working from robert morgan 'building an optimizing compiler' and
making a register allocator. The book is designed around Risc
processors, but I'm trying to see what happens when I use it on a
limited register CISC processor like the x86.


For the most part I can get the algorithms working, which include some
local optimization, live variable analysis, and the register
allocation. However I've come up with a problem where maxing out the
registers to use to store globals (variables used across block
boundaries) confuses the spilling algorithms.


basically I'm compiling the following C language code:


int bb()
{
  int a,b,c,d,e,f,g,h;
  a = 1 ;
  b = 2 ;
  c = 3 ;
  d = 4 ;
  e = 5 ;
  f = 6 ;
  g = 7 ;
  h = 8 ;
  if (d)
    d++;
  aa(a,b,c,d,e,f,g,h);
}


Bear in mind all the variables are globals, and there are only 6
available registers in my implementation. it generates good
intermediate code up to the call of aa(), after which I get the
following:


;
; Line 50: aa(a,b,c,d,e,f,g,h);
;
  TEMP10(unknown).I = **DUMMY3:LINK(-12).I
  **DUMMY5:LINK(-4).I = TEMP10(unknown).I
  PARM TEMP10(unknown).I
  TEMP10(unknown).I = **DUMMY5:LINK(-4).I
  PARM _g[TEMP1]:LINK(EDI).I
  PARM _f[TEMP2]:LINK(EBX).I
  PARM _e[TEMP3]:LINK(ECX).I
  PARM _d[TEMP4]:LINK(ESI).I
  PARM _c[TEMP5]:LINK(EAX).I
  PARM _b[TEMP6]:LINK(EDX).I
  TEMP11(EAX).I = **DUMMY2:LINK(-16).I
  PARM TEMP11(EAX).I
  GOSUB #_aa:RAM.A


basically there has been two spills while processing 'h'... one during
global allocation and one during local. DUMMY3 is the result of the
global spill, DUMMY5 the result of the local one. During the local
allocation it can't find a register because the spill algorithm says go
to the beginning of the block and find the earliest (local) temporary
register that is unused past the current point in the block and spill
it. But we are already at the beginning of the block... I think it
would work fine if I hadn't already maxed out the register usage with
globals, or if it had chosen something other than 'h' to spill. While I
could make the global allocator not spill 'h' in these circumstances, I
don't want to do it because I am concerned another ordering of the
variables in the call to 'a' would result in the same problem.


The book doesn't really talk about the consequences when the registers
are maxed out by the global allocation algorithm, and I'm not sure what
direction to go in here. I'm thinking that if I alter the spill
algorithm slightly to work also when the spilled register is AFTER the
current line of code instead of before, that would work, but am unsure
if that would have other negative consequence. Can anyone shed some
light on this for me?


Thanks,


David


.

Return to the comp.compilers page.
Search the comp.compilers archives again.