buildDomTree computes the dominator tree of f using the LT algorithm. The first node is the distinguished root node.
(nodes []*node)
| 115 | // buildDomTree computes the dominator tree of f using the LT algorithm. |
| 116 | // The first node is the distinguished root node. |
| 117 | func buildDomTree(nodes []*node) { |
| 118 | // The step numbers refer to the original LT paper; the |
| 119 | // reordering is due to Georgiadis. |
| 120 | |
| 121 | // Clear any previous domInfo. |
| 122 | for _, b := range nodes { |
| 123 | b.dom = domInfo{index: -1} |
| 124 | } |
| 125 | |
| 126 | root := nodes[0] |
| 127 | |
| 128 | // The original (ssa) implementation had the precondition |
| 129 | // that all nodes are reachable, but because of Spaghetti's |
| 130 | // "broken edges", some nodes may be unreachable. |
| 131 | // We filter them out now with another graph traversal. |
| 132 | // The domInfo.index numbering is relative to this ordering. |
| 133 | // See other "reachable hack" comments for related parts. |
| 134 | // We should combine this into step 1. |
| 135 | var reachable []*node |
| 136 | var visit func(n *node) |
| 137 | visit = func(n *node) { |
| 138 | if n.dom.index < 0 { |
| 139 | n.dom.index = int32(len(reachable)) |
| 140 | reachable = append(reachable, n) |
| 141 | for _, imp := range n.imports { |
| 142 | visit(imp) |
| 143 | } |
| 144 | } |
| 145 | } |
| 146 | visit(root) |
| 147 | nodes = reachable |
| 148 | |
| 149 | n := len(nodes) |
| 150 | // Allocate space for 5 contiguous [n]*node arrays: |
| 151 | // sdom, parent, ancestor, preorder, buckets. |
| 152 | space := make([]*node, 5*n) |
| 153 | lt := ltState{ |
| 154 | sdom: space[0:n], |
| 155 | parent: space[n : 2*n], |
| 156 | ancestor: space[2*n : 3*n], |
| 157 | } |
| 158 | |
| 159 | // Step 1. Number vertices by depth-first preorder. |
| 160 | preorder := space[3*n : 4*n] |
| 161 | lt.dfs(root, 0, preorder) |
| 162 | |
| 163 | buckets := space[4*n : 5*n] |
| 164 | copy(buckets, preorder) |
| 165 | |
| 166 | // In reverse preorder... |
| 167 | for i := int32(n) - 1; i > 0; i-- { |
| 168 | w := preorder[i] |
| 169 | |
| 170 | // Step 3. Implicitly define the immediate dominator of each node. |
| 171 | for v := buckets[i]; v != w; v = buckets[v.dom.pre] { |
| 172 | u := lt.eval(v) |
| 173 | if lt.sdom[u.dom.index].dom.pre < i { |
| 174 | v.dom.idom = u |
no test coverage detected