Movatterモバイル変換

11using namespacellvm;

13staticconstchar *ClonedLoopTag ="loop_constrainer.loop.clone";

15#define DEBUG_TYPE "loop-constrainer"

17/// Given a loop with an deccreasing induction variable, is it possible to

18/// safely calculate the bounds of a new loop using the given Predicate.

19staticboolisSafeDecreasingBound(constSCEV *Start,constSCEV *BoundSCEV,

20constSCEV *Step,ICmpInst::Predicate Pred,

21unsigned LatchBrExitIdx,Loop *L,

22ScalarEvolution &SE) {

23if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&

24 Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)

25returnfalse;

27if (!SE.isAvailableAtLoopEntry(BoundSCEV, L))

28returnfalse;

30assert(SE.isKnownNegative(Step) &&"expecting negative step");

32LLVM_DEBUG(dbgs() <<"isSafeDecreasingBound with:\n");

33LLVM_DEBUG(dbgs() <<"Start: " << *Start <<"\n");

34LLVM_DEBUG(dbgs() <<"Step: " << *Step <<"\n");

35LLVM_DEBUG(dbgs() <<"BoundSCEV: " << *BoundSCEV <<"\n");

36LLVM_DEBUG(dbgs() <<"Pred: " << Pred <<"\n");

37LLVM_DEBUG(dbgs() <<"LatchExitBrIdx: " << LatchBrExitIdx <<"\n");

39bool IsSigned = ICmpInst::isSigned(Pred);

40// The predicate that we need to check that the induction variable lies

41// within bounds.

42ICmpInst::Predicate BoundPred =

43 IsSigned ?CmpInst::ICMP_SGT :CmpInst::ICMP_UGT;

45auto StartLG = SE.applyLoopGuards(Start, L);

46auto BoundLG = SE.applyLoopGuards(BoundSCEV, L);

48if (LatchBrExitIdx == 1)

49return SE.isLoopEntryGuardedByCond(L, BoundPred, StartLG, BoundLG);

51assert(LatchBrExitIdx == 0 &&"LatchBrExitIdx should be either 0 or 1");

53constSCEV *StepPlusOne = SE.getAddExpr(Step, SE.getOne(Step->getType()));

54unsignedBitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();

55APInt Min = IsSigned ?APInt::getSignedMinValue(BitWidth)

56 :APInt::getMinValue(BitWidth);

57constSCEV *Limit = SE.getMinusSCEV(SE.getConstant(Min), StepPlusOne);

59constSCEV *MinusOne =

60 SE.getMinusSCEV(BoundLG, SE.getOne(BoundLG->getType()));

62return SE.isLoopEntryGuardedByCond(L, BoundPred, StartLG, MinusOne) &&

63 SE.isLoopEntryGuardedByCond(L, BoundPred, BoundLG, Limit);

64}

66/// Given a loop with an increasing induction variable, is it possible to

67/// safely calculate the bounds of a new loop using the given Predicate.

68staticboolisSafeIncreasingBound(constSCEV *Start,constSCEV *BoundSCEV,

69constSCEV *Step,ICmpInst::Predicate Pred,

70unsigned LatchBrExitIdx,Loop *L,

71ScalarEvolution &SE) {

72if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&

73 Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)

74returnfalse;

76if (!SE.isAvailableAtLoopEntry(BoundSCEV, L))

77returnfalse;

79LLVM_DEBUG(dbgs() <<"isSafeIncreasingBound with:\n");

80LLVM_DEBUG(dbgs() <<"Start: " << *Start <<"\n");

81LLVM_DEBUG(dbgs() <<"Step: " << *Step <<"\n");

82LLVM_DEBUG(dbgs() <<"BoundSCEV: " << *BoundSCEV <<"\n");

83LLVM_DEBUG(dbgs() <<"Pred: " << Pred <<"\n");

84LLVM_DEBUG(dbgs() <<"LatchExitBrIdx: " << LatchBrExitIdx <<"\n");

86bool IsSigned = ICmpInst::isSigned(Pred);

87// The predicate that we need to check that the induction variable lies

88// within bounds.

89ICmpInst::Predicate BoundPred =

90 IsSigned ?CmpInst::ICMP_SLT :CmpInst::ICMP_ULT;

92auto StartLG = SE.applyLoopGuards(Start, L);

93auto BoundLG = SE.applyLoopGuards(BoundSCEV, L);

95if (LatchBrExitIdx == 1)

96return SE.isLoopEntryGuardedByCond(L, BoundPred, StartLG, BoundLG);

98assert(LatchBrExitIdx == 0 &&"LatchBrExitIdx should be 0 or 1");

100constSCEV *StepMinusOne = SE.getMinusSCEV(Step, SE.getOne(Step->getType()));

101unsignedBitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();

102APInt Max = IsSigned ?APInt::getSignedMaxValue(BitWidth)

103 :APInt::getMaxValue(BitWidth);

104constSCEV *Limit = SE.getMinusSCEV(SE.getConstant(Max), StepMinusOne);

105

106return (SE.isLoopEntryGuardedByCond(L, BoundPred, StartLG,

107 SE.getAddExpr(BoundLG, Step)) &&

108 SE.isLoopEntryGuardedByCond(L, BoundPred, BoundLG, Limit));

109}

110

111/// Returns estimate for max latch taken count of the loop of the narrowest

112/// available type. If the latch block has such estimate, it is returned.

113/// Otherwise, we use max exit count of whole loop (that is potentially of wider

114/// type than latch check itself), which is still better than no estimate.

115staticconstSCEV *getNarrowestLatchMaxTakenCountEstimate(ScalarEvolution &SE,

116constLoop &L) {

117constSCEV *FromBlock =

118 SE.getExitCount(&L, L.getLoopLatch(),ScalarEvolution::SymbolicMaximum);

119if (isa<SCEVCouldNotCompute>(FromBlock))

120return SE.getSymbolicMaxBackedgeTakenCount(&L);

121return FromBlock;

122}

123

124std::optional<LoopStructure>

