@shafitvm: "Hello all,
Register allocation based on graph colouring is a global register
allocation technique. Most of the modern compliers will have both
global register allocation and local register allocation.
Graph colouring based allocator primarily depends on interference
graph for allocating registers. In the interference graph after its
build will have both the local and global virtual registers(with
respect to a block) as the nodes. These are the nodes that will be
considered later stages of the allocator, as in select and simplify of
chatins/briggs register allocator.  If this is the case, what is the
purpose of a separate local register allocator?
As I Am Implementing A Register Allocator Based On Briggs Optimistic
Register Allocator Which Works On The Pseudo Assembly Instructions, I
Would Want To Know The Need Of A Local Register Allocator.
Any help would be appreciated.
Regards,
Shafi."
    @parthaspanda22: "<quote>
One bright spot is how you approach register allocation on a stack
architecture(e.g. x87). That architecture allows you to think only in
local allocation terms. A useful idea to exploit in local register
allocation is placement of spill code. If you build a trace(like the
one that is created by an instruction scheduler) then you can try
moving code across basic block boundaries(either up or down) to bring
live ranges "closer"(i.e. make them shorter). The more closer a live
range becomes, the less likely will it approach k.
Sincerely."
    @SidTouati: "Mohamed Shafi a icrit :
<quote>
sorry, but I would say "most of the old compilers have ...".
They do exist since many decades, and were designed early for sequential
processors.
Modern compilers target modern ILP processors, not sequential ones...
If your register allocation use graph coloring as for the old sequential
processors, then it is not well designed for ILP processors.
However, some embedded low power processor (such as ARM) are still
sequential."
    @SidTouati: "Miles Bader a icrit :
<quote>
The term "modern" has no sense. It's marketing. Maybe you mean "actual".
Indeed, you should make a distinction what actual compilers do and
what they should do.  Most of the compilers use old register
allocation techniques, designed for sequential processors. When ILP
came, few of them used advanced techniques based on strong theoretical
research results. What happened is that many ad hoc practical
heuristics have been quickly designed to tackle the problem of
register allocation with ILP. Some improvement has been measured, but
on some simple non representative benchmarks. On real life codes, the
old register allocation techniques are not as efficient as people
think..."
    @gneuner2: "On Fri, 30 Nov 2007 16:17:40 +0100, Sid Touati <email_address>
wrote:
<quote>
You didn't answer Miles's question.
Frankly, I don't see what impact ILP has on register allocation.  The
fact that operations may be performed in parallel has no bearing
whatsoever on the number of live values in a block of code.  Either
the processor has enough registers to handle them all concurrently or
it doesn't, and if there aren't enough registers to handle all the
live values, you have to prioritize.  Existing instruction scheduling
and register allocation methods are perfectly adequate to do that.
If you know something different then how about providing some cites to
help the rest of us?
George"
    @gneuner2: "On Sat, 1 Dec 2007 10:12:01 -0800 (PST), "<email_address>"
<quote>
My point was that register allocation for ILP is not, as Sid Touati
seemed to be claiming, a fundamentally different problem from
allocating for a sequential processor.  There is some additional
effort to iterate scheduling and allocation to find a good balance,
but existing methods are up to that task already (whether existing
compilers do as well as they could using them is a different
discussion).
New methods that reduce the effort to find the sweet spot are always
welcome, but IMO claiming the old methods can't do the job is just
wrong.
I've seen that. Thanks.
George"
    @perttikellomaki: "So what are the trade-offs for ILP vs. non-ILP register
allocation? It is pretty clear that you don't want to
introduce unnecessary dependences in you code by register
reuse in the ILP case, but is there more than that to it?
Pertti"
    @SidTouati: "George Neuner a icrit :
