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 to before control barriers. This is to make
 498     * memory barriers followed by control barriers work. */
 499    if (first->has_control_barrier && (second->access_atomic | second->access_relaxed))
 500       return hazard_fail_barrier;
 501
 502    /* don't move memory loads/stores past potentially aliasing loads/stores */
 503    unsigned aliasing_storage = instr->format == Format::SMEM ?
 504                                query->aliasing_storage_smem :
 505                                query->aliasing_storage;
 506    if ((sync.storage & aliasing_storage) && !(sync.semantics & semantic_can_reorder)) {
 507       unsigned intersect = sync.storage & aliasing_storage;
 508       if (intersect & storage_shared)
 509          return hazard_fail_reorder_ds;
 510       return hazard_fail_reorder_vmem_smem;
 511    }
 512
 513    if ((instr->opcode == aco_opcode::p_spill || instr->opcode == aco_opcode::p_reload) &&
 514        query->contains_spill)
 515       return hazard_fail_spill;
 516
 517    if (instr->opcode == aco_opcode::s_sendmsg && query->contains_sendmsg)
 518       return hazard_fail_reorder_sendmsg;
 519
 520    return hazard_success;
 521 }
 522
 523 void schedule_SMEM(sched_ctx& ctx, Block* block,
 524                    std::vector<RegisterDemand>& register_demand,
 525                    Instruction* current, int idx)
 526 {
 527    assert(idx != 0);
 528    int window_size = SMEM_WINDOW_SIZE;
 529    int max_moves = SMEM_MAX_MOVES;
 530    int16_t k = 0;
 531
 532    /* don't move s_memtime/s_memrealtime */
 533    if (current->opcode == aco_opcode::s_memtime || current->opcode == aco_opcode::s_memrealtime)
 534       return;
 535
 536    /* first, check if we have instructions before current to move down */
 537    hazard_query hq;
 538    init_hazard_query(&hq);
 539    add_to_hazard_query(&hq, current);
 540
 541    ctx.mv.downwards_init(idx, false, false);
 542
 543    for (int candidate_idx = idx - 1; k < max_moves && candidate_idx > (int) idx - window_size; candidate_idx--) {
 544       assert(candidate_idx >= 0);
 545       assert(candidate_idx == ctx.mv.source_idx);
 546       aco_ptr<Instruction>& candidate = block->instructions[candidate_idx];
 547
 548       /* break if we'd make the previous SMEM instruction stall */
 549       bool can_stall_prev_smem = idx <= ctx.last_SMEM_dep_idx && candidate_idx < ctx.last_SMEM_dep_idx;
 550       if (can_stall_prev_smem && ctx.last_SMEM_stall >= 0)
 551          break;
 552
 553       /* break when encountering another MEM instruction, logical_start or barriers */
 554       if (candidate->opcode == aco_opcode::p_logical_start)
 555          break;
 556       if (candidate->isVMEM())
 557          break;
 558
 559       bool can_move_down = true;
 560
 561       HazardResult haz = perform_hazard_query(&hq, candidate.get(), false);
 562       if (haz == hazard_fail_reorder_ds || haz == hazard_fail_spill || haz == hazard_fail_reorder_sendmsg || haz == hazard_fail_barrier || haz == hazard_fail_export)
 563          can_move_down = false;
 564       else if (haz != hazard_success)
 565          break;
 566
 567       /* don't use LDS/GDS instructions to hide latency since it can
 568        * significanly worsen LDS scheduling */
 569       if (candidate->format == Format::DS || !can_move_down) {
 570          add_to_hazard_query(&hq, candidate.get());
 571          ctx.mv.downwards_skip();
 572          continue;
 573       }
 574
 575       MoveResult res = ctx.mv.downwards_move(false);
 576       if (res == move_fail_ssa || res == move_fail_rar) {
 577          add_to_hazard_query(&hq, candidate.get());
 578          ctx.mv.downwards_skip();
 579          continue;
 580       } else if (res == move_fail_pressure) {
 581          break;
 582       }
 583
 584       if (candidate_idx < ctx.last_SMEM_dep_idx)
 585          ctx.last_SMEM_stall++;
 586       k++;
 587    }
 588
 589    /* find the first instruction depending on current or find another MEM */
 590    ctx.mv.upwards_init(idx + 1, false);
 591
 592    bool found_dependency = false;
 593    /* second, check if we have instructions after current to move up */
 594    for (int candidate_idx = idx + 1; k < max_moves && candidate_idx < (int) idx + window_size; candidate_idx++) {
 595       assert(candidate_idx == ctx.mv.source_idx);
 596       assert(candidate_idx < (int) block->instructions.size());
 597       aco_ptr<Instruction>& candidate = block->instructions[candidate_idx];
 598
 599       if (candidate->opcode == aco_opcode::p_logical_end)
 600          break;
 601
 602       /* check if candidate depends on current */
 603       bool is_dependency = !found_dependency && !ctx.mv.upwards_check_deps();
 604       /* no need to steal from following VMEM instructions */
 605       if (is_dependency && candidate->isVMEM())
 606          break;
 607
 608       if (found_dependency) {
 609          HazardResult haz = perform_hazard_query(&hq, candidate.get(), true);
 610          if (haz == hazard_fail_reorder_ds || haz == hazard_fail_spill ||
 611              haz == hazard_fail_reorder_sendmsg || haz == hazard_fail_barrier ||
 612              haz == hazard_fail_export)
 613             is_dependency = true;
 614          else if (haz != hazard_success)
 615             break;
 616       }
 617
 618       if (is_dependency) {
 619          if (!found_dependency) {
 620             ctx.mv.upwards_set_insert_idx(candidate_idx);
 621             init_hazard_query(&hq);
 622             found_dependency = true;
 623          }
 624       }
 625
 626       if (is_dependency || !found_dependency) {
 627          if (found_dependency)
 628             add_to_hazard_query(&hq, candidate.get());
 629          else
 630             k++;
 631          ctx.mv.upwards_skip();
 632          continue;
 633       }
 634
 635       MoveResult res = ctx.mv.upwards_move();
 636       if (res == move_fail_ssa || res == move_fail_rar) {
 637          /* no need to steal from following VMEM instructions */
 638          if (res == move_fail_ssa && candidate->isVMEM())
 639             break;
 640          add_to_hazard_query(&hq, candidate.get());
 641          ctx.mv.upwards_skip();
 642          continue;
 643       } else if (res == move_fail_pressure) {
 644          break;
 645       }
 646       k++;
 647    }
 648
 649    ctx.last_SMEM_dep_idx = found_dependency ? ctx.mv.insert_idx : 0;
 650    ctx.last_SMEM_stall = 10 - ctx.num_waves - k;
 651 }
 652
 653 void schedule_VMEM(sched_ctx& ctx, Block* block,
 654                    std::vector<RegisterDemand>& register_demand,
 655                    Instruction* current, int idx)
 656 {
 657    assert(idx != 0);
 658    int window_size = VMEM_WINDOW_SIZE;
 659    int max_moves = VMEM_MAX_MOVES;
 660    int clause_max_grab_dist = VMEM_CLAUSE_MAX_GRAB_DIST;
 661    int16_t k = 0;
 662
 663    /* first, check if we have instructions before current to move down */
 664    hazard_query indep_hq;
 665    hazard_query clause_hq;
 666    init_hazard_query(&indep_hq);
 667    init_hazard_query(&clause_hq);
 668    add_to_hazard_query(&indep_hq, current);
 669
 670    ctx.mv.downwards_init(idx, true, true);
 671
 672    for (int candidate_idx = idx - 1; k < max_moves && candidate_idx > (int) idx - window_size; candidate_idx--) {
 673       assert(candidate_idx == ctx.mv.source_idx);
 674       assert(candidate_idx >= 0);
 675       aco_ptr<Instruction>& candidate = block->instructions[candidate_idx];
 676       bool is_vmem = candidate->isVMEM() || candidate->isFlatOrGlobal();
 677
 678       /* break when encountering another VMEM instruction, logical_start or barriers */
 679       if (candidate->opcode == aco_opcode::p_logical_start)
 680          break;
 681
 682       /* break if we'd make the previous SMEM instruction stall */
 683       bool can_stall_prev_smem = idx <= ctx.last_SMEM_dep_idx && candidate_idx < ctx.last_SMEM_dep_idx;
 684       if (can_stall_prev_smem && ctx.last_SMEM_stall >= 0)
 685          break;
 686
 687       bool part_of_clause = false;
 688       if (current->isVMEM() == candidate->isVMEM()) {
 689          bool same_resource = true;
 690          if (current->isVMEM())
 691             same_resource = candidate->operands[0].tempId() == current->operands[0].tempId();
 692          int grab_dist = ctx.mv.insert_idx_clause - candidate_idx;
 693          /* We can't easily tell how much this will decrease the def-to-use
 694           * distances, so just use how far it will be moved as a heuristic. */
 695          part_of_clause = same_resource && grab_dist < clause_max_grab_dist;
 696       }
 697
 698       /* if current depends on candidate, add additional dependencies and continue */
 699       bool can_move_down = !is_vmem || part_of_clause;
 700
 701       HazardResult haz = perform_hazard_query(part_of_clause ? &clause_hq : &indep_hq, candidate.get(), false);
 702       if (haz == hazard_fail_reorder_ds || haz == hazard_fail_spill ||
 703           haz == hazard_fail_reorder_sendmsg || haz == hazard_fail_barrier ||
 704           haz == hazard_fail_export)
 705          can_move_down = false;
 706       else if (haz != hazard_success)
 707          break;
 708
 709       if (!can_move_down) {
 710          add_to_hazard_query(&indep_hq, candidate.get());
 711          add_to_hazard_query(&clause_hq, candidate.get());
 712          ctx.mv.downwards_skip();
 713          continue;
 714       }
 715
 716       Instruction *candidate_ptr = candidate.get();
 717       MoveResult res = ctx.mv.downwards_move(part_of_clause);
 718       if (res == move_fail_ssa || res == move_fail_rar) {
 719          add_to_hazard_query(&indep_hq, candidate.get());
 720          add_to_hazard_query(&clause_hq, candidate.get());
 721          ctx.mv.downwards_skip();
 722          continue;
 723       } else if (res == move_fail_pressure) {
 724          break;
 725       }
 726       if (part_of_clause)
 727          add_to_hazard_query(&indep_hq, candidate_ptr);
 728       k++;
 729       if (candidate_idx < ctx.last_SMEM_dep_idx)
 730          ctx.last_SMEM_stall++;
 731    }
 732
 733    /* find the first instruction depending on current or find another VMEM */
 734    ctx.mv.upwards_init(idx + 1, true);
 735
 736    bool found_dependency = false;
 737    /* second, check if we have instructions after current to move up */
 738    for (int candidate_idx = idx + 1; k < max_moves && candidate_idx < (int) idx + window_size; candidate_idx++) {
 739       assert(candidate_idx == ctx.mv.source_idx);
 740       assert(candidate_idx < (int) block->instructions.size());
 741       aco_ptr<Instruction>& candidate = block->instructions[candidate_idx];
 742       bool is_vmem = candidate->isVMEM() || candidate->isFlatOrGlobal();
 743
 744       if (candidate->opcode == aco_opcode::p_logical_end)
 745          break;
 746
 747       /* check if candidate depends on current */
 748       bool is_dependency = false;
 749       if (found_dependency) {
 750          HazardResult haz = perform_hazard_query(&indep_hq, candidate.get(), true);
 751          if (haz == hazard_fail_reorder_ds || haz == hazard_fail_spill ||
 752              haz == hazard_fail_reorder_vmem_smem || haz == hazard_fail_reorder_sendmsg ||
 753              haz == hazard_fail_barrier || haz == hazard_fail_export)
 754             is_dependency = true;
 755          else if (haz != hazard_success)
 756             break;
 757       }
 758
 759       is_dependency |= !found_dependency && !ctx.mv.upwards_check_deps();
 760       if (is_dependency) {
 761          if (!found_dependency) {
 762             ctx.mv.upwards_set_insert_idx(candidate_idx);
 763             init_hazard_query(&indep_hq);
 764             found_dependency = true;
 765          }
 766       } else if (is_vmem) {
 767          /* don't move up dependencies of other VMEM instructions */
 768          for (const Definition& def : candidate->definitions) {
 769             if (def.isTemp())
 770                ctx.mv.depends_on[def.tempId()] = true;
 771          }
 772       }
 773
 774       if (is_dependency || !found_dependency) {
 775          if (found_dependency)
 776             add_to_hazard_query(&indep_hq, candidate.get());
 777          ctx.mv.upwards_skip();
 778          continue;
 779       }
 780
 781       MoveResult res = ctx.mv.upwards_move();
 782       if (res == move_fail_ssa || res == move_fail_rar) {
 783          add_to_hazard_query(&indep_hq, candidate.get());
 784          ctx.mv.upwards_skip();
 785          continue;
 786       } else if (res == move_fail_pressure) {
 787          break;
 788       }
 789       k++;
 790    }
 791 }
 792
 793 void schedule_position_export(sched_ctx& ctx, Block* block,
 794                               std::vector<RegisterDemand>& register_demand,
 795                               Instruction* current, int idx)
 796 {
 797    assert(idx != 0);
 798    int window_size = POS_EXP_WINDOW_SIZE;
 799    int max_moves = POS_EXP_MAX_MOVES;
 800    int16_t k = 0;
 801
 802    ctx.mv.downwards_init(idx, true, false);
 803
 804    hazard_query hq;
 805    init_hazard_query(&hq);
 806    add_to_hazard_query(&hq, current);
 807
 808    for (int candidate_idx = idx - 1; k < max_moves && candidate_idx > (int) idx - window_size; candidate_idx--) {
 809       assert(candidate_idx >= 0);
 810       aco_ptr<Instruction>& candidate = block->instructions[candidate_idx];
 811
 812       if (candidate->opcode == aco_opcode::p_logical_start)
 813          break;
 814       if (candidate->isVMEM() || candidate->format == Format::SMEM || candidate->isFlatOrGlobal())
 815          break;
 816
 817       HazardResult haz = perform_hazard_query(&hq, candidate.get(), false);
 818       if (haz == hazard_fail_exec || haz == hazard_fail_unreorderable)
 819          break;
 820
 821       if (haz != hazard_success) {
 822          add_to_hazard_query(&hq, candidate.get());
 823          ctx.mv.downwards_skip();
 824          continue;
 825       }
 826
 827       MoveResult res = ctx.mv.downwards_move(false);
 828       if (res == move_fail_ssa || res == move_fail_rar) {
 829          add_to_hazard_query(&hq, candidate.get());
 830          ctx.mv.downwards_skip();
 831          continue;
 832       } else if (res == move_fail_pressure) {
 833          break;
 834       }
 835       k++;
 836    }
 837 }
 838
 839 void schedule_block(sched_ctx& ctx, Program *program, Block* block, live& live_vars)
 840 {
 841    ctx.last_SMEM_dep_idx = 0;
 842    ctx.last_SMEM_stall = INT16_MIN;
 843    ctx.mv.block = block;
 844    ctx.mv.register_demand = live_vars.register_demand[block->index].data();
 845
 846    /* go through all instructions and find memory loads */
 847    for (unsigned idx = 0; idx < block->instructions.size(); idx++) {
 848       Instruction* current = block->instructions[idx].get();
 849
 850       if (current->definitions.empty())
 851          continue;
 852
 853       if (current->isVMEM() || current->isFlatOrGlobal()) {
 854          ctx.mv.current = current;
 855          schedule_VMEM(ctx, block, live_vars.register_demand[block->index], current, idx);
 856       }
 857
 858       if (current->format == Format::SMEM) {
 859          ctx.mv.current = current;
 860          schedule_SMEM(ctx, block, live_vars.register_demand[block->index], current, idx);
 861       }
 862    }
 863
 864    if ((program->stage & (hw_vs | hw_ngg_gs)) && (block->kind & block_kind_export_end)) {
 865       /* Try to move position exports as far up as possible, to reduce register
 866        * usage and because ISA reference guides say so. */
 867       for (unsigned idx = 0; idx < block->instructions.size(); idx++) {
 868          Instruction* current = block->instructions[idx].get();
 869
 870          if (current->format == Format::EXP) {
 871             unsigned target = static_cast<Export_instruction*>(current)->dest;
 872             if (target >= V_008DFC_SQ_EXP_POS && target < V_008DFC_SQ_EXP_PARAM) {
 873                ctx.mv.current = current;
 874                schedule_position_export(ctx, block, live_vars.register_demand[block->index], current, idx);
 875             }
 876          }
 877       }
 878    }
 879
 880    /* resummarize the block's register demand */
 881    block->register_demand = RegisterDemand();
 882    for (unsigned idx = 0; idx < block->instructions.size(); idx++) {
 883       block->register_demand.update(live_vars.register_demand[block->index][idx]);
 884    }
 885 }
 886
 887
 888 void schedule_program(Program *program, live& live_vars)
 889 {
 890    sched_ctx ctx;
 891    ctx.mv.depends_on.resize(program->peekAllocationId());
 892    ctx.mv.RAR_dependencies.resize(program->peekAllocationId());
 893    ctx.mv.RAR_dependencies_clause.resize(program->peekAllocationId());
 894    /* Allowing the scheduler to reduce the number of waves to as low as 5
 895     * improves performance of Thrones of Britannia significantly and doesn't
 896     * seem to hurt anything else. */
 897    if (program->num_waves <= 5)
 898       ctx.num_waves = program->num_waves;
 899    else if (program->max_reg_demand.vgpr >= 32)
 900       ctx.num_waves = 5;
 901    else if (program->max_reg_demand.vgpr >= 28)
 902       ctx.num_waves = 6;
 903    else if (program->max_reg_demand.vgpr >= 24)
 904       ctx.num_waves = 7;
 905    else
 906       ctx.num_waves = 8;
 907    ctx.num_waves = std::max<uint16_t>(ctx.num_waves, program->min_waves);
 908
 909    assert(ctx.num_waves > 0 && ctx.num_waves <= program->num_waves);
 910    ctx.mv.max_registers = { int16_t(get_addr_vgpr_from_waves(program, ctx.num_waves) - 2),
 911                             int16_t(get_addr_sgpr_from_waves(program, ctx.num_waves))};
 912
 913    for (Block& block : program->blocks)
 914       schedule_block(ctx, program, &block, live_vars);
 915
 916    /* update max_reg_demand and num_waves */
 917    RegisterDemand new_demand;
 918    for (Block& block : program->blocks) {
 919       new_demand.update(block.register_demand);
 920    }
 921    update_vgpr_sgpr_demand(program, new_demand);
 922
 923    /* if enabled, this code asserts that register_demand is updated correctly */
 924    #if 0
 925    int prev_num_waves = program->num_waves;
 926    const RegisterDemand prev_max_demand = program->max_reg_demand;
 927
 928    std::vector<RegisterDemand> demands(program->blocks.size());
 929    for (unsigned j = 0; j < program->blocks.size(); j++) {
 930       demands[j] = program->blocks[j].register_demand;
 931    }
 932
 933    struct radv_nir_compiler_options options;
 934    options.chip_class = program->chip_class;
 935    live live_vars2 = aco::live_var_analysis(program, &options);
 936
 937    for (unsigned j = 0; j < program->blocks.size(); j++) {
 938       Block &b = program->blocks[j];
 939       for (unsigned i = 0; i < b.instructions.size(); i++)
 940          assert(live_vars.register_demand[b.index][i] == live_vars2.register_demand[b.index][i]);
 941       assert(b.register_demand == demands[j]);
 942    }
 943
 944    assert(program->max_reg_demand == prev_max_demand);
 945    assert(program->num_waves == prev_num_waves);
 946    #endif
 947 }
 948
 949 }