Home > Archive > Compilers > October 2007 > Pitfalls in interference graph ?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Pitfalls in interference graph ?
|
|
| Mohamed Shafi 2007-09-28, 7:20 pm |
| 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?
Regards,
Shafi
| |
|
| Mohamed Shafi a icrit :
> 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?
This a pretty old method of register allocation that do no longer work
well. Indeed, it was designed for the case of sequential processors.
Nowadays, processors implement instruction level parallelism. The
register allocation problem changed, and the old graph coloring
methods became useless.
Regards
S.T.
| |
| Torben Ęgidius Mogensen 2007-10-01, 7:18 pm |
| "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
| |
| John L 2007-10-01, 7:18 pm |
| 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
| |
| Peter Bergner 2007-10-02, 4:27 am |
| On Mon, 2007-10-01 at 15:46 +0100, Jeremy Wright wrote:
> 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.
What Muchnick recommends and what Cooper et al. recommends are
solutions to two different problems. Muchnick is concerned with
whether we should allocate registers of different types separately or
at the same time. What Cooper et al. are concerned with is how we
represent the interference information in the interference graph (ie,
do we store all the interferences for all of the register/pseudo types
in one big interference graph or do we partition them into separate
interference graphs, one for each register type).
So you can still allocate FPR and GPR registers at the same time as
recommended by Muchnick while using separate interference graphs for
FPRs and GPRs as recommended by Cooper et al. On the other hand, if
you want, you can also allocate FPRs and GPRs separately while using a
combined interference graph. Both issues are just two of the
implementation details up to the compiler designer.
<disclaimer>
I'm not actually arguing for or against either Muchnick's or Cooper et al.'s
recommendations. I'm just trying to show they're not mutually exclusive.
</disclaimer>
Peter
--
Peter Bergner
Linux on Power Toolchain
IBM Linux Technology Center
| |
| Rayiner Hashem 2007-10-03, 7:14 pm |
|
> How do you specify an affinity that is not 100% necessary? Like older i386
> arch CPU's having a preference for EBX as index register ?
I don't know if there are other ways to do this, but there is a 2002
paper called "Preference Directed Graph Coloring", which describes a
systematic way to address this issue, by trying to globally optimize
the fulfillment of register preferences.
| |
| Rayiner Hashem 2007-10-03, 7:14 pm |
| > > I am trying to implement Briggs Optimistic register allocator after
>
>
> This a pretty old method of register allocation that do no longer work
> well. Indeed, it was designed for the case of sequential processors.
> Nowadays, processors implement instruction level parallelism. The
> register allocation problem changed, and the old graph coloring
> methods became useless.
Huh? Where is the dependence on sequential processing in graph
coloring allocation? Moreover, only a few non mainstream archs expose
non sequential semantics at the ISA level anyway.
| |
| Jeremy Wright 2007-10-03, 7:14 pm |
| >> To preferentially assign a virtual register to a specific machine
> How do you specify an affinity that is not 100% necessary? Like older
> i386 arch CPU's having a preference for EBX as index register ?
Now we really are into the pitfalls.
There is a similar situation on the PowerPC. An operation of the form
ADD vr201 := gr200, -5
where vr = virtual register
can be done using the Power instructions ai vr201,vr200,-5 ; or cal
vr201,-5(vr200). The latter form is preferable as it does not affect
the carry bit, allowing greater freedom for scheduling. However, if
one uses cal then vr200 cannot be assigned to gr0.
Smith and Holloway in "Graph-Coloring Register Allocation for
Irregular Architectures" describes how they implemented graph coloring
on x86 ISA. Quickly rereading, they do not seem to deal specifically
with the question of preferentially assigning ebx, but I may have
missed something. Interesting reading anyway.
Jeremy
| |
| shafi 2007-10-16, 10:17 pm |
| > > Now for building the interference graph what other than register pairs
>
> - Calling conventions, i.e., caller-saves versus callee-saves
> registers, parameter-transfer registers and registers used for
> return address and stack/frame pointer.
>
parameter-transfer registers,return address registers and
stack/frame registers and other instruction specific and fixed-
function specific registers are handled by perpending and appending
move instructions to the register usages.
For caller/callee saved registers : A call instruction must cause all
volatile (caller-saves) registers to
interfere will all virtual register live at the call point.
Is there anything else other than this ?
Any help would be appreciated.
Regards,
Shafi.
| |
| Torben Ęgidius Mogensen 2007-10-17, 10:12 pm |
| shafi <shafitvm@gmail.com> writes:
> parameter-transfer registers,return address registers and
> stack/frame registers and other instruction specific and fixed-
> function specific registers are handled by perpending and appending
> move instructions to the register usages.
> For caller/callee saved registers : A call instruction must cause all
> volatile (caller-saves) registers to
> interfere will all virtual register live at the call point.
> Is there anything else other than this ?
You must make sure that the registers used for parameter passing are
considered live at the time of the call. You can do this by adding
these registers to the list of registers that the call instruction
reads (though it is, in fact, the called function that does this).
Also, make sure that the register(s) used for returning the function
result is considered live at the return point. You can do this by
adding this as a register read by the return instruction.
Chapter 9 of my book "Basics of Compiler Design" (which you can
download for free from http://www.diku.dk/~torbenm/Basics) considers
function calls and how this interacts with register allocation (which
is, otherwise, covered in chapter 8).
Torben
| |
|
| Rayiner Hashem a icrit :
> Huh? Where is the dependence on sequential processing in graph
> coloring allocation? Moreover, only a few non mainstream archs expose
> non sequential semantics at the ISA level anyway.
>
Colouring hurts ILP extraction for both superscalar VLIW and EPIC
processors. Even if the ILP is not exposed at the architectural level,
compilers schedule operations to help the processor to extract it at
execution time.
If register allocation with coloring methods are used, the ILP of the
generated code would not be easily extracted by the processor at
execution time. Dynamic renaming is limited in practice (since the
window od instructions is limited).
| |
| Rayiner Hashem 2007-10-21, 7:18 pm |
| > Colouring hurts ILP extraction for both superscalar VLIW and EPIC
> processors. Even if the ILP is not exposed at the architectural level,
> compilers schedule operations to help the processor to extract it at
> execution time.
I can see how it would hurt ILP extraction if you do register
allocation before scheduling, but if you do it after scheduling I
don't see the problem. Perhaps you could explain the issue in a bit
more detail?
> If register allocation with coloring methods are used, the ILP of the
> generated code would not be easily extracted by the processor at
> execution time. Dynamic renaming is limited in practice (since the
> window od instructions is limited).
Dynamic renaming is certainly limited, but surely the instruction
window on any reasonable OOO processor is big enough to allow renaming
to take care of almost all false dependencies.
| |
| Sid Touati 2007-10-24, 7:27 pm |
| Rayiner Hashem a icrit :
>
> I can see how it would hurt ILP extraction if you do register
> allocation before scheduling, but if you do it after scheduling I
> don't see the problem. Perhaps you could explain the issue in a bit
> more detail?
This is a phase ordering problem highlighted two decades ago. If you
do register allocation after scheduling, then too much spill code
would be generated. No, you can have a discussion how to combine them,
and how to do them separately. Fore more details, please read the
following article:
Sid-Ahmed-Ali Touati. Register Saturation in Instruction Level
Parallelism. International Journal of Parallel Programming,
Springer-Verlag, Volume 33, Issue 4, August 2005.
Indeed, instruction scheduling wants to maximise ILP, yielding in
excessive register requirement. If register allocation is done after
instruction scheduling, new memory operations are inserted to reduce
register pressure. And memory operations are very very bad for ILP
(dynamic cache problems, memory disambiguation mechanisms, memory
banks troubles, bandwidth and so on). For ILP extraction, it's always
better to do not go to memory if possible. When you request a data
from memory, you cannot have a static guarantee on the time it would
take a data to load (depending on the cache state, on the adress, on
the bus, etc.).
> Dynamic renaming is certainly limited, but surely the instruction
> window on any reasonable OOO processor is big enough to allow
> renaming to take care of almost all false dependencies.
This what say architects in general to sell their small instructions
window... But the practice show that nowadays codes are much more bigger
and complex than the benchmarks used to design processors. Nowadays,
codes are automatically generated by many tools, resulting in big code
sizes. Compilers and processors fail to correctly optimise them. The
technical heuristics about renaming (both in compilers and processors)
were designed for codes written by humans, that is small codes...
Nowadays, codes are more and more generated by automatic high level tools...
| |
| parthaspanda22@gmail.com 2007-10-24, 7:27 pm |
| > >I am trying to implement Briggs Optimistic register>allocator after[color=darkred]
At optimization level 0, you may want not to
iterate like Briggs' or Chaitin's algorithm would.
Typically, a production compiler uses a quick
and dirty register allocator that uses coloring
and an interference graph, but it doesnt iterate.
[color=darkred]
Have you considered the case when virtual registers
are live upon entry to an exception handler?
Sincerely.
|
|
|
|
|