Scheduler.cpp Source File (original) (raw)

16 DGNode *TopN = Nodes.front();

18 if (N->getInstruction()->comesBefore(TopN->getInstruction()))

19 TopN = N;

20 }

21 return TopN;

22}

25 DGNode *BotN = Nodes.front();

28 BotN = N;

29 }

30 return BotN;

31}

34 for (auto *N : Nodes) {

35 auto *I = N->getInstruction();

36 if (I->getIterator() == Where)

37 ++Where;

38 I->moveBefore(*Where.getNodeParent(), Where);

39 }

40}

42#ifndef NDEBUG

44 for (auto *N : Nodes)

45 OS << *N;

46}

52#endif

54#ifndef NDEBUG

56 auto ListCopy = List;

57 while (!ListCopy.empty()) {

58 OS << *ListCopy.top() << "\n";

59 ListCopy.pop();

60 }

61}

67#endif

69void Scheduler::scheduleAndUpdateReadyList(SchedBundle &Bndl) {

71 assert(ScheduleTopItOpt && "Should have been set by now!");

72 auto Where = *ScheduleTopItOpt;

80 for (auto *DepN : N->preds(DAG)) {

81 DepN->decrUnscheduledSuccs();

82 if (DepN->ready() && !DepN->scheduled())

83 ReadyList.insert(DepN);

84 }

85 N->setScheduled(true);

86 }

87}

89void Scheduler::notifyCreateInstr(Instruction *I) {

91 auto *N = DAG.getNode(I);

94 if (N == nullptr)

95 return;

98 bool IsScheduled = ScheduleTopItOpt &&

99 *ScheduleTopItOpt != I->getParent()->end() &&

100 (*ScheduleTopItOpt.value()).comesBefore(I);

101 if (IsScheduled)

102 N->setScheduled(true);

103

104

105

106 if (!IsScheduled) {

107 for (auto *PredN : N->preds(DAG)) {

108 ReadyList.remove(PredN);

109 PredN->incrUnscheduledSuccs();

110 }

111 }

112}

113

116 Nodes.reserve(Instrs.size());

117 for (auto *I : Instrs)

118 Nodes.push_back(DAG.getNode(I));

119 auto BndlPtr = std::make_unique(std::move(Nodes));

120 auto *Bndl = BndlPtr.get();

121 Bndls[Bndl] = std::move(BndlPtr);

122 return Bndl;

123}

124

125void Scheduler::eraseBundle(SchedBundle *SB) { Bndls.erase(SB); }

126

128

129

130 auto *InstrsSB = createBundle(Instrs);

131

132

133

135 bool KeepScheduling = true;

136 while (KeepScheduling) {

137 enum class TryScheduleRes {

138 Success,

139 Failure,

140 Finished,

141

142 };

143

144

145

146 auto TryScheduleBndl = [this, InstrsSB](DGNode *ReadyN) -> TryScheduleRes {

147 auto *SB = ReadyN->getSchedBundle();

148 if (SB == nullptr) {

149

150

151 auto *SingletonSB = createBundle({ReadyN->getInstruction()});

152 scheduleAndUpdateReadyList(*SingletonSB);

153 return TryScheduleRes::Success;

154 }

155 if (SB->ready()) {

156

157

158

159 for (auto *N : *SB) {

160 if (N != ReadyN)

161 ReadyList.remove(N);

162 }

163

164 scheduleAndUpdateReadyList(*SB);

165 if (SB == InstrsSB)

166

167 return TryScheduleRes::Finished;

168 return TryScheduleRes::Success;

169 }

170 return TryScheduleRes::Failure;

171 };

172 while (!ReadyList.empty()) {

173 auto *ReadyN = ReadyList.pop();

174 auto Res = TryScheduleBndl(ReadyN);

175 switch (Res) {

176 case TryScheduleRes::Success:

177

178 continue;

179 case TryScheduleRes::Failure:

180

181

182 Retry.push_back(ReadyN);

183 continue;

184 case TryScheduleRes::Finished:

185

186 return true;

187 }

189 }

190

191 KeepScheduling = false;

193 auto Res = TryScheduleBndl(N);

194 if (Res == TryScheduleRes::Success) {

195 Retry.erase(find(Retry, N));

196 KeepScheduling = true;

197 }

198 }

199 }

200

201 eraseBundle(InstrsSB);

202 return false;

203}

204

205Scheduler::BndlSchedState

207 assert(!Instrs.empty() && "Expected non-empty bundle");

208 auto *N0 = DAG.getNode(Instrs[0]);

209 auto *SB0 = N0 != nullptr ? N0->getSchedBundle() : nullptr;

210 bool AllUnscheduled = SB0 == nullptr;

211 bool FullyScheduled = SB0 != nullptr && !SB0->isSingleton();

213 auto *N = DAG.getNode(I);

214 auto *SB = N != nullptr ? N->getSchedBundle() : nullptr;

215 if (SB != nullptr) {

216

217 AllUnscheduled = false;

218 if (SB->isSingleton()) {

219

220

221 FullyScheduled = false;

222 }

223 }

224

225 if (SB != SB0) {

226

227

228 FullyScheduled = false;

229

230 if ((SB != nullptr && !SB->isSingleton()) ||

231 (SB0 != nullptr && !SB0->isSingleton()))

232 return BndlSchedState::AlreadyScheduled;

233 }

