Scheduler.cpp Source File (original) (raw)

17namespace llvm {

18namespace mca {

20#define DEBUG_TYPE "llvm-mca"

22void Scheduler::initializeStrategy(std::unique_ptr S) {

24 Strategy = S ? std::move(S) : std::make_unique();

25}

31#ifndef NDEBUG

33 dbgs() << "[SCHEDULER]: WaitSet size is: " << WaitSet.size() << '\n';

34 dbgs() << "[SCHEDULER]: ReadySet size is: " << ReadySet.size() << '\n';

35 dbgs() << "[SCHEDULER]: IssuedSet size is: " << IssuedSet.size() << '\n';

36 Resources->dump();

37}

38#endif

42 Resources->canBeDispatched(IR.getInstruction()->getUsedBuffers());

45 switch (RSE) {

51 break;

52 }

58 switch (LSS) {

65 }

67 llvm_unreachable("Don't know how to process this LSU state result!");

68}

70void Scheduler::issueInstructionImpl(

72 SmallVectorImpl<std::pair<ResourceRef, ReleaseAtCycles>> &UsedResources) {

78 Resources->issueInstruction(D, UsedResources);

91 }

94 IssuedSet.emplace_back(IR);

97}

102 SmallVectorImpl<std::pair<ResourceRef, ReleaseAtCycles>> &UsedResources,

107 HasDependentUsers |= Inst.isMemOp() && LSU.hasDependentUsers(IR);

108

110 issueInstructionImpl(IR, UsedResources);

111

112

113

114

115 if (HasDependentUsers)

116 if (promoteToPendingSet(PendingInstructions))

117 promoteToReadySet(ReadyInstructions);

118}

119

121

122

123 unsigned PromotedElements = 0;

124 for (auto I = PendingSet.begin(), E = PendingSet.end(); I != E;) {

126 if ()

127 break;

128

129

132 ++I;

133 continue;

134 }

135

137 ++I;

138 continue;

139 }

140

142 << " promoted to the READY set.\n");

143

144 Ready.emplace_back(IR);

145 ReadySet.emplace_back(IR);

146

147 IR.invalidate();

148 ++PromotedElements;

149 std::iter_swap(I, E - PromotedElements);

150 }

151

152 PendingSet.resize(PendingSet.size() - PromotedElements);

153 return PromotedElements;

154}

155

156bool Scheduler::promoteToPendingSet(SmallVectorImpl &Pending) {

157

158

159 unsigned RemovedElements = 0;

160 for (auto I = WaitSet.begin(), E = WaitSet.end(); I != E;) {

161 InstRef &IR = *I;

162 if ()

163 break;

164

165

166

168 if (IS.isDispatched() && !IS.updateDispatched()) {

169 ++I;

170 continue;

171 }

172

173 if (IS.isMemOp() && LSU.isWaiting(IR)) {

174 ++I;

175 continue;

176 }

177

179 << " promoted to the PENDING set.\n");

180

181 Pending.emplace_back(IR);

182 PendingSet.emplace_back(IR);

183

184 IR.invalidate();

185 ++RemovedElements;

186 std::iter_swap(I, E - RemovedElements);

187 }

188

189 WaitSet.resize(WaitSet.size() - RemovedElements);

190 return RemovedElements;

191}

192

194 unsigned QueueIndex = ReadySet.size();

195 for (unsigned I = 0, E = ReadySet.size(); I != E; ++I) {

197 if (QueueIndex == ReadySet.size() ||

198 Strategy->compare(IR, ReadySet[QueueIndex])) {

200 uint64_t BusyResourceMask = Resources->checkAvailability(IS.getDesc());

201 if (BusyResourceMask)

203 BusyResourceUnits |= BusyResourceMask;

204 if (!BusyResourceMask)

205 QueueIndex = I;

206 }

207 }

208

209 if (QueueIndex == ReadySet.size())

211

212

213 InstRef IR = ReadySet[QueueIndex];

214 std::swap(ReadySet[QueueIndex], ReadySet[ReadySet.size() - 1]);

215 ReadySet.pop_back();

216 return IR;

217}

218

220 unsigned RemovedElements = 0;

221 for (auto I = IssuedSet.begin(), E = IssuedSet.end(); I != E;) {

223 if ()

224 break;

228 << " is still executing.\n");

229 ++I;

230 continue;

231 }

232

233

236 ++RemovedElements;

237 IR.invalidate();

238 std::iter_swap(I, E - RemovedElements);

239 }

240

241 IssuedSet.resize(IssuedSet.size() - RemovedElements);

242}

243

246 return BusyResourceUnits;

247}

248

251 const auto EndIt = PendingSet.end() - NumDispatchedToThePendingSet;

254 if (Resources->checkAvailability(IS.getDesc()))

