SimplifyIndVar.cpp

1//===-- SimplifyIndVar.cpp - Induction variable simplification ------------===//

2//

3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

4// See https://llvm.org/LICENSE.txt for license information.

5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

6//

7//===----------------------------------------------------------------------===//

8//

9// This file implements induction variable simplification. It does

10// not define any actual pass or policy, but provides a single function to

11// simplify a loop's induction variables based on ScalarEvolution.

12//

13//===----------------------------------------------------------------------===//

14

15#include "llvm/Transforms/Utils/SimplifyIndVar.h"

16#include "llvm/ADT/SmallVector.h"

17#include "llvm/ADT/Statistic.h"

18#include "llvm/Analysis/LoopInfo.h"

19#include "llvm/Analysis/ValueTracking.h"

20#include "llvm/IR/Dominators.h"

21#include "llvm/IR/IRBuilder.h"

22#include "llvm/IR/Instructions.h"

23#include "llvm/IR/IntrinsicInst.h"

24#include "llvm/IR/PatternMatch.h"

25#include "llvm/Support/Debug.h"

26#include "llvm/Support/raw_ostream.h"

27#include "llvm/Transforms/Utils/Local.h"

28#include "llvm/Transforms/Utils/LoopUtils.h"

29#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"

30

31using namespace llvm;

32using namespace llvm::PatternMatch;

33

34 #define DEBUG_TYPE "indvars"

35

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

40 STATISTIC(

41 NumSimplifiedSDiv,

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

43 STATISTIC(

44 NumSimplifiedSRem,

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

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

47

48namespace {

49 /// This is a utility for simplifying induction variables

50 /// based on ScalarEvolution. It is the primary instrument of the

51 /// IndvarSimplify pass, but it may also be directly invoked to cleanup after

52 /// other loop passes that preserve SCEV.

53 class SimplifyIndvar {

54 Loop *L;

55 LoopInfo *LI;

56 ScalarEvolution *SE;

57 DominatorTree *DT;

58 const TargetTransformInfo *TTI;

59 SCEVExpander &Rewriter;

60 SmallVectorImpl<WeakTrackingVH> &DeadInsts;

61

62 bool Changed = false;

63 bool RunUnswitching = false;

64

65 public:

66 SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT,

67 LoopInfo *LI, const TargetTransformInfo *TTI,

68 SCEVExpander &Rewriter,

69 SmallVectorImpl<WeakTrackingVH> &Dead)

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

71 DeadInsts(Dead) {

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

73 }

74

75 bool hasChanged() const { return Changed; }

76 bool runUnswitching() const { return RunUnswitching; }

77

78 /// Iteratively perform simplification on a worklist of users of the

79 /// specified induction variable. This is the top-level driver that applies

80 /// all simplifications to users of an IV.

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

82

83 void pushIVUsers(Instruction *Def,

84 SmallPtrSet<Instruction *, 16> &Simplified,

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

86 &SimpleIVUsers);

87

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

89

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

91 bool replaceIVUserWithLoopInvariant(Instruction *UseInst);

92 bool replaceFloatIVWithIntegerIV(Instruction *UseInst);

93

94 bool eliminateOverflowIntrinsic(WithOverflowInst *WO);

95 bool eliminateSaturatingIntrinsic(SaturatingInst *SI);

96 bool eliminateTrunc(TruncInst *TI);

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

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

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

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

101 bool IsSigned);

102 void replaceRemWithNumerator(BinaryOperator *Rem);

103 void replaceRemWithNumeratorOrZero(BinaryOperator *Rem);

104 void replaceSRemWithURem(BinaryOperator *Rem);

105 bool eliminateSDiv(BinaryOperator *SDiv);

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

107 bool strengthenOverflowingOperation(BinaryOperator *OBO,

108 Instruction *IVOperand);

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

110 };

111}

112

113/// Find a point in code which dominates all given instructions. We can safely

114/// assume that, whatever fact we can prove at the found point, this fact is

115/// also true for each of the given instructions.

116 static Instruction *findCommonDominator(ArrayRef<Instruction *> Instructions,

117 DominatorTree &DT) {

118 Instruction *CommonDom = nullptr;

119 for (auto *Insn : Instructions)

120 CommonDom =

121 CommonDom ? DT.findNearestCommonDominator(CommonDom, Insn) : Insn;

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

123 return CommonDom;

124}

125

126/// Fold an IV operand into its use. This removes increments of an

127/// aligned IV when used by a instruction that ignores the low bits.

128///

129/// IVOperand is guaranteed SCEVable, but UseInst may not be.

130///

131/// Return the operand of IVOperand for this induction variable if IVOperand can

132/// be folded (in case more folding opportunities have been exposed).

133/// Otherwise return null.

134Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {

135 Value *IVSrc = nullptr;

136 const unsigned OperIdx = 0;

137 const SCEV *FoldedExpr = nullptr;

138 bool MustDropExactFlag = false;

139 switch (UseInst->getOpcode()) {

140 default:

141 return nullptr;

142 case Instruction::UDiv:

143 case Instruction::LShr:

144 // We're only interested in the case where we know something about

145 // the numerator and have a constant denominator.

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

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

148 return nullptr;

149

150 // Attempt to fold a binary operator with constant operand.

151 // e.g. ((I + 1) >> 2) => I >> 2

152 if (!isa<BinaryOperator>(IVOperand)

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

154 return nullptr;

155

156 IVSrc = IVOperand->getOperand(0);

157 // IVSrc must be the (SCEVable) IV, since the other operand is const.

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

159

160 ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1));

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

162 // Get a constant for the divisor. See createSCEV.

163 uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();

164 if (D->getValue().uge(BitWidth))

165 return nullptr;

166

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

168 APInt::getOneBitSet(BitWidth, D->getZExtValue()));

169 }

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

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

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

173 // We might have 'exact' flag set at this point which will no longer be

174 // correct after we make the replacement.

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

176 MustDropExactFlag = true;

177 }

178 // We have something that might fold it's operand. Compare SCEVs.

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

180 return nullptr;

181

182 // Bypass the operand if SCEV can prove it has no effect.

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

184 return nullptr;

185

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

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

188

189 UseInst->setOperand(OperIdx, IVSrc);

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

191

192 if (MustDropExactFlag)

193 UseInst->dropPoisonGeneratingFlags();

194

195 ++NumElimOperand;

196 Changed = true;

197 if (IVOperand->use_empty())

198 DeadInsts.emplace_back(IVOperand);

199 return IVSrc;

200}

201

202bool SimplifyIndvar::makeIVComparisonInvariant(ICmpInst *ICmp,

203 Instruction *IVOperand) {

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

205 if (!Preheader)

206 return false;

207 unsigned IVOperIdx = 0;

208 CmpPredicate Pred = ICmp->getCmpPredicate();

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

210 // Swapped

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

212 IVOperIdx = 1;

213 Pred = ICmpInst::getSwappedCmpPredicate(Pred);

214 }

215

216 // Get the SCEVs for the ICmp operands (in the specific context of the

217 // current loop)

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;

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

225 const SCEV *InvariantLHS = LIP->LHS;

226 const SCEV *InvariantRHS = LIP->RHS;

227

228 // Do not generate something ridiculous.

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

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

231 2 * SCEVCheapExpansionBudget, TTI, PHTerm) ||

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

240 ICmp->setPredicate(InvariantPredicate);

241 ICmp->setOperand(0, NewLHS);

242 ICmp->setOperand(1, NewRHS);

243 RunUnswitching = true;

244 return true;

245}

246

247/// SimplifyIVUsers helper for eliminating useless

248/// comparisons against an induction variable.

249void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp,

250 Instruction *IVOperand) {

251 unsigned IVOperIdx = 0;

252 CmpPredicate Pred = ICmp->getCmpPredicate();

253 ICmpInst::Predicate OriginalPred = Pred;

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

255 // Swapped

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

257 IVOperIdx = 1;

258 Pred = ICmpInst::getSwappedCmpPredicate(Pred);

259 }

260

261 // Get the SCEVs for the ICmp operands (in the specific context of the

262 // current loop)

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 // If the condition is always true or always false in the given context,

268 // replace it with a constant value.

269 SmallVector<Instruction *, 4> Users;

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

271 Users.push_back(cast<Instruction>(U));

272 const Instruction *CtxI = findCommonDominator(Users, *DT);

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

274 SE->forgetValue(ICmp);

275 ICmp->replaceAllUsesWith(ConstantInt::getBool(ICmp->getContext(), *Ev));

276 DeadInsts.emplace_back(ICmp);

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

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

279 // fallthrough to end of function

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

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

282 // If we were unable to make anything above, all we can is to canonicalize

283 // the comparison hoping that it will open the doors for other

284 // optimizations. If we find out that we compare two non-negative values,

285 // we turn the instruction's predicate to its unsigned version. Note that

286 // we cannot rely on Pred here unless we check if we have swapped it.

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

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

289 << '\n');

290 ICmp->setPredicate(ICmpInst::getUnsignedPredicate(OriginalPred));

291 ICmp->setSameSign();

292 } else

293 return;

294

295 ++NumElimCmp;

296 Changed = true;

297}

298

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

300 // Get the SCEVs for the ICmp operands.

301 const SCEV *N = SE->getSCEV(SDiv->getOperand(0));

302 const SCEV *D = SE->getSCEV(SDiv->getOperand(1));

303

304 // Simplify unnecessary loops away.

305 const Loop *L = LI->getLoopFor(SDiv->getParent());

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

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

308

309 // Replace sdiv by udiv if both of the operands are non-negative

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

311 auto *UDiv = BinaryOperator::Create(

312 BinaryOperator::UDiv, SDiv->getOperand(0), SDiv->getOperand(1),

313 SDiv->getName() + ".udiv", SDiv->getIterator());

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

315 SDiv->replaceAllUsesWith(UDiv);

316 UDiv->setDebugLoc(SDiv->getDebugLoc());

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

318 ++NumSimplifiedSDiv;

319 Changed = true;

320 DeadInsts.push_back(SDiv);

321 return true;

322 }

323

324 return false;

325}

326

327// i %s n -> i %u n if i >= 0 and n >= 0

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

329 auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);

330 auto *URem = BinaryOperator::Create(BinaryOperator::URem, N, D,

331 Rem->getName() + ".urem", Rem->getIterator());

332 Rem->replaceAllUsesWith(URem);

333 URem->setDebugLoc(Rem->getDebugLoc());

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

335 ++NumSimplifiedSRem;

336 Changed = true;

337 DeadInsts.emplace_back(Rem);

338}

339

340// i % n --> i if i is in [0,n).

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

342 Rem->replaceAllUsesWith(Rem->getOperand(0));

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

344 ++NumElimRem;

345 Changed = true;

346 DeadInsts.emplace_back(Rem);

347}

348

349// (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n).

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

351 auto *T = Rem->getType();

352 auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);

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

354 ICmp->setDebugLoc(Rem->getDebugLoc());

355 SelectInst *Sel =

356 SelectInst::Create(ICmp, ConstantInt::get(T, 0), N, "iv.rem", Rem->getIterator());

357 Rem->replaceAllUsesWith(Sel);

358 Sel->setDebugLoc(Rem->getDebugLoc());

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

360 ++NumElimRem;

361 Changed = true;

362 DeadInsts.emplace_back(Rem);

363}

364

365/// SimplifyIVUsers helper for eliminating useless remainder operations

366/// operating on an induction variable or replacing srem by urem.

367void SimplifyIndvar::simplifyIVRemainder(BinaryOperator *Rem,

368 Instruction *IVOperand,

369 bool IsSigned) {

370 auto *NValue = Rem->getOperand(0);

371 auto *DValue = Rem->getOperand(1);

372 // We're only interested in the case where we know something about

373 // the numerator, unless it is a srem, because we want to replace srem by urem

374 // in general.

375 bool UsedAsNumerator = IVOperand == NValue;

376 if (!UsedAsNumerator && !IsSigned)

377 return;

378

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

380

381 // Simplify unnecessary loops away.

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

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

384

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

386

387 // Do not proceed if the Numerator may be negative

388 if (!IsNumeratorNonNegative)

389 return;

390

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

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

393

394 if (UsedAsNumerator) {

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

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

397 replaceRemWithNumerator(Rem);

398 return;

399 }

400

401 auto *T = Rem->getType();

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

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

404 replaceRemWithNumeratorOrZero(Rem);

405 return;

406 }

