#include "moar.h"
#include "internal.h"
#include <math.h>

#if MVM_JIT_ARCH == MVM_JIT_ARCH_X64
#include "jit/x64/tile_decl.h"
#include "jit/x64/tile_pattern.h"
#endif


#if MVM_JIT_DEBUG
#define _ASSERT(x, f, ...) do { if (!(x)) { MVM_oops(tc, f, __VA_ARGS__); } } while(0)
#else
#define _ASSERT(x, f, ...) do { } while (0)
#endif

struct TileState {
    /* state is junction of applicable tiles */
    MVMint32 state;
    /* rule is number of best applicable tile */
    MVMint32 rule;
    /* template is template of assigned tile */
    const MVMJitTileTemplate *template;
    /* block that ends at this node (or node ref) */
    MVMint32 block;
};

struct TreeTiler {
    MVM_VECTOR_DECL(struct TileState, states);
    MVMJitCompiler *compiler;
    MVMJitTileList *list;
};

/* Make complete tiles. Note that any argument passed is interpreted as an
 * int32. Used primarily for making 'synthetic' tiles introduced by the
 * compiler */
MVMJitTile* MVM_jit_tile_make(MVMThreadContext *tc, MVMJitCompiler *compiler,
                              void *emit, MVMint32 num_args, MVMint32 num_values, ...) {
    MVMJitTile *tile;
    MVMint32 i;
    va_list arglist;
    va_start(arglist, num_values);
    tile = MVM_spesh_alloc(tc, compiler->graph->sg, sizeof(MVMJitTile));
    tile->emit = emit;
    tile->num_refs = num_values;
    for (i = 0; i < num_args; i++) {
        tile->args[i] = va_arg(arglist, MVMint32);
    }
    for (i = 0; i < num_values; i++) {
        tile->values[i] = (MVMint8)va_arg(arglist, MVMint32);
    }
    va_end(arglist);
    return tile;
}

/* Postorder collection of tile states (rulesets) */
static void tile_node(MVMThreadContext *tc, MVMJitTreeTraverser *traverser,
                      MVMJitExprTree *tree, MVMint32 node) {
    struct TreeTiler *tiler      = traverser->data;
    MVMJitExprNode op            = tree->nodes[node];
    const MVMJitExprOpInfo *info = tree->info[node].op_info;
    MVMint32 first_child = node+1;
    MVMint32 nchild      = info->nchild < 0 ? tree->nodes[first_child++] : info->nchild;
    MVMint32 *state_info = NULL;

    switch (op) {
    case MVM_JIT_ALL:
    case MVM_JIT_ANY:
    case MVM_JIT_ARGLIST:
        {
            /* Unary variadic nodes are exactly the same... */
            MVMint32 i;
            for (i = 0; i < nchild; i++) {
                MVMint32 child = tree->nodes[first_child+i];
                state_info = MVM_jit_tile_state_lookup(tc, op, tiler->states[child].state, -1);
                _ASSERT(state_info != NULL, "OOPS, %s can't be tiled with a %s child at position %d",
                        info->name, tree->info[child].op_info->name, i);
            }
            tiler->states[node].state    = state_info[3];
            tiler->states[node].rule     = state_info[4];
        }
        break;
    case MVM_JIT_DO:
    case MVM_JIT_DOV:
        {
            MVMint32 last_child = first_child+nchild-1;
            MVMint32 left_state = tiler->states[tree->nodes[first_child]].state;
            MVMint32 right_state = tiler->states[tree->nodes[last_child]].state;
            state_info = MVM_jit_tile_state_lookup(tc, op, left_state, right_state);
            _ASSERT(state_info != NULL, "Can't tile this DO node %d", node);
            tiler->states[node].state = state_info[3];
            tiler->states[node].rule  = state_info[4];
        }
        break;
    case MVM_JIT_IF:
    case MVM_JIT_IFV:
        {
            MVMint32 cond = tree->nodes[node+1],
                left = tree->nodes[node+2],
                right = tree->nodes[node+3];
            MVMint32 *left_state  = MVM_jit_tile_state_lookup(tc, op, tiler->states[cond].state,
                                                              tiler->states[left].state);
            MVMint32 *right_state = MVM_jit_tile_state_lookup(tc, op, tiler->states[cond].state,
                                                              tiler->states[right].state);
            _ASSERT(left_state != NULL && right_state != NULL,
                    "Inconsistent %s tile state", info->name);
            tiler->states[node].state = left_state[3];
            tiler->states[node].rule  = left_state[4];
        }
        break;
    default:
        {
            if (nchild == 0) {
                state_info = MVM_jit_tile_state_lookup(tc, op, -1, -1);
            } else if (nchild == 1) {
                MVMint32 left = tree->nodes[first_child];
                MVMint32 lstate = tiler->states[left].state;
                state_info = MVM_jit_tile_state_lookup(tc, op, lstate, -1);
            } else if (nchild == 2) {
                MVMint32 left  = tree->nodes[first_child];
                MVMint32 lstate = tiler->states[left].state;
                MVMint32 right = tree->nodes[first_child+1];
                MVMint32 rstate = tiler->states[right].state;
                state_info = MVM_jit_tile_state_lookup(tc, op, lstate, rstate);
            }
            _ASSERT(state_info != NULL, "Tiler table could not find next state for %s\n", info->name);
            tiler->states[node].state = state_info[3];
            tiler->states[node].rule  = state_info[4];
        }
    }
}


