Re: Pitfalls in interference graph ?

Chaitin, in his original algorithm for register allocation by graph
colouring showed that all these issues are solvable.


To preferentially assign a virtual register to a specific machine
register, rewrite the instruction to use the real register, and
prepend a copy virtual -> real / append a copy real -> virtual. If the
virtual register can safely be assigned to that real register, the
coalescing phase will do this and eliminate the copy. This works for
call parameters, call results, and ops that only take a specific
register.


Where some but not all register can be used - eg r0 cannot be used a
an address base of PowerPC or 390, then mark all virtual registers
that are address bases as interferring with those registers.


A call instruction must cause all volatile (caller-saves) registers to
interfere will all virtual register live at the call point.


FPR vs GPR is an interesting issue. Muchnick, in "Advanced Compiler
Design and Implementation" recommends combining FPR and GPR
allocation. There are cases, such as copying large well aligned blocks
of memory, where one can use an FPR or GPR. Cooper, Harvey, and
Torczon (all from Rice, as Preston Briggs) in "How to Build an
Interference Graph" prefer to treat them separately.


Jeremy Wright


From: (Torben Fgidius Mogensen) <torbenm@app-1.diku.dk>
Sent: 01/10/2007 10:41:39
Subject: Re: Pitfalls in interference graph ?


"Mohamed Shafi" <shafitvm@gmail.com> writes:


> Hello all,
>
> I am trying to implement Briggs Optimistic register allocator after
> reading the the thesis written by Preston Briggs.
>
> Now for building the interference graph what other than register pairs
> is there any other issues that one has to look out for?


  - Calling conventions, i.e., caller-saves versus callee-saves
      registers, parameter-transfer registers and registers used for
      return address and stack/frame pointer.


  - Special-purpose registers, such as multiplication using specific
      registers for arguments and results.


  - Register types such as address/integer/FP registers.


Torben




Micro Focus Limited is registered in England and Wales. Registered number:
01504593
Registered office: The Lawn, 22-30 Old Bath Road Newbury, Berkshire, RG14 1QN,
UK

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