44 #define DEBUG_TYPE "ppc-loop-instr-form-prep" 63 #include "llvm/IR/IntrinsicsPowerPC.h" 86 cl::desc(
"Potential common base number threshold per function for PPC loop " 91 cl::desc(
"prefer update form when ds form is also a update form"));
98 cl::desc(
"Potential PHI threshold per loop for PPC loop prep of update " 103 cl::desc(
"Potential PHI threshold per loop for PPC loop prep of DS form"));
107 cl::desc(
"Potential PHI threshold per loop for PPC loop prep of DQ form"));
116 cl::desc(
"Minimal common base load/store instructions triggering DS/DQ form " 119 STATISTIC(PHINodeAlreadyExistsUpdate,
"PHI node already in pre-increment form");
120 STATISTIC(PHINodeAlreadyExistsDS,
"PHI node already in DS form");
121 STATISTIC(PHINodeAlreadyExistsDQ,
"PHI node already in DQ form");
122 STATISTIC(DSFormChainRewritten,
"Num of DS form chain rewritten");
123 STATISTIC(DQFormChainRewritten,
"Num of DQ form chain rewritten");
124 STATISTIC(UpdFormChainRewritten,
"Num of update form chain rewritten");
127 struct BucketElement {
137 Elements(1, BucketElement(
I)) {}
139 const SCEV *BaseSCEV;
147 enum InstrForm { UpdateForm = 1, DSForm = 4, DQForm = 16 };
182 unsigned SuccPrepCount;
184 bool runOnLoop(
Loop *L);
188 const SCEV *BasePtrStartSCEV,
195 collectCandidates(
Loop *L,
198 unsigned MaxCandidateNum);
203 unsigned MaxCandidateNum);
219 bool prepareBaseForDispFormChain(Bucket &BucketChain,
227 bool prepareBaseForUpdateFormChain(Bucket &BucketChain);
231 bool rewriteLoadStores(
Loop *L, Bucket &BucketChain,
239 static const char *
name =
"Prepare loop for ppc preferred instruction forms";
251 return new PPCLoopInstrFormPrep(
TM);
255 Value *StrippedBasePtr = BasePtr;
256 while (
BitCastInst *BC = dyn_cast<BitCastInst>(StrippedBasePtr))
257 StrippedBasePtr = BC->getOperand(0);
259 return GEP->isInBounds();
265 assert(
I &&
"Invalid paramater!");
267 return (
I->getName() + Suffix).str();
273 if (
LoadInst *LMemI = dyn_cast<LoadInst>(MemI)) {
274 return LMemI->getPointerOperand();
275 }
else if (
StoreInst *SMemI = dyn_cast<StoreInst>(MemI)) {
276 return SMemI->getPointerOperand();
277 }
else if (
IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(MemI)) {
279 IMemI->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp)
280 return IMemI->getArgOperand(0);
281 if (IMemI->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp)
282 return IMemI->getArgOperand(1);
292 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
293 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
294 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
295 DT = DTWP ? &DTWP->getDomTree() :
nullptr;
296 PreserveLCSSA = mustPreserveAnalysisID(
LCSSAID);
297 ST =
TM ?
TM->getSubtargetImpl(
F) :
nullptr;
300 bool MadeChange =
false;
302 for (
auto I = LI->begin(),
IE = LI->end();
I !=
IE; ++
I)
304 MadeChange |= runOnLoop(*L);
309 void PPCLoopInstrFormPrep::addOneCandidate(
Instruction *MemI,
const SCEV *LSCEV,
311 unsigned MaxCandidateNum) {
313 "Candidate should be a memory instruction.");
314 assert(LSCEV &&
"Invalid SCEV for Ptr value.");
315 bool FoundBucket =
false;
316 for (
auto &
B : Buckets) {
317 const SCEV *Diff = SE->getMinusSCEV(LSCEV,
B.BaseSCEV);
318 if (
const auto *CDiff = dyn_cast<SCEVConstant>(Diff)) {
319 B.Elements.push_back(BucketElement(CDiff, MemI));
326 if (Buckets.size() == MaxCandidateNum)
328 Buckets.push_back(Bucket(LSCEV, MemI));
335 unsigned MaxCandidateNum) {
337 for (
const auto &BB : L->
blocks())
338 for (
auto &J : *BB) {
342 if (
LoadInst *LMemI = dyn_cast<LoadInst>(&J)) {
344 PtrValue = LMemI->getPointerOperand();
345 }
else if (
StoreInst *SMemI = dyn_cast<StoreInst>(&J)) {
347 PtrValue = SMemI->getPointerOperand();
348 }
else if (
IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(&J)) {
350 IMemI->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp) {
352 PtrValue = IMemI->getArgOperand(0);
353 }
else if (IMemI->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp) {
355 PtrValue = IMemI->getArgOperand(1);
366 const SCEV *LSCEV = SE->getSCEVAtScope(PtrValue, L);
368 if (!LARSCEV || LARSCEV->
getLoop() != L)
371 if (isValidCandidate(&J, PtrValue))
372 addOneCandidate(MemI, LSCEV, Buckets, MaxCandidateNum);
377 bool PPCLoopInstrFormPrep::prepareBaseForDispFormChain(Bucket &BucketChain,
387 for (
unsigned j = 0, je = BucketChain.Elements.size(); j != je; ++j) {
388 if (!BucketChain.Elements[j].Offset)
389 RemainderOffsetInfo[0] = std::make_pair(0, 1);
392 BucketChain.Elements[j].Offset->getAPInt().urem(
Form);
393 if (RemainderOffsetInfo.
find(Remainder) == RemainderOffsetInfo.
end())
394 RemainderOffsetInfo[Remainder] = std::make_pair(j, 1);
396 RemainderOffsetInfo[Remainder].second++;
414 unsigned MaxCountRemainder = 0;
416 if ((RemainderOffsetInfo.
find(j) != RemainderOffsetInfo.
end()) &&
417 RemainderOffsetInfo[j].second >
418 RemainderOffsetInfo[MaxCountRemainder].second)
419 MaxCountRemainder = j;
427 if (MaxCountRemainder == 0)
432 BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first].Offset;
433 BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV,
Offset);
434 for (
auto &
E : BucketChain.Elements) {
436 E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(
E.Offset,
Offset));
438 E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(
Offset));
441 std::swap(BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first],
442 BucketChain.Elements[0]);
452 bool PPCLoopInstrFormPrep::prepareBaseForUpdateFormChain(Bucket &BucketChain) {
462 for (
int j = 0, je = BucketChain.Elements.size(); j != je; ++j) {
463 if (
auto *II = dyn_cast<IntrinsicInst>(BucketChain.Elements[j].Instr))
473 if (!BucketChain.Elements[j].Offset ||
474 BucketChain.Elements[j].Offset->isZero())
477 const SCEV *
Offset = BucketChain.Elements[j].Offset;
478 BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV,
Offset);
479 for (
auto &
E : BucketChain.Elements) {
481 E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(
E.Offset,
Offset));
483 E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(
Offset));
486 std::swap(BucketChain.Elements[j], BucketChain.Elements[0]);
492 bool PPCLoopInstrFormPrep::rewriteLoadStores(
Loop *L, Bucket &BucketChain,
495 bool MadeChange =
false;
497 cast<SCEVAddRecExpr>(BucketChain.BaseSCEV);
501 LLVM_DEBUG(
dbgs() <<
"PIP: Transforming: " << *BasePtrSCEV <<
"\n");
503 assert(BasePtrSCEV->
getLoop() == L &&
"AddRec for the wrong loop?");
507 Instruction *MemI = BucketChain.Elements.begin()->Instr;
509 assert(BasePtr &&
"No pointer operand");
513 BasePtr->getType()->getPointerAddressSpace());
515 if (!SE->isLoopInvariant(BasePtrSCEV->
getStart(), L))
525 bool CanPreInc = (
Form == UpdateForm ||
528 const SCEV *BasePtrStartSCEV =
nullptr;
531 SE->getMinusSCEV(BasePtrSCEV->
getStart(), BasePtrIncSCEV);
533 BasePtrStartSCEV = BasePtrSCEV->
getStart();
538 if (alreadyPrepared(L, MemI, BasePtrStartSCEV, BasePtrIncSCEV,
Form))
541 LLVM_DEBUG(
dbgs() <<
"PIP: New start is: " << *BasePtrStartSCEV <<
"\n");
544 unsigned HeaderLoopPredCount =
pred_size(Header);
553 Value *BasePtrStart = SCEVE.expandCodeFor(BasePtrStartSCEV, I8PtrTy,
559 if (PI != LoopPredecessor)
562 NewPHI->
addIncoming(BasePtrStart, LoopPredecessor);
570 I8Ty, NewPHI, BasePtrIncSCEV->
getValue(),
574 if (PI == LoopPredecessor)
589 if (PI == LoopPredecessor)
597 I8Ty, NewPHI, BasePtrIncSCEV->
getValue(),
618 if (
Instruction *IDel = dyn_cast<Instruction>(BasePtr))
619 BBChanged.
insert(IDel->getParent());
620 BasePtr->replaceAllUsesWith(NewBasePtr);
626 NewPtrs.
insert(NewBasePtr);
628 for (
auto I = std::next(BucketChain.Elements.begin()),
629 IE = BucketChain.Elements.end();
I !=
IE; ++
I) {
631 assert(Ptr &&
"No pointer operand");
632 if (NewPtrs.
count(Ptr))
636 if (!
I->Offset ||
I->Offset->getValue()->isZero()) {
637 RealNewPtr = NewBasePtr;
640 if (PtrIP && isa<Instruction>(NewBasePtr) &&
643 else if (PtrIP && isa<PHINode>(PtrIP))
649 I8Ty, PtrInc,
I->Offset->getValue(),
657 if (
Instruction *IDel = dyn_cast<Instruction>(Ptr))
658 BBChanged.
insert(IDel->getParent());
666 ReplNewPtr = RealNewPtr;
671 NewPtrs.
insert(RealNewPtr);
678 if (
Form == DSForm && !CanPreInc)
679 DSFormChainRewritten++;
680 else if (
Form == DQForm)
681 DQFormChainRewritten++;
682 else if (
Form == UpdateForm || (
Form == DSForm && CanPreInc))
683 UpdFormChainRewritten++;
688 bool PPCLoopInstrFormPrep::updateFormPrep(
Loop *L,
690 bool MadeChange =
false;
694 for (
auto &Bucket : Buckets)
697 if (prepareBaseForUpdateFormChain(Bucket))
698 MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, UpdateForm);
701 for (
auto &BB : L->
blocks())
702 if (BBChanged.
count(BB))
709 bool MadeChange =
false;
715 for (
auto &Bucket : Buckets) {
718 if (prepareBaseForDispFormChain(Bucket,
Form))
719 MadeChange |= rewriteLoadStores(L, Bucket, BBChanged,
Form);
723 for (
auto &BB : L->
blocks())
724 if (BBChanged.
count(BB))
734 const SCEV *BasePtrStartSCEV,
744 if (!PredBB || !LatchBB)
749 for (
auto & CurrentPHI : PHIIter) {
750 PHINode *CurrentPHINode = dyn_cast<PHINode>(&CurrentPHI);
754 if (!SE->isSCEVable(CurrentPHINode->
getType()))
757 const SCEV *PHISCEV = SE->getSCEVAtScope(CurrentPHINode, L);
759 const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast<SCEVAddRecExpr>(PHISCEV);
765 if (!PHIBasePtrIncSCEV)
773 if (PHIBasePtrIncSCEV == BasePtrIncSCEV) {
776 if (
Form == UpdateForm &&
777 PHIBasePtrSCEV->
getStart() == BasePtrStartSCEV) {
778 ++PHINodeAlreadyExistsUpdate;
781 if (
Form == DSForm ||
Form == DQForm) {
783 SE->getMinusSCEV(PHIBasePtrSCEV->
getStart(), BasePtrStartSCEV));
786 ++PHINodeAlreadyExistsDS;
788 ++PHINodeAlreadyExistsDQ;
799 bool PPCLoopInstrFormPrep::runOnLoop(
Loop *L) {
800 bool MadeChange =
false;
816 if (!LoopPredecessor ||
822 if (!LoopPredecessor) {
823 LLVM_DEBUG(
dbgs() <<
"PIP fails since no predecessor for current loop.\n");
829 const Value *PtrValue) {
830 assert((PtrValue &&
I) &&
"Invalid parameter!");
832 if (
ST &&
ST->hasAltivec() &&
836 auto *II = dyn_cast<IntrinsicInst>(
I);
837 if (II && ((II->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp) ||
838 II->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp))
846 const SCEV *LSCEV = SE->getSCEVAtScope(const_cast<Value *>(PtrValue), L);
848 if (!LARSCEV || LARSCEV->
getLoop() != L)
852 const APInt &ConstInt = StepConst->getValue()->getValue();
862 assert((PtrValue &&
I) &&
"Invalid parameter!");
863 if (isa<IntrinsicInst>(
I))
871 [](
const User *U) {
return isa<SExtInst>(U); }));
876 assert((PtrValue &&
I) &&
"Invalid parameter!");
878 auto *II = dyn_cast<IntrinsicInst>(
I);
880 return II->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp ||
881 II->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp;
883 return ST &&
ST->hasP9Vector() &&
892 if (!UpdateFormBuckets.
empty())
893 MadeChange |= updateFormPrep(L, UpdateFormBuckets);
901 if (!DSFormBuckets.
empty())
902 MadeChange |= dispFormPrep(L, DSFormBuckets, DSForm);
910 if (!DQFormBuckets.
empty())
911 MadeChange |= dispFormPrep(L, DQFormBuckets, DQForm);
void initializePPCLoopInstrFormPrepPass(PassRegistry &)
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
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.
This class represents lattice values for constants.
LLVM_NODISCARD bool empty() const
The main scalar evolution driver.
STATISTIC(NumFunctions, "Total number of functions")
std::enable_if_t<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > cast(const Y &Val)
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
An instruction for reading from memory.
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...
bool isVectorTy() const
True if this is an instance of VectorType.
AnalysisUsage & addRequired()
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Type * getPointerElementType() const
const Loop * getLoop() const
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
void setIsInBounds(bool b=true)
Set or clear the inbounds flag on this GEP instruction.
bool isIntegerTy() const
True if this is an instance of IntegerType.
const APInt & getAPInt() const
BlockT * getHeader() const
ConstantInt * getValue() const
Type * getType() const
All values are typed, get the type of this value.
This node represents a polynomial recurrence on the trip count of the specified loop.
This class represents a no-op cast from one type to another.
An instruction for storing to memory.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
iterator find(const_arg_type_t< KeyT > Val)
bool isVoidTy() const
Return true if this is 'void'.
bool isFloatTy() const
Return true if this is 'float', a 32-bit IEEE fp type.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
LLVM Basic Block Representation.
The instances of the Type class are immutable: once they are created, they are never changed.
df_iterator< T > df_end(const T &G)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Represent the analysis usage information of a pass.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
FunctionPass class - This class is used to implement most global optimizations.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
const SCEV * getStart() const
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Common code between 32-bit and 64-bit PowerPC targets.
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Module.h This file contains the declarations for the Module class.
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
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.
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...
pred_range predecessors(BasicBlock *BB)
unsigned getNumIncomingValues() const
Return the number of incoming edges.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
df_iterator< T > df_begin(const T &G)
A range adaptor for a pair of iterators.
FunctionPass * createPPCLoopInstrFormPrepPass(PPCTargetMachine &TM)
Class for arbitrary precision integers.
This class uses information about analyze scalars to rewrite expressions in canonical form.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This class represents an analyzed expression in the program.
Represents a single loop in the control flow graph.
APInt srem(const APInt &RHS) const
Function for signed remainder operation.
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
unsigned pred_size(const BasicBlock *BB)
Get the number of predecessors of BB.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
bool isSignedIntN(unsigned N) const
Check if this APInt has an N-bits signed integer value.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
static const Function * getParent(const Value *V)
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...
The legacy pass manager's analysis pass to compute loop information.
print Print MemDeps of function
StringRef - Represent a constant reference to a string, i.e.
Legacy analysis pass which computes a DominatorTree.
bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE)
Return true if the given expression is safe to expand in the sense that all materialized values are s...
iterator_range< block_iterator > blocks() const
bool isDoubleTy() const
Return true if this is 'double', a 64-bit IEEE fp type.
static IntegerType * getInt8Ty(LLVMContext &C)
A wrapper class for inspecting calls to intrinsic functions.
const BasicBlock * getParent() const
This class represents a constant integer value.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.