#-------------------------------------------------------------------------------
# Lowering pass 5: Flatten to linear IR

# Must outline anything that can throw, e.g. globalrefs, static params
function is_valid_ir_argument(ctx, ex)
    k = kind(ex)
    if is_simple_atom(ctx, ex) || k in KSet"inert syntaxinert top core quote static_eval foreignsymbol"
        true
    elseif k == K"BindingId"
        binfo = get_binding(ctx, ex)
        bk = binfo.kind
        bk === :slot
    else
        false
    end
end

function is_ssa(ctx, ex)
    kind(ex) == K"BindingId" && get_binding(ctx, ex).is_ssa
end

# Target to jump to, including info on try handler nesting and catch block
# nesting
struct JumpTarget
    label::SyntaxTree
    handler_token_stack::Vector{SyntaxTree}
    catch_token_stack::Vector{SyntaxTree}
    result_var::Union{SyntaxTree, Nothing}  # for symbolicblock valued breaks
end

function JumpTarget(label::SyntaxTree, ctx, result_var=nothing)
    JumpTarget(label, copy(ctx.handler_token_stack), copy(ctx.catch_token_stack), result_var)
end

struct JumpOrigin
    goto::SyntaxTree
    index::Int
    handler_token_stack::Vector{SyntaxTree}
    catch_token_stack::Vector{SyntaxTree}
end

function JumpOrigin(goto::SyntaxTree, index, ctx)
    JumpOrigin(goto, index, copy(ctx.handler_token_stack), copy(ctx.catch_token_stack))
end

struct FinallyHandler
    tagvar::SyntaxTree
    target::JumpTarget
    exit_actions::Vector{Tuple{Symbol,Union{Nothing,SyntaxTree}}}
end

function FinallyHandler(tagvar::SyntaxTree, target::JumpTarget)
    FinallyHandler(tagvar, target,
        Vector{Tuple{Symbol, Union{Nothing,SyntaxTree}}}())
end

"""
Context for creating linear IR.

One of these is created per lambda expression to flatten the body down to
a sequence of statements (linear IR), which eventually becomes one CodeInfo.
"""
mutable struct LinearIRContext <: AbstractLoweringContext
    const code::Vector{SyntaxTree}
    const bindings::Bindings
    const next_label_id::Base.RefValue{Int}
    const is_toplevel_thunk::Bool
    const lambda_bindings::LambdaBindings
    const argmap::Dict{IdTag, IdTag}
    const rettype_ssa::Base.RefValue{Union{Nothing,SyntaxTree}}
    const break_targets::Dict{String, JumpTarget}
    const break_label_stack::Vector{String}  # tracks nesting order of symbolicblock labels
    const handler_token_stack::Vector{SyntaxTree}
    const catch_token_stack::Vector{SyntaxTree}
    const finally_handlers::Vector{FinallyHandler}
    const symbolic_jump_targets::Dict{String,JumpTarget}
    const symbolic_jump_origins::Vector{JumpOrigin}
    const symbolic_block_labels::Set{String}  # labels that are symbolic blocks (not allowed as @goto targets)
    const meta::Dict{Symbol, Any}
    const mod::Module
end

function rettype(ctx::LinearIRContext)
    let r = ctx.rettype_ssa[]
        isnothing(r) ? nothing : r
    end
end

function LinearIRContext(ctx, is_toplevel_thunk, lambda_bindings)
    LinearIRContext(SyntaxList(), ctx.bindings, Ref(0),
                    is_toplevel_thunk, lambda_bindings, Dict{IdTag,IdTag}(),
                    Ref{Union{Nothing,SyntaxTree}}(nothing),
                    Dict{String,JumpTarget}(), String[],
                    SyntaxList(), SyntaxList(),
                    Vector{FinallyHandler}(), Dict{String,JumpTarget}(),
                    Vector{JumpOrigin}(), Set{String}(), Dict{Symbol, Any}(), ctx.mod)
end

function current_lambda_bindings(ctx::LinearIRContext)
    ctx.lambda_bindings
end

function is_valid_body_ir_argument(ctx, ex)
    if is_valid_ir_argument(ctx, ex)
        true
    elseif kind(ex) == K"BindingId"
        get_binding(ctx, ex).is_always_defined
    else
        false
    end
end

function is_simple_arg(ctx, ex)
    k = kind(ex)
    return is_simple_atom(ctx, ex) || k == K"BindingId" || k == K"quote" ||
        k == K"inert" || k == K"syntaxinert" || k == K"top" ||
        k == K"core" || k == K"globalref" || k == K"static_eval" ||
        k == K"foreignsymbol"
end

# flisp note: arguments are always counted as single-assign, so effects on
# arguments within compile_args are thrown out (intentional?)
function is_single_assign_var(ctx::LinearIRContext, ex)
    kind(ex) == K"BindingId" || return false
    binfo = get_binding(ctx, ex)
    return binfo.kind == :argument || binfo.is_assigned_once
end

function is_const_read_arg(ctx, ex)
    k = kind(ex)
    # Even if we have side effects, we know that singly-assigned
    # locals cannot be affected by them so we can inline them anyway.
    # TODO from flisp: "We could also allow const globals here"
    return k == K"inert" || k == K"syntaxinert" || k == K"top" ||
        k == K"core" || k == K"static_eval" || k == K"foreignsymbol" ||
        is_simple_atom(ctx, ex) || is_single_assign_var(ctx, ex)
end

function is_valid_ir_rvalue(ctx, lhs, rhs)
    return is_ssa(ctx, lhs) ||
           is_valid_ir_argument(ctx, rhs) ||
           (kind(lhs) == K"BindingId" &&
            # FIXME: add: invoke ?
            kind(rhs) in KSet"new splatnew cfunction isdefined call foreigncall foreignglobal gc_preserve_begin new_opaque_closure")
end

function check_no_local_bindings(ctx, ex, msg)
    contains_nonglobal_binding = contains_unquoted(ex) do e
        kind(e) == K"BindingId" && get_binding(ctx, e).kind !== :global
    end
    if contains_nonglobal_binding
        throw(LoweringError(ex, msg))
    end
end