/* It may happen that a nodes which is used multiple times is tiled in
 * differrent ways, because it is the parent tile which determines which
 * 'symbol' the child node gets to implement, and hence different parents might
 * decide differently. That may mean the same value will be computed more than
 * once, which could be suboptimal. Still, it is necessary to resolve such
 * conflicts. We do so by generating a new node for the parent node to refer to,
 * leaving the old node as it was. That may cause the tree to grow, which is
 * implemented by realloc. As a result, it is unsafe to take references to tree
 * elements while it is being modified. */

static MVMint32 assign_tile(MVMThreadContext *tc, MVMJitExprTree *tree,
                            MVMJitTreeTraverser *traverser,
                            MVMJitExprNode node, MVMint32 rule_nr) {
    const MVMJitTileTemplate *template = &MVM_jit_tile_templates[rule_nr];
    struct TreeTiler *tiler = traverser->data;

    _ASSERT(rule_nr <= (sizeof(MVM_jit_tile_templates)/sizeof(MVM_jit_tile_templates[0])),
            "Attempt to assign invalid tile rule %d\n", rule_nr);

    if (tiler->states[node].template == NULL || tiler->states[node].template == template ||
        memcmp(template, tiler->states[node].template, sizeof(MVMJitTileTemplate)) == 0) {
        /* happy case, no conflict */
        tiler->states[node].rule     = rule_nr;
        tiler->states[node].template = template;
        return node;
    } else {
        /* resolve conflict by copying this node */
        const MVMJitExprOpInfo *info = tree->info[node].op_info;
        MVMint32 space = (info->nchild < 0 ?
                          2 + tree->nodes[node+1] + info->nargs :
                          1 + info->nchild + info->nargs);
        MVMint32 num   = tree->nodes_num;

        /* NB - we should have an append_during_traversal function
         * because the following is quite a common pattern */

        /* Internal copy; hence no realloc may happen during append, ensure the
         * space is available before the copy */
        MVM_VECTOR_ENSURE_SPACE(tree->nodes, space);
        MVM_VECTOR_APPEND(tree->nodes, tree->nodes + node, space);

        /* Copy the information node as well */
        MVM_VECTOR_ENSURE_SIZE(tree->info, num);
        memcpy(tree->info + num, tree->info + node, sizeof(MVMJitExprNodeInfo));

        /* Also ensure the visits and tiles array are of correct size */
        MVM_VECTOR_ENSURE_SIZE(tiler->states, num);
        MVM_VECTOR_ENSURE_SIZE(traverser->visits, num);

        /* Assign the new tile */
        tiler->states[num].rule     = rule_nr;
        tiler->states[num].template = template;

        /* Return reference to new node */
        return num;
    }
}