125LoopStructure::parseLoopStructure(ScalarEvolution &SE,Loop &L,

126bool AllowUnsignedLatchCond,

127constchar *&FailureReason) {

128if (!L.isLoopSimplifyForm()) {

129 FailureReason ="loop not in LoopSimplify form";

130return std::nullopt;

131 }

132

133BasicBlock *Latch = L.getLoopLatch();

134assert(Latch &&"Simplified loops only have one latch!");

135

136if (Latch->getTerminator()->getMetadata(ClonedLoopTag)) {

137 FailureReason ="loop has already been cloned";

138return std::nullopt;

139 }

140

141if (!L.isLoopExiting(Latch)) {

142 FailureReason ="no loop latch";

143return std::nullopt;

144 }

145

146BasicBlock *Header = L.getHeader();

147BasicBlock *Preheader = L.getLoopPreheader();

148if (!Preheader) {

149 FailureReason ="no preheader";

150return std::nullopt;

151 }

152

153BranchInst *LatchBr = dyn_cast<BranchInst>(Latch->getTerminator());

154if (!LatchBr ||LatchBr->isUnconditional()) {

155 FailureReason ="latch terminator not conditional branch";

156return std::nullopt;

157 }

158

159unsignedLatchBrExitIdx =LatchBr->getSuccessor(0) ==Header ? 1 : 0;

160

161ICmpInst *ICI = dyn_cast<ICmpInst>(LatchBr->getCondition());

162if (!ICI || !isa<IntegerType>(ICI->getOperand(0)->getType())) {

163 FailureReason ="latch terminator branch not conditional on integral icmp";

164return std::nullopt;

165 }

166

167constSCEV *MaxBETakenCount =getNarrowestLatchMaxTakenCountEstimate(SE, L);

168if (isa<SCEVCouldNotCompute>(MaxBETakenCount)) {

169 FailureReason ="could not compute latch count";

170return std::nullopt;

171 }

172assert(SE.getLoopDisposition(MaxBETakenCount, &L) ==

173ScalarEvolution::LoopInvariant &&

174"loop variant exit count doesn't make sense!");

175

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

177Value *LeftValue = ICI->getOperand(0);

178constSCEV *LeftSCEV = SE.getSCEV(LeftValue);

179IntegerType *IndVarTy = cast<IntegerType>(LeftValue->getType());

180

181Value *RightValue = ICI->getOperand(1);

182constSCEV *RightSCEV = SE.getSCEV(RightValue);

183

184// We canonicalize `ICI` such that `LeftSCEV` is an add recurrence.

185if (!isa<SCEVAddRecExpr>(LeftSCEV)) {

186if (isa<SCEVAddRecExpr>(RightSCEV)) {

187std::swap(LeftSCEV, RightSCEV);

188std::swap(LeftValue, RightValue);

189 Pred =ICmpInst::getSwappedPredicate(Pred);

190 }else {

191 FailureReason ="no add recurrences in the icmp";

192return std::nullopt;

193 }

194 }

195

196auto HasNoSignedWrap = [&](constSCEVAddRecExpr *AR) {

197if (AR->getNoWrapFlags(SCEV::FlagNSW))

198returntrue;

199

200IntegerType *Ty = cast<IntegerType>(AR->getType());

201IntegerType *WideTy =

202IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2);

203

204constSCEVAddRecExpr *ExtendAfterOp =

205 dyn_cast<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy));

206if (ExtendAfterOp) {

207constSCEV *ExtendedStart = SE.getSignExtendExpr(AR->getStart(), WideTy);

208constSCEV *ExtendedStep =

209 SE.getSignExtendExpr(AR->getStepRecurrence(SE), WideTy);

210

211bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&

212 ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;

213

214if (NoSignedWrap)

215returntrue;

216 }

217

218// We may have proved this when computing the sign extension above.

219return AR->getNoWrapFlags(SCEV::FlagNSW) !=SCEV::FlagAnyWrap;

220 };

221

222// `ICI` is interpreted as taking the backedge if the *next* value of the

223// induction variable satisfies some constraint.

224

225constSCEVAddRecExpr *IndVarBase = cast<SCEVAddRecExpr>(LeftSCEV);

226if (IndVarBase->getLoop() != &L) {

227 FailureReason ="LHS in cmp is not an AddRec for this loop";

228return std::nullopt;

229 }

230if (!IndVarBase->isAffine()) {

231 FailureReason ="LHS in icmp not induction variable";

232return std::nullopt;

233 }

234constSCEV *StepRec =IndVarBase->getStepRecurrence(SE);

235if (!isa<SCEVConstant>(StepRec)) {

236 FailureReason ="LHS in icmp not induction variable";

237return std::nullopt;

238 }

239ConstantInt *StepCI = cast<SCEVConstant>(StepRec)->getValue();

240

241if (ICI->isEquality() && !HasNoSignedWrap(IndVarBase)) {

242 FailureReason ="LHS in icmp needs nsw for equality predicates";

243return std::nullopt;

244 }

245

246assert(!StepCI->isZero() &&"Zero step?");

247bool IsIncreasing = !StepCI->isNegative();

248boolIsSignedPredicate;

249constSCEV *StartNext =IndVarBase->getStart();

250constSCEV *Addend = SE.getNegativeSCEV(IndVarBase->getStepRecurrence(SE));

251constSCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);

252constSCEV *Step = SE.getSCEV(StepCI);

253

254constSCEV *FixedRightSCEV =nullptr;

255

256// If RightValue resides within loop (but still being loop invariant),

257// regenerate it as preheader.

258if (auto *I = dyn_cast<Instruction>(RightValue))

259if (L.contains(I->getParent()))

260 FixedRightSCEV = RightSCEV;

261

262if (IsIncreasing) {

263bool DecreasedRightValueByOne =false;

264if (StepCI->isOne()) {

265// Try to turn eq/ne predicates to those we can work with.

266if (Pred ==ICmpInst::ICMP_NE &&LatchBrExitIdx == 1)

267// while (++i != len) { while (++i < len) {

268// ... ---> ...

269// } }

270// If both parts are known non-negative, it is profitable to use

271// unsigned comparison in increasing loop. This allows us to make the

272// comparison check against "RightSCEV + 1" more optimistic.

273if (isKnownNonNegativeInLoop(IndVarStart, &L, SE) &&

274isKnownNonNegativeInLoop(RightSCEV, &L, SE))

275 Pred =ICmpInst::ICMP_ULT;

276else

277 Pred =ICmpInst::ICMP_SLT;

278elseif (Pred ==ICmpInst::ICMP_EQ &&LatchBrExitIdx == 0) {

279// while (true) { while (true) {

280// if (++i == len) ---> if (++i > len - 1)

281// break; break;

282// ... ...

283// } }

284if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) &&

285cannotBeMinInLoop(RightSCEV, &L, SE,/*Signed*/false)) {

286 Pred =ICmpInst::ICMP_UGT;

287 RightSCEV =

288 SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType()));

289 DecreasedRightValueByOne =true;

290 }elseif (cannotBeMinInLoop(RightSCEV, &L, SE,/*Signed*/true)) {

291 Pred =ICmpInst::ICMP_SGT;

292 RightSCEV =

293 SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType()));

294 DecreasedRightValueByOne =true;

295 }

296 }

297 }

298

299bool LTPred = (Pred ==ICmpInst::ICMP_SLT || Pred ==ICmpInst::ICMP_ULT);

300bool GTPred = (Pred ==ICmpInst::ICMP_SGT || Pred ==ICmpInst::ICMP_UGT);

301bool FoundExpectedPred =

302 (LTPred &&LatchBrExitIdx == 1) || (GTPred &&LatchBrExitIdx == 0);

303

304if (!FoundExpectedPred) {

305 FailureReason ="expected icmp slt semantically, found something else";

306return std::nullopt;

307 }

308

309IsSignedPredicate =ICmpInst::isSigned(Pred);

310if (!IsSignedPredicate && !AllowUnsignedLatchCond) {

311 FailureReason ="unsigned latch conditions are explicitly prohibited";

312return std::nullopt;

313 }

314

315if (!isSafeIncreasingBound(IndVarStart, RightSCEV, Step, Pred,

316LatchBrExitIdx, &L, SE)) {

317 FailureReason ="Unsafe loop bounds";

318return std::nullopt;

319 }

