SimplifyIndVar.cpp Source File (original) (raw)

31using namespace llvm;

34#define DEBUG_TYPE "indvars"

36 STATISTIC(NumElimIdentity, "Number of IV identities eliminated");

37 STATISTIC(NumElimOperand, "Number of IV operands folded into a use");

38 STATISTIC(NumFoldedUser, "Number of IV users folded into a constant");

39 STATISTIC(NumElimRem , "Number of IV remainder operations eliminated");

41 NumSimplifiedSDiv,

42 "Number of IV signed division operations converted to unsigned division");

44 NumSimplifiedSRem,

45 "Number of IV signed remainder operations converted to unsigned remainder");

46 STATISTIC(NumElimCmp, "Number of IV comparisons eliminated");

47 STATISTIC(NumInvariantCmp, "Number of IV comparisons made loop invariant");

48 STATISTIC(NumSameSign, "Number of IV comparisons with new samesign flags");

50namespace {

55 class SimplifyIndvar {

65 bool RunUnswitching = false;

67 public:

72 : L(Loop), LI(LI), SE(SE), DT(DT), TTI(TTI), Rewriter(Rewriter),

73 DeadInsts(Dead) {

74 assert(LI && "IV simplification requires LoopInfo");

75 }

77 bool hasChanged() const { return Changed; }

78 bool runUnswitching() const { return RunUnswitching; }

83 void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);

85 void pushIVUsers(Instruction *Def,

86 SmallPtrSet<Instruction *, 16> &Simplified,

87 SmallVectorImpl<std::pair<Instruction *, Instruction *>>

88 &SimpleIVUsers);

90 Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);

92 bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);

93 bool replaceIVUserWithLoopInvariant(Instruction *UseInst);

94 bool replaceFloatIVWithIntegerIV(Instruction *UseInst);

96 bool eliminateOverflowIntrinsic(WithOverflowInst *WO);

97 bool eliminateSaturatingIntrinsic(SaturatingInst *SI);

98 bool eliminateTrunc(TruncInst *TI);

99 bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);

100 bool makeIVComparisonInvariant(ICmpInst *ICmp, Instruction *IVOperand);

101 void eliminateIVComparison(ICmpInst *ICmp, Instruction *IVOperand);

102 void simplifyIVRemainder(BinaryOperator *Rem, Instruction *IVOperand,

103 bool IsSigned);

104 void replaceRemWithNumerator(BinaryOperator *Rem);

105 void replaceRemWithNumeratorOrZero(BinaryOperator *Rem);

106 void replaceSRemWithURem(BinaryOperator *Rem);

107 bool eliminateSDiv(BinaryOperator *SDiv);

108 bool strengthenBinaryOp(BinaryOperator *BO, Instruction *IVOperand);

109 bool strengthenOverflowingOperation(BinaryOperator *OBO,

110 Instruction *IVOperand);

111 bool strengthenRightShift(BinaryOperator *BO, Instruction *IVOperand);

112 };

113}

114

115

116

117

121 for (auto *Insn : Instructions)

122 CommonDom =

124 assert(CommonDom && "Common dominator not found?");

125 return CommonDom;

126}

127

128

129

130

131

132

133

134

135

137 Value *IVSrc = nullptr;

138 const unsigned OperIdx = 0;

139 const SCEV *FoldedExpr = nullptr;

140 bool MustDropExactFlag = false;

142 default:

143 return nullptr;

144 case Instruction::UDiv:

145 case Instruction::LShr:

146

147

148 if (IVOperand != UseInst->getOperand(OperIdx) ||

150 return nullptr;

151

152

153

156 return nullptr;

157

159

161

163 if (UseInst->getOpcode() == Instruction::LShr) {

164

167 return nullptr;

168

169 D = ConstantInt::get(UseInst->getContext(),

171 }

172 const SCEV *LHS = SE->getSCEV(IVSrc);

175

176

178 MustDropExactFlag = true;

179 }

180

182 return nullptr;

183

184

185 if (SE->getSCEV(UseInst) != FoldedExpr)

186 return nullptr;

187

188 LLVM_DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand

189 << " -> " << *UseInst << '\n');

190

192 assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");

193

194 if (MustDropExactFlag)

196

197 ++NumElimOperand;

200 DeadInsts.emplace_back(IVOperand);

201 return IVSrc;

202}

203

204bool SimplifyIndvar::makeIVComparisonInvariant(ICmpInst *ICmp,

205 Instruction *IVOperand) {

207 if (!Preheader)

208 return false;

209 unsigned IVOperIdx = 0;

211 if (IVOperand != ICmp->getOperand(0)) {

212

213 assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");

214 IVOperIdx = 1;

216 }

217

218

219

224 if (!LIP)

225 return false;

226 ICmpInst::Predicate InvariantPredicate = LIP->Pred;

227 const SCEV *InvariantLHS = LIP->LHS;

228 const SCEV *InvariantRHS = LIP->RHS;

229

230

231 auto *PHTerm = Preheader->getTerminator();

232 if (Rewriter.isHighCostExpansion({InvariantLHS, InvariantRHS}, L,

234 Rewriter .isSafeToExpandAt(InvariantLHS, PHTerm) ||

235 Rewriter .isSafeToExpandAt(InvariantRHS, PHTerm))

236 return false;

237 auto *NewLHS =

238 Rewriter.expandCodeFor(InvariantLHS, IVOperand->getType(), PHTerm);

239 auto *NewRHS =

240 Rewriter.expandCodeFor(InvariantRHS, IVOperand->getType(), PHTerm);

241 LLVM_DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');

245 RunUnswitching = true;

246 return true;

247}

248

249

250

251void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp,

252 Instruction *IVOperand) {

253 unsigned IVOperIdx = 0;

255 ICmpInst::Predicate OriginalPred = Pred;

256 if (IVOperand != ICmp->getOperand(0)) {

257

258 assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");

259 IVOperIdx = 1;

261 }

262

263

264

268

269

270

271 SmallVector<Instruction *, 4> Users;

272 for (auto *U : ICmp->users())

278 DeadInsts.emplace_back(ICmp);

279 LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');

280 ++NumElimCmp;

282 return;

283 }

284

285 if (makeIVComparisonInvariant(ICmp, IVOperand)) {

286 ++NumInvariantCmp;

288 return;

289 }

290

291 if ((ICmpInst::isSigned(OriginalPred) ||

292 (ICmpInst::isUnsigned(OriginalPred) && !ICmp->hasSameSign())) &&

294

295

296

297

298 assert(ICmp->getPredicate() == OriginalPred && "Predicate changed?");

299 LLVM_DEBUG(dbgs() << "INDVARS: Marking comparison samesign: " << *ICmp

300 << '\n');

303 NumSameSign++;

305 return;

306 }

307}

308

309bool SimplifyIndvar::eliminateSDiv(BinaryOperator *SDiv) {

310

313

314

318

319

324 UDiv->setIsExact(SDiv->isExact());

327 LLVM_DEBUG(dbgs() << "INDVARS: Simplified sdiv: " << *SDiv << '\n');

328 ++NumSimplifiedSDiv;

330 DeadInsts.push_back(SDiv);

331 return true;

332 }

333

334 return false;

335}

336

337

338void SimplifyIndvar::replaceSRemWithURem(BinaryOperator *Rem) {

344 LLVM_DEBUG(dbgs() << "INDVARS: Simplified srem: " << *Rem << '\n');

345 ++NumSimplifiedSRem;

347 DeadInsts.emplace_back(Rem);

348}

349

350

351void SimplifyIndvar::replaceRemWithNumerator(BinaryOperator *Rem) {

353 LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');

354 ++NumElimRem;

356 DeadInsts.emplace_back(Rem);

357}

358

359

