1 //===------ PPCLoopInstrFormPrep.cpp - Loop Instr Form Prep Pass ----------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements a pass to prepare loops for ppc preferred addressing 10 // modes, leveraging different instruction form. (eg: DS/DQ form, D/DS form with 11 // update) 12 // Additional PHIs are created for loop induction variables used by load/store 13 // instructions so that preferred addressing modes can be used. 14 // 15 // 1: DS/DQ form preparation, prepare the load/store instructions so that they 16 // can satisfy the DS/DQ form displacement requirements. 17 // Generically, this means transforming loops like this: 18 // for (int i = 0; i < n; ++i) { 19 // unsigned long x1 = *(unsigned long *)(p + i + 5); 20 // unsigned long x2 = *(unsigned long *)(p + i + 9); 21 // } 22 // 23 // to look like this: 24 // 25 // unsigned NewP = p + 5; 26 // for (int i = 0; i < n; ++i) { 27 // unsigned long x1 = *(unsigned long *)(i + NewP); 28 // unsigned long x2 = *(unsigned long *)(i + NewP + 4); 29 // } 30 // 31 // 2: D/DS form with update preparation, prepare the load/store instructions so 32 // that we can use update form to do pre-increment. 33 // Generically, this means transforming loops like this: 34 // for (int i = 0; i < n; ++i) 35 // array[i] = c; 36 // 37 // to look like this: 38 // 39 // T *p = array[-1]; 40 // for (int i = 0; i < n; ++i) 41 // *++p = c; 42 //===----------------------------------------------------------------------===// 43 44 #define DEBUG_TYPE "ppc-loop-instr-form-prep" 45 46 #include "PPC.h" 47 #include "PPCSubtarget.h" 48 #include "PPCTargetMachine.h" 49 #include "llvm/ADT/DepthFirstIterator.h" 50 #include "llvm/ADT/SmallPtrSet.h" 51 #include "llvm/ADT/SmallSet.h" 52 #include "llvm/ADT/SmallVector.h" 53 #include "llvm/ADT/Statistic.h" 54 #include "llvm/Analysis/LoopInfo.h" 55 #include "llvm/Analysis/ScalarEvolution.h" 56 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 57 #include "llvm/IR/BasicBlock.h" 58 #include "llvm/IR/CFG.h" 59 #include "llvm/IR/Dominators.h" 60 #include "llvm/IR/Instruction.h" 61 #include "llvm/IR/Instructions.h" 62 #include "llvm/IR/IntrinsicInst.h" 63 #include "llvm/IR/Module.h" 64 #include "llvm/IR/Type.h" 65 #include "llvm/IR/Value.h" 66 #include "llvm/InitializePasses.h" 67 #include "llvm/Pass.h" 68 #include "llvm/Support/Casting.h" 69 #include "llvm/Support/CommandLine.h" 70 #include "llvm/Support/Debug.h" 71 #include "llvm/Transforms/Scalar.h" 72 #include "llvm/Transforms/Utils.h" 73 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 74 #include "llvm/Transforms/Utils/Local.h" 75 #include "llvm/Transforms/Utils/LoopUtils.h" 76 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" 77 #include <cassert> 78 #include <iterator> 79 #include <utility> 80 81 using namespace llvm; 82 83 // By default, we limit this to creating 16 common bases out of loops per 84 // function. 16 is a little over half of the allocatable register set. 85 static cl::opt<unsigned> MaxVarsPrep("ppc-formprep-max-vars", 86 cl::Hidden, cl::init(16), 87 cl::desc("Potential common base number threshold per function for PPC loop " 88 "prep")); 89 90 static cl::opt<bool> PreferUpdateForm("ppc-formprep-prefer-update", 91 cl::init(true), cl::Hidden, 92 cl::desc("prefer update form when ds form is also a update form")); 93 94 // Sum of following 3 per loop thresholds for all loops can not be larger 95 // than MaxVarsPrep. 96 // By default, we limit this to creating 9 PHIs for one loop. 97 // 9 and 3 for each kind prep are exterimental values on Power9. 98 static cl::opt<unsigned> MaxVarsUpdateForm("ppc-preinc-prep-max-vars", 99 cl::Hidden, cl::init(3), 100 cl::desc("Potential PHI threshold per loop for PPC loop prep of update " 101 "form")); 102 103 static cl::opt<unsigned> MaxVarsDSForm("ppc-dsprep-max-vars", 104 cl::Hidden, cl::init(3), 105 cl::desc("Potential PHI threshold per loop for PPC loop prep of DS form")); 106 107 static cl::opt<unsigned> MaxVarsDQForm("ppc-dqprep-max-vars", 108 cl::Hidden, cl::init(3), 109 cl::desc("Potential PHI threshold per loop for PPC loop prep of DQ form")); 110 111 112 // If would not be profitable if the common base has only one load/store, ISEL 113 // should already be able to choose best load/store form based on offset for 114 // single load/store. Set minimal profitable value default to 2 and make it as 115 // an option. 116 static cl::opt<unsigned> DispFormPrepMinThreshold("ppc-dispprep-min-threshold", 117 cl::Hidden, cl::init(2), 118 cl::desc("Minimal common base load/store instructions triggering DS/DQ form " 119 "preparation")); 120 121 STATISTIC(PHINodeAlreadyExistsUpdate, "PHI node already in pre-increment form"); 122 STATISTIC(PHINodeAlreadyExistsDS, "PHI node already in DS form"); 123 STATISTIC(PHINodeAlreadyExistsDQ, "PHI node already in DQ form"); 124 STATISTIC(DSFormChainRewritten, "Num of DS form chain rewritten"); 125 STATISTIC(DQFormChainRewritten, "Num of DQ form chain rewritten"); 126 STATISTIC(UpdFormChainRewritten, "Num of update form chain rewritten"); 127 128 namespace { 129 struct BucketElement { 130 BucketElement(const SCEVConstant *O, Instruction *I) : Offset(O), Instr(I) {} 131 BucketElement(Instruction *I) : Offset(nullptr), Instr(I) {} 132 133 const SCEVConstant *Offset; 134 Instruction *Instr; 135 }; 136 137 struct Bucket { 138 Bucket(const SCEV *B, Instruction *I) : BaseSCEV(B), 139 Elements(1, BucketElement(I)) {} 140 141 const SCEV *BaseSCEV; 142 SmallVector<BucketElement, 16> Elements; 143 }; 144 145 // "UpdateForm" is not a real PPC instruction form, it stands for dform 146 // load/store with update like ldu/stdu, or Prefetch intrinsic. 147 // For DS form instructions, their displacements must be multiple of 4. 148 // For DQ form instructions, their displacements must be multiple of 16. 149 enum InstrForm { UpdateForm = 1, DSForm = 4, DQForm = 16 }; 150 151 class PPCLoopInstrFormPrep : public FunctionPass { 152 public: 153 static char ID; // Pass ID, replacement for typeid 154 155 PPCLoopInstrFormPrep() : FunctionPass(ID) { 156 initializePPCLoopInstrFormPrepPass(*PassRegistry::getPassRegistry()); 157 } 158 159 PPCLoopInstrFormPrep(PPCTargetMachine &TM) : FunctionPass(ID), TM(&TM) { 160 initializePPCLoopInstrFormPrepPass(*PassRegistry::getPassRegistry()); 161 } 162 163 void getAnalysisUsage(AnalysisUsage &AU) const override { 164 AU.addPreserved<DominatorTreeWrapperPass>(); 165 AU.addRequired<LoopInfoWrapperPass>(); 166 AU.addPreserved<LoopInfoWrapperPass>(); 167 AU.addRequired<ScalarEvolutionWrapperPass>(); 168 } 169 170 bool runOnFunction(Function &F) override; 171 172 private: 173 PPCTargetMachine *TM = nullptr; 174 const PPCSubtarget *ST; 175 DominatorTree *DT; 176 LoopInfo *LI; 177 ScalarEvolution *SE; 178 bool PreserveLCSSA; 179 180 /// Successful preparation number for Update/DS/DQ form in all inner most 181 /// loops. One successful preparation will put one common base out of loop, 182 /// this may leads to register presure like LICM does. 183 /// Make sure total preparation number can be controlled by option. 184 unsigned SuccPrepCount; 185 186 bool runOnLoop(Loop *L); 187 188 /// Check if required PHI node is already exist in Loop \p L. 189 bool alreadyPrepared(Loop *L, Instruction* MemI, 190 const SCEV *BasePtrStartSCEV, 191 const SCEVConstant *BasePtrIncSCEV, 192 InstrForm Form); 193 194 /// Collect condition matched(\p isValidCandidate() returns true) 195 /// candidates in Loop \p L. 196 SmallVector<Bucket, 16> 197 collectCandidates(Loop *L, 198 std::function<bool(const Instruction *, const Value *)> 199 isValidCandidate, 200 unsigned MaxCandidateNum); 201 202 /// Add a candidate to candidates \p Buckets. 203 void addOneCandidate(Instruction *MemI, const SCEV *LSCEV, 204 SmallVector<Bucket, 16> &Buckets, 205 unsigned MaxCandidateNum); 206 207 /// Prepare all candidates in \p Buckets for update form. 208 bool updateFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets); 209 210 /// Prepare all candidates in \p Buckets for displacement form, now for 211 /// ds/dq. 212 bool dispFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets, 213 InstrForm Form); 214 215 /// Prepare for one chain \p BucketChain, find the best base element and 216 /// update all other elements in \p BucketChain accordingly. 217 /// \p Form is used to find the best base element. 218 /// If success, best base element must be stored as the first element of 219 /// \p BucketChain. 220 /// Return false if no base element found, otherwise return true. 221 bool prepareBaseForDispFormChain(Bucket &BucketChain, 222 InstrForm Form); 223 224 /// Prepare for one chain \p BucketChain, find the best base element and 225 /// update all other elements in \p BucketChain accordingly. 226 /// If success, best base element must be stored as the first element of 227 /// \p BucketChain. 228 /// Return false if no base element found, otherwise return true. 229 bool prepareBaseForUpdateFormChain(Bucket &BucketChain); 230 231 /// Rewrite load/store instructions in \p BucketChain according to 232 /// preparation. 233 bool rewriteLoadStores(Loop *L, Bucket &BucketChain, 234 SmallSet<BasicBlock *, 16> &BBChanged, 235 InstrForm Form); 236 }; 237 238 } // end anonymous namespace 239 240 char PPCLoopInstrFormPrep::ID = 0; 241 static const char *name = "Prepare loop for ppc preferred instruction forms"; 242 INITIALIZE_PASS_BEGIN(PPCLoopInstrFormPrep, DEBUG_TYPE, name, false, false) 243 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 244 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) 245 INITIALIZE_PASS_END(PPCLoopInstrFormPrep, DEBUG_TYPE, name, false, false) 246 247 static constexpr StringRef PHINodeNameSuffix = ".phi"; 248 static constexpr StringRef CastNodeNameSuffix = ".cast"; 249 static constexpr StringRef GEPNodeIncNameSuffix = ".inc"; 250 static constexpr StringRef GEPNodeOffNameSuffix = ".off"; 251 252 FunctionPass *llvm::createPPCLoopInstrFormPrepPass(PPCTargetMachine &TM) { 253 return new PPCLoopInstrFormPrep(TM); 254 } 255 256 static bool IsPtrInBounds(Value *BasePtr) { 257 Value *StrippedBasePtr = BasePtr; 258 while (BitCastInst *BC = dyn_cast<BitCastInst>(StrippedBasePtr)) 259 StrippedBasePtr = BC->getOperand(0); 260 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(StrippedBasePtr)) 261 return GEP->isInBounds(); 262 263 return false; 264 } 265 266 static std::string getInstrName(const Value *I, StringRef Suffix) { 267 assert(I && "Invalid paramater!"); 268 if (I->hasName()) 269 return (I->getName() + Suffix).str(); 270 else 271 return ""; 272 } 273 274 static Value *GetPointerOperand(Value *MemI) { 275 if (LoadInst *LMemI = dyn_cast<LoadInst>(MemI)) { 276 return LMemI->getPointerOperand(); 277 } else if (StoreInst *SMemI = dyn_cast<StoreInst>(MemI)) { 278 return SMemI->getPointerOperand(); 279 } else if (IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(MemI)) { 280 if (IMemI->getIntrinsicID() == Intrinsic::prefetch) 281 return IMemI->getArgOperand(0); 282 } 283 284 return nullptr; 285 } 286 287 bool PPCLoopInstrFormPrep::runOnFunction(Function &F) { 288 if (skipFunction(F)) 289 return false; 290 291 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 292 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 293 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 294 DT = DTWP ? &DTWP->getDomTree() : nullptr; 295 PreserveLCSSA = mustPreserveAnalysisID(LCSSAID); 296 ST = TM ? TM->getSubtargetImpl(F) : nullptr; 297 SuccPrepCount = 0; 298 299 bool MadeChange = false; 300 301 for (auto I = LI->begin(), IE = LI->end(); I != IE; ++I) 302 for (auto L = df_begin(*I), LE = df_end(*I); L != LE; ++L) 303 MadeChange |= runOnLoop(*L); 304 305 return MadeChange; 306 } 307 308 void PPCLoopInstrFormPrep::addOneCandidate(Instruction *MemI, const SCEV *LSCEV, 309 SmallVector<Bucket, 16> &Buckets, 310 unsigned MaxCandidateNum) { 311 assert((MemI && GetPointerOperand(MemI)) && 312 "Candidate should be a memory instruction."); 313 assert(LSCEV && "Invalid SCEV for Ptr value."); 314 bool FoundBucket = false; 315 for (auto &B : Buckets) { 316 const SCEV *Diff = SE->getMinusSCEV(LSCEV, B.BaseSCEV); 317 if (const auto *CDiff = dyn_cast<SCEVConstant>(Diff)) { 318 B.Elements.push_back(BucketElement(CDiff, MemI)); 319 FoundBucket = true; 320 break; 321 } 322 } 323 324 if (!FoundBucket) { 325 if (Buckets.size() == MaxCandidateNum) 326 return; 327 Buckets.push_back(Bucket(LSCEV, MemI)); 328 } 329 } 330 331 SmallVector<Bucket, 16> PPCLoopInstrFormPrep::collectCandidates( 332 Loop *L, 333 std::function<bool(const Instruction *, const Value *)> isValidCandidate, 334 unsigned MaxCandidateNum) { 335 SmallVector<Bucket, 16> Buckets; 336 for (const auto &BB : L->blocks()) 337 for (auto &J : *BB) { 338 Value *PtrValue; 339 Instruction *MemI; 340 341 if (LoadInst *LMemI = dyn_cast<LoadInst>(&J)) { 342 MemI = LMemI; 343 PtrValue = LMemI->getPointerOperand(); 344 } else if (StoreInst *SMemI = dyn_cast<StoreInst>(&J)) { 345 MemI = SMemI; 346 PtrValue = SMemI->getPointerOperand(); 347 } else if (IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(&J)) { 348 if (IMemI->getIntrinsicID() == Intrinsic::prefetch) { 349 MemI = IMemI; 350 PtrValue = IMemI->getArgOperand(0); 351 } else continue; 352 } else continue; 353 354 unsigned PtrAddrSpace = PtrValue->getType()->getPointerAddressSpace(); 355 if (PtrAddrSpace) 356 continue; 357 358 if (L->isLoopInvariant(PtrValue)) 359 continue; 360 361 const SCEV *LSCEV = SE->getSCEVAtScope(PtrValue, L); 362 const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(LSCEV); 363 if (!LARSCEV || LARSCEV->getLoop() != L) 364 continue; 365 366 if (isValidCandidate(&J, PtrValue)) 367 addOneCandidate(MemI, LSCEV, Buckets, MaxCandidateNum); 368 } 369 return Buckets; 370 } 371 372 bool PPCLoopInstrFormPrep::prepareBaseForDispFormChain(Bucket &BucketChain, 373 InstrForm Form) { 374 // RemainderOffsetInfo details: 375 // key: value of (Offset urem DispConstraint). For DSForm, it can 376 // be [0, 4). 377 // first of pair: the index of first BucketElement whose remainder is equal 378 // to key. For key 0, this value must be 0. 379 // second of pair: number of load/stores with the same remainder. 380 DenseMap<unsigned, std::pair<unsigned, unsigned>> RemainderOffsetInfo; 381 382 for (unsigned j = 0, je = BucketChain.Elements.size(); j != je; ++j) { 383 if (!BucketChain.Elements[j].Offset) 384 RemainderOffsetInfo[0] = std::make_pair(0, 1); 385 else { 386 unsigned Remainder = 387 BucketChain.Elements[j].Offset->getAPInt().urem(Form); 388 if (RemainderOffsetInfo.find(Remainder) == RemainderOffsetInfo.end()) 389 RemainderOffsetInfo[Remainder] = std::make_pair(j, 1); 390 else 391 RemainderOffsetInfo[Remainder].second++; 392 } 393 } 394 // Currently we choose the most profitable base as the one which has the max 395 // number of load/store with same remainder. 396 // FIXME: adjust the base selection strategy according to load/store offset 397 // distribution. 398 // For example, if we have one candidate chain for DS form preparation, which 399 // contains following load/stores with different remainders: 400 // 1: 10 load/store whose remainder is 1; 401 // 2: 9 load/store whose remainder is 2; 402 // 3: 1 for remainder 3 and 0 for remainder 0; 403 // Now we will choose the first load/store whose remainder is 1 as base and 404 // adjust all other load/stores according to new base, so we will get 10 DS 405 // form and 10 X form. 406 // But we should be more clever, for this case we could use two bases, one for 407 // remainder 1 and the other for remainder 2, thus we could get 19 DS form and 1 408 // X form. 409 unsigned MaxCountRemainder = 0; 410 for (unsigned j = 0; j < (unsigned)Form; j++) 411 if ((RemainderOffsetInfo.find(j) != RemainderOffsetInfo.end()) && 412 RemainderOffsetInfo[j].second > 413 RemainderOffsetInfo[MaxCountRemainder].second) 414 MaxCountRemainder = j; 415 416 // Abort when there are too few insts with common base. 417 if (RemainderOffsetInfo[MaxCountRemainder].second < DispFormPrepMinThreshold) 418 return false; 419 420 // If the first value is most profitable, no needed to adjust BucketChain 421 // elements as they are substracted the first value when collecting. 422 if (MaxCountRemainder == 0) 423 return true; 424 425 // Adjust load/store to the new chosen base. 426 const SCEV *Offset = 427 BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first].Offset; 428 BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset); 429 for (auto &E : BucketChain.Elements) { 430 if (E.Offset) 431 E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(E.Offset, Offset)); 432 else 433 E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(Offset)); 434 } 435 436 std::swap(BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first], 437 BucketChain.Elements[0]); 438 return true; 439 } 440 441 // FIXME: implement a more clever base choosing policy. 442 // Currently we always choose an exist load/store offset. This maybe lead to 443 // suboptimal code sequences. For example, for one DS chain with offsets 444 // {-32769, 2003, 2007, 2011}, we choose -32769 as base offset, and left disp 445 // for load/stores are {0, 34772, 34776, 34780}. Though each offset now is a 446 // multipler of 4, it cannot be represented by sint16. 447 bool PPCLoopInstrFormPrep::prepareBaseForUpdateFormChain(Bucket &BucketChain) { 448 // We have a choice now of which instruction's memory operand we use as the 449 // base for the generated PHI. Always picking the first instruction in each 450 // bucket does not work well, specifically because that instruction might 451 // be a prefetch (and there are no pre-increment dcbt variants). Otherwise, 452 // the choice is somewhat arbitrary, because the backend will happily 453 // generate direct offsets from both the pre-incremented and 454 // post-incremented pointer values. Thus, we'll pick the first non-prefetch 455 // instruction in each bucket, and adjust the recurrence and other offsets 456 // accordingly. 457 for (int j = 0, je = BucketChain.Elements.size(); j != je; ++j) { 458 if (auto *II = dyn_cast<IntrinsicInst>(BucketChain.Elements[j].Instr)) 459 if (II->getIntrinsicID() == Intrinsic::prefetch) 460 continue; 461 462 // If we'd otherwise pick the first element anyway, there's nothing to do. 463 if (j == 0) 464 break; 465 466 // If our chosen element has no offset from the base pointer, there's 467 // nothing to do. 468 if (!BucketChain.Elements[j].Offset || 469 BucketChain.Elements[j].Offset->isZero()) 470 break; 471 472 const SCEV *Offset = BucketChain.Elements[j].Offset; 473 BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset); 474 for (auto &E : BucketChain.Elements) { 475 if (E.Offset) 476 E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(E.Offset, Offset)); 477 else 478 E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(Offset)); 479 } 480 481 std::swap(BucketChain.Elements[j], BucketChain.Elements[0]); 482 break; 483 } 484 return true; 485 } 486 487 bool PPCLoopInstrFormPrep::rewriteLoadStores(Loop *L, Bucket &BucketChain, 488 SmallSet<BasicBlock *, 16> &BBChanged, 489 InstrForm Form) { 490 bool MadeChange = false; 491 const SCEVAddRecExpr *BasePtrSCEV = 492 cast<SCEVAddRecExpr>(BucketChain.BaseSCEV); 493 if (!BasePtrSCEV->isAffine()) 494 return MadeChange; 495 496 LLVM_DEBUG(dbgs() << "PIP: Transforming: " << *BasePtrSCEV << "\n"); 497 498 assert(BasePtrSCEV->getLoop() == L && "AddRec for the wrong loop?"); 499 500 // The instruction corresponding to the Bucket's BaseSCEV must be the first 501 // in the vector of elements. 502 Instruction *MemI = BucketChain.Elements.begin()->Instr; 503 Value *BasePtr = GetPointerOperand(MemI); 504 assert(BasePtr && "No pointer operand"); 505 506 Type *I8Ty = Type::getInt8Ty(MemI->getParent()->getContext()); 507 Type *I8PtrTy = Type::getInt8PtrTy(MemI->getParent()->getContext(), 508 BasePtr->getType()->getPointerAddressSpace()); 509 510 if (!SE->isLoopInvariant(BasePtrSCEV->getStart(), L)) 511 return MadeChange; 512 513 const SCEVConstant *BasePtrIncSCEV = 514 dyn_cast<SCEVConstant>(BasePtrSCEV->getStepRecurrence(*SE)); 515 if (!BasePtrIncSCEV) 516 return MadeChange; 517 518 // For some DS form load/store instructions, it can also be an update form, 519 // if the stride is a multipler of 4. Use update form if prefer it. 520 bool CanPreInc = (Form == UpdateForm || 521 ((Form == DSForm) && !BasePtrIncSCEV->getAPInt().urem(4) && 522 PreferUpdateForm)); 523 const SCEV *BasePtrStartSCEV = nullptr; 524 if (CanPreInc) 525 BasePtrStartSCEV = 526 SE->getMinusSCEV(BasePtrSCEV->getStart(), BasePtrIncSCEV); 527 else 528 BasePtrStartSCEV = BasePtrSCEV->getStart(); 529 530 if (!isSafeToExpand(BasePtrStartSCEV, *SE)) 531 return MadeChange; 532 533 if (alreadyPrepared(L, MemI, BasePtrStartSCEV, BasePtrIncSCEV, Form)) 534 return MadeChange; 535 536 LLVM_DEBUG(dbgs() << "PIP: New start is: " << *BasePtrStartSCEV << "\n"); 537 538 BasicBlock *Header = L->getHeader(); 539 unsigned HeaderLoopPredCount = pred_size(Header); 540 BasicBlock *LoopPredecessor = L->getLoopPredecessor(); 541 542 PHINode *NewPHI = 543 PHINode::Create(I8PtrTy, HeaderLoopPredCount, 544 getInstrName(MemI, PHINodeNameSuffix), 545 Header->getFirstNonPHI()); 546 547 SCEVExpander SCEVE(*SE, Header->getModule()->getDataLayout(), "pistart"); 548 Value *BasePtrStart = SCEVE.expandCodeFor(BasePtrStartSCEV, I8PtrTy, 549 LoopPredecessor->getTerminator()); 550 551 // Note that LoopPredecessor might occur in the predecessor list multiple 552 // times, and we need to add it the right number of times. 553 for (auto PI : predecessors(Header)) { 554 if (PI != LoopPredecessor) 555 continue; 556 557 NewPHI->addIncoming(BasePtrStart, LoopPredecessor); 558 } 559 560 Instruction *PtrInc = nullptr; 561 Instruction *NewBasePtr = nullptr; 562 if (CanPreInc) { 563 Instruction *InsPoint = &*Header->getFirstInsertionPt(); 564 PtrInc = GetElementPtrInst::Create( 565 I8Ty, NewPHI, BasePtrIncSCEV->getValue(), 566 getInstrName(MemI, GEPNodeIncNameSuffix), InsPoint); 567 cast<GetElementPtrInst>(PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr)); 568 for (auto PI : predecessors(Header)) { 569 if (PI == LoopPredecessor) 570 continue; 571 572 NewPHI->addIncoming(PtrInc, PI); 573 } 574 if (PtrInc->getType() != BasePtr->getType()) 575 NewBasePtr = new BitCastInst( 576 PtrInc, BasePtr->getType(), 577 getInstrName(PtrInc, CastNodeNameSuffix), InsPoint); 578 else 579 NewBasePtr = PtrInc; 580 } else { 581 // Note that LoopPredecessor might occur in the predecessor list multiple 582 // times, and we need to make sure no more incoming value for them in PHI. 583 for (auto PI : predecessors(Header)) { 584 if (PI == LoopPredecessor) 585 continue; 586 587 // For the latch predecessor, we need to insert a GEP just before the 588 // terminator to increase the address. 589 BasicBlock *BB = PI; 590 Instruction *InsPoint = BB->getTerminator(); 591 PtrInc = GetElementPtrInst::Create( 592 I8Ty, NewPHI, BasePtrIncSCEV->getValue(), 593 getInstrName(MemI, GEPNodeIncNameSuffix), InsPoint); 594 595 cast<GetElementPtrInst>(PtrInc)->setIsInBounds(IsPtrInBounds(BasePtr)); 596 597 NewPHI->addIncoming(PtrInc, PI); 598 } 599 PtrInc = NewPHI; 600 if (NewPHI->getType() != BasePtr->getType()) 601 NewBasePtr = 602 new BitCastInst(NewPHI, BasePtr->getType(), 603 getInstrName(NewPHI, CastNodeNameSuffix), 604 &*Header->getFirstInsertionPt()); 605 else 606 NewBasePtr = NewPHI; 607 } 608 609 if (Instruction *IDel = dyn_cast<Instruction>(BasePtr)) 610 BBChanged.insert(IDel->getParent()); 611 BasePtr->replaceAllUsesWith(NewBasePtr); 612 RecursivelyDeleteTriviallyDeadInstructions(BasePtr); 613 614 // Keep track of the replacement pointer values we've inserted so that we 615 // don't generate more pointer values than necessary. 616 SmallPtrSet<Value *, 16> NewPtrs; 617 NewPtrs.insert(NewBasePtr); 618 619 for (auto I = std::next(BucketChain.Elements.begin()), 620 IE = BucketChain.Elements.end(); I != IE; ++I) { 621 Value *Ptr = GetPointerOperand(I->Instr); 622 assert(Ptr && "No pointer operand"); 623 if (NewPtrs.count(Ptr)) 624 continue; 625 626 Instruction *RealNewPtr; 627 if (!I->Offset || I->Offset->getValue()->isZero()) { 628 RealNewPtr = NewBasePtr; 629 } else { 630 Instruction *PtrIP = dyn_cast<Instruction>(Ptr); 631 if (PtrIP && isa<Instruction>(NewBasePtr) && 632 cast<Instruction>(NewBasePtr)->getParent() == PtrIP->getParent()) 633 PtrIP = nullptr; 634 else if (PtrIP && isa<PHINode>(PtrIP)) 635 PtrIP = &*PtrIP->getParent()->getFirstInsertionPt(); 636 else if (!PtrIP) 637 PtrIP = I->Instr; 638 639 GetElementPtrInst *NewPtr = GetElementPtrInst::Create( 640 I8Ty, PtrInc, I->Offset->getValue(), 641 getInstrName(I->Instr, GEPNodeOffNameSuffix), PtrIP); 642 if (!PtrIP) 643 NewPtr->insertAfter(cast<Instruction>(PtrInc)); 644 NewPtr->setIsInBounds(IsPtrInBounds(Ptr)); 645 RealNewPtr = NewPtr; 646 } 647 648 if (Instruction *IDel = dyn_cast<Instruction>(Ptr)) 649 BBChanged.insert(IDel->getParent()); 650 651 Instruction *ReplNewPtr; 652 if (Ptr->getType() != RealNewPtr->getType()) { 653 ReplNewPtr = new BitCastInst(RealNewPtr, Ptr->getType(), 654 getInstrName(Ptr, CastNodeNameSuffix)); 655 ReplNewPtr->insertAfter(RealNewPtr); 656 } else 657 ReplNewPtr = RealNewPtr; 658 659 Ptr->replaceAllUsesWith(ReplNewPtr); 660 RecursivelyDeleteTriviallyDeadInstructions(Ptr); 661 662 NewPtrs.insert(RealNewPtr); 663 } 664 665 MadeChange = true; 666 667 SuccPrepCount++; 668 669 if (Form == DSForm && !CanPreInc) 670 DSFormChainRewritten++; 671 else if (Form == DQForm) 672 DQFormChainRewritten++; 673 else if (Form == UpdateForm || (Form == DSForm && CanPreInc)) 674 UpdFormChainRewritten++; 675 676 return MadeChange; 677 } 678 679 bool PPCLoopInstrFormPrep::updateFormPrep(Loop *L, 680 SmallVector<Bucket, 16> &Buckets) { 681 bool MadeChange = false; 682 if (Buckets.empty()) 683 return MadeChange; 684 SmallSet<BasicBlock *, 16> BBChanged; 685 for (auto &Bucket : Buckets) 686 // The base address of each bucket is transformed into a phi and the others 687 // are rewritten based on new base. 688 if (prepareBaseForUpdateFormChain(Bucket)) 689 MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, UpdateForm); 690 691 if (MadeChange) 692 for (auto &BB : L->blocks()) 693 if (BBChanged.count(BB)) 694 DeleteDeadPHIs(BB); 695 return MadeChange; 696 } 697 698 bool PPCLoopInstrFormPrep::dispFormPrep(Loop *L, SmallVector<Bucket, 16> &Buckets, 699 InstrForm Form) { 700 bool MadeChange = false; 701 702 if (Buckets.empty()) 703 return MadeChange; 704 705 SmallSet<BasicBlock *, 16> BBChanged; 706 for (auto &Bucket : Buckets) { 707 if (Bucket.Elements.size() < DispFormPrepMinThreshold) 708 continue; 709 if (prepareBaseForDispFormChain(Bucket, Form)) 710 MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, Form); 711 } 712 713 if (MadeChange) 714 for (auto &BB : L->blocks()) 715 if (BBChanged.count(BB)) 716 DeleteDeadPHIs(BB); 717 return MadeChange; 718 } 719 720 // In order to prepare for the preferred instruction form, a PHI is added. 721 // This function will check to see if that PHI already exists and will return 722 // true if it found an existing PHI with the matched start and increment as the 723 // one we wanted to create. 724 bool PPCLoopInstrFormPrep::alreadyPrepared(Loop *L, Instruction* MemI, 725 const SCEV *BasePtrStartSCEV, 726 const SCEVConstant *BasePtrIncSCEV, 727 InstrForm Form) { 728 BasicBlock *BB = MemI->getParent(); 729 if (!BB) 730 return false; 731 732 BasicBlock *PredBB = L->getLoopPredecessor(); 733 BasicBlock *LatchBB = L->getLoopLatch(); 734 735 if (!PredBB || !LatchBB) 736 return false; 737 738 // Run through the PHIs and see if we have some that looks like a preparation 739 iterator_range<BasicBlock::phi_iterator> PHIIter = BB->phis(); 740 for (auto & CurrentPHI : PHIIter) { 741 PHINode *CurrentPHINode = dyn_cast<PHINode>(&CurrentPHI); 742 if (!CurrentPHINode) 743 continue; 744 745 if (!SE->isSCEVable(CurrentPHINode->getType())) 746 continue; 747 748 const SCEV *PHISCEV = SE->getSCEVAtScope(CurrentPHINode, L); 749 750 const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast<SCEVAddRecExpr>(PHISCEV); 751 if (!PHIBasePtrSCEV) 752 continue; 753 754 const SCEVConstant *PHIBasePtrIncSCEV = 755 dyn_cast<SCEVConstant>(PHIBasePtrSCEV->getStepRecurrence(*SE)); 756 if (!PHIBasePtrIncSCEV) 757 continue; 758 759 if (CurrentPHINode->getNumIncomingValues() == 2) { 760 if ((CurrentPHINode->getIncomingBlock(0) == LatchBB && 761 CurrentPHINode->getIncomingBlock(1) == PredBB) || 762 (CurrentPHINode->getIncomingBlock(1) == LatchBB && 763 CurrentPHINode->getIncomingBlock(0) == PredBB)) { 764 if (PHIBasePtrIncSCEV == BasePtrIncSCEV) { 765 // The existing PHI (CurrentPHINode) has the same start and increment 766 // as the PHI that we wanted to create. 767 if (Form == UpdateForm && 768 PHIBasePtrSCEV->getStart() == BasePtrStartSCEV) { 769 ++PHINodeAlreadyExistsUpdate; 770 return true; 771 } 772 if (Form == DSForm || Form == DQForm) { 773 const SCEVConstant *Diff = dyn_cast<SCEVConstant>( 774 SE->getMinusSCEV(PHIBasePtrSCEV->getStart(), BasePtrStartSCEV)); 775 if (Diff && !Diff->getAPInt().urem(Form)) { 776 if (Form == DSForm) 777 ++PHINodeAlreadyExistsDS; 778 else 779 ++PHINodeAlreadyExistsDQ; 780 return true; 781 } 782 } 783 } 784 } 785 } 786 } 787 return false; 788 } 789 790 bool PPCLoopInstrFormPrep::runOnLoop(Loop *L) { 791 bool MadeChange = false; 792 793 // Only prep. the inner-most loop 794 if (!L->empty()) 795 return MadeChange; 796 797 // Return if already done enough preparation. 798 if (SuccPrepCount >= MaxVarsPrep) 799 return MadeChange; 800 801 LLVM_DEBUG(dbgs() << "PIP: Examining: " << *L << "\n"); 802 803 BasicBlock *LoopPredecessor = L->getLoopPredecessor(); 804 // If there is no loop predecessor, or the loop predecessor's terminator 805 // returns a value (which might contribute to determining the loop's 806 // iteration space), insert a new preheader for the loop. 807 if (!LoopPredecessor || 808 !LoopPredecessor->getTerminator()->getType()->isVoidTy()) { 809 LoopPredecessor = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA); 810 if (LoopPredecessor) 811 MadeChange = true; 812 } 813 if (!LoopPredecessor) { 814 LLVM_DEBUG(dbgs() << "PIP fails since no predecessor for current loop.\n"); 815 return MadeChange; 816 } 817 // Check if a load/store has update form. This lambda is used by function 818 // collectCandidates which can collect candidates for types defined by lambda. 819 auto isUpdateFormCandidate = [&] (const Instruction *I, 820 const Value *PtrValue) { 821 assert((PtrValue && I) && "Invalid parameter!"); 822 // There are no update forms for Altivec vector load/stores. 823 if (ST && ST->hasAltivec() && 824 PtrValue->getType()->getPointerElementType()->isVectorTy()) 825 return false; 826 // See getPreIndexedAddressParts, the displacement for LDU/STDU has to 827 // be 4's multiple (DS-form). For i64 loads/stores when the displacement 828 // fits in a 16-bit signed field but isn't a multiple of 4, it will be 829 // useless and possible to break some original well-form addressing mode 830 // to make this pre-inc prep for it. 831 if (PtrValue->getType()->getPointerElementType()->isIntegerTy(64)) { 832 const SCEV *LSCEV = SE->getSCEVAtScope(const_cast<Value *>(PtrValue), L); 833 const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(LSCEV); 834 if (!LARSCEV || LARSCEV->getLoop() != L) 835 return false; 836 if (const SCEVConstant *StepConst = 837 dyn_cast<SCEVConstant>(LARSCEV->getStepRecurrence(*SE))) { 838 const APInt &ConstInt = StepConst->getValue()->getValue(); 839 if (ConstInt.isSignedIntN(16) && ConstInt.srem(4) != 0) 840 return false; 841 } 842 } 843 return true; 844 }; 845 846 // Check if a load/store has DS form. 847 auto isDSFormCandidate = [] (const Instruction *I, const Value *PtrValue) { 848 assert((PtrValue && I) && "Invalid parameter!"); 849 if (isa<IntrinsicInst>(I)) 850 return false; 851 Type *PointerElementType = PtrValue->getType()->getPointerElementType(); 852 return (PointerElementType->isIntegerTy(64)) || 853 (PointerElementType->isFloatTy()) || 854 (PointerElementType->isDoubleTy()) || 855 (PointerElementType->isIntegerTy(32) && 856 llvm::any_of(I->users(), 857 [](const User *U) { return isa<SExtInst>(U); })); 858 }; 859 860 // Check if a load/store has DQ form. 861 auto isDQFormCandidate = [&] (const Instruction *I, const Value *PtrValue) { 862 assert((PtrValue && I) && "Invalid parameter!"); 863 return !isa<IntrinsicInst>(I) && ST && ST->hasP9Vector() && 864 (PtrValue->getType()->getPointerElementType()->isVectorTy()); 865 }; 866 867 // intrinsic for update form. 868 SmallVector<Bucket, 16> UpdateFormBuckets = 869 collectCandidates(L, isUpdateFormCandidate, MaxVarsUpdateForm); 870 871 // Prepare for update form. 872 if (!UpdateFormBuckets.empty()) 873 MadeChange |= updateFormPrep(L, UpdateFormBuckets); 874 875 // Collect buckets of comparable addresses used by loads and stores for DS 876 // form. 877 SmallVector<Bucket, 16> DSFormBuckets = 878 collectCandidates(L, isDSFormCandidate, MaxVarsDSForm); 879 880 // Prepare for DS form. 881 if (!DSFormBuckets.empty()) 882 MadeChange |= dispFormPrep(L, DSFormBuckets, DSForm); 883 884 // Collect buckets of comparable addresses used by loads and stores for DQ 885 // form. 886 SmallVector<Bucket, 16> DQFormBuckets = 887 collectCandidates(L, isDQFormCandidate, MaxVarsDQForm); 888 889 // Prepare for DQ form. 890 if (!DQFormBuckets.empty()) 891 MadeChange |= dispFormPrep(L, DQFormBuckets, DQForm); 892 893 return MadeChange; 894 } 895