dymokomi/luce-base
Source of release 0.46.0
0.46.0 / src / back / opt / ranges.lucb
#==============================================================================================
#
# ranges - Range facts about SSA values
#
# DESCRIPTION:
# Facts about immutable SSA values, scoped by dominance. A successful bounds check
# supplies a fact just like a branch does. Unknown ranges retain checks; this pass
# never derives a fact about a memory location from an earlier load. Facts are
# chained by their left and by their right operand, so a query reads the facts about
# its operands rather than every fact in scope: a function with thousands of checks
# builds in time near linear in them.
#
#==============================================================================================
import back.ir.cfg
import back.ir.ir
import support.list
# mark: Facts and the search ==================================================================
enum Relation as u8:
less = 1
at_most = 2
equal = 3
struct Fact:
var relation: Relation
var cls: ir.Class
var left: ir.Ref
var right: ir.Ref
## The fact before this one with the same left, and with the same right, operand
## bucket; 1-based, 0 ends the chain.
var next_left: u32
var next_right: u32
## Operands other than temporaries share this many buckets, by kind and value.
let shared_buckets: usize = 256
## A multiplication that has already completed without overflow. Its factors
## bound smaller products and row-major indexes without requiring a constant
## dimension. The result remains an immutable SSA value.
struct Product:
var cls: ir.Class
var left: ir.Ref
var right: ir.Ref
var value: ir.Ref
## One block of the dominator-tree walk: the block, how many of its children were
## visited, and the facts' and products' counts before the block added its own.
struct RangeVisit:
var block: u32
var child: usize
var mark: usize
var product_mark: usize
var decision_mark: usize
## What an edge decided about the condition its branch tested (`Search.outcomes`).
let undecided: u8 = 0
let failed: u8 = 1
let held: u8 = 2
struct Search:
var f: ir.Function*
var g: cfg.Graph*
var definitions: u32[]
var facts: list.List[Fact]
## The newest fact whose left, and whose right, operand falls in each bucket: one per
## temporary, then `shared_buckets` for the rest; 1-based, 0 when there is none.
var left_heads: u32[]
var right_heads: u32[]
var products: list.List[Product]
## Per temporary a phi defines: 1 + the index of the phi's block; 0 for the others.
var join_of: u32[]
## Per temporary, what a branch on it above decided: `held` or `failed` on the edge
## taken, `undecided` elsewhere; `decisions` lists the temporaries set, newest last,
## to forget them as the walk leaves the blocks the edge dominates.
var outcomes: u8[]
var decisions: list.List[u32]
var changed: bool = false
## The chain bucket of operand `r`: its own for a temporary, a shared one otherwise.
func bucket(r: ir.Ref) -> usize:
let temps = self.left_heads.length - shared_buckets
if r.kind == ir.RefKind.temp and (usize)r.index < temps:
return (usize)r.index
let mixed = ((u64)r.value +% (u64)(u8)r.kind) *% 11400714819323198485
return temps + (usize)(mixed >> 56)
## Drop the facts after the first `mark`, newest first, restoring the chains.
func truncate(mark: usize):
while self.facts.count > mark:
let fact = self.facts.get(self.facts.count - 1)
self.left_heads[self.bucket(fact.left)] = fact.next_left
self.right_heads[self.bucket(fact.right)] = fact.next_right
self.facts.count -= 1
## Equalities are followed only to a bounded depth. Exhausting the search
## loses an optimization, never a check that would have been necessary.
func equal(a: ir.Ref, b: ir.Ref, cls: ir.Class, depth: u32 = 0) -> bool:
if same(a, b):
return true
if depth >= 3:
return false
var at = self.left_heads[self.bucket(a)]
while at != 0:
let fact = self.facts.get((usize)at - 1)
at = fact.next_left
if fact.relation == Relation.equal and fact.cls == cls and same(a, fact.left) and self.equal(fact.right, b, cls, depth + 1):
return true
at = self.right_heads[self.bucket(a)]
while at != 0:
let fact = self.facts.get((usize)at - 1)
at = fact.next_right
if fact.relation == Relation.equal and fact.cls == cls and same(a, fact.right) and self.equal(fact.left, b, cls, depth + 1):
return true
return false
func upper(value: ir.Ref, cls: ir.Class, depth: u32 = 0) -> u64:
let maximum = limit(cls)
if value.kind == ir.RefKind.constant:
return bits(value, cls)
if depth >= 4:
return maximum
var result = maximum
if value.kind == ir.RefKind.temp and self.definitions[value.index] != 0:
let definition = self.f.instrs.get(self.definitions[value.index] - 1)
# an operation computes in its own class; asked in another (the low word of a
# 64-bit shift, as `(u32)(a >> 42)` compares it), its bound holds only when it
# fits that class
let own = definition.cls if definition.cls == ir.Class.w or definition.cls == ir.Class.l else cls
if definition.op == ir.Op.extub:
result = 255
elif definition.op == ir.Op.extuh:
result = 65535
elif definition.op == ir.Op.extuw:
result = self.upper(definition.a, ir.Class.w, depth + 1)
elif definition.op == ir.Op.and_ and definition.b.kind == ir.RefKind.constant:
result = bits(definition.b, own)
elif definition.op == ir.Op.and_ and definition.a.kind == ir.RefKind.constant:
result = bits(definition.a, own)
elif definition.op == ir.Op.urem and definition.b.kind == ir.RefKind.constant and bits(definition.b, own) > 0:
result = bits(definition.b, own) - 1
elif definition.op == ir.Op.lshr and definition.b.kind == ir.RefKind.constant and bits(definition.b, own) < 64:
result = self.upper(definition.a, own, depth + 1) >> bits(definition.b, own)
elif definition.op == ir.Op.udiv and definition.b.kind == ir.RefKind.constant and bits(definition.b, own) > 0:
result = self.upper(definition.a, own, depth + 1) // bits(definition.b, own)
elif (definition.op == ir.Op.mul or definition.op == ir.Op.shl) and definition.b.kind == ir.RefKind.constant and definition.cls == cls:
# a product that cannot wrap bounds the result; one that might, nothing
let factor = bits(definition.b, cls) if definition.op == ir.Op.mul else ((u64)1 << bits(definition.b, cls) if bits(definition.b, cls) < 64 else 0)
let high = self.upper(definition.a, cls, depth + 1)
if factor > 0 and high <= maximum // factor:
result = high * factor
if result > maximum:
result = maximum
var at = self.left_heads[self.bucket(value)]
while at != 0:
let fact = self.facts.get((usize)at - 1)
at = fact.next_left
if fact.cls == cls and same(value, fact.left):
var bound = self.upper(fact.right, cls, depth + 1)
if fact.relation == Relation.less and bound > 0:
bound -= 1
if bound < result:
result = bound
at = self.right_heads[self.bucket(value)]
while at != 0:
let fact = self.facts.get((usize)at - 1)
at = fact.next_right
if fact.relation == Relation.equal and fact.cls == cls and same(value, fact.right):
let bound = self.upper(fact.left, cls, depth + 1)
if bound < result:
result = bound
return result
## The least `value` can be: a constant, a count that starts somewhere and only goes up
## (a loop's `at` from 2, stepped by a checked `+ 1`), a product or a sum of such, or
## what a fact puts below it.
func lower(value: ir.Ref, cls: ir.Class, depth: u32 = 0) -> u64:
if value.kind == ir.RefKind.constant:
return bits(value, cls)
if value.kind != ir.RefKind.temp or depth >= 4:
return 0
var result: u64 = 0
if self.definitions[value.index] != 0:
let definition = self.f.instrs.get(self.definitions[value.index] - 1)
if definition.op == ir.Op.phi and self.f.temp_class(definition.dst) == cls:
result = self.lower_phi(definition, cls, depth)
elif (definition.op == ir.Op.addo and definition.extra == 0) and definition.cls == cls:
# a checked sum never wraps: it is at least its operands' least
let low_a = self.lower(definition.a, cls, depth + 1)
let low_b = self.lower(definition.b, cls, depth + 1)
result = low_a + low_b if low_a <= limit(cls) - low_b else limit(cls)
elif (definition.op == ir.Op.mul or (definition.op == ir.Op.mulo and definition.extra == 0)) and definition.b.kind == ir.RefKind.constant and definition.cls == cls:
# a product that cannot wrap is at least the least factor times the constant
let factor = bits(definition.b, cls)
let low = self.lower(definition.a, cls, depth + 1)
if factor > 0 and self.upper(definition.a, cls, depth + 1) <= limit(cls) // factor:
result = low * factor
elif definition.op == ir.Op.shl and definition.a.kind == ir.RefKind.constant and definition.cls == cls:
# `1 << s` with `s` below the width: no bit of the constant shifted out, so
# it is at least the constant (`(1 << s) - 1` cannot wrap)
let constant = bits(definition.a, cls)
let room = (u64)(32 if cls == ir.Class.w else 64) - significant(constant)
if constant > 0 and self.upper(definition.b, cls, depth + 1) <= room:
result = constant
var at = self.right_heads[self.bucket(value)]
while at != 0:
let fact = self.facts.get((usize)at - 1)
at = fact.next_right
if fact.cls == cls and same(value, fact.right):
var bound = self.lower(fact.left, cls, depth + 1)
if fact.relation == Relation.less and bound < limit(cls):
bound += 1
if bound > result:
result = bound
return result
## A phi's least: the least of what enters it, where a value that is the phi itself
## plus a checked non-negative step (which traps rather than wraps) counts as no less.
func lower_phi(phi: ir.Instr, cls: ir.Class, depth: u32) -> u64:
var result = limit(cls)
for k in 0..<phi.extra2:
let incoming = self.f.phi_args.get((usize)(phi.extra + k)).value
if self.steps_up(incoming, phi.dst):
continue
let low = self.lower(incoming, cls, depth + 1)
if low < result:
result = low
return result if result != limit(cls) else 0
## Whether `value` is temporary `origin` plus a constant through a checked addition.
func steps_up(value: ir.Ref, origin: u32) -> bool:
if value.kind != ir.RefKind.temp or self.definitions[value.index] == 0:
return false
let definition = self.f.instrs.get(self.definitions[value.index] - 1)
if definition.op != ir.Op.addo or definition.extra != 0:
return false
let through = ir.temp_ref(origin)
return (same(definition.a, through) and definition.b.kind == ir.RefKind.constant) or (same(definition.b, through) and definition.a.kind == ir.RefKind.constant)
## Whether `index`, some `i * c + k`, is below `length` (at most it, when not `strict`)
## because `i` is below `x // c` (`x >> s` when `c` is `2^s`), where `x` is `length` or
## `length - d` that cannot wrap: then `i * c <= x - c`, so `index <= length - d - c + k`
## and, with `k <= c`, nothing on the way wraps. A loop over the points of a flat array
## of coordinates (`values[at * 3 + 2]` while `at < values.length // 3`), and over the
## words of a byte span from its second byte (`&data[at * 4 + 1]` while
## `at < (data.length - 1) >> 2`).
func scaled_below(index: ir.Ref, length: ir.Ref, strict: bool = true) -> bool:
if index.kind != ir.RefKind.temp or self.definitions[index.index] == 0:
return false
var scaled = index
var offset: u64 = 0
let sum = self.f.instrs.get(self.definitions[index.index] - 1)
if (sum.op == ir.Op.add or (sum.op == ir.Op.addo and sum.extra == 0)) and sum.cls == ir.Class.l and sum.b.kind == ir.RefKind.constant:
scaled = sum.a
offset = bits(sum.b, ir.Class.l)
if scaled.kind != ir.RefKind.temp or self.definitions[scaled.index] == 0:
return false
let product = self.f.instrs.get(self.definitions[scaled.index] - 1)
if product.cls != ir.Class.l or product.b.kind != ir.RefKind.constant:
return false
var factor: u64 = 0
if product.op == ir.Op.mul or (product.op == ir.Op.mulo and product.extra == 0):
factor = bits(product.b, ir.Class.l)
elif product.op == ir.Op.shl and bits(product.b, ir.Class.l) < 63:
factor = (u64)1 << bits(product.b, ir.Class.l)
if factor == 0 or factor > 1 << 32 or offset > factor:
return false
var at = self.left_heads[self.bucket(product.a)]
while at != 0:
let fact = self.facts.get((usize)at - 1)
at = fact.next_left
if fact.relation != Relation.less or fact.cls != ir.Class.l or not same(product.a, fact.left) or fact.right.kind != ir.RefKind.temp or self.definitions[fact.right.index] == 0:
continue
let quotient = self.f.instrs.get(self.definitions[fact.right.index] - 1)
if quotient.cls != ir.Class.l or quotient.b.kind != ir.RefKind.constant:
continue
let divides = quotient.op == ir.Op.udiv and bits(quotient.b, ir.Class.l) == factor
let shifts = quotient.op == ir.Op.lshr and bits(quotient.b, ir.Class.l) < 63 and ((u64)1 << bits(quotient.b, ir.Class.l)) == factor
if not divides and not shifts:
continue
let short = self.short_of(quotient.a, length)
if short == limit(ir.Class.l):
continue
# index <= length - short - factor + offset
let below = short + factor
if (strict and below > offset) or (not strict and below >= offset):
return true
return false
## How much `x` is below `length`: 0 when the two are equal, `d` when `x` is
## `length - d` that cannot wrap, and the class's limit when neither is known.
func short_of(x: ir.Ref, length: ir.Ref) -> u64:
if self.equal(x, length, ir.Class.l):
return 0
if x.kind != ir.RefKind.temp or self.definitions[x.index] == 0:
return limit(ir.Class.l)
let difference = self.f.instrs.get(self.definitions[x.index] - 1)
if (difference.op != ir.Op.sub and not (difference.op == ir.Op.subo and difference.extra == 0)) or difference.cls != ir.Class.l or difference.b.kind != ir.RefKind.constant:
return limit(ir.Class.l)
let d = bits(difference.b, ir.Class.l)
if d > 1 << 32 or self.lower(difference.a, ir.Class.l) < d or not self.equal(difference.a, length, ir.Class.l):
return limit(ir.Class.l)
return d
## Whether `index`, some `x - c` that cannot wrap (`x` is at least `c`), is below
## `length` because `x` is, or is below it as a scaled index (`values[at * 3 - 2]`).
func below_through_difference(index: ir.Ref, length: ir.Ref) -> bool:
if index.kind != ir.RefKind.temp or self.definitions[index.index] == 0:
return false
let difference = self.f.instrs.get(self.definitions[index.index] - 1)
if (difference.op != ir.Op.sub and not (difference.op == ir.Op.subo and difference.extra == 0)) or difference.cls != ir.Class.l or difference.b.kind != ir.RefKind.constant:
return false
if self.lower(difference.a, ir.Class.l) < bits(difference.b, ir.Class.l):
return false
return self.at_most(difference.a, length, ir.Class.l, true) or self.scaled_below(difference.a, length)
func at_most(a: ir.Ref, b: ir.Ref, cls: ir.Class, strict: bool, depth: u32 = 0) -> bool:
if a.kind == ir.RefKind.constant and b.kind == ir.RefKind.constant:
return bits(a, cls) < bits(b, cls) if strict else bits(a, cls) <= bits(b, cls)
if not strict and self.equal(a, b, cls):
return true
if depth == 0:
# the most `a` can be against the least `b` can be
let high = self.upper(a, cls)
let low = self.lower(b, cls)
if high < low or (not strict and high == low):
return true
if b.kind == ir.RefKind.constant:
let high = self.upper(a, cls)
if high < bits(b, cls) or (not strict and high == bits(b, cls)):
return true
if depth >= 3:
return false
if self.bounded_through(a, a, b, cls, strict, depth, 0):
return true
var at = self.right_heads[self.bucket(a)]
while at != 0:
let fact = self.facts.get((usize)at - 1)
at = fact.next_right
if fact.relation == Relation.equal and fact.cls == cls and same(a, fact.right):
if self.at_most(fact.left, b, cls, strict, depth + 1):
return true
# what `b` equals bounds `a` as well: `table.length == 4096` once asserted puts
# `acc & 4095` inside the table
at = self.left_heads[self.bucket(b)]
while at != 0:
let fact = self.facts.get((usize)at - 1)
at = fact.next_left
if fact.relation == Relation.equal and fact.cls == cls and same(b, fact.left) and not same(a, fact.right):
if self.at_most(a, fact.right, cls, strict, depth + 1):
return true
at = self.right_heads[self.bucket(b)]
while at != 0:
let fact = self.facts.get((usize)at - 1)
at = fact.next_right
if fact.relation == Relation.equal and fact.cls == cls and same(b, fact.right) and not same(a, fact.left):
if self.at_most(a, fact.left, cls, strict, depth + 1):
return true
return false
## Whether a fact whose left is `x`, a value `equal` to `a` within three equalities
## (`hops` taken so far), bounds `a` by `b`: the facts `at_most` would find by asking
## `equal(a, fact.left)` of every fact, reached through the chains instead.
func bounded_through(x: ir.Ref, a: ir.Ref, b: ir.Ref, cls: ir.Class, strict: bool, depth: u32, hops: u32) -> bool:
var at = self.left_heads[self.bucket(x)]
while at != 0:
let fact = self.facts.get((usize)at - 1)
at = fact.next_left
if fact.cls == cls and same(x, fact.left):
if self.at_most(fact.right, b, cls, strict and fact.relation != Relation.less, depth + 1):
return true
if hops >= 3:
return false
at = self.left_heads[self.bucket(x)]
while at != 0:
let fact = self.facts.get((usize)at - 1)
at = fact.next_left
if fact.relation == Relation.equal and fact.cls == cls and same(x, fact.left) and self.bounded_through(fact.right, a, b, cls, strict, depth, hops + 1):
return true
at = self.right_heads[self.bucket(x)]
while at != 0:
let fact = self.facts.get((usize)at - 1)
at = fact.next_right
if fact.relation == Relation.equal and fact.cls == cls and same(x, fact.right) and self.bounded_through(fact.left, a, b, cls, strict, depth, hops + 1):
return true
return false
## What an unsigned comparison answers when the facts decide it, `none` otherwise.
func decided(op: ir.Op, a: ir.Ref, b: ir.Ref, cls: ir.Class) -> bool?:
# every one as `low < high` or `low <= high`, true, or false when the reverse holds
var low = a
var high = b
var strict = true
match op:
.cult: _ = 0
.cule: strict = false
.cugt:
low = b
high = a
.cuge:
low = b
high = a
strict = false
_: return none
if self.at_most(low, high, cls, strict):
return true
if self.at_most(high, low, cls, not strict):
return false
return none
func add(relation: Relation, cls: ir.Class, left: ir.Ref, right: ir.Ref) -> !:
if same(left, right):
return
let l = self.bucket(left)
let r = self.bucket(right)
try self.facts.push(Fact(relation = relation, cls = cls, left = left, right = right, next_left = self.left_heads[l], next_right = self.right_heads[r]))
self.left_heads[l] = (u32)self.facts.count
self.right_heads[r] = (u32)self.facts.count
func product_fits(a: ir.Ref, b: ir.Ref, cls: ir.Class) -> bool:
for product in self.products.span():
if product.cls != cls:
continue
if (self.at_most(a, product.left, cls, false) and self.at_most(b, product.right, cls, false)) or (self.at_most(a, product.right, cls, false) and self.at_most(b, product.left, cls, false)):
return true
return false
## row * width + column < rows * width when row < rows and
## column < width. The checked product supplies the finite upper bound.
func packed(a: ir.Ref, b: ir.Ref, product: Product) -> bool:
if a.kind != ir.RefKind.temp or self.definitions[a.index] == 0:
return false
let multiply = self.f.instrs.get(self.definitions[a.index] - 1)
if multiply.cls != product.cls or (multiply.op != ir.Op.mul and not (multiply.op == ir.Op.mulo and multiply.extra == 0)):
return false
return self.row(multiply.a, multiply.b, b, product.left, product.right, product.cls) or self.row(multiply.b, multiply.a, b, product.left, product.right, product.cls) or self.row(multiply.a, multiply.b, b, product.right, product.left, product.cls) or self.row(multiply.b, multiply.a, b, product.right, product.left, product.cls)
func row(index: ir.Ref, stride: ir.Ref, column: ir.Ref, rows: ir.Ref, width: ir.Ref, cls: ir.Class) -> bool:
return self.equal(stride, width, cls) and self.at_most(index, rows, cls, true) and self.at_most(column, width, cls, true)
func sum_fits(a: ir.Ref, b: ir.Ref, cls: ir.Class) -> bool:
for product in self.products.span():
if product.cls == cls and (self.packed(a, b, product) or self.packed(b, a, product)):
return true
return false
## Whether `index` is below `length` as a row-major index into a checked product:
## `row * width + column`, or `row * width` alone (its column 0), below `rows * width`.
func packed_bound(index: ir.Ref, length: ir.Ref) -> bool:
if index.kind != ir.RefKind.temp or self.definitions[index.index] == 0:
return false
let sum = self.f.instrs.get(self.definitions[index.index] - 1)
if sum.cls != ir.Class.l:
return false
let summed = sum.op == ir.Op.add or (sum.op == ir.Op.addo and sum.extra == 0)
for product in self.products.span():
if product.cls != ir.Class.l or not self.equal(length, product.value, ir.Class.l):
continue
if summed and (self.packed(sum.a, sum.b, product) or self.packed(sum.b, sum.a, product)):
return true
if not summed and self.packed(index, ir.const_ref(0), product):
return true
return false
## Whether `index`, a phi joining a choice (`x if c else y`, before `ifconvert` makes it
## a `select`), is below `length` (at most it, when not `strict`) whichever way the
## choice went: each argument arrives from the block that branched on `c`, directly or
## through a block of its own, and is bounded by the facts in scope here (which hold
## whichever edge was taken) with the branch's sense on its edge assumed beside them.
## A loop's head is no such join: an edge back into it leaves the choice's values behind.
func chosen_below(index: ir.Ref, length: ir.Ref, strict: bool) -> bool!:
if index.kind != ir.RefKind.temp or self.join_of[index.index] == 0:
return false
let phi = self.f.instrs.get(self.definitions[index.index] - 1)
let join = self.join_of[index.index] - 1
if phi.extra2 == 0 or phi.extra2 > 4:
return false
for k in 0..<phi.extra2:
let argument = self.f.phi_args.get((usize)(phi.extra + k))
let edge = self.g.block_of(argument.pred)
var choice = edge
var through = self.g.blocks.get(join).label
let own = self.g.blocks.get(edge)
let last = self.f.instrs.get(own.end - 1).op if own.end > own.start else ir.Op.jmp
if last == ir.Op.switch_:
return false
if last != ir.Op.jnz:
# a block of its own on the way: the choice was its one predecessor's
if own.preds.count != 1:
return false
choice = own.preds.get(0)
through = own.label
let chooser = self.g.blocks.get(choice)
if chooser.end <= chooser.start or self.g.dominates(join, choice):
return false
let branch = self.f.instrs.get(chooser.end - 1)
if branch.op != ir.Op.jnz or branch.extra == branch.extra2 or (branch.extra != through and branch.extra2 != through):
return false
let mark = self.facts.count
try self.assume(branch.a, branch.extra == through)
let below = self.at_most(argument.value, length, ir.Class.l, strict)
self.truncate(mark)
if not below:
return false
return true
## A single predecessor makes this incoming edge unavoidable. This excludes
## joins and loop headers whose backedges could bypass the tested condition.
func incoming(block: cfg.Block) -> !:
if block.preds.count != 1:
return
let predecessor = self.g.blocks.get(block.preds.get(0))
if predecessor.end <= predecessor.start:
return
let branch = self.f.instrs.get(predecessor.end - 1)
if branch.op != ir.Op.jnz or branch.extra == branch.extra2:
return
let yes = branch.extra == block.label
try self.assume(branch.a, yes)
# the condition itself, for a later branch on it below the edge
if branch.a.kind == ir.RefKind.temp and (usize)branch.a.index < self.outcomes.length and self.outcomes[branch.a.index] == undecided:
self.outcomes[branch.a.index] = held if yes else failed
try self.decisions.push(branch.a.index)
## The facts that `condition` being true (`yes`), or false, establishes.
func assume(condition: ir.Ref, yes_now: bool) -> !:
if condition.kind != ir.RefKind.temp:
return
let index = self.definitions[condition.index]
if index == 0:
return
var comparison = self.f.instrs.get(index - 1)
var yes = yes_now
# `x == 0` or `x != 0` of a comparison `x`, as `if a != b or ...` and `not` lower
# before the negations fold: the edge decides the comparison inside, its sense
# flipped by `== 0`
var hops: u32 = 0
while (comparison.op == ir.Op.ceq or comparison.op == ir.Op.cne) and is_zero(comparison.b) and comparison.a.kind == ir.RefKind.temp and hops < 4:
let inner = self.definitions[comparison.a.index]
if inner == 0 or not ir.is_comparison(self.f.instrs.get(inner - 1).op):
break
if comparison.op == ir.Op.ceq:
yes = not yes
comparison = self.f.instrs.get(inner - 1)
hops += 1
if comparison.cls != ir.Class.w and comparison.cls != ir.Class.l:
return
let a = comparison.a
let b = comparison.b
try self.compared(comparison.op, comparison.cls, comparison.a, comparison.b, yes)
# a word zero-extended for its comparison (a shift count against the width) is
# bounded as the word itself
let a_word = self.extended_word(comparison.a)
let b_word = self.extended_word(comparison.b)
if comparison.cls == ir.Class.l and a_word.kind == ir.RefKind.temp and comparison.b.kind == ir.RefKind.constant and bits(comparison.b, ir.Class.l) <= limit(ir.Class.w):
try self.compared(comparison.op, ir.Class.w, a_word, comparison.b, yes)
if comparison.cls == ir.Class.l and b_word.kind == ir.RefKind.temp and comparison.a.kind == ir.RefKind.constant and bits(comparison.a, ir.Class.l) <= limit(ir.Class.w):
try self.compared(comparison.op, ir.Class.w, comparison.a, b_word, yes)
## The facts a comparison `a op b` at `cls` establishes when it is `yes`, or false.
func compared(op: ir.Op, cls: ir.Class, a: ir.Ref, b: ir.Ref, yes: bool) -> !:
match op:
.cult: try self.add(Relation.less if yes else Relation.at_most, cls, a if yes else b, b if yes else a)
.cule: try self.add(Relation.at_most if yes else Relation.less, cls, a if yes else b, b if yes else a)
.cugt: try self.add(Relation.less if yes else Relation.at_most, cls, b if yes else a, a if yes else b)
.cuge: try self.add(Relation.at_most if yes else Relation.less, cls, b if yes else a, a if yes else b)
.ceq, .cne:
if yes == (op == ir.Op.ceq):
try self.add(Relation.equal, cls, a, b)
elif is_zero(b):
# unsigned, a value other than 0 is above it
try self.add(Relation.less, cls, b, a)
elif is_zero(a):
try self.add(Relation.less, cls, a, b)
_: _ = 0
## The word `r` zero-extends (`extuw`), or none.
func extended_word(r: ir.Ref) -> ir.Ref:
if r.kind != ir.RefKind.temp or self.definitions[r.index] == 0:
return ir.none_ref()
let definition = self.f.instrs.get(self.definitions[r.index] - 1)
return definition.a if definition.op == ir.Op.extuw else ir.none_ref()
## Walk the dominator tree from block `root`: each block's facts hold in the blocks it
## dominates and are dropped after them. An explicit stack, not recursion, as in
## `gvn.number`: a long function is a long chain of blocks.
func visit(root: u32) -> !:
var stack = try list.List[RangeVisit].create(64)
defer stack.destroy()
try stack.push(RangeVisit(block = root, child = 0, mark = self.facts.count, product_mark = self.products.count, decision_mark = self.decisions.count))
try self.visit_block(root)
while stack.count > 0:
var top = stack.get(stack.count - 1)
let block = self.g.blocks.get(top.block)
if top.child < block.children.count:
let child = block.children.get(top.child)
top.child += 1
stack.set(stack.count - 1, top)
try stack.push(RangeVisit(block = child, child = 0, mark = self.facts.count, product_mark = self.products.count, decision_mark = self.decisions.count))
try self.visit_block(child)
else:
self.truncate(top.mark)
self.products.count = top.product_mark
while self.decisions.count > top.decision_mark:
self.outcomes[self.decisions.get(self.decisions.count - 1)] = undecided
self.decisions.count -= 1
stack.count -= 1
## Take in block `index`'s incoming facts and its instructions' own, and drop the checks
## the facts make redundant.
func visit_block(index: u32) -> !:
let block = self.g.blocks.get(index)
try self.incoming(block)
var at = block.start
while at < block.end:
var instruction = self.f.instrs.get(at)
let checked_product = instruction.op == ir.Op.mulo and instruction.extra == 0
if is_unsigned_comparison(instruction.op) and (instruction.cls == ir.Class.w or instruction.cls == ir.Class.l) and instruction.dst != 0:
# a comparison the facts decide, a masked shift count against the width
# among them (`(u64)(bits & 63)` is below 64): its answer, which value
# numbering carries into the branch that tests it
if let truth = self.decided(instruction.op, instruction.a, instruction.b, instruction.cls):
instruction = ir.Instr(op = ir.Op.copy, cls = ir.Class.w, dst = instruction.dst, a = ir.const_ref(1 if truth else 0), b = ir.none_ref(), extra = 0, extra2 = 0, line = instruction.line, file = instruction.file, scope = instruction.scope, site = instruction.site)
self.f.instrs.set(at, instruction)
self.changed = true
elif instruction.op == ir.Op.bounds:
# below the bound, or at most it for a one-past-the-end bound (`extra` 1)
let strict = instruction.extra == 0
if self.at_most(instruction.a, instruction.b, ir.Class.l, strict) or self.packed_bound(instruction.a, instruction.b) or self.scaled_below(instruction.a, instruction.b, strict) or self.below_through_difference(instruction.a, instruction.b) or try self.chosen_below(instruction.a, instruction.b, strict):
# Keep graph instruction ranges stable until the walk ends.
instruction = ir.Instr(op = ir.Op.copy, 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)
self.f.instrs.set(at, instruction)
self.changed = true
else:
try self.add(Relation.less if strict else Relation.at_most, ir.Class.l, instruction.a, instruction.b)
elif (instruction.op == ir.Op.addo or instruction.op == ir.Op.subo or instruction.op == ir.Op.mulo) and instruction.extra == 0:
let high_a = self.upper(instruction.a, instruction.cls)
let high_b = self.upper(instruction.b, instruction.cls)
let maximum = limit(instruction.cls)
var safe = false
var operation = ir.Op.add
if instruction.op == ir.Op.addo:
safe = high_a <= maximum - high_b or self.sum_fits(instruction.a, instruction.b, instruction.cls)
elif instruction.op == ir.Op.subo:
safe = self.at_most(instruction.b, instruction.a, instruction.cls, false) or self.upper(instruction.b, instruction.cls) <= self.lower(instruction.a, instruction.cls)
operation = ir.Op.sub
else:
safe = high_b == 0 or high_a <= maximum // high_b or self.product_fits(instruction.a, instruction.b, instruction.cls)
operation = ir.Op.mul
if safe:
instruction.op = operation
instruction.extra = 0
instruction.extra2 = 0
self.f.instrs.set(at, instruction)
self.changed = true
elif instruction.op == ir.Op.jnz and instruction.a.kind == ir.RefKind.temp and instruction.extra != instruction.extra2:
# a branch on a condition an edge above already decided (a shift count
# checked once, tested again for the next shift by the same count)
let decision = self.outcomes[instruction.a.index] if (usize)instruction.a.index < self.outcomes.length else undecided
if decision != undecided:
let taken = instruction.extra if decision == held else instruction.extra2
instruction = ir.Instr(op = ir.Op.jmp, cls = ir.Class.l, dst = 0, a = ir.none_ref(), b = ir.none_ref(), extra = taken, extra2 = 0, line = instruction.line, file = instruction.file, scope = instruction.scope, site = instruction.site)
self.f.instrs.set(at, instruction)
self.changed = true
if checked_product:
try self.products.push(Product(cls = instruction.cls, left = instruction.a, right = instruction.b, value = ir.temp_ref(instruction.dst)))
at += 1
# mark: The pass ==============================================================================
## Run after value numbering/load forwarding, while temporaries still have one
## definition. The caller rebuilds its graph when instructions were removed.
pub func run(f: ir.Function*, g: cfg.Graph*) -> bool!:
let buckets = f.temps.count + 1 + shared_buckets
var search = Search(f = f, g = g, definitions = try new u32[f.temps.count + 1] ---, facts = try list.List[Fact].create(32), left_heads = try new u32[buckets] ---, right_heads = try new u32[buckets] ---, products = try list.List[Product].create(8), join_of = try new u32[f.temps.count + 1] ---, outcomes = try new u8[f.temps.count + 1] ---, decisions = try list.List[u32].create(16))
defer free(search.definitions)
defer free(search.join_of)
defer free(search.outcomes)
defer search.decisions.destroy()
for index in 0..<search.outcomes.length:
search.outcomes[index] = undecided
for index in 0..<search.join_of.length:
search.join_of[index] = 0
for b in 0..<g.count():
let block = g.blocks.get(b)
for at in block.start..<block.end:
let instruction = f.instrs.get((usize)at)
if instruction.op == ir.Op.phi and instruction.dst != 0:
search.join_of[instruction.dst] = (u32)b + 1
defer free(search.left_heads)
defer free(search.right_heads)
for index in 0..<buckets:
search.left_heads[index] = 0
search.right_heads[index] = 0
defer search.facts.destroy()
defer search.products.destroy()
for index in 0..<search.definitions.length:
search.definitions[index] = 0
for index in 0..<f.instrs.count:
let instruction = f.instrs.get(index)
if instruction.dst != 0:
search.definitions[instruction.dst] = (u32)index + 1
if g.count() > 0:
try search.visit(0)
if search.changed:
var kept = try list.List[ir.Instr].create(f.instrs.count)
for instruction in f.instrs.span():
if instruction.op != ir.Op.copy or instruction.dst != 0:
try kept.push(instruction)
f.instrs.destroy()
f.instrs = kept
return search.changed
func is_unsigned_comparison(op: ir.Op) -> bool:
return op == ir.Op.cult or op == ir.Op.cule or op == ir.Op.cugt or op == ir.Op.cuge
## How many bits `value` needs: 0 for 0, 1 for 1, 3 for 7.
func significant(value: u64) -> u64:
var n: u64 = 0
var rest = value
while rest != 0:
rest >>= 1
n += 1
return n
func is_zero(value: ir.Ref) -> bool:
return value.kind == ir.RefKind.constant and value.value == 0
func same(a: ir.Ref, b: ir.Ref) -> bool:
return a.kind == b.kind and a.index == b.index and a.value == b.value and a.name == b.name
func limit(cls: ir.Class) -> u64:
return 4294967295 if cls == ir.Class.w else 18446744073709551615
func bits(value: ir.Ref, cls: ir.Class) -> u64:
return (u64)(u32)value.value if cls == ir.Class.w else (u64)value.value