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");

48namespace {

53 class SimplifyIndvar {

62 bool Changed = false;

63 bool RunUnswitching = false;

65 public:

71 DeadInsts(Dead) {

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

73 }

75 bool hasChanged() const { return Changed; }

76 bool runUnswitching() const { return RunUnswitching; }

86 &SimpleIVUsers);

91 bool replaceIVUserWithLoopInvariant(Instruction *UseInst);

92 bool replaceFloatIVWithIntegerIV(Instruction *UseInst);

95 bool eliminateSaturatingIntrinsic(SaturatingInst *SI);

96 bool eliminateTrunc(TruncInst *TI);

101 bool IsSigned);

103 void replaceRemWithNumeratorOrZero(BinaryOperator *Rem);

107 bool strengthenOverflowingOperation(BinaryOperator *OBO,

110 };

111}

112

113

114

115

119 for (auto *Insn : Instructions)

120 CommonDom =

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

123 return CommonDom;

124}

125

126

127

128

129

130

131

132

133

135 Value *IVSrc = nullptr;

136 const unsigned OperIdx = 0;

137 const SCEV *FoldedExpr = nullptr;

138 bool MustDropExactFlag = false;

140 default:

141 return nullptr;

142 case Instruction::UDiv:

143 case Instruction::LShr:

144

145

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

147 !isa(UseInst->getOperand(1)))

148 return nullptr;

149

150

151

152 if (!isa(IVOperand)

153 || !isa(IVOperand->getOperand(1)))

154 return nullptr;

155

157

158 assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");

159

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

162

165 return nullptr;

166

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

169 }

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

171 const SCEV *RHS = SE->getSCEV(D);

172 FoldedExpr = SE->getUDivExpr(LHS, RHS);

173

174

175 if (UseInst->isExact() && LHS != SE->getMulExpr(FoldedExpr, RHS))

176 MustDropExactFlag = true;

177 }

178

179 if (!SE->isSCEVable(UseInst->getType()))

180 return nullptr;

181

182

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

184 return nullptr;

185

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

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

188

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

191

192 if (MustDropExactFlag)

194

195 ++NumElimOperand;

196 Changed = true;

198 DeadInsts.emplace_back(IVOperand);

199 return IVSrc;

200}

201

202bool SimplifyIndvar::makeIVComparisonInvariant(ICmpInst *ICmp,

204 auto *Preheader = L->getLoopPreheader();

205 if (!Preheader)

206 return false;

207 unsigned IVOperIdx = 0;

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

210

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

212 IVOperIdx = 1;

213 Pred = ICmpInst::getSwappedPredicate(Pred);

214 }

215

216

217

218 const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());

219 const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);

220 const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);

221 auto LIP = SE->getLoopInvariantPredicate(Pred, S, X, L, ICmp);

222 if (!LIP)

223 return false;

225 const SCEV *InvariantLHS = LIP->LHS;

226 const SCEV *InvariantRHS = LIP->RHS;

227

228

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

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

232 Rewriter .isSafeToExpandAt(InvariantLHS, PHTerm) ||

233 Rewriter .isSafeToExpandAt(InvariantRHS, PHTerm))

234 return false;

235 auto *NewLHS =

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

237 auto *NewRHS =

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

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

243 RunUnswitching = true;

244 return true;

245}

246

247

248

249void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp,

251 unsigned IVOperIdx = 0;

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

255

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

257 IVOperIdx = 1;

258 Pred = ICmpInst::getSwappedPredicate(Pred);

259 }

260

261

262

263 const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());

264 const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);

265 const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);

266

267

268

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

271 Users.push_back(cast(U));

273 if (auto Ev = SE->evaluatePredicateAt(Pred, S, X, CtxI)) {

274 SE->forgetValue(ICmp);

276 DeadInsts.emplace_back(ICmp);

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

278 } else if (makeIVComparisonInvariant(ICmp, IVOperand)) {

279

280 } else if (ICmpInst::isSigned(OriginalPred) &&

281 SE->isKnownNonNegative(S) && SE->isKnownNonNegative(X)) {

282

283

284

285

286

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

288 LLVM_DEBUG(dbgs() << "INDVARS: Turn to unsigned comparison: " << *ICmp

289 << '\n');

291 } else

292 return;

293

294 ++NumElimCmp;

295 Changed = true;

296}

297

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

299

302

303

305 N = SE->getSCEVAtScope(N, L);

306 D = SE->getSCEVAtScope(D, L);

307

308

309 if (SE->isKnownNonNegative(N) && SE->isKnownNonNegative(D)) {

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

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

317 ++NumSimplifiedSDiv;

318 Changed = true;

319 DeadInsts.push_back(SDiv);

320 return true;

321 }

322

323 return false;

324}

325

326

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

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

334 ++NumSimplifiedSRem;

335 Changed = true;

