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