LLVM API Documentation

LoopVectorize.cpp
Go to the documentation of this file.
00001 //===- LoopVectorize.cpp - A Loop Vectorizer ------------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This is the LLVM loop vectorizer. This pass modifies 'vectorizable' loops
00011 // and generates target-independent LLVM-IR.
00012 // The vectorizer uses the TargetTransformInfo analysis to estimate the costs
00013 // of instructions in order to estimate the profitability of vectorization.
00014 //
00015 // The loop vectorizer combines consecutive loop iterations into a single
00016 // 'wide' iteration. After this transformation the index is incremented
00017 // by the SIMD vector width, and not by one.
00018 //
00019 // This pass has three parts:
00020 // 1. The main loop pass that drives the different parts.
00021 // 2. LoopVectorizationLegality - A unit that checks for the legality
00022 //    of the vectorization.
00023 // 3. InnerLoopVectorizer - A unit that performs the actual
00024 //    widening of instructions.
00025 // 4. LoopVectorizationCostModel - A unit that checks for the profitability
00026 //    of vectorization. It decides on the optimal vector width, which
00027 //    can be one, if vectorization is not profitable.
00028 //
00029 //===----------------------------------------------------------------------===//
00030 //
00031 // The reduction-variable vectorization is based on the paper:
00032 //  D. Nuzman and R. Henderson. Multi-platform Auto-vectorization.
00033 //
00034 // Variable uniformity checks are inspired by:
00035 //  Karrenberg, R. and Hack, S. Whole Function Vectorization.
00036 //
00037 // Other ideas/concepts are from:
00038 //  A. Zaks and D. Nuzman. Autovectorization in GCC-two years later.
00039 //
00040 //  S. Maleki, Y. Gao, M. Garzaran, T. Wong and D. Padua.  An Evaluation of
00041 //  Vectorizing Compilers.
00042 //
00043 //===----------------------------------------------------------------------===//
00044 
00045 #include "llvm/Transforms/Vectorize.h"
00046 #include "llvm/ADT/DenseMap.h"
00047 #include "llvm/ADT/EquivalenceClasses.h"
00048 #include "llvm/ADT/Hashing.h"
00049 #include "llvm/ADT/MapVector.h"
00050 #include "llvm/ADT/SetVector.h"
00051 #include "llvm/ADT/SmallPtrSet.h"
00052 #include "llvm/ADT/SmallSet.h"
00053 #include "llvm/ADT/SmallVector.h"
00054 #include "llvm/ADT/Statistic.h"
00055 #include "llvm/ADT/StringExtras.h"
00056 #include "llvm/Analysis/AliasAnalysis.h"
00057 #include "llvm/Analysis/BlockFrequencyInfo.h"
00058 #include "llvm/Analysis/LoopInfo.h"
00059 #include "llvm/Analysis/LoopIterator.h"
00060 #include "llvm/Analysis/LoopPass.h"
00061 #include "llvm/Analysis/ScalarEvolution.h"
00062 #include "llvm/Analysis/ScalarEvolutionExpander.h"
00063 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
00064 #include "llvm/Analysis/TargetTransformInfo.h"
00065 #include "llvm/Analysis/ValueTracking.h"
00066 #include "llvm/IR/Constants.h"
00067 #include "llvm/IR/DataLayout.h"
00068 #include "llvm/IR/DebugInfo.h"
00069 #include "llvm/IR/DerivedTypes.h"
00070 #include "llvm/IR/Dominators.h"
00071 #include "llvm/IR/Function.h"
00072 #include "llvm/IR/IRBuilder.h"
00073 #include "llvm/IR/Instructions.h"
00074 #include "llvm/IR/IntrinsicInst.h"
00075 #include "llvm/IR/LLVMContext.h"
00076 #include "llvm/IR/Module.h"
00077 #include "llvm/IR/PatternMatch.h"
00078 #include "llvm/IR/Type.h"
00079 #include "llvm/IR/Value.h"
00080 #include "llvm/IR/ValueHandle.h"
00081 #include "llvm/IR/Verifier.h"
00082 #include "llvm/Pass.h"
00083 #include "llvm/Support/BranchProbability.h"
00084 #include "llvm/Support/CommandLine.h"
00085 #include "llvm/Support/Debug.h"
00086 #include "llvm/Support/Format.h"
00087 #include "llvm/Support/raw_ostream.h"
00088 #include "llvm/Target/TargetLibraryInfo.h"
00089 #include "llvm/Transforms/Scalar.h"
00090 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00091 #include "llvm/Transforms/Utils/Local.h"
00092 #include "llvm/Transforms/Utils/VectorUtils.h"
00093 #include <algorithm>
00094 #include <map>
00095 
00096 using namespace llvm;
00097 using namespace llvm::PatternMatch;
00098 
00099 #define LV_NAME "loop-vectorize"
00100 #define DEBUG_TYPE LV_NAME
00101 
00102 STATISTIC(LoopsVectorized, "Number of loops vectorized");
00103 STATISTIC(LoopsAnalyzed, "Number of loops analyzed for vectorization");
00104 
00105 static cl::opt<unsigned>
00106 VectorizationFactor("force-vector-width", cl::init(0), cl::Hidden,
00107                     cl::desc("Sets the SIMD width. Zero is autoselect."));
00108 
00109 static cl::opt<unsigned>
00110 VectorizationUnroll("force-vector-unroll", cl::init(0), cl::Hidden,
00111                     cl::desc("Sets the vectorization unroll count. "
00112                              "Zero is autoselect."));
00113 
00114 static cl::opt<bool>
00115 EnableIfConversion("enable-if-conversion", cl::init(true), cl::Hidden,
00116                    cl::desc("Enable if-conversion during vectorization."));
00117 
00118 /// We don't vectorize loops with a known constant trip count below this number.
00119 static cl::opt<unsigned>
00120 TinyTripCountVectorThreshold("vectorizer-min-trip-count", cl::init(16),
00121                              cl::Hidden,
00122                              cl::desc("Don't vectorize loops with a constant "
00123                                       "trip count that is smaller than this "
00124                                       "value."));
00125 
00126 /// This enables versioning on the strides of symbolically striding memory
00127 /// accesses in code like the following.
00128 ///   for (i = 0; i < N; ++i)
00129 ///     A[i * Stride1] += B[i * Stride2] ...
00130 ///
00131 /// Will be roughly translated to
00132 ///    if (Stride1 == 1 && Stride2 == 1) {
00133 ///      for (i = 0; i < N; i+=4)
00134 ///       A[i:i+3] += ...
00135 ///    } else
00136 ///      ...
00137 static cl::opt<bool> EnableMemAccessVersioning(
00138     "enable-mem-access-versioning", cl::init(true), cl::Hidden,
00139     cl::desc("Enable symblic stride memory access versioning"));
00140 
00141 /// We don't unroll loops with a known constant trip count below this number.
00142 static const unsigned TinyTripCountUnrollThreshold = 128;
00143 
00144 /// When performing memory disambiguation checks at runtime do not make more
00145 /// than this number of comparisons.
00146 static const unsigned RuntimeMemoryCheckThreshold = 8;
00147 
00148 /// Maximum simd width.
00149 static const unsigned MaxVectorWidth = 64;
00150 
00151 static cl::opt<unsigned> ForceTargetNumScalarRegs(
00152     "force-target-num-scalar-regs", cl::init(0), cl::Hidden,
00153     cl::desc("A flag that overrides the target's number of scalar registers."));
00154 
00155 static cl::opt<unsigned> ForceTargetNumVectorRegs(
00156     "force-target-num-vector-regs", cl::init(0), cl::Hidden,
00157     cl::desc("A flag that overrides the target's number of vector registers."));
00158 
00159 /// Maximum vectorization unroll count.
00160 static const unsigned MaxUnrollFactor = 16;
00161 
00162 static cl::opt<unsigned> ForceTargetMaxScalarUnrollFactor(
00163     "force-target-max-scalar-unroll", cl::init(0), cl::Hidden,
00164     cl::desc("A flag that overrides the target's max unroll factor for scalar "
00165              "loops."));
00166 
00167 static cl::opt<unsigned> ForceTargetMaxVectorUnrollFactor(
00168     "force-target-max-vector-unroll", cl::init(0), cl::Hidden,
00169     cl::desc("A flag that overrides the target's max unroll factor for "
00170              "vectorized loops."));
00171 
00172 static cl::opt<unsigned> ForceTargetInstructionCost(
00173     "force-target-instruction-cost", cl::init(0), cl::Hidden,
00174     cl::desc("A flag that overrides the target's expected cost for "
00175              "an instruction to a single constant value. Mostly "
00176              "useful for getting consistent testing."));
00177 
00178 static cl::opt<unsigned> SmallLoopCost(
00179     "small-loop-cost", cl::init(20), cl::Hidden,
00180     cl::desc("The cost of a loop that is considered 'small' by the unroller."));
00181 
00182 static cl::opt<bool> LoopVectorizeWithBlockFrequency(
00183     "loop-vectorize-with-block-frequency", cl::init(false), cl::Hidden,
00184     cl::desc("Enable the use of the block frequency analysis to access PGO "
00185              "heuristics minimizing code growth in cold regions and being more "
00186              "aggressive in hot regions."));
00187 
00188 // Runtime unroll loops for load/store throughput.
00189 static cl::opt<bool> EnableLoadStoreRuntimeUnroll(
00190     "enable-loadstore-runtime-unroll", cl::init(true), cl::Hidden,
00191     cl::desc("Enable runtime unrolling until load/store ports are saturated"));
00192 
00193 /// The number of stores in a loop that are allowed to need predication.
00194 static cl::opt<unsigned> NumberOfStoresToPredicate(
00195     "vectorize-num-stores-pred", cl::init(1), cl::Hidden,
00196     cl::desc("Max number of stores to be predicated behind an if."));
00197 
00198 static cl::opt<bool> EnableIndVarRegisterHeur(
00199     "enable-ind-var-reg-heur", cl::init(true), cl::Hidden,
00200     cl::desc("Count the induction variable only once when unrolling"));
00201 
00202 static cl::opt<bool> EnableCondStoresVectorization(
00203     "enable-cond-stores-vec", cl::init(false), cl::Hidden,
00204     cl::desc("Enable if predication of stores during vectorization."));
00205 
00206 namespace {
00207 
00208 // Forward declarations.
00209 class LoopVectorizationLegality;
00210 class LoopVectorizationCostModel;
00211 
00212 /// InnerLoopVectorizer vectorizes loops which contain only one basic
00213 /// block to a specified vectorization factor (VF).
00214 /// This class performs the widening of scalars into vectors, or multiple
00215 /// scalars. This class also implements the following features:
00216 /// * It inserts an epilogue loop for handling loops that don't have iteration
00217 ///   counts that are known to be a multiple of the vectorization factor.
00218 /// * It handles the code generation for reduction variables.
00219 /// * Scalarization (implementation using scalars) of un-vectorizable
00220 ///   instructions.
00221 /// InnerLoopVectorizer does not perform any vectorization-legality
00222 /// checks, and relies on the caller to check for the different legality
00223 /// aspects. The InnerLoopVectorizer relies on the
00224 /// LoopVectorizationLegality class to provide information about the induction
00225 /// and reduction variables that were found to a given vectorization factor.
00226 class InnerLoopVectorizer {
00227 public:
00228   InnerLoopVectorizer(Loop *OrigLoop, ScalarEvolution *SE, LoopInfo *LI,
00229                       DominatorTree *DT, const DataLayout *DL,
00230                       const TargetLibraryInfo *TLI, unsigned VecWidth,
00231                       unsigned UnrollFactor)
00232       : OrigLoop(OrigLoop), SE(SE), LI(LI), DT(DT), DL(DL), TLI(TLI),
00233         VF(VecWidth), UF(UnrollFactor), Builder(SE->getContext()), Induction(0),
00234         OldInduction(0), WidenMap(UnrollFactor), Legal(0) {}
00235 
00236   // Perform the actual loop widening (vectorization).
00237   void vectorize(LoopVectorizationLegality *L) {
00238     Legal = L;
00239     // Create a new empty loop. Unlink the old loop and connect the new one.
00240     createEmptyLoop();
00241     // Widen each instruction in the old loop to a new one in the new loop.
00242     // Use the Legality module to find the induction and reduction variables.
00243     vectorizeLoop();
00244     // Register the new loop and update the analysis passes.
00245     updateAnalysis();
00246   }
00247 
00248   virtual ~InnerLoopVectorizer() {}
00249 
00250 protected:
00251   /// A small list of PHINodes.
00252   typedef SmallVector<PHINode*, 4> PhiVector;
00253   /// When we unroll loops we have multiple vector values for each scalar.
00254   /// This data structure holds the unrolled and vectorized values that
00255   /// originated from one scalar instruction.
00256   typedef SmallVector<Value*, 2> VectorParts;
00257 
00258   // When we if-convert we need create edge masks. We have to cache values so
00259   // that we don't end up with exponential recursion/IR.
00260   typedef DenseMap<std::pair<BasicBlock*, BasicBlock*>,
00261                    VectorParts> EdgeMaskCache;
00262 
00263   /// \brief Add code that checks at runtime if the accessed arrays overlap.
00264   ///
00265   /// Returns a pair of instructions where the first element is the first
00266   /// instruction generated in possibly a sequence of instructions and the
00267   /// second value is the final comparator value or NULL if no check is needed.
00268   std::pair<Instruction *, Instruction *> addRuntimeCheck(Instruction *Loc);
00269 
00270   /// \brief Add checks for strides that where assumed to be 1.
00271   ///
00272   /// Returns the last check instruction and the first check instruction in the
00273   /// pair as (first, last).
00274   std::pair<Instruction *, Instruction *> addStrideCheck(Instruction *Loc);
00275 
00276   /// Create an empty loop, based on the loop ranges of the old loop.
00277   void createEmptyLoop();
00278   /// Copy and widen the instructions from the old loop.
00279   virtual void vectorizeLoop();
00280 
00281   /// \brief The Loop exit block may have single value PHI nodes where the
00282   /// incoming value is 'Undef'. While vectorizing we only handled real values
00283   /// that were defined inside the loop. Here we fix the 'undef case'.
00284   /// See PR14725.
00285   void fixLCSSAPHIs();
00286 
00287   /// A helper function that computes the predicate of the block BB, assuming
00288   /// that the header block of the loop is set to True. It returns the *entry*
00289   /// mask for the block BB.
00290   VectorParts createBlockInMask(BasicBlock *BB);
00291   /// A helper function that computes the predicate of the edge between SRC
00292   /// and DST.
00293   VectorParts createEdgeMask(BasicBlock *Src, BasicBlock *Dst);
00294 
00295   /// A helper function to vectorize a single BB within the innermost loop.
00296   void vectorizeBlockInLoop(BasicBlock *BB, PhiVector *PV);
00297 
00298   /// Vectorize a single PHINode in a block. This method handles the induction
00299   /// variable canonicalization. It supports both VF = 1 for unrolled loops and
00300   /// arbitrary length vectors.
00301   void widenPHIInstruction(Instruction *PN, VectorParts &Entry,
00302                            unsigned UF, unsigned VF, PhiVector *PV);
00303 
00304   /// Insert the new loop to the loop hierarchy and pass manager
00305   /// and update the analysis passes.
00306   void updateAnalysis();
00307 
00308   /// This instruction is un-vectorizable. Implement it as a sequence
00309   /// of scalars. If \p IfPredicateStore is true we need to 'hide' each
00310   /// scalarized instruction behind an if block predicated on the control
00311   /// dependence of the instruction.
00312   virtual void scalarizeInstruction(Instruction *Instr,
00313                                     bool IfPredicateStore=false);
00314 
00315   /// Vectorize Load and Store instructions,
00316   virtual void vectorizeMemoryInstruction(Instruction *Instr);
00317 
00318   /// Create a broadcast instruction. This method generates a broadcast
00319   /// instruction (shuffle) for loop invariant values and for the induction
00320   /// value. If this is the induction variable then we extend it to N, N+1, ...
00321   /// this is needed because each iteration in the loop corresponds to a SIMD
00322   /// element.
00323   virtual Value *getBroadcastInstrs(Value *V);
00324 
00325   /// This function adds 0, 1, 2 ... to each vector element, starting at zero.
00326   /// If Negate is set then negative numbers are added e.g. (0, -1, -2, ...).
00327   /// The sequence starts at StartIndex.
00328   virtual Value *getConsecutiveVector(Value* Val, int StartIdx, bool Negate);
00329 
00330   /// When we go over instructions in the basic block we rely on previous
00331   /// values within the current basic block or on loop invariant values.
00332   /// When we widen (vectorize) values we place them in the map. If the values
00333   /// are not within the map, they have to be loop invariant, so we simply
00334   /// broadcast them into a vector.
00335   VectorParts &getVectorValue(Value *V);
00336 
00337   /// Generate a shuffle sequence that will reverse the vector Vec.
00338   virtual Value *reverseVector(Value *Vec);
00339 
00340   /// This is a helper class that holds the vectorizer state. It maps scalar
00341   /// instructions to vector instructions. When the code is 'unrolled' then
00342   /// then a single scalar value is mapped to multiple vector parts. The parts
00343   /// are stored in the VectorPart type.
00344   struct ValueMap {
00345     /// C'tor.  UnrollFactor controls the number of vectors ('parts') that
00346     /// are mapped.
00347     ValueMap(unsigned UnrollFactor) : UF(UnrollFactor) {}
00348 
00349     /// \return True if 'Key' is saved in the Value Map.
00350     bool has(Value *Key) const { return MapStorage.count(Key); }
00351 
00352     /// Initializes a new entry in the map. Sets all of the vector parts to the
00353     /// save value in 'Val'.
00354     /// \return A reference to a vector with splat values.
00355     VectorParts &splat(Value *Key, Value *Val) {
00356       VectorParts &Entry = MapStorage[Key];
00357       Entry.assign(UF, Val);
00358       return Entry;
00359     }
00360 
00361     ///\return A reference to the value that is stored at 'Key'.
00362     VectorParts &get(Value *Key) {
00363       VectorParts &Entry = MapStorage[Key];
00364       if (Entry.empty())
00365         Entry.resize(UF);
00366       assert(Entry.size() == UF);
00367       return Entry;
00368     }
00369 
00370   private:
00371     /// The unroll factor. Each entry in the map stores this number of vector
00372     /// elements.
00373     unsigned UF;
00374 
00375     /// Map storage. We use std::map and not DenseMap because insertions to a
00376     /// dense map invalidates its iterators.
00377     std::map<Value *, VectorParts> MapStorage;
00378   };
00379 
00380   /// The original loop.
00381   Loop *OrigLoop;
00382   /// Scev analysis to use.
00383   ScalarEvolution *SE;
00384   /// Loop Info.
00385   LoopInfo *LI;
00386   /// Dominator Tree.
00387   DominatorTree *DT;
00388   /// Data Layout.
00389   const DataLayout *DL;
00390   /// Target Library Info.
00391   const TargetLibraryInfo *TLI;
00392 
00393   /// The vectorization SIMD factor to use. Each vector will have this many
00394   /// vector elements.
00395   unsigned VF;
00396 
00397 protected:
00398   /// The vectorization unroll factor to use. Each scalar is vectorized to this
00399   /// many different vector instructions.
00400   unsigned UF;
00401 
00402   /// The builder that we use
00403   IRBuilder<> Builder;
00404 
00405   // --- Vectorization state ---
00406 
00407   /// The vector-loop preheader.
00408   BasicBlock *LoopVectorPreHeader;
00409   /// The scalar-loop preheader.
00410   BasicBlock *LoopScalarPreHeader;
00411   /// Middle Block between the vector and the scalar.
00412   BasicBlock *LoopMiddleBlock;
00413   ///The ExitBlock of the scalar loop.
00414   BasicBlock *LoopExitBlock;
00415   ///The vector loop body.
00416   SmallVector<BasicBlock *, 4> LoopVectorBody;
00417   ///The scalar loop body.
00418   BasicBlock *LoopScalarBody;
00419   /// A list of all bypass blocks. The first block is the entry of the loop.
00420   SmallVector<BasicBlock *, 4> LoopBypassBlocks;
00421 
00422   /// The new Induction variable which was added to the new block.
00423   PHINode *Induction;
00424   /// The induction variable of the old basic block.
00425   PHINode *OldInduction;
00426   /// Holds the extended (to the widest induction type) start index.
00427   Value *ExtendedIdx;
00428   /// Maps scalars to widened vectors.
00429   ValueMap WidenMap;
00430   EdgeMaskCache MaskCache;
00431 
00432   LoopVectorizationLegality *Legal;
00433 };
00434 
00435 class InnerLoopUnroller : public InnerLoopVectorizer {
00436 public:
00437   InnerLoopUnroller(Loop *OrigLoop, ScalarEvolution *SE, LoopInfo *LI,
00438                     DominatorTree *DT, const DataLayout *DL,
00439                     const TargetLibraryInfo *TLI, unsigned UnrollFactor) :
00440     InnerLoopVectorizer(OrigLoop, SE, LI, DT, DL, TLI, 1, UnrollFactor) { }
00441 
00442 private:
00443   void scalarizeInstruction(Instruction *Instr,
00444                             bool IfPredicateStore = false) override;
00445   void vectorizeMemoryInstruction(Instruction *Instr) override;
00446   Value *getBroadcastInstrs(Value *V) override;
00447   Value *getConsecutiveVector(Value* Val, int StartIdx, bool Negate) override;
00448   Value *reverseVector(Value *Vec) override;
00449 };
00450 
00451 /// \brief Look for a meaningful debug location on the instruction or it's
00452 /// operands.
00453 static Instruction *getDebugLocFromInstOrOperands(Instruction *I) {
00454   if (!I)
00455     return I;
00456 
00457   DebugLoc Empty;
00458   if (I->getDebugLoc() != Empty)
00459     return I;
00460 
00461   for (User::op_iterator OI = I->op_begin(), OE = I->op_end(); OI != OE; ++OI) {
00462     if (Instruction *OpInst = dyn_cast<Instruction>(*OI))
00463       if (OpInst->getDebugLoc() != Empty)
00464         return OpInst;
00465   }
00466 
00467   return I;
00468 }
00469 
00470 /// \brief Set the debug location in the builder using the debug location in the
00471 /// instruction.
00472 static void setDebugLocFromInst(IRBuilder<> &B, const Value *Ptr) {
00473   if (const Instruction *Inst = dyn_cast_or_null<Instruction>(Ptr))
00474     B.SetCurrentDebugLocation(Inst->getDebugLoc());
00475   else
00476     B.SetCurrentDebugLocation(DebugLoc());
00477 }
00478 
00479 #ifndef NDEBUG
00480 /// \return string containing a file name and a line # for the given
00481 /// instruction.
00482 static format_object3<const char *, const char *, unsigned>
00483 getDebugLocString(const Instruction *I) {
00484   if (!I)
00485     return format<const char *, const char *, unsigned>("", "", "", 0U);
00486   MDNode *N = I->getMetadata("dbg");
00487   if (!N) {
00488     const StringRef ModuleName =
00489         I->getParent()->getParent()->getParent()->getModuleIdentifier();
00490     return format<const char *, const char *, unsigned>("%s", ModuleName.data(),
00491                                                         "", 0U);
00492   }
00493   const DILocation Loc(N);
00494   const unsigned LineNo = Loc.getLineNumber();
00495   const char *DirName = Loc.getDirectory().data();
00496   const char *FileName = Loc.getFilename().data();
00497   return format("%s/%s:%u", DirName, FileName, LineNo);
00498 }
00499 #endif
00500 
00501 /// LoopVectorizationLegality checks if it is legal to vectorize a loop, and
00502 /// to what vectorization factor.
00503 /// This class does not look at the profitability of vectorization, only the
00504 /// legality. This class has two main kinds of checks:
00505 /// * Memory checks - The code in canVectorizeMemory checks if vectorization
00506 ///   will change the order of memory accesses in a way that will change the
00507 ///   correctness of the program.
00508 /// * Scalars checks - The code in canVectorizeInstrs and canVectorizeMemory
00509 /// checks for a number of different conditions, such as the availability of a
00510 /// single induction variable, that all types are supported and vectorize-able,
00511 /// etc. This code reflects the capabilities of InnerLoopVectorizer.
00512 /// This class is also used by InnerLoopVectorizer for identifying
00513 /// induction variable and the different reduction variables.
00514 class LoopVectorizationLegality {
00515 public:
00516   unsigned NumLoads;
00517   unsigned NumStores;
00518   unsigned NumPredStores;
00519 
00520   LoopVectorizationLegality(Loop *L, ScalarEvolution *SE, const DataLayout *DL,
00521                             DominatorTree *DT, TargetLibraryInfo *TLI)
00522       : NumLoads(0), NumStores(0), NumPredStores(0), TheLoop(L), SE(SE), DL(DL),
00523         DT(DT), TLI(TLI), Induction(0), WidestIndTy(0), HasFunNoNaNAttr(false),
00524         MaxSafeDepDistBytes(-1U) {}
00525 
00526   /// This enum represents the kinds of reductions that we support.
00527   enum ReductionKind {
00528     RK_NoReduction, ///< Not a reduction.
00529     RK_IntegerAdd,  ///< Sum of integers.
00530     RK_IntegerMult, ///< Product of integers.
00531     RK_IntegerOr,   ///< Bitwise or logical OR of numbers.
00532     RK_IntegerAnd,  ///< Bitwise or logical AND of numbers.
00533     RK_IntegerXor,  ///< Bitwise or logical XOR of numbers.
00534     RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
00535     RK_FloatAdd,    ///< Sum of floats.
00536     RK_FloatMult,   ///< Product of floats.
00537     RK_FloatMinMax  ///< Min/max implemented in terms of select(cmp()).
00538   };
00539 
00540   /// This enum represents the kinds of inductions that we support.
00541   enum InductionKind {
00542     IK_NoInduction,         ///< Not an induction variable.
00543     IK_IntInduction,        ///< Integer induction variable. Step = 1.
00544     IK_ReverseIntInduction, ///< Reverse int induction variable. Step = -1.
00545     IK_PtrInduction,        ///< Pointer induction var. Step = sizeof(elem).
00546     IK_ReversePtrInduction  ///< Reverse ptr indvar. Step = - sizeof(elem).
00547   };
00548 
00549   // This enum represents the kind of minmax reduction.
00550   enum MinMaxReductionKind {
00551     MRK_Invalid,
00552     MRK_UIntMin,
00553     MRK_UIntMax,
00554     MRK_SIntMin,
00555     MRK_SIntMax,
00556     MRK_FloatMin,
00557     MRK_FloatMax
00558   };
00559 
00560   /// This struct holds information about reduction variables.
00561   struct ReductionDescriptor {
00562     ReductionDescriptor() : StartValue(0), LoopExitInstr(0),
00563       Kind(RK_NoReduction), MinMaxKind(MRK_Invalid) {}
00564 
00565     ReductionDescriptor(Value *Start, Instruction *Exit, ReductionKind K,
00566                         MinMaxReductionKind MK)
00567         : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK) {}
00568 
00569     // The starting value of the reduction.
00570     // It does not have to be zero!
00571     TrackingVH<Value> StartValue;
00572     // The instruction who's value is used outside the loop.
00573     Instruction *LoopExitInstr;
00574     // The kind of the reduction.
00575     ReductionKind Kind;
00576     // If this a min/max reduction the kind of reduction.
00577     MinMaxReductionKind MinMaxKind;
00578   };
00579 
00580   /// This POD struct holds information about a potential reduction operation.
00581   struct ReductionInstDesc {
00582     ReductionInstDesc(bool IsRedux, Instruction *I) :
00583       IsReduction(IsRedux), PatternLastInst(I), MinMaxKind(MRK_Invalid) {}
00584 
00585     ReductionInstDesc(Instruction *I, MinMaxReductionKind K) :
00586       IsReduction(true), PatternLastInst(I), MinMaxKind(K) {}
00587 
00588     // Is this instruction a reduction candidate.
00589     bool IsReduction;
00590     // The last instruction in a min/max pattern (select of the select(icmp())
00591     // pattern), or the current reduction instruction otherwise.
00592     Instruction *PatternLastInst;
00593     // If this is a min/max pattern the comparison predicate.
00594     MinMaxReductionKind MinMaxKind;
00595   };
00596 
00597   /// This struct holds information about the memory runtime legality
00598   /// check that a group of pointers do not overlap.
00599   struct RuntimePointerCheck {
00600     RuntimePointerCheck() : Need(false) {}
00601 
00602     /// Reset the state of the pointer runtime information.
00603     void reset() {
00604       Need = false;
00605       Pointers.clear();
00606       Starts.clear();
00607       Ends.clear();
00608       IsWritePtr.clear();
00609       DependencySetId.clear();
00610     }
00611 
00612     /// Insert a pointer and calculate the start and end SCEVs.
00613     void insert(ScalarEvolution *SE, Loop *Lp, Value *Ptr, bool WritePtr,
00614                 unsigned DepSetId, ValueToValueMap &Strides);
00615 
00616     /// This flag indicates if we need to add the runtime check.
00617     bool Need;
00618     /// Holds the pointers that we need to check.
00619     SmallVector<TrackingVH<Value>, 2> Pointers;
00620     /// Holds the pointer value at the beginning of the loop.
00621     SmallVector<const SCEV*, 2> Starts;
00622     /// Holds the pointer value at the end of the loop.
00623     SmallVector<const SCEV*, 2> Ends;
00624     /// Holds the information if this pointer is used for writing to memory.
00625     SmallVector<bool, 2> IsWritePtr;
00626     /// Holds the id of the set of pointers that could be dependent because of a
00627     /// shared underlying object.
00628     SmallVector<unsigned, 2> DependencySetId;
00629   };
00630 
00631   /// A struct for saving information about induction variables.
00632   struct InductionInfo {
00633     InductionInfo(Value *Start, InductionKind K) : StartValue(Start), IK(K) {}
00634     InductionInfo() : StartValue(0), IK(IK_NoInduction) {}
00635     /// Start value.
00636     TrackingVH<Value> StartValue;
00637     /// Induction kind.
00638     InductionKind IK;
00639   };
00640 
00641   /// ReductionList contains the reduction descriptors for all
00642   /// of the reductions that were found in the loop.
00643   typedef DenseMap<PHINode*, ReductionDescriptor> ReductionList;
00644 
00645   /// InductionList saves induction variables and maps them to the
00646   /// induction descriptor.
00647   typedef MapVector<PHINode*, InductionInfo> InductionList;
00648 
00649   /// Returns true if it is legal to vectorize this loop.
00650   /// This does not mean that it is profitable to vectorize this
00651   /// loop, only that it is legal to do so.
00652   bool canVectorize();
00653 
00654   /// Returns the Induction variable.
00655   PHINode *getInduction() { return Induction; }
00656 
00657   /// Returns the reduction variables found in the loop.
00658   ReductionList *getReductionVars() { return &Reductions; }
00659 
00660   /// Returns the induction variables found in the loop.
00661   InductionList *getInductionVars() { return &Inductions; }
00662 
00663   /// Returns the widest induction type.
00664   Type *getWidestInductionType() { return WidestIndTy; }
00665 
00666   /// Returns True if V is an induction variable in this loop.
00667   bool isInductionVariable(const Value *V);
00668 
00669   /// Return true if the block BB needs to be predicated in order for the loop
00670   /// to be vectorized.
00671   bool blockNeedsPredication(BasicBlock *BB);
00672 
00673   /// Check if this  pointer is consecutive when vectorizing. This happens
00674   /// when the last index of the GEP is the induction variable, or that the
00675   /// pointer itself is an induction variable.
00676   /// This check allows us to vectorize A[idx] into a wide load/store.
00677   /// Returns:
00678   /// 0 - Stride is unknown or non-consecutive.
00679   /// 1 - Address is consecutive.
00680   /// -1 - Address is consecutive, and decreasing.
00681   int isConsecutivePtr(Value *Ptr);
00682 
00683   /// Returns true if the value V is uniform within the loop.
00684   bool isUniform(Value *V);
00685 
00686   /// Returns true if this instruction will remain scalar after vectorization.
00687   bool isUniformAfterVectorization(Instruction* I) { return Uniforms.count(I); }
00688 
00689   /// Returns the information that we collected about runtime memory check.
00690   RuntimePointerCheck *getRuntimePointerCheck() { return &PtrRtCheck; }
00691 
00692   /// This function returns the identity element (or neutral element) for
00693   /// the operation K.
00694   static Constant *getReductionIdentity(ReductionKind K, Type *Tp);
00695 
00696   unsigned getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; }
00697 
00698   bool hasStride(Value *V) { return StrideSet.count(V); }
00699   bool mustCheckStrides() { return !StrideSet.empty(); }
00700   SmallPtrSet<Value *, 8>::iterator strides_begin() {
00701     return StrideSet.begin();
00702   }
00703   SmallPtrSet<Value *, 8>::iterator strides_end() { return StrideSet.end(); }
00704 
00705 private:
00706   /// Check if a single basic block loop is vectorizable.
00707   /// At this point we know that this is a loop with a constant trip count
00708   /// and we only need to check individual instructions.
00709   bool canVectorizeInstrs();
00710 
00711   /// When we vectorize loops we may change the order in which
00712   /// we read and write from memory. This method checks if it is
00713   /// legal to vectorize the code, considering only memory constrains.
00714   /// Returns true if the loop is vectorizable
00715   bool canVectorizeMemory();
00716 
00717   /// Return true if we can vectorize this loop using the IF-conversion
00718   /// transformation.
00719   bool canVectorizeWithIfConvert();
00720 
00721   /// Collect the variables that need to stay uniform after vectorization.
00722   void collectLoopUniforms();
00723 
00724   /// Return true if all of the instructions in the block can be speculatively
00725   /// executed. \p SafePtrs is a list of addresses that are known to be legal
00726   /// and we know that we can read from them without segfault.
00727   bool blockCanBePredicated(BasicBlock *BB, SmallPtrSet<Value *, 8>& SafePtrs);
00728 
00729   /// Returns True, if 'Phi' is the kind of reduction variable for type
00730   /// 'Kind'. If this is a reduction variable, it adds it to ReductionList.
00731   bool AddReductionVar(PHINode *Phi, ReductionKind Kind);
00732   /// Returns a struct describing if the instruction 'I' can be a reduction
00733   /// variable of type 'Kind'. If the reduction is a min/max pattern of
00734   /// select(icmp()) this function advances the instruction pointer 'I' from the
00735   /// compare instruction to the select instruction and stores this pointer in
00736   /// 'PatternLastInst' member of the returned struct.
00737   ReductionInstDesc isReductionInstr(Instruction *I, ReductionKind Kind,
00738                                      ReductionInstDesc &Desc);
00739   /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
00740   /// pattern corresponding to a min(X, Y) or max(X, Y).
00741   static ReductionInstDesc isMinMaxSelectCmpPattern(Instruction *I,
00742                                                     ReductionInstDesc &Prev);
00743   /// Returns the induction kind of Phi. This function may return NoInduction
00744   /// if the PHI is not an induction variable.
00745   InductionKind isInductionVariable(PHINode *Phi);
00746 
00747   /// \brief Collect memory access with loop invariant strides.
00748   ///
00749   /// Looks for accesses like "a[i * StrideA]" where "StrideA" is loop
00750   /// invariant.
00751   void collectStridedAcccess(Value *LoadOrStoreInst);
00752 
00753   /// The loop that we evaluate.
00754   Loop *TheLoop;
00755   /// Scev analysis.
00756   ScalarEvolution *SE;
00757   /// DataLayout analysis.
00758   const DataLayout *DL;
00759   /// Dominators.
00760   DominatorTree *DT;
00761   /// Target Library Info.
00762   TargetLibraryInfo *TLI;
00763 
00764   //  ---  vectorization state --- //
00765 
00766   /// Holds the integer induction variable. This is the counter of the
00767   /// loop.
00768   PHINode *Induction;
00769   /// Holds the reduction variables.
00770   ReductionList Reductions;
00771   /// Holds all of the induction variables that we found in the loop.
00772   /// Notice that inductions don't need to start at zero and that induction
00773   /// variables can be pointers.
00774   InductionList Inductions;
00775   /// Holds the widest induction type encountered.
00776   Type *WidestIndTy;
00777 
00778   /// Allowed outside users. This holds the reduction
00779   /// vars which can be accessed from outside the loop.
00780   SmallPtrSet<Value*, 4> AllowedExit;
00781   /// This set holds the variables which are known to be uniform after
00782   /// vectorization.
00783   SmallPtrSet<Instruction*, 4> Uniforms;
00784   /// We need to check that all of the pointers in this list are disjoint
00785   /// at runtime.
00786   RuntimePointerCheck PtrRtCheck;
00787   /// Can we assume the absence of NaNs.
00788   bool HasFunNoNaNAttr;
00789 
00790   unsigned MaxSafeDepDistBytes;
00791 
00792   ValueToValueMap Strides;
00793   SmallPtrSet<Value *, 8> StrideSet;
00794 };
00795 
00796 /// LoopVectorizationCostModel - estimates the expected speedups due to
00797 /// vectorization.
00798 /// In many cases vectorization is not profitable. This can happen because of
00799 /// a number of reasons. In this class we mainly attempt to predict the
00800 /// expected speedup/slowdowns due to the supported instruction set. We use the
00801 /// TargetTransformInfo to query the different backends for the cost of
00802 /// different operations.
00803 class LoopVectorizationCostModel {
00804 public:
00805   LoopVectorizationCostModel(Loop *L, ScalarEvolution *SE, LoopInfo *LI,
00806                              LoopVectorizationLegality *Legal,
00807                              const TargetTransformInfo &TTI,
00808                              const DataLayout *DL, const TargetLibraryInfo *TLI)
00809       : TheLoop(L), SE(SE), LI(LI), Legal(Legal), TTI(TTI), DL(DL), TLI(TLI) {}
00810 
00811   /// Information about vectorization costs
00812   struct VectorizationFactor {
00813     unsigned Width; // Vector width with best cost
00814     unsigned Cost; // Cost of the loop with that width
00815   };
00816   /// \return The most profitable vectorization factor and the cost of that VF.
00817   /// This method checks every power of two up to VF. If UserVF is not ZERO
00818   /// then this vectorization factor will be selected if vectorization is
00819   /// possible.
00820   VectorizationFactor selectVectorizationFactor(bool OptForSize,
00821                                                 unsigned UserVF);
00822 
00823   /// \return The size (in bits) of the widest type in the code that
00824   /// needs to be vectorized. We ignore values that remain scalar such as
00825   /// 64 bit loop indices.
00826   unsigned getWidestType();
00827 
00828   /// \return The most profitable unroll factor.
00829   /// If UserUF is non-zero then this method finds the best unroll-factor
00830   /// based on register pressure and other parameters.
00831   /// VF and LoopCost are the selected vectorization factor and the cost of the
00832   /// selected VF.
00833   unsigned selectUnrollFactor(bool OptForSize, unsigned UserUF, unsigned VF,
00834                               unsigned LoopCost);
00835 
00836   /// \brief A struct that represents some properties of the register usage
00837   /// of a loop.
00838   struct RegisterUsage {
00839     /// Holds the number of loop invariant values that are used in the loop.
00840     unsigned LoopInvariantRegs;
00841     /// Holds the maximum number of concurrent live intervals in the loop.
00842     unsigned MaxLocalUsers;
00843     /// Holds the number of instructions in the loop.
00844     unsigned NumInstructions;
00845   };
00846 
00847   /// \return  information about the register usage of the loop.
00848   RegisterUsage calculateRegisterUsage();
00849 
00850 private:
00851   /// Returns the expected execution cost. The unit of the cost does
00852   /// not matter because we use the 'cost' units to compare different
00853   /// vector widths. The cost that is returned is *not* normalized by
00854   /// the factor width.
00855   unsigned expectedCost(unsigned VF);
00856 
00857   /// Returns the execution time cost of an instruction for a given vector
00858   /// width. Vector width of one means scalar.
00859   unsigned getInstructionCost(Instruction *I, unsigned VF);
00860 
00861   /// A helper function for converting Scalar types to vector types.
00862   /// If the incoming type is void, we return void. If the VF is 1, we return
00863   /// the scalar type.
00864   static Type* ToVectorTy(Type *Scalar, unsigned VF);
00865 
00866   /// Returns whether the instruction is a load or store and will be a emitted
00867   /// as a vector operation.
00868   bool isConsecutiveLoadOrStore(Instruction *I);
00869 
00870   /// The loop that we evaluate.
00871   Loop *TheLoop;
00872   /// Scev analysis.
00873   ScalarEvolution *SE;
00874   /// Loop Info analysis.
00875   LoopInfo *LI;
00876   /// Vectorization legality.
00877   LoopVectorizationLegality *Legal;
00878   /// Vector target information.
00879   const TargetTransformInfo &TTI;
00880   /// Target data layout information.
00881   const DataLayout *DL;
00882   /// Target Library Info.
00883   const TargetLibraryInfo *TLI;
00884 };
00885 
00886 /// Utility class for getting and setting loop vectorizer hints in the form
00887 /// of loop metadata.
00888 struct LoopVectorizeHints {
00889   /// Vectorization width.
00890   unsigned Width;
00891   /// Vectorization unroll factor.
00892   unsigned Unroll;
00893   /// Vectorization forced (-1 not selected, 0 force disabled, 1 force enabled)
00894   int Force;
00895 
00896   LoopVectorizeHints(const Loop *L, bool DisableUnrolling)
00897   : Width(VectorizationFactor)
00898   , Unroll(DisableUnrolling ? 1 : VectorizationUnroll)
00899   , Force(-1)
00900   , LoopID(L->getLoopID()) {
00901     getHints(L);
00902     // The command line options override any loop metadata except for when
00903     // width == 1 which is used to indicate the loop is already vectorized.
00904     if (VectorizationFactor.getNumOccurrences() > 0 && Width != 1)
00905       Width = VectorizationFactor;
00906     if (VectorizationUnroll.getNumOccurrences() > 0)
00907       Unroll = VectorizationUnroll;
00908 
00909     DEBUG(if (DisableUnrolling && Unroll == 1)
00910             dbgs() << "LV: Unrolling disabled by the pass manager\n");
00911   }
00912 
00913   /// Return the loop vectorizer metadata prefix.
00914   static StringRef Prefix() { return "llvm.vectorizer."; }
00915 
00916   MDNode *createHint(LLVMContext &Context, StringRef Name, unsigned V) {
00917     SmallVector<Value*, 2> Vals;
00918     Vals.push_back(MDString::get(Context, Name));
00919     Vals.push_back(ConstantInt::get(Type::getInt32Ty(Context), V));
00920     return MDNode::get(Context, Vals);
00921   }
00922 
00923   /// Mark the loop L as already vectorized by setting the width to 1.
00924   void setAlreadyVectorized(Loop *L) {
00925     LLVMContext &Context = L->getHeader()->getContext();
00926 
00927     Width = 1;
00928 
00929     // Create a new loop id with one more operand for the already_vectorized
00930     // hint. If the loop already has a loop id then copy the existing operands.
00931     SmallVector<Value*, 4> Vals(1);
00932     if (LoopID)
00933       for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i)
00934         Vals.push_back(LoopID->getOperand(i));
00935 
00936     Vals.push_back(createHint(Context, Twine(Prefix(), "width").str(), Width));
00937     Vals.push_back(createHint(Context, Twine(Prefix(), "unroll").str(), 1));
00938 
00939     MDNode *NewLoopID = MDNode::get(Context, Vals);
00940     // Set operand 0 to refer to the loop id itself.
00941     NewLoopID->replaceOperandWith(0, NewLoopID);
00942 
00943     L->setLoopID(NewLoopID);
00944     if (LoopID)
00945       LoopID->replaceAllUsesWith(NewLoopID);
00946 
00947     LoopID = NewLoopID;
00948   }
00949 
00950 private:
00951   MDNode *LoopID;
00952 
00953   /// Find hints specified in the loop metadata.
00954   void getHints(const Loop *L) {
00955     if (!LoopID)
00956       return;
00957 
00958     // First operand should refer to the loop id itself.
00959     assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
00960     assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
00961 
00962     for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
00963       const MDString *S = 0;
00964       SmallVector<Value*, 4> Args;
00965 
00966       // The expected hint is either a MDString or a MDNode with the first
00967       // operand a MDString.
00968       if (const MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i))) {
00969         if (!MD || MD->getNumOperands() == 0)
00970           continue;
00971         S = dyn_cast<MDString>(MD->getOperand(0));
00972         for (unsigned i = 1, ie = MD->getNumOperands(); i < ie; ++i)
00973           Args.push_back(MD->getOperand(i));
00974       } else {
00975         S = dyn_cast<MDString>(LoopID->getOperand(i));
00976         assert(Args.size() == 0 && "too many arguments for MDString");
00977       }
00978 
00979       if (!S)
00980         continue;
00981 
00982       // Check if the hint starts with the vectorizer prefix.
00983       StringRef Hint = S->getString();
00984       if (!Hint.startswith(Prefix()))
00985         continue;
00986       // Remove the prefix.
00987       Hint = Hint.substr(Prefix().size(), StringRef::npos);
00988 
00989       if (Args.size() == 1)
00990         getHint(Hint, Args[0]);
00991     }
00992   }
00993 
00994   // Check string hint with one operand.
00995   void getHint(StringRef Hint, Value *Arg) {
00996     const ConstantInt *C = dyn_cast<ConstantInt>(Arg);
00997     if (!C) return;
00998     unsigned Val = C->getZExtValue();
00999 
01000     if (Hint == "width") {
01001       if (isPowerOf2_32(Val) && Val <= MaxVectorWidth)
01002         Width = Val;
01003       else
01004         DEBUG(dbgs() << "LV: ignoring invalid width hint metadata\n");
01005     } else if (Hint == "unroll") {
01006       if (isPowerOf2_32(Val) && Val <= MaxUnrollFactor)
01007         Unroll = Val;
01008       else
01009         DEBUG(dbgs() << "LV: ignoring invalid unroll hint metadata\n");
01010     } else if (Hint == "enable") {
01011       if (C->getBitWidth() == 1)
01012         Force = Val;
01013       else
01014         DEBUG(dbgs() << "LV: ignoring invalid enable hint metadata\n");
01015     } else {
01016       DEBUG(dbgs() << "LV: ignoring unknown hint " << Hint << '\n');
01017     }
01018   }
01019 };
01020 
01021 static void addInnerLoop(Loop &L, SmallVectorImpl<Loop *> &V) {
01022   if (L.empty())
01023     return V.push_back(&L);
01024 
01025   for (Loop *InnerL : L)
01026     addInnerLoop(*InnerL, V);
01027 }
01028 
01029 /// The LoopVectorize Pass.
01030 struct LoopVectorize : public FunctionPass {
01031   /// Pass identification, replacement for typeid
01032   static char ID;
01033 
01034   explicit LoopVectorize(bool NoUnrolling = false, bool AlwaysVectorize = true)
01035     : FunctionPass(ID),
01036       DisableUnrolling(NoUnrolling),
01037       AlwaysVectorize(AlwaysVectorize) {
01038     initializeLoopVectorizePass(*PassRegistry::getPassRegistry());
01039   }
01040 
01041   ScalarEvolution *SE;
01042   const DataLayout *DL;
01043   LoopInfo *LI;
01044   TargetTransformInfo *TTI;
01045   DominatorTree *DT;
01046   BlockFrequencyInfo *BFI;
01047   TargetLibraryInfo *TLI;
01048   bool DisableUnrolling;
01049   bool AlwaysVectorize;
01050 
01051   BlockFrequency ColdEntryFreq;
01052 
01053   bool runOnFunction(Function &F) override {
01054     SE = &getAnalysis<ScalarEvolution>();
01055     DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
01056     DL = DLP ? &DLP->getDataLayout() : 0;
01057     LI = &getAnalysis<LoopInfo>();
01058     TTI = &getAnalysis<TargetTransformInfo>();
01059     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
01060     BFI = &getAnalysis<BlockFrequencyInfo>();
01061     TLI = getAnalysisIfAvailable<TargetLibraryInfo>();
01062 
01063     // Compute some weights outside of the loop over the loops. Compute this
01064     // using a BranchProbability to re-use its scaling math.
01065     const BranchProbability ColdProb(1, 5); // 20%
01066     ColdEntryFreq = BlockFrequency(BFI->getEntryFreq()) * ColdProb;
01067 
01068     // If the target claims to have no vector registers don't attempt
01069     // vectorization.
01070     if (!TTI->getNumberOfRegisters(true))
01071       return false;
01072 
01073     if (DL == NULL) {
01074       DEBUG(dbgs() << "\nLV: Not vectorizing " << F.getName()
01075                    << ": Missing data layout\n");
01076       return false;
01077     }
01078 
01079     // Build up a worklist of inner-loops to vectorize. This is necessary as
01080     // the act of vectorizing or partially unrolling a loop creates new loops
01081     // and can invalidate iterators across the loops.
01082     SmallVector<Loop *, 8> Worklist;
01083 
01084     for (Loop *L : *LI)
01085       addInnerLoop(*L, Worklist);
01086 
01087     LoopsAnalyzed += Worklist.size();
01088 
01089     // Now walk the identified inner loops.
01090     bool Changed = false;
01091     while (!Worklist.empty())
01092       Changed |= processLoop(Worklist.pop_back_val());
01093 
01094     // Process each loop nest in the function.
01095     return Changed;
01096   }
01097 
01098   bool processLoop(Loop *L) {
01099     assert(L->empty() && "Only process inner loops.");
01100     DEBUG(dbgs() << "\nLV: Checking a loop in \""
01101                  << L->getHeader()->getParent()->getName() << "\" from "
01102                  << getDebugLocString(L->getHeader()->getFirstNonPHIOrDbg())
01103                  << "\n");
01104 
01105     LoopVectorizeHints Hints(L, DisableUnrolling);
01106 
01107     DEBUG(dbgs() << "LV: Loop hints:"
01108                  << " force=" << (Hints.Force == 0
01109                                       ? "disabled"
01110                                       : (Hints.Force == 1 ? "enabled" : "?"))
01111                  << " width=" << Hints.Width << " unroll=" << Hints.Unroll
01112                  << "\n");
01113 
01114     if (Hints.Force == 0) {
01115       DEBUG(dbgs() << "LV: Not vectorizing: #pragma vectorize disable.\n");
01116       return false;
01117     }
01118 
01119     if (!AlwaysVectorize && Hints.Force != 1) {
01120       DEBUG(dbgs() << "LV: Not vectorizing: No #pragma vectorize enable.\n");
01121       return false;
01122     }
01123 
01124     if (Hints.Width == 1 && Hints.Unroll == 1) {
01125       DEBUG(dbgs() << "LV: Not vectorizing: Disabled/already vectorized.\n");
01126       return false;
01127     }
01128 
01129     // Check if it is legal to vectorize the loop.
01130     LoopVectorizationLegality LVL(L, SE, DL, DT, TLI);
01131     if (!LVL.canVectorize()) {
01132       DEBUG(dbgs() << "LV: Not vectorizing: Cannot prove legality.\n");
01133       return false;
01134     }
01135 
01136     // Use the cost model.
01137     LoopVectorizationCostModel CM(L, SE, LI, &LVL, *TTI, DL, TLI);
01138 
01139     // Check the function attributes to find out if this function should be
01140     // optimized for size.
01141     Function *F = L->getHeader()->getParent();
01142     bool OptForSize =
01143         Hints.Force != 1 && F->hasFnAttribute(Attribute::OptimizeForSize);
01144 
01145     // Compute the weighted frequency of this loop being executed and see if it
01146     // is less than 20% of the function entry baseline frequency. Note that we
01147     // always have a canonical loop here because we think we *can* vectoriez.
01148     // FIXME: This is hidden behind a flag due to pervasive problems with
01149     // exactly what block frequency models.
01150     if (LoopVectorizeWithBlockFrequency) {
01151       BlockFrequency LoopEntryFreq = BFI->getBlockFreq(L->getLoopPreheader());
01152       if (Hints.Force != 1 && LoopEntryFreq < ColdEntryFreq)
01153         OptForSize = true;
01154     }
01155 
01156     // Check the function attributes to see if implicit floats are allowed.a
01157     // FIXME: This check doesn't seem possibly correct -- what if the loop is
01158     // an integer loop and the vector instructions selected are purely integer
01159     // vector instructions?
01160     if (F->hasFnAttribute(Attribute::NoImplicitFloat)) {
01161       DEBUG(dbgs() << "LV: Can't vectorize when the NoImplicitFloat"
01162             "attribute is used.\n");
01163       return false;
01164     }
01165 
01166     // Select the optimal vectorization factor.
01167     const LoopVectorizationCostModel::VectorizationFactor VF =
01168                           CM.selectVectorizationFactor(OptForSize, Hints.Width);
01169     // Select the unroll factor.
01170     const unsigned UF = CM.selectUnrollFactor(OptForSize, Hints.Unroll, VF.Width,
01171                                         VF.Cost);
01172 
01173     DEBUG(dbgs() << "LV: Found a vectorizable loop ("
01174                  << VF.Width << ") in "
01175                  << getDebugLocString(L->getHeader()->getFirstNonPHIOrDbg())
01176                  << '\n');
01177     DEBUG(dbgs() << "LV: Unroll Factor is " << UF << '\n');
01178 
01179     if (VF.Width == 1) {
01180       DEBUG(dbgs() << "LV: Vectorization is possible but not beneficial.\n");
01181       if (UF == 1)
01182         return false;
01183       DEBUG(dbgs() << "LV: Trying to at least unroll the loops.\n");
01184       // We decided not to vectorize, but we may want to unroll.
01185       InnerLoopUnroller Unroller(L, SE, LI, DT, DL, TLI, UF);
01186       Unroller.vectorize(&LVL);
01187     } else {
01188       // If we decided that it is *legal* to vectorize the loop then do it.
01189       InnerLoopVectorizer LB(L, SE, LI, DT, DL, TLI, VF.Width, UF);
01190       LB.vectorize(&LVL);
01191       ++LoopsVectorized;
01192     }
01193 
01194     // Mark the loop as already vectorized to avoid vectorizing again.
01195     Hints.setAlreadyVectorized(L);
01196 
01197     DEBUG(verifyFunction(*L->getHeader()->getParent()));
01198     return true;
01199   }
01200 
01201   void getAnalysisUsage(AnalysisUsage &AU) const override {
01202     AU.addRequiredID(LoopSimplifyID);
01203     AU.addRequiredID(LCSSAID);
01204     AU.addRequired<BlockFrequencyInfo>();
01205     AU.addRequired<DominatorTreeWrapperPass>();
01206     AU.addRequired<LoopInfo>();
01207     AU.addRequired<ScalarEvolution>();
01208     AU.addRequired<TargetTransformInfo>();
01209     AU.addPreserved<LoopInfo>();
01210     AU.addPreserved<DominatorTreeWrapperPass>();
01211   }
01212 
01213 };
01214 
01215 } // end anonymous namespace
01216 
01217 //===----------------------------------------------------------------------===//
01218 // Implementation of LoopVectorizationLegality, InnerLoopVectorizer and
01219 // LoopVectorizationCostModel.
01220 //===----------------------------------------------------------------------===//
01221 
01222 static Value *stripIntegerCast(Value *V) {
01223   if (CastInst *CI = dyn_cast<CastInst>(V))
01224     if (CI->getOperand(0)->getType()->isIntegerTy())
01225       return CI->getOperand(0);
01226   return V;
01227 }
01228 
01229 ///\brief Replaces the symbolic stride in a pointer SCEV expression by one.
01230 ///
01231 /// If \p OrigPtr is not null, use it to look up the stride value instead of
01232 /// \p Ptr.
01233 static const SCEV *replaceSymbolicStrideSCEV(ScalarEvolution *SE,
01234                                              ValueToValueMap &PtrToStride,
01235                                              Value *Ptr, Value *OrigPtr = 0) {
01236 
01237   const SCEV *OrigSCEV = SE->getSCEV(Ptr);
01238 
01239   // If there is an entry in the map return the SCEV of the pointer with the
01240   // symbolic stride replaced by one.
01241   ValueToValueMap::iterator SI = PtrToStride.find(OrigPtr ? OrigPtr : Ptr);
01242   if (SI != PtrToStride.end()) {
01243     Value *StrideVal = SI->second;
01244 
01245     // Strip casts.
01246     StrideVal = stripIntegerCast(StrideVal);
01247 
01248     // Replace symbolic stride by one.
01249     Value *One = ConstantInt::get(StrideVal->getType(), 1);
01250     ValueToValueMap RewriteMap;
01251     RewriteMap[StrideVal] = One;
01252 
01253     const SCEV *ByOne =
01254         SCEVParameterRewriter::rewrite(OrigSCEV, *SE, RewriteMap, true);
01255     DEBUG(dbgs() << "LV: Replacing SCEV: " << *OrigSCEV << " by: " << *ByOne
01256                  << "\n");
01257     return ByOne;
01258   }
01259 
01260   // Otherwise, just return the SCEV of the original pointer.
01261   return SE->getSCEV(Ptr);
01262 }
01263 
01264 void LoopVectorizationLegality::RuntimePointerCheck::insert(
01265     ScalarEvolution *SE, Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId,
01266     ValueToValueMap &Strides) {
01267   // Get the stride replaced scev.
01268   const SCEV *Sc = replaceSymbolicStrideSCEV(SE, Strides, Ptr);
01269   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc);
01270   assert(AR && "Invalid addrec expression");
01271   const SCEV *Ex = SE->getBackedgeTakenCount(Lp);
01272   const SCEV *ScEnd = AR->evaluateAtIteration(Ex, *SE);
01273   Pointers.push_back(Ptr);
01274   Starts.push_back(AR->getStart());
01275   Ends.push_back(ScEnd);
01276   IsWritePtr.push_back(WritePtr);
01277   DependencySetId.push_back(DepSetId);
01278 }
01279 
01280 Value *InnerLoopVectorizer::getBroadcastInstrs(Value *V) {
01281   // We need to place the broadcast of invariant variables outside the loop.
01282   Instruction *Instr = dyn_cast<Instruction>(V);
01283   bool NewInstr =
01284       (Instr && std::find(LoopVectorBody.begin(), LoopVectorBody.end(),
01285                           Instr->getParent()) != LoopVectorBody.end());
01286   bool Invariant = OrigLoop->isLoopInvariant(V) && !NewInstr;
01287 
01288   // Place the code for broadcasting invariant variables in the new preheader.
01289   IRBuilder<>::InsertPointGuard Guard(Builder);
01290   if (Invariant)
01291     Builder.SetInsertPoint(LoopVectorPreHeader->getTerminator());
01292 
01293   // Broadcast the scalar into all locations in the vector.
01294   Value *Shuf = Builder.CreateVectorSplat(VF, V, "broadcast");
01295 
01296   return Shuf;
01297 }
01298 
01299 Value *InnerLoopVectorizer::getConsecutiveVector(Value* Val, int StartIdx,
01300                                                  bool Negate) {
01301   assert(Val->getType()->isVectorTy() && "Must be a vector");
01302   assert(Val->getType()->getScalarType()->isIntegerTy() &&
01303          "Elem must be an integer");
01304   // Create the types.
01305   Type *ITy = Val->getType()->getScalarType();
01306   VectorType *Ty = cast<VectorType>(Val->getType());
01307   int VLen = Ty->getNumElements();
01308   SmallVector<Constant*, 8> Indices;
01309 
01310   // Create a vector of consecutive numbers from zero to VF.
01311   for (int i = 0; i < VLen; ++i) {
01312     int64_t Idx = Negate ? (-i) : i;
01313     Indices.push_back(ConstantInt::get(ITy, StartIdx + Idx, Negate));
01314   }
01315 
01316   // Add the consecutive indices to the vector value.
01317   Constant *Cv = ConstantVector::get(Indices);
01318   assert(Cv->getType() == Val->getType() && "Invalid consecutive vec");
01319   return Builder.CreateAdd(Val, Cv, "induction");
01320 }
01321 
01322 /// \brief Find the operand of the GEP that should be checked for consecutive
01323 /// stores. This ignores trailing indices that have no effect on the final
01324 /// pointer.
01325 static unsigned getGEPInductionOperand(const DataLayout *DL,
01326                                        const GetElementPtrInst *Gep) {
01327   unsigned LastOperand = Gep->getNumOperands() - 1;
01328   unsigned GEPAllocSize = DL->getTypeAllocSize(
01329       cast<PointerType>(Gep->getType()->getScalarType())->getElementType());
01330 
01331   // Walk backwards and try to peel off zeros.
01332   while (LastOperand > 1 && match(Gep->getOperand(LastOperand), m_Zero())) {
01333     // Find the type we're currently indexing into.
01334     gep_type_iterator GEPTI = gep_type_begin(Gep);
01335     std::advance(GEPTI, LastOperand - 1);
01336 
01337     // If it's a type with the same allocation size as the result of the GEP we
01338     // can peel off the zero index.
01339     if (DL->getTypeAllocSize(*GEPTI) != GEPAllocSize)
01340       break;
01341     --LastOperand;
01342   }
01343 
01344   return LastOperand;
01345 }
01346 
01347 int LoopVectorizationLegality::isConsecutivePtr(Value *Ptr) {
01348   assert(Ptr->getType()->isPointerTy() && "Unexpected non-ptr");
01349   // Make sure that the pointer does not point to structs.
01350   if (Ptr->getType()->getPointerElementType()->isAggregateType())
01351     return 0;
01352 
01353   // If this value is a pointer induction variable we know it is consecutive.
01354   PHINode *Phi = dyn_cast_or_null<PHINode>(Ptr);
01355   if (Phi && Inductions.count(Phi)) {
01356     InductionInfo II = Inductions[Phi];
01357     if (IK_PtrInduction == II.IK)
01358       return 1;
01359     else if (IK_ReversePtrInduction == II.IK)
01360       return -1;
01361   }
01362 
01363   GetElementPtrInst *Gep = dyn_cast_or_null<GetElementPtrInst>(Ptr);
01364   if (!Gep)
01365     return 0;
01366 
01367   unsigned NumOperands = Gep->getNumOperands();
01368   Value *GpPtr = Gep->getPointerOperand();
01369   // If this GEP value is a consecutive pointer induction variable and all of
01370   // the indices are constant then we know it is consecutive. We can
01371   Phi = dyn_cast<PHINode>(GpPtr);
01372   if (Phi && Inductions.count(Phi)) {
01373 
01374     // Make sure that the pointer does not point to structs.
01375     PointerType *GepPtrType = cast<PointerType>(GpPtr->getType());
01376     if (GepPtrType->getElementType()->isAggregateType())
01377       return 0;
01378 
01379     // Make sure that all of the index operands are loop invariant.
01380     for (unsigned i = 1; i < NumOperands; ++i)
01381       if (!SE->isLoopInvariant(SE->getSCEV(Gep->getOperand(i)), TheLoop))
01382         return 0;
01383 
01384     InductionInfo II = Inductions[Phi];
01385     if (IK_PtrInduction == II.IK)
01386       return 1;
01387     else if (IK_ReversePtrInduction == II.IK)
01388       return -1;
01389   }
01390 
01391   unsigned InductionOperand = getGEPInductionOperand(DL, Gep);
01392 
01393   // Check that all of the gep indices are uniform except for our induction
01394   // operand.
01395   for (unsigned i = 0; i != NumOperands; ++i)
01396     if (i != InductionOperand &&
01397         !SE->isLoopInvariant(SE->getSCEV(Gep->getOperand(i)), TheLoop))
01398       return 0;
01399 
01400   // We can emit wide load/stores only if the last non-zero index is the
01401   // induction variable.
01402   const SCEV *Last = 0;
01403   if (!Strides.count(Gep))
01404     Last = SE->getSCEV(Gep->getOperand(InductionOperand));
01405   else {
01406     // Because of the multiplication by a stride we can have a s/zext cast.
01407     // We are going to replace this stride by 1 so the cast is safe to ignore.
01408     //
01409     //  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
01410     //  %0 = trunc i64 %indvars.iv to i32
01411     //  %mul = mul i32 %0, %Stride1
01412     //  %idxprom = zext i32 %mul to i64  << Safe cast.
01413     //  %arrayidx = getelementptr inbounds i32* %B, i64 %idxprom
01414     //
01415     Last = replaceSymbolicStrideSCEV(SE, Strides,
01416                                      Gep->getOperand(InductionOperand), Gep);
01417     if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(Last))
01418       Last =
01419           (C->getSCEVType() == scSignExtend || C->getSCEVType() == scZeroExtend)
01420               ? C->getOperand()
01421               : Last;
01422   }
01423   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Last)) {
01424     const SCEV *Step = AR->getStepRecurrence(*SE);
01425 
01426     // The memory is consecutive because the last index is consecutive
01427     // and all other indices are loop invariant.
01428     if (Step->isOne())
01429       return 1;
01430     if (Step->isAllOnesValue())
01431       return -1;
01432   }
01433 
01434   return 0;
01435 }
01436 
01437 bool LoopVectorizationLegality::isUniform(Value *V) {
01438   return (SE->isLoopInvariant(SE->getSCEV(V), TheLoop));
01439 }
01440 
01441 InnerLoopVectorizer::VectorParts&
01442 InnerLoopVectorizer::getVectorValue(Value *V) {
01443   assert(V != Induction && "The new induction variable should not be used.");
01444   assert(!V->getType()->isVectorTy() && "Can't widen a vector");
01445 
01446   // If we have a stride that is replaced by one, do it here.
01447   if (Legal->hasStride(V))
01448     V = ConstantInt::get(V->getType(), 1);
01449 
01450   // If we have this scalar in the map, return it.
01451   if (WidenMap.has(V))
01452     return WidenMap.get(V);
01453 
01454   // If this scalar is unknown, assume that it is a constant or that it is
01455   // loop invariant. Broadcast V and save the value for future uses.
01456   Value *B = getBroadcastInstrs(V);
01457   return WidenMap.splat(V, B);
01458 }
01459 
01460 Value *InnerLoopVectorizer::reverseVector(Value *Vec) {
01461   assert(Vec->getType()->isVectorTy() && "Invalid type");
01462   SmallVector<Constant*, 8> ShuffleMask;
01463   for (unsigned i = 0; i < VF; ++i)
01464     ShuffleMask.push_back(Builder.getInt32(VF - i - 1));
01465 
01466   return Builder.CreateShuffleVector(Vec, UndefValue::get(Vec->getType()),
01467                                      ConstantVector::get(ShuffleMask),
01468                                      "reverse");
01469 }
01470 
01471 void InnerLoopVectorizer::vectorizeMemoryInstruction(Instruction *Instr) {
01472   // Attempt to issue a wide load.
01473   LoadInst *LI = dyn_cast<LoadInst>(Instr);
01474   StoreInst *SI = dyn_cast<StoreInst>(Instr);
01475 
01476   assert((LI || SI) && "Invalid Load/Store instruction");
01477 
01478   Type *ScalarDataTy = LI ? LI->getType() : SI->getValueOperand()->getType();
01479   Type *DataTy = VectorType::get(ScalarDataTy, VF);
01480   Value *Ptr = LI ? LI->getPointerOperand() : SI->getPointerOperand();
01481   unsigned Alignment = LI ? LI->getAlignment() : SI->getAlignment();
01482   // An alignment of 0 means target abi alignment. We need to use the scalar's
01483   // target abi alignment in such a case.
01484   if (!Alignment)
01485     Alignment = DL->getABITypeAlignment(ScalarDataTy);
01486   unsigned AddressSpace = Ptr->getType()->getPointerAddressSpace();
01487   unsigned ScalarAllocatedSize = DL->getTypeAllocSize(ScalarDataTy);
01488   unsigned VectorElementSize = DL->getTypeStoreSize(DataTy)/VF;
01489 
01490   if (SI && Legal->blockNeedsPredication(SI->getParent()))
01491     return scalarizeInstruction(Instr, true);
01492 
01493   if (ScalarAllocatedSize != VectorElementSize)
01494     return scalarizeInstruction(Instr);
01495 
01496   // If the pointer is loop invariant or if it is non-consecutive,
01497   // scalarize the load.
01498   int ConsecutiveStride = Legal->isConsecutivePtr(Ptr);
01499   bool Reverse = ConsecutiveStride < 0;
01500   bool UniformLoad = LI && Legal->isUniform(Ptr);
01501   if (!ConsecutiveStride || UniformLoad)
01502     return scalarizeInstruction(Instr);
01503 
01504   Constant *Zero = Builder.getInt32(0);
01505   VectorParts &Entry = WidenMap.get(Instr);
01506 
01507   // Handle consecutive loads/stores.
01508   GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr);
01509   if (Gep && Legal->isInductionVariable(Gep->getPointerOperand())) {
01510     setDebugLocFromInst(Builder, Gep);
01511     Value *PtrOperand = Gep->getPointerOperand();
01512     Value *FirstBasePtr = getVectorValue(PtrOperand)[0];
01513     FirstBasePtr = Builder.CreateExtractElement(FirstBasePtr, Zero);
01514 
01515     // Create the new GEP with the new induction variable.
01516     GetElementPtrInst *Gep2 = cast<GetElementPtrInst>(Gep->clone());
01517     Gep2->setOperand(0, FirstBasePtr);
01518     Gep2->setName("gep.indvar.base");
01519     Ptr = Builder.Insert(Gep2);
01520   } else if (Gep) {
01521     setDebugLocFromInst(Builder, Gep);
01522     assert(SE->isLoopInvariant(SE->getSCEV(Gep->getPointerOperand()),
01523                                OrigLoop) && "Base ptr must be invariant");
01524 
01525     // The last index does not have to be the induction. It can be
01526     // consecutive and be a function of the index. For example A[I+1];
01527     unsigned NumOperands = Gep->getNumOperands();
01528     unsigned InductionOperand = getGEPInductionOperand(DL, Gep);
01529     // Create the new GEP with the new induction variable.
01530     GetElementPtrInst *Gep2 = cast<GetElementPtrInst>(Gep->clone());
01531 
01532     for (unsigned i = 0; i < NumOperands; ++i) {
01533       Value *GepOperand = Gep->getOperand(i);
01534       Instruction *GepOperandInst = dyn_cast<Instruction>(GepOperand);
01535 
01536       // Update last index or loop invariant instruction anchored in loop.
01537       if (i == InductionOperand ||
01538           (GepOperandInst && OrigLoop->contains(GepOperandInst))) {
01539         assert((i == InductionOperand ||
01540                SE->isLoopInvariant(SE->getSCEV(GepOperandInst), OrigLoop)) &&
01541                "Must be last index or loop invariant");
01542 
01543         VectorParts &GEPParts = getVectorValue(GepOperand);
01544         Value *Index = GEPParts[0];
01545         Index = Builder.CreateExtractElement(Index, Zero);
01546         Gep2->setOperand(i, Index);
01547         Gep2->setName("gep.indvar.idx");
01548       }
01549     }
01550     Ptr = Builder.Insert(Gep2);
01551   } else {
01552     // Use the induction element ptr.
01553     assert(isa<PHINode>(Ptr) && "Invalid induction ptr");
01554     setDebugLocFromInst(Builder, Ptr);
01555     VectorParts &PtrVal = getVectorValue(Ptr);
01556     Ptr = Builder.CreateExtractElement(PtrVal[0], Zero);
01557   }
01558 
01559   // Handle Stores:
01560   if (SI) {
01561     assert(!Legal->isUniform(SI->getPointerOperand()) &&
01562            "We do not allow storing to uniform addresses");
01563     setDebugLocFromInst(Builder, SI);
01564     // We don't want to update the value in the map as it might be used in
01565     // another expression. So don't use a reference type for "StoredVal".
01566     VectorParts StoredVal = getVectorValue(SI->getValueOperand());
01567 
01568     for (unsigned Part = 0; Part < UF; ++Part) {
01569       // Calculate the pointer for the specific unroll-part.
01570       Value *PartPtr = Builder.CreateGEP(Ptr, Builder.getInt32(Part * VF));
01571 
01572       if (Reverse) {
01573         // If we store to reverse consecutive memory locations then we need
01574         // to reverse the order of elements in the stored value.
01575         StoredVal[Part] = reverseVector(StoredVal[Part]);
01576         // If the address is consecutive but reversed, then the
01577         // wide store needs to start at the last vector element.
01578         PartPtr = Builder.CreateGEP(Ptr, Builder.getInt32(-Part * VF));
01579         PartPtr = Builder.CreateGEP(PartPtr, Builder.getInt32(1 - VF));
01580       }
01581 
01582       Value *VecPtr = Builder.CreateBitCast(PartPtr,
01583                                             DataTy->getPointerTo(AddressSpace));
01584       Builder.CreateStore(StoredVal[Part], VecPtr)->setAlignment(Alignment);
01585     }
01586     return;
01587   }
01588 
01589   // Handle loads.
01590   assert(LI && "Must have a load instruction");
01591   setDebugLocFromInst(Builder, LI);
01592   for (unsigned Part = 0; Part < UF; ++Part) {
01593     // Calculate the pointer for the specific unroll-part.
01594     Value *PartPtr = Builder.CreateGEP(Ptr, Builder.getInt32(Part * VF));
01595 
01596     if (Reverse) {
01597       // If the address is consecutive but reversed, then the
01598       // wide store needs to start at the last vector element.
01599       PartPtr = Builder.CreateGEP(Ptr, Builder.getInt32(-Part * VF));
01600       PartPtr = Builder.CreateGEP(PartPtr, Builder.getInt32(1 - VF));
01601     }
01602 
01603     Value *VecPtr = Builder.CreateBitCast(PartPtr,
01604                                           DataTy->getPointerTo(AddressSpace));
01605     Value *LI = Builder.CreateLoad(VecPtr, "wide.load");
01606     cast<LoadInst>(LI)->setAlignment(Alignment);
01607     Entry[Part] = Reverse ? reverseVector(LI) :  LI;
01608   }
01609 }
01610 
01611 void InnerLoopVectorizer::scalarizeInstruction(Instruction *Instr, bool IfPredicateStore) {
01612   assert(!Instr->getType()->isAggregateType() && "Can't handle vectors");
01613   // Holds vector parameters or scalars, in case of uniform vals.
01614   SmallVector<VectorParts, 4> Params;
01615 
01616   setDebugLocFromInst(Builder, Instr);
01617 
01618   // Find all of the vectorized parameters.
01619   for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) {
01620     Value *SrcOp = Instr->getOperand(op);
01621 
01622     // If we are accessing the old induction variable, use the new one.
01623     if (SrcOp == OldInduction) {
01624       Params.push_back(getVectorValue(SrcOp));
01625       continue;
01626     }
01627 
01628     // Try using previously calculated values.
01629     Instruction *SrcInst = dyn_cast<Instruction>(SrcOp);
01630 
01631     // If the src is an instruction that appeared earlier in the basic block
01632     // then it should already be vectorized.
01633     if (SrcInst && OrigLoop->contains(SrcInst)) {
01634       assert(WidenMap.has(SrcInst) && "Source operand is unavailable");
01635       // The parameter is a vector value from earlier.
01636       Params.push_back(WidenMap.get(SrcInst));
01637     } else {
01638       // The parameter is a scalar from outside the loop. Maybe even a constant.
01639       VectorParts Scalars;
01640       Scalars.append(UF, SrcOp);
01641       Params.push_back(Scalars);
01642     }
01643   }
01644 
01645   assert(Params.size() == Instr->getNumOperands() &&
01646          "Invalid number of operands");
01647 
01648   // Does this instruction return a value ?
01649   bool IsVoidRetTy = Instr->getType()->isVoidTy();
01650 
01651   Value *UndefVec = IsVoidRetTy ? 0 :
01652     UndefValue::get(VectorType::get(Instr->getType(), VF));
01653   // Create a new entry in the WidenMap and initialize it to Undef or Null.
01654   VectorParts &VecResults = WidenMap.splat(Instr, UndefVec);
01655 
01656   Instruction *InsertPt = Builder.GetInsertPoint();
01657   BasicBlock *IfBlock = Builder.GetInsertBlock();
01658   BasicBlock *CondBlock = 0;
01659 
01660   VectorParts Cond;
01661   Loop *VectorLp = 0;
01662   if (IfPredicateStore) {
01663     assert(Instr->getParent()->getSinglePredecessor() &&
01664            "Only support single predecessor blocks");
01665     Cond = createEdgeMask(Instr->getParent()->getSinglePredecessor(),
01666                           Instr->getParent());
01667     VectorLp = LI->getLoopFor(IfBlock);
01668     assert(VectorLp && "Must have a loop for this block");
01669   }
01670 
01671   // For each vector unroll 'part':
01672   for (unsigned Part = 0; Part < UF; ++Part) {
01673     // For each scalar that we create:
01674     for (unsigned Width = 0; Width < VF; ++Width) {
01675 
01676       // Start if-block.
01677       Value *Cmp = 0;
01678       if (IfPredicateStore) {
01679         Cmp = Builder.CreateExtractElement(Cond[Part], Builder.getInt32(Width));
01680         Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Cmp, ConstantInt::get(Cmp->getType(), 1));
01681         CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.store");
01682         LoopVectorBody.push_back(CondBlock);
01683         VectorLp->addBasicBlockToLoop(CondBlock, LI->getBase());
01684         // Update Builder with newly created basic block.
01685         Builder.SetInsertPoint(InsertPt);
01686       }
01687 
01688       Instruction *Cloned = Instr->clone();
01689       if (!IsVoidRetTy)
01690         Cloned->setName(Instr->getName() + ".cloned");
01691       // Replace the operands of the cloned instructions with extracted scalars.
01692       for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) {
01693         Value *Op = Params[op][Part];
01694         // Param is a vector. Need to extract the right lane.
01695         if (Op->getType()->isVectorTy())
01696           Op = Builder.CreateExtractElement(Op, Builder.getInt32(Width));
01697         Cloned->setOperand(op, Op);
01698       }
01699 
01700       // Place the cloned scalar in the new loop.
01701       Builder.Insert(Cloned);
01702 
01703       // If the original scalar returns a value we need to place it in a vector
01704       // so that future users will be able to use it.
01705       if (!IsVoidRetTy)
01706         VecResults[Part] = Builder.CreateInsertElement(VecResults[Part], Cloned,
01707                                                        Builder.getInt32(Width));
01708       // End if-block.
01709       if (IfPredicateStore) {
01710          BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else");
01711          LoopVectorBody.push_back(NewIfBlock);
01712          VectorLp->addBasicBlockToLoop(NewIfBlock, LI->getBase());
01713          Builder.SetInsertPoint(InsertPt);
01714          Instruction *OldBr = IfBlock->getTerminator();
01715          BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
01716          OldBr->eraseFromParent();
01717          IfBlock = NewIfBlock;
01718       }
01719     }
01720   }
01721 }
01722 
01723 static Instruction *getFirstInst(Instruction *FirstInst, Value *V,
01724                                  Instruction *Loc) {
01725   if (FirstInst)
01726     return FirstInst;
01727   if (Instruction *I = dyn_cast<Instruction>(V))
01728     return I->getParent() == Loc->getParent() ? I : 0;
01729   return 0;
01730 }
01731 
01732 std::pair<Instruction *, Instruction *>
01733 InnerLoopVectorizer::addStrideCheck(Instruction *Loc) {
01734   Instruction *tnullptr = 0;
01735   if (!Legal->mustCheckStrides())
01736     return std::pair<Instruction *, Instruction *>(tnullptr, tnullptr);
01737 
01738   IRBuilder<> ChkBuilder(Loc);
01739 
01740   // Emit checks.
01741   Value *Check = 0;
01742   Instruction *FirstInst = 0;
01743   for (SmallPtrSet<Value *, 8>::iterator SI = Legal->strides_begin(),
01744                                          SE = Legal->strides_end();
01745        SI != SE; ++SI) {
01746     Value *Ptr = stripIntegerCast(*SI);
01747     Value *C = ChkBuilder.CreateICmpNE(Ptr, ConstantInt::get(Ptr->getType(), 1),
01748                                        "stride.chk");
01749     // Store the first instruction we create.
01750     FirstInst = getFirstInst(FirstInst, C, Loc);
01751     if (Check)
01752       Check = ChkBuilder.CreateOr(Check, C);
01753     else
01754       Check = C;
01755   }
01756 
01757   // We have to do this trickery because the IRBuilder might fold the check to a
01758   // constant expression in which case there is no Instruction anchored in a
01759   // the block.
01760   LLVMContext &Ctx = Loc->getContext();
01761   Instruction *TheCheck =
01762       BinaryOperator::CreateAnd(Check, ConstantInt::getTrue(Ctx));
01763   ChkBuilder.Insert(TheCheck, "stride.not.one");
01764   FirstInst = getFirstInst(FirstInst, TheCheck, Loc);
01765 
01766   return std::make_pair(FirstInst, TheCheck);
01767 }
01768 
01769 std::pair<Instruction *, Instruction *>
01770 InnerLoopVectorizer::addRuntimeCheck(Instruction *Loc) {
01771   LoopVectorizationLegality::RuntimePointerCheck *PtrRtCheck =
01772   Legal->getRuntimePointerCheck();
01773 
01774   Instruction *tnullptr = 0;
01775   if (!PtrRtCheck->Need)
01776     return std::pair<Instruction *, Instruction *>(tnullptr, tnullptr);
01777 
01778   unsigned NumPointers = PtrRtCheck->Pointers.size();
01779   SmallVector<TrackingVH<Value> , 2> Starts;
01780   SmallVector<TrackingVH<Value> , 2> Ends;
01781 
01782   LLVMContext &Ctx = Loc->getContext();
01783   SCEVExpander Exp(*SE, "induction");
01784   Instruction *FirstInst = 0;
01785 
01786   for (unsigned i = 0; i < NumPointers; ++i) {
01787     Value *Ptr = PtrRtCheck->Pointers[i];
01788     const SCEV *Sc = SE->getSCEV(Ptr);
01789 
01790     if (SE->isLoopInvariant(Sc, OrigLoop)) {
01791       DEBUG(dbgs() << "LV: Adding RT check for a loop invariant ptr:" <<
01792             *Ptr <<"\n");
01793       Starts.push_back(Ptr);
01794       Ends.push_back(Ptr);
01795     } else {
01796       DEBUG(dbgs() << "LV: Adding RT check for range:" << *Ptr << '\n');
01797       unsigned AS = Ptr->getType()->getPointerAddressSpace();
01798 
01799       // Use this type for pointer arithmetic.
01800       Type *PtrArithTy = Type::getInt8PtrTy(Ctx, AS);
01801 
01802       Value *Start = Exp.expandCodeFor(PtrRtCheck->Starts[i], PtrArithTy, Loc);
01803       Value *End = Exp.expandCodeFor(PtrRtCheck->Ends[i], PtrArithTy, Loc);
01804       Starts.push_back(Start);
01805       Ends.push_back(End);
01806     }
01807   }
01808 
01809   IRBuilder<> ChkBuilder(Loc);
01810   // Our instructions might fold to a constant.
01811   Value *MemoryRuntimeCheck = 0;
01812   for (unsigned i = 0; i < NumPointers; ++i) {
01813     for (unsigned j = i+1; j < NumPointers; ++j) {
01814       // No need to check if two readonly pointers intersect.
01815       if (!PtrRtCheck->IsWritePtr[i] && !PtrRtCheck->IsWritePtr[j])
01816         continue;
01817 
01818       // Only need to check pointers between two different dependency sets.
01819       if (PtrRtCheck->DependencySetId[i] == PtrRtCheck->DependencySetId[j])
01820        continue;
01821 
01822       unsigned AS0 = Starts[i]->getType()->getPointerAddressSpace();
01823       unsigned AS1 = Starts[j]->getType()->getPointerAddressSpace();
01824 
01825       assert((AS0 == Ends[j]->getType()->getPointerAddressSpace()) &&
01826              (AS1 == Ends[i]->getType()->getPointerAddressSpace()) &&
01827              "Trying to bounds check pointers with different address spaces");
01828 
01829       Type *PtrArithTy0 = Type::getInt8PtrTy(Ctx, AS0);
01830       Type *PtrArithTy1 = Type::getInt8PtrTy(Ctx, AS1);
01831 
01832       Value *Start0 = ChkBuilder.CreateBitCast(Starts[i], PtrArithTy0, "bc");
01833       Value *Start1 = ChkBuilder.CreateBitCast(Starts[j], PtrArithTy1, "bc");
01834       Value *End0 =   ChkBuilder.CreateBitCast(Ends[i],   PtrArithTy1, "bc");
01835       Value *End1 =   ChkBuilder.CreateBitCast(Ends[j],   PtrArithTy0, "bc");
01836 
01837       Value *Cmp0 = ChkBuilder.CreateICmpULE(Start0, End1, "bound0");
01838       FirstInst = getFirstInst(FirstInst, Cmp0, Loc);
01839       Value *Cmp1 = ChkBuilder.CreateICmpULE(Start1, End0, "bound1");
01840       FirstInst = getFirstInst(FirstInst, Cmp1, Loc);
01841       Value *IsConflict = ChkBuilder.CreateAnd(Cmp0, Cmp1, "found.conflict");
01842       FirstInst = getFirstInst(FirstInst, IsConflict, Loc);
01843       if (MemoryRuntimeCheck) {
01844         IsConflict = ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict,
01845                                          "conflict.rdx");
01846         FirstInst = getFirstInst(FirstInst, IsConflict, Loc);
01847       }
01848       MemoryRuntimeCheck = IsConflict;
01849     }
01850   }
01851 
01852   // We have to do this trickery because the IRBuilder might fold the check to a
01853   // constant expression in which case there is no Instruction anchored in a
01854   // the block.
01855   Instruction *Check = BinaryOperator::CreateAnd(MemoryRuntimeCheck,
01856                                                  ConstantInt::getTrue(Ctx));
01857   ChkBuilder.Insert(Check, "memcheck.conflict");
01858   FirstInst = getFirstInst(FirstInst, Check, Loc);
01859   return std::make_pair(FirstInst, Check);
01860 }
01861 
01862 void InnerLoopVectorizer::createEmptyLoop() {
01863   /*
01864    In this function we generate a new loop. The new loop will contain
01865    the vectorized instructions while the old loop will continue to run the
01866    scalar remainder.
01867 
01868        [ ] <-- vector loop bypass (may consist of multiple blocks).
01869      /  |
01870     /   v
01871    |   [ ]     <-- vector pre header.
01872    |    |
01873    |    v
01874    |   [  ] \
01875    |   [  ]_|   <-- vector loop.
01876    |    |
01877     \   v
01878       >[ ]   <--- middle-block.
01879      /  |
01880     /   v
01881    |   [ ]     <--- new preheader.
01882    |    |
01883    |    v
01884    |   [ ] \
01885    |   [ ]_|   <-- old scalar loop to handle remainder.
01886     \   |
01887      \  v
01888       >[ ]     <-- exit block.
01889    ...
01890    */
01891 
01892   BasicBlock *OldBasicBlock = OrigLoop->getHeader();
01893   BasicBlock *BypassBlock = OrigLoop->getLoopPreheader();
01894   BasicBlock *ExitBlock = OrigLoop->getExitBlock();
01895   assert(ExitBlock && "Must have an exit block");
01896 
01897   // Some loops have a single integer induction variable, while other loops
01898   // don't. One example is c++ iterators that often have multiple pointer
01899   // induction variables. In the code below we also support a case where we
01900   // don't have a single induction variable.
01901   OldInduction = Legal->getInduction();
01902   Type *IdxTy = Legal->getWidestInductionType();
01903 
01904   // Find the loop boundaries.
01905   const SCEV *ExitCount = SE->getBackedgeTakenCount(OrigLoop);
01906   assert(ExitCount != SE->getCouldNotCompute() && "Invalid loop count");
01907 
01908   // The exit count might have the type of i64 while the phi is i32. This can
01909   // happen if we have an induction variable that is sign extended before the
01910   // compare. The only way that we get a backedge taken count is that the
01911   // induction variable was signed and as such will not overflow. In such a case
01912   // truncation is legal.
01913   if (ExitCount->getType()->getPrimitiveSizeInBits() >
01914       IdxTy->getPrimitiveSizeInBits())
01915     ExitCount = SE->getTruncateOrNoop(ExitCount, IdxTy);
01916 
01917   ExitCount = SE->getNoopOrZeroExtend(ExitCount, IdxTy);
01918   // Get the total trip count from the count by adding 1.
01919   ExitCount = SE->getAddExpr(ExitCount,
01920                              SE->getConstant(ExitCount->getType(), 1));
01921 
01922   // Expand the trip count and place the new instructions in the preheader.
01923   // Notice that the pre-header does not change, only the loop body.
01924   SCEVExpander Exp(*SE, "induction");
01925 
01926   // Count holds the overall loop count (N).
01927   Value *Count = Exp.expandCodeFor(ExitCount, ExitCount->getType(),
01928                                    BypassBlock->getTerminator());
01929 
01930   // The loop index does not have to start at Zero. Find the original start
01931   // value from the induction PHI node. If we don't have an induction variable
01932   // then we know that it starts at zero.
01933   Builder.SetInsertPoint(BypassBlock->getTerminator());
01934   Value *StartIdx = ExtendedIdx = OldInduction ?
01935     Builder.CreateZExt(OldInduction->getIncomingValueForBlock(BypassBlock),
01936                        IdxTy):
01937     ConstantInt::get(IdxTy, 0);
01938 
01939   assert(BypassBlock && "Invalid loop structure");
01940   LoopBypassBlocks.push_back(BypassBlock);
01941 
01942   // Split the single block loop into the two loop structure described above.
01943   BasicBlock *VectorPH =
01944   BypassBlock->splitBasicBlock(BypassBlock->getTerminator(), "vector.ph");
01945   BasicBlock *VecBody =
01946   VectorPH->splitBasicBlock(VectorPH->getTerminator(), "vector.body");
01947   BasicBlock *MiddleBlock =
01948   VecBody->splitBasicBlock(VecBody->getTerminator(), "middle.block");
01949   BasicBlock *ScalarPH =
01950   MiddleBlock->splitBasicBlock(MiddleBlock->getTerminator(), "scalar.ph");
01951 
01952   // Create and register the new vector loop.
01953   Loop* Lp = new Loop();
01954   Loop *ParentLoop = OrigLoop->getParentLoop();
01955 
01956   // Insert the new loop into the loop nest and register the new basic blocks
01957   // before calling any utilities such as SCEV that require valid LoopInfo.
01958   if (ParentLoop) {
01959     ParentLoop->addChildLoop(Lp);
01960     ParentLoop->addBasicBlockToLoop(ScalarPH, LI->getBase());
01961     ParentLoop->addBasicBlockToLoop(VectorPH, LI->getBase());
01962     ParentLoop->addBasicBlockToLoop(MiddleBlock, LI->getBase());
01963   } else {
01964     LI->addTopLevelLoop(Lp);
01965   }
01966   Lp->addBasicBlockToLoop(VecBody, LI->getBase());
01967 
01968   // Use this IR builder to create the loop instructions (Phi, Br, Cmp)
01969   // inside the loop.
01970   Builder.SetInsertPoint(VecBody->getFirstNonPHI());
01971 
01972   // Generate the induction variable.
01973   setDebugLocFromInst(Builder, getDebugLocFromInstOrOperands(OldInduction));
01974   Induction = Builder.CreatePHI(IdxTy, 2, "index");
01975   // The loop step is equal to the vectorization factor (num of SIMD elements)
01976   // times the unroll factor (num of SIMD instructions).
01977   Constant *Step = ConstantInt::get(IdxTy, VF * UF);
01978 
01979   // This is the IR builder that we use to add all of the logic for bypassing
01980   // the new vector loop.
01981   IRBuilder<> BypassBuilder(BypassBlock->getTerminator());
01982   setDebugLocFromInst(BypassBuilder,
01983                       getDebugLocFromInstOrOperands(OldInduction));
01984 
01985   // We may need to extend the index in case there is a type mismatch.
01986   // We know that the count starts at zero and does not overflow.
01987   if (Count->getType() != IdxTy) {
01988     // The exit count can be of pointer type. Convert it to the correct
01989     // integer type.
01990     if (ExitCount->getType()->isPointerTy())
01991       Count = BypassBuilder.CreatePointerCast(Count, IdxTy, "ptrcnt.to.int");
01992     else
01993       Count = BypassBuilder.CreateZExtOrTrunc(Count, IdxTy, "cnt.cast");
01994   }
01995 
01996   // Add the start index to the loop count to get the new end index.
01997   Value *IdxEnd = BypassBuilder.CreateAdd(Count, StartIdx, "end.idx");
01998 
01999   // Now we need to generate the expression for N - (N % VF), which is
02000   // the part that the vectorized body will execute.
02001   Value *R = BypassBuilder.CreateURem(Count, Step, "n.mod.vf");
02002   Value *CountRoundDown = BypassBuilder.CreateSub(Count, R, "n.vec");
02003   Value *IdxEndRoundDown = BypassBuilder.CreateAdd(CountRoundDown, StartIdx,
02004                                                      "end.idx.rnd.down");
02005 
02006   // Now, compare the new count to zero. If it is zero skip the vector loop and
02007   // jump to the scalar loop.
02008   Value *Cmp = BypassBuilder.CreateICmpEQ(IdxEndRoundDown, StartIdx,
02009                                           "cmp.zero");
02010 
02011   BasicBlock *LastBypassBlock = BypassBlock;
02012 
02013   // Generate the code to check that the strides we assumed to be one are really
02014   // one. We want the new basic block to start at the first instruction in a
02015   // sequence of instructions that form a check.
02016   Instruction *StrideCheck;
02017   Instruction *FirstCheckInst;
02018   std::tie(FirstCheckInst, StrideCheck) =
02019       addStrideCheck(BypassBlock->getTerminator());
02020   if (StrideCheck) {
02021     // Create a new block containing the stride check.
02022     BasicBlock *CheckBlock =
02023         BypassBlock->splitBasicBlock(FirstCheckInst, "vector.stridecheck");
02024     if (ParentLoop)
02025       ParentLoop->addBasicBlockToLoop(CheckBlock, LI->getBase());
02026     LoopBypassBlocks.push_back(CheckBlock);
02027 
02028     // Replace the branch into the memory check block with a conditional branch
02029     // for the "few elements case".
02030     Instruction *OldTerm = BypassBlock->getTerminator();
02031     BranchInst::Create(MiddleBlock, CheckBlock, Cmp, OldTerm);
02032     OldTerm->eraseFromParent();
02033 
02034     Cmp = StrideCheck;
02035     LastBypassBlock = CheckBlock;
02036   }
02037 
02038   // Generate the code that checks in runtime if arrays overlap. We put the
02039   // checks into a separate block to make the more common case of few elements
02040   // faster.
02041   Instruction *MemRuntimeCheck;
02042   std::tie(FirstCheckInst, MemRuntimeCheck) =
02043       addRuntimeCheck(LastBypassBlock->getTerminator());
02044   if (MemRuntimeCheck) {
02045     // Create a new block containing the memory check.
02046     BasicBlock *CheckBlock =
02047         LastBypassBlock->splitBasicBlock(MemRuntimeCheck, "vector.memcheck");
02048     if (ParentLoop)
02049       ParentLoop->addBasicBlockToLoop(CheckBlock, LI->getBase());
02050     LoopBypassBlocks.push_back(CheckBlock);
02051 
02052     // Replace the branch into the memory check block with a conditional branch
02053     // for the "few elements case".
02054     Instruction *OldTerm = LastBypassBlock->getTerminator();
02055     BranchInst::Create(MiddleBlock, CheckBlock, Cmp, OldTerm);
02056     OldTerm->eraseFromParent();
02057 
02058     Cmp = MemRuntimeCheck;
02059     LastBypassBlock = CheckBlock;
02060   }
02061 
02062   LastBypassBlock->getTerminator()->eraseFromParent();
02063   BranchInst::Create(MiddleBlock, VectorPH, Cmp,
02064                      LastBypassBlock);
02065 
02066   // We are going to resume the execution of the scalar loop.
02067   // Go over all of the induction variables that we found and fix the
02068   // PHIs that are left in the scalar version of the loop.
02069   // The starting values of PHI nodes depend on the counter of the last
02070   // iteration in the vectorized loop.
02071   // If we come from a bypass edge then we need to start from the original
02072   // start value.
02073 
02074   // This variable saves the new starting index for the scalar loop.
02075   PHINode *ResumeIndex = 0;
02076   LoopVectorizationLegality::InductionList::iterator I, E;
02077   LoopVectorizationLegality::InductionList *List = Legal->getInductionVars();
02078   // Set builder to point to last bypass block.
02079   BypassBuilder.SetInsertPoint(LoopBypassBlocks.back()->getTerminator());
02080   for (I = List->begin(), E = List->end(); I != E; ++I) {
02081     PHINode *OrigPhi = I->first;
02082     LoopVectorizationLegality::InductionInfo II = I->second;
02083 
02084     Type *ResumeValTy = (OrigPhi == OldInduction) ? IdxTy : OrigPhi->getType();
02085     PHINode *ResumeVal = PHINode::Create(ResumeValTy, 2, "resume.val",
02086                                          MiddleBlock->getTerminator());
02087     // We might have extended the type of the induction variable but we need a
02088     // truncated version for the scalar loop.
02089     PHINode *TruncResumeVal = (OrigPhi == OldInduction) ?
02090       PHINode::Create(OrigPhi->getType(), 2, "trunc.resume.val",
02091                       MiddleBlock->getTerminator()) : 0;
02092 
02093     Value *EndValue = 0;
02094     switch (II.IK) {
02095     case LoopVectorizationLegality::IK_NoInduction:
02096       llvm_unreachable("Unknown induction");
02097     case LoopVectorizationLegality::IK_IntInduction: {
02098       // Handle the integer induction counter.
02099       assert(OrigPhi->getType()->isIntegerTy() && "Invalid type");
02100 
02101       // We have the canonical induction variable.
02102       if (OrigPhi == OldInduction) {
02103         // Create a truncated version of the resume value for the scalar loop,
02104         // we might have promoted the type to a larger width.
02105         EndValue =
02106           BypassBuilder.CreateTrunc(IdxEndRoundDown, OrigPhi->getType());
02107         // The new PHI merges the original incoming value, in case of a bypass,
02108         // or the value at the end of the vectorized loop.
02109         for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I)
02110           TruncResumeVal->addIncoming(II.StartValue, LoopBypassBlocks[I]);
02111         TruncResumeVal->addIncoming(EndValue, VecBody);
02112 
02113         // We know what the end value is.
02114         EndValue = IdxEndRoundDown;
02115         // We also know which PHI node holds it.
02116         ResumeIndex = ResumeVal;
02117         break;
02118       }
02119 
02120       // Not the canonical induction variable - add the vector loop count to the
02121       // start value.
02122       Value *CRD = BypassBuilder.CreateSExtOrTrunc(CountRoundDown,
02123                                                    II.StartValue->getType(),
02124                                                    "cast.crd");
02125       EndValue = BypassBuilder.CreateAdd(CRD, II.StartValue , "ind.end");
02126       break;
02127     }
02128     case LoopVectorizationLegality::IK_ReverseIntInduction: {
02129       // Convert the CountRoundDown variable to the PHI size.
02130       Value *CRD = BypassBuilder.CreateSExtOrTrunc(CountRoundDown,
02131                                                    II.StartValue->getType(),
02132                                                    "cast.crd");
02133       // Handle reverse integer induction counter.
02134       EndValue = BypassBuilder.CreateSub(II.StartValue, CRD, "rev.ind.end");
02135       break;
02136     }
02137     case LoopVectorizationLegality::IK_PtrInduction: {
02138       // For pointer induction variables, calculate the offset using
02139       // the end index.
02140       EndValue = BypassBuilder.CreateGEP(II.StartValue, CountRoundDown,
02141                                          "ptr.ind.end");
02142       break;
02143     }
02144     case LoopVectorizationLegality::IK_ReversePtrInduction: {
02145       // The value at the end of the loop for the reverse pointer is calculated
02146       // by creating a GEP with a negative index starting from the start value.
02147       Value *Zero = ConstantInt::get(CountRoundDown->getType(), 0);
02148       Value *NegIdx = BypassBuilder.CreateSub(Zero, CountRoundDown,
02149                                               "rev.ind.end");
02150       EndValue = BypassBuilder.CreateGEP(II.StartValue, NegIdx,
02151                                          "rev.ptr.ind.end");
02152       break;
02153     }
02154     }// end of case
02155 
02156     // The new PHI merges the original incoming value, in case of a bypass,
02157     // or the value at the end of the vectorized loop.
02158     for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I) {
02159       if (OrigPhi == OldInduction)
02160         ResumeVal->addIncoming(StartIdx, LoopBypassBlocks[I]);
02161       else
02162         ResumeVal->addIncoming(II.StartValue, LoopBypassBlocks[I]);
02163     }
02164     ResumeVal->addIncoming(EndValue, VecBody);
02165 
02166     // Fix the scalar body counter (PHI node).
02167     unsigned BlockIdx = OrigPhi->getBasicBlockIndex(ScalarPH);
02168     // The old inductions phi node in the scalar body needs the truncated value.
02169     if (OrigPhi == OldInduction)
02170       OrigPhi->setIncomingValue(BlockIdx, TruncResumeVal);
02171     else
02172       OrigPhi->setIncomingValue(BlockIdx, ResumeVal);
02173   }
02174 
02175   // If we are generating a new induction variable then we also need to
02176   // generate the code that calculates the exit value. This value is not
02177   // simply the end of the counter because we may skip the vectorized body
02178   // in case of a runtime check.
02179   if (!OldInduction){
02180     assert(!ResumeIndex && "Unexpected resume value found");
02181     ResumeIndex = PHINode::Create(IdxTy, 2, "new.indc.resume.val",
02182                                   MiddleBlock->getTerminator());
02183     for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I)
02184       ResumeIndex->addIncoming(StartIdx, LoopBypassBlocks[I]);
02185     ResumeIndex->addIncoming(IdxEndRoundDown, VecBody);
02186   }
02187 
02188   // Make sure that we found the index where scalar loop needs to continue.
02189   assert(ResumeIndex && ResumeIndex->getType()->isIntegerTy() &&
02190          "Invalid resume Index");
02191 
02192   // Add a check in the middle block to see if we have completed
02193   // all of the iterations in the first vector loop.
02194   // If (N - N%VF) == N, then we *don't* need to run the remainder.
02195   Value *CmpN = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, IdxEnd,
02196                                 ResumeIndex, "cmp.n",
02197                                 MiddleBlock->getTerminator());
02198 
02199   BranchInst::Create(ExitBlock, ScalarPH, CmpN, MiddleBlock->getTerminator());
02200   // Remove the old terminator.
02201   MiddleBlock->getTerminator()->eraseFromParent();
02202 
02203   // Create i+1 and fill the PHINode.
02204   Value *NextIdx = Builder.CreateAdd(Induction, Step, "index.next");
02205   Induction->addIncoming(StartIdx, VectorPH);
02206   Induction->addIncoming(NextIdx, VecBody);
02207   // Create the compare.
02208   Value *ICmp = Builder.CreateICmpEQ(NextIdx, IdxEndRoundDown);
02209   Builder.CreateCondBr(ICmp, MiddleBlock, VecBody);
02210 
02211   // Now we have two terminators. Remove the old one from the block.
02212   VecBody->getTerminator()->eraseFromParent();
02213 
02214   // Get ready to start creating new instructions into the vectorized body.
02215   Builder.SetInsertPoint(VecBody->getFirstInsertionPt());
02216 
02217   // Save the state.
02218   LoopVectorPreHeader = VectorPH;
02219   LoopScalarPreHeader = ScalarPH;
02220   LoopMiddleBlock = MiddleBlock;
02221   LoopExitBlock = ExitBlock;
02222   LoopVectorBody.push_back(VecBody);
02223   LoopScalarBody = OldBasicBlock;
02224 
02225   LoopVectorizeHints Hints(Lp, true);
02226   Hints.setAlreadyVectorized(Lp);
02227 }
02228 
02229 /// This function returns the identity element (or neutral element) for
02230 /// the operation K.
02231 Constant*
02232 LoopVectorizationLegality::getReductionIdentity(ReductionKind K, Type *Tp) {
02233   switch (K) {
02234   case RK_IntegerXor:
02235   case RK_IntegerAdd:
02236   case RK_IntegerOr:
02237     // Adding, Xoring, Oring zero to a number does not change it.
02238     return ConstantInt::get(Tp, 0);
02239   case RK_IntegerMult:
02240     // Multiplying a number by 1 does not change it.
02241     return ConstantInt::get(Tp, 1);
02242   case RK_IntegerAnd:
02243     // AND-ing a number with an all-1 value does not change it.
02244     return ConstantInt::get(Tp, -1, true);
02245   case  RK_FloatMult:
02246     // Multiplying a number by 1 does not change it.
02247     return ConstantFP::get(Tp, 1.0L);
02248   case  RK_FloatAdd:
02249     // Adding zero to a number does not change it.
02250     return ConstantFP::get(Tp, 0.0L);
02251   default:
02252     llvm_unreachable("Unknown reduction kind");
02253   }
02254 }
02255 
02256 static Intrinsic::ID checkUnaryFloatSignature(const CallInst &I,
02257                                               Intrinsic::ID ValidIntrinsicID) {
02258   if (I.getNumArgOperands() != 1 ||
02259       !I.getArgOperand(0)->getType()->isFloatingPointTy() ||
02260       I.getType() != I.getArgOperand(0)->getType() ||
02261       !I.onlyReadsMemory())
02262     return Intrinsic::not_intrinsic;
02263 
02264   return ValidIntrinsicID;
02265 }
02266 
02267 static Intrinsic::ID checkBinaryFloatSignature(const CallInst &I,
02268                                                Intrinsic::ID ValidIntrinsicID) {
02269   if (I.getNumArgOperands() != 2 ||
02270       !I.getArgOperand(0)->getType()->isFloatingPointTy() ||
02271       !I.getArgOperand(1)->getType()->isFloatingPointTy() ||
02272       I.getType() != I.getArgOperand(0)->getType() ||
02273       I.getType() != I.getArgOperand(1)->getType() ||
02274       !I.onlyReadsMemory())
02275     return Intrinsic::not_intrinsic;
02276 
02277   return ValidIntrinsicID;
02278 }
02279 
02280 
02281 static Intrinsic::ID
02282 getIntrinsicIDForCall(CallInst *CI, const TargetLibraryInfo *TLI) {
02283   // If we have an intrinsic call, check if it is trivially vectorizable.
02284   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) {
02285     Intrinsic::ID ID = II->getIntrinsicID();
02286     if (isTriviallyVectorizable(ID) || ID == Intrinsic::lifetime_start ||
02287         ID == Intrinsic::lifetime_end)
02288       return ID;
02289     else
02290       return Intrinsic::not_intrinsic;
02291   }
02292 
02293   if (!TLI)
02294     return Intrinsic::not_intrinsic;
02295 
02296   LibFunc::Func Func;
02297   Function *F = CI->getCalledFunction();
02298   // We're going to make assumptions on the semantics of the functions, check
02299   // that the target knows that it's available in this environment and it does
02300   // not have local linkage.
02301   if (!F || F->hasLocalLinkage() || !TLI->getLibFunc(F->getName(), Func))
02302     return Intrinsic::not_intrinsic;
02303 
02304   // Otherwise check if we have a call to a function that can be turned into a
02305   // vector intrinsic.
02306   switch (Func) {
02307   default:
02308     break;
02309   case LibFunc::sin:
02310   case LibFunc::sinf:
02311   case LibFunc::sinl:
02312     return checkUnaryFloatSignature(*CI, Intrinsic::sin);
02313   case LibFunc::cos:
02314   case LibFunc::cosf:
02315   case LibFunc::cosl:
02316     return checkUnaryFloatSignature(*CI, Intrinsic::cos);
02317   case LibFunc::exp:
02318   case LibFunc::expf:
02319   case LibFunc::expl:
02320     return checkUnaryFloatSignature(*CI, Intrinsic::exp);
02321   case LibFunc::exp2:
02322   case LibFunc::exp2f:
02323   case LibFunc::exp2l:
02324     return checkUnaryFloatSignature(*CI, Intrinsic::exp2);
02325   case LibFunc::log:
02326   case LibFunc::logf:
02327   case LibFunc::logl:
02328     return checkUnaryFloatSignature(*CI, Intrinsic::log);
02329   case LibFunc::log10:
02330   case LibFunc::log10f:
02331   case LibFunc::log10l:
02332     return checkUnaryFloatSignature(*CI, Intrinsic::log10);
02333   case LibFunc::log2:
02334   case LibFunc::log2f:
02335   case LibFunc::log2l:
02336     return checkUnaryFloatSignature(*CI, Intrinsic::log2);
02337   case LibFunc::fabs:
02338   case LibFunc::fabsf:
02339   case LibFunc::fabsl:
02340     return checkUnaryFloatSignature(*CI, Intrinsic::fabs);
02341   case LibFunc::copysign:
02342   case LibFunc::copysignf:
02343   case LibFunc::copysignl:
02344     return checkBinaryFloatSignature(*CI, Intrinsic::copysign);
02345   case LibFunc::floor:
02346   case LibFunc::floorf:
02347   case LibFunc::floorl:
02348     return checkUnaryFloatSignature(*CI, Intrinsic::floor);
02349   case LibFunc::ceil:
02350   case LibFunc::ceilf:
02351   case LibFunc::ceill:
02352     return checkUnaryFloatSignature(*CI, Intrinsic::ceil);
02353   case LibFunc::trunc:
02354   case LibFunc::truncf:
02355   case LibFunc::truncl:
02356     return checkUnaryFloatSignature(*CI, Intrinsic::trunc);
02357   case LibFunc::rint:
02358   case LibFunc::rintf:
02359   case LibFunc::rintl:
02360     return checkUnaryFloatSignature(*CI, Intrinsic::rint);
02361   case LibFunc::nearbyint:
02362   case LibFunc::nearbyintf:
02363   case LibFunc::nearbyintl:
02364     return checkUnaryFloatSignature(*CI, Intrinsic::nearbyint);
02365   case LibFunc::round:
02366   case LibFunc::roundf:
02367   case LibFunc::roundl:
02368     return checkUnaryFloatSignature(*CI, Intrinsic::round);
02369   case LibFunc::pow:
02370   case LibFunc::powf:
02371   case LibFunc::powl:
02372     return checkBinaryFloatSignature(*CI, Intrinsic::pow);
02373   }
02374 
02375   return Intrinsic::not_intrinsic;
02376 }
02377 
02378 /// This function translates the reduction kind to an LLVM binary operator.
02379 static unsigned
02380 getReductionBinOp(LoopVectorizationLegality::ReductionKind Kind) {
02381   switch (Kind) {
02382     case LoopVectorizationLegality::RK_IntegerAdd:
02383       return Instruction::Add;
02384     case LoopVectorizationLegality::RK_IntegerMult:
02385       return Instruction::Mul;
02386     case LoopVectorizationLegality::RK_IntegerOr:
02387       return Instruction::Or;
02388     case LoopVectorizationLegality::RK_IntegerAnd:
02389       return Instruction::And;
02390     case LoopVectorizationLegality::RK_IntegerXor:
02391       return Instruction::Xor;
02392     case LoopVectorizationLegality::RK_FloatMult:
02393       return Instruction::FMul;
02394     case LoopVectorizationLegality::RK_FloatAdd:
02395       return Instruction::FAdd;
02396     case LoopVectorizationLegality::RK_IntegerMinMax:
02397       return Instruction::ICmp;
02398     case LoopVectorizationLegality::RK_FloatMinMax:
02399       return Instruction::FCmp;
02400     default:
02401       llvm_unreachable("Unknown reduction operation");
02402   }
02403 }
02404 
02405 Value *createMinMaxOp(IRBuilder<> &Builder,
02406                       LoopVectorizationLegality::MinMaxReductionKind RK,
02407                       Value *Left,
02408                       Value *Right) {
02409   CmpInst::Predicate P = CmpInst::ICMP_NE;
02410   switch (RK) {
02411   default:
02412     llvm_unreachable("Unknown min/max reduction kind");
02413   case LoopVectorizationLegality::MRK_UIntMin:
02414     P = CmpInst::ICMP_ULT;
02415     break;
02416   case LoopVectorizationLegality::MRK_UIntMax:
02417     P = CmpInst::ICMP_UGT;
02418     break;
02419   case LoopVectorizationLegality::MRK_SIntMin:
02420     P = CmpInst::ICMP_SLT;
02421     break;
02422   case LoopVectorizationLegality::MRK_SIntMax:
02423     P = CmpInst::ICMP_SGT;
02424     break;
02425   case LoopVectorizationLegality::MRK_FloatMin:
02426     P = CmpInst::FCMP_OLT;
02427     break;
02428   case LoopVectorizationLegality::MRK_FloatMax:
02429     P = CmpInst::FCMP_OGT;
02430     break;
02431   }
02432 
02433   Value *Cmp;
02434   if (RK == LoopVectorizationLegality::MRK_FloatMin ||
02435       RK == LoopVectorizationLegality::MRK_FloatMax)
02436     Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
02437   else
02438     Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp");
02439 
02440   Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
02441   return Select;
02442 }
02443 
02444 namespace {
02445 struct CSEDenseMapInfo {
02446   static bool canHandle(Instruction *I) {
02447     return isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) ||
02448            isa<ShuffleVectorInst>(I) || isa<GetElementPtrInst>(I);
02449   }
02450   static inline Instruction *getEmptyKey() {
02451     return DenseMapInfo<Instruction *>::getEmptyKey();
02452   }
02453   static inline Instruction *getTombstoneKey() {
02454     return DenseMapInfo<Instruction *>::getTombstoneKey();
02455   }
02456   static unsigned getHashValue(Instruction *I) {
02457     assert(canHandle(I) && "Unknown instruction!");
02458     return hash_combine(I->getOpcode(), hash_combine_range(I->value_op_begin(),
02459                                                            I->value_op_end()));
02460   }
02461   static bool isEqual(Instruction *LHS, Instruction *RHS) {
02462     if (LHS == getEmptyKey() || RHS == getEmptyKey() ||
02463         LHS == getTombstoneKey() || RHS == getTombstoneKey())
02464       return LHS == RHS;
02465     return LHS->isIdenticalTo(RHS);
02466   }
02467 };
02468 }
02469 
02470 /// \brief Check whether this block is a predicated block.
02471 /// Due to if predication of stores we might create a sequence of "if(pred) a[i]
02472 /// = ...;  " blocks. We start with one vectorized basic block. For every
02473 /// conditional block we split this vectorized block. Therefore, every second
02474 /// block will be a predicated one.
02475 static bool isPredicatedBlock(unsigned BlockNum) {
02476   return BlockNum % 2;
02477 }
02478 
02479 ///\brief Perform cse of induction variable instructions.
02480 static void cse(SmallVector<BasicBlock *, 4> &BBs) {
02481   // Perform simple cse.
02482   SmallDenseMap<Instruction *, Instruction *, 4, CSEDenseMapInfo> CSEMap;
02483   for (unsigned i = 0, e = BBs.size(); i != e; ++i) {
02484     BasicBlock *BB = BBs[i];
02485     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
02486       Instruction *In = I++;
02487 
02488       if (!CSEDenseMapInfo::canHandle(In))
02489         continue;
02490 
02491       // Check if we can replace this instruction with any of the
02492       // visited instructions.
02493       if (Instruction *V = CSEMap.lookup(In)) {
02494         In->replaceAllUsesWith(V);
02495         In->eraseFromParent();
02496         continue;
02497       }
02498       // Ignore instructions in conditional blocks. We create "if (pred) a[i] =
02499       // ...;" blocks for predicated stores. Every second block is a predicated
02500       // block.
02501       if (isPredicatedBlock(i))
02502         continue;
02503 
02504       CSEMap[In] = In;
02505     }
02506   }
02507 }
02508 
02509 /// \brief Adds a 'fast' flag to floating point operations.
02510 static Value *addFastMathFlag(Value *V) {
02511   if (isa<FPMathOperator>(V)){
02512     FastMathFlags Flags;
02513     Flags.setUnsafeAlgebra();
02514     cast<Instruction>(V)->setFastMathFlags(Flags);
02515   }
02516   return V;
02517 }
02518 
02519 void InnerLoopVectorizer::vectorizeLoop() {
02520   //===------------------------------------------------===//
02521   //
02522   // Notice: any optimization or new instruction that go
02523   // into the code below should be also be implemented in
02524   // the cost-model.
02525   //
02526   //===------------------------------------------------===//
02527   Constant *Zero = Builder.getInt32(0);
02528 
02529   // In order to support reduction variables we need to be able to vectorize
02530   // Phi nodes. Phi nodes have cycles, so we need to vectorize them in two
02531   // stages. First, we create a new vector PHI node with no incoming edges.
02532   // We use this value when we vectorize all of the instructions that use the
02533   // PHI. Next, after all of the instructions in the block are complete we
02534   // add the new incoming edges to the PHI. At this point all of the
02535   // instructions in the basic block are vectorized, so we can use them to
02536   // construct the PHI.
02537   PhiVector RdxPHIsToFix;
02538 
02539   // Scan the loop in a topological order to ensure that defs are vectorized
02540   // before users.
02541   LoopBlocksDFS DFS(OrigLoop);
02542   DFS.perform(LI);
02543 
02544   // Vectorize all of the blocks in the original loop.
02545   for (LoopBlocksDFS::RPOIterator bb = DFS.beginRPO(),
02546        be = DFS.endRPO(); bb != be; ++bb)
02547     vectorizeBlockInLoop(*bb, &RdxPHIsToFix);
02548 
02549   // At this point every instruction in the original loop is widened to
02550   // a vector form. We are almost done. Now, we need to fix the PHI nodes
02551   // that we vectorized. The PHI nodes are currently empty because we did
02552   // not want to introduce cycles. Notice that the remaining PHI nodes
02553   // that we need to fix are reduction variables.
02554 
02555   // Create the 'reduced' values for each of the induction vars.
02556   // The reduced values are the vector values that we scalarize and combine
02557   // after the loop is finished.
02558   for (PhiVector::iterator it = RdxPHIsToFix.begin(), e = RdxPHIsToFix.end();
02559        it != e; ++it) {
02560     PHINode *RdxPhi = *it;
02561     assert(RdxPhi && "Unable to recover vectorized PHI");
02562 
02563     // Find the reduction variable descriptor.
02564     assert(Legal->getReductionVars()->count(RdxPhi) &&
02565            "Unable to find the reduction variable");
02566     LoopVectorizationLegality::ReductionDescriptor RdxDesc =
02567     (*Legal->getReductionVars())[RdxPhi];
02568 
02569     setDebugLocFromInst(Builder, RdxDesc.StartValue);
02570 
02571     // We need to generate a reduction vector from the incoming scalar.
02572     // To do so, we need to generate the 'identity' vector and override
02573     // one of the elements with the incoming scalar reduction. We need
02574     // to do it in the vector-loop preheader.
02575     Builder.SetInsertPoint(LoopBypassBlocks.front()->getTerminator());
02576 
02577     // This is the vector-clone of the value that leaves the loop.
02578     VectorParts &VectorExit = getVectorValue(RdxDesc.LoopExitInstr);
02579     Type *VecTy = VectorExit[0]->getType();
02580 
02581     // Find the reduction identity variable. Zero for addition, or, xor,
02582     // one for multiplication, -1 for And.
02583     Value *Identity;
02584     Value *VectorStart;
02585     if (RdxDesc.Kind == LoopVectorizationLegality::RK_IntegerMinMax ||
02586         RdxDesc.Kind == LoopVectorizationLegality::RK_FloatMinMax) {
02587       // MinMax reduction have the start value as their identify.
02588       if (VF == 1) {
02589         VectorStart = Identity = RdxDesc.StartValue;
02590       } else {
02591         VectorStart = Identity = Builder.CreateVectorSplat(VF,
02592                                                            RdxDesc.StartValue,
02593                                                            "minmax.ident");
02594       }
02595     } else {
02596       // Handle other reduction kinds:
02597       Constant *Iden =
02598       LoopVectorizationLegality::getReductionIdentity(RdxDesc.Kind,
02599                                                       VecTy->getScalarType());
02600       if (VF == 1) {
02601         Identity = Iden;
02602         // This vector is the Identity vector where the first element is the
02603         // incoming scalar reduction.
02604         VectorStart = RdxDesc.StartValue;
02605       } else {
02606         Identity = ConstantVector::getSplat(VF, Iden);
02607 
02608         // This vector is the Identity vector where the first element is the
02609         // incoming scalar reduction.
02610         VectorStart = Builder.CreateInsertElement(Identity,
02611                                                   RdxDesc.StartValue, Zero);
02612       }
02613     }
02614 
02615     // Fix the vector-loop phi.
02616     // We created the induction variable so we know that the
02617     // preheader is the first entry.
02618     BasicBlock *VecPreheader = Induction->getIncomingBlock(0);
02619 
02620     // Reductions do not have to start at zero. They can start with
02621     // any loop invariant values.
02622     VectorParts &VecRdxPhi = WidenMap.get(RdxPhi);
02623     BasicBlock *Latch = OrigLoop->getLoopLatch();
02624     Value *LoopVal = RdxPhi->getIncomingValueForBlock(Latch);
02625     VectorParts &Val = getVectorValue(LoopVal);
02626     for (unsigned part = 0; part < UF; ++part) {
02627       // Make sure to add the reduction stat value only to the
02628       // first unroll part.
02629       Value *StartVal = (part == 0) ? VectorStart : Identity;
02630       cast<PHINode>(VecRdxPhi[part])->addIncoming(StartVal, VecPreheader);
02631       cast<PHINode>(VecRdxPhi[part])->addIncoming(Val[part],
02632                                                   LoopVectorBody.back());
02633     }
02634 
02635     // Before each round, move the insertion point right between
02636     // the PHIs and the values we are going to write.
02637     // This allows us to write both PHINodes and the extractelement
02638     // instructions.
02639     Builder.SetInsertPoint(LoopMiddleBlock->getFirstInsertionPt());
02640 
02641     VectorParts RdxParts;
02642     setDebugLocFromInst(Builder, RdxDesc.LoopExitInstr);
02643     for (unsigned part = 0; part < UF; ++part) {
02644       // This PHINode contains the vectorized reduction variable, or
02645       // the initial value vector, if we bypass the vector loop.
02646       VectorParts &RdxExitVal = getVectorValue(RdxDesc.LoopExitInstr);
02647       PHINode *NewPhi = Builder.CreatePHI(VecTy, 2, "rdx.vec.exit.phi");
02648       Value *StartVal = (part == 0) ? VectorStart : Identity;
02649       for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I)
02650         NewPhi->addIncoming(StartVal, LoopBypassBlocks[I]);
02651       NewPhi->addIncoming(RdxExitVal[part],
02652                           LoopVectorBody.back());
02653       RdxParts.push_back(NewPhi);
02654     }
02655 
02656     // Reduce all of the unrolled parts into a single vector.
02657     Value *ReducedPartRdx = RdxParts[0];
02658     unsigned Op = getReductionBinOp(RdxDesc.Kind);
02659     setDebugLocFromInst(Builder, ReducedPartRdx);
02660     for (unsigned part = 1; part < UF; ++part) {
02661       if (Op != Instruction::ICmp && Op != Instruction::FCmp)
02662         // Floating point operations had to be 'fast' to enable the reduction.
02663         ReducedPartRdx = addFastMathFlag(
02664             Builder.CreateBinOp((Instruction::BinaryOps)Op, RdxParts[part],
02665                                 ReducedPartRdx, "bin.rdx"));
02666       else
02667         ReducedPartRdx = createMinMaxOp(Builder, RdxDesc.MinMaxKind,
02668                                         ReducedPartRdx, RdxParts[part]);
02669     }
02670 
02671     if (VF > 1) {
02672       // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
02673       // and vector ops, reducing the set of values being computed by half each
02674       // round.
02675       assert(isPowerOf2_32(VF) &&
02676              "Reduction emission only supported for pow2 vectors!");
02677       Value *TmpVec = ReducedPartRdx;
02678       SmallVector<Constant*, 32> ShuffleMask(VF, 0);
02679       for (unsigned i = VF; i != 1; i >>= 1) {
02680         // Move the upper half of the vector to the lower half.
02681         for (unsigned j = 0; j != i/2; ++j)
02682           ShuffleMask[j] = Builder.getInt32(i/2 + j);
02683 
02684         // Fill the rest of the mask with undef.
02685         std::fill(&ShuffleMask[i/2], ShuffleMask.end(),
02686                   UndefValue::get(Builder.getInt32Ty()));
02687 
02688         Value *Shuf =
02689         Builder.CreateShuffleVector(TmpVec,
02690                                     UndefValue::get(TmpVec->getType()),
02691                                     ConstantVector::get(ShuffleMask),
02692                                     "rdx.shuf");
02693 
02694         if (Op != Instruction::ICmp && Op != Instruction::FCmp)
02695           // Floating point operations had to be 'fast' to enable the reduction.
02696           TmpVec = addFastMathFlag(Builder.CreateBinOp(
02697               (Instruction::BinaryOps)Op, TmpVec, Shuf, "bin.rdx"));
02698         else
02699           TmpVec = createMinMaxOp(Builder, RdxDesc.MinMaxKind, TmpVec, Shuf);
02700       }
02701 
02702       // The result is in the first element of the vector.
02703       ReducedPartRdx = Builder.CreateExtractElement(TmpVec,
02704                                                     Builder.getInt32(0));
02705     }
02706 
02707     // Now, we need to fix the users of the reduction variable
02708     // inside and outside of the scalar remainder loop.
02709     // We know that the loop is in LCSSA form. We need to update the
02710     // PHI nodes in the exit blocks.
02711     for (BasicBlock::iterator LEI = LoopExitBlock->begin(),
02712          LEE = LoopExitBlock->end(); LEI != LEE; ++LEI) {
02713       PHINode *LCSSAPhi = dyn_cast<PHINode>(LEI);
02714       if (!LCSSAPhi) break;
02715 
02716       // All PHINodes need to have a single entry edge, or two if
02717       // we already fixed them.
02718       assert(LCSSAPhi->getNumIncomingValues() < 3 && "Invalid LCSSA PHI");
02719 
02720       // We found our reduction value exit-PHI. Update it with the
02721       // incoming bypass edge.
02722       if (LCSSAPhi->getIncomingValue(0) == RdxDesc.LoopExitInstr) {
02723         // Add an edge coming from the bypass.
02724         LCSSAPhi->addIncoming(ReducedPartRdx, LoopMiddleBlock);
02725         break;
02726       }
02727     }// end of the LCSSA phi scan.
02728 
02729     // Fix the scalar loop reduction variable with the incoming reduction sum
02730     // from the vector body and from the backedge value.
02731     int IncomingEdgeBlockIdx =
02732     (RdxPhi)->getBasicBlockIndex(OrigLoop->getLoopLatch());
02733     assert(IncomingEdgeBlockIdx >= 0 && "Invalid block index");
02734     // Pick the other block.
02735     int SelfEdgeBlockIdx = (IncomingEdgeBlockIdx ? 0 : 1);
02736     (RdxPhi)->setIncomingValue(SelfEdgeBlockIdx, ReducedPartRdx);
02737     (RdxPhi)->setIncomingValue(IncomingEdgeBlockIdx, RdxDesc.LoopExitInstr);
02738   }// end of for each redux variable.
02739 
02740   fixLCSSAPHIs();
02741 
02742   // Remove redundant induction instructions.
02743   cse(LoopVectorBody);
02744 }
02745 
02746 void InnerLoopVectorizer::fixLCSSAPHIs() {
02747   for (BasicBlock::iterator LEI = LoopExitBlock->begin(),
02748        LEE = LoopExitBlock->end(); LEI != LEE; ++LEI) {
02749     PHINode *LCSSAPhi = dyn_cast<PHINode>(LEI);
02750     if (!LCSSAPhi) break;
02751     if (LCSSAPhi->getNumIncomingValues() == 1)
02752       LCSSAPhi->addIncoming(UndefValue::get(LCSSAPhi->getType()),
02753                             LoopMiddleBlock);
02754   }
02755 } 
02756 
02757 InnerLoopVectorizer::VectorParts
02758 InnerLoopVectorizer::createEdgeMask(BasicBlock *Src, BasicBlock *Dst) {
02759   assert(std::find(pred_begin(Dst), pred_end(Dst), Src) != pred_end(Dst) &&
02760          "Invalid edge");
02761 
02762   // Look for cached value.
02763   std::pair<BasicBlock*, BasicBlock*> Edge(Src, Dst);
02764   EdgeMaskCache::iterator ECEntryIt = MaskCache.find(Edge);
02765   if (ECEntryIt != MaskCache.end())
02766     return ECEntryIt->second;
02767 
02768   VectorParts SrcMask = createBlockInMask(Src);
02769 
02770   // The terminator has to be a branch inst!
02771   BranchInst *BI = dyn_cast<BranchInst>(Src->getTerminator());
02772   assert(BI && "Unexpected terminator found");
02773 
02774   if (BI->isConditional()) {
02775     VectorParts EdgeMask = getVectorValue(BI->getCondition());
02776 
02777     if (BI->getSuccessor(0) != Dst)
02778       for (unsigned part = 0; part < UF; ++part)
02779         EdgeMask[part] = Builder.CreateNot(EdgeMask[part]);
02780 
02781     for (unsigned part = 0; part < UF; ++part)
02782       EdgeMask[part] = Builder.CreateAnd(EdgeMask[part], SrcMask[part]);
02783 
02784     MaskCache[Edge] = EdgeMask;
02785     return EdgeMask;
02786   }
02787 
02788   MaskCache[Edge] = SrcMask;
02789   return SrcMask;
02790 }
02791 
02792 InnerLoopVectorizer::VectorParts
02793 InnerLoopVectorizer::createBlockInMask(BasicBlock *BB) {
02794   assert(OrigLoop->contains(BB) && "Block is not a part of a loop");
02795 
02796   // Loop incoming mask is all-one.
02797   if (OrigLoop->getHeader() == BB) {
02798     Value *C = ConstantInt::get(IntegerType::getInt1Ty(BB->getContext()), 1);
02799     return getVectorValue(C);
02800   }
02801 
02802   // This is the block mask. We OR all incoming edges, and with zero.
02803   Value *Zero = ConstantInt::get(IntegerType::getInt1Ty(BB->getContext()), 0);
02804   VectorParts BlockMask = getVectorValue(Zero);
02805 
02806   // For each pred:
02807   for (pred_iterator it = pred_begin(BB), e = pred_end(BB); it != e; ++it) {
02808     VectorParts EM = createEdgeMask(*it, BB);
02809     for (unsigned part = 0; part < UF; ++part)
02810       BlockMask[part] = Builder.CreateOr(BlockMask[part], EM[part]);
02811   }
02812 
02813   return BlockMask;
02814 }
02815 
02816 void InnerLoopVectorizer::widenPHIInstruction(Instruction *PN,
02817                                               InnerLoopVectorizer::VectorParts &Entry,
02818                                               unsigned UF, unsigned VF, PhiVector *PV) {
02819   PHINode* P = cast<PHINode>(PN);
02820   // Handle reduction variables:
02821   if (Legal->getReductionVars()->count(P)) {
02822     for (unsigned part = 0; part < UF; ++part) {
02823       // This is phase one of vectorizing PHIs.
02824       Type *VecTy = (VF == 1) ? PN->getType() :
02825       VectorType::get(PN->getType(), VF);
02826       Entry[part] = PHINode::Create(VecTy, 2, "vec.phi",
02827                                     LoopVectorBody.back()-> getFirstInsertionPt());
02828     }
02829     PV->push_back(P);
02830     return;
02831   }
02832 
02833   setDebugLocFromInst(Builder, P);
02834   // Check for PHI nodes that are lowered to vector selects.
02835   if (P->getParent() != OrigLoop->getHeader()) {
02836     // We know that all PHIs in non-header blocks are converted into
02837     // selects, so we don't have to worry about the insertion order and we
02838     // can just use the builder.
02839     // At this point we generate the predication tree. There may be
02840     // duplications since this is a simple recursive scan, but future
02841     // optimizations will clean it up.
02842 
02843     unsigned NumIncoming = P->getNumIncomingValues();
02844 
02845     // Generate a sequence of selects of the form:
02846     // SELECT(Mask3, In3,
02847     //      SELECT(Mask2, In2,
02848     //                   ( ...)))
02849     for (unsigned In = 0; In < NumIncoming; In++) {
02850       VectorParts Cond = createEdgeMask(P->getIncomingBlock(In),
02851                                         P->getParent());
02852       VectorParts &In0 = getVectorValue(P->getIncomingValue(In));
02853 
02854       for (unsigned part = 0; part < UF; ++part) {
02855         // We might have single edge PHIs (blocks) - use an identity
02856         // 'select' for the first PHI operand.
02857         if (In == 0)
02858           Entry[part] = Builder.CreateSelect(Cond[part], In0[part],
02859                                              In0[part]);
02860         else
02861           // Select between the current value and the previous incoming edge
02862           // based on the incoming mask.
02863           Entry[part] = Builder.CreateSelect(Cond[part], In0[part],
02864                                              Entry[part], "predphi");
02865       }
02866     }
02867     return;
02868   }
02869 
02870   // This PHINode must be an induction variable.
02871   // Make sure that we know about it.
02872   assert(Legal->getInductionVars()->count(P) &&
02873          "Not an induction variable");
02874 
02875   LoopVectorizationLegality::InductionInfo II =
02876   Legal->getInductionVars()->lookup(P);
02877 
02878   switch (II.IK) {
02879     case LoopVectorizationLegality::IK_NoInduction:
02880       llvm_unreachable("Unknown induction");
02881     case LoopVectorizationLegality::IK_IntInduction: {
02882       assert(P->getType() == II.StartValue->getType() && "Types must match");
02883       Type *PhiTy = P->getType();
02884       Value *Broadcasted;
02885       if (P == OldInduction) {
02886         // Handle the canonical induction variable. We might have had to
02887         // extend the type.
02888         Broadcasted = Builder.CreateTrunc(Induction, PhiTy);
02889       } else {
02890         // Handle other induction variables that are now based on the
02891         // canonical one.
02892         Value *NormalizedIdx = Builder.CreateSub(Induction, ExtendedIdx,
02893                                                  "normalized.idx");
02894         NormalizedIdx = Builder.CreateSExtOrTrunc(NormalizedIdx, PhiTy);
02895         Broadcasted = Builder.CreateAdd(II.StartValue, NormalizedIdx,
02896                                         "offset.idx");
02897       }
02898       Broadcasted = getBroadcastInstrs(Broadcasted);
02899       // After broadcasting the induction variable we need to make the vector
02900       // consecutive by adding 0, 1, 2, etc.
02901       for (unsigned part = 0; part < UF; ++part)
02902         Entry[part] = getConsecutiveVector(Broadcasted, VF * part, false);
02903       return;
02904     }
02905     case LoopVectorizationLegality::IK_ReverseIntInduction:
02906     case LoopVectorizationLegality::IK_PtrInduction:
02907     case LoopVectorizationLegality::IK_ReversePtrInduction:
02908       // Handle reverse integer and pointer inductions.
02909       Value *StartIdx = ExtendedIdx;
02910       // This is the normalized GEP that starts counting at zero.
02911       Value *NormalizedIdx = Builder.CreateSub(Induction, StartIdx,
02912                                                "normalized.idx");
02913 
02914       // Handle the reverse integer induction variable case.
02915       if (LoopVectorizationLegality::IK_ReverseIntInduction == II.IK) {
02916         IntegerType *DstTy = cast<IntegerType>(II.StartValue->getType());
02917         Value *CNI = Builder.CreateSExtOrTrunc(NormalizedIdx, DstTy,
02918                                                "resize.norm.idx");
02919         Value *ReverseInd  = Builder.CreateSub(II.StartValue, CNI,
02920                                                "reverse.idx");
02921 
02922         // This is a new value so do not hoist it out.
02923         Value *Broadcasted = getBroadcastInstrs(ReverseInd);
02924         // After broadcasting the induction variable we need to make the
02925         // vector consecutive by adding  ... -3, -2, -1, 0.
02926         for (unsigned part = 0; part < UF; ++part)
02927           Entry[part] = getConsecutiveVector(Broadcasted, -(int)VF * part,
02928                                              true);
02929         return;
02930       }
02931 
02932       // Handle the pointer induction variable case.
02933       assert(P->getType()->isPointerTy() && "Unexpected type.");
02934 
02935       // Is this a reverse induction ptr or a consecutive induction ptr.
02936       bool Reverse = (LoopVectorizationLegality::IK_ReversePtrInduction ==
02937                       II.IK);
02938 
02939       // This is the vector of results. Notice that we don't generate
02940       // vector geps because scalar geps result in better code.
02941       for (unsigned part = 0; part < UF; ++part) {
02942         if (VF == 1) {
02943           int EltIndex = (part) * (Reverse ? -1 : 1);
02944           Constant *Idx = ConstantInt::get(Induction->getType(), EltIndex);
02945           Value *GlobalIdx;
02946           if (Reverse)
02947             GlobalIdx = Builder.CreateSub(Idx, NormalizedIdx, "gep.ridx");
02948           else
02949             GlobalIdx = Builder.CreateAdd(NormalizedIdx, Idx, "gep.idx");
02950 
02951           Value *SclrGep = Builder.CreateGEP(II.StartValue, GlobalIdx,
02952                                              "next.gep");
02953           Entry[part] = SclrGep;
02954           continue;
02955         }
02956 
02957         Value *VecVal = UndefValue::get(VectorType::get(P->getType(), VF));
02958         for (unsigned int i = 0; i < VF; ++i) {
02959           int EltIndex = (i + part * VF) * (Reverse ? -1 : 1);
02960           Constant *Idx = ConstantInt::get(Induction->getType(), EltIndex);
02961           Value *GlobalIdx;
02962           if (!Reverse)
02963             GlobalIdx = Builder.CreateAdd(NormalizedIdx, Idx, "gep.idx");
02964           else
02965             GlobalIdx = Builder.CreateSub(Idx, NormalizedIdx, "gep.ridx");
02966 
02967           Value *SclrGep = Builder.CreateGEP(II.StartValue, GlobalIdx,
02968                                              "next.gep");
02969           VecVal = Builder.CreateInsertElement(VecVal, SclrGep,
02970                                                Builder.getInt32(i),
02971                                                "insert.gep");
02972         }
02973         Entry[part] = VecVal;
02974       }
02975       return;
02976   }
02977 }
02978 
02979 void InnerLoopVectorizer::vectorizeBlockInLoop(BasicBlock *BB, PhiVector *PV) {
02980   // For each instruction in the old loop.
02981   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
02982     VectorParts &Entry = WidenMap.get(it);
02983     switch (it->getOpcode()) {
02984     case Instruction::Br:
02985       // Nothing to do for PHIs and BR, since we already took care of the
02986       // loop control flow instructions.
02987       continue;
02988     case Instruction::PHI:{
02989       // Vectorize PHINodes.
02990       widenPHIInstruction(it, Entry, UF, VF, PV);
02991       continue;
02992     }// End of PHI.
02993 
02994     case Instruction::Add:
02995     case Instruction::FAdd:
02996     case Instruction::Sub:
02997     case Instruction::FSub:
02998     case Instruction::Mul:
02999     case Instruction::FMul:
03000     case Instruction::UDiv:
03001     case Instruction::SDiv:
03002     case Instruction::FDiv:
03003     case Instruction::URem:
03004     case Instruction::SRem:
03005     case Instruction::FRem:
03006     case Instruction::Shl:
03007     case Instruction::LShr:
03008     case Instruction::AShr:
03009     case Instruction::And:
03010     case Instruction::Or:
03011     case Instruction::Xor: {
03012       // Just widen binops.
03013       BinaryOperator *BinOp = dyn_cast<BinaryOperator>(it);
03014       setDebugLocFromInst(Builder, BinOp);
03015       VectorParts &A = getVectorValue(it->getOperand(0));
03016       VectorParts &B = getVectorValue(it->getOperand(1));
03017 
03018       // Use this vector value for all users of the original instruction.
03019       for (unsigned Part = 0; Part < UF; ++Part) {
03020         Value *V = Builder.CreateBinOp(BinOp->getOpcode(), A[Part], B[Part]);
03021 
03022         // Update the NSW, NUW and Exact flags. Notice: V can be an Undef.
03023         BinaryOperator *VecOp = dyn_cast<BinaryOperator>(V);
03024         if (VecOp && isa<OverflowingBinaryOperator>(BinOp)) {
03025           VecOp->setHasNoSignedWrap(BinOp->hasNoSignedWrap());
03026           VecOp->setHasNoUnsignedWrap(BinOp->hasNoUnsignedWrap());
03027         }
03028         if (VecOp && isa<PossiblyExactOperator>(VecOp))
03029           VecOp->setIsExact(BinOp->isExact());
03030 
03031         // Copy the fast-math flags.
03032         if (VecOp && isa<FPMathOperator>(V))
03033           VecOp->setFastMathFlags(it->getFastMathFlags());
03034 
03035         Entry[Part] = V;
03036       }
03037       break;
03038     }
03039     case Instruction::Select: {
03040       // Widen selects.
03041       // If the selector is loop invariant we can create a select
03042       // instruction with a scalar condition. Otherwise, use vector-select.
03043       bool InvariantCond = SE->isLoopInvariant(SE->getSCEV(it->getOperand(0)),
03044                                                OrigLoop);
03045       setDebugLocFromInst(Builder, it);
03046 
03047       // The condition can be loop invariant  but still defined inside the
03048       // loop. This means that we can't just use the original 'cond' value.
03049       // We have to take the 'vectorized' value and pick the first lane.
03050       // Instcombine will make this a no-op.
03051       VectorParts &Cond = getVectorValue(it->getOperand(0));
03052       VectorParts &Op0  = getVectorValue(it->getOperand(1));
03053       VectorParts &Op1  = getVectorValue(it->getOperand(2));
03054 
03055       Value *ScalarCond = (VF == 1) ? Cond[0] :
03056         Builder.CreateExtractElement(Cond[0], Builder.getInt32(0));
03057 
03058       for (unsigned Part = 0; Part < UF; ++Part) {
03059         Entry[Part] = Builder.CreateSelect(
03060           InvariantCond ? ScalarCond : Cond[Part],
03061           Op0[Part],
03062           Op1[Part]);
03063       }
03064       break;
03065     }
03066 
03067     case Instruction::ICmp:
03068     case Instruction::FCmp: {
03069       // Widen compares. Generate vector compares.
03070       bool FCmp = (it->getOpcode() == Instruction::FCmp);
03071       CmpInst *Cmp = dyn_cast<CmpInst>(it);
03072       setDebugLocFromInst(Builder, it);
03073       VectorParts &A = getVectorValue(it->getOperand(0));
03074       VectorParts &B = getVectorValue(it->getOperand(1));
03075       for (unsigned Part = 0; Part < UF; ++Part) {
03076         Value *C = 0;
03077         if (FCmp)
03078           C = Builder.CreateFCmp(Cmp->getPredicate(), A[Part], B[Part]);
03079         else
03080           C = Builder.CreateICmp(Cmp->getPredicate(), A[Part], B[Part]);
03081         Entry[Part] = C;
03082       }
03083       break;
03084     }
03085 
03086     case Instruction::Store:
03087     case Instruction::Load:
03088       vectorizeMemoryInstruction(it);
03089         break;
03090     case Instruction::ZExt:
03091     case Instruction::SExt:
03092     case Instruction::FPToUI:
03093     case Instruction::FPToSI:
03094     case Instruction::FPExt:
03095     case Instruction::PtrToInt:
03096     case Instruction::IntToPtr:
03097     case Instruction::SIToFP:
03098     case Instruction::UIToFP:
03099     case Instruction::Trunc:
03100     case Instruction::FPTrunc:
03101     case Instruction::BitCast: {
03102       CastInst *CI = dyn_cast<CastInst>(it);
03103       setDebugLocFromInst(Builder, it);
03104       /// Optimize the special case where the source is the induction
03105       /// variable. Notice that we can only optimize the 'trunc' case
03106       /// because: a. FP conversions lose precision, b. sext/zext may wrap,
03107       /// c. other casts depend on pointer size.
03108       if (CI->getOperand(0) == OldInduction &&
03109           it->getOpcode() == Instruction::Trunc) {
03110         Value *ScalarCast = Builder.CreateCast(CI->getOpcode(), Induction,
03111                                                CI->getType());
03112         Value *Broadcasted = getBroadcastInstrs(ScalarCast);
03113         for (unsigned Part = 0; Part < UF; ++Part)
03114           Entry[Part] = getConsecutiveVector(Broadcasted, VF * Part, false);
03115         break;
03116       }
03117       /// Vectorize casts.
03118       Type *DestTy = (VF == 1) ? CI->getType() :
03119                                  VectorType::get(CI->getType(), VF);
03120 
03121       VectorParts &A = getVectorValue(it->getOperand(0));
03122       for (unsigned Part = 0; Part < UF; ++Part)
03123         Entry[Part] = Builder.CreateCast(CI->getOpcode(), A[Part], DestTy);
03124       break;
03125     }
03126 
03127     case Instruction::Call: {
03128       // Ignore dbg intrinsics.
03129       if (isa<DbgInfoIntrinsic>(it))
03130         break;
03131       setDebugLocFromInst(Builder, it);
03132 
03133       Module *M = BB->getParent()->getParent();
03134       CallInst *CI = cast<CallInst>(it);
03135       Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
03136       assert(ID && "Not an intrinsic call!");
03137       switch (ID) {
03138       case Intrinsic::lifetime_end:
03139       case Intrinsic::lifetime_start:
03140         scalarizeInstruction(it);
03141         break;
03142       default:
03143         for (unsigned Part = 0; Part < UF; ++Part) {
03144           SmallVector<Value *, 4> Args;
03145           for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i) {
03146             VectorParts &Arg = getVectorValue(CI->getArgOperand(i));
03147             Args.push_back(Arg[Part]);
03148           }
03149           Type *Tys[] = {CI->getType()};
03150           if (VF > 1)
03151             Tys[0] = VectorType::get(CI->getType()->getScalarType(), VF);
03152 
03153           Function *F = Intrinsic::getDeclaration(M, ID, Tys);
03154           Entry[Part] = Builder.CreateCall(F, Args);
03155         }
03156         break;
03157       }
03158       break;
03159     }
03160 
03161     default:
03162       // All other instructions are unsupported. Scalarize them.
03163       scalarizeInstruction(it);
03164       break;
03165     }// end of switch.
03166   }// end of for_each instr.
03167 }
03168 
03169 void InnerLoopVectorizer::updateAnalysis() {
03170   // Forget the original basic block.
03171   SE->forgetLoop(OrigLoop);
03172 
03173   // Update the dominator tree information.
03174   assert(DT->properlyDominates(LoopBypassBlocks.front(), LoopExitBlock) &&
03175          "Entry does not dominate exit.");
03176 
03177   for (unsigned I = 1, E = LoopBypassBlocks.size(); I != E; ++I)
03178     DT->addNewBlock(LoopBypassBlocks[I], LoopBypassBlocks[I-1]);
03179   DT->addNewBlock(LoopVectorPreHeader, LoopBypassBlocks.back());
03180 
03181   // Due to if predication of stores we might create a sequence of "if(pred)
03182   // a[i] = ...;  " blocks.
03183   for (unsigned i = 0, e = LoopVectorBody.size(); i != e; ++i) {
03184     if (i == 0)
03185       DT->addNewBlock(LoopVectorBody[0], LoopVectorPreHeader);
03186     else if (isPredicatedBlock(i)) {
03187       DT->addNewBlock(LoopVectorBody[i], LoopVectorBody[i-1]);
03188     } else {
03189       DT->addNewBlock(LoopVectorBody[i], LoopVectorBody[i-2]);
03190     }
03191   }
03192 
03193   DT->addNewBlock(LoopMiddleBlock, LoopBypassBlocks.front());
03194   DT->addNewBlock(LoopScalarPreHeader, LoopMiddleBlock);
03195   DT->changeImmediateDominator(LoopScalarBody, LoopScalarPreHeader);
03196   DT->changeImmediateDominator(LoopExitBlock, LoopMiddleBlock);
03197 
03198   DEBUG(DT->verifyDomTree());
03199 }
03200 
03201 /// \brief Check whether it is safe to if-convert this phi node.
03202 ///
03203 /// Phi nodes with constant expressions that can trap are not safe to if
03204 /// convert.
03205 static bool canIfConvertPHINodes(BasicBlock *BB) {
03206   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
03207     PHINode *Phi = dyn_cast<PHINode>(I);
03208     if (!Phi)
03209       return true;
03210     for (unsigned p = 0, e = Phi->getNumIncomingValues(); p != e; ++p)
03211       if (Constant *C = dyn_cast<Constant>(Phi->getIncomingValue(p)))
03212         if (C->canTrap())
03213           return false;
03214   }
03215   return true;
03216 }
03217 
03218 bool LoopVectorizationLegality::canVectorizeWithIfConvert() {
03219   if (!EnableIfConversion)
03220     return false;
03221 
03222   assert(TheLoop->getNumBlocks() > 1 && "Single block loops are vectorizable");
03223 
03224   // A list of pointers that we can safely read and write to.
03225   SmallPtrSet<Value *, 8> SafePointes;
03226 
03227   // Collect safe addresses.
03228   for (Loop::block_iterator BI = TheLoop->block_begin(),
03229          BE = TheLoop->block_end(); BI != BE; ++BI) {
03230     BasicBlock *BB = *BI;
03231 
03232     if (blockNeedsPredication(BB))
03233       continue;
03234 
03235     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
03236       if (LoadInst *LI = dyn_cast<LoadInst>(I))
03237         SafePointes.insert(LI->getPointerOperand());
03238       else if (StoreInst *SI = dyn_cast<StoreInst>(I))
03239         SafePointes.insert(SI->getPointerOperand());
03240     }
03241   }
03242 
03243   // Collect the blocks that need predication.
03244   BasicBlock *Header = TheLoop->getHeader();
03245   for (Loop::block_iterator BI = TheLoop->block_begin(),
03246          BE = TheLoop->block_end(); BI != BE; ++BI) {
03247     BasicBlock *BB = *BI;
03248 
03249     // We don't support switch statements inside loops.
03250     if (!isa<BranchInst>(BB->getTerminator()))
03251       return false;
03252 
03253     // We must be able to predicate all blocks that need to be predicated.
03254     if (blockNeedsPredication(BB)) {
03255       if (!blockCanBePredicated(BB, SafePointes))
03256         return false;
03257     } else if (BB != Header && !canIfConvertPHINodes(BB))
03258       return false;
03259 
03260   }
03261 
03262   // We can if-convert this loop.
03263   return true;
03264 }
03265 
03266 bool LoopVectorizationLegality::canVectorize() {
03267   // We must have a loop in canonical form. Loops with indirectbr in them cannot
03268   // be canonicalized.
03269   if (!TheLoop->getLoopPreheader())
03270     return false;
03271 
03272   // We can only vectorize innermost loops.
03273   if (TheLoop->getSubLoopsVector().size())
03274     return false;
03275 
03276   // We must have a single backedge.
03277   if (TheLoop->getNumBackEdges() != 1)
03278     return false;
03279 
03280   // We must have a single exiting block.
03281   if (!TheLoop->getExitingBlock())
03282     return false;
03283 
03284   // We need to have a loop header.
03285   DEBUG(dbgs() << "LV: Found a loop: " <<
03286         TheLoop->getHeader()->getName() << '\n');
03287 
03288   // Check if we can if-convert non-single-bb loops.
03289   unsigned NumBlocks = TheLoop->getNumBlocks();
03290   if (NumBlocks != 1 && !canVectorizeWithIfConvert()) {
03291     DEBUG(dbgs() << "LV: Can't if-convert the loop.\n");
03292     return false;
03293   }
03294 
03295   // ScalarEvolution needs to be able to find the exit count.
03296   const SCEV *ExitCount = SE->getBackedgeTakenCount(TheLoop);
03297   if (ExitCount == SE->getCouldNotCompute()) {
03298     DEBUG(dbgs() << "LV: SCEV could not compute the loop exit count.\n");
03299     return false;
03300   }
03301 
03302   // Do not loop-vectorize loops with a tiny trip count.
03303   BasicBlock *Latch = TheLoop->getLoopLatch();
03304   unsigned TC = SE->getSmallConstantTripCount(TheLoop, Latch);
03305   if (TC > 0u && TC < TinyTripCountVectorThreshold) {
03306     DEBUG(dbgs() << "LV: Found a loop with a very small trip count. " <<
03307           "This loop is not worth vectorizing.\n");
03308     return false;
03309   }
03310 
03311   // Check if we can vectorize the instructions and CFG in this loop.
03312   if (!canVectorizeInstrs()) {
03313     DEBUG(dbgs() << "LV: Can't vectorize the instructions or CFG\n");
03314     return false;
03315   }
03316 
03317   // Go over each instruction and look at memory deps.
03318   if (!canVectorizeMemory()) {
03319     DEBUG(dbgs() << "LV: Can't vectorize due to memory conflicts\n");
03320     return false;
03321   }
03322 
03323   // Collect all of the variables that remain uniform after vectorization.
03324   collectLoopUniforms();
03325 
03326   DEBUG(dbgs() << "LV: We can vectorize this loop" <<
03327         (PtrRtCheck.Need ? " (with a runtime bound check)" : "")
03328         <<"!\n");
03329 
03330   // Okay! We can vectorize. At this point we don't have any other mem analysis
03331   // which may limit our maximum vectorization factor, so just return true with
03332   // no restrictions.
03333   return true;
03334 }
03335 
03336 static Type *convertPointerToIntegerType(const DataLayout &DL, Type *Ty) {
03337   if (Ty->isPointerTy())
03338     return DL.getIntPtrType(Ty);
03339 
03340   // It is possible that char's or short's overflow when we ask for the loop's
03341   // trip count, work around this by changing the type size.
03342   if (Ty->getScalarSizeInBits() < 32)
03343     return Type::getInt32Ty(Ty->getContext());
03344 
03345   return Ty;
03346 }
03347 
03348 static Type* getWiderType(const DataLayout &DL, Type *Ty0, Type *Ty1) {
03349   Ty0 = convertPointerToIntegerType(DL, Ty0);
03350   Ty1 = convertPointerToIntegerType(DL, Ty1);
03351   if (Ty0->getScalarSizeInBits() > Ty1->getScalarSizeInBits())
03352     return Ty0;
03353   return Ty1;
03354 }
03355 
03356 /// \brief Check that the instruction has outside loop users and is not an
03357 /// identified reduction variable.
03358 static bool hasOutsideLoopUser(const Loop *TheLoop, Instruction *Inst,
03359                                SmallPtrSet<Value *, 4> &Reductions) {
03360   // Reduction instructions are allowed to have exit users. All other
03361   // instructions must not have external users.
03362   if (!Reductions.count(Inst))
03363     //Check that all of the users of the loop are inside the BB.
03364     for (User *U : Inst->users()) {
03365       Instruction *UI = cast<Instruction>(U);
03366       // This user may be a reduction exit value.
03367       if (!TheLoop->contains(UI)) {
03368         DEBUG(dbgs() << "LV: Found an outside user for : " << *UI << '\n');
03369         return true;
03370       }
03371     }
03372   return false;
03373 }
03374 
03375 bool LoopVectorizationLegality::canVectorizeInstrs() {
03376   BasicBlock *PreHeader = TheLoop->getLoopPreheader();
03377   BasicBlock *Header = TheLoop->getHeader();
03378 
03379   // Look for the attribute signaling the absence of NaNs.
03380   Function &F = *Header->getParent();
03381   if (F.hasFnAttribute("no-nans-fp-math"))
03382     HasFunNoNaNAttr = F.getAttributes().getAttribute(
03383       AttributeSet::FunctionIndex,
03384       "no-nans-fp-math").getValueAsString() == "true";
03385 
03386   // For each block in the loop.
03387   for (Loop::block_iterator bb = TheLoop->block_begin(),
03388        be = TheLoop->block_end(); bb != be; ++bb) {
03389 
03390     // Scan the instructions in the block and look for hazards.
03391     for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
03392          ++it) {
03393 
03394       if (PHINode *Phi = dyn_cast<PHINode>(it)) {
03395         Type *PhiTy = Phi->getType();
03396         // Check that this PHI type is allowed.
03397         if (!PhiTy->isIntegerTy() &&
03398             !PhiTy->isFloatingPointTy() &&
03399             !PhiTy->isPointerTy()) {
03400           DEBUG(dbgs() << "LV: Found an non-int non-pointer PHI.\n");
03401           return false;
03402         }
03403 
03404         // If this PHINode is not in the header block, then we know that we
03405         // can convert it to select during if-conversion. No need to check if
03406         // the PHIs in this block are induction or reduction variables.
03407         if (*bb != Header) {
03408           // Check that this instruction has no outside users or is an
03409           // identified reduction value with an outside user.
03410           if(!hasOutsideLoopUser(TheLoop, it, AllowedExit))
03411             continue;
03412           return false;
03413         }
03414 
03415         // We only allow if-converted PHIs with more than two incoming values.
03416         if (Phi->getNumIncomingValues() != 2) {
03417           DEBUG(dbgs() << "LV: Found an invalid PHI.\n");
03418           return false;
03419         }
03420 
03421         // This is the value coming from the preheader.
03422         Value *StartValue = Phi->getIncomingValueForBlock(PreHeader);
03423         // Check if this is an induction variable.
03424         InductionKind IK = isInductionVariable(Phi);
03425 
03426         if (IK_NoInduction != IK) {
03427           // Get the widest type.
03428           if (!WidestIndTy)
03429             WidestIndTy = convertPointerToIntegerType(*DL, PhiTy);
03430           else
03431             WidestIndTy = getWiderType(*DL, PhiTy, WidestIndTy);
03432 
03433           // Int inductions are special because we only allow one IV.
03434           if (IK == IK_IntInduction) {
03435             // Use the phi node with the widest type as induction. Use the last
03436             // one if there are multiple (no good reason for doing this other
03437             // than it is expedient).
03438             if (!Induction || PhiTy == WidestIndTy)
03439               Induction = Phi;
03440           }
03441 
03442           DEBUG(dbgs() << "LV: Found an induction variable.\n");
03443           Inductions[Phi] = InductionInfo(StartValue, IK);
03444 
03445           // Until we explicitly handle the case of an induction variable with
03446           // an outside loop user we have to give up vectorizing this loop.
03447           if (hasOutsideLoopUser(TheLoop, it, AllowedExit))
03448             return false;
03449 
03450           continue;
03451         }
03452 
03453         if (AddReductionVar(Phi, RK_IntegerAdd)) {
03454           DEBUG(dbgs() << "LV: Found an ADD reduction PHI."<< *Phi <<"\n");
03455           continue;
03456         }
03457         if (AddReductionVar(Phi, RK_IntegerMult)) {
03458           DEBUG(dbgs() << "LV: Found a MUL reduction PHI."<< *Phi <<"\n");
03459           continue;
03460         }
03461         if (AddReductionVar(Phi, RK_IntegerOr)) {
03462           DEBUG(dbgs() << "LV: Found an OR reduction PHI."<< *Phi <<"\n");
03463           continue;
03464         }
03465         if (AddReductionVar(Phi, RK_IntegerAnd)) {
03466           DEBUG(dbgs() << "LV: Found an AND reduction PHI."<< *Phi <<"\n");
03467           continue;
03468         }
03469         if (AddReductionVar(Phi, RK_IntegerXor)) {
03470           DEBUG(dbgs() << "LV: Found a XOR reduction PHI."<< *Phi <<"\n");
03471           continue;
03472         }
03473         if (AddReductionVar(Phi, RK_IntegerMinMax)) {
03474           DEBUG(dbgs() << "LV: Found a MINMAX reduction PHI."<< *Phi <<"\n");
03475           continue;
03476         }
03477         if (AddReductionVar(Phi, RK_FloatMult)) {
03478           DEBUG(dbgs() << "LV: Found an FMult reduction PHI."<< *Phi <<"\n");
03479           continue;
03480         }
03481         if (AddReductionVar(Phi, RK_FloatAdd)) {
03482           DEBUG(dbgs() << "LV: Found an FAdd reduction PHI."<< *Phi <<"\n");
03483           continue;
03484         }
03485         if (AddReductionVar(Phi, RK_FloatMinMax)) {
03486           DEBUG(dbgs() << "LV: Found an float MINMAX reduction PHI."<< *Phi <<
03487                 "\n");
03488           continue;
03489         }
03490 
03491         DEBUG(dbgs() << "LV: Found an unidentified PHI."<< *Phi <<"\n");
03492         return false;
03493       }// end of PHI handling
03494 
03495       // We still don't handle functions. However, we can ignore dbg intrinsic
03496       // calls and we do handle certain intrinsic and libm functions.
03497       CallInst *CI = dyn_cast<CallInst>(it);
03498       if (CI && !getIntrinsicIDForCall(CI, TLI) && !isa<DbgInfoIntrinsic>(CI)) {
03499         DEBUG(dbgs() << "LV: Found a call site.\n");
03500         return false;
03501       }
03502 
03503       // Check that the instruction return type is vectorizable.
03504       // Also, we can't vectorize extractelement instructions.
03505       if ((!VectorType::isValidElementType(it->getType()) &&
03506            !it->getType()->isVoidTy()) || isa<ExtractElementInst>(it)) {
03507         DEBUG(dbgs() << "LV: Found unvectorizable type.\n");
03508         return false;
03509       }
03510 
03511       // Check that the stored type is vectorizable.
03512       if (StoreInst *ST = dyn_cast<StoreInst>(it)) {
03513         Type *T = ST->getValueOperand()->getType();
03514         if (!VectorType::isValidElementType(T))
03515           return false;
03516         if (EnableMemAccessVersioning)
03517           collectStridedAcccess(ST);
03518       }
03519 
03520       if (EnableMemAccessVersioning)
03521         if (LoadInst *LI = dyn_cast<LoadInst>(it))
03522           collectStridedAcccess(LI);
03523 
03524       // Reduction instructions are allowed to have exit users.
03525       // All other instructions must not have external users.
03526       if (hasOutsideLoopUser(TheLoop, it, AllowedExit))
03527         return false;
03528 
03529     } // next instr.
03530 
03531   }
03532 
03533   if (!Induction) {
03534     DEBUG(dbgs() << "LV: Did not find one integer induction var.\n");
03535     if (Inductions.empty())
03536       return false;
03537   }
03538 
03539   return true;
03540 }
03541 
03542 ///\brief Remove GEPs whose indices but the last one are loop invariant and
03543 /// return the induction operand of the gep pointer.
03544 static Value *stripGetElementPtr(Value *Ptr, ScalarEvolution *SE,
03545                                  const DataLayout *DL, Loop *Lp) {
03546   GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr);
03547   if (!GEP)
03548     return Ptr;
03549 
03550   unsigned InductionOperand = getGEPInductionOperand(DL, GEP);
03551 
03552   // Check that all of the gep indices are uniform except for our induction
03553   // operand.
03554   for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i)
03555     if (i != InductionOperand &&
03556         !SE->isLoopInvariant(SE->getSCEV(GEP->getOperand(i)), Lp))
03557       return Ptr;
03558   return GEP->getOperand(InductionOperand);
03559 }
03560 
03561 ///\brief Look for a cast use of the passed value.
03562 static Value *getUniqueCastUse(Value *Ptr, Loop *Lp, Type *Ty) {
03563   Value *UniqueCast = 0;
03564   for (User *U : Ptr->users()) {
03565     CastInst *CI = dyn_cast<CastInst>(U);
03566     if (CI && CI->getType() == Ty) {
03567       if (!UniqueCast)
03568         UniqueCast = CI;
03569       else
03570         return 0;
03571     }
03572   }
03573   return UniqueCast;
03574 }
03575 
03576 ///\brief Get the stride of a pointer access in a loop.
03577 /// Looks for symbolic strides "a[i*stride]". Returns the symbolic stride as a
03578 /// pointer to the Value, or null otherwise.
03579 static Value *getStrideFromPointer(Value *Ptr, ScalarEvolution *SE,
03580                                    const DataLayout *DL, Loop *Lp) {
03581   const PointerType *PtrTy = dyn_cast<PointerType>(Ptr->getType());
03582   if (!PtrTy || PtrTy->isAggregateType())
03583     return 0;
03584 
03585   // Try to remove a gep instruction to make the pointer (actually index at this
03586   // point) easier analyzable. If OrigPtr is equal to Ptr we are analzying the
03587   // pointer, otherwise, we are analyzing the index.
03588   Value *OrigPtr = Ptr;
03589 
03590   // The size of the pointer access.
03591   int64_t PtrAccessSize = 1;
03592 
03593   Ptr = stripGetElementPtr(Ptr, SE, DL, Lp);
03594   const SCEV *V = SE->getSCEV(Ptr);
03595 
03596   if (Ptr != OrigPtr)
03597     // Strip off casts.
03598     while (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V))
03599       V = C->getOperand();
03600 
03601   const SCEVAddRecExpr *S = dyn_cast<SCEVAddRecExpr>(V);
03602   if (!S)
03603     return 0;
03604 
03605   V = S->getStepRecurrence(*SE);
03606   if (!V)
03607     return 0;
03608 
03609   // Strip off the size of access multiplication if we are still analyzing the
03610   // pointer.
03611   if (OrigPtr == Ptr) {
03612     DL->getTypeAllocSize(PtrTy->getElementType());
03613     if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(V)) {
03614       if (M->getOperand(0)->getSCEVType() != scConstant)
03615         return 0;
03616 
03617       const APInt &APStepVal =
03618           cast<SCEVConstant>(M->getOperand(0))->getValue()->getValue();
03619 
03620       // Huge step value - give up.
03621       if (APStepVal.getBitWidth() > 64)
03622         return 0;
03623 
03624       int64_t StepVal = APStepVal.getSExtValue();
03625       if (PtrAccessSize != StepVal)
03626         return 0;
03627       V = M->getOperand(1);
03628     }
03629   }
03630 
03631   // Strip off casts.
03632   Type *StripedOffRecurrenceCast = 0;
03633   if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V)) {
03634     StripedOffRecurrenceCast = C->getType();
03635     V = C->getOperand();
03636   }
03637 
03638   // Look for the loop invariant symbolic value.
03639   const SCEVUnknown *U = dyn_cast<SCEVUnknown>(V);
03640   if (!U)
03641     return 0;
03642 
03643   Value *Stride = U->getValue();
03644   if (!Lp->isLoopInvariant(Stride))
03645     return 0;
03646 
03647   // If we have stripped off the recurrence cast we have to make sure that we
03648   // return the value that is used in this loop so that we can replace it later.
03649   if (StripedOffRecurrenceCast)
03650     Stride = getUniqueCastUse(Stride, Lp, StripedOffRecurrenceCast);
03651 
03652   return Stride;
03653 }
03654 
03655 void LoopVectorizationLegality::collectStridedAcccess(Value *MemAccess) {
03656   Value *Ptr = 0;
03657   if (LoadInst *LI = dyn_cast<LoadInst>(MemAccess))
03658     Ptr = LI->getPointerOperand();
03659   else if (StoreInst *SI = dyn_cast<StoreInst>(MemAccess))
03660     Ptr = SI->getPointerOperand();
03661   else
03662     return;
03663 
03664   Value *Stride = getStrideFromPointer(Ptr, SE, DL, TheLoop);
03665   if (!Stride)
03666     return;
03667 
03668   DEBUG(dbgs() << "LV: Found a strided access that we can version");
03669   DEBUG(dbgs() << "  Ptr: " << *Ptr << " Stride: " << *Stride << "\n");
03670   Strides[Ptr] = Stride;
03671   StrideSet.insert(Stride);
03672 }
03673 
03674 void LoopVectorizationLegality::collectLoopUniforms() {
03675   // We now know that the loop is vectorizable!
03676   // Collect variables that will remain uniform after vectorization.
03677   std::vector<Value*> Worklist;
03678   BasicBlock *Latch = TheLoop->getLoopLatch();
03679 
03680   // Start with the conditional branch and walk up the block.
03681   Worklist.push_back(Latch->getTerminator()->getOperand(0));
03682 
03683   // Also add all consecutive pointer values; these values will be uniform
03684   // after vectorization (and subsequent cleanup) and, until revectorization is
03685   // supported, all dependencies must also be uniform.
03686   for (Loop::block_iterator B = TheLoop->block_begin(),
03687        BE = TheLoop->block_end(); B != BE; ++B)
03688     for (BasicBlock::iterator I = (*B)->begin(), IE = (*B)->end();
03689          I != IE; ++I)
03690       if (I->getType()->isPointerTy() && isConsecutivePtr(I))
03691         Worklist.insert(Worklist.end(), I->op_begin(), I->op_end());
03692 
03693   while (Worklist.size()) {
03694     Instruction *I = dyn_cast<Instruction>(Worklist.back());
03695     Worklist.pop_back();
03696 
03697     // Look at instructions inside this loop.
03698     // Stop when reaching PHI nodes.
03699     // TODO: we need to follow values all over the loop, not only in this block.
03700     if (!I || !TheLoop->contains(I) || isa<PHINode>(I))
03701       continue;
03702 
03703     // This is a known uniform.
03704     Uniforms.insert(I);
03705 
03706     // Insert all operands.
03707     Worklist.insert(Worklist.end(), I->op_begin(), I->op_end());
03708   }
03709 }
03710 
03711 namespace {
03712 /// \brief Analyses memory accesses in a loop.
03713 ///
03714 /// Checks whether run time pointer checks are needed and builds sets for data
03715 /// dependence checking.
03716 class AccessAnalysis {
03717 public:
03718   /// \brief Read or write access location.
03719   typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
03720   typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet;
03721 
03722   /// \brief Set of potential dependent memory accesses.
03723   typedef EquivalenceClasses<MemAccessInfo> DepCandidates;
03724 
03725   AccessAnalysis(const DataLayout *Dl, DepCandidates &DA) :
03726     DL(Dl), DepCands(DA), AreAllWritesIdentified(true),
03727     AreAllReadsIdentified(true), IsRTCheckNeeded(false) {}
03728 
03729   /// \brief Register a load  and whether it is only read from.
03730   void addLoad(Value *Ptr, bool IsReadOnly) {
03731     Accesses.insert(MemAccessInfo(Ptr, false));
03732     if (IsReadOnly)
03733       ReadOnlyPtr.insert(Ptr);
03734   }
03735 
03736   /// \brief Register a store.
03737   void addStore(Value *Ptr) {
03738     Accesses.insert(MemAccessInfo(Ptr, true));
03739   }
03740 
03741   /// \brief Check whether we can check the pointers at runtime for
03742   /// non-intersection.
03743   bool canCheckPtrAtRT(LoopVectorizationLegality::RuntimePointerCheck &RtCheck,
03744                        unsigned &NumComparisons, ScalarEvolution *SE,
03745                        Loop *TheLoop, ValueToValueMap &Strides,
03746                        bool ShouldCheckStride = false);
03747 
03748   /// \brief Goes over all memory accesses, checks whether a RT check is needed
03749   /// and builds sets of dependent accesses.
03750   void buildDependenceSets() {
03751     // Process read-write pointers first.
03752     processMemAccesses(false);
03753     // Next, process read pointers.
03754     processMemAccesses(true);
03755   }
03756 
03757   bool isRTCheckNeeded() { return IsRTCheckNeeded; }
03758 
03759   bool isDependencyCheckNeeded() { return !CheckDeps.empty(); }
03760   void resetDepChecks() { CheckDeps.clear(); }
03761 
03762   MemAccessInfoSet &getDependenciesToCheck() { return CheckDeps; }
03763 
03764 private:
03765   typedef SetVector<MemAccessInfo> PtrAccessSet;
03766   typedef DenseMap<Value*, MemAccessInfo> UnderlyingObjToAccessMap;
03767 
03768   /// \brief Go over all memory access or only the deferred ones if
03769   /// \p UseDeferred is true and check whether runtime pointer checks are needed
03770   /// and build sets of dependency check candidates.
03771   void processMemAccesses(bool UseDeferred);
03772 
03773   /// Set of all accesses.
03774   PtrAccessSet Accesses;
03775 
03776   /// Set of access to check after all writes have been processed.
03777   PtrAccessSet DeferredAccesses;
03778 
03779   /// Map of pointers to last access encountered.
03780   UnderlyingObjToAccessMap ObjToLastAccess;
03781 
03782   /// Set of accesses that need a further dependence check.
03783   MemAccessInfoSet CheckDeps;
03784 
03785   /// Set of pointers that are read only.
03786   SmallPtrSet<Value*, 16> ReadOnlyPtr;
03787 
03788   /// Set of underlying objects already written to.
03789   SmallPtrSet<Value*, 16> WriteObjects;
03790 
03791   const DataLayout *DL;
03792 
03793   /// Sets of potentially dependent accesses - members of one set share an
03794   /// underlying pointer. The set "CheckDeps" identfies which sets really need a
03795   /// dependence check.
03796   DepCandidates &DepCands;
03797 
03798   bool AreAllWritesIdentified;
03799   bool AreAllReadsIdentified;
03800   bool IsRTCheckNeeded;
03801 };
03802 
03803 } // end anonymous namespace
03804 
03805 /// \brief Check whether a pointer can participate in a runtime bounds check.
03806 static bool hasComputableBounds(ScalarEvolution *SE, ValueToValueMap &Strides,
03807                                 Value *Ptr) {
03808   const SCEV *PtrScev = replaceSymbolicStrideSCEV(SE, Strides, Ptr);
03809   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
03810   if (!AR)
03811     return false;
03812 
03813   return AR->isAffine();
03814 }
03815 
03816 /// \brief Check the stride of the pointer and ensure that it does not wrap in
03817 /// the address space.
03818 static int isStridedPtr(ScalarEvolution *SE, const DataLayout *DL, Value *Ptr,
03819                         const Loop *Lp, ValueToValueMap &StridesMap);
03820 
03821 bool AccessAnalysis::canCheckPtrAtRT(
03822     LoopVectorizationLegality::RuntimePointerCheck &RtCheck,
03823     unsigned &NumComparisons, ScalarEvolution *SE, Loop *TheLoop,
03824     ValueToValueMap &StridesMap, bool ShouldCheckStride) {
03825   // Find pointers with computable bounds. We are going to use this information
03826   // to place a runtime bound check.
03827   unsigned NumReadPtrChecks = 0;
03828   unsigned NumWritePtrChecks = 0;
03829   bool CanDoRT = true;
03830 
03831   bool IsDepCheckNeeded = isDependencyCheckNeeded();
03832   // We assign consecutive id to access from different dependence sets.
03833   // Accesses within the same set don't need a runtime check.
03834   unsigned RunningDepId = 1;
03835   DenseMap<Value *, unsigned> DepSetId;
03836 
03837   for (PtrAccessSet::iterator AI = Accesses.begin(), AE = Accesses.end();
03838        AI != AE; ++AI) {
03839     const MemAccessInfo &Access = *AI;
03840     Value *Ptr = Access.getPointer();
03841     bool IsWrite = Access.getInt();
03842 
03843     // Just add write checks if we have both.
03844     if (!IsWrite && Accesses.count(MemAccessInfo(Ptr, true)))
03845       continue;
03846 
03847     if (IsWrite)
03848       ++NumWritePtrChecks;
03849     else
03850       ++NumReadPtrChecks;
03851 
03852     if (hasComputableBounds(SE, StridesMap, Ptr) &&
03853         // When we run after a failing dependency check we have to make sure we
03854         // don't have wrapping pointers.
03855         (!ShouldCheckStride ||
03856          isStridedPtr(SE, DL, Ptr, TheLoop, StridesMap) == 1)) {
03857       // The id of the dependence set.
03858       unsigned DepId;
03859 
03860       if (IsDepCheckNeeded) {
03861         Value *Leader = DepCands.getLeaderValue(Access).getPointer();
03862         unsigned &LeaderId = DepSetId[Leader];
03863         if (!LeaderId)
03864           LeaderId = RunningDepId++;
03865         DepId = LeaderId;
03866       } else
03867         // Each access has its own dependence set.
03868         DepId = RunningDepId++;
03869 
03870       RtCheck.insert(SE, TheLoop, Ptr, IsWrite, DepId, StridesMap);
03871 
03872       DEBUG(dbgs() << "LV: Found a runtime check ptr:" << *Ptr << '\n');
03873     } else {
03874       CanDoRT = false;
03875     }
03876   }
03877 
03878   if (IsDepCheckNeeded && CanDoRT && RunningDepId == 2)
03879     NumComparisons = 0; // Only one dependence set.
03880   else {
03881     NumComparisons = (NumWritePtrChecks * (NumReadPtrChecks +
03882                                            NumWritePtrChecks - 1));
03883   }
03884 
03885   // If the pointers that we would use for the bounds comparison have different
03886   // address spaces, assume the values aren't directly comparable, so we can't
03887   // use them for the runtime check. We also have to assume they could
03888   // overlap. In the future there should be metadata for whether address spaces
03889   // are disjoint.
03890   unsigned NumPointers = RtCheck.Pointers.size();
03891   for (unsigned i = 0; i < NumPointers; ++i) {
03892     for (unsigned j = i + 1; j < NumPointers; ++j) {
03893       // Only need to check pointers between two different dependency sets.
03894       if (RtCheck.DependencySetId[i] == RtCheck.DependencySetId[j])
03895        continue;
03896 
03897       Value *PtrI = RtCheck.Pointers[i];
03898       Value *PtrJ = RtCheck.Pointers[j];
03899 
03900       unsigned ASi = PtrI->getType()->getPointerAddressSpace();
03901       unsigned ASj = PtrJ->getType()->getPointerAddressSpace();
03902       if (ASi != ASj) {
03903         DEBUG(dbgs() << "LV: Runtime check would require comparison between"
03904                        " different address spaces\n");
03905         return false;
03906       }
03907     }
03908   }
03909 
03910   return CanDoRT;
03911 }
03912 
03913 static bool isFunctionScopeIdentifiedObject(Value *Ptr) {
03914   return isNoAliasArgument(Ptr) || isNoAliasCall(Ptr) || isa<AllocaInst>(Ptr);
03915 }
03916 
03917 void AccessAnalysis::processMemAccesses(bool UseDeferred) {
03918   // We process the set twice: first we process read-write pointers, last we
03919   // process read-only pointers. This allows us to skip dependence tests for
03920   // read-only pointers.
03921 
03922   PtrAccessSet &S = UseDeferred ? DeferredAccesses : Accesses;
03923   for (PtrAccessSet::iterator AI = S.begin(), AE = S.end(); AI != AE; ++AI) {
03924     const MemAccessInfo &Access = *AI;
03925     Value *Ptr = Access.getPointer();
03926     bool IsWrite = Access.getInt();
03927 
03928     DepCands.insert(Access);
03929 
03930     // Memorize read-only pointers for later processing and skip them in the
03931     // first round (they need to be checked after we have seen all write
03932     // pointers). Note: we also mark pointer that are not consecutive as
03933     // "read-only" pointers (so that we check "a[b[i]] +="). Hence, we need the
03934     // second check for "!IsWrite".
03935     bool IsReadOnlyPtr = ReadOnlyPtr.count(Ptr) && !IsWrite;
03936     if (!UseDeferred && IsReadOnlyPtr) {
03937       DeferredAccesses.insert(Access);
03938       continue;
03939     }
03940 
03941     bool NeedDepCheck = false;
03942     // Check whether there is the possibility of dependency because of
03943     // underlying objects being the same.
03944     typedef SmallVector<Value*, 16> ValueVector;
03945     ValueVector TempObjects;
03946     GetUnderlyingObjects(Ptr, TempObjects, DL);
03947     for (ValueVector::iterator UI = TempObjects.begin(), UE = TempObjects.end();
03948          UI != UE; ++UI) {
03949       Value *UnderlyingObj = *UI;
03950 
03951       // If this is a write then it needs to be an identified object.  If this a
03952       // read and all writes (so far) are identified function scope objects we
03953       // don't need an identified underlying object but only an Argument (the
03954       // next write is going to invalidate this assumption if it is
03955       // unidentified).
03956       // This is a micro-optimization for the case where all writes are
03957       // identified and we have one argument pointer.
03958       // Otherwise, we do need a runtime check.
03959       if ((IsWrite && !isFunctionScopeIdentifiedObject(UnderlyingObj)) ||
03960           (!IsWrite && (!AreAllWritesIdentified ||
03961                         !isa<Argument>(UnderlyingObj)) &&
03962            !isIdentifiedObject(UnderlyingObj))) {
03963         DEBUG(dbgs() << "LV: Found an unidentified " <<
03964               (IsWrite ?  "write" : "read" ) << " ptr: " << *UnderlyingObj <<
03965               "\n");
03966         IsRTCheckNeeded = (IsRTCheckNeeded ||
03967                            !isIdentifiedObject(UnderlyingObj) ||
03968                            !AreAllReadsIdentified);
03969 
03970         if (IsWrite)
03971           AreAllWritesIdentified = false;
03972         if (!IsWrite)
03973           AreAllReadsIdentified = false;
03974       }
03975 
03976       // If this is a write - check other reads and writes for conflicts.  If
03977       // this is a read only check other writes for conflicts (but only if there
03978       // is no other write to the ptr - this is an optimization to catch "a[i] =
03979       // a[i] + " without having to do a dependence check).
03980       if ((IsWrite || IsReadOnlyPtr) && WriteObjects.count(UnderlyingObj))
03981         NeedDepCheck = true;
03982 
03983       if (IsWrite)
03984         WriteObjects.insert(UnderlyingObj);
03985 
03986       // Create sets of pointers connected by shared underlying objects.
03987       UnderlyingObjToAccessMap::iterator Prev =
03988         ObjToLastAccess.find(UnderlyingObj);
03989       if (Prev != ObjToLastAccess.end())
03990         DepCands.unionSets(Access, Prev->second);
03991 
03992       ObjToLastAccess[UnderlyingObj] = Access;
03993     }
03994 
03995     if (NeedDepCheck)
03996       CheckDeps.insert(Access);
03997   }
03998 }
03999 
04000 namespace {
04001 /// \brief Checks memory dependences among accesses to the same underlying
04002 /// object to determine whether there vectorization is legal or not (and at
04003 /// which vectorization factor).
04004 ///
04005 /// This class works under the assumption that we already checked that memory
04006 /// locations with different underlying pointers are "must-not alias".
04007 /// We use the ScalarEvolution framework to symbolically evalutate access
04008 /// functions pairs. Since we currently don't restructure the loop we can rely
04009 /// on the program order of memory accesses to determine their safety.
04010 /// At the moment we will only deem accesses as safe for:
04011 ///  * A negative constant distance assuming program order.
04012 ///
04013 ///      Safe: tmp = a[i + 1];     OR     a[i + 1] = x;
04014 ///            a[i] = tmp;                y = a[i];
04015 ///
04016 ///   The latter case is safe because later checks guarantuee that there can't
04017 ///   be a cycle through a phi node (that is, we check that "x" and "y" is not
04018 ///   the same variable: a header phi can only be an induction or a reduction, a
04019 ///   reduction can't have a memory sink, an induction can't have a memory
04020 ///   source). This is important and must not be violated (or we have to
04021 ///   resort to checking for cycles through memory).
04022 ///
04023 ///  * A positive constant distance assuming program order that is bigger
04024 ///    than the biggest memory access.
04025 ///
04026 ///     tmp = a[i]        OR              b[i] = x
04027 ///     a[i+2] = tmp                      y = b[i+2];
04028 ///
04029 ///     Safe distance: 2 x sizeof(a[0]), and 2 x sizeof(b[0]), respectively.
04030 ///
04031 ///  * Zero distances and all accesses have the same size.
04032 ///
04033 class MemoryDepChecker {
04034 public:
04035   typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
04036   typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet;
04037 
04038   MemoryDepChecker(ScalarEvolution *Se, const DataLayout *Dl, const Loop *L)
04039       : SE(Se), DL(Dl), InnermostLoop(L), AccessIdx(0),
04040         ShouldRetryWithRuntimeCheck(false) {}
04041 
04042   /// \brief Register the location (instructions are given increasing numbers)
04043   /// of a write access.
04044   void addAccess(StoreInst *SI) {
04045     Value *Ptr = SI->getPointerOperand();
04046     Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx);
04047     InstMap.push_back(SI);
04048     ++AccessIdx;
04049   }
04050 
04051   /// \brief Register the location (instructions are given increasing numbers)
04052   /// of a write access.
04053   void addAccess(LoadInst *LI) {
04054     Value *Ptr = LI->getPointerOperand();
04055     Accesses[MemAccessInfo(Ptr, false)].push_back(AccessIdx);
04056     InstMap.push_back(LI);
04057     ++AccessIdx;
04058   }
04059 
04060   /// \brief Check whether the dependencies between the accesses are safe.
04061   ///
04062   /// Only checks sets with elements in \p CheckDeps.
04063   bool areDepsSafe(AccessAnalysis::DepCandidates &AccessSets,
04064                    MemAccessInfoSet &CheckDeps, ValueToValueMap &Strides);
04065 
04066   /// \brief The maximum number of bytes of a vector register we can vectorize
04067   /// the accesses safely with.
04068   unsigned getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; }
04069 
04070   /// \brief In same cases when the dependency check fails we can still
04071   /// vectorize the loop with a dynamic array access check.
04072   bool shouldRetryWithRuntimeCheck() { return ShouldRetryWithRuntimeCheck; }
04073 
04074 private:
04075   ScalarEvolution *SE;
04076   const DataLayout *DL;
04077   const Loop *InnermostLoop;
04078 
04079   /// \brief Maps access locations (ptr, read/write) to program order.
04080   DenseMap<MemAccessInfo, std::vector<unsigned> > Accesses;
04081 
04082   /// \brief Memory access instructions in program order.
04083   SmallVector<Instruction *, 16> InstMap;
04084 
04085   /// \brief The program order index to be used for the next instruction.
04086   unsigned AccessIdx;
04087 
04088   // We can access this many bytes in parallel safely.
04089   unsigned MaxSafeDepDistBytes;
04090 
04091   /// \brief If we see a non-constant dependence distance we can still try to
04092   /// vectorize this loop with runtime checks.
04093   bool ShouldRetryWithRuntimeCheck;
04094 
04095   /// \brief Check whether there is a plausible dependence between the two
04096   /// accesses.
04097   ///
04098   /// Access \p A must happen before \p B in program order. The two indices
04099   /// identify the index into the program order map.
04100   ///
04101   /// This function checks  whether there is a plausible dependence (or the
04102   /// absence of such can't be proved) between the two accesses. If there is a
04103   /// plausible dependence but the dependence distance is bigger than one
04104   /// element access it records this distance in \p MaxSafeDepDistBytes (if this
04105   /// distance is smaller than any other distance encountered so far).
04106   /// Otherwise, this function returns true signaling a possible dependence.
04107   bool isDependent(const MemAccessInfo &A, unsigned AIdx,
04108                    const MemAccessInfo &B, unsigned BIdx,
04109                    ValueToValueMap &Strides);
04110 
04111   /// \brief Check whether the data dependence could prevent store-load
04112   /// forwarding.
04113   bool couldPreventStoreLoadForward(unsigned Distance, unsigned TypeByteSize);
04114 };
04115 
04116 } // end anonymous namespace
04117 
04118 static bool isInBoundsGep(Value *Ptr) {
04119   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr))
04120     return GEP->isInBounds();
04121   return false;
04122 }
04123 
04124 /// \brief Check whether the access through \p Ptr has a constant stride.
04125 static int isStridedPtr(ScalarEvolution *SE, const DataLayout *DL, Value *Ptr,
04126                         const Loop *Lp, ValueToValueMap &StridesMap) {
04127   const Type *Ty = Ptr->getType();
04128   assert(Ty->isPointerTy() && "Unexpected non-ptr");
04129 
04130   // Make sure that the pointer does not point to aggregate types.
04131   const PointerType *PtrTy = cast<PointerType>(Ty);
04132   if (PtrTy->getElementType()->isAggregateType()) {
04133     DEBUG(dbgs() << "LV: Bad stride - Not a pointer to a scalar type" << *Ptr <<
04134           "\n");
04135     return 0;
04136   }
04137 
04138   const SCEV *PtrScev = replaceSymbolicStrideSCEV(SE, StridesMap, Ptr);
04139 
04140   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
04141   if (!AR) {
04142     DEBUG(dbgs() << "LV: Bad stride - Not an AddRecExpr pointer "
04143           << *Ptr << " SCEV: " << *PtrScev << "\n");
04144     return 0;
04145   }
04146 
04147   // The accesss function must stride over the innermost loop.
04148   if (Lp != AR->getLoop()) {
04149     DEBUG(dbgs() << "LV: Bad stride - Not striding over innermost loop " <<
04150           *Ptr << " SCEV: " << *PtrScev << "\n");
04151   }
04152 
04153   // The address calculation must not wrap. Otherwise, a dependence could be
04154   // inverted.
04155   // An inbounds getelementptr that is a AddRec with a unit stride
04156   // cannot wrap per definition. The unit stride requirement is checked later.
04157   // An getelementptr without an inbounds attribute and unit stride would have
04158   // to access the pointer value "0" which is undefined behavior in address
04159   // space 0, therefore we can also vectorize this case.
04160   bool IsInBoundsGEP = isInBoundsGep(Ptr);
04161   bool IsNoWrapAddRec = AR->getNoWrapFlags(SCEV::NoWrapMask);
04162   bool IsInAddressSpaceZero = PtrTy->getAddressSpace() == 0;
04163   if (!IsNoWrapAddRec && !IsInBoundsGEP && !IsInAddressSpaceZero) {
04164     DEBUG(dbgs() << "LV: Bad stride - Pointer may wrap in the address space "
04165           << *Ptr << " SCEV: " << *PtrScev << "\n");
04166     return 0;
04167   }
04168 
04169   // Check the step is constant.
04170   const SCEV *Step = AR->getStepRecurrence(*SE);
04171 
04172   // Calculate the pointer stride and check if it is consecutive.
04173   const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
04174   if (!C) {
04175     DEBUG(dbgs() << "LV: Bad stride - Not a constant strided " << *Ptr <<
04176           " SCEV: " << *PtrScev << "\n");
04177     return 0;
04178   }
04179 
04180   int64_t Size = DL->getTypeAllocSize(PtrTy->getElementType());
04181   const APInt &APStepVal = C->getValue()->getValue();
04182 
04183   // Huge step value - give up.
04184   if (APStepVal.getBitWidth() > 64)
04185     return 0;
04186 
04187   int64_t StepVal = APStepVal.getSExtValue();
04188 
04189   // Strided access.
04190   int64_t Stride = StepVal / Size;
04191   int64_t Rem = StepVal % Size;
04192   if (Rem)
04193     return 0;
04194 
04195   // If the SCEV could wrap but we have an inbounds gep with a unit stride we
04196   // know we can't "wrap around the address space". In case of address space
04197   // zero we know that this won't happen without triggering undefined behavior.
04198   if (!IsNoWrapAddRec && (IsInBoundsGEP || IsInAddressSpaceZero) &&
04199       Stride != 1 && Stride != -1)
04200     return 0;
04201 
04202   return Stride;
04203 }
04204 
04205 bool MemoryDepChecker::couldPreventStoreLoadForward(unsigned Distance,
04206                                                     unsigned TypeByteSize) {
04207   // If loads occur at a distance that is not a multiple of a feasible vector
04208   // factor store-load forwarding does not take place.
04209   // Positive dependences might cause troubles because vectorizing them might
04210   // prevent store-load forwarding making vectorized code run a lot slower.
04211   //   a[i] = a[i-3] ^ a[i-8];
04212   //   The stores to a[i:i+1] don't align with the stores to a[i-3:i-2] and
04213   //   hence on your typical architecture store-load forwarding does not take
04214   //   place. Vectorizing in such cases does not make sense.
04215   // Store-load forwarding distance.
04216   const unsigned NumCyclesForStoreLoadThroughMemory = 8*TypeByteSize;
04217   // Maximum vector factor.
04218   unsigned MaxVFWithoutSLForwardIssues = MaxVectorWidth*TypeByteSize;
04219   if(MaxSafeDepDistBytes < MaxVFWithoutSLForwardIssues)
04220     MaxVFWithoutSLForwardIssues = MaxSafeDepDistBytes;
04221 
04222   for (unsigned vf = 2*TypeByteSize; vf <= MaxVFWithoutSLForwardIssues;
04223        vf *= 2) {
04224     if (Distance % vf && Distance / vf < NumCyclesForStoreLoadThroughMemory) {
04225       MaxVFWithoutSLForwardIssues = (vf >>=1);
04226       break;
04227     }
04228   }
04229 
04230   if (MaxVFWithoutSLForwardIssues< 2*TypeByteSize) {
04231     DEBUG(dbgs() << "LV: Distance " << Distance <<
04232           " that could cause a store-load forwarding conflict\n");
04233     return true;
04234   }
04235 
04236   if (MaxVFWithoutSLForwardIssues < MaxSafeDepDistBytes &&
04237       MaxVFWithoutSLForwardIssues != MaxVectorWidth*TypeByteSize)
04238     MaxSafeDepDistBytes = MaxVFWithoutSLForwardIssues;
04239   return false;
04240 }
04241 
04242 bool MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
04243                                    const MemAccessInfo &B, unsigned BIdx,
04244                                    ValueToValueMap &Strides) {
04245   assert (AIdx < BIdx && "Must pass arguments in program order");
04246 
04247   Value *APtr = A.getPointer();
04248   Value *BPtr = B.getPointer();
04249   bool AIsWrite = A.getInt();
04250   bool BIsWrite = B.getInt();
04251 
04252   // Two reads are independent.
04253   if (!AIsWrite && !BIsWrite)
04254     return false;
04255 
04256   const SCEV *AScev = replaceSymbolicStrideSCEV(SE, Strides, APtr);
04257   const SCEV *BScev = replaceSymbolicStrideSCEV(SE, Strides, BPtr);
04258 
04259   int StrideAPtr = isStridedPtr(SE, DL, APtr, InnermostLoop, Strides);
04260   int StrideBPtr = isStridedPtr(SE, DL, BPtr, InnermostLoop, Strides);
04261 
04262   const SCEV *Src = AScev;
04263   const SCEV *Sink = BScev;
04264 
04265   // If the induction step is negative we have to invert source and sink of the
04266   // dependence.
04267   if (StrideAPtr < 0) {
04268     //Src = BScev;
04269     //Sink = AScev;
04270     std::swap(APtr, BPtr);
04271     std::swap(Src, Sink);
04272     std::swap(AIsWrite, BIsWrite);
04273     std::swap(AIdx, BIdx);
04274     std::swap(StrideAPtr, StrideBPtr);
04275   }
04276 
04277   const SCEV *Dist = SE->getMinusSCEV(Sink, Src);
04278 
04279   DEBUG(dbgs() << "LV: Src Scev: " << *Src << "Sink Scev: " << *Sink
04280         << "(Induction step: " << StrideAPtr <<  ")\n");
04281   DEBUG(dbgs() << "LV: Distance for " << *InstMap[AIdx] << " to "
04282         << *InstMap[BIdx] << ": " << *Dist << "\n");
04283 
04284   // Need consecutive accesses. We don't want to vectorize
04285   // "A[B[i]] += ..." and similar code or pointer arithmetic that could wrap in
04286   // the address space.
04287   if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr){
04288     DEBUG(dbgs() << "Non-consecutive pointer access\n");
04289     return true;
04290   }
04291 
04292   const SCEVConstant *C = dyn_cast<SCEVConstant>(Dist);
04293   if (!C) {
04294     DEBUG(dbgs() << "LV: Dependence because of non-constant distance\n");
04295     ShouldRetryWithRuntimeCheck = true;
04296     return true;
04297   }
04298 
04299   Type *ATy = APtr->getType()->getPointerElementType();
04300   Type *BTy = BPtr->getType()->getPointerElementType();
04301   unsigned TypeByteSize = DL->getTypeAllocSize(ATy);
04302 
04303   // Negative distances are not plausible dependencies.
04304   const APInt &Val = C->getValue()->getValue();
04305   if (Val.isNegative()) {
04306     bool IsTrueDataDependence = (AIsWrite && !BIsWrite);
04307     if (IsTrueDataDependence &&
04308         (couldPreventStoreLoadForward(Val.abs().getZExtValue(), TypeByteSize) ||
04309          ATy != BTy))
04310       return true;
04311 
04312     DEBUG(dbgs() << "LV: Dependence is negative: NoDep\n");
04313     return false;
04314   }
04315 
04316   // Write to the same location with the same size.
04317   // Could be improved to assert type sizes are the same (i32 == float, etc).
04318   if (Val == 0) {
04319     if (ATy == BTy)
04320       return false;
04321     DEBUG(dbgs() << "LV: Zero dependence difference but different types\n");
04322     return true;
04323   }
04324 
04325   assert(Val.isStrictlyPositive() && "Expect a positive value");
04326 
04327   // Positive distance bigger than max vectorization factor.
04328   if (ATy != BTy) {
04329     DEBUG(dbgs() <<
04330           "LV: ReadWrite-Write positive dependency with different types\n");
04331     return false;
04332   }
04333 
04334   unsigned Distance = (unsigned) Val.getZExtValue();
04335 
04336   // Bail out early if passed-in parameters make vectorization not feasible.
04337   unsigned ForcedFactor = VectorizationFactor ? VectorizationFactor : 1;
04338   unsigned ForcedUnroll = VectorizationUnroll ? VectorizationUnroll : 1;
04339 
04340   // The distance must be bigger than the size needed for a vectorized version
04341   // of the operation and the size of the vectorized operation must not be
04342   // bigger than the currrent maximum size.
04343   if (Distance < 2*TypeByteSize ||
04344       2*TypeByteSize > MaxSafeDepDistBytes ||
04345       Distance < TypeByteSize * ForcedUnroll * ForcedFactor) {
04346     DEBUG(dbgs() << "LV: Failure because of Positive distance "
04347         << Val.getSExtValue() << '\n');
04348     return true;
04349   }
04350 
04351   MaxSafeDepDistBytes = Distance < MaxSafeDepDistBytes ?
04352     Distance : MaxSafeDepDistBytes;
04353 
04354   bool IsTrueDataDependence = (!AIsWrite && BIsWrite);
04355   if (IsTrueDataDependence &&
04356       couldPreventStoreLoadForward(Distance, TypeByteSize))
04357      return true;
04358 
04359   DEBUG(dbgs() << "LV: Positive distance " << Val.getSExtValue() <<
04360         " with max VF = " << MaxSafeDepDistBytes / TypeByteSize << '\n');
04361 
04362   return false;
04363 }
04364 
04365 bool MemoryDepChecker::areDepsSafe(AccessAnalysis::DepCandidates &AccessSets,
04366                                    MemAccessInfoSet &CheckDeps,
04367                                    ValueToValueMap &Strides) {
04368 
04369   MaxSafeDepDistBytes = -1U;
04370   while (!CheckDeps.empty()) {
04371     MemAccessInfo CurAccess = *CheckDeps.begin();
04372 
04373     // Get the relevant memory access set.
04374     EquivalenceClasses<MemAccessInfo>::iterator I =
04375       AccessSets.findValue(AccessSets.getLeaderValue(CurAccess));
04376 
04377     // Check accesses within this set.
04378     EquivalenceClasses<MemAccessInfo>::member_iterator AI, AE;
04379     AI = AccessSets.member_begin(I), AE = AccessSets.member_end();
04380 
04381     // Check every access pair.
04382     while (AI != AE) {
04383       CheckDeps.erase(*AI);
04384       EquivalenceClasses<MemAccessInfo>::member_iterator OI = std::next(AI);
04385       while (OI != AE) {
04386         // Check every accessing instruction pair in program order.
04387         for (std::vector<unsigned>::iterator I1 = Accesses[*AI].begin(),
04388              I1E = Accesses[*AI].end(); I1 != I1E; ++I1)
04389           for (std::vector<unsigned>::iterator I2 = Accesses[*OI].begin(),
04390                I2E = Accesses[*OI].end(); I2 != I2E; ++I2) {
04391             if (*I1 < *I2 && isDependent(*AI, *I1, *OI, *I2, Strides))
04392               return false;
04393             if (*I2 < *I1 && isDependent(*OI, *I2, *AI, *I1, Strides))
04394               return false;
04395           }
04396         ++OI;
04397       }
04398       AI++;
04399     }
04400   }
04401   return true;
04402 }
04403 
04404 bool LoopVectorizationLegality::canVectorizeMemory() {
04405 
04406   typedef SmallVector<Value*, 16> ValueVector;
04407   typedef SmallPtrSet<Value*, 16> ValueSet;
04408 
04409   // Holds the Load and Store *instructions*.
04410   ValueVector Loads;
04411   ValueVector Stores;
04412 
04413   // Holds all the different accesses in the loop.
04414   unsigned NumReads = 0;
04415   unsigned NumReadWrites = 0;
04416 
04417   PtrRtCheck.Pointers.clear();
04418   PtrRtCheck.Need = false;
04419 
04420   const bool IsAnnotatedParallel = TheLoop->isAnnotatedParallel();
04421   MemoryDepChecker DepChecker(SE, DL, TheLoop);
04422 
04423   // For each block.
04424   for (Loop::block_iterator bb = TheLoop->block_begin(),
04425        be = TheLoop->block_end(); bb != be; ++bb) {
04426 
04427     // Scan the BB and collect legal loads and stores.
04428     for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
04429          ++it) {
04430 
04431       // If this is a load, save it. If this instruction can read from memory
04432       // but is not a load, then we quit. Notice that we don't handle function
04433       // calls that read or write.
04434       if (it->mayReadFromMemory()) {
04435         // Many math library functions read the rounding mode. We will only
04436         // vectorize a loop if it contains known function calls that don't set
04437         // the flag. Therefore, it is safe to ignore this read from memory.
04438         CallInst *Call = dyn_cast<CallInst>(it);
04439         if (Call && getIntrinsicIDForCall(Call, TLI))
04440           continue;
04441 
04442         LoadInst *Ld = dyn_cast<LoadInst>(it);
04443         if (!Ld) return false;
04444         if (!Ld->isSimple() && !IsAnnotatedParallel) {
04445           DEBUG(dbgs() << "LV: Found a non-simple load.\n");
04446           return false;
04447         }
04448         NumLoads++;
04449         Loads.push_back(Ld);
04450         DepChecker.addAccess(Ld);
04451         continue;
04452       }
04453 
04454       // Save 'store' instructions. Abort if other instructions write to memory.
04455       if (it->mayWriteToMemory()) {
04456         StoreInst *St = dyn_cast<StoreInst>(it);
04457         if (!St) return false;
04458         if (!St->isSimple() && !IsAnnotatedParallel) {
04459           DEBUG(dbgs() << "LV: Found a non-simple store.\n");
04460           return false;
04461         }
04462         NumStores++;
04463         Stores.push_back(St);
04464         DepChecker.addAccess(St);
04465       }
04466     } // Next instr.
04467   } // Next block.
04468 
04469   // Now we have two lists that hold the loads and the stores.
04470   // Next, we find the pointers that they use.
04471 
04472   // Check if we see any stores. If there are no stores, then we don't
04473   // care if the pointers are *restrict*.
04474   if (!Stores.size()) {
04475     DEBUG(dbgs() << "LV: Found a read-only loop!\n");
04476     return true;
04477   }
04478 
04479   AccessAnalysis::DepCandidates DependentAccesses;
04480   AccessAnalysis Accesses(DL, DependentAccesses);
04481 
04482   // Holds the analyzed pointers. We don't want to call GetUnderlyingObjects
04483   // multiple times on the same object. If the ptr is accessed twice, once
04484   // for read and once for write, it will only appear once (on the write
04485   // list). This is okay, since we are going to check for conflicts between
04486   // writes and between reads and writes, but not between reads and reads.
04487   ValueSet Seen;
04488 
04489   ValueVector::iterator I, IE;
04490   for (I = Stores.begin(), IE = Stores.end(); I != IE; ++I) {
04491     StoreInst *ST = cast<StoreInst>(*I);
04492     Value* Ptr = ST->getPointerOperand();
04493 
04494     if (isUniform(Ptr)) {
04495       DEBUG(dbgs() << "LV: We don't allow storing to uniform addresses\n");
04496       return false;
04497     }
04498 
04499     // If we did *not* see this pointer before, insert it to  the read-write
04500     // list. At this phase it is only a 'write' list.
04501     if (Seen.insert(Ptr)) {
04502       ++NumReadWrites;
04503       Accesses.addStore(Ptr);
04504     }
04505   }
04506 
04507   if (IsAnnotatedParallel) {
04508     DEBUG(dbgs()
04509           << "LV: A loop annotated parallel, ignore memory dependency "
04510           << "checks.\n");
04511     return true;
04512   }
04513 
04514   for (I = Loads.begin(), IE = Loads.end(); I != IE; ++I) {
04515     LoadInst *LD = cast<LoadInst>(*I);
04516     Value* Ptr = LD->getPointerOperand();
04517     // If we did *not* see this pointer before, insert it to the
04518     // read list. If we *did* see it before, then it is already in
04519     // the read-write list. This allows us to vectorize expressions
04520     // such as A[i] += x;  Because the address of A[i] is a read-write
04521     // pointer. This only works if the index of A[i] is consecutive.
04522     // If the address of i is unknown (for example A[B[i]]) then we may
04523     // read a few words, modify, and write a few words, and some of the
04524     // words may be written to the same address.
04525     bool IsReadOnlyPtr = false;
04526     if (Seen.insert(Ptr) || !isStridedPtr(SE, DL, Ptr, TheLoop, Strides)) {
04527       ++NumReads;
04528       IsReadOnlyPtr = true;
04529     }
04530     Accesses.addLoad(Ptr, IsReadOnlyPtr);
04531   }
04532 
04533   // If we write (or read-write) to a single destination and there are no
04534   // other reads in this loop then is it safe to vectorize.
04535   if (NumReadWrites == 1 && NumReads == 0) {
04536     DEBUG(dbgs() << "LV: Found a write-only loop!\n");
04537     return true;
04538   }
04539 
04540   // Build dependence sets and check whether we need a runtime pointer bounds
04541   // check.
04542   Accesses.buildDependenceSets();
04543   bool NeedRTCheck = Accesses.isRTCheckNeeded();
04544 
04545   // Find pointers with computable bounds. We are going to use this information
04546   // to place a runtime bound check.
04547   unsigned NumComparisons = 0;
04548   bool CanDoRT = false;
04549   if (NeedRTCheck)
04550     CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NumComparisons, SE, TheLoop,
04551                                        Strides);
04552 
04553   DEBUG(dbgs() << "LV: We need to do " << NumComparisons <<
04554         " pointer comparisons.\n");
04555 
04556   // If we only have one set of dependences to check pointers among we don't
04557   // need a runtime check.
04558   if (NumComparisons == 0 && NeedRTCheck)
04559     NeedRTCheck = false;
04560 
04561   // Check that we did not collect too many pointers or found an unsizeable
04562   // pointer.
04563   if (!CanDoRT || NumComparisons > RuntimeMemoryCheckThreshold) {
04564     PtrRtCheck.reset();
04565     CanDoRT = false;
04566   }
04567 
04568   if (CanDoRT) {
04569     DEBUG(dbgs() << "LV: We can perform a memory runtime check if needed.\n");
04570   }
04571 
04572   if (NeedRTCheck && !CanDoRT) {
04573     DEBUG(dbgs() << "LV: We can't vectorize because we can't find " <<
04574           "the array bounds.\n");
04575     PtrRtCheck.reset();
04576     return false;
04577   }
04578 
04579   PtrRtCheck.Need = NeedRTCheck;
04580 
04581   bool CanVecMem = true;
04582   if (Accesses.isDependencyCheckNeeded()) {
04583     DEBUG(dbgs() << "LV: Checking memory dependencies\n");
04584     CanVecMem = DepChecker.areDepsSafe(
04585         DependentAccesses, Accesses.getDependenciesToCheck(), Strides);
04586     MaxSafeDepDistBytes = DepChecker.getMaxSafeDepDistBytes();
04587 
04588     if (!CanVecMem && DepChecker.shouldRetryWithRuntimeCheck()) {
04589       DEBUG(dbgs() << "LV: Retrying with memory checks\n");
04590       NeedRTCheck = true;
04591 
04592       // Clear the dependency checks. We assume they are not needed.
04593       Accesses.resetDepChecks();
04594 
04595       PtrRtCheck.reset();
04596       PtrRtCheck.Need = true;
04597 
04598       CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NumComparisons, SE,
04599                                          TheLoop, Strides, true);
04600       // Check that we did not collect too many pointers or found an unsizeable
04601       // pointer.
04602       if (!CanDoRT || NumComparisons > RuntimeMemoryCheckThreshold) {
04603         DEBUG(dbgs() << "LV: Can't vectorize with memory checks\n");
04604         PtrRtCheck.reset();
04605         return false;
04606       }
04607 
04608       CanVecMem = true;
04609     }
04610   }
04611 
04612   DEBUG(dbgs() << "LV: We" << (NeedRTCheck ? "" : " don't") <<
04613         " need a runtime memory check.\n");
04614 
04615   return CanVecMem;
04616 }
04617 
04618 static bool hasMultipleUsesOf(Instruction *I,
04619                               SmallPtrSet<Instruction *, 8> &Insts) {
04620   unsigned NumUses = 0;
04621   for(User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use) {
04622     if (Insts.count(dyn_cast<Instruction>(*Use)))
04623       ++NumUses;
04624     if (NumUses > 1)
04625       return true;
04626   }
04627 
04628   return false;
04629 }
04630 
04631 static bool areAllUsesIn(Instruction *I, SmallPtrSet<Instruction *, 8> &Set) {
04632   for(User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use)
04633     if (!Set.count(dyn_cast<Instruction>(*Use)))
04634       return false;
04635   return true;
04636 }
04637 
04638 bool LoopVectorizationLegality::AddReductionVar(PHINode *Phi,
04639                                                 ReductionKind Kind) {
04640   if (Phi->getNumIncomingValues() != 2)
04641     return false;
04642 
04643   // Reduction variables are only found in the loop header block.
04644   if (Phi->getParent() != TheLoop->getHeader())
04645     return false;
04646 
04647   // Obtain the reduction start value from the value that comes from the loop
04648   // preheader.
04649   Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
04650 
04651   // ExitInstruction is the single value which is used outside the loop.
04652   // We only allow for a single reduction value to be used outside the loop.
04653   // This includes users of the reduction, variables (which form a cycle
04654   // which ends in the phi node).
04655   Instruction *ExitInstruction = 0;
04656   // Indicates that we found a reduction operation in our scan.
04657   bool FoundReduxOp = false;
04658 
04659   // We start with the PHI node and scan for all of the users of this
04660   // instruction. All users must be instructions that can be used as reduction
04661   // variables (such as ADD). We must have a single out-of-block user. The cycle
04662   // must include the original PHI.
04663   bool FoundStartPHI = false;
04664 
04665   // To recognize min/max patterns formed by a icmp select sequence, we store
04666   // the number of instruction we saw from the recognized min/max pattern,
04667   //  to make sure we only see exactly the two instructions.
04668   unsigned NumCmpSelectPatternInst = 0;
04669   ReductionInstDesc ReduxDesc(false, 0);
04670 
04671   SmallPtrSet<Instruction *, 8> VisitedInsts;
04672   SmallVector<Instruction *, 8> Worklist;
04673   Worklist.push_back(Phi);
04674   VisitedInsts.insert(Phi);
04675 
04676   // A value in the reduction can be used:
04677   //  - By the reduction:
04678   //      - Reduction operation:
04679   //        - One use of reduction value (safe).
04680   //        - Multiple use of reduction value (not safe).
04681   //      - PHI:
04682   //        - All uses of the PHI must be the reduction (safe).
04683   //        - Otherwise, not safe.
04684   //  - By one instruction outside of the loop (safe).
04685   //  - By further instructions outside of the loop (not safe).
04686   //  - By an instruction that is not part of the reduction (not safe).
04687   //    This is either:
04688   //      * An instruction type other than PHI or the reduction operation.
04689   //      * A PHI in the header other than the initial PHI.
04690   while (!Worklist.empty()) {
04691     Instruction *Cur = Worklist.back();
04692     Worklist.pop_back();
04693 
04694     // No Users.
04695     // If the instruction has no users then this is a broken chain and can't be
04696     // a reduction variable.
04697     if (Cur->use_empty())
04698       return false;
04699 
04700     bool IsAPhi = isa<PHINode>(Cur);
04701 
04702     // A header PHI use other than the original PHI.
04703     if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
04704       return false;
04705 
04706     // Reductions of instructions such as Div, and Sub is only possible if the
04707     // LHS is the reduction variable.
04708     if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
04709         !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
04710         !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
04711       return false;
04712 
04713     // Any reduction instruction must be of one of the allowed kinds.
04714     ReduxDesc = isReductionInstr(Cur, Kind, ReduxDesc);
04715     if (!ReduxDesc.IsReduction)
04716       return false;
04717 
04718     // A reduction operation must only have one use of the reduction value.
04719     if (!IsAPhi && Kind != RK_IntegerMinMax && Kind != RK_FloatMinMax &&
04720         hasMultipleUsesOf(Cur, VisitedInsts))
04721       return false;
04722 
04723     // All inputs to a PHI node must be a reduction value.
04724     if(IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
04725       return false;
04726 
04727     if (Kind == RK_IntegerMinMax && (isa<ICmpInst>(Cur) ||
04728                                      isa<SelectInst>(Cur)))
04729       ++NumCmpSelectPatternInst;
04730     if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) ||
04731                                    isa<SelectInst>(Cur)))
04732       ++NumCmpSelectPatternInst;
04733 
04734     // Check  whether we found a reduction operator.
04735     FoundReduxOp |= !IsAPhi;
04736 
04737     // Process users of current instruction. Push non-PHI nodes after PHI nodes
04738     // onto the stack. This way we are going to have seen all inputs to PHI
04739     // nodes once we get to them.
04740     SmallVector<Instruction *, 8> NonPHIs;
04741     SmallVector<Instruction *, 8> PHIs;
04742     for (User *U : Cur->users()) {
04743       Instruction *UI = cast<Instruction>(U);
04744 
04745       // Check if we found the exit user.
04746       BasicBlock *Parent = UI->getParent();
04747       if (!TheLoop->contains(Parent)) {
04748         // Exit if you find multiple outside users or if the header phi node is
04749         // being used. In this case the user uses the value of the previous
04750         // iteration, in which case we would loose "VF-1" iterations of the
04751         // reduction operation if we vectorize.
04752         if (ExitInstruction != 0 || Cur == Phi)
04753           return false;
04754 
04755         // The instruction used by an outside user must be the last instruction
04756         // before we feed back to the reduction phi. Otherwise, we loose VF-1
04757         // operations on the value.
04758         if (std::find(Phi->op_begin(), Phi->op_end(), Cur) == Phi->op_end())
04759          return false;
04760 
04761         ExitInstruction = Cur;
04762         continue;
04763       }
04764 
04765       // Process instructions only once (termination). Each reduction cycle
04766       // value must only be used once, except by phi nodes and min/max
04767       // reductions which are represented as a cmp followed by a select.
04768       ReductionInstDesc IgnoredVal(false, 0);
04769       if (VisitedInsts.insert(UI)) {
04770         if (isa<PHINode>(UI))
04771           PHIs.push_back(UI);
04772         else
04773           NonPHIs.push_back(UI);
04774       } else if (!isa<PHINode>(UI) &&
04775                  ((!isa<FCmpInst>(UI) &&
04776                    !isa<ICmpInst>(UI) &&
04777                    !isa<SelectInst>(UI)) ||
04778                   !isMinMaxSelectCmpPattern(UI, IgnoredVal).IsReduction))
04779         return false;
04780 
04781       // Remember that we completed the cycle.
04782       if (UI == Phi)
04783         FoundStartPHI = true;
04784     }
04785     Worklist.append(PHIs.begin(), PHIs.end());
04786     Worklist.append(NonPHIs.begin(), NonPHIs.end());
04787   }
04788 
04789   // This means we have seen one but not the other instruction of the
04790   // pattern or more than just a select and cmp.
04791   if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) &&
04792       NumCmpSelectPatternInst != 2)
04793     return false;
04794 
04795   if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
04796     return false;
04797 
04798   // We found a reduction var if we have reached the original phi node and we
04799   // only have a single instruction with out-of-loop users.
04800 
04801   // This instruction is allowed to have out-of-loop users.
04802   AllowedExit.insert(ExitInstruction);
04803 
04804   // Save the description of this reduction variable.
04805   ReductionDescriptor RD(RdxStart, ExitInstruction, Kind,
04806                          ReduxDesc.MinMaxKind);
04807   Reductions[Phi] = RD;
04808   // We've ended the cycle. This is a reduction variable if we have an
04809   // outside user and it has a binary op.
04810 
04811   return true;
04812 }
04813 
04814 /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
04815 /// pattern corresponding to a min(X, Y) or max(X, Y).
04816 LoopVectorizationLegality::ReductionInstDesc
04817 LoopVectorizationLegality::isMinMaxSelectCmpPattern(Instruction *I,
04818                                                     ReductionInstDesc &Prev) {
04819 
04820   assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
04821          "Expect a select instruction");
04822   Instruction *Cmp = 0;
04823   SelectInst *Select = 0;
04824 
04825   // We must handle the select(cmp()) as a single instruction. Advance to the
04826   // select.
04827   if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) {
04828     if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
04829       return ReductionInstDesc(false, I);
04830     return ReductionInstDesc(Select, Prev.MinMaxKind);
04831   }
04832 
04833   // Only handle single use cases for now.
04834   if (!(Select = dyn_cast<SelectInst>(I)))
04835     return ReductionInstDesc(false, I);
04836   if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
04837       !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
04838     return ReductionInstDesc(false, I);
04839   if (!Cmp->hasOneUse())
04840     return ReductionInstDesc(false, I);
04841 
04842   Value *CmpLeft;
04843   Value *CmpRight;
04844 
04845   // Look for a min/max pattern.
04846   if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
04847     return ReductionInstDesc(Select, MRK_UIntMin);
04848   else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
04849     return ReductionInstDesc(Select, MRK_UIntMax);
04850   else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
04851     return ReductionInstDesc(Select, MRK_SIntMax);
04852   else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
04853     return ReductionInstDesc(Select, MRK_SIntMin);
04854   else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
04855     return ReductionInstDesc(Select, MRK_FloatMin);
04856   else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
04857     return ReductionInstDesc(Select, MRK_FloatMax);
04858   else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
04859     return ReductionInstDesc(Select, MRK_FloatMin);
04860   else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
04861     return ReductionInstDesc(Select, MRK_FloatMax);
04862 
04863   return ReductionInstDesc(false, I);
04864 }
04865 
04866 LoopVectorizationLegality::ReductionInstDesc
04867 LoopVectorizationLegality::isReductionInstr(Instruction *I,
04868                                             ReductionKind Kind,
04869                                             ReductionInstDesc &Prev) {
04870   bool FP = I->getType()->isFloatingPointTy();
04871   bool FastMath = (FP && I->isCommutative() && I->isAssociative());
04872   switch (I->getOpcode()) {
04873   default:
04874     return ReductionInstDesc(false, I);
04875   case Instruction::PHI:
04876       if (FP && (Kind != RK_FloatMult && Kind != RK_FloatAdd &&
04877                  Kind != RK_FloatMinMax))
04878         return ReductionInstDesc(false, I);
04879     return ReductionInstDesc(I, Prev.MinMaxKind);
04880   case Instruction::Sub:
04881   case Instruction::Add:
04882     return ReductionInstDesc(Kind == RK_IntegerAdd, I);
04883   case Instruction::Mul:
04884     return ReductionInstDesc(Kind == RK_IntegerMult, I);
04885   case Instruction::And:
04886     return ReductionInstDesc(Kind == RK_IntegerAnd, I);
04887   case Instruction::Or:
04888     return ReductionInstDesc(Kind == RK_IntegerOr, I);
04889   case Instruction::Xor:
04890     return ReductionInstDesc(Kind == RK_IntegerXor, I);
04891   case Instruction::FMul:
04892     return ReductionInstDesc(Kind == RK_FloatMult && FastMath, I);
04893   case Instruction::FAdd:
04894     return ReductionInstDesc(Kind == RK_FloatAdd && FastMath, I);
04895   case Instruction::FCmp:
04896   case Instruction::ICmp:
04897   case Instruction::Select:
04898     if (Kind != RK_IntegerMinMax &&
04899         (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
04900       return ReductionInstDesc(false, I);
04901     return isMinMaxSelectCmpPattern(I, Prev);
04902   }
04903 }
04904 
04905 LoopVectorizationLegality::InductionKind
04906 LoopVectorizationLegality::isInductionVariable(PHINode *Phi) {
04907   Type *PhiTy = Phi->getType();
04908   // We only handle integer and pointer inductions variables.
04909   if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
04910     return IK_NoInduction;
04911 
04912   // Check that the PHI is consecutive.
04913   const SCEV *PhiScev = SE->getSCEV(Phi);
04914   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
04915   if (!AR) {
04916     DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
04917     return IK_NoInduction;
04918   }
04919   const SCEV *Step = AR->getStepRecurrence(*SE);
04920 
04921   // Integer inductions need to have a stride of one.
04922   if (PhiTy->isIntegerTy()) {
04923     if (Step->isOne())
04924       return IK_IntInduction;
04925     if (Step->isAllOnesValue())
04926       return IK_ReverseIntInduction;
04927     return IK_NoInduction;
04928   }
04929 
04930   // Calculate the pointer stride and check if it is consecutive.
04931   const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
04932   if (!C)
04933     return IK_NoInduction;
04934 
04935   assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
04936   uint64_t Size = DL->getTypeAllocSize(PhiTy->getPointerElementType());
04937   if (C->getValue()->equalsInt(Size))
04938     return IK_PtrInduction;
04939   else if (C->getValue()->equalsInt(0 - Size))
04940     return IK_ReversePtrInduction;
04941 
04942   return IK_NoInduction;
04943 }
04944 
04945 bool LoopVectorizationLegality::isInductionVariable(const Value *V) {
04946   Value *In0 = const_cast<Value*>(V);
04947   PHINode *PN = dyn_cast_or_null<PHINode>(In0);
04948   if (!PN)
04949     return false;
04950 
04951   return Inductions.count(PN);
04952 }
04953 
04954 bool LoopVectorizationLegality::blockNeedsPredication(BasicBlock *BB)  {
04955   assert(TheLoop->contains(BB) && "Unknown block used");
04956 
04957   // Blocks that do not dominate the latch need predication.
04958   BasicBlock* Latch = TheLoop->getLoopLatch();
04959   return !DT->dominates(BB, Latch);
04960 }
04961 
04962 bool LoopVectorizationLegality::blockCanBePredicated(BasicBlock *BB,
04963                                             SmallPtrSet<Value *, 8>& SafePtrs) {
04964   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
04965     // We might be able to hoist the load.
04966     if (it->mayReadFromMemory()) {
04967       LoadInst *LI = dyn_cast<LoadInst>(it);
04968       if (!LI || !SafePtrs.count(LI->getPointerOperand()))
04969         return false;
04970     }
04971 
04972     // We don't predicate stores at the moment.
04973     if (it->mayWriteToMemory()) {
04974       StoreInst *SI = dyn_cast<StoreInst>(it);
04975       // We only support predication of stores in basic blocks with one
04976       // predecessor.
04977       if (!SI || ++NumPredStores > NumberOfStoresToPredicate ||
04978           !SafePtrs.count(SI->getPointerOperand()) ||
04979           !SI->getParent()->getSinglePredecessor())
04980         return false;
04981     }
04982     if (it->mayThrow())
04983       return false;
04984 
04985     // Check that we don't have a constant expression that can trap as operand.
04986     for (Instruction::op_iterator OI = it->op_begin(), OE = it->op_end();
04987          OI != OE; ++OI) {
04988       if (Constant *C = dyn_cast<Constant>(*OI))
04989         if (C->canTrap())
04990           return false;
04991     }
04992 
04993     // The instructions below can trap.
04994     switch (it->getOpcode()) {
04995     default: continue;
04996     case Instruction::UDiv:
04997     case Instruction::SDiv:
04998     case Instruction::URem:
04999     case Instruction::SRem:
05000              return false;
05001     }
05002   }
05003 
05004   return true;
05005 }
05006 
05007 LoopVectorizationCostModel::VectorizationFactor
05008 LoopVectorizationCostModel::selectVectorizationFactor(bool OptForSize,
05009                                                       unsigned UserVF) {
05010   // Width 1 means no vectorize
05011   VectorizationFactor Factor = { 1U, 0U };
05012   if (OptForSize && Legal->getRuntimePointerCheck()->Need) {
05013     DEBUG(dbgs() << "LV: Aborting. Runtime ptr check is required in Os.\n");
05014     return Factor;
05015   }
05016 
05017   if (!EnableCondStoresVectorization && Legal->NumPredStores) {
05018     DEBUG(dbgs() << "LV: No vectorization. There are conditional stores.\n");
05019     return Factor;
05020   }
05021 
05022   // Find the trip count.
05023   unsigned TC = SE->getSmallConstantTripCount(TheLoop, TheLoop->getLoopLatch());
05024   DEBUG(dbgs() << "LV: Found trip count: " << TC << '\n');
05025 
05026   unsigned WidestType = getWidestType();
05027   unsigned WidestRegister = TTI.getRegisterBitWidth(true);
05028   unsigned MaxSafeDepDist = -1U;
05029   if (Legal->getMaxSafeDepDistBytes() != -1U)
05030     MaxSafeDepDist = Legal->getMaxSafeDepDistBytes() * 8;
05031   WidestRegister = ((WidestRegister < MaxSafeDepDist) ?
05032                     WidestRegister : MaxSafeDepDist);
05033   unsigned MaxVectorSize = WidestRegister / WidestType;
05034   DEBUG(dbgs() << "LV: The Widest type: " << WidestType << " bits.\n");
05035   DEBUG(dbgs() << "LV: The Widest register is: "
05036           << WidestRegister << " bits.\n");
05037 
05038   if (MaxVectorSize == 0) {
05039     DEBUG(dbgs() << "LV: The target has no vector registers.\n");
05040     MaxVectorSize = 1;
05041   }
05042 
05043   assert(MaxVectorSize <= 32 && "Did not expect to pack so many elements"
05044          " into one vector!");
05045 
05046   unsigned VF = MaxVectorSize;
05047 
05048   // If we optimize the program for size, avoid creating the tail loop.
05049   if (OptForSize) {
05050     // If we are unable to calculate the trip count then don't try to vectorize.
05051     if (TC < 2) {
05052       DEBUG(dbgs() << "LV: Aborting. A tail loop is required in Os.\n");
05053       return Factor;
05054     }
05055 
05056     // Find the maximum SIMD width that can fit within the trip count.
05057     VF = TC % MaxVectorSize;
05058 
05059     if (VF == 0)
05060       VF = MaxVectorSize;
05061 
05062     // If the trip count that we found modulo the vectorization factor is not
05063     // zero then we require a tail.
05064     if (VF < 2) {
05065       DEBUG(dbgs() << "LV: Aborting. A tail loop is required in Os.\n");
05066       return Factor;
05067     }
05068   }
05069 
05070   if (UserVF != 0) {
05071     assert(isPowerOf2_32(UserVF) && "VF needs to be a power of two");
05072     DEBUG(dbgs() << "LV: Using user VF " << UserVF << ".\n");
05073 
05074     Factor.Width = UserVF;
05075     return Factor;
05076   }
05077 
05078   float Cost = expectedCost(1);
05079   unsigned Width = 1;
05080   DEBUG(dbgs() << "LV: Scalar loop costs: " << (int)Cost << ".\n");
05081   for (unsigned i=2; i <= VF; i*=2) {
05082     // Notice that the vector loop needs to be executed less times, so
05083     // we need to divide the cost of the vector loops by the width of
05084     // the vector elements.
05085     float VectorCost = expectedCost(i) / (float)i;
05086     DEBUG(dbgs() << "LV: Vector loop of width " << i << " costs: " <<
05087           (int)VectorCost << ".\n");
05088     if (VectorCost < Cost) {
05089       Cost = VectorCost;
05090       Width = i;
05091     }
05092   }
05093 
05094   DEBUG(dbgs() << "LV: Selecting VF: "<< Width << ".\n");
05095   Factor.Width = Width;
05096   Factor.Cost = Width * Cost;
05097   return Factor;
05098 }
05099 
05100 unsigned LoopVectorizationCostModel::getWidestType() {
05101   unsigned MaxWidth = 8;
05102 
05103   // For each block.
05104   for (Loop::block_iterator bb = TheLoop->block_begin(),
05105        be = TheLoop->block_end(); bb != be; ++bb) {
05106     BasicBlock *BB = *bb;
05107 
05108     // For each instruction in the loop.
05109     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
05110       Type *T = it->getType();
05111 
05112       // Only examine Loads, Stores and PHINodes.
05113       if (!isa<LoadInst>(it) && !isa<StoreInst>(it) && !isa<PHINode>(it))
05114         continue;
05115 
05116       // Examine PHI nodes that are reduction variables.
05117       if (PHINode *PN = dyn_cast<PHINode>(it))
05118         if (!Legal->getReductionVars()->count(PN))
05119           continue;
05120 
05121       // Examine the stored values.
05122       if (StoreInst *ST = dyn_cast<StoreInst>(it))
05123         T = ST->getValueOperand()->getType();
05124 
05125       // Ignore loaded pointer types and stored pointer types that are not
05126       // consecutive. However, we do want to take consecutive stores/loads of
05127       // pointer vectors into account.
05128       if (T->isPointerTy() && !isConsecutiveLoadOrStore(it))
05129         continue;
05130 
05131       MaxWidth = std::max(MaxWidth,
05132                           (unsigned)DL->getTypeSizeInBits(T->getScalarType()));
05133     }
05134   }
05135 
05136   return MaxWidth;
05137 }
05138 
05139 unsigned
05140 LoopVectorizationCostModel::selectUnrollFactor(bool OptForSize,
05141                                                unsigned UserUF,
05142                                                unsigned VF,
05143                                                unsigned LoopCost) {
05144 
05145   // -- The unroll heuristics --
05146   // We unroll the loop in order to expose ILP and reduce the loop overhead.
05147   // There are many micro-architectural considerations that we can't predict
05148   // at this level. For example frontend pressure (on decode or fetch) due to
05149   // code size, or the number and capabilities of the execution ports.
05150   //
05151   // We use the following heuristics to select the unroll factor:
05152   // 1. If the code has reductions the we unroll in order to break the cross
05153   // iteration dependency.
05154   // 2. If the loop is really small then we unroll in order to reduce the loop
05155   // overhead.
05156   // 3. We don't unroll if we think that we will spill registers to memory due
05157   // to the increased register pressure.
05158 
05159   // Use the user preference, unless 'auto' is selected.
05160   if (UserUF != 0)
05161     return UserUF;
05162 
05163   // When we optimize for size we don't unroll.
05164   if (OptForSize)
05165     return 1;
05166 
05167   // We used the distance for the unroll factor.
05168   if (Legal->getMaxSafeDepDistBytes() != -1U)
05169     return 1;
05170 
05171   // Do not unroll loops with a relatively small trip count.
05172   unsigned TC = SE->getSmallConstantTripCount(TheLoop,
05173                                               TheLoop->getLoopLatch());
05174   if (TC > 1 && TC < TinyTripCountUnrollThreshold)
05175     return 1;
05176 
05177   unsigned TargetNumRegisters = TTI.getNumberOfRegisters(VF > 1);
05178   DEBUG(dbgs() << "LV: The target has " << TargetNumRegisters <<
05179         " registers\n");
05180 
05181   if (VF == 1) {
05182     if (ForceTargetNumScalarRegs.getNumOccurrences() > 0)
05183       TargetNumRegisters = ForceTargetNumScalarRegs;
05184   } else {
05185     if (ForceTargetNumVectorRegs.getNumOccurrences() > 0)
05186       TargetNumRegisters = ForceTargetNumVectorRegs;
05187   }
05188 
05189   LoopVectorizationCostModel::RegisterUsage R = calculateRegisterUsage();
05190   // We divide by these constants so assume that we have at least one
05191   // instruction that uses at least one register.
05192   R.MaxLocalUsers = std::max(R.MaxLocalUsers, 1U);
05193   R.NumInstructions = std::max(R.NumInstructions, 1U);
05194 
05195   // We calculate the unroll factor using the following formula.
05196   // Subtract the number of loop invariants from the number of available
05197   // registers. These registers are used by all of the unrolled instances.
05198   // Next, divide the remaining registers by the number of registers that is
05199   // required by the loop, in order to estimate how many parallel instances
05200   // fit without causing spills. All of this is rounded down if necessary to be
05201   // a power of two. We want power of two unroll factors to simplify any
05202   // addressing operations or alignment considerations.
05203   unsigned UF = PowerOf2Floor((TargetNumRegisters - R.LoopInvariantRegs) /
05204                               R.MaxLocalUsers);
05205 
05206   // Don't count the induction variable as unrolled.
05207   if (EnableIndVarRegisterHeur)
05208     UF = PowerOf2Floor((TargetNumRegisters - R.LoopInvariantRegs - 1) /
05209                        std::max(1U, (R.MaxLocalUsers - 1)));
05210 
05211   // Clamp the unroll factor ranges to reasonable factors.
05212   unsigned MaxUnrollSize = TTI.getMaximumUnrollFactor();
05213 
05214   // Check if the user has overridden the unroll max.
05215   if (VF == 1) {
05216     if (ForceTargetMaxScalarUnrollFactor.getNumOccurrences() > 0)
05217       MaxUnrollSize = ForceTargetMaxScalarUnrollFactor;
05218   } else {
05219     if (ForceTargetMaxVectorUnrollFactor.getNumOccurrences() > 0)
05220       MaxUnrollSize = ForceTargetMaxVectorUnrollFactor;
05221   }
05222 
05223   // If we did not calculate the cost for VF (because the user selected the VF)
05224   // then we calculate the cost of VF here.
05225   if (LoopCost == 0)
05226     LoopCost = expectedCost(VF);
05227 
05228   // Clamp the calculated UF to be between the 1 and the max unroll factor
05229   // that the target allows.
05230   if (UF > MaxUnrollSize)
05231     UF = MaxUnrollSize;
05232   else if (UF < 1)
05233     UF = 1;
05234 
05235   // Unroll if we vectorized this loop and there is a reduction that could
05236   // benefit from unrolling.
05237   if (VF > 1 && Legal->getReductionVars()->size()) {
05238     DEBUG(dbgs() << "LV: Unrolling because of reductions.\n");
05239     return UF;
05240   }
05241 
05242   // Note that if we've already vectorized the loop we will have done the
05243   // runtime check and so unrolling won't require further checks.
05244   bool UnrollingRequiresRuntimePointerCheck =
05245       (VF == 1 && Legal->getRuntimePointerCheck()->Need);
05246 
05247   // We want to unroll small loops in order to reduce the loop overhead and
05248   // potentially expose ILP opportunities.
05249   DEBUG(dbgs() << "LV: Loop cost is " << LoopCost << '\n');
05250   if (!UnrollingRequiresRuntimePointerCheck &&
05251       LoopCost < SmallLoopCost) {
05252     // We assume that the cost overhead is 1 and we use the cost model
05253     // to estimate the cost of the loop and unroll until the cost of the
05254     // loop overhead is about 5% of the cost of the loop.
05255     unsigned SmallUF = std::min(UF, (unsigned)PowerOf2Floor(SmallLoopCost / LoopCost));
05256 
05257     // Unroll until store/load ports (estimated by max unroll factor) are
05258     // saturated.
05259     unsigned StoresUF = UF / (Legal->NumStores ? Legal->NumStores : 1);
05260     unsigned LoadsUF = UF /  (Legal->NumLoads ? Legal->NumLoads : 1);
05261 
05262     if (EnableLoadStoreRuntimeUnroll && std::max(StoresUF, LoadsUF) > SmallUF) {
05263       DEBUG(dbgs() << "LV: Unrolling to saturate store or load ports.\n");
05264       return std::max(StoresUF, LoadsUF);
05265     }
05266 
05267     DEBUG(dbgs() << "LV: Unrolling to reduce branch cost.\n");
05268     return SmallUF;
05269   }
05270 
05271   DEBUG(dbgs() << "LV: Not Unrolling.\n");
05272   return 1;
05273 }
05274 
05275 LoopVectorizationCostModel::RegisterUsage
05276 LoopVectorizationCostModel::calculateRegisterUsage() {
05277   // This function calculates the register usage by measuring the highest number
05278   // of values that are alive at a single location. Obviously, this is a very
05279   // rough estimation. We scan the loop in a topological order in order and
05280   // assign a number to each instruction. We use RPO to ensure that defs are
05281   // met before their users. We assume that each instruction that has in-loop
05282   // users starts an interval. We record every time that an in-loop value is
05283   // used, so we have a list of the first and last occurrences of each
05284   // instruction. Next, we transpose this data structure into a multi map that
05285   // holds the list of intervals that *end* at a specific location. This multi
05286   // map allows us to perform a linear search. We scan the instructions linearly
05287   // and record each time that a new interval starts, by placing it in a set.
05288   // If we find this value in the multi-map then we remove it from the set.
05289   // The max register usage is the maximum size of the set.
05290   // We also search for instructions that are defined outside the loop, but are
05291   // used inside the loop. We need this number separately from the max-interval
05292   // usage number because when we unroll, loop-invariant values do not take
05293   // more register.
05294   LoopBlocksDFS DFS(TheLoop);
05295   DFS.perform(LI);
05296 
05297   RegisterUsage R;
05298   R.NumInstructions = 0;
05299 
05300   // Each 'key' in the map opens a new interval. The values
05301   // of the map are the index of the 'last seen' usage of the
05302   // instruction that is the key.
05303   typedef DenseMap<Instruction*, unsigned> IntervalMap;
05304   // Maps instruction to its index.
05305   DenseMap<unsigned, Instruction*> IdxToInstr;
05306   // Marks the end of each interval.
05307   IntervalMap EndPoint;
05308   // Saves the list of instruction indices that are used in the loop.
05309   SmallSet<Instruction*, 8> Ends;
05310   // Saves the list of values that are used in the loop but are
05311   // defined outside the loop, such as arguments and constants.
05312   SmallPtrSet<Value*, 8> LoopInvariants;
05313 
05314   unsigned Index = 0;
05315   for (LoopBlocksDFS::RPOIterator bb = DFS.beginRPO(),
05316        be = DFS.endRPO(); bb != be; ++bb) {
05317     R.NumInstructions += (*bb)->size();
05318     for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
05319          ++it) {
05320       Instruction *I = it;
05321       IdxToInstr[Index++] = I;
05322 
05323       // Save the end location of each USE.
05324       for (unsigned i = 0; i < I->getNumOperands(); ++i) {
05325         Value *U = I->getOperand(i);
05326         Instruction *Instr = dyn_cast<Instruction>(U);
05327 
05328         // Ignore non-instruction values such as arguments, constants, etc.
05329         if (!Instr) continue;
05330 
05331         // If this instruction is outside the loop then record it and continue.
05332         if (!TheLoop->contains(Instr)) {
05333           LoopInvariants.insert(Instr);
05334           continue;
05335         }
05336 
05337         // Overwrite previous end points.
05338         EndPoint[Instr] = Index;
05339         Ends.insert(Instr);
05340       }
05341     }
05342   }
05343 
05344   // Saves the list of intervals that end with the index in 'key'.
05345   typedef SmallVector<Instruction*, 2> InstrList;
05346   DenseMap<unsigned, InstrList> TransposeEnds;
05347 
05348   // Transpose the EndPoints to a list of values that end at each index.
05349   for (IntervalMap::iterator it = EndPoint.begin(), e = EndPoint.end();
05350        it != e; ++it)
05351     TransposeEnds[it->second].push_back(it->first);
05352 
05353   SmallSet<Instruction*, 8> OpenIntervals;
05354   unsigned MaxUsage = 0;
05355 
05356 
05357   DEBUG(dbgs() << "LV(REG): Calculating max register usage:\n");
05358   for (unsigned int i = 0; i < Index; ++i) {
05359     Instruction *I = IdxToInstr[i];
05360     // Ignore instructions that are never used within the loop.
05361     if (!Ends.count(I)) continue;
05362 
05363     // Remove all of the instructions that end at this location.
05364     InstrList &List = TransposeEnds[i];
05365     for (unsigned int j=0, e = List.size(); j < e; ++j)
05366       OpenIntervals.erase(List[j]);
05367 
05368     // Count the number of live interals.
05369     MaxUsage = std::max(MaxUsage, OpenIntervals.size());
05370 
05371     DEBUG(dbgs() << "LV(REG): At #" << i << " Interval # " <<
05372           OpenIntervals.size() << '\n');
05373 
05374     // Add the current instruction to the list of open intervals.
05375     OpenIntervals.insert(I);
05376   }
05377 
05378   unsigned Invariant = LoopInvariants.size();
05379   DEBUG(dbgs() << "LV(REG): Found max usage: " << MaxUsage << '\n');
05380   DEBUG(dbgs() << "LV(REG): Found invariant usage: " << Invariant << '\n');
05381   DEBUG(dbgs() << "LV(REG): LoopSize: " << R.NumInstructions << '\n');
05382 
05383   R.LoopInvariantRegs = Invariant;
05384   R.MaxLocalUsers = MaxUsage;
05385   return R;
05386 }
05387 
05388 unsigned LoopVectorizationCostModel::expectedCost(unsigned VF) {
05389   unsigned Cost = 0;
05390 
05391   // For each block.
05392   for (Loop::block_iterator bb = TheLoop->block_begin(),
05393        be = TheLoop->block_end(); bb != be; ++bb) {
05394     unsigned BlockCost = 0;
05395     BasicBlock *BB = *bb;
05396 
05397     // For each instruction in the old loop.
05398     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
05399       // Skip dbg intrinsics.
05400       if (isa<DbgInfoIntrinsic>(it))
05401         continue;
05402 
05403       unsigned C = getInstructionCost(it, VF);
05404 
05405       // Check if we should override the cost.
05406       if (ForceTargetInstructionCost.getNumOccurrences() > 0)
05407         C = ForceTargetInstructionCost;
05408 
05409       BlockCost += C;
05410       DEBUG(dbgs() << "LV: Found an estimated cost of " << C << " for VF " <<
05411             VF << " For instruction: " << *it << '\n');
05412     }
05413 
05414     // We assume that if-converted blocks have a 50% chance of being executed.
05415     // When the code is scalar then some of the blocks are avoided due to CF.
05416     // When the code is vectorized we execute all code paths.
05417     if (VF == 1 && Legal->blockNeedsPredication(*bb))
05418       BlockCost /= 2;
05419 
05420     Cost += BlockCost;
05421   }
05422 
05423   return Cost;
05424 }
05425 
05426 /// \brief Check whether the address computation for a non-consecutive memory
05427 /// access looks like an unlikely candidate for being merged into the indexing
05428 /// mode.
05429 ///
05430 /// We look for a GEP which has one index that is an induction variable and all
05431 /// other indices are loop invariant. If the stride of this access is also
05432 /// within a small bound we decide that this address computation can likely be
05433 /// merged into the addressing mode.
05434 /// In all other cases, we identify the address computation as complex.
05435 static bool isLikelyComplexAddressComputation(Value *Ptr,
05436                                               LoopVectorizationLegality *Legal,
05437                                               ScalarEvolution *SE,
05438                                               const Loop *TheLoop) {
05439   GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr);
05440   if (!Gep)
05441     return true;
05442 
05443   // We are looking for a gep with all loop invariant indices except for one
05444   // which should be an induction variable.
05445   unsigned NumOperands = Gep->getNumOperands();
05446   for (unsigned i = 1; i < NumOperands; ++i) {
05447     Value *Opd = Gep->getOperand(i);
05448     if (!SE->isLoopInvariant(SE->getSCEV(Opd), TheLoop) &&
05449         !Legal->isInductionVariable(Opd))
05450       return true;
05451   }
05452 
05453   // Now we know we have a GEP ptr, %inv, %ind, %inv. Make sure that the step
05454   // can likely be merged into the address computation.
05455   unsigned MaxMergeDistance = 64;
05456 
05457   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Ptr));
05458   if (!AddRec)
05459     return true;
05460 
05461   // Check the step is constant.
05462   const SCEV *Step = AddRec->getStepRecurrence(*SE);
05463   // Calculate the pointer stride and check if it is consecutive.
05464   const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
05465   if (!C)
05466     return true;
05467 
05468   const APInt &APStepVal = C->getValue()->getValue();
05469 
05470   // Huge step value - give up.
05471   if (APStepVal.getBitWidth() > 64)
05472     return true;
05473 
05474   int64_t StepVal = APStepVal.getSExtValue();
05475 
05476   return StepVal > MaxMergeDistance;
05477 }
05478 
05479 static bool isStrideMul(Instruction *I, LoopVectorizationLegality *Legal) {
05480   if (Legal->hasStride(I->getOperand(0)) || Legal->hasStride(I->getOperand(1)))
05481     return true;
05482   return false;
05483 }
05484 
05485 unsigned
05486 LoopVectorizationCostModel::getInstructionCost(Instruction *I, unsigned VF) {
05487   // If we know that this instruction will remain uniform, check the cost of
05488   // the scalar version.
05489   if (Legal->isUniformAfterVectorization(I))
05490     VF = 1;
05491 
05492   Type *RetTy = I->getType();
05493   Type *VectorTy = ToVectorTy(RetTy, VF);
05494 
05495   // TODO: We need to estimate the cost of intrinsic calls.
05496   switch (I->getOpcode()) {
05497   case Instruction::GetElementPtr:
05498     // We mark this instruction as zero-cost because the cost of GEPs in
05499     // vectorized code depends on whether the corresponding memory instruction
05500     // is scalarized or not. Therefore, we handle GEPs with the memory
05501     // instruction cost.
05502     return 0;
05503   case Instruction::Br: {
05504     return TTI.getCFInstrCost(I->getOpcode());
05505   }
05506   case Instruction::PHI:
05507     //TODO: IF-converted IFs become selects.
05508     return 0;
05509   case Instruction::Add:
05510   case Instruction::FAdd:
05511   case Instruction::Sub:
05512   case Instruction::FSub:
05513   case Instruction::Mul:
05514   case Instruction::FMul:
05515   case Instruction::UDiv:
05516   case Instruction::SDiv:
05517   case Instruction::FDiv:
05518   case Instruction::URem:
05519   case Instruction::SRem:
05520   case Instruction::FRem:
05521   case Instruction::Shl:
05522   case Instruction::LShr:
05523   case Instruction::AShr:
05524   case Instruction::And:
05525   case Instruction::Or:
05526   case Instruction::Xor: {
05527     // Since we will replace the stride by 1 the multiplication should go away.
05528     if (I->getOpcode() == Instruction::Mul && isStrideMul(I, Legal))
05529       return 0;
05530     // Certain instructions can be cheaper to vectorize if they have a constant
05531     // second vector operand. One example of this are shifts on x86.
05532     TargetTransformInfo::OperandValueKind Op1VK =
05533       TargetTransformInfo::OK_AnyValue;
05534     TargetTransformInfo::OperandValueKind Op2VK =
05535       TargetTransformInfo::OK_AnyValue;
05536     Value *Op2 = I->getOperand(1);
05537 
05538     // Check for a splat of a constant or for a non uniform vector of constants.
05539     if (isa<ConstantInt>(Op2))
05540       Op2VK = TargetTransformInfo::OK_UniformConstantValue;
05541     else if (isa<ConstantVector>(Op2) || isa<ConstantDataVector>(Op2)) {
05542       Op2VK = TargetTransformInfo::OK_NonUniformConstantValue;
05543       if (cast<Constant>(Op2)->getSplatValue() != NULL)
05544         Op2VK = TargetTransformInfo::OK_UniformConstantValue;
05545     }
05546 
05547     return TTI.getArithmeticInstrCost(I->getOpcode(), VectorTy, Op1VK, Op2VK);
05548   }
05549   case Instruction::Select: {
05550     SelectInst *SI = cast<SelectInst>(I);
05551     const SCEV *CondSCEV = SE->getSCEV(SI->getCondition());
05552     bool ScalarCond = (SE->isLoopInvariant(CondSCEV, TheLoop));
05553     Type *CondTy = SI->getCondition()->getType();
05554     if (!ScalarCond)
05555       CondTy = VectorType::get(CondTy, VF);
05556 
05557     return TTI.getCmpSelInstrCost(I->getOpcode(), VectorTy, CondTy);
05558   }
05559   case Instruction::ICmp:
05560   case Instruction::FCmp: {
05561     Type *ValTy = I->getOperand(0)->getType();
05562     VectorTy = ToVectorTy(ValTy, VF);
05563     return TTI.getCmpSelInstrCost(I->getOpcode(), VectorTy);
05564   }
05565   case Instruction::Store:
05566   case Instruction::Load: {
05567     StoreInst *SI = dyn_cast<StoreInst>(I);
05568     LoadInst *LI = dyn_cast<LoadInst>(I);
05569     Type *ValTy = (SI ? SI->getValueOperand()->getType() :
05570                    LI->getType());
05571     VectorTy = ToVectorTy(ValTy, VF);
05572 
05573     unsigned Alignment = SI ? SI->getAlignment() : LI->getAlignment();
05574     unsigned AS = SI ? SI->getPointerAddressSpace() :
05575       LI->getPointerAddressSpace();
05576     Value *Ptr = SI ? SI->getPointerOperand() : LI->getPointerOperand();
05577     // We add the cost of address computation here instead of with the gep
05578     // instruction because only here we know whether the operation is
05579     // scalarized.
05580     if (VF == 1)
05581       return TTI.getAddressComputationCost(VectorTy) +
05582         TTI.getMemoryOpCost(I->getOpcode(), VectorTy, Alignment, AS);
05583 
05584     // Scalarized loads/stores.
05585     int ConsecutiveStride = Legal->isConsecutivePtr(Ptr);
05586     bool Reverse = ConsecutiveStride < 0;
05587     unsigned ScalarAllocatedSize = DL->getTypeAllocSize(ValTy);
05588     unsigned VectorElementSize = DL->getTypeStoreSize(VectorTy)/VF;
05589     if (!ConsecutiveStride || ScalarAllocatedSize != VectorElementSize) {
05590       bool IsComplexComputation =
05591         isLikelyComplexAddressComputation(Ptr, Legal, SE, TheLoop);
05592       unsigned Cost = 0;
05593       // The cost of extracting from the value vector and pointer vector.
05594       Type *PtrTy = ToVectorTy(Ptr->getType(), VF);
05595       for (unsigned i = 0; i < VF; ++i) {
05596         //  The cost of extracting the pointer operand.
05597         Cost += TTI.getVectorInstrCost(Instruction::ExtractElement, PtrTy, i);
05598         // In case of STORE, the cost of ExtractElement from the vector.
05599         // In case of LOAD, the cost of InsertElement into the returned
05600         // vector.
05601         Cost += TTI.getVectorInstrCost(SI ? Instruction::ExtractElement :
05602                                             Instruction::InsertElement,
05603                                             VectorTy, i);
05604       }
05605 
05606       // The cost of the scalar loads/stores.
05607       Cost += VF * TTI.getAddressComputationCost(PtrTy, IsComplexComputation);
05608       Cost += VF * TTI.getMemoryOpCost(I->getOpcode(), ValTy->getScalarType(),
05609                                        Alignment, AS);
05610       return Cost;
05611     }
05612 
05613     // Wide load/stores.
05614     unsigned Cost = TTI.getAddressComputationCost(VectorTy);
05615     Cost += TTI.getMemoryOpCost(I->getOpcode(), VectorTy, Alignment, AS);
05616 
05617     if (Reverse)
05618       Cost += TTI.getShuffleCost(TargetTransformInfo::SK_Reverse,
05619                                   VectorTy, 0);
05620     return Cost;
05621   }
05622   case Instruction::ZExt:
05623   case Instruction::SExt:
05624   case Instruction::FPToUI:
05625   case Instruction::FPToSI:
05626   case Instruction::FPExt:
05627   case Instruction::PtrToInt:
05628   case Instruction::IntToPtr:
05629   case Instruction::SIToFP:
05630   case Instruction::UIToFP:
05631   case Instruction::Trunc:
05632   case Instruction::FPTrunc:
05633   case Instruction::BitCast: {
05634     // We optimize the truncation of induction variable.
05635     // The cost of these is the same as the scalar operation.
05636     if (I->getOpcode() == Instruction::Trunc &&
05637         Legal->isInductionVariable(I->getOperand(0)))
05638       return TTI.getCastInstrCost(I->getOpcode(), I->getType(),
05639                                   I->getOperand(0)->getType());
05640 
05641     Type *SrcVecTy = ToVectorTy(I->getOperand(0)->getType(), VF);
05642     return TTI.getCastInstrCost(I->getOpcode(), VectorTy, SrcVecTy);
05643   }
05644   case Instruction::Call: {
05645     CallInst *CI = cast<CallInst>(I);
05646     Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
05647     assert(ID && "Not an intrinsic call!");
05648     Type *RetTy = ToVectorTy(CI->getType(), VF);
05649     SmallVector<Type*, 4> Tys;
05650     for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i)
05651       Tys.push_back(ToVectorTy(CI->getArgOperand(i)->getType(), VF));
05652     return TTI.getIntrinsicInstrCost(ID, RetTy, Tys);
05653   }
05654   default: {
05655     // We are scalarizing the instruction. Return the cost of the scalar
05656     // instruction, plus the cost of insert and extract into vector
05657     // elements, times the vector width.
05658     unsigned Cost = 0;
05659 
05660     if (!RetTy->isVoidTy() && VF != 1) {
05661       unsigned InsCost = TTI.getVectorInstrCost(Instruction::InsertElement,
05662                                                 VectorTy);
05663       unsigned ExtCost = TTI.getVectorInstrCost(Instruction::ExtractElement,
05664                                                 VectorTy);
05665 
05666       // The cost of inserting the results plus extracting each one of the
05667       // operands.
05668       Cost += VF * (InsCost + ExtCost * I->getNumOperands());
05669     }
05670 
05671     // The cost of executing VF copies of the scalar instruction. This opcode
05672     // is unknown. Assume that it is the same as 'mul'.
05673     Cost += VF * TTI.getArithmeticInstrCost(Instruction::Mul, VectorTy);
05674     return Cost;
05675   }
05676   }// end of switch.
05677 }
05678 
05679 Type* LoopVectorizationCostModel::ToVectorTy(Type *Scalar, unsigned VF) {
05680   if (Scalar->isVoidTy() || VF == 1)
05681     return Scalar;
05682   return VectorType::get(Scalar, VF);
05683 }
05684 
05685 char LoopVectorize::ID = 0;
05686 static const char lv_name[] = "Loop Vectorization";
05687 INITIALIZE_PASS_BEGIN(LoopVectorize, LV_NAME, lv_name, false, false)
05688 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
05689 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfo)
05690 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
05691 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
05692 INITIALIZE_PASS_DEPENDENCY(LCSSA)
05693 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
05694 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
05695 INITIALIZE_PASS_END(LoopVectorize, LV_NAME, lv_name, false, false)
05696 
05697 namespace llvm {
05698   Pass *createLoopVectorizePass(bool NoUnrolling, bool AlwaysVectorize) {
05699     return new LoopVectorize(NoUnrolling, AlwaysVectorize);
05700   }
05701 }
05702 
05703 bool LoopVectorizationCostModel::isConsecutiveLoadOrStore(Instruction *Inst) {
05704   // Check for a store.
05705   if (StoreInst *ST = dyn_cast<StoreInst>(Inst))
05706     return Legal->isConsecutivePtr(ST->getPointerOperand()) != 0;
05707 
05708   // Check for a load.
05709   if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
05710     return Legal->isConsecutivePtr(LI->getPointerOperand()) != 0;
05711 
05712   return false;
05713 }
05714 
05715 
05716 void InnerLoopUnroller::scalarizeInstruction(Instruction *Instr,
05717                                              bool IfPredicateStore) {
05718   assert(!Instr->getType()->isAggregateType() && "Can't handle vectors");
05719   // Holds vector parameters or scalars, in case of uniform vals.
05720   SmallVector<VectorParts, 4> Params;
05721 
05722   setDebugLocFromInst(Builder, Instr);
05723 
05724   // Find all of the vectorized parameters.
05725   for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) {
05726     Value *SrcOp = Instr->getOperand(op);
05727 
05728     // If we are accessing the old induction variable, use the new one.
05729     if (SrcOp == OldInduction) {
05730       Params.push_back(getVectorValue(SrcOp));
05731       continue;
05732     }
05733 
05734     // Try using previously calculated values.
05735     Instruction *SrcInst = dyn_cast<Instruction>(SrcOp);
05736 
05737     // If the src is an instruction that appeared earlier in the basic block
05738     // then it should already be vectorized.
05739     if (SrcInst && OrigLoop->contains(SrcInst)) {
05740       assert(WidenMap.has(SrcInst) && "Source operand is unavailable");
05741       // The parameter is a vector value from earlier.
05742       Params.push_back(WidenMap.get(SrcInst));
05743     } else {
05744       // The parameter is a scalar from outside the loop. Maybe even a constant.
05745       VectorParts Scalars;
05746       Scalars.append(UF, SrcOp);
05747       Params.push_back(Scalars);
05748     }
05749   }
05750 
05751   assert(Params.size() == Instr->getNumOperands() &&
05752          "Invalid number of operands");
05753 
05754   // Does this instruction return a value ?
05755   bool IsVoidRetTy = Instr->getType()->isVoidTy();
05756 
05757   Value *UndefVec = IsVoidRetTy ? 0 :
05758   UndefValue::get(Instr->getType());
05759   // Create a new entry in the WidenMap and initialize it to Undef or Null.
05760   VectorParts &VecResults = WidenMap.splat(Instr, UndefVec);
05761 
05762   Instruction *InsertPt = Builder.GetInsertPoint();
05763   BasicBlock *IfBlock = Builder.GetInsertBlock();
05764   BasicBlock *CondBlock = 0;
05765 
05766   VectorParts Cond;
05767   Loop *VectorLp = 0;
05768   if (IfPredicateStore) {
05769     assert(Instr->getParent()->getSinglePredecessor() &&
05770            "Only support single predecessor blocks");
05771     Cond = createEdgeMask(Instr->getParent()->getSinglePredecessor(),
05772                           Instr->getParent());
05773     VectorLp = LI->getLoopFor(IfBlock);
05774     assert(VectorLp && "Must have a loop for this block");
05775   }
05776 
05777   // For each vector unroll 'part':
05778   for (unsigned Part = 0; Part < UF; ++Part) {
05779     // For each scalar that we create:
05780 
05781     // Start an "if (pred) a[i] = ..." block.
05782     Value *Cmp = 0;
05783     if (IfPredicateStore) {
05784       if (Cond[Part]->getType()->isVectorTy())
05785         Cond[Part] =
05786             Builder.CreateExtractElement(Cond[Part], Builder.getInt32(0));
05787       Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Cond[Part],
05788                                ConstantInt::get(Cond[Part]->getType(), 1));
05789       CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.store");
05790       LoopVectorBody.push_back(CondBlock);
05791       VectorLp->addBasicBlockToLoop(CondBlock, LI->getBase());
05792       // Update Builder with newly created basic block.
05793       Builder.SetInsertPoint(InsertPt);
05794     }
05795 
05796     Instruction *Cloned = Instr->clone();
05797       if (!IsVoidRetTy)
05798         Cloned->setName(Instr->getName() + ".cloned");
05799       // Replace the operands of the cloned instructions with extracted scalars.
05800       for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) {
05801         Value *Op = Params[op][Part];
05802         Cloned->setOperand(op, Op);
05803       }
05804 
05805       // Place the cloned scalar in the new loop.
05806       Builder.Insert(Cloned);
05807 
05808       // If the original scalar returns a value we need to place it in a vector
05809       // so that future users will be able to use it.
05810       if (!IsVoidRetTy)
05811         VecResults[Part] = Cloned;
05812 
05813     // End if-block.
05814       if (IfPredicateStore) {
05815         BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else");
05816         LoopVectorBody.push_back(NewIfBlock);
05817         VectorLp->addBasicBlockToLoop(NewIfBlock, LI->getBase());
05818         Builder.SetInsertPoint(InsertPt);
05819         Instruction *OldBr = IfBlock->getTerminator();
05820         BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
05821         OldBr->eraseFromParent();
05822         IfBlock = NewIfBlock;
05823       }
05824   }
05825 }
05826 
05827 void InnerLoopUnroller::vectorizeMemoryInstruction(Instruction *Instr) {
05828   StoreInst *SI = dyn_cast<StoreInst>(Instr);
05829   bool IfPredicateStore = (SI && Legal->blockNeedsPredication(SI->getParent()));
05830 
05831   return scalarizeInstruction(Instr, IfPredicateStore);
05832 }
05833 
05834 Value *InnerLoopUnroller::reverseVector(Value *Vec) {
05835   return Vec;
05836 }
05837 
05838 Value *InnerLoopUnroller::getBroadcastInstrs(Value *V) {
05839   return V;
05840 }
05841 
05842 Value *InnerLoopUnroller::getConsecutiveVector(Value* Val, int StartIdx,
05843                                                bool Negate) {
05844   // When unrolling and the VF is 1, we only need to add a simple scalar.
05845   Type *ITy = Val->getType();
05846   assert(!ITy->isVectorTy() && "Val must be a scalar");
05847   Constant *C = ConstantInt::get(ITy, StartIdx, Negate);
05848   return Builder.CreateAdd(Val, C, "induction");
05849 }
05850