336 DeadInsts.emplace_back(Rem);

337}

338

339

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

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

343 ++NumElimRem;

344 Changed = true;

345 DeadInsts.emplace_back(Rem);

346}

347

348

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

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

358 ++NumElimRem;

359 Changed = true;

360 DeadInsts.emplace_back(Rem);

361}

362

363

364

365void SimplifyIndvar::simplifyIVRemainder(BinaryOperator *Rem,

367 bool IsSigned) {

370

371

372

373 bool UsedAsNumerator = IVOperand == NValue;

374 if (!UsedAsNumerator && !IsSigned)

375 return;

376

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

378

379

380 const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());

381 N = SE->getSCEVAtScope(N, ICmpLoop);

382

383 bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(N);

384

385

386 if (!IsNumeratorNonNegative)

387 return;

388

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

390 D = SE->getSCEVAtScope(D, ICmpLoop);

391

392 if (UsedAsNumerator) {

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

394 if (SE->isKnownPredicate(LT, N, D)) {

395 replaceRemWithNumerator(Rem);

396 return;

397 }

398

400 const SCEV *NLessOne = SE->getMinusSCEV(N, SE->getOne(T));

401 if (SE->isKnownPredicate(LT, NLessOne, D)) {

402 replaceRemWithNumeratorOrZero(Rem);

403 return;

404 }

405 }

406

407

408

409 if (!IsSigned || !SE->isKnownNonNegative(D))

410 return;

411

412 replaceSRemWithURem(Rem);

413}

414

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

419 return false;

420

421

422

423

426

429 else

431

433

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

435 if (auto *EVI = dyn_cast(U)) {

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

438 else {

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

440 EVI->replaceAllUsesWith(NewResult);

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

442 }

444 }

445 }

446

447 for (auto *EVI : ToDelete)

448 EVI->eraseFromParent();

449

452

453 Changed = true;

454 return true;

455}

456

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

458 const SCEV *LHS = SE->getSCEV(SI->getLHS());

459 const SCEV *RHS = SE->getSCEV(SI->getRHS());

460 if (!SE->willNotOverflow(SI->getBinaryOp(), SI->isSigned(), LHS, RHS))

461 return false;

462

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

465 if (SI->isSigned())

467 else

469

470 SI->replaceAllUsesWith(BO);

472 DeadInsts.emplace_back(SI);

473 Changed = true;

474 return true;

475}

476

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

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

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

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

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

498

499

500

501 bool DoesSExtCollapse = false;

502 bool DoesZExtCollapse = false;

503 if (IVSCEV == SE->getSignExtendExpr(TISCEV, IVTy))

504 DoesSExtCollapse = true;

505 if (IVSCEV == SE->getZeroExtendExpr(TISCEV, IVTy))

506 DoesZExtCollapse = true;

507

508

509

510 if (!DoesSExtCollapse && !DoesZExtCollapse)

511 return false;

512

513

514

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

517

518 if (isa(U) &&

520 continue;

521 ICmpInst *ICI = dyn_cast(U);

522 if (!ICI) return false;

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

526 return false;

527

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

529 return false;

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

531 return false;

532

534 }

535

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

537

539 return true;

540

541 if (!DoesZExtCollapse)

542 return false;

543

545 return true;

546

547

548

549

550 const SCEV *SCEVOP1 = SE->getSCEV(ICI->getOperand(0));

551 const SCEV *SCEVOP2 = SE->getSCEV(ICI->getOperand(1));

552 return SE->isKnownNonNegative(SCEVOP1) && SE->isKnownNonNegative(SCEVOP2);

553 };

554

555 for (auto *ICI : ICmpUsers) {

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

560

561

562

563

564

565

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

568 if (CanUseZExt(ICI)) {

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

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

572 } else {

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

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

576 }

577 bool Changed;

578 L->makeLoopInvariant(Ext, Changed);

579 (void)Changed;

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

582 DeadInsts.emplace_back(ICI);

583 }

584

585

587 DeadInsts.emplace_back(TI);

588 return true;

589}

590

591

592

593

594bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,

596 if (ICmpInst *ICmp = dyn_cast(UseInst)) {

597 eliminateIVComparison(ICmp, IVOperand);

598 return true;

599 }

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

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

603 simplifyIVRemainder(Bin, IVOperand, IsSRem);

604 return true;

605 }

606

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

608 return eliminateSDiv(Bin);

609 }

610

611 if (auto *WO = dyn_cast(UseInst))

612 if (eliminateOverflowIntrinsic(WO))

613 return true;

614

615 if (auto *SI = dyn_cast(UseInst))

616 if (eliminateSaturatingIntrinsic(SI))

617 return true;

618

619 if (auto *TI = dyn_cast(UseInst))

620 if (eliminateTrunc(TI))

621 return true;

622

623 if (eliminateIdentitySCEV(UseInst, IVOperand))