360void SimplifyIndvar::replaceRemWithNumeratorOrZero(BinaryOperator *Rem) {

363 ICmpInst *ICmp = new ICmpInst(Rem->getIterator(), ICmpInst::ICMP_EQ, N, D);

365 SelectInst *Sel =

369 LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');

370 ++NumElimRem;

372 DeadInsts.emplace_back(Rem);

373}

374

375

376

377void SimplifyIndvar::simplifyIVRemainder(BinaryOperator *Rem,

378 Instruction *IVOperand,

379 bool IsSigned) {

382

383

384

385 bool UsedAsNumerator = IVOperand == NValue;

386 if (!UsedAsNumerator && !IsSigned)

387 return;

388

389 const SCEV *N = SE->getSCEV(NValue);

390

391

394

396

397

398 if (!IsNumeratorNonNegative)

399 return;

400

401 const SCEV *D = SE->getSCEV(DValue);

403

404 if (UsedAsNumerator) {

405 auto LT = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;

407 replaceRemWithNumerator(Rem);

408 return;

409 }

410

414 replaceRemWithNumeratorOrZero(Rem);

415 return;

416 }

417 }

418

419

420

422 return;

423

424 replaceSRemWithURem(Rem);

425}

426

427bool SimplifyIndvar::eliminateOverflowIntrinsic(WithOverflowInst *WO) {

431 return false;

432

433

434

435

438

441 else

443

445

446 for (auto *U : WO->users()) {

448 if (EVI->getIndices()[0] == 1)

450 else {

451 assert(EVI->getIndices()[0] == 0 && "Only two possibilities!");

452 EVI->replaceAllUsesWith(NewResult);

453 NewResult->setDebugLoc(EVI->getDebugLoc());

454 }

456 }

457 }

458

459 for (auto *EVI : ToDelete)

460 EVI->eraseFromParent();

461

464

466 return true;

467}

468

469bool SimplifyIndvar::eliminateSaturatingIntrinsic(SaturatingInst *SI) {

473 return false;

474

476 SI->getBinaryOp(), SI->getLHS(), SI->getRHS(), SI->getName(), SI->getIterator());

477 if (SI->isSigned())

479 else

481

482 SI->replaceAllUsesWith(BO);

484 DeadInsts.emplace_back(SI);

486 return true;

487}

488

489bool SimplifyIndvar::eliminateTrunc(TruncInst *TI) {

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

507 Type *IVTy = IV->getType();

508 const SCEV *IVSCEV = SE->getSCEV(IV);

509 const SCEV *TISCEV = SE->getSCEV(TI);

510

511

512

513 bool DoesSExtCollapse = false;

514 bool DoesZExtCollapse = false;

516 DoesSExtCollapse = true;

518 DoesZExtCollapse = true;

519

520

521

522 if (!DoesSExtCollapse && !DoesZExtCollapse)

523 return false;

524

525

526

528 for (auto *U : TI->users()) {

529

532 continue;

534 if (!ICI) return false;

535 assert(L->contains(ICI->getParent()) && "LCSSA form broken?");

538 return false;

539

540 if (ICI->isSigned() && !DoesSExtCollapse)

541 return false;

542 if (ICI->isUnsigned() && !DoesZExtCollapse)

543 return false;

544

546 }

547

548 auto CanUseZExt = [&](ICmpInst *ICI) {

549

551 return true;

552

553 if (!DoesZExtCollapse)

554 return false;

555

557 return true;

558

559

560

561

565 };

566

567 for (auto *ICI : ICmpUsers) {

568 bool IsSwapped = L->isLoopInvariant(ICI->getOperand(0));

571 Value *Ext = nullptr;

572

573

574

575

576

577

578 ICmpInst::Predicate Pred = ICI->getPredicate();

579 if (IsSwapped) Pred = ICmpInst::getSwappedPredicate(Pred);

580 if (CanUseZExt(ICI)) {

581 assert(DoesZExtCollapse && "Unprofitable zext?");

582 Ext = Builder.CreateZExt(Op1, IVTy, "zext");

584 } else {

585 assert(DoesSExtCollapse && "Unprofitable sext?");

586 Ext = Builder.CreateSExt(Op1, IVTy, "sext");

588 }

590 L->makeLoopInvariant(Ext, Changed);

592 auto *NewCmp = Builder.CreateICmp(Pred, IV, Ext);

594 DeadInsts.emplace_back(ICI);

595 }

596

597

599 DeadInsts.emplace_back(TI);

600 return true;

601}

602

603

604

605

606bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,

607 Instruction *IVOperand) {

609 eliminateIVComparison(ICmp, IVOperand);

610 return true;

611 }

613 bool IsSRem = Bin->getOpcode() == Instruction::SRem;

614 if (IsSRem || Bin->getOpcode() == Instruction::URem) {

615 simplifyIVRemainder(Bin, IVOperand, IsSRem);

616 return true;

617 }

618

619 if (Bin->getOpcode() == Instruction::SDiv)

620 return eliminateSDiv(Bin);

621 }

622

624 if (eliminateOverflowIntrinsic(WO))

625 return true;

626

628 if (eliminateSaturatingIntrinsic(SI))

629 return true;

630

632 if (eliminateTrunc(TI))

633 return true;

634

635 if (eliminateIdentitySCEV(UseInst, IVOperand))

636 return true;

637

638 return false;

639}

640

642 if (auto *BB = L->getLoopPreheader())

643 return BB->getTerminator();

644

645 return Hint;

646}

647

648

649bool SimplifyIndvar::replaceIVUserWithLoopInvariant(Instruction *I) {

651 return false;

652

653

654 const SCEV *S = SE->getSCEV(I);

655

657 return false;

658

659

661 return false;

662

664

665 if ( Rewriter .isSafeToExpandAt(S, IP)) {

666 LLVM_DEBUG(dbgs() << "INDVARS: Can not replace IV user: " << *I

667 << " with non-speculable loop invariant: " << *S << '\n');

668 return false;

669 }

670

671 auto *Invariant = Rewriter.expandCodeFor(S, I->getType(), IP);

672 bool NeedToEmitLCSSAPhis = false;

674 NeedToEmitLCSSAPhis = true;

675

676 I->replaceAllUsesWith(Invariant);

678 << " with loop invariant: " << *S << '\n');

679

680 if (NeedToEmitLCSSAPhis) {

684 LLVM_DEBUG(dbgs() << " INDVARS: Replacement breaks LCSSA form"

685 << " inserting LCSSA Phis" << '\n');

686 }

687 ++NumFoldedUser;

689 DeadInsts.emplace_back(I);

690 return true;

691}

692

693

694bool SimplifyIndvar::replaceFloatIVWithIntegerIV(Instruction *UseInst) {

695 if (UseInst->getOpcode() != CastInst::SIToFP &&

696 UseInst->getOpcode() != CastInst::UIToFP)

697 return false;

698

700

701 const SCEV *IV = SE->getSCEV(IVOperand);

702 int MaskBits;

703 if (UseInst->getOpcode() == CastInst::SIToFP)

705 else

708 if (MaskBits <= DestNumSigBits) {

709 for (User *U : UseInst->users()) {

710

712 if (!CI)

713 continue;

714

715 CastInst::CastOps Opcode = CI->getOpcode();

716 if (Opcode != CastInst::FPToSI && Opcode != CastInst::FPToUI)

717 continue;

718

719 Value *Conv = nullptr;

720 if (IVOperand->getType() != CI->getType()) {

723

724

727 Conv = Builder.CreateTrunc(IVOperand, CI->getType(), Name + ".trunc");

728 } else if (Opcode == CastInst::FPToUI ||

729 UseInst->getOpcode() == CastInst::UIToFP) {

730 Conv = Builder.CreateZExt(IVOperand, CI->getType(), Name + ".zext");

731 } else {

732 Conv = Builder.CreateSExt(IVOperand, CI->getType(), Name + ".sext");

733 }

734 } else

735 Conv = IVOperand;

736

738 DeadInsts.push_back(CI);

739 LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *CI

740 << " with: " << *Conv << '\n');

741

742 ++NumFoldedUser;

744 }

