LoopUnroll.cpp Source File (original) (raw)

67#include <assert.h>

68#include

69#include

71namespace llvm {

74}

76using namespace llvm;

78#define DEBUG_TYPE "loop-unroll"

81 STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled");

82 STATISTIC(NumUnrolled, "Number of loops unrolled (completely or otherwise)");

83 STATISTIC(NumUnrolledNotLatch, "Number of loops unrolled without a conditional "

84 "latch (completely or otherwise)");

88 cl::desc("Allow runtime unrolled loops to be unrolled "

89 "with epilog instead of prolog."));

93 cl::desc("Verify domtree after unrolling"),

94#ifdef EXPENSIVE_CHECKS

96#else

98#endif

99 );

100

103 cl::desc("Verify loopinfo after unrolling"),

104#ifdef EXPENSIVE_CHECKS

106#else

108#endif

109 );

110

113 cl::desc("Allow unrolling to add parallel reduction phis."));

114

115

116

117

118

119

120

121

122

123

125 const std::vector<BasicBlock *> &Blocks,

129 continue;

131 for (Use &U : I.operands()) {

134 if (!DefLoop)

135 continue;

137 return true;

138 }

139 }

140 }

141 }

142 return false;

143}

144

145

146

147

148

152

154 assert(OldLoop && "Should (at least) be in the loop being unrolled!");

155

156 Loop *&NewLoop = NewLoops[OldLoop];

157 if (!NewLoop) {

158

160 "Header should be first in RPO");

161

164

165 if (NewLoopParent)

167 else

169

171 return OldLoop;

172 } else {

174 return nullptr;

175 }

176}

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

204 BasicBlock *PreHeader = L->getLoopPreheader();

206 assert(PreHeader && Header);

207 for (const PHINode &PN : Header->phis()) {

208 if (isa(PN.getIncomingValueForBlock(PreHeader)))

209 return true;

210 }

211 return false;

212}

213

221

224 unsigned CurrentGeneration;

225 unsigned ChildGeneration;

229 bool Processed = false;

230

231public:

235 : LoadScope(AvailableLoads), CurrentGeneration(cg), ChildGeneration(cg),

236 Node(N), ChildIter(Child), EndIter(End) {}

237

243

246 ++ChildIter;

247 return Child;

248 }

249

253};

254

258 if (!LV.DefI)

259 return nullptr;

261 return nullptr;

262 if (LV.Generation != CurrentGeneration) {

264 if (!MSSA)

265 return nullptr;

269 if (!MSSA->dominates(LaterDef, EarlierMA))

270 return nullptr;

271 }

272 return LV.DefI;

273}

274

281 HeaderD->begin(), HeaderD->end()));

282

283 unsigned CurrentGeneration = 0;

284 while (!NodesToProcess.empty()) {

285 StackNode *NodeToProcess = &*NodesToProcess.back();

286

288

290

291

292

293

294

295

296

297

298

300 ++CurrentGeneration;

302

304 if (!Load || !Load->isSimple()) {

305 if (I.mayWriteToMemory())

306 CurrentGeneration++;

307 continue;

308 }

309

310 const SCEV *PtrSCEV = SE.getSCEV(Load->getPointerOperand());

313 getMatchingValue(LV, Load, CurrentGeneration, BAA, GetMSSA)) {

315 Load->replaceAllUsesWith(M);

316 Load->eraseFromParent();

317 }

318 } else {

319 AvailableLoads.insert(PtrSCEV, LoadValue(Load, CurrentGeneration));

320 }

321 }

323 NodeToProcess->process();

324 } else if (NodeToProcess->childIter() != NodeToProcess->end()) {

325

327 if (!L->contains(Child->getBlock()))

328 continue;

331 Child->begin(), Child->end()));

332 } else {

333

334

336 }

337 }

338}

339

340

341

342

349

350

351 if (SE && SimplifyIVs) {

354

355

356

357 while (!DeadInsts.empty()) {

361 }

362

363 if (AA) {

364 std::unique_ptr MSSA = nullptr;

367 if (!MSSA)

369 return &*MSSA;

370 });

371 }

372 }

373

374

375

376 const DataLayout &DL = L->getHeader()->getDataLayout();

378 for (BasicBlock *BB : L->getBlocks()) {

379

380 if (BB->getParent()->getSubprogram())

382

386 Inst.replaceAllUsesWith(V);

389

390

391

392

393

394 {

396 const APInt *C1, *C2;

400 bool SignedOverflow;

401 APInt NewC = C1->sadd_ov(*C2, SignedOverflow);

402 Inst.setOperand(0, X);

403 Inst.setOperand(1, ConstantInt::get(Inst.getType(), NewC));

404 Inst.setHasNoUnsignedWrap(Inst.hasNoUnsignedWrap() &&

405 InnerOBO->hasNoUnsignedWrap());

406 Inst.setHasNoSignedWrap(Inst.hasNoSignedWrap() &&

407 InnerOBO->hasNoSignedWrap() &&

408 !SignedOverflow);

411 }

412 }

