An Optimal Linear-Time Algorithm for Interprocedural Register Allocation in High Level Synthesis Using SSA Form

作者：Brisk Philip^*; Verma Ajay K; Ienne Paolo

来源：IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2010, 29(7): 1096-1109.

DOI：10.1109/TCAD.2010.2049060

• Chordal graph
• graph coloring
• high level synthesis
• (inteprocedural) register allocation
• static single assignment (SSA) form

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(vertical bar V vertical bar+vertical bar E vertical bar) 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.

• 出版日期2010-7