.githooks/
compiler/
kernel/
lib/
examples/
std/
arch/
bits/
char/
collections/
fs/
hash/
lang/
alloc/
ast/
gen/
il/
binary/
tests/
cfg.rad
8.2 KiB
collect.rad
4.3 KiB
linkage.rad
4.8 KiB
program.rad
30.5 KiB
reader.rad
28.5 KiB
tests.rad
30.4 KiB
writer.rad
28.4 KiB
link/
printer/
verify/
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/binary/cfg.rad
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 | } |