Predict register usage

Hi,

When the optimization inline extension is performed on a high-level
intermediate representation or on a low-level IR before register
allocation, the final result for the inlined code after the register
allocation is not known. Thus, it might happen that due to the
increased register pressure after inlining, spill code must be added
heavily leading to a worse performance than before the
optimization. Do you know of any approaches which try to predict the
resulting spill code added by a register allocation when inlining is
done for a particular function?

My idea was that lifetime analyses might be used for that purpose.
could find out how many variables (in high-level) or register are life
across a call. This is an indication for spill code candidates. Based
on this one could develop some heuristics that omit inlining for
functions that are supposed to add too much spilling. What do you
think about this idea?

Are there in general any approaches that try to predict the register
usage/spill code generation in the generated assembly code exclusively
based on the consideration of the source code (or high-level code) and
the knowledge of the underlying hardware the compiler produces code
for? This is probably very hard since it requires a deep knowledge of
the register allocator.

Regards,
Tim

Function call has overheads including calling convention spill/reload
or maybe you do global register allocation. Finally the code is
executed at the same place, right? call or no call there is no magic,
you need the resources. Though inlining reduces call overhead,
subsequent code motion can increase register usage. Maybe by not
inlining you are limiting the ability of downstream optimizations to
mess up and inlining is not the issue. So what you can do here might
be driven less by the particular goodness of a particular approach and
more by what your downstream optimizations do, including how good
allocation is. For a cheap solution, you could try putting code motion
barriers around your inlined function when you see high register
pressure.

For a general solution, to me it seems that my ability to consider all
inter-optimization tradeoffs, architectural tradeoffs, fiddle
endlessly with switches to produce good results is limited. Using
machine learning or autotuners and letting machine do a good part of
this work might be the long term solution in coming time.

Inderaj

Before instruction scheduling, predicting the register usage is
difficult. If you target a computer engineering purpose, you can
imagine plenty of heuristics and techniques; in general, no guarantee
is required for engineering solutions, practical efficiency on a set
of benchmarks would be sufficient.

If you target a computer science purpose, you would require to think
about some formal guarantees. There are some fundamental answers to
your question. For instance, what you can predict is a interval for
register usage: say an exact maximal register usage, or an exact
minimal register usage.

For the exact minimal register usage, it is commonly called register
sufficiency. It has been proved that this minimal register usage depends
on the target architecture, that is, this minimal register usage is NT
a reachable minimal bound for any instruction schedule.

For the exact maximal register usage, it is called register
saturation. Contrary to the register sufficiency, the register
saturation does not depend on the target architecture. If the
instruction selection pass has been done, it is proved that the
register saturation IS a reachable upper bound for register usage for
any target architecture and for any instruction schedule. You can then
use register saturation to have a safe estimation of your maximum
register usage, independently on the final instruction schedule. And
this maximum register usage is always reachable (not over-estimated).

For more information:
Register Saturation in Instruction Level Parallelism. International
Journal of Parallel Programming, Springer-Verlag, Volume 33, Issue 4,
August 2005. 57 pages.

My practical experience suggests that if you have a proper optimizing
compiler with lots of phases, you *can't* predict effects of inlining
on register allocation. There are too many phases between -- many of
them able to radically impact register allocation. You can't predict
all these phases.

I saw cases when a single additional strength reduction blew up
register allocation.

Andrey