LLVM  mainline
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/AliasSetTracker.h"
00058 #include "llvm/Analysis/AssumptionCache.h"
00059 #include "llvm/Analysis/BlockFrequencyInfo.h"
00060 #include "llvm/Analysis/CodeMetrics.h"
00061 #include "llvm/Analysis/LoopAccessAnalysis.h"
00062 #include "llvm/Analysis/LoopInfo.h"
00063 #include "llvm/Analysis/LoopIterator.h"
00064 #include "llvm/Analysis/LoopPass.h"
00065 #include "llvm/Analysis/ScalarEvolution.h"
00066 #include "llvm/Analysis/ScalarEvolutionExpander.h"
00067 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
00068 #include "llvm/Analysis/TargetTransformInfo.h"
00069 #include "llvm/Analysis/ValueTracking.h"
00070 #include "llvm/IR/Constants.h"
00071 #include "llvm/IR/DataLayout.h"
00072 #include "llvm/IR/DebugInfo.h"
00073 #include "llvm/IR/DerivedTypes.h"
00074 #include "llvm/IR/DiagnosticInfo.h"
00075 #include "llvm/IR/Dominators.h"
00076 #include "llvm/IR/Function.h"
00077 #include "llvm/IR/IRBuilder.h"
00078 #include "llvm/IR/Instructions.h"
00079 #include "llvm/IR/IntrinsicInst.h"
00080 #include "llvm/IR/LLVMContext.h"
00081 #include "llvm/IR/Module.h"
00082 #include "llvm/IR/PatternMatch.h"
00083 #include "llvm/IR/Type.h"
00084 #include "llvm/IR/Value.h"
00085 #include "llvm/IR/ValueHandle.h"
00086 #include "llvm/IR/Verifier.h"
00087 #include "llvm/Pass.h"
00088 #include "llvm/Support/BranchProbability.h"
00089 #include "llvm/Support/CommandLine.h"
00090 #include "llvm/Support/Debug.h"
00091 #include "llvm/Support/raw_ostream.h"
00092 #include "llvm/Transforms/Scalar.h"
00093 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00094 #include "llvm/Transforms/Utils/Local.h"
00095 #include "llvm/Transforms/Utils/VectorUtils.h"
00096 #include "llvm/Transforms/Utils/LoopUtils.h"
00097 #include <algorithm>
00098 #include <map>
00099 #include <tuple>
00100 
00101 using namespace llvm;
00102 using namespace llvm::PatternMatch;
00103 
00104 #define LV_NAME "loop-vectorize"
00105 #define DEBUG_TYPE LV_NAME
00106 
00107 STATISTIC(LoopsVectorized, "Number of loops vectorized");
00108 STATISTIC(LoopsAnalyzed, "Number of loops analyzed for vectorization");
00109 
00110 static cl::opt<bool>
00111 EnableIfConversion("enable-if-conversion", cl::init(true), cl::Hidden,
00112                    cl::desc("Enable if-conversion during vectorization."));
00113 
00114 /// We don't vectorize loops with a known constant trip count below this number.
00115 static cl::opt<unsigned>
00116 TinyTripCountVectorThreshold("vectorizer-min-trip-count", cl::init(16),
00117                              cl::Hidden,
00118                              cl::desc("Don't vectorize loops with a constant "
00119                                       "trip count that is smaller than this "
00120                                       "value."));
00121 
00122 /// This enables versioning on the strides of symbolically striding memory
00123 /// accesses in code like the following.
00124 ///   for (i = 0; i < N; ++i)
00125 ///     A[i * Stride1] += B[i * Stride2] ...
00126 ///
00127 /// Will be roughly translated to
00128 ///    if (Stride1 == 1 && Stride2 == 1) {
00129 ///      for (i = 0; i < N; i+=4)
00130 ///       A[i:i+3] += ...
00131 ///    } else
00132 ///      ...
00133 static cl::opt<bool> EnableMemAccessVersioning(
00134     "enable-mem-access-versioning", cl::init(true), cl::Hidden,
00135     cl::desc("Enable symblic stride memory access versioning"));
00136 
00137 /// We don't unroll loops with a known constant trip count below this number.
00138 static const unsigned TinyTripCountUnrollThreshold = 128;
00139 
00140 static cl::opt<unsigned> ForceTargetNumScalarRegs(
00141     "force-target-num-scalar-regs", cl::init(0), cl::Hidden,
00142     cl::desc("A flag that overrides the target's number of scalar registers."));
00143 
00144 static cl::opt<unsigned> ForceTargetNumVectorRegs(
00145     "force-target-num-vector-regs", cl::init(0), cl::Hidden,
00146     cl::desc("A flag that overrides the target's number of vector registers."));
00147 
00148 /// Maximum vectorization interleave count.
00149 static const unsigned MaxInterleaveFactor = 16;
00150 
00151 static cl::opt<unsigned> ForceTargetMaxScalarInterleaveFactor(
00152     "force-target-max-scalar-interleave", cl::init(0), cl::Hidden,
00153     cl::desc("A flag that overrides the target's max interleave factor for "
00154              "scalar loops."));
00155 
00156 static cl::opt<unsigned> ForceTargetMaxVectorInterleaveFactor(
00157     "force-target-max-vector-interleave", cl::init(0), cl::Hidden,
00158     cl::desc("A flag that overrides the target's max interleave factor for "
00159              "vectorized loops."));
00160 
00161 static cl::opt<unsigned> ForceTargetInstructionCost(
00162     "force-target-instruction-cost", cl::init(0), cl::Hidden,
00163     cl::desc("A flag that overrides the target's expected cost for "
00164              "an instruction to a single constant value. Mostly "
00165              "useful for getting consistent testing."));
00166 
00167 static cl::opt<unsigned> SmallLoopCost(
00168     "small-loop-cost", cl::init(20), cl::Hidden,
00169     cl::desc("The cost of a loop that is considered 'small' by the unroller."));
00170 
00171 static cl::opt<bool> LoopVectorizeWithBlockFrequency(
00172     "loop-vectorize-with-block-frequency", cl::init(false), cl::Hidden,
00173     cl::desc("Enable the use of the block frequency analysis to access PGO "
00174              "heuristics minimizing code growth in cold regions and being more "
00175              "aggressive in hot regions."));
00176 
00177 // Runtime unroll loops for load/store throughput.
00178 static cl::opt<bool> EnableLoadStoreRuntimeUnroll(
00179     "enable-loadstore-runtime-unroll", cl::init(true), cl::Hidden,
00180     cl::desc("Enable runtime unrolling until load/store ports are saturated"));
00181 
00182 /// The number of stores in a loop that are allowed to need predication.
00183 static cl::opt<unsigned> NumberOfStoresToPredicate(
00184     "vectorize-num-stores-pred", cl::init(1), cl::Hidden,
00185     cl::desc("Max number of stores to be predicated behind an if."));
00186 
00187 static cl::opt<bool> EnableIndVarRegisterHeur(
00188     "enable-ind-var-reg-heur", cl::init(true), cl::Hidden,
00189     cl::desc("Count the induction variable only once when unrolling"));
00190 
00191 static cl::opt<bool> EnableCondStoresVectorization(
00192     "enable-cond-stores-vec", cl::init(false), cl::Hidden,
00193     cl::desc("Enable if predication of stores during vectorization."));
00194 
00195 static cl::opt<unsigned> MaxNestedScalarReductionUF(
00196     "max-nested-scalar-reduction-unroll", cl::init(2), cl::Hidden,
00197     cl::desc("The maximum unroll factor to use when unrolling a scalar "
00198              "reduction in a nested loop."));
00199 
00200 namespace {
00201 
00202 // Forward declarations.
00203 class LoopVectorizationLegality;
00204 class LoopVectorizationCostModel;
00205 class LoopVectorizeHints;
00206 
00207 /// \brief This modifies LoopAccessReport to initialize message with
00208 /// loop-vectorizer-specific part.
00209 class VectorizationReport : public LoopAccessReport {
00210 public:
00211   VectorizationReport(Instruction *I = nullptr)
00212       : LoopAccessReport("loop not vectorized: ", I) {}
00213 
00214   /// \brief This allows promotion of the loop-access analysis report into the
00215   /// loop-vectorizer report.  It modifies the message to add the
00216   /// loop-vectorizer-specific part of the message.
00217   explicit VectorizationReport(const LoopAccessReport &R)
00218       : LoopAccessReport(Twine("loop not vectorized: ") + R.str(),
00219                          R.getInstr()) {}
00220 };
00221 
00222 /// A helper function for converting Scalar types to vector types.
00223 /// If the incoming type is void, we return void. If the VF is 1, we return
00224 /// the scalar type.
00225 static Type* ToVectorTy(Type *Scalar, unsigned VF) {
00226   if (Scalar->isVoidTy() || VF == 1)
00227     return Scalar;
00228   return VectorType::get(Scalar, VF);
00229 }
00230 
00231 /// InnerLoopVectorizer vectorizes loops which contain only one basic
00232 /// block to a specified vectorization factor (VF).
00233 /// This class performs the widening of scalars into vectors, or multiple
00234 /// scalars. This class also implements the following features:
00235 /// * It inserts an epilogue loop for handling loops that don't have iteration
00236 ///   counts that are known to be a multiple of the vectorization factor.
00237 /// * It handles the code generation for reduction variables.
00238 /// * Scalarization (implementation using scalars) of un-vectorizable
00239 ///   instructions.
00240 /// InnerLoopVectorizer does not perform any vectorization-legality
00241 /// checks, and relies on the caller to check for the different legality
00242 /// aspects. The InnerLoopVectorizer relies on the
00243 /// LoopVectorizationLegality class to provide information about the induction
00244 /// and reduction variables that were found to a given vectorization factor.
00245 class InnerLoopVectorizer {
00246 public:
00247   InnerLoopVectorizer(Loop *OrigLoop, ScalarEvolution *SE, LoopInfo *LI,
00248                       DominatorTree *DT, const TargetLibraryInfo *TLI,
00249                       const TargetTransformInfo *TTI, unsigned VecWidth,
00250                       unsigned UnrollFactor)
00251       : OrigLoop(OrigLoop), SE(SE), LI(LI), DT(DT), TLI(TLI), TTI(TTI),
00252         VF(VecWidth), UF(UnrollFactor), Builder(SE->getContext()),
00253         Induction(nullptr), OldInduction(nullptr), WidenMap(UnrollFactor),
00254         Legal(nullptr), AddedSafetyChecks(false) {}
00255 
00256   // Perform the actual loop widening (vectorization).
00257   void vectorize(LoopVectorizationLegality *L) {
00258     Legal = L;
00259     // Create a new empty loop. Unlink the old loop and connect the new one.
00260     createEmptyLoop();
00261     // Widen each instruction in the old loop to a new one in the new loop.
00262     // Use the Legality module to find the induction and reduction variables.
00263     vectorizeLoop();
00264     // Register the new loop and update the analysis passes.
00265     updateAnalysis();
00266   }
00267 
00268   // Return true if any runtime check is added.
00269   bool IsSafetyChecksAdded() {
00270     return AddedSafetyChecks;
00271   }
00272 
00273   virtual ~InnerLoopVectorizer() {}
00274 
00275 protected:
00276   /// A small list of PHINodes.
00277   typedef SmallVector<PHINode*, 4> PhiVector;
00278   /// When we unroll loops we have multiple vector values for each scalar.
00279   /// This data structure holds the unrolled and vectorized values that
00280   /// originated from one scalar instruction.
00281   typedef SmallVector<Value*, 2> VectorParts;
00282 
00283   // When we if-convert we need to create edge masks. We have to cache values
00284   // so that we don't end up with exponential recursion/IR.
00285   typedef DenseMap<std::pair<BasicBlock*, BasicBlock*>,
00286                    VectorParts> EdgeMaskCache;
00287 
00288   /// \brief Add checks for strides that were assumed to be 1.
00289   ///
00290   /// Returns the last check instruction and the first check instruction in the
00291   /// pair as (first, last).
00292   std::pair<Instruction *, Instruction *> addStrideCheck(Instruction *Loc);
00293 
00294   /// Create an empty loop, based on the loop ranges of the old loop.
00295   void createEmptyLoop();
00296   /// Copy and widen the instructions from the old loop.
00297   virtual void vectorizeLoop();
00298 
00299   /// \brief The Loop exit block may have single value PHI nodes where the
00300   /// incoming value is 'Undef'. While vectorizing we only handled real values
00301   /// that were defined inside the loop. Here we fix the 'undef case'.
00302   /// See PR14725.
00303   void fixLCSSAPHIs();
00304 
00305   /// A helper function that computes the predicate of the block BB, assuming
00306   /// that the header block of the loop is set to True. It returns the *entry*
00307   /// mask for the block BB.
00308   VectorParts createBlockInMask(BasicBlock *BB);
00309   /// A helper function that computes the predicate of the edge between SRC
00310   /// and DST.
00311   VectorParts createEdgeMask(BasicBlock *Src, BasicBlock *Dst);
00312 
00313   /// A helper function to vectorize a single BB within the innermost loop.
00314   void vectorizeBlockInLoop(BasicBlock *BB, PhiVector *PV);
00315 
00316   /// Vectorize a single PHINode in a block. This method handles the induction
00317   /// variable canonicalization. It supports both VF = 1 for unrolled loops and
00318   /// arbitrary length vectors.
00319   void widenPHIInstruction(Instruction *PN, VectorParts &Entry,
00320                            unsigned UF, unsigned VF, PhiVector *PV);
00321 
00322   /// Insert the new loop to the loop hierarchy and pass manager
00323   /// and update the analysis passes.
00324   void updateAnalysis();
00325 
00326   /// This instruction is un-vectorizable. Implement it as a sequence
00327   /// of scalars. If \p IfPredicateStore is true we need to 'hide' each
00328   /// scalarized instruction behind an if block predicated on the control
00329   /// dependence of the instruction.
00330   virtual void scalarizeInstruction(Instruction *Instr,
00331                                     bool IfPredicateStore=false);
00332 
00333   /// Vectorize Load and Store instructions,
00334   virtual void vectorizeMemoryInstruction(Instruction *Instr);
00335 
00336   /// Create a broadcast instruction. This method generates a broadcast
00337   /// instruction (shuffle) for loop invariant values and for the induction
00338   /// value. If this is the induction variable then we extend it to N, N+1, ...
00339   /// this is needed because each iteration in the loop corresponds to a SIMD
00340   /// element.
00341   virtual Value *getBroadcastInstrs(Value *V);
00342 
00343   /// This function adds (StartIdx, StartIdx + Step, StartIdx + 2*Step, ...)
00344   /// to each vector element of Val. The sequence starts at StartIndex.
00345   virtual Value *getStepVector(Value *Val, int StartIdx, Value *Step);
00346 
00347   /// When we go over instructions in the basic block we rely on previous
00348   /// values within the current basic block or on loop invariant values.
00349   /// When we widen (vectorize) values we place them in the map. If the values
00350   /// are not within the map, they have to be loop invariant, so we simply
00351   /// broadcast them into a vector.
00352   VectorParts &getVectorValue(Value *V);
00353 
00354   /// Generate a shuffle sequence that will reverse the vector Vec.
00355   virtual Value *reverseVector(Value *Vec);
00356 
00357   /// This is a helper class that holds the vectorizer state. It maps scalar
00358   /// instructions to vector instructions. When the code is 'unrolled' then
00359   /// then a single scalar value is mapped to multiple vector parts. The parts
00360   /// are stored in the VectorPart type.
00361   struct ValueMap {
00362     /// C'tor.  UnrollFactor controls the number of vectors ('parts') that
00363     /// are mapped.
00364     ValueMap(unsigned UnrollFactor) : UF(UnrollFactor) {}
00365 
00366     /// \return True if 'Key' is saved in the Value Map.
00367     bool has(Value *Key) const { return MapStorage.count(Key); }
00368 
00369     /// Initializes a new entry in the map. Sets all of the vector parts to the
00370     /// save value in 'Val'.
00371     /// \return A reference to a vector with splat values.
00372     VectorParts &splat(Value *Key, Value *Val) {
00373       VectorParts &Entry = MapStorage[Key];
00374       Entry.assign(UF, Val);
00375       return Entry;
00376     }
00377 
00378     ///\return A reference to the value that is stored at 'Key'.
00379     VectorParts &get(Value *Key) {
00380       VectorParts &Entry = MapStorage[Key];
00381       if (Entry.empty())
00382         Entry.resize(UF);
00383       assert(Entry.size() == UF);
00384       return Entry;
00385     }
00386 
00387   private:
00388     /// The unroll factor. Each entry in the map stores this number of vector
00389     /// elements.
00390     unsigned UF;
00391 
00392     /// Map storage. We use std::map and not DenseMap because insertions to a
00393     /// dense map invalidates its iterators.
00394     std::map<Value *, VectorParts> MapStorage;
00395   };
00396 
00397   /// The original loop.
00398   Loop *OrigLoop;
00399   /// Scev analysis to use.
00400   ScalarEvolution *SE;
00401   /// Loop Info.
00402   LoopInfo *LI;
00403   /// Dominator Tree.
00404   DominatorTree *DT;
00405   /// Alias Analysis.
00406   AliasAnalysis *AA;
00407   /// Target Library Info.
00408   const TargetLibraryInfo *TLI;
00409   /// Target Transform Info.
00410   const TargetTransformInfo *TTI;
00411 
00412   /// The vectorization SIMD factor to use. Each vector will have this many
00413   /// vector elements.
00414   unsigned VF;
00415 
00416 protected:
00417   /// The vectorization unroll factor to use. Each scalar is vectorized to this
00418   /// many different vector instructions.
00419   unsigned UF;
00420 
00421   /// The builder that we use
00422   IRBuilder<> Builder;
00423 
00424   // --- Vectorization state ---
00425 
00426   /// The vector-loop preheader.
00427   BasicBlock *LoopVectorPreHeader;
00428   /// The scalar-loop preheader.
00429   BasicBlock *LoopScalarPreHeader;
00430   /// Middle Block between the vector and the scalar.
00431   BasicBlock *LoopMiddleBlock;
00432   ///The ExitBlock of the scalar loop.
00433   BasicBlock *LoopExitBlock;
00434   ///The vector loop body.
00435   SmallVector<BasicBlock *, 4> LoopVectorBody;
00436   ///The scalar loop body.
00437   BasicBlock *LoopScalarBody;
00438   /// A list of all bypass blocks. The first block is the entry of the loop.
00439   SmallVector<BasicBlock *, 4> LoopBypassBlocks;
00440 
00441   /// The new Induction variable which was added to the new block.
00442   PHINode *Induction;
00443   /// The induction variable of the old basic block.
00444   PHINode *OldInduction;
00445   /// Holds the extended (to the widest induction type) start index.
00446   Value *ExtendedIdx;
00447   /// Maps scalars to widened vectors.
00448   ValueMap WidenMap;
00449   EdgeMaskCache MaskCache;
00450 
00451   LoopVectorizationLegality *Legal;
00452 
00453   // Record whether runtime check is added.
00454   bool AddedSafetyChecks;
00455 };
00456 
00457 class InnerLoopUnroller : public InnerLoopVectorizer {
00458 public:
00459   InnerLoopUnroller(Loop *OrigLoop, ScalarEvolution *SE, LoopInfo *LI,
00460                     DominatorTree *DT, const TargetLibraryInfo *TLI,
00461                     const TargetTransformInfo *TTI, unsigned UnrollFactor)
00462       : InnerLoopVectorizer(OrigLoop, SE, LI, DT, TLI, TTI, 1, UnrollFactor) {}
00463 
00464 private:
00465   void scalarizeInstruction(Instruction *Instr,
00466                             bool IfPredicateStore = false) override;
00467   void vectorizeMemoryInstruction(Instruction *Instr) override;
00468   Value *getBroadcastInstrs(Value *V) override;
00469   Value *getStepVector(Value *Val, int StartIdx, Value *Step) override;
00470   Value *reverseVector(Value *Vec) override;
00471 };
00472 
00473 /// \brief Look for a meaningful debug location on the instruction or it's
00474 /// operands.
00475 static Instruction *getDebugLocFromInstOrOperands(Instruction *I) {
00476   if (!I)
00477     return I;
00478 
00479   DebugLoc Empty;
00480   if (I->getDebugLoc() != Empty)
00481     return I;
00482 
00483   for (User::op_iterator OI = I->op_begin(), OE = I->op_end(); OI != OE; ++OI) {
00484     if (Instruction *OpInst = dyn_cast<Instruction>(*OI))
00485       if (OpInst->getDebugLoc() != Empty)
00486         return OpInst;
00487   }
00488 
00489   return I;
00490 }
00491 
00492 /// \brief Set the debug location in the builder using the debug location in the
00493 /// instruction.
00494 static void setDebugLocFromInst(IRBuilder<> &B, const Value *Ptr) {
00495   if (const Instruction *Inst = dyn_cast_or_null<Instruction>(Ptr))
00496     B.SetCurrentDebugLocation(Inst->getDebugLoc());
00497   else
00498     B.SetCurrentDebugLocation(DebugLoc());
00499 }
00500 
00501 #ifndef NDEBUG
00502 /// \return string containing a file name and a line # for the given loop.
00503 static std::string getDebugLocString(const Loop *L) {
00504   std::string Result;
00505   if (L) {
00506     raw_string_ostream OS(Result);
00507     if (const DebugLoc LoopDbgLoc = L->getStartLoc())
00508       LoopDbgLoc.print(OS);
00509     else
00510       // Just print the module name.
00511       OS << L->getHeader()->getParent()->getParent()->getModuleIdentifier();
00512     OS.flush();
00513   }
00514   return Result;
00515 }
00516 #endif
00517 
00518 /// \brief Propagate known metadata from one instruction to another.
00519 static void propagateMetadata(Instruction *To, const Instruction *From) {
00520   SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
00521   From->getAllMetadataOtherThanDebugLoc(Metadata);
00522 
00523   for (auto M : Metadata) {
00524     unsigned Kind = M.first;
00525 
00526     // These are safe to transfer (this is safe for TBAA, even when we
00527     // if-convert, because should that metadata have had a control dependency
00528     // on the condition, and thus actually aliased with some other
00529     // non-speculated memory access when the condition was false, this would be
00530     // caught by the runtime overlap checks).
00531     if (Kind != LLVMContext::MD_tbaa &&
00532         Kind != LLVMContext::MD_alias_scope &&
00533         Kind != LLVMContext::MD_noalias &&
00534         Kind != LLVMContext::MD_fpmath)
00535       continue;
00536 
00537     To->setMetadata(Kind, M.second);
00538   }
00539 }
00540 
00541 /// \brief Propagate known metadata from one instruction to a vector of others.
00542 static void propagateMetadata(SmallVectorImpl<Value *> &To, const Instruction *From) {
00543   for (Value *V : To)
00544     if (Instruction *I = dyn_cast<Instruction>(V))
00545       propagateMetadata(I, From);
00546 }
00547 
00548 /// LoopVectorizationLegality checks if it is legal to vectorize a loop, and
00549 /// to what vectorization factor.
00550 /// This class does not look at the profitability of vectorization, only the
00551 /// legality. This class has two main kinds of checks:
00552 /// * Memory checks - The code in canVectorizeMemory checks if vectorization
00553 ///   will change the order of memory accesses in a way that will change the
00554 ///   correctness of the program.
00555 /// * Scalars checks - The code in canVectorizeInstrs and canVectorizeMemory
00556 /// checks for a number of different conditions, such as the availability of a
00557 /// single induction variable, that all types are supported and vectorize-able,
00558 /// etc. This code reflects the capabilities of InnerLoopVectorizer.
00559 /// This class is also used by InnerLoopVectorizer for identifying
00560 /// induction variable and the different reduction variables.
00561 class LoopVectorizationLegality {
00562 public:
00563   LoopVectorizationLegality(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
00564                             TargetLibraryInfo *TLI, AliasAnalysis *AA,
00565                             Function *F, const TargetTransformInfo *TTI,
00566                             LoopAccessAnalysis *LAA)
00567       : NumPredStores(0), TheLoop(L), SE(SE), TLI(TLI), TheFunction(F),
00568         TTI(TTI), DT(DT), LAA(LAA), LAI(nullptr), Induction(nullptr),
00569         WidestIndTy(nullptr), HasFunNoNaNAttr(false) {}
00570 
00571   /// This enum represents the kinds of inductions that we support.
00572   enum InductionKind {
00573     IK_NoInduction,  ///< Not an induction variable.
00574     IK_IntInduction, ///< Integer induction variable. Step = C.
00575     IK_PtrInduction  ///< Pointer induction var. Step = C / sizeof(elem).
00576   };
00577 
00578   /// A struct for saving information about induction variables.
00579   struct InductionInfo {
00580     InductionInfo(Value *Start, InductionKind K, ConstantInt *Step)
00581         : StartValue(Start), IK(K), StepValue(Step) {
00582       assert(IK != IK_NoInduction && "Not an induction");
00583       assert(StartValue && "StartValue is null");
00584       assert(StepValue && !StepValue->isZero() && "StepValue is zero");
00585       assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
00586              "StartValue is not a pointer for pointer induction");
00587       assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
00588              "StartValue is not an integer for integer induction");
00589       assert(StepValue->getType()->isIntegerTy() &&
00590              "StepValue is not an integer");
00591     }
00592     InductionInfo()
00593         : StartValue(nullptr), IK(IK_NoInduction), StepValue(nullptr) {}
00594 
00595     /// Get the consecutive direction. Returns:
00596     ///   0 - unknown or non-consecutive.
00597     ///   1 - consecutive and increasing.
00598     ///  -1 - consecutive and decreasing.
00599     int getConsecutiveDirection() const {
00600       if (StepValue && (StepValue->isOne() || StepValue->isMinusOne()))
00601         return StepValue->getSExtValue();
00602       return 0;
00603     }
00604 
00605     /// Compute the transformed value of Index at offset StartValue using step
00606     /// StepValue.
00607     /// For integer induction, returns StartValue + Index * StepValue.
00608     /// For pointer induction, returns StartValue[Index * StepValue].
00609     /// FIXME: The newly created binary instructions should contain nsw/nuw
00610     /// flags, which can be found from the original scalar operations.
00611     Value *transform(IRBuilder<> &B, Value *Index) const {
00612       switch (IK) {
00613       case IK_IntInduction:
00614         assert(Index->getType() == StartValue->getType() &&
00615                "Index type does not match StartValue type");
00616         if (StepValue->isMinusOne())
00617           return B.CreateSub(StartValue, Index);
00618         if (!StepValue->isOne())
00619           Index = B.CreateMul(Index, StepValue);
00620         return B.CreateAdd(StartValue, Index);
00621 
00622       case IK_PtrInduction:
00623         if (StepValue->isMinusOne())
00624           Index = B.CreateNeg(Index);
00625         else if (!StepValue->isOne())
00626           Index = B.CreateMul(Index, StepValue);
00627         return B.CreateGEP(nullptr, StartValue, Index);
00628 
00629       case IK_NoInduction:
00630         return nullptr;
00631       }
00632       llvm_unreachable("invalid enum");
00633     }
00634 
00635     /// Start value.
00636     TrackingVH<Value> StartValue;
00637     /// Induction kind.
00638     InductionKind IK;
00639     /// Step value.
00640     ConstantInt *StepValue;
00641   };
00642 
00643   /// ReductionList contains the reduction descriptors for all
00644   /// of the reductions that were found in the loop.
00645   typedef DenseMap<PHINode*, ReductionDescriptor> ReductionList;
00646 
00647   /// InductionList saves induction variables and maps them to the
00648   /// induction descriptor.
00649   typedef MapVector<PHINode*, InductionInfo> InductionList;
00650 
00651   /// Returns true if it is legal to vectorize this loop.
00652   /// This does not mean that it is profitable to vectorize this
00653   /// loop, only that it is legal to do so.
00654   bool canVectorize();
00655 
00656   /// Returns the Induction variable.
00657   PHINode *getInduction() { return Induction; }
00658 
00659   /// Returns the reduction variables found in the loop.
00660   ReductionList *getReductionVars() { return &Reductions; }
00661 
00662   /// Returns the induction variables found in the loop.
00663   InductionList *getInductionVars() { return &Inductions; }
00664 
00665   /// Returns the widest induction type.
00666   Type *getWidestInductionType() { return WidestIndTy; }
00667 
00668   /// Returns True if V is an induction variable in this loop.
00669   bool isInductionVariable(const Value *V);
00670 
00671   /// Return true if the block BB needs to be predicated in order for the loop
00672   /// to be vectorized.
00673   bool blockNeedsPredication(BasicBlock *BB);
00674 
00675   /// Check if this  pointer is consecutive when vectorizing. This happens
00676   /// when the last index of the GEP is the induction variable, or that the
00677   /// pointer itself is an induction variable.
00678   /// This check allows us to vectorize A[idx] into a wide load/store.
00679   /// Returns:
00680   /// 0 - Stride is unknown or non-consecutive.
00681   /// 1 - Address is consecutive.
00682   /// -1 - Address is consecutive, and decreasing.
00683   int isConsecutivePtr(Value *Ptr);
00684 
00685   /// Returns true if the value V is uniform within the loop.
00686   bool isUniform(Value *V);
00687 
00688   /// Returns true if this instruction will remain scalar after vectorization.
00689   bool isUniformAfterVectorization(Instruction* I) { return Uniforms.count(I); }
00690 
00691   /// Returns the information that we collected about runtime memory check.
00692   const LoopAccessInfo::RuntimePointerCheck *getRuntimePointerCheck() const {
00693     return LAI->getRuntimePointerCheck();
00694   }
00695 
00696   const LoopAccessInfo *getLAI() const {
00697     return LAI;
00698   }
00699 
00700   unsigned getMaxSafeDepDistBytes() { return LAI->getMaxSafeDepDistBytes(); }
00701 
00702   bool hasStride(Value *V) { return StrideSet.count(V); }
00703   bool mustCheckStrides() { return !StrideSet.empty(); }
00704   SmallPtrSet<Value *, 8>::iterator strides_begin() {
00705     return StrideSet.begin();
00706   }
00707   SmallPtrSet<Value *, 8>::iterator strides_end() { return StrideSet.end(); }
00708 
00709   /// Returns true if the target machine supports masked store operation
00710   /// for the given \p DataType and kind of access to \p Ptr.
00711   bool isLegalMaskedStore(Type *DataType, Value *Ptr) {
00712     return TTI->isLegalMaskedStore(DataType, isConsecutivePtr(Ptr));
00713   }
00714   /// Returns true if the target machine supports masked load operation
00715   /// for the given \p DataType and kind of access to \p Ptr.
00716   bool isLegalMaskedLoad(Type *DataType, Value *Ptr) {
00717     return TTI->isLegalMaskedLoad(DataType, isConsecutivePtr(Ptr));
00718   }
00719   /// Returns true if vector representation of the instruction \p I
00720   /// requires mask.
00721   bool isMaskRequired(const Instruction* I) {
00722     return (MaskedOp.count(I) != 0);
00723   }
00724   unsigned getNumStores() const {
00725     return LAI->getNumStores();
00726   }
00727   unsigned getNumLoads() const {
00728     return LAI->getNumLoads();
00729   }
00730   unsigned getNumPredStores() const {
00731     return NumPredStores;
00732   }
00733 private:
00734   /// Check if a single basic block loop is vectorizable.
00735   /// At this point we know that this is a loop with a constant trip count
00736   /// and we only need to check individual instructions.
00737   bool canVectorizeInstrs();
00738 
00739   /// When we vectorize loops we may change the order in which
00740   /// we read and write from memory. This method checks if it is
00741   /// legal to vectorize the code, considering only memory constrains.
00742   /// Returns true if the loop is vectorizable
00743   bool canVectorizeMemory();
00744 
00745   /// Return true if we can vectorize this loop using the IF-conversion
00746   /// transformation.
00747   bool canVectorizeWithIfConvert();
00748 
00749   /// Collect the variables that need to stay uniform after vectorization.
00750   void collectLoopUniforms();
00751 
00752   /// Return true if all of the instructions in the block can be speculatively
00753   /// executed. \p SafePtrs is a list of addresses that are known to be legal
00754   /// and we know that we can read from them without segfault.
00755   bool blockCanBePredicated(BasicBlock *BB, SmallPtrSetImpl<Value *> &SafePtrs);
00756 
00757   /// Returns the induction kind of Phi and record the step. This function may
00758   /// return NoInduction if the PHI is not an induction variable.
00759   InductionKind isInductionVariable(PHINode *Phi, ConstantInt *&StepValue);
00760 
00761   /// \brief Collect memory access with loop invariant strides.
00762   ///
00763   /// Looks for accesses like "a[i * StrideA]" where "StrideA" is loop
00764   /// invariant.
00765   void collectStridedAccess(Value *LoadOrStoreInst);
00766 
00767   /// Report an analysis message to assist the user in diagnosing loops that are
00768   /// not vectorized.  These are handled as LoopAccessReport rather than
00769   /// VectorizationReport because the << operator of VectorizationReport returns
00770   /// LoopAccessReport.
00771   void emitAnalysis(const LoopAccessReport &Message) {
00772     LoopAccessReport::emitAnalysis(Message, TheFunction, TheLoop, LV_NAME);
00773   }
00774 
00775   unsigned NumPredStores;
00776 
00777   /// The loop that we evaluate.
00778   Loop *TheLoop;
00779   /// Scev analysis.
00780   ScalarEvolution *SE;
00781   /// Target Library Info.
00782   TargetLibraryInfo *TLI;
00783   /// Parent function
00784   Function *TheFunction;
00785   /// Target Transform Info
00786   const TargetTransformInfo *TTI;
00787   /// Dominator Tree.
00788   DominatorTree *DT;
00789   // LoopAccess analysis.
00790   LoopAccessAnalysis *LAA;
00791   // And the loop-accesses info corresponding to this loop.  This pointer is
00792   // null until canVectorizeMemory sets it up.
00793   const LoopAccessInfo *LAI;
00794 
00795   //  ---  vectorization state --- //
00796 
00797   /// Holds the integer induction variable. This is the counter of the
00798   /// loop.
00799   PHINode *Induction;
00800   /// Holds the reduction variables.
00801   ReductionList Reductions;
00802   /// Holds all of the induction variables that we found in the loop.
00803   /// Notice that inductions don't need to start at zero and that induction
00804   /// variables can be pointers.
00805   InductionList Inductions;
00806   /// Holds the widest induction type encountered.
00807   Type *WidestIndTy;
00808 
00809   /// Allowed outside users. This holds the reduction
00810   /// vars which can be accessed from outside the loop.
00811   SmallPtrSet<Value*, 4> AllowedExit;
00812   /// This set holds the variables which are known to be uniform after
00813   /// vectorization.
00814   SmallPtrSet<Instruction*, 4> Uniforms;
00815 
00816   /// Can we assume the absence of NaNs.
00817   bool HasFunNoNaNAttr;
00818 
00819   ValueToValueMap Strides;
00820   SmallPtrSet<Value *, 8> StrideSet;
00821 
00822   /// While vectorizing these instructions we have to generate a
00823   /// call to the appropriate masked intrinsic
00824   SmallPtrSet<const Instruction*, 8> MaskedOp;
00825 };
00826 
00827 /// LoopVectorizationCostModel - estimates the expected speedups due to
00828 /// vectorization.
00829 /// In many cases vectorization is not profitable. This can happen because of
00830 /// a number of reasons. In this class we mainly attempt to predict the
00831 /// expected speedup/slowdowns due to the supported instruction set. We use the
00832 /// TargetTransformInfo to query the different backends for the cost of
00833 /// different operations.
00834 class LoopVectorizationCostModel {
00835 public:
00836   LoopVectorizationCostModel(Loop *L, ScalarEvolution *SE, LoopInfo *LI,
00837                              LoopVectorizationLegality *Legal,
00838                              const TargetTransformInfo &TTI,
00839                              const TargetLibraryInfo *TLI, AssumptionCache *AC,
00840                              const Function *F, const LoopVectorizeHints *Hints)
00841       : TheLoop(L), SE(SE), LI(LI), Legal(Legal), TTI(TTI), TLI(TLI),
00842         TheFunction(F), Hints(Hints) {
00843     CodeMetrics::collectEphemeralValues(L, AC, EphValues);
00844   }
00845 
00846   /// Information about vectorization costs
00847   struct VectorizationFactor {
00848     unsigned Width; // Vector width with best cost
00849     unsigned Cost; // Cost of the loop with that width
00850   };
00851   /// \return The most profitable vectorization factor and the cost of that VF.
00852   /// This method checks every power of two up to VF. If UserVF is not ZERO
00853   /// then this vectorization factor will be selected if vectorization is
00854   /// possible.
00855   VectorizationFactor selectVectorizationFactor(bool OptForSize);
00856 
00857   /// \return The size (in bits) of the widest type in the code that
00858   /// needs to be vectorized. We ignore values that remain scalar such as
00859   /// 64 bit loop indices.
00860   unsigned getWidestType();
00861 
00862   /// \return The most profitable unroll factor.
00863   /// If UserUF is non-zero then this method finds the best unroll-factor
00864   /// based on register pressure and other parameters.
00865   /// VF and LoopCost are the selected vectorization factor and the cost of the
00866   /// selected VF.
00867   unsigned selectUnrollFactor(bool OptForSize, unsigned VF, unsigned LoopCost);
00868 
00869   /// \brief A struct that represents some properties of the register usage
00870   /// of a loop.
00871   struct RegisterUsage {
00872     /// Holds the number of loop invariant values that are used in the loop.
00873     unsigned LoopInvariantRegs;
00874     /// Holds the maximum number of concurrent live intervals in the loop.
00875     unsigned MaxLocalUsers;
00876     /// Holds the number of instructions in the loop.
00877     unsigned NumInstructions;
00878   };
00879 
00880   /// \return  information about the register usage of the loop.
00881   RegisterUsage calculateRegisterUsage();
00882 
00883 private:
00884   /// Returns the expected execution cost. The unit of the cost does
00885   /// not matter because we use the 'cost' units to compare different
00886   /// vector widths. The cost that is returned is *not* normalized by
00887   /// the factor width.
00888   unsigned expectedCost(unsigned VF);
00889 
00890   /// Returns the execution time cost of an instruction for a given vector
00891   /// width. Vector width of one means scalar.
00892   unsigned getInstructionCost(Instruction *I, unsigned VF);
00893 
00894   /// Returns whether the instruction is a load or store and will be a emitted
00895   /// as a vector operation.
00896   bool isConsecutiveLoadOrStore(Instruction *I);
00897 
00898   /// Report an analysis message to assist the user in diagnosing loops that are
00899   /// not vectorized.  These are handled as LoopAccessReport rather than
00900   /// VectorizationReport because the << operator of VectorizationReport returns
00901   /// LoopAccessReport.
00902   void emitAnalysis(const LoopAccessReport &Message) {
00903     LoopAccessReport::emitAnalysis(Message, TheFunction, TheLoop, LV_NAME);
00904   }
00905 
00906   /// Values used only by @llvm.assume calls.
00907   SmallPtrSet<const Value *, 32> EphValues;
00908 
00909   /// The loop that we evaluate.
00910   Loop *TheLoop;
00911   /// Scev analysis.
00912   ScalarEvolution *SE;
00913   /// Loop Info analysis.
00914   LoopInfo *LI;
00915   /// Vectorization legality.
00916   LoopVectorizationLegality *Legal;
00917   /// Vector target information.
00918   const TargetTransformInfo &TTI;
00919   /// Target Library Info.
00920   const TargetLibraryInfo *TLI;
00921   const Function *TheFunction;
00922   // Loop Vectorize Hint.
00923   const LoopVectorizeHints *Hints;
00924 };
00925 
00926 /// Utility class for getting and setting loop vectorizer hints in the form
00927 /// of loop metadata.
00928 /// This class keeps a number of loop annotations locally (as member variables)
00929 /// and can, upon request, write them back as metadata on the loop. It will
00930 /// initially scan the loop for existing metadata, and will update the local
00931 /// values based on information in the loop.
00932 /// We cannot write all values to metadata, as the mere presence of some info,
00933 /// for example 'force', means a decision has been made. So, we need to be
00934 /// careful NOT to add them if the user hasn't specifically asked so.
00935 class LoopVectorizeHints {
00936   enum HintKind {
00937     HK_WIDTH,
00938     HK_UNROLL,
00939     HK_FORCE
00940   };
00941 
00942   /// Hint - associates name and validation with the hint value.
00943   struct Hint {
00944     const char * Name;
00945     unsigned Value; // This may have to change for non-numeric values.
00946     HintKind Kind;
00947 
00948     Hint(const char * Name, unsigned Value, HintKind Kind)
00949       : Name(Name), Value(Value), Kind(Kind) { }
00950 
00951     bool validate(unsigned Val) {
00952       switch (Kind) {
00953       case HK_WIDTH:
00954         return isPowerOf2_32(Val) && Val <= VectorizerParams::MaxVectorWidth;
00955       case HK_UNROLL:
00956         return isPowerOf2_32(Val) && Val <= MaxInterleaveFactor;
00957       case HK_FORCE:
00958         return (Val <= 1);
00959       }
00960       return false;
00961     }
00962   };
00963 
00964   /// Vectorization width.
00965   Hint Width;
00966   /// Vectorization interleave factor.
00967   Hint Interleave;
00968   /// Vectorization forced
00969   Hint Force;
00970 
00971   /// Return the loop metadata prefix.
00972   static StringRef Prefix() { return "llvm.loop."; }
00973 
00974 public:
00975   enum ForceKind {
00976     FK_Undefined = -1, ///< Not selected.
00977     FK_Disabled = 0,   ///< Forcing disabled.
00978     FK_Enabled = 1,    ///< Forcing enabled.
00979   };
00980 
00981   LoopVectorizeHints(const Loop *L, bool DisableInterleaving)
00982       : Width("vectorize.width", VectorizerParams::VectorizationFactor,
00983               HK_WIDTH),
00984         Interleave("interleave.count", DisableInterleaving, HK_UNROLL),
00985         Force("vectorize.enable", FK_Undefined, HK_FORCE),
00986         TheLoop(L) {
00987     // Populate values with existing loop metadata.
00988     getHintsFromMetadata();
00989 
00990     // force-vector-interleave overrides DisableInterleaving.
00991     if (VectorizerParams::isInterleaveForced())
00992       Interleave.Value = VectorizerParams::VectorizationInterleave;
00993 
00994     DEBUG(if (DisableInterleaving && Interleave.Value == 1) dbgs()
00995           << "LV: Interleaving disabled by the pass manager\n");
00996   }
00997 
00998   /// Mark the loop L as already vectorized by setting the width to 1.
00999   void setAlreadyVectorized() {
01000     Width.Value = Interleave.Value = 1;
01001     Hint Hints[] = {Width, Interleave};
01002     writeHintsToMetadata(Hints);
01003   }
01004 
01005   /// Dumps all the hint information.
01006   std::string emitRemark() const {
01007     VectorizationReport R;
01008     if (Force.Value == LoopVectorizeHints::FK_Disabled)
01009       R << "vectorization is explicitly disabled";
01010     else {
01011       R << "use -Rpass-analysis=loop-vectorize for more info";
01012       if (Force.Value == LoopVectorizeHints::FK_Enabled) {
01013         R << " (Force=true";
01014         if (Width.Value != 0)
01015           R << ", Vector Width=" << Width.Value;
01016         if (Interleave.Value != 0)
01017           R << ", Interleave Count=" << Interleave.Value;
01018         R << ")";
01019       }
01020     }
01021 
01022     return R.str();
01023   }
01024 
01025   unsigned getWidth() const { return Width.Value; }
01026   unsigned getInterleave() const { return Interleave.Value; }
01027   enum ForceKind getForce() const { return (ForceKind)Force.Value; }
01028 
01029 private:
01030   /// Find hints specified in the loop metadata and update local values.
01031   void getHintsFromMetadata() {
01032     MDNode *LoopID = TheLoop->getLoopID();
01033     if (!LoopID)
01034       return;
01035 
01036     // First operand should refer to the loop id itself.
01037     assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
01038     assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
01039 
01040     for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
01041       const MDString *S = nullptr;
01042       SmallVector<Metadata *, 4> Args;
01043 
01044       // The expected hint is either a MDString or a MDNode with the first
01045       // operand a MDString.
01046       if (const MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i))) {
01047         if (!MD || MD->getNumOperands() == 0)
01048           continue;
01049         S = dyn_cast<MDString>(MD->getOperand(0));
01050         for (unsigned i = 1, ie = MD->getNumOperands(); i < ie; ++i)
01051           Args.push_back(MD->getOperand(i));
01052       } else {
01053         S = dyn_cast<MDString>(LoopID->getOperand(i));
01054         assert(Args.size() == 0 && "too many arguments for MDString");
01055       }
01056 
01057       if (!S)
01058         continue;
01059 
01060       // Check if the hint starts with the loop metadata prefix.
01061       StringRef Name = S->getString();
01062       if (Args.size() == 1)
01063         setHint(Name, Args[0]);
01064     }
01065   }
01066 
01067   /// Checks string hint with one operand and set value if valid.
01068   void setHint(StringRef Name, Metadata *Arg) {
01069     if (!Name.startswith(Prefix()))
01070       return;
01071     Name = Name.substr(Prefix().size(), StringRef::npos);
01072 
01073     const ConstantInt *C = mdconst::dyn_extract<ConstantInt>(Arg);
01074     if (!C) return;
01075     unsigned Val = C->getZExtValue();
01076 
01077     Hint *Hints[] = {&Width, &Interleave, &Force};
01078     for (auto H : Hints) {
01079       if (Name == H->Name) {
01080         if (H->validate(Val))
01081           H->Value = Val;
01082         else
01083           DEBUG(dbgs() << "LV: ignoring invalid hint '" << Name << "'\n");
01084         break;
01085       }
01086     }
01087   }
01088 
01089   /// Create a new hint from name / value pair.
01090   MDNode *createHintMetadata(StringRef Name, unsigned V) const {
01091     LLVMContext &Context = TheLoop->getHeader()->getContext();
01092     Metadata *MDs[] = {MDString::get(Context, Name),
01093                        ConstantAsMetadata::get(
01094                            ConstantInt::get(Type::getInt32Ty(Context), V))};
01095     return MDNode::get(Context, MDs);
01096   }
01097 
01098   /// Matches metadata with hint name.
01099   bool matchesHintMetadataName(MDNode *Node, ArrayRef<Hint> HintTypes) {
01100     MDString* Name = dyn_cast<MDString>(Node->getOperand(0));
01101     if (!Name)
01102       return false;
01103 
01104     for (auto H : HintTypes)
01105       if (Name->getString().endswith(H.Name))
01106         return true;
01107     return false;
01108   }
01109 
01110   /// Sets current hints into loop metadata, keeping other values intact.
01111   void writeHintsToMetadata(ArrayRef<Hint> HintTypes) {
01112     if (HintTypes.size() == 0)
01113       return;
01114 
01115     // Reserve the first element to LoopID (see below).
01116     SmallVector<Metadata *, 4> MDs(1);
01117     // If the loop already has metadata, then ignore the existing operands.
01118     MDNode *LoopID = TheLoop->getLoopID();
01119     if (LoopID) {
01120       for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
01121         MDNode *Node = cast<MDNode>(LoopID->getOperand(i));
01122         // If node in update list, ignore old value.
01123         if (!matchesHintMetadataName(Node, HintTypes))
01124           MDs.push_back(Node);
01125       }
01126     }
01127 
01128     // Now, add the missing hints.
01129     for (auto H : HintTypes)
01130       MDs.push_back(createHintMetadata(Twine(Prefix(), H.Name).str(), H.Value));
01131 
01132     // Replace current metadata node with new one.
01133     LLVMContext &Context = TheLoop->getHeader()->getContext();
01134     MDNode *NewLoopID = MDNode::get(Context, MDs);
01135     // Set operand 0 to refer to the loop id itself.
01136     NewLoopID->replaceOperandWith(0, NewLoopID);
01137 
01138     TheLoop->setLoopID(NewLoopID);
01139   }
01140 
01141   /// The loop these hints belong to.
01142   const Loop *TheLoop;
01143 };
01144 
01145 static void emitMissedWarning(Function *F, Loop *L,
01146                               const LoopVectorizeHints &LH) {
01147   emitOptimizationRemarkMissed(F->getContext(), DEBUG_TYPE, *F,
01148                                L->getStartLoc(), LH.emitRemark());
01149 
01150   if (LH.getForce() == LoopVectorizeHints::FK_Enabled) {
01151     if (LH.getWidth() != 1)
01152       emitLoopVectorizeWarning(
01153           F->getContext(), *F, L->getStartLoc(),
01154           "failed explicitly specified loop vectorization");
01155     else if (LH.getInterleave() != 1)
01156       emitLoopInterleaveWarning(
01157           F->getContext(), *F, L->getStartLoc(),
01158           "failed explicitly specified loop interleaving");
01159   }
01160 }
01161 
01162 static void addInnerLoop(Loop &L, SmallVectorImpl<Loop *> &V) {
01163   if (L.empty())
01164     return V.push_back(&L);
01165 
01166   for (Loop *InnerL : L)
01167     addInnerLoop(*InnerL, V);
01168 }
01169 
01170 /// The LoopVectorize Pass.
01171 struct LoopVectorize : public FunctionPass {
01172   /// Pass identification, replacement for typeid
01173   static char ID;
01174 
01175   explicit LoopVectorize(bool NoUnrolling = false, bool AlwaysVectorize = true)
01176     : FunctionPass(ID),
01177       DisableUnrolling(NoUnrolling),
01178       AlwaysVectorize(AlwaysVectorize) {
01179     initializeLoopVectorizePass(*PassRegistry::getPassRegistry());
01180   }
01181 
01182   ScalarEvolution *SE;
01183   LoopInfo *LI;
01184   TargetTransformInfo *TTI;
01185   DominatorTree *DT;
01186   BlockFrequencyInfo *BFI;
01187   TargetLibraryInfo *TLI;
01188   AliasAnalysis *AA;
01189   AssumptionCache *AC;
01190   LoopAccessAnalysis *LAA;
01191   bool DisableUnrolling;
01192   bool AlwaysVectorize;
01193 
01194   BlockFrequency ColdEntryFreq;
01195 
01196   bool runOnFunction(Function &F) override {
01197     SE = &getAnalysis<ScalarEvolution>();
01198     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
01199     TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
01200     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
01201     BFI = &getAnalysis<BlockFrequencyInfo>();
01202     auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
01203     TLI = TLIP ? &TLIP->getTLI() : nullptr;
01204     AA = &getAnalysis<AliasAnalysis>();
01205     AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
01206     LAA = &getAnalysis<LoopAccessAnalysis>();
01207 
01208     // Compute some weights outside of the loop over the loops. Compute this
01209     // using a BranchProbability to re-use its scaling math.
01210     const BranchProbability ColdProb(1, 5); // 20%
01211     ColdEntryFreq = BlockFrequency(BFI->getEntryFreq()) * ColdProb;
01212 
01213     // If the target claims to have no vector registers don't attempt
01214     // vectorization.
01215     if (!TTI->getNumberOfRegisters(true))
01216       return false;
01217 
01218     // Build up a worklist of inner-loops to vectorize. This is necessary as
01219     // the act of vectorizing or partially unrolling a loop creates new loops
01220     // and can invalidate iterators across the loops.
01221     SmallVector<Loop *, 8> Worklist;
01222 
01223     for (Loop *L : *LI)
01224       addInnerLoop(*L, Worklist);
01225 
01226     LoopsAnalyzed += Worklist.size();
01227 
01228     // Now walk the identified inner loops.
01229     bool Changed = false;
01230     while (!Worklist.empty())
01231       Changed |= processLoop(Worklist.pop_back_val());
01232 
01233     // Process each loop nest in the function.
01234     return Changed;
01235   }
01236 
01237   static void AddRuntimeUnrollDisableMetaData(Loop *L) {
01238     SmallVector<Metadata *, 4> MDs;
01239     // Reserve first location for self reference to the LoopID metadata node.
01240     MDs.push_back(nullptr);
01241     bool IsUnrollMetadata = false;
01242     MDNode *LoopID = L->getLoopID();
01243     if (LoopID) {
01244       // First find existing loop unrolling disable metadata.
01245       for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
01246         MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
01247         if (MD) {
01248           const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
01249           IsUnrollMetadata =
01250               S && S->getString().startswith("llvm.loop.unroll.disable");
01251         }
01252         MDs.push_back(LoopID->getOperand(i));
01253       }
01254     }
01255 
01256     if (!IsUnrollMetadata) {
01257       // Add runtime unroll disable metadata.
01258       LLVMContext &Context = L->getHeader()->getContext();
01259       SmallVector<Metadata *, 1> DisableOperands;
01260       DisableOperands.push_back(
01261           MDString::get(Context, "llvm.loop.unroll.runtime.disable"));
01262       MDNode *DisableNode = MDNode::get(Context, DisableOperands);
01263       MDs.push_back(DisableNode);
01264       MDNode *NewLoopID = MDNode::get(Context, MDs);
01265       // Set operand 0 to refer to the loop id itself.
01266       NewLoopID->replaceOperandWith(0, NewLoopID);
01267       L->setLoopID(NewLoopID);
01268     }
01269   }
01270 
01271   bool processLoop(Loop *L) {
01272     assert(L->empty() && "Only process inner loops.");
01273 
01274 #ifndef NDEBUG
01275     const std::string DebugLocStr = getDebugLocString(L);
01276 #endif /* NDEBUG */
01277 
01278     DEBUG(dbgs() << "\nLV: Checking a loop in \""
01279                  << L->getHeader()->getParent()->getName() << "\" from "
01280                  << DebugLocStr << "\n");
01281 
01282     LoopVectorizeHints Hints(L, DisableUnrolling);
01283 
01284     DEBUG(dbgs() << "LV: Loop hints:"
01285                  << " force="
01286                  << (Hints.getForce() == LoopVectorizeHints::FK_Disabled
01287                          ? "disabled"
01288                          : (Hints.getForce() == LoopVectorizeHints::FK_Enabled
01289                                 ? "enabled"
01290                                 : "?")) << " width=" << Hints.getWidth()
01291                  << " unroll=" << Hints.getInterleave() << "\n");
01292 
01293     // Function containing loop
01294     Function *F = L->getHeader()->getParent();
01295 
01296     // Looking at the diagnostic output is the only way to determine if a loop
01297     // was vectorized (other than looking at the IR or machine code), so it
01298     // is important to generate an optimization remark for each loop. Most of
01299     // these messages are generated by emitOptimizationRemarkAnalysis. Remarks
01300     // generated by emitOptimizationRemark and emitOptimizationRemarkMissed are
01301     // less verbose reporting vectorized loops and unvectorized loops that may
01302     // benefit from vectorization, respectively.
01303 
01304     if (Hints.getForce() == LoopVectorizeHints::FK_Disabled) {
01305       DEBUG(dbgs() << "LV: Not vectorizing: #pragma vectorize disable.\n");
01306       emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F,
01307                                      L->getStartLoc(), Hints.emitRemark());
01308       return false;
01309     }
01310 
01311     if (!AlwaysVectorize && Hints.getForce() != LoopVectorizeHints::FK_Enabled) {
01312       DEBUG(dbgs() << "LV: Not vectorizing: No #pragma vectorize enable.\n");
01313       emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F,
01314                                      L->getStartLoc(), Hints.emitRemark());
01315       return false;
01316     }
01317 
01318     if (Hints.getWidth() == 1 && Hints.getInterleave() == 1) {
01319       DEBUG(dbgs() << "LV: Not vectorizing: Disabled/already vectorized.\n");
01320       emitOptimizationRemarkAnalysis(
01321           F->getContext(), DEBUG_TYPE, *F, L->getStartLoc(),
01322           "loop not vectorized: vector width and interleave count are "
01323           "explicitly set to 1");
01324       return false;
01325     }
01326 
01327     // Check the loop for a trip count threshold:
01328     // do not vectorize loops with a tiny trip count.
01329     const unsigned TC = SE->getSmallConstantTripCount(L);
01330     if (TC > 0u && TC < TinyTripCountVectorThreshold) {
01331       DEBUG(dbgs() << "LV: Found a loop with a very small trip count. "
01332                    << "This loop is not worth vectorizing.");
01333       if (Hints.getForce() == LoopVectorizeHints::FK_Enabled)
01334         DEBUG(dbgs() << " But vectorizing was explicitly forced.\n");
01335       else {
01336         DEBUG(dbgs() << "\n");
01337         emitOptimizationRemarkAnalysis(
01338             F->getContext(), DEBUG_TYPE, *F, L->getStartLoc(),
01339             "vectorization is not beneficial and is not explicitly forced");
01340         return false;
01341       }
01342     }
01343 
01344     // Check if it is legal to vectorize the loop.
01345     LoopVectorizationLegality LVL(L, SE, DT, TLI, AA, F, TTI, LAA);
01346     if (!LVL.canVectorize()) {
01347       DEBUG(dbgs() << "LV: Not vectorizing: Cannot prove legality.\n");
01348       emitMissedWarning(F, L, Hints);
01349       return false;
01350     }
01351 
01352     // Use the cost model.
01353     LoopVectorizationCostModel CM(L, SE, LI, &LVL, *TTI, TLI, AC, F, &Hints);
01354 
01355     // Check the function attributes to find out if this function should be
01356     // optimized for size.
01357     bool OptForSize = Hints.getForce() != LoopVectorizeHints::FK_Enabled &&
01358                       F->hasFnAttribute(Attribute::OptimizeForSize);
01359 
01360     // Compute the weighted frequency of this loop being executed and see if it
01361     // is less than 20% of the function entry baseline frequency. Note that we
01362     // always have a canonical loop here because we think we *can* vectoriez.
01363     // FIXME: This is hidden behind a flag due to pervasive problems with
01364     // exactly what block frequency models.
01365     if (LoopVectorizeWithBlockFrequency) {
01366       BlockFrequency LoopEntryFreq = BFI->getBlockFreq(L->getLoopPreheader());
01367       if (Hints.getForce() != LoopVectorizeHints::FK_Enabled &&
01368           LoopEntryFreq < ColdEntryFreq)
01369         OptForSize = true;
01370     }
01371 
01372     // Check the function attributes to see if implicit floats are allowed.a
01373     // FIXME: This check doesn't seem possibly correct -- what if the loop is
01374     // an integer loop and the vector instructions selected are purely integer
01375     // vector instructions?
01376     if (F->hasFnAttribute(Attribute::NoImplicitFloat)) {
01377       DEBUG(dbgs() << "LV: Can't vectorize when the NoImplicitFloat"
01378             "attribute is used.\n");
01379       emitOptimizationRemarkAnalysis(
01380           F->getContext(), DEBUG_TYPE, *F, L->getStartLoc(),
01381           "loop not vectorized due to NoImplicitFloat attribute");
01382       emitMissedWarning(F, L, Hints);
01383       return false;
01384     }
01385 
01386     // Select the optimal vectorization factor.
01387     const LoopVectorizationCostModel::VectorizationFactor VF =
01388         CM.selectVectorizationFactor(OptForSize);
01389 
01390     // Select the unroll factor.
01391     const unsigned UF =
01392         CM.selectUnrollFactor(OptForSize, VF.Width, VF.Cost);
01393 
01394     DEBUG(dbgs() << "LV: Found a vectorizable loop (" << VF.Width << ") in "
01395                  << DebugLocStr << '\n');
01396     DEBUG(dbgs() << "LV: Unroll Factor is " << UF << '\n');
01397 
01398     if (VF.Width == 1) {
01399       DEBUG(dbgs() << "LV: Vectorization is possible but not beneficial\n");
01400 
01401       if (UF == 1) {
01402         emitOptimizationRemarkAnalysis(
01403             F->getContext(), DEBUG_TYPE, *F, L->getStartLoc(),
01404             "not beneficial to vectorize and user disabled interleaving");
01405         return false;
01406       }
01407       DEBUG(dbgs() << "LV: Trying to at least unroll the loops.\n");
01408 
01409       // Report the unrolling decision.
01410       emitOptimizationRemark(F->getContext(), DEBUG_TYPE, *F, L->getStartLoc(),
01411                              Twine("unrolled with interleaving factor " +
01412                                    Twine(UF) +
01413                                    " (vectorization not beneficial)"));
01414 
01415       // We decided not to vectorize, but we may want to unroll.
01416 
01417       InnerLoopUnroller Unroller(L, SE, LI, DT, TLI, TTI, UF);
01418       Unroller.vectorize(&LVL);
01419     } else {
01420       // If we decided that it is *legal* to vectorize the loop then do it.
01421       InnerLoopVectorizer LB(L, SE, LI, DT, TLI, TTI, VF.Width, UF);
01422       LB.vectorize(&LVL);
01423       ++LoopsVectorized;
01424 
01425       // Add metadata to disable runtime unrolling scalar loop when there's no
01426       // runtime check about strides and memory. Because at this situation,
01427       // scalar loop is rarely used not worthy to be unrolled.
01428       if (!LB.IsSafetyChecksAdded())
01429         AddRuntimeUnrollDisableMetaData(L);
01430 
01431       // Report the vectorization decision.
01432       emitOptimizationRemark(
01433           F->getContext(), DEBUG_TYPE, *F, L->getStartLoc(),
01434           Twine("vectorized loop (vectorization factor: ") + Twine(VF.Width) +
01435               ", unrolling interleave factor: " + Twine(UF) + ")");
01436     }
01437 
01438     // Mark the loop as already vectorized to avoid vectorizing again.
01439     Hints.setAlreadyVectorized();
01440 
01441     DEBUG(verifyFunction(*L->getHeader()->getParent()));
01442     return true;
01443   }
01444 
01445   void getAnalysisUsage(AnalysisUsage &AU) const override {
01446     AU.addRequired<AssumptionCacheTracker>();
01447     AU.addRequiredID(LoopSimplifyID);
01448     AU.addRequiredID(LCSSAID);
01449     AU.addRequired<BlockFrequencyInfo>();
01450     AU.addRequired<DominatorTreeWrapperPass>();
01451     AU.addRequired<LoopInfoWrapperPass>();
01452     AU.addRequired<ScalarEvolution>();
01453     AU.addRequired<TargetTransformInfoWrapperPass>();
01454     AU.addRequired<AliasAnalysis>();
01455     AU.addRequired<LoopAccessAnalysis>();
01456     AU.addPreserved<LoopInfoWrapperPass>();
01457     AU.addPreserved<DominatorTreeWrapperPass>();
01458     AU.addPreserved<AliasAnalysis>();
01459   }
01460 
01461 };
01462 
01463 } // end anonymous namespace
01464 
01465 //===----------------------------------------------------------------------===//
01466 // Implementation of LoopVectorizationLegality, InnerLoopVectorizer and
01467 // LoopVectorizationCostModel.
01468 //===----------------------------------------------------------------------===//
01469 
01470 Value *InnerLoopVectorizer::getBroadcastInstrs(Value *V) {
01471   // We need to place the broadcast of invariant variables outside the loop.
01472   Instruction *Instr = dyn_cast<Instruction>(V);
01473   bool NewInstr =
01474       (Instr && std::find(LoopVectorBody.begin(), LoopVectorBody.end(),
01475                           Instr->getParent()) != LoopVectorBody.end());
01476   bool Invariant = OrigLoop->isLoopInvariant(V) && !NewInstr;
01477 
01478   // Place the code for broadcasting invariant variables in the new preheader.
01479   IRBuilder<>::InsertPointGuard Guard(Builder);
01480   if (Invariant)
01481     Builder.SetInsertPoint(LoopVectorPreHeader->getTerminator());
01482 
01483   // Broadcast the scalar into all locations in the vector.
01484   Value *Shuf = Builder.CreateVectorSplat(VF, V, "broadcast");
01485 
01486   return Shuf;
01487 }
01488 
01489 Value *InnerLoopVectorizer::getStepVector(Value *Val, int StartIdx,
01490                                           Value *Step) {
01491   assert(Val->getType()->isVectorTy() && "Must be a vector");
01492   assert(Val->getType()->getScalarType()->isIntegerTy() &&
01493          "Elem must be an integer");
01494   assert(Step->getType() == Val->getType()->getScalarType() &&
01495          "Step has wrong type");
01496   // Create the types.
01497   Type *ITy = Val->getType()->getScalarType();
01498   VectorType *Ty = cast<VectorType>(Val->getType());
01499   int VLen = Ty->getNumElements();
01500   SmallVector<Constant*, 8> Indices;
01501 
01502   // Create a vector of consecutive numbers from zero to VF.
01503   for (int i = 0; i < VLen; ++i)
01504     Indices.push_back(ConstantInt::get(ITy, StartIdx + i));
01505 
01506   // Add the consecutive indices to the vector value.
01507   Constant *Cv = ConstantVector::get(Indices);
01508   assert(Cv->getType() == Val->getType() && "Invalid consecutive vec");
01509   Step = Builder.CreateVectorSplat(VLen, Step);
01510   assert(Step->getType() == Val->getType() && "Invalid step vec");
01511   // FIXME: The newly created binary instructions should contain nsw/nuw flags,
01512   // which can be found from the original scalar operations.
01513   Step = Builder.CreateMul(Cv, Step);
01514   return Builder.CreateAdd(Val, Step, "induction");
01515 }
01516 
01517 /// \brief Find the operand of the GEP that should be checked for consecutive
01518 /// stores. This ignores trailing indices that have no effect on the final
01519 /// pointer.
01520 static unsigned getGEPInductionOperand(const GetElementPtrInst *Gep) {
01521   const DataLayout &DL = Gep->getModule()->getDataLayout();
01522   unsigned LastOperand = Gep->getNumOperands() - 1;
01523   unsigned GEPAllocSize = DL.getTypeAllocSize(
01524       cast<PointerType>(Gep->getType()->getScalarType())->getElementType());
01525 
01526   // Walk backwards and try to peel off zeros.
01527   while (LastOperand > 1 && match(Gep->getOperand(LastOperand), m_Zero())) {
01528     // Find the type we're currently indexing into.
01529     gep_type_iterator GEPTI = gep_type_begin(Gep);
01530     std::advance(GEPTI, LastOperand - 1);
01531 
01532     // If it's a type with the same allocation size as the result of the GEP we
01533     // can peel off the zero index.
01534     if (DL.getTypeAllocSize(*GEPTI) != GEPAllocSize)
01535       break;
01536     --LastOperand;
01537   }
01538 
01539   return LastOperand;
01540 }
01541 
01542 int LoopVectorizationLegality::isConsecutivePtr(Value *Ptr) {
01543   assert(Ptr->getType()->isPointerTy() && "Unexpected non-ptr");
01544   // Make sure that the pointer does not point to structs.
01545   if (Ptr->getType()->getPointerElementType()->isAggregateType())
01546     return 0;
01547 
01548   // If this value is a pointer induction variable we know it is consecutive.
01549   PHINode *Phi = dyn_cast_or_null<PHINode>(Ptr);
01550   if (Phi && Inductions.count(Phi)) {
01551     InductionInfo II = Inductions[Phi];
01552     return II.getConsecutiveDirection();
01553   }
01554 
01555   GetElementPtrInst *Gep = dyn_cast_or_null<GetElementPtrInst>(Ptr);
01556   if (!Gep)
01557     return 0;
01558 
01559   unsigned NumOperands = Gep->getNumOperands();
01560   Value *GpPtr = Gep->getPointerOperand();
01561   // If this GEP value is a consecutive pointer induction variable and all of
01562   // the indices are constant then we know it is consecutive. We can
01563   Phi = dyn_cast<PHINode>(GpPtr);
01564   if (Phi && Inductions.count(Phi)) {
01565 
01566     // Make sure that the pointer does not point to structs.
01567     PointerType *GepPtrType = cast<PointerType>(GpPtr->getType());
01568     if (GepPtrType->getElementType()->isAggregateType())
01569       return 0;
01570 
01571     // Make sure that all of the index operands are loop invariant.
01572     for (unsigned i = 1; i < NumOperands; ++i)
01573       if (!SE->isLoopInvariant(SE->getSCEV(Gep->getOperand(i)), TheLoop))
01574         return 0;
01575 
01576     InductionInfo II = Inductions[Phi];
01577     return II.getConsecutiveDirection();
01578   }
01579 
01580   unsigned InductionOperand = getGEPInductionOperand(Gep);
01581 
01582   // Check that all of the gep indices are uniform except for our induction
01583   // operand.
01584   for (unsigned i = 0; i != NumOperands; ++i)
01585     if (i != InductionOperand &&
01586         !SE->isLoopInvariant(SE->getSCEV(Gep->getOperand(i)), TheLoop))
01587       return 0;
01588 
01589   // We can emit wide load/stores only if the last non-zero index is the
01590   // induction variable.
01591   const SCEV *Last = nullptr;
01592   if (!Strides.count(Gep))
01593     Last = SE->getSCEV(Gep->getOperand(InductionOperand));
01594   else {
01595     // Because of the multiplication by a stride we can have a s/zext cast.
01596     // We are going to replace this stride by 1 so the cast is safe to ignore.
01597     //
01598     //  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
01599     //  %0 = trunc i64 %indvars.iv to i32
01600     //  %mul = mul i32 %0, %Stride1
01601     //  %idxprom = zext i32 %mul to i64  << Safe cast.
01602     //  %arrayidx = getelementptr inbounds i32* %B, i64 %idxprom
01603     //
01604     Last = replaceSymbolicStrideSCEV(SE, Strides,
01605                                      Gep->getOperand(InductionOperand), Gep);
01606     if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(Last))
01607       Last =
01608           (C->getSCEVType() == scSignExtend || C->getSCEVType() == scZeroExtend)
01609               ? C->getOperand()
01610               : Last;
01611   }
01612   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Last)) {
01613     const SCEV *Step = AR->getStepRecurrence(*SE);
01614 
01615     // The memory is consecutive because the last index is consecutive
01616     // and all other indices are loop invariant.
01617     if (Step->isOne())
01618       return 1;
01619     if (Step->isAllOnesValue())
01620       return -1;
01621   }
01622 
01623   return 0;
01624 }
01625 
01626 bool LoopVectorizationLegality::isUniform(Value *V) {
01627   return LAI->isUniform(V);
01628 }
01629 
01630 InnerLoopVectorizer::VectorParts&
01631 InnerLoopVectorizer::getVectorValue(Value *V) {
01632   assert(V != Induction && "The new induction variable should not be used.");
01633   assert(!V->getType()->isVectorTy() && "Can't widen a vector");
01634 
01635   // If we have a stride that is replaced by one, do it here.
01636   if (Legal->hasStride(V))
01637     V = ConstantInt::get(V->getType(), 1);
01638 
01639   // If we have this scalar in the map, return it.
01640   if (WidenMap.has(V))
01641     return WidenMap.get(V);
01642 
01643   // If this scalar is unknown, assume that it is a constant or that it is
01644   // loop invariant. Broadcast V and save the value for future uses.
01645   Value *B = getBroadcastInstrs(V);
01646   return WidenMap.splat(V, B);
01647 }
01648 
01649 Value *InnerLoopVectorizer::reverseVector(Value *Vec) {
01650   assert(Vec->getType()->isVectorTy() && "Invalid type");
01651   SmallVector<Constant*, 8> ShuffleMask;
01652   for (unsigned i = 0; i < VF; ++i)
01653     ShuffleMask.push_back(Builder.getInt32(VF - i - 1));
01654 
01655   return Builder.CreateShuffleVector(Vec, UndefValue::get(Vec->getType()),
01656                                      ConstantVector::get(ShuffleMask),
01657                                      "reverse");
01658 }
01659 
01660 void InnerLoopVectorizer::vectorizeMemoryInstruction(Instruction *Instr) {
01661   // Attempt to issue a wide load.
01662   LoadInst *LI = dyn_cast<LoadInst>(Instr);
01663   StoreInst *SI = dyn_cast<StoreInst>(Instr);
01664 
01665   assert((LI || SI) && "Invalid Load/Store instruction");
01666 
01667   Type *ScalarDataTy = LI ? LI->getType() : SI->getValueOperand()->getType();
01668   Type *DataTy = VectorType::get(ScalarDataTy, VF);
01669   Value *Ptr = LI ? LI->getPointerOperand() : SI->getPointerOperand();
01670   unsigned Alignment = LI ? LI->getAlignment() : SI->getAlignment();
01671   // An alignment of 0 means target abi alignment. We need to use the scalar's
01672   // target abi alignment in such a case.
01673   const DataLayout &DL = Instr->getModule()->getDataLayout();
01674   if (!Alignment)
01675     Alignment = DL.getABITypeAlignment(ScalarDataTy);
01676   unsigned AddressSpace = Ptr->getType()->getPointerAddressSpace();
01677   unsigned ScalarAllocatedSize = DL.getTypeAllocSize(ScalarDataTy);
01678   unsigned VectorElementSize = DL.getTypeStoreSize(DataTy) / VF;
01679 
01680   if (SI && Legal->blockNeedsPredication(SI->getParent()) &&
01681       !Legal->isMaskRequired(SI))
01682     return scalarizeInstruction(Instr, true);
01683 
01684   if (ScalarAllocatedSize != VectorElementSize)
01685     return scalarizeInstruction(Instr);
01686 
01687   // If the pointer is loop invariant or if it is non-consecutive,
01688   // scalarize the load.
01689   int ConsecutiveStride = Legal->isConsecutivePtr(Ptr);
01690   bool Reverse = ConsecutiveStride < 0;
01691   bool UniformLoad = LI && Legal->isUniform(Ptr);
01692   if (!ConsecutiveStride || UniformLoad)
01693     return scalarizeInstruction(Instr);
01694 
01695   Constant *Zero = Builder.getInt32(0);
01696   VectorParts &Entry = WidenMap.get(Instr);
01697 
01698   // Handle consecutive loads/stores.
01699   GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr);
01700   if (Gep && Legal->isInductionVariable(Gep->getPointerOperand())) {
01701     setDebugLocFromInst(Builder, Gep);
01702     Value *PtrOperand = Gep->getPointerOperand();
01703     Value *FirstBasePtr = getVectorValue(PtrOperand)[0];
01704     FirstBasePtr = Builder.CreateExtractElement(FirstBasePtr, Zero);
01705 
01706     // Create the new GEP with the new induction variable.
01707     GetElementPtrInst *Gep2 = cast<GetElementPtrInst>(Gep->clone());
01708     Gep2->setOperand(0, FirstBasePtr);
01709     Gep2->setName("gep.indvar.base");
01710     Ptr = Builder.Insert(Gep2);
01711   } else if (Gep) {
01712     setDebugLocFromInst(Builder, Gep);
01713     assert(SE->isLoopInvariant(SE->getSCEV(Gep->getPointerOperand()),
01714                                OrigLoop) && "Base ptr must be invariant");
01715 
01716     // The last index does not have to be the induction. It can be
01717     // consecutive and be a function of the index. For example A[I+1];
01718     unsigned NumOperands = Gep->getNumOperands();
01719     unsigned InductionOperand = getGEPInductionOperand(Gep);
01720     // Create the new GEP with the new induction variable.
01721     GetElementPtrInst *Gep2 = cast<GetElementPtrInst>(Gep->clone());
01722 
01723     for (unsigned i = 0; i < NumOperands; ++i) {
01724       Value *GepOperand = Gep->getOperand(i);
01725       Instruction *GepOperandInst = dyn_cast<Instruction>(GepOperand);
01726 
01727       // Update last index or loop invariant instruction anchored in loop.
01728       if (i == InductionOperand ||
01729           (GepOperandInst && OrigLoop->contains(GepOperandInst))) {
01730         assert((i == InductionOperand ||
01731                SE->isLoopInvariant(SE->getSCEV(GepOperandInst), OrigLoop)) &&
01732                "Must be last index or loop invariant");
01733 
01734         VectorParts &GEPParts = getVectorValue(GepOperand);
01735         Value *Index = GEPParts[0];
01736         Index = Builder.CreateExtractElement(Index, Zero);
01737         Gep2->setOperand(i, Index);
01738         Gep2->setName("gep.indvar.idx");
01739       }
01740     }
01741     Ptr = Builder.Insert(Gep2);
01742   } else {
01743     // Use the induction element ptr.
01744     assert(isa<PHINode>(Ptr) && "Invalid induction ptr");
01745     setDebugLocFromInst(Builder, Ptr);
01746     VectorParts &PtrVal = getVectorValue(Ptr);
01747     Ptr = Builder.CreateExtractElement(PtrVal[0], Zero);
01748   }
01749 
01750   VectorParts Mask = createBlockInMask(Instr->getParent());
01751   // Handle Stores:
01752   if (SI) {
01753     assert(!Legal->isUniform(SI->getPointerOperand()) &&
01754            "We do not allow storing to uniform addresses");
01755     setDebugLocFromInst(Builder, SI);
01756     // We don't want to update the value in the map as it might be used in
01757     // another expression. So don't use a reference type for "StoredVal".
01758     VectorParts StoredVal = getVectorValue(SI->getValueOperand());
01759     
01760     for (unsigned Part = 0; Part < UF; ++Part) {
01761       // Calculate the pointer for the specific unroll-part.
01762       Value *PartPtr =
01763           Builder.CreateGEP(nullptr, Ptr, Builder.getInt32(Part * VF));
01764 
01765       if (Reverse) {
01766         // If we store to reverse consecutive memory locations then we need
01767         // to reverse the order of elements in the stored value.
01768         StoredVal[Part] = reverseVector(StoredVal[Part]);
01769         // If the address is consecutive but reversed, then the
01770         // wide store needs to start at the last vector element.
01771         PartPtr = Builder.CreateGEP(nullptr, Ptr, Builder.getInt32(-Part * VF));
01772         PartPtr = Builder.CreateGEP(nullptr, PartPtr, Builder.getInt32(1 - VF));
01773         Mask[Part] = reverseVector(Mask[Part]);
01774       }
01775 
01776       Value *VecPtr = Builder.CreateBitCast(PartPtr,
01777                                             DataTy->getPointerTo(AddressSpace));
01778 
01779       Instruction *NewSI;
01780       if (Legal->isMaskRequired(SI))
01781         NewSI = Builder.CreateMaskedStore(StoredVal[Part], VecPtr, Alignment,
01782                                           Mask[Part]);
01783       else 
01784         NewSI = Builder.CreateAlignedStore(StoredVal[Part], VecPtr, Alignment);
01785       propagateMetadata(NewSI, SI);
01786     }
01787     return;
01788   }
01789 
01790   // Handle loads.
01791   assert(LI && "Must have a load instruction");
01792   setDebugLocFromInst(Builder, LI);
01793   for (unsigned Part = 0; Part < UF; ++Part) {
01794     // Calculate the pointer for the specific unroll-part.
01795     Value *PartPtr =
01796         Builder.CreateGEP(nullptr, Ptr, Builder.getInt32(Part * VF));
01797 
01798     if (Reverse) {
01799       // If the address is consecutive but reversed, then the
01800       // wide load needs to start at the last vector element.
01801       PartPtr = Builder.CreateGEP(nullptr, Ptr, Builder.getInt32(-Part * VF));
01802       PartPtr = Builder.CreateGEP(nullptr, PartPtr, Builder.getInt32(1 - VF));
01803       Mask[Part] = reverseVector(Mask[Part]);
01804     }
01805 
01806     Instruction* NewLI;
01807     Value *VecPtr = Builder.CreateBitCast(PartPtr,
01808                                           DataTy->getPointerTo(AddressSpace));
01809     if (Legal->isMaskRequired(LI))
01810       NewLI = Builder.CreateMaskedLoad(VecPtr, Alignment, Mask[Part],
01811                                        UndefValue::get(DataTy),
01812                                        "wide.masked.load");
01813     else
01814       NewLI = Builder.CreateAlignedLoad(VecPtr, Alignment, "wide.load");
01815     propagateMetadata(NewLI, LI);
01816     Entry[Part] = Reverse ? reverseVector(NewLI) :  NewLI;
01817   }
01818 }
01819 
01820 void InnerLoopVectorizer::scalarizeInstruction(Instruction *Instr, bool IfPredicateStore) {
01821   assert(!Instr->getType()->isAggregateType() && "Can't handle vectors");
01822   // Holds vector parameters or scalars, in case of uniform vals.
01823   SmallVector<VectorParts, 4> Params;
01824 
01825   setDebugLocFromInst(Builder, Instr);
01826 
01827   // Find all of the vectorized parameters.
01828   for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) {
01829     Value *SrcOp = Instr->getOperand(op);
01830 
01831     // If we are accessing the old induction variable, use the new one.
01832     if (SrcOp == OldInduction) {
01833       Params.push_back(getVectorValue(SrcOp));
01834       continue;
01835     }
01836 
01837     // Try using previously calculated values.
01838     Instruction *SrcInst = dyn_cast<Instruction>(SrcOp);
01839 
01840     // If the src is an instruction that appeared earlier in the basic block
01841     // then it should already be vectorized.
01842     if (SrcInst && OrigLoop->contains(SrcInst)) {
01843       assert(WidenMap.has(SrcInst) && "Source operand is unavailable");
01844       // The parameter is a vector value from earlier.
01845       Params.push_back(WidenMap.get(SrcInst));
01846     } else {
01847       // The parameter is a scalar from outside the loop. Maybe even a constant.
01848       VectorParts Scalars;
01849       Scalars.append(UF, SrcOp);
01850       Params.push_back(Scalars);
01851     }
01852   }
01853 
01854   assert(Params.size() == Instr->getNumOperands() &&
01855          "Invalid number of operands");
01856 
01857   // Does this instruction return a value ?
01858   bool IsVoidRetTy = Instr->getType()->isVoidTy();
01859 
01860   Value *UndefVec = IsVoidRetTy ? nullptr :
01861     UndefValue::get(VectorType::get(Instr->getType(), VF));
01862   // Create a new entry in the WidenMap and initialize it to Undef or Null.
01863   VectorParts &VecResults = WidenMap.splat(Instr, UndefVec);
01864 
01865   Instruction *InsertPt = Builder.GetInsertPoint();
01866   BasicBlock *IfBlock = Builder.GetInsertBlock();
01867   BasicBlock *CondBlock = nullptr;
01868 
01869   VectorParts Cond;
01870   Loop *VectorLp = nullptr;
01871   if (IfPredicateStore) {
01872     assert(Instr->getParent()->getSinglePredecessor() &&
01873            "Only support single predecessor blocks");
01874     Cond = createEdgeMask(Instr->getParent()->getSinglePredecessor(),
01875                           Instr->getParent());
01876     VectorLp = LI->getLoopFor(IfBlock);
01877     assert(VectorLp && "Must have a loop for this block");
01878   }
01879 
01880   // For each vector unroll 'part':
01881   for (unsigned Part = 0; Part < UF; ++Part) {
01882     // For each scalar that we create:
01883     for (unsigned Width = 0; Width < VF; ++Width) {
01884 
01885       // Start if-block.
01886       Value *Cmp = nullptr;
01887       if (IfPredicateStore) {
01888         Cmp = Builder.CreateExtractElement(Cond[Part], Builder.getInt32(Width));
01889         Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Cmp, ConstantInt::get(Cmp->getType(), 1));
01890         CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.store");
01891         LoopVectorBody.push_back(CondBlock);
01892         VectorLp->addBasicBlockToLoop(CondBlock, *LI);
01893         // Update Builder with newly created basic block.
01894         Builder.SetInsertPoint(InsertPt);
01895       }
01896 
01897       Instruction *Cloned = Instr->clone();
01898       if (!IsVoidRetTy)
01899         Cloned->setName(Instr->getName() + ".cloned");
01900       // Replace the operands of the cloned instructions with extracted scalars.
01901       for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) {
01902         Value *Op = Params[op][Part];
01903         // Param is a vector. Need to extract the right lane.
01904         if (Op->getType()->isVectorTy())
01905           Op = Builder.CreateExtractElement(Op, Builder.getInt32(Width));
01906         Cloned->setOperand(op, Op);
01907       }
01908 
01909       // Place the cloned scalar in the new loop.
01910       Builder.Insert(Cloned);
01911 
01912       // If the original scalar returns a value we need to place it in a vector
01913       // so that future users will be able to use it.
01914       if (!IsVoidRetTy)
01915         VecResults[Part] = Builder.CreateInsertElement(VecResults[Part], Cloned,
01916                                                        Builder.getInt32(Width));
01917       // End if-block.
01918       if (IfPredicateStore) {
01919          BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else");
01920          LoopVectorBody.push_back(NewIfBlock);
01921          VectorLp->addBasicBlockToLoop(NewIfBlock, *LI);
01922          Builder.SetInsertPoint(InsertPt);
01923          Instruction *OldBr = IfBlock->getTerminator();
01924          BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
01925          OldBr->eraseFromParent();
01926          IfBlock = NewIfBlock;
01927       }
01928     }
01929   }
01930 }
01931 
01932 static Instruction *getFirstInst(Instruction *FirstInst, Value *V,
01933                                  Instruction *Loc) {
01934   if (FirstInst)
01935     return FirstInst;
01936   if (Instruction *I = dyn_cast<Instruction>(V))
01937     return I->getParent() == Loc->getParent() ? I : nullptr;
01938   return nullptr;
01939 }
01940 
01941 std::pair<Instruction *, Instruction *>
01942 InnerLoopVectorizer::addStrideCheck(Instruction *Loc) {
01943   Instruction *tnullptr = nullptr;
01944   if (!Legal->mustCheckStrides())
01945     return std::pair<Instruction *, Instruction *>(tnullptr, tnullptr);
01946 
01947   IRBuilder<> ChkBuilder(Loc);
01948 
01949   // Emit checks.
01950   Value *Check = nullptr;
01951   Instruction *FirstInst = nullptr;
01952   for (SmallPtrSet<Value *, 8>::iterator SI = Legal->strides_begin(),
01953                                          SE = Legal->strides_end();
01954        SI != SE; ++SI) {
01955     Value *Ptr = stripIntegerCast(*SI);
01956     Value *C = ChkBuilder.CreateICmpNE(Ptr, ConstantInt::get(Ptr->getType(), 1),
01957                                        "stride.chk");
01958     // Store the first instruction we create.
01959     FirstInst = getFirstInst(FirstInst, C, Loc);
01960     if (Check)
01961       Check = ChkBuilder.CreateOr(Check, C);
01962     else
01963       Check = C;
01964   }
01965 
01966   // We have to do this trickery because the IRBuilder might fold the check to a
01967   // constant expression in which case there is no Instruction anchored in a
01968   // the block.
01969   LLVMContext &Ctx = Loc->getContext();
01970   Instruction *TheCheck =
01971       BinaryOperator::CreateAnd(Check, ConstantInt::getTrue(Ctx));
01972   ChkBuilder.Insert(TheCheck, "stride.not.one");
01973   FirstInst = getFirstInst(FirstInst, TheCheck, Loc);
01974 
01975   return std::make_pair(FirstInst, TheCheck);
01976 }
01977 
01978 void InnerLoopVectorizer::createEmptyLoop() {
01979   /*
01980    In this function we generate a new loop. The new loop will contain
01981    the vectorized instructions while the old loop will continue to run the
01982    scalar remainder.
01983 
01984        [ ] <-- Back-edge taken count overflow check.
01985     /   |
01986    /    v
01987   |    [ ] <-- vector loop bypass (may consist of multiple blocks).
01988   |  /  |
01989   | /   v
01990   ||   [ ]     <-- vector pre header.
01991   ||    |
01992   ||    v
01993   ||   [  ] \
01994   ||   [  ]_|   <-- vector loop.
01995   ||    |
01996   | \   v
01997   |   >[ ]   <--- middle-block.
01998   |  /  |
01999   | /   v
02000   -|- >[ ]     <--- new preheader.
02001    |    |
02002    |    v
02003    |   [ ] \
02004    |   [ ]_|   <-- old scalar loop to handle remainder.
02005     \   |
02006      \  v
02007       >[ ]     <-- exit block.
02008    ...
02009    */
02010 
02011   BasicBlock *OldBasicBlock = OrigLoop->getHeader();
02012   BasicBlock *BypassBlock = OrigLoop->getLoopPreheader();
02013   BasicBlock *ExitBlock = OrigLoop->getExitBlock();
02014   assert(BypassBlock && "Invalid loop structure");
02015   assert(ExitBlock && "Must have an exit block");
02016 
02017   // Some loops have a single integer induction variable, while other loops
02018   // don't. One example is c++ iterators that often have multiple pointer
02019   // induction variables. In the code below we also support a case where we
02020   // don't have a single induction variable.
02021   OldInduction = Legal->getInduction();
02022   Type *IdxTy = Legal->getWidestInductionType();
02023 
02024   // Find the loop boundaries.
02025   const SCEV *ExitCount = SE->getBackedgeTakenCount(OrigLoop);
02026   assert(ExitCount != SE->getCouldNotCompute() && "Invalid loop count");
02027 
02028   // The exit count might have the type of i64 while the phi is i32. This can
02029   // happen if we have an induction variable that is sign extended before the
02030   // compare. The only way that we get a backedge taken count is that the
02031   // induction variable was signed and as such will not overflow. In such a case
02032   // truncation is legal.
02033   if (ExitCount->getType()->getPrimitiveSizeInBits() >
02034       IdxTy->getPrimitiveSizeInBits())
02035     ExitCount = SE->getTruncateOrNoop(ExitCount, IdxTy);
02036 
02037   const SCEV *BackedgeTakeCount = SE->getNoopOrZeroExtend(ExitCount, IdxTy);
02038   // Get the total trip count from the count by adding 1.
02039   ExitCount = SE->getAddExpr(BackedgeTakeCount,
02040                              SE->getConstant(BackedgeTakeCount->getType(), 1));
02041 
02042   const DataLayout &DL = OldBasicBlock->getModule()->getDataLayout();
02043 
02044   // Expand the trip count and place the new instructions in the preheader.
02045   // Notice that the pre-header does not change, only the loop body.
02046   SCEVExpander Exp(*SE, DL, "induction");
02047 
02048   // We need to test whether the backedge-taken count is uint##_max. Adding one
02049   // to it will cause overflow and an incorrect loop trip count in the vector
02050   // body. In case of overflow we want to directly jump to the scalar remainder
02051   // loop.
02052   Value *BackedgeCount =
02053       Exp.expandCodeFor(BackedgeTakeCount, BackedgeTakeCount->getType(),
02054                         BypassBlock->getTerminator());
02055   if (BackedgeCount->getType()->isPointerTy())
02056     BackedgeCount = CastInst::CreatePointerCast(BackedgeCount, IdxTy,
02057                                                 "backedge.ptrcnt.to.int",
02058                                                 BypassBlock->getTerminator());
02059   Instruction *CheckBCOverflow =
02060       CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, BackedgeCount,
02061                       Constant::getAllOnesValue(BackedgeCount->getType()),
02062                       "backedge.overflow", BypassBlock->getTerminator());
02063 
02064   // The loop index does not have to start at Zero. Find the original start
02065   // value from the induction PHI node. If we don't have an induction variable
02066   // then we know that it starts at zero.
02067   Builder.SetInsertPoint(BypassBlock->getTerminator());
02068   Value *StartIdx = ExtendedIdx = OldInduction ?
02069     Builder.CreateZExt(OldInduction->getIncomingValueForBlock(BypassBlock),
02070                        IdxTy):
02071     ConstantInt::get(IdxTy, 0);
02072 
02073   // We need an instruction to anchor the overflow check on. StartIdx needs to
02074   // be defined before the overflow check branch. Because the scalar preheader
02075   // is going to merge the start index and so the overflow branch block needs to
02076   // contain a definition of the start index.
02077   Instruction *OverflowCheckAnchor = BinaryOperator::CreateAdd(
02078       StartIdx, ConstantInt::get(IdxTy, 0), "overflow.check.anchor",
02079       BypassBlock->getTerminator());
02080 
02081   // Count holds the overall loop count (N).
02082   Value *Count = Exp.expandCodeFor(ExitCount, ExitCount->getType(),
02083                                    BypassBlock->getTerminator());
02084 
02085   LoopBypassBlocks.push_back(BypassBlock);
02086 
02087   // Split the single block loop into the two loop structure described above.
02088   BasicBlock *VectorPH =
02089   BypassBlock->splitBasicBlock(BypassBlock->getTerminator(), "vector.ph");
02090   BasicBlock *VecBody =
02091   VectorPH->splitBasicBlock(VectorPH->getTerminator(), "vector.body");
02092   BasicBlock *MiddleBlock =
02093   VecBody->splitBasicBlock(VecBody->getTerminator(), "middle.block");
02094   BasicBlock *ScalarPH =
02095   MiddleBlock->splitBasicBlock(MiddleBlock->getTerminator(), "scalar.ph");
02096 
02097   // Create and register the new vector loop.
02098   Loop* Lp = new Loop();
02099   Loop *ParentLoop = OrigLoop->getParentLoop();
02100 
02101   // Insert the new loop into the loop nest and register the new basic blocks
02102   // before calling any utilities such as SCEV that require valid LoopInfo.
02103   if (ParentLoop) {
02104     ParentLoop->addChildLoop(Lp);
02105     ParentLoop->addBasicBlockToLoop(ScalarPH, *LI);
02106     ParentLoop->addBasicBlockToLoop(VectorPH, *LI);
02107     ParentLoop->addBasicBlockToLoop(MiddleBlock, *LI);
02108   } else {
02109     LI->addTopLevelLoop(Lp);
02110   }
02111   Lp->addBasicBlockToLoop(VecBody, *LI);
02112 
02113   // Use this IR builder to create the loop instructions (Phi, Br, Cmp)
02114   // inside the loop.
02115   Builder.SetInsertPoint(VecBody->getFirstNonPHI());
02116 
02117   // Generate the induction variable.
02118   setDebugLocFromInst(Builder, getDebugLocFromInstOrOperands(OldInduction));
02119   Induction = Builder.CreatePHI(IdxTy, 2, "index");
02120   // The loop step is equal to the vectorization factor (num of SIMD elements)
02121   // times the unroll factor (num of SIMD instructions).
02122   Constant *Step = ConstantInt::get(IdxTy, VF * UF);
02123 
02124   // This is the IR builder that we use to add all of the logic for bypassing
02125   // the new vector loop.
02126   IRBuilder<> BypassBuilder(BypassBlock->getTerminator());
02127   setDebugLocFromInst(BypassBuilder,
02128                       getDebugLocFromInstOrOperands(OldInduction));
02129 
02130   // We may need to extend the index in case there is a type mismatch.
02131   // We know that the count starts at zero and does not overflow.
02132   if (Count->getType() != IdxTy) {
02133     // The exit count can be of pointer type. Convert it to the correct
02134     // integer type.
02135     if (ExitCount->getType()->isPointerTy())
02136       Count = BypassBuilder.CreatePointerCast(Count, IdxTy, "ptrcnt.to.int");
02137     else
02138       Count = BypassBuilder.CreateZExtOrTrunc(Count, IdxTy, "cnt.cast");
02139   }
02140 
02141   // Add the start index to the loop count to get the new end index.
02142   Value *IdxEnd = BypassBuilder.CreateAdd(Count, StartIdx, "end.idx");
02143 
02144   // Now we need to generate the expression for N - (N % VF), which is
02145   // the part that the vectorized body will execute.
02146   Value *R = BypassBuilder.CreateURem(Count, Step, "n.mod.vf");
02147   Value *CountRoundDown = BypassBuilder.CreateSub(Count, R, "n.vec");
02148   Value *IdxEndRoundDown = BypassBuilder.CreateAdd(CountRoundDown, StartIdx,
02149                                                      "end.idx.rnd.down");
02150 
02151   // Now, compare the new count to zero. If it is zero skip the vector loop and
02152   // jump to the scalar loop.
02153   Value *Cmp =
02154       BypassBuilder.CreateICmpEQ(IdxEndRoundDown, StartIdx, "cmp.zero");
02155 
02156   BasicBlock *LastBypassBlock = BypassBlock;
02157 
02158   // Generate code to check that the loops trip count that we computed by adding
02159   // one to the backedge-taken count will not overflow.
02160   {
02161     auto PastOverflowCheck =
02162         std::next(BasicBlock::iterator(OverflowCheckAnchor));
02163     BasicBlock *CheckBlock =
02164       LastBypassBlock->splitBasicBlock(PastOverflowCheck, "overflow.checked");
02165     if (ParentLoop)
02166       ParentLoop->addBasicBlockToLoop(CheckBlock, *LI);
02167     LoopBypassBlocks.push_back(CheckBlock);
02168     Instruction *OldTerm = LastBypassBlock->getTerminator();
02169     BranchInst::Create(ScalarPH, CheckBlock, CheckBCOverflow, OldTerm);
02170     OldTerm->eraseFromParent();
02171     LastBypassBlock = CheckBlock;
02172   }
02173 
02174   // Generate the code to check that the strides we assumed to be one are really
02175   // one. We want the new basic block to start at the first instruction in a
02176   // sequence of instructions that form a check.
02177   Instruction *StrideCheck;
02178   Instruction *FirstCheckInst;
02179   std::tie(FirstCheckInst, StrideCheck) =
02180       addStrideCheck(LastBypassBlock->getTerminator());
02181   if (StrideCheck) {
02182     AddedSafetyChecks = true;
02183     // Create a new block containing the stride check.
02184     BasicBlock *CheckBlock =
02185         LastBypassBlock->splitBasicBlock(FirstCheckInst, "vector.stridecheck");
02186     if (ParentLoop)
02187       ParentLoop->addBasicBlockToLoop(CheckBlock, *LI);
02188     LoopBypassBlocks.push_back(CheckBlock);
02189 
02190     // Replace the branch into the memory check block with a conditional branch
02191     // for the "few elements case".
02192     Instruction *OldTerm = LastBypassBlock->getTerminator();
02193     BranchInst::Create(MiddleBlock, CheckBlock, Cmp, OldTerm);
02194     OldTerm->eraseFromParent();
02195 
02196     Cmp = StrideCheck;
02197     LastBypassBlock = CheckBlock;
02198   }
02199 
02200   // Generate the code that checks in runtime if arrays overlap. We put the
02201   // checks into a separate block to make the more common case of few elements
02202   // faster.
02203   Instruction *MemRuntimeCheck;
02204   std::tie(FirstCheckInst, MemRuntimeCheck) =
02205     Legal->getLAI()->addRuntimeCheck(LastBypassBlock->getTerminator());
02206   if (MemRuntimeCheck) {
02207     AddedSafetyChecks = true;
02208     // Create a new block containing the memory check.
02209     BasicBlock *CheckBlock =
02210         LastBypassBlock->splitBasicBlock(FirstCheckInst, "vector.memcheck");
02211     if (ParentLoop)
02212       ParentLoop->addBasicBlockToLoop(CheckBlock, *LI);
02213     LoopBypassBlocks.push_back(CheckBlock);
02214 
02215     // Replace the branch into the memory check block with a conditional branch
02216     // for the "few elements case".
02217     Instruction *OldTerm = LastBypassBlock->getTerminator();
02218     BranchInst::Create(MiddleBlock, CheckBlock, Cmp, OldTerm);
02219     OldTerm->eraseFromParent();
02220 
02221     Cmp = MemRuntimeCheck;
02222     LastBypassBlock = CheckBlock;
02223   }
02224 
02225   LastBypassBlock->getTerminator()->eraseFromParent();
02226   BranchInst::Create(MiddleBlock, VectorPH, Cmp,
02227                      LastBypassBlock);
02228 
02229   // We are going to resume the execution of the scalar loop.
02230   // Go over all of the induction variables that we found and fix the
02231   // PHIs that are left in the scalar version of the loop.
02232   // The starting values of PHI nodes depend on the counter of the last
02233   // iteration in the vectorized loop.
02234   // If we come from a bypass edge then we need to start from the original
02235   // start value.
02236 
02237   // This variable saves the new starting index for the scalar loop.
02238   PHINode *ResumeIndex = nullptr;
02239   LoopVectorizationLegality::InductionList::iterator I, E;
02240   LoopVectorizationLegality::InductionList *List = Legal->getInductionVars();
02241   // Set builder to point to last bypass block.
02242   BypassBuilder.SetInsertPoint(LoopBypassBlocks.back()->getTerminator());
02243   for (I = List->begin(), E = List->end(); I != E; ++I) {
02244     PHINode *OrigPhi = I->first;
02245     LoopVectorizationLegality::InductionInfo II = I->second;
02246 
02247     Type *ResumeValTy = (OrigPhi == OldInduction) ? IdxTy : OrigPhi->getType();
02248     PHINode *ResumeVal = PHINode::Create(ResumeValTy, 2, "resume.val",
02249                                          MiddleBlock->getTerminator());
02250     // We might have extended the type of the induction variable but we need a
02251     // truncated version for the scalar loop.
02252     PHINode *TruncResumeVal = (OrigPhi == OldInduction) ?
02253       PHINode::Create(OrigPhi->getType(), 2, "trunc.resume.val",
02254                       MiddleBlock->getTerminator()) : nullptr;
02255 
02256     // Create phi nodes to merge from the  backedge-taken check block.
02257     PHINode *BCResumeVal = PHINode::Create(ResumeValTy, 3, "bc.resume.val",
02258                                            ScalarPH->getTerminator());
02259     BCResumeVal->addIncoming(ResumeVal, MiddleBlock);
02260 
02261     PHINode *BCTruncResumeVal = nullptr;
02262     if (OrigPhi == OldInduction) {
02263       BCTruncResumeVal =
02264           PHINode::Create(OrigPhi->getType(), 2, "bc.trunc.resume.val",
02265                           ScalarPH->getTerminator());
02266       BCTruncResumeVal->addIncoming(TruncResumeVal, MiddleBlock);
02267     }
02268 
02269     Value *EndValue = nullptr;
02270     switch (II.IK) {
02271     case LoopVectorizationLegality::IK_NoInduction:
02272       llvm_unreachable("Unknown induction");
02273     case LoopVectorizationLegality::IK_IntInduction: {
02274       // Handle the integer induction counter.
02275       assert(OrigPhi->getType()->isIntegerTy() && "Invalid type");
02276 
02277       // We have the canonical induction variable.
02278       if (OrigPhi == OldInduction) {
02279         // Create a truncated version of the resume value for the scalar loop,
02280         // we might have promoted the type to a larger width.
02281         EndValue =
02282           BypassBuilder.CreateTrunc(IdxEndRoundDown, OrigPhi->getType());
02283         // The new PHI merges the original incoming value, in case of a bypass,
02284         // or the value at the end of the vectorized loop.
02285         for (unsigned I = 1, E = LoopBypassBlocks.size(); I != E; ++I)
02286           TruncResumeVal->addIncoming(II.StartValue, LoopBypassBlocks[I]);
02287         TruncResumeVal->addIncoming(EndValue, VecBody);
02288 
02289         BCTruncResumeVal->addIncoming(II.StartValue, LoopBypassBlocks[0]);
02290 
02291         // We know what the end value is.
02292         EndValue = IdxEndRoundDown;
02293         // We also know which PHI node holds it.
02294         ResumeIndex = ResumeVal;
02295         break;
02296       }
02297 
02298       // Not the canonical induction variable - add the vector loop count to the
02299       // start value.
02300       Value *CRD = BypassBuilder.CreateSExtOrTrunc(CountRoundDown,
02301                                                    II.StartValue->getType(),
02302                                                    "cast.crd");
02303       EndValue = II.transform(BypassBuilder, CRD);
02304       EndValue->setName("ind.end");
02305       break;
02306     }
02307     case LoopVectorizationLegality::IK_PtrInduction: {
02308       EndValue = II.transform(BypassBuilder, CountRoundDown);
02309       EndValue->setName("ptr.ind.end");
02310       break;
02311     }
02312     }// end of case
02313 
02314     // The new PHI merges the original incoming value, in case of a bypass,
02315     // or the value at the end of the vectorized loop.
02316     for (unsigned I = 1, E = LoopBypassBlocks.size(); I != E; ++I) {
02317       if (OrigPhi == OldInduction)
02318         ResumeVal->addIncoming(StartIdx, LoopBypassBlocks[I]);
02319       else
02320         ResumeVal->addIncoming(II.StartValue, LoopBypassBlocks[I]);
02321     }
02322     ResumeVal->addIncoming(EndValue, VecBody);
02323 
02324     // Fix the scalar body counter (PHI node).
02325     unsigned BlockIdx = OrigPhi->getBasicBlockIndex(ScalarPH);
02326 
02327     // The old induction's phi node in the scalar body needs the truncated
02328     // value.
02329     if (OrigPhi == OldInduction) {
02330       BCResumeVal->addIncoming(StartIdx, LoopBypassBlocks[0]);
02331       OrigPhi->setIncomingValue(BlockIdx, BCTruncResumeVal);
02332     } else {
02333       BCResumeVal->addIncoming(II.StartValue, LoopBypassBlocks[0]);
02334       OrigPhi->setIncomingValue(BlockIdx, BCResumeVal);
02335     }
02336   }
02337 
02338   // If we are generating a new induction variable then we also need to
02339   // generate the code that calculates the exit value. This value is not
02340   // simply the end of the counter because we may skip the vectorized body
02341   // in case of a runtime check.
02342   if (!OldInduction){
02343     assert(!ResumeIndex && "Unexpected resume value found");
02344     ResumeIndex = PHINode::Create(IdxTy, 2, "new.indc.resume.val",
02345                                   MiddleBlock->getTerminator());
02346     for (unsigned I = 1, E = LoopBypassBlocks.size(); I != E; ++I)
02347       ResumeIndex->addIncoming(StartIdx, LoopBypassBlocks[I]);
02348     ResumeIndex->addIncoming(IdxEndRoundDown, VecBody);
02349   }
02350 
02351   // Make sure that we found the index where scalar loop needs to continue.
02352   assert(ResumeIndex && ResumeIndex->getType()->isIntegerTy() &&
02353          "Invalid resume Index");
02354 
02355   // Add a check in the middle block to see if we have completed
02356   // all of the iterations in the first vector loop.
02357   // If (N - N%VF) == N, then we *don't* need to run the remainder.
02358   Value *CmpN = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, IdxEnd,
02359                                 ResumeIndex, "cmp.n",
02360                                 MiddleBlock->getTerminator());
02361 
02362   BranchInst::Create(ExitBlock, ScalarPH, CmpN, MiddleBlock->getTerminator());
02363   // Remove the old terminator.
02364   MiddleBlock->getTerminator()->eraseFromParent();
02365 
02366   // Create i+1 and fill the PHINode.
02367   Value *NextIdx = Builder.CreateAdd(Induction, Step, "index.next");
02368   Induction->addIncoming(StartIdx, VectorPH);
02369   Induction->addIncoming(NextIdx, VecBody);
02370   // Create the compare.
02371   Value *ICmp = Builder.CreateICmpEQ(NextIdx, IdxEndRoundDown);
02372   Builder.CreateCondBr(ICmp, MiddleBlock, VecBody);
02373 
02374   // Now we have two terminators. Remove the old one from the block.
02375   VecBody->getTerminator()->eraseFromParent();
02376 
02377   // Get ready to start creating new instructions into the vectorized body.
02378   Builder.SetInsertPoint(VecBody->getFirstInsertionPt());
02379 
02380   // Save the state.
02381   LoopVectorPreHeader = VectorPH;
02382   LoopScalarPreHeader = ScalarPH;
02383   LoopMiddleBlock = MiddleBlock;
02384   LoopExitBlock = ExitBlock;
02385   LoopVectorBody.push_back(VecBody);
02386   LoopScalarBody = OldBasicBlock;
02387 
02388   LoopVectorizeHints Hints(Lp, true);
02389   Hints.setAlreadyVectorized();
02390 }
02391 
02392 namespace {
02393 struct CSEDenseMapInfo {
02394   static bool canHandle(Instruction *I) {
02395     return isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) ||
02396            isa<ShuffleVectorInst>(I) || isa<GetElementPtrInst>(I);
02397   }
02398   static inline Instruction *getEmptyKey() {
02399     return DenseMapInfo<Instruction *>::getEmptyKey();
02400   }
02401   static inline Instruction *getTombstoneKey() {
02402     return DenseMapInfo<Instruction *>::getTombstoneKey();
02403   }
02404   static unsigned getHashValue(Instruction *I) {
02405     assert(canHandle(I) && "Unknown instruction!");
02406     return hash_combine(I->getOpcode(), hash_combine_range(I->value_op_begin(),
02407                                                            I->value_op_end()));
02408   }
02409   static bool isEqual(Instruction *LHS, Instruction *RHS) {
02410     if (LHS == getEmptyKey() || RHS == getEmptyKey() ||
02411         LHS == getTombstoneKey() || RHS == getTombstoneKey())
02412       return LHS == RHS;
02413     return LHS->isIdenticalTo(RHS);
02414   }
02415 };
02416 }
02417 
02418 /// \brief Check whether this block is a predicated block.
02419 /// Due to if predication of stores we might create a sequence of "if(pred) a[i]
02420 /// = ...;  " blocks. We start with one vectorized basic block. For every
02421 /// conditional block we split this vectorized block. Therefore, every second
02422 /// block will be a predicated one.
02423 static bool isPredicatedBlock(unsigned BlockNum) {
02424   return BlockNum % 2;
02425 }
02426 
02427 ///\brief Perform cse of induction variable instructions.
02428 static void cse(SmallVector<BasicBlock *, 4> &BBs) {
02429   // Perform simple cse.
02430   SmallDenseMap<Instruction *, Instruction *, 4, CSEDenseMapInfo> CSEMap;
02431   for (unsigned i = 0, e = BBs.size(); i != e; ++i) {
02432     BasicBlock *BB = BBs[i];
02433     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
02434       Instruction *In = I++;
02435 
02436       if (!CSEDenseMapInfo::canHandle(In))
02437         continue;
02438 
02439       // Check if we can replace this instruction with any of the
02440       // visited instructions.
02441       if (Instruction *V = CSEMap.lookup(In)) {
02442         In->replaceAllUsesWith(V);
02443         In->eraseFromParent();
02444         continue;
02445       }
02446       // Ignore instructions in conditional blocks. We create "if (pred) a[i] =
02447       // ...;" blocks for predicated stores. Every second block is a predicated
02448       // block.
02449       if (isPredicatedBlock(i))
02450         continue;
02451 
02452       CSEMap[In] = In;
02453     }
02454   }
02455 }
02456 
02457 /// \brief Adds a 'fast' flag to floating point operations.
02458 static Value *addFastMathFlag(Value *V) {
02459   if (isa<FPMathOperator>(V)){
02460     FastMathFlags Flags;
02461     Flags.setUnsafeAlgebra();
02462     cast<Instruction>(V)->setFastMathFlags(Flags);
02463   }
02464   return V;
02465 }
02466 
02467 /// Estimate the overhead of scalarizing a value. Insert and Extract are set if
02468 /// the result needs to be inserted and/or extracted from vectors.
02469 static unsigned getScalarizationOverhead(Type *Ty, bool Insert, bool Extract,
02470                                          const TargetTransformInfo &TTI) {
02471   if (Ty->isVoidTy())
02472     return 0;
02473 
02474   assert(Ty->isVectorTy() && "Can only scalarize vectors");
02475   unsigned Cost = 0;
02476 
02477   for (int i = 0, e = Ty->getVectorNumElements(); i < e; ++i) {
02478     if (Insert)
02479       Cost += TTI.getVectorInstrCost(Instruction::InsertElement, Ty, i);
02480     if (Extract)
02481       Cost += TTI.getVectorInstrCost(Instruction::ExtractElement, Ty, i);
02482   }
02483 
02484   return Cost;
02485 }
02486 
02487 // Estimate cost of a call instruction CI if it were vectorized with factor VF.
02488 // Return the cost of the instruction, including scalarization overhead if it's
02489 // needed. The flag NeedToScalarize shows if the call needs to be scalarized -
02490 // i.e. either vector version isn't available, or is too expensive.
02491 static unsigned getVectorCallCost(CallInst *CI, unsigned VF,
02492                                   const TargetTransformInfo &TTI,
02493                                   const TargetLibraryInfo *TLI,
02494                                   bool &NeedToScalarize) {
02495   Function *F = CI->getCalledFunction();
02496   StringRef FnName = CI->getCalledFunction()->getName();
02497   Type *ScalarRetTy = CI->getType();
02498   SmallVector<Type *, 4> Tys, ScalarTys;
02499   for (auto &ArgOp : CI->arg_operands())
02500     ScalarTys.push_back(ArgOp->getType());
02501 
02502   // Estimate cost of scalarized vector call. The source operands are assumed
02503   // to be vectors, so we need to extract individual elements from there,
02504   // execute VF scalar calls, and then gather the result into the vector return
02505   // value.
02506   unsigned ScalarCallCost = TTI.getCallInstrCost(F, ScalarRetTy, ScalarTys);
02507   if (VF == 1)
02508     return ScalarCallCost;
02509 
02510   // Compute corresponding vector type for return value and arguments.
02511   Type *RetTy = ToVectorTy(ScalarRetTy, VF);
02512   for (unsigned i = 0, ie = ScalarTys.size(); i != ie; ++i)
02513     Tys.push_back(ToVectorTy(ScalarTys[i], VF));
02514 
02515   // Compute costs of unpacking argument values for the scalar calls and
02516   // packing the return values to a vector.
02517   unsigned ScalarizationCost =
02518       getScalarizationOverhead(RetTy, true, false, TTI);
02519   for (unsigned i = 0, ie = Tys.size(); i != ie; ++i)
02520     ScalarizationCost += getScalarizationOverhead(Tys[i], false, true, TTI);
02521 
02522   unsigned Cost = ScalarCallCost * VF + ScalarizationCost;
02523 
02524   // If we can't emit a vector call for this function, then the currently found
02525   // cost is the cost we need to return.
02526   NeedToScalarize = true;
02527   if (!TLI || !TLI->isFunctionVectorizable(FnName, VF) || CI->isNoBuiltin())
02528     return Cost;
02529 
02530   // If the corresponding vector cost is cheaper, return its cost.
02531   unsigned VectorCallCost = TTI.getCallInstrCost(nullptr, RetTy, Tys);
02532   if (VectorCallCost < Cost) {
02533     NeedToScalarize = false;
02534     return VectorCallCost;
02535   }
02536   return Cost;
02537 }
02538 
02539 // Estimate cost of an intrinsic call instruction CI if it were vectorized with
02540 // factor VF.  Return the cost of the instruction, including scalarization
02541 // overhead if it's needed.
02542 static unsigned getVectorIntrinsicCost(CallInst *CI, unsigned VF,
02543                                        const TargetTransformInfo &TTI,
02544                                        const TargetLibraryInfo *TLI) {
02545   Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
02546   assert(ID && "Expected intrinsic call!");
02547 
02548   Type *RetTy = ToVectorTy(CI->getType(), VF);
02549   SmallVector<Type *, 4> Tys;
02550   for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i)
02551     Tys.push_back(ToVectorTy(CI->getArgOperand(i)->getType(), VF));
02552 
02553   return TTI.getIntrinsicInstrCost(ID, RetTy, Tys);
02554 }
02555 
02556 void InnerLoopVectorizer::vectorizeLoop() {
02557   //===------------------------------------------------===//
02558   //
02559   // Notice: any optimization or new instruction that go
02560   // into the code below should be also be implemented in
02561   // the cost-model.
02562   //
02563   //===------------------------------------------------===//
02564   Constant *Zero = Builder.getInt32(0);
02565 
02566   // In order to support reduction variables we need to be able to vectorize
02567   // Phi nodes. Phi nodes have cycles, so we need to vectorize them in two
02568   // stages. First, we create a new vector PHI node with no incoming edges.
02569   // We use this value when we vectorize all of the instructions that use the
02570   // PHI. Next, after all of the instructions in the block are complete we
02571   // add the new incoming edges to the PHI. At this point all of the
02572   // instructions in the basic block are vectorized, so we can use them to
02573   // construct the PHI.
02574   PhiVector RdxPHIsToFix;
02575 
02576   // Scan the loop in a topological order to ensure that defs are vectorized
02577   // before users.
02578   LoopBlocksDFS DFS(OrigLoop);
02579   DFS.perform(LI);
02580 
02581   // Vectorize all of the blocks in the original loop.
02582   for (LoopBlocksDFS::RPOIterator bb = DFS.beginRPO(),
02583        be = DFS.endRPO(); bb != be; ++bb)
02584     vectorizeBlockInLoop(*bb, &RdxPHIsToFix);
02585 
02586   // At this point every instruction in the original loop is widened to
02587   // a vector form. We are almost done. Now, we need to fix the PHI nodes
02588   // that we vectorized. The PHI nodes are currently empty because we did
02589   // not want to introduce cycles. Notice that the remaining PHI nodes
02590   // that we need to fix are reduction variables.
02591 
02592   // Create the 'reduced' values for each of the induction vars.
02593   // The reduced values are the vector values that we scalarize and combine
02594   // after the loop is finished.
02595   for (PhiVector::iterator it = RdxPHIsToFix.begin(), e = RdxPHIsToFix.end();
02596        it != e; ++it) {
02597     PHINode *RdxPhi = *it;
02598     assert(RdxPhi && "Unable to recover vectorized PHI");
02599 
02600     // Find the reduction variable descriptor.
02601     assert(Legal->getReductionVars()->count(RdxPhi) &&
02602            "Unable to find the reduction variable");
02603     ReductionDescriptor RdxDesc = (*Legal->getReductionVars())[RdxPhi];
02604 
02605     ReductionDescriptor::ReductionKind RK = RdxDesc.getReductionKind();
02606     TrackingVH<Value> ReductionStartValue = RdxDesc.getReductionStartValue();
02607     Instruction *LoopExitInst = RdxDesc.getLoopExitInstr();
02608     ReductionInstDesc::MinMaxReductionKind MinMaxKind =
02609         RdxDesc.getMinMaxReductionKind();
02610     setDebugLocFromInst(Builder, ReductionStartValue);
02611 
02612     // We need to generate a reduction vector from the incoming scalar.
02613     // To do so, we need to generate the 'identity' vector and override
02614     // one of the elements with the incoming scalar reduction. We need
02615     // to do it in the vector-loop preheader.
02616     Builder.SetInsertPoint(LoopBypassBlocks[1]->getTerminator());
02617 
02618     // This is the vector-clone of the value that leaves the loop.
02619     VectorParts &VectorExit = getVectorValue(LoopExitInst);
02620     Type *VecTy = VectorExit[0]->getType();
02621 
02622     // Find the reduction identity variable. Zero for addition, or, xor,
02623     // one for multiplication, -1 for And.
02624     Value *Identity;
02625     Value *VectorStart;
02626     if (RK == ReductionDescriptor::RK_IntegerMinMax ||
02627         RK == ReductionDescriptor::RK_FloatMinMax) {
02628       // MinMax reduction have the start value as their identify.
02629       if (VF == 1) {
02630         VectorStart = Identity = ReductionStartValue;
02631       } else {
02632         VectorStart = Identity =
02633             Builder.CreateVectorSplat(VF, ReductionStartValue, "minmax.ident");
02634       }
02635     } else {
02636       // Handle other reduction kinds:
02637       Constant *Iden =
02638           ReductionDescriptor::getReductionIdentity(RK, VecTy->getScalarType());
02639       if (VF == 1) {
02640         Identity = Iden;
02641         // This vector is the Identity vector where the first element is the
02642         // incoming scalar reduction.
02643         VectorStart = ReductionStartValue;
02644       } else {
02645         Identity = ConstantVector::getSplat(VF, Iden);
02646 
02647         // This vector is the Identity vector where the first element is the
02648         // incoming scalar reduction.
02649         VectorStart =
02650             Builder.CreateInsertElement(Identity, ReductionStartValue, Zero);
02651       }
02652     }
02653 
02654     // Fix the vector-loop phi.
02655 
02656     // Reductions do not have to start at zero. They can start with
02657     // any loop invariant values.
02658     VectorParts &VecRdxPhi = WidenMap.get(RdxPhi);
02659     BasicBlock *Latch = OrigLoop->getLoopLatch();
02660     Value *LoopVal = RdxPhi->getIncomingValueForBlock(Latch);
02661     VectorParts &Val = getVectorValue(LoopVal);
02662     for (unsigned part = 0; part < UF; ++part) {
02663       // Make sure to add the reduction stat value only to the
02664       // first unroll part.
02665       Value *StartVal = (part == 0) ? VectorStart : Identity;
02666       cast<PHINode>(VecRdxPhi[part])->addIncoming(StartVal,
02667                                                   LoopVectorPreHeader);
02668       cast<PHINode>(VecRdxPhi[part])->addIncoming(Val[part],
02669                                                   LoopVectorBody.back());
02670     }
02671 
02672     // Before each round, move the insertion point right between
02673     // the PHIs and the values we are going to write.
02674     // This allows us to write both PHINodes and the extractelement
02675     // instructions.
02676     Builder.SetInsertPoint(LoopMiddleBlock->getFirstInsertionPt());
02677 
02678     VectorParts RdxParts;
02679     setDebugLocFromInst(Builder, LoopExitInst);
02680     for (unsigned part = 0; part < UF; ++part) {
02681       // This PHINode contains the vectorized reduction variable, or
02682       // the initial value vector, if we bypass the vector loop.
02683       VectorParts &RdxExitVal = getVectorValue(LoopExitInst);
02684       PHINode *NewPhi = Builder.CreatePHI(VecTy, 2, "rdx.vec.exit.phi");
02685       Value *StartVal = (part == 0) ? VectorStart : Identity;
02686       for (unsigned I = 1, E = LoopBypassBlocks.size(); I != E; ++I)
02687         NewPhi->addIncoming(StartVal, LoopBypassBlocks[I]);
02688       NewPhi->addIncoming(RdxExitVal[part],
02689                           LoopVectorBody.back());
02690       RdxParts.push_back(NewPhi);
02691     }
02692 
02693     // Reduce all of the unrolled parts into a single vector.
02694     Value *ReducedPartRdx = RdxParts[0];
02695     unsigned Op = ReductionDescriptor::getReductionBinOp(RK);
02696     setDebugLocFromInst(Builder, ReducedPartRdx);
02697     for (unsigned part = 1; part < UF; ++part) {
02698       if (Op != Instruction::ICmp && Op != Instruction::FCmp)
02699         // Floating point operations had to be 'fast' to enable the reduction.
02700         ReducedPartRdx = addFastMathFlag(
02701             Builder.CreateBinOp((Instruction::BinaryOps)Op, RdxParts[part],
02702                                 ReducedPartRdx, "bin.rdx"));
02703       else
02704         ReducedPartRdx = ReductionDescriptor::createMinMaxOp(
02705             Builder, MinMaxKind, ReducedPartRdx, RdxParts[part]);
02706     }
02707 
02708     if (VF > 1) {
02709       // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
02710       // and vector ops, reducing the set of values being computed by half each
02711       // round.
02712       assert(isPowerOf2_32(VF) &&
02713              "Reduction emission only supported for pow2 vectors!");
02714       Value *TmpVec = ReducedPartRdx;
02715       SmallVector<Constant*, 32> ShuffleMask(VF, nullptr);
02716       for (unsigned i = VF; i != 1; i >>= 1) {
02717         // Move the upper half of the vector to the lower half.
02718         for (unsigned j = 0; j != i/2; ++j)
02719           ShuffleMask[j] = Builder.getInt32(i/2 + j);
02720 
02721         // Fill the rest of the mask with undef.
02722         std::fill(&ShuffleMask[i/2], ShuffleMask.end(),
02723                   UndefValue::get(Builder.getInt32Ty()));
02724 
02725         Value *Shuf =
02726         Builder.CreateShuffleVector(TmpVec,
02727                                     UndefValue::get(TmpVec->getType()),
02728                                     ConstantVector::get(ShuffleMask),
02729                                     "rdx.shuf");
02730 
02731         if (Op != Instruction::ICmp && Op != Instruction::FCmp)
02732           // Floating point operations had to be 'fast' to enable the reduction.
02733           TmpVec = addFastMathFlag(Builder.CreateBinOp(
02734               (Instruction::BinaryOps)Op, TmpVec, Shuf, "bin.rdx"));
02735         else
02736           TmpVec = ReductionDescriptor::createMinMaxOp(Builder, MinMaxKind,
02737                                                        TmpVec, Shuf);
02738       }
02739 
02740       // The result is in the first element of the vector.
02741       ReducedPartRdx = Builder.CreateExtractElement(TmpVec,
02742                                                     Builder.getInt32(0));
02743     }
02744 
02745     // Create a phi node that merges control-flow from the backedge-taken check
02746     // block and the middle block.
02747     PHINode *BCBlockPhi = PHINode::Create(RdxPhi->getType(), 2, "bc.merge.rdx",
02748                                           LoopScalarPreHeader->getTerminator());
02749     BCBlockPhi->addIncoming(ReductionStartValue, LoopBypassBlocks[0]);
02750     BCBlockPhi->addIncoming(ReducedPartRdx, LoopMiddleBlock);
02751 
02752     // Now, we need to fix the users of the reduction variable
02753     // inside and outside of the scalar remainder loop.
02754     // We know that the loop is in LCSSA form. We need to update the
02755     // PHI nodes in the exit blocks.
02756     for (BasicBlock::iterator LEI = LoopExitBlock->begin(),
02757          LEE = LoopExitBlock->end(); LEI != LEE; ++LEI) {
02758       PHINode *LCSSAPhi = dyn_cast<PHINode>(LEI);
02759       if (!LCSSAPhi) break;
02760 
02761       // All PHINodes need to have a single entry edge, or two if
02762       // we already fixed them.
02763       assert(LCSSAPhi->getNumIncomingValues() < 3 && "Invalid LCSSA PHI");
02764 
02765       // We found our reduction value exit-PHI. Update it with the
02766       // incoming bypass edge.
02767       if (LCSSAPhi->getIncomingValue(0) == LoopExitInst) {
02768         // Add an edge coming from the bypass.
02769         LCSSAPhi->addIncoming(ReducedPartRdx, LoopMiddleBlock);
02770         break;
02771       }
02772     }// end of the LCSSA phi scan.
02773 
02774     // Fix the scalar loop reduction variable with the incoming reduction sum
02775     // from the vector body and from the backedge value.
02776     int IncomingEdgeBlockIdx =
02777     (RdxPhi)->getBasicBlockIndex(OrigLoop->getLoopLatch());
02778     assert(IncomingEdgeBlockIdx >= 0 && "Invalid block index");
02779     // Pick the other block.
02780     int SelfEdgeBlockIdx = (IncomingEdgeBlockIdx ? 0 : 1);
02781     (RdxPhi)->setIncomingValue(SelfEdgeBlockIdx, BCBlockPhi);
02782     (RdxPhi)->setIncomingValue(IncomingEdgeBlockIdx, LoopExitInst);
02783   }// end of for each redux variable.
02784 
02785   fixLCSSAPHIs();
02786 
02787   // Remove redundant induction instructions.
02788   cse(LoopVectorBody);
02789 }
02790 
02791 void InnerLoopVectorizer::fixLCSSAPHIs() {
02792   for (BasicBlock::iterator LEI = LoopExitBlock->begin(),
02793        LEE = LoopExitBlock->end(); LEI != LEE; ++LEI) {
02794     PHINode *LCSSAPhi = dyn_cast<PHINode>(LEI);
02795     if (!LCSSAPhi) break;
02796     if (LCSSAPhi->getNumIncomingValues() == 1)
02797       LCSSAPhi->addIncoming(UndefValue::get(LCSSAPhi->getType()),
02798                             LoopMiddleBlock);
02799   }
02800 }
02801 
02802 InnerLoopVectorizer::VectorParts
02803 InnerLoopVectorizer::createEdgeMask(BasicBlock *Src, BasicBlock *Dst) {
02804   assert(std::find(pred_begin(Dst), pred_end(Dst), Src) != pred_end(Dst) &&
02805          "Invalid edge");
02806 
02807   // Look for cached value.
02808   std::pair<BasicBlock*, BasicBlock*> Edge(Src, Dst);
02809   EdgeMaskCache::iterator ECEntryIt = MaskCache.find(Edge);
02810   if (ECEntryIt != MaskCache.end())
02811     return ECEntryIt->second;
02812 
02813   VectorParts SrcMask = createBlockInMask(Src);
02814 
02815   // The terminator has to be a branch inst!
02816   BranchInst *BI = dyn_cast<BranchInst>(Src->getTerminator());
02817   assert(BI && "Unexpected terminator found");
02818 
02819   if (BI->isConditional()) {
02820     VectorParts EdgeMask = getVectorValue(BI->getCondition());
02821 
02822     if (BI->getSuccessor(0) != Dst)
02823       for (unsigned part = 0; part < UF; ++part)
02824         EdgeMask[part] = Builder.CreateNot(EdgeMask[part]);
02825 
02826     for (unsigned part = 0; part < UF; ++part)
02827       EdgeMask[part] = Builder.CreateAnd(EdgeMask[part], SrcMask[part]);
02828 
02829     MaskCache[Edge] = EdgeMask;
02830     return EdgeMask;
02831   }
02832 
02833   MaskCache[Edge] = SrcMask;
02834   return SrcMask;
02835 }
02836 
02837 InnerLoopVectorizer::VectorParts
02838 InnerLoopVectorizer::createBlockInMask(BasicBlock *BB) {
02839   assert(OrigLoop->contains(BB) && "Block is not a part of a loop");
02840 
02841   // Loop incoming mask is all-one.
02842   if (OrigLoop->getHeader() == BB) {
02843     Value *C = ConstantInt::get(IntegerType::getInt1Ty(BB->getContext()), 1);
02844     return getVectorValue(C);
02845   }
02846 
02847   // This is the block mask. We OR all incoming edges, and with zero.
02848   Value *Zero = ConstantInt::get(IntegerType::getInt1Ty(BB->getContext()), 0);
02849   VectorParts BlockMask = getVectorValue(Zero);
02850 
02851   // For each pred:
02852   for (pred_iterator it = pred_begin(BB), e = pred_end(BB); it != e; ++it) {
02853     VectorParts EM = createEdgeMask(*it, BB);
02854     for (unsigned part = 0; part < UF; ++part)
02855       BlockMask[part] = Builder.CreateOr(BlockMask[part], EM[part]);
02856   }
02857 
02858   return BlockMask;
02859 }
02860 
02861 void InnerLoopVectorizer::widenPHIInstruction(Instruction *PN,
02862                                               InnerLoopVectorizer::VectorParts &Entry,
02863                                               unsigned UF, unsigned VF, PhiVector *PV) {
02864   PHINode* P = cast<PHINode>(PN);
02865   // Handle reduction variables:
02866   if (Legal->getReductionVars()->count(P)) {
02867     for (unsigned part = 0; part < UF; ++part) {
02868       // This is phase one of vectorizing PHIs.
02869       Type *VecTy = (VF == 1) ? PN->getType() :
02870       VectorType::get(PN->getType(), VF);
02871       Entry[part] = PHINode::Create(VecTy, 2, "vec.phi",
02872                                     LoopVectorBody.back()-> getFirstInsertionPt());
02873     }
02874     PV->push_back(P);
02875     return;
02876   }
02877 
02878   setDebugLocFromInst(Builder, P);
02879   // Check for PHI nodes that are lowered to vector selects.
02880   if (P->getParent() != OrigLoop->getHeader()) {
02881     // We know that all PHIs in non-header blocks are converted into
02882     // selects, so we don't have to worry about the insertion order and we
02883     // can just use the builder.
02884     // At this point we generate the predication tree. There may be
02885     // duplications since this is a simple recursive scan, but future
02886     // optimizations will clean it up.
02887 
02888     unsigned NumIncoming = P->getNumIncomingValues();
02889 
02890     // Generate a sequence of selects of the form:
02891     // SELECT(Mask3, In3,
02892     //      SELECT(Mask2, In2,
02893     //                   ( ...)))
02894     for (unsigned In = 0; In < NumIncoming; In++) {
02895       VectorParts Cond = createEdgeMask(P->getIncomingBlock(In),
02896                                         P->getParent());
02897       VectorParts &In0 = getVectorValue(P->getIncomingValue(In));
02898 
02899       for (unsigned part = 0; part < UF; ++part) {
02900         // We might have single edge PHIs (blocks) - use an identity
02901         // 'select' for the first PHI operand.
02902         if (In == 0)
02903           Entry[part] = Builder.CreateSelect(Cond[part], In0[part],
02904                                              In0[part]);
02905         else
02906           // Select between the current value and the previous incoming edge
02907           // based on the incoming mask.
02908           Entry[part] = Builder.CreateSelect(Cond[part], In0[part],
02909                                              Entry[part], "predphi");
02910       }
02911     }
02912     return;
02913   }
02914 
02915   // This PHINode must be an induction variable.
02916   // Make sure that we know about it.
02917   assert(Legal->getInductionVars()->count(P) &&
02918          "Not an induction variable");
02919 
02920   LoopVectorizationLegality::InductionInfo II =
02921   Legal->getInductionVars()->lookup(P);
02922 
02923   // FIXME: The newly created binary instructions should contain nsw/nuw flags,
02924   // which can be found from the original scalar operations.
02925   switch (II.IK) {
02926     case LoopVectorizationLegality::IK_NoInduction:
02927       llvm_unreachable("Unknown induction");
02928     case LoopVectorizationLegality::IK_IntInduction: {
02929       assert(P->getType() == II.StartValue->getType() && "Types must match");
02930       Type *PhiTy = P->getType();
02931       Value *Broadcasted;
02932       if (P == OldInduction) {
02933         // Handle the canonical induction variable. We might have had to
02934         // extend the type.
02935         Broadcasted = Builder.CreateTrunc(Induction, PhiTy);
02936       } else {
02937         // Handle other induction variables that are now based on the
02938         // canonical one.
02939         Value *NormalizedIdx = Builder.CreateSub(Induction, ExtendedIdx,
02940                                                  "normalized.idx");
02941         NormalizedIdx = Builder.CreateSExtOrTrunc(NormalizedIdx, PhiTy);
02942         Broadcasted = II.transform(Builder, NormalizedIdx);
02943         Broadcasted->setName("offset.idx");
02944       }
02945       Broadcasted = getBroadcastInstrs(Broadcasted);
02946       // After broadcasting the induction variable we need to make the vector
02947       // consecutive by adding 0, 1, 2, etc.
02948       for (unsigned part = 0; part < UF; ++part)
02949         Entry[part] = getStepVector(Broadcasted, VF * part, II.StepValue);
02950       return;
02951     }
02952     case LoopVectorizationLegality::IK_PtrInduction:
02953       // Handle the pointer induction variable case.
02954       assert(P->getType()->isPointerTy() && "Unexpected type.");
02955       // This is the normalized GEP that starts counting at zero.
02956       Value *NormalizedIdx =
02957           Builder.CreateSub(Induction, ExtendedIdx, "normalized.idx");
02958       // This is the vector of results. Notice that we don't generate
02959       // vector geps because scalar geps result in better code.
02960       for (unsigned part = 0; part < UF; ++part) {
02961         if (VF == 1) {
02962           int EltIndex = part;
02963           Constant *Idx = ConstantInt::get(Induction->getType(), EltIndex);
02964           Value *GlobalIdx = Builder.CreateAdd(NormalizedIdx, Idx);
02965           Value *SclrGep = II.transform(Builder, GlobalIdx);
02966           SclrGep->setName("next.gep");
02967           Entry[part] = SclrGep;
02968           continue;
02969         }
02970 
02971         Value *VecVal = UndefValue::get(VectorType::get(P->getType(), VF));
02972         for (unsigned int i = 0; i < VF; ++i) {
02973           int EltIndex = i + part * VF;
02974           Constant *Idx = ConstantInt::get(Induction->getType(), EltIndex);
02975           Value *GlobalIdx = Builder.CreateAdd(NormalizedIdx, Idx);
02976           Value *SclrGep = II.transform(Builder, GlobalIdx);
02977           SclrGep->setName("next.gep");
02978           VecVal = Builder.CreateInsertElement(VecVal, SclrGep,
02979                                                Builder.getInt32(i),
02980                                                "insert.gep");
02981         }
02982         Entry[part] = VecVal;
02983       }
02984       return;
02985   }
02986 }
02987 
02988 void InnerLoopVectorizer::vectorizeBlockInLoop(BasicBlock *BB, PhiVector *PV) {
02989   // For each instruction in the old loop.
02990   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
02991     VectorParts &Entry = WidenMap.get(it);
02992     switch (it->getOpcode()) {
02993     case Instruction::Br:
02994       // Nothing to do for PHIs and BR, since we already took care of the
02995       // loop control flow instructions.
02996       continue;
02997     case Instruction::PHI: {
02998       // Vectorize PHINodes.
02999       widenPHIInstruction(it, Entry, UF, VF, PV);
03000       continue;
03001     }// End of PHI.
03002 
03003     case Instruction::Add:
03004     case Instruction::FAdd:
03005     case Instruction::Sub:
03006     case Instruction::FSub:
03007     case Instruction::Mul:
03008     case Instruction::FMul:
03009     case Instruction::UDiv:
03010     case Instruction::SDiv:
03011     case Instruction::FDiv:
03012     case Instruction::URem:
03013     case Instruction::SRem:
03014     case Instruction::FRem:
03015     case Instruction::Shl:
03016     case Instruction::LShr:
03017     case Instruction::AShr:
03018     case Instruction::And:
03019     case Instruction::Or:
03020     case Instruction::Xor: {
03021       // Just widen binops.
03022       BinaryOperator *BinOp = dyn_cast<BinaryOperator>(it);
03023       setDebugLocFromInst(Builder, BinOp);
03024       VectorParts &A = getVectorValue(it->getOperand(0));
03025       VectorParts &B = getVectorValue(it->getOperand(1));
03026 
03027       // Use this vector value for all users of the original instruction.
03028       for (unsigned Part = 0; Part < UF; ++Part) {
03029         Value *V = Builder.CreateBinOp(BinOp->getOpcode(), A[Part], B[Part]);
03030 
03031         if (BinaryOperator *VecOp = dyn_cast<BinaryOperator>(V))
03032           VecOp->copyIRFlags(BinOp);
03033 
03034         Entry[Part] = V;
03035       }
03036 
03037       propagateMetadata(Entry, it);
03038       break;
03039     }
03040     case Instruction::Select: {
03041       // Widen selects.
03042       // If the selector is loop invariant we can create a select
03043       // instruction with a scalar condition. Otherwise, use vector-select.
03044       bool InvariantCond = SE->isLoopInvariant(SE->getSCEV(it->getOperand(0)),
03045                                                OrigLoop);
03046       setDebugLocFromInst(Builder, it);
03047 
03048       // The condition can be loop invariant  but still defined inside the
03049       // loop. This means that we can't just use the original 'cond' value.
03050       // We have to take the 'vectorized' value and pick the first lane.
03051       // Instcombine will make this a no-op.
03052       VectorParts &Cond = getVectorValue(it->getOperand(0));
03053       VectorParts &Op0  = getVectorValue(it->getOperand(1));
03054       VectorParts &Op1  = getVectorValue(it->getOperand(2));
03055 
03056       Value *ScalarCond = (VF == 1) ? Cond[0] :
03057         Builder.CreateExtractElement(Cond[0], Builder.getInt32(0));
03058 
03059       for (unsigned Part = 0; Part < UF; ++Part) {
03060         Entry[Part] = Builder.CreateSelect(
03061           InvariantCond ? ScalarCond : Cond[Part],
03062           Op0[Part],
03063           Op1[Part]);
03064       }
03065 
03066       propagateMetadata(Entry, it);
03067       break;
03068     }
03069 
03070     case Instruction::ICmp:
03071     case Instruction::FCmp: {
03072       // Widen compares. Generate vector compares.
03073       bool FCmp = (it->getOpcode() == Instruction::FCmp);
03074       CmpInst *Cmp = dyn_cast<CmpInst>(it);
03075       setDebugLocFromInst(Builder, it);
03076       VectorParts &A = getVectorValue(it->getOperand(0));
03077       VectorParts &B = getVectorValue(it->getOperand(1));
03078       for (unsigned Part = 0; Part < UF; ++Part) {
03079         Value *C = nullptr;
03080         if (FCmp)
03081           C = Builder.CreateFCmp(Cmp->getPredicate(), A[Part], B[Part]);
03082         else
03083           C = Builder.CreateICmp(Cmp->getPredicate(), A[Part], B[Part]);
03084         Entry[Part] = C;
03085       }
03086 
03087       propagateMetadata(Entry, it);
03088       break;
03089     }
03090 
03091     case Instruction::Store:
03092     case Instruction::Load:
03093       vectorizeMemoryInstruction(it);
03094         break;
03095     case Instruction::ZExt:
03096     case Instruction::SExt:
03097     case Instruction::FPToUI:
03098     case Instruction::FPToSI:
03099     case Instruction::FPExt:
03100     case Instruction::PtrToInt:
03101     case Instruction::IntToPtr:
03102     case Instruction::SIToFP:
03103     case Instruction::UIToFP:
03104     case Instruction::Trunc:
03105     case Instruction::FPTrunc:
03106     case Instruction::BitCast: {
03107       CastInst *CI = dyn_cast<CastInst>(it);
03108       setDebugLocFromInst(Builder, it);
03109       /// Optimize the special case where the source is the induction
03110       /// variable. Notice that we can only optimize the 'trunc' case
03111       /// because: a. FP conversions lose precision, b. sext/zext may wrap,
03112       /// c. other casts depend on pointer size.
03113       if (CI->getOperand(0) == OldInduction &&
03114           it->getOpcode() == Instruction::Trunc) {
03115         Value *ScalarCast = Builder.CreateCast(CI->getOpcode(), Induction,
03116                                                CI->getType());
03117         Value *Broadcasted = getBroadcastInstrs(ScalarCast);
03118         LoopVectorizationLegality::InductionInfo II =
03119             Legal->getInductionVars()->lookup(OldInduction);
03120         Constant *Step =
03121             ConstantInt::getSigned(CI->getType(), II.StepValue->getSExtValue());
03122         for (unsigned Part = 0; Part < UF; ++Part)
03123           Entry[Part] = getStepVector(Broadcasted, VF * Part, Step);
03124         propagateMetadata(Entry, it);
03125         break;
03126       }
03127       /// Vectorize casts.
03128       Type *DestTy = (VF == 1) ? CI->getType() :
03129                                  VectorType::get(CI->getType(), VF);
03130 
03131       VectorParts &A = getVectorValue(it->getOperand(0));
03132       for (unsigned Part = 0; Part < UF; ++Part)
03133         Entry[Part] = Builder.CreateCast(CI->getOpcode(), A[Part], DestTy);
03134       propagateMetadata(Entry, it);
03135       break;
03136     }
03137 
03138     case Instruction::Call: {
03139       // Ignore dbg intrinsics.
03140       if (isa<DbgInfoIntrinsic>(it))
03141         break;
03142       setDebugLocFromInst(Builder, it);
03143 
03144       Module *M = BB->getParent()->getParent();
03145       CallInst *CI = cast<CallInst>(it);
03146 
03147       StringRef FnName = CI->getCalledFunction()->getName();
03148       Function *F = CI->getCalledFunction();
03149       Type *RetTy = ToVectorTy(CI->getType(), VF);
03150       SmallVector<Type *, 4> Tys;
03151       for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i)
03152         Tys.push_back(ToVectorTy(CI->getArgOperand(i)->getType(), VF));
03153 
03154       Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
03155       if (ID &&
03156           (ID == Intrinsic::assume || ID == Intrinsic::lifetime_end ||
03157            ID == Intrinsic::lifetime_start)) {
03158         scalarizeInstruction(it);
03159         break;
03160       }
03161       // The flag shows whether we use Intrinsic or a usual Call for vectorized
03162       // version of the instruction.
03163       // Is it beneficial to perform intrinsic call compared to lib call?
03164       bool NeedToScalarize;
03165       unsigned CallCost = getVectorCallCost(CI, VF, *TTI, TLI, NeedToScalarize);
03166       bool UseVectorIntrinsic =
03167           ID && getVectorIntrinsicCost(CI, VF, *TTI, TLI) <= CallCost;
03168       if (!UseVectorIntrinsic && NeedToScalarize) {
03169         scalarizeInstruction(it);
03170         break;
03171       }
03172 
03173       for (unsigned Part = 0; Part < UF; ++Part) {
03174         SmallVector<Value *, 4> Args;
03175         for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i) {
03176           Value *Arg = CI->getArgOperand(i);
03177           // Some intrinsics have a scalar argument - don't replace it with a
03178           // vector.
03179           if (!UseVectorIntrinsic || !hasVectorInstrinsicScalarOpd(ID, i)) {
03180             VectorParts &VectorArg = getVectorValue(CI->getArgOperand(i));
03181             Arg = VectorArg[Part];
03182           }
03183           Args.push_back(Arg);
03184         }
03185 
03186         Function *VectorF;
03187         if (UseVectorIntrinsic) {
03188           // Use vector version of the intrinsic.
03189           Type *TysForDecl[] = {CI->getType()};
03190           if (VF > 1)
03191             TysForDecl[0] = VectorType::get(CI->getType()->getScalarType(), VF);
03192           VectorF = Intrinsic::getDeclaration(M, ID, TysForDecl);
03193         } else {
03194           // Use vector version of the library call.
03195           StringRef VFnName = TLI->getVectorizedFunction(FnName, VF);
03196           assert(!VFnName.empty() && "Vector function name is empty.");
03197           VectorF = M->getFunction(VFnName);
03198           if (!VectorF) {
03199             // Generate a declaration
03200             FunctionType *FTy = FunctionType::get(RetTy, Tys, false);
03201             VectorF =
03202                 Function::Create(FTy, Function::ExternalLinkage, VFnName, M);
03203             VectorF->copyAttributesFrom(F);
03204           }
03205         }
03206         assert(VectorF && "Can't create vector function.");
03207         Entry[Part] = Builder.CreateCall(VectorF, Args);
03208       }
03209 
03210       propagateMetadata(Entry, it);
03211       break;
03212     }
03213 
03214     default:
03215       // All other instructions are unsupported. Scalarize them.
03216       scalarizeInstruction(it);
03217       break;
03218     }// end of switch.
03219   }// end of for_each instr.
03220 }
03221 
03222 void InnerLoopVectorizer::updateAnalysis() {
03223   // Forget the original basic block.
03224   SE->forgetLoop(OrigLoop);
03225 
03226   // Update the dominator tree information.
03227   assert(DT->properlyDominates(LoopBypassBlocks.front(), LoopExitBlock) &&
03228          "Entry does not dominate exit.");
03229 
03230   for (unsigned I = 1, E = LoopBypassBlocks.size(); I != E; ++I)
03231     DT->addNewBlock(LoopBypassBlocks[I], LoopBypassBlocks[I-1]);
03232   DT->addNewBlock(LoopVectorPreHeader, LoopBypassBlocks.back());
03233 
03234   // Due to if predication of stores we might create a sequence of "if(pred)
03235   // a[i] = ...;  " blocks.
03236   for (unsigned i = 0, e = LoopVectorBody.size(); i != e; ++i) {
03237     if (i == 0)
03238       DT->addNewBlock(LoopVectorBody[0], LoopVectorPreHeader);
03239     else if (isPredicatedBlock(i)) {
03240       DT->addNewBlock(LoopVectorBody[i], LoopVectorBody[i-1]);
03241     } else {
03242       DT->addNewBlock(LoopVectorBody[i], LoopVectorBody[i-2]);
03243     }
03244   }
03245 
03246   DT->addNewBlock(LoopMiddleBlock, LoopBypassBlocks[1]);
03247   DT->addNewBlock(LoopScalarPreHeader, LoopBypassBlocks[0]);
03248   DT->changeImmediateDominator(LoopScalarBody, LoopScalarPreHeader);
03249   DT->changeImmediateDominator(LoopExitBlock, LoopBypassBlocks[0]);
03250 
03251   DEBUG(DT->verifyDomTree());
03252 }
03253 
03254 /// \brief Check whether it is safe to if-convert this phi node.
03255 ///
03256 /// Phi nodes with constant expressions that can trap are not safe to if
03257 /// convert.
03258 static bool canIfConvertPHINodes(BasicBlock *BB) {
03259   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
03260     PHINode *Phi = dyn_cast<PHINode>(I);
03261     if (!Phi)
03262       return true;
03263     for (unsigned p = 0, e = Phi->getNumIncomingValues(); p != e; ++p)
03264       if (Constant *C = dyn_cast<Constant>(Phi->getIncomingValue(p)))
03265         if (C->canTrap())
03266           return false;
03267   }
03268   return true;
03269 }
03270 
03271 bool LoopVectorizationLegality::canVectorizeWithIfConvert() {
03272   if (!EnableIfConversion) {
03273     emitAnalysis(VectorizationReport() << "if-conversion is disabled");
03274     return false;
03275   }
03276 
03277   assert(TheLoop->getNumBlocks() > 1 && "Single block loops are vectorizable");
03278 
03279   // A list of pointers that we can safely read and write to.
03280   SmallPtrSet<Value *, 8> SafePointes;
03281 
03282   // Collect safe addresses.
03283   for (Loop::block_iterator BI = TheLoop->block_begin(),
03284          BE = TheLoop->block_end(); BI != BE; ++BI) {
03285     BasicBlock *BB = *BI;
03286 
03287     if (blockNeedsPredication(BB))
03288       continue;
03289 
03290     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
03291       if (LoadInst *LI = dyn_cast<LoadInst>(I))
03292         SafePointes.insert(LI->getPointerOperand());
03293       else if (StoreInst *SI = dyn_cast<StoreInst>(I))
03294         SafePointes.insert(SI->getPointerOperand());
03295     }
03296   }
03297 
03298   // Collect the blocks that need predication.
03299   BasicBlock *Header = TheLoop->getHeader();
03300   for (Loop::block_iterator BI = TheLoop->block_begin(),
03301          BE = TheLoop->block_end(); BI != BE; ++BI) {
03302     BasicBlock *BB = *BI;
03303 
03304     // We don't support switch statements inside loops.
03305     if (!isa<BranchInst>(BB->getTerminator())) {
03306       emitAnalysis(VectorizationReport(BB->getTerminator())
03307                    << "loop contains a switch statement");
03308       return false;
03309     }
03310 
03311     // We must be able to predicate all blocks that need to be predicated.
03312     if (blockNeedsPredication(BB)) {
03313       if (!blockCanBePredicated(BB, SafePointes)) {
03314         emitAnalysis(VectorizationReport(BB->getTerminator())
03315                      << "control flow cannot be substituted for a select");
03316         return false;
03317       }
03318     } else if (BB != Header && !canIfConvertPHINodes(BB)) {
03319       emitAnalysis(VectorizationReport(BB->getTerminator())
03320                    << "control flow cannot be substituted for a select");
03321       return false;
03322     }
03323   }
03324 
03325   // We can if-convert this loop.
03326   return true;
03327 }
03328 
03329 bool LoopVectorizationLegality::canVectorize() {
03330   // We must have a loop in canonical form. Loops with indirectbr in them cannot
03331   // be canonicalized.
03332   if (!TheLoop->getLoopPreheader()) {
03333     emitAnalysis(
03334         VectorizationReport() <<
03335         "loop control flow is not understood by vectorizer");
03336     return false;
03337   }
03338 
03339   // We can only vectorize innermost loops.
03340   if (!TheLoop->getSubLoopsVector().empty()) {
03341     emitAnalysis(VectorizationReport() << "loop is not the innermost loop");
03342     return false;
03343   }
03344 
03345   // We must have a single backedge.
03346   if (TheLoop->getNumBackEdges() != 1) {
03347     emitAnalysis(
03348         VectorizationReport() <<
03349         "loop control flow is not understood by vectorizer");
03350     return false;
03351   }
03352 
03353   // We must have a single exiting block.
03354   if (!TheLoop->getExitingBlock()) {
03355     emitAnalysis(
03356         VectorizationReport() <<
03357         "loop control flow is not understood by vectorizer");
03358     return false;
03359   }
03360 
03361   // We only handle bottom-tested loops, i.e. loop in which the condition is
03362   // checked at the end of each iteration. With that we can assume that all
03363   // instructions in the loop are executed the same number of times.
03364   if (TheLoop->getExitingBlock() != TheLoop->getLoopLatch()) {
03365     emitAnalysis(
03366         VectorizationReport() <<
03367         "loop control flow is not understood by vectorizer");
03368     return false;
03369   }
03370 
03371   // We need to have a loop header.
03372   DEBUG(dbgs() << "LV: Found a loop: " <<
03373         TheLoop->getHeader()->getName() << '\n');
03374 
03375   // Check if we can if-convert non-single-bb loops.
03376   unsigned NumBlocks = TheLoop->getNumBlocks();
03377   if (NumBlocks != 1 && !canVectorizeWithIfConvert()) {
03378     DEBUG(dbgs() << "LV: Can't if-convert the loop.\n");
03379     return false;
03380   }
03381 
03382   // ScalarEvolution needs to be able to find the exit count.
03383   const SCEV *ExitCount = SE->getBackedgeTakenCount(TheLoop);
03384   if (ExitCount == SE->getCouldNotCompute()) {
03385     emitAnalysis(VectorizationReport() <<
03386                  "could not determine number of loop iterations");
03387     DEBUG(dbgs() << "LV: SCEV could not compute the loop exit count.\n");
03388     return false;
03389   }
03390 
03391   // Check if we can vectorize the instructions and CFG in this loop.
03392   if (!canVectorizeInstrs()) {
03393     DEBUG(dbgs() << "LV: Can't vectorize the instructions or CFG\n");
03394     return false;
03395   }
03396 
03397   // Go over each instruction and look at memory deps.
03398   if (!canVectorizeMemory()) {
03399     DEBUG(dbgs() << "LV: Can't vectorize due to memory conflicts\n");
03400     return false;
03401   }
03402 
03403   // Collect all of the variables that remain uniform after vectorization.
03404   collectLoopUniforms();
03405 
03406   DEBUG(dbgs() << "LV: We can vectorize this loop" <<
03407         (LAI->getRuntimePointerCheck()->Need ? " (with a runtime bound check)" :
03408          "")
03409         <<"!\n");
03410 
03411   // Okay! We can vectorize. At this point we don't have any other mem analysis
03412   // which may limit our maximum vectorization factor, so just return true with
03413   // no restrictions.
03414   return true;
03415 }
03416 
03417 static Type *convertPointerToIntegerType(const DataLayout &DL, Type *Ty) {
03418   if (Ty->isPointerTy())
03419     return DL.getIntPtrType(Ty);
03420 
03421   // It is possible that char's or short's overflow when we ask for the loop's
03422   // trip count, work around this by changing the type size.
03423   if (Ty->getScalarSizeInBits() < 32)
03424     return Type::getInt32Ty(Ty->getContext());
03425 
03426   return Ty;
03427 }
03428 
03429 static Type* getWiderType(const DataLayout &DL, Type *Ty0, Type *Ty1) {
03430   Ty0 = convertPointerToIntegerType(DL, Ty0);
03431   Ty1 = convertPointerToIntegerType(DL, Ty1);
03432   if (Ty0->getScalarSizeInBits() > Ty1->getScalarSizeInBits())
03433     return Ty0;
03434   return Ty1;
03435 }
03436 
03437 /// \brief Check that the instruction has outside loop users and is not an
03438 /// identified reduction variable.
03439 static bool hasOutsideLoopUser(const Loop *TheLoop, Instruction *Inst,
03440                                SmallPtrSetImpl<Value *> &Reductions) {
03441   // Reduction instructions are allowed to have exit users. All other
03442   // instructions must not have external users.
03443   if (!Reductions.count(Inst))
03444     //Check that all of the users of the loop are inside the BB.
03445     for (User *U : Inst->users()) {
03446       Instruction *UI = cast<Instruction>(U);
03447       // This user may be a reduction exit value.
03448       if (!TheLoop->contains(UI)) {
03449         DEBUG(dbgs() << "LV: Found an outside user for : " << *UI << '\n');
03450         return true;
03451       }
03452     }
03453   return false;
03454 }
03455 
03456 bool LoopVectorizationLegality::canVectorizeInstrs() {
03457   BasicBlock *PreHeader = TheLoop->getLoopPreheader();
03458   BasicBlock *Header = TheLoop->getHeader();
03459 
03460   // Look for the attribute signaling the absence of NaNs.
03461   Function &F = *Header->getParent();
03462   const DataLayout &DL = F.getParent()->getDataLayout();
03463   if (F.hasFnAttribute("no-nans-fp-math"))
03464     HasFunNoNaNAttr =
03465         F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
03466 
03467   // For each block in the loop.
03468   for (Loop::block_iterator bb = TheLoop->block_begin(),
03469        be = TheLoop->block_end(); bb != be; ++bb) {
03470 
03471     // Scan the instructions in the block and look for hazards.
03472     for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
03473          ++it) {
03474 
03475       if (PHINode *Phi = dyn_cast<PHINode>(it)) {
03476         Type *PhiTy = Phi->getType();
03477         // Check that this PHI type is allowed.
03478         if (!PhiTy->isIntegerTy() &&
03479             !PhiTy->isFloatingPointTy() &&
03480             !PhiTy->isPointerTy()) {
03481           emitAnalysis(VectorizationReport(it)
03482                        << "loop control flow is not understood by vectorizer");
03483           DEBUG(dbgs() << "LV: Found an non-int non-pointer PHI.\n");
03484           return false;
03485         }
03486 
03487         // If this PHINode is not in the header block, then we know that we
03488         // can convert it to select during if-conversion. No need to check if
03489         // the PHIs in this block are induction or reduction variables.
03490         if (*bb != Header) {
03491           // Check that this instruction has no outside users or is an
03492           // identified reduction value with an outside user.
03493           if (!hasOutsideLoopUser(TheLoop, it, AllowedExit))
03494             continue;
03495           emitAnalysis(VectorizationReport(it) <<
03496                        "value could not be identified as "
03497                        "an induction or reduction variable");
03498           return false;
03499         }
03500 
03501         // We only allow if-converted PHIs with exactly two incoming values.
03502         if (Phi->getNumIncomingValues() != 2) {
03503           emitAnalysis(VectorizationReport(it)
03504                        << "control flow not understood by vectorizer");
03505           DEBUG(dbgs() << "LV: Found an invalid PHI.\n");
03506           return false;
03507         }
03508 
03509         // This is the value coming from the preheader.
03510         Value *StartValue = Phi->getIncomingValueForBlock(PreHeader);
03511         ConstantInt *StepValue = nullptr;
03512         // Check if this is an induction variable.
03513         InductionKind IK = isInductionVariable(Phi, StepValue);
03514 
03515         if (IK_NoInduction != IK) {
03516           // Get the widest type.
03517           if (!WidestIndTy)
03518             WidestIndTy = convertPointerToIntegerType(DL, PhiTy);
03519           else
03520             WidestIndTy = getWiderType(DL, PhiTy, WidestIndTy);
03521 
03522           // Int inductions are special because we only allow one IV.
03523           if (IK == IK_IntInduction && StepValue->isOne()) {
03524             // Use the phi node with the widest type as induction. Use the last
03525             // one if there are multiple (no good reason for doing this other
03526             // than it is expedient).
03527             if (!Induction || PhiTy == WidestIndTy)
03528               Induction = Phi;
03529           }
03530 
03531           DEBUG(dbgs() << "LV: Found an induction variable.\n");
03532           Inductions[Phi] = InductionInfo(StartValue, IK, StepValue);
03533 
03534           // Until we explicitly handle the case of an induction variable with
03535           // an outside loop user we have to give up vectorizing this loop.
03536           if (hasOutsideLoopUser(TheLoop, it, AllowedExit)) {
03537             emitAnalysis(VectorizationReport(it) <<
03538                          "use of induction value outside of the "
03539                          "loop is not handled by vectorizer");
03540             return false;
03541           }
03542 
03543           continue;
03544         }
03545 
03546         if (ReductionDescriptor::isReductionPHI(Phi, TheLoop,
03547                                                 Reductions[Phi])) {
03548           AllowedExit.insert(Reductions[Phi].getLoopExitInstr());
03549           continue;
03550         }
03551 
03552         emitAnalysis(VectorizationReport(it) <<
03553                      "value that could not be identified as "
03554                      "reduction is used outside the loop");
03555         DEBUG(dbgs() << "LV: Found an unidentified PHI."<< *Phi <<"\n");
03556         return false;
03557       }// end of PHI handling
03558 
03559       // We handle calls that:
03560       //   * Are debug info intrinsics.
03561       //   * Have a mapping to an IR intrinsic.
03562       //   * Have a vector version available.
03563       CallInst *CI = dyn_cast<CallInst>(it);
03564       if (CI && !getIntrinsicIDForCall(CI, TLI) && !isa<DbgInfoIntrinsic>(CI) &&
03565           !(CI->getCalledFunction() && TLI &&
03566             TLI->isFunctionVectorizable(CI->getCalledFunction()->getName()))) {
03567         emitAnalysis(VectorizationReport(it) <<
03568                      "call instruction cannot be vectorized");
03569         DEBUG(dbgs() << "LV: Found a non-intrinsic, non-libfunc callsite.\n");
03570         return false;
03571       }
03572 
03573       // Intrinsics such as powi,cttz and ctlz are legal to vectorize if the
03574       // second argument is the same (i.e. loop invariant)
03575       if (CI &&
03576           hasVectorInstrinsicScalarOpd(getIntrinsicIDForCall(CI, TLI), 1)) {
03577         if (!SE->isLoopInvariant(SE->getSCEV(CI->getOperand(1)), TheLoop)) {
03578           emitAnalysis(VectorizationReport(it)
03579                        << "intrinsic instruction cannot be vectorized");
03580           DEBUG(dbgs() << "LV: Found unvectorizable intrinsic " << *CI << "\n");
03581           return false;
03582         }
03583       }
03584 
03585       // Check that the instruction return type is vectorizable.
03586       // Also, we can't vectorize extractelement instructions.
03587       if ((!VectorType::isValidElementType(it->getType()) &&
03588            !it->getType()->isVoidTy()) || isa<ExtractElementInst>(it)) {
03589         emitAnalysis(VectorizationReport(it)
03590                      << "instruction return type cannot be vectorized");
03591         DEBUG(dbgs() << "LV: Found unvectorizable type.\n");
03592         return false;
03593       }
03594 
03595       // Check that the stored type is vectorizable.
03596       if (StoreInst *ST = dyn_cast<StoreInst>(it)) {
03597         Type *T = ST->getValueOperand()->getType();
03598         if (!VectorType::isValidElementType(T)) {
03599           emitAnalysis(VectorizationReport(ST) <<
03600                        "store instruction cannot be vectorized");
03601           return false;
03602         }
03603         if (EnableMemAccessVersioning)
03604           collectStridedAccess(ST);
03605       }
03606 
03607       if (EnableMemAccessVersioning)
03608         if (LoadInst *LI = dyn_cast<LoadInst>(it))
03609           collectStridedAccess(LI);
03610 
03611       // Reduction instructions are allowed to have exit users.
03612       // All other instructions must not have external users.
03613       if (hasOutsideLoopUser(TheLoop, it, AllowedExit)) {
03614         emitAnalysis(VectorizationReport(it) <<
03615                      "value cannot be used outside the loop");
03616         return false;
03617       }
03618 
03619     } // next instr.
03620 
03621   }
03622 
03623   if (!Induction) {
03624     DEBUG(dbgs() << "LV: Did not find one integer induction var.\n");
03625     if (Inductions.empty()) {
03626       emitAnalysis(VectorizationReport()
03627                    << "loop induction variable could not be identified");
03628       return false;
03629     }
03630   }
03631 
03632   return true;
03633 }
03634 
03635 ///\brief Remove GEPs whose indices but the last one are loop invariant and
03636 /// return the induction operand of the gep pointer.
03637 static Value *stripGetElementPtr(Value *Ptr, ScalarEvolution *SE, Loop *Lp) {
03638   GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr);
03639   if (!GEP)
03640     return Ptr;
03641 
03642   unsigned InductionOperand = getGEPInductionOperand(GEP);
03643 
03644   // Check that all of the gep indices are uniform except for our induction
03645   // operand.
03646   for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i)
03647     if (i != InductionOperand &&
03648         !SE->isLoopInvariant(SE->getSCEV(GEP->getOperand(i)), Lp))
03649       return Ptr;
03650   return GEP->getOperand(InductionOperand);
03651 }
03652 
03653 ///\brief Look for a cast use of the passed value.
03654 static Value *getUniqueCastUse(Value *Ptr, Loop *Lp, Type *Ty) {
03655   Value *UniqueCast = nullptr;
03656   for (User *U : Ptr->users()) {
03657     CastInst *CI = dyn_cast<CastInst>(U);
03658     if (CI && CI->getType() == Ty) {
03659       if (!UniqueCast)
03660         UniqueCast = CI;
03661       else
03662         return nullptr;
03663     }
03664   }
03665   return UniqueCast;
03666 }
03667 
03668 ///\brief Get the stride of a pointer access in a loop.
03669 /// Looks for symbolic strides "a[i*stride]". Returns the symbolic stride as a
03670 /// pointer to the Value, or null otherwise.
03671 static Value *getStrideFromPointer(Value *Ptr, ScalarEvolution *SE, Loop *Lp) {
03672   const PointerType *PtrTy = dyn_cast<PointerType>(Ptr->getType());
03673   if (!PtrTy || PtrTy->isAggregateType())
03674     return nullptr;
03675 
03676   // Try to remove a gep instruction to make the pointer (actually index at this
03677   // point) easier analyzable. If OrigPtr is equal to Ptr we are analzying the
03678   // pointer, otherwise, we are analyzing the index.
03679   Value *OrigPtr = Ptr;
03680 
03681   // The size of the pointer access.
03682   int64_t PtrAccessSize = 1;
03683 
03684   Ptr = stripGetElementPtr(Ptr, SE, Lp);
03685   const SCEV *V = SE->getSCEV(Ptr);
03686 
03687   if (Ptr != OrigPtr)
03688     // Strip off casts.
03689     while (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V))
03690       V = C->getOperand();
03691 
03692   const SCEVAddRecExpr *S = dyn_cast<SCEVAddRecExpr>(V);
03693   if (!S)
03694     return nullptr;
03695 
03696   V = S->getStepRecurrence(*SE);
03697   if (!V)
03698     return nullptr;
03699 
03700   // Strip off the size of access multiplication if we are still analyzing the
03701   // pointer.
03702   if (OrigPtr == Ptr) {
03703     const DataLayout &DL = Lp->getHeader()->getModule()->getDataLayout();
03704     DL.getTypeAllocSize(PtrTy->getElementType());
03705     if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(V)) {
03706       if (M->getOperand(0)->getSCEVType() != scConstant)
03707         return nullptr;
03708 
03709       const APInt &APStepVal =
03710           cast<SCEVConstant>(M->getOperand(0))->getValue()->getValue();
03711 
03712       // Huge step value - give up.
03713       if (APStepVal.getBitWidth() > 64)
03714         return nullptr;
03715 
03716       int64_t StepVal = APStepVal.getSExtValue();
03717       if (PtrAccessSize != StepVal)
03718         return nullptr;
03719       V = M->getOperand(1);
03720     }
03721   }
03722 
03723   // Strip off casts.
03724   Type *StripedOffRecurrenceCast = nullptr;
03725   if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V)) {
03726     StripedOffRecurrenceCast = C->getType();
03727     V = C->getOperand();
03728   }
03729 
03730   // Look for the loop invariant symbolic value.
03731   const SCEVUnknown *U = dyn_cast<SCEVUnknown>(V);
03732   if (!U)
03733     return nullptr;
03734 
03735   Value *Stride = U->getValue();
03736   if (!Lp->isLoopInvariant(Stride))
03737     return nullptr;
03738 
03739   // If we have stripped off the recurrence cast we have to make sure that we
03740   // return the value that is used in this loop so that we can replace it later.
03741   if (StripedOffRecurrenceCast)
03742     Stride = getUniqueCastUse(Stride, Lp, StripedOffRecurrenceCast);
03743 
03744   return Stride;
03745 }
03746 
03747 void LoopVectorizationLegality::collectStridedAccess(Value *MemAccess) {
03748   Value *Ptr = nullptr;
03749   if (LoadInst *LI = dyn_cast<LoadInst>(MemAccess))
03750     Ptr = LI->getPointerOperand();
03751   else if (StoreInst *SI = dyn_cast<StoreInst>(MemAccess))
03752     Ptr = SI->getPointerOperand();
03753   else
03754     return;
03755 
03756   Value *Stride = getStrideFromPointer(Ptr, SE, TheLoop);
03757   if (!Stride)
03758     return;
03759 
03760   DEBUG(dbgs() << "LV: Found a strided access that we can version");
03761   DEBUG(dbgs() << "  Ptr: " << *Ptr << " Stride: " << *Stride << "\n");
03762   Strides[Ptr] = Stride;
03763   StrideSet.insert(Stride);
03764 }
03765 
03766 void LoopVectorizationLegality::collectLoopUniforms() {
03767   // We now know that the loop is vectorizable!
03768   // Collect variables that will remain uniform after vectorization.
03769   std::vector<Value*> Worklist;
03770   BasicBlock *Latch = TheLoop->getLoopLatch();
03771 
03772   // Start with the conditional branch and walk up the block.
03773   Worklist.push_back(Latch->getTerminator()->getOperand(0));
03774 
03775   // Also add all consecutive pointer values; these values will be uniform
03776   // after vectorization (and subsequent cleanup) and, until revectorization is
03777   // supported, all dependencies must also be uniform.
03778   for (Loop::block_iterator B = TheLoop->block_begin(),
03779        BE = TheLoop->block_end(); B != BE; ++B)
03780     for (BasicBlock::iterator I = (*B)->begin(), IE = (*B)->end();
03781          I != IE; ++I)
03782       if (I->getType()->isPointerTy() && isConsecutivePtr(I))
03783         Worklist.insert(Worklist.end(), I->op_begin(), I->op_end());
03784 
03785   while (!Worklist.empty()) {
03786     Instruction *I = dyn_cast<Instruction>(Worklist.back());
03787     Worklist.pop_back();
03788 
03789     // Look at instructions inside this loop.
03790     // Stop when reaching PHI nodes.
03791     // TODO: we need to follow values all over the loop, not only in this block.
03792     if (!I || !TheLoop->contains(I) || isa<PHINode>(I))
03793       continue;
03794 
03795     // This is a known uniform.
03796     Uniforms.insert(I);
03797 
03798     // Insert all operands.
03799     Worklist.insert(Worklist.end(), I->op_begin(), I->op_end());
03800   }
03801 }
03802 
03803 bool LoopVectorizationLegality::canVectorizeMemory() {
03804   LAI = &LAA->getInfo(TheLoop, Strides);
03805   auto &OptionalReport = LAI->getReport();
03806   if (OptionalReport)
03807     emitAnalysis(VectorizationReport(*OptionalReport));
03808   if (!LAI->canVectorizeMemory())
03809     return false;
03810 
03811   if (LAI->hasStoreToLoopInvariantAddress()) {
03812     emitAnalysis(
03813         VectorizationReport()
03814         << "write to a loop invariant address could not be vectorized");
03815     DEBUG(dbgs() << "LV: We don't allow storing to uniform addresses\n");
03816     return false;
03817   }
03818 
03819   if (LAI->getNumRuntimePointerChecks() >
03820       VectorizerParams::RuntimeMemoryCheckThreshold) {
03821     emitAnalysis(VectorizationReport()
03822                  << LAI->getNumRuntimePointerChecks() << " exceeds limit of "
03823                  << VectorizerParams::RuntimeMemoryCheckThreshold
03824                  << " dependent memory operations checked at runtime");
03825     DEBUG(dbgs() << "LV: Too many memory checks needed.\n");
03826     return false;
03827   }
03828   return true;
03829 }
03830 
03831 LoopVectorizationLegality::InductionKind
03832 LoopVectorizationLegality::isInductionVariable(PHINode *Phi,
03833                                                ConstantInt *&StepValue) {
03834   if (!isInductionPHI(Phi, SE, StepValue))
03835     return IK_NoInduction;
03836 
03837   Type *PhiTy = Phi->getType();
03838   // Found an Integer induction variable.
03839   if (PhiTy->isIntegerTy())
03840     return IK_IntInduction;
03841   // Found an Pointer induction variable.
03842   return IK_PtrInduction;
03843 }
03844 
03845 bool LoopVectorizationLegality::isInductionVariable(const Value *V) {
03846   Value *In0 = const_cast<Value*>(V);
03847   PHINode *PN = dyn_cast_or_null<PHINode>(In0);
03848   if (!PN)
03849     return false;
03850 
03851   return Inductions.count(PN);
03852 }
03853 
03854 bool LoopVectorizationLegality::blockNeedsPredication(BasicBlock *BB)  {
03855   return LoopAccessInfo::blockNeedsPredication(BB, TheLoop, DT);
03856 }
03857 
03858 bool LoopVectorizationLegality::blockCanBePredicated(BasicBlock *BB,
03859                                            SmallPtrSetImpl<Value *> &SafePtrs) {
03860   
03861   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
03862     // Check that we don't have a constant expression that can trap as operand.
03863     for (Instruction::op_iterator OI = it->op_begin(), OE = it->op_end();
03864          OI != OE; ++OI) {
03865       if (Constant *C = dyn_cast<Constant>(*OI))
03866         if (C->canTrap())
03867           return false;
03868     }
03869     // We might be able to hoist the load.
03870     if (it->mayReadFromMemory()) {
03871       LoadInst *LI = dyn_cast<LoadInst>(it);
03872       if (!LI)
03873         return false;
03874       if (!SafePtrs.count(LI->getPointerOperand())) {
03875         if (isLegalMaskedLoad(LI->getType(), LI->getPointerOperand())) {
03876           MaskedOp.insert(LI);
03877           continue;
03878         }
03879         return false;
03880       }
03881     }
03882 
03883     // We don't predicate stores at the moment.
03884     if (it->mayWriteToMemory()) {
03885       StoreInst *SI = dyn_cast<StoreInst>(it);
03886       // We only support predication of stores in basic blocks with one
03887       // predecessor.
03888       if (!SI)
03889         return false;
03890 
03891       bool isSafePtr = (SafePtrs.count(SI->getPointerOperand()) != 0);
03892       bool isSinglePredecessor = SI->getParent()->getSinglePredecessor();
03893       
03894       if (++NumPredStores > NumberOfStoresToPredicate || !isSafePtr ||
03895           !isSinglePredecessor) {
03896         // Build a masked store if it is legal for the target, otherwise scalarize
03897         // the block.
03898         bool isLegalMaskedOp =
03899           isLegalMaskedStore(SI->getValueOperand()->getType(),
03900                              SI->getPointerOperand());
03901         if (isLegalMaskedOp) {
03902           --NumPredStores;
03903           MaskedOp.insert(SI);
03904           continue;
03905         }
03906         return false;
03907       }
03908     }
03909     if (it->mayThrow())
03910       return false;
03911 
03912     // The instructions below can trap.
03913     switch (it->getOpcode()) {
03914     default: continue;
03915     case Instruction::UDiv:
03916     case Instruction::SDiv:
03917     case Instruction::URem:
03918     case Instruction::SRem:
03919       return false;
03920     }
03921   }
03922 
03923   return true;
03924 }
03925 
03926 LoopVectorizationCostModel::VectorizationFactor
03927 LoopVectorizationCostModel::selectVectorizationFactor(bool OptForSize) {
03928   // Width 1 means no vectorize
03929   VectorizationFactor Factor = { 1U, 0U };
03930   if (OptForSize && Legal->getRuntimePointerCheck()->Need) {
03931     emitAnalysis(VectorizationReport() <<
03932                  "runtime pointer checks needed. Enable vectorization of this "
03933                  "loop with '#pragma clang loop vectorize(enable)' when "
03934                  "compiling with -Os");
03935     DEBUG(dbgs() << "LV: Aborting. Runtime ptr check is required in Os.\n");
03936     return Factor;
03937   }
03938 
03939   if (!EnableCondStoresVectorization && Legal->getNumPredStores()) {
03940     emitAnalysis(VectorizationReport() <<
03941                  "store that is conditionally executed prevents vectorization");
03942     DEBUG(dbgs() << "LV: No vectorization. There are conditional stores.\n");
03943     return Factor;
03944   }
03945 
03946   // Find the trip count.
03947   unsigned TC = SE->getSmallConstantTripCount(TheLoop);
03948   DEBUG(dbgs() << "LV: Found trip count: " << TC << '\n');
03949 
03950   unsigned WidestType = getWidestType();
03951   unsigned WidestRegister = TTI.getRegisterBitWidth(true);
03952   unsigned MaxSafeDepDist = -1U;
03953   if (Legal->getMaxSafeDepDistBytes() != -1U)
03954     MaxSafeDepDist = Legal->getMaxSafeDepDistBytes() * 8;
03955   WidestRegister = ((WidestRegister < MaxSafeDepDist) ?
03956                     WidestRegister : MaxSafeDepDist);
03957   unsigned MaxVectorSize = WidestRegister / WidestType;
03958   DEBUG(dbgs() << "LV: The Widest type: " << WidestType << " bits.\n");
03959   DEBUG(dbgs() << "LV: The Widest register is: "
03960           << WidestRegister << " bits.\n");
03961 
03962   if (MaxVectorSize == 0) {
03963     DEBUG(dbgs() << "LV: The target has no vector registers.\n");
03964     MaxVectorSize = 1;
03965   }
03966 
03967   assert(MaxVectorSize <= 64 && "Did not expect to pack so many elements"
03968          " into one vector!");
03969 
03970   unsigned VF = MaxVectorSize;
03971 
03972   // If we optimize the program for size, avoid creating the tail loop.
03973   if (OptForSize) {
03974     // If we are unable to calculate the trip count then don't try to vectorize.
03975     if (TC < 2) {
03976       emitAnalysis
03977         (VectorizationReport() <<
03978          "unable to calculate the loop count due to complex control flow");
03979       DEBUG(dbgs() << "LV: Aborting. A tail loop is required in Os.\n");
03980       return Factor;
03981     }
03982 
03983     // Find the maximum SIMD width that can fit within the trip count.
03984     VF = TC % MaxVectorSize;
03985 
03986     if (VF == 0)
03987       VF = MaxVectorSize;
03988 
03989     // If the trip count that we found modulo the vectorization factor is not
03990     // zero then we require a tail.
03991     if (VF < 2) {
03992       emitAnalysis(VectorizationReport() <<
03993                    "cannot optimize for size and vectorize at the "
03994                    "same time. Enable vectorization of this loop "
03995                    "with '#pragma clang loop vectorize(enable)' "
03996                    "when compiling with -Os");
03997       DEBUG(dbgs() << "LV: Aborting. A tail loop is required in Os.\n");
03998       return Factor;
03999     }
04000   }
04001 
04002   int UserVF = Hints->getWidth();
04003   if (UserVF != 0) {
04004     assert(isPowerOf2_32(UserVF) && "VF needs to be a power of two");
04005     DEBUG(dbgs() << "LV: Using user VF " << UserVF << ".\n");
04006 
04007     Factor.Width = UserVF;
04008     return Factor;
04009   }
04010 
04011   float Cost = expectedCost(1);
04012 #ifndef NDEBUG
04013   const float ScalarCost = Cost;
04014 #endif /* NDEBUG */
04015   unsigned Width = 1;
04016   DEBUG(dbgs() << "LV: Scalar loop costs: " << (int)ScalarCost << ".\n");
04017 
04018   bool ForceVectorization = Hints->getForce() == LoopVectorizeHints::FK_Enabled;
04019   // Ignore scalar width, because the user explicitly wants vectorization.
04020   if (ForceVectorization && VF > 1) {
04021     Width = 2;
04022     Cost = expectedCost(Width) / (float)Width;
04023   }
04024 
04025   for (unsigned i=2; i <= VF; i*=2) {
04026     // Notice that the vector loop needs to be executed less times, so
04027     // we need to divide the cost of the vector loops by the width of
04028     // the vector elements.
04029     float VectorCost = expectedCost(i) / (float)i;
04030     DEBUG(dbgs() << "LV: Vector loop of width " << i << " costs: " <<
04031           (int)VectorCost << ".\n");
04032     if (VectorCost < Cost) {
04033       Cost = VectorCost;
04034       Width = i;
04035     }
04036   }
04037 
04038   DEBUG(if (ForceVectorization && Width > 1 && Cost >= ScalarCost) dbgs()
04039         << "LV: Vectorization seems to be not beneficial, "
04040         << "but was forced by a user.\n");
04041   DEBUG(dbgs() << "LV: Selecting VF: "<< Width << ".\n");
04042   Factor.Width = Width;
04043   Factor.Cost = Width * Cost;
04044   return Factor;
04045 }
04046 
04047 unsigned LoopVectorizationCostModel::getWidestType() {
04048   unsigned MaxWidth = 8;
04049   const DataLayout &DL = TheFunction->getParent()->getDataLayout();
04050 
04051   // For each block.
04052   for (Loop::block_iterator bb = TheLoop->block_begin(),
04053        be = TheLoop->block_end(); bb != be; ++bb) {
04054     BasicBlock *BB = *bb;
04055 
04056     // For each instruction in the loop.
04057     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
04058       Type *T = it->getType();
04059 
04060       // Ignore ephemeral values.
04061       if (EphValues.count(it))
04062         continue;
04063 
04064       // Only examine Loads, Stores and PHINodes.
04065       if (!isa<LoadInst>(it) && !isa<StoreInst>(it) && !isa<PHINode>(it))
04066         continue;
04067 
04068       // Examine PHI nodes that are reduction variables.
04069       if (PHINode *PN = dyn_cast<PHINode>(it))
04070         if (!Legal->getReductionVars()->count(PN))
04071           continue;
04072 
04073       // Examine the stored values.
04074       if (StoreInst *ST = dyn_cast<StoreInst>(it))
04075         T = ST->getValueOperand()->getType();
04076 
04077       // Ignore loaded pointer types and stored pointer types that are not
04078       // consecutive. However, we do want to take consecutive stores/loads of
04079       // pointer vectors into account.
04080       if (T->isPointerTy() && !isConsecutiveLoadOrStore(it))
04081         continue;
04082 
04083       MaxWidth = std::max(MaxWidth,
04084                           (unsigned)DL.getTypeSizeInBits(T->getScalarType()));
04085     }
04086   }
04087 
04088   return MaxWidth;
04089 }
04090 
04091 unsigned
04092 LoopVectorizationCostModel::selectUnrollFactor(bool OptForSize,
04093                                                unsigned VF,
04094                                                unsigned LoopCost) {
04095 
04096   // -- The unroll heuristics --
04097   // We unroll the loop in order to expose ILP and reduce the loop overhead.
04098   // There are many micro-architectural considerations that we can't predict
04099   // at this level. For example, frontend pressure (on decode or fetch) due to
04100   // code size, or the number and capabilities of the execution ports.
04101   //
04102   // We use the following heuristics to select the unroll factor:
04103   // 1. If the code has reductions, then we unroll in order to break the cross
04104   // iteration dependency.
04105   // 2. If the loop is really small, then we unroll in order to reduce the loop
04106   // overhead.
04107   // 3. We don't unroll if we think that we will spill registers to memory due
04108   // to the increased register pressure.
04109 
04110   // Use the user preference, unless 'auto' is selected.
04111   int UserUF = Hints->getInterleave();
04112   if (UserUF != 0)
04113     return UserUF;
04114 
04115   // When we optimize for size, we don't unroll.
04116   if (OptForSize)
04117     return 1;
04118 
04119   // We used the distance for the unroll factor.
04120   if (Legal->getMaxSafeDepDistBytes() != -1U)
04121     return 1;
04122 
04123   // Do not unroll loops with a relatively small trip count.
04124   unsigned TC = SE->getSmallConstantTripCount(TheLoop);
04125   if (TC > 1 && TC < TinyTripCountUnrollThreshold)
04126     return 1;
04127 
04128   unsigned TargetNumRegisters = TTI.getNumberOfRegisters(VF > 1);
04129   DEBUG(dbgs() << "LV: The target has " << TargetNumRegisters <<
04130         " registers\n");
04131 
04132   if (VF == 1) {
04133     if (ForceTargetNumScalarRegs.getNumOccurrences() > 0)
04134       TargetNumRegisters = ForceTargetNumScalarRegs;
04135   } else {
04136     if (ForceTargetNumVectorRegs.getNumOccurrences() > 0)
04137       TargetNumRegisters = ForceTargetNumVectorRegs;
04138   }
04139 
04140   LoopVectorizationCostModel::RegisterUsage R = calculateRegisterUsage();
04141   // We divide by these constants so assume that we have at least one
04142   // instruction that uses at least one register.
04143   R.MaxLocalUsers = std::max(R.MaxLocalUsers, 1U);
04144   R.NumInstructions = std::max(R.NumInstructions, 1U);
04145 
04146   // We calculate the unroll factor using the following formula.
04147   // Subtract the number of loop invariants from the number of available
04148   // registers. These registers are used by all of the unrolled instances.
04149   // Next, divide the remaining registers by the number of registers that is
04150   // required by the loop, in order to estimate how many parallel instances
04151   // fit without causing spills. All of this is rounded down if necessary to be
04152   // a power of two. We want power of two unroll factors to simplify any
04153   // addressing operations or alignment considerations.
04154   unsigned UF = PowerOf2Floor((TargetNumRegisters - R.LoopInvariantRegs) /
04155                               R.MaxLocalUsers);
04156 
04157   // Don't count the induction variable as unrolled.
04158   if (EnableIndVarRegisterHeur)
04159     UF = PowerOf2Floor((TargetNumRegisters - R.LoopInvariantRegs - 1) /
04160                        std::max(1U, (R.MaxLocalUsers - 1)));
04161 
04162   // Clamp the unroll factor ranges to reasonable factors.
04163   unsigned MaxInterleaveSize = TTI.getMaxInterleaveFactor();
04164 
04165   // Check if the user has overridden the unroll max.
04166   if (VF == 1) {
04167     if (ForceTargetMaxScalarInterleaveFactor.getNumOccurrences() > 0)
04168       MaxInterleaveSize = ForceTargetMaxScalarInterleaveFactor;
04169   } else {
04170     if (ForceTargetMaxVectorInterleaveFactor.getNumOccurrences() > 0)
04171       MaxInterleaveSize = ForceTargetMaxVectorInterleaveFactor;
04172   }
04173 
04174   // If we did not calculate the cost for VF (because the user selected the VF)
04175   // then we calculate the cost of VF here.
04176   if (LoopCost == 0)
04177     LoopCost = expectedCost(VF);
04178 
04179   // Clamp the calculated UF to be between the 1 and the max unroll factor
04180   // that the target allows.
04181   if (UF > MaxInterleaveSize)
04182     UF = MaxInterleaveSize;
04183   else if (UF < 1)
04184     UF = 1;
04185 
04186   // Unroll if we vectorized this loop and there is a reduction that could
04187   // benefit from unrolling.
04188   if (VF > 1 && Legal->getReductionVars()->size()) {
04189     DEBUG(dbgs() << "LV: Unrolling because of reductions.\n");
04190     return UF;
04191   }
04192 
04193   // Note that if we've already vectorized the loop we will have done the
04194   // runtime check and so unrolling won't require further checks.
04195   bool UnrollingRequiresRuntimePointerCheck =
04196       (VF == 1 && Legal->getRuntimePointerCheck()->Need);
04197 
04198   // We want to unroll small loops in order to reduce the loop overhead and
04199   // potentially expose ILP opportunities.
04200   DEBUG(dbgs() << "LV: Loop cost is " << LoopCost << '\n');
04201   if (!UnrollingRequiresRuntimePointerCheck &&
04202       LoopCost < SmallLoopCost) {
04203     // We assume that the cost overhead is 1 and we use the cost model
04204     // to estimate the cost of the loop and unroll until the cost of the
04205     // loop overhead is about 5% of the cost of the loop.
04206     unsigned SmallUF = std::min(UF, (unsigned)PowerOf2Floor(SmallLoopCost / LoopCost));
04207 
04208     // Unroll until store/load ports (estimated by max unroll factor) are
04209     // saturated.
04210     unsigned NumStores = Legal->getNumStores();
04211     unsigned NumLoads = Legal->getNumLoads();
04212     unsigned StoresUF = UF / (NumStores ? NumStores : 1);
04213     unsigned LoadsUF = UF /  (NumLoads ? NumLoads : 1);
04214 
04215     // If we have a scalar reduction (vector reductions are already dealt with
04216     // by this point), we can increase the critical path length if the loop
04217     // we're unrolling is inside another loop. Limit, by default to 2, so the
04218     // critical path only gets increased by one reduction operation.
04219     if (Legal->getReductionVars()->size() &&
04220         TheLoop->getLoopDepth() > 1) {
04221       unsigned F = static_cast<unsigned>(MaxNestedScalarReductionUF);
04222       SmallUF = std::min(SmallUF, F);
04223       StoresUF = std::min(StoresUF, F);
04224       LoadsUF = std::min(LoadsUF, F);
04225     }
04226 
04227     if (EnableLoadStoreRuntimeUnroll && std::max(StoresUF, LoadsUF) > SmallUF) {
04228       DEBUG(dbgs() << "LV: Unrolling to saturate store or load ports.\n");
04229       return std::max(StoresUF, LoadsUF);
04230     }
04231 
04232     DEBUG(dbgs() << "LV: Unrolling to reduce branch cost.\n");
04233     return SmallUF;
04234   }
04235 
04236   // Unroll if this is a large loop (small loops are already dealt with by this
04237   // point) that could benefit from interleaved unrolling.
04238   bool HasReductions = (Legal->getReductionVars()->size() > 0);
04239   if (TTI.enableAggressiveInterleaving(HasReductions)) {
04240     DEBUG(dbgs() << "LV: Unrolling to expose ILP.\n");
04241     return UF;
04242   }
04243 
04244   DEBUG(dbgs() << "LV: Not Unrolling.\n");
04245   return 1;
04246 }
04247 
04248 LoopVectorizationCostModel::RegisterUsage
04249 LoopVectorizationCostModel::calculateRegisterUsage() {
04250   // This function calculates the register usage by measuring the highest number
04251   // of values that are alive at a single location. Obviously, this is a very
04252   // rough estimation. We scan the loop in a topological order in order and
04253   // assign a number to each instruction. We use RPO to ensure that defs are
04254   // met before their users. We assume that each instruction that has in-loop
04255   // users starts an interval. We record every time that an in-loop value is
04256   // used, so we have a list of the first and last occurrences of each
04257   // instruction. Next, we transpose this data structure into a multi map that
04258   // holds the list of intervals that *end* at a specific location. This multi
04259   // map allows us to perform a linear search. We scan the instructions linearly
04260   // and record each time that a new interval starts, by placing it in a set.
04261   // If we find this value in the multi-map then we remove it from the set.
04262   // The max register usage is the maximum size of the set.
04263   // We also search for instructions that are defined outside the loop, but are
04264   // used inside the loop. We need this number separately from the max-interval
04265   // usage number because when we unroll, loop-invariant values do not take
04266   // more register.
04267   LoopBlocksDFS DFS(TheLoop);
04268   DFS.perform(LI);
04269 
04270   RegisterUsage R;
04271   R.NumInstructions = 0;
04272 
04273   // Each 'key' in the map opens a new interval. The values
04274   // of the map are the index of the 'last seen' usage of the
04275   // instruction that is the key.
04276   typedef DenseMap<Instruction*, unsigned> IntervalMap;
04277   // Maps instruction to its index.
04278   DenseMap<unsigned, Instruction*> IdxToInstr;
04279   // Marks the end of each interval.
04280   IntervalMap EndPoint;
04281   // Saves the list of instruction indices that are used in the loop.
04282   SmallSet<Instruction*, 8> Ends;
04283   // Saves the list of values that are used in the loop but are
04284   // defined outside the loop, such as arguments and constants.
04285   SmallPtrSet<Value*, 8> LoopInvariants;
04286 
04287   unsigned Index = 0;
04288   for (LoopBlocksDFS::RPOIterator bb = DFS.beginRPO(),
04289        be = DFS.endRPO(); bb != be; ++bb) {
04290     R.NumInstructions += (*bb)->size();
04291     for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
04292          ++it) {
04293       Instruction *I = it;
04294       IdxToInstr[Index++] = I;
04295 
04296       // Save the end location of each USE.
04297       for (unsigned i = 0; i < I->getNumOperands(); ++i) {
04298         Value *U = I->getOperand(i);
04299         Instruction *Instr = dyn_cast<Instruction>(U);
04300 
04301         // Ignore non-instruction values such as arguments, constants, etc.
04302         if (!Instr) continue;
04303 
04304         // If this instruction is outside the loop then record it and continue.
04305         if (!TheLoop->contains(Instr)) {
04306           LoopInvariants.insert(Instr);
04307           continue;
04308         }
04309 
04310         // Overwrite previous end points.
04311         EndPoint[Instr] = Index;
04312         Ends.insert(Instr);
04313       }
04314     }
04315   }
04316 
04317   // Saves the list of intervals that end with the index in 'key'.
04318   typedef SmallVector<Instruction*, 2> InstrList;
04319   DenseMap<unsigned, InstrList> TransposeEnds;
04320 
04321   // Transpose the EndPoints to a list of values that end at each index.
04322   for (IntervalMap::iterator it = EndPoint.begin(), e = EndPoint.end();
04323        it != e; ++it)
04324     TransposeEnds[it->second].push_back(it->first);
04325 
04326   SmallSet<Instruction*, 8> OpenIntervals;
04327   unsigned MaxUsage = 0;
04328 
04329 
04330   DEBUG(dbgs() << "LV(REG): Calculating max register usage:\n");
04331   for (unsigned int i = 0; i < Index; ++i) {
04332     Instruction *I = IdxToInstr[i];
04333     // Ignore instructions that are never used within the loop.
04334     if (!Ends.count(I)) continue;
04335 
04336     // Ignore ephemeral values.
04337     if (EphValues.count(I))
04338       continue;
04339 
04340     // Remove all of the instructions that end at this location.
04341     InstrList &List = TransposeEnds[i];
04342     for (unsigned int j=0, e = List.size(); j < e; ++j)
04343       OpenIntervals.erase(List[j]);
04344 
04345     // Count the number of live interals.
04346     MaxUsage = std::max(MaxUsage, OpenIntervals.size());
04347 
04348     DEBUG(dbgs() << "LV(REG): At #" << i << " Interval # " <<
04349           OpenIntervals.size() << '\n');
04350 
04351     // Add the current instruction to the list of open intervals.
04352     OpenIntervals.insert(I);
04353   }
04354 
04355   unsigned Invariant = LoopInvariants.size();
04356   DEBUG(dbgs() << "LV(REG): Found max usage: " << MaxUsage << '\n');
04357   DEBUG(dbgs() << "LV(REG): Found invariant usage: " << Invariant << '\n');
04358   DEBUG(dbgs() << "LV(REG): LoopSize: " << R.NumInstructions << '\n');
04359 
04360   R.LoopInvariantRegs = Invariant;
04361   R.MaxLocalUsers = MaxUsage;
04362   return R;
04363 }
04364 
04365 unsigned LoopVectorizationCostModel::expectedCost(unsigned VF) {
04366   unsigned Cost = 0;
04367 
04368   // For each block.
04369   for (Loop::block_iterator bb = TheLoop->block_begin(),
04370        be = TheLoop->block_end(); bb != be; ++bb) {
04371     unsigned BlockCost = 0;
04372     BasicBlock *BB = *bb;
04373 
04374     // For each instruction in the old loop.
04375     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
04376       // Skip dbg intrinsics.
04377       if (isa<DbgInfoIntrinsic>(it))
04378         continue;
04379 
04380       // Ignore ephemeral values.
04381       if (EphValues.count(it))
04382         continue;
04383 
04384       unsigned C = getInstructionCost(it, VF);
04385 
04386       // Check if we should override the cost.
04387       if (ForceTargetInstructionCost.getNumOccurrences() > 0)
04388         C = ForceTargetInstructionCost;
04389 
04390       BlockCost += C;
04391       DEBUG(dbgs() << "LV: Found an estimated cost of " << C << " for VF " <<
04392             VF << " For instruction: " << *it << '\n');
04393     }
04394 
04395     // We assume that if-converted blocks have a 50% chance of being executed.
04396     // When the code is scalar then some of the blocks are avoided due to CF.
04397     // When the code is vectorized we execute all code paths.
04398     if (VF == 1 && Legal->blockNeedsPredication(*bb))
04399       BlockCost /= 2;
04400 
04401     Cost += BlockCost;
04402   }
04403 
04404   return Cost;
04405 }
04406 
04407 /// \brief Check whether the address computation for a non-consecutive memory
04408 /// access looks like an unlikely candidate for being merged into the indexing
04409 /// mode.
04410 ///
04411 /// We look for a GEP which has one index that is an induction variable and all
04412 /// other indices are loop invariant. If the stride of this access is also
04413 /// within a small bound we decide that this address computation can likely be
04414 /// merged into the addressing mode.
04415 /// In all other cases, we identify the address computation as complex.
04416 static bool isLikelyComplexAddressComputation(Value *Ptr,
04417                                               LoopVectorizationLegality *Legal,
04418                                               ScalarEvolution *SE,
04419                                               const Loop *TheLoop) {
04420   GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr);
04421   if (!Gep)
04422     return true;
04423 
04424   // We are looking for a gep with all loop invariant indices except for one
04425   // which should be an induction variable.
04426   unsigned NumOperands = Gep->getNumOperands();
04427   for (unsigned i = 1; i < NumOperands; ++i) {
04428     Value *Opd = Gep->getOperand(i);
04429     if (!SE->isLoopInvariant(SE->getSCEV(Opd), TheLoop) &&
04430         !Legal->isInductionVariable(Opd))
04431       return true;
04432   }
04433 
04434   // Now we know we have a GEP ptr, %inv, %ind, %inv. Make sure that the step
04435   // can likely be merged into the address computation.
04436   unsigned MaxMergeDistance = 64;
04437 
04438   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Ptr));
04439   if (!AddRec)
04440     return true;
04441 
04442   // Check the step is constant.
04443   const SCEV *Step = AddRec->getStepRecurrence(*SE);
04444   // Calculate the pointer stride and check if it is consecutive.
04445   const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
04446   if (!C)
04447     return true;
04448 
04449   const APInt &APStepVal = C->getValue()->getValue();
04450 
04451   // Huge step value - give up.
04452   if (APStepVal.getBitWidth() > 64)
04453     return true;
04454 
04455   int64_t StepVal = APStepVal.getSExtValue();
04456 
04457   return StepVal > MaxMergeDistance;
04458 }
04459 
04460 static bool isStrideMul(Instruction *I, LoopVectorizationLegality *Legal) {
04461   if (Legal->hasStride(I->getOperand(0)) || Legal->hasStride(I->getOperand(1)))
04462     return true;
04463   return false;
04464 }
04465 
04466 unsigned
04467 LoopVectorizationCostModel::getInstructionCost(Instruction *I, unsigned VF) {
04468   // If we know that this instruction will remain uniform, check the cost of
04469   // the scalar version.
04470   if (Legal->isUniformAfterVectorization(I))
04471     VF = 1;
04472 
04473   Type *RetTy = I->getType();
04474   Type *VectorTy = ToVectorTy(RetTy, VF);
04475 
04476   // TODO: We need to estimate the cost of intrinsic calls.
04477   switch (I->getOpcode()) {
04478   case Instruction::GetElementPtr:
04479     // We mark this instruction as zero-cost because the cost of GEPs in
04480     // vectorized code depends on whether the corresponding memory instruction
04481     // is scalarized or not. Therefore, we handle GEPs with the memory
04482     // instruction cost.
04483     return 0;
04484   case Instruction::Br: {
04485     return TTI.getCFInstrCost(I->getOpcode());
04486   }
04487   case Instruction::PHI:
04488     //TODO: IF-converted IFs become selects.
04489     return 0;
04490   case Instruction::Add:
04491   case Instruction::FAdd:
04492   case Instruction::Sub:
04493   case Instruction::FSub:
04494   case Instruction::Mul:
04495   case Instruction::FMul:
04496   case Instruction::UDiv:
04497   case Instruction::SDiv:
04498   case Instruction::FDiv:
04499   case Instruction::URem:
04500   case Instruction::SRem:
04501   case Instruction::FRem:
04502   case Instruction::Shl:
04503   case Instruction::LShr:
04504   case Instruction::AShr:
04505   case Instruction::And:
04506   case Instruction::Or:
04507   case Instruction::Xor: {
04508     // Since we will replace the stride by 1 the multiplication should go away.
04509     if (I->getOpcode() == Instruction::Mul && isStrideMul(I, Legal))
04510       return 0;
04511     // Certain instructions can be cheaper to vectorize if they have a constant
04512     // second vector operand. One example of this are shifts on x86.
04513     TargetTransformInfo::OperandValueKind Op1VK =
04514       TargetTransformInfo::OK_AnyValue;
04515     TargetTransformInfo::OperandValueKind Op2VK =
04516       TargetTransformInfo::OK_AnyValue;
04517     TargetTransformInfo::OperandValueProperties Op1VP =
04518         TargetTransformInfo::OP_None;
04519     TargetTransformInfo::OperandValueProperties Op2VP =
04520         TargetTransformInfo::OP_None;
04521     Value *Op2 = I->getOperand(1);
04522 
04523     // Check for a splat of a constant or for a non uniform vector of constants.
04524     if (isa<ConstantInt>(Op2)) {
04525       ConstantInt *CInt = cast<ConstantInt>(Op2);
04526       if (CInt && CInt->getValue().isPowerOf2())
04527         Op2VP = TargetTransformInfo::OP_PowerOf2;
04528       Op2VK = TargetTransformInfo::OK_UniformConstantValue;
04529     } else if (isa<ConstantVector>(Op2) || isa<ConstantDataVector>(Op2)) {
04530       Op2VK = TargetTransformInfo::OK_NonUniformConstantValue;
04531       Constant *SplatValue = cast<Constant>(Op2)->getSplatValue();
04532       if (SplatValue) {
04533         ConstantInt *CInt = dyn_cast<ConstantInt>(SplatValue);
04534         if (CInt && CInt->getValue().isPowerOf2())
04535           Op2VP = TargetTransformInfo::OP_PowerOf2;
04536         Op2VK = TargetTransformInfo::OK_UniformConstantValue;
04537       }
04538     }
04539 
04540     return TTI.getArithmeticInstrCost(I->getOpcode(), VectorTy, Op1VK, Op2VK,
04541                                       Op1VP, Op2VP);
04542   }
04543   case Instruction::Select: {
04544     SelectInst *SI = cast<SelectInst>(I);
04545     const SCEV *CondSCEV = SE->getSCEV(SI->getCondition());
04546     bool ScalarCond = (SE->isLoopInvariant(CondSCEV, TheLoop));
04547     Type *CondTy = SI->getCondition()->getType();
04548     if (!ScalarCond)
04549       CondTy = VectorType::get(CondTy, VF);
04550 
04551     return TTI.getCmpSelInstrCost(I->getOpcode(), VectorTy, CondTy);
04552   }
04553   case Instruction::ICmp:
04554   case Instruction::FCmp: {
04555     Type *ValTy = I->getOperand(0)->getType();
04556     VectorTy = ToVectorTy(ValTy, VF);
04557     return TTI.getCmpSelInstrCost(I->getOpcode(), VectorTy);
04558   }
04559   case Instruction::Store:
04560   case Instruction::Load: {
04561     StoreInst *SI = dyn_cast<StoreInst>(I);
04562     LoadInst *LI = dyn_cast<LoadInst>(I);
04563     Type *ValTy = (SI ? SI->getValueOperand()->getType() :
04564                    LI->getType());
04565     VectorTy = ToVectorTy(ValTy, VF);
04566 
04567     unsigned Alignment = SI ? SI->getAlignment() : LI->getAlignment();
04568     unsigned AS = SI ? SI->getPointerAddressSpace() :
04569       LI->getPointerAddressSpace();
04570     Value *Ptr = SI ? SI->getPointerOperand() : LI->getPointerOperand();
04571     // We add the cost of address computation here instead of with the gep
04572     // instruction because only here we know whether the operation is
04573     // scalarized.
04574     if (VF == 1)
04575       return TTI.getAddressComputationCost(VectorTy) +
04576         TTI.getMemoryOpCost(I->getOpcode(), VectorTy, Alignment, AS);
04577 
04578     // Scalarized loads/stores.
04579     int ConsecutiveStride = Legal->isConsecutivePtr(Ptr);
04580     bool Reverse = ConsecutiveStride < 0;
04581     const DataLayout &DL = I->getModule()->getDataLayout();
04582     unsigned ScalarAllocatedSize = DL.getTypeAllocSize(ValTy);
04583     unsigned VectorElementSize = DL.getTypeStoreSize(VectorTy) / VF;
04584     if (!ConsecutiveStride || ScalarAllocatedSize != VectorElementSize) {
04585       bool IsComplexComputation =
04586         isLikelyComplexAddressComputation(Ptr, Legal, SE, TheLoop);
04587       unsigned Cost = 0;
04588       // The cost of extracting from the value vector and pointer vector.
04589       Type *PtrTy = ToVectorTy(Ptr->getType(), VF);
04590       for (unsigned i = 0; i < VF; ++i) {
04591         //  The cost of extracting the pointer operand.
04592         Cost += TTI.getVectorInstrCost(Instruction::ExtractElement, PtrTy, i);
04593         // In case of STORE, the cost of ExtractElement from the vector.
04594         // In case of LOAD, the cost of InsertElement into the returned
04595         // vector.
04596         Cost += TTI.getVectorInstrCost(SI ? Instruction::ExtractElement :
04597                                             Instruction::InsertElement,
04598                                             VectorTy, i);
04599       }
04600 
04601       // The cost of the scalar loads/stores.
04602       Cost += VF * TTI.getAddressComputationCost(PtrTy, IsComplexComputation);
04603       Cost += VF * TTI.getMemoryOpCost(I->getOpcode(), ValTy->getScalarType(),
04604                                        Alignment, AS);
04605       return Cost;
04606     }
04607 
04608     // Wide load/stores.
04609     unsigned Cost = TTI.getAddressComputationCost(VectorTy);
04610     if (Legal->isMaskRequired(I))
04611       Cost += TTI.getMaskedMemoryOpCost(I->getOpcode(), VectorTy, Alignment,
04612                                         AS);
04613     else
04614       Cost += TTI.getMemoryOpCost(I->getOpcode(), VectorTy, Alignment, AS);
04615 
04616     if (Reverse)
04617       Cost += TTI.getShuffleCost(TargetTransformInfo::SK_Reverse,
04618                                   VectorTy, 0);
04619     return Cost;
04620   }
04621   case Instruction::ZExt:
04622   case Instruction::SExt:
04623   case Instruction::FPToUI:
04624   case Instruction::FPToSI:
04625   case Instruction::FPExt:
04626   case Instruction::PtrToInt:
04627   case Instruction::IntToPtr:
04628   case Instruction::SIToFP:
04629   case Instruction::UIToFP:
04630   case Instruction::Trunc:
04631   case Instruction::FPTrunc:
04632   case Instruction::BitCast: {
04633     // We optimize the truncation of induction variable.
04634     // The cost of these is the same as the scalar operation.
04635     if (I->getOpcode() == Instruction::Trunc &&
04636         Legal->isInductionVariable(I->getOperand(0)))
04637       return TTI.getCastInstrCost(I->getOpcode(), I->getType(),
04638                                   I->getOperand(0)->getType());
04639 
04640     Type *SrcVecTy = ToVectorTy(I->getOperand(0)->getType(), VF);
04641     return TTI.getCastInstrCost(I->getOpcode(), VectorTy, SrcVecTy);
04642   }
04643   case Instruction::Call: {
04644     bool NeedToScalarize;
04645     CallInst *CI = cast<CallInst>(I);
04646     unsigned CallCost = getVectorCallCost(CI, VF, TTI, TLI, NeedToScalarize);
04647     if (getIntrinsicIDForCall(CI, TLI))
04648       return std::min(CallCost, getVectorIntrinsicCost(CI, VF, TTI, TLI));
04649     return CallCost;
04650   }
04651   default: {
04652     // We are scalarizing the instruction. Return the cost of the scalar
04653     // instruction, plus the cost of insert and extract into vector
04654     // elements, times the vector width.
04655     unsigned Cost = 0;
04656 
04657     if (!RetTy->isVoidTy() && VF != 1) {
04658       unsigned InsCost = TTI.getVectorInstrCost(Instruction::InsertElement,
04659                                                 VectorTy);
04660       unsigned ExtCost = TTI.getVectorInstrCost(Instruction::ExtractElement,
04661                                                 VectorTy);
04662 
04663       // The cost of inserting the results plus extracting each one of the
04664       // operands.
04665       Cost += VF * (InsCost + ExtCost * I->getNumOperands());
04666     }
04667 
04668     // The cost of executing VF copies of the scalar instruction. This opcode
04669     // is unknown. Assume that it is the same as 'mul'.
04670     Cost += VF * TTI.getArithmeticInstrCost(Instruction::Mul, VectorTy);
04671     return Cost;
04672   }
04673   }// end of switch.
04674 }
04675 
04676 char LoopVectorize::ID = 0;
04677 static const char lv_name[] = "Loop Vectorization";
04678 INITIALIZE_PASS_BEGIN(LoopVectorize, LV_NAME, lv_name, false, false)
04679 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
04680 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
04681 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
04682 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfo)
04683 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
04684 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
04685 INITIALIZE_PASS_DEPENDENCY(LCSSA)
04686 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
04687 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
04688 INITIALIZE_PASS_DEPENDENCY(LoopAccessAnalysis)
04689 INITIALIZE_PASS_END(LoopVectorize, LV_NAME, lv_name, false, false)
04690 
04691 namespace llvm {
04692   Pass *createLoopVectorizePass(bool NoUnrolling, bool AlwaysVectorize) {
04693     return new LoopVectorize(NoUnrolling, AlwaysVectorize);
04694   }
04695 }
04696 
04697 bool LoopVectorizationCostModel::isConsecutiveLoadOrStore(Instruction *Inst) {
04698   // Check for a store.
04699   if (StoreInst *ST = dyn_cast<StoreInst>(Inst))
04700     return Legal->isConsecutivePtr(ST->getPointerOperand()) != 0;
04701 
04702   // Check for a load.
04703   if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
04704     return Legal->isConsecutivePtr(LI->getPointerOperand()) != 0;
04705 
04706   return false;
04707 }
04708 
04709 
04710 void InnerLoopUnroller::scalarizeInstruction(Instruction *Instr,
04711                                              bool IfPredicateStore) {
04712   assert(!Instr->getType()->isAggregateType() && "Can't handle vectors");
04713   // Holds vector parameters or scalars, in case of uniform vals.
04714   SmallVector<VectorParts, 4> Params;
04715 
04716   setDebugLocFromInst(Builder, Instr);
04717 
04718   // Find all of the vectorized parameters.
04719   for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) {
04720     Value *SrcOp = Instr->getOperand(op);
04721 
04722     // If we are accessing the old induction variable, use the new one.
04723     if (SrcOp == OldInduction) {
04724       Params.push_back(getVectorValue(SrcOp));
04725       continue;
04726     }
04727 
04728     // Try using previously calculated values.
04729     Instruction *SrcInst = dyn_cast<Instruction>(SrcOp);
04730 
04731     // If the src is an instruction that appeared earlier in the basic block
04732     // then it should already be vectorized.
04733     if (SrcInst && OrigLoop->contains(SrcInst)) {
04734       assert(WidenMap.has(SrcInst) && "Source operand is unavailable");
04735       // The parameter is a vector value from earlier.
04736       Params.push_back(WidenMap.get(SrcInst));
04737     } else {
04738       // The parameter is a scalar from outside the loop. Maybe even a constant.
04739       VectorParts Scalars;
04740       Scalars.append(UF, SrcOp);
04741       Params.push_back(Scalars);
04742     }
04743   }
04744 
04745   assert(Params.size() == Instr->getNumOperands() &&
04746          "Invalid number of operands");
04747 
04748   // Does this instruction return a value ?
04749   bool IsVoidRetTy = Instr->getType()->isVoidTy();
04750 
04751   Value *UndefVec = IsVoidRetTy ? nullptr :
04752   UndefValue::get(Instr->getType());
04753   // Create a new entry in the WidenMap and initialize it to Undef or Null.
04754   VectorParts &VecResults = WidenMap.splat(Instr, UndefVec);
04755 
04756   Instruction *InsertPt = Builder.GetInsertPoint();
04757   BasicBlock *IfBlock = Builder.GetInsertBlock();
04758   BasicBlock *CondBlock = nullptr;
04759 
04760   VectorParts Cond;
04761   Loop *VectorLp = nullptr;
04762   if (IfPredicateStore) {
04763     assert(Instr->getParent()->getSinglePredecessor() &&
04764            "Only support single predecessor blocks");
04765     Cond = createEdgeMask(Instr->getParent()->getSinglePredecessor(),
04766                           Instr->getParent());
04767     VectorLp = LI->getLoopFor(IfBlock);
04768     assert(VectorLp && "Must have a loop for this block");
04769   }
04770 
04771   // For each vector unroll 'part':
04772   for (unsigned Part = 0; Part < UF; ++Part) {
04773     // For each scalar that we create:
04774 
04775     // Start an "if (pred) a[i] = ..." block.
04776     Value *Cmp = nullptr;
04777     if (IfPredicateStore) {
04778       if (Cond[Part]->getType()->isVectorTy())
04779         Cond[Part] =
04780             Builder.CreateExtractElement(Cond[Part], Builder.getInt32(0));
04781       Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Cond[Part],
04782                                ConstantInt::get(Cond[Part]->getType(), 1));
04783       CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.store");
04784       LoopVectorBody.push_back(CondBlock);
04785       VectorLp->addBasicBlockToLoop(CondBlock, *LI);
04786       // Update Builder with newly created basic block.
04787       Builder.SetInsertPoint(InsertPt);
04788     }
04789 
04790     Instruction *Cloned = Instr->clone();
04791       if (!IsVoidRetTy)
04792         Cloned->setName(Instr->getName() + ".cloned");
04793       // Replace the operands of the cloned instructions with extracted scalars.
04794       for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) {
04795         Value *Op = Params[op][Part];
04796         Cloned->setOperand(op, Op);
04797       }
04798 
04799       // Place the cloned scalar in the new loop.
04800       Builder.Insert(Cloned);
04801 
04802       // If the original scalar returns a value we need to place it in a vector
04803       // so that future users will be able to use it.
04804       if (!IsVoidRetTy)
04805         VecResults[Part] = Cloned;
04806 
04807     // End if-block.
04808       if (IfPredicateStore) {
04809         BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else");
04810         LoopVectorBody.push_back(NewIfBlock);
04811         VectorLp->addBasicBlockToLoop(NewIfBlock, *LI);
04812         Builder.SetInsertPoint(InsertPt);
04813         Instruction *OldBr = IfBlock->getTerminator();
04814         BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
04815         OldBr->eraseFromParent();
04816         IfBlock = NewIfBlock;
04817       }
04818   }
04819 }
04820 
04821 void InnerLoopUnroller::vectorizeMemoryInstruction(Instruction *Instr) {
04822   StoreInst *SI = dyn_cast<StoreInst>(Instr);
04823   bool IfPredicateStore = (SI && Legal->blockNeedsPredication(SI->getParent()));
04824 
04825   return scalarizeInstruction(Instr, IfPredicateStore);
04826 }
04827 
04828 Value *InnerLoopUnroller::reverseVector(Value *Vec) {
04829   return Vec;
04830 }
04831 
04832 Value *InnerLoopUnroller::getBroadcastInstrs(Value *V) {
04833   return V;
04834 }
04835 
04836 Value *InnerLoopUnroller::getStepVector(Value *Val, int StartIdx, Value *Step) {
04837   // When unrolling and the VF is 1, we only need to add a simple scalar.
04838   Type *ITy = Val->getType();
04839   assert(!ITy->isVectorTy() && "Val must be a scalar");
04840   Constant *C = ConstantInt::get(ITy, StartIdx);
04841   return Builder.CreateAdd(Val, Builder.CreateMul(C, Step), "induction");
04842 }