745 }

746

748}

749

750

751bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,

752 Instruction *IVOperand) {

755 return false;

756

757 const SCEV *UseSCEV = SE->getSCEV(UseInst);

758 if (UseSCEV != SE->getSCEV(IVOperand))

759 return false;

760

761

762

763

764

765

766

767

768

769

770

771

772

773

774

775

776

778

779

780 if (!DT || !DT->dominates(IVOperand, UseInst))

781 return false;

782

784 return false;

785

786

789 if (!SE->canReuseInstruction(UseSCEV, IVOperand, DropPoisonGeneratingInsts))

790 return false;

791

792 for (Instruction *I : DropPoisonGeneratingInsts)

793 I->dropPoisonGeneratingAnnotations();

794 }

795

796 LLVM_DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');

797

800 ++NumElimIdentity;

802 DeadInsts.emplace_back(UseInst);

803 return true;

804}

805

806bool SimplifyIndvar::strengthenBinaryOp(BinaryOperator *BO,

807 Instruction *IVOperand) {

809 strengthenOverflowingOperation(BO, IVOperand)) ||

810 (isa(BO) && strengthenRightShift(BO, IVOperand));

811}

812

813

814

815bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,

816 Instruction *IVOperand) {

819

820 if (!Flags)

821 return false;

822

827

828

829

830

831

832

833 return true;

834}

835

836

837

838

839bool SimplifyIndvar::strengthenRightShift(BinaryOperator *BO,

840 Instruction *IVOperand) {

841 if (BO->getOpcode() == Instruction::Shl) {

844 for (auto *U : BO->users()) {

845 const APInt *C;

854 }

855 }

856 }

858 }

859

860 return false;

861}

862

863

864void SimplifyIndvar::pushIVUsers(

865 Instruction *Def, SmallPtrSet<Instruction *, 16> &Simplified,

866 SmallVectorImpl<std::pair<Instruction *, Instruction *>> &SimpleIVUsers) {

867 for (User *U : Def->users()) {

869

870

871

872

873

874 if (UI == Def)

875 continue;

876

877

878

879 if (->contains(UI))

880 continue;

881

882

884 continue;

885

886 SimpleIVUsers.push_back(std::make_pair(UI, Def));

887 }

888}

889

890

891

892

893

894

895

898 return false;

899

900

902

903

905 if (AR && AR->getLoop() == L)

906 return true;

907

908 return false;

909}

910

911

912

913

914

915

916

917

918

919

920

921

922

923void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {

925 return;

926

927

928 SmallPtrSet<Instruction*,16> Simplified;

929

930

932

933

934

935

936 pushIVUsers(CurrIV, Simplified, SimpleIVUsers);

937

938 while (!SimpleIVUsers.empty()) {

939 std::pair<Instruction*, Instruction*> UseOper =

942

943

944

945

946

948 DeadInsts.emplace_back(UseInst);

949 continue;

950 }

951

952

953 if (UseInst == CurrIV) continue;

954

955

956

957 if (replaceIVUserWithLoopInvariant(UseInst))

958 continue;

959

960

961

963 for (Use &U : UseInst->uses()) {

965 if (replaceIVUserWithLoopInvariant(User))

966 break;

967 }

968

970 for (unsigned N = 0; IVOperand; ++N) {

972 (void) N;

973

974 Value *NewOper = foldIVUser(UseInst, IVOperand);

975 if (!NewOper)

976 break;

978 }

979 if (!IVOperand)

980 continue;

981

982 if (eliminateIVUser(UseInst, IVOperand)) {

983 pushIVUsers(IVOperand, Simplified, SimpleIVUsers);

984 continue;

985 }

986

988 if (strengthenBinaryOp(BO, IVOperand)) {

989

990

991 pushIVUsers(IVOperand, Simplified, SimpleIVUsers);

992 }

993 }

994

995

996 if (replaceFloatIVWithIntegerIV(UseInst)) {

997

998 pushIVUsers(IVOperand, Simplified, SimpleIVUsers);

999 continue;

1000 }

1001

1003 if (V && Cast) {

1004 V->visitCast(Cast);

1005 continue;

1006 }

1008 pushIVUsers(UseInst, Simplified, SimpleIVUsers);

1009 }

1010 }

1011}

1012

1013namespace llvm {

1014

1016

1017

1018

1019

1020

1021

1028 Rewriter, Dead);

1029 SIV.simplifyUsers(CurrIV, V);

1030 return {SIV.hasChanged(), SIV.runUnswitching()};

1031}

1032

1033

1034

1039#if LLVM_ENABLE_ABI_BREAKING_CHECKS

1041#endif

1044 const auto &[C, _] =

1047 }

1049}

1050

1051}

1052

1053namespace {

1054

1055

1056

1057

1058

1060

1061 PHINode *OrigPhi;

1062 Type *WideType;

1063

1064

1065 LoopInfo *LI;

1066 Loop *L;

1067 ScalarEvolution *SE;

1068 DominatorTree *DT;

1069

1070

1071

1072 bool HasGuards;

1073

1075

1076

1077 unsigned NumElimExt = 0;

1078 unsigned NumWidened = 0;

1079

1080

1081 PHINode *WidePhi = nullptr;

1083 const SCEV *WideIncExpr = nullptr;

1084 SmallVectorImpl &DeadInsts;

1085

1086 SmallPtrSet<Instruction *,16> Widened;

1087

1088 enum class ExtendKind { Zero, Sign, Unknown };

1089

1090

1091

1092

1093

1094 DenseMap<AssertingVH, ExtendKind> ExtendKindMap;

1095

1096 using DefUserPair = std::pair<AssertingVH, AssertingVH>;

1097

1098

1099

1100

1101

1102 DenseMap<DefUserPair, ConstantRange> PostIncRangeInfos;

1103

1104 std::optional getPostIncRangeInfo(Value *Def,

1105 Instruction *UseI) {

1106 DefUserPair Key(Def, UseI);

1107 auto It = PostIncRangeInfos.find(Key);

1108 return It == PostIncRangeInfos.end()

1109 ? std::optional(std::nullopt)

1110 : std::optional(It->second);

1111 }

1112

1113 void calculatePostIncRanges(PHINode *OrigPhi);

1114 void calculatePostIncRange(Instruction *NarrowDef, Instruction *NarrowUser);

1115

1116 void updatePostIncRangeInfo(Value *Def, Instruction *UseI, ConstantRange R) {

1117 DefUserPair Key(Def, UseI);

1119 if (!Inserted)

1120 It->second = R.intersectWith(It->second);

1121 }

1122

1123public:

1124

1125

1126

1127 struct NarrowIVDefUse {

1131

1132

1133

1134

1135 bool NeverNegative = false;

1136

1137 NarrowIVDefUse(Instruction *ND, Instruction *NU, Instruction *WD,

1138 bool NeverNegative)

1139 : NarrowDef(ND), NarrowUse(NU), WideDef(WD),

1140 NeverNegative(NeverNegative) {}

1141 };

1142

1143 WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, ScalarEvolution *SEv,

1144 DominatorTree *DTree, SmallVectorImpl &DI,

1146

1148

1149 unsigned getNumElimExt() { return NumElimExt; };

1150 unsigned getNumWidened() { return NumWidened; };

1151

1152protected:

1153 Value *createExtendInst(Value *NarrowOper, Type *WideType, bool IsSigned,

1154 Instruction *Use);

1155

1156 Instruction *cloneIVUser(NarrowIVDefUse DU, const SCEVAddRecExpr *WideAR);

1157 Instruction *cloneArithmeticIVUser(NarrowIVDefUse DU,

1158 const SCEVAddRecExpr *WideAR);

1159 Instruction *cloneBitwiseIVUser(NarrowIVDefUse DU);

1160

1161 ExtendKind getExtendKind(Instruction *I);

1162

1163 using WidenedRecTy = std::pair<const SCEVAddRecExpr *, ExtendKind>;

1164

1165 WidenedRecTy getWideRecurrence(NarrowIVDefUse DU);

1166

1167 WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU);

