DocumentCode :
1519317
Title :
An Optimal Linear-Time Algorithm for Interprocedural Register Allocation in High Level Synthesis Using SSA Form
Author :
Brisk, Philip ; Verma, Ajay K. ; Ienne, Paolo
Author_Institution :
Dept. of Comput. Sci. & Eng., Univ. of California, Riverside, CA, USA
Volume :
29
Issue :
7
fYear :
2010
fDate :
7/1/2010 12:00:00 AM
Firstpage :
1096
Lastpage :
1109
Abstract :
An optimal linear-time algorithm for interprocedural register allocation in high level synthesis is presented. Historically, register allocation has been modeled as a graph coloring problem, which is nondeterministic polynomial time-complete in general; however, converting each procedure to static single assignment (SSA) form ensures a chordal interference graph, which can be colored in O(V + E) time; the interprocedural interference graph (IIG) is not guaranteed to be chordal after this transformation. An extension to SSA form is introduced which ensures that the IIG is chordal, and the conversion process does not increase its chromatic number. The resulting IIG can then be colored in linear-time.
Keywords :
circuit complexity; graph colouring; high level synthesis; optimising compilers; chordal interference graph; graph coloring problem; high level synthesis; interprocedural interference graph; interprocedural register allocation; nondeterministic polynomial time; optimal linear-time algorithm; static single assignment; Computer architecture; Computer science; High level synthesis; History; Interference; Laboratories; Optimizing compilers; Polynomials; Programming profession; Registers; (inteprocedural) register allocation; Chordal graph; graph coloring; high level synthesis; static single assignment (SSA) form;
fLanguage :
English
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
0278-0070
Type :
jour
DOI :
10.1109/TCAD.2010.2049060
Filename :
5487467
Link To Document :
بازگشت