LLVM  12.0.0git
LoopFlatten.cpp
Go to the documentation of this file.
1 //===- LoopFlatten.cpp - Loop flattening pass------------------------------===//
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 pass flattens pairs nested loops into a single loop.
10 //
11 // The intention is to optimise loop nests like this, which together access an
12 // array linearly:
13 // for (int i = 0; i < N; ++i)
14 // for (int j = 0; j < M; ++j)
15 // f(A[i*M+j]);
16 // into one loop:
17 // for (int i = 0; i < (N*M); ++i)
18 // f(A[i]);
19 //
20 // It can also flatten loops where the induction variables are not used in the
21 // loop. This is only worth doing if the induction variables are only used in an
22 // expression like i*M+j. If they had any other uses, we would have to insert a
23 // div/mod to reconstruct the original values, so this wouldn't be profitable.
24 //
25 // We also need to prove that N*M will not overflow.
26 //
27 //===----------------------------------------------------------------------===//
28 
31 #include "llvm/Analysis/LoopInfo.h"
36 #include "llvm/IR/Dominators.h"
37 #include "llvm/IR/Function.h"
38 #include "llvm/IR/IRBuilder.h"
39 #include "llvm/IR/Module.h"
40 #include "llvm/IR/PatternMatch.h"
41 #include "llvm/IR/Verifier.h"
42 #include "llvm/InitializePasses.h"
43 #include "llvm/Pass.h"
44 #include "llvm/Support/Debug.h"
46 #include "llvm/Transforms/Scalar.h"
51 
52 #define DEBUG_TYPE "loop-flatten"
53 
54 using namespace llvm;
55 using namespace llvm::PatternMatch;
56 
58  "loop-flatten-cost-threshold", cl::Hidden, cl::init(2),
59  cl::desc("Limit on the cost of instructions that can be repeated due to "
60  "loop flattening"));
61 
62 static cl::opt<bool>
63  AssumeNoOverflow("loop-flatten-assume-no-overflow", cl::Hidden,
64  cl::init(false),
65  cl::desc("Assume that the product of the two iteration "
66  "limits will never overflow"));
67 
68 static cl::opt<bool>
69  WidenIV("loop-flatten-widen-iv", cl::Hidden,
70  cl::init(true),
71  cl::desc("Widen the loop induction variables, if possible, so "
72  "overflow checks won't reject flattening"));
73 
74 struct FlattenInfo {
75  Loop *OuterLoop = nullptr;
76  Loop *InnerLoop = nullptr;
77  PHINode *InnerInductionPHI = nullptr;
78  PHINode *OuterInductionPHI = nullptr;
79  Value *InnerLimit = nullptr;
80  Value *OuterLimit = nullptr;
81  BinaryOperator *InnerIncrement = nullptr;
82  BinaryOperator *OuterIncrement = nullptr;
83  BranchInst *InnerBranch = nullptr;
84  BranchInst *OuterBranch = nullptr;
87 
88  // Whether this holds the flatten info before or after widening.
89  bool Widened = false;
90 
91  FlattenInfo(Loop *OL, Loop *IL) : OuterLoop(OL), InnerLoop(IL) {};
92 };
93 
94 // Finds the induction variable, increment and limit for a simple loop that we
95 // can flatten.
96 static bool findLoopComponents(
97  Loop *L, SmallPtrSetImpl<Instruction *> &IterationInstructions,
98  PHINode *&InductionPHI, Value *&Limit, BinaryOperator *&Increment,
99  BranchInst *&BackBranch, ScalarEvolution *SE) {
100  LLVM_DEBUG(dbgs() << "Finding components of loop: " << L->getName() << "\n");
101 
102  if (!L->isLoopSimplifyForm()) {
103  LLVM_DEBUG(dbgs() << "Loop is not in normal form\n");
104  return false;
105  }
106 
107  // There must be exactly one exiting block, and it must be the same at the
108  // latch.
109  BasicBlock *Latch = L->getLoopLatch();
110  if (L->getExitingBlock() != Latch) {
111  LLVM_DEBUG(dbgs() << "Exiting and latch block are different\n");
112  return false;
113  }
114  // Latch block must end in a conditional branch.
115  BackBranch = dyn_cast<BranchInst>(Latch->getTerminator());
116  if (!BackBranch || !BackBranch->isConditional()) {
117  LLVM_DEBUG(dbgs() << "Could not find back-branch\n");
118  return false;
119  }
120  IterationInstructions.insert(BackBranch);
121  LLVM_DEBUG(dbgs() << "Found back branch: "; BackBranch->dump());
122  bool ContinueOnTrue = L->contains(BackBranch->getSuccessor(0));
123 
124  // Find the induction PHI. If there is no induction PHI, we can't do the
125  // transformation. TODO: could other variables trigger this? Do we have to
126  // search for the best one?
127  InductionPHI = nullptr;
128  for (PHINode &PHI : L->getHeader()->phis()) {
130  if (InductionDescriptor::isInductionPHI(&PHI, L, SE, ID)) {
131  InductionPHI = &PHI;
132  LLVM_DEBUG(dbgs() << "Found induction PHI: "; InductionPHI->dump());
133  break;
134  }
135  }
136  if (!InductionPHI) {
137  LLVM_DEBUG(dbgs() << "Could not find induction PHI\n");
138  return false;
139  }
140 
141  auto IsValidPredicate = [&](ICmpInst::Predicate Pred) {
142  if (ContinueOnTrue)
143  return Pred == CmpInst::ICMP_NE || Pred == CmpInst::ICMP_ULT;
144  else
145  return Pred == CmpInst::ICMP_EQ;
146  };
147 
148  // Find Compare and make sure it is valid
149  ICmpInst *Compare = dyn_cast<ICmpInst>(BackBranch->getCondition());
150  if (!Compare || !IsValidPredicate(Compare->getUnsignedPredicate()) ||
151  Compare->hasNUsesOrMore(2)) {
152  LLVM_DEBUG(dbgs() << "Could not find valid comparison\n");
153  return false;
154  }
155  IterationInstructions.insert(Compare);
156  LLVM_DEBUG(dbgs() << "Found comparison: "; Compare->dump());
157 
158  // Find increment and limit from the compare
159  Increment = nullptr;
160  if (match(Compare->getOperand(0),
161  m_c_Add(m_Specific(InductionPHI), m_ConstantInt<1>()))) {
162  Increment = dyn_cast<BinaryOperator>(Compare->getOperand(0));
163  Limit = Compare->getOperand(1);
164  } else if (Compare->getUnsignedPredicate() == CmpInst::ICMP_NE &&
165  match(Compare->getOperand(1),
166  m_c_Add(m_Specific(InductionPHI), m_ConstantInt<1>()))) {
167  Increment = dyn_cast<BinaryOperator>(Compare->getOperand(1));
168  Limit = Compare->getOperand(0);
169  }
170  if (!Increment || Increment->hasNUsesOrMore(3)) {
171  LLVM_DEBUG(dbgs() << "Cound not find valid increment\n");
172  return false;
173  }
174  IterationInstructions.insert(Increment);
175  LLVM_DEBUG(dbgs() << "Found increment: "; Increment->dump());
176  LLVM_DEBUG(dbgs() << "Found limit: "; Limit->dump());
177 
178  assert(InductionPHI->getNumIncomingValues() == 2);
179  assert(InductionPHI->getIncomingValueForBlock(Latch) == Increment &&
180  "PHI value is not increment inst");
181 
182  auto *CI = dyn_cast<ConstantInt>(
183  InductionPHI->getIncomingValueForBlock(L->getLoopPreheader()));
184  if (!CI || !CI->isZero()) {
185  LLVM_DEBUG(dbgs() << "PHI value is not zero: "; CI->dump());
186  return false;
187  }
188 
189  LLVM_DEBUG(dbgs() << "Successfully found all loop components\n");
190  return true;
191 }
192 
193 static bool checkPHIs(struct FlattenInfo &FI,
194  const TargetTransformInfo *TTI) {
195  // All PHIs in the inner and outer headers must either be:
196  // - The induction PHI, which we are going to rewrite as one induction in
197  // the new loop. This is already checked by findLoopComponents.
198  // - An outer header PHI with all incoming values from outside the loop.
199  // LoopSimplify guarantees we have a pre-header, so we don't need to
200  // worry about that here.
201  // - Pairs of PHIs in the inner and outer headers, which implement a
202  // loop-carried dependency that will still be valid in the new loop. To
203  // be valid, this variable must be modified only in the inner loop.
204 
205  // The set of PHI nodes in the outer loop header that we know will still be
206  // valid after the transformation. These will not need to be modified (with
207  // the exception of the induction variable), but we do need to check that
208  // there are no unsafe PHI nodes.
209  SmallPtrSet<PHINode *, 4> SafeOuterPHIs;
210  SafeOuterPHIs.insert(FI.OuterInductionPHI);
211 
212  // Check that all PHI nodes in the inner loop header match one of the valid
213  // patterns.
214  for (PHINode &InnerPHI : FI.InnerLoop->getHeader()->phis()) {
215  // The induction PHIs break these rules, and that's OK because we treat
216  // them specially when doing the transformation.
217  if (&InnerPHI == FI.InnerInductionPHI)
218  continue;
219 
220  // Each inner loop PHI node must have two incoming values/blocks - one
221  // from the pre-header, and one from the latch.
222  assert(InnerPHI.getNumIncomingValues() == 2);
223  Value *PreHeaderValue =
224  InnerPHI.getIncomingValueForBlock(FI.InnerLoop->getLoopPreheader());
225  Value *LatchValue =
226  InnerPHI.getIncomingValueForBlock(FI.InnerLoop->getLoopLatch());
227 
228  // The incoming value from the outer loop must be the PHI node in the
229  // outer loop header, with no modifications made in the top of the outer
230  // loop.
231  PHINode *OuterPHI = dyn_cast<PHINode>(PreHeaderValue);
232  if (!OuterPHI || OuterPHI->getParent() != FI.OuterLoop->getHeader()) {
233  LLVM_DEBUG(dbgs() << "value modified in top of outer loop\n");
234  return false;
235  }
236 
237  // The other incoming value must come from the inner loop, without any
238  // modifications in the tail end of the outer loop. We are in LCSSA form,
239  // so this will actually be a PHI in the inner loop's exit block, which
240  // only uses values from inside the inner loop.
241  PHINode *LCSSAPHI = dyn_cast<PHINode>(
243  if (!LCSSAPHI) {
244  LLVM_DEBUG(dbgs() << "could not find LCSSA PHI\n");
245  return false;
246  }
247 
248  // The value used by the LCSSA PHI must be the same one that the inner
249  // loop's PHI uses.
250  if (LCSSAPHI->hasConstantValue() != LatchValue) {
251  LLVM_DEBUG(
252  dbgs() << "LCSSA PHI incoming value does not match latch value\n");
253  return false;
254  }
255 
256  LLVM_DEBUG(dbgs() << "PHI pair is safe:\n");
257  LLVM_DEBUG(dbgs() << " Inner: "; InnerPHI.dump());
258  LLVM_DEBUG(dbgs() << " Outer: "; OuterPHI->dump());
259  SafeOuterPHIs.insert(OuterPHI);
260  FI.InnerPHIsToTransform.insert(&InnerPHI);
261  }
262 
263  for (PHINode &OuterPHI : FI.OuterLoop->getHeader()->phis()) {
264  if (!SafeOuterPHIs.count(&OuterPHI)) {
265  LLVM_DEBUG(dbgs() << "found unsafe PHI in outer loop: "; OuterPHI.dump());
266  return false;
267  }
268  }
269 
270  LLVM_DEBUG(dbgs() << "checkPHIs: OK\n");
271  return true;
272 }
273 
274 static bool
276  SmallPtrSetImpl<Instruction *> &IterationInstructions,
277  const TargetTransformInfo *TTI) {
278  // Check for instructions in the outer but not inner loop. If any of these
279  // have side-effects then this transformation is not legal, and if there is
280  // a significant amount of code here which can't be optimised out that it's
281  // not profitable (as these instructions would get executed for each
282  // iteration of the inner loop).
283  unsigned RepeatedInstrCost = 0;
284  for (auto *B : FI.OuterLoop->getBlocks()) {
285  if (FI.InnerLoop->contains(B))
286  continue;
287 
288  for (auto &I : *B) {
289  if (!isa<PHINode>(&I) && !I.isTerminator() &&
291  LLVM_DEBUG(dbgs() << "Cannot flatten because instruction may have "
292  "side effects: ";
293  I.dump());
294  return false;
295  }
296  // The execution count of the outer loop's iteration instructions
297  // (increment, compare and branch) will be increased, but the
298  // equivalent instructions will be removed from the inner loop, so
299  // they make a net difference of zero.
300  if (IterationInstructions.count(&I))
301  continue;
302  // The uncoditional branch to the inner loop's header will turn into
303  // a fall-through, so adds no cost.
304  BranchInst *Br = dyn_cast<BranchInst>(&I);
305  if (Br && Br->isUnconditional() &&
306  Br->getSuccessor(0) == FI.InnerLoop->getHeader())
307  continue;
308  // Multiplies of the outer iteration variable and inner iteration
309  // count will be optimised out.
311  m_Specific(FI.InnerLimit))))
312  continue;
314  LLVM_DEBUG(dbgs() << "Cost " << Cost << ": "; I.dump());
315  RepeatedInstrCost += Cost;
316  }
317  }
318 
319  LLVM_DEBUG(dbgs() << "Cost of instructions that will be repeated: "
320  << RepeatedInstrCost << "\n");
321  // Bail out if flattening the loops would cause instructions in the outer
322  // loop but not in the inner loop to be executed extra times.
323  if (RepeatedInstrCost > RepeatedInstructionThreshold) {
324  LLVM_DEBUG(dbgs() << "checkOuterLoopInsts: not profitable, bailing.\n");
325  return false;
326  }
327 
328  LLVM_DEBUG(dbgs() << "checkOuterLoopInsts: OK\n");
329  return true;
330 }
331 
332 static bool checkIVUsers(struct FlattenInfo &FI) {
333  // We require all uses of both induction variables to match this pattern:
334  //
335  // (OuterPHI * InnerLimit) + InnerPHI
336  //
337  // Any uses of the induction variables not matching that pattern would
338  // require a div/mod to reconstruct in the flattened loop, so the
339  // transformation wouldn't be profitable.
340 
341  Value *InnerLimit = FI.InnerLimit;
342  if (FI.Widened &&
343  (isa<SExtInst>(InnerLimit) || isa<ZExtInst>(InnerLimit)))
344  InnerLimit = cast<Instruction>(InnerLimit)->getOperand(0);
345 
346  // Check that all uses of the inner loop's induction variable match the
347  // expected pattern, recording the uses of the outer IV.
348  SmallPtrSet<Value *, 4> ValidOuterPHIUses;
349  for (User *U : FI.InnerInductionPHI->users()) {
350  if (U == FI.InnerIncrement)
351  continue;
352 
353  // After widening the IVs, a trunc instruction might have been introduced, so
354  // look through truncs.
355  if (isa<TruncInst>(U)) {
356  if (!U->hasOneUse())
357  return false;
358  U = *U->user_begin();
359  }
360 
361  LLVM_DEBUG(dbgs() << "Found use of inner induction variable: "; U->dump());
362 
363  Value *MatchedMul;
364  Value *MatchedItCount;
365  bool IsAdd = match(U, m_c_Add(m_Specific(FI.InnerInductionPHI),
366  m_Value(MatchedMul))) &&
367  match(MatchedMul, m_c_Mul(m_Specific(FI.OuterInductionPHI),
368  m_Value(MatchedItCount)));
369 
370  // Matches the same pattern as above, except it also looks for truncs
371  // on the phi, which can be the result of widening the induction variables.
372  bool IsAddTrunc = match(U, m_c_Add(m_Trunc(m_Specific(FI.InnerInductionPHI)),
373  m_Value(MatchedMul))) &&
374  match(MatchedMul,
376  m_Value(MatchedItCount)));
377 
378  if ((IsAdd || IsAddTrunc) && MatchedItCount == InnerLimit) {
379  LLVM_DEBUG(dbgs() << "Use is optimisable\n");
380  ValidOuterPHIUses.insert(MatchedMul);
381  FI.LinearIVUses.insert(U);
382  } else {
383  LLVM_DEBUG(dbgs() << "Did not match expected pattern, bailing\n");
384  return false;
385  }
386  }
387 
388  // Check that there are no uses of the outer IV other than the ones found
389  // as part of the pattern above.
390  for (User *U : FI.OuterInductionPHI->users()) {
391  if (U == FI.OuterIncrement)
392  continue;
393 
394  auto IsValidOuterPHIUses = [&] (User *U) -> bool {
395  LLVM_DEBUG(dbgs() << "Found use of outer induction variable: "; U->dump());
396  if (!ValidOuterPHIUses.count(U)) {
397  LLVM_DEBUG(dbgs() << "Did not match expected pattern, bailing\n");
398  return false;
399  }
400  LLVM_DEBUG(dbgs() << "Use is optimisable\n");
401  return true;
402  };
403 
404  if (auto *V = dyn_cast<TruncInst>(U)) {
405  for (auto *K : V->users()) {
406  if (!IsValidOuterPHIUses(K))
407  return false;
408  }
409  continue;
410  }
411 
412  if (!IsValidOuterPHIUses(U))
413  return false;
414  }
415 
416  LLVM_DEBUG(dbgs() << "checkIVUsers: OK\n";
417  dbgs() << "Found " << FI.LinearIVUses.size()
418  << " value(s) that can be replaced:\n";
419  for (Value *V : FI.LinearIVUses) {
420  dbgs() << " ";
421  V->dump();
422  });
423  return true;
424 }
425 
426 // Return an OverflowResult dependant on if overflow of the multiplication of
427 // InnerLimit and OuterLimit can be assumed not to happen.
429  DominatorTree *DT, AssumptionCache *AC) {
430  Function *F = FI.OuterLoop->getHeader()->getParent();
431  const DataLayout &DL = F->getParent()->getDataLayout();
432 
433  // For debugging/testing.
434  if (AssumeNoOverflow)
436 
437  // Check if the multiply could not overflow due to known ranges of the
438  // input values.
440  FI.InnerLimit, FI.OuterLimit, DL, AC,
443  return OR;
444 
445  for (Value *V : FI.LinearIVUses) {
446  for (Value *U : V->users()) {
447  if (auto *GEP = dyn_cast<GetElementPtrInst>(U)) {
448  // The IV is used as the operand of a GEP, and the IV is at least as
449  // wide as the address space of the GEP. In this case, the GEP would
450  // wrap around the address space before the IV increment wraps, which
451  // would be UB.
452  if (GEP->isInBounds() &&
453  V->getType()->getIntegerBitWidth() >=
454  DL.getPointerTypeSizeInBits(GEP->getType())) {
455  LLVM_DEBUG(
456  dbgs() << "use of linear IV would be UB if overflow occurred: ";
457  GEP->dump());
459  }
460  }
461  }
462  }
463 
465 }
466 
467 static bool CanFlattenLoopPair(struct FlattenInfo &FI, DominatorTree *DT,
468  LoopInfo *LI, ScalarEvolution *SE,
470  SmallPtrSet<Instruction *, 8> IterationInstructions;
471  if (!findLoopComponents(FI.InnerLoop, IterationInstructions, FI.InnerInductionPHI,
472  FI.InnerLimit, FI.InnerIncrement, FI.InnerBranch, SE))
473  return false;
474  if (!findLoopComponents(FI.OuterLoop, IterationInstructions, FI.OuterInductionPHI,
475  FI.OuterLimit, FI.OuterIncrement, FI.OuterBranch, SE))
476  return false;
477 
478  // Both of the loop limit values must be invariant in the outer loop
479  // (non-instructions are all inherently invariant).
480  if (!FI.OuterLoop->isLoopInvariant(FI.InnerLimit)) {
481  LLVM_DEBUG(dbgs() << "inner loop limit not invariant\n");
482  return false;
483  }
484  if (!FI.OuterLoop->isLoopInvariant(FI.OuterLimit)) {
485  LLVM_DEBUG(dbgs() << "outer loop limit not invariant\n");
486  return false;
487  }
488 
489  if (!checkPHIs(FI, TTI))
490  return false;
491 
492  // FIXME: it should be possible to handle different types correctly.
494  return false;
495 
496  if (!checkOuterLoopInsts(FI, IterationInstructions, TTI))
497  return false;
498 
499  // Find the values in the loop that can be replaced with the linearized
500  // induction variable, and check that there are no other uses of the inner
501  // or outer induction variable. If there were, we could still do this
502  // transformation, but we'd have to insert a div/mod to calculate the
503  // original IVs, so it wouldn't be profitable.
504  if (!checkIVUsers(FI))
505  return false;
506 
507  LLVM_DEBUG(dbgs() << "CanFlattenLoopPair: OK\n");
508  return true;
509 }
510 
511 static bool DoFlattenLoopPair(struct FlattenInfo &FI, DominatorTree *DT,
512  LoopInfo *LI, ScalarEvolution *SE,
513  AssumptionCache *AC,
514  const TargetTransformInfo *TTI) {
515  Function *F = FI.OuterLoop->getHeader()->getParent();
516  LLVM_DEBUG(dbgs() << "Checks all passed, doing the transformation\n");
517  {
518  using namespace ore;
520  FI.InnerLoop->getHeader());
522  Remark << "Flattened into outer loop";
523  ORE.emit(Remark);
524  }
525 
526  Value *NewTripCount =
527  BinaryOperator::CreateMul(FI.InnerLimit, FI.OuterLimit, "flatten.tripcount",
529  LLVM_DEBUG(dbgs() << "Created new trip count in preheader: ";
530  NewTripCount->dump());
531 
532  // Fix up PHI nodes that take values from the inner loop back-edge, which
533  // we are about to remove.
535 
536  // The old Phi will be optimised away later, but for now we can't leave
537  // leave it in an invalid state, so are updating them too.
538  for (PHINode *PHI : FI.InnerPHIsToTransform)
540 
541  // Modify the trip count of the outer loop to be the product of the two
542  // trip counts.
543  cast<User>(FI.OuterBranch->getCondition())->setOperand(1, NewTripCount);
544 
545  // Replace the inner loop backedge with an unconditional branch to the exit.
546  BasicBlock *InnerExitBlock = FI.InnerLoop->getExitBlock();
547  BasicBlock *InnerExitingBlock = FI.InnerLoop->getExitingBlock();
548  InnerExitingBlock->getTerminator()->eraseFromParent();
549  BranchInst::Create(InnerExitBlock, InnerExitingBlock);
550  DT->deleteEdge(InnerExitingBlock, FI.InnerLoop->getHeader());
551 
552  // Replace all uses of the polynomial calculated from the two induction
553  // variables with the one new one.
555  for (Value *V : FI.LinearIVUses) {
556  Value *OuterValue = FI.OuterInductionPHI;
557  if (FI.Widened)
558  OuterValue = Builder.CreateTrunc(FI.OuterInductionPHI, V->getType(),
559  "flatten.trunciv");
560 
561  LLVM_DEBUG(dbgs() << "Replacing: "; V->dump();
562  dbgs() << "with: "; OuterValue->dump());
563  V->replaceAllUsesWith(OuterValue);
564  }
565 
566  // Tell LoopInfo, SCEV and the pass manager that the inner loop has been
567  // deleted, and any information that have about the outer loop invalidated.
568  SE->forgetLoop(FI.OuterLoop);
569  SE->forgetLoop(FI.InnerLoop);
570  LI->erase(FI.InnerLoop);
571  return true;
572 }
573 
574 static bool CanWidenIV(struct FlattenInfo &FI, DominatorTree *DT,
575  LoopInfo *LI, ScalarEvolution *SE,
577  if (!WidenIV) {
578  LLVM_DEBUG(dbgs() << "Widening the IVs is disabled\n");
579  return false;
580  }
581 
582  LLVM_DEBUG(dbgs() << "Try widening the IVs\n");
583  Module *M = FI.InnerLoop->getHeader()->getParent()->getParent();
584  auto &DL = M->getDataLayout();
585  auto *InnerType = FI.InnerInductionPHI->getType();
586  auto *OuterType = FI.OuterInductionPHI->getType();
587  unsigned MaxLegalSize = DL.getLargestLegalIntTypeSizeInBits();
588  auto *MaxLegalType = DL.getLargestLegalIntType(M->getContext());
589 
590  // If both induction types are less than the maximum legal integer width,
591  // promote both to the widest type available so we know calculating
592  // (OuterLimit * InnerLimit) as the new trip count is safe.
593  if (InnerType != OuterType ||
594  InnerType->getScalarSizeInBits() >= MaxLegalSize ||
595  MaxLegalType->getScalarSizeInBits() < InnerType->getScalarSizeInBits() * 2) {
596  LLVM_DEBUG(dbgs() << "Can't widen the IV\n");
597  return false;
598  }
599 
600  SCEVExpander Rewriter(*SE, DL, "loopflatten");
603  WideIVs.push_back( {FI.InnerInductionPHI, MaxLegalType, false });
604  WideIVs.push_back( {FI.OuterInductionPHI, MaxLegalType, false });
605  unsigned ElimExt;
606  unsigned Widened;
607 
608  for (unsigned i = 0; i < WideIVs.size(); i++) {
609  PHINode *WidePhi = createWideIV(WideIVs[i], LI, SE, Rewriter, DT, DeadInsts,
610  ElimExt, Widened, true /* HasGuards */,
611  true /* UsePostIncrementRanges */);
612  if (!WidePhi)
613  return false;
614  LLVM_DEBUG(dbgs() << "Created wide phi: "; WidePhi->dump());
615  LLVM_DEBUG(dbgs() << "Deleting old phi: "; WideIVs[i].NarrowIV->dump());
616  RecursivelyDeleteDeadPHINode(WideIVs[i].NarrowIV);
617  }
618  // After widening, rediscover all the loop components.
619  assert(Widened && "Widenend IV expected");
620  FI.Widened = true;
621  return CanFlattenLoopPair(FI, DT, LI, SE, AC, TTI);
622 }
623 
624 static bool FlattenLoopPair(struct FlattenInfo &FI, DominatorTree *DT,
625  LoopInfo *LI, ScalarEvolution *SE,
626  AssumptionCache *AC,
627  const TargetTransformInfo *TTI) {
628  LLVM_DEBUG(
629  dbgs() << "Loop flattening running on outer loop "
630  << FI.OuterLoop->getHeader()->getName() << " and inner loop "
631  << FI.InnerLoop->getHeader()->getName() << " in "
632  << FI.OuterLoop->getHeader()->getParent()->getName() << "\n");
633 
634  if (!CanFlattenLoopPair(FI, DT, LI, SE, AC, TTI))
635  return false;
636 
637  // Check if we can widen the induction variables to avoid overflow checks.
638  if (CanWidenIV(FI, DT, LI, SE, AC, TTI))
639  return DoFlattenLoopPair(FI, DT, LI, SE, AC, TTI);
640 
641  // Check if the new iteration variable might overflow. In this case, we
642  // need to version the loop, and select the original version at runtime if
643  // the iteration space is too large.
644  // TODO: We currently don't version the loop.
645  OverflowResult OR = checkOverflow(FI, DT, AC);
648  LLVM_DEBUG(dbgs() << "Multiply would always overflow, so not profitable\n");
649  return false;
650  } else if (OR == OverflowResult::MayOverflow) {
651  LLVM_DEBUG(dbgs() << "Multiply might overflow, not flattening\n");
652  return false;
653  }
654 
655  LLVM_DEBUG(dbgs() << "Multiply cannot overflow, modifying loop in-place\n");
656  return DoFlattenLoopPair(FI, DT, LI, SE, AC, TTI);
657 }
658 
661  bool Changed = false;
662  for (auto *InnerLoop : LI->getLoopsInPreorder()) {
663  auto *OuterLoop = InnerLoop->getParentLoop();
664  if (!OuterLoop)
665  continue;
666  struct FlattenInfo FI(OuterLoop, InnerLoop);
667  Changed |= FlattenLoopPair(FI, DT, LI, SE, AC, TTI);
668  }
669  return Changed;
670 }
671 
674  auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
675  auto *LI = &AM.getResult<LoopAnalysis>(F);
676  auto *SE = &AM.getResult<ScalarEvolutionAnalysis>(F);
677  auto *AC = &AM.getResult<AssumptionAnalysis>(F);
678  auto *TTI = &AM.getResult<TargetIRAnalysis>(F);
679 
680  if (!Flatten(DT, LI, SE, AC, TTI))
681  return PreservedAnalyses::all();
682 
684  PA.preserveSet<CFGAnalyses>();
685  return PA;
686 }
687 
688 namespace {
689 class LoopFlattenLegacyPass : public FunctionPass {
690 public:
691  static char ID; // Pass ID, replacement for typeid
692  LoopFlattenLegacyPass() : FunctionPass(ID) {
694  }
695 
696  // Possibly flatten loop L into its child.
697  bool runOnFunction(Function &F) override;
698 
699  void getAnalysisUsage(AnalysisUsage &AU) const override {
705  }
706 };
707 } // namespace
708 
710 INITIALIZE_PASS_BEGIN(LoopFlattenLegacyPass, "loop-flatten", "Flattens loops",
711  false, false)
714 INITIALIZE_PASS_END(LoopFlattenLegacyPass, "loop-flatten", "Flattens loops",
715  false, false)
716 
717 FunctionPass *llvm::createLoopFlattenPass() { return new LoopFlattenLegacyPass(); }
718 
720  ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
721  LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
722  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
723  DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
724  auto &TTIP = getAnalysis<TargetTransformInfoWrapperPass>();
725  auto *TTI = &TTIP.getTTI(F);
726  auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
727  return Flatten(DT, LI, SE, AC, TTI);
728 }
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
BranchInst * OuterBranch
Definition: LoopFlatten.cpp:84
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:111
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
loop flatten
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:215
SmallPtrSet< PHINode *, 4 > InnerPHIsToTransform
Definition: LoopFlatten.cpp:86
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
INITIALIZE_PASS_BEGIN(LoopFlattenLegacyPass, "loop-flatten", "Flattens loops", false, false) INITIALIZE_PASS_END(LoopFlattenLegacyPass
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:785
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static bool CanWidenIV(struct FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI)
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
unsigned less than
Definition: InstrTypes.h:747
The main scalar evolution driver.
FunctionPass * createLoopFlattenPass()
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:166
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
Analysis pass providing the TargetTransformInfo.
Always overflows in the direction of signed/unsigned min value.
BasicBlock * getSuccessor(unsigned i) const
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:249
F(f)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Hexagon Common GEP
Value * getCondition() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:148
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
PHINode * InnerInductionPHI
Definition: LoopFlatten.cpp:77
Loop * InnerLoop
Definition: LoopFlatten.cpp:76
PHINode * OuterInductionPHI
Definition: LoopFlatten.cpp:78
static cl::opt< bool > AssumeNoOverflow("loop-flatten-assume-no-overflow", cl::Hidden, cl::init(false), cl::desc("Assume that the product of the two iteration " "limits will never overflow"))
void dump() const
Support for debugging, callable in GDB: V->dump()
Definition: AsmWriter.cpp:4727
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
AnalysisUsage & addRequired()
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
PHINode * createWideIV(const WideIVInfo &WI, LoopInfo *LI, ScalarEvolution *SE, SCEVExpander &Rewriter, DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, unsigned &NumElimExt, unsigned &NumWidened, bool HasGuards, bool UsePostIncrementRanges)
Widen Induction Variables - Extend the width of an IV to cover its widest uses.
int getUserCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const
Estimate the cost of a given IR user when lowered.
static bool DoFlattenLoopPair(struct FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI)
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
void deleteEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge deletion and update the tree.
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:880
static bool CanFlattenLoopPair(struct FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI)
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1224
BlockT * getHeader() const
Definition: LoopInfo.h:104
Value * OuterLimit
Definition: LoopFlatten.cpp:80
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
May or may not overflow.
static bool checkPHIs(struct FlattenInfo &FI, const TargetTransformInfo *TTI)
#define DEBUG_TYPE
Definition: LoopFlatten.cpp:52
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:523
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
The weighted sum of size and latency.
static bool checkOuterLoopInsts(struct FlattenInfo &FI, SmallPtrSetImpl< Instruction * > &IterationInstructions, const TargetTransformInfo *TTI)
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:427
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Wrapper pass for TargetTransformInfo.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
BinaryOp_match< LHS, RHS, Instruction::Add, true > m_c_Add(const LHS &L, const RHS &R)
Matches a Add with LHS and RHS in either order.
static bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)
Returns true if Phi is an induction in the loop L.
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Conditional or Unconditional Branch instruction.
static cl::opt< unsigned > RepeatedInstructionThreshold("loop-flatten-cost-threshold", cl::Hidden, cl::init(2), cl::desc("Limit on the cost of instructions that can be repeated due to " "loop flattening"))
Loop * OuterLoop
Definition: LoopFlatten.cpp:75
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Value * InnerLimit
Definition: LoopFlatten.cpp:79
bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
If the specified value is an effectively dead PHI node, due to being a def-use chain of single-use no...
Definition: Local.cpp:594
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
Diagnostic information for applied optimization remarks.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:754
Represent the analysis usage information of a pass.
This instruction compares its operands according to the predicate given to the constructor.
static bool findLoopComponents(Loop *L, SmallPtrSetImpl< Instruction * > &IterationInstructions, PHINode *&InductionPHI, Value *&Limit, BinaryOperator *&Increment, BranchInst *&BackBranch, ScalarEvolution *SE)
Definition: LoopFlatten.cpp:96
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:375
assume Assume Builder
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:81
static bool checkIVUsers(struct FlattenInfo &FI)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:634
static cl::opt< bool > WidenIV("loop-flatten-widen-iv", cl::Hidden, cl::init(true), cl::desc("Widen the loop induction variables, if possible, so " "overflow checks won't reject flattening"))
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
BinaryOperator * InnerIncrement
Definition: LoopFlatten.cpp:81
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:63
size_type size() const
Definition: SmallPtrSet.h:92
A function analysis which provides an AssumptionCache.
Value * hasConstantValue() const
If the specified PHI node always merges together the same value, return the value,...
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
A struct for saving information about induction variables.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
void initializeLoopFlattenLegacyPassPass(PassRegistry &)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1116
Module.h This file contains the declarations for the Module class.
static OverflowResult checkOverflow(struct FlattenInfo &FI, DominatorTree *DT, AssumptionCache *AC)
BinaryOp_match< LHS, RHS, Instruction::Mul, true > m_c_Mul(const LHS &L, const RHS &R)
Matches a Mul with LHS and RHS in either order.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
bool isConditional() const
unsigned getNumIncomingValues() const
Return the number of incoming edges.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
BranchInst * InnerBranch
Definition: LoopFlatten.cpp:83
iterator_range< user_iterator > users()
Definition: Value.h:424
This class uses information about analyze scalars to rewrite expressions in canonical form.
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
Analysis pass that exposes the ScalarEvolution for a function.
Virtual Register Rewriter
Definition: VirtRegMap.cpp:221
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:471
Always overflows in the direction of signed/unsigned max value.
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:96
OverflowResult
StringRef getName() const
Definition: LoopInfo.h:862
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:529
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:171
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:191
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:295
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
#define I(x, y, z)
Definition: MD5.cpp:59
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:155
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:354
bool isUnconditional() const
SmallVector< LoopT *, 4 > getLoopsInPreorder()
Return all of the loops in the function in preorder across the loop nests, with siblings in forward p...
Definition: LoopInfoImpl.h:573
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool Flatten(DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, TargetTransformInfo *TTI)
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:572
LLVM Value Representation.
Definition: Value.h:75
BinaryOperator * OuterIncrement
Definition: LoopFlatten.cpp:82
static bool FlattenLoopPair(struct FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI)
loop Flattens loops
A container for analyses that lazily runs them and caches their results.
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
This pass exposes codegen information to IR-level passes.
SmallPtrSet< Value *, 4 > LinearIVUses
Definition: LoopFlatten.cpp:85
FlattenInfo(Loop *OL, Loop *IL)
Definition: LoopFlatten.cpp:91
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
#define LLVM_DEBUG(X)
Definition: Debug.h:122
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:48
The optimization diagnostic interface.
const BasicBlock * getParent() const
Definition: Instruction.h:94
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL