LLVM  14.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 #include "PPC.h"
45 #include "PPCSubtarget.h"
46 #include "PPCTargetMachine.h"
48 #include "llvm/ADT/SmallPtrSet.h"
49 #include "llvm/ADT/SmallSet.h"
50 #include "llvm/ADT/SmallVector.h"
51 #include "llvm/ADT/Statistic.h"
52 #include "llvm/Analysis/LoopInfo.h"
55 #include "llvm/IR/BasicBlock.h"
56 #include "llvm/IR/CFG.h"
57 #include "llvm/IR/Dominators.h"
58 #include "llvm/IR/Instruction.h"
59 #include "llvm/IR/Instructions.h"
60 #include "llvm/IR/IntrinsicInst.h"
61 #include "llvm/IR/IntrinsicsPowerPC.h"
62 #include "llvm/IR/Module.h"
63 #include "llvm/IR/Type.h"
64 #include "llvm/IR/Value.h"
65 #include "llvm/InitializePasses.h"
66 #include "llvm/Pass.h"
67 #include "llvm/Support/Casting.h"
69 #include "llvm/Support/Debug.h"
70 #include "llvm/Transforms/Scalar.h"
71 #include "llvm/Transforms/Utils.h"
76 #include <cassert>
77 #include <iterator>
78 #include <utility>
79 
80 #define DEBUG_TYPE "ppc-loop-instr-form-prep"
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 SCEV *O, Instruction *I) : Offset(O), Instr(I) {}
129  BucketElement(Instruction *I) : Offset(nullptr), Instr(I) {}
130 
131  const SCEV *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  bool HasCandidateForPrepare;
178 
179  /// Successful preparation number for Update/DS/DQ form in all inner most
180  /// loops. One successful preparation will put one common base out of loop,
181  /// this may leads to register presure like LICM does.
182  /// Make sure total preparation number can be controlled by option.
183  unsigned SuccPrepCount;
184 
185  bool runOnLoop(Loop *L);
186 
187  /// Check if required PHI node is already exist in Loop \p L.
188  bool alreadyPrepared(Loop *L, Instruction *MemI,
189  const SCEV *BasePtrStartSCEV,
190  const SCEV *BasePtrIncSCEV, InstrForm Form);
191 
192  /// Get the value which defines the increment SCEV \p BasePtrIncSCEV.
193  Value *getNodeForInc(Loop *L, Instruction *MemI,
194  const SCEV *BasePtrIncSCEV);
195 
196  /// Collect condition matched(\p isValidCandidate() returns true)
197  /// candidates in Loop \p L.
198  SmallVector<Bucket, 16> collectCandidates(
199  Loop *L,
200  std::function<bool(const Instruction *, const Value *, const Type *)>
201  isValidCandidate,
202  unsigned MaxCandidateNum);
203 
204  /// Add a candidate to candidates \p Buckets.
205  void addOneCandidate(Instruction *MemI, const SCEV *LSCEV,
206  SmallVector<Bucket, 16> &Buckets,
207  unsigned MaxCandidateNum);
208 
209  /// Prepare all candidates in \p Buckets for update form.
210  bool updateFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets);
211 
212  /// Prepare all candidates in \p Buckets for displacement form, now for
213  /// ds/dq.
214  bool dispFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets,
215  InstrForm Form);
216 
217  /// Prepare for one chain \p BucketChain, find the best base element and
218  /// update all other elements in \p BucketChain accordingly.
219  /// \p Form is used to find the best base element.
220  /// If success, best base element must be stored as the first element of
221  /// \p BucketChain.
222  /// Return false if no base element found, otherwise return true.
223  bool prepareBaseForDispFormChain(Bucket &BucketChain,
224  InstrForm Form);
225 
226  /// Prepare for one chain \p BucketChain, find the best base element and
227  /// update all other elements in \p BucketChain accordingly.
228  /// If success, best base element must be stored as the first element of
229  /// \p BucketChain.
230  /// Return false if no base element found, otherwise return true.
231  bool prepareBaseForUpdateFormChain(Bucket &BucketChain);
232 
233  /// Rewrite load/store instructions in \p BucketChain according to
234  /// preparation.
235  bool rewriteLoadStores(Loop *L, Bucket &BucketChain,
236  SmallSet<BasicBlock *, 16> &BBChanged,
237  InstrForm Form);
238 
239  /// Rewrite for the base load/store of a chain.
240  std::pair<Instruction *, Instruction *>
241  rewriteForBase(Loop *L, const SCEVAddRecExpr *BasePtrSCEV,
242  Instruction *BaseMemI, bool CanPreInc, InstrForm Form,
243  SCEVExpander &SCEVE, SmallPtrSet<Value *, 16> &DeletedPtrs);
244 
245  /// Rewrite for the other load/stores of a chain according to the new \p
246  /// Base.
247  Instruction *
248  rewriteForBucketElement(std::pair<Instruction *, Instruction *> Base,
249  const BucketElement &Element, Value *OffToBase,
250  SmallPtrSet<Value *, 16> &DeletedPtrs);
251  };
252 
253 } // end anonymous namespace
254 
255 char PPCLoopInstrFormPrep::ID = 0;
256 static const char *name = "Prepare loop for ppc preferred instruction forms";
257 INITIALIZE_PASS_BEGIN(PPCLoopInstrFormPrep, DEBUG_TYPE, name, false, false)
260 INITIALIZE_PASS_END(PPCLoopInstrFormPrep, DEBUG_TYPE, name, false, false)
261 
262 static constexpr StringRef PHINodeNameSuffix = ".phi";
263 static constexpr StringRef CastNodeNameSuffix = ".cast";
264 static constexpr StringRef GEPNodeIncNameSuffix = ".inc";
265 static constexpr StringRef GEPNodeOffNameSuffix = ".off";
266 
268  return new PPCLoopInstrFormPrep(TM);
269 }
270 
271 static bool IsPtrInBounds(Value *BasePtr) {
272  Value *StrippedBasePtr = BasePtr;
273  while (BitCastInst *BC = dyn_cast<BitCastInst>(StrippedBasePtr))
274  StrippedBasePtr = BC->getOperand(0);
275  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(StrippedBasePtr))
276  return GEP->isInBounds();
277 
278  return false;
279 }
280 
281 static std::string getInstrName(const Value *I, StringRef Suffix) {
282  assert(I && "Invalid paramater!");
283  if (I->hasName())
284  return (I->getName() + Suffix).str();
285  else
286  return "";
287 }
288 
290  Type **PtrElementType = nullptr) {
291 
292  Value *PtrValue = nullptr;
293  Type *PointerElementType = nullptr;
294 
295  if (LoadInst *LMemI = dyn_cast<LoadInst>(MemI)) {
296  PtrValue = LMemI->getPointerOperand();
297  PointerElementType = LMemI->getType();
298  } else if (StoreInst *SMemI = dyn_cast<StoreInst>(MemI)) {
299  PtrValue = SMemI->getPointerOperand();
300  PointerElementType = SMemI->getValueOperand()->getType();
301  } else if (IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(MemI)) {
302  PointerElementType = Type::getInt8Ty(MemI->getContext());
303  if (IMemI->getIntrinsicID() == Intrinsic::prefetch ||
304  IMemI->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp) {
305  PtrValue = IMemI->getArgOperand(0);
306  } else if (IMemI->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp) {
307  PtrValue = IMemI->getArgOperand(1);
308  }
309  }
310  /*Get ElementType if PtrElementType is not null.*/
311  if (PtrElementType)
312  *PtrElementType = PointerElementType;
313 
314  return PtrValue;
315 }
316 
318  if (skipFunction(F))
319  return false;
320 
321  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
322  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
323  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
324  DT = DTWP ? &DTWP->getDomTree() : nullptr;
325  PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
326  ST = TM ? TM->getSubtargetImpl(F) : nullptr;
327  SuccPrepCount = 0;
328 
329  bool MadeChange = false;
330 
331  for (auto I = LI->begin(), IE = LI->end(); I != IE; ++I)
332  for (auto L = df_begin(*I), LE = df_end(*I); L != LE; ++L)
333  MadeChange |= runOnLoop(*L);
334 
335  return MadeChange;
336 }
337 
338 // Rewrite the new base according to BasePtrSCEV.
339 // bb.loop.preheader:
340 // %newstart = ...
341 // bb.loop.body:
342 // %phinode = phi [ %newstart, %bb.loop.preheader ], [ %add, %bb.loop.body ]
343 // ...
344 // %add = getelementptr %phinode, %inc
345 //
346 // First returned instruciton is %phinode (or a type cast to %phinode), caller
347 // needs this value to rewrite other load/stores in the same chain.
348 // Second returned instruction is %add, caller needs this value to rewrite other
349 // load/stores in the same chain.
350 std::pair<Instruction *, Instruction *>
351 PPCLoopInstrFormPrep::rewriteForBase(Loop *L, const SCEVAddRecExpr *BasePtrSCEV,
352  Instruction *BaseMemI, bool CanPreInc,
353  InstrForm Form, SCEVExpander &SCEVE,
354  SmallPtrSet<Value *, 16> &DeletedPtrs) {
355 
356  LLVM_DEBUG(dbgs() << "PIP: Transforming: " << *BasePtrSCEV << "\n");
357 
358  assert(BasePtrSCEV->getLoop() == L && "AddRec for the wrong loop?");
359 
361  assert(BasePtr && "No pointer operand");
362 
363  Type *I8Ty = Type::getInt8Ty(BaseMemI->getParent()->getContext());
364  Type *I8PtrTy =
365  Type::getInt8PtrTy(BaseMemI->getParent()->getContext(),
366  BasePtr->getType()->getPointerAddressSpace());
367 
368  bool IsConstantInc = false;
369  const SCEV *BasePtrIncSCEV = BasePtrSCEV->getStepRecurrence(*SE);
370  Value *IncNode = getNodeForInc(L, BaseMemI, BasePtrIncSCEV);
371 
372  const SCEVConstant *BasePtrIncConstantSCEV =
373  dyn_cast<SCEVConstant>(BasePtrIncSCEV);
374  if (BasePtrIncConstantSCEV)
375  IsConstantInc = true;
376 
377  // No valid representation for the increment.
378  if (!IncNode) {
379  LLVM_DEBUG(dbgs() << "Loop Increasement can not be represented!\n");
380  return std::make_pair(nullptr, nullptr);
381  }
382 
383  const SCEV *BasePtrStartSCEV = nullptr;
384  if (CanPreInc) {
385  assert(SE->isLoopInvariant(BasePtrIncSCEV, L) &&
386  "Increment is not loop invariant!\n");
387  BasePtrStartSCEV = SE->getMinusSCEV(BasePtrSCEV->getStart(),
388  IsConstantInc ? BasePtrIncConstantSCEV
389  : BasePtrIncSCEV);
390  } else
391  BasePtrStartSCEV = BasePtrSCEV->getStart();
392 
393  if (alreadyPrepared(L, BaseMemI, BasePtrStartSCEV, BasePtrIncSCEV, Form)) {
394  LLVM_DEBUG(dbgs() << "Instruction form is already prepared!\n");
395  return std::make_pair(nullptr, nullptr);
396  }
397 
398  LLVM_DEBUG(dbgs() << "PIP: New start is: " << *BasePtrStartSCEV << "\n");
399 
400  BasicBlock *Header = L->getHeader();
401  unsigned HeaderLoopPredCount = pred_size(Header);
402  BasicBlock *LoopPredecessor = L->getLoopPredecessor();
403 
404  PHINode *NewPHI = PHINode::Create(I8PtrTy, HeaderLoopPredCount,
405  getInstrName(BaseMemI, PHINodeNameSuffix),
406  Header->getFirstNonPHI());
407 
408  Value *BasePtrStart = SCEVE.expandCodeFor(BasePtrStartSCEV, I8PtrTy,
409  LoopPredecessor->getTerminator());
410 
411  // Note that LoopPredecessor might occur in the predecessor list multiple
412  // times, and we need to add it the right number of times.
413  for (auto PI : predecessors(Header)) {
414  if (PI != LoopPredecessor)
415  continue;
416 
417  NewPHI->addIncoming(BasePtrStart, LoopPredecessor);
418  }
419 
420  Instruction *PtrInc = nullptr;
421  Instruction *NewBasePtr = nullptr;
422  if (CanPreInc) {
423  Instruction *InsPoint = &*Header->getFirstInsertionPt();
424  PtrInc = GetElementPtrInst::Create(
425  I8Ty, NewPHI, IncNode, getInstrName(BaseMemI, GEPNodeIncNameSuffix),
426  InsPoint);
427  cast<GetElementPtrInst>(PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr));
428  for (auto PI : predecessors(Header)) {
429  if (PI == LoopPredecessor)
430  continue;
431 
432  NewPHI->addIncoming(PtrInc, PI);
433  }
434  if (PtrInc->getType() != BasePtr->getType())
435  NewBasePtr =
436  new BitCastInst(PtrInc, BasePtr->getType(),
437  getInstrName(PtrInc, CastNodeNameSuffix), InsPoint);
438  else
439  NewBasePtr = PtrInc;
440  } else {
441  // Note that LoopPredecessor might occur in the predecessor list multiple
442  // times, and we need to make sure no more incoming value for them in PHI.
443  for (auto PI : predecessors(Header)) {
444  if (PI == LoopPredecessor)
445  continue;
446 
447  // For the latch predecessor, we need to insert a GEP just before the
448  // terminator to increase the address.
449  BasicBlock *BB = PI;
450  Instruction *InsPoint = BB->getTerminator();
451  PtrInc = GetElementPtrInst::Create(
452  I8Ty, NewPHI, IncNode, getInstrName(BaseMemI, GEPNodeIncNameSuffix),
453  InsPoint);
454  cast<GetElementPtrInst>(PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr));
455 
456  NewPHI->addIncoming(PtrInc, PI);
457  }
458  PtrInc = NewPHI;
459  if (NewPHI->getType() != BasePtr->getType())
460  NewBasePtr = new BitCastInst(NewPHI, BasePtr->getType(),
462  &*Header->getFirstInsertionPt());
463  else
464  NewBasePtr = NewPHI;
465  }
466 
467  BasePtr->replaceAllUsesWith(NewBasePtr);
468 
469  DeletedPtrs.insert(BasePtr);
470 
471  return std::make_pair(NewBasePtr, PtrInc);
472 }
473 
474 Instruction *PPCLoopInstrFormPrep::rewriteForBucketElement(
475  std::pair<Instruction *, Instruction *> Base, const BucketElement &Element,
476  Value *OffToBase, SmallPtrSet<Value *, 16> &DeletedPtrs) {
477  Instruction *NewBasePtr = Base.first;
478  Instruction *PtrInc = Base.second;
479  assert((NewBasePtr && PtrInc) && "base does not exist!\n");
480 
481  Type *I8Ty = Type::getInt8Ty(PtrInc->getParent()->getContext());
482 
483  Value *Ptr = getPointerOperandAndType(Element.Instr);
484  assert(Ptr && "No pointer operand");
485 
486  Instruction *RealNewPtr;
487  if (!Element.Offset ||
488  (isa<SCEVConstant>(Element.Offset) &&
489  cast<SCEVConstant>(Element.Offset)->getValue()->isZero())) {
490  RealNewPtr = NewBasePtr;
491  } else {
492  Instruction *PtrIP = dyn_cast<Instruction>(Ptr);
493  if (PtrIP && isa<Instruction>(NewBasePtr) &&
494  cast<Instruction>(NewBasePtr)->getParent() == PtrIP->getParent())
495  PtrIP = nullptr;
496  else if (PtrIP && isa<PHINode>(PtrIP))
497  PtrIP = &*PtrIP->getParent()->getFirstInsertionPt();
498  else if (!PtrIP)
499  PtrIP = Element.Instr;
500 
501  assert(OffToBase && "There should be an offset for non base element!\n");
503  I8Ty, PtrInc, OffToBase,
504  getInstrName(Element.Instr, GEPNodeOffNameSuffix), PtrIP);
505  if (!PtrIP)
506  NewPtr->insertAfter(cast<Instruction>(PtrInc));
507  NewPtr->setIsInBounds(IsPtrInBounds(Ptr));
508  RealNewPtr = NewPtr;
509  }
510 
511  Instruction *ReplNewPtr;
512  if (Ptr->getType() != RealNewPtr->getType()) {
513  ReplNewPtr = new BitCastInst(RealNewPtr, Ptr->getType(),
515  ReplNewPtr->insertAfter(RealNewPtr);
516  } else
517  ReplNewPtr = RealNewPtr;
518 
519  Ptr->replaceAllUsesWith(ReplNewPtr);
520  DeletedPtrs.insert(Ptr);
521 
522  return ReplNewPtr;
523 }
524 
525 void PPCLoopInstrFormPrep::addOneCandidate(Instruction *MemI, const SCEV *LSCEV,
526  SmallVector<Bucket, 16> &Buckets,
527  unsigned MaxCandidateNum) {
528  assert((MemI && getPointerOperandAndType(MemI)) &&
529  "Candidate should be a memory instruction.");
530  assert(LSCEV && "Invalid SCEV for Ptr value.");
531  bool FoundBucket = false;
532  for (auto &B : Buckets) {
533  const SCEV *Diff = SE->getMinusSCEV(LSCEV, B.BaseSCEV);
534  if (const auto *CDiff = dyn_cast<SCEVConstant>(Diff)) {
535  B.Elements.push_back(BucketElement(CDiff, MemI));
536  FoundBucket = true;
537  break;
538  }
539  }
540 
541  if (!FoundBucket) {
542  if (Buckets.size() == MaxCandidateNum)
543  return;
544  Buckets.push_back(Bucket(LSCEV, MemI));
545  }
546 }
547 
548 SmallVector<Bucket, 16> PPCLoopInstrFormPrep::collectCandidates(
549  Loop *L,
550  std::function<bool(const Instruction *, const Value *, const Type *)>
551  isValidCandidate,
552  unsigned MaxCandidateNum) {
553  SmallVector<Bucket, 16> Buckets;
554  for (const auto &BB : L->blocks())
555  for (auto &J : *BB) {
556  Value *PtrValue = nullptr;
557  Type *PointerElementType = nullptr;
558  PtrValue = getPointerOperandAndType(&J, &PointerElementType);
559 
560  if (!PtrValue)
561  continue;
562 
563  if (PtrValue->getType()->getPointerAddressSpace())
564  continue;
565 
566  if (L->isLoopInvariant(PtrValue))
567  continue;
568 
569  const SCEV *LSCEV = SE->getSCEVAtScope(PtrValue, L);
570  const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(LSCEV);
571  if (!LARSCEV || LARSCEV->getLoop() != L)
572  continue;
573 
574  // Mark that we have candidates for preparing.
575  HasCandidateForPrepare = true;
576 
577  if (isValidCandidate(&J, PtrValue, PointerElementType))
578  addOneCandidate(&J, LSCEV, Buckets, MaxCandidateNum);
579  }
580  return Buckets;
581 }
582 
583 bool PPCLoopInstrFormPrep::prepareBaseForDispFormChain(Bucket &BucketChain,
584  InstrForm Form) {
585  // RemainderOffsetInfo details:
586  // key: value of (Offset urem DispConstraint). For DSForm, it can
587  // be [0, 4).
588  // first of pair: the index of first BucketElement whose remainder is equal
589  // to key. For key 0, this value must be 0.
590  // second of pair: number of load/stores with the same remainder.
592 
593  for (unsigned j = 0, je = BucketChain.Elements.size(); j != je; ++j) {
594  if (!BucketChain.Elements[j].Offset)
595  RemainderOffsetInfo[0] = std::make_pair(0, 1);
596  else {
597  unsigned Remainder = cast<SCEVConstant>(BucketChain.Elements[j].Offset)
598  ->getAPInt()
599  .urem(Form);
600  if (RemainderOffsetInfo.find(Remainder) == RemainderOffsetInfo.end())
601  RemainderOffsetInfo[Remainder] = std::make_pair(j, 1);
602  else
603  RemainderOffsetInfo[Remainder].second++;
604  }
605  }
606  // Currently we choose the most profitable base as the one which has the max
607  // number of load/store with same remainder.
608  // FIXME: adjust the base selection strategy according to load/store offset
609  // distribution.
610  // For example, if we have one candidate chain for DS form preparation, which
611  // contains following load/stores with different remainders:
612  // 1: 10 load/store whose remainder is 1;
613  // 2: 9 load/store whose remainder is 2;
614  // 3: 1 for remainder 3 and 0 for remainder 0;
615  // Now we will choose the first load/store whose remainder is 1 as base and
616  // adjust all other load/stores according to new base, so we will get 10 DS
617  // form and 10 X form.
618  // But we should be more clever, for this case we could use two bases, one for
619  // remainder 1 and the other for remainder 2, thus we could get 19 DS form and
620  // 1 X form.
621  unsigned MaxCountRemainder = 0;
622  for (unsigned j = 0; j < (unsigned)Form; j++)
623  if ((RemainderOffsetInfo.find(j) != RemainderOffsetInfo.end()) &&
624  RemainderOffsetInfo[j].second >
625  RemainderOffsetInfo[MaxCountRemainder].second)
626  MaxCountRemainder = j;
627 
628  // Abort when there are too few insts with common base.
629  if (RemainderOffsetInfo[MaxCountRemainder].second < DispFormPrepMinThreshold)
630  return false;
631 
632  // If the first value is most profitable, no needed to adjust BucketChain
633  // elements as they are substracted the first value when collecting.
634  if (MaxCountRemainder == 0)
635  return true;
636 
637  // Adjust load/store to the new chosen base.
638  const SCEV *Offset =
639  BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first].Offset;
640  BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset);
641  for (auto &E : BucketChain.Elements) {
642  if (E.Offset)
643  E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(E.Offset, Offset));
644  else
645  E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(Offset));
646  }
647 
648  std::swap(BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first],
649  BucketChain.Elements[0]);
650  return true;
651 }
652 
653 // FIXME: implement a more clever base choosing policy.
654 // Currently we always choose an exist load/store offset. This maybe lead to
655 // suboptimal code sequences. For example, for one DS chain with offsets
656 // {-32769, 2003, 2007, 2011}, we choose -32769 as base offset, and left disp
657 // for load/stores are {0, 34772, 34776, 34780}. Though each offset now is a
658 // multipler of 4, it cannot be represented by sint16.
659 bool PPCLoopInstrFormPrep::prepareBaseForUpdateFormChain(Bucket &BucketChain) {
660  // We have a choice now of which instruction's memory operand we use as the
661  // base for the generated PHI. Always picking the first instruction in each
662  // bucket does not work well, specifically because that instruction might
663  // be a prefetch (and there are no pre-increment dcbt variants). Otherwise,
664  // the choice is somewhat arbitrary, because the backend will happily
665  // generate direct offsets from both the pre-incremented and
666  // post-incremented pointer values. Thus, we'll pick the first non-prefetch
667  // instruction in each bucket, and adjust the recurrence and other offsets
668  // accordingly.
669  for (int j = 0, je = BucketChain.Elements.size(); j != je; ++j) {
670  if (auto *II = dyn_cast<IntrinsicInst>(BucketChain.Elements[j].Instr))
671  if (II->getIntrinsicID() == Intrinsic::prefetch)
672  continue;
673 
674  // If we'd otherwise pick the first element anyway, there's nothing to do.
675  if (j == 0)
676  break;
677 
678  // If our chosen element has no offset from the base pointer, there's
679  // nothing to do.
680  if (!BucketChain.Elements[j].Offset ||
681  cast<SCEVConstant>(BucketChain.Elements[j].Offset)->isZero())
682  break;
683 
684  const SCEV *Offset = BucketChain.Elements[j].Offset;
685  BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset);
686  for (auto &E : BucketChain.Elements) {
687  if (E.Offset)
688  E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(E.Offset, Offset));
689  else
690  E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(Offset));
691  }
692 
693  std::swap(BucketChain.Elements[j], BucketChain.Elements[0]);
694  break;
695  }
696  return true;
697 }
698 
699 bool PPCLoopInstrFormPrep::rewriteLoadStores(
700  Loop *L, Bucket &BucketChain, SmallSet<BasicBlock *, 16> &BBChanged,
701  InstrForm Form) {
702  bool MadeChange = false;
703 
704  const SCEVAddRecExpr *BasePtrSCEV =
705  cast<SCEVAddRecExpr>(BucketChain.BaseSCEV);
706  if (!BasePtrSCEV->isAffine())
707  return MadeChange;
708 
709  if (!isSafeToExpand(BasePtrSCEV->getStart(), *SE))
710  return MadeChange;
711 
712  SmallPtrSet<Value *, 16> DeletedPtrs;
713 
714  BasicBlock *Header = L->getHeader();
715  SCEVExpander SCEVE(*SE, Header->getModule()->getDataLayout(), "pistart");
716 
717  // For some DS form load/store instructions, it can also be an update form,
718  // if the stride is constant and is a multipler of 4. Use update form if
719  // prefer it.
720  bool CanPreInc = (Form == UpdateForm ||
721  ((Form == DSForm) &&
722  isa<SCEVConstant>(BasePtrSCEV->getStepRecurrence(*SE)) &&
723  !cast<SCEVConstant>(BasePtrSCEV->getStepRecurrence(*SE))
724  ->getAPInt()
725  .urem(4) &&
727 
728  std::pair<Instruction *, Instruction *> Base =
729  rewriteForBase(L, BasePtrSCEV, BucketChain.Elements.begin()->Instr,
730  CanPreInc, Form, SCEVE, DeletedPtrs);
731 
732  if (!Base.first || !Base.second)
733  return MadeChange;
734 
735  // Keep track of the replacement pointer values we've inserted so that we
736  // don't generate more pointer values than necessary.
737  SmallPtrSet<Value *, 16> NewPtrs;
738  NewPtrs.insert(Base.first);
739 
740  for (auto I = std::next(BucketChain.Elements.begin()),
741  IE = BucketChain.Elements.end(); I != IE; ++I) {
742  Value *Ptr = getPointerOperandAndType(I->Instr);
743  assert(Ptr && "No pointer operand");
744  if (NewPtrs.count(Ptr))
745  continue;
746 
747  Instruction *NewPtr = rewriteForBucketElement(
748  Base, *I,
749  I->Offset ? cast<SCEVConstant>(I->Offset)->getValue() : nullptr,
750  DeletedPtrs);
751  assert(NewPtr && "wrong rewrite!\n");
752  NewPtrs.insert(NewPtr);
753  }
754 
755  // Clear the rewriter cache, because values that are in the rewriter's cache
756  // can be deleted below, causing the AssertingVH in the cache to trigger.
757  SCEVE.clear();
758 
759  for (auto *Ptr : DeletedPtrs) {
760  if (Instruction *IDel = dyn_cast<Instruction>(Ptr))
761  BBChanged.insert(IDel->getParent());
763  }
764 
765  MadeChange = true;
766 
767  SuccPrepCount++;
768 
769  if (Form == DSForm && !CanPreInc)
770  DSFormChainRewritten++;
771  else if (Form == DQForm)
772  DQFormChainRewritten++;
773  else if (Form == UpdateForm || (Form == DSForm && CanPreInc))
774  UpdFormChainRewritten++;
775 
776  return MadeChange;
777 }
778 
779 bool PPCLoopInstrFormPrep::updateFormPrep(Loop *L,
780  SmallVector<Bucket, 16> &Buckets) {
781  bool MadeChange = false;
782  if (Buckets.empty())
783  return MadeChange;
784  SmallSet<BasicBlock *, 16> BBChanged;
785  for (auto &Bucket : Buckets)
786  // The base address of each bucket is transformed into a phi and the others
787  // are rewritten based on new base.
788  if (prepareBaseForUpdateFormChain(Bucket))
789  MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, UpdateForm);
790 
791  if (MadeChange)
792  for (auto *BB : BBChanged)
794  return MadeChange;
795 }
796 
797 bool PPCLoopInstrFormPrep::dispFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets,
798  InstrForm Form) {
799  bool MadeChange = false;
800 
801  if (Buckets.empty())
802  return MadeChange;
803 
804  SmallSet<BasicBlock *, 16> BBChanged;
805  for (auto &Bucket : Buckets) {
806  if (Bucket.Elements.size() < DispFormPrepMinThreshold)
807  continue;
808  if (prepareBaseForDispFormChain(Bucket, Form))
809  MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, Form);
810  }
811 
812  if (MadeChange)
813  for (auto *BB : BBChanged)
815  return MadeChange;
816 }
817 
818 // Find the loop invariant increment node for SCEV BasePtrIncSCEV.
819 // bb.loop.preheader:
820 // %start = ...
821 // bb.loop.body:
822 // %phinode = phi [ %start, %bb.loop.preheader ], [ %add, %bb.loop.body ]
823 // ...
824 // %add = add %phinode, %inc ; %inc is what we want to get.
825 //
826 Value *PPCLoopInstrFormPrep::getNodeForInc(Loop *L, Instruction *MemI,
827  const SCEV *BasePtrIncSCEV) {
828  // If the increment is a constant, no definition is needed.
829  // Return the value directly.
830  if (isa<SCEVConstant>(BasePtrIncSCEV))
831  return cast<SCEVConstant>(BasePtrIncSCEV)->getValue();
832 
833  if (!SE->isLoopInvariant(BasePtrIncSCEV, L))
834  return nullptr;
835 
836  BasicBlock *BB = MemI->getParent();
837  if (!BB)
838  return nullptr;
839 
840  BasicBlock *LatchBB = L->getLoopLatch();
841 
842  if (!LatchBB)
843  return nullptr;
844 
845  // Run through the PHIs and check their operands to find valid representation
846  // for the increment SCEV.
848  for (auto &CurrentPHI : PHIIter) {
849  PHINode *CurrentPHINode = dyn_cast<PHINode>(&CurrentPHI);
850  if (!CurrentPHINode)
851  continue;
852 
853  if (!SE->isSCEVable(CurrentPHINode->getType()))
854  continue;
855 
856  const SCEV *PHISCEV = SE->getSCEVAtScope(CurrentPHINode, L);
857 
858  const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast<SCEVAddRecExpr>(PHISCEV);
859  if (!PHIBasePtrSCEV)
860  continue;
861 
862  const SCEV *PHIBasePtrIncSCEV = PHIBasePtrSCEV->getStepRecurrence(*SE);
863 
864  if (!PHIBasePtrIncSCEV || (PHIBasePtrIncSCEV != BasePtrIncSCEV))
865  continue;
866 
867  // Get the incoming value from the loop latch and check if the value has
868  // the add form with the required increment.
869  if (Instruction *I = dyn_cast<Instruction>(
870  CurrentPHINode->getIncomingValueForBlock(LatchBB))) {
871  Value *StrippedBaseI = I;
872  while (BitCastInst *BC = dyn_cast<BitCastInst>(StrippedBaseI))
873  StrippedBaseI = BC->getOperand(0);
874 
875  Instruction *StrippedI = dyn_cast<Instruction>(StrippedBaseI);
876  if (!StrippedI)
877  continue;
878 
879  // LSR pass may add a getelementptr instruction to do the loop increment,
880  // also search in that getelementptr instruction.
881  if (StrippedI->getOpcode() == Instruction::Add ||
882  (StrippedI->getOpcode() == Instruction::GetElementPtr &&
883  StrippedI->getNumOperands() == 2)) {
884  if (SE->getSCEVAtScope(StrippedI->getOperand(0), L) == BasePtrIncSCEV)
885  return StrippedI->getOperand(0);
886  if (SE->getSCEVAtScope(StrippedI->getOperand(1), L) == BasePtrIncSCEV)
887  return StrippedI->getOperand(1);
888  }
889  }
890  }
891  return nullptr;
892 }
893 
894 // In order to prepare for the preferred instruction form, a PHI is added.
895 // This function will check to see if that PHI already exists and will return
896 // true if it found an existing PHI with the matched start and increment as the
897 // one we wanted to create.
898 bool PPCLoopInstrFormPrep::alreadyPrepared(Loop *L, Instruction *MemI,
899  const SCEV *BasePtrStartSCEV,
900  const SCEV *BasePtrIncSCEV,
901  InstrForm Form) {
902  BasicBlock *BB = MemI->getParent();
903  if (!BB)
904  return false;
905 
906  BasicBlock *PredBB = L->getLoopPredecessor();
907  BasicBlock *LatchBB = L->getLoopLatch();
908 
909  if (!PredBB || !LatchBB)
910  return false;
911 
912  // Run through the PHIs and see if we have some that looks like a preparation
914  for (auto & CurrentPHI : PHIIter) {
915  PHINode *CurrentPHINode = dyn_cast<PHINode>(&CurrentPHI);
916  if (!CurrentPHINode)
917  continue;
918 
919  if (!SE->isSCEVable(CurrentPHINode->getType()))
920  continue;
921 
922  const SCEV *PHISCEV = SE->getSCEVAtScope(CurrentPHINode, L);
923 
924  const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast<SCEVAddRecExpr>(PHISCEV);
925  if (!PHIBasePtrSCEV)
926  continue;
927 
928  const SCEVConstant *PHIBasePtrIncSCEV =
929  dyn_cast<SCEVConstant>(PHIBasePtrSCEV->getStepRecurrence(*SE));
930  if (!PHIBasePtrIncSCEV)
931  continue;
932 
933  if (CurrentPHINode->getNumIncomingValues() == 2) {
934  if ((CurrentPHINode->getIncomingBlock(0) == LatchBB &&
935  CurrentPHINode->getIncomingBlock(1) == PredBB) ||
936  (CurrentPHINode->getIncomingBlock(1) == LatchBB &&
937  CurrentPHINode->getIncomingBlock(0) == PredBB)) {
938  if (PHIBasePtrIncSCEV == BasePtrIncSCEV) {
939  // The existing PHI (CurrentPHINode) has the same start and increment
940  // as the PHI that we wanted to create.
941  if (Form == UpdateForm &&
942  PHIBasePtrSCEV->getStart() == BasePtrStartSCEV) {
943  ++PHINodeAlreadyExistsUpdate;
944  return true;
945  }
946  if (Form == DSForm || Form == DQForm) {
947  const SCEVConstant *Diff = dyn_cast<SCEVConstant>(
948  SE->getMinusSCEV(PHIBasePtrSCEV->getStart(), BasePtrStartSCEV));
949  if (Diff && !Diff->getAPInt().urem(Form)) {
950  if (Form == DSForm)
951  ++PHINodeAlreadyExistsDS;
952  else
953  ++PHINodeAlreadyExistsDQ;
954  return true;
955  }
956  }
957  }
958  }
959  }
960  }
961  return false;
962 }
963 
964 bool PPCLoopInstrFormPrep::runOnLoop(Loop *L) {
965  bool MadeChange = false;
966 
967  // Only prep. the inner-most loop
968  if (!L->isInnermost())
969  return MadeChange;
970 
971  // Return if already done enough preparation.
972  if (SuccPrepCount >= MaxVarsPrep)
973  return MadeChange;
974 
975  LLVM_DEBUG(dbgs() << "PIP: Examining: " << *L << "\n");
976 
977  BasicBlock *LoopPredecessor = L->getLoopPredecessor();
978  // If there is no loop predecessor, or the loop predecessor's terminator
979  // returns a value (which might contribute to determining the loop's
980  // iteration space), insert a new preheader for the loop.
981  if (!LoopPredecessor ||
982  !LoopPredecessor->getTerminator()->getType()->isVoidTy()) {
983  LoopPredecessor = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA);
984  if (LoopPredecessor)
985  MadeChange = true;
986  }
987  if (!LoopPredecessor) {
988  LLVM_DEBUG(dbgs() << "PIP fails since no predecessor for current loop.\n");
989  return MadeChange;
990  }
991  // Check if a load/store has update form. This lambda is used by function
992  // collectCandidates which can collect candidates for types defined by lambda.
993  auto isUpdateFormCandidate = [&](const Instruction *I, const Value *PtrValue,
994  const Type *PointerElementType) {
995  assert((PtrValue && I) && "Invalid parameter!");
996  // There are no update forms for Altivec vector load/stores.
997  if (ST && ST->hasAltivec() && PointerElementType->isVectorTy())
998  return false;
999  // There are no update forms for P10 lxvp/stxvp intrinsic.
1000  auto *II = dyn_cast<IntrinsicInst>(I);
1001  if (II && ((II->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp) ||
1002  II->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp))
1003  return false;
1004  // See getPreIndexedAddressParts, the displacement for LDU/STDU has to
1005  // be 4's multiple (DS-form). For i64 loads/stores when the displacement
1006  // fits in a 16-bit signed field but isn't a multiple of 4, it will be
1007  // useless and possible to break some original well-form addressing mode
1008  // to make this pre-inc prep for it.
1009  if (PointerElementType->isIntegerTy(64)) {
1010  const SCEV *LSCEV = SE->getSCEVAtScope(const_cast<Value *>(PtrValue), L);
1011  const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(LSCEV);
1012  if (!LARSCEV || LARSCEV->getLoop() != L)
1013  return false;
1014  if (const SCEVConstant *StepConst =
1015  dyn_cast<SCEVConstant>(LARSCEV->getStepRecurrence(*SE))) {
1016  const APInt &ConstInt = StepConst->getValue()->getValue();
1017  if (ConstInt.isSignedIntN(16) && ConstInt.srem(4) != 0)
1018  return false;
1019  }
1020  }
1021  return true;
1022  };
1023 
1024  // Check if a load/store has DS form.
1025  auto isDSFormCandidate = [](const Instruction *I, const Value *PtrValue,
1026  const Type *PointerElementType) {
1027  assert((PtrValue && I) && "Invalid parameter!");
1028  if (isa<IntrinsicInst>(I))
1029  return false;
1030  return (PointerElementType->isIntegerTy(64)) ||
1031  (PointerElementType->isFloatTy()) ||
1032  (PointerElementType->isDoubleTy()) ||
1033  (PointerElementType->isIntegerTy(32) &&
1034  llvm::any_of(I->users(),
1035  [](const User *U) { return isa<SExtInst>(U); }));
1036  };
1037 
1038  // Check if a load/store has DQ form.
1039  auto isDQFormCandidate = [&](const Instruction *I, const Value *PtrValue,
1040  const Type *PointerElementType) {
1041  assert((PtrValue && I) && "Invalid parameter!");
1042  // Check if it is a P10 lxvp/stxvp intrinsic.
1043  auto *II = dyn_cast<IntrinsicInst>(I);
1044  if (II)
1045  return II->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp ||
1046  II->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp;
1047  // Check if it is a P9 vector load/store.
1048  return ST && ST->hasP9Vector() && (PointerElementType->isVectorTy());
1049  };
1050 
1051  HasCandidateForPrepare = false;
1052 
1053  // Collect buckets of comparable addresses used by loads and stores for update
1054  // form.
1055  SmallVector<Bucket, 16> UpdateFormBuckets =
1056  collectCandidates(L, isUpdateFormCandidate, MaxVarsUpdateForm);
1057 
1058  // Prepare for update form.
1059  if (!UpdateFormBuckets.empty())
1060  MadeChange |= updateFormPrep(L, UpdateFormBuckets);
1061  else if (!HasCandidateForPrepare)
1062  // If no candidate for preparing, return early.
1063  return MadeChange;
1064 
1065  // Collect buckets of comparable addresses used by loads and stores for DS
1066  // form.
1067  SmallVector<Bucket, 16> DSFormBuckets =
1068  collectCandidates(L, isDSFormCandidate, MaxVarsDSForm);
1069 
1070  // Prepare for DS form.
1071  if (!DSFormBuckets.empty())
1072  MadeChange |= dispFormPrep(L, DSFormBuckets, DSForm);
1073 
1074  // Collect buckets of comparable addresses used by loads and stores for DQ
1075  // form.
1076  SmallVector<Bucket, 16> DQFormBuckets =
1077  collectCandidates(L, isDQFormCandidate, MaxVarsDQForm);
1078 
1079  // Prepare for DQ form.
1080  if (!DQFormBuckets.empty())
1081  MadeChange |= dispFormPrep(L, DQFormBuckets, DQForm);
1082 
1083  return MadeChange;
1084 }
llvm::RecursivelyDeleteTriviallyDeadInstructions
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:511
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
llvm::cast
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
llvm::GetElementPtrInst::setIsInBounds
void setIsInBounds(bool b=true)
Set or clear the inbounds flag on this GEP instruction.
Definition: Instructions.cpp:1810
llvm::Loop::isLoopInvariant
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:64
GEPNodeIncNameSuffix
static constexpr StringRef GEPNodeIncNameSuffix
Definition: PPCLoopInstrFormPrep.cpp:264
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::isSafeToExpand
bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE, bool CanonicalMode=true)
Return true if the given expression is safe to expand in the sense that all materialized values are s...
Definition: ScalarEvolutionExpander.cpp:2657
llvm::Type::getInt8PtrTy
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:293
llvm::SCEVAddRecExpr::isAffine
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
Definition: ScalarEvolutionExpressions.h:379
IntrinsicInst.h
ScalarEvolutionExpander.h
llvm::APInt::isSignedIntN
bool isSignedIntN(unsigned N) const
Check if this APInt has an N-bits signed integer value.
Definition: APInt.h:420
MaxVarsDQForm
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"))
Scalar.h
llvm::SCEVAddRecExpr::getStart
const SCEV * getStart() const
Definition: ScalarEvolutionExpressions.h:363
llvm::Function
Definition: Function.h:62
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
Pass.h
llvm::SCEVExpander
This class uses information about analyze scalars to rewrite expressions in canonical form.
Definition: ScalarEvolutionExpander.h:65
CastNodeNameSuffix
static constexpr StringRef CastNodeNameSuffix
Definition: PPCLoopInstrFormPrep.cpp:263
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5198
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::LoopBase::getLoopPredecessor
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
Definition: LoopInfoImpl.h:195
llvm::dwarf::Form
Form
Definition: Dwarf.h:131
llvm::Type::getPointerAddressSpace
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
Definition: DerivedTypes.h:734
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
llvm::df_end
df_iterator< T > df_end(const T &G)
Definition: DepthFirstIterator.h:223
Local.h
llvm::createPPCLoopInstrFormPrepPass
FunctionPass * createPPCLoopInstrFormPrepPass(PPCTargetMachine &TM)
Definition: PPCLoopInstrFormPrep.cpp:267
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::SCEVExpander::expandCodeFor
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
Definition: ScalarEvolutionExpander.h:277
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
ScalarEvolution.h
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Module.h
getPointerOperandAndType
static Value * getPointerOperandAndType(Value *MemI, Type **PtrElementType=nullptr)
Definition: PPCLoopInstrFormPrep.cpp:289
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1268
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
PHINodeNameSuffix
static constexpr StringRef PHINodeNameSuffix
Definition: PPCLoopInstrFormPrep.cpp:262
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::SmallPtrSet< Value *, 16 >
llvm::Type::getInt8Ty
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:239
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::initializePPCLoopInstrFormPrepPass
void initializePPCLoopInstrFormPrepPass(PassRegistry &)
DepthFirstIterator.h
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Instruction.h
PPCSubtarget.h
CommandLine.h
llvm::Instruction::insertAfter
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
Definition: Instruction.cpp:90
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::PPCSubtarget
Definition: PPCSubtarget.h:71
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
MaxVarsDSForm
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"))
llvm::User
Definition: User.h:44
name
static const char * name
Definition: PPCLoopInstrFormPrep.cpp:256
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:178
llvm::Type::isVectorTy
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:226
llvm::BasicBlock::getFirstInsertionPt
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:253
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2818
llvm::Instruction
Definition: Instruction.h:45
MaxVarsUpdateForm
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"))
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
PPC.h
llvm::codeview::EncodedFramePtrReg::BasePtr
@ BasePtr
llvm::AArch64CC::LE
@ LE
Definition: AArch64BaseInfo.h:268
LoopUtils.h
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2088
SmallPtrSet.h
llvm::BasicBlock::getModule
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:148
llvm::BasicBlock::getFirstNonPHI
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:216
Utils.h
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2725
Type.h
llvm::APInt::srem
APInt srem(const APInt &RHS) const
Function for signed remainder operation.
Definition: APInt.cpp:1728
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
CFG.h
LoopInfo.h
llvm::ARM_PROC::IE
@ IE
Definition: ARMBaseInfo.h:27
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:190
llvm::InsertPreheaderForLoop
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...
Definition: LoopSimplify.cpp:123
BasicBlock.h
llvm::cl::opt
Definition: CommandLine.h:1432
DispFormPrepMinThreshold
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"))
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:77
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:197
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:304
inc
Current eax eax eax ret Ideal eax eax ret Re implement atomic builtins x86 does not have to use add to implement these it can use inc
Definition: README.txt:1367
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2783
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:928
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
llvm::SCEVConstant
This class represents a constant integer value.
Definition: ScalarEvolutionExpressions.h:47
llvm::df_begin
df_iterator< T > df_begin(const T &G)
Definition: DepthFirstIterator.h:218
GEPNodeOffNameSuffix
static constexpr StringRef GEPNodeOffNameSuffix
Definition: PPCLoopInstrFormPrep.cpp:265
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:138
llvm::SCEVExpander::clear
void clear()
Erase the contents of the InsertedExpressions map so that users trying to expand the same expression ...
Definition: ScalarEvolutionExpander.h:201
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::APInt::urem
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
Definition: APInt.cpp:1658
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
getInstrName
static std::string getInstrName(const Value *I, StringRef Suffix)
Definition: PPCLoopInstrFormPrep.cpp:281
prefetch
loop data prefetch
Definition: LoopDataPrefetch.cpp:152
llvm::GetElementPtrInst::Create
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:954
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::any_of
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:1558
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::pred_size
unsigned pred_size(const BasicBlock *BB)
Get the number of predecessors of BB.
Definition: CFG.h:124
DEBUG_TYPE
#define DEBUG_TYPE
Definition: PPCLoopInstrFormPrep.cpp:80
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:867
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:990
PreferUpdateForm
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"))
llvm::SmallSet::insert
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
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
llvm::BasicBlock::getTerminator
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:152
MaxVarsPrep
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"))
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:36
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
j
return j(j<< 16)
llvm::LoopBase::isInnermost
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
Definition: LoopInfo.h:165
llvm::LCSSAID
char & LCSSAID
Definition: LCSSA.cpp:485
llvm::SCEVAddRecExpr::getLoop
const Loop * getLoop() const
Definition: ScalarEvolutionExpressions.h:364
llvm::Type::isFloatTy
bool isFloatTy() const
Return true if this is 'float', a 32-bit IEEE fp type.
Definition: Type.h:147
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
llvm::PHINode::Create
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...
Definition: Instructions.h:2675
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:352
Casting.h
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::Type::isDoubleTy
bool isDoubleTy() const
Return true if this is 'double', a 64-bit IEEE fp type.
Definition: Type.h:150
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::PPCTargetMachine
Common code between 32-bit and 64-bit PowerPC targets.
Definition: PPCTargetMachine.h:25
llvm::DeleteDeadPHIs
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.
Definition: BasicBlockUtils.cpp:157
llvm::SCEVConstant::getAPInt
const APInt & getAPInt() const
Definition: ScalarEvolutionExpressions.h:57
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:45
ScalarEvolutionExpressions.h
IsPtrInBounds
static bool IsPtrInBounds(Value *BasePtr)
Definition: PPCLoopInstrFormPrep.cpp:271
Instructions.h
llvm::numbers::phi
constexpr double phi
Definition: MathExtras.h:71
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
INITIALIZE_PASS_BEGIN
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:51
SmallVector.h
Dominators.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2749
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::PHINode
Definition: Instructions.h:2633
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:401
TM
const char LLVMTargetMachineRef TM
Definition: PassBuilderBindings.cpp:47
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::cl::desc
Definition: CommandLine.h:412
BasicBlockUtils.h
Value.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
PPCTargetMachine.h
llvm::SCEVAddRecExpr::getStepRecurrence
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
Definition: ScalarEvolutionExpressions.h:370
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
SmallSet.h
llvm::SmallPtrSetImpl::insert
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
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37