413 }

414

415

416

418 }

419}

420

421

422

426 return false;

427

428

429 for (auto &BB : L->blocks()) {

430 for (auto &I : *BB) {

432 return true;

434 if (CB->isConvergent())

435 return CB->getConvergenceControlToken();

436 }

437 }

438 return true;

439}

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

462 bool PreserveLCSSA, Loop **RemainderLoop, AAResults *AA) {

463 assert(DT && "DomTree is required");

464

465 if (!L->getLoopPreheader()) {

466 LLVM_DEBUG(dbgs() << " Can't unroll; loop preheader-insertion failed.\n");

468 }

469

470 if (!L->getLoopLatch()) {

471 LLVM_DEBUG(dbgs() << " Can't unroll; loop exit-block-insertion failed.\n");

473 }

474

475

476 if (!L->isSafeToClone()) {

477 LLVM_DEBUG(dbgs() << " Can't unroll; Loop body cannot be cloned.\n");

479 }

480

481 if (L->getHeader()->hasAddressTaken()) {

482

484 dbgs() << " Won't unroll loop: address of header block is taken.\n");

486 }

487

489

490

491

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

494 BasicBlock *LatchBlock = L->getLoopLatch();

496 L->getExitBlocks(ExitBlocks);

497 std::vector<BasicBlock *> OriginalLoopBlocks = L->getBlocks();

498

501 std::optional OriginalTripCount =

504

505

506

507 if (MaxTripCount && ULO.Count > MaxTripCount)

508 ULO.Count = MaxTripCount;

509

510 struct ExitInfo {

511 unsigned TripCount;

512 unsigned TripMultiple;

513 unsigned BreakoutTrip;

514 bool ExitOnTrue;

515 BasicBlock *FirstExitingBlock = nullptr;

517 };

520 L->getExitingBlocks(ExitingBlocks);

521 for (auto *ExitingBlock : ExitingBlocks) {

522

523

525 if (!BI)

526 continue;

527

528 ExitInfo &Info = ExitInfos[ExitingBlock];

531 if (Info.TripCount != 0) {

532 Info.BreakoutTrip = Info.TripCount % ULO.Count;

533 Info.TripMultiple = 0;

534 } else {

535 Info.BreakoutTrip = Info.TripMultiple =

536 (unsigned)std::gcd(ULO.Count, Info.TripMultiple);

537 }

538 Info.ExitOnTrue = !L->contains(BI->getSuccessor(0));

539 Info.ExitingBlocks.push_back(ExitingBlock);

540 LLVM_DEBUG(dbgs() << " Exiting block %" << ExitingBlock->getName()

541 << ": TripCount=" << Info.TripCount

542 << ", TripMultiple=" << Info.TripMultiple

543 << ", BreakoutTrip=" << Info.BreakoutTrip << "\n");

544 }

545

546

547

548

549 const bool CompletelyUnroll = ULO.Count == MaxTripCount;

550

551 const bool PreserveOnlyFirst = CompletelyUnroll && MaxOrZero;

552

553

554

555 if (CompletelyUnroll)

557

558

559

560

561

562

563

564 bool NeedToFixLCSSA =

565 PreserveLCSSA && CompletelyUnroll &&

568

569

570

571

572

573

574

576

577

578

579 bool LatchIsExiting = L->isLoopExiting(LatchBlock);

580 if (!LatchBI || (LatchBI->isConditional() && !LatchIsExiting)) {

582 dbgs() << "Can't unroll; a conditional latch must exit the loop");

584 }

585

587 "Can't runtime unroll if loop contains a convergent operation.");

588

589 bool EpilogProfitability =

592

598 RemainderLoop, OriginalTripCount, OriginalLoopProb)) {

601 else {

602 LLVM_DEBUG(dbgs() << "Won't unroll; remainder loop could not be "

603 "generated when assuming runtime trip count\n");

605 }

606 }

607

608 using namespace ore;

609

610 if (CompletelyUnroll) {

611 LLVM_DEBUG(dbgs() << "COMPLETELY UNROLLING loop %" << Header->getName()

612 << " with trip count " << ULO.Count << "!\n");

613 if (ORE)

614 ORE->emit([&]() {

616 L->getHeader())

617 << "completely unrolled loop with "

618 << NV("UnrollCount", ULO.Count) << " iterations";

619 });