# evaluate the arguments of a call, creating temporary locations as needed
function compile_args(ctx, args)
    # First check if all the arguments are simple (and therefore side-effect free).
    # Otherwise, we need to use ssa values for all arguments to ensure proper
    # left-to-right evaluation semantics.
    all_simple = all(a->is_simple_arg(ctx, a), args)
    args_out = SyntaxList()
    for arg in args
        arg_val = compile(ctx, arg, true, false)
        if isnothing(arg_val)
            # arguments that don't return a value, e.g. `f(return)`
            push!(args_out, nothing_(ctx, arg))
        elseif ((all_simple || is_const_read_arg(ctx, arg_val)) &&
                is_valid_body_ir_argument(ctx, arg_val))
            push!(args_out, arg_val)
        else
            push!(args_out, emit_assign_tmp(ctx, arg_val))
        end
    end
    return args_out
end

function emit(ctx::LinearIRContext, ex)
    push!(ctx.code, ex)
    return ex
end

# Emit computation of ex, assigning the result to an ssavar and returning that
function emit_assign_tmp(ctx::LinearIRContext, ex, name="tmp")
    tmp = ssavar(ctx, ex, name)
    emit(ctx, @ast ctx ex [K"=" tmp ex])
    return tmp
end

function compile_pop_exception(ctx, srcref, src_tokens, dest_tokens)
    # It's valid to leave the context of src_tokens for the context of
    # dest_tokens when src_tokens is the same or nested within dest_tokens.
    # It's enough to check the token on the top of the dest stack.
    n = length(dest_tokens)
    jump_ok = n == 0 || (n <= length(src_tokens) && syntax_id(dest_tokens[n]) == syntax_id(src_tokens[n]))
    jump_ok || throw(LoweringError(srcref, "Attempt to jump into catch block"))
    if n < length(src_tokens)
        @ast ctx srcref [K"pop_exception" src_tokens[n+1]]
    else
        nothing
    end
end

function compile_leave_handler(ctx, srcref, src_tokens, dest_tokens)
    n = length(dest_tokens)
    jump_ok = n == 0 || (n <= length(src_tokens) && syntax_id(dest_tokens[n]) == syntax_id(src_tokens[n]))
    jump_ok || throw(LoweringError(srcref, "Attempt to jump into try block"))
    if n < length(src_tokens)
        @ast ctx srcref [K"leave" src_tokens[n+1:end]...]
    else
        nothing
    end
end

function emit_pop_exception(ctx::LinearIRContext, srcref, dest_tokens)
    pexc = compile_pop_exception(ctx, srcref, ctx.catch_token_stack, dest_tokens)
    if !isnothing(pexc)
        emit(ctx, pexc)
    end
end

function emit_leave_handler(ctx::LinearIRContext, srcref, dest_tokens)
    ex = compile_leave_handler(ctx, srcref, ctx.handler_token_stack, dest_tokens)
    if !isnothing(ex)
        emit(ctx, ex)
    end
end

# Enter the current finally block, either through the landing pad (on_exit ==
# :rethrow) or via a jump (on_exit ∈ (:return, :break)).
#
# An integer tag is created to identify the current code path and select the
# on_exit action to be taken at finally handler exit.
function enter_finally_block(ctx, srcref, on_exit, value)
    @jl_assert on_exit ∈ (:rethrow, :break, :return) srcref
    handler = last(ctx.finally_handlers)
    push!(handler.exit_actions, (on_exit, value))
    tag = length(handler.exit_actions)
    emit(ctx, @ast ctx srcref [K"=" handler.tagvar tag::K"Integer"])
    if on_exit != :rethrow
        emit_pop_exception(ctx, srcref, handler.target.catch_token_stack)
        emit_leave_handler(ctx, srcref, handler.target.handler_token_stack[1:end-1])
        emit(ctx, @ast ctx srcref [K"goto" handler.target.label])
    end
    tag
end

# Helper function for emit_return
function _actually_return(ctx, ex)
    # TODO: Handle the implicit return coverage hack for #53354 ?
    if (rett = rettype(ctx); !isnothing(rett))
        ex = compile(ctx, convert_for_type_decl(ctx, rett, ex, rett, true), true, false)
    end
    simple_ret_val = isempty(ctx.catch_token_stack) ?
        # returning lambda directly is needed for @generated
        (is_valid_ir_argument(ctx, ex) || kind(ex) == K"lambda") :
        is_simple_atom(ctx, ex)
    if !simple_ret_val
        ex = emit_assign_tmp(ctx, ex, "return_tmp")
    end
    emit_pop_exception(ctx, ex, SyntaxList())
    emit(ctx, @ast ctx ex [K"return" ex])
    return nothing
end

function emit_return(ctx, srcref, ex)
    # todo: Mark implicit returns
    if isnothing(ex)
        return
    elseif isempty(ctx.handler_token_stack)
        _actually_return(ctx, ex)
        return
    end
    # TODO: What's this !is_ssa(ctx, ex) here about?
    x = if is_simple_atom(ctx, ex) && !(is_ssa(ctx, ex) && !isempty(ctx.finally_handlers))
        ex
    elseif !isempty(ctx.finally_handlers)
        # todo: Why does flisp lowering create a mutable variable here even
        # though we don't mutate it?
        # tmp = ssavar(ctx, srcref, "returnval_via_finally") # <- can we use this?
        tmp = new_local_binding(ctx, srcref, "returnval_via_finally")
        emit(ctx, @ast ctx srcref [K"=" tmp ex])
        tmp
    else
        emit_assign_tmp(ctx, ex, "returnval_via_finally")
    end
    if !isempty(ctx.finally_handlers)
        enter_finally_block(ctx, srcref, :return, x)
    else
        emit(ctx, @ast ctx srcref [K"leave" ctx.handler_token_stack...])
        _actually_return(ctx, x)
    end
    return nothing
end

function emit_return(ctx, ex)
    emit_return(ctx, ex, ex)
end

