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