Re: Pitfalls in interference graph ?

Sid Touati <>
Wed, 24 Oct 2007 17:49:35 +0200

          From comp.compilers

Related articles
[7 earlier articles]
Re: Pitfalls in interference graph ? (Rayiner Hashem) (2007-10-01)
Re: Pitfalls in interference graph ? (Jeremy Wright) (2007-10-02)
Re: Pitfalls in interference graph ? (shafi) (2007-10-15)
Re: Pitfalls in interference graph ? (2007-10-17)
Re: Pitfalls in interference graph ? (ST) (2007-10-18)
Re: Pitfalls in interference graph ? (Rayiner Hashem) (2007-10-21)
Re: Pitfalls in interference graph ? (Sid Touati) (2007-10-24)
Re: Pitfalls in interference graph ? (2007-10-24)
| List of all articles for this month |

From: Sid Touati <>
Newsgroups: comp.compilers
Date: Wed, 24 Oct 2007 17:49:35 +0200
Organization: Universite de Versailles Saint-Quentin-en-Yvelines
References: 07-09-10407-10-021 07-10-058 07-10-065
Keywords: parallel, analysis
Posted-Date: 24 Oct 2007 12:16:41 EDT

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...

Post a followup to this message

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