Re: Predict register usage

Sid Touati <>
Mon, 28 Apr 2008 12:11:26 +0200

          From comp.compilers

Related articles
Predict register usage (Tim Frink) (2008-04-25)
Re: Predict register usage (Chris F Clark) (2008-04-25)
Predict register usage (Inderaj Bains) (2008-04-26)
Re: Predict register usage (Sid Touati) (2008-04-28)
Re: Predict register usage (2008-05-02)
Re: Predict register usage (2008-05-02)
Re: Predict register usage (=?ISO-8859-1?Q?Bj=F6rn_Franke?=) (2008-05-09)
| List of all articles for this month |

From: Sid Touati <>
Newsgroups: comp.compilers
Date: Mon, 28 Apr 2008 12:11:26 +0200
Organization: I.N.R.I.A Rocquencourt
References: 08-04-093
Keywords: registers, optimize
Posted-Date: 28 Apr 2008 22:44:01 EDT

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.

Post a followup to this message

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