624 return true;

625

626 return false;

627}

628

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

631 return BB->getTerminator();

632

633 return Hint;

634}

635

636

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

638 if (!SE->isSCEVable(I->getType()))

639 return false;

640

641

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

643

644 if (!SE->isLoopInvariant(S, L))

645 return false;

646

647

649 return false;

650

652

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

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

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

656 return false;

657 }

658

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

660 bool NeedToEmitLCSSAPhis = false;

661 if (!LI->replacementPreservesLCSSAForm(I, Invariant))

662 NeedToEmitLCSSAPhis = true;

663

664 I->replaceAllUsesWith(Invariant);

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

667

668 if (NeedToEmitLCSSAPhis) {

670 NeedsLCSSAPhis.push_back(cast(Invariant));

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

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

674 }

675 ++NumFoldedUser;

676 Changed = true;

677 DeadInsts.emplace_back(I);

678 return true;

679}

680

681

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

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

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

685 return false;

686

688

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

690 int MaskBits;

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

692 MaskBits = (int)SE->getSignedRange(IV).getMinSignedBits();

693 else

694 MaskBits = (int)SE->getUnsignedRange(IV).getActiveBits();

696 if (MaskBits <= DestNumSigBits) {

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

698

699 auto *CI = dyn_cast(U);

700 if (!CI)

701 continue;

702

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

705 continue;

706

707 Value *Conv = nullptr;

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

711

712

713 if (SE->getTypeSizeInBits(IVOperand->getType()) >

714 SE->getTypeSizeInBits(CI->getType())) {

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

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

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

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

719 } else {

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

721 }

722 } else

723 Conv = IVOperand;

724

726 DeadInsts.push_back(CI);

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

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

729

730 ++NumFoldedUser;

731 Changed = true;

732 }

733 }

734

735 return Changed;

736}

737

738

739bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,

741 if (!SE->isSCEVable(UseInst->getType()) ||

743 return false;

744

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

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

747 return false;

748

749

750

751

752

753

754

755

756

757

758

759

760

761

762

763

764

765 if (isa(UseInst))

766

767

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

769 return false;

770

771 if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))

772 return false;

773

774

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

778 return false;

779

780 for (Instruction *I : DropPoisonGeneratingInsts)

781 I->dropPoisonGeneratingAnnotations();

782 }

783

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

785

786 SE->forgetValue(UseInst);

788 ++NumElimIdentity;

789 Changed = true;

790 DeadInsts.emplace_back(UseInst);

791 return true;

792}

793

794bool SimplifyIndvar::strengthenBinaryOp(BinaryOperator *BO,

796 return (isa(BO) &&

797 strengthenOverflowingOperation(BO, IVOperand)) ||

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

799}

800

801

802

803bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,

805 auto Flags = SE->getStrengthenedNoWrapFlagsFromBinOp(

806 cast(BO));

807

808 if (!Flags)

809 return false;

810

815

816

817

818

819

820

821 return true;

822}

823

824

825

826

827bool SimplifyIndvar::strengthenRightShift(BinaryOperator *BO,

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

830 bool Changed = false;

831 ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));

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

841 Changed = true;

842 }

843 }

844 }

845 return Changed;

846 }

847

848 return false;

849}

850

851

852void SimplifyIndvar::pushIVUsers(

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

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

857

858

859

860

861

862 if (UI == Def)

863 continue;

864

865

866

867 if (->contains(UI))

868 continue;

869

870

872 continue;

873

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

875 }

876}

877

878

879

880

881

882

883

886 return false;

887

888

890

891

892 const SCEVAddRecExpr *AR = dyn_cast(S);

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

894 return true;

895

896 return false;

897}

898

899

900

901

902

903

904

905

906

907

908

909

910

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

912 if (!SE->isSCEVable(CurrIV->getType()))

913 return;

914

915

917

918

920

921

922

923

924 pushIVUsers(CurrIV, Simplified, SimpleIVUsers);

925

926 while (!SimpleIVUsers.empty()) {

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

930

931

932

933

934

936 DeadInsts.emplace_back(UseInst);

937 continue;

938 }

939

940

941 if (UseInst == CurrIV) continue;

942

943

944

945 if (replaceIVUserWithLoopInvariant(UseInst))

946 continue;

947

948

949

950 if ((isa(UseInst)) || (isa(UseInst)))

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

953 if (replaceIVUserWithLoopInvariant(User))

954 break;

955 }

956

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

960 (void) N;

961

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

963 if (!NewOper)

964 break;

965 IVOperand = dyn_cast(NewOper);

966 }

967 if (!IVOperand)

968 continue;

969

970 if (eliminateIVUser(UseInst, IVOperand)) {

971 pushIVUsers(IVOperand, Simplified, SimpleIVUsers);

972 continue;

973 }

974

