Re: Pitfalls in interference graph ?

johnl@iecc.com (John L)
Mon, 1 Oct 2007 15:46:45 +0100

          From comp.compilers

Related articles
Pitfalls in interference graph ? shafitvm@gmail.com (Mohamed Shafi) (2007-09-28)
Re: Pitfalls in interference graph ? SidTouati@inria.fr (ST) (2007-10-01)
Re: Pitfalls in interference graph ? torbenm@app-1.diku.dk (2007-10-01)
Re: Pitfalls in interference graph ? johnl@iecc.com (2007-10-01)
Re: Pitfalls in interference graph ? bergner@vnet.ibm.com (Peter Bergner) (2007-10-01)
Re: Pitfalls in interference graph ? marcov@stack.nl (Marco van de Voort) (2007-10-01)
Re: Pitfalls in interference graph ? rayiner@gmail.com (Rayiner Hashem) (2007-10-01)
Re: Pitfalls in interference graph ? rayiner@gmail.com (Rayiner Hashem) (2007-10-01)
Re: Pitfalls in interference graph ? jeremy.wright@microfocus.com (Jeremy Wright) (2007-10-02)
Re: Pitfalls in interference graph ? shafitvm@gmail.com (shafi) (2007-10-15)
[5 later articles]
| List of all articles for this month |

From: johnl@iecc.com (John L)
Newsgroups: comp.compilers
Date: Mon, 1 Oct 2007 15:46:45 +0100
Organization: Compilers Central
References: 07-09-104 07-10-007
Keywords: optimize, registers
Posted-Date: 01 Oct 2007 12:07:37 EDT

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



Post a followup to this message

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