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