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