/* Preorder propagation of rules downward */
static void select_tiles(MVMThreadContext *tc, MVMJitTreeTraverser *traverser,
                         MVMJitExprTree *tree, MVMint32 node) {

    MVMJitExprNode op    = tree->nodes[node];
    MVMint32 first_child = node+1;
    MVMint32 nchild      = (tree->info[node].op_info->nchild < 0 ?
                            tree->nodes[first_child++] :
                            tree->info[node].op_info->nchild);
    struct TreeTiler *tiler = traverser->data;

    const MVMJitTileTemplate *tile = tiler->states[node].template;
    MVMint32 left_sym = tile->left_sym, right_sym = tile->right_sym;

/* Tile assignment is somewhat precarious due to (among other things), possible
 * reallocation. So let's provide a single macro to do it correctly. */
#define DO_ASSIGN_CHILD(NUM, SYM) do { \
        MVMint32 child     = tree->nodes[first_child+(NUM)]; \
        MVMint32 state     = tiler->states[child].state; \
        MVMint32 rule      = MVM_jit_tile_select_lookup(tc, state, (SYM)); \
        MVMint32 assigned  = assign_tile(tc, tree, traverser, child, rule); \
        tree->nodes[first_child+(NUM)] = assigned; \
    } while(0)

    switch (op) {
    case MVM_JIT_ALL:
    case MVM_JIT_ANY:
    case MVM_JIT_ARGLIST:
        {
            MVMint32 i;
            for (i = 0; i < nchild; i++) {
                DO_ASSIGN_CHILD(i, left_sym);
            }
        }
        break;
    case MVM_JIT_DO:
    case MVM_JIT_DOV:
        {
            MVMint32 i, last_child, last_rule;
            for (i = 0; i < nchild - 1; i++) {
                DO_ASSIGN_CHILD(i, left_sym);
            }
            DO_ASSIGN_CHILD(i, right_sym);
        }
        break;
    case MVM_JIT_IF:
    case MVM_JIT_IFV:
        {
            DO_ASSIGN_CHILD(0, left_sym);
            DO_ASSIGN_CHILD(1, right_sym);
            DO_ASSIGN_CHILD(2, right_sym);
        }
        break;
    case MVM_JIT_GUARD:
        {
            /* tree->nodes[node+2] = the first guard of the before/after pair */
            if (tree->nodes[node+2] != 0) {
                MVMJitTile *tile = MVM_jit_tile_make(tc, tiler->compiler,
                                                     MVM_jit_compile_guard, 1, 0,
                                                     tree->nodes[node+2]);
                /* XXX - request a spare register (necessary for DYMAMIC LABEL
                 * etc). This should be generalized */
                tile->register_spec = MVM_JIT_REGISTER_ANY;
                tile->debug_name    = "(guard :pre)";
                MVM_VECTOR_PUSH(tiler->list->items, tile);
            }
            DO_ASSIGN_CHILD(0, left_sym);
        }
    default:
        {
            _ASSERT(nchild <= 2, "Can't tile %d children of %s", nchild,
                    tree->info[node].op_info->name);
            if (nchild > 0) {
                DO_ASSIGN_CHILD(0, left_sym);
            }
            if (nchild > 1) {
                DO_ASSIGN_CHILD(1, right_sym);
            }
        }
    }
#undef DO_ASSIGN_CHILD
    /* (Currently) we never insert into the tile list here */
}


static void start_basic_block(MVMThreadContext *tc, struct TreeTiler *tiler, MVMint32 node) {
    /* After the last tile of a basic block (e.g. after a branch) or before the
     * first tile of a new basic block (before a label), 'split' off a new basic
     * block from the old one; tag the node with this basic block, so the
     * patchup process can work */
    MVMJitTileList *list = tiler->list;
    MVMint32 tile_idx = list->items_num, block_idx = list->blocks_num;

    MVM_VECTOR_ENSURE_SPACE(list->blocks, 1);
    list->blocks[block_idx].end     = tile_idx;
    list->blocks[block_idx+1].start = tile_idx;
    list->blocks_num++;
    /* associate block with node */
    tiler->states[node].block = block_idx;
}

static void extend_last_block(MVMThreadContext *tc, struct TreeTiler *tiler, MVMint32 node) {
    /* In some cases (ANY in WHEN, ALL in ANY, ANY in ALL) the last basic block
     * of the inner block has functionally the same successors as the outer node
     * block; in this case we can 'extend' this block to include the
     * (unconditional) branch and tag the outer block withthe inner block. This
     * works mostly because the call to extend_last_block follows directly after
     * the start_basic_block by the inner block. */
    MVMJitTileList *list = tiler->list;
    MVMint32 tile_idx = list->items_num, block_idx = list->blocks_num;
    list->blocks[block_idx - 1].end = tile_idx;
    list->blocks[block_idx].start   = tile_idx;
    tiler->states[node].block = block_idx - 1;
}

