dymokomi/luce-base
Source of release 0.46.0
0.46.0 / src / back / native / layout.lucb
#==============================================================================================
#
# layout - Where a loop's blocks go: the round's last blocks above its body
#
# DESCRIPTION:
# A rotated loop (`selection.rotations`) tests whether to go round where its latch
# jumps back to its head. When its body ends in an `if`, the arm laid out last falls
# into the latch and every other arm jumps to it, so each round takes two branches:
# into its arm or to the latch, and back to the body's top. Laid out the way C
# compilers place a loop's blocks, the chain of blocks that falls into the latch
# moves above the body: the latch's test then falls into the body and leaves only
# when the loop ends, the body's branch into that arm goes back up to it, and each
# round takes one branch. The head is entered once, by a branch to the body that
# jumps over the chain. The chain moves whole: only blocks nothing else falls into
# begin it, it holds no loop of its own, and a loop whose body falls into its latch
# by itself keeps its order. The chain's first block is the loop's top, which the
# generators align in place of the body (`selection.rotate_heads`).
#
#==============================================================================================
import back.ir.ir
import back.native.frame
import back.native.selection
import support.list
# mark: Arranging =============================================================================
## Put `f`'s blocks in the order its generator selects them in: each jump sent to the first
## of its label's run and on through blocks that only jump (`selection.canonical_labels`),
## the blocks that only trap last (`selection.traps_last`), and each rotated loop's latch
## chain above its body (`latches_first`).
pub func arrange(f: ir.Function*, floats: bool) -> !:
try selection.canonical_labels(f)
if not f.debug:
try selection.traps_last(f)
try latches_first(f, floats)
## Move each rotated loop's latch chain above its body, in `f` as the generators are about
## to select it; `floats` is whether a float comparison fuses with its branch, as
## `selection.rotations` asks.
pub func latches_first(f: ir.Function*, floats: bool) -> !:
if f.debug or f.symbols or f.naked or f.dynamic_levels != 0 or f.labels == 0:
return
var heads = try selection.loop_heads(f)
defer free(heads)
var counts = try selection.uses(f)
defer free(counts)
var tests = try selection.rotations(f, heads, counts, floats)
defer free(tests)
# where each label is, and the last jump back to each head
var at = try new u32[heads.length] ---
defer free(at)
var last_jump = try new u32[heads.length] ---
defer free(last_jump)
for k in 0..<at.length:
at[k] = 0
last_jump[k] = 0
for i in 0..<f.instrs.count:
let x = f.instrs.get(i)
if x.op == ir.Op.label and (usize)x.extra < at.length:
at[(usize)x.extra] = u32(i) + 1
elif x.op == ir.Op.jmp and (usize)x.extra < last_jump.length:
last_jump[(usize)x.extra] = u32(i) + 1
# by instruction: 1 + the chain moved in front of it, and whether it moves
var chain_before = try new u32[f.instrs.count + 1] ---
defer free(chain_before)
var moved = try new bool[f.instrs.count + 1] ---
defer free(moved)
for i in 0..<moved.length:
chain_before[i] = 0
moved[i] = false
var starts = try list.List[u32].create(4)
defer starts.destroy()
var ends = try list.List[u32].create(4)
defer ends.destroy()
for head in 0..<tests.length:
if tests[head] == 0 or last_jump[head] == 0:
continue
let branch_at = (usize)tests[head]
let branch = f.instrs.get(branch_at)
# the body directly after the head's test, which it enters when the loop goes on
if branch.extra == branch.extra2 or selection.label_at(f, branch_at + 1) != branch.extra:
continue
let jump_at = (usize)last_jump[head] - 1
if jump_at <= branch_at:
continue
if let start = chain_start(f, heads, branch_at + 1, jump_at):
chain_before[branch_at + 1] = u32(starts.count) + 1
try starts.push(u32(start))
try ends.push(u32(jump_at) + 1)
for i in start..<jump_at + 1:
moved[i] = true
if starts.count == 0:
return
var out = try list.List[ir.Instr].create(f.instrs.count)
for i in 0..<f.instrs.count:
if chain_before[i] != 0:
let k = (usize)chain_before[i] - 1
for c in (usize)starts.get(k)..<(usize)ends.get(k):
try out.push(f.instrs.get(c))
if not moved[i]:
try out.push(f.instrs.get(i))
f.instrs.destroy()
f.instrs = out
## Where the chain of blocks ending in the jump back at `jump_at` begins: the first label
## of the block that the blocks after it fall into one by one and that nothing falls into
## itself (it follows a jump, a return or a trap, not a branch, whose other way it is). None when the chain reaches the body at `body_at` (the body falls into its latch
## by itself), holds a loop's head, or begins without a label.
func chain_start(f: ir.Function*, heads: bool[], body_at: usize, jump_at: usize) -> usize?:
var i = jump_at
while i > body_at:
i -= 1
let x = f.instrs.get(i)
if x.op == ir.Op.label:
if (usize)x.extra < heads.length and heads[(usize)x.extra]:
return none
# the run's first label: what comes before it falls in, or does not
var first = i
while first > body_at and f.instrs.get(first - 1).op == ir.Op.label:
first -= 1
let y = f.instrs.get(first)
if (usize)y.extra < heads.length and heads[(usize)y.extra]:
return none
if first <= body_at:
return none
var before = first - 1
while before > body_at and f.instrs.get(before).op == ir.Op.dbg:
before -= 1
# a branch falls into the block after it when that is one of its targets
let last = f.instrs.get(before).op
if ir.is_terminator(last) and last != ir.Op.jnz:
return first
i = first
elif ir.is_terminator(x.op):
return none
return none
# mark: Threading after allocation ============================================================
## Where `thread_after_allocation` found each branch's targets, to put back once the
## function's text is written: x86-64 lays a Windows function out again, and its allocation
## must see the branches as the first one did.
pub struct Threaded:
var targets: list.List[u32]
var tables: list.List[u32]
## Put every branch's targets back, and give back the storage.
pub func restore(f: ir.Function*):
var k: usize = 0
for i in 0..<f.instrs.count:
var x = f.instrs.get(i)
if x.op == ir.Op.jmp or x.op == ir.Op.jnz or x.op == ir.Op.switch_:
x.extra = self.targets.get(k)
x.extra2 = self.targets.get(k + 1)
f.instrs.set(i, x)
k += 2
for i in 0..<self.tables.count:
f.jump_labels.set(i, self.tables.get(i))
self.targets.destroy()
self.tables.destroy()
## Once `f`'s registers are allocated: each jump or branch to a block of copies that emit
## nothing goes where that block goes (`selection.thread_quiet`). The targets before, to
## restore after the text (`Threaded.restore`).
pub func thread_after_allocation(f: ir.Function*, fr: frame.Frame*) -> Threaded!:
var threaded = Threaded(targets = try list.List[u32].create(64), tables = try list.List[u32].create(f.jump_labels.count + 1))
for x in f.instrs.span():
if x.op == ir.Op.jmp or x.op == ir.Op.jnz or x.op == ir.Op.switch_:
try threaded.targets.push(x.extra)
try threaded.targets.push(x.extra2)
for label in f.jump_labels.span():
try threaded.tables.push(label)
let quiet = try fr.quiet(f)
defer free(quiet)
try selection.thread_quiet(f, quiet)
return threaded