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");

48 STATISTIC(NumRotated, "Number of loops rotated");

52 cl::desc("Allow loop rotation multiple times in order to reach "

53 "a better latch exit"));

58namespace {

60class LoopRotate {

61 const unsigned MaxHeaderSize;

69 bool RotationOnly;

70 bool IsUtilMode;

71 bool PrepareForLTO;

73public:

74 LoopRotate(unsigned MaxHeaderSize, LoopInfo *LI,

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

78 bool PrepareForLTO)

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

80 MSSAU(MSSAU), SQ(SQ), RotationOnly(RotationOnly),

81 IsUtilMode(IsUtilMode), PrepareForLTO(PrepareForLTO) {}

82 bool processLoop(Loop *L);

84private:

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

86 bool simplifyLoopLatch(Loop *L);

87};

88}

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

95 (void)Inserted;

96}

100

106

108 for (I = OrigHeader->begin(); PHINode *PN = dyn_cast(I); ++I)

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

110

111

112

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

115 Value *OrigHeaderVal = &*I;

116

117

118

120 continue;

121

123

124

125

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

127

128

129 if (SE)

131 SSA.AddAvailableValue(OrigHeader, OrigHeaderVal);

132 SSA.AddAvailableValue(OrigPreheader, OrigPreHeaderVal);

133

134

136

137

138 Instruction *UserInst = cast(U.getUser());

139 if (!isa(UserInst)) {

141

142

143

144 if (UserBB == OrigHeader)

145 continue;

146

147

148

149 if (UserBB == OrigPreheader) {

150 U = OrigPreHeaderVal;

151 continue;

152 }

153 }

154

155

156 SSA.RewriteUse(U);

157 }

158

159

160

164 for (auto &DbgValue : DbgValues) {

165

166

168 if (UserBB == OrigHeader)

169 continue;

170

171

172

173

174

176 if (UserBB == OrigPreheader)

177 NewVal = OrigPreHeaderVal;

178 else if (SSA.HasValueForBlock(UserBB))

179 NewVal = SSA.GetValueInMiddleOfBlock(UserBB);

180 else

182 DbgValue->replaceVariableLocationOp(OrigHeaderVal, NewVal);

183 }

184

185

186

188

189

191 if (UserBB == OrigHeader)

192 continue;

193

194

195

196

197

199 if (UserBB == OrigPreheader)

200 NewVal = OrigPreHeaderVal;

201 else if (SSA.HasValueForBlock(UserBB))

202 NewVal = SSA.GetValueInMiddleOfBlock(UserBB);

203 else

205 DVR->replaceVariableLocationOp(OrigHeaderVal, NewVal);

206 }

207 }

208}

209

210

211

212

215 BranchInst *BI = dyn_cast(Header->getTerminator());

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

218 if (L->contains(HeaderExit))

220

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

222

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

225 }))

226 continue;

227 return true;

228 }

229 return false;

230}

231

232

233

234

235

236

237

239 BasicBlock *Latch = L->getLoopLatch();

240 assert(Latch && "need latch");

242

244 return false;

245

247 if (L->contains(Exit))

249

250

251 if (!Exit->getPostdominatingDeoptimizeCall())

252 return false;

253

255 L->getUniqueExitBlocks(Exits);

256 if (!Exits.empty()) {

257

258

259

260

261

262

263

264

265

266

267

268

271 });

272 }

273 return false;

274}

275

277 bool HasConditionalPreHeader,

278 bool SuccsSwapped) {

280 if (WeightMD == nullptr)

281 return;

282

283

284

285

287 return;

288

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

292 return;

293 uint32_t OrigLoopExitWeight = Weights[0];

294 uint32_t OrigLoopBackedgeWeight = Weights[1];

295

296 if (SuccsSwapped)

297 std::swap(OrigLoopExitWeight, OrigLoopBackedgeWeight);

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322 uint32_t ExitWeight0;

323 uint32_t ExitWeight1;

324 uint32_t EnterWeight;

325 uint32_t LoopBackWeight;

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

327 ExitWeight0 = 0;

328 if (HasConditionalPreHeader) {

329

330 if (OrigLoopBackedgeWeight >= OrigLoopExitWeight) {

331

332

334

335

337

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

340 (OrigLoopExitWeight & HighBit) != 0)

341 break;

342 OrigLoopBackedgeWeight <<= 1;

343 OrigLoopExitWeight <<= 1;

344 }

345 } else {

346

347

348 ExitWeight0 = OrigLoopExitWeight - OrigLoopBackedgeWeight;

349 }

