Movatterモバイル変換

Go to the documentation of this file.

1//===- DependencyGraph.cpp ------------------------------------------===//

2//

3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

4// See https://llvm.org/LICENSE.txt for license information.

5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

6//

7//===----------------------------------------------------------------------===//

9#include "llvm/Transforms/Vectorize/SandboxVectorizer/DependencyGraph.h"

10#include "llvm/ADT/ArrayRef.h"

11#include "llvm/SandboxIR/Instruction.h"

12#include "llvm/SandboxIR/Utils.h"

13#include "llvm/Transforms/Vectorize/SandboxVectorizer/Scheduler.h"

15namespacellvm::sandboxir {

17PredIterator::value_type PredIterator::operator*() {

18// If it's a DGNode then we dereference the operand iterator.

19if (!isa<MemDGNode>(N)) {

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

21return DAG->getNode(cast<Instruction>((Value *)*OpIt));

22 }

23// It's a MemDGNode, so we check if we return either the use-def operand,

24// or a mem predecessor.

25if (OpIt != OpItE)

26return DAG->getNode(cast<Instruction>((Value *)*OpIt));

27// It's a MemDGNode with OpIt == end, so we need to use MemIt.

28assert(MemIt != cast<MemDGNode>(N)->MemPreds.end() &&

29"Cant' dereference end iterator!");

30return *MemIt;

31}

33PredIterator &PredIterator::operator++() {

34// If it's a DGNode then we increment the use-def iterator.

35if (!isa<MemDGNode>(N)) {

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

37 ++OpIt;

38// Skip operands that are not instructions.

39 OpIt =skipNonInstr(OpIt, OpItE);

40return *this;

41 }

42// It's a MemDGNode, so if we are not at the end of the use-def iterator we

43// need to first increment that.

44if (OpIt != OpItE) {

45 ++OpIt;

46// Skip operands that are not instructions.

47 OpIt =skipNonInstr(OpIt, OpItE);

48return *this;

49 }

50// It's a MemDGNode with OpIt == end, so we need to increment MemIt.

51assert(MemIt != cast<MemDGNode>(N)->MemPreds.end() &&"Already at end!");

52 ++MemIt;

53return *this;

54}

56boolPredIterator::operator==(constPredIterator &Other) const{

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

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

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

60}

62DGNode::~DGNode() {

63if (SB ==nullptr)

64return;

65SB->eraseFromBundle(this);

66}

68#ifndef NDEBUG

69voidDGNode::print(raw_ostream &OS,bool PrintDeps) const{

70OS << *I <<" USuccs:" <<UnscheduledSuccs <<" Sched:" <<Scheduled <<"\n";

71}

72voidDGNode::dump() const{print(dbgs()); }

73voidMemDGNode::print(raw_ostream &OS,bool PrintDeps) const{

74DGNode::print(OS,false);

75if (PrintDeps) {

76// Print memory preds.

77staticconstexprconstunsigned Indent = 4;

78for (auto *Pred : MemPreds)

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

80 }

81}

82#endif// NDEBUG

84MemDGNode *

85MemDGNodeIntervalBuilder::getTopMemDGNode(constInterval<Instruction> &Intvl,

86constDependencyGraph &DAG) {

87Instruction *I = Intvl.top();

88Instruction *BeforeI = Intvl.bottom();

89// Walk down the chain looking for a mem-dep candidate instruction.

90while (!DGNode::isMemDepNodeCandidate(I) &&I != BeforeI)

91I =I->getNextNode();

92if (!DGNode::isMemDepNodeCandidate(I))

93returnnullptr;

94return cast<MemDGNode>(DAG.getNode(I));

95}

97MemDGNode *

98MemDGNodeIntervalBuilder::getBotMemDGNode(constInterval<Instruction> &Intvl,

99constDependencyGraph &DAG) {

100Instruction *I = Intvl.bottom();

101Instruction *AfterI = Intvl.top();

102// Walk up the chain looking for a mem-dep candidate instruction.

103while (!DGNode::isMemDepNodeCandidate(I) &&I != AfterI)

104I =I->getPrevNode();

105if (!DGNode::isMemDepNodeCandidate(I))

106returnnullptr;

107return cast<MemDGNode>(DAG.getNode(I));

108}

109

110Interval<MemDGNode>

111MemDGNodeIntervalBuilder::make(constInterval<Instruction> &Instrs,

112DependencyGraph &DAG) {

113auto *TopMemN =getTopMemDGNode(Instrs, DAG);

114// If we couldn't find a mem node in range TopN - BotN then it's empty.

115if (TopMemN ==nullptr)

116return {};

117auto *BotMemN =getBotMemDGNode(Instrs, DAG);

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

119// Now that we have the mem-dep nodes, create and return the range.

120returnInterval<MemDGNode>(TopMemN, BotMemN);

121}

122

123DependencyGraph::DependencyType

124DependencyGraph::getRoughDepType(Instruction *FromI,Instruction *ToI) {

125// TODO: Perhaps compile-time improvement by skipping if neither is mem?

126if (FromI->mayWriteToMemory()) {

127if (ToI->mayReadFromMemory())

128return DependencyType::ReadAfterWrite;

129if (ToI->mayWriteToMemory())

130return DependencyType::WriteAfterWrite;

131 }elseif (FromI->mayReadFromMemory()) {

132if (ToI->mayWriteToMemory())

133return DependencyType::WriteAfterRead;

134 }

135if (isa<sandboxir::PHINode>(FromI) || isa<sandboxir::PHINode>(ToI))

136return DependencyType::Control;

137if (ToI->isTerminator())

138return DependencyType::Control;

139if (DGNode::isStackSaveOrRestoreIntrinsic(FromI) ||

140DGNode::isStackSaveOrRestoreIntrinsic(ToI))

141return DependencyType::Other;

142return DependencyType::None;

143}

144

145staticboolisOrdered(Instruction *I) {

146auto IsOrdered = [](Instruction *I) {

147if (auto *LI = dyn_cast<LoadInst>(I))

148return !LI->isUnordered();

149if (auto *SI = dyn_cast<StoreInst>(I))

150return !SI->isUnordered();

151if (DGNode::isFenceLike(I))

152returntrue;

153returnfalse;

154 };

155bool Is = IsOrdered(I);

156assert((!Is ||DGNode::isMemDepCandidate(I)) &&

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

158return Is;

159}

160

161bool DependencyGraph::alias(Instruction *SrcI,Instruction *DstI,

162 DependencyType DepType) {

163 std::optional<MemoryLocation> DstLocOpt =

164Utils::memoryLocationGetOrNone(DstI);

165if (!DstLocOpt)

166returntrue;

167// Check aliasing.

168assert((SrcI->mayReadFromMemory() || SrcI->mayWriteToMemory()) &&

169"Expected a mem instr");

170// TODO: Check AABudget

171ModRefInfo SrcModRef =

172isOrdered(SrcI)

173 ?ModRefInfo::ModRef

174 :Utils::aliasAnalysisGetModRefInfo(*BatchAA, SrcI, *DstLocOpt);

175switch (DepType) {

176case DependencyType::ReadAfterWrite:

177case DependencyType::WriteAfterWrite:

178returnisModSet(SrcModRef);

179case DependencyType::WriteAfterRead:

180returnisRefSet(SrcModRef);

181default:

182llvm_unreachable("Expected only RAW, WAW and WAR!");

183 }

184}

185

186bool DependencyGraph::hasDep(Instruction *SrcI, Instruction *DstI) {

187 DependencyType RoughDepType = getRoughDepType(SrcI, DstI);

188switch (RoughDepType) {

189case DependencyType::ReadAfterWrite:

190case DependencyType::WriteAfterWrite:

191case DependencyType::WriteAfterRead:

192return alias(SrcI, DstI, RoughDepType);

193case DependencyType::Control:

194// Adding actual dep edges from PHIs/to terminator would just create too

195// many edges, which would be bad for compile-time.

196// So we ignore them in the DAG formation but handle them in the

197// scheduler, while sorting the ready list.

198returnfalse;

199case DependencyType::Other:

200returntrue;

201case DependencyType::None:

202returnfalse;

203 }

204llvm_unreachable("Unknown DependencyType enum");

205}

206

207void DependencyGraph::scanAndAddDeps(MemDGNode &DstN,

208constInterval<MemDGNode> &SrcScanRange) {

209assert(isa<MemDGNode>(DstN) &&

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

211 Instruction *DstI = DstN.getInstruction();

212// Walk up the instruction chain from ScanRange bottom to top, looking for

213// memory instrs that may alias.

214for (MemDGNode &SrcN :reverse(SrcScanRange)) {

215 Instruction *SrcI = SrcN.getInstruction();

216if (hasDep(SrcI, DstI))

217 DstN.addMemPred(&SrcN);

218 }

219}

220

221void DependencyGraph::setDefUseUnscheduledSuccs(

222constInterval<Instruction> &NewInterval) {

223// +---+

224// | | Def

225// | | |

226// | | v

227// | | Use

228// +---+

229// Set the intra-interval counters in NewInterval.

230for (Instruction &I : NewInterval) {

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

232auto *OpI = dyn_cast<Instruction>(Op);

233if (OpI ==nullptr)

234continue;

235// TODO: For now don't cross BBs.

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

237continue;

238if (!NewInterval.contains(OpI))

239continue;

240auto *OpN =getNode(OpI);

241if (OpN ==nullptr)

242continue;

243 ++OpN->UnscheduledSuccs;

244 }

245 }

246

247// Now handle the cross-interval edges.

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

249constauto &TopInterval = NewIsAbove ? NewInterval : DAGInterval;

250constauto &BotInterval = NewIsAbove ? DAGInterval : NewInterval;

251// +---+

252// |Top|

253// | | Def

254// +---+ |

255// | | v

256// |Bot| Use

257// | |

258// +---+

259// Walk over all instructions in "BotInterval" and update the counter

260// of operands that are in "TopInterval".

261for (Instruction &BotI : BotInterval) {

262auto *BotN =getNode(&BotI);

263// Skip scheduled nodes.

264if (BotN->scheduled())

265continue;

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

267auto *OpI = dyn_cast<Instruction>(Op);

268if (OpI ==nullptr)

269continue;

270auto *OpN =getNode(OpI);

271if (OpN ==nullptr)

272continue;

273if (!TopInterval.contains(OpI))

274continue;

275 ++OpN->UnscheduledSuccs;

276 }

277 }

278}

279

280void DependencyGraph::createNewNodes(constInterval<Instruction> &NewInterval) {

281// Create Nodes only for the new sections of the DAG.

282DGNode *LastN =getOrCreateNode(NewInterval.top());

283MemDGNode *LastMemN = dyn_cast<MemDGNode>(LastN);

284for (Instruction &I :drop_begin(NewInterval)) {

285auto *N =getOrCreateNode(&I);

286// Build the Mem node chain.

287if (auto *MemN = dyn_cast<MemDGNode>(N)) {

288 MemN->setPrevNode(LastMemN);

289 LastMemN = MemN;

290 }

291 }

292// Link new MemDGNode chain with the old one, if any.

293if (!DAGInterval.empty()) {

294bool NewIsAbove = NewInterval.comesBefore(DAGInterval);

295constauto &TopInterval = NewIsAbove ? NewInterval : DAGInterval;

296constauto &BotInterval = NewIsAbove ? DAGInterval : NewInterval;

297MemDGNode *LinkTopN =

298MemDGNodeIntervalBuilder::getBotMemDGNode(TopInterval, *this);

299MemDGNode *LinkBotN =

300MemDGNodeIntervalBuilder::getTopMemDGNode(BotInterval, *this);

301assert((LinkTopN ==nullptr || LinkBotN ==nullptr ||

302 LinkTopN->comesBefore(LinkBotN)) &&

303"Wrong order!");

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

305 LinkTopN->setNextNode(LinkBotN);

306 }

307#ifndef NDEBUG

308// TODO: Remove this once we've done enough testing.

309// Check that the chain is well formed.

310auto UnionIntvl = DAGInterval.getUnionInterval(NewInterval);

311MemDGNode *ChainTopN =

312MemDGNodeIntervalBuilder::getTopMemDGNode(UnionIntvl, *this);

313MemDGNode *ChainBotN =

314MemDGNodeIntervalBuilder::getBotMemDGNode(UnionIntvl, *this);

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

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

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

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

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

320 }

321 }