320if (LatchBrExitIdx == 0) {

321// We need to increase the right value unless we have already decreased

322// it virtually when we replaced EQ with SGT.

323if (!DecreasedRightValueByOne)

324 FixedRightSCEV =

325 SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));

326 }else {

327assert(!DecreasedRightValueByOne &&

328"Right value can be decreased only for LatchBrExitIdx == 0!");

329 }

330 }else {

331bool IncreasedRightValueByOne =false;

332if (StepCI->isMinusOne()) {

333// Try to turn eq/ne predicates to those we can work with.

334if (Pred ==ICmpInst::ICMP_NE &&LatchBrExitIdx == 1)

335// while (--i != len) { while (--i > len) {

336// ... ---> ...

337// } }

338// We intentionally don't turn the predicate into UGT even if we know

339// that both operands are non-negative, because it will only pessimize

340// our check against "RightSCEV - 1".

341 Pred =ICmpInst::ICMP_SGT;

342elseif (Pred ==ICmpInst::ICMP_EQ &&LatchBrExitIdx == 0) {

343// while (true) { while (true) {

344// if (--i == len) ---> if (--i < len + 1)

345// break; break;

346// ... ...

347// } }

348if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) &&

349cannotBeMaxInLoop(RightSCEV, &L, SE,/* Signed */false)) {

350 Pred =ICmpInst::ICMP_ULT;

351 RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));

352 IncreasedRightValueByOne =true;

353 }elseif (cannotBeMaxInLoop(RightSCEV, &L, SE,/* Signed */true)) {

354 Pred =ICmpInst::ICMP_SLT;

355 RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));

356 IncreasedRightValueByOne =true;

357 }

358 }

359 }

360

361bool LTPred = (Pred ==ICmpInst::ICMP_SLT || Pred ==ICmpInst::ICMP_ULT);

362bool GTPred = (Pred ==ICmpInst::ICMP_SGT || Pred ==ICmpInst::ICMP_UGT);

363

364bool FoundExpectedPred =

365 (GTPred &&LatchBrExitIdx == 1) || (LTPred &&LatchBrExitIdx == 0);

366

367if (!FoundExpectedPred) {

368 FailureReason ="expected icmp sgt semantically, found something else";

369return std::nullopt;

370 }

371

372IsSignedPredicate =

373 Pred ==ICmpInst::ICMP_SLT || Pred ==ICmpInst::ICMP_SGT;

374

375if (!IsSignedPredicate && !AllowUnsignedLatchCond) {

376 FailureReason ="unsigned latch conditions are explicitly prohibited";

377return std::nullopt;

378 }

379

380if (!isSafeDecreasingBound(IndVarStart, RightSCEV, Step, Pred,

381LatchBrExitIdx, &L, SE)) {

382 FailureReason ="Unsafe bounds";

383return std::nullopt;

384 }

385

386if (LatchBrExitIdx == 0) {

387// We need to decrease the right value unless we have already increased

388// it virtually when we replaced EQ with SLT.

389if (!IncreasedRightValueByOne)

390 FixedRightSCEV =

391 SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType()));

392 }else {

393assert(!IncreasedRightValueByOne &&

394"Right value can be increased only for LatchBrExitIdx == 0!");

395 }

396 }

397BasicBlock *LatchExit =LatchBr->getSuccessor(LatchBrExitIdx);

398

399assert(!L.contains(LatchExit) &&"expected an exit block!");

400constDataLayout &DL = Preheader->getDataLayout();

401SCEVExpander Expander(SE,DL,"loop-constrainer");

402Instruction *Ins = Preheader->getTerminator();

403

404if (FixedRightSCEV)

405 RightValue =

406 Expander.expandCodeFor(FixedRightSCEV, FixedRightSCEV->getType(), Ins);

407

408Value *IndVarStartV = Expander.expandCodeFor(IndVarStart, IndVarTy, Ins);

409 IndVarStartV->setName("indvar.start");

410

411LoopStructure Result;

412

413 Result.Tag ="main";

414 Result.Header =Header;

415 Result.Latch =Latch;

416 Result.LatchBr =LatchBr;

417 Result.LatchExit =LatchExit;

418 Result.LatchBrExitIdx =LatchBrExitIdx;

419 Result.IndVarStart = IndVarStartV;

420 Result.IndVarStep = StepCI;

421 Result.IndVarBase = LeftValue;

422 Result.IndVarIncreasing = IsIncreasing;

423 Result.LoopExitAt = RightValue;

424 Result.IsSignedPredicate =IsSignedPredicate;

425 Result.ExitCountTy = cast<IntegerType>(MaxBETakenCount->getType());

426

427 FailureReason =nullptr;

428

429return Result;

430}

431

432// Add metadata to the loop L to disable loop optimizations. Callers need to

433// confirm that optimizing loop L is not beneficial.

434staticvoidDisableAllLoopOptsOnLoop(Loop &L) {

435// We do not care about any existing loopID related metadata for L, since we

436// are setting all loop metadata to false.

437LLVMContext &Context = L.getHeader()->getContext();

438// Reserve first location for self reference to the LoopID metadata node.

439MDNode *Dummy =MDNode::get(Context, {});

440MDNode *DisableUnroll =MDNode::get(

441 Context, {MDString::get(Context,"llvm.loop.unroll.disable")});

442Metadata *FalseVal =

443ConstantAsMetadata::get(ConstantInt::get(Type::getInt1Ty(Context), 0));

444MDNode *DisableVectorize =MDNode::get(

445 Context,

446 {MDString::get(Context,"llvm.loop.vectorize.enable"), FalseVal});

447MDNode *DisableLICMVersioning =MDNode::get(

448 Context, {MDString::get(Context,"llvm.loop.licm_versioning.disable")});

449MDNode *DisableDistribution =MDNode::get(

450 Context,

451 {MDString::get(Context,"llvm.loop.distribute.enable"), FalseVal});

452MDNode *NewLoopID =

453MDNode::get(Context, {Dummy, DisableUnroll, DisableVectorize,

454 DisableLICMVersioning, DisableDistribution});

455// Set operand 0 to refer to the loop id itself.

456 NewLoopID->replaceOperandWith(0, NewLoopID);

457 L.setLoopID(NewLoopID);

458}

459

460LoopConstrainer::LoopConstrainer(Loop &L,LoopInfo &LI,

461function_ref<void(Loop *,bool)> LPMAddNewLoop,

462constLoopStructure &LS,ScalarEvolution &SE,

463DominatorTree &DT,Type *T,SubRanges SR)

464 :F(*L.getHeader()->getParent()), Ctx(L.getHeader()->getContext()), SE(SE),

465 DT(DT), LI(LI), LPMAddNewLoop(LPMAddNewLoop), OriginalLoop(L), RangeTy(T),

466 MainLoopStructure(LS), SR(SR) {}

467

468void LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result,

