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