util: rename list_empty() to list_is_empty()

[mesa.git] / src / gallium / drivers / vc4 / vc4_qir_schedule.c

/*
 * Copyright © 2010 Intel Corporation
 * Copyright © 2014-2015 Broadcom
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice (including the next
 * paragraph) shall be included in all copies or substantial portions of the
 * Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 * IN THE SOFTWARE.
 */

/**
 * @file vc4_qir_schedule.c
 *
 * The basic model of the list scheduler is to take a basic block, compute a
 * DAG of the dependencies from the bottom up, and make a list of the DAG
 * heads.  Heuristically pick a DAG head and schedule (remove) it, then put
 * all the parents that are now DAG heads into the list of things to
 * schedule.
 *
 * The goal of scheduling here, before register allocation and conversion to
 * QPU instructions, is to reduce register pressure by reordering instructions
 * to consume values when possible.
 */

#include "vc4_qir.h"
#include "util/dag.h"

static bool debug;

struct schedule_node {
        struct dag_node dag;
        struct list_head link;
        struct qinst *inst;

        /* Length of the longest (latency) chain from a DAG head to the this
         * instruction.
         */
        uint32_t delay;

        /* Longest time + latency_between(parent, this) of any parent of this
         * node.
         */
        uint32_t unblocked_time;
};

struct schedule_state {
        struct dag *dag;

        uint32_t time;

        uint32_t *temp_writes;

        BITSET_WORD *temp_live;
};

/* When walking the instructions in reverse, we need to swap before/after in
 * add_dep().
 */
enum direction { F, R };

/**
 * Marks a dependency between two intructions, that \p after must appear after
 * \p before.
 *
 * Our dependencies are tracked as a DAG.  Since we're scheduling bottom-up,
 * the latest instructions with nothing left to schedule are the DAG heads,
 * and their inputs are their children.
 */
static void
add_dep(enum direction dir,
        struct schedule_node *before,
        struct schedule_node *after)
{
        if (!before || !after)
                return;

        assert(before != after);

        if (dir == R) {
                struct schedule_node *t = before;
                before = after;
                after = t;
        }

        dag_add_edge(&after->dag, &before->dag, NULL);
}

static void
add_write_dep(enum direction dir,
              struct schedule_node **before,
              struct schedule_node *after)
{
        add_dep(dir, *before, after);
        *before = after;
}

struct schedule_setup_state {
        struct schedule_node **last_temp_write;
        struct schedule_node *last_sf;
        struct schedule_node *last_vary_read;
        struct schedule_node *last_vpm_read;
        struct schedule_node *last_vpm_write;
        struct schedule_node *last_tex_coord;
        struct schedule_node *last_tex_result;
        struct schedule_node *last_tlb;
        struct schedule_node *last_uniforms_reset;
        enum direction dir;

        /**
         * Texture FIFO tracking.  This is done top-to-bottom, and is used to
         * track the QOP_TEX_RESULTs and add dependencies on previous ones
         * when trying to submit texture coords with TFREQ full or new texture
         * fetches with TXRCV full.
         */
        struct {
                struct schedule_node *node;
                int coords;
        } tex_fifo[8];
        int tfreq_count; /**< Number of texture coords outstanding. */
        int tfrcv_count; /**< Number of texture results outstanding. */
        int tex_fifo_pos;
};

static void
block_until_tex_result(struct schedule_setup_state *state, struct schedule_node *n)
{
        add_dep(state->dir, state->tex_fifo[0].node, n);

        state->tfreq_count -= state->tex_fifo[0].coords;
        state->tfrcv_count--;

        memmove(&state->tex_fifo[0],
                &state->tex_fifo[1],
                state->tex_fifo_pos * sizeof(state->tex_fifo[0]));
        state->tex_fifo_pos--;
}

/**
 * Common code for dependencies that need to be tracked both forward and
 * backward.
 *
 * This is for things like "all VPM reads have to happen in order."
 */
