1#include "llvm/Transforms/Utils/LoopConstrainer.h"
2#include "llvm/Analysis/LoopInfo.h"
3#include "llvm/Analysis/ScalarEvolution.h"
4#include "llvm/Analysis/ScalarEvolutionExpressions.h"
5#include "llvm/IR/Dominators.h"
6#include "llvm/Transforms/Utils/Cloning.h"
7#include "llvm/Transforms/Utils/LoopSimplify.h"
8#include "llvm/Transforms/Utils/LoopUtils.h"
9#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
10
11using namespace llvm;
12
13static const char *ClonedLoopTag = "loop_constrainer.loop.clone";
14
15#define DEBUG_TYPE "loop-constrainer"
16
17static bool isLoopEntryGuardedByCond(ScalarEvolution &SE, Loop *L,
18 ICmpInst::Predicate Pred,
19 const SCEV *Start, const SCEV *Bound) {
20 // First, try to prove the predicate without applying loop guards.
21 if (SE.isLoopEntryGuardedByCond(L, Pred, LHS: Start, RHS: Bound))
22 return true;
23 // Otherwise, try again with loop guards applied to the SCEVs.
24 auto StartLG = SE.applyLoopGuards(Expr: Start, L);
25 auto BoundLG = SE.applyLoopGuards(Expr: Bound, L);
26 return SE.isLoopEntryGuardedByCond(L, Pred, LHS: StartLG, RHS: BoundLG);
27}
28
29/// Given a loop with an deccreasing induction variable, is it possible to
30/// safely calculate the bounds of a new loop using the given Predicate.
31static bool isSafeDecreasingBound(const SCEV *Start, const SCEV *BoundSCEV,
32 const SCEV *Step, ICmpInst::Predicate Pred,
33 unsigned LatchBrExitIdx, Loop *L,
34 ScalarEvolution &SE) {
35 if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&
36 Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
37 return false;
38
39 if (!SE.isAvailableAtLoopEntry(S: BoundSCEV, L))
40 return false;
41
42 assert(SE.isKnownNegative(Step) && "expecting negative step");
43
44 LLVM_DEBUG(dbgs() << "isSafeDecreasingBound with:\n");
45 LLVM_DEBUG(dbgs() << "Start: " << *Start << "\n");
46 LLVM_DEBUG(dbgs() << "Step: " << *Step << "\n");
47 LLVM_DEBUG(dbgs() << "BoundSCEV: " << *BoundSCEV << "\n");
48 LLVM_DEBUG(dbgs() << "Pred: " << Pred << "\n");
49 LLVM_DEBUG(dbgs() << "LatchExitBrIdx: " << LatchBrExitIdx << "\n");
50
51 bool IsSigned = ICmpInst::isSigned(Pred);
52 // The predicate that we need to check that the induction variable lies
53 // within bounds.
54 ICmpInst::Predicate BoundPred =
55 IsSigned ? CmpInst::ICMP_SGT : CmpInst::ICMP_UGT;
56
57 if (LatchBrExitIdx == 1)
58 return isLoopEntryGuardedByCond(SE, L, Pred: BoundPred, Start, Bound: BoundSCEV);
59
60 assert(LatchBrExitIdx == 0 && "LatchBrExitIdx should be either 0 or 1");
61
62 const SCEV *StepPlusOne = SE.getAddExpr(LHS: Step, RHS: SE.getOne(Ty: Step->getType()));
63 unsigned BitWidth = cast<IntegerType>(Val: BoundSCEV->getType())->getBitWidth();
64 APInt Min = IsSigned ? APInt::getSignedMinValue(numBits: BitWidth)
65 : APInt::getMinValue(numBits: BitWidth);
66 const SCEV *Limit = SE.getMinusSCEV(LHS: SE.getConstant(Val: Min), RHS: StepPlusOne);
67
68 const SCEV *MinusOne =
69 SE.getMinusSCEV(LHS: BoundSCEV, RHS: SE.getOne(Ty: BoundSCEV->getType()));
70
71 return isLoopEntryGuardedByCond(SE, L, Pred: BoundPred, Start, Bound: MinusOne) &&
72 isLoopEntryGuardedByCond(SE, L, Pred: BoundPred, Start: BoundSCEV, Bound: Limit);
73}
74
75/// Given a loop with an increasing induction variable, is it possible to
76/// safely calculate the bounds of a new loop using the given Predicate.
77static bool isSafeIncreasingBound(const SCEV *Start, const SCEV *BoundSCEV,
78 const SCEV *Step, ICmpInst::Predicate Pred,
79 unsigned LatchBrExitIdx, Loop *L,
80 ScalarEvolution &SE) {
81 if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&
82 Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
83 return false;
84
85 if (!SE.isAvailableAtLoopEntry(S: BoundSCEV, L))
86 return false;
87
88 LLVM_DEBUG(dbgs() << "isSafeIncreasingBound with:\n");
89 LLVM_DEBUG(dbgs() << "Start: " << *Start << "\n");
90 LLVM_DEBUG(dbgs() << "Step: " << *Step << "\n");
91 LLVM_DEBUG(dbgs() << "BoundSCEV: " << *BoundSCEV << "\n");
92 LLVM_DEBUG(dbgs() << "Pred: " << Pred << "\n");
93 LLVM_DEBUG(dbgs() << "LatchExitBrIdx: " << LatchBrExitIdx << "\n");
94
95 bool IsSigned = ICmpInst::isSigned(Pred);
96 // The predicate that we need to check that the induction variable lies
97 // within bounds.
98 ICmpInst::Predicate BoundPred =
99 IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
100
101 if (LatchBrExitIdx == 1)
102 return isLoopEntryGuardedByCond(SE, L, Pred: BoundPred, Start, Bound: BoundSCEV);
103
104 assert(LatchBrExitIdx == 0 && "LatchBrExitIdx should be 0 or 1");
105
106 const SCEV *StepMinusOne = SE.getMinusSCEV(LHS: Step, RHS: SE.getOne(Ty: Step->getType()));
107 unsigned BitWidth = cast<IntegerType>(Val: BoundSCEV->getType())->getBitWidth();
108 APInt Max = IsSigned ? APInt::getSignedMaxValue(numBits: BitWidth)
109 : APInt::getMaxValue(numBits: BitWidth);
110 const SCEV *Limit = SE.getMinusSCEV(LHS: SE.getConstant(Val: Max), RHS: StepMinusOne);
111
112 return (isLoopEntryGuardedByCond(SE, L, Pred: BoundPred, Start,
113 Bound: SE.getAddExpr(LHS: BoundSCEV, RHS: Step)) &&
114 isLoopEntryGuardedByCond(SE, L, Pred: BoundPred, Start: BoundSCEV, Bound: Limit));
115}
116
117/// Returns estimate for max latch taken count of the loop of the narrowest
118/// available type. If the latch block has such estimate, it is returned.
119/// Otherwise, we use max exit count of whole loop (that is potentially of wider
120/// type than latch check itself), which is still better than no estimate.
121static const SCEV *getNarrowestLatchMaxTakenCountEstimate(ScalarEvolution &SE,
122 const Loop &L) {
123 const SCEV *FromBlock =
124 SE.getExitCount(L: &L, ExitingBlock: L.getLoopLatch(), Kind: ScalarEvolution::SymbolicMaximum);
125 if (isa<SCEVCouldNotCompute>(Val: FromBlock))
126 return SE.getSymbolicMaxBackedgeTakenCount(L: &L);
127 return FromBlock;
128}
129
130std::optional<LoopStructure>
131LoopStructure::parseLoopStructure(SCEVExpander &Expander, Loop &L,
132 bool AllowUnsignedLatchCond,
133 const char *&FailureReason) {
134 ScalarEvolution &SE = *Expander.getSE();
135 if (!L.isLoopSimplifyForm()) {
136 FailureReason = "loop not in LoopSimplify form";
137 return std::nullopt;
138 }
139
140 BasicBlock *Latch = L.getLoopLatch();
141 assert(Latch && "Simplified loops only have one latch!");
142
143 if (Latch->getTerminator()->getMetadata(Kind: ClonedLoopTag)) {
144 FailureReason = "loop has already been cloned";
145 return std::nullopt;
146 }
147
148 if (!L.isLoopExiting(BB: Latch)) {
149 FailureReason = "no loop latch";
150 return std::nullopt;
151 }
152
153 BasicBlock *Header = L.getHeader();
154 BasicBlock *Preheader = L.getLoopPreheader();
155 if (!Preheader) {
156 FailureReason = "no preheader";
157 return std::nullopt;
158 }
159
160 CondBrInst *LatchBr = dyn_cast<CondBrInst>(Val: Latch->getTerminator());
161 if (!LatchBr) {
162 FailureReason = "latch terminator not conditional branch";
163 return std::nullopt;
164 }
165
166 unsigned LatchBrExitIdx = LatchBr->getSuccessor(i: 0) == Header ? 1 : 0;
167
168 ICmpInst *ICI = dyn_cast<ICmpInst>(Val: LatchBr->getCondition());
169 if (!ICI || !isa<IntegerType>(Val: ICI->getOperand(i_nocapture: 0)->getType())) {
170 FailureReason = "latch terminator branch not conditional on integral icmp";
171 return std::nullopt;
172 }
173
174 const SCEV *MaxBETakenCount = getNarrowestLatchMaxTakenCountEstimate(SE, L);
175 if (isa<SCEVCouldNotCompute>(Val: MaxBETakenCount)) {
176 FailureReason = "could not compute latch count";
177 return std::nullopt;
178 }
179 assert(SE.getLoopDisposition(MaxBETakenCount, &L) ==
180 ScalarEvolution::LoopInvariant &&
181 "loop variant exit count doesn't make sense!");
182
183 ICmpInst::Predicate Pred = ICI->getPredicate();
184 Value *LeftValue = ICI->getOperand(i_nocapture: 0);
185 const SCEV *LeftSCEV = SE.getSCEV(V: LeftValue);
186 IntegerType *IndVarTy = cast<IntegerType>(Val: LeftValue->getType());
187
188 Value *RightValue = ICI->getOperand(i_nocapture: 1);
189 const SCEV *RightSCEV = SE.getSCEV(V: RightValue);
190
191 // We canonicalize `ICI` such that `LeftSCEV` is an add recurrence.
192 if (!isa<SCEVAddRecExpr>(Val: LeftSCEV)) {
193 if (isa<SCEVAddRecExpr>(Val: RightSCEV)) {
194 std::swap(a&: LeftSCEV, b&: RightSCEV);
195 std::swap(a&: LeftValue, b&: RightValue);
196 Pred = ICmpInst::getSwappedPredicate(pred: Pred);
197 } else {
198 FailureReason = "no add recurrences in the icmp";
199 return std::nullopt;
200 }
201 }
202
203 auto HasNoSignedWrap = [&](const SCEVAddRecExpr *AR) {
204 if (AR->hasNoSignedWrap())
205 return true;
206
207 IntegerType *Ty = cast<IntegerType>(Val: AR->getType());
208 IntegerType *WideTy =
209 IntegerType::get(C&: Ty->getContext(), NumBits: Ty->getBitWidth() * 2);
210
211 const SCEVAddRecExpr *ExtendAfterOp =
212 dyn_cast<SCEVAddRecExpr>(Val: SE.getSignExtendExpr(Op: AR, Ty: WideTy));
213 if (ExtendAfterOp) {
214 const SCEV *ExtendedStart = SE.getSignExtendExpr(Op: AR->getStart(), Ty: WideTy);
215 const SCEV *ExtendedStep =
216 SE.getSignExtendExpr(Op: AR->getStepRecurrence(SE), Ty: WideTy);
217
218 bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
219 ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
220
221 if (NoSignedWrap)
222 return true;
223 }
224
225 // We may have proved this when computing the sign extension above.
226 return AR->hasNoSignedWrap();
227 };
228
229 // `ICI` is interpreted as taking the backedge if the *next* value of the
230 // induction variable satisfies some constraint.
231
232 const SCEVAddRecExpr *IndVarBase = cast<SCEVAddRecExpr>(Val: LeftSCEV);
233 if (IndVarBase->getLoop() != &L) {
234 FailureReason = "LHS in cmp is not an AddRec for this loop";
235 return std::nullopt;
236 }
237 if (!IndVarBase->isAffine()) {
238 FailureReason = "LHS in icmp not induction variable";
239 return std::nullopt;
240 }
241 const SCEV *StepRec = IndVarBase->getStepRecurrence(SE);
242 if (!isa<SCEVConstant>(Val: StepRec)) {
243 FailureReason = "LHS in icmp not induction variable";
244 return std::nullopt;
245 }
246 ConstantInt *StepCI = cast<SCEVConstant>(Val: StepRec)->getValue();
247
248 if (ICI->isEquality() && !HasNoSignedWrap(IndVarBase)) {
249 FailureReason = "LHS in icmp needs nsw for equality predicates";
250 return std::nullopt;
251 }
252
253 assert(!StepCI->isZero() && "Zero step?");
254 bool IsIncreasing = !StepCI->isNegative();
255 bool IsSignedPredicate;
256 const SCEV *StartNext = IndVarBase->getStart();
257 const SCEV *Addend = SE.getNegativeSCEV(V: IndVarBase->getStepRecurrence(SE));
258 const SCEV *IndVarStart = SE.getAddExpr(LHS: StartNext, RHS: Addend);
259 const SCEV *Step = SE.getSCEV(V: StepCI);
260
261 const SCEV *FixedRightSCEV = nullptr;
262
263 // If RightValue resides within loop (but still being loop invariant),
264 // regenerate it as preheader.
265 if (auto *I = dyn_cast<Instruction>(Val: RightValue))
266 if (L.contains(BB: I->getParent()))
267 FixedRightSCEV = RightSCEV;
268
269 if (IsIncreasing) {
270 bool DecreasedRightValueByOne = false;
271 if (StepCI->isOne()) {
272 // Try to turn eq/ne predicates to those we can work with.
273 if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
274 // while (++i != len) { while (++i < len) {
275 // ... ---> ...
276 // } }
277 // If both parts are known non-negative, it is profitable to use
278 // unsigned comparison in increasing loop. This allows us to make the
279 // comparison check against "RightSCEV + 1" more optimistic.
280 if (isKnownNonNegativeInLoop(S: IndVarStart, L: &L, SE) &&
281 isKnownNonNegativeInLoop(S: RightSCEV, L: &L, SE))
282 Pred = ICmpInst::ICMP_ULT;
283 else
284 Pred = ICmpInst::ICMP_SLT;
285 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
286 // while (true) { while (true) {
287 // if (++i == len) ---> if (++i > len - 1)
288 // break; break;
289 // ... ...
290 // } }
291 if (IndVarBase->hasNoUnsignedWrap() &&
292 cannotBeMinInLoop(S: RightSCEV, L: &L, SE, /*Signed*/ false)) {
293 Pred = ICmpInst::ICMP_UGT;
294 RightSCEV =
295 SE.getMinusSCEV(LHS: RightSCEV, RHS: SE.getOne(Ty: RightSCEV->getType()));
296 DecreasedRightValueByOne = true;
297 } else if (cannotBeMinInLoop(S: RightSCEV, L: &L, SE, /*Signed*/ true)) {
298 Pred = ICmpInst::ICMP_SGT;
299 RightSCEV =
300 SE.getMinusSCEV(LHS: RightSCEV, RHS: SE.getOne(Ty: RightSCEV->getType()));
301 DecreasedRightValueByOne = true;
302 }
303 }
304 }
305
306 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
307 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
308 bool FoundExpectedPred =
309 (LTPred && LatchBrExitIdx == 1) || (GTPred && LatchBrExitIdx == 0);
310
311 if (!FoundExpectedPred) {
312 FailureReason = "expected icmp slt semantically, found something else";
313 return std::nullopt;
314 }
315
316 IsSignedPredicate = ICmpInst::isSigned(Pred);
317 if (!IsSignedPredicate && !AllowUnsignedLatchCond) {
318 FailureReason = "unsigned latch conditions are explicitly prohibited";
319 return std::nullopt;
320 }
321
322 if (!isSafeIncreasingBound(Start: IndVarStart, BoundSCEV: RightSCEV, Step, Pred,
323 LatchBrExitIdx, L: &L, SE)) {
324 FailureReason = "Unsafe loop bounds";
325 return std::nullopt;
326 }
327 if (LatchBrExitIdx == 0) {
328 // We need to increase the right value unless we have already decreased
329 // it virtually when we replaced EQ with SGT.
330 if (!DecreasedRightValueByOne)
331 FixedRightSCEV =
332 SE.getAddExpr(LHS: RightSCEV, RHS: SE.getOne(Ty: RightSCEV->getType()));
333 } else {
334 assert(!DecreasedRightValueByOne &&
335 "Right value can be decreased only for LatchBrExitIdx == 0!");
336 }
337 } else {
338 bool IncreasedRightValueByOne = false;
339 if (StepCI->isMinusOne()) {
340 // Try to turn eq/ne predicates to those we can work with.
341 if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
342 // while (--i != len) { while (--i > len) {
343 // ... ---> ...
344 // } }
345 // We intentionally don't turn the predicate into UGT even if we know
346 // that both operands are non-negative, because it will only pessimize
347 // our check against "RightSCEV - 1".
348 Pred = ICmpInst::ICMP_SGT;
349 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
350 // while (true) { while (true) {
351 // if (--i == len) ---> if (--i < len + 1)
352 // break; break;
353 // ... ...
354 // } }
355 if (IndVarBase->hasNoUnsignedWrap() &&
356 cannotBeMaxInLoop(S: RightSCEV, L: &L, SE, /* Signed */ false)) {
357 Pred = ICmpInst::ICMP_ULT;
358 RightSCEV = SE.getAddExpr(LHS: RightSCEV, RHS: SE.getOne(Ty: RightSCEV->getType()));
359 IncreasedRightValueByOne = true;
360 } else if (cannotBeMaxInLoop(S: RightSCEV, L: &L, SE, /* Signed */ true)) {
361 Pred = ICmpInst::ICMP_SLT;
362 RightSCEV = SE.getAddExpr(LHS: RightSCEV, RHS: SE.getOne(Ty: RightSCEV->getType()));
363 IncreasedRightValueByOne = true;
364 }
365 }
366 }
367
368 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
369 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
370
371 bool FoundExpectedPred =
372 (GTPred && LatchBrExitIdx == 1) || (LTPred && LatchBrExitIdx == 0);
373
374 if (!FoundExpectedPred) {
375 FailureReason = "expected icmp sgt semantically, found something else";
376 return std::nullopt;
377 }
378
379 IsSignedPredicate =
380 Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
381
382 if (!IsSignedPredicate && !AllowUnsignedLatchCond) {
383 FailureReason = "unsigned latch conditions are explicitly prohibited";
384 return std::nullopt;
385 }
386
387 if (!isSafeDecreasingBound(Start: IndVarStart, BoundSCEV: RightSCEV, Step, Pred,
388 LatchBrExitIdx, L: &L, SE)) {
389 FailureReason = "Unsafe bounds";
390 return std::nullopt;
391 }
392
393 if (LatchBrExitIdx == 0) {
394 // We need to decrease the right value unless we have already increased
395 // it virtually when we replaced EQ with SLT.
396 if (!IncreasedRightValueByOne)
397 FixedRightSCEV =
398 SE.getMinusSCEV(LHS: RightSCEV, RHS: SE.getOne(Ty: RightSCEV->getType()));
399 } else {
400 assert(!IncreasedRightValueByOne &&
401 "Right value can be increased only for LatchBrExitIdx == 0!");
402 }
403 }
404 BasicBlock *LatchExit = LatchBr->getSuccessor(i: LatchBrExitIdx);
405
406 assert(!L.contains(LatchExit) && "expected an exit block!");
407 Instruction *Ins = Preheader->getTerminator();
408
409 if (FixedRightSCEV)
410 RightValue =
411 Expander.expandCodeFor(SH: FixedRightSCEV, Ty: FixedRightSCEV->getType(), I: Ins);
412
413 Value *IndVarStartV = Expander.expandCodeFor(SH: IndVarStart, Ty: IndVarTy, I: Ins);
414
415 LoopStructure Result;
416
417 Result.Tag = "main";
418 Result.Header = Header;
419 Result.Latch = Latch;
420 Result.LatchBr = LatchBr;
421 Result.LatchExit = LatchExit;
422 Result.LatchBrExitIdx = LatchBrExitIdx;
423 Result.IndVarStart = IndVarStartV;
424 Result.IndVarStep = StepCI;
425 Result.IndVarBase = LeftValue;
426 Result.IndVarIncreasing = IsIncreasing;
427 Result.LoopExitAt = RightValue;
428 Result.IsSignedPredicate = IsSignedPredicate;
429 Result.ExitCountTy = cast<IntegerType>(Val: MaxBETakenCount->getType());
430
431 FailureReason = nullptr;
432
433 return Result;
434}
435
436// Add metadata to the loop L to disable loop optimizations. Callers need to
437// confirm that optimizing loop L is not beneficial.
438static void DisableAllLoopOptsOnLoop(Loop &L) {
439 // We do not care about any existing loopID related metadata for L, since we
440 // are setting all loop metadata to false.
441 LLVMContext &Context = L.getHeader()->getContext();
442 // Reserve first location for self reference to the LoopID metadata node.
443 MDNode *Dummy = MDNode::get(Context, MDs: {});
444 MDNode *DisableUnroll = MDNode::get(
445 Context, MDs: {MDString::get(Context, Str: "llvm.loop.unroll.disable")});
446 MDNode *DisableVectorize = MDNode::get(
447 Context, MDs: {MDString::get(Context, Str: "llvm.loop.vectorize.disable")});
448 MDNode *DisableLICMVersioning = MDNode::get(
449 Context, MDs: {MDString::get(Context, Str: "llvm.loop.licm_versioning.disable")});
450 MDNode *DisableDistribution = MDNode::get(
451 Context, MDs: {MDString::get(Context, Str: "llvm.loop.distribute.disable")});
452 MDNode *NewLoopID =
453 MDNode::get(Context, MDs: {Dummy, DisableUnroll, DisableVectorize,
454 DisableLICMVersioning, DisableDistribution});
455 // Set operand 0 to refer to the loop id itself.
456 NewLoopID->replaceOperandWith(I: 0, New: NewLoopID);
457 L.setLoopID(NewLoopID);
458}
459
460LoopConstrainer::LoopConstrainer(Loop &L, LoopInfo &LI,
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, VMap&: Result.Map, NameSuffix: Twine(".") + Tag, F: &F);
472 Result.Blocks.push_back(x: 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(Val: 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>(Val: GetClonedValue(OriginalLoop.getLoopLatch()));
486 ClonedLatch->getTerminator()->setMetadata(Kind: ClonedLoopTag,
487 Node: MDNode::get(Context&: Ctx, MDs: {}));
488
489 Result.Structure = MainLoopStructure.map(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)
499 RemapInstruction(I: &I, VM&: Result.Map,
500 Flags: RF_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
506 for (auto *SBB : successors(BB: OriginalBB)) {
507 if (OriginalLoop.contains(BB: SBB))
508 continue; // not an exit block
509
510 for (PHINode &PN : SBB->phis()) {
511 Value *OldIncoming = PN.getIncomingValueForBlock(BB: OriginalBB);
512 PN.addIncoming(V: GetClonedValue(OldIncoming), BB: ClonedBB);
513 SE.forgetLcssaPhiWithNewPredecessor(L: &OriginalLoop, V: &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(Context&: Ctx, Name: Twine(LS.Tag) + ".exit.selector",
597 Parent: &F, InsertBefore: BBInsertLocation);
598 RRI.PseudoExit = BasicBlock::Create(Context&: Ctx, Name: Twine(LS.Tag) + ".pseudo.exit", Parent: &F,
599 InsertBefore: BBInsertLocation);
600
601 Instruction *PreheaderJump = 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, DestTy: RangeTy, Name: "wide." + V->getName())
610 : B.CreateZExt(V, DestTy: RangeTy, Name: "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(P: Pred, LHS: IndVarStart, RHS: ExitSubloopAt);
621
622 B.CreateCondBr(Cond: EnterLoopCond, True: LS.Header, False: RRI.PseudoExit);
623 PreheaderJump->eraseFromParent();
624
625 LS.LatchBr->setSuccessor(idx: LS.LatchBrExitIdx, NewSucc: RRI.ExitSelector);
626 B.SetInsertPoint(LS.LatchBr);
627 Value *IndVarBase = NoopOrExt(LS.IndVarBase);
628 Value *TakeBackedgeLoopCond = B.CreateICmp(P: Pred, LHS: IndVarBase, RHS: ExitSubloopAt);
629
630 Value *CondForBranch = LS.LatchBrExitIdx == 1
631 ? TakeBackedgeLoopCond
632 : B.CreateNot(V: 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(P: Pred, LHS: IndVarBase, RHS: LoopExitAt);
643 B.CreateCondBr(Cond: IterationsLeft, True: RRI.PseudoExit, False: LS.LatchExit);
644
645 UncondBrInst *BranchToContinuation =
646 UncondBrInst::Create(Target: ContinuationBlock, InsertBefore: 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(Ty: PN.getType(), NumReservedValues: 2, NameStr: PN.getName() + ".copy",
653 InsertBefore: BranchToContinuation->getIterator());
654
655 NewPHI->addIncoming(V: PN.getIncomingValueForBlock(BB: Preheader), BB: Preheader);
656 NewPHI->addIncoming(V: PN.getIncomingValueForBlock(BB: LS.Latch),
657 BB: RRI.ExitSelector);
658 RRI.PHIValuesAtPseudoExit.push_back(x: NewPHI);
659 }
660
661 RRI.IndVarEnd = PHINode::Create(Ty: IndVarBase->getType(), NumReservedValues: 2, NameStr: "indvar.end",
662 InsertBefore: BranchToContinuation->getIterator());
663 RRI.IndVarEnd->addIncoming(V: IndVarStart, BB: Preheader);
664 RRI.IndVarEnd->addIncoming(V: IndVarBase, BB: 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(Old: LS.Latch, New: 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(BB: ContinuationBlock,
679 V: 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(Context&: Ctx, Name: Tag, Parent: &F, InsertBefore: LS.Header);
688 UncondBrInst::Create(Target: LS.Header, InsertBefore: Preheader);
689
690 LS.Header->replacePhiUsesWith(Old: OldPreheader, New: 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(NewBB: BB, LI);
702}
703
704Loop *LoopConstrainer::createClonedLoopStructure(Loop *Original, Loop *Parent,
705 ValueToValueMapTy &VM,
706 bool IsSubloop) {
707 Loop &New = *LI.AllocateLoop();
708 if (Parent)
709 Parent->addChildLoop(NewChild: &New);
710 else
711 LI.addTopLevelLoop(New: &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(NewBB: cast<BasicBlock>(Val&: VM[BB]), LI);
718
719 // Add all of the subloops to the new loop.
720 for (Loop *SubLoop : *Original)
721 createClonedLoopStructure(Original: SubLoop, Parent: &New, VM, /* IsSubloop */ true);
722
723 return &New;
724}
725
726bool LoopConstrainer::run() {
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>(Val: RangeTy);
735
736 SCEVExpander Expander(SE, "loop-constrainer");
737 SCEVExpanderCleaner ExpanderCleaner(Expander);
738 Instruction *InsertPt = OriginalPreheader->getTerminator();
739
740 // It would have been better to make `PreLoop' and `PostLoop'
741 // `std::optional<ClonedLoop>'s, but `ValueToValueMapTy' does not have a copy
742 // constructor.
743 ClonedLoop PreLoop, PostLoop;
744 bool NeedsPreLoop =
745 Increasing ? SR.LowLimit.has_value() : SR.HighLimit.has_value();
746 bool NeedsPostLoop =
747 Increasing ? SR.HighLimit.has_value() : SR.LowLimit.has_value();
748
749 Value *ExitPreLoopAt = nullptr;
750 Value *ExitMainLoopAt = nullptr;
751 const SCEVConstant *MinusOneS =
752 cast<SCEVConstant>(Val: SE.getConstant(Ty: IVTy, V: -1, isSigned: true /* isSigned */));
753
754 if (NeedsPreLoop) {
755 const SCEV *ExitPreLoopAtSCEV = nullptr;
756
757 if (Increasing)
758 ExitPreLoopAtSCEV = *SR.LowLimit;
759 else if (cannotBeMinInLoop(S: *SR.HighLimit, L: &OriginalLoop, SE,
760 Signed: IsSignedPredicate))
761 ExitPreLoopAtSCEV = SE.getAddExpr(LHS: *SR.HighLimit, RHS: MinusOneS);
762 else {
763 LLVM_DEBUG(dbgs() << "could not prove no-overflow when computing "
764 << "preloop exit limit. HighLimit = "
765 << *(*SR.HighLimit) << "\n");
766 return false;
767 }
768
769 if (!Expander.isSafeToExpandAt(S: ExitPreLoopAtSCEV, InsertionPoint: InsertPt)) {
770 LLVM_DEBUG(dbgs() << "could not prove that it is safe to expand the"
771 << " preloop exit limit " << *ExitPreLoopAtSCEV
772 << " at block " << InsertPt->getParent()->getName()
773 << "\n");
774 return false;
775 }
776
777 ExitPreLoopAt = Expander.expandCodeFor(SH: ExitPreLoopAtSCEV, Ty: IVTy, I: InsertPt);
778 }
779
780 if (NeedsPostLoop) {
781 const SCEV *ExitMainLoopAtSCEV = nullptr;
782
783 if (Increasing)
784 ExitMainLoopAtSCEV = *SR.HighLimit;
785 else if (cannotBeMinInLoop(S: *SR.LowLimit, L: &OriginalLoop, SE,
786 Signed: IsSignedPredicate))
787 ExitMainLoopAtSCEV = SE.getAddExpr(LHS: *SR.LowLimit, RHS: 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(S: ExitMainLoopAtSCEV, InsertionPoint: 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(SH: ExitMainLoopAtSCEV, Ty: IVTy, I: InsertPt);
804 ExitMainLoopAt->setName("exit.mainloop.at");
805 }
806
807 // All checks which can fail after expanding SCEVs are complete. Keep the
808 // expansions now that the loop transformation is guaranteed to proceed.
809 ExpanderCleaner.markResultUsed();
810 if (ExitPreLoopAt)
811 ExitPreLoopAt->setName("exit.preloop.at");
812
813 // We clone these ahead of time so that we don't have to deal with changing
814 // and temporarily invalid IR as we transform the loops.
815 if (NeedsPreLoop)
816 cloneLoop(Result&: PreLoop, Tag: "preloop");
817 if (NeedsPostLoop)
818 cloneLoop(Result&: PostLoop, Tag: "postloop");
819
820 RewrittenRangeInfo PreLoopRRI;
821
822 if (NeedsPreLoop) {
823 Preheader->getTerminator()->replaceUsesOfWith(From: MainLoopStructure.Header,
824 To: PreLoop.Structure.Header);
825
826 MainLoopPreheader =
827 createPreheader(LS: MainLoopStructure, OldPreheader: Preheader, Tag: "mainloop");
828 PreLoopRRI = changeIterationSpaceEnd(LS: PreLoop.Structure, Preheader,
829 ExitSubloopAt: ExitPreLoopAt, ContinuationBlock: MainLoopPreheader);
830 rewriteIncomingValuesForPHIs(LS&: MainLoopStructure, ContinuationBlock: MainLoopPreheader,
831 RRI: PreLoopRRI);
832 }
833
834 BasicBlock *PostLoopPreheader = nullptr;
835 RewrittenRangeInfo PostLoopRRI;
836
837 if (NeedsPostLoop) {
838 PostLoopPreheader =
839 createPreheader(LS: PostLoop.Structure, OldPreheader: Preheader, Tag: "postloop");
840 PostLoopRRI = changeIterationSpaceEnd(LS: MainLoopStructure, Preheader: MainLoopPreheader,
841 ExitSubloopAt: ExitMainLoopAt, ContinuationBlock: PostLoopPreheader);
842 rewriteIncomingValuesForPHIs(LS&: PostLoop.Structure, ContinuationBlock: PostLoopPreheader,
843 RRI: PostLoopRRI);
844 }
845
846 BasicBlock *NewMainLoopPreheader =
847 MainLoopPreheader != Preheader ? MainLoopPreheader : nullptr;
848 BasicBlock *NewBlocks[] = {PostLoopPreheader, PreLoopRRI.PseudoExit,
849 PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit,
850 PostLoopRRI.ExitSelector, NewMainLoopPreheader};
851
852 // Some of the above may be nullptr, filter them out before passing to
853 // addToParentLoopIfNeeded.
854 auto NewBlocksEnd =
855 std::remove(first: std::begin(arr&: NewBlocks), last: std::end(arr&: NewBlocks), value: nullptr);
856
857 addToParentLoopIfNeeded(BBs: ArrayRef(std::begin(arr&: NewBlocks), NewBlocksEnd));
858
859 DT.recalculate(Func&: F);
860
861 // We need to first add all the pre and post loop blocks into the loop
862 // structures (as part of createClonedLoopStructure), and then update the
863 // LCSSA form and LoopSimplifyForm. This is necessary for correctly updating
864 // LI when LoopSimplifyForm is generated.
865 Loop *PreL = nullptr, *PostL = nullptr;
866 if (!PreLoop.Blocks.empty()) {
867 PreL = createClonedLoopStructure(Original: &OriginalLoop,
868 Parent: OriginalLoop.getParentLoop(), VM&: PreLoop.Map,
869 /* IsSubLoop */ IsSubloop: false);
870 }
871
872 if (!PostLoop.Blocks.empty()) {
873 PostL =
874 createClonedLoopStructure(Original: &OriginalLoop, Parent: OriginalLoop.getParentLoop(),
875 VM&: PostLoop.Map, /* IsSubLoop */ IsSubloop: false);
876 }
877
878 // This function canonicalizes the loop into Loop-Simplify and LCSSA forms.
879 auto CanonicalizeLoop = [&](Loop *L, bool IsOriginalLoop) {
880 formLCSSARecursively(L&: *L, DT, LI: &LI, SE: &SE);
881 simplifyLoop(L, DT: &DT, LI: &LI, SE: &SE, AC: nullptr, MSSAU: nullptr, PreserveLCSSA: true);
882 // Pre/post loops are slow paths, we do not need to perform any loop
883 // optimizations on them.
884 if (!IsOriginalLoop)
885 DisableAllLoopOptsOnLoop(L&: *L);
886 };
887 if (PreL)
888 CanonicalizeLoop(PreL, false);
889 if (PostL)
890 CanonicalizeLoop(PostL, false);
891 CanonicalizeLoop(&OriginalLoop, true);
892
893 /// At this point:
894 /// - We've broken a "main loop" out of the loop in a way that the "main loop"
895 /// runs with the induction variable in a subset of [Begin, End).
896 /// - There is no overflow when computing "main loop" exit limit.
897 /// - Max latch taken count of the loop is limited.
898 /// It guarantees that induction variable will not overflow iterating in the
899 /// "main loop".
900 if (isa<OverflowingBinaryOperator>(Val: MainLoopStructure.IndVarBase))
901 if (IsSignedPredicate)
902 cast<BinaryOperator>(Val: MainLoopStructure.IndVarBase)
903 ->setHasNoSignedWrap(true);
904 /// TODO: support unsigned predicate.
905 /// To add NUW flag we need to prove that both operands of BO are
906 /// non-negative. E.g:
907 /// ...
908 /// %iv.next = add nsw i32 %iv, -1
909 /// %cmp = icmp ult i32 %iv.next, %n
910 /// br i1 %cmp, label %loopexit, label %loop
911 ///
912 /// -1 is MAX_UINT in terms of unsigned int. Adding anything but zero will
913 /// overflow, therefore NUW flag is not legal here.
914
915 return true;
916}
917