Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.46.0

0.46.0 / src / back / assemble / layout.lucb

#==============================================================================================
#
#   layout - Where everything lands, and the object it makes
#
#   DESCRIPTION:
#       The pieces of every section start small: a jump short, an alignment as its address
#       asks. Passes over the sections then size each piece from where its target lands,
#       as GNU `as` relaxes: a place before the piece where this pass put it, one after it
#       where the last pass did, moved by what this pass has grown so far. A jump only
#       grows, so the passes end, each a walk of the pieces; the layout is final when one
#       changes nothing. The object then takes each section's bytes with the pieces
#       written in and the fixups resolved: a distance within a section, or a jump or
#       displacement to a place in it, becomes a number; anything else a relocation, the
#       addend in place, against the section's own symbol for a place defined here, or the
#       symbol itself when it is undefined or weak.
#
#==============================================================================================

import back.assemble.contents
import back.assemble.directives
import back.assemble.object
import back.assemble.state
import memory
import strings
import support.list

# mark: Settling the pieces ===================================================================

## Size every piece of every section from where things land, until nothing changes.
pub func settle(u: state.Unit*) -> !:
    for i in 0..<u.sections.count:
        let s = &u.sections.items[i]
        let n = s.pieces.count
        if s.growth.length != n + 1:
            s.growth = try new u64[n + 1] ---
            s.regions = try new u32[n + 1] ---
        var running: u64 = 0
        var region: u32 = 0
        for k in 0..<n:
            s.growth[k] = running
            s.regions[k] = region
            let p = &s.pieces.items[k]
            running += p.size
            if p.shape == state.Shape.align or p.shape == state.Shape.pad:
                region += 1
        s.growth[n] = running
        s.regions[n] = region
    var passes = 0
    while true:
        var changed = false
        for i in 0..<u.sections.count:
            if try relax(u, u32(i)):
                changed = true
        if not changed:
            return
        passes += 1
        if passes > 1000:
            try u.fail("the layout does not settle")

## One pass over section `i`'s pieces; whether one changed size.
func relax(u: state.Unit*, i: u32) -> bool!:
    let s = &u.sections.items[i]
    var running: u64 = 0
    var changed = false
    for k in 0..<s.pieces.count:
        let p = &s.pieces.items[k]
        let stretch = (i64)running - (i64)s.growth[k]
        s.growth[k] = running
        let address = p.at + running
        var size = p.size
        match p.shape:
            .jump, .branch:
                if size == 2 and not try reaches(u, i, k, stretch, p, address):
                    size = 5 if p.shape == state.Shape.jump else 6
            .align, .pad:
                size = padding(address, p.power, p.limit)
            .uleb, .sleb:
                u.line = p.line
                size = directives.leb_size(try distance(u, i, k, stretch, p.value), p.shape == state.Shape.sleb)
        if size != p.size:
            changed = true
            p.size = size
        running += size
    s.growth[s.pieces.count] = running
    return changed

## Where `place` is during the pass over section `i` at piece `k`: placed already when it
## is before the piece, else where the last pass put it, moved by `stretch`.
func address_in_pass(u: state.Unit*, i: u32, k: usize, stretch: i64, place: state.Place) -> u64:
    let s = &u.sections.items[place.section]
    let address = place.offset + s.growth[place.pieces]
    if place.section != i or (usize)place.pieces <= k:
        return address
    return (u64)((i64)address + stretch)

## Whether the two-byte jump `p` at `address`, piece `k` of section `i`, reaches its
## target: a label in the same section, not weak, within a signed byte of the jump's end.
## A label this pass has not reached yet moves with the growth so far, unless an alignment
## lies between, which may absorb it; one that then seems behind the jump is not judged
## until the next pass, as GNU `as` relaxes.
func reaches(u: state.Unit*, i: u32, k: usize, stretch: i64, p: state.Piece*, address: u64) -> bool!:
    let t = &u.symbols.items[p.value.symbol - 1]
    if not t.defined or t.weak or t.place.section != i:
        return false
    let s = &u.sections.items[i]
    var target = (i64)(t.place.offset + s.growth[t.place.pieces]) + p.value.constant
    if (usize)t.place.pieces > k and stretch != 0:
        if stretch < 0 or s.regions[t.place.pieces] == s.regions[k]:
            target += stretch
        elif target < (i64)address:
            return true
    let aim = target - (i64)(address + 1)
    return aim >= -127 and aim <= 128

## The padding an alignment to `2^power` needs at `address`, none past `limit`.
func padding(address: u64, power: u8, limit: u64) -> u64:
    let size = (u64)1 << power
    let pad = (size - address % size) % size
    return 0 if limit != 0 and pad > limit else pad

