dymokomi/luce-base
Source of release 0.44.0
0.44.0 / src / back / native / flags.lucb
#==============================================================================================
#
# flags - Conditions kept in the flags from their comparisons to the select that reads them
#
# DESCRIPTION:
# `ifconvert` turns `if a == 10 or a == 13: n += 1` into comparisons joined by `or`
# and one `select`. Each comparison would set a register (`cset`) for the `or`s, and
# the select test the joined word against 0 again. A generator with conditional
# comparisons (arm64's `ccmp`) instead keeps the chain in its flags: the first
# comparison sets them, each later one compares only while the chain so far leaves
# the answer open and otherwise sets flags that settle it, and the select reads the
# last condition. Its `add x, 1` arm, when the other arm is `x`, is the select's own
# increment (`cinc`).
#
# `plan` gives each instruction its role, from what the generators share: a chain
# is comparisons of integers or of `f32`s and `f64`s (`fccmp`), every one used once,
# joined by one kind of `or` or `and`, all in the select's block before it, with only
# instructions between them that no generator lowers with the flags (arithmetic,
# loads, stores, extensions).
#
#==============================================================================================
import back.ir.ir
# mark: Roles ==================================================================================
## Selected as ever.
pub let plain: u8 = 0
## The chain's first comparison: it sets the flags.
pub let first: u8 = 1
## A later comparison joined to the chain by `or`: it compares while the chain is false.
pub let either: u8 = 2
## A later comparison joined by `and`: it compares while the chain is true.
pub let both: u8 = 4
## An `or` or `and` of the chain: there is nothing to select.
pub let joined: u8 = 8
## The select that reads the chain's condition from the flags.
pub let reads: u8 = 16
## An `add x, 1` its select computes itself: there is nothing to select.
pub let folded: u8 = 32
## A select whose value when true is its value when false plus 1.
pub let then_increments: u8 = 64
## A select whose value when false is its value when true plus 1.
pub let else_increments: u8 = 128
## The most comparisons and joins in one chain.
let most_nodes: usize = 16
## By instruction, its role: a sum of the values above. `counts` is every temporary's uses
## (`selection.uses`). A build a debugger reads keeps every value where it can see it.
pub func plan(f: ir.Function*, counts: u32[]) -> u8[]!:
var roles = try new u8[f.instrs.count + 1] ---
for k in 0..<roles.length:
roles[k] = plain
if f.debug or f.symbols:
return roles
# 1 + the index of each temporary's one definition; 0 when it has none or several
var defs = try new u32[f.temps.count + 1] ---
defer free(defs)
var several = try new bool[f.temps.count + 1] ---
defer free(several)
for k in 0..<defs.length:
defs[k] = 0
several[k] = false
for k in 0..<f.instrs.count:
let x = f.instrs.get(k)
if x.dst != 0 and (usize)x.dst < defs.length:
if defs[x.dst] != 0:
several[x.dst] = true
defs[x.dst] = (u32)k + 1
for k in 0..<defs.length:
if several[k]:
defs[k] = 0
for k in 0..<f.instrs.count:
let x = f.instrs.get(k)
if x.op != ir.Op.select or x.cls == ir.Class.h or x.cls == ir.Class.v:
continue
fold(f, k, counts, defs, roles)
chain(f, k, counts, defs, roles)
return roles
# mark: Increments =============================================================================
## The instruction defining temporary `r` alone, when it is before `at` in `at`'s block:
## its index, else `at` itself.
func defined_in_block(f: ir.Function*, r: ir.Ref, defs: u32[], at: usize) -> usize:
if r.kind != ir.RefKind.temp or defs[r.index] == 0:
return at
let d = (usize)defs[r.index] - 1
if d >= at:
return at
for j in (d + 1)..<at:
if ends_block(f.instrs.get(j).op):
return at
return d
func ends_block(op: ir.Op) -> bool:
return op == ir.Op.label or op == ir.Op.jmp or op == ir.Op.jnz or op == ir.Op.switch_ or op == ir.Op.ret or op == ir.Op.trap_
## The select at `at` choosing between `x` and `x + 1` becomes an increment of `x` by its
## condition, and the `add` is not selected: when that is the sum's only use, the sum is
## in the select's block, and `x` is not assigned between the two.
func fold(f: ir.Function*, at: usize, counts: u32[], defs: u32[], roles: u8[]):
let x = f.instrs.get(at)
if x.cls != ir.Class.w and x.cls != ir.Class.l:
return
let other = f.args.get((usize)x.extra2).value
if let d = increment(f, x.b, other, at, counts, defs):
roles[d] = folded
roles[at] |= then_increments
elif let d = increment(f, other, x.b, at, counts, defs):
roles[d] = folded
roles[at] |= else_increments
## Where `sum` is `base + 1`, used once, in the block before `at`, with `base` unchanged
## until `at`: the index of the `add`.
func increment(f: ir.Function*, sum: ir.Ref, base: ir.Ref, at: usize, counts: u32[], defs: u32[]) -> usize?:
if sum.kind != ir.RefKind.temp or counts[sum.index] != 1:
return none
let d = defined_in_block(f, sum, defs, at)
if d == at:
return none
let add = f.instrs.get(d)
if add.op != ir.Op.add or add.cls != f.instrs.get(at).cls:
return none
let one_after = (same(add.a, base) and add.b.kind == ir.RefKind.constant and add.b.value == 1) or (same(add.b, base) and add.a.kind == ir.RefKind.constant and add.a.value == 1)
if not one_after:
return none
if base.kind == ir.RefKind.temp:
# `base` read at the add must be the one the select reads
for j in (d + 1)..<at:
if f.instrs.get(j).dst == base.index:
return none
elif base.kind != ir.RefKind.constant:
return none
return d
func same(a: ir.Ref, b: ir.Ref) -> bool:
if a.kind != b.kind:
return false
if a.kind == ir.RefKind.constant:
return a.value == b.value
return a.kind == ir.RefKind.temp and a.index == b.index
# mark: Chains =================================================================================
## The select at `at` reads its condition from the flags when the condition is a chain:
## integer comparisons joined by one kind of `or` or `and`, each used once, in the select's
## block, with only instructions between the first and the select that leave the flags be.
func chain(f: ir.Function*, at: usize, counts: u32[], defs: u32[], roles: u8[]):
let x = f.instrs.get(at)
if x.extra != 0 or x.a.kind != ir.RefKind.temp:
return
var nodes: usize[16] = ---
var pending: u32[16] = ---
var count: usize = 0
var waiting: usize = 1
pending[0] = x.a.index
var join = ir.Op.copy
while waiting > 0:
waiting -= 1
let r = ir.temp_ref(pending[waiting])
if counts[r.index] != 1 or count == most_nodes:
return
let d = defined_in_block(f, r, defs, at)
if d == at or roles[d] != plain:
return
let n = f.instrs.get(d)
if ir.is_comparison(n.op) and (n.cls == ir.Class.w or n.cls == ir.Class.l or n.cls == ir.Class.s or n.cls == ir.Class.d):
nodes[count] = d
count += 1
continue
if (n.op != ir.Op.or_ and n.op != ir.Op.and_) or n.cls != ir.Class.w or n.a.kind != ir.RefKind.temp or n.b.kind != ir.RefKind.temp:
return
if join != ir.Op.copy and join != n.op:
return
join = n.op
if waiting + 2 > most_nodes:
return
nodes[count] = d
count += 1
pending[waiting] = n.a.index
pending[waiting + 1] = n.b.index
waiting += 2
var low = at
for k in 0..<count:
if nodes[k] < low:
low = nodes[k]
# between the first and the select: the chain, and what leaves the flags be
for j in low..<at:
if member(nodes[0..<count], j):
continue
if roles[j] != plain and roles[j] != folded:
return
if not leaves_flags(f.instrs.get(j).op):
return
var seen_first = false
for j in low..<at:
if not member(nodes[0..<count], j):
continue
if not ir.is_comparison(f.instrs.get(j).op):
roles[j] = joined
elif not seen_first:
roles[j] = first
seen_first = true
else:
roles[j] = either if join == ir.Op.or_ else both
roles[at] |= reads
func member(nodes: usize[], j: usize) -> bool:
for n in nodes:
if n == j:
return true
return false
## Whether every generator lowers `op` without the flags: plain arithmetic, loads, stores
## and extensions (division, checked arithmetic, bounds, calls and branches may use them).
func leaves_flags(op: ir.Op) -> bool:
match op:
.copy, .add, .sub, .mul, .and_, .or_, .xor, .shl, .lshr, .ashr, .neg, .addr, .dbg:
return true
.loadsb, .loadub, .loadsh, .loaduh, .loadsw, .loaduw, .loadl, .loads, .loadd:
return true
.storeb, .storeh, .storew, .storel, .stores, .stored:
return true
.extsb, .extub, .extsh, .extuh, .extsw, .extuw:
return true
_:
return false