DependencyGraph.cpp Source File (original) (raw)

20 auto Skip = [&DAG](auto OpIt) {

22 return I == nullptr || DAG.getNode(I) == nullptr;

23 };

24 while (OpIt != OpItE && Skip(OpIt))

25 ++OpIt;

26 return OpIt;

27}

32 assert(OpIt != OpItE && "Can't dereference end iterator!");

34 }

37 if (OpIt != OpItE)

41 "Cant' dereference end iterator!");

42 return *MemIt;

43}

48 assert(OpIt != OpItE && "Already at end!");

49 ++OpIt;

51 OpIt = PredIterator::skipBadIt(OpIt, OpItE, *DAG);

52 return *this;

53 }

56 if (OpIt != OpItE) {

57 ++OpIt;

59 OpIt = PredIterator::skipBadIt(OpIt, OpItE, *DAG);

60 return *this;

61 }

64 ++MemIt;

65 return *this;

66}

69 assert(DAG == Other.DAG && "Iterators of different DAGs!");

70 assert(N == Other.N && "Iterators of different nodes!");

71 return OpIt == Other.OpIt && MemIt == Other.MemIt;

72}

75 if (this->SB != nullptr)

76 this->SB->eraseFromBundle(this);

77 this->SB = &SB;

78}

81 if (SB == nullptr)

82 return;

83 SB->eraseFromBundle(this);

84}

86#ifndef NDEBUG

93 if (PrintDeps) {

95 static constexpr unsigned Indent = 4;

96 for (auto *Pred : MemPreds)

97 OS.indent(Indent) << "<-" << *Pred->getInstruction() << "\n";

98 }

99}

100#endif

101

107

109 I = I->getNextNode();

111 return nullptr;

113}

114

120

122 I = I->getPrevNode();

124 return nullptr;

126}

127

131 if (Instrs.empty())

132 return {};

134

135 if (TopMemN == nullptr)

136 return {};

138 assert(BotMemN != nullptr && "TopMemN should be null too!");

139

141}

142

143DependencyGraph::DependencyType

145

148 return DependencyType::ReadAfterWrite;

150 return DependencyType::WriteAfterWrite;

153 return DependencyType::WriteAfterRead;

154 }

156 return DependencyType::Control;

158 return DependencyType::Control;

161 return DependencyType::Other;

162 return DependencyType::None;

163}

164

168 return !LI->isUnordered();

170 return ->isUnordered();

172 return true;

173 return false;

174 };

175 bool Is = IsOrdered(I);

177 "An ordered instruction must be a MemDepCandidate!");

178 return Is;

179}

180

182 DependencyType DepType) {

183 std::optional DstLocOpt =

185 if (!DstLocOpt)

186 return true;

187

189 "Expected a mem instr");

190

195 switch (DepType) {

196 case DependencyType::ReadAfterWrite:

197 case DependencyType::WriteAfterWrite:

199 case DependencyType::WriteAfterRead:

201 default:

203 }

204}

205

207 DependencyType RoughDepType = getRoughDepType(SrcI, DstI);

208 switch (RoughDepType) {

209 case DependencyType::ReadAfterWrite:

210 case DependencyType::WriteAfterWrite:

211 case DependencyType::WriteAfterRead:

212 return alias(SrcI, DstI, RoughDepType);

213 case DependencyType::Control:

214

215

216

217

218 return false;

219 case DependencyType::Other:

220 return true;

221 case DependencyType::None:

222 return false;

223 }

225}

226

227void DependencyGraph::scanAndAddDeps(MemDGNode &DstN,

230 "DstN is the mem dep destination, so it must be mem");

231 Instruction *DstI = DstN.getInstruction();

232

233

235 Instruction *SrcI = SrcN.getInstruction();

236 if (hasDep(SrcI, DstI))

237 DstN.addMemPred(&SrcN);

238 }

239}

240

241void DependencyGraph::setDefUseUnscheduledSuccs(

243

244

245

246

247

248

249

251 for (Value *Op : I.operands()) {

253 if (OpI == nullptr)

254 continue;

255

256 if (OpI->getParent() != I.getParent())

257 continue;

258 if (!NewInterval.contains(OpI))

259 continue;

260 auto *OpN = getNode(OpI);

261 if (OpN == nullptr)

262 continue;

263 ++OpN->UnscheduledSuccs;

264 }

265 }