static void patch_shortcircuit_blocks(MVMThreadContext *tc, struct TreeTiler *tiler, MVMJitExprTree *tree, MVMint32 node, MVMint32 alt) {
    /* Shortcircuit operators (ALL/ANY), are series of tests and conditional
     * jumps to a common label (i.e. basic block). Hence every block associated
     * with a child has two successors, namely the following block (block + 1)
     * or the shortcircuited block (alt). */
    MVMJitTileList *list = tiler->list;
    MVMint32 i, nchild = tree->nodes[node+1];
    for (i = 0; i < nchild; i++) {
        MVMint32 child = tree->nodes[node + 2 + i];
        MVMint32 block = tiler->states[node + 2 + i].block;
        if (tree->nodes[child] == tree->nodes[node]) {
            /* in the case of nested shortcircuit operators, if they are equal
             * they shortcircuit identically, and so all children need to be
             * patched up in the same way */
            patch_shortcircuit_blocks(tc, tiler, tree, child, alt);
        } else if (tree->nodes[child] == MVM_JIT_ALL || tree->nodes[child] == MVM_JIT_ANY) {
            /* unequal nested shortcircuit operators (ALL in ANY or ANY in ALL)
             * have the behaviour that shortcircuit to the next block or at the
             * end shortcircuit to the alternative block. E.g. ANY nested in ALL
             * must jump to the next block (continue tests) or continue testing;
             * after the last block, however, if we reach it we can shortcircuit
             * (in ANY, we only reach it, if nothing was true, in ALL, only if
             * everything was true, and hence one of the ANY is true) */
            patch_shortcircuit_blocks(tc, tiler, tree, child, block + 1);
        }
        list->blocks[block].num_succ = 2;
        list->blocks[block].succ[0] = block + 1;
        list->blocks[block].succ[1] = alt;
    }
}

static void patch_basic_blocks(MVMThreadContext *tc, struct TreeTiler *tiler, MVMJitExprTree *tree, MVMint32 node) {
    /* Postorder assign the successors to blocks associated with nodes */
    MVMJitTileList *list = tiler->list;
    MVMint32 test = tree->nodes[node+1];
    if (tree->nodes[node] == MVM_JIT_WHEN) {
        MVMint32 pre  = tiler->states[node + 1].block;
        MVMint32 post = tiler->states[node + 2].block;
        if (tree->nodes[test] == MVM_JIT_ALL) {
            patch_shortcircuit_blocks(tc, tiler, tree, test, post + 1);
        } else if (tree->nodes[test] == MVM_JIT_ANY) {
            /* ANY will start numbering the blocks and assigning (n+1, pre+1) to
             * each of them; pre+1 is the alternative successor.  */
            patch_shortcircuit_blocks(tc, tiler, tree, test, pre + 1);
        }
        list->blocks[pre].num_succ = 2;
        list->blocks[pre].succ[0] = pre + 1;
        list->blocks[pre].succ[1] = post + 1;
        list->blocks[post].num_succ = 1;
        list->blocks[post].succ[0] = post + 1;
    } else if (tree->nodes[node] == MVM_JIT_IF || tree->nodes[node] == MVM_JIT_IFV) {
        MVMint32 pre  = tiler->states[node + 1].block;
        MVMint32 cond = tiler->states[node + 2].block;
        MVMint32 post = tiler->states[node + 3].block;
        if (tree->nodes[test] == MVM_JIT_ALL) {
            patch_shortcircuit_blocks(tc, tiler, tree, test, cond + 1);
        } else if (tree->nodes[test] == MVM_JIT_ANY) {
            patch_shortcircuit_blocks(tc, tiler, tree, test, pre + 1);
        }
        list->blocks[pre].num_succ = 2;
        list->blocks[pre].succ[0] = pre + 1;
        list->blocks[pre].succ[1] = cond + 1;
        list->blocks[cond].num_succ = 1;
        list->blocks[cond].succ[0] = post + 1;
        list->blocks[post].num_succ = 1;
        list->blocks[post].succ[0] = post + 1;
    }
}

