SLPVectorizer: Improve the cost model for loop invariant broadcast values.
[oota-llvm.git] / 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/Analysis/LoopInfo.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/IntrinsicInst.h"
31 #include "llvm/IR/Module.h"
32 #include "llvm/IR/Type.h"
33 #include "llvm/IR/Value.h"
34 #include "llvm/Pass.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/raw_ostream.h"
38 #include <map>
39
40 using namespace llvm;
41
42 static cl::opt<int>
43 SLPCostThreshold("slp-threshold", cl::init(0), cl::Hidden,
44                  cl::desc("Only vectorize trees if the gain is above this "
45                           "number. (gain = -cost of vectorization)"));
46 namespace {
47
48 /// The SLPVectorizer Pass.
49 struct SLPVectorizer : public FunctionPass {
50   typedef std::map<Value*, BoUpSLP::StoreList> StoreListMap;
51
52   /// Pass identification, replacement for typeid
53   static char ID;
54
55   explicit SLPVectorizer() : FunctionPass(ID) {
56     initializeSLPVectorizerPass(*PassRegistry::getPassRegistry());
57   }
58
59   ScalarEvolution *SE;
60   DataLayout *DL;
61   TargetTransformInfo *TTI;
62   AliasAnalysis *AA;
63   LoopInfo *LI;
64
65   virtual bool runOnFunction(Function &F) {
66     SE = &getAnalysis<ScalarEvolution>();
67     DL = getAnalysisIfAvailable<DataLayout>();
68     TTI = &getAnalysis<TargetTransformInfo>();
69     AA = &getAnalysis<AliasAnalysis>();
70     LI = &getAnalysis<LoopInfo>();
71
72     StoreRefs.clear();
73     bool Changed = false;
74
75     // Must have DataLayout. We can't require it because some tests run w/o
76     // triple.
77     if (!DL)
78       return false;
79
80     for (Function::iterator it = F.begin(), e = F.end(); it != e; ++it) {
81       BasicBlock *BB = it;
82       bool BBChanged = false;
83
84       // Use the bollom up slp vectorizer to construct chains that start with
85       // he store instructions.
86       BoUpSLP R(BB, SE, DL, TTI, AA, LI->getLoopFor(BB));
87
88       // Vectorize trees that end at reductions.
89       BBChanged |= vectorizeReductions(BB, R);
90
91       // Vectorize trees that end at stores.
92       if (unsigned count = collectStores(BB, R)) {
93         DEBUG(dbgs()<<"SLP: Found " << count << " stores to vectorize.\n");
94         BBChanged |= vectorizeStoreChains(R);
95       }
96
97       // Try to hoist some of the scalarization code to the preheader.
98       if (BBChanged) hoistGatherSequence(LI, BB, R);
99
100       Changed |= BBChanged;
101     }
102
103     if (Changed) {
104       DEBUG(dbgs()<<"SLP: vectorized \""<<F.getName()<<"\"\n");
105       DEBUG(verifyFunction(F));
106     }
107     return Changed;
108   }
109
110   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
111     FunctionPass::getAnalysisUsage(AU);
112     AU.addRequired<ScalarEvolution>();
113     AU.addRequired<AliasAnalysis>();
114     AU.addRequired<TargetTransformInfo>();
115     AU.addRequired<LoopInfo>();
116   }
117
118 private:
119
120   /// \brief Collect memory references and sort them according to their base
121   /// object. We sort the stores to their base objects to reduce the cost of the
122   /// quadratic search on the stores. TODO: We can further reduce this cost
123   /// if we flush the chain creation every time we run into a memory barrier.
124   unsigned collectStores(BasicBlock *BB, BoUpSLP &R);
125
126   /// \brief Try to vectorize a chain that starts at two arithmetic instrs.
127   bool tryToVectorizePair(Value *A, Value *B,  BoUpSLP &R);
128
129   /// \brief Try to vectorize a chain that may start at the operands of \V;
130   bool tryToVectorize(BinaryOperator *V,  BoUpSLP &R);
131
132   /// \brief Vectorize the stores that were collected in StoreRefs.
133   bool vectorizeStoreChains(BoUpSLP &R);
134
135   /// \brief Try to hoist gather sequences outside of the loop in cases where
136   /// all of the sources are loop invariant.
137   void hoistGatherSequence(LoopInfo *LI, BasicBlock *BB, BoUpSLP &R);
138
139   /// \brief Scan the basic block and look for reductions that may start a
140   /// vectorization chain.
141   bool vectorizeReductions(BasicBlock *BB, BoUpSLP &R);
142
143 private:
144   StoreListMap StoreRefs;
145 };
146
147 unsigned SLPVectorizer::collectStores(BasicBlock *BB, BoUpSLP &R) {
148   unsigned count = 0;
149   StoreRefs.clear();
150   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
151     StoreInst *SI = dyn_cast<StoreInst>(it);
152     if (!SI)
153       continue;
154
155     // Check that the pointer points to scalars.
156     if (SI->getValueOperand()->getType()->isAggregateType())
157       return 0;
158
159     // Find the base of the GEP.
160     Value *Ptr = SI->getPointerOperand();
161     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr))
162       Ptr = GEP->getPointerOperand();
163
164     // Save the store locations.
165     StoreRefs[Ptr].push_back(SI);
166     count++;
167   }
168   return count;
169 }
170
171 bool SLPVectorizer::tryToVectorizePair(Value *A, Value *B,  BoUpSLP &R) {
172   if (!A || !B) return false;
173   BoUpSLP::ValueList VL;
174   VL.push_back(A);
175   VL.push_back(B);
176   int Cost = R.getTreeCost(VL);
177   int ExtrCost = R.getScalarizationCost(VL);
178   DEBUG(dbgs()<<"SLP: Cost of pair:" << Cost <<
179         " Cost of extract:" << ExtrCost << ".\n");
180   if ((Cost+ExtrCost) >= -SLPCostThreshold) return false;
181   DEBUG(dbgs()<<"SLP: Vectorizing pair.\n");
182   R.vectorizeArith(VL);
183   return true;
184 }
185
186 bool SLPVectorizer::tryToVectorize(BinaryOperator *V,  BoUpSLP &R) {
187   if (!V) return false;
188   // Try to vectorize V.
189   if (tryToVectorizePair(V->getOperand(0), V->getOperand(1), R))
190     return true;
191
192   BinaryOperator *A = dyn_cast<BinaryOperator>(V->getOperand(0));
193   BinaryOperator *B = dyn_cast<BinaryOperator>(V->getOperand(1));
194   // Try to skip B.
195   if (B && B->hasOneUse()) {
196     BinaryOperator *B0 = dyn_cast<BinaryOperator>(B->getOperand(0));
197     BinaryOperator *B1 = dyn_cast<BinaryOperator>(B->getOperand(1));
198     if (tryToVectorizePair(A, B0, R)) {
199       B->moveBefore(V);
200       return true;
201     }
202     if (tryToVectorizePair(A, B1, R)) {
203       B->moveBefore(V);
204       return true;
205     }
206   }
207
208   // Try to slip A.
209   if (A && A->hasOneUse()) {
210     BinaryOperator *A0 = dyn_cast<BinaryOperator>(A->getOperand(0));
211     BinaryOperator *A1 = dyn_cast<BinaryOperator>(A->getOperand(1));
212     if (tryToVectorizePair(A0, B, R)) {
213       A->moveBefore(V);
214       return true;
215     }
216     if (tryToVectorizePair(A1, B, R)) {
217       A->moveBefore(V);
218       return true;
219     }
220   }
221   return 0;
222 }
223
224 bool SLPVectorizer::vectorizeReductions(BasicBlock *BB, BoUpSLP &R) {
225   bool Changed = false;
226   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
227     if (isa<DbgInfoIntrinsic>(it)) continue;
228
229     // Try to vectorize reductions that use PHINodes.
230     if (PHINode *P = dyn_cast<PHINode>(it)) {
231       // Check that the PHI is a reduction PHI.
232       if (P->getNumIncomingValues() != 2) return Changed;
233       Value *Rdx = (P->getIncomingBlock(0) == BB ? P->getIncomingValue(0) :
234                     (P->getIncomingBlock(1) == BB ? P->getIncomingValue(1) :
235                      0));
236       // Check if this is a Binary Operator.
237       BinaryOperator *BI = dyn_cast_or_null<BinaryOperator>(Rdx);
238       if (!BI)
239         continue;
240
241       Value *Inst = BI->getOperand(0);
242       if (Inst == P) Inst = BI->getOperand(1);
243       Changed |= tryToVectorize(dyn_cast<BinaryOperator>(Inst), R);
244       continue;
245     }
246
247     // Try to vectorize trees that start at compare instructions.
248     if (CmpInst *CI = dyn_cast<CmpInst>(it)) {
249       if (tryToVectorizePair(CI->getOperand(0), CI->getOperand(1), R)) {
250         Changed |= true;
251         continue;
252       }
253       for (int i = 0; i < 2; ++i)
254         if (BinaryOperator *BI = dyn_cast<BinaryOperator>(CI->getOperand(i)))
255           Changed |= tryToVectorize(BI, R);
256       continue;
257     }
258   }
259
260   return Changed;
261 }
262
263 bool SLPVectorizer::vectorizeStoreChains(BoUpSLP &R) {
264   bool Changed = false;
265   // Attempt to sort and vectorize each of the store-groups.
266   for (StoreListMap::iterator it = StoreRefs.begin(), e = StoreRefs.end();
267        it != e; ++it) {
268     if (it->second.size() < 2)
269       continue;
270
271     DEBUG(dbgs()<<"SLP: Analyzing a store chain of length " <<
272           it->second.size() << ".\n");
273
274     Changed |= R.vectorizeStores(it->second, -SLPCostThreshold);
275   }
276   return Changed;
277 }
278
279 void SLPVectorizer::hoistGatherSequence(LoopInfo *LI, BasicBlock *BB,
280                                         BoUpSLP &R) {
281   // Check if this block is inside a loop.
282   Loop *L = LI->getLoopFor(BB);
283   if (!L)
284     return;
285
286   // Check if it has a preheader.
287   BasicBlock *PreHeader = L->getLoopPreheader();
288   if (!PreHeader)
289     return;
290
291   // Mark the insertion point for the block.
292   Instruction *Location = PreHeader->getTerminator();
293
294   BoUpSLP::ValueList &Gathers = R.getGatherSeqInstructions();
295   for (BoUpSLP::ValueList::iterator it = Gathers.begin(), e = Gathers.end();
296        it != e; ++it) {
297     InsertElementInst *Insert = dyn_cast<InsertElementInst>(*it);
298
299     // The InsertElement sequence can be simplified into a constant.
300     if (!Insert)
301       continue;
302
303     // If the vector or the element that we insert into it are
304     // instructions that are defined in this basic block then we can't
305     // hoist this instruction.
306     Instruction *CurrVec = dyn_cast<Instruction>(Insert->getOperand(0));
307     Instruction *NewElem = dyn_cast<Instruction>(Insert->getOperand(1));
308     if (CurrVec && L->contains(CurrVec)) continue;
309     if (NewElem && L->contains(NewElem)) continue;
310
311     // We can hoist this instruction. Move it to the pre-header.
312     Insert->moveBefore(Location);
313   }
314 }
315
316 } // end anonymous namespace
317
318 char SLPVectorizer::ID = 0;
319 static const char lv_name[] = "SLP Vectorizer";
320 INITIALIZE_PASS_BEGIN(SLPVectorizer, SV_NAME, lv_name, false, false)
321 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
322 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
323 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
324 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
325 INITIALIZE_PASS_END(SLPVectorizer, SV_NAME, lv_name, false, false)
326
327 namespace llvm {
328   Pass *createSLPVectorizerPass() {
329     return new SLPVectorizer();
330   }
331 }
332