DependencyGraph.h Source File (original) (raw)

22#ifndef LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_DEPENDENCYGRAPH_H

23#define LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_DEPENDENCYGRAPH_H

47class DependencyGraph;

53class PredIterator {

63 : OpIt(OpIt), OpItE(OpItE), MemIt(MemIt), N(N), DAG(&DAG) {}

66 : OpIt(OpIt), OpItE(OpItE), N(N), DAG(&DAG) {}

67 friend class DGNode;

68 friend class MemDGNode;

76public:

85 auto Copy = *this;

86 ++(*this);

87 return Copy;

88 }

91};

96protected:

101

103

105

107

110 friend class SchedBundle;

111

115

116public:

122

124

134

136

139

141

146 PredIterator::skipBadIt(I->op_begin(), I->op_end(), DAG), I->op_end(),

147 this, DAG);

148 }

158

159

160

161

165

168 auto IID = II->getIntrinsicID();

169 return IID == Intrinsic::stackrestore || IID == Intrinsic::stacksave;

170 }

171 return false;

172 }

173

174

175

177 auto IID = I->getIntrinsicID();

178 return IID != Intrinsic::sideeffect && IID != Intrinsic::pseudoprobe;

179 }

180

181

182

183

186 return I->mayReadOrWriteMemory() &&

188 }

189

190

193 return I->isFenceLike() &&

195 }

196

197

205

207

208#ifndef NDEBUG

209 virtual void print(raw_ostream &OS, bool PrintDeps = true) const;

211 N.print(OS);

212 return OS;

213 }

215#endif

216};

217

218

219

220

224

226

229

231 assert(N != this && "About to point to self!");

232 NextMemN = N;

233 if (NextMemN != nullptr)

234 NextMemN->PrevMemN = this;

235 }

236

238 assert(N != this && "About to point to self!");

239 PrevMemN = N;

240 if (PrevMemN != nullptr)

241 PrevMemN->NextMemN = this;

242 }

244 void detachFromChain() {

245 if (PrevMemN != nullptr)

246 PrevMemN->NextMemN = NextMemN;

247 if (NextMemN != nullptr)

248 NextMemN->PrevMemN = PrevMemN;

249 PrevMemN = nullptr;

250 NextMemN = nullptr;

251 }

252

253public:

261 auto OpEndIt = I->op_end();

262 return PredIterator(PredIterator::skipBadIt(I->op_begin(), OpEndIt, DAG),

263 OpEndIt, MemPreds.begin(), this, DAG);

264 }

266 return PredIterator(I->op_end(), I->op_end(), MemPreds.end(), this, DAG);

267 }

268

270

272

273

274

276 [[maybe_unused]] auto Inserted = MemPreds.insert(PredN).second;

277 assert(Inserted && "PredN already exists!");

278 assert(PredN != this && "Trying to add a dependency to self!");

279 PredN->MemSuccs.insert(this);

282 }

283 }

284

285

287 MemPreds.erase(PredN);

288 PredN->MemSuccs.erase(this);

291 }

292 }

293

296 return MemPreds.count(MN);

297 return false;

298 }

299

301 return make_range(MemPreds.begin(), MemPreds.end());

302 }

303

305 return make_range(MemSuccs.begin(), MemSuccs.end());

306 }

307#ifndef NDEBUG

308 void print(raw_ostream &OS, bool PrintDeps = true) const override;

309#endif

310};

311

312

314public:

315

316

319

320

323

324

325

329};

330

332private:

334

336

338 std::optionalContext::CallbackID CreateInstrCB;

339 std::optionalContext::CallbackID EraseInstrCB;

340 std::optionalContext::CallbackID MoveInstrCB;

341 std::optionalContext::CallbackID SetUseCB;

342

343 std::unique_ptr BatchAA;

344

345 enum class DependencyType {

346 ReadAfterWrite,

347 WriteAfterWrite,

348 WriteAfterRead,

349 Control,

350 Other,

351 None,

352 };

353

354

355

356

357

359

360

361

363

365

366

367

369

370

371

373

374

375

377

378

379

380

382 MemDGNode *SkipN = nullptr) const;

383

384

385

387 MemDGNode *SkipN = nullptr) const;

388

389

391

392

394

395

397

399

400public:

401

404 CreateInstrCB = Ctx.registerCreateInstrCallback(

405 [this](Instruction *I) { notifyCreateInstr(I); });

406 EraseInstrCB = Ctx.registerEraseInstrCallback(

407 [this](Instruction *I) { notifyEraseInstr(I); });

408 MoveInstrCB = Ctx.registerMoveInstrCallback(

409 [this](Instruction *I, const BBIterator &To) {

410 notifyMoveInstr(I, To);

411 });

412 SetUseCB = Ctx.registerSetUseCallback(

413 [this](const Use &U, Value *NewSrc) { notifySetUse(U, NewSrc); });

414 }

416 if (CreateInstrCB)

417 Ctx->unregisterCreateInstrCallback(*CreateInstrCB);

