15-745 Lecture 515-745 Lecture 5Control flow analysisNatural loopsNatural loopsClassical Loop OptimizationsDdiDependenciesC i ht © S th G ld t i 2008Lecture 5 15-745 © 2008 1Copyright © Seth Goldstein, 2008Based on slides from Lee & CallahanLoops are Key• Loops are extremely important–the “90-10” rulethe 9010 rule• Loop optimization involves–understanding controlflow structure–understanding control-flow structure– Understanding data-dependence informationsensitivity to sideeffecting operations–sensitivity to side-effecting operations– extra care in some transformations such as register spillingregister spillingLecture 5 15-745 © 2008 2Common loop optimizations• Hoisting of loop-invariant computationsScalar opts,DF l i– pre-compute before entering the loop• Elimination of induction variablesh i* b b h b i iDF analysis,Control flow analysis–change p=i*w+b to p=b,p+=w, when w,b invariant• Loop unrollingto improve scheduling of the loop body–to improve scheduling of the loop body• Software pipelining–To improve scheduling of the loop bodyRequires understanding data To improve scheduling of the loop body• Loop permutation–to improve cache memory performancedata dependenciesLecture 5 15-745 © 2008 3Finding Loops• To optimize loops, we need to find them!•Could use source language loop information in Could use source language loop information in the abstract syntax tree…•BUT:– There are multiple source loop constructs: for, while, do-while, even goto in C– Want IR to support different languages– Ideally, we want a single concept of a loop so all have same analysis same optimizationssame analysis, same optimizations– Solution: dismantle source-level constructs, then re-find loops from fundamentalsLecture 5 15-745 © 2008 4Finding Loops• To optimize loops, we need to find them!•Specifically:Specifically– loop-header node(s)• nodes in a loop that have immediate predecessors not in the loop– back edge(s)cnt lfl d s t •control-flow edges to previously executed nodes– all nodes in the loop bodypyLecture 5 15-745 © 2008 5Control-flow analysis• Many languages have goto and other complex control, so loops can be hard to find in generalcontrol, so loops can be hard to f nd n general• Determining the control structure of a program gpgis called control-flow analysis• Based on the notion of dominatorsLecture 5 15-745 © 2008 6Dominators•a dom b–node a dominates b if every possible node a dom nates b f every poss ble execution path from entry to b includes a• a sdom b– a strictly dominates b if a dom b and a != b•a idom b i di l di b if d b ND –a immediately dominates b if a sdom b, AND there is no c such that a sdom c and c sdom bLecture 5 15-745 © 2008 7Back edges and loop headers• A control-flow edge from node B3 to B2 Entryfrom node B3 to B is a back edge if B2 dom B3k = falsei = 1j = 2B1• Furthermore, in i <= nB2that case node B2 is a loop headerj = j*2k = truei = i+1..k..print ji = i+1B4B3print ji = i+1exitB6B5Lecture 5 15-745 © 2008 8Natural loop• Consider a back edge from node n to node h• The natural loop of n→h is the set of nodes L such that for all x∈L:such that for all x∈L:–h dom x and–there is a path from x to n not containing hthere is a path from x to n not containing hLecture 5 15-745 © 2008 9ExamplesSimple example:(often it’s more complicated, since FOR l f d i a FOR loop found in the source codemight need an if/then Lecture 5 15-745 © 2008 10gguard)ExamplesTry this:abdcefLecture 5 15-745 © 2008 11Examplesfor (..) {if {…} else {…if (x) {eif (x) {e;break;)}}Lecture 5 15-745 © 2008 12Examplesfor (..) {if {…} else {…if (x) {elexically, in loop, but not in natural loopif (x) {e;break;)}}Lecture 5 15-745 © 2008 13Examplesfor (..) {if {…} else {…if (x) {elexically, in loop, but not in natural loopif (x) {e;break;)and another reason why CFG }}yanalysis is preferred over source/AST loops Lecture 5 15-745 © 2008 14loops Examples• Yes, it can happen in CLecture 5 15-745 © 2008 15Natural LoopsWhat are the natural loops?One loop per header..000{012}1121{0,1,2}22033021{}21{1,2},{0,1,2,3}{1,2,3}Lecture 5 1615-745 © 2008Nested Loops• Unless two natural loops have the same header, they are either disjoint or nestedwithin each they are e ther d sjo nt or nestedw th n each other•If A and B are loops (sets of blocks) with p( )headers a and b such that a ≠ b and b ∈ A–B⊂ A– loop B is nestedwithin A–Bis the inner loopp• Can compute the loop-nest treeLecture 5 1715-745 © 2008General Loops• A more general looping structure is a strongly td tf th t l fl hconnected componentof the control flow graph– subgraph <Nscc,Escc> such thatevery block in Nsccis reachable from every other node using only edges in Eother node using only edges in Escc0021scc21Not very useful definition of a loopLecture 5 1815-745 © 2008Reducible Flow GraphsThere is a special class of flow graphs, called pgp,reducible flow graphs, for which several code-optimizations are especially easy to perform.In reducible flow graphs loops are unambiguously In reducible flow graphs loops are unambiguously defined and dominators can be efficiently computed.computed.19Lecture 5 15-745 © 2008Reducible flow graphsDefinition: A flow graph G is reducible iff we can partition the edges into two disjoint groups, forward edges and back edges with the following two propertiesedges, with the following two properties.1. The forward edges form an acyclic graph in which every node can be reached from the initial node of Gnode can be reached from the initial node of G.2. The back edges consist only of edges whose heads dominate their tails. 0Why isn’t this reducible?021This flow graph has no back edges Thus it would be 2021This flow graph has no back edges. Thus, it would be reducible if the entire graph were acyclic, which is not the case.Lecture 5 15-745 © 2008Alternative definition• Definition: A flow graph G is reducible if we can repeatedly collapse (reduce) together blocks (x,y) where xis the only predecessor of y(ignoring self where xis the only predecessor of y(ignoring self loops) until we are left with a single node000011,21,2,31,2,32,3,,012321330,1,2,3Lecture 5 15-745 © 2008Properties of Reducible Flow Graphs• In a reducible flow graph,gp,all loops are natural loops• Can use DFS to find loopsp• Many analyses
View Full Document
Unlocking...