Optimizing Compilers CISC 673 Spring 2011 Static Single Assignment John Cavazos University of Delaware UNIVERSITY OF DELAWARE COMPUTER & INFORMATION SCIENCES DEPARTMENT Placing functions Safe to put functions for every variable at every join point But:
inefficient not necessarily sparse! loses information Goal: minimal nodes, subject to need UNIVERSITY OF DELAWARE COMPUTER & INFORMATION SCIENCES DEPARTMENT 2 Function Requirement Node Z needs function for v if: Z is convergence point for two paths both originating nodes contain assignments to v or also need functions for v v=1 v=2
Z v1 = 1 v2 = 2 v3=(vv1,v2) Z UNIVERSITY OF DELAWARE COMPUTER & INFORMATION SCIENCES DEPARTMENT 3 Minimal Placement of functions Nave computation is expensive Can be done in O(N) time Relies on dominance frontier computation
[Cytron et al., 1991] UNIVERSITY OF DELAWARE COMPUTER & INFORMATION SCIENCES DEPARTMENT 4 Some Dominance Relationships x dominates y (x dom y) in CFG, all paths to y go through x Dom(v) = set of all nodes that dominate v Entry dominates every node Every node dominates itself
UNIVERSITY OF DELAWARE COMPUTER & INFORMATION SCIENCES DEPARTMENT 5 Finding Dominators Dom(n) = {n} ( p PRED(n) Dom(p) ) A node dominates itself! A node that dominates all predecessors UNIVERSITY OF DELAWARE COMPUTER & INFORMATION SCIENCES DEPARTMENT 6 Finding Dominators
Dom(n) = {n} ( p PRED(n) Dom(p) ) DOM(vEntry) = {Entry} Algorithm: For n V-{Entry} DOM(vn) = V repeat changed = false for n V-{Entry} olddom = DOM(vn) DOM(vn) = {n} (vp PRED(vn) DOM(vp)) if DOM(vn) olddom changed = true UNIVERSITY OF DELAWARE COMPUTER & INFORMATION SCIENCES DEPARTMENT 7 Dominator Algorithm Example A (vEntry) DOM(vEntry) = {Entry}
for v V-{Entry} Dom DOM(vv) = C D Dom E F repeat changed = false for n V-{Entry} olddom = DOM(vn) DOM(vn) = {n} (vp2 PRED(vn) DOM(vp)) Dom
B Dom V Dom if DOM(vn) olddom changed = true Dom G (vExit) Dom UNIVERSITY OF DELAWARE COMPUTER & INFORMATION SCIENCES DEPARTMENT
8 Dominator Algorithm Example A (vEntry) B C Dom: A DOM(vv) = V repeat changed = false for n V-{Entry} olddom = DOM(vn) DOM(vn) = {n} (vp2 PRED(vn) DOM(vp)) Dom: A,B Dom: A, B, C E
F DOM(vEntry) = {Entry} for v V-{Entry} Dom: A, B, E, F D Dom: A, B, D if DOM(vn) olddom changed = true Dom: A, B, E G (vExit)
Dom: A, B, E G UNIVERSITY OF DELAWARE COMPUTER & INFORMATION SCIENCES DEPARTMENT 9 Other Dominators Strict dominators Dom!(v) = Dom(v) {v} Immediate dominator Idom(v) = closest strict dominator of v Idom induces tree
UNIVERSITY OF DELAWARE COMPUTER & INFORMATION SCIENCES DEPARTMENT 10 Dominator Example A (vEntry) C F Dom: A Dom! Idom Dom: A, B B Dom! Dom: A, Idom B, Dom: A, B, C D
D Dom! Dom! Idom Idom Dom: A, B, E E Dom! Dom: A, B, E, Idom F G (vExit) Dom! Idom Dom: A, B, E, G Dom! Idom UNIVERSITY OF DELAWARE COMPUTER & INFORMATION SCIENCES DEPARTMENT 11
Dominator Tree A (vEntry) A (vEntry) B B C D C E F D E G (vExit) F
G (vExit) UNIVERSITY OF DELAWARE COMPUTER & INFORMATION SCIENCES DEPARTMENT 12 Dominance Frontiers (intuitively) The dominance frontier DF(X) is set of all nodes Y such that: X dominates a predecessor of Y But X does not strictly dominate Y The fringe just beyond the region X dominates UNIVERSITY OF DELAWARE COMPUTER & INFORMATION SCIENCES DEPARTMENT 13
Dominance Frontiers (formally) DF(X) = {Y|( P PRED(Y): X Dom P) and X Dom! Y} UNIVERSITY OF DELAWARE COMPUTER & INFORMATION SCIENCES DEPARTMENT 14 Dominance Frontiers (visually) UNIVERSITY OF DELAWARE COMPUTER & INFORMATION SCIENCES DEPARTMENT 15 Why Dominance Frontiers Dominance frontier criterion:
if node x contains def of a, then any node z in DF(x) needs a function for a intuition: at least two non-intersecting paths converge to z, and one path must contain node strictly dominated by x UNIVERSITY OF DELAWARE COMPUTER & INFORMATION SCIENCES DEPARTMENT 16 Dominance Frontier Example S X A node y is in dominance frontier of node x if:
x dominates predecessor of y but does not strictly dominate y B DF(vX) = {Y|(v P PRED(vY): X Dom P) and X Dom! Y) UNIVERSITY OF DELAWARE COMPUTER & INFORMATION SCIENCES DEPARTMENT 17 Next Lecture Computing dominance frontiers Computing SSA form UNIVERSITY OF DELAWARE COMPUTER & INFORMATION SCIENCES DEPARTMENT 18