975 if (BinaryOperator *BO = dyn_cast(UseInst)) {

976 if (strengthenBinaryOp(BO, IVOperand)) {

977

978

979 pushIVUsers(IVOperand, Simplified, SimpleIVUsers);

980 }

981 }

982

983

984 if (replaceFloatIVWithIntegerIV(UseInst)) {

985

986 pushIVUsers(IVOperand, Simplified, SimpleIVUsers);

987 continue;

988 }

989

990 CastInst *Cast = dyn_cast(UseInst);

991 if (V && Cast) {

992 V->visitCast(Cast);

993 continue;

994 }

996 pushIVUsers(UseInst, Simplified, SimpleIVUsers);

997 }

998 }

999}

1000

1001namespace llvm {

1002

1004

1005

1006

1007

1008

1009

1017 SIV.simplifyUsers(CurrIV, V);

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

1019}

1020

1021

1022

1027#if LLVM_ENABLE_ABI_BREAKING_CHECKS

1029#endif

1030 bool Changed = false;

1032 const auto &[C, _] =

1034 Changed |= C;

1035 }

1036 return Changed;

1037}

1038

1039}

1040

1041namespace {

1042

1043

1044

1045

1046

1048

1050 Type *WideType;

1051

1052

1057

1058

1059

1060 bool HasGuards;

1061

1062 bool UsePostIncrementRanges;

1063

1064

1065 unsigned NumElimExt = 0;

1066 unsigned NumWidened = 0;

1067

1068

1069 PHINode *WidePhi = nullptr;

1071 const SCEV *WideIncExpr = nullptr;

1073

1075

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

1077

1078

1079

1080

1081

1083

1085

1086

1087

1088

1089

1091

1092 std::optional getPostIncRangeInfo(Value *Def,

1094 DefUserPair Key(Def, UseI);

1095 auto It = PostIncRangeInfos.find(Key);

1096 return It == PostIncRangeInfos.end()

1097 ? std::optional(std::nullopt)

1099 }

1100

1101 void calculatePostIncRanges(PHINode *OrigPhi);

1103

1105 DefUserPair Key(Def, UseI);

1107 if (!Inserted)

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

1109 }

1110

1111public:

1112

1113

1114

1115 struct NarrowIVDefUse {

1119

1120

1121

1122

1123 bool NeverNegative = false;

1124

1126 bool NeverNegative)

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

1128 NeverNegative(NeverNegative) {}

1129 };

1130

1133 bool HasGuards, bool UsePostIncrementRanges = true);

1134

1136

1137 unsigned getNumElimExt() { return NumElimExt; };

1138 unsigned getNumWidened() { return NumWidened; };

1139

1140protected:

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

1143

1145 Instruction *cloneArithmeticIVUser(NarrowIVDefUse DU,

1147 Instruction *cloneBitwiseIVUser(NarrowIVDefUse DU);

1148

1150

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

1152

1153 WidenedRecTy getWideRecurrence(NarrowIVDefUse DU);

1154

1155 WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU);

1156

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

1158 unsigned OpCode) const;

1159

1162 void truncateIVUse(NarrowIVDefUse DU);

1163

1164 bool widenLoopCompare(NarrowIVDefUse DU);

1165 bool widenWithVariantUse(NarrowIVDefUse DU);

1166

1168

1169private:

1171};

1172}

1173

1174

1175

1176

1177

1178

1179

1183 if ( PHI )

1184 return User;

1185

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

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

1189 continue;

1190

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

1192

1194 continue;

1195

1196 if (!InsertPt) {

1198 continue;

1199 }

1202 }

1203

1204

1205

1206 if (!InsertPt)

1207 return nullptr;

1208

1209 auto *DefI = dyn_cast(Def);

1210 if (!DefI)

1211 return InsertPt;

1212

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

1214

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

1217

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

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

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

1221

1223}

1224

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

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

1231 DeadInsts(DI) {

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

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

1234}

1235

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

1238

1240

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

1243 L = L->getParentLoop())

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

1245

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

1247 Builder.CreateZExt(NarrowOper, WideType);

1248}

1249

1250

1251

1252

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

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

1256 switch (Opcode) {

1257 default:

1258 return nullptr;

1259 case Instruction::Add:

1260 case Instruction::Mul:

1261 case Instruction::UDiv:

1262 case Instruction::Sub:

1263 return cloneArithmeticIVUser(DU, WideAR);

1264

1265 case Instruction::And:

1266 case Instruction::Or:

1267 case Instruction::Xor:

1268 case Instruction::Shl:

1269 case Instruction::LShr:

1270 case Instruction::AShr:

1271 return cloneBitwiseIVUser(DU);

1272 }

1273}

1274

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

1279

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

1281

1282

1283

1284

1285

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

1288 ? WideDef

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

1290 IsSigned, NarrowUse);

1292 ? WideDef

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

1294 IsSigned, NarrowUse);

1295