/* Insert labels, compute basic block extents (eventually) */
static void build_blocks(MVMThreadContext *tc, MVMJitTreeTraverser *traverser,
                         MVMJitExprTree *tree, MVMint32 node, MVMint32 i) {
    struct TreeTiler *tiler = traverser->data;
    MVMJitTileList *list    = tiler->list;
    switch (tree->nodes[node]) {
    case MVM_JIT_WHEN:
    {
        MVMint32 when_label = tree->info[node].label;
        if (i == 0) {
            MVMint32 test  = tree->nodes[node+1];
            MVMint32 flag  = tree->nodes[test];
            /* First child is the test */
            if (flag == MVM_JIT_ALL) {
                /* Do nothing, shortcircuit of ALL has skipped the conditional
                   block if necessary */
                MVMint32 last_child = test + tree->nodes[test+1] + 1;
                tiler->states[node+1].block = tiler->states[last_child].block;
            } else if (flag == MVM_JIT_ANY) {
                /* If ANY hasn't short-circuited into the conditional block,
                 * it has failed, so insert an unconditional jump past it */
                MVMint32 any_label = tree->info[test].label;
                MVMJitTile *branch = MVM_jit_tile_make(tc, tiler->compiler, MVM_jit_compile_branch,
                                                       1, 0, when_label);
                MVMJitTile *label  = MVM_jit_tile_make(tc, tiler->compiler, MVM_jit_compile_label,
                                                       1, 0, any_label);
                branch->debug_name = "(branch :fail)";
                label->debug_name  = "(label :success)";
                MVM_VECTOR_PUSH(list->items, branch);
                /* extends last block of ANY to include the unconditional branch */
                extend_last_block(tc, tiler, node + 2 + i);
                MVM_VECTOR_PUSH(list->items, label);
            } else {
                /* Other tests require a conditional branch, but no label */
                MVMJitTile *branch = MVM_jit_tile_make(tc, tiler->compiler, MVM_jit_compile_conditional_branch,
                                                       2, 0, MVM_jit_expr_op_negate_flag(tc, flag), when_label);
                branch->debug_name = "(branch :fail)";
                MVM_VECTOR_PUSH(list->items, branch);
                start_basic_block(tc, tiler, node + 1);
            }
        } else {
            /* after child of WHEN, insert the label */
            MVMJitTile *label = MVM_jit_tile_make(tc, tiler->compiler, MVM_jit_compile_label,
                                                  1, 0, when_label);
            label->debug_name = "(label :fail)";
            start_basic_block(tc, tiler, node + 2);
            MVM_VECTOR_PUSH(list->items, label);
        }
        break;
    }
    case MVM_JIT_ALL:
    {
        MVMint32 test = tree->nodes[node+2+i];
        MVMint32 flag = tree->nodes[test];
        MVMint32 all_label = tree->info[node].label;

        if (flag == MVM_JIT_ALL) {
            /* Nested ALL short-circuits identically */
            MVMint32 last_child = test + 1 + tree->nodes[test + 1];
            tiler->states[node + 2 + i].block = tiler->states[last_child].block;
        } else if (flag == MVM_JIT_ANY) {
            /* If ANY reached it's end, that means it's false. So short-circuit out */
            MVMint32 any_label = tree->info[test].label;
            MVMJitTile *branch = MVM_jit_tile_make(tc, tiler->compiler, MVM_jit_compile_branch, 1, 0, all_label);
            MVMJitTile *label  = MVM_jit_tile_make(tc, tiler->compiler, MVM_jit_compile_label, 1, 0, any_label);
            branch->debug_name = "(branch :fail)   # ALL";
            label->debug_name  = "(label :success) # ANY";
            MVM_VECTOR_PUSH(list->items, branch);
            /* extends last block of ANY to include the unconditional branch */
            extend_last_block(tc, tiler, node + 2 + i);
            /* And if ANY short-circuits we should continue the evaluation of ALL */
            MVM_VECTOR_PUSH(list->items, label);
        } else {
            /* Flag should be negated (ALL = short-circiut unless condition)) */
            MVMJitTile *branch = MVM_jit_tile_make(tc, tiler->compiler,
                                                   MVM_jit_compile_conditional_branch, 2, 0,
                                                   MVM_jit_expr_op_negate_flag(tc, flag), all_label);
            branch->debug_name = "(conditional-branch :fail)";
            MVM_VECTOR_PUSH(list->items, branch);
            start_basic_block(tc, tiler, node + 2 + i);
        }
        break;
    }
    case MVM_JIT_ANY:
    {
        MVMint32 test  = tree->nodes[node+2+i];
        MVMint32 flag  = tree->nodes[test];
        MVMint32 any_label = tree->info[node].label;
        if (flag == MVM_JIT_ALL) {
            /* If ALL reached the end, it must have been succesful, and ANY's
               short-circuit behaviour implies we should branch out */
            MVMint32 all_label = tree->info[test].label;
            MVMJitTile *branch = MVM_jit_tile_make(tc, tiler->compiler, MVM_jit_compile_branch,
                                                   1, 0, any_label);
            MVMJitTile *label  = MVM_jit_tile_make(tc, tiler->compiler, MVM_jit_compile_label,
                                                   1, 0, all_label);
            branch->debug_name = "(branch :success) # ALL";
            label->debug_name  = "(label  :fail) # ANY";
            MVM_VECTOR_PUSH(list->items, branch);
            extend_last_block(tc, tiler, node + 2 + i);
            /* If not succesful, testing should continue (thus ALL must branch
             * into our ANY) */
            MVM_VECTOR_PUSH(list->items, label);
        } else if (flag == MVM_JIT_ANY) {
            /* Nothing to do here, since nested ANY already short-circuits to
               our label */
            MVMint32 last_child = test + 1 + tree->nodes[test + 1];
            tiler->states[node + 2 + i].block = tiler->states[last_child].block;
        } else {
            /* Normal evaluation (ANY = short-circuit if condition) */
            MVMJitTile *branch = MVM_jit_tile_make(tc, tiler->compiler,
                                                   MVM_jit_compile_conditional_branch,
                                                   2, 0, flag, any_label);
            branch->debug_name  = "(branch :success)";
            MVM_VECTOR_PUSH(list->items, branch);
            start_basic_block(tc, tiler, node + 2 + i);
        }
        break;
    }
    case MVM_JIT_IF:
    case MVM_JIT_IFV:
    {
        MVMint32 left_label = tree->info[node].label;
        MVMint32 right_label = left_label + 1;
        if (i == 0) {
            /* after flag child */
            MVMint32 test = tree->nodes[node+1];
            MVMint32 flag = tree->nodes[test];
            if (flag == MVM_JIT_ALL) {
                /* If we reach this code then ALL was true, hence we should
                 * enter the left block, and do nothing */
                MVMint32 last_child = test + 1 + tree->nodes[test + 1];
                tiler->states[node + 1].block = tiler->states[last_child].block;
            } else if (flag == MVM_JIT_ANY) {
                /* We need the branch to the right block and the label for ANY
                 * to jump to enter the left block */
                MVMint32 any_label = tree->info[test].label;
                MVMJitTile *branch = MVM_jit_tile_make(tc, tiler->compiler, MVM_jit_compile_branch,
                                                       1, 0, left_label);
                MVMJitTile *label  = MVM_jit_tile_make(tc, tiler->compiler, MVM_jit_compile_label,
                                                       1, 0, any_label);
                branch->debug_name = "(branch: fail)";
                label->debug_name = "(label :success)";
                MVM_VECTOR_PUSH(list->items, branch);
                extend_last_block(tc, tiler, node + 1);
                MVM_VECTOR_PUSH(list->items, label);
            } else {
                MVMJitTile *branch = MVM_jit_tile_make(tc, tiler->compiler,
                                                       MVM_jit_compile_conditional_branch, 2, 0,
                                                       MVM_jit_expr_op_negate_flag(tc, flag), left_label);
                branch->debug_name = "(conditional-branch: fail)";
                MVM_VECTOR_PUSH(list->items, branch);
                start_basic_block(tc, tiler, node + 1);
            }
        } else if (i == 1) {
            /* between left and right conditional block */
            MVMJitTile *branch = MVM_jit_tile_make(tc, tiler->compiler, MVM_jit_compile_branch,
                                                   1, 0, right_label);
            MVMJitTile *label  = MVM_jit_tile_make(tc, tiler->compiler, MVM_jit_compile_label,
                                                   1, 0, left_label);
            branch->debug_name = "(branch :after)";
            label->debug_name  = "(label :fail)";
            MVM_VECTOR_PUSH(list->items, branch);
            start_basic_block(tc, tiler, node + 2);
            MVM_VECTOR_PUSH(list->items, label);
        } else {
            /* after 'right' conditional block */
            MVMJitTile *label = MVM_jit_tile_make(tc, tiler->compiler, MVM_jit_compile_label,
                                                   1, 0, right_label);
            label->debug_name = "(branch :after)";
            start_basic_block(tc, tiler, node + 3);
            MVM_VECTOR_PUSH(list->items, label);
        }
    }
    default:
        break;
    }
}