234 }

235 return AllUnscheduled ? BndlSchedState::NoneScheduled

236 : FullyScheduled ? BndlSchedState::FullyScheduled

237 : BndlSchedState::TemporarilyScheduled;

238}

239

241

242

243

244

245

246

247

248

249

250

251

252

253

254 Instruction *TopI = &*ScheduleTopItOpt.value();

256

257 for (auto *I = LowestI, *E = TopI->getPrevNode(); I != E;

258 I = I->getPrevNode()) {

259 auto *N = DAG.getNode(I);

260 if (N == nullptr)

261 continue;

262 auto *SB = N->getSchedBundle();

263 if (SB->isSingleton())

264 eraseBundle(SB);

265 }

266

267

268

269

270

273 auto *N = DAG.getNode(&I);

274 N->resetScheduleState();

275

276

277 for (auto *PredN : N->preds(DAG))

278 PredN->incrUnscheduledSuccs();

279 }

280

281 ReadyList.clear();

284 auto *N = DAG.getNode(&I);

285 if (N->ready())

286 ReadyList.insert(N);

287 }

288}

289

293 return I->getParent() == (*Instrs.begin())->getParent();

294 }) &&

295 "Instrs not in the same BB, should have been rejected by Legality!");

296

297 if (!DAG.getInterval().empty()) {

298 auto *BB = DAG.getInterval().top()->getParent();

299 if (any_of(Instrs, [BB](auto *I) { return I->getParent() != BB; }))

300 return false;

301 }

302 if (ScheduledBB == nullptr)

303 ScheduledBB = Instrs[0]->getParent();

304

306 [this](Instruction *I) { return I->getParent() != ScheduledBB; }))

307 return false;

308 auto SchedState = getBndlSchedState(Instrs);

309 switch (SchedState) {

310 case BndlSchedState::FullyScheduled:

311

312 return true;

313 case BndlSchedState::AlreadyScheduled:

314

315

316

317 return false;

318 case BndlSchedState::TemporarilyScheduled:

319

320

321

322 DAG.extend(Instrs);

323 trimSchedule(Instrs);

324 ScheduleTopItOpt = std::next(VecUtils::getLowest(Instrs)->getIterator());

325 return tryScheduleUntil(Instrs);

326 case BndlSchedState::NoneScheduled: {

327

328 if (!ScheduleTopItOpt)

329

330 ScheduleTopItOpt = std::next(VecUtils::getLowest(Instrs)->getIterator());

331

333

335 auto *N = DAG.getNode(&I);

336 if (N->ready())

337 ReadyList.insert(N);

338 }

339

340 return tryScheduleUntil(Instrs);

341 }

342 }

344}

345

346#ifndef NDEBUG

348 OS << "ReadyList:\n";

349 ReadyList.dump(OS);

350 OS << "Top of schedule: ";

351 if (ScheduleTopItOpt)

352 OS << **ScheduleTopItOpt;

353 else

354 OS << "Empty";

355 OS << "\n";

356}

358#endif

359

360}

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

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

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

InstListType::iterator iterator

Instruction iterators...

void reserve(size_type N)

This class implements an extremely fast bulk output stream that can only output to a stream.

A DependencyGraph Node that points to an Instruction and contains memory dependency edges.

Instruction * getInstruction() const

A sandboxir::User with operands, opcode and linked with previous/next instructions in an instruction ...

LLVM_ABI BBIterator getIterator() const

\Returns a BasicBlock::iterator for this Instruction.

bool comesBefore(const Instruction *Other) const

Given an instruction Other in the same basic block as this instruction, return true if this instructi...

LLVM_DUMP_METHOD void dump() const

Definition Scheduler.cpp:63

The nodes that need to be scheduled back-to-back in a single scheduling cycle form a SchedBundle.

LLVM_ABI DGNode * getBot() const

\Returns the bundle node that comes after the others in program order.

Definition Scheduler.cpp:24

LLVM_ABI DGNode * getTop() const

\Returns the bundle node that comes before the others in program order.

Definition Scheduler.cpp:15

SmallVector< DGNode *, 4 > ContainerTy

LLVM_DUMP_METHOD void dump() const

Definition Scheduler.cpp:48

LLVM_ABI void cluster(BasicBlock::iterator Where)

Move all bundle instructions to Where back-to-back.

Definition Scheduler.cpp:33

LLVM_DUMP_METHOD void dump() const

Definition Scheduler.cpp:357

LLVM_ABI bool trySchedule(ArrayRef< Instruction * > Instrs)

Tries to build a schedule that includes all of Instrs scheduled at the same scheduling cycle.

Definition Scheduler.cpp:290

static Instruction * getLowest(ArrayRef< Instruction * > Instrs)

\Returns the instruction in Instrs that is lowest in the BB.

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

template class LLVM_TEMPLATE_ABI Interval< Instruction >

friend class Instruction

Iterator for Instructions in a `BasicBlock.

auto drop_begin(T &&RangeOrContainer, size_t N=1)

Return a range covering RangeOrContainer with the first N elements excluded.

auto find(R &&Range, const T &Val)

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

bool all_of(R &&range, UnaryPredicate P)

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

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

bool any_of(R &&range, UnaryPredicate P)

Provide wrappers to std::any_of 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.

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

@ Success

The lock was released successfully.

ArrayRef(const T &OneElt) -> ArrayRef< T >