1296 auto *NarrowBO = cast(NarrowUse);

1298 NarrowBO->getName());

1300 Builder.Insert(WideBO);

1301 WideBO->copyIRFlags(NarrowBO);

1302 return WideBO;

1303}

1304

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

1310

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

1312

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

1314

1315

1316

1317

1318

1319

1320

1321

1322

1323

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

1325 const SCEV *WideLHS;

1326 const SCEV *WideRHS;

1327

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

1329 if (SignExt)

1332 };

1333

1334 if (IVOpIdx == 0) {

1335 WideLHS = SE->getSCEV(WideDef);

1337 WideRHS = GetExtend(NarrowRHS, WideType);

1338 } else {

1340 WideLHS = GetExtend(NarrowLHS, WideType);

1341 WideRHS = SE->getSCEV(WideDef);

1342 }

1343

1344

1345 const SCEV *WideUse =

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

1347

1348 return WideUse == WideAR;

1349 };

1350

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

1352 if (!GuessNonIVOperand(SignExtend)) {

1353 SignExtend = !SignExtend;

1354 if (!GuessNonIVOperand(SignExtend))

1355 return nullptr;

1356 }

1357

1359 ? WideDef

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

1361 SignExtend, NarrowUse);

1363 ? WideDef

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

1365 SignExtend, NarrowUse);

1366

1367 auto *NarrowBO = cast(NarrowUse);

1369 NarrowBO->getName());

1370

1372 Builder.Insert(WideBO);

1373 WideBO->copyIRFlags(NarrowBO);

1374 return WideBO;

1375}

1376

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

1378 auto It = ExtendKindMap.find(I);

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

1380 return It->second;

1381}

1382

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

1384 unsigned OpCode) const {

1385 switch (OpCode) {

1386 case Instruction::Add:

1388 case Instruction::Sub:

1390 case Instruction::Mul:

1392 case Instruction::UDiv:

1394 default:

1396 };

1397}

1398

1399namespace {

1400

1401

1402

1403

1404struct BinaryOp {

1405 unsigned Opcode;

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

1407 bool IsNSW = false;

1408 bool IsNUW = false;

1409

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

1413 if (auto *OBO = dyn_cast(Op)) {

1414 IsNSW = OBO->hasNoSignedWrap();

1415 IsNUW = OBO->hasNoUnsignedWrap();

1416 }

1417 }

1418

1420 bool IsNSW = false, bool IsNUW = false)

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

1422};

1423

1424}

1425

1427 switch (Op->getOpcode()) {

1428 case Instruction::Add:

1429 case Instruction::Sub:

1430 case Instruction::Mul:

1431 return BinaryOp(Op);

1432 case Instruction::Or: {

1433

1434 if (cast(Op)->isDisjoint())

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

1436 true, true);

1437 break;

1438 }

1439 case Instruction::Shl: {

1440 if (ConstantInt *SA = dyn_cast(Op->getOperand(1))) {

1441 unsigned BitWidth = cast(SA->getType())->getBitWidth();

1442

1443

1444

1445

1446

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

1448

1449

1450

1451

1452 bool IsNUW = Op->hasNoUnsignedWrap();

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

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

1455

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

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

1460 }

1461 }

1462

1463 break;

1464 }

1465 }

1466

1467 return std::nullopt;

1468}

1469

1470

1471

1472

1473

1474

1475WidenIV::WidenedRecTy

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

1478 if ()

1479 return {nullptr, ExtendKind::Unknown};

1480

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

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

1483 "Unexpected opcode");

1484

1485

1486

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

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

1489

1490 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);

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

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

1493 ExtKind = ExtendKind::Unknown;

1494

1495

1496

1497

1498

1499 if (DU.NeverNegative) {

1500 if (Op->IsNSW) {

1501 ExtKind = ExtendKind::Sign;

1502 } else if (Op->IsNUW) {

1503 ExtKind = ExtendKind::Zero;

1504 }

1505 }

1506 }

1507

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

1509 if (ExtKind == ExtendKind::Sign)

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

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

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

1513 else

1514 return {nullptr, ExtendKind::Unknown};

1515

1516

1517

1518

1519

1520

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

1522 const SCEV *rhs = ExtendOperExpr;

1523

1524

1525

1526 if (ExtendOperIdx == 0)

1529 dyn_cast(getSCEVByOpCode(lhs, rhs, Op->Opcode));

1530

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

1532 return {nullptr, ExtendKind::Unknown};

1533

1534 return {AddRec, ExtKind};

1535}

1536

1537

1538

1539

1540

1541

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

1543 if (!DU.NarrowUse->getType()->isIntegerTy())

1544 return {nullptr, ExtendKind::Unknown};

1545

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

1549

1550

1551 return {nullptr, ExtendKind::Unknown};

1552 }

1553

1554 const SCEV *WideExpr;

1555 ExtendKind ExtKind;