407 }

408

409 // Try to replace SRem with URem, if both N and D are known non-negative.

410 // Since we had already check N, we only need to check D now

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

412 return;

413

414 replaceSRemWithURem(Rem);

415}

416

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

418 const SCEV *LHS = SE->getSCEV(WO->getLHS());

419 const SCEV *RHS = SE->getSCEV(WO->getRHS());

420 if (!SE->willNotOverflow(WO->getBinaryOp(), WO->isSigned(), LHS, RHS))

421 return false;

422

423 // Proved no overflow, nuke the overflow check and, if possible, the overflow

424 // intrinsic as well.

425

426 BinaryOperator *NewResult = BinaryOperator::Create(

427 WO->getBinaryOp(), WO->getLHS(), WO->getRHS(), "", WO->getIterator());

428

429 if (WO->isSigned())

430 NewResult->setHasNoSignedWrap(true);

431 else

432 NewResult->setHasNoUnsignedWrap(true);

433

434 SmallVector<ExtractValueInst *, 4> ToDelete;

435

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

437 if (auto *EVI = dyn_cast<ExtractValueInst>(U)) {

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

439 EVI->replaceAllUsesWith(ConstantInt::getFalse(WO->getContext()));

440 else {

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

442 EVI->replaceAllUsesWith(NewResult);

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

444 }

445 ToDelete.push_back(EVI);

446 }

447 }

448

449 for (auto *EVI : ToDelete)

450 EVI->eraseFromParent();

451

452 if (WO->use_empty())

453 WO->eraseFromParent();

454

455 Changed = true;

456 return true;

457}

458

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

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

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

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

463 return false;

464

465 BinaryOperator *BO = BinaryOperator::Create(

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

467 if (SI->isSigned())

468 BO->setHasNoSignedWrap();

469 else

470 BO->setHasNoUnsignedWrap();

471

472 SI->replaceAllUsesWith(BO);

473 BO->setDebugLoc(SI->getDebugLoc());

474 DeadInsts.emplace_back(SI);

475 Changed = true;

476 return true;

477}

478

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

480 // It is always legal to replace

481 // icmp <pred> i32 trunc(iv), n

482 // with

483 // icmp <pred> i64 sext(trunc(iv)), sext(n), if pred is signed predicate.

484 // Or with

485 // icmp <pred> i64 zext(trunc(iv)), zext(n), if pred is unsigned predicate.

486 // Or with either of these if pred is an equality predicate.

487 //

488 // If we can prove that iv == sext(trunc(iv)) or iv == zext(trunc(iv)) for

489 // every comparison which uses trunc, it means that we can replace each of

490 // them with comparison of iv against sext/zext(n). We no longer need trunc

491 // after that.

492 //

493 // TODO: Should we do this if we can widen *some* comparisons, but not all

494 // of them? Sometimes it is enough to enable other optimizations, but the

495 // trunc instruction will stay in the loop.

496 Value *IV = TI->getOperand(0);

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

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

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

500

501 // Check if iv == zext(trunc(iv)) and if iv == sext(trunc(iv)). If so, we can

502 // get rid of trunc

503 bool DoesSExtCollapse = false;

504 bool DoesZExtCollapse = false;

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

506 DoesSExtCollapse = true;

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

508 DoesZExtCollapse = true;

509

510 // If neither sext nor zext does collapse, it is not profitable to do any

511 // transform. Bail.

512 if (!DoesSExtCollapse && !DoesZExtCollapse)

513 return false;

514

515 // Collect users of the trunc that look like comparisons against invariants.

516 // Bail if we find something different.

517 SmallVector<ICmpInst *, 4> ICmpUsers;

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

519 // We don't care about users in unreachable blocks.

520 if (isa<Instruction>(U) &&

521 !DT->isReachableFromEntry(cast<Instruction>(U)->getParent()))

522 continue;

523 ICmpInst *ICI = dyn_cast<ICmpInst>(U);

524 if (!ICI) return false;

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

526 if (!(ICI->getOperand(0) == TI && L->isLoopInvariant(ICI->getOperand(1))) &&

527 !(ICI->getOperand(1) == TI && L->isLoopInvariant(ICI->getOperand(0))))

528 return false;

529 // If we cannot get rid of trunc, bail.

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

531 return false;

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

533 return false;

534 // For equality, either signed or unsigned works.

535 ICmpUsers.push_back(ICI);

536 }

537

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

539 // Unsigned comparison can be widened as unsigned.

540 if (ICI->isUnsigned())

541 return true;

542 // Is it profitable to do zext?

543 if (!DoesZExtCollapse)

544 return false;

545 // For equality, we can safely zext both parts.

546 if (ICI->isEquality())

547 return true;

548 // Otherwise we can only use zext when comparing two non-negative or two

549 // negative values. But in practice, we will never pass DoesZExtCollapse

550 // check for a negative value, because zext(trunc(x)) is non-negative. So

551 // it only make sense to check for non-negativity here.

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

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

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

555 };

556 // Replace all comparisons against trunc with comparisons against IV.

557 for (auto *ICI : ICmpUsers) {

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

559 auto *Op1 = IsSwapped ? ICI->getOperand(0) : ICI->getOperand(1);

560 IRBuilder<> Builder(ICI);

561 Value *Ext = nullptr;

562 // For signed/unsigned predicate, replace the old comparison with comparison

563 // of immediate IV against sext/zext of the invariant argument. If we can

564 // use either sext or zext (i.e. we are dealing with equality predicate),

565 // then prefer zext as a more canonical form.

566 // TODO: If we see a signed comparison which can be turned into unsigned,

567 // we can do it here for canonicalization purposes.

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

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

570 if (CanUseZExt(ICI)) {

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

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

573 Pred = ICmpInst::getUnsignedPredicate(Pred);

574 } else {

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

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

577 assert(Pred == ICmpInst::getSignedPredicate(Pred) && "Must be signed!");

578 }

579 bool Changed;

580 L->makeLoopInvariant(Ext, Changed);

581 (void)Changed;

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

583 ICI->replaceAllUsesWith(NewCmp);

584 DeadInsts.emplace_back(ICI);

585 }

586

587 // Trunc no longer needed.

588 TI->replaceAllUsesWith(PoisonValue::get(TI->getType()));

589 DeadInsts.emplace_back(TI);

590 return true;

591}

592

593/// Eliminate an operation that consumes a simple IV and has no observable

594/// side-effect given the range of IV values. IVOperand is guaranteed SCEVable,

595/// but UseInst may not be.

596bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,

597 Instruction *IVOperand) {

598 if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {

599 eliminateIVComparison(ICmp, IVOperand);

600 return true;

601 }

602 if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(UseInst)) {

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

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

605 simplifyIVRemainder(Bin, IVOperand, IsSRem);

606 return true;

607 }

608

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

610 return eliminateSDiv(Bin);

611 }

612

613 if (auto *WO = dyn_cast<WithOverflowInst>(UseInst))

614 if (eliminateOverflowIntrinsic(WO))

615 return true;

616

617 if (auto *SI = dyn_cast<SaturatingInst>(UseInst))

618 if (eliminateSaturatingIntrinsic(SI))

619 return true;

620

621 if (auto *TI = dyn_cast<TruncInst>(UseInst))

622 if (eliminateTrunc(TI))

623 return true;

624

625 if (eliminateIdentitySCEV(UseInst, IVOperand))

626 return true;

627

628 return false;

629}

630

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

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

633 return BB->getTerminator();

634

635 return Hint;

636}

637

638/// Replace the UseInst with a loop invariant expression if it is safe.

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

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

641 return false;

642

643 // Get the symbolic expression for this instruction.

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

645

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

647 return false;

648

649 // Do not generate something ridiculous even if S is loop invariant.

650 if (Rewriter.isHighCostExpansion(S, L, SCEVCheapExpansionBudget, TTI, I))

651 return false;

652

653 auto *IP = GetLoopInvariantInsertPosition(L, I);

654

655 if (!Rewriter.isSafeToExpandAt(S, IP)) {

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

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

658 return false;

659 }

660

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

662 bool NeedToEmitLCSSAPhis = false;

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

664 NeedToEmitLCSSAPhis = true;

665

666 I->replaceAllUsesWith(Invariant);

667 LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I

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

669

670 if (NeedToEmitLCSSAPhis) {

671 SmallVector<Instruction *, 1> NeedsLCSSAPhis;

672 NeedsLCSSAPhis.push_back(cast<Instruction>(Invariant));

673 formLCSSAForInstructions(NeedsLCSSAPhis, *DT, *LI, SE);

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

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

676 }

677 ++NumFoldedUser;

678 Changed = true;

679 DeadInsts.emplace_back(I);

680 return true;

681}

682

683/// Eliminate redundant type cast between integer and float.

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

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

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

687 return false;

688

689 Instruction *IVOperand = cast<Instruction>(UseInst->getOperand(0));

690 // Get the symbolic expression for this instruction.

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

692 int MaskBits;

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

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

695 else

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

697 int DestNumSigBits = UseInst->getType()->getFPMantissaWidth();

698 if (MaskBits <= DestNumSigBits) {

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

700 // Match for fptosi/fptoui of sitofp and with same type.

701 auto *CI = dyn_cast<CastInst>(U);

702 if (!CI)

703 continue;

704

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

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

707 continue;

708

709 Value *Conv = nullptr;

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

711 IRBuilder<> Builder(CI);

712 StringRef Name = IVOperand->getName();

713 // To match InstCombine logic, we only need sext if both fptosi and

714 // sitofp are used. If one of them is unsigned, then we can use zext.

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

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

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

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

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

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

721 } else {

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

723 }

724 } else

725 Conv = IVOperand;

726

727 CI->replaceAllUsesWith(Conv);

728 DeadInsts.push_back(CI);

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

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

731

732 ++NumFoldedUser;

733 Changed = true;

734 }

735 }

736

737 return Changed;

738}

739

740/// Eliminate any operation that SCEV can prove is an identity function.

741bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,

742 Instruction *IVOperand) {

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

744 UseInst->getType() != IVOperand->getType())

745 return false;

746

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

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

749 return false;

750

751 // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the

752 // dominator tree, even if X is an operand to Y. For instance, in

753 //

754 // %iv = phi i32 {0,+,1}

755 // br %cond, label %left, label %merge

756 //

757 // left:

758 // %X = add i32 %iv, 0

759 // br label %merge

760 //

761 // merge:

762 // %M = phi (%X, %iv)

763 //

764 // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and

765 // %M.replaceAllUsesWith(%X) would be incorrect.

766

767 if (isa<PHINode>(UseInst))

768 // If UseInst is not a PHI node then we know that IVOperand dominates

769 // UseInst directly from the legality of SSA.

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

771 return false;

772

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

774 return false;

775

776 // Make sure the operand is not more poisonous than the instruction.

777 if (!impliesPoison(IVOperand, UseInst)) {

778 SmallVector<Instruction *> DropPoisonGeneratingInsts;

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

780 return false;

781

782 for (Instruction *I : DropPoisonGeneratingInsts)

783 I->dropPoisonGeneratingAnnotations();

784 }

785

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

787

788 SE->forgetValue(UseInst);

789 UseInst->replaceAllUsesWith(IVOperand);

790 ++NumElimIdentity;

791 Changed = true;

792 DeadInsts.emplace_back(UseInst);

793 return true;

794}

795

796bool SimplifyIndvar::strengthenBinaryOp(BinaryOperator *BO,

797 Instruction *IVOperand) {

798 return (isa<OverflowingBinaryOperator>(BO) &&

799 strengthenOverflowingOperation(BO, IVOperand)) ||

800 (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand));

801}

802

803/// Annotate BO with nsw / nuw if it provably does not signed-overflow /

804/// unsigned-overflow. Returns true if anything changed, false otherwise.

805bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,

806 Instruction *IVOperand) {

807 auto Flags = SE->getStrengthenedNoWrapFlagsFromBinOp(

808 cast<OverflowingBinaryOperator>(BO));

809

810 if (!Flags)

811 return false;

812

813 BO->setHasNoUnsignedWrap(ScalarEvolution::maskFlags(*Flags, SCEV::FlagNUW) ==

814 SCEV::FlagNUW);

815 BO->setHasNoSignedWrap(ScalarEvolution::maskFlags(*Flags, SCEV::FlagNSW) ==

816 SCEV::FlagNSW);

817

818 // The getStrengthenedNoWrapFlagsFromBinOp() check inferred additional nowrap

819 // flags on addrecs while performing zero/sign extensions. We could call

820 // forgetValue() here to make sure those flags also propagate to any other

821 // SCEV expressions based on the addrec. However, this can have pathological

822 // compile-time impact, see https://bugs.llvm.org/show_bug.cgi?id=50384.

823 return true;

824}