322#endif// NDEBUG

323 }

324

325 setDefUseUnscheduledSuccs(NewInterval);

326}

327

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

329 MemDGNode *SkipN) const{

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

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

332 PrevI = PrevI->getPrevNode()) {

333auto *PrevN =getNodeOrNull(PrevI);

334if (PrevN ==nullptr)

335returnnullptr;

336auto *PrevMemN = dyn_cast<MemDGNode>(PrevN);

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

338return PrevMemN;

339 }

340returnnullptr;

341}

342

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

344 MemDGNode *SkipN) const{

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

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

347 NextI = NextI->getNextNode()) {

348auto *NextN =getNodeOrNull(NextI);

349if (NextN ==nullptr)

350returnnullptr;

351auto *NextMemN = dyn_cast<MemDGNode>(NextN);

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

353return NextMemN;

354 }

355returnnullptr;

356}

357

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

359auto *MemN = dyn_cast<MemDGNode>(getOrCreateNode(I));

360// TODO: Update the dependencies for the new node.

361

362// Update the MemDGNode chain if this is a memory node.

363if (MemN !=nullptr) {

364if (auto *PrevMemN = getMemDGNodeBefore(MemN,/*IncludingN=*/false)) {

365 PrevMemN->NextMemN = MemN;

366 MemN->PrevMemN = PrevMemN;

367 }

368if (auto *NextMemN = getMemDGNodeAfter(MemN,/*IncludingN=*/false)) {

369 NextMemN->PrevMemN = MemN;

370 MemN->NextMemN = NextMemN;

371 }

372 }

