LoopRotationUtils.cpp Source File (original) (raw)

38using namespace llvm;

40#define DEBUG_TYPE "loop-rotate"

43 "Number of loops not rotated due to the header size");

45 "Number of instructions hoisted into loop preheader");

47 "Number of instructions cloned into loop preheader");

52namespace {

54class LoopRotate {

55 const unsigned MaxHeaderSize;

56 LoopInfo *LI;

57 const TargetTransformInfo *TTI;

58 AssumptionCache *AC;

59 DominatorTree *DT;

60 ScalarEvolution *SE;

61 MemorySSAUpdater *MSSAU;

62 const SimplifyQuery &SQ;

63 bool RotationOnly;

64 bool IsUtilMode;

65 bool PrepareForLTO;

67public:

68 LoopRotate(unsigned MaxHeaderSize, LoopInfo *LI,

69 const TargetTransformInfo *TTI, AssumptionCache *AC,

70 DominatorTree *DT, ScalarEvolution *SE, MemorySSAUpdater *MSSAU,

71 const SimplifyQuery &SQ, bool RotationOnly, bool IsUtilMode,

72 bool PrepareForLTO)

73 : MaxHeaderSize(MaxHeaderSize), LI(LI), TTI(TTI), AC(AC), DT(DT), SE(SE),

74 MSSAU(MSSAU), SQ(SQ), RotationOnly(RotationOnly),

75 IsUtilMode(IsUtilMode), PrepareForLTO(PrepareForLTO) {}

76 bool processLoop(Loop *L);

78private:

79 bool rotateLoop(Loop *L, bool SimplifiedLatch);

80 bool simplifyLoopLatch(Loop *L);

81};

82}

87 bool Inserted = VM.insert({K, V}).second;

89 (void)Inserted;

90}

100

103 PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreheader));

104

105

106

108 for (I = OrigHeader->begin(); I != E; ++I) {

109 Value *OrigHeaderVal = &*I;

110

111

112

114 continue;

115

117

118

119

120 SSA.Initialize(OrigHeaderVal->getType(), OrigHeaderVal->getName());

121

122

123 if (SE)

125 SSA.AddAvailableValue(OrigHeader, OrigHeaderVal);

126 SSA.AddAvailableValue(OrigPreheader, OrigPreHeaderVal);

127

128

130

131

135

136

137

138 if (UserBB == OrigHeader)

139 continue;

140

141

142

143 if (UserBB == OrigPreheader) {

144 U = OrigPreHeaderVal;

145 continue;

146 }

147 }

148

149

150 SSA.RewriteUse(U);

151 }

152

153

154

157

159

160

162 if (UserBB == OrigHeader)

163 continue;

164

165

166

167

168

170 if (UserBB == OrigPreheader)

171 NewVal = OrigPreHeaderVal;

172 else if (SSA.HasValueForBlock(UserBB))

173 NewVal = SSA.GetValueInMiddleOfBlock(UserBB);

174 else

176 DVR->replaceVariableLocationOp(OrigHeaderVal, NewVal);

177 }

178 }

179}

180

181

182

183

187 assert(BI && BI->isConditional() && "need header with conditional exit");

189 if (L->contains(HeaderExit))

191

192 for (auto &Phi : Header->phis()) {

193

195 return cast(U)->getParent() != HeaderExit;

196 }))

197 continue;

198 return true;

199 }

200 return false;

201}

202

204 bool HasConditionalPreHeader,

