lib/Transforms/Scalar/LoopIdiomRecognize.cpp

   1 //===-- LoopIdiomRecognize.cpp - Loop idiom recognition -------------------===//
   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 pass implements an idiom recognizer that transforms simple loops into a
  11 // non-loop form.  In cases that this kicks in, it can be a significant
  12 // performance win.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "loop-idiom"
  17 #include "llvm/Transforms/Scalar.h"
  18 #include "llvm/Analysis/LoopPass.h"
  19 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  20 #include "llvm/Analysis/ValueTracking.h"
  21 #include "llvm/Target/TargetData.h"
  22 #include "llvm/Support/Debug.h"
  23 #include "llvm/Support/raw_ostream.h"
  24 using namespace llvm;
  25
  26 // TODO: Recognize "N" size array multiplies: replace with call to blas or
  27 // something.
  28
  29 namespace {
  30   class LoopIdiomRecognize : public LoopPass {
  31     Loop *CurLoop;
  32     const TargetData *TD;
  33     ScalarEvolution *SE;
  34   public:
  35     static char ID;
  36     explicit LoopIdiomRecognize() : LoopPass(ID) {
  37       initializeLoopIdiomRecognizePass(*PassRegistry::getPassRegistry());
  38     }
  39
  40     bool runOnLoop(Loop *L, LPPassManager &LPM);
  41
  42     bool processLoopStore(StoreInst *SI, const SCEV *BECount);
  43
  44     /// This transformation requires natural loop information & requires that
  45     /// loop preheaders be inserted into the CFG.
  46     ///
  47     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  48       AU.addRequired<LoopInfo>();
  49       AU.addPreserved<LoopInfo>();
  50       AU.addRequiredID(LoopSimplifyID);
  51       AU.addPreservedID(LoopSimplifyID);
  52       AU.addRequiredID(LCSSAID);
  53       AU.addPreservedID(LCSSAID);
  54       AU.addRequired<ScalarEvolution>();
  55       AU.addPreserved<ScalarEvolution>();
  56       AU.addPreserved<DominatorTree>();
  57     }
  58   };
  59 }
  60
  61 char LoopIdiomRecognize::ID = 0;
  62 INITIALIZE_PASS_BEGIN(LoopIdiomRecognize, "loop-idiom", "Recognize loop idioms",
  63                       false, false)
  64 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
  65 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
  66 INITIALIZE_PASS_DEPENDENCY(LCSSA)
  67 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
  68 INITIALIZE_PASS_END(LoopIdiomRecognize, "loop-idiom", "Recognize loop idioms",
  69                     false, false)
  70
  71 Pass *llvm::createLoopIdiomPass() { return new LoopIdiomRecognize(); }
  72
  73 bool LoopIdiomRecognize::runOnLoop(Loop *L, LPPassManager &LPM) {
  74   CurLoop = L;
  75
  76   // We only look at trivial single basic block loops.
  77   // TODO: eventually support more complex loops, scanning the header.
  78   if (L->getBlocks().size() != 1)
  79     return false;
  80
  81   // The trip count of the loop must be analyzable.
  82   SE = &getAnalysis<ScalarEvolution>();
  83   if (!SE->hasLoopInvariantBackedgeTakenCount(L))
  84     return false;
  85   const SCEV *BECount = SE->getBackedgeTakenCount(L);
  86   if (isa<SCEVCouldNotCompute>(BECount)) return false;
  87
  88   // We require target data for now.
  89   TD = getAnalysisIfAvailable<TargetData>();
  90   if (TD == 0) return false;
  91
  92   BasicBlock *BB = L->getHeader();
  93   DEBUG(dbgs() << "loop-idiom Scanning: F[" << BB->getParent()->getName()
  94                << "] Loop %" << BB->getName() << "\n");
  95
  96   bool MadeChange = false;
  97   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
  98     // Look for store instructions, which may be memsets.
  99     if (StoreInst *SI = dyn_cast<StoreInst>(I++))
 100       MadeChange |= processLoopStore(SI, BECount);
 101   }
 102
 103   return MadeChange;
 104 }
 105
 106 /// scanBlock - Look over a block to see if we can promote anything out of it.
 107 bool LoopIdiomRecognize::processLoopStore(StoreInst *SI, const SCEV *BECount) {
 108   Value *StoredVal = SI->getValueOperand();
 109
 110   // Check to see if the store updates all bits in memory.  We don't want to
 111   // process things like a store of i3.  We also require that the store be a
 112   // multiple of a byte.
 113   uint64_t SizeInBits = TD->getTypeSizeInBits(StoredVal->getType());
 114   if ((SizeInBits & 7) || (SizeInBits >> 32) != 0 ||
 115       SizeInBits != TD->getTypeStoreSizeInBits(StoredVal->getType()))
 116     return false;
 117
 118   // See if the pointer expression is an AddRec like {base,+,1} on the current
 119   // loop, which indicates a strided store.  If we have something else, it's a
 120   // random store we can't handle.
 121   const SCEVAddRecExpr *Ev =
 122     dyn_cast<SCEVAddRecExpr>(SE->getSCEV(SI->getPointerOperand()));
 123   if (Ev == 0 || Ev->getLoop() != CurLoop || !Ev->isAffine())
 124     return false;
 125
 126   // Check to see if the stride matches the size of the store.  If so, then we
 127   // know that every byte is touched in the loop.
 128   unsigned StoreSize = (unsigned)SizeInBits >> 3;
 129   const SCEVConstant *Stride = dyn_cast<SCEVConstant>(Ev->getOperand(1));
 130   if (Stride == 0 || StoreSize != Stride->getValue()->getValue())
 131     return false;
 132
 133   errs() << "Found strided store: " << *Ev << "\n";
 134
 135   // Check for memcpy here.
 136
 137
 138   // If the stored value is a byte-wise value (like i32 -1), then it may be
 139   // turned into a memset of i8 -1, assuming that all the consequtive bytes
 140   // are stored.  A store of i32 0x01020304 can never be turned into a memset.
 141   Value *SplatValue = isBytewiseValue(StoredVal);
 142   if (SplatValue == 0) return false;
 143
 144
 145   return false;
 146 }
 147