620 } else {

621 LLVM_DEBUG(dbgs() << "UNROLLING loop %" << Header->getName() << " by "

626

627 if (ORE)

628 ORE->emit([&]() {

630 L->getHeader());

631 Diag << "unrolled loop by a factor of " << NV("UnrollCount", ULO.Count);

633 Diag << " with run-time trip count";

634 return Diag;

635 });

636 }

637

638

639

640

641

642

643

644

645

646 if (SE) {

649 else {

652 }

653 }

654

655 if (!LatchIsExiting)

656 ++NumUnrolledNotLatch;

657

658

659

661 std::vector<PHINode*> OrigPHINode;

664 }

665

666

667

668

669

670

672 bool CanAddAdditionalAccumulators =

676 !CompletelyUnroll && L->getNumBlocks() == 1 &&

678 (ExitInfos.contains(Header) && ((ExitInfos[Header].TripCount != 0 &&

679 ExitInfos[Header].BreakoutTrip == 0))));

680

681

682

683

684

685

686 if (CanAddAdditionalAccumulators && ULO.Count <= 4) {

687 for (PHINode &Phi : Header->phis()) {

689 if (!RdxDesc)

690 continue;

691

692

693

695 continue;

696

698 }

699 }

700

701 std::vector<BasicBlock *> Headers;

702 std::vector<BasicBlock *> Latches;

703 Headers.push_back(Header);

704 Latches.push_back(LatchBlock);

705

706

707

708

711

712

715

716 std::vector<BasicBlock*> UnrolledLoopBlocks = L->getBlocks();

717

718

719

720

721

724

725

726

727 if (Header->getParent()->shouldEmitDebugInfoForProfiling() &&

729 for (BasicBlock *BB : L->getBlocks())

731 if (.isDebugOrPseudoInst())

732 if (const DILocation *DIL = I.getDebugLoc()) {

733 auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(ULO.Count);

734 if (NewDIL)

735 I.setDebugLoc(*NewDIL);

736 else

738 << "Failed to create new discriminator: "

739 << DIL->getFilename() << " Line: " << DIL->getLine());

740 }

741

742

743

746

747

748

749

750 auto BlockInsertPt = std::next(LatchBlock->getIterator());

752 for (unsigned It = 1; It != ULO.Count; ++It) {

755 NewLoops[L] = L;

756

760 Header->getParent()->insert(BlockInsertPt, New);

761

763 "Header should not be in a sub-loop");

764

766 if (OldLoop)

767 LoopsToSimplify.insert(NewLoops[OldLoop]);

768

769 if (*BB == Header) {

770

771

772 for (PHINode *OrigPHI : OrigPHINode) {

775

776

777

779

780 if (PartialReductions.empty())

783

784

785

788 L->getLoopPreheader(),

790 OrigPHI->getType(),

792

793

794

796 NewPHI->moveBefore(OrigPHI->getIterator());

797 continue;

798 }

799

801 if (It > 1 && L->contains(InValI))

802 InVal = LastValueMap[InValI];

803 VMap[OrigPHI] = InVal;

805 }

806

807

814 }

815 }

816

817

818

819

820

821 if (!VMap.AtomMap.empty())

824

825

826 LastValueMap[*BB] = New;

828 VI != VE; ++VI)

829 LastValueMap[VI->first] = VI->second;

830

831

833 if (L->contains(Succ))

834 continue;

838 if (It != LastValueMap.end())

842 }

843 }

844

845

846 if (*BB == Header)

847 Headers.push_back(New);

848 if (*BB == LatchBlock)

849 Latches.push_back(New);

850

851

852

853 auto ExitInfoIt = ExitInfos.find(*BB);

854 if (ExitInfoIt != ExitInfos.end())

855 ExitInfoIt->second.ExitingBlocks.push_back(New);

856

858 UnrolledLoopBlocks.push_back(New);

859

860

861

862

863

864 if (*BB == Header)

866 else {

867 auto BBDomNode = DT->getNode(*BB);

868 auto BBIDom = BBDomNode->getIDom();

869 BasicBlock *OriginalBBIDom = BBIDom->getBlock();

872 }

873 }

874

875

876

878 for (BasicBlock *NewBlock : NewBlocks)

882

883 {

884

885

886

887 std::string ext = (Twine("It") + Twine(It)).str();

889 Header->getContext(), ext);

890 }

891 }

892

893

894 for (PHINode *PN : OrigPHINode) {

895 if (CompletelyUnroll) {

896 PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader));

897 PN->eraseFromParent();

898 } else if (ULO.Count > 1) {

900 continue;

901

902 Value *InVal = PN->removeIncomingValue(LatchBlock, false);

903

904

906 if (L->contains(InValI))

907 InVal = LastValueMap[InVal];

908 }

909 assert(Latches.back() == LastValueMap[LatchBlock] && "bad last latch");

910 PN->addIncoming(InVal, Latches.back());

911 }

912 }

