uvg_analyze.jou

# See doc/compiler_internals/uvg.md

import "stdlib/str.jou"
import "stdlib/mem.jou"

import "./uvg.jou"
import "./errors_and_warnings.jou"


enum VarStatus:
    Unvisited           # Don't know anything about this variable yet.
    Undefined           # Holds a garbage value.
    Defined             # This variable has been set to some non-garbage value.
    PossiblyUndefined   # Could hold a garbage or non-garbage value.
    DontAnalyze         # The "don't analyze" UVG instruction has been used.


# TODO: use "if False:"
if WINDOWS and not WINDOWS:
    def print_statuses(uvg: Uvg*, statuses: VarStatus*) -> None:
        printf("VAR STATUSES:")
        for v = 0; v < uvg->nvars; v++:
            printf(" %s=", uvg->varnames[v])
            match statuses[v]:
                case VarStatus.Unvisited:
                    printf("{}")
                case VarStatus.Undefined:
                    printf("{u}")
                case VarStatus.Defined:
                    printf("{d}")
                case VarStatus.PossiblyUndefined:
                    printf("{u,d}")
                case VarStatus.DontAnalyze:
                    printf("-")
        printf("\n")


# a and b are statuses from different branches that both jump to the same block.
# Should have these properties:
#
#   merge(a, VarStatus.Unvisited) == a
#   merge(a, a) == a
#   merge(a, b) == merge(b, a)
#   merge(a, merge(b, c)) == merge(merge(a, b), c)
#
# In other words:
#   - It makes sense to merge an unordered collection of statuses.
#   - Unvisited corresponds with merging an empty set of statuses.
#   - Having the same status several times doesn't affect anything.
#
# Or even more simply: It makes sense to think of statuses as sets. Merging
# means taking the union of those sets. Unvisited is the empty set.
def merge(a: VarStatus, b: VarStatus) -> VarStatus:
    if a == b:
        return a

    if a == VarStatus.DontAnalyze or b == VarStatus.DontAnalyze:
        return VarStatus.DontAnalyze

    if a == VarStatus.Unvisited:
        return b
    if b == VarStatus.Unvisited:
        return a

    assert a == VarStatus.Undefined or a == VarStatus.Defined or a == VarStatus.PossiblyUndefined
    assert b == VarStatus.Undefined or b == VarStatus.Defined or b == VarStatus.PossiblyUndefined
    assert a != b
    return VarStatus.PossiblyUndefined


def build_statuses_at_end_before_analyzing(uvg: Uvg*) -> VarStatus**:
    # statuses_at_end[b][v] = status of variable v at end of block b
    statuses_at_end: VarStatus** = malloc(sizeof(statuses_at_end[0]) * uvg->nblocks)
    assert statuses_at_end != NULL
    for b = 0; b < uvg->nblocks; b++:
        statuses_at_end[b] = malloc(sizeof(statuses_at_end[b][0]) * uvg->nvars)
        if uvg->nvars != 0:
            assert statuses_at_end[b] != NULL
        for v = 0; v < uvg->nvars; v++:
            statuses_at_end[b][v] = VarStatus.Unvisited
    return statuses_at_end


def free_statuses(uvg: Uvg*, statuses_at_end: VarStatus**) -> None:
    for b = 0; b < uvg->nblocks; b++:
        free(statuses_at_end[b])
    free(statuses_at_end)


def build_statuses_at_start_of_block(uvg: Uvg*, statuses_at_end: VarStatus**, blockidx: int) -> VarStatus*:
    statuses: VarStatus* = malloc(sizeof(statuses[0]) * uvg->nvars)
    if uvg->nvars != 0:
        assert statuses != NULL

    for v = 0; v < uvg->nvars; v++:
        if blockidx == 0:
            # The start block, everything is initially undefined
            statuses[v] = VarStatus.Undefined
        else:
            statuses[v] = VarStatus.Unvisited

        for b = 0; b < uvg->nblocks; b++:
            if uvg->blocks[b]->jumps_to(uvg->blocks[blockidx]):
                statuses[v] = merge(statuses[v], statuses_at_end[b][v])

    return statuses


