Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.45.0

0.45.0 / src / back / ir / lower / memory.lucb

#==============================================================================================
#
#   lower/memory - Memory
#
#   DESCRIPTION:
#       Allocation, `free`, and the `memory` module (§12).
#
#==============================================================================================
extend Lowerer:
    # mark: Memory =============================================================================

    func allocator_of(e: ast.Node*?) -> ir.Ref!:
        let a = e else return try self.allocator_global()
        return try self.allocator_view(a)

    ## The address of a two-word `Allocator` view for `in x` and `with x`.
    func allocator_view(e: ast.Node*) -> ir.Ref!:
        let t = try self.ty(e)
        if self.is_iface(t):
            let v = try self.expr(e)
            return v.ref
        let iface = self.c.allocator_type()
        if self.is_ptr(t):
            let p = try self.expr(e)
            let view = try self.iface_view(p.ref, self.elem(t), iface)
            return view.ref
        let address = try self.place(e)
        let view = try self.iface_view(address, t, iface)
        return view.ref

    ## `view.allocate(size, alignment)`: the optional span answered, in memory; under the
    ## diagnostic profile the block is also recorded with the function and line asking (§19.4).
    func allocate_bytes(view: ir.Ref, size: ir.Ref, alignment: ir.Ref) -> ir.Ref!:
        let block = try self.allocate_bytes_raw(view, size, alignment)
        if self.diagnostic:
            let data = try self.f.load(ir.Op.loadl, ir.Class.l, block)
            let text = try self.program_unit.text(self.f.name)
            let name = try self.f.address_of(ir.text_ref(text))
            let function = try self.span_of(name, ir.const_ref((i64)self.f.name.length), types.str_id)
            let start = u32(self.f.args.count)
            try self.f.args.push(ir.Arg(value = data, cls = ir.Class.l, size = 0, align = 8, type_id = types.usize_id, shape = 0))
            try self.f.args.push(ir.Arg(value = size, cls = ir.Class.l, size = 0, align = 8, type_id = types.usize_id, shape = 0))
            try self.f.args.push(ir.Arg(value = function.ref, cls = ir.Class.l, size = 16, align = 8, type_id = types.str_id, shape = try self.shape_of(types.str_id)))
            try self.f.args.push(ir.Arg(value = ir.const_ref((i64)self.site_line), cls = ir.Class.w, size = 0, align = 4, type_id = types.u32_id, shape = 0))
            _ = try self.call_named("lb_memory_9note_site", start, 4, ir.Class.w, false, types.unit_id)
        return block

    func allocate_bytes_raw(view: ir.Ref, size: ir.Ref, alignment: ir.Ref) -> ir.Ref!:
        let data = try self.f.load(ir.Op.loadl, ir.Class.l, view)
        let table = try self.f.load(ir.Op.loadl, ir.Class.l, try self.offset_address(view, 8))
        let ok = self.f.label()
        let bad = self.f.label()
        try self.f.branch(table, ok, bad)
        try self.f.place_label(bad)
        try self.trap_with("memory.unset")
        try self.f.place_label(ok)
        let target = try self.f.load(ir.Op.loadl, ir.Class.l, table)
        let start = u32(self.f.args.count)
        try self.f.args.push(ir.Arg(value = data, cls = ir.Class.l, size = 0, align = 8, type_id = types.usize_id, shape = 0))
        try self.f.args.push(ir.Arg(value = size, cls = ir.Class.l, size = 0, align = 8, type_id = types.usize_id, shape = 0))
        try self.f.args.push(ir.Arg(value = alignment, cls = ir.Class.l, size = 0, align = 8, type_id = types.usize_id, shape = 0))
        let block_type = try self.c.table.optional(try self.c.table.span(types.u8_id, false))
        let slot = try self.new_slot(block_type)
        let info = ir.CallInfo(args_start = start, args_count = 3, fixed_count = 3, variadic = false, result_cls = ir.Class.l, has_result = true, result_size = self.size(block_type), result_align = 8, result_type = block_type, result_slot = slot, result_shape = try self.shape_of(block_type))
        try self.f.calls.push(info)
        try self.f.emit(ir.Op.call, ir.Class.l, 0, target, ir.none_ref(), u32(self.f.calls.count - 1))
        return try self.slot_address(slot)

    func allocator_release(view: ir.Ref, block: ir.Ref) -> !:
        let data = try self.f.load(ir.Op.loadl, ir.Class.l, view)
        let table = try self.f.load(ir.Op.loadl, ir.Class.l, try self.offset_address(view, 8))
        let skip = self.f.label()
        let go = self.f.label()
        try self.f.branch(table, go, skip)
        try self.f.place_label(go)
        let target = try self.f.load(ir.Op.loadl, ir.Class.l, try self.offset_address(table, 16))
        let start = u32(self.f.args.count)
        try self.f.args.push(ir.Arg(value = data, cls = ir.Class.l, size = 0, align = 8, type_id = types.usize_id, shape = 0))
        let bytes_type = try self.c.table.span(types.u8_id, false)
        try self.f.args.push(ir.Arg(value = block, cls = ir.Class.l, size = 16, align = 8, type_id = bytes_type, shape = try self.shape_of(bytes_type)))
        let info = ir.CallInfo(args_start = start, args_count = 2, fixed_count = 2, variadic = false, result_cls = ir.Class.w, has_result = false, result_size = 0, result_align = 8, result_type = types.unit_id, result_slot = 0, result_shape = 0)
        try self.f.calls.push(info)
        try self.f.emit(ir.Op.call, ir.Class.w, 0, target, ir.none_ref(), u32(self.f.calls.count - 1))
        try self.f.jump(skip)
        try self.f.place_label(skip)

    ## `count` elements of `elem` from `view`, into a result of `result_type` (a span!),
    ## zeroed when asked, else left unwritten, which the diagnostic profile fills with its
    ## pattern (§19.4); the result's address.
    func counted_allocation(view: ir.Ref, elem: u32, count: ir.Ref, result_type: u32, zero: bool) -> ir.Ref!:
        let slot = try self.new_slot(result_type)
        let a = try self.slot_address(slot)
        let stride = self.c.table.size_of(elem)
        # Compare elements before multiplying: a wrapped product can appear small
        # while the resulting span still advertises the original element count.
        let too_big = self.f.label()
        let fits = self.f.label()
        let done = self.f.label()
        let maximum = 18446744073709551615 if stride == 0 else 4611686018427387904 // stride
        let limit = ir.const_ref((i64)maximum)
        let big = try self.f.binary(ir.Op.cugt, ir.Class.l, count, limit)
        try self.f.branch(big, too_big, fits)
        try self.f.place_label(too_big)
        try self.store_error(a, result_type, (i64)check.exhausted_code(), "memory.exhausted: the allocation size overflows")
        try self.f.jump(done)
        try self.f.place_label(fits)
        let bytes = try self.f.binary(ir.Op.mul, ir.Class.l, count, ir.const_ref((i64)stride))
        let block = try self.allocate_bytes(view, bytes, ir.const_ref((i64)self.c.table.align_of(elem)))
        let present = try self.f.load(ir.Op.loadub, ir.Class.w, try self.offset_address(block, 16))
        let nonzero = try self.f.binary(ir.Op.cne, ir.Class.l, bytes, ir.const_ref(0))
        let missing = try self.f.binary(ir.Op.ceq, ir.Class.w, present, ir.const_ref(0))
        let failed = try self.f.binary(ir.Op.and_, ir.Class.w, nonzero, missing)
        let no = self.f.label()
        let yes = self.f.label()
        try self.f.branch(failed, no, yes)
        try self.f.place_label(no)
        try self.store_error(a, result_type, (i64)check.exhausted_code(), "memory.exhausted")
        try self.f.jump(done)
        try self.f.place_label(yes)
        let data = try self.f.load(ir.Op.loadl, ir.Class.l, block)
        if zero:
            try self.set_bytes(data, 0, bytes)
        elif self.diagnostic:
            try self.set_bytes(data, 170, bytes)
        try self.f.store(ir.Op.storel, data, a)
        try self.f.store(ir.Op.storel, count, try self.offset_address(a, 8))
        try self.f.store(ir.Op.storeb, ir.const_ref(0), try self.offset_address(a, self.failed_offset(result_type)))
        try self.f.jump(done)
        try self.f.place_label(done)
        return a

    ## `memset(data, byte, bytes)`, for a count of bytes known only when the program runs.
    func set_bytes(data: ir.Ref, byte: i64, bytes: ir.Ref) -> !:
        let start = u32(self.f.args.count)
        try self.f.args.push(ir.Arg(value = data, cls = ir.Class.l, size = 0, align = 8, type_id = types.usize_id, shape = 0))
        try self.f.args.push(ir.Arg(value = ir.const_ref(byte), cls = ir.Class.w, size = 0, align = 4, type_id = types.i32_id, shape = 0))
        try self.f.args.push(ir.Arg(value = bytes, cls = ir.Class.l, size = 0, align = 8, type_id = types.usize_id, shape = 0))
        _ = try self.call_named("memset", start, 3, ir.Class.l, true, types.usize_id)

    func new_expr(e: ast.Node*) -> LowerValue!:
        self.site_line = e.line
        let t = e.ty else return try self.fail(e, "no type")
        let result = try self.ty(e)
        let payload = self.elem(result)
        let source_view = try self.allocator_of(e.right)
        let view_slot = try self.f.slot(16, 8)
        let view = try self.slot_address(view_slot)
        try self.f.copy_bytes(view, source_view, 16)
        if self.is_span(payload):
            let count = t.right else return try self.fail(e, "no count")
            let cv = try self.value(count, types.usize_id)
            let a = try self.counted_allocation(view, self.elem(payload), cv.ref, result, true)
            return LowerValue(ref = a, type_id = result, in_memory = true)
        let et = self.elem(payload)
        let slot = try self.new_slot(result)
        let a = try self.slot_address(slot)
        let block = try self.allocate_bytes(view, ir.const_ref((i64)self.c.table.size_of(et)), ir.const_ref((i64)self.c.table.align_of(et)))
        let present = try self.f.load(ir.Op.loadub, ir.Class.w, try self.offset_address(block, 16))
        let ok = self.f.label()
        let bad = self.f.label()
        let done = self.f.label()
        try self.f.branch(present, ok, bad)
        try self.f.place_label(bad)
        try self.store_error(a, result, (i64)check.exhausted_code(), "memory.exhausted")
        try self.f.jump(done)
        try self.f.place_label(ok)
        let p = try self.f.load(ir.Op.loadl, ir.Class.l, block)
        if let init = e.initializer():
            let status = try self.initialize_at(e, init, et, p)
            if self.is_fail(status.type_id):
                let failed = try self.f.load(ir.Op.loadub, ir.Class.w, try self.offset_address(status.ref, self.failed_offset(status.type_id)))
                let fine = self.f.label()
                let broke = self.f.label()
                try self.f.branch(failed, broke, fine)
                try self.f.place_label(broke)
                try self.f.store(ir.Op.storeb, ir.const_ref(1), try self.offset_address(a, self.failed_offset(result)))
                # the allocator may fail and recover inside itself: the error stays the init's
                let kept = try self.f.slot(24, 8)
                try self.f.copy_bytes(try self.slot_address(kept), try self.failure_address(), 24)
                try self.allocator_release(view, block)
                try self.f.copy_bytes(try self.failure_address(), try self.slot_address(kept), 24)
                try self.f.jump(done)
                try self.f.place_label(fine)
        elif let body = e.body:
            let value = try self.enum_value(body) if body.kind == ast.Kind.case_value else try self.constructor(e, et)
            try self.f.copy_bytes(p, value.ref, self.size(et))
        elif e.text == "()":
            let value = try self.constructor(e, et)
            try self.f.copy_bytes(p, value.ref, self.size(et))
        else:
            try self.f.zero_bytes(p, self.size(et))
        try self.f.store(ir.Op.storel, p, a)
        try self.f.store(ir.Op.storeb, ir.const_ref(0), try self.offset_address(a, self.failed_offset(result)))
        try self.f.jump(done)
        try self.f.place_label(done)
        return LowerValue(ref = a, type_id = result, in_memory = true)

    ## `new T[count] ---`: `count` elements through the allocator, left unwritten (§12.2).
    func unwritten_expr(e: ast.Node*) -> LowerValue!:
        self.site_line = e.line
        let result = try self.ty(e)
        let payload = self.elem(result)
        let view = try self.allocator_of(e.right)
        let t = e.ty else return try self.fail(e, "no type")
        let count = t.right else return try self.fail(e, "no count")
        let cv = try self.value(count, types.usize_id)
        let a = try self.counted_allocation(view, self.elem(payload), cv.ref, result, false)
        return LowerValue(ref = a, type_id = result, in_memory = true)

    ## Whether the tree at `n` calls `memory.frame` (§12.7).
    func calls_frame(n: ast.Node*?) -> bool:
        var cursor = n
        while let x = cursor:
            if x.kind == ast.Kind.call:
                if let d = x.resolved:
                    if self.c.is_memory_frame(d):
                        return true
            if self.calls_frame(x.left) or self.calls_frame(x.right) or self.calls_frame(x.body) or self.calls_frame(x.ty):
                return true
            cursor = x.next
        return false

    ## `memory.frame[T](count, most)` (§12.7): `count` elements taken from the frame, after a
    ## trap when `count` is past `most`; the span is the bytes' address and `count`. The
    ## diagnostic profile fills the bytes with its pattern (§19.4).
    func frame_storage(e: ast.Node*) -> LowerValue!:
        let result = try self.ty(e)
        let first = e.body else return try self.fail(e, "no count")
        let second = first.next else return try self.fail(e, "no most")
        let count_node = first.left else return try self.fail(e, "no count")
        let most_node = second.left else return try self.fail(e, "no most")
        let most = self.c.constant_u64(most_node) else return try self.fail(e, "`memory.frame`'s most is a constant")
        let cv = try self.value(count_node, types.usize_id)
        let over = try self.f.binary(ir.Op.cugt, ir.Class.l, cv.ref, ir.const_ref((i64)most))
        let past = self.f.label()
        let within = self.f.label()
        try self.f.branch(over, past, within)
        try self.f.place_label(past)
        try self.trap_with("memory.frame count is past its most")
        try self.f.place_label(within)
        # the bytes, to sixteen; count is at most `most`, so this cannot overflow
        let bytes = try self.f.binary(ir.Op.mul, ir.Class.l, cv.ref, ir.const_ref((i64)self.size(self.elem(result))))
        let rounded = try self.f.binary(ir.Op.and_, ir.Class.l, try self.f.binary(ir.Op.add, ir.Class.l, bytes, ir.const_ref(15)), ir.const_ref(-16))
        let t = try self.temp(ir.Class.l)
        try self.f.emit(ir.Op.alloca, ir.Class.l, t.index, rounded, ir.none_ref(), 0)
        self.f.allocates_frame = true
        if self.diagnostic:
            # the diagnostic profile fills unwritten storage with a pattern (§19.4)
            try self.set_bytes(t, 170, bytes)
        let slot = try self.new_slot(result)
        let a = try self.slot_address(slot)
        try self.f.store(ir.Op.storel, t, a)
        try self.f.store(ir.Op.storel, cv.ref, try self.offset_address(a, 8))
        return LowerValue(ref = a, type_id = result, in_memory = true)