825

826/// Annotate the Shr in (X << IVOperand) >> C as exact using the

827/// information from the IV's range. Returns true if anything changed, false

828/// otherwise.

829bool SimplifyIndvar::strengthenRightShift(BinaryOperator *BO,

830 Instruction *IVOperand) {

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

832 bool Changed = false;

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

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

835 const APInt *C;

836 if (match(U,

837 m_AShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C))) ||

838 match(U,

839 m_LShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C)))) {

840 BinaryOperator *Shr = cast<BinaryOperator>(U);

841 if (!Shr->isExact() && IVRange.getUnsignedMin().uge(*C)) {

842 Shr->setIsExact(true);

843 Changed = true;

844 }

845 }

846 }

847 return Changed;

848 }

849

850 return false;

851}

852

853/// Add all uses of Def to the current IV's worklist.

854void SimplifyIndvar::pushIVUsers(

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

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

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

858 Instruction *UI = cast<Instruction>(U);

859

860 // Avoid infinite or exponential worklist processing.

861 // Also ensure unique worklist users.

862 // If Def is a LoopPhi, it may not be in the Simplified set, so check for

863 // self edges first.

864 if (UI == Def)

865 continue;

866

867 // Only change the current Loop, do not change the other parts (e.g. other

868 // Loops).

869 if (!L->contains(UI))

870 continue;

871

872 // Do not push the same instruction more than once.

873 if (!Simplified.insert(UI).second)

874 continue;

875

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

877 }

878}

879

880/// Return true if this instruction generates a simple SCEV

881/// expression in terms of that IV.

882///

883/// This is similar to IVUsers' isInteresting() but processes each instruction

884/// non-recursively when the operand is already known to be a simpleIVUser.

885///

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

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

888 return false;

889

890 // Get the symbolic expression for this instruction.

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

892

893 // Only consider affine recurrences.

894 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);

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

896 return true;

897

898 return false;

899}

900

901/// Iteratively perform simplification on a worklist of users

902/// of the specified induction variable. Each successive simplification may push

903/// more users which may themselves be candidates for simplification.

904///

905/// This algorithm does not require IVUsers analysis. Instead, it simplifies

906/// instructions in-place during analysis. Rather than rewriting induction

907/// variables bottom-up from their users, it transforms a chain of IVUsers

908/// top-down, updating the IR only when it encounters a clear optimization

909/// opportunity.

910///

911/// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.

912///

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

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

915 return;

916

917 // Instructions processed by SimplifyIndvar for CurrIV.

918 SmallPtrSet<Instruction*,16> Simplified;

919

920 // Use-def pairs if IV users waiting to be processed for CurrIV.

921 SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;

922

923 // Push users of the current LoopPhi. In rare cases, pushIVUsers may be

924 // called multiple times for the same LoopPhi. This is the proper thing to

925 // do for loop header phis that use each other.

926 pushIVUsers(CurrIV, Simplified, SimpleIVUsers);

927

928 while (!SimpleIVUsers.empty()) {

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

930 SimpleIVUsers.pop_back_val();

931 Instruction *UseInst = UseOper.first;

932

933 // If a user of the IndVar is trivially dead, we prefer just to mark it dead

934 // rather than try to do some complex analysis or transformation (such as

935 // widening) basing on it.

936 // TODO: Propagate TLI and pass it here to handle more cases.

937 if (isInstructionTriviallyDead(UseInst, /* TLI */ nullptr)) {

938 DeadInsts.emplace_back(UseInst);

939 continue;

940 }

941

942 // Bypass back edges to avoid extra work.

943 if (UseInst == CurrIV) continue;

944

945 // Try to replace UseInst with a loop invariant before any other

946 // simplifications.

947 if (replaceIVUserWithLoopInvariant(UseInst))

948 continue;

949

950 // Go further for the bitcast 'prtoint ptr to i64' or if the cast is done

951 // by truncation

952 if ((isa<PtrToIntInst>(UseInst)) || (isa<TruncInst>(UseInst)))

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

954 Instruction *User = cast<Instruction>(U.getUser());

955 if (replaceIVUserWithLoopInvariant(User))

956 break; // done replacing

957 }

958

959 Instruction *IVOperand = UseOper.second;

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

961 assert(N <= Simplified.size() && "runaway iteration");

962 (void) N;

963

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

965 if (!NewOper)

966 break; // done folding

967 IVOperand = dyn_cast<Instruction>(NewOper);

968 }

969 if (!IVOperand)

970 continue;

971

972 if (eliminateIVUser(UseInst, IVOperand)) {

973 pushIVUsers(IVOperand, Simplified, SimpleIVUsers);

974 continue;

975 }

976

977 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseInst)) {

978 if (strengthenBinaryOp(BO, IVOperand)) {

979 // re-queue uses of the now modified binary operator and fall

980 // through to the checks that remain.

981 pushIVUsers(IVOperand, Simplified, SimpleIVUsers);

982 }

983 }

984

985 // Try to use integer induction for FPToSI of float induction directly.

986 if (replaceFloatIVWithIntegerIV(UseInst)) {

987 // Re-queue the potentially new direct uses of IVOperand.

988 pushIVUsers(IVOperand, Simplified, SimpleIVUsers);

989 continue;

990 }

991

992 CastInst *Cast = dyn_cast<CastInst>(UseInst);

993 if (V && Cast) {

994 V->visitCast(Cast);

995 continue;

996 }

997 if (isSimpleIVUser(UseInst, L, SE)) {

998 pushIVUsers(UseInst, Simplified, SimpleIVUsers);

999 }

1000 }

1001}

1002

1003namespace llvm {

1004

1005 void IVVisitor::anchor() { }

1006

1007/// Simplify instructions that use this induction variable

1008/// by using ScalarEvolution to analyze the IV's recurrence.

1009/// Returns a pair where the first entry indicates that the function makes

1010/// changes and the second entry indicates that it introduced new opportunities

1011/// for loop unswitching.

1012 std::pair<bool, bool> simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE,

1013 DominatorTree *DT, LoopInfo *LI,

1014 const TargetTransformInfo *TTI,

1015 SmallVectorImpl<WeakTrackingVH> &Dead,

1016 SCEVExpander &Rewriter, IVVisitor *V) {

1017 SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, TTI,

1018 Rewriter, Dead);

1019 SIV.simplifyUsers(CurrIV, V);

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

1021}

1022

1023/// Simplify users of induction variables within this

1024/// loop. This does not actually change or add IVs.

1025 bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT,

1026 LoopInfo *LI, const TargetTransformInfo *TTI,

1027 SmallVectorImpl<WeakTrackingVH> &Dead) {

1028 SCEVExpander Rewriter(*SE, SE->getDataLayout(), "indvars");

1029#if LLVM_ENABLE_ABI_BREAKING_CHECKS

1030 Rewriter.setDebugType(DEBUG_TYPE);

1031#endif

1032 bool Changed = false;

1033 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {

1034 const auto &[C, _] =

1035 simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LI, TTI, Dead, Rewriter);

1036 Changed |= C;

1037 }

1038 return Changed;

1039}

1040

1041} // namespace llvm

1042

1043namespace {

1044//===----------------------------------------------------------------------===//

1045// Widen Induction Variables - Extend the width of an IV to cover its

1046// widest uses.

1047//===----------------------------------------------------------------------===//

1048

1049class WidenIV {

1050 // Parameters

1051 PHINode *OrigPhi;

1052 Type *WideType;

1053

1054 // Context

1055 LoopInfo *LI;

1056 Loop *L;

1057 ScalarEvolution *SE;

1058 DominatorTree *DT;

1059

1060 // Does the module have any calls to the llvm.experimental.guard intrinsic

1061 // at all? If not we can avoid scanning instructions looking for guards.

1062 bool HasGuards;

1063

1064 bool UsePostIncrementRanges;

1065

1066 // Statistics

1067 unsigned NumElimExt = 0;

1068 unsigned NumWidened = 0;

1069

1070 // Result

1071 PHINode *WidePhi = nullptr;

1072 Instruction *WideInc = nullptr;

1073 const SCEV *WideIncExpr = nullptr;

1074 SmallVectorImpl<WeakTrackingVH> &DeadInsts;

1075

1076 SmallPtrSet<Instruction *,16> Widened;

1077

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

1079

1080 // A map tracking the kind of extension used to widen each narrow IV

1081 // and narrow IV user.

1082 // Key: pointer to a narrow IV or IV user.

1083 // Value: the kind of extension used to widen this Instruction.

1084 DenseMap<AssertingVH<Instruction>, ExtendKind> ExtendKindMap;

1085

1086 using DefUserPair = std::pair<AssertingVH<Value>, AssertingVH<Instruction>>;

1087

1088 // A map with control-dependent ranges for post increment IV uses. The key is

1089 // a pair of IV def and a use of this def denoting the context. The value is

1090 // a ConstantRange representing possible values of the def at the given

1091 // context.

1092 DenseMap<DefUserPair, ConstantRange> PostIncRangeInfos;

1093

1094 std::optional<ConstantRange> getPostIncRangeInfo(Value *Def,

1095 Instruction *UseI) {

1096 DefUserPair Key(Def, UseI);

1097 auto It = PostIncRangeInfos.find(Key);

1098 return It == PostIncRangeInfos.end()

1099 ? std::optional<ConstantRange>(std::nullopt)

1100 : std::optional<ConstantRange>(It->second);

1101 }

1102

1103 void calculatePostIncRanges(PHINode *OrigPhi);

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

1105

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

1107 DefUserPair Key(Def, UseI);

1108 auto [It, Inserted] = PostIncRangeInfos.try_emplace(Key, R);

1109 if (!Inserted)

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

1111 }

1112

1113public:

1114 /// Record a link in the Narrow IV def-use chain along with the WideIV that

1115 /// computes the same value as the Narrow IV def. This avoids caching Use*

1116 /// pointers.

1117 struct NarrowIVDefUse {

1118 Instruction *NarrowDef = nullptr;

1119 Instruction *NarrowUse = nullptr;

1120 Instruction *WideDef = nullptr;

1121

1122 // True if the narrow def is never negative. Tracking this information lets

1123 // us use a sign extension instead of a zero extension or vice versa, when

1124 // profitable and legal.

1125 bool NeverNegative = false;

1126

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

1128 bool NeverNegative)

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

1130 NeverNegative(NeverNegative) {}

1131 };

1132

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

1134 DominatorTree *DTree, SmallVectorImpl<WeakTrackingVH> &DI,

1135 bool HasGuards, bool UsePostIncrementRanges = true);

1136

1137 PHINode *createWideIV(SCEVExpander &Rewriter);

1138

1139 unsigned getNumElimExt() { return NumElimExt; };

1140 unsigned getNumWidened() { return NumWidened; };

1141

1142protected:

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

1144 Instruction *Use);

1145

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

1147 Instruction *cloneArithmeticIVUser(NarrowIVDefUse DU,

1148 const SCEVAddRecExpr *WideAR);

1149 Instruction *cloneBitwiseIVUser(NarrowIVDefUse DU);

1150

1151 ExtendKind getExtendKind(Instruction *I);

1152

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

1154

1155 WidenedRecTy getWideRecurrence(NarrowIVDefUse DU);

1156

1157 WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU);

1158

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

1160 unsigned OpCode) const;

1161

1162 Instruction *widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter,

1163 PHINode *OrigPhi, PHINode *WidePhi);

1164 void truncateIVUse(NarrowIVDefUse DU);

1165

1166 bool widenLoopCompare(NarrowIVDefUse DU);

1167 bool widenWithVariantUse(NarrowIVDefUse DU);

1168

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

1170

1171private:

1172 SmallVector<NarrowIVDefUse, 8> NarrowIVUsers;

1173};

1174} // namespace

1175

1176/// Determine the insertion point for this user. By default, insert immediately

1177/// before the user. SCEVExpander or LICM will hoist loop invariants out of the

1178/// loop. For PHI nodes, there may be multiple uses, so compute the nearest

1179/// common dominator for the incoming blocks. A nullptr can be returned if no

