LLVM  10.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 STATISTIC(UpdFormChainRewritten, "Num of update form chain rewritten");
67 
68 namespace {
69  struct BucketElement {
70  BucketElement(const SCEVConstant *O, Instruction *I) : Offset(O), Instr(I) {}
71  BucketElement(Instruction *I) : Offset(nullptr), Instr(I) {}
72 
73  const SCEVConstant *Offset;
74  Instruction *Instr;
75  };
76 
77  struct Bucket {
78  Bucket(const SCEV *B, Instruction *I) : BaseSCEV(B),
79  Elements(1, BucketElement(I)) {}
80 
81  const SCEV *BaseSCEV;
83  };
84 
85  class PPCLoopPreIncPrep : public FunctionPass {
86  public:
87  static char ID; // Pass ID, replacement for typeid
88 
89  PPCLoopPreIncPrep() : FunctionPass(ID) {
91  }
92 
93  PPCLoopPreIncPrep(PPCTargetMachine &TM) : FunctionPass(ID), TM(&TM) {
95  }
96 
97  void getAnalysisUsage(AnalysisUsage &AU) const override {
102  }
103 
104  bool runOnFunction(Function &F) override;
105 
106  private:
107  PPCTargetMachine *TM = nullptr;
108  const PPCSubtarget *ST;
109  DominatorTree *DT;
110  LoopInfo *LI;
111  ScalarEvolution *SE;
112  bool PreserveLCSSA;
113 
114  bool runOnLoop(Loop *L);
115 
116  /// Check if required PHI node is already exist in Loop \p L.
117  bool alreadyPrepared(Loop *L, Instruction* MemI,
118  const SCEV *BasePtrStartSCEV,
119  const SCEVConstant *BasePtrIncSCEV);
120 
121  /// Collect condition matched(\p isValidCandidate() returns true)
122  /// candidates in Loop \p L.
124  collectCandidates(Loop *L,
125  std::function<bool(const Instruction *, const Value *)>
126  isValidCandidate,
127  unsigned MaxCandidateNum);
128 
129  /// Add a candidate to candidates \p Buckets.
130  void addOneCandidate(Instruction *MemI, const SCEV *LSCEV,
131  SmallVector<Bucket, 16> &Buckets,
132  unsigned MaxCandidateNum);
133 
134  /// Prepare all candidates in \p Buckets for update form.
135  bool updateFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets);
136 
137  /// Prepare for one chain \p BucketChain, find the best base element and
138  /// update all other elements in \p BucketChain accordingly.
139  bool prepareBaseForUpdateFormChain(Bucket &BucketChain);
140 
141  /// Rewrite load/store instructions in \p BucketChain according to
142  /// preparation.
143  bool rewriteLoadStores(Loop *L, Bucket &BucketChain,
144  SmallSet<BasicBlock *, 16> &BBChanged);
145  };
146 
147 } // end anonymous namespace
148 
149 char PPCLoopPreIncPrep::ID = 0;
150 static const char *name = "Prepare loop for pre-inc. addressing modes";
151 INITIALIZE_PASS_BEGIN(PPCLoopPreIncPrep, DEBUG_TYPE, name, false, false)
154 INITIALIZE_PASS_END(PPCLoopPreIncPrep, DEBUG_TYPE, name, false, false)
155 
156 static const std::string PHINodeNameSuffix = ".phi";
157 static const std::string CastNodeNameSuffix = ".cast";
158 static const std::string GEPNodeIncNameSuffix = ".inc";
159 static const std::string GEPNodeOffNameSuffix = ".off";
160 
162  return new PPCLoopPreIncPrep(TM);
163 }
164 
165 static bool IsPtrInBounds(Value *BasePtr) {
166  Value *StrippedBasePtr = BasePtr;
167  while (BitCastInst *BC = dyn_cast<BitCastInst>(StrippedBasePtr))
168  StrippedBasePtr = BC->getOperand(0);
169  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(StrippedBasePtr))
170  return GEP->isInBounds();
171 
172  return false;
173 }
174 
175 static std::string getInstrName(const Value *I, const std::string Suffix) {
176  assert(I && "Invalid paramater!");
177  if (I->hasName())
178  return (I->getName() + Suffix).str();
179  else
180  return "";
181 }
182 
183 static Value *GetPointerOperand(Value *MemI) {
184  if (LoadInst *LMemI = dyn_cast<LoadInst>(MemI)) {
185  return LMemI->getPointerOperand();
186  } else if (StoreInst *SMemI = dyn_cast<StoreInst>(MemI)) {
187  return SMemI->getPointerOperand();
188  } else if (IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(MemI)) {
189  if (IMemI->getIntrinsicID() == Intrinsic::prefetch)
190  return IMemI->getArgOperand(0);
191  }
192 
193  return nullptr;
194 }
195 
197  if (skipFunction(F))
198  return false;
199 
200  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
201  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
202  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
203  DT = DTWP ? &DTWP->getDomTree() : nullptr;
204  PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
205  ST = TM ? TM->getSubtargetImpl(F) : nullptr;
206 
207  bool MadeChange = false;
208 
209  for (auto I = LI->begin(), IE = LI->end(); I != IE; ++I)
210  for (auto L = df_begin(*I), LE = df_end(*I); L != LE; ++L)
211  MadeChange |= runOnLoop(*L);
212 
213  return MadeChange;
214 }
215 
216 void PPCLoopPreIncPrep::addOneCandidate(Instruction *MemI, const SCEV *LSCEV,
217  SmallVector<Bucket, 16> &Buckets,
218  unsigned MaxCandidateNum) {
219  assert((MemI && GetPointerOperand(MemI)) &&
220  "Candidate should be a memory instruction.");
221  assert(LSCEV && "Invalid SCEV for Ptr value.");
222  bool FoundBucket = false;
223  for (auto &B : Buckets) {
224  const SCEV *Diff = SE->getMinusSCEV(LSCEV, B.BaseSCEV);
225  if (const auto *CDiff = dyn_cast<SCEVConstant>(Diff)) {
226  B.Elements.push_back(BucketElement(CDiff, MemI));
227  FoundBucket = true;
228  break;
229  }
230  }
231 
232  if (!FoundBucket) {
233  if (Buckets.size() == MaxCandidateNum)
234  return;
235  Buckets.push_back(Bucket(LSCEV, MemI));
236  }
237 }
238 
239 SmallVector<Bucket, 16> PPCLoopPreIncPrep::collectCandidates(
240  Loop *L,
241  std::function<bool(const Instruction *, const Value *)> isValidCandidate,
242  unsigned MaxCandidateNum) {
243  SmallVector<Bucket, 16> Buckets;
244  for (const auto &BB : L->blocks())
245  for (auto &J : *BB) {
246  Value *PtrValue;
247  Instruction *MemI;
248 
249  if (LoadInst *LMemI = dyn_cast<LoadInst>(&J)) {
250  MemI = LMemI;
251  PtrValue = LMemI->getPointerOperand();
252  } else if (StoreInst *SMemI = dyn_cast<StoreInst>(&J)) {
253  MemI = SMemI;
254  PtrValue = SMemI->getPointerOperand();
255  } else if (IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(&J)) {
256  if (IMemI->getIntrinsicID() == Intrinsic::prefetch) {
257  MemI = IMemI;
258  PtrValue = IMemI->getArgOperand(0);
259  } else continue;
260  } else continue;
261 
262  unsigned PtrAddrSpace = PtrValue->getType()->getPointerAddressSpace();
263  if (PtrAddrSpace)
264  continue;
265 
266  if (L->isLoopInvariant(PtrValue))
267  continue;
268 
269  const SCEV *LSCEV = SE->getSCEVAtScope(PtrValue, L);
270  const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(LSCEV);
271  if (!LARSCEV || LARSCEV->getLoop() != L)
272  continue;
273 
274  if (isValidCandidate(&J, PtrValue))
275  addOneCandidate(MemI, LSCEV, Buckets, MaxCandidateNum);
276  }
277  return Buckets;
278 }
279 
280 // TODO: implement a more clever base choosing policy.
281 // Currently we always choose an exist load/store offset. This maybe lead to
282 // suboptimal code sequences. For example, for one DS chain with offsets
283 // {-32769, 2003, 2007, 2011}, we choose -32769 as base offset, and left disp
284 // for load/stores are {0, 34772, 34776, 34780}. Though each offset now is a
285 // multipler of 4, it cannot be represented by sint16.
286 bool PPCLoopPreIncPrep::prepareBaseForUpdateFormChain(Bucket &BucketChain) {
287  // We have a choice now of which instruction's memory operand we use as the
288  // base for the generated PHI. Always picking the first instruction in each
289  // bucket does not work well, specifically because that instruction might
290  // be a prefetch (and there are no pre-increment dcbt variants). Otherwise,
291  // the choice is somewhat arbitrary, because the backend will happily
292  // generate direct offsets from both the pre-incremented and
293  // post-incremented pointer values. Thus, we'll pick the first non-prefetch
294  // instruction in each bucket, and adjust the recurrence and other offsets
295  // accordingly.
296  for (int j = 0, je = BucketChain.Elements.size(); j != je; ++j) {
297  if (auto *II = dyn_cast<IntrinsicInst>(BucketChain.Elements[j].Instr))
298  if (II->getIntrinsicID() == Intrinsic::prefetch)
299  continue;
300 
301  // If we'd otherwise pick the first element anyway, there's nothing to do.
302  if (j == 0)
303  break;
304 
305  // If our chosen element has no offset from the base pointer, there's
306  // nothing to do.
307  if (!BucketChain.Elements[j].Offset ||
308  BucketChain.Elements[j].Offset->isZero())
309  break;
310 
311  const SCEV *Offset = BucketChain.Elements[j].Offset;
312  BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset);
313  for (auto &E : BucketChain.Elements) {
314  if (E.Offset)
315  E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(E.Offset, Offset));
316  else
317  E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(Offset));
318  }
319 
320  std::swap(BucketChain.Elements[j], BucketChain.Elements[0]);
321  break;
322  }
323  return true;
324 }
325 
326 bool PPCLoopPreIncPrep::rewriteLoadStores(
327  Loop *L, Bucket &BucketChain, SmallSet<BasicBlock *, 16> &BBChanged) {
328  bool MadeChange = false;
329  const SCEVAddRecExpr *BasePtrSCEV =
330  cast<SCEVAddRecExpr>(BucketChain.BaseSCEV);
331  if (!BasePtrSCEV->isAffine())
332  return MadeChange;
333 
334  LLVM_DEBUG(dbgs() << "PIP: Transforming: " << *BasePtrSCEV << "\n");
335 
336  assert(BasePtrSCEV->getLoop() == L && "AddRec for the wrong loop?");
337 
338  // The instruction corresponding to the Bucket's BaseSCEV must be the first
339  // in the vector of elements.
340  Instruction *MemI = BucketChain.Elements.begin()->Instr;
341  Value *BasePtr = GetPointerOperand(MemI);
342  assert(BasePtr && "No pointer operand");
343 
344  Type *I8Ty = Type::getInt8Ty(MemI->getParent()->getContext());
345  Type *I8PtrTy = Type::getInt8PtrTy(MemI->getParent()->getContext(),
346  BasePtr->getType()->getPointerAddressSpace());
347 
348  const SCEV *BasePtrStartSCEV = BasePtrSCEV->getStart();
349  if (!SE->isLoopInvariant(BasePtrStartSCEV, L))
350  return MadeChange;
351 
352  const SCEVConstant *BasePtrIncSCEV =
353  dyn_cast<SCEVConstant>(BasePtrSCEV->getStepRecurrence(*SE));
354  if (!BasePtrIncSCEV)
355  return MadeChange;
356  BasePtrStartSCEV = SE->getMinusSCEV(BasePtrStartSCEV, BasePtrIncSCEV);
357  if (!isSafeToExpand(BasePtrStartSCEV, *SE))
358  return MadeChange;
359 
360  if (alreadyPrepared(L, MemI, BasePtrStartSCEV, BasePtrIncSCEV))
361  return MadeChange;
362 
363  LLVM_DEBUG(dbgs() << "PIP: New start is: " << *BasePtrStartSCEV << "\n");
364 
365  BasicBlock *Header = L->getHeader();
366  unsigned HeaderLoopPredCount = pred_size(Header);
367  BasicBlock *LoopPredecessor = L->getLoopPredecessor();
368 
369  PHINode *NewPHI =
370  PHINode::Create(I8PtrTy, HeaderLoopPredCount,
372  Header->getFirstNonPHI());
373 
374  SCEVExpander SCEVE(*SE, Header->getModule()->getDataLayout(), "pistart");
375  Value *BasePtrStart = SCEVE.expandCodeFor(BasePtrStartSCEV, I8PtrTy,
376  LoopPredecessor->getTerminator());
377 
378  // Note that LoopPredecessor might occur in the predecessor list multiple
379  // times, and we need to add it the right number of times.
380  for (const auto &PI : predecessors(Header)) {
381  if (PI != LoopPredecessor)
382  continue;
383 
384  NewPHI->addIncoming(BasePtrStart, LoopPredecessor);
385  }
386 
387  Instruction *InsPoint = &*Header->getFirstInsertionPt();
389  I8Ty, NewPHI, BasePtrIncSCEV->getValue(),
390  getInstrName(MemI, GEPNodeIncNameSuffix), InsPoint);
391  PtrInc->setIsInBounds(IsPtrInBounds(BasePtr));
392  for (const auto &PI : predecessors(Header)) {
393  if (PI == LoopPredecessor)
394  continue;
395 
396  NewPHI->addIncoming(PtrInc, PI);
397  }
398 
399  Instruction *NewBasePtr;
400  if (PtrInc->getType() != BasePtr->getType())
401  NewBasePtr = new BitCastInst(PtrInc, BasePtr->getType(),
402  getInstrName(PtrInc, CastNodeNameSuffix), InsPoint);
403  else
404  NewBasePtr = PtrInc;
405 
406  if (Instruction *IDel = dyn_cast<Instruction>(BasePtr))
407  BBChanged.insert(IDel->getParent());
408  BasePtr->replaceAllUsesWith(NewBasePtr);
410 
411  // Keep track of the replacement pointer values we've inserted so that we
412  // don't generate more pointer values than necessary.
413  SmallPtrSet<Value *, 16> NewPtrs;
414  NewPtrs.insert(NewBasePtr);
415 
416  for (auto I = std::next(BucketChain.Elements.begin()),
417  IE = BucketChain.Elements.end(); I != IE; ++I) {
418  Value *Ptr = GetPointerOperand(I->Instr);
419  assert(Ptr && "No pointer operand");
420  if (NewPtrs.count(Ptr))
421  continue;
422 
423  Instruction *RealNewPtr;
424  if (!I->Offset || I->Offset->getValue()->isZero()) {
425  RealNewPtr = NewBasePtr;
426  } else {
427  Instruction *PtrIP = dyn_cast<Instruction>(Ptr);
428  if (PtrIP && isa<Instruction>(NewBasePtr) &&
429  cast<Instruction>(NewBasePtr)->getParent() == PtrIP->getParent())
430  PtrIP = nullptr;
431  else if (PtrIP && isa<PHINode>(PtrIP))
432  PtrIP = &*PtrIP->getParent()->getFirstInsertionPt();
433  else if (!PtrIP)
434  PtrIP = I->Instr;
435 
437  I8Ty, PtrInc, I->Offset->getValue(),
438  getInstrName(I->Instr, GEPNodeOffNameSuffix), PtrIP);
439  if (!PtrIP)
440  NewPtr->insertAfter(cast<Instruction>(PtrInc));
441  NewPtr->setIsInBounds(IsPtrInBounds(Ptr));
442  RealNewPtr = NewPtr;
443  }
444 
445  if (Instruction *IDel = dyn_cast<Instruction>(Ptr))
446  BBChanged.insert(IDel->getParent());
447 
448  Instruction *ReplNewPtr;
449  if (Ptr->getType() != RealNewPtr->getType()) {
450  ReplNewPtr = new BitCastInst(RealNewPtr, Ptr->getType(),
452  ReplNewPtr->insertAfter(RealNewPtr);
453  } else
454  ReplNewPtr = RealNewPtr;
455 
456  Ptr->replaceAllUsesWith(ReplNewPtr);
458 
459  NewPtrs.insert(RealNewPtr);
460  }
461 
462  MadeChange = true;
463  UpdFormChainRewritten++;
464 
465  return MadeChange;
466 }
467 
468 bool PPCLoopPreIncPrep::updateFormPrep(Loop *L,
469  SmallVector<Bucket, 16> &Buckets) {
470  bool MadeChange = false;
471  if (Buckets.empty())
472  return MadeChange;
473  SmallSet<BasicBlock *, 16> BBChanged;
474  for (auto &Bucket : Buckets)
475  // The base address of each bucket is transformed into a phi and the others
476  // are rewritten based on new base.
477  if (prepareBaseForUpdateFormChain(Bucket))
478  MadeChange |= rewriteLoadStores(L, Bucket, BBChanged);
479  if (MadeChange)
480  for (auto &BB : L->blocks())
481  if (BBChanged.count(BB))
482  DeleteDeadPHIs(BB);
483  return MadeChange;
484 }
485 
486 // In order to prepare for the pre-increment a PHI is added.
487 // This function will check to see if that PHI already exists and will return
488 // true if it found an existing PHI with the same start and increment as the
489 // one we wanted to create.
490 bool PPCLoopPreIncPrep::alreadyPrepared(Loop *L, Instruction* MemI,
491  const SCEV *BasePtrStartSCEV,
492  const SCEVConstant *BasePtrIncSCEV) {
493  BasicBlock *BB = MemI->getParent();
494  if (!BB)
495  return false;
496 
497  BasicBlock *PredBB = L->getLoopPredecessor();
498  BasicBlock *LatchBB = L->getLoopLatch();
499 
500  if (!PredBB || !LatchBB)
501  return false;
502 
503  // Run through the PHIs and see if we have some that looks like a preparation
505  for (auto & CurrentPHI : PHIIter) {
506  PHINode *CurrentPHINode = dyn_cast<PHINode>(&CurrentPHI);
507  if (!CurrentPHINode)
508  continue;
509 
510  if (!SE->isSCEVable(CurrentPHINode->getType()))
511  continue;
512 
513  const SCEV *PHISCEV = SE->getSCEVAtScope(CurrentPHINode, L);
514 
515  const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast<SCEVAddRecExpr>(PHISCEV);
516  if (!PHIBasePtrSCEV)
517  continue;
518 
519  const SCEVConstant *PHIBasePtrIncSCEV =
520  dyn_cast<SCEVConstant>(PHIBasePtrSCEV->getStepRecurrence(*SE));
521  if (!PHIBasePtrIncSCEV)
522  continue;
523 
524  if (CurrentPHINode->getNumIncomingValues() == 2) {
525  if ((CurrentPHINode->getIncomingBlock(0) == LatchBB &&
526  CurrentPHINode->getIncomingBlock(1) == PredBB) ||
527  (CurrentPHINode->getIncomingBlock(1) == LatchBB &&
528  CurrentPHINode->getIncomingBlock(0) == PredBB)) {
529  if (PHIBasePtrSCEV->getStart() == BasePtrStartSCEV &&
530  PHIBasePtrIncSCEV == BasePtrIncSCEV) {
531  // The existing PHI (CurrentPHINode) has the same start and increment
532  // as the PHI that we wanted to create.
533  ++PHINodeAlreadyExists;
534  return true;
535  }
536  }
537  }
538  }
539  return false;
540 }
541 
542 bool PPCLoopPreIncPrep::runOnLoop(Loop *L) {
543  bool MadeChange = false;
544 
545  // Only prep. the inner-most loop
546  if (!L->empty())
547  return MadeChange;
548 
549  LLVM_DEBUG(dbgs() << "PIP: Examining: " << *L << "\n");
550 
551  BasicBlock *LoopPredecessor = L->getLoopPredecessor();
552  // If there is no loop predecessor, or the loop predecessor's terminator
553  // returns a value (which might contribute to determining the loop's
554  // iteration space), insert a new preheader for the loop.
555  if (!LoopPredecessor ||
556  !LoopPredecessor->getTerminator()->getType()->isVoidTy()) {
557  LoopPredecessor = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA);
558  if (LoopPredecessor)
559  MadeChange = true;
560  }
561  if (!LoopPredecessor) {
562  LLVM_DEBUG(dbgs() << "PIP fails since no predecessor for current loop.\n");
563  return MadeChange;
564  }
565 
566  // Check if a load/store has update form. This lambda is used by function
567  // collectCandidates which can collect candidates for types defined by lambda.
568  auto isUpdateFormCandidate = [&] (const Instruction *I,
569  const Value *PtrValue) {
570  assert((PtrValue && I) && "Invalid parameter!");
571  // There are no update forms for Altivec vector load/stores.
572  if (ST && ST->hasAltivec() &&
573  PtrValue->getType()->getPointerElementType()->isVectorTy())
574  return false;
575  // See getPreIndexedAddressParts, the displacement for LDU/STDU has to
576  // be 4's multiple (DS-form). For i64 loads/stores when the displacement
577  // fits in a 16-bit signed field but isn't a multiple of 4, it will be
578  // useless and possible to break some original well-form addressing mode
579  // to make this pre-inc prep for it.
580  if (PtrValue->getType()->getPointerElementType()->isIntegerTy(64)) {
581  const SCEV *LSCEV = SE->getSCEVAtScope(const_cast<Value *>(PtrValue), L);
582  const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(LSCEV);
583  if (!LARSCEV || LARSCEV->getLoop() != L)
584  return false;
585  if (const SCEVConstant *StepConst =
586  dyn_cast<SCEVConstant>(LARSCEV->getStepRecurrence(*SE))) {
587  const APInt &ConstInt = StepConst->getValue()->getValue();
588  if (ConstInt.isSignedIntN(16) && ConstInt.srem(4) != 0)
589  return false;
590  }
591  }
592  return true;
593  };
594 
595  // Collect buckets of comparable addresses used by loads, stores and prefetch
596  // intrinsic for update form.
597  SmallVector<Bucket, 16> UpdateFormBuckets =
598  collectCandidates(L, isUpdateFormCandidate, MaxVars);
599 
600  // Prepare for update form.
601  if (!UpdateFormBuckets.empty())
602  MadeChange |= updateFormPrep(L, UpdateFormBuckets);
603 
604  return MadeChange;
605 }
static std::string getInstrName(const Value *I, const std::string Suffix)
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:209
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
The main scalar evolution driver.
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:909
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:635
An instruction for reading from memory.
Definition: Instructions.h:169
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:144
loop data prefetch
static Value * GetPointerOperand(Value *MemI)
constexpr double phi
Definition: MathExtras.h:71
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:140
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Definition: BitVector.h:937
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
void setIsInBounds(bool b=true)
Set or clear the inbounds flag on this GEP instruction.
BlockT * getHeader() const
Definition: LoopInfo.h:105
#define DEBUG_TYPE
ConstantInt * getValue() const
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
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:325
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
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
std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type cast(const Y &Val)
Definition: Casting.h:249
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:883
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:196
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:223
bool hasName() const
Definition: Value.h:252
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:46
df_iterator< T > df_end(const T &G)
static const std::string GEPNodeOffNameSuffix
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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:467
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
Represent the analysis usage information of a pass.
static const std::string GEPNodeIncNameSuffix
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
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
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:180
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:440
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:224
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:61
static const std::string CastNodeNameSuffix
BlockT * getLoopPredecessor() const
If the given loop&#39;s header has exactly one unique predecessor outside the loop, return it...
Definition: LoopInfoImpl.h:188
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
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...
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:124
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...
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:509
APInt srem(const APInt &RHS) const
Function for signed remainder operation.
Definition: APInt.cpp:1739
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
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
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:329
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:151
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
FunctionPass * createPPCLoopPreIncPrepPass(PPCTargetMachine &TM)
aarch64 promote const
LLVM Value Representation.
Definition: Value.h:74
static const char * name
static const Function * getParent(const Value *V)
BasicBlock * InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
InsertPreheaderForLoop - Once we discover that a loop doesn&#39;t have a preheader, this method is called...
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:1208
print Print MemDeps of function
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...
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:161
static const std::string PHINodeNameSuffix
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:178
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.
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164