418 if (EraseInstrCB)

419 Ctx->unregisterEraseInstrCallback(*EraseInstrCB);

420 if (MoveInstrCB)

421 Ctx->unregisterMoveInstrCallback(*MoveInstrCB);

422 if (SetUseCB)

423 Ctx->unregisterSetUseCallback(*SetUseCB);

424 }

425

427 auto It = InstrToNodeMap.find(I);

428 return It != InstrToNodeMap.end() ? It->second.get() : nullptr;

429 }

430

432 if (I == nullptr)

433 return nullptr;

435 }

437 auto [It, NotInMap] = InstrToNodeMap.try_emplace(I);

438 if (NotInMap) {

440 It->second = std::make_unique(I);

441 else

442 It->second = std::make_unique(I);

443 }

444 return It->second.get();

445 }

446

447

449

452 InstrToNodeMap.clear();

453 DAGInterval = {};

454 }

455#ifndef NDEBUG

456

458 bool IsEmpty = InstrToNodeMap.empty();

459 assert(IsEmpty == DAGInterval.empty() &&

460 "Interval and InstrToNodeMap out of sync!");

461 return IsEmpty;

462 }

465#endif

466};

467}

468

469#endif

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

#define LLVM_TEMPLATE_ABI

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

This file defines the DenseMap class.

std::pair< uint64_t, uint64_t > Interval

uint64_t IntrinsicInst * II

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

This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...

Represent a node in the directed graph.

Implements a dense probed hash-table based set.

DenseSetIterator< false > iterator

A range adaptor for a pair of iterators.

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

bool isUsedWithInAlloca() const

Return true if this alloca is used as an inalloca argument to a call.

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

Definition DependencyGraph.h:95

void incrUnscheduledSuccs()

Definition DependencyGraph.h:129

friend class SchedBundle

Definition DependencyGraph.h:110

void decrUnscheduledSuccs()

Definition DependencyGraph.h:125

friend class DependencyGraph

Definition DependencyGraph.h:114

DGNode(Instruction *I)

Definition DependencyGraph.h:117

static bool isMemDepCandidate(Instruction *I)

We consider I as a Memory Dependency Candidate instruction if it reads/write memory or if it has side...

Definition DependencyGraph.h:184

virtual iterator preds_end(DependencyGraph &DAG)

Definition DependencyGraph.h:149

static bool isMemIntrinsic(IntrinsicInst *I)

\Returns true if intrinsic I touches memory.

Definition DependencyGraph.h:176

iterator preds_begin(DependencyGraph &DAG) const

Definition DependencyGraph.h:152

Instruction * I

Definition DependencyGraph.h:97

friend class MemDGNode

Definition DependencyGraph.h:113

PredIterator iterator

Definition DependencyGraph.h:143

DGNode(Instruction *I, DGNodeID ID)

Definition DependencyGraph.h:112

unsigned getNumUnscheduledSuccs() const

\Returns the number of unscheduled successors.

Definition DependencyGraph.h:123

void setSchedBundle(SchedBundle &SB)

bool scheduled() const

\Returns true if this node has been scheduled.

Definition DependencyGraph.h:137

unsigned UnscheduledSuccs

The number of unscheduled successors.

Definition DependencyGraph.h:102

void setScheduled(bool NewVal)

Definition DependencyGraph.h:138

bool ready() const

\Returns true if all dependent successors have been scheduled.

Definition DependencyGraph.h:135

iterator_range< iterator > preds(DependencyGraph &DAG) const

\Returns a range of DAG predecessors nodes.

Definition DependencyGraph.h:162

iterator preds_end(DependencyGraph &DAG) const

Definition DependencyGraph.h:155

SchedBundle * SB

The scheduler bundle that this node belongs to.

Definition DependencyGraph.h:106

bool Scheduled

This is true if this node has been scheduled.

Definition DependencyGraph.h:104

static bool isMemDepNodeCandidate(Instruction *I)

\Returns true if I is a memory dependency candidate instruction.

Definition DependencyGraph.h:198

SchedBundle * getSchedBundle() const

\Returns the scheduling bundle that this node belongs to, or nullptr.

Definition DependencyGraph.h:140

DGNodeID SubclassID

For isa/dyn_cast etc.

Definition DependencyGraph.h:100

DGNode(const DGNode &Other)=delete

static bool isFenceLike(Instruction *I)

\Returns true if I is fence like. It excludes non-mem intrinsics.

Definition DependencyGraph.h:191

void clearSchedBundle()

Definition DependencyGraph.h:109

void resetScheduleState()

Definition DependencyGraph.h:130

Instruction * getInstruction() const

Definition DependencyGraph.h:206

static bool isStackSaveOrRestoreIntrinsic(Instruction *I)

Definition DependencyGraph.h:166

bool comesBefore(const DGNode *Other)

\Returns true if this is before Other in program order.

Definition DependencyGraph.h:142

friend raw_ostream & operator<<(raw_ostream &OS, DGNode &N)

Definition DependencyGraph.h:210

