IndVarSimplify.cpp Source File (original) (raw)

76#include

77#include

78#include

80using namespace llvm;

84#define DEBUG_TYPE "indvars"

86 STATISTIC(NumWidened , "Number of indvars widened");

87 STATISTIC(NumReplaced , "Number of exit values replaced");

88 STATISTIC(NumLFTR , "Number of loop exit tests replaced");

89 STATISTIC(NumElimExt , "Number of IV sign/zero extends eliminated");

90 STATISTIC(NumElimIV , "Number of congruent IVs eliminated");

94 cl::desc("Choose the strategy to replace exit value in IndVarSimplify"),

98 "only replace exit value when the cost is cheap"),

101 "only replace exit value when it is an unused "

102 "induction variable in the loop and has cheap replacement cost"),

104 "only replace exit values when loop def likely dead"),

106 "always replace exit value whenever possible")));

107

109 "indvars-post-increment-ranges", cl::Hidden,

110 cl::desc("Use post increment control-dependent ranges in IndVarSimplify"),

112

115 cl::desc("Disable Linear Function Test Replace optimization"));

116

119 cl::desc("Predicate conditions in read only loops"));

120

123 cl::desc("Predicate conditions that trap in loops with only local writes"));

124

127 cl::desc("Allow widening of indvars to eliminate s/zext"));

128

129namespace {

130

131class IndVarSimplify {

138 std::unique_ptr MSSAU;

139

141 bool WidenIndVars;

142

143 bool RunUnswitching = false;

144

145 bool handleFloatingPointIV(Loop *L, PHINode *PH);

146 bool rewriteNonIntegerIVs(Loop *L);

147

149

150

151

152 bool canonicalizeExitCondition(Loop *L);

153

155

156

158

159 bool rewriteFirstIterationLoopExitValues(Loop *L);

160

161 bool linearFunctionTestReplace(Loop *L, BasicBlock *ExitingBB,

162 const SCEV *ExitCount,

164

165 bool sinkUnusedInvariants(Loop *L);

166

167public:

171 : LI(LI), SE(SE), DT(DT), DL(DL), TLI(TLI), TTI(TTI),

172 WidenIndVars(WidenIndVars) {

173 if (MSSA)

174 MSSAU = std::make_unique(MSSA);

175 }

176

177 bool run(Loop *L);

178

179 bool runUnswitching() const { return RunUnswitching; }

180};

181

182}

183

184

185

186

187

188

190 bool isExact = false;

191

195 !isExact)

196 return false;

197 IntVal = UIntVal;

198 return true;

199}

200

201

202

203

205 int64_t IntVal) {

208 return false;

210}

211

212

213

226

227

234

236 switch (FPPred) {

255 default:

257 }

258}

259

260

261

262

263

264static std::optional

266

267 unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));

268 unsigned BackEdge = IncomingEdge ^ 1;

269

270

272 if (!InitValueVal)

273 return std::nullopt;

274

275

276

278 if (!Incr || Incr->getOpcode() != Instruction::FAdd)

279 return std::nullopt;

280

281

282

284 if (!IncValueVal || Incr->getOperand(0) != PN)

285 return std::nullopt;

286

287

288

289

290 if (!Incr->hasNUses(2))

291 return std::nullopt;

292

293

294

296 [](const User *U) { return isa(U); });

297 if (It == Incr->users().end())

298 return std::nullopt;

299

301 if (!Compare->hasOneUse())

302 return std::nullopt;

303

304

305

306

307

309 if (!BI)

310 return std::nullopt;

311

312 assert(BI->isConditional() && "Can't use fcmp if not conditional");

313 if (!L->contains(BI->getParent()) ||

314 (L->contains(BI->getSuccessor(0)) && L->contains(BI->getSuccessor(1))))

315 return std::nullopt;

316

317

318

320 if (!ExitValueVal)

321 return std::nullopt;

322

324 IncValueVal->getValueAPF(),

325 ExitValueVal->getValueAPF(), Compare, Incr);

326}

327

328

329

330

331

332static std::optional

334

337 return std::nullopt;

338

339

340 int64_t InitValue, IncrValue, ExitValue;

344 return std::nullopt;

345

346

349 return std::nullopt;

350

351

352

353

354

355

356

358 return std::nullopt;

359

360

361 if (IncrValue == 0)

362 return std::nullopt;

363

364

365 if (IncrValue > 0) {

366

367

368 if (InitValue >= ExitValue)

369 return std::nullopt;

370

372

373

375 if (++Range == 0)

376 return std::nullopt;

377 }

378

380

381

382

383

385 Leftover != 0)

386 return std::nullopt;

387

388

389

390 if (Leftover != 0 && int32_t(ExitValue + IncrValue) < ExitValue)

391 return std::nullopt;

392 } else {

393

394

395 if (InitValue <= ExitValue)

396 return std::nullopt;

397

399

400

402 if (++Range == 0)

403 return std::nullopt;

404 }

405

406 unsigned Leftover = Range % uint32_t(-IncrValue);

407

408

409

410

412 Leftover != 0)

413 return std::nullopt;

414

415

416

417 if (Leftover != 0 && int32_t(ExitValue + IncrValue) > ExitValue)

418 return std::nullopt;

419 }

420

421 return IntegerIV{InitValue, IncrValue, ExitValue, NewPred};

422}

423

424

429 std::unique_ptr &MSSAU) {

430 unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));

431 unsigned BackEdge = IncomingEdge ^ 1;

432

436

437 LLVM_DEBUG(dbgs() << "INDVARS: Rewriting floating-point IV to integer IV:\n"

438 << " Init: " << IIV.InitValue << "\n"

439 << " Incr: " << IIV.IncrValue << "\n"

440 << " Exit: " << IIV.ExitValue << "\n"

442 << "\n"

443 << " Original PN: " << *PN << "\n");

444

445

451

452 Instruction *NewAdd = BinaryOperator::CreateAdd(

454 Incr->getName() + ".int", Incr->getIterator());

455 NewAdd->setDebugLoc(Incr->getDebugLoc());

457

459 BI->getIterator(), IIV.NewPred, NewAdd,

462

463

464

466

467

468

472

473

476

477

478

479

480

481

482

483

484 if (WeakPH) {

486 PN->getParent()->getFirstInsertionPt());

490 }

491}

492

493

494

495

496

497

498

499

500bool IndVarSimplify::handleFloatingPointIV(Loop *L, PHINode *PN) {

501

503 if (!FPIV)

504 return false;

505

506

508 if (!IIV)

509 return false;

510

511

513 return true;

514}

515

516bool IndVarSimplify::rewriteNonIntegerIVs(Loop *L) {

517

518

519

521

523

525 for (WeakTrackingVH &PHI : PHIs)

527 Changed |= handleFloatingPointIV(L, PN);

528

529

530

531

535}

536

537

538

539

540

541

542

543

544

545

