LLVM  12.0.0git
PPCLoopInstrFormPrep.cpp
Go to the documentation of this file.
1 //===------ PPCLoopInstrFormPrep.cpp - Loop Instr Form 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 ppc preferred addressing
10 // modes, leveraging different instruction form. (eg: DS/DQ form, D/DS form with
11 // update)
12 // Additional PHIs are created for loop induction variables used by load/store
13 // instructions so that preferred addressing modes can be used.
14 //
15 // 1: DS/DQ form preparation, prepare the load/store instructions so that they
16 // can satisfy the DS/DQ form displacement requirements.
17 // Generically, this means transforming loops like this:
18 // for (int i = 0; i < n; ++i) {
19 // unsigned long x1 = *(unsigned long *)(p + i + 5);
20 // unsigned long x2 = *(unsigned long *)(p + i + 9);
21 // }
22 //
23 // to look like this:
24 //
25 // unsigned NewP = p + 5;
26 // for (int i = 0; i < n; ++i) {
27 // unsigned long x1 = *(unsigned long *)(i + NewP);
28 // unsigned long x2 = *(unsigned long *)(i + NewP + 4);
29 // }
30 //
31 // 2: D/DS form with update preparation, prepare the load/store instructions so
32 // that we can use update form to do pre-increment.
33 // Generically, this means transforming loops like this:
34 // for (int i = 0; i < n; ++i)
35 // array[i] = c;
36 //
37 // to look like this:
38 //
39 // T *p = array[-1];
40 // for (int i = 0; i < n; ++i)
41 // *++p = c;
42 //===----------------------------------------------------------------------===//
43 
44 #define DEBUG_TYPE "ppc-loop-instr-form-prep"
45 
46 #include "PPC.h"
47 #include "PPCSubtarget.h"
48 #include "PPCTargetMachine.h"
50 #include "llvm/ADT/SmallPtrSet.h"
51 #include "llvm/ADT/SmallSet.h"
52 #include "llvm/ADT/SmallVector.h"
53 #include "llvm/ADT/Statistic.h"
54 #include "llvm/Analysis/LoopInfo.h"
57 #include "llvm/IR/BasicBlock.h"
58 #include "llvm/IR/CFG.h"
59 #include "llvm/IR/Dominators.h"
60 #include "llvm/IR/Instruction.h"
61 #include "llvm/IR/Instructions.h"
62 #include "llvm/IR/IntrinsicInst.h"
63 #include "llvm/IR/IntrinsicsPowerPC.h"
64 #include "llvm/IR/Module.h"
65 #include "llvm/IR/Type.h"
66 #include "llvm/IR/Value.h"
67 #include "llvm/InitializePasses.h"
68 #include "llvm/Pass.h"
69 #include "llvm/Support/Casting.h"
71 #include "llvm/Support/Debug.h"
72 #include "llvm/Transforms/Scalar.h"
73 #include "llvm/Transforms/Utils.h"
78 #include <cassert>
79 #include <iterator>
80 #include <utility>
81 
82 using namespace llvm;
83 
84 static cl::opt<unsigned> MaxVarsPrep("ppc-formprep-max-vars",
85  cl::Hidden, cl::init(24),
86  cl::desc("Potential common base number threshold per function for PPC loop "
87  "prep"));
88 
89 static cl::opt<bool> PreferUpdateForm("ppc-formprep-prefer-update",
90  cl::init(true), cl::Hidden,
91  cl::desc("prefer update form when ds form is also a update form"));
92 
93 // Sum of following 3 per loop thresholds for all loops can not be larger
94 // than MaxVarsPrep.
95 // now the thresholds for each kind prep are exterimental values on Power9.
96 static cl::opt<unsigned> MaxVarsUpdateForm("ppc-preinc-prep-max-vars",
97  cl::Hidden, cl::init(3),
98  cl::desc("Potential PHI threshold per loop for PPC loop prep of update "
99  "form"));
100 
101 static cl::opt<unsigned> MaxVarsDSForm("ppc-dsprep-max-vars",
102  cl::Hidden, cl::init(3),
103  cl::desc("Potential PHI threshold per loop for PPC loop prep of DS form"));
104 
105 static cl::opt<unsigned> MaxVarsDQForm("ppc-dqprep-max-vars",
106  cl::Hidden, cl::init(8),
107  cl::desc("Potential PHI threshold per loop for PPC loop prep of DQ form"));
108 
109 
110 // If would not be profitable if the common base has only one load/store, ISEL
111 // should already be able to choose best load/store form based on offset for
112 // single load/store. Set minimal profitable value default to 2 and make it as
113 // an option.
114 static cl::opt<unsigned> DispFormPrepMinThreshold("ppc-dispprep-min-threshold",
115  cl::Hidden, cl::init(2),
116  cl::desc("Minimal common base load/store instructions triggering DS/DQ form "
117  "preparation"));
118 
119 STATISTIC(PHINodeAlreadyExistsUpdate, "PHI node already in pre-increment form");
120 STATISTIC(PHINodeAlreadyExistsDS, "PHI node already in DS form");
121 STATISTIC(PHINodeAlreadyExistsDQ, "PHI node already in DQ form");
122 STATISTIC(DSFormChainRewritten, "Num of DS form chain rewritten");
123 STATISTIC(DQFormChainRewritten, "Num of DQ form chain rewritten");
124 STATISTIC(UpdFormChainRewritten, "Num of update form chain rewritten");
125 
126 namespace {
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  // "UpdateForm" is not a real PPC instruction form, it stands for dform
144  // load/store with update like ldu/stdu, or Prefetch intrinsic.
145  // For DS form instructions, their displacements must be multiple of 4.
146  // For DQ form instructions, their displacements must be multiple of 16.
147  enum InstrForm { UpdateForm = 1, DSForm = 4, DQForm = 16 };
148 
149  class PPCLoopInstrFormPrep : public FunctionPass {
150  public:
151  static char ID; // Pass ID, replacement for typeid
152 
153  PPCLoopInstrFormPrep() : FunctionPass(ID) {
155  }
156 
157  PPCLoopInstrFormPrep(PPCTargetMachine &TM) : FunctionPass(ID), TM(&TM) {
159  }
160 
161  void getAnalysisUsage(AnalysisUsage &AU) const override {
166  }
167 
168  bool runOnFunction(Function &F) override;
169 
170  private:
171  PPCTargetMachine *TM = nullptr;
172  const PPCSubtarget *ST;
173  DominatorTree *DT;
174  LoopInfo *LI;
175  ScalarEvolution *SE;
176  bool PreserveLCSSA;
177 
178  /// Successful preparation number for Update/DS/DQ form in all inner most
179  /// loops. One successful preparation will put one common base out of loop,
180  /// this may leads to register presure like LICM does.
181  /// Make sure total preparation number can be controlled by option.
182  unsigned SuccPrepCount;
183 
184  bool runOnLoop(Loop *L);
185 
186  /// Check if required PHI node is already exist in Loop \p L.
187  bool alreadyPrepared(Loop *L, Instruction* MemI,
188  const SCEV *BasePtrStartSCEV,
189  const SCEVConstant *BasePtrIncSCEV,
190  InstrForm Form);
191 
192  /// Collect condition matched(\p isValidCandidate() returns true)
193  /// candidates in Loop \p L.
195  collectCandidates(Loop *L,
196  std::function<bool(const Instruction *, const Value *)>
197  isValidCandidate,
198  unsigned MaxCandidateNum);
199 
200  /// Add a candidate to candidates \p Buckets.
201  void addOneCandidate(Instruction *MemI, const SCEV *LSCEV,
202  SmallVector<Bucket, 16> &Buckets,
203  unsigned MaxCandidateNum);
204 
205  /// Prepare all candidates in \p Buckets for update form.
206  bool updateFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets);
207 
208  /// Prepare all candidates in \p Buckets for displacement form, now for
209  /// ds/dq.
210  bool dispFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets,
211  InstrForm Form);
212 
213  /// Prepare for one chain \p BucketChain, find the best base element and
214  /// update all other elements in \p BucketChain accordingly.
215  /// \p Form is used to find the best base element.
216  /// If success, best base element must be stored as the first element of
217  /// \p BucketChain.
218  /// Return false if no base element found, otherwise return true.
219  bool prepareBaseForDispFormChain(Bucket &BucketChain,
220  InstrForm Form);
221 
222  /// Prepare for one chain \p BucketChain, find the best base element and
223  /// update all other elements in \p BucketChain accordingly.
224  /// If success, best base element must be stored as the first element of
225  /// \p BucketChain.
226  /// Return false if no base element found, otherwise return true.
227  bool prepareBaseForUpdateFormChain(Bucket &BucketChain);
228 
229  /// Rewrite load/store instructions in \p BucketChain according to
230  /// preparation.
231  bool rewriteLoadStores(Loop *L, Bucket &BucketChain,
232  SmallSet<BasicBlock *, 16> &BBChanged,
233  InstrForm Form);
234  };
235 
236 } // end anonymous namespace
237 
238 char PPCLoopInstrFormPrep::ID = 0;
239 static const char *name = "Prepare loop for ppc preferred instruction forms";
240 INITIALIZE_PASS_BEGIN(PPCLoopInstrFormPrep, DEBUG_TYPE, name, false, false)
243 INITIALIZE_PASS_END(PPCLoopInstrFormPrep, DEBUG_TYPE, name, false, false)
244 
245 static constexpr StringRef PHINodeNameSuffix = ".phi";
246 static constexpr StringRef CastNodeNameSuffix = ".cast";
247 static constexpr StringRef GEPNodeIncNameSuffix = ".inc";
248 static constexpr StringRef GEPNodeOffNameSuffix = ".off";
249 
251  return new PPCLoopInstrFormPrep(TM);
252 }
253 
254 static bool IsPtrInBounds(Value *BasePtr) {
255  Value *StrippedBasePtr = BasePtr;
256  while (BitCastInst *BC = dyn_cast<BitCastInst>(StrippedBasePtr))
257  StrippedBasePtr = BC->getOperand(0);
258  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(StrippedBasePtr))
259  return GEP->isInBounds();
260 
261  return false;
262 }
263 
264 static std::string getInstrName(const Value *I, StringRef Suffix) {
265  assert(I && "Invalid paramater!");
266  if (I->hasName())
267  return (I->getName() + Suffix).str();
268  else
269  return "";
270 }
271 
272 static Value *GetPointerOperand(Value *MemI) {
273  if (LoadInst *LMemI = dyn_cast<LoadInst>(MemI)) {
274  return LMemI->getPointerOperand();
275  } else if (StoreInst *SMemI = dyn_cast<StoreInst>(MemI)) {
276  return SMemI->getPointerOperand();
277  } else if (IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(MemI)) {
278  if (IMemI->getIntrinsicID() == Intrinsic::prefetch ||
279  IMemI->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp)
280  return IMemI->getArgOperand(0);
281  if (IMemI->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp)
282  return IMemI->getArgOperand(1);
283  }
284 
285  return nullptr;
286 }
287 
289  if (skipFunction(F))
290  return false;
291 
292  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
293  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
294  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
295  DT = DTWP ? &DTWP->getDomTree() : nullptr;
296  PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
297  ST = TM ? TM->getSubtargetImpl(F) : nullptr;
298  SuccPrepCount = 0;
299 
300  bool MadeChange = false;
301 
302  for (auto I = LI->begin(), IE = LI->end(); I != IE; ++I)
303  for (auto L = df_begin(*I), LE = df_end(*I); L != LE; ++L)
304  MadeChange |= runOnLoop(*L);
305 
306  return MadeChange;
307 }
308 
309 void PPCLoopInstrFormPrep::addOneCandidate(Instruction *MemI, const SCEV *LSCEV,
310  SmallVector<Bucket, 16> &Buckets,
311  unsigned MaxCandidateNum) {
312  assert((MemI && GetPointerOperand(MemI)) &&
313  "Candidate should be a memory instruction.");
314  assert(LSCEV && "Invalid SCEV for Ptr value.");
315  bool FoundBucket = false;
316  for (auto &B : Buckets) {
317  const SCEV *Diff = SE->getMinusSCEV(LSCEV, B.BaseSCEV);
318  if (const auto *CDiff = dyn_cast<SCEVConstant>(Diff)) {
319  B.Elements.push_back(BucketElement(CDiff, MemI));
320  FoundBucket = true;
321  break;
322  }
323  }
324 
325  if (!FoundBucket) {
326  if (Buckets.size() == MaxCandidateNum)
327  return;
328  Buckets.push_back(Bucket(LSCEV, MemI));
329  }
330 }
331 
332 SmallVector<Bucket, 16> PPCLoopInstrFormPrep::collectCandidates(
333  Loop *L,
334  std::function<bool(const Instruction *, const Value *)> isValidCandidate,
335  unsigned MaxCandidateNum) {
336  SmallVector<Bucket, 16> Buckets;
337  for (const auto &BB : L->blocks())
338  for (auto &J : *BB) {
339  Value *PtrValue;
340  Instruction *MemI;
341 
342  if (LoadInst *LMemI = dyn_cast<LoadInst>(&J)) {
343  MemI = LMemI;
344  PtrValue = LMemI->getPointerOperand();
345  } else if (StoreInst *SMemI = dyn_cast<StoreInst>(&J)) {
346  MemI = SMemI;
347  PtrValue = SMemI->getPointerOperand();
348  } else if (IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(&J)) {
349  if (IMemI->getIntrinsicID() == Intrinsic::prefetch ||
350  IMemI->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp) {
351  MemI = IMemI;
352  PtrValue = IMemI->getArgOperand(0);
353  } else if (IMemI->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp) {
354  MemI = IMemI;
355  PtrValue = IMemI->getArgOperand(1);
356  } else continue;
357  } else continue;
358 
359  unsigned PtrAddrSpace = PtrValue->getType()->getPointerAddressSpace();
360  if (PtrAddrSpace)
361  continue;
362 
363  if (L->isLoopInvariant(PtrValue))
364  continue;
365 
366  const SCEV *LSCEV = SE->getSCEVAtScope(PtrValue, L);
367  const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(LSCEV);
368  if (!LARSCEV || LARSCEV->getLoop() != L)
369  continue;
370 
371  if (isValidCandidate(&J, PtrValue))
372  addOneCandidate(MemI, LSCEV, Buckets, MaxCandidateNum);
373  }
374  return Buckets;
375 }
376 
377 bool PPCLoopInstrFormPrep::prepareBaseForDispFormChain(Bucket &BucketChain,
378  InstrForm Form) {
379  // RemainderOffsetInfo details:
380  // key: value of (Offset urem DispConstraint). For DSForm, it can
381  // be [0, 4).
382  // first of pair: the index of first BucketElement whose remainder is equal
383  // to key. For key 0, this value must be 0.
384  // second of pair: number of load/stores with the same remainder.
386 
387  for (unsigned j = 0, je = BucketChain.Elements.size(); j != je; ++j) {
388  if (!BucketChain.Elements[j].Offset)
389  RemainderOffsetInfo[0] = std::make_pair(0, 1);
390  else {
391  unsigned Remainder =
392  BucketChain.Elements[j].Offset->getAPInt().urem(Form);
393  if (RemainderOffsetInfo.find(Remainder) == RemainderOffsetInfo.end())
394  RemainderOffsetInfo[Remainder] = std::make_pair(j, 1);
395  else
396  RemainderOffsetInfo[Remainder].second++;
397  }
398  }
399  // Currently we choose the most profitable base as the one which has the max
400  // number of load/store with same remainder.
401  // FIXME: adjust the base selection strategy according to load/store offset
402  // distribution.
403  // For example, if we have one candidate chain for DS form preparation, which
404  // contains following load/stores with different remainders:
405  // 1: 10 load/store whose remainder is 1;
406  // 2: 9 load/store whose remainder is 2;
407  // 3: 1 for remainder 3 and 0 for remainder 0;
408  // Now we will choose the first load/store whose remainder is 1 as base and
409  // adjust all other load/stores according to new base, so we will get 10 DS
410  // form and 10 X form.
411  // But we should be more clever, for this case we could use two bases, one for
412  // remainder 1 and the other for remainder 2, thus we could get 19 DS form and 1
413  // X form.
414  unsigned MaxCountRemainder = 0;
415  for (unsigned j = 0; j < (unsigned)Form; j++)
416  if ((RemainderOffsetInfo.find(j) != RemainderOffsetInfo.end()) &&
417  RemainderOffsetInfo[j].second >
418  RemainderOffsetInfo[MaxCountRemainder].second)
419  MaxCountRemainder = j;
420 
421  // Abort when there are too few insts with common base.
422  if (RemainderOffsetInfo[MaxCountRemainder].second < DispFormPrepMinThreshold)
423  return false;
424 
425  // If the first value is most profitable, no needed to adjust BucketChain
426  // elements as they are substracted the first value when collecting.
427  if (MaxCountRemainder == 0)
428  return true;
429 
430  // Adjust load/store to the new chosen base.
431  const SCEV *Offset =
432  BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first].Offset;
433  BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset);
434  for (auto &E : BucketChain.Elements) {
435  if (E.Offset)
436  E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(E.Offset, Offset));
437  else
438  E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(Offset));
439  }
440 
441  std::swap(BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first],
442  BucketChain.Elements[0]);
443  return true;
444 }
445 
446 // FIXME: implement a more clever base choosing policy.
447 // Currently we always choose an exist load/store offset. This maybe lead to
448 // suboptimal code sequences. For example, for one DS chain with offsets
449 // {-32769, 2003, 2007, 2011}, we choose -32769 as base offset, and left disp
450 // for load/stores are {0, 34772, 34776, 34780}. Though each offset now is a
451 // multipler of 4, it cannot be represented by sint16.
452 bool PPCLoopInstrFormPrep::prepareBaseForUpdateFormChain(Bucket &BucketChain) {
453  // We have a choice now of which instruction's memory operand we use as the
454  // base for the generated PHI. Always picking the first instruction in each
455  // bucket does not work well, specifically because that instruction might
456  // be a prefetch (and there are no pre-increment dcbt variants). Otherwise,
457  // the choice is somewhat arbitrary, because the backend will happily
458  // generate direct offsets from both the pre-incremented and
459  // post-incremented pointer values. Thus, we'll pick the first non-prefetch
460  // instruction in each bucket, and adjust the recurrence and other offsets
461  // accordingly.
462  for (int j = 0, je = BucketChain.Elements.size(); j != je; ++j) {
463  if (auto *II = dyn_cast<IntrinsicInst>(BucketChain.Elements[j].Instr))
464  if (II->getIntrinsicID() == Intrinsic::prefetch)
465  continue;
466 
467  // If we'd otherwise pick the first element anyway, there's nothing to do.
468  if (j == 0)
469  break;
470 
471  // If our chosen element has no offset from the base pointer, there's
472  // nothing to do.
473  if (!BucketChain.Elements[j].Offset ||
474  BucketChain.Elements[j].Offset->isZero())
475  break;
476 
477  const SCEV *Offset = BucketChain.Elements[j].Offset;
478  BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset);
479  for (auto &E : BucketChain.Elements) {
480  if (E.Offset)
481  E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(E.Offset, Offset));
482  else
483  E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(Offset));
484  }
485 
486  std::swap(BucketChain.Elements[j], BucketChain.Elements[0]);
487  break;
488  }
489  return true;
490 }
491 
492 bool PPCLoopInstrFormPrep::rewriteLoadStores(Loop *L, Bucket &BucketChain,
493  SmallSet<BasicBlock *, 16> &BBChanged,
494  InstrForm Form) {
495  bool MadeChange = false;
496  const SCEVAddRecExpr *BasePtrSCEV =
497  cast<SCEVAddRecExpr>(BucketChain.BaseSCEV);
498  if (!BasePtrSCEV->isAffine())
499  return MadeChange;
500 
501  LLVM_DEBUG(dbgs() << "PIP: Transforming: " << *BasePtrSCEV << "\n");
502 
503  assert(BasePtrSCEV->getLoop() == L && "AddRec for the wrong loop?");
504 
505  // The instruction corresponding to the Bucket's BaseSCEV must be the first
506  // in the vector of elements.
507  Instruction *MemI = BucketChain.Elements.begin()->Instr;
509  assert(BasePtr && "No pointer operand");
510 
511  Type *I8Ty = Type::getInt8Ty(MemI->getParent()->getContext());
512  Type *I8PtrTy = Type::getInt8PtrTy(MemI->getParent()->getContext(),
513  BasePtr->getType()->getPointerAddressSpace());
514 
515  if (!SE->isLoopInvariant(BasePtrSCEV->getStart(), L))
516  return MadeChange;
517 
518  const SCEVConstant *BasePtrIncSCEV =
519  dyn_cast<SCEVConstant>(BasePtrSCEV->getStepRecurrence(*SE));
520  if (!BasePtrIncSCEV)
521  return MadeChange;
522 
523  // For some DS form load/store instructions, it can also be an update form,
524  // if the stride is a multipler of 4. Use update form if prefer it.
525  bool CanPreInc = (Form == UpdateForm ||
526  ((Form == DSForm) && !BasePtrIncSCEV->getAPInt().urem(4) &&
528  const SCEV *BasePtrStartSCEV = nullptr;
529  if (CanPreInc)
530  BasePtrStartSCEV =
531  SE->getMinusSCEV(BasePtrSCEV->getStart(), BasePtrIncSCEV);
532  else
533  BasePtrStartSCEV = BasePtrSCEV->getStart();
534 
535  if (!isSafeToExpand(BasePtrStartSCEV, *SE))
536  return MadeChange;
537 
538  if (alreadyPrepared(L, MemI, BasePtrStartSCEV, BasePtrIncSCEV, Form))
539  return MadeChange;
540 
541  LLVM_DEBUG(dbgs() << "PIP: New start is: " << *BasePtrStartSCEV << "\n");
542 
543  BasicBlock *Header = L->getHeader();
544  unsigned HeaderLoopPredCount = pred_size(Header);
545  BasicBlock *LoopPredecessor = L->getLoopPredecessor();
546 
547  PHINode *NewPHI =
548  PHINode::Create(I8PtrTy, HeaderLoopPredCount,
550  Header->getFirstNonPHI());
551 
552  SCEVExpander SCEVE(*SE, Header->getModule()->getDataLayout(), "pistart");
553  Value *BasePtrStart = SCEVE.expandCodeFor(BasePtrStartSCEV, I8PtrTy,
554  LoopPredecessor->getTerminator());
555 
556  // Note that LoopPredecessor might occur in the predecessor list multiple
557  // times, and we need to add it the right number of times.
558  for (auto PI : predecessors(Header)) {
559  if (PI != LoopPredecessor)
560  continue;
561 
562  NewPHI->addIncoming(BasePtrStart, LoopPredecessor);
563  }
564 
565  Instruction *PtrInc = nullptr;
566  Instruction *NewBasePtr = nullptr;
567  if (CanPreInc) {
568  Instruction *InsPoint = &*Header->getFirstInsertionPt();
569  PtrInc = GetElementPtrInst::Create(
570  I8Ty, NewPHI, BasePtrIncSCEV->getValue(),
571  getInstrName(MemI, GEPNodeIncNameSuffix), InsPoint);
572  cast<GetElementPtrInst>(PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr));
573  for (auto PI : predecessors(Header)) {
574  if (PI == LoopPredecessor)
575  continue;
576 
577  NewPHI->addIncoming(PtrInc, PI);
578  }
579  if (PtrInc->getType() != BasePtr->getType())
580  NewBasePtr = new BitCastInst(
581  PtrInc, BasePtr->getType(),
582  getInstrName(PtrInc, CastNodeNameSuffix), InsPoint);
583  else
584  NewBasePtr = PtrInc;
585  } else {
586  // Note that LoopPredecessor might occur in the predecessor list multiple
587  // times, and we need to make sure no more incoming value for them in PHI.
588  for (auto PI : predecessors(Header)) {
589  if (PI == LoopPredecessor)
590  continue;
591 
592  // For the latch predecessor, we need to insert a GEP just before the
593  // terminator to increase the address.
594  BasicBlock *BB = PI;
595  Instruction *InsPoint = BB->getTerminator();
596  PtrInc = GetElementPtrInst::Create(
597  I8Ty, NewPHI, BasePtrIncSCEV->getValue(),
598  getInstrName(MemI, GEPNodeIncNameSuffix), InsPoint);
599 
600  cast<GetElementPtrInst>(PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr));
601 
602  NewPHI->addIncoming(PtrInc, PI);
603  }
604  PtrInc = NewPHI;
605  if (NewPHI->getType() != BasePtr->getType())
606  NewBasePtr =
607  new BitCastInst(NewPHI, BasePtr->getType(),
609  &*Header->getFirstInsertionPt());
610  else
611  NewBasePtr = NewPHI;
612  }
613 
614  // Clear the rewriter cache, because values that are in the rewriter's cache
615  // can be deleted below, causing the AssertingVH in the cache to trigger.
616  SCEVE.clear();
617 
618  if (Instruction *IDel = dyn_cast<Instruction>(BasePtr))
619  BBChanged.insert(IDel->getParent());
620  BasePtr->replaceAllUsesWith(NewBasePtr);
622 
623  // Keep track of the replacement pointer values we've inserted so that we
624  // don't generate more pointer values than necessary.
625  SmallPtrSet<Value *, 16> NewPtrs;
626  NewPtrs.insert(NewBasePtr);
627 
628  for (auto I = std::next(BucketChain.Elements.begin()),
629  IE = BucketChain.Elements.end(); I != IE; ++I) {
630  Value *Ptr = GetPointerOperand(I->Instr);
631  assert(Ptr && "No pointer operand");
632  if (NewPtrs.count(Ptr))
633  continue;
634 
635  Instruction *RealNewPtr;
636  if (!I->Offset || I->Offset->getValue()->isZero()) {
637  RealNewPtr = NewBasePtr;
638  } else {
639  Instruction *PtrIP = dyn_cast<Instruction>(Ptr);
640  if (PtrIP && isa<Instruction>(NewBasePtr) &&
641  cast<Instruction>(NewBasePtr)->getParent() == PtrIP->getParent())
642  PtrIP = nullptr;
643  else if (PtrIP && isa<PHINode>(PtrIP))
644  PtrIP = &*PtrIP->getParent()->getFirstInsertionPt();
645  else if (!PtrIP)
646  PtrIP = I->Instr;
647 
649  I8Ty, PtrInc, I->Offset->getValue(),
650  getInstrName(I->Instr, GEPNodeOffNameSuffix), PtrIP);
651  if (!PtrIP)
652  NewPtr->insertAfter(cast<Instruction>(PtrInc));
653  NewPtr->setIsInBounds(IsPtrInBounds(Ptr));
654  RealNewPtr = NewPtr;
655  }
656 
657  if (Instruction *IDel = dyn_cast<Instruction>(Ptr))
658  BBChanged.insert(IDel->getParent());
659 
660  Instruction *ReplNewPtr;
661  if (Ptr->getType() != RealNewPtr->getType()) {
662  ReplNewPtr = new BitCastInst(RealNewPtr, Ptr->getType(),
664  ReplNewPtr->insertAfter(RealNewPtr);
665  } else
666  ReplNewPtr = RealNewPtr;
667 
668  Ptr->replaceAllUsesWith(ReplNewPtr);
670 
671  NewPtrs.insert(RealNewPtr);
672  }
673 
674  MadeChange = true;
675 
676  SuccPrepCount++;
677 
678  if (Form == DSForm && !CanPreInc)
679  DSFormChainRewritten++;
680  else if (Form == DQForm)
681  DQFormChainRewritten++;
682  else if (Form == UpdateForm || (Form == DSForm && CanPreInc))
683  UpdFormChainRewritten++;
684 
685  return MadeChange;
686 }
687 
688 bool PPCLoopInstrFormPrep::updateFormPrep(Loop *L,
689  SmallVector<Bucket, 16> &Buckets) {
690  bool MadeChange = false;
691  if (Buckets.empty())
692  return MadeChange;
693  SmallSet<BasicBlock *, 16> BBChanged;
694  for (auto &Bucket : Buckets)
695  // The base address of each bucket is transformed into a phi and the others
696  // are rewritten based on new base.
697  if (prepareBaseForUpdateFormChain(Bucket))
698  MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, UpdateForm);
699 
700  if (MadeChange)
701  for (auto &BB : L->blocks())
702  if (BBChanged.count(BB))
703  DeleteDeadPHIs(BB);
704  return MadeChange;
705 }
706 
707 bool PPCLoopInstrFormPrep::dispFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets,
708  InstrForm Form) {
709  bool MadeChange = false;
710 
711  if (Buckets.empty())
712  return MadeChange;
713 
714  SmallSet<BasicBlock *, 16> BBChanged;
715  for (auto &Bucket : Buckets) {
716  if (Bucket.Elements.size() < DispFormPrepMinThreshold)
717  continue;
718  if (prepareBaseForDispFormChain(Bucket, Form))
719  MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, Form);
720  }
721 
722  if (MadeChange)
723  for (auto &BB : L->blocks())
724  if (BBChanged.count(BB))
725  DeleteDeadPHIs(BB);
726  return MadeChange;
727 }
728 
729 // In order to prepare for the preferred instruction form, a PHI is added.
730 // This function will check to see if that PHI already exists and will return
731 // true if it found an existing PHI with the matched start and increment as the
732 // one we wanted to create.
733 bool PPCLoopInstrFormPrep::alreadyPrepared(Loop *L, Instruction* MemI,
734  const SCEV *BasePtrStartSCEV,
735  const SCEVConstant *BasePtrIncSCEV,
736  InstrForm Form) {
737  BasicBlock *BB = MemI->getParent();
738  if (!BB)
739  return false;
740 
741  BasicBlock *PredBB = L->getLoopPredecessor();
742  BasicBlock *LatchBB = L->getLoopLatch();
743 
744  if (!PredBB || !LatchBB)
745  return false;
746 
747  // Run through the PHIs and see if we have some that looks like a preparation
749  for (auto & CurrentPHI : PHIIter) {
750  PHINode *CurrentPHINode = dyn_cast<PHINode>(&CurrentPHI);
751  if (!CurrentPHINode)
752  continue;
753 
754  if (!SE->isSCEVable(CurrentPHINode->getType()))
755  continue;
756 
757  const SCEV *PHISCEV = SE->getSCEVAtScope(CurrentPHINode, L);
758 
759  const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast<SCEVAddRecExpr>(PHISCEV);
760  if (!PHIBasePtrSCEV)
761  continue;
762 
763  const SCEVConstant *PHIBasePtrIncSCEV =
764  dyn_cast<SCEVConstant>(PHIBasePtrSCEV->getStepRecurrence(*SE));
765  if (!PHIBasePtrIncSCEV)
766  continue;
767 
768  if (CurrentPHINode->getNumIncomingValues() == 2) {
769  if ((CurrentPHINode->getIncomingBlock(0) == LatchBB &&
770  CurrentPHINode->getIncomingBlock(1) == PredBB) ||
771  (CurrentPHINode->getIncomingBlock(1) == LatchBB &&
772  CurrentPHINode->getIncomingBlock(0) == PredBB)) {
773  if (PHIBasePtrIncSCEV == BasePtrIncSCEV) {
774  // The existing PHI (CurrentPHINode) has the same start and increment
775  // as the PHI that we wanted to create.
776  if (Form == UpdateForm &&
777  PHIBasePtrSCEV->getStart() == BasePtrStartSCEV) {
778  ++PHINodeAlreadyExistsUpdate;
779  return true;
780  }
781  if (Form == DSForm || Form == DQForm) {
782  const SCEVConstant *Diff = dyn_cast<SCEVConstant>(
783  SE->getMinusSCEV(PHIBasePtrSCEV->getStart(), BasePtrStartSCEV));
784  if (Diff && !Diff->getAPInt().urem(Form)) {
785  if (Form == DSForm)
786  ++PHINodeAlreadyExistsDS;
787  else
788  ++PHINodeAlreadyExistsDQ;
789  return true;
790  }
791  }
792  }
793  }
794  }
795  }
796  return false;
797 }
798 
799 bool PPCLoopInstrFormPrep::runOnLoop(Loop *L) {
800  bool MadeChange = false;
801 
802  // Only prep. the inner-most loop
803  if (!L->isInnermost())
804  return MadeChange;
805 
806  // Return if already done enough preparation.
807  if (SuccPrepCount >= MaxVarsPrep)
808  return MadeChange;
809 
810  LLVM_DEBUG(dbgs() << "PIP: Examining: " << *L << "\n");
811 
812  BasicBlock *LoopPredecessor = L->getLoopPredecessor();
813  // If there is no loop predecessor, or the loop predecessor's terminator
814  // returns a value (which might contribute to determining the loop's
815  // iteration space), insert a new preheader for the loop.
816  if (!LoopPredecessor ||
817  !LoopPredecessor->getTerminator()->getType()->isVoidTy()) {
818  LoopPredecessor = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA);
819  if (LoopPredecessor)
820  MadeChange = true;
821  }
822  if (!LoopPredecessor) {
823  LLVM_DEBUG(dbgs() << "PIP fails since no predecessor for current loop.\n");
824  return MadeChange;
825  }
826  // Check if a load/store has update form. This lambda is used by function
827  // collectCandidates which can collect candidates for types defined by lambda.
828  auto isUpdateFormCandidate = [&] (const Instruction *I,
829  const Value *PtrValue) {
830  assert((PtrValue && I) && "Invalid parameter!");
831  // There are no update forms for Altivec vector load/stores.
832  if (ST && ST->hasAltivec() &&
833  PtrValue->getType()->getPointerElementType()->isVectorTy())
834  return false;
835  // There are no update forms for P10 lxvp/stxvp intrinsic.
836  auto *II = dyn_cast<IntrinsicInst>(I);
837  if (II && ((II->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp) ||
838  II->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp))
839  return false;
840  // See getPreIndexedAddressParts, the displacement for LDU/STDU has to
841  // be 4's multiple (DS-form). For i64 loads/stores when the displacement
842  // fits in a 16-bit signed field but isn't a multiple of 4, it will be
843  // useless and possible to break some original well-form addressing mode
844  // to make this pre-inc prep for it.
845  if (PtrValue->getType()->getPointerElementType()->isIntegerTy(64)) {
846  const SCEV *LSCEV = SE->getSCEVAtScope(const_cast<Value *>(PtrValue), L);
847  const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(LSCEV);
848  if (!LARSCEV || LARSCEV->getLoop() != L)
849  return false;
850  if (const SCEVConstant *StepConst =
851  dyn_cast<SCEVConstant>(LARSCEV->getStepRecurrence(*SE))) {
852  const APInt &ConstInt = StepConst->getValue()->getValue();
853  if (ConstInt.isSignedIntN(16) && ConstInt.srem(4) != 0)
854  return false;
855  }
856  }
857  return true;
858  };
859 
860  // Check if a load/store has DS form.
861  auto isDSFormCandidate = [] (const Instruction *I, const Value *PtrValue) {
862  assert((PtrValue && I) && "Invalid parameter!");
863  if (isa<IntrinsicInst>(I))
864  return false;
865  Type *PointerElementType = PtrValue->getType()->getPointerElementType();
866  return (PointerElementType->isIntegerTy(64)) ||
867  (PointerElementType->isFloatTy()) ||
868  (PointerElementType->isDoubleTy()) ||
869  (PointerElementType->isIntegerTy(32) &&
870  llvm::any_of(I->users(),
871  [](const User *U) { return isa<SExtInst>(U); }));
872  };
873 
874  // Check if a load/store has DQ form.
875  auto isDQFormCandidate = [&] (const Instruction *I, const Value *PtrValue) {
876  assert((PtrValue && I) && "Invalid parameter!");
877  // Check if it is a P10 lxvp/stxvp intrinsic.
878  auto *II = dyn_cast<IntrinsicInst>(I);
879  if (II)
880  return II->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp ||
881  II->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp;
882  // Check if it is a P9 vector load/store.
883  return ST && ST->hasP9Vector() &&
884  (PtrValue->getType()->getPointerElementType()->isVectorTy());
885  };
886 
887  // intrinsic for update form.
888  SmallVector<Bucket, 16> UpdateFormBuckets =
889  collectCandidates(L, isUpdateFormCandidate, MaxVarsUpdateForm);
890 
891  // Prepare for update form.
892  if (!UpdateFormBuckets.empty())
893  MadeChange |= updateFormPrep(L, UpdateFormBuckets);
894 
895  // Collect buckets of comparable addresses used by loads and stores for DS
896  // form.
897  SmallVector<Bucket, 16> DSFormBuckets =
898  collectCandidates(L, isDSFormCandidate, MaxVarsDSForm);
899 
900  // Prepare for DS form.
901  if (!DSFormBuckets.empty())
902  MadeChange |= dispFormPrep(L, DSFormBuckets, DSForm);
903 
904  // Collect buckets of comparable addresses used by loads and stores for DQ
905  // form.
906  SmallVector<Bucket, 16> DQFormBuckets =
907  collectCandidates(L, isDQFormCandidate, MaxVarsDQForm);
908 
909  // Prepare for DQ form.
910  if (!DQFormBuckets.empty())
911  MadeChange |= dispFormPrep(L, DQFormBuckets, DQForm);
912 
913  return MadeChange;
914 }
static cl::opt< unsigned > MaxVarsDSForm("ppc-dsprep-max-vars", cl::Hidden, cl::init(3), cl::desc("Potential PHI threshold per loop for PPC loop prep of DS form"))
void initializePPCLoopInstrFormPrepPass(PassRegistry &)
static const char * name
static constexpr StringRef PHINodeNameSuffix
static constexpr StringRef GEPNodeOffNameSuffix
static cl::opt< unsigned > MaxVarsPrep("ppc-formprep-max-vars", cl::Hidden, cl::init(24), cl::desc("Potential common base number threshold per function for PPC loop " "prep"))
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:215
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Examine each PHI in the given block and delete it if it is dead.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
The main scalar evolution driver.
static bool IsPtrInBounds(Value *BasePtr)
STATISTIC(NumFunctions, "Total number of functions")
std::enable_if_t<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > cast(const Y &Val)
Definition: Casting.h:254
F(f)
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
Definition: DerivedTypes.h:711
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
Definition: LoopInfo.h:165
An instruction for reading from memory.
Definition: Instructions.h:174
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:148
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:235
loop data prefetch
constexpr double phi
Definition: MathExtras.h:72
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:144
Type * getPointerElementType() const
Definition: Type.h:374
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:397
static cl::opt< unsigned > DispFormPrepMinThreshold("ppc-dispprep-min-threshold", cl::Hidden, cl::init(2), cl::desc("Minimal common base load/store instructions triggering DS/DQ form " "preparation"))
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:202
const APInt & getAPInt() const
BlockT * getHeader() const
Definition: LoopInfo.h:104
ConstantInt * getValue() const
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
This node represents a polynomial recurrence on the trip count of the specified loop.
This class represents a no-op cast from one type to another.
An instruction for storing to memory.
Definition: Instructions.h:303
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:523
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:151
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:139
bool isFloatTy() const
Return true if this is 'float', a 32-bit IEEE fp type.
Definition: Type.h:148
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:905
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:427
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:212
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:249
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
Definition: APInt.cpp:1693
static Value * GetPointerOperand(Value *MemI)
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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")
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:489
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:364
Represent the analysis usage information of a pass.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1505
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
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:375
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:180
static std::string getInstrName(const Value *I, StringRef Suffix)
Common code between 32-bit and 64-bit PowerPC targets.
static cl::opt< unsigned > MaxVarsUpdateForm("ppc-preinc-prep-max-vars", cl::Hidden, cl::init(3), cl::desc("Potential PHI threshold per loop for PPC loop prep of update " "form"))
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:249
static constexpr StringRef GEPNodeIncNameSuffix
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:931
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:63
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
Definition: LoopInfoImpl.h:194
uint64_t Offset
#define DEBUG_TYPE
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1116
Module.h This file contains the declarations for the Module class.
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:51
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:483
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:125
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:944
df_iterator< T > df_begin(const T &G)
A range adaptor for a pair of iterators.
FunctionPass * createPPCLoopInstrFormPrepPass(PPCTargetMachine &TM)
Class for arbitrary precision integers.
Definition: APInt.h:70
This class uses information about analyze scalars to rewrite expressions in canonical form.
static cl::opt< bool > PreferUpdateForm("ppc-formprep-prefer-update", cl::init(true), cl::Hidden, cl::desc("prefer update form when ds form is also a update form"))
static constexpr StringRef CastNodeNameSuffix
static cl::opt< unsigned > MaxVarsDQForm("ppc-dqprep-max-vars", cl::Hidden, cl::init(8), cl::desc("Potential PHI threshold per loop for PPC loop prep of DQ 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.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:529
APInt srem(const APInt &RHS) const
Function for signed remainder operation.
Definition: APInt.cpp:1763
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:89
unsigned pred_size(const BasicBlock *BB)
Get the number of predecessors of BB.
Definition: CFG.h:122
#define I(x, y, z)
Definition: MD5.cpp:59
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:354
bool isSignedIntN(unsigned N) const
Check if this APInt has an N-bits signed integer value.
Definition: APInt.h:461
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:75
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't have a preheader, this method is called...
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1249
print Print MemDeps of function
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:278
#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:178
bool isDoubleTy() const
Return true if this is 'double', a 64-bit IEEE fp type.
Definition: Type.h:151
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:195
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
const BasicBlock * getParent() const
Definition: Instruction.h:94
This class represents a constant integer value.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164