LoopPeel.cpp Source File (original) (raw)

43#include

44#include

45#include

46#include

48using namespace llvm;

52#define DEBUG_TYPE "loop-peel"

54 STATISTIC(NumPeeled, "Number of loops peeled");

55 STATISTIC(NumPeeledEnd, "Number of loops peeled from end");

57namespace llvm {

60 cl::desc("Set the unroll peeling count, for testing purposes"));

64 cl::desc("Allows loops to be peeled when the dynamic "

65 "trip count is known to be low."));

70 cl::desc("Allows loop nests to be peeled."));

74 cl::desc("Max average trip count which will cause loop peeling."));

78 cl::desc("Force a peel count regardless of profiling information."));

83 "Disable advance peeling. Issues for convergent targets (D134803)."));

87 cl::desc("Enable peeling to convert Phi nodes into IVs"));

92}

97 if (!L->isLoopSimplifyForm())

98 return false;

100 return true;

101

103 L->getUniqueNonLatchExitBlocks(Exits);

104

105

106

107

108

109

110

111

113}

114

115namespace {

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195class PhiAnalyzer {

196public:

197 PhiAnalyzer(const Loop &L, unsigned MaxIterations, bool PeelForIV);

198

199

200

201 std::optional calculateIterationsToPeel();

202

203protected:

204 enum class PeelCounterType {

205 Invariant,

206 Induction,

207 };

208

209 using PeelCounterValue = std::pair<unsigned, PeelCounterType>;

210 using PeelCounter = std::optional;

211 const PeelCounter Unknown = std::nullopt;

212

213

214 PeelCounter addOne(PeelCounter PC) const {

215 if (PC == Unknown)

216 return Unknown;

217 auto [Val, Ty] = *PC;

218 return (Val + 1 <= MaxIterations) ? PeelCounter({Val + 1, Ty}) : Unknown;

219 }

220

221

222 PeelCounter makeZero(PeelCounterType Ty) const {

223 return PeelCounter({0, Ty});

224 }

225

226

227

228 PeelCounter calculate(const Value &);

229

230

231

232 PeelCounter mergeTwoCounters(const Instruction &CmpOrBinaryOp,

233 const PeelCounterValue &LHS,

234 const PeelCounterValue &RHS) const;

235

236

237

238 bool isInductionPHI(const PHINode *Phi) const;

239

240 const Loop &L;

241 const unsigned MaxIterations;

242 const bool PeelForIV;

243

244

245 SmallDenseMap<const Value *, PeelCounter> IterationsToInvarianceOrInduction;

246};

247

248PhiAnalyzer::PhiAnalyzer(const Loop &L, unsigned MaxIterations, bool PeelForIV)

249 : L(L), MaxIterations(MaxIterations), PeelForIV(PeelForIV) {

250 assert(canPeel(&L) && "loop is not suitable for peeling");

251 assert(MaxIterations > 0 && "no peeling is allowed?");

252}

253

254

255

256

257

258bool PhiAnalyzer::isInductionPHI(const PHINode *Phi) const {

259

261 if (Latch == nullptr)

262 return false;

263

264 Value *Cur = Phi->getIncomingValueForBlock(Latch);

265 SmallPtrSet<Value *, 4> Visited;

266 bool VisitBinOp = false;

267

268

269

270

271 while (true) {

272 if (Cur == Phi)

273 break;

274

275

276 if (!Visited.insert(Cur).second)

277 return false;

278

280 if ( || .contains(I))

281 return false;

282

284 Cur = Cast->getOperand(0);

286 if (BinOp->getOpcode() != Instruction::Add &&

287 BinOp->getOpcode() != Instruction::Sub)

288 return false;

290 return false;

291

292 VisitBinOp = true;

293 Cur = BinOp->getOperand(0);

294 } else {

295 return false;

296 }

297 }

298

299

300 return VisitBinOp;

301}

302

303

304

305

306

307

308

309PhiAnalyzer::PeelCounter

310PhiAnalyzer::mergeTwoCounters(const Instruction &CmpOrBinaryOp,

311 const PeelCounterValue &LHS,

312 const PeelCounterValue &RHS) const {

313 auto &[LVal, LTy] = LHS;

314 auto &[RVal, RTy] = RHS;

315 unsigned NewVal = std::max(LVal, RVal);

316

317 if (LTy == PeelCounterType::Induction || RTy == PeelCounterType::Induction) {

319 if (BinOp->getOpcode() == Instruction::Add ||

320 BinOp->getOpcode() == Instruction::Sub)

321 return PeelCounter({NewVal, PeelCounterType::Induction});

322 }

324 }