205 bool SuccsSwapped) {

207 if (WeightMD == nullptr)

208 return;

209

210

211

212

214 return;

215

218 if (Weights.size() != 2)

219 return;

220 uint32_t OrigLoopExitWeight = Weights[0];

221 uint32_t OrigLoopBackedgeWeight = Weights[1];

222

223 if (SuccsSwapped)

224 std::swap(OrigLoopExitWeight, OrigLoopBackedgeWeight);

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249 uint32_t ExitWeight0;

250 uint32_t ExitWeight1;

251 uint32_t EnterWeight;

252 uint32_t LoopBackWeight;

253 if (OrigLoopExitWeight > 0 && OrigLoopBackedgeWeight > 0) {

254 ExitWeight0 = 0;

255 if (HasConditionalPreHeader) {

256

257 if (OrigLoopBackedgeWeight >= OrigLoopExitWeight) {

258

259

261

262

264

266 if ((OrigLoopBackedgeWeight & HighBit) != 0 ||

267 (OrigLoopExitWeight & HighBit) != 0)

268 break;

269 OrigLoopBackedgeWeight <<= 1;

270 OrigLoopExitWeight <<= 1;

271 }

272 } else {

273

274

275 ExitWeight0 = OrigLoopExitWeight - OrigLoopBackedgeWeight;

276 }

277 } else {

278

279

280

281

282

283 if (OrigLoopExitWeight > OrigLoopBackedgeWeight)

284 OrigLoopBackedgeWeight = OrigLoopExitWeight;

285 }

286 assert(OrigLoopExitWeight >= ExitWeight0 && "Bad branch weight");

287 ExitWeight1 = OrigLoopExitWeight - ExitWeight0;

288 EnterWeight = ExitWeight1;

289 assert(OrigLoopBackedgeWeight >= EnterWeight && "Bad branch weight");

290 LoopBackWeight = OrigLoopBackedgeWeight - EnterWeight;

291 } else if (OrigLoopExitWeight == 0) {

292 if (OrigLoopBackedgeWeight == 0) {

293

294 ExitWeight0 = 0;

295 ExitWeight1 = 0;

296 EnterWeight = 0;

297 LoopBackWeight = 0;

298 } else {

299

300

301

302 ExitWeight0 = 0;

303 ExitWeight1 = 0;

304 EnterWeight = 1;

305 LoopBackWeight = OrigLoopBackedgeWeight;

306 }

307 } else {

308

309 assert(OrigLoopBackedgeWeight == 0 && "remaining case is backedge zero");

310 ExitWeight0 = 1;

311 ExitWeight1 = 1;

312 EnterWeight = 0;

313 LoopBackWeight = 0;

314 }

315

316 const uint32_t LoopBIWeights[] = {

317 SuccsSwapped ? LoopBackWeight : ExitWeight1,

318 SuccsSwapped ? ExitWeight1 : LoopBackWeight,

319 };

320 setBranchWeights(LoopBI, LoopBIWeights, false);

321 if (HasConditionalPreHeader) {

322 const uint32_t PreHeaderBIWeights[] = {

323 SuccsSwapped ? EnterWeight : ExitWeight0,

324 SuccsSwapped ? ExitWeight0 : EnterWeight,

325 };

326 setBranchWeights(PreHeaderBI, PreHeaderBIWeights, false);

327 }

328}

329

330

331

332

333

334

335

336

337

338

339

340bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {

341

342 if (L->getBlocks().size() == 1)

343 return false;

344

345 bool Rotated = false;

347 BasicBlock *OrigLatch = L->getLoopLatch();

348

351 return Rotated;

352

353

354

355

356 if (->isLoopExiting(OrigHeader))

357 return Rotated;

358

359

360

361 if (!OrigLatch)

362 return Rotated;

363

364

365

366 if (L->isLoopExiting(OrigLatch) && !SimplifiedLatch && IsUtilMode == false &&

368 return Rotated;

369

370

371

372 {

373 SmallPtrSet<const Value *, 32> EphValues;

375

377 Metrics.analyzeBasicBlock(OrigHeader, *TTI, EphValues, PrepareForLTO);

378 if (Metrics.notDuplicatable) {

380 dbgs() << "LoopRotation: NOT rotating - contains non-duplicatable"

381 << " instructions: ";

382 L->dump());

383 return Rotated;

384 }

385 if (Metrics.Convergence != ConvergenceKind::None) {

386 LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains convergent "

387 "instructions: ";

388 L->dump());

389 return Rotated;

390 }

391 if ( Metrics .NumInsts.isValid()) {

392 LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains instructions"

393 " with invalid cost: ";

394 L->dump());

395 return Rotated;

396 }

397 if (Metrics.NumInsts > MaxHeaderSize) {

398 LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains "

400 << " instructions, which is more than the threshold ("

401 << MaxHeaderSize << " instructions): ";

402 L->dump());

403 ++NumNotRotatedDueToHeaderSize;

404 return Rotated;

405 }

406

407

408

409 if (PrepareForLTO && Metrics.NumInlineCandidates > 0)

410 return Rotated;

411 }

412

413

414 BasicBlock *OrigPreheader = L->getLoopPreheader();

415

416

417

418 if (!OrigPreheader || ->hasDedicatedExits())

419 return Rotated;

420

421

422

423

424

425

426 if (SE) {

428

429

430

431

433 }

434

435 LLVM_DEBUG(dbgs() << "LoopRotation: rotating "; L->dump());

438

439

440

441

