/* * Copyright © 2014 Rob Clark * SPDX-License-Identifier: MIT * * Authors: * Rob Clark */ #include "util/dag.h" #include "util/u_math.h" #include "ir3.h" #include "ir3_compiler.h" #if MESA_DEBUG #define SCHED_DEBUG (ir3_shader_debug & IR3_DBG_SCHEDMSGS) #else #define SCHED_DEBUG 0 #endif #define d(fmt, ...) \ do { \ if (SCHED_DEBUG) { \ mesa_logi("SCHED: " fmt, ##__VA_ARGS__); \ } \ } while (0) #define di(instr, fmt, ...) \ do { \ if (SCHED_DEBUG) { \ struct log_stream *stream = mesa_log_streami(); \ mesa_log_stream_printf(stream, "SCHED: " fmt ": ", ##__VA_ARGS__); \ ir3_print_instr_stream(stream, instr); \ mesa_log_stream_destroy(stream); \ } \ } while (0) /* * Instruction Scheduling: * * A block-level pre-RA scheduler, which works by creating a DAG of * instruction dependencies, and heuristically picking a DAG head * (instruction with no unscheduled dependencies). * * Where possible, it tries to pick instructions that avoid nop delay * slots, but it will prefer to pick instructions that reduce (or do * not increase) the number of live values. * * If the only possible choices are instructions that increase the * number of live values, it will try to pick the one with the earliest * consumer (based on pre-sched program order). * * There are a few special cases that need to be handled, since sched * is currently independent of register allocation. Usages of address * register (a0.x) or predicate register (p0.x) must be serialized. Ie. * if you have two pairs of instructions that write the same special * register and then read it, then those pairs cannot be interleaved. * To solve this, when we are in such a scheduling "critical section", * and we encounter a conflicting write to a special register, we try * to schedule any remaining instructions that use that value first. * * TODO we can detect too-large live_values here.. would be a good place * to "spill" cheap things, like move from uniform/immed. (Constructing * list of ssa def consumers before sched pass would make this easier. * Also, in general it is general it might be best not to re-use load_immed * across blocks. * * TODO we can use (abs)/(neg) src modifiers in a lot of cases to reduce * the # of immediates in play (or at least that would help with * dEQP-GLES31.functional.ubo.random.all_per_block_buffers.*).. probably * do this in a nir pass that inserts fneg/etc? The cp pass should fold * these into src modifiers.. */ struct ir3_sched_ctx { struct ir3_compiler *compiler; struct ir3_block *block; /* the current block */ struct dag *dag; struct list_head unscheduled_list; /* unscheduled instructions */ struct ir3_instruction *scheduled; /* last scheduled instr */ struct ir3_instruction *addr0; /* current a0.x user, if any */ struct ir3_instruction *addr1; /* current a1.x user, if any */ struct ir3_instruction *split; /* most-recently-split a0/a1 producer */ int remaining_kills; int remaining_tex; bool error; unsigned ip; int sy_delay; int ss_delay; /* We order the scheduled (sy)/(ss) producers, and keep track of the * index of the last waited on instruction, so we can know which * instructions are still outstanding (and therefore would require us to * wait for all outstanding instructions before scheduling a use). */ int sy_index, first_outstanding_sy_index; int ss_index, first_outstanding_ss_index; }; struct ir3_sched_node { struct dag_node dag; /* must be first for util_dynarray_foreach */ struct ir3_instruction *instr; unsigned delay; unsigned max_delay; unsigned sy_index; unsigned ss_index; /* For ready instructions, the earliest possible ip that it could be * scheduled. */ unsigned earliest_ip; /* For instructions that are a meta:collect src, once we schedule * the first src of the collect, the entire vecN is live (at least * from the PoV of the first RA pass.. the 2nd scalar pass can fill * in some of the gaps, but often not all). So we want to help out * RA, and realize that as soon as we schedule the first collect * src, there is no penalty to schedule the remainder (ie. they * don't make additional values live). In fact we'd prefer to * schedule the rest ASAP to minimize the live range of the vecN. * * For instructions that are the src of a collect, we track the * corresponding collect, and mark them as partially live as soon * as any one of the src's is scheduled. */ struct ir3_instruction *collect; bool partially_live; /* Is this instruction a direct or indirect dependency for a kill? * If so, we should prioritize it when possible */ bool kill_path; /* This node represents a shader output. A semi-common pattern in * shaders is something along the lines of: * * fragcolor.w = 1.0 * * Which we'd prefer to schedule as late as possible, since it * produces a live value that is never killed/consumed. So detect * outputs up-front, and avoid scheduling them unless the reduce * register pressure (or at least are neutral) */ bool output; }; #define foreach_sched_node(__n, __list) \ list_for_each_entry (struct ir3_sched_node, __n, __list, dag.link) static void sched_node_init(struct ir3_sched_ctx *ctx, struct ir3_instruction *instr); static void sched_node_add_dep(struct ir3_sched_ctx *ctx, struct ir3_instruction *instr, struct ir3_instruction *src, int i); static bool is_scheduled(struct ir3_instruction *instr) { return !!(instr->flags & IR3_INSTR_MARK); } /* check_src_cond() passing the user and ir3_sched_ctx. */ static bool sched_check_src_cond(struct ir3_instruction *instr, bool (*cond)(struct ir3_instruction *, struct ir3_instruction *, struct ir3_sched_ctx *), struct ir3_sched_ctx *ctx) { foreach_ssa_src (src, instr) { /* meta:split/collect aren't real instructions, the thing that * we actually care about is *their* srcs */ if ((src->opc == OPC_META_SPLIT) || (src->opc == OPC_META_COLLECT)) { if (sched_check_src_cond(src, cond, ctx)) return true; } else { if (cond(src, instr, ctx)) return true; } } return false; } /* Is this a sy producer that hasn't been waited on yet? */ static bool is_outstanding_sy(struct ir3_instruction *instr, struct ir3_instruction *use, struct ir3_sched_ctx *ctx) { if (!is_sy_producer(instr)) return false; /* The sched node is only valid within the same block, we cannot * really say anything about src's from other blocks */ if (instr->block != ctx->block) return true; struct ir3_sched_node *n = instr->data; return n->sy_index >= ctx->first_outstanding_sy_index; } static bool is_outstanding_ss(struct ir3_instruction *instr, struct ir3_instruction *use, struct ir3_sched_ctx *ctx) { if (!needs_ss(ctx->compiler, instr, use)) return false; /* The sched node is only valid within the same block, we cannot * really say anything about src's from other blocks */ if (instr->block != ctx->block) return true; struct ir3_sched_node *n = instr->data; return n->ss_index >= ctx->first_outstanding_ss_index; } static unsigned cycle_count(struct ir3_instruction *instr) { if (instr->opc == OPC_META_COLLECT) { /* Assume that only immed/const sources produce moves */ unsigned n = 0; foreach_src (src, instr) { if (src->flags & (IR3_REG_IMMED | IR3_REG_CONST)) n++; } return n; } else if (is_meta(instr)) { return 0; } else { return 1; } } static void schedule(struct ir3_sched_ctx *ctx, struct ir3_instruction *instr) { assert(ctx->block == instr->block); /* remove from depth list: */ list_delinit(&instr->node); if (writes_addr0(instr)) { assert(ctx->addr0 == NULL); ctx->addr0 = instr; } if (writes_addr1(instr)) { assert(ctx->addr1 == NULL); ctx->addr1 = instr; } instr->flags |= IR3_INSTR_MARK; di(instr, "schedule"); list_addtail(&instr->node, &instr->block->instr_list); ctx->scheduled = instr; if (is_kill_or_demote(instr)) { assert(ctx->remaining_kills > 0); ctx->remaining_kills--; } struct ir3_sched_node *n = instr->data; /* If this instruction is a meta:collect src, mark the remaining * collect srcs as partially live. */ if (n->collect) { foreach_ssa_src (src, n->collect) { if (src->block != instr->block) continue; struct ir3_sched_node *sn = src->data; sn->partially_live = true; } } bool counts_for_delay = is_alu(instr) || is_flow(instr); /* TODO: switch to "cycles". For now try to match ir3_delay. */ unsigned delay_cycles = counts_for_delay ? 1 + instr->repeat : 0; /* We insert any nop's needed to get to earliest_ip, then advance * delay_cycles by scheduling the instruction. */ ctx->ip = MAX2(ctx->ip, n->earliest_ip) + delay_cycles; util_dynarray_foreach (&n->dag.edges, struct dag_edge, edge) { unsigned delay = (unsigned)(uintptr_t)edge->data; struct ir3_sched_node *child = container_of(edge->child, struct ir3_sched_node, dag); child->earliest_ip = MAX2(child->earliest_ip, ctx->ip + delay); } dag_prune_head(ctx->dag, &n->dag); unsigned cycles = cycle_count(instr); if (is_ss_producer(instr)) { ctx->ss_delay = soft_ss_delay(instr); n->ss_index = ctx->ss_index++; } else if (!is_meta(instr) && sched_check_src_cond(instr, is_outstanding_ss, ctx)) { ctx->ss_delay = 0; ctx->first_outstanding_ss_index = ctx->ss_index; } else if (ctx->ss_delay > 0) { ctx->ss_delay -= MIN2(cycles, ctx->ss_delay); } if (is_sy_producer(instr)) { /* NOTE that this isn't an attempt to hide texture fetch latency, * but an attempt to hide the cost of switching to another warp. * If we can, we'd like to try to schedule another texture fetch * before scheduling something that would sync. */ ctx->sy_delay = soft_sy_delay(instr, ctx->block->shader); assert(ctx->remaining_tex > 0); ctx->remaining_tex--; n->sy_index = ctx->sy_index++; } else if (!is_meta(instr) && sched_check_src_cond(instr, is_outstanding_sy, ctx)) { ctx->sy_delay = 0; ctx->first_outstanding_sy_index = ctx->sy_index; } else if (ctx->sy_delay > 0) { ctx->sy_delay -= MIN2(cycles, ctx->sy_delay); } } struct ir3_sched_notes { /* there is at least one kill which could be scheduled, except * for unscheduled bary.f's: */ bool blocked_kill; /* there is at least one instruction that could be scheduled, * except for conflicting address register usage: */ bool addr0_conflict, addr1_conflict; }; static bool should_skip(struct ir3_sched_ctx *ctx, struct ir3_instruction *instr) { if (ctx->remaining_kills && (is_tex(instr) || is_mem(instr))) { /* avoid texture/memory access if we have unscheduled kills * that could make the expensive operation unnecessary. By * definition, if there are remaining kills, and this instr * is not a dependency of a kill, there are other instructions * that we can choose from. */ struct ir3_sched_node *n = instr->data; if (!n->kill_path) return true; } return false; } /* could an instruction be scheduled if specified ssa src was scheduled? */ static bool could_sched(struct ir3_sched_ctx *ctx, struct ir3_instruction *instr, struct ir3_instruction *src) { foreach_ssa_src (other_src, instr) { /* if dependency not scheduled, we aren't ready yet: */ if ((src != other_src) && !is_scheduled(other_src)) { return false; } } /* Instructions not in the current block can never be scheduled. */ if (instr->block != src->block) return false; return !should_skip(ctx, instr); } /* Check if instruction is ok to schedule. Make sure it is not blocked * by use of addr/predicate register, etc. */ static bool check_instr(struct ir3_sched_ctx *ctx, struct ir3_sched_notes *notes, struct ir3_instruction *instr) { assert(!is_scheduled(instr)); if (instr == ctx->split) { /* Don't schedule instructions created by splitting a a0.x/a1.x/p0.x * write until another "normal" instruction has been scheduled. */ return false; } if (should_skip(ctx, instr)) return false; /* For instructions that write address register we need to * make sure there is at least one instruction that uses the * addr value which is otherwise ready. * * NOTE if any instructions use pred register and have other * src args, we would need to do the same for writes_pred().. */ if (writes_addr0(instr)) { struct ir3 *ir = instr->block->shader; bool ready = false; for (unsigned i = 0; (i < ir->a0_users_count) && !ready; i++) { struct ir3_instruction *indirect = ir->a0_users[i]; if (!indirect) continue; if (indirect->address->def != instr->dsts[0]) continue; ready = could_sched(ctx, indirect, instr); } /* nothing could be scheduled, so keep looking: */ if (!ready) return false; } if (writes_addr1(instr)) { struct ir3 *ir = instr->block->shader; bool ready = false; for (unsigned i = 0; (i < ir->a1_users_count) && !ready; i++) { struct ir3_instruction *indirect = ir->a1_users[i]; if (!indirect) continue; if (indirect->address->def != instr->dsts[0]) continue; ready = could_sched(ctx, indirect, instr); } /* nothing could be scheduled, so keep looking: */ if (!ready) return false; } /* if this is a write to address/predicate register, and that * register is currently in use, we need to defer until it is * free: */ if (writes_addr0(instr) && ctx->addr0) { assert(ctx->addr0 != instr); notes->addr0_conflict = true; return false; } if (writes_addr1(instr) && ctx->addr1) { assert(ctx->addr1 != instr); notes->addr1_conflict = true; return false; } /* if the instruction is a kill, we need to ensure *every* * bary.f is scheduled. The hw seems unhappy if the thread * gets killed before the end-input (ei) flag is hit. * * We could do this by adding each bary.f instruction as * virtual ssa src for the kill instruction. But we have * fixed length instr->srcs[]. * * TODO we could handle this by false-deps now, probably. */ if (is_kill_or_demote(instr)) { struct ir3 *ir = instr->block->shader; for (unsigned i = 0; i < ir->baryfs_count; i++) { struct ir3_instruction *baryf = ir->baryfs[i]; if (baryf->flags & IR3_INSTR_UNUSED) continue; if (!is_scheduled(baryf)) { notes->blocked_kill = true; return false; } } } return true; } /* Find the instr->ip of the closest use of an instruction, in * pre-sched order. This isn't going to be the same as post-sched * order, but it is a reasonable approximation to limit scheduling * instructions *too* early. This is mostly to prevent bad behavior * in cases where we have a large number of possible instructions * to choose, to avoid creating too much parallelism (ie. blowing * up register pressure) * * See * dEQP-GLES31.functional.atomic_counter.layout.reverse_offset.inc_dec.8_counters_5_calls_1_thread */ static int nearest_use(struct ir3_instruction *instr) { unsigned nearest = ~0; foreach_ssa_use (use, instr) if (!is_scheduled(use)) nearest = MIN2(nearest, use->ip); /* slight hack.. this heuristic tends to push bary.f's to later * in the shader, closer to their uses. But we actually would * prefer to get these scheduled earlier, to unlock varying * storage for more VS jobs: */ if (is_input(instr)) nearest /= 2; return nearest; } static bool is_only_nonscheduled_use(struct ir3_instruction *instr, struct ir3_instruction *use) { foreach_ssa_use (other_use, instr) { if (other_use != use && !is_scheduled(other_use)) return false; } return true; } static unsigned new_regs(struct ir3_instruction *instr) { unsigned regs = 0; foreach_dst (dst, instr) { if (!is_dest_gpr(dst)) continue; regs += reg_elems(dst); } return regs; } /* find net change to live values if instruction were scheduled: */ static int live_effect(struct ir3_instruction *instr) { struct ir3_sched_node *n = instr->data; int new_live = (n->partially_live || !instr->uses || instr->uses->entries == 0) ? 0 : new_regs(instr); int freed_live = 0; /* if we schedule something that causes a vecN to be live, * then count all it's other components too: */ if (n->collect) new_live *= n->collect->srcs_count; foreach_ssa_src_n (src, n, instr) { if (__is_false_dep(instr, n)) continue; if (instr->block != src->block) continue; if (is_only_nonscheduled_use(src, instr)) freed_live += new_regs(src); } return new_live - freed_live; } /* Determine if this is an instruction that we'd prefer not to schedule * yet, in order to avoid an (ss)/(sy) sync. This is limited by the * ss_delay/sy_delay counters, ie. the more cycles it has been since * the last SFU/tex, the less costly a sync would be, and the number of * outstanding SFU/tex instructions to prevent a blowup in register pressure. */ static bool should_defer(struct ir3_sched_ctx *ctx, struct ir3_instruction *instr) { if (ctx->ss_delay) { if (sched_check_src_cond(instr, is_outstanding_ss, ctx)) return true; } /* We mostly just want to try to schedule another texture fetch * before scheduling something that would (sy) sync, so we can * limit this rule to cases where there are remaining texture * fetches */ if (ctx->sy_delay && ctx->remaining_tex) { if (sched_check_src_cond(instr, is_outstanding_sy, ctx)) return true; } /* Avoid scheduling too many outstanding texture or sfu instructions at * once by deferring further tex/SFU instructions. This both prevents * stalls when the queue of texture/sfu instructions becomes too large, * and prevents unacceptably large increases in register pressure from too * many outstanding texture instructions. */ if (ctx->sy_index - ctx->first_outstanding_sy_index >= 8 && is_sy_producer(instr)) return true; if (ctx->ss_index - ctx->first_outstanding_ss_index >= 8 && is_ss_producer(instr)) return true; return false; } static struct ir3_sched_node *choose_instr_inc(struct ir3_sched_ctx *ctx, struct ir3_sched_notes *notes, bool defer, bool avoid_output); enum choose_instr_dec_rank { DEC_NEUTRAL, DEC_NEUTRAL_READY, DEC_FREED, DEC_FREED_READY, }; static const char * dec_rank_name(enum choose_instr_dec_rank rank) { switch (rank) { case DEC_NEUTRAL: return "neutral"; case DEC_NEUTRAL_READY: return "neutral+ready"; case DEC_FREED: return "freed"; case DEC_FREED_READY: return "freed+ready"; default: return NULL; } } static unsigned node_delay(struct ir3_sched_ctx *ctx, struct ir3_sched_node *n) { return MAX2(n->earliest_ip, ctx->ip) - ctx->ip; } /** * Chooses an instruction to schedule using the Goodman/Hsu (1988) CSR (Code * Scheduling for Register pressure) heuristic. * * Only handles the case of choosing instructions that reduce register pressure * or are even. */ static struct ir3_sched_node * choose_instr_dec(struct ir3_sched_ctx *ctx, struct ir3_sched_notes *notes, bool defer) { const char *mode = defer ? "-d" : ""; struct ir3_sched_node *chosen = NULL; enum choose_instr_dec_rank chosen_rank = DEC_NEUTRAL; foreach_sched_node (n, &ctx->dag->heads) { if (defer && should_defer(ctx, n->instr)) continue; unsigned d = node_delay(ctx, n); int live = live_effect(n->instr); if (live > 0) continue; if (!check_instr(ctx, notes, n->instr)) continue; enum choose_instr_dec_rank rank; if (live < 0) { /* Prioritize instrs which free up regs and can be scheduled with no * delay. */ if (d == 0) rank = DEC_FREED_READY; else rank = DEC_FREED; } else { /* Contra the paper, pick a leader with no effect on used regs. This * may open up new opportunities, as otherwise a single-operand instr * consuming a value will tend to block finding freeing that value. * This had a massive effect on reducing spilling on V3D. * * XXX: Should this prioritize ready? */ if (d == 0) rank = DEC_NEUTRAL_READY; else rank = DEC_NEUTRAL; } /* Prefer higher-ranked instructions, or in the case of a rank tie, the * highest latency-to-end-of-program instruction. */ if (!chosen || rank > chosen_rank || (rank == chosen_rank && chosen->max_delay < n->max_delay)) { chosen = n; chosen_rank = rank; } } if (chosen) { di(chosen->instr, "dec%s: chose (%s)", mode, dec_rank_name(chosen_rank)); return chosen; } return choose_instr_inc(ctx, notes, defer, true); } enum choose_instr_inc_rank { INC_DISTANCE, INC_DISTANCE_READY, }; static const char * inc_rank_name(enum choose_instr_inc_rank rank) { switch (rank) { case INC_DISTANCE: return "distance"; case INC_DISTANCE_READY: return "distance+ready"; default: return NULL; } } /** * When we can't choose an instruction that reduces register pressure or * is neutral, we end up here to try and pick the least bad option. */ static struct ir3_sched_node * choose_instr_inc(struct ir3_sched_ctx *ctx, struct ir3_sched_notes *notes, bool defer, bool avoid_output) { const char *mode = defer ? "-d" : ""; struct ir3_sched_node *chosen = NULL; enum choose_instr_inc_rank chosen_rank = INC_DISTANCE; /* * From hear on out, we are picking something that increases * register pressure. So try to pick something which will * be consumed soon: */ unsigned chosen_distance = 0; /* Pick the max delay of the remaining ready set. */ foreach_sched_node (n, &ctx->dag->heads) { if (avoid_output && n->output) continue; if (defer && should_defer(ctx, n->instr)) continue; if (!check_instr(ctx, notes, n->instr)) continue; unsigned d = node_delay(ctx, n); enum choose_instr_inc_rank rank; if (d == 0) rank = INC_DISTANCE_READY; else rank = INC_DISTANCE; unsigned distance = nearest_use(n->instr); if (!chosen || rank > chosen_rank || (rank == chosen_rank && distance < chosen_distance)) { chosen = n; chosen_distance = distance; chosen_rank = rank; } } if (chosen) { di(chosen->instr, "inc%s: chose (%s)", mode, inc_rank_name(chosen_rank)); return chosen; } return NULL; } /* Handles instruction selections for instructions we want to prioritize * even if csp/csr would not pick them. */ static struct ir3_sched_node * choose_instr_prio(struct ir3_sched_ctx *ctx, struct ir3_sched_notes *notes) { struct ir3_sched_node *chosen = NULL; foreach_sched_node (n, &ctx->dag->heads) { /* * - phi nodes and inputs must be scheduled first * - split should be scheduled first, so that the vector value is * killed as soon as possible. RA cannot split up the vector and * reuse components that have been killed until it's been killed. * - collect, on the other hand, should be treated as a "normal" * instruction, and may add to register pressure if its sources are * part of another vector or immediates. */ if (!is_meta(n->instr) || n->instr->opc == OPC_META_COLLECT) continue; if (!chosen || (chosen->max_delay < n->max_delay)) chosen = n; } if (chosen) { di(chosen->instr, "prio: chose (meta)"); return chosen; } return NULL; } static void dump_state(struct ir3_sched_ctx *ctx) { if (!SCHED_DEBUG) return; foreach_sched_node (n, &ctx->dag->heads) { di(n->instr, "maxdel=%3d le=%d del=%u ", n->max_delay, live_effect(n->instr), node_delay(ctx, n)); util_dynarray_foreach (&n->dag.edges, struct dag_edge, edge) { struct ir3_sched_node *child = (struct ir3_sched_node *)edge->child; di(child->instr, " -> (%d parents) ", child->dag.parent_count); } } } /* find instruction to schedule: */ static struct ir3_instruction * choose_instr(struct ir3_sched_ctx *ctx, struct ir3_sched_notes *notes) { struct ir3_sched_node *chosen; dump_state(ctx); chosen = choose_instr_prio(ctx, notes); if (chosen) return chosen->instr; chosen = choose_instr_dec(ctx, notes, true); if (chosen) return chosen->instr; chosen = choose_instr_dec(ctx, notes, false); if (chosen) return chosen->instr; chosen = choose_instr_inc(ctx, notes, false, false); if (chosen) return chosen->instr; return NULL; } static struct ir3_instruction * split_instr(struct ir3_sched_ctx *ctx, struct ir3_instruction *orig_instr) { struct ir3_instruction *new_instr = ir3_instr_clone(orig_instr); di(new_instr, "split instruction"); sched_node_init(ctx, new_instr); return new_instr; } /* "spill" the address registers by remapping any unscheduled * instructions which depend on the current address register * to a clone of the instruction which wrote the address reg. */ static struct ir3_instruction * split_addr(struct ir3_sched_ctx *ctx, struct ir3_instruction **addr, struct ir3_instruction **users, unsigned users_count) { struct ir3_instruction *new_addr = NULL; unsigned i; assert(*addr); for (i = 0; i < users_count; i++) { struct ir3_instruction *indirect = users[i]; if (!indirect) continue; /* skip instructions already scheduled: */ if (is_scheduled(indirect)) continue; /* remap remaining instructions using current addr * to new addr: */ if (indirect->address->def == (*addr)->dsts[0]) { if (!new_addr) { new_addr = split_instr(ctx, *addr); /* original addr is scheduled, but new one isn't: */ new_addr->flags &= ~IR3_INSTR_MARK; } indirect->address->def = new_addr->dsts[0]; /* don't need to remove old dag edge since old addr is * already scheduled: */ sched_node_add_dep(ctx, indirect, new_addr, 0); di(indirect, "new address"); } } /* all remaining indirects remapped to new addr: */ *addr = NULL; return new_addr; } static void sched_node_init(struct ir3_sched_ctx *ctx, struct ir3_instruction *instr) { struct ir3_sched_node *n = rzalloc(ctx->dag, struct ir3_sched_node); dag_init_node(ctx->dag, &n->dag); n->instr = instr; instr->data = n; } static void sched_node_add_dep(struct ir3_sched_ctx *ctx, struct ir3_instruction *instr, struct ir3_instruction *src, int i) { /* don't consider dependencies in other blocks: */ if (src->block != instr->block) return; /* we could have false-dep's that end up unused: */ if (src->flags & IR3_INSTR_UNUSED) { assert(__is_false_dep(instr, i)); return; } struct ir3_sched_node *n = instr->data; struct ir3_sched_node *sn = src->data; /* If src is consumed by a collect, track that to realize that once * any of the collect srcs are live, we should hurry up and schedule * the rest. */ if (instr->opc == OPC_META_COLLECT) sn->collect = instr; unsigned d_soft = ir3_delayslots(ctx->compiler, src, instr, i, true); unsigned d = ir3_delayslots(ctx->compiler, src, instr, i, false); /* delays from (ss) and (sy) are considered separately and more accurately in * the scheduling heuristic, so ignore it when calculating the ip of * instructions, but do consider it when prioritizing which instructions to * schedule. */ dag_add_edge_max_data(&sn->dag, &n->dag, (uintptr_t)d); n->delay = MAX2(n->delay, d_soft); } static void mark_kill_path(struct ir3_instruction *instr) { struct ir3_sched_node *n = instr->data; if (n->kill_path) { return; } n->kill_path = true; foreach_ssa_src (src, instr) { if (src->block != instr->block) continue; mark_kill_path(src); } } /* Is it an output? */ static bool is_output_collect(struct ir3_instruction *instr) { if (instr->opc != OPC_META_COLLECT) return false; foreach_ssa_use (use, instr) { if (use->opc != OPC_END && use->opc != OPC_CHMASK) return false; } return true; } /* Is it's only use as output? */ static bool is_output_only(struct ir3_instruction *instr) { foreach_ssa_use (use, instr) if (!is_output_collect(use)) return false; return true; } static void sched_node_add_deps(struct ir3_sched_ctx *ctx, struct ir3_instruction *instr) { /* There's nothing to do for phi nodes, since they always go first. And * phi nodes can reference sources later in the same block, so handling * sources is not only unnecessary but could cause problems. */ if (instr->opc == OPC_META_PHI) return; /* Since foreach_ssa_src() already handles false-dep's we can construct * the DAG easily in a single pass. */ foreach_ssa_src_n (src, i, instr) { sched_node_add_dep(ctx, instr, src, i); } /* NOTE that all inputs must be scheduled before a kill, so * mark these to be prioritized as well: */ if (is_kill_or_demote(instr) || is_input(instr)) { mark_kill_path(instr); } if (is_output_only(instr)) { struct ir3_sched_node *n = instr->data; n->output = true; } } static void sched_dag_max_delay_cb(struct dag_node *node, void *state) { struct ir3_sched_node *n = (struct ir3_sched_node *)node; uint32_t max_delay = 0; util_dynarray_foreach (&n->dag.edges, struct dag_edge, edge) { struct ir3_sched_node *child = (struct ir3_sched_node *)edge->child; max_delay = MAX2(child->max_delay, max_delay); } n->max_delay = MAX2(n->max_delay, max_delay + n->delay); } #ifndef NDEBUG static void sched_dag_validate_cb(const struct dag_node *node, void *data) { struct ir3_sched_node *n = (struct ir3_sched_node *)node; ir3_print_instr(n->instr); } #endif static void sched_dag_init(struct ir3_sched_ctx *ctx) { ctx->dag = dag_create(ctx); foreach_instr (instr, &ctx->unscheduled_list) sched_node_init(ctx, instr); #ifndef NDEBUG dag_validate(ctx->dag, sched_dag_validate_cb, NULL); #endif foreach_instr (instr, &ctx->unscheduled_list) sched_node_add_deps(ctx, instr); dag_traverse_bottom_up(ctx->dag, sched_dag_max_delay_cb, NULL); } static void sched_dag_destroy(struct ir3_sched_ctx *ctx) { ralloc_free(ctx->dag); ctx->dag = NULL; } static void sched_block(struct ir3_sched_ctx *ctx, struct ir3_block *block) { ctx->block = block; /* addr/pred writes are per-block: */ ctx->addr0 = NULL; ctx->addr1 = NULL; ctx->sy_delay = 0; ctx->ss_delay = 0; ctx->sy_index = ctx->first_outstanding_sy_index = 0; ctx->ss_index = ctx->first_outstanding_ss_index = 0; /* The terminator has to stay at the end. Instead of trying to set up * dependencies to achieve this, it's easier to just remove it now and add it * back after scheduling. */ struct ir3_instruction *terminator = ir3_block_take_terminator(block); /* move all instructions to the unscheduled list, and * empty the block's instruction list (to which we will * be inserting). */ list_replace(&block->instr_list, &ctx->unscheduled_list); list_inithead(&block->instr_list); sched_dag_init(ctx); ctx->remaining_kills = 0; ctx->remaining_tex = 0; foreach_instr_safe (instr, &ctx->unscheduled_list) { if (is_kill_or_demote(instr)) ctx->remaining_kills++; if (is_sy_producer(instr)) ctx->remaining_tex++; } /* First schedule all meta:input and meta:phi instructions, followed by * tex-prefetch. We want all of the instructions that load values into * registers before the shader starts to go before any other instructions. * But in particular we want inputs to come before prefetches. This is * because a FS's bary_ij input may not actually be live in the shader, * but it should not be scheduled on top of any other input (but can be * overwritten by a tex prefetch) * * Note: Because the first block cannot have predecessors, meta:input and * meta:phi cannot exist in the same block. */ foreach_instr_safe (instr, &ctx->unscheduled_list) if (instr->opc == OPC_META_INPUT || instr->opc == OPC_META_PHI) schedule(ctx, instr); foreach_instr_safe (instr, &ctx->unscheduled_list) if (instr->opc == OPC_META_TEX_PREFETCH) schedule(ctx, instr); foreach_instr_safe (instr, &ctx->unscheduled_list) if (instr->opc == OPC_PUSH_CONSTS_LOAD_MACRO) schedule(ctx, instr); while (!list_is_empty(&ctx->unscheduled_list)) { struct ir3_sched_notes notes = {0}; struct ir3_instruction *instr; instr = choose_instr(ctx, ¬es); if (instr) { unsigned delay = node_delay(ctx, instr->data); d("delay=%u", delay); assert(delay <= 6); schedule(ctx, instr); /* Since we've scheduled a "real" instruction, we can now * schedule any split instruction created by the scheduler again. */ ctx->split = NULL; } else { struct ir3_instruction *new_instr = NULL; struct ir3 *ir = block->shader; /* nothing available to schedule.. if we are blocked on * address/predicate register conflict, then break the * deadlock by cloning the instruction that wrote that * reg: */ if (notes.addr0_conflict) { new_instr = split_addr(ctx, &ctx->addr0, ir->a0_users, ir->a0_users_count); } else if (notes.addr1_conflict) { new_instr = split_addr(ctx, &ctx->addr1, ir->a1_users, ir->a1_users_count); } else { d("unscheduled_list:"); foreach_instr (instr, &ctx->unscheduled_list) di(instr, "unscheduled: "); assert(0); ctx->error = true; return; } if (new_instr) { list_delinit(&new_instr->node); list_addtail(&new_instr->node, &ctx->unscheduled_list); } /* If we produced a new instruction, do not schedule it next to * guarantee progress. */ ctx->split = new_instr; } } sched_dag_destroy(ctx); if (terminator) list_addtail(&terminator->node, &block->instr_list); } int ir3_sched(struct ir3 *ir) { struct ir3_sched_ctx *ctx = rzalloc(NULL, struct ir3_sched_ctx); ctx->compiler = ir->compiler; foreach_block (block, &ir->block_list) { foreach_instr (instr, &block->instr_list) { instr->data = NULL; } } ir3_count_instructions_sched(ir); ir3_clear_mark(ir); ir3_find_ssa_uses(ir, ctx, false); foreach_block (block, &ir->block_list) { sched_block(ctx, block); } int ret = ctx->error ? -1 : 0; ralloc_free(ctx); return ret; } static unsigned get_array_id(struct ir3_instruction *instr) { /* The expectation is that there is only a single array * src or dst, ir3_cp should enforce this. */ foreach_dst (dst, instr) if (dst->flags & IR3_REG_ARRAY) return dst->array.id; foreach_src (src, instr) if (src->flags & IR3_REG_ARRAY) return src->array.id; unreachable("this was unexpected"); } /* does instruction 'prior' need to be scheduled before 'instr'? */ static bool depends_on(struct ir3_instruction *instr, struct ir3_instruction *prior) { /* TODO for dependencies that are related to a specific object, ie * a specific SSBO/image/array, we could relax this constraint to * make accesses to unrelated objects not depend on each other (at * least as long as not declared coherent) */ if (((instr->barrier_class & IR3_BARRIER_EVERYTHING) && prior->barrier_class) || ((prior->barrier_class & IR3_BARRIER_EVERYTHING) && instr->barrier_class)) return true; if (instr->barrier_class & prior->barrier_conflict) { if (!(instr->barrier_class & ~(IR3_BARRIER_ARRAY_R | IR3_BARRIER_ARRAY_W))) { /* if only array barrier, then we can further limit false-deps * by considering the array-id, ie reads/writes to different * arrays do not depend on each other (no aliasing) */ if (get_array_id(instr) != get_array_id(prior)) { return false; } } return true; } return false; } static void add_barrier_deps(struct ir3_block *block, struct ir3_instruction *instr) { struct list_head *prev = instr->node.prev; struct list_head *next = instr->node.next; /* add dependencies on previous instructions that must be scheduled * prior to the current instruction */ while (prev != &block->instr_list) { struct ir3_instruction *pi = list_entry(prev, struct ir3_instruction, node); prev = prev->prev; if (is_meta(pi)) continue; if (instr->barrier_class == pi->barrier_class) { ir3_instr_add_dep(instr, pi); break; } if (depends_on(instr, pi)) ir3_instr_add_dep(instr, pi); } /* add dependencies on this instruction to following instructions * that must be scheduled after the current instruction: */ while (next != &block->instr_list) { struct ir3_instruction *ni = list_entry(next, struct ir3_instruction, node); next = next->next; if (is_meta(ni)) continue; if (instr->barrier_class == ni->barrier_class) { ir3_instr_add_dep(ni, instr); break; } if (depends_on(ni, instr)) ir3_instr_add_dep(ni, instr); } } /* before scheduling a block, we need to add any necessary false-dependencies * to ensure that: * * (1) barriers are scheduled in the right order wrt instructions related * to the barrier * * (2) reads that come before a write actually get scheduled before the * write */ bool ir3_sched_add_deps(struct ir3 *ir) { bool progress = false; foreach_block (block, &ir->block_list) { foreach_instr (instr, &block->instr_list) { if (instr->barrier_class) { add_barrier_deps(block, instr); progress = true; } } } return progress; }