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 : Bucket.BaseSCEV;
557 const SCEVAddRecExpr *BasePtrSCEV = cast<SCEVAddRecExpr>(Val: BaseSCEV);
558
559 // Make sure the base is able to expand.
560 if (!SCEVE.isSafeToExpand(S: BasePtrSCEV->getStart()))
561 return MadeChange;
562
563 assert(BasePtrSCEV->isAffine() &&
564 "Invalid SCEV type for the base ptr for a candidate chain!\n");
565
566 std::pair<Instruction *, Instruction *> Base = rewriteForBase(
567 L, BasePtrSCEV, BaseMemI: Bucket.Elements[BaseElemIdx].Instr,
568 CanPreInc: false /* CanPreInc */, Form: ChainCommoning, SCEVE, DeletedPtrs);
569
570 if (!Base.first || !Base.second)
571 return MadeChange;
572
573 // Keep track of the replacement pointer values we've inserted so that we
574 // don't generate more pointer values than necessary.
575 SmallPtrSet<Value *, 16> NewPtrs;
576 NewPtrs.insert(Ptr: Base.first);
577
578 for (unsigned Idx = BaseElemIdx + 1; Idx < BaseElemIdx + Bucket.ChainSize;
579 ++Idx) {
580 BucketElement &I = Bucket.Elements[Idx];
581 Value *Ptr = getPointerOperandAndType(MemI: I.Instr);
582 assert(Ptr && "No pointer operand");
583 if (NewPtrs.count(Ptr))
584 continue;
585
586 const SCEV *OffsetSCEV =
587 BaseElemIdx ? SE->getMinusSCEV(LHS: Bucket.Elements[Idx].Offset,
588 RHS: Bucket.Elements[BaseElemIdx].Offset)
589 : Bucket.Elements[Idx].Offset;
590
591 // Make sure offset is able to expand. Only need to check one time as the
592 // offsets are reused between different chains.
593 if (!BaseElemIdx)
594 if (!SCEVE.isSafeToExpand(S: OffsetSCEV))
595 return false;
596
597 Value *OffsetValue = SCEVE.expandCodeFor(
598 SH: OffsetSCEV, Ty: OffsetSCEV->getType(), I: LoopPredecessor->getTerminator());
599
600 Instruction *NewPtr = rewriteForBucketElement(Base, Element: Bucket.Elements[Idx],
601 OffToBase: OffsetValue, DeletedPtrs);
602
603 assert(NewPtr && "Wrong rewrite!\n");
604 NewPtrs.insert(Ptr: NewPtr);
605 }
606
607 ++ChainCommoningRewritten;
608 }
609
610 // Clear the rewriter cache, because values that are in the rewriter's cache
611 // can be deleted below, causing the AssertingVH in the cache to trigger.
612 SCEVE.clear();
613
614 for (auto *Ptr : DeletedPtrs) {
615 if (Instruction *IDel = dyn_cast<Instruction>(Val: Ptr))
616 BBChanged.insert(Ptr: IDel->getParent());
617 RecursivelyDeleteTriviallyDeadInstructions(V: Ptr);
618 }
619
620 MadeChange = true;
621 return MadeChange;
622}
623
624// Rewrite the new base according to BasePtrSCEV.
625// bb.loop.preheader:
626// %newstart = ...
627// bb.loop.body:
628// %phinode = phi [ %newstart, %bb.loop.preheader ], [ %add, %bb.loop.body ]
629// ...
630// %add = getelementptr %phinode, %inc
631//
632// First returned instruciton is %phinode (or a type cast to %phinode), caller
633// needs this value to rewrite other load/stores in the same chain.
634// Second returned instruction is %add, caller needs this value to rewrite other
635// load/stores in the same chain.
636std::pair<Instruction *, Instruction *>
637PPCLoopInstrFormPrep::rewriteForBase(Loop *L, const SCEVAddRecExpr *BasePtrSCEV,
638 Instruction *BaseMemI, bool CanPreInc,
639 PrepForm Form, SCEVExpander &SCEVE,
640 SmallPtrSet<Value *, 16> &DeletedPtrs) {
641
642 LLVM_DEBUG(dbgs() << "PIP: Transforming: " << *BasePtrSCEV << "\n");
643
644 assert(BasePtrSCEV->getLoop() == L && "AddRec for the wrong loop?");
645
646 Value *BasePtr = getPointerOperandAndType(MemI: BaseMemI);
647 assert(BasePtr && "No pointer operand");
648
649 Type *I8Ty = Type::getInt8Ty(C&: BaseMemI->getParent()->getContext());
650 Type *I8PtrTy =
651 PointerType::get(C&: BaseMemI->getParent()->getContext(),
652 AddressSpace: BasePtr->getType()->getPointerAddressSpace());
653
654 bool IsConstantInc = false;
655 const SCEV *BasePtrIncSCEV = BasePtrSCEV->getStepRecurrence(SE&: *SE);
656 Value *IncNode = getNodeForInc(L, MemI: BaseMemI, BasePtrIncSCEV);
657
658 const SCEVConstant *BasePtrIncConstantSCEV =
659 dyn_cast<SCEVConstant>(Val: BasePtrIncSCEV);
660 if (BasePtrIncConstantSCEV)
661 IsConstantInc = true;
662
663 // No valid representation for the increment.
664 if (!IncNode) {
665 LLVM_DEBUG(dbgs() << "Loop Increasement can not be represented!\n");
666 return std::make_pair(x: nullptr, y: nullptr);
667 }
668
669 if (Form == UpdateForm && !IsConstantInc && !EnableUpdateFormForNonConstInc) {
670 LLVM_DEBUG(
671 dbgs()
672 << "Update form prepare for non-const increment is not enabled!\n");
673 return std::make_pair(x: nullptr, y: nullptr);
674 }
675
676 const SCEV *BasePtrStartSCEV = nullptr;
677 if (CanPreInc) {
678 assert(SE->isLoopInvariant(BasePtrIncSCEV, L) &&
679 "Increment is not loop invariant!\n");
680 BasePtrStartSCEV = SE->getMinusSCEV(LHS: BasePtrSCEV->getStart(),
681 RHS: IsConstantInc ? BasePtrIncConstantSCEV
682 : BasePtrIncSCEV);
683 } else
684 BasePtrStartSCEV = BasePtrSCEV->getStart();
685
686 if (alreadyPrepared(L, MemI: BaseMemI, BasePtrStartSCEV, BasePtrIncSCEV, Form)) {
687 LLVM_DEBUG(dbgs() << "Instruction form is already prepared!\n");
688 return std::make_pair(x: nullptr, y: nullptr);
689 }
690
691 LLVM_DEBUG(dbgs() << "PIP: New start is: " << *BasePtrStartSCEV << "\n");
692
693 BasicBlock *Header = L->getHeader();
694 unsigned HeaderLoopPredCount = pred_size(BB: Header);
695 BasicBlock *LoopPredecessor = L->getLoopPredecessor();
696
697 PHINode *NewPHI = PHINode::Create(Ty: I8PtrTy, NumReservedValues: HeaderLoopPredCount,
698 NameStr: getInstrName(I: BaseMemI, Suffix: PHINodeNameSuffix));
699 NewPHI->insertBefore(InsertPos: Header->getFirstNonPHIIt());
700
701 Value *BasePtrStart = SCEVE.expandCodeFor(SH: BasePtrStartSCEV, Ty: I8PtrTy,
702 I: LoopPredecessor->getTerminator());
703
704 // Note that LoopPredecessor might occur in the predecessor list multiple
705 // times, and we need to add it the right number of times.
706 for (auto *PI : predecessors(BB: Header)) {
707 if (PI != LoopPredecessor)
708 continue;
709
710 NewPHI->addIncoming(V: BasePtrStart, BB: LoopPredecessor);
711 }
712
713 Instruction *PtrInc = nullptr;
714 Instruction *NewBasePtr = nullptr;
715 if (CanPreInc) {
716 BasicBlock::iterator InsPoint = Header->getFirstInsertionPt();
717 PtrInc = GetElementPtrInst::Create(
718 PointeeType: I8Ty, Ptr: NewPHI, IdxList: IncNode, NameStr: getInstrName(I: BaseMemI, Suffix: GEPNodeIncNameSuffix),
719 InsertBefore: InsPoint);
720 cast<GetElementPtrInst>(Val: PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr));
721 for (auto *PI : predecessors(BB: Header)) {
722 if (PI == LoopPredecessor)
723 continue;
724
725 NewPHI->addIncoming(V: PtrInc, BB: PI);
726 }
727 if (PtrInc->getType() != BasePtr->getType())
728 NewBasePtr =
729 new BitCastInst(PtrInc, BasePtr->getType(),
730 getInstrName(I: PtrInc, Suffix: CastNodeNameSuffix), InsPoint);
731 else
732 NewBasePtr = PtrInc;
733 } else {
734 // Note that LoopPredecessor might occur in the predecessor list multiple
735 // times, and we need to make sure no more incoming value for them in PHI.
736 for (auto *PI : predecessors(BB: Header)) {
737 if (PI == LoopPredecessor)
738 continue;
739
740 // For the latch predecessor, we need to insert a GEP just before the
741 // terminator to increase the address.
742 BasicBlock *BB = PI;
743 BasicBlock::iterator InsPoint = BB->getTerminator()->getIterator();
744 PtrInc = GetElementPtrInst::Create(
745 PointeeType: I8Ty, Ptr: NewPHI, IdxList: IncNode, NameStr: getInstrName(I: BaseMemI, Suffix: GEPNodeIncNameSuffix),
746 InsertBefore: InsPoint);
747 cast<GetElementPtrInst>(Val: PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr));
748
749 NewPHI->addIncoming(V: PtrInc, BB: PI);
750 }
751 PtrInc = NewPHI;
752 if (NewPHI->getType() != BasePtr->getType())
753 NewBasePtr = new BitCastInst(NewPHI, BasePtr->getType(),
754 getInstrName(I: NewPHI, Suffix: CastNodeNameSuffix),
755 Header->getFirstInsertionPt());
756 else
757 NewBasePtr = NewPHI;
758 }
759
760 BasePtr->replaceAllUsesWith(V: NewBasePtr);
761
762 DeletedPtrs.insert(Ptr: BasePtr);
763
764 return std::make_pair(x&: NewBasePtr, y&: PtrInc);
765}
766
767Instruction *PPCLoopInstrFormPrep::rewriteForBucketElement(
768 std::pair<Instruction *, Instruction *> Base, const BucketElement &Element,
769 Value *OffToBase, SmallPtrSet<Value *, 16> &DeletedPtrs) {
770 Instruction *NewBasePtr = Base.first;
771 Instruction *PtrInc = Base.second;
772 assert((NewBasePtr && PtrInc) && "base does not exist!\n");
773
774 Type *I8Ty = Type::getInt8Ty(C&: PtrInc->getParent()->getContext());
775
776 Value *Ptr = getPointerOperandAndType(MemI: Element.Instr);
777 assert(Ptr && "No pointer operand");
778
779 Instruction *RealNewPtr;
780 if (!Element.Offset ||
781 (isa<SCEVConstant>(Val: Element.Offset) &&
782 cast<SCEVConstant>(Val: Element.Offset)->getValue()->isZero())) {
783 RealNewPtr = NewBasePtr;
784 } else {
785 std::optional<BasicBlock::iterator> PtrIP = std::nullopt;
786 if (Instruction *I = dyn_cast<Instruction>(Val: Ptr))
787 PtrIP = I->getIterator();
788
789 if (PtrIP && isa<Instruction>(Val: NewBasePtr) &&
790 cast<Instruction>(Val: NewBasePtr)->getParent() == (*PtrIP)->getParent())
791 PtrIP = std::nullopt;
792 else if (PtrIP && isa<PHINode>(Val: *PtrIP))
793 PtrIP = (*PtrIP)->getParent()->getFirstInsertionPt();
794 else if (!PtrIP)
795 PtrIP = Element.Instr->getIterator();
796
797 assert(OffToBase && "There should be an offset for non base element!\n");
798 GetElementPtrInst *NewPtr = GetElementPtrInst::Create(
799 PointeeType: I8Ty, Ptr: PtrInc, IdxList: OffToBase,
800 NameStr: getInstrName(I: Element.Instr, Suffix: GEPNodeOffNameSuffix));
801 if (PtrIP)
802 NewPtr->insertBefore(BB&: *(*PtrIP)->getParent(), InsertPos: *PtrIP);
803 else
804 NewPtr->insertAfter(InsertPos: cast<Instruction>(Val: PtrInc));
805 NewPtr->setIsInBounds(IsPtrInBounds(BasePtr: Ptr));
806 RealNewPtr = NewPtr;
807 }
808
809 Instruction *ReplNewPtr;
810 if (Ptr->getType() != RealNewPtr->getType()) {
811 ReplNewPtr = new BitCastInst(RealNewPtr, Ptr->getType(),
812 getInstrName(I: Ptr, Suffix: CastNodeNameSuffix));
813 ReplNewPtr->insertAfter(InsertPos: RealNewPtr);
814 } else
815 ReplNewPtr = RealNewPtr;
816
817 Ptr->replaceAllUsesWith(V: ReplNewPtr);
818 DeletedPtrs.insert(Ptr);
819
820 return ReplNewPtr;
821}
822
823void PPCLoopInstrFormPrep::addOneCandidate(
824 Instruction *MemI, const SCEV *LSCEV, SmallVector<Bucket, 16> &Buckets,
825 std::function<bool(const SCEV *)> isValidDiff, unsigned MaxCandidateNum) {
826 assert((MemI && getPointerOperandAndType(MemI)) &&
827 "Candidate should be a memory instruction.");
828 assert(LSCEV && "Invalid SCEV for Ptr value.");
829
830 bool FoundBucket = false;
831 for (auto &B : Buckets) {
832 if (cast<SCEVAddRecExpr>(Val: B.BaseSCEV)->getStepRecurrence(SE&: *SE) !=
833 cast<SCEVAddRecExpr>(Val: LSCEV)->getStepRecurrence(SE&: *SE))
834 continue;
835 const SCEV *Diff = SE->getMinusSCEV(LHS: LSCEV, RHS: B.BaseSCEV);
836 if (isValidDiff(Diff)) {
837 B.Elements.push_back(Elt: BucketElement(Diff, MemI));
838 FoundBucket = true;
839 break;
840 }
841 }
842
843 if (!FoundBucket) {
844 if (Buckets.size() == MaxCandidateNum) {
845 LLVM_DEBUG(dbgs() << "Can not prepare more chains, reach maximum limit "
846 << MaxCandidateNum << "\n");
847 return;
848 }
849 Buckets.push_back(Elt: Bucket(LSCEV, MemI));
850 }
851}
852
853SmallVector<Bucket, 16> PPCLoopInstrFormPrep::collectCandidates(
854 Loop *L,
855 std::function<bool(const Instruction *, Value *, const Type *)>
856 isValidCandidate,
857 std::function<bool(const SCEV *)> isValidDiff, unsigned MaxCandidateNum) {
858 SmallVector<Bucket, 16> Buckets;
859
860 for (const auto &BB : L->blocks())
861 for (auto &J : *BB) {
862 Value *PtrValue = nullptr;
863 Type *PointerElementType = nullptr;
864 PtrValue = getPointerOperandAndType(MemI: &J, PtrElementType: &PointerElementType);
865
866 if (!PtrValue)
867 continue;
868
869 if (PtrValue->getType()->getPointerAddressSpace())
870 continue;
871
872 if (L->isLoopInvariant(V: PtrValue))
873 continue;
874
875 const SCEV *LSCEV = SE->getSCEVAtScope(V: PtrValue, L);
876 const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(Val: LSCEV);
877 if (!LARSCEV || LARSCEV->getLoop() != L)
878 continue;
879
880 // Mark that we have candidates for preparing.
881 HasCandidateForPrepare = true;
882
883 if (isValidCandidate(&J, PtrValue, PointerElementType))
884 addOneCandidate(MemI: &J, LSCEV, Buckets, isValidDiff, MaxCandidateNum);
885 }
886 return Buckets;
887}
888
889bool PPCLoopInstrFormPrep::prepareBaseForDispFormChain(Bucket &BucketChain,
890 PrepForm Form) {
891 // RemainderOffsetInfo details:
892 // key: value of (Offset urem DispConstraint). For DSForm, it can
893 // be [0, 4).
894 // first of pair: the index of first BucketElement whose remainder is equal
895 // to key. For key 0, this value must be 0.
896 // second of pair: number of load/stores with the same remainder.
897 DenseMap<unsigned, std::pair<unsigned, unsigned>> RemainderOffsetInfo;
898
899 for (unsigned j = 0, je = BucketChain.Elements.size(); j != je; ++j) {
900 if (!BucketChain.Elements[j].Offset)
901 RemainderOffsetInfo[0] = std::make_pair(x: 0, y: 1);
902 else {
903 unsigned Remainder = cast<SCEVConstant>(Val: BucketChain.Elements[j].Offset)
904 ->getAPInt()
905 .urem(RHS: Form);
906 if (!RemainderOffsetInfo.contains(Val: Remainder))
907 RemainderOffsetInfo[Remainder] = std::make_pair(x&: j, y: 1);
908 else
909 RemainderOffsetInfo[Remainder].second++;
910 }
911 }
912 // Currently we choose the most profitable base as the one which has the max
913 // number of load/store with same remainder.
914 // FIXME: adjust the base selection strategy according to load/store offset
915 // distribution.
916 // For example, if we have one candidate chain for DS form preparation, which
917 // contains following load/stores with different remainders:
918 // 1: 10 load/store whose remainder is 1;
919 // 2: 9 load/store whose remainder is 2;
920 // 3: 1 for remainder 3 and 0 for remainder 0;
921 // Now we will choose the first load/store whose remainder is 1 as base and
922 // adjust all other load/stores according to new base, so we will get 10 DS
923 // form and 10 X form.
924 // But we should be more clever, for this case we could use two bases, one for
925 // remainder 1 and the other for remainder 2, thus we could get 19 DS form and
926 // 1 X form.
927 unsigned MaxCountRemainder = 0;
928 for (unsigned j = 0; j < (unsigned)Form; j++)
929 if (auto It = RemainderOffsetInfo.find(Val: j);
930 It != RemainderOffsetInfo.end() &&
931 It->second.second > RemainderOffsetInfo[MaxCountRemainder].second)
932 MaxCountRemainder = j;
933
934 // Abort when there are too few insts with common base.
935 if (RemainderOffsetInfo[MaxCountRemainder].second < DispFormPrepMinThreshold)
936 return false;
937
938 // If the first value is most profitable, no needed to adjust BucketChain
939 // elements as they are substracted the first value when collecting.
940 if (MaxCountRemainder == 0)
941 return true;
942
943 // Adjust load/store to the new chosen base.
944 const SCEV *Offset =
945 BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first].Offset;
946 BucketChain.BaseSCEV = SE->getAddExpr(LHS: BucketChain.BaseSCEV, RHS: Offset);
947 for (auto &E : BucketChain.Elements) {
948 if (E.Offset)
949 E.Offset = cast<SCEVConstant>(Val: SE->getMinusSCEV(LHS: E.Offset, RHS: Offset));
950 else
951 E.Offset = cast<SCEVConstant>(Val: SE->getNegativeSCEV(V: Offset));
952 }
953
954 std::swap(a&: BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first],
955 b&: BucketChain.Elements[0]);
956 return true;
957}
958
959// FIXME: implement a more clever base choosing policy.
960// Currently we always choose an exist load/store offset. This maybe lead to
961// suboptimal code sequences. For example, for one DS chain with offsets
962// {-32769, 2003, 2007, 2011}, we choose -32769 as base offset, and left disp
963// for load/stores are {0, 34772, 34776, 34780}. Though each offset now is a
964// multipler of 4, it cannot be represented by sint16.
965bool PPCLoopInstrFormPrep::prepareBaseForUpdateFormChain(Bucket &BucketChain) {
966 // We have a choice now of which instruction's memory operand we use as the
967 // base for the generated PHI. Always picking the first instruction in each
968 // bucket does not work well, specifically because that instruction might
969 // be a prefetch (and there are no pre-increment dcbt variants). Otherwise,
970 // the choice is somewhat arbitrary, because the backend will happily
971 // generate direct offsets from both the pre-incremented and
972 // post-incremented pointer values. Thus, we'll pick the first non-prefetch
973 // instruction in each bucket, and adjust the recurrence and other offsets
974 // accordingly.
975 for (int j = 0, je = BucketChain.Elements.size(); j != je; ++j) {
976 if (auto *II = dyn_cast<IntrinsicInst>(Val: BucketChain.Elements[j].Instr))
977 if (II->getIntrinsicID() == Intrinsic::prefetch)
978 continue;
979
980 // If we'd otherwise pick the first element anyway, there's nothing to do.
981 if (j == 0)
982 break;
983
984 // If our chosen element has no offset from the base pointer, there's
985 // nothing to do.
986 if (!BucketChain.Elements[j].Offset ||
987 cast<SCEVConstant>(Val: BucketChain.Elements[j].Offset)->isZero())
988 break;
989
990 const SCEV *Offset = BucketChain.Elements[j].Offset;
991 BucketChain.BaseSCEV = SE->getAddExpr(LHS: BucketChain.BaseSCEV, RHS: Offset);
992 for (auto &E : BucketChain.Elements) {
993 if (E.Offset)
994 E.Offset = cast<SCEVConstant>(Val: SE->getMinusSCEV(LHS: E.Offset, RHS: Offset));
995 else
996 E.Offset = cast<SCEVConstant>(Val: SE->getNegativeSCEV(V: Offset));
997 }
998
999 std::swap(a&: BucketChain.Elements[j], b&: BucketChain.Elements[0]);
1000 break;
1001 }
1002 return true;
1003}
1004
1005bool PPCLoopInstrFormPrep::rewriteLoadStores(
1006 Loop *L, Bucket &BucketChain, SmallPtrSet<BasicBlock *, 16> &BBChanged,
1007 PrepForm Form) {
1008 bool MadeChange = false;
1009
1010 const SCEVAddRecExpr *BasePtrSCEV =
1011 cast<SCEVAddRecExpr>(Val: BucketChain.BaseSCEV);
1012 if (!BasePtrSCEV->isAffine())
1013 return MadeChange;
1014
1015 SCEVExpander SCEVE(*SE, "loopprepare-formrewrite");
1016 if (!SCEVE.isSafeToExpand(S: BasePtrSCEV->getStart()))
1017 return MadeChange;
1018
1019 SmallPtrSet<Value *, 16> DeletedPtrs;
1020
1021 // For some DS form load/store instructions, it can also be an update form,
1022 // if the stride is constant and is a multipler of 4. Use update form if
1023 // prefer it.
1024 bool CanPreInc = (Form == UpdateForm ||
1025 ((Form == DSForm) &&
1026 isa<SCEVConstant>(Val: BasePtrSCEV->getStepRecurrence(SE&: *SE)) &&
1027 !cast<SCEVConstant>(Val: BasePtrSCEV->getStepRecurrence(SE&: *SE))
1028 ->getAPInt()
1029 .urem(RHS: 4) &&
1030 PreferUpdateForm));
1031
1032 std::pair<Instruction *, Instruction *> Base =
1033 rewriteForBase(L, BasePtrSCEV, BaseMemI: BucketChain.Elements.begin()->Instr,
1034 CanPreInc, Form, SCEVE, DeletedPtrs);
1035
1036 if (!Base.first || !Base.second)
1037 return MadeChange;
1038
1039 // Keep track of the replacement pointer values we've inserted so that we
1040 // don't generate more pointer values than necessary.
1041 SmallPtrSet<Value *, 16> NewPtrs;
1042 NewPtrs.insert(Ptr: Base.first);
1043
1044 for (const BucketElement &BE : llvm::drop_begin(RangeOrContainer&: BucketChain.Elements)) {
1045 Value *Ptr = getPointerOperandAndType(MemI: BE.Instr);
1046 assert(Ptr && "No pointer operand");
1047 if (NewPtrs.count(Ptr))
1048 continue;
1049
1050 Instruction *NewPtr = rewriteForBucketElement(
1051 Base, Element: BE,
1052 OffToBase: BE.Offset ? cast<SCEVConstant>(Val: BE.Offset)->getValue() : nullptr,
1053 DeletedPtrs);
1054 assert(NewPtr && "wrong rewrite!\n");
1055 NewPtrs.insert(Ptr: NewPtr);
1056 }
1057
1058 // Clear the rewriter cache, because values that are in the rewriter's cache
1059 // can be deleted below, causing the AssertingVH in the cache to trigger.
1060 SCEVE.clear();
1061
1062 for (auto *Ptr : DeletedPtrs) {
1063 if (Instruction *IDel = dyn_cast<Instruction>(Val: Ptr))
1064 BBChanged.insert(Ptr: IDel->getParent());
1065 RecursivelyDeleteTriviallyDeadInstructions(V: Ptr);
1066 }
1067
1068 MadeChange = true;
1069
1070 SuccPrepCount++;
1071
1072 if (Form == DSForm && !CanPreInc)
1073 DSFormChainRewritten++;
1074 else if (Form == DQForm)
1075 DQFormChainRewritten++;
1076 else if (Form == UpdateForm || (Form == DSForm && CanPreInc))
1077 UpdFormChainRewritten++;
1078
1079 return MadeChange;
1080}
1081
1082bool PPCLoopInstrFormPrep::updateFormPrep(Loop *L,
1083 SmallVector<Bucket, 16> &Buckets) {
1084 bool MadeChange = false;
1085 if (Buckets.empty())
1086 return MadeChange;
1087 SmallPtrSet<BasicBlock *, 16> BBChanged;
1088 for (auto &Bucket : Buckets)
1089 // The base address of each bucket is transformed into a phi and the others
1090 // are rewritten based on new base.
1091 if (prepareBaseForUpdateFormChain(BucketChain&: Bucket))
1092 MadeChange |= rewriteLoadStores(L, BucketChain&: Bucket, BBChanged, Form: UpdateForm);
1093
1094 if (MadeChange)
1095 for (auto *BB : BBChanged)
1096 DeleteDeadPHIs(BB);
1097 return MadeChange;
1098}
1099
1100bool PPCLoopInstrFormPrep::dispFormPrep(Loop *L,
1101 SmallVector<Bucket, 16> &Buckets,
1102 PrepForm Form) {
1103 bool MadeChange = false;
1104
1105 if (Buckets.empty())
1106 return MadeChange;
1107
1108 SmallPtrSet<BasicBlock *, 16> BBChanged;
1109 for (auto &Bucket : Buckets) {
1110 if (Bucket.Elements.size() < DispFormPrepMinThreshold)
1111 continue;
1112 if (prepareBaseForDispFormChain(BucketChain&: Bucket, Form))
1113 MadeChange |= rewriteLoadStores(L, BucketChain&: Bucket, BBChanged, Form);
1114 }
1115
1116 if (MadeChange)
1117 for (auto *BB : BBChanged)
1118 DeleteDeadPHIs(BB);
1119 return MadeChange;
1120}
1121
1122// Find the loop invariant increment node for SCEV BasePtrIncSCEV.
1123// bb.loop.preheader:
1124// %start = ...
1125// bb.loop.body:
1126// %phinode = phi [ %start, %bb.loop.preheader ], [ %add, %bb.loop.body ]
1127// ...
1128// %add = add %phinode, %inc ; %inc is what we want to get.
1129//
1130Value *PPCLoopInstrFormPrep::getNodeForInc(Loop *L, Instruction *MemI,
1131 const SCEV *BasePtrIncSCEV) {
1132 // If the increment is a constant, no definition is needed.
1133 // Return the value directly.
1134 if (isa<SCEVConstant>(Val: BasePtrIncSCEV))
1135 return cast<SCEVConstant>(Val: BasePtrIncSCEV)->getValue();
1136
1137 if (!SE->isLoopInvariant(S: BasePtrIncSCEV, L))
1138 return nullptr;
1139
1140 BasicBlock *BB = MemI->getParent();
1141 if (!BB)
1142 return nullptr;
1143
1144 BasicBlock *LatchBB = L->getLoopLatch();
1145
1146 if (!LatchBB)
1147 return nullptr;
1148
1149 // Run through the PHIs and check their operands to find valid representation
1150 // for the increment SCEV.
1151 iterator_range<BasicBlock::phi_iterator> PHIIter = BB->phis();
1152 for (auto &CurrentPHI : PHIIter) {
1153 PHINode *CurrentPHINode = dyn_cast<PHINode>(Val: &CurrentPHI);
1154 if (!CurrentPHINode)
1155 continue;
1156
1157 if (!SE->isSCEVable(Ty: CurrentPHINode->getType()))
1158 continue;
1159
1160 const SCEV *PHISCEV = SE->getSCEVAtScope(V: CurrentPHINode, L);
1161
1162 const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast<SCEVAddRecExpr>(Val: PHISCEV);
1163 if (!PHIBasePtrSCEV)
1164 continue;
1165
1166 const SCEV *PHIBasePtrIncSCEV = PHIBasePtrSCEV->getStepRecurrence(SE&: *SE);
1167
1168 if (!PHIBasePtrIncSCEV || (PHIBasePtrIncSCEV != BasePtrIncSCEV))
1169 continue;
1170
1171 // Get the incoming value from the loop latch and check if the value has
1172 // the add form with the required increment.
1173 if (CurrentPHINode->getBasicBlockIndex(BB: LatchBB) < 0)
1174 continue;
1175 if (Instruction *I = dyn_cast<Instruction>(
1176 Val: CurrentPHINode->getIncomingValueForBlock(BB: LatchBB))) {
1177 Value *StrippedBaseI = I;
1178 while (BitCastInst *BC = dyn_cast<BitCastInst>(Val: StrippedBaseI))
1179 StrippedBaseI = BC->getOperand(i_nocapture: 0);
1180
1181 Instruction *StrippedI = dyn_cast<Instruction>(Val: StrippedBaseI);
1182 if (!StrippedI)
1183 continue;
1184
1185 // LSR pass may add a getelementptr instruction to do the loop increment,
1186 // also search in that getelementptr instruction.
1187 if (StrippedI->getOpcode() == Instruction::Add ||
1188 (StrippedI->getOpcode() == Instruction::GetElementPtr &&
1189 StrippedI->getNumOperands() == 2)) {
1190 if (SE->getSCEVAtScope(V: StrippedI->getOperand(i: 0), L) == BasePtrIncSCEV)
1191 return StrippedI->getOperand(i: 0);
1192 if (SE->getSCEVAtScope(V: StrippedI->getOperand(i: 1), L) == BasePtrIncSCEV)
1193 return StrippedI->getOperand(i: 1);
1194 }
1195 }
1196 }
1197 return nullptr;
1198}
1199
1200// In order to prepare for the preferred instruction form, a PHI is added.
1201// This function will check to see if that PHI already exists and will return
1202// true if it found an existing PHI with the matched start and increment as the
1203// one we wanted to create.
1204bool PPCLoopInstrFormPrep::alreadyPrepared(Loop *L, Instruction *MemI,
1205 const SCEV *BasePtrStartSCEV,
1206 const SCEV *BasePtrIncSCEV,
1207 PrepForm Form) {
1208 BasicBlock *BB = MemI->getParent();
1209 if (!BB)
1210 return false;
1211
1212 BasicBlock *PredBB = L->getLoopPredecessor();
1213 BasicBlock *LatchBB = L->getLoopLatch();
1214
1215 if (!PredBB || !LatchBB)
1216 return false;
1217
1218 // Run through the PHIs and see if we have some that looks like a preparation
1219 iterator_range<BasicBlock::phi_iterator> PHIIter = BB->phis();
1220 for (auto & CurrentPHI : PHIIter) {
1221 PHINode *CurrentPHINode = dyn_cast<PHINode>(Val: &CurrentPHI);
1222 if (!CurrentPHINode)
1223 continue;
1224
1225 if (!SE->isSCEVable(Ty: CurrentPHINode->getType()))
1226 continue;
1227
1228 const SCEV *PHISCEV = SE->getSCEVAtScope(V: CurrentPHINode, L);
1229
1230 const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast<SCEVAddRecExpr>(Val: PHISCEV);
1231 if (!PHIBasePtrSCEV)
1232 continue;
1233
1234 const SCEVConstant *PHIBasePtrIncSCEV =
1235 dyn_cast<SCEVConstant>(Val: PHIBasePtrSCEV->getStepRecurrence(SE&: *SE));
1236 if (!PHIBasePtrIncSCEV)
1237 continue;
1238
1239 if (CurrentPHINode->getNumIncomingValues() == 2) {
1240 if ((CurrentPHINode->getIncomingBlock(i: 0) == LatchBB &&
1241 CurrentPHINode->getIncomingBlock(i: 1) == PredBB) ||
1242 (CurrentPHINode->getIncomingBlock(i: 1) == LatchBB &&
1243 CurrentPHINode->getIncomingBlock(i: 0) == PredBB)) {
1244 if (PHIBasePtrIncSCEV == BasePtrIncSCEV) {
1245 // The existing PHI (CurrentPHINode) has the same start and increment
1246 // as the PHI that we wanted to create.
1247 if ((Form == UpdateForm || Form == ChainCommoning ) &&
1248 PHIBasePtrSCEV->getStart() == BasePtrStartSCEV) {
1249 ++PHINodeAlreadyExistsUpdate;
1250 return true;
1251 }
1252 if (Form == DSForm || Form == DQForm) {
1253 const SCEVConstant *Diff = dyn_cast<SCEVConstant>(
1254 Val: SE->getMinusSCEV(LHS: PHIBasePtrSCEV->getStart(), RHS: BasePtrStartSCEV));
1255 if (Diff && !Diff->getAPInt().urem(RHS: Form)) {
1256 if (Form == DSForm)
1257 ++PHINodeAlreadyExistsDS;
1258 else
1259 ++PHINodeAlreadyExistsDQ;
1260 return true;
1261 }
1262 }
1263 }
1264 }
1265 }
1266 }
1267 return false;
1268}
1269
1270bool PPCLoopInstrFormPrep::runOnLoop(Loop *L) {
1271 bool MadeChange = false;
1272
1273 // Only prep. the inner-most loop
1274 if (!L->isInnermost())
1275 return MadeChange;
1276
1277 // Return if already done enough preparation.
1278 if (SuccPrepCount >= MaxVarsPrep)
1279 return MadeChange;
1280
1281 LLVM_DEBUG(dbgs() << "PIP: Examining: " << *L << "\n");
1282
1283 BasicBlock *LoopPredecessor = L->getLoopPredecessor();
1284 // If there is no loop predecessor, or the loop predecessor's terminator
1285 // returns a value (which might contribute to determining the loop's
1286 // iteration space), insert a new preheader for the loop.
1287 if (!LoopPredecessor ||
1288 !LoopPredecessor->getTerminator()->getType()->isVoidTy()) {
1289 LoopPredecessor = InsertPreheaderForLoop(L, DT, LI, MSSAU: nullptr, PreserveLCSSA);
1290 if (LoopPredecessor)
1291 MadeChange = true;
1292 }
1293 if (!LoopPredecessor) {
1294 LLVM_DEBUG(dbgs() << "PIP fails since no predecessor for current loop.\n");
1295 return MadeChange;
1296 }
1297 // Check if a load/store has update form. This lambda is used by function
1298 // collectCandidates which can collect candidates for types defined by lambda.
1299 auto isUpdateFormCandidate = [&](const Instruction *I, Value *PtrValue,
1300 const Type *PointerElementType) {
1301 assert((PtrValue && I) && "Invalid parameter!");
1302 // There are no update forms for Altivec vector load/stores.
1303 if (ST && ST->hasAltivec() && PointerElementType->isVectorTy())
1304 return false;
1305 // There are no update forms for P10 lxvp/stxvp intrinsic.
1306 auto *II = dyn_cast<IntrinsicInst>(Val: I);
1307 if (II && ((II->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp) ||
1308 II->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp))
1309 return false;
1310 // See getPreIndexedAddressParts, the displacement for LDU/STDU has to
1311 // be 4's multiple (DS-form). For i64 loads/stores when the displacement
1312 // fits in a 16-bit signed field but isn't a multiple of 4, it will be
1313 // useless and possible to break some original well-form addressing mode
1314 // to make this pre-inc prep for it.
1315 if (PointerElementType->isIntegerTy(Bitwidth: 64)) {
1316 const SCEV *LSCEV = SE->getSCEVAtScope(V: PtrValue, L);
1317 const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(Val: LSCEV);
1318 if (!LARSCEV || LARSCEV->getLoop() != L)
1319 return false;
1320 if (const SCEVConstant *StepConst =
1321 dyn_cast<SCEVConstant>(Val: LARSCEV->getStepRecurrence(SE&: *SE))) {
1322 const APInt &ConstInt = StepConst->getValue()->getValue();
1323 if (ConstInt.isSignedIntN(N: 16) && ConstInt.srem(RHS: 4) != 0)
1324 return false;
1325 }
1326 }
1327 return true;
1328 };
1329
1330 // Check if a load/store has DS form.
1331 auto isDSFormCandidate = [](const Instruction *I, Value *PtrValue,
1332 const Type *PointerElementType) {
1333 assert((PtrValue && I) && "Invalid parameter!");
1334 if (isa<IntrinsicInst>(Val: I))
1335 return false;
1336 return (PointerElementType->isIntegerTy(Bitwidth: 64)) ||
1337 (PointerElementType->isFloatTy()) ||
1338 (PointerElementType->isDoubleTy()) ||
1339 (PointerElementType->isIntegerTy(Bitwidth: 32) &&
1340 llvm::any_of(Range: I->users(),
1341 P: [](const User *U) { return isa<SExtInst>(Val: U); }));
1342 };
1343
1344 // Check if a load/store has DQ form.
1345 auto isDQFormCandidate = [&](const Instruction *I, Value *PtrValue,
1346 const Type *PointerElementType) {
1347 assert((PtrValue && I) && "Invalid parameter!");
1348 // Check if it is a P10 lxvp/stxvp intrinsic.
1349 auto *II = dyn_cast<IntrinsicInst>(Val: I);
1350 if (II)
1351 return II->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp ||
1352 II->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp;
1353 // Check if it is a P9 vector load/store.
1354 return ST && ST->hasP9Vector() && (PointerElementType->isVectorTy());
1355 };
1356
1357 // Check if a load/store is candidate for chain commoning.
1358 // If the SCEV is only with one ptr operand in its start, we can use that
1359 // start as a chain separator. Mark this load/store as a candidate.
1360 auto isChainCommoningCandidate = [&](const Instruction *I, Value *PtrValue,
1361 const Type *PointerElementType) {
1362 const SCEVAddRecExpr *ARSCEV =
1363 cast<SCEVAddRecExpr>(Val: SE->getSCEVAtScope(V: PtrValue, L));
1364 if (!ARSCEV)
1365 return false;
1366
1367 if (!ARSCEV->isAffine())
1368 return false;
1369
1370 const SCEV *Start = ARSCEV->getStart();
1371
1372 // A single pointer. We can treat it as offset 0.
1373 if (isa<SCEVUnknown>(Val: Start) && Start->getType()->isPointerTy())
1374 return true;
1375
1376 const SCEVAddExpr *ASCEV = dyn_cast<SCEVAddExpr>(Val: Start);
1377
1378 // We need a SCEVAddExpr to include both base and offset.
1379 if (!ASCEV)
1380 return false;
1381
1382 // Make sure there is only one pointer operand(base) and all other operands
1383 // are integer type.
1384 bool SawPointer = false;
1385 for (const SCEV *Op : ASCEV->operands()) {
1386 if (Op->getType()->isPointerTy()) {
1387 if (SawPointer)
1388 return false;
1389 SawPointer = true;
1390 } else if (!Op->getType()->isIntegerTy())
1391 return false;
1392 }
1393
1394 return SawPointer;
1395 };
1396
1397 // Check if the diff is a constant type. This is used for update/DS/DQ form
1398 // preparation.
1399 auto isValidConstantDiff = [](const SCEV *Diff) {
1400 return dyn_cast<SCEVConstant>(Val: Diff) != nullptr;
1401 };
1402
1403 // Make sure the diff between the base and new candidate is required type.
1404 // This is used for chain commoning preparation.
1405 auto isValidChainCommoningDiff = [](const SCEV *Diff) {
1406 assert(Diff && "Invalid Diff!\n");
1407
1408 // Don't mess up previous dform prepare.
1409 if (isa<SCEVConstant>(Val: Diff))
1410 return false;
1411
1412 // A single integer type offset.
1413 if (isa<SCEVUnknown>(Val: Diff) && Diff->getType()->isIntegerTy())
1414 return true;
1415
1416 const SCEVNAryExpr *ADiff = dyn_cast<SCEVNAryExpr>(Val: Diff);
1417 if (!ADiff)
1418 return false;
1419
1420 for (const SCEV *Op : ADiff->operands())
1421 if (!Op->getType()->isIntegerTy())
1422 return false;
1423
1424 return true;
1425 };
1426
1427 HasCandidateForPrepare = false;
1428
1429 LLVM_DEBUG(dbgs() << "Start to prepare for update form.\n");
1430 // Collect buckets of comparable addresses used by loads and stores for update
1431 // form.
1432 SmallVector<Bucket, 16> UpdateFormBuckets = collectCandidates(
1433 L, isValidCandidate: isUpdateFormCandidate, isValidDiff: isValidConstantDiff, MaxCandidateNum: MaxVarsUpdateForm);
1434
1435 // Prepare for update form.
1436 if (!UpdateFormBuckets.empty())
1437 MadeChange |= updateFormPrep(L, Buckets&: UpdateFormBuckets);
1438 else if (!HasCandidateForPrepare) {
1439 LLVM_DEBUG(
1440 dbgs()
1441 << "No prepare candidates found, stop praparation for current loop!\n");
1442 // If no candidate for preparing, return early.
1443 return MadeChange;
1444 }
1445
1446 LLVM_DEBUG(dbgs() << "Start to prepare for DS form.\n");
1447 // Collect buckets of comparable addresses used by loads and stores for DS
1448 // form.
1449 SmallVector<Bucket, 16> DSFormBuckets = collectCandidates(
1450 L, isValidCandidate: isDSFormCandidate, isValidDiff: isValidConstantDiff, MaxCandidateNum: MaxVarsDSForm);
1451
1452 // Prepare for DS form.
1453 if (!DSFormBuckets.empty())
1454 MadeChange |= dispFormPrep(L, Buckets&: DSFormBuckets, Form: DSForm);
1455
1456 LLVM_DEBUG(dbgs() << "Start to prepare for DQ form.\n");
1457 // Collect buckets of comparable addresses used by loads and stores for DQ
1458 // form.
1459 SmallVector<Bucket, 16> DQFormBuckets = collectCandidates(
1460 L, isValidCandidate: isDQFormCandidate, isValidDiff: isValidConstantDiff, MaxCandidateNum: MaxVarsDQForm);
1461
1462 // Prepare for DQ form.
1463 if (!DQFormBuckets.empty())
1464 MadeChange |= dispFormPrep(L, Buckets&: DQFormBuckets, Form: DQForm);
1465
1466 // Collect buckets of comparable addresses used by loads and stores for chain
1467 // commoning. With chain commoning, we reuse offsets between the chains, so
1468 // the register pressure will be reduced.
1469 if (!EnableChainCommoning) {
1470 LLVM_DEBUG(dbgs() << "Chain commoning is not enabled.\n");
1471 return MadeChange;
1472 }
1473
1474 LLVM_DEBUG(dbgs() << "Start to prepare for chain commoning.\n");
1475 SmallVector<Bucket, 16> Buckets =
1476 collectCandidates(L, isValidCandidate: isChainCommoningCandidate, isValidDiff: isValidChainCommoningDiff,
1477 MaxCandidateNum: MaxVarsChainCommon);
1478
1479 // Prepare for chain commoning.
1480 if (!Buckets.empty())
1481 MadeChange |= chainCommoning(L, Buckets);
1482
1483 return MadeChange;
1484}
1485