266

267

268 bool NewIsAbove = DAGInterval.empty() || NewInterval.comesBefore(DAGInterval);

269 const auto &TopInterval = NewIsAbove ? NewInterval : DAGInterval;

270 const auto &BotInterval = NewIsAbove ? DAGInterval : NewInterval;

271

272

273

274

275

276

277

278

279

280

282 auto *BotN = getNode(&BotI);

283

284 if (BotN->scheduled())

285 continue;

286 for (Value *Op : BotI.operands()) {

288 if (OpI == nullptr)

289 continue;

290 auto *OpN = getNode(OpI);

291 if (OpN == nullptr)

292 continue;

293 if (!TopInterval.contains(OpI))

294 continue;

295 ++OpN->UnscheduledSuccs;

296 }

297 }

298}

299

301

306

308 MemN->setPrevNode(LastMemN);

309 LastMemN = MemN;

310 }

311 }

312

313 if (!DAGInterval.empty()) {

314 bool NewIsAbove = NewInterval.comesBefore(DAGInterval);

315 const auto &TopInterval = NewIsAbove ? NewInterval : DAGInterval;

316 const auto &BotInterval = NewIsAbove ? DAGInterval : NewInterval;

321 assert((LinkTopN == nullptr || LinkBotN == nullptr ||

322 LinkTopN->comesBefore(LinkBotN)) &&

323 "Wrong order!");

324 if (LinkTopN != nullptr && LinkBotN != nullptr) {

325 LinkTopN->setNextNode(LinkBotN);

326 }

327#ifndef NDEBUG

328

329

330 auto UnionIntvl = DAGInterval.getUnionInterval(NewInterval);

335 if (ChainTopN != nullptr && ChainBotN != nullptr) {

336 for (auto *N = ChainTopN->getNextNode(), *LastN = ChainTopN; N != nullptr;

337 LastN = N, N = N->getNextNode()) {

338 assert(N == LastN->getNextNode() && "Bad chain!");

339 assert(N->getPrevNode() == LastN && "Bad chain!");

340 }

341 }

342#endif

343 }

344

345 setDefUseUnscheduledSuccs(NewInterval);

346}

347

348MemDGNode *DependencyGraph::getMemDGNodeBefore(DGNode *N, bool IncludingN,

351 for (auto *PrevI = IncludingN ? I : I->getPrevNode(); PrevI != nullptr;

352 PrevI = PrevI->getPrevNode()) {

354 if (PrevN == nullptr)

355 return nullptr;

357 if (PrevMemN != nullptr && PrevMemN != SkipN)

358 return PrevMemN;

359 }

360 return nullptr;

361}

362

363MemDGNode *DependencyGraph::getMemDGNodeAfter(DGNode *N, bool IncludingN,

366 for (auto *NextI = IncludingN ? I : I->getNextNode(); NextI != nullptr;

367 NextI = NextI->getNextNode()) {

369 if (NextN == nullptr)

370 return nullptr;

372 if (NextMemN != nullptr && NextMemN != SkipN)

373 return NextMemN;

374 }

375 return nullptr;

376}

377

378void DependencyGraph::notifyCreateInstr(Instruction *I) {

380

381 return;

382

383 if (!(DAGInterval.contains(I) || DAGInterval.touches(I)))

384 return;

385

386 DAGInterval = DAGInterval.getUnionInterval({I, I});

389

390

391 if (MemN != nullptr) {

392 if (auto *PrevMemN = getMemDGNodeBefore(MemN, false)) {

393 PrevMemN->NextMemN = MemN;

394 MemN->PrevMemN = PrevMemN;

395 }

396 if (auto *NextMemN = getMemDGNodeAfter(MemN, false)) {

397 NextMemN->PrevMemN = MemN;

398 MemN->NextMemN = NextMemN;

399 }

400

401

402

403 if (DAGInterval.top()->comesBefore(I)) {

406 scanAndAddDeps(*MemN, SrcInterval);

407 }

408

409 if (I->comesBefore(DAGInterval.bottom())) {

414 }

415 }

416}