913

914

915

916 for (unsigned i = 0, e = Latches.size(); i != e; ++i) {

917 unsigned j = (i + 1) % e;

918 Latches[i]->getTerminator()->replaceSuccessorWith(Headers[i], Headers[j]);

919 }

920

921

922

923

924

925 if (ULO.Count > 1) {

926 for (auto *BB : OriginalLoopBlocks) {

927 auto *BBDomNode = DT->getNode(BB);

929 for (auto *ChildDomNode : BBDomNode->children()) {

930 auto *ChildBB = ChildDomNode->getBlock();

931 if (!L->contains(ChildBB))

932 ChildrenToUpdate.push_back(ChildBB);

933 }

934

935

936

937

939 for (auto *ChildBB : ChildrenToUpdate)

941 }

942 }

943

945 DT->verify(DominatorTree::VerificationLevel::Fast));

946

948 auto SetDest = [&](BasicBlock *Src, bool WillExit, bool ExitOnTrue) {

950 const unsigned Idx = ExitOnTrue ^ WillExit;

951 BasicBlock *Dest = Term->getSuccessor(Idx);

952 BasicBlock *DeadSucc = Term->getSuccessor(1-Idx);

953

954

956

957

959 BI->setDebugLoc(Term->getDebugLoc());

960 Term->eraseFromParent();

961

963 };

964

965 auto WillExit = [&](const ExitInfo &Info, unsigned i, unsigned j,

966 bool IsLatch) -> std::optional {

967 if (CompletelyUnroll) {

968 if (PreserveOnlyFirst) {

969 if (i == 0)

970 return std::nullopt;

971 return j == 0;

972 }

973

974 if (j == 0)

975 return true;

976 if (Info.TripCount && j != Info.TripCount)

977 return false;

978 return std::nullopt;

979 }

980

982

983

984 if (IsLatch && j != 0)

985 return false;

986 return std::nullopt;

987 }

988

989 if (j != Info.BreakoutTrip &&

990 (Info.TripMultiple == 0 || j % Info.TripMultiple != 0)) {

991

992

993 return false;

994 }

995 return std::nullopt;

996 };

997

998

999

1000 for (auto &Pair : ExitInfos) {

1001 ExitInfo &Info = Pair.second;

1002 for (unsigned i = 0, e = Info.ExitingBlocks.size(); i != e; ++i) {

1003

1004 unsigned j = (i + 1) % e;

1005 bool IsLatch = Pair.first == LatchBlock;

1006 std::optional KnownWillExit = WillExit(Info, i, j, IsLatch);

1007 if (!KnownWillExit) {

1008 if (!Info.FirstExitingBlock)

1009 Info.FirstExitingBlock = Info.ExitingBlocks[i];

1010 continue;

1011 }

1012

1013

1014

1015

1016

1017

1018 if (*KnownWillExit && !IsLatch) {

1019 if (!Info.FirstExitingBlock)

1020 Info.FirstExitingBlock = Info.ExitingBlocks[i];

1021 continue;

1022 }

1023

1024 SetDest(Info.ExitingBlocks[i], *KnownWillExit, Info.ExitOnTrue);

1025 }

1026 }

1027

1028 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);

1030 if (ExitingBlocks.size() == 1 && ExitInfos.size() == 1) {

1031

1032

1033

1034

1035

1036

1037 DTUToUse = nullptr;

1038 auto &[OriginalExit, Info] = *ExitInfos.begin();

1039 if (!Info.FirstExitingBlock)

1040 Info.FirstExitingBlock = Info.ExitingBlocks.back();

1042 if (L->contains(C->getBlock()))

1043 continue;

1044 C->setIDom(DT->getNode(Info.FirstExitingBlock));

1045 }

1046 } else {

1048 }

1049

1050

1051 if (!LatchIsExiting && CompletelyUnroll) {

1052

1053

1054

1057 }

1058

1059

1063 (CompletelyUnroll && !LatchIsExiting && Latch == Latches.back())) &&

1064 "Need a branch as terminator, except when fully unrolling with "

1065 "unconditional latch");

1066 if (Term && Term->isUnconditional()) {

1067 BasicBlock *Dest = Term->getSuccessor(0);

1070 nullptr, nullptr,

1071 false,

1072 DTUToUse ? nullptr : DT)) {

1073

1076 }

1077 }

1078 }

1079

1080

1081

1082 if (!PartialReductions.empty()) {

1083 BasicBlock *ExitBlock = L->getExitBlock();

1085 "Can only introduce parallel reduction phis with single exit block");

1087 "currently only a single reduction is supported");

1088 Value *FinalRdxValue = PartialReductions.back();

1089 Value *RdxResult = nullptr;