static void build_tilelist(MVMThreadContext *tc, MVMJitTreeTraverser *traverser,
                           MVMJitExprTree *tree, MVMint32 node) {
    struct TreeTiler *tiler = traverser->data;
    const MVMJitTileTemplate *template = tiler->states[node].template;
    MVMJitTile *tile;

    /* only need to add 'real' tiles; emit may be null for a definition */
    if (template->expr == NULL)
        return;

    tile = MVM_jit_tile_make_from_template(tc, tiler->compiler, template, tree, node);

    MVM_VECTOR_PUSH(tiler->list->items, tile);
    /* count tne number of refs for ARGLIST */
    if (tile->op == MVM_JIT_ARGLIST) {
        tiler->list->num_arglist_refs += tile->num_refs;
    } else if (tile->op == MVM_JIT_WHEN || tile->op == MVM_JIT_IF ||
               tile->op == MVM_JIT_IFV) {
        /* NB: ALL and ANY also generate basic blocks, but their successors can
         * only be resolved after the conditional construct */
        patch_basic_blocks(tc, tiler, tree, node);
    } else if (tile->op == MVM_JIT_GUARD && tile->args[1] != 0) {
        /* second arg is wrap after (and nonzero if required). Because guard is
         * a 'definition' tile, it's emit is usually NULL, so we can overwrite
         * it to make it a 'real' tile. */
        tile->args[0] = tile->args[1];
        tile->emit    = MVM_jit_compile_guard;
    }
}

