# 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 sethml@puree.ugcs.caltech.edu (1995-03-04)
Re: optimization and register allocation preston@tera.com (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 :

>while(1)
> 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
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.

NOW I HAVE A QUESTION.

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