static void
calculate_deps(struct schedule_setup_state *state, struct schedule_node *n)
{
        struct qinst *inst = n->inst;
        enum direction dir = state->dir;


        /* Add deps for temp registers and varyings accesses.  Note that we
         * ignore uniforms accesses, because qir_reorder_uniforms() happens
         * after this.
         */
        for (int i = 0; i < qir_get_nsrc(inst); i++) {
                switch (inst->src[i].file) {
                case QFILE_TEMP:
                        add_dep(dir,
                                state->last_temp_write[inst->src[i].index], n);
                        break;

                case QFILE_VARY:
                        add_write_dep(dir, &state->last_vary_read, n);
                        break;

                case QFILE_VPM:
                        add_write_dep(dir, &state->last_vpm_read, n);
                        break;

                default:
                        break;
                }
        }

        switch (inst->op) {
        case QOP_VARY_ADD_C:
                add_dep(dir, state->last_vary_read, n);
                break;

        case QOP_TEX_RESULT:
                /* Results have to be fetched in order. */
                add_write_dep(dir, &state->last_tex_result, n);
                break;

        case QOP_THRSW:
                /* After a new THRSW, one must collect all texture samples
                 * queued since the previous THRSW/program start.  For now, we
                 * have one THRSW in between each texture setup and its
                 * results collection as our input, and we just make sure that
                 * that ordering is maintained.
                 */
                add_write_dep(dir, &state->last_tex_coord, n);
                add_write_dep(dir, &state->last_tex_result, n);

                /* accumulators and flags are lost across thread switches. */
                add_write_dep(dir, &state->last_sf, n);

                /* Setup, like the varyings, will need to be drained before we
                 * thread switch.
                 */
                add_write_dep(dir, &state->last_vary_read, n);

                /* The TLB-locking operations have to stay after the last
                 * thread switch.
                 */
                add_write_dep(dir, &state->last_tlb, n);
                break;

        case QOP_TLB_COLOR_READ:
        case QOP_MS_MASK:
                add_write_dep(dir, &state->last_tlb, n);
                break;

        default:
                break;
        }

        switch (inst->dst.file) {
        case QFILE_VPM:
                add_write_dep(dir, &state->last_vpm_write, n);
                break;

        case QFILE_TEMP:
                add_write_dep(dir, &state->last_temp_write[inst->dst.index], n);
                break;

        case QFILE_TLB_COLOR_WRITE:
        case QFILE_TLB_COLOR_WRITE_MS:
        case QFILE_TLB_Z_WRITE:
        case QFILE_TLB_STENCIL_SETUP:
                add_write_dep(dir, &state->last_tlb, n);
                break;

        case QFILE_TEX_S_DIRECT:
        case QFILE_TEX_S:
        case QFILE_TEX_T:
        case QFILE_TEX_R:
        case QFILE_TEX_B:
                /* Texturing setup gets scheduled in order, because
                 * the uniforms referenced by them have to land in a
                 * specific order.
                 */
                add_write_dep(dir, &state->last_tex_coord, n);
                break;

        default:
                break;
        }

        if (qir_depends_on_flags(inst))
                add_dep(dir, state->last_sf, n);

        if (inst->sf)
                add_write_dep(dir, &state->last_sf, n);
}

static void
calculate_forward_deps(struct vc4_compile *c, void *mem_ctx,
                       struct list_head *schedule_list)
{
        struct schedule_setup_state state;

        memset(&state, 0, sizeof(state));
        state.last_temp_write = rzalloc_array(mem_ctx, struct schedule_node *,
                                              c->num_temps);
        state.dir = F;