/* Create a tile from a template */
MVMJitTile * MVM_jit_tile_make_from_template(MVMThreadContext *tc, MVMJitCompiler *compiler,
                                             const MVMJitTileTemplate *template,
                                             MVMJitExprTree *tree, MVMint32 node) {
    MVMJitTile *tile;
    tile = MVM_spesh_alloc(tc, compiler->graph->sg, sizeof(MVMJitTile));
    tile->emit          = template->emit;
    tile->register_spec = template->register_spec;
    tile->node          = node;
    tile->op            = tree->nodes[node];
    tile->size          = tree->info[node].size;

    /* Assign tile arguments and compute the refering nodes */
    switch (tile->op) {
    case MVM_JIT_IF:
    {
        tile->refs[0] = tree->nodes[node+2];
        tile->refs[1] = tree->nodes[node+3];
        tile->num_refs = 2;
        break;
    }
    case MVM_JIT_ARGLIST:
    {
        /* because arglist needs special-casing and because it will use more
         * than 8 (never mind 4) values, it won't fit into refs, so we're not
         * reading them here */
        tile->num_refs = tree->nodes[node+1];
        break;
    }
    case MVM_JIT_DO:
    {
        MVMint32 nchild  = tree->nodes[node+1];
        tile->refs[0]    = tree->nodes[node+1+nchild];
        tile->num_refs = 1;
        break;
    }
    default:
    {
        MVMint32 i, j, k, num_nodes, value_bitmap;
        MVMJitExprNode buffer[8];
        num_nodes        = MVM_jit_expr_tree_get_nodes(tc, tree, node, template->path, buffer);
        value_bitmap     = template->value_bitmap;
        tile->num_refs   = template->num_refs;
        j = 0;
        k = 0;
        /* splice out args from node refs */
        for (i = 0; i < num_nodes; i++) {
            if (value_bitmap & 1) {
                tile->refs[j++] = buffer[i];
            } else {
                tile->args[k++] = buffer[i];
            }
            value_bitmap >>= 1;
        }
        break;
    }
    }
    tile->debug_name = template->expr;
    return tile;
}

