/** * CFG analyses over a ZIR body: predecessors, reverse postorder, and * dominators (Cooper–Harvey–Kennedy). Shared by the verifier and the * emitter. Computed once per body on demand; bodies are not mutated * between construction and use in the current pipeline. */ import { IrBody, IrScratch } from './ir.zena'; export final class IrCfg { body: IrBody; // The per-block lists are packed, block b's entries being // list[start[b] .. start[b + 1]): one array per table rather than one // per block, for a structure built several times per body per pass. /** Predecessor block ids per block. */ predStart: GrowableArray; predList: GrowableArray; /** Successor block ids per block (edge order, duplicates preserved). */ succStart: GrowableArray; succList: GrowableArray; /** Blocks in reverse postorder (entry first). */ rpo: GrowableArray; /** Reverse-postorder number per block; -1 = unreachable from entry. */ rpoIndex: GrowableArray; /** Immediate dominator per block; entry's is itself; -1 = unreachable. */ idom: GrowableArray; /** Dominator-tree children per block, in ascending RPO order. */ domChildStart: GrowableArray; domChildList: GrowableArray; /** Where the tables came from; null means fresh lists of its own. */ #scratch: IrScratch | null; predCount(block: i32): i32 { return this.predStart[block + 1] - this.predStart[block]; } pred(block: i32, k: i32): i32 { return this.predList[this.predStart[block] + k]; } succCount(block: i32): i32 { return this.succStart[block + 1] - this.succStart[block]; } succ(block: i32, k: i32): i32 { return this.succList[this.succStart[block] + k]; } domChildCount(block: i32): i32 { return this.domChildStart[block + 1] - this.domChildStart[block]; } domChild(block: i32, k: i32): i32 { return this.domChildList[this.domChildStart[block] + k]; } /** * With a pool, the tables and the temporaries come from the caller's * current scope, and the CFG must not outlive it: a pass builds its * CFG inside its own scope. Without one, the lists are fresh. */ new(this.body, scratch: IrScratch | null = null) : predStart = listFrom(scratch), predList = listFrom(scratch), succStart = listFrom(scratch), succList = listFrom(scratch), rpo = listFrom(scratch), rpoIndex = listFrom(scratch), idom = listFrom(scratch), domChildStart = listFrom(scratch), domChildList = listFrom(scratch), #scratch = scratch { this.#computePreds(); this.#computeRpo(); this.#computeDominators(); this.#computeDomChildren(); } isReachable(block: i32): boolean { return this.rpoIndex[block] >= 0; } /** True if `block` has a predecessor that appears later in RPO. */ isLoopHeader(block: i32): boolean { for (var pK = 0; pK < this.predCount(block); pK += 1) { let p = this.pred(block, pK); if (this.rpoIndex[p] >= this.rpoIndex[block]) { return true; } } return false; } /** True if `block` has two or more forward-edge predecessors. */ isMergeNode(block: i32): boolean { var forward = 0; for (var pK = 0; pK < this.predCount(block); pK += 1) { let p = this.pred(block, pK); if (this.rpoIndex[p] < this.rpoIndex[block]) { forward += 1; } } return forward >= 2; } dominates(a: i32, b: i32): boolean { var blockId = b; while (true) { if (blockId == a) { return true; } if (blockId == 0) { return false; } blockId = this.idom[blockId]; if (blockId < 0) { return false; } } } #computePreds(): void { let {body} = this; let nb = body.blocks.length; // Count each block's edges in and out, prefix-sum into the start // tables, then place. for (var b = 0; b <= nb; b += 1) { this.predStart.push(0); this.succStart.push(0); } var total = 0; for (var b = 0; b < nb; b += 1) { let insts = body.blocks[b].insts; if (insts.length == 0) { continue; } let term = insts[insts.length - 1]; let n = body.successorCount(term); for (var k = 0; k < n; k += 1) { let target = body.extra[body.successorRecord(term, k)]; if (target >= 0 && target < nb) { this.predStart[target + 1] = this.predStart[target + 1] + 1; this.succStart[b + 1] = this.succStart[b + 1] + 1; total += 1; } } } for (var b = 0; b < nb; b += 1) { this.predStart[b + 1] = this.predStart[b + 1] + this.predStart[b]; this.succStart[b + 1] = this.succStart[b + 1] + this.succStart[b]; } let predNext = listFrom(this.#scratch); let succNext = listFrom(this.#scratch); for (var b = 0; b < nb; b += 1) { predNext.push(this.predStart[b]); succNext.push(this.succStart[b]); } for (var i = 0; i < total; i += 1) { this.predList.push(0); this.succList.push(0); } for (var b = 0; b < nb; b += 1) { let insts = body.blocks[b].insts; if (insts.length == 0) { continue; } let term = insts[insts.length - 1]; let n = body.successorCount(term); for (var k = 0; k < n; k += 1) { let target = body.extra[body.successorRecord(term, k)]; if (target >= 0 && target < nb) { this.predList[predNext[target]] = b; predNext[target] = predNext[target] + 1; this.succList[succNext[b]] = target; succNext[b] = succNext[b] + 1; } } } } #computeRpo(): void { let {body} = this; var i = 0; while (i < body.blocks.length) { this.rpoIndex.push(-1); i += 1; } if (body.blocks.length == 0) { return; } // Iterative DFS postorder from the entry, then reverse. A node must // finish only after all its (non-cyclic) successors have finished, so // each stack entry keeps a cursor into its successor list — the // simpler push-all-successors form finishes nodes too early and // produces orderings where a forward edge looks like a back edge. let postorder = listFrom(this.#scratch); let stack = listFrom(this.#scratch); let cursor = listFrom(this.#scratch); let visited = boolsFrom(this.#scratch); i = 0; while (i < body.blocks.length) { visited.push(false); i += 1; } stack.push(0); cursor.push(0); visited[0] = true; while (stack.length > 0) { let blockId = stack[stack.length - 1]; let next = cursor[cursor.length - 1]; if (next < this.succCount(blockId)) { cursor[cursor.length - 1] = next + 1; let target = this.succ(blockId, next); if (!visited[target]) { visited[target] = true; stack.push(target); cursor.push(0); } continue; } stack.pop(); cursor.pop(); postorder.push(blockId); } i = postorder.length - 1; while (i >= 0) { this.rpoIndex[postorder[i]] = this.rpo.length; this.rpo.push(postorder[i]); i -= 1; } } /** Cooper–Harvey–Kennedy iterative dominator computation over RPO. */ #computeDominators(): void { var i = 0; while (i < this.body.blocks.length) { this.idom.push(-1); i += 1; } if (this.body.blocks.length == 0) { return; } this.idom[0] = 0; var changed = true; while (changed) { changed = false; var r = 1; while (r < this.rpo.length) { let blockId = this.rpo[r]; var newIdom = -1; for (var predK = 0; predK < this.predCount(blockId); predK += 1) { let pred = this.pred(blockId, predK); if (this.rpoIndex[pred] < 0 || this.idom[pred] < 0) { continue; // unreachable or not yet processed } if (newIdom < 0) { newIdom = pred; } else { newIdom = this.#intersect(pred, newIdom); } } if (newIdom >= 0 && this.idom[blockId] != newIdom) { this.idom[blockId] = newIdom; changed = true; } r += 1; } } } #intersect(x: i32, y: i32): i32 { var a = x; var b = y; while (a != b) { while (this.rpoIndex[a] > this.rpoIndex[b]) { a = this.idom[a]; } while (this.rpoIndex[b] > this.rpoIndex[a]) { b = this.idom[b]; } } return a; } #computeDomChildren(): void { let nb = this.body.blocks.length; for (var b = 0; b <= nb; b += 1) { this.domChildStart.push(0); } var r = 1; while (r < this.rpo.length) { let blockId = this.rpo[r]; let parent = this.idom[blockId]; if (parent >= 0 && parent != blockId) { this.domChildStart[parent + 1] = this.domChildStart[parent + 1] + 1; } r += 1; } for (var b = 0; b < nb; b += 1) { this.domChildStart[b + 1] = this.domChildStart[b + 1] + this.domChildStart[b]; } let next = listFrom(this.#scratch); for (var b = 0; b < nb; b += 1) { next.push(this.domChildStart[b]); } let total = this.domChildStart[nb]; for (var i = 0; i < total; i += 1) { this.domChildList.push(0); } // Walk in RPO so children lists come out in ascending RPO order. r = 1; while (r < this.rpo.length) { let blockId = this.rpo[r]; let parent = this.idom[blockId]; if (parent >= 0 && parent != blockId) { this.domChildList[next[parent]] = blockId; next[parent] = next[parent] + 1; } r += 1; } } } function listFrom(scratch: IrScratch | null): GrowableArray { return if (scratch != null) scratch.i32() else new Array(); } function boolsFrom(scratch: IrScratch | null): GrowableArray { return if (scratch != null) scratch.bool() else new Array(); }