lib/std/lang/il/binary/cfg.rad 8.2 KiB raw
1
//! Control flow of decoded functions: predecessors and loop depth.
2
//!
3
//! The wire format carries neither. The decoder derives them from the
4
//! terminator of each block, so they always agree with the instructions.
5
6
use std::mem::heap;
7
use std::lang::il;
8
use std::lang::il::binary;
9
10
/// Search state of a block in the depth-first walk.
11
union Visit: Copy {
12
    /// Not reached yet.
13
    Fresh,
14
    /// On the current path from the entry block.
15
    Open,
16
    /// Fully explored.
17
    Done,
18
}
19
20
/// Edges of a function in compressed form. The successors of block `b` are
21
/// `succs[succStart[b]..succStart[b + 1]]`, and its predecessors are
22
/// `preds[predStart[b]..predStart[b + 1]]`.
23
record Edges {
24
    /// Index in `succs` of the first successor of each block, and the edge count.
25
    succStart: *[u32],
26
    /// Targets of the edges, grouped by source block, without repeats.
27
    succs: *[u32],
28
    /// Index in `preds` of the first predecessor of each block, and the edge count.
29
    predStart: *[u32],
30
    /// Sources of the edges, grouped by target block in increasing order.
31
    preds: *[u32],
32
}
33
34
/// Append the targets of the terminator of `block` to `targets`. Repeated targets of
35
/// one terminator are kept once.
36
fn terminatorTargets(
37
    block: il::Block,
38
    cases: &[il::SwitchCase],
39
    first: u32,
40
    targets: &mut *mut [u32],
41
    a: &heap::Heap
42
) throws (binary::Error) {
43
    if block.instrs.len == 0 {
44
        return;
45
    }
46
    match block.instrs[block.instrs.len - 1] {
47
        case il::Instr::Jmp { target, .. } => {
48
            try addTarget(targets, first, target, a);
49
        }
50
        case il::Instr::Br { thenTarget, elseTarget, .. } => {
51
            try addTarget(targets, first, thenTarget, a);
52
            try addTarget(targets, first, elseTarget, a);
53
        }
54
        case il::Instr::Switch { defaultTarget, cases: range, .. } => {
55
            try addTarget(targets, first, defaultTarget, a);
56
            for branch in &cases[range.start .. range.start + range.len] {
57
                try addTarget(targets, first, branch.target, a);
58
            }
59
        }
60
        else => {}
61
    }
62
}
63
64
/// Append `target` to `targets` unless the terminator that starts at `first` has it already.
65
fn addTarget(targets: &mut *mut [u32], first: u32, target: u32, a: &heap::Heap)
66
    throws (binary::Error)
67
{
68
    for i in first .. targets.len {
69
        if targets[i] == target {
70
            return;
71
        }
72
    }
73
    try targets.append(target, a) catch {
74
        throw binary::Error::Storage;
75
    };
76
}
77
78
/// Build the edge lists of the blocks from their terminators. Targets must be in range.
79
fn collect(blocks: &[il::Block], cases: &[il::SwitchCase], a: &heap::Heap) -> Edges
80
    throws (binary::Error)
