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