lib/std/lang/il/verify/flow.rad 6.9 KiB 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
}