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