GCNILPSched.cpp Source File (original) (raw)

15using namespace llvm;

17#define DEBUG_TYPE "machine-scheduler"

19namespace {

21class GCNILPScheduler {

22 struct Candidate : ilist_node {

25 Candidate(SUnit *SU_)

26 : SU(SU_) {}

27 };

31 Queue PendingQueue;

32 Queue AvailQueue;

33 unsigned CurQueueId = 0;

35 std::vector SUNumbers;

38 unsigned CurCycle = 0;

40 unsigned getNodePriority(const SUnit *SU) const;

42 const SUnit *pickBest(const SUnit *left, const SUnit *right);

43 Candidate* pickCandidate();

45 void releasePending();

46 void advanceToCycle(unsigned NextCycle);

47 void releasePredecessors(const SUnit* SU);

49public:

52};

53}

57static unsigned

59 unsigned &SethiUllmanNumber = SUNumbers[SU->NodeNum];

60 if (SethiUllmanNumber != 0)

61 return SethiUllmanNumber;

63 unsigned Extra = 0;

64 for (const SDep &Pred : SU->Preds) {

65 if (Pred.isCtrl()) continue;

66 SUnit *PredSU = Pred.getSUnit();

68 if (PredSethiUllman > SethiUllmanNumber) {

69 SethiUllmanNumber = PredSethiUllman;

70 Extra = 0;

71 }

72 else if (PredSethiUllman == SethiUllmanNumber)

73 ++Extra;

74 }

76 SethiUllmanNumber += Extra;

78 if (SethiUllmanNumber == 0)

79 SethiUllmanNumber = 1;

81 return SethiUllmanNumber;

82}

86unsigned GCNILPScheduler::getNodePriority(const SUnit *SU) const {

94 return 0xffff;

99 return 0;

100

101 return SUNumbers[SU->NodeNum];

102}

103

104

105

107 unsigned MaxHeight = 0;

108 for (const SDep &Succ : SU->Succs) {

109 if (Succ.isCtrl()) continue;

111

112

113 if (Height > MaxHeight)

114 MaxHeight = Height;

115 }

116 return MaxHeight;

117}

118

119

120

122 unsigned Scratches = 0;

123 for (const SDep &Pred : SU->Preds) {

124 if (Pred.isCtrl()) continue;

125 Scratches++;

126 }

127 return Scratches;

128}

129

130

131

133

134

135 int LHeight = (int)left->getHeight();

136 int RHeight = (int)right->getHeight();

137

138

139

140

141

142

143

144

145 if (LHeight != RHeight)

146 return LHeight > RHeight ? 1 : -1;

147

148 int LDepth = left->getDepth();

149 int RDepth = right->getDepth();

150 if (LDepth != RDepth) {

152 << ") depth " << LDepth << " vs SU (" << right->NodeNum

153 << ") depth " << RDepth << "\n");

154 return LDepth < RDepth ? 1 : -1;

155 }

158

159 return 0;

160}

161

162const SUnit *GCNILPScheduler::pickBest(const SUnit *left, const SUnit *right)

163{

164

165

173 << "): " << right->getDepth() << "\n");

175 }

176 }

177

183 }

184

185

186 unsigned LPriority = getNodePriority(left);

187 unsigned RPriority = getNodePriority(right);

188

189 if (LPriority != RPriority)

190 return LPriority > RPriority ? right : left;

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

211 if (LDist != RDist)

212 return LDist < RDist ? right : left;

213

214

217 if (LScratch != RScratch)

218 return LScratch > RScratch ? right : left;

219

223 if (result != 0)

224 return result > 0 ? right : left;

225 return left;

226 }

229

231 return (left->getDepth() < right->getDepth()) ? right : left;

232

234 "NodeQueueId cannot be zero");

236}

237

238GCNILPScheduler::Candidate* GCNILPScheduler::pickCandidate() {

239 if (AvailQueue.empty())

240 return nullptr;

241 auto Best = AvailQueue.begin();

242 for (auto I = std::next(AvailQueue.begin()), E = AvailQueue.end(); I != E; ++I) {

243 const auto *NewBestSU = pickBest(Best->SU, I->SU);

244 if (NewBestSU != Best->SU) {

245 assert(NewBestSU == I->SU);

246 Best = I;

247 }

248 }

249 return &*Best;

250}

251

252void GCNILPScheduler::releasePending() {

253

254

255 for(auto I = PendingQueue.begin(), E = PendingQueue.end(); I != E;) {

256 auto &C = *I++;

257 if (C.SU->getHeight() <= CurCycle) {

260 C.SU->NodeQueueId = CurQueueId++;

261 }

262 }

263}

264

265

266void GCNILPScheduler::advanceToCycle(unsigned NextCycle) {

267 if (NextCycle <= CurCycle)

268 return;

269 CurCycle = NextCycle;

270 releasePending();

271}

272

273void GCNILPScheduler::releasePredecessors(const SUnit* SU) {

274 for (const auto &PredEdge : SU->Preds) {

275 auto *PredSU = PredEdge.getSUnit();

276 if (PredEdge.isWeak())

277 continue;

278 assert(PredSU->isBoundaryNode() || PredSU->NumSuccsLeft > 0);

279

280 PredSU->setHeightToAtLeast(SU->getHeight() + PredEdge.getLatency());

281

282 if (!PredSU->isBoundaryNode() && --PredSU->NumSuccsLeft == 0)

283 PendingQueue.push_front(*new (Alloc.Allocate()) Candidate(PredSU));

284 }

285}