444 bool BISuccsSwapped = L->contains(Exit);

445 if (BISuccsSwapped)

447 assert(NewHeader && "Unable to determine new loop header");

448 assert(L->contains(NewHeader) && ->contains(Exit) &&

449 "Unable to determine loop header and exit blocks");

450

451

452

454 "New header doesn't have one pred!");

456

457

458

461

462

463

467

468

469

471

472

473

474 using DbgHash =

475 std::pair<std::pair<hash_code, DILocalVariable *>, DIExpression *>;

476 auto makeHash = [](const DbgVariableRecord *D) -> DbgHash {

477 auto VarLocOps = D->location_ops();

479 D->getExpression()};

480 };

481

482 SmallDenseSet<DbgHash, 8> DbgRecords;

483

484

485 for (const DbgVariableRecord &DVR :

487 DbgRecords.insert(makeHash(&DVR));

488

489

490

491

493 for (Instruction &I : *OrigHeader)

495 NoAliasDeclInstructions.push_back(Decl);

496

497 Module *M = OrigHeader->getModule();

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

522

523 while (I != E) {

525

526

527

528

529

530

531

532 if (L->hasLoopInvariantOperands(Inst) && !Inst->mayReadFromMemory() &&

535

536

537

538

539

540

541

542

544

545 if (!NextDbgInsts.empty()) {

546 auto DbgValueRange =

550

551 for (DbgVariableRecord &DVR :

553 if (DbgRecords.count(makeHash(&DVR)))

554 DVR.eraseFromParent();

555 }

556

557 NextDbgInsts = I->getDbgRecordRange();

558

560

561 ++NumInstrsHoisted;

562 continue;

563 }

564

565

567 if (const DebugLoc &DL = C->getDebugLoc())

569

570 C->insertBefore(LoopEntryBranch->getIterator());

571

572 ++NumInstrsDuplicated;

573

574 if (!NextDbgInsts.empty()) {

575 auto Range = C->cloneDebugInfoFrom(Inst, NextDbgInsts.begin());

579

581 if (DbgRecords.count(makeHash(&DVR)))

582 DVR.eraseFromParent();

583 }

584

585

588

589

590

591

594

595

597 if (->mayHaveSideEffects()) {

598 C->eraseFromParent();

599 C = nullptr;

600 }

601 } else {

603 }

604 if (C) {

605

607

610

611

612 if (MSSAU)

614 }

615 }

616

617 if (!NoAliasDeclInstructions.empty()) {

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636

637

638

639

642 for (NoAliasScopeDeclInst *NAD : NoAliasDeclInstructions) {

643 LLVM_DEBUG(dbgs() << " Cloning llvm.experimental.noalias.scope.decl:"

644 << *NAD << "\n");

646 NewNAD->insertBefore(*NewHeader, NewHeaderInsertionPoint);

647 }

648

649

650

651 {

653

655 for (NoAliasScopeDeclInst *NAD : NoAliasDeclInstructions)

656 NoAliasDeclScopes.push_back(NAD->getScopeList());

657

658 LLVM_DEBUG(dbgs() << " Updating OrigHeader scopes\n");

660 "h.rot");

662

663

664

665

666

667

668 LLVM_DEBUG(dbgs() << " Updating part of OrigPreheader scopes\n");

669 auto *FirstDecl =

671 auto *LastInst = &OrigPreheader->back();

675

678 }

679 }

680

681

682

683

684 for (BasicBlock *SuccBB : successors(OrigHeader))

688

689

690

691

694

695

696

697 if (MSSAU) {

700 ValueMapMSSA);

701 }

702

704

705

707 &InsertedPHIs);

708

709

710

711

712 if (!InsertedPHIs.empty())

714

715

716 L->moveToHeader(NewHeader);

717 assert(L->getHeader() == NewHeader && "Latch block is our new header");

718

719

720 if (DT) {

721

722

724 {DominatorTree::Insert, OrigPreheader, Exit},

725 {DominatorTree::Insert, OrigPreheader, NewHeader},

726 {DominatorTree::Delete, OrigPreheader, OrigHeader}};

727

728 if (MSSAU) {

729 MSSAU->applyUpdates(Updates, *DT, true);

732 } else {

734 }

735 }

736

737

738

739

740

741

742

743

747 const bool HasConditionalPreHeader =

750

751 updateBranchWeights(*PHBI, *BI, HasConditionalPreHeader, BISuccsSwapped);

752

