Paper Info
Title
A Progressive Register Allocator for Irregular Architectures
Abstract
Register allocation is one of the most important optimizations a compiler performs. Conventional graph-coloring based register allocators are fast and do well on regular, RISC-like, architectures, but perform poorly on irregular, CISC-like, architectures with few registers and non-orthogonal instruction sets. At the other extreme, optimal register allocators based on integer linear programming are capable of fully modeling and exploiting the peculiarities of irregular architectures but do not scale well. We introduce the idea of a progressive allocator. A progressive allocator finds an initial allocation of quality comparable to a conventional allocator, but as more time is allowed for computation the quality of the allocation approaches optimal. This paper presents a progressive register allocator which uses a multi-commodity network flow model to elegantly represent the intricacies of irregular architectures. We evaluate our allocator as a substitute for gcc's local register allocation pass.
Year
DOI
Venue
2005
10.1109/CGO.2005.4
CGO
Keywords
Field
DocType
register allocation,conventional graph-coloring,conventional allocator,irregular architectures,irregular architecture,progressive allocator,local register allocation,initial allocation,progressive register allocator,register allocators,optimal register,national electric code,registers,computer architecture,sections,cost function,network flow,graph coloring,computer science,integer linear programming,extremal optimization,reduced instruction set computing,instruction sets
Register allocation,Computer science,Instruction set,Parallel computing,Compiler,Register window,Integer programming,Reduced instruction set computing,Processor register,Allocator
Conference
ISSN
ISBN
Citations 
2164-2397
0-7695-2298-X
12
PageRank 
References 
Authors
0.65
14
2
Name
Order
Citations
PageRank
David Koes1392.58
Seth Copen Goldstein21951232.71