MVMJitTileList * MVM_jit_tile_expr_tree(MVMThreadContext *tc, MVMJitCompiler *compiler, MVMJitExprTree *tree) {
    MVMJitTreeTraverser traverser;
    MVMint32 i;
    struct TreeTiler tiler;

    MVM_VECTOR_INIT(tiler.states, tree->nodes_num);
    traverser.policy = MVM_JIT_TRAVERSER_ONCE;
    traverser.inorder = NULL;
    traverser.preorder = NULL;
    traverser.postorder = &tile_node;
    traverser.data = &tiler;

    MVM_jit_expr_tree_traverse(tc, tree, &traverser);
    /* 'pushdown' of tiles to roots */
    for (i = 0; i < tree->roots_num; i++) {
        MVMint32 node = tree->roots[i];
        assign_tile(tc, tree, &traverser, tree->roots[i], tiler.states[node].rule);
    }

    /* Create serial list of actual tiles which represent the final low-level code */
    tiler.compiler      = compiler;
    tiler.list          = MVM_spesh_alloc(tc, compiler->graph->sg, sizeof(MVMJitTileList));
    tiler.list->tree    = tree;
    tiler.list->num_arglist_refs = 0;

    MVM_VECTOR_INIT(tiler.list->items, tree->nodes_num / 2);
    MVM_VECTOR_INIT(tiler.list->inserts, 0);
    MVM_VECTOR_INIT(tiler.list->blocks, 8);

    traverser.preorder  = &select_tiles;
    traverser.inorder   = &build_blocks;
    traverser.postorder = &build_tilelist;

    MVM_jit_expr_tree_traverse(tc, tree, &traverser);

    MVM_free(tiler.states);

    /* finish last list block */
    {
        MVMint32 last_block = tiler.list->blocks_num++;
        tiler.list->blocks[last_block].end = tiler.list->items_num;
        tiler.list->blocks[last_block].num_succ = 0;
    }

    return tiler.list;
}


static int cmp_tile_insert(const void *p1, const void *p2) {
    const struct MVMJitTileInsert *a = p1, *b = p2;
    return a->position == b->position ?
        a->order - b->order :
        a->position - b->position;
}


void MVM_jit_tile_list_insert(MVMThreadContext *tc, MVMJitTileList *list, MVMJitTile *tile, MVMint32 position, MVMint32 order) {
    struct MVMJitTileInsert i = { position, order, tile };
    MVM_VECTOR_PUSH(list->inserts, i);
}

void MVM_jit_tile_list_edit(MVMThreadContext *tc, MVMJitTileList *list) {
    MVMJitTile **worklist;
    MVMint32 i, j, k, n;
    if (list->inserts_num == 0)
        return;

    /* sort inserted tiles in ascending order */
    qsort(list->inserts, list->inserts_num,
          sizeof(struct MVMJitTileInsert), cmp_tile_insert);

    /* create a new array for the tiles */
    worklist = MVM_malloc((list->items_num + list->inserts_num) * sizeof(MVMJitTile*));

    i = 0; /* items */
    j = 0; /* inserts */
    k = 0; /* output */
    n = 0; /* block */

    while (i < list->items_num) {
        while (j < list->inserts_num &&
               list->inserts[j].position < i) {
            worklist[k++] = list->inserts[j++].tile;
        }
        if (list->blocks[n].end == i) {
            list->blocks[n++].end = k;
            list->blocks[n].start = k;
        }
        worklist[k++] = list->items[i++];
    }
    /* insert all tiles after the last one, if any */
    while (j < list->inserts_num) {
        worklist[k++] = list->inserts[j++].tile;
    }
    list->blocks[n].end = k;

    /* swap old and new list */
    MVM_free(list->items);
    list->items = worklist;
    list->items_num = k;
    list->items_alloc = k;

    /* Cleanup edits buffer */
    MVM_free(list->inserts);
    MVM_VECTOR_INIT(list->inserts, 0);
}

void MVM_jit_tile_list_destroy(MVMThreadContext *tc, MVMJitTileList *list) {
    MVM_free(list->items);
    MVM_free(list->inserts);
    MVM_free(list->blocks);
}