LLVM  9.0.0svn
LoopRerollPass.cpp
Go to the documentation of this file.
1 //===- LoopReroll.cpp - Loop rerolling 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 implements a simple loop reroller.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/ADT/APInt.h"
14 #include "llvm/ADT/BitVector.h"
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/DenseSet.h"
17 #include "llvm/ADT/MapVector.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/Statistic.h"
24 #include "llvm/Analysis/LoopInfo.h"
25 #include "llvm/Analysis/LoopPass.h"
32 #include "llvm/IR/BasicBlock.h"
33 #include "llvm/IR/Constants.h"
34 #include "llvm/IR/DataLayout.h"
35 #include "llvm/IR/DerivedTypes.h"
36 #include "llvm/IR/Dominators.h"
37 #include "llvm/IR/IRBuilder.h"
38 #include "llvm/IR/InstrTypes.h"
39 #include "llvm/IR/Instruction.h"
40 #include "llvm/IR/Instructions.h"
41 #include "llvm/IR/IntrinsicInst.h"
42 #include "llvm/IR/Intrinsics.h"
43 #include "llvm/IR/Module.h"
44 #include "llvm/IR/Type.h"
45 #include "llvm/IR/Use.h"
46 #include "llvm/IR/User.h"
47 #include "llvm/IR/Value.h"
48 #include "llvm/Pass.h"
49 #include "llvm/Support/Casting.h"
51 #include "llvm/Support/Debug.h"
53 #include "llvm/Transforms/Scalar.h"
54 #include "llvm/Transforms/Utils.h"
57 #include <cassert>
58 #include <cstddef>
59 #include <cstdint>
60 #include <cstdlib>
61 #include <iterator>
62 #include <map>
63 #include <utility>
64 
65 using namespace llvm;
66 
67 #define DEBUG_TYPE "loop-reroll"
68 
69 STATISTIC(NumRerolledLoops, "Number of rerolled loops");
70 
71 static cl::opt<unsigned>
72 NumToleratedFailedMatches("reroll-num-tolerated-failed-matches", cl::init(400),
73  cl::Hidden,
74  cl::desc("The maximum number of failures to tolerate"
75  " during fuzzy matching. (default: 400)"));
76 
77 // This loop re-rolling transformation aims to transform loops like this:
78 //
79 // int foo(int a);
80 // void bar(int *x) {
81 // for (int i = 0; i < 500; i += 3) {
82 // foo(i);
83 // foo(i+1);
84 // foo(i+2);
85 // }
86 // }
87 //
88 // into a loop like this:
89 //
90 // void bar(int *x) {
91 // for (int i = 0; i < 500; ++i)
92 // foo(i);
93 // }
94 //
95 // It does this by looking for loops that, besides the latch code, are composed
96 // of isomorphic DAGs of instructions, with each DAG rooted at some increment
97 // to the induction variable, and where each DAG is isomorphic to the DAG
98 // rooted at the induction variable (excepting the sub-DAGs which root the
99 // other induction-variable increments). In other words, we're looking for loop
100 // bodies of the form:
101 //
102 // %iv = phi [ (preheader, ...), (body, %iv.next) ]
103 // f(%iv)
104 // %iv.1 = add %iv, 1 <-- a root increment
105 // f(%iv.1)
106 // %iv.2 = add %iv, 2 <-- a root increment
107 // f(%iv.2)
108 // %iv.scale_m_1 = add %iv, scale-1 <-- a root increment
109 // f(%iv.scale_m_1)
110 // ...
111 // %iv.next = add %iv, scale
112 // %cmp = icmp(%iv, ...)
113 // br %cmp, header, exit
114 //
115 // where each f(i) is a set of instructions that, collectively, are a function
116 // only of i (and other loop-invariant values).
117 //
118 // As a special case, we can also reroll loops like this:
119 //
120 // int foo(int);
121 // void bar(int *x) {
122 // for (int i = 0; i < 500; ++i) {
123 // x[3*i] = foo(0);
124 // x[3*i+1] = foo(0);
125 // x[3*i+2] = foo(0);
126 // }
127 // }
128 //
129 // into this:
130 //
131 // void bar(int *x) {
132 // for (int i = 0; i < 1500; ++i)
133 // x[i] = foo(0);
134 // }
135 //
136 // in which case, we're looking for inputs like this:
137 //
138 // %iv = phi [ (preheader, ...), (body, %iv.next) ]
139 // %scaled.iv = mul %iv, scale
140 // f(%scaled.iv)
141 // %scaled.iv.1 = add %scaled.iv, 1
142 // f(%scaled.iv.1)
143 // %scaled.iv.2 = add %scaled.iv, 2
144 // f(%scaled.iv.2)
145 // %scaled.iv.scale_m_1 = add %scaled.iv, scale-1
146 // f(%scaled.iv.scale_m_1)
147 // ...
148 // %iv.next = add %iv, 1
149 // %cmp = icmp(%iv, ...)
150 // br %cmp, header, exit
151 
152 namespace {
153 
155  /// The maximum number of iterations that we'll try and reroll.
156  IL_MaxRerollIterations = 32,
157  /// The bitvector index used by loop induction variables and other
158  /// instructions that belong to all iterations.
159  IL_All,
160  IL_End
161  };
162 
163  class LoopReroll : public LoopPass {
164  public:
165  static char ID; // Pass ID, replacement for typeid
166 
167  LoopReroll() : LoopPass(ID) {
169  }
170 
171  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
172 
173  void getAnalysisUsage(AnalysisUsage &AU) const override {
176  }
177 
178  protected:
179  AliasAnalysis *AA;
180  LoopInfo *LI;
181  ScalarEvolution *SE;
182  TargetLibraryInfo *TLI;
183  DominatorTree *DT;
184  bool PreserveLCSSA;
185 
186  using SmallInstructionVector = SmallVector<Instruction *, 16>;
187  using SmallInstructionSet = SmallPtrSet<Instruction *, 16>;
188 
189  // Map between induction variable and its increment
191 
192  // For loop with multiple induction variable, remember the one used only to
193  // control the loop.
194  Instruction *LoopControlIV;
195 
196  // A chain of isomorphic instructions, identified by a single-use PHI
197  // representing a reduction. Only the last value may be used outside the
198  // loop.
199  struct SimpleLoopReduction {
200  SimpleLoopReduction(Instruction *P, Loop *L) : Instructions(1, P) {
201  assert(isa<PHINode>(P) && "First reduction instruction must be a PHI");
202  add(L);
203  }
204 
205  bool valid() const {
206  return Valid;
207  }
208 
209  Instruction *getPHI() const {
210  assert(Valid && "Using invalid reduction");
211  return Instructions.front();
212  }
213 
214  Instruction *getReducedValue() const {
215  assert(Valid && "Using invalid reduction");
216  return Instructions.back();
217  }
218 
219  Instruction *get(size_t i) const {
220  assert(Valid && "Using invalid reduction");
221  return Instructions[i+1];
222  }
223 
224  Instruction *operator [] (size_t i) const { return get(i); }
225 
226  // The size, ignoring the initial PHI.
227  size_t size() const {
228  assert(Valid && "Using invalid reduction");
229  return Instructions.size()-1;
230  }
231 
232  using iterator = SmallInstructionVector::iterator;
233  using const_iterator = SmallInstructionVector::const_iterator;
234 
235  iterator begin() {
236  assert(Valid && "Using invalid reduction");
237  return std::next(Instructions.begin());
238  }
239 
240  const_iterator begin() const {
241  assert(Valid && "Using invalid reduction");
242  return std::next(Instructions.begin());
243  }
244 
245  iterator end() { return Instructions.end(); }
246  const_iterator end() const { return Instructions.end(); }
247 
248  protected:
249  bool Valid = false;
250  SmallInstructionVector Instructions;
251 
252  void add(Loop *L);
253  };
254 
255  // The set of all reductions, and state tracking of possible reductions
256  // during loop instruction processing.
257  struct ReductionTracker {
258  using SmallReductionVector = SmallVector<SimpleLoopReduction, 16>;
259 
260  // Add a new possible reduction.
261  void addSLR(SimpleLoopReduction &SLR) { PossibleReds.push_back(SLR); }
262 
263  // Setup to track possible reductions corresponding to the provided
264  // rerolling scale. Only reductions with a number of non-PHI instructions
265  // that is divisible by the scale are considered. Three instructions sets
266  // are filled in:
267  // - A set of all possible instructions in eligible reductions.
268  // - A set of all PHIs in eligible reductions
269  // - A set of all reduced values (last instructions) in eligible
270  // reductions.
271  void restrictToScale(uint64_t Scale,
272  SmallInstructionSet &PossibleRedSet,
273  SmallInstructionSet &PossibleRedPHISet,
274  SmallInstructionSet &PossibleRedLastSet) {
275  PossibleRedIdx.clear();
276  PossibleRedIter.clear();
277  Reds.clear();
278 
279  for (unsigned i = 0, e = PossibleReds.size(); i != e; ++i)
280  if (PossibleReds[i].size() % Scale == 0) {
281  PossibleRedLastSet.insert(PossibleReds[i].getReducedValue());
282  PossibleRedPHISet.insert(PossibleReds[i].getPHI());
283 
284  PossibleRedSet.insert(PossibleReds[i].getPHI());
285  PossibleRedIdx[PossibleReds[i].getPHI()] = i;
286  for (Instruction *J : PossibleReds[i]) {
287  PossibleRedSet.insert(J);
288  PossibleRedIdx[J] = i;
289  }
290  }
291  }
292 
293  // The functions below are used while processing the loop instructions.
294 
295  // Are the two instructions both from reductions, and furthermore, from
296  // the same reduction?
297  bool isPairInSame(Instruction *J1, Instruction *J2) {
298  DenseMap<Instruction *, int>::iterator J1I = PossibleRedIdx.find(J1);
299  if (J1I != PossibleRedIdx.end()) {
300  DenseMap<Instruction *, int>::iterator J2I = PossibleRedIdx.find(J2);
301  if (J2I != PossibleRedIdx.end() && J1I->second == J2I->second)
302  return true;
303  }
304 
305  return false;
306  }
307 
308  // The two provided instructions, the first from the base iteration, and
309  // the second from iteration i, form a matched pair. If these are part of
310  // a reduction, record that fact.
311  void recordPair(Instruction *J1, Instruction *J2, unsigned i) {
312  if (PossibleRedIdx.count(J1)) {
313  assert(PossibleRedIdx.count(J2) &&
314  "Recording reduction vs. non-reduction instruction?");
315 
316  PossibleRedIter[J1] = 0;
317  PossibleRedIter[J2] = i;
318 
319  int Idx = PossibleRedIdx[J1];
320  assert(Idx == PossibleRedIdx[J2] &&
321  "Recording pair from different reductions?");
322  Reds.insert(Idx);
323  }
324  }
325 
326  // The functions below can be called after we've finished processing all
327  // instructions in the loop, and we know which reductions were selected.
328 
329  bool validateSelected();
330  void replaceSelected();
331 
332  protected:
333  // The vector of all possible reductions (for any scale).
334  SmallReductionVector PossibleReds;
335 
336  DenseMap<Instruction *, int> PossibleRedIdx;
337  DenseMap<Instruction *, int> PossibleRedIter;
338  DenseSet<int> Reds;
339  };
340 
341  // A DAGRootSet models an induction variable being used in a rerollable
342  // loop. For example,
343  //
344  // x[i*3+0] = y1
345  // x[i*3+1] = y2
346  // x[i*3+2] = y3
347  //
348  // Base instruction -> i*3
349  // +---+----+
350  // / | \
351  // ST[y1] +1 +2 <-- Roots
352  // | |
353  // ST[y2] ST[y3]
354  //
355  // There may be multiple DAGRoots, for example:
356  //
357  // x[i*2+0] = ... (1)
358  // x[i*2+1] = ... (1)
359  // x[i*2+4] = ... (2)
360  // x[i*2+5] = ... (2)
361  // x[(i+1234)*2+5678] = ... (3)
362  // x[(i+1234)*2+5679] = ... (3)
363  //
364  // The loop will be rerolled by adding a new loop induction variable,
365  // one for the Base instruction in each DAGRootSet.
366  //
367  struct DAGRootSet {
368  Instruction *BaseInst;
369  SmallInstructionVector Roots;
370 
371  // The instructions between IV and BaseInst (but not including BaseInst).
372  SmallInstructionSet SubsumedInsts;
373  };
374 
375  // The set of all DAG roots, and state tracking of all roots
376  // for a particular induction variable.
377  struct DAGRootTracker {
378  DAGRootTracker(LoopReroll *Parent, Loop *L, Instruction *IV,
381  bool PreserveLCSSA,
383  Instruction *LoopCtrlIV)
384  : Parent(Parent), L(L), SE(SE), AA(AA), TLI(TLI), DT(DT), LI(LI),
385  PreserveLCSSA(PreserveLCSSA), IV(IV), IVToIncMap(IncrMap),
386  LoopControlIV(LoopCtrlIV) {}
387 
388  /// Stage 1: Find all the DAG roots for the induction variable.
389  bool findRoots();
390 
391  /// Stage 2: Validate if the found roots are valid.
392  bool validate(ReductionTracker &Reductions);
393 
394  /// Stage 3: Assuming validate() returned true, perform the
395  /// replacement.
396  /// @param BackedgeTakenCount The backedge-taken count of L.
397  void replace(const SCEV *BackedgeTakenCount);
398 
399  protected:
401 
402  void findRootsRecursive(Instruction *IVU,
403  SmallInstructionSet SubsumedInsts);
404  bool findRootsBase(Instruction *IVU, SmallInstructionSet SubsumedInsts);
405  bool collectPossibleRoots(Instruction *Base,
406  std::map<int64_t,Instruction*> &Roots);
407  bool validateRootSet(DAGRootSet &DRS);
408 
409  bool collectUsedInstructions(SmallInstructionSet &PossibleRedSet);
410  void collectInLoopUserSet(const SmallInstructionVector &Roots,
411  const SmallInstructionSet &Exclude,
412  const SmallInstructionSet &Final,
414  void collectInLoopUserSet(Instruction *Root,
415  const SmallInstructionSet &Exclude,
416  const SmallInstructionSet &Final,
417  DenseSet<Instruction *> &Users);
418 
419  UsesTy::iterator nextInstr(int Val, UsesTy &In,
420  const SmallInstructionSet &Exclude,
421  UsesTy::iterator *StartI=nullptr);
422  bool isBaseInst(Instruction *I);
423  bool isRootInst(Instruction *I);
424  bool instrDependsOn(Instruction *I,
425  UsesTy::iterator Start,
426  UsesTy::iterator End);
427  void replaceIV(DAGRootSet &DRS, const SCEV *Start, const SCEV *IncrExpr);
428 
429  LoopReroll *Parent;
430 
431  // Members of Parent, replicated here for brevity.
432  Loop *L;
433  ScalarEvolution *SE;
434  AliasAnalysis *AA;
435  TargetLibraryInfo *TLI;
436  DominatorTree *DT;
437  LoopInfo *LI;
438  bool PreserveLCSSA;
439 
440  // The loop induction variable.
441  Instruction *IV;
442 
443  // Loop step amount.
444  int64_t Inc;
445 
446  // Loop reroll count; if Inc == 1, this records the scaling applied
447  // to the indvar: a[i*2+0] = ...; a[i*2+1] = ... ;
448  // If Inc is not 1, Scale = Inc.
449  uint64_t Scale;
450 
451  // The roots themselves.
453 
454  // All increment instructions for IV.
455  SmallInstructionVector LoopIncs;
456 
457  // Map of all instructions in the loop (in order) to the iterations
458  // they are used in (or specially, IL_All for instructions
459  // used in the loop increment mechanism).
460  UsesTy Uses;
461 
462  // Map between induction variable and its increment
464 
465  Instruction *LoopControlIV;
466  };
467 
468  // Check if it is a compare-like instruction whose user is a branch
469  bool isCompareUsedByBranch(Instruction *I) {
470  auto *TI = I->getParent()->getTerminator();
471  if (!isa<BranchInst>(TI) || !isa<CmpInst>(I))
472  return false;
473  return I->hasOneUse() && TI->getOperand(0) == I;
474  };
475 
476  bool isLoopControlIV(Loop *L, Instruction *IV);
477  void collectPossibleIVs(Loop *L, SmallInstructionVector &PossibleIVs);
478  void collectPossibleReductions(Loop *L,
479  ReductionTracker &Reductions);
480  bool reroll(Instruction *IV, Loop *L, BasicBlock *Header,
481  const SCEV *BackedgeTakenCount, ReductionTracker &Reductions);
482  };
483 
484 } // end anonymous namespace
485 
486 char LoopReroll::ID = 0;
487 
488 INITIALIZE_PASS_BEGIN(LoopReroll, "loop-reroll", "Reroll loops", false, false)
491 INITIALIZE_PASS_END(LoopReroll, "loop-reroll", "Reroll loops", false, false)
492 
494  return new LoopReroll;
495 }
496 
497 // Returns true if the provided instruction is used outside the given loop.
498 // This operates like Instruction::isUsedOutsideOfBlock, but considers PHIs in
499 // non-loop blocks to be outside the loop.
501  for (User *U : I->users()) {
502  if (!L->contains(cast<Instruction>(U)))
503  return true;
504  }
505  return false;
506 }
507 
508 // Check if an IV is only used to control the loop. There are two cases:
509 // 1. It only has one use which is loop increment, and the increment is only
510 // used by comparison and the PHI (could has sext with nsw in between), and the
511 // comparison is only used by branch.
512 // 2. It is used by loop increment and the comparison, the loop increment is
513 // only used by the PHI, and the comparison is used only by the branch.
514 bool LoopReroll::isLoopControlIV(Loop *L, Instruction *IV) {
515  unsigned IVUses = IV->getNumUses();
516  if (IVUses != 2 && IVUses != 1)
517  return false;
518 
519  for (auto *User : IV->users()) {
520  int32_t IncOrCmpUses = User->getNumUses();
521  bool IsCompInst = isCompareUsedByBranch(cast<Instruction>(User));
522 
523  // User can only have one or two uses.
524  if (IncOrCmpUses != 2 && IncOrCmpUses != 1)
525  return false;
526 
527  // Case 1
528  if (IVUses == 1) {
529  // The only user must be the loop increment.
530  // The loop increment must have two uses.
531  if (IsCompInst || IncOrCmpUses != 2)
532  return false;
533  }
534 
535  // Case 2
536  if (IVUses == 2 && IncOrCmpUses != 1)
537  return false;
538 
539  // The users of the IV must be a binary operation or a comparison
540  if (auto *BO = dyn_cast<BinaryOperator>(User)) {
541  if (BO->getOpcode() == Instruction::Add) {
542  // Loop Increment
543  // User of Loop Increment should be either PHI or CMP
544  for (auto *UU : User->users()) {
545  if (PHINode *PN = dyn_cast<PHINode>(UU)) {
546  if (PN != IV)
547  return false;
548  }
549  // Must be a CMP or an ext (of a value with nsw) then CMP
550  else {
551  Instruction *UUser = dyn_cast<Instruction>(UU);
552  // Skip SExt if we are extending an nsw value
553  // TODO: Allow ZExt too
554  if (BO->hasNoSignedWrap() && UUser && UUser->hasOneUse() &&
555  isa<SExtInst>(UUser))
556  UUser = dyn_cast<Instruction>(*(UUser->user_begin()));
557  if (!isCompareUsedByBranch(UUser))
558  return false;
559  }
560  }
561  } else
562  return false;
563  // Compare : can only have one use, and must be branch
564  } else if (!IsCompInst)
565  return false;
566  }
567  return true;
568 }
569 
570 // Collect the list of loop induction variables with respect to which it might
571 // be possible to reroll the loop.
572 void LoopReroll::collectPossibleIVs(Loop *L,
573  SmallInstructionVector &PossibleIVs) {
574  BasicBlock *Header = L->getHeader();
575  for (BasicBlock::iterator I = Header->begin(),
576  IE = Header->getFirstInsertionPt(); I != IE; ++I) {
577  if (!isa<PHINode>(I))
578  continue;
579  if (!I->getType()->isIntegerTy() && !I->getType()->isPointerTy())
580  continue;
581 
582  if (const SCEVAddRecExpr *PHISCEV =
583  dyn_cast<SCEVAddRecExpr>(SE->getSCEV(&*I))) {
584  if (PHISCEV->getLoop() != L)
585  continue;
586  if (!PHISCEV->isAffine())
587  continue;
588  auto IncSCEV = dyn_cast<SCEVConstant>(PHISCEV->getStepRecurrence(*SE));
589  if (IncSCEV) {
590  IVToIncMap[&*I] = IncSCEV->getValue()->getSExtValue();
591  LLVM_DEBUG(dbgs() << "LRR: Possible IV: " << *I << " = " << *PHISCEV
592  << "\n");
593 
594  if (isLoopControlIV(L, &*I)) {
595  assert(!LoopControlIV && "Found two loop control only IV");
596  LoopControlIV = &(*I);
597  LLVM_DEBUG(dbgs() << "LRR: Possible loop control only IV: " << *I
598  << " = " << *PHISCEV << "\n");
599  } else
600  PossibleIVs.push_back(&*I);
601  }
602  }
603  }
604 }
605 
606 // Add the remainder of the reduction-variable chain to the instruction vector
607 // (the initial PHINode has already been added). If successful, the object is
608 // marked as valid.
610  assert(!Valid && "Cannot add to an already-valid chain");
611 
612  // The reduction variable must be a chain of single-use instructions
613  // (including the PHI), except for the last value (which is used by the PHI
614  // and also outside the loop).
615  Instruction *C = Instructions.front();
616  if (C->user_empty())
617  return;
618 
619  do {
620  C = cast<Instruction>(*C->user_begin());
621  if (C->hasOneUse()) {
622  if (!C->isBinaryOp())
623  return;
624 
625  if (!(isa<PHINode>(Instructions.back()) ||
626  C->isSameOperationAs(Instructions.back())))
627  return;
628 
629  Instructions.push_back(C);
630  }
631  } while (C->hasOneUse());
632 
633  if (Instructions.size() < 2 ||
634  !C->isSameOperationAs(Instructions.back()) ||
635  C->use_empty())
636  return;
637 
638  // C is now the (potential) last instruction in the reduction chain.
639  for (User *U : C->users()) {
640  // The only in-loop user can be the initial PHI.
641  if (L->contains(cast<Instruction>(U)))
642  if (cast<Instruction>(U) != Instructions.front())
643  return;
644  }
645 
646  Instructions.push_back(C);
647  Valid = true;
648 }
649 
650 // Collect the vector of possible reduction variables.
651 void LoopReroll::collectPossibleReductions(Loop *L,
652  ReductionTracker &Reductions) {
653  BasicBlock *Header = L->getHeader();
654  for (BasicBlock::iterator I = Header->begin(),
655  IE = Header->getFirstInsertionPt(); I != IE; ++I) {
656  if (!isa<PHINode>(I))
657  continue;
658  if (!I->getType()->isSingleValueType())
659  continue;
660 
661  SimpleLoopReduction SLR(&*I, L);
662  if (!SLR.valid())
663  continue;
664 
665  LLVM_DEBUG(dbgs() << "LRR: Possible reduction: " << *I << " (with "
666  << SLR.size() << " chained instructions)\n");
667  Reductions.addSLR(SLR);
668  }
669 }
670 
671 // Collect the set of all users of the provided root instruction. This set of
672 // users contains not only the direct users of the root instruction, but also
673 // all users of those users, and so on. There are two exceptions:
674 //
675 // 1. Instructions in the set of excluded instructions are never added to the
676 // use set (even if they are users). This is used, for example, to exclude
677 // including root increments in the use set of the primary IV.
678 //
679 // 2. Instructions in the set of final instructions are added to the use set
680 // if they are users, but their users are not added. This is used, for
681 // example, to prevent a reduction update from forcing all later reduction
682 // updates into the use set.
683 void LoopReroll::DAGRootTracker::collectInLoopUserSet(
684  Instruction *Root, const SmallInstructionSet &Exclude,
685  const SmallInstructionSet &Final,
687  SmallInstructionVector Queue(1, Root);
688  while (!Queue.empty()) {
689  Instruction *I = Queue.pop_back_val();
690  if (!Users.insert(I).second)
691  continue;
692 
693  if (!Final.count(I))
694  for (Use &U : I->uses()) {
695  Instruction *User = cast<Instruction>(U.getUser());
696  if (PHINode *PN = dyn_cast<PHINode>(User)) {
697  // Ignore "wrap-around" uses to PHIs of this loop's header.
698  if (PN->getIncomingBlock(U) == L->getHeader())
699  continue;
700  }
701 
702  if (L->contains(User) && !Exclude.count(User)) {
703  Queue.push_back(User);
704  }
705  }
706 
707  // We also want to collect single-user "feeder" values.
708  for (User::op_iterator OI = I->op_begin(),
709  OIE = I->op_end(); OI != OIE; ++OI) {
710  if (Instruction *Op = dyn_cast<Instruction>(*OI))
711  if (Op->hasOneUse() && L->contains(Op) && !Exclude.count(Op) &&
712  !Final.count(Op))
713  Queue.push_back(Op);
714  }
715  }
716 }
717 
718 // Collect all of the users of all of the provided root instructions (combined
719 // into a single set).
720 void LoopReroll::DAGRootTracker::collectInLoopUserSet(
721  const SmallInstructionVector &Roots,
722  const SmallInstructionSet &Exclude,
723  const SmallInstructionSet &Final,
724  DenseSet<Instruction *> &Users) {
725  for (Instruction *Root : Roots)
726  collectInLoopUserSet(Root, Exclude, Final, Users);
727 }
728 
730  if (LoadInst *LI = dyn_cast<LoadInst>(I))
731  return LI->isUnordered();
732  if (StoreInst *SI = dyn_cast<StoreInst>(I))
733  return SI->isUnordered();
734  if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I))
735  return !MI->isVolatile();
736  return false;
737 }
738 
739 /// Return true if IVU is a "simple" arithmetic operation.
740 /// This is used for narrowing the search space for DAGRoots; only arithmetic
741 /// and GEPs can be part of a DAGRoot.
742 static bool isSimpleArithmeticOp(User *IVU) {
743  if (Instruction *I = dyn_cast<Instruction>(IVU)) {
744  switch (I->getOpcode()) {
745  default: return false;
746  case Instruction::Add:
747  case Instruction::Sub:
748  case Instruction::Mul:
749  case Instruction::Shl:
750  case Instruction::AShr:
751  case Instruction::LShr:
752  case Instruction::GetElementPtr:
753  case Instruction::Trunc:
754  case Instruction::ZExt:
755  case Instruction::SExt:
756  return true;
757  }
758  }
759  return false;
760 }
761 
762 static bool isLoopIncrement(User *U, Instruction *IV) {
764 
765  if ((BO && BO->getOpcode() != Instruction::Add) ||
766  (!BO && !isa<GetElementPtrInst>(U)))
767  return false;
768 
769  for (auto *UU : U->users()) {
770  PHINode *PN = dyn_cast<PHINode>(UU);
771  if (PN && PN == IV)
772  return true;
773  }
774  return false;
775 }
776 
777 bool LoopReroll::DAGRootTracker::
778 collectPossibleRoots(Instruction *Base, std::map<int64_t,Instruction*> &Roots) {
779  SmallInstructionVector BaseUsers;
780 
781  for (auto *I : Base->users()) {
782  ConstantInt *CI = nullptr;
783 
784  if (isLoopIncrement(I, IV)) {
785  LoopIncs.push_back(cast<Instruction>(I));
786  continue;
787  }
788 
789  // The root nodes must be either GEPs, ORs or ADDs.
790  if (auto *BO = dyn_cast<BinaryOperator>(I)) {
791  if (BO->getOpcode() == Instruction::Add ||
792  BO->getOpcode() == Instruction::Or)
793  CI = dyn_cast<ConstantInt>(BO->getOperand(1));
794  } else if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
795  Value *LastOperand = GEP->getOperand(GEP->getNumOperands()-1);
796  CI = dyn_cast<ConstantInt>(LastOperand);
797  }
798 
799  if (!CI) {
800  if (Instruction *II = dyn_cast<Instruction>(I)) {
801  BaseUsers.push_back(II);
802  continue;
803  } else {
804  LLVM_DEBUG(dbgs() << "LRR: Aborting due to non-instruction: " << *I
805  << "\n");
806  return false;
807  }
808  }
809 
810  int64_t V = std::abs(CI->getValue().getSExtValue());
811  if (Roots.find(V) != Roots.end())
812  // No duplicates, please.
813  return false;
814 
815  Roots[V] = cast<Instruction>(I);
816  }
817 
818  // Make sure we have at least two roots.
819  if (Roots.empty() || (Roots.size() == 1 && BaseUsers.empty()))
820  return false;
821 
822  // If we found non-loop-inc, non-root users of Base, assume they are
823  // for the zeroth root index. This is because "add %a, 0" gets optimized
824  // away.
825  if (BaseUsers.size()) {
826  if (Roots.find(0) != Roots.end()) {
827  LLVM_DEBUG(dbgs() << "LRR: Multiple roots found for base - aborting!\n");
828  return false;
829  }
830  Roots[0] = Base;
831  }
832 
833  // Calculate the number of users of the base, or lowest indexed, iteration.
834  unsigned NumBaseUses = BaseUsers.size();
835  if (NumBaseUses == 0)
836  NumBaseUses = Roots.begin()->second->getNumUses();
837 
838  // Check that every node has the same number of users.
839  for (auto &KV : Roots) {
840  if (KV.first == 0)
841  continue;
842  if (!KV.second->hasNUses(NumBaseUses)) {
843  LLVM_DEBUG(dbgs() << "LRR: Aborting - Root and Base #users not the same: "
844  << "#Base=" << NumBaseUses
845  << ", #Root=" << KV.second->getNumUses() << "\n");
846  return false;
847  }
848  }
849 
850  return true;
851 }
852 
853 void LoopReroll::DAGRootTracker::
854 findRootsRecursive(Instruction *I, SmallInstructionSet SubsumedInsts) {
855  // Does the user look like it could be part of a root set?
856  // All its users must be simple arithmetic ops.
857  if (I->hasNUsesOrMore(IL_MaxRerollIterations + 1))
858  return;
859 
860  if (I != IV && findRootsBase(I, SubsumedInsts))
861  return;
862 
863  SubsumedInsts.insert(I);
864 
865  for (User *V : I->users()) {
866  Instruction *I = cast<Instruction>(V);
867  if (is_contained(LoopIncs, I))
868  continue;
869 
870  if (!isSimpleArithmeticOp(I))
871  continue;
872 
873  // The recursive call makes a copy of SubsumedInsts.
874  findRootsRecursive(I, SubsumedInsts);
875  }
876 }
877 
878 bool LoopReroll::DAGRootTracker::validateRootSet(DAGRootSet &DRS) {
879  if (DRS.Roots.empty())
880  return false;
881 
882  // Consider a DAGRootSet with N-1 roots (so N different values including
883  // BaseInst).
884  // Define d = Roots[0] - BaseInst, which should be the same as
885  // Roots[I] - Roots[I-1] for all I in [1..N).
886  // Define D = BaseInst@J - BaseInst@J-1, where "@J" means the value at the
887  // loop iteration J.
888  //
889  // Now, For the loop iterations to be consecutive:
890  // D = d * N
891  const auto *ADR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(DRS.BaseInst));
892  if (!ADR)
893  return false;
894 
895  // Check that the first root is evenly spaced.
896  unsigned N = DRS.Roots.size() + 1;
897  const SCEV *StepSCEV = SE->getMinusSCEV(SE->getSCEV(DRS.Roots[0]), ADR);
898  const SCEV *ScaleSCEV = SE->getConstant(StepSCEV->getType(), N);
899  if (ADR->getStepRecurrence(*SE) != SE->getMulExpr(StepSCEV, ScaleSCEV))
900  return false;
901 
902  // Check that the remainling roots are evenly spaced.
903  for (unsigned i = 1; i < N - 1; ++i) {
904  const SCEV *NewStepSCEV = SE->getMinusSCEV(SE->getSCEV(DRS.Roots[i]),
905  SE->getSCEV(DRS.Roots[i-1]));
906  if (NewStepSCEV != StepSCEV)
907  return false;
908  }
909 
910  return true;
911 }
912 
913 bool LoopReroll::DAGRootTracker::
914 findRootsBase(Instruction *IVU, SmallInstructionSet SubsumedInsts) {
915  // The base of a RootSet must be an AddRec, so it can be erased.
916  const auto *IVU_ADR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(IVU));
917  if (!IVU_ADR || IVU_ADR->getLoop() != L)
918  return false;
919 
920  std::map<int64_t, Instruction*> V;
921  if (!collectPossibleRoots(IVU, V))
922  return false;
923 
924  // If we didn't get a root for index zero, then IVU must be
925  // subsumed.
926  if (V.find(0) == V.end())
927  SubsumedInsts.insert(IVU);
928 
929  // Partition the vector into monotonically increasing indexes.
930  DAGRootSet DRS;
931  DRS.BaseInst = nullptr;
932 
933  SmallVector<DAGRootSet, 16> PotentialRootSets;
934 
935  for (auto &KV : V) {
936  if (!DRS.BaseInst) {
937  DRS.BaseInst = KV.second;
938  DRS.SubsumedInsts = SubsumedInsts;
939  } else if (DRS.Roots.empty()) {
940  DRS.Roots.push_back(KV.second);
941  } else if (V.find(KV.first - 1) != V.end()) {
942  DRS.Roots.push_back(KV.second);
943  } else {
944  // Linear sequence terminated.
945  if (!validateRootSet(DRS))
946  return false;
947 
948  // Construct a new DAGRootSet with the next sequence.
949  PotentialRootSets.push_back(DRS);
950  DRS.BaseInst = KV.second;
951  DRS.Roots.clear();
952  }
953  }
954 
955  if (!validateRootSet(DRS))
956  return false;
957 
958  PotentialRootSets.push_back(DRS);
959 
960  RootSets.append(PotentialRootSets.begin(), PotentialRootSets.end());
961 
962  return true;
963 }
964 
965 bool LoopReroll::DAGRootTracker::findRoots() {
966  Inc = IVToIncMap[IV];
967 
968  assert(RootSets.empty() && "Unclean state!");
969  if (std::abs(Inc) == 1) {
970  for (auto *IVU : IV->users()) {
971  if (isLoopIncrement(IVU, IV))
972  LoopIncs.push_back(cast<Instruction>(IVU));
973  }
974  findRootsRecursive(IV, SmallInstructionSet());
975  LoopIncs.push_back(IV);
976  } else {
977  if (!findRootsBase(IV, SmallInstructionSet()))
978  return false;
979  }
980 
981  // Ensure all sets have the same size.
982  if (RootSets.empty()) {
983  LLVM_DEBUG(dbgs() << "LRR: Aborting because no root sets found!\n");
984  return false;
985  }
986  for (auto &V : RootSets) {
987  if (V.Roots.empty() || V.Roots.size() != RootSets[0].Roots.size()) {
988  LLVM_DEBUG(
989  dbgs()
990  << "LRR: Aborting because not all root sets have the same size\n");
991  return false;
992  }
993  }
994 
995  Scale = RootSets[0].Roots.size() + 1;
996 
997  if (Scale > IL_MaxRerollIterations) {
998  LLVM_DEBUG(dbgs() << "LRR: Aborting - too many iterations found. "
999  << "#Found=" << Scale
1000  << ", #Max=" << IL_MaxRerollIterations << "\n");
1001  return false;
1002  }
1003 
1004  LLVM_DEBUG(dbgs() << "LRR: Successfully found roots: Scale=" << Scale
1005  << "\n");
1006 
1007  return true;
1008 }
1009 
1010 bool LoopReroll::DAGRootTracker::collectUsedInstructions(SmallInstructionSet &PossibleRedSet) {
1011  // Populate the MapVector with all instructions in the block, in order first,
1012  // so we can iterate over the contents later in perfect order.
1013  for (auto &I : *L->getHeader()) {
1014  Uses[&I].resize(IL_End);
1015  }
1016 
1017  SmallInstructionSet Exclude;
1018  for (auto &DRS : RootSets) {
1019  Exclude.insert(DRS.Roots.begin(), DRS.Roots.end());
1020  Exclude.insert(DRS.SubsumedInsts.begin(), DRS.SubsumedInsts.end());
1021  Exclude.insert(DRS.BaseInst);
1022  }
1023  Exclude.insert(LoopIncs.begin(), LoopIncs.end());
1024 
1025  for (auto &DRS : RootSets) {
1026  DenseSet<Instruction*> VBase;
1027  collectInLoopUserSet(DRS.BaseInst, Exclude, PossibleRedSet, VBase);
1028  for (auto *I : VBase) {
1029  Uses[I].set(0);
1030  }
1031 
1032  unsigned Idx = 1;
1033  for (auto *Root : DRS.Roots) {
1035  collectInLoopUserSet(Root, Exclude, PossibleRedSet, V);
1036 
1037  // While we're here, check the use sets are the same size.
1038  if (V.size() != VBase.size()) {
1039  LLVM_DEBUG(dbgs() << "LRR: Aborting - use sets are different sizes\n");
1040  return false;
1041  }
1042 
1043  for (auto *I : V) {
1044  Uses[I].set(Idx);
1045  }
1046  ++Idx;
1047  }
1048 
1049  // Make sure our subsumed instructions are remembered too.
1050  for (auto *I : DRS.SubsumedInsts) {
1051  Uses[I].set(IL_All);
1052  }
1053  }
1054 
1055  // Make sure the loop increments are also accounted for.
1056 
1057  Exclude.clear();
1058  for (auto &DRS : RootSets) {
1059  Exclude.insert(DRS.Roots.begin(), DRS.Roots.end());
1060  Exclude.insert(DRS.SubsumedInsts.begin(), DRS.SubsumedInsts.end());
1061  Exclude.insert(DRS.BaseInst);
1062  }
1063 
1065  collectInLoopUserSet(LoopIncs, Exclude, PossibleRedSet, V);
1066  for (auto *I : V) {
1067  Uses[I].set(IL_All);
1068  }
1069 
1070  return true;
1071 }
1072 
1073 /// Get the next instruction in "In" that is a member of set Val.
1074 /// Start searching from StartI, and do not return anything in Exclude.
1075 /// If StartI is not given, start from In.begin().
1077 LoopReroll::DAGRootTracker::nextInstr(int Val, UsesTy &In,
1078  const SmallInstructionSet &Exclude,
1079  UsesTy::iterator *StartI) {
1080  UsesTy::iterator I = StartI ? *StartI : In.begin();
1081  while (I != In.end() && (I->second.test(Val) == 0 ||
1082  Exclude.count(I->first) != 0))
1083  ++I;
1084  return I;
1085 }
1086 
1087 bool LoopReroll::DAGRootTracker::isBaseInst(Instruction *I) {
1088  for (auto &DRS : RootSets) {
1089  if (DRS.BaseInst == I)
1090  return true;
1091  }
1092  return false;
1093 }
1094 
1095 bool LoopReroll::DAGRootTracker::isRootInst(Instruction *I) {
1096  for (auto &DRS : RootSets) {
1097  if (is_contained(DRS.Roots, I))
1098  return true;
1099  }
1100  return false;
1101 }
1102 
1103 /// Return true if instruction I depends on any instruction between
1104 /// Start and End.
1105 bool LoopReroll::DAGRootTracker::instrDependsOn(Instruction *I,
1106  UsesTy::iterator Start,
1107  UsesTy::iterator End) {
1108  for (auto *U : I->users()) {
1109  for (auto It = Start; It != End; ++It)
1110  if (U == It->first)
1111  return true;
1112  }
1113  return false;
1114 }
1115 
1116 static bool isIgnorableInst(const Instruction *I) {
1117  if (isa<DbgInfoIntrinsic>(I))
1118  return true;
1119  const IntrinsicInst* II = dyn_cast<IntrinsicInst>(I);
1120  if (!II)
1121  return false;
1122  switch (II->getIntrinsicID()) {
1123  default:
1124  return false;
1125  case Intrinsic::annotation:
1126  case Intrinsic::ptr_annotation:
1127  case Intrinsic::var_annotation:
1128  // TODO: the following intrinsics may also be whitelisted:
1129  // lifetime_start, lifetime_end, invariant_start, invariant_end
1130  return true;
1131  }
1132  return false;
1133 }
1134 
1135 bool LoopReroll::DAGRootTracker::validate(ReductionTracker &Reductions) {
1136  // We now need to check for equivalence of the use graph of each root with
1137  // that of the primary induction variable (excluding the roots). Our goal
1138  // here is not to solve the full graph isomorphism problem, but rather to
1139  // catch common cases without a lot of work. As a result, we will assume
1140  // that the relative order of the instructions in each unrolled iteration
1141  // is the same (although we will not make an assumption about how the
1142  // different iterations are intermixed). Note that while the order must be
1143  // the same, the instructions may not be in the same basic block.
1144 
1145  // An array of just the possible reductions for this scale factor. When we
1146  // collect the set of all users of some root instructions, these reduction
1147  // instructions are treated as 'final' (their uses are not considered).
1148  // This is important because we don't want the root use set to search down
1149  // the reduction chain.
1150  SmallInstructionSet PossibleRedSet;
1151  SmallInstructionSet PossibleRedLastSet;
1152  SmallInstructionSet PossibleRedPHISet;
1153  Reductions.restrictToScale(Scale, PossibleRedSet,
1154  PossibleRedPHISet, PossibleRedLastSet);
1155 
1156  // Populate "Uses" with where each instruction is used.
1157  if (!collectUsedInstructions(PossibleRedSet))
1158  return false;
1159 
1160  // Make sure we mark the reduction PHIs as used in all iterations.
1161  for (auto *I : PossibleRedPHISet) {
1162  Uses[I].set(IL_All);
1163  }
1164 
1165  // Make sure we mark loop-control-only PHIs as used in all iterations. See
1166  // comment above LoopReroll::isLoopControlIV for more information.
1167  BasicBlock *Header = L->getHeader();
1168  if (LoopControlIV && LoopControlIV != IV) {
1169  for (auto *U : LoopControlIV->users()) {
1170  Instruction *IVUser = dyn_cast<Instruction>(U);
1171  // IVUser could be loop increment or compare
1172  Uses[IVUser].set(IL_All);
1173  for (auto *UU : IVUser->users()) {
1174  Instruction *UUser = dyn_cast<Instruction>(UU);
1175  // UUser could be compare, PHI or branch
1176  Uses[UUser].set(IL_All);
1177  // Skip SExt
1178  if (isa<SExtInst>(UUser)) {
1179  UUser = dyn_cast<Instruction>(*(UUser->user_begin()));
1180  Uses[UUser].set(IL_All);
1181  }
1182  // Is UUser a compare instruction?
1183  if (UU->hasOneUse()) {
1184  Instruction *BI = dyn_cast<BranchInst>(*UUser->user_begin());
1185  if (BI == cast<BranchInst>(Header->getTerminator()))
1186  Uses[BI].set(IL_All);
1187  }
1188  }
1189  }
1190  }
1191 
1192  // Make sure all instructions in the loop are in one and only one
1193  // set.
1194  for (auto &KV : Uses) {
1195  if (KV.second.count() != 1 && !isIgnorableInst(KV.first)) {
1196  LLVM_DEBUG(
1197  dbgs() << "LRR: Aborting - instruction is not used in 1 iteration: "
1198  << *KV.first << " (#uses=" << KV.second.count() << ")\n");
1199  return false;
1200  }
1201  }
1202 
1203  LLVM_DEBUG(for (auto &KV
1204  : Uses) {
1205  dbgs() << "LRR: " << KV.second.find_first() << "\t" << *KV.first << "\n";
1206  });
1207 
1208  for (unsigned Iter = 1; Iter < Scale; ++Iter) {
1209  // In addition to regular aliasing information, we need to look for
1210  // instructions from later (future) iterations that have side effects
1211  // preventing us from reordering them past other instructions with side
1212  // effects.
1213  bool FutureSideEffects = false;
1214  AliasSetTracker AST(*AA);
1215  // The map between instructions in f(%iv.(i+1)) and f(%iv).
1217 
1218  // Compare iteration Iter to the base.
1219  SmallInstructionSet Visited;
1220  auto BaseIt = nextInstr(0, Uses, Visited);
1221  auto RootIt = nextInstr(Iter, Uses, Visited);
1222  auto LastRootIt = Uses.begin();
1223 
1224  while (BaseIt != Uses.end() && RootIt != Uses.end()) {
1225  Instruction *BaseInst = BaseIt->first;
1226  Instruction *RootInst = RootIt->first;
1227 
1228  // Skip over the IV or root instructions; only match their users.
1229  bool Continue = false;
1230  if (isBaseInst(BaseInst)) {
1231  Visited.insert(BaseInst);
1232  BaseIt = nextInstr(0, Uses, Visited);
1233  Continue = true;
1234  }
1235  if (isRootInst(RootInst)) {
1236  LastRootIt = RootIt;
1237  Visited.insert(RootInst);
1238  RootIt = nextInstr(Iter, Uses, Visited);
1239  Continue = true;
1240  }
1241  if (Continue) continue;
1242 
1243  if (!BaseInst->isSameOperationAs(RootInst)) {
1244  // Last chance saloon. We don't try and solve the full isomorphism
1245  // problem, but try and at least catch the case where two instructions
1246  // *of different types* are round the wrong way. We won't be able to
1247  // efficiently tell, given two ADD instructions, which way around we
1248  // should match them, but given an ADD and a SUB, we can at least infer
1249  // which one is which.
1250  //
1251  // This should allow us to deal with a greater subset of the isomorphism
1252  // problem. It does however change a linear algorithm into a quadratic
1253  // one, so limit the number of probes we do.
1254  auto TryIt = RootIt;
1255  unsigned N = NumToleratedFailedMatches;
1256  while (TryIt != Uses.end() &&
1257  !BaseInst->isSameOperationAs(TryIt->first) &&
1258  N--) {
1259  ++TryIt;
1260  TryIt = nextInstr(Iter, Uses, Visited, &TryIt);
1261  }
1262 
1263  if (TryIt == Uses.end() || TryIt == RootIt ||
1264  instrDependsOn(TryIt->first, RootIt, TryIt)) {
1265  LLVM_DEBUG(dbgs() << "LRR: iteration root match failed at "
1266  << *BaseInst << " vs. " << *RootInst << "\n");
1267  return false;
1268  }
1269 
1270  RootIt = TryIt;
1271  RootInst = TryIt->first;
1272  }
1273 
1274  // All instructions between the last root and this root
1275  // may belong to some other iteration. If they belong to a
1276  // future iteration, then they're dangerous to alias with.
1277  //
1278  // Note that because we allow a limited amount of flexibility in the order
1279  // that we visit nodes, LastRootIt might be *before* RootIt, in which
1280  // case we've already checked this set of instructions so we shouldn't
1281  // do anything.
1282  for (; LastRootIt < RootIt; ++LastRootIt) {
1283  Instruction *I = LastRootIt->first;
1284  if (LastRootIt->second.find_first() < (int)Iter)
1285  continue;
1286  if (I->mayWriteToMemory())
1287  AST.add(I);
1288  // Note: This is specifically guarded by a check on isa<PHINode>,
1289  // which while a valid (somewhat arbitrary) micro-optimization, is
1290  // needed because otherwise isSafeToSpeculativelyExecute returns
1291  // false on PHI nodes.
1292  if (!isa<PHINode>(I) && !isUnorderedLoadStore(I) &&
1294  // Intervening instructions cause side effects.
1295  FutureSideEffects = true;
1296  }
1297 
1298  // Make sure that this instruction, which is in the use set of this
1299  // root instruction, does not also belong to the base set or the set of
1300  // some other root instruction.
1301  if (RootIt->second.count() > 1) {
1302  LLVM_DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInst
1303  << " vs. " << *RootInst << " (prev. case overlap)\n");
1304  return false;
1305  }
1306 
1307  // Make sure that we don't alias with any instruction in the alias set
1308  // tracker. If we do, then we depend on a future iteration, and we
1309  // can't reroll.
1310  if (RootInst->mayReadFromMemory())
1311  for (auto &K : AST) {
1312  if (K.aliasesUnknownInst(RootInst, *AA)) {
1313  LLVM_DEBUG(dbgs() << "LRR: iteration root match failed at "
1314  << *BaseInst << " vs. " << *RootInst
1315  << " (depends on future store)\n");
1316  return false;
1317  }
1318  }
1319 
1320  // If we've past an instruction from a future iteration that may have
1321  // side effects, and this instruction might also, then we can't reorder
1322  // them, and this matching fails. As an exception, we allow the alias
1323  // set tracker to handle regular (unordered) load/store dependencies.
1324  if (FutureSideEffects && ((!isUnorderedLoadStore(BaseInst) &&
1325  !isSafeToSpeculativelyExecute(BaseInst)) ||
1326  (!isUnorderedLoadStore(RootInst) &&
1327  !isSafeToSpeculativelyExecute(RootInst)))) {
1328  LLVM_DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInst
1329  << " vs. " << *RootInst
1330  << " (side effects prevent reordering)\n");
1331  return false;
1332  }
1333 
1334  // For instructions that are part of a reduction, if the operation is
1335  // associative, then don't bother matching the operands (because we
1336  // already know that the instructions are isomorphic, and the order
1337  // within the iteration does not matter). For non-associative reductions,
1338  // we do need to match the operands, because we need to reject
1339  // out-of-order instructions within an iteration!
1340  // For example (assume floating-point addition), we need to reject this:
1341  // x += a[i]; x += b[i];
1342  // x += a[i+1]; x += b[i+1];
1343  // x += b[i+2]; x += a[i+2];
1344  bool InReduction = Reductions.isPairInSame(BaseInst, RootInst);
1345 
1346  if (!(InReduction && BaseInst->isAssociative())) {
1347  bool Swapped = false, SomeOpMatched = false;
1348  for (unsigned j = 0; j < BaseInst->getNumOperands(); ++j) {
1349  Value *Op2 = RootInst->getOperand(j);
1350 
1351  // If this is part of a reduction (and the operation is not
1352  // associatve), then we match all operands, but not those that are
1353  // part of the reduction.
1354  if (InReduction)
1355  if (Instruction *Op2I = dyn_cast<Instruction>(Op2))
1356  if (Reductions.isPairInSame(RootInst, Op2I))
1357  continue;
1358 
1359  DenseMap<Value *, Value *>::iterator BMI = BaseMap.find(Op2);
1360  if (BMI != BaseMap.end()) {
1361  Op2 = BMI->second;
1362  } else {
1363  for (auto &DRS : RootSets) {
1364  if (DRS.Roots[Iter-1] == (Instruction*) Op2) {
1365  Op2 = DRS.BaseInst;
1366  break;
1367  }
1368  }
1369  }
1370 
1371  if (BaseInst->getOperand(Swapped ? unsigned(!j) : j) != Op2) {
1372  // If we've not already decided to swap the matched operands, and
1373  // we've not already matched our first operand (note that we could
1374  // have skipped matching the first operand because it is part of a
1375  // reduction above), and the instruction is commutative, then try
1376  // the swapped match.
1377  if (!Swapped && BaseInst->isCommutative() && !SomeOpMatched &&
1378  BaseInst->getOperand(!j) == Op2) {
1379  Swapped = true;
1380  } else {
1381  LLVM_DEBUG(dbgs()
1382  << "LRR: iteration root match failed at " << *BaseInst
1383  << " vs. " << *RootInst << " (operand " << j << ")\n");
1384  return false;
1385  }
1386  }
1387 
1388  SomeOpMatched = true;
1389  }
1390  }
1391 
1392  if ((!PossibleRedLastSet.count(BaseInst) &&
1393  hasUsesOutsideLoop(BaseInst, L)) ||
1394  (!PossibleRedLastSet.count(RootInst) &&
1395  hasUsesOutsideLoop(RootInst, L))) {
1396  LLVM_DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInst
1397  << " vs. " << *RootInst << " (uses outside loop)\n");
1398  return false;
1399  }
1400 
1401  Reductions.recordPair(BaseInst, RootInst, Iter);
1402  BaseMap.insert(std::make_pair(RootInst, BaseInst));
1403 
1404  LastRootIt = RootIt;
1405  Visited.insert(BaseInst);
1406  Visited.insert(RootInst);
1407  BaseIt = nextInstr(0, Uses, Visited);
1408  RootIt = nextInstr(Iter, Uses, Visited);
1409  }
1410  assert(BaseIt == Uses.end() && RootIt == Uses.end() &&
1411  "Mismatched set sizes!");
1412  }
1413 
1414  LLVM_DEBUG(dbgs() << "LRR: Matched all iteration increments for " << *IV
1415  << "\n");
1416 
1417  return true;
1418 }
1419 
1420 void LoopReroll::DAGRootTracker::replace(const SCEV *BackedgeTakenCount) {
1421  BasicBlock *Header = L->getHeader();
1422 
1423  // Compute the start and increment for each BaseInst before we start erasing
1424  // instructions.
1425  SmallVector<const SCEV *, 8> StartExprs;
1426  SmallVector<const SCEV *, 8> IncrExprs;
1427  for (auto &DRS : RootSets) {
1428  const SCEVAddRecExpr *IVSCEV =
1429  cast<SCEVAddRecExpr>(SE->getSCEV(DRS.BaseInst));
1430  StartExprs.push_back(IVSCEV->getStart());
1431  IncrExprs.push_back(SE->getMinusSCEV(SE->getSCEV(DRS.Roots[0]), IVSCEV));
1432  }
1433 
1434  // Remove instructions associated with non-base iterations.
1435  for (BasicBlock::reverse_iterator J = Header->rbegin(), JE = Header->rend();
1436  J != JE;) {
1437  unsigned I = Uses[&*J].find_first();
1438  if (I > 0 && I < IL_All) {
1439  LLVM_DEBUG(dbgs() << "LRR: removing: " << *J << "\n");
1440  J++->eraseFromParent();
1441  continue;
1442  }
1443 
1444  ++J;
1445  }
1446 
1447  // Rewrite each BaseInst using SCEV.
1448  for (size_t i = 0, e = RootSets.size(); i != e; ++i)
1449  // Insert the new induction variable.
1450  replaceIV(RootSets[i], StartExprs[i], IncrExprs[i]);
1451 
1452  { // Limit the lifetime of SCEVExpander.
1453  BranchInst *BI = cast<BranchInst>(Header->getTerminator());
1454  const DataLayout &DL = Header->getModule()->getDataLayout();
1455  SCEVExpander Expander(*SE, DL, "reroll");
1456  auto Zero = SE->getZero(BackedgeTakenCount->getType());
1457  auto One = SE->getOne(BackedgeTakenCount->getType());
1458  auto NewIVSCEV = SE->getAddRecExpr(Zero, One, L, SCEV::FlagAnyWrap);
1459  Value *NewIV =
1460  Expander.expandCodeFor(NewIVSCEV, BackedgeTakenCount->getType(),
1461  Header->getFirstNonPHIOrDbg());
1462  // FIXME: This arithmetic can overflow.
1463  auto TripCount = SE->getAddExpr(BackedgeTakenCount, One);
1464  auto ScaledTripCount = SE->getMulExpr(
1465  TripCount, SE->getConstant(BackedgeTakenCount->getType(), Scale));
1466  auto ScaledBECount = SE->getMinusSCEV(ScaledTripCount, One);
1467  Value *TakenCount =
1468  Expander.expandCodeFor(ScaledBECount, BackedgeTakenCount->getType(),
1469  Header->getFirstNonPHIOrDbg());
1470  Value *Cond =
1471  new ICmpInst(BI, CmpInst::ICMP_EQ, NewIV, TakenCount, "exitcond");
1472  BI->setCondition(Cond);
1473 
1474  if (BI->getSuccessor(1) != Header)
1475  BI->swapSuccessors();
1476  }
1477 
1478  SimplifyInstructionsInBlock(Header, TLI);
1479  DeleteDeadPHIs(Header, TLI);
1480 }
1481 
1482 void LoopReroll::DAGRootTracker::replaceIV(DAGRootSet &DRS,
1483  const SCEV *Start,
1484  const SCEV *IncrExpr) {
1485  BasicBlock *Header = L->getHeader();
1486  Instruction *Inst = DRS.BaseInst;
1487 
1488  const SCEV *NewIVSCEV =
1489  SE->getAddRecExpr(Start, IncrExpr, L, SCEV::FlagAnyWrap);
1490 
1491  { // Limit the lifetime of SCEVExpander.
1492  const DataLayout &DL = Header->getModule()->getDataLayout();
1493  SCEVExpander Expander(*SE, DL, "reroll");
1494  Value *NewIV = Expander.expandCodeFor(NewIVSCEV, Inst->getType(),
1495  Header->getFirstNonPHIOrDbg());
1496 
1497  for (auto &KV : Uses)
1498  if (KV.second.find_first() == 0)
1499  KV.first->replaceUsesOfWith(Inst, NewIV);
1500  }
1501 }
1502 
1503 // Validate the selected reductions. All iterations must have an isomorphic
1504 // part of the reduction chain and, for non-associative reductions, the chain
1505 // entries must appear in order.
1506 bool LoopReroll::ReductionTracker::validateSelected() {
1507  // For a non-associative reduction, the chain entries must appear in order.
1508  for (int i : Reds) {
1509  int PrevIter = 0, BaseCount = 0, Count = 0;
1510  for (Instruction *J : PossibleReds[i]) {
1511  // Note that all instructions in the chain must have been found because
1512  // all instructions in the function must have been assigned to some
1513  // iteration.
1514  int Iter = PossibleRedIter[J];
1515  if (Iter != PrevIter && Iter != PrevIter + 1 &&
1516  !PossibleReds[i].getReducedValue()->isAssociative()) {
1517  LLVM_DEBUG(dbgs() << "LRR: Out-of-order non-associative reduction: "
1518  << J << "\n");
1519  return false;
1520  }
1521 
1522  if (Iter != PrevIter) {
1523  if (Count != BaseCount) {
1524  LLVM_DEBUG(dbgs()
1525  << "LRR: Iteration " << PrevIter << " reduction use count "
1526  << Count << " is not equal to the base use count "
1527  << BaseCount << "\n");
1528  return false;
1529  }
1530 
1531  Count = 0;
1532  }
1533 
1534  ++Count;
1535  if (Iter == 0)
1536  ++BaseCount;
1537 
1538  PrevIter = Iter;
1539  }
1540  }
1541 
1542  return true;
1543 }
1544 
1545 // For all selected reductions, remove all parts except those in the first
1546 // iteration (and the PHI). Replace outside uses of the reduced value with uses
1547 // of the first-iteration reduced value (in other words, reroll the selected
1548 // reductions).
1549 void LoopReroll::ReductionTracker::replaceSelected() {
1550  // Fixup reductions to refer to the last instruction associated with the
1551  // first iteration (not the last).
1552  for (int i : Reds) {
1553  int j = 0;
1554  for (int e = PossibleReds[i].size(); j != e; ++j)
1555  if (PossibleRedIter[PossibleReds[i][j]] != 0) {
1556  --j;
1557  break;
1558  }
1559 
1560  // Replace users with the new end-of-chain value.
1561  SmallInstructionVector Users;
1562  for (User *U : PossibleReds[i].getReducedValue()->users()) {
1563  Users.push_back(cast<Instruction>(U));
1564  }
1565 
1566  for (Instruction *User : Users)
1567  User->replaceUsesOfWith(PossibleReds[i].getReducedValue(),
1568  PossibleReds[i][j]);
1569  }
1570 }
1571 
1572 // Reroll the provided loop with respect to the provided induction variable.
1573 // Generally, we're looking for a loop like this:
1574 //
1575 // %iv = phi [ (preheader, ...), (body, %iv.next) ]
1576 // f(%iv)
1577 // %iv.1 = add %iv, 1 <-- a root increment
1578 // f(%iv.1)
1579 // %iv.2 = add %iv, 2 <-- a root increment
1580 // f(%iv.2)
1581 // %iv.scale_m_1 = add %iv, scale-1 <-- a root increment
1582 // f(%iv.scale_m_1)
1583 // ...
1584 // %iv.next = add %iv, scale
1585 // %cmp = icmp(%iv, ...)
1586 // br %cmp, header, exit
1587 //
1588 // Notably, we do not require that f(%iv), f(%iv.1), etc. be isolated groups of
1589 // instructions. In other words, the instructions in f(%iv), f(%iv.1), etc. can
1590 // be intermixed with eachother. The restriction imposed by this algorithm is
1591 // that the relative order of the isomorphic instructions in f(%iv), f(%iv.1),
1592 // etc. be the same.
1593 //
1594 // First, we collect the use set of %iv, excluding the other increment roots.
1595 // This gives us f(%iv). Then we iterate over the loop instructions (scale-1)
1596 // times, having collected the use set of f(%iv.(i+1)), during which we:
1597 // - Ensure that the next unmatched instruction in f(%iv) is isomorphic to
1598 // the next unmatched instruction in f(%iv.(i+1)).
1599 // - Ensure that both matched instructions don't have any external users
1600 // (with the exception of last-in-chain reduction instructions).
1601 // - Track the (aliasing) write set, and other side effects, of all
1602 // instructions that belong to future iterations that come before the matched
1603 // instructions. If the matched instructions read from that write set, then
1604 // f(%iv) or f(%iv.(i+1)) has some dependency on instructions in
1605 // f(%iv.(j+1)) for some j > i, and we cannot reroll the loop. Similarly,
1606 // if any of these future instructions had side effects (could not be
1607 // speculatively executed), and so do the matched instructions, when we
1608 // cannot reorder those side-effect-producing instructions, and rerolling
1609 // fails.
1610 //
1611 // Finally, we make sure that all loop instructions are either loop increment
1612 // roots, belong to simple latch code, parts of validated reductions, part of
1613 // f(%iv) or part of some f(%iv.i). If all of that is true (and all reductions
1614 // have been validated), then we reroll the loop.
1615 bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header,
1616  const SCEV *BackedgeTakenCount,
1617  ReductionTracker &Reductions) {
1618  DAGRootTracker DAGRoots(this, L, IV, SE, AA, TLI, DT, LI, PreserveLCSSA,
1619  IVToIncMap, LoopControlIV);
1620 
1621  if (!DAGRoots.findRoots())
1622  return false;
1623  LLVM_DEBUG(dbgs() << "LRR: Found all root induction increments for: " << *IV
1624  << "\n");
1625 
1626  if (!DAGRoots.validate(Reductions))
1627  return false;
1628  if (!Reductions.validateSelected())
1629  return false;
1630  // At this point, we've validated the rerolling, and we're committed to
1631  // making changes!
1632 
1633  Reductions.replaceSelected();
1634  DAGRoots.replace(BackedgeTakenCount);
1635 
1636  ++NumRerolledLoops;
1637  return true;
1638 }
1639 
1640 bool LoopReroll::runOnLoop(Loop *L, LPPassManager &LPM) {
1641  if (skipLoop(L))
1642  return false;
1643 
1644  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
1645  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1646  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1647  TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1648  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1649  PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
1650 
1651  BasicBlock *Header = L->getHeader();
1652  LLVM_DEBUG(dbgs() << "LRR: F[" << Header->getParent()->getName() << "] Loop %"
1653  << Header->getName() << " (" << L->getNumBlocks()
1654  << " block(s))\n");
1655 
1656  // For now, we'll handle only single BB loops.
1657  if (L->getNumBlocks() > 1)
1658  return false;
1659 
1660  if (!SE->hasLoopInvariantBackedgeTakenCount(L))
1661  return false;
1662 
1663  const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
1664  LLVM_DEBUG(dbgs() << "\n Before Reroll:\n" << *(L->getHeader()) << "\n");
1665  LLVM_DEBUG(dbgs() << "LRR: backedge-taken count = " << *BackedgeTakenCount
1666  << "\n");
1667 
1668  // First, we need to find the induction variable with respect to which we can
1669  // reroll (there may be several possible options).
1670  SmallInstructionVector PossibleIVs;
1671  IVToIncMap.clear();
1672  LoopControlIV = nullptr;
1673  collectPossibleIVs(L, PossibleIVs);
1674 
1675  if (PossibleIVs.empty()) {
1676  LLVM_DEBUG(dbgs() << "LRR: No possible IVs found\n");
1677  return false;
1678  }
1679 
1680  ReductionTracker Reductions;
1681  collectPossibleReductions(L, Reductions);
1682  bool Changed = false;
1683 
1684  // For each possible IV, collect the associated possible set of 'root' nodes
1685  // (i+1, i+2, etc.).
1686  for (Instruction *PossibleIV : PossibleIVs)
1687  if (reroll(PossibleIV, L, Header, BackedgeTakenCount, Reductions)) {
1688  Changed = true;
1689  break;
1690  }
1691  LLVM_DEBUG(dbgs() << "\n After Reroll:\n" << *(L->getHeader()) << "\n");
1692 
1693  // Trip count of L has changed so SE must be re-evaluated.
1694  if (Changed)
1695  SE->forgetLoop(L);
1696 
1697  return Changed;
1698 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
uint64_t CallInst * C
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
Pass * createLoopRerollPass()
iterator_range< use_iterator > uses()
Definition: Value.h:354
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
bool isSameOperationAs(const Instruction *I, unsigned flags=0) const
This function determines if the specified instruction executes the same operation as the current one...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
BinaryOps getOpcode() const
Definition: InstrTypes.h:379
void swapSuccessors()
Swap the successors of this branch instruction.
bool user_empty() const
Definition: Value.h:363
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
void push_back(const T &Elt)
Definition: SmallVector.h:211
static cl::opt< unsigned > NumToleratedFailedMatches("reroll-num-tolerated-failed-matches", cl::init(400), cl::Hidden, cl::desc("The maximum number of failures to tolerate" " during fuzzy matching. (default: 400)"))
void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo)
These methods are used to add different types of instructions to the alias sets.
The main scalar evolution driver.
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
This class implements a map that also provides access to all stored values in a deterministic order...
Definition: MapVector.h:37
BasicBlock * getSuccessor(unsigned i) const
STATISTIC(NumFunctions, "Total number of functions")
bool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)
Scan the specified basic block and try to simplify any instructions in it and recursively delete dead...
Definition: Local.cpp:596
void initializeLoopRerollPass(PassRegistry &)
reverse_iterator rend()
Definition: BasicBlock.h:275
An instruction for reading from memory.
Definition: Instructions.h:167
reverse_iterator rbegin()
Definition: BasicBlock.h:273
Hexagon Common GEP
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:137
iv Induction Variable Users
Definition: IVUsers.cpp:51
This defines the Use class.
op_iterator op_begin()
Definition: User.h:229
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:221
static bool isIgnorableInst(const Instruction *I)
AnalysisUsage & addRequired()
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:133
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
static bool isUnorderedLoadStore(Instruction *I)
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
static bool hasUsesOutsideLoop(Instruction *I, Loop *L)
This file implements a class to represent arbitrary precision integral constant values and operations...
BlockT * getHeader() const
Definition: LoopInfo.h:100
ConstantInt * getValue() const
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1574
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
This node represents a polynomial recurrence on the trip count of the specified loop.
bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)
Examine each PHI in the given block and delete it if it is dead.
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:137
An instruction for storing to memory.
Definition: Instructions.h:320
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Value * getOperand(unsigned i) const
Definition: User.h:169
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:20
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:176
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
friend const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
bool hasNUsesOrMore(unsigned N) const
Return true if this value has N users or more.
Definition: Value.cpp:135
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:216
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
Conditional or Unconditional Branch instruction.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
char & LCSSAID
Definition: LCSSA.cpp:467
bool isAssociative() const LLVM_READONLY
Return true if the instruction is associative:
Represent the analysis usage information of a pass.
op_iterator op_end()
Definition: User.h:231
This instruction compares its operands according to the predicate given to the constructor.
bool isBinaryOp() const
Definition: Instruction.h:130
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
static void replace(Module &M, GlobalVariable *Old, GlobalVariable *New)
static bool isLoopIncrement(User *U, Instruction *IV)
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:50
IterationLimits
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
This is the common base class for memset/memcpy/memmove.
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:191
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1166
Type * getType() const
Return the LLVM type of this SCEV expression.
static uint64_t add(uint64_t LeftOp, uint64_t RightOp)
Definition: FileCheck.cpp:124
Module.h This file contains the declarations for the Module class.
Provides information about what library functions are available for the current target.
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:47
typename VectorType::iterator iterator
Definition: MapVector.h:49
bool isCommutative() const
Return true if the instruction is commutative:
Definition: Instruction.h:488
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
iterator_range< user_iterator > users()
Definition: Value.h:399
This class uses information about analyze scalars to rewrite expressions in canonical form...
static bool isSimpleArithmeticOp(User *IVU)
Return true if IVU is a "simple" arithmetic operation.
unsigned getNumBlocks() const
Get the number of blocks in this loop in constant time.
Definition: LoopInfo.h:163
unsigned getNumUses() const
This method computes the number of uses of this Value.
Definition: Value.cpp:160
iv users
Definition: IVUsers.cpp:51
This class represents an analyzed expression in the program.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:465
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Definition: APFloat.h:1212
bool mayReadFromMemory() const
Return true if this instruction may read memory.
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:136
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
void setCondition(Value *V)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:375
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 ...
LLVM Value Representation.
Definition: Value.h:72
IRTranslator LLVM IR MI
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:412
const Instruction * getFirstNonPHIOrDbg() const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic...
Definition: BasicBlock.cpp:196
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Definition: Constants.h:156
static bool isAssociative(const COFFSection &Section)
#define LLVM_DEBUG(X)
Definition: Debug.h:122
bool use_empty() const
Definition: Value.h:322
void validate(const Triple &TT, const FeatureBitset &FeatureBits)
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43
const BasicBlock * getParent() const
Definition: Instruction.h:66
This class represents a constant integer value.
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1244