lib/Transforms/Vectorize/VecUtils.cpp

   1 //===- VecUtils.cpp --- Vectorization Utilities ---------------------------===//
   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 #define DEBUG_TYPE "SLP"
  10
  11 #include "VecUtils.h"
  12 #include "llvm/ADT/DenseMap.h"
  13 #include "llvm/ADT/SmallPtrSet.h"
  14 #include "llvm/ADT/SmallSet.h"
  15 #include "llvm/ADT/SmallVector.h"
  16 #include "llvm/Analysis/AliasAnalysis.h"
  17 #include "llvm/Analysis/ScalarEvolution.h"
  18 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  19 #include "llvm/Analysis/TargetTransformInfo.h"
  20 #include "llvm/Analysis/Verifier.h"
  21 #include "llvm/Analysis/LoopInfo.h"
  22 #include "llvm/IR/Constants.h"
  23 #include "llvm/IR/DataLayout.h"
  24 #include "llvm/IR/Function.h"
  25 #include "llvm/IR/Instructions.h"
  26 #include "llvm/IR/Module.h"
  27 #include "llvm/IR/Type.h"
  28 #include "llvm/IR/Value.h"
  29 #include "llvm/Pass.h"
  30 #include "llvm/Support/CommandLine.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/raw_ostream.h"
  33 #include "llvm/Target/TargetLibraryInfo.h"
  34 #include "llvm/Transforms/Scalar.h"
  35 #include "llvm/Transforms/Utils/Local.h"
  36 #include <algorithm>
  37 #include <map>
  38
  39 using namespace llvm;
  40
  41 static const unsigned MinVecRegSize = 128;
  42
  43 static const unsigned RecursionMaxDepth = 6;
  44
  45 namespace llvm {
  46
  47 BoUpSLP::BoUpSLP(BasicBlock *Bb, ScalarEvolution *S, DataLayout *Dl,
  48                  TargetTransformInfo *Tti, AliasAnalysis *Aa, Loop *Lp) :
  49   BB(Bb), SE(S), DL(Dl), TTI(Tti), AA(Aa), L(Lp)  {
  50   numberInstructions();
  51 }
  52
  53 void BoUpSLP::numberInstructions() {
  54   int Loc = 0;
  55   InstrIdx.clear();
  56   InstrVec.clear();
  57   // Number the instructions in the block.
  58   for (BasicBlock::iterator it=BB->begin(), e=BB->end(); it != e; ++it) {
  59     InstrIdx[it] = Loc++;
  60     InstrVec.push_back(it);
  61     assert(InstrVec[InstrIdx[it]] == it && "Invalid allocation");
  62   }
  63 }
  64
  65 Value *BoUpSLP::getPointerOperand(Value *I) {
  66   if (LoadInst *LI = dyn_cast<LoadInst>(I)) return LI->getPointerOperand();
  67   if (StoreInst *SI = dyn_cast<StoreInst>(I)) return SI->getPointerOperand();
  68   return 0;
  69 }
  70
  71 unsigned BoUpSLP::getAddressSpaceOperand(Value *I) {
  72   if (LoadInst *L=dyn_cast<LoadInst>(I)) return L->getPointerAddressSpace();
  73   if (StoreInst *S=dyn_cast<StoreInst>(I)) return S->getPointerAddressSpace();
  74   return -1;
  75 }
  76
  77 bool BoUpSLP::isConsecutiveAccess(Value *A, Value *B) {
  78   Value *PtrA = getPointerOperand(A);
  79   Value *PtrB = getPointerOperand(B);
  80   unsigned ASA = getAddressSpaceOperand(A);
  81   unsigned ASB = getAddressSpaceOperand(B);
  82
  83   // Check that the address spaces match and that the pointers are valid.
  84   if (!PtrA || !PtrB || (ASA != ASB)) return false;
  85
  86   // Check that A and B are of the same type.
  87   if (PtrA->getType() != PtrB->getType()) return false;
  88
  89   // Calculate the distance.
  90   const SCEV *PtrSCEVA = SE->getSCEV(PtrA);
  91   const SCEV *PtrSCEVB = SE->getSCEV(PtrB);
  92   const SCEV *OffsetSCEV = SE->getMinusSCEV(PtrSCEVA, PtrSCEVB);
  93   const SCEVConstant *ConstOffSCEV = dyn_cast<SCEVConstant>(OffsetSCEV);
  94
  95   // Non constant distance.
  96   if (!ConstOffSCEV) return false;
  97
  98   int64_t Offset = ConstOffSCEV->getValue()->getSExtValue();
  99   Type *Ty = cast<PointerType>(PtrA->getType())->getElementType();
 100   // The Instructions are connsecutive if the size of the first load/store is
 101   // the same as the offset.
 102   int64_t Sz = DL->getTypeStoreSize(Ty);
 103   return ((-Offset) == Sz);
 104 }
 105
 106 bool BoUpSLP::vectorizeStoreChain(ArrayRef<Value *> Chain, int CostThreshold) {
 107   Type *StoreTy = cast<StoreInst>(Chain[0])->getValueOperand()->getType();
 108   unsigned Sz = DL->getTypeSizeInBits(StoreTy);
 109   unsigned VF = MinVecRegSize / Sz;
 110
 111   if (!isPowerOf2_32(Sz) || VF < 2) return false;
 112
 113   bool Changed = false;
 114   // Look for profitable vectorizable trees at all offsets, starting at zero.
 115   for (unsigned i = 0, e = Chain.size(); i < e; ++i) {
 116     if (i + VF > e) return Changed;
 117     DEBUG(dbgs()<<"SLP: Analyzing " << VF << " stores at offset "<< i << "\n");
 118     ArrayRef<Value *> Operands = Chain.slice(i, VF);
 119
 120     int Cost = getTreeCost(Operands);
 121     DEBUG(dbgs() << "SLP: Found cost=" << Cost << " for VF=" << VF << "\n");
 122     if (Cost < CostThreshold) {
 123       DEBUG(dbgs() << "SLP: Decided to vectorize cost=" << Cost << "\n");
 124       vectorizeTree(Operands, VF);
 125       i += VF - 1;
 126       Changed = true;
 127     }
 128   }
 129
 130   return Changed;
 131 }
 132
 133 bool BoUpSLP::vectorizeStores(ArrayRef<StoreInst *> Stores, int costThreshold) {
 134   ValueSet Heads, Tails;
 135   SmallDenseMap<Value*, Value*> ConsecutiveChain;
 136
 137   // We may run into multiple chains that merge into a single chain. We mark the
 138   // stores that we vectorized so that we don't visit the same store twice.
 139   ValueSet VectorizedStores;
 140   bool Changed = false;
 141
 142   // Do a quadratic search on all of the given stores and find
 143   // all of the pairs of loads that follow each other.
 144   for (unsigned i = 0, e = Stores.size(); i < e; ++i)
 145     for (unsigned j = 0; j < e; ++j) {
 146       if (i == j) continue;
 147       if (isConsecutiveAccess(Stores[i], Stores[j])) {
 148         Tails.insert(Stores[j]);
 149         Heads.insert(Stores[i]);
 150         ConsecutiveChain[Stores[i]] = Stores[j];
 151       }
 152     }
 153
 154   // For stores that start but don't end a link in the chain:
 155   for (ValueSet::iterator it = Heads.begin(), e = Heads.end();it != e; ++it) {
 156     if (Tails.count(*it)) continue;
 157
 158     // We found a store instr that starts a chain. Now follow the chain and try
 159     // to vectorize it.
 160     ValueList Operands;
 161     Value *I = *it;
 162     // Collect the chain into a list.
 163     while (Tails.count(I) || Heads.count(I)) {
 164       if (VectorizedStores.count(I)) break;
 165       Operands.push_back(I);
 166       // Move to the next value in the chain.
 167       I = ConsecutiveChain[I];
 168     }
 169
 170     bool Vectorized = vectorizeStoreChain(Operands, costThreshold);
 171
 172     // Mark the vectorized stores so that we don't vectorize them again.
 173     if (Vectorized)
 174       VectorizedStores.insert(Operands.begin(), Operands.end());
 175     Changed |= Vectorized;
 176   }
 177
 178   return Changed;
 179 }
 180
 181 int BoUpSLP::getScalarizationCost(ArrayRef<Value *> VL) {
 182   // Find the type of the operands in VL.
 183   Type *ScalarTy = VL[0]->getType();
 184   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
 185     ScalarTy = SI->getValueOperand()->getType();
 186   VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
 187   // Find the cost of inserting/extracting values from the vector.
 188   return getScalarizationCost(VecTy);
 189 }
 190
 191 int BoUpSLP::getScalarizationCost(Type *Ty) {
 192   int Cost = 0;
 193   for (unsigned i = 0, e = cast<VectorType>(Ty)->getNumElements(); i < e; ++i)
 194     Cost += TTI->getVectorInstrCost(Instruction::InsertElement, Ty, i);
 195   return Cost;
 196 }
 197
 198 AliasAnalysis::Location BoUpSLP::getLocation(Instruction *I) {
 199   if (StoreInst *SI = dyn_cast<StoreInst>(I)) return AA->getLocation(SI);
 200   if (LoadInst *LI = dyn_cast<LoadInst>(I)) return AA->getLocation(LI);
 201   return AliasAnalysis::Location();
 202 }
 203
 204 Value *BoUpSLP::isUnsafeToSink(Instruction *Src, Instruction *Dst) {
 205   assert(Src->getParent() == Dst->getParent() && "Not the same BB");
 206   BasicBlock::iterator I = Src, E = Dst;
 207   /// Scan all of the instruction from SRC to DST and check if
 208   /// the source may alias.
 209   for (++I; I != E; ++I) {
 210     // Ignore store instructions that are marked as 'ignore'.
 211     if (MemBarrierIgnoreList.count(I)) continue;
 212     if (Src->mayWriteToMemory()) /* Write */ {
 213       if (!I->mayReadOrWriteMemory()) continue;
 214     } else /* Read */ {
 215       if (!I->mayWriteToMemory()) continue;
 216     }
 217     AliasAnalysis::Location A = getLocation(&*I);
 218     AliasAnalysis::Location B = getLocation(Src);
 219
 220     if (!A.Ptr || !B.Ptr || AA->alias(A, B))
 221       return I;
 222   }
 223   return 0;
 224 }
 225
 226 void BoUpSLP::vectorizeArith(ArrayRef<Value *> Operands) {
 227   Value *Vec = vectorizeTree(Operands, Operands.size());
 228   BasicBlock::iterator Loc = cast<Instruction>(Vec);
 229   IRBuilder<> Builder(++Loc);
 230   // After vectorizing the operands we need to generate extractelement
 231   // instructions and replace all of the uses of the scalar values with
 232   // the values that we extracted from the vectorized tree.
 233   for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
 234     Value *S = Builder.CreateExtractElement(Vec, Builder.getInt32(i));
 235     Operands[i]->replaceAllUsesWith(S);
 236   }
 237 }
 238
 239 int BoUpSLP::getTreeCost(ArrayRef<Value *> VL) {
 240   // Get rid of the list of stores that were removed, and from the
 241   // lists of instructions with multiple users.
 242   MemBarrierIgnoreList.clear();
 243   LaneMap.clear();
 244   MultiUserVals.clear();
 245   MustScalarize.clear();
 246
 247   // Scan the tree and find which value is used by which lane, and which values
 248   // must be scalarized.
 249   getTreeUses_rec(VL, 0);
 250
 251   // Check that instructions with multiple users can be vectorized. Mark unsafe
 252   // instructions.
 253   for (ValueSet::iterator it = MultiUserVals.begin(),
 254        e = MultiUserVals.end(); it != e; ++it) {
 255     // Check that all of the users of this instr are within the tree
 256     // and that they are all from the same lane.
 257     int Lane = -1;
 258     for (Value::use_iterator I = (*it)->use_begin(), E = (*it)->use_end();
 259          I != E; ++I) {
 260       if (LaneMap.find(*I) == LaneMap.end()) {
 261         MustScalarize.insert(*it);
 262         DEBUG(dbgs()<<"SLP: Adding " << **it <<
 263               " to MustScalarize because of an out of tree usage.\n");
 264         break;
 265       }
 266       if (Lane == -1) Lane = LaneMap[*I];
 267       if (Lane != LaneMap[*I]) {
 268         MustScalarize.insert(*it);
 269         DEBUG(dbgs()<<"Adding " << **it <<
 270               " to MustScalarize because multiple lane use it: "
 271               << Lane << " and " << LaneMap[*I] << ".\n");
 272         break;
 273       }
 274     }
 275   }
 276
 277   // Now calculate the cost of vectorizing the tree.
 278   return getTreeCost_rec(VL, 0);
 279 }
 280
 281 void BoUpSLP::getTreeUses_rec(ArrayRef<Value *> VL, unsigned Depth) {
 282   if (Depth == RecursionMaxDepth) return;
 283
 284   // Don't handle vectors.
 285   if (VL[0]->getType()->isVectorTy()) return;
 286   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
 287     if (SI->getValueOperand()->getType()->isVectorTy()) return;
 288
 289   // Check if all of the operands are constants.
 290   bool AllConst = true;
 291   bool AllSameScalar = true;
 292   for (unsigned i = 0, e = VL.size(); i < e; ++i) {
 293     AllConst &= isa<Constant>(VL[i]);
 294     AllSameScalar &= (VL[0] == VL[i]);
 295     Instruction *I = dyn_cast<Instruction>(VL[i]);
 296     // If one of the instructions is out of this BB, we need to scalarize all.
 297     if (I && I->getParent() != BB) return;
 298   }
 299
 300   // If all of the operands are identical or constant we have a simple solution.
 301   if (AllConst || AllSameScalar) return;
 302
 303   // Scalarize unknown structures.
 304   Instruction *VL0 = dyn_cast<Instruction>(VL[0]);
 305   if (!VL0) return;
 306
 307   unsigned Opcode = VL0->getOpcode();
 308   for (unsigned i = 0, e = VL.size(); i < e; ++i) {
 309     Instruction *I = dyn_cast<Instruction>(VL[i]);
 310     // If not all of the instructions are identical then we have to scalarize.
 311     if (!I || Opcode != I->getOpcode()) return;
 312   }
 313
 314   // Mark instructions with multiple users.
 315   for (unsigned i = 0, e = VL.size(); i < e; ++i) {
 316     Instruction *I = dyn_cast<Instruction>(VL[i]);
 317     // Remember to check if all of the users of this instr are vectorized
 318     // within our tree.
 319     if (I && I->getNumUses() > 1) MultiUserVals.insert(I);
 320   }
 321
 322   for (int i = 0, e = VL.size(); i < e; ++i) {
 323     // Check that the instruction is only used within
 324     // one lane.
 325     if (LaneMap.count(VL[i]) && LaneMap[VL[i]] != i) return;
 326     // Make this instruction as 'seen' and remember the lane.
 327     LaneMap[VL[i]] = i;
 328   }
 329
 330   switch (Opcode) {
 331     case Instruction::Add:
 332     case Instruction::FAdd:
 333     case Instruction::Sub:
 334     case Instruction::FSub:
 335     case Instruction::Mul:
 336     case Instruction::FMul:
 337     case Instruction::UDiv:
 338     case Instruction::SDiv:
 339     case Instruction::FDiv:
 340     case Instruction::URem:
 341     case Instruction::SRem:
 342     case Instruction::FRem:
 343     case Instruction::Shl:
 344     case Instruction::LShr:
 345     case Instruction::AShr:
 346     case Instruction::And:
 347     case Instruction::Or:
 348     case Instruction::Xor: {
 349       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
 350         ValueList Operands;
 351         // Prepare the operand vector.
 352         for (unsigned j = 0; j < VL.size(); ++j)
 353           Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
 354
 355         getTreeUses_rec(Operands, Depth+1);
 356       }
 357       return;
 358     }
 359     case Instruction::Store: {
 360       ValueList Operands;
 361       for (unsigned j = 0; j < VL.size(); ++j)
 362         Operands.push_back(cast<Instruction>(VL[j])->getOperand(0));
 363       getTreeUses_rec(Operands, Depth+1);
 364       return;
 365     }
 366     default:
 367     return;
 368   }
 369 }
 370
 371 int BoUpSLP::getTreeCost_rec(ArrayRef<Value *> VL, unsigned Depth) {
 372   Type *ScalarTy = VL[0]->getType();
 373
 374   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
 375     ScalarTy = SI->getValueOperand()->getType();
 376
 377   /// Don't mess with vectors.
 378   if (ScalarTy->isVectorTy()) return max_cost;
 379   VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
 380
 381   if (Depth == RecursionMaxDepth) return getScalarizationCost(VecTy);
 382
 383   // Check if all of the operands are constants.
 384   bool AllConst = true;
 385   bool AllSameScalar = true;
 386   bool MustScalarizeFlag = false;
 387   for (unsigned i = 0, e = VL.size(); i < e; ++i) {
 388     AllConst &= isa<Constant>(VL[i]);
 389     AllSameScalar &= (VL[0] == VL[i]);
 390     // Must have a single use.
 391     Instruction *I = dyn_cast<Instruction>(VL[i]);
 392     MustScalarizeFlag |= MustScalarize.count(VL[i]);
 393     // This instruction is outside the basic block.
 394     if (I && I->getParent() != BB)
 395       return getScalarizationCost(VecTy);
 396   }
 397
 398   // Is this a simple vector constant.
 399   if (AllConst) return 0;
 400
 401   // If all of the operands are identical we can broadcast them.
 402   Instruction *VL0 = dyn_cast<Instruction>(VL[0]);
 403   if (AllSameScalar) {
 404     // If we are in a loop, and this is not an instruction (e.g. constant or
 405     // argument) or the instruction is defined outside the loop then assume
 406     // that the cost is zero.
 407     if (L && (!VL0 || !L->contains(VL0)))
 408       return 0;
 409
 410     // We need to broadcast the scalar.
 411     return TTI->getShuffleCost(TargetTransformInfo::SK_Broadcast, VecTy, 0);
 412   }
 413
 414   // If this is not a constant, or a scalar from outside the loop then we
 415   // need to scalarize it.
 416   if (MustScalarizeFlag)
 417     return getScalarizationCost(VecTy);
 418
 419   if (!VL0) return getScalarizationCost(VecTy);
 420   assert(VL0->getParent() == BB && "Wrong BB");
 421
 422   unsigned Opcode = VL0->getOpcode();
 423   for (unsigned i = 0, e = VL.size(); i < e; ++i) {
 424     Instruction *I = dyn_cast<Instruction>(VL[i]);
 425     // If not all of the instructions are identical then we have to scalarize.
 426     if (!I || Opcode != I->getOpcode()) return getScalarizationCost(VecTy);
 427   }
 428
 429   // Check if it is safe to sink the loads or the stores.
 430   if (Opcode == Instruction::Load || Opcode == Instruction::Store) {
 431     int MaxIdx = InstrIdx[VL0];
 432     for (unsigned i = 1, e = VL.size(); i < e; ++i )
 433       MaxIdx = std::max(MaxIdx, InstrIdx[VL[i]]);
 434
 435     Instruction *Last = InstrVec[MaxIdx];
 436     for (unsigned i = 0, e = VL.size(); i < e; ++i ) {
 437       if (VL[i] == Last) continue;
 438       Value *Barrier = isUnsafeToSink(cast<Instruction>(VL[i]), Last);
 439       if (Barrier) {
 440         DEBUG(dbgs() << "SLP: Can't sink " << *VL[i] << "\n down to " <<
 441               *Last << "\n because of " << *Barrier << "\n");
 442         return max_cost;
 443       }
 444     }
 445   }
 446
 447   switch (Opcode) {
 448   case Instruction::Add:
 449   case Instruction::FAdd:
 450   case Instruction::Sub:
 451   case Instruction::FSub:
 452   case Instruction::Mul:
 453   case Instruction::FMul:
 454   case Instruction::UDiv:
 455   case Instruction::SDiv:
 456   case Instruction::FDiv:
 457   case Instruction::URem:
 458   case Instruction::SRem:
 459   case Instruction::FRem:
 460   case Instruction::Shl:
 461   case Instruction::LShr:
 462   case Instruction::AShr:
 463   case Instruction::And:
 464   case Instruction::Or:
 465   case Instruction::Xor: {
 466     int Cost = 0;
 467     // Calculate the cost of all of the operands.
 468     for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
 469       ValueList Operands;
 470       // Prepare the operand vector.
 471       for (unsigned j = 0; j < VL.size(); ++j)
 472         Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
 473
 474       Cost += getTreeCost_rec(Operands, Depth+1);
 475       if (Cost >= max_cost) return max_cost;
 476     }
 477
 478     // Calculate the cost of this instruction.
 479     int ScalarCost = VecTy->getNumElements() *
 480       TTI->getArithmeticInstrCost(Opcode, ScalarTy);
 481
 482     int VecCost = TTI->getArithmeticInstrCost(Opcode, VecTy);
 483     Cost += (VecCost - ScalarCost);
 484     return Cost;
 485   }
 486   case Instruction::Load: {
 487     // If we are scalarize the loads, add the cost of forming the vector.
 488     for (unsigned i = 0, e = VL.size()-1; i < e; ++i)
 489       if (!isConsecutiveAccess(VL[i], VL[i+1]))
 490         return getScalarizationCost(VecTy);
 491
 492     // Cost of wide load - cost of scalar loads.
 493     int ScalarLdCost = VecTy->getNumElements() *
 494       TTI->getMemoryOpCost(Instruction::Load, ScalarTy, 1, 0);
 495     int VecLdCost = TTI->getMemoryOpCost(Instruction::Load, ScalarTy, 1, 0);
 496     return VecLdCost - ScalarLdCost;
 497   }
 498   case Instruction::Store: {
 499     // We know that we can merge the stores. Calculate the cost.
 500     int ScalarStCost = VecTy->getNumElements() *
 501       TTI->getMemoryOpCost(Instruction::Store, ScalarTy, 1, 0);
 502     int VecStCost = TTI->getMemoryOpCost(Instruction::Store, ScalarTy, 1,0);
 503     int StoreCost = VecStCost - ScalarStCost;
 504
 505     ValueList Operands;
 506     for (unsigned j = 0; j < VL.size(); ++j) {
 507       Operands.push_back(cast<Instruction>(VL[j])->getOperand(0));
 508       MemBarrierIgnoreList.insert(VL[j]);
 509     }
 510
 511     int TotalCost = StoreCost + getTreeCost_rec(Operands, Depth + 1);
 512     return TotalCost;
 513   }
 514   default:
 515     // Unable to vectorize unknown instructions.
 516     return getScalarizationCost(VecTy);
 517   }
 518 }
 519
 520 Instruction *BoUpSLP::GetLastInstr(ArrayRef<Value *> VL, unsigned VF) {
 521   int MaxIdx = InstrIdx[BB->getFirstNonPHI()];
 522   for (unsigned i = 0; i < VF; ++i )
 523     MaxIdx = std::max(MaxIdx, InstrIdx[VL[i]]);
 524   return InstrVec[MaxIdx + 1];
 525 }
 526
 527 Value *BoUpSLP::Scalarize(ArrayRef<Value *> VL, VectorType *Ty) {
 528   IRBuilder<> Builder(GetLastInstr(VL, Ty->getNumElements()));
 529   Value *Vec = UndefValue::get(Ty);
 530   for (unsigned i=0; i < Ty->getNumElements(); ++i) {
 531     // Generate the 'InsertElement' instruction.
 532     Vec = Builder.CreateInsertElement(Vec, VL[i], Builder.getInt32(i));
 533     // Remember that this instruction is used as part of a 'gather' sequence.
 534     // The caller of the bottom-up slp vectorizer can try to hoist the sequence
 535     // if the users are outside of the basic block.
 536     GatherInstructions.push_back(Vec);
 537   }
 538
 539   return Vec;
 540 }
 541
 542 Value *BoUpSLP::vectorizeTree(ArrayRef<Value *> VL, int VF) {
 543   Value *V = vectorizeTree_rec(VL, VF);
 544   // We moved some instructions around. We have to number them again
 545   // before we can do any analysis.
 546   numberInstructions();
 547   MustScalarize.clear();
 548   return V;
 549 }
 550
 551 Value *BoUpSLP::vectorizeTree_rec(ArrayRef<Value *> VL, int VF) {
 552   Type *ScalarTy = VL[0]->getType();
 553   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
 554     ScalarTy = SI->getValueOperand()->getType();
 555   VectorType *VecTy = VectorType::get(ScalarTy, VF);
 556
 557   // Check if all of the operands are constants or identical.
 558   bool AllConst = true;
 559   bool AllSameScalar = true;
 560   for (unsigned i = 0, e = VF; i < e; ++i) {
 561     AllConst &= isa<Constant>(VL[i]);
 562     AllSameScalar &= (VL[0] == VL[i]);
 563     // The instruction must be in the same BB, and it must be vectorizable.
 564     Instruction *I = dyn_cast<Instruction>(VL[i]);
 565     if (MustScalarize.count(VL[i]) || (I && I->getParent() != BB))
 566       return Scalarize(VL, VecTy);
 567   }
 568
 569   // Check that this is a simple vector constant.
 570   if (AllConst || AllSameScalar) return Scalarize(VL, VecTy);
 571
 572   // Scalarize unknown structures.
 573   Instruction *VL0 = dyn_cast<Instruction>(VL[0]);
 574   if (!VL0) return Scalarize(VL, VecTy);
 575
 576   if (VectorizedValues.count(VL0)) return VectorizedValues[VL0];
 577
 578   unsigned Opcode = VL0->getOpcode();
 579   for (unsigned i = 0, e = VF; i < e; ++i) {
 580     Instruction *I = dyn_cast<Instruction>(VL[i]);
 581     // If not all of the instructions are identical then we have to scalarize.
 582     if (!I || Opcode != I->getOpcode()) return Scalarize(VL, VecTy);
 583   }
 584
 585   switch (Opcode) {
 586   case Instruction::Add:
 587   case Instruction::FAdd:
 588   case Instruction::Sub:
 589   case Instruction::FSub:
 590   case Instruction::Mul:
 591   case Instruction::FMul:
 592   case Instruction::UDiv:
 593   case Instruction::SDiv:
 594   case Instruction::FDiv:
 595   case Instruction::URem:
 596   case Instruction::SRem:
 597   case Instruction::FRem:
 598   case Instruction::Shl:
 599   case Instruction::LShr:
 600   case Instruction::AShr:
 601   case Instruction::And:
 602   case Instruction::Or:
 603   case Instruction::Xor: {
 604     ValueList LHSVL, RHSVL;
 605     for (int i = 0; i < VF; ++i) {
 606       RHSVL.push_back(cast<Instruction>(VL[i])->getOperand(0));
 607       LHSVL.push_back(cast<Instruction>(VL[i])->getOperand(1));
 608     }
 609
 610     Value *RHS = vectorizeTree_rec(RHSVL, VF);
 611     Value *LHS = vectorizeTree_rec(LHSVL, VF);
 612     IRBuilder<> Builder(GetLastInstr(VL, VF));
 613     BinaryOperator *BinOp = cast<BinaryOperator>(VL0);
 614     Value *V = Builder.CreateBinOp(BinOp->getOpcode(), RHS,LHS);
 615     VectorizedValues[VL0] = V;
 616     return V;
 617   }
 618   case Instruction::Load: {
 619     LoadInst *LI = cast<LoadInst>(VL0);
 620     unsigned Alignment = LI->getAlignment();
 621
 622     // Check if all of the loads are consecutive.
 623     for (unsigned i = 1, e = VF; i < e; ++i)
 624       if (!isConsecutiveAccess(VL[i-1], VL[i]))
 625         return Scalarize(VL, VecTy);
 626
 627     IRBuilder<> Builder(GetLastInstr(VL, VF));
 628     Value *VecPtr = Builder.CreateBitCast(LI->getPointerOperand(),
 629                                           VecTy->getPointerTo());
 630     LI = Builder.CreateLoad(VecPtr);
 631     LI->setAlignment(Alignment);
 632     VectorizedValues[VL0] = LI;
 633     return LI;
 634   }
 635   case Instruction::Store: {
 636     StoreInst *SI = cast<StoreInst>(VL0);
 637     unsigned Alignment = SI->getAlignment();
 638
 639     ValueList ValueOp;
 640     for (int i = 0; i < VF; ++i)
 641       ValueOp.push_back(cast<StoreInst>(VL[i])->getValueOperand());
 642
 643     Value *VecValue = vectorizeTree_rec(ValueOp, VF);
 644
 645     IRBuilder<> Builder(GetLastInstr(VL, VF));
 646     Value *VecPtr = Builder.CreateBitCast(SI->getPointerOperand(),
 647                                           VecTy->getPointerTo());
 648     Builder.CreateStore(VecValue, VecPtr)->setAlignment(Alignment);
 649
 650     for (int i = 0; i < VF; ++i)
 651       cast<Instruction>(VL[i])->eraseFromParent();
 652     return 0;
 653   }
 654   default:
 655     Value *S = Scalarize(VL, VecTy);
 656     VectorizedValues[VL0] = S;
 657     return S;
 658   }
 659 }
 660
 661 } // end of namespace