1168

1169 const SCEV *getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,

1170 unsigned OpCode) const;

1171

1173 PHINode *OrigPhi, PHINode *WidePhi);

1174 void truncateIVUse(NarrowIVDefUse DU);

1175

1176 bool widenLoopCompare(NarrowIVDefUse DU);

1177 bool widenWithVariantUse(NarrowIVDefUse DU);

1178

1179 void pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef);

1180

1181private:

1183};

1184}

1185

1186

1187

1188

1189

1190

1191

1195 if ( PHI )

1196 return User;

1197

1199 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {

1200 if (PHI->getIncomingValue(i) != Def)

1201 continue;

1202

1203 BasicBlock *InsertBB = PHI->getIncomingBlock(i);

1204

1206 continue;

1207

1208 if (!InsertPt) {

1210 continue;

1211 }

1214 }

1215

1216

1217

1218 if (!InsertPt)

1219 return nullptr;

1220

1222 if (!DefI)

1223 return InsertPt;

1224

1225 assert(DT->dominates(DefI, InsertPt) && "def does not dominate all uses");

1226

1227 auto *L = LI->getLoopFor(DefI->getParent());

1229

1230 for (auto *DTN = (*DT)[InsertPt->getParent()]; DTN; DTN = DTN->getIDom())

1231 if (LI->getLoopFor(DTN->getBlock()) == L)

1232 return DTN->getBlock()->getTerminator();

1233

1235}

1236

1240 : OrigPhi(WI.NarrowIV), WideType(WI.WidestNativeType), LI(LInfo),

1241 L(LI->getLoopFor(OrigPhi->getParent())), SE(SEv), DT(DTree),

1243 DeadInsts(DI) {

1244 assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV");

1245 ExtendKindMap[OrigPhi] = WI.IsSigned ? ExtendKind::Sign : ExtendKind::Zero;

1246}

1247

1248Value *WidenIV::createExtendInst(Value *NarrowOper, Type *WideType,

1250

1252

1253 for (const Loop *L = LI->getLoopFor(Use->getParent());

1254 L && L->getLoopPreheader() && L->isLoopInvariant(NarrowOper);

1255 L = L->getParentLoop())

1256 Builder.SetInsertPoint(L->getLoopPreheader()->getTerminator());

1257

1258 return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) :

1259 Builder.CreateZExt(NarrowOper, WideType);

1260}

1261

1262

1263

1264

1265Instruction *WidenIV::cloneIVUser(WidenIV::NarrowIVDefUse DU,

1266 const SCEVAddRecExpr *WideAR) {

1267 unsigned Opcode = DU.NarrowUse->getOpcode();

1268 switch (Opcode) {

1269 default:

1270 return nullptr;

1271 case Instruction::Add:

1272 case Instruction::Mul:

1273 case Instruction::UDiv:

1274 case Instruction::Sub:

1275 return cloneArithmeticIVUser(DU, WideAR);

1276

1277 case Instruction::And:

1278 case Instruction::Or:

1279 case Instruction::Xor:

1280 case Instruction::Shl:

1281 case Instruction::LShr:

1282 case Instruction::AShr:

1283 return cloneBitwiseIVUser(DU);

1284 }

1285}

1286

1287Instruction *WidenIV::cloneBitwiseIVUser(WidenIV::NarrowIVDefUse DU) {

1291

1292 LLVM_DEBUG(dbgs() << "Cloning bitwise IVUser: " << *NarrowUse << "\n");

1293

1294

1295

1296

1297

1298 bool IsSigned = getExtendKind(NarrowDef) == ExtendKind::Sign;

1300 ? WideDef

1301 : createExtendInst(NarrowUse->getOperand(0), WideType,

1302 IsSigned, NarrowUse);

1304 ? WideDef

1305 : createExtendInst(NarrowUse->getOperand(1), WideType,

1306 IsSigned, NarrowUse);

1307

1312 Builder.Insert(WideBO);

1313 WideBO->copyIRFlags(NarrowBO);

1314 return WideBO;

1315}

1316

1317Instruction *WidenIV::cloneArithmeticIVUser(WidenIV::NarrowIVDefUse DU,

1318 const SCEVAddRecExpr *WideAR) {

1322

1323 LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");

1324

1325 unsigned IVOpIdx = (NarrowUse->getOperand(0) == NarrowDef) ? 0 : 1;

1326

1327

1328

1329

1330

1331

1332

1333

1334

1335

1336 auto GuessNonIVOperand = [&](bool SignExt) {

1337 const SCEV *WideLHS;

1338 const SCEV *WideRHS;

1339

1340 auto GetExtend = [this, SignExt](const SCEV *S, Type *Ty) {

1341 if (SignExt)

1344 };

1345

1346 if (IVOpIdx == 0) {

1347 WideLHS = SE->getSCEV(WideDef);

1349 WideRHS = GetExtend(NarrowRHS, WideType);

1350 } else {

1352 WideLHS = GetExtend(NarrowLHS, WideType);

1353 WideRHS = SE->getSCEV(WideDef);

1354 }

1355

1356

1357 const SCEV *WideUse =

1358 getSCEVByOpCode(WideLHS, WideRHS, NarrowUse->getOpcode());

1359

1360 return WideUse == WideAR;

1361 };

1362

1363 bool SignExtend = getExtendKind(NarrowDef) == ExtendKind::Sign;

1364 if (!GuessNonIVOperand(SignExtend)) {

1365 SignExtend = !SignExtend;

1366 if (!GuessNonIVOperand(SignExtend))

1367 return nullptr;

1368 }

1369

1371 ? WideDef

1372 : createExtendInst(NarrowUse->getOperand(0), WideType,

1373 SignExtend, NarrowUse);

1375 ? WideDef

1376 : createExtendInst(NarrowUse->getOperand(1), WideType,

1377 SignExtend, NarrowUse);

1378

1382

1384 Builder.Insert(WideBO);

1385 WideBO->copyIRFlags(NarrowBO);

1386 return WideBO;

1387}

1388

1389WidenIV::ExtendKind WidenIV::getExtendKind(Instruction *I) {

1390 auto It = ExtendKindMap.find(I);

1391 assert(It != ExtendKindMap.end() && "Instruction not yet extended!");

1392 return It->second;

1393}

1394

1395const SCEV *WidenIV::getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,

1396 unsigned OpCode) const {

1397 switch (OpCode) {

1398 case Instruction::Add:

1400 case Instruction::Sub:

1402 case Instruction::Mul:

1404 case Instruction::UDiv:

1406 default:

1408 };

1409}

1410

1411namespace {

1412

1413

1414

1415

1416struct BinaryOp {

1417 unsigned Opcode;

1418 std::array<Value *, 2> Operands;

1419 bool IsNSW = false;

1420 bool IsNUW = false;

1421

1422 explicit BinaryOp(Instruction *Op)

1424 Operands({Op->getOperand(0), Op->getOperand(1)}) {

1426 IsNSW = OBO->hasNoSignedWrap();

1427 IsNUW = OBO->hasNoUnsignedWrap();

1428 }

1429 }

1430

1432 bool IsNSW = false, bool IsNUW = false)

1433 : Opcode(Opcode), Operands({LHS, RHS}), IsNSW(IsNSW), IsNUW(IsNUW) {}

1434};

1435

1436}

1437