753 if (HasConditionalPreHeader) {

754

755

756

757

758

759

761 OrigPreheader, NewHeader,

762 CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA());

764

765

766

767

768

770 bool SplitLatchEdge = false;

771 for (BasicBlock *ExitPred : ExitPreds) {

772

773 Loop *PredLoop = LI->getLoopFor(ExitPred);

774 if (!PredLoop || PredLoop->contains(Exit) ||

776 continue;

777 SplitLatchEdge |= L->getLoopLatch() == ExitPred;

779 ExitPred, Exit,

780 CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA());

782 }

783 assert(SplitLatchEdge &&

784 "Despite splitting all preds, failed to split latch exit?");

785 (void)SplitLatchEdge;

786 } else {

787

788

789 Exit->removePredecessor(OrigPreheader, true );

793

794

795 if (DT)

797

798

799 if (MSSAU)

800 MSSAU->removeEdge(OrigPreheader, Exit);

801 }

802

803 assert(L->getLoopPreheader() && "Invalid loop preheader after loop rotation");

804 assert(L->getLoopLatch() && "Invalid loop latch after loop rotation");

805

808

809

810

811

812

813 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);

814 BasicBlock *PredBB = OrigHeader->getUniquePredecessor();

816 if (DidMerge)

818

821

823

824 return true;

825}

826

827

828

829

830

833 bool seenIncrement = false;

834 bool MultiExitLoop = false;

835

836 if (!L->getExitingBlock())

837 MultiExitLoop = true;

838

840

842 return false;

843

844 switch (I->getOpcode()) {

845 default:

846 return false;

847 case Instruction::GetElementPtr:

848

850 return false;

851

852 [[fallthrough]];

853 case Instruction::Add:

854 case Instruction::Sub:

855 case Instruction::And:

856 case Instruction::Or:

857 case Instruction::Xor:

858 case Instruction::Shl:

859 case Instruction::LShr:

860 case Instruction::AShr: {

863 ? I->getOperand(0)

864 : isa<Constant> (I->getOperand(1)) ? I->getOperand(1) : nullptr;

865 if (!IVOpnd)

866 return false;

867

868

869

870 if (MultiExitLoop) {

871 for (User *UseI : IVOpnd->users()) {

873 if (!L->contains(UserInst))

874 return false;

875 }

876 }

877

878 if (seenIncrement)

879 return false;

880 seenIncrement = true;

881 break;

882 }

883 case Instruction::Trunc:

884 case Instruction::ZExt:

885 case Instruction::SExt:

886

887 break;

888 }

889 }

890 return true;

891}

892

893

894

895

896

897

898

899

900

901bool LoopRotate::simplifyLoopLatch(Loop *L) {

904 return false;

905

908 return false;

909

911 if (!LastExit || ->isLoopExiting(LastExit))

912 return false;

913

915 if (!BI)

916 return false;

917

919 return false;

920

922 << LastExit->getName() << "\n");

923

924 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);

926 true);

927

928 if (SE) {

929

931 }

932

935

936 return true;

937}

938

939

940bool LoopRotate::processLoop(Loop *L) {

941

942 MDNode *LoopMD = L->getLoopID();

943

944 bool SimplifiedLatch = false;

945

946

947

948

949 if (!RotationOnly)

950 SimplifiedLatch = simplifyLoopLatch(L);

951

952 bool MadeChange = rotateLoop(L, SimplifiedLatch);

953 assert((!MadeChange || L->isLoopExiting(L->getLoopLatch())) &&

954 "Loop latch should be exiting after loop-rotate.");

955

956

957

958 if ((MadeChange || SimplifiedLatch) && LoopMD)

959 L->setLoopID(LoopMD);

960

961 return MadeChange || SimplifiedLatch;

962}

963

964

965

969 const SimplifyQuery &SQ, bool RotationOnly = true,

970 unsigned Threshold = unsigned(-1),

971 bool IsUtilMode = true, bool PrepareForLTO) {

972 LoopRotate LR(Threshold, LI, TTI, AC, DT, SE, MSSAU, SQ, RotationOnly,

973 IsUtilMode, PrepareForLTO);

974 return LR.processLoop(L);

975}

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

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

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

This file provides various utilities for inspecting and working with the control flow graph in LLVM I...

static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)

static constexpr uint32_t ZeroTripCountWeights[]

Definition LoopRotationUtils.cpp:50

static bool shouldSpeculateInstrs(BasicBlock::iterator Begin, BasicBlock::iterator End, Loop *L)

