Re: optimization and register allocation

davidm@Rational.COM (David Moore)
Tue, 28 Feb 1995 01:39:20 GMT

          From comp.compilers

Related articles
optimization and register allocation sastry@GODEL.MIEL.MOT.COM (1995-02-24)
Re: optimization and register allocation davidm@Rational.COM (1995-02-28)
Re: optimization and register allocation (1995-03-04)
Re: optimization and register allocation (1995-03-06)
| List of all articles for this month |

Newsgroups: comp.compilers
From: davidm@Rational.COM (David Moore)
Keywords: optimize, registers
Organization: Rational Software Corporation
References: 95-02-182
Date: Tue, 28 Feb 1995 01:39:20 GMT

sastry@GODEL.MIEL.MOT.COM (Venkateshwara Sastry) writes:

>Consider the following piece of code :

> y = (-a) +f2 ;
> ... many uses of a here.

>An optimizing compiler probably find that (-a) is loop invariant and
>replace the code by [code which increases register pressure]

>How can one determine whether to perform such optimizations( whose
>behavior depend on register allocator) or not?

The particular case you mention may be handled by algebraic
simplification. The above statement being replaced by f2-a.
Note that f2-a is not quite the same as (-a)+f2 because the
latter may overflow while the former does not. In C you
can make this optimization because it does not care. In
Ada you can make this optimization even though the
language does care because you can notionally do the
calculation in a wider type which would not overflow.

However, the general question you are asking is "How do you avoid
hoisting invariants out of loops which are cheaper to
recalculate than a spill they cause"

One answer is to just let the register allocator handle it.
There is a technique called "rematerialization" which will
seek to re-calculate values which otherwise would be spilled
and filled.

(There have been some excellent articles on register allocation in
the last year in Transactions on Programming Languages and Systems.
If you have access to ACM publications, you could do worse than
to start with Chaitin's paper in Communications of the ACM (circa
1978?) and then work forward through Transactions on Programming
Languages and Systems (TOPLAS) reading the register allocation papers)

For example, a constant can be rematerialised. On a risc machine,
the sort of constant you would hoist in the first place will
probably take two instructions to recalculate, which may be one more
than it takes to reload it, so you have a nice decision as
to whether to take the instruction and potentially pollute
your cache or else recalculate and leave the cache untouched.

For non-constants, you can rematerialise if the operands are
allocated at the point of rematerialisation. You do not
want to use them if they are not allocated in the loop since
this will extend the live range into the loop and they will
now need to be allocated there.

Requring them to be allocated is not
quite the same as requiring them to be live since you may
not be splitting live ranges. However, if one of the operands
is not live but is allocated, you could possibly save the
spill altogether by splitting live ranges for the operand.
Of course, you would need the operand to be live nowhere
in the loop since otherwise the constant will interfere with
the operand somewhere.

This suggests that it might be desirable to split live ranges
only for cases where a value is dead for an entire loop and
live on either side of it.


I have heard it said that live range splitting is not usually
worth the expense. How true is this?

Has anyone investigated doing splitting
only in response to register pressure, or only for values
that are dead in loops but would be in registers there?

Post a followup to this message

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