350 } else {

351

352

353

354

355

356 if (OrigLoopExitWeight > OrigLoopBackedgeWeight)

357 OrigLoopBackedgeWeight = OrigLoopExitWeight;

358 }

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

360 ExitWeight1 = OrigLoopExitWeight - ExitWeight0;

361 EnterWeight = ExitWeight1;

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

363 LoopBackWeight = OrigLoopBackedgeWeight - EnterWeight;

364 } else if (OrigLoopExitWeight == 0) {

365 if (OrigLoopBackedgeWeight == 0) {

366

367 ExitWeight0 = 0;

368 ExitWeight1 = 0;

369 EnterWeight = 0;

370 LoopBackWeight = 0;

371 } else {

372

373

374

375 ExitWeight0 = 0;

376 ExitWeight1 = 0;

377 EnterWeight = 1;

378 LoopBackWeight = OrigLoopBackedgeWeight;

379 }

380 } else {

381

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

383 ExitWeight0 = 1;

384 ExitWeight1 = 1;

385 EnterWeight = 0;

386 LoopBackWeight = 0;

387 }

388

389 const uint32_t LoopBIWeights[] = {

390 SuccsSwapped ? LoopBackWeight : ExitWeight1,

391 SuccsSwapped ? ExitWeight1 : LoopBackWeight,

392 };

393 setBranchWeights(LoopBI, LoopBIWeights, false);

394 if (HasConditionalPreHeader) {

395 const uint32_t PreHeaderBIWeights[] = {

396 SuccsSwapped ? EnterWeight : ExitWeight0,

397 SuccsSwapped ? ExitWeight0 : EnterWeight,

398 };

399 setBranchWeights(PreHeaderBI, PreHeaderBIWeights, false);

400 }

401}

402

403

404

405

406

407

408

409

410

411

412

413

414

415

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

417

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

419 return false;

420

421 bool Rotated = false;

422 do {

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

425

428 return Rotated;

429

430

431

432

433 if (->isLoopExiting(OrigHeader))

434 return Rotated;

435

436

437

438 if (!OrigLatch)

439 return Rotated;

440

441

442

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

446 return Rotated;

447

448

449

450 {

453

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

456 if (Metrics.notDuplicatable) {

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

459 << " instructions: ";

460 L->dump());

461 return Rotated;

462 }

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

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

465 "instructions: ";

466 L->dump());

467 return Rotated;

468 }

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

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

471 " with invalid cost: ";

472 L->dump());

473 return Rotated;

474 }

475 if (Metrics.NumInsts > MaxHeaderSize) {

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

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

479 << MaxHeaderSize << " instructions): ";

480 L->dump());

481 ++NumNotRotatedDueToHeaderSize;

482 return Rotated;

483 }

484

485

486

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

488 return Rotated;

489 }

490

491

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

493

494

495

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

497 return Rotated;

498

499

500

501

502

503

504 if (SE) {

505 SE->forgetTopmostLoop(L);

506

507

508

509

510 SE->forgetBlockAndLoopDispositions();

511 }

512

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

515 MSSAU->getMemorySSA()->verifyMemorySSA();

516

517

518

519

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

523 if (BISuccsSwapped)

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

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

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

528

529

530

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

534

535

536

539

540

541

542 for (; PHINode *PN = dyn_cast(I); ++I)

545

546

547

549

550

551

552 using DbgIntrinsicHash =

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

554 auto makeHash = [](auto *D) -> DbgIntrinsicHash {

555 auto VarLocOps = D->location_ops();

557 D->getVariable()},

558 D->getExpression()};

559 };

560

563 if (auto *DII = dyn_cast(&I)) {

564 DbgIntrinsics.insert(makeHash(DII));

565

566

567

570 DbgIntrinsics.insert(makeHash(&DVR));

571 } else {

572 break;

573 }

574 }

575

576

577

580 DbgIntrinsics.insert(makeHash(&DVR));

581

582

583

584

587 if (auto *Decl = dyn_cast(&I))

588 NoAliasDeclInstructions.push_back(Decl);

589

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

591

592

593

594

595

596

597

598

599

600

601

602

603

604

605

606

607

608

609

610

611

612

615

616 while (I != E) {

618

619

620

621

622

623

624

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

627 !isa(Inst) && !isa(Inst) &&

628

629

630

631

632

633

634

635

637

638 if (LoopEntryBranch->getParent()->IsNewDbgInfoFormat &&

639 !NextDbgInsts.empty()) {

640 auto DbgValueRange =

644

647 if (DbgIntrinsics.count(makeHash(&DVR)))

648 DVR.eraseFromParent();

649 }

650

651 NextDbgInsts = I->getDbgRecordRange();

652

654

655 ++NumInstrsHoisted;

656 continue;

657 }