1439 switch (Op->getOpcode()) {

1440 case Instruction::Add:

1441 case Instruction::Sub:

1442 case Instruction::Mul:

1443 return BinaryOp(Op);

1444 case Instruction::Or: {

1445

1447 return BinaryOp(Instruction::Add, Op->getOperand(0), Op->getOperand(1),

1448 true, true);

1449 break;

1450 }

1451 case Instruction::Shl: {

1454

1455

1456

1457

1458

1459 if (SA->getValue().ult(BitWidth)) {

1460

1461

1462

1463

1464 bool IsNUW = Op->hasNoUnsignedWrap();

1465 bool IsNSW = Op->hasNoSignedWrap() &&

1466 (IsNUW || SA->getValue().ult(BitWidth - 1));

1467

1469 ConstantInt::get(Op->getContext(),

1471 return BinaryOp(Instruction::Mul, Op->getOperand(0), X, IsNSW, IsNUW);

1472 }

1473 }

1474

1475 break;

1476 }

1477 }

1478

1479 return std::nullopt;

1480}

1481

1482

1483

1484

1485

1486

1487WidenIV::WidenedRecTy

1488WidenIV::getExtendedOperandRecurrence(WidenIV::NarrowIVDefUse DU) {

1490 if ()

1491 return {nullptr, ExtendKind::Unknown};

1492

1493 assert((Op->Opcode == Instruction::Add || Op->Opcode == Instruction::Sub ||

1494 Op->Opcode == Instruction::Mul) &&

1495 "Unexpected opcode");

1496

1497

1498

1499 const unsigned ExtendOperIdx = Op->Operands[0] == DU.NarrowDef ? 1 : 0;

1500 assert(Op->Operands[1 - ExtendOperIdx] == DU.NarrowDef && "bad DU");

1501

1502 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);

1503 if (!(ExtKind == ExtendKind::Sign && Op->IsNSW) &&

1504 !(ExtKind == ExtendKind::Zero && Op->IsNUW)) {

1505 ExtKind = ExtendKind::Unknown;

1506

1507

1508

1509

1510

1511 if (DU.NeverNegative) {

1512 if (Op->IsNSW) {

1513 ExtKind = ExtendKind::Sign;

1514 } else if (Op->IsNUW) {

1515 ExtKind = ExtendKind::Zero;

1516 }

1517 }

1518 }

1519

1520 const SCEV *ExtendOperExpr = SE->getSCEV(Op->Operands[ExtendOperIdx]);

1521 if (ExtKind == ExtendKind::Sign)

1522 ExtendOperExpr = SE->getSignExtendExpr(ExtendOperExpr, WideType);

1523 else if (ExtKind == ExtendKind::Zero)

1524 ExtendOperExpr = SE->getZeroExtendExpr(ExtendOperExpr, WideType);

1525 else

1526 return {nullptr, ExtendKind::Unknown};

1527

1528

1529

1530

1531

1532

1533 const SCEV *lhs = SE->getSCEV(DU.WideDef);

1534 const SCEV *rhs = ExtendOperExpr;

1535

1536

1537

1538 if (ExtendOperIdx == 0)

1540 const SCEVAddRecExpr *AddRec =

1542

1543 if (!AddRec || AddRec->getLoop() != L)

1544 return {nullptr, ExtendKind::Unknown};

1545

1546 return {AddRec, ExtKind};

1547}

1548

1549

1550

1551

1552

1553

1554WidenIV::WidenedRecTy WidenIV::getWideRecurrence(WidenIV::NarrowIVDefUse DU) {

1556 return {nullptr, ExtendKind::Unknown};

1557

1558 const SCEV *NarrowExpr = SE->getSCEV(DU.NarrowUse);

1561

1562

1563 return {nullptr, ExtendKind::Unknown};

1564 }

1565

1566 const SCEV *WideExpr;

1567 ExtendKind ExtKind;

1568 if (DU.NeverNegative) {

1571 ExtKind = ExtendKind::Sign;

1572 else {

1574 ExtKind = ExtendKind::Zero;

1575 }

1576 } else if (getExtendKind(DU.NarrowDef) == ExtendKind::Sign) {

1578 ExtKind = ExtendKind::Sign;

1579 } else {

1581 ExtKind = ExtendKind::Zero;

1582 }

1584 if (!AddRec || AddRec->getLoop() != L)

1585 return {nullptr, ExtendKind::Unknown};

1586 return {AddRec, ExtKind};

1587}

1588

1589

1590

1591void WidenIV::truncateIVUse(NarrowIVDefUse DU) {

1593 if (!InsertPt)

1594 return;

1595 LLVM_DEBUG(dbgs() << "INDVARS: Truncate IV " << *DU.WideDef << " for user "

1596 << *DU.NarrowUse << "\n");

1597 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);

1600 Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType(), "",

1601 DU.NeverNegative || ExtKind == ExtendKind::Zero,

1602 DU.NeverNegative || ExtKind == ExtendKind::Sign);

1603 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);

1604}

1605

1606

1607

1608

1609bool WidenIV::widenLoopCompare(WidenIV::NarrowIVDefUse DU) {

1611 if (!Cmp)

1612 return false;

1613

1614

1615

1616

1617

1618

1619

1620

1621

1622

1623

1624

1625

1626

1627

1628 bool IsSigned = getExtendKind(DU.NarrowDef) == ExtendKind::Sign;

1629 bool CmpPreferredSign = Cmp->hasSameSign() ? IsSigned : Cmp->isSigned();

1630 if (!DU.NeverNegative && IsSigned != CmpPreferredSign)

1631 return false;

1632

1633 Value *Op = Cmp->getOperand(Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);

1636 assert(CastWidth <= IVWidth && "Unexpected width while widening compare.");

1637

1638

1640

1641

1642 if (CastWidth < IVWidth) {

1643

1644

1645

1647 CmpPreferredSign = true;

1648

1649 Value *ExtOp = createExtendInst(Op, WideType, CmpPreferredSign, Cmp);

1651 }

1652 return true;

1653}

1654

1655

1656

1657

1658

1659

1660

1661

1662

1663

1664

1665

1666

1667

1668

1669

1670

1671

1672

1673

1674

1675bool WidenIV::widenWithVariantUse(WidenIV::NarrowIVDefUse DU) {

1679

1680

1682

1683 if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&

1684 OpCode != Instruction::Mul)

1685 return false;

1686

1687

1688

1690 NarrowUse->getOperand(1) == NarrowDef) &&

1691 "bad DU");

1692

1693 const OverflowingBinaryOperator *OBO =

1695 ExtendKind ExtKind = getExtendKind(NarrowDef);

1696 bool CanSignExtend = ExtKind == ExtendKind::Sign && OBO->hasNoSignedWrap();

1697 bool CanZeroExtend = ExtKind == ExtendKind::Zero && OBO->hasNoUnsignedWrap();

1698 auto AnotherOpExtKind = ExtKind;

1699

1700

1701

1702

1703

1704

1705 SmallVector<Instruction *, 4> ExtUsers;

1708 for (Use &U : NarrowUse->uses()) {

1710 if (User == NarrowDef)

1711 continue;

1712 if (->contains(User)) {

1714

1715

1716 if (LCSSAPhi->getNumOperands() != 1)

1717 return false;

1718 LCSSAPhiUsers.push_back(LCSSAPhi);

1719 continue;

1720 }

1723

1724

1725

1726

1727 if (ExtKind == ExtendKind::Zero && ICmpInst::isSigned(Pred))

1728 return false;

1729 if (ExtKind == ExtendKind::Sign && ICmpInst::isUnsigned(Pred))

1730 return false;

1732 continue;

1733 }

1734 if (ExtKind == ExtendKind::Sign)

1736 else

1738 if (!User || User->getType() != WideType)

1739 return false;

1741 }

