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