81
{
82
    let n = blocks.len;
83
    let mut succStart: *mut [u32] = &mut [];
84
    let mut succs: *mut [u32] = &mut [];
85
    for b in 0 .. n {
86
        let first = succs.len;
87
        try succStart.append(first, a) catch {
88
            throw binary::Error::Storage;
89
        };
90
        try terminatorTargets(blocks[b], cases, first, &mut succs, a);
91
    }
92
    let total = succs.len;
93
    try succStart.append(total, a) catch {
94
        throw binary::Error::Storage;
95
    };
96
    // Count the predecessors of each block, then place the sources in increasing order.
97
    let mut predStart: *mut [u32] = &mut [];
98
    try predStart.resize(n + 1, 0, a) catch {
99
        throw binary::Error::Storage;
100
    };
101
    for i in 0 .. total {
102
        set predStart[succs[i] + 1] += 1;
103
    }
104
    for b in 0 .. n {
105
        set predStart[b + 1] += predStart[b];
106
    }
107
    let mut next: *mut [u32] = &mut [];
108
    try next.resize(n, 0, a) catch {
109
        throw binary::Error::Storage;
110
    };
111
    let mut preds: *mut [u32] = &mut [];
112
    try preds.resize(total, 0, a) catch {
113
        throw binary::Error::Storage;
114
    };
115
    for b in 0 .. n {
116
        for i in succStart[b] .. succStart[b + 1] {
117
            let target = succs[i];
118
            set preds[predStart[target] + next[target]] = b;
119
            set next[target] += 1;
120
        }
121
    }
122
    return Edges {
123
        succStart: &succStart[..], succs: &succs[..], predStart: &predStart[..], preds: &preds[..]
124
    };
125
}
126
127
/// Find the back edges of the graph reachable from the entry block. An edge is a back
128
/// edge when its target is on the current path. Return the sources in `from` and
129
/// the targets, the loop headers, in `to`.
130
fn backEdges(
131
    edges: &Edges,
132
    from: &mut *mut [u32],
133
    to: &mut *mut [u32],
134
    a: &heap::Heap
135
) throws (binary::Error) {
136
    let n = edges.predStart.len - 1;
137
    if n == 0 {
138
        return;
139
    }
140
    let mut visit: *mut [Visit] = &mut [];
141
    let mut next: *mut [u32] = &mut [];
142
    let mut path: *mut [u32] = &mut [];
143
    try visit.resize(n, Visit::Fresh, a) catch {
144
        throw binary::Error::Storage;
145
    };
146
    try next.resize(n, 0, a) catch {
147
        throw binary::Error::Storage;
148
    };
149
    try path.append(0, a) catch {
150
        throw binary::Error::Storage;
151
    };
152
    set visit[0] = Visit::Open;
153
    while path.len > 0 {
154
        let b = path[path.len - 1];
155
        let at = edges.succStart[b] + next[b];
156
        if at == edges.succStart[b + 1] {
157
            set visit[b] = Visit::Done;
158
            path.delete(path.len - 1);
159
            continue;
160
        }
161
        let target = edges.succs[at];
162
        set next[b] += 1;
163
        match visit[target] {
164
            case Visit::Fresh => {
165
                set visit[target] = Visit::Open;
166
                try path.append(target, a) catch {
167
                    throw binary::Error::Storage;
168
                };
169
            }
170
            case Visit::Open => {
171
                try from.append(b, a) catch {
172
                    throw binary::Error::Storage;
173
                };
174
                try to.append(target, a) catch {
175
                    throw binary::Error::Storage;
176
                };
177
            }
178
            case Visit::Done => {}
179
        }
180
    }
181
}
182
183
/// Count, for each block, the natural loops that contain it. The loop of a header
184
/// is the header and every block that reaches a back edge source without passing
185
/// the header. Loops that share a header count once.
186
fn loopDepths(edges: &Edges, a: &heap::Heap) -> *mut [u32] throws (binary::Error) {
187
    let n = edges.predStart.len - 1;
188
    let mut from: *mut [u32] = &mut [];
189
    let mut to: *mut [u32] = &mut [];
190
    try backEdges(edges, &mut from, &mut to, a);
191
192
    let mut depth: *mut [u32] = &mut [];
193
    let mut mark: *mut [u32] = &mut [];
194
    let mut counted: *mut [bool] = &mut [];
195
    let mut work: *mut [u32] = &mut [];
196
    try depth.resize(n, 0, a) catch {
197
        throw binary::Error::Storage;
198
    };
199
    try mark.resize(n, 0, a) catch {
200
        throw binary::Error::Storage;
201
    };
202
    try counted.resize(n, false, a) catch {
203
        throw binary::Error::Storage;
204
    };
205
    for i in 0 .. to.len {
206
        let header = to[i];
207
        if counted[header] {
208
            continue;
209
        }
210
        set counted[header] = true;
211
        // Blocks of this loop carry the stamp, which differs for every header.
212
        let stamp = header + 1;
213
        set mark[header] = stamp;
214
        for j in i .. to.len {
215
            if to[j] == header {
216
                try work.append(from[j], a) catch {
217
                    throw binary::Error::Storage;
218
                };
219
            }
220
        }
221
        while work.len > 0 {
222
            let b = work[work.len - 1];
223
            work.delete(work.len - 1);
224
            if mark[b] == stamp {
225
                continue;
226
            }
227
            set mark[b] = stamp;
228
            for k in edges.predStart[b] .. edges.predStart[b + 1] {
229
                try work.append(edges.preds[k], a) catch {
230
                    throw binary::Error::Storage;
231
                };
232
            }
233
        }
234
        for b in 0 .. n {
235
            if mark[b] == stamp {
236
                set depth[b] += 1;
237
            }
238
        }
239
    }
240
    return depth;
241
}
242
243
/// Set the predecessors and the loop depth of every block of a function from
244
/// its terminators. `cases` is the case pool the switch terminators index.
245
/// Every branch target must be a block of the function.
246
export fn link(blocks: &mut [il::Block], cases: &[il::SwitchCase], a: &heap::Heap)
247
    throws (binary::Error)
248
{
249
    let edges = try collect(blocks, cases, a);
250
    let depth = try loopDepths(&edges, a);
251
    for b in 0 .. blocks.len {
252
        set blocks[b].preds = &edges.preds[edges.predStart[b] .. edges.predStart[b + 1]];
253
        set blocks[b].loopDepth = depth[b];
254
    }
255
}