src/amd/compiler/aco_scheduler.cpp

   1 /*
   2  * Copyright © 2018 Valve Corporation
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  21  * IN THE SOFTWARE.
  22  *
  23  */
  24
  25 #include "aco_ir.h"
  26 #include "aco_builder.h"
  27 #include <unordered_set>
  28 #include <algorithm>
  29
  30 #include "vulkan/radv_shader.h" // for radv_nir_compiler_options
  31 #include "amdgfxregs.h"
  32
  33 #define SMEM_WINDOW_SIZE (350 - ctx.num_waves * 35)
  34 #define VMEM_WINDOW_SIZE (1024 - ctx.num_waves * 64)
  35 #define POS_EXP_WINDOW_SIZE 512
  36 #define SMEM_MAX_MOVES (64 - ctx.num_waves * 4)
  37 #define VMEM_MAX_MOVES (128 - ctx.num_waves * 8)
  38 /* creating clauses decreases def-use distances, so make it less aggressive the lower num_waves is */
  39 #define VMEM_CLAUSE_MAX_GRAB_DIST ((ctx.num_waves - 1) * 8)
  40 #define POS_EXP_MAX_MOVES 512
  41
  42 namespace aco {
  43
  44 enum MoveResult {
  45    move_success,
  46    move_fail_ssa,
  47    move_fail_rar,
  48    move_fail_pressure,
  49 };
  50
  51 struct MoveState {
  52    RegisterDemand max_registers;
  53
  54    Block *block;
  55    Instruction *current;
  56    RegisterDemand *register_demand;
  57    bool improved_rar;
  58
  59    std::vector<bool> depends_on;
  60    /* Two are needed because, for downwards VMEM scheduling, one needs to
  61     * exclude the instructions in the clause, since new instructions in the
  62     * clause are not moved past any other instructions in the clause. */
  63    std::vector<bool> RAR_dependencies;
  64    std::vector<bool> RAR_dependencies_clause;
  65
  66    int source_idx;
  67    int insert_idx, insert_idx_clause;
  68    RegisterDemand total_demand, total_demand_clause;
  69
  70    /* for moving instructions before the current instruction to after it */
  71    void downwards_init(int current_idx, bool improved_rar, bool may_form_clauses);
  72    MoveResult downwards_move(bool clause);
  73    void downwards_skip();
  74
  75    /* for moving instructions after the first use of the current instruction upwards */
  76    void upwards_init(int source_idx, bool improved_rar);
  77    bool upwards_check_deps();
  78    void upwards_set_insert_idx(int before);
  79    MoveResult upwards_move();
  80    void upwards_skip();
  81
  82 private:
  83    void downwards_advance_helper();
  84 };
  85
  86 struct sched_ctx {
  87    int16_t num_waves;
  88    int16_t last_SMEM_stall;
  89    int last_SMEM_dep_idx;
  90    MoveState mv;
  91 };
  92
  93 /* This scheduler is a simple bottom-up pass based on ideas from
  94  * "A Novel Lightweight Instruction Scheduling Algorithm for Just-In-Time Compiler"
  95  * from Xiaohua Shi and Peng Guo.
  96  * The basic approach is to iterate over all instructions. When a memory instruction
  97  * is encountered it tries to move independent instructions from above and below
  98  * between the memory instruction and it's first user.
  99  * The novelty is that this scheduler cares for the current register pressure:
 100  * Instructions will only be moved if the register pressure won't exceed a certain bound.
 101  */
 102
 103 template <typename T>
 104 void move_element(T begin_it, size_t idx, size_t before) {
 105     if (idx < before) {
 106         auto begin = std::next(begin_it, idx);
 107         auto end = std::next(begin_it, before);
 108         std::rotate(begin, begin + 1, end);
 109     } else if (idx > before) {
 110         auto begin = std::next(begin_it, before);
 111         auto end = std::next(begin_it, idx + 1);
 112         std::rotate(begin, end - 1, end);
 113     }
 114 }
 115
 116 void MoveState::downwards_advance_helper()
 117 {
 118    source_idx--;
 119    total_demand.update(register_demand[source_idx]);
 120 }
 121
 122 void MoveState::downwards_init(int current_idx, bool improved_rar_, bool may_form_clauses)
 123 {
 124    improved_rar = improved_rar_;
 125    source_idx = current_idx;
 126
 127    insert_idx = current_idx + 1;
 128    insert_idx_clause = current_idx;
 129
 130    total_demand = total_demand_clause = register_demand[current_idx];
 131
 132    std::fill(depends_on.begin(), depends_on.end(), false);
 133    if (improved_rar) {
 134       std::fill(RAR_dependencies.begin(), RAR_dependencies.end(), false);
 135       if (may_form_clauses)
 136          std::fill(RAR_dependencies_clause.begin(), RAR_dependencies_clause.end(), false);
 137    }
 138
 139    for (const Operand& op : current->operands) {
 140       if (op.isTemp()) {
 141          depends_on[op.tempId()] = true;
 142          if (improved_rar && op.isFirstKill())
 143             RAR_dependencies[op.tempId()] = true;
 144       }
 145    }
 146
 147    /* update total_demand/source_idx */
 148    downwards_advance_helper();
 149 }
 150
 151 MoveResult MoveState::downwards_move(bool clause)
 152 {
 153    aco_ptr<Instruction>& instr = block->instructions[source_idx];
 154
 155    for (const Definition& def : instr->definitions)
 156       if (def.isTemp() && depends_on[def.tempId()])
 157          return move_fail_ssa;
 158
 159    /* check if one of candidate's operands is killed by depending instruction */
 160    std::vector<bool>& RAR_deps = improved_rar ? (clause ? RAR_dependencies_clause : RAR_dependencies) : depends_on;
 161    for (const Operand& op : instr->operands) {
 162       if (op.isTemp() && RAR_deps[op.tempId()]) {
 163          // FIXME: account for difference in register pressure
 164          return move_fail_rar;
 165       }
 166    }
 167
 168    if (clause) {
 169       for (const Operand& op : instr->operands) {
 170          if (op.isTemp()) {
 171             depends_on[op.tempId()] = true;
 172             if (op.isFirstKill())
 173                RAR_dependencies[op.tempId()] = true;
 174          }
 175       }
 176    }
 177
 178    int dest_insert_idx = clause ? insert_idx_clause : insert_idx;
 179    RegisterDemand register_pressure = clause ? total_demand_clause : total_demand;
 180
 181    const RegisterDemand candidate_diff = get_live_changes(instr);
 182    const RegisterDemand temp = get_temp_registers(instr);
 183    if (RegisterDemand(register_pressure - candidate_diff).exceeds(max_registers))
 184       return move_fail_pressure;
 185    const RegisterDemand temp2 = get_temp_registers(block->instructions[dest_insert_idx - 1]);
 186    const RegisterDemand new_demand = register_demand[dest_insert_idx - 1] - temp2 + temp;
 187    if (new_demand.exceeds(max_registers))
 188       return move_fail_pressure;
 189
 190    /* move the candidate below the memory load */
 191    move_element(block->instructions.begin(), source_idx, dest_insert_idx);
 192
 193    /* update register pressure */
 194    move_element(register_demand, source_idx, dest_insert_idx);
 195    for (int i = source_idx; i < dest_insert_idx - 1; i++)
 196       register_demand[i] -= candidate_diff;
 197    register_demand[dest_insert_idx - 1] = new_demand;
 198    total_demand_clause -= candidate_diff;
 199    insert_idx_clause--;
 200    if (!clause) {
 201       total_demand -= candidate_diff;
 202       insert_idx--;
 203    }
 204
 205    downwards_advance_helper();
 206    return move_success;
 207 }
 208
 209 void MoveState::downwards_skip()
 210 {
 211    aco_ptr<Instruction>& instr = block->instructions[source_idx];
 212
 213    for (const Operand& op : instr->operands) {
 214       if (op.isTemp()) {
 215          depends_on[op.tempId()] = true;
 216          if (improved_rar && op.isFirstKill()) {
 217             RAR_dependencies[op.tempId()] = true;
 218             RAR_dependencies_clause[op.tempId()] = true;
 219          }
 220       }
 221    }
 222    total_demand_clause.update(register_demand[source_idx]);
 223
 224    downwards_advance_helper();
 225 }
 226
 227 void MoveState::upwards_init(int source_idx_, bool improved_rar_)
 228 {
 229    source_idx = source_idx_;
 230    improved_rar = improved_rar_;
 231
 232    insert_idx = -1;
 233
 234    std::fill(depends_on.begin(), depends_on.end(), false);
 235    std::fill(RAR_dependencies.begin(), RAR_dependencies.end(), false);
 236
 237    for (const Definition& def : current->definitions) {
 238       if (def.isTemp())
 239          depends_on[def.tempId()] = true;
 240    }
 241 }
 242
 243 bool MoveState::upwards_check_deps()
 244 {
 245    aco_ptr<Instruction>& instr = block->instructions[source_idx];
 246    for (const Operand& op : instr->operands) {
 247       if (op.isTemp() && depends_on[op.tempId()])
 248          return false;
 249    }
 250    return true;
 251 }
 252
 253 void MoveState::upwards_set_insert_idx(int before)
 254 {
 255    insert_idx = before;
 256    total_demand = register_demand[before - 1];
 257 }
 258
 259 MoveResult MoveState::upwards_move()
 260 {
 261    assert(insert_idx >= 0);
 262
 263    aco_ptr<Instruction>& instr = block->instructions[source_idx];
 264    for (const Operand& op : instr->operands) {
 265       if (op.isTemp() && depends_on[op.tempId()])
 266          return move_fail_ssa;
 267    }
 268
 269    /* check if candidate uses/kills an operand which is used by a dependency */
 270    for (const Operand& op : instr->operands) {
 271       if (op.isTemp() && (!improved_rar || op.isFirstKill()) && RAR_dependencies[op.tempId()])
 272          return move_fail_rar;
 273    }
 274
 275    /* check if register pressure is low enough: the diff is negative if register pressure is decreased */
 276    const RegisterDemand candidate_diff = get_live_changes(instr);
 277    const RegisterDemand temp = get_temp_registers(instr);
 278    if (RegisterDemand(total_demand + candidate_diff).exceeds(max_registers))
 279       return move_fail_pressure;
 280    const RegisterDemand temp2 = get_temp_registers(block->instructions[insert_idx - 1]);
 281    const RegisterDemand new_demand = register_demand[insert_idx - 1] - temp2 + candidate_diff + temp;
 282    if (new_demand.exceeds(max_registers))
 283       return move_fail_pressure;
 284
 285    /* move the candidate above the insert_idx */
 286    move_element(block->instructions.begin(), source_idx, insert_idx);
 287
 288    /* update register pressure */
 289    move_element(register_demand, source_idx, insert_idx);
 290    for (int i = insert_idx + 1; i <= source_idx; i++)
 291       register_demand[i] += candidate_diff;
 292    register_demand[insert_idx] = new_demand;
 293    total_demand += candidate_diff;
 294
 295    insert_idx++;
 296
 297    total_demand.update(register_demand[source_idx]);
 298    source_idx++;
 299
 300    return move_success;
 301 }
 302
 303 void MoveState::upwards_skip()
 304 {
 305    if (insert_idx >= 0) {
 306       aco_ptr<Instruction>& instr = block->instructions[source_idx];
 307       for (const Definition& def : instr->definitions) {
 308          if (def.isTemp())
 309             depends_on[def.tempId()] = true;
 310       }
 311       for (const Operand& op : instr->operands) {
 312          if (op.isTemp())
 313             RAR_dependencies[op.tempId()] = true;
 314       }
 315       total_demand.update(register_demand[source_idx]);
 316    }
 317
 318    source_idx++;
 319 }
 320
 321 bool is_gs_or_done_sendmsg(const Instruction *instr)
 322 {
 323    if (instr->opcode == aco_opcode::s_sendmsg) {
 324       uint16_t imm = static_cast<const SOPP_instruction*>(instr)->imm;
 325       return (imm & sendmsg_id_mask) == _sendmsg_gs ||
 326              (imm & sendmsg_id_mask) == _sendmsg_gs_done;
 327    }
 328    return false;
 329 }
 330
 331 bool is_done_sendmsg(const Instruction *instr)
 332 {
 333    if (instr->opcode == aco_opcode::s_sendmsg) {
 334       uint16_t imm = static_cast<const SOPP_instruction*>(instr)->imm;
 335       return (imm & sendmsg_id_mask) == _sendmsg_gs_done;
 336    }
 337    return false;
 338 }
 339
 340 memory_sync_info get_sync_info_with_hack(const Instruction* instr)
 341 {
 342    memory_sync_info sync = get_sync_info(instr);
 343    if (instr->format == Format::SMEM && !instr->operands.empty() && instr->operands[0].bytes() == 16) {
 344       // FIXME: currently, it doesn't seem beneficial to omit this due to how our scheduler works
 345       sync.storage = (storage_class)(sync.storage | storage_buffer);
 346       sync.semantics = (memory_semantics)(sync.semantics | semantic_private);
 347    }
 348    return sync;
 349 }
 350
 351 struct memory_event_set {
 352    bool has_control_barrier;
 353
 354    unsigned bar_acquire;
 355    unsigned bar_release;
 356    unsigned bar_classes;
 357
 358    unsigned access_acquire;
 359    unsigned access_release;
 360    unsigned access_relaxed;
 361    unsigned access_atomic;
 362 };
 363
 364 struct hazard_query {
 365    bool contains_spill;
 366    bool contains_sendmsg;
 367    memory_event_set mem_events;
 368    unsigned aliasing_storage; /* storage classes which are accessed (non-SMEM) */
 369    unsigned aliasing_storage_smem; /* storage classes which are accessed (SMEM) */
 370 };
 371
 372 void init_hazard_query(hazard_query *query) {
 373    query->contains_spill = false;
 374    query->contains_sendmsg = false;
 375    memset(&query->mem_events, 0, sizeof(query->mem_events));
 376    query->aliasing_storage = 0;
 377    query->aliasing_storage_smem = 0;
 378 }
 379
 380 void add_memory_event(memory_event_set *set, Instruction *instr, memory_sync_info *sync)
 381 {
 382    set->has_control_barrier |= is_done_sendmsg(instr);
 383    if (instr->opcode == aco_opcode::p_barrier) {
 384       Pseudo_barrier_instruction *bar = static_cast<Pseudo_barrier_instruction*>(instr);
 385       if (bar->sync.semantics & semantic_acquire)
 386          set->bar_acquire |= bar->sync.storage;
 387       if (bar->sync.semantics & semantic_release)
 388          set->bar_release |= bar->sync.storage;
 389       set->bar_classes |= bar->sync.storage;
 390
 391       set->has_control_barrier |= bar->exec_scope > scope_invocation;
 392    }
 393
 394    if (!sync->storage)
 395       return;
 396
 397    if (sync->semantics & semantic_acquire)
 398       set->access_acquire |= sync->storage;
 399    if (sync->semantics & semantic_release)
 400       set->access_release |= sync->storage;
 401
 402    if (!(sync->semantics & semantic_private)) {
 403       if (sync->semantics & semantic_atomic)
 404          set->access_atomic |= sync->storage;
 405       else
 406          set->access_relaxed |= sync->storage;
 407    }
 408 }
 409
 410 void add_to_hazard_query(hazard_query *query, Instruction *instr)
 411 {
 412    if (instr->opcode == aco_opcode::p_spill || instr->opcode == aco_opcode::p_reload)
 413       query->contains_spill = true;
 414    query->contains_sendmsg |= instr->opcode == aco_opcode::s_sendmsg;
 415
 416    memory_sync_info sync = get_sync_info_with_hack(instr);
 417
 418    add_memory_event(&query->mem_events, instr, &sync);
 419
 420    if (!(sync.semantics & semantic_can_reorder)) {
 421       unsigned storage = sync.storage;
 422       /* images and buffer/global memory can alias */ //TODO: more precisely, buffer images and buffer/global memory can alias
 423       if (storage & (storage_buffer | storage_image))
 424          storage |= storage_buffer | storage_image;
 425       if (instr->format == Format::SMEM)
 426          query->aliasing_storage_smem |= storage;
 427       else
 428          query->aliasing_storage |= storage;
 429    }
 430 }
 431
 432 enum HazardResult {
 433    hazard_success,
 434    hazard_fail_reorder_vmem_smem,
 435    hazard_fail_reorder_ds,
 436    hazard_fail_reorder_sendmsg,
 437    hazard_fail_spill,
 438    hazard_fail_export,
 439    hazard_fail_barrier,
 440    /* Must stop at these failures. The hazard query code doesn't consider them
 441     * when added. */
 442    hazard_fail_exec,
 443    hazard_fail_unreorderable,
 444 };
 445
 446 HazardResult perform_hazard_query(hazard_query *query, Instruction *instr, bool upwards)
 447 {
 448    if (instr->opcode == aco_opcode::p_exit_early_if)
 449       return hazard_fail_exec;
 450    for (const Definition& def : instr->definitions) {
 451       if (def.isFixed() && def.physReg() == exec)
 452          return hazard_fail_exec;
 453    }
 454
 455    /* don't move exports so that they stay closer together */
 456    if (instr->format == Format::EXP)
 457       return hazard_fail_export;
 458
 459    /* don't move non-reorderable instructions */
 460    if (instr->opcode == aco_opcode::s_memtime ||
 461        instr->opcode == aco_opcode::s_memrealtime ||
 462        instr->opcode == aco_opcode::s_setprio)
 463       return hazard_fail_unreorderable;
 464
 465    memory_event_set instr_set;
 466    memset(&instr_set, 0, sizeof(instr_set));
 467    memory_sync_info sync = get_sync_info_with_hack(instr);
 468    add_memory_event(&instr_set, instr, &sync);
 469
 470    memory_event_set *first = &instr_set;
 471    memory_event_set *second = &query->mem_events;
 472    if (upwards)
 473       std::swap(first, second);
 474
 475    /* everything after barrier(acquire) happens after the atomics/control_barriers before
 476     * everything after load(acquire) happens after the load
 477     */
 478    if ((first->has_control_barrier || first->access_atomic) && second->bar_acquire)
 479       return hazard_fail_barrier;
 480    if (((first->access_acquire || first->bar_acquire) && second->bar_classes) ||
 481        ((first->access_acquire | first->bar_acquire) & (second->access_relaxed | second->access_atomic)))
 482       return hazard_fail_barrier;
 483
 484    /* everything before barrier(release) happens before the atomics/control_barriers after *
 485     * everything before store(release) happens before the store
 486     */
 487    if (first->bar_release && (second->has_control_barrier || second->access_atomic))
 488       return hazard_fail_barrier;
 489    if ((first->bar_classes && (second->bar_release || second->access_release)) ||
 490        ((first->access_relaxed | first->access_atomic) & (second->bar_release | second->access_release)))
 491       return hazard_fail_barrier;
 492
 493    /* don't move memory barriers around other memory barriers */
 494    if (first->bar_classes && second->bar_classes)
 495       return hazard_fail_barrier;
 496
 497    /* don't move memory loads/stores past potentially aliasing loads/stores */
 498    unsigned aliasing_storage = instr->format == Format::SMEM ?
 499                                query->aliasing_storage_smem :
 500                                query->aliasing_storage;
 501    if ((sync.storage & aliasing_storage) && !(sync.semantics & semantic_can_reorder)) {
 502       unsigned intersect = sync.storage & aliasing_storage;
 503       if (intersect & storage_shared)
 504          return hazard_fail_reorder_ds;
 505       return hazard_fail_reorder_vmem_smem;
 506    }
 507
 508    if ((instr->opcode == aco_opcode::p_spill || instr->opcode == aco_opcode::p_reload) &&
 509        query->contains_spill)
 510       return hazard_fail_spill;
 511
 512    if (instr->opcode == aco_opcode::s_sendmsg && query->contains_sendmsg)
 513       return hazard_fail_reorder_sendmsg;
 514
 515    return hazard_success;
 516 }
 517
 518 void schedule_SMEM(sched_ctx& ctx, Block* block,
 519                    std::vector<RegisterDemand>& register_demand,
 520                    Instruction* current, int idx)
 521 {
 522    assert(idx != 0);
 523    int window_size = SMEM_WINDOW_SIZE;
 524    int max_moves = SMEM_MAX_MOVES;
 525    int16_t k = 0;
 526
 527    /* don't move s_memtime/s_memrealtime */
 528    if (current->opcode == aco_opcode::s_memtime || current->opcode == aco_opcode::s_memrealtime)
 529       return;
 530
 531    /* first, check if we have instructions before current to move down */
 532    hazard_query hq;
 533    init_hazard_query(&hq);
 534    add_to_hazard_query(&hq, current);
 535
 536    ctx.mv.downwards_init(idx, false, false);
 537
 538    for (int candidate_idx = idx - 1; k < max_moves && candidate_idx > (int) idx - window_size; candidate_idx--) {
 539       assert(candidate_idx >= 0);
 540       assert(candidate_idx == ctx.mv.source_idx);
 541       aco_ptr<Instruction>& candidate = block->instructions[candidate_idx];
 542
 543       /* break if we'd make the previous SMEM instruction stall */
 544       bool can_stall_prev_smem = idx <= ctx.last_SMEM_dep_idx && candidate_idx < ctx.last_SMEM_dep_idx;
 545       if (can_stall_prev_smem && ctx.last_SMEM_stall >= 0)
 546          break;
 547
 548       /* break when encountering another MEM instruction, logical_start or barriers */
 549       if (candidate->opcode == aco_opcode::p_logical_start)
 550          break;
 551       if (candidate->isVMEM())
 552          break;
 553
 554       bool can_move_down = true;
 555
 556       HazardResult haz = perform_hazard_query(&hq, candidate.get(), false);
 557       if (haz == hazard_fail_reorder_ds || haz == hazard_fail_spill || haz == hazard_fail_reorder_sendmsg || haz == hazard_fail_barrier || haz == hazard_fail_export)
 558          can_move_down = false;
 559       else if (haz != hazard_success)
 560          break;
 561
 562       /* don't use LDS/GDS instructions to hide latency since it can
 563        * significanly worsen LDS scheduling */
 564       if (candidate->format == Format::DS || !can_move_down) {
 565          add_to_hazard_query(&hq, candidate.get());
 566          ctx.mv.downwards_skip();
 567          continue;
 568       }
 569
 570       MoveResult res = ctx.mv.downwards_move(false);
 571       if (res == move_fail_ssa || res == move_fail_rar) {
 572          add_to_hazard_query(&hq, candidate.get());
 573          ctx.mv.downwards_skip();
 574          continue;
 575       } else if (res == move_fail_pressure) {
 576          break;
 577       }
 578
 579       if (candidate_idx < ctx.last_SMEM_dep_idx)
 580          ctx.last_SMEM_stall++;
 581       k++;
 582    }
 583
 584    /* find the first instruction depending on current or find another MEM */
 585    ctx.mv.upwards_init(idx + 1, false);
 586
 587    bool found_dependency = false;
 588    /* second, check if we have instructions after current to move up */
 589    for (int candidate_idx = idx + 1; k < max_moves && candidate_idx < (int) idx + window_size; candidate_idx++) {
 590       assert(candidate_idx == ctx.mv.source_idx);
 591       assert(candidate_idx < (int) block->instructions.size());
 592       aco_ptr<Instruction>& candidate = block->instructions[candidate_idx];
 593
 594       if (candidate->opcode == aco_opcode::p_logical_end)
 595          break;
 596
 597       /* check if candidate depends on current */
 598       bool is_dependency = !found_dependency && !ctx.mv.upwards_check_deps();
 599       /* no need to steal from following VMEM instructions */
 600       if (is_dependency && candidate->isVMEM())
 601          break;
 602
 603       if (found_dependency) {
 604          HazardResult haz = perform_hazard_query(&hq, candidate.get(), true);
 605          if (haz == hazard_fail_reorder_ds || haz == hazard_fail_spill ||
 606              haz == hazard_fail_reorder_sendmsg || haz == hazard_fail_barrier ||
 607              haz == hazard_fail_export)
 608             is_dependency = true;
 609          else if (haz != hazard_success)
 610             break;
 611       }
 612
 613       if (is_dependency) {
 614          if (!found_dependency) {
 615             ctx.mv.upwards_set_insert_idx(candidate_idx);
 616             init_hazard_query(&hq);
 617             found_dependency = true;
 618          }
 619       }
 620
 621       if (is_dependency || !found_dependency) {
 622          if (found_dependency)
 623             add_to_hazard_query(&hq, candidate.get());
 624          else
 625             k++;
 626          ctx.mv.upwards_skip();
 627          continue;
 628       }
 629
 630       MoveResult res = ctx.mv.upwards_move();
 631       if (res == move_fail_ssa || res == move_fail_rar) {
 632          /* no need to steal from following VMEM instructions */
 633          if (res == move_fail_ssa && candidate->isVMEM())
 634             break;
 635          add_to_hazard_query(&hq, candidate.get());
 636          ctx.mv.upwards_skip();
 637          continue;
 638       } else if (res == move_fail_pressure) {
 639          break;
 640       }
 641       k++;
 642    }
 643
 644    ctx.last_SMEM_dep_idx = found_dependency ? ctx.mv.insert_idx : 0;
 645    ctx.last_SMEM_stall = 10 - ctx.num_waves - k;
 646 }
 647
 648 void schedule_VMEM(sched_ctx& ctx, Block* block,
 649                    std::vector<RegisterDemand>& register_demand,
 650                    Instruction* current, int idx)
 651 {
 652    assert(idx != 0);
 653    int window_size = VMEM_WINDOW_SIZE;
 654    int max_moves = VMEM_MAX_MOVES;
 655    int clause_max_grab_dist = VMEM_CLAUSE_MAX_GRAB_DIST;
 656    int16_t k = 0;
 657
 658    /* first, check if we have instructions before current to move down */
 659    hazard_query indep_hq;
 660    hazard_query clause_hq;
 661    init_hazard_query(&indep_hq);
 662    init_hazard_query(&clause_hq);
 663    add_to_hazard_query(&indep_hq, current);
 664
 665    ctx.mv.downwards_init(idx, true, true);
 666
 667    for (int candidate_idx = idx - 1; k < max_moves && candidate_idx > (int) idx - window_size; candidate_idx--) {
 668       assert(candidate_idx == ctx.mv.source_idx);
 669       assert(candidate_idx >= 0);
 670       aco_ptr<Instruction>& candidate = block->instructions[candidate_idx];
 671       bool is_vmem = candidate->isVMEM() || candidate->isFlatOrGlobal();
 672
 673       /* break when encountering another VMEM instruction, logical_start or barriers */
 674       if (candidate->opcode == aco_opcode::p_logical_start)
 675          break;
 676
 677       /* break if we'd make the previous SMEM instruction stall */
 678       bool can_stall_prev_smem = idx <= ctx.last_SMEM_dep_idx && candidate_idx < ctx.last_SMEM_dep_idx;
 679       if (can_stall_prev_smem && ctx.last_SMEM_stall >= 0)
 680          break;
 681
 682       bool part_of_clause = false;
 683       if (current->isVMEM() == candidate->isVMEM()) {
 684          bool same_resource = true;
 685          if (current->isVMEM())
 686             same_resource = candidate->operands[0].tempId() == current->operands[0].tempId();
 687          int grab_dist = ctx.mv.insert_idx_clause - candidate_idx;
 688          /* We can't easily tell how much this will decrease the def-to-use
 689           * distances, so just use how far it will be moved as a heuristic. */
 690          part_of_clause = same_resource && grab_dist < clause_max_grab_dist;
 691       }
 692
 693       /* if current depends on candidate, add additional dependencies and continue */
 694       bool can_move_down = !is_vmem || part_of_clause;
 695
 696       HazardResult haz = perform_hazard_query(part_of_clause ? &clause_hq : &indep_hq, candidate.get(), false);
 697       if (haz == hazard_fail_reorder_ds || haz == hazard_fail_spill ||
 698           haz == hazard_fail_reorder_sendmsg || haz == hazard_fail_barrier ||
 699           haz == hazard_fail_export)
 700          can_move_down = false;
 701       else if (haz != hazard_success)
 702          break;
 703
 704       if (!can_move_down) {
 705          add_to_hazard_query(&indep_hq, candidate.get());
 706          add_to_hazard_query(&clause_hq, candidate.get());
 707          ctx.mv.downwards_skip();
 708          continue;
 709       }
 710
 711       Instruction *candidate_ptr = candidate.get();
 712       MoveResult res = ctx.mv.downwards_move(part_of_clause);
 713       if (res == move_fail_ssa || res == move_fail_rar) {
 714          add_to_hazard_query(&indep_hq, candidate.get());
 715          add_to_hazard_query(&clause_hq, candidate.get());
 716          ctx.mv.downwards_skip();
 717          continue;
 718       } else if (res == move_fail_pressure) {
 719          break;
 720       }
 721       if (part_of_clause)
 722          add_to_hazard_query(&indep_hq, candidate_ptr);
 723       k++;
 724       if (candidate_idx < ctx.last_SMEM_dep_idx)
 725          ctx.last_SMEM_stall++;
 726    }
 727
 728    /* find the first instruction depending on current or find another VMEM */
 729    ctx.mv.upwards_init(idx + 1, true);
 730
 731    bool found_dependency = false;
 732    /* second, check if we have instructions after current to move up */
 733    for (int candidate_idx = idx + 1; k < max_moves && candidate_idx < (int) idx + window_size; candidate_idx++) {
 734       assert(candidate_idx == ctx.mv.source_idx);
 735       assert(candidate_idx < (int) block->instructions.size());
 736       aco_ptr<Instruction>& candidate = block->instructions[candidate_idx];
 737       bool is_vmem = candidate->isVMEM() || candidate->isFlatOrGlobal();
 738
 739       if (candidate->opcode == aco_opcode::p_logical_end)
 740          break;
 741
 742       /* check if candidate depends on current */
 743       bool is_dependency = false;
 744       if (found_dependency) {
 745          HazardResult haz = perform_hazard_query(&indep_hq, candidate.get(), true);
 746          if (haz == hazard_fail_reorder_ds || haz == hazard_fail_spill ||
 747              haz == hazard_fail_reorder_vmem_smem || haz == hazard_fail_reorder_sendmsg ||
 748              haz == hazard_fail_barrier || haz == hazard_fail_export)
 749             is_dependency = true;
 750          else if (haz != hazard_success)
 751             break;
 752       }
 753
 754       is_dependency |= !found_dependency && !ctx.mv.upwards_check_deps();
 755       if (is_dependency) {
 756          if (!found_dependency) {
 757             ctx.mv.upwards_set_insert_idx(candidate_idx);
 758             init_hazard_query(&indep_hq);
 759             found_dependency = true;
 760          }
 761       } else if (is_vmem) {
 762          /* don't move up dependencies of other VMEM instructions */
 763          for (const Definition& def : candidate->definitions) {
 764             if (def.isTemp())
 765                ctx.mv.depends_on[def.tempId()] = true;
 766          }
 767       }
 768
 769       if (is_dependency || !found_dependency) {
 770          if (found_dependency)
 771             add_to_hazard_query(&indep_hq, candidate.get());
 772          ctx.mv.upwards_skip();
 773          continue;
 774       }
 775
 776       MoveResult res = ctx.mv.upwards_move();
 777       if (res == move_fail_ssa || res == move_fail_rar) {
 778          add_to_hazard_query(&indep_hq, candidate.get());
 779          ctx.mv.upwards_skip();
 780          continue;
 781       } else if (res == move_fail_pressure) {
 782          break;
 783       }
 784       k++;
 785    }
 786 }
 787
 788 void schedule_position_export(sched_ctx& ctx, Block* block,
 789                               std::vector<RegisterDemand>& register_demand,
 790                               Instruction* current, int idx)
 791 {
 792    assert(idx != 0);
 793    int window_size = POS_EXP_WINDOW_SIZE;
 794    int max_moves = POS_EXP_MAX_MOVES;
 795    int16_t k = 0;
 796
 797    ctx.mv.downwards_init(idx, true, false);
 798
 799    hazard_query hq;
 800    init_hazard_query(&hq);
 801    add_to_hazard_query(&hq, current);
 802
 803    for (int candidate_idx = idx - 1; k < max_moves && candidate_idx > (int) idx - window_size; candidate_idx--) {
 804       assert(candidate_idx >= 0);
 805       aco_ptr<Instruction>& candidate = block->instructions[candidate_idx];
 806
 807       if (candidate->opcode == aco_opcode::p_logical_start)
 808          break;
 809       if (candidate->isVMEM() || candidate->format == Format::SMEM || candidate->isFlatOrGlobal())
 810          break;
 811
 812       HazardResult haz = perform_hazard_query(&hq, candidate.get(), false);
 813       if (haz == hazard_fail_exec || haz == hazard_fail_unreorderable)
 814          break;
 815
 816       if (haz != hazard_success) {
 817          add_to_hazard_query(&hq, candidate.get());
 818          ctx.mv.downwards_skip();
 819          continue;
 820       }
 821
 822       MoveResult res = ctx.mv.downwards_move(false);
 823       if (res == move_fail_ssa || res == move_fail_rar) {
 824          add_to_hazard_query(&hq, candidate.get());
 825          ctx.mv.downwards_skip();
 826          continue;
 827       } else if (res == move_fail_pressure) {
 828          break;
 829       }
 830       k++;
 831    }
 832 }
 833
 834 void schedule_block(sched_ctx& ctx, Program *program, Block* block, live& live_vars)
 835 {
 836    ctx.last_SMEM_dep_idx = 0;
 837    ctx.last_SMEM_stall = INT16_MIN;
 838    ctx.mv.block = block;
 839    ctx.mv.register_demand = live_vars.register_demand[block->index].data();
 840
 841    /* go through all instructions and find memory loads */
 842    for (unsigned idx = 0; idx < block->instructions.size(); idx++) {
 843       Instruction* current = block->instructions[idx].get();
 844
 845       if (current->definitions.empty())
 846          continue;
 847
 848       if (current->isVMEM() || current->isFlatOrGlobal()) {
 849          ctx.mv.current = current;
 850          schedule_VMEM(ctx, block, live_vars.register_demand[block->index], current, idx);
 851       }
 852
 853       if (current->format == Format::SMEM) {
 854          ctx.mv.current = current;
 855          schedule_SMEM(ctx, block, live_vars.register_demand[block->index], current, idx);
 856       }
 857    }
 858
 859    if ((program->stage & (hw_vs | hw_ngg_gs)) && (block->kind & block_kind_export_end)) {
 860       /* Try to move position exports as far up as possible, to reduce register
 861        * usage and because ISA reference guides say so. */
 862       for (unsigned idx = 0; idx < block->instructions.size(); idx++) {
 863          Instruction* current = block->instructions[idx].get();
 864
 865          if (current->format == Format::EXP) {
 866             unsigned target = static_cast<Export_instruction*>(current)->dest;
 867             if (target >= V_008DFC_SQ_EXP_POS && target < V_008DFC_SQ_EXP_PARAM) {
 868                ctx.mv.current = current;
 869                schedule_position_export(ctx, block, live_vars.register_demand[block->index], current, idx);
 870             }
 871          }
 872       }
 873    }
 874
 875    /* resummarize the block's register demand */
 876    block->register_demand = RegisterDemand();
 877    for (unsigned idx = 0; idx < block->instructions.size(); idx++) {
 878       block->register_demand.update(live_vars.register_demand[block->index][idx]);
 879    }
 880 }
 881
 882
 883 void schedule_program(Program *program, live& live_vars)
 884 {
 885    sched_ctx ctx;
 886    ctx.mv.depends_on.resize(program->peekAllocationId());
 887    ctx.mv.RAR_dependencies.resize(program->peekAllocationId());
 888    ctx.mv.RAR_dependencies_clause.resize(program->peekAllocationId());
 889    /* Allowing the scheduler to reduce the number of waves to as low as 5
 890     * improves performance of Thrones of Britannia significantly and doesn't
 891     * seem to hurt anything else. */
 892    if (program->num_waves <= 5)
 893       ctx.num_waves = program->num_waves;
 894    else if (program->max_reg_demand.vgpr >= 32)
 895       ctx.num_waves = 5;
 896    else if (program->max_reg_demand.vgpr >= 28)
 897       ctx.num_waves = 6;
 898    else if (program->max_reg_demand.vgpr >= 24)
 899       ctx.num_waves = 7;
 900    else
 901       ctx.num_waves = 8;
 902    ctx.num_waves = std::max<uint16_t>(ctx.num_waves, program->min_waves);
 903
 904    assert(ctx.num_waves > 0 && ctx.num_waves <= program->num_waves);
 905    ctx.mv.max_registers = { int16_t(get_addr_vgpr_from_waves(program, ctx.num_waves) - 2),
 906                             int16_t(get_addr_sgpr_from_waves(program, ctx.num_waves))};
 907
 908    for (Block& block : program->blocks)
 909       schedule_block(ctx, program, &block, live_vars);
 910
 911    /* update max_reg_demand and num_waves */
 912    RegisterDemand new_demand;
 913    for (Block& block : program->blocks) {
 914       new_demand.update(block.register_demand);
 915    }
 916    update_vgpr_sgpr_demand(program, new_demand);
 917
 918    /* if enabled, this code asserts that register_demand is updated correctly */
 919    #if 0
 920    int prev_num_waves = program->num_waves;
 921    const RegisterDemand prev_max_demand = program->max_reg_demand;
 922
 923    std::vector<RegisterDemand> demands(program->blocks.size());
 924    for (unsigned j = 0; j < program->blocks.size(); j++) {
 925       demands[j] = program->blocks[j].register_demand;
 926    }
 927
 928    struct radv_nir_compiler_options options;
 929    options.chip_class = program->chip_class;
 930    live live_vars2 = aco::live_var_analysis(program, &options);
 931
 932    for (unsigned j = 0; j < program->blocks.size(); j++) {
 933       Block &b = program->blocks[j];
 934       for (unsigned i = 0; i < b.instructions.size(); i++)
 935          assert(live_vars.register_demand[b.index][i] == live_vars2.register_demand[b.index][i]);
 936       assert(b.register_demand == demands[j]);
 937    }
 938
 939    assert(program->max_reg_demand == prev_max_demand);
 940    assert(program->num_waves == prev_num_waves);
 941    #endif
 942 }
 943
 944 }