1742 if (ExtUsers.empty()) {

1744 return true;

1745 }

1746

1747

1748

1749

1751

1752 if (!CanSignExtend && !CanZeroExtend) {

1753

1754

1755 if (OpCode != Instruction::Add)

1756 return false;

1757 if (ExtKind != ExtendKind::Zero)

1758 return false;

1761

1762 if (NarrowUse->getOperand(0) != NarrowDef)

1763 return false;

1764

1765 if (NarrowUse->getOperand(1) == NarrowDef)

1766 return false;

1768 return false;

1771 if (!ProvedSubNUW)

1772 return false;

1773

1774

1775 AnotherOpExtKind = ExtendKind::Sign;

1776 }

1777

1778

1779 const SCEV *Op1 = SE->getSCEV(WideDef);

1781 if (!AddRecOp1 || AddRecOp1->getLoop() != L)

1782 return false;

1783

1784 LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");

1785

1786

1788 (NarrowUse->getOperand(0) == NarrowDef)

1789 ? WideDef

1790 : createExtendInst(NarrowUse->getOperand(0), WideType,

1791 AnotherOpExtKind == ExtendKind::Sign, NarrowUse);

1793 (NarrowUse->getOperand(1) == NarrowDef)

1794 ? WideDef

1795 : createExtendInst(NarrowUse->getOperand(1), WideType,

1796 AnotherOpExtKind == ExtendKind::Sign, NarrowUse);

1797

1802 Builder.Insert(WideBO);

1803 WideBO->copyIRFlags(NarrowBO);

1804 ExtendKindMap[NarrowUse] = ExtKind;

1805

1806 for (Instruction *User : ExtUsers) {

1807 assert(User->getType() == WideType && "Checked before!");

1808 LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *User << " replaced by "

1809 << *WideBO << "\n");

1810 ++NumElimExt;

1811 User->replaceAllUsesWith(WideBO);

1813 }

1814

1815 for (PHINode *User : LCSSAPhiUsers) {

1816 assert(User->getNumOperands() == 1 && "Checked before!");

1817 Builder.SetInsertPoint(User);

1818 auto *WidePN =

1819 Builder.CreatePHI(WideBO->getType(), 1, User->getName() + ".wide");

1820 BasicBlock *LoopExitingBlock = User->getParent()->getSinglePredecessor();

1821 assert(LoopExitingBlock && L->contains(LoopExitingBlock) &&

1822 "Not a LCSSA Phi?");

1823 WidePN->addIncoming(WideBO, LoopExitingBlock);

1824 Builder.SetInsertPoint(User->getParent(),

1825 User->getParent()->getFirstInsertionPt());

1826 auto *TruncPN = Builder.CreateTrunc(WidePN, User->getType());

1827 User->replaceAllUsesWith(TruncPN);

1829 }

1830

1831 for (ICmpInst *User : ICmpUsers) {

1832 Builder.SetInsertPoint(User);

1833 auto ExtendedOp = [&](Value * V)->Value * {

1834 if (V == NarrowUse)

1835 return WideBO;

1836 if (ExtKind == ExtendKind::Zero)

1837 return Builder.CreateZExt(V, WideBO->getType());

1838 else

1839 return Builder.CreateSExt(V, WideBO->getType());

1840 };

1841 auto Pred = User->getPredicate();

1842 auto *LHS = ExtendedOp(User->getOperand(0));

1843 auto *RHS = ExtendedOp(User->getOperand(1));

1844 auto *WideCmp =

1845 Builder.CreateICmp(Pred, LHS, RHS, User->getName() + ".wide");

1846 User->replaceAllUsesWith(WideCmp);

1848 }

1849

1850 return true;

1851}

1852

1853

1854

1855Instruction *WidenIV::widenIVUse(WidenIV::NarrowIVDefUse DU,

1856 SCEVExpander &Rewriter, PHINode *OrigPhi,

1857 PHINode *WidePhi) {

1858 assert(ExtendKindMap.count(DU.NarrowDef) &&

1859 "Should already know the kind of extension used to widen NarrowDef");

1860

1861

1862

1863 bool CanWidenBySExt =

1864 DU.NeverNegative || getExtendKind(DU.NarrowDef) == ExtendKind::Sign;

1865 bool CanWidenByZExt =

1866 DU.NeverNegative || getExtendKind(DU.NarrowDef) == ExtendKind::Zero;

1867

1868

1870 if (LI->getLoopFor(UsePhi->getParent()) != L) {

1871

1872

1873

1874 if (UsePhi->getNumOperands() != 1)

1875 truncateIVUse(DU);

1876 else {

1877

1878

1879

1881 return nullptr;

1882

1883 PHINode *WidePhi =

1885 UsePhi->getIterator());

1886 WidePhi->addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0));

1889 Value *Trunc = Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType(), "",

1890 CanWidenByZExt, CanWidenBySExt);

1893 LLVM_DEBUG(dbgs() << "INDVARS: Widen lcssa phi " << *UsePhi << " to "

1894 << *WidePhi << "\n");

1895 }

1896 return nullptr;

1897 }

1898 }

1899

1900

1902 (isa(DU.NarrowUse) && CanWidenByZExt)) {

1903 Value *NewDef = DU.WideDef;

1904 if (DU.NarrowUse->getType() != WideType) {

1907 if (CastWidth < IVWidth) {

1908

1910 NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType(), "",

1911 CanWidenByZExt, CanWidenBySExt);

1912 }

1913 else {

1914

1915

1916

1918 << " not wide enough to subsume " << *DU.NarrowUse

1919 << "\n");

1921 NewDef = DU.NarrowUse;

1922 }

1923 }

1924 if (NewDef != DU.NarrowUse) {

1925 LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *DU.NarrowUse

1926 << " replaced by " << *DU.WideDef << "\n");

1927 ++NumElimExt;

1930 }

1931

1932

1933

1934

1935

1936

1937

1938 return nullptr;

1939 }

1940

1941 auto tryAddRecExpansion = [&]() -> Instruction* {

1942

1943 WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);

1944 if (!WideAddRec.first)

1945 WideAddRec = getWideRecurrence(DU);

1946 assert((WideAddRec.first == nullptr) ==

1947 (WideAddRec.second == ExtendKind::Unknown));

1948 if (!WideAddRec.first)

1949 return nullptr;

1950

1951 auto CanUseWideInc = [&]() {

1952 if (!WideInc)

1953 return false;

1954

1955

1956

1957

1958 bool NeedToRecomputeFlags =

1960 OrigPhi, WidePhi, DU.NarrowUse, WideInc) ||

1963 return WideAddRec.first == WideIncExpr &&

1964 Rewriter.hoistIVInc(WideInc, DU.NarrowUse, NeedToRecomputeFlags);

1965 };

1966

1968 if (CanUseWideInc())

1969 WideUse = WideInc;

1970 else {

1971 WideUse = cloneIVUser(DU, WideAddRec.first);

1972 if (!WideUse)

1973 return nullptr;

1974 }

1975

1976

1977

1978

1979

1980 if (WideAddRec.first != SE->getSCEV(WideUse)) {

1981 LLVM_DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse << ": "

1982 << *SE->getSCEV(WideUse) << " != " << *WideAddRec.first

1983 << "\n");

1985 return nullptr;

1986 };

1987

1988

1989

1991

1992 ExtendKindMap[DU.NarrowUse] = WideAddRec.second;

1993

1994 return WideUse;

1995 };

1996

1997 if (auto *I = tryAddRecExpansion())

1998 return I;

1999

2000

2001

2002 if (widenLoopCompare(DU))

2003 return nullptr;

2004

2005

2006

2007

2008

2009

2010 if (widenWithVariantUse(DU))

2011 return nullptr;

2012

2013

2014

2015

2016 truncateIVUse(DU);

2017 return nullptr;

2018}

2019

2020

