| File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU/GCNMinRegStrategy.cpp |
| Warning: | line 170, column 5 Value stored to 'Num' is never read |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | //===- GCNMinRegStrategy.cpp ----------------------------------------------===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | /// |
| 9 | /// \file |
| 10 | /// This file defines and imlements the class GCNMinRegScheduler, which |
| 11 | /// implements an experimental, simple scheduler whose main goal is to learn |
| 12 | /// ways about consuming less possible registers for a region. |
| 13 | /// |
| 14 | //===----------------------------------------------------------------------===// |
| 15 | |
| 16 | #include "llvm/CodeGen/ScheduleDAG.h" |
| 17 | using namespace llvm; |
| 18 | |
| 19 | #define DEBUG_TYPE"machine-scheduler" "machine-scheduler" |
| 20 | |
| 21 | namespace { |
| 22 | |
| 23 | class GCNMinRegScheduler { |
| 24 | struct Candidate : ilist_node<Candidate> { |
| 25 | const SUnit *SU; |
| 26 | int Priority; |
| 27 | |
| 28 | Candidate(const SUnit *SU_, int Priority_ = 0) |
| 29 | : SU(SU_), Priority(Priority_) {} |
| 30 | }; |
| 31 | |
| 32 | SpecificBumpPtrAllocator<Candidate> Alloc; |
| 33 | using Queue = simple_ilist<Candidate>; |
| 34 | Queue RQ; // Ready queue |
| 35 | |
| 36 | std::vector<unsigned> NumPreds; |
| 37 | |
| 38 | bool isScheduled(const SUnit *SU) const { |
| 39 | assert(!SU->isBoundaryNode())((void)0); |
| 40 | return NumPreds[SU->NodeNum] == std::numeric_limits<unsigned>::max(); |
| 41 | } |
| 42 | |
| 43 | void setIsScheduled(const SUnit *SU) { |
| 44 | assert(!SU->isBoundaryNode())((void)0); |
| 45 | NumPreds[SU->NodeNum] = std::numeric_limits<unsigned>::max(); |
| 46 | } |
| 47 | |
| 48 | unsigned getNumPreds(const SUnit *SU) const { |
| 49 | assert(!SU->isBoundaryNode())((void)0); |
| 50 | assert(NumPreds[SU->NodeNum] != std::numeric_limits<unsigned>::max())((void)0); |
| 51 | return NumPreds[SU->NodeNum]; |
| 52 | } |
| 53 | |
| 54 | unsigned decNumPreds(const SUnit *SU) { |
| 55 | assert(!SU->isBoundaryNode())((void)0); |
| 56 | assert(NumPreds[SU->NodeNum] != std::numeric_limits<unsigned>::max())((void)0); |
| 57 | return --NumPreds[SU->NodeNum]; |
| 58 | } |
| 59 | |
| 60 | void initNumPreds(const decltype(ScheduleDAG::SUnits) &SUnits); |
| 61 | |
| 62 | int getReadySuccessors(const SUnit *SU) const; |
| 63 | int getNotReadySuccessors(const SUnit *SU) const; |
| 64 | |
| 65 | template <typename Calc> |
| 66 | unsigned findMax(unsigned Num, Calc C); |
| 67 | |
| 68 | Candidate* pickCandidate(); |
| 69 | |
| 70 | void bumpPredsPriority(const SUnit *SchedSU, int Priority); |
| 71 | void releaseSuccessors(const SUnit* SU, int Priority); |
| 72 | |
| 73 | public: |
| 74 | std::vector<const SUnit*> schedule(ArrayRef<const SUnit*> TopRoots, |
| 75 | const ScheduleDAG &DAG); |
| 76 | }; |
| 77 | |
| 78 | } // end anonymous namespace |
| 79 | |
| 80 | void GCNMinRegScheduler::initNumPreds(const decltype(ScheduleDAG::SUnits) &SUnits) { |
| 81 | NumPreds.resize(SUnits.size()); |
| 82 | for (unsigned I = 0; I < SUnits.size(); ++I) |
| 83 | NumPreds[I] = SUnits[I].NumPredsLeft; |
| 84 | } |
| 85 | |
| 86 | int GCNMinRegScheduler::getReadySuccessors(const SUnit *SU) const { |
| 87 | unsigned NumSchedSuccs = 0; |
| 88 | for (auto SDep : SU->Succs) { |
| 89 | bool wouldBeScheduled = true; |
| 90 | for (auto PDep : SDep.getSUnit()->Preds) { |
| 91 | auto PSU = PDep.getSUnit(); |
| 92 | assert(!PSU->isBoundaryNode())((void)0); |
| 93 | if (PSU != SU && !isScheduled(PSU)) { |
| 94 | wouldBeScheduled = false; |
| 95 | break; |
| 96 | } |
| 97 | } |
| 98 | NumSchedSuccs += wouldBeScheduled ? 1 : 0; |
| 99 | } |
| 100 | return NumSchedSuccs; |
| 101 | } |
| 102 | |
| 103 | int GCNMinRegScheduler::getNotReadySuccessors(const SUnit *SU) const { |
| 104 | return SU->Succs.size() - getReadySuccessors(SU); |
| 105 | } |
| 106 | |
| 107 | template <typename Calc> |
| 108 | unsigned GCNMinRegScheduler::findMax(unsigned Num, Calc C) { |
| 109 | assert(!RQ.empty() && Num <= RQ.size())((void)0); |
| 110 | |
| 111 | using T = decltype(C(*RQ.begin())) ; |
| 112 | |
| 113 | T Max = std::numeric_limits<T>::min(); |
| 114 | unsigned NumMax = 0; |
| 115 | for (auto I = RQ.begin(); Num; --Num) { |
| 116 | T Cur = C(*I); |
| 117 | if (Cur >= Max) { |
| 118 | if (Cur > Max) { |
| 119 | Max = Cur; |
| 120 | NumMax = 1; |
| 121 | } else |
| 122 | ++NumMax; |
| 123 | auto &Cand = *I++; |
| 124 | RQ.remove(Cand); |
| 125 | RQ.push_front(Cand); |
| 126 | continue; |
| 127 | } |
| 128 | ++I; |
| 129 | } |
| 130 | return NumMax; |
| 131 | } |
| 132 | |
| 133 | GCNMinRegScheduler::Candidate* GCNMinRegScheduler::pickCandidate() { |
| 134 | do { |
| 135 | unsigned Num = RQ.size(); |
| 136 | if (Num == 1) break; |
| 137 | |
| 138 | LLVM_DEBUG(dbgs() << "\nSelecting max priority candidates among " << Numdo { } while (false) |
| 139 | << '\n')do { } while (false); |
| 140 | Num = findMax(Num, [=](const Candidate &C) { return C.Priority; }); |
| 141 | if (Num == 1) break; |
| 142 | |
| 143 | LLVM_DEBUG(dbgs() << "\nSelecting min non-ready producing candidate among "do { } while (false) |
| 144 | << Num << '\n')do { } while (false); |
| 145 | Num = findMax(Num, [=](const Candidate &C) { |
| 146 | auto SU = C.SU; |
| 147 | int Res = getNotReadySuccessors(SU); |
| 148 | LLVM_DEBUG(dbgs() << "SU(" << SU->NodeNum << ") would left non-ready "do { } while (false) |
| 149 | << Res << " successors, metric = " << -Res << '\n')do { } while (false); |
| 150 | return -Res; |
| 151 | }); |
| 152 | if (Num == 1) break; |
| 153 | |
| 154 | LLVM_DEBUG(dbgs() << "\nSelecting most producing candidate among " << Numdo { } while (false) |
| 155 | << '\n')do { } while (false); |
| 156 | Num = findMax(Num, [=](const Candidate &C) { |
| 157 | auto SU = C.SU; |
| 158 | auto Res = getReadySuccessors(SU); |
| 159 | LLVM_DEBUG(dbgs() << "SU(" << SU->NodeNum << ") would make ready " << Resdo { } while (false) |
| 160 | << " successors, metric = " << Res << '\n')do { } while (false); |
| 161 | return Res; |
| 162 | }); |
| 163 | if (Num == 1) break; |
| 164 | |
| 165 | Num = Num ? Num : RQ.size(); |
| 166 | LLVM_DEBUG(do { } while (false) |
| 167 | dbgs()do { } while (false) |
| 168 | << "\nCan't find best candidate, selecting in program order among "do { } while (false) |
| 169 | << Num << '\n')do { } while (false); |
| 170 | Num = findMax(Num, [=](const Candidate &C) { return -(int64_t)C.SU->NodeNum; }); |
Value stored to 'Num' is never read | |
| 171 | assert(Num == 1)((void)0); |
| 172 | } while (false); |
| 173 | |
| 174 | return &RQ.front(); |
| 175 | } |
| 176 | |
| 177 | void GCNMinRegScheduler::bumpPredsPriority(const SUnit *SchedSU, int Priority) { |
| 178 | SmallPtrSet<const SUnit*, 32> Set; |
| 179 | for (const auto &S : SchedSU->Succs) { |
| 180 | if (S.getSUnit()->isBoundaryNode() || isScheduled(S.getSUnit()) || |
| 181 | S.getKind() != SDep::Data) |
| 182 | continue; |
| 183 | for (const auto &P : S.getSUnit()->Preds) { |
| 184 | auto PSU = P.getSUnit(); |
| 185 | assert(!PSU->isBoundaryNode())((void)0); |
| 186 | if (PSU != SchedSU && !isScheduled(PSU)) { |
| 187 | Set.insert(PSU); |
| 188 | } |
| 189 | } |
| 190 | } |
| 191 | SmallVector<const SUnit*, 32> Worklist(Set.begin(), Set.end()); |
| 192 | while (!Worklist.empty()) { |
| 193 | auto SU = Worklist.pop_back_val(); |
| 194 | assert(!SU->isBoundaryNode())((void)0); |
| 195 | for (const auto &P : SU->Preds) { |
| 196 | if (!P.getSUnit()->isBoundaryNode() && !isScheduled(P.getSUnit()) && |
| 197 | Set.insert(P.getSUnit()).second) |
| 198 | Worklist.push_back(P.getSUnit()); |
| 199 | } |
| 200 | } |
| 201 | LLVM_DEBUG(dbgs() << "Make the predecessors of SU(" << SchedSU->NodeNumdo { } while (false) |
| 202 | << ")'s non-ready successors of " << Prioritydo { } while (false) |
| 203 | << " priority in ready queue: ")do { } while (false); |
| 204 | for (auto &C : RQ) { |
| 205 | if (Set.count(C.SU)) { |
| 206 | C.Priority = Priority; |
| 207 | LLVM_DEBUG(dbgs() << " SU(" << C.SU->NodeNum << ')')do { } while (false); |
| 208 | } |
| 209 | } |
| 210 | LLVM_DEBUG(dbgs() << '\n')do { } while (false); |
| 211 | } |
| 212 | |
| 213 | void GCNMinRegScheduler::releaseSuccessors(const SUnit* SU, int Priority) { |
| 214 | for (const auto &S : SU->Succs) { |
| 215 | auto SuccSU = S.getSUnit(); |
| 216 | if (S.isWeak()) |
| 217 | continue; |
| 218 | assert(SuccSU->isBoundaryNode() || getNumPreds(SuccSU) > 0)((void)0); |
| 219 | if (!SuccSU->isBoundaryNode() && decNumPreds(SuccSU) == 0) |
| 220 | RQ.push_front(*new (Alloc.Allocate()) Candidate(SuccSU, Priority)); |
| 221 | } |
| 222 | } |
| 223 | |
| 224 | std::vector<const SUnit*> |
| 225 | GCNMinRegScheduler::schedule(ArrayRef<const SUnit*> TopRoots, |
| 226 | const ScheduleDAG &DAG) { |
| 227 | const auto &SUnits = DAG.SUnits; |
| 228 | std::vector<const SUnit*> Schedule; |
| 229 | Schedule.reserve(SUnits.size()); |
| 230 | |
| 231 | initNumPreds(SUnits); |
| 232 | |
| 233 | int StepNo = 0; |
| 234 | |
| 235 | for (auto SU : TopRoots) { |
| 236 | RQ.push_back(*new (Alloc.Allocate()) Candidate(SU, StepNo)); |
| 237 | } |
| 238 | releaseSuccessors(&DAG.EntrySU, StepNo); |
| 239 | |
| 240 | while (!RQ.empty()) { |
| 241 | LLVM_DEBUG(dbgs() << "\n=== Picking candidate, Step = " << StepNodo { } while (false) |
| 242 | << "\n"do { } while (false) |
| 243 | "Ready queue:";do { } while (false) |
| 244 | for (auto &Cdo { } while (false) |
| 245 | : RQ) dbgs()do { } while (false) |
| 246 | << ' ' << C.SU->NodeNum << "(P" << C.Priority << ')';do { } while (false) |
| 247 | dbgs() << '\n';)do { } while (false); |
| 248 | |
| 249 | auto C = pickCandidate(); |
| 250 | assert(C)((void)0); |
| 251 | RQ.remove(*C); |
| 252 | auto SU = C->SU; |
| 253 | LLVM_DEBUG(dbgs() << "Selected "; DAG.dumpNode(*SU))do { } while (false); |
| 254 | |
| 255 | releaseSuccessors(SU, StepNo); |
| 256 | Schedule.push_back(SU); |
| 257 | setIsScheduled(SU); |
| 258 | |
| 259 | if (getReadySuccessors(SU) == 0) |
| 260 | bumpPredsPriority(SU, StepNo); |
| 261 | |
| 262 | ++StepNo; |
| 263 | } |
| 264 | assert(SUnits.size() == Schedule.size())((void)0); |
| 265 | |
| 266 | return Schedule; |
| 267 | } |
| 268 | |
| 269 | namespace llvm { |
| 270 | |
| 271 | std::vector<const SUnit*> makeMinRegSchedule(ArrayRef<const SUnit*> TopRoots, |
| 272 | const ScheduleDAG &DAG) { |
| 273 | GCNMinRegScheduler S; |
| 274 | return S.schedule(TopRoots, DAG); |
| 275 | } |
| 276 | |
| 277 | } // end namespace llvm |