## The value of distance `v` during a pass: both its symbols placed in one section.
func distance(u: state.Unit*, i: u32, k: usize, stretch: i64, v: state.Value) -> i64!:
    if v.symbol == 0 or v.minus == 0:
        try u.fail("a LEB128 is a number or the distance between two labels")
    let a = &u.symbols.items[v.symbol - 1]
    let b = &u.symbols.items[v.minus - 1]
    if not a.defined or not b.defined or a.place.section != b.place.section:
        try u.fail(f"`{a.name}` and `{b.name}` are not both defined in one section")
    return (i64)address_in_pass(u, i, k, stretch, a.place) - (i64)address_in_pass(u, i, k, stretch, b.place) + v.constant

# mark: The object ============================================================================

## The object the settled unit makes: its symbols, then each section's bytes and
## relocations.
pub func object_of(u: state.Unit*) -> object.Object!:
    var o = try object.Object.create()
    for i in 0..<u.sections.count:
        u.sections.items[i].number = u32(i + 1)
    try mark_referenced(u)
    try symbols(u, &o)
    for i in 0..<u.sections.count:
        try o.sections.push(try contents.contents(u, u32(i)))
    return o

## Mark each symbol a relocation may name: one a fixup or a jump refers to while it is
## undefined, or weak; and each empty section a relocation names through a place in it.
func mark_referenced(u: state.Unit*) -> !:
    for i in 0..<u.sections.count:
        let s = &u.sections.items[i]
        for f in s.fixups.span():
            if f.value.minus == 0:
                mark(u, f.value.symbol)
        for p in s.pieces.span():
            if p.shape == state.Shape.jump or p.shape == state.Shape.branch:
                mark(u, p.value.symbol)
    for s in u.symbols.span():
        if s.referenced and not s.defined and state.starts(s.name, " "):
            try u.fail("a numbered label is used but never defined")

func mark(u: state.Unit*, symbol: u32):
    if symbol == 0:
        return
    let s = &u.symbols.items[symbol - 1]
    if not s.defined or s.weak:
        s.referenced = true
    else:
        u.sections.items[s.place.section].referenced = true

## The symbol table, in the order of GNU `as`'s COFF: the file, the local labels, the
## sections, then the defined globals, each weak symbol's fallback where the weak symbol
## first appeared, then the undefined and weak externals; each kind in the order its
## symbols were first named.
func symbols(u: state.Unit*, o: object.Object*) -> !:
    try o.symbols.push(object.Symbol(name = "fake", section = 0, value = 0, binding = object.Binding.file, code = false, fallback = 0))
    for s in &u.symbols.span():
        if s.defined and not s.external and not s.weak and not s.hidden:
            s.index = u32(o.symbols.count)
            try o.symbols.push(defined(u, s, object.Binding.internal))
    # every section's symbol but an empty one's (`.text`, `.data` and `.bss` aside), which
    # only a relocation brings, and then without its auxiliary record, as GNU `as` does
    for i in 0..<u.sections.count:
        let s = &u.sections.items[i]
        let empty = s.size() == 0 and i >= 3
        if empty and not s.referenced:
            continue
        s.symbol = u32(o.symbols.count)
        try o.symbols.push(object.Symbol(name = s.name, section = s.number, value = 0,
                                         binding = object.Binding.internal if empty else object.Binding.section_base, code = false, fallback = 0))
    # a weak symbol's fallback is named after the first defined global
    var first = ""
    for s in u.symbols.span():
        if s.defined and s.external and not s.weak:
            first = s.name
            break
    for s in &u.symbols.span():
        if s.weak:
            s.fallback = u32(o.symbols.count)
            var room: u8[4096]
            let name = try strings.format(room, f".weak.{s.name}.{first}")
            var fallback = object.Symbol(name = try strings.copy(name), section = object.absolute_section, value = 0, binding = object.Binding.external,
                                         code = false, fallback = 0)
            if s.defined:
                fallback = defined(u, s, object.Binding.external)
                fallback.name = try strings.copy(name)
            try o.symbols.push(fallback)
        elif s.defined and s.external:
            s.index = u32(o.symbols.count)
            try o.symbols.push(defined(u, s, object.Binding.external))
    for s in &u.symbols.span():
        if s.weak:
            s.index = u32(o.symbols.count)
            try o.symbols.push(object.Symbol(name = s.name, section = 0, value = 0, binding = object.Binding.weak_external, code = false,
                                             fallback = s.fallback))
        elif not s.defined and (s.external or s.referenced):
            # an undefined `L` name is another object's, like any other
            s.index = u32(o.symbols.count)
            try o.symbols.push(object.Symbol(name = s.name, section = 0, value = 0, binding = object.Binding.external, code = false, fallback = 0))

## Defined symbol `s` as the object names it, with `binding`.
func defined(u: state.Unit*, s: const state.Symbol*, binding: object.Binding) -> object.Symbol:
    let section = &u.sections.items[s.place.section]
    return object.Symbol(name = s.name, section = section.number, value = section.address(s.place), binding = binding,
                         code = section.content == object.Content.code, fallback = 0)