1180/// viable location is found: it may happen if User is a PHI and Def only comes

1181/// to this PHI from unreachable blocks.

1182 static Instruction *getInsertPointForUses(Instruction *User, Value *Def,

1183 DominatorTree *DT, LoopInfo *LI) {

1184 PHINode *PHI = dyn_cast<PHINode>(User);

1185 if (!PHI)

1186 return User;

1187

1188 Instruction *InsertPt = nullptr;

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

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

1191 continue;

1192

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

1194

1195 if (!DT->isReachableFromEntry(InsertBB))

1196 continue;

1197

1198 if (!InsertPt) {

1199 InsertPt = InsertBB->getTerminator();

1200 continue;

1201 }

1202 InsertBB = DT->findNearestCommonDominator(InsertPt->getParent(), InsertBB);

1203 InsertPt = InsertBB->getTerminator();

1204 }

1205

1206 // If we have skipped all inputs, it means that Def only comes to Phi from

1207 // unreachable blocks.

1208 if (!InsertPt)

1209 return nullptr;

1210

1211 auto *DefI = dyn_cast<Instruction>(Def);

1212 if (!DefI)

1213 return InsertPt;

1214

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

1216

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

1218 assert(!L || L->contains(LI->getLoopFor(InsertPt->getParent())));

1219

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

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

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

1223

1224 llvm_unreachable("DefI dominates InsertPt!");

1225}

1226

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

1228 DominatorTree *DTree, SmallVectorImpl<WeakTrackingVH> &DI,

1229 bool HasGuards, bool UsePostIncrementRanges)

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

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

1232 HasGuards(HasGuards), UsePostIncrementRanges(UsePostIncrementRanges),

1233 DeadInsts(DI) {

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

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

1236}

1237

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

1239 bool IsSigned, Instruction *Use) {

1240 // Set the debug location and conservative insertion point.

1241 IRBuilder<> Builder(Use);

1242 // Hoist the insertion point into loop preheaders as far as possible.

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

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

1245 L = L->getParentLoop())

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

1247

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

1249 Builder.CreateZExt(NarrowOper, WideType);

1250}

1251

1252/// Instantiate a wide operation to replace a narrow operation. This only needs

1253/// to handle operations that can evaluation to SCEVAddRec. It can safely return

1254/// 0 for any operation we decide not to clone.

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

1256 const SCEVAddRecExpr *WideAR) {

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

1258 switch (Opcode) {

1259 default:

1260 return nullptr;

1261 case Instruction::Add:

1262 case Instruction::Mul:

1263 case Instruction::UDiv:

1264 case Instruction::Sub:

1265 return cloneArithmeticIVUser(DU, WideAR);

1266

1267 case Instruction::And:

1268 case Instruction::Or:

1269 case Instruction::Xor:

1270 case Instruction::Shl:

1271 case Instruction::LShr:

1272 case Instruction::AShr:

1273 return cloneBitwiseIVUser(DU);

1274 }

1275}

1276

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

1278 Instruction *NarrowUse = DU.NarrowUse;

1279 Instruction *NarrowDef = DU.NarrowDef;

1280 Instruction *WideDef = DU.WideDef;

1281

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

1283

1284 // Replace NarrowDef operands with WideDef. Otherwise, we don't know anything

1285 // about the narrow operand yet so must insert a [sz]ext. It is probably loop

1286 // invariant and will be folded or hoisted. If it actually comes from a

1287 // widened IV, it should be removed during a future call to widenIVUse.

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

1289 Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)

1290 ? WideDef

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

1292 IsSigned, NarrowUse);

1293 Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)

1294 ? WideDef

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

1296 IsSigned, NarrowUse);

1297

1298 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);

1299 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,

1300 NarrowBO->getName());

1301 IRBuilder<> Builder(NarrowUse);

1302 Builder.Insert(WideBO);

1303 WideBO->copyIRFlags(NarrowBO);

1304 return WideBO;

1305}

1306

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

1308 const SCEVAddRecExpr *WideAR) {

1309 Instruction *NarrowUse = DU.NarrowUse;

1310 Instruction *NarrowDef = DU.NarrowDef;

1311 Instruction *WideDef = DU.WideDef;

1312

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

1314

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

1316

1317 // We're trying to find X such that

1318 //

1319 // Widen(NarrowDef `op` NonIVNarrowDef) == WideAR == WideDef `op.wide` X

1320 //

1321 // We guess two solutions to X, sext(NonIVNarrowDef) and zext(NonIVNarrowDef),

1322 // and check using SCEV if any of them are correct.

1323

1324 // Returns true if extending NonIVNarrowDef according to `SignExt` is a

1325 // correct solution to X.

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

1327 const SCEV *WideLHS;

1328 const SCEV *WideRHS;

1329

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

1331 if (SignExt)

1332 return SE->getSignExtendExpr(S, Ty);

1333 return SE->getZeroExtendExpr(S, Ty);

1334 };

1335

1336 if (IVOpIdx == 0) {

1337 WideLHS = SE->getSCEV(WideDef);

1338 const SCEV *NarrowRHS = SE->getSCEV(NarrowUse->getOperand(1));

1339 WideRHS = GetExtend(NarrowRHS, WideType);

1340 } else {

1341 const SCEV *NarrowLHS = SE->getSCEV(NarrowUse->getOperand(0));

1342 WideLHS = GetExtend(NarrowLHS, WideType);

1343 WideRHS = SE->getSCEV(WideDef);

1344 }

1345

1346 // WideUse is "WideDef `op.wide` X" as described in the comment.

1347 const SCEV *WideUse =

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

1349

1350 return WideUse == WideAR;

1351 };

1352

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

1354 if (!GuessNonIVOperand(SignExtend)) {

1355 SignExtend = !SignExtend;

1356 if (!GuessNonIVOperand(SignExtend))

1357 return nullptr;

1358 }

1359

1360 Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)

1361 ? WideDef

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

1363 SignExtend, NarrowUse);

1364 Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)

1365 ? WideDef

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

1367 SignExtend, NarrowUse);

1368

1369 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);

1370 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,

1371 NarrowBO->getName());

1372

1373 IRBuilder<> Builder(NarrowUse);

1374 Builder.Insert(WideBO);

1375 WideBO->copyIRFlags(NarrowBO);

1376 return WideBO;

1377}

1378

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

1380 auto It = ExtendKindMap.find(I);

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

1382 return It->second;

1383}

1384

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

1386 unsigned OpCode) const {

1387 switch (OpCode) {

1388 case Instruction::Add:

1389 return SE->getAddExpr(LHS, RHS);

1390 case Instruction::Sub:

1391 return SE->getMinusSCEV(LHS, RHS);

1392 case Instruction::Mul:

1393 return SE->getMulExpr(LHS, RHS);

1394 case Instruction::UDiv:

1395 return SE->getUDivExpr(LHS, RHS);

1396 default:

1397 llvm_unreachable("Unsupported opcode.");

1398 };

1399}

1400

1401namespace {

1402

1403// Represents a interesting integer binary operation for

1404// getExtendedOperandRecurrence. This may be a shl that is being treated as a

1405// multiply or a 'or disjoint' that is being treated as 'add nsw nuw'.

1406struct BinaryOp {

1407 unsigned Opcode;

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

1409 bool IsNSW = false;

1410 bool IsNUW = false;

1411

1412 explicit BinaryOp(Instruction *Op)

1413 : Opcode(Op->getOpcode()),

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

1415 if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(Op)) {

1416 IsNSW = OBO->hasNoSignedWrap();

1417 IsNUW = OBO->hasNoUnsignedWrap();

1418 }

1419 }

1420

1421 explicit BinaryOp(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,

1422 bool IsNSW = false, bool IsNUW = false)

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

1424};

1425

1426} // end anonymous namespace

1427

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

1429 switch (Op->getOpcode()) {

1430 case Instruction::Add:

1431 case Instruction::Sub:

1432 case Instruction::Mul:

1433 return BinaryOp(Op);

1434 case Instruction::Or: {

1435 // Convert or disjoint into add nuw nsw.

1436 if (cast<PossiblyDisjointInst>(Op)->isDisjoint())

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

1438 /*IsNSW=*/true, /*IsNUW=*/true);

1439 break;

1440 }

1441 case Instruction::Shl: {

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

1443 unsigned BitWidth = cast<IntegerType>(SA->getType())->getBitWidth();

1444

1445 // If the shift count is not less than the bitwidth, the result of

1446 // the shift is undefined. Don't try to analyze it, because the

1447 // resolution chosen here may differ from the resolution chosen in

1448 // other parts of the compiler.

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

1450 // We can safely preserve the nuw flag in all cases. It's also safe to

1451 // turn a nuw nsw shl into a nuw nsw mul. However, nsw in isolation

1452 // requires special handling. It can be preserved as long as we're not

1453 // left shifting by bitwidth - 1.

1454 bool IsNUW = Op->hasNoUnsignedWrap();

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

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

1457

1458 ConstantInt *X =

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

1460 APInt::getOneBitSet(BitWidth, SA->getZExtValue()));

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

1462 }

1463 }

1464

1465 break;

1466 }

1467 }

1468

1469 return std::nullopt;

1470}

1471

1472/// No-wrap operations can transfer sign extension of their result to their

1473/// operands. Generate the SCEV value for the widened operation without

1474/// actually modifying the IR yet. If the expression after extending the

1475/// operands is an AddRec for this loop, return the AddRec and the kind of

1476/// extension used.

1477WidenIV::WidenedRecTy

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

1479 auto Op = matchBinaryOp(DU.NarrowUse);

1480 if (!Op)

1481 return {nullptr, ExtendKind::Unknown};

1482

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

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

1485 "Unexpected opcode");

1486

1487 // One operand (NarrowDef) has already been extended to WideDef. Now determine

1488 // if extending the other will lead to a recurrence.

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

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

1491

1492 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);

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

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

1495 ExtKind = ExtendKind::Unknown;

1496

1497 // For a non-negative NarrowDef, we can choose either type of

1498 // extension. We want to use the current extend kind if legal

1499 // (see above), and we only hit this code if we need to check

1500 // the opposite case.

1501 if (DU.NeverNegative) {

1502 if (Op->IsNSW) {

1503 ExtKind = ExtendKind::Sign;

1504 } else if (Op->IsNUW) {

1505 ExtKind = ExtendKind::Zero;

1506 }

1507 }

1508 }

1509

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

1511 if (ExtKind == ExtendKind::Sign)

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

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

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

1515 else

1516 return {nullptr, ExtendKind::Unknown};

1517

1518 // When creating this SCEV expr, don't apply the current operations NSW or NUW

1519 // flags. This instruction may be guarded by control flow that the no-wrap

1520 // behavior depends on. Non-control-equivalent instructions can be mapped to

1521 // the same SCEV expression, and it would be incorrect to transfer NSW/NUW

1522 // semantics to those operations.

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

1524 const SCEV *rhs = ExtendOperExpr;

1525

1526 // Let's swap operands to the initial order for the case of non-commutative

1527 // operations, like SUB. See PR21014.

1528 if (ExtendOperIdx == 0)

1529 std::swap(lhs, rhs);

1530 const SCEVAddRecExpr *AddRec =

1531 dyn_cast<SCEVAddRecExpr>(getSCEVByOpCode(lhs, rhs, Op->Opcode));

1532

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

1534 return {nullptr, ExtendKind::Unknown};

1535

1536 return {AddRec, ExtKind};

1537}

1538

1539/// Is this instruction potentially interesting for further simplification after

1540/// widening it's type? In other words, can the extend be safely hoisted out of

1541/// the loop with SCEV reducing the value to a recurrence on the same loop. If

1542/// so, return the extended recurrence and the kind of extension used. Otherwise

1543/// return {nullptr, ExtendKind::Unknown}.

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

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

1546 return {nullptr, ExtendKind::Unknown};

1547

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

1549 if (SE->getTypeSizeInBits(NarrowExpr->getType()) >=

1550 SE->getTypeSizeInBits(WideType)) {

1551 // NarrowUse implicitly widens its operand. e.g. a gep with a narrow

1552 // index. So don't follow this use.

1553 return {nullptr, ExtendKind::Unknown};

1554 }

1555

1556 const SCEV *WideExpr;

1557 ExtendKind ExtKind;

1558 if (DU.NeverNegative) {

1559 WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);

1560 if (isa<SCEVAddRecExpr>(WideExpr))