def handle_missing_return_statement(uvg: Uvg*, location: Location) -> None:
    # Check if there is a "return" statement that user wrote.
    n = 0
    for b = 0; b < uvg->nblocks; b++:
        if uvg->blocks[b]->terminator.kind == UvgTerminatorKind.Return:
            n++

    # There is always automatically generated "return" statement at the end of the function.
    assert n >= 1

    msg: byte[500]
    if n == 1:
        # There are no return statements. Tell user to add them and why they are needed.
        snprintf(
            msg, sizeof(msg),
            "%s '%s' must return a value, because it is defined with '-> %s'",
            uvg->signature->function_or_method(),
            uvg->signature->name,
            uvg->signature->returntype->name,
        )
        fail(location, msg)
    else:
        # There are some return statements but they don't cover all cases.
        snprintf(
            msg, sizeof(msg),
            "%s '%s' does not seem to return a value in all cases",
            uvg->signature->function_or_method(),
            uvg->signature->name,
        )
        show_warning(location, msg)


def update_statuses_based_on_instructions(uvg: Uvg*, statuses: VarStatus*, block: UvgBlock*, warn: bool) -> None:
    msg: byte[500]

    for ins = block->instructions; ins < &block->instructions[block->ninstructions]; ins++:
        match ins->kind:
            case UvgInstructionKind.Set:
                if statuses[ins->var] != VarStatus.DontAnalyze:
                    statuses[ins->var] = VarStatus.Defined
            case UvgInstructionKind.Use:
                if warn and uvg->varnames[ins->var][0] != '$':
                    match statuses[ins->var]:
                        case VarStatus.Defined | VarStatus.DontAnalyze:
                            pass
                        case VarStatus.Undefined:
                            if strcmp(uvg->varnames[ins->var], "return") == 0:
                                handle_missing_return_statement(uvg, ins->location)
                            else:
                                snprintf(msg, sizeof(msg), "the value of '%s' is undefined", uvg->varnames[ins->var])
                                show_warning(ins->location, msg)
                        case VarStatus.PossiblyUndefined:
                            if strcmp(uvg->varnames[ins->var], "return") == 0:
                                handle_missing_return_statement(uvg, ins->location)
                            else:
                                snprintf(msg, sizeof(msg), "the value of '%s' may be undefined", uvg->varnames[ins->var])
                                show_warning(ins->location, msg)
                        case VarStatus.Unvisited:
                            pass
            case UvgInstructionKind.DontAnalyze:
                statuses[ins->var] = VarStatus.DontAnalyze


def analyze_block(uvg: Uvg*, statuses_at_end: VarStatus**, blockidx: int, warn: bool) -> bool:
    statuses = build_statuses_at_start_of_block(uvg, statuses_at_end, blockidx)
    update_statuses_based_on_instructions(uvg, statuses, uvg->blocks[blockidx], warn)

    if memcmp(statuses, statuses_at_end[blockidx], sizeof(statuses[0]) * uvg->nvars) != 0:
        # Statuses changed
        assert not warn  # warnings should be applied at the end when statuses are stable
        free(statuses_at_end[blockidx])
        statuses_at_end[blockidx] = statuses
        return True
    else:
        free(statuses)
        return False


def find_true(arr: bool*, len: int) -> int:
    for i = 0; i < len; i++:
        if arr[i]:
            return i
    return -1


@public
def uvg_analyze(uvg: Uvg*) -> None:
    assert uvg->nblocks >= 1  # must have at least start block

    queue: bool* = calloc(sizeof(queue[0]), uvg->nblocks)
    reachable: bool* = calloc(sizeof(queue[0]), uvg->nblocks)
    assert queue != NULL
    assert reachable != NULL

    statuses_at_end = build_statuses_at_end_before_analyzing(uvg)

    queue[0] = True
    while True:
        blockidx = find_true(queue, uvg->nblocks)
        if blockidx == -1:
            break
        reachable[blockidx] = True

        queue[blockidx] = False
        if analyze_block(uvg, statuses_at_end, blockidx, False):
            for b = 0; b < uvg->nblocks; b++:
                if uvg->blocks[blockidx]->jumps_to(uvg->blocks[b]):
                    queue[b] = True

    for b = 0; b < uvg->nblocks; b++:
        if reachable[b]:
            analyze_block(uvg, statuses_at_end, b, True)

    free_statuses(uvg, statuses_at_end)
    free(queue)
    free(reachable)