546bool IndVarSimplify::rewriteFirstIterationLoopExitValues(Loop *L) {

547

548 assert(L->isLCSSAForm(*DT));

549

550 SmallVector<BasicBlock *, 8> ExitBlocks;

551 L->getUniqueExitBlocks(ExitBlocks);

552

553 bool MadeAnyChanges = false;

554 for (auto *ExitBB : ExitBlocks) {

555

556

557 for (PHINode &PN : ExitBB->phis()) {

559 IncomingValIdx != E; ++IncomingValIdx) {

561

562

563

564

565

566

567 if (->getLoopLatch() ||

568 !DT->dominates(IncomingBB, L->getLoopLatch()))

569 continue;

570

571

573

576

577

578 Cond = BI->getCondition();

580 Cond = SI->getCondition();

581 else

582 continue;

583

584 if (->isLoopInvariant(Cond))

585 continue;

586

588

589

590 if (!ExitVal || ExitVal->getParent() != L->getHeader())

591 continue;

592

593

594

595

596 auto *LoopPreheader = L->getLoopPreheader();

597 assert(LoopPreheader && "Invalid loop");

598 int PreheaderIdx = ExitVal->getBasicBlockIndex(LoopPreheader);

599 if (PreheaderIdx != -1) {

600 assert(ExitVal->getParent() == L->getHeader() &&

601 "ExitVal must be in loop header");

602 MadeAnyChanges = true;

604 ExitVal->getIncomingValue(PreheaderIdx));

606 }

607 }

608 }

609 }

610 return MadeAnyChanges;

611}

612

613

614

615

616

617

618

619

623 bool IsSigned = Cast->getOpcode() == Instruction::SExt;

624 if (!IsSigned && Cast->getOpcode() != Instruction::ZExt)

625 return;

626

630 return;

631

632

633

634

635

637 if (NarrowIVWidth >= Width)

638 return;

639

640

641

642

643

644

645

646 if (TTI &&

647 TTI->getArithmeticInstrCost(Instruction::Add, Ty) >

648 TTI->getArithmeticInstrCost(Instruction::Add,

650 return;

651 }

652

657 return;

658 }

659

660

661

662

663

665}

666

667

668

669

670

671

672

673

674

675namespace {

676

677class IndVarSimplifyVisitor : public IVVisitor {

678 ScalarEvolution *SE;

679 const TargetTransformInfo *TTI;

680 PHINode *IVPhi;

681

682public:

683 WideIVInfo WI;

684

685 IndVarSimplifyVisitor(PHINode *IV, ScalarEvolution *SCEV,

686 const TargetTransformInfo *TTI,

687 const DominatorTree *DTree)

688 : SE(SCEV), TTI(TTI), IVPhi(IV) {

689 DT = DTree;

691 }

692

693

694 void visitCast(CastInst *Cast) override { visitIVCast(Cast, WI, SE, TTI); }

695};

696

697}

698

699

700

701

702

703

704bool IndVarSimplify::simplifyAndExtend(Loop *L,

706 LoopInfo *LI) {

708

710 L->getBlocks()[0]->getModule(), Intrinsic::experimental_guard);

711 bool HasGuards = GuardDecl && !GuardDecl->use_empty();

712

715

716

717

718

719

721 while (!LoopPhis.empty()) {

722

723

724

725

726

727

728 do {

729 PHINode *CurrIV = LoopPhis.pop_back_val();

730

731

732 IndVarSimplifyVisitor Visitor(CurrIV, SE, TTI, DT);

733

736

738 RunUnswitching |= U;

739 if (Visitor.WI.WidestNativeType) {

741 }

742 } while(!LoopPhis.empty());

743

744

745 if (!WidenIndVars)

746 continue;

747

749 unsigned ElimExt;

750 unsigned Widened;

752 DT, DeadInsts, ElimExt, Widened,

754 NumElimExt += ElimExt;

755 NumWidened += Widened;

757 LoopPhis.push_back(WidePhi);

758 }

759 }

760 }

762}

763

764

765

766

767

768

769

770

773 if (!IncI)

774 return nullptr;

775

777 case Instruction::Add:

778 case Instruction::Sub:

779 break;

780 case Instruction::GetElementPtr:

781

783 break;

784 [[fallthrough]];

785 default:

786 return nullptr;

787 }

788

790 if (Phi && Phi->getParent() == L->getHeader()) {

791 if (L->isLoopInvariant(IncI->getOperand(1)))

792 return Phi;

793 return nullptr;

794 }

795 if (IncI->getOpcode() == Instruction::GetElementPtr)

796 return nullptr;

797

798

800 if (Phi && Phi->getParent() == L->getHeader()) {

801 if (L->isLoopInvariant(IncI->getOperand(0)))

802 return Phi;

803 }

804 return nullptr;

805}

806

807

808

812

813 if (!ICmp)

814 return false;

815

816

818}

819

820

821

823 assert(L->getLoopLatch() && "Must be in simplified form");

824

825

826

827

828

831 return false;

832

833

836 return true;

837

838

841 return true;

842

843

846 if (!L->isLoopInvariant(RHS)) {

847 if (!L->isLoopInvariant(LHS))

848 return true;

850 }

851

853 if (!Phi)

855

856 if (!Phi)

857 return true;

858

859

860 int Idx = Phi->getBasicBlockIndex(L->getLoopLatch());

861 if (Idx < 0)

862 return true;

863

864

865 Value *IncV = Phi->getIncomingValue(Idx);

867}

868

869

870

871

873 unsigned Depth) {

876

878 return false;

879

880

881

883 if ()

884 return false;

885

886

888 return false;

889

890

891 for (Value *Op : I->operands()) {

892 if (!Visited.insert(Op).second)

893 continue;

895 return false;

896 }

897 return true;

898}

899

900

901

902

903

904

910

911

912

913

916 assert(Phi->getParent() == L->getHeader());

917 assert(L->getLoopLatch());

918

920 return false;

921

924 return false;

925

926 int LatchIdx = Phi->getBasicBlockIndex(L->getLoopLatch());

927 Value *IncV = Phi->getIncomingValue(LatchIdx);

930}

931

932

933

934

935

936

937

938

940 const SCEV *BECount,

943

945

946

947 PHINode *BestPhi = nullptr;

948 const SCEV *BestInit = nullptr;

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

950 assert(LatchBlock && "Must be in simplified form");

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

952

956 continue;

957

959

960

961

962

964 if (PhiWidth < BCWidth || .isLegalInteger(PhiWidth))

965 continue;

966

967

968

970

971

972

973 Value *IncPhi = Phi->getIncomingValueForBlock(LatchBlock);

976 continue;

977 }

978

979

980

981

982

983

984

985

986

987 if (!Phi->getType()->isIntegerTy() &&

989 continue;

990

991 const SCEV *Init = AR->getStart();

992

994

996 continue;

997

998

999

1000 if (BestInit->isZero() != Init->isZero()) {

1001 if (BestInit->isZero())

1002 continue;

1003 }

1004

1005

1006

1007 else if (PhiWidth <= SE->getTypeSizeInBits(BestPhi->getType()))

1008 continue;

1009 }

1010 BestPhi = Phi;

1011 BestInit = Init;

1012 }

1013 return BestPhi;

1014}

1015

1016

1017