325 return PeelCounter({NewVal, PeelCounterType::Invariant});

326}

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342PhiAnalyzer::PeelCounter PhiAnalyzer::calculate(const Value &V) {

343

344

345

347 IterationsToInvarianceOrInduction.try_emplace(&V, Unknown);

348 if (!Inserted)

349 return I->second;

350

351 if (L.isLoopInvariant(&V))

352

353 return (IterationsToInvarianceOrInduction[&V] =

354 makeZero(PeelCounterType::Invariant));

356 if (Phi->getParent() != L.getHeader()) {

357

358 assert(IterationsToInvarianceOrInduction[&V] == Unknown &&

359 "unexpected value saved");

361 }

362

363

364 if (PeelForIV && isInductionPHI(Phi))

365 return (IterationsToInvarianceOrInduction[&V] =

366 makeZero(PeelCounterType::Induction));

367

368

369 Value *Input = Phi->getIncomingValueForBlock(L.getLoopLatch());

370 PeelCounter Iterations = calculate(*Input);

371 assert(IterationsToInvarianceOrInduction[Input] == Iterations &&

372 "unexpected value saved");

373 return (IterationsToInvarianceOrInduction[Phi] = addOne(Iterations));

374 }

377

378 PeelCounter LHS = calculate(*I->getOperand(0));

381 PeelCounter RHS = calculate(*I->getOperand(1));

384 return (IterationsToInvarianceOrInduction[I] =

385 mergeTwoCounters(*I, *LHS, *RHS));

386 }

387 if (I->isCast())

388

389 return (IterationsToInvarianceOrInduction[I] =

390 calculate(*I->getOperand(0)));

391 }

392

393

394

395 assert(IterationsToInvarianceOrInduction[&V] == Unknown &&

396 "unexpected value saved");

398}

399

400std::optional PhiAnalyzer::calculateIterationsToPeel() {

401 unsigned Iterations = 0;

402 for (auto &PHI : L.getHeader()->phis()) {

403 PeelCounter ToInvarianceOrInduction = calculate(PHI);

404 if (ToInvarianceOrInduction != Unknown) {

405 unsigned Val = ToInvarianceOrInduction->first;

406 assert(Val <= MaxIterations && "bad result in phi analysis");

407 Iterations = std::max(Iterations, Val);

408 if (Iterations == MaxIterations)

409 break;

410 }

411 }

412 assert((Iterations <= MaxIterations) && "bad result in phi analysis");

413 return Iterations ? std::optional(Iterations) : std::nullopt;

414}

415

416}

417

418

419

420

421

425

426

427 if (L.getExitingBlock())

428 return 0;

429

430

431

433 L.getUniqueNonLatchExitBlocks(Exits);

436 }))

437 return 0;

438

439

440

441

442

443

445 BasicBlock *Latch = L.getLoopLatch();

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

450

451 if (I.mayWriteToMemory() &&

454 return 0;

455

458

459

460 if (BB == Header)

461 continue;

463 Value *Ptr = LI->getPointerOperand();

464 if (DT.dominates(BB, Latch) && L.isLoopInvariant(Ptr) &&

467 }

468 }

469 }

471 L.getExitingBlocks(ExitingBlocks);

472 if (any_of(ExitingBlocks, [&LoadUsers](BasicBlock *Exiting) {

474 }))

475 return 1;

476 return 0;

477}

478

482 return false;

483

484

485

486

487

488

489 BasicBlock *Latch = L.getLoopLatch();

495 return Latch && Latch == L.getExitingBlock() &&

505}

506

507

508

509

515 return false;

516

521 L.getLoopPredecessor()->getTerminator()))

522 return false;

523

530

532 RightSCEV) &&

534}

535

536

537

538

539

540

541

542

543

544

545

546

547static std::pair<unsigned, unsigned>

550 assert(L.isLoopSimplifyForm() && "Loop needs to be in loop simplify form");

551 unsigned DesiredPeelCount = 0;

552 unsigned DesiredPeelCountLast = 0;

553

554

557 MaxPeelCount =

558 std::min((unsigned)SC->getAPInt().getLimitedValue() - 1, MaxPeelCount);

559

560

561

562

563 auto PeelWhilePredicateIsKnown =

564 [&](unsigned &PeelCount, const SCEV *&IterVal, const SCEV *BoundSCEV,

566 while (PeelCount < MaxPeelCount &&

568 IterVal = SE.getAddExpr(IterVal, Step);

569 ++PeelCount;

570 }

572 BoundSCEV);

573 };

574

575 const unsigned MaxDepth = 4;