469constchar *Tag) const{

470for (BasicBlock *BB : OriginalLoop.getBlocks()) {

471BasicBlock *Clone =CloneBasicBlock(BB, Result.Map,Twine(".") +Tag, &F);

472 Result.Blocks.push_back(Clone);

473 Result.Map[BB] = Clone;

474 }

475

476auto GetClonedValue = [&Result](Value *V) {

477assert(V &&"null values not in domain!");

478auto It = Result.Map.find(V);

479if (It == Result.Map.end())

480return V;

481returnstatic_cast<Value *>(It->second);

482 };

483

484auto *ClonedLatch =

485 cast<BasicBlock>(GetClonedValue(OriginalLoop.getLoopLatch()));

486 ClonedLatch->getTerminator()->setMetadata(ClonedLoopTag,

487MDNode::get(Ctx, {}));

488

489Result.Structure = MainLoopStructure.map(GetClonedValue);

490Result.Structure.Tag =Tag;

491

492for (unsigned i = 0, e =Result.Blocks.size(); i != e; ++i) {

493BasicBlock *ClonedBB =Result.Blocks[i];

494BasicBlock *OriginalBB = OriginalLoop.getBlocks()[i];

495

496assert(Result.Map[OriginalBB] == ClonedBB &&"invariant!");

497

498for (Instruction &I : *ClonedBB)

499RemapInstruction(&I,Result.Map,

500RF_NoModuleLevelChanges |RF_IgnoreMissingLocals);

501

502// Exit blocks will now have one more predecessor and their PHI nodes need

503// to be edited to reflect that. No phi nodes need to be introduced because

504// the loop is in LCSSA.

505

506for (auto *SBB :successors(OriginalBB)) {

507if (OriginalLoop.contains(SBB))

508continue;// not an exit block

509

510for (PHINode &PN :SBB->phis()) {

511Value *OldIncoming = PN.getIncomingValueForBlock(OriginalBB);

512 PN.addIncoming(GetClonedValue(OldIncoming), ClonedBB);

513 SE.forgetLcssaPhiWithNewPredecessor(&OriginalLoop, &PN);

514 }

515 }

516 }

517}

518

519LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(

520constLoopStructure &LS,BasicBlock *Preheader,Value *ExitSubloopAt,

521BasicBlock *ContinuationBlock) const{

522// We start with a loop with a single latch:

523//

524// +--------------------+

525// | |

526// | preheader |

527// | |

528// +--------+-----------+

529// | ----------------\

530 // | / |

531// +--------v----v------+ |

532// | | |

533// | header | |

534// | | |

535// +--------------------+ |

536// |

537// ..... |

538// |

539// +--------------------+ |

540// | | |

541// | latch >----------/

542// | |

543// +-------v------------+

544// |

545// |

546// | +--------------------+

547// | | |

548// +---> original exit |

549// | |

550// +--------------------+

551//

552// We change the control flow to look like

553//

554//

555// +--------------------+

556// | |

557// | preheader >-------------------------+

558// | | |

559// +--------v-----------+ |

560// | /-------------+ |

561// | / | |

562// +--------v--v--------+ | |

563// | | | |

564// | header | | +--------+ |

565// | | | | | |

566// +--------------------+ | | +-----v-----v-----------+

567// | | | |

568// | | | .pseudo.exit |

569// | | | |

570// | | +-----------v-----------+

571// | | |

572// ..... | | |

573// | | +--------v-------------+

574// +--------------------+ | | | |

575// | | | | | ContinuationBlock |

576// | latch >------+ | | |

577// | | | +----------------------+

578// +---------v----------+ |

579// | |

580// | |

581// | +---------------^-----+

582// | | |

583// +-----> .exit.selector |

584// | |

585// +----------v----------+

586// |

587// +--------------------+ |

588// | | |

589// | original exit <----+

590// | |

591// +--------------------+

592

593 RewrittenRangeInfo RRI;

594

595BasicBlock *BBInsertLocation =LS.Latch->getNextNode();

596 RRI.ExitSelector =BasicBlock::Create(Ctx,Twine(LS.Tag) +".exit.selector",

597 &F, BBInsertLocation);

598 RRI.PseudoExit =BasicBlock::Create(Ctx,Twine(LS.Tag) +".pseudo.exit", &F,

599 BBInsertLocation);

600

601BranchInst *PreheaderJump = cast<BranchInst>(Preheader->getTerminator());

602bool Increasing =LS.IndVarIncreasing;

603bool IsSignedPredicate =LS.IsSignedPredicate;

604

605IRBuilder<>B(PreheaderJump);

606auto NoopOrExt = [&](Value *V) {

607if (V->getType() == RangeTy)

608return V;

609return IsSignedPredicate ?B.CreateSExt(V, RangeTy,"wide." +V->getName())

610 :B.CreateZExt(V, RangeTy,"wide." +V->getName());

611 };

612

613// EnterLoopCond - is it okay to start executing this `LS'?

614Value *EnterLoopCond =nullptr;

615auto Pred =

616 Increasing

617 ? (IsSignedPredicate ?ICmpInst::ICMP_SLT :ICmpInst::ICMP_ULT)

618 : (IsSignedPredicate ?ICmpInst::ICMP_SGT :ICmpInst::ICMP_UGT);

619Value *IndVarStart = NoopOrExt(LS.IndVarStart);

620 EnterLoopCond =B.CreateICmp(Pred, IndVarStart, ExitSubloopAt);

621

622B.CreateCondBr(EnterLoopCond,LS.Header, RRI.PseudoExit);

623 PreheaderJump->eraseFromParent();

624

625LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector);

626B.SetInsertPoint(LS.LatchBr);

627Value *IndVarBase = NoopOrExt(LS.IndVarBase);

628Value *TakeBackedgeLoopCond =B.CreateICmp(Pred, IndVarBase, ExitSubloopAt);

629

630Value *CondForBranch =LS.LatchBrExitIdx == 1

631 ? TakeBackedgeLoopCond

632 :B.CreateNot(TakeBackedgeLoopCond);

633

634LS.LatchBr->setCondition(CondForBranch);

635

636B.SetInsertPoint(RRI.ExitSelector);

637

638// IterationsLeft - are there any more iterations left, given the original

639// upper bound on the induction variable? If not, we branch to the "real"

640// exit.

641Value *LoopExitAt = NoopOrExt(LS.LoopExitAt);

642Value *IterationsLeft =B.CreateICmp(Pred, IndVarBase, LoopExitAt);

643B.CreateCondBr(IterationsLeft, RRI.PseudoExit,LS.LatchExit);

644

645BranchInst *BranchToContinuation =

646BranchInst::Create(ContinuationBlock, RRI.PseudoExit);

647

648// We emit PHI nodes into `RRI.PseudoExit' that compute the "latest" value of

649// each of the PHI nodes in the loop header. This feeds into the initial

650// value of the same PHI nodes if/when we continue execution.

651for (PHINode &PN :LS.Header->phis()) {

652PHINode *NewPHI =PHINode::Create(PN.getType(), 2, PN.getName() +".copy",

653 BranchToContinuation->getIterator());

654

655 NewPHI->addIncoming(PN.getIncomingValueForBlock(Preheader), Preheader);

656 NewPHI->addIncoming(PN.getIncomingValueForBlock(LS.Latch),

657 RRI.ExitSelector);

658 RRI.PHIValuesAtPseudoExit.push_back(NewPHI);

659 }

660

661 RRI.IndVarEnd =PHINode::Create(IndVarBase->getType(), 2,"indvar.end",

662 BranchToContinuation->getIterator());