2021void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) {

2022 const SCEV *NarrowSCEV = SE->getSCEV(NarrowDef);

2023 bool NonNegativeDef =

2026 for (User *U : NarrowDef->users()) {

2028

2029

2030 if (!Widened.insert(NarrowUser).second)

2031 continue;

2032

2033 bool NonNegativeUse = false;

2034 if (!NonNegativeDef) {

2035

2036 if (auto RangeInfo = getPostIncRangeInfo(NarrowDef, NarrowUser))

2037 NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();

2038 }

2039

2040 NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef,

2041 NonNegativeDef || NonNegativeUse);

2042 }

2043}

2044

2045

2046

2047

2048

2049

2050

2051

2052

2053PHINode *WidenIV::createWideIV(SCEVExpander &Rewriter) {

2054

2056 if (!AddRec)

2057 return nullptr;

2058

2059

2060 const SCEV *WideIVExpr = getExtendKind(OrigPhi) == ExtendKind::Sign

2063

2065 "Expect the new IV expression to preserve its type");

2066

2067

2069 if (!AddRec || AddRec->getLoop() != L)

2070 return nullptr;

2071

2072

2073

2074

2078 "Loop header phi recurrence inputs do not dominate the loop");

2079

2080

2081

2082

2083

2084

2085

2086

2087

2088

2089

2091 calculatePostIncRanges(OrigPhi);

2092

2093

2094

2095

2096

2097 Instruction *InsertPt = &*L->getHeader()->getFirstInsertionPt();

2098 Value *ExpandInst = Rewriter.expandCodeFor(AddRec, WideType, InsertPt);

2099

2100

2102

2103

2104

2108 return nullptr;

2109 }

2110

2111

2112

2113

2114

2115 if (BasicBlock *LatchBlock = L->getLoopLatch()) {

2116 WideInc =

2118 if (WideInc) {

2119 WideIncExpr = SE->getSCEV(WideInc);

2120

2121

2122 auto *OrigInc =

2124

2125 WideInc->setDebugLoc(OrigInc->getDebugLoc());

2126

2127

2128

2129

2130

2131

2132

2133

2134

2136 OrigInc, WideInc) &&

2140 OrigInc->hasNoUnsignedWrap());

2142 OrigInc->hasNoSignedWrap());

2143 }

2144 }

2145 }

2146

2147 LLVM_DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n");

2148 ++NumWidened;

2149

2150

2151 assert(Widened.empty() && NarrowIVUsers.empty() && "expect initial state" );

2152

2153 Widened.insert(OrigPhi);

2154 pushNarrowIVUsers(OrigPhi, WidePhi);

2155

2156 while (!NarrowIVUsers.empty()) {

2157 WidenIV::NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();

2158

2159

2160

2162

2163

2164 if (WideUse)

2165 pushNarrowIVUsers(DU.NarrowUse, WideUse);

2166

2167

2170 }

2171

2172

2174

2175 return WidePhi;

2176}

2177

2178

2179

2180void WidenIV::calculatePostIncRange(Instruction *NarrowDef,

2181 Instruction *NarrowUser) {

2182 Value *NarrowDefLHS;

2183 const APInt *NarrowDefRHS;

2185 m_APInt(NarrowDefRHS))) ||

2187 return;

2188

2189 auto UpdateRangeFromCondition = [&](Value *Condition, bool TrueDest) {

2190 CmpPredicate Pred;

2194 return;

2195

2197

2199 auto CmpConstrainedLHSRange =

2201 auto NarrowDefRange = CmpConstrainedLHSRange.addWithNoWrap(

2203

2204 updatePostIncRangeInfo(NarrowDef, NarrowUser, NarrowDefRange);

2205 };

2206

2207 auto UpdateRangeFromGuards = [&](Instruction *Ctx) {

2208 if (!HasGuards)

2209 return;

2210

2211 for (Instruction &I : make_range(Ctx->getIterator().getReverse(),

2212 Ctx->getParent()->rend())) {

2215 UpdateRangeFromCondition(C, true);

2216 }

2217 };

2218

2219 UpdateRangeFromGuards(NarrowUser);

2220

2222

2223

2225 return;

2226

2227 for (auto *DTB = (*DT)[NarrowUserBB]->getIDom();

2228 L->contains(DTB->getBlock());

2229 DTB = DTB->getIDom()) {

2230 auto *BB = DTB->getBlock();

2231 auto *TI = BB->getTerminator();

2232 UpdateRangeFromGuards(TI);

2233

2235 if (!BI || !BI->isConditional())

2236 continue;

2237

2238 auto *TrueSuccessor = BI->getSuccessor(0);

2239 auto *FalseSuccessor = BI->getSuccessor(1);

2240

2241 auto DominatesNarrowUser = [this, NarrowUser] (BasicBlockEdge BBE) {

2242 return BBE.isSingleEdge() &&

2244 };

2245

2246 if (DominatesNarrowUser(BasicBlockEdge(BB, TrueSuccessor)))

2247 UpdateRangeFromCondition(BI->getCondition(), true);

2248

2249 if (DominatesNarrowUser(BasicBlockEdge(BB, FalseSuccessor)))

2250 UpdateRangeFromCondition(BI->getCondition(), false);

2251 }

2252}

2253

2254

2255void WidenIV::calculatePostIncRanges(PHINode *OrigPhi) {

2256 SmallPtrSet<Instruction *, 16> Visited;

2259 Visited.insert(OrigPhi);

2260

2261 while (!Worklist.empty()) {

2263

2264 for (Use &U : NarrowDef->uses()) {

2266

2267

2268 auto *NarrowUserLoop = (*LI)[NarrowUser->getParent()];

2269 if (!NarrowUserLoop || ->contains(NarrowUserLoop))

2270 continue;

2271

2272 if (!Visited.insert(NarrowUser).second)

2273 continue;

2274

2276

2277 calculatePostIncRange(NarrowDef, NarrowUser);

2278 }

2279 }

2280}

2281

2285 unsigned &NumElimExt, unsigned &NumWidened,

2288 PHINode *WidePHI = Widener.createWideIV(Rewriter);

2289 NumElimExt = Widener.getNumElimExt();

2290 NumWidened = Widener.getNumWidened();

2291 return WidePHI;

2292}

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

static const Function * getParent(const Value *V)

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

iv Induction Variable Users

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 cl::opt< bool > WidenIV("loop-flatten-widen-iv", cl::Hidden, cl::init(true), cl::desc("Widen the loop induction variables, if possible, so " "overflow checks won't reject flattening"))

Definition SimplifyIndVar.cpp:1237

static Instruction * GetLoopInvariantInsertPosition(Loop *L, Instruction *Hint)

Definition SimplifyIndVar.cpp:641

static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE)

Return true if this instruction generates a simple SCEV expression in terms of that IV.

Definition SimplifyIndVar.cpp:896

static Instruction * findCommonDominator(ArrayRef< Instruction * > Instructions, DominatorTree &DT)

Find a point in code which dominates all given instructions.

Definition SimplifyIndVar.cpp:118

static Instruction * getInsertPointForUses(Instruction *User, Value *Def, DominatorTree *DT, LoopInfo *LI)

Determine the insertion point for this user.

Definition SimplifyIndVar.cpp:1192

static std::optional< BinaryOp > matchBinaryOp(Instruction *Op)

Definition SimplifyIndVar.cpp:1438

This file defines the SmallVector class.

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

#define STATISTIC(VARNAME, DESC)

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

static std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)

Returns the opcode of Values or ~0 if they do not all agree.

Virtual Register Rewriter

static const uint32_t IV[8]

bool isNonNegative() const

Determine if this APInt Value is non-negative (>= 0)

static APInt getOneBitSet(unsigned numBits, unsigned BitNo)

Return an APInt with exactly one bit set in the result.