576 std::function<void(Value *, unsigned)> ComputePeelCount =

577 [&](Value *Condition, unsigned Depth) -> void {

579 return;

580

581 Value *LeftVal, *RightVal;

584 ComputePeelCount(LeftVal, Depth + 1);

585 ComputePeelCount(RightVal, Depth + 1);

586 return;

587 }

588

591 return;

592

593 const SCEV *LeftSCEV = SE.getSCEV(LeftVal);

594 const SCEV *RightSCEV = SE.getSCEV(RightVal);

595

596

597

599 return;

600

601

602

607 } else

608 return;

609 }

610

612

613

614

616 return;

619 return;

620

621

622

623 unsigned NewPeelCount = DesiredPeelCount;

624

627

628

629

630

633

635 if (!PeelWhilePredicateIsKnown(NewPeelCount, IterVal, RightSCEV, Step,

636 Pred)) {

638 DesiredPeelCountLast = 1;

639 return;

640 }

641

642

643

644

645 const SCEV *NextIterVal = SE.getAddExpr(IterVal, Step);

648 RightSCEV) &&

651 if (NewPeelCount >= MaxPeelCount)

652 return;

653 ++NewPeelCount;

654 }

655

656 DesiredPeelCount = std::max(DesiredPeelCount, NewPeelCount);

657 DesiredPeelCountLast = std::max(DesiredPeelCountLast, NewPeelCount);

658 };

659

661 if ( MinMax ->getType()->isIntegerTy())

662 return;

664 const SCEV *BoundSCEV, *IterSCEV;

665 if (L.isLoopInvariant(LHS)) {

668 } else if (L.isLoopInvariant(RHS)) {

671 } else

672 return;

674

675 if (!AddRec || !AddRec->isAffine() || AddRec->getLoop() != &L)

676 return;

677 const SCEV *Step = AddRec->getStepRecurrence(SE);

678 bool IsSigned = MinMax->isSigned();

679

680

686 else

687 return;

688

689 if (!(IsSigned ? AddRec->hasNoSignedWrap() : AddRec->hasNoUnsignedWrap()))

690 return;

691 unsigned NewPeelCount = DesiredPeelCount;

692 const SCEV *IterVal = AddRec->evaluateAtIteration(

693 SE.getConstant(AddRec->getType(), NewPeelCount), SE);

694 if (!PeelWhilePredicateIsKnown(NewPeelCount, IterVal, BoundSCEV, Step,

695 Pred)) {

697 DesiredPeelCountLast = 1;

698 return;

699 }

700 DesiredPeelCount = NewPeelCount;

701 };

702

706 ComputePeelCount(SI->getCondition(), 0);

708 ComputePeelCountMinMax(MinMax);

709 }

710

712 if (!BI || BI->isUnconditional())

713 continue;

714

715

716 if (L.getLoopLatch() == BB)

717 continue;

718

719 ComputePeelCount(BI->getCondition(), 0);

720 }

721

722 return {DesiredPeelCount, DesiredPeelCountLast};

723}

724

725

726

727

728

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

731 if (!Latch)

732 return true;

733

735 if (!LatchBR || LatchBR->getNumSuccessors() != 2 || !L->isLoopExiting(Latch))

736 return true;

737

739 LatchBR->getSuccessor(1) == L->getHeader()) &&

740 "At least one edge out of the latch must go to the header");

741

743 L->getUniqueNonLatchExitBlocks(ExitBlocks);

746 });

747}

748

749

750

756 assert(LoopSize > 0 && "Zero loop size is not allowed!");

757

758

759 unsigned TargetPeelCount = PP.PeelCount;

763 return;

764

765

766

767

769 return;

770

771

773 if (UserPeelCount) {

775 << " iterations.\n");

778 return;

779 }

780

781

783 return;

784

785

786 if (2 * LoopSize > Threshold)

787 return;

788

789 unsigned AlreadyPeeled = 0;

791 AlreadyPeeled = *Peeled;

792

794 return;

795

796

798 MaxPeelCount = std::min(MaxPeelCount, Threshold / LoopSize - 1);

799

800

801

802 unsigned DesiredPeelCount = TargetPeelCount;

803

804

805

806

807

808

809 if (MaxPeelCount > DesiredPeelCount) {

810

812 .calculateIterationsToPeel();

813 if (NumPeels)

814 DesiredPeelCount = std::max(DesiredPeelCount, *NumPeels);

815 }

816

817 const auto &[CountToEliminateCmps, CountToEliminateCmpsLast] =

819 DesiredPeelCount = std::max(DesiredPeelCount, CountToEliminateCmps);

820

