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