373}

374

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

376// NOTE: This function runs before `I` moves to its new destination.

377BasicBlock *BB = To.getNodeParent();

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

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

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

381

382// TODO: We can only handle fully internal movements within DAGInterval or at

383// the borders, i.e., right before the top or right after the bottom.

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

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

386assert(

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

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

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

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

391"before/after it.");

392

393// Make a copy of the DAGInterval before we update it.

394auto OrigDAGInterval = DAGInterval;

395

396// Maintain the DAGInterval.

397 DAGInterval.notifyMoveInstr(I, To);

398

399// TODO: Perhaps check if this is legal by checking the dependencies?

400

401// Update the MemDGNode chain to reflect the instr movement if necessary.

402DGNode *N =getNodeOrNull(I);

403if (N ==nullptr)

404return;

405MemDGNode *MemN = dyn_cast<MemDGNode>(N);

406if (MemN ==nullptr)

407return;

408

409// First safely detach it from the existing chain.

410 MemN->detachFromChain();

411

412// Now insert it back into the chain at the new location.

413//

414// We won't always have a DGNode to insert before it. If `To` is BB->end() or

415// if it points to an instr after DAGInterval.bottom() then we will have to

416// find a node to insert *after*.

417//

418// BB: BB:

419// I1 I1 ^