821 if (DesiredPeelCount == 0)

823

824 if (DesiredPeelCount > 0) {

825 DesiredPeelCount = std::min(DesiredPeelCount, MaxPeelCount);

826

827 assert(DesiredPeelCount > 0 && "Wrong loop size estimation?");

830 << " iteration(s) to turn"

831 << " some Phis into invariants or inductions.\n");

835 return;

836 }

837 }

838

839 if (CountToEliminateCmpsLast > 0) {

840 unsigned DesiredPeelCountLast =

841 std::min(CountToEliminateCmpsLast, MaxPeelCount);

842

843 assert(DesiredPeelCountLast > 0 && "Wrong loop size estimation?");

846 << " iteration(s) to turn"

847 << " some Phis into invariants.\n");

848 PP.PeelCount = DesiredPeelCountLast;

851 return;

852 }

853 }

854

855

856

857 if (TripCount)

858 return;

859

860

862 return;

863

864

865

866

867

868 if (L->getHeader()->getParent()->hasProfileData()) {

870 return;

872 if (!EstimatedTripCount)

873 return;

874

875 LLVM_DEBUG(dbgs() << "Profile-based estimated trip count is "

876 << *EstimatedTripCount << "\n");

877

878 if (*EstimatedTripCount + AlreadyPeeled <= MaxPeelCount) {

879 unsigned PeelCount = *EstimatedTripCount;

880 LLVM_DEBUG(dbgs() << "Peeling first " << PeelCount << " iterations.\n");

882 return;

883 }

884 LLVM_DEBUG(dbgs() << "Already peel count: " << AlreadyPeeled << "\n");

886 LLVM_DEBUG(dbgs() << "Loop cost: " << LoopSize << "\n");

887 LLVM_DEBUG(dbgs() << "Max peel cost: " << Threshold << "\n");

889 << (Threshold / LoopSize - 1) << "\n");

890 }

891}

892

893

894

895

896

897

898

899

900

901

902

903

905 Loop *L, unsigned IterNumber, bool PeelLast, BasicBlock *InsertTop,

907 SmallVectorImpl<std::pair<BasicBlock *, BasicBlock *>> &ExitEdges,

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

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

915

916 Function *F = Header->getParent();

919 Loop *ParentLoop = L->getParentLoop();

920

921

922

926

927

928

929

930 if (ParentLoop && LI->getLoopFor(*BB) == L)

932

933 VMap[*BB] = NewBB;

934

935

936 if (DT) {

937 if (Header == *BB)

939 else {

941

943 }

944 }

945 }

946

947 {

948

949

950

951 std::string Ext = (Twine("Peel") + Twine(IterNumber)).str();

953 Header->getContext(), Ext);

954 }

955

956

957

958 for (Loop *ChildLoop : *L) {

959 cloneLoop(ChildLoop, ParentLoop, VMap, LI, nullptr);

960 }

961

962

963

964

965

967

968

969

971 if (PeelLast) {

972

973

974 assert(IterNumber == 0 && "Only peeling a single iteration implemented.");

976 LatchTerm->setSuccessor(0, InsertBot);

977 LatchTerm->setSuccessor(1, InsertBot);

978 } else {

980

981

982

983 for (unsigned idx = 0, e = LatchTerm->getNumSuccessors(); idx < e; ++idx) {

984 if (LatchTerm->getSuccessor(idx) == Header) {

985 LatchTerm->setSuccessor(idx, InsertBot);

986 break;

987 }

988 }

989 }

990 if (DT)

992

993

994

995

996

997 if (PeelLast) {

998

999

1000

1001

1007 if (OrigPreHeader)

1009 OrigPreHeader);

1010

1012 Latch);

1013 VMap[&*I] = PN;

1014 }

1015 } else {

1016

1017

1018

1019

1022 if (IterNumber == 0) {

1024 } else {

1027 if (LatchInst && L->contains(LatchInst))

1028 VMap[&*I] = LVMap[LatchInst];

1029 else

1030 VMap[&*I] = LatchVal;

1031 }

1033 }

1034 }

1035

1036

1037

1038

1039

1040 for (auto Edge : ExitEdges)

1041 for (PHINode &PHI : Edge.second->phis()) {

1042 Value *LatchVal = PHI.getIncomingValueForBlock(Edge.first);

1044 if (LatchInst && L->contains(LatchInst))

1045 LatchVal = VMap[LatchVal];

1048 }

1049

1050

1051

1052 for (auto KV : VMap)

1053 LVMap[KV.first] = KV.second;

1054}

1055

1056TargetTransformInfo::PeelingPreferences

1059 std::optional UserAllowPeeling,