1556 if (DU.NeverNegative) {

1558 if (isa(WideExpr))

1559 ExtKind = ExtendKind::Sign;

1560 else {

1562 ExtKind = ExtendKind::Zero;

1563 }

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

1566 ExtKind = ExtendKind::Sign;

1567 } else {

1569 ExtKind = ExtendKind::Zero;

1570 }

1571 const SCEVAddRecExpr *AddRec = dyn_cast(WideExpr);

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

1573 return {nullptr, ExtendKind::Unknown};

1574 return {AddRec, ExtKind};

1575}

1576

1577

1578

1579void WidenIV::truncateIVUse(NarrowIVDefUse DU) {

1581 if (!InsertPt)

1582 return;

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

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

1585 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);

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

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

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

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

1592}

1593

1594

1595

1596

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

1598 ICmpInst *Cmp = dyn_cast(DU.NarrowUse);

1599 if (!Cmp)

1600 return false;

1601

1602

1603

1604

1605

1606

1607

1608

1609

1610

1611

1612

1613

1614

1615

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

1617 if (!(DU.NeverNegative || IsSigned == Cmp->isSigned()))

1618 return false;

1619

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

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

1624

1625

1626 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);

1627

1628

1629 if (CastWidth < IVWidth) {

1630 Value *ExtOp = createExtendInst(Op, WideType, Cmp->isSigned(), Cmp);

1631 DU.NarrowUse->replaceUsesOfWith(Op, ExtOp);

1632 }

1633 return true;

1634}

1635

1636

1637

1638

1639

1640

1641

1642

1643

1644

1645

1646

1647

1648

1649

1650

1651

1652

1653

1654

1655

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

1660

1661

1663

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

1665 OpCode != Instruction::Mul)

1666 return false;

1667

1668

1669

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

1672 "bad DU");

1673

1675 cast(NarrowUse);

1676 ExtendKind ExtKind = getExtendKind(NarrowDef);

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

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

1679 auto AnotherOpExtKind = ExtKind;

1680

1681

1682

1683

1684

1685

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

1691 if (User == NarrowDef)

1692 continue;

1693 if (->contains(User)) {

1694 auto *LCSSAPhi = cast(User);

1695

1696

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

1698 return false;

1699 LCSSAPhiUsers.push_back(LCSSAPhi);

1700 continue;

1701 }

1702 if (auto *ICmp = dyn_cast(User)) {

1704

1705

1706

1707

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

1709 return false;

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

1711 return false;

1713 continue;

1714 }

1715 if (ExtKind == ExtendKind::Sign)

1716 User = dyn_cast(User);

1717 else

1718 User = dyn_cast(User);

1720 return false;

1722 }

1723 if (ExtUsers.empty()) {

1725 return true;

1726 }

1727

1728

1729

1730

1732

1733 if (!CanSignExtend && !CanZeroExtend) {

1734

1735

1736 if (OpCode != Instruction::Add)

1737 return false;

1738 if (ExtKind != ExtendKind::Zero)

1739 return false;

1742

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

1744 return false;

1746 return false;

1749 if (!ProvedSubNUW)

1750 return false;

1751

1752

1753 AnotherOpExtKind = ExtendKind::Sign;

1754 }

1755

1756

1758 const SCEVAddRecExpr *AddRecOp1 = dyn_cast(Op1);

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

1760 return false;

1761

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

1763

1764

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

1767 ? WideDef

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

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

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

1772 ? WideDef

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

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

1775

1776 auto *NarrowBO = cast(NarrowUse);

1778 NarrowBO->getName());

1780 Builder.Insert(WideBO);

1781 WideBO->copyIRFlags(NarrowBO);

1782 ExtendKindMap[NarrowUse] = ExtKind;

1783

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

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

1788 ++NumElimExt;

1791 }

1792

1795 Builder.SetInsertPoint(User);

1796 auto *WidePN =

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

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

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

1800 "Not a LCSSA Phi?");

1801 WidePN->addIncoming(WideBO, LoopExitingBlock);

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

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

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

1807 }

1808

1810 Builder.SetInsertPoint(User);

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

1812 if (V == NarrowUse)

1813 return WideBO;

1814 if (ExtKind == ExtendKind::Zero)

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

1816 else

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

1818 };

1819 auto Pred = User->getPredicate();

1822 auto *WideCmp =

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

1826 }

1827

1828 return true;

1829}

1830

1831

1832

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

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

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

1838

1839

1840

1841 bool CanWidenBySExt =

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

1843 bool CanWidenByZExt =

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

1845

1846

1847 if (PHINode *UsePhi = dyn_cast(DU.NarrowUse)) {

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

1849

1850

1851

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

1853 truncateIVUse(DU);

1854 else {

1855

1856

1857

1858 if (isa(UsePhi->getParent()->getTerminator()))

1859 return nullptr;

1860

1862 PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() + ".wide",

1863 UsePhi->getIterator());

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

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

1868 CanWidenByZExt, CanWidenBySExt);

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

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