Determine whether the instructions in this range may be safely and cheaply speculated.

Definition LoopRotationUtils.cpp:831

static bool profitableToRotateLoopExitingLatch(Loop *L)

Definition LoopRotationUtils.cpp:184

static void updateBranchWeights(BranchInst &PreHeaderBI, BranchInst &LoopBI, bool HasConditionalPreHeader, bool SuccsSwapped)

Definition LoopRotationUtils.cpp:203

static void InsertNewValueIntoMap(ValueToValueMapTy &VM, Value *K, Value *V)

Insert (K, V) pair into the ValueToValueMap, and verify the key did not previously exist in the map,...

Definition LoopRotationUtils.cpp:86

static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader, BasicBlock *OrigPreheader, ValueToValueMapTy &ValueMap, ScalarEvolution *SE, SmallVectorImpl< PHINode * > *InsertedPHIs)

RewriteUsesOfClonedInstructions - We just cloned the instructions from the old header into the prehea...

Definition LoopRotationUtils.cpp:95

Machine Check Debug Module

This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...

ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))

uint64_t IntrinsicInst * II

This file contains the declarations for profiling metadata utility functions.

const SmallVectorImpl< MachineOperand > & Cond

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

A cache of @llvm.assume calls within a function.

LLVM_ABI void registerAssumption(AssumeInst *CI)

Add an @llvm.assume intrinsic to this function's cache.

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

const Instruction & back() const

bool hasAddressTaken() const

Returns true if there are any uses of this basic block other than direct branches,...

LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const

Returns an iterator to the first instruction in this block that is not a PHINode instruction.

LLVM_ABI const BasicBlock * getSinglePredecessor() const

Return the predecessor of this block if it has a single predecessor block.

LLVM_ABI void flushTerminatorDbgRecords()

Eject any debug-info trailing at the end of a block.

LLVM_ABI DbgMarker * getMarker(InstListType::iterator It)

Return the DbgMarker for the position given by It, so that DbgRecords can be inserted there.

InstListType::iterator iterator

Instruction iterators...

LLVM_ABI LLVMContext & getContext() const

Get the context in which this basic block lives.

void moveBefore(BasicBlock *MovePos)

Unlink this basic block from its current function and insert it into the function that MovePos lives ...

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

Conditional or Unconditional Branch instruction.

bool isConditional() const

static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)

BasicBlock * getSuccessor(unsigned i) const

bool isUnconditional() const

Value * getCondition() const

static iterator_range< simple_ilist< DbgRecord >::iterator > getEmptyDbgRecordRange()

LLVM_ABI const BasicBlock * getParent() const

Record of a variable value-assignment, aka a non instruction representation of the dbg....

void applyUpdates(ArrayRef< UpdateType > Updates)

Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...

void deleteEdge(NodeT *From, NodeT *To)

Inform the dominator tree about a CFG edge deletion and update the tree.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

bool isPresplitCoroutine() const

Determine if the function is presplit coroutine.

LLVM_ABI Instruction * clone() const

Create a copy of 'this' instruction that is identical in all ways except the following:

LLVM_ABI iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)

Clone any debug-info attached to From onto this instruction.

LLVM_ABI bool mayWriteToMemory() const LLVM_READONLY

Return true if this instruction may modify memory.

iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const

Return a range over the DbgRecords attached to this instruction.

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

LLVM_ABI void moveBefore(InstListType::iterator InsertPos)

Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...

LLVM_ABI void insertBefore(InstListType::iterator InsertPos)

Insert an unlinked instruction into a basic block immediately before the specified position.

LLVM_ABI InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

LLVM_ABI const Function * getFunction() const

Return the function this instruction belongs to.

bool isTerminator() const

LLVM_ABI bool mayReadFromMemory() const LLVM_READONLY

Return true if this instruction may read memory.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

bool contains(const LoopT *L) const

Return true if the specified loop is contained within in this loop.

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

bool replacementPreservesLCSSAForm(Instruction *From, Value *To)

Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.

Represents a single loop in the control flow graph.

MemorySSA * getMemorySSA() const

Get handle on MemorySSA.

LLVM_ABI void removeEdge(BasicBlock *From, BasicBlock *To)

Update the MemoryPhi in To following an edge deletion between From and To.

LLVM_ABI void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM)

LLVM_ABI void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)

Apply CFG updates, analogous with the DT edge updates.

LLVM_ABI void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const

Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...

void addIncoming(Value *V, BasicBlock *BB)

Add an incoming value to the end of the PHI list.