1060 std::optional UserAllowProfileBasedPeeling,

1061 bool UnrollingSpecficValues) {

1063

1064

1070

1071

1072 TTI.getPeelingPreferences(L, SE, PP);

1073

1074

1075 if (UnrollingSpecficValues) {

1082 }

1083

1084

1085 if (UserAllowPeeling)

1087 if (UserAllowProfileBasedPeeling)

1089

1090 return PP;

1091}

1092

1093

1094

1095

1096

1097

1098

1099

1100

1101

1105 assert(PeelCount > 0 && "Attempt to peel out zero iterations?");

1106 assert(canPeel(L) && "Attempt to peel a loop which is not peelable?");

1108 "when peeling the last iteration, the loop must be supported and can "

1109 "only peel a single iteration");

1110

1112 LoopBlocks.perform(LI);

1113

1114 BasicBlock *Header = L->getHeader();

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

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

1118 L->getExitEdges(ExitEdges);

1119

1120

1121

1122

1123

1125 for (auto *BB : L->blocks()) {

1126 auto *BBDomNode = DT.getNode(BB);

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

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

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

1131 ChildrenToUpdate.push_back(ChildBB);

1132 }

1133

1134

1135

1136

1138 for (auto *ChildBB : ChildrenToUpdate)

1139 NonLoopBlocksIDom[ChildBB] = NewIDom;

1140 }

1141

1142 Function *F = Header->getParent();

1143

1144

1149 if (PeelLast) {

1150

1151

1152

1153

1154

1155

1156

1157

1158

1159

1160

1161

1162

1163

1164

1165

1166

1167

1168

1169

1170

1171

1172

1173

1174 BasicBlock *Exit = L->getExitBlock();

1175 for (PHINode &P : Exit->phis())

1176 ExitValues[&P] = P.getIncomingValueForBlock(Latch);

1177

1179

1180 InsertTop = SplitEdge(Latch, Exit, &DT, LI);

1182

1183 InsertTop->setName(Exit->getName() + ".peel.begin");

1184 InsertBot->setName(Exit->getName() + ".peel.next");

1185 NewPreHeader = nullptr;

1186

1187

1188

1189

1190

1192

1193

1194

1195

1196

1197

1198

1199

1200

1201

1203

1204

1206 double Freq = 1 / ExitP.toDouble();

1207

1208

1209

1210 assert(Freq >= 1.0 && "expected freq >= 1 due to initial iteration");

1211 double NewFreq = std::max(Freq - 1, 1.0);

1214 }

1215 }

1216 } else {

1217 NewPreHeader = SplitEdge(PreHeader, Header, &DT, LI);

1219

1221 Value *BTCValue =

1225 B.CreateICmpNE(BTCValue, ConstantInt::get(BTCValue->getType(), 0));

1226 auto *BI = B.CreateCondBr(Cond, NewPreHeader, InsertTop);

1231 if (HasBranchWeights) {

1232

1233

1234

1235

1236

1237

1238

1239

1240 if (L->getExitBlock() == OrigLatchBr->getSuccessor(0))

1241 std::swap(Weights[0], Weights[1]);

1243 }

1245

1246

1248 }

1249 } else {

1250

1251

1252

1253

1254

1255

1256

1257

1258

1259

1260

1261

1262

1263

1264

1265

1266

1267

1268

1269

1270

1271

1272

1273

1274

1275

1276

1277

1278

1279

1280

1281

1282

1283

1284

1285

1286

1287

1288

1289

1290

1291

1292

1293

1294

1295 InsertTop = SplitEdge(PreHeader, Header, &DT, LI);

1298

1299 InsertTop->setName(Header->getName() + ".peel.begin");

1300 InsertBot->setName(Header->getName() + ".peel.next");

1301 NewPreHeader->setName(PreHeader->getName() + ".peel.newph");

1302 }

1303

1306

1307

1308

1311

1312