        list_for_each_entry(struct schedule_node, n, schedule_list, link) {
                struct qinst *inst = n->inst;

                calculate_deps(&state, n);

                for (int i = 0; i < qir_get_nsrc(inst); i++) {
                        switch (inst->src[i].file) {
                        case QFILE_UNIF:
                                add_dep(state.dir, state.last_uniforms_reset, n);
                                break;
                        default:
                                break;
                        }
                }

                switch (inst->dst.file) {
                case QFILE_TEX_S_DIRECT:
                case QFILE_TEX_S:
                case QFILE_TEX_T:
                case QFILE_TEX_R:
                case QFILE_TEX_B:
                        /* From the VC4 spec:
                         *
                         *     "The TFREQ input FIFO holds two full lots of s,
                         *      t, r, b data, plus associated setup data, per
                         *      QPU, that is, there are eight data slots. For
                         *      each texture request, slots are only consumed
                         *      for the components of s, t, r, and b actually
                         *      written. Thus the FIFO can hold four requests
                         *      of just (s, t) data, or eight requests of just
                         *      s data (for direct addressed data lookups).
                         *
                         *      Note that there is one FIFO per QPU, and the
                         *      FIFO has no concept of threads - that is,
                         *      multi-threaded shaders must be careful to use
                         *      only 1/2 the FIFO depth before reading
                         *      back. Multi-threaded programs must also
                         *      therefore always thread switch on texture
                         *      fetch as the other thread may have data
                         *      waiting in the FIFO."
                         *
                         * If the texture coordinate fifo is full, block this
                         * on the last QOP_TEX_RESULT.
                         */
                        if (state.tfreq_count == (c->fs_threaded ? 4 : 8)) {
                                block_until_tex_result(&state, n);
                        }

                        /* From the VC4 spec:
                         *
                         *     "Since the maximum number of texture requests
                         *      in the input (TFREQ) FIFO is four lots of (s,
                         *      t) data, the output (TFRCV) FIFO is sized to
                         *      holds four lots of max-size color data per
                         *      QPU. For non-float color, reads are packed
                         *      RGBA8888 data (one read per pixel). For 16-bit
                         *      float color, two reads are necessary per
                         *      pixel, with reads packed as RG1616 then
                         *      BA1616. So per QPU there are eight color slots
                         *      in the TFRCV FIFO."
                         *
                         * If the texture result fifo is full, block adding
                         * any more to it until the last QOP_TEX_RESULT.
                         */
                        if (inst->dst.file == QFILE_TEX_S ||
                            inst->dst.file == QFILE_TEX_S_DIRECT) {
                                if (state.tfrcv_count ==
                                    (c->fs_threaded ? 2 : 4))
                                        block_until_tex_result(&state, n);
                                state.tfrcv_count++;
                        }

                        state.tex_fifo[state.tex_fifo_pos].coords++;
                        state.tfreq_count++;
                        break;

                default:
                        break;
                }

                switch (inst->op) {
                case QOP_TEX_RESULT:
                        /* Results have to be fetched after the
                         * coordinate setup.  Note that we're assuming
                         * here that our input shader has the texture
                         * coord setup and result fetch in order,
                         * which is true initially but not of our
                         * instruction stream after this pass.
                         */
                        add_dep(state.dir, state.last_tex_coord, n);

                        state.tex_fifo[state.tex_fifo_pos].node = n;

                        state.tex_fifo_pos++;
                        memset(&state.tex_fifo[state.tex_fifo_pos], 0,
                               sizeof(state.tex_fifo[0]));
                        break;

                case QOP_UNIFORMS_RESET:
                        add_write_dep(state.dir, &state.last_uniforms_reset, n);
                        break;

                default:
                        break;
                }
        }
}

static void
calculate_reverse_deps(struct vc4_compile *c, void *mem_ctx,
                       struct list_head *schedule_list)
{
        struct schedule_setup_state state;

        memset(&state, 0, sizeof(state));
        state.dir = R;
        state.last_temp_write = rzalloc_array(mem_ctx, struct schedule_node *,
                                              c->num_temps);

        list_for_each_entry_rev(struct schedule_node, n, schedule_list, link) {
                calculate_deps(&state, n);
        }
}

static int
get_register_pressure_cost(struct schedule_state *state, struct qinst *inst)
{
        int cost = 0;

        if (inst->dst.file == QFILE_TEMP &&
            state->temp_writes[inst->dst.index] == 1)
                cost--;

        for (int i = 0; i < qir_get_nsrc(inst); i++) {
                if (inst->src[i].file != QFILE_TEMP ||
                    BITSET_TEST(state->temp_live, inst->src[i].index)) {
                        continue;
                }

                bool already_counted = false;
                for (int j = 0; j < i; j++) {
                        if (inst->src[i].file == inst->src[j].file &&
                            inst->src[i].index == inst->src[j].index) {
                                already_counted = true;
                        }
                }
                if (!already_counted)
                        cost++;
        }

        return cost;
}

static bool
locks_scoreboard(struct qinst *inst)
{
        if (inst->op == QOP_TLB_COLOR_READ)
                return true;

        switch (inst->dst.file) {
        case QFILE_TLB_Z_WRITE:
        case QFILE_TLB_COLOR_WRITE:
        case QFILE_TLB_COLOR_WRITE_MS:
                return true;
        default:
                return false;
        }
}