420// I2 I2 | DAGInteval [I1 to I3]

421// I3 I3 V

422// I4 I4 <- `To` == right after DAGInterval

423// <- `To` == BB->end()

424//

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

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

427// If we don't have a node to insert before, find a node to insert after and

428// update the chain.

429DGNode *InsertAfterN =getNode(&*std::prev(To));

430 MemN->setPrevNode(

431 getMemDGNodeBefore(InsertAfterN,/*IncludingN=*/true,/*SkipN=*/MemN));

432 }else {

433// We have a node to insert before, so update the chain.

434DGNode *BeforeToN =getNode(&*To);

435 MemN->setPrevNode(

436 getMemDGNodeBefore(BeforeToN,/*IncludingN=*/false,/*SkipN=*/MemN));

437 MemN->setNextNode(

438 getMemDGNodeAfter(BeforeToN,/*IncludingN=*/true,/*SkipN=*/MemN));

439 }

440}

441

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

443// Update the MemDGNode chain if this is a memory node.

444if (auto *MemN = dyn_cast_or_null<MemDGNode>(getNodeOrNull(I))) {

445auto *PrevMemN = getMemDGNodeBefore(MemN,/*IncludingN=*/false);

446auto *NextMemN = getMemDGNodeAfter(MemN,/*IncludingN=*/false);

447if (PrevMemN !=nullptr)

448 PrevMemN->NextMemN = NextMemN;

449if (NextMemN !=nullptr)

450 NextMemN->PrevMemN = PrevMemN;

451 }

