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 if (I.mayWriteToMemory())

451 return 0;

452

455

456

457 if (BB == Header)

458 continue;

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

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

464 }

465 }

466 }

468 L.getExitingBlocks(ExitingBlocks);

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

471 }))

472 return 1;

473 return 0;

474}

475

479 return false;

480

481

482

483

484

485

486 BasicBlock *Latch = L.getLoopLatch();

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

502}

503

504

505

506

512 return false;

513

515 SCEVExpander Expander(SE, L.getHeader()->getDataLayout(), "loop-peel");

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

519 return false;

520

527

529 RightSCEV) &&

531}

532

533

534

535

536

537

538

539

540

541

542

543

544static std::pair<unsigned, unsigned>

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

548 unsigned DesiredPeelCount = 0;

549 unsigned DesiredPeelCountLast = 0;

550

551

554 MaxPeelCount =

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

556

557

558

559

560 auto PeelWhilePredicateIsKnown =

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

563 while (PeelCount < MaxPeelCount &&

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

566 ++PeelCount;

567 }

569 BoundSCEV);

570 };

571

572 const unsigned MaxDepth = 4;

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

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

576 return;

577

578 Value *LeftVal, *RightVal;

581 ComputePeelCount(LeftVal, Depth + 1);

582 ComputePeelCount(RightVal, Depth + 1);

583 return;

584 }

585

588 return;

589

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

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

592

593

594

596 return;

597

598

599

604 } else

605 return;

606 }

607

609

610

611

613 return;

616 return;

617

618

619

620 unsigned NewPeelCount = DesiredPeelCount;

621

624

625

626

627

630

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

633 Pred)) {

635 DesiredPeelCountLast = 1;

636 return;

637 }

638

639

640

641

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

645 RightSCEV) &&

648 if (NewPeelCount >= MaxPeelCount)

649 return;

650 ++NewPeelCount;

651 }

652

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

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

655 };

656

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

659 return;

661 const SCEV *BoundSCEV, *IterSCEV;

662 if (L.isLoopInvariant(LHS)) {

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

668 } else

669 return;

671

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

673 return;

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

675 bool IsSigned = MinMax->isSigned();

676

677

683 else

684 return;

685

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

687 return;

688 unsigned NewPeelCount = DesiredPeelCount;

689 const SCEV *IterVal = AddRec->evaluateAtIteration(

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

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

692 Pred)) {

694 DesiredPeelCountLast = 1;

695 return;

696 }

697 DesiredPeelCount = NewPeelCount;

698 };

699

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

705 ComputePeelCountMinMax(MinMax);

706 }

707

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

710 continue;

711

712

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

714 continue;

715

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

717 }

718

719 return {DesiredPeelCount, DesiredPeelCountLast};

720}

721

722

723

724

725

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

728 if (!Latch)

729 return true;

730

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

733 return true;

734

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

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

738

740 L->getUniqueNonLatchExitBlocks(ExitBlocks);

743 });

744}

745

746

747

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

754

755

756 unsigned TargetPeelCount = PP.PeelCount;

760 return;

761

762

763

764

766 return;

767

768

770 if (UserPeelCount) {

772 << " iterations.\n");

775 return;

776 }

777

778

780 return;

781

782

783 if (2 * LoopSize > Threshold)

784 return;

785

786 unsigned AlreadyPeeled = 0;

788 AlreadyPeeled = *Peeled;

789

791 return;

792

793

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

796

797

798

799 unsigned DesiredPeelCount = TargetPeelCount;

800

801

802

803

804

805

806 if (MaxPeelCount > DesiredPeelCount) {

807

809 .calculateIterationsToPeel();

810 if (NumPeels)

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

812 }

813

814 const auto &[CountToEliminateCmps, CountToEliminateCmpsLast] =

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

817

818 if (DesiredPeelCount == 0)

820

821 if (DesiredPeelCount > 0) {

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

823

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

827 << " iteration(s) to turn"

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

832 return;

833 }

834 }

835

836 if (CountToEliminateCmpsLast > 0) {

837 unsigned DesiredPeelCountLast =

838 std::min(CountToEliminateCmpsLast, MaxPeelCount);

839

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

843 << " iteration(s) to turn"

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

845 PP.PeelCount = DesiredPeelCountLast;

848 return;

849 }

850 }

851

852

853

854 if (TripCount)

855 return;

856

857

859 return;

860

861

862

863

864

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

867 return;

869 if (!EstimatedTripCount)

870 return;

871

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

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

874

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

876 unsigned PeelCount = *EstimatedTripCount;

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

879 return;

880 }

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

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

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

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

887 }

888}

889

890

891

892

893

894

895

896

897

898

899

900

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

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

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

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

912

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

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

917

918

919

923

924

925

926

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

929

930 VMap[*BB] = NewBB;

931

932

933 if (DT) {

934 if (Header == *BB)

936 else {

938

940 }

941 }

942 }

943

944 {

945

946

947

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

950 Header->getContext(), Ext);

951 }

952

953

954

955 for (Loop *ChildLoop : *L) {

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

957 }

958

959

960

961

962

964

965

966

968 if (PeelLast) {

969

970

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

973 LatchTerm->setSuccessor(0, InsertBot);

974 LatchTerm->setSuccessor(1, InsertBot);

975 } else {

977

978

979

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

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

982 LatchTerm->setSuccessor(idx, InsertBot);

983 break;

984 }

