Index: llvm/lib/Target/PowerPC/CMakeLists.txt =================================================================== --- llvm/lib/Target/PowerPC/CMakeLists.txt +++ llvm/lib/Target/PowerPC/CMakeLists.txt @@ -29,7 +29,7 @@ PPCEarlyReturn.cpp PPCFastISel.cpp PPCFrameLowering.cpp - PPCLoopPreIncPrep.cpp + PPCLoopInstrFormPrep.cpp PPCMCInstLower.cpp PPCMachineFunctionInfo.cpp PPCMachineScheduler.cpp Index: llvm/lib/Target/PowerPC/PPCLoopInstrFormPrep.cpp =================================================================== --- /dev/null +++ llvm/lib/Target/PowerPC/PPCLoopInstrFormPrep.cpp @@ -0,0 +1,890 @@ +//===------ PPCLoopPreIncPrep.cpp - Loop Pre-Inc. AM Prep. Pass -----------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file implements a pass to prepare loops for ppc preferred addressing +// modes, leveraging different instruction form. (eg: DS/DQ form, D/DS form with +// update) +// Additional PHIs are created for loop induction variables used by load/store +// instructions so that preferred addressing modes can be used. +// +// 1: DS/DQ form preparation, prepare the load/store instructions so that they +// can satisfy the DS/DQ form displacement requirements. +// Generically, this means transforming loops like this: +// for (int i = 0; i < n; ++i) { +// unsigned long x1 = *(unsigned long *)(p + i + 5); +// unsigned long x2 = *(unsigned long *)(p + i + 9); +// } +// +// to look like this: +// +// unsigned NewP = p + 5; +// for (int i = 0; i < n; ++i) { +// unsigned long x1 = *(unsigned long *)(i + NewP); +// unsigned long x2 = *(unsigned long *)(i + NewP + 4); +// } +// +// 2: D/DS form with update preparation, prepare the load/store instructions so +// that we can use update form to do pre-increment. +// Generically, this means transforming loops like this: +// for (int i = 0; i < n; ++i) +// array[i] = c; +// +// to look like this: +// +// T *p = array[-1]; +// for (int i = 0; i < n; ++i) +// *++p = c; +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "ppc-loop-preinc-prep" + +#include "PPC.h" +#include "PPCSubtarget.h" +#include "PPCTargetMachine.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionExpander.h" +#include "llvm/Analysis/ScalarEvolutionExpressions.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Instruction.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/Type.h" +#include "llvm/IR/Value.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/Local.h" +#include "llvm/Transforms/Utils/LoopUtils.h" +#include +#include +#include + +using namespace llvm; + +// By default, we limit this to creating 16 common bases out of loops per +// function. 16 is a little over half of the allocatable register set. +static cl::opt MaxVarsPrep("ppc-formprep-max-vars", + cl::Hidden, cl::init(16), + cl::desc("Potential common base number threshold per function for PPC loop " + "prep")); + +static cl::opt PreferUpdateForm("ppc-formprep-prefer-update", + cl::init(true), cl::Hidden, + cl::desc("prefer update form when ds form is also a update form")); + +// Sum of following 3 per loop thresholds for all loops can not be larger +// than MaxVarsPrep. +// By default, we limit this to creating 9 PHIs for one loop. +// 9 and 3 for each kind prep are exterimental values on Power9. +static cl::opt 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 cl::opt 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 cl::opt MaxVarsDQForm("ppc-dqprep-max-vars", + cl::Hidden, cl::init(3), + cl::desc("Potential PHI threshold per loop for PPC loop prep of DQ form")); + + +// If would not be profitable if the common base has only one load/store, ISEL +// should already be able to choose best load/store form based on offset for +// single load/store. Set minimal profitable value default to 2 and make it as +// an option. +static cl::opt DispFormPrepMinThreshold("ppc-dispprep-min-threshold", + cl::Hidden, cl::init(2), + cl::desc("Minimal common base load/store instructions triggering DS/DQ form " + "preparation")); + +STATISTIC(PHINodeAlreadyExistsUpdate, "PHI node already in pre-increment form"); +STATISTIC(PHINodeAlreadyExistsDS, "PHI node already in DS form"); +STATISTIC(PHINodeAlreadyExistsDQ, "PHI node already in DQ form"); +STATISTIC(DSFormChainRewritten, "Num of DS form chain rewritten"); +STATISTIC(DQFormChainRewritten, "Num of DQ form chain rewritten"); +STATISTIC(UpdFormChainRewritten, "Num of update form chain rewritten"); + +namespace { + struct BucketElement { + BucketElement(const SCEVConstant *O, Instruction *I) : Offset(O), Instr(I) {} + BucketElement(Instruction *I) : Offset(nullptr), Instr(I) {} + + const SCEVConstant *Offset; + Instruction *Instr; + }; + + struct Bucket { + Bucket(const SCEV *B, Instruction *I) : BaseSCEV(B), + Elements(1, BucketElement(I)) {} + + const SCEV *BaseSCEV; + SmallVector Elements; + }; + + // "UpdateForm" is not a real PPC instruction form, it stands for dform + // load/store with update like ldu/stdu, or Prefetch intrinsic. + // For DS form instructions, their displacements must be multiple of 4. + // For DQ form instructions, their displacements must be multiple of 16. + enum InstrForm { UpdateForm = 1, DSForm = 4, DQForm = 16 }; + + class PPCLoopPreIncPrep : public FunctionPass { + public: + static char ID; // Pass ID, replacement for typeid + + PPCLoopPreIncPrep() : FunctionPass(ID) { + initializePPCLoopPreIncPrepPass(*PassRegistry::getPassRegistry()); + } + + PPCLoopPreIncPrep(PPCTargetMachine &TM) : FunctionPass(ID), TM(&TM) { + initializePPCLoopPreIncPrepPass(*PassRegistry::getPassRegistry()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); + } + + bool runOnFunction(Function &F) override; + + private: + PPCTargetMachine *TM = nullptr; + const PPCSubtarget *ST; + DominatorTree *DT; + LoopInfo *LI; + ScalarEvolution *SE; + bool PreserveLCSSA; + + /// Successful preparation number for Update/DS/DQ form in all inner most + /// loops. One successful preparation will put one common base out of loop, + /// this may leads to register presure like LICM does. + /// Make sure total preparation number can be controlled by option. + unsigned SuccPrepCount; + + bool runOnLoop(Loop *L); + + /// Check if required PHI node is already exist in Loop \p L. + bool alreadyPrepared(Loop *L, Instruction* MemI, + const SCEV *BasePtrStartSCEV, + const SCEVConstant *BasePtrIncSCEV, + InstrForm Form); + + /// Collect condition matched(\p isValidCandidate() returns true) + /// candidates in Loop \p L. + SmallVector + collectCandidates(Loop *L, + std::function + isValidCandidate, + unsigned MaxCandidateNum); + + /// Add a candidate to candidates \p Buckets. + void addOneCandidate(Instruction *MemI, const SCEV *LSCEV, + SmallVector &Buckets, + unsigned MaxCandidateNum); + + /// Prepare all candidates in \p Buckets for update form. + bool updateFormPrep(Loop *L, SmallVector &Buckets); + + /// Prepare all candidates in \p Buckets for displacement form, now for + /// ds/dq. + bool dispFormPrep(Loop *L, SmallVector &Buckets, + InstrForm Form); + + /// Prepare for one chain \p BucketChain, find the best base element and + /// update all other elements in \p BucketChain accordingly. + /// \p Form is used to find the best base element. + /// If success, best base element must be stored as the first element of + /// \p BucketChain. + /// Return false if no base element found, otherwise return true. + bool prepareBaseForDispFormChain(Bucket &BucketChain, + InstrForm Form); + + /// Prepare for one chain \p BucketChain, find the best base element and + /// update all other elements in \p BucketChain accordingly. + /// If success, best base element must be stored as the first element of + /// \p BucketChain. + /// Return false if no base element found, otherwise return true. + bool prepareBaseForUpdateFormChain(Bucket &BucketChain); + + /// Rewrite load/store instructions in \p BucketChain according to + /// preparation. + bool rewriteLoadStores(Loop *L, Bucket &BucketChain, + SmallSet &BBChanged, + InstrForm Form); + }; + +} // end anonymous namespace + +char PPCLoopPreIncPrep::ID = 0; +static const char *name = "Prepare loop for pre-inc. addressing modes"; +INITIALIZE_PASS_BEGIN(PPCLoopPreIncPrep, DEBUG_TYPE, name, false, false) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) +INITIALIZE_PASS_END(PPCLoopPreIncPrep, DEBUG_TYPE, name, false, false) + +static const std::string PHINodeNameSuffix = ".phi"; +static const std::string CastNodeNameSuffix = ".cast"; +static const std::string GEPNodeIncNameSuffix = ".inc"; +static const std::string GEPNodeOffNameSuffix = ".off"; + +FunctionPass *llvm::createPPCLoopPreIncPrepPass(PPCTargetMachine &TM) { + return new PPCLoopPreIncPrep(TM); +} + +static bool IsPtrInBounds(Value *BasePtr) { + Value *StrippedBasePtr = BasePtr; + while (BitCastInst *BC = dyn_cast(StrippedBasePtr)) + StrippedBasePtr = BC->getOperand(0); + if (GetElementPtrInst *GEP = dyn_cast(StrippedBasePtr)) + return GEP->isInBounds(); + + return false; +} + +static std::string getInstrName(const Value *I, const std::string Suffix) { + assert(I && "Invalid paramater!"); + if (I->hasName()) + return (I->getName() + Suffix).str(); + else + return ""; +} + +static Value *GetPointerOperand(Value *MemI) { + if (LoadInst *LMemI = dyn_cast(MemI)) { + return LMemI->getPointerOperand(); + } else if (StoreInst *SMemI = dyn_cast(MemI)) { + return SMemI->getPointerOperand(); + } else if (IntrinsicInst *IMemI = dyn_cast(MemI)) { + if (IMemI->getIntrinsicID() == Intrinsic::prefetch) + return IMemI->getArgOperand(0); + } + + return nullptr; +} + +bool PPCLoopPreIncPrep::runOnFunction(Function &F) { + if (skipFunction(F)) + return false; + + LI = &getAnalysis().getLoopInfo(); + SE = &getAnalysis().getSE(); + auto *DTWP = getAnalysisIfAvailable(); + DT = DTWP ? &DTWP->getDomTree() : nullptr; + PreserveLCSSA = mustPreserveAnalysisID(LCSSAID); + ST = TM ? TM->getSubtargetImpl(F) : nullptr; + SuccPrepCount = 0; + + bool MadeChange = false; + + for (auto I = LI->begin(), IE = LI->end(); I != IE; ++I) + for (auto L = df_begin(*I), LE = df_end(*I); L != LE; ++L) + MadeChange |= runOnLoop(*L); + + return MadeChange; +} + +void PPCLoopPreIncPrep::addOneCandidate(Instruction *MemI, const SCEV *LSCEV, + SmallVector &Buckets, + unsigned MaxCandidateNum) { + assert((MemI && GetPointerOperand(MemI)) && + "Candidate should be a memory instruction."); + assert(LSCEV && "Invalid SCEV for Ptr value."); + bool FoundBucket = false; + for (auto &B : Buckets) { + const SCEV *Diff = SE->getMinusSCEV(LSCEV, B.BaseSCEV); + if (const auto *CDiff = dyn_cast(Diff)) { + B.Elements.push_back(BucketElement(CDiff, MemI)); + FoundBucket = true; + break; + } + } + + if (!FoundBucket) { + if (Buckets.size() == MaxCandidateNum) + return; + Buckets.push_back(Bucket(LSCEV, MemI)); + } +} + +SmallVector PPCLoopPreIncPrep::collectCandidates( + Loop *L, + std::function isValidCandidate, + unsigned MaxCandidateNum) { + SmallVector Buckets; + for (const auto &BB : L->blocks()) + for (auto &J : *BB) { + Value *PtrValue; + Instruction *MemI; + + if (LoadInst *LMemI = dyn_cast(&J)) { + MemI = LMemI; + PtrValue = LMemI->getPointerOperand(); + } else if (StoreInst *SMemI = dyn_cast(&J)) { + MemI = SMemI; + PtrValue = SMemI->getPointerOperand(); + } else if (IntrinsicInst *IMemI = dyn_cast(&J)) { + if (IMemI->getIntrinsicID() == Intrinsic::prefetch) { + MemI = IMemI; + PtrValue = IMemI->getArgOperand(0); + } else continue; + } else continue; + + unsigned PtrAddrSpace = PtrValue->getType()->getPointerAddressSpace(); + if (PtrAddrSpace) + continue; + + if (L->isLoopInvariant(PtrValue)) + continue; + + const SCEV *LSCEV = SE->getSCEVAtScope(PtrValue, L); + const SCEVAddRecExpr *LARSCEV = dyn_cast(LSCEV); + if (!LARSCEV || LARSCEV->getLoop() != L) + continue; + + if (isValidCandidate(&J, PtrValue)) + addOneCandidate(MemI, LSCEV, Buckets, MaxCandidateNum); + } + return Buckets; +} + +bool PPCLoopPreIncPrep::prepareBaseForDispFormChain(Bucket &BucketChain, + InstrForm Form) { + // RemainderOffsetInfo details: + // key: value of (Offset urem DispConstraint). For DSForm, it can + // be [0, 4). + // first of pair: the index of first BucketElement whose remainder is equal + // to key. For key 0, this value must be 0. + // second of pair: number of load/stores with the same remainder. + DenseMap> RemainderOffsetInfo; + + for (unsigned j = 0, je = BucketChain.Elements.size(); j != je; ++j) { + if (!BucketChain.Elements[j].Offset) + RemainderOffsetInfo[0] = std::make_pair(0, 1); + else { + unsigned Remainder = + BucketChain.Elements[j].Offset->getAPInt().urem(Form); + if (RemainderOffsetInfo.find(Remainder) == RemainderOffsetInfo.end()) + RemainderOffsetInfo[Remainder] = std::make_pair(j, 1); + else + RemainderOffsetInfo[Remainder].second++; + } + } + // Currently we choose the most profitable base as the one which has the max + // number of load/store with same remainder. + // FIXME: adjust the base selection strategy according to load/store offset + // distribution. + // For example, if we have one candidate chain for DS form preparation, which + // contains following load/stores with different remainders: + // 1: 10 load/store whose remainder is 1; + // 2: 9 load/store whose remainder is 2; + // 3: 1 for remainder 3 and 0 for remainder 0; + // Now we will choose the first load/store whose remainder is 1 as base and + // adjust all other load/stores according to new base, so we will get 10 DS + // form and 10 X form. + // But we should be more clever, for this case we could use two bases, one for + // remainder 1 and the other for remainder 2, thus we could get 19 DS form and 1 + // X form. + unsigned MaxCountRemainder = 0; + for (unsigned j = 0; j < (unsigned)Form; j++) + if ((RemainderOffsetInfo.find(j) != RemainderOffsetInfo.end()) && + RemainderOffsetInfo[j].second > + RemainderOffsetInfo[MaxCountRemainder].second) + MaxCountRemainder = j; + + // Abort when there are too few insts with common base. + if (RemainderOffsetInfo[MaxCountRemainder].second < DispFormPrepMinThreshold) + return false; + + // If the first value is most profitable, no needed to adjust BucketChain + // elements as they are substracted the first value when collecting. + if (MaxCountRemainder == 0) + return true; + + // Adjust load/store to the new chosen base. + const SCEV *Offset = + BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first].Offset; + BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset); + for (auto &E : BucketChain.Elements) { + if (E.Offset) + E.Offset = cast(SE->getMinusSCEV(E.Offset, Offset)); + else + E.Offset = cast(SE->getNegativeSCEV(Offset)); + } + + std::swap(BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first], + BucketChain.Elements[0]); + return true; +} + +// FIXME: implement a more clever base choosing policy. +// Currently we always choose an exist load/store offset. This maybe lead to +// suboptimal code sequences. For example, for one DS chain with offsets +// {-32769, 2003, 2007, 2011}, we choose -32769 as base offset, and left disp +// for load/stores are {0, 34772, 34776, 34780}. Though each offset now is a +// multipler of 4, it cannot be represented by sint16. +bool PPCLoopPreIncPrep::prepareBaseForUpdateFormChain(Bucket &BucketChain) { + // We have a choice now of which instruction's memory operand we use as the + // base for the generated PHI. Always picking the first instruction in each + // bucket does not work well, specifically because that instruction might + // be a prefetch (and there are no pre-increment dcbt variants). Otherwise, + // the choice is somewhat arbitrary, because the backend will happily + // generate direct offsets from both the pre-incremented and + // post-incremented pointer values. Thus, we'll pick the first non-prefetch + // instruction in each bucket, and adjust the recurrence and other offsets + // accordingly. + for (int j = 0, je = BucketChain.Elements.size(); j != je; ++j) { + if (auto *II = dyn_cast(BucketChain.Elements[j].Instr)) + if (II->getIntrinsicID() == Intrinsic::prefetch) + continue; + + // If we'd otherwise pick the first element anyway, there's nothing to do. + if (j == 0) + break; + + // If our chosen element has no offset from the base pointer, there's + // nothing to do. + if (!BucketChain.Elements[j].Offset || + BucketChain.Elements[j].Offset->isZero()) + break; + + const SCEV *Offset = BucketChain.Elements[j].Offset; + BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset); + for (auto &E : BucketChain.Elements) { + if (E.Offset) + E.Offset = cast(SE->getMinusSCEV(E.Offset, Offset)); + else + E.Offset = cast(SE->getNegativeSCEV(Offset)); + } + + std::swap(BucketChain.Elements[j], BucketChain.Elements[0]); + break; + } + return true; +} + +bool PPCLoopPreIncPrep::rewriteLoadStores(Loop *L, Bucket &BucketChain, + SmallSet &BBChanged, + InstrForm Form) { + bool MadeChange = false; + const SCEVAddRecExpr *BasePtrSCEV = + cast(BucketChain.BaseSCEV); + if (!BasePtrSCEV->isAffine()) + return MadeChange; + + LLVM_DEBUG(dbgs() << "PIP: Transforming: " << *BasePtrSCEV << "\n"); + + assert(BasePtrSCEV->getLoop() == L && "AddRec for the wrong loop?"); + + // The instruction corresponding to the Bucket's BaseSCEV must be the first + // in the vector of elements. + Instruction *MemI = BucketChain.Elements.begin()->Instr; + Value *BasePtr = GetPointerOperand(MemI); + assert(BasePtr && "No pointer operand"); + + Type *I8Ty = Type::getInt8Ty(MemI->getParent()->getContext()); + Type *I8PtrTy = Type::getInt8PtrTy(MemI->getParent()->getContext(), + BasePtr->getType()->getPointerAddressSpace()); + + if (!SE->isLoopInvariant(BasePtrSCEV->getStart(), L)) + return MadeChange; + + const SCEVConstant *BasePtrIncSCEV = + dyn_cast(BasePtrSCEV->getStepRecurrence(*SE)); + if (!BasePtrIncSCEV) + return MadeChange; + + // For some DS form load/store instructions, it can also be an update form, + // if the stride is a multipler of 4. Use update form if prefer it. + bool CanPreInc = (Form == UpdateForm || + ((Form == DSForm) && !BasePtrIncSCEV->getAPInt().urem(4) && + PreferUpdateForm)); + const SCEV *BasePtrStartSCEV = nullptr; + if (CanPreInc) + BasePtrStartSCEV = + SE->getMinusSCEV(BasePtrSCEV->getStart(), BasePtrIncSCEV); + else + BasePtrStartSCEV = BasePtrSCEV->getStart(); + + if (!isSafeToExpand(BasePtrStartSCEV, *SE)) + return MadeChange; + + if (alreadyPrepared(L, MemI, BasePtrStartSCEV, BasePtrIncSCEV, Form)) + return MadeChange; + + LLVM_DEBUG(dbgs() << "PIP: New start is: " << *BasePtrStartSCEV << "\n"); + + BasicBlock *Header = L->getHeader(); + unsigned HeaderLoopPredCount = pred_size(Header); + BasicBlock *LoopPredecessor = L->getLoopPredecessor(); + + PHINode *NewPHI = + PHINode::Create(I8PtrTy, HeaderLoopPredCount, + getInstrName(MemI, PHINodeNameSuffix), + Header->getFirstNonPHI()); + + SCEVExpander SCEVE(*SE, Header->getModule()->getDataLayout(), "pistart"); + Value *BasePtrStart = SCEVE.expandCodeFor(BasePtrStartSCEV, I8PtrTy, + LoopPredecessor->getTerminator()); + + // Note that LoopPredecessor might occur in the predecessor list multiple + // times, and we need to add it the right number of times. + for (const auto &PI : predecessors(Header)) { + if (PI != LoopPredecessor) + continue; + + NewPHI->addIncoming(BasePtrStart, LoopPredecessor); + } + + Instruction *PtrInc = nullptr; + Instruction *NewBasePtr = nullptr; + if (CanPreInc) { + Instruction *InsPoint = &*Header->getFirstInsertionPt(); + PtrInc = GetElementPtrInst::Create( + I8Ty, NewPHI, BasePtrIncSCEV->getValue(), + getInstrName(MemI, GEPNodeIncNameSuffix), InsPoint); + cast(PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr)); + for (const auto &PI : predecessors(Header)) { + if (PI == LoopPredecessor) + continue; + + NewPHI->addIncoming(PtrInc, PI); + } + if (PtrInc->getType() != BasePtr->getType()) + NewBasePtr = new BitCastInst( + PtrInc, BasePtr->getType(), + getInstrName(PtrInc, CastNodeNameSuffix), InsPoint); + else + NewBasePtr = PtrInc; + } else { + // Note that LoopPredecessor might occur in the predecessor list multiple + // times, and we need to make sure no more incoming value for them in PHI. + for (const auto &PI : predecessors(Header)) { + if (PI == LoopPredecessor) + continue; + + // For the latch predecessor, we need to insert a GEP just before the + // terminator to increase the address. + BasicBlock *BB = PI; + Instruction *InsPoint = BB->getTerminator(); + PtrInc = GetElementPtrInst::Create( + I8Ty, NewPHI, BasePtrIncSCEV->getValue(), + getInstrName(MemI, GEPNodeIncNameSuffix), InsPoint); + + cast(PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr)); + + NewPHI->addIncoming(PtrInc, PI); + } + PtrInc = NewPHI; + if (NewPHI->getType() != BasePtr->getType()) + NewBasePtr = + new BitCastInst(NewPHI, BasePtr->getType(), + getInstrName(NewPHI, CastNodeNameSuffix), + &*Header->getFirstInsertionPt()); + else + NewBasePtr = NewPHI; + } + + if (Instruction *IDel = dyn_cast(BasePtr)) + BBChanged.insert(IDel->getParent()); + BasePtr->replaceAllUsesWith(NewBasePtr); + RecursivelyDeleteTriviallyDeadInstructions(BasePtr); + + // Keep track of the replacement pointer values we've inserted so that we + // don't generate more pointer values than necessary. + SmallPtrSet NewPtrs; + NewPtrs.insert(NewBasePtr); + + for (auto I = std::next(BucketChain.Elements.begin()), + IE = BucketChain.Elements.end(); I != IE; ++I) { + Value *Ptr = GetPointerOperand(I->Instr); + assert(Ptr && "No pointer operand"); + if (NewPtrs.count(Ptr)) + continue; + + Instruction *RealNewPtr; + if (!I->Offset || I->Offset->getValue()->isZero()) { + RealNewPtr = NewBasePtr; + } else { + Instruction *PtrIP = dyn_cast(Ptr); + if (PtrIP && isa(NewBasePtr) && + cast(NewBasePtr)->getParent() == PtrIP->getParent()) + PtrIP = nullptr; + else if (PtrIP && isa(PtrIP)) + PtrIP = &*PtrIP->getParent()->getFirstInsertionPt(); + else if (!PtrIP) + PtrIP = I->Instr; + + GetElementPtrInst *NewPtr = GetElementPtrInst::Create( + I8Ty, PtrInc, I->Offset->getValue(), + getInstrName(I->Instr, GEPNodeOffNameSuffix), PtrIP); + if (!PtrIP) + NewPtr->insertAfter(cast(PtrInc)); + NewPtr->setIsInBounds(IsPtrInBounds(Ptr)); + RealNewPtr = NewPtr; + } + + if (Instruction *IDel = dyn_cast(Ptr)) + BBChanged.insert(IDel->getParent()); + + Instruction *ReplNewPtr; + if (Ptr->getType() != RealNewPtr->getType()) { + ReplNewPtr = new BitCastInst(RealNewPtr, Ptr->getType(), + getInstrName(Ptr, CastNodeNameSuffix)); + ReplNewPtr->insertAfter(RealNewPtr); + } else + ReplNewPtr = RealNewPtr; + + Ptr->replaceAllUsesWith(ReplNewPtr); + RecursivelyDeleteTriviallyDeadInstructions(Ptr); + + NewPtrs.insert(RealNewPtr); + } + + MadeChange = true; + + SuccPrepCount++; + + if (Form == DSForm && !CanPreInc) + DSFormChainRewritten++; + else if (Form == DQForm) + DQFormChainRewritten++; + else if (Form == UpdateForm || (Form == DSForm && CanPreInc)) + UpdFormChainRewritten++; + + return MadeChange; +} + +bool PPCLoopPreIncPrep::updateFormPrep(Loop *L, + SmallVector &Buckets) { + bool MadeChange = false; + if (Buckets.empty()) + return MadeChange; + SmallSet BBChanged; + for (auto &Bucket : Buckets) + // The base address of each bucket is transformed into a phi and the others + // are rewritten based on new base. + if (prepareBaseForUpdateFormChain(Bucket)) + MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, UpdateForm); + + if (MadeChange) + for (auto &BB : L->blocks()) + if (BBChanged.count(BB)) + DeleteDeadPHIs(BB); + return MadeChange; +} + +bool PPCLoopPreIncPrep::dispFormPrep(Loop *L, SmallVector &Buckets, + InstrForm Form) { + bool MadeChange = false; + + if (Buckets.empty()) + return MadeChange; + + SmallSet BBChanged; + for (auto &Bucket : Buckets) { + if (Bucket.Elements.size() < DispFormPrepMinThreshold) + continue; + if (prepareBaseForDispFormChain(Bucket, Form)) + MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, Form); + } + + if (MadeChange) + for (auto &BB : L->blocks()) + if (BBChanged.count(BB)) + DeleteDeadPHIs(BB); + return MadeChange; +} + +// In order to prepare for the preferred instruction form, a PHI is added. +// This function will check to see if that PHI already exists and will return +// true if it found an existing PHI with the matched start and increment as the +// one we wanted to create. +bool PPCLoopPreIncPrep::alreadyPrepared(Loop *L, Instruction* MemI, + const SCEV *BasePtrStartSCEV, + const SCEVConstant *BasePtrIncSCEV, + InstrForm Form) { + BasicBlock *BB = MemI->getParent(); + if (!BB) + return false; + + BasicBlock *PredBB = L->getLoopPredecessor(); + BasicBlock *LatchBB = L->getLoopLatch(); + + if (!PredBB || !LatchBB) + return false; + + // Run through the PHIs and see if we have some that looks like a preparation + iterator_range PHIIter = BB->phis(); + for (auto & CurrentPHI : PHIIter) { + PHINode *CurrentPHINode = dyn_cast(&CurrentPHI); + if (!CurrentPHINode) + continue; + + if (!SE->isSCEVable(CurrentPHINode->getType())) + continue; + + const SCEV *PHISCEV = SE->getSCEVAtScope(CurrentPHINode, L); + + const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast(PHISCEV); + if (!PHIBasePtrSCEV) + continue; + + const SCEVConstant *PHIBasePtrIncSCEV = + dyn_cast(PHIBasePtrSCEV->getStepRecurrence(*SE)); + if (!PHIBasePtrIncSCEV) + continue; + + if (CurrentPHINode->getNumIncomingValues() == 2) { + if ((CurrentPHINode->getIncomingBlock(0) == LatchBB && + CurrentPHINode->getIncomingBlock(1) == PredBB) || + (CurrentPHINode->getIncomingBlock(1) == LatchBB && + CurrentPHINode->getIncomingBlock(0) == PredBB)) { + if (PHIBasePtrIncSCEV == BasePtrIncSCEV) { + // The existing PHI (CurrentPHINode) has the same start and increment + // as the PHI that we wanted to create. + if (Form == UpdateForm && + PHIBasePtrSCEV->getStart() == BasePtrStartSCEV) { + ++PHINodeAlreadyExistsUpdate; + return true; + } + if (Form == DSForm || Form == DQForm) { + const SCEVConstant *Diff = dyn_cast( + SE->getMinusSCEV(PHIBasePtrSCEV->getStart(), BasePtrStartSCEV)); + if (Diff && !Diff->getAPInt().urem(Form)) { + if (Form == DSForm) + ++PHINodeAlreadyExistsDS; + else + ++PHINodeAlreadyExistsDQ; + return true; + } + } + } + } + } + } + return false; +} + +bool PPCLoopPreIncPrep::runOnLoop(Loop *L) { + bool MadeChange = false; + + // Only prep. the inner-most loop + if (!L->empty()) + return MadeChange; + + // Return if already done enough preparation. + if (SuccPrepCount >= MaxVarsPrep) + return MadeChange; + + LLVM_DEBUG(dbgs() << "PIP: Examining: " << *L << "\n"); + + BasicBlock *LoopPredecessor = L->getLoopPredecessor(); + // If there is no loop predecessor, or the loop predecessor's terminator + // returns a value (which might contribute to determining the loop's + // iteration space), insert a new preheader for the loop. + if (!LoopPredecessor || + !LoopPredecessor->getTerminator()->getType()->isVoidTy()) { + LoopPredecessor = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA); + if (LoopPredecessor) + MadeChange = true; + } + if (!LoopPredecessor) { + LLVM_DEBUG(dbgs() << "PIP fails since no predecessor for current loop.\n"); + return MadeChange; + } + // Check if a load/store has update form. This lambda is used by function + // collectCandidates which can collect candidates for types defined by lambda. + auto isUpdateFormCandidate = [&] (const Instruction *I, + const Value *PtrValue) { + assert((PtrValue && I) && "Invalid parameter!"); + // There are no update forms for Altivec vector load/stores. + if (ST && ST->hasAltivec() && + PtrValue->getType()->getPointerElementType()->isVectorTy()) + return false; + // See getPreIndexedAddressParts, the displacement for LDU/STDU has to + // be 4's multiple (DS-form). For i64 loads/stores when the displacement + // fits in a 16-bit signed field but isn't a multiple of 4, it will be + // useless and possible to break some original well-form addressing mode + // to make this pre-inc prep for it. + if (PtrValue->getType()->getPointerElementType()->isIntegerTy(64)) { + const SCEV *LSCEV = SE->getSCEVAtScope(const_cast(PtrValue), L); + const SCEVAddRecExpr *LARSCEV = dyn_cast(LSCEV); + if (!LARSCEV || LARSCEV->getLoop() != L) + return false; + if (const SCEVConstant *StepConst = + dyn_cast(LARSCEV->getStepRecurrence(*SE))) { + const APInt &ConstInt = StepConst->getValue()->getValue(); + if (ConstInt.isSignedIntN(16) && ConstInt.srem(4) != 0) + return false; + } + } + return true; + }; + + // Check if a load/store has DS form. + auto isDSFormCandidate = [] (const Instruction *I, const Value *PtrValue) { + assert((PtrValue && I) && "Invalid parameter!"); + // FIXME: 32 bit instruction lwa is also DS form. + return !isa(I) && + ((PtrValue->getType()->getPointerElementType()->isIntegerTy(64)) || + (PtrValue->getType()->getPointerElementType()->isFloatTy()) || + (PtrValue->getType()->getPointerElementType()->isDoubleTy())); + }; + + // Check if a load/store has DQ form. + auto isDQFormCandidate = [&] (const Instruction *I, const Value *PtrValue) { + assert((PtrValue && I) && "Invalid parameter!"); + return !isa(I) && ST && ST->hasP9Vector() && + (PtrValue->getType()->getPointerElementType()->isVectorTy()); + }; + + // intrinsic for update form. + SmallVector UpdateFormBuckets = + collectCandidates(L, isUpdateFormCandidate, MaxVarsUpdateForm); + + // Prepare for update form. + if (!UpdateFormBuckets.empty()) + MadeChange |= updateFormPrep(L, UpdateFormBuckets); + + // Collect buckets of comparable addresses used by loads and stores for DS + // form. + SmallVector DSFormBuckets = + collectCandidates(L, isDSFormCandidate, MaxVarsDSForm); + + // Prepare for DS form. + if (!DSFormBuckets.empty()) + MadeChange |= dispFormPrep(L, DSFormBuckets, DSForm); + + // Collect buckets of comparable addresses used by loads and stores for DQ + // form. + SmallVector DQFormBuckets = + collectCandidates(L, isDQFormCandidate, MaxVarsDQForm); + + // Prepare for DQ form. + if (!DQFormBuckets.empty()) + MadeChange |= dispFormPrep(L, DQFormBuckets, DQForm); + + return MadeChange; +} Index: llvm/lib/Target/PowerPC/PPCLoopPreIncPrep.cpp =================================================================== --- llvm/lib/Target/PowerPC/PPCLoopPreIncPrep.cpp +++ /dev/null @@ -1,890 +0,0 @@ -//===------ PPCLoopPreIncPrep.cpp - Loop Pre-Inc. AM Prep. Pass -----------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -// -// This file implements a pass to prepare loops for ppc preferred addressing -// modes, leveraging different instruction form. (eg: DS/DQ form, D/DS form with -// update) -// Additional PHIs are created for loop induction variables used by load/store -// instructions so that preferred addressing modes can be used. -// -// 1: DS/DQ form preparation, prepare the load/store instructions so that they -// can satisfy the DS/DQ form displacement requirements. -// Generically, this means transforming loops like this: -// for (int i = 0; i < n; ++i) { -// unsigned long x1 = *(unsigned long *)(p + i + 5); -// unsigned long x2 = *(unsigned long *)(p + i + 9); -// } -// -// to look like this: -// -// unsigned NewP = p + 5; -// for (int i = 0; i < n; ++i) { -// unsigned long x1 = *(unsigned long *)(i + NewP); -// unsigned long x2 = *(unsigned long *)(i + NewP + 4); -// } -// -// 2: D/DS form with update preparation, prepare the load/store instructions so -// that we can use update form to do pre-increment. -// Generically, this means transforming loops like this: -// for (int i = 0; i < n; ++i) -// array[i] = c; -// -// to look like this: -// -// T *p = array[-1]; -// for (int i = 0; i < n; ++i) -// *++p = c; -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "ppc-loop-preinc-prep" - -#include "PPC.h" -#include "PPCSubtarget.h" -#include "PPCTargetMachine.h" -#include "llvm/ADT/DepthFirstIterator.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallSet.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/Analysis/LoopInfo.h" -#include "llvm/Analysis/ScalarEvolution.h" -#include "llvm/Analysis/ScalarEvolutionExpander.h" -#include "llvm/Analysis/ScalarEvolutionExpressions.h" -#include "llvm/IR/BasicBlock.h" -#include "llvm/IR/CFG.h" -#include "llvm/IR/Dominators.h" -#include "llvm/IR/Instruction.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/IntrinsicInst.h" -#include "llvm/IR/Module.h" -#include "llvm/IR/Type.h" -#include "llvm/IR/Value.h" -#include "llvm/InitializePasses.h" -#include "llvm/Pass.h" -#include "llvm/Support/Casting.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Debug.h" -#include "llvm/Transforms/Scalar.h" -#include "llvm/Transforms/Utils.h" -#include "llvm/Transforms/Utils/BasicBlockUtils.h" -#include "llvm/Transforms/Utils/Local.h" -#include "llvm/Transforms/Utils/LoopUtils.h" -#include -#include -#include - -using namespace llvm; - -// By default, we limit this to creating 16 common bases out of loops per -// function. 16 is a little over half of the allocatable register set. -static cl::opt MaxVarsPrep("ppc-formprep-max-vars", - cl::Hidden, cl::init(16), - cl::desc("Potential common base number threshold per function for PPC loop " - "prep")); - -static cl::opt PreferUpdateForm("ppc-formprep-prefer-update", - cl::init(true), cl::Hidden, - cl::desc("prefer update form when ds form is also a update form")); - -// Sum of following 3 per loop thresholds for all loops can not be larger -// than MaxVarsPrep. -// By default, we limit this to creating 9 PHIs for one loop. -// 9 and 3 for each kind prep are exterimental values on Power9. -static cl::opt 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 cl::opt 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 cl::opt MaxVarsDQForm("ppc-dqprep-max-vars", - cl::Hidden, cl::init(3), - cl::desc("Potential PHI threshold per loop for PPC loop prep of DQ form")); - - -// If would not be profitable if the common base has only one load/store, ISEL -// should already be able to choose best load/store form based on offset for -// single load/store. Set minimal profitable value default to 2 and make it as -// an option. -static cl::opt DispFormPrepMinThreshold("ppc-dispprep-min-threshold", - cl::Hidden, cl::init(2), - cl::desc("Minimal common base load/store instructions triggering DS/DQ form " - "preparation")); - -STATISTIC(PHINodeAlreadyExistsUpdate, "PHI node already in pre-increment form"); -STATISTIC(PHINodeAlreadyExistsDS, "PHI node already in DS form"); -STATISTIC(PHINodeAlreadyExistsDQ, "PHI node already in DQ form"); -STATISTIC(DSFormChainRewritten, "Num of DS form chain rewritten"); -STATISTIC(DQFormChainRewritten, "Num of DQ form chain rewritten"); -STATISTIC(UpdFormChainRewritten, "Num of update form chain rewritten"); - -namespace { - struct BucketElement { - BucketElement(const SCEVConstant *O, Instruction *I) : Offset(O), Instr(I) {} - BucketElement(Instruction *I) : Offset(nullptr), Instr(I) {} - - const SCEVConstant *Offset; - Instruction *Instr; - }; - - struct Bucket { - Bucket(const SCEV *B, Instruction *I) : BaseSCEV(B), - Elements(1, BucketElement(I)) {} - - const SCEV *BaseSCEV; - SmallVector Elements; - }; - - // "UpdateForm" is not a real PPC instruction form, it stands for dform - // load/store with update like ldu/stdu, or Prefetch intrinsic. - // For DS form instructions, their displacements must be multiple of 4. - // For DQ form instructions, their displacements must be multiple of 16. - enum InstrForm { UpdateForm = 1, DSForm = 4, DQForm = 16 }; - - class PPCLoopPreIncPrep : public FunctionPass { - public: - static char ID; // Pass ID, replacement for typeid - - PPCLoopPreIncPrep() : FunctionPass(ID) { - initializePPCLoopPreIncPrepPass(*PassRegistry::getPassRegistry()); - } - - PPCLoopPreIncPrep(PPCTargetMachine &TM) : FunctionPass(ID), TM(&TM) { - initializePPCLoopPreIncPrepPass(*PassRegistry::getPassRegistry()); - } - - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addPreserved(); - AU.addRequired(); - AU.addPreserved(); - AU.addRequired(); - } - - bool runOnFunction(Function &F) override; - - private: - PPCTargetMachine *TM = nullptr; - const PPCSubtarget *ST; - DominatorTree *DT; - LoopInfo *LI; - ScalarEvolution *SE; - bool PreserveLCSSA; - - /// Successful preparation number for Update/DS/DQ form in all inner most - /// loops. One successful preparation will put one common base out of loop, - /// this may leads to register presure like LICM does. - /// Make sure total preparation number can be controlled by option. - unsigned SuccPrepCount; - - bool runOnLoop(Loop *L); - - /// Check if required PHI node is already exist in Loop \p L. - bool alreadyPrepared(Loop *L, Instruction* MemI, - const SCEV *BasePtrStartSCEV, - const SCEVConstant *BasePtrIncSCEV, - InstrForm Form); - - /// Collect condition matched(\p isValidCandidate() returns true) - /// candidates in Loop \p L. - SmallVector - collectCandidates(Loop *L, - std::function - isValidCandidate, - unsigned MaxCandidateNum); - - /// Add a candidate to candidates \p Buckets. - void addOneCandidate(Instruction *MemI, const SCEV *LSCEV, - SmallVector &Buckets, - unsigned MaxCandidateNum); - - /// Prepare all candidates in \p Buckets for update form. - bool updateFormPrep(Loop *L, SmallVector &Buckets); - - /// Prepare all candidates in \p Buckets for displacement form, now for - /// ds/dq. - bool dispFormPrep(Loop *L, SmallVector &Buckets, - InstrForm Form); - - /// Prepare for one chain \p BucketChain, find the best base element and - /// update all other elements in \p BucketChain accordingly. - /// \p Form is used to find the best base element. - /// If success, best base element must be stored as the first element of - /// \p BucketChain. - /// Return false if no base element found, otherwise return true. - bool prepareBaseForDispFormChain(Bucket &BucketChain, - InstrForm Form); - - /// Prepare for one chain \p BucketChain, find the best base element and - /// update all other elements in \p BucketChain accordingly. - /// If success, best base element must be stored as the first element of - /// \p BucketChain. - /// Return false if no base element found, otherwise return true. - bool prepareBaseForUpdateFormChain(Bucket &BucketChain); - - /// Rewrite load/store instructions in \p BucketChain according to - /// preparation. - bool rewriteLoadStores(Loop *L, Bucket &BucketChain, - SmallSet &BBChanged, - InstrForm Form); - }; - -} // end anonymous namespace - -char PPCLoopPreIncPrep::ID = 0; -static const char *name = "Prepare loop for pre-inc. addressing modes"; -INITIALIZE_PASS_BEGIN(PPCLoopPreIncPrep, DEBUG_TYPE, name, false, false) -INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) -INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) -INITIALIZE_PASS_END(PPCLoopPreIncPrep, DEBUG_TYPE, name, false, false) - -static const std::string PHINodeNameSuffix = ".phi"; -static const std::string CastNodeNameSuffix = ".cast"; -static const std::string GEPNodeIncNameSuffix = ".inc"; -static const std::string GEPNodeOffNameSuffix = ".off"; - -FunctionPass *llvm::createPPCLoopPreIncPrepPass(PPCTargetMachine &TM) { - return new PPCLoopPreIncPrep(TM); -} - -static bool IsPtrInBounds(Value *BasePtr) { - Value *StrippedBasePtr = BasePtr; - while (BitCastInst *BC = dyn_cast(StrippedBasePtr)) - StrippedBasePtr = BC->getOperand(0); - if (GetElementPtrInst *GEP = dyn_cast(StrippedBasePtr)) - return GEP->isInBounds(); - - return false; -} - -static std::string getInstrName(const Value *I, const std::string Suffix) { - assert(I && "Invalid paramater!"); - if (I->hasName()) - return (I->getName() + Suffix).str(); - else - return ""; -} - -static Value *GetPointerOperand(Value *MemI) { - if (LoadInst *LMemI = dyn_cast(MemI)) { - return LMemI->getPointerOperand(); - } else if (StoreInst *SMemI = dyn_cast(MemI)) { - return SMemI->getPointerOperand(); - } else if (IntrinsicInst *IMemI = dyn_cast(MemI)) { - if (IMemI->getIntrinsicID() == Intrinsic::prefetch) - return IMemI->getArgOperand(0); - } - - return nullptr; -} - -bool PPCLoopPreIncPrep::runOnFunction(Function &F) { - if (skipFunction(F)) - return false; - - LI = &getAnalysis().getLoopInfo(); - SE = &getAnalysis().getSE(); - auto *DTWP = getAnalysisIfAvailable(); - DT = DTWP ? &DTWP->getDomTree() : nullptr; - PreserveLCSSA = mustPreserveAnalysisID(LCSSAID); - ST = TM ? TM->getSubtargetImpl(F) : nullptr; - SuccPrepCount = 0; - - bool MadeChange = false; - - for (auto I = LI->begin(), IE = LI->end(); I != IE; ++I) - for (auto L = df_begin(*I), LE = df_end(*I); L != LE; ++L) - MadeChange |= runOnLoop(*L); - - return MadeChange; -} - -void PPCLoopPreIncPrep::addOneCandidate(Instruction *MemI, const SCEV *LSCEV, - SmallVector &Buckets, - unsigned MaxCandidateNum) { - assert((MemI && GetPointerOperand(MemI)) && - "Candidate should be a memory instruction."); - assert(LSCEV && "Invalid SCEV for Ptr value."); - bool FoundBucket = false; - for (auto &B : Buckets) { - const SCEV *Diff = SE->getMinusSCEV(LSCEV, B.BaseSCEV); - if (const auto *CDiff = dyn_cast(Diff)) { - B.Elements.push_back(BucketElement(CDiff, MemI)); - FoundBucket = true; - break; - } - } - - if (!FoundBucket) { - if (Buckets.size() == MaxCandidateNum) - return; - Buckets.push_back(Bucket(LSCEV, MemI)); - } -} - -SmallVector PPCLoopPreIncPrep::collectCandidates( - Loop *L, - std::function isValidCandidate, - unsigned MaxCandidateNum) { - SmallVector Buckets; - for (const auto &BB : L->blocks()) - for (auto &J : *BB) { - Value *PtrValue; - Instruction *MemI; - - if (LoadInst *LMemI = dyn_cast(&J)) { - MemI = LMemI; - PtrValue = LMemI->getPointerOperand(); - } else if (StoreInst *SMemI = dyn_cast(&J)) { - MemI = SMemI; - PtrValue = SMemI->getPointerOperand(); - } else if (IntrinsicInst *IMemI = dyn_cast(&J)) { - if (IMemI->getIntrinsicID() == Intrinsic::prefetch) { - MemI = IMemI; - PtrValue = IMemI->getArgOperand(0); - } else continue; - } else continue; - - unsigned PtrAddrSpace = PtrValue->getType()->getPointerAddressSpace(); - if (PtrAddrSpace) - continue; - - if (L->isLoopInvariant(PtrValue)) - continue; - - const SCEV *LSCEV = SE->getSCEVAtScope(PtrValue, L); - const SCEVAddRecExpr *LARSCEV = dyn_cast(LSCEV); - if (!LARSCEV || LARSCEV->getLoop() != L) - continue; - - if (isValidCandidate(&J, PtrValue)) - addOneCandidate(MemI, LSCEV, Buckets, MaxCandidateNum); - } - return Buckets; -} - -bool PPCLoopPreIncPrep::prepareBaseForDispFormChain(Bucket &BucketChain, - InstrForm Form) { - // RemainderOffsetInfo details: - // key: value of (Offset urem DispConstraint). For DSForm, it can - // be [0, 4). - // first of pair: the index of first BucketElement whose remainder is equal - // to key. For key 0, this value must be 0. - // second of pair: number of load/stores with the same remainder. - DenseMap> RemainderOffsetInfo; - - for (unsigned j = 0, je = BucketChain.Elements.size(); j != je; ++j) { - if (!BucketChain.Elements[j].Offset) - RemainderOffsetInfo[0] = std::make_pair(0, 1); - else { - unsigned Remainder = - BucketChain.Elements[j].Offset->getAPInt().urem(Form); - if (RemainderOffsetInfo.find(Remainder) == RemainderOffsetInfo.end()) - RemainderOffsetInfo[Remainder] = std::make_pair(j, 1); - else - RemainderOffsetInfo[Remainder].second++; - } - } - // Currently we choose the most profitable base as the one which has the max - // number of load/store with same remainder. - // FIXME: adjust the base selection strategy according to load/store offset - // distribution. - // For example, if we have one candidate chain for DS form preparation, which - // contains following load/stores with different remainders: - // 1: 10 load/store whose remainder is 1; - // 2: 9 load/store whose remainder is 2; - // 3: 1 for remainder 3 and 0 for remainder 0; - // Now we will choose the first load/store whose remainder is 1 as base and - // adjust all other load/stores according to new base, so we will get 10 DS - // form and 10 X form. - // But we should be more clever, for this case we could use two bases, one for - // remainder 1 and the other for remainder 2, thus we could get 19 DS form and 1 - // X form. - unsigned MaxCountRemainder = 0; - for (unsigned j = 0; j < (unsigned)Form; j++) - if ((RemainderOffsetInfo.find(j) != RemainderOffsetInfo.end()) && - RemainderOffsetInfo[j].second > - RemainderOffsetInfo[MaxCountRemainder].second) - MaxCountRemainder = j; - - // Abort when there are too few insts with common base. - if (RemainderOffsetInfo[MaxCountRemainder].second < DispFormPrepMinThreshold) - return false; - - // If the first value is most profitable, no needed to adjust BucketChain - // elements as they are substracted the first value when collecting. - if (MaxCountRemainder == 0) - return true; - - // Adjust load/store to the new chosen base. - const SCEV *Offset = - BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first].Offset; - BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset); - for (auto &E : BucketChain.Elements) { - if (E.Offset) - E.Offset = cast(SE->getMinusSCEV(E.Offset, Offset)); - else - E.Offset = cast(SE->getNegativeSCEV(Offset)); - } - - std::swap(BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first], - BucketChain.Elements[0]); - return true; -} - -// FIXME: implement a more clever base choosing policy. -// Currently we always choose an exist load/store offset. This maybe lead to -// suboptimal code sequences. For example, for one DS chain with offsets -// {-32769, 2003, 2007, 2011}, we choose -32769 as base offset, and left disp -// for load/stores are {0, 34772, 34776, 34780}. Though each offset now is a -// multipler of 4, it cannot be represented by sint16. -bool PPCLoopPreIncPrep::prepareBaseForUpdateFormChain(Bucket &BucketChain) { - // We have a choice now of which instruction's memory operand we use as the - // base for the generated PHI. Always picking the first instruction in each - // bucket does not work well, specifically because that instruction might - // be a prefetch (and there are no pre-increment dcbt variants). Otherwise, - // the choice is somewhat arbitrary, because the backend will happily - // generate direct offsets from both the pre-incremented and - // post-incremented pointer values. Thus, we'll pick the first non-prefetch - // instruction in each bucket, and adjust the recurrence and other offsets - // accordingly. - for (int j = 0, je = BucketChain.Elements.size(); j != je; ++j) { - if (auto *II = dyn_cast(BucketChain.Elements[j].Instr)) - if (II->getIntrinsicID() == Intrinsic::prefetch) - continue; - - // If we'd otherwise pick the first element anyway, there's nothing to do. - if (j == 0) - break; - - // If our chosen element has no offset from the base pointer, there's - // nothing to do. - if (!BucketChain.Elements[j].Offset || - BucketChain.Elements[j].Offset->isZero()) - break; - - const SCEV *Offset = BucketChain.Elements[j].Offset; - BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset); - for (auto &E : BucketChain.Elements) { - if (E.Offset) - E.Offset = cast(SE->getMinusSCEV(E.Offset, Offset)); - else - E.Offset = cast(SE->getNegativeSCEV(Offset)); - } - - std::swap(BucketChain.Elements[j], BucketChain.Elements[0]); - break; - } - return true; -} - -bool PPCLoopPreIncPrep::rewriteLoadStores(Loop *L, Bucket &BucketChain, - SmallSet &BBChanged, - InstrForm Form) { - bool MadeChange = false; - const SCEVAddRecExpr *BasePtrSCEV = - cast(BucketChain.BaseSCEV); - if (!BasePtrSCEV->isAffine()) - return MadeChange; - - LLVM_DEBUG(dbgs() << "PIP: Transforming: " << *BasePtrSCEV << "\n"); - - assert(BasePtrSCEV->getLoop() == L && "AddRec for the wrong loop?"); - - // The instruction corresponding to the Bucket's BaseSCEV must be the first - // in the vector of elements. - Instruction *MemI = BucketChain.Elements.begin()->Instr; - Value *BasePtr = GetPointerOperand(MemI); - assert(BasePtr && "No pointer operand"); - - Type *I8Ty = Type::getInt8Ty(MemI->getParent()->getContext()); - Type *I8PtrTy = Type::getInt8PtrTy(MemI->getParent()->getContext(), - BasePtr->getType()->getPointerAddressSpace()); - - if (!SE->isLoopInvariant(BasePtrSCEV->getStart(), L)) - return MadeChange; - - const SCEVConstant *BasePtrIncSCEV = - dyn_cast(BasePtrSCEV->getStepRecurrence(*SE)); - if (!BasePtrIncSCEV) - return MadeChange; - - // For some DS form load/store instructions, it can also be an update form, - // if the stride is a multipler of 4. Use update form if prefer it. - bool CanPreInc = (Form == UpdateForm || - ((Form == DSForm) && !BasePtrIncSCEV->getAPInt().urem(4) && - PreferUpdateForm)); - const SCEV *BasePtrStartSCEV = nullptr; - if (CanPreInc) - BasePtrStartSCEV = - SE->getMinusSCEV(BasePtrSCEV->getStart(), BasePtrIncSCEV); - else - BasePtrStartSCEV = BasePtrSCEV->getStart(); - - if (!isSafeToExpand(BasePtrStartSCEV, *SE)) - return MadeChange; - - if (alreadyPrepared(L, MemI, BasePtrStartSCEV, BasePtrIncSCEV, Form)) - return MadeChange; - - LLVM_DEBUG(dbgs() << "PIP: New start is: " << *BasePtrStartSCEV << "\n"); - - BasicBlock *Header = L->getHeader(); - unsigned HeaderLoopPredCount = pred_size(Header); - BasicBlock *LoopPredecessor = L->getLoopPredecessor(); - - PHINode *NewPHI = - PHINode::Create(I8PtrTy, HeaderLoopPredCount, - getInstrName(MemI, PHINodeNameSuffix), - Header->getFirstNonPHI()); - - SCEVExpander SCEVE(*SE, Header->getModule()->getDataLayout(), "pistart"); - Value *BasePtrStart = SCEVE.expandCodeFor(BasePtrStartSCEV, I8PtrTy, - LoopPredecessor->getTerminator()); - - // Note that LoopPredecessor might occur in the predecessor list multiple - // times, and we need to add it the right number of times. - for (const auto &PI : predecessors(Header)) { - if (PI != LoopPredecessor) - continue; - - NewPHI->addIncoming(BasePtrStart, LoopPredecessor); - } - - Instruction *PtrInc = nullptr; - Instruction *NewBasePtr = nullptr; - if (CanPreInc) { - Instruction *InsPoint = &*Header->getFirstInsertionPt(); - PtrInc = GetElementPtrInst::Create( - I8Ty, NewPHI, BasePtrIncSCEV->getValue(), - getInstrName(MemI, GEPNodeIncNameSuffix), InsPoint); - cast(PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr)); - for (const auto &PI : predecessors(Header)) { - if (PI == LoopPredecessor) - continue; - - NewPHI->addIncoming(PtrInc, PI); - } - if (PtrInc->getType() != BasePtr->getType()) - NewBasePtr = new BitCastInst( - PtrInc, BasePtr->getType(), - getInstrName(PtrInc, CastNodeNameSuffix), InsPoint); - else - NewBasePtr = PtrInc; - } else { - // Note that LoopPredecessor might occur in the predecessor list multiple - // times, and we need to make sure no more incoming value for them in PHI. - for (const auto &PI : predecessors(Header)) { - if (PI == LoopPredecessor) - continue; - - // For the latch predecessor, we need to insert a GEP just before the - // terminator to increase the address. - BasicBlock *BB = PI; - Instruction *InsPoint = BB->getTerminator(); - PtrInc = GetElementPtrInst::Create( - I8Ty, NewPHI, BasePtrIncSCEV->getValue(), - getInstrName(MemI, GEPNodeIncNameSuffix), InsPoint); - - cast(PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr)); - - NewPHI->addIncoming(PtrInc, PI); - } - PtrInc = NewPHI; - if (NewPHI->getType() != BasePtr->getType()) - NewBasePtr = - new BitCastInst(NewPHI, BasePtr->getType(), - getInstrName(NewPHI, CastNodeNameSuffix), - &*Header->getFirstInsertionPt()); - else - NewBasePtr = NewPHI; - } - - if (Instruction *IDel = dyn_cast(BasePtr)) - BBChanged.insert(IDel->getParent()); - BasePtr->replaceAllUsesWith(NewBasePtr); - RecursivelyDeleteTriviallyDeadInstructions(BasePtr); - - // Keep track of the replacement pointer values we've inserted so that we - // don't generate more pointer values than necessary. - SmallPtrSet NewPtrs; - NewPtrs.insert(NewBasePtr); - - for (auto I = std::next(BucketChain.Elements.begin()), - IE = BucketChain.Elements.end(); I != IE; ++I) { - Value *Ptr = GetPointerOperand(I->Instr); - assert(Ptr && "No pointer operand"); - if (NewPtrs.count(Ptr)) - continue; - - Instruction *RealNewPtr; - if (!I->Offset || I->Offset->getValue()->isZero()) { - RealNewPtr = NewBasePtr; - } else { - Instruction *PtrIP = dyn_cast(Ptr); - if (PtrIP && isa(NewBasePtr) && - cast(NewBasePtr)->getParent() == PtrIP->getParent()) - PtrIP = nullptr; - else if (PtrIP && isa(PtrIP)) - PtrIP = &*PtrIP->getParent()->getFirstInsertionPt(); - else if (!PtrIP) - PtrIP = I->Instr; - - GetElementPtrInst *NewPtr = GetElementPtrInst::Create( - I8Ty, PtrInc, I->Offset->getValue(), - getInstrName(I->Instr, GEPNodeOffNameSuffix), PtrIP); - if (!PtrIP) - NewPtr->insertAfter(cast(PtrInc)); - NewPtr->setIsInBounds(IsPtrInBounds(Ptr)); - RealNewPtr = NewPtr; - } - - if (Instruction *IDel = dyn_cast(Ptr)) - BBChanged.insert(IDel->getParent()); - - Instruction *ReplNewPtr; - if (Ptr->getType() != RealNewPtr->getType()) { - ReplNewPtr = new BitCastInst(RealNewPtr, Ptr->getType(), - getInstrName(Ptr, CastNodeNameSuffix)); - ReplNewPtr->insertAfter(RealNewPtr); - } else - ReplNewPtr = RealNewPtr; - - Ptr->replaceAllUsesWith(ReplNewPtr); - RecursivelyDeleteTriviallyDeadInstructions(Ptr); - - NewPtrs.insert(RealNewPtr); - } - - MadeChange = true; - - SuccPrepCount++; - - if (Form == DSForm && !CanPreInc) - DSFormChainRewritten++; - else if (Form == DQForm) - DQFormChainRewritten++; - else if (Form == UpdateForm || (Form == DSForm && CanPreInc)) - UpdFormChainRewritten++; - - return MadeChange; -} - -bool PPCLoopPreIncPrep::updateFormPrep(Loop *L, - SmallVector &Buckets) { - bool MadeChange = false; - if (Buckets.empty()) - return MadeChange; - SmallSet BBChanged; - for (auto &Bucket : Buckets) - // The base address of each bucket is transformed into a phi and the others - // are rewritten based on new base. - if (prepareBaseForUpdateFormChain(Bucket)) - MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, UpdateForm); - - if (MadeChange) - for (auto &BB : L->blocks()) - if (BBChanged.count(BB)) - DeleteDeadPHIs(BB); - return MadeChange; -} - -bool PPCLoopPreIncPrep::dispFormPrep(Loop *L, SmallVector &Buckets, - InstrForm Form) { - bool MadeChange = false; - - if (Buckets.empty()) - return MadeChange; - - SmallSet BBChanged; - for (auto &Bucket : Buckets) { - if (Bucket.Elements.size() < DispFormPrepMinThreshold) - continue; - if (prepareBaseForDispFormChain(Bucket, Form)) - MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, Form); - } - - if (MadeChange) - for (auto &BB : L->blocks()) - if (BBChanged.count(BB)) - DeleteDeadPHIs(BB); - return MadeChange; -} - -// In order to prepare for the preferred instruction form, a PHI is added. -// This function will check to see if that PHI already exists and will return -// true if it found an existing PHI with the matched start and increment as the -// one we wanted to create. -bool PPCLoopPreIncPrep::alreadyPrepared(Loop *L, Instruction* MemI, - const SCEV *BasePtrStartSCEV, - const SCEVConstant *BasePtrIncSCEV, - InstrForm Form) { - BasicBlock *BB = MemI->getParent(); - if (!BB) - return false; - - BasicBlock *PredBB = L->getLoopPredecessor(); - BasicBlock *LatchBB = L->getLoopLatch(); - - if (!PredBB || !LatchBB) - return false; - - // Run through the PHIs and see if we have some that looks like a preparation - iterator_range PHIIter = BB->phis(); - for (auto & CurrentPHI : PHIIter) { - PHINode *CurrentPHINode = dyn_cast(&CurrentPHI); - if (!CurrentPHINode) - continue; - - if (!SE->isSCEVable(CurrentPHINode->getType())) - continue; - - const SCEV *PHISCEV = SE->getSCEVAtScope(CurrentPHINode, L); - - const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast(PHISCEV); - if (!PHIBasePtrSCEV) - continue; - - const SCEVConstant *PHIBasePtrIncSCEV = - dyn_cast(PHIBasePtrSCEV->getStepRecurrence(*SE)); - if (!PHIBasePtrIncSCEV) - continue; - - if (CurrentPHINode->getNumIncomingValues() == 2) { - if ((CurrentPHINode->getIncomingBlock(0) == LatchBB && - CurrentPHINode->getIncomingBlock(1) == PredBB) || - (CurrentPHINode->getIncomingBlock(1) == LatchBB && - CurrentPHINode->getIncomingBlock(0) == PredBB)) { - if (PHIBasePtrIncSCEV == BasePtrIncSCEV) { - // The existing PHI (CurrentPHINode) has the same start and increment - // as the PHI that we wanted to create. - if (Form == UpdateForm && - PHIBasePtrSCEV->getStart() == BasePtrStartSCEV) { - ++PHINodeAlreadyExistsUpdate; - return true; - } - if (Form == DSForm || Form == DQForm) { - const SCEVConstant *Diff = dyn_cast( - SE->getMinusSCEV(PHIBasePtrSCEV->getStart(), BasePtrStartSCEV)); - if (Diff && !Diff->getAPInt().urem(Form)) { - if (Form == DSForm) - ++PHINodeAlreadyExistsDS; - else - ++PHINodeAlreadyExistsDQ; - return true; - } - } - } - } - } - } - return false; -} - -bool PPCLoopPreIncPrep::runOnLoop(Loop *L) { - bool MadeChange = false; - - // Only prep. the inner-most loop - if (!L->empty()) - return MadeChange; - - // Return if already done enough preparation. - if (SuccPrepCount >= MaxVarsPrep) - return MadeChange; - - LLVM_DEBUG(dbgs() << "PIP: Examining: " << *L << "\n"); - - BasicBlock *LoopPredecessor = L->getLoopPredecessor(); - // If there is no loop predecessor, or the loop predecessor's terminator - // returns a value (which might contribute to determining the loop's - // iteration space), insert a new preheader for the loop. - if (!LoopPredecessor || - !LoopPredecessor->getTerminator()->getType()->isVoidTy()) { - LoopPredecessor = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA); - if (LoopPredecessor) - MadeChange = true; - } - if (!LoopPredecessor) { - LLVM_DEBUG(dbgs() << "PIP fails since no predecessor for current loop.\n"); - return MadeChange; - } - // Check if a load/store has update form. This lambda is used by function - // collectCandidates which can collect candidates for types defined by lambda. - auto isUpdateFormCandidate = [&] (const Instruction *I, - const Value *PtrValue) { - assert((PtrValue && I) && "Invalid parameter!"); - // There are no update forms for Altivec vector load/stores. - if (ST && ST->hasAltivec() && - PtrValue->getType()->getPointerElementType()->isVectorTy()) - return false; - // See getPreIndexedAddressParts, the displacement for LDU/STDU has to - // be 4's multiple (DS-form). For i64 loads/stores when the displacement - // fits in a 16-bit signed field but isn't a multiple of 4, it will be - // useless and possible to break some original well-form addressing mode - // to make this pre-inc prep for it. - if (PtrValue->getType()->getPointerElementType()->isIntegerTy(64)) { - const SCEV *LSCEV = SE->getSCEVAtScope(const_cast(PtrValue), L); - const SCEVAddRecExpr *LARSCEV = dyn_cast(LSCEV); - if (!LARSCEV || LARSCEV->getLoop() != L) - return false; - if (const SCEVConstant *StepConst = - dyn_cast(LARSCEV->getStepRecurrence(*SE))) { - const APInt &ConstInt = StepConst->getValue()->getValue(); - if (ConstInt.isSignedIntN(16) && ConstInt.srem(4) != 0) - return false; - } - } - return true; - }; - - // Check if a load/store has DS form. - auto isDSFormCandidate = [] (const Instruction *I, const Value *PtrValue) { - assert((PtrValue && I) && "Invalid parameter!"); - // FIXME: 32 bit instruction lwa is also DS form. - return !isa(I) && - ((PtrValue->getType()->getPointerElementType()->isIntegerTy(64)) || - (PtrValue->getType()->getPointerElementType()->isFloatTy()) || - (PtrValue->getType()->getPointerElementType()->isDoubleTy())); - }; - - // Check if a load/store has DQ form. - auto isDQFormCandidate = [&] (const Instruction *I, const Value *PtrValue) { - assert((PtrValue && I) && "Invalid parameter!"); - return !isa(I) && ST && ST->hasP9Vector() && - (PtrValue->getType()->getPointerElementType()->isVectorTy()); - }; - - // intrinsic for update form. - SmallVector UpdateFormBuckets = - collectCandidates(L, isUpdateFormCandidate, MaxVarsUpdateForm); - - // Prepare for update form. - if (!UpdateFormBuckets.empty()) - MadeChange |= updateFormPrep(L, UpdateFormBuckets); - - // Collect buckets of comparable addresses used by loads and stores for DS - // form. - SmallVector DSFormBuckets = - collectCandidates(L, isDSFormCandidate, MaxVarsDSForm); - - // Prepare for DS form. - if (!DSFormBuckets.empty()) - MadeChange |= dispFormPrep(L, DSFormBuckets, DSForm); - - // Collect buckets of comparable addresses used by loads and stores for DQ - // form. - SmallVector DQFormBuckets = - collectCandidates(L, isDQFormCandidate, MaxVarsDQForm); - - // Prepare for DQ form. - if (!DQFormBuckets.empty()) - MadeChange |= dispFormPrep(L, DQFormBuckets, DQForm); - - return MadeChange; -} Index: llvm/utils/gn/secondary/llvm/lib/Target/PowerPC/BUILD.gn =================================================================== --- llvm/utils/gn/secondary/llvm/lib/Target/PowerPC/BUILD.gn +++ llvm/utils/gn/secondary/llvm/lib/Target/PowerPC/BUILD.gn @@ -53,7 +53,7 @@ "PPCISelDAGToDAG.cpp", "PPCISelLowering.cpp", "PPCInstrInfo.cpp", - "PPCLoopPreIncPrep.cpp", + "PPCLoopInstrFormPrep.cpp", "PPCLowerMASSVEntries.cpp", "PPCMCInstLower.cpp", "PPCMIPeephole.cpp",