lib/Transforms/Vectorize/LoopVectorize.cpp

   1 //===- LoopVectorize.cpp - A Loop Vectorizer ------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This is the LLVM loop vectorizer. This pass modifies 'vectorizable' loops
  11 // and generates target-independent LLVM-IR. Legalization of the IR is done
  12 // in the codegen. However, the vectorizes uses (will use) the codegen
  13 // interfaces to generate IR that is likely to result in an optimal binary.
  14 //
  15 // The loop vectorizer combines consecutive loop iteration into a single
  16 // 'wide' iteration. After this transformation the index is incremented
  17 // by the SIMD vector width, and not by one.
  18 //
  19 // This pass has three parts:
  20 // 1. The main loop pass that drives the different parts.
  21 // 2. LoopVectorizationLegality - A unit that checks for the legality
  22 //    of the vectorization.
  23 // 3. SingleBlockLoopVectorizer - A unit that performs the actual
  24 //    widening of instructions.
  25 // 4. LoopVectorizationCostModel - A unit that checks for the profitability
  26 //    of vectorization. It decides on the optimal vector width, which
  27 //    can be one, if vectorization is not profitable.
  28 //===----------------------------------------------------------------------===//
  29 //
  30 // The reduction-variable vectorization is based on the paper:
  31 //  D. Nuzman and R. Henderson. Multi-platform Auto-vectorization.
  32 //
  33 // Variable uniformity checks are inspired by:
  34 // Karrenberg, R. and Hack, S. Whole Function Vectorization.
  35 //
  36 // Other ideas/concepts are from:
  37 //  A. Zaks and D. Nuzman. Autovectorization in GCC-two years later.
  38 //
  39 //===----------------------------------------------------------------------===//
  40 #define LV_NAME "loop-vectorize"
  41 #define DEBUG_TYPE LV_NAME
  42 #include "llvm/Constants.h"
  43 #include "llvm/DerivedTypes.h"
  44 #include "llvm/Instructions.h"
  45 #include "llvm/LLVMContext.h"
  46 #include "llvm/Pass.h"
  47 #include "llvm/Analysis/LoopPass.h"
  48 #include "llvm/Value.h"
  49 #include "llvm/Function.h"
  50 #include "llvm/Analysis/Verifier.h"
  51 #include "llvm/Module.h"
  52 #include "llvm/Type.h"
  53 #include "llvm/ADT/SmallVector.h"
  54 #include "llvm/ADT/StringExtras.h"
  55 #include "llvm/Analysis/AliasAnalysis.h"
  56 #include "llvm/Analysis/AliasSetTracker.h"
  57 #include "llvm/Analysis/ScalarEvolution.h"
  58 #include "llvm/Analysis/Dominators.h"
  59 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  60 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  61 #include "llvm/Analysis/LoopInfo.h"
  62 #include "llvm/Analysis/ValueTracking.h"
  63 #include "llvm/Transforms/Scalar.h"
  64 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  65 #include "llvm/TargetTransformInfo.h"
  66 #include "llvm/Support/CommandLine.h"
  67 #include "llvm/Support/Debug.h"
  68 #include "llvm/Support/raw_ostream.h"
  69 #include "llvm/DataLayout.h"
  70 #include "llvm/Transforms/Utils/Local.h"
  71 #include <algorithm>
  72 using namespace llvm;
  73
  74 static cl::opt<unsigned>
  75 VectorizationFactor("force-vector-width", cl::init(0), cl::Hidden,
  76           cl::desc("Set the default vectorization width. Zero is autoselect."));
  77
  78 /// We don't vectorize loops with a known constant trip count below this number.
  79 const unsigned TinyTripCountThreshold = 16;
  80
  81 /// When performing a runtime memory check, do not check more than this
  82 /// number of pointers. Notice that the check is quadratic!
  83 const unsigned RuntimeMemoryCheckThreshold = 2;
  84
  85 namespace {
  86
  87 // Forward declarations.
  88 class LoopVectorizationLegality;
  89 class LoopVectorizationCostModel;
  90
  91 /// SingleBlockLoopVectorizer vectorizes loops which contain only one basic
  92 /// block to a specified vectorization factor (VF).
  93 /// This class performs the widening of scalars into vectors, or multiple
  94 /// scalars. This class also implements the following features:
  95 /// * It inserts an epilogue loop for handling loops that don't have iteration
  96 ///   counts that are known to be a multiple of the vectorization factor.
  97 /// * It handles the code generation for reduction variables.
  98 /// * Scalarization (implementation using scalars) of un-vectorizable
  99 ///   instructions.
 100 /// SingleBlockLoopVectorizer does not perform any vectorization-legality
 101 /// checks, and relies on the caller to check for the different legality
 102 /// aspects. The SingleBlockLoopVectorizer relies on the
 103 /// LoopVectorizationLegality class to provide information about the induction
 104 /// and reduction variables that were found to a given vectorization factor.
 105 class SingleBlockLoopVectorizer {
 106 public:
 107   /// Ctor.
 108   SingleBlockLoopVectorizer(Loop *Orig, ScalarEvolution *Se, LoopInfo *Li,
 109                             DominatorTree *dt, DataLayout *dl,
 110                             LPPassManager *Lpm,
 111                             unsigned VecWidth):
 112   OrigLoop(Orig), SE(Se), LI(Li), DT(dt), DL(dl), LPM(Lpm), VF(VecWidth),
 113   Builder(Se->getContext()), Induction(0), OldInduction(0) { }
 114
 115   // Perform the actual loop widening (vectorization).
 116   void vectorize(LoopVectorizationLegality *Legal) {
 117     ///Create a new empty loop. Unlink the old loop and connect the new one.
 118     createEmptyLoop(Legal);
 119     /// Widen each instruction in the old loop to a new one in the new loop.
 120     /// Use the Legality module to find the induction and reduction variables.
 121     vectorizeLoop(Legal);
 122     // Register the new loop and update the analysis passes.
 123     updateAnalysis();
 124  }
 125
 126 private:
 127   /// Create an empty loop, based on the loop ranges of the old loop.
 128   void createEmptyLoop(LoopVectorizationLegality *Legal);
 129   /// Copy and widen the instructions from the old loop.
 130   void vectorizeLoop(LoopVectorizationLegality *Legal);
 131   /// Insert the new loop to the loop hierarchy and pass manager
 132   /// and update the analysis passes.
 133   void updateAnalysis();
 134
 135   /// This instruction is un-vectorizable. Implement it as a sequence
 136   /// of scalars.
 137   void scalarizeInstruction(Instruction *Instr);
 138
 139   /// Create a broadcast instruction. This method generates a broadcast
 140   /// instruction (shuffle) for loop invariant values and for the induction
 141   /// value. If this is the induction variable then we extend it to N, N+1, ...
 142   /// this is needed because each iteration in the loop corresponds to a SIMD
 143   /// element.
 144   Value *getBroadcastInstrs(Value *V);
 145
 146   /// This is a helper function used by getBroadcastInstrs. It adds 0, 1, 2 ..
 147   /// for each element in the vector. Starting from zero.
 148   Value *getConsecutiveVector(Value* Val);
 149
 150   /// When we go over instructions in the basic block we rely on previous
 151   /// values within the current basic block or on loop invariant values.
 152   /// When we widen (vectorize) values we place them in the map. If the values
 153   /// are not within the map, they have to be loop invariant, so we simply
 154   /// broadcast them into a vector.
 155   Value *getVectorValue(Value *V);
 156
 157   /// Get a uniform vector of constant integers. We use this to get
 158   /// vectors of ones and zeros for the reduction code.
 159   Constant* getUniformVector(unsigned Val, Type* ScalarTy);
 160
 161   typedef DenseMap<Value*, Value*> ValueMap;
 162
 163   /// The original loop.
 164   Loop *OrigLoop;
 165   // Scev analysis to use.
 166   ScalarEvolution *SE;
 167   // Loop Info.
 168   LoopInfo *LI;
 169   // Dominator Tree.
 170   DominatorTree *DT;
 171   // Data Layout;
 172   DataLayout *DL;
 173   // Loop Pass Manager;
 174   LPPassManager *LPM;
 175   // The vectorization factor to use.
 176   unsigned VF;
 177
 178   // The builder that we use
 179   IRBuilder<> Builder;
 180
 181   // --- Vectorization state ---
 182
 183   /// The vector-loop preheader.
 184   BasicBlock *LoopVectorPreHeader;
 185   /// The scalar-loop preheader.
 186   BasicBlock *LoopScalarPreHeader;
 187   /// Middle Block between the vector and the scalar.
 188   BasicBlock *LoopMiddleBlock;
 189   ///The ExitBlock of the scalar loop.
 190   BasicBlock *LoopExitBlock;
 191   ///The vector loop body.
 192   BasicBlock *LoopVectorBody;
 193   ///The scalar loop body.
 194   BasicBlock *LoopScalarBody;
 195   ///The first bypass block.
 196   BasicBlock *LoopBypassBlock;
 197
 198   /// The new Induction variable which was added to the new block.
 199   PHINode *Induction;
 200   /// The induction variable of the old basic block.
 201   PHINode *OldInduction;
 202   // Maps scalars to widened vectors.
 203   ValueMap WidenMap;
 204 };
 205
 206 /// LoopVectorizationLegality checks if it is legal to vectorize a loop, and
 207 /// to what vectorization factor.
 208 /// This class does not look at the profitability of vectorization, only the
 209 /// legality. This class has two main kinds of checks:
 210 /// * Memory checks - The code in canVectorizeMemory checks if vectorization
 211 ///   will change the order of memory accesses in a way that will change the
 212 ///   correctness of the program.
 213 /// * Scalars checks - The code in canVectorizeBlock checks for a number
 214 ///   of different conditions, such as the availability of a single induction
 215 ///   variable, that all types are supported and vectorize-able, etc.
 216 /// This code reflects the capabilities of SingleBlockLoopVectorizer.
 217 /// This class is also used by SingleBlockLoopVectorizer for identifying
 218 /// induction variable and the different reduction variables.
 219 class LoopVectorizationLegality {
 220 public:
 221   LoopVectorizationLegality(Loop *Lp, ScalarEvolution *Se, DataLayout *Dl):
 222   TheLoop(Lp), SE(Se), DL(Dl), Induction(0) { }
 223
 224   /// This represents the kinds of reductions that we support.
 225   enum ReductionKind {
 226     NoReduction, /// Not a reduction.
 227     IntegerAdd,  /// Sum of numbers.
 228     IntegerMult, /// Product of numbers.
 229     IntegerOr,   /// Bitwise or logical OR of numbers.
 230     IntegerAnd,  /// Bitwise or logical AND of numbers.
 231     IntegerXor   /// Bitwise or logical XOR of numbers.
 232   };
 233
 234   /// This POD struct holds information about reduction variables.
 235   struct ReductionDescriptor {
 236     // Default C'tor
 237     ReductionDescriptor():
 238     StartValue(0), LoopExitInstr(0), Kind(NoReduction) {}
 239
 240     // C'tor.
 241     ReductionDescriptor(Value *Start, Instruction *Exit, ReductionKind K):
 242     StartValue(Start), LoopExitInstr(Exit), Kind(K) {}
 243
 244     // The starting value of the reduction.
 245     // It does not have to be zero!
 246     Value *StartValue;
 247     // The instruction who's value is used outside the loop.
 248     Instruction *LoopExitInstr;
 249     // The kind of the reduction.
 250     ReductionKind Kind;
 251   };
 252
 253   // This POD struct holds information about the memory runtime legality
 254   // check that a group of pointers do not overlap.
 255   struct RuntimePointerCheck {
 256     RuntimePointerCheck(): Need(false) {}
 257
 258     /// Reset the state of the pointer runtime information.
 259     void reset() {
 260       Need = false;
 261       Pointers.clear();
 262       Starts.clear();
 263       Ends.clear();
 264     }
 265
 266     /// Insert a pointer and calculate the start and end SCEVs.
 267     void insert_pointer(ScalarEvolution *SE, Loop *Lp, Value *Ptr) {
 268       const SCEV *Sc = SE->getSCEV(Ptr);
 269       const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc);
 270       assert(AR && "Invalid addrec expression");
 271       const SCEV *Ex = SE->getExitCount(Lp, Lp->getHeader());
 272       const SCEV *ScEnd = AR->evaluateAtIteration(Ex, *SE);
 273       Pointers.push_back(Ptr);
 274       Starts.push_back(AR->getStart());
 275       Ends.push_back(ScEnd);
 276     }
 277
 278     /// This flag indicates if we need to add the runtime check.
 279     bool Need;
 280     /// Holds the pointers that we need to check.
 281     SmallVector<Value*, 2> Pointers;
 282     /// Holds the pointer value at the beginning of the loop.
 283     SmallVector<const SCEV*, 2> Starts;
 284     /// Holds the pointer value at the end of the loop.
 285     SmallVector<const SCEV*, 2> Ends;
 286   };
 287
 288   /// ReductionList contains the reduction descriptors for all
 289   /// of the reductions that were found in the loop.
 290   typedef DenseMap<PHINode*, ReductionDescriptor> ReductionList;
 291
 292   /// InductionList saves induction variables and maps them to the initial
 293   /// value entring the loop.
 294   typedef DenseMap<PHINode*, Value*> InductionList;
 295
 296   /// Returns true if it is legal to vectorize this loop.
 297   /// This does not mean that it is profitable to vectorize this
 298   /// loop, only that it is legal to do so.
 299   bool canVectorize();
 300
 301   /// Returns the Induction variable.
 302   PHINode *getInduction() {return Induction;}
 303
 304   /// Returns the reduction variables found in the loop.
 305   ReductionList *getReductionVars() { return &Reductions; }
 306
 307   /// Returns the induction variables found in the loop.
 308   InductionList *getInductionVars() { return &Inductions; }
 309
 310   /// Check if this  pointer is consecutive when vectorizing. This happens
 311   /// when the last index of the GEP is the induction variable, or that the
 312   /// pointer itself is an induction variable.
 313   /// This check allows us to vectorize A[idx] into a wide load/store.
 314   bool isConsecutivePtr(Value *Ptr);
 315
 316   /// Returns true if the value V is uniform within the loop.
 317   bool isUniform(Value *V);
 318
 319   /// Returns true if this instruction will remain scalar after vectorization.
 320   bool isUniformAfterVectorization(Instruction* I) {return Uniforms.count(I);}
 321
 322   /// Returns the information that we collected about runtime memory check.
 323   RuntimePointerCheck *getRuntimePointerCheck() {return &PtrRtCheck; }
 324 private:
 325   /// Check if a single basic block loop is vectorizable.
 326   /// At this point we know that this is a loop with a constant trip count
 327   /// and we only need to check individual instructions.
 328   bool canVectorizeBlock(BasicBlock &BB);
 329
 330   /// When we vectorize loops we may change the order in which
 331   /// we read and write from memory. This method checks if it is
 332   /// legal to vectorize the code, considering only memory constrains.
 333   /// Returns true if BB is vectorizable
 334   bool canVectorizeMemory(BasicBlock &BB);
 335
 336   /// Returns True, if 'Phi' is the kind of reduction variable for type
 337   /// 'Kind'. If this is a reduction variable, it adds it to ReductionList.
 338   bool AddReductionVar(PHINode *Phi, ReductionKind Kind);
 339   /// Returns true if the instruction I can be a reduction variable of type
 340   /// 'Kind'.
 341   bool isReductionInstr(Instruction *I, ReductionKind Kind);
 342   /// Returns True, if 'Phi' is an induction variable.
 343   bool isInductionVariable(PHINode *Phi);
 344   /// Return true if can compute the address bounds of Ptr within the loop.
 345   bool hasComputableBounds(Value *Ptr);
 346
 347   /// The loop that we evaluate.
 348   Loop *TheLoop;
 349   /// Scev analysis.
 350   ScalarEvolution *SE;
 351   /// DataLayout analysis.
 352   DataLayout *DL;
 353
 354   //  ---  vectorization state --- //
 355
 356   /// Holds the integer induction variable. This is the counter of the
 357   /// loop.
 358   PHINode *Induction;
 359   /// Holds the reduction variables.
 360   ReductionList Reductions;
 361   /// Holds all of the induction variables that we found in the loop.
 362   /// Notice that inductions don't need to start at zero and that induction
 363   /// variables can be pointers.
 364   InductionList Inductions;
 365
 366   /// Allowed outside users. This holds the reduction
 367   /// vars which can be accessed from outside the loop.
 368   SmallPtrSet<Value*, 4> AllowedExit;
 369   /// This set holds the variables which are known to be uniform after
 370   /// vectorization.
 371   SmallPtrSet<Instruction*, 4> Uniforms;
 372   /// We need to check that all of the pointers in this list are disjoint
 373   /// at runtime.
 374   RuntimePointerCheck PtrRtCheck;
 375 };
 376
 377 /// LoopVectorizationCostModel - estimates the expected speedups due to
 378 /// vectorization.
 379 /// In many cases vectorization is not profitable. This can happen because
 380 /// of a number of reasons. In this class we mainly attempt to predict
 381 /// the expected speedup/slowdowns due to the supported instruction set.
 382 /// We use the VectorTargetTransformInfo to query the different backends
 383 /// for the cost of different operations.
 384 class LoopVectorizationCostModel {
 385 public:
 386   /// C'tor.
 387   LoopVectorizationCostModel(Loop *Lp, ScalarEvolution *Se,
 388                              LoopVectorizationLegality *Leg,
 389                              const VectorTargetTransformInfo *Vtti):
 390   TheLoop(Lp), SE(Se), Legal(Leg), VTTI(Vtti) { }
 391
 392   /// Returns the most profitable vectorization factor for the loop that is
 393   /// smaller or equal to the VF argument. This method checks every power
 394   /// of two up to VF.
 395   unsigned findBestVectorizationFactor(unsigned VF = 8);
 396
 397 private:
 398   /// Returns the expected execution cost. The unit of the cost does
 399   /// not matter because we use the 'cost' units to compare different
 400   /// vector widths. The cost that is returned is *not* normalized by
 401   /// the factor width.
 402   unsigned expectedCost(unsigned VF);
 403
 404   /// Returns the execution time cost of an instruction for a given vector
 405   /// width. Vector width of one means scalar.
 406   unsigned getInstructionCost(Instruction *I, unsigned VF);
 407
 408   /// A helper function for converting Scalar types to vector types.
 409   /// If the incoming type is void, we return void. If the VF is 1, we return
 410   /// the scalar type.
 411   static Type* ToVectorTy(Type *Scalar, unsigned VF);
 412
 413   /// The loop that we evaluate.
 414   Loop *TheLoop;
 415   /// Scev analysis.
 416   ScalarEvolution *SE;
 417
 418   /// Vectorization legality.
 419   LoopVectorizationLegality *Legal;
 420   /// Vector target information.
 421   const VectorTargetTransformInfo *VTTI;
 422 };
 423
 424 struct LoopVectorize : public LoopPass {
 425   static char ID; // Pass identification, replacement for typeid
 426
 427   LoopVectorize() : LoopPass(ID) {
 428     initializeLoopVectorizePass(*PassRegistry::getPassRegistry());
 429   }
 430
 431   ScalarEvolution *SE;
 432   DataLayout *DL;
 433   LoopInfo *LI;
 434   TargetTransformInfo *TTI;
 435   DominatorTree *DT;
 436
 437   virtual bool runOnLoop(Loop *L, LPPassManager &LPM) {
 438     // We only vectorize innermost loops.
 439     if (!L->empty())
 440       return false;
 441
 442     SE = &getAnalysis<ScalarEvolution>();
 443     DL = getAnalysisIfAvailable<DataLayout>();
 444     LI = &getAnalysis<LoopInfo>();
 445     TTI = getAnalysisIfAvailable<TargetTransformInfo>();
 446     DT = &getAnalysis<DominatorTree>();
 447
 448     DEBUG(dbgs() << "LV: Checking a loop in \"" <<
 449           L->getHeader()->getParent()->getName() << "\"\n");
 450
 451     // Check if it is legal to vectorize the loop.
 452     LoopVectorizationLegality LVL(L, SE, DL);
 453     if (!LVL.canVectorize()) {
 454       DEBUG(dbgs() << "LV: Not vectorizing.\n");
 455       return false;
 456     }
 457
 458     // Select the preffered vectorization factor.
 459     unsigned VF = 1;
 460     if (VectorizationFactor == 0) {
 461       const VectorTargetTransformInfo *VTTI = 0;
 462       if (TTI)
 463         VTTI = TTI->getVectorTargetTransformInfo();
 464       // Use the cost model.
 465       LoopVectorizationCostModel CM(L, SE, &LVL, VTTI);
 466       VF = CM.findBestVectorizationFactor();
 467
 468       if (VF == 1) {
 469         DEBUG(dbgs() << "LV: Vectorization is possible but not beneficial.\n");
 470         return false;
 471       }
 472
 473     } else {
 474       // Use the user command flag.
 475       VF = VectorizationFactor;
 476     }
 477
 478     DEBUG(dbgs() << "LV: Found a vectorizable loop ("<< VF << ") in "<<
 479           L->getHeader()->getParent()->getParent()->getModuleIdentifier()<<
 480           "\n");
 481
 482     // If we decided that it is *legal* to vectorizer the loop then do it.
 483     SingleBlockLoopVectorizer LB(L, SE, LI, DT, DL, &LPM, VF);
 484     LB.vectorize(&LVL);
 485
 486     DEBUG(verifyFunction(*L->getHeader()->getParent()));
 487     return true;
 488   }
 489
 490   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 491     LoopPass::getAnalysisUsage(AU);
 492     AU.addRequiredID(LoopSimplifyID);
 493     AU.addRequiredID(LCSSAID);
 494     AU.addRequired<LoopInfo>();
 495     AU.addRequired<ScalarEvolution>();
 496     AU.addRequired<DominatorTree>();
 497     AU.addPreserved<LoopInfo>();
 498     AU.addPreserved<DominatorTree>();
 499   }
 500
 501 };
 502
 503 Value *SingleBlockLoopVectorizer::getBroadcastInstrs(Value *V) {
 504   // Create the types.
 505   LLVMContext &C = V->getContext();
 506   Type *VTy = VectorType::get(V->getType(), VF);
 507   Type *I32 = IntegerType::getInt32Ty(C);
 508   Constant *Zero = ConstantInt::get(I32, 0);
 509   Value *Zeros = ConstantAggregateZero::get(VectorType::get(I32, VF));
 510   Value *UndefVal = UndefValue::get(VTy);
 511   // Insert the value into a new vector.
 512   Value *SingleElem = Builder.CreateInsertElement(UndefVal, V, Zero);
 513   // Broadcast the scalar into all locations in the vector.
 514   Value *Shuf = Builder.CreateShuffleVector(SingleElem, UndefVal, Zeros,
 515                                              "broadcast");
 516   // We are accessing the induction variable. Make sure to promote the
 517   // index for each consecutive SIMD lane. This adds 0,1,2 ... to all lanes.
 518   if (V == Induction)
 519     return getConsecutiveVector(Shuf);
 520   return Shuf;
 521 }
 522
 523 Value *SingleBlockLoopVectorizer::getConsecutiveVector(Value* Val) {
 524   assert(Val->getType()->isVectorTy() && "Must be a vector");
 525   assert(Val->getType()->getScalarType()->isIntegerTy() &&
 526          "Elem must be an integer");
 527   // Create the types.
 528   Type *ITy = Val->getType()->getScalarType();
 529   VectorType *Ty = cast<VectorType>(Val->getType());
 530   unsigned VLen = Ty->getNumElements();
 531   SmallVector<Constant*, 8> Indices;
 532
 533   // Create a vector of consecutive numbers from zero to VF.
 534   for (unsigned i = 0; i < VLen; ++i)
 535     Indices.push_back(ConstantInt::get(ITy, i));
 536
 537   // Add the consecutive indices to the vector value.
 538   Constant *Cv = ConstantVector::get(Indices);
 539   assert(Cv->getType() == Val->getType() && "Invalid consecutive vec");
 540   return Builder.CreateAdd(Val, Cv, "induction");
 541 }
 542
 543 bool LoopVectorizationLegality::isConsecutivePtr(Value *Ptr) {
 544   assert(Ptr->getType()->isPointerTy() && "Unexpected non ptr");
 545
 546   // If this pointer is an induction variable, return it.
 547   PHINode *Phi = dyn_cast_or_null<PHINode>(Ptr);
 548   if (Phi && getInductionVars()->count(Phi))
 549     return true;
 550
 551   GetElementPtrInst *Gep = dyn_cast_or_null<GetElementPtrInst>(Ptr);
 552   if (!Gep)
 553     return false;
 554
 555   unsigned NumOperands = Gep->getNumOperands();
 556   Value *LastIndex = Gep->getOperand(NumOperands - 1);
 557
 558   // Check that all of the gep indices are uniform except for the last.
 559   for (unsigned i = 0; i < NumOperands - 1; ++i)
 560     if (!SE->isLoopInvariant(SE->getSCEV(Gep->getOperand(i)), TheLoop))
 561       return false;
 562
 563   // We can emit wide load/stores only of the last index is the induction
 564   // variable.
 565   const SCEV *Last = SE->getSCEV(LastIndex);
 566   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Last)) {
 567     const SCEV *Step = AR->getStepRecurrence(*SE);
 568
 569     // The memory is consecutive because the last index is consecutive
 570     // and all other indices are loop invariant.
 571     if (Step->isOne())
 572       return true;
 573   }
 574
 575   return false;
 576 }
 577
 578 bool LoopVectorizationLegality::isUniform(Value *V) {
 579   return (SE->isLoopInvariant(SE->getSCEV(V), TheLoop));
 580 }
 581
 582 Value *SingleBlockLoopVectorizer::getVectorValue(Value *V) {
 583   assert(!V->getType()->isVectorTy() && "Can't widen a vector");
 584   // If we saved a vectorized copy of V, use it.
 585   Value *&MapEntry = WidenMap[V];
 586   if (MapEntry)
 587     return MapEntry;
 588
 589   // Broadcast V and save the value for future uses.
 590   Value *B = getBroadcastInstrs(V);
 591   MapEntry = B;
 592   return B;
 593 }
 594
 595 Constant*
 596 SingleBlockLoopVectorizer::getUniformVector(unsigned Val, Type* ScalarTy) {
 597   return ConstantVector::getSplat(VF, ConstantInt::get(ScalarTy, Val, true));
 598 }
 599
 600 void SingleBlockLoopVectorizer::scalarizeInstruction(Instruction *Instr) {
 601   assert(!Instr->getType()->isAggregateType() && "Can't handle vectors");
 602   // Holds vector parameters or scalars, in case of uniform vals.
 603   SmallVector<Value*, 8> Params;
 604
 605   // Find all of the vectorized parameters.
 606   for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) {
 607     Value *SrcOp = Instr->getOperand(op);
 608
 609     // If we are accessing the old induction variable, use the new one.
 610     if (SrcOp == OldInduction) {
 611       Params.push_back(getVectorValue(Induction));
 612       continue;
 613     }
 614
 615     // Try using previously calculated values.
 616     Instruction *SrcInst = dyn_cast<Instruction>(SrcOp);
 617
 618     // If the src is an instruction that appeared earlier in the basic block
 619     // then it should already be vectorized.
 620     if (SrcInst && SrcInst->getParent() == Instr->getParent()) {
 621       assert(WidenMap.count(SrcInst) && "Source operand is unavailable");
 622       // The parameter is a vector value from earlier.
 623       Params.push_back(WidenMap[SrcInst]);
 624     } else {
 625       // The parameter is a scalar from outside the loop. Maybe even a constant.
 626       Params.push_back(SrcOp);
 627     }
 628   }
 629
 630   assert(Params.size() == Instr->getNumOperands() &&
 631          "Invalid number of operands");
 632
 633   // Does this instruction return a value ?
 634   bool IsVoidRetTy = Instr->getType()->isVoidTy();
 635   Value *VecResults = 0;
 636
 637   // If we have a return value, create an empty vector. We place the scalarized
 638   // instructions in this vector.
 639   if (!IsVoidRetTy)
 640     VecResults = UndefValue::get(VectorType::get(Instr->getType(), VF));
 641
 642   // For each scalar that we create:
 643   for (unsigned i = 0; i < VF; ++i) {
 644     Instruction *Cloned = Instr->clone();
 645     if (!IsVoidRetTy)
 646       Cloned->setName(Instr->getName() + ".cloned");
 647     // Replace the operands of the cloned instrucions with extracted scalars.
 648     for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) {
 649       Value *Op = Params[op];
 650       // Param is a vector. Need to extract the right lane.
 651       if (Op->getType()->isVectorTy())
 652         Op = Builder.CreateExtractElement(Op, Builder.getInt32(i));
 653       Cloned->setOperand(op, Op);
 654     }
 655
 656     // Place the cloned scalar in the new loop.
 657     Builder.Insert(Cloned);
 658
 659     // If the original scalar returns a value we need to place it in a vector
 660     // so that future users will be able to use it.
 661     if (!IsVoidRetTy)
 662       VecResults = Builder.CreateInsertElement(VecResults, Cloned,
 663                                                Builder.getInt32(i));
 664   }
 665
 666   if (!IsVoidRetTy)
 667     WidenMap[Instr] = VecResults;
 668 }
 669
 670 void
 671 SingleBlockLoopVectorizer::createEmptyLoop(LoopVectorizationLegality *Legal) {
 672   /*
 673    In this function we generate a new loop. The new loop will contain
 674    the vectorized instructions while the old loop will continue to run the
 675    scalar remainder.
 676
 677     [ ] <-- vector loop bypass.
 678   /  |
 679  /   v
 680 |   [ ]     <-- vector pre header.
 681 |    |
 682 |    v
 683 |   [  ] \
 684 |   [  ]_|   <-- vector loop.
 685 |    |
 686  \   v
 687    >[ ]   <--- middle-block.
 688   /  |
 689  /   v
 690 |   [ ]     <--- new preheader.
 691 |    |
 692 |    v
 693 |   [ ] \
 694 |   [ ]_|   <-- old scalar loop to handle remainder.
 695  \   |
 696   \  v
 697    >[ ]     <-- exit block.
 698    ...
 699    */
 700
 701   // Some loops have a single integer induction variable, while other loops
 702   // don't. One example is c++ iterators that often have multiple pointer
 703   // induction variables. In the code below we also support a case where we
 704   // don't have a single induction variable.
 705   OldInduction = Legal->getInduction();
 706   Type *IdxTy = OldInduction ? OldInduction->getType() :
 707     DL->getIntPtrType(SE->getContext());
 708
 709   // Find the loop boundaries.
 710   const SCEV *ExitCount = SE->getExitCount(OrigLoop, OrigLoop->getHeader());
 711   assert(ExitCount != SE->getCouldNotCompute() && "Invalid loop count");
 712
 713   // Get the total trip count from the count by adding 1.
 714   ExitCount = SE->getAddExpr(ExitCount,
 715                              SE->getConstant(ExitCount->getType(), 1));
 716
 717   // This is the original scalar-loop preheader.
 718   BasicBlock *BypassBlock = OrigLoop->getLoopPreheader();
 719   BasicBlock *ExitBlock = OrigLoop->getExitBlock();
 720   assert(ExitBlock && "Must have an exit block");
 721
 722   // The loop index does not have to start at Zero. Find the original start
 723   // value from the induction PHI node. If we don't have an induction variable
 724   // then we know that it starts at zero.
 725   Value *StartIdx = OldInduction ?
 726     OldInduction->getIncomingValueForBlock(BypassBlock):
 727     ConstantInt::get(IdxTy, 0);
 728
 729   assert(OrigLoop->getNumBlocks() == 1 && "Invalid loop");
 730   assert(BypassBlock && "Invalid loop structure");
 731
 732   BasicBlock *VectorPH =
 733       BypassBlock->splitBasicBlock(BypassBlock->getTerminator(), "vector.ph");
 734   BasicBlock *VecBody = VectorPH->splitBasicBlock(VectorPH->getTerminator(),
 735                                                  "vector.body");
 736
 737   BasicBlock *MiddleBlock = VecBody->splitBasicBlock(VecBody->getTerminator(),
 738                                                   "middle.block");
 739   BasicBlock *ScalarPH =
 740     MiddleBlock->splitBasicBlock(MiddleBlock->getTerminator(),
 741                                  "scalar.preheader");
 742   // Find the induction variable.
 743   BasicBlock *OldBasicBlock = OrigLoop->getHeader();
 744
 745   // Use this IR builder to create the loop instructions (Phi, Br, Cmp)
 746   // inside the loop.
 747   Builder.SetInsertPoint(VecBody->getFirstInsertionPt());
 748
 749   // Generate the induction variable.
 750   Induction = Builder.CreatePHI(IdxTy, 2, "index");
 751   Constant *Step = ConstantInt::get(IdxTy, VF);
 752
 753   // Expand the trip count and place the new instructions in the preheader.
 754   // Notice that the pre-header does not change, only the loop body.
 755   SCEVExpander Exp(*SE, "induction");
 756   Instruction *Loc = BypassBlock->getTerminator();
 757
 758   // Count holds the overall loop count (N).
 759   Value *Count = Exp.expandCodeFor(ExitCount, ExitCount->getType(), Loc);
 760
 761   // We may need to extend the index in case there is a type mismatch.
 762   // We know that the count starts at zero and does not overflow.
 763   if (Count->getType() != IdxTy) {
 764     // The exit count can be of pointer type. Convert it to the correct
 765     // integer type.
 766     if (ExitCount->getType()->isPointerTy())
 767       Count = CastInst::CreatePointerCast(Count, IdxTy, "ptrcnt.to.int", Loc);
 768     else
 769       Count = CastInst::CreateZExtOrBitCast(Count, IdxTy, "zext.cnt", Loc);
 770   }
 771
 772   // Add the start index to the loop count to get the new end index.
 773   Value *IdxEnd = BinaryOperator::CreateAdd(Count, StartIdx, "end.idx", Loc);
 774
 775   // Now we need to generate the expression for N - (N % VF), which is
 776   // the part that the vectorized body will execute.
 777   Constant *CIVF = ConstantInt::get(IdxTy, VF);
 778   Value *R = BinaryOperator::CreateURem(Count, CIVF, "n.mod.vf", Loc);
 779   Value *CountRoundDown = BinaryOperator::CreateSub(Count, R, "n.vec", Loc);
 780   Value *IdxEndRoundDown = BinaryOperator::CreateAdd(CountRoundDown, StartIdx,
 781                                                      "end.idx.rnd.down", Loc);
 782
 783   // Now, compare the new count to zero. If it is zero skip the vector loop and
 784   // jump to the scalar loop.
 785   Value *Cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ,
 786                                IdxEndRoundDown,
 787                                StartIdx,
 788                                "cmp.zero", Loc);
 789
 790   LoopVectorizationLegality::RuntimePointerCheck *PtrRtCheck =
 791     Legal->getRuntimePointerCheck();
 792   Value *MemoryRuntimeCheck = 0;
 793   if (PtrRtCheck->Need) {
 794     unsigned NumPointers = PtrRtCheck->Pointers.size();
 795     SmallVector<Value* , 2> Starts;
 796     SmallVector<Value* , 2> Ends;
 797
 798     // Use this type for pointer arithmetic.
 799     Type* PtrArithTy = PtrRtCheck->Pointers[0]->getType();
 800
 801     for (unsigned i=0; i < NumPointers; ++i) {
 802       Value *Ptr = PtrRtCheck->Pointers[i];
 803       const SCEV *Sc = SE->getSCEV(Ptr);
 804
 805       if (SE->isLoopInvariant(Sc, OrigLoop)) {
 806         DEBUG(dbgs() << "LV1: Adding RT check for a loop invariant ptr:" <<
 807               *Ptr <<"\n");
 808         Starts.push_back(Ptr);
 809         Ends.push_back(Ptr);
 810       } else {
 811         DEBUG(dbgs() << "LV: Adding RT check for range:" << *Ptr <<"\n");
 812
 813         Value *Start = Exp.expandCodeFor(PtrRtCheck->Starts[i],
 814                                          PtrArithTy, Loc);
 815         Value *End = Exp.expandCodeFor(PtrRtCheck->Ends[i], PtrArithTy, Loc);
 816         Starts.push_back(Start);
 817         Ends.push_back(End);
 818       }
 819     }
 820
 821     for (unsigned i = 0; i < NumPointers; ++i) {
 822       for (unsigned j = i+1; j < NumPointers; ++j) {
 823         Value *Cmp0 = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_ULE,
 824                                       Starts[i], Ends[j], "bound0", Loc);
 825         Value *Cmp1 = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_ULE,
 826                                       Starts[j], Ends[i], "bound1", Loc);
 827         Value *IsConflict = BinaryOperator::Create(Instruction::And, Cmp0, Cmp1,
 828                                                     "found.conflict", Loc);
 829         if (MemoryRuntimeCheck) {
 830           MemoryRuntimeCheck = BinaryOperator::Create(Instruction::Or,
 831                                                       MemoryRuntimeCheck,
 832                                                       IsConflict,
 833                                                       "conflict.rdx", Loc);
 834         } else {
 835           MemoryRuntimeCheck = IsConflict;
 836         }
 837       }
 838     }
 839   }// end of need-runtime-check code.
 840
 841   // If we are using memory runtime checks, include them in.
 842   if (MemoryRuntimeCheck) {
 843     Cmp = BinaryOperator::Create(Instruction::Or, Cmp, MemoryRuntimeCheck,
 844                                  "CntOrMem", Loc);
 845   }
 846
 847   BranchInst::Create(MiddleBlock, VectorPH, Cmp, Loc);
 848   // Remove the old terminator.
 849   Loc->eraseFromParent();
 850
 851   // We are going to resume the execution of the scalar loop.
 852   // Go over all of the induction variables that we found and fix the
 853   // PHIs that are left in the scalar version of the loop.
 854   // The starting values of PHI nodes depend on the counter of the last
 855   // iteration in the vectorized loop.
 856   // If we come from a bypass edge then we need to start from the original start
 857   // value.
 858
 859   // This variable saves the new starting index for the scalar loop.
 860   PHINode *ResumeIndex = 0;
 861   LoopVectorizationLegality::InductionList::iterator I, E;
 862   LoopVectorizationLegality::InductionList *List = Legal->getInductionVars();
 863   for (I = List->begin(), E = List->end(); I != E; ++I) {
 864     PHINode *OrigPhi = I->first;
 865     PHINode *ResumeVal = PHINode::Create(OrigPhi->getType(), 2, "resume.val",
 866                                            MiddleBlock->getTerminator());
 867     Value *EndValue = 0;
 868     if (OrigPhi->getType()->isIntegerTy()) {
 869       // Handle the integer induction counter:
 870       assert(OrigPhi == OldInduction && "Unknown integer PHI");
 871       // We know what the end value is.
 872       EndValue = IdxEndRoundDown;
 873       // We also know which PHI node holds it.
 874       ResumeIndex = ResumeVal;
 875     } else {
 876       // For pointer induction variables, calculate the offset using
 877       // the end index.
 878       EndValue = GetElementPtrInst::Create(I->second, CountRoundDown,
 879                                            "ptr.ind.end",
 880                                            BypassBlock->getTerminator());
 881     }
 882
 883     // The new PHI merges the original incoming value, in case of a bypass,
 884     // or the value at the end of the vectorized loop.
 885     ResumeVal->addIncoming(I->second, BypassBlock);
 886     ResumeVal->addIncoming(EndValue, VecBody);
 887
 888     // Fix the scalar body counter (PHI node).
 889     unsigned BlockIdx = OrigPhi->getBasicBlockIndex(ScalarPH);
 890     OrigPhi->setIncomingValue(BlockIdx, ResumeVal);
 891   }
 892
 893   // If we are generating a new induction variable then we also need to
 894   // generate the code that calculates the exit value. This value is not
 895   // simply the end of the counter because we may skip the vectorized body
 896   // in case of a runtime check.
 897   if (!OldInduction){
 898     assert(!ResumeIndex && "Unexpected resume value found");
 899     ResumeIndex = PHINode::Create(IdxTy, 2, "new.indc.resume.val",
 900                                   MiddleBlock->getTerminator());
 901     ResumeIndex->addIncoming(StartIdx, BypassBlock);
 902     ResumeIndex->addIncoming(IdxEndRoundDown, VecBody);
 903   }
 904
 905   // Make sure that we found the index where scalar loop needs to continue.
 906   assert(ResumeIndex && ResumeIndex->getType()->isIntegerTy() &&
 907          "Invalid resume Index");
 908
 909   // Add a check in the middle block to see if we have completed
 910   // all of the iterations in the first vector loop.
 911   // If (N - N%VF) == N, then we *don't* need to run the remainder.
 912   Value *CmpN = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, IdxEnd,
 913                                 ResumeIndex, "cmp.n",
 914                                 MiddleBlock->getTerminator());
 915
 916   BranchInst::Create(ExitBlock, ScalarPH, CmpN, MiddleBlock->getTerminator());
 917   // Remove the old terminator.
 918   MiddleBlock->getTerminator()->eraseFromParent();
 919
 920   // Create i+1 and fill the PHINode.
 921   Value *NextIdx = Builder.CreateAdd(Induction, Step, "index.next");
 922   Induction->addIncoming(StartIdx, VectorPH);
 923   Induction->addIncoming(NextIdx, VecBody);
 924   // Create the compare.
 925   Value *ICmp = Builder.CreateICmpEQ(NextIdx, IdxEndRoundDown);
 926   Builder.CreateCondBr(ICmp, MiddleBlock, VecBody);
 927
 928   // Now we have two terminators. Remove the old one from the block.
 929   VecBody->getTerminator()->eraseFromParent();
 930
 931   // Get ready to start creating new instructions into the vectorized body.
 932   Builder.SetInsertPoint(VecBody->getFirstInsertionPt());
 933
 934   // Register the new loop.
 935   Loop* Lp = new Loop();
 936   LPM->insertLoop(Lp, OrigLoop->getParentLoop());
 937
 938   Lp->addBasicBlockToLoop(VecBody, LI->getBase());
 939
 940   Loop *ParentLoop = OrigLoop->getParentLoop();
 941   if (ParentLoop) {
 942     ParentLoop->addBasicBlockToLoop(ScalarPH, LI->getBase());
 943     ParentLoop->addBasicBlockToLoop(VectorPH, LI->getBase());
 944     ParentLoop->addBasicBlockToLoop(MiddleBlock, LI->getBase());
 945   }
 946
 947   // Save the state.
 948   LoopVectorPreHeader = VectorPH;
 949   LoopScalarPreHeader = ScalarPH;
 950   LoopMiddleBlock = MiddleBlock;
 951   LoopExitBlock = ExitBlock;
 952   LoopVectorBody = VecBody;
 953   LoopScalarBody = OldBasicBlock;
 954   LoopBypassBlock = BypassBlock;
 955 }
 956
 957 /// This function returns the identity element (or neutral element) for
 958 /// the operation K.
 959 static unsigned
 960 getReductionIdentity(LoopVectorizationLegality::ReductionKind K) {
 961   switch (K) {
 962   case LoopVectorizationLegality::IntegerXor:
 963   case LoopVectorizationLegality::IntegerAdd:
 964   case LoopVectorizationLegality::IntegerOr:
 965     // Adding, Xoring, Oring zero to a number does not change it.
 966     return 0;
 967   case LoopVectorizationLegality::IntegerMult:
 968     // Multiplying a number by 1 does not change it.
 969     return 1;
 970   case LoopVectorizationLegality::IntegerAnd:
 971     // AND-ing a number with an all-1 value does not change it.
 972     return -1;
 973   default:
 974     llvm_unreachable("Unknown reduction kind");
 975   }
 976 }
 977
 978 void
 979 SingleBlockLoopVectorizer::vectorizeLoop(LoopVectorizationLegality *Legal) {
 980   //===------------------------------------------------===//
 981   //
 982   // Notice: any optimization or new instruction that go
 983   // into the code below should be also be implemented in
 984   // the cost-model.
 985   //
 986   //===------------------------------------------------===//
 987   typedef SmallVector<PHINode*, 4> PhiVector;
 988   BasicBlock &BB = *OrigLoop->getHeader();
 989   Constant *Zero = ConstantInt::get(
 990     IntegerType::getInt32Ty(BB.getContext()), 0);
 991
 992   // In order to support reduction variables we need to be able to vectorize
 993   // Phi nodes. Phi nodes have cycles, so we need to vectorize them in two
 994   // steages. First, we create a new vector PHI node with no incoming edges.
 995   // We use this value when we vectorize all of the instructions that use the
 996   // PHI. Next, after all of the instructions in the block are complete we
 997   // add the new incoming edges to the PHI. At this point all of the
 998   // instructions in the basic block are vectorized, so we can use them to
 999   // construct the PHI.
1000   PhiVector RdxPHIsToFix;
1001
1002   // For each instruction in the old loop.
1003   for (BasicBlock::iterator it = BB.begin(), e = BB.end(); it != e; ++it) {
1004     Instruction *Inst = it;
1005
1006     switch (Inst->getOpcode()) {
1007       case Instruction::Br:
1008         // Nothing to do for PHIs and BR, since we already took care of the
1009         // loop control flow instructions.
1010         continue;
1011       case Instruction::PHI:{
1012         PHINode* P = cast<PHINode>(Inst);
1013         // Handle reduction variables:
1014         if (Legal->getReductionVars()->count(P)) {
1015           // This is phase one of vectorizing PHIs.
1016           Type *VecTy = VectorType::get(Inst->getType(), VF);
1017           WidenMap[Inst] = PHINode::Create(VecTy, 2, "vec.phi",
1018                                   LoopVectorBody->getFirstInsertionPt());
1019           RdxPHIsToFix.push_back(P);
1020           continue;
1021         }
1022
1023         // This PHINode must be an induction variable.
1024         // Make sure that we know about it.
1025         assert(Legal->getInductionVars()->count(P) &&
1026                "Not an induction variable");
1027
1028         if (P->getType()->isIntegerTy()) {
1029           assert(P == OldInduction && "Unexpected PHI");
1030           WidenMap[Inst] = getBroadcastInstrs(Induction);
1031           continue;
1032         }
1033
1034         // Handle pointer inductions:
1035         assert(P->getType()->isPointerTy() && "Unexpected type.");
1036         Value *StartIdx = OldInduction ?
1037           Legal->getInductionVars()->lookup(OldInduction) :
1038           ConstantInt::get(Induction->getType(), 0);
1039
1040         // This is the pointer value coming into the loop.
1041         Value *StartPtr = Legal->getInductionVars()->lookup(P);
1042
1043         // This is the normalized GEP that starts counting at zero.
1044         Value *NormalizedIdx = Builder.CreateSub(Induction, StartIdx,
1045                                                  "normalized.idx");
1046
1047         // This is the vector of results. Notice that we don't generate vector
1048         // geps because scalar geps result in better code.
1049         Value *VecVal = UndefValue::get(VectorType::get(P->getType(), VF));
1050         for (unsigned int i = 0; i < VF; ++i) {
1051           Constant *Idx = ConstantInt::get(Induction->getType(), i);
1052           Value *GlobalIdx = Builder.CreateAdd(NormalizedIdx, Idx, "gep.idx");
1053           Value *SclrGep = Builder.CreateGEP(StartPtr, GlobalIdx, "next.gep");
1054           VecVal = Builder.CreateInsertElement(VecVal, SclrGep,
1055                                                Builder.getInt32(i),
1056                                                "insert.gep");
1057         }
1058
1059         WidenMap[Inst] = VecVal;
1060         continue;
1061       }
1062       case Instruction::Add:
1063       case Instruction::FAdd:
1064       case Instruction::Sub:
1065       case Instruction::FSub:
1066       case Instruction::Mul:
1067       case Instruction::FMul:
1068       case Instruction::UDiv:
1069       case Instruction::SDiv:
1070       case Instruction::FDiv:
1071       case Instruction::URem:
1072       case Instruction::SRem:
1073       case Instruction::FRem:
1074       case Instruction::Shl:
1075       case Instruction::LShr:
1076       case Instruction::AShr:
1077       case Instruction::And:
1078       case Instruction::Or:
1079       case Instruction::Xor: {
1080         // Just widen binops.
1081         BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst);
1082         Value *A = getVectorValue(Inst->getOperand(0));
1083         Value *B = getVectorValue(Inst->getOperand(1));
1084
1085         // Use this vector value for all users of the original instruction.
1086         Value *V = Builder.CreateBinOp(BinOp->getOpcode(), A, B);
1087         WidenMap[Inst] = V;
1088
1089         // Update the NSW, NUW and Exact flags.
1090         BinaryOperator *VecOp = cast<BinaryOperator>(V);
1091         if (isa<OverflowingBinaryOperator>(BinOp)) {
1092           VecOp->setHasNoSignedWrap(BinOp->hasNoSignedWrap());
1093           VecOp->setHasNoUnsignedWrap(BinOp->hasNoUnsignedWrap());
1094         }
1095         if (isa<PossiblyExactOperator>(VecOp))
1096           VecOp->setIsExact(BinOp->isExact());
1097         break;
1098       }
1099       case Instruction::Select: {
1100         // Widen selects.
1101         // If the selector is loop invariant we can create a select
1102         // instruction with a scalar condition. Otherwise, use vector-select.
1103         Value *Cond = Inst->getOperand(0);
1104         bool InvariantCond = SE->isLoopInvariant(SE->getSCEV(Cond), OrigLoop);
1105
1106         // The condition can be loop invariant  but still defined inside the
1107         // loop. This means that we can't just use the original 'cond' value.
1108         // We have to take the 'vectorized' value and pick the first lane.
1109         // Instcombine will make this a no-op.
1110         Cond = getVectorValue(Cond);
1111         if (InvariantCond)
1112           Cond = Builder.CreateExtractElement(Cond, Builder.getInt32(0));
1113
1114         Value *Op0 = getVectorValue(Inst->getOperand(1));
1115         Value *Op1 = getVectorValue(Inst->getOperand(2));
1116         WidenMap[Inst] = Builder.CreateSelect(Cond, Op0, Op1);
1117         break;
1118       }
1119
1120       case Instruction::ICmp:
1121       case Instruction::FCmp: {
1122         // Widen compares. Generate vector compares.
1123         bool FCmp = (Inst->getOpcode() == Instruction::FCmp);
1124         CmpInst *Cmp = dyn_cast<CmpInst>(Inst);
1125         Value *A = getVectorValue(Inst->getOperand(0));
1126         Value *B = getVectorValue(Inst->getOperand(1));
1127         if (FCmp)
1128           WidenMap[Inst] = Builder.CreateFCmp(Cmp->getPredicate(), A, B);
1129         else
1130           WidenMap[Inst] = Builder.CreateICmp(Cmp->getPredicate(), A, B);
1131         break;
1132       }
1133
1134       case Instruction::Store: {
1135         // Attempt to issue a wide store.
1136         StoreInst *SI = dyn_cast<StoreInst>(Inst);
1137         Type *StTy = VectorType::get(SI->getValueOperand()->getType(), VF);
1138         Value *Ptr = SI->getPointerOperand();
1139         unsigned Alignment = SI->getAlignment();
1140
1141         assert(!Legal->isUniform(Ptr) &&
1142                "We do not allow storing to uniform addresses");
1143
1144         GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr);
1145
1146         // This store does not use GEPs.
1147         if (!Legal->isConsecutivePtr(Ptr)) {
1148           scalarizeInstruction(Inst);
1149           break;
1150         }
1151
1152         if (Gep) {
1153           // The last index does not have to be the induction. It can be
1154           // consecutive and be a function of the index. For example A[I+1];
1155           unsigned NumOperands = Gep->getNumOperands();
1156           Value *LastIndex = getVectorValue(Gep->getOperand(NumOperands - 1));
1157           LastIndex = Builder.CreateExtractElement(LastIndex, Zero);
1158
1159           // Create the new GEP with the new induction variable.
1160           GetElementPtrInst *Gep2 = cast<GetElementPtrInst>(Gep->clone());
1161           Gep2->setOperand(NumOperands - 1, LastIndex);
1162           Ptr = Builder.Insert(Gep2);
1163         } else {
1164           // Use the induction element ptr.
1165           assert(isa<PHINode>(Ptr) && "Invalid induction ptr");
1166           Ptr = Builder.CreateExtractElement(getVectorValue(Ptr), Zero);
1167         }
1168         Ptr = Builder.CreateBitCast(Ptr, StTy->getPointerTo());
1169         Value *Val = getVectorValue(SI->getValueOperand());
1170         Builder.CreateStore(Val, Ptr)->setAlignment(Alignment);
1171         break;
1172       }
1173       case Instruction::Load: {
1174         // Attempt to issue a wide load.
1175         LoadInst *LI = dyn_cast<LoadInst>(Inst);
1176         Type *RetTy = VectorType::get(LI->getType(), VF);
1177         Value *Ptr = LI->getPointerOperand();
1178         unsigned Alignment = LI->getAlignment();
1179         GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr);
1180
1181         // If the pointer is loop invariant or if it is non consecutive,
1182         // scalarize the load.
1183         bool Con = Legal->isConsecutivePtr(Ptr);
1184         if (Legal->isUniform(Ptr) || !Con) {
1185           scalarizeInstruction(Inst);
1186           break;
1187         }
1188
1189         if (Gep) {
1190           // The last index does not have to be the induction. It can be
1191           // consecutive and be a function of the index. For example A[I+1];
1192           unsigned NumOperands = Gep->getNumOperands();
1193           Value *LastIndex = getVectorValue(Gep->getOperand(NumOperands -1));
1194           LastIndex = Builder.CreateExtractElement(LastIndex, Zero);
1195
1196           // Create the new GEP with the new induction variable.
1197           GetElementPtrInst *Gep2 = cast<GetElementPtrInst>(Gep->clone());
1198           Gep2->setOperand(NumOperands - 1, LastIndex);
1199           Ptr = Builder.Insert(Gep2);
1200         } else {
1201           // Use the induction element ptr.
1202           assert(isa<PHINode>(Ptr) && "Invalid induction ptr");
1203           Ptr = Builder.CreateExtractElement(getVectorValue(Ptr), Zero);
1204         }
1205
1206         Ptr = Builder.CreateBitCast(Ptr, RetTy->getPointerTo());
1207         LI = Builder.CreateLoad(Ptr);
1208         LI->setAlignment(Alignment);
1209         // Use this vector value for all users of the load.
1210         WidenMap[Inst] = LI;
1211         break;
1212       }
1213       case Instruction::ZExt:
1214       case Instruction::SExt:
1215       case Instruction::FPToUI:
1216       case Instruction::FPToSI:
1217       case Instruction::FPExt:
1218       case Instruction::PtrToInt:
1219       case Instruction::IntToPtr:
1220       case Instruction::SIToFP:
1221       case Instruction::UIToFP:
1222       case Instruction::Trunc:
1223       case Instruction::FPTrunc:
1224       case Instruction::BitCast: {
1225         /// Vectorize bitcasts.
1226         CastInst *CI = dyn_cast<CastInst>(Inst);
1227         Value *A = getVectorValue(Inst->getOperand(0));
1228         Type *DestTy = VectorType::get(CI->getType()->getScalarType(), VF);
1229         WidenMap[Inst] = Builder.CreateCast(CI->getOpcode(), A, DestTy);
1230         break;
1231       }
1232
1233       default:
1234         /// All other instructions are unsupported. Scalarize them.
1235         scalarizeInstruction(Inst);
1236         break;
1237     }// end of switch.
1238   }// end of for_each instr.
1239
1240   // At this point every instruction in the original loop is widended to
1241   // a vector form. We are almost done. Now, we need to fix the PHI nodes
1242   // that we vectorized. The PHI nodes are currently empty because we did
1243   // not want to introduce cycles. Notice that the remaining PHI nodes
1244   // that we need to fix are reduction variables.
1245
1246   // Create the 'reduced' values for each of the induction vars.
1247   // The reduced values are the vector values that we scalarize and combine
1248   // after the loop is finished.
1249   for (PhiVector::iterator it = RdxPHIsToFix.begin(), e = RdxPHIsToFix.end();
1250        it != e; ++it) {
1251     PHINode *RdxPhi = *it;
1252     PHINode *VecRdxPhi = dyn_cast<PHINode>(WidenMap[RdxPhi]);
1253     assert(RdxPhi && "Unable to recover vectorized PHI");
1254
1255     // Find the reduction variable descriptor.
1256     assert(Legal->getReductionVars()->count(RdxPhi) &&
1257            "Unable to find the reduction variable");
1258     LoopVectorizationLegality::ReductionDescriptor RdxDesc =
1259       (*Legal->getReductionVars())[RdxPhi];
1260
1261     // We need to generate a reduction vector from the incoming scalar.
1262     // To do so, we need to generate the 'identity' vector and overide
1263     // one of the elements with the incoming scalar reduction. We need
1264     // to do it in the vector-loop preheader.
1265     Builder.SetInsertPoint(LoopBypassBlock->getTerminator());
1266
1267     // This is the vector-clone of the value that leaves the loop.
1268     Value *VectorExit = getVectorValue(RdxDesc.LoopExitInstr);
1269     Type *VecTy = VectorExit->getType();
1270
1271     // Find the reduction identity variable. Zero for addition, or, xor,
1272     // one for multiplication, -1 for And.
1273     Constant *Identity = getUniformVector(getReductionIdentity(RdxDesc.Kind),
1274                                           VecTy->getScalarType());
1275
1276     // This vector is the Identity vector where the first element is the
1277     // incoming scalar reduction.
1278     Value *VectorStart = Builder.CreateInsertElement(Identity,
1279                                                     RdxDesc.StartValue, Zero);
1280
1281     // Fix the vector-loop phi.
1282     // We created the induction variable so we know that the
1283     // preheader is the first entry.
1284     BasicBlock *VecPreheader = Induction->getIncomingBlock(0);
1285
1286     // Reductions do not have to start at zero. They can start with
1287     // any loop invariant values.
1288     VecRdxPhi->addIncoming(VectorStart, VecPreheader);
1289     unsigned SelfEdgeIdx = (RdxPhi)->getBasicBlockIndex(LoopScalarBody);
1290     Value *Val = getVectorValue(RdxPhi->getIncomingValue(SelfEdgeIdx));
1291     VecRdxPhi->addIncoming(Val, LoopVectorBody);
1292
1293     // Before each round, move the insertion point right between
1294     // the PHIs and the values we are going to write.
1295     // This allows us to write both PHINodes and the extractelement
1296     // instructions.
1297     Builder.SetInsertPoint(LoopMiddleBlock->getFirstInsertionPt());
1298
1299     // This PHINode contains the vectorized reduction variable, or
1300     // the initial value vector, if we bypass the vector loop.
1301     PHINode *NewPhi = Builder.CreatePHI(VecTy, 2, "rdx.vec.exit.phi");
1302     NewPhi->addIncoming(VectorStart, LoopBypassBlock);
1303     NewPhi->addIncoming(getVectorValue(RdxDesc.LoopExitInstr), LoopVectorBody);
1304
1305     // Extract the first scalar.
1306     Value *Scalar0 =
1307       Builder.CreateExtractElement(NewPhi, Builder.getInt32(0));
1308     // Extract and reduce the remaining vector elements.
1309     for (unsigned i=1; i < VF; ++i) {
1310       Value *Scalar1 =
1311         Builder.CreateExtractElement(NewPhi, Builder.getInt32(i));
1312       switch (RdxDesc.Kind) {
1313         case LoopVectorizationLegality::IntegerAdd:
1314           Scalar0 = Builder.CreateAdd(Scalar0, Scalar1);
1315           break;
1316         case LoopVectorizationLegality::IntegerMult:
1317           Scalar0 = Builder.CreateMul(Scalar0, Scalar1);
1318           break;
1319         case LoopVectorizationLegality::IntegerOr:
1320           Scalar0 = Builder.CreateOr(Scalar0, Scalar1);
1321           break;
1322         case LoopVectorizationLegality::IntegerAnd:
1323           Scalar0 = Builder.CreateAnd(Scalar0, Scalar1);
1324           break;
1325         case LoopVectorizationLegality::IntegerXor:
1326           Scalar0 = Builder.CreateXor(Scalar0, Scalar1);
1327           break;
1328         default:
1329           llvm_unreachable("Unknown reduction operation");
1330       }
1331     }
1332
1333     // Now, we need to fix the users of the reduction variable
1334     // inside and outside of the scalar remainder loop.
1335     // We know that the loop is in LCSSA form. We need to update the
1336     // PHI nodes in the exit blocks.
1337     for (BasicBlock::iterator LEI = LoopExitBlock->begin(),
1338          LEE = LoopExitBlock->end(); LEI != LEE; ++LEI) {
1339       PHINode *LCSSAPhi = dyn_cast<PHINode>(LEI);
1340       if (!LCSSAPhi) continue;
1341
1342       // All PHINodes need to have a single entry edge, or two if
1343       // we already fixed them.
1344       assert(LCSSAPhi->getNumIncomingValues() < 3 && "Invalid LCSSA PHI");
1345
1346       // We found our reduction value exit-PHI. Update it with the
1347       // incoming bypass edge.
1348       if (LCSSAPhi->getIncomingValue(0) == RdxDesc.LoopExitInstr) {
1349         // Add an edge coming from the bypass.
1350         LCSSAPhi->addIncoming(Scalar0, LoopMiddleBlock);
1351         break;
1352       }
1353     }// end of the LCSSA phi scan.
1354
1355     // Fix the scalar loop reduction variable with the incoming reduction sum
1356     // from the vector body and from the backedge value.
1357     int IncomingEdgeBlockIdx = (RdxPhi)->getBasicBlockIndex(LoopScalarBody);
1358     int SelfEdgeBlockIdx = (IncomingEdgeBlockIdx ? 0 : 1); // The other block.
1359     (RdxPhi)->setIncomingValue(SelfEdgeBlockIdx, Scalar0);
1360     (RdxPhi)->setIncomingValue(IncomingEdgeBlockIdx, RdxDesc.LoopExitInstr);
1361   }// end of for each redux variable.
1362 }
1363
1364 void SingleBlockLoopVectorizer::updateAnalysis() {
1365   // The original basic block.
1366   SE->forgetLoop(OrigLoop);
1367
1368   // Update the dominator tree information.
1369   assert(DT->properlyDominates(LoopBypassBlock, LoopExitBlock) &&
1370          "Entry does not dominate exit.");
1371
1372   DT->addNewBlock(LoopVectorPreHeader, LoopBypassBlock);
1373   DT->addNewBlock(LoopVectorBody, LoopVectorPreHeader);
1374   DT->addNewBlock(LoopMiddleBlock, LoopBypassBlock);
1375   DT->addNewBlock(LoopScalarPreHeader, LoopMiddleBlock);
1376   DT->changeImmediateDominator(LoopScalarBody, LoopScalarPreHeader);
1377   DT->changeImmediateDominator(LoopExitBlock, LoopMiddleBlock);
1378
1379   DEBUG(DT->verifyAnalysis());
1380 }
1381
1382 bool LoopVectorizationLegality::canVectorize() {
1383   if (!TheLoop->getLoopPreheader()) {
1384     assert(false && "No preheader!!");
1385     DEBUG(dbgs() << "LV: Loop not normalized." << "\n");
1386     return false;
1387   }
1388
1389   // We can only vectorize single basic block loops.
1390   unsigned NumBlocks = TheLoop->getNumBlocks();
1391   if (NumBlocks != 1) {
1392     DEBUG(dbgs() << "LV: Too many blocks:" << NumBlocks << "\n");
1393     return false;
1394   }
1395
1396   // We need to have a loop header.
1397   BasicBlock *BB = TheLoop->getHeader();
1398   DEBUG(dbgs() << "LV: Found a loop: " << BB->getName() << "\n");
1399
1400   // ScalarEvolution needs to be able to find the exit count.
1401   const SCEV *ExitCount = SE->getExitCount(TheLoop, BB);
1402   if (ExitCount == SE->getCouldNotCompute()) {
1403     DEBUG(dbgs() << "LV: SCEV could not compute the loop exit count.\n");
1404     return false;
1405   }
1406
1407   // Do not loop-vectorize loops with a tiny trip count.
1408   unsigned TC = SE->getSmallConstantTripCount(TheLoop, BB);
1409   if (TC > 0u && TC < TinyTripCountThreshold) {
1410     DEBUG(dbgs() << "LV: Found a loop with a very small trip count. " <<
1411           "This loop is not worth vectorizing.\n");
1412     return false;
1413   }
1414
1415   // Go over each instruction and look at memory deps.
1416   if (!canVectorizeBlock(*BB)) {
1417     DEBUG(dbgs() << "LV: Can't vectorize this loop header\n");
1418     return false;
1419   }
1420
1421   DEBUG(dbgs() << "LV: We can vectorize this loop" <<
1422         (PtrRtCheck.Need ? " (with a runtime bound check)" : "")
1423         <<"!\n");
1424
1425   // Okay! We can vectorize. At this point we don't have any other mem analysis
1426   // which may limit our maximum vectorization factor, so just return true with
1427   // no restrictions.
1428   return true;
1429 }
1430
1431 bool LoopVectorizationLegality::canVectorizeBlock(BasicBlock &BB) {
1432
1433   BasicBlock *PreHeader = TheLoop->getLoopPreheader();
1434
1435   // Scan the instructions in the block and look for hazards.
1436   for (BasicBlock::iterator it = BB.begin(), e = BB.end(); it != e; ++it) {
1437     Instruction *I = it;
1438
1439     if (PHINode *Phi = dyn_cast<PHINode>(I)) {
1440       // This should not happen because the loop should be normalized.
1441       if (Phi->getNumIncomingValues() != 2) {
1442         DEBUG(dbgs() << "LV: Found an invalid PHI.\n");
1443         return false;
1444       }
1445
1446       // This is the value coming from the preheader.
1447       Value *StartValue = Phi->getIncomingValueForBlock(PreHeader);
1448
1449       // We only look at integer and pointer phi nodes.
1450       if (Phi->getType()->isPointerTy() && isInductionVariable(Phi)) {
1451         DEBUG(dbgs() << "LV: Found a pointer induction variable.\n");
1452         Inductions[Phi] = StartValue;
1453         continue;
1454       } else if (!Phi->getType()->isIntegerTy()) {
1455         DEBUG(dbgs() << "LV: Found an non-int non-pointer PHI.\n");
1456         return false;
1457       }
1458
1459       // Handle integer PHIs:
1460       if (isInductionVariable(Phi)) {
1461         if (Induction) {
1462           DEBUG(dbgs() << "LV: Found too many inductions."<< *Phi <<"\n");
1463           return false;
1464         }
1465         DEBUG(dbgs() << "LV: Found the induction PHI."<< *Phi <<"\n");
1466         Induction = Phi;
1467         Inductions[Phi] = StartValue;
1468         continue;
1469       }
1470       if (AddReductionVar(Phi, IntegerAdd)) {
1471         DEBUG(dbgs() << "LV: Found an ADD reduction PHI."<< *Phi <<"\n");
1472         continue;
1473       }
1474       if (AddReductionVar(Phi, IntegerMult)) {
1475         DEBUG(dbgs() << "LV: Found a MUL reduction PHI."<< *Phi <<"\n");
1476         continue;
1477       }
1478       if (AddReductionVar(Phi, IntegerOr)) {
1479         DEBUG(dbgs() << "LV: Found an OR reduction PHI."<< *Phi <<"\n");
1480         continue;
1481       }
1482       if (AddReductionVar(Phi, IntegerAnd)) {
1483         DEBUG(dbgs() << "LV: Found an AND reduction PHI."<< *Phi <<"\n");
1484         continue;
1485       }
1486       if (AddReductionVar(Phi, IntegerXor)) {
1487         DEBUG(dbgs() << "LV: Found a XOR reduction PHI."<< *Phi <<"\n");
1488         continue;
1489       }
1490
1491       DEBUG(dbgs() << "LV: Found an unidentified PHI."<< *Phi <<"\n");
1492       return false;
1493     }// end of PHI handling
1494
1495     // We still don't handle functions.
1496     CallInst *CI = dyn_cast<CallInst>(I);
1497     if (CI) {
1498       DEBUG(dbgs() << "LV: Found a call site.\n");
1499       return false;
1500     }
1501
1502     // We do not re-vectorize vectors.
1503     if (!VectorType::isValidElementType(I->getType()) &&
1504         !I->getType()->isVoidTy()) {
1505       DEBUG(dbgs() << "LV: Found unvectorizable type." << "\n");
1506       return false;
1507     }
1508
1509     // Reduction instructions are allowed to have exit users.
1510     // All other instructions must not have external users.
1511     if (!AllowedExit.count(I))
1512       //Check that all of the users of the loop are inside the BB.
1513       for (Value::use_iterator it = I->use_begin(), e = I->use_end();
1514            it != e; ++it) {
1515         Instruction *U = cast<Instruction>(*it);
1516         // This user may be a reduction exit value.
1517         BasicBlock *Parent = U->getParent();
1518         if (Parent != &BB) {
1519           DEBUG(dbgs() << "LV: Found an outside user for : "<< *U << "\n");
1520           return false;
1521         }
1522     }
1523   } // next instr.
1524
1525   if (!Induction) {
1526     DEBUG(dbgs() << "LV: Did not find one integer induction var.\n");
1527     assert(getInductionVars()->size() && "No induction variables");
1528   }
1529
1530   // Don't vectorize if the memory dependencies do not allow vectorization.
1531   if (!canVectorizeMemory(BB))
1532     return false;
1533
1534   // We now know that the loop is vectorizable!
1535   // Collect variables that will remain uniform after vectorization.
1536   std::vector<Value*> Worklist;
1537
1538   // Start with the conditional branch and walk up the block.
1539   Worklist.push_back(BB.getTerminator()->getOperand(0));
1540
1541   while (Worklist.size()) {
1542     Instruction *I = dyn_cast<Instruction>(Worklist.back());
1543     Worklist.pop_back();
1544
1545     // Look at instructions inside this block. Stop when reaching PHI nodes.
1546     if (!I || I->getParent() != &BB || isa<PHINode>(I))
1547       continue;
1548
1549     // This is a known uniform.
1550     Uniforms.insert(I);
1551
1552     // Insert all operands.
1553     for (int i=0, Op = I->getNumOperands(); i < Op; ++i) {
1554       Worklist.push_back(I->getOperand(i));
1555     }
1556   }
1557
1558   return true;
1559 }
1560
1561 bool LoopVectorizationLegality::canVectorizeMemory(BasicBlock &BB) {
1562   typedef SmallVector<Value*, 16> ValueVector;
1563   typedef SmallPtrSet<Value*, 16> ValueSet;
1564   // Holds the Load and Store *instructions*.
1565   ValueVector Loads;
1566   ValueVector Stores;
1567   PtrRtCheck.Pointers.clear();
1568   PtrRtCheck.Need = false;
1569
1570   // Scan the BB and collect legal loads and stores.
1571   for (BasicBlock::iterator it = BB.begin(), e = BB.end(); it != e; ++it) {
1572     Instruction *I = it;
1573
1574     // If this is a load, save it. If this instruction can read from memory
1575     // but is not a load, then we quit. Notice that we don't handle function
1576     // calls that read or write.
1577     if (I->mayReadFromMemory()) {
1578       LoadInst *Ld = dyn_cast<LoadInst>(I);
1579       if (!Ld) return false;
1580       if (!Ld->isSimple()) {
1581         DEBUG(dbgs() << "LV: Found a non-simple load.\n");
1582         return false;
1583       }
1584       Loads.push_back(Ld);
1585       continue;
1586     }
1587
1588     // Save store instructions. Abort if other instructions write to memory.
1589     if (I->mayWriteToMemory()) {
1590       StoreInst *St = dyn_cast<StoreInst>(I);
1591       if (!St) return false;
1592       if (!St->isSimple()) {
1593         DEBUG(dbgs() << "LV: Found a non-simple store.\n");
1594         return false;
1595       }
1596       Stores.push_back(St);
1597     }
1598   } // next instr.
1599
1600   // Now we have two lists that hold the loads and the stores.
1601   // Next, we find the pointers that they use.
1602
1603   // Check if we see any stores. If there are no stores, then we don't
1604   // care if the pointers are *restrict*.
1605   if (!Stores.size()) {
1606         DEBUG(dbgs() << "LV: Found a read-only loop!\n");
1607         return true;
1608   }
1609
1610   // Holds the read and read-write *pointers* that we find.
1611   ValueVector Reads;
1612   ValueVector ReadWrites;
1613
1614   // Holds the analyzed pointers. We don't want to call GetUnderlyingObjects
1615   // multiple times on the same object. If the ptr is accessed twice, once
1616   // for read and once for write, it will only appear once (on the write
1617   // list). This is okay, since we are going to check for conflicts between
1618   // writes and between reads and writes, but not between reads and reads.
1619   ValueSet Seen;
1620
1621   ValueVector::iterator I, IE;
1622   for (I = Stores.begin(), IE = Stores.end(); I != IE; ++I) {
1623     StoreInst *ST = dyn_cast<StoreInst>(*I);
1624     assert(ST && "Bad StoreInst");
1625     Value* Ptr = ST->getPointerOperand();
1626
1627     if (isUniform(Ptr)) {
1628       DEBUG(dbgs() << "LV: We don't allow storing to uniform addresses\n");
1629       return false;
1630     }
1631
1632     // If we did *not* see this pointer before, insert it to
1633     // the read-write list. At this phase it is only a 'write' list.
1634     if (Seen.insert(Ptr))
1635       ReadWrites.push_back(Ptr);
1636   }
1637
1638   for (I = Loads.begin(), IE = Loads.end(); I != IE; ++I) {
1639     LoadInst *LD = dyn_cast<LoadInst>(*I);
1640     assert(LD && "Bad LoadInst");
1641     Value* Ptr = LD->getPointerOperand();
1642     // If we did *not* see this pointer before, insert it to the
1643     // read list. If we *did* see it before, then it is already in
1644     // the read-write list. This allows us to vectorize expressions
1645     // such as A[i] += x;  Because the address of A[i] is a read-write
1646     // pointer. This only works if the index of A[i] is consecutive.
1647     // If the address of i is unknown (for example A[B[i]]) then we may
1648     // read a few words, modify, and write a few words, and some of the
1649     // words may be written to the same address.
1650     if (Seen.insert(Ptr) || !isConsecutivePtr(Ptr))
1651       Reads.push_back(Ptr);
1652   }
1653
1654   // If we write (or read-write) to a single destination and there are no
1655   // other reads in this loop then is it safe to vectorize.
1656   if (ReadWrites.size() == 1 && Reads.size() == 0) {
1657     DEBUG(dbgs() << "LV: Found a write-only loop!\n");
1658     return true;
1659   }
1660
1661   // Find pointers with computable bounds. We are going to use this information
1662   // to place a runtime bound check.
1663   bool RT = true;
1664   for (I = ReadWrites.begin(), IE = ReadWrites.end(); I != IE; ++I)
1665     if (hasComputableBounds(*I)) {
1666       PtrRtCheck.insert_pointer(SE, TheLoop, *I);
1667       DEBUG(dbgs() << "LV: Found a runtime check ptr:" << **I <<"\n");
1668     } else {
1669       RT = false;
1670       break;
1671     }
1672   for (I = Reads.begin(), IE = Reads.end(); I != IE; ++I)
1673     if (hasComputableBounds(*I)) {
1674       PtrRtCheck.insert_pointer(SE, TheLoop, *I);
1675       DEBUG(dbgs() << "LV: Found a runtime check ptr:" << **I <<"\n");
1676     } else {
1677       RT = false;
1678       break;
1679     }
1680
1681   // Check that we did not collect too many pointers or found a
1682   // unsizeable pointer.
1683   if (!RT || PtrRtCheck.Pointers.size() > RuntimeMemoryCheckThreshold) {
1684     PtrRtCheck.reset();
1685     RT = false;
1686   }
1687
1688   PtrRtCheck.Need = RT;
1689
1690   if (RT) {
1691     DEBUG(dbgs() << "LV: We can perform a memory runtime check if needed.\n");
1692   }
1693
1694   // Now that the pointers are in two lists (Reads and ReadWrites), we
1695   // can check that there are no conflicts between each of the writes and
1696   // between the writes to the reads.
1697   ValueSet WriteObjects;
1698   ValueVector TempObjects;
1699
1700   // Check that the read-writes do not conflict with other read-write
1701   // pointers.
1702   for (I = ReadWrites.begin(), IE = ReadWrites.end(); I != IE; ++I) {
1703     GetUnderlyingObjects(*I, TempObjects, DL);
1704     for (ValueVector::iterator it=TempObjects.begin(), e=TempObjects.end();
1705          it != e; ++it) {
1706       if (!isIdentifiedObject(*it)) {
1707         DEBUG(dbgs() << "LV: Found an unidentified write ptr:"<< **it <<"\n");
1708         return RT;
1709       }
1710       if (!WriteObjects.insert(*it)) {
1711         DEBUG(dbgs() << "LV: Found a possible write-write reorder:"
1712               << **it <<"\n");
1713         return RT;
1714       }
1715     }
1716     TempObjects.clear();
1717   }
1718
1719   /// Check that the reads don't conflict with the read-writes.
1720   for (I = Reads.begin(), IE = Reads.end(); I != IE; ++I) {
1721     GetUnderlyingObjects(*I, TempObjects, DL);
1722     for (ValueVector::iterator it=TempObjects.begin(), e=TempObjects.end();
1723          it != e; ++it) {
1724       if (!isIdentifiedObject(*it)) {
1725         DEBUG(dbgs() << "LV: Found an unidentified read ptr:"<< **it <<"\n");
1726         return RT;
1727       }
1728       if (WriteObjects.count(*it)) {
1729         DEBUG(dbgs() << "LV: Found a possible read/write reorder:"
1730               << **it <<"\n");
1731         return RT;
1732       }
1733     }
1734     TempObjects.clear();
1735   }
1736
1737   // It is safe to vectorize and we don't need any runtime checks.
1738   DEBUG(dbgs() << "LV: We don't need a runtime memory check.\n");
1739   PtrRtCheck.reset();
1740   return true;
1741 }
1742
1743 bool LoopVectorizationLegality::AddReductionVar(PHINode *Phi,
1744                                                 ReductionKind Kind) {
1745   if (Phi->getNumIncomingValues() != 2)
1746     return false;
1747
1748   // Find the possible incoming reduction variable.
1749   BasicBlock *BB = Phi->getParent();
1750   int SelfEdgeIdx = Phi->getBasicBlockIndex(BB);
1751   int InEdgeBlockIdx = (SelfEdgeIdx ? 0 : 1); // The other entry.
1752   Value *RdxStart = Phi->getIncomingValue(InEdgeBlockIdx);
1753
1754   // ExitInstruction is the single value which is used outside the loop.
1755   // We only allow for a single reduction value to be used outside the loop.
1756   // This includes users of the reduction, variables (which form a cycle
1757   // which ends in the phi node).
1758   Instruction *ExitInstruction = 0;
1759
1760   // Iter is our iterator. We start with the PHI node and scan for all of the
1761   // users of this instruction. All users must be instructions which can be
1762   // used as reduction variables (such as ADD). We may have a single
1763   // out-of-block user. They cycle must end with the original PHI.
1764   // Also, we can't have multiple block-local users.
1765   Instruction *Iter = Phi;
1766   while (true) {
1767     // Any reduction instr must be of one of the allowed kinds.
1768     if (!isReductionInstr(Iter, Kind))
1769       return false;
1770
1771     // Did we found a user inside this block ?
1772     bool FoundInBlockUser = false;
1773     // Did we reach the initial PHI node ?
1774     bool FoundStartPHI = false;
1775
1776     // If the instruction has no users then this is a broken
1777     // chain and can't be a reduction variable.
1778     if (Iter->use_empty())
1779       return false;
1780
1781     // For each of the *users* of iter.
1782     for (Value::use_iterator it = Iter->use_begin(), e = Iter->use_end();
1783          it != e; ++it) {
1784       Instruction *U = cast<Instruction>(*it);
1785       // We already know that the PHI is a user.
1786       if (U == Phi) {
1787         FoundStartPHI = true;
1788         continue;
1789       }
1790       // Check if we found the exit user.
1791       BasicBlock *Parent = U->getParent();
1792       if (Parent != BB) {
1793         // We must have a single exit instruction.
1794         if (ExitInstruction != 0)
1795           return false;
1796         ExitInstruction = Iter;
1797       }
1798       // We can't have multiple inside users.
1799       if (FoundInBlockUser)
1800         return false;
1801       FoundInBlockUser = true;
1802       Iter = U;
1803     }
1804
1805     // We found a reduction var if we have reached the original
1806     // phi node and we only have a single instruction with out-of-loop
1807     // users.
1808    if (FoundStartPHI && ExitInstruction) {
1809      // This instruction is allowed to have out-of-loop users.
1810      AllowedExit.insert(ExitInstruction);
1811
1812      // Save the description of this reduction variable.
1813      ReductionDescriptor RD(RdxStart, ExitInstruction, Kind);
1814      Reductions[Phi] = RD;
1815      return true;
1816    }
1817   }
1818 }
1819
1820 bool
1821 LoopVectorizationLegality::isReductionInstr(Instruction *I,
1822                                             ReductionKind Kind) {
1823     switch (I->getOpcode()) {
1824     default:
1825       return false;
1826     case Instruction::PHI:
1827       // possibly.
1828       return true;
1829     case Instruction::Add:
1830     case Instruction::Sub:
1831       return Kind == IntegerAdd;
1832     case Instruction::Mul:
1833       return Kind == IntegerMult;
1834     case Instruction::And:
1835       return Kind == IntegerAnd;
1836     case Instruction::Or:
1837       return Kind == IntegerOr;
1838     case Instruction::Xor:
1839       return Kind == IntegerXor;
1840     }
1841 }
1842
1843 bool LoopVectorizationLegality::isInductionVariable(PHINode *Phi) {
1844   Type *PhiTy = Phi->getType();
1845   // We only handle integer and pointer inductions variables.
1846   if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
1847     return false;
1848
1849   // Check that the PHI is consecutive and starts at zero.
1850   const SCEV *PhiScev = SE->getSCEV(Phi);
1851   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1852   if (!AR) {
1853     DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1854     return false;
1855   }
1856   const SCEV *Step = AR->getStepRecurrence(*SE);
1857
1858   // Integer inductions need to have a stride of one.
1859   if (PhiTy->isIntegerTy())
1860     return Step->isOne();
1861
1862   // Calculate the pointer stride and check if it is consecutive.
1863   const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
1864   if (!C) return false;
1865
1866   assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
1867   uint64_t Size = DL->getTypeAllocSize(PhiTy->getPointerElementType());
1868   return (C->getValue()->equalsInt(Size));
1869 }
1870
1871 bool LoopVectorizationLegality::hasComputableBounds(Value *Ptr) {
1872   const SCEV *PhiScev = SE->getSCEV(Ptr);
1873   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1874   if (!AR)
1875     return false;
1876
1877   return AR->isAffine();
1878 }
1879
1880 unsigned
1881 LoopVectorizationCostModel::findBestVectorizationFactor(unsigned VF) {
1882   if (!VTTI) {
1883     DEBUG(dbgs() << "LV: No vector target information. Not vectorizing. \n");
1884     return 1;
1885   }
1886
1887   float Cost = expectedCost(1);
1888   unsigned Width = 1;
1889   DEBUG(dbgs() << "LV: Scalar loop costs: "<< (int)Cost << ".\n");
1890   for (unsigned i=2; i <= VF; i*=2) {
1891     // Notice that the vector loop needs to be executed less times, so
1892     // we need to divide the cost of the vector loops by the width of
1893     // the vector elements.
1894     float VectorCost = expectedCost(i) / (float)i;
1895     DEBUG(dbgs() << "LV: Vector loop of width "<< i << " costs: " <<
1896           (int)VectorCost << ".\n");
1897     if (VectorCost < Cost) {
1898       Cost = VectorCost;
1899       Width = i;
1900     }
1901   }
1902
1903   DEBUG(dbgs() << "LV: Selecting VF = : "<< Width << ".\n");
1904   return Width;
1905 }
1906
1907 unsigned LoopVectorizationCostModel::expectedCost(unsigned VF) {
1908   // We can only estimate the cost of single basic block loops.
1909   assert(1 == TheLoop->getNumBlocks() && "Too many blocks in loop");
1910
1911   BasicBlock *BB = TheLoop->getHeader();
1912   unsigned Cost = 0;
1913
1914   // For each instruction in the old loop.
1915   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
1916     Instruction *Inst = it;
1917     unsigned C = getInstructionCost(Inst, VF);
1918     Cost += C;
1919     DEBUG(dbgs() << "LV: Found an estimated cost of "<< C <<" for VF "<< VF <<
1920           " For instruction: "<< *Inst << "\n");
1921   }
1922
1923   return Cost;
1924 }
1925
1926 unsigned
1927 LoopVectorizationCostModel::getInstructionCost(Instruction *I, unsigned VF) {
1928   assert(VTTI && "Invalid vector target transformation info");
1929
1930   // If we know that this instruction will remain uniform, check the cost of
1931   // the scalar version.
1932   if (Legal->isUniformAfterVectorization(I))
1933     VF = 1;
1934
1935   Type *RetTy = I->getType();
1936   Type *VectorTy = ToVectorTy(RetTy, VF);
1937
1938
1939   // TODO: We need to estimate the cost of intrinsic calls.
1940   switch (I->getOpcode()) {
1941     case Instruction::GetElementPtr:
1942       // We mark this instruction as zero-cost because scalar GEPs are usually
1943       // lowered to the intruction addressing mode. At the moment we don't
1944       // generate vector geps.
1945       return 0;
1946     case Instruction::Br: {
1947       return VTTI->getCFInstrCost(I->getOpcode());
1948     }
1949     case Instruction::PHI:
1950       return 0;
1951     case Instruction::Add:
1952     case Instruction::FAdd:
1953     case Instruction::Sub:
1954     case Instruction::FSub:
1955     case Instruction::Mul:
1956     case Instruction::FMul:
1957     case Instruction::UDiv:
1958     case Instruction::SDiv:
1959     case Instruction::FDiv:
1960     case Instruction::URem:
1961     case Instruction::SRem:
1962     case Instruction::FRem:
1963     case Instruction::Shl:
1964     case Instruction::LShr:
1965     case Instruction::AShr:
1966     case Instruction::And:
1967     case Instruction::Or:
1968     case Instruction::Xor: {
1969       return VTTI->getArithmeticInstrCost(I->getOpcode(), VectorTy);
1970     }
1971     case Instruction::Select: {
1972       SelectInst *SI = cast<SelectInst>(I);
1973       const SCEV *CondSCEV = SE->getSCEV(SI->getCondition());
1974       bool ScalarCond = (SE->isLoopInvariant(CondSCEV, TheLoop));
1975       Type *CondTy = SI->getCondition()->getType();
1976       if (ScalarCond)
1977         CondTy = VectorType::get(CondTy, VF);
1978
1979       return VTTI->getCmpSelInstrCost(I->getOpcode(), VectorTy, CondTy);
1980     }
1981     case Instruction::ICmp:
1982     case Instruction::FCmp: {
1983       Type *ValTy = I->getOperand(0)->getType();
1984       VectorTy = ToVectorTy(ValTy, VF);
1985       return VTTI->getCmpSelInstrCost(I->getOpcode(), VectorTy);
1986     }
1987     case Instruction::Store: {
1988       StoreInst *SI = cast<StoreInst>(I);
1989       Type *ValTy = SI->getValueOperand()->getType();
1990       VectorTy = ToVectorTy(ValTy, VF);
1991
1992       if (VF == 1)
1993         return VTTI->getMemoryOpCost(I->getOpcode(), ValTy,
1994                               SI->getAlignment(), SI->getPointerAddressSpace());
1995
1996       // Scalarized stores.
1997       if (!Legal->isConsecutivePtr(SI->getPointerOperand())) {
1998         unsigned Cost = 0;
1999         unsigned ExtCost = VTTI->getInstrCost(Instruction::ExtractElement,
2000                                               ValTy);
2001         // The cost of extracting from the value vector.
2002         Cost += VF * (ExtCost);
2003         // The cost of the scalar stores.
2004         Cost += VF * VTTI->getMemoryOpCost(I->getOpcode(),
2005                                            ValTy->getScalarType(),
2006                                            SI->getAlignment(),
2007                                            SI->getPointerAddressSpace());
2008         return Cost;
2009       }
2010
2011       // Wide stores.
2012       return VTTI->getMemoryOpCost(I->getOpcode(), VectorTy, SI->getAlignment(),
2013                                    SI->getPointerAddressSpace());
2014     }
2015     case Instruction::Load: {
2016       LoadInst *LI = cast<LoadInst>(I);
2017
2018       if (VF == 1)
2019         return VTTI->getMemoryOpCost(I->getOpcode(), RetTy,
2020                                      LI->getAlignment(),
2021                                      LI->getPointerAddressSpace());
2022
2023       // Scalarized loads.
2024       if (!Legal->isConsecutivePtr(LI->getPointerOperand())) {
2025         unsigned Cost = 0;
2026         unsigned InCost = VTTI->getInstrCost(Instruction::InsertElement, RetTy);
2027         // The cost of inserting the loaded value into the result vector.
2028         Cost += VF * (InCost);
2029         // The cost of the scalar stores.
2030         Cost += VF * VTTI->getMemoryOpCost(I->getOpcode(),
2031                                            RetTy->getScalarType(),
2032                                            LI->getAlignment(),
2033                                            LI->getPointerAddressSpace());
2034         return Cost;
2035       }
2036
2037       // Wide loads.
2038       return VTTI->getMemoryOpCost(I->getOpcode(), VectorTy, LI->getAlignment(),
2039                                    LI->getPointerAddressSpace());
2040     }
2041     case Instruction::ZExt:
2042     case Instruction::SExt:
2043     case Instruction::FPToUI:
2044     case Instruction::FPToSI:
2045     case Instruction::FPExt:
2046     case Instruction::PtrToInt:
2047     case Instruction::IntToPtr:
2048     case Instruction::SIToFP:
2049     case Instruction::UIToFP:
2050     case Instruction::Trunc:
2051     case Instruction::FPTrunc:
2052     case Instruction::BitCast: {
2053       Type *SrcVecTy = ToVectorTy(I->getOperand(0)->getType(), VF);
2054       return VTTI->getCastInstrCost(I->getOpcode(), VectorTy, SrcVecTy);
2055     }
2056     default: {
2057       // We are scalarizing the instruction. Return the cost of the scalar
2058       // instruction, plus the cost of insert and extract into vector
2059       // elements, times the vector width.
2060       unsigned Cost = 0;
2061
2062       bool IsVoid = RetTy->isVoidTy();
2063
2064       unsigned InsCost = (IsVoid ? 0 :
2065                           VTTI->getInstrCost(Instruction::InsertElement,
2066                                              VectorTy));
2067
2068       unsigned ExtCost = VTTI->getInstrCost(Instruction::ExtractElement,
2069                                             VectorTy);
2070
2071       // The cost of inserting the results plus extracting each one of the
2072       // operands.
2073       Cost += VF * (InsCost + ExtCost * I->getNumOperands());
2074
2075       // The cost of executing VF copies of the scalar instruction.
2076       Cost += VF * VTTI->getInstrCost(I->getOpcode(), RetTy);
2077       return Cost;
2078     }
2079   }// end of switch.
2080 }
2081
2082 Type* LoopVectorizationCostModel::ToVectorTy(Type *Scalar, unsigned VF) {
2083   if (Scalar->isVoidTy() || VF == 1)
2084     return Scalar;
2085   return VectorType::get(Scalar, VF);
2086 }
2087
2088 } // namespace
2089
2090 char LoopVectorize::ID = 0;
2091 static const char lv_name[] = "Loop Vectorization";
2092 INITIALIZE_PASS_BEGIN(LoopVectorize, LV_NAME, lv_name, false, false)
2093 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
2094 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
2095 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
2096 INITIALIZE_PASS_END(LoopVectorize, LV_NAME, lv_name, false, false)
2097
2098 namespace llvm {
2099   Pass *createLoopVectorizePass() {
2100     return new LoopVectorize();
2101   }
2102 }
2103