function emit_break(ctx, ex)
    name = syntax_name(ex[1])
    target = get(ctx.break_targets, name, nothing)
    if isnothing(target)
        if name == "loop-exit"
            throw(LoweringError(ex, "`break` must be used inside a `while`, `for` loop, or `@label` block"))
        elseif name == "loop-cont"
            throw(LoweringError(ex, "`continue` must be used inside a `while` or `for` loop"))
        elseif endswith(name, "#cont")
            label = name[1:end-5]
            throw(LoweringError(ex, "`continue $label` is not inside a `@label $label` loop"))
        else
            throw(LoweringError(ex, "`break $name` is not inside a `@label $name` block"))
        end
    end
    # If targeting loop-exit, check for intervening named @label blocks
    if name == "loop-exit"
        for i in lastindex(ctx.break_label_stack):-1:1
            lbl = ctx.break_label_stack[i]
            lbl == "loop-exit" && break
            if lbl != "loop-cont" && !contains(lbl, '#')
                throw(LoweringError(ex,
                    "plain `break` inside `@label $lbl` block is disallowed; use `break $lbl` to exit the block"))
            end
        end
    end
    # If targeting loop-cont, check for intervening loop-exit (@label block)
    if name == "loop-cont"
        for i in lastindex(ctx.break_label_stack):-1:1
            lbl = ctx.break_label_stack[i]
            lbl == "loop-cont" && break
            if lbl == "loop-exit"
                throw(LoweringError(ex, "`continue` inside an anonymous `@label` block is not allowed"))
            end
        end
    end
    # Handle valued break (break name val)
    if numchildren(ex) >= 2
        if isnothing(target.result_var)
            throw(LoweringError(ex, "break with value not allowed for label `$name`"))
        end
        val = compile(ctx, ex[2], true, false)
        emit_assignment(ctx, ex, target.result_var, val)
    end
    if (!isempty(ctx.finally_handlers) && length(target.handler_token_stack) <
        length(last(ctx.finally_handlers).target.handler_token_stack))
        enter_finally_block(ctx, ex, :break, ex)
        return
    else
        emit_pop_exception(ctx, ex, target.catch_token_stack)
        emit_leave_handler(ctx, ex, target.handler_token_stack)
        emit(ctx, @ast ctx ex [K"goto" target.label])
    end
end

# `op` may be either K"=" (where global assignments are converted to setglobal!)
# or K"constdecl".  flisp: emit-assignment-or-setglobal
function emit_simple_assignment(ctx, srcref, lhs, rhs, op=K"=")
    binfo = get_binding(ctx, lhs)
    if binfo.kind == :global
        emit(ctx, @ast ctx srcref [
            K"call"
            op == K"constdecl" ? "declare_const"::K"core" : "setglobal!"::K"core"
            binfo.mod::K"Value"
            binfo.name::K"Symbol"
            rhs
        ])
    else
        emit(ctx, @ast ctx srcref [op lhs rhs])
    end
end

function emit_assignment(ctx, srcref, lhs, rhs, op=K"=")
    if !isnothing(rhs)
        if is_valid_ir_rvalue(ctx, lhs, rhs)
            emit_simple_assignment(ctx, srcref, lhs, rhs, op)
        else
            r = emit_assign_tmp(ctx, rhs)
            emit_simple_assignment(ctx, srcref, lhs, r, op)
        end
    else
        # in unreachable code (such as after return); still emit the assignment
        # so that the structure of those uses is preserved
        emit_simple_assignment(ctx, srcref, lhs, nothing_(ctx, srcref), op)
        nothing
    end
end

function make_label(ctx, srcref)
    id = ctx.next_label_id[]
    ctx.next_label_id[] += 1
    newleaf(srcref, K"label", id)
end

# flisp: make&mark-label
function emit_label(ctx, srcref)
    if !isempty(ctx.code)
        # Use current label if available
        e = ctx.code[end]
        if kind(e) == K"label"
            return e
        end
    end
    l = make_label(ctx, srcref)
    emit(ctx, l)
    l
end

function emit_latestworld(ctx, srcref)
    (isempty(ctx.code) || kind(last(ctx.code)) != K"latestworld") &&
        emit(ctx, kind(srcref) === K"latestworld" ? srcref :
        newleaf(srcref, K"latestworld"))
end

function compile_condition_term(ctx, ex)
    cond = compile(ctx, ex, true, false)
    isnothing(cond) && return nothing
    if !is_valid_body_ir_argument(ctx, cond)
        cond = emit_assign_tmp(ctx, cond)
    end
    return cond
end

# flisp: emit-cond
function compile_conditional(ctx, ex, false_label)
    if kind(ex) == K"block" && numchildren(ex) >= 1
        for i in 1:numchildren(ex)-1
            compile(ctx, ex[i], false, false)
        end
        test = ex[end]
    else
        test = ex
    end
    k = kind(test)
    if k == K"||"
        true_label = make_label(ctx, test)
        for (i,e) in enumerate(children(test))
            c = compile_condition_term(ctx, e)
            isnothing(c) && break
            if i < numchildren(test)
                next_term_label = make_label(ctx, test)
                # Jump over short circuit
                emit(ctx, @ast ctx e [K"gotoifnot" c next_term_label])
                # Short circuit to true
                emit(ctx, @ast ctx e [K"goto" true_label])
                emit(ctx, next_term_label)
            else
                emit(ctx, @ast ctx e [K"gotoifnot" c false_label])
            end
        end
        emit(ctx, true_label)
    elseif k == K"&&"
        for e in children(test)
            c = compile_condition_term(ctx, e)
            isnothing(c) && break
            emit(ctx, @ast ctx e [K"gotoifnot" c false_label])
        end
    else
        c = compile_condition_term(ctx, test)
        isnothing(c) || emit(ctx, @ast ctx test [K"gotoifnot" c false_label])
    end
end