663 RRI.IndVarEnd->addIncoming(IndVarStart, Preheader);

664 RRI.IndVarEnd->addIncoming(IndVarBase, RRI.ExitSelector);

665

666// The latch exit now has a branch from `RRI.ExitSelector' instead of

667// `LS.Latch'. The PHI nodes need to be updated to reflect that.

668LS.LatchExit->replacePhiUsesWith(LS.Latch, RRI.ExitSelector);

669

670return RRI;

671}

672

673void LoopConstrainer::rewriteIncomingValuesForPHIs(

674LoopStructure &LS,BasicBlock *ContinuationBlock,

675const LoopConstrainer::RewrittenRangeInfo &RRI) const{

676unsigned PHIIndex = 0;

677for (PHINode &PN :LS.Header->phis())

678 PN.setIncomingValueForBlock(ContinuationBlock,

679 RRI.PHIValuesAtPseudoExit[PHIIndex++]);

680

681LS.IndVarStart = RRI.IndVarEnd;

682}

683

684BasicBlock *LoopConstrainer::createPreheader(constLoopStructure &LS,

685BasicBlock *OldPreheader,

686constchar *Tag) const{

687BasicBlock *Preheader =BasicBlock::Create(Ctx,Tag, &F,LS.Header);

688BranchInst::Create(LS.Header, Preheader);

689

690LS.Header->replacePhiUsesWith(OldPreheader, Preheader);

691

692return Preheader;

693}

694

695void LoopConstrainer::addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs) {

696Loop *ParentLoop = OriginalLoop.getParentLoop();

697if (!ParentLoop)

698return;

699

700for (BasicBlock *BB : BBs)

701 ParentLoop->addBasicBlockToLoop(BB, LI);

702}

703

704Loop *LoopConstrainer::createClonedLoopStructure(Loop *Original,Loop *Parent,

705ValueToValueMapTy &VM,

706bool IsSubloop) {

707Loop &New = *LI.AllocateLoop();

708if (Parent)

709 Parent->addChildLoop(&New);

710else

711 LI.addTopLevelLoop(&New);

712 LPMAddNewLoop(&New, IsSubloop);

713

714// Add all of the blocks in Original to the new loop.

715for (auto *BB : Original->blocks())

716if (LI.getLoopFor(BB) == Original)

717New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), LI);

718

719// Add all of the subloops to the new loop.

720for (Loop *SubLoop : *Original)

721 createClonedLoopStructure(SubLoop, &New, VM,/* IsSubloop */true);

722

723return &New;

724}

725

726boolLoopConstrainer::run() {

727BasicBlock *Preheader = OriginalLoop.getLoopPreheader();

728assert(Preheader !=nullptr &&"precondition!");

729

730 OriginalPreheader = Preheader;

731 MainLoopPreheader = Preheader;

732bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;

733bool Increasing = MainLoopStructure.IndVarIncreasing;

734IntegerType *IVTy = cast<IntegerType>(RangeTy);

735

736SCEVExpander Expander(SE, F.getDataLayout(),"loop-constrainer");

737Instruction *InsertPt = OriginalPreheader->getTerminator();

738

739// It would have been better to make `PreLoop' and `PostLoop'

740// `std::optional<ClonedLoop>'s, but `ValueToValueMapTy' does not have a copy

741// constructor.

742 ClonedLoop PreLoop, PostLoop;

743bool NeedsPreLoop =

744 Increasing ? SR.LowLimit.has_value() : SR.HighLimit.has_value();

745bool NeedsPostLoop =

746 Increasing ? SR.HighLimit.has_value() : SR.LowLimit.has_value();

747

748Value *ExitPreLoopAt =nullptr;

749Value *ExitMainLoopAt =nullptr;

750constSCEVConstant *MinusOneS =

751 cast<SCEVConstant>(SE.getConstant(IVTy, -1,true/* isSigned */));

752

753if (NeedsPreLoop) {

754constSCEV *ExitPreLoopAtSCEV =nullptr;

755

756if (Increasing)

757 ExitPreLoopAtSCEV = *SR.LowLimit;

758elseif (cannotBeMinInLoop(*SR.HighLimit, &OriginalLoop, SE,

759 IsSignedPredicate))

760 ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);

761else {

762LLVM_DEBUG(dbgs() <<"could not prove no-overflow when computing "

763 <<"preloop exit limit. HighLimit = "

764 << *(*SR.HighLimit) <<"\n");

765returnfalse;

766 }

767

768if (!Expander.isSafeToExpandAt(ExitPreLoopAtSCEV, InsertPt)) {

769LLVM_DEBUG(dbgs() <<"could not prove that it is safe to expand the"

770 <<" preloop exit limit " << *ExitPreLoopAtSCEV

771 <<" at block " << InsertPt->getParent()->getName()

772 <<"\n");

773returnfalse;

774 }

775

776 ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt);

777 ExitPreLoopAt->setName("exit.preloop.at");

778 }

779

780if (NeedsPostLoop) {

781constSCEV *ExitMainLoopAtSCEV =nullptr;

782

783if (Increasing)

784 ExitMainLoopAtSCEV = *SR.HighLimit;

785elseif (cannotBeMinInLoop(*SR.LowLimit, &OriginalLoop, SE,

786 IsSignedPredicate))

787 ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);

788else {

789LLVM_DEBUG(dbgs() <<"could not prove no-overflow when computing "

790 <<"mainloop exit limit. LowLimit = "

791 << *(*SR.LowLimit) <<"\n");

792returnfalse;

793 }

794

795if (!Expander.isSafeToExpandAt(ExitMainLoopAtSCEV, InsertPt)) {

796LLVM_DEBUG(dbgs() <<"could not prove that it is safe to expand the"

797 <<" main loop exit limit " << *ExitMainLoopAtSCEV

798 <<" at block " << InsertPt->getParent()->getName()

799 <<"\n");

800returnfalse;

801 }

802

803 ExitMainLoopAt = Expander.expandCodeFor(ExitMainLoopAtSCEV, IVTy, InsertPt);

804 ExitMainLoopAt->setName("exit.mainloop.at");

805 }

806

807// We clone these ahead of time so that we don't have to deal with changing

808// and temporarily invalid IR as we transform the loops.

809if (NeedsPreLoop)

810 cloneLoop(PreLoop,"preloop");

811if (NeedsPostLoop)

812 cloneLoop(PostLoop,"postloop");

813

814 RewrittenRangeInfo PreLoopRRI;

815

816if (NeedsPreLoop) {

817 Preheader->getTerminator()->replaceUsesOfWith(MainLoopStructure.Header,

818 PreLoop.Structure.Header);

819

820 MainLoopPreheader =

821 createPreheader(MainLoopStructure, Preheader,"mainloop");

822 PreLoopRRI = changeIterationSpaceEnd(PreLoop.Structure, Preheader,

823 ExitPreLoopAt, MainLoopPreheader);

824 rewriteIncomingValuesForPHIs(MainLoopStructure, MainLoopPreheader,

825 PreLoopRRI);

826 }

827

828BasicBlock *PostLoopPreheader =nullptr;

829 RewrittenRangeInfo PostLoopRRI;

830

