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