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/ScalarEvolutionExpressions.h"
  59 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  60 #include "llvm/Analysis/LoopInfo.h"
  61 #include "llvm/Analysis/ValueTracking.h"
  62 #include "llvm/Transforms/Scalar.h"
  63 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  64 #include "llvm/TargetTransformInfo.h"
  65 #include "llvm/Support/CommandLine.h"
  66 #include "llvm/Support/Debug.h"
  67 #include "llvm/Support/raw_ostream.h"
  68 #include "llvm/DataLayout.h"
  69 #include "llvm/Transforms/Utils/Local.h"
  70 #include <algorithm>
  71 using namespace llvm;
  72
  73 static cl::opt<unsigned>
  74 VectorizationFactor("force-vector-width", cl::init(0), cl::Hidden,
  75           cl::desc("Set the default vectorization width. Zero is autoselect."));
  76
  77 namespace {
  78
  79 // Forward declarations.
  80 class LoopVectorizationLegality;
  81 class LoopVectorizationCostModel;
  82
  83 /// SingleBlockLoopVectorizer vectorizes loops which contain only one basic
  84 /// block to a specified vectorization factor (VF).
  85 /// This class performs the widening of scalars into vectors, or multiple
  86 /// scalars. This class also implements the following features:
  87 /// * It inserts an epilogue loop for handling loops that don't have iteration
  88 ///   counts that are known to be a multiple of the vectorization factor.
  89 /// * It handles the code generation for reduction variables.
  90 /// * Scalarization (implementation using scalars) of un-vectorizable
  91 ///   instructions.
  92 /// SingleBlockLoopVectorizer does not perform any vectorization-legality
  93 /// checks, and relies on the caller to check for the different legality
  94 /// aspects. The SingleBlockLoopVectorizer relies on the
  95 /// LoopVectorizationLegality class to provide information about the induction
  96 /// and reduction variables that were found to a given vectorization factor.
  97 class SingleBlockLoopVectorizer {
  98 public:
  99   /// Ctor.
 100   SingleBlockLoopVectorizer(Loop *Orig, ScalarEvolution *Se, LoopInfo *Li,
 101                             LPPassManager *Lpm, unsigned VecWidth):
 102   OrigLoop(Orig), SE(Se), LI(Li), LPM(Lpm), VF(VecWidth),
 103   Builder(Se->getContext()), Induction(0), OldInduction(0) { }
 104
 105   // Perform the actual loop widening (vectorization).
 106   void vectorize(LoopVectorizationLegality *Legal) {
 107     ///Create a new empty loop. Unlink the old loop and connect the new one.
 108     createEmptyLoop(Legal);
 109     /// Widen each instruction in the old loop to a new one in the new loop.
 110     /// Use the Legality module to find the induction and reduction variables.
 111     vectorizeLoop(Legal);
 112     // register the new loop.
 113     cleanup();
 114  }
 115
 116 private:
 117   /// Create an empty loop, based on the loop ranges of the old loop.
 118   void createEmptyLoop(LoopVectorizationLegality *Legal);
 119   /// Copy and widen the instructions from the old loop.
 120   void vectorizeLoop(LoopVectorizationLegality *Legal);
 121   /// Insert the new loop to the loop hierarchy and pass manager.
 122   void cleanup();
 123
 124   /// This instruction is un-vectorizable. Implement it as a sequence
 125   /// of scalars.
 126   void scalarizeInstruction(Instruction *Instr);
 127
 128   /// Create a broadcast instruction. This method generates a broadcast
 129   /// instruction (shuffle) for loop invariant values and for the induction
 130   /// value. If this is the induction variable then we extend it to N, N+1, ...
 131   /// this is needed because each iteration in the loop corresponds to a SIMD
 132   /// element.
 133   Value *getBroadcastInstrs(Value *V);
 134
 135   /// This is a helper function used by getBroadcastInstrs. It adds 0, 1, 2 ..
 136   /// for each element in the vector. Starting from zero.
 137   Value *getConsecutiveVector(Value* Val);
 138
 139   /// When we go over instructions in the basic block we rely on previous
 140   /// values within the current basic block or on loop invariant values.
 141   /// When we widen (vectorize) values we place them in the map. If the values
 142   /// are not within the map, they have to be loop invariant, so we simply
 143   /// broadcast them into a vector.
 144   Value *getVectorValue(Value *V);
 145
 146   /// Get a uniform vector of constant integers. We use this to get
 147   /// vectors of ones and zeros for the reduction code.
 148   Constant* getUniformVector(unsigned Val, Type* ScalarTy);
 149
 150   typedef DenseMap<Value*, Value*> ValueMap;
 151
 152   /// The original loop.
 153   Loop *OrigLoop;
 154   // Scev analysis to use.
 155   ScalarEvolution *SE;
 156   // Loop Info.
 157   LoopInfo *LI;
 158   // Loop Pass Manager;
 159   LPPassManager *LPM;
 160   // The vectorization factor to use.
 161   unsigned VF;
 162
 163   // The builder that we use
 164   IRBuilder<> Builder;
 165
 166   // --- Vectorization state ---
 167
 168   /// Middle Block between the vector and the scalar.
 169   BasicBlock *LoopMiddleBlock;
 170   ///The ExitBlock of the scalar loop.
 171   BasicBlock *LoopExitBlock;
 172   ///The vector loop body.
 173   BasicBlock *LoopVectorBody;
 174   ///The scalar loop body.
 175   BasicBlock *LoopScalarBody;
 176   ///The first bypass block.
 177   BasicBlock *LoopBypassBlock;
 178
 179   /// The new Induction variable which was added to the new block.
 180   PHINode *Induction;
 181   /// The induction variable of the old basic block.
 182   PHINode *OldInduction;
 183   // Maps scalars to widened vectors.
 184   ValueMap WidenMap;
 185 };
 186
 187 /// LoopVectorizationLegality checks if it is legal to vectorize a loop, and
 188 /// to what vectorization factor.
 189 /// This class does not look at the profitability of vectorization, only the
 190 /// legality. This class has two main kinds of checks:
 191 /// * Memory checks - The code in canVectorizeMemory checks if vectorization
 192 ///   will change the order of memory accesses in a way that will change the
 193 ///   correctness of the program.
 194 /// * Scalars checks - The code in canVectorizeBlock checks for a number
 195 ///   of different conditions, such as the availability of a single induction
 196 ///   variable, that all types are supported and vectorize-able, etc.
 197 /// This code reflects the capabilities of SingleBlockLoopVectorizer.
 198 /// This class is also used by SingleBlockLoopVectorizer for identifying
 199 /// induction variable and the different reduction variables.
 200 class LoopVectorizationLegality {
 201 public:
 202   LoopVectorizationLegality(Loop *Lp, ScalarEvolution *Se, DataLayout *Dl):
 203   TheLoop(Lp), SE(Se), DL(Dl), Induction(0) { }
 204
 205   /// This represents the kinds of reductions that we support.
 206   /// We use the enum values to hold the 'identity' value for
 207   /// each operand. This value does not change the result if applied.
 208   enum ReductionKind {
 209     NoReduction = -1, /// Not a reduction.
 210     IntegerAdd  = 0,  /// Sum of numbers.
 211     IntegerMult = 1,  /// Product of numbers.
 212     IntegerOr   = 2,  /// Bitwise or logical OR of numbers.
 213     IntegerAnd  = 3,  /// Bitwise or logical AND of numbers.
 214     IntegerXor  = 4   /// Bitwise or logical XOR of numbers.
 215   };
 216
 217   /// This POD struct holds information about reduction variables.
 218   struct ReductionDescriptor {
 219     // Default C'tor
 220     ReductionDescriptor():
 221     StartValue(0), LoopExitInstr(0), Kind(NoReduction) {}
 222
 223     // C'tor.
 224     ReductionDescriptor(Value *Start, Instruction *Exit, ReductionKind K):
 225     StartValue(Start), LoopExitInstr(Exit), Kind(K) {}
 226
 227     // The starting value of the reduction.
 228     // It does not have to be zero!
 229     Value *StartValue;
 230     // The instruction who's value is used outside the loop.
 231     Instruction *LoopExitInstr;
 232     // The kind of the reduction.
 233     ReductionKind Kind;
 234   };
 235
 236   /// ReductionList contains the reduction descriptors for all
 237   /// of the reductions that were found in the loop.
 238   typedef DenseMap<PHINode*, ReductionDescriptor> ReductionList;
 239
 240   /// Returns true if it is legal to vectorize this loop.
 241   /// This does not mean that it is profitable to vectorize this
 242   /// loop, only that it is legal to do so.
 243   bool canVectorize();
 244
 245   /// Returns the Induction variable.
 246   PHINode *getInduction() {return Induction;}
 247
 248   /// Returns the reduction variables found in the loop.
 249   ReductionList *getReductionVars() { return &Reductions; }
 250
 251   /// Check if the pointer returned by this GEP is consecutive
 252   /// when the index is vectorized. This happens when the last
 253   /// index of the GEP is consecutive, like the induction variable.
 254   /// This check allows us to vectorize A[idx] into a wide load/store.
 255   bool isConsecutiveGep(Value *Ptr);
 256
 257   /// Returns true if this instruction will remain scalar after vectorization.
 258   bool isUniformAfterVectorization(Instruction* I) {return Uniforms.count(I);}
 259
 260 private:
 261   /// Check if a single basic block loop is vectorizable.
 262   /// At this point we know that this is a loop with a constant trip count
 263   /// and we only need to check individual instructions.
 264   bool canVectorizeBlock(BasicBlock &BB);
 265
 266   /// When we vectorize loops we may change the order in which
 267   /// we read and write from memory. This method checks if it is
 268   /// legal to vectorize the code, considering only memory constrains.
 269   /// Returns true if BB is vectorizable
 270   bool canVectorizeMemory(BasicBlock &BB);
 271
 272   /// Returns True, if 'Phi' is the kind of reduction variable for type
 273   /// 'Kind'. If this is a reduction variable, it adds it to ReductionList.
 274   bool AddReductionVar(PHINode *Phi, ReductionKind Kind);
 275   /// Returns true if the instruction I can be a reduction variable of type
 276   /// 'Kind'.
 277   bool isReductionInstr(Instruction *I, ReductionKind Kind);
 278   /// Returns True, if 'Phi' is an induction variable.
 279   bool isInductionVariable(PHINode *Phi);
 280
 281   /// The loop that we evaluate.
 282   Loop *TheLoop;
 283   /// Scev analysis.
 284   ScalarEvolution *SE;
 285   /// DataLayout analysis.
 286   DataLayout *DL;
 287
 288   //  ---  vectorization state --- //
 289
 290   /// Holds the induction variable.
 291   PHINode *Induction;
 292   /// Holds the reduction variables.
 293   ReductionList Reductions;
 294   /// Allowed outside users. This holds the reduction
 295   /// vars which can be accessed from outside the loop.
 296   SmallPtrSet<Value*, 4> AllowedExit;
 297   /// This set holds the variables which are known to be uniform after
 298   /// vectorization.
 299   SmallPtrSet<Instruction*, 4> Uniforms;
 300 };
 301
 302 /// LoopVectorizationCostModel - estimates the expected speedups due to
 303 /// vectorization.
 304 /// In many cases vectorization is not profitable. This can happen because
 305 /// of a number of reasons. In this class we mainly attempt to predict
 306 /// the expected speedup/slowdowns due to the supported instruction set.
 307 /// We use the VectorTargetTransformInfo to query the different backends
 308 /// for the cost of different operations.
 309 class LoopVectorizationCostModel {
 310 public:
 311   /// C'tor.
 312   LoopVectorizationCostModel(Loop *Lp, ScalarEvolution *Se,
 313                              LoopVectorizationLegality *Leg,
 314                              const VectorTargetTransformInfo *Vtti):
 315   TheLoop(Lp), SE(Se), Legal(Leg), VTTI(Vtti) { }
 316
 317   /// Returns the most profitable vectorization factor for the loop that is
 318   /// smaller or equal to the VF argument. This method checks every power
 319   /// of two up to VF.
 320   unsigned findBestVectorizationFactor(unsigned VF = 8);
 321
 322 private:
 323   /// Returns the expected execution cost. The unit of the cost does
 324   /// not matter because we use the 'cost' units to compare different
 325   /// vector widths. The cost that is returned is *not* normalized by
 326   /// the factor width.
 327   unsigned expectedCost(unsigned VF);
 328
 329   /// Returns the execution time cost of an instruction for a given vector
 330   /// width. Vector width of one means scalar.
 331   unsigned getInstructionCost(Instruction *I, unsigned VF);
 332
 333   /// A helper function for converting Scalar types to vector types.
 334   /// If the incoming type is void, we return void. If the VF is 1, we return
 335   /// the scalar type.
 336   static Type* ToVectorTy(Type *Scalar, unsigned VF);
 337
 338   /// The loop that we evaluate.
 339   Loop *TheLoop;
 340   /// Scev analysis.
 341   ScalarEvolution *SE;
 342
 343   /// Vectorization legality.
 344   LoopVectorizationLegality *Legal;
 345   /// Vector target information.
 346   const VectorTargetTransformInfo *VTTI;
 347 };
 348
 349 struct LoopVectorize : public LoopPass {
 350   static char ID; // Pass identification, replacement for typeid
 351
 352   LoopVectorize() : LoopPass(ID) {
 353     initializeLoopVectorizePass(*PassRegistry::getPassRegistry());
 354   }
 355
 356   ScalarEvolution *SE;
 357   DataLayout *DL;
 358   LoopInfo *LI;
 359   TargetTransformInfo *TTI;
 360
 361   virtual bool runOnLoop(Loop *L, LPPassManager &LPM) {
 362     // We only vectorize innermost loops.
 363     if (!L->empty())
 364       return false;
 365
 366     SE = &getAnalysis<ScalarEvolution>();
 367     DL = getAnalysisIfAvailable<DataLayout>();
 368     LI = &getAnalysis<LoopInfo>();
 369     TTI = getAnalysisIfAvailable<TargetTransformInfo>();
 370
 371     DEBUG(dbgs() << "LV: Checking a loop in \"" <<
 372           L->getHeader()->getParent()->getName() << "\"\n");
 373
 374     // Check if it is legal to vectorize the loop.
 375     LoopVectorizationLegality LVL(L, SE, DL);
 376     if (!LVL.canVectorize()) {
 377       DEBUG(dbgs() << "LV: Not vectorizing.\n");
 378       return false;
 379     }
 380
 381     // Select the preffered vectorization factor.
 382     unsigned VF = 1;
 383     if (VectorizationFactor == 0) {
 384       const VectorTargetTransformInfo *VTTI = 0;
 385       if (TTI)
 386         VTTI = TTI->getVectorTargetTransformInfo();
 387       // Use the cost model.
 388       LoopVectorizationCostModel CM(L, SE, &LVL, VTTI);
 389       VF = CM.findBestVectorizationFactor();
 390
 391       if (VF == 1) {
 392         DEBUG(dbgs() << "LV: Vectorization is possible but not beneficial.\n");
 393         return false;
 394       }
 395
 396     } else {
 397       // Use the user command flag.
 398       VF = VectorizationFactor;
 399     }
 400
 401     DEBUG(dbgs() << "LV: Found a vectorizable loop ("<< VF << ").\n");
 402
 403     // If we decided that it is *legal* to vectorizer the loop then do it.
 404     SingleBlockLoopVectorizer LB(L, SE, LI, &LPM, VF);
 405     LB.vectorize(&LVL);
 406
 407     DEBUG(verifyFunction(*L->getHeader()->getParent()));
 408     return true;
 409   }
 410
 411   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 412     LoopPass::getAnalysisUsage(AU);
 413     AU.addRequiredID(LoopSimplifyID);
 414     AU.addRequiredID(LCSSAID);
 415     AU.addRequired<LoopInfo>();
 416     AU.addRequired<ScalarEvolution>();
 417   }
 418
 419 };
 420
 421 Value *SingleBlockLoopVectorizer::getBroadcastInstrs(Value *V) {
 422   // Instructions that access the old induction variable
 423   // actually want to get the new one.
 424   if (V == OldInduction)
 425     V = Induction;
 426   // Create the types.
 427   LLVMContext &C = V->getContext();
 428   Type *VTy = VectorType::get(V->getType(), VF);
 429   Type *I32 = IntegerType::getInt32Ty(C);
 430   Constant *Zero = ConstantInt::get(I32, 0);
 431   Value *Zeros = ConstantAggregateZero::get(VectorType::get(I32, VF));
 432   Value *UndefVal = UndefValue::get(VTy);
 433   // Insert the value into a new vector.
 434   Value *SingleElem = Builder.CreateInsertElement(UndefVal, V, Zero);
 435   // Broadcast the scalar into all locations in the vector.
 436   Value *Shuf = Builder.CreateShuffleVector(SingleElem, UndefVal, Zeros,
 437                                              "broadcast");
 438   // We are accessing the induction variable. Make sure to promote the
 439   // index for each consecutive SIMD lane. This adds 0,1,2 ... to all lanes.
 440   if (V == Induction)
 441     return getConsecutiveVector(Shuf);
 442   return Shuf;
 443 }
 444
 445 Value *SingleBlockLoopVectorizer::getConsecutiveVector(Value* Val) {
 446   assert(Val->getType()->isVectorTy() && "Must be a vector");
 447   assert(Val->getType()->getScalarType()->isIntegerTy() &&
 448          "Elem must be an integer");
 449   // Create the types.
 450   Type *ITy = Val->getType()->getScalarType();
 451   VectorType *Ty = cast<VectorType>(Val->getType());
 452   unsigned VLen = Ty->getNumElements();
 453   SmallVector<Constant*, 8> Indices;
 454
 455   // Create a vector of consecutive numbers from zero to VF.
 456   for (unsigned i = 0; i < VLen; ++i)
 457     Indices.push_back(ConstantInt::get(ITy, i));
 458
 459   // Add the consecutive indices to the vector value.
 460   Constant *Cv = ConstantVector::get(Indices);
 461   assert(Cv->getType() == Val->getType() && "Invalid consecutive vec");
 462   return Builder.CreateAdd(Val, Cv, "induction");
 463 }
 464
 465 bool LoopVectorizationLegality::isConsecutiveGep(Value *Ptr) {
 466   GetElementPtrInst *Gep = dyn_cast_or_null<GetElementPtrInst>(Ptr);
 467   if (!Gep)
 468     return false;
 469
 470   unsigned NumOperands = Gep->getNumOperands();
 471   Value *LastIndex = Gep->getOperand(NumOperands - 1);
 472
 473   // Check that all of the gep indices are uniform except for the last.
 474   for (unsigned i = 0; i < NumOperands - 1; ++i)
 475     if (!SE->isLoopInvariant(SE->getSCEV(Gep->getOperand(i)), TheLoop))
 476       return false;
 477
 478   // We can emit wide load/stores only of the last index is the induction
 479   // variable.
 480   const SCEV *Last = SE->getSCEV(LastIndex);
 481   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Last)) {
 482     const SCEV *Step = AR->getStepRecurrence(*SE);
 483
 484     // The memory is consecutive because the last index is consecutive
 485     // and all other indices are loop invariant.
 486     if (Step->isOne())
 487       return true;
 488   }
 489
 490   return false;
 491 }
 492
 493 Value *SingleBlockLoopVectorizer::getVectorValue(Value *V) {
 494   assert(!V->getType()->isVectorTy() && "Can't widen a vector");
 495   // If we saved a vectorized copy of V, use it.
 496   Value *&MapEntry = WidenMap[V];
 497   if (MapEntry)
 498     return MapEntry;
 499
 500   // Broadcast V and save the value for future uses.
 501   Value *B = getBroadcastInstrs(V);
 502   MapEntry = B;
 503   return B;
 504 }
 505
 506 Constant*
 507 SingleBlockLoopVectorizer::getUniformVector(unsigned Val, Type* ScalarTy) {
 508   SmallVector<Constant*, 8> Indices;
 509   // Create a vector of consecutive numbers from zero to VF.
 510   for (unsigned i = 0; i < VF; ++i)
 511     Indices.push_back(ConstantInt::get(ScalarTy, Val));
 512
 513   // Add the consecutive indices to the vector value.
 514   return ConstantVector::get(Indices);
 515 }
 516
 517 void SingleBlockLoopVectorizer::scalarizeInstruction(Instruction *Instr) {
 518   assert(!Instr->getType()->isAggregateType() && "Can't handle vectors");
 519   // Holds vector parameters or scalars, in case of uniform vals.
 520   SmallVector<Value*, 8> Params;
 521
 522   // Find all of the vectorized parameters.
 523   for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) {
 524     Value *SrcOp = Instr->getOperand(op);
 525
 526     // If we are accessing the old induction variable, use the new one.
 527     if (SrcOp == OldInduction) {
 528       Params.push_back(getBroadcastInstrs(Induction));
 529       continue;
 530     }
 531
 532     // Try using previously calculated values.
 533     Instruction *SrcInst = dyn_cast<Instruction>(SrcOp);
 534
 535     // If the src is an instruction that appeared earlier in the basic block
 536     // then it should already be vectorized.
 537     if (SrcInst && SrcInst->getParent() == Instr->getParent()) {
 538       assert(WidenMap.count(SrcInst) && "Source operand is unavailable");
 539       // The parameter is a vector value from earlier.
 540       Params.push_back(WidenMap[SrcInst]);
 541     } else {
 542       // The parameter is a scalar from outside the loop. Maybe even a constant.
 543       Params.push_back(SrcOp);
 544     }
 545   }
 546
 547   assert(Params.size() == Instr->getNumOperands() &&
 548          "Invalid number of operands");
 549
 550   // Does this instruction return a value ?
 551   bool IsVoidRetTy = Instr->getType()->isVoidTy();
 552   Value *VecResults = 0;
 553
 554   // If we have a return value, create an empty vector. We place the scalarized
 555   // instructions in this vector.
 556   if (!IsVoidRetTy)
 557     VecResults = UndefValue::get(VectorType::get(Instr->getType(), VF));
 558
 559   // For each scalar that we create:
 560   for (unsigned i = 0; i < VF; ++i) {
 561     Instruction *Cloned = Instr->clone();
 562     if (!IsVoidRetTy)
 563       Cloned->setName(Instr->getName() + ".cloned");
 564     // Replace the operands of the cloned instrucions with extracted scalars.
 565     for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) {
 566       Value *Op = Params[op];
 567       // Param is a vector. Need to extract the right lane.
 568       if (Op->getType()->isVectorTy())
 569         Op = Builder.CreateExtractElement(Op, Builder.getInt32(i));
 570       Cloned->setOperand(op, Op);
 571     }
 572
 573     // Place the cloned scalar in the new loop.
 574     Builder.Insert(Cloned);
 575
 576     // If the original scalar returns a value we need to place it in a vector
 577     // so that future users will be able to use it.
 578     if (!IsVoidRetTy)
 579       VecResults = Builder.CreateInsertElement(VecResults, Cloned,
 580                                                Builder.getInt32(i));
 581   }
 582
 583   if (!IsVoidRetTy)
 584     WidenMap[Instr] = VecResults;
 585 }
 586
 587 void SingleBlockLoopVectorizer::createEmptyLoop(LoopVectorizationLegality *Legal) {
 588   /*
 589    In this function we generate a new loop. The new loop will contain
 590    the vectorized instructions while the old loop will continue to run the
 591    scalar remainder.
 592
 593     [ ] <-- vector loop bypass.
 594   /  |
 595  /   v
 596 |   [ ]     <-- vector pre header.
 597 |    |
 598 |    v
 599 |   [  ] \
 600 |   [  ]_|   <-- vector loop.
 601 |    |
 602  \   v
 603    >[ ]   <--- middle-block.
 604   /  |
 605  /   v
 606 |   [ ]     <--- new preheader.
 607 |    |
 608 |    v
 609 |   [ ] \
 610 |   [ ]_|   <-- old scalar loop to handle remainder.
 611  \   |
 612   \  v
 613    >[ ]     <-- exit block.
 614    ...
 615    */
 616
 617   // This is the original scalar-loop preheader.
 618   BasicBlock *BypassBlock = OrigLoop->getLoopPreheader();
 619   BasicBlock *ExitBlock = OrigLoop->getExitBlock();
 620   assert(ExitBlock && "Must have an exit block");
 621
 622   assert(OrigLoop->getNumBlocks() == 1 && "Invalid loop");
 623   assert(BypassBlock && "Invalid loop structure");
 624
 625   BasicBlock *VectorPH =
 626       BypassBlock->splitBasicBlock(BypassBlock->getTerminator(), "vector.ph");
 627   BasicBlock *VecBody = VectorPH->splitBasicBlock(VectorPH->getTerminator(),
 628                                                  "vector.body");
 629
 630   BasicBlock *MiddleBlock = VecBody->splitBasicBlock(VecBody->getTerminator(),
 631                                                   "middle.block");
 632   BasicBlock *ScalarPH =
 633     MiddleBlock->splitBasicBlock(MiddleBlock->getTerminator(),
 634                                  "scalar.preheader");
 635   // Find the induction variable.
 636   BasicBlock *OldBasicBlock = OrigLoop->getHeader();
 637   OldInduction = Legal->getInduction();
 638   assert(OldInduction && "We must have a single phi node.");
 639   Type *IdxTy = OldInduction->getType();
 640
 641   // Use this IR builder to create the loop instructions (Phi, Br, Cmp)
 642   // inside the loop.
 643   Builder.SetInsertPoint(VecBody->getFirstInsertionPt());
 644
 645   // Generate the induction variable.
 646   Induction = Builder.CreatePHI(IdxTy, 2, "index");
 647   Constant *Zero = ConstantInt::get(IdxTy, 0);
 648   Constant *Step = ConstantInt::get(IdxTy, VF);
 649
 650   // Find the loop boundaries.
 651   const SCEV *ExitCount = SE->getExitCount(OrigLoop, OrigLoop->getHeader());
 652   assert(ExitCount != SE->getCouldNotCompute() && "Invalid loop count");
 653
 654   // Get the total trip count from the count by adding 1.
 655   ExitCount = SE->getAddExpr(ExitCount,
 656                              SE->getConstant(ExitCount->getType(), 1));
 657
 658   // Expand the trip count and place the new instructions in the preheader.
 659   // Notice that the pre-header does not change, only the loop body.
 660   SCEVExpander Exp(*SE, "induction");
 661   Instruction *Loc = BypassBlock->getTerminator();
 662
 663   // We may need to extend the index in case there is a type mismatch.
 664   // We know that the count starts at zero and does not overflow.
 665   // We are using Zext because it should be less expensive.
 666   if (ExitCount->getType() != Induction->getType())
 667     ExitCount = SE->getZeroExtendExpr(ExitCount, IdxTy);
 668
 669   // Count holds the overall loop count (N).
 670   Value *Count = Exp.expandCodeFor(ExitCount, Induction->getType(), Loc);
 671   // Now we need to generate the expression for N - (N % VF), which is
 672   // the part that the vectorized body will execute.
 673   Constant *CIVF = ConstantInt::get(IdxTy, VF);
 674   Value *R = BinaryOperator::CreateURem(Count, CIVF, "n.mod.vf", Loc);
 675   Value *CountRoundDown = BinaryOperator::CreateSub(Count, R, "n.vec", Loc);
 676
 677   // Now, compare the new count to zero. If it is zero, jump to the scalar part.
 678   Value *Cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ,
 679                                CountRoundDown, ConstantInt::getNullValue(IdxTy),
 680                                "cmp.zero", Loc);
 681   BranchInst::Create(MiddleBlock, VectorPH, Cmp, Loc);
 682   // Remove the old terminator.
 683   Loc->eraseFromParent();
 684
 685   // Add a check in the middle block to see if we have completed
 686   // all of the iterations in the first vector loop.
 687   // If (N - N%VF) == N, then we *don't* need to run the remainder.
 688   Value *CmpN = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, Count,
 689                                 CountRoundDown, "cmp.n",
 690                                 MiddleBlock->getTerminator());
 691
 692   BranchInst::Create(ExitBlock, ScalarPH, CmpN, MiddleBlock->getTerminator());
 693   // Remove the old terminator.
 694   MiddleBlock->getTerminator()->eraseFromParent();
 695
 696   // Create i+1 and fill the PHINode.
 697   Value *NextIdx = Builder.CreateAdd(Induction, Step, "index.next");
 698   Induction->addIncoming(Zero, VectorPH);
 699   Induction->addIncoming(NextIdx, VecBody);
 700   // Create the compare.
 701   Value *ICmp = Builder.CreateICmpEQ(NextIdx, CountRoundDown);
 702   Builder.CreateCondBr(ICmp, MiddleBlock, VecBody);
 703
 704   // Now we have two terminators. Remove the old one from the block.
 705   VecBody->getTerminator()->eraseFromParent();
 706
 707   // Fix the scalar body iteration count.
 708   unsigned BlockIdx = OldInduction->getBasicBlockIndex(ScalarPH);
 709   OldInduction->setIncomingValue(BlockIdx, CountRoundDown);
 710
 711   // Get ready to start creating new instructions into the vectorized body.
 712   Builder.SetInsertPoint(VecBody->getFirstInsertionPt());
 713
 714   // Register the new loop.
 715   Loop* Lp = new Loop();
 716   LPM->insertLoop(Lp, OrigLoop->getParentLoop());
 717
 718   Lp->addBasicBlockToLoop(VecBody, LI->getBase());
 719
 720   Loop *ParentLoop = OrigLoop->getParentLoop();
 721   if (ParentLoop) {
 722     ParentLoop->addBasicBlockToLoop(ScalarPH, LI->getBase());
 723     ParentLoop->addBasicBlockToLoop(VectorPH, LI->getBase());
 724     ParentLoop->addBasicBlockToLoop(MiddleBlock, LI->getBase());
 725   }
 726
 727   // Save the state.
 728   LoopMiddleBlock = MiddleBlock;
 729   LoopExitBlock = ExitBlock;
 730   LoopVectorBody = VecBody;
 731   LoopScalarBody = OldBasicBlock;
 732   LoopBypassBlock = BypassBlock;
 733 }
 734
 735 void
 736 SingleBlockLoopVectorizer::vectorizeLoop(LoopVectorizationLegality *Legal) {
 737   //===------------------------------------------------===//
 738   //
 739   // Notice: any optimization or new instruction that go
 740   // into the code below should be also be implemented in
 741   // the cost-model.
 742   //
 743   //===------------------------------------------------===//
 744   typedef SmallVector<PHINode*, 4> PhiVector;
 745   BasicBlock &BB = *OrigLoop->getHeader();
 746   Constant *Zero = ConstantInt::get(
 747     IntegerType::getInt32Ty(BB.getContext()), 0);
 748
 749   // In order to support reduction variables we need to be able to vectorize
 750   // Phi nodes. Phi nodes have cycles, so we need to vectorize them in two
 751   // steages. First, we create a new vector PHI node with no incoming edges.
 752   // We use this value when we vectorize all of the instructions that use the
 753   // PHI. Next, after all of the instructions in the block are complete we
 754   // add the new incoming edges to the PHI. At this point all of the
 755   // instructions in the basic block are vectorized, so we can use them to
 756   // construct the PHI.
 757   PhiVector PHIsToFix;
 758
 759   // For each instruction in the old loop.
 760   for (BasicBlock::iterator it = BB.begin(), e = BB.end(); it != e; ++it) {
 761     Instruction *Inst = it;
 762
 763     switch (Inst->getOpcode()) {
 764       case Instruction::Br:
 765         // Nothing to do for PHIs and BR, since we already took care of the
 766         // loop control flow instructions.
 767         continue;
 768       case Instruction::PHI:{
 769         PHINode* P = cast<PHINode>(Inst);
 770         // Special handling for the induction var.
 771         if (OldInduction == Inst)
 772           continue;
 773         // This is phase one of vectorizing PHIs.
 774         // This has to be a reduction variable.
 775         assert(Legal->getReductionVars()->count(P) && "Not a Reduction");
 776         Type *VecTy = VectorType::get(Inst->getType(), VF);
 777         WidenMap[Inst] = Builder.CreatePHI(VecTy, 2, "vec.phi");
 778         PHIsToFix.push_back(P);
 779         continue;
 780       }
 781       case Instruction::Add:
 782       case Instruction::FAdd:
 783       case Instruction::Sub:
 784       case Instruction::FSub:
 785       case Instruction::Mul:
 786       case Instruction::FMul:
 787       case Instruction::UDiv:
 788       case Instruction::SDiv:
 789       case Instruction::FDiv:
 790       case Instruction::URem:
 791       case Instruction::SRem:
 792       case Instruction::FRem:
 793       case Instruction::Shl:
 794       case Instruction::LShr:
 795       case Instruction::AShr:
 796       case Instruction::And:
 797       case Instruction::Or:
 798       case Instruction::Xor: {
 799         // Just widen binops.
 800         BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst);
 801         Value *A = getVectorValue(Inst->getOperand(0));
 802         Value *B = getVectorValue(Inst->getOperand(1));
 803         // Use this vector value for all users of the original instruction.
 804         WidenMap[Inst] = Builder.CreateBinOp(BinOp->getOpcode(), A, B);
 805         break;
 806       }
 807       case Instruction::Select: {
 808         // Widen selects.
 809         // If the selector is loop invariant we can create a select
 810         // instruction with a scalar condition. Otherwise, use vector-select.
 811         Value *Cond = Inst->getOperand(0);
 812         bool InvariantCond = SE->isLoopInvariant(SE->getSCEV(Cond), OrigLoop);
 813
 814         // The condition can be loop invariant  but still defined inside the
 815         // loop. This means that we can't just use the original 'cond' value.
 816         // We have to take the 'vectorized' value and pick the first lane.
 817         // Instcombine will make this a no-op.
 818         Cond = getVectorValue(Cond);
 819         if (InvariantCond)
 820           Cond = Builder.CreateExtractElement(Cond, Builder.getInt32(0));
 821
 822         Value *Op0 = getVectorValue(Inst->getOperand(1));
 823         Value *Op1 = getVectorValue(Inst->getOperand(2));
 824         WidenMap[Inst] = Builder.CreateSelect(Cond, Op0, Op1);
 825         break;
 826       }
 827
 828       case Instruction::ICmp:
 829       case Instruction::FCmp: {
 830         // Widen compares. Generate vector compares.
 831         bool FCmp = (Inst->getOpcode() == Instruction::FCmp);
 832         CmpInst *Cmp = dyn_cast<CmpInst>(Inst);
 833         Value *A = getVectorValue(Inst->getOperand(0));
 834         Value *B = getVectorValue(Inst->getOperand(1));
 835         if (FCmp)
 836           WidenMap[Inst] = Builder.CreateFCmp(Cmp->getPredicate(), A, B);
 837         else
 838           WidenMap[Inst] = Builder.CreateICmp(Cmp->getPredicate(), A, B);
 839         break;
 840       }
 841
 842       case Instruction::Store: {
 843         // Attempt to issue a wide store.
 844         StoreInst *SI = dyn_cast<StoreInst>(Inst);
 845         Type *StTy = VectorType::get(SI->getValueOperand()->getType(), VF);
 846         Value *Ptr = SI->getPointerOperand();
 847         unsigned Alignment = SI->getAlignment();
 848         GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr);
 849         // This store does not use GEPs.
 850         if (!Legal->isConsecutiveGep(Gep)) {
 851           scalarizeInstruction(Inst);
 852           break;
 853         }
 854
 855         // The last index does not have to be the induction. It can be
 856         // consecutive and be a function of the index. For example A[I+1];
 857         unsigned NumOperands = Gep->getNumOperands();
 858         Value *LastIndex = getVectorValue(Gep->getOperand(NumOperands -1));
 859         LastIndex = Builder.CreateExtractElement(LastIndex, Builder.getInt32(0));
 860
 861         // Create the new GEP with the new induction variable.
 862         GetElementPtrInst *Gep2 = cast<GetElementPtrInst>(Gep->clone());
 863         Gep2->setOperand(NumOperands - 1, LastIndex);
 864         Ptr = Builder.Insert(Gep2);
 865         Ptr = Builder.CreateBitCast(Ptr, StTy->getPointerTo());
 866         Value *Val = getVectorValue(SI->getValueOperand());
 867         Builder.CreateStore(Val, Ptr)->setAlignment(Alignment);
 868         break;
 869       }
 870       case Instruction::Load: {
 871         // Attempt to issue a wide load.
 872         LoadInst *LI = dyn_cast<LoadInst>(Inst);
 873         Type *RetTy = VectorType::get(LI->getType(), VF);
 874         Value *Ptr = LI->getPointerOperand();
 875         unsigned Alignment = LI->getAlignment();
 876         GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr);
 877
 878         // We don't have a gep. Scalarize the load.
 879         if (!Legal->isConsecutiveGep(Gep)) {
 880           scalarizeInstruction(Inst);
 881           break;
 882         }
 883
 884         // The last index does not have to be the induction. It can be
 885         // consecutive and be a function of the index. For example A[I+1];
 886         unsigned NumOperands = Gep->getNumOperands();
 887         Value *LastIndex = getVectorValue(Gep->getOperand(NumOperands -1));
 888         LastIndex = Builder.CreateExtractElement(LastIndex, Builder.getInt32(0));
 889
 890         // Create the new GEP with the new induction variable.
 891         GetElementPtrInst *Gep2 = cast<GetElementPtrInst>(Gep->clone());
 892         Gep2->setOperand(NumOperands - 1, LastIndex);
 893         Ptr = Builder.Insert(Gep2);
 894         Ptr = Builder.CreateBitCast(Ptr, RetTy->getPointerTo());
 895         LI = Builder.CreateLoad(Ptr);
 896         LI->setAlignment(Alignment);
 897         // Use this vector value for all users of the load.
 898         WidenMap[Inst] = LI;
 899         break;
 900       }
 901       case Instruction::ZExt:
 902       case Instruction::SExt:
 903       case Instruction::FPToUI:
 904       case Instruction::FPToSI:
 905       case Instruction::FPExt:
 906       case Instruction::PtrToInt:
 907       case Instruction::IntToPtr:
 908       case Instruction::SIToFP:
 909       case Instruction::UIToFP:
 910       case Instruction::Trunc:
 911       case Instruction::FPTrunc:
 912       case Instruction::BitCast: {
 913         /// Vectorize bitcasts.
 914         CastInst *CI = dyn_cast<CastInst>(Inst);
 915         Value *A = getVectorValue(Inst->getOperand(0));
 916         Type *DestTy = VectorType::get(CI->getType()->getScalarType(), VF);
 917         WidenMap[Inst] = Builder.CreateCast(CI->getOpcode(), A, DestTy);
 918         break;
 919       }
 920
 921       default:
 922         /// All other instructions are unsupported. Scalarize them.
 923         scalarizeInstruction(Inst);
 924         break;
 925     }// end of switch.
 926   }// end of for_each instr.
 927
 928   // At this point every instruction in the original loop is widended to
 929   // a vector form. We are almost done. Now, we need to fix the PHI nodes
 930   // that we vectorized. The PHI nodes are currently empty because we did
 931   // not want to introduce cycles. Notice that the remaining PHI nodes
 932   // that we need to fix are reduction variables.
 933
 934   // Create the 'reduced' values for each of the induction vars.
 935   // The reduced values are the vector values that we scalarize and combine
 936   // after the loop is finished.
 937   for (PhiVector::iterator it = PHIsToFix.begin(), e = PHIsToFix.end();
 938        it != e; ++it) {
 939     PHINode *RdxPhi = *it;
 940     PHINode *VecRdxPhi = dyn_cast<PHINode>(WidenMap[RdxPhi]);
 941     assert(RdxPhi && "Unable to recover vectorized PHI");
 942
 943     // Find the reduction variable descriptor.
 944     assert(Legal->getReductionVars()->count(RdxPhi) &&
 945            "Unable to find the reduction variable");
 946     LoopVectorizationLegality::ReductionDescriptor RdxDesc =
 947       (*Legal->getReductionVars())[RdxPhi];
 948
 949     // We need to generate a reduction vector from the incoming scalar.
 950     // To do so, we need to generate the 'identity' vector and overide
 951     // one of the elements with the incoming scalar reduction. We need
 952     // to do it in the vector-loop preheader.
 953     Builder.SetInsertPoint(LoopBypassBlock->getTerminator());
 954
 955     // This is the vector-clone of the value that leaves the loop.
 956     Value *VectorExit = getVectorValue(RdxDesc.LoopExitInstr);
 957     Type *VecTy = VectorExit->getType();
 958
 959     // Find the reduction identity variable. The value of the enum is the
 960     // identity. Zero for addition. One for Multiplication.
 961     unsigned IdentitySclr =  RdxDesc.Kind;
 962     Constant *Identity = getUniformVector(IdentitySclr,
 963                                           VecTy->getScalarType());
 964
 965     // This vector is the Identity vector where the first element is the
 966     // incoming scalar reduction.
 967     Value *VectorStart = Builder.CreateInsertElement(Identity,
 968                                                     RdxDesc.StartValue, Zero);
 969
 970
 971     // Fix the vector-loop phi.
 972     // We created the induction variable so we know that the
 973     // preheader is the first entry.
 974     BasicBlock *VecPreheader = Induction->getIncomingBlock(0);
 975
 976     // Reductions do not have to start at zero. They can start with
 977     // any loop invariant values.
 978     VecRdxPhi->addIncoming(VectorStart, VecPreheader);
 979     unsigned SelfEdgeIdx = (RdxPhi)->getBasicBlockIndex(LoopScalarBody);
 980     Value *Val = getVectorValue(RdxPhi->getIncomingValue(SelfEdgeIdx));
 981     VecRdxPhi->addIncoming(Val, LoopVectorBody);
 982
 983     // Before each round, move the insertion point right between
 984     // the PHIs and the values we are going to write.
 985     // This allows us to write both PHINodes and the extractelement
 986     // instructions.
 987     Builder.SetInsertPoint(LoopMiddleBlock->getFirstInsertionPt());
 988
 989     // This PHINode contains the vectorized reduction variable, or
 990     // the initial value vector, if we bypass the vector loop.
 991     PHINode *NewPhi = Builder.CreatePHI(VecTy, 2, "rdx.vec.exit.phi");
 992     NewPhi->addIncoming(VectorStart, LoopBypassBlock);
 993     NewPhi->addIncoming(getVectorValue(RdxDesc.LoopExitInstr), LoopVectorBody);
 994
 995     // Extract the first scalar.
 996     Value *Scalar0 =
 997       Builder.CreateExtractElement(NewPhi, Builder.getInt32(0));
 998     // Extract and reduce the remaining vector elements.
 999     for (unsigned i=1; i < VF; ++i) {
1000       Value *Scalar1 =
1001         Builder.CreateExtractElement(NewPhi, Builder.getInt32(i));
1002       switch (RdxDesc.Kind) {
1003         case LoopVectorizationLegality::IntegerAdd:
1004           Scalar0 = Builder.CreateAdd(Scalar0, Scalar1);
1005           break;
1006         case LoopVectorizationLegality::IntegerMult:
1007           Scalar0 = Builder.CreateMul(Scalar0, Scalar1);
1008           break;
1009         case LoopVectorizationLegality::IntegerOr:
1010           Scalar0 = Builder.CreateOr(Scalar0, Scalar1);
1011           break;
1012         case LoopVectorizationLegality::IntegerAnd:
1013           Scalar0 = Builder.CreateAnd(Scalar0, Scalar1);
1014           break;
1015         case LoopVectorizationLegality::IntegerXor:
1016           Scalar0 = Builder.CreateXor(Scalar0, Scalar1);
1017           break;
1018         default:
1019           llvm_unreachable("Unknown reduction operation");
1020       }
1021     }
1022
1023     // Now, we need to fix the users of the reduction variable
1024     // inside and outside of the scalar remainder loop.
1025     // We know that the loop is in LCSSA form. We need to update the
1026     // PHI nodes in the exit blocks.
1027     for (BasicBlock::iterator LEI = LoopExitBlock->begin(),
1028          LEE = LoopExitBlock->end(); LEI != LEE; ++LEI) {
1029       PHINode *LCSSAPhi = dyn_cast<PHINode>(LEI);
1030       if (!LCSSAPhi) continue;
1031
1032       // All PHINodes need to have a single entry edge, or two if
1033       // we already fixed them.
1034       assert(LCSSAPhi->getNumIncomingValues() < 3 && "Invalid LCSSA PHI");
1035
1036       // We found our reduction value exit-PHI. Update it with the
1037       // incoming bypass edge.
1038       if (LCSSAPhi->getIncomingValue(0) == RdxDesc.LoopExitInstr) {
1039         // Add an edge coming from the bypass.
1040         LCSSAPhi->addIncoming(Scalar0, LoopMiddleBlock);
1041         break;
1042       }
1043     }// end of the LCSSA phi scan.
1044
1045     // Fix the scalar loop reduction variable with the incoming reduction sum
1046     // from the vector body and from the backedge value.
1047     int IncomingEdgeBlockIdx = (RdxPhi)->getBasicBlockIndex(LoopScalarBody);
1048     int SelfEdgeBlockIdx = (IncomingEdgeBlockIdx ? 0 : 1); // The other block.
1049     (RdxPhi)->setIncomingValue(SelfEdgeBlockIdx, Scalar0);
1050     (RdxPhi)->setIncomingValue(IncomingEdgeBlockIdx, RdxDesc.LoopExitInstr);
1051   }// end of for each redux variable.
1052 }
1053
1054 void SingleBlockLoopVectorizer::cleanup() {
1055   // The original basic block.
1056   SE->forgetLoop(OrigLoop);
1057 }
1058
1059 bool LoopVectorizationLegality::canVectorize() {
1060   if (!TheLoop->getLoopPreheader()) {
1061     assert(false && "No preheader!!");
1062     DEBUG(dbgs() << "LV: Loop not normalized." << "\n");
1063     return  false;
1064   }
1065
1066   // We can only vectorize single basic block loops.
1067   unsigned NumBlocks = TheLoop->getNumBlocks();
1068   if (NumBlocks != 1) {
1069     DEBUG(dbgs() << "LV: Too many blocks:" << NumBlocks << "\n");
1070     return false;
1071   }
1072
1073   // We need to have a loop header.
1074   BasicBlock *BB = TheLoop->getHeader();
1075   DEBUG(dbgs() << "LV: Found a loop: " << BB->getName() << "\n");
1076
1077   // Go over each instruction and look at memory deps.
1078   if (!canVectorizeBlock(*BB)) {
1079     DEBUG(dbgs() << "LV: Can't vectorize this loop header\n");
1080     return false;
1081   }
1082
1083   // ScalarEvolution needs to be able to find the exit count.
1084   const SCEV *ExitCount = SE->getExitCount(TheLoop, BB);
1085   if (ExitCount == SE->getCouldNotCompute()) {
1086     DEBUG(dbgs() << "LV: SCEV could not compute the loop exit count.\n");
1087     return false;
1088   }
1089
1090   DEBUG(dbgs() << "LV: We can vectorize this loop!\n");
1091
1092   // Okay! We can vectorize. At this point we don't have any other mem analysis
1093   // which may limit our maximum vectorization factor, so just return true with
1094   // no restrictions.
1095   return true;
1096 }
1097
1098 bool LoopVectorizationLegality::canVectorizeBlock(BasicBlock &BB) {
1099   // Scan the instructions in the block and look for hazards.
1100   for (BasicBlock::iterator it = BB.begin(), e = BB.end(); it != e; ++it) {
1101     Instruction *I = it;
1102
1103     PHINode *Phi = dyn_cast<PHINode>(I);
1104     if (Phi) {
1105       // This should not happen because the loop should be normalized.
1106       if (Phi->getNumIncomingValues() != 2) {
1107         DEBUG(dbgs() << "LV: Found an invalid PHI.\n");
1108         return false;
1109       }
1110       // We only look at integer phi nodes.
1111       if (!Phi->getType()->isIntegerTy()) {
1112         DEBUG(dbgs() << "LV: Found an non-int PHI.\n");
1113         return false;
1114       }
1115
1116       if (isInductionVariable(Phi)) {
1117         if (Induction) {
1118           DEBUG(dbgs() << "LV: Found too many inductions."<< *Phi <<"\n");
1119           return false;
1120         }
1121         DEBUG(dbgs() << "LV: Found the induction PHI."<< *Phi <<"\n");
1122         Induction = Phi;
1123         continue;
1124       }
1125       if (AddReductionVar(Phi, IntegerAdd)) {
1126         DEBUG(dbgs() << "LV: Found an ADD reduction PHI."<< *Phi <<"\n");
1127         continue;
1128       }
1129       if (AddReductionVar(Phi, IntegerMult)) {
1130         DEBUG(dbgs() << "LV: Found a MUL reduction PHI."<< *Phi <<"\n");
1131         continue;
1132       }
1133       if (AddReductionVar(Phi, IntegerOr)) {
1134         DEBUG(dbgs() << "LV: Found an OR reduction PHI."<< *Phi <<"\n");
1135         continue;
1136       }
1137       if (AddReductionVar(Phi, IntegerAnd)) {
1138         DEBUG(dbgs() << "LV: Found an AND reduction PHI."<< *Phi <<"\n");
1139         continue;
1140       }
1141       if (AddReductionVar(Phi, IntegerXor)) {
1142         DEBUG(dbgs() << "LV: Found a XOR reduction PHI."<< *Phi <<"\n");
1143         continue;
1144       }
1145
1146       DEBUG(dbgs() << "LV: Found an unidentified PHI."<< *Phi <<"\n");
1147       return false;
1148     }// end of PHI handling
1149
1150     // We still don't handle functions.
1151     CallInst *CI = dyn_cast<CallInst>(I);
1152     if (CI) {
1153       DEBUG(dbgs() << "LV: Found a call site:"<<
1154             CI->getCalledFunction()->getName() << "\n");
1155       return false;
1156     }
1157
1158     // We do not re-vectorize vectors.
1159     if (!VectorType::isValidElementType(I->getType()) &&
1160         !I->getType()->isVoidTy()) {
1161       DEBUG(dbgs() << "LV: Found unvectorizable type." << "\n");
1162       return false;
1163     }
1164
1165     // Reduction instructions are allowed to have exit users.
1166     // All other instructions must not have external users.
1167     if (!AllowedExit.count(I))
1168       //Check that all of the users of the loop are inside the BB.
1169       for (Value::use_iterator it = I->use_begin(), e = I->use_end();
1170            it != e; ++it) {
1171         Instruction *U = cast<Instruction>(*it);
1172         // This user may be a reduction exit value.
1173         BasicBlock *Parent = U->getParent();
1174         if (Parent != &BB) {
1175           DEBUG(dbgs() << "LV: Found an outside user for : "<< *U << "\n");
1176           return false;
1177         }
1178     }
1179   } // next instr.
1180
1181   if (!Induction) {
1182       DEBUG(dbgs() << "LV: Did not find an induction var.\n");
1183       return false;
1184   }
1185
1186   // Don't vectorize if the memory dependencies do not allow vectorization.
1187   if (!canVectorizeMemory(BB))
1188     return false;
1189
1190   // We now know that the loop is vectorizable!
1191   // Collect variables that will remain uniform after vectorization.
1192   std::vector<Value*> Worklist;
1193
1194   // Start with the conditional branch and walk up the block.
1195   Worklist.push_back(BB.getTerminator()->getOperand(0));
1196
1197   while (Worklist.size()) {
1198     Instruction *I = dyn_cast<Instruction>(Worklist.back());
1199     Worklist.pop_back();
1200     // Look at instructions inside this block.
1201     if (!I) continue;
1202     if (I->getParent() != &BB) continue;
1203
1204     // Stop when reaching PHI nodes.
1205     if (isa<PHINode>(I)) {
1206       assert(I == Induction && "Found a uniform PHI that is not the induction");
1207       break;
1208     }
1209
1210     // This is a known uniform.
1211     Uniforms.insert(I);
1212
1213     // Insert all operands.
1214     for (int i=0, Op = I->getNumOperands(); i < Op; ++i) {
1215       Worklist.push_back(I->getOperand(i));
1216     }
1217   }
1218
1219   return true;
1220 }
1221
1222 bool LoopVectorizationLegality::canVectorizeMemory(BasicBlock &BB) {
1223   typedef SmallVector<Value*, 16> ValueVector;
1224   typedef SmallPtrSet<Value*, 16> ValueSet;
1225   // Holds the Load and Store *instructions*.
1226   ValueVector Loads;
1227   ValueVector Stores;
1228
1229   // Scan the BB and collect legal loads and stores.
1230   for (BasicBlock::iterator it = BB.begin(), e = BB.end(); it != e; ++it) {
1231     Instruction *I = it;
1232
1233     // If this is a load, save it. If this instruction can read from memory
1234     // but is not a load, then we quit. Notice that we don't handle function
1235     // calls that read or write.
1236     if (I->mayReadFromMemory()) {
1237       LoadInst *Ld = dyn_cast<LoadInst>(I);
1238       if (!Ld) return false;
1239       if (!Ld->isSimple()) {
1240         DEBUG(dbgs() << "LV: Found a non-simple load.\n");
1241         return false;
1242       }
1243       Loads.push_back(Ld);
1244       continue;
1245     }
1246
1247     // Save store instructions. Abort if other instructions write to memory.
1248     if (I->mayWriteToMemory()) {
1249       StoreInst *St = dyn_cast<StoreInst>(I);
1250       if (!St) return false;
1251       if (!St->isSimple()) {
1252         DEBUG(dbgs() << "LV: Found a non-simple store.\n");
1253         return false;
1254       }
1255       Stores.push_back(St);
1256     }
1257   } // next instr.
1258
1259   // Now we have two lists that hold the loads and the stores.
1260   // Next, we find the pointers that they use.
1261
1262   // Check if we see any stores. If there are no stores, then we don't
1263   // care if the pointers are *restrict*.
1264   if (!Stores.size()) {
1265         DEBUG(dbgs() << "LV: Found a read-only loop!\n");
1266         return true;
1267   }
1268
1269   // Holds the read and read-write *pointers* that we find.
1270   ValueVector Reads;
1271   ValueVector ReadWrites;
1272
1273   // Holds the analyzed pointers. We don't want to call GetUnderlyingObjects
1274   // multiple times on the same object. If the ptr is accessed twice, once
1275   // for read and once for write, it will only appear once (on the write
1276   // list). This is okay, since we are going to check for conflicts between
1277   // writes and between reads and writes, but not between reads and reads.
1278   ValueSet Seen;
1279
1280   ValueVector::iterator I, IE;
1281   for (I = Stores.begin(), IE = Stores.end(); I != IE; ++I) {
1282     StoreInst *ST = dyn_cast<StoreInst>(*I);
1283     assert(ST && "Bad StoreInst");
1284     Value* Ptr = ST->getPointerOperand();
1285     // If we did *not* see this pointer before, insert it to
1286     // the read-write list. At this phase it is only a 'write' list.
1287     if (Seen.insert(Ptr))
1288       ReadWrites.push_back(Ptr);
1289   }
1290
1291   for (I = Loads.begin(), IE = Loads.end(); I != IE; ++I) {
1292     LoadInst *LD = dyn_cast<LoadInst>(*I);
1293     assert(LD && "Bad LoadInst");
1294     Value* Ptr = LD->getPointerOperand();
1295     // If we did *not* see this pointer before, insert it to the
1296     // read list. If we *did* see it before, then it is already in
1297     // the read-write list. This allows us to vectorize expressions
1298     // such as A[i] += x;  Because the address of A[i] is a read-write
1299     // pointer. This only works if the index of A[i] is consecutive.
1300     // If the address of i is unknown (for example A[B[i]]) then we may
1301     // read a few words, modify, and write a few words, and some of the
1302     // words may be written to the same address.
1303     if (Seen.insert(Ptr) || !isConsecutiveGep(Ptr))
1304       Reads.push_back(Ptr);
1305   }
1306
1307   // Now that the pointers are in two lists (Reads and ReadWrites), we
1308   // can check that there are no conflicts between each of the writes and
1309   // between the writes to the reads.
1310   ValueSet WriteObjects;
1311   ValueVector TempObjects;
1312
1313   // Check that the read-writes do not conflict with other read-write
1314   // pointers.
1315   for (I = ReadWrites.begin(), IE = ReadWrites.end(); I != IE; ++I) {
1316     GetUnderlyingObjects(*I, TempObjects, DL);
1317     for (ValueVector::iterator it=TempObjects.begin(), e=TempObjects.end();
1318          it != e; ++it) {
1319       if (!isIdentifiedObject(*it)) {
1320         DEBUG(dbgs() << "LV: Found an unidentified write ptr:"<< **it <<"\n");
1321         return false;
1322       }
1323       if (!WriteObjects.insert(*it)) {
1324         DEBUG(dbgs() << "LV: Found a possible write-write reorder:"
1325               << **it <<"\n");
1326         return false;
1327       }
1328     }
1329     TempObjects.clear();
1330   }
1331
1332   /// Check that the reads don't conflict with the read-writes.
1333   for (I = Reads.begin(), IE = Reads.end(); I != IE; ++I) {
1334     GetUnderlyingObjects(*I, TempObjects, DL);
1335     for (ValueVector::iterator it=TempObjects.begin(), e=TempObjects.end();
1336          it != e; ++it) {
1337       if (!isIdentifiedObject(*it)) {
1338         DEBUG(dbgs() << "LV: Found an unidentified read ptr:"<< **it <<"\n");
1339         return false;
1340       }
1341       if (WriteObjects.count(*it)) {
1342         DEBUG(dbgs() << "LV: Found a possible read/write reorder:"
1343               << **it <<"\n");
1344         return false;
1345       }
1346     }
1347     TempObjects.clear();
1348   }
1349
1350   // All is okay.
1351   return true;
1352 }
1353
1354 bool LoopVectorizationLegality::AddReductionVar(PHINode *Phi,
1355                                                 ReductionKind Kind) {
1356   if (Phi->getNumIncomingValues() != 2)
1357     return false;
1358
1359   // Find the possible incoming reduction variable.
1360   BasicBlock *BB = Phi->getParent();
1361   int SelfEdgeIdx = Phi->getBasicBlockIndex(BB);
1362   int InEdgeBlockIdx = (SelfEdgeIdx ? 0 : 1); // The other entry.
1363   Value *RdxStart = Phi->getIncomingValue(InEdgeBlockIdx);
1364
1365   // ExitInstruction is the single value which is used outside the loop.
1366   // We only allow for a single reduction value to be used outside the loop.
1367   // This includes users of the reduction, variables (which form a cycle
1368   // which ends in the phi node).
1369   Instruction *ExitInstruction = 0;
1370
1371   // Iter is our iterator. We start with the PHI node and scan for all of the
1372   // users of this instruction. All users must be instructions which can be
1373   // used as reduction variables (such as ADD). We may have a single
1374   // out-of-block user. They cycle must end with the original PHI.
1375   // Also, we can't have multiple block-local users.
1376   Instruction *Iter = Phi;
1377   while (true) {
1378     // Any reduction instr must be of one of the allowed kinds.
1379     if (!isReductionInstr(Iter, Kind))
1380       return false;
1381
1382     // Did we found a user inside this block ?
1383     bool FoundInBlockUser = false;
1384     // Did we reach the initial PHI node ?
1385     bool FoundStartPHI = false;
1386
1387     // If the instruction has no users then this is a broken
1388     // chain and can't be a reduction variable.
1389     if (Iter->use_empty())
1390       return false;
1391
1392     // For each of the *users* of iter.
1393     for (Value::use_iterator it = Iter->use_begin(), e = Iter->use_end();
1394          it != e; ++it) {
1395       Instruction *U = cast<Instruction>(*it);
1396       // We already know that the PHI is a user.
1397       if (U == Phi) {
1398         FoundStartPHI = true;
1399         continue;
1400       }
1401       // Check if we found the exit user.
1402       BasicBlock *Parent = U->getParent();
1403       if (Parent != BB) {
1404         // We must have a single exit instruction.
1405         if (ExitInstruction != 0)
1406           return false;
1407         ExitInstruction = Iter;
1408       }
1409       // We can't have multiple inside users.
1410       if (FoundInBlockUser)
1411         return false;
1412       FoundInBlockUser = true;
1413       Iter = U;
1414     }
1415
1416     // We found a reduction var if we have reached the original
1417     // phi node and we only have a single instruction with out-of-loop
1418     // users.
1419    if (FoundStartPHI && ExitInstruction) {
1420      // This instruction is allowed to have out-of-loop users.
1421      AllowedExit.insert(ExitInstruction);
1422
1423      // Save the description of this reduction variable.
1424      ReductionDescriptor RD(RdxStart, ExitInstruction, Kind);
1425      Reductions[Phi] = RD;
1426      return true;
1427    }
1428   }
1429 }
1430
1431 bool
1432 LoopVectorizationLegality::isReductionInstr(Instruction *I,
1433                                             ReductionKind Kind) {
1434     switch (I->getOpcode()) {
1435     default:
1436       return false;
1437     case Instruction::PHI:
1438       // possibly.
1439       return true;
1440     case Instruction::Add:
1441     case Instruction::Sub:
1442       return Kind == IntegerAdd;
1443     case Instruction::Mul:
1444     case Instruction::UDiv:
1445     case Instruction::SDiv:
1446       return Kind == IntegerMult;
1447     case Instruction::And:
1448       return Kind == IntegerAnd;
1449     case Instruction::Or:
1450       return Kind == IntegerOr;
1451     case Instruction::Xor:
1452       return Kind == IntegerXor;
1453     }
1454 }
1455
1456 bool LoopVectorizationLegality::isInductionVariable(PHINode *Phi) {
1457   // Check that the PHI is consecutive and starts at zero.
1458   const SCEV *PhiScev = SE->getSCEV(Phi);
1459   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1460   if (!AR) {
1461     DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1462     return false;
1463   }
1464   const SCEV *Step = AR->getStepRecurrence(*SE);
1465   const SCEV *Start = AR->getStart();
1466
1467   if (!Step->isOne() || !Start->isZero()) {
1468     DEBUG(dbgs() << "LV: PHI does not start at zero or steps by one.\n");
1469     return false;
1470   }
1471   return true;
1472 }
1473
1474 unsigned
1475 LoopVectorizationCostModel::findBestVectorizationFactor(unsigned VF) {
1476   if (!VTTI) {
1477     DEBUG(dbgs() << "LV: No vector target information. Not vectorizing. \n");
1478     return 1;
1479   }
1480
1481   float Cost = expectedCost(1);
1482   unsigned Width = 1;
1483   DEBUG(dbgs() << "LV: Scalar loop costs: "<< (int)Cost << ".\n");
1484   for (unsigned i=2; i <= VF; i*=2) {
1485     // Notice that the vector loop needs to be executed less times, so
1486     // we need to divide the cost of the vector loops by the width of
1487     // the vector elements.
1488     float VectorCost = expectedCost(i) / (float)i;
1489     DEBUG(dbgs() << "LV: Vector loop of width "<< i << " costs: " <<
1490           (int)VectorCost << ".\n");
1491     if (VectorCost < Cost) {
1492       Cost = VectorCost;
1493       Width = i;
1494     }
1495   }
1496
1497   DEBUG(dbgs() << "LV: Selecting VF = : "<< Width << ".\n");
1498   return Width;
1499 }
1500
1501 unsigned LoopVectorizationCostModel::expectedCost(unsigned VF) {
1502   // We can only estimate the cost of single basic block loops.
1503   assert(1 == TheLoop->getNumBlocks() && "Too many blocks in loop");
1504
1505   BasicBlock *BB = TheLoop->getHeader();
1506   unsigned Cost = 0;
1507
1508   // For each instruction in the old loop.
1509   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
1510     Instruction *Inst = it;
1511     unsigned C = getInstructionCost(Inst, VF);
1512     Cost += C;
1513     DEBUG(dbgs() << "LV: Found an estimated cost of "<< C <<" for VF "<< VF <<
1514           " For instruction: "<< *Inst << "\n");
1515   }
1516
1517   return Cost;
1518 }
1519
1520 unsigned
1521 LoopVectorizationCostModel::getInstructionCost(Instruction *I, unsigned VF) {
1522   assert(VTTI && "Invalid vector target transformation info");
1523
1524   // If we know that this instruction will remain uniform, check the cost of
1525   // the scalar version.
1526   if (Legal->isUniformAfterVectorization(I))
1527     VF = 1;
1528
1529   Type *RetTy = I->getType();
1530   Type *VectorTy = ToVectorTy(RetTy, VF);
1531
1532
1533   // TODO: We need to estimate the cost of intrinsic calls.
1534   switch (I->getOpcode()) {
1535     case Instruction::GetElementPtr:
1536       // We mark this instruction as zero-cost because scalar GEPs are usually
1537       // lowered to the intruction addressing mode. At the moment we don't
1538       // generate vector geps.
1539       return 0;
1540     case Instruction::Br: {
1541       return VTTI->getCFInstrCost(I->getOpcode());
1542     }
1543     case Instruction::PHI:
1544       return 0;
1545     case Instruction::Add:
1546     case Instruction::FAdd:
1547     case Instruction::Sub:
1548     case Instruction::FSub:
1549     case Instruction::Mul:
1550     case Instruction::FMul:
1551     case Instruction::UDiv:
1552     case Instruction::SDiv:
1553     case Instruction::FDiv:
1554     case Instruction::URem:
1555     case Instruction::SRem:
1556     case Instruction::FRem:
1557     case Instruction::Shl:
1558     case Instruction::LShr:
1559     case Instruction::AShr:
1560     case Instruction::And:
1561     case Instruction::Or:
1562     case Instruction::Xor: {
1563       return VTTI->getArithmeticInstrCost(I->getOpcode(), VectorTy);
1564     }
1565     case Instruction::Select: {
1566       SelectInst *SI = cast<SelectInst>(I);
1567       const SCEV *CondSCEV = SE->getSCEV(SI->getCondition());
1568       bool ScalarCond = (SE->isLoopInvariant(CondSCEV, TheLoop));
1569       Type *CondTy = SI->getCondition()->getType();
1570       if (ScalarCond)
1571         CondTy = VectorType::get(CondTy, VF);
1572
1573       return VTTI->getCmpSelInstrCost(I->getOpcode(), VectorTy, CondTy);
1574     }
1575     case Instruction::ICmp:
1576     case Instruction::FCmp: {
1577       Type *ValTy = I->getOperand(0)->getType();
1578       VectorTy = ToVectorTy(ValTy, VF);
1579       return VTTI->getCmpSelInstrCost(I->getOpcode(), VectorTy);
1580     }
1581     case Instruction::Store: {
1582       StoreInst *SI = cast<StoreInst>(I);
1583       Type *ValTy = SI->getValueOperand()->getType();
1584       VectorTy = ToVectorTy(ValTy, VF);
1585
1586       if (VF == 1)
1587         return VTTI->getMemoryOpCost(I->getOpcode(), ValTy,
1588                               SI->getAlignment(), SI->getPointerAddressSpace());
1589
1590       // Scalarized stores.
1591       if (!Legal->isConsecutiveGep(SI->getPointerOperand())) {
1592         unsigned Cost = 0;
1593         unsigned ExtCost = VTTI->getInstrCost(Instruction::ExtractElement,
1594                                               ValTy);
1595         // The cost of extracting from the value vector.
1596         Cost += VF * (ExtCost);
1597         // The cost of the scalar stores.
1598         Cost += VF * VTTI->getMemoryOpCost(I->getOpcode(),
1599                                            ValTy->getScalarType(),
1600                                            SI->getAlignment(),
1601                                            SI->getPointerAddressSpace());
1602         return Cost;
1603       }
1604
1605       // Wide stores.
1606       return VTTI->getMemoryOpCost(I->getOpcode(), VectorTy, SI->getAlignment(),
1607                                    SI->getPointerAddressSpace());
1608     }
1609     case Instruction::Load: {
1610       LoadInst *LI = cast<LoadInst>(I);
1611
1612       if (VF == 1)
1613         return VTTI->getMemoryOpCost(I->getOpcode(), RetTy,
1614                                      LI->getAlignment(),
1615                                      LI->getPointerAddressSpace());
1616
1617       // Scalarized loads.
1618       if (!Legal->isConsecutiveGep(LI->getPointerOperand())) {
1619         unsigned Cost = 0;
1620         unsigned InCost = VTTI->getInstrCost(Instruction::InsertElement, RetTy);
1621         // The cost of inserting the loaded value into the result vector.
1622         Cost += VF * (InCost);
1623         // The cost of the scalar stores.
1624         Cost += VF * VTTI->getMemoryOpCost(I->getOpcode(),
1625                                            RetTy->getScalarType(),
1626                                            LI->getAlignment(),
1627                                            LI->getPointerAddressSpace());
1628         return Cost;
1629       }
1630
1631       // Wide loads.
1632       return VTTI->getMemoryOpCost(I->getOpcode(), VectorTy, LI->getAlignment(),
1633                                    LI->getPointerAddressSpace());
1634     }
1635     case Instruction::ZExt:
1636     case Instruction::SExt:
1637     case Instruction::FPToUI:
1638     case Instruction::FPToSI:
1639     case Instruction::FPExt:
1640     case Instruction::PtrToInt:
1641     case Instruction::IntToPtr:
1642     case Instruction::SIToFP:
1643     case Instruction::UIToFP:
1644     case Instruction::Trunc:
1645     case Instruction::FPTrunc:
1646     case Instruction::BitCast: {
1647       Type *SrcVecTy = ToVectorTy(I->getOperand(0)->getType(), VF);
1648       return VTTI->getCastInstrCost(I->getOpcode(), VectorTy, SrcVecTy);
1649     }
1650     default: {
1651       // We are scalarizing the instruction. Return the cost of the scalar
1652       // instruction, plus the cost of insert and extract into vector
1653       // elements, times the vector width.
1654       unsigned Cost = 0;
1655
1656       bool IsVoid = RetTy->isVoidTy();
1657
1658       unsigned InsCost = (IsVoid ? 0 :
1659                           VTTI->getInstrCost(Instruction::InsertElement,
1660                                              VectorTy));
1661
1662       unsigned ExtCost = VTTI->getInstrCost(Instruction::ExtractElement,
1663                                             VectorTy);
1664
1665       // The cost of inserting the results plus extracting each one of the
1666       // operands.
1667       Cost += VF * (InsCost + ExtCost * I->getNumOperands());
1668
1669       // The cost of executing VF copies of the scalar instruction.
1670       Cost += VF * VTTI->getInstrCost(I->getOpcode(), RetTy);
1671       return Cost;
1672     }
1673   }// end of switch.
1674 }
1675
1676 Type* LoopVectorizationCostModel::ToVectorTy(Type *Scalar, unsigned VF) {
1677   if (Scalar->isVoidTy() || VF == 1)
1678     return Scalar;
1679   return VectorType::get(Scalar, VF);
1680 }
1681
1682 } // namespace
1683
1684 char LoopVectorize::ID = 0;
1685 static const char lv_name[] = "Loop Vectorization";
1686 INITIALIZE_PASS_BEGIN(LoopVectorize, LV_NAME, lv_name, false, false)
1687 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
1688 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
1689 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
1690 INITIALIZE_PASS_END(LoopVectorize, LV_NAME, lv_name, false, false)
1691
1692 namespace llvm {
1693   Pass *createLoopVectorizePass() {
1694     return new LoopVectorize();
1695   }
1696 }
1697