831if (NeedsPostLoop) {

832 PostLoopPreheader =

833 createPreheader(PostLoop.Structure, Preheader,"postloop");

834 PostLoopRRI = changeIterationSpaceEnd(MainLoopStructure, MainLoopPreheader,

835 ExitMainLoopAt, PostLoopPreheader);

836 rewriteIncomingValuesForPHIs(PostLoop.Structure, PostLoopPreheader,

837 PostLoopRRI);

838 }

839

840BasicBlock *NewMainLoopPreheader =

841 MainLoopPreheader != Preheader ? MainLoopPreheader :nullptr;

842BasicBlock *NewBlocks[] = {PostLoopPreheader, PreLoopRRI.PseudoExit,

843 PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit,

844 PostLoopRRI.ExitSelector, NewMainLoopPreheader};

845

846// Some of the above may be nullptr, filter them out before passing to

847// addToParentLoopIfNeeded.

848auto NewBlocksEnd =

849 std::remove(std::begin(NewBlocks), std::end(NewBlocks),nullptr);

850

851 addToParentLoopIfNeeded(ArrayRef(std::begin(NewBlocks), NewBlocksEnd));

852

853 DT.recalculate(F);

854

855// We need to first add all the pre and post loop blocks into the loop

856// structures (as part of createClonedLoopStructure), and then update the

857// LCSSA form and LoopSimplifyForm. This is necessary for correctly updating

858// LI when LoopSimplifyForm is generated.

859Loop *PreL =nullptr, *PostL =nullptr;

860if (!PreLoop.Blocks.empty()) {

861 PreL = createClonedLoopStructure(&OriginalLoop,

862 OriginalLoop.getParentLoop(), PreLoop.Map,

863/* IsSubLoop */false);

864 }

865

866if (!PostLoop.Blocks.empty()) {

867 PostL =

868 createClonedLoopStructure(&OriginalLoop, OriginalLoop.getParentLoop(),

869 PostLoop.Map,/* IsSubLoop */false);

870 }

871

872// This function canonicalizes the loop into Loop-Simplify and LCSSA forms.

873auto CanonicalizeLoop = [&](Loop *L,bool IsOriginalLoop) {

874formLCSSARecursively(*L, DT, &LI, &SE);

875simplifyLoop(L, &DT, &LI, &SE,nullptr,nullptr,true);

876// Pre/post loops are slow paths, we do not need to perform any loop

877// optimizations on them.

878if (!IsOriginalLoop)

879DisableAllLoopOptsOnLoop(*L);

880 };

881if (PreL)

882 CanonicalizeLoop(PreL,false);

883if (PostL)

884 CanonicalizeLoop(PostL,false);

885 CanonicalizeLoop(&OriginalLoop,true);

886

887 /// At this point:

888 /// - We've broken a "main loop" out of the loop in a way that the "main loop"

889 /// runs with the induction variable in a subset of [Begin, End).

890 /// - There is no overflow when computing "main loop" exit limit.

891 /// - Max latch taken count of the loop is limited.

892 /// It guarantees that induction variable will not overflow iterating in the

893 /// "main loop".

894if (isa<OverflowingBinaryOperator>(MainLoopStructure.IndVarBase))

895if (IsSignedPredicate)

896 cast<BinaryOperator>(MainLoopStructure.IndVarBase)

897 ->setHasNoSignedWrap(true);

898 /// TODO: support unsigned predicate.

899 /// To add NUW flag we need to prove that both operands of BO are

900 /// non-negative. E.g:

901 /// ...

902 /// %iv.next = add nsw i32 %iv, -1

903 /// %cmp = icmp ult i32 %iv.next, %n

904 /// br i1 %cmp, label %loopexit, label %loop

905 ///

906 /// -1 is MAX_UINT in terms of unsigned int. Adding anything but zero will

907 /// overflow, therefore NUW flag is not legal here.

908

909returntrue;

910}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Definition:ARMSLSHardening.cpp:73

getParent

static const Function * getParent(const Value *V)

Definition:BasicAliasAnalysis.cpp:863

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

Cloning.h

LLVM_DEBUG

#define LLVM_DEBUG(...)

Definition:Debug.h:106

Dominators.h

ClonedLoopTag

static const char * ClonedLoopTag

Definition:LoopConstrainer.cpp:13

getNarrowestLatchMaxTakenCountEstimate

static const SCEV * getNarrowestLatchMaxTakenCountEstimate(ScalarEvolution &SE, const Loop &L)

Returns estimate for max latch taken count of the loop of the narrowest available type.

Definition:LoopConstrainer.cpp:115

isSafeDecreasingBound

static bool isSafeDecreasingBound(const SCEV *Start, const SCEV *BoundSCEV, const SCEV *Step, ICmpInst::Predicate Pred, unsigned LatchBrExitIdx, Loop *L, ScalarEvolution &SE)

Given a loop with an deccreasing induction variable, is it possible to safely calculate the bounds of...

Definition:LoopConstrainer.cpp:19

DisableAllLoopOptsOnLoop

static void DisableAllLoopOptsOnLoop(Loop &L)

Definition:LoopConstrainer.cpp:434

isSafeIncreasingBound

static bool isSafeIncreasingBound(const SCEV *Start, const SCEV *BoundSCEV, const SCEV *Step, ICmpInst::Predicate Pred, unsigned LatchBrExitIdx, Loop *L, ScalarEvolution &SE)

Given a loop with an increasing induction variable, is it possible to safely calculate the bounds of ...

Definition:LoopConstrainer.cpp:68

#define F(x, y, z)

Definition:MD5.cpp:55

#define I(x, y, z)

Definition:MD5.cpp:58

assert

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

ScalarEvolutionExpander.h

ScalarEvolutionExpressions.h

ScalarEvolution.h

llvm::APInt

Class for arbitrary precision integers.

Definition:APInt.h:78

llvm::APInt::getMaxValue

static APInt getMaxValue(unsigned numBits)

Gets maximum unsigned value of APInt for specific bit width.

Definition:APInt.h:206

llvm::APInt::getSignedMaxValue

static APInt getSignedMaxValue(unsigned numBits)

Gets maximum signed value of APInt for a specific bit width.

Definition:APInt.h:209

llvm::APInt::getMinValue

static APInt getMinValue(unsigned numBits)

Gets minimum unsigned value of APInt for a specific bit width.

Definition:APInt.h:216

llvm::APInt::getSignedMinValue

static APInt getSignedMinValue(unsigned numBits)

Gets minimum signed value of APInt for a specific bit width.

Definition:APInt.h:219

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

llvm::BasicBlock::Create

static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)

Creates a new BasicBlock.

Definition:BasicBlock.h:213

llvm::BasicBlock::getDataLayout

const DataLayout & getDataLayout() const

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

Definition:BasicBlock.cpp:296

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

llvm::BranchInst

Conditional or Unconditional Branch instruction.

Definition:Instructions.h:3016

llvm::BranchInst::Create

static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)

Definition:Instructions.h:3072

llvm::BranchInst::getSuccessor

BasicBlock * getSuccessor(unsigned i) const

Definition:Instructions.h:3104

llvm::BranchInst::isUnconditional

bool isUnconditional() const