1018

1020 const SCEV *ExitCount, bool UsePostInc, Loop *L,

1026

1027

1028

1029

1030

1031

1038 }

1039

1043 "Computed iteration count is not loop invariant!");

1044 return Rewriter.expandCodeFor(IVLimit, ARBase->getType(),

1046}

1047

1048

1049

1050

1051

1052

1053bool IndVarSimplify::

1054linearFunctionTestReplace(Loop *L, BasicBlock *ExitingBB,

1055 const SCEV *ExitCount,

1056 PHINode *IndVar, SCEVExpander &Rewriter) {

1057 assert(L->getLoopLatch() && "Loop no longer in simplified form?");

1061

1062

1063 Value *CmpIndVar = IndVar;

1064 bool UsePostInc = false;

1065

1066

1067

1068

1069 if (ExitingBB == L->getLoopLatch()) {

1070

1071

1072

1073

1074 bool SafeToPostInc =

1078 if (SafeToPostInc) {

1079 UsePostInc = true;

1080 CmpIndVar = IncVar;

1081 }

1082 }

1083

1084

1085

1086

1087

1088

1089

1090

1091

1092

1093

1094

1095

1098 if (BO->hasNoUnsignedWrap())

1100 if (BO->hasNoSignedWrap())

1102 }

1103

1105 IndVar, ExitingBB, ExitCount, UsePostInc, L, Rewriter, SE);

1108 "genLoopLimit missed a cast");

1109

1110

1112 ICmpInst::Predicate P;

1114 P = ICmpInst::ICMP_NE;

1115 else

1116 P = ICmpInst::ICMP_EQ;

1117

1119

1120

1121

1123 Builder.SetCurrentDebugLocation(Cond->getDebugLoc());

1124

1125

1126

1127

1128

1129

1132 if (CmpIndVarSize > ExitCntSize) {

1135

1136

1137

1138

1139

1140

1142 const SCEV *IV = SE->getSCEV(CmpIndVar);

1144 const SCEV *ZExtTrunc =

1146

1147 if (ZExtTrunc == IV) {

1149 ExitCnt = Builder.CreateZExt(ExitCnt, IndVar->getType(),

1150 "wide.trip.count");

1151 } else {

1152 const SCEV *SExtTrunc =

1154 if (SExtTrunc == IV) {

1156 ExitCnt = Builder.CreateSExt(ExitCnt, IndVar->getType(),

1157 "wide.trip.count");

1158 }

1159 }

1160

1161 if (Extended) {

1162 bool Discard;

1163 L->makeLoopInvariant(ExitCnt, Discard);

1164 } else

1165 CmpIndVar = Builder.CreateTrunc(CmpIndVar, ExitCnt->getType(),

1166 "lftr.wideiv");

1167 }

1168 LLVM_DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n"

1169 << " LHS:" << *CmpIndVar << '\n'

1170 << " op:\t" << (P == ICmpInst::ICMP_NE ? "!=" : "==")

1171 << "\n"

1172 << " RHS:\t" << *ExitCnt << "\n"

1173 << "ExitCount:\t" << *ExitCount << "\n"

1174 << " was: " << *BI->getCondition() << "\n");

1175

1176 Value *Cond = Builder.CreateICmp(P, CmpIndVar, ExitCnt, "exitcond");

1178

1179

1180

1181

1182

1185

1186 ++NumLFTR;

1187 return true;

1188}

1189

1190

1191

1192

1193

1194

1195

1196

1197bool IndVarSimplify::sinkUnusedInvariants(Loop *L) {

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

1199 if (!ExitBlock) return false;

1200

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

1202 if (!Preheader) return false;

1203

1204 bool MadeAnyChanges = false;

1206

1207

1209 continue;

1210

1211

1213 break;

1214

1215

1216

1217

1218

1219

1220

1221 if (I.mayHaveSideEffects() || I.mayReadFromMemory())

1222 continue;

1223

1224

1225 if (I.isDebugOrPseudoInst())

1226 continue;

1227

1228

1229 if (I.isEHPad())

1230 continue;

1231

1232

1233

1234

1235

1237 continue;

1238

1239

1240

1241 bool UsedInLoop = false;

1242 for (Use &U : I.uses()) {

1246 unsigned i =

1248 UseBB = P->getIncomingBlock(i);

1249 }

1250 if (UseBB == Preheader || L->contains(UseBB)) {

1251 UsedInLoop = true;

1252 break;

1253 }

1254 }

1255

1256

1257 if (UsedInLoop)

1258 continue;

1259

1260

1263 MadeAnyChanges = true;

1264 }

1265

1266 return MadeAnyChanges;

1267}

1268

1272 LLVM_DEBUG(dbgs() << "Replacing condition of loop-exiting branch " << *BI

1273 << " with " << *NewCond << "\n");

1275 if (OldCond->use_empty())

1277}

1278

1280 bool IsTaken) {

1282 bool ExitIfTrue = !L->contains(*succ_begin(ExitingBB));

1284 return ConstantInt::get(OldCond->getType(),

1285 IsTaken ? ExitIfTrue : !ExitIfTrue);

1286}

1287

1294

1298 assert(L->isLoopSimplifyForm() && "Should only do it in simplify form!");

1299 auto *LoopPreheader = L->getLoopPreheader();

1300 auto *LoopHeader = L->getHeader();

1302 for (auto &PN : LoopHeader->phis()) {

1309 }

1310

1311

1312

1314 while (!Worklist.empty()) {

1316 if (!Visited.insert(I).second)

1317 continue;

1318

1319

1320 if (!L->contains(I))

1321 continue;

1322

1325 for (User *U : I->users())

1327 I->replaceAllUsesWith(Res);

1329 }

1330 }

1331}

1332

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

1339 assert(Preheader && "Preheader doesn't exist");

1340 Rewriter.setInsertPoint(Preheader->getTerminator());

1341 auto *LHSV = Rewriter.expandCodeFor(LIP.LHS);

1342 auto *RHSV = Rewriter.expandCodeFor(LIP.RHS);

1343 bool ExitIfTrue = !L->contains(*succ_begin(ExitingBB));

1344 if (ExitIfTrue)

1348 return Builder.CreateICmp(InvariantPred, LHSV, RHSV,

1350}

1351

1352static std::optional<Value *>

1354 const SCEV *MaxIter, bool Inverted, bool SkipLastIter,

1359

1360

1362 if (Inverted)

1364

1367

1370

1371 auto *ARTy = LHSS->getType();

1372 auto *MaxIterTy = MaxIter->getType();

1373

1381 }

1382

1383 if (SkipLastIter) {

1384

1385

1386

1387

1390 for (const SCEV *Op : UMin->operands())

1393 } else

1395 }

1396

1397

1399 L, BI, MaxIter);

1400 if (!LIP)

1401 return std::nullopt;

1402

1403

1406 else

1408}

1409

1416 "Not a loop exit!");

1417

1418

1419

1420

1421 bool Inverted = L->contains(BI->getSuccessor(1));

1426 Visited.insert(OldCond);

1428

