2控制流分析.PDF

2 2.1 2.1 ABAB (basic block) 2.2 DominatorPost-dominator DominatorAB DominatorBAA Dom B 2.2 Dominance Dominance(x Dom x)(x Dom y y Dom zx Dom z)(x Dom yy Dom x)x Dom yx!=yxystrict dominator xystrict dominator(Dom!)xy dominator ww Dom xsyimmediate dominator(IDom) immediate dominatordominance Post-DominatorDominator x PDom yyx dominator lockunlock Dominatorimmediate dominator immediate dominatordominator dominatordominator 2.3Lingodominator 2.3 dominator dominator 2.4 2.4 dominator entrydominator(entry ) (Dom) dominator 2.5 2.5 DFS (pre-order)(post- order)dominator () (reverse post-order) reverse post-orderpre-order [1] Dominance Tree2.62.4 (undefined)dominance ()reverse postorderb (processed)doms[b]Undefined , bimmediate dominatorintersect(b1,b2) intersect()(post order)b1b2 whilereverse postorderreverse postorder (postorder) 2.6 immediate dominatordominance tree 2.42.6(entry node)dominator ( )dominance 2.6 Dominance Tree 2.3 2.7 2.7 yxxy P xyP nnyynpost dominator yxstrict post dominatorxy xy2.8 54644 656,7,857 PDOM! 68 PDOM! 7 2.8 2.4 (DFS) forward edge cross edgebackward edge backward edgecross edgebackward edge2.9 83(backward edge)6878DFS (cross edge)AB BA 2.9 (Strong connected component)Tarjan2.10 TarjanO(n+m)n m()preorder n.ordern n.rootn nn n(n) “” root()2.10repeat/until v.root = n.orderroot Tarjan[2] Clang 2.10 Tarjan 2.5 (natural loops) goto goto T1T2 (reducible) A. T1: n B. T2: [1] Keith D. Cooper, Timothy J. Harvey and Ken Kennedy. “A Simple, Fast Dominance Algori