LLVM 19.0.0git
LoopConstrainer.cpp
Go to the documentation of this file.
10
11using namespace llvm;
12
13static const char *ClonedLoopTag = "loop_constrainer.loop.clone";
14
15#define DEBUG_TYPE "loop-constrainer"
16
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.
19static bool isSafeDecreasingBound(const SCEV *Start, const SCEV *BoundSCEV,
20 const SCEV *Step, ICmpInst::Predicate Pred,
21 unsigned LatchBrExitIdx, Loop *L,
22 ScalarEvolution &SE) {
23 if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&
24 Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
25 return false;
26
27 if (!SE.isAvailableAtLoopEntry(BoundSCEV, L))
28 return false;
29
30 assert(SE.isKnownNegative(Step) && "expecting negative step");
31
32 LLVM_DEBUG(dbgs() << "isSafeDecreasingBound with:\n");
33 LLVM_DEBUG(dbgs() << "Start: " << *Start << "\n");
34 LLVM_DEBUG(dbgs() << "Step: " << *Step << "\n");
35 LLVM_DEBUG(dbgs() << "BoundSCEV: " << *BoundSCEV << "\n");
36 LLVM_DEBUG(dbgs() << "Pred: " << Pred << "\n");
37 LLVM_DEBUG(dbgs() << "LatchExitBrIdx: " << LatchBrExitIdx << "\n");
38
39 bool IsSigned = ICmpInst::isSigned(Pred);
40 // The predicate that we need to check that the induction variable lies
41 // within bounds.
42 ICmpInst::Predicate BoundPred =
44
45 auto StartLG = SE.applyLoopGuards(Start, L);
46 auto BoundLG = SE.applyLoopGuards(BoundSCEV, L);
47
48 if (LatchBrExitIdx == 1)
49 return SE.isLoopEntryGuardedByCond(L, BoundPred, StartLG, BoundLG);
50
51 assert(LatchBrExitIdx == 0 && "LatchBrExitIdx should be either 0 or 1");
52
53 const SCEV *StepPlusOne = SE.getAddExpr(Step, SE.getOne(Step->getType()));
54 unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
57 const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Min), StepPlusOne);
58
59 const SCEV *MinusOne =
60 SE.getMinusSCEV(BoundLG, SE.getOne(BoundLG->getType()));
61
62 return SE.isLoopEntryGuardedByCond(L, BoundPred, StartLG, MinusOne) &&
63 SE.isLoopEntryGuardedByCond(L, BoundPred, BoundLG, Limit);
64}
65
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.
68static bool isSafeIncreasingBound(const SCEV *Start, const SCEV *BoundSCEV,
69 const SCEV *Step, ICmpInst::Predicate Pred,
70 unsigned LatchBrExitIdx, Loop *L,
71 ScalarEvolution &SE) {
72 if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&
73 Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
74 return false;
75
76 if (!SE.isAvailableAtLoopEntry(BoundSCEV, L))
77 return false;
78
79 LLVM_DEBUG(dbgs() << "isSafeIncreasingBound with:\n");
80 LLVM_DEBUG(dbgs() << "Start: " << *Start << "\n");
81 LLVM_DEBUG(dbgs() << "Step: " << *Step << "\n");
82 LLVM_DEBUG(dbgs() << "BoundSCEV: " << *BoundSCEV << "\n");
83 LLVM_DEBUG(dbgs() << "Pred: " << Pred << "\n");
84 LLVM_DEBUG(dbgs() << "LatchExitBrIdx: " << LatchBrExitIdx << "\n");
85
86 bool IsSigned = ICmpInst::isSigned(Pred);
87 // The predicate that we need to check that the induction variable lies
88 // within bounds.
89 ICmpInst::Predicate BoundPred =
91
92 auto StartLG = SE.applyLoopGuards(Start, L);
93 auto BoundLG = SE.applyLoopGuards(BoundSCEV, L);
94
95 if (LatchBrExitIdx == 1)
96 return SE.isLoopEntryGuardedByCond(L, BoundPred, StartLG, BoundLG);
97
98 assert(LatchBrExitIdx == 0 && "LatchBrExitIdx should be 0 or 1");
99
100 const SCEV *StepMinusOne = SE.getMinusSCEV(Step, SE.getOne(Step->getType()));
101 unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
102 APInt Max = IsSigned ? APInt::getSignedMaxValue(BitWidth)
104 const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Max), StepMinusOne);
105
106 return (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.
116 const Loop &L) {
117 const SCEV *FromBlock =
118 SE.getExitCount(&L, L.getLoopLatch(), ScalarEvolution::SymbolicMaximum);
119 if (isa<SCEVCouldNotCompute>(FromBlock))
121 return FromBlock;
122}
123
124std::optional<LoopStructure>
126 bool AllowUnsignedLatchCond,
127 const char *&FailureReason) {
128 if (!L.isLoopSimplifyForm()) {
129 FailureReason = "loop not in LoopSimplify form";
130 return std::nullopt;
131 }
132
133 BasicBlock *Latch = L.getLoopLatch();
134 assert(Latch && "Simplified loops only have one latch!");
135
137 FailureReason = "loop has already been cloned";
138 return std::nullopt;
139 }
140
141 if (!L.isLoopExiting(Latch)) {
142 FailureReason = "no loop latch";
143 return std::nullopt;
144 }
145
146 BasicBlock *Header = L.getHeader();
147 BasicBlock *Preheader = L.getLoopPreheader();
148 if (!Preheader) {
149 FailureReason = "no preheader";
150 return std::nullopt;
151 }
152
153 BranchInst *LatchBr = dyn_cast<BranchInst>(Latch->getTerminator());
154 if (!LatchBr || LatchBr->isUnconditional()) {
155 FailureReason = "latch terminator not conditional branch";
156 return std::nullopt;
157 }
158
159 unsigned LatchBrExitIdx = LatchBr->getSuccessor(0) == Header ? 1 : 0;
160
161 ICmpInst *ICI = dyn_cast<ICmpInst>(LatchBr->getCondition());
162 if (!ICI || !isa<IntegerType>(ICI->getOperand(0)->getType())) {
163 FailureReason = "latch terminator branch not conditional on integral icmp";
164 return std::nullopt;
165 }
166
167 const SCEV *MaxBETakenCount = getNarrowestLatchMaxTakenCountEstimate(SE, L);
168 if (isa<SCEVCouldNotCompute>(MaxBETakenCount)) {
169 FailureReason = "could not compute latch count";
170 return std::nullopt;
171 }
172 assert(SE.getLoopDisposition(MaxBETakenCount, &L) ==
174 "loop variant exit count doesn't make sense!");
175
176 ICmpInst::Predicate Pred = ICI->getPredicate();
177 Value *LeftValue = ICI->getOperand(0);
178 const SCEV *LeftSCEV = SE.getSCEV(LeftValue);
179 IntegerType *IndVarTy = cast<IntegerType>(LeftValue->getType());
180
181 Value *RightValue = ICI->getOperand(1);
182 const SCEV *RightSCEV = SE.getSCEV(RightValue);
183
184 // We canonicalize `ICI` such that `LeftSCEV` is an add recurrence.
185 if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
186 if (isa<SCEVAddRecExpr>(RightSCEV)) {
187 std::swap(LeftSCEV, RightSCEV);
188 std::swap(LeftValue, RightValue);
190 } else {
191 FailureReason = "no add recurrences in the icmp";
192 return std::nullopt;
193 }
194 }
195
196 auto HasNoSignedWrap = [&](const SCEVAddRecExpr *AR) {
197 if (AR->getNoWrapFlags(SCEV::FlagNSW))
198 return true;
199
200 IntegerType *Ty = cast<IntegerType>(AR->getType());
201 IntegerType *WideTy =
202 IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2);
203
204 const SCEVAddRecExpr *ExtendAfterOp =
205 dyn_cast<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy));
206 if (ExtendAfterOp) {
207 const SCEV *ExtendedStart = SE.getSignExtendExpr(AR->getStart(), WideTy);
208 const SCEV *ExtendedStep =
209 SE.getSignExtendExpr(AR->getStepRecurrence(SE), WideTy);
210
211 bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
212 ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
213
214 if (NoSignedWrap)
215 return true;
216 }
217
218 // We may have proved this when computing the sign extension above.
219 return 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
225 const SCEVAddRecExpr *IndVarBase = cast<SCEVAddRecExpr>(LeftSCEV);
226 if (IndVarBase->getLoop() != &L) {
227 FailureReason = "LHS in cmp is not an AddRec for this loop";
228 return std::nullopt;
229 }
230 if (!IndVarBase->isAffine()) {
231 FailureReason = "LHS in icmp not induction variable";
232 return std::nullopt;
233 }
234 const SCEV *StepRec = IndVarBase->getStepRecurrence(SE);
235 if (!isa<SCEVConstant>(StepRec)) {
236 FailureReason = "LHS in icmp not induction variable";
237 return std::nullopt;
238 }
239 ConstantInt *StepCI = cast<SCEVConstant>(StepRec)->getValue();
240
241 if (ICI->isEquality() && !HasNoSignedWrap(IndVarBase)) {
242 FailureReason = "LHS in icmp needs nsw for equality predicates";
243 return std::nullopt;
244 }
245
246 assert(!StepCI->isZero() && "Zero step?");
247 bool IsIncreasing = !StepCI->isNegative();
249 const SCEV *StartNext = IndVarBase->getStart();
250 const SCEV *Addend = SE.getNegativeSCEV(IndVarBase->getStepRecurrence(SE));
251 const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);
252 const SCEV *Step = SE.getSCEV(StepCI);
253
254 const SCEV *FixedRightSCEV = nullptr;
255
256 // If RightValue resides within loop (but still being loop invariant),
257 // regenerate it as preheader.
258 if (auto *I = dyn_cast<Instruction>(RightValue))
259 if (L.contains(I->getParent()))
260 FixedRightSCEV = RightSCEV;
261
262 if (IsIncreasing) {
263 bool DecreasedRightValueByOne = false;
264 if (StepCI->isOne()) {
265 // Try to turn eq/ne predicates to those we can work with.
266 if (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.
274 isKnownNonNegativeInLoop(RightSCEV, &L, SE))
275 Pred = ICmpInst::ICMP_ULT;
276 else
277 Pred = ICmpInst::ICMP_SLT;
278 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
279 // while (true) { while (true) {
280 // if (++i == len) ---> if (++i > len - 1)
281 // break; break;
282 // ... ...
283 // } }
284 if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) &&
285 cannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/ false)) {
286 Pred = ICmpInst::ICMP_UGT;
287 RightSCEV =
288 SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType()));
289 DecreasedRightValueByOne = true;
290 } else if (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
299 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
300 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
301 bool FoundExpectedPred =
302 (LTPred && LatchBrExitIdx == 1) || (GTPred && LatchBrExitIdx == 0);
303
304 if (!FoundExpectedPred) {
305 FailureReason = "expected icmp slt semantically, found something else";
306 return std::nullopt;
307 }
308
310 if (!IsSignedPredicate && !AllowUnsignedLatchCond) {
311 FailureReason = "unsigned latch conditions are explicitly prohibited";
312 return std::nullopt;
313 }
314
315 if (!isSafeIncreasingBound(IndVarStart, RightSCEV, Step, Pred,
316 LatchBrExitIdx, &L, SE)) {
317 FailureReason = "Unsafe loop bounds";
318 return std::nullopt;
319 }
320 if (LatchBrExitIdx == 0) {
321 // We need to increase the right value unless we have already decreased
322 // it virtually when we replaced EQ with SGT.
323 if (!DecreasedRightValueByOne)
324 FixedRightSCEV =
325 SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
326 } else {
327 assert(!DecreasedRightValueByOne &&
328 "Right value can be decreased only for LatchBrExitIdx == 0!");
329 }
330 } else {
331 bool IncreasedRightValueByOne = false;
332 if (StepCI->isMinusOne()) {
333 // Try to turn eq/ne predicates to those we can work with.
334 if (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;
342 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
343 // while (true) { while (true) {
344 // if (--i == len) ---> if (--i < len + 1)
345 // break; break;
346 // ... ...
347 // } }
348 if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) &&
349 cannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ false)) {
350 Pred = ICmpInst::ICMP_ULT;
351 RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
352 IncreasedRightValueByOne = true;
353 } else if (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
361 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
362 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
363
364 bool FoundExpectedPred =
365 (GTPred && LatchBrExitIdx == 1) || (LTPred && LatchBrExitIdx == 0);
366
367 if (!FoundExpectedPred) {
368 FailureReason = "expected icmp sgt semantically, found something else";
369 return std::nullopt;
370 }
371
373 Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
374
375 if (!IsSignedPredicate && !AllowUnsignedLatchCond) {
376 FailureReason = "unsigned latch conditions are explicitly prohibited";
377 return std::nullopt;
378 }
379
380 if (!isSafeDecreasingBound(IndVarStart, RightSCEV, Step, Pred,
381 LatchBrExitIdx, &L, SE)) {
382 FailureReason = "Unsafe bounds";
383 return std::nullopt;
384 }
385
386 if (LatchBrExitIdx == 0) {
387 // We need to decrease the right value unless we have already increased
388 // it virtually when we replaced EQ with SLT.
389 if (!IncreasedRightValueByOne)
390 FixedRightSCEV =
391 SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType()));
392 } else {
393 assert(!IncreasedRightValueByOne &&
394 "Right value can be increased only for LatchBrExitIdx == 0!");
395 }
396 }
398
399 assert(!L.contains(LatchExit) && "expected an exit block!");
400 const DataLayout &DL = Preheader->getModule()->getDataLayout();
401 SCEVExpander Expander(SE, DL, "loop-constrainer");
402 Instruction *Ins = Preheader->getTerminator();
403
404 if (FixedRightSCEV)
405 RightValue =
406 Expander.expandCodeFor(FixedRightSCEV, FixedRightSCEV->getType(), Ins);
407
408 Value *IndVarStartV = Expander.expandCodeFor(IndVarStart, IndVarTy, Ins);
409 IndVarStartV->setName("indvar.start");
410
411 LoopStructure 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
429 return 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.
435 // We do not care about any existing loopID related metadata for L, since we
436 // are setting all loop metadata to false.
437 LLVMContext &Context = L.getHeader()->getContext();
438 // Reserve first location for self reference to the LoopID metadata node.
439 MDNode *Dummy = MDNode::get(Context, {});
440 MDNode *DisableUnroll = MDNode::get(
441 Context, {MDString::get(Context, "llvm.loop.unroll.disable")});
442 Metadata *FalseVal =
443 ConstantAsMetadata::get(ConstantInt::get(Type::getInt1Ty(Context), 0));
444 MDNode *DisableVectorize = MDNode::get(
445 Context,
446 {MDString::get(Context, "llvm.loop.vectorize.enable"), FalseVal});
447 MDNode *DisableLICMVersioning = MDNode::get(
448 Context, {MDString::get(Context, "llvm.loop.licm_versioning.disable")});
449 MDNode *DisableDistribution = MDNode::get(
450 Context,
451 {MDString::get(Context, "llvm.loop.distribute.enable"), FalseVal});
452 MDNode *NewLoopID =
453 MDNode::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
461 function_ref<void(Loop *, bool)> LPMAddNewLoop,
462 const LoopStructure &LS, ScalarEvolution &SE,
463 DominatorTree &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,
469 const char *Tag) const {
470 for (BasicBlock *BB : OriginalLoop.getBlocks()) {
471 BasicBlock *Clone = CloneBasicBlock(BB, Result.Map, Twine(".") + Tag, &F);
472 Result.Blocks.push_back(Clone);
473 Result.Map[BB] = Clone;
474 }
475
476 auto GetClonedValue = [&Result](Value *V) {
477 assert(V && "null values not in domain!");
478 auto It = Result.Map.find(V);
479 if (It == Result.Map.end())
480 return V;
481 return static_cast<Value *>(It->second);
482 };
483
484 auto *ClonedLatch =
485 cast<BasicBlock>(GetClonedValue(OriginalLoop.getLoopLatch()));
486 ClonedLatch->getTerminator()->setMetadata(ClonedLoopTag,
487 MDNode::get(Ctx, {}));
488
489 Result.Structure = MainLoopStructure.map(GetClonedValue);
490 Result.Structure.Tag = Tag;
491
492 for (unsigned i = 0, e = Result.Blocks.size(); i != e; ++i) {
493 BasicBlock *ClonedBB = Result.Blocks[i];
494 BasicBlock *OriginalBB = OriginalLoop.getBlocks()[i];
495
496 assert(Result.Map[OriginalBB] == ClonedBB && "invariant!");
497
498 for (Instruction &I : *ClonedBB)
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
506 for (auto *SBB : successors(OriginalBB)) {
507 if (OriginalLoop.contains(SBB))
508 continue; // not an exit block
509
510 for (PHINode &PN : SBB->phis()) {
511 Value *OldIncoming = PN.getIncomingValueForBlock(OriginalBB);
512 PN.addIncoming(GetClonedValue(OldIncoming), ClonedBB);
513 SE.forgetValue(&PN);
514 }
515 }
516 }
517}
518
519LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(
520 const LoopStructure &LS, BasicBlock *Preheader, Value *ExitSubloopAt,
521 BasicBlock *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
595 BasicBlock *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
601 BranchInst *PreheaderJump = cast<BranchInst>(Preheader->getTerminator());
602 bool Increasing = LS.IndVarIncreasing;
603 bool IsSignedPredicate = LS.IsSignedPredicate;
604
605 IRBuilder<> B(PreheaderJump);
606 auto NoopOrExt = [&](Value *V) {
607 if (V->getType() == RangeTy)
608 return V;
609 return 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'?
614 Value *EnterLoopCond = nullptr;
615 auto Pred =
616 Increasing
617 ? (IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT)
618 : (IsSignedPredicate ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT);
619 Value *IndVarStart = NoopOrExt(LS.IndVarStart);
620 EnterLoopCond = B.CreateICmp(Pred, IndVarStart, ExitSubloopAt);
621
622 B.CreateCondBr(EnterLoopCond, LS.Header, RRI.PseudoExit);
623 PreheaderJump->eraseFromParent();
624
625 LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector);
626 B.SetInsertPoint(LS.LatchBr);
627 Value *IndVarBase = NoopOrExt(LS.IndVarBase);
628 Value *TakeBackedgeLoopCond = B.CreateICmp(Pred, IndVarBase, ExitSubloopAt);
629
630 Value *CondForBranch = LS.LatchBrExitIdx == 1
631 ? TakeBackedgeLoopCond
632 : B.CreateNot(TakeBackedgeLoopCond);
633
634 LS.LatchBr->setCondition(CondForBranch);
635
636 B.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.
641 Value *LoopExitAt = NoopOrExt(LS.LoopExitAt);
642 Value *IterationsLeft = B.CreateICmp(Pred, IndVarBase, LoopExitAt);
643 B.CreateCondBr(IterationsLeft, RRI.PseudoExit, LS.LatchExit);
644
645 BranchInst *BranchToContinuation =
646 BranchInst::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.
651 for (PHINode &PN : LS.Header->phis()) {
652 PHINode *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.
668 LS.LatchExit->replacePhiUsesWith(LS.Latch, RRI.ExitSelector);
669
670 return RRI;
671}
672
673void LoopConstrainer::rewriteIncomingValuesForPHIs(
674 LoopStructure &LS, BasicBlock *ContinuationBlock,
675 const LoopConstrainer::RewrittenRangeInfo &RRI) const {
676 unsigned PHIIndex = 0;
677 for (PHINode &PN : LS.Header->phis())
678 PN.setIncomingValueForBlock(ContinuationBlock,
679 RRI.PHIValuesAtPseudoExit[PHIIndex++]);
680
681 LS.IndVarStart = RRI.IndVarEnd;
682}
683
684BasicBlock *LoopConstrainer::createPreheader(const LoopStructure &LS,
685 BasicBlock *OldPreheader,
686 const char *Tag) const {
687 BasicBlock *Preheader = BasicBlock::Create(Ctx, Tag, &F, LS.Header);
688 BranchInst::Create(LS.Header, Preheader);
689
690 LS.Header->replacePhiUsesWith(OldPreheader, Preheader);
691
692 return Preheader;
693}
694
695void LoopConstrainer::addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs) {
696 Loop *ParentLoop = OriginalLoop.getParentLoop();
697 if (!ParentLoop)
698 return;
699
700 for (BasicBlock *BB : BBs)
701 ParentLoop->addBasicBlockToLoop(BB, LI);
702}
703
704Loop *LoopConstrainer::createClonedLoopStructure(Loop *Original, Loop *Parent,
706 bool IsSubloop) {
707 Loop &New = *LI.AllocateLoop();
708 if (Parent)
709 Parent->addChildLoop(&New);
710 else
711 LI.addTopLevelLoop(&New);
712 LPMAddNewLoop(&New, IsSubloop);
713
714 // Add all of the blocks in Original to the new loop.
715 for (auto *BB : Original->blocks())
716 if (LI.getLoopFor(BB) == Original)
717 New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), LI);
718
719 // Add all of the subloops to the new loop.
720 for (Loop *SubLoop : *Original)
721 createClonedLoopStructure(SubLoop, &New, VM, /* IsSubloop */ true);
722
723 return &New;
724}
725
727 BasicBlock *Preheader = OriginalLoop.getLoopPreheader();
728 assert(Preheader != nullptr && "precondition!");
729
730 OriginalPreheader = Preheader;
731 MainLoopPreheader = Preheader;
732 bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;
733 bool Increasing = MainLoopStructure.IndVarIncreasing;
734 IntegerType *IVTy = cast<IntegerType>(RangeTy);
735
736 SCEVExpander Expander(SE, F.getParent()->getDataLayout(), "loop-constrainer");
737 Instruction *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;
743 bool NeedsPreLoop =
744 Increasing ? SR.LowLimit.has_value() : SR.HighLimit.has_value();
745 bool NeedsPostLoop =
746 Increasing ? SR.HighLimit.has_value() : SR.LowLimit.has_value();
747
748 Value *ExitPreLoopAt = nullptr;
749 Value *ExitMainLoopAt = nullptr;
750 const SCEVConstant *MinusOneS =
751 cast<SCEVConstant>(SE.getConstant(IVTy, -1, true /* isSigned */));
752
753 if (NeedsPreLoop) {
754 const SCEV *ExitPreLoopAtSCEV = nullptr;
755
756 if (Increasing)
757 ExitPreLoopAtSCEV = *SR.LowLimit;
758 else if (cannotBeMinInLoop(*SR.HighLimit, &OriginalLoop, SE,
759 IsSignedPredicate))
760 ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);
761 else {
762 LLVM_DEBUG(dbgs() << "could not prove no-overflow when computing "
763 << "preloop exit limit. HighLimit = "
764 << *(*SR.HighLimit) << "\n");
765 return false;
766 }
767
768 if (!Expander.isSafeToExpandAt(ExitPreLoopAtSCEV, InsertPt)) {
769 LLVM_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");
773 return false;
774 }
775
776 ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt);
777 ExitPreLoopAt->setName("exit.preloop.at");
778 }
779
780 if (NeedsPostLoop) {
781 const SCEV *ExitMainLoopAtSCEV = nullptr;
782
783 if (Increasing)
784 ExitMainLoopAtSCEV = *SR.HighLimit;
785 else if (cannotBeMinInLoop(*SR.LowLimit, &OriginalLoop, SE,
786 IsSignedPredicate))
787 ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);
788 else {
789 LLVM_DEBUG(dbgs() << "could not prove no-overflow when computing "
790 << "mainloop exit limit. LowLimit = "
791 << *(*SR.LowLimit) << "\n");
792 return false;
793 }
794
795 if (!Expander.isSafeToExpandAt(ExitMainLoopAtSCEV, InsertPt)) {
796 LLVM_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");
800 return false;
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.
809 if (NeedsPreLoop)
810 cloneLoop(PreLoop, "preloop");
811 if (NeedsPostLoop)
812 cloneLoop(PostLoop, "postloop");
813
814 RewrittenRangeInfo PreLoopRRI;
815
816 if (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
828 BasicBlock *PostLoopPreheader = nullptr;
829 RewrittenRangeInfo PostLoopRRI;
830
831 if (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
840 BasicBlock *NewMainLoopPreheader =
841 MainLoopPreheader != Preheader ? MainLoopPreheader : nullptr;
842 BasicBlock *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.
848 auto 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.
859 Loop *PreL = nullptr, *PostL = nullptr;
860 if (!PreLoop.Blocks.empty()) {
861 PreL = createClonedLoopStructure(&OriginalLoop,
862 OriginalLoop.getParentLoop(), PreLoop.Map,
863 /* IsSubLoop */ false);
864 }
865
866 if (!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.
873 auto CanonicalizeLoop = [&](Loop *L, bool IsOriginalLoop) {
874 formLCSSARecursively(*L, DT, &LI, &SE);
875 simplifyLoop(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.
878 if (!IsOriginalLoop)
880 };
881 if (PreL)
882 CanonicalizeLoop(PreL, false);
883 if (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".
894 if (isa<OverflowingBinaryOperator>(MainLoopStructure.IndVarBase))
895 if (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
909 return true;
910}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static const Function * getParent(const Value *V)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static const char * ClonedLoopTag
static const SCEV * getNarrowestLatchMaxTakenCountEstimate(ScalarEvolution &SE, const Loop &L)
Returns estimate for max latch taken count of the loop of the narrowest available type.
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...
static void DisableAllLoopOptsOnLoop(Loop &L)
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 ...
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Class for arbitrary precision integers.
Definition: APInt.h:77
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:185
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:188
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
Definition: APInt.h:195
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:198
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:199
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:221
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:289
Conditional or Unconditional Branch instruction.
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Value * getCondition() const
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:993
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:1022
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:1016
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:1020
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:1018
@ ICMP_EQ
equal
Definition: InstrTypes.h:1014
@ ICMP_NE
not equal
Definition: InstrTypes.h:1015
bool isSigned() const
Definition: InstrTypes.h:1265
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:1167
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:1105
static ConstantAsMetadata * get(Constant *C)
Definition: Metadata.h:528
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
Definition: Constants.h:218
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Definition: Constants.h:212
bool isNegative() const
Definition: Constants.h:201
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:206
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:146
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:655
This instruction compares its operands according to the predicate given to the constructor.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2666
const BasicBlock * getParent() const
Definition: Instruction.h:152
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:359
Class to represent integer types.
Definition: DerivedTypes.h:40
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:278
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:72
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
iterator_range< block_iterator > blocks() const
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
LoopConstrainer(Loop &L, LoopInfo &LI, function_ref< void(Loop *, bool)> LPMAddNewLoop, const LoopStructure &LS, ScalarEvolution &SE, DominatorTree &DT, Type *T, SubRanges SR)
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
LoopT * AllocateLoop(ArgsTy &&...Args)
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
Metadata node.
Definition: Metadata.h:1067
void replaceOperandWith(unsigned I, Metadata *New)
Replace a specific operand.
Definition: Metadata.cpp:1071
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1541
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:600
Root of the metadata hierarchy.
Definition: Metadata.h:62
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.h:293
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
This class represents a constant integer value.
This class uses information about analyze scalars to rewrite expressions in canonical form.
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...
Value * expandCodeFor(const SCEV *SH, Type *Ty, BasicBlock::iterator I)
Insert code to directly compute the specified SCEV expression into the program.
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
const SCEV * getConstant(ConstantInt *V)
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
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...
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
@ LoopInvariant
The SCEV is loop-invariant.
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
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...
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
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.
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
static IntegerType * getInt1Ty(LLVMContext &C)
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:129
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
Value * getOperand(unsigned i) const
Definition: User.h:169
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:377
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
An efficient, type-erasing, non-owning reference to a callable.
self_iterator getIterator()
Definition: ilist_node.h:109
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
auto successors(const MachineBasicBlock *BB)
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:425
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:1282
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, DebugInfoFinder *DIFinder=nullptr)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
Definition: ValueMapper.h:94
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition: ValueMapper.h:76
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
Definition: ValueMapper.h:263
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:191
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:1271
bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always non-negative in loop L.
Definition: LoopUtils.cpp:1250
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
std::optional< const SCEV * > LowLimit
std::optional< const SCEV * > HighLimit
BasicBlock * LatchExit
LoopStructure map(M Map) const
BranchInst * LatchBr
static std::optional< LoopStructure > parseLoopStructure(ScalarEvolution &, Loop &, bool, const char *&)