452

453 InstrToNodeMap.erase(I);

454

455// TODO: Update the dependencies.

456}

457

458Interval<Instruction>DependencyGraph::extend(ArrayRef<Instruction *> Instrs) {

459if (Instrs.empty())

460return {};

461

462Interval<Instruction> InstrsInterval(Instrs);

463Interval<Instruction> Union = DAGInterval.getUnionInterval(InstrsInterval);

464auto NewInterval = Union.getSingleDiff(DAGInterval);

465if (NewInterval.empty())

466return {};

467

468 createNewNodes(NewInterval);

469

470// Create the dependencies.

471//

472// 1. This is a new DAG, DAGInterval is empty. Fully scan the whole interval.

473// +---+ - -

474// | | SrcN | |

475// | | | | SrcRange |

476// |New| v | | DstRange

477// | | DstN - |

478// | | |

479// +---+ -

480// We are scanning for deps with destination in NewInterval and sources in

481// NewInterval until DstN, for each DstN.

482auto FullScan = [this](constInterval<Instruction> Intvl) {

483auto DstRange =MemDGNodeIntervalBuilder::make(Intvl, *this);

484if (!DstRange.empty()) {

485for (MemDGNode &DstN :drop_begin(DstRange)) {

486auto SrcRange =Interval<MemDGNode>(DstRange.top(), DstN.getPrevNode());

487 scanAndAddDeps(DstN, SrcRange);

488 }

489 }

490 };

491if (DAGInterval.empty()) {

492assert(NewInterval == InstrsInterval &&"Expected empty DAGInterval!");

493 FullScan(NewInterval);

494 }

495// 2. The new section is below the old section.

496// +---+ -

497// | | |

498// |Old| SrcN |

499// | | | |

500// +---+ | | SrcRange

501// +---+ | | -

502// | | | | |

503// |New| v | | DstRange

504// | | DstN - |

505// | | |

506// +---+ -

507// We are scanning for deps with destination in NewInterval because the deps

508// in DAGInterval have already been computed. We consider sources in the whole

509// range including both NewInterval and DAGInterval until DstN, for each DstN.

510elseif (DAGInterval.bottom()->comesBefore(NewInterval.top())) {

511auto DstRange =MemDGNodeIntervalBuilder::make(NewInterval, *this);

512auto SrcRangeFull =MemDGNodeIntervalBuilder::make(

513 DAGInterval.getUnionInterval(NewInterval), *this);

514for (MemDGNode &DstN : DstRange) {

515auto SrcRange =

516Interval<MemDGNode>(SrcRangeFull.top(), DstN.getPrevNode());

517 scanAndAddDeps(DstN, SrcRange);

518 }

519 }

520// 3. The new section is above the old section.

521elseif (NewInterval.bottom()->comesBefore(DAGInterval.top())) {

522// +---+ - -

523// | | SrcN | |

524// |New| | | SrcRange | DstRange

525// | | v | |

526// | | DstN - |

527// | | |

528// +---+ -

529// +---+

530// |Old|

531// | |

532// +---+

533// When scanning for deps with destination in NewInterval we need to fully

534// scan the interval. This is the same as the scanning for a new DAG.

535 FullScan(NewInterval);

536

537// +---+ -

538// | | |

539// |New| SrcN | SrcRange

540// | | | |

541// | | | |

542// | | | |

543// +---+ | -

544// +---+ | -

545// |Old| v | DstRange

546// | | DstN |

547// +---+ -

548// When scanning for deps with destination in DAGInterval we need to

549// consider sources from the NewInterval only, because all intra-DAGInterval

550// dependencies have already been created.

551auto DstRangeOld =MemDGNodeIntervalBuilder::make(DAGInterval, *this);

552auto SrcRange =MemDGNodeIntervalBuilder::make(NewInterval, *this);

553for (MemDGNode &DstN : DstRangeOld)

554 scanAndAddDeps(DstN, SrcRange);

555 }else {

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

557 }

558

559 DAGInterval = Union;

560return NewInterval;

561}

562

563#ifndef NDEBUG

