1 | //===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This transformation analyzes and transforms the induction variables (and |
10 | // computations derived from them) into simpler forms suitable for subsequent |
11 | // analysis and transformation. |
12 | // |
13 | // If the trip count of a loop is computable, this pass also makes the following |
14 | // changes: |
15 | // 1. The exit condition for the loop is canonicalized to compare the |
16 | // induction value against the exit value. This turns loops like: |
17 | // 'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)' |
18 | // 2. Any use outside of the loop of an expression derived from the indvar |
19 | // is changed to compute the derived value outside of the loop, eliminating |
20 | // the dependence on the exit value of the induction variable. If the only |
21 | // purpose of the loop is to compute the exit value of some derived |
22 | // expression, this transformation will make the loop dead. |
23 | // |
24 | //===----------------------------------------------------------------------===// |
25 | |
26 | #include "llvm/Transforms/Scalar/IndVarSimplify.h" |
27 | #include "llvm/ADT/APFloat.h" |
28 | #include "llvm/ADT/ArrayRef.h" |
29 | #include "llvm/ADT/STLExtras.h" |
30 | #include "llvm/ADT/SmallPtrSet.h" |
31 | #include "llvm/ADT/SmallSet.h" |
32 | #include "llvm/ADT/SmallVector.h" |
33 | #include "llvm/ADT/Statistic.h" |
34 | #include "llvm/ADT/iterator_range.h" |
35 | #include "llvm/Analysis/LoopInfo.h" |
36 | #include "llvm/Analysis/LoopPass.h" |
37 | #include "llvm/Analysis/MemorySSA.h" |
38 | #include "llvm/Analysis/MemorySSAUpdater.h" |
39 | #include "llvm/Analysis/ScalarEvolution.h" |
40 | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
41 | #include "llvm/Analysis/TargetLibraryInfo.h" |
42 | #include "llvm/Analysis/TargetTransformInfo.h" |
43 | #include "llvm/Analysis/ValueTracking.h" |
44 | #include "llvm/IR/BasicBlock.h" |
45 | #include "llvm/IR/Constant.h" |
46 | #include "llvm/IR/ConstantRange.h" |
47 | #include "llvm/IR/Constants.h" |
48 | #include "llvm/IR/DataLayout.h" |
49 | #include "llvm/IR/DerivedTypes.h" |
50 | #include "llvm/IR/Dominators.h" |
51 | #include "llvm/IR/Function.h" |
52 | #include "llvm/IR/IRBuilder.h" |
53 | #include "llvm/IR/InstrTypes.h" |
54 | #include "llvm/IR/Instruction.h" |
55 | #include "llvm/IR/Instructions.h" |
56 | #include "llvm/IR/IntrinsicInst.h" |
57 | #include "llvm/IR/Intrinsics.h" |
58 | #include "llvm/IR/Module.h" |
59 | #include "llvm/IR/Operator.h" |
60 | #include "llvm/IR/PassManager.h" |
61 | #include "llvm/IR/PatternMatch.h" |
62 | #include "llvm/IR/Type.h" |
63 | #include "llvm/IR/Use.h" |
64 | #include "llvm/IR/User.h" |
65 | #include "llvm/IR/Value.h" |
66 | #include "llvm/IR/ValueHandle.h" |
67 | #include "llvm/Support/Casting.h" |
68 | #include "llvm/Support/CommandLine.h" |
69 | #include "llvm/Support/Compiler.h" |
70 | #include "llvm/Support/Debug.h" |
71 | #include "llvm/Support/MathExtras.h" |
72 | #include "llvm/Support/raw_ostream.h" |
73 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
74 | #include "llvm/Transforms/Utils/Local.h" |
75 | #include "llvm/Transforms/Utils/LoopUtils.h" |
76 | #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" |
77 | #include "llvm/Transforms/Utils/SimplifyIndVar.h" |
78 | #include <cassert> |
79 | #include <cstdint> |
80 | #include <utility> |
81 | |
82 | using namespace llvm; |
83 | using namespace PatternMatch; |
84 | |
85 | #define DEBUG_TYPE "indvars" |
86 | |
87 | STATISTIC(NumWidened , "Number of indvars widened" ); |
88 | STATISTIC(NumReplaced , "Number of exit values replaced" ); |
89 | STATISTIC(NumLFTR , "Number of loop exit tests replaced" ); |
90 | STATISTIC(NumElimExt , "Number of IV sign/zero extends eliminated" ); |
91 | STATISTIC(NumElimIV , "Number of congruent IVs eliminated" ); |
92 | |
93 | static cl::opt<ReplaceExitVal> ReplaceExitValue( |
94 | "replexitval" , cl::Hidden, cl::init(Val: OnlyCheapRepl), |
95 | cl::desc("Choose the strategy to replace exit value in IndVarSimplify" ), |
96 | cl::values( |
97 | clEnumValN(NeverRepl, "never" , "never replace exit value" ), |
98 | clEnumValN(OnlyCheapRepl, "cheap" , |
99 | "only replace exit value when the cost is cheap" ), |
100 | clEnumValN( |
101 | UnusedIndVarInLoop, "unusedindvarinloop" , |
102 | "only replace exit value when it is an unused " |
103 | "induction variable in the loop and has cheap replacement cost" ), |
104 | clEnumValN(NoHardUse, "noharduse" , |
105 | "only replace exit values when loop def likely dead" ), |
106 | clEnumValN(AlwaysRepl, "always" , |
107 | "always replace exit value whenever possible" ))); |
108 | |
109 | static cl::opt<bool> UsePostIncrementRanges( |
110 | "indvars-post-increment-ranges" , cl::Hidden, |
111 | cl::desc("Use post increment control-dependent ranges in IndVarSimplify" ), |
112 | cl::init(Val: true)); |
113 | |
114 | static cl::opt<bool> |
115 | DisableLFTR("disable-lftr" , cl::Hidden, cl::init(Val: false), |
116 | cl::desc("Disable Linear Function Test Replace optimization" )); |
117 | |
118 | static cl::opt<bool> |
119 | LoopPredication("indvars-predicate-loops" , cl::Hidden, cl::init(Val: true), |
120 | cl::desc("Predicate conditions in read only loops" )); |
121 | |
122 | static cl::opt<bool> |
123 | AllowIVWidening("indvars-widen-indvars" , cl::Hidden, cl::init(Val: true), |
124 | cl::desc("Allow widening of indvars to eliminate s/zext" )); |
125 | |
126 | namespace { |
127 | |
128 | class IndVarSimplify { |
129 | LoopInfo *LI; |
130 | ScalarEvolution *SE; |
131 | DominatorTree *DT; |
132 | const DataLayout &DL; |
133 | TargetLibraryInfo *TLI; |
134 | const TargetTransformInfo *TTI; |
135 | std::unique_ptr<MemorySSAUpdater> MSSAU; |
136 | |
137 | SmallVector<WeakTrackingVH, 16> DeadInsts; |
138 | bool WidenIndVars; |
139 | |
140 | bool handleFloatingPointIV(Loop *L, PHINode *PH); |
141 | bool rewriteNonIntegerIVs(Loop *L); |
142 | |
143 | bool simplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LoopInfo *LI); |
144 | /// Try to improve our exit conditions by converting condition from signed |
145 | /// to unsigned or rotating computation out of the loop. |
146 | /// (See inline comment about why this is duplicated from simplifyAndExtend) |
147 | bool canonicalizeExitCondition(Loop *L); |
148 | /// Try to eliminate loop exits based on analyzeable exit counts |
149 | bool optimizeLoopExits(Loop *L, SCEVExpander &Rewriter); |
150 | /// Try to form loop invariant tests for loop exits by changing how many |
151 | /// iterations of the loop run when that is unobservable. |
152 | bool predicateLoopExits(Loop *L, SCEVExpander &Rewriter); |
153 | |
154 | bool rewriteFirstIterationLoopExitValues(Loop *L); |
155 | |
156 | bool linearFunctionTestReplace(Loop *L, BasicBlock *ExitingBB, |
157 | const SCEV *ExitCount, |
158 | PHINode *IndVar, SCEVExpander &Rewriter); |
159 | |
160 | bool sinkUnusedInvariants(Loop *L); |
161 | |
162 | public: |
163 | IndVarSimplify(LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, |
164 | const DataLayout &DL, TargetLibraryInfo *TLI, |
165 | TargetTransformInfo *TTI, MemorySSA *MSSA, bool WidenIndVars) |
166 | : LI(LI), SE(SE), DT(DT), DL(DL), TLI(TLI), TTI(TTI), |
167 | WidenIndVars(WidenIndVars) { |
168 | if (MSSA) |
169 | MSSAU = std::make_unique<MemorySSAUpdater>(args&: MSSA); |
170 | } |
171 | |
172 | bool run(Loop *L); |
173 | }; |
174 | |
175 | } // end anonymous namespace |
176 | |
177 | //===----------------------------------------------------------------------===// |
178 | // rewriteNonIntegerIVs and helpers. Prefer integer IVs. |
179 | //===----------------------------------------------------------------------===// |
180 | |
181 | /// Convert APF to an integer, if possible. |
182 | static bool ConvertToSInt(const APFloat &APF, int64_t &IntVal) { |
183 | bool isExact = false; |
184 | // See if we can convert this to an int64_t |
185 | uint64_t UIntVal; |
186 | if (APF.convertToInteger(Input: MutableArrayRef(UIntVal), Width: 64, IsSigned: true, |
187 | RM: APFloat::rmTowardZero, IsExact: &isExact) != APFloat::opOK || |
188 | !isExact) |
189 | return false; |
190 | IntVal = UIntVal; |
191 | return true; |
192 | } |
193 | |
194 | /// If the loop has floating induction variable then insert corresponding |
195 | /// integer induction variable if possible. |
196 | /// For example, |
197 | /// for(double i = 0; i < 10000; ++i) |
198 | /// bar(i) |
199 | /// is converted into |
200 | /// for(int i = 0; i < 10000; ++i) |
201 | /// bar((double)i); |
202 | bool IndVarSimplify::handleFloatingPointIV(Loop *L, PHINode *PN) { |
203 | unsigned IncomingEdge = L->contains(BB: PN->getIncomingBlock(i: 0)); |
204 | unsigned BackEdge = IncomingEdge^1; |
205 | |
206 | // Check incoming value. |
207 | auto *InitValueVal = dyn_cast<ConstantFP>(Val: PN->getIncomingValue(i: IncomingEdge)); |
208 | |
209 | int64_t InitValue; |
210 | if (!InitValueVal || !ConvertToSInt(APF: InitValueVal->getValueAPF(), IntVal&: InitValue)) |
211 | return false; |
212 | |
213 | // Check IV increment. Reject this PN if increment operation is not |
214 | // an add or increment value can not be represented by an integer. |
215 | auto *Incr = dyn_cast<BinaryOperator>(Val: PN->getIncomingValue(i: BackEdge)); |
216 | if (Incr == nullptr || Incr->getOpcode() != Instruction::FAdd) return false; |
217 | |
218 | // If this is not an add of the PHI with a constantfp, or if the constant fp |
219 | // is not an integer, bail out. |
220 | ConstantFP *IncValueVal = dyn_cast<ConstantFP>(Val: Incr->getOperand(i_nocapture: 1)); |
221 | int64_t IncValue; |
222 | if (IncValueVal == nullptr || Incr->getOperand(i_nocapture: 0) != PN || |
223 | !ConvertToSInt(APF: IncValueVal->getValueAPF(), IntVal&: IncValue)) |
224 | return false; |
225 | |
226 | // Check Incr uses. One user is PN and the other user is an exit condition |
227 | // used by the conditional terminator. |
228 | Value::user_iterator IncrUse = Incr->user_begin(); |
229 | Instruction *U1 = cast<Instruction>(Val: *IncrUse++); |
230 | if (IncrUse == Incr->user_end()) return false; |
231 | Instruction *U2 = cast<Instruction>(Val: *IncrUse++); |
232 | if (IncrUse != Incr->user_end()) return false; |
233 | |
234 | // Find exit condition, which is an fcmp. If it doesn't exist, or if it isn't |
235 | // only used by a branch, we can't transform it. |
236 | FCmpInst *Compare = dyn_cast<FCmpInst>(Val: U1); |
237 | if (!Compare) |
238 | Compare = dyn_cast<FCmpInst>(Val: U2); |
239 | if (!Compare || !Compare->hasOneUse() || |
240 | !isa<BranchInst>(Val: Compare->user_back())) |
241 | return false; |
242 | |
243 | BranchInst *TheBr = cast<BranchInst>(Val: Compare->user_back()); |
244 | |
245 | // We need to verify that the branch actually controls the iteration count |
246 | // of the loop. If not, the new IV can overflow and no one will notice. |
247 | // The branch block must be in the loop and one of the successors must be out |
248 | // of the loop. |
249 | assert(TheBr->isConditional() && "Can't use fcmp if not conditional" ); |
250 | if (!L->contains(BB: TheBr->getParent()) || |
251 | (L->contains(BB: TheBr->getSuccessor(i: 0)) && |
252 | L->contains(BB: TheBr->getSuccessor(i: 1)))) |
253 | return false; |
254 | |
255 | // If it isn't a comparison with an integer-as-fp (the exit value), we can't |
256 | // transform it. |
257 | ConstantFP *ExitValueVal = dyn_cast<ConstantFP>(Val: Compare->getOperand(i_nocapture: 1)); |
258 | int64_t ExitValue; |
259 | if (ExitValueVal == nullptr || |
260 | !ConvertToSInt(APF: ExitValueVal->getValueAPF(), IntVal&: ExitValue)) |
261 | return false; |
262 | |
263 | // Find new predicate for integer comparison. |
264 | CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE; |
265 | switch (Compare->getPredicate()) { |
266 | default: return false; // Unknown comparison. |
267 | case CmpInst::FCMP_OEQ: |
268 | case CmpInst::FCMP_UEQ: NewPred = CmpInst::ICMP_EQ; break; |
269 | case CmpInst::FCMP_ONE: |
270 | case CmpInst::FCMP_UNE: NewPred = CmpInst::ICMP_NE; break; |
271 | case CmpInst::FCMP_OGT: |
272 | case CmpInst::FCMP_UGT: NewPred = CmpInst::ICMP_SGT; break; |
273 | case CmpInst::FCMP_OGE: |
274 | case CmpInst::FCMP_UGE: NewPred = CmpInst::ICMP_SGE; break; |
275 | case CmpInst::FCMP_OLT: |
276 | case CmpInst::FCMP_ULT: NewPred = CmpInst::ICMP_SLT; break; |
277 | case CmpInst::FCMP_OLE: |
278 | case CmpInst::FCMP_ULE: NewPred = CmpInst::ICMP_SLE; break; |
279 | } |
280 | |
281 | // We convert the floating point induction variable to a signed i32 value if |
282 | // we can. This is only safe if the comparison will not overflow in a way |
283 | // that won't be trapped by the integer equivalent operations. Check for this |
284 | // now. |
285 | // TODO: We could use i64 if it is native and the range requires it. |
286 | |
287 | // The start/stride/exit values must all fit in signed i32. |
288 | if (!isInt<32>(x: InitValue) || !isInt<32>(x: IncValue) || !isInt<32>(x: ExitValue)) |
289 | return false; |
290 | |
291 | // If not actually striding (add x, 0.0), avoid touching the code. |
292 | if (IncValue == 0) |
293 | return false; |
294 | |
295 | // Positive and negative strides have different safety conditions. |
296 | if (IncValue > 0) { |
297 | // If we have a positive stride, we require the init to be less than the |
298 | // exit value. |
299 | if (InitValue >= ExitValue) |
300 | return false; |
301 | |
302 | uint32_t Range = uint32_t(ExitValue-InitValue); |
303 | // Check for infinite loop, either: |
304 | // while (i <= Exit) or until (i > Exit) |
305 | if (NewPred == CmpInst::ICMP_SLE || NewPred == CmpInst::ICMP_SGT) { |
306 | if (++Range == 0) return false; // Range overflows. |
307 | } |
308 | |
309 | unsigned Leftover = Range % uint32_t(IncValue); |
310 | |
311 | // If this is an equality comparison, we require that the strided value |
312 | // exactly land on the exit value, otherwise the IV condition will wrap |
313 | // around and do things the fp IV wouldn't. |
314 | if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) && |
315 | Leftover != 0) |
316 | return false; |
317 | |
318 | // If the stride would wrap around the i32 before exiting, we can't |
319 | // transform the IV. |
320 | if (Leftover != 0 && int32_t(ExitValue+IncValue) < ExitValue) |
321 | return false; |
322 | } else { |
323 | // If we have a negative stride, we require the init to be greater than the |
324 | // exit value. |
325 | if (InitValue <= ExitValue) |
326 | return false; |
327 | |
328 | uint32_t Range = uint32_t(InitValue-ExitValue); |
329 | // Check for infinite loop, either: |
330 | // while (i >= Exit) or until (i < Exit) |
331 | if (NewPred == CmpInst::ICMP_SGE || NewPred == CmpInst::ICMP_SLT) { |
332 | if (++Range == 0) return false; // Range overflows. |
333 | } |
334 | |
335 | unsigned Leftover = Range % uint32_t(-IncValue); |
336 | |
337 | // If this is an equality comparison, we require that the strided value |
338 | // exactly land on the exit value, otherwise the IV condition will wrap |
339 | // around and do things the fp IV wouldn't. |
340 | if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) && |
341 | Leftover != 0) |
342 | return false; |
343 | |
344 | // If the stride would wrap around the i32 before exiting, we can't |
345 | // transform the IV. |
346 | if (Leftover != 0 && int32_t(ExitValue+IncValue) > ExitValue) |
347 | return false; |
348 | } |
349 | |
350 | IntegerType *Int32Ty = Type::getInt32Ty(C&: PN->getContext()); |
351 | |
352 | // Insert new integer induction variable. |
353 | PHINode *NewPHI = PHINode::Create(Ty: Int32Ty, NumReservedValues: 2, NameStr: PN->getName()+".int" , InsertBefore: PN); |
354 | NewPHI->addIncoming(V: ConstantInt::get(Ty: Int32Ty, V: InitValue), |
355 | BB: PN->getIncomingBlock(i: IncomingEdge)); |
356 | |
357 | Value *NewAdd = |
358 | BinaryOperator::CreateAdd(V1: NewPHI, V2: ConstantInt::get(Ty: Int32Ty, V: IncValue), |
359 | Name: Incr->getName()+".int" , I: Incr); |
360 | NewPHI->addIncoming(V: NewAdd, BB: PN->getIncomingBlock(i: BackEdge)); |
361 | |
362 | ICmpInst *NewCompare = new ICmpInst(TheBr, NewPred, NewAdd, |
363 | ConstantInt::get(Ty: Int32Ty, V: ExitValue), |
364 | Compare->getName()); |
365 | |
366 | // In the following deletions, PN may become dead and may be deleted. |
367 | // Use a WeakTrackingVH to observe whether this happens. |
368 | WeakTrackingVH WeakPH = PN; |
369 | |
370 | // Delete the old floating point exit comparison. The branch starts using the |
371 | // new comparison. |
372 | NewCompare->takeName(V: Compare); |
373 | Compare->replaceAllUsesWith(V: NewCompare); |
374 | RecursivelyDeleteTriviallyDeadInstructions(V: Compare, TLI, MSSAU: MSSAU.get()); |
375 | |
376 | // Delete the old floating point increment. |
377 | Incr->replaceAllUsesWith(V: PoisonValue::get(T: Incr->getType())); |
378 | RecursivelyDeleteTriviallyDeadInstructions(V: Incr, TLI, MSSAU: MSSAU.get()); |
379 | |
380 | // If the FP induction variable still has uses, this is because something else |
381 | // in the loop uses its value. In order to canonicalize the induction |
382 | // variable, we chose to eliminate the IV and rewrite it in terms of an |
383 | // int->fp cast. |
384 | // |
385 | // We give preference to sitofp over uitofp because it is faster on most |
386 | // platforms. |
387 | if (WeakPH) { |
388 | Value *Conv = new SIToFPInst(NewPHI, PN->getType(), "indvar.conv" , |
389 | &*PN->getParent()->getFirstInsertionPt()); |
390 | PN->replaceAllUsesWith(V: Conv); |
391 | RecursivelyDeleteTriviallyDeadInstructions(V: PN, TLI, MSSAU: MSSAU.get()); |
392 | } |
393 | return true; |
394 | } |
395 | |
396 | bool IndVarSimplify::rewriteNonIntegerIVs(Loop *L) { |
397 | // First step. Check to see if there are any floating-point recurrences. |
398 | // If there are, change them into integer recurrences, permitting analysis by |
399 | // the SCEV routines. |
400 | BasicBlock * = L->getHeader(); |
401 | |
402 | SmallVector<WeakTrackingVH, 8> PHIs; |
403 | for (PHINode &PN : Header->phis()) |
404 | PHIs.push_back(Elt: &PN); |
405 | |
406 | bool Changed = false; |
407 | for (WeakTrackingVH &PHI : PHIs) |
408 | if (PHINode *PN = dyn_cast_or_null<PHINode>(Val: &*PHI)) |
409 | Changed |= handleFloatingPointIV(L, PN); |
410 | |
411 | // If the loop previously had floating-point IV, ScalarEvolution |
412 | // may not have been able to compute a trip count. Now that we've done some |
413 | // re-writing, the trip count may be computable. |
414 | if (Changed) |
415 | SE->forgetLoop(L); |
416 | return Changed; |
417 | } |
418 | |
419 | //===---------------------------------------------------------------------===// |
420 | // rewriteFirstIterationLoopExitValues: Rewrite loop exit values if we know |
421 | // they will exit at the first iteration. |
422 | //===---------------------------------------------------------------------===// |
423 | |
424 | /// Check to see if this loop has loop invariant conditions which lead to loop |
425 | /// exits. If so, we know that if the exit path is taken, it is at the first |
426 | /// loop iteration. This lets us predict exit values of PHI nodes that live in |
427 | /// loop header. |
428 | bool IndVarSimplify::rewriteFirstIterationLoopExitValues(Loop *L) { |
429 | // Verify the input to the pass is already in LCSSA form. |
430 | assert(L->isLCSSAForm(*DT)); |
431 | |
432 | SmallVector<BasicBlock *, 8> ExitBlocks; |
433 | L->getUniqueExitBlocks(ExitBlocks); |
434 | |
435 | bool MadeAnyChanges = false; |
436 | for (auto *ExitBB : ExitBlocks) { |
437 | // If there are no more PHI nodes in this exit block, then no more |
438 | // values defined inside the loop are used on this path. |
439 | for (PHINode &PN : ExitBB->phis()) { |
440 | for (unsigned IncomingValIdx = 0, E = PN.getNumIncomingValues(); |
441 | IncomingValIdx != E; ++IncomingValIdx) { |
442 | auto *IncomingBB = PN.getIncomingBlock(i: IncomingValIdx); |
443 | |
444 | // Can we prove that the exit must run on the first iteration if it |
445 | // runs at all? (i.e. early exits are fine for our purposes, but |
446 | // traces which lead to this exit being taken on the 2nd iteration |
447 | // aren't.) Note that this is about whether the exit branch is |
448 | // executed, not about whether it is taken. |
449 | if (!L->getLoopLatch() || |
450 | !DT->dominates(A: IncomingBB, B: L->getLoopLatch())) |
451 | continue; |
452 | |
453 | // Get condition that leads to the exit path. |
454 | auto *TermInst = IncomingBB->getTerminator(); |
455 | |
456 | Value *Cond = nullptr; |
457 | if (auto *BI = dyn_cast<BranchInst>(Val: TermInst)) { |
458 | // Must be a conditional branch, otherwise the block |
459 | // should not be in the loop. |
460 | Cond = BI->getCondition(); |
461 | } else if (auto *SI = dyn_cast<SwitchInst>(Val: TermInst)) |
462 | Cond = SI->getCondition(); |
463 | else |
464 | continue; |
465 | |
466 | if (!L->isLoopInvariant(V: Cond)) |
467 | continue; |
468 | |
469 | auto *ExitVal = dyn_cast<PHINode>(Val: PN.getIncomingValue(i: IncomingValIdx)); |
470 | |
471 | // Only deal with PHIs in the loop header. |
472 | if (!ExitVal || ExitVal->getParent() != L->getHeader()) |
473 | continue; |
474 | |
475 | // If ExitVal is a PHI on the loop header, then we know its |
476 | // value along this exit because the exit can only be taken |
477 | // on the first iteration. |
478 | auto * = L->getLoopPreheader(); |
479 | assert(LoopPreheader && "Invalid loop" ); |
480 | int = ExitVal->getBasicBlockIndex(BB: LoopPreheader); |
481 | if (PreheaderIdx != -1) { |
482 | assert(ExitVal->getParent() == L->getHeader() && |
483 | "ExitVal must be in loop header" ); |
484 | MadeAnyChanges = true; |
485 | PN.setIncomingValue(i: IncomingValIdx, |
486 | V: ExitVal->getIncomingValue(i: PreheaderIdx)); |
487 | SE->forgetValue(V: &PN); |
488 | } |
489 | } |
490 | } |
491 | } |
492 | return MadeAnyChanges; |
493 | } |
494 | |
495 | //===----------------------------------------------------------------------===// |
496 | // IV Widening - Extend the width of an IV to cover its widest uses. |
497 | //===----------------------------------------------------------------------===// |
498 | |
499 | /// Update information about the induction variable that is extended by this |
500 | /// sign or zero extend operation. This is used to determine the final width of |
501 | /// the IV before actually widening it. |
502 | static void visitIVCast(CastInst *Cast, WideIVInfo &WI, |
503 | ScalarEvolution *SE, |
504 | const TargetTransformInfo *TTI) { |
505 | bool IsSigned = Cast->getOpcode() == Instruction::SExt; |
506 | if (!IsSigned && Cast->getOpcode() != Instruction::ZExt) |
507 | return; |
508 | |
509 | Type *Ty = Cast->getType(); |
510 | uint64_t Width = SE->getTypeSizeInBits(Ty); |
511 | if (!Cast->getModule()->getDataLayout().isLegalInteger(Width)) |
512 | return; |
513 | |
514 | // Check that `Cast` actually extends the induction variable (we rely on this |
515 | // later). This takes care of cases where `Cast` is extending a truncation of |
516 | // the narrow induction variable, and thus can end up being narrower than the |
517 | // "narrow" induction variable. |
518 | uint64_t NarrowIVWidth = SE->getTypeSizeInBits(Ty: WI.NarrowIV->getType()); |
519 | if (NarrowIVWidth >= Width) |
520 | return; |
521 | |
522 | // Cast is either an sext or zext up to this point. |
523 | // We should not widen an indvar if arithmetics on the wider indvar are more |
524 | // expensive than those on the narrower indvar. We check only the cost of ADD |
525 | // because at least an ADD is required to increment the induction variable. We |
526 | // could compute more comprehensively the cost of all instructions on the |
527 | // induction variable when necessary. |
528 | if (TTI && |
529 | TTI->getArithmeticInstrCost(Opcode: Instruction::Add, Ty) > |
530 | TTI->getArithmeticInstrCost(Opcode: Instruction::Add, |
531 | Ty: Cast->getOperand(i_nocapture: 0)->getType())) { |
532 | return; |
533 | } |
534 | |
535 | if (!WI.WidestNativeType || |
536 | Width > SE->getTypeSizeInBits(Ty: WI.WidestNativeType)) { |
537 | WI.WidestNativeType = SE->getEffectiveSCEVType(Ty); |
538 | WI.IsSigned = IsSigned; |
539 | return; |
540 | } |
541 | |
542 | // We extend the IV to satisfy the sign of its user(s), or 'signed' |
543 | // if there are multiple users with both sign- and zero extensions, |
544 | // in order not to introduce nondeterministic behaviour based on the |
545 | // unspecified order of a PHI nodes' users-iterator. |
546 | WI.IsSigned |= IsSigned; |
547 | } |
548 | |
549 | //===----------------------------------------------------------------------===// |
550 | // Live IV Reduction - Minimize IVs live across the loop. |
551 | //===----------------------------------------------------------------------===// |
552 | |
553 | //===----------------------------------------------------------------------===// |
554 | // Simplification of IV users based on SCEV evaluation. |
555 | //===----------------------------------------------------------------------===// |
556 | |
557 | namespace { |
558 | |
559 | class IndVarSimplifyVisitor : public IVVisitor { |
560 | ScalarEvolution *SE; |
561 | const TargetTransformInfo *TTI; |
562 | PHINode *IVPhi; |
563 | |
564 | public: |
565 | WideIVInfo WI; |
566 | |
567 | IndVarSimplifyVisitor(PHINode *IV, ScalarEvolution *SCEV, |
568 | const TargetTransformInfo *TTI, |
569 | const DominatorTree *DTree) |
570 | : SE(SCEV), TTI(TTI), IVPhi(IV) { |
571 | DT = DTree; |
572 | WI.NarrowIV = IVPhi; |
573 | } |
574 | |
575 | // Implement the interface used by simplifyUsersOfIV. |
576 | void visitCast(CastInst *Cast) override { visitIVCast(Cast, WI, SE, TTI); } |
577 | }; |
578 | |
579 | } // end anonymous namespace |
580 | |
581 | /// Iteratively perform simplification on a worklist of IV users. Each |
582 | /// successive simplification may push more users which may themselves be |
583 | /// candidates for simplification. |
584 | /// |
585 | /// Sign/Zero extend elimination is interleaved with IV simplification. |
586 | bool IndVarSimplify::simplifyAndExtend(Loop *L, |
587 | SCEVExpander &Rewriter, |
588 | LoopInfo *LI) { |
589 | SmallVector<WideIVInfo, 8> WideIVs; |
590 | |
591 | auto *GuardDecl = L->getBlocks()[0]->getModule()->getFunction( |
592 | Intrinsic::getName(Intrinsic::experimental_guard)); |
593 | bool HasGuards = GuardDecl && !GuardDecl->use_empty(); |
594 | |
595 | SmallVector<PHINode *, 8> LoopPhis; |
596 | for (PHINode &PN : L->getHeader()->phis()) |
597 | LoopPhis.push_back(Elt: &PN); |
598 | |
599 | // Each round of simplification iterates through the SimplifyIVUsers worklist |
600 | // for all current phis, then determines whether any IVs can be |
601 | // widened. Widening adds new phis to LoopPhis, inducing another round of |
602 | // simplification on the wide IVs. |
603 | bool Changed = false; |
604 | while (!LoopPhis.empty()) { |
605 | // Evaluate as many IV expressions as possible before widening any IVs. This |
606 | // forces SCEV to set no-wrap flags before evaluating sign/zero |
607 | // extension. The first time SCEV attempts to normalize sign/zero extension, |
608 | // the result becomes final. So for the most predictable results, we delay |
609 | // evaluation of sign/zero extend evaluation until needed, and avoid running |
610 | // other SCEV based analysis prior to simplifyAndExtend. |
611 | do { |
612 | PHINode *CurrIV = LoopPhis.pop_back_val(); |
613 | |
614 | // Information about sign/zero extensions of CurrIV. |
615 | IndVarSimplifyVisitor Visitor(CurrIV, SE, TTI, DT); |
616 | |
617 | Changed |= simplifyUsersOfIV(CurrIV, SE, DT, LI, TTI, Dead&: DeadInsts, Rewriter, |
618 | V: &Visitor); |
619 | |
620 | if (Visitor.WI.WidestNativeType) { |
621 | WideIVs.push_back(Elt: Visitor.WI); |
622 | } |
623 | } while(!LoopPhis.empty()); |
624 | |
625 | // Continue if we disallowed widening. |
626 | if (!WidenIndVars) |
627 | continue; |
628 | |
629 | for (; !WideIVs.empty(); WideIVs.pop_back()) { |
630 | unsigned ElimExt; |
631 | unsigned Widened; |
632 | if (PHINode *WidePhi = createWideIV(WI: WideIVs.back(), LI, SE, Rewriter, |
633 | DT, DeadInsts, NumElimExt&: ElimExt, NumWidened&: Widened, |
634 | HasGuards, UsePostIncrementRanges)) { |
635 | NumElimExt += ElimExt; |
636 | NumWidened += Widened; |
637 | Changed = true; |
638 | LoopPhis.push_back(Elt: WidePhi); |
639 | } |
640 | } |
641 | } |
642 | return Changed; |
643 | } |
644 | |
645 | //===----------------------------------------------------------------------===// |
646 | // linearFunctionTestReplace and its kin. Rewrite the loop exit condition. |
647 | //===----------------------------------------------------------------------===// |
648 | |
649 | /// Given an Value which is hoped to be part of an add recurance in the given |
650 | /// loop, return the associated Phi node if so. Otherwise, return null. Note |
651 | /// that this is less general than SCEVs AddRec checking. |
652 | static PHINode *getLoopPhiForCounter(Value *IncV, Loop *L) { |
653 | Instruction *IncI = dyn_cast<Instruction>(Val: IncV); |
654 | if (!IncI) |
655 | return nullptr; |
656 | |
657 | switch (IncI->getOpcode()) { |
658 | case Instruction::Add: |
659 | case Instruction::Sub: |
660 | break; |
661 | case Instruction::GetElementPtr: |
662 | // An IV counter must preserve its type. |
663 | if (IncI->getNumOperands() == 2) |
664 | break; |
665 | [[fallthrough]]; |
666 | default: |
667 | return nullptr; |
668 | } |
669 | |
670 | PHINode *Phi = dyn_cast<PHINode>(Val: IncI->getOperand(i: 0)); |
671 | if (Phi && Phi->getParent() == L->getHeader()) { |
672 | if (L->isLoopInvariant(V: IncI->getOperand(i: 1))) |
673 | return Phi; |
674 | return nullptr; |
675 | } |
676 | if (IncI->getOpcode() == Instruction::GetElementPtr) |
677 | return nullptr; |
678 | |
679 | // Allow add/sub to be commuted. |
680 | Phi = dyn_cast<PHINode>(Val: IncI->getOperand(i: 1)); |
681 | if (Phi && Phi->getParent() == L->getHeader()) { |
682 | if (L->isLoopInvariant(V: IncI->getOperand(i: 0))) |
683 | return Phi; |
684 | } |
685 | return nullptr; |
686 | } |
687 | |
688 | /// Whether the current loop exit test is based on this value. Currently this |
689 | /// is limited to a direct use in the loop condition. |
690 | static bool isLoopExitTestBasedOn(Value *V, BasicBlock *ExitingBB) { |
691 | BranchInst *BI = cast<BranchInst>(Val: ExitingBB->getTerminator()); |
692 | ICmpInst *ICmp = dyn_cast<ICmpInst>(Val: BI->getCondition()); |
693 | // TODO: Allow non-icmp loop test. |
694 | if (!ICmp) |
695 | return false; |
696 | |
697 | // TODO: Allow indirect use. |
698 | return ICmp->getOperand(i_nocapture: 0) == V || ICmp->getOperand(i_nocapture: 1) == V; |
699 | } |
700 | |
701 | /// linearFunctionTestReplace policy. Return true unless we can show that the |
702 | /// current exit test is already sufficiently canonical. |
703 | static bool needsLFTR(Loop *L, BasicBlock *ExitingBB) { |
704 | assert(L->getLoopLatch() && "Must be in simplified form" ); |
705 | |
706 | // Avoid converting a constant or loop invariant test back to a runtime |
707 | // test. This is critical for when SCEV's cached ExitCount is less precise |
708 | // than the current IR (such as after we've proven a particular exit is |
709 | // actually dead and thus the BE count never reaches our ExitCount.) |
710 | BranchInst *BI = cast<BranchInst>(Val: ExitingBB->getTerminator()); |
711 | if (L->isLoopInvariant(V: BI->getCondition())) |
712 | return false; |
713 | |
714 | // Do LFTR to simplify the exit condition to an ICMP. |
715 | ICmpInst *Cond = dyn_cast<ICmpInst>(Val: BI->getCondition()); |
716 | if (!Cond) |
717 | return true; |
718 | |
719 | // Do LFTR to simplify the exit ICMP to EQ/NE |
720 | ICmpInst::Predicate Pred = Cond->getPredicate(); |
721 | if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ) |
722 | return true; |
723 | |
724 | // Look for a loop invariant RHS |
725 | Value *LHS = Cond->getOperand(i_nocapture: 0); |
726 | Value *RHS = Cond->getOperand(i_nocapture: 1); |
727 | if (!L->isLoopInvariant(V: RHS)) { |
728 | if (!L->isLoopInvariant(V: LHS)) |
729 | return true; |
730 | std::swap(a&: LHS, b&: RHS); |
731 | } |
732 | // Look for a simple IV counter LHS |
733 | PHINode *Phi = dyn_cast<PHINode>(Val: LHS); |
734 | if (!Phi) |
735 | Phi = getLoopPhiForCounter(IncV: LHS, L); |
736 | |
737 | if (!Phi) |
738 | return true; |
739 | |
740 | // Do LFTR if PHI node is defined in the loop, but is *not* a counter. |
741 | int Idx = Phi->getBasicBlockIndex(BB: L->getLoopLatch()); |
742 | if (Idx < 0) |
743 | return true; |
744 | |
745 | // Do LFTR if the exit condition's IV is *not* a simple counter. |
746 | Value *IncV = Phi->getIncomingValue(i: Idx); |
747 | return Phi != getLoopPhiForCounter(IncV, L); |
748 | } |
749 | |
750 | /// Recursive helper for hasConcreteDef(). Unfortunately, this currently boils |
751 | /// down to checking that all operands are constant and listing instructions |
752 | /// that may hide undef. |
753 | static bool hasConcreteDefImpl(Value *V, SmallPtrSetImpl<Value*> &Visited, |
754 | unsigned Depth) { |
755 | if (isa<Constant>(Val: V)) |
756 | return !isa<UndefValue>(Val: V); |
757 | |
758 | if (Depth >= 6) |
759 | return false; |
760 | |
761 | // Conservatively handle non-constant non-instructions. For example, Arguments |
762 | // may be undef. |
763 | Instruction *I = dyn_cast<Instruction>(Val: V); |
764 | if (!I) |
765 | return false; |
766 | |
767 | // Load and return values may be undef. |
768 | if(I->mayReadFromMemory() || isa<CallInst>(Val: I) || isa<InvokeInst>(Val: I)) |
769 | return false; |
770 | |
771 | // Optimistically handle other instructions. |
772 | for (Value *Op : I->operands()) { |
773 | if (!Visited.insert(Ptr: Op).second) |
774 | continue; |
775 | if (!hasConcreteDefImpl(V: Op, Visited, Depth: Depth+1)) |
776 | return false; |
777 | } |
778 | return true; |
779 | } |
780 | |
781 | /// Return true if the given value is concrete. We must prove that undef can |
782 | /// never reach it. |
783 | /// |
784 | /// TODO: If we decide that this is a good approach to checking for undef, we |
785 | /// may factor it into a common location. |
786 | static bool hasConcreteDef(Value *V) { |
787 | SmallPtrSet<Value*, 8> Visited; |
788 | Visited.insert(Ptr: V); |
789 | return hasConcreteDefImpl(V, Visited, Depth: 0); |
790 | } |
791 | |
792 | /// Return true if the given phi is a "counter" in L. A counter is an |
793 | /// add recurance (of integer or pointer type) with an arbitrary start, and a |
794 | /// step of 1. Note that L must have exactly one latch. |
795 | static bool isLoopCounter(PHINode* Phi, Loop *L, |
796 | ScalarEvolution *SE) { |
797 | assert(Phi->getParent() == L->getHeader()); |
798 | assert(L->getLoopLatch()); |
799 | |
800 | if (!SE->isSCEVable(Ty: Phi->getType())) |
801 | return false; |
802 | |
803 | const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Val: SE->getSCEV(V: Phi)); |
804 | if (!AR || AR->getLoop() != L || !AR->isAffine()) |
805 | return false; |
806 | |
807 | const SCEV *Step = dyn_cast<SCEVConstant>(Val: AR->getStepRecurrence(SE&: *SE)); |
808 | if (!Step || !Step->isOne()) |
809 | return false; |
810 | |
811 | int LatchIdx = Phi->getBasicBlockIndex(BB: L->getLoopLatch()); |
812 | Value *IncV = Phi->getIncomingValue(i: LatchIdx); |
813 | return (getLoopPhiForCounter(IncV, L) == Phi && |
814 | isa<SCEVAddRecExpr>(Val: SE->getSCEV(V: IncV))); |
815 | } |
816 | |
817 | /// Search the loop header for a loop counter (anadd rec w/step of one) |
818 | /// suitable for use by LFTR. If multiple counters are available, select the |
819 | /// "best" one based profitable heuristics. |
820 | /// |
821 | /// BECount may be an i8* pointer type. The pointer difference is already |
822 | /// valid count without scaling the address stride, so it remains a pointer |
823 | /// expression as far as SCEV is concerned. |
824 | static PHINode *FindLoopCounter(Loop *L, BasicBlock *ExitingBB, |
825 | const SCEV *BECount, |
826 | ScalarEvolution *SE, DominatorTree *DT) { |
827 | uint64_t BCWidth = SE->getTypeSizeInBits(Ty: BECount->getType()); |
828 | |
829 | Value *Cond = cast<BranchInst>(Val: ExitingBB->getTerminator())->getCondition(); |
830 | |
831 | // Loop over all of the PHI nodes, looking for a simple counter. |
832 | PHINode *BestPhi = nullptr; |
833 | const SCEV *BestInit = nullptr; |
834 | BasicBlock *LatchBlock = L->getLoopLatch(); |
835 | assert(LatchBlock && "Must be in simplified form" ); |
836 | const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); |
837 | |
838 | for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(Val: I); ++I) { |
839 | PHINode *Phi = cast<PHINode>(Val&: I); |
840 | if (!isLoopCounter(Phi, L, SE)) |
841 | continue; |
842 | |
843 | const auto *AR = cast<SCEVAddRecExpr>(Val: SE->getSCEV(V: Phi)); |
844 | |
845 | // AR may be a pointer type, while BECount is an integer type. |
846 | // AR may be wider than BECount. With eq/ne tests overflow is immaterial. |
847 | // AR may not be a narrower type, or we may never exit. |
848 | uint64_t PhiWidth = SE->getTypeSizeInBits(Ty: AR->getType()); |
849 | if (PhiWidth < BCWidth || !DL.isLegalInteger(Width: PhiWidth)) |
850 | continue; |
851 | |
852 | // Avoid reusing a potentially undef value to compute other values that may |
853 | // have originally had a concrete definition. |
854 | if (!hasConcreteDef(V: Phi)) { |
855 | // We explicitly allow unknown phis as long as they are already used by |
856 | // the loop exit test. This is legal since performing LFTR could not |
857 | // increase the number of undef users. |
858 | Value *IncPhi = Phi->getIncomingValueForBlock(BB: LatchBlock); |
859 | if (!isLoopExitTestBasedOn(V: Phi, ExitingBB) && |
860 | !isLoopExitTestBasedOn(V: IncPhi, ExitingBB)) |
861 | continue; |
862 | } |
863 | |
864 | // Avoid introducing undefined behavior due to poison which didn't exist in |
865 | // the original program. (Annoyingly, the rules for poison and undef |
866 | // propagation are distinct, so this does NOT cover the undef case above.) |
867 | // We have to ensure that we don't introduce UB by introducing a use on an |
868 | // iteration where said IV produces poison. Our strategy here differs for |
869 | // pointers and integer IVs. For integers, we strip and reinfer as needed, |
870 | // see code in linearFunctionTestReplace. For pointers, we restrict |
871 | // transforms as there is no good way to reinfer inbounds once lost. |
872 | if (!Phi->getType()->isIntegerTy() && |
873 | !mustExecuteUBIfPoisonOnPathTo(Root: Phi, OnPathTo: ExitingBB->getTerminator(), DT)) |
874 | continue; |
875 | |
876 | const SCEV *Init = AR->getStart(); |
877 | |
878 | if (BestPhi && !isAlmostDeadIV(IV: BestPhi, LatchBlock, Cond)) { |
879 | // Don't force a live loop counter if another IV can be used. |
880 | if (isAlmostDeadIV(IV: Phi, LatchBlock, Cond)) |
881 | continue; |
882 | |
883 | // Prefer to count-from-zero. This is a more "canonical" counter form. It |
884 | // also prefers integer to pointer IVs. |
885 | if (BestInit->isZero() != Init->isZero()) { |
886 | if (BestInit->isZero()) |
887 | continue; |
888 | } |
889 | // If two IVs both count from zero or both count from nonzero then the |
890 | // narrower is likely a dead phi that has been widened. Use the wider phi |
891 | // to allow the other to be eliminated. |
892 | else if (PhiWidth <= SE->getTypeSizeInBits(Ty: BestPhi->getType())) |
893 | continue; |
894 | } |
895 | BestPhi = Phi; |
896 | BestInit = Init; |
897 | } |
898 | return BestPhi; |
899 | } |
900 | |
901 | /// Insert an IR expression which computes the value held by the IV IndVar |
902 | /// (which must be an loop counter w/unit stride) after the backedge of loop L |
903 | /// is taken ExitCount times. |
904 | static Value *genLoopLimit(PHINode *IndVar, BasicBlock *ExitingBB, |
905 | const SCEV *ExitCount, bool UsePostInc, Loop *L, |
906 | SCEVExpander &Rewriter, ScalarEvolution *SE) { |
907 | assert(isLoopCounter(IndVar, L, SE)); |
908 | assert(ExitCount->getType()->isIntegerTy() && "exit count must be integer" ); |
909 | const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(Val: SE->getSCEV(V: IndVar)); |
910 | assert(AR->getStepRecurrence(*SE)->isOne() && "only handles unit stride" ); |
911 | |
912 | // For integer IVs, truncate the IV before computing the limit unless we |
913 | // know apriori that the limit must be a constant when evaluated in the |
914 | // bitwidth of the IV. We prefer (potentially) keeping a truncate of the |
915 | // IV in the loop over a (potentially) expensive expansion of the widened |
916 | // exit count add(zext(add)) expression. |
917 | if (IndVar->getType()->isIntegerTy() && |
918 | SE->getTypeSizeInBits(Ty: AR->getType()) > |
919 | SE->getTypeSizeInBits(Ty: ExitCount->getType())) { |
920 | const SCEV *IVInit = AR->getStart(); |
921 | if (!isa<SCEVConstant>(Val: IVInit) || !isa<SCEVConstant>(Val: ExitCount)) |
922 | AR = cast<SCEVAddRecExpr>(Val: SE->getTruncateExpr(Op: AR, Ty: ExitCount->getType())); |
923 | } |
924 | |
925 | const SCEVAddRecExpr *ARBase = UsePostInc ? AR->getPostIncExpr(SE&: *SE) : AR; |
926 | const SCEV *IVLimit = ARBase->evaluateAtIteration(It: ExitCount, SE&: *SE); |
927 | assert(SE->isLoopInvariant(IVLimit, L) && |
928 | "Computed iteration count is not loop invariant!" ); |
929 | return Rewriter.expandCodeFor(SH: IVLimit, Ty: ARBase->getType(), |
930 | I: ExitingBB->getTerminator()); |
931 | } |
932 | |
933 | /// This method rewrites the exit condition of the loop to be a canonical != |
934 | /// comparison against the incremented loop induction variable. This pass is |
935 | /// able to rewrite the exit tests of any loop where the SCEV analysis can |
936 | /// determine a loop-invariant trip count of the loop, which is actually a much |
937 | /// broader range than just linear tests. |
938 | bool IndVarSimplify:: |
939 | linearFunctionTestReplace(Loop *L, BasicBlock *ExitingBB, |
940 | const SCEV *ExitCount, |
941 | PHINode *IndVar, SCEVExpander &Rewriter) { |
942 | assert(L->getLoopLatch() && "Loop no longer in simplified form?" ); |
943 | assert(isLoopCounter(IndVar, L, SE)); |
944 | Instruction * const IncVar = |
945 | cast<Instruction>(Val: IndVar->getIncomingValueForBlock(BB: L->getLoopLatch())); |
946 | |
947 | // Initialize CmpIndVar to the preincremented IV. |
948 | Value *CmpIndVar = IndVar; |
949 | bool UsePostInc = false; |
950 | |
951 | // If the exiting block is the same as the backedge block, we prefer to |
952 | // compare against the post-incremented value, otherwise we must compare |
953 | // against the preincremented value. |
954 | if (ExitingBB == L->getLoopLatch()) { |
955 | // For pointer IVs, we chose to not strip inbounds which requires us not |
956 | // to add a potentially UB introducing use. We need to either a) show |
957 | // the loop test we're modifying is already in post-inc form, or b) show |
958 | // that adding a use must not introduce UB. |
959 | bool SafeToPostInc = |
960 | IndVar->getType()->isIntegerTy() || |
961 | isLoopExitTestBasedOn(V: IncVar, ExitingBB) || |
962 | mustExecuteUBIfPoisonOnPathTo(Root: IncVar, OnPathTo: ExitingBB->getTerminator(), DT); |
963 | if (SafeToPostInc) { |
964 | UsePostInc = true; |
965 | CmpIndVar = IncVar; |
966 | } |
967 | } |
968 | |
969 | // It may be necessary to drop nowrap flags on the incrementing instruction |
970 | // if either LFTR moves from a pre-inc check to a post-inc check (in which |
971 | // case the increment might have previously been poison on the last iteration |
972 | // only) or if LFTR switches to a different IV that was previously dynamically |
973 | // dead (and as such may be arbitrarily poison). We remove any nowrap flags |
974 | // that SCEV didn't infer for the post-inc addrec (even if we use a pre-inc |
975 | // check), because the pre-inc addrec flags may be adopted from the original |
976 | // instruction, while SCEV has to explicitly prove the post-inc nowrap flags. |
977 | // TODO: This handling is inaccurate for one case: If we switch to a |
978 | // dynamically dead IV that wraps on the first loop iteration only, which is |
979 | // not covered by the post-inc addrec. (If the new IV was not dynamically |
980 | // dead, it could not be poison on the first iteration in the first place.) |
981 | if (auto *BO = dyn_cast<BinaryOperator>(Val: IncVar)) { |
982 | const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(Val: SE->getSCEV(V: IncVar)); |
983 | if (BO->hasNoUnsignedWrap()) |
984 | BO->setHasNoUnsignedWrap(AR->hasNoUnsignedWrap()); |
985 | if (BO->hasNoSignedWrap()) |
986 | BO->setHasNoSignedWrap(AR->hasNoSignedWrap()); |
987 | } |
988 | |
989 | Value *ExitCnt = genLoopLimit( |
990 | IndVar, ExitingBB, ExitCount, UsePostInc, L, Rewriter, SE); |
991 | assert(ExitCnt->getType()->isPointerTy() == |
992 | IndVar->getType()->isPointerTy() && |
993 | "genLoopLimit missed a cast" ); |
994 | |
995 | // Insert a new icmp_ne or icmp_eq instruction before the branch. |
996 | BranchInst *BI = cast<BranchInst>(Val: ExitingBB->getTerminator()); |
997 | ICmpInst::Predicate P; |
998 | if (L->contains(BB: BI->getSuccessor(i: 0))) |
999 | P = ICmpInst::ICMP_NE; |
1000 | else |
1001 | P = ICmpInst::ICMP_EQ; |
1002 | |
1003 | IRBuilder<> Builder(BI); |
1004 | |
1005 | // The new loop exit condition should reuse the debug location of the |
1006 | // original loop exit condition. |
1007 | if (auto *Cond = dyn_cast<Instruction>(Val: BI->getCondition())) |
1008 | Builder.SetCurrentDebugLocation(Cond->getDebugLoc()); |
1009 | |
1010 | // For integer IVs, if we evaluated the limit in the narrower bitwidth to |
1011 | // avoid the expensive expansion of the limit expression in the wider type, |
1012 | // emit a truncate to narrow the IV to the ExitCount type. This is safe |
1013 | // since we know (from the exit count bitwidth), that we can't self-wrap in |
1014 | // the narrower type. |
1015 | unsigned CmpIndVarSize = SE->getTypeSizeInBits(Ty: CmpIndVar->getType()); |
1016 | unsigned ExitCntSize = SE->getTypeSizeInBits(Ty: ExitCnt->getType()); |
1017 | if (CmpIndVarSize > ExitCntSize) { |
1018 | assert(!CmpIndVar->getType()->isPointerTy() && |
1019 | !ExitCnt->getType()->isPointerTy()); |
1020 | |
1021 | // Before resorting to actually inserting the truncate, use the same |
1022 | // reasoning as from SimplifyIndvar::eliminateTrunc to see if we can extend |
1023 | // the other side of the comparison instead. We still evaluate the limit |
1024 | // in the narrower bitwidth, we just prefer a zext/sext outside the loop to |
1025 | // a truncate within in. |
1026 | bool Extended = false; |
1027 | const SCEV *IV = SE->getSCEV(V: CmpIndVar); |
1028 | const SCEV *TruncatedIV = SE->getTruncateExpr(Op: IV, Ty: ExitCnt->getType()); |
1029 | const SCEV *ZExtTrunc = |
1030 | SE->getZeroExtendExpr(Op: TruncatedIV, Ty: CmpIndVar->getType()); |
1031 | |
1032 | if (ZExtTrunc == IV) { |
1033 | Extended = true; |
1034 | ExitCnt = Builder.CreateZExt(V: ExitCnt, DestTy: IndVar->getType(), |
1035 | Name: "wide.trip.count" ); |
1036 | } else { |
1037 | const SCEV *SExtTrunc = |
1038 | SE->getSignExtendExpr(Op: TruncatedIV, Ty: CmpIndVar->getType()); |
1039 | if (SExtTrunc == IV) { |
1040 | Extended = true; |
1041 | ExitCnt = Builder.CreateSExt(V: ExitCnt, DestTy: IndVar->getType(), |
1042 | Name: "wide.trip.count" ); |
1043 | } |
1044 | } |
1045 | |
1046 | if (Extended) { |
1047 | bool Discard; |
1048 | L->makeLoopInvariant(V: ExitCnt, Changed&: Discard); |
1049 | } else |
1050 | CmpIndVar = Builder.CreateTrunc(V: CmpIndVar, DestTy: ExitCnt->getType(), |
1051 | Name: "lftr.wideiv" ); |
1052 | } |
1053 | LLVM_DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n" |
1054 | << " LHS:" << *CmpIndVar << '\n' |
1055 | << " op:\t" << (P == ICmpInst::ICMP_NE ? "!=" : "==" ) |
1056 | << "\n" |
1057 | << " RHS:\t" << *ExitCnt << "\n" |
1058 | << "ExitCount:\t" << *ExitCount << "\n" |
1059 | << " was: " << *BI->getCondition() << "\n" ); |
1060 | |
1061 | Value *Cond = Builder.CreateICmp(P, LHS: CmpIndVar, RHS: ExitCnt, Name: "exitcond" ); |
1062 | Value *OrigCond = BI->getCondition(); |
1063 | // It's tempting to use replaceAllUsesWith here to fully replace the old |
1064 | // comparison, but that's not immediately safe, since users of the old |
1065 | // comparison may not be dominated by the new comparison. Instead, just |
1066 | // update the branch to use the new comparison; in the common case this |
1067 | // will make old comparison dead. |
1068 | BI->setCondition(Cond); |
1069 | DeadInsts.emplace_back(Args&: OrigCond); |
1070 | |
1071 | ++NumLFTR; |
1072 | return true; |
1073 | } |
1074 | |
1075 | //===----------------------------------------------------------------------===// |
1076 | // sinkUnusedInvariants. A late subpass to cleanup loop preheaders. |
1077 | //===----------------------------------------------------------------------===// |
1078 | |
1079 | /// If there's a single exit block, sink any loop-invariant values that |
1080 | /// were defined in the preheader but not used inside the loop into the |
1081 | /// exit block to reduce register pressure in the loop. |
1082 | bool IndVarSimplify::sinkUnusedInvariants(Loop *L) { |
1083 | BasicBlock *ExitBlock = L->getExitBlock(); |
1084 | if (!ExitBlock) return false; |
1085 | |
1086 | BasicBlock * = L->getLoopPreheader(); |
1087 | if (!Preheader) return false; |
1088 | |
1089 | bool MadeAnyChanges = false; |
1090 | BasicBlock::iterator InsertPt = ExitBlock->getFirstInsertionPt(); |
1091 | BasicBlock::iterator I(Preheader->getTerminator()); |
1092 | while (I != Preheader->begin()) { |
1093 | --I; |
1094 | // New instructions were inserted at the end of the preheader. |
1095 | if (isa<PHINode>(Val: I)) |
1096 | break; |
1097 | |
1098 | // Don't move instructions which might have side effects, since the side |
1099 | // effects need to complete before instructions inside the loop. Also don't |
1100 | // move instructions which might read memory, since the loop may modify |
1101 | // memory. Note that it's okay if the instruction might have undefined |
1102 | // behavior: LoopSimplify guarantees that the preheader dominates the exit |
1103 | // block. |
1104 | if (I->mayHaveSideEffects() || I->mayReadFromMemory()) |
1105 | continue; |
1106 | |
1107 | // Skip debug info intrinsics. |
1108 | if (isa<DbgInfoIntrinsic>(Val: I)) |
1109 | continue; |
1110 | |
1111 | // Skip eh pad instructions. |
1112 | if (I->isEHPad()) |
1113 | continue; |
1114 | |
1115 | // Don't sink alloca: we never want to sink static alloca's out of the |
1116 | // entry block, and correctly sinking dynamic alloca's requires |
1117 | // checks for stacksave/stackrestore intrinsics. |
1118 | // FIXME: Refactor this check somehow? |
1119 | if (isa<AllocaInst>(Val: I)) |
1120 | continue; |
1121 | |
1122 | // Determine if there is a use in or before the loop (direct or |
1123 | // otherwise). |
1124 | bool UsedInLoop = false; |
1125 | for (Use &U : I->uses()) { |
1126 | Instruction *User = cast<Instruction>(Val: U.getUser()); |
1127 | BasicBlock *UseBB = User->getParent(); |
1128 | if (PHINode *P = dyn_cast<PHINode>(Val: User)) { |
1129 | unsigned i = |
1130 | PHINode::getIncomingValueNumForOperand(i: U.getOperandNo()); |
1131 | UseBB = P->getIncomingBlock(i); |
1132 | } |
1133 | if (UseBB == Preheader || L->contains(BB: UseBB)) { |
1134 | UsedInLoop = true; |
1135 | break; |
1136 | } |
1137 | } |
1138 | |
1139 | // If there is, the def must remain in the preheader. |
1140 | if (UsedInLoop) |
1141 | continue; |
1142 | |
1143 | // Otherwise, sink it to the exit block. |
1144 | Instruction *ToMove = &*I; |
1145 | bool Done = false; |
1146 | |
1147 | if (I != Preheader->begin()) { |
1148 | // Skip debug info intrinsics. |
1149 | do { |
1150 | --I; |
1151 | } while (I->isDebugOrPseudoInst() && I != Preheader->begin()); |
1152 | |
1153 | if (I->isDebugOrPseudoInst() && I == Preheader->begin()) |
1154 | Done = true; |
1155 | } else { |
1156 | Done = true; |
1157 | } |
1158 | |
1159 | MadeAnyChanges = true; |
1160 | ToMove->moveBefore(BB&: *ExitBlock, I: InsertPt); |
1161 | SE->forgetValue(V: ToMove); |
1162 | if (Done) break; |
1163 | InsertPt = ToMove->getIterator(); |
1164 | } |
1165 | |
1166 | return MadeAnyChanges; |
1167 | } |
1168 | |
1169 | static void replaceExitCond(BranchInst *BI, Value *NewCond, |
1170 | SmallVectorImpl<WeakTrackingVH> &DeadInsts) { |
1171 | auto *OldCond = BI->getCondition(); |
1172 | LLVM_DEBUG(dbgs() << "Replacing condition of loop-exiting branch " << *BI |
1173 | << " with " << *NewCond << "\n" ); |
1174 | BI->setCondition(NewCond); |
1175 | if (OldCond->use_empty()) |
1176 | DeadInsts.emplace_back(Args&: OldCond); |
1177 | } |
1178 | |
1179 | static Constant *createFoldedExitCond(const Loop *L, BasicBlock *ExitingBB, |
1180 | bool IsTaken) { |
1181 | BranchInst *BI = cast<BranchInst>(Val: ExitingBB->getTerminator()); |
1182 | bool ExitIfTrue = !L->contains(BB: *succ_begin(BB: ExitingBB)); |
1183 | auto *OldCond = BI->getCondition(); |
1184 | return ConstantInt::get(Ty: OldCond->getType(), |
1185 | V: IsTaken ? ExitIfTrue : !ExitIfTrue); |
1186 | } |
1187 | |
1188 | static void foldExit(const Loop *L, BasicBlock *ExitingBB, bool IsTaken, |
1189 | SmallVectorImpl<WeakTrackingVH> &DeadInsts) { |
1190 | BranchInst *BI = cast<BranchInst>(Val: ExitingBB->getTerminator()); |
1191 | auto *NewCond = createFoldedExitCond(L, ExitingBB, IsTaken); |
1192 | replaceExitCond(BI, NewCond, DeadInsts); |
1193 | } |
1194 | |
1195 | static void ( |
1196 | LoopInfo *LI, Loop *L, SmallVectorImpl<WeakTrackingVH> &DeadInsts, |
1197 | ScalarEvolution &SE) { |
1198 | assert(L->isLoopSimplifyForm() && "Should only do it in simplify form!" ); |
1199 | auto * = L->getLoopPreheader(); |
1200 | auto * = L->getHeader(); |
1201 | SmallVector<Instruction *> Worklist; |
1202 | for (auto &PN : LoopHeader->phis()) { |
1203 | auto * = PN.getIncomingValueForBlock(BB: LoopPreheader); |
1204 | for (User *U : PN.users()) |
1205 | Worklist.push_back(Elt: cast<Instruction>(Val: U)); |
1206 | SE.forgetValue(V: &PN); |
1207 | PN.replaceAllUsesWith(V: PreheaderIncoming); |
1208 | DeadInsts.emplace_back(Args: &PN); |
1209 | } |
1210 | |
1211 | // Replacing with the preheader value will often allow IV users to simplify |
1212 | // (especially if the preheader value is a constant). |
1213 | SmallPtrSet<Instruction *, 16> Visited; |
1214 | while (!Worklist.empty()) { |
1215 | auto *I = cast<Instruction>(Val: Worklist.pop_back_val()); |
1216 | if (!Visited.insert(Ptr: I).second) |
1217 | continue; |
1218 | |
1219 | // Don't simplify instructions outside the loop. |
1220 | if (!L->contains(Inst: I)) |
1221 | continue; |
1222 | |
1223 | Value *Res = simplifyInstruction(I, Q: I->getModule()->getDataLayout()); |
1224 | if (Res && LI->replacementPreservesLCSSAForm(From: I, To: Res)) { |
1225 | for (User *U : I->users()) |
1226 | Worklist.push_back(Elt: cast<Instruction>(Val: U)); |
1227 | I->replaceAllUsesWith(V: Res); |
1228 | DeadInsts.emplace_back(Args&: I); |
1229 | } |
1230 | } |
1231 | } |
1232 | |
1233 | static Value * |
1234 | createInvariantCond(const Loop *L, BasicBlock *ExitingBB, |
1235 | const ScalarEvolution::LoopInvariantPredicate &LIP, |
1236 | SCEVExpander &Rewriter) { |
1237 | ICmpInst::Predicate InvariantPred = LIP.Pred; |
1238 | BasicBlock * = L->getLoopPreheader(); |
1239 | assert(Preheader && "Preheader doesn't exist" ); |
1240 | Rewriter.setInsertPoint(Preheader->getTerminator()); |
1241 | auto *LHSV = Rewriter.expandCodeFor(SH: LIP.LHS); |
1242 | auto *RHSV = Rewriter.expandCodeFor(SH: LIP.RHS); |
1243 | bool ExitIfTrue = !L->contains(BB: *succ_begin(BB: ExitingBB)); |
1244 | if (ExitIfTrue) |
1245 | InvariantPred = ICmpInst::getInversePredicate(pred: InvariantPred); |
1246 | IRBuilder<> Builder(Preheader->getTerminator()); |
1247 | BranchInst *BI = cast<BranchInst>(Val: ExitingBB->getTerminator()); |
1248 | return Builder.CreateICmp(P: InvariantPred, LHS: LHSV, RHS: RHSV, |
1249 | Name: BI->getCondition()->getName()); |
1250 | } |
1251 | |
1252 | static std::optional<Value *> |
1253 | createReplacement(ICmpInst *ICmp, const Loop *L, BasicBlock *ExitingBB, |
1254 | const SCEV *MaxIter, bool Inverted, bool SkipLastIter, |
1255 | ScalarEvolution *SE, SCEVExpander &Rewriter) { |
1256 | ICmpInst::Predicate Pred = ICmp->getPredicate(); |
1257 | Value *LHS = ICmp->getOperand(i_nocapture: 0); |
1258 | Value *RHS = ICmp->getOperand(i_nocapture: 1); |
1259 | |
1260 | // 'LHS pred RHS' should now mean that we stay in loop. |
1261 | auto *BI = cast<BranchInst>(Val: ExitingBB->getTerminator()); |
1262 | if (Inverted) |
1263 | Pred = CmpInst::getInversePredicate(pred: Pred); |
1264 | |
1265 | const SCEV *LHSS = SE->getSCEVAtScope(V: LHS, L); |
1266 | const SCEV *RHSS = SE->getSCEVAtScope(V: RHS, L); |
1267 | // Can we prove it to be trivially true or false? |
1268 | if (auto EV = SE->evaluatePredicateAt(Pred, LHS: LHSS, RHS: RHSS, CtxI: BI)) |
1269 | return createFoldedExitCond(L, ExitingBB, /*IsTaken*/ !*EV); |
1270 | |
1271 | auto *ARTy = LHSS->getType(); |
1272 | auto *MaxIterTy = MaxIter->getType(); |
1273 | // If possible, adjust types. |
1274 | if (SE->getTypeSizeInBits(Ty: ARTy) > SE->getTypeSizeInBits(Ty: MaxIterTy)) |
1275 | MaxIter = SE->getZeroExtendExpr(Op: MaxIter, Ty: ARTy); |
1276 | else if (SE->getTypeSizeInBits(Ty: ARTy) < SE->getTypeSizeInBits(Ty: MaxIterTy)) { |
1277 | const SCEV *MinusOne = SE->getMinusOne(Ty: ARTy); |
1278 | auto *MaxAllowedIter = SE->getZeroExtendExpr(Op: MinusOne, Ty: MaxIterTy); |
1279 | if (SE->isKnownPredicateAt(Pred: ICmpInst::ICMP_ULE, LHS: MaxIter, RHS: MaxAllowedIter, CtxI: BI)) |
1280 | MaxIter = SE->getTruncateExpr(Op: MaxIter, Ty: ARTy); |
1281 | } |
1282 | |
1283 | if (SkipLastIter) { |
1284 | // Semantically skip last iter is "subtract 1, do not bother about unsigned |
1285 | // wrap". getLoopInvariantExitCondDuringFirstIterations knows how to deal |
1286 | // with umin in a smart way, but umin(a, b) - 1 will likely not simplify. |
1287 | // So we manually construct umin(a - 1, b - 1). |
1288 | SmallVector<const SCEV *, 4> Elements; |
1289 | if (auto *UMin = dyn_cast<SCEVUMinExpr>(Val: MaxIter)) { |
1290 | for (auto *Op : UMin->operands()) |
1291 | Elements.push_back(Elt: SE->getMinusSCEV(LHS: Op, RHS: SE->getOne(Ty: Op->getType()))); |
1292 | MaxIter = SE->getUMinFromMismatchedTypes(Ops&: Elements); |
1293 | } else |
1294 | MaxIter = SE->getMinusSCEV(LHS: MaxIter, RHS: SE->getOne(Ty: MaxIter->getType())); |
1295 | } |
1296 | |
1297 | // Check if there is a loop-invariant predicate equivalent to our check. |
1298 | auto LIP = SE->getLoopInvariantExitCondDuringFirstIterations(Pred, LHS: LHSS, RHS: RHSS, |
1299 | L, CtxI: BI, MaxIter); |
1300 | if (!LIP) |
1301 | return std::nullopt; |
1302 | |
1303 | // Can we prove it to be trivially true? |
1304 | if (SE->isKnownPredicateAt(Pred: LIP->Pred, LHS: LIP->LHS, RHS: LIP->RHS, CtxI: BI)) |
1305 | return createFoldedExitCond(L, ExitingBB, /*IsTaken*/ false); |
1306 | else |
1307 | return createInvariantCond(L, ExitingBB, LIP: *LIP, Rewriter); |
1308 | } |
1309 | |
1310 | static bool optimizeLoopExitWithUnknownExitCount( |
1311 | const Loop *L, BranchInst *BI, BasicBlock *ExitingBB, const SCEV *MaxIter, |
1312 | bool SkipLastIter, ScalarEvolution *SE, SCEVExpander &Rewriter, |
1313 | SmallVectorImpl<WeakTrackingVH> &DeadInsts) { |
1314 | assert( |
1315 | (L->contains(BI->getSuccessor(0)) != L->contains(BI->getSuccessor(1))) && |
1316 | "Not a loop exit!" ); |
1317 | |
1318 | // For branch that stays in loop by TRUE condition, go through AND. For branch |
1319 | // that stays in loop by FALSE condition, go through OR. Both gives the |
1320 | // similar logic: "stay in loop iff all conditions are true(false)". |
1321 | bool Inverted = L->contains(BB: BI->getSuccessor(i: 1)); |
1322 | SmallVector<ICmpInst *, 4> LeafConditions; |
1323 | SmallVector<Value *, 4> Worklist; |
1324 | SmallPtrSet<Value *, 4> Visited; |
1325 | Value *OldCond = BI->getCondition(); |
1326 | Visited.insert(Ptr: OldCond); |
1327 | Worklist.push_back(Elt: OldCond); |
1328 | |
1329 | auto GoThrough = [&](Value *V) { |
1330 | Value *LHS = nullptr, *RHS = nullptr; |
1331 | if (Inverted) { |
1332 | if (!match(V, P: m_LogicalOr(L: m_Value(V&: LHS), R: m_Value(V&: RHS)))) |
1333 | return false; |
1334 | } else { |
1335 | if (!match(V, P: m_LogicalAnd(L: m_Value(V&: LHS), R: m_Value(V&: RHS)))) |
1336 | return false; |
1337 | } |
1338 | if (Visited.insert(Ptr: LHS).second) |
1339 | Worklist.push_back(Elt: LHS); |
1340 | if (Visited.insert(Ptr: RHS).second) |
1341 | Worklist.push_back(Elt: RHS); |
1342 | return true; |
1343 | }; |
1344 | |
1345 | do { |
1346 | Value *Curr = Worklist.pop_back_val(); |
1347 | // Go through AND/OR conditions. Collect leaf ICMPs. We only care about |
1348 | // those with one use, to avoid instruction duplication. |
1349 | if (Curr->hasOneUse()) |
1350 | if (!GoThrough(Curr)) |
1351 | if (auto *ICmp = dyn_cast<ICmpInst>(Val: Curr)) |
1352 | LeafConditions.push_back(Elt: ICmp); |
1353 | } while (!Worklist.empty()); |
1354 | |
1355 | // If the current basic block has the same exit count as the whole loop, and |
1356 | // it consists of multiple icmp's, try to collect all icmp's that give exact |
1357 | // same exit count. For all other icmp's, we could use one less iteration, |
1358 | // because their value on the last iteration doesn't really matter. |
1359 | SmallPtrSet<ICmpInst *, 4> ICmpsFailingOnLastIter; |
1360 | if (!SkipLastIter && LeafConditions.size() > 1 && |
1361 | SE->getExitCount(L, ExitingBlock: ExitingBB, |
1362 | Kind: ScalarEvolution::ExitCountKind::SymbolicMaximum) == |
1363 | MaxIter) |
1364 | for (auto *ICmp : LeafConditions) { |
1365 | auto EL = SE->computeExitLimitFromCond(L, ExitCond: ICmp, ExitIfTrue: Inverted, |
1366 | /*ControlsExit*/ ControlsOnlyExit: false); |
1367 | auto *ExitMax = EL.SymbolicMaxNotTaken; |
1368 | if (isa<SCEVCouldNotCompute>(Val: ExitMax)) |
1369 | continue; |
1370 | // They could be of different types (specifically this happens after |
1371 | // IV widening). |
1372 | auto *WiderType = |
1373 | SE->getWiderType(Ty1: ExitMax->getType(), Ty2: MaxIter->getType()); |
1374 | auto *WideExitMax = SE->getNoopOrZeroExtend(V: ExitMax, Ty: WiderType); |
1375 | auto *WideMaxIter = SE->getNoopOrZeroExtend(V: MaxIter, Ty: WiderType); |
1376 | if (WideExitMax == WideMaxIter) |
1377 | ICmpsFailingOnLastIter.insert(Ptr: ICmp); |
1378 | } |
1379 | |
1380 | bool Changed = false; |
1381 | for (auto *OldCond : LeafConditions) { |
1382 | // Skip last iteration for this icmp under one of two conditions: |
1383 | // - We do it for all conditions; |
1384 | // - There is another ICmp that would fail on last iter, so this one doesn't |
1385 | // really matter. |
1386 | bool OptimisticSkipLastIter = SkipLastIter; |
1387 | if (!OptimisticSkipLastIter) { |
1388 | if (ICmpsFailingOnLastIter.size() > 1) |
1389 | OptimisticSkipLastIter = true; |
1390 | else if (ICmpsFailingOnLastIter.size() == 1) |
1391 | OptimisticSkipLastIter = !ICmpsFailingOnLastIter.count(Ptr: OldCond); |
1392 | } |
1393 | if (auto Replaced = |
1394 | createReplacement(ICmp: OldCond, L, ExitingBB, MaxIter, Inverted, |
1395 | SkipLastIter: OptimisticSkipLastIter, SE, Rewriter)) { |
1396 | Changed = true; |
1397 | auto *NewCond = *Replaced; |
1398 | if (auto *NCI = dyn_cast<Instruction>(Val: NewCond)) { |
1399 | NCI->setName(OldCond->getName() + ".first_iter" ); |
1400 | } |
1401 | LLVM_DEBUG(dbgs() << "Unknown exit count: Replacing " << *OldCond |
1402 | << " with " << *NewCond << "\n" ); |
1403 | assert(OldCond->hasOneUse() && "Must be!" ); |
1404 | OldCond->replaceAllUsesWith(V: NewCond); |
1405 | DeadInsts.push_back(Elt: OldCond); |
1406 | // Make sure we no longer consider this condition as failing on last |
1407 | // iteration. |
1408 | ICmpsFailingOnLastIter.erase(Ptr: OldCond); |
1409 | } |
1410 | } |
1411 | return Changed; |
1412 | } |
1413 | |
1414 | bool IndVarSimplify::canonicalizeExitCondition(Loop *L) { |
1415 | // Note: This is duplicating a particular part on SimplifyIndVars reasoning. |
1416 | // We need to duplicate it because given icmp zext(small-iv), C, IVUsers |
1417 | // never reaches the icmp since the zext doesn't fold to an AddRec unless |
1418 | // it already has flags. The alternative to this would be to extending the |
1419 | // set of "interesting" IV users to include the icmp, but doing that |
1420 | // regresses results in practice by querying SCEVs before trip counts which |
1421 | // rely on them which results in SCEV caching sub-optimal answers. The |
1422 | // concern about caching sub-optimal results is why we only query SCEVs of |
1423 | // the loop invariant RHS here. |
1424 | SmallVector<BasicBlock*, 16> ExitingBlocks; |
1425 | L->getExitingBlocks(ExitingBlocks); |
1426 | bool Changed = false; |
1427 | for (auto *ExitingBB : ExitingBlocks) { |
1428 | auto *BI = dyn_cast<BranchInst>(Val: ExitingBB->getTerminator()); |
1429 | if (!BI) |
1430 | continue; |
1431 | assert(BI->isConditional() && "exit branch must be conditional" ); |
1432 | |
1433 | auto *ICmp = dyn_cast<ICmpInst>(Val: BI->getCondition()); |
1434 | if (!ICmp || !ICmp->hasOneUse()) |
1435 | continue; |
1436 | |
1437 | auto *LHS = ICmp->getOperand(i_nocapture: 0); |
1438 | auto *RHS = ICmp->getOperand(i_nocapture: 1); |
1439 | // For the range reasoning, avoid computing SCEVs in the loop to avoid |
1440 | // poisoning cache with sub-optimal results. For the must-execute case, |
1441 | // this is a neccessary precondition for correctness. |
1442 | if (!L->isLoopInvariant(V: RHS)) { |
1443 | if (!L->isLoopInvariant(V: LHS)) |
1444 | continue; |
1445 | // Same logic applies for the inverse case |
1446 | std::swap(a&: LHS, b&: RHS); |
1447 | } |
1448 | |
1449 | // Match (icmp signed-cond zext, RHS) |
1450 | Value *LHSOp = nullptr; |
1451 | if (!match(V: LHS, P: m_ZExt(Op: m_Value(V&: LHSOp))) || !ICmp->isSigned()) |
1452 | continue; |
1453 | |
1454 | const DataLayout &DL = ExitingBB->getModule()->getDataLayout(); |
1455 | const unsigned InnerBitWidth = DL.getTypeSizeInBits(Ty: LHSOp->getType()); |
1456 | const unsigned OuterBitWidth = DL.getTypeSizeInBits(Ty: RHS->getType()); |
1457 | auto FullCR = ConstantRange::getFull(BitWidth: InnerBitWidth); |
1458 | FullCR = FullCR.zeroExtend(BitWidth: OuterBitWidth); |
1459 | auto RHSCR = SE->getUnsignedRange(S: SE->applyLoopGuards(Expr: SE->getSCEV(V: RHS), L)); |
1460 | if (FullCR.contains(CR: RHSCR)) { |
1461 | // We have now matched icmp signed-cond zext(X), zext(Y'), and can thus |
1462 | // replace the signed condition with the unsigned version. |
1463 | ICmp->setPredicate(ICmp->getUnsignedPredicate()); |
1464 | Changed = true; |
1465 | // Note: No SCEV invalidation needed. We've changed the predicate, but |
1466 | // have not changed exit counts, or the values produced by the compare. |
1467 | continue; |
1468 | } |
1469 | } |
1470 | |
1471 | // Now that we've canonicalized the condition to match the extend, |
1472 | // see if we can rotate the extend out of the loop. |
1473 | for (auto *ExitingBB : ExitingBlocks) { |
1474 | auto *BI = dyn_cast<BranchInst>(Val: ExitingBB->getTerminator()); |
1475 | if (!BI) |
1476 | continue; |
1477 | assert(BI->isConditional() && "exit branch must be conditional" ); |
1478 | |
1479 | auto *ICmp = dyn_cast<ICmpInst>(Val: BI->getCondition()); |
1480 | if (!ICmp || !ICmp->hasOneUse() || !ICmp->isUnsigned()) |
1481 | continue; |
1482 | |
1483 | bool Swapped = false; |
1484 | auto *LHS = ICmp->getOperand(i_nocapture: 0); |
1485 | auto *RHS = ICmp->getOperand(i_nocapture: 1); |
1486 | if (L->isLoopInvariant(V: LHS) == L->isLoopInvariant(V: RHS)) |
1487 | // Nothing to rotate |
1488 | continue; |
1489 | if (L->isLoopInvariant(V: LHS)) { |
1490 | // Same logic applies for the inverse case until we actually pick |
1491 | // which operand of the compare to update. |
1492 | Swapped = true; |
1493 | std::swap(a&: LHS, b&: RHS); |
1494 | } |
1495 | assert(!L->isLoopInvariant(LHS) && L->isLoopInvariant(RHS)); |
1496 | |
1497 | // Match (icmp unsigned-cond zext, RHS) |
1498 | // TODO: Extend to handle corresponding sext/signed-cmp case |
1499 | // TODO: Extend to other invertible functions |
1500 | Value *LHSOp = nullptr; |
1501 | if (!match(V: LHS, P: m_ZExt(Op: m_Value(V&: LHSOp)))) |
1502 | continue; |
1503 | |
1504 | // In general, we only rotate if we can do so without increasing the number |
1505 | // of instructions. The exception is when we have an zext(add-rec). The |
1506 | // reason for allowing this exception is that we know we need to get rid |
1507 | // of the zext for SCEV to be able to compute a trip count for said loops; |
1508 | // we consider the new trip count valuable enough to increase instruction |
1509 | // count by one. |
1510 | if (!LHS->hasOneUse() && !isa<SCEVAddRecExpr>(Val: SE->getSCEV(V: LHSOp))) |
1511 | continue; |
1512 | |
1513 | // Given a icmp unsigned-cond zext(Op) where zext(trunc(RHS)) == RHS |
1514 | // replace with an icmp of the form icmp unsigned-cond Op, trunc(RHS) |
1515 | // when zext is loop varying and RHS is loop invariant. This converts |
1516 | // loop varying work to loop-invariant work. |
1517 | auto doRotateTransform = [&]() { |
1518 | assert(ICmp->isUnsigned() && "must have proven unsigned already" ); |
1519 | auto *NewRHS = |
1520 | CastInst::Create(Instruction::Trunc, S: RHS, Ty: LHSOp->getType(), Name: "" , |
1521 | InsertBefore: L->getLoopPreheader()->getTerminator()); |
1522 | ICmp->setOperand(i_nocapture: Swapped ? 1 : 0, Val_nocapture: LHSOp); |
1523 | ICmp->setOperand(i_nocapture: Swapped ? 0 : 1, Val_nocapture: NewRHS); |
1524 | if (LHS->use_empty()) |
1525 | DeadInsts.push_back(Elt: LHS); |
1526 | }; |
1527 | |
1528 | |
1529 | const DataLayout &DL = ExitingBB->getModule()->getDataLayout(); |
1530 | const unsigned InnerBitWidth = DL.getTypeSizeInBits(Ty: LHSOp->getType()); |
1531 | const unsigned OuterBitWidth = DL.getTypeSizeInBits(Ty: RHS->getType()); |
1532 | auto FullCR = ConstantRange::getFull(BitWidth: InnerBitWidth); |
1533 | FullCR = FullCR.zeroExtend(BitWidth: OuterBitWidth); |
1534 | auto RHSCR = SE->getUnsignedRange(S: SE->applyLoopGuards(Expr: SE->getSCEV(V: RHS), L)); |
1535 | if (FullCR.contains(CR: RHSCR)) { |
1536 | doRotateTransform(); |
1537 | Changed = true; |
1538 | // Note, we are leaving SCEV in an unfortunately imprecise case here |
1539 | // as rotation tends to reveal information about trip counts not |
1540 | // previously visible. |
1541 | continue; |
1542 | } |
1543 | } |
1544 | |
1545 | return Changed; |
1546 | } |
1547 | |
1548 | bool IndVarSimplify::optimizeLoopExits(Loop *L, SCEVExpander &Rewriter) { |
1549 | SmallVector<BasicBlock*, 16> ExitingBlocks; |
1550 | L->getExitingBlocks(ExitingBlocks); |
1551 | |
1552 | // Remove all exits which aren't both rewriteable and execute on every |
1553 | // iteration. |
1554 | llvm::erase_if(C&: ExitingBlocks, P: [&](BasicBlock *ExitingBB) { |
1555 | // If our exitting block exits multiple loops, we can only rewrite the |
1556 | // innermost one. Otherwise, we're changing how many times the innermost |
1557 | // loop runs before it exits. |
1558 | if (LI->getLoopFor(BB: ExitingBB) != L) |
1559 | return true; |
1560 | |
1561 | // Can't rewrite non-branch yet. |
1562 | BranchInst *BI = dyn_cast<BranchInst>(Val: ExitingBB->getTerminator()); |
1563 | if (!BI) |
1564 | return true; |
1565 | |
1566 | // Likewise, the loop latch must be dominated by the exiting BB. |
1567 | if (!DT->dominates(A: ExitingBB, B: L->getLoopLatch())) |
1568 | return true; |
1569 | |
1570 | if (auto *CI = dyn_cast<ConstantInt>(Val: BI->getCondition())) { |
1571 | // If already constant, nothing to do. However, if this is an |
1572 | // unconditional exit, we can still replace header phis with their |
1573 | // preheader value. |
1574 | if (!L->contains(BB: BI->getSuccessor(i: CI->isNullValue()))) |
1575 | replaceLoopPHINodesWithPreheaderValues(LI, L, DeadInsts, SE&: *SE); |
1576 | return true; |
1577 | } |
1578 | |
1579 | return false; |
1580 | }); |
1581 | |
1582 | if (ExitingBlocks.empty()) |
1583 | return false; |
1584 | |
1585 | // Get a symbolic upper bound on the loop backedge taken count. |
1586 | const SCEV *MaxBECount = SE->getSymbolicMaxBackedgeTakenCount(L); |
1587 | if (isa<SCEVCouldNotCompute>(Val: MaxBECount)) |
1588 | return false; |
1589 | |
1590 | // Visit our exit blocks in order of dominance. We know from the fact that |
1591 | // all exits must dominate the latch, so there is a total dominance order |
1592 | // between them. |
1593 | llvm::sort(C&: ExitingBlocks, Comp: [&](BasicBlock *A, BasicBlock *B) { |
1594 | // std::sort sorts in ascending order, so we want the inverse of |
1595 | // the normal dominance relation. |
1596 | if (A == B) return false; |
1597 | if (DT->properlyDominates(A, B)) |
1598 | return true; |
1599 | else { |
1600 | assert(DT->properlyDominates(B, A) && |
1601 | "expected total dominance order!" ); |
1602 | return false; |
1603 | } |
1604 | }); |
1605 | #ifdef ASSERT |
1606 | for (unsigned i = 1; i < ExitingBlocks.size(); i++) { |
1607 | assert(DT->dominates(ExitingBlocks[i-1], ExitingBlocks[i])); |
1608 | } |
1609 | #endif |
1610 | |
1611 | bool Changed = false; |
1612 | bool SkipLastIter = false; |
1613 | const SCEV *CurrMaxExit = SE->getCouldNotCompute(); |
1614 | auto UpdateSkipLastIter = [&](const SCEV *MaxExitCount) { |
1615 | if (SkipLastIter || isa<SCEVCouldNotCompute>(Val: MaxExitCount)) |
1616 | return; |
1617 | if (isa<SCEVCouldNotCompute>(Val: CurrMaxExit)) |
1618 | CurrMaxExit = MaxExitCount; |
1619 | else |
1620 | CurrMaxExit = SE->getUMinFromMismatchedTypes(LHS: CurrMaxExit, RHS: MaxExitCount); |
1621 | // If the loop has more than 1 iteration, all further checks will be |
1622 | // executed 1 iteration less. |
1623 | if (CurrMaxExit == MaxBECount) |
1624 | SkipLastIter = true; |
1625 | }; |
1626 | SmallSet<const SCEV *, 8> DominatingExactExitCounts; |
1627 | for (BasicBlock *ExitingBB : ExitingBlocks) { |
1628 | const SCEV *ExactExitCount = SE->getExitCount(L, ExitingBlock: ExitingBB); |
1629 | const SCEV *MaxExitCount = SE->getExitCount( |
1630 | L, ExitingBlock: ExitingBB, Kind: ScalarEvolution::ExitCountKind::SymbolicMaximum); |
1631 | if (isa<SCEVCouldNotCompute>(Val: ExactExitCount)) { |
1632 | // Okay, we do not know the exit count here. Can we at least prove that it |
1633 | // will remain the same within iteration space? |
1634 | auto *BI = cast<BranchInst>(Val: ExitingBB->getTerminator()); |
1635 | auto OptimizeCond = [&](bool SkipLastIter) { |
1636 | return optimizeLoopExitWithUnknownExitCount(L, BI, ExitingBB, |
1637 | MaxIter: MaxBECount, SkipLastIter, |
1638 | SE, Rewriter, DeadInsts); |
1639 | }; |
1640 | |
1641 | // TODO: We might have proved that we can skip the last iteration for |
1642 | // this check. In this case, we only want to check the condition on the |
1643 | // pre-last iteration (MaxBECount - 1). However, there is a nasty |
1644 | // corner case: |
1645 | // |
1646 | // for (i = len; i != 0; i--) { ... check (i ult X) ... } |
1647 | // |
1648 | // If we could not prove that len != 0, then we also could not prove that |
1649 | // (len - 1) is not a UINT_MAX. If we simply query (len - 1), then |
1650 | // OptimizeCond will likely not prove anything for it, even if it could |
1651 | // prove the same fact for len. |
1652 | // |
1653 | // As a temporary solution, we query both last and pre-last iterations in |
1654 | // hope that we will be able to prove triviality for at least one of |
1655 | // them. We can stop querying MaxBECount for this case once SCEV |
1656 | // understands that (MaxBECount - 1) will not overflow here. |
1657 | if (OptimizeCond(false)) |
1658 | Changed = true; |
1659 | else if (SkipLastIter && OptimizeCond(true)) |
1660 | Changed = true; |
1661 | UpdateSkipLastIter(MaxExitCount); |
1662 | continue; |
1663 | } |
1664 | |
1665 | UpdateSkipLastIter(ExactExitCount); |
1666 | |
1667 | // If we know we'd exit on the first iteration, rewrite the exit to |
1668 | // reflect this. This does not imply the loop must exit through this |
1669 | // exit; there may be an earlier one taken on the first iteration. |
1670 | // We know that the backedge can't be taken, so we replace all |
1671 | // the header PHIs with values coming from the preheader. |
1672 | if (ExactExitCount->isZero()) { |
1673 | foldExit(L, ExitingBB, IsTaken: true, DeadInsts); |
1674 | replaceLoopPHINodesWithPreheaderValues(LI, L, DeadInsts, SE&: *SE); |
1675 | Changed = true; |
1676 | continue; |
1677 | } |
1678 | |
1679 | assert(ExactExitCount->getType()->isIntegerTy() && |
1680 | MaxBECount->getType()->isIntegerTy() && |
1681 | "Exit counts must be integers" ); |
1682 | |
1683 | Type *WiderType = |
1684 | SE->getWiderType(Ty1: MaxBECount->getType(), Ty2: ExactExitCount->getType()); |
1685 | ExactExitCount = SE->getNoopOrZeroExtend(V: ExactExitCount, Ty: WiderType); |
1686 | MaxBECount = SE->getNoopOrZeroExtend(V: MaxBECount, Ty: WiderType); |
1687 | assert(MaxBECount->getType() == ExactExitCount->getType()); |
1688 | |
1689 | // Can we prove that some other exit must be taken strictly before this |
1690 | // one? |
1691 | if (SE->isLoopEntryGuardedByCond(L, Pred: CmpInst::ICMP_ULT, LHS: MaxBECount, |
1692 | RHS: ExactExitCount)) { |
1693 | foldExit(L, ExitingBB, IsTaken: false, DeadInsts); |
1694 | Changed = true; |
1695 | continue; |
1696 | } |
1697 | |
1698 | // As we run, keep track of which exit counts we've encountered. If we |
1699 | // find a duplicate, we've found an exit which would have exited on the |
1700 | // exiting iteration, but (from the visit order) strictly follows another |
1701 | // which does the same and is thus dead. |
1702 | if (!DominatingExactExitCounts.insert(Ptr: ExactExitCount).second) { |
1703 | foldExit(L, ExitingBB, IsTaken: false, DeadInsts); |
1704 | Changed = true; |
1705 | continue; |
1706 | } |
1707 | |
1708 | // TODO: There might be another oppurtunity to leverage SCEV's reasoning |
1709 | // here. If we kept track of the min of dominanting exits so far, we could |
1710 | // discharge exits with EC >= MDEC. This is less powerful than the existing |
1711 | // transform (since later exits aren't considered), but potentially more |
1712 | // powerful for any case where SCEV can prove a >=u b, but neither a == b |
1713 | // or a >u b. Such a case is not currently known. |
1714 | } |
1715 | return Changed; |
1716 | } |
1717 | |
1718 | bool IndVarSimplify::predicateLoopExits(Loop *L, SCEVExpander &Rewriter) { |
1719 | SmallVector<BasicBlock*, 16> ExitingBlocks; |
1720 | L->getExitingBlocks(ExitingBlocks); |
1721 | |
1722 | // Finally, see if we can rewrite our exit conditions into a loop invariant |
1723 | // form. If we have a read-only loop, and we can tell that we must exit down |
1724 | // a path which does not need any of the values computed within the loop, we |
1725 | // can rewrite the loop to exit on the first iteration. Note that this |
1726 | // doesn't either a) tell us the loop exits on the first iteration (unless |
1727 | // *all* exits are predicateable) or b) tell us *which* exit might be taken. |
1728 | // This transformation looks a lot like a restricted form of dead loop |
1729 | // elimination, but restricted to read-only loops and without neccesssarily |
1730 | // needing to kill the loop entirely. |
1731 | if (!LoopPredication) |
1732 | return false; |
1733 | |
1734 | // Note: ExactBTC is the exact backedge taken count *iff* the loop exits |
1735 | // through *explicit* control flow. We have to eliminate the possibility of |
1736 | // implicit exits (see below) before we know it's truly exact. |
1737 | const SCEV *ExactBTC = SE->getBackedgeTakenCount(L); |
1738 | if (isa<SCEVCouldNotCompute>(Val: ExactBTC) || !Rewriter.isSafeToExpand(S: ExactBTC)) |
1739 | return false; |
1740 | |
1741 | assert(SE->isLoopInvariant(ExactBTC, L) && "BTC must be loop invariant" ); |
1742 | assert(ExactBTC->getType()->isIntegerTy() && "BTC must be integer" ); |
1743 | |
1744 | auto BadExit = [&](BasicBlock *ExitingBB) { |
1745 | // If our exiting block exits multiple loops, we can only rewrite the |
1746 | // innermost one. Otherwise, we're changing how many times the innermost |
1747 | // loop runs before it exits. |
1748 | if (LI->getLoopFor(BB: ExitingBB) != L) |
1749 | return true; |
1750 | |
1751 | // Can't rewrite non-branch yet. |
1752 | BranchInst *BI = dyn_cast<BranchInst>(Val: ExitingBB->getTerminator()); |
1753 | if (!BI) |
1754 | return true; |
1755 | |
1756 | // If already constant, nothing to do. |
1757 | if (isa<Constant>(Val: BI->getCondition())) |
1758 | return true; |
1759 | |
1760 | // If the exit block has phis, we need to be able to compute the values |
1761 | // within the loop which contains them. This assumes trivially lcssa phis |
1762 | // have already been removed; TODO: generalize |
1763 | BasicBlock *ExitBlock = |
1764 | BI->getSuccessor(i: L->contains(BB: BI->getSuccessor(i: 0)) ? 1 : 0); |
1765 | if (!ExitBlock->phis().empty()) |
1766 | return true; |
1767 | |
1768 | const SCEV *ExitCount = SE->getExitCount(L, ExitingBlock: ExitingBB); |
1769 | if (isa<SCEVCouldNotCompute>(Val: ExitCount) || |
1770 | !Rewriter.isSafeToExpand(S: ExitCount)) |
1771 | return true; |
1772 | |
1773 | assert(SE->isLoopInvariant(ExitCount, L) && |
1774 | "Exit count must be loop invariant" ); |
1775 | assert(ExitCount->getType()->isIntegerTy() && "Exit count must be integer" ); |
1776 | return false; |
1777 | }; |
1778 | |
1779 | // If we have any exits which can't be predicated themselves, than we can't |
1780 | // predicate any exit which isn't guaranteed to execute before it. Consider |
1781 | // two exits (a) and (b) which would both exit on the same iteration. If we |
1782 | // can predicate (b), but not (a), and (a) preceeds (b) along some path, then |
1783 | // we could convert a loop from exiting through (a) to one exiting through |
1784 | // (b). Note that this problem exists only for exits with the same exit |
1785 | // count, and we could be more aggressive when exit counts are known inequal. |
1786 | llvm::sort(C&: ExitingBlocks, |
1787 | Comp: [&](BasicBlock *A, BasicBlock *B) { |
1788 | // std::sort sorts in ascending order, so we want the inverse of |
1789 | // the normal dominance relation, plus a tie breaker for blocks |
1790 | // unordered by dominance. |
1791 | if (DT->properlyDominates(A, B)) return true; |
1792 | if (DT->properlyDominates(A: B, B: A)) return false; |
1793 | return A->getName() < B->getName(); |
1794 | }); |
1795 | // Check to see if our exit blocks are a total order (i.e. a linear chain of |
1796 | // exits before the backedge). If they aren't, reasoning about reachability |
1797 | // is complicated and we choose not to for now. |
1798 | for (unsigned i = 1; i < ExitingBlocks.size(); i++) |
1799 | if (!DT->dominates(A: ExitingBlocks[i-1], B: ExitingBlocks[i])) |
1800 | return false; |
1801 | |
1802 | // Given our sorted total order, we know that exit[j] must be evaluated |
1803 | // after all exit[i] such j > i. |
1804 | for (unsigned i = 0, e = ExitingBlocks.size(); i < e; i++) |
1805 | if (BadExit(ExitingBlocks[i])) { |
1806 | ExitingBlocks.resize(N: i); |
1807 | break; |
1808 | } |
1809 | |
1810 | if (ExitingBlocks.empty()) |
1811 | return false; |
1812 | |
1813 | // We rely on not being able to reach an exiting block on a later iteration |
1814 | // then it's statically compute exit count. The implementaton of |
1815 | // getExitCount currently has this invariant, but assert it here so that |
1816 | // breakage is obvious if this ever changes.. |
1817 | assert(llvm::all_of(ExitingBlocks, [&](BasicBlock *ExitingBB) { |
1818 | return DT->dominates(ExitingBB, L->getLoopLatch()); |
1819 | })); |
1820 | |
1821 | // At this point, ExitingBlocks consists of only those blocks which are |
1822 | // predicatable. Given that, we know we have at least one exit we can |
1823 | // predicate if the loop is doesn't have side effects and doesn't have any |
1824 | // implicit exits (because then our exact BTC isn't actually exact). |
1825 | // @Reviewers - As structured, this is O(I^2) for loop nests. Any |
1826 | // suggestions on how to improve this? I can obviously bail out for outer |
1827 | // loops, but that seems less than ideal. MemorySSA can find memory writes, |
1828 | // is that enough for *all* side effects? |
1829 | for (BasicBlock *BB : L->blocks()) |
1830 | for (auto &I : *BB) |
1831 | // TODO:isGuaranteedToTransfer |
1832 | if (I.mayHaveSideEffects()) |
1833 | return false; |
1834 | |
1835 | bool Changed = false; |
1836 | // Finally, do the actual predication for all predicatable blocks. A couple |
1837 | // of notes here: |
1838 | // 1) We don't bother to constant fold dominated exits with identical exit |
1839 | // counts; that's simply a form of CSE/equality propagation and we leave |
1840 | // it for dedicated passes. |
1841 | // 2) We insert the comparison at the branch. Hoisting introduces additional |
1842 | // legality constraints and we leave that to dedicated logic. We want to |
1843 | // predicate even if we can't insert a loop invariant expression as |
1844 | // peeling or unrolling will likely reduce the cost of the otherwise loop |
1845 | // varying check. |
1846 | Rewriter.setInsertPoint(L->getLoopPreheader()->getTerminator()); |
1847 | IRBuilder<> B(L->getLoopPreheader()->getTerminator()); |
1848 | Value *ExactBTCV = nullptr; // Lazily generated if needed. |
1849 | for (BasicBlock *ExitingBB : ExitingBlocks) { |
1850 | const SCEV *ExitCount = SE->getExitCount(L, ExitingBlock: ExitingBB); |
1851 | |
1852 | auto *BI = cast<BranchInst>(Val: ExitingBB->getTerminator()); |
1853 | Value *NewCond; |
1854 | if (ExitCount == ExactBTC) { |
1855 | NewCond = L->contains(BB: BI->getSuccessor(i: 0)) ? |
1856 | B.getFalse() : B.getTrue(); |
1857 | } else { |
1858 | Value *ECV = Rewriter.expandCodeFor(SH: ExitCount); |
1859 | if (!ExactBTCV) |
1860 | ExactBTCV = Rewriter.expandCodeFor(SH: ExactBTC); |
1861 | Value *RHS = ExactBTCV; |
1862 | if (ECV->getType() != RHS->getType()) { |
1863 | Type *WiderTy = SE->getWiderType(Ty1: ECV->getType(), Ty2: RHS->getType()); |
1864 | ECV = B.CreateZExt(V: ECV, DestTy: WiderTy); |
1865 | RHS = B.CreateZExt(V: RHS, DestTy: WiderTy); |
1866 | } |
1867 | auto Pred = L->contains(BB: BI->getSuccessor(i: 0)) ? |
1868 | ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ; |
1869 | NewCond = B.CreateICmp(P: Pred, LHS: ECV, RHS); |
1870 | } |
1871 | Value *OldCond = BI->getCondition(); |
1872 | BI->setCondition(NewCond); |
1873 | if (OldCond->use_empty()) |
1874 | DeadInsts.emplace_back(Args&: OldCond); |
1875 | Changed = true; |
1876 | } |
1877 | |
1878 | return Changed; |
1879 | } |
1880 | |
1881 | //===----------------------------------------------------------------------===// |
1882 | // IndVarSimplify driver. Manage several subpasses of IV simplification. |
1883 | //===----------------------------------------------------------------------===// |
1884 | |
1885 | bool IndVarSimplify::run(Loop *L) { |
1886 | // We need (and expect!) the incoming loop to be in LCSSA. |
1887 | assert(L->isRecursivelyLCSSAForm(*DT, *LI) && |
1888 | "LCSSA required to run indvars!" ); |
1889 | |
1890 | // If LoopSimplify form is not available, stay out of trouble. Some notes: |
1891 | // - LSR currently only supports LoopSimplify-form loops. Indvars' |
1892 | // canonicalization can be a pessimization without LSR to "clean up" |
1893 | // afterwards. |
1894 | // - We depend on having a preheader; in particular, |
1895 | // Loop::getCanonicalInductionVariable only supports loops with preheaders, |
1896 | // and we're in trouble if we can't find the induction variable even when |
1897 | // we've manually inserted one. |
1898 | // - LFTR relies on having a single backedge. |
1899 | if (!L->isLoopSimplifyForm()) |
1900 | return false; |
1901 | |
1902 | bool Changed = false; |
1903 | // If there are any floating-point recurrences, attempt to |
1904 | // transform them to use integer recurrences. |
1905 | Changed |= rewriteNonIntegerIVs(L); |
1906 | |
1907 | // Create a rewriter object which we'll use to transform the code with. |
1908 | SCEVExpander Rewriter(*SE, DL, "indvars" ); |
1909 | #ifndef NDEBUG |
1910 | Rewriter.setDebugType(DEBUG_TYPE); |
1911 | #endif |
1912 | |
1913 | // Eliminate redundant IV users. |
1914 | // |
1915 | // Simplification works best when run before other consumers of SCEV. We |
1916 | // attempt to avoid evaluating SCEVs for sign/zero extend operations until |
1917 | // other expressions involving loop IVs have been evaluated. This helps SCEV |
1918 | // set no-wrap flags before normalizing sign/zero extension. |
1919 | Rewriter.disableCanonicalMode(); |
1920 | Changed |= simplifyAndExtend(L, Rewriter, LI); |
1921 | |
1922 | // Check to see if we can compute the final value of any expressions |
1923 | // that are recurrent in the loop, and substitute the exit values from the |
1924 | // loop into any instructions outside of the loop that use the final values |
1925 | // of the current expressions. |
1926 | if (ReplaceExitValue != NeverRepl) { |
1927 | if (int Rewrites = rewriteLoopExitValues(L, LI, TLI, SE, TTI, Rewriter, DT, |
1928 | ReplaceExitValue, DeadInsts)) { |
1929 | NumReplaced += Rewrites; |
1930 | Changed = true; |
1931 | } |
1932 | } |
1933 | |
1934 | // Eliminate redundant IV cycles. |
1935 | NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts, TTI); |
1936 | |
1937 | // Try to convert exit conditions to unsigned and rotate computation |
1938 | // out of the loop. Note: Handles invalidation internally if needed. |
1939 | Changed |= canonicalizeExitCondition(L); |
1940 | |
1941 | // Try to eliminate loop exits based on analyzeable exit counts |
1942 | if (optimizeLoopExits(L, Rewriter)) { |
1943 | Changed = true; |
1944 | // Given we've changed exit counts, notify SCEV |
1945 | // Some nested loops may share same folded exit basic block, |
1946 | // thus we need to notify top most loop. |
1947 | SE->forgetTopmostLoop(L); |
1948 | } |
1949 | |
1950 | // Try to form loop invariant tests for loop exits by changing how many |
1951 | // iterations of the loop run when that is unobservable. |
1952 | if (predicateLoopExits(L, Rewriter)) { |
1953 | Changed = true; |
1954 | // Given we've changed exit counts, notify SCEV |
1955 | SE->forgetLoop(L); |
1956 | } |
1957 | |
1958 | // If we have a trip count expression, rewrite the loop's exit condition |
1959 | // using it. |
1960 | if (!DisableLFTR) { |
1961 | BasicBlock * = L->getLoopPreheader(); |
1962 | |
1963 | SmallVector<BasicBlock*, 16> ExitingBlocks; |
1964 | L->getExitingBlocks(ExitingBlocks); |
1965 | for (BasicBlock *ExitingBB : ExitingBlocks) { |
1966 | // Can't rewrite non-branch yet. |
1967 | if (!isa<BranchInst>(Val: ExitingBB->getTerminator())) |
1968 | continue; |
1969 | |
1970 | // If our exitting block exits multiple loops, we can only rewrite the |
1971 | // innermost one. Otherwise, we're changing how many times the innermost |
1972 | // loop runs before it exits. |
1973 | if (LI->getLoopFor(BB: ExitingBB) != L) |
1974 | continue; |
1975 | |
1976 | if (!needsLFTR(L, ExitingBB)) |
1977 | continue; |
1978 | |
1979 | const SCEV *ExitCount = SE->getExitCount(L, ExitingBlock: ExitingBB); |
1980 | if (isa<SCEVCouldNotCompute>(Val: ExitCount)) |
1981 | continue; |
1982 | |
1983 | // This was handled above, but as we form SCEVs, we can sometimes refine |
1984 | // existing ones; this allows exit counts to be folded to zero which |
1985 | // weren't when optimizeLoopExits saw them. Arguably, we should iterate |
1986 | // until stable to handle cases like this better. |
1987 | if (ExitCount->isZero()) |
1988 | continue; |
1989 | |
1990 | PHINode *IndVar = FindLoopCounter(L, ExitingBB, BECount: ExitCount, SE, DT); |
1991 | if (!IndVar) |
1992 | continue; |
1993 | |
1994 | // Avoid high cost expansions. Note: This heuristic is questionable in |
1995 | // that our definition of "high cost" is not exactly principled. |
1996 | if (Rewriter.isHighCostExpansion(Exprs: ExitCount, L, Budget: SCEVCheapExpansionBudget, |
1997 | TTI, At: PreHeader->getTerminator())) |
1998 | continue; |
1999 | |
2000 | if (!Rewriter.isSafeToExpand(S: ExitCount)) |
2001 | continue; |
2002 | |
2003 | Changed |= linearFunctionTestReplace(L, ExitingBB, |
2004 | ExitCount, IndVar, |
2005 | Rewriter); |
2006 | } |
2007 | } |
2008 | // Clear the rewriter cache, because values that are in the rewriter's cache |
2009 | // can be deleted in the loop below, causing the AssertingVH in the cache to |
2010 | // trigger. |
2011 | Rewriter.clear(); |
2012 | |
2013 | // Now that we're done iterating through lists, clean up any instructions |
2014 | // which are now dead. |
2015 | while (!DeadInsts.empty()) { |
2016 | Value *V = DeadInsts.pop_back_val(); |
2017 | |
2018 | if (PHINode *PHI = dyn_cast_or_null<PHINode>(Val: V)) |
2019 | Changed |= RecursivelyDeleteDeadPHINode(PN: PHI, TLI, MSSAU: MSSAU.get()); |
2020 | else if (Instruction *Inst = dyn_cast_or_null<Instruction>(Val: V)) |
2021 | Changed |= |
2022 | RecursivelyDeleteTriviallyDeadInstructions(V: Inst, TLI, MSSAU: MSSAU.get()); |
2023 | } |
2024 | |
2025 | // The Rewriter may not be used from this point on. |
2026 | |
2027 | // Loop-invariant instructions in the preheader that aren't used in the |
2028 | // loop may be sunk below the loop to reduce register pressure. |
2029 | Changed |= sinkUnusedInvariants(L); |
2030 | |
2031 | // rewriteFirstIterationLoopExitValues does not rely on the computation of |
2032 | // trip count and therefore can further simplify exit values in addition to |
2033 | // rewriteLoopExitValues. |
2034 | Changed |= rewriteFirstIterationLoopExitValues(L); |
2035 | |
2036 | // Clean up dead instructions. |
2037 | Changed |= DeleteDeadPHIs(BB: L->getHeader(), TLI, MSSAU: MSSAU.get()); |
2038 | |
2039 | // Check a post-condition. |
2040 | assert(L->isRecursivelyLCSSAForm(*DT, *LI) && |
2041 | "Indvars did not preserve LCSSA!" ); |
2042 | if (VerifyMemorySSA && MSSAU) |
2043 | MSSAU->getMemorySSA()->verifyMemorySSA(); |
2044 | |
2045 | return Changed; |
2046 | } |
2047 | |
2048 | PreservedAnalyses IndVarSimplifyPass::run(Loop &L, LoopAnalysisManager &AM, |
2049 | LoopStandardAnalysisResults &AR, |
2050 | LPMUpdater &) { |
2051 | Function *F = L.getHeader()->getParent(); |
2052 | const DataLayout &DL = F->getParent()->getDataLayout(); |
2053 | |
2054 | IndVarSimplify IVS(&AR.LI, &AR.SE, &AR.DT, DL, &AR.TLI, &AR.TTI, AR.MSSA, |
2055 | WidenIndVars && AllowIVWidening); |
2056 | if (!IVS.run(L: &L)) |
2057 | return PreservedAnalyses::all(); |
2058 | |
2059 | auto PA = getLoopPassPreservedAnalyses(); |
2060 | PA.preserveSet<CFGAnalyses>(); |
2061 | if (AR.MSSA) |
2062 | PA.preserve<MemorySSAAnalysis>(); |
2063 | return PA; |
2064 | } |
2065 | |