# Lowering of exception handling must ensure that
#
# * Each `enter` is matched with a `leave` on every possible non-exceptional
#   program path (including implicit returns generated in tail position).
# * Each catch block which is entered and handles the exception - by exiting
#   via a non-exceptional program path - leaves the block with `pop_exception`.
# * Each `finally` block runs, regardless of any early `return` or jumps
#   via `break`/`continue`/`goto` etc.
#
# These invariants are upheld by tracking the nesting using
# `handler_token_stack` and `catch_token_stack` and using these when emitting
# any control flow (return / goto) which leaves the associated block.
#
# The following special forms are emitted into the IR:
#
#   (= tok (enter catch_label dynscope))
#     push exception handler with catch block at `catch_label` and dynamic
#     scope `dynscope`, yielding a token which is used by `leave` and
#     `pop_exception`. `dynscope` is only used in the special `tryfinally` form
#     without associated source level syntax (see the `@with` macro)
#
#   (leave tok)
#     pop exception handler back to the state of the `tok` from the associated
#     `enter`. Multiple tokens can be supplied to pop multiple handlers using
#     `(leave tok1 tok2 ...)`.
#
#   (pop_exception tok) - pop exception stack back to state of associated enter
#
# See the devdocs for further discussion.
function compile_try(ctx::LinearIRContext, ex, needs_value, in_tail_pos)
    (try_block, catch_block, else_block, finally_block, catch_label, scope) = @stm ex begin
         [K"trycatchelse" t c] -> (t, c, nothing, nothing, make_label(ctx, c), nothing)
         [K"trycatchelse" t c e] -> (t, c, e, nothing, make_label(ctx, c), nothing)
         [K"tryfinally" t f] -> (t, nothing, nothing, f, make_label(ctx, f), nothing)
         [K"tryfinally" t f scope] -> (t, nothing, nothing, f, make_label(ctx, f), scope)
     end

    has_finally_block = !isnothing(finally_block)
    end_label = !in_tail_pos || has_finally_block ? make_label(ctx, ex) : nothing
    try_result = needs_value && !in_tail_pos ? new_local_binding(ctx, ex, "try_result") : nothing

    enter_scope_arg = SyntaxList()
    if scope !== nothing
        args = SyntaxList()
        push!(args, scope)
        enter_scope_arg = compile_args(ctx, args)
    end
    # Exception handler block prefix
    handler_token = ssavar(ctx, ex, "handler_token")
    emit(ctx, @ast ctx ex [K"="
        handler_token
        [K"enter" catch_label enter_scope_arg...]
    ])
    push!(ctx.handler_token_stack, handler_token)
    if has_finally_block
        # TODO: Trivial finally block optimization from JuliaLang/julia#52593 (or
        # support a special form for @with)?
        finally_handler = FinallyHandler(new_local_binding(ctx, finally_block, "finally_tag"),
                                         JumpTarget(end_label, ctx))
        push!(ctx.finally_handlers, finally_handler)
        emit(ctx, @ast ctx finally_block [K"=" finally_handler.tagvar (-1)::K"Integer"])
    end

    # Try block code.
    try_val = compile(ctx, try_block, needs_value, false)
    # Exception handler block postfix
    if isnothing(else_block)
        if in_tail_pos
            if !isnothing(try_val)
                emit_return(ctx, try_val)
            end
        else
            if needs_value && !isnothing(try_val)
                emit_assignment(ctx, ex, try_result, try_val)
            end
            emit(ctx, @ast ctx ex [K"leave" handler_token])
        end
        pop!(ctx.handler_token_stack)
    else
        if !isnothing(try_val) && (in_tail_pos || needs_value)
            emit(ctx, try_val) # TODO: Only for any side effects ?
        end
        emit(ctx, @ast ctx ex [K"leave" handler_token])
        pop!(ctx.handler_token_stack)
        # Else block code
        else_val = compile(ctx, else_block, needs_value, in_tail_pos)
        if !in_tail_pos
            if needs_value && !isnothing(else_val)
                emit_assignment(ctx, ex, try_result, else_val)
            end
        end
    end
    if !in_tail_pos
        emit(ctx, @ast ctx ex [K"goto" end_label])
    end

    # Catch pad
    # Emit either catch or finally block. A combined try/catch/finally block
    # was split into separate trycatchelse and tryfinally blocks earlier.
    emit(ctx, catch_label) # <- Exceptional control flow enters here
    if has_finally_block
        @assert @isdefined(finally_handler) "compiler hint"
        # Attribute the postfix and prefix to the finally block as a whole.
        srcref = finally_block
        enter_finally_block(ctx, srcref, :rethrow, nothing)
        emit(ctx, end_label) # <- Non-exceptional control flow enters here
        pop!(ctx.finally_handlers)
        compile(ctx, finally_block, false, false)
        # Finally block postfix: Emit a branch for every code path which enters
        # the block to dynamically decide which return/break/rethrow exit action to take
        for (tag, (on_exit, value)) in Iterators.reverse(enumerate(finally_handler.exit_actions))
            next_action_label = !in_tail_pos || tag != 1 || on_exit != :return ?
                make_label(ctx, srcref) : nothing
            if !isnothing(next_action_label)
                tmp = ssavar(ctx, srcref, "do_finally_action")
                emit(ctx, @ast ctx srcref [K"=" tmp
                    [K"call"
                        "==="::K"core"
                        finally_handler.tagvar
                        tag::K"Integer"
                    ]
                ])
                emit(ctx, @ast ctx srcref [K"gotoifnot" tmp next_action_label])
            end
            if on_exit === :return
                emit_return(ctx, value)
            elseif on_exit === :break
                emit_break(ctx, value)
            elseif on_exit === :rethrow
                emit(ctx, @ast ctx srcref [K"call" "rethrow"::K"top"])
            else
                @jl_assert false finally_block
            end
            if !isnothing(next_action_label)
                emit(ctx, next_action_label)
            end
        end
    else
        @assert !isnothing(catch_block)
        push!(ctx.catch_token_stack, handler_token)
        catch_val = compile(ctx, catch_block, needs_value, in_tail_pos)
        if !isnothing(try_result) && !isnothing(catch_val)
            emit_assignment(ctx, ex, try_result, catch_val)
        end
        if !in_tail_pos
            emit(ctx, @ast ctx ex [K"pop_exception" handler_token])
            emit(ctx, end_label)
        else
            # (pop_exception done in emit_return)
        end
        pop!(ctx.catch_token_stack)
    end
    try_result
end

