Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.42.0

0.42.0 / src / back / ir / lower / reach.lucb

#==============================================================================================
#
#   lower/reach - The functions the program reaches, lowered on demand
#
#   DESCRIPTION:
#       Every function of every module is registered as an instance, but only those the
#       program can reach are lowered: the program's own (its package's), what is exported
#       or kept by an attribute, what assembly names, and then whatever a lowered body names.
#       A program importing a large package uses a small part of it; lowering the rest only
#       for the inliner's pruner (`inline.drop_unused_standard`) to drop it cost most of a
#       build's time. The roots and the edges are the pruner's: a function's instructions
#       and arguments naming a function, a witness table or a global, and a standard
#       global's initialiser counting once its global is named. The order is the order of
#       discovery, the same in every build of the same program.
#
#==============================================================================================
extend Lowerer:
    # mark: Reachable functions =================================================================

    ## Lower every function the program reaches, until none is left to lower.
    func lower_reached() -> !:
        while true:
            try self.name_instances()
            try self.scan_functions()
            if self.reach_next >= self.reach_queue.count:
                return
            let index = self.reach_queue.get(self.reach_next)
            self.reach_next += 1
            var inst = self.funcs.items.get(index)
            if inst.done:
                continue
            inst.done = true
            self.funcs.items.set(index, inst)
            try self.function(inst)
            if names.export_wrapped(&self.c.table, inst.decl):
                try self.export_wrapper(inst)

    ## Name the instances registered since the last call, and queue those that are roots.
    func name_instances() -> !:
        while self.reach_named < self.funcs.items.count:
            let index = self.reach_named
            self.reach_named += 1
            let inst = self.funcs.items.get(index)
            let name = try self.function_name(inst.decl, inst.args, inst.owner, inst.owner_args)
            try self.reach_names.push(name)
            _ = try self.reach_by_name.add(name, index)
            if try self.is_root(inst, name):
                try self.want(index)

    ## Whether instance `inst`, named `name`, is lowered whether or not anything names it: the
    ## program's own functions and those the pruner keeps for their linkage.
    func is_root(inst: instances.Instance, name: str) -> bool!:
        let d = inst.decl
        if ast.is_linked(d):
            return false
        if not check.is_library_module(names.module_of(inst.owner else d)):
            return true
        if d.has(ast.flag_export) or ast.has_attribute(d, "used") or ast.has_attribute(d, "weak") or ast.has_attribute(d, "naked") or section_of(d).length > 0:
            return true
        if name == self.program_unit.trap_function or name == self.program_unit.trap_at_function or name == self.program_unit.trap_two_at_function:
            return true
        for text in self.reach_asm.span():
            if contains_name(text, name):
                return true
        return false

    ## Queue instance `index` for lowering, once.
    func want(index: usize) -> !:
        if self.reach_wanted.count <= index:
            while self.reach_wanted.count <= index:
                try self.reach_wanted.push(false)
        if self.reach_wanted.get(index):
            return
        self.reach_wanted.set(index, true)
        try self.reach_queue.push(index)

    ## Follow the references of every function lowered since the last call, except the
    ## standard globals' initialisers, which count only once their global is named.
    func scan_functions() -> !:
        while self.reach_scanned < self.program_unit.functions.count:
            let fi = self.reach_scanned
            self.reach_scanned += 1
            let name = self.program_unit.functions.items[fi].name
            if self.reach_initialisers.has(name):
                continue
            try self.scan_function(fi)

    ## Follow the references of function `fi` of the unit.
    func scan_function(fi: usize) -> !:
        var k: usize = 0
        while k < self.program_unit.functions.items[fi].instrs.count:
            let instruction = self.program_unit.functions.items[fi].instrs.get(k)
            k += 1
            try self.follow(instruction.a)
            try self.follow(instruction.b)
            if instruction.op == ir.Op.asm_ and instruction.b.kind == ir.RefKind.text:
                try self.note_asm(self.program_unit.texts.get((usize)instruction.b.index).bytes)
        k = 0
        while k < self.program_unit.functions.items[fi].args.count:
            try self.follow(self.program_unit.functions.items[fi].args.get(k).value)
            k += 1

    ## What reference `r` reaches: a function instance, a witness table's methods, or a
    ## standard global's initialiser.
    func follow(r: ir.Ref) -> !:
        if r.kind == ir.RefKind.function:
            if let index = self.reach_by_name.find(r.name):
                try self.want(index)
            return
        if r.kind != ir.RefKind.global:
            return
        try self.reach_table(r.name)
        try self.reach_initialiser(r.name)

    ## The methods of the witness table named `name`, when it is one.
    func reach_table(name: str) -> !:
        try self.name_tables()
        let ti = self.reach_tables.find(name) else return
        if self.reach_tables_done.get(ti):
            return
        self.reach_tables_done.set(ti, true)
        let w = self.vtables.get(ti)
        let d = self.decl_of(w.record) else return
        let iface = self.decl_of(w.iface) else return
        let t = self.c.table.get(w.record)
        for m in (try instances.witnessed(d, iface)).span():
            let index = try self.add_func(m, try types.no_args(), d, t.args)
            try self.name_instances()
            try self.want(index)

    ## Name the witness tables noted since the last call.
    func name_tables() -> !:
        while self.reach_tables_done.count < self.vtables.count:
            let ti = self.reach_tables_done.count
            let w = self.vtables.get(ti)
            try self.reach_tables_done.push(false)
            let iface = self.decl_of(w.iface) else continue
            let name = try self.vtable_name(w.record, iface)
            _ = try self.reach_tables.add(name, ti)
            for text in self.reach_asm.span():
                if contains_name(text, name):
                    try self.reach_table(name)
                    break

    ## The initialiser of the standard global `name`, once: its body counts from now on.
    func reach_initialiser(global: str) -> !:
        let fi = self.reach_global_inits.find(global) else return
        let name = self.program_unit.functions.items[fi].name
        if not self.reach_initialisers.has(name):
            return
        # scanned once: the name stays, marking it done, under a key no function has
        if self.reach_inits_done.has(name):
            return
        _ = try self.reach_inits_done.add(name, fi)
        try self.scan_function(fi)

    ## The standard globals' initialisers `globals_initialiser` made, by their global's name.
    func note_initialisers() -> !:
        for g in 0..<self.program_unit.globals.count:
            let global = self.program_unit.globals.get(g)
            if global.init_function.length == 0:
                continue
            for fi in 0..<self.program_unit.functions.count:
                if self.program_unit.functions.items[fi].name == global.init_function:
                    _ = try self.reach_initialisers.add(global.init_function, fi)
                    _ = try self.reach_global_inits.add(global.name, fi)
                    break

    ## Assembly text `text` of a lowered function: the functions and tables it spells are
    ## reached.
    func note_asm(text: str) -> !:
        try self.reach_asm.push(text)
        for index in 0..<self.reach_names.count:
            if contains_name(text, self.reach_names.get(index)):
                try self.want(index)
        try self.name_tables()
        for ti in 0..<self.vtables.count:
            let w = self.vtables.get(ti)
            let iface = self.decl_of(w.iface) else continue
            let name = try self.vtable_name(w.record, iface)
            if contains_name(text, name):
                try self.reach_table(name)

    ## The package declaration `d` belongs to, by its module (`check.Module.package_name`),
    ## `(standard)` for a standard module's; empty when no module is known.
    func package_of(d: ast.Node*) -> str!:
        let m = d.resolved else return ""
        if self.module_packages.count() == 0:
            for k in 0..<self.c.modules.count:
                _ = try self.module_packages.add(self.c.modules.get(k).tree.text, k)
        let k = self.module_packages.find(m.text) else return ""
        let package = self.c.modules.get(k).package_name
        return package if package.length > 0 else "(standard)"

## Whether `text` spells `name` anywhere, as the pruner asks of assembly
## (`inline.named_in_asm`).
func contains_name(text: str, name: str) -> bool:
    return name.length > 0 and strings.find(text, name) != none