<quote>
I am sorry if I was not clear enough. I try to provide a better message
below.
The problem of register allocation if you consider sequential codes is
fundamentally different from the case of ILP codes. Indeed, register
allocation on sequential codes tries to minimize the number of required
registers. This is the main objective (since it minimizes spill code as
side effect). Such objective can be solved by a classical interference
graph coloring, as initially presented by Chaitin, revisited recently by
Alain Darte (by the way, I suggest the community to study the recent
results of Alain Darte on this topic, since he revisited this old
problem and his team proveed many excellent new results). In ILP codes,
you should not only minimise the register need, but you should also take
care of critical path. In reality, you can just tackle the problem of
minimizing the critical path without exceeding the number of available
registers. This new constraints produces a new mathematical problem,
which is fundamentally different from just minimizing the register need.
For instance, I give one common example showing a fundamental difference
on register allocation on sequential and ILP codes. Let take a binary
tree, representing for example the DDG of an arithmetic expression. Then:
- the problem of register allocation on a sequential processor can be
solved optimally by Sethi Ullman algorithm, which is a well known
polynomial algorithm. While the general problem is NP-complete, the
problem is polynomial in case of binary trees.
- the problem of register allocation with critical path minimization on
ILP codes is NP-complete (see the paper of Gasperoni and Eisenbeis 1995
on this topic). This problem is NP-complete even for trees and chains.
As you can see, a well known polynomial register allocation problem in
sequential code becomes an NP-complete problem on ILP codes. Introducing
a new constraints (take care of critical path) in the register
allocation problem makes it distinct mathematically. Furthermore, the
spilling problem in ILP codes is  different from the spilling problem in
sequential codes.
There are many other mathematical differences... To understand them, one
should read fundamental research papers in computer science, which  use
formal reasoning and provide some mathematical results. If one relies on
ad-hoc heuristics to understand the problems, the understanding would
remain somehow superficial.
S.T."
    @torbenm: "Pertti Kellomdki <email_address> writes:
<quote>
Actually, register reuse is not a problem on most OOO architectures,
as they use register renaming at runtime to avoid this kind of
dependencies.  And on processors that do dynamic runtime scheduling,
compile-time scheduling is less important than avoiding spills: The
processor can to some extent schedule around a bad compile-time
schedule, but it can't undo a spill.
If you work with processors that have little or no runtime scheduling
but lots of registers (Itanium, Cell, etc.), then compile-time
scheduling becomes more important than register allocation.
	Torben"
    @gah: "(snip)
<quote>
The 360/91 floating point unit, designed for an architecture with only
four floating point registers, had to be able to undo a spill.  Memory
load requests look in the store buffer for a recent store, and will
take the value directly from the store buffer.  A later store to the
same address will cancel the previous store request.  (Assuming all
hazards are resolved.)  If the source of the store hasn't completed
yet, register renaming will get back to the original source.  A spill
inside a tight loop will likely be resolved by the processor logic,
with only the final value actually stored.
 glen"
    @SidTouati: "Anton Ertl a icrit :
mal schedule...
<quote>
The problem is that the number of situations is infinite. So, saying
"most of the codes", "most of the situations" or "representative
codes" has no absolute signification. Everyone has its own definition
of "practice". In my opinion, a compiler should be designed for
current codes, and also for future codes the do not already
exist. Designing a compiler for existing codes is meaningless for me
(it's my own opinion).
Usually, architects adds microarchitectural hardware to accelerate
current codes, not future codes. Optimizing compiler should (try) to
optimize all codes, current and future ones. This makes optimizing
compilation more difficult in general than engineering a processor.
If you can read our previous citations, we showed in very simple
"practical" existing BLAS1 loops, and even if data are in the L1/L2
cache, OoO schedulers can be:
- 21x far from the optimal in alpha 21264
- at least twice the optimal in power 4.
-  twice the optimal on itanium2 (here, the processor is in-order)
We have taken very small simple loops, where data reside in caches, and
a large amount of ILP exist. I cannot imagine codes simpler than that.
Both the compiler (with a lot of compilation swicths) and the OoO
execution fail to reach peak performance
Of course not, it is proved that any (polynomial time) list scheduler
(for any priority) can be twice far from the optimal. That is, for any
variant of list scheduler, you can be twice the optimal. This is a
mathematical fact, not an opinion.
This is because any variant of list scheduler do not delay a ready
instruction.
See my previous opinion about "most of the codes".
Yes, that comes to opinions about what is "too bad" and what is
"satisfactory". Depending on the objectives you target, you may be
satisfied or not by a solution.
When I compile an application on my desktop station, I am always
satisfied by the compiler. Buy when I compile a small embedded code, I
am not satisfied, since I always find a great space for improvement at
backend level."
{'source': 'USENET', 'other_information': '{"reply_count": 10, "forum_name": "comp.compilers.20140608.mbox"}', 'file': 'data/output/usenet-comp.compilers.parquet'}