1090 for (PHINode &Phi : ExitBlock->phis()) {

1091 if (Phi.getIncomingValueForBlock(L->getLoopLatch()) != FinalRdxValue)

1092 continue;

1093 if (!RdxResult) {

1094 RdxResult = PartialReductions.front();

1096 Builder.setFastMathFlags(Reductions.begin()->second.getFastMathFlags());

1099 RdxResult = Builder.CreateBinOp(

1101 RdxPart, RdxResult, "bin.rdx");

1102 }

1103 NeedToFixLCSSA = true;

1104 for (Instruction *RdxPart : PartialReductions)

1105 RdxPart->dropPoisonGeneratingFlags();

1106 }

1107

1108 Phi.replaceAllUsesWith(RdxResult);

1109 }

1110 }

1111

1112 if (DTUToUse) {

1113

1115 }

1117 DT->verify(DominatorTree::VerificationLevel::Fast));

1118

1119

1120

1123

1124 NumCompletelyUnrolled += CompletelyUnroll;

1125 ++NumUnrolled;

1126

1127 Loop *OuterL = L->getParentLoop();

1128

1129 if (CompletelyUnroll) {

1131

1132 L = nullptr;

1133 } else {

1134

1135

1136

1137

1138

1139

1140

1141

1142

1143

1144

1145

1146

1147

1148

1149

1150

1151

1152

1153

1154

1155

1156

1157

1158

1159

1160

1161

1162 if (!OriginalLoopProb.isUnknown() && ULO.Runtime && EpilogProfitability) {

1163

1164

1166 }

1167 if (OriginalTripCount) {

1168 unsigned NewTripCount = *OriginalTripCount / ULO.Count;

1169 if (!ULO.Runtime && *OriginalTripCount % ULO.Count)

1170 ++NewTripCount;

1172 }

1173 }

1174

1175

1178

1179

1180

1181

1182

1183

1184

1185

1186

1187 if (PreserveLCSSA && OuterL && CompletelyUnroll && !NeedToFixLCSSA)

1189

1190

1191

1192

1193 if (OuterL) {

1194

1195

1196

1197 if (NeedToFixLCSSA) {

1198

1199

1200

1202 Loop *FixLCSSALoop = OuterL;

1203 if (!FixLCSSALoop->contains(LatchLoop))

1204 while (FixLCSSALoop->getParentLoop() != LatchLoop)

1206

1208 } else if (PreserveLCSSA) {

1210 "Loops should be in LCSSA form after loop-unroll.");

1211 }

1212

1213

1214

1215 simplifyLoop(OuterL, DT, LI, SE, AC, nullptr, PreserveLCSSA);

1216 } else {

1217

1218 for (Loop *SubLoop : LoopsToSimplify)

1219 simplifyLoop(SubLoop, DT, LI, SE, AC, nullptr, PreserveLCSSA);

1220 }

1221

1224}

1225

1226

1227

1228

1230

1232 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");

1233

1236 if (!MD)

1237 continue;

1238

1240 if (!S)

1241 continue;

1242

1244 return MD;

1245 }

1246 return nullptr;

1247}

1248

1249std::optional

1254 nullptr,

1255 nullptr, nullptr, SE))

1256 return std::nullopt;

1258 return std::nullopt;

1260

1261

1265 return std::nullopt;

1266

1268 return std::nullopt;

1269

1271 return std::nullopt;

1272

1273

1274

1276 ->operands(),

1278 return std::nullopt;

1279

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

1281 if (!Latch ||

1283 cast(Phi.getIncomingValueForBlock(Latch))->operands(),

1284 &Phi))

1285 return std::nullopt;

1286

1287 return RdxDesc;

1288}

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Optimize for code generation

#define LLVM_ATTRIBUTE_USED

This file contains the declarations for the subclasses of Constant, which represent the different fla...

This file defines the DenseMap class.

early cse Early CSE w MemorySSA

This file defines a set of templates that efficiently compute a dominator tree over a generic graph.

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

This defines the Use class.

static bool needToInsertPhisForLCSSA(Loop *L, const std::vector< BasicBlock * > &Blocks, LoopInfo *LI)

Check if unrolling created a situation where we need to insert phi nodes to preserve LCSSA form.

Definition LoopUnroll.cpp:124

static bool isEpilogProfitable(Loop *L)

The function chooses which type of unroll (epilog or prolog) is more profitabale.

Definition LoopUnroll.cpp:203

void loadCSE(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, BatchAAResults &BAA, function_ref< MemorySSA *()> GetMSSA)

Definition LoopUnroll.cpp:275

Value * getMatchingValue(LoadValue LV, LoadInst *LI, unsigned CurrentGeneration, BatchAAResults &BAA, function_ref< MemorySSA *()> GetMSSA)

Definition LoopUnroll.cpp:255

