dymokomi/luce-base
Source of release 0.46.0
0.46.0 / src / back / opt / slp.lucb
#==============================================================================================
#
# slp - Paired float arithmetic as vector operations, within a basic block
#
# DESCRIPTION:
# Superword-level parallelism (Larsen and Amarasinghe; LLVM's bottom-up form): stores
# of doubles to two neighbouring addresses, or of singles to four (two on arm64), seed
# a tree of lanes. Lanes the same operation computes become one vector operation of
# their operands' lanes, and loads from neighbouring addresses one vector load; any
# other lanes are packed from their scalars (a broadcast when they are one value).
# The tree is kept when it saves instructions: each vector operation, load and store
# saves all but one of its lanes' scalars, each packing and each lane a scalar still
# needs elsewhere costs one or two.
#
# A vector operation stands where its last lane did, its operands before it and a
# lane's scalar, when something outside the tree reads it, extracted after it. A tree
# is kept only when that order keeps the program's: every scalar outside it reads a
# lane after the vector computes it, and no load or store crosses a store or a call it
# may touch (`load.Aliases`), nor a store a check that may trap. Each lane computes
# what its scalar computed, in the same order, rounding once: lane-wise IEEE
# arithmetic is exact as the scalar is, so the results are the same bits. A sum or a
# product may take its operands in either order, as value numbering already does.
#
#==============================================================================================
import back.ir.cfg
import back.ir.ir
import back.opt.load
import back.target as targets
import support.list
# mark: Nodes =================================================================================
## A tree node's kind: lanes one vector operation computes, lanes loaded together, the
## seed's stores, one value in every lane, and lanes packed from their scalars.
let operation: u8 = 1
let loaded: u8 = 2
let stored: u8 = 3
let broadcast: u8 = 4
let packed: u8 = 5
## No node, no instruction.
let none_index: u32 = 0xFFFFFFFF
## How deep a tree goes before its lanes are packed from scalars instead.
let deepest: u32 = 12
## The most instructions a tree may span, so the order checks stay cheap.
let widest_span: u32 = 384
## One node of a tree of lanes.
struct Node:
var kind: u8
## The vector operation, for an `operation` node.
var op: ir.Op
## The lanes' class, `d` or `s`.
var cls: ir.Class
## The lanes' values (a store's stored value for `stored`).
var values: ir.Ref[4]
## The scalar instruction of each lane, for `operation`, `loaded` and `stored`.
var instrs: u32[4]
## The operand nodes: the first, the second (`none_index` when there is none).
var first: u32
var second: u32
## Where the vector operation stands: the last of its lanes' instructions.
var at: u32
## The vector temporary, once emitted.
var vector: u32
## A vector instruction to place after instruction `at` of the function.
struct Insert:
var at: u32
var instr: ir.Instr
# mark: The pass ==============================================================================
## Pack the paired float arithmetic of `f`'s blocks into vector operations where it pays,
## for a target of `arch`; whether anything changed.
pub func run(f: ir.Function*, arch: targets.Arch) -> bool!:
if f.naked or f.debug or f.symbols or not has_seed(f):
return false
var g = try cfg.Graph.over(f)
defer g.release()
var aliases = try load.Aliases.over(f, &g)
defer aliases.release()
var s = try Pass.over(f, &g, &aliases, arch)
defer s.release()
for b in g.order.span():
try s.block(g.blocks.get((usize)b))
if s.inserts.count == 0:
return false
try s.rewrite()
return true
## Whether `f` stores a float anywhere: no tree grows without a seed.
func has_seed(f: ir.Function*) -> bool:
for x in f.instrs.span():
if x.op == ir.Op.stored or x.op == ir.Op.stores:
return true
return false
## The pass over one function: where each temporary is defined and read, the trees of the
## block at hand, and what the kept ones put in and take out.
struct Pass:
var f: ir.Function*
var g: cfg.Graph*
var aliases: load.Aliases*
var arch: targets.Arch
## Per temporary, the instruction defining it; `none_index` for none.
var defined: u32[]
## Per instruction, the block holding it.
var block_of: u32[]
## The readers of each temporary, as positions: `use_start[t] ..< use_start[t + 1]`
## of `use_at` (an instruction's index; a phi's argument reads at its predecessor's end,
## after its last instruction, and `by_phi` says so: that instruction is not the reader).
var use_start: u32[]
var use_at: u32[]
var by_phi: bool[]
## Per instruction, whether a kept tree took it (`claimed`) or removed it (`removed`).
var claimed: bool[]
var removed: bool[]
## The tree being grown.
var nodes: list.List[Node]
## The kept trees' vector instructions, in order.
var inserts: list.List[Insert]
## The block at hand.
var start: u32
var end: u32
static func over(f: ir.Function*, g: cfg.Graph*, aliases: load.Aliases*, arch: targets.Arch) -> Pass!:
let n = f.instrs.count
var s = Pass(f = f, g = g, aliases = aliases, arch = arch, defined = try new u32[f.temps.count + 1] ---, block_of = try new u32[n + 1] ---, use_start = try new u32[f.temps.count + 2] ---, use_at = try new u32[1] ---, by_phi = try new bool[1] ---, claimed = try new bool[n + 1] ---, removed = try new bool[n + 1] ---, nodes = try list.List[Node].create(16), inserts = try list.List[Insert].create(16), start = 0, end = 0)
for t in 0..<s.defined.length:
s.defined[t] = none_index
for i in 0..<s.claimed.length:
s.claimed[i] = false
s.removed[i] = false
s.block_of[i] = none_index
for b in 0..<g.blocks.count:
let block = g.blocks.get(b)
for i in block.start..<block.end:
s.block_of[(usize)i] = u32(b)
for i in 0..<n:
let x = f.instrs.get(i)
if x.dst != 0:
s.defined[(usize)x.dst] = u32(i)
try s.find_uses()
return s
func release():
free(self.defined)
free(self.block_of)
free(self.use_start)
free(self.use_at)
free(self.by_phi)
free(self.claimed)
free(self.removed)
self.nodes.destroy()
self.inserts.destroy()
# mark: Readers ===========================================================================
## Every reader of every temporary, counted then placed: an instruction's operands and
## arguments at its index, a phi's argument at the last instruction of the block it
## comes from.
func find_uses() -> !:
let temps = self.f.temps.count + 1
var counts = try new u32[temps] ---
defer free(counts)
for t in 0..<temps:
counts[t] = 0
self.walk_uses(counts, false)
var total: u32 = 0
for t in 0..<temps:
self.use_start[t] = total
total += counts[t]
counts[t] = self.use_start[t]
self.use_start[temps] = total
free(self.use_at)
free(self.by_phi)
self.use_at = try new u32[(usize)total + 1] ---
self.by_phi = try new bool[(usize)total + 1] ---
self.walk_uses(counts, true)
## One pass over the readers: counting each temporary's in `counts`, or, with `place`,
## writing each at the next free position `counts` holds.
func walk_uses(counts: u32[], place: bool):
for i in 0..<self.f.instrs.count:
let x = self.f.instrs.get(i)
if x.op == ir.Op.phi:
for k in 0..<x.extra2:
let arg = self.f.phi_args.get((usize)(x.extra + k))
let pred = self.g.block_of(arg.pred)
var at = u32(i)
if pred != cfg.none_block:
let block = self.g.blocks.get((usize)pred)
at = block.end - 1 if block.end > block.start else block.end
self.use(counts, arg.value, at, true, place)
continue
self.use(counts, x.a, u32(i), false, place)
self.use(counts, x.b, u32(i), false, place)
let (args_start, args_count) = ir.argument_range(self.f, x)
for k in 0..<args_count:
self.use(counts, self.f.args.get((usize)(args_start + k)).value, u32(i), false, place)
func use(counts: u32[], r: ir.Ref, at: u32, phi: bool, place: bool):
if r.kind != ir.RefKind.temp or (usize)r.index >= counts.length:
return
if place:
self.use_at[(usize)counts[(usize)r.index]] = at
self.by_phi[(usize)counts[(usize)r.index]] = phi
counts[(usize)r.index] += 1
# mark: Seeds =============================================================================
## The trees block `block` grows, each from stores to neighbouring addresses: the lowest
## of a run of them starts a group, of two doubles, or of four singles, else two.
func block(block: cfg.Block) -> !:
if block.end - block.start < 4:
return
self.start = block.start
self.end = block.end
var stores = try list.List[u32].create(8)
defer stores.destroy()
for i in block.start..<block.end:
let x = self.f.instrs.get((usize)i)
if x.op == ir.Op.stored or x.op == ir.Op.stores:
try stores.push(i)
if stores.count < 2:
return
var tried = try new bool[stores.count] ---
defer free(tried)
for k in 0..<stores.count:
tried[k] = false
for k in 0..<stores.count:
let i = stores.get(k)
if self.claimed[(usize)i] or self.neighbour(&stores, tried, i, -1, true) != none_index:
continue
tried[k] = true
let x = self.f.instrs.get((usize)i)
var group: u32[4] = [i, none_index, none_index, none_index]
var lanes: u32 = 2 if x.op == ir.Op.stored else 4
var found = true
for l in 1..<lanes:
group[l] = self.neighbour(&stores, tried, i, (i64)l, false)
found = found and group[l] != none_index
if not found and lanes == 4 and group[1] != none_index:
lanes = 2
found = true
if found:
try self.seed(group, lanes)
## The store of the same kind as store `i`, in the block's `stores`, unclaimed, at `l`
## lanes past it (`l` negative: before it); `none_index` when there is none. With
## `untried`, only a store not yet tried as a group's start counts.
func neighbour(stores: list.List[u32]*, tried: bool[], i: u32, l: i64, untried: bool) -> u32:
let x = self.f.instrs.get((usize)i)
let width = width_of(x.op)
let here = self.aliases.at(x.b, 0)
for k in 0..<stores.count:
let j = stores.get(k)
let y = self.f.instrs.get((usize)j)
if j == i or y.op != x.op or self.claimed[(usize)j] or (untried and tried[k]):
continue
let there = self.aliases.at(y.b, 0)
if same_base(here, there) and there.offset == here.offset +% l * width:
return j
return none_index
## Grow the tree of the stores `group` of `lanes` lanes, and keep it if it is lawful and
## pays.
func seed(group: u32[4], lanes: u32) -> !:
self.nodes.count = 0
let first = self.f.instrs.get((usize)group[0])
let cls = ir.Class.d if first.op == ir.Op.stored else ir.Class.s
var values: ir.Ref[4] = [ir.none_ref(), ir.none_ref(), ir.none_ref(), ir.none_ref()]
var at: u32 = 0
for l in 0..<lanes:
values[l] = self.f.instrs.get((usize)group[l]).a
at = group[l] if group[l] > at else at
let child = try self.build(values, lanes, cls, 0)
if child == none_index:
return
try self.nodes.push(Node(kind = stored, op = ir.Op.storev, cls = cls, values = values, instrs = group, first = child, second = none_index, at = at, vector = 0))
var extracts = try new bool[self.nodes.count * 4] ---
defer free(extracts)
for k in 0..<extracts.length:
extracts[k] = false
if not try self.ordered(lanes, extracts) or not self.reaches(lanes) or self.profit(lanes, extracts) < 1:
return
try self.emit(lanes, extracts)
# mark: Growing a tree ====================================================================
## The node computing `values`, `lanes` of class `cls`, `depth` below the seed: one
## operation or one load of every lane where the lanes allow it, else a broadcast or a
## packing; `none_index` when nothing can (four singles packed on x86-64, which has no
## instruction for a lane past the second before SSE4.1).
func build(values: ir.Ref[4], lanes: u32, cls: ir.Class, depth: u32) -> u32!:
var same = true
for l in 1..<lanes:
same = same and same_value(values[0], values[l])
if same and not self.narrow(lanes, cls):
return try self.add(Node(kind = broadcast, op = ir.Op.vsplat, cls = cls, values = values, instrs = no_instrs(), first = none_index, second = none_index, at = 0, vector = 0))
if depth < deepest:
if let found = try self.lanes_of(values, lanes, cls, depth):
return found
if self.narrow(lanes, cls) or (lanes > 2 and self.arch == targets.Arch.x86_64):
return none_index
return try self.add(Node(kind = packed, op = ir.Op.vinsert, cls = cls, values = values, instrs = no_instrs(), first = none_index, second = none_index, at = 0, vector = 0))
## Whether lanes of `lanes` and `cls` are two singles on x86-64, which only loads, stores
## and converts: SSE computes on four, and the two it would not use hold anything.
func narrow(lanes: u32, cls: ir.Class) -> bool:
return self.arch == targets.Arch.x86_64 and lanes == 2 and cls == ir.Class.s
## The node one instruction per lane makes of `values`: the same operation, of the same
## class, in this block, on instructions no tree has taken; none when there is none.
func lanes_of(values: ir.Ref[4], lanes: u32, cls: ir.Class, depth: u32) -> u32?!:
var instrs = no_instrs()
var at: u32 = 0
for l in 0..<lanes:
let v = values[l]
if v.kind != ir.RefKind.temp or (usize)v.index >= self.defined.length:
return none
let i = self.defined[(usize)v.index]
if i == none_index or i < self.start or i >= self.end or self.claimed[(usize)i]:
return none
instrs[l] = i
at = i if i > at else at
let x = self.f.instrs.get((usize)instrs[0])
if x.cls != cls:
return none
for l in 1..<lanes:
let y = self.f.instrs.get((usize)instrs[l])
if y.op != x.op or y.cls != cls or instrs[l] == instrs[0]:
return none
if let known = self.node_of(instrs, lanes):
return known
for l in 0..<lanes:
if self.taken(instrs[l], lanes) != none:
# a lane of another node of the tree: packed from its scalar instead
return none
if x.op == ir.Op.loadd or x.op == ir.Op.loads:
let base = self.aliases.at(x.a, 0)
for l in 1..<lanes:
let there = self.aliases.at(self.f.instrs.get((usize)instrs[l]).a, 0)
if not same_base(base, there) or there.offset != base.offset +% (i64)l * width_of(x.op):
return none
return try self.add(Node(kind = loaded, op = ir.Op.loadv, cls = cls, values = values, instrs = instrs, first = none_index, second = none_index, at = at, vector = 0))
let op = vector_of(x.op)
if op == ir.Op.copy or (self.narrow(lanes, cls) and op != ir.Op.vtruncd):
return none
# a conversion's operands are lanes of the other width
let operand_cls = ir.Class.s if op == ir.Op.vexts else (ir.Class.d if op == ir.Op.vtruncd else cls)
if (op == ir.Op.vexts or op == ir.Op.vtruncd) and lanes != 2:
return none
var left: ir.Ref[4] = [x.a, ir.none_ref(), ir.none_ref(), ir.none_ref()]
var right: ir.Ref[4] = [x.b, ir.none_ref(), ir.none_ref(), ir.none_ref()]
for l in 1..<lanes:
let y = self.f.instrs.get((usize)instrs[l])
left[l] = y.a
right[l] = y.b
if (x.op == ir.Op.add or x.op == ir.Op.mul) and self.likeness(x.a, y.b) + self.likeness(x.b, y.a) > self.likeness(x.a, y.a) + self.likeness(x.b, y.b):
# the sum or product's operands the other way, as the first lane has them
left[l] = y.b
right[l] = y.a
let first = try self.build(left, lanes, operand_cls, depth + 1)
if first == none_index:
return none_index
var second = none_index
if op != ir.Op.vneg and op != ir.Op.vsqrt and op != ir.Op.vexts and op != ir.Op.vtruncd:
second = try self.build(right, lanes, cls, depth + 1)
if second == none_index:
return none_index
return try self.add(Node(kind = operation, op = op, cls = cls, values = values, instrs = instrs, first = first, second = second, at = at, vector = 0))
## How alike two operands are, for the order of a sum's or a product's: the same value,
## or loads from neighbouring addresses, most; values one kind of instruction computes,
## less; anything else, not at all.
func likeness(p: ir.Ref, q: ir.Ref) -> u32:
if same_value(p, q):
return 3
if p.kind != ir.RefKind.temp or q.kind != ir.RefKind.temp or (usize)p.index >= self.defined.length or (usize)q.index >= self.defined.length:
return 0
let i = self.defined[(usize)p.index]
let j = self.defined[(usize)q.index]
if i == none_index or j == none_index:
return 0
let x = self.f.instrs.get((usize)i)
let y = self.f.instrs.get((usize)j)
if x.op != y.op:
return 0
if (x.op == ir.Op.loadd or x.op == ir.Op.loads) and same_base(self.aliases.at(x.a, 0), self.aliases.at(y.a, 0)):
return 3
return 2
## The tree's node for exactly these lanes' instructions, already grown.
func node_of(instrs: u32[4], lanes: u32) -> u32?:
for k in 0..<self.nodes.count:
let n = self.nodes.get(k)
if n.kind != operation and n.kind != loaded:
continue
var same = true
for l in 0..<lanes:
same = same and n.instrs[l] == instrs[l]
if same:
return u32(k)
return none
## Whether instruction `i` is a lane of a node of the tree; its node.
func taken(i: u32, lanes: u32) -> u32?:
for k in 0..<self.nodes.count:
let n = self.nodes.get(k)
if n.kind == operation or n.kind == loaded or n.kind == stored:
for l in 0..<lanes:
if n.instrs[l] == i:
return u32(k)
return none
func add(n: Node) -> u32!:
try self.nodes.push(n)
return u32(self.nodes.count - 1)
# mark: Whether a tree is kept ============================================================
## Whether every scalar a lane's value is still read as comes after the node computing
## it, where the lane is then extracted (`extracts`, four flags a node): each reader
## outside the tree, and each packing or broadcast of the value, which stands before
## the node reading it. A tree spanning more than `widest_span` instructions is left be.
func ordered(lanes: u32, extracts: bool[]) -> bool!:
let root = self.nodes.get(self.nodes.count - 1)
var low = root.at
for n in self.nodes.span():
if n.kind == operation or n.kind == loaded or n.kind == stored:
for l in 0..<lanes:
low = n.instrs[l] if n.instrs[l] < low else low
if root.at - low > widest_span:
return false
for k in 0..<self.nodes.count:
let n = self.nodes.get(k)
if n.kind != operation and n.kind != loaded:
continue
for l in 0..<lanes:
let t = (usize)n.values[l].index
for p in (usize)self.use_start[t]..<(usize)self.use_start[t + 1]:
let u = self.use_at[p]
if self.by_phi[p]:
# a phi past the block's end: it reads the scalar after the node
if not self.later(u, n.at) and u != n.at:
return false
extracts[k * 4 + l] = true
continue
if self.taken(u, lanes) != none:
# a lane reads it through this node, or through a packing below
continue
if not self.later(u, n.at):
return false
extracts[k * 4 + l] = true
for n in self.nodes.span():
if n.kind != operation and n.kind != stored:
continue
if not try self.packs_after(n, n.first, lanes, extracts) or not try self.packs_after(n, n.second, lanes, extracts):
return false
return true
## Whether the packing or broadcast `child` of `n` reads each lane value of the tree it
## takes after that value's node computes it; the lanes it takes are extracted.
func packs_after(n: Node, child: u32, lanes: u32, extracts: bool[]) -> bool!:
if child == none_index:
return true
let c = self.nodes.get((usize)child)
if c.kind != packed and c.kind != broadcast:
return true
for l in 0..<lanes:
let v = c.values[l]
if v.kind != ir.RefKind.temp or (usize)v.index >= self.defined.length or self.defined[(usize)v.index] == none_index:
continue
if let owner = self.taken(self.defined[(usize)v.index], lanes):
let m = self.nodes.get((usize)owner)
if n.at <= m.at:
return false
for l2 in 0..<lanes:
if same_value(m.values[l2], v):
extracts[(usize)owner * 4 + l2] = true
return true
## Whether a read at instruction `u` comes after instruction `at`: later in the same
## block, or in another (which the value's block dominates).
func later(u: u32, at: u32) -> bool:
return (usize)u >= self.block_of.length or self.block_of[(usize)u] != self.block_of[(usize)at] or u > at
## Whether moving each load and store of the tree to its node's place keeps every access
## it passes in order: a load passes no store it may touch, a store no access it may
## touch and no check that may trap, and neither passes a call or anything else that
## reaches memory unseen.
func reaches(lanes: u32) -> bool:
for k in 0..<self.nodes.count:
let n = self.nodes.get(k)
if n.kind != loaded and n.kind != stored:
continue
for l in 0..<lanes:
let i = n.instrs[l]
let x = self.f.instrs.get((usize)i)
for j in i + 1..<n.at + 1:
if let m = self.taken(j, lanes):
if m == u32(k) or self.nodes.get((usize)m).at > n.at:
continue
if not self.passes(x, self.f.instrs.get((usize)j)):
return false
return true
## Whether the scalar load or store `x` may move past instruction `y`.
func passes(x: ir.Instr, y: ir.Instr) -> bool:
let storing = x.op == ir.Op.stored or x.op == ir.Op.stores
if barrier(y):
return false
if may_trap(y):
return not storing
let y_loads = load.is_load(y.op) or y.op == ir.Op.loadv
let y_stores = load.is_store(y.op) or y.op == ir.Op.storev
if not y_stores and not (y_loads and storing):
return true
let here = self.aliases.at(x.b if storing else x.a, 0)
let there = y.b if y_stores else y.a
return self.aliases.relation(here, width_of(x.op), there, access_width(y)) == load.no_alias
## What the tree saves: every vector operation, load and store all but one of its lanes'
## instructions; less one for each broadcast (two on x86-64, whose broadcast copies the
## scalar first), as many as the lanes for each packing, and one for each lane extracted
## (two past the first on x86-64, which shuffles the lane down).
func profit(lanes: u32, extracts: bool[]) -> i64:
let x86 = self.arch == targets.Arch.x86_64
var gain: i64 = 0
for k in 0..<self.nodes.count:
let n = self.nodes.get(k)
if n.kind == operation or n.kind == loaded or n.kind == stored:
gain += (i64)lanes - 1
elif n.kind == broadcast:
gain -= 2 if x86 else 1
else:
gain -= (i64)lanes
for l in 0..<lanes:
if extracts[k * 4 + l]:
gain -= 2 if x86 and l > 0 else 1
return gain
# mark: Emitting a kept tree ==============================================================
## The tree's vector instructions, each after the last of its lanes' instructions, which
## go: its operands' packings and broadcasts first, then the operation, then the lanes
## a scalar still reads, extracted into the temporaries that held them.
func emit(lanes: u32, extracts: bool[]) -> !:
for k in 0..<self.nodes.count:
var n = self.nodes.get(k)
if n.kind == packed or n.kind == broadcast:
continue
let shape = shape_of(n.cls, lanes)
let near = self.f.instrs.get((usize)n.at)
let a = try self.operand(n.first, n.at, near, lanes)
let b = try self.operand(n.second, n.at, near, lanes)
let lane0 = self.f.instrs.get((usize)n.instrs[0])
if n.kind == stored:
try self.insert(n.at, near, ir.Op.storev, ir.Class.v, 0, a, lane0.b, shape, 0)
else:
n.vector = try self.f.temp(ir.Class.v)
self.nodes.set(k, n)
if n.kind == loaded:
try self.insert(n.at, near, ir.Op.loadv, ir.Class.v, n.vector, lane0.a, ir.none_ref(), shape, 0)
else:
try self.insert(n.at, near, n.op, ir.Class.v, n.vector, a, b, shape, 0)
for l in 0..<lanes:
if extracts[k * 4 + l]:
try self.insert(n.at, near, ir.Op.vextract, n.cls, n.values[l].index, ir.temp_ref(n.vector), ir.none_ref(), shape, l)
for l in 0..<lanes:
self.removed[(usize)n.instrs[l]] = true
self.claimed[(usize)n.instrs[l]] = true
## The vector operand node `child` stands for at `at`: an emitted node's own vector, or a
## broadcast or packing formed there.
func operand(child: u32, at: u32, near: ir.Instr, lanes: u32) -> ir.Ref!:
if child == none_index:
return ir.none_ref()
let c = self.nodes.get((usize)child)
let shape = shape_of(c.cls, lanes)
if c.kind == operation or c.kind == loaded:
return ir.temp_ref(c.vector)
if c.kind == broadcast:
let t = try self.f.temp(ir.Class.v)
try self.insert(at, near, ir.Op.vsplat, ir.Class.v, t, c.values[0], ir.none_ref(), shape, 0)
return ir.temp_ref(t)
var vector = ir.none_ref()
for l in 0..<lanes:
let t = try self.f.temp(ir.Class.v)
try self.insert(at, near, ir.Op.vinsert, ir.Class.v, t, vector, c.values[l], shape, l)
vector = ir.temp_ref(t)
return vector
func insert(at: u32, near: ir.Instr, op: ir.Op, cls: ir.Class, dst: u32, a: ir.Ref, b: ir.Ref, shape: u32, lane: u32) -> !:
try self.inserts.push(Insert(at = at, instr = ir.Instr(op = op, cls = cls, dst = dst, a = a, b = b, extra = shape, extra2 = lane, line = near.line, file = near.file, scope = near.scope, site = near.site)))
## The function's instructions again: the removed ones gone, each insert after the
## instruction it names, in the order the trees made them.
func rewrite() -> !:
let n = self.f.instrs.count
var first = try new u32[n + 1] ---
defer free(first)
for i in 0..<first.length:
first[i] = 0
for x in self.inserts.span():
first[(usize)x.at + 1] += 1
for i in 1..<first.length:
first[i] += first[i - 1]
var order = try new u32[self.inserts.count] ---
defer free(order)
var next = try new u32[n + 1] ---
defer free(next)
for i in 0..<first.length:
next[i] = first[i]
for k in 0..<self.inserts.count:
let at = (usize)self.inserts.get(k).at
order[(usize)next[at]] = u32(k)
next[at] += 1
var out = try list.List[ir.Instr].create(n + self.inserts.count)
for i in 0..<n:
if not self.removed[i]:
try out.push(self.f.instrs.get(i))
let stop = (usize)first[i + 1] if i + 1 < first.length else self.inserts.count
for k in (usize)first[i]..<stop:
try out.push(self.inserts.get((usize)order[k]).instr)
self.f.instrs.destroy()
self.f.instrs = out
# mark: Helpers ===============================================================================
## The shape of `lanes` float lanes of class `cls`.
func shape_of(cls: ir.Class, lanes: u32) -> u32:
return ir.lanes(64 if cls == ir.Class.d else 32, lanes, true, false)
func no_instrs() -> u32[4]:
return [none_index, none_index, none_index, none_index]
## Whether two operands are one value: the same temporary or the same constant.
func same_value(p: ir.Ref, q: ir.Ref) -> bool:
if p.kind != q.kind:
return false
if p.kind == ir.RefKind.temp:
return p.index == q.index
return p.kind == ir.RefKind.constant and p.value == q.value
## Whether two addresses are offsets from one base.
func same_base(a: load.Alias, b: load.Alias) -> bool:
return a.kind == b.kind and a.base == b.base and a.name == b.name
## The bytes a scalar float load or store moves.
func width_of(op: ir.Op) -> i64:
return 8 if op == ir.Op.loadd or op == ir.Op.stored else 4
## The bytes any load or store moves, for the order of two accesses.
func access_width(y: ir.Instr) -> i64:
if y.op == ir.Op.loadv or y.op == ir.Op.storev:
return (i64)ir.vector_bytes(y.extra)
match y.op:
.loadsb, .loadub, .storeb: return 1
.loadsh, .loaduh, .loadhf, .storeh, .storehf: return 2
.loadsw, .loaduw, .loads, .storew, .stores: return 4
_: return 8
## The vector operation computing a float scalar operation lane by lane; `copy` for none.
func vector_of(op: ir.Op) -> ir.Op:
match op:
.add: return ir.Op.vadd
.sub: return ir.Op.vsub
.mul: return ir.Op.vmul
.sdiv: return ir.Op.vdiv
.neg: return ir.Op.vneg
.fsqrt: return ir.Op.vsqrt
.exts: return ir.Op.vexts
.truncd: return ir.Op.vtruncd
_: return ir.Op.copy
## Whether `y` reaches memory beyond what a load or store names, or runs what may: a call,
## an atomic, a fence, an asm block, a block copy, the frame's own storage.
func barrier(y: ir.Instr) -> bool:
match y.op:
.call, .asm_, .set_reg, .get_reg, .blit, .zero, .fill, .fence, .alloca, .reserve, .atomic_load, .atomic_store, .atomic_add, .atomic_sub, .atomic_or, .atomic_and_not, .atomic_xor, .atomic_swap, .atomic_max, .atomic_min, .atomic_cas: return true
_: return false
## Whether `y` may trap: a check, a checked operation, an integer division.
func may_trap(y: ir.Instr) -> bool:
match y.op:
.bounds, .addo, .subo, .mulo, .trap_, .vaddo, .vsubo: return true
.sdiv, .udiv, .srem, .urem: return not ir.is_float_class(y.cls)
_: return false