564voidDependencyGraph::print(raw_ostream &OS) const{

565// InstrToNodeMap is unordered so we need to create an ordered vector.

566SmallVector<DGNode *> Nodes;

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

568for (constauto &Pair : InstrToNodeMap)

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

570// Sort them based on which one comes first in the BB.

571sort(Nodes, [](DGNode *N1,DGNode *N2) {

572return N1->getInstruction()->comesBefore(N2->getInstruction());

573 });

574for (auto *N : Nodes)

575N->print(OS,/*PrintDeps=*/true);

576}

577

578voidDependencyGraph::dump() const{

579print(dbgs());

580dbgs() <<"\n";

581}

582#endif// NDEBUG

583

584}// namespace llvm::sandboxir

ArrayRef.h

DependencyGraph.h

#define I(x, y, z)

Definition:MD5.cpp:58

Interval

std::pair< uint64_t, uint64_t > Interval

Definition:MappedBlockStream.cpp:36

assert

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

raw_pwrite_stream & OS

Definition:SampleProfWriter.cpp:51

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

Definition:ArrayRef.h:41

llvm::ArrayRef::empty

bool empty() const

empty - Check if the array is empty.

Definition:ArrayRef.h:163

llvm::Instruction

Definition:Instruction.h:68

llvm::Instruction::mayWriteToMemory

bool mayWriteToMemory() const LLVM_READONLY

Return true if this instruction may modify memory.

Definition:Instruction.cpp:1011

llvm::Instruction::mayReadFromMemory

bool mayReadFromMemory() const LLVM_READONLY

Return true if this instruction may read memory.

Definition:Instruction.cpp:991

llvm::SmallVectorImpl::reserve

void reserve(size_type N)

Definition:SmallVector.h:663

llvm::SmallVectorTemplateBase::push_back

void push_back(const T &Elt)

Definition:SmallVector.h:413

llvm::SmallVector

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

Definition:SmallVector.h:1196

llvm::raw_ostream

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

Definition:raw_ostream.h:52

llvm::sandboxir::DGNode

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

Definition:DependencyGraph.h:94

llvm::sandboxir::DGNode::print

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

Definition:DependencyGraph.cpp:69

llvm::sandboxir::DGNode::isMemDepCandidate

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:176

llvm::sandboxir::DGNode::I

Instruction * I

Definition:DependencyGraph.h:96

llvm::sandboxir::DGNode::~DGNode

virtual ~DGNode()

Definition:DependencyGraph.cpp:62

llvm::sandboxir::DGNode::UnscheduledSuccs

unsigned UnscheduledSuccs

The number of unscheduled successors.

Definition:DependencyGraph.h:101

llvm::sandboxir::DGNode::SB

SchedBundle * SB

The scheduler bundle that this node belongs to.

Definition:DependencyGraph.h:105

llvm::sandboxir::DGNode::Scheduled

bool Scheduled

This is true if this node has been scheduled.

Definition:DependencyGraph.h:103

llvm::sandboxir::DGNode::isMemDepNodeCandidate

static bool isMemDepNodeCandidate(Instruction *I)

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

Definition:DependencyGraph.h:190

llvm::sandboxir::DGNode::isFenceLike

static bool isFenceLike(Instruction *I)

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

Definition:DependencyGraph.h:183

llvm::sandboxir::DGNode::dump

LLVM_DUMP_METHOD void dump() const

Definition:DependencyGraph.cpp:72

llvm::sandboxir::DGNode::getInstruction

Instruction * getInstruction() const

Definition:DependencyGraph.h:198

llvm::sandboxir::DGNode::isStackSaveOrRestoreIntrinsic

static bool isStackSaveOrRestoreIntrinsic(Instruction *I)

Definition:DependencyGraph.h:158

llvm::sandboxir::DependencyGraph

Definition:DependencyGraph.h:306

llvm::sandboxir::DependencyGraph::dump

LLVM_DUMP_METHOD void dump() const

Definition:DependencyGraph.cpp:578

llvm::sandboxir::DependencyGraph::getNode

DGNode * getNode(Instruction *I) const

Definition:DependencyGraph.h:394

llvm::sandboxir::DependencyGraph::getNodeOrNull

DGNode * getNodeOrNull(Instruction *I) const

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

Definition:DependencyGraph.h:399

llvm::sandboxir::DependencyGraph::print