1561 ExtKind = ExtendKind::Sign;

1562 else {

1563 WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);

1564 ExtKind = ExtendKind::Zero;

1565 }

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

1567 WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);

1568 ExtKind = ExtendKind::Sign;

1569 } else {

1570 WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);

1571 ExtKind = ExtendKind::Zero;

1572 }

1573 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr);

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

1575 return {nullptr, ExtendKind::Unknown};

1576 return {AddRec, ExtKind};

1577}

1578

1579/// This IV user cannot be widened. Replace this use of the original narrow IV

1580/// with a truncation of the new wide IV to isolate and eliminate the narrow IV.

1581void WidenIV::truncateIVUse(NarrowIVDefUse DU) {

1582 auto *InsertPt = getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI);

1583 if (!InsertPt)

1584 return;

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

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

1587 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);

1588 IRBuilder<> Builder(InsertPt);

1589 Value *Trunc =

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

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

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

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

1594}

1595

1596/// If the narrow use is a compare instruction, then widen the compare

1597// (and possibly the other operand). The extend operation is hoisted into the

1598// loop preheader as far as possible.

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

1600 ICmpInst *Cmp = dyn_cast<ICmpInst>(DU.NarrowUse);

1601 if (!Cmp)

1602 return false;

1603

1604 // We can legally widen the comparison in the following two cases:

1605 //

1606 // - The signedness of the IV extension and comparison match

1607 //

1608 // - The narrow IV is always non-negative (and thus its sign extension is

1609 // equal to its zero extension). For instance, let's say we're zero

1610 // extending %narrow for the following use

1611 //

1612 // icmp slt i32 %narrow, %val ... (A)

1613 //

1614 // and %narrow is always non-negative. Then

1615 //

1616 // (A) == icmp slt i32 sext(%narrow), sext(%val)

1617 // == icmp slt i32 zext(%narrow), sext(%val)

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

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

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

1621 return false;

1622

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

1624 unsigned CastWidth = SE->getTypeSizeInBits(Op->getType());

1625 unsigned IVWidth = SE->getTypeSizeInBits(WideType);

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

1627

1628 // Widen the compare instruction.

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

1630

1631 // Widen the other operand of the compare, if necessary.

1632 if (CastWidth < IVWidth) {

1633 // If the narrow IV is always non-negative and the other operand is sext,

1634 // widen using sext so we can combine them. This works for all non-signed

1635 // comparison predicates.

1636 if (DU.NeverNegative && isa<SExtInst>(Op) && !Cmp->isSigned())

1637 CmpPreferredSign = true;

1638

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

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

1641 }

1642 return true;

1643}

1644

1645// The widenIVUse avoids generating trunc by evaluating the use as AddRec, this

1646// will not work when:

1647// 1) SCEV traces back to an instruction inside the loop that SCEV can not

1648// expand, eg. add %indvar, (load %addr)

1649// 2) SCEV finds a loop variant, eg. add %indvar, %loopvariant

1650// While SCEV fails to avoid trunc, we can still try to use instruction

1651// combining approach to prove trunc is not required. This can be further

1652// extended with other instruction combining checks, but for now we handle the

1653// following case (sub can be "add" and "mul", "nsw + sext" can be "nus + zext")

1654//

1655// Src:

1656// %c = sub nsw %b, %indvar

1657// %d = sext %c to i64

1658// Dst:

1659// %indvar.ext1 = sext %indvar to i64

1660// %m = sext %b to i64

1661// %d = sub nsw i64 %m, %indvar.ext1

1662// Therefore, as long as the result of add/sub/mul is extended to wide type, no

1663// trunc is required regardless of how %b is generated. This pattern is common

1664// when calculating address in 64 bit architecture

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

1666 Instruction *NarrowUse = DU.NarrowUse;

1667 Instruction *NarrowDef = DU.NarrowDef;

1668 Instruction *WideDef = DU.WideDef;

1669

1670 // Handle the common case of add<nsw/nuw>

1671 const unsigned OpCode = NarrowUse->getOpcode();

1672 // Only Add/Sub/Mul instructions are supported.

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

1674 OpCode != Instruction::Mul)

1675 return false;

1676

1677 // The operand that is not defined by NarrowDef of DU. Let's call it the

1678 // other operand.

1679 assert((NarrowUse->getOperand(0) == NarrowDef ||

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

1681 "bad DU");

1682

1683 const OverflowingBinaryOperator *OBO =

1684 cast<OverflowingBinaryOperator>(NarrowUse);

1685 ExtendKind ExtKind = getExtendKind(NarrowDef);

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

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

1688 auto AnotherOpExtKind = ExtKind;

1689

1690 // Check that all uses are either:

1691 // - narrow def (in case of we are widening the IV increment);

1692 // - single-input LCSSA Phis;

1693 // - comparison of the chosen type;

1694 // - extend of the chosen type (raison d'etre).

1695 SmallVector<Instruction *, 4> ExtUsers;

1696 SmallVector<PHINode *, 4> LCSSAPhiUsers;

1697 SmallVector<ICmpInst *, 4> ICmpUsers;

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

1699 Instruction *User = cast<Instruction>(U.getUser());

1700 if (User == NarrowDef)

1701 continue;

1702 if (!L->contains(User)) {

1703 auto *LCSSAPhi = cast<PHINode>(User);

1704 // Make sure there is only 1 input, so that we don't have to split

1705 // critical edges.

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

1707 return false;

1708 LCSSAPhiUsers.push_back(LCSSAPhi);

1709 continue;

1710 }

1711 if (auto *ICmp = dyn_cast<ICmpInst>(User)) {

1712 auto Pred = ICmp->getPredicate();

1713 // We have 3 types of predicates: signed, unsigned and equality

1714 // predicates. For equality, it's legal to widen icmp for either sign and

1715 // zero extend. For sign extend, we can also do so for signed predicates,

1716 // likeweise for zero extend we can widen icmp for unsigned predicates.

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

1718 return false;

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

1720 return false;

1721 ICmpUsers.push_back(ICmp);

1722 continue;

1723 }

1724 if (ExtKind == ExtendKind::Sign)

1725 User = dyn_cast<SExtInst>(User);

1726 else

1727 User = dyn_cast<ZExtInst>(User);

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

1729 return false;

1730 ExtUsers.push_back(User);

1731 }

1732 if (ExtUsers.empty()) {

1733 DeadInsts.emplace_back(NarrowUse);

1734 return true;

1735 }

1736

1737 // We'll prove some facts that should be true in the context of ext users. If

1738 // there is no users, we are done now. If there are some, pick their common

1739 // dominator as context.

1740 const Instruction *CtxI = findCommonDominator(ExtUsers, *DT);

1741

1742 if (!CanSignExtend && !CanZeroExtend) {

1743 // Because InstCombine turns 'sub nuw' to 'add' losing the no-wrap flag, we

1744 // will most likely not see it. Let's try to prove it.

1745 if (OpCode != Instruction::Add)

1746 return false;

1747 if (ExtKind != ExtendKind::Zero)

1748 return false;

1749 const SCEV *LHS = SE->getSCEV(OBO->getOperand(0));

1750 const SCEV *RHS = SE->getSCEV(OBO->getOperand(1));

1751 // TODO: Support case for NarrowDef = NarrowUse->getOperand(1).

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

1753 return false;

1754 // We cannot use a different extend kind for the same operand.

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

1756 return false;

1757 if (!SE->isKnownNegative(RHS))

1758 return false;

1759 bool ProvedSubNUW = SE->isKnownPredicateAt(ICmpInst::ICMP_UGE, LHS,

1760 SE->getNegativeSCEV(RHS), CtxI);

1761 if (!ProvedSubNUW)

1762 return false;

1763 // In fact, our 'add' is 'sub nuw'. We will need to widen the 2nd operand as

1764 // neg(zext(neg(op))), which is basically sext(op).

1765 AnotherOpExtKind = ExtendKind::Sign;

1766 }

1767

1768 // Verifying that Defining operand is an AddRec

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

1770 const SCEVAddRecExpr *AddRecOp1 = dyn_cast<SCEVAddRecExpr>(Op1);

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

1772 return false;

1773

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

1775

1776 // Generating a widening use instruction.

1777 Value *LHS =

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

1779 ? WideDef

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

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

1782 Value *RHS =

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

1784 ? WideDef

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

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

1787

1788 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);

1789 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,

1790 NarrowBO->getName());

1791 IRBuilder<> Builder(NarrowUse);

1792 Builder.Insert(WideBO);

1793 WideBO->copyIRFlags(NarrowBO);

1794 ExtendKindMap[NarrowUse] = ExtKind;

1795

1796 for (Instruction *User : ExtUsers) {

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

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

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

1800 ++NumElimExt;

1801 User->replaceAllUsesWith(WideBO);

1802 DeadInsts.emplace_back(User);

1803 }

1804

1805 for (PHINode *User : LCSSAPhiUsers) {

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

1807 Builder.SetInsertPoint(User);

1808 auto *WidePN =

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

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

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

1812 "Not a LCSSA Phi?");

1813 WidePN->addIncoming(WideBO, LoopExitingBlock);

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

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

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

1817 User->replaceAllUsesWith(TruncPN);

1818 DeadInsts.emplace_back(User);

1819 }

1820

1821 for (ICmpInst *User : ICmpUsers) {

1822 Builder.SetInsertPoint(User);

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

1824 if (V == NarrowUse)

1825 return WideBO;

1826 if (ExtKind == ExtendKind::Zero)

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

1828 else

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

1830 };

1831 auto Pred = User->getPredicate();

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

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

1834 auto *WideCmp =

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

1836 User->replaceAllUsesWith(WideCmp);

1837 DeadInsts.emplace_back(User);

1838 }

1839

1840 return true;

1841}

1842

1843/// Determine whether an individual user of the narrow IV can be widened. If so,

1844/// return the wide clone of the user.

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

1846 SCEVExpander &Rewriter, PHINode *OrigPhi,

1847 PHINode *WidePhi) {

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

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

1850

1851 // This narrow use can be widened by a sext if it's non-negative or its narrow

1852 // def was widened by a sext. Same for zext.

1853 bool CanWidenBySExt =

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

1855 bool CanWidenByZExt =

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

1857

1858 // Stop traversing the def-use chain at inner-loop phis or post-loop phis.

1859 if (PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) {

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

1861 // For LCSSA phis, sink the truncate outside the loop.

1862 // After SimplifyCFG most loop exit targets have a single predecessor.

1863 // Otherwise fall back to a truncate within the loop.

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

1865 truncateIVUse(DU);

1866 else {

1867 // Widening the PHI requires us to insert a trunc. The logical place

1868 // for this trunc is in the same BB as the PHI. This is not possible if

1869 // the BB is terminated by a catchswitch.

1870 if (isa<CatchSwitchInst>(UsePhi->getParent()->getTerminator()))

1871 return nullptr;

1872

1873 PHINode *WidePhi =

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

1875 UsePhi->getIterator());

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

1877 BasicBlock *WidePhiBB = WidePhi->getParent();

1878 IRBuilder<> Builder(WidePhiBB, WidePhiBB->getFirstInsertionPt());

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

1880 CanWidenByZExt, CanWidenBySExt);

1881 UsePhi->replaceAllUsesWith(Trunc);

1882 DeadInsts.emplace_back(UsePhi);

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

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

1885 }

1886 return nullptr;

1887 }

1888 }

1889

1890 // Our raison d'etre! Eliminate sign and zero extension.

1891 if ((match(DU.NarrowUse, m_SExtLike(m_Value())) && CanWidenBySExt) ||

1892 (isa<ZExtInst>(DU.NarrowUse) && CanWidenByZExt)) {

1893 Value *NewDef = DU.WideDef;

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

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

1896 unsigned IVWidth = SE->getTypeSizeInBits(WideType);

1897 if (CastWidth < IVWidth) {

1898 // The cast isn't as wide as the IV, so insert a Trunc.

1899 IRBuilder<> Builder(DU.NarrowUse);

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

1901 CanWidenByZExt, CanWidenBySExt);

1902 }

1903 else {

1904 // A wider extend was hidden behind a narrower one. This may induce

1905 // another round of IV widening in which the intermediate IV becomes

1906 // dead. It should be very rare.

1907 LLVM_DEBUG(dbgs() << "INDVARS: New IV " << *WidePhi

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

1909 << "\n");

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

1911 NewDef = DU.NarrowUse;

1912 }

