Re: Register allocation

kamalp@acm.org (Kamal R. Prasad)
9 Aug 2004 01:27:13 -0400

          From comp.compilers

Related articles
[6 earlier articles]
Re: Register allocation sumesh_uk@hotmail.com (2003-07-31)
Register allocation avizit@gmail.com (2004-07-15)
Re: Register allocation gopi@sankhya.com (2004-07-28)
Re: Register allocation rajaram@acmet.com (Rajaram) (2004-08-04)
Re: Register allocation kamalp@acm.org (2004-08-05)
Re: Register allocation kym@sdf.lonestar.org (russell kym horsell) (2004-08-09)
Re: Register allocation kamalp@acm.org (2004-08-09)
Re: Register allocation gopi@sankhya.com (2004-08-10)
Re: Register allocation anton@mips.complang.tuwien.ac.at (2004-08-10)
Re: Register allocation anton@mips.complang.tuwien.ac.at (2004-08-10)
Re: Register allocation kym@kymhorsell.com (2004-08-11)
Re: Register allocation kamalp@acm.org (2004-08-13)
Register allocation thibault.langlois@di.fc.ul.pt (thibault.langlois@di.fc.ul.pt) (2005-05-13)
[16 later articles]
| List of all articles for this month |
From: kamalp@acm.org (Kamal R. Prasad)
Newsgroups: comp.compilers
Date: 9 Aug 2004 01:27:13 -0400
Organization: http://groups.google.com
References: 04-07-044 04-08-008
Keywords: registers
Posted-Date: 09 Aug 2004 01:27:13 EDT

"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


Post a followup to this message

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