1314 for (unsigned Iter = 0; Iter < PeelCount; ++Iter) {

1316

1317 cloneLoopBlocks(L, Iter, PeelLast, InsertTop, InsertBot,

1318 NewPreHeader ? PreHeader : nullptr, ExitEdges, NewBlocks,

1319 LoopBlocks, VMap, LVMap, &DT, LI,

1320 LoopLocalNoAliasDeclScopes, *SE);

1321

1322

1323

1325

1326 if (Iter == 0) {

1327 if (PeelLast) {

1328

1329

1330

1331

1332

1333

1334 auto *Cmp =

1335 cast(L->getLoopLatch()->getTerminator()->getOperand(0));

1337 Cmp->setOperand(

1338 1, B.CreateSub(Cmp->getOperand(1),

1339 ConstantInt::get(Cmp->getOperand(1)->getType(), 1)));

1340 } else {

1341

1342 for (auto BBIDom : NonLoopBlocksIDom)

1345 }

1346 }

1347

1348#ifdef EXPENSIVE_CHECKS

1349 assert(DT.verify(DominatorTree::VerificationLevel::Fast));

1350#endif

1351

1352

1353

1355 LatchTermCopy->setMetadata(LLVMContext::MD_loop, nullptr);

1356

1357 InsertTop = InsertBot;

1359 InsertBot->setName(Header->getName() + ".peel.next");

1360

1361 F->splice(InsertTop->getIterator(), F, NewBlocks[0]->getIterator(),

1362 F->end());

1363 }

1364

1365 if (PeelLast) {

1366

1367

1368 for (const auto &[P, E] : ExitValues) {

1370 if (ExitInst && L->contains(ExitInst))

1371 P->replaceAllUsesWith(&*VMap[ExitInst]);

1372 else

1373 P->replaceAllUsesWith(E);

1374 P->eraseFromParent();

1375 }

1377 } else {

1378

1379

1382 Value *NewVal = PHI->getIncomingValueForBlock(Latch);

1384 if (LatchInst && L->contains(LatchInst))

1385 NewVal = LVMap[LatchInst];

1386

1387 PHI->setIncomingValueForBlock(NewPreHeader, NewVal);

1388 }

1389 }

1390

1391

1392 unsigned AlreadyPeeled = 0;

1394 AlreadyPeeled = *Peeled;

1395 unsigned TotalPeeled = AlreadyPeeled + PeelCount;

1397

1398

1399

1400

1401

1402

1403

1404

1405

1406

1407

1408

1409

1410

1411

1412

1413

1414

1416 unsigned EstimatedTripCountNew = *EstimatedTripCount;

1417 if (EstimatedTripCountNew < TotalPeeled)

1418 EstimatedTripCountNew = 0;

1419 else

1420 EstimatedTripCountNew -= TotalPeeled;

1422 }

1423

1424 if (Loop *ParentLoop = L->getParentLoop())

1425 L = ParentLoop;

1426

1427

1430

1431#ifdef EXPENSIVE_CHECKS

1432

1433 assert(DT.verify(DominatorTree::VerificationLevel::Fast));

1434#endif

1435

1436

1437 simplifyLoop(L, &DT, LI, SE, AC, nullptr, PreserveLCSSA);

1438

1439 NumPeeled++;

1440 NumPeeledEnd += PeelLast;

1441

1442 return true;

1443}

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

This file defines the DenseMap class.

static bool shouldPeelLastIteration(Loop &L, CmpPredicate Pred, const SCEVAddRecExpr *LeftAR, const SCEV *RightSCEV, ScalarEvolution &SE, const TargetTransformInfo &TTI)

Returns true if the last iteration can be peeled off and the condition (Pred LeftAR,...

Definition LoopPeel.cpp:510

static bool violatesLegacyMultiExitLoopCheck(Loop *L)

This "heuristic" exactly matches implicit behavior which used to exist inside getLoopEstimatedTripCou...

Definition LoopPeel.cpp:729

static std::pair< unsigned, unsigned > countToEliminateCompares(Loop &L, unsigned MaxPeelCount, ScalarEvolution &SE, const TargetTransformInfo &TTI)

Definition LoopPeel.cpp:548

static void cloneLoopBlocks(Loop *L, unsigned IterNumber, bool PeelLast, BasicBlock *InsertTop, BasicBlock *InsertBot, BasicBlock *OrigPreHeader, SmallVectorImpl< std::pair< BasicBlock *, BasicBlock * > > &ExitEdges, SmallVectorImpl< BasicBlock * > &NewBlocks, LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap, ValueToValueMapTy &LVMap, DominatorTree *DT, LoopInfo *LI, ArrayRef< MDNode * > LoopLocalNoAliasDeclScopes, ScalarEvolution &SE)

Clones the body of the loop L, putting it between InsertTop and InsertBot.

Definition LoopPeel.cpp:904

static unsigned peelToTurnInvariantLoadsDereferenceable(Loop &L, DominatorTree &DT, AssumptionCache *AC)

Definition LoopPeel.cpp:422

This file contains the declarations for profiling metadata utility functions.

const SmallVectorImpl< MachineOperand > & Cond

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)

This pass exposes codegen information to IR-level passes.

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

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

LLVM Basic Block Representation.

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 CallInst * getTerminatingDeoptimizeCall() const

Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...

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

