Re: Register allocation

"Rajaram" <rajaram@acmet.com> wrote
> > Are there any published records of how much improvement ( both in code
> > size and run time ) "register allocation" provides?
>
> I think there are many . Anyway checkout
>
> "Register Allocation by Priority-based Coloring" Frederick Chow t and John
> Hennessy
>
> It talks about register allocation statistics for benchmark programs(Section
> 7.1).


The original poster wanted one that does NOT use costing. Im not sure
why that (costing) should be a problem -but just to let you know that
"Register allocation by priority based coloring" by Chow Hennessy (ACM
Transaction of Programming Languages and Systems, Vol 12, No 4, Oct
1990) does use some sort of costing to find out which variable to
assign to a register. This algorithm is an improvement over the one
proposed by Chaitin (ref. Chaitin G.J, Register allocation and
spilling via graph coloring In Proceedings of the ACM SIGPLAN 82,
Symposium on Compiler Construction pp 98-105). Chaitin performs
optimization over machine code, whereas Hennessy relies on
intermediate code which the original poster intends to use. Both
Chaitin and Hennessy perform an intra-procedural analysis only. There
are quite a few other papers like:-


-Register allocation across procedure and module boundaries by Vatsa
Santhanam, Daryl Odnert in ACM SIGPLAN notices, June 1990 Vol 25 No 6
-A generalized scheme for graph coloring and register allocation by
Michael D Smith, Normal Ramsey and Glenn Holloway in ACM SIGPLAN
notices, Vol 39, No 6
-some other papers detailing techniques for parallel, embedded
architectures etc.. + optimizations for multi-threaded applications,
which Im not sure are of any interest to the original poster.


regards
-kamal

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