dymokomi/luce-base
Source of release 0.41.0
0.41.0 / src / back / opt / vectorize.lucb
#==============================================================================================
#
# vectorize - Versioning counted loops for 128-bit SIMD
#
# DESCRIPTION:
# A recognized loop contains only contiguous loads, arithmetic and at most one store, or
# one wrapping integer sum; everything else keeps its scalar implementation. Float
# expressions retain their operation order, and float reductions are excluded.
#
#==============================================================================================
import back.ir.cfg
import back.ir.ir
import back.opt.loops
import support.list
# mark: Recognizing a loop ====================================================================
struct Analysis:
var f: ir.Function*
var g: cfg.Graph*
var loop: loops.Natural*
var definitions: u32[]
var kinds: u8[]
var bases: ir.Ref[]
var streams: list.List[ir.Ref]
var header: cfg.Block
var body: cfg.Block
var counter: u32 = 0
var increment: u32 = 0
var accumulator: u32 = 0
var reduction: u32 = 0
var initial: ir.Ref
var bound: ir.Ref
var store_base: ir.Ref
var cls: ir.Class = ir.Class.l
var width: u32 = 0
var stride: u32 = 0
func invariant(value: ir.Ref) -> bool:
return loops.invariant(value, self.loop.members, self.definitions)
func kind(value: ir.Ref) -> u8:
return self.kinds[value.index] if value.kind == ir.RefKind.temp else 0
func definition(temp: u32) -> ir.Instr?:
let block = self.g.blocks.get(self.definitions[temp])
for i in block.start..<block.end:
let x = self.f.instrs.get(i)
if x.dst == temp:
return x
return none
## Each accepted phi has one entry and one backedge. Returning references
## separately keeps the original scalar recurrence available for the tail.
func incoming(phi: ir.Instr) -> (ir.Ref, ir.Ref)?:
if phi.extra2 != 2:
return none
var entry = ir.none_ref()
var back = ir.none_ref()
let label = self.g.blocks.get(self.loop.preheader).label
for k in 0..<phi.extra2:
let arg = self.f.phi_args.get(phi.extra + k)
if arg.pred == label:
entry = arg.value
elif arg.pred == self.body.label:
back = arg.value
if entry.kind == ir.RefKind.none_ or back.kind == ir.RefKind.none_:
return none
return (entry, back)
func recognize() -> bool!:
var count: u32 = 0
for member in self.loop.members:
if member:
count += 1
if count != 2 or self.header.end <= self.header.start:
return false
let branch = self.f.instrs.get(self.header.end - 1)
if branch.op != ir.Op.jnz or branch.a.kind != ir.RefKind.temp:
return false
let body_index = self.g.block_of(branch.extra)
if body_index == self.loop.header or not self.loop.members[body_index] or self.loop.members[self.g.block_of(branch.extra2)]:
return false
self.body = self.g.blocks.get(body_index)
if self.body.preds.count != 1 or self.body.end <= self.body.start:
return false
let tail = self.f.instrs.get(self.body.end - 1)
if tail.op != ir.Op.jmp or tail.extra != self.header.label:
return false
let comparison = self.definition(branch.a.index) else return false
if comparison.op != ir.Op.cult or comparison.cls != ir.Class.l or comparison.a.kind != ir.RefKind.temp or not self.invariant(comparison.b):
return false
self.counter = comparison.a.index
self.bound = comparison.b
let counter = self.definition(self.counter) else return false
if counter.op != ir.Op.phi or counter.cls != ir.Class.l:
return false
let (initial, step) = self.incoming(counter) else return false
if initial.kind != ir.RefKind.constant or initial.value != 0 or step.kind != ir.RefKind.temp:
return false
let increment = self.definition(step.index) else return false
if increment.op != ir.Op.add or increment.cls != ir.Class.l or not ((is_temp(increment.a, self.counter) and is_constant(increment.b, 1)) or (is_temp(increment.b, self.counter) and is_constant(increment.a, 1))):
return false
self.increment = step.index
for i in self.header.start..<self.header.end:
let x = self.f.instrs.get(i)
if x.dst == self.counter or x.dst == comparison.dst or x.op == ir.Op.jnz:
continue
if x.op != ir.Op.phi or self.accumulator != 0 or (x.cls != ir.Class.w and x.cls != ir.Class.l):
return false
let (seed, next) = self.incoming(x) else return false
if next.kind != ir.RefKind.temp:
return false
let reduction = self.definition(next.index) else return false
if reduction.op != ir.Op.add or reduction.cls != x.cls or (is_temp(reduction.a, x.dst) == is_temp(reduction.b, x.dst)):
return false
self.accumulator = x.dst
self.reduction = next.index
self.initial = seed
self.cls = x.cls
self.width = 8 if x.cls == ir.Class.l else 4
self.kinds[x.dst] = 3
for i in self.body.start..<self.body.end:
let x = self.f.instrs.get(i)
if x.dst == self.increment or x.op == ir.Op.jmp:
continue
if self.accumulator != 0 and x.dst != self.reduction and (is_temp(x.a, self.accumulator) or is_temp(x.b, self.accumulator)):
return false
if x.op == ir.Op.mul and x.cls == ir.Class.l:
let scale = x.b if is_temp(x.a, self.counter) else x.a
if (is_temp(x.a, self.counter) or is_temp(x.b, self.counter)) and scale.kind == ir.RefKind.constant and (scale.value == 4 or scale.value == 8):
if self.stride != 0 and self.stride != (u32)scale.value:
return false
self.stride = (u32)scale.value
self.kinds[x.dst] = 1
continue
if x.op == ir.Op.add and x.cls == ir.Class.l:
let base = x.b if self.kind(x.a) == 1 else x.a
if (self.kind(x.a) == 1 or self.kind(x.b) == 1) and self.invariant(base):
self.kinds[x.dst] = 2
self.bases[x.dst] = base
continue
if is_lane_load(x.op):
let width: u32 = 8 if x.op == ir.Op.loadl or x.op == ir.Op.loadd else 4
# a 32-bit integer lane is the word as loaded, signed or not, never widened
let widened = (x.op == ir.Op.loaduw or x.op == ir.Op.loadsw) and x.cls != ir.Class.w
if widened or self.kind(x.a) != 2 or (self.width != 0 and (self.width != width or self.cls != x.cls)):
return false
self.width = width
self.cls = x.cls
self.kinds[x.dst] = 3
try self.streams.push(self.bases[x.a.index])
continue
if x.op == ir.Op.storel or x.op == ir.Op.storew or x.op == ir.Op.stored or x.op == ir.Op.stores:
let store_class = ir.Class.d if x.op == ir.Op.stored else (ir.Class.s if x.op == ir.Op.stores else (ir.Class.w if x.op == ir.Op.storew else ir.Class.l))
if self.accumulator != 0 or self.store_base.kind != ir.RefKind.none_ or self.kind(x.a) != 3 or self.kind(x.b) != 2 or store_class != self.cls:
return false
self.store_base = self.bases[x.b.index]
continue
if vector_op(x.op, x.cls) == ir.Op.copy or x.cls != self.cls or not self.data(x.a) or not self.data(x.b) or (self.kind(x.a) != 3 and self.kind(x.b) != 3):
return false
self.kinds[x.dst] = 3
return self.streams.count > 0 and self.width == self.stride and (self.accumulator != 0 or self.store_base.kind != ir.RefKind.none_)
func data(value: ir.Ref) -> bool:
return self.kind(value) == 3 or (self.invariant(value) and (value.kind == ir.RefKind.constant or (value.kind == ir.RefKind.temp and self.f.temp_class(value.index) == self.cls)))
# mark: Building the vector loop ==============================================================
struct Builder:
var f: ir.Function*
var analysis: Analysis*
var pre: list.List[ir.Instr]
var body: list.List[ir.Instr]
var values: ir.Ref[]
var index: ir.Ref
var shape: u32
func value(original: ir.Ref) -> ir.Ref!:
if original.kind == ir.RefKind.temp and self.values[original.index].kind != ir.RefKind.none_:
return self.values[original.index]
let value = try result(self.f, &self.pre, ir.Op.vsplat, ir.Class.v, original, ir.none_ref(), self.shape)
if original.kind == ir.RefKind.temp:
self.values[original.index] = value
return value
func address(original: ir.Ref) -> ir.Ref!:
let base = self.analysis.bases[original.index]
let offset = try result(self.f, &self.body, ir.Op.mul, ir.Class.l, self.index, ir.const_ref((i64)self.analysis.width))
return try result(self.f, &self.body, ir.Op.add, ir.Class.l, base, offset)
func translate() -> !:
let block = self.analysis.body
for i in block.start..<block.end:
let x = self.f.instrs.get(i)
if x.dst == self.analysis.increment or x.op == ir.Op.jmp or (x.dst != 0 and self.analysis.kinds[x.dst] != 3):
continue
if is_lane_load(x.op):
let address = try self.address(x.a)
self.values[x.dst] = try result(self.f, &self.body, ir.Op.loadv, ir.Class.v, address, ir.none_ref(), self.shape)
elif x.dst == 0:
let value = try self.value(x.a)
let address = try self.address(x.b)
try self.body.push(instruction(ir.Op.storev, ir.Class.v, 0, value, address, self.shape))
else:
let a = try self.value(x.a)
let b = try self.value(x.b)
self.values[x.dst] = try result(self.f, &self.body, vector_op(x.op, x.cls), ir.Class.v, a, b, self.shape)
# mark: The pass ==============================================================================
## Version every counted loop of `f` that qualifies for 128-bit SIMD.
pub func run(f: ir.Function*) -> !:
# Newly made vector loops contain vector operations, so cannot match again.
# Remember original headers: their scalar tails must not be versioned again.
let original_labels = f.labels
var handled = try new bool[(usize)original_labels + 1] ---
defer free(handled)
for i in 0..<handled.length:
handled[i] = false
for round in 0..<16:
var g = try cfg.Graph.over(f)
defer g.release()
var transformed = false
for h in g.order.span():
let header = g.blocks.get(h)
if header.label > original_labels or handled[header.label]:
continue
handled[header.label] = true
if let found = try loops.Natural.find(&g, h):
var loop = found
defer loop.release()
var analysis = Analysis(f = f, g = &g, loop = &loop, definitions = try loops.definition_blocks(f, &g), kinds = try new u8[f.temps.count + 1] ---, bases = try new ir.Ref[f.temps.count + 1] ---, streams = try list.List[ir.Ref].create(4), header = header, body = header, initial = ir.none_ref(), bound = ir.none_ref(), store_base = ir.none_ref())
defer free(analysis.definitions)
defer free(analysis.kinds)
defer free(analysis.bases)
defer analysis.streams.destroy()
for i in 0..<analysis.kinds.length:
analysis.kinds[i] = 0
analysis.bases[i] = ir.none_ref()
if try analysis.recognize():
try rewrite(&analysis)
transformed = true
break
if not transformed:
return
## Versions the loop `a` recognised: a guard picks a vector loop of `16 / width` lanes,
## unrolled for an accumulator, then a reduction of its lanes, before the original scalar
## loop takes the rest from where the vector loop stopped.
func rewrite(a: Analysis*) -> !:
let f = a.f
let lanes = 16 // a.width
# Independent accumulators avoid serializing every vector load behind one
# add latency. Maps keep one vector per iteration to limit code growth.
let unroll: u32 = 4 if a.accumulator != 0 else 1
let step = lanes * unroll
let shape = ir.lanes(a.width * 8, lanes, ir.is_float_class(a.cls), false)
let guard_label = f.label()
let pre_label = f.label()
let head_label = f.label()
let body_label = f.label()
let finish_label = f.label()
let join_label = f.label()
let index = ir.temp_ref(try f.temp(ir.Class.l))
var accumulators = try new ir.Ref[unroll] ---
defer free(accumulators)
var backedges = try new ir.Ref[unroll] ---
defer free(backedges)
var builder = Builder(f = f, analysis = a, pre = try list.List[ir.Instr].create(8), body = try list.List[ir.Instr].create(32), values = try new ir.Ref[f.temps.count + 1] ---, index = index, shape = shape)
defer builder.pre.destroy()
defer builder.body.destroy()
defer free(builder.values)
try translate_groups(a, &builder, accumulators, backedges, lanes)
var code = try list.List[ir.Instr].create(64)
defer code.destroy()
try emit_label(&code, guard_label)
let end = try result(f, &code, ir.Op.and_, ir.Class.l, a.bound, ir.const_ref(0 - (i64)step))
let allowed = try guard_condition(a, &code, step)
try emit_branch(&code, allowed, pre_label, join_label)
try emit_label(&code, pre_label)
for x in builder.pre.span():
try code.push(x)
let zero = try result(f, &code, ir.Op.vsplat, ir.Class.v, ir.const_ref(0), ir.none_ref(), shape) if a.accumulator != 0 else ir.none_ref()
try emit_jump(&code, head_label)
try emit_label(&code, head_label)
let next_index = ir.temp_ref(try f.temp(ir.Class.l))
try emit_phi(f, &code, index, ir.Class.l, ir.const_ref(0), pre_label, next_index, body_label)
if a.accumulator != 0:
for group in 0..<unroll:
try emit_phi(f, &code, accumulators[group], ir.Class.v, zero, pre_label, backedges[group], body_label)
let more = try result(f, &code, ir.Op.cult, ir.Class.l, index, end)
try emit_branch(&code, more, body_label, finish_label)
try emit_label(&code, body_label)
for x in builder.body.span():
try code.push(x)
try code.push(instruction(ir.Op.add, ir.Class.l, next_index.index, index, ir.const_ref((i64)step)))
try emit_jump(&code, head_label)
try emit_label(&code, finish_label)
let reduced = try reduce(a, &code, accumulators, lanes, shape)
try emit_jump(&code, join_label)
try emit_label(&code, join_label)
let scalar_index = ir.temp_ref(try f.temp(ir.Class.l))
try emit_phi(f, &code, scalar_index, ir.Class.l, ir.const_ref(0), guard_label, end, finish_label)
var scalar_acc = ir.none_ref()
if a.accumulator != 0:
scalar_acc = ir.temp_ref(try f.temp(a.cls))
try emit_phi(f, &code, scalar_acc, a.cls, a.initial, guard_label, reduced, finish_label)
try emit_jump(&code, a.header.label)
resume_scalar(a, join_label, scalar_index, scalar_acc)
try splice(a, &code, guard_label)
## The vector loop's body into `builder`: one translation of the scalar body per unrolled
## group, each at its own index and, with an accumulator, its own vector of partial sums,
## whose value at the end of the body is that group's back edge.
func translate_groups(a: Analysis*, builder: Builder*, accumulators: ir.Ref[], backedges: ir.Ref[], lanes: u32) -> !:
let f = a.f
let index = builder.index
for i in 0..<builder.values.length:
builder.values[i] = ir.none_ref()
for group in 0..<(u32)accumulators.length:
accumulators[group] = ir.none_ref()
backedges[group] = ir.none_ref()
if group > 0:
builder.index = try result(f, &builder.body, ir.Op.add, ir.Class.l, index, ir.const_ref((i64)(group * lanes)))
if a.accumulator != 0:
accumulators[group] = ir.temp_ref(try f.temp(ir.Class.v))
builder.values[a.accumulator] = accumulators[group]
try builder.translate()
if a.accumulator != 0:
backedges[group] = builder.values[a.reduction]
## Whether the vector loop may run: at least one `step` of iterations, and, for a loop
## that stores, every stream it reads either the stored one or wholly apart from it.
func guard_condition(a: Analysis*, code: list.List[ir.Instr]*, step: u32) -> ir.Ref!:
let f = a.f
var allowed = try result(f, code, ir.Op.cuge, ir.Class.l, a.bound, ir.const_ref((i64)step))
if a.store_base.kind == ir.RefKind.none_:
return allowed
# Unsigned differences avoid pointer-end overflow. Bound the byte count
# before relying on it. Exact aliasing is safe for equal-stride streams;
# partial overlap executes the original scalar loop in its original order.
let fits = try result(f, code, ir.Op.cule, ir.Class.l, a.bound, ir.const_ref((i64)(18446744073709551615 // (u64)a.width)))
allowed = try result(f, code, ir.Op.and_, ir.Class.w, allowed, fits)
let bytes = try result(f, code, ir.Op.mul, ir.Class.l, a.bound, ir.const_ref((i64)a.width))
for source in a.streams.span():
if loops.same(source, a.store_base):
continue
let forward = try result(f, code, ir.Op.sub, ir.Class.l, source, a.store_base)
let backward = try result(f, code, ir.Op.sub, ir.Class.l, a.store_base, source)
let beyond_a = try result(f, code, ir.Op.cuge, ir.Class.l, forward, bytes)
let beyond_b = try result(f, code, ir.Op.cuge, ir.Class.l, backward, bytes)
let disjoint = try result(f, code, ir.Op.and_, ir.Class.w, beyond_a, beyond_b)
let equal = try result(f, code, ir.Op.ceq, ir.Class.l, source, a.store_base)
let independent = try result(f, code, ir.Op.or_, ir.Class.w, disjoint, equal)
allowed = try result(f, code, ir.Op.and_, ir.Class.w, allowed, independent)
return allowed
## The accumulator after the vector loop: its partial sums added lane-wise, stored, and
## each lane added to the initial value; the initial value when there is none.
func reduce(a: Analysis*, code: list.List[ir.Instr]*, accumulators: ir.Ref[], lanes: u32, shape: u32) -> ir.Ref!:
let f = a.f
var reduced = a.initial
if a.accumulator == 0:
return reduced
let slot = ir.slot_ref(try f.slot(16, 16))
var combined = accumulators[0]
for group in (u32)1..<(u32)accumulators.length:
combined = try result(f, code, ir.Op.vaddw, ir.Class.v, combined, accumulators[group], shape)
try code.push(instruction(ir.Op.storev, ir.Class.v, 0, combined, slot, shape))
for lane in 0..<lanes:
let address = try result(f, code, ir.Op.add, ir.Class.l, slot, ir.const_ref((i64)(lane * a.width)))
let value = try result(f, code, ir.Op.loadl if a.width == 8 else ir.Op.loaduw, a.cls, address, ir.none_ref())
reduced = try result(f, code, ir.Op.add, a.cls, reduced, value)
return reduced
## The scalar loop's header phis take their entry from `join_label` instead of the
## preheader: the counter where the vector loop stopped, the accumulator as reduced.
func resume_scalar(a: Analysis*, join_label: u32, scalar_index: ir.Ref, scalar_acc: ir.Ref):
let f = a.f
let old_label = a.g.blocks.get(a.loop.preheader).label
for i in a.header.start..<a.header.end:
let x = f.instrs.get(i)
if x.op != ir.Op.phi:
continue
for k in 0..<x.extra2:
var arg = f.phi_args.get(x.extra + k)
if arg.pred == old_label:
arg.pred = join_label
arg.value = scalar_index if x.dst == a.counter else scalar_acc
f.phi_args.set(x.extra + k, arg)
## `code` into the function at the end of the loop's preheader, entered by a jump to
## `guard_label` that replaces the preheader's own jump to the header.
func splice(a: Analysis*, code: list.List[ir.Instr]*, guard_label: u32) -> !:
let f = a.f
let preheader = a.g.blocks.get(a.loop.preheader)
let replaces_jump = preheader.end > preheader.start and f.instrs.get(preheader.end - 1).op == ir.Op.jmp
let insertion = preheader.end - 1 if replaces_jump else preheader.end
var out = try list.List[ir.Instr].create(f.instrs.count + code.count)
for i in 0..=f.instrs.count:
if i == insertion:
try emit_jump(&out, guard_label)
for x in code.span():
try out.push(x)
if i < f.instrs.count and (i != insertion or not replaces_jump):
try out.push(f.instrs.get(i))
f.instrs.destroy()
f.instrs = out
func instruction(op: ir.Op, cls: ir.Class, dst: u32, a: ir.Ref, b: ir.Ref, extra: u32 = 0, extra2: u32 = 0) -> ir.Instr:
return ir.Instr(op = op, cls = cls, dst = dst, a = a, b = b, extra = extra, extra2 = extra2, line = 0, file = 0, scope = 0, site = 0)
func result(f: ir.Function*, out: list.List[ir.Instr]*, op: ir.Op, cls: ir.Class, a: ir.Ref, b: ir.Ref, shape: u32 = 0) -> ir.Ref!:
let temp = try f.temp(ir.Class.w if ir.is_comparison(op) else cls)
try out.push(instruction(op, cls, temp, a, b, shape))
return ir.temp_ref(temp)
func emit_label(out: list.List[ir.Instr]*, label: u32) -> !:
try out.push(instruction(ir.Op.label, ir.Class.l, 0, ir.none_ref(), ir.none_ref(), label))
func emit_jump(out: list.List[ir.Instr]*, label: u32) -> !:
try out.push(instruction(ir.Op.jmp, ir.Class.l, 0, ir.none_ref(), ir.none_ref(), label))
func emit_branch(out: list.List[ir.Instr]*, condition: ir.Ref, yes: u32, no: u32) -> !:
try out.push(instruction(ir.Op.jnz, ir.Class.w, 0, condition, ir.none_ref(), yes, no))
func emit_phi(f: ir.Function*, out: list.List[ir.Instr]*, dst: ir.Ref, cls: ir.Class, first: ir.Ref, first_label: u32, second: ir.Ref, second_label: u32) -> !:
let start = (u32)f.phi_args.count
try f.phi_args.push(ir.PhiArg(value = first, pred = first_label))
try f.phi_args.push(ir.PhiArg(value = second, pred = second_label))
try out.push(instruction(ir.Op.phi, cls, dst.index, ir.none_ref(), ir.none_ref(), start, 2))
## Whether `op` loads one whole lane: 32 or 64 bits, integer or float.
func is_lane_load(op: ir.Op) -> bool:
return op == ir.Op.loadl or op == ir.Op.loaduw or op == ir.Op.loadsw or op == ir.Op.loadd or op == ir.Op.loads
func is_temp(value: ir.Ref, index: u32) -> bool:
return value.kind == ir.RefKind.temp and value.index == index
func is_constant(value: ir.Ref, number: i64) -> bool:
return value.kind == ir.RefKind.constant and value.value == number
func vector_op(op: ir.Op, cls: ir.Class) -> ir.Op:
if cls == ir.Class.s or cls == ir.Class.d:
match op:
.add: return ir.Op.vadd
.sub: return ir.Op.vsub
.mul: return ir.Op.vmul
_: return ir.Op.copy
if cls == ir.Class.w or cls == ir.Class.l:
match op:
.add: return ir.Op.vaddw
.sub: return ir.Op.vsubw
.and_: return ir.Op.vand
.or_: return ir.Op.vor
.xor: return ir.Op.vxor
_: return ir.Op.copy
return ir.Op.copy