255 continue;

256

257 if (IS.isMemOp() && LSU.isPending(IR))

259

262 }

263}

264

269 LSU.cycleEvent();

270

271

272 Resources->cycleEvent(Freed);

273

275 IR.getInstruction()->cycleEvent();

276 updateIssuedSet(Executed);

277

279 IR.getInstruction()->cycleEvent();

280

282 IR.getInstruction()->cycleEvent();

283

284 promoteToPendingSet(Pending);

285 promoteToReadySet(Ready);

286

287 NumDispatchedToThePendingSet = 0;

288 BusyResourceUnits = 0;

289}

290

293 if (Desc.isZeroLatency())

294 return true;

295

296

297

298 return Desc.MustIssueImmediately;

299}

300

304

305

308

310 LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the WaitSet\n");

311 WaitSet.push_back(IR);

312 return false;

313 }

314

317 << " to the PendingSet\n");

318 PendingSet.push_back(IR);

319 ++NumDispatchedToThePendingSet;

320 return false;

321 }

322

324 "Unexpected internal state found!");

325

326

327

328

329

330

331

332

334 LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the ReadySet\n");

335 ReadySet.push_back(IR);

336 }

337

338 return true;

339}

340

341}

342}

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

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

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

Legalize the Machine IR a function s Machine IR

A scheduler for Processor Resource Units and Processor Resource Groups.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

reference emplace_back(ArgTypes &&... Args)

~DefaultSchedulerStrategy() override

An InstRef contains both a SourceMgr index and Instruction pair.

const InstrDesc & getDesc() const

bool hasDependentUsers() const

An instruction propagated through the simulated instruction pipeline.

bool isDispatched() const

void setCriticalResourceMask(uint64_t ResourceMask)

LLVM_ABI const CriticalDependency & computeCriticalRegDep()

LLVM_ABI void execute(unsigned IID)

LLVM_ABI bool updatePending()

void setLSUTokenID(unsigned LSUTok)

void setCriticalMemDep(const CriticalDependency &MemDep)

uint64_t getUsedBuffers() const

unsigned getLSUTokenID() const

virtual bool isReady(const InstRef &IR) const =0

Check if a peviously dispatched instruction IR is now ready for execution.

virtual void onInstructionExecuted(const InstRef &IR)=0

virtual const CriticalDependency getCriticalPredecessor(unsigned GroupId)=0

virtual void onInstructionIssued(const InstRef &IR)=0

virtual ~SchedulerStrategy()

@ SC_DISPATCH_GROUP_STALL

LLVM_ABI InstRef select()

Select the next instruction to issue from the ReadySet.

Definition Scheduler.cpp:193

LLVM_ABI void issueInstruction(InstRef &IR, SmallVectorImpl< std::pair< ResourceRef, ReleaseAtCycles > > &Used, SmallVectorImpl< InstRef > &Pending, SmallVectorImpl< InstRef > &Ready)

Issue an instruction and populates a vector of used pipeline resources, and a vector of instructions ...

Definition Scheduler.cpp:100

LLVM_ABI Status isAvailable(const InstRef &IR)

Check if the instruction in 'IR' can be dispatched during this cycle.

Definition Scheduler.cpp:40

LLVM_ABI void analyzeDataDependencies(SmallVectorImpl< InstRef > &RegDeps, SmallVectorImpl< InstRef > &MemDeps)

This method is called by the ExecuteStage at the end of each cycle to identify bottlenecks caused by ...

Definition Scheduler.cpp:249

LLVM_ABI bool dispatch(InstRef &IR)

Reserves buffer and LSUnit queue resources that are necessary to issue this instruction.

Definition Scheduler.cpp:301

LLVM_ABI void cycleEvent(SmallVectorImpl< ResourceRef > &Freed, SmallVectorImpl< InstRef > &Executed, SmallVectorImpl< InstRef > &Pending, SmallVectorImpl< InstRef > &Ready)

This routine notifies the Scheduler that a new cycle just started.

Definition Scheduler.cpp:265

LLVM_ABI bool mustIssueImmediately(const InstRef &IR) const

Returns true if IR has to be issued immediately, or if IR is a zero latency instruction.

Definition Scheduler.cpp:291

LLVM_ABI uint64_t analyzeResourcePressure(SmallVectorImpl< InstRef > &Insts)

Returns a mask of busy resources, and populates vector Insts with instructions that could not be issu...

Definition Scheduler.cpp:244

void dump() const

Definition Scheduler.cpp:32

#define llvm_unreachable(msg)

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

ResourceStateEvent

Used to notify the internal state of a processor resource.

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

LLVM_ABI raw_ostream & dbgs()

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

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

A critical data dependency descriptor.

An instruction descriptor.