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       Changed |= R.vectorizeStores(it->second, -SLPCostThreshold);
  95     }
  96     return Changed;
  97   }
  98
  99   virtual bool runOnBasicBlock(BasicBlock &BB) {
 100     SE = &getAnalysis<ScalarEvolution>();
 101     DL = getAnalysisIfAvailable<DataLayout>();
 102     TTI = &getAnalysis<TargetTransformInfo>();
 103     AA = &getAnalysis<AliasAnalysis>();
 104     StoreRefs.clear();
 105
 106     // Must have DataLayout. We can't require it because some tests run w/o
 107     // triple.
 108     if (!DL)
 109       return false;
 110
 111     // Use the bollom up slp vectorizer to construct chains that start with
 112     // he store instructions.
 113     BoUpSLP R(&BB, SE, DL, TTI, AA);
 114
 115     if (!CollectStores(&BB, R))
 116       return false;
 117
 118     bool Changed = RollStoreChains(R);
 119     if (Changed) {
 120       DEBUG(dbgs()<<"Rolled chains in \""<<BB.getParent()->getName()<<"\"\n");
 121       DEBUG(verifyFunction(*BB.getParent()));
 122     }
 123
 124     return Changed;
 125   }
 126
 127   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 128     BasicBlockPass::getAnalysisUsage(AU);
 129     AU.addRequired<ScalarEvolution>();
 130     AU.addRequired<AliasAnalysis>();
 131     AU.addRequired<TargetTransformInfo>();
 132   }
 133
 134 private:
 135   StoreListMap StoreRefs;
 136 };
 137
 138 } // end anonymous namespace
 139
 140 char SLPVectorizer::ID = 0;
 141 static const char lv_name[] = "SLP Vectorizer";
 142 INITIALIZE_PASS_BEGIN(SLPVectorizer, SV_NAME, lv_name, false, false)
 143 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 144 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
 145 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
 146 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 147 INITIALIZE_PASS_END(SLPVectorizer, SV_NAME, lv_name, false, false)
 148
 149 namespace llvm {
 150   Pass *createSLPVectorizerPass() {
 151     return new SLPVectorizer();
 152   }
 153 }
 154