1429 auto GoThrough = [&](Value *V) {

1431 if (Inverted) {

1433 return false;

1434 } else {

1436 return false;

1437 }

1442 return true;

1443 };

1444

1445 do {

1447

1448

1450 if (!GoThrough(Curr))

1453 } while (!Worklist.empty());

1454

1455

1456

1457

1458

1460 if (!SkipLastIter && LeafConditions.size() > 1 &&

1463 MaxIter)

1464 for (auto *ICmp : LeafConditions) {

1466 false);

1467 const SCEV *ExitMax = EL.SymbolicMaxNotTaken;

1469 continue;

1470

1471

1472 auto *WiderType =

1476 if (WideExitMax == WideMaxIter)

1477 ICmpsFailingOnLastIter.insert(ICmp);

1478 }

1479

1481 for (auto *OldCond : LeafConditions) {

1482

1483

1484

1485

1486 bool OptimisticSkipLastIter = SkipLastIter;

1487 if (!OptimisticSkipLastIter) {

1488 if (ICmpsFailingOnLastIter.size() > 1)

1489 OptimisticSkipLastIter = true;

1490 else if (ICmpsFailingOnLastIter.size() == 1)

1491 OptimisticSkipLastIter = !ICmpsFailingOnLastIter.count(OldCond);

1492 }

1493 if (auto Replaced =

1495 OptimisticSkipLastIter, SE, Rewriter)) {

1497 auto *NewCond = *Replaced;

1499 NCI->setName(OldCond->getName() + ".first_iter");

1500 }

1501 LLVM_DEBUG(dbgs() << "Unknown exit count: Replacing " << *OldCond

1502 << " with " << *NewCond << "\n");

1506

1507

1508 ICmpsFailingOnLastIter.erase(OldCond);

1509 }

1510 }

1512}

1513

1514bool IndVarSimplify::canonicalizeExitCondition(Loop *L) {

1515

1516

1517

1518

1519

1520

1521

1522

1523

1524 SmallVector<BasicBlock*, 16> ExitingBlocks;

1525 L->getExitingBlocks(ExitingBlocks);

1527 for (auto *ExitingBB : ExitingBlocks) {

1529 if (!BI)

1530 continue;

1532

1534 if (!ICmp || !ICmp->hasOneUse())

1535 continue;

1536

1537 auto *LHS = ICmp->getOperand(0);

1538 auto *RHS = ICmp->getOperand(1);

1539

1540

1541

1542 if (->isLoopInvariant(RHS)) {

1543 if (->isLoopInvariant(LHS))

1544 continue;

1545

1547 }

1548

1549

1550 Value *LHSOp = nullptr;

1552 continue;

1553

1554 const unsigned InnerBitWidth = DL.getTypeSizeInBits(LHSOp->getType());

1555 const unsigned OuterBitWidth = DL.getTypeSizeInBits(RHS->getType());

1556 auto FullCR = ConstantRange::getFull(InnerBitWidth);

1557 FullCR = FullCR.zeroExtend(OuterBitWidth);

1559 if (FullCR.contains(RHSCR)) {

1560

1561

1562 ICmp->setPredicate(ICmp->getUnsignedPredicate());

1564

1565

1566 continue;

1567 }

1568 }

1569

1570

1571

1572 for (auto *ExitingBB : ExitingBlocks) {

1574 if (!BI)

1575 continue;

1577

1579 if (!ICmp || !ICmp->hasOneUse() || !ICmp->isUnsigned())

1580 continue;

1581

1582 bool Swapped = false;

1583 auto *LHS = ICmp->getOperand(0);

1584 auto *RHS = ICmp->getOperand(1);

1585 if (L->isLoopInvariant(LHS) == L->isLoopInvariant(RHS))

1586

1587 continue;

1588 if (L->isLoopInvariant(LHS)) {

1589

1590

1591 Swapped = true;

1593 }

1594 assert(->isLoopInvariant(LHS) && L->isLoopInvariant(RHS));

1595

1596

1597

1598

1599 Value *LHSOp = nullptr;

1601 continue;

1602

1603

1604

1605

1606

1607

1608

1610 continue;

1611

1612

1613

1614

1615

1616 auto doRotateTransform = [&]() {

1617 assert(ICmp->isUnsigned() && "must have proven unsigned already");

1619 Instruction::Trunc, RHS, LHSOp->getType(), "",

1620 L->getLoopPreheader()->getTerminator()->getIterator());

1621

1622

1624 ICmp->setOperand(Swapped ? 1 : 0, LHSOp);

1625 ICmp->setOperand(Swapped ? 0 : 1, NewRHS);

1626

1627 ICmp->setSameSign(false);

1630 };

1631

1632 const unsigned InnerBitWidth = DL.getTypeSizeInBits(LHSOp->getType());

1633 const unsigned OuterBitWidth = DL.getTypeSizeInBits(RHS->getType());

1634 auto FullCR = ConstantRange::getFull(InnerBitWidth);

1635 FullCR = FullCR.zeroExtend(OuterBitWidth);

1637 if (FullCR.contains(RHSCR)) {

1638 doRotateTransform();

1640

1641

1642

1643 continue;

1644 }

1645 }

1646

1648}

1649

1650bool IndVarSimplify::optimizeLoopExits(Loop *L, SCEVExpander &Rewriter) {

1651 SmallVector<BasicBlock*, 16> ExitingBlocks;

1652 L->getExitingBlocks(ExitingBlocks);

1653

1654

1655

1656 llvm::erase_if(ExitingBlocks, [&](BasicBlock *ExitingBB) {

1657

1658

1659

1661 return true;

1662

1663

1665 if (!BI)

1666 return true;

1667

1668

1669 if (!DT->dominates(ExitingBB, L->getLoopLatch()))

1670 return true;

1671

1673

1674

1675

1676 if (->contains(BI->getSuccessor(CI->isNullValue())))

1678 return true;

1679 }

1680

1681 return false;

1682 });

1683

1684 if (ExitingBlocks.empty())

1685 return false;

1686

1687

1690 return false;

1691

1692

1693

1694

1695 llvm::sort(ExitingBlocks, [&](BasicBlock *A, BasicBlock *B) {

1696

1697

1698 if (A == B) return false;

1700 return true;

1701 else {

1703 "expected total dominance order!");

1704 return false;

1705 }

1706 });

1707#ifdef ASSERT

1708 for (unsigned i = 1; i < ExitingBlocks.size(); i++) {

1709 assert(DT->dominates(ExitingBlocks[i-1], ExitingBlocks[i]));

1710 }

1711#endif

1712

1714 bool SkipLastIter = false;

1716 auto UpdateSkipLastIter = [&](const SCEV *MaxExitCount) {

1718 return;

1720 CurrMaxExit = MaxExitCount;

1721 else

1723

1724

1725 if (CurrMaxExit == MaxBECount)

1726 SkipLastIter = true;

1727 };

1728 SmallPtrSet<const SCEV *, 8> DominatingExactExitCounts;