# This pass behaves like an interpreter on the given code.
# To perform stateful operations, it calls `emit` to record that something
# needs to be done. In value position, it returns an expression computing
# the needed value.
function compile(ctx::LinearIRContext, ex, needs_value, in_tail_pos)
    k = kind(ex)
    if k == K"BindingId" || is_literal(k) || k == K"nothing" ||
            k == K"inert" || k == K"syntaxinert" || k == K"top" ||
            k == K"core" || k == K"Value" || k == K"Symbol" ||
            k == K"SourceLocation" || k == K"static_eval" ||
            k == K"foreignsymbol" || k == K"static_parameter"
        ex1 = ex
        if kind(ex1) == K"BindingId"
            binfo = get_binding(ctx, ex1)
            if haskey(ctx.argmap, binfo.id)
                ex1 = newleaf(ex1, K"BindingId", ctx.argmap[binfo.id])
            end
        end
        if in_tail_pos
            emit_return(ctx, ex1)
        elseif needs_value
            ex1
        else
            if k == K"BindingId" && !is_ssa(ctx, ex1)
                emit(ctx, ex1) # keep identifiers for undefined-var checking
            end
            nothing
        end
    elseif k == K"Placeholder"
        if needs_value
            throw(LoweringError(ex, "all-underscore identifiers are write-only and their values cannot be used in expressions"))
        end
        nothing
    elseif k == K"TOMBSTONE"
        @jl_assert !needs_value (ex,"TOMBSTONE encountered in value position")
        nothing
    elseif k == K"call" || k == K"new" || k == K"splatnew" || k == K"foreigncall" ||
            k == K"foreignglobal" || k == K"new_opaque_closure" || k == K"cfunction"
        callex = newnode(ex, k, compile_args(ctx, children(ex)))
        if in_tail_pos
            emit_return(ctx, ex, callex)
        elseif needs_value
            callex
        else
            emit(ctx, callex)
            nothing
        end
    elseif k == K"=" || k == K"constdecl"
        lhs = ex[1]
        res = if kind(lhs) == K"Placeholder"
            compile(ctx, ex[2], needs_value, in_tail_pos)
        elseif k == K"constdecl" && numchildren(ex) == 1
            # No RHS - make undefined constant
            mod, name = if kind(ex[1]) == K"BindingId"
                binfo = get_binding(ctx, ex[1])
                binfo.mod, binfo.name
            else
                @jl_assert kind(ex[1]) == K"Value" && typeof(ex[1].value) === GlobalRef ex
                gr = ex[1].value
                gr.mod, String(gr.name)
            end
            emit(ctx, @ast ctx ex [K"call" "declare_const"::K"core"
                                   mod::K"Value" name::K"Symbol"])
        else
            rhs = compile(ctx, ex[2], true, false)
            if kind(lhs) == K"BindingId"
                binfo = get_binding(ctx, lhs)
                if haskey(ctx.argmap, binfo.id)
                    lhs = newleaf(lhs, K"BindingId", ctx.argmap[binfo.id])
                end
            end
            if needs_value && !isnothing(rhs)
                r = emit_assign_tmp(ctx, rhs)
                emit_simple_assignment(ctx, ex, lhs, r, k)
                if in_tail_pos
                    emit_return(ctx, ex, r)
                else
                    r
                end
            else
                emit_assignment(ctx, ex, lhs, rhs, k)
            end
        end
        k == K"constdecl" && emit_latestworld(ctx, ex)
        res
    elseif k == K"block" || k == K"scope_block"
        nc = numchildren(ex)
        if nc == 0
            if in_tail_pos
                emit_return(ctx, nothing_(ctx, ex))
            elseif needs_value
                nothing_(ctx, ex)
            else
                nothing
            end
        else
            res = nothing
            for i in 1:nc
                islast = i == nc
                res = compile(ctx, ex[i], islast && needs_value, islast && in_tail_pos)
            end
            res
        end
    elseif k == K"symbolicblock"
        name = syntax_name(ex[1])
        # Skip duplicate check for default-scope labels (loop-exit, loop-cont) which allow nesting
        if name != "loop-exit" && name != "loop-cont"
            if haskey(ctx.symbolic_jump_targets, name) || name in ctx.symbolic_block_labels
                throw(LoweringError(ex, "Label `$name` defined multiple times"))
            end
            push!(ctx.symbolic_block_labels, name)
        end
        end_label = make_label(ctx, ex)
        need_value = needs_value || in_tail_pos
        result_var = need_value ? new_local_binding(ctx, ex, "$(name)_result") : nothing
        outer_target = get(ctx.break_targets, name, nothing)
        ctx.break_targets[name] = JumpTarget(end_label, ctx, result_var)
        push!(ctx.break_label_stack, name)
        body_val = compile(ctx, ex[2], need_value, false)
        pop!(ctx.break_label_stack)
        if !isnothing(result_var) && !isnothing(body_val)
            emit_assignment(ctx, ex, result_var, body_val)
        end
        if isnothing(outer_target)
            delete!(ctx.break_targets, name)
        else
            ctx.break_targets[name] = outer_target
        end
        emit(ctx, end_label)
        # Use isdefined to handle the case where initialization was
        # skipped (e.g., by @goto jumping into a loop body).
        if !isnothing(result_var)
            defined_label = make_label(ctx, ex)
            done_label = make_label(ctx, ex)
            isdef = emit_assign_tmp(ctx, @ast ctx ex [K"isdefined" result_var])
            emit(ctx, @ast ctx ex [K"gotoifnot" isdef defined_label])
            emit(ctx, @ast ctx ex [K"goto" done_label])
            emit(ctx, defined_label)
            emit_assignment(ctx, ex, result_var, nothing_(ctx, ex))
            emit(ctx, done_label)
        end
        if in_tail_pos
            emit_return(ctx, ex, result_var)
            nothing
        elseif needs_value
            result_var
        end
    elseif k == K"break"
        emit_break(ctx, ex)
        nothing
    elseif k == K"symboliclabel"
        label = emit_label(ctx, ex)
        name = syntax_name(ex)
        if haskey(ctx.symbolic_jump_targets, name) || name in ctx.symbolic_block_labels
            throw(LoweringError(ex, "Label `$name` defined multiple times"))
        end
        push!(ctx.symbolic_jump_targets, name=>JumpTarget(label, ctx))
        if in_tail_pos
            emit_return(ctx, ex, nothing_(ctx, ex))
        elseif needs_value
            throw(LoweringError(ex, "misplaced label in value position"))
        end
    elseif k == K"symbolicgoto" || k == K"oldsymbolicgoto"
        push!(ctx.symbolic_jump_origins, JumpOrigin(ex, length(ctx.code)+1, ctx))
        emit(ctx, newleaf(ex, K"TOMBSTONE")) # ? pop_exception
        emit(ctx, newleaf(ex, K"TOMBSTONE")) # ? leave
        emit(ctx, newleaf(ex, K"TOMBSTONE")) # ? goto
        nothing
    elseif k == K"return"
        compile(ctx, ex[1], true, true)
        nothing
    elseif k == K"removable"
        if needs_value
            compile(ctx, ex[1], needs_value, in_tail_pos)
        else
            nothing
        end
    elseif k == K"if" || k == K"elseif"
        @jl_assert numchildren(ex) <= 3 ex
        has_else = numchildren(ex) > 2
        else_label = make_label(ctx, ex)
        compile_conditional(ctx, ex[1], else_label)
        if in_tail_pos
            compile(ctx, ex[2], needs_value, in_tail_pos)
            emit(ctx, else_label)
            if has_else
                compile(ctx, ex[3], needs_value, in_tail_pos)
            else
                emit_return(ctx, ex, nothing_(ctx, ex))
            end
            nothing
        else
            val = needs_value && new_local_binding(ctx, ex, "if_val")
            v1 = compile(ctx, ex[2], needs_value, in_tail_pos)
            if needs_value
                emit_assignment(ctx, ex, val, v1)
            end
            if has_else || needs_value
                end_label = make_label(ctx, ex)
                emit(ctx, @ast ctx ex [K"goto" end_label])
            else
                end_label = nothing
            end
            emit(ctx, else_label)
            v2 = if has_else
                compile(ctx, ex[3], needs_value, in_tail_pos)
            elseif needs_value
                nothing_(ctx, ex)
            end
            if needs_value
                emit_assignment(ctx, ex, val, v2)
            end
            if !isnothing(end_label)
                emit(ctx, end_label)
            end
            val
        end
    elseif k == K"trycatchelse" || k == K"tryfinally"
        compile_try(ctx, ex, needs_value, in_tail_pos)
    elseif k == K"method"
        @jl_assert ctx.is_toplevel_thunk (ex, "method not at top level")
        res = if numchildren(ex) == 1
            # Generic function declaration: define_method(module, name)
            func_name = ex[1]
            mod, name = if kind(func_name) == K"BindingId"
                binfo = get_binding(ctx, func_name)
                binfo.mod, binfo.name
            elseif kind(func_name) == K"globalref"
                func_name.mod, syntax_name(func_name)
            else
                ctx.mod, syntax_name(func_name)
            end
            call_ex = @ast ctx ex [K"call" "define_method"::K"core"
                                   mod::K"Value" name::K"Symbol"]
            if in_tail_pos
                emit_return(ctx, call_ex)
            elseif needs_value
                call_ex
            else
                emit(ctx, call_ex)
                nothing
            end
        else
            @jl_assert numchildren(ex) == 3 ex
            fname = ex[1]
            sig = compile(ctx, ex[2], true, false)
            if !is_valid_ir_argument(ctx, sig)
                sig = emit_assign_tmp(ctx, sig)
            end
            lam = ex[3]
            if kind(lam) == K"lambda"
                lam = compile_lambda(ctx, lam)
            else
                lam = emit_assign_tmp(ctx, compile(ctx, lam, true, false))
            end
            emit(ctx, @ast ctx ex [K"call" "define_method"::K"core"
                                   ctx.mod::K"Value" fname sig lam])
        end
        emit_latestworld(ctx, ex)
        res
    elseif k == K"opaque_closure_method"
        @ast ctx ex [K"opaque_closure_method"
            ex[1]
            ex[2]
            ex[3]
            ex[4]
            compile_lambda(ctx, ex[5])
        ]
    elseif k in KSet"lambda generated_lambda toplevel_lambda"
        lam = compile_lambda(ctx, ex)
        if in_tail_pos
            emit_return(ctx, lam)
        elseif needs_value
            lam
        else
            emit(ctx, lam)
        end
    elseif k == K"gc_preserve_begin"
        newnode(ex, k, compile_args(ctx, children(ex)))
    elseif k == K"gc_preserve_end" || k == K"loopinfo"
        if needs_value
            throw(LoweringError(ex, "misplaced kind $k in value position"))
        end
        emit(ctx, ex)
        nothing
    elseif k == K"meta"
        if numchildren(ex) >= 1
            # Certain blessed forms are allowed to share a meta expression;
            # others (nkw, optlevel) treat ex[1] as head and ex[2:end] as args
            if kind(ex[1]) === K"purity" ||
                kind(ex[1]) === K"Symbol" && syntax_name(ex[1]) in (
                    "inline", "noinline", "propagate_inbounds",
                    "nospecializeinfer", "aggressive_constprop", "no_constprop")
                for c in children(ex)
                    if kind(c) === K"purity"
                        old = get(ctx.meta, :purity, UInt16(0))
                        ctx.meta[:purity] = (old | purity_expr_to_flags(c))::UInt16
                    elseif kind(c) === K"Symbol"
                        ctx.meta[Symbol(syntax_name(c))] = true
                    else
                        @jl_assert false c
                    end
                end
            else
                emit(ctx, ex)
            end
        end
        if needs_value
            val = @ast ctx ex (::K"nothing")
            if in_tail_pos
                emit_return(ctx, val)
            else
                val
            end
        end
    elseif k == K"inbounds" || k == K"inbounds_pop" ||
        k == K"inline" || k == K"noinline" || k == K"purity" ||
        k == K"aliasscope" || k == K"popaliasscope"
        emit(ctx, ex) # if absorbed in flags, converted to nothing later
        if needs_value
            val = @ast ctx ex (::K"nothing")
            if in_tail_pos
                emit_return(ctx, val)
            else
                val
            end
        end
    elseif k == K"_while"
        end_label = make_label(ctx, ex)
        top_label = emit_label(ctx, ex)
        compile_conditional(ctx, ex[1], end_label)
        compile(ctx, ex[2], false, false)
        emit(ctx, @ast ctx ex [K"goto" top_label])
        emit(ctx, end_label)
        if needs_value
            compile(ctx, nothing_(ctx, ex), needs_value, in_tail_pos)
        end
    elseif k == K"_do_while"
        end_label = make_label(ctx, ex)
        top_label = emit_label(ctx, ex)
        compile(ctx, ex[1], false, false)
        compile_conditional(ctx, ex[2], end_label)
        emit(ctx, @ast ctx ex [K"goto" top_label])
        emit(ctx, end_label)
        if needs_value
            compile(ctx, nothing_(ctx, ex), needs_value, in_tail_pos)
        end
    elseif k == K"isdefined" || k == K"captured_local" ||
        k == K"throw_undef_if_not" || k == K"boundscheck"
        if in_tail_pos
            emit_return(ctx, ex)
        elseif needs_value
            ex
        end
    elseif k == K"newvar"
        @jl_assert !needs_value ex
        is_duplicate = !isempty(ctx.code) &&
            (e = last(ctx.code); kind(e) == K"newvar" && syntax_id(e[1]) == syntax_id(ex[1]))
        if !is_duplicate
            # TODO: also exclude deleted vars
            emit(ctx, ex)
        end
    elseif k == K"latestworld"
        if needs_value
            throw(LoweringError(ex, "misplaced latestworld"))
        end
        emit_latestworld(ctx, ex)
    elseif k == K"latestworld_if_toplevel"
        ctx.is_toplevel_thunk && emit_latestworld(ctx, ex)
    elseif k == K"unused_only"
        if needs_value && !in_tail_pos
            throw(LoweringError(
                ex, "global declaration doesn't read the variable and can't return a value"))
        end
        if needs_value && in_tail_pos && !ctx.is_toplevel_thunk
            compile(ctx, ex[1], false, false)
            compile(ctx, @ast(ctx, ex, (::K"nothing")), needs_value, in_tail_pos)
        else
            compile(ctx, ex[1], needs_value, in_tail_pos)
        end
    else
        throw(LoweringError(ex, "Invalid syntax; $(repr(k))"))
    end
