dymokomi/luce-base
Source of release 0.43.0
0.43.0 / src / back / backend.lucb
#==============================================================================================
#
# backend - The interface every code generator implements
#
# DESCRIPTION:
# The pipeline is checked tree (the high-level form the checker leaves, with a type and
# a resolution on every node) to a target. A `Backend` is the last stage: it takes the
# checked program and yields the text its host tool consumes. Two implement it today:
# `CBackend` streams C for the host C compiler; `NativeBackend` lowers the tree to the
# machine-neutral IR of `ir` (the middle form, in the spirit of QBE) and turns that into
# the target's assembly, arm64 (Mach-O) or x86_64 (ELF). A third target adds a
# generator and a line here and changes nothing else: the driver holds a `Backend`
# view and never names a generator.
#
#==============================================================================================
import c
import io
import memory
import platform
import back.native.dwarf
import back.native.arm64
import back.ir.cfg
import back.opt.addresses
import back.opt.ifconvert
import back.opt.dessa
import back.opt.gvn
import back.opt.load
import back.opt.loops
import back.opt.ranges
import back.opt.slp
import back.opt.split
import back.opt.ssa
import back.opt.vectorize
import back.target as targets
import back.native.x86_64
import back.c.emit
import back.opt.inline
import back.parallel
import back.ir.ir
import back.ir.irtext
import back.ir.digest
import back.reuse
import back.native.stable_names
import back.ir.lower
import back.opt.opt
import front.ast
import sema.check
## What a build takes from the last one (`NativeBackend.take_reused`): each function's key,
## the text taken for it and its generator's flags (empty where it is generated), and
## which functions are generated.
struct Taken:
var keys: digest.Digest[]
var texts: str[]
var flags: u8[]
var generated: bool[]
## A build took a function's text from the last one, but its labels were named otherwise
## this time (`NativeBackend.keep_texts`): the driver translates again without reuse.
pub let stale: ErrorCode = ErrorCode.package(57)
# mark: Backends ==============================================================================
## The last stage of the pipeline: the checked program as the target's text.
pub interface Backend:
## `mode` is 0 for a `main` program, 1 for the test runner, 2 for an `answer()` program,
## 3 for a library, which has no entry and initialises itself when loaded (§17.6), 4 for
## a freestanding program, whose own `_start` is the entry (§19.4), 5 for one member of
## the standard library's archive: its own module's bodies and `lb_<module>_0init`.
func compile(mode: u32) -> str!
## C for the host C compiler.
pub struct CBackend: Backend:
var emitter: emit.Emitter
## A C backend that emits `entry`, checked by `checker`.
## Positions name a source under `position_root` relative to it, as a native build's do.
pub static func over(checker: check.Checker*, entry: ast.Node*, diagnostic: bool, position_root: str = "") -> CBackend!:
var emitter = try emit.Emitter.create(checker, entry)
emitter.diagnostic = diagnostic
emitter.position_root = position_root
return CBackend(emitter = emitter)
## Emit the whole program as C and return its text.
pub func compile(mode: u32) -> str!:
try self.emitter.program(mode)
return self.emitter.text()
## arm64 assembly through the IR: lower the tree, then generate.
pub struct NativeBackend: Backend:
var checker: check.Checker*
var lowerer: lower.Lowerer
var debug: bool
## `--emit=ir`: the IR as text after every pass before the target, instead of assembly.
pub var dump_ir: bool
## How far the optimiser goes, and on how many functions (`--opt`, `--opt-count`).
pub var opt_level: u32
## How many functions the optimiser processes; all of them when `0xFFFFFFFF`.
pub var opt_count: u32
## `--opt-report`: the time each stage took, on standard error.
pub var report: bool
## The target of the build (§19.5); every target has a generator.
var target: targets.Target
## Whether the driver will assemble the text in pieces (`support.pieces`): the
## generator then names the labels functions share as hidden symbols.
pub var split: bool = false
## Whether the build is a program, not a library (`Generator.program`).
pub var program: bool = false
## Labels and literals named by what they label without splitting (`Generator.stable`):
## what `reuse` needs on a target whose assembly is one file.
pub var stable: bool = false
## After `compile`: where each function's text begins, then where the rest begins.
pub var starts: usize[]
## After `compile` with `split`: each function's tag (`stable_names`), which places the
## cuts between pieces.
pub var tags: u64[]
## After `compile`: where the format's closing directives begin.
pub var ending: usize = 0
## After `compile`: whether the program has module-level assembly (§8.9), whose labels
## its functions may name as labels local to the one file.
pub var module_asm: bool = false
## With `split` or `stable`, a build that may take its functions' texts from the last
## build of the program (`reuse`): the digest of its settings.
pub var reuse_settings: digest.Digest? = none
## The name the program's texts are kept under (`reuse.pack_name`).
pub var reuse_name: str = ""
## After `compile`: how many functions were taken from the last build.
pub var reused_count: usize = 0
## A native backend that lowers `entry` to IR and generates the target's assembly.
## Positions name a source under `position_root` relative to it (`lower.Lowerer`).
pub static func over(checker: check.Checker*, entry: ast.Node*, debug: bool, diagnostic: bool, symbols: bool = false, position_root: str = "") -> NativeBackend!:
var lowerer = try lower.Lowerer.create(checker, entry)
lowerer.diagnostic = diagnostic
lowerer.symbols = symbols
lowerer.position_root = position_root
return NativeBackend(checker = checker, lowerer = lowerer, debug = debug, dump_ir = false, opt_level = 3, opt_count = 0xFFFFFFFF, report = false, target = checker.build_target)
## Lower, optimise, and generate the target's assembly, or the IR text with `dump_ir`.
pub func compile(mode: u32) -> str!:
let t = self.target
self.lowerer.debug = self.debug
self.lowerer.target = t
timing = self.report
parallel.serial = self.report
var at = ticks()
# the IR's lists grow by copying: from the heap their old storage goes back to it,
# where the driver's arena would keep every outgrown copy until the build ends
with memory.heap:
try self.lowerer.program(mode)
try note(&at, 0)
# what the last build generated of each function as it stands now, taken again
# (`reuse`): empty where the function is generated
var taken: Taken
# the expansions, the optimiser and the tidying rebuild each function's lists: from the
# heap, the copies they replace go back to it, where the driver's arena would keep
# them all until the build ends
with memory.heap:
try inline.expand(&self.lowerer.program_unit)
try note(&at, 1)
# the functions the last build generated as they stand now are taken again; the
# rest, and what they call, are optimised (`reuse`)
taken = try self.take_reused()
let n = self.lowerer.program_unit.functions.count
let generated = taken.generated
let optimised = try self.lowerer.program_unit.called_by(generated)
try optimise_functions(&self.lowerer.program_unit, self.opt_level, self.opt_count, optimised, t.arch)
# small leaf functions measured as optimised, expanded where they are called; the
# callers that gained bodies are optimised again and tidied
if not self.debug and self.opt_level >= 2 and self.opt_count == 0xFFFFFFFF:
let changed = try inline.expand_small(&self.lowerer.program_unit, optimised_small)
defer free(changed)
for i in 0..<n:
changed[i] = changed[i] and generated[i]
try optimise_functions(&self.lowerer.program_unit, self.opt_level, self.opt_count, changed, t.arch)
# every function tidied, not only those this pass changed: the first pass's
# expansions leave parameter stores and unreached blocks behind as well
try each_function(&self.lowerer.program_unit, tidy_task, generated)
if not self.debug:
if self.opt_level >= 2 and self.opt_count == 0xFFFFFFFF:
try each_function(&self.lowerer.program_unit, clean_task, generated)
else:
try each_function(&self.lowerer.program_unit, sweep_task, generated)
try note(&at, 7)
self.module_asm = self.lowerer.program_unit.module_asm.count > 0
if self.dump_ir:
return try irtext.render(&self.lowerer.program_unit)
# each function's allocation and frame working memory goes back to the heap once
# the function is written
var text = ""
with memory.heap:
var dw = try dwarf.Emitter.over(self.checker, &self.lowerer.program_unit, t.os, t.arch)
if t.arch == targets.Arch.x86_64:
var generator = try x86_64.Generator.create(&self.lowerer.program_unit, t.os, t.symbol_prefix)
if self.debug or self.lowerer.symbols:
generator.dw = &dw
generator.level = t.level
generator.split = self.split
generator.stable = self.stable
generator.program = self.program
generator.reused = taken.texts
generator.reused_flags = taken.flags
try generator.generate()
text = generator.text()
self.starts = generator.starts
self.ending = generator.ending
self.tags = generator.function_tags
try self.keep_texts(taken.keys, text, generator.function_flags, generator.function_tags, generator.text_tags)
else:
var generator = try arm64.Generator.create(&self.lowerer.program_unit, t.os, t.symbol_prefix)
if self.debug or self.lowerer.symbols:
generator.dw = &dw
generator.split = self.split
generator.stable = self.stable
generator.reused = taken.texts
generator.reused_flags = taken.flags
try generator.generate()
text = generator.text()
self.starts = generator.starts
self.ending = generator.ending
self.tags = generator.function_tags
try self.keep_texts(taken.keys, text, generator.function_flags, generator.function_tags, generator.text_tags)
try note(&at, 8)
if self.report:
try print_report()
return text
## The texts of the last build taken for the functions that stand as they did, by
## their keys (`reuse_keys`, none when this build reuses nothing).
func take_reused() -> Taken!:
let keys = try self.reuse_keys()
let n = self.lowerer.program_unit.functions.count
var kept = try reuse.Kept.load(self.reuse_name, keys.length > 0)
var taken = Taken(keys = keys, texts = try new str[keys.length] ---, flags = try new u8[keys.length] ---, generated = try new bool[n] ---)
for i in 0..<n:
taken.generated[i] = true
for i in 0..<keys.length:
taken.texts[i] = ""
taken.flags[i] = 0
if let entry = kept.find(keys[i]):
taken.texts[i] = entry.text
taken.flags[i] = entry.flags
taken.generated[i] = false
self.reused_count += 1
return taken
## Each function's key (`reuse.keys`) when this build may reuse the last one's texts:
## with labels named by what they label (`split` or `stable`), at the default
## optimisation, and with no debugging information; none otherwise.
func reuse_keys() -> digest.Digest[]!:
let settings = self.reuse_settings else return try new digest.Digest[0] ---
if not (self.split or self.stable) or self.debug or self.lowerer.symbols or self.dump_ir or self.report or self.opt_level != 3 or self.opt_count != 0xFFFFFFFF:
return try new digest.Digest[0] ---
return try reuse.keys(&self.lowerer.program_unit, settings)
## Keep this build's function texts for the next (`reuse.store`). A text taken from the
## last build was generated with every label named by its first tag (`stable_names`):
## when a clash between names gave one a later tag, the build is made again without
## reuse (`stale`), and its texts are not kept.
func keep_texts(keys: const digest.Digest[], text: str, flags: const u8[], function_tags: const u64[], text_tags: const u64[]) -> !:
if keys.length == 0:
return
if not stable_names.first_tags(&self.lowerer.program_unit, function_tags, text_tags):
if self.reused_count > 0:
error(stale, "a function's labels clashed with another's; the build is made again")
return
reuse.store(self.reuse_name, keys, text, self.starts, flags)
# mark: Optimisation pipeline =================================================================
## Time per stage, in microseconds: processor time from the C library's clock, which on
## Windows is the time since the process started, in milliseconds. Lower, inline, promote,
## ssa, gvn, load, dessa, the sweep, generate.
var stage_ticks: u64[9] = [0, 0, 0, 0, 0, 0, 0, 0, 0]
## Whether this build keeps stage times (`--opt-report`).
var timing: bool = false
let stage_names: str[9] = ["lower", "inline", "promote", "ssa", "gvn", "load", "dessa", "opt", "generate"]
extern func c_clock as "clock"() -> c.long
func ticks() -> u64:
let clock = (u64)(i64)c_clock()
return clock * 1000 if platform.windows else clock
## Stage times, kept only for `--opt-report`, which runs every stage on one thread.
func note(at: u64*, stage: usize) -> !:
if not timing:
return
let now = ticks()
stage_ticks[stage] += now -% *at
*at = now
func print_report() -> !:
let err = io.stderr()
var k: usize = 0
while k < stage_names.length:
try err.write(f"{stage_names[k]}: {stage_ticks[k] // 1000} ms\n")
k += 1
## The optimiser over the IR, function by function: slots into temporaries, the function
## into single-assignment form, the passes, then the phis back into copies for the
## generator. A naked function is its assembly; a function under `--debug` keeps its
## locals in their slots, where the frame descriptor says they are.
## The most instructions an optimised leaf function may have to be expanded at every
## call by the second inlining pass (`inline.expand_small`): js_dup_value and its kin in
## luce-js optimise to 25 to 30.
let optimised_small: usize = 48
## Optimise every function of `program` (the first `count`), or only those `only` marks,
## each on whichever thread takes it (back.parallel), for a target of `arch`: a function's
## passes read and write that function alone. A failure is reported for the first function
## that failed.
func optimise_functions(program: ir.Unit*, level: u32, count: u32, only: bool[]?, arch: targets.Arch) -> !:
let n = program.functions.count if program.functions.count < (usize)count else (usize)count
with memory.heap:
var job = Optimising(program = program, level = level, arch = arch, only = only, failures = try parallel.failures(n))
defer free(job.failures)
let order = try program.largest_first(n)
defer free(order)
try parallel.each_ordered(n, optimise_task, (void*)&job, order)
try parallel.check(job.failures)
## Run `task` over the functions of `program` that `only` marks, each on whichever thread
## takes it; the first function's failure, if any failed, is the call's.
func each_function(program: ir.Unit*, task: func(ir.Function*) -> unit!, only: const bool[]) -> !:
let n = program.functions.count
with memory.heap:
var job = PerFunction(program = program, task = task, only = only, failures = try parallel.failures(n))
defer free(job.failures)
let order = try program.largest_first(n)
defer free(order)
try parallel.each_ordered(n, per_function_task, (void*)&job, order)
try parallel.check(job.failures)
## What the threads running one task over a program's functions share.
struct PerFunction:
var program: ir.Unit*
var task: func(ir.Function*) -> unit!
## Which functions the task runs over.
var only: const bool[]
var failures: parallel.Failure[]
func per_function_task(context: void*?, index: usize):
let job = (PerFunction*)(context else return)
if not job.only[index]:
return
with memory.heap:
job.task(&job.program.functions.items[index]) catch failure:
job.failures[index] = parallel.failed(failure.code, failure.message)
## After the second inlining pass: every function tidied, not only those it changed.
func tidy_task(f: ir.Function*) -> !:
if not f.naked and not f.debug and f.instrs.count > 0:
try inline.tidy_expanded(f)
func clean_task(f: ir.Function*) -> !:
try opt.clean_function(f)
func sweep_task(f: ir.Function*) -> !:
try opt.function(f)
## What the threads optimising a program share: the program, the level, which functions,
## and each function's failure, if it had one.
struct Optimising:
var program: ir.Unit*
var level: u32
var arch: targets.Arch
var only: bool[]?
var failures: parallel.Failure[]
## Optimise function `index` of the job `context` points at.
func optimise_task(context: void*?, index: usize):
let job = (Optimising*)(context else return)
if let marked = job.only:
if index >= marked.length or not marked[index]:
return
optimise_function(&job.program.functions.items[index], job.level, job.arch) catch failure:
job.failures[index] = parallel.failed(failure.code, failure.message)
## The optimiser's passes over `f` at `level`, for a target of `arch`.
func optimise_function(f: ir.Function*, level: u32, arch: targets.Arch) -> !:
if f.naked or f.debug or f.instrs.count == 0 or level == 0:
return
with memory.heap:
var at = ticks()
var g = try cfg.Graph.over(f)
if try ssa.promote(f):
g.release()
g = try cfg.Graph.over(f)
# small aggregates whose address stays in the frame, taken apart into their
# fields once promote has made the addresses an expansion passed through its
# parameters' slots plain temporaries; promote then keeps each field in one
if level >= 2 and try split.run(f):
_ = try ssa.promote(f)
g.release()
g = try cfg.Graph.over(f)
try note(&at, 2)
var g2 = try ssa.construct(f, &g)
g.release()
try note(&at, 3)
if level < 2:
try dessa.run(f, &g2)
g2.release()
try note(&at, 6)
return
var g3 = try gvn.run(f, &g2)
g2.release()
try note(&at, 4)
# a call through a known function's address calls it, for the inliner to expand
_ = try opt.direct_calls(f)
if level >= 3 and try load.run(f, &g3):
# loads became copies, and phis joined some blocks: number again
g3.release()
g3 = try cfg.Graph.over(f)
try note(&at, 5)
var g4 = try gvn.run(f, &g3)
g3.release()
g3 = g4
try note(&at, 4)
try note(&at, 5)
if level >= 3 and try loops.simplify_phis(f, &g3):
var simplified = try gvn.run(f, &g3)
g3.release()
g3 = simplified
if try ranges.run(f, &g3):
g3.release()
g3 = try cfg.Graph.over(f)
var simplified = try gvn.run(f, &g3)
g3.release()
g3 = simplified
# branches that only choose a value become selects
if try ifconvert.run(f):
g3.release()
g3 = try cfg.Graph.over(f)
# neighbouring elements' accesses add constants to one address
_ = try addresses.run(f)
if level >= 3:
g3.release()
_ = try loops.straighten(f)
try loops.run(f)
try vectorize.run(f)
# paired float arithmetic within a block, as vector operations where it pays
_ = try slp.run(f, arch)
g3 = try cfg.Graph.over(f)
try dessa.run(f, &g3)
g3.release()
try note(&at, 6)