1 // Copyright 2016 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 package ssa 6 7 // Code to compute lowest common ancestors in the dominator tree. 8 // https://en.wikipedia.org/wiki/Lowest_common_ancestor 9 // https://en.wikipedia.org/wiki/Range_minimum_query#Solution_using_constant_time_and_linearithmic_space 10 11 // lcaRange is a data structure that can compute lowest common ancestor queries 12 // in O(n lg n) precomputed space and O(1) time per query. 13 type lcaRange struct { 14 // Additional information about each block (indexed by block ID). 15 blocks []lcaRangeBlock 16 17 // Data structure for range minimum queries. 18 // rangeMin[k][i] contains the ID of the minimum depth block 19 // in the Euler tour from positions i to i+1<<k-1, inclusive. 20 rangeMin [][]ID 21 } 22 23 type lcaRangeBlock struct { 24 b *Block 25 parent ID // parent in dominator tree. 0 = no parent (entry or unreachable) 26 firstChild ID // first child in dominator tree 27 sibling ID // next child of parent 28 pos int32 // an index in the Euler tour where this block appears (any one of its occurrences) 29 depth int32 // depth in dominator tree (root=0, its children=1, etc.) 30 } 31 32 func makeLCArange(f *Func) *lcaRange { 33 dom := f.Idom() 34 35 // Build tree 36 blocks := make([]lcaRangeBlock, f.NumBlocks()) 37 for _, b := range f.Blocks { 38 blocks[b.ID].b = b 39 if dom[b.ID] == nil { 40 continue // entry or unreachable 41 } 42 parent := dom[b.ID].ID 43 blocks[b.ID].parent = parent 44 blocks[b.ID].sibling = blocks[parent].firstChild 45 blocks[parent].firstChild = b.ID 46 } 47 48 // Compute euler tour ordering. 49 // Each reachable block will appear #children+1 times in the tour. 50 tour := make([]ID, 0, f.NumBlocks()*2-1) 51 type queueEntry struct { 52 bid ID // block to work on 53 cid ID // child we're already working on (0 = haven't started yet) 54 } 55 q := []queueEntry{{f.Entry.ID, 0}} 56 for len(q) > 0 { 57 n := len(q) - 1 58 bid := q[n].bid 59 cid := q[n].cid 60 q = q[:n] 61 62 // Add block to tour. 63 blocks[bid].pos = int32(len(tour)) 64 tour = append(tour, bid) 65 66 // Proceed down next child edge (if any). 67 if cid == 0 { 68 // This is our first visit to b. Set its depth. 69 blocks[bid].depth = blocks[blocks[bid].parent].depth + 1 70 // Then explore its first child. 71 cid = blocks[bid].firstChild 72 } else { 73 // We've seen b before. Explore the next child. 74 cid = blocks[cid].sibling 75 } 76 if cid != 0 { 77 q = append(q, queueEntry{bid, cid}, queueEntry{cid, 0}) 78 } 79 } 80 81 // Compute fast range-minimum query data structure 82 var rangeMin [][]ID 83 rangeMin = append(rangeMin, tour) // 1-size windows are just the tour itself. 84 for logS, s := 1, 2; s < len(tour); logS, s = logS+1, s*2 { 85 r := make([]ID, len(tour)-s+1) 86 for i := 0; i < len(tour)-s+1; i++ { 87 bid := rangeMin[logS-1][i] 88 bid2 := rangeMin[logS-1][i+s/2] 89 if blocks[bid2].depth < blocks[bid].depth { 90 bid = bid2 91 } 92 r[i] = bid 93 } 94 rangeMin = append(rangeMin, r) 95 } 96 97 return &lcaRange{blocks: blocks, rangeMin: rangeMin} 98 } 99 100 // find returns the lowest common ancestor of a and b. 101 func (lca *lcaRange) find(a, b *Block) *Block { 102 if a == b { 103 return a 104 } 105 // Find the positions of a and bin the Euler tour. 106 p1 := lca.blocks[a.ID].pos 107 p2 := lca.blocks[b.ID].pos 108 if p1 > p2 { 109 p1, p2 = p2, p1 110 } 111 112 // The lowest common ancestor is the minimum depth block 113 // on the tour from p1 to p2. We've precomputed minimum 114 // depth blocks for powers-of-two subsequences of the tour. 115 // Combine the right two precomputed values to get the answer. 116 logS := uint(log2(int64(p2 - p1))) 117 bid1 := lca.rangeMin[logS][p1] 118 bid2 := lca.rangeMin[logS][p2-1<<logS+1] 119 if lca.blocks[bid1].depth < lca.blocks[bid2].depth { 120 return lca.blocks[bid1].b 121 } 122 return lca.blocks[bid2].b 123 } 124