end

function _remove_vars_with_isdefined_check!(vars, ex)
    if is_leaf(ex) || is_quoted(ex) || kind(ex) == K"static_eval"
        return
    elseif kind(ex) == K"isdefined"
        delete!(vars, syntax_id(ex[1]))
    else
        for e in children(ex)
            _remove_vars_with_isdefined_check!(vars, e)
        end
    end
end

# Find newvar nodes that are unnecessary because
# 1. The variable is not captured and
# 2. The variable is assigned before any branches.
#
# This is used to remove newvar nodes that are not needed for re-initializing
# variables to undefined (see Julia issue #11065). It doesn't look for variable
# *uses*, because any variables used-before-def that also pass this test are
# *always* used undefined, and therefore don't need to be reinitialized. The
# one exception to that is `@isdefined`, which can observe an undefined
# variable without throwing an error.
function unnecessary_newvar_ids(ctx, stmts)
    vars = Set{IdTag}()
    ids_assigned_before_branch = Set{IdTag}()
    for ex in stmts
        _remove_vars_with_isdefined_check!(vars, ex)
        k = kind(ex)
        if k == K"newvar"
            id = syntax_id(ex[1])
            if !get_binding(ctx, id).is_captured
                push!(vars, id)
            end
        elseif k == K"goto" || k == K"gotoifnot" || (k == K"=" && kind(ex[2]) == K"enter")
            empty!(vars)
        elseif k == K"="
            id = syntax_id(ex[1])
            if id in vars
                delete!(vars, id)
                push!(ids_assigned_before_branch, id)
            end
        end
    end
    ids_assigned_before_branch