virtual iterator preds_begin(DependencyGraph &DAG)

Definition DependencyGraph.h:144

Definition DependencyGraph.h:331

void clear()

Definition DependencyGraph.h:451

Interval< Instruction > getInterval() const

\Returns the range of instructions included in the DAG.

Definition DependencyGraph.h:450

bool empty() const

\Returns true if the DAG's state is clear. Used in assertions.

Definition DependencyGraph.h:457

LLVM_DUMP_METHOD void dump() const

DGNode * getNode(Instruction *I) const

Definition DependencyGraph.h:426

DependencyGraph(AAResults &AA, Context &Ctx)

This constructor also registers callbacks.

Definition DependencyGraph.h:402

~DependencyGraph()

Definition DependencyGraph.h:415

DGNode * getNodeOrNull(Instruction *I) const

Like getNode() but returns nullptr if I is nullptr.

Definition DependencyGraph.h:431

void print(raw_ostream &OS) const

DGNode * getOrCreateNode(Instruction *I)

Definition DependencyGraph.h:436

LLVM_ABI Interval< Instruction > extend(ArrayRef< Instruction * > Instrs)

Build/extend the dependency graph such that it includes Instrs.

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

Convenience builders for a MemDGNode interval.

Definition DependencyGraph.h:313

static LLVM_ABI MemDGNode * getBotMemDGNode(const Interval< Instruction > &Intvl, const DependencyGraph &DAG)

Scans the instruction chain in Intvl bottom-up, returning the bottom-most MemDGNode,...

static Interval< MemDGNode > makeEmpty()

Definition DependencyGraph.h:328

static LLVM_ABI MemDGNode * getTopMemDGNode(const Interval< Instruction > &Intvl, const DependencyGraph &DAG)

Scans the instruction chain in Intvl top-down, returning the top-most MemDGNode, or nullptr.

static LLVM_ABI Interval< MemDGNode > make(const Interval< Instruction > &Instrs, DependencyGraph &DAG)

Given Instrs it finds their closest mem nodes in the interval and returns the corresponding mem range...

A DependencyGraph Node for instructions that may read/write memory, or have some ordering constraints...

Definition DependencyGraph.h:221

iterator preds_end(DependencyGraph &DAG) override

Definition DependencyGraph.h:265

friend class DependencyGraph

Definition DependencyGraph.h:243

iterator preds_begin(DependencyGraph &DAG) override

Definition DependencyGraph.h:260

bool hasMemPred(DGNode *N) const

\Returns true if there is a memory dependency N->this.

Definition DependencyGraph.h:294

static bool classof(const DGNode *Other)

Definition DependencyGraph.h:257

iterator_range< DenseSet< MemDGNode * >::const_iterator > memPreds() const

\Returns all memory dependency predecessors. Used by tests.

Definition DependencyGraph.h:300

MemDGNode * getNextNode() const

\Returns the next Mem DGNode in instruction order.

Definition DependencyGraph.h:271

iterator_range< DenseSet< MemDGNode * >::const_iterator > memSuccs() const

\Returns all memory dependency successors.

Definition DependencyGraph.h:304

void removeMemPred(MemDGNode *PredN)

Removes the memory dependency PredN->this.

Definition DependencyGraph.h:286

MemDGNode(Instruction *I)

Definition DependencyGraph.h:254

MemDGNode * getPrevNode() const

\Returns the previous Mem DGNode in instruction order.

Definition DependencyGraph.h:269

void addMemPred(MemDGNode *PredN)

Adds the mem dependency edge PredN->this.

Definition DependencyGraph.h:275

friend class PredIterator

Definition DependencyGraph.h:228

Iterate over both def-use and mem dependencies.

Definition DependencyGraph.h:53

std::ptrdiff_t difference_type

Definition DependencyGraph.h:77

PredIterator operator++(int)

Definition DependencyGraph.h:84

value_type & reference

Definition DependencyGraph.h:80

friend class MemDGNode

Definition DependencyGraph.h:68

DGNode * value_type

Definition DependencyGraph.h:78

value_type * pointer

Definition DependencyGraph.h:79

bool operator!=(const PredIterator &Other) const

Definition DependencyGraph.h:90

LLVM_ABI PredIterator & operator++()

friend class DGNode

Definition DependencyGraph.h:67

std::input_iterator_tag iterator_category

Definition DependencyGraph.h:81

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

Represents a Def-use/Use-def edge in SandboxIR.

OperandUseIterator op_iterator

A SandboxIR Value has users. This is the base class.

This provides a very simple, boring adaptor for a begin and end iterator into a range type.

Abstract Attribute helper functions.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

DGNodeID

SubclassIDs for isa/dyn_cast etc.

Definition DependencyGraph.h:40

@ MemDGNode

Definition DependencyGraph.h:42

void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)

Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

APInt operator*(APInt a, uint64_t RHS)

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

Convenience function for iterating over sub-ranges.

bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)

Implement std::hash so that hash_code can be used in STL containers.