Definition:Instructions.h:3089

llvm::BranchInst::getCondition

Value * getCondition() const

Definition:Instructions.h:3092

llvm::CmpInst::Predicate

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

Definition:InstrTypes.h:673

llvm::CmpInst::ICMP_SLT

@ ICMP_SLT

signed less than

Definition:InstrTypes.h:702

llvm::CmpInst::ICMP_UGT

@ ICMP_UGT

unsigned greater than

Definition:InstrTypes.h:696

llvm::CmpInst::ICMP_SGT

@ ICMP_SGT

signed greater than

Definition:InstrTypes.h:700

llvm::CmpInst::ICMP_ULT

@ ICMP_ULT

unsigned less than

Definition:InstrTypes.h:698

llvm::CmpInst::ICMP_EQ

@ ICMP_EQ

equal

Definition:InstrTypes.h:694

llvm::CmpInst::ICMP_NE

@ ICMP_NE

not equal

Definition:InstrTypes.h:695

llvm::CmpInst::isSigned

bool isSigned() const

Definition:InstrTypes.h:928

llvm::CmpInst::getSwappedPredicate

Predicate getSwappedPredicate() const

For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.

Definition:InstrTypes.h:825

llvm::CmpInst::getPredicate

Predicate getPredicate() const

Return the predicate for this instruction.

Definition:InstrTypes.h:763

llvm::ConstantAsMetadata::get

static ConstantAsMetadata * get(Constant *C)

Definition:Metadata.h:532

llvm::ConstantInt

This is the shared class of boolean and integer constants.

Definition:Constants.h:83

llvm::ConstantInt::isMinusOne

bool isMinusOne() const

This function will return true iff every bit in this constant is set to true.

Definition:Constants.h:220

llvm::ConstantInt::isOne

bool isOne() const

This is just a convenience method to make client code smaller for a common case.

Definition:Constants.h:214

llvm::ConstantInt::isNegative

bool isNegative() const

Definition:Constants.h:203

llvm::ConstantInt::isZero

bool isZero() const

This is just a convenience method to make client code smaller for a common code.

Definition:Constants.h:208

llvm::ConstantInt::getValue

const APInt & getValue() const

Return the constant as an APInt value reference.

Definition:Constants.h:148

llvm::DataLayout

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

Definition:DataLayout.h:63

llvm::DominatorTreeBase::recalculate

void recalculate(ParentType &Func)

recalculate - compute a dominator tree for the given function

Definition:GenericDomTree.h:859

llvm::DominatorTree

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

Definition:Dominators.h:162

llvm::Function::getDataLayout

const DataLayout & getDataLayout() const

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

Definition:Function.cpp:373

llvm::ICmpInst

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

Definition:Instructions.h:1158

llvm::ICmpInst::isEquality

static bool isEquality(Predicate P)

Return true if this predicate is either EQ or NE.

Definition:Instructions.h:1285

llvm::IRBuilder

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

Definition:IRBuilder.h:2705

llvm::Instruction

Definition:Instruction.h:68

llvm::Instruction::eraseFromParent

InstListType::iterator eraseFromParent()

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

Definition:Instruction.cpp:94

llvm::Instruction::getMetadata

MDNode * getMetadata(unsigned KindID) const

Get the metadata of given kind attached to this Instruction.

Definition:Instruction.h:407

llvm::IntegerType

Class to represent integer types.

Definition:DerivedTypes.h:42

llvm::IntegerType::get

static IntegerType * get(LLVMContext &C, unsigned NumBits)

This static method is the primary way of constructing an IntegerType.

Definition:Type.cpp:311

llvm::IntegerType::getBitWidth

unsigned getBitWidth() const

Get the number of bits in this IntegerType.

Definition:DerivedTypes.h:74

llvm::LLVMContext

This is an important class for using LLVM in a threaded context.

Definition:LLVMContext.h:67

llvm::LoopBase::contains

bool contains(const LoopT *L) const

Return true if the specified loop is contained within in this loop.

Definition:GenericLoopInfo.h:124

llvm::LoopBase::getLoopLatch

BlockT * getLoopLatch() const

If there is a single latch block for this loop, return it.

Definition:GenericLoopInfoImpl.h:256

llvm::LoopBase::addBasicBlockToLoop

void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)

This method is used by other analyses to update loop information.

Definition:GenericLoopInfoImpl.h:282

llvm::LoopBase::blocks

iterator_range< block_iterator > blocks() const

Definition:GenericLoopInfo.h:180

llvm::LoopBase::addChildLoop

void addChildLoop(LoopT *NewChild)

Add the specified loop to be a child of this loop.

Definition:GenericLoopInfo.h:391

llvm::LoopBase::getLoopPreheader

BlockT * getLoopPreheader() const

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

Definition:GenericLoopInfoImpl.h:210

llvm::LoopBase::getBlocks

ArrayRef< BlockT * > getBlocks() const

Get a list of the basic blocks which make up this loop.

Definition:GenericLoopInfo.h:173

llvm::LoopBase::getParentLoop

LoopT * getParentLoop() const

Return the parent loop if it exists or nullptr for top level loops.

Definition:GenericLoopInfo.h:99

llvm::LoopConstrainer::LoopConstrainer

LoopConstrainer(Loop &L, LoopInfo &LI, function_ref< void(Loop *, bool)> LPMAddNewLoop, const LoopStructure &LS, ScalarEvolution &SE, DominatorTree &DT, Type *T, SubRanges SR)

Definition:LoopConstrainer.cpp:460

llvm::LoopConstrainer::run

bool run()

Definition:LoopConstrainer.cpp:726

llvm::LoopInfoBase::addTopLevelLoop

void addTopLevelLoop(LoopT *New)

This adds the specified loop to the collection of top-level loops.

Definition:GenericLoopInfo.h:663

llvm::LoopInfoBase::AllocateLoop

LoopT * AllocateLoop(ArgsTy &&...Args)

Definition:GenericLoopInfo.h:570

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

llvm::Loop

Represents a single loop in the control flow graph.

Definition:LoopInfo.h:39

llvm::MDNode

Metadata node.

Definition:Metadata.h:1073

llvm::MDNode::replaceOperandWith

void replaceOperandWith(unsigned I, Metadata *New)

Replace a specific operand.

Definition:Metadata.cpp:1077

llvm::MDNode::get

static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)

Definition:Metadata.h:1549

llvm::MDString::get

static MDString * get(LLVMContext &Context, StringRef Str)

Definition:Metadata.cpp:606

llvm::Metadata

Root of the metadata hierarchy.

Definition:Metadata.h:62

llvm::PHINode

Definition:Instructions.h:2600

llvm::PHINode::addIncoming

void addIncoming(Value *V, BasicBlock *BB)

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

Definition:Instructions.h:2735

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

llvm::SCEVAddRecExpr

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

Definition:ScalarEvolutionExpressions.h:347

llvm::SCEVAddRecExpr::getStart

const SCEV * getStart() const

Definition:ScalarEvolutionExpressions.h:358

llvm::SCEVAddRecExpr::getStepRecurrence

const SCEV * getStepRecurrence(ScalarEvolution &SE) const

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

Definition:ScalarEvolutionExpressions.h:365

