vc4: Do instruction scheduling on the QIR to hide texture fetch latency.

This is a rewrite of vc4_opt_qpu_schedule.c to operate on QIR.  Texture
fetch can probably take as much as the rest of the cycles of the program,
so it's important to hide our other cycles during it (which is hard to do
after register allocation).  Also, we can queue up multiple texture
requests before collecting the resulting samples, so that we keep the
texture unit busy more of the time.

High-settings openarena performance +2.35849% +/- 0.221154% (n=7).  Also
about 2-3% on the multiarb demo.  8 piglit tests
(ext_framebuffer_multisample accuracy depthstencil) go from failing in
rendering to failing in register allocation, but hopefully I can fix that
up with some better register pressure handling here.

total instructions in shared programs: 87723 -> 88448 (0.83%)
instructions in affected programs:     78411 -> 79136 (0.92%)
total estimated cycles in shared programs: 276583 -> 246306 (-10.95%)
estimated cycles in affected programs:     265691 -> 235414 (-11.40%)

4 files changed, 624 insertions, 0 deletions

diff --git a/src/gallium/drivers/vc4/Makefile.sources b/src/gallium/drivers/vc4/Makefile.sources
index 24b577ae9f3..a9a2742ec66 100644
--- a/src/gallium/drivers/vc4/Makefile.sources
+++ b/src/gallium/drivers/vc4/Makefile.sources
@@ -32,6 +32,7 @@ C_SOURCES := \
 	vc4_program.c \
 	vc4_qir.c \
 	vc4_qir_lower_uniforms.c \
+	vc4_qir_schedule.c \
 	vc4_qir.h \
 	vc4_qpu.c \
 	vc4_qpu_defines.h \