1729 for (BasicBlock *ExitingBB : ExitingBlocks) {

1730 const SCEV *ExactExitCount = SE->getExitCount(L, ExitingBB);

1731 const SCEV *MaxExitCount = SE->getExitCount(

1732 L, ExitingBB, ScalarEvolution::ExitCountKind::SymbolicMaximum);

1734

1735

1737 auto OptimizeCond = [&](bool SkipLastIter) {

1739 MaxBECount, SkipLastIter,

1741 };

1742

1743

1744

1745

1746

1747

1748

1749

1750

1751

1752

1753

1754

1755

1756

1757

1758

1759 if (OptimizeCond(false))

1761 else if (SkipLastIter && OptimizeCond(true))

1763 UpdateSkipLastIter(MaxExitCount);

1764 continue;

1765 }

1766

1767 UpdateSkipLastIter(ExactExitCount);

1768

1769

1770

1771

1772

1773

1774 if (ExactExitCount->isZero()) {

1775 foldExit(L, ExitingBB, true, DeadInsts);

1778 continue;

1779 }

1780

1783 "Exit counts must be integers");

1784

1785 Type *WiderType =

1790

1791

1792

1794 ExactExitCount)) {

1795 foldExit(L, ExitingBB, false, DeadInsts);

1797 continue;

1798 }

1799

1800

1801

1802

1803

1804 if (!DominatingExactExitCounts.insert(ExactExitCount).second) {

1805 foldExit(L, ExitingBB, false, DeadInsts);

1807 continue;

1808 }

1809

1810

1811

1812

1813

1814

1815

1816 }

1818}

1819

1822

1823

1824

1825

1826

1827

1828

1829

1831 if (CB->onlyAccessesInaccessibleMemory())

1832 return true;

1833 }

1835 });

1836}

1837

1838bool IndVarSimplify::predicateLoopExits(Loop *L, SCEVExpander &Rewriter) {

1839 SmallVector<BasicBlock*, 16> ExitingBlocks;

1840 L->getExitingBlocks(ExitingBlocks);

1841

1842

1843

1844

1845

1846

1847

1848

1849

1850

1852 return false;

1853

1854

1855

1856

1859 return false;

1860

1863

1864 auto BadExit = [&](BasicBlock *ExitingBB) {

1865

1866

1867

1869 return true;

1870

1871

1873 if (!BI)

1874 return true;

1875

1876

1878 return true;

1879

1880

1881

1882

1885 if (!ExitBlock->phis().empty())

1886 return true;

1887

1888 const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);

1890 Rewriter .isSafeToExpand(ExitCount))

1891 return true;

1892

1894 "Exit count must be loop invariant");

1896 return false;

1897 };

1898

1899

1900

1902 for (BasicBlock *ExitingBB : ExitingBlocks)

1903 if (!DT->dominates(ExitingBB, Latch))

1904 return false;

1905

1906

1907

1908

1909

1910

1911

1912

1913 llvm::sort(ExitingBlocks, [&](BasicBlock *A, BasicBlock *B) {

1914

1915

1916 if (A == B)

1917 return false;

1919 return true;

1921 return false;

1923 });

1924

1925

1926

1927 for (unsigned i = 1; i < ExitingBlocks.size(); i++)

1928 assert(DT->dominates(ExitingBlocks[i - 1], ExitingBlocks[i]) &&

1929 "Not sorted by dominance");

1930

1931

1932

1933 for (unsigned i = 0, e = ExitingBlocks.size(); i < e; i++)

1934 if (BadExit(ExitingBlocks[i])) {

1935 ExitingBlocks.resize(i);

1936 break;

1937 }

1938

1939 if (ExitingBlocks.empty())

1940 return false;

1941

1942

1943

1944

1945

1946

1947

1948

1949

1950 bool HasThreadLocalSideEffects = false;

1951 for (BasicBlock *BB : L->blocks())

1952 for (auto &I : *BB) {

1953

1954 if (I.mayHaveSideEffects()) {

1956 return false;

1957 HasThreadLocalSideEffects = true;

1959

1960

1961

1962

1963 if (->isSimple())

1964 return false;

1965 } else {

1966 return false;

1967 }

1968 }

1969

1970

1971

1972 if (I.getType()->isTokenTy()) {

1973 for (User *U : I.users()) {

1975 if (UserInst && ->contains(UserInst)) {

1976 return false;

1977 }

1978 }

1979 }

1980 }

1981

1983

1984

1985

1986

1987

1988

1989

1990

1991

1992

1993 Rewriter.setInsertPoint(L->getLoopPreheader()->getTerminator());

1994 IRBuilder<> B(L->getLoopPreheader()->getTerminator());

1995 Value *ExactBTCV = nullptr;

1996 for (BasicBlock *ExitingBB : ExitingBlocks) {

1997 const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);

1998

2000 if (HasThreadLocalSideEffects) {

2001 const BasicBlock *Unreachable = nullptr;

2002 for (const BasicBlock *Succ : BI->successors()) {

2004 Unreachable = Succ;

2005 }

2006

2007

2008

2009

2012 }

2014 if (ExitCount == ExactBTC) {

2016 B.getFalse() : B.getTrue();

2017 } else {

2019 if (!ExactBTCV)

2020 ExactBTCV = Rewriter.expandCodeFor(ExactBTC);

2024 ECV = B.CreateZExt(ECV, WiderTy);

2025 RHS = B.CreateZExt(RHS, WiderTy);

2026 }

2028 ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ;

2029 NewCond = B.CreateICmp(Pred, ECV, RHS);

2030 }

2036 RunUnswitching = true;

2037 }

2038

2040}

2041

2042

2043

2044

2045

2046bool IndVarSimplify::run(Loop *L) {

2047

2048 assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&

2049 "LCSSA required to run indvars!");

2050

2051

2052

2053

2054

2055

2056

2057

2058

2059

2060 if (->isLoopSimplifyForm())

2061 return false;

2062

2064

2065

2066 Changed |= rewriteNonIntegerIVs(L);

2067

2068

2069 SCEVExpander Rewriter(*SE, DL, "indvars");

2070#if LLVM_ENABLE_ABI_BREAKING_CHECKS

2072#endif

2073

2074

2075

2076

2077

2078

2079

2080 Rewriter.disableCanonicalMode();

2082

2083

2084

2085

2086

2090 NumReplaced += Rewrites;

2092 }

2093 }

2094

2095

2096 NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts, TTI);

2097

2098

2099

2100 Changed |= canonicalizeExitCondition(L);

2101

2102

2103 if (optimizeLoopExits(L, Rewriter)) {

2105

2106

2107

2109 }

2110

2111

2112

2113 if (predicateLoopExits(L, Rewriter)) {

2115

2117 }

2118

2119

2120

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

2123

2124 SmallVector<BasicBlock*, 16> ExitingBlocks;

2125 L->getExitingBlocks(ExitingBlocks);

2126 for (BasicBlock *ExitingBB : ExitingBlocks) {

2127

2129 continue;

2130

2131

2132

2133

2135 continue;

2136

2138 continue;

2139

2140 const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);

2142 continue;

2143

2144

2145

2146

2147

2148 if (ExitCount->isZero())

2149 continue;