417

418void DependencyGraph::notifyMoveInstr(Instruction *I, const BBIterator &To) {

420

421 return;

422

424 assert(!(To != BB->end() && &*To == I->getNextNode()) &&

425 !(To == BB->end() && std::next(I->getIterator()) == BB->end()) &&

426 "Should not have been called if destination is same as origin.");

427

428

429

430 assert(To.getNodeParent() == I->getParent() &&

431 "TODO: We don't support movement across BBs!");

433 (To == std::next(DAGInterval.bottom()->getIterator()) ||

434 (To != BB->end() && std::next(To) == DAGInterval.top()->getIterator()) ||

435 (To != BB->end() && DAGInterval.contains(&*To))) &&

436 "TODO: To should be either within the DAGInterval or right "

437 "before/after it.");

438

439

440 auto OrigDAGInterval = DAGInterval;

441

442

443 DAGInterval.notifyMoveInstr(I, To);

444

445

446

447

449 if (N == nullptr)

450 return;

452 if (MemN == nullptr)

453 return;

454

455

456 MemN->detachFromChain();

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471 if (To == BB->end() ||

472 To == std::next(OrigDAGInterval.bottom()->getIterator())) {

473

474

476 MemN->setPrevNode(

477 getMemDGNodeBefore(InsertAfterN, true, MemN));

478 } else {

479

481 MemN->setPrevNode(

482 getMemDGNodeBefore(BeforeToN, false, MemN));

483 MemN->setNextNode(

484 getMemDGNodeAfter(BeforeToN, true, MemN));

485 }

486}

487

488void DependencyGraph::notifyEraseInstr(Instruction *I) {

490

491 return;

493 if (N == nullptr)

494

495 return;

497

498 auto *PrevMemN = getMemDGNodeBefore(MemN, false);

499 auto *NextMemN = getMemDGNodeAfter(MemN, false);

500 if (PrevMemN != nullptr)

501 PrevMemN->NextMemN = NextMemN;

502 if (NextMemN != nullptr)

503 NextMemN->PrevMemN = PrevMemN;

504

505

506 while (!MemN->memPreds().empty()) {

507 auto *PredN = *MemN->memPreds().begin();

508 MemN->removeMemPred(PredN);

509 }

510 while (!MemN->memSuccs().empty()) {

511 auto *SuccN = *MemN->memSuccs().begin();

512 SuccN->removeMemPred(MemN);

513 }

514

515 } else {

516

517 if (->scheduled())

518 for (auto *PredN : N->preds(*this))

519 PredN->decrUnscheduledSuccs();

520 }

521

522 InstrToNodeMap.erase(I);

523}

524

525void DependencyGraph::notifySetUse(const Use &U, Value *NewSrc) {

526

527

529 if (auto *CurrSrcN = getNode(CurrSrcI)) {

530 CurrSrcN->decrUnscheduledSuccs();

531 }

532 }

534 if (auto *NewSrcN = getNode(NewSrcI)) {

535 ++NewSrcN->UnscheduledSuccs;

536 }

537 }

538}

539

541 if (Instrs.empty())

542 return {};

543

546 auto NewInterval = Union.getSingleDiff(DAGInterval);

547 if (NewInterval.empty())

548 return {};

549

550 createNewNodes(NewInterval);

551

552

553

554

555

556

557

558

559

560

561

562

563

566 if (!DstRange.empty()) {

569 scanAndAddDeps(DstN, SrcRange);

570 }

571 }

572 };

574 if (MemDAGInterval.empty()) {

575 FullScan(NewInterval);

576 }

577

578

579

580

581

582

583

584

585

586

587

588

589

590

591

592 else if (DAGInterval.bottom()->comesBefore(NewInterval.top())) {

594 auto SrcRangeFull = MemDAGInterval.getUnionInterval(DstRange);

595 for (MemDGNode &DstN : DstRange) {

596 auto SrcRange =

598 scanAndAddDeps(DstN, SrcRange);

599 }

600 }

601