658

659

661 C->insertBefore(LoopEntryBranch);

662

663 ++NumInstrsDuplicated;

664

665 if (LoopEntryBranch->getParent()->IsNewDbgInfoFormat &&

666 !NextDbgInsts.empty()) {

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

671

674 if (DbgIntrinsics.count(makeHash(&DVR)))

675 DVR.eraseFromParent();

676 }

677

678

681

682

683 if (auto *DII = dyn_cast(C))

684 if (DbgIntrinsics.count(makeHash(DII))) {

685 C->eraseFromParent();

686 continue;

687 }

688

689

690

691

693 if (V && LI->replacementPreservesLCSSAForm(C, V)) {

694

695

697 if (->mayHaveSideEffects()) {

698 C->eraseFromParent();

699 C = nullptr;

700 }

701 } else {

703 }

704 if (C) {

705

707

708 if (auto *II = dyn_cast(C))

709 AC->registerAssumption(II);

710

711

712 if (MSSAU)

714 }

715 }

716

717 if (!NoAliasDeclInstructions.empty()) {

718

719

720

721

722

723

724

725

726

727

728

729

730

731

732

733

734

735

736

737

738

739

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

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

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

747 }

748

749

750

751 {

752 auto &Context = NewHeader->getContext();

753

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

757

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

760 "h.rot");

762

763

764

765

766

767

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

769 auto *FirstDecl =

770 cast(ValueMap[*NoAliasDeclInstructions.begin()]);

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

773 Context, "pre.rot");

775

778 }

779 }

780

781

782

783

786 PHINode *PN = dyn_cast(BI); ++BI)

788

789

790

791

794

795

796

797 if (MSSAU) {

799 MSSAU->updateForClonedBlockIntoPred(OrigHeader, OrigPreheader,

800 ValueMapMSSA);

801 }

802

804

805

807 &InsertedPHIs);

808

809

810

811

812 if (!InsertedPHIs.empty())

814

815

816 L->moveToHeader(NewHeader);

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

818

819

820 if (DT) {

821

822

824 Updates.push_back({DominatorTree::Insert, OrigPreheader, Exit});

825 Updates.push_back({DominatorTree::Insert, OrigPreheader, NewHeader});

826 Updates.push_back({DominatorTree::Delete, OrigPreheader, OrigHeader});

827

828 if (MSSAU) {

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

831 MSSAU->getMemorySSA()->verifyMemorySSA();

832 } else {

834 }

835 }

836

837

838

839

840

841

842

843

847 const bool HasConditionalPreHeader =

848 !isa(Cond) ||

850

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

852

853 if (HasConditionalPreHeader) {

854

855

856

857

858

859

861 OrigPreheader, NewHeader,

864

865

866

867

868

870 bool SplitLatchEdge = false;

871 for (BasicBlock *ExitPred : ExitPreds) {

872

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

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

875 isa(ExitPred->getTerminator()))

876 continue;

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

879 ExitPred, Exit,

882 }

883 assert(SplitLatchEdge &&

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

885 (void)SplitLatchEdge;

886 } else {

887

888

889 Exit->removePredecessor(OrigPreheader, true );

893

894

895 if (DT) DT->deleteEdge(OrigPreheader, Exit);

896

897

898 if (MSSAU)

899 MSSAU->removeEdge(OrigPreheader, Exit);

900 }

901

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

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

904

906 MSSAU->getMemorySSA()->verifyMemorySSA();

907

908

909

910

911

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

915 if (DidMerge)

917

919 MSSAU->getMemorySSA()->verifyMemorySSA();

920

922

923 ++NumRotated;

924

925 Rotated = true;

926 SimplifiedLatch = false;

927

928

929

930

931

933

934

935 return true;

936}

937

938

939

940

941

944 bool seenIncrement = false;

945 bool MultiExitLoop = false;

946

947 if (!L->getExitingBlock())

948 MultiExitLoop = true;

949

951

953 return false;

954

955 if (isa(I))

956 continue;

957

958 switch (I->getOpcode()) {

959 default:

960 return false;

961 case Instruction::GetElementPtr:

962

963 if (!cast(I)->hasAllConstantIndices())

964 return false;

965

966 [[fallthrough]];

967 case Instruction::Add:

968 case Instruction::Sub:

969 case Instruction::And:

970 case Instruction::Or:

971 case Instruction::Xor:

972 case Instruction::Shl:

973 case Instruction::LShr:

974 case Instruction::AShr: {

976 !isa(I->getOperand(0))

977 ? I->getOperand(0)

978 : !isa(I->getOperand(1)) ? I->getOperand(1) : nullptr;

979 if (!IVOpnd)

980 return false;

981

982

983

984 if (MultiExitLoop) {

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

986 auto *UserInst = cast(UseI);

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

988 return false;

989 }

990 }

991

992 if (seenIncrement)

993 return false;

994 seenIncrement = true;

995 break;

996 }

