dymokomi/luce-base
Source of release 0.46.0
0.46.0 / src / back / ir / cfg.lucb
#==============================================================================================
#
# cfg - The control flow graph of a function: blocks, dominators, frontiers, loops
#
# DESCRIPTION:
# The IR is a flat list of instructions with labels; the optimiser's passes want it
# as a graph. A block runs from a label (or the function's start) to the instruction
# that leaves it, a jump, a branch, a jump table, a return, or a trap, or to the next label, which
# the block then falls into. The graph numbers the reachable blocks in reverse
# post-order, finds each block's immediate dominator ("A Simple, Fast Dominance
# Algorithm", Cooper, Harvey, and Kennedy), its dominance frontier, its depth in the
# dominator tree, and its loop weight (1, times 10 per enclosing loop), as QBE's
# cfg.c does. The instructions stay where they are: a block names its range, and a
# pass that rewrites the list builds the graph again.
#
#==============================================================================================
import support.list
import back.ir.ir
## No block.
pub let none_block: u32 = 0xFFFFFFFF
# mark: Basic blocks and the graph ============================================================
## One basic block: its instructions, its edges, and its place in the dominator tree.
pub struct Block:
## The label at the block's head; 0 for the entry, which has none.
pub var label: u32
## The instructions of the block: `start` is the first after the label, `end` one past
## the last, the terminator included when there is one.
pub var start: u32
## One past the block's last instruction.
pub var end: u32
## Successors by block index (`none_block` when absent): a jump's target, a branch's
## two, the block fallen into.
pub var succ1: u32
## The second successor, a branch's else; `none_block` when absent. A `switch` has its
## default in `succ1` and none here: its other targets are only in `succs`.
pub var succ2: u32
## Every successor, each once, `succ1` first: what a pass that walks the edges reads.
pub var succs: list.List[u32]
## Predecessor block indices.
pub var preds: list.List[u32]
## The reverse post-order number, `none_block` when unreachable from the entry.
pub var rpo: u32
## The immediate dominator's block index.
pub var idom: u32
## The dominance frontier: the blocks where this block's dominance ends.
pub var frontier: list.List[u32]
## Children in the dominator tree, and the depth below the entry.
pub var children: list.List[u32]
## The depth below the entry in the dominator tree.
pub var depth: u32
## 1 outside every loop, 10 inside one, 100 inside a nested one, at most a million.
pub var loop_weight: u32
## The control-flow graph of one function.
pub struct Graph:
## The basic blocks, indexed by block number.
pub var blocks: list.List[Block]
## Block indices in reverse post-order; `order.count` reachable blocks.
pub var order: list.List[u32]
## The block a label heads, by label number.
var by_label: u32[]
## The graph of `f` as its instructions stand.
pub static func over(f: ir.Function*) -> Graph!:
var g = try Graph.blocks_of(f)
try g.dominators()
try g.frontiers()
g.depths()
try g.loops()
return g
## The blocks, their edges, and the reverse post-order alone: what liveness needs, at
## a fraction of the cost of the dominators, frontiers, and loops `over` adds.
pub static func blocks_of(f: ir.Function*) -> Graph!:
var g = Graph(blocks = try list.List[Block].create(32), order = try list.List[u32].create(32), by_label = try new u32[(usize)f.labels + 1] ---)
var k: usize = 0
while k < g.by_label.length:
g.by_label[k] = none_block
k += 1
try g.split(f)
# the entry has no label; label 0 names it
g.by_label[0] = 0
try g.link(f)
try g.number()
return g
## Release the graph's storage.
pub func release():
var i: usize = 0
while i < self.blocks.count:
var b = self.blocks.get(i)
b.preds.destroy()
b.succs.destroy()
b.frontier.destroy()
b.children.destroy()
i += 1
self.blocks.destroy()
self.order.destroy()
free(self.by_label)
## The block that label `label` heads.
pub func block_of(label: u32) -> u32:
return self.by_label[(usize)label]
## How many blocks the graph has.
pub func count() -> usize:
return self.blocks.count
## Whether `a` dominates `b`.
pub func dominates(a: u32, b: u32) -> bool:
var x = b
while x != none_block:
if x == a:
return true
if x == 0:
return false
x = self.blocks.items[(usize)x].idom
return false
## Whether `a` strictly dominates `b`.
pub func strictly_dominates(a: u32, b: u32) -> bool:
return a != b and self.dominates(a, b)
# -- construction ---------------------------------------------------------------------
## Cut the instruction list into blocks.
func split(f: ir.Function*) -> !:
var start: u32 = 0
var label: u32 = 0
var open = true
var i: u32 = 0
while (usize)i < f.instrs.count:
let n = f.instrs.get((usize)i)
if n.op == ir.Op.label:
if open:
try self.add(label, start, i)
label = n.extra
start = i + 1
open = true
elif ir.is_terminator(n.op):
try self.add(label, start, i + 1)
open = false
label = 0
start = i + 1
i += 1
if open:
try self.add(label, start, i)
func add(label: u32, start: u32, end: u32) -> !:
let index = u32(self.blocks.count)
try self.blocks.push(Block(label = label, start = start, end = end, succ1 = none_block, succ2 = none_block, succs = try list.List[u32].create(2), preds = try list.List[u32].create(2),
rpo = none_block, idom = none_block, frontier = try list.List[u32].create(2), children = try list.List[u32].create(2),
depth = 0, loop_weight = 1))
if label != 0:
self.by_label[(usize)label] = index
## Successors from each block's last instruction, or the block after it.
func link(f: ir.Function*) -> !:
var i: usize = 0
while i < self.blocks.count:
var b = self.blocks.get(i)
let last = f.instrs.get((usize)b.end - 1) if b.end > b.start else ir.Instr(op = ir.Op.label, cls = ir.Class.l, dst = 0, a = ir.none_ref(), b = ir.none_ref(), extra = 0, extra2 = 0, line = 0, file = 0, scope = 0, site = 0)
if b.end > b.start and last.op == ir.Op.jmp:
b.succ1 = self.by_label[(usize)last.extra]
elif b.end > b.start and last.op == ir.Op.jnz:
b.succ1 = self.by_label[(usize)last.extra]
b.succ2 = self.by_label[(usize)last.extra2]
elif b.end > b.start and last.op == ir.Op.switch_:
b.succ1 = self.by_label[(usize)last.extra]
elif b.end > b.start and (last.op == ir.Op.ret or last.op == ir.Op.trap_):
_ = 0
elif i + 1 < self.blocks.count:
b.succ1 = u32(i + 1)
try add_successor(&b.succs, b.succ1)
try add_successor(&b.succs, b.succ2)
if b.end > b.start and last.op == ir.Op.switch_:
for label in f.table_targets(last.extra2):
try add_successor(&b.succs, self.by_label[(usize)label])
self.blocks.set(i, b)
i += 1
## Reverse post-order from the entry; predecessors of the reachable blocks.
func number() -> !:
let n = self.blocks.count
var state = try new u8[n + 1] ---
defer free(state)
var stack = try new u32[n + 1] ---
defer free(stack)
var next = try new u32[n + 1] ---
defer free(next)
var post = try new u32[n + 1] ---
defer free(post)
var k: usize = 0
while k <= n:
state[k] = 0
k += 1
var count: usize = 0
var depth: usize = 1
stack[0] = 0
next[0] = 0
state[0] = 1
while depth > 0:
let b = stack[depth - 1]
let block = self.blocks.get((usize)b)
var pushed = false
while (usize)next[depth - 1] < block.succs.count:
let s = block.succs.get((usize)next[depth - 1])
next[depth - 1] += 1
if state[(usize)s] == 0:
state[(usize)s] = 1
stack[depth] = s
next[depth] = 0
depth += 1
pushed = true
break
if not pushed:
post[count] = b
count += 1
depth -= 1
# reverse post-order: the last finished first
self.order.count = 0
var r: usize = count
while r > 0:
r -= 1
let b = post[r]
var block = self.blocks.get((usize)b)
block.rpo = u32(count - 1 - r)
self.blocks.set((usize)b, block)
try self.order.push(b)
var i: usize = 0
while i < self.order.count:
let b = self.order.get(i)
let block = self.blocks.get((usize)b)
for s in block.succs.span():
try self.add_pred(s, b)
i += 1
func add_pred(to: u32, source: u32) -> !:
var block = self.blocks.get((usize)to)
try block.preds.push(source)
self.blocks.set((usize)to, block)
## Immediate dominators over the reverse post-order.
func dominators() -> !:
var changed = true
while changed:
changed = false
var i: usize = 1
while i < self.order.count:
let b = self.order.get(i)
var block = self.blocks.get((usize)b)
var d = none_block
var p: usize = 0
while p < block.preds.count:
let pred = block.preds.get(p)
if pred == 0 or self.blocks.items[(usize)pred].idom != none_block:
d = self.intersect(d, pred)
p += 1
if d != block.idom:
block.idom = d
self.blocks.set((usize)b, block)
changed = true
i += 1
var i: usize = 1
while i < self.order.count:
let b = self.order.get(i)
let d = self.blocks.items[(usize)b].idom
if d != none_block:
var parent = self.blocks.get((usize)d)
try parent.children.push(b)
self.blocks.set((usize)d, parent)
i += 1
func intersect(a: u32, b: u32) -> u32:
if a == none_block:
return b
var x = a
var y = b
while x != y:
while self.blocks.items[(usize)x].rpo > self.blocks.items[(usize)y].rpo:
x = self.blocks.items[(usize)x].idom
while self.blocks.items[(usize)y].rpo > self.blocks.items[(usize)x].rpo:
y = self.blocks.items[(usize)y].idom
return x
## Dominance frontiers: a successor a block does not strictly dominate is in the
## frontier of the block and of its dominators up to the successor's.
func frontiers() -> !:
var i: usize = 0
while i < self.order.count:
let b = self.order.get(i)
let block = self.blocks.get((usize)b)
for s in block.succs.span():
try self.frontier_edge(b, s)
i += 1
func frontier_edge(head: u32, to: u32) -> !:
if to == none_block:
return
var a = head
while not self.strictly_dominates(a, to):
var block = self.blocks.get((usize)a)
var present = false
var k: usize = 0
while k < block.frontier.count:
if block.frontier.get(k) == to:
present = true
k += 1
if not present:
try block.frontier.push(to)
self.blocks.set((usize)a, block)
a = block.idom
if a == none_block:
return
## Depth in the dominator tree, in reverse post-order (a dominator comes first).
func depths():
var i: usize = 0
while i < self.order.count:
let b = self.order.get(i)
var block = self.blocks.get((usize)b)
block.depth = 0 if block.idom == none_block else self.blocks.items[(usize)block.idom].depth + 1
self.blocks.set((usize)b, block)
i += 1
## Loop weights: a back-edge into a header marks every block that reaches the header
## inside the loop (QBE's `loopiter`).
pub func loops() -> !:
let n = self.blocks.count
var visit = try new u32[n + 1] ---
defer free(visit)
var k: usize = 0
while k <= n:
visit[k] = none_block
k += 1
var stack = try new u32[n + 1] ---
defer free(stack)
var i: usize = 0
while i < self.order.count:
let head = self.order.get(i)
let block = self.blocks.get((usize)head)
var p: usize = 0
while p < block.preds.count:
let pred = block.preds.get(p)
if self.blocks.items[(usize)pred].rpo >= block.rpo:
# a back-edge: walk the predecessors back to the header
var depth: usize = 1
stack[0] = pred
while depth > 0:
depth -= 1
let b = stack[depth]
let inner = self.blocks.get((usize)b)
if inner.rpo == none_block or inner.rpo < block.rpo or visit[(usize)b] == head:
continue
visit[(usize)b] = head
var marked = self.blocks.get((usize)b)
# ten per loop, up to a million: six deep weighs as much as deeper
marked.loop_weight = marked.loop_weight * 10 if marked.loop_weight < 1000000 else marked.loop_weight
self.blocks.set((usize)b, marked)
var q: usize = 0
while q < inner.preds.count:
stack[depth] = inner.preds.get(q)
depth += 1
q += 1
p += 1
i += 1
## Add block `s` to `succs` unless it is none or already there.
func add_successor(succs: list.List[u32]*, s: u32) -> !:
if s == none_block:
return
for have in succs.span():
if have == s:
return
try succs.push(s)