1913 }

1914 if (NewDef != DU.NarrowUse) {

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

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

1917 ++NumElimExt;

1918 DU.NarrowUse->replaceAllUsesWith(NewDef);

1919 DeadInsts.emplace_back(DU.NarrowUse);

1920 }

1921 // Now that the extend is gone, we want to expose it's uses for potential

1922 // further simplification. We don't need to directly inform SimplifyIVUsers

1923 // of the new users, because their parent IV will be processed later as a

1924 // new loop phi. If we preserved IVUsers analysis, we would also want to

1925 // push the uses of WideDef here.

1926

1927 // No further widening is needed. The deceased [sz]ext had done it for us.

1928 return nullptr;

1929 }

1930

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

1932 // Does this user itself evaluate to a recurrence after widening?

1933 WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);

1934 if (!WideAddRec.first)

1935 WideAddRec = getWideRecurrence(DU);

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

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

1938 if (!WideAddRec.first)

1939 return nullptr;

1940

1941 auto CanUseWideInc = [&]() {

1942 if (!WideInc)

1943 return false;

1944 // Reuse the IV increment that SCEVExpander created. Recompute flags,

1945 // unless the flags for both increments agree and it is safe to use the

1946 // ones from the original inc. In that case, the new use of the wide

1947 // increment won't be more poisonous.

1948 bool NeedToRecomputeFlags =

1949 !SCEVExpander::canReuseFlagsFromOriginalIVInc(

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

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

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

1953 return WideAddRec.first == WideIncExpr &&

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

1955 };

1956

1957 Instruction *WideUse = nullptr;

1958 if (CanUseWideInc())

1959 WideUse = WideInc;

1960 else {

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

1962 if (!WideUse)

1963 return nullptr;

1964 }

1965 // Evaluation of WideAddRec ensured that the narrow expression could be

1966 // extended outside the loop without overflow. This suggests that the wide use

1967 // evaluates to the same expression as the extended narrow use, but doesn't

1968 // absolutely guarantee it. Hence the following failsafe check. In rare cases

1969 // where it fails, we simply throw away the newly created wide use.

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

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

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

1973 << "\n");

1974 DeadInsts.emplace_back(WideUse);

1975 return nullptr;

1976 };

1977

1978 // if we reached this point then we are going to replace

1979 // DU.NarrowUse with WideUse. Reattach DbgValue then.

1980 replaceAllDbgUsesWith(*DU.NarrowUse, *WideUse, *WideUse, *DT);

1981

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

1983 // Returning WideUse pushes it on the worklist.

1984 return WideUse;

1985 };

1986

1987 if (auto *I = tryAddRecExpansion())

1988 return I;

1989

1990 // If use is a loop condition, try to promote the condition instead of

1991 // truncating the IV first.

1992 if (widenLoopCompare(DU))

1993 return nullptr;

1994

1995 // We are here about to generate a truncate instruction that may hurt

1996 // performance because the scalar evolution expression computed earlier

1997 // in WideAddRec.first does not indicate a polynomial induction expression.

1998 // In that case, look at the operands of the use instruction to determine

1999 // if we can still widen the use instead of truncating its operand.

2000 if (widenWithVariantUse(DU))

2001 return nullptr;

2002

2003 // This user does not evaluate to a recurrence after widening, so don't

2004 // follow it. Instead insert a Trunc to kill off the original use,

2005 // eventually isolating the original narrow IV so it can be removed.

2006 truncateIVUse(DU);

2007 return nullptr;

2008}

2009

2010/// Add eligible users of NarrowDef to NarrowIVUsers.

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

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

2013 bool NonNegativeDef =

2014 SE->isKnownPredicate(ICmpInst::ICMP_SGE, NarrowSCEV,

2015 SE->getZero(NarrowSCEV->getType()));

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

2017 Instruction *NarrowUser = cast<Instruction>(U);

2018

2019 // Handle data flow merges and bizarre phi cycles.

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

2021 continue;

2022

2023 bool NonNegativeUse = false;

2024 if (!NonNegativeDef) {

2025 // We might have a control-dependent range information for this context.

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

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

2028 }

2029

2030 NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef,

2031 NonNegativeDef || NonNegativeUse);

2032 }

2033}

2034

2035/// Process a single induction variable. First use the SCEVExpander to create a

2036/// wide induction variable that evaluates to the same recurrence as the

2037/// original narrow IV. Then use a worklist to forward traverse the narrow IV's

2038/// def-use chain. After widenIVUse has processed all interesting IV users, the

2039/// narrow IV will be isolated for removal by DeleteDeadPHIs.

2040///

2041/// It would be simpler to delete uses as they are processed, but we must avoid

2042/// invalidating SCEV expressions.

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

2044 // Is this phi an induction variable?

2045 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi));

2046 if (!AddRec)

2047 return nullptr;

2048

2049 // Widen the induction variable expression.

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

2051 ? SE->getSignExtendExpr(AddRec, WideType)

2052 : SE->getZeroExtendExpr(AddRec, WideType);

2053

2054 assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType &&

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

2056

2057 // Can the IV be extended outside the loop without overflow?

2058 AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr);

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

2060 return nullptr;

2061

2062 // An AddRec must have loop-invariant operands. Since this AddRec is

2063 // materialized by a loop header phi, the expression cannot have any post-loop

2064 // operands, so they must dominate the loop header.

2065 assert(

2066 SE->properlyDominates(AddRec->getStart(), L->getHeader()) &&

2067 SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) &&

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

2069

2070 // Iterate over IV uses (including transitive ones) looking for IV increments

2071 // of the form 'add nsw %iv, <const>'. For each increment and each use of

2072 // the increment calculate control-dependent range information basing on

2073 // dominating conditions inside of the loop (e.g. a range check inside of the

2074 // loop). Calculated ranges are stored in PostIncRangeInfos map.

2075 //

2076 // Control-dependent range information is later used to prove that a narrow

2077 // definition is not negative (see pushNarrowIVUsers). It's difficult to do

2078 // this on demand because when pushNarrowIVUsers needs this information some

2079 // of the dominating conditions might be already widened.

2080 if (UsePostIncrementRanges)

2081 calculatePostIncRanges(OrigPhi);

2082

2083 // The rewriter provides a value for the desired IV expression. This may

2084 // either find an existing phi or materialize a new one. Either way, we

2085 // expect a well-formed cyclic phi-with-increments. i.e. any operand not part

2086 // of the phi-SCC dominates the loop entry.

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

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

2089 // If the wide phi is not a phi node, for example a cast node, like bitcast,

2090 // inttoptr, ptrtoint, just skip for now.

2091 if (!(WidePhi = dyn_cast<PHINode>(ExpandInst))) {

2092 // if the cast node is an inserted instruction without any user, we should

2093 // remove it to make sure the pass don't touch the function as we can not

2094 // wide the phi.

2095 if (ExpandInst->use_empty() &&

2096 Rewriter.isInsertedInstruction(cast<Instruction>(ExpandInst)))

2097 DeadInsts.emplace_back(ExpandInst);

2098 return nullptr;

2099 }

2100

2101 // Remembering the WideIV increment generated by SCEVExpander allows

2102 // widenIVUse to reuse it when widening the narrow IV's increment. We don't

2103 // employ a general reuse mechanism because the call above is the only call to

2104 // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses.

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

2106 WideInc =

2107 dyn_cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock));

2108 if (WideInc) {

2109 WideIncExpr = SE->getSCEV(WideInc);

2110 // Propagate the debug location associated with the original loop

2111 // increment to the new (widened) increment.

2112 auto *OrigInc =

2113 cast<Instruction>(OrigPhi->getIncomingValueForBlock(LatchBlock));

2114

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

2116 // We are replacing a narrow IV increment with a wider IV increment. If

2117 // the original (narrow) increment did not wrap, the wider increment one

2118 // should not wrap either. Set the flags to be the union of both wide

2119 // increment and original increment; this ensures we preserve flags SCEV

2120 // could infer for the wider increment. Limit this only to cases where

2121 // both increments directly increment the corresponding PHI nodes and have

2122 // the same opcode. It is not safe to re-use the flags from the original

2123 // increment, if it is more complex and SCEV expansion may have yielded a

2124 // more simplified wider increment.

2125 if (SCEVExpander::canReuseFlagsFromOriginalIVInc(OrigPhi, WidePhi,

2126 OrigInc, WideInc) &&

2127 isa<OverflowingBinaryOperator>(OrigInc) &&

2128 isa<OverflowingBinaryOperator>(WideInc)) {

2129 WideInc->setHasNoUnsignedWrap(WideInc->hasNoUnsignedWrap() ||

2130 OrigInc->hasNoUnsignedWrap());

2131 WideInc->setHasNoSignedWrap(WideInc->hasNoSignedWrap() ||

2132 OrigInc->hasNoSignedWrap());

2133 }

2134 }

2135 }

2136

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

2138 ++NumWidened;

2139

2140 // Traverse the def-use chain using a worklist starting at the original IV.

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

2142

2143 Widened.insert(OrigPhi);

2144 pushNarrowIVUsers(OrigPhi, WidePhi);

2145

2146 while (!NarrowIVUsers.empty()) {

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

2148

2149 // Process a def-use edge. This may replace the use, so don't hold a

2150 // use_iterator across it.

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

2152

2153 // Follow all def-use edges from the previous narrow use.

2154 if (WideUse)

2155 pushNarrowIVUsers(DU.NarrowUse, WideUse);

2156

2157 // widenIVUse may have removed the def-use edge.

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

2159 DeadInsts.emplace_back(DU.NarrowDef);

2160 }

2161

2162 // Attach any debug information to the new PHI.

2163 replaceAllDbgUsesWith(*OrigPhi, *WidePhi, *WidePhi, *DT);

2164

2165 return WidePhi;

2166}

2167

2168/// Calculates control-dependent range for the given def at the given context

2169/// by looking at dominating conditions inside of the loop

2170void WidenIV::calculatePostIncRange(Instruction *NarrowDef,

2171 Instruction *NarrowUser) {

2172 Value *NarrowDefLHS;

2173 const APInt *NarrowDefRHS;

2174 if (!match(NarrowDef, m_NSWAdd(m_Value(NarrowDefLHS),

2175 m_APInt(NarrowDefRHS))) ||

2176 !NarrowDefRHS->isNonNegative())

2177 return;

2178

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

2180 CmpPredicate Pred;

2181 Value *CmpRHS;

2182 if (!match(Condition, m_ICmp(Pred, m_Specific(NarrowDefLHS),

2183 m_Value(CmpRHS))))

2184 return;

2185

2186 CmpPredicate P = TrueDest ? Pred : ICmpInst::getInverseCmpPredicate(Pred);

2187

2188 auto CmpRHSRange = SE->getSignedRange(SE->getSCEV(CmpRHS));

2189 auto CmpConstrainedLHSRange =

2190 ConstantRange::makeAllowedICmpRegion(P, CmpRHSRange);

2191 auto NarrowDefRange = CmpConstrainedLHSRange.addWithNoWrap(

2192 *NarrowDefRHS, OverflowingBinaryOperator::NoSignedWrap);

2193

2194 updatePostIncRangeInfo(NarrowDef, NarrowUser, NarrowDefRange);

2195 };

2196

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

2198 if (!HasGuards)

2199 return;

2200

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

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

2203 Value *C = nullptr;

2204 if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(C))))

2205 UpdateRangeFromCondition(C, /*TrueDest=*/true);

2206 }

2207 };

2208

2209 UpdateRangeFromGuards(NarrowUser);

2210

2211 BasicBlock *NarrowUserBB = NarrowUser->getParent();

2212 // If NarrowUserBB is statically unreachable asking dominator queries may

2213 // yield surprising results. (e.g. the block may not have a dom tree node)

2214 if (!DT->isReachableFromEntry(NarrowUserBB))

2215 return;

2216

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

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

2219 DTB = DTB->getIDom()) {

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

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

2222 UpdateRangeFromGuards(TI);

2223

2224 auto *BI = dyn_cast<BranchInst>(TI);

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

2226 continue;

2227

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

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

2230

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

2232 return BBE.isSingleEdge() &&

2233 DT->dominates(BBE, NarrowUser->getParent());

2234 };

2235

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

2237 UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/true);

2238

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

2240 UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/false);

2241 }

2242}

2243

2244/// Calculates PostIncRangeInfos map for the given IV

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