Conditional or Unconditional Branch instruction.

unsigned getNumSuccessors() const

BasicBlock * getSuccessor(unsigned i) const

static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

@ ICMP_SLT

signed less than

@ ICMP_UGT

unsigned greater than

@ ICMP_SGT

signed greater than

@ ICMP_ULT

unsigned less than

Predicate getSwappedPredicate() const

For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.

Predicate getInversePredicate() const

For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...

An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...

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

DomTreeNodeBase * getIDom() const

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.

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

LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const

Return true if the (end of the) basic block BB dominates the use U.

static bool isEquality(Predicate P)

Return true if this predicate is either EQ or NE.

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

LLVM_ABI InstListType::iterator eraseFromParent()

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

LLVM_ABI void setSuccessor(unsigned Idx, BasicBlock *BB)

Update the specified successor to point at the provided block.

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

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

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

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

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

Represents a single loop in the control flow graph.

This class represents min/max intrinsics.

void addIncoming(Value *V, BasicBlock *BB)

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

Value * getIncomingValueForBlock(const BasicBlock *BB) const

This node represents a polynomial recurrence on the trip count of the specified loop.

LLVM_ABI const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const

Return the value of this chain of recurrences at the specified iteration number.

const SCEV * getStepRecurrence(ScalarEvolution &SE) const

Constructs and returns the recurrence indicating how much this expression steps by.

bool isAffine() const

Return true if this represents an expression A + B*x where A and B are loop invariant values.

const Loop * getLoop() const

This class represents a constant integer value.

This class uses information about analyze scalars to rewrite expressions in canonical form.

bool isHighCostExpansion(ArrayRef< const SCEV * > Exprs, Loop *L, unsigned Budget, const TargetTransformInfo *TTI, const Instruction *At)

Return true for expressions that can't be evaluated at runtime within given Budget.

LLVM_ABI Value * expandCodeFor(const SCEV *SH, Type *Ty, BasicBlock::iterator I)

Insert code to directly compute the specified SCEV expression into the program.

bool hasNoSelfWrap() const

This class represents an analyzed expression in the program.

LLVM_ABI Type * getType() const

Return the LLVM type of this SCEV expression.

static LLVM_ABI LoopGuards collect(const Loop *L, ScalarEvolution &SE)

Collect rewrite map for loop guards for loop L, together with flags indicating if NUW and NSW can be ...

The main scalar evolution driver.

const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)

When successful, this returns a SCEVConstant that is greater than or equal to (i.e.

LLVM_ABI bool isKnownNegative(const SCEV *S)

Test if the given expression is known to be negative.

LLVM_ABI bool isKnownNonZero(const SCEV *S)

Test if the given expression is known to be non-zero.

LLVM_ABI const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)

If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...

LLVM_ABI const SCEV * getConstant(ConstantInt *V)

LLVM_ABI const SCEV * getSCEV(Value *V)

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

const SCEV * getOne(Type *Ty)

Return a SCEV for the constant 1 of a specific type.

LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L)

Return true if the value of the given SCEV is unchanging in the specified loop.

LLVM_ABI bool isKnownPositive(const SCEV *S)

Test if the given expression is known to be positive.

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 const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)

Return LHS-RHS.

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 std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)

If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...

LLVM_ABI const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)

Try to apply information from loop guards for L to Expr.

LLVM_ABI std::optional< bool > evaluatePredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)

Check whether the condition described by Pred, LHS, and RHS is true or false.

LLVM_ABI const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)

Get a canonical add expression, or something simpler if possible.

LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)

Test if the given expression is known to satisfy the condition described by Pred, LHS,...

This class represents the LLVM 'select' instruction.

void insert_range(Range &&R)

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

bool contains(ConstPtrType Ptr) const

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.

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

bool isIntegerTy() const

True if this is an instance of IntegerType.

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.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

self_iterator getIterator()

@ BasicBlock

Various leaf nodes.

OneUse_match< SubPat > m_OneUse(const SubPat &SP)

BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)

brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)

class_match< BasicBlock > m_BasicBlock()

Match an arbitrary basic block value and ignore it.

BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)

cst_pred_ty< is_one > m_scev_One()

Match an integer 1.

specificloop_ty m_SpecificLoop(const Loop *L)

SCEVAffineAddRec_match< Op0_t, Op1_t, class_match< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)

bool match(const SCEV *S, const Pattern &P)

class_match< const SCEV > m_SCEV()

initializer< Ty > init(const Ty &Val)

NodeAddr< PhiNode * > Phi

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.

FunctionAddr VTableAddr Value

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

Return either:

