lib/Transforms/Vectorize/SLPVectorizer.cpp

   1 //===- SLPVectorizer.cpp - A bottom up SLP Vectorizer ---------------------===//
   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 // This pass implements the Bottom Up SLP vectorizer. It detects consecutive
  10 // stores that can be put together into vector-stores. Next, it attempts to
  11 // construct vectorizable tree using the use-def chains. If a profitable tree
  12 // was found, the SLP vectorizer performs vectorization on the tree.
  13 //
  14 // The pass is inspired by the work described in the paper:
  15 //  "Loop-Aware SLP in GCC" by Ira Rosen, Dorit Nuzman, Ayal Zaks.
  16 //
  17 //===----------------------------------------------------------------------===//
  18 #define SV_NAME "slp-vectorizer"
  19 #define DEBUG_TYPE SV_NAME
  20
  21 #include "VecUtils.h"
  22 #include "llvm/Transforms/Vectorize.h"
  23 #include "llvm/Analysis/AliasAnalysis.h"
  24 #include "llvm/Analysis/ScalarEvolution.h"
  25 #include "llvm/Analysis/TargetTransformInfo.h"
  26 #include "llvm/Analysis/Verifier.h"
  27 #include "llvm/IR/DataLayout.h"
  28 #include "llvm/IR/Instructions.h"
  29 #include "llvm/IR/Module.h"
  30 #include "llvm/IR/Type.h"
  31 #include "llvm/IR/Value.h"
  32 #include "llvm/Pass.h"
  33 #include "llvm/Support/CommandLine.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Support/raw_ostream.h"
  36 #include <map>
  37
  38 using namespace llvm;
  39
  40 static cl::opt<int>
  41 SLPCostThreshold("slp-threshold", cl::init(1), cl::Hidden,
  42                  cl::desc("Only vectorize trees if the gain is above this "
  43                           "number. (gain = -cost of vectorization)"));
  44 namespace {
  45
  46 /// The SLPVectorizer Pass.
  47 struct SLPVectorizer : public BasicBlockPass {
  48   typedef std::map<Value*, BoUpSLP::StoreList> StoreListMap;
  49
  50   /// Pass identification, replacement for typeid
  51   static char ID;
  52
  53   explicit SLPVectorizer() : BasicBlockPass(ID) {
  54     initializeSLPVectorizerPass(*PassRegistry::getPassRegistry());
  55   }
  56
  57   ScalarEvolution *SE;
  58   DataLayout *DL;
  59   TargetTransformInfo *TTI;
  60   AliasAnalysis *AA;
  61
  62   /// \brief Collect memory references and sort them according to their base
  63   /// object. We sort the stores to their base objects to reduce the cost of the
  64   /// quadratic search on the stores. TODO: We can further reduce this cost
  65   /// if we flush the chain creation every time we run into a memory barrier.
  66   bool CollectStores(BasicBlock *BB, BoUpSLP &R) {
  67     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
  68       StoreInst *SI = dyn_cast<StoreInst>(it);
  69       if (!SI)
  70         continue;
  71
  72       // Check that the pointer points to scalars.
  73       if (SI->getValueOperand()->getType()->isAggregateType())
  74         return false;
  75
  76       // Find the base of the GEP.
  77       Value *Ptr = SI->getPointerOperand();
  78       if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr))
  79         Ptr = GEP->getPointerOperand();
  80
  81       // Save the store locations.
  82       StoreRefs[Ptr].push_back(SI);
  83     }
  84     return true;
  85   }
  86
  87   bool RollStoreChains(BoUpSLP &R) {
  88     bool Changed = false;
  89     // Attempt to sort and vectorize each of the store-groups.
  90     for (StoreListMap::iterator it = StoreRefs.begin(), e = StoreRefs.end();
  91          it != e; ++it) {
  92       if (it->second.size() < 2)
  93         continue;
  94
  95       DEBUG(dbgs()<<"SLP: Analyzing a store chain of length " <<
  96             it->second.size() << ".\n");
  97
  98       Changed |= R.vectorizeStores(it->second, -SLPCostThreshold);
  99     }
 100     return Changed;
 101   }
 102
 103   virtual bool runOnBasicBlock(BasicBlock &BB) {
 104     SE = &getAnalysis<ScalarEvolution>();
 105     DL = getAnalysisIfAvailable<DataLayout>();
 106     TTI = &getAnalysis<TargetTransformInfo>();
 107     AA = &getAnalysis<AliasAnalysis>();
 108     StoreRefs.clear();
 109
 110     // Must have DataLayout. We can't require it because some tests run w/o
 111     // triple.
 112     if (!DL)
 113       return false;
 114
 115     // Use the bollom up slp vectorizer to construct chains that start with
 116     // he store instructions.
 117     BoUpSLP R(&BB, SE, DL, TTI, AA);
 118
 119     if (!CollectStores(&BB, R))
 120       return false;
 121
 122     bool Changed = RollStoreChains(R);
 123     if (Changed) {
 124       DEBUG(dbgs()<<"SLP: vectorized in \""<<BB.getParent()->getName()<<"\"\n");
 125       DEBUG(verifyFunction(*BB.getParent()));
 126     }
 127
 128     return Changed;
 129   }
 130
 131   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 132     BasicBlockPass::getAnalysisUsage(AU);
 133     AU.addRequired<ScalarEvolution>();
 134     AU.addRequired<AliasAnalysis>();
 135     AU.addRequired<TargetTransformInfo>();
 136   }
 137
 138 private:
 139   StoreListMap StoreRefs;
 140 };
 141
 142 } // end anonymous namespace
 143
 144 char SLPVectorizer::ID = 0;
 145 static const char lv_name[] = "SLP Vectorizer";
 146 INITIALIZE_PASS_BEGIN(SLPVectorizer, SV_NAME, lv_name, false, false)
 147 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 148 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
 149 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
 150 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 151 INITIALIZE_PASS_END(SLPVectorizer, SV_NAME, lv_name, false, false)
 152
 153 namespace llvm {
 154   Pass *createSLPVectorizerPass() {
 155     return new SLPVectorizer();
 156   }
 157 }
 158