286

287std::vector<const SUnit*>

288GCNILPScheduler::schedule(ArrayRef<const SUnit*> BotRoots,

289 const ScheduleDAG &DAG) {

290 auto &SUnits = const_cast<ScheduleDAG&>(DAG).SUnits;

291

292 std::vector SUSavedCopy;

293 SUSavedCopy.resize(SUnits.size());

294

295

296

297 for (const SUnit &SU : SUnits)

298 SUSavedCopy[SU.NodeNum] = SU;

299

300 SUNumbers.assign(SUnits.size(), 0);

301 for (const SUnit &SU : SUnits)

303

304 for (const auto *SU : BotRoots) {

306 *new (Alloc.Allocate()) Candidate(const_cast<SUnit*>(SU)));

307 }

308 releasePredecessors(&DAG.ExitSU);

309

310 std::vector<const SUnit*> Schedule;

311 Schedule.reserve(SUnits.size());

312 while (true) {

313 if (AvailQueue.empty() && !PendingQueue.empty()) {

314 auto *EarliestSU =

316 const Candidate &C2) {

317 return C1.SU->getHeight() < C2.SU->getHeight();

318 })->SU;

319 advanceToCycle(std::max(CurCycle + 1, EarliestSU->getHeight()));

320 }

321 if (AvailQueue.empty())

322 break;

323

325 "Ready queue:";

326 for (auto &C

327 : AvailQueue) dbgs()

328 << ' ' << C.SU->NodeNum;

329 dbgs() << '\n';);

330

331 auto *C = pickCandidate();

333 AvailQueue.remove(*C);

334 auto *SU = C->SU;

336

338

339 releasePredecessors(SU);

340 Schedule.push_back(SU);

342 }

343 assert(SUnits.size() == Schedule.size());

344

345 std::reverse(Schedule.begin(), Schedule.end());

346

347

348 for (auto &SU : SUnits)

349 SU = SUSavedCopy[SU.NodeNum];

350

351 return Schedule;

352}

353

354namespace llvm {

357 GCNILPScheduler S;

358 return S.schedule(BotRoots, DAG);

359}

360}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

AMDGPU Prepare AGPR Alloc

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

static unsigned CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector< unsigned > &SUNumbers)

CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.

Definition GCNILPSched.cpp:58

static cl::opt< bool > DisableSchedCycles("disable-sched-cycles", cl::Hidden, cl::init(false), cl::desc("Disable cycle-level precision during preRA scheduling"))

static cl::opt< bool > DisableSchedCriticalPath("disable-sched-critical-path", cl::Hidden, cl::init(false), cl::desc("Disable critical path priority in sched=list-ilp"))

static cl::opt< int > MaxReorderWindow("max-sched-reorder", cl::Hidden, cl::init(6), cl::desc("Number of instructions to allow ahead of the critical path " "in sched=list-ilp"))

static unsigned closestSucc(const SUnit *SU)

closestSucc - Returns the scheduled cycle of the successor which is closest to the current cycle.

static cl::opt< bool > DisableSchedHeight("disable-sched-height", cl::Hidden, cl::init(false), cl::desc("Disable scheduled-height priority in sched=list-ilp"))

static unsigned calcMaxScratches(const SUnit *SU)

calcMaxScratches - Returns an cost estimate of the worse case requirement for scratch registers,...

static unsigned CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector< unsigned > &SUNumbers)

CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.

static int BUCompareLatency(SUnit *left, SUnit *right, bool checkPref, RegReductionPQBase *SPQ)

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

bool isCtrl() const

Shorthand for getKind() != SDep::Data.

Scheduling unit. This is a node in the scheduling DAG.

unsigned NodeQueueId

Queue id of node.

unsigned NodeNum

Entry # of node in the node vector.

unsigned getHeight() const

Returns the height of this node, which is the length of the maximum path down to any node which has n...

unsigned short Latency

Node latency.

unsigned getDepth() const

Returns the depth of this node, which is the length of the maximum path up to any node which has no p...

bool isScheduled

True once scheduled.

SmallVector< SDep, 4 > Succs

All sunit successors.

SmallVector< SDep, 4 > Preds

All sunit predecessors.

virtual void dumpNode(const SUnit &SU) const =0

SUnit ExitSU

Special node for the region exit.

A BumpPtrAllocator that allows only elements of a specific type to be allocated.

A simple intrusive list implementation.

void push_front(reference Node)

Insert a node at the front; never copies.

bool empty() const

Check if the list is empty in constant time.

void push_back(reference Node)

Insert a node at the back; never copies.

void remove(reference N)

Remove a node by reference; never deletes.

@ C

The default llvm calling convention, compatible with C.

This is an optimization pass for GlobalISel generic memory operations.

auto min_element(R &&Range)

Provide wrappers to std::min_element which take ranges instead of having to pass begin/end explicitly...

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

std::vector< const SUnit * > makeGCNILPScheduler(ArrayRef< const SUnit * > BotRoots, const ScheduleDAG &DAG)

Definition GCNILPSched.cpp:355