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// 3: common multiple chains for the load/stores with same offsets in the loop,
44// so that we can reuse the offsets and reduce the register pressure in the
45// loop. This transformation can also increase the loop ILP as now each chain
46// uses its own loop induction add/addi. But this will increase the number of
47// add/addi in the loop.
48//
49// Generically, this means transforming loops like this:
50//
51// char *p;
52// A1 = p + base1
53// A2 = p + base1 + offset
54// B1 = p + base2
55// B2 = p + base2 + offset
56//
57// for (int i = 0; i < n; i++)
58// unsigned long x1 = *(unsigned long *)(A1 + i);
59// unsigned long x2 = *(unsigned long *)(A2 + i)
60// unsigned long x3 = *(unsigned long *)(B1 + i);
61// unsigned long x4 = *(unsigned long *)(B2 + i);
62// }
63//
64// to look like this:
65//
66// A1_new = p + base1 // chain 1
67// B1_new = p + base2 // chain 2, now inside the loop, common offset is
68// // reused.
69//
70// for (long long i = 0; i < n; i+=count) {
71// unsigned long x1 = *(unsigned long *)(A1_new + i);
72// unsigned long x2 = *(unsigned long *)((A1_new + i) + offset);
73// unsigned long x3 = *(unsigned long *)(B1_new + i);
74// unsigned long x4 = *(unsigned long *)((B1_new + i) + offset);
75// }
76//===----------------------------------------------------------------------===//
77
78#include "PPC.h"
79#include "PPCSubtarget.h"
80#include "PPCTargetMachine.h"
81#include "llvm/ADT/DepthFirstIterator.h"
82#include "llvm/ADT/SmallPtrSet.h"
83#include "llvm/ADT/SmallVector.h"
84#include "llvm/ADT/Statistic.h"
85#include "llvm/Analysis/LoopInfo.h"
86#include "llvm/Analysis/ScalarEvolution.h"
87#include "llvm/Analysis/ScalarEvolutionExpressions.h"
88#include "llvm/IR/BasicBlock.h"
89#include "llvm/IR/CFG.h"
90#include "llvm/IR/Dominators.h"
91#include "llvm/IR/Instruction.h"
92#include "llvm/IR/Instructions.h"
93#include "llvm/IR/IntrinsicInst.h"
94#include "llvm/IR/IntrinsicsPowerPC.h"
95#include "llvm/IR/Type.h"
96#include "llvm/IR/Value.h"
97#include "llvm/InitializePasses.h"
98#include "llvm/Pass.h"
99#include "llvm/Support/Casting.h"
100#include "llvm/Support/CommandLine.h"
101#include "llvm/Support/Debug.h"
102#include "llvm/Transforms/Scalar.h"
103#include "llvm/Transforms/Utils.h"
104#include "llvm/Transforms/Utils/BasicBlockUtils.h"
105#include "llvm/Transforms/Utils/Local.h"
106#include "llvm/Transforms/Utils/LoopUtils.h"
107#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
108#include <cassert>
109#include <cmath>
110#include <utility>
111
112#define DEBUG_TYPE "ppc-loop-instr-form-prep"
113
114using namespace llvm;
115
116static cl::opt<unsigned>
117 MaxVarsPrep("ppc-formprep-max-vars", cl::Hidden, cl::init(Val: 24),
118 cl::desc("Potential common base number threshold per function "
119 "for PPC loop prep"));
120
121static cl::opt<bool> PreferUpdateForm("ppc-formprep-prefer-update",
122 cl::init(Val: true), cl::Hidden,
123 cl::desc("prefer update form when ds form is also a update form"));
124
125static cl::opt<bool> EnableUpdateFormForNonConstInc(
126 "ppc-formprep-update-nonconst-inc", cl::init(Val: false), cl::Hidden,
127 cl::desc("prepare update form when the load/store increment is a loop "
128 "invariant non-const value."));
129
130static cl::opt<bool> EnableChainCommoning(
131 "ppc-formprep-chain-commoning", cl::init(Val: false), cl::Hidden,
132 cl::desc("Enable chain commoning in PPC loop prepare pass."));
133
134// Sum of following 3 per loop thresholds for all loops can not be larger
135// than MaxVarsPrep.
136// now the thresholds for each kind prep are exterimental values on Power9.
137static cl::opt<unsigned> MaxVarsUpdateForm("ppc-preinc-prep-max-vars",
138 cl::Hidden, cl::init(Val: 3),
139 cl::desc("Potential PHI threshold per loop for PPC loop prep of update "
140 "form"));
141
142static cl::opt<unsigned> MaxVarsDSForm("ppc-dsprep-max-vars",
143 cl::Hidden, cl::init(Val: 3),
144 cl::desc("Potential PHI threshold per loop for PPC loop prep of DS form"));
145
146static cl::opt<unsigned> MaxVarsDQForm("ppc-dqprep-max-vars",
147 cl::Hidden, cl::init(Val: 8),
148 cl::desc("Potential PHI threshold per loop for PPC loop prep of DQ form"));
149
150// Commoning chain will reduce the register pressure, so we don't consider about
151// the PHI nodes number.
152// But commoning chain will increase the addi/add number in the loop and also
153// increase loop ILP. Maximum chain number should be same with hardware
154// IssueWidth, because we won't benefit from ILP if the parallel chains number
155// is bigger than IssueWidth. We assume there are 2 chains in one bucket, so
156// there would be 4 buckets at most on P9(IssueWidth is 8).
157static cl::opt<unsigned> MaxVarsChainCommon(
158 "ppc-chaincommon-max-vars", cl::Hidden, cl::init(Val: 4),
159 cl::desc("Bucket number per loop for PPC loop chain common"));
160
161// If would not be profitable if the common base has only one load/store, ISEL
162// should already be able to choose best load/store form based on offset for
163// single load/store. Set minimal profitable value default to 2 and make it as
164// an option.
165static cl::opt<unsigned> DispFormPrepMinThreshold("ppc-dispprep-min-threshold",
166 cl::Hidden, cl::init(Val: 2),
167 cl::desc("Minimal common base load/store instructions triggering DS/DQ form "
168 "preparation"));
169
170static cl::opt<unsigned> ChainCommonPrepMinThreshold(
171 "ppc-chaincommon-min-threshold", cl::Hidden, cl::init(Val: 4),
172 cl::desc("Minimal common base load/store instructions triggering chain "
173 "commoning preparation. Must be not smaller than 4"));
174
175STATISTIC(PHINodeAlreadyExistsUpdate, "PHI node already in pre-increment form");
176STATISTIC(PHINodeAlreadyExistsDS, "PHI node already in DS form");
177STATISTIC(PHINodeAlreadyExistsDQ, "PHI node already in DQ form");
178STATISTIC(DSFormChainRewritten, "Num of DS form chain rewritten");
179STATISTIC(DQFormChainRewritten, "Num of DQ form chain rewritten");
180STATISTIC(UpdFormChainRewritten, "Num of update form chain rewritten");
181STATISTIC(ChainCommoningRewritten, "Num of commoning chains");
182
183namespace {
184 struct BucketElement {
185 BucketElement(const SCEV *O, Instruction *I) : Offset(O), Instr(I) {}
186 BucketElement(Instruction *I) : Offset(nullptr), Instr(I) {}
187
188 const SCEV *Offset;
189 Instruction *Instr;
190 };
191
192 struct Bucket {
193 Bucket(const SCEV *B, Instruction *I)
194 : BaseSCEV(B), Elements(1, BucketElement(I)) {
195 ChainSize = 0;
196 }
197
198 // The base of the whole bucket.
199 const SCEV *BaseSCEV;
200
201 // All elements in the bucket. In the bucket, the element with the BaseSCEV
202 // has no offset and all other elements are stored as offsets to the
203 // BaseSCEV.
204 SmallVector<BucketElement, 16> Elements;
205
206 // The potential chains size. This is used for chain commoning only.
207 unsigned ChainSize;
208
209 // The base for each potential chain. This is used for chain commoning only.
210 SmallVector<BucketElement, 16> ChainBases;
211 };
212
213 // "UpdateForm" is not a real PPC instruction form, it stands for dform
214 // load/store with update like ldu/stdu, or Prefetch intrinsic.
215 // For DS form instructions, their displacements must be multiple of 4.
216 // For DQ form instructions, their displacements must be multiple of 16.
217 enum PrepForm { UpdateForm = 1, DSForm = 4, DQForm = 16, ChainCommoning };
218
219 class PPCLoopInstrFormPrep : public FunctionPass {
220 public:
221 static char ID; // Pass ID, replacement for typeid
222
223 PPCLoopInstrFormPrep(PPCTargetMachine &TM) : FunctionPass(ID), TM(&TM) {}
224
225 void getAnalysisUsage(AnalysisUsage &AU) const override {
226 AU.addPreserved<DominatorTreeWrapperPass>();
227 AU.addRequired<LoopInfoWrapperPass>();
228 AU.addPreserved<LoopInfoWrapperPass>();
229 AU.addRequired<ScalarEvolutionWrapperPass>();
230 }
231
232 bool runOnFunction(Function &F) override;
233
234 private:
235 PPCTargetMachine *TM = nullptr;
236 const PPCSubtarget *ST;
237 DominatorTree *DT;
238 LoopInfo *LI;
239 ScalarEvolution *SE;
240 bool PreserveLCSSA;
241 bool HasCandidateForPrepare;
242
243 /// Successful preparation number for Update/DS/DQ form in all inner most
244 /// loops. One successful preparation will put one common base out of loop,
245 /// this may leads to register presure like LICM does.
246 /// Make sure total preparation number can be controlled by option.
247 unsigned SuccPrepCount;
248
249 bool runOnLoop(Loop *L);
250
251 /// Check if required PHI node is already exist in Loop \p L.
252 bool alreadyPrepared(Loop *L, Instruction *MemI,
253 const SCEV *BasePtrStartSCEV,
254 const SCEV *BasePtrIncSCEV, PrepForm Form);
255
256 /// Get the value which defines the increment SCEV \p BasePtrIncSCEV.
257 Value *getNodeForInc(Loop *L, Instruction *MemI,
258 const SCEV *BasePtrIncSCEV);
259
260 /// Common chains to reuse offsets for a loop to reduce register pressure.
261 bool chainCommoning(Loop *L, SmallVector<Bucket, 16> &Buckets);
262
263 /// Find out the potential commoning chains and their bases.
264 bool prepareBasesForCommoningChains(Bucket &BucketChain);
265
266 /// Rewrite load/store according to the common chains.
267 bool rewriteLoadStoresForCommoningChains(
268 Loop *L, Bucket &Bucket, SmallPtrSet<BasicBlock *, 16> &BBChanged);
269
270 /// Collect condition matched(\p isValidCandidate() returns true)
271 /// candidates in Loop \p L.
272 SmallVector<Bucket, 16> collectCandidates(
273 Loop *L,
274 std::function<bool(const Instruction *, Value *, const Type *)>
275 isValidCandidate,
276 std::function<bool(const SCEV *)> isValidDiff,
277 unsigned MaxCandidateNum);
278
279 /// Add a candidate to candidates \p Buckets if diff between candidate and
280 /// one base in \p Buckets matches \p isValidDiff.
281 void addOneCandidate(Instruction *MemI, const SCEV *LSCEV,
282 SmallVector<Bucket, 16> &Buckets,
283 std::function<bool(const SCEV *)> isValidDiff,
284 unsigned MaxCandidateNum);
285
286 /// Prepare all candidates in \p Buckets for update form.
287 bool updateFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets);
288
289 /// Prepare all candidates in \p Buckets for displacement form, now for
290 /// ds/dq.
291 bool dispFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets, PrepForm Form);
292
293 /// Prepare for one chain \p BucketChain, find the best base element and
294 /// update all other elements in \p BucketChain accordingly.
295 /// \p Form is used to find the best base element.
296 /// If success, best base element must be stored as the first element of
297 /// \p BucketChain.
298 /// Return false if no base element found, otherwise return true.
299 bool prepareBaseForDispFormChain(Bucket &BucketChain, PrepForm Form);
300
301 /// Prepare for one chain \p BucketChain, find the best base element and
302 /// update all other elements in \p BucketChain accordingly.
303 /// If success, best base element must be stored as the first element of
304 /// \p BucketChain.
305 /// Return false if no base element found, otherwise return true.
306 bool prepareBaseForUpdateFormChain(Bucket &BucketChain);
307
308 /// Rewrite load/store instructions in \p BucketChain according to
309 /// preparation.
310 bool rewriteLoadStores(Loop *L, Bucket &BucketChain,
311 SmallPtrSet<BasicBlock *, 16> &BBChanged,
312 PrepForm Form);
313
314 /// Rewrite for the base load/store of a chain.
315 std::pair<Instruction *, Instruction *>
316 rewriteForBase(Loop *L, const SCEVAddRecExpr *BasePtrSCEV,
317 Instruction *BaseMemI, bool CanPreInc, PrepForm Form,
318 SCEVExpander &SCEVE, SmallPtrSet<Value *, 16> &DeletedPtrs);
319
320 /// Rewrite for the other load/stores of a chain according to the new \p
321 /// Base.
322 Instruction *
323 rewriteForBucketElement(std::pair<Instruction *, Instruction *> Base,
324 const BucketElement &Element, Value *OffToBase,
325 SmallPtrSet<Value *, 16> &DeletedPtrs);
326 };
327
328} // end anonymous namespace
329
330char PPCLoopInstrFormPrep::ID = 0;
331static const char *name = "Prepare loop for ppc preferred instruction forms";
332INITIALIZE_PASS_BEGIN(PPCLoopInstrFormPrep, DEBUG_TYPE, name, false, false)
333INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
334INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
335INITIALIZE_PASS_END(PPCLoopInstrFormPrep, DEBUG_TYPE, name, false, false)
336
337static constexpr StringRef PHINodeNameSuffix = ".phi";
338static constexpr StringRef CastNodeNameSuffix = ".cast";
339static constexpr StringRef GEPNodeIncNameSuffix = ".inc";
340static constexpr StringRef GEPNodeOffNameSuffix = ".off";
341
342FunctionPass *llvm::createPPCLoopInstrFormPrepPass(PPCTargetMachine &TM) {
343 return new PPCLoopInstrFormPrep(TM);
344}
345
346static bool IsPtrInBounds(Value *BasePtr) {
347 Value *StrippedBasePtr = BasePtr;
348 while (BitCastInst *BC = dyn_cast<BitCastInst>(Val: StrippedBasePtr))
349 StrippedBasePtr = BC->getOperand(i_nocapture: 0);
350 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Val: StrippedBasePtr))
351 return GEP->isInBounds();
352
353 return false;
354}
355
356static std::string getInstrName(const Value *I, StringRef Suffix) {
357 assert(I && "Invalid paramater!");
358 if (I->hasName())
359 return (I->getName() + Suffix).str();
360 else
361 return "";
362}
363
364static Value *getPointerOperandAndType(Value *MemI,
365 Type **PtrElementType = nullptr) {
366
367 Value *PtrValue = nullptr;
368 Type *PointerElementType = nullptr;
369
370 if (LoadInst *LMemI = dyn_cast<LoadInst>(Val: MemI)) {
371 PtrValue = LMemI->getPointerOperand();
372 PointerElementType = LMemI->getType();
373 } else if (StoreInst *SMemI = dyn_cast<StoreInst>(Val: MemI)) {
374 PtrValue = SMemI->getPointerOperand();
375 PointerElementType = SMemI->getValueOperand()->getType();
376 } else if (IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(Val: MemI)) {
377 PointerElementType = Type::getInt8Ty(C&: MemI->getContext());
378 if (IMemI->getIntrinsicID() == Intrinsic::prefetch ||
379 IMemI->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp) {
380 PtrValue = IMemI->getArgOperand(i: 0);
381 } else if (IMemI->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp) {
382 PtrValue = IMemI->getArgOperand(i: 1);
383 }
384 }
385 /*Get ElementType if PtrElementType is not null.*/
386 if (PtrElementType)
387 *PtrElementType = PointerElementType;
388
389 return PtrValue;
390}
391
392bool PPCLoopInstrFormPrep::runOnFunction(Function &F) {
393 if (skipFunction(F))
394 return false;
395
396 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
397 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
398 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
399 DT = DTWP ? &DTWP->getDomTree() : nullptr;
400 PreserveLCSSA = mustPreserveAnalysisID(AID&: LCSSAID);
401 ST = TM ? TM->getSubtargetImpl(F) : nullptr;
402 SuccPrepCount = 0;
403
404 bool MadeChange = false;
405
406 for (Loop *I : *LI)
407 for (Loop *L : depth_first(G: I))
408 MadeChange |= runOnLoop(L);
409
410 return MadeChange;
411}
412
413// Finding the minimal(chain_number + reusable_offset_number) is a complicated
414// algorithmic problem.
415// For now, the algorithm used here is simply adjusted to handle the case for
416// manually unrolling cases.
417// FIXME: use a more powerful algorithm to find minimal sum of chain_number and
418// reusable_offset_number for one base with multiple offsets.
419bool PPCLoopInstrFormPrep::prepareBasesForCommoningChains(Bucket &CBucket) {
420 // The minimal size for profitable chain commoning:
421 // A1 = base + offset1
422 // A2 = base + offset2 (offset2 - offset1 = X)
423 // A3 = base + offset3
424 // A4 = base + offset4 (offset4 - offset3 = X)
425 // ======>
426 // base1 = base + offset1
427 // base2 = base + offset3
428 // A1 = base1
429 // A2 = base1 + X
430 // A3 = base2
431 // A4 = base2 + X
432 //
433 // There is benefit because of reuse of offest 'X'.
434
435 assert(ChainCommonPrepMinThreshold >= 4 &&
436 "Thredhold can not be smaller than 4!\n");
437 if (CBucket.Elements.size() < ChainCommonPrepMinThreshold)
438 return false;
439
440 // We simply select the FirstOffset as the first reusable offset between each
441 // chain element 1 and element 0.
442 const SCEV *FirstOffset = CBucket.Elements[1].Offset;
443
444 // Figure out how many times above FirstOffset is used in the chain.
445 // For a success commoning chain candidate, offset difference between each
446 // chain element 1 and element 0 must be also FirstOffset.
447 unsigned FirstOffsetReusedCount = 1;
448
449 // Figure out how many times above FirstOffset is used in the first chain.
450 // Chain number is FirstOffsetReusedCount / FirstOffsetReusedCountInFirstChain
451 unsigned FirstOffsetReusedCountInFirstChain = 1;
452
453 unsigned EleNum = CBucket.Elements.size();
454 bool SawChainSeparater = false;
455 for (unsigned j = 2; j != EleNum; ++j) {
456 if (SE->getMinusSCEV(LHS: CBucket.Elements[j].Offset,
457 RHS: CBucket.Elements[j - 1].Offset) == FirstOffset) {
458 if (!SawChainSeparater)
459 FirstOffsetReusedCountInFirstChain++;
460 FirstOffsetReusedCount++;
461 } else
462 // For now, if we meet any offset which is not FirstOffset, we assume we
463 // find a new Chain.
464 // This makes us miss some opportunities.
465 // For example, we can common:
466 //
467 // {OffsetA, Offset A, OffsetB, OffsetA, OffsetA, OffsetB}
468 //
469 // as two chains:
470 // {{OffsetA, Offset A, OffsetB}, {OffsetA, OffsetA, OffsetB}}
471 // FirstOffsetReusedCount = 4; FirstOffsetReusedCountInFirstChain = 2
472 //
473 // But we fail to common:
474 //
475 // {OffsetA, OffsetB, OffsetA, OffsetA, OffsetB, OffsetA}
476 // FirstOffsetReusedCount = 4; FirstOffsetReusedCountInFirstChain = 1
477
478 SawChainSeparater = true;
479 }
480
481 // FirstOffset is not reused, skip this bucket.
482 if (FirstOffsetReusedCount == 1)
483 return false;
484
485 unsigned ChainNum =
486 FirstOffsetReusedCount / FirstOffsetReusedCountInFirstChain;
487
488 // All elements are increased by FirstOffset.
489 // The number of chains should be sqrt(EleNum).
490 if (!SawChainSeparater)
491 ChainNum = (unsigned)sqrt(x: (double)EleNum);
492
493 CBucket.ChainSize = (unsigned)(EleNum / ChainNum);
494
495 // If this is not a perfect chain(eg: not all elements can be put inside
496 // commoning chains.), skip now.
497 if (CBucket.ChainSize * ChainNum != EleNum)
498 return false;
499
500 if (SawChainSeparater) {
501 // Check that the offset seqs are the same for all chains.
502 for (unsigned i = 1; i < CBucket.ChainSize; i++)
503 for (unsigned j = 1; j < ChainNum; j++)
504 if (CBucket.Elements[i].Offset !=
505 SE->getMinusSCEV(LHS: CBucket.Elements[i + j * CBucket.ChainSize].Offset,
506 RHS: CBucket.Elements[j * CBucket.ChainSize].Offset))
507 return false;
508 }
509
510 for (unsigned i = 0; i < ChainNum; i++)
511 CBucket.ChainBases.push_back(Elt: CBucket.Elements[i * CBucket.ChainSize]);
512
513 LLVM_DEBUG(dbgs() << "Bucket has " << ChainNum << " chains.\n");
514
515 return true;
516}
517
518bool PPCLoopInstrFormPrep::chainCommoning(Loop *L,
519 SmallVector<Bucket, 16> &Buckets) {
520 bool MadeChange = false;
521
522 if (Buckets.empty())
523 return MadeChange;
524
525 SmallPtrSet<BasicBlock *, 16> BBChanged;
526
527 for (auto &Bucket : Buckets) {
528 if (prepareBasesForCommoningChains(CBucket&: Bucket))
529 MadeChange |= rewriteLoadStoresForCommoningChains(L, Bucket, BBChanged);
530 }
531
532 if (MadeChange)
533 for (auto *BB : BBChanged)
534 DeleteDeadPHIs(BB);
535 return MadeChange;
536}
537
538bool PPCLoopInstrFormPrep::rewriteLoadStoresForCommoningChains(
539 Loop *L, Bucket &Bucket, SmallPtrSet<BasicBlock *, 16> &BBChanged) {
540 bool MadeChange = false;
541
542 assert(Bucket.Elements.size() ==
543 Bucket.ChainBases.size() * Bucket.ChainSize &&
544 "invalid bucket for chain commoning!\n");
545 SmallPtrSet<Value *, 16> DeletedPtrs;
546
547 BasicBlock *LoopPredecessor = L->getLoopPredecessor();
548
549 SCEVExpander SCEVE(*SE, "loopprepare-chaincommon");
550
551 for (unsigned ChainIdx = 0; ChainIdx < Bucket.ChainBases.size(); ++ChainIdx) {
552 unsigned BaseElemIdx = Bucket.ChainSize * ChainIdx;
553 const SCEV *BaseSCEV =
554 ChainIdx ? SE->getAddExpr(LHS: Bucket.BaseSCEV,
555 RHS: Bucket.Elements[BaseElemIdx].Offset)
556 .getPointer()
557 : Bucket.BaseSCEV;
558 const SCEVAddRecExpr *BasePtrSCEV = cast<SCEVAddRecExpr>(Val: BaseSCEV);
559
560 // Make sure the base is able to expand.
561 if (!SCEVE.isSafeToExpand(S: BasePtrSCEV->getStart()))
562 return MadeChange;
563
564 assert(BasePtrSCEV->isAffine() &&
565 "Invalid SCEV type for the base ptr for a candidate chain!\n");
566
567 std::pair<Instruction *, Instruction *> Base = rewriteForBase(
568 L, BasePtrSCEV, BaseMemI: Bucket.Elements[BaseElemIdx].Instr,
569 CanPreInc: false /* CanPreInc */, Form: ChainCommoning, SCEVE, DeletedPtrs);
570
571 if (!Base.first || !Base.second)
572 return MadeChange;
573
574 // Keep track of the replacement pointer values we've inserted so that we
575 // don't generate more pointer values than necessary.
576 SmallPtrSet<Value *, 16> NewPtrs;
577 NewPtrs.insert(Ptr: Base.first);
578
579 for (unsigned Idx = BaseElemIdx + 1; Idx < BaseElemIdx + Bucket.ChainSize;
580 ++Idx) {
581 BucketElement &I = Bucket.Elements[Idx];
582 Value *Ptr = getPointerOperandAndType(MemI: I.Instr);
583 assert(Ptr && "No pointer operand");
584 if (NewPtrs.count(Ptr))
585 continue;
586
587 const SCEV *OffsetSCEV =
588 BaseElemIdx ? SE->getMinusSCEV(LHS: Bucket.Elements[Idx].Offset,
589 RHS: Bucket.Elements[BaseElemIdx].Offset)
590 : Bucket.Elements[Idx].Offset;
591
592 // Make sure offset is able to expand. Only need to check one time as the
593 // offsets are reused between different chains.
594 if (!BaseElemIdx)
595 if (!SCEVE.isSafeToExpand(S: OffsetSCEV))
596 return false;
597
598 Value *OffsetValue = SCEVE.expandCodeFor(
599 SH: OffsetSCEV, Ty: OffsetSCEV->getType(), I: LoopPredecessor->getTerminator());
600
601 Instruction *NewPtr = rewriteForBucketElement(Base, Element: Bucket.Elements[Idx],
602 OffToBase: OffsetValue, DeletedPtrs);
603
604 assert(NewPtr && "Wrong rewrite!\n");
605 NewPtrs.insert(Ptr: NewPtr);
606 }
607
608 ++ChainCommoningRewritten;
609 }
610
611 // Clear the rewriter cache, because values that are in the rewriter's cache
612 // can be deleted below, causing the AssertingVH in the cache to trigger.
613 SCEVE.clear();
614
615 for (auto *Ptr : DeletedPtrs) {
616 if (Instruction *IDel = dyn_cast<Instruction>(Val: Ptr))
617 BBChanged.insert(Ptr: IDel->getParent());
618 RecursivelyDeleteTriviallyDeadInstructions(V: Ptr);
619 }
620
621 MadeChange = true;
622 return MadeChange;
623}
624
625// Rewrite the new base according to BasePtrSCEV.
626// bb.loop.preheader:
627// %newstart = ...
628// bb.loop.body:
629// %phinode = phi [ %newstart, %bb.loop.preheader ], [ %add, %bb.loop.body ]
630// ...
631// %add = getelementptr %phinode, %inc
632//
633// First returned instruciton is %phinode (or a type cast to %phinode), caller
634// needs this value to rewrite other load/stores in the same chain.
635// Second returned instruction is %add, caller needs this value to rewrite other
636// load/stores in the same chain.
637std::pair<Instruction *, Instruction *>
638PPCLoopInstrFormPrep::rewriteForBase(Loop *L, const SCEVAddRecExpr *BasePtrSCEV,
639 Instruction *BaseMemI, bool CanPreInc,
640 PrepForm Form, SCEVExpander &SCEVE,
641 SmallPtrSet<Value *, 16> &DeletedPtrs) {
642
643 LLVM_DEBUG(dbgs() << "PIP: Transforming: " << *BasePtrSCEV << "\n");
644
645 assert(BasePtrSCEV->getLoop() == L && "AddRec for the wrong loop?");
646
647 Value *BasePtr = getPointerOperandAndType(MemI: BaseMemI);
648 assert(BasePtr && "No pointer operand");
649
650 Type *I8Ty = Type::getInt8Ty(C&: BaseMemI->getParent()->getContext());
651 Type *I8PtrTy =
652 PointerType::get(C&: BaseMemI->getParent()->getContext(),
653 AddressSpace: BasePtr->getType()->getPointerAddressSpace());
654
655 bool IsConstantInc = false;
656 const SCEV *BasePtrIncSCEV = BasePtrSCEV->getStepRecurrence(SE&: *SE);
657 Value *IncNode = getNodeForInc(L, MemI: BaseMemI, BasePtrIncSCEV);
658
659 const SCEVConstant *BasePtrIncConstantSCEV =
660 dyn_cast<SCEVConstant>(Val: BasePtrIncSCEV);
661 if (BasePtrIncConstantSCEV)
662 IsConstantInc = true;
663
664 // No valid representation for the increment.
665 if (!IncNode) {
666 LLVM_DEBUG(dbgs() << "Loop Increasement can not be represented!\n");
667 return std::make_pair(x: nullptr, y: nullptr);
668 }
669
670 if (Form == UpdateForm && !IsConstantInc && !EnableUpdateFormForNonConstInc) {
671 LLVM_DEBUG(
672 dbgs()
673 << "Update form prepare for non-const increment is not enabled!\n");
674 return std::make_pair(x: nullptr, y: nullptr);
675 }
676
677 const SCEV *BasePtrStartSCEV = nullptr;
678 if (CanPreInc) {
679 assert(SE->isLoopInvariant(BasePtrIncSCEV, L) &&
680 "Increment is not loop invariant!\n");
681 BasePtrStartSCEV = SE->getMinusSCEV(LHS: BasePtrSCEV->getStart(),
682 RHS: IsConstantInc ? BasePtrIncConstantSCEV
683 : BasePtrIncSCEV);
684 } else
685 BasePtrStartSCEV = BasePtrSCEV->getStart();
686
687 if (alreadyPrepared(L, MemI: BaseMemI, BasePtrStartSCEV, BasePtrIncSCEV, Form)) {
688 LLVM_DEBUG(dbgs() << "Instruction form is already prepared!\n");
689 return std::make_pair(x: nullptr, y: nullptr);
690 }
691
692 LLVM_DEBUG(dbgs() << "PIP: New start is: " << *BasePtrStartSCEV << "\n");
693
694 BasicBlock *Header = L->getHeader();
695 unsigned HeaderLoopPredCount = pred_size(BB: Header);
696 BasicBlock *LoopPredecessor = L->getLoopPredecessor();
697
698 PHINode *NewPHI = PHINode::Create(Ty: I8PtrTy, NumReservedValues: HeaderLoopPredCount,
699 NameStr: getInstrName(I: BaseMemI, Suffix: PHINodeNameSuffix));
700 NewPHI->insertBefore(InsertPos: Header->getFirstNonPHIIt());
701
702 Value *BasePtrStart = SCEVE.expandCodeFor(SH: BasePtrStartSCEV, Ty: I8PtrTy,
703 I: LoopPredecessor->getTerminator());
704
705 // Note that LoopPredecessor might occur in the predecessor list multiple
706 // times, and we need to add it the right number of times.
707 for (auto *PI : predecessors(BB: Header)) {
708 if (PI != LoopPredecessor)
709 continue;
710
711 NewPHI->addIncoming(V: BasePtrStart, BB: LoopPredecessor);
712 }
713
714 Instruction *PtrInc = nullptr;
715 Instruction *NewBasePtr = nullptr;
716 if (CanPreInc) {
717 BasicBlock::iterator InsPoint = Header->getFirstInsertionPt();
718 PtrInc = GetElementPtrInst::Create(
719 PointeeType: I8Ty, Ptr: NewPHI, IdxList: IncNode, NameStr: getInstrName(I: BaseMemI, Suffix: GEPNodeIncNameSuffix),
720 InsertBefore: InsPoint);
721 cast<GetElementPtrInst>(Val: PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr));
722 for (auto *PI : predecessors(BB: Header)) {
723 if (PI == LoopPredecessor)
724 continue;
725
726 NewPHI->addIncoming(V: PtrInc, BB: PI);
727 }
728 if (PtrInc->getType() != BasePtr->getType())
729 NewBasePtr =
730 new BitCastInst(PtrInc, BasePtr->getType(),
731 getInstrName(I: PtrInc, Suffix: CastNodeNameSuffix), InsPoint);
732 else
733 NewBasePtr = PtrInc;
734 } else {
735 // Note that LoopPredecessor might occur in the predecessor list multiple
736 // times, and we need to make sure no more incoming value for them in PHI.
737 for (auto *PI : predecessors(BB: Header)) {
738 if (PI == LoopPredecessor)
739 continue;
740
741 // For the latch predecessor, we need to insert a GEP just before the
742 // terminator to increase the address.
743 BasicBlock *BB = PI;
744 BasicBlock::iterator InsPoint = BB->getTerminator()->getIterator();
745 PtrInc = GetElementPtrInst::Create(
746 PointeeType: I8Ty, Ptr: NewPHI, IdxList: IncNode, NameStr: getInstrName(I: BaseMemI, Suffix: GEPNodeIncNameSuffix),
747 InsertBefore: InsPoint);
748 cast<GetElementPtrInst>(Val: PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr));
749
750 NewPHI->addIncoming(V: PtrInc, BB: PI);
751 }
752 PtrInc = NewPHI;
753 if (NewPHI->getType() != BasePtr->getType())
754 NewBasePtr = new BitCastInst(NewPHI, BasePtr->getType(),
755 getInstrName(I: NewPHI, Suffix: CastNodeNameSuffix),
756 Header->getFirstInsertionPt());
757 else
758 NewBasePtr = NewPHI;
759 }
760
761 BasePtr->replaceAllUsesWith(V: NewBasePtr);
762
763 DeletedPtrs.insert(Ptr: BasePtr);
764
765 return std::make_pair(x&: NewBasePtr, y&: PtrInc);
766}
767
768Instruction *PPCLoopInstrFormPrep::rewriteForBucketElement(
769 std::pair<Instruction *, Instruction *> Base, const BucketElement &Element,
770 Value *OffToBase, SmallPtrSet<Value *, 16> &DeletedPtrs) {
771 Instruction *NewBasePtr = Base.first;
772 Instruction *PtrInc = Base.second;
773 assert((NewBasePtr && PtrInc) && "base does not exist!\n");
774
775 Type *I8Ty = Type::getInt8Ty(C&: PtrInc->getParent()->getContext());
776
777 Value *Ptr = getPointerOperandAndType(MemI: Element.Instr);
778 assert(Ptr && "No pointer operand");
779
780 Instruction *RealNewPtr;
781 if (!Element.Offset ||
782 (isa<SCEVConstant>(Val: Element.Offset) &&
783 cast<SCEVConstant>(Val: Element.Offset)->getValue()->isZero())) {
784 RealNewPtr = NewBasePtr;
785 } else {
786 std::optional<BasicBlock::iterator> PtrIP = std::nullopt;
787 if (Instruction *I = dyn_cast<Instruction>(Val: Ptr))
788 PtrIP = I->getIterator();
789
790 if (PtrIP && isa<Instruction>(Val: NewBasePtr) &&
791 cast<Instruction>(Val: NewBasePtr)->getParent() == (*PtrIP)->getParent())
792 PtrIP = std::nullopt;
793 else if (PtrIP && isa<PHINode>(Val: *PtrIP))
794 PtrIP = (*PtrIP)->getParent()->getFirstInsertionPt();
795 else if (!PtrIP)
796 PtrIP = Element.Instr->getIterator();
797
798 assert(OffToBase && "There should be an offset for non base element!\n");
799 GetElementPtrInst *NewPtr = GetElementPtrInst::Create(
800 PointeeType: I8Ty, Ptr: PtrInc, IdxList: OffToBase,
801 NameStr: getInstrName(I: Element.Instr, Suffix: GEPNodeOffNameSuffix));
802 if (PtrIP)
803 NewPtr->insertBefore(BB&: *(*PtrIP)->getParent(), InsertPos: *PtrIP);
804 else
805 NewPtr->insertAfter(InsertPos: cast<Instruction>(Val: PtrInc));
806 NewPtr->setIsInBounds(IsPtrInBounds(BasePtr: Ptr));
807 RealNewPtr = NewPtr;
808 }
809
810 Instruction *ReplNewPtr;
811 if (Ptr->getType() != RealNewPtr->getType()) {
812 ReplNewPtr = new BitCastInst(RealNewPtr, Ptr->getType(),
813 getInstrName(I: Ptr, Suffix: CastNodeNameSuffix));
814 ReplNewPtr->insertAfter(InsertPos: RealNewPtr);
815 } else
816 ReplNewPtr = RealNewPtr;
817
818 Ptr->replaceAllUsesWith(V: ReplNewPtr);
819 DeletedPtrs.insert(Ptr);
820
821 return ReplNewPtr;
822}
823
824void PPCLoopInstrFormPrep::addOneCandidate(
825 Instruction *MemI, const SCEV *LSCEV, SmallVector<Bucket, 16> &Buckets,
826 std::function<bool(const SCEV *)> isValidDiff, unsigned MaxCandidateNum) {
827 assert((MemI && getPointerOperandAndType(MemI)) &&
828 "Candidate should be a memory instruction.");
829 assert(LSCEV && "Invalid SCEV for Ptr value.");
830
831 bool FoundBucket = false;
832 for (auto &B : Buckets) {
833 if (cast<SCEVAddRecExpr>(Val: B.BaseSCEV)->getStepRecurrence(SE&: *SE) !=
834 cast<SCEVAddRecExpr>(Val: LSCEV)->getStepRecurrence(SE&: *SE))
835 continue;
836 const SCEV *Diff = SE->getMinusSCEV(LHS: LSCEV, RHS: B.BaseSCEV);
837 if (isValidDiff(Diff)) {
838 B.Elements.push_back(Elt: BucketElement(Diff, MemI));
839 FoundBucket = true;
840 break;
841 }
842 }
843
844 if (!FoundBucket) {
845 if (Buckets.size() == MaxCandidateNum) {
846 LLVM_DEBUG(dbgs() << "Can not prepare more chains, reach maximum limit "
847 << MaxCandidateNum << "\n");
848 return;
849 }
850 Buckets.push_back(Elt: Bucket(LSCEV, MemI));
851 }
852}
853
854SmallVector<Bucket, 16> PPCLoopInstrFormPrep::collectCandidates(
855 Loop *L,
856 std::function<bool(const Instruction *, Value *, const Type *)>
857 isValidCandidate,
858 std::function<bool(const SCEV *)> isValidDiff, unsigned MaxCandidateNum) {
859 SmallVector<Bucket, 16> Buckets;
860
861 for (const auto &BB : L->blocks())
862 for (auto &J : *BB) {
863 Value *PtrValue = nullptr;
864 Type *PointerElementType = nullptr;
865 PtrValue = getPointerOperandAndType(MemI: &J, PtrElementType: &PointerElementType);
866
867 if (!PtrValue)
868 continue;
869
870 if (PtrValue->getType()->getPointerAddressSpace())
871 continue;
872
873 if (L->isLoopInvariant(V: PtrValue))
874 continue;
875
876 const SCEV *LSCEV = SE->getSCEVAtScope(V: PtrValue, L);
877 const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(Val: LSCEV);
878 if (!LARSCEV || LARSCEV->getLoop() != L)
879 continue;
880
881 // Mark that we have candidates for preparing.
882 HasCandidateForPrepare = true;
883
884 if (isValidCandidate(&J, PtrValue, PointerElementType))
885 addOneCandidate(MemI: &J, LSCEV, Buckets, isValidDiff, MaxCandidateNum);
886 }
887 return Buckets;
888}
889
890bool PPCLoopInstrFormPrep::prepareBaseForDispFormChain(Bucket &BucketChain,
891 PrepForm Form) {
892 // RemainderOffsetInfo details:
893 // key: value of (Offset urem DispConstraint). For DSForm, it can
894 // be [0, 4).
895 // first of pair: the index of first BucketElement whose remainder is equal
896 // to key. For key 0, this value must be 0.
897 // second of pair: number of load/stores with the same remainder.
898 DenseMap<unsigned, std::pair<unsigned, unsigned>> RemainderOffsetInfo;
899
900 for (unsigned j = 0, je = BucketChain.Elements.size(); j != je; ++j) {
901 if (!BucketChain.Elements[j].Offset)
902 RemainderOffsetInfo[0] = std::make_pair(x: 0, y: 1);
903 else {
904 unsigned Remainder = cast<SCEVConstant>(Val: BucketChain.Elements[j].Offset)
905 ->getAPInt()
906 .urem(RHS: Form);
907 if (!RemainderOffsetInfo.contains(Val: Remainder))
908 RemainderOffsetInfo[Remainder] = std::make_pair(x&: j, y: 1);
909 else
910 RemainderOffsetInfo[Remainder].second++;
911 }
912 }
913 // Currently we choose the most profitable base as the one which has the max
914 // number of load/store with same remainder.
915 // FIXME: adjust the base selection strategy according to load/store offset
916 // distribution.
917 // For example, if we have one candidate chain for DS form preparation, which
918 // contains following load/stores with different remainders:
919 // 1: 10 load/store whose remainder is 1;
920 // 2: 9 load/store whose remainder is 2;
921 // 3: 1 for remainder 3 and 0 for remainder 0;
922 // Now we will choose the first load/store whose remainder is 1 as base and
923 // adjust all other load/stores according to new base, so we will get 10 DS
924 // form and 10 X form.
925 // But we should be more clever, for this case we could use two bases, one for
926 // remainder 1 and the other for remainder 2, thus we could get 19 DS form and
927 // 1 X form.
928 unsigned MaxCountRemainder = 0;
929 for (unsigned j = 0; j < (unsigned)Form; j++)
930 if (auto It = RemainderOffsetInfo.find(Val: j);
931 It != RemainderOffsetInfo.end() &&
932 It->second.second > RemainderOffsetInfo[MaxCountRemainder].second)
933 MaxCountRemainder = j;
934
935 // Abort when there are too few insts with common base.
936 if (RemainderOffsetInfo[MaxCountRemainder].second < DispFormPrepMinThreshold)
937 return false;
938
939 // If the first value is most profitable, no needed to adjust BucketChain
940 // elements as they are substracted the first value when collecting.
941 if (MaxCountRemainder == 0)
942 return true;
943
944 // Adjust load/store to the new chosen base.
945 const SCEV *Offset =
946 BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first].Offset;
947 BucketChain.BaseSCEV = SE->getAddExpr(LHS: BucketChain.BaseSCEV, RHS: Offset);
948 for (auto &E : BucketChain.Elements) {
949 if (E.Offset)
950 E.Offset = cast<SCEVConstant>(Val: SE->getMinusSCEV(LHS: E.Offset, RHS: Offset));
951 else
952 E.Offset = cast<SCEVConstant>(Val: SE->getNegativeSCEV(V: Offset));
953 }
954
955 std::swap(a&: BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first],
956 b&: BucketChain.Elements[0]);
957 return true;
958}
959
960// FIXME: implement a more clever base choosing policy.
961// Currently we always choose an exist load/store offset. This maybe lead to
962// suboptimal code sequences. For example, for one DS chain with offsets
963// {-32769, 2003, 2007, 2011}, we choose -32769 as base offset, and left disp
964// for load/stores are {0, 34772, 34776, 34780}. Though each offset now is a
965// multipler of 4, it cannot be represented by sint16.
966bool PPCLoopInstrFormPrep::prepareBaseForUpdateFormChain(Bucket &BucketChain) {
967 // We have a choice now of which instruction's memory operand we use as the
968 // base for the generated PHI. Always picking the first instruction in each
969 // bucket does not work well, specifically because that instruction might
970 // be a prefetch (and there are no pre-increment dcbt variants). Otherwise,
971 // the choice is somewhat arbitrary, because the backend will happily
972 // generate direct offsets from both the pre-incremented and
973 // post-incremented pointer values. Thus, we'll pick the first non-prefetch
974 // instruction in each bucket, and adjust the recurrence and other offsets
975 // accordingly.
976 for (int j = 0, je = BucketChain.Elements.size(); j != je; ++j) {
977 if (auto *II = dyn_cast<IntrinsicInst>(Val: BucketChain.Elements[j].Instr))
978 if (II->getIntrinsicID() == Intrinsic::prefetch)
979 continue;
980
981 // If we'd otherwise pick the first element anyway, there's nothing to do.
982 if (j == 0)
983 break;
984
985 // If our chosen element has no offset from the base pointer, there's
986 // nothing to do.
987 if (!BucketChain.Elements[j].Offset ||
988 cast<SCEVConstant>(Val: BucketChain.Elements[j].Offset)->isZero())
989 break;
990
991 const SCEV *Offset = BucketChain.Elements[j].Offset;
992 BucketChain.BaseSCEV = SE->getAddExpr(LHS: BucketChain.BaseSCEV, RHS: Offset);
993 for (auto &E : BucketChain.Elements) {
994 if (E.Offset)
995 E.Offset = cast<SCEVConstant>(Val: SE->getMinusSCEV(LHS: E.Offset, RHS: Offset));
996 else
997 E.Offset = cast<SCEVConstant>(Val: SE->getNegativeSCEV(V: Offset));
998 }
999
1000 std::swap(a&: BucketChain.Elements[j], b&: BucketChain.Elements[0]);
1001 break;
1002 }
1003 return true;
1004}
1005
1006bool PPCLoopInstrFormPrep::rewriteLoadStores(
1007 Loop *L, Bucket &BucketChain, SmallPtrSet<BasicBlock *, 16> &BBChanged,
1008 PrepForm Form) {
1009 bool MadeChange = false;
1010
1011 const SCEVAddRecExpr *BasePtrSCEV =
1012 cast<SCEVAddRecExpr>(Val: BucketChain.BaseSCEV);
1013 if (!BasePtrSCEV->isAffine())
1014 return MadeChange;
1015
1016 SCEVExpander SCEVE(*SE, "loopprepare-formrewrite");
1017 if (!SCEVE.isSafeToExpand(S: BasePtrSCEV->getStart()))
1018 return MadeChange;
1019
1020 SmallPtrSet<Value *, 16> DeletedPtrs;
1021
1022 // For some DS form load/store instructions, it can also be an update form,
1023 // if the stride is constant and is a multipler of 4. Use update form if
1024 // prefer it.
1025 bool CanPreInc = (Form == UpdateForm ||
1026 ((Form == DSForm) &&
1027 isa<SCEVConstant>(Val: BasePtrSCEV->getStepRecurrence(SE&: *SE)) &&
1028 !cast<SCEVConstant>(Val: BasePtrSCEV->getStepRecurrence(SE&: *SE))
1029 ->getAPInt()
1030 .urem(RHS: 4) &&
1031 PreferUpdateForm));
1032
1033 std::pair<Instruction *, Instruction *> Base =
1034 rewriteForBase(L, BasePtrSCEV, BaseMemI: BucketChain.Elements.begin()->Instr,
1035 CanPreInc, Form, SCEVE, DeletedPtrs);
1036
1037 if (!Base.first || !Base.second)
1038 return MadeChange;
1039
1040 // Keep track of the replacement pointer values we've inserted so that we
1041 // don't generate more pointer values than necessary.
1042 SmallPtrSet<Value *, 16> NewPtrs;
1043 NewPtrs.insert(Ptr: Base.first);
1044
1045 for (const BucketElement &BE : llvm::drop_begin(RangeOrContainer&: BucketChain.Elements)) {
1046 Value *Ptr = getPointerOperandAndType(MemI: BE.Instr);
1047 assert(Ptr && "No pointer operand");
1048 if (NewPtrs.count(Ptr))
1049 continue;
1050
1051 Instruction *NewPtr = rewriteForBucketElement(
1052 Base, Element: BE,
1053 OffToBase: BE.Offset ? cast<SCEVConstant>(Val: BE.Offset)->getValue() : nullptr,
1054 DeletedPtrs);
1055 assert(NewPtr && "wrong rewrite!\n");
1056 NewPtrs.insert(Ptr: NewPtr);
1057 }
1058
1059 // Clear the rewriter cache, because values that are in the rewriter's cache
1060 // can be deleted below, causing the AssertingVH in the cache to trigger.
1061 SCEVE.clear();
1062
1063 for (auto *Ptr : DeletedPtrs) {
1064 if (Instruction *IDel = dyn_cast<Instruction>(Val: Ptr))
1065 BBChanged.insert(Ptr: IDel->getParent());
1066 RecursivelyDeleteTriviallyDeadInstructions(V: Ptr);
1067 }
1068
1069 MadeChange = true;
1070
1071 SuccPrepCount++;
1072
1073 if (Form == DSForm && !CanPreInc)
1074 DSFormChainRewritten++;
1075 else if (Form == DQForm)
1076 DQFormChainRewritten++;
1077 else if (Form == UpdateForm || (Form == DSForm && CanPreInc))
1078 UpdFormChainRewritten++;
1079
1080 return MadeChange;
1081}
1082
1083bool PPCLoopInstrFormPrep::updateFormPrep(Loop *L,
1084 SmallVector<Bucket, 16> &Buckets) {
1085 bool MadeChange = false;
1086 if (Buckets.empty())
1087 return MadeChange;
1088 SmallPtrSet<BasicBlock *, 16> BBChanged;
1089 for (auto &Bucket : Buckets)
1090 // The base address of each bucket is transformed into a phi and the others
1091 // are rewritten based on new base.
1092 if (prepareBaseForUpdateFormChain(BucketChain&: Bucket))
1093 MadeChange |= rewriteLoadStores(L, BucketChain&: Bucket, BBChanged, Form: UpdateForm);
1094
1095 if (MadeChange)
1096 for (auto *BB : BBChanged)
1097 DeleteDeadPHIs(BB);
1098 return MadeChange;
1099}
1100
1101bool PPCLoopInstrFormPrep::dispFormPrep(Loop *L,
1102 SmallVector<Bucket, 16> &Buckets,
1103 PrepForm Form) {
1104 bool MadeChange = false;
1105
1106 if (Buckets.empty())
1107 return MadeChange;
1108
1109 SmallPtrSet<BasicBlock *, 16> BBChanged;
1110 for (auto &Bucket : Buckets) {
1111 if (Bucket.Elements.size() < DispFormPrepMinThreshold)
1112 continue;
1113 if (prepareBaseForDispFormChain(BucketChain&: Bucket, Form))
1114 MadeChange |= rewriteLoadStores(L, BucketChain&: Bucket, BBChanged, Form);
1115 }
1116
1117 if (MadeChange)
1118 for (auto *BB : BBChanged)
1119 DeleteDeadPHIs(BB);
1120 return MadeChange;
1121}
1122
1123// Find the loop invariant increment node for SCEV BasePtrIncSCEV.
1124// bb.loop.preheader:
1125// %start = ...
1126// bb.loop.body:
1127// %phinode = phi [ %start, %bb.loop.preheader ], [ %add, %bb.loop.body ]
1128// ...
1129// %add = add %phinode, %inc ; %inc is what we want to get.
1130//
1131Value *PPCLoopInstrFormPrep::getNodeForInc(Loop *L, Instruction *MemI,
1132 const SCEV *BasePtrIncSCEV) {
1133 // If the increment is a constant, no definition is needed.
1134 // Return the value directly.
1135 if (isa<SCEVConstant>(Val: BasePtrIncSCEV))
1136 return cast<SCEVConstant>(Val: BasePtrIncSCEV)->getValue();
1137
1138 if (!SE->isLoopInvariant(S: BasePtrIncSCEV, L))
1139 return nullptr;
1140
1141 BasicBlock *BB = MemI->getParent();
1142 if (!BB)
1143 return nullptr;
1144
1145 BasicBlock *LatchBB = L->getLoopLatch();
1146
1147 if (!LatchBB)
1148 return nullptr;
1149
1150 // Run through the PHIs and check their operands to find valid representation
1151 // for the increment SCEV.
1152 iterator_range<BasicBlock::phi_iterator> PHIIter = BB->phis();
1153 for (auto &CurrentPHI : PHIIter) {
1154 PHINode *CurrentPHINode = dyn_cast<PHINode>(Val: &CurrentPHI);
1155 if (!CurrentPHINode)
1156 continue;
1157
1158 if (!SE->isSCEVable(Ty: CurrentPHINode->getType()))
1159 continue;
1160
1161 const SCEV *PHISCEV = SE->getSCEVAtScope(V: CurrentPHINode, L);
1162
1163 const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast<SCEVAddRecExpr>(Val: PHISCEV);
1164 if (!PHIBasePtrSCEV)
1165 continue;
1166
1167 const SCEV *PHIBasePtrIncSCEV = PHIBasePtrSCEV->getStepRecurrence(SE&: *SE);
1168
1169 if (!PHIBasePtrIncSCEV || (PHIBasePtrIncSCEV != BasePtrIncSCEV))
1170 continue;
1171
1172 // Get the incoming value from the loop latch and check if the value has
1173 // the add form with the required increment.
1174 if (CurrentPHINode->getBasicBlockIndex(BB: LatchBB) < 0)
1175 continue;
1176 if (Instruction *I = dyn_cast<Instruction>(
1177 Val: CurrentPHINode->getIncomingValueForBlock(BB: LatchBB))) {
1178 Value *StrippedBaseI = I;
1179 while (BitCastInst *BC = dyn_cast<BitCastInst>(Val: StrippedBaseI))
1180 StrippedBaseI = BC->getOperand(i_nocapture: 0);
1181
1182 Instruction *StrippedI = dyn_cast<Instruction>(Val: StrippedBaseI);
1183 if (!StrippedI)
1184 continue;
1185
1186 // LSR pass may add a getelementptr instruction to do the loop increment,
1187 // also search in that getelementptr instruction.
1188 if (StrippedI->getOpcode() == Instruction::Add ||
1189 (StrippedI->getOpcode() == Instruction::GetElementPtr &&
1190 StrippedI->getNumOperands() == 2)) {
1191 if (SE->getSCEVAtScope(V: StrippedI->getOperand(i: 0), L) == BasePtrIncSCEV)
1192 return StrippedI->getOperand(i: 0);
1193 if (SE->getSCEVAtScope(V: StrippedI->getOperand(i: 1), L) == BasePtrIncSCEV)
1194 return StrippedI->getOperand(i: 1);
1195 }
1196 }
1197 }
1198 return nullptr;
1199}
1200
1201// In order to prepare for the preferred instruction form, a PHI is added.
1202// This function will check to see if that PHI already exists and will return
1203// true if it found an existing PHI with the matched start and increment as the
1204// one we wanted to create.
1205bool PPCLoopInstrFormPrep::alreadyPrepared(Loop *L, Instruction *MemI,
1206 const SCEV *BasePtrStartSCEV,
1207 const SCEV *BasePtrIncSCEV,
1208 PrepForm Form) {
1209 BasicBlock *BB = MemI->getParent();
1210 if (!BB)
1211 return false;
1212
1213 BasicBlock *PredBB = L->getLoopPredecessor();
1214 BasicBlock *LatchBB = L->getLoopLatch();
1215
1216 if (!PredBB || !LatchBB)
1217 return false;
1218
1219 // Run through the PHIs and see if we have some that looks like a preparation
1220 iterator_range<BasicBlock::phi_iterator> PHIIter = BB->phis();
1221 for (auto & CurrentPHI : PHIIter) {
1222 PHINode *CurrentPHINode = dyn_cast<PHINode>(Val: &CurrentPHI);
1223 if (!CurrentPHINode)
1224 continue;
1225
1226 if (!SE->isSCEVable(Ty: CurrentPHINode->getType()))
1227 continue;
1228
1229 const SCEV *PHISCEV = SE->getSCEVAtScope(V: CurrentPHINode, L);
1230
1231 const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast<SCEVAddRecExpr>(Val: PHISCEV);
1232 if (!PHIBasePtrSCEV)
1233 continue;
1234
1235 const SCEVConstant *PHIBasePtrIncSCEV =
1236 dyn_cast<SCEVConstant>(Val: PHIBasePtrSCEV->getStepRecurrence(SE&: *SE));
1237 if (!PHIBasePtrIncSCEV)
1238 continue;
1239
1240 if (CurrentPHINode->getNumIncomingValues() == 2) {
1241 if ((CurrentPHINode->getIncomingBlock(i: 0) == LatchBB &&
1242 CurrentPHINode->getIncomingBlock(i: 1) == PredBB) ||
1243 (CurrentPHINode->getIncomingBlock(i: 1) == LatchBB &&
1244 CurrentPHINode->getIncomingBlock(i: 0) == PredBB)) {
1245 if (PHIBasePtrIncSCEV == BasePtrIncSCEV) {
1246 // The existing PHI (CurrentPHINode) has the same start and increment
1247 // as the PHI that we wanted to create.
1248 if ((Form == UpdateForm || Form == ChainCommoning ) &&
1249 PHIBasePtrSCEV->getStart() == BasePtrStartSCEV) {
1250 ++PHINodeAlreadyExistsUpdate;
1251 return true;
1252 }
1253 if (Form == DSForm || Form == DQForm) {
1254 const SCEVConstant *Diff = dyn_cast<SCEVConstant>(
1255 Val: SE->getMinusSCEV(LHS: PHIBasePtrSCEV->getStart(), RHS: BasePtrStartSCEV));
1256 if (Diff && !Diff->getAPInt().urem(RHS: Form)) {
1257 if (Form == DSForm)
1258 ++PHINodeAlreadyExistsDS;
1259 else
1260 ++PHINodeAlreadyExistsDQ;
1261 return true;
1262 }
1263 }
1264 }
1265 }
1266 }
1267 }
1268 return false;
1269}
1270
1271bool PPCLoopInstrFormPrep::runOnLoop(Loop *L) {
1272 bool MadeChange = false;
1273
1274 // Only prep. the inner-most loop
1275 if (!L->isInnermost())
1276 return MadeChange;
1277
1278 // Return if already done enough preparation.
1279 if (SuccPrepCount >= MaxVarsPrep)
1280 return MadeChange;
1281
1282 LLVM_DEBUG(dbgs() << "PIP: Examining: " << *L << "\n");
1283
1284 BasicBlock *LoopPredecessor = L->getLoopPredecessor();
1285 // If there is no loop predecessor, or the loop predecessor's terminator
1286 // returns a value (which might contribute to determining the loop's
1287 // iteration space), insert a new preheader for the loop.
1288 if (!LoopPredecessor ||
1289 !LoopPredecessor->getTerminator()->getType()->isVoidTy()) {
1290 LoopPredecessor = InsertPreheaderForLoop(L, DT, LI, MSSAU: nullptr, PreserveLCSSA);
1291 if (LoopPredecessor)
1292 MadeChange = true;
1293 }
1294 if (!LoopPredecessor) {
1295 LLVM_DEBUG(dbgs() << "PIP fails since no predecessor for current loop.\n");
1296 return MadeChange;
1297 }
1298 // Check if a load/store has update form. This lambda is used by function
1299 // collectCandidates which can collect candidates for types defined by lambda.
1300 auto isUpdateFormCandidate = [&](const Instruction *I, Value *PtrValue,
1301 const Type *PointerElementType) {
1302 assert((PtrValue && I) && "Invalid parameter!");
1303 // There are no update forms for Altivec vector load/stores.
1304 if (ST && ST->hasAltivec() && PointerElementType->isVectorTy())
1305 return false;
1306 // There are no update forms for P10 lxvp/stxvp intrinsic.
1307 auto *II = dyn_cast<IntrinsicInst>(Val: I);
1308 if (II && ((II->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp) ||
1309 II->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp))
1310 return false;
1311 // See getPreIndexedAddressParts, the displacement for LDU/STDU has to
1312 // be 4's multiple (DS-form). For i64 loads/stores when the displacement
1313 // fits in a 16-bit signed field but isn't a multiple of 4, it will be
1314 // useless and possible to break some original well-form addressing mode
1315 // to make this pre-inc prep for it.
1316 if (PointerElementType->isIntegerTy(BitWidth: 64)) {
1317 const SCEV *LSCEV = SE->getSCEVAtScope(V: PtrValue, L);
1318 const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(Val: LSCEV);
1319 if (!LARSCEV || LARSCEV->getLoop() != L)
1320 return false;
1321 if (const SCEVConstant *StepConst =
1322 dyn_cast<SCEVConstant>(Val: LARSCEV->getStepRecurrence(SE&: *SE))) {
1323 const APInt &ConstInt = StepConst->getValue()->getValue();
1324 if (ConstInt.isSignedIntN(N: 16) && ConstInt.srem(RHS: 4) != 0)
1325 return false;
1326 }
1327 }
1328 return true;
1329 };
1330
1331 // Check if a load/store has DS form.
1332 auto isDSFormCandidate = [](const Instruction *I, Value *PtrValue,
1333 const Type *PointerElementType) {
1334 assert((PtrValue && I) && "Invalid parameter!");
1335 if (isa<IntrinsicInst>(Val: I))
1336 return false;
1337 return (PointerElementType->isIntegerTy(BitWidth: 64)) ||
1338 (PointerElementType->isFloatTy()) ||
1339 (PointerElementType->isDoubleTy()) ||
1340 (PointerElementType->isIntegerTy(BitWidth: 32) &&
1341 llvm::any_of(Range: I->users(),
1342 P: [](const User *U) { return isa<SExtInst>(Val: U); }));
1343 };
1344
1345 // Check if a load/store has DQ form.
1346 auto isDQFormCandidate = [&](const Instruction *I, Value *PtrValue,
1347 const Type *PointerElementType) {
1348 assert((PtrValue && I) && "Invalid parameter!");
1349 // Check if it is a P10 lxvp/stxvp intrinsic.
1350 auto *II = dyn_cast<IntrinsicInst>(Val: I);
1351 if (II)
1352 return II->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp ||
1353 II->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp;
1354 // Check if it is a P9 vector load/store.
1355 return ST && ST->hasP9Vector() && (PointerElementType->isVectorTy());
1356 };
1357
1358 // Check if a load/store is candidate for chain commoning.
1359 // If the SCEV is only with one ptr operand in its start, we can use that
1360 // start as a chain separator. Mark this load/store as a candidate.
1361 auto isChainCommoningCandidate = [&](const Instruction *I, Value *PtrValue,
1362 const Type *PointerElementType) {
1363 const SCEVAddRecExpr *ARSCEV =
1364 cast<SCEVAddRecExpr>(Val: SE->getSCEVAtScope(V: PtrValue, L));
1365 if (!ARSCEV)
1366 return false;
1367
1368 if (!ARSCEV->isAffine())
1369 return false;
1370
1371 const SCEV *Start = ARSCEV->getStart();
1372
1373 // A single pointer. We can treat it as offset 0.
1374 if (isa<SCEVUnknown>(Val: Start) && Start->getType()->isPointerTy())
1375 return true;
1376
1377 const SCEVAddExpr *ASCEV = dyn_cast<SCEVAddExpr>(Val: Start);
1378
1379 // We need a SCEVAddExpr to include both base and offset.
1380 if (!ASCEV)
1381 return false;
1382
1383 // Make sure there is only one pointer operand(base) and all other operands
1384 // are integer type.
1385 bool SawPointer = false;
1386 for (const SCEV *Op : ASCEV->operands()) {
1387 if (Op->getType()->isPointerTy()) {
1388 if (SawPointer)
1389 return false;
1390 SawPointer = true;
1391 } else if (!Op->getType()->isIntegerTy())
1392 return false;
1393 }
1394
1395 return SawPointer;
1396 };
1397
1398 // Check if the diff is a constant type. This is used for update/DS/DQ form
1399 // preparation.
1400 auto isValidConstantDiff = [](const SCEV *Diff) {
1401 return dyn_cast<SCEVConstant>(Val: Diff) != nullptr;
1402 };
1403
1404 // Make sure the diff between the base and new candidate is required type.
1405 // This is used for chain commoning preparation.
1406 auto isValidChainCommoningDiff = [](const SCEV *Diff) {
1407 assert(Diff && "Invalid Diff!\n");
1408
1409 // Don't mess up previous dform prepare.
1410 if (isa<SCEVConstant>(Val: Diff))
1411 return false;
1412
1413 // A single integer type offset.
1414 if (isa<SCEVUnknown>(Val: Diff) && Diff->getType()->isIntegerTy())
1415 return true;
1416
1417 const SCEVNAryExpr *ADiff = dyn_cast<SCEVNAryExpr>(Val: Diff);
1418 if (!ADiff)
1419 return false;
1420
1421 for (const SCEV *Op : ADiff->operands())
1422 if (!Op->getType()->isIntegerTy())
1423 return false;
1424
1425 return true;
1426 };
1427
1428 HasCandidateForPrepare = false;
1429
1430 LLVM_DEBUG(dbgs() << "Start to prepare for update form.\n");
1431 // Collect buckets of comparable addresses used by loads and stores for update
1432 // form.
1433 SmallVector<Bucket, 16> UpdateFormBuckets = collectCandidates(
1434 L, isValidCandidate: isUpdateFormCandidate, isValidDiff: isValidConstantDiff, MaxCandidateNum: MaxVarsUpdateForm);
1435
1436 // Prepare for update form.
1437 if (!UpdateFormBuckets.empty())
1438 MadeChange |= updateFormPrep(L, Buckets&: UpdateFormBuckets);
1439 else if (!HasCandidateForPrepare) {
1440 LLVM_DEBUG(
1441 dbgs()
1442 << "No prepare candidates found, stop praparation for current loop!\n");
1443 // If no candidate for preparing, return early.
1444 return MadeChange;
1445 }
1446
1447 LLVM_DEBUG(dbgs() << "Start to prepare for DS form.\n");
1448 // Collect buckets of comparable addresses used by loads and stores for DS
1449 // form.
1450 SmallVector<Bucket, 16> DSFormBuckets = collectCandidates(
1451 L, isValidCandidate: isDSFormCandidate, isValidDiff: isValidConstantDiff, MaxCandidateNum: MaxVarsDSForm);
1452
1453 // Prepare for DS form.
1454 if (!DSFormBuckets.empty())
1455 MadeChange |= dispFormPrep(L, Buckets&: DSFormBuckets, Form: DSForm);
1456
1457 LLVM_DEBUG(dbgs() << "Start to prepare for DQ form.\n");
1458 // Collect buckets of comparable addresses used by loads and stores for DQ
1459 // form.
1460 SmallVector<Bucket, 16> DQFormBuckets = collectCandidates(
1461 L, isValidCandidate: isDQFormCandidate, isValidDiff: isValidConstantDiff, MaxCandidateNum: MaxVarsDQForm);
1462
1463 // Prepare for DQ form.
1464 if (!DQFormBuckets.empty())
1465 MadeChange |= dispFormPrep(L, Buckets&: DQFormBuckets, Form: DQForm);
1466
1467 // Collect buckets of comparable addresses used by loads and stores for chain
1468 // commoning. With chain commoning, we reuse offsets between the chains, so
1469 // the register pressure will be reduced.
1470 if (!EnableChainCommoning) {
1471 LLVM_DEBUG(dbgs() << "Chain commoning is not enabled.\n");
1472 return MadeChange;
1473 }
1474
1475 LLVM_DEBUG(dbgs() << "Start to prepare for chain commoning.\n");
1476 SmallVector<Bucket, 16> Buckets =
1477 collectCandidates(L, isValidCandidate: isChainCommoningCandidate, isValidDiff: isValidChainCommoningDiff,
1478 MaxCandidateNum: MaxVarsChainCommon);
1479
1480 // Prepare for chain commoning.
1481 if (!Buckets.empty())
1482 MadeChange |= chainCommoning(L, Buckets);
1483
1484 return MadeChange;
1485}
1486