DOC PREVIEW
CMU CS 15745 - Register Allocation

This preview shows page 1-2-3-21-22-23-43-44-45 out of 45 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Register Allocation Ajay Mathew Register Allocation –RecapGeorge and Appel’s iterative spilling algorithm Chordal Graphuseful propertiesSimplicial Elimination OrderingAlgorithm The maximum cardinality search algorithm(MCS)The greedy coloring algorithmAlgorithm Post spillingCoalescingCoalescingPre-spillingCaveatsRegister Allocation after Classical SSA Elimination is NP-complete Talk OutlineCore register allocation problemChaitin’s ProofStatic Single Assignment (SSA)Register Allocation for SSA ProgramsSSA and Chordal interference graphsRegister Allocation after conversion to SSA may be easier.Why Chatin’s proof does not work after SSA elimination?Chatin’s proof does not work after SSA eliminationWhat we learnt till now…The current approachThe current approachCircular Graphs and SSA-Circular Graphs - ICircular Graphs and SSA-Circular Graphs - IISSA and Chordal interference graphsCircular Graphs and SSA-Circular Graphs - IIICircular Graphs and SSA-Circular Graphs - IVThe Reduction - IThe Reduction - IIAfter SSA-elimination …Current View – Register AllocationQuestions?Thanks Register AllocationAjay Mathew • Pereira and Palsberg. Register allocation via coloring of chordal graphs. APLOS'05 • Pereira and Palsberg. Register allocation after classical SSA elimination is NP-complete. FOSSACS'06Register Allocation –Recap• Interference graph• Graph coloring• NP Complete- Chaitin’s proof• Heuristics- priority coloring, Kempe’smethodSome examples and graphics are borrowed from the ASPLOS’05 paperGeorge and Appel’s iterative spilling algorithm• Drawback of George and Appel’s iterative spilling algorithm- spilling and coalescing very complex.• The interference relations b/w temporary variables can form any possible graph-ChaitinChordal Graph• Chord- an edge which is not part of the cycle but which connects two vertices on the cycle.• A graph is chordal if every cycle with four or more edges has a chord.useful properties• Minimum coloring-- O(E + V ) time• maximum clique• maximum independent set • minimum covering by cliquesAll these NP complete problems in general graphs are now solvable in polynomial time.Simplicial Elimination Ordering•A vertex v is called simplicial if its neighborhood in G is a clique.• A SEO of G is a bijectionV (G) -->{1…V}, such that every vertex viis a simplicial vertex in the subgraph induced by {v1,…. vi}{b; a; c; d} is a simplicial elimination ordering.• An undirected graph without self-loops is chordal if and only if it has a simplicialelimination ordering. (Dirac)AlgorithmThe maximum cardinality search algorithm(MCS)The greedy coloring algorithmAlgorithmPost spilling• polynomial algorithm-- O(V K)• the greedy coloring tends to use the lower colors first.Coalescing• For each instruction a := b, look for a color c not used in N(a) [ N(b),• If such a color exists, then the temporaries a and b are coalesced into a single register with the color c.CoalescingPre-spilling• Maintains k-colorable property• removes nodes to bring the size of the largest clique down to the number of available colorsiterated register coalescing algorithm.New algorithmCaveats• entire run-time library of the standard Java 1.5 distribution• Loop variables – spilling ?• JoeQ compiler(John Whaley)• IR- a set of instructions (quads- operator + 4 operands) organized into a control flow graph• control flow can potentially exit from the middle of a basic blockRegister Allocation after Classical SSAElimination is NP-completeSumit Kumar JhaSome examples and graphics are borrowed from the FOSSACS’06 paper and talk by the author Fernando M Q Pereira.Talk Outline• Background on “old” complexity results in register allocation• SSA form and the register allocation problem• Circular Graphs and Post-SSA Circular Graphs• The Reduction of coloring Circular graphs to register allocation after SSA elimination.• The Big PictureCore register allocation problem• Instance: a program P and a number N of available registers.• Problem: Can each of the temporaries of P be mapped to one of the N registers such that temporary variables with interfering live ranges are assigned to different registers?NP CompleteChaitin’s Proof• Chaitin et al. showed in 1981 that the core register allocation problem is NP-complete• They used a reduction from the graph coloringproblem. – The essence of Chaitin et al.'s proof is that every graph is the interference graph of some program.Static Single Assignment (SSA)• SSA form. Static single assignment (SSA) form is an intermediate representation used in many compilers like gcc 4.• If a program is in SSA form, then every variable is assigned exactly once, and each use refers to exactly one definition.Register Allocation for SSA Programs• Bouchez and Hack (2006) proved the result that strict programs in SSA form have chordal interference graphs. • Chordal graphs can be colored in polynomial time!• Strict program: Every path from the initial block to the use of a variable v passes through a definition of v.SSA and Chordal interference graphs• The core register allocation problem is NP-complete. [Chaitin 1981]• Also, a compiler can transform a given program into SSA form in cubic time.• We can color a chordal graph in linear time so we can solve the core register allocation problem for programs in SSA form in linear time. • A contradiction!! Not really.Register Allocation after conversion to SSA may be easier.• Given a program P, its SSA-form version P0, and a number of registers K, • the core register allocation problem (P,K) is not equivalent to (P0,K). – we can map a (P;K)-solution to a (P0;K)-solution, – we can not necessarily map a (P0;K)-solution to a (P;K)-solution.• The SSA transformation splits the live ranges of temporaries in P in such a way that P0 may need fewer registers than P.Why Chatin’s proof does not work after SSA elimination?(a) Chaitin et al.'s program to represent C4. (b) The interference graph of the original programChatin’s proof does not work after SSA eliminationWhat we learnt till now…• Core Register Allocation is NP Complete.• Chatin’s NP completeness proof does not work after classical SSA elimination.• The solution obtained by analyzing a SSA form program [chordal graphs] in polynomial time can not be mapped back to the original program.• So, the question if Register Allocation after SSA elimination


View Full Document

CMU CS 15745 - Register Allocation

Documents in this Course
Lecture

Lecture

14 pages

Lecture

Lecture

19 pages

Lecture

Lecture

8 pages

Lecture

Lecture

5 pages

Lecture

Lecture

6 pages

lecture

lecture

17 pages

Lecture 3

Lecture 3

12 pages

Lecture

Lecture

17 pages

Lecture

Lecture

18 pages

lecture

lecture

14 pages

lecture

lecture

8 pages

lecture

lecture

5 pages

Lecture

Lecture

19 pages

lecture

lecture

10 pages

Lecture

Lecture

20 pages

Lecture

Lecture

8 pages

Lecture

Lecture

7 pages

lecture

lecture

59 pages

Lecture

Lecture

10 pages

Task 2

Task 2

2 pages

Handout

Handout

18 pages

Load more
Download Register Allocation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Register Allocation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Register Allocation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?