Home | History | Annotate | Download | only in Vectorize
      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. Legalization of the IR is done
     12 // in the codegen. However, the vectorizer uses (will use) the codegen
     13 // interfaces to generate IR that is likely to result in an optimal binary.
     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/MapVector.h"
     51 #include "llvm/ADT/SmallPtrSet.h"
     52 #include "llvm/ADT/SmallSet.h"
     53 #include "llvm/ADT/SmallVector.h"
     54 #include "llvm/ADT/StringExtras.h"
     55 #include "llvm/Analysis/AliasAnalysis.h"
     56 #include "llvm/Analysis/AliasSetTracker.h"
     57 #include "llvm/Analysis/Dominators.h"
     58 #include "llvm/Analysis/LoopInfo.h"
     59 #include "llvm/Analysis/LoopIterator.h"
     60 #include "llvm/Analysis/LoopPass.h"
     61 #include "llvm/Analysis/ScalarEvolution.h"
     62 #include "llvm/Analysis/ScalarEvolutionExpander.h"
     63 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
     64 #include "llvm/Analysis/TargetTransformInfo.h"
     65 #include "llvm/Analysis/ValueTracking.h"
     66 #include "llvm/Analysis/Verifier.h"
     67 #include "llvm/IR/Constants.h"
     68 #include "llvm/IR/DataLayout.h"
     69 #include "llvm/IR/DerivedTypes.h"
     70 #include "llvm/IR/Function.h"
     71 #include "llvm/IR/IRBuilder.h"
     72 #include "llvm/IR/Instructions.h"
     73 #include "llvm/IR/IntrinsicInst.h"
     74 #include "llvm/IR/LLVMContext.h"
     75 #include "llvm/IR/Module.h"
     76 #include "llvm/IR/Type.h"
     77 #include "llvm/IR/Value.h"
     78 #include "llvm/Pass.h"
     79 #include "llvm/Support/CommandLine.h"
     80 #include "llvm/Support/Debug.h"
     81 #include "llvm/Support/raw_ostream.h"
     82 #include "llvm/Target/TargetLibraryInfo.h"
     83 #include "llvm/Transforms/Scalar.h"
     84 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
     85 #include "llvm/Transforms/Utils/Local.h"
     86 #include <algorithm>
     87 #include <map>
     88 
     89 using namespace llvm;
     90 
     91 static cl::opt<unsigned>
     92 VectorizationFactor("force-vector-width", cl::init(0), cl::Hidden,
     93                     cl::desc("Sets the SIMD width. Zero is autoselect."));
     94 
     95 static cl::opt<unsigned>
     96 VectorizationUnroll("force-vector-unroll", cl::init(0), cl::Hidden,
     97                     cl::desc("Sets the vectorization unroll count. "
     98                              "Zero is autoselect."));
     99 
    100 static cl::opt<bool>
    101 EnableIfConversion("enable-if-conversion", cl::init(true), cl::Hidden,
    102                    cl::desc("Enable if-conversion during vectorization."));
    103 
    104 /// We don't vectorize loops with a known constant trip count below this number.
    105 static cl::opt<unsigned>
    106 TinyTripCountVectorThreshold("vectorizer-min-trip-count", cl::init(16),
    107                              cl::Hidden,
    108                              cl::desc("Don't vectorize loops with a constant "
    109                                       "trip count that is smaller than this "
    110                                       "value."));
    111 
    112 /// We don't unroll loops with a known constant trip count below this number.
    113 static const unsigned TinyTripCountUnrollThreshold = 128;
    114 
    115 /// When performing a runtime memory check, do not check more than this
    116 /// number of pointers. Notice that the check is quadratic!
    117 static const unsigned RuntimeMemoryCheckThreshold = 4;
    118 
    119 /// We use a metadata with this name  to indicate that a scalar loop was
    120 /// vectorized and that we don't need to re-vectorize it if we run into it
    121 /// again.
    122 static const char*
    123 AlreadyVectorizedMDName = "llvm.vectorizer.already_vectorized";
    124 
    125 namespace {
    126 
    127 // Forward declarations.
    128 class LoopVectorizationLegality;
    129 class LoopVectorizationCostModel;
    130 
    131 /// InnerLoopVectorizer vectorizes loops which contain only one basic
    132 /// block to a specified vectorization factor (VF).
    133 /// This class performs the widening of scalars into vectors, or multiple
    134 /// scalars. This class also implements the following features:
    135 /// * It inserts an epilogue loop for handling loops that don't have iteration
    136 ///   counts that are known to be a multiple of the vectorization factor.
    137 /// * It handles the code generation for reduction variables.
    138 /// * Scalarization (implementation using scalars) of un-vectorizable
    139 ///   instructions.
    140 /// InnerLoopVectorizer does not perform any vectorization-legality
    141 /// checks, and relies on the caller to check for the different legality
    142 /// aspects. The InnerLoopVectorizer relies on the
    143 /// LoopVectorizationLegality class to provide information about the induction
    144 /// and reduction variables that were found to a given vectorization factor.
    145 class InnerLoopVectorizer {
    146 public:
    147   InnerLoopVectorizer(Loop *OrigLoop, ScalarEvolution *SE, LoopInfo *LI,
    148                       DominatorTree *DT, DataLayout *DL,
    149                       const TargetLibraryInfo *TLI, unsigned VecWidth,
    150                       unsigned UnrollFactor)
    151       : OrigLoop(OrigLoop), SE(SE), LI(LI), DT(DT), DL(DL), TLI(TLI),
    152         VF(VecWidth), UF(UnrollFactor), Builder(SE->getContext()), Induction(0),
    153         OldInduction(0), WidenMap(UnrollFactor) {}
    154 
    155   // Perform the actual loop widening (vectorization).
    156   void vectorize(LoopVectorizationLegality *Legal) {
    157     // Create a new empty loop. Unlink the old loop and connect the new one.
    158     createEmptyLoop(Legal);
    159     // Widen each instruction in the old loop to a new one in the new loop.
    160     // Use the Legality module to find the induction and reduction variables.
    161     vectorizeLoop(Legal);
    162     // Register the new loop and update the analysis passes.
    163     updateAnalysis();
    164   }
    165 
    166 private:
    167   /// A small list of PHINodes.
    168   typedef SmallVector<PHINode*, 4> PhiVector;
    169   /// When we unroll loops we have multiple vector values for each scalar.
    170   /// This data structure holds the unrolled and vectorized values that
    171   /// originated from one scalar instruction.
    172   typedef SmallVector<Value*, 2> VectorParts;
    173 
    174   /// Add code that checks at runtime if the accessed arrays overlap.
    175   /// Returns the comparator value or NULL if no check is needed.
    176   Instruction *addRuntimeCheck(LoopVectorizationLegality *Legal,
    177                                Instruction *Loc);
    178   /// Create an empty loop, based on the loop ranges of the old loop.
    179   void createEmptyLoop(LoopVectorizationLegality *Legal);
    180   /// Copy and widen the instructions from the old loop.
    181   void vectorizeLoop(LoopVectorizationLegality *Legal);
    182 
    183   /// A helper function that computes the predicate of the block BB, assuming
    184   /// that the header block of the loop is set to True. It returns the *entry*
    185   /// mask for the block BB.
    186   VectorParts createBlockInMask(BasicBlock *BB);
    187   /// A helper function that computes the predicate of the edge between SRC
    188   /// and DST.
    189   VectorParts createEdgeMask(BasicBlock *Src, BasicBlock *Dst);
    190 
    191   /// A helper function to vectorize a single BB within the innermost loop.
    192   void vectorizeBlockInLoop(LoopVectorizationLegality *Legal, BasicBlock *BB,
    193                             PhiVector *PV);
    194 
    195   /// Insert the new loop to the loop hierarchy and pass manager
    196   /// and update the analysis passes.
    197   void updateAnalysis();
    198 
    199   /// This instruction is un-vectorizable. Implement it as a sequence
    200   /// of scalars.
    201   void scalarizeInstruction(Instruction *Instr);
    202 
    203   /// Vectorize Load and Store instructions,
    204   void vectorizeMemoryInstruction(Instruction *Instr,
    205                                   LoopVectorizationLegality *Legal);
    206 
    207   /// Create a broadcast instruction. This method generates a broadcast
    208   /// instruction (shuffle) for loop invariant values and for the induction
    209   /// value. If this is the induction variable then we extend it to N, N+1, ...
    210   /// this is needed because each iteration in the loop corresponds to a SIMD
    211   /// element.
    212   Value *getBroadcastInstrs(Value *V);
    213 
    214   /// This function adds 0, 1, 2 ... to each vector element, starting at zero.
    215   /// If Negate is set then negative numbers are added e.g. (0, -1, -2, ...).
    216   /// The sequence starts at StartIndex.
    217   Value *getConsecutiveVector(Value* Val, unsigned StartIdx, bool Negate);
    218 
    219   /// When we go over instructions in the basic block we rely on previous
    220   /// values within the current basic block or on loop invariant values.
    221   /// When we widen (vectorize) values we place them in the map. If the values
    222   /// are not within the map, they have to be loop invariant, so we simply
    223   /// broadcast them into a vector.
    224   VectorParts &getVectorValue(Value *V);
    225 
    226   /// Generate a shuffle sequence that will reverse the vector Vec.
    227   Value *reverseVector(Value *Vec);
    228 
    229   /// This is a helper class that holds the vectorizer state. It maps scalar
    230   /// instructions to vector instructions. When the code is 'unrolled' then
    231   /// then a single scalar value is mapped to multiple vector parts. The parts
    232   /// are stored in the VectorPart type.
    233   struct ValueMap {
    234     /// C'tor.  UnrollFactor controls the number of vectors ('parts') that
    235     /// are mapped.
    236     ValueMap(unsigned UnrollFactor) : UF(UnrollFactor) {}
    237 
    238     /// \return True if 'Key' is saved in the Value Map.
    239     bool has(Value *Key) const { return MapStorage.count(Key); }
    240 
    241     /// Initializes a new entry in the map. Sets all of the vector parts to the
    242     /// save value in 'Val'.
    243     /// \return A reference to a vector with splat values.
    244     VectorParts &splat(Value *Key, Value *Val) {
    245       VectorParts &Entry = MapStorage[Key];
    246       Entry.assign(UF, Val);
    247       return Entry;
    248     }
    249 
    250     ///\return A reference to the value that is stored at 'Key'.
    251     VectorParts &get(Value *Key) {
    252       VectorParts &Entry = MapStorage[Key];
    253       if (Entry.empty())
    254         Entry.resize(UF);
    255       assert(Entry.size() == UF);
    256       return Entry;
    257     }
    258 
    259   private:
    260     /// The unroll factor. Each entry in the map stores this number of vector
    261     /// elements.
    262     unsigned UF;
    263 
    264     /// Map storage. We use std::map and not DenseMap because insertions to a
    265     /// dense map invalidates its iterators.
    266     std::map<Value *, VectorParts> MapStorage;
    267   };
    268 
    269   /// The original loop.
    270   Loop *OrigLoop;
    271   /// Scev analysis to use.
    272   ScalarEvolution *SE;
    273   /// Loop Info.
    274   LoopInfo *LI;
    275   /// Dominator Tree.
    276   DominatorTree *DT;
    277   /// Data Layout.
    278   DataLayout *DL;
    279   /// Target Library Info.
    280   const TargetLibraryInfo *TLI;
    281 
    282   /// The vectorization SIMD factor to use. Each vector will have this many
    283   /// vector elements.
    284   unsigned VF;
    285   /// The vectorization unroll factor to use. Each scalar is vectorized to this
    286   /// many different vector instructions.
    287   unsigned UF;
    288 
    289   /// The builder that we use
    290   IRBuilder<> Builder;
    291 
    292   // --- Vectorization state ---
    293 
    294   /// The vector-loop preheader.
    295   BasicBlock *LoopVectorPreHeader;
    296   /// The scalar-loop preheader.
    297   BasicBlock *LoopScalarPreHeader;
    298   /// Middle Block between the vector and the scalar.
    299   BasicBlock *LoopMiddleBlock;
    300   ///The ExitBlock of the scalar loop.
    301   BasicBlock *LoopExitBlock;
    302   ///The vector loop body.
    303   BasicBlock *LoopVectorBody;
    304   ///The scalar loop body.
    305   BasicBlock *LoopScalarBody;
    306   /// A list of all bypass blocks. The first block is the entry of the loop.
    307   SmallVector<BasicBlock *, 4> LoopBypassBlocks;
    308 
    309   /// The new Induction variable which was added to the new block.
    310   PHINode *Induction;
    311   /// The induction variable of the old basic block.
    312   PHINode *OldInduction;
    313   /// Maps scalars to widened vectors.
    314   ValueMap WidenMap;
    315 };
    316 
    317 /// LoopVectorizationLegality checks if it is legal to vectorize a loop, and
    318 /// to what vectorization factor.
    319 /// This class does not look at the profitability of vectorization, only the
    320 /// legality. This class has two main kinds of checks:
    321 /// * Memory checks - The code in canVectorizeMemory checks if vectorization
    322 ///   will change the order of memory accesses in a way that will change the
    323 ///   correctness of the program.
    324 /// * Scalars checks - The code in canVectorizeInstrs and canVectorizeMemory
    325 /// checks for a number of different conditions, such as the availability of a
    326 /// single induction variable, that all types are supported and vectorize-able,
    327 /// etc. This code reflects the capabilities of InnerLoopVectorizer.
    328 /// This class is also used by InnerLoopVectorizer for identifying
    329 /// induction variable and the different reduction variables.
    330 class LoopVectorizationLegality {
    331 public:
    332   LoopVectorizationLegality(Loop *L, ScalarEvolution *SE, DataLayout *DL,
    333                             DominatorTree *DT, TargetTransformInfo* TTI,
    334                             AliasAnalysis *AA, TargetLibraryInfo *TLI)
    335       : TheLoop(L), SE(SE), DL(DL), DT(DT), TTI(TTI), AA(AA), TLI(TLI),
    336         Induction(0) {}
    337 
    338   /// This enum represents the kinds of reductions that we support.
    339   enum ReductionKind {
    340     RK_NoReduction, ///< Not a reduction.
    341     RK_IntegerAdd,  ///< Sum of integers.
    342     RK_IntegerMult, ///< Product of integers.
    343     RK_IntegerOr,   ///< Bitwise or logical OR of numbers.
    344     RK_IntegerAnd,  ///< Bitwise or logical AND of numbers.
    345     RK_IntegerXor,  ///< Bitwise or logical XOR of numbers.
    346     RK_FloatAdd,    ///< Sum of floats.
    347     RK_FloatMult    ///< Product of floats.
    348   };
    349 
    350   /// This enum represents the kinds of inductions that we support.
    351   enum InductionKind {
    352     IK_NoInduction,         ///< Not an induction variable.
    353     IK_IntInduction,        ///< Integer induction variable. Step = 1.
    354     IK_ReverseIntInduction, ///< Reverse int induction variable. Step = -1.
    355     IK_PtrInduction,        ///< Pointer induction var. Step = sizeof(elem).
    356     IK_ReversePtrInduction  ///< Reverse ptr indvar. Step = - sizeof(elem).
    357   };
    358 
    359   /// This POD struct holds information about reduction variables.
    360   struct ReductionDescriptor {
    361     ReductionDescriptor() : StartValue(0), LoopExitInstr(0),
    362       Kind(RK_NoReduction) {}
    363 
    364     ReductionDescriptor(Value *Start, Instruction *Exit, ReductionKind K)
    365         : StartValue(Start), LoopExitInstr(Exit), Kind(K) {}
    366 
    367     // The starting value of the reduction.
    368     // It does not have to be zero!
    369     Value *StartValue;
    370     // The instruction who's value is used outside the loop.
    371     Instruction *LoopExitInstr;
    372     // The kind of the reduction.
    373     ReductionKind Kind;
    374   };
    375 
    376   // This POD struct holds information about the memory runtime legality
    377   // check that a group of pointers do not overlap.
    378   struct RuntimePointerCheck {
    379     RuntimePointerCheck() : Need(false) {}
    380 
    381     /// Reset the state of the pointer runtime information.
    382     void reset() {
    383       Need = false;
    384       Pointers.clear();
    385       Starts.clear();
    386       Ends.clear();
    387     }
    388 
    389     /// Insert a pointer and calculate the start and end SCEVs.
    390     void insert(ScalarEvolution *SE, Loop *Lp, Value *Ptr);
    391 
    392     /// This flag indicates if we need to add the runtime check.
    393     bool Need;
    394     /// Holds the pointers that we need to check.
    395     SmallVector<Value*, 2> Pointers;
    396     /// Holds the pointer value at the beginning of the loop.
    397     SmallVector<const SCEV*, 2> Starts;
    398     /// Holds the pointer value at the end of the loop.
    399     SmallVector<const SCEV*, 2> Ends;
    400   };
    401 
    402   /// A POD for saving information about induction variables.
    403   struct InductionInfo {
    404     InductionInfo(Value *Start, InductionKind K) : StartValue(Start), IK(K) {}
    405     InductionInfo() : StartValue(0), IK(IK_NoInduction) {}
    406     /// Start value.
    407     Value *StartValue;
    408     /// Induction kind.
    409     InductionKind IK;
    410   };
    411 
    412   /// ReductionList contains the reduction descriptors for all
    413   /// of the reductions that were found in the loop.
    414   typedef DenseMap<PHINode*, ReductionDescriptor> ReductionList;
    415 
    416   /// InductionList saves induction variables and maps them to the
    417   /// induction descriptor.
    418   typedef MapVector<PHINode*, InductionInfo> InductionList;
    419 
    420   /// Alias(Multi)Map stores the values (GEPs or underlying objects and their
    421   /// respective Store/Load instruction(s) to calculate aliasing.
    422   typedef MapVector<Value*, Instruction* > AliasMap;
    423   typedef DenseMap<Value*, std::vector<Instruction*> > AliasMultiMap;
    424 
    425   /// Returns true if it is legal to vectorize this loop.
    426   /// This does not mean that it is profitable to vectorize this
    427   /// loop, only that it is legal to do so.
    428   bool canVectorize();
    429 
    430   /// Returns the Induction variable.
    431   PHINode *getInduction() { return Induction; }
    432 
    433   /// Returns the reduction variables found in the loop.
    434   ReductionList *getReductionVars() { return &Reductions; }
    435 
    436   /// Returns the induction variables found in the loop.
    437   InductionList *getInductionVars() { return &Inductions; }
    438 
    439   /// Returns True if V is an induction variable in this loop.
    440   bool isInductionVariable(const Value *V);
    441 
    442   /// Return true if the block BB needs to be predicated in order for the loop
    443   /// to be vectorized.
    444   bool blockNeedsPredication(BasicBlock *BB);
    445 
    446   /// Check if this  pointer is consecutive when vectorizing. This happens
    447   /// when the last index of the GEP is the induction variable, or that the
    448   /// pointer itself is an induction variable.
    449   /// This check allows us to vectorize A[idx] into a wide load/store.
    450   /// Returns:
    451   /// 0 - Stride is unknown or non consecutive.
    452   /// 1 - Address is consecutive.
    453   /// -1 - Address is consecutive, and decreasing.
    454   int isConsecutivePtr(Value *Ptr);
    455 
    456   /// Returns true if the value V is uniform within the loop.
    457   bool isUniform(Value *V);
    458 
    459   /// Returns true if this instruction will remain scalar after vectorization.
    460   bool isUniformAfterVectorization(Instruction* I) { return Uniforms.count(I); }
    461 
    462   /// Returns the information that we collected about runtime memory check.
    463   RuntimePointerCheck *getRuntimePointerCheck() { return &PtrRtCheck; }
    464 private:
    465   /// Check if a single basic block loop is vectorizable.
    466   /// At this point we know that this is a loop with a constant trip count
    467   /// and we only need to check individual instructions.
    468   bool canVectorizeInstrs();
    469 
    470   /// When we vectorize loops we may change the order in which
    471   /// we read and write from memory. This method checks if it is
    472   /// legal to vectorize the code, considering only memory constrains.
    473   /// Returns true if the loop is vectorizable
    474   bool canVectorizeMemory();
    475 
    476   /// Return true if we can vectorize this loop using the IF-conversion
    477   /// transformation.
    478   bool canVectorizeWithIfConvert();
    479 
    480   /// Collect the variables that need to stay uniform after vectorization.
    481   void collectLoopUniforms();
    482 
    483   /// Return true if all of the instructions in the block can be speculatively
    484   /// executed.
    485   bool blockCanBePredicated(BasicBlock *BB);
    486 
    487   /// Returns True, if 'Phi' is the kind of reduction variable for type
    488   /// 'Kind'. If this is a reduction variable, it adds it to ReductionList.
    489   bool AddReductionVar(PHINode *Phi, ReductionKind Kind);
    490   /// Returns true if the instruction I can be a reduction variable of type
    491   /// 'Kind'.
    492   bool isReductionInstr(Instruction *I, ReductionKind Kind);
    493   /// Returns the induction kind of Phi. This function may return NoInduction
    494   /// if the PHI is not an induction variable.
    495   InductionKind isInductionVariable(PHINode *Phi);
    496   /// Return true if can compute the address bounds of Ptr within the loop.
    497   bool hasComputableBounds(Value *Ptr);
    498   /// Return true if there is the chance of write reorder.
    499   bool hasPossibleGlobalWriteReorder(Value *Object,
    500                                      Instruction *Inst,
    501                                      AliasMultiMap &WriteObjects,
    502                                      unsigned MaxByteWidth);
    503   /// Return the AA location for a load or a store.
    504   AliasAnalysis::Location getLoadStoreLocation(Instruction *Inst);
    505 
    506 
    507   /// The loop that we evaluate.
    508   Loop *TheLoop;
    509   /// Scev analysis.
    510   ScalarEvolution *SE;
    511   /// DataLayout analysis.
    512   DataLayout *DL;
    513   /// Dominators.
    514   DominatorTree *DT;
    515   /// Target Info.
    516   TargetTransformInfo *TTI;
    517   /// Alias Analysis.
    518   AliasAnalysis *AA;
    519   /// Target Library Info.
    520   TargetLibraryInfo *TLI;
    521 
    522   //  ---  vectorization state --- //
    523 
    524   /// Holds the integer induction variable. This is the counter of the
    525   /// loop.
    526   PHINode *Induction;
    527   /// Holds the reduction variables.
    528   ReductionList Reductions;
    529   /// Holds all of the induction variables that we found in the loop.
    530   /// Notice that inductions don't need to start at zero and that induction
    531   /// variables can be pointers.
    532   InductionList Inductions;
    533 
    534   /// Allowed outside users. This holds the reduction
    535   /// vars which can be accessed from outside the loop.
    536   SmallPtrSet<Value*, 4> AllowedExit;
    537   /// This set holds the variables which are known to be uniform after
    538   /// vectorization.
    539   SmallPtrSet<Instruction*, 4> Uniforms;
    540   /// We need to check that all of the pointers in this list are disjoint
    541   /// at runtime.
    542   RuntimePointerCheck PtrRtCheck;
    543 };
    544 
    545 /// LoopVectorizationCostModel - estimates the expected speedups due to
    546 /// vectorization.
    547 /// In many cases vectorization is not profitable. This can happen because of
    548 /// a number of reasons. In this class we mainly attempt to predict the
    549 /// expected speedup/slowdowns due to the supported instruction set. We use the
    550 /// TargetTransformInfo to query the different backends for the cost of
    551 /// different operations.
    552 class LoopVectorizationCostModel {
    553 public:
    554   LoopVectorizationCostModel(Loop *L, ScalarEvolution *SE, LoopInfo *LI,
    555                              LoopVectorizationLegality *Legal,
    556                              const TargetTransformInfo &TTI,
    557                              DataLayout *DL, const TargetLibraryInfo *TLI)
    558       : TheLoop(L), SE(SE), LI(LI), Legal(Legal), TTI(TTI), DL(DL), TLI(TLI) {}
    559 
    560   /// Information about vectorization costs
    561   struct VectorizationFactor {
    562     unsigned Width; // Vector width with best cost
    563     unsigned Cost; // Cost of the loop with that width
    564   };
    565   /// \return The most profitable vectorization factor and the cost of that VF.
    566   /// This method checks every power of two up to VF. If UserVF is not ZERO
    567   /// then this vectorization factor will be selected if vectorization is
    568   /// possible.
    569   VectorizationFactor selectVectorizationFactor(bool OptForSize,
    570                                                 unsigned UserVF);
    571 
    572   /// \return The size (in bits) of the widest type in the code that
    573   /// needs to be vectorized. We ignore values that remain scalar such as
    574   /// 64 bit loop indices.
    575   unsigned getWidestType();
    576 
    577   /// \return The most profitable unroll factor.
    578   /// If UserUF is non-zero then this method finds the best unroll-factor
    579   /// based on register pressure and other parameters.
    580   /// VF and LoopCost are the selected vectorization factor and the cost of the
    581   /// selected VF.
    582   unsigned selectUnrollFactor(bool OptForSize, unsigned UserUF, unsigned VF,
    583                               unsigned LoopCost);
    584 
    585   /// \brief A struct that represents some properties of the register usage
    586   /// of a loop.
    587   struct RegisterUsage {
    588     /// Holds the number of loop invariant values that are used in the loop.
    589     unsigned LoopInvariantRegs;
    590     /// Holds the maximum number of concurrent live intervals in the loop.
    591     unsigned MaxLocalUsers;
    592     /// Holds the number of instructions in the loop.
    593     unsigned NumInstructions;
    594   };
    595 
    596   /// \return  information about the register usage of the loop.
    597   RegisterUsage calculateRegisterUsage();
    598 
    599 private:
    600   /// Returns the expected execution cost. The unit of the cost does
    601   /// not matter because we use the 'cost' units to compare different
    602   /// vector widths. The cost that is returned is *not* normalized by
    603   /// the factor width.
    604   unsigned expectedCost(unsigned VF);
    605 
    606   /// Returns the execution time cost of an instruction for a given vector
    607   /// width. Vector width of one means scalar.
    608   unsigned getInstructionCost(Instruction *I, unsigned VF);
    609 
    610   /// A helper function for converting Scalar types to vector types.
    611   /// If the incoming type is void, we return void. If the VF is 1, we return
    612   /// the scalar type.
    613   static Type* ToVectorTy(Type *Scalar, unsigned VF);
    614 
    615   /// Returns whether the instruction is a load or store and will be a emitted
    616   /// as a vector operation.
    617   bool isConsecutiveLoadOrStore(Instruction *I);
    618 
    619   /// The loop that we evaluate.
    620   Loop *TheLoop;
    621   /// Scev analysis.
    622   ScalarEvolution *SE;
    623   /// Loop Info analysis.
    624   LoopInfo *LI;
    625   /// Vectorization legality.
    626   LoopVectorizationLegality *Legal;
    627   /// Vector target information.
    628   const TargetTransformInfo &TTI;
    629   /// Target data layout information.
    630   DataLayout *DL;
    631   /// Target Library Info.
    632   const TargetLibraryInfo *TLI;
    633 };
    634 
    635 /// The LoopVectorize Pass.
    636 struct LoopVectorize : public LoopPass {
    637   /// Pass identification, replacement for typeid
    638   static char ID;
    639 
    640   explicit LoopVectorize() : LoopPass(ID) {
    641     initializeLoopVectorizePass(*PassRegistry::getPassRegistry());
    642   }
    643 
    644   ScalarEvolution *SE;
    645   DataLayout *DL;
    646   LoopInfo *LI;
    647   TargetTransformInfo *TTI;
    648   DominatorTree *DT;
    649   AliasAnalysis *AA;
    650   TargetLibraryInfo *TLI;
    651 
    652   virtual bool runOnLoop(Loop *L, LPPassManager &LPM) {
    653     // We only vectorize innermost loops.
    654     if (!L->empty())
    655       return false;
    656 
    657     SE = &getAnalysis<ScalarEvolution>();
    658     DL = getAnalysisIfAvailable<DataLayout>();
    659     LI = &getAnalysis<LoopInfo>();
    660     TTI = &getAnalysis<TargetTransformInfo>();
    661     DT = &getAnalysis<DominatorTree>();
    662     AA = getAnalysisIfAvailable<AliasAnalysis>();
    663     TLI = getAnalysisIfAvailable<TargetLibraryInfo>();
    664 
    665     DEBUG(dbgs() << "LV: Checking a loop in \"" <<
    666           L->getHeader()->getParent()->getName() << "\"\n");
    667 
    668     // Check if it is legal to vectorize the loop.
    669     LoopVectorizationLegality LVL(L, SE, DL, DT, TTI, AA, TLI);
    670     if (!LVL.canVectorize()) {
    671       DEBUG(dbgs() << "LV: Not vectorizing.\n");
    672       return false;
    673     }
    674 
    675     // Use the cost model.
    676     LoopVectorizationCostModel CM(L, SE, LI, &LVL, *TTI, DL, TLI);
    677 
    678     // Check the function attributes to find out if this function should be
    679     // optimized for size.
    680     Function *F = L->getHeader()->getParent();
    681     Attribute::AttrKind SzAttr = Attribute::OptimizeForSize;
    682     Attribute::AttrKind FlAttr = Attribute::NoImplicitFloat;
    683     unsigned FnIndex = AttributeSet::FunctionIndex;
    684     bool OptForSize = F->getAttributes().hasAttribute(FnIndex, SzAttr);
    685     bool NoFloat = F->getAttributes().hasAttribute(FnIndex, FlAttr);
    686 
    687     if (NoFloat) {
    688       DEBUG(dbgs() << "LV: Can't vectorize when the NoImplicitFloat"
    689             "attribute is used.\n");
    690       return false;
    691     }
    692 
    693     // Select the optimal vectorization factor.
    694     LoopVectorizationCostModel::VectorizationFactor VF;
    695     VF = CM.selectVectorizationFactor(OptForSize, VectorizationFactor);
    696     // Select the unroll factor.
    697     unsigned UF = CM.selectUnrollFactor(OptForSize, VectorizationUnroll,
    698                                         VF.Width, VF.Cost);
    699 
    700     if (VF.Width == 1) {
    701       DEBUG(dbgs() << "LV: Vectorization is possible but not beneficial.\n");
    702       return false;
    703     }
    704 
    705     DEBUG(dbgs() << "LV: Found a vectorizable loop ("<< VF.Width << ") in "<<
    706           F->getParent()->getModuleIdentifier()<<"\n");
    707     DEBUG(dbgs() << "LV: Unroll Factor is " << UF << "\n");
    708 
    709     // If we decided that it is *legal* to vectorize the loop then do it.
    710     InnerLoopVectorizer LB(L, SE, LI, DT, DL, TLI, VF.Width, UF);
    711     LB.vectorize(&LVL);
    712 
    713     DEBUG(verifyFunction(*L->getHeader()->getParent()));
    714     return true;
    715   }
    716 
    717   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
    718     LoopPass::getAnalysisUsage(AU);
    719     AU.addRequiredID(LoopSimplifyID);
    720     AU.addRequiredID(LCSSAID);
    721     AU.addRequired<DominatorTree>();
    722     AU.addRequired<LoopInfo>();
    723     AU.addRequired<ScalarEvolution>();
    724     AU.addRequired<TargetTransformInfo>();
    725     AU.addPreserved<LoopInfo>();
    726     AU.addPreserved<DominatorTree>();
    727   }
    728 
    729 };
    730 
    731 } // end anonymous namespace
    732 
    733 //===----------------------------------------------------------------------===//
    734 // Implementation of LoopVectorizationLegality, InnerLoopVectorizer and
    735 // LoopVectorizationCostModel.
    736 //===----------------------------------------------------------------------===//
    737 
    738 void
    739 LoopVectorizationLegality::RuntimePointerCheck::insert(ScalarEvolution *SE,
    740                                                        Loop *Lp, Value *Ptr) {
    741   const SCEV *Sc = SE->getSCEV(Ptr);
    742   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc);
    743   assert(AR && "Invalid addrec expression");
    744   const SCEV *Ex = SE->getExitCount(Lp, Lp->getLoopLatch());
    745   const SCEV *ScEnd = AR->evaluateAtIteration(Ex, *SE);
    746   Pointers.push_back(Ptr);
    747   Starts.push_back(AR->getStart());
    748   Ends.push_back(ScEnd);
    749 }
    750 
    751 Value *InnerLoopVectorizer::getBroadcastInstrs(Value *V) {
    752   // Save the current insertion location.
    753   Instruction *Loc = Builder.GetInsertPoint();
    754 
    755   // We need to place the broadcast of invariant variables outside the loop.
    756   Instruction *Instr = dyn_cast<Instruction>(V);
    757   bool NewInstr = (Instr && Instr->getParent() == LoopVectorBody);
    758   bool Invariant = OrigLoop->isLoopInvariant(V) && !NewInstr;
    759 
    760   // Place the code for broadcasting invariant variables in the new preheader.
    761   if (Invariant)
    762     Builder.SetInsertPoint(LoopVectorPreHeader->getTerminator());
    763 
    764   // Broadcast the scalar into all locations in the vector.
    765   Value *Shuf = Builder.CreateVectorSplat(VF, V, "broadcast");
    766 
    767   // Restore the builder insertion point.
    768   if (Invariant)
    769     Builder.SetInsertPoint(Loc);
    770 
    771   return Shuf;
    772 }
    773 
    774 Value *InnerLoopVectorizer::getConsecutiveVector(Value* Val, unsigned StartIdx,
    775                                                  bool Negate) {
    776   assert(Val->getType()->isVectorTy() && "Must be a vector");
    777   assert(Val->getType()->getScalarType()->isIntegerTy() &&
    778          "Elem must be an integer");
    779   // Create the types.
    780   Type *ITy = Val->getType()->getScalarType();
    781   VectorType *Ty = cast<VectorType>(Val->getType());
    782   int VLen = Ty->getNumElements();
    783   SmallVector<Constant*, 8> Indices;
    784 
    785   // Create a vector of consecutive numbers from zero to VF.
    786   for (int i = 0; i < VLen; ++i) {
    787     int Idx = Negate ? (-i): i;
    788     Indices.push_back(ConstantInt::get(ITy, StartIdx + Idx));
    789   }
    790 
    791   // Add the consecutive indices to the vector value.
    792   Constant *Cv = ConstantVector::get(Indices);
    793   assert(Cv->getType() == Val->getType() && "Invalid consecutive vec");
    794   return Builder.CreateAdd(Val, Cv, "induction");
    795 }
    796 
    797 int LoopVectorizationLegality::isConsecutivePtr(Value *Ptr) {
    798   assert(Ptr->getType()->isPointerTy() && "Unexpected non ptr");
    799   // Make sure that the pointer does not point to structs.
    800   if (cast<PointerType>(Ptr->getType())->getElementType()->isAggregateType())
    801     return 0;
    802 
    803   // If this value is a pointer induction variable we know it is consecutive.
    804   PHINode *Phi = dyn_cast_or_null<PHINode>(Ptr);
    805   if (Phi && Inductions.count(Phi)) {
    806     InductionInfo II = Inductions[Phi];
    807     if (IK_PtrInduction == II.IK)
    808       return 1;
    809     else if (IK_ReversePtrInduction == II.IK)
    810       return -1;
    811   }
    812 
    813   GetElementPtrInst *Gep = dyn_cast_or_null<GetElementPtrInst>(Ptr);
    814   if (!Gep)
    815     return 0;
    816 
    817   unsigned NumOperands = Gep->getNumOperands();
    818   Value *LastIndex = Gep->getOperand(NumOperands - 1);
    819 
    820   Value *GpPtr = Gep->getPointerOperand();
    821   // If this GEP value is a consecutive pointer induction variable and all of
    822   // the indices are constant then we know it is consecutive. We can
    823   Phi = dyn_cast<PHINode>(GpPtr);
    824   if (Phi && Inductions.count(Phi)) {
    825 
    826     // Make sure that the pointer does not point to structs.
    827     PointerType *GepPtrType = cast<PointerType>(GpPtr->getType());
    828     if (GepPtrType->getElementType()->isAggregateType())
    829       return 0;
    830 
    831     // Make sure that all of the index operands are loop invariant.
    832     for (unsigned i = 1; i < NumOperands; ++i)
    833       if (!SE->isLoopInvariant(SE->getSCEV(Gep->getOperand(i)), TheLoop))
    834         return 0;
    835 
    836     InductionInfo II = Inductions[Phi];
    837     if (IK_PtrInduction == II.IK)
    838       return 1;
    839     else if (IK_ReversePtrInduction == II.IK)
    840       return -1;
    841   }
    842 
    843   // Check that all of the gep indices are uniform except for the last.
    844   for (unsigned i = 0; i < NumOperands - 1; ++i)
    845     if (!SE->isLoopInvariant(SE->getSCEV(Gep->getOperand(i)), TheLoop))
    846       return 0;
    847 
    848   // We can emit wide load/stores only if the last index is the induction
    849   // variable.
    850   const SCEV *Last = SE->getSCEV(LastIndex);
    851   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Last)) {
    852     const SCEV *Step = AR->getStepRecurrence(*SE);
    853 
    854     // The memory is consecutive because the last index is consecutive
    855     // and all other indices are loop invariant.
    856     if (Step->isOne())
    857       return 1;
    858     if (Step->isAllOnesValue())
    859       return -1;
    860   }
    861 
    862   return 0;
    863 }
    864 
    865 bool LoopVectorizationLegality::isUniform(Value *V) {
    866   return (SE->isLoopInvariant(SE->getSCEV(V), TheLoop));
    867 }
    868 
    869 InnerLoopVectorizer::VectorParts&
    870 InnerLoopVectorizer::getVectorValue(Value *V) {
    871   assert(V != Induction && "The new induction variable should not be used.");
    872   assert(!V->getType()->isVectorTy() && "Can't widen a vector");
    873 
    874   // If we have this scalar in the map, return it.
    875   if (WidenMap.has(V))
    876     return WidenMap.get(V);
    877 
    878   // If this scalar is unknown, assume that it is a constant or that it is
    879   // loop invariant. Broadcast V and save the value for future uses.
    880   Value *B = getBroadcastInstrs(V);
    881   return WidenMap.splat(V, B);
    882 }
    883 
    884 Value *InnerLoopVectorizer::reverseVector(Value *Vec) {
    885   assert(Vec->getType()->isVectorTy() && "Invalid type");
    886   SmallVector<Constant*, 8> ShuffleMask;
    887   for (unsigned i = 0; i < VF; ++i)
    888     ShuffleMask.push_back(Builder.getInt32(VF - i - 1));
    889 
    890   return Builder.CreateShuffleVector(Vec, UndefValue::get(Vec->getType()),
    891                                      ConstantVector::get(ShuffleMask),
    892                                      "reverse");
    893 }
    894 
    895 
    896 void InnerLoopVectorizer::vectorizeMemoryInstruction(Instruction *Instr,
    897                                              LoopVectorizationLegality *Legal) {
    898   // Attempt to issue a wide load.
    899   LoadInst *LI = dyn_cast<LoadInst>(Instr);
    900   StoreInst *SI = dyn_cast<StoreInst>(Instr);
    901 
    902   assert((LI || SI) && "Invalid Load/Store instruction");
    903 
    904   Type *ScalarDataTy = LI ? LI->getType() : SI->getValueOperand()->getType();
    905   Type *DataTy = VectorType::get(ScalarDataTy, VF);
    906   Value *Ptr = LI ? LI->getPointerOperand() : SI->getPointerOperand();
    907   unsigned Alignment = LI ? LI->getAlignment() : SI->getAlignment();
    908 
    909   // If the pointer is loop invariant or if it is non consecutive,
    910   // scalarize the load.
    911   int Stride = Legal->isConsecutivePtr(Ptr);
    912   bool Reverse = Stride < 0;
    913   bool UniformLoad = LI && Legal->isUniform(Ptr);
    914   if (Stride == 0 || UniformLoad)
    915     return scalarizeInstruction(Instr);
    916 
    917   Constant *Zero = Builder.getInt32(0);
    918   VectorParts &Entry = WidenMap.get(Instr);
    919 
    920   // Handle consecutive loads/stores.
    921   GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr);
    922   if (Gep && Legal->isInductionVariable(Gep->getPointerOperand())) {
    923     Value *PtrOperand = Gep->getPointerOperand();
    924     Value *FirstBasePtr = getVectorValue(PtrOperand)[0];
    925     FirstBasePtr = Builder.CreateExtractElement(FirstBasePtr, Zero);
    926 
    927     // Create the new GEP with the new induction variable.
    928     GetElementPtrInst *Gep2 = cast<GetElementPtrInst>(Gep->clone());
    929     Gep2->setOperand(0, FirstBasePtr);
    930     Gep2->setName("gep.indvar.base");
    931     Ptr = Builder.Insert(Gep2);
    932   } else if (Gep) {
    933     assert(SE->isLoopInvariant(SE->getSCEV(Gep->getPointerOperand()),
    934                                OrigLoop) && "Base ptr must be invariant");
    935 
    936     // The last index does not have to be the induction. It can be
    937     // consecutive and be a function of the index. For example A[I+1];
    938     unsigned NumOperands = Gep->getNumOperands();
    939 
    940     Value *LastGepOperand = Gep->getOperand(NumOperands - 1);
    941     VectorParts &GEPParts = getVectorValue(LastGepOperand);
    942     Value *LastIndex = GEPParts[0];
    943     LastIndex = Builder.CreateExtractElement(LastIndex, Zero);
    944 
    945     // Create the new GEP with the new induction variable.
    946     GetElementPtrInst *Gep2 = cast<GetElementPtrInst>(Gep->clone());
    947     Gep2->setOperand(NumOperands - 1, LastIndex);
    948     Gep2->setName("gep.indvar.idx");
    949     Ptr = Builder.Insert(Gep2);
    950   } else {
    951     // Use the induction element ptr.
    952     assert(isa<PHINode>(Ptr) && "Invalid induction ptr");
    953     VectorParts &PtrVal = getVectorValue(Ptr);
    954     Ptr = Builder.CreateExtractElement(PtrVal[0], Zero);
    955   }
    956 
    957   // Handle Stores:
    958   if (SI) {
    959     assert(!Legal->isUniform(SI->getPointerOperand()) &&
    960            "We do not allow storing to uniform addresses");
    961 
    962     VectorParts &StoredVal = getVectorValue(SI->getValueOperand());
    963     for (unsigned Part = 0; Part < UF; ++Part) {
    964       // Calculate the pointer for the specific unroll-part.
    965       Value *PartPtr = Builder.CreateGEP(Ptr, Builder.getInt32(Part * VF));
    966 
    967       if (Reverse) {
    968         // If we store to reverse consecutive memory locations then we need
    969         // to reverse the order of elements in the stored value.
    970         StoredVal[Part] = reverseVector(StoredVal[Part]);
    971         // If the address is consecutive but reversed, then the
    972         // wide store needs to start at the last vector element.
    973         PartPtr = Builder.CreateGEP(Ptr, Builder.getInt32(-Part * VF));
    974         PartPtr = Builder.CreateGEP(PartPtr, Builder.getInt32(1 - VF));
    975       }
    976 
    977       Value *VecPtr = Builder.CreateBitCast(PartPtr, DataTy->getPointerTo());
    978       Builder.CreateStore(StoredVal[Part], VecPtr)->setAlignment(Alignment);
    979     }
    980   }
    981 
    982   for (unsigned Part = 0; Part < UF; ++Part) {
    983     // Calculate the pointer for the specific unroll-part.
    984     Value *PartPtr = Builder.CreateGEP(Ptr, Builder.getInt32(Part * VF));
    985 
    986     if (Reverse) {
    987       // If the address is consecutive but reversed, then the
    988       // wide store needs to start at the last vector element.
    989       PartPtr = Builder.CreateGEP(Ptr, Builder.getInt32(-Part * VF));
    990       PartPtr = Builder.CreateGEP(PartPtr, Builder.getInt32(1 - VF));
    991     }
    992 
    993     Value *VecPtr = Builder.CreateBitCast(PartPtr, DataTy->getPointerTo());
    994     Value *LI = Builder.CreateLoad(VecPtr, "wide.load");
    995     cast<LoadInst>(LI)->setAlignment(Alignment);
    996     Entry[Part] = Reverse ? reverseVector(LI) :  LI;
    997   }
    998 }
    999 
   1000 void InnerLoopVectorizer::scalarizeInstruction(Instruction *Instr) {
   1001   assert(!Instr->getType()->isAggregateType() && "Can't handle vectors");
   1002   // Holds vector parameters or scalars, in case of uniform vals.
   1003   SmallVector<VectorParts, 4> Params;
   1004 
   1005   // Find all of the vectorized parameters.
   1006   for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) {
   1007     Value *SrcOp = Instr->getOperand(op);
   1008 
   1009     // If we are accessing the old induction variable, use the new one.
   1010     if (SrcOp == OldInduction) {
   1011       Params.push_back(getVectorValue(SrcOp));
   1012       continue;
   1013     }
   1014 
   1015     // Try using previously calculated values.
   1016     Instruction *SrcInst = dyn_cast<Instruction>(SrcOp);
   1017 
   1018     // If the src is an instruction that appeared earlier in the basic block
   1019     // then it should already be vectorized.
   1020     if (SrcInst && OrigLoop->contains(SrcInst)) {
   1021       assert(WidenMap.has(SrcInst) && "Source operand is unavailable");
   1022       // The parameter is a vector value from earlier.
   1023       Params.push_back(WidenMap.get(SrcInst));
   1024     } else {
   1025       // The parameter is a scalar from outside the loop. Maybe even a constant.
   1026       VectorParts Scalars;
   1027       Scalars.append(UF, SrcOp);
   1028       Params.push_back(Scalars);
   1029     }
   1030   }
   1031 
   1032   assert(Params.size() == Instr->getNumOperands() &&
   1033          "Invalid number of operands");
   1034 
   1035   // Does this instruction return a value ?
   1036   bool IsVoidRetTy = Instr->getType()->isVoidTy();
   1037 
   1038   Value *UndefVec = IsVoidRetTy ? 0 :
   1039     UndefValue::get(VectorType::get(Instr->getType(), VF));
   1040   // Create a new entry in the WidenMap and initialize it to Undef or Null.
   1041   VectorParts &VecResults = WidenMap.splat(Instr, UndefVec);
   1042 
   1043   // For each scalar that we create:
   1044   for (unsigned Width = 0; Width < VF; ++Width) {
   1045     // For each vector unroll 'part':
   1046     for (unsigned Part = 0; Part < UF; ++Part) {
   1047       Instruction *Cloned = Instr->clone();
   1048       if (!IsVoidRetTy)
   1049         Cloned->setName(Instr->getName() + ".cloned");
   1050       // Replace the operands of the cloned instrucions with extracted scalars.
   1051       for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) {
   1052         Value *Op = Params[op][Part];
   1053         // Param is a vector. Need to extract the right lane.
   1054         if (Op->getType()->isVectorTy())
   1055           Op = Builder.CreateExtractElement(Op, Builder.getInt32(Width));
   1056         Cloned->setOperand(op, Op);
   1057       }
   1058 
   1059       // Place the cloned scalar in the new loop.
   1060       Builder.Insert(Cloned);
   1061 
   1062       // If the original scalar returns a value we need to place it in a vector
   1063       // so that future users will be able to use it.
   1064       if (!IsVoidRetTy)
   1065         VecResults[Part] = Builder.CreateInsertElement(VecResults[Part], Cloned,
   1066                                                        Builder.getInt32(Width));
   1067     }
   1068   }
   1069 }
   1070 
   1071 Instruction *
   1072 InnerLoopVectorizer::addRuntimeCheck(LoopVectorizationLegality *Legal,
   1073                                      Instruction *Loc) {
   1074   LoopVectorizationLegality::RuntimePointerCheck *PtrRtCheck =
   1075   Legal->getRuntimePointerCheck();
   1076 
   1077   if (!PtrRtCheck->Need)
   1078     return NULL;
   1079 
   1080   Instruction *MemoryRuntimeCheck = 0;
   1081   unsigned NumPointers = PtrRtCheck->Pointers.size();
   1082   SmallVector<Value* , 2> Starts;
   1083   SmallVector<Value* , 2> Ends;
   1084 
   1085   SCEVExpander Exp(*SE, "induction");
   1086 
   1087   // Use this type for pointer arithmetic.
   1088   Type* PtrArithTy = Type::getInt8PtrTy(Loc->getContext(), 0);
   1089 
   1090   for (unsigned i = 0; i < NumPointers; ++i) {
   1091     Value *Ptr = PtrRtCheck->Pointers[i];
   1092     const SCEV *Sc = SE->getSCEV(Ptr);
   1093 
   1094     if (SE->isLoopInvariant(Sc, OrigLoop)) {
   1095       DEBUG(dbgs() << "LV: Adding RT check for a loop invariant ptr:" <<
   1096             *Ptr <<"\n");
   1097       Starts.push_back(Ptr);
   1098       Ends.push_back(Ptr);
   1099     } else {
   1100       DEBUG(dbgs() << "LV: Adding RT check for range:" << *Ptr <<"\n");
   1101 
   1102       Value *Start = Exp.expandCodeFor(PtrRtCheck->Starts[i], PtrArithTy, Loc);
   1103       Value *End = Exp.expandCodeFor(PtrRtCheck->Ends[i], PtrArithTy, Loc);
   1104       Starts.push_back(Start);
   1105       Ends.push_back(End);
   1106     }
   1107   }
   1108 
   1109   IRBuilder<> ChkBuilder(Loc);
   1110 
   1111   for (unsigned i = 0; i < NumPointers; ++i) {
   1112     for (unsigned j = i+1; j < NumPointers; ++j) {
   1113       Value *Start0 = ChkBuilder.CreateBitCast(Starts[i], PtrArithTy, "bc");
   1114       Value *Start1 = ChkBuilder.CreateBitCast(Starts[j], PtrArithTy, "bc");
   1115       Value *End0 =   ChkBuilder.CreateBitCast(Ends[i],   PtrArithTy, "bc");
   1116       Value *End1 =   ChkBuilder.CreateBitCast(Ends[j],   PtrArithTy, "bc");
   1117 
   1118       Value *Cmp0 = ChkBuilder.CreateICmpULE(Start0, End1, "bound0");
   1119       Value *Cmp1 = ChkBuilder.CreateICmpULE(Start1, End0, "bound1");
   1120       Value *IsConflict = ChkBuilder.CreateAnd(Cmp0, Cmp1, "found.conflict");
   1121       if (MemoryRuntimeCheck)
   1122         IsConflict = ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict,
   1123                                          "conflict.rdx");
   1124 
   1125       MemoryRuntimeCheck = cast<Instruction>(IsConflict);
   1126     }
   1127   }
   1128 
   1129   return MemoryRuntimeCheck;
   1130 }
   1131 
   1132 void
   1133 InnerLoopVectorizer::createEmptyLoop(LoopVectorizationLegality *Legal) {
   1134   /*
   1135    In this function we generate a new loop. The new loop will contain
   1136    the vectorized instructions while the old loop will continue to run the
   1137    scalar remainder.
   1138 
   1139        [ ] <-- vector loop bypass (may consist of multiple blocks).
   1140      /  |
   1141     /   v
   1142    |   [ ]     <-- vector pre header.
   1143    |    |
   1144    |    v
   1145    |   [  ] \
   1146    |   [  ]_|   <-- vector loop.
   1147    |    |
   1148     \   v
   1149       >[ ]   <--- middle-block.
   1150      /  |
   1151     /   v
   1152    |   [ ]     <--- new preheader.
   1153    |    |
   1154    |    v
   1155    |   [ ] \
   1156    |   [ ]_|   <-- old scalar loop to handle remainder.
   1157     \   |
   1158      \  v
   1159       >[ ]     <-- exit block.
   1160    ...
   1161    */
   1162 
   1163   BasicBlock *OldBasicBlock = OrigLoop->getHeader();
   1164   BasicBlock *BypassBlock = OrigLoop->getLoopPreheader();
   1165   BasicBlock *ExitBlock = OrigLoop->getExitBlock();
   1166   assert(ExitBlock && "Must have an exit block");
   1167 
   1168   // Mark the old scalar loop with metadata that tells us not to vectorize this
   1169   // loop again if we run into it.
   1170   MDNode *MD = MDNode::get(OldBasicBlock->getContext(), ArrayRef<Value*>());
   1171   OldBasicBlock->getTerminator()->setMetadata(AlreadyVectorizedMDName, MD);
   1172 
   1173   // Some loops have a single integer induction variable, while other loops
   1174   // don't. One example is c++ iterators that often have multiple pointer
   1175   // induction variables. In the code below we also support a case where we
   1176   // don't have a single induction variable.
   1177   OldInduction = Legal->getInduction();
   1178   Type *IdxTy = OldInduction ? OldInduction->getType() :
   1179   DL->getIntPtrType(SE->getContext());
   1180 
   1181   // Find the loop boundaries.
   1182   const SCEV *ExitCount = SE->getExitCount(OrigLoop, OrigLoop->getLoopLatch());
   1183   assert(ExitCount != SE->getCouldNotCompute() && "Invalid loop count");
   1184 
   1185   // Get the total trip count from the count by adding 1.
   1186   ExitCount = SE->getAddExpr(ExitCount,
   1187                              SE->getConstant(ExitCount->getType(), 1));
   1188 
   1189   // Expand the trip count and place the new instructions in the preheader.
   1190   // Notice that the pre-header does not change, only the loop body.
   1191   SCEVExpander Exp(*SE, "induction");
   1192 
   1193   // Count holds the overall loop count (N).
   1194   Value *Count = Exp.expandCodeFor(ExitCount, ExitCount->getType(),
   1195                                    BypassBlock->getTerminator());
   1196 
   1197   // The loop index does not have to start at Zero. Find the original start
   1198   // value from the induction PHI node. If we don't have an induction variable
   1199   // then we know that it starts at zero.
   1200   Value *StartIdx = OldInduction ?
   1201   OldInduction->getIncomingValueForBlock(BypassBlock):
   1202   ConstantInt::get(IdxTy, 0);
   1203 
   1204   assert(BypassBlock && "Invalid loop structure");
   1205   LoopBypassBlocks.push_back(BypassBlock);
   1206 
   1207   // Split the single block loop into the two loop structure described above.
   1208   BasicBlock *VectorPH =
   1209   BypassBlock->splitBasicBlock(BypassBlock->getTerminator(), "vector.ph");
   1210   BasicBlock *VecBody =
   1211   VectorPH->splitBasicBlock(VectorPH->getTerminator(), "vector.body");
   1212   BasicBlock *MiddleBlock =
   1213   VecBody->splitBasicBlock(VecBody->getTerminator(), "middle.block");
   1214   BasicBlock *ScalarPH =
   1215   MiddleBlock->splitBasicBlock(MiddleBlock->getTerminator(), "scalar.ph");
   1216 
   1217   // Use this IR builder to create the loop instructions (Phi, Br, Cmp)
   1218   // inside the loop.
   1219   Builder.SetInsertPoint(VecBody->getFirstInsertionPt());
   1220 
   1221   // Generate the induction variable.
   1222   Induction = Builder.CreatePHI(IdxTy, 2, "index");
   1223   // The loop step is equal to the vectorization factor (num of SIMD elements)
   1224   // times the unroll factor (num of SIMD instructions).
   1225   Constant *Step = ConstantInt::get(IdxTy, VF * UF);
   1226 
   1227   // This is the IR builder that we use to add all of the logic for bypassing
   1228   // the new vector loop.
   1229   IRBuilder<> BypassBuilder(BypassBlock->getTerminator());
   1230 
   1231   // We may need to extend the index in case there is a type mismatch.
   1232   // We know that the count starts at zero and does not overflow.
   1233   if (Count->getType() != IdxTy) {
   1234     // The exit count can be of pointer type. Convert it to the correct
   1235     // integer type.
   1236     if (ExitCount->getType()->isPointerTy())
   1237       Count = BypassBuilder.CreatePointerCast(Count, IdxTy, "ptrcnt.to.int");
   1238     else
   1239       Count = BypassBuilder.CreateZExtOrTrunc(Count, IdxTy, "cnt.cast");
   1240   }
   1241 
   1242   // Add the start index to the loop count to get the new end index.
   1243   Value *IdxEnd = BypassBuilder.CreateAdd(Count, StartIdx, "end.idx");
   1244 
   1245   // Now we need to generate the expression for N - (N % VF), which is
   1246   // the part that the vectorized body will execute.
   1247   Value *R = BypassBuilder.CreateURem(Count, Step, "n.mod.vf");
   1248   Value *CountRoundDown = BypassBuilder.CreateSub(Count, R, "n.vec");
   1249   Value *IdxEndRoundDown = BypassBuilder.CreateAdd(CountRoundDown, StartIdx,
   1250                                                      "end.idx.rnd.down");
   1251 
   1252   // Now, compare the new count to zero. If it is zero skip the vector loop and
   1253   // jump to the scalar loop.
   1254   Value *Cmp = BypassBuilder.CreateICmpEQ(IdxEndRoundDown, StartIdx,
   1255                                           "cmp.zero");
   1256 
   1257   BasicBlock *LastBypassBlock = BypassBlock;
   1258 
   1259   // Generate the code that checks in runtime if arrays overlap. We put the
   1260   // checks into a separate block to make the more common case of few elements
   1261   // faster.
   1262   Instruction *MemRuntimeCheck = addRuntimeCheck(Legal,
   1263                                                  BypassBlock->getTerminator());
   1264   if (MemRuntimeCheck) {
   1265     // Create a new block containing the memory check.
   1266     BasicBlock *CheckBlock = BypassBlock->splitBasicBlock(MemRuntimeCheck,
   1267                                                           "vector.memcheck");
   1268     LoopBypassBlocks.push_back(CheckBlock);
   1269 
   1270     // Replace the branch into the memory check block with a conditional branch
   1271     // for the "few elements case".
   1272     Instruction *OldTerm = BypassBlock->getTerminator();
   1273     BranchInst::Create(MiddleBlock, CheckBlock, Cmp, OldTerm);
   1274     OldTerm->eraseFromParent();
   1275 
   1276     Cmp = MemRuntimeCheck;
   1277     LastBypassBlock = CheckBlock;
   1278   }
   1279 
   1280   LastBypassBlock->getTerminator()->eraseFromParent();
   1281   BranchInst::Create(MiddleBlock, VectorPH, Cmp,
   1282                      LastBypassBlock);
   1283 
   1284   // We are going to resume the execution of the scalar loop.
   1285   // Go over all of the induction variables that we found and fix the
   1286   // PHIs that are left in the scalar version of the loop.
   1287   // The starting values of PHI nodes depend on the counter of the last
   1288   // iteration in the vectorized loop.
   1289   // If we come from a bypass edge then we need to start from the original
   1290   // start value.
   1291 
   1292   // This variable saves the new starting index for the scalar loop.
   1293   PHINode *ResumeIndex = 0;
   1294   LoopVectorizationLegality::InductionList::iterator I, E;
   1295   LoopVectorizationLegality::InductionList *List = Legal->getInductionVars();
   1296   for (I = List->begin(), E = List->end(); I != E; ++I) {
   1297     PHINode *OrigPhi = I->first;
   1298     LoopVectorizationLegality::InductionInfo II = I->second;
   1299     PHINode *ResumeVal = PHINode::Create(OrigPhi->getType(), 2, "resume.val",
   1300                                          MiddleBlock->getTerminator());
   1301     Value *EndValue = 0;
   1302     switch (II.IK) {
   1303     case LoopVectorizationLegality::IK_NoInduction:
   1304       llvm_unreachable("Unknown induction");
   1305     case LoopVectorizationLegality::IK_IntInduction: {
   1306       // Handle the integer induction counter:
   1307       assert(OrigPhi->getType()->isIntegerTy() && "Invalid type");
   1308       assert(OrigPhi == OldInduction && "Unknown integer PHI");
   1309       // We know what the end value is.
   1310       EndValue = IdxEndRoundDown;
   1311       // We also know which PHI node holds it.
   1312       ResumeIndex = ResumeVal;
   1313       break;
   1314     }
   1315     case LoopVectorizationLegality::IK_ReverseIntInduction: {
   1316       // Convert the CountRoundDown variable to the PHI size.
   1317       unsigned CRDSize = CountRoundDown->getType()->getScalarSizeInBits();
   1318       unsigned IISize = II.StartValue->getType()->getScalarSizeInBits();
   1319       Value *CRD = CountRoundDown;
   1320       if (CRDSize > IISize)
   1321         CRD = CastInst::Create(Instruction::Trunc, CountRoundDown,
   1322                                II.StartValue->getType(), "tr.crd",
   1323                                LoopBypassBlocks.back()->getTerminator());
   1324       else if (CRDSize < IISize)
   1325         CRD = CastInst::Create(Instruction::SExt, CountRoundDown,
   1326                                II.StartValue->getType(),
   1327                                "sext.crd",
   1328                                LoopBypassBlocks.back()->getTerminator());
   1329       // Handle reverse integer induction counter:
   1330       EndValue =
   1331         BinaryOperator::CreateSub(II.StartValue, CRD, "rev.ind.end",
   1332                                   LoopBypassBlocks.back()->getTerminator());
   1333       break;
   1334     }
   1335     case LoopVectorizationLegality::IK_PtrInduction: {
   1336       // For pointer induction variables, calculate the offset using
   1337       // the end index.
   1338       EndValue =
   1339         GetElementPtrInst::Create(II.StartValue, CountRoundDown, "ptr.ind.end",
   1340                                   LoopBypassBlocks.back()->getTerminator());
   1341       break;
   1342     }
   1343     case LoopVectorizationLegality::IK_ReversePtrInduction: {
   1344       // The value at the end of the loop for the reverse pointer is calculated
   1345       // by creating a GEP with a negative index starting from the start value.
   1346       Value *Zero = ConstantInt::get(CountRoundDown->getType(), 0);
   1347       Value *NegIdx = BinaryOperator::CreateSub(Zero, CountRoundDown,
   1348                                   "rev.ind.end",
   1349                                   LoopBypassBlocks.back()->getTerminator());
   1350       EndValue = GetElementPtrInst::Create(II.StartValue, NegIdx,
   1351                                   "rev.ptr.ind.end",
   1352                                   LoopBypassBlocks.back()->getTerminator());
   1353       break;
   1354     }
   1355     }// end of case
   1356 
   1357     // The new PHI merges the original incoming value, in case of a bypass,
   1358     // or the value at the end of the vectorized loop.
   1359     for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I)
   1360       ResumeVal->addIncoming(II.StartValue, LoopBypassBlocks[I]);
   1361     ResumeVal->addIncoming(EndValue, VecBody);
   1362 
   1363     // Fix the scalar body counter (PHI node).
   1364     unsigned BlockIdx = OrigPhi->getBasicBlockIndex(ScalarPH);
   1365     OrigPhi->setIncomingValue(BlockIdx, ResumeVal);
   1366   }
   1367 
   1368   // If we are generating a new induction variable then we also need to
   1369   // generate the code that calculates the exit value. This value is not
   1370   // simply the end of the counter because we may skip the vectorized body
   1371   // in case of a runtime check.
   1372   if (!OldInduction){
   1373     assert(!ResumeIndex && "Unexpected resume value found");
   1374     ResumeIndex = PHINode::Create(IdxTy, 2, "new.indc.resume.val",
   1375                                   MiddleBlock->getTerminator());
   1376     for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I)
   1377       ResumeIndex->addIncoming(StartIdx, LoopBypassBlocks[I]);
   1378     ResumeIndex->addIncoming(IdxEndRoundDown, VecBody);
   1379   }
   1380 
   1381   // Make sure that we found the index where scalar loop needs to continue.
   1382   assert(ResumeIndex && ResumeIndex->getType()->isIntegerTy() &&
   1383          "Invalid resume Index");
   1384 
   1385   // Add a check in the middle block to see if we have completed
   1386   // all of the iterations in the first vector loop.
   1387   // If (N - N%VF) == N, then we *don't* need to run the remainder.
   1388   Value *CmpN = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, IdxEnd,
   1389                                 ResumeIndex, "cmp.n",
   1390                                 MiddleBlock->getTerminator());
   1391 
   1392   BranchInst::Create(ExitBlock, ScalarPH, CmpN, MiddleBlock->getTerminator());
   1393   // Remove the old terminator.
   1394   MiddleBlock->getTerminator()->eraseFromParent();
   1395 
   1396   // Create i+1 and fill the PHINode.
   1397   Value *NextIdx = Builder.CreateAdd(Induction, Step, "index.next");
   1398   Induction->addIncoming(StartIdx, VectorPH);
   1399   Induction->addIncoming(NextIdx, VecBody);
   1400   // Create the compare.
   1401   Value *ICmp = Builder.CreateICmpEQ(NextIdx, IdxEndRoundDown);
   1402   Builder.CreateCondBr(ICmp, MiddleBlock, VecBody);
   1403 
   1404   // Now we have two terminators. Remove the old one from the block.
   1405   VecBody->getTerminator()->eraseFromParent();
   1406 
   1407   // Get ready to start creating new instructions into the vectorized body.
   1408   Builder.SetInsertPoint(VecBody->getFirstInsertionPt());
   1409 
   1410   // Create and register the new vector loop.
   1411   Loop* Lp = new Loop();
   1412   Loop *ParentLoop = OrigLoop->getParentLoop();
   1413 
   1414   // Insert the new loop into the loop nest and register the new basic blocks.
   1415   if (ParentLoop) {
   1416     ParentLoop->addChildLoop(Lp);
   1417     for (unsigned I = 1, E = LoopBypassBlocks.size(); I != E; ++I)
   1418       ParentLoop->addBasicBlockToLoop(LoopBypassBlocks[I], LI->getBase());
   1419     ParentLoop->addBasicBlockToLoop(ScalarPH, LI->getBase());
   1420     ParentLoop->addBasicBlockToLoop(VectorPH, LI->getBase());
   1421     ParentLoop->addBasicBlockToLoop(MiddleBlock, LI->getBase());
   1422   } else {
   1423     LI->addTopLevelLoop(Lp);
   1424   }
   1425 
   1426   Lp->addBasicBlockToLoop(VecBody, LI->getBase());
   1427 
   1428   // Save the state.
   1429   LoopVectorPreHeader = VectorPH;
   1430   LoopScalarPreHeader = ScalarPH;
   1431   LoopMiddleBlock = MiddleBlock;
   1432   LoopExitBlock = ExitBlock;
   1433   LoopVectorBody = VecBody;
   1434   LoopScalarBody = OldBasicBlock;
   1435 }
   1436 
   1437 /// This function returns the identity element (or neutral element) for
   1438 /// the operation K.
   1439 static Constant*
   1440 getReductionIdentity(LoopVectorizationLegality::ReductionKind K, Type *Tp) {
   1441   switch (K) {
   1442   case LoopVectorizationLegality:: RK_IntegerXor:
   1443   case LoopVectorizationLegality:: RK_IntegerAdd:
   1444   case LoopVectorizationLegality:: RK_IntegerOr:
   1445     // Adding, Xoring, Oring zero to a number does not change it.
   1446     return ConstantInt::get(Tp, 0);
   1447   case LoopVectorizationLegality:: RK_IntegerMult:
   1448     // Multiplying a number by 1 does not change it.
   1449     return ConstantInt::get(Tp, 1);
   1450   case LoopVectorizationLegality:: RK_IntegerAnd:
   1451     // AND-ing a number with an all-1 value does not change it.
   1452     return ConstantInt::get(Tp, -1, true);
   1453   case LoopVectorizationLegality:: RK_FloatMult:
   1454     // Multiplying a number by 1 does not change it.
   1455     return ConstantFP::get(Tp, 1.0L);
   1456   case LoopVectorizationLegality:: RK_FloatAdd:
   1457     // Adding zero to a number does not change it.
   1458     return ConstantFP::get(Tp, 0.0L);
   1459   default:
   1460     llvm_unreachable("Unknown reduction kind");
   1461   }
   1462 }
   1463 
   1464 static Intrinsic::ID
   1465 getIntrinsicIDForCall(CallInst *CI, const TargetLibraryInfo *TLI) {
   1466   // If we have an intrinsic call, check if it is trivially vectorizable.
   1467   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) {
   1468     switch (II->getIntrinsicID()) {
   1469     case Intrinsic::sqrt:
   1470     case Intrinsic::sin:
   1471     case Intrinsic::cos:
   1472     case Intrinsic::exp:
   1473     case Intrinsic::exp2:
   1474     case Intrinsic::log:
   1475     case Intrinsic::log10:
   1476     case Intrinsic::log2:
   1477     case Intrinsic::fabs:
   1478     case Intrinsic::floor:
   1479     case Intrinsic::ceil:
   1480     case Intrinsic::trunc:
   1481     case Intrinsic::rint:
   1482     case Intrinsic::nearbyint:
   1483     case Intrinsic::pow:
   1484     case Intrinsic::fma:
   1485     case Intrinsic::fmuladd:
   1486       return II->getIntrinsicID();
   1487     default:
   1488       return Intrinsic::not_intrinsic;
   1489     }
   1490   }
   1491 
   1492   if (!TLI)
   1493     return Intrinsic::not_intrinsic;
   1494 
   1495   LibFunc::Func Func;
   1496   Function *F = CI->getCalledFunction();
   1497   // We're going to make assumptions on the semantics of the functions, check
   1498   // that the target knows that it's available in this environment.
   1499   if (!F || !TLI->getLibFunc(F->getName(), Func))
   1500     return Intrinsic::not_intrinsic;
   1501 
   1502   // Otherwise check if we have a call to a function that can be turned into a
   1503   // vector intrinsic.
   1504   switch (Func) {
   1505   default:
   1506     break;
   1507   case LibFunc::sin:
   1508   case LibFunc::sinf:
   1509   case LibFunc::sinl:
   1510     return Intrinsic::sin;
   1511   case LibFunc::cos:
   1512   case LibFunc::cosf:
   1513   case LibFunc::cosl:
   1514     return Intrinsic::cos;
   1515   case LibFunc::exp:
   1516   case LibFunc::expf:
   1517   case LibFunc::expl:
   1518     return Intrinsic::exp;
   1519   case LibFunc::exp2:
   1520   case LibFunc::exp2f:
   1521   case LibFunc::exp2l:
   1522     return Intrinsic::exp2;
   1523   case LibFunc::log:
   1524   case LibFunc::logf:
   1525   case LibFunc::logl:
   1526     return Intrinsic::log;
   1527   case LibFunc::log10:
   1528   case LibFunc::log10f:
   1529   case LibFunc::log10l:
   1530     return Intrinsic::log10;
   1531   case LibFunc::log2:
   1532   case LibFunc::log2f:
   1533   case LibFunc::log2l:
   1534     return Intrinsic::log2;
   1535   case LibFunc::fabs:
   1536   case LibFunc::fabsf:
   1537   case LibFunc::fabsl:
   1538     return Intrinsic::fabs;
   1539   case LibFunc::floor:
   1540   case LibFunc::floorf:
   1541   case LibFunc::floorl:
   1542     return Intrinsic::floor;
   1543   case LibFunc::ceil:
   1544   case LibFunc::ceilf:
   1545   case LibFunc::ceill:
   1546     return Intrinsic::ceil;
   1547   case LibFunc::trunc:
   1548   case LibFunc::truncf:
   1549   case LibFunc::truncl:
   1550     return Intrinsic::trunc;
   1551   case LibFunc::rint:
   1552   case LibFunc::rintf:
   1553   case LibFunc::rintl:
   1554     return Intrinsic::rint;
   1555   case LibFunc::nearbyint:
   1556   case LibFunc::nearbyintf:
   1557   case LibFunc::nearbyintl:
   1558     return Intrinsic::nearbyint;
   1559   case LibFunc::pow:
   1560   case LibFunc::powf:
   1561   case LibFunc::powl:
   1562     return Intrinsic::pow;
   1563   }
   1564 
   1565   return Intrinsic::not_intrinsic;
   1566 }
   1567 
   1568 /// This function translates the reduction kind to an LLVM binary operator.
   1569 static Instruction::BinaryOps
   1570 getReductionBinOp(LoopVectorizationLegality::ReductionKind Kind) {
   1571   switch (Kind) {
   1572     case LoopVectorizationLegality::RK_IntegerAdd:
   1573       return Instruction::Add;
   1574     case LoopVectorizationLegality::RK_IntegerMult:
   1575       return Instruction::Mul;
   1576     case LoopVectorizationLegality::RK_IntegerOr:
   1577       return Instruction::Or;
   1578     case LoopVectorizationLegality::RK_IntegerAnd:
   1579       return Instruction::And;
   1580     case LoopVectorizationLegality::RK_IntegerXor:
   1581       return Instruction::Xor;
   1582     case LoopVectorizationLegality::RK_FloatMult:
   1583       return Instruction::FMul;
   1584     case LoopVectorizationLegality::RK_FloatAdd:
   1585       return Instruction::FAdd;
   1586     default:
   1587       llvm_unreachable("Unknown reduction operation");
   1588   }
   1589 }
   1590 
   1591 void
   1592 InnerLoopVectorizer::vectorizeLoop(LoopVectorizationLegality *Legal) {
   1593   //===------------------------------------------------===//
   1594   //
   1595   // Notice: any optimization or new instruction that go
   1596   // into the code below should be also be implemented in
   1597   // the cost-model.
   1598   //
   1599   //===------------------------------------------------===//
   1600   Constant *Zero = Builder.getInt32(0);
   1601 
   1602   // In order to support reduction variables we need to be able to vectorize
   1603   // Phi nodes. Phi nodes have cycles, so we need to vectorize them in two
   1604   // stages. First, we create a new vector PHI node with no incoming edges.
   1605   // We use this value when we vectorize all of the instructions that use the
   1606   // PHI. Next, after all of the instructions in the block are complete we
   1607   // add the new incoming edges to the PHI. At this point all of the
   1608   // instructions in the basic block are vectorized, so we can use them to
   1609   // construct the PHI.
   1610   PhiVector RdxPHIsToFix;
   1611 
   1612   // Scan the loop in a topological order to ensure that defs are vectorized
   1613   // before users.
   1614   LoopBlocksDFS DFS(OrigLoop);
   1615   DFS.perform(LI);
   1616 
   1617   // Vectorize all of the blocks in the original loop.
   1618   for (LoopBlocksDFS::RPOIterator bb = DFS.beginRPO(),
   1619        be = DFS.endRPO(); bb != be; ++bb)
   1620     vectorizeBlockInLoop(Legal, *bb, &RdxPHIsToFix);
   1621 
   1622   // At this point every instruction in the original loop is widened to
   1623   // a vector form. We are almost done. Now, we need to fix the PHI nodes
   1624   // that we vectorized. The PHI nodes are currently empty because we did
   1625   // not want to introduce cycles. Notice that the remaining PHI nodes
   1626   // that we need to fix are reduction variables.
   1627 
   1628   // Create the 'reduced' values for each of the induction vars.
   1629   // The reduced values are the vector values that we scalarize and combine
   1630   // after the loop is finished.
   1631   for (PhiVector::iterator it = RdxPHIsToFix.begin(), e = RdxPHIsToFix.end();
   1632        it != e; ++it) {
   1633     PHINode *RdxPhi = *it;
   1634     assert(RdxPhi && "Unable to recover vectorized PHI");
   1635 
   1636     // Find the reduction variable descriptor.
   1637     assert(Legal->getReductionVars()->count(RdxPhi) &&
   1638            "Unable to find the reduction variable");
   1639     LoopVectorizationLegality::ReductionDescriptor RdxDesc =
   1640     (*Legal->getReductionVars())[RdxPhi];
   1641 
   1642     // We need to generate a reduction vector from the incoming scalar.
   1643     // To do so, we need to generate the 'identity' vector and overide
   1644     // one of the elements with the incoming scalar reduction. We need
   1645     // to do it in the vector-loop preheader.
   1646     Builder.SetInsertPoint(LoopBypassBlocks.front()->getTerminator());
   1647 
   1648     // This is the vector-clone of the value that leaves the loop.
   1649     VectorParts &VectorExit = getVectorValue(RdxDesc.LoopExitInstr);
   1650     Type *VecTy = VectorExit[0]->getType();
   1651 
   1652     // Find the reduction identity variable. Zero for addition, or, xor,
   1653     // one for multiplication, -1 for And.
   1654     Constant *Iden = getReductionIdentity(RdxDesc.Kind, VecTy->getScalarType());
   1655     Constant *Identity = ConstantVector::getSplat(VF, Iden);
   1656 
   1657     // This vector is the Identity vector where the first element is the
   1658     // incoming scalar reduction.
   1659     Value *VectorStart = Builder.CreateInsertElement(Identity,
   1660                                                      RdxDesc.StartValue, Zero);
   1661 
   1662     // Fix the vector-loop phi.
   1663     // We created the induction variable so we know that the
   1664     // preheader is the first entry.
   1665     BasicBlock *VecPreheader = Induction->getIncomingBlock(0);
   1666 
   1667     // Reductions do not have to start at zero. They can start with
   1668     // any loop invariant values.
   1669     VectorParts &VecRdxPhi = WidenMap.get(RdxPhi);
   1670     BasicBlock *Latch = OrigLoop->getLoopLatch();
   1671     Value *LoopVal = RdxPhi->getIncomingValueForBlock(Latch);
   1672     VectorParts &Val = getVectorValue(LoopVal);
   1673     for (unsigned part = 0; part < UF; ++part) {
   1674       // Make sure to add the reduction stat value only to the
   1675       // first unroll part.
   1676       Value *StartVal = (part == 0) ? VectorStart : Identity;
   1677       cast<PHINode>(VecRdxPhi[part])->addIncoming(StartVal, VecPreheader);
   1678       cast<PHINode>(VecRdxPhi[part])->addIncoming(Val[part], LoopVectorBody);
   1679     }
   1680 
   1681     // Before each round, move the insertion point right between
   1682     // the PHIs and the values we are going to write.
   1683     // This allows us to write both PHINodes and the extractelement
   1684     // instructions.
   1685     Builder.SetInsertPoint(LoopMiddleBlock->getFirstInsertionPt());
   1686 
   1687     VectorParts RdxParts;
   1688     for (unsigned part = 0; part < UF; ++part) {
   1689       // This PHINode contains the vectorized reduction variable, or
   1690       // the initial value vector, if we bypass the vector loop.
   1691       VectorParts &RdxExitVal = getVectorValue(RdxDesc.LoopExitInstr);
   1692       PHINode *NewPhi = Builder.CreatePHI(VecTy, 2, "rdx.vec.exit.phi");
   1693       Value *StartVal = (part == 0) ? VectorStart : Identity;
   1694       for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I)
   1695         NewPhi->addIncoming(StartVal, LoopBypassBlocks[I]);
   1696       NewPhi->addIncoming(RdxExitVal[part], LoopVectorBody);
   1697       RdxParts.push_back(NewPhi);
   1698     }
   1699 
   1700     // Reduce all of the unrolled parts into a single vector.
   1701     Value *ReducedPartRdx = RdxParts[0];
   1702     for (unsigned part = 1; part < UF; ++part) {
   1703       Instruction::BinaryOps Op = getReductionBinOp(RdxDesc.Kind);
   1704       ReducedPartRdx = Builder.CreateBinOp(Op, RdxParts[part], ReducedPartRdx,
   1705                                            "bin.rdx");
   1706     }
   1707 
   1708     // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
   1709     // and vector ops, reducing the set of values being computed by half each
   1710     // round.
   1711     assert(isPowerOf2_32(VF) &&
   1712            "Reduction emission only supported for pow2 vectors!");
   1713     Value *TmpVec = ReducedPartRdx;
   1714     SmallVector<Constant*, 32> ShuffleMask(VF, 0);
   1715     for (unsigned i = VF; i != 1; i >>= 1) {
   1716       // Move the upper half of the vector to the lower half.
   1717       for (unsigned j = 0; j != i/2; ++j)
   1718         ShuffleMask[j] = Builder.getInt32(i/2 + j);
   1719 
   1720       // Fill the rest of the mask with undef.
   1721       std::fill(&ShuffleMask[i/2], ShuffleMask.end(),
   1722                 UndefValue::get(Builder.getInt32Ty()));
   1723 
   1724       Value *Shuf =
   1725         Builder.CreateShuffleVector(TmpVec,
   1726                                     UndefValue::get(TmpVec->getType()),
   1727                                     ConstantVector::get(ShuffleMask),
   1728                                     "rdx.shuf");
   1729 
   1730       Instruction::BinaryOps Op = getReductionBinOp(RdxDesc.Kind);
   1731       TmpVec = Builder.CreateBinOp(Op, TmpVec, Shuf, "bin.rdx");
   1732     }
   1733 
   1734     // The result is in the first element of the vector.
   1735     Value *Scalar0 = Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
   1736 
   1737     // Now, we need to fix the users of the reduction variable
   1738     // inside and outside of the scalar remainder loop.
   1739     // We know that the loop is in LCSSA form. We need to update the
   1740     // PHI nodes in the exit blocks.
   1741     for (BasicBlock::iterator LEI = LoopExitBlock->begin(),
   1742          LEE = LoopExitBlock->end(); LEI != LEE; ++LEI) {
   1743       PHINode *LCSSAPhi = dyn_cast<PHINode>(LEI);
   1744       if (!LCSSAPhi) continue;
   1745 
   1746       // All PHINodes need to have a single entry edge, or two if
   1747       // we already fixed them.
   1748       assert(LCSSAPhi->getNumIncomingValues() < 3 && "Invalid LCSSA PHI");
   1749 
   1750       // We found our reduction value exit-PHI. Update it with the
   1751       // incoming bypass edge.
   1752       if (LCSSAPhi->getIncomingValue(0) == RdxDesc.LoopExitInstr) {
   1753         // Add an edge coming from the bypass.
   1754         LCSSAPhi->addIncoming(Scalar0, LoopMiddleBlock);
   1755         break;
   1756       }
   1757     }// end of the LCSSA phi scan.
   1758 
   1759     // Fix the scalar loop reduction variable with the incoming reduction sum
   1760     // from the vector body and from the backedge value.
   1761     int IncomingEdgeBlockIdx =
   1762     (RdxPhi)->getBasicBlockIndex(OrigLoop->getLoopLatch());
   1763     assert(IncomingEdgeBlockIdx >= 0 && "Invalid block index");
   1764     // Pick the other block.
   1765     int SelfEdgeBlockIdx = (IncomingEdgeBlockIdx ? 0 : 1);
   1766     (RdxPhi)->setIncomingValue(SelfEdgeBlockIdx, Scalar0);
   1767     (RdxPhi)->setIncomingValue(IncomingEdgeBlockIdx, RdxDesc.LoopExitInstr);
   1768   }// end of for each redux variable.
   1769 
   1770   // The Loop exit block may have single value PHI nodes where the incoming
   1771   // value is 'undef'. While vectorizing we only handled real values that
   1772   // were defined inside the loop. Here we handle the 'undef case'.
   1773   // See PR14725.
   1774   for (BasicBlock::iterator LEI = LoopExitBlock->begin(),
   1775        LEE = LoopExitBlock->end(); LEI != LEE; ++LEI) {
   1776     PHINode *LCSSAPhi = dyn_cast<PHINode>(LEI);
   1777     if (!LCSSAPhi) continue;
   1778     if (LCSSAPhi->getNumIncomingValues() == 1)
   1779       LCSSAPhi->addIncoming(UndefValue::get(LCSSAPhi->getType()),
   1780                             LoopMiddleBlock);
   1781   }
   1782 }
   1783 
   1784 InnerLoopVectorizer::VectorParts
   1785 InnerLoopVectorizer::createEdgeMask(BasicBlock *Src, BasicBlock *Dst) {
   1786   assert(std::find(pred_begin(Dst), pred_end(Dst), Src) != pred_end(Dst) &&
   1787          "Invalid edge");
   1788 
   1789   VectorParts SrcMask = createBlockInMask(Src);
   1790 
   1791   // The terminator has to be a branch inst!
   1792   BranchInst *BI = dyn_cast<BranchInst>(Src->getTerminator());
   1793   assert(BI && "Unexpected terminator found");
   1794 
   1795   if (BI->isConditional()) {
   1796     VectorParts EdgeMask = getVectorValue(BI->getCondition());
   1797 
   1798     if (BI->getSuccessor(0) != Dst)
   1799       for (unsigned part = 0; part < UF; ++part)
   1800         EdgeMask[part] = Builder.CreateNot(EdgeMask[part]);
   1801 
   1802     for (unsigned part = 0; part < UF; ++part)
   1803       EdgeMask[part] = Builder.CreateAnd(EdgeMask[part], SrcMask[part]);
   1804     return EdgeMask;
   1805   }
   1806 
   1807   return SrcMask;
   1808 }
   1809 
   1810 InnerLoopVectorizer::VectorParts
   1811 InnerLoopVectorizer::createBlockInMask(BasicBlock *BB) {
   1812   assert(OrigLoop->contains(BB) && "Block is not a part of a loop");
   1813 
   1814   // Loop incoming mask is all-one.
   1815   if (OrigLoop->getHeader() == BB) {
   1816     Value *C = ConstantInt::get(IntegerType::getInt1Ty(BB->getContext()), 1);
   1817     return getVectorValue(C);
   1818   }
   1819 
   1820   // This is the block mask. We OR all incoming edges, and with zero.
   1821   Value *Zero = ConstantInt::get(IntegerType::getInt1Ty(BB->getContext()), 0);
   1822   VectorParts BlockMask = getVectorValue(Zero);
   1823 
   1824   // For each pred:
   1825   for (pred_iterator it = pred_begin(BB), e = pred_end(BB); it != e; ++it) {
   1826     VectorParts EM = createEdgeMask(*it, BB);
   1827     for (unsigned part = 0; part < UF; ++part)
   1828       BlockMask[part] = Builder.CreateOr(BlockMask[part], EM[part]);
   1829   }
   1830 
   1831   return BlockMask;
   1832 }
   1833 
   1834 void
   1835 InnerLoopVectorizer::vectorizeBlockInLoop(LoopVectorizationLegality *Legal,
   1836                                           BasicBlock *BB, PhiVector *PV) {
   1837   // For each instruction in the old loop.
   1838   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
   1839     VectorParts &Entry = WidenMap.get(it);
   1840     switch (it->getOpcode()) {
   1841     case Instruction::Br:
   1842       // Nothing to do for PHIs and BR, since we already took care of the
   1843       // loop control flow instructions.
   1844       continue;
   1845     case Instruction::PHI:{
   1846       PHINode* P = cast<PHINode>(it);
   1847       // Handle reduction variables:
   1848       if (Legal->getReductionVars()->count(P)) {
   1849         for (unsigned part = 0; part < UF; ++part) {
   1850           // This is phase one of vectorizing PHIs.
   1851           Type *VecTy = VectorType::get(it->getType(), VF);
   1852           Entry[part] = PHINode::Create(VecTy, 2, "vec.phi",
   1853                                         LoopVectorBody-> getFirstInsertionPt());
   1854         }
   1855         PV->push_back(P);
   1856         continue;
   1857       }
   1858 
   1859       // Check for PHI nodes that are lowered to vector selects.
   1860       if (P->getParent() != OrigLoop->getHeader()) {
   1861         // We know that all PHIs in non header blocks are converted into
   1862         // selects, so we don't have to worry about the insertion order and we
   1863         // can just use the builder.
   1864 
   1865         // At this point we generate the predication tree. There may be
   1866         // duplications since this is a simple recursive scan, but future
   1867         // optimizations will clean it up.
   1868         VectorParts Cond = createEdgeMask(P->getIncomingBlock(0),
   1869                                                P->getParent());
   1870 
   1871         for (unsigned part = 0; part < UF; ++part) {
   1872         VectorParts &In0 = getVectorValue(P->getIncomingValue(0));
   1873         VectorParts &In1 = getVectorValue(P->getIncomingValue(1));
   1874           Entry[part] = Builder.CreateSelect(Cond[part], In0[part], In1[part],
   1875                                              "predphi");
   1876         }
   1877         continue;
   1878       }
   1879 
   1880       // This PHINode must be an induction variable.
   1881       // Make sure that we know about it.
   1882       assert(Legal->getInductionVars()->count(P) &&
   1883              "Not an induction variable");
   1884 
   1885       LoopVectorizationLegality::InductionInfo II =
   1886         Legal->getInductionVars()->lookup(P);
   1887 
   1888       switch (II.IK) {
   1889       case LoopVectorizationLegality::IK_NoInduction:
   1890         llvm_unreachable("Unknown induction");
   1891       case LoopVectorizationLegality::IK_IntInduction: {
   1892         assert(P == OldInduction && "Unexpected PHI");
   1893         Value *Broadcasted = getBroadcastInstrs(Induction);
   1894         // After broadcasting the induction variable we need to make the
   1895         // vector consecutive by adding 0, 1, 2 ...
   1896         for (unsigned part = 0; part < UF; ++part)
   1897           Entry[part] = getConsecutiveVector(Broadcasted, VF * part, false);
   1898         continue;
   1899       }
   1900       case LoopVectorizationLegality::IK_ReverseIntInduction:
   1901       case LoopVectorizationLegality::IK_PtrInduction:
   1902       case LoopVectorizationLegality::IK_ReversePtrInduction:
   1903         // Handle reverse integer and pointer inductions.
   1904         Value *StartIdx = 0;
   1905         // If we have a single integer induction variable then use it.
   1906         // Otherwise, start counting at zero.
   1907         if (OldInduction) {
   1908           LoopVectorizationLegality::InductionInfo OldII =
   1909             Legal->getInductionVars()->lookup(OldInduction);
   1910           StartIdx = OldII.StartValue;
   1911         } else {
   1912           StartIdx = ConstantInt::get(Induction->getType(), 0);
   1913         }
   1914         // This is the normalized GEP that starts counting at zero.
   1915         Value *NormalizedIdx = Builder.CreateSub(Induction, StartIdx,
   1916                                                  "normalized.idx");
   1917 
   1918         // Handle the reverse integer induction variable case.
   1919         if (LoopVectorizationLegality::IK_ReverseIntInduction == II.IK) {
   1920           IntegerType *DstTy = cast<IntegerType>(II.StartValue->getType());
   1921           Value *CNI = Builder.CreateSExtOrTrunc(NormalizedIdx, DstTy,
   1922                                                  "resize.norm.idx");
   1923           Value *ReverseInd  = Builder.CreateSub(II.StartValue, CNI,
   1924                                                  "reverse.idx");
   1925 
   1926           // This is a new value so do not hoist it out.
   1927           Value *Broadcasted = getBroadcastInstrs(ReverseInd);
   1928           // After broadcasting the induction variable we need to make the
   1929           // vector consecutive by adding  ... -3, -2, -1, 0.
   1930           for (unsigned part = 0; part < UF; ++part)
   1931             Entry[part] = getConsecutiveVector(Broadcasted, -VF * part, true);
   1932           continue;
   1933         }
   1934 
   1935         // Handle the pointer induction variable case.
   1936         assert(P->getType()->isPointerTy() && "Unexpected type.");
   1937 
   1938         // Is this a reverse induction ptr or a consecutive induction ptr.
   1939         bool Reverse = (LoopVectorizationLegality::IK_ReversePtrInduction ==
   1940                         II.IK);
   1941 
   1942         // This is the vector of results. Notice that we don't generate
   1943         // vector geps because scalar geps result in better code.
   1944         for (unsigned part = 0; part < UF; ++part) {
   1945           Value *VecVal = UndefValue::get(VectorType::get(P->getType(), VF));
   1946           for (unsigned int i = 0; i < VF; ++i) {
   1947             int EltIndex = (i + part * VF) * (Reverse ? -1 : 1);
   1948             Constant *Idx = ConstantInt::get(Induction->getType(), EltIndex);
   1949             Value *GlobalIdx;
   1950             if (!Reverse)
   1951               GlobalIdx = Builder.CreateAdd(NormalizedIdx, Idx, "gep.idx");
   1952             else
   1953               GlobalIdx = Builder.CreateSub(Idx, NormalizedIdx, "gep.ridx");
   1954 
   1955             Value *SclrGep = Builder.CreateGEP(II.StartValue, GlobalIdx,
   1956                                                "next.gep");
   1957             VecVal = Builder.CreateInsertElement(VecVal, SclrGep,
   1958                                                  Builder.getInt32(i),
   1959                                                  "insert.gep");
   1960           }
   1961           Entry[part] = VecVal;
   1962         }
   1963         continue;
   1964       }
   1965 
   1966     }// End of PHI.
   1967 
   1968     case Instruction::Add:
   1969     case Instruction::FAdd:
   1970     case Instruction::Sub:
   1971     case Instruction::FSub:
   1972     case Instruction::Mul:
   1973     case Instruction::FMul:
   1974     case Instruction::UDiv:
   1975     case Instruction::SDiv:
   1976     case Instruction::FDiv:
   1977     case Instruction::URem:
   1978     case Instruction::SRem:
   1979     case Instruction::FRem:
   1980     case Instruction::Shl:
   1981     case Instruction::LShr:
   1982     case Instruction::AShr:
   1983     case Instruction::And:
   1984     case Instruction::Or:
   1985     case Instruction::Xor: {
   1986       // Just widen binops.
   1987       BinaryOperator *BinOp = dyn_cast<BinaryOperator>(it);
   1988       VectorParts &A = getVectorValue(it->getOperand(0));
   1989       VectorParts &B = getVectorValue(it->getOperand(1));
   1990 
   1991       // Use this vector value for all users of the original instruction.
   1992       for (unsigned Part = 0; Part < UF; ++Part) {
   1993         Value *V = Builder.CreateBinOp(BinOp->getOpcode(), A[Part], B[Part]);
   1994 
   1995         // Update the NSW, NUW and Exact flags. Notice: V can be an Undef.
   1996         BinaryOperator *VecOp = dyn_cast<BinaryOperator>(V);
   1997         if (VecOp && isa<OverflowingBinaryOperator>(BinOp)) {
   1998           VecOp->setHasNoSignedWrap(BinOp->hasNoSignedWrap());
   1999           VecOp->setHasNoUnsignedWrap(BinOp->hasNoUnsignedWrap());
   2000         }
   2001         if (VecOp && isa<PossiblyExactOperator>(VecOp))
   2002           VecOp->setIsExact(BinOp->isExact());
   2003 
   2004         Entry[Part] = V;
   2005       }
   2006       break;
   2007     }
   2008     case Instruction::Select: {
   2009       // Widen selects.
   2010       // If the selector is loop invariant we can create a select
   2011       // instruction with a scalar condition. Otherwise, use vector-select.
   2012       bool InvariantCond = SE->isLoopInvariant(SE->getSCEV(it->getOperand(0)),
   2013                                                OrigLoop);
   2014 
   2015       // The condition can be loop invariant  but still defined inside the
   2016       // loop. This means that we can't just use the original 'cond' value.
   2017       // We have to take the 'vectorized' value and pick the first lane.
   2018       // Instcombine will make this a no-op.
   2019       VectorParts &Cond = getVectorValue(it->getOperand(0));
   2020       VectorParts &Op0  = getVectorValue(it->getOperand(1));
   2021       VectorParts &Op1  = getVectorValue(it->getOperand(2));
   2022       Value *ScalarCond = Builder.CreateExtractElement(Cond[0],
   2023                                                        Builder.getInt32(0));
   2024       for (unsigned Part = 0; Part < UF; ++Part) {
   2025         Entry[Part] = Builder.CreateSelect(
   2026           InvariantCond ? ScalarCond : Cond[Part],
   2027           Op0[Part],
   2028           Op1[Part]);
   2029       }
   2030       break;
   2031     }
   2032 
   2033     case Instruction::ICmp:
   2034     case Instruction::FCmp: {
   2035       // Widen compares. Generate vector compares.
   2036       bool FCmp = (it->getOpcode() == Instruction::FCmp);
   2037       CmpInst *Cmp = dyn_cast<CmpInst>(it);
   2038       VectorParts &A = getVectorValue(it->getOperand(0));
   2039       VectorParts &B = getVectorValue(it->getOperand(1));
   2040       for (unsigned Part = 0; Part < UF; ++Part) {
   2041         Value *C = 0;
   2042         if (FCmp)
   2043           C = Builder.CreateFCmp(Cmp->getPredicate(), A[Part], B[Part]);
   2044         else
   2045           C = Builder.CreateICmp(Cmp->getPredicate(), A[Part], B[Part]);
   2046         Entry[Part] = C;
   2047       }
   2048       break;
   2049     }
   2050 
   2051     case Instruction::Store:
   2052     case Instruction::Load:
   2053         vectorizeMemoryInstruction(it, Legal);
   2054         break;
   2055     case Instruction::ZExt:
   2056     case Instruction::SExt:
   2057     case Instruction::FPToUI:
   2058     case Instruction::FPToSI:
   2059     case Instruction::FPExt:
   2060     case Instruction::PtrToInt:
   2061     case Instruction::IntToPtr:
   2062     case Instruction::SIToFP:
   2063     case Instruction::UIToFP:
   2064     case Instruction::Trunc:
   2065     case Instruction::FPTrunc:
   2066     case Instruction::BitCast: {
   2067       CastInst *CI = dyn_cast<CastInst>(it);
   2068       /// Optimize the special case where the source is the induction
   2069       /// variable. Notice that we can only optimize the 'trunc' case
   2070       /// because: a. FP conversions lose precision, b. sext/zext may wrap,
   2071       /// c. other casts depend on pointer size.
   2072       if (CI->getOperand(0) == OldInduction &&
   2073           it->getOpcode() == Instruction::Trunc) {
   2074         Value *ScalarCast = Builder.CreateCast(CI->getOpcode(), Induction,
   2075                                                CI->getType());
   2076         Value *Broadcasted = getBroadcastInstrs(ScalarCast);
   2077         for (unsigned Part = 0; Part < UF; ++Part)
   2078           Entry[Part] = getConsecutiveVector(Broadcasted, VF * Part, false);
   2079         break;
   2080       }
   2081       /// Vectorize casts.
   2082       Type *DestTy = VectorType::get(CI->getType()->getScalarType(), VF);
   2083 
   2084       VectorParts &A = getVectorValue(it->getOperand(0));
   2085       for (unsigned Part = 0; Part < UF; ++Part)
   2086         Entry[Part] = Builder.CreateCast(CI->getOpcode(), A[Part], DestTy);
   2087       break;
   2088     }
   2089 
   2090     case Instruction::Call: {
   2091       // Ignore dbg intrinsics.
   2092       if (isa<DbgInfoIntrinsic>(it))
   2093         break;
   2094 
   2095       Module *M = BB->getParent()->getParent();
   2096       CallInst *CI = cast<CallInst>(it);
   2097       Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
   2098       assert(ID && "Not an intrinsic call!");
   2099       for (unsigned Part = 0; Part < UF; ++Part) {
   2100         SmallVector<Value*, 4> Args;
   2101         for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i) {
   2102           VectorParts &Arg = getVectorValue(CI->getArgOperand(i));
   2103           Args.push_back(Arg[Part]);
   2104         }
   2105         Type *Tys[] = { VectorType::get(CI->getType()->getScalarType(), VF) };
   2106         Function *F = Intrinsic::getDeclaration(M, ID, Tys);
   2107         Entry[Part] = Builder.CreateCall(F, Args);
   2108       }
   2109       break;
   2110     }
   2111 
   2112     default:
   2113       // All other instructions are unsupported. Scalarize them.
   2114       scalarizeInstruction(it);
   2115       break;
   2116     }// end of switch.
   2117   }// end of for_each instr.
   2118 }
   2119 
   2120 void InnerLoopVectorizer::updateAnalysis() {
   2121   // Forget the original basic block.
   2122   SE->forgetLoop(OrigLoop);
   2123 
   2124   // Update the dominator tree information.
   2125   assert(DT->properlyDominates(LoopBypassBlocks.front(), LoopExitBlock) &&
   2126          "Entry does not dominate exit.");
   2127 
   2128   for (unsigned I = 1, E = LoopBypassBlocks.size(); I != E; ++I)
   2129     DT->addNewBlock(LoopBypassBlocks[I], LoopBypassBlocks[I-1]);
   2130   DT->addNewBlock(LoopVectorPreHeader, LoopBypassBlocks.back());
   2131   DT->addNewBlock(LoopVectorBody, LoopVectorPreHeader);
   2132   DT->addNewBlock(LoopMiddleBlock, LoopBypassBlocks.front());
   2133   DT->addNewBlock(LoopScalarPreHeader, LoopMiddleBlock);
   2134   DT->changeImmediateDominator(LoopScalarBody, LoopScalarPreHeader);
   2135   DT->changeImmediateDominator(LoopExitBlock, LoopMiddleBlock);
   2136 
   2137   DEBUG(DT->verifyAnalysis());
   2138 }
   2139 
   2140 bool LoopVectorizationLegality::canVectorizeWithIfConvert() {
   2141   if (!EnableIfConversion)
   2142     return false;
   2143 
   2144   assert(TheLoop->getNumBlocks() > 1 && "Single block loops are vectorizable");
   2145   std::vector<BasicBlock*> &LoopBlocks = TheLoop->getBlocksVector();
   2146 
   2147   // Collect the blocks that need predication.
   2148   for (unsigned i = 0, e = LoopBlocks.size(); i < e; ++i) {
   2149     BasicBlock *BB = LoopBlocks[i];
   2150 
   2151     // We don't support switch statements inside loops.
   2152     if (!isa<BranchInst>(BB->getTerminator()))
   2153       return false;
   2154 
   2155     // We must have at most two predecessors because we need to convert
   2156     // all PHIs to selects.
   2157     unsigned Preds = std::distance(pred_begin(BB), pred_end(BB));
   2158     if (Preds > 2)
   2159       return false;
   2160 
   2161     // We must be able to predicate all blocks that need to be predicated.
   2162     if (blockNeedsPredication(BB) && !blockCanBePredicated(BB))
   2163       return false;
   2164   }
   2165 
   2166   // We can if-convert this loop.
   2167   return true;
   2168 }
   2169 
   2170 bool LoopVectorizationLegality::canVectorize() {
   2171   assert(TheLoop->getLoopPreheader() && "No preheader!!");
   2172 
   2173   // We can only vectorize innermost loops.
   2174   if (TheLoop->getSubLoopsVector().size())
   2175     return false;
   2176 
   2177   // We must have a single backedge.
   2178   if (TheLoop->getNumBackEdges() != 1)
   2179     return false;
   2180 
   2181   // We must have a single exiting block.
   2182   if (!TheLoop->getExitingBlock())
   2183     return false;
   2184 
   2185   unsigned NumBlocks = TheLoop->getNumBlocks();
   2186 
   2187   // Check if we can if-convert non single-bb loops.
   2188   if (NumBlocks != 1 && !canVectorizeWithIfConvert()) {
   2189     DEBUG(dbgs() << "LV: Can't if-convert the loop.\n");
   2190     return false;
   2191   }
   2192 
   2193   // We need to have a loop header.
   2194   BasicBlock *Latch = TheLoop->getLoopLatch();
   2195   DEBUG(dbgs() << "LV: Found a loop: " <<
   2196         TheLoop->getHeader()->getName() << "\n");
   2197 
   2198   // ScalarEvolution needs to be able to find the exit count.
   2199   const SCEV *ExitCount = SE->getExitCount(TheLoop, Latch);
   2200   if (ExitCount == SE->getCouldNotCompute()) {
   2201     DEBUG(dbgs() << "LV: SCEV could not compute the loop exit count.\n");
   2202     return false;
   2203   }
   2204 
   2205   // Do not loop-vectorize loops with a tiny trip count.
   2206   unsigned TC = SE->getSmallConstantTripCount(TheLoop, Latch);
   2207   if (TC > 0u && TC < TinyTripCountVectorThreshold) {
   2208     DEBUG(dbgs() << "LV: Found a loop with a very small trip count. " <<
   2209           "This loop is not worth vectorizing.\n");
   2210     return false;
   2211   }
   2212 
   2213   // Check if we can vectorize the instructions and CFG in this loop.
   2214   if (!canVectorizeInstrs()) {
   2215     DEBUG(dbgs() << "LV: Can't vectorize the instructions or CFG\n");
   2216     return false;
   2217   }
   2218 
   2219   // Go over each instruction and look at memory deps.
   2220   if (!canVectorizeMemory()) {
   2221     DEBUG(dbgs() << "LV: Can't vectorize due to memory conflicts\n");
   2222     return false;
   2223   }
   2224 
   2225   // Collect all of the variables that remain uniform after vectorization.
   2226   collectLoopUniforms();
   2227 
   2228   DEBUG(dbgs() << "LV: We can vectorize this loop" <<
   2229         (PtrRtCheck.Need ? " (with a runtime bound check)" : "")
   2230         <<"!\n");
   2231 
   2232   // Okay! We can vectorize. At this point we don't have any other mem analysis
   2233   // which may limit our maximum vectorization factor, so just return true with
   2234   // no restrictions.
   2235   return true;
   2236 }
   2237 
   2238 bool LoopVectorizationLegality::canVectorizeInstrs() {
   2239   BasicBlock *PreHeader = TheLoop->getLoopPreheader();
   2240   BasicBlock *Header = TheLoop->getHeader();
   2241 
   2242   // If we marked the scalar loop as "already vectorized" then no need
   2243   // to vectorize it again.
   2244   if (Header->getTerminator()->getMetadata(AlreadyVectorizedMDName)) {
   2245     DEBUG(dbgs() << "LV: This loop was vectorized before\n");
   2246     return false;
   2247   }
   2248 
   2249   // For each block in the loop.
   2250   for (Loop::block_iterator bb = TheLoop->block_begin(),
   2251        be = TheLoop->block_end(); bb != be; ++bb) {
   2252 
   2253     // Scan the instructions in the block and look for hazards.
   2254     for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
   2255          ++it) {
   2256 
   2257       if (PHINode *Phi = dyn_cast<PHINode>(it)) {
   2258         // This should not happen because the loop should be normalized.
   2259         if (Phi->getNumIncomingValues() != 2) {
   2260           DEBUG(dbgs() << "LV: Found an invalid PHI.\n");
   2261           return false;
   2262         }
   2263 
   2264         // Check that this PHI type is allowed.
   2265         if (!Phi->getType()->isIntegerTy() &&
   2266             !Phi->getType()->isFloatingPointTy() &&
   2267             !Phi->getType()->isPointerTy()) {
   2268           DEBUG(dbgs() << "LV: Found an non-int non-pointer PHI.\n");
   2269           return false;
   2270         }
   2271 
   2272         // If this PHINode is not in the header block, then we know that we
   2273         // can convert it to select during if-conversion. No need to check if
   2274         // the PHIs in this block are induction or reduction variables.
   2275         if (*bb != Header)
   2276           continue;
   2277 
   2278         // This is the value coming from the preheader.
   2279         Value *StartValue = Phi->getIncomingValueForBlock(PreHeader);
   2280         // Check if this is an induction variable.
   2281         InductionKind IK = isInductionVariable(Phi);
   2282 
   2283         if (IK_NoInduction != IK) {
   2284           // Int inductions are special because we only allow one IV.
   2285           if (IK == IK_IntInduction) {
   2286             if (Induction) {
   2287               DEBUG(dbgs() << "LV: Found too many inductions."<< *Phi <<"\n");
   2288               return false;
   2289             }
   2290             Induction = Phi;
   2291           }
   2292 
   2293           DEBUG(dbgs() << "LV: Found an induction variable.\n");
   2294           Inductions[Phi] = InductionInfo(StartValue, IK);
   2295           continue;
   2296         }
   2297 
   2298         if (AddReductionVar(Phi, RK_IntegerAdd)) {
   2299           DEBUG(dbgs() << "LV: Found an ADD reduction PHI."<< *Phi <<"\n");
   2300           continue;
   2301         }
   2302         if (AddReductionVar(Phi, RK_IntegerMult)) {
   2303           DEBUG(dbgs() << "LV: Found a MUL reduction PHI."<< *Phi <<"\n");
   2304           continue;
   2305         }
   2306         if (AddReductionVar(Phi, RK_IntegerOr)) {
   2307           DEBUG(dbgs() << "LV: Found an OR reduction PHI."<< *Phi <<"\n");
   2308           continue;
   2309         }
   2310         if (AddReductionVar(Phi, RK_IntegerAnd)) {
   2311           DEBUG(dbgs() << "LV: Found an AND reduction PHI."<< *Phi <<"\n");
   2312           continue;
   2313         }
   2314         if (AddReductionVar(Phi, RK_IntegerXor)) {
   2315           DEBUG(dbgs() << "LV: Found a XOR reduction PHI."<< *Phi <<"\n");
   2316           continue;
   2317         }
   2318         if (AddReductionVar(Phi, RK_FloatMult)) {
   2319           DEBUG(dbgs() << "LV: Found an FMult reduction PHI."<< *Phi <<"\n");
   2320           continue;
   2321         }
   2322         if (AddReductionVar(Phi, RK_FloatAdd)) {
   2323           DEBUG(dbgs() << "LV: Found an FAdd reduction PHI."<< *Phi <<"\n");
   2324           continue;
   2325         }
   2326 
   2327         DEBUG(dbgs() << "LV: Found an unidentified PHI."<< *Phi <<"\n");
   2328         return false;
   2329       }// end of PHI handling
   2330 
   2331       // We still don't handle functions. However, we can ignore dbg intrinsic
   2332       // calls and we do handle certain intrinsic and libm functions.
   2333       CallInst *CI = dyn_cast<CallInst>(it);
   2334       if (CI && !getIntrinsicIDForCall(CI, TLI) && !isa<DbgInfoIntrinsic>(CI)) {
   2335         DEBUG(dbgs() << "LV: Found a call site.\n");
   2336         return false;
   2337       }
   2338 
   2339       // Check that the instruction return type is vectorizable.
   2340       if (!VectorType::isValidElementType(it->getType()) &&
   2341           !it->getType()->isVoidTy()) {
   2342         DEBUG(dbgs() << "LV: Found unvectorizable type." << "\n");
   2343         return false;
   2344       }
   2345 
   2346       // Check that the stored type is vectorizable.
   2347       if (StoreInst *ST = dyn_cast<StoreInst>(it)) {
   2348         Type *T = ST->getValueOperand()->getType();
   2349         if (!VectorType::isValidElementType(T))
   2350           return false;
   2351       }
   2352 
   2353       // Reduction instructions are allowed to have exit users.
   2354       // All other instructions must not have external users.
   2355       if (!AllowedExit.count(it))
   2356         //Check that all of the users of the loop are inside the BB.
   2357         for (Value::use_iterator I = it->use_begin(), E = it->use_end();
   2358              I != E; ++I) {
   2359           Instruction *U = cast<Instruction>(*I);
   2360           // This user may be a reduction exit value.
   2361           if (!TheLoop->contains(U)) {
   2362             DEBUG(dbgs() << "LV: Found an outside user for : "<< *U << "\n");
   2363             return false;
   2364           }
   2365         }
   2366     } // next instr.
   2367 
   2368   }
   2369 
   2370   if (!Induction) {
   2371     DEBUG(dbgs() << "LV: Did not find one integer induction var.\n");
   2372     assert(getInductionVars()->size() && "No induction variables");
   2373   }
   2374 
   2375   return true;
   2376 }
   2377 
   2378 void LoopVectorizationLegality::collectLoopUniforms() {
   2379   // We now know that the loop is vectorizable!
   2380   // Collect variables that will remain uniform after vectorization.
   2381   std::vector<Value*> Worklist;
   2382   BasicBlock *Latch = TheLoop->getLoopLatch();
   2383 
   2384   // Start with the conditional branch and walk up the block.
   2385   Worklist.push_back(Latch->getTerminator()->getOperand(0));
   2386 
   2387   while (Worklist.size()) {
   2388     Instruction *I = dyn_cast<Instruction>(Worklist.back());
   2389     Worklist.pop_back();
   2390 
   2391     // Look at instructions inside this loop.
   2392     // Stop when reaching PHI nodes.
   2393     // TODO: we need to follow values all over the loop, not only in this block.
   2394     if (!I || !TheLoop->contains(I) || isa<PHINode>(I))
   2395       continue;
   2396 
   2397     // This is a known uniform.
   2398     Uniforms.insert(I);
   2399 
   2400     // Insert all operands.
   2401     for (int i = 0, Op = I->getNumOperands(); i < Op; ++i) {
   2402       Worklist.push_back(I->getOperand(i));
   2403     }
   2404   }
   2405 }
   2406 
   2407 AliasAnalysis::Location
   2408 LoopVectorizationLegality::getLoadStoreLocation(Instruction *Inst) {
   2409   if (StoreInst *Store = dyn_cast<StoreInst>(Inst))
   2410     return AA->getLocation(Store);
   2411   else if (LoadInst *Load = dyn_cast<LoadInst>(Inst))
   2412     return AA->getLocation(Load);
   2413 
   2414   llvm_unreachable("Should be either load or store instruction");
   2415 }
   2416 
   2417 bool
   2418 LoopVectorizationLegality::hasPossibleGlobalWriteReorder(
   2419                                                 Value *Object,
   2420                                                 Instruction *Inst,
   2421                                                 AliasMultiMap& WriteObjects,
   2422                                                 unsigned MaxByteWidth) {
   2423 
   2424   AliasAnalysis::Location ThisLoc = getLoadStoreLocation(Inst);
   2425 
   2426   std::vector<Instruction*>::iterator
   2427               it = WriteObjects[Object].begin(),
   2428               end = WriteObjects[Object].end();
   2429 
   2430   for (; it != end; ++it) {
   2431     Instruction* I = *it;
   2432     if (I == Inst)
   2433       continue;
   2434 
   2435     AliasAnalysis::Location ThatLoc = getLoadStoreLocation(I);
   2436     if (AA->alias(ThisLoc.getWithNewSize(MaxByteWidth),
   2437                   ThatLoc.getWithNewSize(MaxByteWidth)))
   2438       return true;
   2439   }
   2440   return false;
   2441 }
   2442 
   2443 bool LoopVectorizationLegality::canVectorizeMemory() {
   2444 
   2445   if (TheLoop->isAnnotatedParallel()) {
   2446     DEBUG(dbgs()
   2447           << "LV: A loop annotated parallel, ignore memory dependency "
   2448           << "checks.\n");
   2449     return true;
   2450   }
   2451 
   2452   typedef SmallVector<Value*, 16> ValueVector;
   2453   typedef SmallPtrSet<Value*, 16> ValueSet;
   2454   // Holds the Load and Store *instructions*.
   2455   ValueVector Loads;
   2456   ValueVector Stores;
   2457   PtrRtCheck.Pointers.clear();
   2458   PtrRtCheck.Need = false;
   2459 
   2460   // For each block.
   2461   for (Loop::block_iterator bb = TheLoop->block_begin(),
   2462        be = TheLoop->block_end(); bb != be; ++bb) {
   2463 
   2464     // Scan the BB and collect legal loads and stores.
   2465     for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
   2466          ++it) {
   2467 
   2468       // If this is a load, save it. If this instruction can read from memory
   2469       // but is not a load, then we quit. Notice that we don't handle function
   2470       // calls that read or write.
   2471       if (it->mayReadFromMemory()) {
   2472         LoadInst *Ld = dyn_cast<LoadInst>(it);
   2473         if (!Ld) return false;
   2474         if (!Ld->isSimple()) {
   2475           DEBUG(dbgs() << "LV: Found a non-simple load.\n");
   2476           return false;
   2477         }
   2478         Loads.push_back(Ld);
   2479         continue;
   2480       }
   2481 
   2482       // Save 'store' instructions. Abort if other instructions write to memory.
   2483       if (it->mayWriteToMemory()) {
   2484         StoreInst *St = dyn_cast<StoreInst>(it);
   2485         if (!St) return false;
   2486         if (!St->isSimple()) {
   2487           DEBUG(dbgs() << "LV: Found a non-simple store.\n");
   2488           return false;
   2489         }
   2490         Stores.push_back(St);
   2491       }
   2492     } // next instr.
   2493   } // next block.
   2494 
   2495   // Now we have two lists that hold the loads and the stores.
   2496   // Next, we find the pointers that they use.
   2497 
   2498   // Check if we see any stores. If there are no stores, then we don't
   2499   // care if the pointers are *restrict*.
   2500   if (!Stores.size()) {
   2501     DEBUG(dbgs() << "LV: Found a read-only loop!\n");
   2502     return true;
   2503   }
   2504 
   2505   // Holds the read and read-write *pointers* that we find. These maps hold
   2506   // unique values for pointers (so no need for multi-map).
   2507   AliasMap Reads;
   2508   AliasMap ReadWrites;
   2509 
   2510   // Holds the analyzed pointers. We don't want to call GetUnderlyingObjects
   2511   // multiple times on the same object. If the ptr is accessed twice, once
   2512   // for read and once for write, it will only appear once (on the write
   2513   // list). This is okay, since we are going to check for conflicts between
   2514   // writes and between reads and writes, but not between reads and reads.
   2515   ValueSet Seen;
   2516 
   2517   ValueVector::iterator I, IE;
   2518   for (I = Stores.begin(), IE = Stores.end(); I != IE; ++I) {
   2519     StoreInst *ST = cast<StoreInst>(*I);
   2520     Value* Ptr = ST->getPointerOperand();
   2521 
   2522     if (isUniform(Ptr)) {
   2523       DEBUG(dbgs() << "LV: We don't allow storing to uniform addresses\n");
   2524       return false;
   2525     }
   2526 
   2527     // If we did *not* see this pointer before, insert it to
   2528     // the read-write list. At this phase it is only a 'write' list.
   2529     if (Seen.insert(Ptr))
   2530       ReadWrites.insert(std::make_pair(Ptr, ST));
   2531   }
   2532 
   2533   for (I = Loads.begin(), IE = Loads.end(); I != IE; ++I) {
   2534     LoadInst *LD = cast<LoadInst>(*I);
   2535     Value* Ptr = LD->getPointerOperand();
   2536     // If we did *not* see this pointer before, insert it to the
   2537     // read list. If we *did* see it before, then it is already in
   2538     // the read-write list. This allows us to vectorize expressions
   2539     // such as A[i] += x;  Because the address of A[i] is a read-write
   2540     // pointer. This only works if the index of A[i] is consecutive.
   2541     // If the address of i is unknown (for example A[B[i]]) then we may
   2542     // read a few words, modify, and write a few words, and some of the
   2543     // words may be written to the same address.
   2544     if (Seen.insert(Ptr) || 0 == isConsecutivePtr(Ptr))
   2545       Reads.insert(std::make_pair(Ptr, LD));
   2546   }
   2547 
   2548   // If we write (or read-write) to a single destination and there are no
   2549   // other reads in this loop then is it safe to vectorize.
   2550   if (ReadWrites.size() == 1 && Reads.size() == 0) {
   2551     DEBUG(dbgs() << "LV: Found a write-only loop!\n");
   2552     return true;
   2553   }
   2554 
   2555   // Find pointers with computable bounds. We are going to use this information
   2556   // to place a runtime bound check.
   2557   bool CanDoRT = true;
   2558   AliasMap::iterator MI, ME;
   2559   for (MI = ReadWrites.begin(), ME = ReadWrites.end(); MI != ME; ++MI) {
   2560     Value *V = (*MI).first;
   2561     if (hasComputableBounds(V)) {
   2562       PtrRtCheck.insert(SE, TheLoop, V);
   2563       DEBUG(dbgs() << "LV: Found a runtime check ptr:" << *V <<"\n");
   2564     } else {
   2565       CanDoRT = false;
   2566       break;
   2567     }
   2568   }
   2569   for (MI = Reads.begin(), ME = Reads.end(); MI != ME; ++MI) {
   2570     Value *V = (*MI).first;
   2571     if (hasComputableBounds(V)) {
   2572       PtrRtCheck.insert(SE, TheLoop, V);
   2573       DEBUG(dbgs() << "LV: Found a runtime check ptr:" << *V <<"\n");
   2574     } else {
   2575       CanDoRT = false;
   2576       break;
   2577     }
   2578   }
   2579 
   2580   // Check that we did not collect too many pointers or found a
   2581   // unsizeable pointer.
   2582   if (!CanDoRT || PtrRtCheck.Pointers.size() > RuntimeMemoryCheckThreshold) {
   2583     PtrRtCheck.reset();
   2584     CanDoRT = false;
   2585   }
   2586 
   2587   if (CanDoRT) {
   2588     DEBUG(dbgs() << "LV: We can perform a memory runtime check if needed.\n");
   2589   }
   2590 
   2591   bool NeedRTCheck = false;
   2592 
   2593   // Biggest vectorized access possible, vector width * unroll factor.
   2594   // TODO: We're being very pessimistic here, find a way to know the
   2595   // real access width before getting here.
   2596   unsigned MaxByteWidth = (TTI->getRegisterBitWidth(true) / 8) *
   2597                            TTI->getMaximumUnrollFactor();
   2598   // Now that the pointers are in two lists (Reads and ReadWrites), we
   2599   // can check that there are no conflicts between each of the writes and
   2600   // between the writes to the reads.
   2601   // Note that WriteObjects duplicates the stores (indexed now by underlying
   2602   // objects) to avoid pointing to elements inside ReadWrites.
   2603   // TODO: Maybe create a new type where they can interact without duplication.
   2604   AliasMultiMap WriteObjects;
   2605   ValueVector TempObjects;
   2606 
   2607   // Check that the read-writes do not conflict with other read-write
   2608   // pointers.
   2609   bool AllWritesIdentified = true;
   2610   for (MI = ReadWrites.begin(), ME = ReadWrites.end(); MI != ME; ++MI) {
   2611     Value *Val = (*MI).first;
   2612     Instruction *Inst = (*MI).second;
   2613 
   2614     GetUnderlyingObjects(Val, TempObjects, DL);
   2615     for (ValueVector::iterator UI=TempObjects.begin(), UE=TempObjects.end();
   2616          UI != UE; ++UI) {
   2617       if (!isIdentifiedObject(*UI)) {
   2618         DEBUG(dbgs() << "LV: Found an unidentified write ptr:"<< **UI <<"\n");
   2619         NeedRTCheck = true;
   2620         AllWritesIdentified = false;
   2621       }
   2622 
   2623       // Never seen it before, can't alias.
   2624       if (WriteObjects[*UI].empty()) {
   2625         DEBUG(dbgs() << "LV: Adding Underlying value:" << **UI <<"\n");
   2626         WriteObjects[*UI].push_back(Inst);
   2627         continue;
   2628       }
   2629       // Direct alias found.
   2630       if (!AA || dyn_cast<GlobalValue>(*UI) == NULL) {
   2631         DEBUG(dbgs() << "LV: Found a possible write-write reorder:"
   2632               << **UI <<"\n");
   2633         return false;
   2634       }
   2635       DEBUG(dbgs() << "LV: Found a conflicting global value:"
   2636             << **UI <<"\n");
   2637       DEBUG(dbgs() << "LV: While examining store:" << *Inst <<"\n");
   2638       DEBUG(dbgs() << "LV: On value:" << *Val <<"\n");
   2639 
   2640       // If global alias, make sure they do alias.
   2641       if (hasPossibleGlobalWriteReorder(*UI,
   2642                                         Inst,
   2643                                         WriteObjects,
   2644                                         MaxByteWidth)) {
   2645         DEBUG(dbgs() << "LV: Found a possible write-write reorder:"
   2646               << *UI <<"\n");
   2647         return false;
   2648       }
   2649 
   2650       // Didn't alias, insert into map for further reference.
   2651       WriteObjects[*UI].push_back(Inst);
   2652     }
   2653     TempObjects.clear();
   2654   }
   2655 
   2656   /// Check that the reads don't conflict with the read-writes.
   2657   for (MI = Reads.begin(), ME = Reads.end(); MI != ME; ++MI) {
   2658     Value *Val = (*MI).first;
   2659     GetUnderlyingObjects(Val, TempObjects, DL);
   2660     for (ValueVector::iterator UI=TempObjects.begin(), UE=TempObjects.end();
   2661          UI != UE; ++UI) {
   2662       // If all of the writes are identified then we don't care if the read
   2663       // pointer is identified or not.
   2664       if (!AllWritesIdentified && !isIdentifiedObject(*UI)) {
   2665         DEBUG(dbgs() << "LV: Found an unidentified read ptr:"<< **UI <<"\n");
   2666         NeedRTCheck = true;
   2667       }
   2668 
   2669       // Never seen it before, can't alias.
   2670       if (WriteObjects[*UI].empty())
   2671         continue;
   2672       // Direct alias found.
   2673       if (!AA || dyn_cast<GlobalValue>(*UI) == NULL) {
   2674         DEBUG(dbgs() << "LV: Found a possible write-write reorder:"
   2675               << **UI <<"\n");
   2676         return false;
   2677       }
   2678       DEBUG(dbgs() << "LV: Found a global value:  "
   2679             << **UI <<"\n");
   2680       Instruction *Inst = (*MI).second;
   2681       DEBUG(dbgs() << "LV: While examining load:" << *Inst <<"\n");
   2682       DEBUG(dbgs() << "LV: On value:" << *Val <<"\n");
   2683 
   2684       // If global alias, make sure they do alias.
   2685       if (hasPossibleGlobalWriteReorder(*UI,
   2686                                         Inst,
   2687                                         WriteObjects,
   2688                                         MaxByteWidth)) {
   2689         DEBUG(dbgs() << "LV: Found a possible read-write reorder:"
   2690               << *UI <<"\n");
   2691         return false;
   2692       }
   2693     }
   2694     TempObjects.clear();
   2695   }
   2696 
   2697   PtrRtCheck.Need = NeedRTCheck;
   2698   if (NeedRTCheck && !CanDoRT) {
   2699     DEBUG(dbgs() << "LV: We can't vectorize because we can't find " <<
   2700           "the array bounds.\n");
   2701     PtrRtCheck.reset();
   2702     return false;
   2703   }
   2704 
   2705   DEBUG(dbgs() << "LV: We "<< (NeedRTCheck ? "" : "don't") <<
   2706         " need a runtime memory check.\n");
   2707   return true;
   2708 }
   2709 
   2710 bool LoopVectorizationLegality::AddReductionVar(PHINode *Phi,
   2711                                                 ReductionKind Kind) {
   2712   if (Phi->getNumIncomingValues() != 2)
   2713     return false;
   2714 
   2715   // Reduction variables are only found in the loop header block.
   2716   if (Phi->getParent() != TheLoop->getHeader())
   2717     return false;
   2718 
   2719   // Obtain the reduction start value from the value that comes from the loop
   2720   // preheader.
   2721   Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
   2722 
   2723   // ExitInstruction is the single value which is used outside the loop.
   2724   // We only allow for a single reduction value to be used outside the loop.
   2725   // This includes users of the reduction, variables (which form a cycle
   2726   // which ends in the phi node).
   2727   Instruction *ExitInstruction = 0;
   2728   // Indicates that we found a binary operation in our scan.
   2729   bool FoundBinOp = false;
   2730 
   2731   // Iter is our iterator. We start with the PHI node and scan for all of the
   2732   // users of this instruction. All users must be instructions that can be
   2733   // used as reduction variables (such as ADD). We may have a single
   2734   // out-of-block user. The cycle must end with the original PHI.
   2735   Instruction *Iter = Phi;
   2736   while (true) {
   2737     // If the instruction has no users then this is a broken
   2738     // chain and can't be a reduction variable.
   2739     if (Iter->use_empty())
   2740       return false;
   2741 
   2742     // Did we find a user inside this loop already ?
   2743     bool FoundInBlockUser = false;
   2744     // Did we reach the initial PHI node already ?
   2745     bool FoundStartPHI = false;
   2746 
   2747     // Is this a bin op ?
   2748     FoundBinOp |= !isa<PHINode>(Iter);
   2749 
   2750     // Remember the current instruction.
   2751     Instruction *OldIter = Iter;
   2752 
   2753     // For each of the *users* of iter.
   2754     for (Value::use_iterator it = Iter->use_begin(), e = Iter->use_end();
   2755          it != e; ++it) {
   2756       Instruction *U = cast<Instruction>(*it);
   2757       // We already know that the PHI is a user.
   2758       if (U == Phi) {
   2759         FoundStartPHI = true;
   2760         continue;
   2761       }
   2762 
   2763       // Check if we found the exit user.
   2764       BasicBlock *Parent = U->getParent();
   2765       if (!TheLoop->contains(Parent)) {
   2766         // Exit if you find multiple outside users.
   2767         if (ExitInstruction != 0)
   2768           return false;
   2769         ExitInstruction = Iter;
   2770       }
   2771 
   2772       // We allow in-loop PHINodes which are not the original reduction PHI
   2773       // node. If this PHI is the only user of Iter (happens in IF w/ no ELSE
   2774       // structure) then don't skip this PHI.
   2775       if (isa<PHINode>(Iter) && isa<PHINode>(U) &&
   2776           U->getParent() != TheLoop->getHeader() &&
   2777           TheLoop->contains(U) &&
   2778           Iter->hasNUsesOrMore(2))
   2779         continue;
   2780 
   2781       // We can't have multiple inside users.
   2782       if (FoundInBlockUser)
   2783         return false;
   2784       FoundInBlockUser = true;
   2785 
   2786       // Any reduction instr must be of one of the allowed kinds.
   2787       if (!isReductionInstr(U, Kind))
   2788         return false;
   2789 
   2790       // Reductions of instructions such as Div, and Sub is only
   2791       // possible if the LHS is the reduction variable.
   2792       if (!U->isCommutative() && !isa<PHINode>(U) && U->getOperand(0) != Iter)
   2793         return false;
   2794 
   2795       Iter = U;
   2796     }
   2797 
   2798     // If all uses were skipped this can't be a reduction variable.
   2799     if (Iter == OldIter)
   2800       return false;
   2801 
   2802     // We found a reduction var if we have reached the original
   2803     // phi node and we only have a single instruction with out-of-loop
   2804     // users.
   2805     if (FoundStartPHI) {
   2806       // This instruction is allowed to have out-of-loop users.
   2807       AllowedExit.insert(ExitInstruction);
   2808 
   2809       // Save the description of this reduction variable.
   2810       ReductionDescriptor RD(RdxStart, ExitInstruction, Kind);
   2811       Reductions[Phi] = RD;
   2812       // We've ended the cycle. This is a reduction variable if we have an
   2813       // outside user and it has a binary op.
   2814       return FoundBinOp && ExitInstruction;
   2815     }
   2816   }
   2817 }
   2818 
   2819 bool
   2820 LoopVectorizationLegality::isReductionInstr(Instruction *I,
   2821                                             ReductionKind Kind) {
   2822   bool FP = I->getType()->isFloatingPointTy();
   2823   bool FastMath = (FP && I->isCommutative() && I->isAssociative());
   2824 
   2825   switch (I->getOpcode()) {
   2826   default:
   2827     return false;
   2828   case Instruction::PHI:
   2829       if (FP && (Kind != RK_FloatMult && Kind != RK_FloatAdd))
   2830         return false;
   2831     // possibly.
   2832     return true;
   2833   case Instruction::Sub:
   2834   case Instruction::Add:
   2835     return Kind == RK_IntegerAdd;
   2836   case Instruction::SDiv:
   2837   case Instruction::UDiv:
   2838   case Instruction::Mul:
   2839     return Kind == RK_IntegerMult;
   2840   case Instruction::And:
   2841     return Kind == RK_IntegerAnd;
   2842   case Instruction::Or:
   2843     return Kind == RK_IntegerOr;
   2844   case Instruction::Xor:
   2845     return Kind == RK_IntegerXor;
   2846   case Instruction::FMul:
   2847     return Kind == RK_FloatMult && FastMath;
   2848   case Instruction::FAdd:
   2849     return Kind == RK_FloatAdd && FastMath;
   2850    }
   2851 }
   2852 
   2853 LoopVectorizationLegality::InductionKind
   2854 LoopVectorizationLegality::isInductionVariable(PHINode *Phi) {
   2855   Type *PhiTy = Phi->getType();
   2856   // We only handle integer and pointer inductions variables.
   2857   if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
   2858     return IK_NoInduction;
   2859 
   2860   // Check that the PHI is consecutive.
   2861   const SCEV *PhiScev = SE->getSCEV(Phi);
   2862   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
   2863   if (!AR) {
   2864     DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
   2865     return IK_NoInduction;
   2866   }
   2867   const SCEV *Step = AR->getStepRecurrence(*SE);
   2868 
   2869   // Integer inductions need to have a stride of one.
   2870   if (PhiTy->isIntegerTy()) {
   2871     if (Step->isOne())
   2872       return IK_IntInduction;
   2873     if (Step->isAllOnesValue())
   2874       return IK_ReverseIntInduction;
   2875     return IK_NoInduction;
   2876   }
   2877 
   2878   // Calculate the pointer stride and check if it is consecutive.
   2879   const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
   2880   if (!C)
   2881     return IK_NoInduction;
   2882 
   2883   assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
   2884   uint64_t Size = DL->getTypeAllocSize(PhiTy->getPointerElementType());
   2885   if (C->getValue()->equalsInt(Size))
   2886     return IK_PtrInduction;
   2887   else if (C->getValue()->equalsInt(0 - Size))
   2888     return IK_ReversePtrInduction;
   2889 
   2890   return IK_NoInduction;
   2891 }
   2892 
   2893 bool LoopVectorizationLegality::isInductionVariable(const Value *V) {
   2894   Value *In0 = const_cast<Value*>(V);
   2895   PHINode *PN = dyn_cast_or_null<PHINode>(In0);
   2896   if (!PN)
   2897     return false;
   2898 
   2899   return Inductions.count(PN);
   2900 }
   2901 
   2902 bool LoopVectorizationLegality::blockNeedsPredication(BasicBlock *BB)  {
   2903   assert(TheLoop->contains(BB) && "Unknown block used");
   2904 
   2905   // Blocks that do not dominate the latch need predication.
   2906   BasicBlock* Latch = TheLoop->getLoopLatch();
   2907   return !DT->dominates(BB, Latch);
   2908 }
   2909 
   2910 bool LoopVectorizationLegality::blockCanBePredicated(BasicBlock *BB) {
   2911   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
   2912     // We don't predicate loads/stores at the moment.
   2913     if (it->mayReadFromMemory() || it->mayWriteToMemory() || it->mayThrow())
   2914       return false;
   2915 
   2916     // The instructions below can trap.
   2917     switch (it->getOpcode()) {
   2918     default: continue;
   2919     case Instruction::UDiv:
   2920     case Instruction::SDiv:
   2921     case Instruction::URem:
   2922     case Instruction::SRem:
   2923              return false;
   2924     }
   2925   }
   2926 
   2927   return true;
   2928 }
   2929 
   2930 bool LoopVectorizationLegality::hasComputableBounds(Value *Ptr) {
   2931   const SCEV *PhiScev = SE->getSCEV(Ptr);
   2932   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
   2933   if (!AR)
   2934     return false;
   2935 
   2936   return AR->isAffine();
   2937 }
   2938 
   2939 LoopVectorizationCostModel::VectorizationFactor
   2940 LoopVectorizationCostModel::selectVectorizationFactor(bool OptForSize,
   2941                                                       unsigned UserVF) {
   2942   // Width 1 means no vectorize
   2943   VectorizationFactor Factor = { 1U, 0U };
   2944   if (OptForSize && Legal->getRuntimePointerCheck()->Need) {
   2945     DEBUG(dbgs() << "LV: Aborting. Runtime ptr check is required in Os.\n");
   2946     return Factor;
   2947   }
   2948 
   2949   // Find the trip count.
   2950   unsigned TC = SE->getSmallConstantTripCount(TheLoop, TheLoop->getLoopLatch());
   2951   DEBUG(dbgs() << "LV: Found trip count:"<<TC<<"\n");
   2952 
   2953   unsigned WidestType = getWidestType();
   2954   unsigned WidestRegister = TTI.getRegisterBitWidth(true);
   2955   unsigned MaxVectorSize = WidestRegister / WidestType;
   2956   DEBUG(dbgs() << "LV: The Widest type: " << WidestType << " bits.\n");
   2957   DEBUG(dbgs() << "LV: The Widest register is:" << WidestRegister << "bits.\n");
   2958 
   2959   if (MaxVectorSize == 0) {
   2960     DEBUG(dbgs() << "LV: The target has no vector registers.\n");
   2961     MaxVectorSize = 1;
   2962   }
   2963 
   2964   assert(MaxVectorSize <= 32 && "Did not expect to pack so many elements"
   2965          " into one vector!");
   2966 
   2967   unsigned VF = MaxVectorSize;
   2968 
   2969   // If we optimize the program for size, avoid creating the tail loop.
   2970   if (OptForSize) {
   2971     // If we are unable to calculate the trip count then don't try to vectorize.
   2972     if (TC < 2) {
   2973       DEBUG(dbgs() << "LV: Aborting. A tail loop is required in Os.\n");
   2974       return Factor;
   2975     }
   2976 
   2977     // Find the maximum SIMD width that can fit within the trip count.
   2978     VF = TC % MaxVectorSize;
   2979 
   2980     if (VF == 0)
   2981       VF = MaxVectorSize;
   2982 
   2983     // If the trip count that we found modulo the vectorization factor is not
   2984     // zero then we require a tail.
   2985     if (VF < 2) {
   2986       DEBUG(dbgs() << "LV: Aborting. A tail loop is required in Os.\n");
   2987       return Factor;
   2988     }
   2989   }
   2990 
   2991   if (UserVF != 0) {
   2992     assert(isPowerOf2_32(UserVF) && "VF needs to be a power of two");
   2993     DEBUG(dbgs() << "LV: Using user VF "<<UserVF<<".\n");
   2994 
   2995     Factor.Width = UserVF;
   2996     return Factor;
   2997   }
   2998 
   2999   float Cost = expectedCost(1);
   3000   unsigned Width = 1;
   3001   DEBUG(dbgs() << "LV: Scalar loop costs: "<< (int)Cost << ".\n");
   3002   for (unsigned i=2; i <= VF; i*=2) {
   3003     // Notice that the vector loop needs to be executed less times, so
   3004     // we need to divide the cost of the vector loops by the width of
   3005     // the vector elements.
   3006     float VectorCost = expectedCost(i) / (float)i;
   3007     DEBUG(dbgs() << "LV: Vector loop of width "<< i << " costs: " <<
   3008           (int)VectorCost << ".\n");
   3009     if (VectorCost < Cost) {
   3010       Cost = VectorCost;
   3011       Width = i;
   3012     }
   3013   }
   3014 
   3015   DEBUG(dbgs() << "LV: Selecting VF = : "<< Width << ".\n");
   3016   Factor.Width = Width;
   3017   Factor.Cost = Width * Cost;
   3018   return Factor;
   3019 }
   3020 
   3021 unsigned LoopVectorizationCostModel::getWidestType() {
   3022   unsigned MaxWidth = 8;
   3023 
   3024   // For each block.
   3025   for (Loop::block_iterator bb = TheLoop->block_begin(),
   3026        be = TheLoop->block_end(); bb != be; ++bb) {
   3027     BasicBlock *BB = *bb;
   3028 
   3029     // For each instruction in the loop.
   3030     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
   3031       Type *T = it->getType();
   3032 
   3033       // Only examine Loads, Stores and PHINodes.
   3034       if (!isa<LoadInst>(it) && !isa<StoreInst>(it) && !isa<PHINode>(it))
   3035         continue;
   3036 
   3037       // Examine PHI nodes that are reduction variables.
   3038       if (PHINode *PN = dyn_cast<PHINode>(it))
   3039         if (!Legal->getReductionVars()->count(PN))
   3040           continue;
   3041 
   3042       // Examine the stored values.
   3043       if (StoreInst *ST = dyn_cast<StoreInst>(it))
   3044         T = ST->getValueOperand()->getType();
   3045 
   3046       // Ignore loaded pointer types and stored pointer types that are not
   3047       // consecutive. However, we do want to take consecutive stores/loads of
   3048       // pointer vectors into account.
   3049       if (T->isPointerTy() && !isConsecutiveLoadOrStore(it))
   3050         continue;
   3051 
   3052       MaxWidth = std::max(MaxWidth,
   3053                           (unsigned)DL->getTypeSizeInBits(T->getScalarType()));
   3054     }
   3055   }
   3056 
   3057   return MaxWidth;
   3058 }
   3059 
   3060 unsigned
   3061 LoopVectorizationCostModel::selectUnrollFactor(bool OptForSize,
   3062                                                unsigned UserUF,
   3063                                                unsigned VF,
   3064                                                unsigned LoopCost) {
   3065 
   3066   // -- The unroll heuristics --
   3067   // We unroll the loop in order to expose ILP and reduce the loop overhead.
   3068   // There are many micro-architectural considerations that we can't predict
   3069   // at this level. For example frontend pressure (on decode or fetch) due to
   3070   // code size, or the number and capabilities of the execution ports.
   3071   //
   3072   // We use the following heuristics to select the unroll factor:
   3073   // 1. If the code has reductions the we unroll in order to break the cross
   3074   // iteration dependency.
   3075   // 2. If the loop is really small then we unroll in order to reduce the loop
   3076   // overhead.
   3077   // 3. We don't unroll if we think that we will spill registers to memory due
   3078   // to the increased register pressure.
   3079 
   3080   // Use the user preference, unless 'auto' is selected.
   3081   if (UserUF != 0)
   3082     return UserUF;
   3083 
   3084   // When we optimize for size we don't unroll.
   3085   if (OptForSize)
   3086     return 1;
   3087 
   3088   // Do not unroll loops with a relatively small trip count.
   3089   unsigned TC = SE->getSmallConstantTripCount(TheLoop,
   3090                                               TheLoop->getLoopLatch());
   3091   if (TC > 1 && TC < TinyTripCountUnrollThreshold)
   3092     return 1;
   3093 
   3094   unsigned TargetVectorRegisters = TTI.getNumberOfRegisters(true);
   3095   DEBUG(dbgs() << "LV: The target has " << TargetVectorRegisters <<
   3096         " vector registers\n");
   3097 
   3098   LoopVectorizationCostModel::RegisterUsage R = calculateRegisterUsage();
   3099   // We divide by these constants so assume that we have at least one
   3100   // instruction that uses at least one register.
   3101   R.MaxLocalUsers = std::max(R.MaxLocalUsers, 1U);
   3102   R.NumInstructions = std::max(R.NumInstructions, 1U);
   3103 
   3104   // We calculate the unroll factor using the following formula.
   3105   // Subtract the number of loop invariants from the number of available
   3106   // registers. These registers are used by all of the unrolled instances.
   3107   // Next, divide the remaining registers by the number of registers that is
   3108   // required by the loop, in order to estimate how many parallel instances
   3109   // fit without causing spills.
   3110   unsigned UF = (TargetVectorRegisters - R.LoopInvariantRegs) / R.MaxLocalUsers;
   3111 
   3112   // Clamp the unroll factor ranges to reasonable factors.
   3113   unsigned MaxUnrollSize = TTI.getMaximumUnrollFactor();
   3114 
   3115   // If we did not calculate the cost for VF (because the user selected the VF)
   3116   // then we calculate the cost of VF here.
   3117   if (LoopCost == 0)
   3118     LoopCost = expectedCost(VF);
   3119 
   3120   // Clamp the calculated UF to be between the 1 and the max unroll factor
   3121   // that the target allows.
   3122   if (UF > MaxUnrollSize)
   3123     UF = MaxUnrollSize;
   3124   else if (UF < 1)
   3125     UF = 1;
   3126 
   3127   if (Legal->getReductionVars()->size()) {
   3128     DEBUG(dbgs() << "LV: Unrolling because of reductions. \n");
   3129     return UF;
   3130   }
   3131 
   3132   // We want to unroll tiny loops in order to reduce the loop overhead.
   3133   // We assume that the cost overhead is 1 and we use the cost model
   3134   // to estimate the cost of the loop and unroll until the cost of the
   3135   // loop overhead is about 5% of the cost of the loop.
   3136   DEBUG(dbgs() << "LV: Loop cost is "<< LoopCost <<" \n");
   3137   if (LoopCost < 20) {
   3138     DEBUG(dbgs() << "LV: Unrolling to reduce branch cost. \n");
   3139     unsigned NewUF = 20/LoopCost + 1;
   3140     return std::min(NewUF, UF);
   3141   }
   3142 
   3143   DEBUG(dbgs() << "LV: Not Unrolling. \n");
   3144   return 1;
   3145 }
   3146 
   3147 LoopVectorizationCostModel::RegisterUsage
   3148 LoopVectorizationCostModel::calculateRegisterUsage() {
   3149   // This function calculates the register usage by measuring the highest number
   3150   // of values that are alive at a single location. Obviously, this is a very
   3151   // rough estimation. We scan the loop in a topological order in order and
   3152   // assign a number to each instruction. We use RPO to ensure that defs are
   3153   // met before their users. We assume that each instruction that has in-loop
   3154   // users starts an interval. We record every time that an in-loop value is
   3155   // used, so we have a list of the first and last occurrences of each
   3156   // instruction. Next, we transpose this data structure into a multi map that
   3157   // holds the list of intervals that *end* at a specific location. This multi
   3158   // map allows us to perform a linear search. We scan the instructions linearly
   3159   // and record each time that a new interval starts, by placing it in a set.
   3160   // If we find this value in the multi-map then we remove it from the set.
   3161   // The max register usage is the maximum size of the set.
   3162   // We also search for instructions that are defined outside the loop, but are
   3163   // used inside the loop. We need this number separately from the max-interval
   3164   // usage number because when we unroll, loop-invariant values do not take
   3165   // more register.
   3166   LoopBlocksDFS DFS(TheLoop);
   3167   DFS.perform(LI);
   3168 
   3169   RegisterUsage R;
   3170   R.NumInstructions = 0;
   3171 
   3172   // Each 'key' in the map opens a new interval. The values
   3173   // of the map are the index of the 'last seen' usage of the
   3174   // instruction that is the key.
   3175   typedef DenseMap<Instruction*, unsigned> IntervalMap;
   3176   // Maps instruction to its index.
   3177   DenseMap<unsigned, Instruction*> IdxToInstr;
   3178   // Marks the end of each interval.
   3179   IntervalMap EndPoint;
   3180   // Saves the list of instruction indices that are used in the loop.
   3181   SmallSet<Instruction*, 8> Ends;
   3182   // Saves the list of values that are used in the loop but are
   3183   // defined outside the loop, such as arguments and constants.
   3184   SmallPtrSet<Value*, 8> LoopInvariants;
   3185 
   3186   unsigned Index = 0;
   3187   for (LoopBlocksDFS::RPOIterator bb = DFS.beginRPO(),
   3188        be = DFS.endRPO(); bb != be; ++bb) {
   3189     R.NumInstructions += (*bb)->size();
   3190     for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
   3191          ++it) {
   3192       Instruction *I = it;
   3193       IdxToInstr[Index++] = I;
   3194 
   3195       // Save the end location of each USE.
   3196       for (unsigned i = 0; i < I->getNumOperands(); ++i) {
   3197         Value *U = I->getOperand(i);
   3198         Instruction *Instr = dyn_cast<Instruction>(U);
   3199 
   3200         // Ignore non-instruction values such as arguments, constants, etc.
   3201         if (!Instr) continue;
   3202 
   3203         // If this instruction is outside the loop then record it and continue.
   3204         if (!TheLoop->contains(Instr)) {
   3205           LoopInvariants.insert(Instr);
   3206           continue;
   3207         }
   3208 
   3209         // Overwrite previous end points.
   3210         EndPoint[Instr] = Index;
   3211         Ends.insert(Instr);
   3212       }
   3213     }
   3214   }
   3215 
   3216   // Saves the list of intervals that end with the index in 'key'.
   3217   typedef SmallVector<Instruction*, 2> InstrList;
   3218   DenseMap<unsigned, InstrList> TransposeEnds;
   3219 
   3220   // Transpose the EndPoints to a list of values that end at each index.
   3221   for (IntervalMap::iterator it = EndPoint.begin(), e = EndPoint.end();
   3222        it != e; ++it)
   3223     TransposeEnds[it->second].push_back(it->first);
   3224 
   3225   SmallSet<Instruction*, 8> OpenIntervals;
   3226   unsigned MaxUsage = 0;
   3227 
   3228 
   3229   DEBUG(dbgs() << "LV(REG): Calculating max register usage:\n");
   3230   for (unsigned int i = 0; i < Index; ++i) {
   3231     Instruction *I = IdxToInstr[i];
   3232     // Ignore instructions that are never used within the loop.
   3233     if (!Ends.count(I)) continue;
   3234 
   3235     // Remove all of the instructions that end at this location.
   3236     InstrList &List = TransposeEnds[i];
   3237     for (unsigned int j=0, e = List.size(); j < e; ++j)
   3238       OpenIntervals.erase(List[j]);
   3239 
   3240     // Count the number of live interals.
   3241     MaxUsage = std::max(MaxUsage, OpenIntervals.size());
   3242 
   3243     DEBUG(dbgs() << "LV(REG): At #" << i << " Interval # " <<
   3244           OpenIntervals.size() <<"\n");
   3245 
   3246     // Add the current instruction to the list of open intervals.
   3247     OpenIntervals.insert(I);
   3248   }
   3249 
   3250   unsigned Invariant = LoopInvariants.size();
   3251   DEBUG(dbgs() << "LV(REG): Found max usage: " << MaxUsage << " \n");
   3252   DEBUG(dbgs() << "LV(REG): Found invariant usage: " << Invariant << " \n");
   3253   DEBUG(dbgs() << "LV(REG): LoopSize: " << R.NumInstructions << " \n");
   3254 
   3255   R.LoopInvariantRegs = Invariant;
   3256   R.MaxLocalUsers = MaxUsage;
   3257   return R;
   3258 }
   3259 
   3260 unsigned LoopVectorizationCostModel::expectedCost(unsigned VF) {
   3261   unsigned Cost = 0;
   3262 
   3263   // For each block.
   3264   for (Loop::block_iterator bb = TheLoop->block_begin(),
   3265        be = TheLoop->block_end(); bb != be; ++bb) {
   3266     unsigned BlockCost = 0;
   3267     BasicBlock *BB = *bb;
   3268 
   3269     // For each instruction in the old loop.
   3270     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
   3271       // Skip dbg intrinsics.
   3272       if (isa<DbgInfoIntrinsic>(it))
   3273         continue;
   3274 
   3275       unsigned C = getInstructionCost(it, VF);
   3276       Cost += C;
   3277       DEBUG(dbgs() << "LV: Found an estimated cost of "<< C <<" for VF " <<
   3278             VF << " For instruction: "<< *it << "\n");
   3279     }
   3280 
   3281     // We assume that if-converted blocks have a 50% chance of being executed.
   3282     // When the code is scalar then some of the blocks are avoided due to CF.
   3283     // When the code is vectorized we execute all code paths.
   3284     if (Legal->blockNeedsPredication(*bb) && VF == 1)
   3285       BlockCost /= 2;
   3286 
   3287     Cost += BlockCost;
   3288   }
   3289 
   3290   return Cost;
   3291 }
   3292 
   3293 unsigned
   3294 LoopVectorizationCostModel::getInstructionCost(Instruction *I, unsigned VF) {
   3295   // If we know that this instruction will remain uniform, check the cost of
   3296   // the scalar version.
   3297   if (Legal->isUniformAfterVectorization(I))
   3298     VF = 1;
   3299 
   3300   Type *RetTy = I->getType();
   3301   Type *VectorTy = ToVectorTy(RetTy, VF);
   3302 
   3303   // TODO: We need to estimate the cost of intrinsic calls.
   3304   switch (I->getOpcode()) {
   3305   case Instruction::GetElementPtr:
   3306     // We mark this instruction as zero-cost because the cost of GEPs in
   3307     // vectorized code depends on whether the corresponding memory instruction
   3308     // is scalarized or not. Therefore, we handle GEPs with the memory
   3309     // instruction cost.
   3310     return 0;
   3311   case Instruction::Br: {
   3312     return TTI.getCFInstrCost(I->getOpcode());
   3313   }
   3314   case Instruction::PHI:
   3315     //TODO: IF-converted IFs become selects.
   3316     return 0;
   3317   case Instruction::Add:
   3318   case Instruction::FAdd:
   3319   case Instruction::Sub:
   3320   case Instruction::FSub:
   3321   case Instruction::Mul:
   3322   case Instruction::FMul:
   3323   case Instruction::UDiv:
   3324   case Instruction::SDiv:
   3325   case Instruction::FDiv:
   3326   case Instruction::URem:
   3327   case Instruction::SRem:
   3328   case Instruction::FRem:
   3329   case Instruction::Shl:
   3330   case Instruction::LShr:
   3331   case Instruction::AShr:
   3332   case Instruction::And:
   3333   case Instruction::Or:
   3334   case Instruction::Xor:
   3335     return TTI.getArithmeticInstrCost(I->getOpcode(), VectorTy);
   3336   case Instruction::Select: {
   3337     SelectInst *SI = cast<SelectInst>(I);
   3338     const SCEV *CondSCEV = SE->getSCEV(SI->getCondition());
   3339     bool ScalarCond = (SE->isLoopInvariant(CondSCEV, TheLoop));
   3340     Type *CondTy = SI->getCondition()->getType();
   3341     if (!ScalarCond)
   3342       CondTy = VectorType::get(CondTy, VF);
   3343 
   3344     return TTI.getCmpSelInstrCost(I->getOpcode(), VectorTy, CondTy);
   3345   }
   3346   case Instruction::ICmp:
   3347   case Instruction::FCmp: {
   3348     Type *ValTy = I->getOperand(0)->getType();
   3349     VectorTy = ToVectorTy(ValTy, VF);
   3350     return TTI.getCmpSelInstrCost(I->getOpcode(), VectorTy);
   3351   }
   3352   case Instruction::Store:
   3353   case Instruction::Load: {
   3354     StoreInst *SI = dyn_cast<StoreInst>(I);
   3355     LoadInst *LI = dyn_cast<LoadInst>(I);
   3356     Type *ValTy = (SI ? SI->getValueOperand()->getType() :
   3357                    LI->getType());
   3358     VectorTy = ToVectorTy(ValTy, VF);
   3359 
   3360     unsigned Alignment = SI ? SI->getAlignment() : LI->getAlignment();
   3361     unsigned AS = SI ? SI->getPointerAddressSpace() :
   3362       LI->getPointerAddressSpace();
   3363     Value *Ptr = SI ? SI->getPointerOperand() : LI->getPointerOperand();
   3364     // We add the cost of address computation here instead of with the gep
   3365     // instruction because only here we know whether the operation is
   3366     // scalarized.
   3367     if (VF == 1)
   3368       return TTI.getAddressComputationCost(VectorTy) +
   3369         TTI.getMemoryOpCost(I->getOpcode(), VectorTy, Alignment, AS);
   3370 
   3371     // Scalarized loads/stores.
   3372     int Stride = Legal->isConsecutivePtr(Ptr);
   3373     bool Reverse = Stride < 0;
   3374     if (0 == Stride) {
   3375       unsigned Cost = 0;
   3376       // The cost of extracting from the value vector and pointer vector.
   3377       Type *PtrTy = ToVectorTy(Ptr->getType(), VF);
   3378       for (unsigned i = 0; i < VF; ++i) {
   3379         //  The cost of extracting the pointer operand.
   3380         Cost += TTI.getVectorInstrCost(Instruction::ExtractElement, PtrTy, i);
   3381         // In case of STORE, the cost of ExtractElement from the vector.
   3382         // In case of LOAD, the cost of InsertElement into the returned
   3383         // vector.
   3384         Cost += TTI.getVectorInstrCost(SI ? Instruction::ExtractElement :
   3385                                             Instruction::InsertElement,
   3386                                             VectorTy, i);
   3387       }
   3388 
   3389       // The cost of the scalar loads/stores.
   3390       Cost += VF * TTI.getAddressComputationCost(ValTy->getScalarType());
   3391       Cost += VF * TTI.getMemoryOpCost(I->getOpcode(), ValTy->getScalarType(),
   3392                                        Alignment, AS);
   3393       return Cost;
   3394     }
   3395 
   3396     // Wide load/stores.
   3397     unsigned Cost = TTI.getAddressComputationCost(VectorTy);
   3398     Cost += TTI.getMemoryOpCost(I->getOpcode(), VectorTy, Alignment, AS);
   3399 
   3400     if (Reverse)
   3401       Cost += TTI.getShuffleCost(TargetTransformInfo::SK_Reverse,
   3402                                   VectorTy, 0);
   3403     return Cost;
   3404   }
   3405   case Instruction::ZExt:
   3406   case Instruction::SExt:
   3407   case Instruction::FPToUI:
   3408   case Instruction::FPToSI:
   3409   case Instruction::FPExt:
   3410   case Instruction::PtrToInt:
   3411   case Instruction::IntToPtr:
   3412   case Instruction::SIToFP:
   3413   case Instruction::UIToFP:
   3414   case Instruction::Trunc:
   3415   case Instruction::FPTrunc:
   3416   case Instruction::BitCast: {
   3417     // We optimize the truncation of induction variable.
   3418     // The cost of these is the same as the scalar operation.
   3419     if (I->getOpcode() == Instruction::Trunc &&
   3420         Legal->isInductionVariable(I->getOperand(0)))
   3421       return TTI.getCastInstrCost(I->getOpcode(), I->getType(),
   3422                                   I->getOperand(0)->getType());
   3423 
   3424     Type *SrcVecTy = ToVectorTy(I->getOperand(0)->getType(), VF);
   3425     return TTI.getCastInstrCost(I->getOpcode(), VectorTy, SrcVecTy);
   3426   }
   3427   case Instruction::Call: {
   3428     CallInst *CI = cast<CallInst>(I);
   3429     Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
   3430     assert(ID && "Not an intrinsic call!");
   3431     Type *RetTy = ToVectorTy(CI->getType(), VF);
   3432     SmallVector<Type*, 4> Tys;
   3433     for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i)
   3434       Tys.push_back(ToVectorTy(CI->getArgOperand(i)->getType(), VF));
   3435     return TTI.getIntrinsicInstrCost(ID, RetTy, Tys);
   3436   }
   3437   default: {
   3438     // We are scalarizing the instruction. Return the cost of the scalar
   3439     // instruction, plus the cost of insert and extract into vector
   3440     // elements, times the vector width.
   3441     unsigned Cost = 0;
   3442 
   3443     if (!RetTy->isVoidTy() && VF != 1) {
   3444       unsigned InsCost = TTI.getVectorInstrCost(Instruction::InsertElement,
   3445                                                 VectorTy);
   3446       unsigned ExtCost = TTI.getVectorInstrCost(Instruction::ExtractElement,
   3447                                                 VectorTy);
   3448 
   3449       // The cost of inserting the results plus extracting each one of the
   3450       // operands.
   3451       Cost += VF * (InsCost + ExtCost * I->getNumOperands());
   3452     }
   3453 
   3454     // The cost of executing VF copies of the scalar instruction. This opcode
   3455     // is unknown. Assume that it is the same as 'mul'.
   3456     Cost += VF * TTI.getArithmeticInstrCost(Instruction::Mul, VectorTy);
   3457     return Cost;
   3458   }
   3459   }// end of switch.
   3460 }
   3461 
   3462 Type* LoopVectorizationCostModel::ToVectorTy(Type *Scalar, unsigned VF) {
   3463   if (Scalar->isVoidTy() || VF == 1)
   3464     return Scalar;
   3465   return VectorType::get(Scalar, VF);
   3466 }
   3467 
   3468 char LoopVectorize::ID = 0;
   3469 static const char lv_name[] = "Loop Vectorization";
   3470 INITIALIZE_PASS_BEGIN(LoopVectorize, LV_NAME, lv_name, false, false)
   3471 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
   3472 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
   3473 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
   3474 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
   3475 INITIALIZE_PASS_END(LoopVectorize, LV_NAME, lv_name, false, false)
   3476 
   3477 namespace llvm {
   3478   Pass *createLoopVectorizePass() {
   3479     return new LoopVectorize();
   3480   }
   3481 }
   3482 
   3483 bool LoopVectorizationCostModel::isConsecutiveLoadOrStore(Instruction *Inst) {
   3484   // Check for a store.
   3485   if (StoreInst *ST = dyn_cast<StoreInst>(Inst))
   3486     return Legal->isConsecutivePtr(ST->getPointerOperand()) != 0;
   3487 
   3488   // Check for a load.
   3489   if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
   3490     return Legal->isConsecutivePtr(LI->getPointerOperand()) != 0;
   3491 
   3492   return false;
   3493 }
   3494