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