997 case Instruction::Trunc:

998 case Instruction::ZExt:

999 case Instruction::SExt:

1000

1001 break;

1002 }

1003 }

1004 return true;

1005}

1006

1007

1008

1009

1010

1011

1012

1013

1014

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

1018 return false;

1019

1022 return false;

1023

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

1026 return false;

1027

1029 if (!BI)

1030 return false;

1031

1033 return false;

1034

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

1037

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

1040 true);

1041

1042 if (SE) {

1043

1044 SE->forgetBlockAndLoopDispositions();

1045 }

1046

1048 MSSAU->getMemorySSA()->verifyMemorySSA();

1049

1050 return true;

1051}

1052

1053

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

1055

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

1057

1058 bool SimplifiedLatch = false;

1059

1060

1061

1062

1063 if (!RotationOnly)

1064 SimplifiedLatch = simplifyLoopLatch(L);

1065

1066 bool MadeChange = rotateLoop(L, SimplifiedLatch);

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

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

1069

1070

1071

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

1073 L->setLoopID(LoopMD);

1074

1075 return MadeChange || SimplifiedLatch;

1076}

1077

1078

1079

1083 const SimplifyQuery &SQ, bool RotationOnly = true,

1084 unsigned Threshold = unsigned(-1),

1085 bool IsUtilMode = true, bool PrepareForLTO) {

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

1087 IsUtilMode, PrepareForLTO);

1088 return LR.processLoop(L);

1089}

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

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[]

static bool canRotateDeoptimizingLatchExit(Loop *L)

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

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

static cl::opt< bool > MultiRotate("loop-rotate-multi", cl::init(false), cl::Hidden, cl::desc("Allow loop rotation multiple times in order to reach " "a better latch exit"))

static bool profitableToRotateLoopExitingLatch(Loop *L)

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

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

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

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

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

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

#define STATISTIC(VARNAME, DESC)

Class recording the (high level) value of a variable.

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

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

bool hasAddressTaken() const

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

InstListType::const_iterator getFirstNonPHIIt() const

Iterator returning form of getFirstNonPHI.

const BasicBlock * getSinglePredecessor() const

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

const BasicBlock * getUniquePredecessor() const

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

void flushTerminatorDbgRecords()

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

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

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

const CallInst * getPostdominatingDeoptimizeCall() const

Returns the call instruction calling @llvm.experimental.deoptimize that is present either in current ...

const Instruction & back() const

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()

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.

Instruction * clone() const

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

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.

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.

void insertBefore(Instruction *InsertPos)

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

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

InstListType::iterator eraseFromParent()

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

const Function * getFunction() const

Return the function this instruction belongs to.

bool isTerminator() const

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.

void moveBefore(Instruction *MovePos)

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

bool contains(const LoopT *L) const

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

Represents a single loop in the control flow graph.

A Module instance is used to store all the information related to an LLVM module.

void addIncoming(Value *V, BasicBlock *BB)

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

Value * getIncomingValueForBlock(const BasicBlock *BB) const

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

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

Implements a dense probed hash-table based set with some number of buckets stored inline.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

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.

void setName(const Twine &Name)

Change the name of the value.

iterator_range< user_iterator > users()

iterator_range< use_iterator > uses()

StringRef getName() const

Return a constant reference to the value's name.

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()

A range adaptor for a pair of iterators.

@ C

The default llvm calling convention, compatible with C.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

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

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

bool RemoveRedundantDbgInstrs(BasicBlock *BB)

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

auto successors(const MachineBasicBlock *BB)

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

void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V, SmallVectorImpl< DbgVariableRecord * > *DbgVariableRecords=nullptr)

Finds the llvm.dbg.value intrinsics describing a value.

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

Propagate dbg.value intrinsics through the newly inserted PHIs.

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

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

bool any_of(R &&range, UnaryPredicate P)

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

auto reverse(ContainerTy &&C)

void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected)

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

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

raw_ostream & dbgs()

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

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

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

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

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

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

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

bool VerifyMemorySSA

Enables verification of MemorySSA.

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.

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.

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

Clone the specified noalias decl scopes.

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

We know that BB has one predecessor.

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.

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.

hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)

Compute a hash_code for a sequence of values.

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

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

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

Implement std::swap in terms of BitVector swap.

Utility to calculate the size and a few similar metrics for a set of basic blocks.

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

Option class for critical edge splitting.