LLVM  7.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  } else {
298  continue;
299  }
300 
301  bool FoundBucket = false;
302  for (auto &B : Buckets) {
303  const SCEV *Diff = SE->getMinusSCEV(LSCEV, B.BaseSCEV);
304  if (const auto *CDiff = dyn_cast<SCEVConstant>(Diff)) {
305  B.Elements.push_back(BucketElement(CDiff, MemI));
306  FoundBucket = true;
307  break;
308  }
309  }
310 
311  if (!FoundBucket) {
312  if (Buckets.size() == MaxVars)
313  return MadeChange;
314  Buckets.push_back(Bucket(LSCEV, MemI));
315  }
316  }
317  }
318 
319  if (Buckets.empty())
320  return MadeChange;
321 
322  BasicBlock *LoopPredecessor = L->getLoopPredecessor();
323  // If there is no loop predecessor, or the loop predecessor's terminator
324  // returns a value (which might contribute to determining the loop's
325  // iteration space), insert a new preheader for the loop.
326  if (!LoopPredecessor ||
327  !LoopPredecessor->getTerminator()->getType()->isVoidTy()) {
328  LoopPredecessor = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA);
329  if (LoopPredecessor)
330  MadeChange = true;
331  }
332  if (!LoopPredecessor)
333  return MadeChange;
334 
335  LLVM_DEBUG(dbgs() << "PIP: Found " << Buckets.size() << " buckets\n");
336 
337  SmallSet<BasicBlock *, 16> BBChanged;
338  for (unsigned i = 0, e = Buckets.size(); i != e; ++i) {
339  // The base address of each bucket is transformed into a phi and the others
340  // are rewritten as offsets of that variable.
341 
342  // We have a choice now of which instruction's memory operand we use as the
343  // base for the generated PHI. Always picking the first instruction in each
344  // bucket does not work well, specifically because that instruction might
345  // be a prefetch (and there are no pre-increment dcbt variants). Otherwise,
346  // the choice is somewhat arbitrary, because the backend will happily
347  // generate direct offsets from both the pre-incremented and
348  // post-incremented pointer values. Thus, we'll pick the first non-prefetch
349  // instruction in each bucket, and adjust the recurrence and other offsets
350  // accordingly.
351  for (int j = 0, je = Buckets[i].Elements.size(); j != je; ++j) {
352  if (auto *II = dyn_cast<IntrinsicInst>(Buckets[i].Elements[j].Instr))
353  if (II->getIntrinsicID() == Intrinsic::prefetch)
354  continue;
355 
356  // If we'd otherwise pick the first element anyway, there's nothing to do.
357  if (j == 0)
358  break;
359 
360  // If our chosen element has no offset from the base pointer, there's
361  // nothing to do.
362  if (!Buckets[i].Elements[j].Offset ||
363  Buckets[i].Elements[j].Offset->isZero())
364  break;
365 
366  const SCEV *Offset = Buckets[i].Elements[j].Offset;
367  Buckets[i].BaseSCEV = SE->getAddExpr(Buckets[i].BaseSCEV, Offset);
368  for (auto &E : Buckets[i].Elements) {
369  if (E.Offset)
370  E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(E.Offset, Offset));
371  else
372  E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(Offset));
373  }
374 
375  std::swap(Buckets[i].Elements[j], Buckets[i].Elements[0]);
376  break;
377  }
378 
379  const SCEVAddRecExpr *BasePtrSCEV =
380  cast<SCEVAddRecExpr>(Buckets[i].BaseSCEV);
381  if (!BasePtrSCEV->isAffine())
382  continue;
383 
384  LLVM_DEBUG(dbgs() << "PIP: Transforming: " << *BasePtrSCEV << "\n");
385  assert(BasePtrSCEV->getLoop() == L &&
386  "AddRec for the wrong loop?");
387 
388  // The instruction corresponding to the Bucket's BaseSCEV must be the first
389  // in the vector of elements.
390  Instruction *MemI = Buckets[i].Elements.begin()->Instr;
391  Value *BasePtr = GetPointerOperand(MemI);
392  assert(BasePtr && "No pointer operand");
393 
394  Type *I8Ty = Type::getInt8Ty(MemI->getParent()->getContext());
395  Type *I8PtrTy = Type::getInt8PtrTy(MemI->getParent()->getContext(),
396  BasePtr->getType()->getPointerAddressSpace());
397 
398  const SCEV *BasePtrStartSCEV = BasePtrSCEV->getStart();
399  if (!SE->isLoopInvariant(BasePtrStartSCEV, L))
400  continue;
401 
402  const SCEVConstant *BasePtrIncSCEV =
403  dyn_cast<SCEVConstant>(BasePtrSCEV->getStepRecurrence(*SE));
404  if (!BasePtrIncSCEV)
405  continue;
406  BasePtrStartSCEV = SE->getMinusSCEV(BasePtrStartSCEV, BasePtrIncSCEV);
407  if (!isSafeToExpand(BasePtrStartSCEV, *SE))
408  continue;
409 
410  LLVM_DEBUG(dbgs() << "PIP: New start is: " << *BasePtrStartSCEV << "\n");
411 
412  if (alreadyPrepared(L, MemI, BasePtrStartSCEV, BasePtrIncSCEV))
413  continue;
414 
415  PHINode *NewPHI = PHINode::Create(I8PtrTy, HeaderLoopPredCount,
416  MemI->hasName() ? MemI->getName() + ".phi" : "",
417  Header->getFirstNonPHI());
418 
419  SCEVExpander SCEVE(*SE, Header->getModule()->getDataLayout(), "pistart");
420  Value *BasePtrStart = SCEVE.expandCodeFor(BasePtrStartSCEV, I8PtrTy,
421  LoopPredecessor->getTerminator());
422 
423  // Note that LoopPredecessor might occur in the predecessor list multiple
424  // times, and we need to add it the right number of times.
425  for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
426  PI != PE; ++PI) {
427  if (*PI != LoopPredecessor)
428  continue;
429 
430  NewPHI->addIncoming(BasePtrStart, LoopPredecessor);
431  }
432 
433  Instruction *InsPoint = &*Header->getFirstInsertionPt();
435  I8Ty, NewPHI, BasePtrIncSCEV->getValue(),
436  MemI->hasName() ? MemI->getName() + ".inc" : "", InsPoint);
437  PtrInc->setIsInBounds(IsPtrInBounds(BasePtr));
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(PtrInc, *PI);
444  }
445 
446  Instruction *NewBasePtr;
447  if (PtrInc->getType() != BasePtr->getType())
448  NewBasePtr = new BitCastInst(PtrInc, BasePtr->getType(),
449  PtrInc->hasName() ? PtrInc->getName() + ".cast" : "", InsPoint);
450  else
451  NewBasePtr = PtrInc;
452 
453  if (Instruction *IDel = dyn_cast<Instruction>(BasePtr))
454  BBChanged.insert(IDel->getParent());
455  BasePtr->replaceAllUsesWith(NewBasePtr);
457 
458  // Keep track of the replacement pointer values we've inserted so that we
459  // don't generate more pointer values than necessary.
460  SmallPtrSet<Value *, 16> NewPtrs;
461  NewPtrs.insert( NewBasePtr);
462 
463  for (auto I = std::next(Buckets[i].Elements.begin()),
464  IE = Buckets[i].Elements.end(); I != IE; ++I) {
465  Value *Ptr = GetPointerOperand(I->Instr);
466  assert(Ptr && "No pointer operand");
467  if (NewPtrs.count(Ptr))
468  continue;
469 
470  Instruction *RealNewPtr;
471  if (!I->Offset || I->Offset->getValue()->isZero()) {
472  RealNewPtr = NewBasePtr;
473  } else {
474  Instruction *PtrIP = dyn_cast<Instruction>(Ptr);
475  if (PtrIP && isa<Instruction>(NewBasePtr) &&
476  cast<Instruction>(NewBasePtr)->getParent() == PtrIP->getParent())
477  PtrIP = nullptr;
478  else if (isa<PHINode>(PtrIP))
479  PtrIP = &*PtrIP->getParent()->getFirstInsertionPt();
480  else if (!PtrIP)
481  PtrIP = I->Instr;
482 
484  I8Ty, PtrInc, I->Offset->getValue(),
485  I->Instr->hasName() ? I->Instr->getName() + ".off" : "", PtrIP);
486  if (!PtrIP)
487  NewPtr->insertAfter(cast<Instruction>(PtrInc));
488  NewPtr->setIsInBounds(IsPtrInBounds(Ptr));
489  RealNewPtr = NewPtr;
490  }
491 
492  if (Instruction *IDel = dyn_cast<Instruction>(Ptr))
493  BBChanged.insert(IDel->getParent());
494 
495  Instruction *ReplNewPtr;
496  if (Ptr->getType() != RealNewPtr->getType()) {
497  ReplNewPtr = new BitCastInst(RealNewPtr, Ptr->getType(),
498  Ptr->hasName() ? Ptr->getName() + ".cast" : "");
499  ReplNewPtr->insertAfter(RealNewPtr);
500  } else
501  ReplNewPtr = RealNewPtr;
502 
503  Ptr->replaceAllUsesWith(ReplNewPtr);
505 
506  NewPtrs.insert(RealNewPtr);
507  }
508 
509  MadeChange = true;
510  }
511 
512  for (Loop::block_iterator I = L->block_begin(), IE = L->block_end();
513  I != IE; ++I) {
514  if (BBChanged.count(*I))
515  DeleteDeadPHIs(*I);
516  }
517 
518  return MadeChange;
519 }
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:157
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
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:137
The main scalar evolution driver.
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:863
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:164
Hexagon Common GEP
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:227
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:373
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
void setIsInBounds(bool b=true)
Set or clear the inbounds flag on this GEP instruction.
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:306
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:142
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:837
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:117
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:36
char & LCSSAID
Definition: LCSSA.cpp:423
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)
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:429
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:57
BlockT * getLoopPredecessor() const
If the given loop&#39;s header has exactly one unique predecessor outside the loop, return it...
Definition: LoopInfoImpl.h:134
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:861
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:924
df_iterator< T > df_begin(const T &G)
A range adaptor for a pair of iterators.
This class uses information about analyze scalars to rewrite expressions in canonical form...
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:121
This class represents an analyzed expression in the program.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:62
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:445
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:110
#define I(x, y, z)
Definition: MD5.cpp:58
bool hasAltivec() const
Definition: PPCSubtarget.h:240
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
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:254
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:119
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.