1488 lines · cpp
1//===------ PPCLoopInstrFormPrep.cpp - Loop Instr Form Prep Pass ----------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements a pass to prepare loops for ppc preferred addressing10// modes, leveraging different instruction form. (eg: DS/DQ form, D/DS form with11// update)12// Additional PHIs are created for loop induction variables used by load/store13// instructions so that preferred addressing modes can be used.14//15// 1: DS/DQ form preparation, prepare the load/store instructions so that they16// can satisfy the DS/DQ form displacement requirements.17// Generically, this means transforming loops like this:18// for (int i = 0; i < n; ++i) {19// unsigned long x1 = *(unsigned long *)(p + i + 5);20// unsigned long x2 = *(unsigned long *)(p + i + 9);21// }22//23// to look like this:24//25// unsigned NewP = p + 5;26// for (int i = 0; i < n; ++i) {27// unsigned long x1 = *(unsigned long *)(i + NewP);28// unsigned long x2 = *(unsigned long *)(i + NewP + 4);29// }30//31// 2: D/DS form with update preparation, prepare the load/store instructions so32// that we can use update form to do pre-increment.33// Generically, this means transforming loops like this:34// for (int i = 0; i < n; ++i)35// array[i] = c;36//37// to look like this:38//39// T *p = array[-1];40// for (int i = 0; i < n; ++i)41// *++p = c;42//43// 3: common multiple chains for the load/stores with same offsets in the loop,44// so that we can reuse the offsets and reduce the register pressure in the45// loop. This transformation can also increase the loop ILP as now each chain46// uses its own loop induction add/addi. But this will increase the number of47// add/addi in the loop.48//49// Generically, this means transforming loops like this:50//51// char *p;52// A1 = p + base153// A2 = p + base1 + offset54// B1 = p + base255// B2 = p + base2 + offset56//57// for (int i = 0; i < n; i++)58// unsigned long x1 = *(unsigned long *)(A1 + i);59// unsigned long x2 = *(unsigned long *)(A2 + i)60// unsigned long x3 = *(unsigned long *)(B1 + i);61// unsigned long x4 = *(unsigned long *)(B2 + i);62// }63//64// to look like this:65//66// A1_new = p + base1 // chain 167// B1_new = p + base2 // chain 2, now inside the loop, common offset is68// // reused.69//70// for (long long i = 0; i < n; i+=count) {71// unsigned long x1 = *(unsigned long *)(A1_new + i);72// unsigned long x2 = *(unsigned long *)((A1_new + i) + offset);73// unsigned long x3 = *(unsigned long *)(B1_new + i);74// unsigned long x4 = *(unsigned long *)((B1_new + i) + offset);75// }76//===----------------------------------------------------------------------===//77 78#include "PPC.h"79#include "PPCSubtarget.h"80#include "PPCTargetMachine.h"81#include "llvm/ADT/DepthFirstIterator.h"82#include "llvm/ADT/SmallPtrSet.h"83#include "llvm/ADT/SmallVector.h"84#include "llvm/ADT/Statistic.h"85#include "llvm/Analysis/LoopInfo.h"86#include "llvm/Analysis/ScalarEvolution.h"87#include "llvm/Analysis/ScalarEvolutionExpressions.h"88#include "llvm/IR/BasicBlock.h"89#include "llvm/IR/CFG.h"90#include "llvm/IR/Dominators.h"91#include "llvm/IR/Instruction.h"92#include "llvm/IR/Instructions.h"93#include "llvm/IR/IntrinsicInst.h"94#include "llvm/IR/IntrinsicsPowerPC.h"95#include "llvm/IR/Type.h"96#include "llvm/IR/Value.h"97#include "llvm/Pass.h"98#include "llvm/Support/Casting.h"99#include "llvm/Support/CommandLine.h"100#include "llvm/Support/Debug.h"101#include "llvm/Transforms/Scalar.h"102#include "llvm/Transforms/Utils.h"103#include "llvm/Transforms/Utils/BasicBlockUtils.h"104#include "llvm/Transforms/Utils/Local.h"105#include "llvm/Transforms/Utils/LoopUtils.h"106#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"107#include <cassert>108#include <cmath>109#include <utility>110 111#define DEBUG_TYPE "ppc-loop-instr-form-prep"112 113using namespace llvm;114 115static cl::opt<unsigned>116 MaxVarsPrep("ppc-formprep-max-vars", cl::Hidden, cl::init(24),117 cl::desc("Potential common base number threshold per function "118 "for PPC loop prep"));119 120static cl::opt<bool> PreferUpdateForm("ppc-formprep-prefer-update",121 cl::init(true), cl::Hidden,122 cl::desc("prefer update form when ds form is also a update form"));123 124static cl::opt<bool> EnableUpdateFormForNonConstInc(125 "ppc-formprep-update-nonconst-inc", cl::init(false), cl::Hidden,126 cl::desc("prepare update form when the load/store increment is a loop "127 "invariant non-const value."));128 129static cl::opt<bool> EnableChainCommoning(130 "ppc-formprep-chain-commoning", cl::init(false), cl::Hidden,131 cl::desc("Enable chain commoning in PPC loop prepare pass."));132 133// Sum of following 3 per loop thresholds for all loops can not be larger134// than MaxVarsPrep.135// now the thresholds for each kind prep are exterimental values on Power9.136static cl::opt<unsigned> MaxVarsUpdateForm("ppc-preinc-prep-max-vars",137 cl::Hidden, cl::init(3),138 cl::desc("Potential PHI threshold per loop for PPC loop prep of update "139 "form"));140 141static cl::opt<unsigned> MaxVarsDSForm("ppc-dsprep-max-vars",142 cl::Hidden, cl::init(3),143 cl::desc("Potential PHI threshold per loop for PPC loop prep of DS form"));144 145static cl::opt<unsigned> MaxVarsDQForm("ppc-dqprep-max-vars",146 cl::Hidden, cl::init(8),147 cl::desc("Potential PHI threshold per loop for PPC loop prep of DQ form"));148 149// Commoning chain will reduce the register pressure, so we don't consider about150// the PHI nodes number.151// But commoning chain will increase the addi/add number in the loop and also152// increase loop ILP. Maximum chain number should be same with hardware153// IssueWidth, because we won't benefit from ILP if the parallel chains number154// is bigger than IssueWidth. We assume there are 2 chains in one bucket, so155// there would be 4 buckets at most on P9(IssueWidth is 8).156static cl::opt<unsigned> MaxVarsChainCommon(157 "ppc-chaincommon-max-vars", cl::Hidden, cl::init(4),158 cl::desc("Bucket number per loop for PPC loop chain common"));159 160// If would not be profitable if the common base has only one load/store, ISEL161// should already be able to choose best load/store form based on offset for162// single load/store. Set minimal profitable value default to 2 and make it as163// an option.164static cl::opt<unsigned> DispFormPrepMinThreshold("ppc-dispprep-min-threshold",165 cl::Hidden, cl::init(2),166 cl::desc("Minimal common base load/store instructions triggering DS/DQ form "167 "preparation"));168 169static cl::opt<unsigned> ChainCommonPrepMinThreshold(170 "ppc-chaincommon-min-threshold", cl::Hidden, cl::init(4),171 cl::desc("Minimal common base load/store instructions triggering chain "172 "commoning preparation. Must be not smaller than 4"));173 174STATISTIC(PHINodeAlreadyExistsUpdate, "PHI node already in pre-increment form");175STATISTIC(PHINodeAlreadyExistsDS, "PHI node already in DS form");176STATISTIC(PHINodeAlreadyExistsDQ, "PHI node already in DQ form");177STATISTIC(DSFormChainRewritten, "Num of DS form chain rewritten");178STATISTIC(DQFormChainRewritten, "Num of DQ form chain rewritten");179STATISTIC(UpdFormChainRewritten, "Num of update form chain rewritten");180STATISTIC(ChainCommoningRewritten, "Num of commoning chains");181 182namespace {183 struct BucketElement {184 BucketElement(const SCEV *O, Instruction *I) : Offset(O), Instr(I) {}185 BucketElement(Instruction *I) : Offset(nullptr), Instr(I) {}186 187 const SCEV *Offset;188 Instruction *Instr;189 };190 191 struct Bucket {192 Bucket(const SCEV *B, Instruction *I)193 : BaseSCEV(B), Elements(1, BucketElement(I)) {194 ChainSize = 0;195 }196 197 // The base of the whole bucket.198 const SCEV *BaseSCEV;199 200 // All elements in the bucket. In the bucket, the element with the BaseSCEV201 // has no offset and all other elements are stored as offsets to the202 // BaseSCEV.203 SmallVector<BucketElement, 16> Elements;204 205 // The potential chains size. This is used for chain commoning only.206 unsigned ChainSize;207 208 // The base for each potential chain. This is used for chain commoning only.209 SmallVector<BucketElement, 16> ChainBases;210 };211 212 // "UpdateForm" is not a real PPC instruction form, it stands for dform213 // load/store with update like ldu/stdu, or Prefetch intrinsic.214 // For DS form instructions, their displacements must be multiple of 4.215 // For DQ form instructions, their displacements must be multiple of 16.216 enum PrepForm { UpdateForm = 1, DSForm = 4, DQForm = 16, ChainCommoning };217 218 class PPCLoopInstrFormPrep : public FunctionPass {219 public:220 static char ID; // Pass ID, replacement for typeid221 222 PPCLoopInstrFormPrep(PPCTargetMachine &TM) : FunctionPass(ID), TM(&TM) {}223 224 void getAnalysisUsage(AnalysisUsage &AU) const override {225 AU.addPreserved<DominatorTreeWrapperPass>();226 AU.addRequired<LoopInfoWrapperPass>();227 AU.addPreserved<LoopInfoWrapperPass>();228 AU.addRequired<ScalarEvolutionWrapperPass>();229 }230 231 bool runOnFunction(Function &F) override;232 233 private:234 PPCTargetMachine *TM = nullptr;235 const PPCSubtarget *ST;236 DominatorTree *DT;237 LoopInfo *LI;238 ScalarEvolution *SE;239 bool PreserveLCSSA;240 bool HasCandidateForPrepare;241 242 /// Successful preparation number for Update/DS/DQ form in all inner most243 /// loops. One successful preparation will put one common base out of loop,244 /// this may leads to register presure like LICM does.245 /// Make sure total preparation number can be controlled by option.246 unsigned SuccPrepCount;247 248 bool runOnLoop(Loop *L);249 250 /// Check if required PHI node is already exist in Loop \p L.251 bool alreadyPrepared(Loop *L, Instruction *MemI,252 const SCEV *BasePtrStartSCEV,253 const SCEV *BasePtrIncSCEV, PrepForm Form);254 255 /// Get the value which defines the increment SCEV \p BasePtrIncSCEV.256 Value *getNodeForInc(Loop *L, Instruction *MemI,257 const SCEV *BasePtrIncSCEV);258 259 /// Common chains to reuse offsets for a loop to reduce register pressure.260 bool chainCommoning(Loop *L, SmallVector<Bucket, 16> &Buckets);261 262 /// Find out the potential commoning chains and their bases.263 bool prepareBasesForCommoningChains(Bucket &BucketChain);264 265 /// Rewrite load/store according to the common chains.266 bool rewriteLoadStoresForCommoningChains(267 Loop *L, Bucket &Bucket, SmallPtrSet<BasicBlock *, 16> &BBChanged);268 269 /// Collect condition matched(\p isValidCandidate() returns true)270 /// candidates in Loop \p L.271 SmallVector<Bucket, 16> collectCandidates(272 Loop *L,273 std::function<bool(const Instruction *, Value *, const Type *)>274 isValidCandidate,275 std::function<bool(const SCEV *)> isValidDiff,276 unsigned MaxCandidateNum);277 278 /// Add a candidate to candidates \p Buckets if diff between candidate and279 /// one base in \p Buckets matches \p isValidDiff.280 void addOneCandidate(Instruction *MemI, const SCEV *LSCEV,281 SmallVector<Bucket, 16> &Buckets,282 std::function<bool(const SCEV *)> isValidDiff,283 unsigned MaxCandidateNum);284 285 /// Prepare all candidates in \p Buckets for update form.286 bool updateFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets);287 288 /// Prepare all candidates in \p Buckets for displacement form, now for289 /// ds/dq.290 bool dispFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets, PrepForm Form);291 292 /// Prepare for one chain \p BucketChain, find the best base element and293 /// update all other elements in \p BucketChain accordingly.294 /// \p Form is used to find the best base element.295 /// If success, best base element must be stored as the first element of296 /// \p BucketChain.297 /// Return false if no base element found, otherwise return true.298 bool prepareBaseForDispFormChain(Bucket &BucketChain, PrepForm Form);299 300 /// Prepare for one chain \p BucketChain, find the best base element and301 /// update all other elements in \p BucketChain accordingly.302 /// If success, best base element must be stored as the first element of303 /// \p BucketChain.304 /// Return false if no base element found, otherwise return true.305 bool prepareBaseForUpdateFormChain(Bucket &BucketChain);306 307 /// Rewrite load/store instructions in \p BucketChain according to308 /// preparation.309 bool rewriteLoadStores(Loop *L, Bucket &BucketChain,310 SmallPtrSet<BasicBlock *, 16> &BBChanged,311 PrepForm Form);312 313 /// Rewrite for the base load/store of a chain.314 std::pair<Instruction *, Instruction *>315 rewriteForBase(Loop *L, const SCEVAddRecExpr *BasePtrSCEV,316 Instruction *BaseMemI, bool CanPreInc, PrepForm Form,317 SCEVExpander &SCEVE, SmallPtrSet<Value *, 16> &DeletedPtrs);318 319 /// Rewrite for the other load/stores of a chain according to the new \p320 /// Base.321 Instruction *322 rewriteForBucketElement(std::pair<Instruction *, Instruction *> Base,323 const BucketElement &Element, Value *OffToBase,324 SmallPtrSet<Value *, 16> &DeletedPtrs);325 };326 327} // end anonymous namespace328 329char PPCLoopInstrFormPrep::ID = 0;330static const char *name = "Prepare loop for ppc preferred instruction forms";331INITIALIZE_PASS_BEGIN(PPCLoopInstrFormPrep, DEBUG_TYPE, name, false, false)332INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)333INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)334INITIALIZE_PASS_END(PPCLoopInstrFormPrep, DEBUG_TYPE, name, false, false)335 336static constexpr StringRef PHINodeNameSuffix = ".phi";337static constexpr StringRef CastNodeNameSuffix = ".cast";338static constexpr StringRef GEPNodeIncNameSuffix = ".inc";339static constexpr StringRef GEPNodeOffNameSuffix = ".off";340 341FunctionPass *llvm::createPPCLoopInstrFormPrepPass(PPCTargetMachine &TM) {342 return new PPCLoopInstrFormPrep(TM);343}344 345static bool IsPtrInBounds(Value *BasePtr) {346 Value *StrippedBasePtr = BasePtr;347 while (BitCastInst *BC = dyn_cast<BitCastInst>(StrippedBasePtr))348 StrippedBasePtr = BC->getOperand(0);349 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(StrippedBasePtr))350 return GEP->isInBounds();351 352 return false;353}354 355static std::string getInstrName(const Value *I, StringRef Suffix) {356 assert(I && "Invalid paramater!");357 if (I->hasName())358 return (I->getName() + Suffix).str();359 else360 return "";361}362 363static Value *getPointerOperandAndType(Value *MemI,364 Type **PtrElementType = nullptr) {365 366 Value *PtrValue = nullptr;367 Type *PointerElementType = nullptr;368 369 if (LoadInst *LMemI = dyn_cast<LoadInst>(MemI)) {370 PtrValue = LMemI->getPointerOperand();371 PointerElementType = LMemI->getType();372 } else if (StoreInst *SMemI = dyn_cast<StoreInst>(MemI)) {373 PtrValue = SMemI->getPointerOperand();374 PointerElementType = SMemI->getValueOperand()->getType();375 } else if (IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(MemI)) {376 PointerElementType = Type::getInt8Ty(MemI->getContext());377 if (IMemI->getIntrinsicID() == Intrinsic::prefetch ||378 IMemI->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp) {379 PtrValue = IMemI->getArgOperand(0);380 } else if (IMemI->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp) {381 PtrValue = IMemI->getArgOperand(1);382 }383 }384 /*Get ElementType if PtrElementType is not null.*/385 if (PtrElementType)386 *PtrElementType = PointerElementType;387 388 return PtrValue;389}390 391bool PPCLoopInstrFormPrep::runOnFunction(Function &F) {392 if (skipFunction(F))393 return false;394 395 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();396 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();397 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();398 DT = DTWP ? &DTWP->getDomTree() : nullptr;399 PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);400 ST = TM ? TM->getSubtargetImpl(F) : nullptr;401 SuccPrepCount = 0;402 403 bool MadeChange = false;404 405 for (Loop *I : *LI)406 for (Loop *L : depth_first(I))407 MadeChange |= runOnLoop(L);408 409 return MadeChange;410}411 412// Finding the minimal(chain_number + reusable_offset_number) is a complicated413// algorithmic problem.414// For now, the algorithm used here is simply adjusted to handle the case for415// manually unrolling cases.416// FIXME: use a more powerful algorithm to find minimal sum of chain_number and417// reusable_offset_number for one base with multiple offsets.418bool PPCLoopInstrFormPrep::prepareBasesForCommoningChains(Bucket &CBucket) {419 // The minimal size for profitable chain commoning:420 // A1 = base + offset1421 // A2 = base + offset2 (offset2 - offset1 = X)422 // A3 = base + offset3423 // A4 = base + offset4 (offset4 - offset3 = X)424 // ======>425 // base1 = base + offset1426 // base2 = base + offset3427 // A1 = base1428 // A2 = base1 + X429 // A3 = base2430 // A4 = base2 + X431 //432 // There is benefit because of reuse of offest 'X'.433 434 assert(ChainCommonPrepMinThreshold >= 4 &&435 "Thredhold can not be smaller than 4!\n");436 if (CBucket.Elements.size() < ChainCommonPrepMinThreshold)437 return false;438 439 // We simply select the FirstOffset as the first reusable offset between each440 // chain element 1 and element 0.441 const SCEV *FirstOffset = CBucket.Elements[1].Offset;442 443 // Figure out how many times above FirstOffset is used in the chain.444 // For a success commoning chain candidate, offset difference between each445 // chain element 1 and element 0 must be also FirstOffset.446 unsigned FirstOffsetReusedCount = 1;447 448 // Figure out how many times above FirstOffset is used in the first chain.449 // Chain number is FirstOffsetReusedCount / FirstOffsetReusedCountInFirstChain450 unsigned FirstOffsetReusedCountInFirstChain = 1;451 452 unsigned EleNum = CBucket.Elements.size();453 bool SawChainSeparater = false;454 for (unsigned j = 2; j != EleNum; ++j) {455 if (SE->getMinusSCEV(CBucket.Elements[j].Offset,456 CBucket.Elements[j - 1].Offset) == FirstOffset) {457 if (!SawChainSeparater)458 FirstOffsetReusedCountInFirstChain++;459 FirstOffsetReusedCount++;460 } else461 // For now, if we meet any offset which is not FirstOffset, we assume we462 // find a new Chain.463 // This makes us miss some opportunities.464 // For example, we can common:465 //466 // {OffsetA, Offset A, OffsetB, OffsetA, OffsetA, OffsetB}467 //468 // as two chains:469 // {{OffsetA, Offset A, OffsetB}, {OffsetA, OffsetA, OffsetB}}470 // FirstOffsetReusedCount = 4; FirstOffsetReusedCountInFirstChain = 2471 //472 // But we fail to common:473 //474 // {OffsetA, OffsetB, OffsetA, OffsetA, OffsetB, OffsetA}475 // FirstOffsetReusedCount = 4; FirstOffsetReusedCountInFirstChain = 1476 477 SawChainSeparater = true;478 }479 480 // FirstOffset is not reused, skip this bucket.481 if (FirstOffsetReusedCount == 1)482 return false;483 484 unsigned ChainNum =485 FirstOffsetReusedCount / FirstOffsetReusedCountInFirstChain;486 487 // All elements are increased by FirstOffset.488 // The number of chains should be sqrt(EleNum).489 if (!SawChainSeparater)490 ChainNum = (unsigned)sqrt((double)EleNum);491 492 CBucket.ChainSize = (unsigned)(EleNum / ChainNum);493 494 // If this is not a perfect chain(eg: not all elements can be put inside495 // commoning chains.), skip now.496 if (CBucket.ChainSize * ChainNum != EleNum)497 return false;498 499 if (SawChainSeparater) {500 // Check that the offset seqs are the same for all chains.501 for (unsigned i = 1; i < CBucket.ChainSize; i++)502 for (unsigned j = 1; j < ChainNum; j++)503 if (CBucket.Elements[i].Offset !=504 SE->getMinusSCEV(CBucket.Elements[i + j * CBucket.ChainSize].Offset,505 CBucket.Elements[j * CBucket.ChainSize].Offset))506 return false;507 }508 509 for (unsigned i = 0; i < ChainNum; i++)510 CBucket.ChainBases.push_back(CBucket.Elements[i * CBucket.ChainSize]);511 512 LLVM_DEBUG(dbgs() << "Bucket has " << ChainNum << " chains.\n");513 514 return true;515}516 517bool PPCLoopInstrFormPrep::chainCommoning(Loop *L,518 SmallVector<Bucket, 16> &Buckets) {519 bool MadeChange = false;520 521 if (Buckets.empty())522 return MadeChange;523 524 SmallPtrSet<BasicBlock *, 16> BBChanged;525 526 for (auto &Bucket : Buckets) {527 if (prepareBasesForCommoningChains(Bucket))528 MadeChange |= rewriteLoadStoresForCommoningChains(L, Bucket, BBChanged);529 }530 531 if (MadeChange)532 for (auto *BB : BBChanged)533 DeleteDeadPHIs(BB);534 return MadeChange;535}536 537bool PPCLoopInstrFormPrep::rewriteLoadStoresForCommoningChains(538 Loop *L, Bucket &Bucket, SmallPtrSet<BasicBlock *, 16> &BBChanged) {539 bool MadeChange = false;540 541 assert(Bucket.Elements.size() ==542 Bucket.ChainBases.size() * Bucket.ChainSize &&543 "invalid bucket for chain commoning!\n");544 SmallPtrSet<Value *, 16> DeletedPtrs;545 546 BasicBlock *Header = L->getHeader();547 BasicBlock *LoopPredecessor = L->getLoopPredecessor();548 549 SCEVExpander SCEVE(*SE, Header->getDataLayout(),550 "loopprepare-chaincommon");551 552 for (unsigned ChainIdx = 0; ChainIdx < Bucket.ChainBases.size(); ++ChainIdx) {553 unsigned BaseElemIdx = Bucket.ChainSize * ChainIdx;554 const SCEV *BaseSCEV =555 ChainIdx ? SE->getAddExpr(Bucket.BaseSCEV,556 Bucket.Elements[BaseElemIdx].Offset)557 : Bucket.BaseSCEV;558 const SCEVAddRecExpr *BasePtrSCEV = cast<SCEVAddRecExpr>(BaseSCEV);559 560 // Make sure the base is able to expand.561 if (!SCEVE.isSafeToExpand(BasePtrSCEV->getStart()))562 return MadeChange;563 564 assert(BasePtrSCEV->isAffine() &&565 "Invalid SCEV type for the base ptr for a candidate chain!\n");566 567 std::pair<Instruction *, Instruction *> Base = rewriteForBase(568 L, BasePtrSCEV, Bucket.Elements[BaseElemIdx].Instr,569 false /* CanPreInc */, ChainCommoning, SCEVE, DeletedPtrs);570 571 if (!Base.first || !Base.second)572 return MadeChange;573 574 // Keep track of the replacement pointer values we've inserted so that we575 // don't generate more pointer values than necessary.576 SmallPtrSet<Value *, 16> NewPtrs;577 NewPtrs.insert(Base.first);578 579 for (unsigned Idx = BaseElemIdx + 1; Idx < BaseElemIdx + Bucket.ChainSize;580 ++Idx) {581 BucketElement &I = Bucket.Elements[Idx];582 Value *Ptr = getPointerOperandAndType(I.Instr);583 assert(Ptr && "No pointer operand");584 if (NewPtrs.count(Ptr))585 continue;586 587 const SCEV *OffsetSCEV =588 BaseElemIdx ? SE->getMinusSCEV(Bucket.Elements[Idx].Offset,589 Bucket.Elements[BaseElemIdx].Offset)590 : Bucket.Elements[Idx].Offset;591 592 // Make sure offset is able to expand. Only need to check one time as the593 // offsets are reused between different chains.594 if (!BaseElemIdx)595 if (!SCEVE.isSafeToExpand(OffsetSCEV))596 return false;597 598 Value *OffsetValue = SCEVE.expandCodeFor(599 OffsetSCEV, OffsetSCEV->getType(), LoopPredecessor->getTerminator());600 601 Instruction *NewPtr = rewriteForBucketElement(Base, Bucket.Elements[Idx],602 OffsetValue, DeletedPtrs);603 604 assert(NewPtr && "Wrong rewrite!\n");605 NewPtrs.insert(NewPtr);606 }607 608 ++ChainCommoningRewritten;609 }610 611 // Clear the rewriter cache, because values that are in the rewriter's cache612 // can be deleted below, causing the AssertingVH in the cache to trigger.613 SCEVE.clear();614 615 for (auto *Ptr : DeletedPtrs) {616 if (Instruction *IDel = dyn_cast<Instruction>(Ptr))617 BBChanged.insert(IDel->getParent());618 RecursivelyDeleteTriviallyDeadInstructions(Ptr);619 }620 621 MadeChange = true;622 return MadeChange;623}624 625// Rewrite the new base according to BasePtrSCEV.626// bb.loop.preheader:627// %newstart = ...628// bb.loop.body:629// %phinode = phi [ %newstart, %bb.loop.preheader ], [ %add, %bb.loop.body ]630// ...631// %add = getelementptr %phinode, %inc632//633// First returned instruciton is %phinode (or a type cast to %phinode), caller634// needs this value to rewrite other load/stores in the same chain.635// Second returned instruction is %add, caller needs this value to rewrite other636// load/stores in the same chain.637std::pair<Instruction *, Instruction *>638PPCLoopInstrFormPrep::rewriteForBase(Loop *L, const SCEVAddRecExpr *BasePtrSCEV,639 Instruction *BaseMemI, bool CanPreInc,640 PrepForm Form, SCEVExpander &SCEVE,641 SmallPtrSet<Value *, 16> &DeletedPtrs) {642 643 LLVM_DEBUG(dbgs() << "PIP: Transforming: " << *BasePtrSCEV << "\n");644 645 assert(BasePtrSCEV->getLoop() == L && "AddRec for the wrong loop?");646 647 Value *BasePtr = getPointerOperandAndType(BaseMemI);648 assert(BasePtr && "No pointer operand");649 650 Type *I8Ty = Type::getInt8Ty(BaseMemI->getParent()->getContext());651 Type *I8PtrTy =652 PointerType::get(BaseMemI->getParent()->getContext(),653 BasePtr->getType()->getPointerAddressSpace());654 655 bool IsConstantInc = false;656 const SCEV *BasePtrIncSCEV = BasePtrSCEV->getStepRecurrence(*SE);657 Value *IncNode = getNodeForInc(L, BaseMemI, BasePtrIncSCEV);658 659 const SCEVConstant *BasePtrIncConstantSCEV =660 dyn_cast<SCEVConstant>(BasePtrIncSCEV);661 if (BasePtrIncConstantSCEV)662 IsConstantInc = true;663 664 // No valid representation for the increment.665 if (!IncNode) {666 LLVM_DEBUG(dbgs() << "Loop Increasement can not be represented!\n");667 return std::make_pair(nullptr, nullptr);668 }669 670 if (Form == UpdateForm && !IsConstantInc && !EnableUpdateFormForNonConstInc) {671 LLVM_DEBUG(672 dbgs()673 << "Update form prepare for non-const increment is not enabled!\n");674 return std::make_pair(nullptr, nullptr);675 }676 677 const SCEV *BasePtrStartSCEV = nullptr;678 if (CanPreInc) {679 assert(SE->isLoopInvariant(BasePtrIncSCEV, L) &&680 "Increment is not loop invariant!\n");681 BasePtrStartSCEV = SE->getMinusSCEV(BasePtrSCEV->getStart(),682 IsConstantInc ? BasePtrIncConstantSCEV683 : BasePtrIncSCEV);684 } else685 BasePtrStartSCEV = BasePtrSCEV->getStart();686 687 if (alreadyPrepared(L, BaseMemI, BasePtrStartSCEV, BasePtrIncSCEV, Form)) {688 LLVM_DEBUG(dbgs() << "Instruction form is already prepared!\n");689 return std::make_pair(nullptr, nullptr);690 }691 692 LLVM_DEBUG(dbgs() << "PIP: New start is: " << *BasePtrStartSCEV << "\n");693 694 BasicBlock *Header = L->getHeader();695 unsigned HeaderLoopPredCount = pred_size(Header);696 BasicBlock *LoopPredecessor = L->getLoopPredecessor();697 698 PHINode *NewPHI = PHINode::Create(I8PtrTy, HeaderLoopPredCount,699 getInstrName(BaseMemI, PHINodeNameSuffix));700 NewPHI->insertBefore(Header->getFirstNonPHIIt());701 702 Value *BasePtrStart = SCEVE.expandCodeFor(BasePtrStartSCEV, I8PtrTy,703 LoopPredecessor->getTerminator());704 705 // Note that LoopPredecessor might occur in the predecessor list multiple706 // times, and we need to add it the right number of times.707 for (auto *PI : predecessors(Header)) {708 if (PI != LoopPredecessor)709 continue;710 711 NewPHI->addIncoming(BasePtrStart, LoopPredecessor);712 }713 714 Instruction *PtrInc = nullptr;715 Instruction *NewBasePtr = nullptr;716 if (CanPreInc) {717 BasicBlock::iterator InsPoint = Header->getFirstInsertionPt();718 PtrInc = GetElementPtrInst::Create(719 I8Ty, NewPHI, IncNode, getInstrName(BaseMemI, GEPNodeIncNameSuffix),720 InsPoint);721 cast<GetElementPtrInst>(PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr));722 for (auto *PI : predecessors(Header)) {723 if (PI == LoopPredecessor)724 continue;725 726 NewPHI->addIncoming(PtrInc, PI);727 }728 if (PtrInc->getType() != BasePtr->getType())729 NewBasePtr =730 new BitCastInst(PtrInc, BasePtr->getType(),731 getInstrName(PtrInc, CastNodeNameSuffix), InsPoint);732 else733 NewBasePtr = PtrInc;734 } else {735 // Note that LoopPredecessor might occur in the predecessor list multiple736 // times, and we need to make sure no more incoming value for them in PHI.737 for (auto *PI : predecessors(Header)) {738 if (PI == LoopPredecessor)739 continue;740 741 // For the latch predecessor, we need to insert a GEP just before the742 // terminator to increase the address.743 BasicBlock *BB = PI;744 BasicBlock::iterator InsPoint = BB->getTerminator()->getIterator();745 PtrInc = GetElementPtrInst::Create(746 I8Ty, NewPHI, IncNode, getInstrName(BaseMemI, GEPNodeIncNameSuffix),747 InsPoint);748 cast<GetElementPtrInst>(PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr));749 750 NewPHI->addIncoming(PtrInc, PI);751 }752 PtrInc = NewPHI;753 if (NewPHI->getType() != BasePtr->getType())754 NewBasePtr = new BitCastInst(NewPHI, BasePtr->getType(),755 getInstrName(NewPHI, CastNodeNameSuffix),756 Header->getFirstInsertionPt());757 else758 NewBasePtr = NewPHI;759 }760 761 BasePtr->replaceAllUsesWith(NewBasePtr);762 763 DeletedPtrs.insert(BasePtr);764 765 return std::make_pair(NewBasePtr, PtrInc);766}767 768Instruction *PPCLoopInstrFormPrep::rewriteForBucketElement(769 std::pair<Instruction *, Instruction *> Base, const BucketElement &Element,770 Value *OffToBase, SmallPtrSet<Value *, 16> &DeletedPtrs) {771 Instruction *NewBasePtr = Base.first;772 Instruction *PtrInc = Base.second;773 assert((NewBasePtr && PtrInc) && "base does not exist!\n");774 775 Type *I8Ty = Type::getInt8Ty(PtrInc->getParent()->getContext());776 777 Value *Ptr = getPointerOperandAndType(Element.Instr);778 assert(Ptr && "No pointer operand");779 780 Instruction *RealNewPtr;781 if (!Element.Offset ||782 (isa<SCEVConstant>(Element.Offset) &&783 cast<SCEVConstant>(Element.Offset)->getValue()->isZero())) {784 RealNewPtr = NewBasePtr;785 } else {786 std::optional<BasicBlock::iterator> PtrIP = std::nullopt;787 if (Instruction *I = dyn_cast<Instruction>(Ptr))788 PtrIP = I->getIterator();789 790 if (PtrIP && isa<Instruction>(NewBasePtr) &&791 cast<Instruction>(NewBasePtr)->getParent() == (*PtrIP)->getParent())792 PtrIP = std::nullopt;793 else if (PtrIP && isa<PHINode>(*PtrIP))794 PtrIP = (*PtrIP)->getParent()->getFirstInsertionPt();795 else if (!PtrIP)796 PtrIP = Element.Instr->getIterator();797 798 assert(OffToBase && "There should be an offset for non base element!\n");799 GetElementPtrInst *NewPtr = GetElementPtrInst::Create(800 I8Ty, PtrInc, OffToBase,801 getInstrName(Element.Instr, GEPNodeOffNameSuffix));802 if (PtrIP)803 NewPtr->insertBefore(*(*PtrIP)->getParent(), *PtrIP);804 else805 NewPtr->insertAfter(cast<Instruction>(PtrInc));806 NewPtr->setIsInBounds(IsPtrInBounds(Ptr));807 RealNewPtr = NewPtr;808 }809 810 Instruction *ReplNewPtr;811 if (Ptr->getType() != RealNewPtr->getType()) {812 ReplNewPtr = new BitCastInst(RealNewPtr, Ptr->getType(),813 getInstrName(Ptr, CastNodeNameSuffix));814 ReplNewPtr->insertAfter(RealNewPtr);815 } else816 ReplNewPtr = RealNewPtr;817 818 Ptr->replaceAllUsesWith(ReplNewPtr);819 DeletedPtrs.insert(Ptr);820 821 return ReplNewPtr;822}823 824void PPCLoopInstrFormPrep::addOneCandidate(825 Instruction *MemI, const SCEV *LSCEV, SmallVector<Bucket, 16> &Buckets,826 std::function<bool(const SCEV *)> isValidDiff, unsigned MaxCandidateNum) {827 assert((MemI && getPointerOperandAndType(MemI)) &&828 "Candidate should be a memory instruction.");829 assert(LSCEV && "Invalid SCEV for Ptr value.");830 831 bool FoundBucket = false;832 for (auto &B : Buckets) {833 if (cast<SCEVAddRecExpr>(B.BaseSCEV)->getStepRecurrence(*SE) !=834 cast<SCEVAddRecExpr>(LSCEV)->getStepRecurrence(*SE))835 continue;836 const SCEV *Diff = SE->getMinusSCEV(LSCEV, B.BaseSCEV);837 if (isValidDiff(Diff)) {838 B.Elements.push_back(BucketElement(Diff, MemI));839 FoundBucket = true;840 break;841 }842 }843 844 if (!FoundBucket) {845 if (Buckets.size() == MaxCandidateNum) {846 LLVM_DEBUG(dbgs() << "Can not prepare more chains, reach maximum limit "847 << MaxCandidateNum << "\n");848 return;849 }850 Buckets.push_back(Bucket(LSCEV, MemI));851 }852}853 854SmallVector<Bucket, 16> PPCLoopInstrFormPrep::collectCandidates(855 Loop *L,856 std::function<bool(const Instruction *, Value *, const Type *)>857 isValidCandidate,858 std::function<bool(const SCEV *)> isValidDiff, unsigned MaxCandidateNum) {859 SmallVector<Bucket, 16> Buckets;860 861 for (const auto &BB : L->blocks())862 for (auto &J : *BB) {863 Value *PtrValue = nullptr;864 Type *PointerElementType = nullptr;865 PtrValue = getPointerOperandAndType(&J, &PointerElementType);866 867 if (!PtrValue)868 continue;869 870 if (PtrValue->getType()->getPointerAddressSpace())871 continue;872 873 if (L->isLoopInvariant(PtrValue))874 continue;875 876 const SCEV *LSCEV = SE->getSCEVAtScope(PtrValue, L);877 const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(LSCEV);878 if (!LARSCEV || LARSCEV->getLoop() != L)879 continue;880 881 // Mark that we have candidates for preparing.882 HasCandidateForPrepare = true;883 884 if (isValidCandidate(&J, PtrValue, PointerElementType))885 addOneCandidate(&J, LSCEV, Buckets, isValidDiff, MaxCandidateNum);886 }887 return Buckets;888}889 890bool PPCLoopInstrFormPrep::prepareBaseForDispFormChain(Bucket &BucketChain,891 PrepForm Form) {892 // RemainderOffsetInfo details:893 // key: value of (Offset urem DispConstraint). For DSForm, it can894 // be [0, 4).895 // first of pair: the index of first BucketElement whose remainder is equal896 // to key. For key 0, this value must be 0.897 // second of pair: number of load/stores with the same remainder.898 DenseMap<unsigned, std::pair<unsigned, unsigned>> RemainderOffsetInfo;899 900 for (unsigned j = 0, je = BucketChain.Elements.size(); j != je; ++j) {901 if (!BucketChain.Elements[j].Offset)902 RemainderOffsetInfo[0] = std::make_pair(0, 1);903 else {904 unsigned Remainder = cast<SCEVConstant>(BucketChain.Elements[j].Offset)905 ->getAPInt()906 .urem(Form);907 if (!RemainderOffsetInfo.contains(Remainder))908 RemainderOffsetInfo[Remainder] = std::make_pair(j, 1);909 else910 RemainderOffsetInfo[Remainder].second++;911 }912 }913 // Currently we choose the most profitable base as the one which has the max914 // number of load/store with same remainder.915 // FIXME: adjust the base selection strategy according to load/store offset916 // distribution.917 // For example, if we have one candidate chain for DS form preparation, which918 // contains following load/stores with different remainders:919 // 1: 10 load/store whose remainder is 1;920 // 2: 9 load/store whose remainder is 2;921 // 3: 1 for remainder 3 and 0 for remainder 0;922 // Now we will choose the first load/store whose remainder is 1 as base and923 // adjust all other load/stores according to new base, so we will get 10 DS924 // form and 10 X form.925 // But we should be more clever, for this case we could use two bases, one for926 // remainder 1 and the other for remainder 2, thus we could get 19 DS form and927 // 1 X form.928 unsigned MaxCountRemainder = 0;929 for (unsigned j = 0; j < (unsigned)Form; j++)930 if (auto It = RemainderOffsetInfo.find(j);931 It != RemainderOffsetInfo.end() &&932 It->second.second > RemainderOffsetInfo[MaxCountRemainder].second)933 MaxCountRemainder = j;934 935 // Abort when there are too few insts with common base.936 if (RemainderOffsetInfo[MaxCountRemainder].second < DispFormPrepMinThreshold)937 return false;938 939 // If the first value is most profitable, no needed to adjust BucketChain940 // elements as they are substracted the first value when collecting.941 if (MaxCountRemainder == 0)942 return true;943 944 // Adjust load/store to the new chosen base.945 const SCEV *Offset =946 BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first].Offset;947 BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset);948 for (auto &E : BucketChain.Elements) {949 if (E.Offset)950 E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(E.Offset, Offset));951 else952 E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(Offset));953 }954 955 std::swap(BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first],956 BucketChain.Elements[0]);957 return true;958}959 960// FIXME: implement a more clever base choosing policy.961// Currently we always choose an exist load/store offset. This maybe lead to962// suboptimal code sequences. For example, for one DS chain with offsets963// {-32769, 2003, 2007, 2011}, we choose -32769 as base offset, and left disp964// for load/stores are {0, 34772, 34776, 34780}. Though each offset now is a965// multipler of 4, it cannot be represented by sint16.966bool PPCLoopInstrFormPrep::prepareBaseForUpdateFormChain(Bucket &BucketChain) {967 // We have a choice now of which instruction's memory operand we use as the968 // base for the generated PHI. Always picking the first instruction in each969 // bucket does not work well, specifically because that instruction might970 // be a prefetch (and there are no pre-increment dcbt variants). Otherwise,971 // the choice is somewhat arbitrary, because the backend will happily972 // generate direct offsets from both the pre-incremented and973 // post-incremented pointer values. Thus, we'll pick the first non-prefetch974 // instruction in each bucket, and adjust the recurrence and other offsets975 // accordingly.976 for (int j = 0, je = BucketChain.Elements.size(); j != je; ++j) {977 if (auto *II = dyn_cast<IntrinsicInst>(BucketChain.Elements[j].Instr))978 if (II->getIntrinsicID() == Intrinsic::prefetch)979 continue;980 981 // If we'd otherwise pick the first element anyway, there's nothing to do.982 if (j == 0)983 break;984 985 // If our chosen element has no offset from the base pointer, there's986 // nothing to do.987 if (!BucketChain.Elements[j].Offset ||988 cast<SCEVConstant>(BucketChain.Elements[j].Offset)->isZero())989 break;990 991 const SCEV *Offset = BucketChain.Elements[j].Offset;992 BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset);993 for (auto &E : BucketChain.Elements) {994 if (E.Offset)995 E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(E.Offset, Offset));996 else997 E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(Offset));998 }999 1000 std::swap(BucketChain.Elements[j], BucketChain.Elements[0]);1001 break;1002 }1003 return true;1004}1005 1006bool PPCLoopInstrFormPrep::rewriteLoadStores(1007 Loop *L, Bucket &BucketChain, SmallPtrSet<BasicBlock *, 16> &BBChanged,1008 PrepForm Form) {1009 bool MadeChange = false;1010 1011 const SCEVAddRecExpr *BasePtrSCEV =1012 cast<SCEVAddRecExpr>(BucketChain.BaseSCEV);1013 if (!BasePtrSCEV->isAffine())1014 return MadeChange;1015 1016 BasicBlock *Header = L->getHeader();1017 SCEVExpander SCEVE(*SE, Header->getDataLayout(),1018 "loopprepare-formrewrite");1019 if (!SCEVE.isSafeToExpand(BasePtrSCEV->getStart()))1020 return MadeChange;1021 1022 SmallPtrSet<Value *, 16> DeletedPtrs;1023 1024 // For some DS form load/store instructions, it can also be an update form,1025 // if the stride is constant and is a multipler of 4. Use update form if1026 // prefer it.1027 bool CanPreInc = (Form == UpdateForm ||1028 ((Form == DSForm) &&1029 isa<SCEVConstant>(BasePtrSCEV->getStepRecurrence(*SE)) &&1030 !cast<SCEVConstant>(BasePtrSCEV->getStepRecurrence(*SE))1031 ->getAPInt()1032 .urem(4) &&1033 PreferUpdateForm));1034 1035 std::pair<Instruction *, Instruction *> Base =1036 rewriteForBase(L, BasePtrSCEV, BucketChain.Elements.begin()->Instr,1037 CanPreInc, Form, SCEVE, DeletedPtrs);1038 1039 if (!Base.first || !Base.second)1040 return MadeChange;1041 1042 // Keep track of the replacement pointer values we've inserted so that we1043 // don't generate more pointer values than necessary.1044 SmallPtrSet<Value *, 16> NewPtrs;1045 NewPtrs.insert(Base.first);1046 1047 for (const BucketElement &BE : llvm::drop_begin(BucketChain.Elements)) {1048 Value *Ptr = getPointerOperandAndType(BE.Instr);1049 assert(Ptr && "No pointer operand");1050 if (NewPtrs.count(Ptr))1051 continue;1052 1053 Instruction *NewPtr = rewriteForBucketElement(1054 Base, BE,1055 BE.Offset ? cast<SCEVConstant>(BE.Offset)->getValue() : nullptr,1056 DeletedPtrs);1057 assert(NewPtr && "wrong rewrite!\n");1058 NewPtrs.insert(NewPtr);1059 }1060 1061 // Clear the rewriter cache, because values that are in the rewriter's cache1062 // can be deleted below, causing the AssertingVH in the cache to trigger.1063 SCEVE.clear();1064 1065 for (auto *Ptr : DeletedPtrs) {1066 if (Instruction *IDel = dyn_cast<Instruction>(Ptr))1067 BBChanged.insert(IDel->getParent());1068 RecursivelyDeleteTriviallyDeadInstructions(Ptr);1069 }1070 1071 MadeChange = true;1072 1073 SuccPrepCount++;1074 1075 if (Form == DSForm && !CanPreInc)1076 DSFormChainRewritten++;1077 else if (Form == DQForm)1078 DQFormChainRewritten++;1079 else if (Form == UpdateForm || (Form == DSForm && CanPreInc))1080 UpdFormChainRewritten++;1081 1082 return MadeChange;1083}1084 1085bool PPCLoopInstrFormPrep::updateFormPrep(Loop *L,1086 SmallVector<Bucket, 16> &Buckets) {1087 bool MadeChange = false;1088 if (Buckets.empty())1089 return MadeChange;1090 SmallPtrSet<BasicBlock *, 16> BBChanged;1091 for (auto &Bucket : Buckets)1092 // The base address of each bucket is transformed into a phi and the others1093 // are rewritten based on new base.1094 if (prepareBaseForUpdateFormChain(Bucket))1095 MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, UpdateForm);1096 1097 if (MadeChange)1098 for (auto *BB : BBChanged)1099 DeleteDeadPHIs(BB);1100 return MadeChange;1101}1102 1103bool PPCLoopInstrFormPrep::dispFormPrep(Loop *L,1104 SmallVector<Bucket, 16> &Buckets,1105 PrepForm Form) {1106 bool MadeChange = false;1107 1108 if (Buckets.empty())1109 return MadeChange;1110 1111 SmallPtrSet<BasicBlock *, 16> BBChanged;1112 for (auto &Bucket : Buckets) {1113 if (Bucket.Elements.size() < DispFormPrepMinThreshold)1114 continue;1115 if (prepareBaseForDispFormChain(Bucket, Form))1116 MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, Form);1117 }1118 1119 if (MadeChange)1120 for (auto *BB : BBChanged)1121 DeleteDeadPHIs(BB);1122 return MadeChange;1123}1124 1125// Find the loop invariant increment node for SCEV BasePtrIncSCEV.1126// bb.loop.preheader:1127// %start = ...1128// bb.loop.body:1129// %phinode = phi [ %start, %bb.loop.preheader ], [ %add, %bb.loop.body ]1130// ...1131// %add = add %phinode, %inc ; %inc is what we want to get.1132//1133Value *PPCLoopInstrFormPrep::getNodeForInc(Loop *L, Instruction *MemI,1134 const SCEV *BasePtrIncSCEV) {1135 // If the increment is a constant, no definition is needed.1136 // Return the value directly.1137 if (isa<SCEVConstant>(BasePtrIncSCEV))1138 return cast<SCEVConstant>(BasePtrIncSCEV)->getValue();1139 1140 if (!SE->isLoopInvariant(BasePtrIncSCEV, L))1141 return nullptr;1142 1143 BasicBlock *BB = MemI->getParent();1144 if (!BB)1145 return nullptr;1146 1147 BasicBlock *LatchBB = L->getLoopLatch();1148 1149 if (!LatchBB)1150 return nullptr;1151 1152 // Run through the PHIs and check their operands to find valid representation1153 // for the increment SCEV.1154 iterator_range<BasicBlock::phi_iterator> PHIIter = BB->phis();1155 for (auto &CurrentPHI : PHIIter) {1156 PHINode *CurrentPHINode = dyn_cast<PHINode>(&CurrentPHI);1157 if (!CurrentPHINode)1158 continue;1159 1160 if (!SE->isSCEVable(CurrentPHINode->getType()))1161 continue;1162 1163 const SCEV *PHISCEV = SE->getSCEVAtScope(CurrentPHINode, L);1164 1165 const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast<SCEVAddRecExpr>(PHISCEV);1166 if (!PHIBasePtrSCEV)1167 continue;1168 1169 const SCEV *PHIBasePtrIncSCEV = PHIBasePtrSCEV->getStepRecurrence(*SE);1170 1171 if (!PHIBasePtrIncSCEV || (PHIBasePtrIncSCEV != BasePtrIncSCEV))1172 continue;1173 1174 // Get the incoming value from the loop latch and check if the value has1175 // the add form with the required increment.1176 if (CurrentPHINode->getBasicBlockIndex(LatchBB) < 0)1177 continue;1178 if (Instruction *I = dyn_cast<Instruction>(1179 CurrentPHINode->getIncomingValueForBlock(LatchBB))) {1180 Value *StrippedBaseI = I;1181 while (BitCastInst *BC = dyn_cast<BitCastInst>(StrippedBaseI))1182 StrippedBaseI = BC->getOperand(0);1183 1184 Instruction *StrippedI = dyn_cast<Instruction>(StrippedBaseI);1185 if (!StrippedI)1186 continue;1187 1188 // LSR pass may add a getelementptr instruction to do the loop increment,1189 // also search in that getelementptr instruction.1190 if (StrippedI->getOpcode() == Instruction::Add ||1191 (StrippedI->getOpcode() == Instruction::GetElementPtr &&1192 StrippedI->getNumOperands() == 2)) {1193 if (SE->getSCEVAtScope(StrippedI->getOperand(0), L) == BasePtrIncSCEV)1194 return StrippedI->getOperand(0);1195 if (SE->getSCEVAtScope(StrippedI->getOperand(1), L) == BasePtrIncSCEV)1196 return StrippedI->getOperand(1);1197 }1198 }1199 }1200 return nullptr;1201}1202 1203// In order to prepare for the preferred instruction form, a PHI is added.1204// This function will check to see if that PHI already exists and will return1205// true if it found an existing PHI with the matched start and increment as the1206// one we wanted to create.1207bool PPCLoopInstrFormPrep::alreadyPrepared(Loop *L, Instruction *MemI,1208 const SCEV *BasePtrStartSCEV,1209 const SCEV *BasePtrIncSCEV,1210 PrepForm Form) {1211 BasicBlock *BB = MemI->getParent();1212 if (!BB)1213 return false;1214 1215 BasicBlock *PredBB = L->getLoopPredecessor();1216 BasicBlock *LatchBB = L->getLoopLatch();1217 1218 if (!PredBB || !LatchBB)1219 return false;1220 1221 // Run through the PHIs and see if we have some that looks like a preparation1222 iterator_range<BasicBlock::phi_iterator> PHIIter = BB->phis();1223 for (auto & CurrentPHI : PHIIter) {1224 PHINode *CurrentPHINode = dyn_cast<PHINode>(&CurrentPHI);1225 if (!CurrentPHINode)1226 continue;1227 1228 if (!SE->isSCEVable(CurrentPHINode->getType()))1229 continue;1230 1231 const SCEV *PHISCEV = SE->getSCEVAtScope(CurrentPHINode, L);1232 1233 const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast<SCEVAddRecExpr>(PHISCEV);1234 if (!PHIBasePtrSCEV)1235 continue;1236 1237 const SCEVConstant *PHIBasePtrIncSCEV =1238 dyn_cast<SCEVConstant>(PHIBasePtrSCEV->getStepRecurrence(*SE));1239 if (!PHIBasePtrIncSCEV)1240 continue;1241 1242 if (CurrentPHINode->getNumIncomingValues() == 2) {1243 if ((CurrentPHINode->getIncomingBlock(0) == LatchBB &&1244 CurrentPHINode->getIncomingBlock(1) == PredBB) ||1245 (CurrentPHINode->getIncomingBlock(1) == LatchBB &&1246 CurrentPHINode->getIncomingBlock(0) == PredBB)) {1247 if (PHIBasePtrIncSCEV == BasePtrIncSCEV) {1248 // The existing PHI (CurrentPHINode) has the same start and increment1249 // as the PHI that we wanted to create.1250 if ((Form == UpdateForm || Form == ChainCommoning ) &&1251 PHIBasePtrSCEV->getStart() == BasePtrStartSCEV) {1252 ++PHINodeAlreadyExistsUpdate;1253 return true;1254 }1255 if (Form == DSForm || Form == DQForm) {1256 const SCEVConstant *Diff = dyn_cast<SCEVConstant>(1257 SE->getMinusSCEV(PHIBasePtrSCEV->getStart(), BasePtrStartSCEV));1258 if (Diff && !Diff->getAPInt().urem(Form)) {1259 if (Form == DSForm)1260 ++PHINodeAlreadyExistsDS;1261 else1262 ++PHINodeAlreadyExistsDQ;1263 return true;1264 }1265 }1266 }1267 }1268 }1269 }1270 return false;1271}1272 1273bool PPCLoopInstrFormPrep::runOnLoop(Loop *L) {1274 bool MadeChange = false;1275 1276 // Only prep. the inner-most loop1277 if (!L->isInnermost())1278 return MadeChange;1279 1280 // Return if already done enough preparation.1281 if (SuccPrepCount >= MaxVarsPrep)1282 return MadeChange;1283 1284 LLVM_DEBUG(dbgs() << "PIP: Examining: " << *L << "\n");1285 1286 BasicBlock *LoopPredecessor = L->getLoopPredecessor();1287 // If there is no loop predecessor, or the loop predecessor's terminator1288 // returns a value (which might contribute to determining the loop's1289 // iteration space), insert a new preheader for the loop.1290 if (!LoopPredecessor ||1291 !LoopPredecessor->getTerminator()->getType()->isVoidTy()) {1292 LoopPredecessor = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA);1293 if (LoopPredecessor)1294 MadeChange = true;1295 }1296 if (!LoopPredecessor) {1297 LLVM_DEBUG(dbgs() << "PIP fails since no predecessor for current loop.\n");1298 return MadeChange;1299 }1300 // Check if a load/store has update form. This lambda is used by function1301 // collectCandidates which can collect candidates for types defined by lambda.1302 auto isUpdateFormCandidate = [&](const Instruction *I, Value *PtrValue,1303 const Type *PointerElementType) {1304 assert((PtrValue && I) && "Invalid parameter!");1305 // There are no update forms for Altivec vector load/stores.1306 if (ST && ST->hasAltivec() && PointerElementType->isVectorTy())1307 return false;1308 // There are no update forms for P10 lxvp/stxvp intrinsic.1309 auto *II = dyn_cast<IntrinsicInst>(I);1310 if (II && ((II->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp) ||1311 II->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp))1312 return false;1313 // See getPreIndexedAddressParts, the displacement for LDU/STDU has to1314 // be 4's multiple (DS-form). For i64 loads/stores when the displacement1315 // fits in a 16-bit signed field but isn't a multiple of 4, it will be1316 // useless and possible to break some original well-form addressing mode1317 // to make this pre-inc prep for it.1318 if (PointerElementType->isIntegerTy(64)) {1319 const SCEV *LSCEV = SE->getSCEVAtScope(PtrValue, L);1320 const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(LSCEV);1321 if (!LARSCEV || LARSCEV->getLoop() != L)1322 return false;1323 if (const SCEVConstant *StepConst =1324 dyn_cast<SCEVConstant>(LARSCEV->getStepRecurrence(*SE))) {1325 const APInt &ConstInt = StepConst->getValue()->getValue();1326 if (ConstInt.isSignedIntN(16) && ConstInt.srem(4) != 0)1327 return false;1328 }1329 }1330 return true;1331 };1332 1333 // Check if a load/store has DS form.1334 auto isDSFormCandidate = [](const Instruction *I, Value *PtrValue,1335 const Type *PointerElementType) {1336 assert((PtrValue && I) && "Invalid parameter!");1337 if (isa<IntrinsicInst>(I))1338 return false;1339 return (PointerElementType->isIntegerTy(64)) ||1340 (PointerElementType->isFloatTy()) ||1341 (PointerElementType->isDoubleTy()) ||1342 (PointerElementType->isIntegerTy(32) &&1343 llvm::any_of(I->users(),1344 [](const User *U) { return isa<SExtInst>(U); }));1345 };1346 1347 // Check if a load/store has DQ form.1348 auto isDQFormCandidate = [&](const Instruction *I, Value *PtrValue,1349 const Type *PointerElementType) {1350 assert((PtrValue && I) && "Invalid parameter!");1351 // Check if it is a P10 lxvp/stxvp intrinsic.1352 auto *II = dyn_cast<IntrinsicInst>(I);1353 if (II)1354 return II->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp ||1355 II->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp;1356 // Check if it is a P9 vector load/store.1357 return ST && ST->hasP9Vector() && (PointerElementType->isVectorTy());1358 };1359 1360 // Check if a load/store is candidate for chain commoning.1361 // If the SCEV is only with one ptr operand in its start, we can use that1362 // start as a chain separator. Mark this load/store as a candidate.1363 auto isChainCommoningCandidate = [&](const Instruction *I, Value *PtrValue,1364 const Type *PointerElementType) {1365 const SCEVAddRecExpr *ARSCEV =1366 cast<SCEVAddRecExpr>(SE->getSCEVAtScope(PtrValue, L));1367 if (!ARSCEV)1368 return false;1369 1370 if (!ARSCEV->isAffine())1371 return false;1372 1373 const SCEV *Start = ARSCEV->getStart();1374 1375 // A single pointer. We can treat it as offset 0.1376 if (isa<SCEVUnknown>(Start) && Start->getType()->isPointerTy())1377 return true;1378 1379 const SCEVAddExpr *ASCEV = dyn_cast<SCEVAddExpr>(Start);1380 1381 // We need a SCEVAddExpr to include both base and offset.1382 if (!ASCEV)1383 return false;1384 1385 // Make sure there is only one pointer operand(base) and all other operands1386 // are integer type.1387 bool SawPointer = false;1388 for (const SCEV *Op : ASCEV->operands()) {1389 if (Op->getType()->isPointerTy()) {1390 if (SawPointer)1391 return false;1392 SawPointer = true;1393 } else if (!Op->getType()->isIntegerTy())1394 return false;1395 }1396 1397 return SawPointer;1398 };1399 1400 // Check if the diff is a constant type. This is used for update/DS/DQ form1401 // preparation.1402 auto isValidConstantDiff = [](const SCEV *Diff) {1403 return dyn_cast<SCEVConstant>(Diff) != nullptr;1404 };1405 1406 // Make sure the diff between the base and new candidate is required type.1407 // This is used for chain commoning preparation.1408 auto isValidChainCommoningDiff = [](const SCEV *Diff) {1409 assert(Diff && "Invalid Diff!\n");1410 1411 // Don't mess up previous dform prepare.1412 if (isa<SCEVConstant>(Diff))1413 return false;1414 1415 // A single integer type offset.1416 if (isa<SCEVUnknown>(Diff) && Diff->getType()->isIntegerTy())1417 return true;1418 1419 const SCEVNAryExpr *ADiff = dyn_cast<SCEVNAryExpr>(Diff);1420 if (!ADiff)1421 return false;1422 1423 for (const SCEV *Op : ADiff->operands())1424 if (!Op->getType()->isIntegerTy())1425 return false;1426 1427 return true;1428 };1429 1430 HasCandidateForPrepare = false;1431 1432 LLVM_DEBUG(dbgs() << "Start to prepare for update form.\n");1433 // Collect buckets of comparable addresses used by loads and stores for update1434 // form.1435 SmallVector<Bucket, 16> UpdateFormBuckets = collectCandidates(1436 L, isUpdateFormCandidate, isValidConstantDiff, MaxVarsUpdateForm);1437 1438 // Prepare for update form.1439 if (!UpdateFormBuckets.empty())1440 MadeChange |= updateFormPrep(L, UpdateFormBuckets);1441 else if (!HasCandidateForPrepare) {1442 LLVM_DEBUG(1443 dbgs()1444 << "No prepare candidates found, stop praparation for current loop!\n");1445 // If no candidate for preparing, return early.1446 return MadeChange;1447 }1448 1449 LLVM_DEBUG(dbgs() << "Start to prepare for DS form.\n");1450 // Collect buckets of comparable addresses used by loads and stores for DS1451 // form.1452 SmallVector<Bucket, 16> DSFormBuckets = collectCandidates(1453 L, isDSFormCandidate, isValidConstantDiff, MaxVarsDSForm);1454 1455 // Prepare for DS form.1456 if (!DSFormBuckets.empty())1457 MadeChange |= dispFormPrep(L, DSFormBuckets, DSForm);1458 1459 LLVM_DEBUG(dbgs() << "Start to prepare for DQ form.\n");1460 // Collect buckets of comparable addresses used by loads and stores for DQ1461 // form.1462 SmallVector<Bucket, 16> DQFormBuckets = collectCandidates(1463 L, isDQFormCandidate, isValidConstantDiff, MaxVarsDQForm);1464 1465 // Prepare for DQ form.1466 if (!DQFormBuckets.empty())1467 MadeChange |= dispFormPrep(L, DQFormBuckets, DQForm);1468 1469 // Collect buckets of comparable addresses used by loads and stores for chain1470 // commoning. With chain commoning, we reuse offsets between the chains, so1471 // the register pressure will be reduced.1472 if (!EnableChainCommoning) {1473 LLVM_DEBUG(dbgs() << "Chain commoning is not enabled.\n");1474 return MadeChange;1475 }1476 1477 LLVM_DEBUG(dbgs() << "Start to prepare for chain commoning.\n");1478 SmallVector<Bucket, 16> Buckets =1479 collectCandidates(L, isChainCommoningCandidate, isValidChainCommoningDiff,1480 MaxVarsChainCommon);1481 1482 // Prepare for chain commoning.1483 if (!Buckets.empty())1484 MadeChange |= chainCommoning(L, Buckets);1485 1486 return MadeChange;1487}1488