Terminology, Principles, and Concerns, III COMP 512 Rice University Houston, Texas Fall 2008 Copyright 2008, Keith D. Cooper & Linda Torczon, all rights reserved. Students enrolled in Comp 512 at Rice University have explicit permission to make copies of these materials for their personal use. Last Lecture •! Extended Basic Blocks •! Superlocal value numbering >! Treat each path as a single basic block >! Use a scoped hash table & SSA names to make it efficient COMP 512, Fall 2008! 2!This Lecture •! Dominator Trees >! Computing dominator information >! Global data-flow analysis •! Dominator-based Value Numbering >! Enhance the Superlocal Value Numbering algorithm so that it can cover more blocks •! Optimizing a loop nest >! Finding loop nests >! Loop unrolling as an initial transformation COMP 512, Fall 2008! 3!COMP 512, Fall 2008! 4!This is in SSA Form Superlocal Value Numbering m0 ! a + b!n0 ! a + b!A p0 ! c + d!r0 ! c + d!B r2 ! "(r0,r1)!y0 ! a + b!z0 ! c + d!G q0 ! a + b!r1 ! c + d!C e0 ! b + 18!s0 ! a + b!u0 ! e + f!D e1 ! a + 17!t0 ! c + d!u1 ! e + f!E e3 ! "(e0,e1)!u2 ! "(u0,u1)!v0 ! a + b!w0 ! c + d!x0 ! e + f!F With all the bells & whistles •! Find more redundancy •! Pay little additional cost •! Still does nothing for F & G Superlocal techniques •! Some local methods extend cleanly to superlocal scopes •! VN does not back up •! If C adds to A, it’s a problemCOMP 512, Fall 2008! 5!What About Larger Scopes? We have not helped with F or G •! Multiple predecessors •! Must decide what facts hold in F and in G >! For G, combine B & F? >! Merging state is expensive >! Fall back on what’s known Gm0 ! a + b!n0 ! a + b!Ap0 ! c + d!r0 ! c + d!Br2 ! "(r0,r1)!y0 ! a + b!z0 ! c + d!q0 ! a + b!r1 ! c + d!Ce0 ! b + 18!s0 ! a + b!u0 ! e + f!De1 ! a + 17!t0 ! c + d!u1 ! e + f!E e3 ! "(e0,e1)!u2 ! "(u0,u1)!v0 ! a + b!w0 ! c + d!x0 ! e + f!F COMP 512, Fall 2008! 6!Dominators Definitions x dominates y if and only if every path from the entry of the control-flow graph to the node for y includes x •! By definition, x dominates x •! We associate a Dom set with each node •! |Dom(x )| ! 1 Immediate dominators •! For any node x, there must be a y in Dom(x ) closest to x •! We call this y the immediate dominator of x •! As a matter of notation, we write this as IDom(x )COMP 512, Fall 2008! 7!Dominators Dominators have many uses in analysis & transformation •! Finding loops •! Building SSA form •! Making code motion decisions We’ll look at how to compute dominators later A B C G F E D Dominator tree Block Dom IDomA A –B A,B AC A,C AD A,C,D CE A,C,E CF A,C,F CG A,G ADominator sets Back to the discussion of value numbering over larger scopes ... * m0 ! a + b!n0 ! a + b!Ap0 ! c + d!r0 ! c + d!Br2 ! "(r0,r1)!y0 ! a + b!z0 ! c + d!Gq0 ! a + b!r1 ! c + d!Ce0 ! b + 18!s0 ! a + b!u0 ! e + f!De1 ! a + 17!t0 ! c + d!u1 ! e + f!E e3 ! "(e0,e1)!u2 ! "(u0,u1)!v0 ! a + b!w0 ! c + d!x0 ! e + f!F Original idea: R.T. Prosser. “Applications of Boolean matrices to the analysis of flow diagrams,” Proceedings of the Eastern Joint Computer Conference, Spartan Books, New York, pages 133-138. COMP 512, Fall 2008! 8!What About Larger Scopes? We have not helped with F or G •! Multiple predecessors •! Must decide what facts hold in F and in G >! For G, combine B & F? >! Merging state is expensive >! Fall back on what’s known •! Can use table from IDom(x ) to start x >! Use C for F and A for G >! Imposes a Dom-based application order Leads to Dominator VN Technique (DVNT) * m0 ! a + b!n0 ! a + b!Ap0 ! c + d!r0 ! c + d!Br2 ! "(r0,r1)!y0 ! a + b!z0 ! c + d!Gq0 ! a + b!r1 ! c + d!Ce0 ! b + 18!s0 ! a + b!u0 ! e + f!De1 ! a + 17!t0 ! c + d!u1 ! e + f!E e3 ! "(e0,e1)!u2 ! "(u0,u1)!v0 ! a + b!w0 ! c + d!x0 ! e + f!FCOMP 512, Fall 2008! 9!Dominator Value Numbering The DVNT Algorithm •! Use superlocal algorithm on extended basic blocks >! Retain use of scoped hash tables & SSA name space •! Start each node with table from its IDom >! DVNT generalizes the superlocal algorithm •! No values flow along back edges (i.e., around loops) •! Constant folding, algebraic identities as before Larger scope leads to (potentially) better results >! LVN + SVN + good start for EBBs missed by SVN COMP 512, Fall 2008! 10!Dominator Value Numbering m ! a + b!n ! a + b!A p ! c + d!r ! c + d!B r2 ! "(r0,r1)!y ! a + b!z ! c + d!G q ! a + b!r ! c + d!C e ! b + 18!s ! a + b!u ! e + f!D e ! a + 17!t ! c + d!u ! e + f!E e3 ! "(e1,e2)!u2 ! "(u0,u1)!v ! a + b!w ! c + d!x ! e + f!F DVNT advantages •! Find more redundancy •! Little additional cost •! Retains online character DVNT shortcomings •! Misses some opportunities •! No loop-carried CSEs or constantsCOMP 512, Fall 2008! 11!Computing Dominators Critical first step in SSA construction and in DVNT •! A node n dominates m iff n is on every path from n0 to m >! Every node dominates itself >!n’s immediate dominator is its closest dominator, IDOM(n)† DOM(n0 ) = { n0 } DOM(n) = { n } # ($p!preds(n) DOM(p)) Computing DOM •! These simultaneous set equations define a simple problem in data-flow analysis •! Equations have a unique fixed point solution •! An iterative fixed-point algorithm will solve them quickly †IDOM(n ) " n, unless n is n0, by convention.!Initially, DOM(n) = N, % n!n0 COMP 512, Fall 2008! 12!Round-robin Iterative Algorithm Termination •! Makes sweeps over the nodes •! Halts when some sweep produces no change DOM (b0 ) ! Ø for i ! 1 to N DOM(bi ) ! { all nodes in graph } change ! true while (change) change ! false for i ! 0 to N TEMP ! { i } # ($x!pred (b) DOM(x )) if DOM(bi ) " TEMP then change ! true DOM(bi ) ! TEMPCOMP 512, Fall 2008! 13!Example B1 B2 B3 B4 B5 …