void print(raw_ostream &OS) const

Definition:DependencyGraph.cpp:564

llvm::sandboxir::DependencyGraph::getOrCreateNode

DGNode * getOrCreateNode(Instruction *I)

Definition:DependencyGraph.h:404

llvm::sandboxir::DependencyGraph::extend

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

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

Definition:DependencyGraph.cpp:458

llvm::sandboxir::Instruction

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

Definition:Instruction.h:42

llvm::sandboxir::Instruction::mayWriteToMemory

bool mayWriteToMemory() const

Definition:Instruction.h:332

llvm::sandboxir::Instruction::mayReadFromMemory

bool mayReadFromMemory() const

Definition:Instruction.h:336

llvm::sandboxir::Instruction::isTerminator

bool isTerminator() const

Definition:Instruction.h:142

llvm::sandboxir::Interval

Definition:Interval.h:78

llvm::sandboxir::Interval::bottom

T * bottom() const

Definition:Interval.h:112

llvm::sandboxir::Interval::top

T * top() const

Definition:Interval.h:111

llvm::sandboxir::MemDGNodeIntervalBuilder::getBotMemDGNode

static 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:98

llvm::sandboxir::MemDGNodeIntervalBuilder::getTopMemDGNode

static 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:85

llvm::sandboxir::MemDGNodeIntervalBuilder::make

static 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:111

llvm::sandboxir::MemDGNode

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

Definition:DependencyGraph.h:213

llvm::sandboxir::MemDGNode::print

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

Definition:DependencyGraph.cpp:73

llvm::sandboxir::PredIterator

Iterate over both def-use and mem dependencies.

Definition:DependencyGraph.h:58

llvm::sandboxir::PredIterator::operator*

value_type operator*()

Definition:DependencyGraph.cpp:17

llvm::sandboxir::PredIterator::operator++

PredIterator & operator++()

Definition:DependencyGraph.cpp:33

llvm::sandboxir::PredIterator::operator==

bool operator==(const PredIterator &Other) const

Definition:DependencyGraph.cpp:56

llvm::sandboxir::Utils::aliasAnalysisGetModRefInfo

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

Equivalent to BatchAA::getModRefInfo().

Definition:Utils.h:123

llvm::sandboxir::Utils::memoryLocationGetOrNone

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

Equivalent to MemoryLocation::getOrNone(I).

Definition:Utils.h:85

llvm::sandboxir::Value

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

Definition:Value.h:63

llvm_unreachable

#define llvm_unreachable(msg)

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

Definition:ErrorHandling.h:143

llvm::ISD::BasicBlock

@ BasicBlock

Various leaf nodes.

Definition:ISDOpcodes.h:71

llvm::sandboxir

Definition:Argument.h:15

llvm::sandboxir::isOrdered

static bool isOrdered(Instruction *I)

Definition:DependencyGraph.cpp:145

llvm::sandboxir::skipNonInstr

static User::op_iterator skipNonInstr(User::op_iterator OpIt, User::op_iterator OpItE)

While OpIt points to a Value that is not an Instruction keep incrementing it.

Definition:DependencyGraph.h:50

llvm::sandboxir::DGNodeID::DGNode

@ DGNode

llvm::sandboxir::DGNodeID::MemDGNode

@ MemDGNode

llvm::drop_begin

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

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

Definition:STLExtras.h:329

llvm::reverse

auto reverse(ContainerTy &&C)

Definition:STLExtras.h:420

llvm::isModSet

bool isModSet(const ModRefInfo MRI)

Definition:ModRef.h:48

llvm::sort

void sort(IteratorTy Start, IteratorTy End)

Definition:STLExtras.h:1664

llvm::dbgs

raw_ostream & dbgs()

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

Definition:Debug.cpp:163

llvm::ModRefInfo

ModRefInfo

Flags indicating whether a memory access modifies or references memory.

Definition:ModRef.h:27

llvm::ModRefInfo::ModRef

@ ModRef

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

llvm::IRMemLocation::Other

@ Other

Any other memory.

llvm::Op

DWARFExpression::Operation Op

Definition:DWARFExpression.cpp:22

llvm::isRefSet

bool isRefSet(const ModRefInfo MRI)

Definition:ModRef.h:51

#define N