llvm::SCEVConstant

This class represents a constant integer value.

Definition:ScalarEvolutionExpressions.h:60

llvm::SCEVExpander

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

Definition:ScalarEvolutionExpander.h:63

llvm::SCEVExpander::isSafeToExpandAt

bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint) const

Return true if the given expression is safe to expand in the sense that all materialized values are d...

Definition:ScalarEvolutionExpander.cpp:2359

llvm::SCEVExpander::expandCodeFor

Value * expandCodeFor(const SCEV *SH, Type *Ty, BasicBlock::iterator I)

Insert code to directly compute the specified SCEV expression into the program.

Definition:ScalarEvolutionExpander.cpp:1443

llvm::SCEV

This class represents an analyzed expression in the program.

Definition:ScalarEvolution.h:71

llvm::SCEV::getType

Type * getType() const

Return the LLVM type of this SCEV expression.

Definition:ScalarEvolution.cpp:386

llvm::SCEV::FlagAnyWrap

@ FlagAnyWrap

Definition:ScalarEvolution.h:127

llvm::SCEV::FlagNSW

@ FlagNSW

Definition:ScalarEvolution.h:130

llvm::SCEV::FlagNUW

@ FlagNUW

Definition:ScalarEvolution.h:129

llvm::ScalarEvolution

The main scalar evolution driver.

Definition:ScalarEvolution.h:447

llvm::ScalarEvolution::getNegativeSCEV

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

Return the SCEV object corresponding to -V.

Definition:ScalarEvolution.cpp:4569

llvm::ScalarEvolution::isKnownNegative

bool isKnownNegative(const SCEV *S)

Test if the given expression is known to be negative.

Definition:ScalarEvolution.cpp:10944

llvm::ScalarEvolution::isLoopEntryGuardedByCond

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

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

Definition:ScalarEvolution.cpp:11721

llvm::ScalarEvolution::getConstant

const SCEV * getConstant(ConstantInt *V)

Definition:ScalarEvolution.cpp:473

llvm::ScalarEvolution::getSCEV

const SCEV * getSCEV(Value *V)

Return a SCEV expression for the full generality of the specified expression.

Definition:ScalarEvolution.cpp:4547

llvm::ScalarEvolution::getOne

const SCEV * getOne(Type *Ty)

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

Definition:ScalarEvolution.h:656

llvm::ScalarEvolution::getLoopDisposition

LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)

Return the "disposition" of the given SCEV with respect to the given loop.

Definition:ScalarEvolution.cpp:14010

llvm::ScalarEvolution::getMinusSCEV

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

Return LHS-RHS.

Definition:ScalarEvolution.cpp:4655

llvm::ScalarEvolution::LoopInvariant

@ LoopInvariant

The SCEV is loop-invariant.

Definition:ScalarEvolution.h:454

llvm::ScalarEvolution::forgetLcssaPhiWithNewPredecessor

void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)

Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...

Definition:ScalarEvolution.cpp:8557

llvm::ScalarEvolution::isAvailableAtLoopEntry

bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)

Determine if the SCEV can be evaluated at loop's entry.

Definition:ScalarEvolution.cpp:2521

llvm::ScalarEvolution::getExitCount

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

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

Definition:ScalarEvolution.cpp:8314

llvm::ScalarEvolution::getSignExtendExpr

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

Definition:ScalarEvolution.cpp:1900

llvm::ScalarEvolution::SymbolicMaximum

@ SymbolicMaximum

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

Definition:ScalarEvolution.h:865

llvm::ScalarEvolution::applyLoopGuards

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

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

Definition:ScalarEvolution.cpp:15967

llvm::ScalarEvolution::getAddExpr

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

llvm::ScalarEvolution::getSymbolicMaxBackedgeTakenCount

const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)

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

Definition:ScalarEvolution.h:922

llvm::Twine

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

Definition:Twine.h:81

llvm::Type

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

Definition:Type.h:45

llvm::Type::getInt1Ty

static IntegerType * getInt1Ty(LLVMContext &C)

llvm::Type::getContext

LLVMContext & getContext() const

Return the LLVMContext in which this type was uniqued.

Definition:Type.h:128

llvm::User::replaceUsesOfWith

bool replaceUsesOfWith(Value *From, Value *To)

Replace uses of one Value with another.

Definition:User.cpp:21

llvm::User::getOperand

Value * getOperand(unsigned i) const

Definition:User.h:228

llvm::ValueMap< const Value *, WeakTrackingVH >

llvm::Value

LLVM Value Representation.

Definition:Value.h:74

llvm::Value::getType

Type * getType() const

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

Definition:Value.h:255

llvm::Value::setName

void setName(const Twine &Name)

Change the name of the value.

Definition:Value.cpp:377

llvm::function_ref

An efficient, type-erasing, non-owning reference to a callable.

Definition:STLFunctionalExtras.h:37

llvm::ilist_detail::node_parent_access::getParent

const ParentTy * getParent() const

Definition:ilist_node.h:32

llvm::ilist_node_impl::getIterator

self_iterator getIterator()

Definition:ilist_node.h:132

llvm::AArch64CC::LS

@ LS

Definition:AArch64BaseInfo.h:264

llvm::M68k::MemAddrModeKind::V

@ V

llvm::X86ISD::SBB

@ SBB

Definition:X86ISelLowering.h:409

llvm::ms_demangle::IntrinsicFunctionKind::New

@ New

llvm::ms_demangle::QualifierMangleMode::Result

@ Result

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::simplifyLoop

bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)

Simplify each loop in a loop nest recursively.

Definition:LoopSimplify.cpp:697

llvm::successors

auto successors(const MachineBasicBlock *BB)

Definition:MachineBasicBlock.h:1376

llvm::formLCSSARecursively

bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)

Put a loop nest into LCSSA form.

Definition:LCSSA.cpp:465

llvm::cannotBeMaxInLoop

bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool Signed)

Returns true if S is defined and never is equal to signed/unsigned max.

Definition:LoopUtils.cpp:1427

llvm::RF_IgnoreMissingLocals

@ RF_IgnoreMissingLocals

If this flag is set, the remapper ignores missing function-local entries (Argument,...

Definition:ValueMapper.h:96

llvm::RF_NoModuleLevelChanges

@ RF_NoModuleLevelChanges

If this flag is set, the remapper knows that only local values within a function (such as an instruct...

Definition:ValueMapper.h:78

llvm::dbgs

raw_ostream & dbgs()

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

Definition:Debug.cpp:163

llvm::RemapInstruction

void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataSetTy *IdentityMD=nullptr)

Convert the instruction operands from referencing the current values into those specified by VM.

Definition:ValueMapper.h:277

llvm::CloneBasicBlock

BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr)

Return a copy of the specified basic block, but without embedding the block into a particular functio...

Definition:CloneFunction.cpp:44

llvm::BitWidth

constexpr unsigned BitWidth

Definition:BitmaskEnum.h:217

llvm::HighlightColor::Tag

@ Tag

llvm::cannotBeMinInLoop

bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool Signed)

Returns true if S is defined and never is equal to signed/unsigned min.

Definition:LoopUtils.cpp:1416

llvm::isKnownNonNegativeInLoop