diff --git a/src/gallium/drivers/vc4/vc4_program.c b/src/gallium/drivers/vc4/vc4_program.c
index 26bdc9951af..d11c4e3b7ca 100644
--- a/src/gallium/drivers/vc4/vc4_program.c
+++ b/src/gallium/drivers/vc4/vc4_program.c
@@ -1848,12 +1848,15 @@ vc4_shader_ntq(struct vc4_context *vc4, enum qstage stage,
         qir_optimize(c);
         qir_lower_uniforms(c);
 
+        qir_schedule_instructions(c);
+
         if (vc4_debug & VC4_DEBUG_QIR) {
                 fprintf(stderr, "%s prog %d/%d QIR:\n",
                         qir_get_stage_name(c->stage),
                         c->program_id, c->variant_id);
                 qir_dump(c);
         }
+
         qir_reorder_uniforms(c);
         vc4_generate_code(vc4, c);
 
diff --git a/src/gallium/drivers/vc4/vc4_qir.h b/src/gallium/drivers/vc4/vc4_qir.h
index c34dce3aec8..b0fbb4c1db2 100644
--- a/src/gallium/drivers/vc4/vc4_qir.h
+++ b/src/gallium/drivers/vc4/vc4_qir.h
@@ -459,6 +459,7 @@ void qir_remove_instruction(struct vc4_compile *c, struct qinst *qinst);
 struct qreg qir_uniform(struct vc4_compile *c,
                         enum quniform_contents contents,
                         uint32_t data);
+void qir_schedule_instructions(struct vc4_compile *c);
 void qir_reorder_uniforms(struct vc4_compile *c);
 
 void qir_emit(struct vc4_compile *c, struct qinst *inst);
diff --git a/src/gallium/drivers/vc4/vc4_qir_schedule.c b/src/gallium/drivers/vc4/vc4_qir_schedule.c
new file mode 100644
index 00000000000..d20815f055e
--- /dev/null
+++ b/src/gallium/drivers/vc4/vc4_qir_schedule.c
@@ -0,0 +1,619 @@
+/*
+ * 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"
+
+static bool debug;
+
+struct schedule_node {
+        struct list_head link;
+        struct qinst *inst;
+
+        struct schedule_node **children;
+        uint32_t child_count;
+        uint32_t child_array_size;
+        uint32_t parent_count;
+
+        /* 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 {
+        /* List of struct schedule_node *.  This starts out with all
+         * instructions, and after dependency updates it's trimmed to be just
+         * the DAG heads.
+         */
+        struct list_head worklist;
+
+        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 @after must appear after
+ * @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;
+        }
+
+        for (int i = 0; i < after->child_count; i++) {
+                if (after->children[i] == after)
+                        return;
+        }
+
+        if (after->child_array_size <= after->child_count) {
+                after->child_array_size = MAX2(after->child_array_size * 2, 16);
+                after->children = reralloc(after, after->children,
+                                           struct schedule_node *,
+                                           after->child_array_size);
+        }
+
+        after->children[after->child_count] = before;
+        after->child_count++;
+        before->parent_count++;
+}
+
+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;
+        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_op_nsrc(inst->op); 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_S:
+        case QOP_TEX_T:
+        case QOP_TEX_R:
+        case QOP_TEX_B:
+        case QOP_TEX_DIRECT:
+                /* 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;
+
+        case QOP_TEX_RESULT:
+                /* Results have to be fetched in order. */
+                add_write_dep(dir, &state->last_tex_result, n);
+                break;
+
+        case QOP_TLB_COLOR_WRITE:
+        case QOP_TLB_COLOR_READ:
+        case QOP_TLB_Z_WRITE:
+        case QOP_TLB_STENCIL_SETUP:
+        case QOP_MS_MASK:
+                add_write_dep(dir, &state->last_tlb, n);
+                break;
+
+        case QOP_TLB_DISCARD_SETUP:
+                add_write_dep(dir, &state->last_sf, n);
+                add_write_dep(dir, &state->last_tlb, n);
+                break;
+
+        default:
+                break;
+        }
+
+        if (inst->dst.file == QFILE_VPM)
+                add_write_dep(dir, &state->last_vpm_write, n);
+        else if (inst->dst.file == QFILE_TEMP)
+                add_write_dep(dir, &state->last_temp_write[inst->dst.index], n);
+
+        if (inst->sf)
+                add_write_dep(dir, &state->last_sf, n);
+
+        if (qir_depends_on_flags(inst)) {
+                add_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);
+
+                switch (inst->op) {
+                case QOP_TEX_S:
+                case QOP_TEX_T:
+                case QOP_TEX_R:
+                case QOP_TEX_B:
+                case QOP_TEX_DIRECT:
+                        /* If the texture coordinate fifo is full,
+                         * block this on the last QOP_TEX_RESULT.
+                         */
+                        if (state.tfreq_count == 8) {
+                                block_until_tex_result(&state, n);
+                        }
+
+                        /* If the texture result fifo is full, block
+                         * adding any more to it until the last
+                         * QOP_TEX_RESULT.
+                         */
+                        if (inst->op == QOP_TEX_S ||
+                            inst->op == QOP_TEX_DIRECT) {
+                                if (state.tfrcv_count == 4)
+                                        block_until_tex_result(&state, n);
+                                state.tfrcv_count++;
+                        }
+
+                        state.tex_fifo[state.tex_fifo_pos].coords++;
+                        state.tfreq_count++;
+                        break;
+
+                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;
+                default:
+                        assert(!qir_is_tex(inst));
+                        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_op_nsrc(inst->op); i++) {
+                if (inst->src[i].file == QFILE_TEMP &&
+                    !BITSET_TEST(state->temp_live, inst->src[i].index)) {
+                        cost++;
+                }
+        }
+
+        return cost;
+}
+
+static bool
+locks_scoreboard(struct qinst *inst)
+{
+        switch (inst->op) {
+        case QOP_TLB_Z_WRITE:
+        case QOP_TLB_COLOR_WRITE:
+        case QOP_TLB_COLOR_WRITE_MS:
+        case QOP_TLB_COLOR_READ:
+                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->worklist, link) {
+                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 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->worklist, link) {
+                fprintf(stderr, "%3d: ", i++);
+                qir_dump_inst(c, n->inst);
+                fprintf(stderr, " (%d cost)\n",
+                        get_register_pressure_cost(state, n->inst));
+
+                for (int i = 0; i < n->child_count; i++) {
+                        struct schedule_node *child = n->children[i];
+                        fprintf(stderr, "   - ");
+                        qir_dump_inst(c, child->inst);
+                        fprintf(stderr, " (%d parents)\n", child->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->op == QOP_TEX_S ||
+             before->inst->op == QOP_TEX_DIRECT) &&
+            after->inst->op == QOP_TEX_RESULT)
+                return 100;
+
+        return 1;
+}
+
+/** Recursive computation of the delay member of a node. */
+static void
+compute_delay(struct schedule_node *n)
+{
+        if (!n->child_count) {
+                /* 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;
+        } else {
+                for (int i = 0; i < n->child_count; i++) {
+                        if (!n->children[i]->delay)
+                                compute_delay(n->children[i]);
+                        n->delay = MAX2(n->delay,
+                                        n->children[i]->delay +
+                                        latency_between(n, n->children[i]));
+                }
+        }
+}
+
+static void
+schedule_instructions(struct vc4_compile *c, struct schedule_state *state)
+{
+        if (debug) {
+                fprintf(stderr, "initial deps:\n");
+                dump_state(c, state);
+        }
+
+        /* Remove non-DAG heads from the list. */
+        list_for_each_entry_safe(struct schedule_node, n,
+                                 &state->worklist, link) {
+                if (n->parent_count != 0)
+                        list_del(&n->link);
+        }
+
+        state->time = 0;
+        while (!list_empty(&state->worklist)) {
+                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_del(&chosen->link);
+                list_add(&inst->link, &c->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.
+                 */
+                for (int i = chosen->child_count - 1; i >= 0; i--) {
+                        struct schedule_node *child = chosen->children[i];
+
+                        child->unblocked_time = MAX2(child->unblocked_time,
+                                                     state->time +
+                                                     latency_between(chosen,
+                                                                     child));
+                        child->parent_count--;
+                        if (child->parent_count == 0)
+                                list_add(&child->link, &state->worklist);
+                }
+
+                /* Update our tracking of register pressure. */
+                for (int i = 0; i < qir_get_op_nsrc(inst->op); 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++;
+        }
+}
+
+void
+qir_schedule_instructions(struct vc4_compile *c)
+{
+        void *mem_ctx = ralloc_context(NULL);
+        struct schedule_state state = { 0 };
+
+        if (debug) {
+                fprintf(stderr, "Pre-schedule instructions\n");
+                qir_dump(c);
+        }
+
+        state.temp_writes = rzalloc_array(mem_ctx, uint32_t, c->num_temps);
+        state.temp_live = rzalloc_array(mem_ctx, BITSET_WORD,
+                                        BITSET_WORDS(c->num_temps));
+        list_inithead(&state.worklist);
+
+        /* Wrap each instruction in a scheduler structure. */
+        list_for_each_entry_safe(struct qinst, inst, &c->instructions, link) {
+                struct schedule_node *n = rzalloc(mem_ctx, struct schedule_node);
+
+                n->inst = inst;
+                list_del(&inst->link);
+                list_addtail(&n->link, &state.worklist);
+
+                if (inst->dst.file == QFILE_TEMP)
+                        state.temp_writes[inst->dst.index]++;
+        }
+
+        /* Dependencies tracked top-to-bottom. */
+        calculate_forward_deps(c, mem_ctx, &state.worklist);
+        /* Dependencies tracked bottom-to-top. */
+        calculate_reverse_deps(c, mem_ctx, &state.worklist);
+
+        list_for_each_entry(struct schedule_node, n, &state.worklist, link)
+                compute_delay(n);
+
+        schedule_instructions(c, &state);
+
+        if (debug) {
+                fprintf(stderr, "Post-schedule instructions\n");
+                qir_dump(c);
+        }
+
+        ralloc_free(mem_ctx);
+}