1873 }

1874 return nullptr;

1875 }

1876 }

1877

1878

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

1881 Value *NewDef = DU.WideDef;

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

1883 unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType());

1885 if (CastWidth < IVWidth) {

1886

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

1889 CanWidenByZExt, CanWidenBySExt);

1890 }

1891 else {

1892

1893

1894

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

1897 << "\n");

1898 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);

1899 NewDef = DU.NarrowUse;

1900 }

1901 }

1902 if (NewDef != DU.NarrowUse) {

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

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

1905 ++NumElimExt;

1906 DU.NarrowUse->replaceAllUsesWith(NewDef);

1908 }

1909

1910

1911

1912

1913

1914

1915

1916 return nullptr;

1917 }

1918

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

1920

1921 WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);

1922 if (!WideAddRec.first)

1923 WideAddRec = getWideRecurrence(DU);

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

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

1926 if (!WideAddRec.first)

1927 return nullptr;

1928

1929 auto CanUseWideInc = [&]() {

1930 if (!WideInc)

1931 return false;

1932

1933

1934

1935

1936 bool NeedToRecomputeFlags =

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

1939 DU.NarrowUse->hasNoUnsignedWrap() != WideInc->hasNoUnsignedWrap() ||

1940 DU.NarrowUse->hasNoSignedWrap() != WideInc->hasNoSignedWrap();

1941 return WideAddRec.first == WideIncExpr &&

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

1943 };

1944

1946 if (CanUseWideInc())

1947 WideUse = WideInc;

1948 else {

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

1950 if (!WideUse)

1951 return nullptr;

1952 }

1953

1954

1955

1956

1957

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

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

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

1961 << "\n");

1963 return nullptr;

1964 };

1965

1966

1967

1969

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

1971

1972 return WideUse;

1973 };

1974

1975 if (auto *I = tryAddRecExpansion())

1976 return I;

1977

1978

1979

1980 if (widenLoopCompare(DU))

1981 return nullptr;

1982

1983

1984

1985

1986

1987

1988 if (widenWithVariantUse(DU))

1989 return nullptr;

1990

1991

1992

1993

1994 truncateIVUse(DU);

1995 return nullptr;

1996}

1997

1998

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

2001 bool NonNegativeDef =

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

2005 Instruction *NarrowUser = cast(U);

2006

2007

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

2009 continue;

2010

2011 bool NonNegativeUse = false;

2012 if (!NonNegativeDef) {

2013

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

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

2016 }

2017

2018 NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef,

2019 NonNegativeDef || NonNegativeUse);

2020 }

2021}

2022

2023

2024

2025

2026

2027

2028

2029

2030

2032

2034 if (!AddRec)

2035 return nullptr;

2036

2037

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

2041

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

2044

2045

2046 AddRec = dyn_cast(WideIVExpr);

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

2048 return nullptr;

2049

2050

2051

2052

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

2057

2058

2059

2060

2061

2062

2063

2064

2065

2066

2067

2069 calculatePostIncRanges(OrigPhi);

2070

2071

2072

2073

2074

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

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

2077

2078

2079 if (!(WidePhi = dyn_cast(ExpandInst))) {

2080

2081

2082

2083 if (ExpandInst->hasNUses(0) &&

2084 Rewriter.isInsertedInstruction(cast(ExpandInst)))

2086 return nullptr;

2087 }

2088

2089

2090

2091

2092

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

2094 WideInc =

2096 if (WideInc) {

2097 WideIncExpr = SE->getSCEV(WideInc);

2098

2099

2100 auto *OrigInc =

2102

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

2104

2105

2106

2107

2108

2109

2110

2111

2112

2114 OrigInc, WideInc) &&

2115 isa(OrigInc) &&

2116 isa(WideInc)) {

2118 OrigInc->hasNoUnsignedWrap());

2120 OrigInc->hasNoSignedWrap());

2121 }

2122 }

2123 }

2124

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

2126 ++NumWidened;

2127

2128

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

2130

2131 Widened.insert(OrigPhi);

2132 pushNarrowIVUsers(OrigPhi, WidePhi);

2133

2134 while (!NarrowIVUsers.empty()) {

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

2136

2137

2138

2139 Instruction *WideUse = widenIVUse(DU, Rewriter, OrigPhi, WidePhi);

2140

2141

2142 if (WideUse)

2143 pushNarrowIVUsers(DU.NarrowUse, WideUse);

2144

2145

2146 if (DU.NarrowDef->use_empty())

2148 }

2149

2150

2152

2153 return WidePhi;

2154}

2155

2156

2157

2158void WidenIV::calculatePostIncRange(Instruction *NarrowDef,

2160 Value *NarrowDefLHS;

2161 const APInt *NarrowDefRHS;

2163 m_APInt(NarrowDefRHS))) ||

