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