2246 SmallPtrSet<Instruction *, 16> Visited;

2247 SmallVector<Instruction *, 6> Worklist;

2248 Worklist.push_back(OrigPhi);

2249 Visited.insert(OrigPhi);

2250

2251 while (!Worklist.empty()) {

2252 Instruction *NarrowDef = Worklist.pop_back_val();

2253

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

2255 auto *NarrowUser = cast<Instruction>(U.getUser());

2256

2257 // Don't go looking outside the current loop.

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

2259 if (!NarrowUserLoop || !L->contains(NarrowUserLoop))

2260 continue;

2261

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

2263 continue;

2264

2265 Worklist.push_back(NarrowUser);

2266

2267 calculatePostIncRange(NarrowDef, NarrowUser);

2268 }

2269 }

2270}

2271

2272 PHINode *llvm::createWideIV(const WideIVInfo &WI,

2273 LoopInfo *LI, ScalarEvolution *SE, SCEVExpander &Rewriter,

2274 DominatorTree *DT, SmallVectorImpl<WeakTrackingVH> &DeadInsts,

2275 unsigned &NumElimExt, unsigned &NumWidened,

2276 bool HasGuards, bool UsePostIncrementRanges) {

2277 WidenIV Widener(WI, LI, SE, DT, DeadInsts, HasGuards, UsePostIncrementRanges);

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

2279 NumElimExt = Widener.getNumElimExt();

2280 NumWidened = Widener.getNumWidened();

2281 return WidePHI;

2282}

assert

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

PHI

Rewrite undef for PHI

Definition AMDGPURewriteUndefForPHI.cpp:98

getParent

static const Function * getParent(const Value *V)

Definition BasicAliasAnalysis.cpp:885

D

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

Dominators.h

DEBUG_TYPE

#define DEBUG_TYPE

Definition GenericCycleImpl.h:31

_

#define _

Definition HexagonMCCodeEmitter.cpp:46

IRBuilder.h

IntrinsicInst.h

Users

iv Induction Variable Users

Definition IVUsers.cpp:48

UsePostIncrementRanges

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

Instructions.h

TemplateParamKind::Type

@ Type

Definition ItaniumDemangle.h:1243

WidenIV

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

LoopInfo.h

LoopUtils.h

I

#define I(x, y, z)

Definition MD5.cpp:58

T

#define T

Definition Mips16ISelLowering.cpp:353

Unknown

@ Unknown

Definition NVPTXISelLowering.cpp:5798

P

#define P(N)

PatternMatch.h

ScalarEvolutionExpander.h

GetLoopInvariantInsertPosition

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

Definition SimplifyIndVar.cpp:631

isSimpleIVUser

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

findCommonDominator

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

Find a point in code which dominates all given instructions.

Definition SimplifyIndVar.cpp:116

getInsertPointForUses

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

Determine the insertion point for this user.

Definition SimplifyIndVar.cpp:1182

matchBinaryOp

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

Definition SimplifyIndVar.cpp:1428

SimplifyIndVar.h

SmallVector.h

This file defines the SmallVector class.

Statistic.h

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

STATISTIC

#define STATISTIC(VARNAME, DESC)

Definition Statistic.h:171

Debug.h

LLVM_DEBUG

#define LLVM_DEBUG(...)

Definition Debug.h:114

X

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

Local.h

getOpcode

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

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

Definition VPlanSLP.cpp:247

ValueTracking.h

Rewriter

Virtual Register Rewriter

Definition VirtRegMap.cpp:269

RHS

Value * RHS

Definition X86PartialReduction.cpp:81

LHS

Value * LHS

Definition X86PartialReduction.cpp:80

IV

static const uint32_t IV[8]

Definition blake3_impl.h:83

llvm::APInt::isNonNegative

bool isNonNegative() const

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

Definition APInt.h:335

llvm::APInt::getOneBitSet

static APInt getOneBitSet(unsigned numBits, unsigned BitNo)

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

Definition APInt.h:240

llvm::APInt::uge

bool uge(const APInt &RHS) const

Unsigned greater or equal comparison.

Definition APInt.h:1222

llvm::ArrayRef

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

Definition ArrayRef.h:41

llvm::BasicBlock

LLVM Basic Block Representation.

Definition BasicBlock.h:62

llvm::BasicBlock::getFirstInsertionPt

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

Definition BasicBlock.cpp:393

llvm::BasicBlock::iterator

InstListType::iterator iterator

Instruction iterators...

Definition BasicBlock.h:170

llvm::BasicBlock::getTerminator

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

Definition BasicBlock.h:233

llvm::BinaryOpIntrinsic::getRHS

Value * getRHS() const

Definition IntrinsicInst.h:937

llvm::BinaryOpIntrinsic::isSigned

LLVM_ABI bool isSigned() const

Whether the intrinsic is signed or unsigned.

Definition IntrinsicInst.cpp:827

llvm::BinaryOpIntrinsic::getBinaryOp

LLVM_ABI Instruction::BinaryOps getBinaryOp() const

Returns the binary operation underlying the intrinsic.

Definition IntrinsicInst.cpp:807

llvm::BinaryOpIntrinsic::getLHS

Value * getLHS() const

Definition IntrinsicInst.h:936

llvm::BinaryOperator::getOpcode

BinaryOps getOpcode() const

Definition InstrTypes.h:374

llvm::BinaryOperator::Create

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.

Definition Instructions.cpp:2707

llvm::CmpInst::setPredicate

void setPredicate(Predicate P)

Set the predicate for this instruction to the specified value.

Definition InstrTypes.h:768

llvm::CmpInst::isSigned

bool isSigned() const

Definition InstrTypes.h:930

llvm::CmpInst::getPredicate

Predicate getPredicate() const

Return the predicate for this instruction.

Definition InstrTypes.h:765

llvm::CmpInst::isUnsigned

bool isUnsigned() const

Definition InstrTypes.h:936

llvm::ConstantInt

This is the shared class of boolean and integer constants.

Definition Constants.h:87

llvm::ConstantInt::getFalse

static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)

Definition Constants.cpp:878

llvm::ConstantInt::getBool

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

Definition Constants.cpp:885

llvm::ConstantRange::getActiveBits

LLVM_ABI unsigned getActiveBits() const

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

Definition ConstantRange.cpp:544

llvm::ConstantRange::getUnsignedMin

LLVM_ABI APInt getUnsignedMin() const

Return the smallest unsigned value contained in the ConstantRange.

Definition ConstantRange.cpp:499

llvm::ConstantRange::makeAllowedICmpRegion

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

Definition ConstantRange.cpp:109

llvm::ConstantRange::getMinSignedBits

LLVM_ABI unsigned getMinSignedBits() const

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

Definition ConstantRange.cpp:551

llvm::DenseMapBase::find

iterator find(const_arg_type_t< KeyT > Val)

Definition DenseMap.h:178

llvm::DenseMapBase::try_emplace

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

Definition DenseMap.h:248

llvm::DenseMapBase::count

size_type count(const_arg_type_t< KeyT > Val) const

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

Definition DenseMap.h:174

llvm::DenseMapBase::end

iterator end()

Definition DenseMap.h:81

llvm::DominatorTree

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

Definition Dominators.h:165

llvm::DominatorTree::isReachableFromEntry

LLVM_ABI bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

Definition Dominators.cpp:334

llvm::DominatorTree::findNearestCommonDominator

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

Definition Dominators.cpp:357

llvm::DominatorTree::dominates

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.

Definition Dominators.cpp:135

llvm::ICmpInst::setSameSign

void setSameSign(bool B=true)

Definition Instructions.h:1306

llvm::ICmpInst::getCmpPredicate

CmpPredicate getCmpPredicate() const

Definition Instructions.h:1228

llvm::ICmpInst::getSwappedCmpPredicate

CmpPredicate getSwappedCmpPredicate() const

Definition Instructions.h:1250

llvm::ICmpInst::getInverseCmpPredicate

CmpPredicate getInverseCmpPredicate() const

Definition Instructions.h:1239

llvm::ICmpInst::getSignedPredicate

Predicate getSignedPredicate() const

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

Definition Instructions.h:1270

llvm::ICmpInst::isEquality

static bool isEquality(Predicate P)

Return true if this predicate is either EQ or NE.

Definition Instructions.h:1317

llvm::ICmpInst::getUnsignedPredicate

Predicate getUnsignedPredicate() const

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

Definition Instructions.h:1281

llvm::IVVisitor

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

Definition SimplifyIndVar.h:36

llvm::IVVisitor::anchor

virtual void anchor()

Definition SimplifyIndVar.cpp:1005

llvm::Instruction

Definition Instruction.h:69

llvm::Instruction::setHasNoUnsignedWrap

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.

Definition Instruction.cpp:391

llvm::Instruction::hasNoUnsignedWrap

LLVM_ABI bool hasNoUnsignedWrap() const LLVM_READONLY

Determine whether the no unsigned wrap flag is set.

Definition Instruction.cpp:415

llvm::Instruction::hasNoSignedWrap

LLVM_ABI bool hasNoSignedWrap() const LLVM_READONLY

Determine whether the no signed wrap flag is set.

Definition Instruction.cpp:422

llvm::Instruction::setHasNoSignedWrap

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.

Definition Instruction.cpp:398

llvm::Instruction::getDebugLoc

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

Definition Instruction.h:513

llvm::Instruction::eraseFromParent

LLVM_ABI InstListType::iterator eraseFromParent()

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

Definition Instruction.cpp:108

llvm::Instruction::isExact

LLVM_ABI bool isExact() const LLVM_READONLY

Determine whether the exact flag is set.

Definition Instruction.cpp:589

llvm::Instruction::getOpcode

unsigned getOpcode() const

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

Definition Instruction.h:312

llvm::Instruction::setIsExact

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.

Definition Instruction.cpp:405

llvm::Instruction::BinaryOps

BinaryOps

Definition Instruction.h:998

llvm::Instruction::dropPoisonGeneratingFlags

LLVM_ABI void dropPoisonGeneratingFlags()

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

Definition Instruction.cpp:438

llvm::Instruction::setDebugLoc

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

Definition Instruction.h:510

llvm::LoopBase::getLoopPreheader

BlockT * getLoopPreheader() const

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

Definition GenericLoopInfoImpl.h:210

llvm::LoopInfoBase::getLoopFor

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

Definition GenericLoopInfo.h:606

llvm::LoopInfo

Definition LoopInfo.h:408

llvm::LoopInfo::replacementPreservesLCSSAForm

bool replacementPreservesLCSSAForm(Instruction *From, Value *To)

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

Definition LoopInfo.h:441

llvm::Loop

Represents a single loop in the control flow graph.

Definition LoopInfo.h:40

llvm::OverflowingBinaryOperator::NoSignedWrap

@ NoSignedWrap

Definition Operator.h:83

llvm::OverflowingBinaryOperator::hasNoSignedWrap

bool hasNoSignedWrap() const

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

Definition Operator.h:111

llvm::OverflowingBinaryOperator::hasNoUnsignedWrap

bool hasNoUnsignedWrap() const

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

Definition Operator.h:105

llvm::PHINode

Definition Instructions.h:2639

llvm::PHINode::addIncoming

void addIncoming(Value *V, BasicBlock *BB)

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

Definition Instructions.h:2774

llvm::PHINode::getIncomingValueForBlock

Value * getIncomingValueForBlock(const BasicBlock *BB) const

Definition Instructions.h:2815

llvm::PHINode::Create

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

Definition Instructions.h:2674

llvm::PoisonValue::get

static LLVM_ABI PoisonValue * get(Type *T)

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

Definition Constants.cpp:1888

llvm::SCEVAddRecExpr

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

Definition ScalarEvolutionExpressions.h:348

llvm::SCEVAddRecExpr::getStart

const SCEV * getStart() const

Definition ScalarEvolutionExpressions.h:359

llvm::SCEVAddRecExpr::getStepRecurrence

const SCEV * getStepRecurrence(ScalarEvolution &SE) const

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

Definition ScalarEvolutionExpressions.h:366

llvm::SCEVAddRecExpr::getLoop

const Loop * getLoop() const

Definition ScalarEvolutionExpressions.h:360

llvm::SCEVExpander

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

Definition ScalarEvolutionExpander.h:64

llvm::SCEVExpander::canReuseFlagsFromOriginalIVInc

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

Definition ScalarEvolutionExpander.cpp:870

llvm::SCEV

This class represents an analyzed expression in the program.

