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/Support/Debug.h"
  21 #include "llvm/Support/raw_ostream.h"
  22 using namespace llvm;
  23
  24 // TODO: Recognize "N" size array multiplies: replace with call to blas or
  25 // something.
  26
  27 namespace {
  28   class LoopIdiomRecognize : public LoopPass {
  29   public:
  30     static char ID;
  31     explicit LoopIdiomRecognize() : LoopPass(ID) {
  32       initializeLoopIdiomRecognizePass(*PassRegistry::getPassRegistry());
  33     }
  34
  35     bool runOnLoop(Loop *L, LPPassManager &LPM);
  36
  37     bool scanBlock(BasicBlock *BB, Loop *L);
  38
  39     /// This transformation requires natural loop information & requires that
  40     /// loop preheaders be inserted into the CFG.
  41     ///
  42     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  43       AU.addRequired<LoopInfo>();
  44       AU.addPreserved<LoopInfo>();
  45       AU.addRequiredID(LoopSimplifyID);
  46       AU.addPreservedID(LoopSimplifyID);
  47       AU.addRequiredID(LCSSAID);
  48       AU.addPreservedID(LCSSAID);
  49       AU.addRequired<ScalarEvolution>();
  50       AU.addPreserved<ScalarEvolution>();
  51       AU.addPreserved<DominatorTree>();
  52     }
  53   };
  54 }
  55
  56 char LoopIdiomRecognize::ID = 0;
  57 INITIALIZE_PASS_BEGIN(LoopIdiomRecognize, "loop-idiom", "Recognize loop idioms",
  58                       false, false)
  59 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
  60 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
  61 INITIALIZE_PASS_DEPENDENCY(LCSSA)
  62 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
  63 INITIALIZE_PASS_END(LoopIdiomRecognize, "loop-idiom", "Recognize loop idioms",
  64                     false, false)
  65
  66 Pass *llvm::createLoopIdiomPass() { return new LoopIdiomRecognize(); }
  67
  68 bool LoopIdiomRecognize::runOnLoop(Loop *L, LPPassManager &LPM) {
  69   // We only look at trivial single basic block loops.
  70   // TODO: eventually support more complex loops, scanning the header.
  71   if (L->getBlocks().size() != 1)
  72     return false;
  73
  74   BasicBlock *BB = L->getHeader();
  75   DEBUG(dbgs() << "Loop Idiom Recognize: F[" << BB->getParent()->getName()
  76                << "] Loop %" << BB->getName() << "\n");
  77
  78   return scanBlock(BB, L);
  79 }
  80
  81 /// scanBlock - Look over a block to see if we can promote anything out of it.
  82 bool LoopIdiomRecognize::scanBlock(BasicBlock *BB, Loop *L) {
  83   ScalarEvolution &SE = getAnalysis<ScalarEvolution>();
  84
  85   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
  86     // Look for store instructions, which may be memsets.
  87     StoreInst *SI = dyn_cast<StoreInst>(I++);
  88     if (SI == 0) continue;
  89
  90     // See if the pointer expression is an AddRec like {base,+,1} on the current
  91     // loop, which indicates a strided store.  If we have something else, it's a
  92     // random store we can't handle.
  93     const SCEVAddRecExpr *Ev =
  94       dyn_cast<SCEVAddRecExpr>(SE.getSCEV(SI->getPointerOperand()));
  95     if (Ev == 0 || Ev->getLoop() != L)
  96       continue;
  97
  98     errs() << "Found strided store: " << *Ev << "\n";
  99   }
 100
 101   return false;
 102 }
 103