2165 return;

2166

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

2172 return;

2173

2175

2177 auto CmpConstrainedLHSRange =

2179 auto NarrowDefRange = CmpConstrainedLHSRange.addWithNoWrap(

2181

2182 updatePostIncRangeInfo(NarrowDef, NarrowUser, NarrowDefRange);

2183 };

2184

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

2186 if (!HasGuards)

2187 return;

2188

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

2192 if (match(&I, m_IntrinsicIntrinsic::experimental\_guard(m_Value(C))))

2193 UpdateRangeFromCondition(C, true);

2194 }

2195 };

2196

2197 UpdateRangeFromGuards(NarrowUser);

2198

2200

2201

2203 return;

2204

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

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

2207 DTB = DTB->getIDom()) {

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

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

2210 UpdateRangeFromGuards(TI);

2211

2212 auto *BI = dyn_cast(TI);

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

2214 continue;

2215

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

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

2218

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

2220 return BBE.isSingleEdge() &&

2222 };

2223

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

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

2226

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

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

2229 }

2230}

2231

2232

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

2237 Visited.insert(OrigPhi);

2238

2239 while (!Worklist.empty()) {

2241

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

2243 auto *NarrowUser = cast(U.getUser());

2244

2245

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

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

2248 continue;

2249

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

2251 continue;

2252

2254

2255 calculatePostIncRange(NarrowDef, NarrowUser);

2256 }

2257 }

2258}

2259

2263 unsigned &NumElimExt, unsigned &NumWidened,

2267 NumElimExt = Widener.getNumElimExt();

2268 NumWidened = Widener.getNumWidened();

2269 return WidePHI;

2270}

SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn

static const Function * getParent(const Value *V)

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

static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")

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

mir Rename Register Operands

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

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

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.

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

Find a point in code which dominates all given instructions.

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

Determine the insertion point for this user.

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

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

Class for arbitrary precision integers.

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

Value handle that asserts if the Value is deleted.

LLVM Basic Block Representation.

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

bool isSigned() const

Whether the intrinsic is signed or unsigned.

Instruction::BinaryOps getBinaryOp() const

Returns the binary operation underlying the intrinsic.

BinaryOps getOpcode() const

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

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

void setPredicate(Predicate P)

Set the predicate for this instruction to the specified value.

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

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

This is the shared class of boolean and integer constants.

static ConstantInt * getFalse(LLVMContext &Context)

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

This class represents a range of values.

APInt getUnsignedMin() const

Return the smallest unsigned value contained in the ConstantRange.

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

This class represents an Operation in the Expression.

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.

bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

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

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

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

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

void setHasNoUnsignedWrap(bool b=true)

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

bool hasNoUnsignedWrap() const LLVM_READONLY

Determine whether the no unsigned wrap flag is set.

bool hasNoSignedWrap() const LLVM_READONLY

Determine whether the no signed wrap flag is set.

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.

InstListType::iterator eraseFromParent()

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

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.

void setIsExact(bool b=true)

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

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.

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

Represents a single loop in the control flow graph.

Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.

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

Type * getType() const

Return the LLVM type of this SCEV expression.

Represents a saturating add/sub intrinsic.

The main scalar evolution driver.

const DataLayout & getDataLayout() const

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

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

Return the SCEV object corresponding to -V.

bool isKnownNegative(const SCEV *S)

Test if the given expression is known to be negative.

const SCEV * getZero(Type *Ty)

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

uint64_t getTypeSizeInBits(Type *Ty) const

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

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

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

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

bool isSCEVable(Type *Ty) const

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

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

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

Return LHS-RHS.

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

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

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

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

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 * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)

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

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

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

This class represents the LLVM 'select' instruction.

static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", InsertPosition InsertBefore=nullptr, 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.

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.

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

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

This class represents a truncation of integer types.

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

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)

Value * getOperand(unsigned i) const

unsigned getNumOperands() const

LLVM Value Representation.

Type * getType() const

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

void replaceAllUsesWith(Value *V)

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

iterator_range< user_iterator > users()

bool hasNUses(unsigned N) const

Return true if this Value has exactly N uses.

LLVMContext & getContext() const

All values hold a context through their type.

iterator_range< use_iterator > uses()

StringRef getName() const

Return a constant reference to the value's name.

Represents an op.with.overflow intrinsic.

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.

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

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

specificval_ty m_Specific(const Value *V)

Match if we have a specific specified value.

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

Match either "sext" or "zext nneg".

apint_match m_APInt(const APInt *&Res)

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

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)

NodeAddr< DefNode * > Def

This is an optimization pass for GlobalISel generic memory operations.

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.

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.

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

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

raw_ostream & dbgs()

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

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.

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

constexpr unsigned BitWidth

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.

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.

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