Definition ScalarEvolution.h:72

llvm::SCEV::getType

LLVM_ABI Type * getType() const

Return the LLVM type of this SCEV expression.

Definition ScalarEvolution.cpp:383

llvm::SCEV::FlagNSW

@ FlagNSW

Definition ScalarEvolution.h:131

llvm::SCEV::FlagNUW

@ FlagNUW

Definition ScalarEvolution.h:130

llvm::ScalarEvolution

The main scalar evolution driver.

Definition ScalarEvolution.h:448

llvm::ScalarEvolution::getDataLayout

const DataLayout & getDataLayout() const

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

Definition ScalarEvolution.h:1314

llvm::ScalarEvolution::isKnownNonNegative

LLVM_ABI bool isKnownNonNegative(const SCEV *S)

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

Definition ScalarEvolution.cpp:11024

llvm::ScalarEvolution::getNegativeSCEV

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

Return the SCEV object corresponding to -V.

Definition ScalarEvolution.cpp:4609

llvm::ScalarEvolution::isKnownNegative

LLVM_ABI bool isKnownNegative(const SCEV *S)

Test if the given expression is known to be negative.

Definition ScalarEvolution.cpp:11016

llvm::ScalarEvolution::getSCEVAtScope

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.

Definition ScalarEvolution.cpp:9899

llvm::ScalarEvolution::getZero

const SCEV * getZero(Type *Ty)

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

Definition ScalarEvolution.h:667

llvm::ScalarEvolution::willNotOverflow

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

Definition ScalarEvolution.cpp:2303

llvm::ScalarEvolution::getTypeSizeInBits

LLVM_ABI uint64_t getTypeSizeInBits(Type *Ty) const

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

Definition ScalarEvolution.cpp:4488

llvm::ScalarEvolution::getSCEV

LLVM_ABI const SCEV * getSCEV(Value *V)

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

Definition ScalarEvolution.cpp:4587

llvm::ScalarEvolution::getSignedRange

ConstantRange getSignedRange(const SCEV *S)

Determine the signed range for a particular SCEV.

Definition ScalarEvolution.h:1039

llvm::ScalarEvolution::getOne

const SCEV * getOne(Type *Ty)

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

Definition ScalarEvolution.h:670

llvm::ScalarEvolution::evaluatePredicateAt

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.

Definition ScalarEvolution.cpp:11206

llvm::ScalarEvolution::isLoopInvariant

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.

Definition ScalarEvolution.cpp:14205

llvm::ScalarEvolution::getUDivExpr

LLVM_ABI const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)

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

Definition ScalarEvolution.cpp:3437

llvm::ScalarEvolution::getZeroExtendExpr

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

Definition ScalarEvolution.cpp:1556

llvm::ScalarEvolution::isSCEVable

LLVM_ABI bool isSCEVable(Type *Ty) const

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

Definition ScalarEvolution.cpp:4481

llvm::ScalarEvolution::getEffectiveSCEVType

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

Definition ScalarEvolution.cpp:4498

llvm::ScalarEvolution::getUnsignedRange

ConstantRange getUnsignedRange(const SCEV *S)

Determine the unsigned range for a particular SCEV.

Definition ScalarEvolution.h:1023

llvm::ScalarEvolution::forgetValue

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

Definition ScalarEvolution.cpp:8585

llvm::ScalarEvolution::getLoopInvariantPredicate

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

Definition ScalarEvolution.cpp:11292

llvm::ScalarEvolution::getMinusSCEV

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

Return LHS-RHS.

Definition ScalarEvolution.cpp:4689

llvm::ScalarEvolution::getStrengthenedNoWrapFlagsFromBinOp

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

Definition ScalarEvolution.cpp:2380

llvm::ScalarEvolution::getSignExtendExpr

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

Definition ScalarEvolution.cpp:1890

llvm::ScalarEvolution::getMulExpr

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.

Definition ScalarEvolution.cpp:3104

llvm::ScalarEvolution::maskFlags

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

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

Definition ScalarEvolution.h:468

llvm::ScalarEvolution::properlyDominates

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.

Definition ScalarEvolution.cpp:14292

llvm::ScalarEvolution::canReuseInstruction

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.

Definition ScalarEvolution.cpp:4209

llvm::ScalarEvolution::isKnownPredicateAt

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

Definition ScalarEvolution.cpp:11197

llvm::ScalarEvolution::getAddExpr

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.

Definition ScalarEvolution.cpp:2515

llvm::ScalarEvolution::isKnownPredicate

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

Definition ScalarEvolution.cpp:11172

llvm::SelectInst::Create

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

Definition Instructions.h:1715

llvm::SmallPtrSetImplBase::empty

bool empty() const

Definition SmallPtrSet.h:98

llvm::SmallPtrSetImpl::insert

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

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

Definition SmallPtrSet.h:389

llvm::SmallVectorImpl

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

Definition SmallVector.h:574

llvm::SmallVectorImpl::pop_back_val

T pop_back_val()

Definition SmallVector.h:674

llvm::SmallVectorImpl::emplace_back

reference emplace_back(ArgTypes &&... Args)

Definition SmallVector.h:944

llvm::SmallVectorTemplateBase::push_back

void push_back(const T &Elt)

Definition SmallVector.h:417

llvm::SmallVectorTemplateCommon::empty

bool empty() const

Definition SmallVector.h:83

llvm::TargetTransformInfo

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

Definition TargetTransformInfo.h:223

llvm::Type

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

Definition Type.h:45

llvm::Type::isIntegerTy

bool isIntegerTy() const

True if this is an instance of IntegerType.

Definition Type.h:240

llvm::Type::getFPMantissaWidth

LLVM_ABI int getFPMantissaWidth() const

Return the width of the mantissa of this type.

Definition Type.cpp:236

llvm::Use

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

Definition Use.h:35

llvm::User

Definition User.h:44

llvm::User::setOperand

void setOperand(unsigned i, Value *Val)

Definition User.h:237

llvm::User::replaceUsesOfWith

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

Replace uses of one Value with another.

Definition User.cpp:24

llvm::User::getOperand

Value * getOperand(unsigned i) const

Definition User.h:232

llvm::Value

LLVM Value Representation.

Definition Value.h:75

llvm::Value::getType

Type * getType() const

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

Definition Value.h:256

llvm::Value::replaceAllUsesWith

LLVM_ABI void replaceAllUsesWith(Value *V)

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

Definition Value.cpp:546

llvm::Value::users

iterator_range< user_iterator > users()

Definition Value.h:426

llvm::Value::use_empty

bool use_empty() const

Definition Value.h:346

llvm::Value::getContext

LLVM_ABI LLVMContext & getContext() const

All values hold a context through their type.

Definition Value.cpp:1099

llvm::Value::uses

iterator_range< use_iterator > uses()

Definition Value.h:380

llvm::Value::getName

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

Definition Value.cpp:322

llvm::ilist_detail::node_parent_access::getParent

const ParentTy * getParent() const

Definition ilist_node.h:34

llvm::ilist_node_impl::getIterator

self_iterator getIterator()

Definition ilist_node.h:123

Changed

Definition ObjCARCOpts.cpp:2369

llvm_unreachable

#define llvm_unreachable(msg)

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

Definition ErrorHandling.h:164

llvm::AArch64CC::LT

@ LT

Definition AArch64BaseInfo.h:266

llvm::CallingConv::C

@ C

The default llvm calling convention, compatible with C.

Definition CallingConv.h:34

llvm::GraphProgram::Name

Name

Definition GraphWriter.h:51

llvm::ISD::BasicBlock

@ BasicBlock

Various leaf nodes.

Definition ISDOpcodes.h:81

llvm::JumpTable::Simplified

@ Simplified

Definition TargetOptions.h:41

llvm::M68k::MemAddrModeKind::U

@ U

Definition M68kBaseInfo.h:61

llvm::M68k::MemAddrModeKind::V

@ V

Definition M68kBaseInfo.h:63

llvm::M68k::MemAddrModeKind::L

@ L

Definition M68kBaseInfo.h:70

llvm::MipsISD::Ext

@ Ext

Definition MipsISelLowering.h:157

llvm::PatternMatch

Definition PatternMatch.h:47

llvm::PatternMatch::m_AShr

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

Definition PatternMatch.h:1338

llvm::PatternMatch::m_APInt

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

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

Definition PatternMatch.h:311

llvm::PatternMatch::match

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

Definition PatternMatch.h:49

llvm::PatternMatch::m_Specific

specificval_ty m_Specific(const Value *V)

Match if we have a specific specified value.

Definition PatternMatch.h:974

llvm::PatternMatch::m_Intrinsic

IntrinsicID_match m_Intrinsic()

Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))

Definition PatternMatch.h:2796

llvm::PatternMatch::m_SExtLike

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

Match either "sext" or "zext nneg".

Definition PatternMatch.h:2291

llvm::PatternMatch::m_Value

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

Definition PatternMatch.h:105

llvm::PatternMatch::m_NSWAdd

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

Definition PatternMatch.h:1412

llvm::PatternMatch::m_LShr

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

Definition PatternMatch.h:1332

llvm::PatternMatch::m_ICmp

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

Definition PatternMatch.h:1766

llvm::PatternMatch::m_Shl

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

Definition PatternMatch.h:1326

llvm::RISCVFenceField::R

@ R

Definition RISCVBaseInfo.h:462

llvm::SIEncodingFamily::SI

@ SI

Definition SIDefines.h:36

llvm::X86::FirstMacroFusionInstKind::Cmp

@ Cmp

Definition X86BaseInfo.h:109

llvm::dxil::OpCode

OpCode

Definition DXILConstants.h:18

llvm::logicalview::LVAttributeKind::Inserted

@ Inserted

Definition LVOptions.h:109

llvm::logicalview::LVAttributeKind::Zero

@ Zero

Definition LVOptions.h:130

llvm::objcarc::ARCInstKind::User

@ User

could "use" a pointer

Definition ObjCARCInstKind.h:52

llvm::rdf::Def

NodeAddr< DefNode * > Def

Definition RDFGraph.h:384

llvm::rdf::Use

NodeAddr< UseNode * > Use

Definition RDFGraph.h:385

llvm::sandboxir::Instruction

friend class Instruction

Iterator for Instructions in a `BasicBlock.

Definition BasicBlock.h:73

llvm::sframe::Flags

Flags

Definition SFrame.h:39

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition AddressRanges.h:18

llvm::Value

FunctionAddr VTableAddr Value

Definition InstrProf.h:137

llvm::dyn_cast

decltype(auto) dyn_cast(const From &Val)

dyn_cast<X> - Return the argument parameter cast to the specified type.

Definition Casting.h:643

llvm::make_range

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

Convenience function for iterating over sub-ranges.

Definition iterator_range.h:70

llvm::createWideIV

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

llvm::SubDirectoryType::Bin

@ Bin

Definition MSVCPaths.h:26

llvm::isInstructionTriviallyDead

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.

Definition Local.cpp:402

llvm::impliesPoison

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

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

Definition ValueTracking.cpp:7538

llvm::dbgs

LLVM_ABI raw_ostream & dbgs()

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

Definition Debug.cpp:207

llvm::SCEVCheapExpansionBudget

LLVM_ABI cl::opt< unsigned > SCEVCheapExpansionBudget

llvm::simplifyLoopIVs

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

llvm::SmallVector

class LLVM_GSL_OWNER SmallVector

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

Definition SmallVector.h:1129

llvm::isa

bool isa(const From &Val)

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

Definition Casting.h:547

llvm::Key

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

Definition PassManager.h:668

llvm::replaceAllDbgUsesWith

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

Point debug users of From to To or salvage them.

Definition Local.cpp:2414

llvm::simplifyUsersOfIV

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

llvm::TTI

TargetTransformInfo TTI

Definition TargetTransformInfo.h:218

llvm::IRBuilder

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

llvm::Op

DWARFExpression::Operation Op

Definition DWARFExpressionPrinter.cpp:22

llvm::BitWidth

constexpr unsigned BitWidth

Definition BitmaskEnum.h:220

llvm::formLCSSAForInstructions

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.

Definition LCSSA.cpp:308

llvm::cast

decltype(auto) cast(const From &Val)

cast<X> - Return the argument parameter cast to the specified type.

Definition Casting.h:559

std::swap

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

Implement std::swap in terms of BitVector swap.

Definition BitVector.h:869

raw_ostream.h

N