bool all_of(R &&range, UnaryPredicate P)

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

static cl::opt< bool > DisableAdvancedPeeling("disable-advanced-peeling", cl::init(false), cl::Hidden, cl::desc("Disable advance peeling. Issues for convergent targets (D134803)."))

static cl::opt< bool > UnrollAllowPeeling("unroll-allow-peeling", cl::init(true), cl::Hidden, cl::desc("Allows loops to be peeled when the dynamic " "trip count is known to be low."))

LLVM_ABI bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)

Check if we can prove that all paths starting from this block converge to a block that either has a @...

static cl::opt< bool > EnablePeelingForIV("enable-peeling-for-iv", cl::init(false), cl::Hidden, cl::desc("Enable peeling to convert Phi nodes into IVs"))

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

decltype(auto) dyn_cast(const From &Val)

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

bool canPeel(const Loop *L)

Definition LoopPeel.cpp:95

bool canPeelLastIteration(const Loop &L, ScalarEvolution &SE)

Returns true if the last iteration of L can be peeled off.

Definition LoopPeel.cpp:479

LLVM_ABI void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)

Set input string into loop metadata by keeping other values intact.

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

static const char * PeeledCountMetaData

Definition LoopPeel.cpp:89

DomTreeNodeBase< BasicBlock > DomTreeNode

bool any_of(R &&range, UnaryPredicate P)

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

TargetTransformInfo::PeelingPreferences gatherPeelingPreferences(Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, std::optional< bool > UserAllowPeeling, std::optional< bool > UserAllowProfileBasedPeeling, bool UnrollingSpecficValues=false)

Definition LoopPeel.cpp:1057

LLVM_ABI raw_ostream & dbgs()

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

void computePeelCount(Loop *L, unsigned LoopSize, TargetTransformInfo::PeelingPreferences &PP, unsigned TripCount, DominatorTree &DT, ScalarEvolution &SE, const TargetTransformInfo &TTI, AssumptionCache *AC=nullptr, unsigned Threshold=UINT_MAX)

Definition LoopPeel.cpp:751

LLVM_ABI cl::opt< unsigned > SCEVCheapExpansionBudget

BranchProbability getLoopProbability(Loop *L)

Based on branch weight metadata, return either:

static cl::opt< unsigned > UnrollForcePeelCount("unroll-force-peel-count", cl::init(0), cl::Hidden, cl::desc("Force a peel count regardless of profiling information."))

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 std::optional< int > getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name)

Find named metadata for a loop with an integer value.

bool setLoopProbability(Loop *L, BranchProbability P)

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

static cl::opt< bool > UnrollAllowLoopNestsPeeling("unroll-allow-loop-nests-peeling", cl::init(false), cl::Hidden, cl::desc("Allows loop nests to be peeled."))

static cl::opt< unsigned > UnrollPeelMaxCount("unroll-peel-max-count", cl::init(7), cl::Hidden, cl::desc("Max average trip count which will cause loop peeling."))

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 isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)

Return true if this is always a dereferenceable pointer.

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 bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)

Extract branch weights from MD_prof metadata.

decltype(auto) cast(const From &Val)

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

LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)

Split the specified block at the specified instruction.

cl::opt< bool > ProfcheckDisableMetadataFixes("profcheck-disable-metadata-fixes", cl::Hidden, cl::init(false), cl::desc("Disable metadata propagation fixes discovered through Issue #147390"))

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 BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")

Split the edge connecting the specified blocks, and return the newly created basic block between From...

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

Put loop into LCSSA form.

bool peelLoop(Loop *L, unsigned PeelCount, bool PeelLast, LoopInfo *LI, ScalarEvolution *SE, DominatorTree &DT, AssumptionCache *AC, bool PreserveLCSSA, ValueToValueMapTy &VMap)

VMap is the value-map that maps instructions from the original loop to instructions in the last peele...

Definition LoopPeel.cpp:1102

static cl::opt< unsigned > UnrollPeelCount("unroll-peel-count", cl::Hidden, cl::desc("Set the unroll peeling count, for testing purposes"))

LLVM_ABI Loop * cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM)

Recursively clone the specified loop and all of its children, mapping the blocks with the specified m...

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

Implement std::swap in terms of BitVector swap.

bool AllowPeeling

Allow peeling off loop iterations.

bool AllowLoopNestsPeeling

Allow peeling off loop iterations for loop nests.

bool PeelLast

Peel off the last PeelCount loop iterations.

bool PeelProfiledIterations

Allow peeling basing on profile.

unsigned PeelCount

A forced peeling factor (the number of bodied of the original loop that should be peeled off before t...