602 else if (NewInterval.bottom()->comesBefore(DAGInterval.top())) {

603

604

605

606

607

608

609

610

611

612

613

614

615

616 FullScan(NewInterval);

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632 auto DstRangeOld = MemDAGInterval;

634 for (MemDGNode &DstN : DstRangeOld)

635 scanAndAddDeps(DstN, SrcRange);

636 } else {

637 llvm_unreachable("We don't expect extending in both directions!");

638 }

639

640 DAGInterval = Union;

641 return NewInterval;

642}

643

644#ifndef NDEBUG

646

648 Nodes.reserve(InstrToNodeMap.size());

649 for (const auto &Pair : InstrToNodeMap)

650 Nodes.push_back(Pair.second.get());

651

654 });

655 for (auto *N : Nodes)

656 N->print(OS, true);

657}

658

663#endif

664

665}

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

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

bool empty() const

empty - Check if the array is empty.

LLVM_ABI bool mayWriteToMemory() const LLVM_READONLY

Return true if this instruction may modify memory.

LLVM_ABI bool mayReadFromMemory() const LLVM_READONLY

Return true if this instruction may read memory.

void reserve(size_type N)

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

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

raw_ostream & indent(unsigned NumSpaces)

indent - Insert 'NumSpaces' spaces.

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

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

Definition DependencyGraph.cpp:87

static bool isMemDepCandidate(Instruction *I)

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

virtual ~DGNode()

Definition DependencyGraph.cpp:80

void setSchedBundle(SchedBundle &SB)

Definition DependencyGraph.cpp:74

unsigned UnscheduledSuccs

The number of unscheduled successors.

SchedBundle * SB

The scheduler bundle that this node belongs to.

bool Scheduled

This is true if this node has been scheduled.

static bool isMemDepNodeCandidate(Instruction *I)

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

static bool isFenceLike(Instruction *I)

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

LLVM_DUMP_METHOD void dump() const

Definition DependencyGraph.cpp:90

Instruction * getInstruction() const

static bool isStackSaveOrRestoreIntrinsic(Instruction *I)

LLVM_DUMP_METHOD void dump() const

Definition DependencyGraph.cpp:659

DGNode * getNode(Instruction *I) const

DGNode * getNodeOrNull(Instruction *I) const

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

void print(raw_ostream &OS) const

Definition DependencyGraph.cpp:645

DGNode * getOrCreateNode(Instruction *I)

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

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

Definition DependencyGraph.cpp:540

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

bool mayWriteToMemory() const

bool mayReadFromMemory() const

bool comesBefore(const Instruction *Other) const

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

bool isTerminator() const

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,...

Definition DependencyGraph.cpp:116

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.

Definition DependencyGraph.cpp:103

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...

Definition DependencyGraph.cpp:129

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

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

Definition DependencyGraph.cpp:91

LLVM_ABI value_type operator*()

Definition DependencyGraph.cpp:29

LLVM_ABI PredIterator & operator++()

Definition DependencyGraph.cpp:45

LLVM_ABI bool operator==(const PredIterator &Other) const

Definition DependencyGraph.cpp:68

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

OperandUseIterator op_iterator

static ModRefInfo aliasAnalysisGetModRefInfo(BatchAAResults &BatchAA, const Instruction *I, const std::optional< MemoryLocation > &OptLoc)

Equivalent to BatchAA::getModRefInfo().

static std::optional< llvm::MemoryLocation > memoryLocationGetOrNone(const Instruction *I)

Equivalent to MemoryLocation::getOrNone(I).

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

#define llvm_unreachable(msg)

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

static bool isOrdered(Instruction *I)

Definition DependencyGraph.cpp:165

template class LLVM_TEMPLATE_ABI Interval< MemDGNode >

BasicBlock(llvm::BasicBlock *BB, Context &SBCtx)

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.

FunctionAddr VTableAddr Value

decltype(auto) dyn_cast(const From &Val)

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

auto reverse(ContainerTy &&C)

bool isModSet(const ModRefInfo MRI)

void sort(IteratorTy Start, IteratorTy End)

LLVM_ABI raw_ostream & dbgs()

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

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

ModRefInfo

Flags indicating whether a memory access modifies or references memory.

@ ModRef

The access may reference and may modify the value stored in memory.

DWARFExpression::Operation Op

decltype(auto) cast(const From &Val)

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

bool isRefSet(const ModRefInfo MRI)