2150

2151 PHINode *IndVar = FindLoopCounter(L, ExitingBB, ExitCount, SE, DT);

2152 if (!IndVar)

2153 continue;

2154

2155

2156

2159 continue;

2160

2161 if ( Rewriter .isSafeToExpand(ExitCount))

2162 continue;

2163

2164 Changed |= linearFunctionTestReplace(L, ExitingBB,

2165 ExitCount, IndVar,

2167 }

2168 }

2169

2170

2171

2173

2174

2175

2176 while (!DeadInsts.empty()) {

2178

2184 }

2185

2186

2187

2188

2189

2190 Changed |= sinkUnusedInvariants(L);

2191

2192

2193

2194

2195 Changed |= rewriteFirstIterationLoopExitValues(L);

2196

2197

2199

2200

2201 assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&

2202 "Indvars did not preserve LCSSA!");

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

2205

2207}

2208

2212 Function *F = L.getHeader()->getParent();

2214

2215 IndVarSimplify IVS(&AR.LI, &AR.SE, &AR.DT, DL, &AR.TLI, &AR.TTI, AR.MSSA,

2217 if (!IVS.run(&L))

2219

2222 if (IVS.runUnswitching()) {

2225 }

2226

2227 if (AR.MSSA)

2229 return PA;

2230}

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

This file declares a class to represent arbitrary precision floating point values and provide a varie...

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

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

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

#define clEnumValN(ENUMVAL, FLAGNAME, DESC)

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

This header defines various interfaces for pass management in LLVM.

This defines the Use class.

static Value * genLoopLimit(PHINode *IndVar, BasicBlock *ExitingBB, const SCEV *ExitCount, bool UsePostInc, Loop *L, SCEVExpander &Rewriter, ScalarEvolution *SE)

Insert an IR expression which computes the value held by the IV IndVar (which must be an loop counter...

Definition IndVarSimplify.cpp:1019

static std::optional< FloatingPointIV > maybeFloatingPointRecurrence(Loop *L, PHINode *PN)

Analyze a PN to determine whether it represents a simple floating-point induction variable,...

Definition IndVarSimplify.cpp:265

static void replaceExitCond(BranchInst *BI, Value *NewCond, SmallVectorImpl< WeakTrackingVH > &DeadInsts)

Definition IndVarSimplify.cpp:1269

static cl::opt< bool > DisableLFTR("disable-lftr", cl::Hidden, cl::init(false), cl::desc("Disable Linear Function Test Replace optimization"))

static bool isLoopExitTestBasedOn(Value *V, BasicBlock *ExitingBB)

Whether the current loop exit test is based on this value.

Definition IndVarSimplify.cpp:809

static cl::opt< ReplaceExitVal > ReplaceExitValue("replexitval", cl::Hidden, cl::init(OnlyCheapRepl), cl::desc("Choose the strategy to replace exit value in IndVarSimplify"), cl::values(clEnumValN(NeverRepl, "never", "never replace exit value"), clEnumValN(OnlyCheapRepl, "cheap", "only replace exit value when the cost is cheap"), clEnumValN(UnusedIndVarInLoop, "unusedindvarinloop", "only replace exit value when it is an unused " "induction variable in the loop and has cheap replacement cost"), clEnumValN(NoHardUse, "noharduse", "only replace exit values when loop def likely dead"), clEnumValN(AlwaysRepl, "always", "always replace exit value whenever possible")))

static void visitIVCast(CastInst *Cast, WideIVInfo &WI, ScalarEvolution *SE, const TargetTransformInfo *TTI)

Update information about the induction variable that is extended by this sign or zero extend operatio...

Definition IndVarSimplify.cpp:620

static bool isRepresentableAsExactInteger(const APFloat &FPVal, int64_t IntVal)

Ensure we stay within the bounds of fp values that can be represented as integers without gaps,...

Definition IndVarSimplify.cpp:204

static void replaceLoopPHINodesWithPreheaderValues(LoopInfo *LI, Loop *L, SmallVectorImpl< WeakTrackingVH > &DeadInsts, ScalarEvolution &SE)

Definition IndVarSimplify.cpp:1295

static bool needsLFTR(Loop *L, BasicBlock *ExitingBB)

linearFunctionTestReplace policy.

Definition IndVarSimplify.cpp:822

static bool optimizeLoopExitWithUnknownExitCount(const Loop *L, BranchInst *BI, BasicBlock *ExitingBB, const SCEV *MaxIter, bool SkipLastIter, ScalarEvolution *SE, SCEVExpander &Rewriter, SmallVectorImpl< WeakTrackingVH > &DeadInsts)

Definition IndVarSimplify.cpp:1410

static Value * createInvariantCond(const Loop *L, BasicBlock *ExitingBB, const ScalarEvolution::LoopInvariantPredicate &LIP, SCEVExpander &Rewriter)

Definition IndVarSimplify.cpp:1334

static bool isLoopCounter(PHINode *Phi, Loop *L, ScalarEvolution *SE)

Return true if the given phi is a "counter" in L.

Definition IndVarSimplify.cpp:914

static std::optional< Value * > createReplacement(ICmpInst *ICmp, const Loop *L, BasicBlock *ExitingBB, const SCEV *MaxIter, bool Inverted, bool SkipLastIter, ScalarEvolution *SE, SCEVExpander &Rewriter)

Definition IndVarSimplify.cpp:1353

static bool hasConcreteDefImpl(Value *V, SmallPtrSetImpl< Value * > &Visited, unsigned Depth)

Recursive helper for hasConcreteDef().

Definition IndVarSimplify.cpp:872

static bool hasConcreteDef(Value *V)

Return true if the given value is concrete.

Definition IndVarSimplify.cpp:905

static void foldExit(const Loop *L, BasicBlock *ExitingBB, bool IsTaken, SmallVectorImpl< WeakTrackingVH > &DeadInsts)

Definition IndVarSimplify.cpp:1288

static PHINode * getLoopPhiForCounter(Value *IncV, Loop *L)

Given an Value which is hoped to be part of an add recurance in the given loop, return the associated...

Definition IndVarSimplify.cpp:771

static Constant * createFoldedExitCond(const Loop *L, BasicBlock *ExitingBB, bool IsTaken)

Definition IndVarSimplify.cpp:1279

static std::optional< IntegerIV > tryConvertToIntegerIV(const FloatingPointIV &FPIV)

Ensure that the floating-point IV can be converted to a semantics-preserving signed 32-bit integer IV...

Definition IndVarSimplify.cpp:333

static cl::opt< bool > LoopPredicationTraps("indvars-predicate-loop-traps", cl::Hidden, cl::init(true), cl::desc("Predicate conditions that trap in loops with only local writes"))

static cl::opt< bool > UsePostIncrementRanges("indvars-post-increment-ranges", cl::Hidden, cl::desc("Use post increment control-dependent ranges in IndVarSimplify"), cl::init(true))

static void canonicalizeToIntegerIV(Loop *L, PHINode *PN, const FloatingPointIV &FPIV, const IntegerIV &IIV, const TargetLibraryInfo *TLI, std::unique_ptr< MemorySSAUpdater > &MSSAU)

Rewrite the floating-point IV as an integer IV.

Definition IndVarSimplify.cpp:425

static PHINode * FindLoopCounter(Loop *L, BasicBlock *ExitingBB, const SCEV *BECount, ScalarEvolution *SE, DominatorTree *DT)

Search the loop header for a loop counter (anadd rec w/step of one) suitable for use by LFTR.

Definition IndVarSimplify.cpp:939

static cl::opt< bool > AllowIVWidening("indvars-widen-indvars", cl::Hidden, cl::init(true), cl::desc("Allow widening of indvars to eliminate s/zext"))

static bool crashingBBWithoutEffect(const BasicBlock &BB)

Definition IndVarSimplify.cpp:1820

static CmpInst::Predicate getIntegerPredicate(CmpInst::Predicate FPPred)

Definition IndVarSimplify.cpp:235

static bool ConvertToSInt(const APFloat &APF, int64_t &IntVal)

Convert APF to an integer, if possible.

Definition IndVarSimplify.cpp:189

static cl::opt< bool > LoopPredication("indvars-predicate-loops", cl::Hidden, cl::init(true), cl::desc("Predicate conditions in read only loops"))

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

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

const SmallVectorImpl< MachineOperand > & Cond

This file defines the SmallPtrSet class.

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.

Virtual Register Rewriter

static const uint32_t IV[8]

static constexpr roundingMode rmTowardZero

static LLVM_ABI unsigned int semanticsPrecision(const fltSemantics &)

static LLVM_ABI bool isIEEELikeFP(const fltSemantics &)

const fltSemantics & getSemantics() const

opStatus convertToInteger(MutableArrayRef< integerPart > Input, unsigned int Width, bool IsSigned, roundingMode RM, bool *IsExact) const

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

LLVM Basic Block Representation.

iterator_range< const_phi_iterator > phis() const

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

LLVM_ABI const_iterator getFirstInsertionPt() const

Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...

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.

iterator_range< succ_op_iterator > successors()

void setCondition(Value *V)

bool isConditional() const

BasicBlock * getSuccessor(unsigned i) const

Value * getCondition() const

Represents analyses that only rely on functions' control flow.

This is the base class for all instructions that perform data casts.

Instruction::CastOps getOpcode() const

Return the opcode of this CastInst.

static LLVM_ABI CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)

Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