Value * getIncomingValueForBlock(const BasicBlock *BB) const

static LLVM_ABI PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

Helper class for SSA formation on a set of values defined in multiple blocks.

The main scalar evolution driver.

LLVM_ABI void forgetTopmostLoop(const Loop *L)

LLVM_ABI void forgetValue(Value *V)

This method should be called by the client when it has changed a value in a way that may effect its v...

LLVM_ABI void forgetBlockAndLoopDispositions(Value *V=nullptr)

Called when the client has changed the disposition of values in a loop or block.

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

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 pass provides access to the codegen interfaces that are needed for IR-level transformations.

A Use represents the edge between a Value definition and its users.

ValueT lookup(const KeyT &Val) const

lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

LLVM Value Representation.

Type * getType() const

All values are typed, get the type of this value.

LLVM_ABI void setName(const Twine &Name)

Change the name of the value.

iterator_range< user_iterator > users()

iterator_range< use_iterator > uses()

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

LLVM_ABI void dump() const

Support for debugging, callable in GDB: V->dump()

std::pair< iterator, bool > insert(const ValueT &V)

size_type count(const_arg_type_t< ValueT > V) const

Return 1 if the specified key is in the set, 0 otherwise.

const ParentTy * getParent() const

self_iterator getIterator()

@ C

The default llvm calling convention, compatible with C.

@ BasicBlock

Various leaf nodes.

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

LLVM_ABI bool RemoveRedundantDbgInstrs(BasicBlock *BB)

Try to remove redundant dbg.value instructions from given basic block.

LLVM_ABI void findDbgValues(Value *V, SmallVectorImpl< DbgVariableRecord * > &DbgVariableRecords)

Finds the dbg.values describing a value.

decltype(auto) dyn_cast(const From &Val)

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

auto successors(const MachineBasicBlock *BB)

LLVM_ABI MDNode * getBranchWeightMDNode(const Instruction &I)

Get the branch weights metadata node.

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

LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)

Return true if the instruction does not have any effects besides calculating the result and does not ...

LLVM_ABI void insertDebugValuesForPHIs(BasicBlock *BB, SmallVectorImpl< PHINode * > &InsertedPHIs)

Propagate dbg.value intrinsics through the newly inserted PHIs.

LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)

See if we can compute a simplified version of this instruction.

LLVM_ABI void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected, bool ElideAllZero=false)

Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...

bool any_of(R &&range, UnaryPredicate P)

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

void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)

Remap the Values used in the DbgRecords Range using the value map VM.

@ RF_IgnoreMissingLocals

If this flag is set, the remapper ignores missing function-local entries (Argument,...

@ RF_NoModuleLevelChanges

If this flag is set, the remapper knows that only local values within a function (such as an instruct...

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

bool isa(const From &Val)

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

iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >

LLVM_ABI void extractFromBranchWeightMD32(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)

Faster version of extractBranchWeights() that skips checks and must only be called with "branch_weigh...

LLVM_ABI bool VerifyMemorySSA

Enables verification of MemorySSA.

LLVM_ABI bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)

Attempts to merge a block into its predecessor, if possible.

void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)

Convert the instruction operands from referencing the current values into those specified by VM.

LLVM_ABI BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")

If this edge is a critical edge, insert a new node to split the critical edge.

LLVM_ABI void cloneAndAdaptNoAliasScopes(ArrayRef< MDNode * > NoAliasDeclScopes, ArrayRef< BasicBlock * > NewBlocks, LLVMContext &Context, StringRef Ext)

Clone the specified noalias decl scopes.

LLVM_ABI bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)

We know that BB has one predecessor.

ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy

decltype(auto) cast(const From &Val)

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

auto predecessors(const MachineBasicBlock *BB)

static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)

Filter the DbgRecord range to DbgVariableRecord types only and downcast.

LLVM_ABI bool LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI, AssumptionCache *AC, DominatorTree *DT, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, const SimplifyQuery &SQ, bool RotationOnly, unsigned Threshold, bool IsUtilMode, bool PrepareForLTO=false)

Convert a loop into a loop with bottom test.

Definition LoopRotationUtils.cpp:966

hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)

Compute a hash_code for a sequence of values.

LLVM_ABI void mapAtomInstance(const DebugLoc &DL, ValueToValueMapTy &VMap)

Mark a cloned instruction as a new instance so that its source loc can be updated when remapped.

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

Implement std::swap in terms of BitVector swap.

static LLVM_ABI void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)

Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).