contrib/llvm/lib/Target/PowerPC/PPCLoopPreIncPrep.cpp

   1 //===------ PPCLoopPreIncPrep.cpp - Loop Pre-Inc. AM Prep. Pass -----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a pass to prepare loops for pre-increment addressing
  11 // modes. Additional PHIs are created for loop induction variables used by
  12 // load/store instructions so that the pre-increment forms can be used.
  13 // Generically, this means transforming loops like this:
  14 //   for (int i = 0; i < n; ++i)
  15 //     array[i] = c;
  16 // to look like this:
  17 //   T *p = array[-1];
  18 //   for (int i = 0; i < n; ++i)
  19 //     *++p = c;
  20 //===----------------------------------------------------------------------===//
  21
  22 #define DEBUG_TYPE "ppc-loop-preinc-prep"
  23
  24 #include "PPC.h"
  25 #include "PPCSubtarget.h"
  26 #include "PPCTargetMachine.h"
  27 #include "llvm/ADT/DepthFirstIterator.h"
  28 #include "llvm/ADT/SmallPtrSet.h"
  29 #include "llvm/ADT/SmallSet.h"
  30 #include "llvm/ADT/SmallVector.h"
  31 #include "llvm/Analysis/LoopInfo.h"
  32 #include "llvm/Analysis/ScalarEvolution.h"
  33 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  34 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  35 #include "llvm/IR/BasicBlock.h"
  36 #include "llvm/IR/CFG.h"
  37 #include "llvm/IR/Dominators.h"
  38 #include "llvm/IR/Instruction.h"
  39 #include "llvm/IR/Instructions.h"
  40 #include "llvm/IR/IntrinsicInst.h"
  41 #include "llvm/IR/Module.h"
  42 #include "llvm/IR/Value.h"
  43 #include "llvm/Pass.h"
  44 #include "llvm/Support/Casting.h"
  45 #include "llvm/Support/CommandLine.h"
  46 #include "llvm/Support/Debug.h"
  47 #include "llvm/Transforms/Scalar.h"
  48 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  49 #include "llvm/Transforms/Utils/Local.h"
  50 #include "llvm/Transforms/Utils/LoopUtils.h"
  51 #include <cassert>
  52 #include <iterator>
  53 #include <utility>
  54
  55 using namespace llvm;
  56
  57 // By default, we limit this to creating 16 PHIs (which is a little over half
  58 // of the allocatable register set).
  59 static cl::opt<unsigned> MaxVars("ppc-preinc-prep-max-vars",
  60                                  cl::Hidden, cl::init(16),
  61   cl::desc("Potential PHI threshold for PPC preinc loop prep"));
  62
  63 namespace llvm {
  64
  65   void initializePPCLoopPreIncPrepPass(PassRegistry&);
  66
  67 } // end namespace llvm
  68
  69 namespace {
  70
  71   class PPCLoopPreIncPrep : public FunctionPass {
  72   public:
  73     static char ID; // Pass ID, replacement for typeid
  74
  75     PPCLoopPreIncPrep() : FunctionPass(ID), TM(nullptr) {
  76       initializePPCLoopPreIncPrepPass(*PassRegistry::getPassRegistry());
  77     }
  78     PPCLoopPreIncPrep(PPCTargetMachine &TM) : FunctionPass(ID), TM(&TM) {
  79       initializePPCLoopPreIncPrepPass(*PassRegistry::getPassRegistry());
  80     }
  81
  82     void getAnalysisUsage(AnalysisUsage &AU) const override {
  83       AU.addPreserved<DominatorTreeWrapperPass>();
  84       AU.addRequired<LoopInfoWrapperPass>();
  85       AU.addPreserved<LoopInfoWrapperPass>();
  86       AU.addRequired<ScalarEvolutionWrapperPass>();
  87     }
  88
  89     bool runOnFunction(Function &F) override;
  90
  91     bool runOnLoop(Loop *L);
  92     void simplifyLoopLatch(Loop *L);
  93     bool rotateLoop(Loop *L);
  94
  95   private:
  96     PPCTargetMachine *TM;
  97     DominatorTree *DT;
  98     LoopInfo *LI;
  99     ScalarEvolution *SE;
 100     bool PreserveLCSSA;
 101   };
 102
 103 } // end anonymous namespace
 104
 105 char PPCLoopPreIncPrep::ID = 0;
 106 static const char *name = "Prepare loop for pre-inc. addressing modes";
 107 INITIALIZE_PASS_BEGIN(PPCLoopPreIncPrep, DEBUG_TYPE, name, false, false)
 108 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 109 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 110 INITIALIZE_PASS_END(PPCLoopPreIncPrep, DEBUG_TYPE, name, false, false)
 111
 112 FunctionPass *llvm::createPPCLoopPreIncPrepPass(PPCTargetMachine &TM) {
 113   return new PPCLoopPreIncPrep(TM);
 114 }
 115
 116 namespace {
 117
 118   struct BucketElement {
 119     BucketElement(const SCEVConstant *O, Instruction *I) : Offset(O), Instr(I) {}
 120     BucketElement(Instruction *I) : Offset(nullptr), Instr(I) {}
 121
 122     const SCEVConstant *Offset;
 123     Instruction *Instr;
 124   };
 125
 126   struct Bucket {
 127     Bucket(const SCEV *B, Instruction *I) : BaseSCEV(B),
 128                                             Elements(1, BucketElement(I)) {}
 129
 130     const SCEV *BaseSCEV;
 131     SmallVector<BucketElement, 16> Elements;
 132   };
 133
 134 } // end anonymous namespace
 135
 136 static bool IsPtrInBounds(Value *BasePtr) {
 137   Value *StrippedBasePtr = BasePtr;
 138   while (BitCastInst *BC = dyn_cast<BitCastInst>(StrippedBasePtr))
 139     StrippedBasePtr = BC->getOperand(0);
 140   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(StrippedBasePtr))
 141     return GEP->isInBounds();
 142
 143   return false;
 144 }
 145
 146 static Value *GetPointerOperand(Value *MemI) {
 147   if (LoadInst *LMemI = dyn_cast<LoadInst>(MemI)) {
 148     return LMemI->getPointerOperand();
 149   } else if (StoreInst *SMemI = dyn_cast<StoreInst>(MemI)) {
 150     return SMemI->getPointerOperand();
 151   } else if (IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(MemI)) {
 152     if (IMemI->getIntrinsicID() == Intrinsic::prefetch)
 153       return IMemI->getArgOperand(0);
 154   }
 155
 156   return nullptr;
 157 }
 158
 159 bool PPCLoopPreIncPrep::runOnFunction(Function &F) {
 160   if (skipFunction(F))
 161     return false;
 162
 163   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 164   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 165   auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
 166   DT = DTWP ? &DTWP->getDomTree() : nullptr;
 167   PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
 168
 169   bool MadeChange = false;
 170
 171   for (auto I = LI->begin(), IE = LI->end(); I != IE; ++I)
 172     for (auto L = df_begin(*I), LE = df_end(*I); L != LE; ++L)
 173       MadeChange |= runOnLoop(*L);
 174
 175   return MadeChange;
 176 }
 177
 178 bool PPCLoopPreIncPrep::runOnLoop(Loop *L) {
 179   bool MadeChange = false;
 180
 181   // Only prep. the inner-most loop
 182   if (!L->empty())
 183     return MadeChange;
 184
 185   DEBUG(dbgs() << "PIP: Examining: " << *L << "\n");
 186
 187   BasicBlock *Header = L->getHeader();
 188
 189   const PPCSubtarget *ST =
 190     TM ? TM->getSubtargetImpl(*Header->getParent()) : nullptr;
 191
 192   unsigned HeaderLoopPredCount =
 193     std::distance(pred_begin(Header), pred_end(Header));
 194
 195   // Collect buckets of comparable addresses used by loads and stores.
 196   SmallVector<Bucket, 16> Buckets;
 197   for (Loop::block_iterator I = L->block_begin(), IE = L->block_end();
 198        I != IE; ++I) {
 199     for (BasicBlock::iterator J = (*I)->begin(), JE = (*I)->end();
 200         J != JE; ++J) {
 201       Value *PtrValue;
 202       Instruction *MemI;
 203
 204       if (LoadInst *LMemI = dyn_cast<LoadInst>(J)) {
 205         MemI = LMemI;
 206         PtrValue = LMemI->getPointerOperand();
 207       } else if (StoreInst *SMemI = dyn_cast<StoreInst>(J)) {
 208         MemI = SMemI;
 209         PtrValue = SMemI->getPointerOperand();
 210       } else if (IntrinsicInst *IMemI = dyn_cast<IntrinsicInst>(J)) {
 211         if (IMemI->getIntrinsicID() == Intrinsic::prefetch) {
 212           MemI = IMemI;
 213           PtrValue = IMemI->getArgOperand(0);
 214         } else continue;
 215       } else continue;
 216
 217       unsigned PtrAddrSpace = PtrValue->getType()->getPointerAddressSpace();
 218       if (PtrAddrSpace)
 219         continue;
 220
 221       // There are no update forms for Altivec vector load/stores.
 222       if (ST && ST->hasAltivec() &&
 223           PtrValue->getType()->getPointerElementType()->isVectorTy())
 224         continue;
 225
 226       if (L->isLoopInvariant(PtrValue))
 227         continue;
 228
 229       const SCEV *LSCEV = SE->getSCEVAtScope(PtrValue, L);
 230       if (const SCEVAddRecExpr *LARSCEV = dyn_cast<SCEVAddRecExpr>(LSCEV)) {
 231         if (LARSCEV->getLoop() != L)
 232           continue;
 233       } else {
 234         continue;
 235       }
 236
 237       bool FoundBucket = false;
 238       for (auto &B : Buckets) {
 239         const SCEV *Diff = SE->getMinusSCEV(LSCEV, B.BaseSCEV);
 240         if (const auto *CDiff = dyn_cast<SCEVConstant>(Diff)) {
 241           B.Elements.push_back(BucketElement(CDiff, MemI));
 242           FoundBucket = true;
 243           break;
 244         }
 245       }
 246
 247       if (!FoundBucket) {
 248         if (Buckets.size() == MaxVars)
 249           return MadeChange;
 250         Buckets.push_back(Bucket(LSCEV, MemI));
 251       }
 252     }
 253   }
 254
 255   if (Buckets.empty())
 256     return MadeChange;
 257
 258   BasicBlock *LoopPredecessor = L->getLoopPredecessor();
 259   // If there is no loop predecessor, or the loop predecessor's terminator
 260   // returns a value (which might contribute to determining the loop's
 261   // iteration space), insert a new preheader for the loop.
 262   if (!LoopPredecessor ||
 263       !LoopPredecessor->getTerminator()->getType()->isVoidTy()) {
 264     LoopPredecessor = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA);
 265     if (LoopPredecessor)
 266       MadeChange = true;
 267   }
 268   if (!LoopPredecessor)
 269     return MadeChange;
 270
 271   DEBUG(dbgs() << "PIP: Found " << Buckets.size() << " buckets\n");
 272
 273   SmallSet<BasicBlock *, 16> BBChanged;
 274   for (unsigned i = 0, e = Buckets.size(); i != e; ++i) {
 275     // The base address of each bucket is transformed into a phi and the others
 276     // are rewritten as offsets of that variable.
 277
 278     // We have a choice now of which instruction's memory operand we use as the
 279     // base for the generated PHI. Always picking the first instruction in each
 280     // bucket does not work well, specifically because that instruction might
 281     // be a prefetch (and there are no pre-increment dcbt variants). Otherwise,
 282     // the choice is somewhat arbitrary, because the backend will happily
 283     // generate direct offsets from both the pre-incremented and
 284     // post-incremented pointer values. Thus, we'll pick the first non-prefetch
 285     // instruction in each bucket, and adjust the recurrence and other offsets
 286     // accordingly.
 287     for (int j = 0, je = Buckets[i].Elements.size(); j != je; ++j) {
 288       if (auto *II = dyn_cast<IntrinsicInst>(Buckets[i].Elements[j].Instr))
 289         if (II->getIntrinsicID() == Intrinsic::prefetch)
 290           continue;
 291
 292       // If we'd otherwise pick the first element anyway, there's nothing to do.
 293       if (j == 0)
 294         break;
 295
 296       // If our chosen element has no offset from the base pointer, there's
 297       // nothing to do.
 298       if (!Buckets[i].Elements[j].Offset ||
 299           Buckets[i].Elements[j].Offset->isZero())
 300         break;
 301
 302       const SCEV *Offset = Buckets[i].Elements[j].Offset;
 303       Buckets[i].BaseSCEV = SE->getAddExpr(Buckets[i].BaseSCEV, Offset);
 304       for (auto &E : Buckets[i].Elements) {
 305         if (E.Offset)
 306           E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(E.Offset, Offset));
 307         else
 308           E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(Offset));
 309       }
 310
 311       std::swap(Buckets[i].Elements[j], Buckets[i].Elements[0]);
 312       break;
 313     }
 314
 315     const SCEVAddRecExpr *BasePtrSCEV =
 316       cast<SCEVAddRecExpr>(Buckets[i].BaseSCEV);
 317     if (!BasePtrSCEV->isAffine())
 318       continue;
 319
 320     DEBUG(dbgs() << "PIP: Transforming: " << *BasePtrSCEV << "\n");
 321     assert(BasePtrSCEV->getLoop() == L &&
 322            "AddRec for the wrong loop?");
 323
 324     // The instruction corresponding to the Bucket's BaseSCEV must be the first
 325     // in the vector of elements.
 326     Instruction *MemI = Buckets[i].Elements.begin()->Instr;
 327     Value *BasePtr = GetPointerOperand(MemI);
 328     assert(BasePtr && "No pointer operand");
 329
 330     Type *I8Ty = Type::getInt8Ty(MemI->getParent()->getContext());
 331     Type *I8PtrTy = Type::getInt8PtrTy(MemI->getParent()->getContext(),
 332       BasePtr->getType()->getPointerAddressSpace());
 333
 334     const SCEV *BasePtrStartSCEV = BasePtrSCEV->getStart();
 335     if (!SE->isLoopInvariant(BasePtrStartSCEV, L))
 336       continue;
 337
 338     const SCEVConstant *BasePtrIncSCEV =
 339       dyn_cast<SCEVConstant>(BasePtrSCEV->getStepRecurrence(*SE));
 340     if (!BasePtrIncSCEV)
 341       continue;
 342     BasePtrStartSCEV = SE->getMinusSCEV(BasePtrStartSCEV, BasePtrIncSCEV);
 343     if (!isSafeToExpand(BasePtrStartSCEV, *SE))
 344       continue;
 345
 346     DEBUG(dbgs() << "PIP: New start is: " << *BasePtrStartSCEV << "\n");
 347
 348     PHINode *NewPHI = PHINode::Create(I8PtrTy, HeaderLoopPredCount,
 349       MemI->hasName() ? MemI->getName() + ".phi" : "",
 350       Header->getFirstNonPHI());
 351
 352     SCEVExpander SCEVE(*SE, Header->getModule()->getDataLayout(), "pistart");
 353     Value *BasePtrStart = SCEVE.expandCodeFor(BasePtrStartSCEV, I8PtrTy,
 354       LoopPredecessor->getTerminator());
 355
 356     // Note that LoopPredecessor might occur in the predecessor list multiple
 357     // times, and we need to add it the right number of times.
 358     for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
 359          PI != PE; ++PI) {
 360       if (*PI != LoopPredecessor)
 361         continue;
 362
 363       NewPHI->addIncoming(BasePtrStart, LoopPredecessor);
 364     }
 365
 366     Instruction *InsPoint = &*Header->getFirstInsertionPt();
 367     GetElementPtrInst *PtrInc = GetElementPtrInst::Create(
 368         I8Ty, NewPHI, BasePtrIncSCEV->getValue(),
 369         MemI->hasName() ? MemI->getName() + ".inc" : "", InsPoint);
 370     PtrInc->setIsInBounds(IsPtrInBounds(BasePtr));
 371     for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
 372          PI != PE; ++PI) {
 373       if (*PI == LoopPredecessor)
 374         continue;
 375
 376       NewPHI->addIncoming(PtrInc, *PI);
 377     }
 378
 379     Instruction *NewBasePtr;
 380     if (PtrInc->getType() != BasePtr->getType())
 381       NewBasePtr = new BitCastInst(PtrInc, BasePtr->getType(),
 382         PtrInc->hasName() ? PtrInc->getName() + ".cast" : "", InsPoint);
 383     else
 384       NewBasePtr = PtrInc;
 385
 386     if (Instruction *IDel = dyn_cast<Instruction>(BasePtr))
 387       BBChanged.insert(IDel->getParent());
 388     BasePtr->replaceAllUsesWith(NewBasePtr);
 389     RecursivelyDeleteTriviallyDeadInstructions(BasePtr);
 390
 391     // Keep track of the replacement pointer values we've inserted so that we
 392     // don't generate more pointer values than necessary.
 393     SmallPtrSet<Value *, 16> NewPtrs;
 394     NewPtrs.insert( NewBasePtr);
 395
 396     for (auto I = std::next(Buckets[i].Elements.begin()),
 397          IE = Buckets[i].Elements.end(); I != IE; ++I) {
 398       Value *Ptr = GetPointerOperand(I->Instr);
 399       assert(Ptr && "No pointer operand");
 400       if (NewPtrs.count(Ptr))
 401         continue;
 402
 403       Instruction *RealNewPtr;
 404       if (!I->Offset || I->Offset->getValue()->isZero()) {
 405         RealNewPtr = NewBasePtr;
 406       } else {
 407         Instruction *PtrIP = dyn_cast<Instruction>(Ptr);
 408         if (PtrIP && isa<Instruction>(NewBasePtr) &&
 409             cast<Instruction>(NewBasePtr)->getParent() == PtrIP->getParent())
 410           PtrIP = nullptr;
 411         else if (isa<PHINode>(PtrIP))
 412           PtrIP = &*PtrIP->getParent()->getFirstInsertionPt();
 413         else if (!PtrIP)
 414           PtrIP = I->Instr;
 415
 416         GetElementPtrInst *NewPtr = GetElementPtrInst::Create(
 417             I8Ty, PtrInc, I->Offset->getValue(),
 418             I->Instr->hasName() ? I->Instr->getName() + ".off" : "", PtrIP);
 419         if (!PtrIP)
 420           NewPtr->insertAfter(cast<Instruction>(PtrInc));
 421         NewPtr->setIsInBounds(IsPtrInBounds(Ptr));
 422         RealNewPtr = NewPtr;
 423       }
 424
 425       if (Instruction *IDel = dyn_cast<Instruction>(Ptr))
 426         BBChanged.insert(IDel->getParent());
 427
 428       Instruction *ReplNewPtr;
 429       if (Ptr->getType() != RealNewPtr->getType()) {
 430         ReplNewPtr = new BitCastInst(RealNewPtr, Ptr->getType(),
 431           Ptr->hasName() ? Ptr->getName() + ".cast" : "");
 432         ReplNewPtr->insertAfter(RealNewPtr);
 433       } else
 434         ReplNewPtr = RealNewPtr;
 435
 436       Ptr->replaceAllUsesWith(ReplNewPtr);
 437       RecursivelyDeleteTriviallyDeadInstructions(Ptr);
 438
 439       NewPtrs.insert(RealNewPtr);
 440     }
 441
 442     MadeChange = true;
 443   }
 444
 445   for (Loop::block_iterator I = L->block_begin(), IE = L->block_end();
 446        I != IE; ++I) {
 447     if (BBChanged.count(*I))
 448       DeleteDeadPHIs(*I);
 449   }
 450
 451   return MadeChange;
 452 }