LLVM  8.0.0svn
PPCLoopPreIncPrep.cpp
Go to the documentation of this file.
1 //===------ PPCLoopPreIncPrep.cpp - Loop Pre-Inc. AM Prep. 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 file implements a pass to prepare loops for pre-increment addressing
11 // modes. Additional PHIs are created for loop induction variables used by
12 // load/store instructions so that the pre-increment forms can be used.
13 // Generically, this means transforming loops like this:
14 // for (int i = 0; i < n; ++i)
15 // array[i] = c;
16 // to look like this:
17 // T *p = array[-1];
18 // for (int i = 0; i < n; ++i)
19 // *++p = c;
20 //===----------------------------------------------------------------------===//
21 
22 #define DEBUG_TYPE "ppc-loop-preinc-prep"
23 
24 #include "PPC.h"
25 #include "PPCSubtarget.h"
26 #include "PPCTargetMachine.h"
28 #include "llvm/ADT/SmallPtrSet.h"
29 #include "llvm/ADT/SmallSet.h"
30 #include "llvm/ADT/SmallVector.h"
31 #include "llvm/ADT/Statistic.h"
32 #include "llvm/Analysis/LoopInfo.h"
37 #include "llvm/IR/BasicBlock.h"
38 #include "llvm/IR/CFG.h"
39 #include "llvm/IR/Dominators.h"
40 #include "llvm/IR/Instruction.h"
41 #include "llvm/IR/Instructions.h"
42 #include "llvm/IR/IntrinsicInst.h"
43 #include "llvm/IR/Module.h"
44 #include "llvm/IR/Type.h"
45 #include "llvm/IR/Value.h"
46 #include "llvm/Pass.h"
47 #include "llvm/Support/Casting.h"
49 #include "llvm/Support/Debug.h"
50 #include "llvm/Transforms/Scalar.h"
51 #include "llvm/Transforms/Utils.h"
54 #include <cassert>
55 #include <iterator>
56 #include <utility>
57 
58 using namespace llvm;
59 
60 // By default, we limit this to creating 16 PHIs (which is a little over half
61 // of the allocatable register set).
62 static cl::opt<unsigned> MaxVars("ppc-preinc-prep-max-vars",
63  cl::Hidden, cl::init(16),
64  cl::desc("Potential PHI threshold for PPC preinc loop prep"));
65 
66 STATISTIC(PHINodeAlreadyExists, "PHI node already in pre-increment form");
67 
68 namespace llvm {
69 
71 
72 } // end namespace llvm
73 
74 namespace {
75 
76  class PPCLoopPreIncPrep : public FunctionPass {
77  public:
78  static char ID; // Pass ID, replacement for typeid
79 
80  PPCLoopPreIncPrep() : FunctionPass(ID) {
82  }
83 
84  PPCLoopPreIncPrep(PPCTargetMachine &TM) : FunctionPass(ID), TM(&TM) {
86  }
87 
88  void getAnalysisUsage(AnalysisUsage &AU) const override {
93  }
94 
95  bool alreadyPrepared(Loop *L, Instruction* MemI,
96  const SCEV *BasePtrStartSCEV,
97  const SCEVConstant *BasePtrIncSCEV);
98  bool runOnFunction(Function &F) override;
99 
100  bool runOnLoop(Loop *L);
101  void simplifyLoopLatch(Loop *L);
102  bool rotateLoop(Loop *L);
103 
104  private:
105  PPCTargetMachine *TM = nullptr;
106  DominatorTree *DT;
107  LoopInfo *LI;
108  ScalarEvolution *SE;
109  bool PreserveLCSSA;
110  };
111 
112 } // end anonymous namespace
113 
114 char PPCLoopPreIncPrep::ID = 0;
115 static const char *name = "Prepare loop for pre-inc. addressing modes";
116 INITIALIZE_PASS_BEGIN(PPCLoopPreIncPrep, DEBUG_TYPE, name, false, false)
119 INITIALIZE_PASS_END(PPCLoopPreIncPrep, DEBUG_TYPE, name, false, false)
120 
122  return new PPCLoopPreIncPrep(TM);
123 }
124 
125 namespace {
126 
127  struct BucketElement {
128  BucketElement(const SCEVConstant *O, Instruction *I) : Offset(O), Instr(I) {}
129  BucketElement(Instruction *I) : Offset(nullptr), Instr(I) {}
130 
131  const SCEVConstant *Offset;
132  Instruction *Instr;
133  };
134 
135  struct Bucket {
136  Bucket(const SCEV *B, Instruction *I) : BaseSCEV(B),
137  Elements(1, BucketElement(I)) {}
138 
139  const SCEV *BaseSCEV;
141  };
142 
143 } // end anonymous namespace
144 
145 static bool IsPtrInBounds(Value *BasePtr) {
146  Value *StrippedBasePtr = BasePtr;
147  while (BitCastInst *BC = dyn_cast<BitCastInst>(StrippedBasePtr))
148  StrippedBasePtr = BC->getOperand(0);
149  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(StrippedBasePtr))
150  return GEP->isInBounds();
151 
152  return false;
153 }
154 
155 static Value *GetPointerOperand(Value *MemI) {
156  if (LoadInst *LMemI = dyn_cast<LoadInst>(MemI)) {
157  return LMemI->getPointerOperand();
158  } else if (StoreInst *SMemI = dyn_cast<StoreInst>(MemI)) {
159  return SMemI->getPointerOperand();
160  } else if (IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(MemI)) {
161  if (IMemI->getIntrinsicID() == Intrinsic::prefetch)
162  return IMemI->getArgOperand(0);
163  }
164 
165  return nullptr;
166 }
167 
169  if (skipFunction(F))
170  return false;
171 
172  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
173  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
174  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
175  DT = DTWP ? &DTWP->getDomTree() : nullptr;
176  PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
177 
178  bool MadeChange = false;
179 
180  for (auto I = LI->begin(), IE = LI->end(); I != IE; ++I)
181  for (auto L = df_begin(*I), LE = df_end(*I); L != LE; ++L)
182  MadeChange |= runOnLoop(*L);
183 
184  return MadeChange;
185 }
186 
187 // In order to prepare for the pre-increment a PHI is added.
188 // This function will check to see if that PHI already exists and will return
189 // true if it found an existing PHI with the same start and increment as the
190 // one we wanted to create.
191 bool PPCLoopPreIncPrep::alreadyPrepared(Loop *L, Instruction* MemI,
192  const SCEV *BasePtrStartSCEV,
193  const SCEVConstant *BasePtrIncSCEV) {
194  BasicBlock *BB = MemI->getParent();
195  if (!BB)
196  return false;
197 
198  BasicBlock *PredBB = L->getLoopPredecessor();
199  BasicBlock *LatchBB = L->getLoopLatch();
200 
201  if (!PredBB || !LatchBB)
202  return false;
203 
204  // Run through the PHIs and see if we have some that looks like a preparation
206  for (auto & CurrentPHI : PHIIter) {
207  PHINode *CurrentPHINode = dyn_cast<PHINode>(&CurrentPHI);
208  if (!CurrentPHINode)
209  continue;
210 
211  if (!SE->isSCEVable(CurrentPHINode->getType()))
212  continue;
213 
214  const SCEV *PHISCEV = SE->getSCEVAtScope(CurrentPHINode, L);
215 
216  const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast<SCEVAddRecExpr>(PHISCEV);
217  if (!PHIBasePtrSCEV)
218  continue;
219 
220  const SCEVConstant *PHIBasePtrIncSCEV =
221  dyn_cast<SCEVConstant>(PHIBasePtrSCEV->getStepRecurrence(*SE));
222  if (!PHIBasePtrIncSCEV)
223  continue;
224 
225  if (CurrentPHINode->getNumIncomingValues() == 2) {
226  if ( (CurrentPHINode->getIncomingBlock(0) == LatchBB &&
227  CurrentPHINode->getIncomingBlock(1) == PredBB) ||
228  (CurrentPHINode->getIncomingBlock(1) == LatchBB &&
229  CurrentPHINode->getIncomingBlock(0) == PredBB) ) {
230  if (PHIBasePtrSCEV->getStart() == BasePtrStartSCEV &&
231  PHIBasePtrIncSCEV == BasePtrIncSCEV) {
232  // The existing PHI (CurrentPHINode) has the same start and increment
233  // as the PHI that we wanted to create.
234  ++PHINodeAlreadyExists;
235  return true;
236  }
237  }
238  }
239  }
240  return false;
241 }
242 
243 bool PPCLoopPreIncPrep::runOnLoop(Loop *L) {
244  bool MadeChange = false;
245 
246  // Only prep. the inner-most loop
247  if (!L->empty())
248  return MadeChange;
249 
250  LLVM_DEBUG(dbgs() << "PIP: Examining: " << *L << "\n");
251 
252  BasicBlock *Header = L->getHeader();
253 
254  const PPCSubtarget *ST =
255  TM ? TM->getSubtargetImpl(*Header->getParent()) : nullptr;
256 
257  unsigned HeaderLoopPredCount = pred_size(Header);
258 
259  // Collect buckets of comparable addresses used by loads and stores.
260  SmallVector<Bucket, 16> Buckets;
261  for (Loop::block_iterator I = L->block_begin(), IE = L->block_end();
262  I != IE; ++I) {
263  for (BasicBlock::iterator J = (*I)->begin(), JE = (*I)->end();
264  J != JE; ++J) {
265  Value *PtrValue;
266  Instruction *MemI;
267 
268  if (LoadInst *LMemI = dyn_cast<LoadInst>(J)) {
269  MemI = LMemI;
270  PtrValue = LMemI->getPointerOperand();
271  } else if (StoreInst *SMemI = dyn_cast<StoreInst>(J)) {
272  MemI = SMemI;
273  PtrValue = SMemI->getPointerOperand();
274  } else if (IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(J)) {
275  if (IMemI->getIntrinsicID() == Intrinsic::prefetch) {
276  MemI = IMemI;
277  PtrValue = IMemI->getArgOperand(0);
278  } else continue;
279  } else continue;
280 
281  unsigned PtrAddrSpace = PtrValue->getType()->getPointerAddressSpace();
282  if (PtrAddrSpace)
283  continue;
284 
285  // There are no update forms for Altivec vector load/stores.
286  if (ST && ST->hasAltivec() &&
287  PtrValue->getType()->getPointerElementType()->isVectorTy())
288  continue;
289 
290  if (L->isLoopInvariant(PtrValue))
291  continue;
292 
293  const SCEV *LSCEV = SE->getSCEVAtScope(PtrValue, L);
294  if (const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(LSCEV)) {
295  if (LARSCEV->getLoop() != L)
296  continue;
297  // See getPreIndexedAddressParts, the displacement for LDU/STDU has to
298  // be 4's multiple (DS-form). For i64 loads/stores when the displacement
299  // fits in a 16-bit signed field but isn't a multiple of 4, it will be
300  // useless and possible to break some original well-form addressing mode
301  // to make this pre-inc prep for it.
302  if (PtrValue->getType()->getPointerElementType()->isIntegerTy(64)) {
303  if (const SCEVConstant *StepConst =
304  dyn_cast<SCEVConstant>(LARSCEV->getStepRecurrence(*SE))) {
305  const APInt &ConstInt = StepConst->getValue()->getValue();
306  if (ConstInt.isSignedIntN(16) && ConstInt.srem(4) != 0)
307  continue;
308  }
309  }
310  } else {
311  continue;
312  }
313 
314  bool FoundBucket = false;
315  for (auto &B : Buckets) {
316  const SCEV *Diff = SE->getMinusSCEV(LSCEV, B.BaseSCEV);
317  if (const auto *CDiff = dyn_cast<SCEVConstant>(Diff)) {
318  B.Elements.push_back(BucketElement(CDiff, MemI));
319  FoundBucket = true;
320  break;
321  }
322  }
323 
324  if (!FoundBucket) {
325  if (Buckets.size() == MaxVars)
326  return MadeChange;
327  Buckets.push_back(Bucket(LSCEV, MemI));
328  }
329  }
330  }
331 
332  if (Buckets.empty())
333  return MadeChange;
334 
335  BasicBlock *LoopPredecessor = L->getLoopPredecessor();
336  // If there is no loop predecessor, or the loop predecessor's terminator
337  // returns a value (which might contribute to determining the loop's
338  // iteration space), insert a new preheader for the loop.
339  if (!LoopPredecessor ||
340  !LoopPredecessor->getTerminator()->getType()->isVoidTy()) {
341  LoopPredecessor = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA);
342  if (LoopPredecessor)
343  MadeChange = true;
344  }
345  if (!LoopPredecessor)
346  return MadeChange;
347 
348  LLVM_DEBUG(dbgs() << "PIP: Found " << Buckets.size() << " buckets\n");
349 
350  SmallSet<BasicBlock *, 16> BBChanged;
351  for (unsigned i = 0, e = Buckets.size(); i != e; ++i) {
352  // The base address of each bucket is transformed into a phi and the others
353  // are rewritten as offsets of that variable.
354 
355  // We have a choice now of which instruction's memory operand we use as the
356  // base for the generated PHI. Always picking the first instruction in each
357  // bucket does not work well, specifically because that instruction might
358  // be a prefetch (and there are no pre-increment dcbt variants). Otherwise,
359  // the choice is somewhat arbitrary, because the backend will happily
360  // generate direct offsets from both the pre-incremented and
361  // post-incremented pointer values. Thus, we'll pick the first non-prefetch
362  // instruction in each bucket, and adjust the recurrence and other offsets
363  // accordingly.
364  for (int j = 0, je = Buckets[i].Elements.size(); j != je; ++j) {
365  if (auto *II = dyn_cast<IntrinsicInst>(Buckets[i].Elements[j].Instr))
366  if (II->getIntrinsicID() == Intrinsic::prefetch)
367  continue;
368 
369  // If we'd otherwise pick the first element anyway, there's nothing to do.
370  if (j == 0)
371  break;
372 
373  // If our chosen element has no offset from the base pointer, there's
374  // nothing to do.
375  if (!Buckets[i].Elements[j].Offset ||
376  Buckets[i].Elements[j].Offset->isZero())
377  break;
378 
379  const SCEV *Offset = Buckets[i].Elements[j].Offset;
380  Buckets[i].BaseSCEV = SE->getAddExpr(Buckets[i].BaseSCEV, Offset);
381  for (auto &E : Buckets[i].Elements) {
382  if (E.Offset)
383  E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(E.Offset, Offset));
384  else
385  E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(Offset));
386  }
387 
388  std::swap(Buckets[i].Elements[j], Buckets[i].Elements[0]);
389  break;
390  }
391 
392  const SCEVAddRecExpr *BasePtrSCEV =
393  cast<SCEVAddRecExpr>(Buckets[i].BaseSCEV);
394  if (!BasePtrSCEV->isAffine())
395  continue;
396 
397  LLVM_DEBUG(dbgs() << "PIP: Transforming: " << *BasePtrSCEV << "\n");
398  assert(BasePtrSCEV->getLoop() == L &&
399  "AddRec for the wrong loop?");
400 
401  // The instruction corresponding to the Bucket's BaseSCEV must be the first
402  // in the vector of elements.
403  Instruction *MemI = Buckets[i].Elements.begin()->Instr;
404  Value *BasePtr = GetPointerOperand(MemI);
405  assert(BasePtr && "No pointer operand");
406 
407  Type *I8Ty = Type::getInt8Ty(MemI->getParent()->getContext());
408  Type *I8PtrTy = Type::getInt8PtrTy(MemI->getParent()->getContext(),
409  BasePtr->getType()->getPointerAddressSpace());
410 
411  const SCEV *BasePtrStartSCEV = BasePtrSCEV->getStart();
412  if (!SE->isLoopInvariant(BasePtrStartSCEV, L))
413  continue;
414 
415  const SCEVConstant *BasePtrIncSCEV =
416  dyn_cast<SCEVConstant>(BasePtrSCEV->getStepRecurrence(*SE));
417  if (!BasePtrIncSCEV)
418  continue;
419  BasePtrStartSCEV = SE->getMinusSCEV(BasePtrStartSCEV, BasePtrIncSCEV);
420  if (!isSafeToExpand(BasePtrStartSCEV, *SE))
421  continue;
422 
423  LLVM_DEBUG(dbgs() << "PIP: New start is: " << *BasePtrStartSCEV << "\n");
424 
425  if (alreadyPrepared(L, MemI, BasePtrStartSCEV, BasePtrIncSCEV))
426  continue;
427 
428  PHINode *NewPHI = PHINode::Create(I8PtrTy, HeaderLoopPredCount,
429  MemI->hasName() ? MemI->getName() + ".phi" : "",
430  Header->getFirstNonPHI());
431 
432  SCEVExpander SCEVE(*SE, Header->getModule()->getDataLayout(), "pistart");
433  Value *BasePtrStart = SCEVE.expandCodeFor(BasePtrStartSCEV, I8PtrTy,
434  LoopPredecessor->getTerminator());
435 
436  // Note that LoopPredecessor might occur in the predecessor list multiple
437  // times, and we need to add it the right number of times.
438  for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
439  PI != PE; ++PI) {
440  if (*PI != LoopPredecessor)
441  continue;
442 
443  NewPHI->addIncoming(BasePtrStart, LoopPredecessor);
444  }
445 
446  Instruction *InsPoint = &*Header->getFirstInsertionPt();
448  I8Ty, NewPHI, BasePtrIncSCEV->getValue(),
449  MemI->hasName() ? MemI->getName() + ".inc" : "", InsPoint);
450  PtrInc->setIsInBounds(IsPtrInBounds(BasePtr));
451  for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
452  PI != PE; ++PI) {
453  if (*PI == LoopPredecessor)
454  continue;
455 
456  NewPHI->addIncoming(PtrInc, *PI);
457  }
458 
459  Instruction *NewBasePtr;
460  if (PtrInc->getType() != BasePtr->getType())
461  NewBasePtr = new BitCastInst(PtrInc, BasePtr->getType(),
462  PtrInc->hasName() ? PtrInc->getName() + ".cast" : "", InsPoint);
463  else
464  NewBasePtr = PtrInc;
465 
466  if (Instruction *IDel = dyn_cast<Instruction>(BasePtr))
467  BBChanged.insert(IDel->getParent());
468  BasePtr->replaceAllUsesWith(NewBasePtr);
470 
471  // Keep track of the replacement pointer values we've inserted so that we
472  // don't generate more pointer values than necessary.
473  SmallPtrSet<Value *, 16> NewPtrs;
474  NewPtrs.insert( NewBasePtr);
475 
476  for (auto I = std::next(Buckets[i].Elements.begin()),
477  IE = Buckets[i].Elements.end(); I != IE; ++I) {
478  Value *Ptr = GetPointerOperand(I->Instr);
479  assert(Ptr && "No pointer operand");
480  if (NewPtrs.count(Ptr))
481  continue;
482 
483  Instruction *RealNewPtr;
484  if (!I->Offset || I->Offset->getValue()->isZero()) {
485  RealNewPtr = NewBasePtr;
486  } else {
487  Instruction *PtrIP = dyn_cast<Instruction>(Ptr);
488  if (PtrIP && isa<Instruction>(NewBasePtr) &&
489  cast<Instruction>(NewBasePtr)->getParent() == PtrIP->getParent())
490  PtrIP = nullptr;
491  else if (isa<PHINode>(PtrIP))
492  PtrIP = &*PtrIP->getParent()->getFirstInsertionPt();
493  else if (!PtrIP)
494  PtrIP = I->Instr;
495 
497  I8Ty, PtrInc, I->Offset->getValue(),
498  I->Instr->hasName() ? I->Instr->getName() + ".off" : "", PtrIP);
499  if (!PtrIP)
500  NewPtr->insertAfter(cast<Instruction>(PtrInc));
501  NewPtr->setIsInBounds(IsPtrInBounds(Ptr));
502  RealNewPtr = NewPtr;
503  }
504 
505  if (Instruction *IDel = dyn_cast<Instruction>(Ptr))
506  BBChanged.insert(IDel->getParent());
507 
508  Instruction *ReplNewPtr;
509  if (Ptr->getType() != RealNewPtr->getType()) {
510  ReplNewPtr = new BitCastInst(RealNewPtr, Ptr->getType(),
511  Ptr->hasName() ? Ptr->getName() + ".cast" : "");
512  ReplNewPtr->insertAfter(RealNewPtr);
513  } else
514  ReplNewPtr = RealNewPtr;
515 
516  Ptr->replaceAllUsesWith(ReplNewPtr);
518 
519  NewPtrs.insert(RealNewPtr);
520  }
521 
522  MadeChange = true;
523  }
524 
525  for (Loop::block_iterator I = L->block_begin(), IE = L->block_end();
526  I != IE; ++I) {
527  if (BBChanged.count(*I))
528  DeleteDeadPHIs(*I);
529  }
530 
531  return MadeChange;
532 }
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:225
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
ArrayRef< BasicBlock *>::const_iterator block_iterator
Definition: LoopInfo.h:153
The main scalar evolution driver.
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:867
BasicBlock * InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA)
InsertPreheaderForLoop - Once we discover that a loop doesn&#39;t have a preheader, this method is called...
STATISTIC(NumFunctions, "Total number of functions")
F(f)
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
Definition: DerivedTypes.h:503
An instruction for reading from memory.
Definition: Instructions.h:168
Hexagon Common GEP
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:230
loop data prefetch
static Value * GetPointerOperand(Value *MemI)
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
Type * getPointerElementType() const
Definition: Type.h:376
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:364
void setIsInBounds(bool b=true)
Set or clear the inbounds flag on this GEP instruction.
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:197
BlockT * getHeader() const
Definition: LoopInfo.h:100
#define DEBUG_TYPE
ConstantInt * getValue() const
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
void initializePPCLoopPreIncPrepPass(PassRegistry &)
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.
This class represents a no-op cast from one type to another.
An instruction for storing to memory.
Definition: Instructions.h:310
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:439
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:141
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:841
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:189
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
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:218
bool hasName() const
Definition: Value.h:251
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
df_iterator< T > df_end(const T &G)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
char & LCSSAID
Definition: LCSSA.cpp:424
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
Common code between 32-bit and 64-bit PowerPC targets.
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:430
size_t size() const
Definition: SmallVector.h:53
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:220
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:58
BlockT * getLoopPredecessor() const
If the given loop&#39;s header has exactly one unique predecessor outside the loop, return it...
Definition: LoopInfoImpl.h:202
Iterator for intrusive lists based on ilist_node.
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.
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:48
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
unsigned getNumIncomingValues() const
Return the number of incoming edges.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:941
df_iterator< T > df_begin(const T &G)
A range adaptor for a pair of iterators.
Class for arbitrary precision integers.
Definition: APInt.h:70
This class uses information about analyze scalars to rewrite expressions in canonical form...
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:133
This class represents an analyzed expression in the program.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
APInt srem(const APInt &RHS) const
Function for signed remainder operation.
Definition: APInt.cpp:1683
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction...
Definition: Instruction.cpp:80
unsigned pred_size(const BasicBlock *BB)
Definition: CFG.h:120
#define I(x, y, z)
Definition: MD5.cpp:58
bool hasAltivec() const
Definition: PPCSubtarget.h:242
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
block_iterator block_end() const
Definition: LoopInfo.h:155
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:320
bool isSignedIntN(unsigned N) const
Check if this APInt has an N-bits signed integer value.
Definition: APInt.h:456
static bool IsPtrInBounds(Value *BasePtr)
bool empty() const
Definition: LoopInfo.h:146
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
FunctionPass * createPPCLoopPreIncPrepPass(PPCTargetMachine &TM)
LLVM Value Representation.
Definition: Value.h:73
static const char * name
static const Function * getParent(const Value *V)
static cl::opt< unsigned > MaxVars("ppc-preinc-prep-max-vars", cl::Hidden, cl::init(16), cl::desc("Potential PHI threshold for PPC preinc loop prep"))
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:964
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:39
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:260
const TerminatorInst * 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
#define LLVM_DEBUG(X)
Definition: Debug.h:123
bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE)
Return true if the given expression is safe to expand in the sense that all materialized values are s...
block_iterator block_begin() const
Definition: LoopInfo.h:154
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:174
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.