static cl::opt< bool > UnrollRuntimeEpilog("unroll-runtime-epilog", cl::init(false), cl::Hidden, cl::desc("Allow runtime unrolled loops to be unrolled " "with epilog instead of prolog."))

static cl::opt< bool > UnrollVerifyLoopInfo("unroll-verify-loopinfo", cl::Hidden, cl::desc("Verify loopinfo after unrolling"), cl::init(false))

static cl::opt< bool > UnrollVerifyDomtree("unroll-verify-domtree", cl::Hidden, cl::desc("Verify domtree after unrolling"), cl::init(false))

static LLVM_ATTRIBUTE_USED bool canHaveUnrollRemainder(const Loop *L)

Definition LoopUnroll.cpp:424

static cl::opt< bool > UnrollAddParallelReductions("unroll-add-parallel-reductions", cl::init(false), cl::Hidden, cl::desc("Allow unrolling to add parallel reduction phis."))

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

uint64_t IntrinsicInst * II

This file implements a set that has insertion order iteration characteristics.

This file defines the SmallVector class.

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

#define STATISTIC(VARNAME, DESC)

static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")

Definition LoopUnroll.cpp:222

void childGeneration(unsigned generation)

Definition LoopUnroll.cpp:240

bool isProcessed() const

Definition LoopUnroll.cpp:251

unsigned currentGeneration() const

Definition LoopUnroll.cpp:238

unsigned childGeneration() const

Definition LoopUnroll.cpp:239

StackNode(ScopedHashTable< const SCEV *, LoadValue > &AvailableLoads, unsigned cg, DomTreeNode *N, DomTreeNode::const_iterator Child, DomTreeNode::const_iterator End)

Definition LoopUnroll.cpp:232

DomTreeNode::const_iterator end() const

Definition LoopUnroll.cpp:250

void process()

Definition LoopUnroll.cpp:252

DomTreeNode * nextChild()

Definition LoopUnroll.cpp:244

DomTreeNode::const_iterator childIter() const

Definition LoopUnroll.cpp:242

DomTreeNode * node()

Definition LoopUnroll.cpp:241

Class for arbitrary precision integers.

LLVM_ABI APInt sadd_ov(const APInt &RHS, bool &Overflow) const

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.

iterator_range< const_phi_iterator > phis() const

Returns a range that iterates over the phis in the basic block.

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 const BasicBlock * getUniquePredecessor() const

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

LLVM_ABI const BasicBlock * getSingleSuccessor() const

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

InstListType::iterator iterator

Instruction iterators...

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

LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)

Update PHI nodes in this BasicBlock before removal of predecessor Pred.

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

Conditional or Unconditional Branch instruction.

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

BranchProbability pow(unsigned N) const

Compute pow(Probability, N).

A parsed version of the target data layout string in and methods for querying it.

ValueT lookup(const_arg_type_t< KeyT > Val) const

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

iterator find(const_arg_type_t< KeyT > Val)

bool contains(const_arg_type_t< KeyT > Val) const

Return true if the specified key is in the map, false otherwise.

iterator_range< iterator > children()

DomTreeNodeBase * getIDom() const

typename SmallVector< DomTreeNodeBase *, 4 >::const_iterator const_iterator

bool verify(VerificationLevel VL=VerificationLevel::Full) const

verify - checks if the tree is correct.

void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)

changeImmediateDominator - This method is used to update the dominator tree information when a node's...

DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)

Add a new node to the dominator tree information.

static constexpr UpdateKind Delete

DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const

getNode - return the (Post)DominatorTree node for the specified basic block.

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

LLVM_ABI Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const

Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...

DomTreeT & getDomTree()

Flush DomTree updates and return DomTree.

void applyUpdates(ArrayRef< UpdateT > Updates)

Submit updates to all available trees.

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

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 InstListType::iterator eraseFromParent()

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

An instruction for reading from memory.

bool contains(const LoopT *L) const

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

BlockT * getHeader() const

void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)

This method is used by other analyses to update loop information.

void addChildLoop(LoopT *NewChild)

Add the specified loop to be a child of this loop.

LoopT * getParentLoop() const

Return the parent loop if it exists or nullptr for top level loops.

Store the result of a depth first search within basic blocks contained by a single loop.

RPOIterator beginRPO() const

Reverse iterate over the cached postorder blocks.

std::vector< BasicBlock * >::const_reverse_iterator RPOIterator

void perform(const LoopInfo *LI)

Traverse the loop blocks and store the DFS result.

RPOIterator endRPO() const

void verify(const DominatorTreeBase< BlockT, false > &DomTree) const

void addTopLevelLoop(LoopT *New)

This adds the specified loop to the collection of top-level loops.

LoopT * AllocateLoop(ArgsTy &&...Args)

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.

LLVM_ABI void erase(Loop *L)