static struct schedule_node *
choose_instruction(struct schedule_state *state)
{
        struct schedule_node *chosen = NULL;

        list_for_each_entry(struct schedule_node, n, &state->dag->heads,
                            dag.link) {
                /* The branches aren't being tracked as dependencies.  Make
                 * sure that they stay scheduled as the last instruction of
                 * the block, which is to say the first one we choose to
                 * schedule.
                 */
                if (n->inst->op == QOP_BRANCH)
                        return n;

                if (!chosen) {
                        chosen = n;
                        continue;
                }

                /* Prefer scheduling things that lock the scoreboard, so that
                 * they appear late in the program and we get more parallelism
                 * between shaders on multiple QPUs hitting the same fragment.
                 */
                if (locks_scoreboard(n->inst) &&
                    !locks_scoreboard(chosen->inst)) {
                        chosen = n;
                        continue;
                } else if (!locks_scoreboard(n->inst) &&
                           locks_scoreboard(chosen->inst)) {
                        continue;
                }

                /* If we would block on the previously chosen node, but would
                 * block less on this one, then prefer it.
                 */
                if (chosen->unblocked_time > state->time &&
                    n->unblocked_time < chosen->unblocked_time) {
                        chosen = n;
                        continue;
                } else if (n->unblocked_time > state->time &&
                           n->unblocked_time > chosen->unblocked_time) {
                        continue;
                }

                /* If we can definitely reduce register pressure, do so
                 * immediately.
                 */
                int register_pressure_cost =
                        get_register_pressure_cost(state, n->inst);
                int chosen_register_pressure_cost =
                        get_register_pressure_cost(state, chosen->inst);

                if (register_pressure_cost < chosen_register_pressure_cost) {
                        chosen = n;
                        continue;
                } else if (register_pressure_cost >
                           chosen_register_pressure_cost) {
                        continue;
                }

                /* Otherwise, prefer instructions with the deepest chain to
                 * the end of the program.  This avoids the problem of
                 * "everything generates a temp, nothing finishes freeing one,
                 * guess I'll just keep emitting varying mul/adds".
                 */
                if (n->delay > chosen->delay) {
                        chosen = n;
                        continue;
                } else if (n->delay < chosen->delay) {
                        continue;
                }
        }

        return chosen;
}

static void
dump_state(struct vc4_compile *c, struct schedule_state *state)
{
        uint32_t i = 0;
        list_for_each_entry(struct schedule_node, n, &state->dag->heads,
                            dag.link) {
                fprintf(stderr, "%3d: ", i++);
                qir_dump_inst(c, n->inst);
                fprintf(stderr, " (%d cost)\n",
                        get_register_pressure_cost(state, n->inst));

                util_dynarray_foreach(&n->dag.edges, struct dag_edge, edge) {
                        struct schedule_node *child =
                                (struct schedule_node *)edge->child;
                        fprintf(stderr, "   - ");
                        qir_dump_inst(c, child->inst);
                        fprintf(stderr, " (%d parents)\n",
                                child->dag.parent_count);
                }
        }
}

/* Estimate of how many instructions we should schedule between operations.
 *
 * These aren't in real cycle counts, because we're just estimating cycle
 * times anyway.  QIR instructions will get paired up when turned into QPU
 * instructions, or extra NOP delays will have to be added due to register
 * allocation choices.
 */
static uint32_t
latency_between(struct schedule_node *before, struct schedule_node *after)
{
        if ((before->inst->dst.file == QFILE_TEX_S ||
             before->inst->dst.file == QFILE_TEX_S_DIRECT) &&
            after->inst->op == QOP_TEX_RESULT)
                return 100;

        switch (before->inst->op) {
        case QOP_RCP:
        case QOP_RSQ:
        case QOP_EXP2:
        case QOP_LOG2:
                for (int i = 0; i < qir_get_nsrc(after->inst); i++) {
                        if (after->inst->src[i].file ==
                            before->inst->dst.file &&
                            after->inst->src[i].index ==
                            before->inst->dst.index) {
                                /* There are two QPU delay slots before we can
                                 * read a math result, which could be up to 4
                                 * QIR instructions if they packed well.
                                 */
                                return 4;
                        }
                }
                break;
        default:
                break;
        }

        return 1;
}