end

# flisp: compile-body
function compile_body(ctx::LinearIRContext, ex)
    compile(ctx, ex, true, true)

    # Fix up any symbolic gotos. (We can't do this earlier because the goto
    # might precede the label definition in unstructured control flow.)
    for origin in ctx.symbolic_jump_origins
        name = syntax_name(origin.goto)
        target = get(ctx.symbolic_jump_targets, name, nothing)
        if isnothing(target)
            # Check if it's a symbolic block label
            if name in ctx.symbolic_block_labels
                throw(LoweringError(origin.goto, "cannot use @goto to jump to @label block `$name`"))
            end
            throw(LoweringError(origin.goto, "label `$name` referenced but not defined"))
        end
        i = origin.index
        pop_ex = compile_pop_exception(ctx, origin.goto, origin.catch_token_stack,
                                     target.catch_token_stack)
        if !isnothing(pop_ex)
            @jl_assert kind(ctx.code[i]) == K"TOMBSTONE" ctx.code[i]
            ctx.code[i] = pop_ex
            i += 1
        end
        leave_ex = compile_leave_handler(ctx, origin.goto, origin.handler_token_stack,
                                         target.handler_token_stack)
        if !isnothing(leave_ex)
            @jl_assert kind(ctx.code[i]) == K"TOMBSTONE" ctx.code[i]
            ctx.code[i] = leave_ex
            i += 1
        end
        @jl_assert kind(ctx.code[i]) == K"TOMBSTONE" ctx.code[i]
        ctx.code[i] = @ast ctx origin.goto [K"goto" target.label]
    end

    # Filter out unnecessary newvar nodes
    ids_assigned_before_branch = unnecessary_newvar_ids(ctx, ctx.code)
    filter!(ctx.code) do ex
        !(kind(ex) == K"newvar" && syntax_id(ex[1]) in ids_assigned_before_branch)
    end
end

#-------------------------------------------------------------------------------

# Recursively renumber an expression within linear IR
# flisp: renumber-stuff
function _renumber(ctx, ssa_rewrites, slot_rewrites, label_table, ex)
    k = kind(ex)
    if k == K"BindingId"
        id = syntax_id(ex)
        if haskey(ssa_rewrites, id)
            newleaf(ex, K"SSAValue", ssa_rewrites[id])
        else
            new_id = get(slot_rewrites, id, nothing)
            binfo = get_binding(ctx, id)
            if !isnothing(new_id)
                sk = binfo.kind == :local || binfo.kind == :argument ? K"slot"             :
                     binfo.kind == :static_parameter                 ? K"static_parameter" :
                     throw(LoweringError(ex, "Found unexpected binding of kind $(binfo.kind)"))
                newleaf(ex, sk, new_id)
            else
                if binfo.kind !== :global
                    throw(LoweringError(ex, "Found unexpected binding of kind $(binfo.kind)"))
                end
                @mknode(ex; kind=K"globalref", value=binfo.name, mod=binfo.mod)
            end
        end
    elseif k == K"meta" || k == K"static_eval"
        # Somewhat-hack for Expr(:meta, :generated, gen) which has
        # weird top-level semantics for `gen`, but we still need to translate
        # the binding it contains to a globalref. (TODO: use
        # static_eval for this meta, somehow)
        mapchildren(ex) do e
            _renumber(ctx, ssa_rewrites, slot_rewrites, label_table, e)
        end
    elseif is_literal(k) || is_quoted(k)
        ex
    elseif k == K"label"
        @ast ctx ex label_table[syntax_id(ex)]::K"label"
    elseif k == K"code_info"
        ex
    else
        mapchildren(ex) do e
            _renumber(ctx, ssa_rewrites, slot_rewrites, label_table, e)
        end
    end
end