@ FCMP_OEQ

0 0 0 1 True if ordered and equal

@ ICMP_SLT

signed less than

@ ICMP_SLE

signed less or equal

@ FCMP_OLT

0 1 0 0 True if ordered and less than

@ FCMP_ULE

1 1 0 1 True if unordered, less than, or equal

@ FCMP_OGT

0 0 1 0 True if ordered and greater than

@ FCMP_OGE

0 0 1 1 True if ordered and greater than or equal

@ ICMP_SGT

signed greater than

@ FCMP_ULT

1 1 0 0 True if unordered or less than

@ FCMP_ONE

0 1 1 0 True if ordered and operands are unequal

@ FCMP_UEQ

1 0 0 1 True if unordered or equal

@ ICMP_ULT

unsigned less than

@ FCMP_UGT

1 0 1 0 True if unordered or greater than

@ FCMP_OLE

0 1 0 1 True if ordered and less than or equal

@ ICMP_SGE

signed greater or equal

@ FCMP_UNE

1 1 1 0 True if unordered or not equal

@ ICMP_ULE

unsigned less or equal

@ FCMP_UGE

1 0 1 1 True if unordered, greater than, or equal

Predicate getInversePredicate() const

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

static LLVM_ABI StringRef getPredicateName(Predicate P)

Predicate getPredicate() const

Return the predicate for this instruction.

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

static ConstantInt * getSigned(IntegerType *Ty, int64_t V)

Return a ConstantInt with the specified value for the specified type.

This is an important base class in LLVM.

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

bool isLegalInteger(uint64_t Width) const

Returns true if the specified type is known to be a native integer type supported by the CPU.

static DebugLoc getDropped()

bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const

properlyDominates - Returns true iff A dominates B and A != B.

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

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.

This instruction compares its operands according to the predicate given to the constructor.

CmpPredicate getCmpPredicate() const

CmpPredicate getInverseCmpPredicate() const

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

PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)

Definition IndVarSimplify.cpp:2209

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

Instruction * user_back()

Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...

unsigned getOpcode() const

Returns a member of one of the enums like Instruction::Add.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

LLVM_ABI const DataLayout & getDataLayout() const

Get the data layout of the module this instruction belongs to.

Class to represent integer types.

This class provides an interface for updating the loop pass manager based on mutations to the loop ne...

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

bool replacementPreservesLCSSAForm(Instruction *From, Value *To)

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

Represents a single loop in the control flow graph.

An analysis that produces MemorySSA for a function.

Encapsulates MemorySSA, including all data associated with memory accesses.

MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...

void addIncoming(Value *V, BasicBlock *BB)

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

void setIncomingValue(unsigned i, Value *V)

Value * getIncomingValueForBlock(const BasicBlock *BB) const

BasicBlock * getIncomingBlock(unsigned i) const

Return incoming basic block number i.

Value * getIncomingValue(unsigned i) const

Return incoming value number x.

static unsigned getIncomingValueNumForOperand(unsigned i)

unsigned getNumIncomingValues() const

Return the number of incoming edges.

static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...

static LLVM_ABI PoisonValue * get(Type *T)

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

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

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

const SCEV * getStart() const

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.

LLVM_ABI const SCEVAddRecExpr * getPostIncExpr(ScalarEvolution &SE) const

Return an expression representing the value of this expression one iteration of the loop ahead.

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

bool hasNoUnsignedWrap() const

bool hasNoSignedWrap() const

This class represents an analyzed expression in the program.

LLVM_ABI bool isOne() const

Return true if the expression is a constant one.

LLVM_ABI bool isZero() const

Return true if the expression is a constant zero.

LLVM_ABI Type * getType() const

Return the LLVM type of this SCEV expression.

This class represents a cast from signed integer to floating point.

The main scalar evolution driver.

LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)

If the result of the predicate LHS Pred RHS is loop invariant with respect to L at given Context duri...

LLVM_ABI Type * getWiderType(Type *Ty1, Type *Ty2) const

LLVM_ABI bool isLoopEntryGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)

Test whether entry to the loop is protected by a conditional between LHS and RHS.

LLVM_ABI const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)

Return a SCEV expression for the specified value at the specified scope in the program.

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 ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit, bool AllowPredicates=false)

Compute the number of times the backedge of the specified loop will execute if its exit condition wer...

LLVM_ABI uint64_t getTypeSizeInBits(Type *Ty) const

Return the size in bits of the specified type, for which isSCEVable must return true.

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 std::optional< bool > evaluatePredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)

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

LLVM_ABI void forgetLoop(const Loop *L)

This method should be called by the client when it has changed a loop in a way that may effect Scalar...

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 const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)

LLVM_ABI bool isSCEVable(Type *Ty) const

