95#include "llvm/IR/IntrinsicsPowerPC.h"
115#define DEBUG_TYPE "ppc-loop-instr-form-prep"
121 cl::desc(
"Potential common base number threshold per function "
122 "for PPC loop prep"));
126 cl::desc(
"prefer update form when ds form is also a update form"));
130 cl::desc(
"prepare update form when the load/store increment is a loop "
131 "invariant non-const value."));
135 cl::desc(
"Enable chain commoning in PPC loop prepare pass."));
142 cl::desc(
"Potential PHI threshold per loop for PPC loop prep of update "
147 cl::desc(
"Potential PHI threshold per loop for PPC loop prep of DS form"));
151 cl::desc(
"Potential PHI threshold per loop for PPC loop prep of DQ form"));
162 cl::desc(
"Bucket number per loop for PPC loop chain common"));
170 cl::desc(
"Minimal common base load/store instructions triggering DS/DQ form "
175 cl::desc(
"Minimal common base load/store instructions triggering chain "
176 "commoning preparation. Must be not smaller than 4"));
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");
187 struct BucketElement {
197 : BaseSCEV(
B),
Elements(1, BucketElement(
I)) {
202 const SCEV *BaseSCEV;
220 enum PrepForm { UpdateForm = 1, DSForm = 4, DQForm = 16, ChainCommoning };
250 bool HasCandidateForPrepare;
256 unsigned SuccPrepCount;
258 bool runOnLoop(
Loop *L);
262 const SCEV *BasePtrStartSCEV,
263 const SCEV *BasePtrIncSCEV, PrepForm
Form);
267 const SCEV *BasePtrIncSCEV);
273 bool prepareBasesForCommoningChains(Bucket &BucketChain);
277 rewriteLoadStoresForCommoningChains(
Loop *L, Bucket &Bucket,
286 std::function<
bool(
const SCEV *)> isValidDiff,
287 unsigned MaxCandidateNum);
293 std::function<
bool(
const SCEV *)> isValidDiff,
294 unsigned MaxCandidateNum);
309 bool prepareBaseForDispFormChain(Bucket &BucketChain, PrepForm
Form);
316 bool prepareBaseForUpdateFormChain(Bucket &BucketChain);
320 bool rewriteLoadStores(
Loop *L, Bucket &BucketChain,
325 std::pair<Instruction *, Instruction *>
333 rewriteForBucketElement(std::pair<Instruction *, Instruction *>
Base,
334 const BucketElement &Element,
Value *OffToBase,
340char PPCLoopInstrFormPrep::ID = 0;
341static const char *
name =
"Prepare loop for ppc preferred instruction forms";
353 return new PPCLoopInstrFormPrep(
TM);
357 Value *StrippedBasePtr = BasePtr;
358 while (
BitCastInst *BC = dyn_cast<BitCastInst>(StrippedBasePtr))
359 StrippedBasePtr = BC->getOperand(0);
361 return GEP->isInBounds();
367 assert(
I &&
"Invalid paramater!");
369 return (
I->getName() + Suffix).str();
375 Type **PtrElementType =
nullptr) {
377 Value *PtrValue =
nullptr;
378 Type *PointerElementType =
nullptr;
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)) {
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);
397 *PtrElementType = PointerElementType;
402bool PPCLoopInstrFormPrep::runOnFunction(
Function &
F) {
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;
414 bool MadeChange =
false;
418 MadeChange |= runOnLoop(L);
429bool PPCLoopInstrFormPrep::prepareBasesForCommoningChains(Bucket &CBucket) {
446 "Thredhold can not be smaller than 4!\n");
452 const SCEV *FirstOffset = CBucket.Elements[1].Offset;
457 unsigned FirstOffsetReusedCount = 1;
461 unsigned FirstOffsetReusedCountInFirstChain = 1;
463 unsigned EleNum = CBucket.Elements.size();
464 bool SawChainSeparater =
false;
465 for (
unsigned j = 2;
j != EleNum; ++
j) {
467 CBucket.Elements[j - 1].Offset) == FirstOffset) {
468 if (!SawChainSeparater)
469 FirstOffsetReusedCountInFirstChain++;
470 FirstOffsetReusedCount++;
488 SawChainSeparater =
true;
492 if (FirstOffsetReusedCount == 1)
496 FirstOffsetReusedCount / FirstOffsetReusedCountInFirstChain;
500 if (!SawChainSeparater)
501 ChainNum = (
unsigned)sqrt((
double)EleNum);
503 CBucket.ChainSize = (
unsigned)(EleNum / ChainNum);
507 if (CBucket.ChainSize * ChainNum != EleNum)
510 if (SawChainSeparater) {
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))
520 for (
unsigned i = 0; i < ChainNum; i++)
521 CBucket.ChainBases.push_back(CBucket.Elements[i * CBucket.ChainSize]);
528bool PPCLoopInstrFormPrep::chainCommoning(
Loop *L,
530 bool MadeChange =
false;
537 for (
auto &Bucket : Buckets) {
538 if (prepareBasesForCommoningChains(Bucket))
539 MadeChange |= rewriteLoadStoresForCommoningChains(L, Bucket, BBChanged);
543 for (
auto *BB : BBChanged)
548bool PPCLoopInstrFormPrep::rewriteLoadStoresForCommoningChains(
550 bool MadeChange =
false;
552 assert(Bucket.Elements.size() ==
553 Bucket.ChainBases.size() * Bucket.ChainSize &&
554 "invalid bucket for chain commoning!\n");
558 BasicBlock *LoopPredecessor =
L->getLoopPredecessor();
561 "loopprepare-chaincommon");
563 for (
unsigned ChainIdx = 0; ChainIdx < Bucket.ChainBases.size(); ++ChainIdx) {
564 unsigned BaseElemIdx = Bucket.ChainSize * ChainIdx;
565 const SCEV *BaseSCEV =
567 Bucket.Elements[BaseElemIdx].Offset)
569 const SCEVAddRecExpr *BasePtrSCEV = cast<SCEVAddRecExpr>(BaseSCEV);
572 if (!SCEVE.isSafeToExpand(BasePtrSCEV->
getStart()))
576 "Invalid SCEV type for the base ptr for a candidate chain!\n");
578 std::pair<Instruction *, Instruction *>
Base = rewriteForBase(
579 L, BasePtrSCEV, Bucket.Elements[BaseElemIdx].Instr,
580 false , ChainCommoning, SCEVE, DeletedPtrs);
590 for (
unsigned Idx = BaseElemIdx + 1;
Idx < BaseElemIdx + Bucket.ChainSize;
592 BucketElement &
I = Bucket.Elements[
Idx];
598 const SCEV *OffsetSCEV =
600 Bucket.Elements[BaseElemIdx].Offset)
601 : Bucket.Elements[
Idx].Offset;
606 if (!SCEVE.isSafeToExpand(OffsetSCEV))
609 Value *OffsetValue = SCEVE.expandCodeFor(
613 OffsetValue, DeletedPtrs);
615 assert(NewPtr &&
"Wrong rewrite!\n");
619 ++ChainCommoningRewritten;
626 for (
auto *
Ptr : DeletedPtrs) {
628 BBChanged.
insert(IDel->getParent());
648std::pair<Instruction *, Instruction *>
654 LLVM_DEBUG(
dbgs() <<
"PIP: Transforming: " << *BasePtrSCEV <<
"\n");
656 assert(BasePtrSCEV->
getLoop() == L &&
"AddRec for the wrong loop?");
659 assert(BasePtr &&
"No pointer operand");
663 PointerType::get(BaseMemI->
getParent()->getContext(),
664 BasePtr->getType()->getPointerAddressSpace());
666 bool IsConstantInc =
false;
668 Value *IncNode = getNodeForInc(L, BaseMemI, BasePtrIncSCEV);
671 dyn_cast<SCEVConstant>(BasePtrIncSCEV);
672 if (BasePtrIncConstantSCEV)
673 IsConstantInc =
true;
677 LLVM_DEBUG(
dbgs() <<
"Loop Increasement can not be represented!\n");
678 return std::make_pair(
nullptr,
nullptr);
684 <<
"Update form prepare for non-const increment is not enabled!\n");
685 return std::make_pair(
nullptr,
nullptr);
688 const SCEV *BasePtrStartSCEV =
nullptr;
691 "Increment is not loop invariant!\n");
693 IsConstantInc ? BasePtrIncConstantSCEV
696 BasePtrStartSCEV = BasePtrSCEV->
getStart();
698 if (alreadyPrepared(L, BaseMemI, BasePtrStartSCEV, BasePtrIncSCEV,
Form)) {
700 return std::make_pair(
nullptr,
nullptr);
703 LLVM_DEBUG(
dbgs() <<
"PIP: New start is: " << *BasePtrStartSCEV <<
"\n");
706 unsigned HeaderLoopPredCount =
pred_size(Header);
707 BasicBlock *LoopPredecessor =
L->getLoopPredecessor();
719 if (PI != LoopPredecessor)
722 NewPHI->
addIncoming(BasePtrStart, LoopPredecessor);
732 cast<GetElementPtrInst>(PtrInc)->setIsInBounds(
IsPtrInBounds(BasePtr));
734 if (PI == LoopPredecessor)
749 if (PI == LoopPredecessor)
759 cast<GetElementPtrInst>(PtrInc)->setIsInBounds(
IsPtrInBounds(BasePtr));
767 Header->getFirstInsertionPt());
772 BasePtr->replaceAllUsesWith(NewBasePtr);
774 DeletedPtrs.
insert(BasePtr);
776 return std::make_pair(NewBasePtr, PtrInc);
779Instruction *PPCLoopInstrFormPrep::rewriteForBucketElement(
780 std::pair<Instruction *, Instruction *>
Base,
const BucketElement &Element,
784 assert((NewBasePtr && PtrInc) &&
"base does not exist!\n");
792 if (!Element.Offset ||
793 (isa<SCEVConstant>(Element.Offset) &&
794 cast<SCEVConstant>(Element.Offset)->getValue()->isZero())) {
795 RealNewPtr = NewBasePtr;
797 std::optional<BasicBlock::iterator> PtrIP = std::nullopt;
799 PtrIP =
I->getIterator();
801 if (PtrIP && isa<Instruction>(NewBasePtr) &&
803 PtrIP = std::nullopt;
804 else if (PtrIP && isa<PHINode>(*PtrIP))
805 PtrIP = (*PtrIP)->getParent()->getFirstInsertionPt();
807 PtrIP = Element.Instr->getIterator();
809 assert(OffToBase &&
"There should be an offset for non base element!\n");
811 I8Ty, PtrInc, OffToBase,
822 if (
Ptr->getType() != RealNewPtr->
getType()) {
827 ReplNewPtr = RealNewPtr;
829 Ptr->replaceAllUsesWith(ReplNewPtr);
835void PPCLoopInstrFormPrep::addOneCandidate(
837 std::function<
bool(
const SCEV *)> isValidDiff,
unsigned MaxCandidateNum) {
839 "Candidate should be a memory instruction.");
840 assert(LSCEV &&
"Invalid SCEV for Ptr value.");
842 bool FoundBucket =
false;
843 for (
auto &
B : Buckets) {
844 if (cast<SCEVAddRecExpr>(
B.BaseSCEV)->getStepRecurrence(*SE) !=
845 cast<SCEVAddRecExpr>(LSCEV)->getStepRecurrence(*SE))
848 if (isValidDiff(Diff)) {
849 B.Elements.push_back(BucketElement(Diff, MemI));
856 if (Buckets.size() == MaxCandidateNum) {
857 LLVM_DEBUG(
dbgs() <<
"Can not prepare more chains, reach maximum limit "
858 << MaxCandidateNum <<
"\n");
861 Buckets.push_back(Bucket(LSCEV, MemI));
869 std::function<
bool(
const SCEV *)> isValidDiff,
unsigned MaxCandidateNum) {
872 for (
const auto &BB :
L->blocks())
873 for (
auto &J : *BB) {
874 Value *PtrValue =
nullptr;
875 Type *PointerElementType =
nullptr;
884 if (
L->isLoopInvariant(PtrValue))
889 if (!LARSCEV || LARSCEV->
getLoop() != L)
893 HasCandidateForPrepare =
true;
895 if (isValidCandidate(&J, PtrValue, PointerElementType))
896 addOneCandidate(&J, LSCEV, Buckets, isValidDiff, MaxCandidateNum);
901bool PPCLoopInstrFormPrep::prepareBaseForDispFormChain(Bucket &BucketChain,
911 for (
unsigned j = 0, je = BucketChain.Elements.size(); j != je; ++j) {
912 if (!BucketChain.Elements[j].Offset)
913 RemainderOffsetInfo[0] = std::make_pair(0, 1);
915 unsigned Remainder = cast<SCEVConstant>(BucketChain.Elements[j].Offset)
918 if (!RemainderOffsetInfo.
contains(Remainder))
919 RemainderOffsetInfo[Remainder] = std::make_pair(j, 1);
921 RemainderOffsetInfo[Remainder].second++;
939 unsigned MaxCountRemainder = 0;
941 if ((RemainderOffsetInfo.
contains(j)) &&
942 RemainderOffsetInfo[
j].second >
943 RemainderOffsetInfo[MaxCountRemainder].second)
944 MaxCountRemainder = j;
952 if (MaxCountRemainder == 0)
957 BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first].Offset;
959 for (
auto &E : BucketChain.Elements) {
966 std::swap(BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first],
967 BucketChain.Elements[0]);
977bool PPCLoopInstrFormPrep::prepareBaseForUpdateFormChain(Bucket &BucketChain) {
987 for (
int j = 0, je = BucketChain.Elements.size(); j != je; ++j) {
988 if (
auto *
II = dyn_cast<IntrinsicInst>(BucketChain.Elements[j].Instr))
989 if (
II->getIntrinsicID() == Intrinsic::prefetch)
998 if (!BucketChain.Elements[j].Offset ||
999 cast<SCEVConstant>(BucketChain.Elements[j].Offset)->isZero())
1002 const SCEV *
Offset = BucketChain.Elements[
j].Offset;
1004 for (
auto &E : BucketChain.Elements) {
1011 std::swap(BucketChain.Elements[j], BucketChain.Elements[0]);
1017bool PPCLoopInstrFormPrep::rewriteLoadStores(
1020 bool MadeChange =
false;
1023 cast<SCEVAddRecExpr>(BucketChain.BaseSCEV);
1029 "loopprepare-formrewrite");
1038 bool CanPreInc = (
Form == UpdateForm ||
1039 ((
Form == DSForm) &&
1046 std::pair<Instruction *, Instruction *>
Base =
1047 rewriteForBase(L, BasePtrSCEV, BucketChain.Elements.begin()->Instr,
1048 CanPreInc,
Form, SCEVE, DeletedPtrs);
1066 BE.Offset ? cast<SCEVConstant>(BE.Offset)->getValue() :
nullptr,
1068 assert(NewPtr &&
"wrong rewrite!\n");
1076 for (
auto *
Ptr : DeletedPtrs) {
1078 BBChanged.
insert(IDel->getParent());
1086 if (
Form == DSForm && !CanPreInc)
1087 DSFormChainRewritten++;
1088 else if (
Form == DQForm)
1089 DQFormChainRewritten++;
1090 else if (
Form == UpdateForm || (
Form == DSForm && CanPreInc))
1091 UpdFormChainRewritten++;
1096bool PPCLoopInstrFormPrep::updateFormPrep(
Loop *L,
1098 bool MadeChange =
false;
1099 if (Buckets.
empty())
1102 for (
auto &Bucket : Buckets)
1105 if (prepareBaseForUpdateFormChain(Bucket))
1106 MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, UpdateForm);
1109 for (
auto *BB : BBChanged)
1114bool PPCLoopInstrFormPrep::dispFormPrep(
Loop *L,
1117 bool MadeChange =
false;
1119 if (Buckets.
empty())
1123 for (
auto &Bucket : Buckets) {
1126 if (prepareBaseForDispFormChain(Bucket,
Form))
1127 MadeChange |= rewriteLoadStores(L, Bucket, BBChanged,
Form);
1131 for (
auto *BB : BBChanged)
1145 const SCEV *BasePtrIncSCEV) {
1148 if (isa<SCEVConstant>(BasePtrIncSCEV))
1149 return cast<SCEVConstant>(BasePtrIncSCEV)->getValue();
1166 for (
auto &CurrentPHI : PHIIter) {
1167 PHINode *CurrentPHINode = dyn_cast<PHINode>(&CurrentPHI);
1168 if (!CurrentPHINode)
1176 const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast<SCEVAddRecExpr>(PHISCEV);
1177 if (!PHIBasePtrSCEV)
1182 if (!PHIBasePtrIncSCEV || (PHIBasePtrIncSCEV != BasePtrIncSCEV))
1191 Value *StrippedBaseI =
I;
1192 while (
BitCastInst *BC = dyn_cast<BitCastInst>(StrippedBaseI))
1193 StrippedBaseI = BC->getOperand(0);
1195 Instruction *StrippedI = dyn_cast<Instruction>(StrippedBaseI);
1201 if (StrippedI->
getOpcode() == Instruction::Add ||
1202 (StrippedI->
getOpcode() == Instruction::GetElementPtr &&
1219 const SCEV *BasePtrStartSCEV,
1220 const SCEV *BasePtrIncSCEV,
1229 if (!PredBB || !LatchBB)
1234 for (
auto & CurrentPHI : PHIIter) {
1235 PHINode *CurrentPHINode = dyn_cast<PHINode>(&CurrentPHI);
1236 if (!CurrentPHINode)
1244 const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast<SCEVAddRecExpr>(PHISCEV);
1245 if (!PHIBasePtrSCEV)
1250 if (!PHIBasePtrIncSCEV)
1258 if (PHIBasePtrIncSCEV == BasePtrIncSCEV) {
1261 if ((
Form == UpdateForm ||
Form == ChainCommoning ) &&
1262 PHIBasePtrSCEV->
getStart() == BasePtrStartSCEV) {
1263 ++PHINodeAlreadyExistsUpdate;
1266 if (
Form == DSForm ||
Form == DQForm) {
1271 ++PHINodeAlreadyExistsDS;
1273 ++PHINodeAlreadyExistsDQ;
1284bool PPCLoopInstrFormPrep::runOnLoop(
Loop *L) {
1285 bool MadeChange =
false;
1288 if (!
L->isInnermost())
1297 BasicBlock *LoopPredecessor =
L->getLoopPredecessor();
1301 if (!LoopPredecessor ||
1304 if (LoopPredecessor)
1307 if (!LoopPredecessor) {
1308 LLVM_DEBUG(
dbgs() <<
"PIP fails since no predecessor for current loop.\n");
1314 const Type *PointerElementType) {
1315 assert((PtrValue &&
I) &&
"Invalid parameter!");
1317 if (ST &&
ST->hasAltivec() && PointerElementType->
isVectorTy())
1320 auto *
II = dyn_cast<IntrinsicInst>(
I);
1321 if (
II && ((
II->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp) ||
1322 II->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp))
1332 if (!LARSCEV || LARSCEV->
getLoop() != L)
1336 const APInt &ConstInt = StepConst->getValue()->getValue();
1346 const Type *PointerElementType) {
1347 assert((PtrValue &&
I) &&
"Invalid parameter!");
1348 if (isa<IntrinsicInst>(
I))
1355 [](
const User *U) { return isa<SExtInst>(U); }));
1360 const Type *PointerElementType) {
1361 assert((PtrValue &&
I) &&
"Invalid parameter!");
1363 auto *
II = dyn_cast<IntrinsicInst>(
I);
1365 return II->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp ||
1366 II->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp;
1368 return ST &&
ST->hasP9Vector() && (PointerElementType->
isVectorTy());
1375 const Type *PointerElementType) {
1387 if (isa<SCEVUnknown>(Start) && Start->getType()->isPointerTy())
1390 const SCEVAddExpr *ASCEV = dyn_cast<SCEVAddExpr>(Start);
1398 bool SawPointer =
false;
1400 if (
Op->getType()->isPointerTy()) {
1404 }
else if (!
Op->getType()->isIntegerTy())
1413 auto isValidConstantDiff = [](
const SCEV *Diff) {
1414 return dyn_cast<SCEVConstant>(Diff) !=
nullptr;
1419 auto isValidChainCommoningDiff = [](
const SCEV *Diff) {
1420 assert(Diff &&
"Invalid Diff!\n");
1423 if (isa<SCEVConstant>(Diff))
1430 const SCEVNAryExpr *ADiff = dyn_cast<SCEVNAryExpr>(Diff);
1435 if (!
Op->getType()->isIntegerTy())
1441 HasCandidateForPrepare =
false;
1450 if (!UpdateFormBuckets.
empty())
1451 MadeChange |= updateFormPrep(L, UpdateFormBuckets);
1452 else if (!HasCandidateForPrepare) {
1455 <<
"No prepare candidates found, stop praparation for current loop!\n");
1467 if (!DSFormBuckets.
empty())
1468 MadeChange |= dispFormPrep(L, DSFormBuckets, DSForm);
1477 if (!DQFormBuckets.
empty())
1478 MadeChange |= dispFormPrep(L, DQFormBuckets, DQForm);
1490 collectCandidates(L, isChainCommoningCandidate, isValidChainCommoningDiff,
1494 if (!Buckets.
empty())
1495 MadeChange |= chainCommoning(L, Buckets);
static const Function * getParent(const Value *V)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-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
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Module.h This file contains the declarations for the Module class.
uint64_t IntrinsicInst * II
const char LLVMTargetMachineRef TM
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
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)
Class for arbitrary precision integers.
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
bool isSignedIntN(unsigned N) const
Check if this APInt has an N-bits signed integer value.
APInt srem(const APInt &RHS) const
Function for signed remainder operation.
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.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
InstListType::iterator iterator
Instruction iterators...
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...
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.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
FunctionPass class - This class is used to implement most global optimizations.
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
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
void setIsInBounds(bool b=true)
Set or clear the inbounds flag on this GEP instruction.
Module * getParent()
Get the module that this global value is contained inside of...
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
A wrapper class for inspecting calls to intrinsic functions.
An instruction for reading from memory.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
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.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
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...
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 * getStart() const
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.
const Loop * getLoop() const
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.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
StringRef - Represent a constant reference to a string, i.e.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isVectorTy() const
True if this is an instance of VectorType.
bool isFloatTy() const
Return true if this is 'float', a 32-bit IEEE fp type.
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.
bool isIntegerTy() const
True if this is an instance of IntegerType.
bool isVoidTy() const
Return true if this is 'void'.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVMContext & getContext() const
All values hold a context through their type.
const ParentTy * getParent() const
self_iterator getIterator()
A range adaptor for a pair of iterators.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
initializer< Ty > init(const Ty &Val)
NodeAddr< InstrNode * > Instr
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
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.
FunctionPass * createPPCLoopInstrFormPrepPass(PPCTargetMachine &TM)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
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.
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
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.