bool uge(const APInt &RHS) const

Unsigned greater or equal comparison.

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

LLVM Basic Block Representation.

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

LLVM_ABI bool isSigned() const

Whether the intrinsic is signed or unsigned.

LLVM_ABI Instruction::BinaryOps getBinaryOp() const

Returns the binary operation underlying the intrinsic.

BinaryOps getOpcode() const

static LLVM_ABI BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), InsertPosition InsertBefore=nullptr)

Construct a binary instruction, given the opcode and the two operands.

void setPredicate(Predicate P)

Set the predicate for this instruction to the specified value.

Predicate getPredicate() const

Return the predicate for this instruction.

This is the shared class of boolean and integer constants.

static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)

static LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)

LLVM_ABI unsigned getActiveBits() const

Compute the maximal number of active bits needed to represent every value in this range.

LLVM_ABI APInt getUnsignedMin() const

Return the smallest unsigned value contained in the ConstantRange.

static LLVM_ABI ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)

Produce the smallest range such that all values that may satisfy the given predicate with any value c...

LLVM_ABI unsigned getMinSignedBits() const

Compute the maximal number of bits needed to represent every value in this signed range.

iterator find(const_arg_type_t< KeyT > Val)

std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)

size_type count(const_arg_type_t< KeyT > Val) const

Return 1 if the specified key is in the map, 0 otherwise.

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

LLVM_ABI bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

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.

bool hasSameSign() const

An icmp instruction, which can be marked as "samesign", indicating that the two operands have the sam...

void setSameSign(bool B=true)

CmpPredicate getCmpPredicate() const

CmpPredicate getSwappedCmpPredicate() const

CmpPredicate getInverseCmpPredicate() const

Predicate getSignedPredicate() const

For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.

static bool isEquality(Predicate P)

Return true if this predicate is either EQ or NE.

Predicate getUnsignedPredicate() const

For example, EQ->EQ, SLE->ULE, UGT->UGT, etc.

Interface for visiting interesting IV users that are recognized but not simplified by this utility.

virtual void anchor()

Definition SimplifyIndVar.cpp:1015

LLVM_ABI void setHasNoUnsignedWrap(bool b=true)

Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.

LLVM_ABI bool hasNoUnsignedWrap() const LLVM_READONLY

Determine whether the no unsigned wrap flag is set.

LLVM_ABI bool hasNoSignedWrap() const LLVM_READONLY

Determine whether the no signed wrap flag is set.

LLVM_ABI void setHasNoSignedWrap(bool b=true)

Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

LLVM_ABI InstListType::iterator eraseFromParent()

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

LLVM_ABI bool isExact() const LLVM_READONLY

Determine whether the exact flag is set.

unsigned getOpcode() const

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

LLVM_ABI void setIsExact(bool b=true)

Set or clear the exact flag on this instruction, which must be an operator which supports this flag.

LLVM_ABI void dropPoisonGeneratingFlags()

Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

BlockT * getLoopPreheader() const

If there is a preheader for this loop, return it.

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.

bool hasNoSignedWrap() const

Test whether this operation is known to never undergo signed overflow, aka the nsw property.

bool hasNoUnsignedWrap() const

Test whether this operation is known to never undergo unsigned overflow, aka the nuw property.

void addIncoming(Value *V, BasicBlock *BB)

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

Value * getIncomingValueForBlock(const BasicBlock *BB) const

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.

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

const SCEV * getStart() const

const SCEV * getStepRecurrence(ScalarEvolution &SE) const

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

const Loop * getLoop() const

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

static LLVM_ABI bool canReuseFlagsFromOriginalIVInc(PHINode *OrigPhi, PHINode *WidePhi, Instruction *OrigInc, Instruction *WideInc)

Return true if both increments directly increment the corresponding IV PHI nodes and have the same op...

This class represents an analyzed expression in the program.

LLVM_ABI Type * getType() const

Return the LLVM type of this SCEV expression.

The main scalar evolution driver.

const DataLayout & getDataLayout() const

Return the DataLayout associated with the module this SCEV instance is operating on.

LLVM_ABI bool isKnownNonNegative(const SCEV *S)

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

LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)

Return the SCEV object corresponding to -V.

LLVM_ABI bool isKnownNegative(const SCEV *S)

Test if the given expression is known to be negative.

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.

const SCEV * getZero(Type *Ty)

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

LLVM_ABI bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)

Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?

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.

ConstantRange getSignedRange(const SCEV *S)

Determine the signed range for a particular SCEV.

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 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 * getUDivExpr(const SCEV *LHS, const SCEV *RHS)

Get a canonical unsigned division expression, or something simpler if possible.

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

LLVM_ABI bool haveSameSign(const SCEV *S1, const SCEV *S2)

Return true if we know that S1 and S2 must have the same sign.

ConstantRange getUnsignedRange(const SCEV *S)

Determine the unsigned range for a particular SCEV.

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 std::optional< LoopInvariantPredicate > getLoopInvariantPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI=nullptr)

If the result of the predicate LHS Pred RHS is loop invariant with respect to L, return a LoopInvaria...

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

Return LHS-RHS.

LLVM_ABI std::optional< SCEV::NoWrapFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)

Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...

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

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

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

static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask)

Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name ...

LLVM_ABI bool properlyDominates(const SCEV *S, const BasicBlock *BB)

Return true if elements that makes up the given SCEV properly dominate the specified basic block.

LLVM_ABI bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)

Check whether it is poison-safe to represent the expression S using the instruction I.

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

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

static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", InsertPosition InsertBefore=nullptr, const Instruction *MDFrom=nullptr)

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

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

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

bool isIntegerTy() const

True if this is an instance of IntegerType.

LLVM_ABI int getFPMantissaWidth() const

Return the width of the mantissa of this type.

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

void setOperand(unsigned i, Value *Val)

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

Replace uses of one Value with another.

Value * getOperand(unsigned i) const

LLVM Value Representation.

Type * getType() const

All values are typed, get the type 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.

iterator_range< use_iterator > uses()

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

const ParentTy * getParent() const

self_iterator getIterator()

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

BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)

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

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

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

specificval_ty m_Specific(const Value *V)

Match if we have a specific specified value.

IntrinsicID_match m_Intrinsic()

Match intrinsic calls like this: m_IntrinsicIntrinsic::fabs(m_Value(X))

match_combine_or< CastInst_match< OpTy, SExtInst >, NNegZExt_match< OpTy > > m_SExtLike(const OpTy &Op)

Match either "sext" or "zext nneg".

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)

BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)

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

BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)

@ User

could "use" a pointer

NodeAddr< DefNode * > Def

NodeAddr< UseNode * > Use

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

decltype(auto) dyn_cast(const From &Val)

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

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

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.

Definition SimplifyIndVar.cpp:2282

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

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

LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)

Return true if V is poison given that ValAssumedPoison is already poison.

LLVM_ABI raw_ostream & dbgs()

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

LLVM_ABI cl::opt< unsigned > SCEVCheapExpansionBudget

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

SimplifyLoopIVs - Simplify users of induction variables within this loop.

Definition SimplifyIndVar.cpp:1035

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

LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key

LLVM_ABI bool replaceAllDbgUsesWith(Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT)

Point debug users of From to To or salvage them.

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

Definition SimplifyIndVar.cpp:1022

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

DWARFExpression::Operation Op

constexpr unsigned BitWidth

LLVM_ABI bool formLCSSAForInstructions(SmallVectorImpl< Instruction * > &Worklist, const DominatorTree &DT, const LoopInfo &LI, ScalarEvolution *SE, SmallVectorImpl< PHINode * > *PHIsToRemove=nullptr, SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)

Ensures LCSSA form for every instruction from the Worklist in the scope of innermost containing loop.

decltype(auto) cast(const From &Val)

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

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

Implement std::swap in terms of BitVector swap.

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