.githooks/
compiler/
kernel/
lib/
examples/
std/
arch/
bits/
char/
collections/
fs/
hash/
lang/
alloc/
ast/
gen/
il/
binary/
link/
printer/
verify/
data.rad
12.4 KiB
flow.rad
6.9 KiB
layout.rad
30.9 KiB
linking.rad
7.2 KiB
tests.rad
216.6 KiB
binary.rad
14.7 KiB
link.rad
11.8 KiB
printer.rad
31.7 KiB
verify.rad
99.5 KiB
layout/
lower/
manifest/
module/
parser/
resolver/
scanner/
sexpr/
alloc.rad
1.2 KiB
ast.rad
36.0 KiB
gen.rad
513 B
il.rad
48.5 KiB
layout.rad
6.9 KiB
lower.rad
487.6 KiB
manifest.rad
22.5 KiB
module.rad
17.8 KiB
package.rad
1.5 KiB
parser.rad
114.1 KiB
pretty.rad
103.6 KiB
resolver.rad
508.1 KiB
scanner.rad
19.3 KiB
sexpr.rad
7.1 KiB
strings.rad
3.3 KiB
types.rad
620 B
mem/
sys/
arch.rad
68 B
bits.rad
1.6 KiB
char.rad
1.5 KiB
collections.rad
39 B
fmt.rad
11.6 KiB
fs.rad
11.0 KiB
hash.rad
41 B
intrinsics.rad
467 B
io.rad
1.7 KiB
lang.rad
335 B
mem.rad
12.0 KiB
mem.ras
919 B
process.rad
6.2 KiB
std.manifest
4.9 KiB
std.rad
349 B
sys.rad
1.0 KiB
testing.rad
2.4 KiB
tests.rad
26.6 KiB
vec.rad
3.2 KiB
scripts/
seed/
sublime/
test/
vim/
.gitignore
333 B
.gitsigners
224 B
AGENTS.md
8.3 KiB
CONTRIBUTING
2.1 KiB
LICENSE
1.1 KiB
Makefile
2.5 KiB
README
3.4 KiB
STYLE
3.2 KiB
std.lib
2.1 KiB
std.lib.test
1.1 KiB
lib/std/lang/il/verify/flow.rad
raw
| 1 | //! Control flow analysis of the RIL verifier: reverse postorder, immediate dominators |
| 2 | //! and constant-time dominance queries for the blocks of one function. |
| 3 | //! |
| 4 | //! Dominators come from the algorithm of Cooper, Harvey and Kennedy. Dominance queries |
| 5 | //! use the interval numbering of the dominator tree: a block dominates the blocks whose |
| 6 | //! preorder number falls inside its subtree. Blocks that the entry block cannot reach have |
| 7 | //! no number, and dominate only themselves. |
| 8 | |
| 9 | use std::mem::heap; |
| 10 | use std::lang::il; |
| 11 | use std::lang::il::verify; |
| 12 | |
| 13 | /// Number of a block that the entry block cannot reach. |
| 14 | export constant UNREACHABLE: u32 = 0xffffffff; |
| 15 | /// Mark of a block that the depth-first search has entered. |
| 16 | constant VISITED: u32 = 0xfffffffe; |
| 17 | /// Immediate dominator of a block that has none yet. |
| 18 | constant UNDEFINED: u32 = 0xffffffff; |
| 19 | |
| 20 | /// Scratch tables of the analysis. The tables are sized for the largest function, and |
| 21 | /// [`compute`] fills the part that the current function uses. |
| 22 | export record Flow { |
| 23 | /// Blocks in reverse postorder, followed by the unreachable blocks in index order. |
| 24 | order: *mut [u32], |
| 25 | /// Reverse postorder number of each block, or [`UNREACHABLE`]. |
| 26 | number: *mut [u32], |
| 27 | /// Reverse postorder number of the immediate dominator, by reverse postorder number. |
| 28 | idom: *mut [u32], |
| 29 | /// Size of the dominator subtree, by reverse postorder number. |
| 30 | size: *mut [u32], |
| 31 | /// Preorder number in the dominator tree, by reverse postorder number. |
| 32 | pre: *mut [u32], |
| 33 | /// Search stack, and then the next free preorder number of each subtree. |
| 34 | stack: *mut [u32], |
| 35 | /// Index of the next successor to follow in the search, by block. |
| 36 | cursor: *mut [u32], |
| 37 | /// Start of the predecessor list of each block, by reverse postorder number. |
| 38 | predStart: *mut [u32], |
| 39 | /// Reverse postorder numbers of the predecessors of the blocks that are reachable. |
| 40 | preds: *mut [u32], |
| 41 | } |
| 42 | |
| 43 | /// Allocate a table of `n` entries. |
| 44 | fn table(n: u32, a: &heap::Heap) -> *mut [u32] throws (verify::Error) { |
| 45 | let mut t: *mut [u32] = &mut []; |
| 46 | try t.resize(n, 0, a) catch { |
| 47 | throw verify::STORAGE; |
| 48 | }; |
| 49 | return t; |
| 50 | } |
| 51 | |
| 52 | /// Allocate tables for functions of up to `blocks` blocks and `edges` control flow edges. |
| 53 | export fn new(blocks: u32, edges: u32, a: &heap::Heap) -> Flow throws (verify::Error) { |
| 54 | return Flow { |
| 55 | order: try table(blocks, a), |
| 56 | number: try table(blocks, a), |
| 57 | idom: try table(blocks, a), |
| 58 | size: try table(blocks, a), |
| 59 | pre: try table(blocks, a), |
| 60 | stack: try table(blocks, a), |
| 61 | cursor: try table(blocks, a), |
| 62 | predStart: try table(blocks + 1, a), |
| 63 | preds: try table(edges, a), |
| 64 | }; |
| 65 | } |
| 66 | |
| 67 | /// Analyze `func`, whose blocks all end with a terminator that targets a block of `func`. |
| 68 | export fn compute(f: &mut Flow, func: *il::Fn) { |
| 69 | let n = func.blocks.len; |
| 70 | for b in 0 .. n { |
| 71 | set f.number[b] = UNREACHABLE; |
| 72 | set f.cursor[b] = 0; |
| 73 | } |
| 74 | // Depth-first search from the entry block. Blocks leave the stack in postorder. |
| 75 | let mut depth: u32 = 1; |
| 76 | let mut reached: u32 = 0; |
| 77 | set f.stack[0] = 0; |
| 78 | set f.number[0] = VISITED; |
| 79 | while depth > 0 { |
| 80 | let b = f.stack[depth - 1]; |
| 81 | let k = f.cursor[b]; |
| 82 | if k < il::successorCount(func, b) { |
| 83 | set f.cursor[b] = k + 1; |
| 84 | let target = il::successor(func, b, k); |
| 85 | if f.number[target] == UNREACHABLE { |
| 86 | set f.number[target] = VISITED; |
| 87 | set f.stack[depth] = target; |
| 88 | set depth += 1; |
| 89 | } |
| 90 | } else { |
| 91 | set f.order[reached] = b; |
| 92 | set reached += 1; |
| 93 | set depth -= 1; |
| 94 | } |
| 95 | } |
| 96 | for i in 0 .. reached / 2 { |
| 97 | let swap = f.order[i]; |
| 98 | set f.order[i] = f.order[reached - 1 - i]; |
| 99 | set f.order[reached - 1 - i] = swap; |
| 100 | } |
| 101 | for i in 0 .. reached { |
| 102 | set f.number[f.order[i]] = i; |
| 103 | } |
| 104 | let mut next = reached; |
| 105 | for b in 0 .. n { |
| 106 | if f.number[b] == UNREACHABLE { |
| 107 | set f.order[next] = b; |
| 108 | set next += 1; |
| 109 | } |
| 110 | } |
| 111 | predecessors(f, func, reached); |
| 112 | dominators(f, reached); |
| 113 | } |
| 114 | |
| 115 | /// Build the predecessor lists of the reachable blocks, by reverse postorder number. |
| 116 | fn predecessors(f: &mut Flow, func: *il::Fn, reached: u32) { |
| 117 | for i in 0 .. reached + 1 { |
| 118 | set f.predStart[i] = 0; |
| 119 | } |
| 120 | for i in 0 .. reached { |
| 121 | let b = f.order[i]; |
| 122 | for k in 0 .. il::successorCount(func, b) { |
| 123 | set f.predStart[f.number[il::successor(func, b, k)] + 1] += 1; |
| 124 | } |
| 125 | } |
| 126 | for i in 0 .. reached { |
| 127 | set f.predStart[i + 1] += f.predStart[i]; |
| 128 | set f.cursor[i] = 0; |
| 129 | } |
| 130 | for i in 0 .. reached { |
| 131 | let b = f.order[i]; |
| 132 | for k in 0 .. il::successorCount(func, b) { |
| 133 | let target = f.number[il::successor(func, b, k)]; |
| 134 | set f.preds[f.predStart[target] + f.cursor[target]] = i; |
| 135 | set f.cursor[target] += 1; |
| 136 | } |
| 137 | } |
| 138 | } |
| 139 | |
| 140 | /// Find the nearest common dominator of two blocks with the dominators found so far. |
| 141 | fn intersect(idom: &[u32], a: u32, b: u32) -> u32 { |
| 142 | let mut x = a; |
| 143 | let mut y = b; |
| 144 | while x <> y { |
| 145 | while x > y { |
| 146 | set x = idom[x]; |
| 147 | } |
| 148 | while y > x { |
| 149 | set y = idom[y]; |
| 150 | } |
| 151 | } |
| 152 | return x; |
| 153 | } |
| 154 | |
| 155 | /// Compute the immediate dominators of the `reached` reachable blocks, and number the |
| 156 | /// dominator tree. |
| 157 | fn dominators(f: &mut Flow, reached: u32) { |
| 158 | for i in 0 .. reached { |
| 159 | set f.idom[i] = UNDEFINED; |
| 160 | } |
| 161 | set f.idom[0] = 0; |
| 162 | let mut changed = true; |
| 163 | while changed { |
| 164 | set changed = false; |
| 165 | for i in 1 .. reached { |
| 166 | let mut best = UNDEFINED; |
| 167 | for j in f.predStart[i] .. f.predStart[i + 1] { |
| 168 | let p = f.preds[j]; |
| 169 | if f.idom[p] == UNDEFINED { |
| 170 | continue; |
| 171 | } |
| 172 | set best = p if best == UNDEFINED else intersect(&f.idom[..], best, p); |
| 173 | } |
| 174 | if f.idom[i] <> best { |
| 175 | set f.idom[i] = best; |
| 176 | set changed = true; |
| 177 | } |
| 178 | } |
| 179 | } |
| 180 | // A dominator comes before the blocks it dominates, so subtree sizes accumulate |
| 181 | // from the last block back, and preorder numbers are handed out from the first. |
| 182 | for i in 0 .. reached { |
| 183 | set f.size[i] = 1; |
| 184 | } |
| 185 | let mut last = reached; |
| 186 | while last > 1 { |
| 187 | set last -= 1; |
| 188 | set f.size[f.idom[last]] += f.size[last]; |
| 189 | } |
| 190 | set f.pre[0] = 0; |
| 191 | set f.stack[0] = 1; |
| 192 | for i in 1 .. reached { |
| 193 | let parent = f.idom[i]; |
| 194 | set f.pre[i] = f.stack[parent]; |
| 195 | set f.stack[parent] += f.size[i]; |
| 196 | set f.stack[i] = f.pre[i] + 1; |
| 197 | } |
| 198 | } |
| 199 | |
| 200 | /// Whether block `a` dominates block `b`. |
| 201 | export fn dominates(f: &Flow, a: u32, b: u32) -> bool { |
| 202 | let x = f.number[a]; |
| 203 | let y = f.number[b]; |
| 204 | if x == UNREACHABLE or y == UNREACHABLE { |
| 205 | return a == b; |
| 206 | } |
| 207 | return f.pre[x] <= f.pre[y] and f.pre[y] < f.pre[x] + f.size[x]; |
| 208 | } |