Update LoopInfo after removing the last backedge from a loop.

Represents a single loop in the control flow graph.

bool isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens=true) const

Return true if the Loop is in LCSSA form.

const MDOperand & getOperand(unsigned I) const

ArrayRef< MDOperand > operands() const

unsigned getNumOperands() const

Return number of MDNode operands.

Tracking metadata reference owned by Metadata.

LLVM_ABI StringRef getString() const

MemoryAccess * getClobberingMemoryAccess(const Instruction *I, BatchAAResults &AA)

Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...

Encapsulates MemorySSA, including all data associated with memory accesses.

LLVM_ABI bool dominates(const MemoryAccess *A, const MemoryAccess *B) const

Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates...

LLVM_ABI MemorySSAWalker * getWalker()

MemoryUseOrDef * getMemoryAccess(const Instruction *I) const

Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.

void setIncomingValueForBlock(const BasicBlock *BB, Value *V)

Set every incoming value(s) for block BB to V.

Value * getIncomingValueForBlock(const BasicBlock *BB) const

The RecurrenceDescriptor is used to identify recurrences variables in a loop.

FastMathFlags getFastMathFlags() const

bool hasExactFPMath() const

Returns true if the recurrence has floating-point math that requires precise (ordered) operations.

static LLVM_ABI unsigned getOpcode(RecurKind Kind)

Returns the opcode corresponding to the RecurrenceKind.

static LLVM_ABI bool isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr, ScalarEvolution *SE=nullptr)

Returns true if Phi is a reduction in TheLoop.

bool hasUsesOutsideReductionChain() const

Returns true if the reduction PHI has any uses outside the reduction chain.

static bool isAnyOfRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...

RecurKind getRecurrenceKind() const

StoreInst * IntermediateStore

Reductions may store temporary or final result to an invariant address.

static bool isFindIVRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...

static bool isMinMaxRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is any min/max kind.

This class represents an analyzed expression in the program.

The main scalar evolution driver.

LLVM_ABI unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)

Returns the largest constant divisor of the trip count as a normal unsigned value,...

LLVM_ABI const SCEV * getSCEV(Value *V)

Return a SCEV expression for the full generality of the specified expression.

LLVM_ABI unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)

Returns the upper bound of the loop trip count as a normal unsigned value.

LLVM_ABI bool isBackedgeTakenCountMaxOrZero(const Loop *L)

Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...

LLVM_ABI void forgetTopmostLoop(const Loop *L)

LLVM_ABI void forgetBlockAndLoopDispositions(Value *V=nullptr)

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

LLVM_ABI void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)

Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...

LLVM_ABI unsigned getSmallConstantTripCount(const Loop *L)

Returns the exact trip count of the loop if we can compute it, and the result is a small constant.

LLVM_ABI void forgetAllLoops()

void insert(const K &Key, const V &Val)

V lookup(const K &Key) const

ScopedHashTableScope< K, V, KInfo, AllocatorTy > ScopeTy

ScopeTy - A type alias for easy access to the name of the scope for this hash table.

void insert_range(Range &&R)

bool insert(const value_type &X)

Insert a new element into the SetVector.

A SetVector that performs no allocations if smaller than a certain size.

reference emplace_back(ArgTypes &&... Args)

void push_back(const T &Elt)

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

StringRef - Represent a constant reference to a string, i.e.

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

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

LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)

Replace uses of one Value with another.

iterator find(const KeyT &Val)

ValueMapIteratorImpl< MapT, const Value *, false > iterator

bool erase(const KeyT &Val)

DMAtomT AtomMap

Map {(InlinedAt, old atom number) -> new atom number}.

LLVM Value Representation.

Type * getType() const

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

An efficient, type-erasing, non-owning reference to a callable.

self_iterator getIterator()

Abstract Attribute helper functions.

@ C

The default llvm calling convention, compatible with C.

BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)

ap_match< APInt > m_APInt(const APInt *&Res)

Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.

bool match(Val *V, const Pattern &P)

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

initializer< Ty > init(const Ty &Val)

Add a small namespace to avoid name clashes with the classes used in the streaming interface.

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)

Simplify each loop in a loop nest recursively.

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

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

LLVM_ABI bool RemoveRedundantDbgInstrs(BasicBlock *BB)

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

LLVM_ABI std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)

Return either:

LLVM_ABI void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, AAResults *AA=nullptr)

Perform some cleanup and simplifications on loops after unrolling.

Definition LoopUnroll.cpp:343

LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())

If the specified value is a trivially dead instruction, delete it.

LLVM_ABI BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, bool MapAtoms=true)

Return a copy of the specified basic block, but without embedding the block into a particular functio...

LLVM_ABI std::optional< RecurrenceDescriptor > canParallelizeReductionWhenUnrolling(PHINode &Phi, Loop *L, ScalarEvolution *SE)