985 }

986 }

987 if (DT)

989

990

991

992

993

994 if (PeelLast) {

995

996

997

998

1004 if (OrigPreHeader)

1006 OrigPreHeader);

1007

1009 Latch);

1010 VMap[&*I] = PN;

1011 }

1012 } else {

1013

1014

1015

1016

1019 if (IterNumber == 0) {

1021 } else {

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

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

1026 else

1027 VMap[&*I] = LatchVal;

1028 }

1030 }

1031 }

1032

1033

1034

1035

1036

1037 for (auto Edge : ExitEdges)

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

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

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

1042 LatchVal = VMap[LatchVal];

1045 }

1046

1047

1048

1049 for (auto KV : VMap)

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

1051}

1052

1053TargetTransformInfo::PeelingPreferences

1056 std::optional UserAllowPeeling,

1057 std::optional UserAllowProfileBasedPeeling,

1058 bool UnrollingSpecficValues) {

1060

1061

1067

1068

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

1070

1071

1072 if (UnrollingSpecficValues) {

1079 }

1080

1081

1082 if (UserAllowPeeling)

1084 if (UserAllowProfileBasedPeeling)

1086

1087 return PP;

1088}

1089

1090

1091

1092

1093

1094

1095

1096

1097

1098

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

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

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

1106 "only peel a single iteration");

1107

1109 LoopBlocks.perform(LI);

1110

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

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

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

1115 L->getExitEdges(ExitEdges);

1116

1117

1118

1119

1120

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

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

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

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

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

1128 ChildrenToUpdate.push_back(ChildBB);

1129 }

1130

1131

1132

1133

1135 for (auto *ChildBB : ChildrenToUpdate)

1136 NonLoopBlocksIDom[ChildBB] = NewIDom;

1137 }

1138

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

1140

1141

1146 if (PeelLast) {

1147

1148

1149

1150

1151

1152

1153

1154

1155

1156

1157

1158

1159

1160

1161

1162

1163

1164

1165

1166

1167

1168

1169

1170

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

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

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

1174

1176

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

1179

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

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

1182 NewPreHeader = nullptr;

1183

1184

1185

1186

1187

1189

1190

1191

1192

1193

1194

1195

1196

1197

1198

1200

1201

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

1204

1205

1206

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

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

1211 }

1212 }

1213 } else {

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

1216

1218 Value *BTCValue =

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

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

1228 if (HasBranchWeights) {

1229

1230

1231

1232

1233

1234

1235

1236

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

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

1240 }

1242

1243

1245 }

1246 } else {

1247

1248

1249

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 InsertTop = SplitEdge(PreHeader, Header, &DT, LI);

1295

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

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

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

1299 }

1300

1303

1304

1305

1308

1309

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

1313

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

1315 NewPreHeader ? PreHeader : nullptr, ExitEdges, NewBlocks,

1316 LoopBlocks, VMap, LVMap, &DT, LI,

1317 LoopLocalNoAliasDeclScopes, *SE);

1318

1319

1320

1322

1323 if (Iter == 0) {

1324 if (PeelLast) {

1325

1326

1327

1328

1329

1330

1331 auto *Cmp =

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

1334 Cmp->setOperand(

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

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

1337 } else {

1338

1339 for (auto BBIDom : NonLoopBlocksIDom)

1342 }

1343 }

1344

1345#ifdef EXPENSIVE_CHECKS

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

1347#endif

1348

1349

1350

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

1353

1354 InsertTop = InsertBot;

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

1357

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

1359 F->end());

1360 }

1361

1362 if (PeelLast) {

1363

1364

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

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

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

1369 else

1370 P->replaceAllUsesWith(E);

1371 P->eraseFromParent();

1372 }

1374 } else {

1375

1376

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

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

1382 NewVal = LVMap[LatchInst];

1383

1384 PHI->setIncomingValueForBlock(NewPreHeader, NewVal);

1385 }

1386 }

1387

1388

1389 unsigned AlreadyPeeled = 0;

1391 AlreadyPeeled = *Peeled;

1392 unsigned TotalPeeled = AlreadyPeeled + PeelCount;

1394

1395

1396

1397

1398

1399

1400

1401

1402

1403

1404

1405

1406

1407

1408

1409

1410

1411

1413 unsigned EstimatedTripCountNew = *EstimatedTripCount;

1414 if (EstimatedTripCountNew < TotalPeeled)

1415 EstimatedTripCountNew = 0;

1416 else

1417 EstimatedTripCountNew -= TotalPeeled;

1419 }

1420

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

1422 L = ParentLoop;

1423

1424

1427

1428#ifdef EXPENSIVE_CHECKS

1429

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

1431#endif

1432

1433

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

1435

1436 NumPeeled++;

1437 NumPeeledEnd += PeelLast;

1438

1439 return true;

1440}

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

static bool violatesLegacyMultiExitLoopCheck(Loop *L)

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

Definition LoopPeel.cpp:726

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

Definition LoopPeel.cpp:545

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

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

LLVM_ABI const DataLayout & getDataLayout() const

Get the data layout of the module this basic block belongs to.

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

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

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

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

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