[Modules] Move the LLVM IR pattern match header into the IR library, it
[oota-llvm.git] / lib / Transforms / Vectorize / LoopVectorize.cpp
1 //===- LoopVectorize.cpp - A Loop 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 //
10 // This is the LLVM loop vectorizer. This pass modifies 'vectorizable' loops
11 // and generates target-independent LLVM-IR.
12 // The vectorizer uses the TargetTransformInfo analysis to estimate the costs
13 // of instructions in order to estimate the profitability of vectorization.
14 //
15 // The loop vectorizer combines consecutive loop iterations into a single
16 // 'wide' iteration. After this transformation the index is incremented
17 // by the SIMD vector width, and not by one.
18 //
19 // This pass has three parts:
20 // 1. The main loop pass that drives the different parts.
21 // 2. LoopVectorizationLegality - A unit that checks for the legality
22 //    of the vectorization.
23 // 3. InnerLoopVectorizer - A unit that performs the actual
24 //    widening of instructions.
25 // 4. LoopVectorizationCostModel - A unit that checks for the profitability
26 //    of vectorization. It decides on the optimal vector width, which
27 //    can be one, if vectorization is not profitable.
28 //
29 //===----------------------------------------------------------------------===//
30 //
31 // The reduction-variable vectorization is based on the paper:
32 //  D. Nuzman and R. Henderson. Multi-platform Auto-vectorization.
33 //
34 // Variable uniformity checks are inspired by:
35 //  Karrenberg, R. and Hack, S. Whole Function Vectorization.
36 //
37 // Other ideas/concepts are from:
38 //  A. Zaks and D. Nuzman. Autovectorization in GCC-two years later.
39 //
40 //  S. Maleki, Y. Gao, M. Garzaran, T. Wong and D. Padua.  An Evaluation of
41 //  Vectorizing Compilers.
42 //
43 //===----------------------------------------------------------------------===//
44
45 #define LV_NAME "loop-vectorize"
46 #define DEBUG_TYPE LV_NAME
47
48 #include "llvm/Transforms/Vectorize.h"
49 #include "llvm/ADT/DenseMap.h"
50 #include "llvm/ADT/EquivalenceClasses.h"
51 #include "llvm/ADT/Hashing.h"
52 #include "llvm/ADT/MapVector.h"
53 #include "llvm/ADT/SetVector.h"
54 #include "llvm/ADT/SmallPtrSet.h"
55 #include "llvm/ADT/SmallSet.h"
56 #include "llvm/ADT/SmallVector.h"
57 #include "llvm/ADT/StringExtras.h"
58 #include "llvm/Analysis/AliasAnalysis.h"
59 #include "llvm/Analysis/BlockFrequencyInfo.h"
60 #include "llvm/Analysis/LoopInfo.h"
61 #include "llvm/Analysis/LoopIterator.h"
62 #include "llvm/Analysis/LoopPass.h"
63 #include "llvm/Analysis/ScalarEvolution.h"
64 #include "llvm/Analysis/ScalarEvolutionExpander.h"
65 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
66 #include "llvm/Analysis/TargetTransformInfo.h"
67 #include "llvm/Analysis/ValueTracking.h"
68 #include "llvm/IR/Constants.h"
69 #include "llvm/IR/DataLayout.h"
70 #include "llvm/IR/DerivedTypes.h"
71 #include "llvm/IR/Dominators.h"
72 #include "llvm/IR/Function.h"
73 #include "llvm/IR/IRBuilder.h"
74 #include "llvm/IR/Instructions.h"
75 #include "llvm/IR/IntrinsicInst.h"
76 #include "llvm/IR/LLVMContext.h"
77 #include "llvm/IR/Module.h"
78 #include "llvm/IR/PatternMatch.h"
79 #include "llvm/IR/Type.h"
80 #include "llvm/IR/Value.h"
81 #include "llvm/IR/Verifier.h"
82 #include "llvm/Pass.h"
83 #include "llvm/Support/BranchProbability.h"
84 #include "llvm/Support/CommandLine.h"
85 #include "llvm/Support/Debug.h"
86 #include "llvm/Support/ValueHandle.h"
87 #include "llvm/Support/raw_ostream.h"
88 #include "llvm/Target/TargetLibraryInfo.h"
89 #include "llvm/Transforms/Scalar.h"
90 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
91 #include "llvm/Transforms/Utils/Local.h"
92 #include <algorithm>
93 #include <map>
94
95 using namespace llvm;
96 using namespace llvm::PatternMatch;
97
98 static cl::opt<unsigned>
99 VectorizationFactor("force-vector-width", cl::init(0), cl::Hidden,
100                     cl::desc("Sets the SIMD width. Zero is autoselect."));
101
102 static cl::opt<unsigned>
103 VectorizationUnroll("force-vector-unroll", cl::init(0), cl::Hidden,
104                     cl::desc("Sets the vectorization unroll count. "
105                              "Zero is autoselect."));
106
107 static cl::opt<bool>
108 EnableIfConversion("enable-if-conversion", cl::init(true), cl::Hidden,
109                    cl::desc("Enable if-conversion during vectorization."));
110
111 /// We don't vectorize loops with a known constant trip count below this number.
112 static cl::opt<unsigned>
113 TinyTripCountVectorThreshold("vectorizer-min-trip-count", cl::init(16),
114                              cl::Hidden,
115                              cl::desc("Don't vectorize loops with a constant "
116                                       "trip count that is smaller than this "
117                                       "value."));
118
119 /// This enables versioning on the strides of symbolically striding memory
120 /// accesses in code like the following.
121 ///   for (i = 0; i < N; ++i)
122 ///     A[i * Stride1] += B[i * Stride2] ...
123 ///
124 /// Will be roughly translated to
125 ///    if (Stride1 == 1 && Stride2 == 1) {
126 ///      for (i = 0; i < N; i+=4)
127 ///       A[i:i+3] += ...
128 ///    } else
129 ///      ...
130 static cl::opt<bool> EnableMemAccessVersioning(
131     "enable-mem-access-versioning", cl::init(true), cl::Hidden,
132     cl::desc("Enable symblic stride memory access versioning"));
133
134 /// We don't unroll loops with a known constant trip count below this number.
135 static const unsigned TinyTripCountUnrollThreshold = 128;
136
137 /// When performing memory disambiguation checks at runtime do not make more
138 /// than this number of comparisons.
139 static const unsigned RuntimeMemoryCheckThreshold = 8;
140
141 /// Maximum simd width.
142 static const unsigned MaxVectorWidth = 64;
143
144 static cl::opt<unsigned> ForceTargetNumScalarRegs(
145     "force-target-num-scalar-regs", cl::init(0), cl::Hidden,
146     cl::desc("A flag that overrides the target's number of scalar registers."));
147
148 static cl::opt<unsigned> ForceTargetNumVectorRegs(
149     "force-target-num-vector-regs", cl::init(0), cl::Hidden,
150     cl::desc("A flag that overrides the target's number of vector registers."));
151
152 /// Maximum vectorization unroll count.
153 static const unsigned MaxUnrollFactor = 16;
154
155 static cl::opt<unsigned> ForceTargetMaxScalarUnrollFactor(
156     "force-target-max-scalar-unroll", cl::init(0), cl::Hidden,
157     cl::desc("A flag that overrides the target's max unroll factor for scalar "
158              "loops."));
159
160 static cl::opt<unsigned> ForceTargetMaxVectorUnrollFactor(
161     "force-target-max-vector-unroll", cl::init(0), cl::Hidden,
162     cl::desc("A flag that overrides the target's max unroll factor for "
163              "vectorized loops."));
164
165 static cl::opt<unsigned> ForceTargetInstructionCost(
166     "force-target-instruction-cost", cl::init(0), cl::Hidden,
167     cl::desc("A flag that overrides the target's expected cost for "
168              "an instruction to a single constant value. Mostly "
169              "useful for getting consistent testing."));
170
171 static cl::opt<unsigned> SmallLoopCost(
172     "small-loop-cost", cl::init(20), cl::Hidden,
173     cl::desc("The cost of a loop that is considered 'small' by the unroller."));
174
175 static cl::opt<bool> LoopVectorizeWithBlockFrequency(
176     "loop-vectorize-with-block-frequency", cl::init(false), cl::Hidden,
177     cl::desc("Enable the use of the block frequency analysis to access PGO "
178              "heuristics minimizing code growth in cold regions and being more "
179              "aggressive in hot regions."));
180
181 // Runtime unroll loops for load/store throughput.
182 static cl::opt<bool> EnableLoadStoreRuntimeUnroll(
183     "enable-loadstore-runtime-unroll", cl::init(true), cl::Hidden,
184     cl::desc("Enable runtime unrolling until load/store ports are saturated"));
185
186 /// The number of stores in a loop that are allowed to need predication.
187 static cl::opt<unsigned> NumberOfStoresToPredicate(
188     "vectorize-num-stores-pred", cl::init(1), cl::Hidden,
189     cl::desc("Max number of stores to be predicated behind an if."));
190
191 static cl::opt<bool> EnableIndVarRegisterHeur(
192     "enable-ind-var-reg-heur", cl::init(true), cl::Hidden,
193     cl::desc("Count the induction variable only once when unrolling"));
194
195 static cl::opt<bool> EnableCondStoresVectorization(
196     "enable-cond-stores-vec", cl::init(false), cl::Hidden,
197     cl::desc("Enable if predication of stores during vectorization."));
198
199 namespace {
200
201 // Forward declarations.
202 class LoopVectorizationLegality;
203 class LoopVectorizationCostModel;
204
205 /// InnerLoopVectorizer vectorizes loops which contain only one basic
206 /// block to a specified vectorization factor (VF).
207 /// This class performs the widening of scalars into vectors, or multiple
208 /// scalars. This class also implements the following features:
209 /// * It inserts an epilogue loop for handling loops that don't have iteration
210 ///   counts that are known to be a multiple of the vectorization factor.
211 /// * It handles the code generation for reduction variables.
212 /// * Scalarization (implementation using scalars) of un-vectorizable
213 ///   instructions.
214 /// InnerLoopVectorizer does not perform any vectorization-legality
215 /// checks, and relies on the caller to check for the different legality
216 /// aspects. The InnerLoopVectorizer relies on the
217 /// LoopVectorizationLegality class to provide information about the induction
218 /// and reduction variables that were found to a given vectorization factor.
219 class InnerLoopVectorizer {
220 public:
221   InnerLoopVectorizer(Loop *OrigLoop, ScalarEvolution *SE, LoopInfo *LI,
222                       DominatorTree *DT, const DataLayout *DL,
223                       const TargetLibraryInfo *TLI, unsigned VecWidth,
224                       unsigned UnrollFactor)
225       : OrigLoop(OrigLoop), SE(SE), LI(LI), DT(DT), DL(DL), TLI(TLI),
226         VF(VecWidth), UF(UnrollFactor), Builder(SE->getContext()), Induction(0),
227         OldInduction(0), WidenMap(UnrollFactor), Legal(0) {}
228
229   // Perform the actual loop widening (vectorization).
230   void vectorize(LoopVectorizationLegality *L) {
231     Legal = L;
232     // Create a new empty loop. Unlink the old loop and connect the new one.
233     createEmptyLoop();
234     // Widen each instruction in the old loop to a new one in the new loop.
235     // Use the Legality module to find the induction and reduction variables.
236     vectorizeLoop();
237     // Register the new loop and update the analysis passes.
238     updateAnalysis();
239   }
240
241   virtual ~InnerLoopVectorizer() {}
242
243 protected:
244   /// A small list of PHINodes.
245   typedef SmallVector<PHINode*, 4> PhiVector;
246   /// When we unroll loops we have multiple vector values for each scalar.
247   /// This data structure holds the unrolled and vectorized values that
248   /// originated from one scalar instruction.
249   typedef SmallVector<Value*, 2> VectorParts;
250
251   // When we if-convert we need create edge masks. We have to cache values so
252   // that we don't end up with exponential recursion/IR.
253   typedef DenseMap<std::pair<BasicBlock*, BasicBlock*>,
254                    VectorParts> EdgeMaskCache;
255
256   /// \brief Add code that checks at runtime if the accessed arrays overlap.
257   ///
258   /// Returns a pair of instructions where the first element is the first
259   /// instruction generated in possibly a sequence of instructions and the
260   /// second value is the final comparator value or NULL if no check is needed.
261   std::pair<Instruction *, Instruction *> addRuntimeCheck(Instruction *Loc);
262
263   /// \brief Add checks for strides that where assumed to be 1.
264   ///
265   /// Returns the last check instruction and the first check instruction in the
266   /// pair as (first, last).
267   std::pair<Instruction *, Instruction *> addStrideCheck(Instruction *Loc);
268
269   /// Create an empty loop, based on the loop ranges of the old loop.
270   void createEmptyLoop();
271   /// Copy and widen the instructions from the old loop.
272   virtual void vectorizeLoop();
273
274   /// \brief The Loop exit block may have single value PHI nodes where the
275   /// incoming value is 'Undef'. While vectorizing we only handled real values
276   /// that were defined inside the loop. Here we fix the 'undef case'.
277   /// See PR14725.
278   void fixLCSSAPHIs();
279
280   /// A helper function that computes the predicate of the block BB, assuming
281   /// that the header block of the loop is set to True. It returns the *entry*
282   /// mask for the block BB.
283   VectorParts createBlockInMask(BasicBlock *BB);
284   /// A helper function that computes the predicate of the edge between SRC
285   /// and DST.
286   VectorParts createEdgeMask(BasicBlock *Src, BasicBlock *Dst);
287
288   /// A helper function to vectorize a single BB within the innermost loop.
289   void vectorizeBlockInLoop(BasicBlock *BB, PhiVector *PV);
290
291   /// Vectorize a single PHINode in a block. This method handles the induction
292   /// variable canonicalization. It supports both VF = 1 for unrolled loops and
293   /// arbitrary length vectors.
294   void widenPHIInstruction(Instruction *PN, VectorParts &Entry,
295                            unsigned UF, unsigned VF, PhiVector *PV);
296
297   /// Insert the new loop to the loop hierarchy and pass manager
298   /// and update the analysis passes.
299   void updateAnalysis();
300
301   /// This instruction is un-vectorizable. Implement it as a sequence
302   /// of scalars. If \p IfPredicateStore is true we need to 'hide' each
303   /// scalarized instruction behind an if block predicated on the control
304   /// dependence of the instruction.
305   virtual void scalarizeInstruction(Instruction *Instr,
306                                     bool IfPredicateStore=false);
307
308   /// Vectorize Load and Store instructions,
309   virtual void vectorizeMemoryInstruction(Instruction *Instr);
310
311   /// Create a broadcast instruction. This method generates a broadcast
312   /// instruction (shuffle) for loop invariant values and for the induction
313   /// value. If this is the induction variable then we extend it to N, N+1, ...
314   /// this is needed because each iteration in the loop corresponds to a SIMD
315   /// element.
316   virtual Value *getBroadcastInstrs(Value *V);
317
318   /// This function adds 0, 1, 2 ... to each vector element, starting at zero.
319   /// If Negate is set then negative numbers are added e.g. (0, -1, -2, ...).
320   /// The sequence starts at StartIndex.
321   virtual Value *getConsecutiveVector(Value* Val, int StartIdx, bool Negate);
322
323   /// When we go over instructions in the basic block we rely on previous
324   /// values within the current basic block or on loop invariant values.
325   /// When we widen (vectorize) values we place them in the map. If the values
326   /// are not within the map, they have to be loop invariant, so we simply
327   /// broadcast them into a vector.
328   VectorParts &getVectorValue(Value *V);
329
330   /// Generate a shuffle sequence that will reverse the vector Vec.
331   virtual Value *reverseVector(Value *Vec);
332
333   /// This is a helper class that holds the vectorizer state. It maps scalar
334   /// instructions to vector instructions. When the code is 'unrolled' then
335   /// then a single scalar value is mapped to multiple vector parts. The parts
336   /// are stored in the VectorPart type.
337   struct ValueMap {
338     /// C'tor.  UnrollFactor controls the number of vectors ('parts') that
339     /// are mapped.
340     ValueMap(unsigned UnrollFactor) : UF(UnrollFactor) {}
341
342     /// \return True if 'Key' is saved in the Value Map.
343     bool has(Value *Key) const { return MapStorage.count(Key); }
344
345     /// Initializes a new entry in the map. Sets all of the vector parts to the
346     /// save value in 'Val'.
347     /// \return A reference to a vector with splat values.
348     VectorParts &splat(Value *Key, Value *Val) {
349       VectorParts &Entry = MapStorage[Key];
350       Entry.assign(UF, Val);
351       return Entry;
352     }
353
354     ///\return A reference to the value that is stored at 'Key'.
355     VectorParts &get(Value *Key) {
356       VectorParts &Entry = MapStorage[Key];
357       if (Entry.empty())
358         Entry.resize(UF);
359       assert(Entry.size() == UF);
360       return Entry;
361     }
362
363   private:
364     /// The unroll factor. Each entry in the map stores this number of vector
365     /// elements.
366     unsigned UF;
367
368     /// Map storage. We use std::map and not DenseMap because insertions to a
369     /// dense map invalidates its iterators.
370     std::map<Value *, VectorParts> MapStorage;
371   };
372
373   /// The original loop.
374   Loop *OrigLoop;
375   /// Scev analysis to use.
376   ScalarEvolution *SE;
377   /// Loop Info.
378   LoopInfo *LI;
379   /// Dominator Tree.
380   DominatorTree *DT;
381   /// Data Layout.
382   const DataLayout *DL;
383   /// Target Library Info.
384   const TargetLibraryInfo *TLI;
385
386   /// The vectorization SIMD factor to use. Each vector will have this many
387   /// vector elements.
388   unsigned VF;
389
390 protected:
391   /// The vectorization unroll factor to use. Each scalar is vectorized to this
392   /// many different vector instructions.
393   unsigned UF;
394
395   /// The builder that we use
396   IRBuilder<> Builder;
397
398   // --- Vectorization state ---
399
400   /// The vector-loop preheader.
401   BasicBlock *LoopVectorPreHeader;
402   /// The scalar-loop preheader.
403   BasicBlock *LoopScalarPreHeader;
404   /// Middle Block between the vector and the scalar.
405   BasicBlock *LoopMiddleBlock;
406   ///The ExitBlock of the scalar loop.
407   BasicBlock *LoopExitBlock;
408   ///The vector loop body.
409   SmallVector<BasicBlock *, 4> LoopVectorBody;
410   ///The scalar loop body.
411   BasicBlock *LoopScalarBody;
412   /// A list of all bypass blocks. The first block is the entry of the loop.
413   SmallVector<BasicBlock *, 4> LoopBypassBlocks;
414
415   /// The new Induction variable which was added to the new block.
416   PHINode *Induction;
417   /// The induction variable of the old basic block.
418   PHINode *OldInduction;
419   /// Holds the extended (to the widest induction type) start index.
420   Value *ExtendedIdx;
421   /// Maps scalars to widened vectors.
422   ValueMap WidenMap;
423   EdgeMaskCache MaskCache;
424
425   LoopVectorizationLegality *Legal;
426 };
427
428 class InnerLoopUnroller : public InnerLoopVectorizer {
429 public:
430   InnerLoopUnroller(Loop *OrigLoop, ScalarEvolution *SE, LoopInfo *LI,
431                     DominatorTree *DT, const DataLayout *DL,
432                     const TargetLibraryInfo *TLI, unsigned UnrollFactor) :
433     InnerLoopVectorizer(OrigLoop, SE, LI, DT, DL, TLI, 1, UnrollFactor) { }
434
435 private:
436   virtual void scalarizeInstruction(Instruction *Instr, bool IfPredicateStore = false);
437   virtual void vectorizeMemoryInstruction(Instruction *Instr);
438   virtual Value *getBroadcastInstrs(Value *V);
439   virtual Value *getConsecutiveVector(Value* Val, int StartIdx, bool Negate);
440   virtual Value *reverseVector(Value *Vec);
441 };
442
443 /// \brief Look for a meaningful debug location on the instruction or it's
444 /// operands.
445 static Instruction *getDebugLocFromInstOrOperands(Instruction *I) {
446   if (!I)
447     return I;
448
449   DebugLoc Empty;
450   if (I->getDebugLoc() != Empty)
451     return I;
452
453   for (User::op_iterator OI = I->op_begin(), OE = I->op_end(); OI != OE; ++OI) {
454     if (Instruction *OpInst = dyn_cast<Instruction>(*OI))
455       if (OpInst->getDebugLoc() != Empty)
456         return OpInst;
457   }
458
459   return I;
460 }
461
462 /// \brief Set the debug location in the builder using the debug location in the
463 /// instruction.
464 static void setDebugLocFromInst(IRBuilder<> &B, const Value *Ptr) {
465   if (const Instruction *Inst = dyn_cast_or_null<Instruction>(Ptr))
466     B.SetCurrentDebugLocation(Inst->getDebugLoc());
467   else
468     B.SetCurrentDebugLocation(DebugLoc());
469 }
470
471 /// LoopVectorizationLegality checks if it is legal to vectorize a loop, and
472 /// to what vectorization factor.
473 /// This class does not look at the profitability of vectorization, only the
474 /// legality. This class has two main kinds of checks:
475 /// * Memory checks - The code in canVectorizeMemory checks if vectorization
476 ///   will change the order of memory accesses in a way that will change the
477 ///   correctness of the program.
478 /// * Scalars checks - The code in canVectorizeInstrs and canVectorizeMemory
479 /// checks for a number of different conditions, such as the availability of a
480 /// single induction variable, that all types are supported and vectorize-able,
481 /// etc. This code reflects the capabilities of InnerLoopVectorizer.
482 /// This class is also used by InnerLoopVectorizer for identifying
483 /// induction variable and the different reduction variables.
484 class LoopVectorizationLegality {
485 public:
486   unsigned NumLoads;
487   unsigned NumStores;
488   unsigned NumPredStores;
489
490   LoopVectorizationLegality(Loop *L, ScalarEvolution *SE, const DataLayout *DL,
491                             DominatorTree *DT, TargetLibraryInfo *TLI)
492       : NumLoads(0), NumStores(0), NumPredStores(0), TheLoop(L), SE(SE), DL(DL),
493         DT(DT), TLI(TLI), Induction(0), WidestIndTy(0), HasFunNoNaNAttr(false),
494         MaxSafeDepDistBytes(-1U) {}
495
496   /// This enum represents the kinds of reductions that we support.
497   enum ReductionKind {
498     RK_NoReduction, ///< Not a reduction.
499     RK_IntegerAdd,  ///< Sum of integers.
500     RK_IntegerMult, ///< Product of integers.
501     RK_IntegerOr,   ///< Bitwise or logical OR of numbers.
502     RK_IntegerAnd,  ///< Bitwise or logical AND of numbers.
503     RK_IntegerXor,  ///< Bitwise or logical XOR of numbers.
504     RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
505     RK_FloatAdd,    ///< Sum of floats.
506     RK_FloatMult,   ///< Product of floats.
507     RK_FloatMinMax  ///< Min/max implemented in terms of select(cmp()).
508   };
509
510   /// This enum represents the kinds of inductions that we support.
511   enum InductionKind {
512     IK_NoInduction,         ///< Not an induction variable.
513     IK_IntInduction,        ///< Integer induction variable. Step = 1.
514     IK_ReverseIntInduction, ///< Reverse int induction variable. Step = -1.
515     IK_PtrInduction,        ///< Pointer induction var. Step = sizeof(elem).
516     IK_ReversePtrInduction  ///< Reverse ptr indvar. Step = - sizeof(elem).
517   };
518
519   // This enum represents the kind of minmax reduction.
520   enum MinMaxReductionKind {
521     MRK_Invalid,
522     MRK_UIntMin,
523     MRK_UIntMax,
524     MRK_SIntMin,
525     MRK_SIntMax,
526     MRK_FloatMin,
527     MRK_FloatMax
528   };
529
530   /// This struct holds information about reduction variables.
531   struct ReductionDescriptor {
532     ReductionDescriptor() : StartValue(0), LoopExitInstr(0),
533       Kind(RK_NoReduction), MinMaxKind(MRK_Invalid) {}
534
535     ReductionDescriptor(Value *Start, Instruction *Exit, ReductionKind K,
536                         MinMaxReductionKind MK)
537         : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK) {}
538
539     // The starting value of the reduction.
540     // It does not have to be zero!
541     TrackingVH<Value> StartValue;
542     // The instruction who's value is used outside the loop.
543     Instruction *LoopExitInstr;
544     // The kind of the reduction.
545     ReductionKind Kind;
546     // If this a min/max reduction the kind of reduction.
547     MinMaxReductionKind MinMaxKind;
548   };
549
550   /// This POD struct holds information about a potential reduction operation.
551   struct ReductionInstDesc {
552     ReductionInstDesc(bool IsRedux, Instruction *I) :
553       IsReduction(IsRedux), PatternLastInst(I), MinMaxKind(MRK_Invalid) {}
554
555     ReductionInstDesc(Instruction *I, MinMaxReductionKind K) :
556       IsReduction(true), PatternLastInst(I), MinMaxKind(K) {}
557
558     // Is this instruction a reduction candidate.
559     bool IsReduction;
560     // The last instruction in a min/max pattern (select of the select(icmp())
561     // pattern), or the current reduction instruction otherwise.
562     Instruction *PatternLastInst;
563     // If this is a min/max pattern the comparison predicate.
564     MinMaxReductionKind MinMaxKind;
565   };
566
567   /// This struct holds information about the memory runtime legality
568   /// check that a group of pointers do not overlap.
569   struct RuntimePointerCheck {
570     RuntimePointerCheck() : Need(false) {}
571
572     /// Reset the state of the pointer runtime information.
573     void reset() {
574       Need = false;
575       Pointers.clear();
576       Starts.clear();
577       Ends.clear();
578       IsWritePtr.clear();
579       DependencySetId.clear();
580     }
581
582     /// Insert a pointer and calculate the start and end SCEVs.
583     void insert(ScalarEvolution *SE, Loop *Lp, Value *Ptr, bool WritePtr,
584                 unsigned DepSetId, ValueToValueMap &Strides);
585
586     /// This flag indicates if we need to add the runtime check.
587     bool Need;
588     /// Holds the pointers that we need to check.
589     SmallVector<TrackingVH<Value>, 2> Pointers;
590     /// Holds the pointer value at the beginning of the loop.
591     SmallVector<const SCEV*, 2> Starts;
592     /// Holds the pointer value at the end of the loop.
593     SmallVector<const SCEV*, 2> Ends;
594     /// Holds the information if this pointer is used for writing to memory.
595     SmallVector<bool, 2> IsWritePtr;
596     /// Holds the id of the set of pointers that could be dependent because of a
597     /// shared underlying object.
598     SmallVector<unsigned, 2> DependencySetId;
599   };
600
601   /// A struct for saving information about induction variables.
602   struct InductionInfo {
603     InductionInfo(Value *Start, InductionKind K) : StartValue(Start), IK(K) {}
604     InductionInfo() : StartValue(0), IK(IK_NoInduction) {}
605     /// Start value.
606     TrackingVH<Value> StartValue;
607     /// Induction kind.
608     InductionKind IK;
609   };
610
611   /// ReductionList contains the reduction descriptors for all
612   /// of the reductions that were found in the loop.
613   typedef DenseMap<PHINode*, ReductionDescriptor> ReductionList;
614
615   /// InductionList saves induction variables and maps them to the
616   /// induction descriptor.
617   typedef MapVector<PHINode*, InductionInfo> InductionList;
618
619   /// Returns true if it is legal to vectorize this loop.
620   /// This does not mean that it is profitable to vectorize this
621   /// loop, only that it is legal to do so.
622   bool canVectorize();
623
624   /// Returns the Induction variable.
625   PHINode *getInduction() { return Induction; }
626
627   /// Returns the reduction variables found in the loop.
628   ReductionList *getReductionVars() { return &Reductions; }
629
630   /// Returns the induction variables found in the loop.
631   InductionList *getInductionVars() { return &Inductions; }
632
633   /// Returns the widest induction type.
634   Type *getWidestInductionType() { return WidestIndTy; }
635
636   /// Returns True if V is an induction variable in this loop.
637   bool isInductionVariable(const Value *V);
638
639   /// Return true if the block BB needs to be predicated in order for the loop
640   /// to be vectorized.
641   bool blockNeedsPredication(BasicBlock *BB);
642
643   /// Check if this  pointer is consecutive when vectorizing. This happens
644   /// when the last index of the GEP is the induction variable, or that the
645   /// pointer itself is an induction variable.
646   /// This check allows us to vectorize A[idx] into a wide load/store.
647   /// Returns:
648   /// 0 - Stride is unknown or non-consecutive.
649   /// 1 - Address is consecutive.
650   /// -1 - Address is consecutive, and decreasing.
651   int isConsecutivePtr(Value *Ptr);
652
653   /// Returns true if the value V is uniform within the loop.
654   bool isUniform(Value *V);
655
656   /// Returns true if this instruction will remain scalar after vectorization.
657   bool isUniformAfterVectorization(Instruction* I) { return Uniforms.count(I); }
658
659   /// Returns the information that we collected about runtime memory check.
660   RuntimePointerCheck *getRuntimePointerCheck() { return &PtrRtCheck; }
661
662   /// This function returns the identity element (or neutral element) for
663   /// the operation K.
664   static Constant *getReductionIdentity(ReductionKind K, Type *Tp);
665
666   unsigned getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; }
667
668   bool hasStride(Value *V) { return StrideSet.count(V); }
669   bool mustCheckStrides() { return !StrideSet.empty(); }
670   SmallPtrSet<Value *, 8>::iterator strides_begin() {
671     return StrideSet.begin();
672   }
673   SmallPtrSet<Value *, 8>::iterator strides_end() { return StrideSet.end(); }
674
675 private:
676   /// Check if a single basic block loop is vectorizable.
677   /// At this point we know that this is a loop with a constant trip count
678   /// and we only need to check individual instructions.
679   bool canVectorizeInstrs();
680
681   /// When we vectorize loops we may change the order in which
682   /// we read and write from memory. This method checks if it is
683   /// legal to vectorize the code, considering only memory constrains.
684   /// Returns true if the loop is vectorizable
685   bool canVectorizeMemory();
686
687   /// Return true if we can vectorize this loop using the IF-conversion
688   /// transformation.
689   bool canVectorizeWithIfConvert();
690
691   /// Collect the variables that need to stay uniform after vectorization.
692   void collectLoopUniforms();
693
694   /// Return true if all of the instructions in the block can be speculatively
695   /// executed. \p SafePtrs is a list of addresses that are known to be legal
696   /// and we know that we can read from them without segfault.
697   bool blockCanBePredicated(BasicBlock *BB, SmallPtrSet<Value *, 8>& SafePtrs);
698
699   /// Returns True, if 'Phi' is the kind of reduction variable for type
700   /// 'Kind'. If this is a reduction variable, it adds it to ReductionList.
701   bool AddReductionVar(PHINode *Phi, ReductionKind Kind);
702   /// Returns a struct describing if the instruction 'I' can be a reduction
703   /// variable of type 'Kind'. If the reduction is a min/max pattern of
704   /// select(icmp()) this function advances the instruction pointer 'I' from the
705   /// compare instruction to the select instruction and stores this pointer in
706   /// 'PatternLastInst' member of the returned struct.
707   ReductionInstDesc isReductionInstr(Instruction *I, ReductionKind Kind,
708                                      ReductionInstDesc &Desc);
709   /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
710   /// pattern corresponding to a min(X, Y) or max(X, Y).
711   static ReductionInstDesc isMinMaxSelectCmpPattern(Instruction *I,
712                                                     ReductionInstDesc &Prev);
713   /// Returns the induction kind of Phi. This function may return NoInduction
714   /// if the PHI is not an induction variable.
715   InductionKind isInductionVariable(PHINode *Phi);
716
717   /// \brief Collect memory access with loop invariant strides.
718   ///
719   /// Looks for accesses like "a[i * StrideA]" where "StrideA" is loop
720   /// invariant.
721   void collectStridedAcccess(Value *LoadOrStoreInst);
722
723   /// The loop that we evaluate.
724   Loop *TheLoop;
725   /// Scev analysis.
726   ScalarEvolution *SE;
727   /// DataLayout analysis.
728   const DataLayout *DL;
729   /// Dominators.
730   DominatorTree *DT;
731   /// Target Library Info.
732   TargetLibraryInfo *TLI;
733
734   //  ---  vectorization state --- //
735
736   /// Holds the integer induction variable. This is the counter of the
737   /// loop.
738   PHINode *Induction;
739   /// Holds the reduction variables.
740   ReductionList Reductions;
741   /// Holds all of the induction variables that we found in the loop.
742   /// Notice that inductions don't need to start at zero and that induction
743   /// variables can be pointers.
744   InductionList Inductions;
745   /// Holds the widest induction type encountered.
746   Type *WidestIndTy;
747
748   /// Allowed outside users. This holds the reduction
749   /// vars which can be accessed from outside the loop.
750   SmallPtrSet<Value*, 4> AllowedExit;
751   /// This set holds the variables which are known to be uniform after
752   /// vectorization.
753   SmallPtrSet<Instruction*, 4> Uniforms;
754   /// We need to check that all of the pointers in this list are disjoint
755   /// at runtime.
756   RuntimePointerCheck PtrRtCheck;
757   /// Can we assume the absence of NaNs.
758   bool HasFunNoNaNAttr;
759
760   unsigned MaxSafeDepDistBytes;
761
762   ValueToValueMap Strides;
763   SmallPtrSet<Value *, 8> StrideSet;
764 };
765
766 /// LoopVectorizationCostModel - estimates the expected speedups due to
767 /// vectorization.
768 /// In many cases vectorization is not profitable. This can happen because of
769 /// a number of reasons. In this class we mainly attempt to predict the
770 /// expected speedup/slowdowns due to the supported instruction set. We use the
771 /// TargetTransformInfo to query the different backends for the cost of
772 /// different operations.
773 class LoopVectorizationCostModel {
774 public:
775   LoopVectorizationCostModel(Loop *L, ScalarEvolution *SE, LoopInfo *LI,
776                              LoopVectorizationLegality *Legal,
777                              const TargetTransformInfo &TTI,
778                              const DataLayout *DL, const TargetLibraryInfo *TLI)
779       : TheLoop(L), SE(SE), LI(LI), Legal(Legal), TTI(TTI), DL(DL), TLI(TLI) {}
780
781   /// Information about vectorization costs
782   struct VectorizationFactor {
783     unsigned Width; // Vector width with best cost
784     unsigned Cost; // Cost of the loop with that width
785   };
786   /// \return The most profitable vectorization factor and the cost of that VF.
787   /// This method checks every power of two up to VF. If UserVF is not ZERO
788   /// then this vectorization factor will be selected if vectorization is
789   /// possible.
790   VectorizationFactor selectVectorizationFactor(bool OptForSize,
791                                                 unsigned UserVF);
792
793   /// \return The size (in bits) of the widest type in the code that
794   /// needs to be vectorized. We ignore values that remain scalar such as
795   /// 64 bit loop indices.
796   unsigned getWidestType();
797
798   /// \return The most profitable unroll factor.
799   /// If UserUF is non-zero then this method finds the best unroll-factor
800   /// based on register pressure and other parameters.
801   /// VF and LoopCost are the selected vectorization factor and the cost of the
802   /// selected VF.
803   unsigned selectUnrollFactor(bool OptForSize, unsigned UserUF, unsigned VF,
804                               unsigned LoopCost);
805
806   /// \brief A struct that represents some properties of the register usage
807   /// of a loop.
808   struct RegisterUsage {
809     /// Holds the number of loop invariant values that are used in the loop.
810     unsigned LoopInvariantRegs;
811     /// Holds the maximum number of concurrent live intervals in the loop.
812     unsigned MaxLocalUsers;
813     /// Holds the number of instructions in the loop.
814     unsigned NumInstructions;
815   };
816
817   /// \return  information about the register usage of the loop.
818   RegisterUsage calculateRegisterUsage();
819
820 private:
821   /// Returns the expected execution cost. The unit of the cost does
822   /// not matter because we use the 'cost' units to compare different
823   /// vector widths. The cost that is returned is *not* normalized by
824   /// the factor width.
825   unsigned expectedCost(unsigned VF);
826
827   /// Returns the execution time cost of an instruction for a given vector
828   /// width. Vector width of one means scalar.
829   unsigned getInstructionCost(Instruction *I, unsigned VF);
830
831   /// A helper function for converting Scalar types to vector types.
832   /// If the incoming type is void, we return void. If the VF is 1, we return
833   /// the scalar type.
834   static Type* ToVectorTy(Type *Scalar, unsigned VF);
835
836   /// Returns whether the instruction is a load or store and will be a emitted
837   /// as a vector operation.
838   bool isConsecutiveLoadOrStore(Instruction *I);
839
840   /// The loop that we evaluate.
841   Loop *TheLoop;
842   /// Scev analysis.
843   ScalarEvolution *SE;
844   /// Loop Info analysis.
845   LoopInfo *LI;
846   /// Vectorization legality.
847   LoopVectorizationLegality *Legal;
848   /// Vector target information.
849   const TargetTransformInfo &TTI;
850   /// Target data layout information.
851   const DataLayout *DL;
852   /// Target Library Info.
853   const TargetLibraryInfo *TLI;
854 };
855
856 /// Utility class for getting and setting loop vectorizer hints in the form
857 /// of loop metadata.
858 struct LoopVectorizeHints {
859   /// Vectorization width.
860   unsigned Width;
861   /// Vectorization unroll factor.
862   unsigned Unroll;
863   /// Vectorization forced (-1 not selected, 0 force disabled, 1 force enabled)
864   int Force;
865
866   LoopVectorizeHints(const Loop *L, bool DisableUnrolling)
867   : Width(VectorizationFactor)
868   , Unroll(DisableUnrolling ? 1 : VectorizationUnroll)
869   , Force(-1)
870   , LoopID(L->getLoopID()) {
871     getHints(L);
872     // The command line options override any loop metadata except for when
873     // width == 1 which is used to indicate the loop is already vectorized.
874     if (VectorizationFactor.getNumOccurrences() > 0 && Width != 1)
875       Width = VectorizationFactor;
876     if (VectorizationUnroll.getNumOccurrences() > 0)
877       Unroll = VectorizationUnroll;
878
879     DEBUG(if (DisableUnrolling && Unroll == 1)
880             dbgs() << "LV: Unrolling disabled by the pass manager\n");
881   }
882
883   /// Return the loop vectorizer metadata prefix.
884   static StringRef Prefix() { return "llvm.vectorizer."; }
885
886   MDNode *createHint(LLVMContext &Context, StringRef Name, unsigned V) {
887     SmallVector<Value*, 2> Vals;
888     Vals.push_back(MDString::get(Context, Name));
889     Vals.push_back(ConstantInt::get(Type::getInt32Ty(Context), V));
890     return MDNode::get(Context, Vals);
891   }
892
893   /// Mark the loop L as already vectorized by setting the width to 1.
894   void setAlreadyVectorized(Loop *L) {
895     LLVMContext &Context = L->getHeader()->getContext();
896
897     Width = 1;
898
899     // Create a new loop id with one more operand for the already_vectorized
900     // hint. If the loop already has a loop id then copy the existing operands.
901     SmallVector<Value*, 4> Vals(1);
902     if (LoopID)
903       for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i)
904         Vals.push_back(LoopID->getOperand(i));
905
906     Vals.push_back(createHint(Context, Twine(Prefix(), "width").str(), Width));
907     Vals.push_back(createHint(Context, Twine(Prefix(), "unroll").str(), 1));
908
909     MDNode *NewLoopID = MDNode::get(Context, Vals);
910     // Set operand 0 to refer to the loop id itself.
911     NewLoopID->replaceOperandWith(0, NewLoopID);
912
913     L->setLoopID(NewLoopID);
914     if (LoopID)
915       LoopID->replaceAllUsesWith(NewLoopID);
916
917     LoopID = NewLoopID;
918   }
919
920 private:
921   MDNode *LoopID;
922
923   /// Find hints specified in the loop metadata.
924   void getHints(const Loop *L) {
925     if (!LoopID)
926       return;
927
928     // First operand should refer to the loop id itself.
929     assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
930     assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
931
932     for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
933       const MDString *S = 0;
934       SmallVector<Value*, 4> Args;
935
936       // The expected hint is either a MDString or a MDNode with the first
937       // operand a MDString.
938       if (const MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i))) {
939         if (!MD || MD->getNumOperands() == 0)
940           continue;
941         S = dyn_cast<MDString>(MD->getOperand(0));
942         for (unsigned i = 1, ie = MD->getNumOperands(); i < ie; ++i)
943           Args.push_back(MD->getOperand(i));
944       } else {
945         S = dyn_cast<MDString>(LoopID->getOperand(i));
946         assert(Args.size() == 0 && "too many arguments for MDString");
947       }
948
949       if (!S)
950         continue;
951
952       // Check if the hint starts with the vectorizer prefix.
953       StringRef Hint = S->getString();
954       if (!Hint.startswith(Prefix()))
955         continue;
956       // Remove the prefix.
957       Hint = Hint.substr(Prefix().size(), StringRef::npos);
958
959       if (Args.size() == 1)
960         getHint(Hint, Args[0]);
961     }
962   }
963
964   // Check string hint with one operand.
965   void getHint(StringRef Hint, Value *Arg) {
966     const ConstantInt *C = dyn_cast<ConstantInt>(Arg);
967     if (!C) return;
968     unsigned Val = C->getZExtValue();
969
970     if (Hint == "width") {
971       if (isPowerOf2_32(Val) && Val <= MaxVectorWidth)
972         Width = Val;
973       else
974         DEBUG(dbgs() << "LV: ignoring invalid width hint metadata\n");
975     } else if (Hint == "unroll") {
976       if (isPowerOf2_32(Val) && Val <= MaxUnrollFactor)
977         Unroll = Val;
978       else
979         DEBUG(dbgs() << "LV: ignoring invalid unroll hint metadata\n");
980     } else if (Hint == "enable") {
981       if (C->getBitWidth() == 1)
982         Force = Val;
983       else
984         DEBUG(dbgs() << "LV: ignoring invalid enable hint metadata\n");
985     } else {
986       DEBUG(dbgs() << "LV: ignoring unknown hint " << Hint << '\n');
987     }
988   }
989 };
990
991 static void addInnerLoop(Loop *L, SmallVectorImpl<Loop *> &V) {
992   if (L->empty())
993     return V.push_back(L);
994
995   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
996     addInnerLoop(*I, V);
997 }
998
999 /// The LoopVectorize Pass.
1000 struct LoopVectorize : public FunctionPass {
1001   /// Pass identification, replacement for typeid
1002   static char ID;
1003
1004   explicit LoopVectorize(bool NoUnrolling = false, bool AlwaysVectorize = true)
1005     : FunctionPass(ID),
1006       DisableUnrolling(NoUnrolling),
1007       AlwaysVectorize(AlwaysVectorize) {
1008     initializeLoopVectorizePass(*PassRegistry::getPassRegistry());
1009   }
1010
1011   ScalarEvolution *SE;
1012   const DataLayout *DL;
1013   LoopInfo *LI;
1014   TargetTransformInfo *TTI;
1015   DominatorTree *DT;
1016   BlockFrequencyInfo *BFI;
1017   TargetLibraryInfo *TLI;
1018   bool DisableUnrolling;
1019   bool AlwaysVectorize;
1020
1021   BlockFrequency ColdEntryFreq;
1022
1023   virtual bool runOnFunction(Function &F) {
1024     SE = &getAnalysis<ScalarEvolution>();
1025     DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
1026     DL = DLP ? &DLP->getDataLayout() : 0;
1027     LI = &getAnalysis<LoopInfo>();
1028     TTI = &getAnalysis<TargetTransformInfo>();
1029     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1030     BFI = &getAnalysis<BlockFrequencyInfo>();
1031     TLI = getAnalysisIfAvailable<TargetLibraryInfo>();
1032
1033     // Compute some weights outside of the loop over the loops. Compute this
1034     // using a BranchProbability to re-use its scaling math.
1035     const BranchProbability ColdProb(1, 5); // 20%
1036     ColdEntryFreq = BlockFrequency(BFI->getEntryFreq()) * ColdProb;
1037
1038     // If the target claims to have no vector registers don't attempt
1039     // vectorization.
1040     if (!TTI->getNumberOfRegisters(true))
1041       return false;
1042
1043     if (DL == NULL) {
1044       DEBUG(dbgs() << "LV: Not vectorizing: Missing data layout\n");
1045       return false;
1046     }
1047
1048     // Build up a worklist of inner-loops to vectorize. This is necessary as
1049     // the act of vectorizing or partially unrolling a loop creates new loops
1050     // and can invalidate iterators across the loops.
1051     SmallVector<Loop *, 8> Worklist;
1052
1053     for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
1054       addInnerLoop(*I, Worklist);
1055
1056     // Now walk the identified inner loops.
1057     bool Changed = false;
1058     while (!Worklist.empty())
1059       Changed |= processLoop(Worklist.pop_back_val());
1060
1061     // Process each loop nest in the function.
1062     return Changed;
1063   }
1064
1065   bool processLoop(Loop *L) {
1066     // We only handle inner loops, so if there are children just recurse.
1067     if (!L->empty()) {
1068       bool Changed = false;
1069       for (Loop::iterator I = L->begin(), E = L->begin(); I != E; ++I)
1070         Changed |= processLoop(*I);
1071       return Changed;
1072     }
1073
1074     DEBUG(dbgs() << "LV: Checking a loop in \"" <<
1075           L->getHeader()->getParent()->getName() << "\"\n");
1076
1077     LoopVectorizeHints Hints(L, DisableUnrolling);
1078
1079     if (Hints.Force == 0) {
1080       DEBUG(dbgs() << "LV: Not vectorizing: #pragma vectorize disable.\n");
1081       return false;
1082     }
1083
1084     if (!AlwaysVectorize && Hints.Force != 1) {
1085       DEBUG(dbgs() << "LV: Not vectorizing: No #pragma vectorize enable.\n");
1086       return false;
1087     }
1088
1089     if (Hints.Width == 1 && Hints.Unroll == 1) {
1090       DEBUG(dbgs() << "LV: Not vectorizing: Disabled/already vectorized.\n");
1091       return false;
1092     }
1093
1094     // Check if it is legal to vectorize the loop.
1095     LoopVectorizationLegality LVL(L, SE, DL, DT, TLI);
1096     if (!LVL.canVectorize()) {
1097       DEBUG(dbgs() << "LV: Not vectorizing: Cannot prove legality.\n");
1098       return false;
1099     }
1100
1101     // Use the cost model.
1102     LoopVectorizationCostModel CM(L, SE, LI, &LVL, *TTI, DL, TLI);
1103
1104     // Check the function attributes to find out if this function should be
1105     // optimized for size.
1106     Function *F = L->getHeader()->getParent();
1107     bool OptForSize =
1108         Hints.Force != 1 && F->hasFnAttribute(Attribute::OptimizeForSize);
1109
1110     // Compute the weighted frequency of this loop being executed and see if it
1111     // is less than 20% of the function entry baseline frequency. Note that we
1112     // always have a canonical loop here because we think we *can* vectoriez.
1113     // FIXME: This is hidden behind a flag due to pervasive problems with
1114     // exactly what block frequency models.
1115     if (LoopVectorizeWithBlockFrequency) {
1116       BlockFrequency LoopEntryFreq = BFI->getBlockFreq(L->getLoopPreheader());
1117       if (Hints.Force != 1 && LoopEntryFreq < ColdEntryFreq)
1118         OptForSize = true;
1119     }
1120
1121     // Check the function attributes to see if implicit floats are allowed.a
1122     // FIXME: This check doesn't seem possibly correct -- what if the loop is
1123     // an integer loop and the vector instructions selected are purely integer
1124     // vector instructions?
1125     if (F->hasFnAttribute(Attribute::NoImplicitFloat)) {
1126       DEBUG(dbgs() << "LV: Can't vectorize when the NoImplicitFloat"
1127             "attribute is used.\n");
1128       return false;
1129     }
1130
1131     // Select the optimal vectorization factor.
1132     LoopVectorizationCostModel::VectorizationFactor VF;
1133     VF = CM.selectVectorizationFactor(OptForSize, Hints.Width);
1134     // Select the unroll factor.
1135     unsigned UF = CM.selectUnrollFactor(OptForSize, Hints.Unroll, VF.Width,
1136                                         VF.Cost);
1137
1138     DEBUG(dbgs() << "LV: Found a vectorizable loop ("<< VF.Width << ") in "<<
1139           F->getParent()->getModuleIdentifier() << '\n');
1140     DEBUG(dbgs() << "LV: Unroll Factor is " << UF << '\n');
1141
1142     if (VF.Width == 1) {
1143       DEBUG(dbgs() << "LV: Vectorization is possible but not beneficial.\n");
1144       if (UF == 1)
1145         return false;
1146       DEBUG(dbgs() << "LV: Trying to at least unroll the loops.\n");
1147       // We decided not to vectorize, but we may want to unroll.
1148       InnerLoopUnroller Unroller(L, SE, LI, DT, DL, TLI, UF);
1149       Unroller.vectorize(&LVL);
1150     } else {
1151       // If we decided that it is *legal* to vectorize the loop then do it.
1152       InnerLoopVectorizer LB(L, SE, LI, DT, DL, TLI, VF.Width, UF);
1153       LB.vectorize(&LVL);
1154     }
1155
1156     // Mark the loop as already vectorized to avoid vectorizing again.
1157     Hints.setAlreadyVectorized(L);
1158
1159     DEBUG(verifyFunction(*L->getHeader()->getParent()));
1160     return true;
1161   }
1162
1163   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1164     AU.addRequiredID(LoopSimplifyID);
1165     AU.addRequiredID(LCSSAID);
1166     AU.addRequired<BlockFrequencyInfo>();
1167     AU.addRequired<DominatorTreeWrapperPass>();
1168     AU.addRequired<LoopInfo>();
1169     AU.addRequired<ScalarEvolution>();
1170     AU.addRequired<TargetTransformInfo>();
1171     AU.addPreserved<LoopInfo>();
1172     AU.addPreserved<DominatorTreeWrapperPass>();
1173   }
1174
1175 };
1176
1177 } // end anonymous namespace
1178
1179 //===----------------------------------------------------------------------===//
1180 // Implementation of LoopVectorizationLegality, InnerLoopVectorizer and
1181 // LoopVectorizationCostModel.
1182 //===----------------------------------------------------------------------===//
1183
1184 static Value *stripIntegerCast(Value *V) {
1185   if (CastInst *CI = dyn_cast<CastInst>(V))
1186     if (CI->getOperand(0)->getType()->isIntegerTy())
1187       return CI->getOperand(0);
1188   return V;
1189 }
1190
1191 ///\brief Replaces the symbolic stride in a pointer SCEV expression by one.
1192 ///
1193 /// If \p OrigPtr is not null, use it to look up the stride value instead of
1194 /// \p Ptr.
1195 static const SCEV *replaceSymbolicStrideSCEV(ScalarEvolution *SE,
1196                                              ValueToValueMap &PtrToStride,
1197                                              Value *Ptr, Value *OrigPtr = 0) {
1198
1199   const SCEV *OrigSCEV = SE->getSCEV(Ptr);
1200
1201   // If there is an entry in the map return the SCEV of the pointer with the
1202   // symbolic stride replaced by one.
1203   ValueToValueMap::iterator SI = PtrToStride.find(OrigPtr ? OrigPtr : Ptr);
1204   if (SI != PtrToStride.end()) {
1205     Value *StrideVal = SI->second;
1206
1207     // Strip casts.
1208     StrideVal = stripIntegerCast(StrideVal);
1209
1210     // Replace symbolic stride by one.
1211     Value *One = ConstantInt::get(StrideVal->getType(), 1);
1212     ValueToValueMap RewriteMap;
1213     RewriteMap[StrideVal] = One;
1214
1215     const SCEV *ByOne =
1216         SCEVParameterRewriter::rewrite(OrigSCEV, *SE, RewriteMap, true);
1217     DEBUG(dbgs() << "LV: Replacing SCEV: " << *OrigSCEV << " by: " << *ByOne
1218                  << "\n");
1219     return ByOne;
1220   }
1221
1222   // Otherwise, just return the SCEV of the original pointer.
1223   return SE->getSCEV(Ptr);
1224 }
1225
1226 void LoopVectorizationLegality::RuntimePointerCheck::insert(
1227     ScalarEvolution *SE, Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId,
1228     ValueToValueMap &Strides) {
1229   // Get the stride replaced scev.
1230   const SCEV *Sc = replaceSymbolicStrideSCEV(SE, Strides, Ptr);
1231   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc);
1232   assert(AR && "Invalid addrec expression");
1233   const SCEV *Ex = SE->getBackedgeTakenCount(Lp);
1234   const SCEV *ScEnd = AR->evaluateAtIteration(Ex, *SE);
1235   Pointers.push_back(Ptr);
1236   Starts.push_back(AR->getStart());
1237   Ends.push_back(ScEnd);
1238   IsWritePtr.push_back(WritePtr);
1239   DependencySetId.push_back(DepSetId);
1240 }
1241
1242 Value *InnerLoopVectorizer::getBroadcastInstrs(Value *V) {
1243   // We need to place the broadcast of invariant variables outside the loop.
1244   Instruction *Instr = dyn_cast<Instruction>(V);
1245   bool NewInstr =
1246       (Instr && std::find(LoopVectorBody.begin(), LoopVectorBody.end(),
1247                           Instr->getParent()) != LoopVectorBody.end());
1248   bool Invariant = OrigLoop->isLoopInvariant(V) && !NewInstr;
1249
1250   // Place the code for broadcasting invariant variables in the new preheader.
1251   IRBuilder<>::InsertPointGuard Guard(Builder);
1252   if (Invariant)
1253     Builder.SetInsertPoint(LoopVectorPreHeader->getTerminator());
1254
1255   // Broadcast the scalar into all locations in the vector.
1256   Value *Shuf = Builder.CreateVectorSplat(VF, V, "broadcast");
1257
1258   return Shuf;
1259 }
1260
1261 Value *InnerLoopVectorizer::getConsecutiveVector(Value* Val, int StartIdx,
1262                                                  bool Negate) {
1263   assert(Val->getType()->isVectorTy() && "Must be a vector");
1264   assert(Val->getType()->getScalarType()->isIntegerTy() &&
1265          "Elem must be an integer");
1266   // Create the types.
1267   Type *ITy = Val->getType()->getScalarType();
1268   VectorType *Ty = cast<VectorType>(Val->getType());
1269   int VLen = Ty->getNumElements();
1270   SmallVector<Constant*, 8> Indices;
1271
1272   // Create a vector of consecutive numbers from zero to VF.
1273   for (int i = 0; i < VLen; ++i) {
1274     int64_t Idx = Negate ? (-i) : i;
1275     Indices.push_back(ConstantInt::get(ITy, StartIdx + Idx, Negate));
1276   }
1277
1278   // Add the consecutive indices to the vector value.
1279   Constant *Cv = ConstantVector::get(Indices);
1280   assert(Cv->getType() == Val->getType() && "Invalid consecutive vec");
1281   return Builder.CreateAdd(Val, Cv, "induction");
1282 }
1283
1284 /// \brief Find the operand of the GEP that should be checked for consecutive
1285 /// stores. This ignores trailing indices that have no effect on the final
1286 /// pointer.
1287 static unsigned getGEPInductionOperand(const DataLayout *DL,
1288                                        const GetElementPtrInst *Gep) {
1289   unsigned LastOperand = Gep->getNumOperands() - 1;
1290   unsigned GEPAllocSize = DL->getTypeAllocSize(
1291       cast<PointerType>(Gep->getType()->getScalarType())->getElementType());
1292
1293   // Walk backwards and try to peel off zeros.
1294   while (LastOperand > 1 && match(Gep->getOperand(LastOperand), m_Zero())) {
1295     // Find the type we're currently indexing into.
1296     gep_type_iterator GEPTI = gep_type_begin(Gep);
1297     std::advance(GEPTI, LastOperand - 1);
1298
1299     // If it's a type with the same allocation size as the result of the GEP we
1300     // can peel off the zero index.
1301     if (DL->getTypeAllocSize(*GEPTI) != GEPAllocSize)
1302       break;
1303     --LastOperand;
1304   }
1305
1306   return LastOperand;
1307 }
1308
1309 int LoopVectorizationLegality::isConsecutivePtr(Value *Ptr) {
1310   assert(Ptr->getType()->isPointerTy() && "Unexpected non-ptr");
1311   // Make sure that the pointer does not point to structs.
1312   if (Ptr->getType()->getPointerElementType()->isAggregateType())
1313     return 0;
1314
1315   // If this value is a pointer induction variable we know it is consecutive.
1316   PHINode *Phi = dyn_cast_or_null<PHINode>(Ptr);
1317   if (Phi && Inductions.count(Phi)) {
1318     InductionInfo II = Inductions[Phi];
1319     if (IK_PtrInduction == II.IK)
1320       return 1;
1321     else if (IK_ReversePtrInduction == II.IK)
1322       return -1;
1323   }
1324
1325   GetElementPtrInst *Gep = dyn_cast_or_null<GetElementPtrInst>(Ptr);
1326   if (!Gep)
1327     return 0;
1328
1329   unsigned NumOperands = Gep->getNumOperands();
1330   Value *GpPtr = Gep->getPointerOperand();
1331   // If this GEP value is a consecutive pointer induction variable and all of
1332   // the indices are constant then we know it is consecutive. We can
1333   Phi = dyn_cast<PHINode>(GpPtr);
1334   if (Phi && Inductions.count(Phi)) {
1335
1336     // Make sure that the pointer does not point to structs.
1337     PointerType *GepPtrType = cast<PointerType>(GpPtr->getType());
1338     if (GepPtrType->getElementType()->isAggregateType())
1339       return 0;
1340
1341     // Make sure that all of the index operands are loop invariant.
1342     for (unsigned i = 1; i < NumOperands; ++i)
1343       if (!SE->isLoopInvariant(SE->getSCEV(Gep->getOperand(i)), TheLoop))
1344         return 0;
1345
1346     InductionInfo II = Inductions[Phi];
1347     if (IK_PtrInduction == II.IK)
1348       return 1;
1349     else if (IK_ReversePtrInduction == II.IK)
1350       return -1;
1351   }
1352
1353   unsigned InductionOperand = getGEPInductionOperand(DL, Gep);
1354
1355   // Check that all of the gep indices are uniform except for our induction
1356   // operand.
1357   for (unsigned i = 0; i != NumOperands; ++i)
1358     if (i != InductionOperand &&
1359         !SE->isLoopInvariant(SE->getSCEV(Gep->getOperand(i)), TheLoop))
1360       return 0;
1361
1362   // We can emit wide load/stores only if the last non-zero index is the
1363   // induction variable.
1364   const SCEV *Last = 0;
1365   if (!Strides.count(Gep))
1366     Last = SE->getSCEV(Gep->getOperand(InductionOperand));
1367   else {
1368     // Because of the multiplication by a stride we can have a s/zext cast.
1369     // We are going to replace this stride by 1 so the cast is safe to ignore.
1370     //
1371     //  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
1372     //  %0 = trunc i64 %indvars.iv to i32
1373     //  %mul = mul i32 %0, %Stride1
1374     //  %idxprom = zext i32 %mul to i64  << Safe cast.
1375     //  %arrayidx = getelementptr inbounds i32* %B, i64 %idxprom
1376     //
1377     Last = replaceSymbolicStrideSCEV(SE, Strides,
1378                                      Gep->getOperand(InductionOperand), Gep);
1379     if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(Last))
1380       Last =
1381           (C->getSCEVType() == scSignExtend || C->getSCEVType() == scZeroExtend)
1382               ? C->getOperand()
1383               : Last;
1384   }
1385   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Last)) {
1386     const SCEV *Step = AR->getStepRecurrence(*SE);
1387
1388     // The memory is consecutive because the last index is consecutive
1389     // and all other indices are loop invariant.
1390     if (Step->isOne())
1391       return 1;
1392     if (Step->isAllOnesValue())
1393       return -1;
1394   }
1395
1396   return 0;
1397 }
1398
1399 bool LoopVectorizationLegality::isUniform(Value *V) {
1400   return (SE->isLoopInvariant(SE->getSCEV(V), TheLoop));
1401 }
1402
1403 InnerLoopVectorizer::VectorParts&
1404 InnerLoopVectorizer::getVectorValue(Value *V) {
1405   assert(V != Induction && "The new induction variable should not be used.");
1406   assert(!V->getType()->isVectorTy() && "Can't widen a vector");
1407
1408   // If we have a stride that is replaced by one, do it here.
1409   if (Legal->hasStride(V))
1410     V = ConstantInt::get(V->getType(), 1);
1411
1412   // If we have this scalar in the map, return it.
1413   if (WidenMap.has(V))
1414     return WidenMap.get(V);
1415
1416   // If this scalar is unknown, assume that it is a constant or that it is
1417   // loop invariant. Broadcast V and save the value for future uses.
1418   Value *B = getBroadcastInstrs(V);
1419   return WidenMap.splat(V, B);
1420 }
1421
1422 Value *InnerLoopVectorizer::reverseVector(Value *Vec) {
1423   assert(Vec->getType()->isVectorTy() && "Invalid type");
1424   SmallVector<Constant*, 8> ShuffleMask;
1425   for (unsigned i = 0; i < VF; ++i)
1426     ShuffleMask.push_back(Builder.getInt32(VF - i - 1));
1427
1428   return Builder.CreateShuffleVector(Vec, UndefValue::get(Vec->getType()),
1429                                      ConstantVector::get(ShuffleMask),
1430                                      "reverse");
1431 }
1432
1433 void InnerLoopVectorizer::vectorizeMemoryInstruction(Instruction *Instr) {
1434   // Attempt to issue a wide load.
1435   LoadInst *LI = dyn_cast<LoadInst>(Instr);
1436   StoreInst *SI = dyn_cast<StoreInst>(Instr);
1437
1438   assert((LI || SI) && "Invalid Load/Store instruction");
1439
1440   Type *ScalarDataTy = LI ? LI->getType() : SI->getValueOperand()->getType();
1441   Type *DataTy = VectorType::get(ScalarDataTy, VF);
1442   Value *Ptr = LI ? LI->getPointerOperand() : SI->getPointerOperand();
1443   unsigned Alignment = LI ? LI->getAlignment() : SI->getAlignment();
1444   // An alignment of 0 means target abi alignment. We need to use the scalar's
1445   // target abi alignment in such a case.
1446   if (!Alignment)
1447     Alignment = DL->getABITypeAlignment(ScalarDataTy);
1448   unsigned AddressSpace = Ptr->getType()->getPointerAddressSpace();
1449   unsigned ScalarAllocatedSize = DL->getTypeAllocSize(ScalarDataTy);
1450   unsigned VectorElementSize = DL->getTypeStoreSize(DataTy)/VF;
1451
1452   if (SI && Legal->blockNeedsPredication(SI->getParent()))
1453     return scalarizeInstruction(Instr, true);
1454
1455   if (ScalarAllocatedSize != VectorElementSize)
1456     return scalarizeInstruction(Instr);
1457
1458   // If the pointer is loop invariant or if it is non-consecutive,
1459   // scalarize the load.
1460   int ConsecutiveStride = Legal->isConsecutivePtr(Ptr);
1461   bool Reverse = ConsecutiveStride < 0;
1462   bool UniformLoad = LI && Legal->isUniform(Ptr);
1463   if (!ConsecutiveStride || UniformLoad)
1464     return scalarizeInstruction(Instr);
1465
1466   Constant *Zero = Builder.getInt32(0);
1467   VectorParts &Entry = WidenMap.get(Instr);
1468
1469   // Handle consecutive loads/stores.
1470   GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr);
1471   if (Gep && Legal->isInductionVariable(Gep->getPointerOperand())) {
1472     setDebugLocFromInst(Builder, Gep);
1473     Value *PtrOperand = Gep->getPointerOperand();
1474     Value *FirstBasePtr = getVectorValue(PtrOperand)[0];
1475     FirstBasePtr = Builder.CreateExtractElement(FirstBasePtr, Zero);
1476
1477     // Create the new GEP with the new induction variable.
1478     GetElementPtrInst *Gep2 = cast<GetElementPtrInst>(Gep->clone());
1479     Gep2->setOperand(0, FirstBasePtr);
1480     Gep2->setName("gep.indvar.base");
1481     Ptr = Builder.Insert(Gep2);
1482   } else if (Gep) {
1483     setDebugLocFromInst(Builder, Gep);
1484     assert(SE->isLoopInvariant(SE->getSCEV(Gep->getPointerOperand()),
1485                                OrigLoop) && "Base ptr must be invariant");
1486
1487     // The last index does not have to be the induction. It can be
1488     // consecutive and be a function of the index. For example A[I+1];
1489     unsigned NumOperands = Gep->getNumOperands();
1490     unsigned InductionOperand = getGEPInductionOperand(DL, Gep);
1491     // Create the new GEP with the new induction variable.
1492     GetElementPtrInst *Gep2 = cast<GetElementPtrInst>(Gep->clone());
1493
1494     for (unsigned i = 0; i < NumOperands; ++i) {
1495       Value *GepOperand = Gep->getOperand(i);
1496       Instruction *GepOperandInst = dyn_cast<Instruction>(GepOperand);
1497
1498       // Update last index or loop invariant instruction anchored in loop.
1499       if (i == InductionOperand ||
1500           (GepOperandInst && OrigLoop->contains(GepOperandInst))) {
1501         assert((i == InductionOperand ||
1502                SE->isLoopInvariant(SE->getSCEV(GepOperandInst), OrigLoop)) &&
1503                "Must be last index or loop invariant");
1504
1505         VectorParts &GEPParts = getVectorValue(GepOperand);
1506         Value *Index = GEPParts[0];
1507         Index = Builder.CreateExtractElement(Index, Zero);
1508         Gep2->setOperand(i, Index);
1509         Gep2->setName("gep.indvar.idx");
1510       }
1511     }
1512     Ptr = Builder.Insert(Gep2);
1513   } else {
1514     // Use the induction element ptr.
1515     assert(isa<PHINode>(Ptr) && "Invalid induction ptr");
1516     setDebugLocFromInst(Builder, Ptr);
1517     VectorParts &PtrVal = getVectorValue(Ptr);
1518     Ptr = Builder.CreateExtractElement(PtrVal[0], Zero);
1519   }
1520
1521   // Handle Stores:
1522   if (SI) {
1523     assert(!Legal->isUniform(SI->getPointerOperand()) &&
1524            "We do not allow storing to uniform addresses");
1525     setDebugLocFromInst(Builder, SI);
1526     // We don't want to update the value in the map as it might be used in
1527     // another expression. So don't use a reference type for "StoredVal".
1528     VectorParts StoredVal = getVectorValue(SI->getValueOperand());
1529
1530     for (unsigned Part = 0; Part < UF; ++Part) {
1531       // Calculate the pointer for the specific unroll-part.
1532       Value *PartPtr = Builder.CreateGEP(Ptr, Builder.getInt32(Part * VF));
1533
1534       if (Reverse) {
1535         // If we store to reverse consecutive memory locations then we need
1536         // to reverse the order of elements in the stored value.
1537         StoredVal[Part] = reverseVector(StoredVal[Part]);
1538         // If the address is consecutive but reversed, then the
1539         // wide store needs to start at the last vector element.
1540         PartPtr = Builder.CreateGEP(Ptr, Builder.getInt32(-Part * VF));
1541         PartPtr = Builder.CreateGEP(PartPtr, Builder.getInt32(1 - VF));
1542       }
1543
1544       Value *VecPtr = Builder.CreateBitCast(PartPtr,
1545                                             DataTy->getPointerTo(AddressSpace));
1546       Builder.CreateStore(StoredVal[Part], VecPtr)->setAlignment(Alignment);
1547     }
1548     return;
1549   }
1550
1551   // Handle loads.
1552   assert(LI && "Must have a load instruction");
1553   setDebugLocFromInst(Builder, LI);
1554   for (unsigned Part = 0; Part < UF; ++Part) {
1555     // Calculate the pointer for the specific unroll-part.
1556     Value *PartPtr = Builder.CreateGEP(Ptr, Builder.getInt32(Part * VF));
1557
1558     if (Reverse) {
1559       // If the address is consecutive but reversed, then the
1560       // wide store needs to start at the last vector element.
1561       PartPtr = Builder.CreateGEP(Ptr, Builder.getInt32(-Part * VF));
1562       PartPtr = Builder.CreateGEP(PartPtr, Builder.getInt32(1 - VF));
1563     }
1564
1565     Value *VecPtr = Builder.CreateBitCast(PartPtr,
1566                                           DataTy->getPointerTo(AddressSpace));
1567     Value *LI = Builder.CreateLoad(VecPtr, "wide.load");
1568     cast<LoadInst>(LI)->setAlignment(Alignment);
1569     Entry[Part] = Reverse ? reverseVector(LI) :  LI;
1570   }
1571 }
1572
1573 void InnerLoopVectorizer::scalarizeInstruction(Instruction *Instr, bool IfPredicateStore) {
1574   assert(!Instr->getType()->isAggregateType() && "Can't handle vectors");
1575   // Holds vector parameters or scalars, in case of uniform vals.
1576   SmallVector<VectorParts, 4> Params;
1577
1578   setDebugLocFromInst(Builder, Instr);
1579
1580   // Find all of the vectorized parameters.
1581   for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) {
1582     Value *SrcOp = Instr->getOperand(op);
1583
1584     // If we are accessing the old induction variable, use the new one.
1585     if (SrcOp == OldInduction) {
1586       Params.push_back(getVectorValue(SrcOp));
1587       continue;
1588     }
1589
1590     // Try using previously calculated values.
1591     Instruction *SrcInst = dyn_cast<Instruction>(SrcOp);
1592
1593     // If the src is an instruction that appeared earlier in the basic block
1594     // then it should already be vectorized.
1595     if (SrcInst && OrigLoop->contains(SrcInst)) {
1596       assert(WidenMap.has(SrcInst) && "Source operand is unavailable");
1597       // The parameter is a vector value from earlier.
1598       Params.push_back(WidenMap.get(SrcInst));
1599     } else {
1600       // The parameter is a scalar from outside the loop. Maybe even a constant.
1601       VectorParts Scalars;
1602       Scalars.append(UF, SrcOp);
1603       Params.push_back(Scalars);
1604     }
1605   }
1606
1607   assert(Params.size() == Instr->getNumOperands() &&
1608          "Invalid number of operands");
1609
1610   // Does this instruction return a value ?
1611   bool IsVoidRetTy = Instr->getType()->isVoidTy();
1612
1613   Value *UndefVec = IsVoidRetTy ? 0 :
1614     UndefValue::get(VectorType::get(Instr->getType(), VF));
1615   // Create a new entry in the WidenMap and initialize it to Undef or Null.
1616   VectorParts &VecResults = WidenMap.splat(Instr, UndefVec);
1617
1618   Instruction *InsertPt = Builder.GetInsertPoint();
1619   BasicBlock *IfBlock = Builder.GetInsertBlock();
1620   BasicBlock *CondBlock = 0;
1621
1622   VectorParts Cond;
1623   Loop *VectorLp = 0;
1624   if (IfPredicateStore) {
1625     assert(Instr->getParent()->getSinglePredecessor() &&
1626            "Only support single predecessor blocks");
1627     Cond = createEdgeMask(Instr->getParent()->getSinglePredecessor(),
1628                           Instr->getParent());
1629     VectorLp = LI->getLoopFor(IfBlock);
1630     assert(VectorLp && "Must have a loop for this block");
1631   }
1632
1633   // For each vector unroll 'part':
1634   for (unsigned Part = 0; Part < UF; ++Part) {
1635     // For each scalar that we create:
1636     for (unsigned Width = 0; Width < VF; ++Width) {
1637
1638       // Start if-block.
1639       Value *Cmp = 0;
1640       if (IfPredicateStore) {
1641         Cmp = Builder.CreateExtractElement(Cond[Part], Builder.getInt32(Width));
1642         Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Cmp, ConstantInt::get(Cmp->getType(), 1));
1643         CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.store");
1644         LoopVectorBody.push_back(CondBlock);
1645         VectorLp->addBasicBlockToLoop(CondBlock, LI->getBase());
1646         // Update Builder with newly created basic block.
1647         Builder.SetInsertPoint(InsertPt);
1648       }
1649
1650       Instruction *Cloned = Instr->clone();
1651       if (!IsVoidRetTy)
1652         Cloned->setName(Instr->getName() + ".cloned");
1653       // Replace the operands of the cloned instructions with extracted scalars.
1654       for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) {
1655         Value *Op = Params[op][Part];
1656         // Param is a vector. Need to extract the right lane.
1657         if (Op->getType()->isVectorTy())
1658           Op = Builder.CreateExtractElement(Op, Builder.getInt32(Width));
1659         Cloned->setOperand(op, Op);
1660       }
1661
1662       // Place the cloned scalar in the new loop.
1663       Builder.Insert(Cloned);
1664
1665       // If the original scalar returns a value we need to place it in a vector
1666       // so that future users will be able to use it.
1667       if (!IsVoidRetTy)
1668         VecResults[Part] = Builder.CreateInsertElement(VecResults[Part], Cloned,
1669                                                        Builder.getInt32(Width));
1670       // End if-block.
1671       if (IfPredicateStore) {
1672          BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else");
1673          LoopVectorBody.push_back(NewIfBlock);
1674          VectorLp->addBasicBlockToLoop(NewIfBlock, LI->getBase());
1675          Builder.SetInsertPoint(InsertPt);
1676          Instruction *OldBr = IfBlock->getTerminator();
1677          BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
1678          OldBr->eraseFromParent();
1679          IfBlock = NewIfBlock;
1680       }
1681     }
1682   }
1683 }
1684
1685 static Instruction *getFirstInst(Instruction *FirstInst, Value *V,
1686                                  Instruction *Loc) {
1687   if (FirstInst)
1688     return FirstInst;
1689   if (Instruction *I = dyn_cast<Instruction>(V))
1690     return I->getParent() == Loc->getParent() ? I : 0;
1691   return 0;
1692 }
1693
1694 std::pair<Instruction *, Instruction *>
1695 InnerLoopVectorizer::addStrideCheck(Instruction *Loc) {
1696   Instruction *tnullptr = 0;
1697   if (!Legal->mustCheckStrides())
1698     return std::pair<Instruction *, Instruction *>(tnullptr, tnullptr);
1699
1700   IRBuilder<> ChkBuilder(Loc);
1701
1702   // Emit checks.
1703   Value *Check = 0;
1704   Instruction *FirstInst = 0;
1705   for (SmallPtrSet<Value *, 8>::iterator SI = Legal->strides_begin(),
1706                                          SE = Legal->strides_end();
1707        SI != SE; ++SI) {
1708     Value *Ptr = stripIntegerCast(*SI);
1709     Value *C = ChkBuilder.CreateICmpNE(Ptr, ConstantInt::get(Ptr->getType(), 1),
1710                                        "stride.chk");
1711     // Store the first instruction we create.
1712     FirstInst = getFirstInst(FirstInst, C, Loc);
1713     if (Check)
1714       Check = ChkBuilder.CreateOr(Check, C);
1715     else
1716       Check = C;
1717   }
1718
1719   // We have to do this trickery because the IRBuilder might fold the check to a
1720   // constant expression in which case there is no Instruction anchored in a
1721   // the block.
1722   LLVMContext &Ctx = Loc->getContext();
1723   Instruction *TheCheck =
1724       BinaryOperator::CreateAnd(Check, ConstantInt::getTrue(Ctx));
1725   ChkBuilder.Insert(TheCheck, "stride.not.one");
1726   FirstInst = getFirstInst(FirstInst, TheCheck, Loc);
1727
1728   return std::make_pair(FirstInst, TheCheck);
1729 }
1730
1731 std::pair<Instruction *, Instruction *>
1732 InnerLoopVectorizer::addRuntimeCheck(Instruction *Loc) {
1733   LoopVectorizationLegality::RuntimePointerCheck *PtrRtCheck =
1734   Legal->getRuntimePointerCheck();
1735
1736   Instruction *tnullptr = 0;
1737   if (!PtrRtCheck->Need)
1738     return std::pair<Instruction *, Instruction *>(tnullptr, tnullptr);
1739
1740   unsigned NumPointers = PtrRtCheck->Pointers.size();
1741   SmallVector<TrackingVH<Value> , 2> Starts;
1742   SmallVector<TrackingVH<Value> , 2> Ends;
1743
1744   LLVMContext &Ctx = Loc->getContext();
1745   SCEVExpander Exp(*SE, "induction");
1746   Instruction *FirstInst = 0;
1747
1748   for (unsigned i = 0; i < NumPointers; ++i) {
1749     Value *Ptr = PtrRtCheck->Pointers[i];
1750     const SCEV *Sc = SE->getSCEV(Ptr);
1751
1752     if (SE->isLoopInvariant(Sc, OrigLoop)) {
1753       DEBUG(dbgs() << "LV: Adding RT check for a loop invariant ptr:" <<
1754             *Ptr <<"\n");
1755       Starts.push_back(Ptr);
1756       Ends.push_back(Ptr);
1757     } else {
1758       DEBUG(dbgs() << "LV: Adding RT check for range:" << *Ptr << '\n');
1759       unsigned AS = Ptr->getType()->getPointerAddressSpace();
1760
1761       // Use this type for pointer arithmetic.
1762       Type *PtrArithTy = Type::getInt8PtrTy(Ctx, AS);
1763
1764       Value *Start = Exp.expandCodeFor(PtrRtCheck->Starts[i], PtrArithTy, Loc);
1765       Value *End = Exp.expandCodeFor(PtrRtCheck->Ends[i], PtrArithTy, Loc);
1766       Starts.push_back(Start);
1767       Ends.push_back(End);
1768     }
1769   }
1770
1771   IRBuilder<> ChkBuilder(Loc);
1772   // Our instructions might fold to a constant.
1773   Value *MemoryRuntimeCheck = 0;
1774   for (unsigned i = 0; i < NumPointers; ++i) {
1775     for (unsigned j = i+1; j < NumPointers; ++j) {
1776       // No need to check if two readonly pointers intersect.
1777       if (!PtrRtCheck->IsWritePtr[i] && !PtrRtCheck->IsWritePtr[j])
1778         continue;
1779
1780       // Only need to check pointers between two different dependency sets.
1781       if (PtrRtCheck->DependencySetId[i] == PtrRtCheck->DependencySetId[j])
1782        continue;
1783
1784       unsigned AS0 = Starts[i]->getType()->getPointerAddressSpace();
1785       unsigned AS1 = Starts[j]->getType()->getPointerAddressSpace();
1786
1787       assert((AS0 == Ends[j]->getType()->getPointerAddressSpace()) &&
1788              (AS1 == Ends[i]->getType()->getPointerAddressSpace()) &&
1789              "Trying to bounds check pointers with different address spaces");
1790
1791       Type *PtrArithTy0 = Type::getInt8PtrTy(Ctx, AS0);
1792       Type *PtrArithTy1 = Type::getInt8PtrTy(Ctx, AS1);
1793
1794       Value *Start0 = ChkBuilder.CreateBitCast(Starts[i], PtrArithTy0, "bc");
1795       Value *Start1 = ChkBuilder.CreateBitCast(Starts[j], PtrArithTy1, "bc");
1796       Value *End0 =   ChkBuilder.CreateBitCast(Ends[i],   PtrArithTy1, "bc");
1797       Value *End1 =   ChkBuilder.CreateBitCast(Ends[j],   PtrArithTy0, "bc");
1798
1799       Value *Cmp0 = ChkBuilder.CreateICmpULE(Start0, End1, "bound0");
1800       FirstInst = getFirstInst(FirstInst, Cmp0, Loc);
1801       Value *Cmp1 = ChkBuilder.CreateICmpULE(Start1, End0, "bound1");
1802       FirstInst = getFirstInst(FirstInst, Cmp1, Loc);
1803       Value *IsConflict = ChkBuilder.CreateAnd(Cmp0, Cmp1, "found.conflict");
1804       FirstInst = getFirstInst(FirstInst, IsConflict, Loc);
1805       if (MemoryRuntimeCheck) {
1806         IsConflict = ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict,
1807                                          "conflict.rdx");
1808         FirstInst = getFirstInst(FirstInst, IsConflict, Loc);
1809       }
1810       MemoryRuntimeCheck = IsConflict;
1811     }
1812   }
1813
1814   // We have to do this trickery because the IRBuilder might fold the check to a
1815   // constant expression in which case there is no Instruction anchored in a
1816   // the block.
1817   Instruction *Check = BinaryOperator::CreateAnd(MemoryRuntimeCheck,
1818                                                  ConstantInt::getTrue(Ctx));
1819   ChkBuilder.Insert(Check, "memcheck.conflict");
1820   FirstInst = getFirstInst(FirstInst, Check, Loc);
1821   return std::make_pair(FirstInst, Check);
1822 }
1823
1824 void InnerLoopVectorizer::createEmptyLoop() {
1825   /*
1826    In this function we generate a new loop. The new loop will contain
1827    the vectorized instructions while the old loop will continue to run the
1828    scalar remainder.
1829
1830        [ ] <-- vector loop bypass (may consist of multiple blocks).
1831      /  |
1832     /   v
1833    |   [ ]     <-- vector pre header.
1834    |    |
1835    |    v
1836    |   [  ] \
1837    |   [  ]_|   <-- vector loop.
1838    |    |
1839     \   v
1840       >[ ]   <--- middle-block.
1841      /  |
1842     /   v
1843    |   [ ]     <--- new preheader.
1844    |    |
1845    |    v
1846    |   [ ] \
1847    |   [ ]_|   <-- old scalar loop to handle remainder.
1848     \   |
1849      \  v
1850       >[ ]     <-- exit block.
1851    ...
1852    */
1853
1854   BasicBlock *OldBasicBlock = OrigLoop->getHeader();
1855   BasicBlock *BypassBlock = OrigLoop->getLoopPreheader();
1856   BasicBlock *ExitBlock = OrigLoop->getExitBlock();
1857   assert(ExitBlock && "Must have an exit block");
1858
1859   // Some loops have a single integer induction variable, while other loops
1860   // don't. One example is c++ iterators that often have multiple pointer
1861   // induction variables. In the code below we also support a case where we
1862   // don't have a single induction variable.
1863   OldInduction = Legal->getInduction();
1864   Type *IdxTy = Legal->getWidestInductionType();
1865
1866   // Find the loop boundaries.
1867   const SCEV *ExitCount = SE->getBackedgeTakenCount(OrigLoop);
1868   assert(ExitCount != SE->getCouldNotCompute() && "Invalid loop count");
1869
1870   // The exit count might have the type of i64 while the phi is i32. This can
1871   // happen if we have an induction variable that is sign extended before the
1872   // compare. The only way that we get a backedge taken count is that the
1873   // induction variable was signed and as such will not overflow. In such a case
1874   // truncation is legal.
1875   if (ExitCount->getType()->getPrimitiveSizeInBits() >
1876       IdxTy->getPrimitiveSizeInBits())
1877     ExitCount = SE->getTruncateOrNoop(ExitCount, IdxTy);
1878
1879   ExitCount = SE->getNoopOrZeroExtend(ExitCount, IdxTy);
1880   // Get the total trip count from the count by adding 1.
1881   ExitCount = SE->getAddExpr(ExitCount,
1882                              SE->getConstant(ExitCount->getType(), 1));
1883
1884   // Expand the trip count and place the new instructions in the preheader.
1885   // Notice that the pre-header does not change, only the loop body.
1886   SCEVExpander Exp(*SE, "induction");
1887
1888   // Count holds the overall loop count (N).
1889   Value *Count = Exp.expandCodeFor(ExitCount, ExitCount->getType(),
1890                                    BypassBlock->getTerminator());
1891
1892   // The loop index does not have to start at Zero. Find the original start
1893   // value from the induction PHI node. If we don't have an induction variable
1894   // then we know that it starts at zero.
1895   Builder.SetInsertPoint(BypassBlock->getTerminator());
1896   Value *StartIdx = ExtendedIdx = OldInduction ?
1897     Builder.CreateZExt(OldInduction->getIncomingValueForBlock(BypassBlock),
1898                        IdxTy):
1899     ConstantInt::get(IdxTy, 0);
1900
1901   assert(BypassBlock && "Invalid loop structure");
1902   LoopBypassBlocks.push_back(BypassBlock);
1903
1904   // Split the single block loop into the two loop structure described above.
1905   BasicBlock *VectorPH =
1906   BypassBlock->splitBasicBlock(BypassBlock->getTerminator(), "vector.ph");
1907   BasicBlock *VecBody =
1908   VectorPH->splitBasicBlock(VectorPH->getTerminator(), "vector.body");
1909   BasicBlock *MiddleBlock =
1910   VecBody->splitBasicBlock(VecBody->getTerminator(), "middle.block");
1911   BasicBlock *ScalarPH =
1912   MiddleBlock->splitBasicBlock(MiddleBlock->getTerminator(), "scalar.ph");
1913
1914   // Create and register the new vector loop.
1915   Loop* Lp = new Loop();
1916   Loop *ParentLoop = OrigLoop->getParentLoop();
1917
1918   // Insert the new loop into the loop nest and register the new basic blocks
1919   // before calling any utilities such as SCEV that require valid LoopInfo.
1920   if (ParentLoop) {
1921     ParentLoop->addChildLoop(Lp);
1922     ParentLoop->addBasicBlockToLoop(ScalarPH, LI->getBase());
1923     ParentLoop->addBasicBlockToLoop(VectorPH, LI->getBase());
1924     ParentLoop->addBasicBlockToLoop(MiddleBlock, LI->getBase());
1925   } else {
1926     LI->addTopLevelLoop(Lp);
1927   }
1928   Lp->addBasicBlockToLoop(VecBody, LI->getBase());
1929
1930   // Use this IR builder to create the loop instructions (Phi, Br, Cmp)
1931   // inside the loop.
1932   Builder.SetInsertPoint(VecBody->getFirstNonPHI());
1933
1934   // Generate the induction variable.
1935   setDebugLocFromInst(Builder, getDebugLocFromInstOrOperands(OldInduction));
1936   Induction = Builder.CreatePHI(IdxTy, 2, "index");
1937   // The loop step is equal to the vectorization factor (num of SIMD elements)
1938   // times the unroll factor (num of SIMD instructions).
1939   Constant *Step = ConstantInt::get(IdxTy, VF * UF);
1940
1941   // This is the IR builder that we use to add all of the logic for bypassing
1942   // the new vector loop.
1943   IRBuilder<> BypassBuilder(BypassBlock->getTerminator());
1944   setDebugLocFromInst(BypassBuilder,
1945                       getDebugLocFromInstOrOperands(OldInduction));
1946
1947   // We may need to extend the index in case there is a type mismatch.
1948   // We know that the count starts at zero and does not overflow.
1949   if (Count->getType() != IdxTy) {
1950     // The exit count can be of pointer type. Convert it to the correct
1951     // integer type.
1952     if (ExitCount->getType()->isPointerTy())
1953       Count = BypassBuilder.CreatePointerCast(Count, IdxTy, "ptrcnt.to.int");
1954     else
1955       Count = BypassBuilder.CreateZExtOrTrunc(Count, IdxTy, "cnt.cast");
1956   }
1957
1958   // Add the start index to the loop count to get the new end index.
1959   Value *IdxEnd = BypassBuilder.CreateAdd(Count, StartIdx, "end.idx");
1960
1961   // Now we need to generate the expression for N - (N % VF), which is
1962   // the part that the vectorized body will execute.
1963   Value *R = BypassBuilder.CreateURem(Count, Step, "n.mod.vf");
1964   Value *CountRoundDown = BypassBuilder.CreateSub(Count, R, "n.vec");
1965   Value *IdxEndRoundDown = BypassBuilder.CreateAdd(CountRoundDown, StartIdx,
1966                                                      "end.idx.rnd.down");
1967
1968   // Now, compare the new count to zero. If it is zero skip the vector loop and
1969   // jump to the scalar loop.
1970   Value *Cmp = BypassBuilder.CreateICmpEQ(IdxEndRoundDown, StartIdx,
1971                                           "cmp.zero");
1972
1973   BasicBlock *LastBypassBlock = BypassBlock;
1974
1975   // Generate the code to check that the strides we assumed to be one are really
1976   // one. We want the new basic block to start at the first instruction in a
1977   // sequence of instructions that form a check.
1978   Instruction *StrideCheck;
1979   Instruction *FirstCheckInst;
1980   std::tie(FirstCheckInst, StrideCheck) =
1981       addStrideCheck(BypassBlock->getTerminator());
1982   if (StrideCheck) {
1983     // Create a new block containing the stride check.
1984     BasicBlock *CheckBlock =
1985         BypassBlock->splitBasicBlock(FirstCheckInst, "vector.stridecheck");
1986     if (ParentLoop)
1987       ParentLoop->addBasicBlockToLoop(CheckBlock, LI->getBase());
1988     LoopBypassBlocks.push_back(CheckBlock);
1989
1990     // Replace the branch into the memory check block with a conditional branch
1991     // for the "few elements case".
1992     Instruction *OldTerm = BypassBlock->getTerminator();
1993     BranchInst::Create(MiddleBlock, CheckBlock, Cmp, OldTerm);
1994     OldTerm->eraseFromParent();
1995
1996     Cmp = StrideCheck;
1997     LastBypassBlock = CheckBlock;
1998   }
1999
2000   // Generate the code that checks in runtime if arrays overlap. We put the
2001   // checks into a separate block to make the more common case of few elements
2002   // faster.
2003   Instruction *MemRuntimeCheck;
2004   std::tie(FirstCheckInst, MemRuntimeCheck) =
2005       addRuntimeCheck(LastBypassBlock->getTerminator());
2006   if (MemRuntimeCheck) {
2007     // Create a new block containing the memory check.
2008     BasicBlock *CheckBlock =
2009         LastBypassBlock->splitBasicBlock(MemRuntimeCheck, "vector.memcheck");
2010     if (ParentLoop)
2011       ParentLoop->addBasicBlockToLoop(CheckBlock, LI->getBase());
2012     LoopBypassBlocks.push_back(CheckBlock);
2013
2014     // Replace the branch into the memory check block with a conditional branch
2015     // for the "few elements case".
2016     Instruction *OldTerm = LastBypassBlock->getTerminator();
2017     BranchInst::Create(MiddleBlock, CheckBlock, Cmp, OldTerm);
2018     OldTerm->eraseFromParent();
2019
2020     Cmp = MemRuntimeCheck;
2021     LastBypassBlock = CheckBlock;
2022   }
2023
2024   LastBypassBlock->getTerminator()->eraseFromParent();
2025   BranchInst::Create(MiddleBlock, VectorPH, Cmp,
2026                      LastBypassBlock);
2027
2028   // We are going to resume the execution of the scalar loop.
2029   // Go over all of the induction variables that we found and fix the
2030   // PHIs that are left in the scalar version of the loop.
2031   // The starting values of PHI nodes depend on the counter of the last
2032   // iteration in the vectorized loop.
2033   // If we come from a bypass edge then we need to start from the original
2034   // start value.
2035
2036   // This variable saves the new starting index for the scalar loop.
2037   PHINode *ResumeIndex = 0;
2038   LoopVectorizationLegality::InductionList::iterator I, E;
2039   LoopVectorizationLegality::InductionList *List = Legal->getInductionVars();
2040   // Set builder to point to last bypass block.
2041   BypassBuilder.SetInsertPoint(LoopBypassBlocks.back()->getTerminator());
2042   for (I = List->begin(), E = List->end(); I != E; ++I) {
2043     PHINode *OrigPhi = I->first;
2044     LoopVectorizationLegality::InductionInfo II = I->second;
2045
2046     Type *ResumeValTy = (OrigPhi == OldInduction) ? IdxTy : OrigPhi->getType();
2047     PHINode *ResumeVal = PHINode::Create(ResumeValTy, 2, "resume.val",
2048                                          MiddleBlock->getTerminator());
2049     // We might have extended the type of the induction variable but we need a
2050     // truncated version for the scalar loop.
2051     PHINode *TruncResumeVal = (OrigPhi == OldInduction) ?
2052       PHINode::Create(OrigPhi->getType(), 2, "trunc.resume.val",
2053                       MiddleBlock->getTerminator()) : 0;
2054
2055     Value *EndValue = 0;
2056     switch (II.IK) {
2057     case LoopVectorizationLegality::IK_NoInduction:
2058       llvm_unreachable("Unknown induction");
2059     case LoopVectorizationLegality::IK_IntInduction: {
2060       // Handle the integer induction counter.
2061       assert(OrigPhi->getType()->isIntegerTy() && "Invalid type");
2062
2063       // We have the canonical induction variable.
2064       if (OrigPhi == OldInduction) {
2065         // Create a truncated version of the resume value for the scalar loop,
2066         // we might have promoted the type to a larger width.
2067         EndValue =
2068           BypassBuilder.CreateTrunc(IdxEndRoundDown, OrigPhi->getType());
2069         // The new PHI merges the original incoming value, in case of a bypass,
2070         // or the value at the end of the vectorized loop.
2071         for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I)
2072           TruncResumeVal->addIncoming(II.StartValue, LoopBypassBlocks[I]);
2073         TruncResumeVal->addIncoming(EndValue, VecBody);
2074
2075         // We know what the end value is.
2076         EndValue = IdxEndRoundDown;
2077         // We also know which PHI node holds it.
2078         ResumeIndex = ResumeVal;
2079         break;
2080       }
2081
2082       // Not the canonical induction variable - add the vector loop count to the
2083       // start value.
2084       Value *CRD = BypassBuilder.CreateSExtOrTrunc(CountRoundDown,
2085                                                    II.StartValue->getType(),
2086                                                    "cast.crd");
2087       EndValue = BypassBuilder.CreateAdd(CRD, II.StartValue , "ind.end");
2088       break;
2089     }
2090     case LoopVectorizationLegality::IK_ReverseIntInduction: {
2091       // Convert the CountRoundDown variable to the PHI size.
2092       Value *CRD = BypassBuilder.CreateSExtOrTrunc(CountRoundDown,
2093                                                    II.StartValue->getType(),
2094                                                    "cast.crd");
2095       // Handle reverse integer induction counter.
2096       EndValue = BypassBuilder.CreateSub(II.StartValue, CRD, "rev.ind.end");
2097       break;
2098     }
2099     case LoopVectorizationLegality::IK_PtrInduction: {
2100       // For pointer induction variables, calculate the offset using
2101       // the end index.
2102       EndValue = BypassBuilder.CreateGEP(II.StartValue, CountRoundDown,
2103                                          "ptr.ind.end");
2104       break;
2105     }
2106     case LoopVectorizationLegality::IK_ReversePtrInduction: {
2107       // The value at the end of the loop for the reverse pointer is calculated
2108       // by creating a GEP with a negative index starting from the start value.
2109       Value *Zero = ConstantInt::get(CountRoundDown->getType(), 0);
2110       Value *NegIdx = BypassBuilder.CreateSub(Zero, CountRoundDown,
2111                                               "rev.ind.end");
2112       EndValue = BypassBuilder.CreateGEP(II.StartValue, NegIdx,
2113                                          "rev.ptr.ind.end");
2114       break;
2115     }
2116     }// end of case
2117
2118     // The new PHI merges the original incoming value, in case of a bypass,
2119     // or the value at the end of the vectorized loop.
2120     for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I) {
2121       if (OrigPhi == OldInduction)
2122         ResumeVal->addIncoming(StartIdx, LoopBypassBlocks[I]);
2123       else
2124         ResumeVal->addIncoming(II.StartValue, LoopBypassBlocks[I]);
2125     }
2126     ResumeVal->addIncoming(EndValue, VecBody);
2127
2128     // Fix the scalar body counter (PHI node).
2129     unsigned BlockIdx = OrigPhi->getBasicBlockIndex(ScalarPH);
2130     // The old inductions phi node in the scalar body needs the truncated value.
2131     if (OrigPhi == OldInduction)
2132       OrigPhi->setIncomingValue(BlockIdx, TruncResumeVal);
2133     else
2134       OrigPhi->setIncomingValue(BlockIdx, ResumeVal);
2135   }
2136
2137   // If we are generating a new induction variable then we also need to
2138   // generate the code that calculates the exit value. This value is not
2139   // simply the end of the counter because we may skip the vectorized body
2140   // in case of a runtime check.
2141   if (!OldInduction){
2142     assert(!ResumeIndex && "Unexpected resume value found");
2143     ResumeIndex = PHINode::Create(IdxTy, 2, "new.indc.resume.val",
2144                                   MiddleBlock->getTerminator());
2145     for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I)
2146       ResumeIndex->addIncoming(StartIdx, LoopBypassBlocks[I]);
2147     ResumeIndex->addIncoming(IdxEndRoundDown, VecBody);
2148   }
2149
2150   // Make sure that we found the index where scalar loop needs to continue.
2151   assert(ResumeIndex && ResumeIndex->getType()->isIntegerTy() &&
2152          "Invalid resume Index");
2153
2154   // Add a check in the middle block to see if we have completed
2155   // all of the iterations in the first vector loop.
2156   // If (N - N%VF) == N, then we *don't* need to run the remainder.
2157   Value *CmpN = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, IdxEnd,
2158                                 ResumeIndex, "cmp.n",
2159                                 MiddleBlock->getTerminator());
2160
2161   BranchInst::Create(ExitBlock, ScalarPH, CmpN, MiddleBlock->getTerminator());
2162   // Remove the old terminator.
2163   MiddleBlock->getTerminator()->eraseFromParent();
2164
2165   // Create i+1 and fill the PHINode.
2166   Value *NextIdx = Builder.CreateAdd(Induction, Step, "index.next");
2167   Induction->addIncoming(StartIdx, VectorPH);
2168   Induction->addIncoming(NextIdx, VecBody);
2169   // Create the compare.
2170   Value *ICmp = Builder.CreateICmpEQ(NextIdx, IdxEndRoundDown);
2171   Builder.CreateCondBr(ICmp, MiddleBlock, VecBody);
2172
2173   // Now we have two terminators. Remove the old one from the block.
2174   VecBody->getTerminator()->eraseFromParent();
2175
2176   // Get ready to start creating new instructions into the vectorized body.
2177   Builder.SetInsertPoint(VecBody->getFirstInsertionPt());
2178
2179   // Save the state.
2180   LoopVectorPreHeader = VectorPH;
2181   LoopScalarPreHeader = ScalarPH;
2182   LoopMiddleBlock = MiddleBlock;
2183   LoopExitBlock = ExitBlock;
2184   LoopVectorBody.push_back(VecBody);
2185   LoopScalarBody = OldBasicBlock;
2186
2187   LoopVectorizeHints Hints(Lp, true);
2188   Hints.setAlreadyVectorized(Lp);
2189 }
2190
2191 /// This function returns the identity element (or neutral element) for
2192 /// the operation K.
2193 Constant*
2194 LoopVectorizationLegality::getReductionIdentity(ReductionKind K, Type *Tp) {
2195   switch (K) {
2196   case RK_IntegerXor:
2197   case RK_IntegerAdd:
2198   case RK_IntegerOr:
2199     // Adding, Xoring, Oring zero to a number does not change it.
2200     return ConstantInt::get(Tp, 0);
2201   case RK_IntegerMult:
2202     // Multiplying a number by 1 does not change it.
2203     return ConstantInt::get(Tp, 1);
2204   case RK_IntegerAnd:
2205     // AND-ing a number with an all-1 value does not change it.
2206     return ConstantInt::get(Tp, -1, true);
2207   case  RK_FloatMult:
2208     // Multiplying a number by 1 does not change it.
2209     return ConstantFP::get(Tp, 1.0L);
2210   case  RK_FloatAdd:
2211     // Adding zero to a number does not change it.
2212     return ConstantFP::get(Tp, 0.0L);
2213   default:
2214     llvm_unreachable("Unknown reduction kind");
2215   }
2216 }
2217
2218 static Intrinsic::ID checkUnaryFloatSignature(const CallInst &I,
2219                                               Intrinsic::ID ValidIntrinsicID) {
2220   if (I.getNumArgOperands() != 1 ||
2221       !I.getArgOperand(0)->getType()->isFloatingPointTy() ||
2222       I.getType() != I.getArgOperand(0)->getType() ||
2223       !I.onlyReadsMemory())
2224     return Intrinsic::not_intrinsic;
2225
2226   return ValidIntrinsicID;
2227 }
2228
2229 static Intrinsic::ID checkBinaryFloatSignature(const CallInst &I,
2230                                                Intrinsic::ID ValidIntrinsicID) {
2231   if (I.getNumArgOperands() != 2 ||
2232       !I.getArgOperand(0)->getType()->isFloatingPointTy() ||
2233       !I.getArgOperand(1)->getType()->isFloatingPointTy() ||
2234       I.getType() != I.getArgOperand(0)->getType() ||
2235       I.getType() != I.getArgOperand(1)->getType() ||
2236       !I.onlyReadsMemory())
2237     return Intrinsic::not_intrinsic;
2238
2239   return ValidIntrinsicID;
2240 }
2241
2242
2243 static Intrinsic::ID
2244 getIntrinsicIDForCall(CallInst *CI, const TargetLibraryInfo *TLI) {
2245   // If we have an intrinsic call, check if it is trivially vectorizable.
2246   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) {
2247     switch (II->getIntrinsicID()) {
2248     case Intrinsic::sqrt:
2249     case Intrinsic::sin:
2250     case Intrinsic::cos:
2251     case Intrinsic::exp:
2252     case Intrinsic::exp2:
2253     case Intrinsic::log:
2254     case Intrinsic::log10:
2255     case Intrinsic::log2:
2256     case Intrinsic::fabs:
2257     case Intrinsic::copysign:
2258     case Intrinsic::floor:
2259     case Intrinsic::ceil:
2260     case Intrinsic::trunc:
2261     case Intrinsic::rint:
2262     case Intrinsic::nearbyint:
2263     case Intrinsic::round:
2264     case Intrinsic::pow:
2265     case Intrinsic::fma:
2266     case Intrinsic::fmuladd:
2267     case Intrinsic::lifetime_start:
2268     case Intrinsic::lifetime_end:
2269       return II->getIntrinsicID();
2270     default:
2271       return Intrinsic::not_intrinsic;
2272     }
2273   }
2274
2275   if (!TLI)
2276     return Intrinsic::not_intrinsic;
2277
2278   LibFunc::Func Func;
2279   Function *F = CI->getCalledFunction();
2280   // We're going to make assumptions on the semantics of the functions, check
2281   // that the target knows that it's available in this environment and it does
2282   // not have local linkage.
2283   if (!F || F->hasLocalLinkage() || !TLI->getLibFunc(F->getName(), Func))
2284     return Intrinsic::not_intrinsic;
2285
2286   // Otherwise check if we have a call to a function that can be turned into a
2287   // vector intrinsic.
2288   switch (Func) {
2289   default:
2290     break;
2291   case LibFunc::sin:
2292   case LibFunc::sinf:
2293   case LibFunc::sinl:
2294     return checkUnaryFloatSignature(*CI, Intrinsic::sin);
2295   case LibFunc::cos:
2296   case LibFunc::cosf:
2297   case LibFunc::cosl:
2298     return checkUnaryFloatSignature(*CI, Intrinsic::cos);
2299   case LibFunc::exp:
2300   case LibFunc::expf:
2301   case LibFunc::expl:
2302     return checkUnaryFloatSignature(*CI, Intrinsic::exp);
2303   case LibFunc::exp2:
2304   case LibFunc::exp2f:
2305   case LibFunc::exp2l:
2306     return checkUnaryFloatSignature(*CI, Intrinsic::exp2);
2307   case LibFunc::log:
2308   case LibFunc::logf:
2309   case LibFunc::logl:
2310     return checkUnaryFloatSignature(*CI, Intrinsic::log);
2311   case LibFunc::log10:
2312   case LibFunc::log10f:
2313   case LibFunc::log10l:
2314     return checkUnaryFloatSignature(*CI, Intrinsic::log10);
2315   case LibFunc::log2:
2316   case LibFunc::log2f:
2317   case LibFunc::log2l:
2318     return checkUnaryFloatSignature(*CI, Intrinsic::log2);
2319   case LibFunc::fabs:
2320   case LibFunc::fabsf:
2321   case LibFunc::fabsl:
2322     return checkUnaryFloatSignature(*CI, Intrinsic::fabs);
2323   case LibFunc::copysign:
2324   case LibFunc::copysignf:
2325   case LibFunc::copysignl:
2326     return checkBinaryFloatSignature(*CI, Intrinsic::copysign);
2327   case LibFunc::floor:
2328   case LibFunc::floorf:
2329   case LibFunc::floorl:
2330     return checkUnaryFloatSignature(*CI, Intrinsic::floor);
2331   case LibFunc::ceil:
2332   case LibFunc::ceilf:
2333   case LibFunc::ceill:
2334     return checkUnaryFloatSignature(*CI, Intrinsic::ceil);
2335   case LibFunc::trunc:
2336   case LibFunc::truncf:
2337   case LibFunc::truncl:
2338     return checkUnaryFloatSignature(*CI, Intrinsic::trunc);
2339   case LibFunc::rint:
2340   case LibFunc::rintf:
2341   case LibFunc::rintl:
2342     return checkUnaryFloatSignature(*CI, Intrinsic::rint);
2343   case LibFunc::nearbyint:
2344   case LibFunc::nearbyintf:
2345   case LibFunc::nearbyintl:
2346     return checkUnaryFloatSignature(*CI, Intrinsic::nearbyint);
2347   case LibFunc::round:
2348   case LibFunc::roundf:
2349   case LibFunc::roundl:
2350     return checkUnaryFloatSignature(*CI, Intrinsic::round);
2351   case LibFunc::pow:
2352   case LibFunc::powf:
2353   case LibFunc::powl:
2354     return checkBinaryFloatSignature(*CI, Intrinsic::pow);
2355   }
2356
2357   return Intrinsic::not_intrinsic;
2358 }
2359
2360 /// This function translates the reduction kind to an LLVM binary operator.
2361 static unsigned
2362 getReductionBinOp(LoopVectorizationLegality::ReductionKind Kind) {
2363   switch (Kind) {
2364     case LoopVectorizationLegality::RK_IntegerAdd:
2365       return Instruction::Add;
2366     case LoopVectorizationLegality::RK_IntegerMult:
2367       return Instruction::Mul;
2368     case LoopVectorizationLegality::RK_IntegerOr:
2369       return Instruction::Or;
2370     case LoopVectorizationLegality::RK_IntegerAnd:
2371       return Instruction::And;
2372     case LoopVectorizationLegality::RK_IntegerXor:
2373       return Instruction::Xor;
2374     case LoopVectorizationLegality::RK_FloatMult:
2375       return Instruction::FMul;
2376     case LoopVectorizationLegality::RK_FloatAdd:
2377       return Instruction::FAdd;
2378     case LoopVectorizationLegality::RK_IntegerMinMax:
2379       return Instruction::ICmp;
2380     case LoopVectorizationLegality::RK_FloatMinMax:
2381       return Instruction::FCmp;
2382     default:
2383       llvm_unreachable("Unknown reduction operation");
2384   }
2385 }
2386
2387 Value *createMinMaxOp(IRBuilder<> &Builder,
2388                       LoopVectorizationLegality::MinMaxReductionKind RK,
2389                       Value *Left,
2390                       Value *Right) {
2391   CmpInst::Predicate P = CmpInst::ICMP_NE;
2392   switch (RK) {
2393   default:
2394     llvm_unreachable("Unknown min/max reduction kind");
2395   case LoopVectorizationLegality::MRK_UIntMin:
2396     P = CmpInst::ICMP_ULT;
2397     break;
2398   case LoopVectorizationLegality::MRK_UIntMax:
2399     P = CmpInst::ICMP_UGT;
2400     break;
2401   case LoopVectorizationLegality::MRK_SIntMin:
2402     P = CmpInst::ICMP_SLT;
2403     break;
2404   case LoopVectorizationLegality::MRK_SIntMax:
2405     P = CmpInst::ICMP_SGT;
2406     break;
2407   case LoopVectorizationLegality::MRK_FloatMin:
2408     P = CmpInst::FCMP_OLT;
2409     break;
2410   case LoopVectorizationLegality::MRK_FloatMax:
2411     P = CmpInst::FCMP_OGT;
2412     break;
2413   }
2414
2415   Value *Cmp;
2416   if (RK == LoopVectorizationLegality::MRK_FloatMin ||
2417       RK == LoopVectorizationLegality::MRK_FloatMax)
2418     Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
2419   else
2420     Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp");
2421
2422   Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
2423   return Select;
2424 }
2425
2426 namespace {
2427 struct CSEDenseMapInfo {
2428   static bool canHandle(Instruction *I) {
2429     return isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) ||
2430            isa<ShuffleVectorInst>(I) || isa<GetElementPtrInst>(I);
2431   }
2432   static inline Instruction *getEmptyKey() {
2433     return DenseMapInfo<Instruction *>::getEmptyKey();
2434   }
2435   static inline Instruction *getTombstoneKey() {
2436     return DenseMapInfo<Instruction *>::getTombstoneKey();
2437   }
2438   static unsigned getHashValue(Instruction *I) {
2439     assert(canHandle(I) && "Unknown instruction!");
2440     return hash_combine(I->getOpcode(), hash_combine_range(I->value_op_begin(),
2441                                                            I->value_op_end()));
2442   }
2443   static bool isEqual(Instruction *LHS, Instruction *RHS) {
2444     if (LHS == getEmptyKey() || RHS == getEmptyKey() ||
2445         LHS == getTombstoneKey() || RHS == getTombstoneKey())
2446       return LHS == RHS;
2447     return LHS->isIdenticalTo(RHS);
2448   }
2449 };
2450 }
2451
2452 /// \brief Check whether this block is a predicated block.
2453 /// Due to if predication of stores we might create a sequence of "if(pred) a[i]
2454 /// = ...;  " blocks. We start with one vectorized basic block. For every
2455 /// conditional block we split this vectorized block. Therefore, every second
2456 /// block will be a predicated one.
2457 static bool isPredicatedBlock(unsigned BlockNum) {
2458   return BlockNum % 2;
2459 }
2460
2461 ///\brief Perform cse of induction variable instructions.
2462 static void cse(SmallVector<BasicBlock *, 4> &BBs) {
2463   // Perform simple cse.
2464   SmallDenseMap<Instruction *, Instruction *, 4, CSEDenseMapInfo> CSEMap;
2465   for (unsigned i = 0, e = BBs.size(); i != e; ++i) {
2466     BasicBlock *BB = BBs[i];
2467     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
2468       Instruction *In = I++;
2469
2470       if (!CSEDenseMapInfo::canHandle(In))
2471         continue;
2472
2473       // Check if we can replace this instruction with any of the
2474       // visited instructions.
2475       if (Instruction *V = CSEMap.lookup(In)) {
2476         In->replaceAllUsesWith(V);
2477         In->eraseFromParent();
2478         continue;
2479       }
2480       // Ignore instructions in conditional blocks. We create "if (pred) a[i] =
2481       // ...;" blocks for predicated stores. Every second block is a predicated
2482       // block.
2483       if (isPredicatedBlock(i))
2484         continue;
2485
2486       CSEMap[In] = In;
2487     }
2488   }
2489 }
2490
2491 void InnerLoopVectorizer::vectorizeLoop() {
2492   //===------------------------------------------------===//
2493   //
2494   // Notice: any optimization or new instruction that go
2495   // into the code below should be also be implemented in
2496   // the cost-model.
2497   //
2498   //===------------------------------------------------===//
2499   Constant *Zero = Builder.getInt32(0);
2500
2501   // In order to support reduction variables we need to be able to vectorize
2502   // Phi nodes. Phi nodes have cycles, so we need to vectorize them in two
2503   // stages. First, we create a new vector PHI node with no incoming edges.
2504   // We use this value when we vectorize all of the instructions that use the
2505   // PHI. Next, after all of the instructions in the block are complete we
2506   // add the new incoming edges to the PHI. At this point all of the
2507   // instructions in the basic block are vectorized, so we can use them to
2508   // construct the PHI.
2509   PhiVector RdxPHIsToFix;
2510
2511   // Scan the loop in a topological order to ensure that defs are vectorized
2512   // before users.
2513   LoopBlocksDFS DFS(OrigLoop);
2514   DFS.perform(LI);
2515
2516   // Vectorize all of the blocks in the original loop.
2517   for (LoopBlocksDFS::RPOIterator bb = DFS.beginRPO(),
2518        be = DFS.endRPO(); bb != be; ++bb)
2519     vectorizeBlockInLoop(*bb, &RdxPHIsToFix);
2520
2521   // At this point every instruction in the original loop is widened to
2522   // a vector form. We are almost done. Now, we need to fix the PHI nodes
2523   // that we vectorized. The PHI nodes are currently empty because we did
2524   // not want to introduce cycles. Notice that the remaining PHI nodes
2525   // that we need to fix are reduction variables.
2526
2527   // Create the 'reduced' values for each of the induction vars.
2528   // The reduced values are the vector values that we scalarize and combine
2529   // after the loop is finished.
2530   for (PhiVector::iterator it = RdxPHIsToFix.begin(), e = RdxPHIsToFix.end();
2531        it != e; ++it) {
2532     PHINode *RdxPhi = *it;
2533     assert(RdxPhi && "Unable to recover vectorized PHI");
2534
2535     // Find the reduction variable descriptor.
2536     assert(Legal->getReductionVars()->count(RdxPhi) &&
2537            "Unable to find the reduction variable");
2538     LoopVectorizationLegality::ReductionDescriptor RdxDesc =
2539     (*Legal->getReductionVars())[RdxPhi];
2540
2541     setDebugLocFromInst(Builder, RdxDesc.StartValue);
2542
2543     // We need to generate a reduction vector from the incoming scalar.
2544     // To do so, we need to generate the 'identity' vector and override
2545     // one of the elements with the incoming scalar reduction. We need
2546     // to do it in the vector-loop preheader.
2547     Builder.SetInsertPoint(LoopBypassBlocks.front()->getTerminator());
2548
2549     // This is the vector-clone of the value that leaves the loop.
2550     VectorParts &VectorExit = getVectorValue(RdxDesc.LoopExitInstr);
2551     Type *VecTy = VectorExit[0]->getType();
2552
2553     // Find the reduction identity variable. Zero for addition, or, xor,
2554     // one for multiplication, -1 for And.
2555     Value *Identity;
2556     Value *VectorStart;
2557     if (RdxDesc.Kind == LoopVectorizationLegality::RK_IntegerMinMax ||
2558         RdxDesc.Kind == LoopVectorizationLegality::RK_FloatMinMax) {
2559       // MinMax reduction have the start value as their identify.
2560       if (VF == 1) {
2561         VectorStart = Identity = RdxDesc.StartValue;
2562       } else {
2563         VectorStart = Identity = Builder.CreateVectorSplat(VF,
2564                                                            RdxDesc.StartValue,
2565                                                            "minmax.ident");
2566       }
2567     } else {
2568       // Handle other reduction kinds:
2569       Constant *Iden =
2570       LoopVectorizationLegality::getReductionIdentity(RdxDesc.Kind,
2571                                                       VecTy->getScalarType());
2572       if (VF == 1) {
2573         Identity = Iden;
2574         // This vector is the Identity vector where the first element is the
2575         // incoming scalar reduction.
2576         VectorStart = RdxDesc.StartValue;
2577       } else {
2578         Identity = ConstantVector::getSplat(VF, Iden);
2579
2580         // This vector is the Identity vector where the first element is the
2581         // incoming scalar reduction.
2582         VectorStart = Builder.CreateInsertElement(Identity,
2583                                                   RdxDesc.StartValue, Zero);
2584       }
2585     }
2586
2587     // Fix the vector-loop phi.
2588     // We created the induction variable so we know that the
2589     // preheader is the first entry.
2590     BasicBlock *VecPreheader = Induction->getIncomingBlock(0);
2591
2592     // Reductions do not have to start at zero. They can start with
2593     // any loop invariant values.
2594     VectorParts &VecRdxPhi = WidenMap.get(RdxPhi);
2595     BasicBlock *Latch = OrigLoop->getLoopLatch();
2596     Value *LoopVal = RdxPhi->getIncomingValueForBlock(Latch);
2597     VectorParts &Val = getVectorValue(LoopVal);
2598     for (unsigned part = 0; part < UF; ++part) {
2599       // Make sure to add the reduction stat value only to the
2600       // first unroll part.
2601       Value *StartVal = (part == 0) ? VectorStart : Identity;
2602       cast<PHINode>(VecRdxPhi[part])->addIncoming(StartVal, VecPreheader);
2603       cast<PHINode>(VecRdxPhi[part])->addIncoming(Val[part],
2604                                                   LoopVectorBody.back());
2605     }
2606
2607     // Before each round, move the insertion point right between
2608     // the PHIs and the values we are going to write.
2609     // This allows us to write both PHINodes and the extractelement
2610     // instructions.
2611     Builder.SetInsertPoint(LoopMiddleBlock->getFirstInsertionPt());
2612
2613     VectorParts RdxParts;
2614     setDebugLocFromInst(Builder, RdxDesc.LoopExitInstr);
2615     for (unsigned part = 0; part < UF; ++part) {
2616       // This PHINode contains the vectorized reduction variable, or
2617       // the initial value vector, if we bypass the vector loop.
2618       VectorParts &RdxExitVal = getVectorValue(RdxDesc.LoopExitInstr);
2619       PHINode *NewPhi = Builder.CreatePHI(VecTy, 2, "rdx.vec.exit.phi");
2620       Value *StartVal = (part == 0) ? VectorStart : Identity;
2621       for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I)
2622         NewPhi->addIncoming(StartVal, LoopBypassBlocks[I]);
2623       NewPhi->addIncoming(RdxExitVal[part],
2624                           LoopVectorBody.back());
2625       RdxParts.push_back(NewPhi);
2626     }
2627
2628     // Reduce all of the unrolled parts into a single vector.
2629     Value *ReducedPartRdx = RdxParts[0];
2630     unsigned Op = getReductionBinOp(RdxDesc.Kind);
2631     setDebugLocFromInst(Builder, ReducedPartRdx);
2632     for (unsigned part = 1; part < UF; ++part) {
2633       if (Op != Instruction::ICmp && Op != Instruction::FCmp)
2634         ReducedPartRdx = Builder.CreateBinOp((Instruction::BinaryOps)Op,
2635                                              RdxParts[part], ReducedPartRdx,
2636                                              "bin.rdx");
2637       else
2638         ReducedPartRdx = createMinMaxOp(Builder, RdxDesc.MinMaxKind,
2639                                         ReducedPartRdx, RdxParts[part]);
2640     }
2641
2642     if (VF > 1) {
2643       // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
2644       // and vector ops, reducing the set of values being computed by half each
2645       // round.
2646       assert(isPowerOf2_32(VF) &&
2647              "Reduction emission only supported for pow2 vectors!");
2648       Value *TmpVec = ReducedPartRdx;
2649       SmallVector<Constant*, 32> ShuffleMask(VF, 0);
2650       for (unsigned i = VF; i != 1; i >>= 1) {
2651         // Move the upper half of the vector to the lower half.
2652         for (unsigned j = 0; j != i/2; ++j)
2653           ShuffleMask[j] = Builder.getInt32(i/2 + j);
2654
2655         // Fill the rest of the mask with undef.
2656         std::fill(&ShuffleMask[i/2], ShuffleMask.end(),
2657                   UndefValue::get(Builder.getInt32Ty()));
2658
2659         Value *Shuf =
2660         Builder.CreateShuffleVector(TmpVec,
2661                                     UndefValue::get(TmpVec->getType()),
2662                                     ConstantVector::get(ShuffleMask),
2663                                     "rdx.shuf");
2664
2665         if (Op != Instruction::ICmp && Op != Instruction::FCmp)
2666           TmpVec = Builder.CreateBinOp((Instruction::BinaryOps)Op, TmpVec, Shuf,
2667                                        "bin.rdx");
2668         else
2669           TmpVec = createMinMaxOp(Builder, RdxDesc.MinMaxKind, TmpVec, Shuf);
2670       }
2671
2672       // The result is in the first element of the vector.
2673       ReducedPartRdx = Builder.CreateExtractElement(TmpVec,
2674                                                     Builder.getInt32(0));
2675     }
2676
2677     // Now, we need to fix the users of the reduction variable
2678     // inside and outside of the scalar remainder loop.
2679     // We know that the loop is in LCSSA form. We need to update the
2680     // PHI nodes in the exit blocks.
2681     for (BasicBlock::iterator LEI = LoopExitBlock->begin(),
2682          LEE = LoopExitBlock->end(); LEI != LEE; ++LEI) {
2683       PHINode *LCSSAPhi = dyn_cast<PHINode>(LEI);
2684       if (!LCSSAPhi) break;
2685
2686       // All PHINodes need to have a single entry edge, or two if
2687       // we already fixed them.
2688       assert(LCSSAPhi->getNumIncomingValues() < 3 && "Invalid LCSSA PHI");
2689
2690       // We found our reduction value exit-PHI. Update it with the
2691       // incoming bypass edge.
2692       if (LCSSAPhi->getIncomingValue(0) == RdxDesc.LoopExitInstr) {
2693         // Add an edge coming from the bypass.
2694         LCSSAPhi->addIncoming(ReducedPartRdx, LoopMiddleBlock);
2695         break;
2696       }
2697     }// end of the LCSSA phi scan.
2698
2699     // Fix the scalar loop reduction variable with the incoming reduction sum
2700     // from the vector body and from the backedge value.
2701     int IncomingEdgeBlockIdx =
2702     (RdxPhi)->getBasicBlockIndex(OrigLoop->getLoopLatch());
2703     assert(IncomingEdgeBlockIdx >= 0 && "Invalid block index");
2704     // Pick the other block.
2705     int SelfEdgeBlockIdx = (IncomingEdgeBlockIdx ? 0 : 1);
2706     (RdxPhi)->setIncomingValue(SelfEdgeBlockIdx, ReducedPartRdx);
2707     (RdxPhi)->setIncomingValue(IncomingEdgeBlockIdx, RdxDesc.LoopExitInstr);
2708   }// end of for each redux variable.
2709
2710   fixLCSSAPHIs();
2711
2712   // Remove redundant induction instructions.
2713   cse(LoopVectorBody);
2714 }
2715
2716 void InnerLoopVectorizer::fixLCSSAPHIs() {
2717   for (BasicBlock::iterator LEI = LoopExitBlock->begin(),
2718        LEE = LoopExitBlock->end(); LEI != LEE; ++LEI) {
2719     PHINode *LCSSAPhi = dyn_cast<PHINode>(LEI);
2720     if (!LCSSAPhi) break;
2721     if (LCSSAPhi->getNumIncomingValues() == 1)
2722       LCSSAPhi->addIncoming(UndefValue::get(LCSSAPhi->getType()),
2723                             LoopMiddleBlock);
2724   }
2725
2726
2727 InnerLoopVectorizer::VectorParts
2728 InnerLoopVectorizer::createEdgeMask(BasicBlock *Src, BasicBlock *Dst) {
2729   assert(std::find(pred_begin(Dst), pred_end(Dst), Src) != pred_end(Dst) &&
2730          "Invalid edge");
2731
2732   // Look for cached value.
2733   std::pair<BasicBlock*, BasicBlock*> Edge(Src, Dst);
2734   EdgeMaskCache::iterator ECEntryIt = MaskCache.find(Edge);
2735   if (ECEntryIt != MaskCache.end())
2736     return ECEntryIt->second;
2737
2738   VectorParts SrcMask = createBlockInMask(Src);
2739
2740   // The terminator has to be a branch inst!
2741   BranchInst *BI = dyn_cast<BranchInst>(Src->getTerminator());
2742   assert(BI && "Unexpected terminator found");
2743
2744   if (BI->isConditional()) {
2745     VectorParts EdgeMask = getVectorValue(BI->getCondition());
2746
2747     if (BI->getSuccessor(0) != Dst)
2748       for (unsigned part = 0; part < UF; ++part)
2749         EdgeMask[part] = Builder.CreateNot(EdgeMask[part]);
2750
2751     for (unsigned part = 0; part < UF; ++part)
2752       EdgeMask[part] = Builder.CreateAnd(EdgeMask[part], SrcMask[part]);
2753
2754     MaskCache[Edge] = EdgeMask;
2755     return EdgeMask;
2756   }
2757
2758   MaskCache[Edge] = SrcMask;
2759   return SrcMask;
2760 }
2761
2762 InnerLoopVectorizer::VectorParts
2763 InnerLoopVectorizer::createBlockInMask(BasicBlock *BB) {
2764   assert(OrigLoop->contains(BB) && "Block is not a part of a loop");
2765
2766   // Loop incoming mask is all-one.
2767   if (OrigLoop->getHeader() == BB) {
2768     Value *C = ConstantInt::get(IntegerType::getInt1Ty(BB->getContext()), 1);
2769     return getVectorValue(C);
2770   }
2771
2772   // This is the block mask. We OR all incoming edges, and with zero.
2773   Value *Zero = ConstantInt::get(IntegerType::getInt1Ty(BB->getContext()), 0);
2774   VectorParts BlockMask = getVectorValue(Zero);
2775
2776   // For each pred:
2777   for (pred_iterator it = pred_begin(BB), e = pred_end(BB); it != e; ++it) {
2778     VectorParts EM = createEdgeMask(*it, BB);
2779     for (unsigned part = 0; part < UF; ++part)
2780       BlockMask[part] = Builder.CreateOr(BlockMask[part], EM[part]);
2781   }
2782
2783   return BlockMask;
2784 }
2785
2786 void InnerLoopVectorizer::widenPHIInstruction(Instruction *PN,
2787                                               InnerLoopVectorizer::VectorParts &Entry,
2788                                               unsigned UF, unsigned VF, PhiVector *PV) {
2789   PHINode* P = cast<PHINode>(PN);
2790   // Handle reduction variables:
2791   if (Legal->getReductionVars()->count(P)) {
2792     for (unsigned part = 0; part < UF; ++part) {
2793       // This is phase one of vectorizing PHIs.
2794       Type *VecTy = (VF == 1) ? PN->getType() :
2795       VectorType::get(PN->getType(), VF);
2796       Entry[part] = PHINode::Create(VecTy, 2, "vec.phi",
2797                                     LoopVectorBody.back()-> getFirstInsertionPt());
2798     }
2799     PV->push_back(P);
2800     return;
2801   }
2802
2803   setDebugLocFromInst(Builder, P);
2804   // Check for PHI nodes that are lowered to vector selects.
2805   if (P->getParent() != OrigLoop->getHeader()) {
2806     // We know that all PHIs in non-header blocks are converted into
2807     // selects, so we don't have to worry about the insertion order and we
2808     // can just use the builder.
2809     // At this point we generate the predication tree. There may be
2810     // duplications since this is a simple recursive scan, but future
2811     // optimizations will clean it up.
2812
2813     unsigned NumIncoming = P->getNumIncomingValues();
2814
2815     // Generate a sequence of selects of the form:
2816     // SELECT(Mask3, In3,
2817     //      SELECT(Mask2, In2,
2818     //                   ( ...)))
2819     for (unsigned In = 0; In < NumIncoming; In++) {
2820       VectorParts Cond = createEdgeMask(P->getIncomingBlock(In),
2821                                         P->getParent());
2822       VectorParts &In0 = getVectorValue(P->getIncomingValue(In));
2823
2824       for (unsigned part = 0; part < UF; ++part) {
2825         // We might have single edge PHIs (blocks) - use an identity
2826         // 'select' for the first PHI operand.
2827         if (In == 0)
2828           Entry[part] = Builder.CreateSelect(Cond[part], In0[part],
2829                                              In0[part]);
2830         else
2831           // Select between the current value and the previous incoming edge
2832           // based on the incoming mask.
2833           Entry[part] = Builder.CreateSelect(Cond[part], In0[part],
2834                                              Entry[part], "predphi");
2835       }
2836     }
2837     return;
2838   }
2839
2840   // This PHINode must be an induction variable.
2841   // Make sure that we know about it.
2842   assert(Legal->getInductionVars()->count(P) &&
2843          "Not an induction variable");
2844
2845   LoopVectorizationLegality::InductionInfo II =
2846   Legal->getInductionVars()->lookup(P);
2847
2848   switch (II.IK) {
2849     case LoopVectorizationLegality::IK_NoInduction:
2850       llvm_unreachable("Unknown induction");
2851     case LoopVectorizationLegality::IK_IntInduction: {
2852       assert(P->getType() == II.StartValue->getType() && "Types must match");
2853       Type *PhiTy = P->getType();
2854       Value *Broadcasted;
2855       if (P == OldInduction) {
2856         // Handle the canonical induction variable. We might have had to
2857         // extend the type.
2858         Broadcasted = Builder.CreateTrunc(Induction, PhiTy);
2859       } else {
2860         // Handle other induction variables that are now based on the
2861         // canonical one.
2862         Value *NormalizedIdx = Builder.CreateSub(Induction, ExtendedIdx,
2863                                                  "normalized.idx");
2864         NormalizedIdx = Builder.CreateSExtOrTrunc(NormalizedIdx, PhiTy);
2865         Broadcasted = Builder.CreateAdd(II.StartValue, NormalizedIdx,
2866                                         "offset.idx");
2867       }
2868       Broadcasted = getBroadcastInstrs(Broadcasted);
2869       // After broadcasting the induction variable we need to make the vector
2870       // consecutive by adding 0, 1, 2, etc.
2871       for (unsigned part = 0; part < UF; ++part)
2872         Entry[part] = getConsecutiveVector(Broadcasted, VF * part, false);
2873       return;
2874     }
2875     case LoopVectorizationLegality::IK_ReverseIntInduction:
2876     case LoopVectorizationLegality::IK_PtrInduction:
2877     case LoopVectorizationLegality::IK_ReversePtrInduction:
2878       // Handle reverse integer and pointer inductions.
2879       Value *StartIdx = ExtendedIdx;
2880       // This is the normalized GEP that starts counting at zero.
2881       Value *NormalizedIdx = Builder.CreateSub(Induction, StartIdx,
2882                                                "normalized.idx");
2883
2884       // Handle the reverse integer induction variable case.
2885       if (LoopVectorizationLegality::IK_ReverseIntInduction == II.IK) {
2886         IntegerType *DstTy = cast<IntegerType>(II.StartValue->getType());
2887         Value *CNI = Builder.CreateSExtOrTrunc(NormalizedIdx, DstTy,
2888                                                "resize.norm.idx");
2889         Value *ReverseInd  = Builder.CreateSub(II.StartValue, CNI,
2890                                                "reverse.idx");
2891
2892         // This is a new value so do not hoist it out.
2893         Value *Broadcasted = getBroadcastInstrs(ReverseInd);
2894         // After broadcasting the induction variable we need to make the
2895         // vector consecutive by adding  ... -3, -2, -1, 0.
2896         for (unsigned part = 0; part < UF; ++part)
2897           Entry[part] = getConsecutiveVector(Broadcasted, -(int)VF * part,
2898                                              true);
2899         return;
2900       }
2901
2902       // Handle the pointer induction variable case.
2903       assert(P->getType()->isPointerTy() && "Unexpected type.");
2904
2905       // Is this a reverse induction ptr or a consecutive induction ptr.
2906       bool Reverse = (LoopVectorizationLegality::IK_ReversePtrInduction ==
2907                       II.IK);
2908
2909       // This is the vector of results. Notice that we don't generate
2910       // vector geps because scalar geps result in better code.
2911       for (unsigned part = 0; part < UF; ++part) {
2912         if (VF == 1) {
2913           int EltIndex = (part) * (Reverse ? -1 : 1);
2914           Constant *Idx = ConstantInt::get(Induction->getType(), EltIndex);
2915           Value *GlobalIdx;
2916           if (Reverse)
2917             GlobalIdx = Builder.CreateSub(Idx, NormalizedIdx, "gep.ridx");
2918           else
2919             GlobalIdx = Builder.CreateAdd(NormalizedIdx, Idx, "gep.idx");
2920
2921           Value *SclrGep = Builder.CreateGEP(II.StartValue, GlobalIdx,
2922                                              "next.gep");
2923           Entry[part] = SclrGep;
2924           continue;
2925         }
2926
2927         Value *VecVal = UndefValue::get(VectorType::get(P->getType(), VF));
2928         for (unsigned int i = 0; i < VF; ++i) {
2929           int EltIndex = (i + part * VF) * (Reverse ? -1 : 1);
2930           Constant *Idx = ConstantInt::get(Induction->getType(), EltIndex);
2931           Value *GlobalIdx;
2932           if (!Reverse)
2933             GlobalIdx = Builder.CreateAdd(NormalizedIdx, Idx, "gep.idx");
2934           else
2935             GlobalIdx = Builder.CreateSub(Idx, NormalizedIdx, "gep.ridx");
2936
2937           Value *SclrGep = Builder.CreateGEP(II.StartValue, GlobalIdx,
2938                                              "next.gep");
2939           VecVal = Builder.CreateInsertElement(VecVal, SclrGep,
2940                                                Builder.getInt32(i),
2941                                                "insert.gep");
2942         }
2943         Entry[part] = VecVal;
2944       }
2945       return;
2946   }
2947 }
2948
2949 void InnerLoopVectorizer::vectorizeBlockInLoop(BasicBlock *BB, PhiVector *PV) {
2950   // For each instruction in the old loop.
2951   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
2952     VectorParts &Entry = WidenMap.get(it);
2953     switch (it->getOpcode()) {
2954     case Instruction::Br:
2955       // Nothing to do for PHIs and BR, since we already took care of the
2956       // loop control flow instructions.
2957       continue;
2958     case Instruction::PHI:{
2959       // Vectorize PHINodes.
2960       widenPHIInstruction(it, Entry, UF, VF, PV);
2961       continue;
2962     }// End of PHI.
2963
2964     case Instruction::Add:
2965     case Instruction::FAdd:
2966     case Instruction::Sub:
2967     case Instruction::FSub:
2968     case Instruction::Mul:
2969     case Instruction::FMul:
2970     case Instruction::UDiv:
2971     case Instruction::SDiv:
2972     case Instruction::FDiv:
2973     case Instruction::URem:
2974     case Instruction::SRem:
2975     case Instruction::FRem:
2976     case Instruction::Shl:
2977     case Instruction::LShr:
2978     case Instruction::AShr:
2979     case Instruction::And:
2980     case Instruction::Or:
2981     case Instruction::Xor: {
2982       // Just widen binops.
2983       BinaryOperator *BinOp = dyn_cast<BinaryOperator>(it);
2984       setDebugLocFromInst(Builder, BinOp);
2985       VectorParts &A = getVectorValue(it->getOperand(0));
2986       VectorParts &B = getVectorValue(it->getOperand(1));
2987
2988       // Use this vector value for all users of the original instruction.
2989       for (unsigned Part = 0; Part < UF; ++Part) {
2990         Value *V = Builder.CreateBinOp(BinOp->getOpcode(), A[Part], B[Part]);
2991
2992         // Update the NSW, NUW and Exact flags. Notice: V can be an Undef.
2993         BinaryOperator *VecOp = dyn_cast<BinaryOperator>(V);
2994         if (VecOp && isa<OverflowingBinaryOperator>(BinOp)) {
2995           VecOp->setHasNoSignedWrap(BinOp->hasNoSignedWrap());
2996           VecOp->setHasNoUnsignedWrap(BinOp->hasNoUnsignedWrap());
2997         }
2998         if (VecOp && isa<PossiblyExactOperator>(VecOp))
2999           VecOp->setIsExact(BinOp->isExact());
3000
3001         Entry[Part] = V;
3002       }
3003       break;
3004     }
3005     case Instruction::Select: {
3006       // Widen selects.
3007       // If the selector is loop invariant we can create a select
3008       // instruction with a scalar condition. Otherwise, use vector-select.
3009       bool InvariantCond = SE->isLoopInvariant(SE->getSCEV(it->getOperand(0)),
3010                                                OrigLoop);
3011       setDebugLocFromInst(Builder, it);
3012
3013       // The condition can be loop invariant  but still defined inside the
3014       // loop. This means that we can't just use the original 'cond' value.
3015       // We have to take the 'vectorized' value and pick the first lane.
3016       // Instcombine will make this a no-op.
3017       VectorParts &Cond = getVectorValue(it->getOperand(0));
3018       VectorParts &Op0  = getVectorValue(it->getOperand(1));
3019       VectorParts &Op1  = getVectorValue(it->getOperand(2));
3020
3021       Value *ScalarCond = (VF == 1) ? Cond[0] :
3022         Builder.CreateExtractElement(Cond[0], Builder.getInt32(0));
3023
3024       for (unsigned Part = 0; Part < UF; ++Part) {
3025         Entry[Part] = Builder.CreateSelect(
3026           InvariantCond ? ScalarCond : Cond[Part],
3027           Op0[Part],
3028           Op1[Part]);
3029       }
3030       break;
3031     }
3032
3033     case Instruction::ICmp:
3034     case Instruction::FCmp: {
3035       // Widen compares. Generate vector compares.
3036       bool FCmp = (it->getOpcode() == Instruction::FCmp);
3037       CmpInst *Cmp = dyn_cast<CmpInst>(it);
3038       setDebugLocFromInst(Builder, it);
3039       VectorParts &A = getVectorValue(it->getOperand(0));
3040       VectorParts &B = getVectorValue(it->getOperand(1));
3041       for (unsigned Part = 0; Part < UF; ++Part) {
3042         Value *C = 0;
3043         if (FCmp)
3044           C = Builder.CreateFCmp(Cmp->getPredicate(), A[Part], B[Part]);
3045         else
3046           C = Builder.CreateICmp(Cmp->getPredicate(), A[Part], B[Part]);
3047         Entry[Part] = C;
3048       }
3049       break;
3050     }
3051
3052     case Instruction::Store:
3053     case Instruction::Load:
3054       vectorizeMemoryInstruction(it);
3055         break;
3056     case Instruction::ZExt:
3057     case Instruction::SExt:
3058     case Instruction::FPToUI:
3059     case Instruction::FPToSI:
3060     case Instruction::FPExt:
3061     case Instruction::PtrToInt:
3062     case Instruction::IntToPtr:
3063     case Instruction::SIToFP:
3064     case Instruction::UIToFP:
3065     case Instruction::Trunc:
3066     case Instruction::FPTrunc:
3067     case Instruction::BitCast: {
3068       CastInst *CI = dyn_cast<CastInst>(it);
3069       setDebugLocFromInst(Builder, it);
3070       /// Optimize the special case where the source is the induction
3071       /// variable. Notice that we can only optimize the 'trunc' case
3072       /// because: a. FP conversions lose precision, b. sext/zext may wrap,
3073       /// c. other casts depend on pointer size.
3074       if (CI->getOperand(0) == OldInduction &&
3075           it->getOpcode() == Instruction::Trunc) {
3076         Value *ScalarCast = Builder.CreateCast(CI->getOpcode(), Induction,
3077                                                CI->getType());
3078         Value *Broadcasted = getBroadcastInstrs(ScalarCast);
3079         for (unsigned Part = 0; Part < UF; ++Part)
3080           Entry[Part] = getConsecutiveVector(Broadcasted, VF * Part, false);
3081         break;
3082       }
3083       /// Vectorize casts.
3084       Type *DestTy = (VF == 1) ? CI->getType() :
3085                                  VectorType::get(CI->getType(), VF);
3086
3087       VectorParts &A = getVectorValue(it->getOperand(0));
3088       for (unsigned Part = 0; Part < UF; ++Part)
3089         Entry[Part] = Builder.CreateCast(CI->getOpcode(), A[Part], DestTy);
3090       break;
3091     }
3092
3093     case Instruction::Call: {
3094       // Ignore dbg intrinsics.
3095       if (isa<DbgInfoIntrinsic>(it))
3096         break;
3097       setDebugLocFromInst(Builder, it);
3098
3099       Module *M = BB->getParent()->getParent();
3100       CallInst *CI = cast<CallInst>(it);
3101       Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
3102       assert(ID && "Not an intrinsic call!");
3103       switch (ID) {
3104       case Intrinsic::lifetime_end:
3105       case Intrinsic::lifetime_start:
3106         scalarizeInstruction(it);
3107         break;
3108       default:
3109         for (unsigned Part = 0; Part < UF; ++Part) {
3110           SmallVector<Value *, 4> Args;
3111           for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i) {
3112             VectorParts &Arg = getVectorValue(CI->getArgOperand(i));
3113             Args.push_back(Arg[Part]);
3114           }
3115           Type *Tys[] = {CI->getType()};
3116           if (VF > 1)
3117             Tys[0] = VectorType::get(CI->getType()->getScalarType(), VF);
3118
3119           Function *F = Intrinsic::getDeclaration(M, ID, Tys);
3120           Entry[Part] = Builder.CreateCall(F, Args);
3121         }
3122         break;
3123       }
3124       break;
3125     }
3126
3127     default:
3128       // All other instructions are unsupported. Scalarize them.
3129       scalarizeInstruction(it);
3130       break;
3131     }// end of switch.
3132   }// end of for_each instr.
3133 }
3134
3135 void InnerLoopVectorizer::updateAnalysis() {
3136   // Forget the original basic block.
3137   SE->forgetLoop(OrigLoop);
3138
3139   // Update the dominator tree information.
3140   assert(DT->properlyDominates(LoopBypassBlocks.front(), LoopExitBlock) &&
3141          "Entry does not dominate exit.");
3142
3143   for (unsigned I = 1, E = LoopBypassBlocks.size(); I != E; ++I)
3144     DT->addNewBlock(LoopBypassBlocks[I], LoopBypassBlocks[I-1]);
3145   DT->addNewBlock(LoopVectorPreHeader, LoopBypassBlocks.back());
3146
3147   // Due to if predication of stores we might create a sequence of "if(pred)
3148   // a[i] = ...;  " blocks.
3149   for (unsigned i = 0, e = LoopVectorBody.size(); i != e; ++i) {
3150     if (i == 0)
3151       DT->addNewBlock(LoopVectorBody[0], LoopVectorPreHeader);
3152     else if (isPredicatedBlock(i)) {
3153       DT->addNewBlock(LoopVectorBody[i], LoopVectorBody[i-1]);
3154     } else {
3155       DT->addNewBlock(LoopVectorBody[i], LoopVectorBody[i-2]);
3156     }
3157   }
3158
3159   DT->addNewBlock(LoopMiddleBlock, LoopBypassBlocks.front());
3160   DT->addNewBlock(LoopScalarPreHeader, LoopMiddleBlock);
3161   DT->changeImmediateDominator(LoopScalarBody, LoopScalarPreHeader);
3162   DT->changeImmediateDominator(LoopExitBlock, LoopMiddleBlock);
3163
3164   DEBUG(DT->verifyDomTree());
3165 }
3166
3167 /// \brief Check whether it is safe to if-convert this phi node.
3168 ///
3169 /// Phi nodes with constant expressions that can trap are not safe to if
3170 /// convert.
3171 static bool canIfConvertPHINodes(BasicBlock *BB) {
3172   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
3173     PHINode *Phi = dyn_cast<PHINode>(I);
3174     if (!Phi)
3175       return true;
3176     for (unsigned p = 0, e = Phi->getNumIncomingValues(); p != e; ++p)
3177       if (Constant *C = dyn_cast<Constant>(Phi->getIncomingValue(p)))
3178         if (C->canTrap())
3179           return false;
3180   }
3181   return true;
3182 }
3183
3184 bool LoopVectorizationLegality::canVectorizeWithIfConvert() {
3185   if (!EnableIfConversion)
3186     return false;
3187
3188   assert(TheLoop->getNumBlocks() > 1 && "Single block loops are vectorizable");
3189
3190   // A list of pointers that we can safely read and write to.
3191   SmallPtrSet<Value *, 8> SafePointes;
3192
3193   // Collect safe addresses.
3194   for (Loop::block_iterator BI = TheLoop->block_begin(),
3195          BE = TheLoop->block_end(); BI != BE; ++BI) {
3196     BasicBlock *BB = *BI;
3197
3198     if (blockNeedsPredication(BB))
3199       continue;
3200
3201     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
3202       if (LoadInst *LI = dyn_cast<LoadInst>(I))
3203         SafePointes.insert(LI->getPointerOperand());
3204       else if (StoreInst *SI = dyn_cast<StoreInst>(I))
3205         SafePointes.insert(SI->getPointerOperand());
3206     }
3207   }
3208
3209   // Collect the blocks that need predication.
3210   BasicBlock *Header = TheLoop->getHeader();
3211   for (Loop::block_iterator BI = TheLoop->block_begin(),
3212          BE = TheLoop->block_end(); BI != BE; ++BI) {
3213     BasicBlock *BB = *BI;
3214
3215     // We don't support switch statements inside loops.
3216     if (!isa<BranchInst>(BB->getTerminator()))
3217       return false;
3218
3219     // We must be able to predicate all blocks that need to be predicated.
3220     if (blockNeedsPredication(BB)) {
3221       if (!blockCanBePredicated(BB, SafePointes))
3222         return false;
3223     } else if (BB != Header && !canIfConvertPHINodes(BB))
3224       return false;
3225
3226   }
3227
3228   // We can if-convert this loop.
3229   return true;
3230 }
3231
3232 bool LoopVectorizationLegality::canVectorize() {
3233   // We must have a loop in canonical form. Loops with indirectbr in them cannot
3234   // be canonicalized.
3235   if (!TheLoop->getLoopPreheader())
3236     return false;
3237
3238   // We can only vectorize innermost loops.
3239   if (TheLoop->getSubLoopsVector().size())
3240     return false;
3241
3242   // We must have a single backedge.
3243   if (TheLoop->getNumBackEdges() != 1)
3244     return false;
3245
3246   // We must have a single exiting block.
3247   if (!TheLoop->getExitingBlock())
3248     return false;
3249
3250   // We need to have a loop header.
3251   DEBUG(dbgs() << "LV: Found a loop: " <<
3252         TheLoop->getHeader()->getName() << '\n');
3253
3254   // Check if we can if-convert non-single-bb loops.
3255   unsigned NumBlocks = TheLoop->getNumBlocks();
3256   if (NumBlocks != 1 && !canVectorizeWithIfConvert()) {
3257     DEBUG(dbgs() << "LV: Can't if-convert the loop.\n");
3258     return false;
3259   }
3260
3261   // ScalarEvolution needs to be able to find the exit count.
3262   const SCEV *ExitCount = SE->getBackedgeTakenCount(TheLoop);
3263   if (ExitCount == SE->getCouldNotCompute()) {
3264     DEBUG(dbgs() << "LV: SCEV could not compute the loop exit count.\n");
3265     return false;
3266   }
3267
3268   // Do not loop-vectorize loops with a tiny trip count.
3269   BasicBlock *Latch = TheLoop->getLoopLatch();
3270   unsigned TC = SE->getSmallConstantTripCount(TheLoop, Latch);
3271   if (TC > 0u && TC < TinyTripCountVectorThreshold) {
3272     DEBUG(dbgs() << "LV: Found a loop with a very small trip count. " <<
3273           "This loop is not worth vectorizing.\n");
3274     return false;
3275   }
3276
3277   // Check if we can vectorize the instructions and CFG in this loop.
3278   if (!canVectorizeInstrs()) {
3279     DEBUG(dbgs() << "LV: Can't vectorize the instructions or CFG\n");
3280     return false;
3281   }
3282
3283   // Go over each instruction and look at memory deps.
3284   if (!canVectorizeMemory()) {
3285     DEBUG(dbgs() << "LV: Can't vectorize due to memory conflicts\n");
3286     return false;
3287   }
3288
3289   // Collect all of the variables that remain uniform after vectorization.
3290   collectLoopUniforms();
3291
3292   DEBUG(dbgs() << "LV: We can vectorize this loop" <<
3293         (PtrRtCheck.Need ? " (with a runtime bound check)" : "")
3294         <<"!\n");
3295
3296   // Okay! We can vectorize. At this point we don't have any other mem analysis
3297   // which may limit our maximum vectorization factor, so just return true with
3298   // no restrictions.
3299   return true;
3300 }
3301
3302 static Type *convertPointerToIntegerType(const DataLayout &DL, Type *Ty) {
3303   if (Ty->isPointerTy())
3304     return DL.getIntPtrType(Ty);
3305
3306   // It is possible that char's or short's overflow when we ask for the loop's
3307   // trip count, work around this by changing the type size.
3308   if (Ty->getScalarSizeInBits() < 32)
3309     return Type::getInt32Ty(Ty->getContext());
3310
3311   return Ty;
3312 }
3313
3314 static Type* getWiderType(const DataLayout &DL, Type *Ty0, Type *Ty1) {
3315   Ty0 = convertPointerToIntegerType(DL, Ty0);
3316   Ty1 = convertPointerToIntegerType(DL, Ty1);
3317   if (Ty0->getScalarSizeInBits() > Ty1->getScalarSizeInBits())
3318     return Ty0;
3319   return Ty1;
3320 }
3321
3322 /// \brief Check that the instruction has outside loop users and is not an
3323 /// identified reduction variable.
3324 static bool hasOutsideLoopUser(const Loop *TheLoop, Instruction *Inst,
3325                                SmallPtrSet<Value *, 4> &Reductions) {
3326   // Reduction instructions are allowed to have exit users. All other
3327   // instructions must not have external users.
3328   if (!Reductions.count(Inst))
3329     //Check that all of the users of the loop are inside the BB.
3330     for (Value::use_iterator I = Inst->use_begin(), E = Inst->use_end();
3331          I != E; ++I) {
3332       Instruction *U = cast<Instruction>(*I);
3333       // This user may be a reduction exit value.
3334       if (!TheLoop->contains(U)) {
3335         DEBUG(dbgs() << "LV: Found an outside user for : " << *U << '\n');
3336         return true;
3337       }
3338     }
3339   return false;
3340 }
3341
3342 bool LoopVectorizationLegality::canVectorizeInstrs() {
3343   BasicBlock *PreHeader = TheLoop->getLoopPreheader();
3344   BasicBlock *Header = TheLoop->getHeader();
3345
3346   // Look for the attribute signaling the absence of NaNs.
3347   Function &F = *Header->getParent();
3348   if (F.hasFnAttribute("no-nans-fp-math"))
3349     HasFunNoNaNAttr = F.getAttributes().getAttribute(
3350       AttributeSet::FunctionIndex,
3351       "no-nans-fp-math").getValueAsString() == "true";
3352
3353   // For each block in the loop.
3354   for (Loop::block_iterator bb = TheLoop->block_begin(),
3355        be = TheLoop->block_end(); bb != be; ++bb) {
3356
3357     // Scan the instructions in the block and look for hazards.
3358     for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
3359          ++it) {
3360
3361       if (PHINode *Phi = dyn_cast<PHINode>(it)) {
3362         Type *PhiTy = Phi->getType();
3363         // Check that this PHI type is allowed.
3364         if (!PhiTy->isIntegerTy() &&
3365             !PhiTy->isFloatingPointTy() &&
3366             !PhiTy->isPointerTy()) {
3367           DEBUG(dbgs() << "LV: Found an non-int non-pointer PHI.\n");
3368           return false;
3369         }
3370
3371         // If this PHINode is not in the header block, then we know that we
3372         // can convert it to select during if-conversion. No need to check if
3373         // the PHIs in this block are induction or reduction variables.
3374         if (*bb != Header) {
3375           // Check that this instruction has no outside users or is an
3376           // identified reduction value with an outside user.
3377           if(!hasOutsideLoopUser(TheLoop, it, AllowedExit))
3378             continue;
3379           return false;
3380         }
3381
3382         // We only allow if-converted PHIs with more than two incoming values.
3383         if (Phi->getNumIncomingValues() != 2) {
3384           DEBUG(dbgs() << "LV: Found an invalid PHI.\n");
3385           return false;
3386         }
3387
3388         // This is the value coming from the preheader.
3389         Value *StartValue = Phi->getIncomingValueForBlock(PreHeader);
3390         // Check if this is an induction variable.
3391         InductionKind IK = isInductionVariable(Phi);
3392
3393         if (IK_NoInduction != IK) {
3394           // Get the widest type.
3395           if (!WidestIndTy)
3396             WidestIndTy = convertPointerToIntegerType(*DL, PhiTy);
3397           else
3398             WidestIndTy = getWiderType(*DL, PhiTy, WidestIndTy);
3399
3400           // Int inductions are special because we only allow one IV.
3401           if (IK == IK_IntInduction) {
3402             // Use the phi node with the widest type as induction. Use the last
3403             // one if there are multiple (no good reason for doing this other
3404             // than it is expedient).
3405             if (!Induction || PhiTy == WidestIndTy)
3406               Induction = Phi;
3407           }
3408
3409           DEBUG(dbgs() << "LV: Found an induction variable.\n");
3410           Inductions[Phi] = InductionInfo(StartValue, IK);
3411
3412           // Until we explicitly handle the case of an induction variable with
3413           // an outside loop user we have to give up vectorizing this loop.
3414           if (hasOutsideLoopUser(TheLoop, it, AllowedExit))
3415             return false;
3416
3417           continue;
3418         }
3419
3420         if (AddReductionVar(Phi, RK_IntegerAdd)) {
3421           DEBUG(dbgs() << "LV: Found an ADD reduction PHI."<< *Phi <<"\n");
3422           continue;
3423         }
3424         if (AddReductionVar(Phi, RK_IntegerMult)) {
3425           DEBUG(dbgs() << "LV: Found a MUL reduction PHI."<< *Phi <<"\n");
3426           continue;
3427         }
3428         if (AddReductionVar(Phi, RK_IntegerOr)) {
3429           DEBUG(dbgs() << "LV: Found an OR reduction PHI."<< *Phi <<"\n");
3430           continue;
3431         }
3432         if (AddReductionVar(Phi, RK_IntegerAnd)) {
3433           DEBUG(dbgs() << "LV: Found an AND reduction PHI."<< *Phi <<"\n");
3434           continue;
3435         }
3436         if (AddReductionVar(Phi, RK_IntegerXor)) {
3437           DEBUG(dbgs() << "LV: Found a XOR reduction PHI."<< *Phi <<"\n");
3438           continue;
3439         }
3440         if (AddReductionVar(Phi, RK_IntegerMinMax)) {
3441           DEBUG(dbgs() << "LV: Found a MINMAX reduction PHI."<< *Phi <<"\n");
3442           continue;
3443         }
3444         if (AddReductionVar(Phi, RK_FloatMult)) {
3445           DEBUG(dbgs() << "LV: Found an FMult reduction PHI."<< *Phi <<"\n");
3446           continue;
3447         }
3448         if (AddReductionVar(Phi, RK_FloatAdd)) {
3449           DEBUG(dbgs() << "LV: Found an FAdd reduction PHI."<< *Phi <<"\n");
3450           continue;
3451         }
3452         if (AddReductionVar(Phi, RK_FloatMinMax)) {
3453           DEBUG(dbgs() << "LV: Found an float MINMAX reduction PHI."<< *Phi <<
3454                 "\n");
3455           continue;
3456         }
3457
3458         DEBUG(dbgs() << "LV: Found an unidentified PHI."<< *Phi <<"\n");
3459         return false;
3460       }// end of PHI handling
3461
3462       // We still don't handle functions. However, we can ignore dbg intrinsic
3463       // calls and we do handle certain intrinsic and libm functions.
3464       CallInst *CI = dyn_cast<CallInst>(it);
3465       if (CI && !getIntrinsicIDForCall(CI, TLI) && !isa<DbgInfoIntrinsic>(CI)) {
3466         DEBUG(dbgs() << "LV: Found a call site.\n");
3467         return false;
3468       }
3469
3470       // Check that the instruction return type is vectorizable.
3471       // Also, we can't vectorize extractelement instructions.
3472       if ((!VectorType::isValidElementType(it->getType()) &&
3473            !it->getType()->isVoidTy()) || isa<ExtractElementInst>(it)) {
3474         DEBUG(dbgs() << "LV: Found unvectorizable type.\n");
3475         return false;
3476       }
3477
3478       // Check that the stored type is vectorizable.
3479       if (StoreInst *ST = dyn_cast<StoreInst>(it)) {
3480         Type *T = ST->getValueOperand()->getType();
3481         if (!VectorType::isValidElementType(T))
3482           return false;
3483         if (EnableMemAccessVersioning)
3484           collectStridedAcccess(ST);
3485       }
3486
3487       if (EnableMemAccessVersioning)
3488         if (LoadInst *LI = dyn_cast<LoadInst>(it))
3489           collectStridedAcccess(LI);
3490
3491       // Reduction instructions are allowed to have exit users.
3492       // All other instructions must not have external users.
3493       if (hasOutsideLoopUser(TheLoop, it, AllowedExit))
3494         return false;
3495
3496     } // next instr.
3497
3498   }
3499
3500   if (!Induction) {
3501     DEBUG(dbgs() << "LV: Did not find one integer induction var.\n");
3502     if (Inductions.empty())
3503       return false;
3504   }
3505
3506   return true;
3507 }
3508
3509 ///\brief Remove GEPs whose indices but the last one are loop invariant and
3510 /// return the induction operand of the gep pointer.
3511 static Value *stripGetElementPtr(Value *Ptr, ScalarEvolution *SE,
3512                                  const DataLayout *DL, Loop *Lp) {
3513   GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr);
3514   if (!GEP)
3515     return Ptr;
3516
3517   unsigned InductionOperand = getGEPInductionOperand(DL, GEP);
3518
3519   // Check that all of the gep indices are uniform except for our induction
3520   // operand.
3521   for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i)
3522     if (i != InductionOperand &&
3523         !SE->isLoopInvariant(SE->getSCEV(GEP->getOperand(i)), Lp))
3524       return Ptr;
3525   return GEP->getOperand(InductionOperand);
3526 }
3527
3528 ///\brief Look for a cast use of the passed value.
3529 static Value *getUniqueCastUse(Value *Ptr, Loop *Lp, Type *Ty) {
3530   Value *UniqueCast = 0;
3531   for (Value::use_iterator UI = Ptr->use_begin(), UE = Ptr->use_end(); UI != UE;
3532        ++UI) {
3533     CastInst *CI = dyn_cast<CastInst>(*UI);
3534     if (CI && CI->getType() == Ty) {
3535       if (!UniqueCast)
3536         UniqueCast = CI;
3537       else
3538         return 0;
3539     }
3540   }
3541   return UniqueCast;
3542 }
3543
3544 ///\brief Get the stride of a pointer access in a loop.
3545 /// Looks for symbolic strides "a[i*stride]". Returns the symbolic stride as a
3546 /// pointer to the Value, or null otherwise.
3547 static Value *getStrideFromPointer(Value *Ptr, ScalarEvolution *SE,
3548                                    const DataLayout *DL, Loop *Lp) {
3549   const PointerType *PtrTy = dyn_cast<PointerType>(Ptr->getType());
3550   if (!PtrTy || PtrTy->isAggregateType())
3551     return 0;
3552
3553   // Try to remove a gep instruction to make the pointer (actually index at this
3554   // point) easier analyzable. If OrigPtr is equal to Ptr we are analzying the
3555   // pointer, otherwise, we are analyzing the index.
3556   Value *OrigPtr = Ptr;
3557
3558   // The size of the pointer access.
3559   int64_t PtrAccessSize = 1;
3560
3561   Ptr = stripGetElementPtr(Ptr, SE, DL, Lp);
3562   const SCEV *V = SE->getSCEV(Ptr);
3563
3564   if (Ptr != OrigPtr)
3565     // Strip off casts.
3566     while (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V))
3567       V = C->getOperand();
3568
3569   const SCEVAddRecExpr *S = dyn_cast<SCEVAddRecExpr>(V);
3570   if (!S)
3571     return 0;
3572
3573   V = S->getStepRecurrence(*SE);
3574   if (!V)
3575     return 0;
3576
3577   // Strip off the size of access multiplication if we are still analyzing the
3578   // pointer.
3579   if (OrigPtr == Ptr) {
3580     DL->getTypeAllocSize(PtrTy->getElementType());
3581     if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(V)) {
3582       if (M->getOperand(0)->getSCEVType() != scConstant)
3583         return 0;
3584
3585       const APInt &APStepVal =
3586           cast<SCEVConstant>(M->getOperand(0))->getValue()->getValue();
3587
3588       // Huge step value - give up.
3589       if (APStepVal.getBitWidth() > 64)
3590         return 0;
3591
3592       int64_t StepVal = APStepVal.getSExtValue();
3593       if (PtrAccessSize != StepVal)
3594         return 0;
3595       V = M->getOperand(1);
3596     }
3597   }
3598
3599   // Strip off casts.
3600   Type *StripedOffRecurrenceCast = 0;
3601   if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V)) {
3602     StripedOffRecurrenceCast = C->getType();
3603     V = C->getOperand();
3604   }
3605
3606   // Look for the loop invariant symbolic value.
3607   const SCEVUnknown *U = dyn_cast<SCEVUnknown>(V);
3608   if (!U)
3609     return 0;
3610
3611   Value *Stride = U->getValue();
3612   if (!Lp->isLoopInvariant(Stride))
3613     return 0;
3614
3615   // If we have stripped off the recurrence cast we have to make sure that we
3616   // return the value that is used in this loop so that we can replace it later.
3617   if (StripedOffRecurrenceCast)
3618     Stride = getUniqueCastUse(Stride, Lp, StripedOffRecurrenceCast);
3619
3620   return Stride;
3621 }
3622
3623 void LoopVectorizationLegality::collectStridedAcccess(Value *MemAccess) {
3624   Value *Ptr = 0;
3625   if (LoadInst *LI = dyn_cast<LoadInst>(MemAccess))
3626     Ptr = LI->getPointerOperand();
3627   else if (StoreInst *SI = dyn_cast<StoreInst>(MemAccess))
3628     Ptr = SI->getPointerOperand();
3629   else
3630     return;
3631
3632   Value *Stride = getStrideFromPointer(Ptr, SE, DL, TheLoop);
3633   if (!Stride)
3634     return;
3635
3636   DEBUG(dbgs() << "LV: Found a strided access that we can version");
3637   DEBUG(dbgs() << "  Ptr: " << *Ptr << " Stride: " << *Stride << "\n");
3638   Strides[Ptr] = Stride;
3639   StrideSet.insert(Stride);
3640 }
3641
3642 void LoopVectorizationLegality::collectLoopUniforms() {
3643   // We now know that the loop is vectorizable!
3644   // Collect variables that will remain uniform after vectorization.
3645   std::vector<Value*> Worklist;
3646   BasicBlock *Latch = TheLoop->getLoopLatch();
3647
3648   // Start with the conditional branch and walk up the block.
3649   Worklist.push_back(Latch->getTerminator()->getOperand(0));
3650
3651   while (Worklist.size()) {
3652     Instruction *I = dyn_cast<Instruction>(Worklist.back());
3653     Worklist.pop_back();
3654
3655     // Look at instructions inside this loop.
3656     // Stop when reaching PHI nodes.
3657     // TODO: we need to follow values all over the loop, not only in this block.
3658     if (!I || !TheLoop->contains(I) || isa<PHINode>(I))
3659       continue;
3660
3661     // This is a known uniform.
3662     Uniforms.insert(I);
3663
3664     // Insert all operands.
3665     Worklist.insert(Worklist.end(), I->op_begin(), I->op_end());
3666   }
3667 }
3668
3669 namespace {
3670 /// \brief Analyses memory accesses in a loop.
3671 ///
3672 /// Checks whether run time pointer checks are needed and builds sets for data
3673 /// dependence checking.
3674 class AccessAnalysis {
3675 public:
3676   /// \brief Read or write access location.
3677   typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
3678   typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet;
3679
3680   /// \brief Set of potential dependent memory accesses.
3681   typedef EquivalenceClasses<MemAccessInfo> DepCandidates;
3682
3683   AccessAnalysis(const DataLayout *Dl, DepCandidates &DA) :
3684     DL(Dl), DepCands(DA), AreAllWritesIdentified(true),
3685     AreAllReadsIdentified(true), IsRTCheckNeeded(false) {}
3686
3687   /// \brief Register a load  and whether it is only read from.
3688   void addLoad(Value *Ptr, bool IsReadOnly) {
3689     Accesses.insert(MemAccessInfo(Ptr, false));
3690     if (IsReadOnly)
3691       ReadOnlyPtr.insert(Ptr);
3692   }
3693
3694   /// \brief Register a store.
3695   void addStore(Value *Ptr) {
3696     Accesses.insert(MemAccessInfo(Ptr, true));
3697   }
3698
3699   /// \brief Check whether we can check the pointers at runtime for
3700   /// non-intersection.
3701   bool canCheckPtrAtRT(LoopVectorizationLegality::RuntimePointerCheck &RtCheck,
3702                        unsigned &NumComparisons, ScalarEvolution *SE,
3703                        Loop *TheLoop, ValueToValueMap &Strides,
3704                        bool ShouldCheckStride = false);
3705
3706   /// \brief Goes over all memory accesses, checks whether a RT check is needed
3707   /// and builds sets of dependent accesses.
3708   void buildDependenceSets() {
3709     // Process read-write pointers first.
3710     processMemAccesses(false);
3711     // Next, process read pointers.
3712     processMemAccesses(true);
3713   }
3714
3715   bool isRTCheckNeeded() { return IsRTCheckNeeded; }
3716
3717   bool isDependencyCheckNeeded() { return !CheckDeps.empty(); }
3718   void resetDepChecks() { CheckDeps.clear(); }
3719
3720   MemAccessInfoSet &getDependenciesToCheck() { return CheckDeps; }
3721
3722 private:
3723   typedef SetVector<MemAccessInfo> PtrAccessSet;
3724   typedef DenseMap<Value*, MemAccessInfo> UnderlyingObjToAccessMap;
3725
3726   /// \brief Go over all memory access or only the deferred ones if
3727   /// \p UseDeferred is true and check whether runtime pointer checks are needed
3728   /// and build sets of dependency check candidates.
3729   void processMemAccesses(bool UseDeferred);
3730
3731   /// Set of all accesses.
3732   PtrAccessSet Accesses;
3733
3734   /// Set of access to check after all writes have been processed.
3735   PtrAccessSet DeferredAccesses;
3736
3737   /// Map of pointers to last access encountered.
3738   UnderlyingObjToAccessMap ObjToLastAccess;
3739
3740   /// Set of accesses that need a further dependence check.
3741   MemAccessInfoSet CheckDeps;
3742
3743   /// Set of pointers that are read only.
3744   SmallPtrSet<Value*, 16> ReadOnlyPtr;
3745
3746   /// Set of underlying objects already written to.
3747   SmallPtrSet<Value*, 16> WriteObjects;
3748
3749   const DataLayout *DL;
3750
3751   /// Sets of potentially dependent accesses - members of one set share an
3752   /// underlying pointer. The set "CheckDeps" identfies which sets really need a
3753   /// dependence check.
3754   DepCandidates &DepCands;
3755
3756   bool AreAllWritesIdentified;
3757   bool AreAllReadsIdentified;
3758   bool IsRTCheckNeeded;
3759 };
3760
3761 } // end anonymous namespace
3762
3763 /// \brief Check whether a pointer can participate in a runtime bounds check.
3764 static bool hasComputableBounds(ScalarEvolution *SE, ValueToValueMap &Strides,
3765                                 Value *Ptr) {
3766   const SCEV *PtrScev = replaceSymbolicStrideSCEV(SE, Strides, Ptr);
3767   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
3768   if (!AR)
3769     return false;
3770
3771   return AR->isAffine();
3772 }
3773
3774 /// \brief Check the stride of the pointer and ensure that it does not wrap in
3775 /// the address space.
3776 static int isStridedPtr(ScalarEvolution *SE, const DataLayout *DL, Value *Ptr,
3777                         const Loop *Lp, ValueToValueMap &StridesMap);
3778
3779 bool AccessAnalysis::canCheckPtrAtRT(
3780     LoopVectorizationLegality::RuntimePointerCheck &RtCheck,
3781     unsigned &NumComparisons, ScalarEvolution *SE, Loop *TheLoop,
3782     ValueToValueMap &StridesMap, bool ShouldCheckStride) {
3783   // Find pointers with computable bounds. We are going to use this information
3784   // to place a runtime bound check.
3785   unsigned NumReadPtrChecks = 0;
3786   unsigned NumWritePtrChecks = 0;
3787   bool CanDoRT = true;
3788
3789   bool IsDepCheckNeeded = isDependencyCheckNeeded();
3790   // We assign consecutive id to access from different dependence sets.
3791   // Accesses within the same set don't need a runtime check.
3792   unsigned RunningDepId = 1;
3793   DenseMap<Value *, unsigned> DepSetId;
3794
3795   for (PtrAccessSet::iterator AI = Accesses.begin(), AE = Accesses.end();
3796        AI != AE; ++AI) {
3797     const MemAccessInfo &Access = *AI;
3798     Value *Ptr = Access.getPointer();
3799     bool IsWrite = Access.getInt();
3800
3801     // Just add write checks if we have both.
3802     if (!IsWrite && Accesses.count(MemAccessInfo(Ptr, true)))
3803       continue;
3804
3805     if (IsWrite)
3806       ++NumWritePtrChecks;
3807     else
3808       ++NumReadPtrChecks;
3809
3810     if (hasComputableBounds(SE, StridesMap, Ptr) &&
3811         // When we run after a failing dependency check we have to make sure we
3812         // don't have wrapping pointers.
3813         (!ShouldCheckStride ||
3814          isStridedPtr(SE, DL, Ptr, TheLoop, StridesMap) == 1)) {
3815       // The id of the dependence set.
3816       unsigned DepId;
3817
3818       if (IsDepCheckNeeded) {
3819         Value *Leader = DepCands.getLeaderValue(Access).getPointer();
3820         unsigned &LeaderId = DepSetId[Leader];
3821         if (!LeaderId)
3822           LeaderId = RunningDepId++;
3823         DepId = LeaderId;
3824       } else
3825         // Each access has its own dependence set.
3826         DepId = RunningDepId++;
3827
3828       RtCheck.insert(SE, TheLoop, Ptr, IsWrite, DepId, StridesMap);
3829
3830       DEBUG(dbgs() << "LV: Found a runtime check ptr:" << *Ptr << '\n');
3831     } else {
3832       CanDoRT = false;
3833     }
3834   }
3835
3836   if (IsDepCheckNeeded && CanDoRT && RunningDepId == 2)
3837     NumComparisons = 0; // Only one dependence set.
3838   else {
3839     NumComparisons = (NumWritePtrChecks * (NumReadPtrChecks +
3840                                            NumWritePtrChecks - 1));
3841   }
3842
3843   // If the pointers that we would use for the bounds comparison have different
3844   // address spaces, assume the values aren't directly comparable, so we can't
3845   // use them for the runtime check. We also have to assume they could
3846   // overlap. In the future there should be metadata for whether address spaces
3847   // are disjoint.
3848   unsigned NumPointers = RtCheck.Pointers.size();
3849   for (unsigned i = 0; i < NumPointers; ++i) {
3850     for (unsigned j = i + 1; j < NumPointers; ++j) {
3851       // Only need to check pointers between two different dependency sets.
3852       if (RtCheck.DependencySetId[i] == RtCheck.DependencySetId[j])
3853        continue;
3854
3855       Value *PtrI = RtCheck.Pointers[i];
3856       Value *PtrJ = RtCheck.Pointers[j];
3857
3858       unsigned ASi = PtrI->getType()->getPointerAddressSpace();
3859       unsigned ASj = PtrJ->getType()->getPointerAddressSpace();
3860       if (ASi != ASj) {
3861         DEBUG(dbgs() << "LV: Runtime check would require comparison between"
3862                        " different address spaces\n");
3863         return false;
3864       }
3865     }
3866   }
3867
3868   return CanDoRT;
3869 }
3870
3871 static bool isFunctionScopeIdentifiedObject(Value *Ptr) {
3872   return isNoAliasArgument(Ptr) || isNoAliasCall(Ptr) || isa<AllocaInst>(Ptr);
3873 }
3874
3875 void AccessAnalysis::processMemAccesses(bool UseDeferred) {
3876   // We process the set twice: first we process read-write pointers, last we
3877   // process read-only pointers. This allows us to skip dependence tests for
3878   // read-only pointers.
3879
3880   PtrAccessSet &S = UseDeferred ? DeferredAccesses : Accesses;
3881   for (PtrAccessSet::iterator AI = S.begin(), AE = S.end(); AI != AE; ++AI) {
3882     const MemAccessInfo &Access = *AI;
3883     Value *Ptr = Access.getPointer();
3884     bool IsWrite = Access.getInt();
3885
3886     DepCands.insert(Access);
3887
3888     // Memorize read-only pointers for later processing and skip them in the
3889     // first round (they need to be checked after we have seen all write
3890     // pointers). Note: we also mark pointer that are not consecutive as
3891     // "read-only" pointers (so that we check "a[b[i]] +="). Hence, we need the
3892     // second check for "!IsWrite".
3893     bool IsReadOnlyPtr = ReadOnlyPtr.count(Ptr) && !IsWrite;
3894     if (!UseDeferred && IsReadOnlyPtr) {
3895       DeferredAccesses.insert(Access);
3896       continue;
3897     }
3898
3899     bool NeedDepCheck = false;
3900     // Check whether there is the possibility of dependency because of
3901     // underlying objects being the same.
3902     typedef SmallVector<Value*, 16> ValueVector;
3903     ValueVector TempObjects;
3904     GetUnderlyingObjects(Ptr, TempObjects, DL);
3905     for (ValueVector::iterator UI = TempObjects.begin(), UE = TempObjects.end();
3906          UI != UE; ++UI) {
3907       Value *UnderlyingObj = *UI;
3908
3909       // If this is a write then it needs to be an identified object.  If this a
3910       // read and all writes (so far) are identified function scope objects we
3911       // don't need an identified underlying object but only an Argument (the
3912       // next write is going to invalidate this assumption if it is
3913       // unidentified).
3914       // This is a micro-optimization for the case where all writes are
3915       // identified and we have one argument pointer.
3916       // Otherwise, we do need a runtime check.
3917       if ((IsWrite && !isFunctionScopeIdentifiedObject(UnderlyingObj)) ||
3918           (!IsWrite && (!AreAllWritesIdentified ||
3919                         !isa<Argument>(UnderlyingObj)) &&
3920            !isIdentifiedObject(UnderlyingObj))) {
3921         DEBUG(dbgs() << "LV: Found an unidentified " <<
3922               (IsWrite ?  "write" : "read" ) << " ptr: " << *UnderlyingObj <<
3923               "\n");
3924         IsRTCheckNeeded = (IsRTCheckNeeded ||
3925                            !isIdentifiedObject(UnderlyingObj) ||
3926                            !AreAllReadsIdentified);
3927
3928         if (IsWrite)
3929           AreAllWritesIdentified = false;
3930         if (!IsWrite)
3931           AreAllReadsIdentified = false;
3932       }
3933
3934       // If this is a write - check other reads and writes for conflicts.  If
3935       // this is a read only check other writes for conflicts (but only if there
3936       // is no other write to the ptr - this is an optimization to catch "a[i] =
3937       // a[i] + " without having to do a dependence check).
3938       if ((IsWrite || IsReadOnlyPtr) && WriteObjects.count(UnderlyingObj))
3939         NeedDepCheck = true;
3940
3941       if (IsWrite)
3942         WriteObjects.insert(UnderlyingObj);
3943
3944       // Create sets of pointers connected by shared underlying objects.
3945       UnderlyingObjToAccessMap::iterator Prev =
3946         ObjToLastAccess.find(UnderlyingObj);
3947       if (Prev != ObjToLastAccess.end())
3948         DepCands.unionSets(Access, Prev->second);
3949
3950       ObjToLastAccess[UnderlyingObj] = Access;
3951     }
3952
3953     if (NeedDepCheck)
3954       CheckDeps.insert(Access);
3955   }
3956 }
3957
3958 namespace {
3959 /// \brief Checks memory dependences among accesses to the same underlying
3960 /// object to determine whether there vectorization is legal or not (and at
3961 /// which vectorization factor).
3962 ///
3963 /// This class works under the assumption that we already checked that memory
3964 /// locations with different underlying pointers are "must-not alias".
3965 /// We use the ScalarEvolution framework to symbolically evalutate access
3966 /// functions pairs. Since we currently don't restructure the loop we can rely
3967 /// on the program order of memory accesses to determine their safety.
3968 /// At the moment we will only deem accesses as safe for:
3969 ///  * A negative constant distance assuming program order.
3970 ///
3971 ///      Safe: tmp = a[i + 1];     OR     a[i + 1] = x;
3972 ///            a[i] = tmp;                y = a[i];
3973 ///
3974 ///   The latter case is safe because later checks guarantuee that there can't
3975 ///   be a cycle through a phi node (that is, we check that "x" and "y" is not
3976 ///   the same variable: a header phi can only be an induction or a reduction, a
3977 ///   reduction can't have a memory sink, an induction can't have a memory
3978 ///   source). This is important and must not be violated (or we have to
3979 ///   resort to checking for cycles through memory).
3980 ///
3981 ///  * A positive constant distance assuming program order that is bigger
3982 ///    than the biggest memory access.
3983 ///
3984 ///     tmp = a[i]        OR              b[i] = x
3985 ///     a[i+2] = tmp                      y = b[i+2];
3986 ///
3987 ///     Safe distance: 2 x sizeof(a[0]), and 2 x sizeof(b[0]), respectively.
3988 ///
3989 ///  * Zero distances and all accesses have the same size.
3990 ///
3991 class MemoryDepChecker {
3992 public:
3993   typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
3994   typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet;
3995
3996   MemoryDepChecker(ScalarEvolution *Se, const DataLayout *Dl, const Loop *L)
3997       : SE(Se), DL(Dl), InnermostLoop(L), AccessIdx(0),
3998         ShouldRetryWithRuntimeCheck(false) {}
3999
4000   /// \brief Register the location (instructions are given increasing numbers)
4001   /// of a write access.
4002   void addAccess(StoreInst *SI) {
4003     Value *Ptr = SI->getPointerOperand();
4004     Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx);
4005     InstMap.push_back(SI);
4006     ++AccessIdx;
4007   }
4008
4009   /// \brief Register the location (instructions are given increasing numbers)
4010   /// of a write access.
4011   void addAccess(LoadInst *LI) {
4012     Value *Ptr = LI->getPointerOperand();
4013     Accesses[MemAccessInfo(Ptr, false)].push_back(AccessIdx);
4014     InstMap.push_back(LI);
4015     ++AccessIdx;
4016   }
4017
4018   /// \brief Check whether the dependencies between the accesses are safe.
4019   ///
4020   /// Only checks sets with elements in \p CheckDeps.
4021   bool areDepsSafe(AccessAnalysis::DepCandidates &AccessSets,
4022                    MemAccessInfoSet &CheckDeps, ValueToValueMap &Strides);
4023
4024   /// \brief The maximum number of bytes of a vector register we can vectorize
4025   /// the accesses safely with.
4026   unsigned getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; }
4027
4028   /// \brief In same cases when the dependency check fails we can still
4029   /// vectorize the loop with a dynamic array access check.
4030   bool shouldRetryWithRuntimeCheck() { return ShouldRetryWithRuntimeCheck; }
4031
4032 private:
4033   ScalarEvolution *SE;
4034   const DataLayout *DL;
4035   const Loop *InnermostLoop;
4036
4037   /// \brief Maps access locations (ptr, read/write) to program order.
4038   DenseMap<MemAccessInfo, std::vector<unsigned> > Accesses;
4039
4040   /// \brief Memory access instructions in program order.
4041   SmallVector<Instruction *, 16> InstMap;
4042
4043   /// \brief The program order index to be used for the next instruction.
4044   unsigned AccessIdx;
4045
4046   // We can access this many bytes in parallel safely.
4047   unsigned MaxSafeDepDistBytes;
4048
4049   /// \brief If we see a non-constant dependence distance we can still try to
4050   /// vectorize this loop with runtime checks.
4051   bool ShouldRetryWithRuntimeCheck;
4052
4053   /// \brief Check whether there is a plausible dependence between the two
4054   /// accesses.
4055   ///
4056   /// Access \p A must happen before \p B in program order. The two indices
4057   /// identify the index into the program order map.
4058   ///
4059   /// This function checks  whether there is a plausible dependence (or the
4060   /// absence of such can't be proved) between the two accesses. If there is a
4061   /// plausible dependence but the dependence distance is bigger than one
4062   /// element access it records this distance in \p MaxSafeDepDistBytes (if this
4063   /// distance is smaller than any other distance encountered so far).
4064   /// Otherwise, this function returns true signaling a possible dependence.
4065   bool isDependent(const MemAccessInfo &A, unsigned AIdx,
4066                    const MemAccessInfo &B, unsigned BIdx,
4067                    ValueToValueMap &Strides);
4068
4069   /// \brief Check whether the data dependence could prevent store-load
4070   /// forwarding.
4071   bool couldPreventStoreLoadForward(unsigned Distance, unsigned TypeByteSize);
4072 };
4073
4074 } // end anonymous namespace
4075
4076 static bool isInBoundsGep(Value *Ptr) {
4077   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr))
4078     return GEP->isInBounds();
4079   return false;
4080 }
4081
4082 /// \brief Check whether the access through \p Ptr has a constant stride.
4083 static int isStridedPtr(ScalarEvolution *SE, const DataLayout *DL, Value *Ptr,
4084                         const Loop *Lp, ValueToValueMap &StridesMap) {
4085   const Type *Ty = Ptr->getType();
4086   assert(Ty->isPointerTy() && "Unexpected non-ptr");
4087
4088   // Make sure that the pointer does not point to aggregate types.
4089   const PointerType *PtrTy = cast<PointerType>(Ty);
4090   if (PtrTy->getElementType()->isAggregateType()) {
4091     DEBUG(dbgs() << "LV: Bad stride - Not a pointer to a scalar type" << *Ptr <<
4092           "\n");
4093     return 0;
4094   }
4095
4096   const SCEV *PtrScev = replaceSymbolicStrideSCEV(SE, StridesMap, Ptr);
4097
4098   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
4099   if (!AR) {
4100     DEBUG(dbgs() << "LV: Bad stride - Not an AddRecExpr pointer "
4101           << *Ptr << " SCEV: " << *PtrScev << "\n");
4102     return 0;
4103   }
4104
4105   // The accesss function must stride over the innermost loop.
4106   if (Lp != AR->getLoop()) {
4107     DEBUG(dbgs() << "LV: Bad stride - Not striding over innermost loop " <<
4108           *Ptr << " SCEV: " << *PtrScev << "\n");
4109   }
4110
4111   // The address calculation must not wrap. Otherwise, a dependence could be
4112   // inverted.
4113   // An inbounds getelementptr that is a AddRec with a unit stride
4114   // cannot wrap per definition. The unit stride requirement is checked later.
4115   // An getelementptr without an inbounds attribute and unit stride would have
4116   // to access the pointer value "0" which is undefined behavior in address
4117   // space 0, therefore we can also vectorize this case.
4118   bool IsInBoundsGEP = isInBoundsGep(Ptr);
4119   bool IsNoWrapAddRec = AR->getNoWrapFlags(SCEV::NoWrapMask);
4120   bool IsInAddressSpaceZero = PtrTy->getAddressSpace() == 0;
4121   if (!IsNoWrapAddRec && !IsInBoundsGEP && !IsInAddressSpaceZero) {
4122     DEBUG(dbgs() << "LV: Bad stride - Pointer may wrap in the address space "
4123           << *Ptr << " SCEV: " << *PtrScev << "\n");
4124     return 0;
4125   }
4126
4127   // Check the step is constant.
4128   const SCEV *Step = AR->getStepRecurrence(*SE);
4129
4130   // Calculate the pointer stride and check if it is consecutive.
4131   const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
4132   if (!C) {
4133     DEBUG(dbgs() << "LV: Bad stride - Not a constant strided " << *Ptr <<
4134           " SCEV: " << *PtrScev << "\n");
4135     return 0;
4136   }
4137
4138   int64_t Size = DL->getTypeAllocSize(PtrTy->getElementType());
4139   const APInt &APStepVal = C->getValue()->getValue();
4140
4141   // Huge step value - give up.
4142   if (APStepVal.getBitWidth() > 64)
4143     return 0;
4144
4145   int64_t StepVal = APStepVal.getSExtValue();
4146
4147   // Strided access.
4148   int64_t Stride = StepVal / Size;
4149   int64_t Rem = StepVal % Size;
4150   if (Rem)
4151     return 0;
4152
4153   // If the SCEV could wrap but we have an inbounds gep with a unit stride we
4154   // know we can't "wrap around the address space". In case of address space
4155   // zero we know that this won't happen without triggering undefined behavior.
4156   if (!IsNoWrapAddRec && (IsInBoundsGEP || IsInAddressSpaceZero) &&
4157       Stride != 1 && Stride != -1)
4158     return 0;
4159
4160   return Stride;
4161 }
4162
4163 bool MemoryDepChecker::couldPreventStoreLoadForward(unsigned Distance,
4164                                                     unsigned TypeByteSize) {
4165   // If loads occur at a distance that is not a multiple of a feasible vector
4166   // factor store-load forwarding does not take place.
4167   // Positive dependences might cause troubles because vectorizing them might
4168   // prevent store-load forwarding making vectorized code run a lot slower.
4169   //   a[i] = a[i-3] ^ a[i-8];
4170   //   The stores to a[i:i+1] don't align with the stores to a[i-3:i-2] and
4171   //   hence on your typical architecture store-load forwarding does not take
4172   //   place. Vectorizing in such cases does not make sense.
4173   // Store-load forwarding distance.
4174   const unsigned NumCyclesForStoreLoadThroughMemory = 8*TypeByteSize;
4175   // Maximum vector factor.
4176   unsigned MaxVFWithoutSLForwardIssues = MaxVectorWidth*TypeByteSize;
4177   if(MaxSafeDepDistBytes < MaxVFWithoutSLForwardIssues)
4178     MaxVFWithoutSLForwardIssues = MaxSafeDepDistBytes;
4179
4180   for (unsigned vf = 2*TypeByteSize; vf <= MaxVFWithoutSLForwardIssues;
4181        vf *= 2) {
4182     if (Distance % vf && Distance / vf < NumCyclesForStoreLoadThroughMemory) {
4183       MaxVFWithoutSLForwardIssues = (vf >>=1);
4184       break;
4185     }
4186   }
4187
4188   if (MaxVFWithoutSLForwardIssues< 2*TypeByteSize) {
4189     DEBUG(dbgs() << "LV: Distance " << Distance <<
4190           " that could cause a store-load forwarding conflict\n");
4191     return true;
4192   }
4193
4194   if (MaxVFWithoutSLForwardIssues < MaxSafeDepDistBytes &&
4195       MaxVFWithoutSLForwardIssues != MaxVectorWidth*TypeByteSize)
4196     MaxSafeDepDistBytes = MaxVFWithoutSLForwardIssues;
4197   return false;
4198 }
4199
4200 bool MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
4201                                    const MemAccessInfo &B, unsigned BIdx,
4202                                    ValueToValueMap &Strides) {
4203   assert (AIdx < BIdx && "Must pass arguments in program order");
4204
4205   Value *APtr = A.getPointer();
4206   Value *BPtr = B.getPointer();
4207   bool AIsWrite = A.getInt();
4208   bool BIsWrite = B.getInt();
4209
4210   // Two reads are independent.
4211   if (!AIsWrite && !BIsWrite)
4212     return false;
4213
4214   const SCEV *AScev = replaceSymbolicStrideSCEV(SE, Strides, APtr);
4215   const SCEV *BScev = replaceSymbolicStrideSCEV(SE, Strides, BPtr);
4216
4217   int StrideAPtr = isStridedPtr(SE, DL, APtr, InnermostLoop, Strides);
4218   int StrideBPtr = isStridedPtr(SE, DL, BPtr, InnermostLoop, Strides);
4219
4220   const SCEV *Src = AScev;
4221   const SCEV *Sink = BScev;
4222
4223   // If the induction step is negative we have to invert source and sink of the
4224   // dependence.
4225   if (StrideAPtr < 0) {
4226     //Src = BScev;
4227     //Sink = AScev;
4228     std::swap(APtr, BPtr);
4229     std::swap(Src, Sink);
4230     std::swap(AIsWrite, BIsWrite);
4231     std::swap(AIdx, BIdx);
4232     std::swap(StrideAPtr, StrideBPtr);
4233   }
4234
4235   const SCEV *Dist = SE->getMinusSCEV(Sink, Src);
4236
4237   DEBUG(dbgs() << "LV: Src Scev: " << *Src << "Sink Scev: " << *Sink
4238         << "(Induction step: " << StrideAPtr <<  ")\n");
4239   DEBUG(dbgs() << "LV: Distance for " << *InstMap[AIdx] << " to "
4240         << *InstMap[BIdx] << ": " << *Dist << "\n");
4241
4242   // Need consecutive accesses. We don't want to vectorize
4243   // "A[B[i]] += ..." and similar code or pointer arithmetic that could wrap in
4244   // the address space.
4245   if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr){
4246     DEBUG(dbgs() << "Non-consecutive pointer access\n");
4247     return true;
4248   }
4249
4250   const SCEVConstant *C = dyn_cast<SCEVConstant>(Dist);
4251   if (!C) {
4252     DEBUG(dbgs() << "LV: Dependence because of non-constant distance\n");
4253     ShouldRetryWithRuntimeCheck = true;
4254     return true;
4255   }
4256
4257   Type *ATy = APtr->getType()->getPointerElementType();
4258   Type *BTy = BPtr->getType()->getPointerElementType();
4259   unsigned TypeByteSize = DL->getTypeAllocSize(ATy);
4260
4261   // Negative distances are not plausible dependencies.
4262   const APInt &Val = C->getValue()->getValue();
4263   if (Val.isNegative()) {
4264     bool IsTrueDataDependence = (AIsWrite && !BIsWrite);
4265     if (IsTrueDataDependence &&
4266         (couldPreventStoreLoadForward(Val.abs().getZExtValue(), TypeByteSize) ||
4267          ATy != BTy))
4268       return true;
4269
4270     DEBUG(dbgs() << "LV: Dependence is negative: NoDep\n");
4271     return false;
4272   }
4273
4274   // Write to the same location with the same size.
4275   // Could be improved to assert type sizes are the same (i32 == float, etc).
4276   if (Val == 0) {
4277     if (ATy == BTy)
4278       return false;
4279     DEBUG(dbgs() << "LV: Zero dependence difference but different types\n");
4280     return true;
4281   }
4282
4283   assert(Val.isStrictlyPositive() && "Expect a positive value");
4284
4285   // Positive distance bigger than max vectorization factor.
4286   if (ATy != BTy) {
4287     DEBUG(dbgs() <<
4288           "LV: ReadWrite-Write positive dependency with different types\n");
4289     return false;
4290   }
4291
4292   unsigned Distance = (unsigned) Val.getZExtValue();
4293
4294   // Bail out early if passed-in parameters make vectorization not feasible.
4295   unsigned ForcedFactor = VectorizationFactor ? VectorizationFactor : 1;
4296   unsigned ForcedUnroll = VectorizationUnroll ? VectorizationUnroll : 1;
4297
4298   // The distance must be bigger than the size needed for a vectorized version
4299   // of the operation and the size of the vectorized operation must not be
4300   // bigger than the currrent maximum size.
4301   if (Distance < 2*TypeByteSize ||
4302       2*TypeByteSize > MaxSafeDepDistBytes ||
4303       Distance < TypeByteSize * ForcedUnroll * ForcedFactor) {
4304     DEBUG(dbgs() << "LV: Failure because of Positive distance "
4305         << Val.getSExtValue() << '\n');
4306     return true;
4307   }
4308
4309   MaxSafeDepDistBytes = Distance < MaxSafeDepDistBytes ?
4310     Distance : MaxSafeDepDistBytes;
4311
4312   bool IsTrueDataDependence = (!AIsWrite && BIsWrite);
4313   if (IsTrueDataDependence &&
4314       couldPreventStoreLoadForward(Distance, TypeByteSize))
4315      return true;
4316
4317   DEBUG(dbgs() << "LV: Positive distance " << Val.getSExtValue() <<
4318         " with max VF = " << MaxSafeDepDistBytes / TypeByteSize << '\n');
4319
4320   return false;
4321 }
4322
4323 bool MemoryDepChecker::areDepsSafe(AccessAnalysis::DepCandidates &AccessSets,
4324                                    MemAccessInfoSet &CheckDeps,
4325                                    ValueToValueMap &Strides) {
4326
4327   MaxSafeDepDistBytes = -1U;
4328   while (!CheckDeps.empty()) {
4329     MemAccessInfo CurAccess = *CheckDeps.begin();
4330
4331     // Get the relevant memory access set.
4332     EquivalenceClasses<MemAccessInfo>::iterator I =
4333       AccessSets.findValue(AccessSets.getLeaderValue(CurAccess));
4334
4335     // Check accesses within this set.
4336     EquivalenceClasses<MemAccessInfo>::member_iterator AI, AE;
4337     AI = AccessSets.member_begin(I), AE = AccessSets.member_end();
4338
4339     // Check every access pair.
4340     while (AI != AE) {
4341       CheckDeps.erase(*AI);
4342       EquivalenceClasses<MemAccessInfo>::member_iterator OI = std::next(AI);
4343       while (OI != AE) {
4344         // Check every accessing instruction pair in program order.
4345         for (std::vector<unsigned>::iterator I1 = Accesses[*AI].begin(),
4346              I1E = Accesses[*AI].end(); I1 != I1E; ++I1)
4347           for (std::vector<unsigned>::iterator I2 = Accesses[*OI].begin(),
4348                I2E = Accesses[*OI].end(); I2 != I2E; ++I2) {
4349             if (*I1 < *I2 && isDependent(*AI, *I1, *OI, *I2, Strides))
4350               return false;
4351             if (*I2 < *I1 && isDependent(*OI, *I2, *AI, *I1, Strides))
4352               return false;
4353           }
4354         ++OI;
4355       }
4356       AI++;
4357     }
4358   }
4359   return true;
4360 }
4361
4362 bool LoopVectorizationLegality::canVectorizeMemory() {
4363
4364   typedef SmallVector<Value*, 16> ValueVector;
4365   typedef SmallPtrSet<Value*, 16> ValueSet;
4366
4367   // Holds the Load and Store *instructions*.
4368   ValueVector Loads;
4369   ValueVector Stores;
4370
4371   // Holds all the different accesses in the loop.
4372   unsigned NumReads = 0;
4373   unsigned NumReadWrites = 0;
4374
4375   PtrRtCheck.Pointers.clear();
4376   PtrRtCheck.Need = false;
4377
4378   const bool IsAnnotatedParallel = TheLoop->isAnnotatedParallel();
4379   MemoryDepChecker DepChecker(SE, DL, TheLoop);
4380
4381   // For each block.
4382   for (Loop::block_iterator bb = TheLoop->block_begin(),
4383        be = TheLoop->block_end(); bb != be; ++bb) {
4384
4385     // Scan the BB and collect legal loads and stores.
4386     for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
4387          ++it) {
4388
4389       // If this is a load, save it. If this instruction can read from memory
4390       // but is not a load, then we quit. Notice that we don't handle function
4391       // calls that read or write.
4392       if (it->mayReadFromMemory()) {
4393         // Many math library functions read the rounding mode. We will only
4394         // vectorize a loop if it contains known function calls that don't set
4395         // the flag. Therefore, it is safe to ignore this read from memory.
4396         CallInst *Call = dyn_cast<CallInst>(it);
4397         if (Call && getIntrinsicIDForCall(Call, TLI))
4398           continue;
4399
4400         LoadInst *Ld = dyn_cast<LoadInst>(it);
4401         if (!Ld) return false;
4402         if (!Ld->isSimple() && !IsAnnotatedParallel) {
4403           DEBUG(dbgs() << "LV: Found a non-simple load.\n");
4404           return false;
4405         }
4406         NumLoads++;
4407         Loads.push_back(Ld);
4408         DepChecker.addAccess(Ld);
4409         continue;
4410       }
4411
4412       // Save 'store' instructions. Abort if other instructions write to memory.
4413       if (it->mayWriteToMemory()) {
4414         StoreInst *St = dyn_cast<StoreInst>(it);
4415         if (!St) return false;
4416         if (!St->isSimple() && !IsAnnotatedParallel) {
4417           DEBUG(dbgs() << "LV: Found a non-simple store.\n");
4418           return false;
4419         }
4420         NumStores++;
4421         Stores.push_back(St);
4422         DepChecker.addAccess(St);
4423       }
4424     } // Next instr.
4425   } // Next block.
4426
4427   // Now we have two lists that hold the loads and the stores.
4428   // Next, we find the pointers that they use.
4429
4430   // Check if we see any stores. If there are no stores, then we don't
4431   // care if the pointers are *restrict*.
4432   if (!Stores.size()) {
4433     DEBUG(dbgs() << "LV: Found a read-only loop!\n");
4434     return true;
4435   }
4436
4437   AccessAnalysis::DepCandidates DependentAccesses;
4438   AccessAnalysis Accesses(DL, DependentAccesses);
4439
4440   // Holds the analyzed pointers. We don't want to call GetUnderlyingObjects
4441   // multiple times on the same object. If the ptr is accessed twice, once
4442   // for read and once for write, it will only appear once (on the write
4443   // list). This is okay, since we are going to check for conflicts between
4444   // writes and between reads and writes, but not between reads and reads.
4445   ValueSet Seen;
4446
4447   ValueVector::iterator I, IE;
4448   for (I = Stores.begin(), IE = Stores.end(); I != IE; ++I) {
4449     StoreInst *ST = cast<StoreInst>(*I);
4450     Value* Ptr = ST->getPointerOperand();
4451
4452     if (isUniform(Ptr)) {
4453       DEBUG(dbgs() << "LV: We don't allow storing to uniform addresses\n");
4454       return false;
4455     }
4456
4457     // If we did *not* see this pointer before, insert it to  the read-write
4458     // list. At this phase it is only a 'write' list.
4459     if (Seen.insert(Ptr)) {
4460       ++NumReadWrites;
4461       Accesses.addStore(Ptr);
4462     }
4463   }
4464
4465   if (IsAnnotatedParallel) {
4466     DEBUG(dbgs()
4467           << "LV: A loop annotated parallel, ignore memory dependency "
4468           << "checks.\n");
4469     return true;
4470   }
4471
4472   for (I = Loads.begin(), IE = Loads.end(); I != IE; ++I) {
4473     LoadInst *LD = cast<LoadInst>(*I);
4474     Value* Ptr = LD->getPointerOperand();
4475     // If we did *not* see this pointer before, insert it to the
4476     // read list. If we *did* see it before, then it is already in
4477     // the read-write list. This allows us to vectorize expressions
4478     // such as A[i] += x;  Because the address of A[i] is a read-write
4479     // pointer. This only works if the index of A[i] is consecutive.
4480     // If the address of i is unknown (for example A[B[i]]) then we may
4481     // read a few words, modify, and write a few words, and some of the
4482     // words may be written to the same address.
4483     bool IsReadOnlyPtr = false;
4484     if (Seen.insert(Ptr) || !isStridedPtr(SE, DL, Ptr, TheLoop, Strides)) {
4485       ++NumReads;
4486       IsReadOnlyPtr = true;
4487     }
4488     Accesses.addLoad(Ptr, IsReadOnlyPtr);
4489   }
4490
4491   // If we write (or read-write) to a single destination and there are no
4492   // other reads in this loop then is it safe to vectorize.
4493   if (NumReadWrites == 1 && NumReads == 0) {
4494     DEBUG(dbgs() << "LV: Found a write-only loop!\n");
4495     return true;
4496   }
4497
4498   // Build dependence sets and check whether we need a runtime pointer bounds
4499   // check.
4500   Accesses.buildDependenceSets();
4501   bool NeedRTCheck = Accesses.isRTCheckNeeded();
4502
4503   // Find pointers with computable bounds. We are going to use this information
4504   // to place a runtime bound check.
4505   unsigned NumComparisons = 0;
4506   bool CanDoRT = false;
4507   if (NeedRTCheck)
4508     CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NumComparisons, SE, TheLoop,
4509                                        Strides);
4510
4511   DEBUG(dbgs() << "LV: We need to do " << NumComparisons <<
4512         " pointer comparisons.\n");
4513
4514   // If we only have one set of dependences to check pointers among we don't
4515   // need a runtime check.
4516   if (NumComparisons == 0 && NeedRTCheck)
4517     NeedRTCheck = false;
4518
4519   // Check that we did not collect too many pointers or found an unsizeable
4520   // pointer.
4521   if (!CanDoRT || NumComparisons > RuntimeMemoryCheckThreshold) {
4522     PtrRtCheck.reset();
4523     CanDoRT = false;
4524   }
4525
4526   if (CanDoRT) {
4527     DEBUG(dbgs() << "LV: We can perform a memory runtime check if needed.\n");
4528   }
4529
4530   if (NeedRTCheck && !CanDoRT) {
4531     DEBUG(dbgs() << "LV: We can't vectorize because we can't find " <<
4532           "the array bounds.\n");
4533     PtrRtCheck.reset();
4534     return false;
4535   }
4536
4537   PtrRtCheck.Need = NeedRTCheck;
4538
4539   bool CanVecMem = true;
4540   if (Accesses.isDependencyCheckNeeded()) {
4541     DEBUG(dbgs() << "LV: Checking memory dependencies\n");
4542     CanVecMem = DepChecker.areDepsSafe(
4543         DependentAccesses, Accesses.getDependenciesToCheck(), Strides);
4544     MaxSafeDepDistBytes = DepChecker.getMaxSafeDepDistBytes();
4545
4546     if (!CanVecMem && DepChecker.shouldRetryWithRuntimeCheck()) {
4547       DEBUG(dbgs() << "LV: Retrying with memory checks\n");
4548       NeedRTCheck = true;
4549
4550       // Clear the dependency checks. We assume they are not needed.
4551       Accesses.resetDepChecks();
4552
4553       PtrRtCheck.reset();
4554       PtrRtCheck.Need = true;
4555
4556       CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NumComparisons, SE,
4557                                          TheLoop, Strides, true);
4558       // Check that we did not collect too many pointers or found an unsizeable
4559       // pointer.
4560       if (!CanDoRT || NumComparisons > RuntimeMemoryCheckThreshold) {
4561         DEBUG(dbgs() << "LV: Can't vectorize with memory checks\n");
4562         PtrRtCheck.reset();
4563         return false;
4564       }
4565
4566       CanVecMem = true;
4567     }
4568   }
4569
4570   DEBUG(dbgs() << "LV: We" << (NeedRTCheck ? "" : " don't") <<
4571         " need a runtime memory check.\n");
4572
4573   return CanVecMem;
4574 }
4575
4576 static bool hasMultipleUsesOf(Instruction *I,
4577                               SmallPtrSet<Instruction *, 8> &Insts) {
4578   unsigned NumUses = 0;
4579   for(User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use) {
4580     if (Insts.count(dyn_cast<Instruction>(*Use)))
4581       ++NumUses;
4582     if (NumUses > 1)
4583       return true;
4584   }
4585
4586   return false;
4587 }
4588
4589 static bool areAllUsesIn(Instruction *I, SmallPtrSet<Instruction *, 8> &Set) {
4590   for(User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use)
4591     if (!Set.count(dyn_cast<Instruction>(*Use)))
4592       return false;
4593   return true;
4594 }
4595
4596 bool LoopVectorizationLegality::AddReductionVar(PHINode *Phi,
4597                                                 ReductionKind Kind) {
4598   if (Phi->getNumIncomingValues() != 2)
4599     return false;
4600
4601   // Reduction variables are only found in the loop header block.
4602   if (Phi->getParent() != TheLoop->getHeader())
4603     return false;
4604
4605   // Obtain the reduction start value from the value that comes from the loop
4606   // preheader.
4607   Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
4608
4609   // ExitInstruction is the single value which is used outside the loop.
4610   // We only allow for a single reduction value to be used outside the loop.
4611   // This includes users of the reduction, variables (which form a cycle
4612   // which ends in the phi node).
4613   Instruction *ExitInstruction = 0;
4614   // Indicates that we found a reduction operation in our scan.
4615   bool FoundReduxOp = false;
4616
4617   // We start with the PHI node and scan for all of the users of this
4618   // instruction. All users must be instructions that can be used as reduction
4619   // variables (such as ADD). We must have a single out-of-block user. The cycle
4620   // must include the original PHI.
4621   bool FoundStartPHI = false;
4622
4623   // To recognize min/max patterns formed by a icmp select sequence, we store
4624   // the number of instruction we saw from the recognized min/max pattern,
4625   //  to make sure we only see exactly the two instructions.
4626   unsigned NumCmpSelectPatternInst = 0;
4627   ReductionInstDesc ReduxDesc(false, 0);
4628
4629   SmallPtrSet<Instruction *, 8> VisitedInsts;
4630   SmallVector<Instruction *, 8> Worklist;
4631   Worklist.push_back(Phi);
4632   VisitedInsts.insert(Phi);
4633
4634   // A value in the reduction can be used:
4635   //  - By the reduction:
4636   //      - Reduction operation:
4637   //        - One use of reduction value (safe).
4638   //        - Multiple use of reduction value (not safe).
4639   //      - PHI:
4640   //        - All uses of the PHI must be the reduction (safe).
4641   //        - Otherwise, not safe.
4642   //  - By one instruction outside of the loop (safe).
4643   //  - By further instructions outside of the loop (not safe).
4644   //  - By an instruction that is not part of the reduction (not safe).
4645   //    This is either:
4646   //      * An instruction type other than PHI or the reduction operation.
4647   //      * A PHI in the header other than the initial PHI.
4648   while (!Worklist.empty()) {
4649     Instruction *Cur = Worklist.back();
4650     Worklist.pop_back();
4651
4652     // No Users.
4653     // If the instruction has no users then this is a broken chain and can't be
4654     // a reduction variable.
4655     if (Cur->use_empty())
4656       return false;
4657
4658     bool IsAPhi = isa<PHINode>(Cur);
4659
4660     // A header PHI use other than the original PHI.
4661     if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
4662       return false;
4663
4664     // Reductions of instructions such as Div, and Sub is only possible if the
4665     // LHS is the reduction variable.
4666     if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
4667         !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
4668         !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
4669       return false;
4670
4671     // Any reduction instruction must be of one of the allowed kinds.
4672     ReduxDesc = isReductionInstr(Cur, Kind, ReduxDesc);
4673     if (!ReduxDesc.IsReduction)
4674       return false;
4675
4676     // A reduction operation must only have one use of the reduction value.
4677     if (!IsAPhi && Kind != RK_IntegerMinMax && Kind != RK_FloatMinMax &&
4678         hasMultipleUsesOf(Cur, VisitedInsts))
4679       return false;
4680
4681     // All inputs to a PHI node must be a reduction value.
4682     if(IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
4683       return false;
4684
4685     if (Kind == RK_IntegerMinMax && (isa<ICmpInst>(Cur) ||
4686                                      isa<SelectInst>(Cur)))
4687       ++NumCmpSelectPatternInst;
4688     if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) ||
4689                                    isa<SelectInst>(Cur)))
4690       ++NumCmpSelectPatternInst;
4691
4692     // Check  whether we found a reduction operator.
4693     FoundReduxOp |= !IsAPhi;
4694
4695     // Process users of current instruction. Push non-PHI nodes after PHI nodes
4696     // onto the stack. This way we are going to have seen all inputs to PHI
4697     // nodes once we get to them.
4698     SmallVector<Instruction *, 8> NonPHIs;
4699     SmallVector<Instruction *, 8> PHIs;
4700     for (Value::use_iterator UI = Cur->use_begin(), E = Cur->use_end(); UI != E;
4701          ++UI) {
4702       Instruction *Usr = cast<Instruction>(*UI);
4703
4704       // Check if we found the exit user.
4705       BasicBlock *Parent = Usr->getParent();
4706       if (!TheLoop->contains(Parent)) {
4707         // Exit if you find multiple outside users or if the header phi node is
4708         // being used. In this case the user uses the value of the previous
4709         // iteration, in which case we would loose "VF-1" iterations of the
4710         // reduction operation if we vectorize.
4711         if (ExitInstruction != 0 || Cur == Phi)
4712           return false;
4713
4714         // The instruction used by an outside user must be the last instruction
4715         // before we feed back to the reduction phi. Otherwise, we loose VF-1
4716         // operations on the value.
4717         if (std::find(Phi->op_begin(), Phi->op_end(), Cur) == Phi->op_end())
4718          return false;
4719
4720         ExitInstruction = Cur;
4721         continue;
4722       }
4723
4724       // Process instructions only once (termination). Each reduction cycle
4725       // value must only be used once, except by phi nodes and min/max
4726       // reductions which are represented as a cmp followed by a select.
4727       ReductionInstDesc IgnoredVal(false, 0);
4728       if (VisitedInsts.insert(Usr)) {
4729         if (isa<PHINode>(Usr))
4730           PHIs.push_back(Usr);
4731         else
4732           NonPHIs.push_back(Usr);
4733       } else if (!isa<PHINode>(Usr) &&
4734                  ((!isa<FCmpInst>(Usr) &&
4735                    !isa<ICmpInst>(Usr) &&
4736                    !isa<SelectInst>(Usr)) ||
4737                   !isMinMaxSelectCmpPattern(Usr, IgnoredVal).IsReduction))
4738         return false;
4739
4740       // Remember that we completed the cycle.
4741       if (Usr == Phi)
4742         FoundStartPHI = true;
4743     }
4744     Worklist.append(PHIs.begin(), PHIs.end());
4745     Worklist.append(NonPHIs.begin(), NonPHIs.end());
4746   }
4747
4748   // This means we have seen one but not the other instruction of the
4749   // pattern or more than just a select and cmp.
4750   if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) &&
4751       NumCmpSelectPatternInst != 2)
4752     return false;
4753
4754   if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
4755     return false;
4756
4757   // We found a reduction var if we have reached the original phi node and we
4758   // only have a single instruction with out-of-loop users.
4759
4760   // This instruction is allowed to have out-of-loop users.
4761   AllowedExit.insert(ExitInstruction);
4762
4763   // Save the description of this reduction variable.
4764   ReductionDescriptor RD(RdxStart, ExitInstruction, Kind,
4765                          ReduxDesc.MinMaxKind);
4766   Reductions[Phi] = RD;
4767   // We've ended the cycle. This is a reduction variable if we have an
4768   // outside user and it has a binary op.
4769
4770   return true;
4771 }
4772
4773 /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
4774 /// pattern corresponding to a min(X, Y) or max(X, Y).
4775 LoopVectorizationLegality::ReductionInstDesc
4776 LoopVectorizationLegality::isMinMaxSelectCmpPattern(Instruction *I,
4777                                                     ReductionInstDesc &Prev) {
4778
4779   assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
4780          "Expect a select instruction");
4781   Instruction *Cmp = 0;
4782   SelectInst *Select = 0;
4783
4784   // We must handle the select(cmp()) as a single instruction. Advance to the
4785   // select.
4786   if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) {
4787     if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->use_begin())))
4788       return ReductionInstDesc(false, I);
4789     return ReductionInstDesc(Select, Prev.MinMaxKind);
4790   }
4791
4792   // Only handle single use cases for now.
4793   if (!(Select = dyn_cast<SelectInst>(I)))
4794     return ReductionInstDesc(false, I);
4795   if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
4796       !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
4797     return ReductionInstDesc(false, I);
4798   if (!Cmp->hasOneUse())
4799     return ReductionInstDesc(false, I);
4800
4801   Value *CmpLeft;
4802   Value *CmpRight;
4803
4804   // Look for a min/max pattern.
4805   if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
4806     return ReductionInstDesc(Select, MRK_UIntMin);
4807   else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
4808     return ReductionInstDesc(Select, MRK_UIntMax);
4809   else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
4810     return ReductionInstDesc(Select, MRK_SIntMax);
4811   else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
4812     return ReductionInstDesc(Select, MRK_SIntMin);
4813   else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
4814     return ReductionInstDesc(Select, MRK_FloatMin);
4815   else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
4816     return ReductionInstDesc(Select, MRK_FloatMax);
4817   else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
4818     return ReductionInstDesc(Select, MRK_FloatMin);
4819   else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
4820     return ReductionInstDesc(Select, MRK_FloatMax);
4821
4822   return ReductionInstDesc(false, I);
4823 }
4824
4825 LoopVectorizationLegality::ReductionInstDesc
4826 LoopVectorizationLegality::isReductionInstr(Instruction *I,
4827                                             ReductionKind Kind,
4828                                             ReductionInstDesc &Prev) {
4829   bool FP = I->getType()->isFloatingPointTy();
4830   bool FastMath = (FP && I->isCommutative() && I->isAssociative());
4831   switch (I->getOpcode()) {
4832   default:
4833     return ReductionInstDesc(false, I);
4834   case Instruction::PHI:
4835       if (FP && (Kind != RK_FloatMult && Kind != RK_FloatAdd &&
4836                  Kind != RK_FloatMinMax))
4837         return ReductionInstDesc(false, I);
4838     return ReductionInstDesc(I, Prev.MinMaxKind);
4839   case Instruction::Sub:
4840   case Instruction::Add:
4841     return ReductionInstDesc(Kind == RK_IntegerAdd, I);
4842   case Instruction::Mul:
4843     return ReductionInstDesc(Kind == RK_IntegerMult, I);
4844   case Instruction::And:
4845     return ReductionInstDesc(Kind == RK_IntegerAnd, I);
4846   case Instruction::Or:
4847     return ReductionInstDesc(Kind == RK_IntegerOr, I);
4848   case Instruction::Xor:
4849     return ReductionInstDesc(Kind == RK_IntegerXor, I);
4850   case Instruction::FMul:
4851     return ReductionInstDesc(Kind == RK_FloatMult && FastMath, I);
4852   case Instruction::FAdd:
4853     return ReductionInstDesc(Kind == RK_FloatAdd && FastMath, I);
4854   case Instruction::FCmp:
4855   case Instruction::ICmp:
4856   case Instruction::Select:
4857     if (Kind != RK_IntegerMinMax &&
4858         (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
4859       return ReductionInstDesc(false, I);
4860     return isMinMaxSelectCmpPattern(I, Prev);
4861   }
4862 }
4863
4864 LoopVectorizationLegality::InductionKind
4865 LoopVectorizationLegality::isInductionVariable(PHINode *Phi) {
4866   Type *PhiTy = Phi->getType();
4867   // We only handle integer and pointer inductions variables.
4868   if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
4869     return IK_NoInduction;
4870
4871   // Check that the PHI is consecutive.
4872   const SCEV *PhiScev = SE->getSCEV(Phi);
4873   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
4874   if (!AR) {
4875     DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
4876     return IK_NoInduction;
4877   }
4878   const SCEV *Step = AR->getStepRecurrence(*SE);
4879
4880   // Integer inductions need to have a stride of one.
4881   if (PhiTy->isIntegerTy()) {
4882     if (Step->isOne())
4883       return IK_IntInduction;
4884     if (Step->isAllOnesValue())
4885       return IK_ReverseIntInduction;
4886     return IK_NoInduction;
4887   }
4888
4889   // Calculate the pointer stride and check if it is consecutive.
4890   const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
4891   if (!C)
4892     return IK_NoInduction;
4893
4894   assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
4895   uint64_t Size = DL->getTypeAllocSize(PhiTy->getPointerElementType());
4896   if (C->getValue()->equalsInt(Size))
4897     return IK_PtrInduction;
4898   else if (C->getValue()->equalsInt(0 - Size))
4899     return IK_ReversePtrInduction;
4900
4901   return IK_NoInduction;
4902 }
4903
4904 bool LoopVectorizationLegality::isInductionVariable(const Value *V) {
4905   Value *In0 = const_cast<Value*>(V);
4906   PHINode *PN = dyn_cast_or_null<PHINode>(In0);
4907   if (!PN)
4908     return false;
4909
4910   return Inductions.count(PN);
4911 }
4912
4913 bool LoopVectorizationLegality::blockNeedsPredication(BasicBlock *BB)  {
4914   assert(TheLoop->contains(BB) && "Unknown block used");
4915
4916   // Blocks that do not dominate the latch need predication.
4917   BasicBlock* Latch = TheLoop->getLoopLatch();
4918   return !DT->dominates(BB, Latch);
4919 }
4920
4921 bool LoopVectorizationLegality::blockCanBePredicated(BasicBlock *BB,
4922                                             SmallPtrSet<Value *, 8>& SafePtrs) {
4923   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
4924     // We might be able to hoist the load.
4925     if (it->mayReadFromMemory()) {
4926       LoadInst *LI = dyn_cast<LoadInst>(it);
4927       if (!LI || !SafePtrs.count(LI->getPointerOperand()))
4928         return false;
4929     }
4930
4931     // We don't predicate stores at the moment.
4932     if (it->mayWriteToMemory()) {
4933       StoreInst *SI = dyn_cast<StoreInst>(it);
4934       // We only support predication of stores in basic blocks with one
4935       // predecessor.
4936       if (!SI || ++NumPredStores > NumberOfStoresToPredicate ||
4937           !SafePtrs.count(SI->getPointerOperand()) ||
4938           !SI->getParent()->getSinglePredecessor())
4939         return false;
4940     }
4941     if (it->mayThrow())
4942       return false;
4943
4944     // Check that we don't have a constant expression that can trap as operand.
4945     for (Instruction::op_iterator OI = it->op_begin(), OE = it->op_end();
4946          OI != OE; ++OI) {
4947       if (Constant *C = dyn_cast<Constant>(*OI))
4948         if (C->canTrap())
4949           return false;
4950     }
4951
4952     // The instructions below can trap.
4953     switch (it->getOpcode()) {
4954     default: continue;
4955     case Instruction::UDiv:
4956     case Instruction::SDiv:
4957     case Instruction::URem:
4958     case Instruction::SRem:
4959              return false;
4960     }
4961   }
4962
4963   return true;
4964 }
4965
4966 LoopVectorizationCostModel::VectorizationFactor
4967 LoopVectorizationCostModel::selectVectorizationFactor(bool OptForSize,
4968                                                       unsigned UserVF) {
4969   // Width 1 means no vectorize
4970   VectorizationFactor Factor = { 1U, 0U };
4971   if (OptForSize && Legal->getRuntimePointerCheck()->Need) {
4972     DEBUG(dbgs() << "LV: Aborting. Runtime ptr check is required in Os.\n");
4973     return Factor;
4974   }
4975
4976   if (!EnableCondStoresVectorization && Legal->NumPredStores) {
4977     DEBUG(dbgs() << "LV: No vectorization. There are conditional stores.\n");
4978     return Factor;
4979   }
4980
4981   // Find the trip count.
4982   unsigned TC = SE->getSmallConstantTripCount(TheLoop, TheLoop->getLoopLatch());
4983   DEBUG(dbgs() << "LV: Found trip count: " << TC << '\n');
4984
4985   unsigned WidestType = getWidestType();
4986   unsigned WidestRegister = TTI.getRegisterBitWidth(true);
4987   unsigned MaxSafeDepDist = -1U;
4988   if (Legal->getMaxSafeDepDistBytes() != -1U)
4989     MaxSafeDepDist = Legal->getMaxSafeDepDistBytes() * 8;
4990   WidestRegister = ((WidestRegister < MaxSafeDepDist) ?
4991                     WidestRegister : MaxSafeDepDist);
4992   unsigned MaxVectorSize = WidestRegister / WidestType;
4993   DEBUG(dbgs() << "LV: The Widest type: " << WidestType << " bits.\n");
4994   DEBUG(dbgs() << "LV: The Widest register is: "
4995           << WidestRegister << " bits.\n");
4996
4997   if (MaxVectorSize == 0) {
4998     DEBUG(dbgs() << "LV: The target has no vector registers.\n");
4999     MaxVectorSize = 1;
5000   }
5001
5002   assert(MaxVectorSize <= 32 && "Did not expect to pack so many elements"
5003          " into one vector!");
5004
5005   unsigned VF = MaxVectorSize;
5006
5007   // If we optimize the program for size, avoid creating the tail loop.
5008   if (OptForSize) {
5009     // If we are unable to calculate the trip count then don't try to vectorize.
5010     if (TC < 2) {
5011       DEBUG(dbgs() << "LV: Aborting. A tail loop is required in Os.\n");
5012       return Factor;
5013     }
5014
5015     // Find the maximum SIMD width that can fit within the trip count.
5016     VF = TC % MaxVectorSize;
5017
5018     if (VF == 0)
5019       VF = MaxVectorSize;
5020
5021     // If the trip count that we found modulo the vectorization factor is not
5022     // zero then we require a tail.
5023     if (VF < 2) {
5024       DEBUG(dbgs() << "LV: Aborting. A tail loop is required in Os.\n");
5025       return Factor;
5026     }
5027   }
5028
5029   if (UserVF != 0) {
5030     assert(isPowerOf2_32(UserVF) && "VF needs to be a power of two");
5031     DEBUG(dbgs() << "LV: Using user VF " << UserVF << ".\n");
5032
5033     Factor.Width = UserVF;
5034     return Factor;
5035   }
5036
5037   float Cost = expectedCost(1);
5038   unsigned Width = 1;
5039   DEBUG(dbgs() << "LV: Scalar loop costs: " << (int)Cost << ".\n");
5040   for (unsigned i=2; i <= VF; i*=2) {
5041     // Notice that the vector loop needs to be executed less times, so
5042     // we need to divide the cost of the vector loops by the width of
5043     // the vector elements.
5044     float VectorCost = expectedCost(i) / (float)i;
5045     DEBUG(dbgs() << "LV: Vector loop of width " << i << " costs: " <<
5046           (int)VectorCost << ".\n");
5047     if (VectorCost < Cost) {
5048       Cost = VectorCost;
5049       Width = i;
5050     }
5051   }
5052
5053   DEBUG(dbgs() << "LV: Selecting VF = : "<< Width << ".\n");
5054   Factor.Width = Width;
5055   Factor.Cost = Width * Cost;
5056   return Factor;
5057 }
5058
5059 unsigned LoopVectorizationCostModel::getWidestType() {
5060   unsigned MaxWidth = 8;
5061
5062   // For each block.
5063   for (Loop::block_iterator bb = TheLoop->block_begin(),
5064        be = TheLoop->block_end(); bb != be; ++bb) {
5065     BasicBlock *BB = *bb;
5066
5067     // For each instruction in the loop.
5068     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
5069       Type *T = it->getType();
5070
5071       // Only examine Loads, Stores and PHINodes.
5072       if (!isa<LoadInst>(it) && !isa<StoreInst>(it) && !isa<PHINode>(it))
5073         continue;
5074
5075       // Examine PHI nodes that are reduction variables.
5076       if (PHINode *PN = dyn_cast<PHINode>(it))
5077         if (!Legal->getReductionVars()->count(PN))
5078           continue;
5079
5080       // Examine the stored values.
5081       if (StoreInst *ST = dyn_cast<StoreInst>(it))
5082         T = ST->getValueOperand()->getType();
5083
5084       // Ignore loaded pointer types and stored pointer types that are not
5085       // consecutive. However, we do want to take consecutive stores/loads of
5086       // pointer vectors into account.
5087       if (T->isPointerTy() && !isConsecutiveLoadOrStore(it))
5088         continue;
5089
5090       MaxWidth = std::max(MaxWidth,
5091                           (unsigned)DL->getTypeSizeInBits(T->getScalarType()));
5092     }
5093   }
5094
5095   return MaxWidth;
5096 }
5097
5098 unsigned
5099 LoopVectorizationCostModel::selectUnrollFactor(bool OptForSize,
5100                                                unsigned UserUF,
5101                                                unsigned VF,
5102                                                unsigned LoopCost) {
5103
5104   // -- The unroll heuristics --
5105   // We unroll the loop in order to expose ILP and reduce the loop overhead.
5106   // There are many micro-architectural considerations that we can't predict
5107   // at this level. For example frontend pressure (on decode or fetch) due to
5108   // code size, or the number and capabilities of the execution ports.
5109   //
5110   // We use the following heuristics to select the unroll factor:
5111   // 1. If the code has reductions the we unroll in order to break the cross
5112   // iteration dependency.
5113   // 2. If the loop is really small then we unroll in order to reduce the loop
5114   // overhead.
5115   // 3. We don't unroll if we think that we will spill registers to memory due
5116   // to the increased register pressure.
5117
5118   // Use the user preference, unless 'auto' is selected.
5119   if (UserUF != 0)
5120     return UserUF;
5121
5122   // When we optimize for size we don't unroll.
5123   if (OptForSize)
5124     return 1;
5125
5126   // We used the distance for the unroll factor.
5127   if (Legal->getMaxSafeDepDistBytes() != -1U)
5128     return 1;
5129
5130   // Do not unroll loops with a relatively small trip count.
5131   unsigned TC = SE->getSmallConstantTripCount(TheLoop,
5132                                               TheLoop->getLoopLatch());
5133   if (TC > 1 && TC < TinyTripCountUnrollThreshold)
5134     return 1;
5135
5136   unsigned TargetNumRegisters = TTI.getNumberOfRegisters(VF > 1);
5137   DEBUG(dbgs() << "LV: The target has " << TargetNumRegisters <<
5138         " registers\n");
5139
5140   if (VF == 1) {
5141     if (ForceTargetNumScalarRegs.getNumOccurrences() > 0)
5142       TargetNumRegisters = ForceTargetNumScalarRegs;
5143   } else {
5144     if (ForceTargetNumVectorRegs.getNumOccurrences() > 0)
5145       TargetNumRegisters = ForceTargetNumVectorRegs;
5146   }
5147
5148   LoopVectorizationCostModel::RegisterUsage R = calculateRegisterUsage();
5149   // We divide by these constants so assume that we have at least one
5150   // instruction that uses at least one register.
5151   R.MaxLocalUsers = std::max(R.MaxLocalUsers, 1U);
5152   R.NumInstructions = std::max(R.NumInstructions, 1U);
5153
5154   // We calculate the unroll factor using the following formula.
5155   // Subtract the number of loop invariants from the number of available
5156   // registers. These registers are used by all of the unrolled instances.
5157   // Next, divide the remaining registers by the number of registers that is
5158   // required by the loop, in order to estimate how many parallel instances
5159   // fit without causing spills. All of this is rounded down if necessary to be
5160   // a power of two. We want power of two unroll factors to simplify any
5161   // addressing operations or alignment considerations.
5162   unsigned UF = PowerOf2Floor((TargetNumRegisters - R.LoopInvariantRegs) /
5163                               R.MaxLocalUsers);
5164
5165   // Don't count the induction variable as unrolled.
5166   if (EnableIndVarRegisterHeur)
5167     UF = PowerOf2Floor((TargetNumRegisters - R.LoopInvariantRegs - 1) /
5168                        std::max(1U, (R.MaxLocalUsers - 1)));
5169
5170   // Clamp the unroll factor ranges to reasonable factors.
5171   unsigned MaxUnrollSize = TTI.getMaximumUnrollFactor();
5172
5173   // Check if the user has overridden the unroll max.
5174   if (VF == 1) {
5175     if (ForceTargetMaxScalarUnrollFactor.getNumOccurrences() > 0)
5176       MaxUnrollSize = ForceTargetMaxScalarUnrollFactor;
5177   } else {
5178     if (ForceTargetMaxVectorUnrollFactor.getNumOccurrences() > 0)
5179       MaxUnrollSize = ForceTargetMaxVectorUnrollFactor;
5180   }
5181
5182   // If we did not calculate the cost for VF (because the user selected the VF)
5183   // then we calculate the cost of VF here.
5184   if (LoopCost == 0)
5185     LoopCost = expectedCost(VF);
5186
5187   // Clamp the calculated UF to be between the 1 and the max unroll factor
5188   // that the target allows.
5189   if (UF > MaxUnrollSize)
5190     UF = MaxUnrollSize;
5191   else if (UF < 1)
5192     UF = 1;
5193
5194   // Unroll if we vectorized this loop and there is a reduction that could
5195   // benefit from unrolling.
5196   if (VF > 1 && Legal->getReductionVars()->size()) {
5197     DEBUG(dbgs() << "LV: Unrolling because of reductions.\n");
5198     return UF;
5199   }
5200
5201   // Note that if we've already vectorized the loop we will have done the
5202   // runtime check and so unrolling won't require further checks.
5203   bool UnrollingRequiresRuntimePointerCheck =
5204       (VF == 1 && Legal->getRuntimePointerCheck()->Need);
5205
5206   // We want to unroll small loops in order to reduce the loop overhead and
5207   // potentially expose ILP opportunities.
5208   DEBUG(dbgs() << "LV: Loop cost is " << LoopCost << '\n');
5209   if (!UnrollingRequiresRuntimePointerCheck &&
5210       LoopCost < SmallLoopCost) {
5211     // We assume that the cost overhead is 1 and we use the cost model
5212     // to estimate the cost of the loop and unroll until the cost of the
5213     // loop overhead is about 5% of the cost of the loop.
5214     unsigned SmallUF = std::min(UF, (unsigned)PowerOf2Floor(SmallLoopCost / LoopCost));
5215
5216     // Unroll until store/load ports (estimated by max unroll factor) are
5217     // saturated.
5218     unsigned StoresUF = UF / (Legal->NumStores ? Legal->NumStores : 1);
5219     unsigned LoadsUF = UF /  (Legal->NumLoads ? Legal->NumLoads : 1);
5220
5221     if (EnableLoadStoreRuntimeUnroll && std::max(StoresUF, LoadsUF) > SmallUF) {
5222       DEBUG(dbgs() << "LV: Unrolling to saturate store or load ports.\n");
5223       return std::max(StoresUF, LoadsUF);
5224     }
5225
5226     DEBUG(dbgs() << "LV: Unrolling to reduce branch cost.\n");
5227     return SmallUF;
5228   }
5229
5230   DEBUG(dbgs() << "LV: Not Unrolling.\n");
5231   return 1;
5232 }
5233
5234 LoopVectorizationCostModel::RegisterUsage
5235 LoopVectorizationCostModel::calculateRegisterUsage() {
5236   // This function calculates the register usage by measuring the highest number
5237   // of values that are alive at a single location. Obviously, this is a very
5238   // rough estimation. We scan the loop in a topological order in order and
5239   // assign a number to each instruction. We use RPO to ensure that defs are
5240   // met before their users. We assume that each instruction that has in-loop
5241   // users starts an interval. We record every time that an in-loop value is
5242   // used, so we have a list of the first and last occurrences of each
5243   // instruction. Next, we transpose this data structure into a multi map that
5244   // holds the list of intervals that *end* at a specific location. This multi
5245   // map allows us to perform a linear search. We scan the instructions linearly
5246   // and record each time that a new interval starts, by placing it in a set.
5247   // If we find this value in the multi-map then we remove it from the set.
5248   // The max register usage is the maximum size of the set.
5249   // We also search for instructions that are defined outside the loop, but are
5250   // used inside the loop. We need this number separately from the max-interval
5251   // usage number because when we unroll, loop-invariant values do not take
5252   // more register.
5253   LoopBlocksDFS DFS(TheLoop);
5254   DFS.perform(LI);
5255
5256   RegisterUsage R;
5257   R.NumInstructions = 0;
5258
5259   // Each 'key' in the map opens a new interval. The values
5260   // of the map are the index of the 'last seen' usage of the
5261   // instruction that is the key.
5262   typedef DenseMap<Instruction*, unsigned> IntervalMap;
5263   // Maps instruction to its index.
5264   DenseMap<unsigned, Instruction*> IdxToInstr;
5265   // Marks the end of each interval.
5266   IntervalMap EndPoint;
5267   // Saves the list of instruction indices that are used in the loop.
5268   SmallSet<Instruction*, 8> Ends;
5269   // Saves the list of values that are used in the loop but are
5270   // defined outside the loop, such as arguments and constants.
5271   SmallPtrSet<Value*, 8> LoopInvariants;
5272
5273   unsigned Index = 0;
5274   for (LoopBlocksDFS::RPOIterator bb = DFS.beginRPO(),
5275        be = DFS.endRPO(); bb != be; ++bb) {
5276     R.NumInstructions += (*bb)->size();
5277     for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
5278          ++it) {
5279       Instruction *I = it;
5280       IdxToInstr[Index++] = I;
5281
5282       // Save the end location of each USE.
5283       for (unsigned i = 0; i < I->getNumOperands(); ++i) {
5284         Value *U = I->getOperand(i);
5285         Instruction *Instr = dyn_cast<Instruction>(U);
5286
5287         // Ignore non-instruction values such as arguments, constants, etc.
5288         if (!Instr) continue;
5289
5290         // If this instruction is outside the loop then record it and continue.
5291         if (!TheLoop->contains(Instr)) {
5292           LoopInvariants.insert(Instr);
5293           continue;
5294         }
5295
5296         // Overwrite previous end points.
5297         EndPoint[Instr] = Index;
5298         Ends.insert(Instr);
5299       }
5300     }
5301   }
5302
5303   // Saves the list of intervals that end with the index in 'key'.
5304   typedef SmallVector<Instruction*, 2> InstrList;
5305   DenseMap<unsigned, InstrList> TransposeEnds;
5306
5307   // Transpose the EndPoints to a list of values that end at each index.
5308   for (IntervalMap::iterator it = EndPoint.begin(), e = EndPoint.end();
5309        it != e; ++it)
5310     TransposeEnds[it->second].push_back(it->first);
5311
5312   SmallSet<Instruction*, 8> OpenIntervals;
5313   unsigned MaxUsage = 0;
5314
5315
5316   DEBUG(dbgs() << "LV(REG): Calculating max register usage:\n");
5317   for (unsigned int i = 0; i < Index; ++i) {
5318     Instruction *I = IdxToInstr[i];
5319     // Ignore instructions that are never used within the loop.
5320     if (!Ends.count(I)) continue;
5321
5322     // Remove all of the instructions that end at this location.
5323     InstrList &List = TransposeEnds[i];
5324     for (unsigned int j=0, e = List.size(); j < e; ++j)
5325       OpenIntervals.erase(List[j]);
5326
5327     // Count the number of live interals.
5328     MaxUsage = std::max(MaxUsage, OpenIntervals.size());
5329
5330     DEBUG(dbgs() << "LV(REG): At #" << i << " Interval # " <<
5331           OpenIntervals.size() << '\n');
5332
5333     // Add the current instruction to the list of open intervals.
5334     OpenIntervals.insert(I);
5335   }
5336
5337   unsigned Invariant = LoopInvariants.size();
5338   DEBUG(dbgs() << "LV(REG): Found max usage: " << MaxUsage << '\n');
5339   DEBUG(dbgs() << "LV(REG): Found invariant usage: " << Invariant << '\n');
5340   DEBUG(dbgs() << "LV(REG): LoopSize: " << R.NumInstructions << '\n');
5341
5342   R.LoopInvariantRegs = Invariant;
5343   R.MaxLocalUsers = MaxUsage;
5344   return R;
5345 }
5346
5347 unsigned LoopVectorizationCostModel::expectedCost(unsigned VF) {
5348   unsigned Cost = 0;
5349
5350   // For each block.
5351   for (Loop::block_iterator bb = TheLoop->block_begin(),
5352        be = TheLoop->block_end(); bb != be; ++bb) {
5353     unsigned BlockCost = 0;
5354     BasicBlock *BB = *bb;
5355
5356     // For each instruction in the old loop.
5357     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
5358       // Skip dbg intrinsics.
5359       if (isa<DbgInfoIntrinsic>(it))
5360         continue;
5361
5362       unsigned C = getInstructionCost(it, VF);
5363
5364       // Check if we should override the cost.
5365       if (ForceTargetInstructionCost.getNumOccurrences() > 0)
5366         C = ForceTargetInstructionCost;
5367
5368       BlockCost += C;
5369       DEBUG(dbgs() << "LV: Found an estimated cost of " << C << " for VF " <<
5370             VF << " For instruction: " << *it << '\n');
5371     }
5372
5373     // We assume that if-converted blocks have a 50% chance of being executed.
5374     // When the code is scalar then some of the blocks are avoided due to CF.
5375     // When the code is vectorized we execute all code paths.
5376     if (VF == 1 && Legal->blockNeedsPredication(*bb))
5377       BlockCost /= 2;
5378
5379     Cost += BlockCost;
5380   }
5381
5382   return Cost;
5383 }
5384
5385 /// \brief Check whether the address computation for a non-consecutive memory
5386 /// access looks like an unlikely candidate for being merged into the indexing
5387 /// mode.
5388 ///
5389 /// We look for a GEP which has one index that is an induction variable and all
5390 /// other indices are loop invariant. If the stride of this access is also
5391 /// within a small bound we decide that this address computation can likely be
5392 /// merged into the addressing mode.
5393 /// In all other cases, we identify the address computation as complex.
5394 static bool isLikelyComplexAddressComputation(Value *Ptr,
5395                                               LoopVectorizationLegality *Legal,
5396                                               ScalarEvolution *SE,
5397                                               const Loop *TheLoop) {
5398   GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr);
5399   if (!Gep)
5400     return true;
5401
5402   // We are looking for a gep with all loop invariant indices except for one
5403   // which should be an induction variable.
5404   unsigned NumOperands = Gep->getNumOperands();
5405   for (unsigned i = 1; i < NumOperands; ++i) {
5406     Value *Opd = Gep->getOperand(i);
5407     if (!SE->isLoopInvariant(SE->getSCEV(Opd), TheLoop) &&
5408         !Legal->isInductionVariable(Opd))
5409       return true;
5410   }
5411
5412   // Now we know we have a GEP ptr, %inv, %ind, %inv. Make sure that the step
5413   // can likely be merged into the address computation.
5414   unsigned MaxMergeDistance = 64;
5415
5416   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Ptr));
5417   if (!AddRec)
5418     return true;
5419
5420   // Check the step is constant.
5421   const SCEV *Step = AddRec->getStepRecurrence(*SE);
5422   // Calculate the pointer stride and check if it is consecutive.
5423   const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
5424   if (!C)
5425     return true;
5426
5427   const APInt &APStepVal = C->getValue()->getValue();
5428
5429   // Huge step value - give up.
5430   if (APStepVal.getBitWidth() > 64)
5431     return true;
5432
5433   int64_t StepVal = APStepVal.getSExtValue();
5434
5435   return StepVal > MaxMergeDistance;
5436 }
5437
5438 static bool isStrideMul(Instruction *I, LoopVectorizationLegality *Legal) {
5439   if (Legal->hasStride(I->getOperand(0)) || Legal->hasStride(I->getOperand(1)))
5440     return true;
5441   return false;
5442 }
5443
5444 unsigned
5445 LoopVectorizationCostModel::getInstructionCost(Instruction *I, unsigned VF) {
5446   // If we know that this instruction will remain uniform, check the cost of
5447   // the scalar version.
5448   if (Legal->isUniformAfterVectorization(I))
5449     VF = 1;
5450
5451   Type *RetTy = I->getType();
5452   Type *VectorTy = ToVectorTy(RetTy, VF);
5453
5454   // TODO: We need to estimate the cost of intrinsic calls.
5455   switch (I->getOpcode()) {
5456   case Instruction::GetElementPtr:
5457     // We mark this instruction as zero-cost because the cost of GEPs in
5458     // vectorized code depends on whether the corresponding memory instruction
5459     // is scalarized or not. Therefore, we handle GEPs with the memory
5460     // instruction cost.
5461     return 0;
5462   case Instruction::Br: {
5463     return TTI.getCFInstrCost(I->getOpcode());
5464   }
5465   case Instruction::PHI:
5466     //TODO: IF-converted IFs become selects.
5467     return 0;
5468   case Instruction::Add:
5469   case Instruction::FAdd:
5470   case Instruction::Sub:
5471   case Instruction::FSub:
5472   case Instruction::Mul:
5473   case Instruction::FMul:
5474   case Instruction::UDiv:
5475   case Instruction::SDiv:
5476   case Instruction::FDiv:
5477   case Instruction::URem:
5478   case Instruction::SRem:
5479   case Instruction::FRem:
5480   case Instruction::Shl:
5481   case Instruction::LShr:
5482   case Instruction::AShr:
5483   case Instruction::And:
5484   case Instruction::Or:
5485   case Instruction::Xor: {
5486     // Since we will replace the stride by 1 the multiplication should go away.
5487     if (I->getOpcode() == Instruction::Mul && isStrideMul(I, Legal))
5488       return 0;
5489     // Certain instructions can be cheaper to vectorize if they have a constant
5490     // second vector operand. One example of this are shifts on x86.
5491     TargetTransformInfo::OperandValueKind Op1VK =
5492       TargetTransformInfo::OK_AnyValue;
5493     TargetTransformInfo::OperandValueKind Op2VK =
5494       TargetTransformInfo::OK_AnyValue;
5495     Value *Op2 = I->getOperand(1);
5496
5497     // Check for a splat of a constant or for a non uniform vector of constants.
5498     if (isa<ConstantInt>(Op2))
5499       Op2VK = TargetTransformInfo::OK_UniformConstantValue;
5500     else if (isa<ConstantVector>(Op2) || isa<ConstantDataVector>(Op2)) {
5501       Op2VK = TargetTransformInfo::OK_NonUniformConstantValue;
5502       if (cast<Constant>(Op2)->getSplatValue() != NULL)
5503         Op2VK = TargetTransformInfo::OK_UniformConstantValue;
5504     }
5505
5506     return TTI.getArithmeticInstrCost(I->getOpcode(), VectorTy, Op1VK, Op2VK);
5507   }
5508   case Instruction::Select: {
5509     SelectInst *SI = cast<SelectInst>(I);
5510     const SCEV *CondSCEV = SE->getSCEV(SI->getCondition());
5511     bool ScalarCond = (SE->isLoopInvariant(CondSCEV, TheLoop));
5512     Type *CondTy = SI->getCondition()->getType();
5513     if (!ScalarCond)
5514       CondTy = VectorType::get(CondTy, VF);
5515
5516     return TTI.getCmpSelInstrCost(I->getOpcode(), VectorTy, CondTy);
5517   }
5518   case Instruction::ICmp:
5519   case Instruction::FCmp: {
5520     Type *ValTy = I->getOperand(0)->getType();
5521     VectorTy = ToVectorTy(ValTy, VF);
5522     return TTI.getCmpSelInstrCost(I->getOpcode(), VectorTy);
5523   }
5524   case Instruction::Store:
5525   case Instruction::Load: {
5526     StoreInst *SI = dyn_cast<StoreInst>(I);
5527     LoadInst *LI = dyn_cast<LoadInst>(I);
5528     Type *ValTy = (SI ? SI->getValueOperand()->getType() :
5529                    LI->getType());
5530     VectorTy = ToVectorTy(ValTy, VF);
5531
5532     unsigned Alignment = SI ? SI->getAlignment() : LI->getAlignment();
5533     unsigned AS = SI ? SI->getPointerAddressSpace() :
5534       LI->getPointerAddressSpace();
5535     Value *Ptr = SI ? SI->getPointerOperand() : LI->getPointerOperand();
5536     // We add the cost of address computation here instead of with the gep
5537     // instruction because only here we know whether the operation is
5538     // scalarized.
5539     if (VF == 1)
5540       return TTI.getAddressComputationCost(VectorTy) +
5541         TTI.getMemoryOpCost(I->getOpcode(), VectorTy, Alignment, AS);
5542
5543     // Scalarized loads/stores.
5544     int ConsecutiveStride = Legal->isConsecutivePtr(Ptr);
5545     bool Reverse = ConsecutiveStride < 0;
5546     unsigned ScalarAllocatedSize = DL->getTypeAllocSize(ValTy);
5547     unsigned VectorElementSize = DL->getTypeStoreSize(VectorTy)/VF;
5548     if (!ConsecutiveStride || ScalarAllocatedSize != VectorElementSize) {
5549       bool IsComplexComputation =
5550         isLikelyComplexAddressComputation(Ptr, Legal, SE, TheLoop);
5551       unsigned Cost = 0;
5552       // The cost of extracting from the value vector and pointer vector.
5553       Type *PtrTy = ToVectorTy(Ptr->getType(), VF);
5554       for (unsigned i = 0; i < VF; ++i) {
5555         //  The cost of extracting the pointer operand.
5556         Cost += TTI.getVectorInstrCost(Instruction::ExtractElement, PtrTy, i);
5557         // In case of STORE, the cost of ExtractElement from the vector.
5558         // In case of LOAD, the cost of InsertElement into the returned
5559         // vector.
5560         Cost += TTI.getVectorInstrCost(SI ? Instruction::ExtractElement :
5561                                             Instruction::InsertElement,
5562                                             VectorTy, i);
5563       }
5564
5565       // The cost of the scalar loads/stores.
5566       Cost += VF * TTI.getAddressComputationCost(PtrTy, IsComplexComputation);
5567       Cost += VF * TTI.getMemoryOpCost(I->getOpcode(), ValTy->getScalarType(),
5568                                        Alignment, AS);
5569       return Cost;
5570     }
5571
5572     // Wide load/stores.
5573     unsigned Cost = TTI.getAddressComputationCost(VectorTy);
5574     Cost += TTI.getMemoryOpCost(I->getOpcode(), VectorTy, Alignment, AS);
5575
5576     if (Reverse)
5577       Cost += TTI.getShuffleCost(TargetTransformInfo::SK_Reverse,
5578                                   VectorTy, 0);
5579     return Cost;
5580   }
5581   case Instruction::ZExt:
5582   case Instruction::SExt:
5583   case Instruction::FPToUI:
5584   case Instruction::FPToSI:
5585   case Instruction::FPExt:
5586   case Instruction::PtrToInt:
5587   case Instruction::IntToPtr:
5588   case Instruction::SIToFP:
5589   case Instruction::UIToFP:
5590   case Instruction::Trunc:
5591   case Instruction::FPTrunc:
5592   case Instruction::BitCast: {
5593     // We optimize the truncation of induction variable.
5594     // The cost of these is the same as the scalar operation.
5595     if (I->getOpcode() == Instruction::Trunc &&
5596         Legal->isInductionVariable(I->getOperand(0)))
5597       return TTI.getCastInstrCost(I->getOpcode(), I->getType(),
5598                                   I->getOperand(0)->getType());
5599
5600     Type *SrcVecTy = ToVectorTy(I->getOperand(0)->getType(), VF);
5601     return TTI.getCastInstrCost(I->getOpcode(), VectorTy, SrcVecTy);
5602   }
5603   case Instruction::Call: {
5604     CallInst *CI = cast<CallInst>(I);
5605     Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
5606     assert(ID && "Not an intrinsic call!");
5607     Type *RetTy = ToVectorTy(CI->getType(), VF);
5608     SmallVector<Type*, 4> Tys;
5609     for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i)
5610       Tys.push_back(ToVectorTy(CI->getArgOperand(i)->getType(), VF));
5611     return TTI.getIntrinsicInstrCost(ID, RetTy, Tys);
5612   }
5613   default: {
5614     // We are scalarizing the instruction. Return the cost of the scalar
5615     // instruction, plus the cost of insert and extract into vector
5616     // elements, times the vector width.
5617     unsigned Cost = 0;
5618
5619     if (!RetTy->isVoidTy() && VF != 1) {
5620       unsigned InsCost = TTI.getVectorInstrCost(Instruction::InsertElement,
5621                                                 VectorTy);
5622       unsigned ExtCost = TTI.getVectorInstrCost(Instruction::ExtractElement,
5623                                                 VectorTy);
5624
5625       // The cost of inserting the results plus extracting each one of the
5626       // operands.
5627       Cost += VF * (InsCost + ExtCost * I->getNumOperands());
5628     }
5629
5630     // The cost of executing VF copies of the scalar instruction. This opcode
5631     // is unknown. Assume that it is the same as 'mul'.
5632     Cost += VF * TTI.getArithmeticInstrCost(Instruction::Mul, VectorTy);
5633     return Cost;
5634   }
5635   }// end of switch.
5636 }
5637
5638 Type* LoopVectorizationCostModel::ToVectorTy(Type *Scalar, unsigned VF) {
5639   if (Scalar->isVoidTy() || VF == 1)
5640     return Scalar;
5641   return VectorType::get(Scalar, VF);
5642 }
5643
5644 char LoopVectorize::ID = 0;
5645 static const char lv_name[] = "Loop Vectorization";
5646 INITIALIZE_PASS_BEGIN(LoopVectorize, LV_NAME, lv_name, false, false)
5647 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
5648 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfo)
5649 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
5650 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
5651 INITIALIZE_PASS_DEPENDENCY(LCSSA)
5652 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
5653 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
5654 INITIALIZE_PASS_END(LoopVectorize, LV_NAME, lv_name, false, false)
5655
5656 namespace llvm {
5657   Pass *createLoopVectorizePass(bool NoUnrolling, bool AlwaysVectorize) {
5658     return new LoopVectorize(NoUnrolling, AlwaysVectorize);
5659   }
5660 }
5661
5662 bool LoopVectorizationCostModel::isConsecutiveLoadOrStore(Instruction *Inst) {
5663   // Check for a store.
5664   if (StoreInst *ST = dyn_cast<StoreInst>(Inst))
5665     return Legal->isConsecutivePtr(ST->getPointerOperand()) != 0;
5666
5667   // Check for a load.
5668   if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
5669     return Legal->isConsecutivePtr(LI->getPointerOperand()) != 0;
5670
5671   return false;
5672 }
5673
5674
5675 void InnerLoopUnroller::scalarizeInstruction(Instruction *Instr,
5676                                              bool IfPredicateStore) {
5677   assert(!Instr->getType()->isAggregateType() && "Can't handle vectors");
5678   // Holds vector parameters or scalars, in case of uniform vals.
5679   SmallVector<VectorParts, 4> Params;
5680
5681   setDebugLocFromInst(Builder, Instr);
5682
5683   // Find all of the vectorized parameters.
5684   for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) {
5685     Value *SrcOp = Instr->getOperand(op);
5686
5687     // If we are accessing the old induction variable, use the new one.
5688     if (SrcOp == OldInduction) {
5689       Params.push_back(getVectorValue(SrcOp));
5690       continue;
5691     }
5692
5693     // Try using previously calculated values.
5694     Instruction *SrcInst = dyn_cast<Instruction>(SrcOp);
5695
5696     // If the src is an instruction that appeared earlier in the basic block
5697     // then it should already be vectorized.
5698     if (SrcInst && OrigLoop->contains(SrcInst)) {
5699       assert(WidenMap.has(SrcInst) && "Source operand is unavailable");
5700       // The parameter is a vector value from earlier.
5701       Params.push_back(WidenMap.get(SrcInst));
5702     } else {
5703       // The parameter is a scalar from outside the loop. Maybe even a constant.
5704       VectorParts Scalars;
5705       Scalars.append(UF, SrcOp);
5706       Params.push_back(Scalars);
5707     }
5708   }
5709
5710   assert(Params.size() == Instr->getNumOperands() &&
5711          "Invalid number of operands");
5712
5713   // Does this instruction return a value ?
5714   bool IsVoidRetTy = Instr->getType()->isVoidTy();
5715
5716   Value *UndefVec = IsVoidRetTy ? 0 :
5717   UndefValue::get(Instr->getType());
5718   // Create a new entry in the WidenMap and initialize it to Undef or Null.
5719   VectorParts &VecResults = WidenMap.splat(Instr, UndefVec);
5720
5721   Instruction *InsertPt = Builder.GetInsertPoint();
5722   BasicBlock *IfBlock = Builder.GetInsertBlock();
5723   BasicBlock *CondBlock = 0;
5724
5725   VectorParts Cond;
5726   Loop *VectorLp = 0;
5727   if (IfPredicateStore) {
5728     assert(Instr->getParent()->getSinglePredecessor() &&
5729            "Only support single predecessor blocks");
5730     Cond = createEdgeMask(Instr->getParent()->getSinglePredecessor(),
5731                           Instr->getParent());
5732     VectorLp = LI->getLoopFor(IfBlock);
5733     assert(VectorLp && "Must have a loop for this block");
5734   }
5735
5736   // For each vector unroll 'part':
5737   for (unsigned Part = 0; Part < UF; ++Part) {
5738     // For each scalar that we create:
5739
5740     // Start an "if (pred) a[i] = ..." block.
5741     Value *Cmp = 0;
5742     if (IfPredicateStore) {
5743       if (Cond[Part]->getType()->isVectorTy())
5744         Cond[Part] =
5745             Builder.CreateExtractElement(Cond[Part], Builder.getInt32(0));
5746       Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Cond[Part],
5747                                ConstantInt::get(Cond[Part]->getType(), 1));
5748       CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.store");
5749       LoopVectorBody.push_back(CondBlock);
5750       VectorLp->addBasicBlockToLoop(CondBlock, LI->getBase());
5751       // Update Builder with newly created basic block.
5752       Builder.SetInsertPoint(InsertPt);
5753     }
5754
5755     Instruction *Cloned = Instr->clone();
5756       if (!IsVoidRetTy)
5757         Cloned->setName(Instr->getName() + ".cloned");
5758       // Replace the operands of the cloned instructions with extracted scalars.
5759       for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) {
5760         Value *Op = Params[op][Part];
5761         Cloned->setOperand(op, Op);
5762       }
5763
5764       // Place the cloned scalar in the new loop.
5765       Builder.Insert(Cloned);
5766
5767       // If the original scalar returns a value we need to place it in a vector
5768       // so that future users will be able to use it.
5769       if (!IsVoidRetTy)
5770         VecResults[Part] = Cloned;
5771
5772     // End if-block.
5773       if (IfPredicateStore) {
5774         BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else");
5775         LoopVectorBody.push_back(NewIfBlock);
5776         VectorLp->addBasicBlockToLoop(NewIfBlock, LI->getBase());
5777         Builder.SetInsertPoint(InsertPt);
5778         Instruction *OldBr = IfBlock->getTerminator();
5779         BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
5780         OldBr->eraseFromParent();
5781         IfBlock = NewIfBlock;
5782       }
5783   }
5784 }
5785
5786 void InnerLoopUnroller::vectorizeMemoryInstruction(Instruction *Instr) {
5787   StoreInst *SI = dyn_cast<StoreInst>(Instr);
5788   bool IfPredicateStore = (SI && Legal->blockNeedsPredication(SI->getParent()));
5789
5790   return scalarizeInstruction(Instr, IfPredicateStore);
5791 }
5792
5793 Value *InnerLoopUnroller::reverseVector(Value *Vec) {
5794   return Vec;
5795 }
5796
5797 Value *InnerLoopUnroller::getBroadcastInstrs(Value *V) {
5798   return V;
5799 }
5800
5801 Value *InnerLoopUnroller::getConsecutiveVector(Value* Val, int StartIdx,
5802                                                bool Negate) {
5803   // When unrolling and the VF is 1, we only need to add a simple scalar.
5804   Type *ITy = Val->getType();
5805   assert(!ITy->isVectorTy() && "Val must be a scalar");
5806   Constant *C = ConstantInt::get(ITy, StartIdx, Negate);
5807   return Builder.CreateAdd(Val, C, "induction");
5808 }
5809