LLVM  13.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  InstructionCost 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;
313  InstructionCost Cost =
315  LLVM_DEBUG(dbgs() << "Cost " << Cost << ": "; I.dump());
316  RepeatedInstrCost += Cost;
317  }
318  }
319 
320  LLVM_DEBUG(dbgs() << "Cost of instructions that will be repeated: "
321  << RepeatedInstrCost << "\n");
322  // Bail out if flattening the loops would cause instructions in the outer
323  // loop but not in the inner loop to be executed extra times.
324  if (RepeatedInstrCost > RepeatedInstructionThreshold) {
325  LLVM_DEBUG(dbgs() << "checkOuterLoopInsts: not profitable, bailing.\n");
326  return false;
327  }
328 
329  LLVM_DEBUG(dbgs() << "checkOuterLoopInsts: OK\n");
330  return true;
331 }
332 
333 static bool checkIVUsers(struct FlattenInfo &FI) {
334  // We require all uses of both induction variables to match this pattern:
335  //
336  // (OuterPHI * InnerLimit) + InnerPHI
337  //
338  // Any uses of the induction variables not matching that pattern would
339  // require a div/mod to reconstruct in the flattened loop, so the
340  // transformation wouldn't be profitable.
341 
342  Value *InnerLimit = FI.InnerLimit;
343  if (FI.Widened &&
344  (isa<SExtInst>(InnerLimit) || isa<ZExtInst>(InnerLimit)))
345  InnerLimit = cast<Instruction>(InnerLimit)->getOperand(0);
346 
347  // Check that all uses of the inner loop's induction variable match the
348  // expected pattern, recording the uses of the outer IV.
349  SmallPtrSet<Value *, 4> ValidOuterPHIUses;
350  for (User *U : FI.InnerInductionPHI->users()) {
351  if (U == FI.InnerIncrement)
352  continue;
353 
354  // After widening the IVs, a trunc instruction might have been introduced, so
355  // look through truncs.
356  if (isa<TruncInst>(U)) {
357  if (!U->hasOneUse())
358  return false;
359  U = *U->user_begin();
360  }
361 
362  LLVM_DEBUG(dbgs() << "Found use of inner induction variable: "; U->dump());
363 
364  Value *MatchedMul;
365  Value *MatchedItCount;
366  bool IsAdd = match(U, m_c_Add(m_Specific(FI.InnerInductionPHI),
367  m_Value(MatchedMul))) &&
368  match(MatchedMul, m_c_Mul(m_Specific(FI.OuterInductionPHI),
369  m_Value(MatchedItCount)));
370 
371  // Matches the same pattern as above, except it also looks for truncs
372  // on the phi, which can be the result of widening the induction variables.
373  bool IsAddTrunc = match(U, m_c_Add(m_Trunc(m_Specific(FI.InnerInductionPHI)),
374  m_Value(MatchedMul))) &&
375  match(MatchedMul,
377  m_Value(MatchedItCount)));
378 
379  if ((IsAdd || IsAddTrunc) && MatchedItCount == InnerLimit) {
380  LLVM_DEBUG(dbgs() << "Use is optimisable\n");
381  ValidOuterPHIUses.insert(MatchedMul);
382  FI.LinearIVUses.insert(U);
383  } else {
384  LLVM_DEBUG(dbgs() << "Did not match expected pattern, bailing\n");
385  return false;
386  }
387  }
388 
389  // Check that there are no uses of the outer IV other than the ones found
390  // as part of the pattern above.
391  for (User *U : FI.OuterInductionPHI->users()) {
392  if (U == FI.OuterIncrement)
393  continue;
394 
395  auto IsValidOuterPHIUses = [&] (User *U) -> bool {
396  LLVM_DEBUG(dbgs() << "Found use of outer induction variable: "; U->dump());
397  if (!ValidOuterPHIUses.count(U)) {
398  LLVM_DEBUG(dbgs() << "Did not match expected pattern, bailing\n");
399  return false;
400  }
401  LLVM_DEBUG(dbgs() << "Use is optimisable\n");
402  return true;
403  };
404 
405  if (auto *V = dyn_cast<TruncInst>(U)) {
406  for (auto *K : V->users()) {
407  if (!IsValidOuterPHIUses(K))
408  return false;
409  }
410  continue;
411  }
412 
413  if (!IsValidOuterPHIUses(U))
414  return false;
415  }
416 
417  LLVM_DEBUG(dbgs() << "checkIVUsers: OK\n";
418  dbgs() << "Found " << FI.LinearIVUses.size()
419  << " value(s) that can be replaced:\n";
420  for (Value *V : FI.LinearIVUses) {
421  dbgs() << " ";
422  V->dump();
423  });
424  return true;
425 }
426 
427 // Return an OverflowResult dependant on if overflow of the multiplication of
428 // InnerLimit and OuterLimit can be assumed not to happen.
430  DominatorTree *DT, AssumptionCache *AC) {
431  Function *F = FI.OuterLoop->getHeader()->getParent();
432  const DataLayout &DL = F->getParent()->getDataLayout();
433 
434  // For debugging/testing.
435  if (AssumeNoOverflow)
437 
438  // Check if the multiply could not overflow due to known ranges of the
439  // input values.
441  FI.InnerLimit, FI.OuterLimit, DL, AC,
444  return OR;
445 
446  for (Value *V : FI.LinearIVUses) {
447  for (Value *U : V->users()) {
448  if (auto *GEP = dyn_cast<GetElementPtrInst>(U)) {
449  // The IV is used as the operand of a GEP, and the IV is at least as
450  // wide as the address space of the GEP. In this case, the GEP would
451  // wrap around the address space before the IV increment wraps, which
452  // would be UB.
453  if (GEP->isInBounds() &&
454  V->getType()->getIntegerBitWidth() >=
455  DL.getPointerTypeSizeInBits(GEP->getType())) {
456  LLVM_DEBUG(
457  dbgs() << "use of linear IV would be UB if overflow occurred: ";
458  GEP->dump());
460  }
461  }
462  }
463  }
464 
466 }
467 
468 static bool CanFlattenLoopPair(struct FlattenInfo &FI, DominatorTree *DT,
469  LoopInfo *LI, ScalarEvolution *SE,
471  SmallPtrSet<Instruction *, 8> IterationInstructions;
472  if (!findLoopComponents(FI.InnerLoop, IterationInstructions, FI.InnerInductionPHI,
473  FI.InnerLimit, FI.InnerIncrement, FI.InnerBranch, SE))
474  return false;
475  if (!findLoopComponents(FI.OuterLoop, IterationInstructions, FI.OuterInductionPHI,
476  FI.OuterLimit, FI.OuterIncrement, FI.OuterBranch, SE))
477  return false;
478 
479  // Both of the loop limit values must be invariant in the outer loop
480  // (non-instructions are all inherently invariant).
481  if (!FI.OuterLoop->isLoopInvariant(FI.InnerLimit)) {
482  LLVM_DEBUG(dbgs() << "inner loop limit not invariant\n");
483  return false;
484  }
485  if (!FI.OuterLoop->isLoopInvariant(FI.OuterLimit)) {
486  LLVM_DEBUG(dbgs() << "outer loop limit not invariant\n");
487  return false;
488  }
489 
490  if (!checkPHIs(FI, TTI))
491  return false;
492 
493  // FIXME: it should be possible to handle different types correctly.
495  return false;
496 
497  if (!checkOuterLoopInsts(FI, IterationInstructions, TTI))
498  return false;
499 
500  // Find the values in the loop that can be replaced with the linearized
501  // induction variable, and check that there are no other uses of the inner
502  // or outer induction variable. If there were, we could still do this
503  // transformation, but we'd have to insert a div/mod to calculate the
504  // original IVs, so it wouldn't be profitable.
505  if (!checkIVUsers(FI))
506  return false;
507 
508  LLVM_DEBUG(dbgs() << "CanFlattenLoopPair: OK\n");
509  return true;
510 }
511 
512 static bool DoFlattenLoopPair(struct FlattenInfo &FI, DominatorTree *DT,
513  LoopInfo *LI, ScalarEvolution *SE,
514  AssumptionCache *AC,
515  const TargetTransformInfo *TTI) {
516  Function *F = FI.OuterLoop->getHeader()->getParent();
517  LLVM_DEBUG(dbgs() << "Checks all passed, doing the transformation\n");
518  {
519  using namespace ore;
521  FI.InnerLoop->getHeader());
523  Remark << "Flattened into outer loop";
524  ORE.emit(Remark);
525  }
526 
527  Value *NewTripCount =
528  BinaryOperator::CreateMul(FI.InnerLimit, FI.OuterLimit, "flatten.tripcount",
530  LLVM_DEBUG(dbgs() << "Created new trip count in preheader: ";
531  NewTripCount->dump());
532 
533  // Fix up PHI nodes that take values from the inner loop back-edge, which
534  // we are about to remove.
536 
537  // The old Phi will be optimised away later, but for now we can't leave
538  // leave it in an invalid state, so are updating them too.
539  for (PHINode *PHI : FI.InnerPHIsToTransform)
541 
542  // Modify the trip count of the outer loop to be the product of the two
543  // trip counts.
544  cast<User>(FI.OuterBranch->getCondition())->setOperand(1, NewTripCount);
545 
546  // Replace the inner loop backedge with an unconditional branch to the exit.
547  BasicBlock *InnerExitBlock = FI.InnerLoop->getExitBlock();
548  BasicBlock *InnerExitingBlock = FI.InnerLoop->getExitingBlock();
549  InnerExitingBlock->getTerminator()->eraseFromParent();
550  BranchInst::Create(InnerExitBlock, InnerExitingBlock);
551  DT->deleteEdge(InnerExitingBlock, FI.InnerLoop->getHeader());
552 
553  // Replace all uses of the polynomial calculated from the two induction
554  // variables with the one new one.
556  for (Value *V : FI.LinearIVUses) {
557  Value *OuterValue = FI.OuterInductionPHI;
558  if (FI.Widened)
559  OuterValue = Builder.CreateTrunc(FI.OuterInductionPHI, V->getType(),
560  "flatten.trunciv");
561 
562  LLVM_DEBUG(dbgs() << "Replacing: "; V->dump();
563  dbgs() << "with: "; OuterValue->dump());
564  V->replaceAllUsesWith(OuterValue);
565  }
566 
567  // Tell LoopInfo, SCEV and the pass manager that the inner loop has been
568  // deleted, and any information that have about the outer loop invalidated.
569  SE->forgetLoop(FI.OuterLoop);
570  SE->forgetLoop(FI.InnerLoop);
571  LI->erase(FI.InnerLoop);
572  return true;
573 }
574 
575 static bool CanWidenIV(struct FlattenInfo &FI, DominatorTree *DT,
576  LoopInfo *LI, ScalarEvolution *SE,
578  if (!WidenIV) {
579  LLVM_DEBUG(dbgs() << "Widening the IVs is disabled\n");
580  return false;
581  }
582 
583  LLVM_DEBUG(dbgs() << "Try widening the IVs\n");
585  auto &DL = M->getDataLayout();
586  auto *InnerType = FI.InnerInductionPHI->getType();
587  auto *OuterType = FI.OuterInductionPHI->getType();
588  unsigned MaxLegalSize = DL.getLargestLegalIntTypeSizeInBits();
589  auto *MaxLegalType = DL.getLargestLegalIntType(M->getContext());
590 
591  // If both induction types are less than the maximum legal integer width,
592  // promote both to the widest type available so we know calculating
593  // (OuterLimit * InnerLimit) as the new trip count is safe.
594  if (InnerType != OuterType ||
595  InnerType->getScalarSizeInBits() >= MaxLegalSize ||
596  MaxLegalType->getScalarSizeInBits() < InnerType->getScalarSizeInBits() * 2) {
597  LLVM_DEBUG(dbgs() << "Can't widen the IV\n");
598  return false;
599  }
600 
601  SCEVExpander Rewriter(*SE, DL, "loopflatten");
604  WideIVs.push_back( {FI.InnerInductionPHI, MaxLegalType, false });
605  WideIVs.push_back( {FI.OuterInductionPHI, MaxLegalType, false });
606  unsigned ElimExt;
607  unsigned Widened;
608 
609  for (unsigned i = 0; i < WideIVs.size(); i++) {
610  PHINode *WidePhi = createWideIV(WideIVs[i], LI, SE, Rewriter, DT, DeadInsts,
611  ElimExt, Widened, true /* HasGuards */,
612  true /* UsePostIncrementRanges */);
613  if (!WidePhi)
614  return false;
615  LLVM_DEBUG(dbgs() << "Created wide phi: "; WidePhi->dump());
616  LLVM_DEBUG(dbgs() << "Deleting old phi: "; WideIVs[i].NarrowIV->dump());
617  RecursivelyDeleteDeadPHINode(WideIVs[i].NarrowIV);
618  }
619  // After widening, rediscover all the loop components.
620  assert(Widened && "Widenend IV expected");
621  FI.Widened = true;
622  return CanFlattenLoopPair(FI, DT, LI, SE, AC, TTI);
623 }
624 
625 static bool FlattenLoopPair(struct FlattenInfo &FI, DominatorTree *DT,
626  LoopInfo *LI, ScalarEvolution *SE,
627  AssumptionCache *AC,
628  const TargetTransformInfo *TTI) {
629  LLVM_DEBUG(
630  dbgs() << "Loop flattening running on outer loop "
631  << FI.OuterLoop->getHeader()->getName() << " and inner loop "
632  << FI.InnerLoop->getHeader()->getName() << " in "
633  << FI.OuterLoop->getHeader()->getParent()->getName() << "\n");
634 
635  if (!CanFlattenLoopPair(FI, DT, LI, SE, AC, TTI))
636  return false;
637 
638  // Check if we can widen the induction variables to avoid overflow checks.
639  if (CanWidenIV(FI, DT, LI, SE, AC, TTI))
640  return DoFlattenLoopPair(FI, DT, LI, SE, AC, TTI);
641 
642  // Check if the new iteration variable might overflow. In this case, we
643  // need to version the loop, and select the original version at runtime if
644  // the iteration space is too large.
645  // TODO: We currently don't version the loop.
646  OverflowResult OR = checkOverflow(FI, DT, AC);
649  LLVM_DEBUG(dbgs() << "Multiply would always overflow, so not profitable\n");
650  return false;
651  } else if (OR == OverflowResult::MayOverflow) {
652  LLVM_DEBUG(dbgs() << "Multiply might overflow, not flattening\n");
653  return false;
654  }
655 
656  LLVM_DEBUG(dbgs() << "Multiply cannot overflow, modifying loop in-place\n");
657  return DoFlattenLoopPair(FI, DT, LI, SE, AC, TTI);
658 }
659 
662  bool Changed = false;
663  for (auto *InnerLoop : LI->getLoopsInPreorder()) {
664  auto *OuterLoop = InnerLoop->getParentLoop();
665  if (!OuterLoop)
666  continue;
667  struct FlattenInfo FI(OuterLoop, InnerLoop);
668  Changed |= FlattenLoopPair(FI, DT, LI, SE, AC, TTI);
669  }
670  return Changed;
671 }
672 
675  auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
676  auto *LI = &AM.getResult<LoopAnalysis>(F);
677  auto *SE = &AM.getResult<ScalarEvolutionAnalysis>(F);
678  auto *AC = &AM.getResult<AssumptionAnalysis>(F);
679  auto *TTI = &AM.getResult<TargetIRAnalysis>(F);
680 
681  if (!Flatten(DT, LI, SE, AC, TTI))
682  return PreservedAnalyses::all();
683 
685  PA.preserveSet<CFGAnalyses>();
686  return PA;
687 }
688 
689 namespace {
690 class LoopFlattenLegacyPass : public FunctionPass {
691 public:
692  static char ID; // Pass ID, replacement for typeid
693  LoopFlattenLegacyPass() : FunctionPass(ID) {
695  }
696 
697  // Possibly flatten loop L into its child.
698  bool runOnFunction(Function &F) override;
699 
700  void getAnalysisUsage(AnalysisUsage &AU) const override {
706  }
707 };
708 } // namespace
709 
711 INITIALIZE_PASS_BEGIN(LoopFlattenLegacyPass, "loop-flatten", "Flattens loops",
712  false, false)
715 INITIALIZE_PASS_END(LoopFlattenLegacyPass, "loop-flatten", "Flattens loops",
717 
718 FunctionPass *llvm::createLoopFlattenPass() { return new LoopFlattenLegacyPass(); }
719 
721  ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
722  LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
723  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
724  DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
725  auto &TTIP = getAnalysis<TargetTransformInfoWrapperPass>();
726  auto *TTI = &TTIP.getTTI(F);
727  auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
728  return Flatten(DT, LI, SE, AC, TTI);
729 }
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LoopFlattenLegacyPass, "loop-flatten", "Flattens loops", false, false) INITIALIZE_PASS_END(LoopFlattenLegacyPass
i
i
Definition: README.txt:29
llvm::InstructionCost
Definition: InstructionCost.h:26
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
AssumptionCache.h
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2225
llvm::Loop::isLoopInvariant
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:63
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2058
llvm
This class represents lattice values for constants.
Definition: AllocatorList.h:23
llvm::createWideIV
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.
Definition: SimplifyIndVar.cpp:2079
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:743
llvm::OverflowResult::NeverOverflows
@ NeverOverflows
Never overflows.
llvm::LoopBase::getExitBlock
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:82
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:111
llvm::ISD::OR
@ OR
Definition: ISDOpcodes.h:589
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
llvm::computeOverflowForUnsignedMul
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
Definition: ValueTracking.cpp:4509
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
ScalarEvolutionExpander.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:785
AssumeNoOverflow
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"))
Scalar.h
flatten
loop flatten
Definition: LoopFlatten.cpp:715
llvm::Function
Definition: Function.h:61
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:529
llvm::Value::dump
void dump() const
Support for debugging, callable in GDB: V->dump()
Definition: AsmWriter.cpp:4760
Pass.h
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
llvm::SCEVExpander
This class uses information about analyze scalars to rewrite expressions in canonical form.
Definition: ScalarEvolutionExpander.h:63
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:167
llvm::IRBuilder<>
llvm::Loop::getStartLoc
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:626
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:443
FlattenInfo::InnerInductionPHI
PHINode * InnerInductionPHI
Definition: LoopFlatten.cpp:77
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:744
llvm::PHINode::removeIncomingValue
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
Definition: Instructions.cpp:109
ValueTracking.h
Local.h
OptimizationRemarkEmitter.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::getLoopAnalysisUsage
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:150
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
FlattenInfo::OuterIncrement
BinaryOperator * OuterIncrement
Definition: LoopFlatten.cpp:82
LoopFlatten.h
ScalarEvolution.h
llvm::OverflowResult::AlwaysOverflowsLow
@ AlwaysOverflowsLow
Always overflows in the direction of signed/unsigned min value.
Module.h
FlattenInfo::OuterInductionPHI
PHINode * OuterInductionPHI
Definition: LoopFlatten.cpp:78
llvm::SmallPtrSet< Value *, 4 >
FlattenInfo::OuterLoop
Loop * OuterLoop
Definition: LoopFlatten.cpp:75
DEBUG_TYPE
#define DEBUG_TYPE
Definition: LoopFlatten.cpp:52
FlattenInfo::LinearIVUses
SmallPtrSet< Value *, 4 > LinearIVUses
Definition: LoopFlatten.cpp:85
FlattenInfo::InnerLimit
Value * InnerLimit
Definition: LoopFlatten.cpp:79
FlattenInfo::OuterBranch
BranchInst * OuterBranch
Definition: LoopFlatten.cpp:84
INITIALIZE_PASS_END
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Definition: RegBankSelect.cpp:69
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RecursivelyDeleteDeadPHINode
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:598
loop
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
Definition: README.txt:8
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
FlattenInfo::Widened
bool Widened
Definition: LoopFlatten.cpp:89
llvm::InductionDescriptor
A struct for saving information about induction variables.
Definition: IVDescriptors.h:257
llvm::LoopInfoBase::getLoopsInPreorder
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:574
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::isSafeToSpeculativelyExecute
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 ...
Definition: ValueTracking.cpp:4392
Rewriter
Virtual Register Rewriter
Definition: VirtRegMap.cpp:222
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::OverflowResult::MayOverflow
@ MayOverflow
May or may not overflow.
DoFlattenLoopPair
static bool DoFlattenLoopPair(struct FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI)
Definition: LoopFlatten.cpp:512
llvm::User
Definition: User.h:44
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:142
llvm::PatternMatch::m_c_Add
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.
Definition: PatternMatch.h:2170
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2755
llvm::LoopBase::getBlocks
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:171
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:354
LoopUtils.h
checkPHIs
static bool checkPHIs(struct FlattenInfo &FI, const TargetTransformInfo *TTI)
Definition: LoopFlatten.cpp:193
FlattenInfo::InnerBranch
BranchInst * InnerBranch
Definition: LoopFlatten.cpp:83
llvm::LoopBase::getExitingBlock
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:49
PatternMatch.h
llvm::Loop::getName
StringRef getName() const
Definition: LoopInfo.h:862
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2662
llvm::Type::getIntegerBitWidth
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:96
CanFlattenLoopPair
static bool CanFlattenLoopPair(struct FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI)
Definition: LoopFlatten.cpp:468
llvm::OverflowResult
OverflowResult
Definition: ValueTracking.h:485
LoopInfo.h
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3086
llvm::HighlightColor::Remark
@ Remark
llvm::Loop::isLoopSimplifyForm
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:471
llvm::cl::opt
Definition: CommandLine.h:1419
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
llvm::PHINode::hasConstantValue
Value * hasConstantValue() const
If the specified PHI node always merges together the same value, return the value,...
Definition: Instructions.cpp:148
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1178
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2281
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:572
RepeatedInstructionThreshold
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"))
checkOverflow
static OverflowResult checkOverflow(struct FlattenInfo &FI, DominatorTree *DT, AssumptionCache *AC)
Definition: LoopFlatten.cpp:429
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:169
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3061
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:440
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
checkOuterLoopInsts
static bool checkOuterLoopInsts(struct FlattenInfo &FI, SmallPtrSetImpl< Instruction * > &IterationInstructions, const TargetTransformInfo *TTI)
Definition: LoopFlatten.cpp:275
FlattenInfo::InnerIncrement
BinaryOperator * InnerIncrement
Definition: LoopFlatten.cpp:81
llvm::OptimizationRemarkEmitter::emit
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Definition: OptimizationRemarkEmitter.cpp:77
llvm::LoopInfo::erase
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:871
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
checkIVUsers
static bool checkIVUsers(struct FlattenInfo &FI)
Definition: LoopFlatten.cpp:333
FlattenInfo::FlattenInfo
FlattenInfo(Loop *OL, Loop *IL)
Definition: LoopFlatten.cpp:91
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:643
llvm::BranchInst::isUnconditional
bool isUnconditional() const
Definition: Instructions.h:3083
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
Compare
QP Compare Ordered outs ins xscmpudp No builtin are required Or llvm fcmp order unorder compare DP QP Compare builtin are required DP Compare
Definition: README_P9.txt:309
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:200
llvm::LoopInfo
Definition: LoopInfo.h:1079
llvm::BinaryOperator
Definition: InstrTypes.h:190
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
llvm::TargetTransformInfo::TCK_SizeAndLatency
@ TCK_SizeAndLatency
The weighted sum of size and latency.
Definition: TargetTransformInfo.h:214
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:747
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:523
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
findLoopComponents
static bool findLoopComponents(Loop *L, SmallPtrSetImpl< Instruction * > &IterationInstructions, PHINode *&InductionPHI, Value *&Limit, BinaryOperator *&Increment, BranchInst *&BackBranch, ScalarEvolution *SE)
Definition: LoopFlatten.cpp:96
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:295
llvm::BasicBlock::getTerminator
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
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:92
llvm::LoopFlattenPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopFlatten.cpp:673
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
WidenIV
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"))
llvm::InductionDescriptor::isInductionPHI
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.
Definition: IVDescriptors.cpp:1147
Verifier.h
llvm::ScalarEvolution::forgetLoop
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...
Definition: ScalarEvolution.cpp:7084
llvm::TargetTransformInfo::getUserCost
int getUserCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const
Estimate the cost of a given IR user when lowered.
Definition: TargetTransformInfo.cpp:222
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
FlattenInfo::InnerPHIsToTransform
SmallPtrSet< PHINode *, 4 > InnerPHIsToTransform
Definition: LoopFlatten.cpp:86
Function.h
llvm::initializeLoopFlattenLegacyPassPass
void initializeLoopFlattenLegacyPassPass(PassRegistry &)
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::OverflowResult::AlwaysOverflowsHigh
@ AlwaysOverflowsHigh
Always overflows in the direction of signed/unsigned max value.
llvm::PatternMatch::m_c_Mul
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.
Definition: PatternMatch.h:2177
WidenIV
Definition: SimplifyIndVar.cpp:977
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:249
llvm::OptimizationRemark
Diagnostic information for applied optimization remarks.
Definition: DiagnosticInfo.h:684
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:191
FlattenLoopPair
static bool FlattenLoopPair(struct FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI)
Definition: LoopFlatten.cpp:625
llvm::PatternMatch::m_Specific
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:758
Dominators.h
CreateMul
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Definition: Reassociate.cpp:246
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
FlattenInfo
Definition: LoopFlatten.cpp:74
TargetTransformInfo.h
llvm::createLoopFlattenPass
FunctionPass * createLoopFlattenPass()
Definition: LoopFlatten.cpp:718
llvm::PHINode
Definition: Instructions.h:2572
llvm::PatternMatch
Definition: PatternMatch.h:47
llvm::SmallPtrSetImpl< Instruction * >
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:43
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
CanWidenIV
static bool CanWidenIV(struct FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI)
Definition: LoopFlatten.cpp:575
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
Flatten
bool Flatten(DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, TargetTransformInfo *TTI)
Definition: LoopFlatten.cpp:660
llvm::cl::desc
Definition: CommandLine.h:411
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3005
raw_ostream.h
llvm::PatternMatch::m_Trunc
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
Definition: PatternMatch.h:1572
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:424
llvm::DominatorTreeBase::deleteEdge
void deleteEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge deletion and update the tree.
Definition: GenericDomTree.h:602
FlattenInfo::InnerLoop
Loop * InnerLoop
Definition: LoopFlatten.cpp:76
loops
loop Flattens loops
Definition: LoopFlatten.cpp:715
FlattenInfo::OuterLimit
Value * OuterLimit
Definition: LoopFlatten.cpp:80
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3084
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3098
SimplifyIndVar.h
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1224
llvm::SmallPtrSetImpl::insert
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
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37