Definition LoopUnroll.cpp:1250

decltype(auto) dyn_cast(const From &Val)

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

auto successors(const MachineBasicBlock *BB)

SmallDenseMap< const Loop *, Loop *, 4 > NewLoopsMap

LLVM_ABI cl::opt< bool > EnableFSDiscriminator

LLVM_ABI bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)

Put a loop nest into LCSSA form.

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 Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)

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

DomTreeNodeBase< BasicBlock > DomTreeNode

auto dyn_cast_or_null(const Y &Val)

void erase(Container &C, ValueType V)

Wrapper function to remove a value from a container:

bool any_of(R &&range, UnaryPredicate P)

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

LLVM_ABI bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)

Return true if the result produced by the instruction is not used, and the instruction will return.

LLVM_ABI CallBase * getLoopConvergenceHeart(const Loop *TheLoop)

Find the convergence heart of the loop.

LLVM_ABI raw_ostream & dbgs()

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

bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT, LoopInfo *LI, const TargetTransformInfo *TTI, SmallVectorImpl< WeakTrackingVH > &Dead)

SimplifyLoopIVs - Simplify users of induction variables within this loop.

SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)

Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...

BranchProbability getLoopProbability(Loop *L)

Based on branch weight metadata, return either:

LoopUnrollResult

Represents the result of a UnrollLoop invocation.

@ PartiallyUnrolled

The loop was partially unrolled – we still have a loop, but with a smaller trip count.

@ Unmodified

The loop was not modified.

@ FullyUnrolled

The loop was fully unrolled into straight-line code.

bool isa(const From &Val)

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

LLVM_ABI unsigned changeToUnreachable(Instruction *I, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)

Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...

bool setLoopProbability(Loop *L, BranchProbability P)

Set branch weight metadata for the latch of L to indicate that, at the end of any iteration,...

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 replace(R &&Range, const T &OldValue, const T &NewValue)

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

RecurKind

These are the kinds of recurrences that we support.

LLVM_ABI Value * getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF)

Given information about an recurrence kind, return the identity for the @llvm.vector....

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

Clone the specified noalias decl scopes.

LLVM_ABI void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)

Remaps instructions in Blocks using the mapping in VMap.

ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy

LLVM_ABI bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount, std::optional< unsigned > EstimatedLoopInvocationWeight=std::nullopt)

Set llvm.loop.estimated_trip_count with the value EstimatedTripCount in the loop metadata of L.

LLVM_ABI const Loop * addClonedBlockToLoopInfo(BasicBlock *OriginalBB, BasicBlock *ClonedBB, LoopInfo *LI, NewLoopsMap &NewLoops)

Adds ClonedBB to LoopInfo, creates a new loop for ClonedBB if necessary and adds a mapping from the o...

Definition LoopUnroll.cpp:149

decltype(auto) cast(const From &Val)

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

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

LLVM_ABI void identifyNoAliasScopesToClone(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< MDNode * > &NoAliasDeclScopes)

Find the 'llvm.experimental.noalias.scope.decl' intrinsics in the specified basic blocks and extract ...

LLVM_ABI bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, bool PreserveLCSSA, unsigned SCEVExpansionBudget, bool RuntimeUnrollMultiExit, Loop **ResultLoop=nullptr, std::optional< unsigned > OriginalTripCount=std::nullopt, BranchProbability OriginalLoopProb=BranchProbability::getUnknown())

Insert code in the prolog/epilog code when unrolling a loop with a run-time trip-count.

LLVM_ABI MDNode * GetUnrollMetadata(MDNode *LoopID, StringRef Name)

Given an llvm.loop loop id metadata node, returns the loop hint metadata node with the given name (fo...

Definition LoopUnroll.cpp:1229

constexpr detail::IsaCheckPredicate< Types... > IsaPred

Function object wrapper for the llvm::isa type check.

LLVM_ABI void RemapSourceAtom(Instruction *I, ValueToValueMapTy &VM)

Remap source location atom.

LLVM_ABI LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const llvm::TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, Loop **RemainderLoop=nullptr, AAResults *AA=nullptr)

Unroll the given loop by Count.

Definition LoopUnroll.cpp:459

Definition LoopUnroll.cpp:214

Instruction * DefI

Definition LoopUnroll.cpp:215

unsigned Generation

Definition LoopUnroll.cpp:216

LoadValue(Instruction *Inst, unsigned Generation)

Definition LoopUnroll.cpp:218

Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...

const Instruction * Heart

bool RuntimeUnrollMultiExit

bool AllowExpensiveTripCount

bool AddAdditionalAccumulators

unsigned SCEVExpansionBudget

std::conditional_t< IsConst, const ValueT &, ValueT & > second