15-745 Lecture 17 3/20/2007115-745 © Tim Callahan 115-745Structural/Interval Analysis+Dataflow Analysis Take IICopyright © Tim Callahan 2005-200715-745 © Tim Callahan 2Review: Dominators• X dom Yiff every execution path from the entry to Y goes through X• Solved by simple fwd dataflow:– meet: intersection (only dominated by X if all predecessors are dominated by X)– transfer: add myselfABC DEFEntryAA,BA,B,DA,B,CA,B,EAA,FA15-745 © Tim Callahan 3More Review: Natural Loops• Defined by a backedgeY -> X where X dom Y• Finds (only) single-entry loops.• Body: X plus those blocks that can reach Y without going through X.• Will find nested loop structureAXC DYFEntryA15-745 © Tim Callahan 4Not all cycles are natural loops• “irreducible”, “improper”, not “well-structured”...• a multi-entry loop• a CFG is “well-structured”iff its edge set can be partitioned into forward edges that form a DAG, and backedges according to our natural loop definition (the head dominates the tail)AXC DFEntryA15-745 Lecture 17 3/20/2007215-745 © Tim Callahan 5Ok, let's find all the cycles• Actually, usually want to find strongly connected components (SCC)• SCC: every node in the SCC can reach every other node in that SCC by some directed path• Can SCCs be nested?• SCCs important in many areas – e.g. for cyclic scheduling, you want to find the SCCs in the DFG• Singletons – not part of a cycle, their own SCC15-745 © Tim Callahan 6Ok, let's find all the cycles• Actually, usually want to find strongly connected components (SCC)• SCC: every node in the SCC can read every other node in that SCC by some directed path• Can SCCs be nested? NO• SCCs important in many areas – e.g. for cyclic scheduling, you want to find the SCCs in the DFG• Singletons – not part of a cycle, their own SCCevery node belongs to exactly one SCC15-745 © Tim Callahan 7Ok, let's find all the cycles• Actually, usually want to find strongly connected components (SCC)• SCC: every node in the SCC can read every other node in that SCC by some directed path• Can SCCs be nested? NO• SCCs important in many areas – e.g. for cyclic scheduling, you want to find the SCCs in the DFG• Singletons – not part of a cycle, their own SCCevery node belongs to exactly one SCCwell…15-745 © Tim Callahan 8Finding SCCs: Tarjan's Algorithmvisit(v){N[v] = c; /* Mark v visited by assigning it a visit number. */L[v] = c; /* Low-link initially equal to visit number. */c++;push v onto the stack;for each w in OUT(v) {if N[w] == UNDEFINED { /* N[w] == UNDEFINED means w is unvisited. */visit(w);L[v] = min(L[v], L[w]); /* Low-link number can propagate upward. */} else if w is on the stack {L[v] = min(L[v], N[w]);}}/* Check if SC component found. */if L[v] == N[v] {pop vertices off stack down to v; /* These make up an SC component. */}}this is the subtlety...15-745 Lecture 17 3/20/2007315-745 © Tim Callahan 9Finding SCCs: Tarjan's Algorithmmain_program {c : = 0; /* c is the counter for visit numbers. */for each vertex, v, in the graph,N[v] = UNDEFINED /* Mark v "unvisited". */visit(v0); /* v0 is the starting vertex. */}15-745 © Tim Callahan 10Finding SCCs: Tarjan's Algorithmabd cefgh ijvisiting: astack:N0L0a15-745 © Tim Callahan 11Finding SCCs: Tarjan's Algorithmabd cefgh ijvisiting: bstack:N0L0aN1L1b15-745 © Tim Callahan 12Finding SCCs: Tarjan's Algorithmabd cefgh ijvisiting: cstack:N0L0aN1L1bN2L2 c15-745 Lecture 17 3/20/2007415-745 © Tim Callahan 13Finding SCCs: Tarjan's Algorithmabd cefgh ijvisiting: cstack:N0L0aN1L1bN2L2 cc sees visited successor c;L[c] = min(L[c],N[c]) 15-745 © Tim Callahan 14Finding SCCs: Tarjan's Algorithmabd cefgh ijvisiting: estack:N0L0aN1L1bN2L2 ceN3L3 15-745 © Tim Callahan 15Finding SCCs: Tarjan's Algorithmabd cefgh ijvisiting: estack:N0L0aN1L1bN2L2 ceN3L1 e sees visited successor b;L[e] = min(L[e],N[b]) Copyright Tim Callahan15-745 © Tim Callahan 16Finding SCCs: Tarjan's Algorithmabd cefgh ijvisiting: fstack:N0L0aN1L1bN2L2 ceN3L1 Copyright Tim CallahanfN4L415-745 Lecture 17 3/20/2007515-745 © Tim Callahan 17Finding SCCs: Tarjan's Algorithmabd cefgh ijvisiting: gstack:N0L0aN1L1bN2L2 ceN3L1 Copyright Tim CallahanfN4L4 gN5L5 15-745 © Tim Callahan 18Finding SCCs: Tarjan's Algorithmabd cefgh ijvisiting: hstack:N0L0aN1L1bN2L2 ceN3L1 Copyright Tim CallahanfN4L4 gN5L5 N6L6 h15-745 © Tim Callahan 19Finding SCCs: Tarjan's Algorithmabd cefgh ijvisiting: istack:N0L0aN1L1bN2L2 ceN3L1 Copyright Tim CallahanfN4L4 gN5L5 N6L6 hN7L7 i15-745 © Tim Callahan 20Finding SCCs: Tarjan's Algorithmabd cefgh ijvisiting: istack:N0L0aN1L1bN2L2 ceN3L1 Copyright Tim CallahanfN4L4 gN5L5 N6L6 hN7L6 ii sees visited successor h;L[i] = min(L[i],N[h])15-745 Lecture 17 3/20/2007615-745 © Tim Callahan 21Finding SCCs: Tarjan's Algorithmabd cefgh ijvisiting: jstack:N0L0aN1L1bN2L2 ceN3L1 Copyright Tim CallahanfN4L4 gN5L5 N6L6 hN7L6 iN8L8 j15-745 © Tim Callahan 22Finding SCCs: Tarjan's Algorithmabd cefgh ijleaving: jstack:N0L0aN1L1bN2L2 ceN3L1 Copyright Tim CallahanfN4L4 gN5L5 N6L6 hN7L6 iN8L8 jj sees N=L;pops stack to createSCC {j}15-745 © Tim Callahan 23Finding SCCs: Tarjan's Algorithmabd cefgh ijleaving: istack:N0L0aN1L1bN2L2 ceN3L1 Copyright Tim CallahanfN4L4 gN5L5 N6L6 hN7L6 iN8L8 i sees N != L;does nothing15-745 © Tim Callahan 24Finding SCCs: Tarjan's Algorithmabd cefgh ijleaving: hstack:N0L0aN1L1bN2L2 ceN3L1 Copyright Tim CallahanfN4L4 gN5L5 N6L6 hN7L6 iN8L8 h sees N = L;pops stack to formSCC {i,h}15-745 Lecture 17 3/20/2007715-745 © Tim Callahan 25Finding SCCs: Tarjan's Algorithmabd cefgh ijleaving: gstack:N0L0aN1L1bN2L2 ceN3L1 Copyright Tim CallahanfN4L4 gN5L5 N6L6 N7L6 N8L8 g sees N = L;pops stack to formSCC {g}15-745 © Tim Callahan 26Finding SCCs: Tarjan's Algorithmabd cefgh ijleaving: fstack:N0L0aN1L1bN2L2 ceN3L1 Copyright Tim CallahanfN4L4 N5L5 N6L6 N7L6 N8L8 f sees N = L;pops stack to formSCC {f}15-745 © Tim Callahan 27Finding SCCs: Tarjan's Algorithmabd cefgh ijleaving: estack:N0L0aN1L1bN2L2 ceN3L1 Copyright Tim CallahanN4L4 N5L5 N6L6 N7L6 N8L8 e sees N != L;does nothing15-745 © Tim Callahan 28Finding SCCs: Tarjan's Algorithmabd cefgh ijleaving: cstack:N0L0aN1L1bN2L1 ceN3L1 Copyright Tim CallahanN4L4 N5L5 N6L6 N7L6 N8L8 c updatesL[c]=min(L[c],L[e]);sees L != N;does nothing15-745 Lecture 17 3/20/2007815-745 © Tim Callahan 29Finding SCCs: Tarjan's Algorithmabd cefgh ijvisiting: dstack:N0L0aN1L1bN2L1 ceN3L1 Copyright Tim
View Full Document
Unlocking...