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(predicate: 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(predicate: 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(ScalarEvolution &SE, Loop &L,
132 bool AllowUnsignedLatchCond,
133 const char *&FailureReason) {
134 if (!L.isLoopSimplifyForm()) {
135 FailureReason = "loop not in LoopSimplify form";
136 return std::nullopt;
137 }
138
139 BasicBlock *Latch = L.getLoopLatch();
140 assert(Latch && "Simplified loops only have one latch!");
141
142 if (Latch->getTerminator()->getMetadata(Kind: ClonedLoopTag)) {
143 FailureReason = "loop has already been cloned";
144 return std::nullopt;
145 }
146
147 if (!L.isLoopExiting(BB: Latch)) {
148 FailureReason = "no loop latch";
149 return std::nullopt;
150 }
151
152 BasicBlock *Header = L.getHeader();
153 BasicBlock *Preheader = L.getLoopPreheader();
154 if (!Preheader) {
155 FailureReason = "no preheader";
156 return std::nullopt;
157 }
158
159 BranchInst *LatchBr = dyn_cast<BranchInst>(Val: Latch->getTerminator());
160 if (!LatchBr || LatchBr->isUnconditional()) {
161 FailureReason = "latch terminator not conditional branch";
162 return std::nullopt;
163 }
164
165 unsigned LatchBrExitIdx = LatchBr->getSuccessor(i: 0) == Header ? 1 : 0;
166
167 ICmpInst *ICI = dyn_cast<ICmpInst>(Val: LatchBr->getCondition());
168 if (!ICI || !isa<IntegerType>(Val: ICI->getOperand(i_nocapture: 0)->getType())) {
169 FailureReason = "latch terminator branch not conditional on integral icmp";
170 return std::nullopt;
171 }
172
173 const SCEV *MaxBETakenCount = getNarrowestLatchMaxTakenCountEstimate(SE, L);
174 if (isa<SCEVCouldNotCompute>(Val: MaxBETakenCount)) {
175 FailureReason = "could not compute latch count";
176 return std::nullopt;
177 }
178 assert(SE.getLoopDisposition(MaxBETakenCount, &L) ==
179 ScalarEvolution::LoopInvariant &&
180 "loop variant exit count doesn't make sense!");
181
182 ICmpInst::Predicate Pred = ICI->getPredicate();
183 Value *LeftValue = ICI->getOperand(i_nocapture: 0);
184 const SCEV *LeftSCEV = SE.getSCEV(V: LeftValue);
185 IntegerType *IndVarTy = cast<IntegerType>(Val: LeftValue->getType());
186
187 Value *RightValue = ICI->getOperand(i_nocapture: 1);
188 const SCEV *RightSCEV = SE.getSCEV(V: RightValue);
189
190 // We canonicalize `ICI` such that `LeftSCEV` is an add recurrence.
191 if (!isa<SCEVAddRecExpr>(Val: LeftSCEV)) {
192 if (isa<SCEVAddRecExpr>(Val: RightSCEV)) {
193 std::swap(a&: LeftSCEV, b&: RightSCEV);
194 std::swap(a&: LeftValue, b&: RightValue);
195 Pred = ICmpInst::getSwappedPredicate(pred: Pred);
196 } else {
197 FailureReason = "no add recurrences in the icmp";
198 return std::nullopt;
199 }
200 }
201
202 auto HasNoSignedWrap = [&](const SCEVAddRecExpr *AR) {
203 if (AR->getNoWrapFlags(Mask: SCEV::FlagNSW))
204 return true;
205
206 IntegerType *Ty = cast<IntegerType>(Val: AR->getType());
207 IntegerType *WideTy =
208 IntegerType::get(C&: Ty->getContext(), NumBits: Ty->getBitWidth() * 2);
209
210 const SCEVAddRecExpr *ExtendAfterOp =
211 dyn_cast<SCEVAddRecExpr>(Val: SE.getSignExtendExpr(Op: AR, Ty: WideTy));
212 if (ExtendAfterOp) {
213 const SCEV *ExtendedStart = SE.getSignExtendExpr(Op: AR->getStart(), Ty: WideTy);
214 const SCEV *ExtendedStep =
215 SE.getSignExtendExpr(Op: AR->getStepRecurrence(SE), Ty: WideTy);
216
217 bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
218 ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
219
220 if (NoSignedWrap)
221 return true;
222 }
223
224 // We may have proved this when computing the sign extension above.
225 return AR->getNoWrapFlags(Mask: SCEV::FlagNSW) != SCEV::FlagAnyWrap;
226 };
227
228 // `ICI` is interpreted as taking the backedge if the *next* value of the
229 // induction variable satisfies some constraint.
230
231 const SCEVAddRecExpr *IndVarBase = cast<SCEVAddRecExpr>(Val: LeftSCEV);
232 if (IndVarBase->getLoop() != &L) {
233 FailureReason = "LHS in cmp is not an AddRec for this loop";
234 return std::nullopt;
235 }
236 if (!IndVarBase->isAffine()) {
237 FailureReason = "LHS in icmp not induction variable";
238 return std::nullopt;
239 }
240 const SCEV *StepRec = IndVarBase->getStepRecurrence(SE);
241 if (!isa<SCEVConstant>(Val: StepRec)) {
242 FailureReason = "LHS in icmp not induction variable";
243 return std::nullopt;
244 }
245 ConstantInt *StepCI = cast<SCEVConstant>(Val: StepRec)->getValue();
246
247 if (ICI->isEquality() && !HasNoSignedWrap(IndVarBase)) {
248 FailureReason = "LHS in icmp needs nsw for equality predicates";
249 return std::nullopt;
250 }
251
252 assert(!StepCI->isZero() && "Zero step?");
253 bool IsIncreasing = !StepCI->isNegative();
254 bool IsSignedPredicate;
255 const SCEV *StartNext = IndVarBase->getStart();
256 const SCEV *Addend = SE.getNegativeSCEV(V: IndVarBase->getStepRecurrence(SE));
257 const SCEV *IndVarStart = SE.getAddExpr(LHS: StartNext, RHS: Addend);
258 const SCEV *Step = SE.getSCEV(V: StepCI);
259
260 const SCEV *FixedRightSCEV = nullptr;
261
262 // If RightValue resides within loop (but still being loop invariant),
263 // regenerate it as preheader.
264 if (auto *I = dyn_cast<Instruction>(Val: RightValue))
265 if (L.contains(BB: I->getParent()))
266 FixedRightSCEV = RightSCEV;
267
268 if (IsIncreasing) {
269 bool DecreasedRightValueByOne = false;
270 if (StepCI->isOne()) {
271 // Try to turn eq/ne predicates to those we can work with.
272 if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
273 // while (++i != len) { while (++i < len) {
274 // ... ---> ...
275 // } }
276 // If both parts are known non-negative, it is profitable to use
277 // unsigned comparison in increasing loop. This allows us to make the
278 // comparison check against "RightSCEV + 1" more optimistic.
279 if (isKnownNonNegativeInLoop(S: IndVarStart, L: &L, SE) &&
280 isKnownNonNegativeInLoop(S: RightSCEV, L: &L, SE))
281 Pred = ICmpInst::ICMP_ULT;
282 else
283 Pred = ICmpInst::ICMP_SLT;
284 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
285 // while (true) { while (true) {
286 // if (++i == len) ---> if (++i > len - 1)
287 // break; break;
288 // ... ...
289 // } }
290 if (IndVarBase->getNoWrapFlags(Mask: SCEV::FlagNUW) &&
291 cannotBeMinInLoop(S: RightSCEV, L: &L, SE, /*Signed*/ false)) {
292 Pred = ICmpInst::ICMP_UGT;
293 RightSCEV =
294 SE.getMinusSCEV(LHS: RightSCEV, RHS: SE.getOne(Ty: RightSCEV->getType()));
295 DecreasedRightValueByOne = true;
296 } else if (cannotBeMinInLoop(S: RightSCEV, L: &L, SE, /*Signed*/ true)) {
297 Pred = ICmpInst::ICMP_SGT;
298 RightSCEV =
299 SE.getMinusSCEV(LHS: RightSCEV, RHS: SE.getOne(Ty: RightSCEV->getType()));
300 DecreasedRightValueByOne = true;
301 }
302 }
303 }
304
305 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
306 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
307 bool FoundExpectedPred =
308 (LTPred && LatchBrExitIdx == 1) || (GTPred && LatchBrExitIdx == 0);
309
310 if (!FoundExpectedPred) {
311 FailureReason = "expected icmp slt semantically, found something else";
312 return std::nullopt;
313 }
314
315 IsSignedPredicate = ICmpInst::isSigned(predicate: Pred);
316 if (!IsSignedPredicate && !AllowUnsignedLatchCond) {
317 FailureReason = "unsigned latch conditions are explicitly prohibited";
318 return std::nullopt;
319 }
320
321 if (!isSafeIncreasingBound(Start: IndVarStart, BoundSCEV: RightSCEV, Step, Pred,
322 LatchBrExitIdx, L: &L, SE)) {
323 FailureReason = "Unsafe loop bounds";
324 return std::nullopt;
325 }
326 if (LatchBrExitIdx == 0) {
327 // We need to increase the right value unless we have already decreased
328 // it virtually when we replaced EQ with SGT.
329 if (!DecreasedRightValueByOne)
330 FixedRightSCEV =
331 SE.getAddExpr(LHS: RightSCEV, RHS: SE.getOne(Ty: RightSCEV->getType()));
332 } else {
333 assert(!DecreasedRightValueByOne &&
334 "Right value can be decreased only for LatchBrExitIdx == 0!");
335 }
336 } else {
337 bool IncreasedRightValueByOne = false;
338 if (StepCI->isMinusOne()) {
339 // Try to turn eq/ne predicates to those we can work with.
340 if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
341 // while (--i != len) { while (--i > len) {
342 // ... ---> ...
343 // } }
344 // We intentionally don't turn the predicate into UGT even if we know
345 // that both operands are non-negative, because it will only pessimize
346 // our check against "RightSCEV - 1".
347 Pred = ICmpInst::ICMP_SGT;
348 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
349 // while (true) { while (true) {
350 // if (--i == len) ---> if (--i < len + 1)
351 // break; break;
352 // ... ...
353 // } }
354 if (IndVarBase->getNoWrapFlags(Mask: SCEV::FlagNUW) &&
355 cannotBeMaxInLoop(S: RightSCEV, L: &L, SE, /* Signed */ false)) {
356 Pred = ICmpInst::ICMP_ULT;
357 RightSCEV = SE.getAddExpr(LHS: RightSCEV, RHS: SE.getOne(Ty: RightSCEV->getType()));
358 IncreasedRightValueByOne = true;
359 } else if (cannotBeMaxInLoop(S: RightSCEV, L: &L, SE, /* Signed */ true)) {
360 Pred = ICmpInst::ICMP_SLT;
361 RightSCEV = SE.getAddExpr(LHS: RightSCEV, RHS: SE.getOne(Ty: RightSCEV->getType()));
362 IncreasedRightValueByOne = true;
363 }
364 }
365 }
366
367 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
368 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
369
370 bool FoundExpectedPred =
371 (GTPred && LatchBrExitIdx == 1) || (LTPred && LatchBrExitIdx == 0);
372
373 if (!FoundExpectedPred) {
374 FailureReason = "expected icmp sgt semantically, found something else";
375 return std::nullopt;
376 }
377
378 IsSignedPredicate =
379 Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
380
381 if (!IsSignedPredicate && !AllowUnsignedLatchCond) {
382 FailureReason = "unsigned latch conditions are explicitly prohibited";
383 return std::nullopt;
384 }
385
386 if (!isSafeDecreasingBound(Start: IndVarStart, BoundSCEV: RightSCEV, Step, Pred,
387 LatchBrExitIdx, L: &L, SE)) {
388 FailureReason = "Unsafe bounds";
389 return std::nullopt;
390 }
391
392 if (LatchBrExitIdx == 0) {
393 // We need to decrease the right value unless we have already increased
394 // it virtually when we replaced EQ with SLT.
395 if (!IncreasedRightValueByOne)
396 FixedRightSCEV =
397 SE.getMinusSCEV(LHS: RightSCEV, RHS: SE.getOne(Ty: RightSCEV->getType()));
398 } else {
399 assert(!IncreasedRightValueByOne &&
400 "Right value can be increased only for LatchBrExitIdx == 0!");
401 }
402 }
403 BasicBlock *LatchExit = LatchBr->getSuccessor(i: LatchBrExitIdx);
404
405 assert(!L.contains(LatchExit) && "expected an exit block!");
406 SCEVExpander Expander(SE, "loop-constrainer");
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 IndVarStartV->setName("indvar.start");
415
416 LoopStructure Result;
417
418 Result.Tag = "main";
419 Result.Header = Header;
420 Result.Latch = Latch;
421 Result.LatchBr = LatchBr;
422 Result.LatchExit = LatchExit;
423 Result.LatchBrExitIdx = LatchBrExitIdx;
424 Result.IndVarStart = IndVarStartV;
425 Result.IndVarStep = StepCI;
426 Result.IndVarBase = LeftValue;
427 Result.IndVarIncreasing = IsIncreasing;
428 Result.LoopExitAt = RightValue;
429 Result.IsSignedPredicate = IsSignedPredicate;
430 Result.ExitCountTy = cast<IntegerType>(Val: MaxBETakenCount->getType());
431
432 FailureReason = nullptr;
433
434 return Result;
435}
436
437// Add metadata to the loop L to disable loop optimizations. Callers need to
438// confirm that optimizing loop L is not beneficial.
439static void DisableAllLoopOptsOnLoop(Loop &L) {
440 // We do not care about any existing loopID related metadata for L, since we
441 // are setting all loop metadata to false.
442 LLVMContext &Context = L.getHeader()->getContext();
443 // Reserve first location for self reference to the LoopID metadata node.
444 MDNode *Dummy = MDNode::get(Context, MDs: {});
445 MDNode *DisableUnroll = MDNode::get(
446 Context, MDs: {MDString::get(Context, Str: "llvm.loop.unroll.disable")});
447 Metadata *FalseVal =
448 ConstantAsMetadata::get(C: ConstantInt::get(Ty: Type::getInt1Ty(C&: Context), V: 0));
449 MDNode *DisableVectorize = MDNode::get(
450 Context,
451 MDs: {MDString::get(Context, Str: "llvm.loop.vectorize.enable"), FalseVal});
452 MDNode *DisableLICMVersioning = MDNode::get(
453 Context, MDs: {MDString::get(Context, Str: "llvm.loop.licm_versioning.disable")});
454 MDNode *DisableDistribution = MDNode::get(
455 Context,
456 MDs: {MDString::get(Context, Str: "llvm.loop.distribute.enable"), FalseVal});
457 MDNode *NewLoopID =
458 MDNode::get(Context, MDs: {Dummy, DisableUnroll, DisableVectorize,
459 DisableLICMVersioning, DisableDistribution});
460 // Set operand 0 to refer to the loop id itself.
461 NewLoopID->replaceOperandWith(I: 0, New: NewLoopID);
462 L.setLoopID(NewLoopID);
463}
464
465LoopConstrainer::LoopConstrainer(Loop &L, LoopInfo &LI,
466 function_ref<void(Loop *, bool)> LPMAddNewLoop,
467 const LoopStructure &LS, ScalarEvolution &SE,
468 DominatorTree &DT, Type *T, SubRanges SR)
469 : F(*L.getHeader()->getParent()), Ctx(L.getHeader()->getContext()), SE(SE),
470 DT(DT), LI(LI), LPMAddNewLoop(LPMAddNewLoop), OriginalLoop(L), RangeTy(T),
471 MainLoopStructure(LS), SR(SR) {}
472
473void LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result,
474 const char *Tag) const {
475 for (BasicBlock *BB : OriginalLoop.getBlocks()) {
476 BasicBlock *Clone = CloneBasicBlock(BB, VMap&: Result.Map, NameSuffix: Twine(".") + Tag, F: &F);
477 Result.Blocks.push_back(x: Clone);
478 Result.Map[BB] = Clone;
479 }
480
481 auto GetClonedValue = [&Result](Value *V) {
482 assert(V && "null values not in domain!");
483 auto It = Result.Map.find(Val: V);
484 if (It == Result.Map.end())
485 return V;
486 return static_cast<Value *>(It->second);
487 };
488
489 auto *ClonedLatch =
490 cast<BasicBlock>(Val: GetClonedValue(OriginalLoop.getLoopLatch()));
491 ClonedLatch->getTerminator()->setMetadata(Kind: ClonedLoopTag,
492 Node: MDNode::get(Context&: Ctx, MDs: {}));
493
494 Result.Structure = MainLoopStructure.map(Map: GetClonedValue);
495 Result.Structure.Tag = Tag;
496
497 for (unsigned i = 0, e = Result.Blocks.size(); i != e; ++i) {
498 BasicBlock *ClonedBB = Result.Blocks[i];
499 BasicBlock *OriginalBB = OriginalLoop.getBlocks()[i];
500
501 assert(Result.Map[OriginalBB] == ClonedBB && "invariant!");
502
503 for (Instruction &I : *ClonedBB)
504 RemapInstruction(I: &I, VM&: Result.Map,
505 Flags: RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
506
507 // Exit blocks will now have one more predecessor and their PHI nodes need
508 // to be edited to reflect that. No phi nodes need to be introduced because
509 // the loop is in LCSSA.
510
511 for (auto *SBB : successors(BB: OriginalBB)) {
512 if (OriginalLoop.contains(BB: SBB))
513 continue; // not an exit block
514
515 for (PHINode &PN : SBB->phis()) {
516 Value *OldIncoming = PN.getIncomingValueForBlock(BB: OriginalBB);
517 PN.addIncoming(V: GetClonedValue(OldIncoming), BB: ClonedBB);
518 SE.forgetLcssaPhiWithNewPredecessor(L: &OriginalLoop, V: &PN);
519 }
520 }
521 }
522}
523
524LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(
525 const LoopStructure &LS, BasicBlock *Preheader, Value *ExitSubloopAt,
526 BasicBlock *ContinuationBlock) const {
527 // We start with a loop with a single latch:
528 //
529 // +--------------------+
530 // | |
531 // | preheader |
532 // | |
533 // +--------+-----------+
534 // | ----------------\
535 // | / |
536 // +--------v----v------+ |
537 // | | |
538 // | header | |
539 // | | |
540 // +--------------------+ |
541 // |
542 // ..... |
543 // |
544 // +--------------------+ |
545 // | | |
546 // | latch >----------/
547 // | |
548 // +-------v------------+
549 // |
550 // |
551 // | +--------------------+
552 // | | |
553 // +---> original exit |
554 // | |
555 // +--------------------+
556 //
557 // We change the control flow to look like
558 //
559 //
560 // +--------------------+
561 // | |
562 // | preheader >-------------------------+
563 // | | |
564 // +--------v-----------+ |
565 // | /-------------+ |
566 // | / | |
567 // +--------v--v--------+ | |
568 // | | | |
569 // | header | | +--------+ |
570 // | | | | | |
571 // +--------------------+ | | +-----v-----v-----------+
572 // | | | |
573 // | | | .pseudo.exit |
574 // | | | |
575 // | | +-----------v-----------+
576 // | | |
577 // ..... | | |
578 // | | +--------v-------------+
579 // +--------------------+ | | | |
580 // | | | | | ContinuationBlock |
581 // | latch >------+ | | |
582 // | | | +----------------------+
583 // +---------v----------+ |
584 // | |
585 // | |
586 // | +---------------^-----+
587 // | | |
588 // +-----> .exit.selector |
589 // | |
590 // +----------v----------+
591 // |
592 // +--------------------+ |
593 // | | |
594 // | original exit <----+
595 // | |
596 // +--------------------+
597
598 RewrittenRangeInfo RRI;
599
600 BasicBlock *BBInsertLocation = LS.Latch->getNextNode();
601 RRI.ExitSelector = BasicBlock::Create(Context&: Ctx, Name: Twine(LS.Tag) + ".exit.selector",
602 Parent: &F, InsertBefore: BBInsertLocation);
603 RRI.PseudoExit = BasicBlock::Create(Context&: Ctx, Name: Twine(LS.Tag) + ".pseudo.exit", Parent: &F,
604 InsertBefore: BBInsertLocation);
605
606 BranchInst *PreheaderJump = cast<BranchInst>(Val: Preheader->getTerminator());
607 bool Increasing = LS.IndVarIncreasing;
608 bool IsSignedPredicate = LS.IsSignedPredicate;
609
610 IRBuilder<> B(PreheaderJump);
611 auto NoopOrExt = [&](Value *V) {
612 if (V->getType() == RangeTy)
613 return V;
614 return IsSignedPredicate ? B.CreateSExt(V, DestTy: RangeTy, Name: "wide." + V->getName())
615 : B.CreateZExt(V, DestTy: RangeTy, Name: "wide." + V->getName());
616 };
617
618 // EnterLoopCond - is it okay to start executing this `LS'?
619 Value *EnterLoopCond = nullptr;
620 auto Pred =
621 Increasing
622 ? (IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT)
623 : (IsSignedPredicate ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT);
624 Value *IndVarStart = NoopOrExt(LS.IndVarStart);
625 EnterLoopCond = B.CreateICmp(P: Pred, LHS: IndVarStart, RHS: ExitSubloopAt);
626
627 B.CreateCondBr(Cond: EnterLoopCond, True: LS.Header, False: RRI.PseudoExit);
628 PreheaderJump->eraseFromParent();
629
630 LS.LatchBr->setSuccessor(idx: LS.LatchBrExitIdx, NewSucc: RRI.ExitSelector);
631 B.SetInsertPoint(LS.LatchBr);
632 Value *IndVarBase = NoopOrExt(LS.IndVarBase);
633 Value *TakeBackedgeLoopCond = B.CreateICmp(P: Pred, LHS: IndVarBase, RHS: ExitSubloopAt);
634
635 Value *CondForBranch = LS.LatchBrExitIdx == 1
636 ? TakeBackedgeLoopCond
637 : B.CreateNot(V: TakeBackedgeLoopCond);
638
639 LS.LatchBr->setCondition(CondForBranch);
640
641 B.SetInsertPoint(RRI.ExitSelector);
642
643 // IterationsLeft - are there any more iterations left, given the original
644 // upper bound on the induction variable? If not, we branch to the "real"
645 // exit.
646 Value *LoopExitAt = NoopOrExt(LS.LoopExitAt);
647 Value *IterationsLeft = B.CreateICmp(P: Pred, LHS: IndVarBase, RHS: LoopExitAt);
648 B.CreateCondBr(Cond: IterationsLeft, True: RRI.PseudoExit, False: LS.LatchExit);
649
650 BranchInst *BranchToContinuation =
651 BranchInst::Create(IfTrue: ContinuationBlock, InsertBefore: RRI.PseudoExit);
652
653 // We emit PHI nodes into `RRI.PseudoExit' that compute the "latest" value of
654 // each of the PHI nodes in the loop header. This feeds into the initial
655 // value of the same PHI nodes if/when we continue execution.
656 for (PHINode &PN : LS.Header->phis()) {
657 PHINode *NewPHI = PHINode::Create(Ty: PN.getType(), NumReservedValues: 2, NameStr: PN.getName() + ".copy",
658 InsertBefore: BranchToContinuation->getIterator());
659
660 NewPHI->addIncoming(V: PN.getIncomingValueForBlock(BB: Preheader), BB: Preheader);
661 NewPHI->addIncoming(V: PN.getIncomingValueForBlock(BB: LS.Latch),
662 BB: RRI.ExitSelector);
663 RRI.PHIValuesAtPseudoExit.push_back(x: NewPHI);
664 }
665
666 RRI.IndVarEnd = PHINode::Create(Ty: IndVarBase->getType(), NumReservedValues: 2, NameStr: "indvar.end",
667 InsertBefore: BranchToContinuation->getIterator());
668 RRI.IndVarEnd->addIncoming(V: IndVarStart, BB: Preheader);
669 RRI.IndVarEnd->addIncoming(V: IndVarBase, BB: RRI.ExitSelector);
670
671 // The latch exit now has a branch from `RRI.ExitSelector' instead of
672 // `LS.Latch'. The PHI nodes need to be updated to reflect that.
673 LS.LatchExit->replacePhiUsesWith(Old: LS.Latch, New: RRI.ExitSelector);
674
675 return RRI;
676}
677
678void LoopConstrainer::rewriteIncomingValuesForPHIs(
679 LoopStructure &LS, BasicBlock *ContinuationBlock,
680 const LoopConstrainer::RewrittenRangeInfo &RRI) const {
681 unsigned PHIIndex = 0;
682 for (PHINode &PN : LS.Header->phis())
683 PN.setIncomingValueForBlock(BB: ContinuationBlock,
684 V: RRI.PHIValuesAtPseudoExit[PHIIndex++]);
685
686 LS.IndVarStart = RRI.IndVarEnd;
687}
688
689BasicBlock *LoopConstrainer::createPreheader(const LoopStructure &LS,
690 BasicBlock *OldPreheader,
691 const char *Tag) const {
692 BasicBlock *Preheader = BasicBlock::Create(Context&: Ctx, Name: Tag, Parent: &F, InsertBefore: LS.Header);
693 BranchInst::Create(IfTrue: LS.Header, InsertBefore: Preheader);
694
695 LS.Header->replacePhiUsesWith(Old: OldPreheader, New: Preheader);
696
697 return Preheader;
698}
699
700void LoopConstrainer::addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs) {
701 Loop *ParentLoop = OriginalLoop.getParentLoop();
702 if (!ParentLoop)
703 return;
704
705 for (BasicBlock *BB : BBs)
706 ParentLoop->addBasicBlockToLoop(NewBB: BB, LI);
707}
708
709Loop *LoopConstrainer::createClonedLoopStructure(Loop *Original, Loop *Parent,
710 ValueToValueMapTy &VM,
711 bool IsSubloop) {
712 Loop &New = *LI.AllocateLoop();
713 if (Parent)
714 Parent->addChildLoop(NewChild: &New);
715 else
716 LI.addTopLevelLoop(New: &New);
717 LPMAddNewLoop(&New, IsSubloop);
718
719 // Add all of the blocks in Original to the new loop.
720 for (auto *BB : Original->blocks())
721 if (LI.getLoopFor(BB) == Original)
722 New.addBasicBlockToLoop(NewBB: cast<BasicBlock>(Val&: VM[BB]), LI);
723
724 // Add all of the subloops to the new loop.
725 for (Loop *SubLoop : *Original)
726 createClonedLoopStructure(Original: SubLoop, Parent: &New, VM, /* IsSubloop */ true);
727
728 return &New;
729}
730
731bool LoopConstrainer::run() {
732 BasicBlock *Preheader = OriginalLoop.getLoopPreheader();
733 assert(Preheader != nullptr && "precondition!");
734
735 OriginalPreheader = Preheader;
736 MainLoopPreheader = Preheader;
737 bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;
738 bool Increasing = MainLoopStructure.IndVarIncreasing;
739 IntegerType *IVTy = cast<IntegerType>(Val: RangeTy);
740
741 SCEVExpander Expander(SE, "loop-constrainer");
742 Instruction *InsertPt = OriginalPreheader->getTerminator();
743
744 // It would have been better to make `PreLoop' and `PostLoop'
745 // `std::optional<ClonedLoop>'s, but `ValueToValueMapTy' does not have a copy
746 // constructor.
747 ClonedLoop PreLoop, PostLoop;
748 bool NeedsPreLoop =
749 Increasing ? SR.LowLimit.has_value() : SR.HighLimit.has_value();
750 bool NeedsPostLoop =
751 Increasing ? SR.HighLimit.has_value() : SR.LowLimit.has_value();
752
753 Value *ExitPreLoopAt = nullptr;
754 Value *ExitMainLoopAt = nullptr;
755 const SCEVConstant *MinusOneS =
756 cast<SCEVConstant>(Val: SE.getConstant(Ty: IVTy, V: -1, isSigned: true /* isSigned */));
757
758 if (NeedsPreLoop) {
759 const SCEV *ExitPreLoopAtSCEV = nullptr;
760
761 if (Increasing)
762 ExitPreLoopAtSCEV = *SR.LowLimit;
763 else if (cannotBeMinInLoop(S: *SR.HighLimit, L: &OriginalLoop, SE,
764 Signed: IsSignedPredicate))
765 ExitPreLoopAtSCEV = SE.getAddExpr(LHS: *SR.HighLimit, RHS: MinusOneS);
766 else {
767 LLVM_DEBUG(dbgs() << "could not prove no-overflow when computing "
768 << "preloop exit limit. HighLimit = "
769 << *(*SR.HighLimit) << "\n");
770 return false;
771 }
772
773 if (!Expander.isSafeToExpandAt(S: ExitPreLoopAtSCEV, InsertionPoint: InsertPt)) {
774 LLVM_DEBUG(dbgs() << "could not prove that it is safe to expand the"
775 << " preloop exit limit " << *ExitPreLoopAtSCEV
776 << " at block " << InsertPt->getParent()->getName()
777 << "\n");
778 return false;
779 }
780
781 ExitPreLoopAt = Expander.expandCodeFor(SH: ExitPreLoopAtSCEV, Ty: IVTy, I: InsertPt);
782 ExitPreLoopAt->setName("exit.preloop.at");
783 }
784
785 if (NeedsPostLoop) {
786 const SCEV *ExitMainLoopAtSCEV = nullptr;
787
788 if (Increasing)
789 ExitMainLoopAtSCEV = *SR.HighLimit;
790 else if (cannotBeMinInLoop(S: *SR.LowLimit, L: &OriginalLoop, SE,
791 Signed: IsSignedPredicate))
792 ExitMainLoopAtSCEV = SE.getAddExpr(LHS: *SR.LowLimit, RHS: MinusOneS);
793 else {
794 LLVM_DEBUG(dbgs() << "could not prove no-overflow when computing "
795 << "mainloop exit limit. LowLimit = "
796 << *(*SR.LowLimit) << "\n");
797 return false;
798 }
799
800 if (!Expander.isSafeToExpandAt(S: ExitMainLoopAtSCEV, InsertionPoint: InsertPt)) {
801 LLVM_DEBUG(dbgs() << "could not prove that it is safe to expand the"
802 << " main loop exit limit " << *ExitMainLoopAtSCEV
803 << " at block " << InsertPt->getParent()->getName()
804 << "\n");
805 return false;
806 }
807
808 ExitMainLoopAt = Expander.expandCodeFor(SH: ExitMainLoopAtSCEV, Ty: IVTy, I: InsertPt);
809 ExitMainLoopAt->setName("exit.mainloop.at");
810 }
811
812 // We clone these ahead of time so that we don't have to deal with changing
813 // and temporarily invalid IR as we transform the loops.
814 if (NeedsPreLoop)
815 cloneLoop(Result&: PreLoop, Tag: "preloop");
816 if (NeedsPostLoop)
817 cloneLoop(Result&: PostLoop, Tag: "postloop");
818
819 RewrittenRangeInfo PreLoopRRI;
820
821 if (NeedsPreLoop) {
822 Preheader->getTerminator()->replaceUsesOfWith(From: MainLoopStructure.Header,
823 To: PreLoop.Structure.Header);
824
825 MainLoopPreheader =
826 createPreheader(LS: MainLoopStructure, OldPreheader: Preheader, Tag: "mainloop");
827 PreLoopRRI = changeIterationSpaceEnd(LS: PreLoop.Structure, Preheader,
828 ExitSubloopAt: ExitPreLoopAt, ContinuationBlock: MainLoopPreheader);
829 rewriteIncomingValuesForPHIs(LS&: MainLoopStructure, ContinuationBlock: MainLoopPreheader,
830 RRI: PreLoopRRI);
831 }
832
833 BasicBlock *PostLoopPreheader = nullptr;
834 RewrittenRangeInfo PostLoopRRI;
835
836 if (NeedsPostLoop) {
837 PostLoopPreheader =
838 createPreheader(LS: PostLoop.Structure, OldPreheader: Preheader, Tag: "postloop");
839 PostLoopRRI = changeIterationSpaceEnd(LS: MainLoopStructure, Preheader: MainLoopPreheader,
840 ExitSubloopAt: ExitMainLoopAt, ContinuationBlock: PostLoopPreheader);
841 rewriteIncomingValuesForPHIs(LS&: PostLoop.Structure, ContinuationBlock: PostLoopPreheader,
842 RRI: PostLoopRRI);
843 }
844
845 BasicBlock *NewMainLoopPreheader =
846 MainLoopPreheader != Preheader ? MainLoopPreheader : nullptr;
847 BasicBlock *NewBlocks[] = {PostLoopPreheader, PreLoopRRI.PseudoExit,
848 PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit,
849 PostLoopRRI.ExitSelector, NewMainLoopPreheader};
850
851 // Some of the above may be nullptr, filter them out before passing to
852 // addToParentLoopIfNeeded.
853 auto NewBlocksEnd =
854 std::remove(first: std::begin(arr&: NewBlocks), last: std::end(arr&: NewBlocks), value: nullptr);
855
856 addToParentLoopIfNeeded(BBs: ArrayRef(std::begin(arr&: NewBlocks), NewBlocksEnd));
857
858 DT.recalculate(Func&: F);
859
860 // We need to first add all the pre and post loop blocks into the loop
861 // structures (as part of createClonedLoopStructure), and then update the
862 // LCSSA form and LoopSimplifyForm. This is necessary for correctly updating
863 // LI when LoopSimplifyForm is generated.
864 Loop *PreL = nullptr, *PostL = nullptr;
865 if (!PreLoop.Blocks.empty()) {
866 PreL = createClonedLoopStructure(Original: &OriginalLoop,
867 Parent: OriginalLoop.getParentLoop(), VM&: PreLoop.Map,
868 /* IsSubLoop */ IsSubloop: false);
869 }
870
871 if (!PostLoop.Blocks.empty()) {
872 PostL =
873 createClonedLoopStructure(Original: &OriginalLoop, Parent: OriginalLoop.getParentLoop(),
874 VM&: PostLoop.Map, /* IsSubLoop */ IsSubloop: false);
875 }
876
877 // This function canonicalizes the loop into Loop-Simplify and LCSSA forms.
878 auto CanonicalizeLoop = [&](Loop *L, bool IsOriginalLoop) {
879 formLCSSARecursively(L&: *L, DT, LI: &LI, SE: &SE);
880 simplifyLoop(L, DT: &DT, LI: &LI, SE: &SE, AC: nullptr, MSSAU: nullptr, PreserveLCSSA: true);
881 // Pre/post loops are slow paths, we do not need to perform any loop
882 // optimizations on them.
883 if (!IsOriginalLoop)
884 DisableAllLoopOptsOnLoop(L&: *L);
885 };
886 if (PreL)
887 CanonicalizeLoop(PreL, false);
888 if (PostL)
889 CanonicalizeLoop(PostL, false);
890 CanonicalizeLoop(&OriginalLoop, true);
891
892 /// At this point:
893 /// - We've broken a "main loop" out of the loop in a way that the "main loop"
894 /// runs with the induction variable in a subset of [Begin, End).
895 /// - There is no overflow when computing "main loop" exit limit.
896 /// - Max latch taken count of the loop is limited.
897 /// It guarantees that induction variable will not overflow iterating in the
898 /// "main loop".
899 if (isa<OverflowingBinaryOperator>(Val: MainLoopStructure.IndVarBase))
900 if (IsSignedPredicate)
901 cast<BinaryOperator>(Val: MainLoopStructure.IndVarBase)
902 ->setHasNoSignedWrap(true);
903 /// TODO: support unsigned predicate.
904 /// To add NUW flag we need to prove that both operands of BO are
905 /// non-negative. E.g:
906 /// ...
907 /// %iv.next = add nsw i32 %iv, -1
908 /// %cmp = icmp ult i32 %iv.next, %n
909 /// br i1 %cmp, label %loopexit, label %loop
910 ///
911 /// -1 is MAX_UINT in terms of unsigned int. Adding anything but zero will
912 /// overflow, therefore NUW flag is not legal here.
913
914 return true;
915}
916