Test if values of the given type are analyzable within the SCEV framework.

LLVM_ABI Type * getEffectiveSCEVType(Type *Ty) const

Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...

ConstantRange getUnsignedRange(const SCEV *S)

Determine the unsigned range for a particular SCEV.

LLVM_ABI void forgetTopmostLoop(const Loop *L)

LLVM_ABI void forgetValue(Value *V)

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

LLVM_ABI const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)

LLVM_ABI const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)

Return LHS-RHS.

const SCEV * getMinusOne(Type *Ty)

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

LLVM_ABI const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)

Return a SCEV corresponding to a conversion of the input value to the specified type.

LLVM_ABI const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)

Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...

LLVM_ABI const SCEV * getCouldNotCompute()

LLVM_ABI const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)

Return the number of times the backedge executes before the given exit would be taken; if not exactly...

LLVM_ABI const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)

@ SymbolicMaximum

An expression which provides an upper bound on the exact trip count.

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

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

LLVM_ABI bool isKnownPredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)

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

const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)

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

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

bool erase(PtrType Ptr)

Remove pointer from the set.

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

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

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

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

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.

Provides information about what library functions are available for the current target.

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

The instances of the Type class are immutable: once they are created, they are never changed.

static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)

bool isPointerTy() const

True if this is an instance of PointerType.

bool isIntegerTy() const

True if this is an instance of IntegerType.

Value * getOperand(unsigned i) const

unsigned getNumOperands() const

LLVM Value Representation.

Type * getType() const

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

bool hasOneUse() const

Return true if there is exactly one use of this value.

LLVM_ABI void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

iterator_range< user_iterator > users()

LLVM_ABI LLVMContext & getContext() const

All values hold a context through their type.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

LLVM_ABI void takeName(Value *V)

Transfer the name from V to this value.

Value handle that is nullable, but tries to track the Value.

const ParentTy * getParent() const

self_iterator getIterator()

This provides a very simple, boring adaptor for a begin and end iterator into a range type.

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

@ C

The default llvm calling convention, compatible with C.

@ BasicBlock

Various leaf nodes.

LLVM_ABI Function * getDeclarationIfExists(const Module *M, ID id)

Look up the Function declaration of the intrinsic id in the Module M and return it if it exists.

auto m_LogicalOr()

Matches L || R where L and R are arbitrary values.

CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)

Matches ZExt.

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

auto m_LogicalAnd()

Matches L && R where L and R are arbitrary values.

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

ValuesClass values(OptsTy... Options)

Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...

initializer< Ty > init(const Ty &Val)

PointerTypeMap run(const Module &M)

Compute the PointerTypeMap for the module M.

@ User

could "use" a pointer

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI bool mustExecuteUBIfPoisonOnPathTo(Instruction *Root, Instruction *OnPathTo, DominatorTree *DT)

Return true if undefined behavior would provable be executed on the path to OnPathTo if Root produced...

FunctionAddr VTableAddr Value

bool all_of(R &&range, UnaryPredicate P)

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

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.

constexpr bool isInt(int64_t x)

Checks if an integer fits into the given bit width.

decltype(auto) dyn_cast(const From &Val)

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

FunctionAddr VTableAddr uintptr_t uintptr_t Int32Ty

PHINode * createWideIV(const WideIVInfo &WI, LoopInfo *LI, ScalarEvolution *SE, SCEVExpander &Rewriter, DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, unsigned &NumElimExt, unsigned &NumWidened, bool HasGuards, bool UsePostIncrementRanges)

Widen Induction Variables - Extend the width of an IV to cover its widest uses.

constexpr bool isUIntN(unsigned N, uint64_t x)

Checks if an unsigned integer fits into the given (dynamic) bit width.

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.

AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager

The loop analysis manager.

auto dyn_cast_or_null(const Y &Val)

LLVM_ABI bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)

Examine each PHI in the given block and delete it if it is dead.

auto reverse(ContainerTy &&C)

void sort(IteratorTy Start, IteratorTy End)

LLVM_ABI raw_ostream & dbgs()

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

LLVM_ABI cl::opt< unsigned > SCEVCheapExpansionBudget

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

bool isa(const From &Val)

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

std::pair< bool, bool > simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT, LoopInfo *LI, const TargetTransformInfo *TTI, SmallVectorImpl< WeakTrackingVH > &Dead, SCEVExpander &Rewriter, IVVisitor *V=nullptr)

simplifyUsersOfIV - Simplify instructions that use this induction variable by using ScalarEvolution t...

RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)

IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >

LLVM_ABI bool VerifyMemorySSA

Enables verification of MemorySSA.

@ UMin

Unsigned integer min implemented in terms of select(cmp()).

DWARFExpression::Operation Op

constexpr U AbsoluteValue(T X)

Return the absolute value of a signed integer, converted to the corresponding unsigned integer type.

OutputIt move(R &&Range, OutputIt Out)

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

decltype(auto) cast(const From &Val)

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

LLVM_ABI PreservedAnalyses getLoopPassPreservedAnalyses()

Returns the minimum set of Analyses that all loop passes must preserve.

auto find_if(R &&Range, UnaryPredicate P)

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

void erase_if(Container &C, UnaryPredicate P)

Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...

LLVM_ABI bool isAlmostDeadIV(PHINode *IV, BasicBlock *LatchBlock, Value *Cond)

Return true if the induction variable IV in a Loop whose latch is LatchBlock would become dead if the...

LLVM_ABI int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI, ScalarEvolution *SE, const TargetTransformInfo *TTI, SCEVExpander &Rewriter, DominatorTree *DT, ReplaceExitVal ReplaceExitValue, SmallVector< WeakTrackingVH, 16 > &DeadInsts)

If the final value of any expressions that are recurrent in the loop can be computed,...

iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)

LLVM_ABI bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)

If the specified value is an effectively dead PHI node, due to being a def-use chain of single-use no...

Implement std::hash so that hash_code can be used in STL containers.

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

Implement std::swap in terms of BitVector swap.

Represents a floating-point induction variable pattern that may be convertible to integer form.

Definition IndVarSimplify.cpp:214

FloatingPointIV(APFloat Init, APFloat Incr, APFloat Exit, FCmpInst *Compare, BinaryOperator *Add)

Definition IndVarSimplify.cpp:221

APFloat InitValue

Definition IndVarSimplify.cpp:215

FCmpInst * Compare

Definition IndVarSimplify.cpp:218

APFloat ExitValue

Definition IndVarSimplify.cpp:217

BinaryOperator * Add

Definition IndVarSimplify.cpp:219

APFloat IncrValue

Definition IndVarSimplify.cpp:216

Represents the integer values for a converted IV.

Definition IndVarSimplify.cpp:228

int64_t InitValue

Definition IndVarSimplify.cpp:229

int64_t ExitValue

Definition IndVarSimplify.cpp:231

int64_t IncrValue

Definition IndVarSimplify.cpp:230

CmpInst::Predicate NewPred

Definition IndVarSimplify.cpp:232

The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...

TargetTransformInfo & TTI

Collect information about induction variables that are used by sign/zero extend operations.