/** Recursive computation of the delay member of a node. */
static void
compute_delay(struct dag_node *node, void *state)
{
        struct schedule_node *n = (struct schedule_node *)node;

        /* The color read needs to be scheduled late, to avoid locking the
         * scoreboard early.  This is our best tool for encouraging that.  The
         * other scoreboard locking ops will have this happen by default,
         * since they are generally the DAG heads or close to them.
         */
        if (n->inst->op == QOP_TLB_COLOR_READ)
                n->delay = 1000;
        else
                n->delay = 1;

        util_dynarray_foreach(&n->dag.edges, struct dag_edge, edge) {
                struct schedule_node *child =
                        (struct schedule_node *)edge->child;

                n->delay = MAX2(n->delay, (child->delay +
                                           latency_between(child, n)));
        }
}

static void
schedule_instructions(struct vc4_compile *c,
                      struct qblock *block, struct schedule_state *state)
{
        if (debug) {
                fprintf(stderr, "initial deps:\n");
                dump_state(c, state);
        }

        state->time = 0;
        while (!list_is_empty(&state->dag->heads)) {
                struct schedule_node *chosen = choose_instruction(state);
                struct qinst *inst = chosen->inst;

                if (debug) {
                        fprintf(stderr, "current list:\n");
                        dump_state(c, state);
                        fprintf(stderr, "chose: ");
                        qir_dump_inst(c, inst);
                        fprintf(stderr, " (%d cost)\n",
                                get_register_pressure_cost(state, inst));
                }

                state->time = MAX2(state->time, chosen->unblocked_time);

                /* Schedule this instruction back onto the QIR list. */
                list_add(&inst->link, &block->instructions);

                /* Now that we've scheduled a new instruction, some of its
                 * children can be promoted to the list of instructions ready to
                 * be scheduled.  Update the children's unblocked time for this
                 * DAG edge as we do so.
                 */
                util_dynarray_foreach(&chosen->dag.edges,
                                      struct dag_edge, edge) {
                        struct schedule_node *child =
                                (struct schedule_node *)edge->child;

                        child->unblocked_time = MAX2(child->unblocked_time,
                                                     state->time +
                                                     latency_between(child,
                                                                     chosen));
                }
                dag_prune_head(state->dag, &chosen->dag);

                /* Update our tracking of register pressure. */
                for (int i = 0; i < qir_get_nsrc(inst); i++) {
                        if (inst->src[i].file == QFILE_TEMP)
                                BITSET_SET(state->temp_live, inst->src[i].index);
                }
                if (inst->dst.file == QFILE_TEMP) {
                        state->temp_writes[inst->dst.index]--;
                        if (state->temp_writes[inst->dst.index] == 0)
                                BITSET_CLEAR(state->temp_live, inst->dst.index);
                }

                state->time++;
        }
}

static void
qir_schedule_instructions_block(struct vc4_compile *c,
                                struct qblock *block)
{
        struct schedule_state *state = rzalloc(NULL, struct schedule_state);

        state->temp_writes = rzalloc_array(state, uint32_t, c->num_temps);
        state->temp_live = rzalloc_array(state, BITSET_WORD,
                                         BITSET_WORDS(c->num_temps));
        state->dag = dag_create(state);

        struct list_head setup_list;
        list_inithead(&setup_list);

        /* Wrap each instruction in a scheduler structure. */
        qir_for_each_inst_safe(inst, block) {
                struct schedule_node *n = rzalloc(state, struct schedule_node);

                n->inst = inst;
                list_del(&inst->link);
                list_addtail(&n->link, &setup_list);
                dag_init_node(state->dag, &n->dag);

                if (inst->dst.file == QFILE_TEMP)
                        state->temp_writes[inst->dst.index]++;
        }

        /* Dependencies tracked top-to-bottom. */
        calculate_forward_deps(c, state, &setup_list);
        /* Dependencies tracked bottom-to-top. */
        calculate_reverse_deps(c, state, &setup_list);

        dag_traverse_bottom_up(state->dag, compute_delay, NULL);

        schedule_instructions(c, block, state);

        ralloc_free(state);
}

void
qir_schedule_instructions(struct vc4_compile *c)
{

        if (debug) {
                fprintf(stderr, "Pre-schedule instructions\n");
                qir_dump(c);
        }

        qir_for_each_block(block, c)
                qir_schedule_instructions_block(c, block);

        if (debug) {
                fprintf(stderr, "Post-schedule instructions\n");
                qir_dump(c);
        }
}