# flisp: renumber-lambda, compact-ir
function renumber_body(ctx, input_code, slot_rewrites)
    # Step 1: Remove any assignments to SSA variables, record the indices of labels
    ssa_rewrites = Dict{IdTag,IdTag}()
    label_table = Dict{Int,Int}()
    code = SyntaxList()
    for ex in input_code
        k = kind(ex)
        ex_out = nothing
        if k == K"=" && (b = get_binding(ctx, ex[1]); b.is_ssa || b.kind == :typevar)
            lhs_id = syntax_id(ex[1])
            @jl_assert(!haskey(ssa_rewrites, lhs_id),
                       (ex, "multiple assignments to ssavalue"))
            @jl_assert ctx.is_toplevel_thunk || b.kind !== :typevar binding_ex(ctx, b)
            if is_ssa(ctx, ex[2])
                # For SSA₁ = SSA₂, record that all uses of SSA₁ should be replaced by SSA₂
                ssa_rewrites[lhs_id] = ssa_rewrites[syntax_id(ex[2])]
            else
                # Otherwise, record which `code` index this SSA value refers to
                ssa_rewrites[lhs_id] = length(code) + 1
                ex_out = ex[2]
            end
        elseif k == K"label"
            label_table[syntax_id(ex)] = length(code) + 1
        elseif k == K"TOMBSTONE"
            # remove statement
        else
            ex_out = ex
        end
        if !isnothing(ex_out)
            push!(code, ex_out)
        end
    end

    # Step 2:
    # * Translate any SSA uses and labels into indices in the code table
    # * Translate locals into slot indices
    for i in 1:length(code)
        code[i] = _renumber(ctx, ssa_rewrites, slot_rewrites, label_table, code[i])
    end
    code
end

struct Slot
    name::String
    kind::Symbol
    is_nospecialize::Bool
    is_read::Bool
    is_single_assign::Bool
    is_maybe_undef::Bool
    is_called::Bool
end

function compile_lambda(outer_ctx, ex)
    k = kind(ex)
    lbs = lambda_bindings(ex[1])
    lambda_args = ex[2]
    static_parameters = ex[3]
    ctx = LinearIRContext(
        outer_ctx, k === K"toplevel_lambda", lbs)
    if numchildren(ex) == 5
        tmp = ssavar(ctx, ex[5], "rett")
        ctx.rettype_ssa[] = tmp
        compile(ctx, @ast(ctx, ex[5], [K"=" tmp ex[5]]), false, false)
    end
    for arg in children(lambda_args)
        kind(arg) == K"Placeholder" && continue
        @jl_assert kind(arg) == K"BindingId" ex
        binfo = get_binding(ctx, arg)
        if binfo.is_assigned
            @jl_assert !haskey(ctx.argmap, binfo.id) ex arg
            ctx.argmap[binfo.id] = syntax_id(new_local_binding(ctx, binding_ex(ctx, binfo), binfo.name))
        end
    end
    compile_body(ctx, ex[4])
    for (id, remapped) in pairs(ctx.argmap)
        binding = binding_ex(ctx, id)
        local_slot = binding_ex(ctx, remapped)
        pushfirst!(ctx.code, @ast ctx binding [K"=" local_slot binding])
    end
    slots = Vector{Slot}()
    slot_rewrites = Dict{IdTag,Int}()
    for arg in children(lambda_args)
        if kind(arg) == K"Placeholder"
            # Unused functions arguments like: `_` or `::T`
            push!(slots, Slot(UNUSED, :argument,
                              getmeta(arg, :nospecialize, false)::Bool,
                              false, false, false, false))
        else
            @jl_assert kind(arg) == K"BindingId" ex arg
            id = syntax_id(arg)
            binfo = get_binding(ctx, id)
            @jl_assert binfo.kind == :local || binfo.kind == :argument ex arg
            push!(slots, Slot(binfo.name, :argument, binfo.is_nospecialize,
                              binfo.is_read, binfo.is_assigned_once,
                              binfo.is_used_undef, binfo.is_called))
            slot_rewrites[id] = length(slots)
        end
    end
    # Sorting the lambda locals is required to remove dependence on Dict iteration order.
    for (id, is_capt) in sort(collect(pairs(lbs.locals_capt)), by=first)
        if !is_capt
            binfo = get_binding(ctx.bindings, id)
            if binfo.kind == :local
                push!(slots, Slot(binfo.name, :local, false,
                                  binfo.is_read, binfo.is_assigned_once,
                                  binfo.is_used_undef, binfo.is_called))
                slot_rewrites[id] = length(slots)
            end
        end
    end
    for (i,arg) in enumerate(children(static_parameters))
        @jl_assert kind(arg) == K"BindingId" arg
        id = syntax_id(arg)
        info = get_binding(ctx.bindings, id)
        @jl_assert info.kind == :static_parameter arg
        slot_rewrites[id] = i
    end
    let ns_slots = SyntaxList()
        for (i, s) in enumerate(slots)
            if s.is_nospecialize
                s.kind === :argument || throw(LoweringError(
                    ex, "nospecialize on non-argument"))
                push!(ns_slots, newleaf(lambda_args[i], K"slot", i))
            end
        end
        if !isempty(ns_slots)
            nargs = numchildren(lambda_args)
            @jl_assert(length(ns_slots) < nargs, ex)
            # all args but self
            length(ns_slots) == nargs - 1 && empty!(ns_slots)
            pushfirst!(ctx.code,
                  @ast ctx lambda_args [K"meta" "nospecialize"::K"Symbol" ns_slots...])
        end
    end
    code = renumber_body(ctx, ctx.code, slot_rewrites)
    meta = CompileHints()
    for (k, v) in ctx.meta
        meta = CompileHints(meta, k, v)
    end
    out = @ast ctx ex [K"code_info"(;meta=meta)
        slots::K"Slots"
        [K"block"(ex[4]) code...]
    ]
    k === K"toplevel_lambda" ? @ast(ctx, ex, [K"thunk" out]) : out
end

"""
This pass converts nested ASTs in the body of a lambda into a list of
statements (ie, Julia's linear/untyped IR).

Most of the complexity of this pass is in lowering structured control flow (if,
loops, etc) to gotos and exception handling to enter/leave. We also convert
`K"BindingId"` into `K"slot"`, `K"globalref"` or `K"SSAValue"` as appropriate.
"""
@fzone "JL: linearize" function linearize_ir(ctx::ClosureConversionCtx, ex)
    ctx_out = LinearIRContext(ctx, false, LambdaBindings())
    ex_out = compile_lambda(ctx_out, ex)
    ctx_out, ex_out
end
