lib/Transforms/Vectorize/BBVectorize.cpp

   1 //===- BBVectorize.cpp - A Basic-Block Vectorizer -------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a basic-block vectorization pass. The algorithm was
  11 // inspired by that used by the Vienna MAP Vectorizor by Franchetti and Kral,
  12 // et al. It works by looking for chains of pairable operations and then
  13 // pairing them.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #define BBV_NAME "bb-vectorize"
  18 #define DEBUG_TYPE BBV_NAME
  19 #include "llvm/Constants.h"
  20 #include "llvm/DerivedTypes.h"
  21 #include "llvm/Function.h"
  22 #include "llvm/Instructions.h"
  23 #include "llvm/IntrinsicInst.h"
  24 #include "llvm/Intrinsics.h"
  25 #include "llvm/LLVMContext.h"
  26 #include "llvm/Metadata.h"
  27 #include "llvm/Pass.h"
  28 #include "llvm/Type.h"
  29 #include "llvm/ADT/DenseMap.h"
  30 #include "llvm/ADT/DenseSet.h"
  31 #include "llvm/ADT/SmallVector.h"
  32 #include "llvm/ADT/Statistic.h"
  33 #include "llvm/ADT/STLExtras.h"
  34 #include "llvm/ADT/StringExtras.h"
  35 #include "llvm/Analysis/AliasAnalysis.h"
  36 #include "llvm/Analysis/AliasSetTracker.h"
  37 #include "llvm/Analysis/ScalarEvolution.h"
  38 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  39 #include "llvm/Analysis/ValueTracking.h"
  40 #include "llvm/Support/CommandLine.h"
  41 #include "llvm/Support/Debug.h"
  42 #include "llvm/Support/raw_ostream.h"
  43 #include "llvm/Support/ValueHandle.h"
  44 #include "llvm/Target/TargetData.h"
  45 #include "llvm/Transforms/Utils/Local.h"
  46 #include "llvm/Transforms/Vectorize.h"
  47 #include <algorithm>
  48 #include <map>
  49 using namespace llvm;
  50
  51 static cl::opt<unsigned>
  52 ReqChainDepth("bb-vectorize-req-chain-depth", cl::init(6), cl::Hidden,
  53   cl::desc("The required chain depth for vectorization"));
  54
  55 static cl::opt<unsigned>
  56 SearchLimit("bb-vectorize-search-limit", cl::init(400), cl::Hidden,
  57   cl::desc("The maximum search distance for instruction pairs"));
  58
  59 static cl::opt<bool>
  60 SplatBreaksChain("bb-vectorize-splat-breaks-chain", cl::init(false), cl::Hidden,
  61   cl::desc("Replicating one element to a pair breaks the chain"));
  62
  63 static cl::opt<unsigned>
  64 VectorBits("bb-vectorize-vector-bits", cl::init(128), cl::Hidden,
  65   cl::desc("The size of the native vector registers"));
  66
  67 static cl::opt<unsigned>
  68 MaxIter("bb-vectorize-max-iter", cl::init(0), cl::Hidden,
  69   cl::desc("The maximum number of pairing iterations"));
  70
  71 static cl::opt<bool>
  72 Pow2LenOnly("bb-vectorize-pow2-len-only", cl::init(false), cl::Hidden,
  73   cl::desc("Don't try to form non-2^n-length vectors"));
  74
  75 static cl::opt<unsigned>
  76 MaxInsts("bb-vectorize-max-instr-per-group", cl::init(500), cl::Hidden,
  77   cl::desc("The maximum number of pairable instructions per group"));
  78
  79 static cl::opt<unsigned>
  80 MaxCandPairsForCycleCheck("bb-vectorize-max-cycle-check-pairs", cl::init(200),
  81   cl::Hidden, cl::desc("The maximum number of candidate pairs with which to use"
  82                        " a full cycle check"));
  83
  84 static cl::opt<bool>
  85 NoBools("bb-vectorize-no-bools", cl::init(false), cl::Hidden,
  86   cl::desc("Don't try to vectorize boolean (i1) values"));
  87
  88 static cl::opt<bool>
  89 NoInts("bb-vectorize-no-ints", cl::init(false), cl::Hidden,
  90   cl::desc("Don't try to vectorize integer values"));
  91
  92 static cl::opt<bool>
  93 NoFloats("bb-vectorize-no-floats", cl::init(false), cl::Hidden,
  94   cl::desc("Don't try to vectorize floating-point values"));
  95
  96 static cl::opt<bool>
  97 NoPointers("bb-vectorize-no-pointers", cl::init(false), cl::Hidden,
  98   cl::desc("Don't try to vectorize pointer values"));
  99
 100 static cl::opt<bool>
 101 NoCasts("bb-vectorize-no-casts", cl::init(false), cl::Hidden,
 102   cl::desc("Don't try to vectorize casting (conversion) operations"));
 103
 104 static cl::opt<bool>
 105 NoMath("bb-vectorize-no-math", cl::init(false), cl::Hidden,
 106   cl::desc("Don't try to vectorize floating-point math intrinsics"));
 107
 108 static cl::opt<bool>
 109 NoFMA("bb-vectorize-no-fma", cl::init(false), cl::Hidden,
 110   cl::desc("Don't try to vectorize the fused-multiply-add intrinsic"));
 111
 112 static cl::opt<bool>
 113 NoSelect("bb-vectorize-no-select", cl::init(false), cl::Hidden,
 114   cl::desc("Don't try to vectorize select instructions"));
 115
 116 static cl::opt<bool>
 117 NoCmp("bb-vectorize-no-cmp", cl::init(false), cl::Hidden,
 118   cl::desc("Don't try to vectorize comparison instructions"));
 119
 120 static cl::opt<bool>
 121 NoGEP("bb-vectorize-no-gep", cl::init(false), cl::Hidden,
 122   cl::desc("Don't try to vectorize getelementptr instructions"));
 123
 124 static cl::opt<bool>
 125 NoMemOps("bb-vectorize-no-mem-ops", cl::init(false), cl::Hidden,
 126   cl::desc("Don't try to vectorize loads and stores"));
 127
 128 static cl::opt<bool>
 129 AlignedOnly("bb-vectorize-aligned-only", cl::init(false), cl::Hidden,
 130   cl::desc("Only generate aligned loads and stores"));
 131
 132 static cl::opt<bool>
 133 NoMemOpBoost("bb-vectorize-no-mem-op-boost",
 134   cl::init(false), cl::Hidden,
 135   cl::desc("Don't boost the chain-depth contribution of loads and stores"));
 136
 137 static cl::opt<bool>
 138 FastDep("bb-vectorize-fast-dep", cl::init(false), cl::Hidden,
 139   cl::desc("Use a fast instruction dependency analysis"));
 140
 141 #ifndef NDEBUG
 142 static cl::opt<bool>
 143 DebugInstructionExamination("bb-vectorize-debug-instruction-examination",
 144   cl::init(false), cl::Hidden,
 145   cl::desc("When debugging is enabled, output information on the"
 146            " instruction-examination process"));
 147 static cl::opt<bool>
 148 DebugCandidateSelection("bb-vectorize-debug-candidate-selection",
 149   cl::init(false), cl::Hidden,
 150   cl::desc("When debugging is enabled, output information on the"
 151            " candidate-selection process"));
 152 static cl::opt<bool>
 153 DebugPairSelection("bb-vectorize-debug-pair-selection",
 154   cl::init(false), cl::Hidden,
 155   cl::desc("When debugging is enabled, output information on the"
 156            " pair-selection process"));
 157 static cl::opt<bool>
 158 DebugCycleCheck("bb-vectorize-debug-cycle-check",
 159   cl::init(false), cl::Hidden,
 160   cl::desc("When debugging is enabled, output information on the"
 161            " cycle-checking process"));
 162 #endif
 163
 164 STATISTIC(NumFusedOps, "Number of operations fused by bb-vectorize");
 165
 166 namespace {
 167   struct BBVectorize : public BasicBlockPass {
 168     static char ID; // Pass identification, replacement for typeid
 169
 170     const VectorizeConfig Config;
 171
 172     BBVectorize(const VectorizeConfig &C = VectorizeConfig())
 173       : BasicBlockPass(ID), Config(C) {
 174       initializeBBVectorizePass(*PassRegistry::getPassRegistry());
 175     }
 176
 177     BBVectorize(Pass *P, const VectorizeConfig &C)
 178       : BasicBlockPass(ID), Config(C) {
 179       AA = &P->getAnalysis<AliasAnalysis>();
 180       SE = &P->getAnalysis<ScalarEvolution>();
 181       TD = P->getAnalysisIfAvailable<TargetData>();
 182     }
 183
 184     typedef std::pair<Value *, Value *> ValuePair;
 185     typedef std::pair<ValuePair, size_t> ValuePairWithDepth;
 186     typedef std::pair<ValuePair, ValuePair> VPPair; // A ValuePair pair
 187     typedef std::pair<std::multimap<Value *, Value *>::iterator,
 188               std::multimap<Value *, Value *>::iterator> VPIteratorPair;
 189     typedef std::pair<std::multimap<ValuePair, ValuePair>::iterator,
 190               std::multimap<ValuePair, ValuePair>::iterator>
 191                 VPPIteratorPair;
 192
 193     AliasAnalysis *AA;
 194     ScalarEvolution *SE;
 195     TargetData *TD;
 196
 197     // FIXME: const correct?
 198
 199     bool vectorizePairs(BasicBlock &BB, bool NonPow2Len = false);
 200
 201     bool getCandidatePairs(BasicBlock &BB,
 202                        BasicBlock::iterator &Start,
 203                        std::multimap<Value *, Value *> &CandidatePairs,
 204                        std::vector<Value *> &PairableInsts, bool NonPow2Len);
 205
 206     void computeConnectedPairs(std::multimap<Value *, Value *> &CandidatePairs,
 207                        std::vector<Value *> &PairableInsts,
 208                        std::multimap<ValuePair, ValuePair> &ConnectedPairs);
 209
 210     void buildDepMap(BasicBlock &BB,
 211                        std::multimap<Value *, Value *> &CandidatePairs,
 212                        std::vector<Value *> &PairableInsts,
 213                        DenseSet<ValuePair> &PairableInstUsers);
 214
 215     void choosePairs(std::multimap<Value *, Value *> &CandidatePairs,
 216                         std::vector<Value *> &PairableInsts,
 217                         std::multimap<ValuePair, ValuePair> &ConnectedPairs,
 218                         DenseSet<ValuePair> &PairableInstUsers,
 219                         DenseMap<Value *, Value *>& ChosenPairs);
 220
 221     void fuseChosenPairs(BasicBlock &BB,
 222                      std::vector<Value *> &PairableInsts,
 223                      DenseMap<Value *, Value *>& ChosenPairs);
 224
 225     bool isInstVectorizable(Instruction *I, bool &IsSimpleLoadStore);
 226
 227     bool areInstsCompatible(Instruction *I, Instruction *J,
 228                        bool IsSimpleLoadStore, bool NonPow2Len);
 229
 230     bool trackUsesOfI(DenseSet<Value *> &Users,
 231                       AliasSetTracker &WriteSet, Instruction *I,
 232                       Instruction *J, bool UpdateUsers = true,
 233                       std::multimap<Value *, Value *> *LoadMoveSet = 0);
 234
 235     void computePairsConnectedTo(
 236                       std::multimap<Value *, Value *> &CandidatePairs,
 237                       std::vector<Value *> &PairableInsts,
 238                       std::multimap<ValuePair, ValuePair> &ConnectedPairs,
 239                       ValuePair P);
 240
 241     bool pairsConflict(ValuePair P, ValuePair Q,
 242                  DenseSet<ValuePair> &PairableInstUsers,
 243                  std::multimap<ValuePair, ValuePair> *PairableInstUserMap = 0);
 244
 245     bool pairWillFormCycle(ValuePair P,
 246                        std::multimap<ValuePair, ValuePair> &PairableInstUsers,
 247                        DenseSet<ValuePair> &CurrentPairs);
 248
 249     void pruneTreeFor(
 250                       std::multimap<Value *, Value *> &CandidatePairs,
 251                       std::vector<Value *> &PairableInsts,
 252                       std::multimap<ValuePair, ValuePair> &ConnectedPairs,
 253                       DenseSet<ValuePair> &PairableInstUsers,
 254                       std::multimap<ValuePair, ValuePair> &PairableInstUserMap,
 255                       DenseMap<Value *, Value *> &ChosenPairs,
 256                       DenseMap<ValuePair, size_t> &Tree,
 257                       DenseSet<ValuePair> &PrunedTree, ValuePair J,
 258                       bool UseCycleCheck);
 259
 260     void buildInitialTreeFor(
 261                       std::multimap<Value *, Value *> &CandidatePairs,
 262                       std::vector<Value *> &PairableInsts,
 263                       std::multimap<ValuePair, ValuePair> &ConnectedPairs,
 264                       DenseSet<ValuePair> &PairableInstUsers,
 265                       DenseMap<Value *, Value *> &ChosenPairs,
 266                       DenseMap<ValuePair, size_t> &Tree, ValuePair J);
 267
 268     void findBestTreeFor(
 269                       std::multimap<Value *, Value *> &CandidatePairs,
 270                       std::vector<Value *> &PairableInsts,
 271                       std::multimap<ValuePair, ValuePair> &ConnectedPairs,
 272                       DenseSet<ValuePair> &PairableInstUsers,
 273                       std::multimap<ValuePair, ValuePair> &PairableInstUserMap,
 274                       DenseMap<Value *, Value *> &ChosenPairs,
 275                       DenseSet<ValuePair> &BestTree, size_t &BestMaxDepth,
 276                       size_t &BestEffSize, VPIteratorPair ChoiceRange,
 277                       bool UseCycleCheck);
 278
 279     Value *getReplacementPointerInput(LLVMContext& Context, Instruction *I,
 280                      Instruction *J, unsigned o, bool FlipMemInputs);
 281
 282     void fillNewShuffleMask(LLVMContext& Context, Instruction *J,
 283                      unsigned MaskOffset, unsigned NumInElem,
 284                      unsigned NumInElem1, unsigned IdxOffset,
 285                      std::vector<Constant*> &Mask);
 286
 287     Value *getReplacementShuffleMask(LLVMContext& Context, Instruction *I,
 288                      Instruction *J);
 289
 290     bool expandIEChain(LLVMContext& Context, Instruction *I, Instruction *J,
 291                        unsigned o, Value *&LOp, unsigned numElemL,
 292                        Type *ArgTypeL, Type *ArgTypeR,
 293                        unsigned IdxOff = 0);
 294
 295     Value *getReplacementInput(LLVMContext& Context, Instruction *I,
 296                      Instruction *J, unsigned o, bool FlipMemInputs);
 297
 298     void getReplacementInputsForPair(LLVMContext& Context, Instruction *I,
 299                      Instruction *J, SmallVector<Value *, 3> &ReplacedOperands,
 300                      bool FlipMemInputs);
 301
 302     void replaceOutputsOfPair(LLVMContext& Context, Instruction *I,
 303                      Instruction *J, Instruction *K,
 304                      Instruction *&InsertionPt, Instruction *&K1,
 305                      Instruction *&K2, bool FlipMemInputs);
 306
 307     void collectPairLoadMoveSet(BasicBlock &BB,
 308                      DenseMap<Value *, Value *> &ChosenPairs,
 309                      std::multimap<Value *, Value *> &LoadMoveSet,
 310                      Instruction *I);
 311
 312     void collectLoadMoveSet(BasicBlock &BB,
 313                      std::vector<Value *> &PairableInsts,
 314                      DenseMap<Value *, Value *> &ChosenPairs,
 315                      std::multimap<Value *, Value *> &LoadMoveSet);
 316
 317     void collectPtrInfo(std::vector<Value *> &PairableInsts,
 318                         DenseMap<Value *, Value *> &ChosenPairs,
 319                         DenseSet<Value *> &LowPtrInsts);
 320
 321     bool canMoveUsesOfIAfterJ(BasicBlock &BB,
 322                      std::multimap<Value *, Value *> &LoadMoveSet,
 323                      Instruction *I, Instruction *J);
 324
 325     void moveUsesOfIAfterJ(BasicBlock &BB,
 326                      std::multimap<Value *, Value *> &LoadMoveSet,
 327                      Instruction *&InsertionPt,
 328                      Instruction *I, Instruction *J);
 329
 330     void combineMetadata(Instruction *K, const Instruction *J);
 331
 332     bool vectorizeBB(BasicBlock &BB) {
 333       bool changed = false;
 334       // Iterate a sufficient number of times to merge types of size 1 bit,
 335       // then 2 bits, then 4, etc. up to half of the target vector width of the
 336       // target vector register.
 337       unsigned n = 1;
 338       for (unsigned v = 2;
 339            v <= Config.VectorBits && (!Config.MaxIter || n <= Config.MaxIter);
 340            v *= 2, ++n) {
 341         DEBUG(dbgs() << "BBV: fusing loop #" << n <<
 342               " for " << BB.getName() << " in " <<
 343               BB.getParent()->getName() << "...\n");
 344         if (vectorizePairs(BB))
 345           changed = true;
 346         else
 347           break;
 348       }
 349
 350       if (changed && !Pow2LenOnly) {
 351         ++n;
 352         for (; !Config.MaxIter || n <= Config.MaxIter; ++n) {
 353           DEBUG(dbgs() << "BBV: fusing for non-2^n-length vectors loop #: " <<
 354                 n << " for " << BB.getName() << " in " <<
 355                 BB.getParent()->getName() << "...\n");
 356           if (!vectorizePairs(BB, true)) break;
 357         }
 358       }
 359
 360       DEBUG(dbgs() << "BBV: done!\n");
 361       return changed;
 362     }
 363
 364     virtual bool runOnBasicBlock(BasicBlock &BB) {
 365       AA = &getAnalysis<AliasAnalysis>();
 366       SE = &getAnalysis<ScalarEvolution>();
 367       TD = getAnalysisIfAvailable<TargetData>();
 368
 369       return vectorizeBB(BB);
 370     }
 371
 372     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 373       BasicBlockPass::getAnalysisUsage(AU);
 374       AU.addRequired<AliasAnalysis>();
 375       AU.addRequired<ScalarEvolution>();
 376       AU.addPreserved<AliasAnalysis>();
 377       AU.addPreserved<ScalarEvolution>();
 378       AU.setPreservesCFG();
 379     }
 380
 381     static inline VectorType *getVecTypeForPair(Type *ElemTy, Type *Elem2Ty) {
 382       assert(ElemTy->getScalarType() == Elem2Ty->getScalarType() &&
 383              "Cannot form vector from incompatible scalar types");
 384       Type *STy = ElemTy->getScalarType();
 385
 386       unsigned numElem;
 387       if (VectorType *VTy = dyn_cast<VectorType>(ElemTy)) {
 388         numElem = VTy->getNumElements();
 389       } else {
 390         numElem = 1;
 391       }
 392
 393       if (VectorType *VTy = dyn_cast<VectorType>(Elem2Ty)) {
 394         numElem += VTy->getNumElements();
 395       } else {
 396         numElem += 1;
 397       }
 398
 399       return VectorType::get(STy, numElem);
 400     }
 401
 402     static inline void getInstructionTypes(Instruction *I,
 403                                            Type *&T1, Type *&T2) {
 404       if (isa<StoreInst>(I)) {
 405         // For stores, it is the value type, not the pointer type that matters
 406         // because the value is what will come from a vector register.
 407
 408         Value *IVal = cast<StoreInst>(I)->getValueOperand();
 409         T1 = IVal->getType();
 410       } else {
 411         T1 = I->getType();
 412       }
 413
 414       if (I->isCast())
 415         T2 = cast<CastInst>(I)->getSrcTy();
 416       else
 417         T2 = T1;
 418     }
 419
 420     // Returns the weight associated with the provided value. A chain of
 421     // candidate pairs has a length given by the sum of the weights of its
 422     // members (one weight per pair; the weight of each member of the pair
 423     // is assumed to be the same). This length is then compared to the
 424     // chain-length threshold to determine if a given chain is significant
 425     // enough to be vectorized. The length is also used in comparing
 426     // candidate chains where longer chains are considered to be better.
 427     // Note: when this function returns 0, the resulting instructions are
 428     // not actually fused.
 429     inline size_t getDepthFactor(Value *V) {
 430       // InsertElement and ExtractElement have a depth factor of zero. This is
 431       // for two reasons: First, they cannot be usefully fused. Second, because
 432       // the pass generates a lot of these, they can confuse the simple metric
 433       // used to compare the trees in the next iteration. Thus, giving them a
 434       // weight of zero allows the pass to essentially ignore them in
 435       // subsequent iterations when looking for vectorization opportunities
 436       // while still tracking dependency chains that flow through those
 437       // instructions.
 438       if (isa<InsertElementInst>(V) || isa<ExtractElementInst>(V))
 439         return 0;
 440
 441       // Give a load or store half of the required depth so that load/store
 442       // pairs will vectorize.
 443       if (!Config.NoMemOpBoost && (isa<LoadInst>(V) || isa<StoreInst>(V)))
 444         return Config.ReqChainDepth/2;
 445
 446       return 1;
 447     }
 448
 449     // This determines the relative offset of two loads or stores, returning
 450     // true if the offset could be determined to be some constant value.
 451     // For example, if OffsetInElmts == 1, then J accesses the memory directly
 452     // after I; if OffsetInElmts == -1 then I accesses the memory
 453     // directly after J.
 454     bool getPairPtrInfo(Instruction *I, Instruction *J,
 455         Value *&IPtr, Value *&JPtr, unsigned &IAlignment, unsigned &JAlignment,
 456         int64_t &OffsetInElmts) {
 457       OffsetInElmts = 0;
 458       if (isa<LoadInst>(I)) {
 459         IPtr = cast<LoadInst>(I)->getPointerOperand();
 460         JPtr = cast<LoadInst>(J)->getPointerOperand();
 461         IAlignment = cast<LoadInst>(I)->getAlignment();
 462         JAlignment = cast<LoadInst>(J)->getAlignment();
 463       } else {
 464         IPtr = cast<StoreInst>(I)->getPointerOperand();
 465         JPtr = cast<StoreInst>(J)->getPointerOperand();
 466         IAlignment = cast<StoreInst>(I)->getAlignment();
 467         JAlignment = cast<StoreInst>(J)->getAlignment();
 468       }
 469
 470       const SCEV *IPtrSCEV = SE->getSCEV(IPtr);
 471       const SCEV *JPtrSCEV = SE->getSCEV(JPtr);
 472
 473       // If this is a trivial offset, then we'll get something like
 474       // 1*sizeof(type). With target data, which we need anyway, this will get
 475       // constant folded into a number.
 476       const SCEV *OffsetSCEV = SE->getMinusSCEV(JPtrSCEV, IPtrSCEV);
 477       if (const SCEVConstant *ConstOffSCEV =
 478             dyn_cast<SCEVConstant>(OffsetSCEV)) {
 479         ConstantInt *IntOff = ConstOffSCEV->getValue();
 480         int64_t Offset = IntOff->getSExtValue();
 481
 482         Type *VTy = cast<PointerType>(IPtr->getType())->getElementType();
 483         int64_t VTyTSS = (int64_t) TD->getTypeStoreSize(VTy);
 484
 485         Type *VTy2 = cast<PointerType>(JPtr->getType())->getElementType();
 486         if (VTy != VTy2 && Offset < 0) {
 487           int64_t VTy2TSS = (int64_t) TD->getTypeStoreSize(VTy2);
 488           OffsetInElmts = Offset/VTy2TSS;
 489           return (abs64(Offset) % VTy2TSS) == 0;
 490         }
 491
 492         OffsetInElmts = Offset/VTyTSS;
 493         return (abs64(Offset) % VTyTSS) == 0;
 494       }
 495
 496       return false;
 497     }
 498
 499     // Returns true if the provided CallInst represents an intrinsic that can
 500     // be vectorized.
 501     bool isVectorizableIntrinsic(CallInst* I) {
 502       Function *F = I->getCalledFunction();
 503       if (!F) return false;
 504
 505       unsigned IID = F->getIntrinsicID();
 506       if (!IID) return false;
 507
 508       switch(IID) {
 509       default:
 510         return false;
 511       case Intrinsic::sqrt:
 512       case Intrinsic::powi:
 513       case Intrinsic::sin:
 514       case Intrinsic::cos:
 515       case Intrinsic::log:
 516       case Intrinsic::log2:
 517       case Intrinsic::log10:
 518       case Intrinsic::exp:
 519       case Intrinsic::exp2:
 520       case Intrinsic::pow:
 521         return Config.VectorizeMath;
 522       case Intrinsic::fma:
 523         return Config.VectorizeFMA;
 524       }
 525     }
 526
 527     // Returns true if J is the second element in some pair referenced by
 528     // some multimap pair iterator pair.
 529     template <typename V>
 530     bool isSecondInIteratorPair(V J, std::pair<
 531            typename std::multimap<V, V>::iterator,
 532            typename std::multimap<V, V>::iterator> PairRange) {
 533       for (typename std::multimap<V, V>::iterator K = PairRange.first;
 534            K != PairRange.second; ++K)
 535         if (K->second == J) return true;
 536
 537       return false;
 538     }
 539   };
 540
 541   // This function implements one vectorization iteration on the provided
 542   // basic block. It returns true if the block is changed.
 543   bool BBVectorize::vectorizePairs(BasicBlock &BB, bool NonPow2Len) {
 544     bool ShouldContinue;
 545     BasicBlock::iterator Start = BB.getFirstInsertionPt();
 546
 547     std::vector<Value *> AllPairableInsts;
 548     DenseMap<Value *, Value *> AllChosenPairs;
 549
 550     do {
 551       std::vector<Value *> PairableInsts;
 552       std::multimap<Value *, Value *> CandidatePairs;
 553       ShouldContinue = getCandidatePairs(BB, Start, CandidatePairs,
 554                                          PairableInsts, NonPow2Len);
 555       if (PairableInsts.empty()) continue;
 556
 557       // Now we have a map of all of the pairable instructions and we need to
 558       // select the best possible pairing. A good pairing is one such that the
 559       // users of the pair are also paired. This defines a (directed) forest
 560       // over the pairs such that two pairs are connected iff the second pair
 561       // uses the first.
 562
 563       // Note that it only matters that both members of the second pair use some
 564       // element of the first pair (to allow for splatting).
 565
 566       std::multimap<ValuePair, ValuePair> ConnectedPairs;
 567       computeConnectedPairs(CandidatePairs, PairableInsts, ConnectedPairs);
 568       if (ConnectedPairs.empty()) continue;
 569
 570       // Build the pairable-instruction dependency map
 571       DenseSet<ValuePair> PairableInstUsers;
 572       buildDepMap(BB, CandidatePairs, PairableInsts, PairableInstUsers);
 573
 574       // There is now a graph of the connected pairs. For each variable, pick
 575       // the pairing with the largest tree meeting the depth requirement on at
 576       // least one branch. Then select all pairings that are part of that tree
 577       // and remove them from the list of available pairings and pairable
 578       // variables.
 579
 580       DenseMap<Value *, Value *> ChosenPairs;
 581       choosePairs(CandidatePairs, PairableInsts, ConnectedPairs,
 582         PairableInstUsers, ChosenPairs);
 583
 584       if (ChosenPairs.empty()) continue;
 585       AllPairableInsts.insert(AllPairableInsts.end(), PairableInsts.begin(),
 586                               PairableInsts.end());
 587       AllChosenPairs.insert(ChosenPairs.begin(), ChosenPairs.end());
 588     } while (ShouldContinue);
 589
 590     if (AllChosenPairs.empty()) return false;
 591     NumFusedOps += AllChosenPairs.size();
 592
 593     // A set of pairs has now been selected. It is now necessary to replace the
 594     // paired instructions with vector instructions. For this procedure each
 595     // operand must be replaced with a vector operand. This vector is formed
 596     // by using build_vector on the old operands. The replaced values are then
 597     // replaced with a vector_extract on the result.  Subsequent optimization
 598     // passes should coalesce the build/extract combinations.
 599
 600     fuseChosenPairs(BB, AllPairableInsts, AllChosenPairs);
 601
 602     // It is important to cleanup here so that future iterations of this
 603     // function have less work to do.
 604     (void) SimplifyInstructionsInBlock(&BB, TD);
 605     return true;
 606   }
 607
 608   // This function returns true if the provided instruction is capable of being
 609   // fused into a vector instruction. This determination is based only on the
 610   // type and other attributes of the instruction.
 611   bool BBVectorize::isInstVectorizable(Instruction *I,
 612                                          bool &IsSimpleLoadStore) {
 613     IsSimpleLoadStore = false;
 614
 615     if (CallInst *C = dyn_cast<CallInst>(I)) {
 616       if (!isVectorizableIntrinsic(C))
 617         return false;
 618     } else if (LoadInst *L = dyn_cast<LoadInst>(I)) {
 619       // Vectorize simple loads if possbile:
 620       IsSimpleLoadStore = L->isSimple();
 621       if (!IsSimpleLoadStore || !Config.VectorizeMemOps)
 622         return false;
 623     } else if (StoreInst *S = dyn_cast<StoreInst>(I)) {
 624       // Vectorize simple stores if possbile:
 625       IsSimpleLoadStore = S->isSimple();
 626       if (!IsSimpleLoadStore || !Config.VectorizeMemOps)
 627         return false;
 628     } else if (CastInst *C = dyn_cast<CastInst>(I)) {
 629       // We can vectorize casts, but not casts of pointer types, etc.
 630       if (!Config.VectorizeCasts)
 631         return false;
 632
 633       Type *SrcTy = C->getSrcTy();
 634       if (!SrcTy->isSingleValueType())
 635         return false;
 636
 637       Type *DestTy = C->getDestTy();
 638       if (!DestTy->isSingleValueType())
 639         return false;
 640     } else if (isa<SelectInst>(I)) {
 641       if (!Config.VectorizeSelect)
 642         return false;
 643     } else if (isa<CmpInst>(I)) {
 644       if (!Config.VectorizeCmp)
 645         return false;
 646     } else if (GetElementPtrInst *G = dyn_cast<GetElementPtrInst>(I)) {
 647       if (!Config.VectorizeGEP)
 648         return false;
 649
 650       // Currently, vector GEPs exist only with one index.
 651       if (G->getNumIndices() != 1)
 652         return false;
 653     } else if (!(I->isBinaryOp() || isa<ShuffleVectorInst>(I) ||
 654         isa<ExtractElementInst>(I) || isa<InsertElementInst>(I))) {
 655       return false;
 656     }
 657
 658     // We can't vectorize memory operations without target data
 659     if (TD == 0 && IsSimpleLoadStore)
 660       return false;
 661
 662     Type *T1, *T2;
 663     getInstructionTypes(I, T1, T2);
 664
 665     // Not every type can be vectorized...
 666     if (!(VectorType::isValidElementType(T1) || T1->isVectorTy()) ||
 667         !(VectorType::isValidElementType(T2) || T2->isVectorTy()))
 668       return false;
 669
 670     if (T1->getScalarSizeInBits() == 1 && T2->getScalarSizeInBits() == 1) {
 671       if (!Config.VectorizeBools)
 672         return false;
 673     } else {
 674       if (!Config.VectorizeInts
 675           && (T1->isIntOrIntVectorTy() || T2->isIntOrIntVectorTy()))
 676         return false;
 677     }
 678
 679     if (!Config.VectorizeFloats
 680         && (T1->isFPOrFPVectorTy() || T2->isFPOrFPVectorTy()))
 681       return false;
 682
 683     // Don't vectorize target-specific types.
 684     if (T1->isX86_FP80Ty() || T1->isPPC_FP128Ty() || T1->isX86_MMXTy())
 685       return false;
 686     if (T2->isX86_FP80Ty() || T2->isPPC_FP128Ty() || T2->isX86_MMXTy())
 687       return false;
 688
 689     if ((!Config.VectorizePointers || TD == 0) &&
 690         (T1->getScalarType()->isPointerTy() ||
 691          T2->getScalarType()->isPointerTy()))
 692       return false;
 693
 694     if (T1->getPrimitiveSizeInBits() >= Config.VectorBits ||
 695         T2->getPrimitiveSizeInBits() >= Config.VectorBits)
 696       return false;
 697
 698     return true;
 699   }
 700
 701   // This function returns true if the two provided instructions are compatible
 702   // (meaning that they can be fused into a vector instruction). This assumes
 703   // that I has already been determined to be vectorizable and that J is not
 704   // in the use tree of I.
 705   bool BBVectorize::areInstsCompatible(Instruction *I, Instruction *J,
 706                        bool IsSimpleLoadStore, bool NonPow2Len) {
 707     DEBUG(if (DebugInstructionExamination) dbgs() << "BBV: looking at " << *I <<
 708                      " <-> " << *J << "\n");
 709
 710     // Loads and stores can be merged if they have different alignments,
 711     // but are otherwise the same.
 712     if (!J->isSameOperationAs(I, Instruction::CompareIgnoringAlignment |
 713                       (NonPow2Len ? Instruction::CompareUsingScalarTypes : 0)))
 714       return false;
 715
 716     Type *IT1, *IT2, *JT1, *JT2;
 717     getInstructionTypes(I, IT1, IT2);
 718     getInstructionTypes(J, JT1, JT2);
 719     unsigned MaxTypeBits = std::max(
 720       IT1->getPrimitiveSizeInBits() + JT1->getPrimitiveSizeInBits(),
 721       IT2->getPrimitiveSizeInBits() + JT2->getPrimitiveSizeInBits());
 722     if (MaxTypeBits > Config.VectorBits)
 723       return false;
 724
 725     // FIXME: handle addsub-type operations!
 726
 727     if (IsSimpleLoadStore) {
 728       Value *IPtr, *JPtr;
 729       unsigned IAlignment, JAlignment;
 730       int64_t OffsetInElmts = 0;
 731       if (getPairPtrInfo(I, J, IPtr, JPtr, IAlignment, JAlignment,
 732             OffsetInElmts) && abs64(OffsetInElmts) == 1) {
 733         if (Config.AlignedOnly) {
 734           Type *aTypeI = isa<StoreInst>(I) ?
 735             cast<StoreInst>(I)->getValueOperand()->getType() : I->getType();
 736           Type *aTypeJ = isa<StoreInst>(J) ?
 737             cast<StoreInst>(J)->getValueOperand()->getType() : J->getType();
 738
 739           // An aligned load or store is possible only if the instruction
 740           // with the lower offset has an alignment suitable for the
 741           // vector type.
 742
 743           unsigned BottomAlignment = IAlignment;
 744           if (OffsetInElmts < 0) BottomAlignment = JAlignment;
 745
 746           Type *VType = getVecTypeForPair(aTypeI, aTypeJ);
 747           unsigned VecAlignment = TD->getPrefTypeAlignment(VType);
 748           if (BottomAlignment < VecAlignment)
 749             return false;
 750         }
 751       } else {
 752         return false;
 753       }
 754     }
 755
 756     // The powi intrinsic is special because only the first argument is
 757     // vectorized, the second arguments must be equal.
 758     CallInst *CI = dyn_cast<CallInst>(I);
 759     Function *FI;
 760     if (CI && (FI = CI->getCalledFunction()) &&
 761         FI->getIntrinsicID() == Intrinsic::powi) {
 762
 763       Value *A1I = CI->getArgOperand(1),
 764             *A1J = cast<CallInst>(J)->getArgOperand(1);
 765       const SCEV *A1ISCEV = SE->getSCEV(A1I),
 766                  *A1JSCEV = SE->getSCEV(A1J);
 767       return (A1ISCEV == A1JSCEV);
 768     }
 769
 770     return true;
 771   }
 772
 773   // Figure out whether or not J uses I and update the users and write-set
 774   // structures associated with I. Specifically, Users represents the set of
 775   // instructions that depend on I. WriteSet represents the set
 776   // of memory locations that are dependent on I. If UpdateUsers is true,
 777   // and J uses I, then Users is updated to contain J and WriteSet is updated
 778   // to contain any memory locations to which J writes. The function returns
 779   // true if J uses I. By default, alias analysis is used to determine
 780   // whether J reads from memory that overlaps with a location in WriteSet.
 781   // If LoadMoveSet is not null, then it is a previously-computed multimap
 782   // where the key is the memory-based user instruction and the value is
 783   // the instruction to be compared with I. So, if LoadMoveSet is provided,
 784   // then the alias analysis is not used. This is necessary because this
 785   // function is called during the process of moving instructions during
 786   // vectorization and the results of the alias analysis are not stable during
 787   // that process.
 788   bool BBVectorize::trackUsesOfI(DenseSet<Value *> &Users,
 789                        AliasSetTracker &WriteSet, Instruction *I,
 790                        Instruction *J, bool UpdateUsers,
 791                        std::multimap<Value *, Value *> *LoadMoveSet) {
 792     bool UsesI = false;
 793
 794     // This instruction may already be marked as a user due, for example, to
 795     // being a member of a selected pair.
 796     if (Users.count(J))
 797       UsesI = true;
 798
 799     if (!UsesI)
 800       for (User::op_iterator JU = J->op_begin(), JE = J->op_end();
 801            JU != JE; ++JU) {
 802         Value *V = *JU;
 803         if (I == V || Users.count(V)) {
 804           UsesI = true;
 805           break;
 806         }
 807       }
 808     if (!UsesI && J->mayReadFromMemory()) {
 809       if (LoadMoveSet) {
 810         VPIteratorPair JPairRange = LoadMoveSet->equal_range(J);
 811         UsesI = isSecondInIteratorPair<Value*>(I, JPairRange);
 812       } else {
 813         for (AliasSetTracker::iterator W = WriteSet.begin(),
 814              WE = WriteSet.end(); W != WE; ++W) {
 815           if (W->aliasesUnknownInst(J, *AA)) {
 816             UsesI = true;
 817             break;
 818           }
 819         }
 820       }
 821     }
 822
 823     if (UsesI && UpdateUsers) {
 824       if (J->mayWriteToMemory()) WriteSet.add(J);
 825       Users.insert(J);
 826     }
 827
 828     return UsesI;
 829   }
 830
 831   // This function iterates over all instruction pairs in the provided
 832   // basic block and collects all candidate pairs for vectorization.
 833   bool BBVectorize::getCandidatePairs(BasicBlock &BB,
 834                        BasicBlock::iterator &Start,
 835                        std::multimap<Value *, Value *> &CandidatePairs,
 836                        std::vector<Value *> &PairableInsts, bool NonPow2Len) {
 837     BasicBlock::iterator E = BB.end();
 838     if (Start == E) return false;
 839
 840     bool ShouldContinue = false, IAfterStart = false;
 841     for (BasicBlock::iterator I = Start++; I != E; ++I) {
 842       if (I == Start) IAfterStart = true;
 843
 844       bool IsSimpleLoadStore;
 845       if (!isInstVectorizable(I, IsSimpleLoadStore)) continue;
 846
 847       // Look for an instruction with which to pair instruction *I...
 848       DenseSet<Value *> Users;
 849       AliasSetTracker WriteSet(*AA);
 850       bool JAfterStart = IAfterStart;
 851       BasicBlock::iterator J = llvm::next(I);
 852       for (unsigned ss = 0; J != E && ss <= Config.SearchLimit; ++J, ++ss) {
 853         if (J == Start) JAfterStart = true;
 854
 855         // Determine if J uses I, if so, exit the loop.
 856         bool UsesI = trackUsesOfI(Users, WriteSet, I, J, !Config.FastDep);
 857         if (Config.FastDep) {
 858           // Note: For this heuristic to be effective, independent operations
 859           // must tend to be intermixed. This is likely to be true from some
 860           // kinds of grouped loop unrolling (but not the generic LLVM pass),
 861           // but otherwise may require some kind of reordering pass.
 862
 863           // When using fast dependency analysis,
 864           // stop searching after first use:
 865           if (UsesI) break;
 866         } else {
 867           if (UsesI) continue;
 868         }
 869
 870         // J does not use I, and comes before the first use of I, so it can be
 871         // merged with I if the instructions are compatible.
 872         if (!areInstsCompatible(I, J, IsSimpleLoadStore, NonPow2Len)) continue;
 873
 874         // J is a candidate for merging with I.
 875         if (!PairableInsts.size() ||
 876              PairableInsts[PairableInsts.size()-1] != I) {
 877           PairableInsts.push_back(I);
 878         }
 879
 880         CandidatePairs.insert(ValuePair(I, J));
 881
 882         // The next call to this function must start after the last instruction
 883         // selected during this invocation.
 884         if (JAfterStart) {
 885           Start = llvm::next(J);
 886           IAfterStart = JAfterStart = false;
 887         }
 888
 889         DEBUG(if (DebugCandidateSelection) dbgs() << "BBV: candidate pair "
 890                      << *I << " <-> " << *J << "\n");
 891
 892         // If we have already found too many pairs, break here and this function
 893         // will be called again starting after the last instruction selected
 894         // during this invocation.
 895         if (PairableInsts.size() >= Config.MaxInsts) {
 896           ShouldContinue = true;
 897           break;
 898         }
 899       }
 900
 901       if (ShouldContinue)
 902         break;
 903     }
 904
 905     DEBUG(dbgs() << "BBV: found " << PairableInsts.size()
 906            << " instructions with candidate pairs\n");
 907
 908     return ShouldContinue;
 909   }
 910
 911   // Finds candidate pairs connected to the pair P = <PI, PJ>. This means that
 912   // it looks for pairs such that both members have an input which is an
 913   // output of PI or PJ.
 914   void BBVectorize::computePairsConnectedTo(
 915                       std::multimap<Value *, Value *> &CandidatePairs,
 916                       std::vector<Value *> &PairableInsts,
 917                       std::multimap<ValuePair, ValuePair> &ConnectedPairs,
 918                       ValuePair P) {
 919     StoreInst *SI, *SJ;
 920
 921     // For each possible pairing for this variable, look at the uses of
 922     // the first value...
 923     for (Value::use_iterator I = P.first->use_begin(),
 924          E = P.first->use_end(); I != E; ++I) {
 925       if (isa<LoadInst>(*I)) {
 926         // A pair cannot be connected to a load because the load only takes one
 927         // operand (the address) and it is a scalar even after vectorization.
 928         continue;
 929       } else if ((SI = dyn_cast<StoreInst>(*I)) &&
 930                  P.first == SI->getPointerOperand()) {
 931         // Similarly, a pair cannot be connected to a store through its
 932         // pointer operand.
 933         continue;
 934       }
 935
 936       VPIteratorPair IPairRange = CandidatePairs.equal_range(*I);
 937
 938       // For each use of the first variable, look for uses of the second
 939       // variable...
 940       for (Value::use_iterator J = P.second->use_begin(),
 941            E2 = P.second->use_end(); J != E2; ++J) {
 942         if ((SJ = dyn_cast<StoreInst>(*J)) &&
 943             P.second == SJ->getPointerOperand())
 944           continue;
 945
 946         VPIteratorPair JPairRange = CandidatePairs.equal_range(*J);
 947
 948         // Look for <I, J>:
 949         if (isSecondInIteratorPair<Value*>(*J, IPairRange))
 950           ConnectedPairs.insert(VPPair(P, ValuePair(*I, *J)));
 951
 952         // Look for <J, I>:
 953         if (isSecondInIteratorPair<Value*>(*I, JPairRange))
 954           ConnectedPairs.insert(VPPair(P, ValuePair(*J, *I)));
 955       }
 956
 957       if (Config.SplatBreaksChain) continue;
 958       // Look for cases where just the first value in the pair is used by
 959       // both members of another pair (splatting).
 960       for (Value::use_iterator J = P.first->use_begin(); J != E; ++J) {
 961         if ((SJ = dyn_cast<StoreInst>(*J)) &&
 962             P.first == SJ->getPointerOperand())
 963           continue;
 964
 965         if (isSecondInIteratorPair<Value*>(*J, IPairRange))
 966           ConnectedPairs.insert(VPPair(P, ValuePair(*I, *J)));
 967       }
 968     }
 969
 970     if (Config.SplatBreaksChain) return;
 971     // Look for cases where just the second value in the pair is used by
 972     // both members of another pair (splatting).
 973     for (Value::use_iterator I = P.second->use_begin(),
 974          E = P.second->use_end(); I != E; ++I) {
 975       if (isa<LoadInst>(*I))
 976         continue;
 977       else if ((SI = dyn_cast<StoreInst>(*I)) &&
 978                P.second == SI->getPointerOperand())
 979         continue;
 980
 981       VPIteratorPair IPairRange = CandidatePairs.equal_range(*I);
 982
 983       for (Value::use_iterator J = P.second->use_begin(); J != E; ++J) {
 984         if ((SJ = dyn_cast<StoreInst>(*J)) &&
 985             P.second == SJ->getPointerOperand())
 986           continue;
 987
 988         if (isSecondInIteratorPair<Value*>(*J, IPairRange))
 989           ConnectedPairs.insert(VPPair(P, ValuePair(*I, *J)));
 990       }
 991     }
 992   }
 993
 994   // This function figures out which pairs are connected.  Two pairs are
 995   // connected if some output of the first pair forms an input to both members
 996   // of the second pair.
 997   void BBVectorize::computeConnectedPairs(
 998                       std::multimap<Value *, Value *> &CandidatePairs,
 999                       std::vector<Value *> &PairableInsts,
1000                       std::multimap<ValuePair, ValuePair> &ConnectedPairs) {
1001
1002     for (std::vector<Value *>::iterator PI = PairableInsts.begin(),
1003          PE = PairableInsts.end(); PI != PE; ++PI) {
1004       VPIteratorPair choiceRange = CandidatePairs.equal_range(*PI);
1005
1006       for (std::multimap<Value *, Value *>::iterator P = choiceRange.first;
1007            P != choiceRange.second; ++P)
1008         computePairsConnectedTo(CandidatePairs, PairableInsts,
1009                                 ConnectedPairs, *P);
1010     }
1011
1012     DEBUG(dbgs() << "BBV: found " << ConnectedPairs.size()
1013                  << " pair connections.\n");
1014   }
1015
1016   // This function builds a set of use tuples such that <A, B> is in the set
1017   // if B is in the use tree of A. If B is in the use tree of A, then B
1018   // depends on the output of A.
1019   void BBVectorize::buildDepMap(
1020                       BasicBlock &BB,
1021                       std::multimap<Value *, Value *> &CandidatePairs,
1022                       std::vector<Value *> &PairableInsts,
1023                       DenseSet<ValuePair> &PairableInstUsers) {
1024     DenseSet<Value *> IsInPair;
1025     for (std::multimap<Value *, Value *>::iterator C = CandidatePairs.begin(),
1026          E = CandidatePairs.end(); C != E; ++C) {
1027       IsInPair.insert(C->first);
1028       IsInPair.insert(C->second);
1029     }
1030
1031     // Iterate through the basic block, recording all Users of each
1032     // pairable instruction.
1033
1034     BasicBlock::iterator E = BB.end();
1035     for (BasicBlock::iterator I = BB.getFirstInsertionPt(); I != E; ++I) {
1036       if (IsInPair.find(I) == IsInPair.end()) continue;
1037
1038       DenseSet<Value *> Users;
1039       AliasSetTracker WriteSet(*AA);
1040       for (BasicBlock::iterator J = llvm::next(I); J != E; ++J)
1041         (void) trackUsesOfI(Users, WriteSet, I, J);
1042
1043       for (DenseSet<Value *>::iterator U = Users.begin(), E = Users.end();
1044            U != E; ++U)
1045         PairableInstUsers.insert(ValuePair(I, *U));
1046     }
1047   }
1048
1049   // Returns true if an input to pair P is an output of pair Q and also an
1050   // input of pair Q is an output of pair P. If this is the case, then these
1051   // two pairs cannot be simultaneously fused.
1052   bool BBVectorize::pairsConflict(ValuePair P, ValuePair Q,
1053                      DenseSet<ValuePair> &PairableInstUsers,
1054                      std::multimap<ValuePair, ValuePair> *PairableInstUserMap) {
1055     // Two pairs are in conflict if they are mutual Users of eachother.
1056     bool QUsesP = PairableInstUsers.count(ValuePair(P.first,  Q.first))  ||
1057                   PairableInstUsers.count(ValuePair(P.first,  Q.second)) ||
1058                   PairableInstUsers.count(ValuePair(P.second, Q.first))  ||
1059                   PairableInstUsers.count(ValuePair(P.second, Q.second));
1060     bool PUsesQ = PairableInstUsers.count(ValuePair(Q.first,  P.first))  ||
1061                   PairableInstUsers.count(ValuePair(Q.first,  P.second)) ||
1062                   PairableInstUsers.count(ValuePair(Q.second, P.first))  ||
1063                   PairableInstUsers.count(ValuePair(Q.second, P.second));
1064     if (PairableInstUserMap) {
1065       // FIXME: The expensive part of the cycle check is not so much the cycle
1066       // check itself but this edge insertion procedure. This needs some
1067       // profiling and probably a different data structure (same is true of
1068       // most uses of std::multimap).
1069       if (PUsesQ) {
1070         VPPIteratorPair QPairRange = PairableInstUserMap->equal_range(Q);
1071         if (!isSecondInIteratorPair(P, QPairRange))
1072           PairableInstUserMap->insert(VPPair(Q, P));
1073       }
1074       if (QUsesP) {
1075         VPPIteratorPair PPairRange = PairableInstUserMap->equal_range(P);
1076         if (!isSecondInIteratorPair(Q, PPairRange))
1077           PairableInstUserMap->insert(VPPair(P, Q));
1078       }
1079     }
1080
1081     return (QUsesP && PUsesQ);
1082   }
1083
1084   // This function walks the use graph of current pairs to see if, starting
1085   // from P, the walk returns to P.
1086   bool BBVectorize::pairWillFormCycle(ValuePair P,
1087                        std::multimap<ValuePair, ValuePair> &PairableInstUserMap,
1088                        DenseSet<ValuePair> &CurrentPairs) {
1089     DEBUG(if (DebugCycleCheck)
1090             dbgs() << "BBV: starting cycle check for : " << *P.first << " <-> "
1091                    << *P.second << "\n");
1092     // A lookup table of visisted pairs is kept because the PairableInstUserMap
1093     // contains non-direct associations.
1094     DenseSet<ValuePair> Visited;
1095     SmallVector<ValuePair, 32> Q;
1096     // General depth-first post-order traversal:
1097     Q.push_back(P);
1098     do {
1099       ValuePair QTop = Q.pop_back_val();
1100       Visited.insert(QTop);
1101
1102       DEBUG(if (DebugCycleCheck)
1103               dbgs() << "BBV: cycle check visiting: " << *QTop.first << " <-> "
1104                      << *QTop.second << "\n");
1105       VPPIteratorPair QPairRange = PairableInstUserMap.equal_range(QTop);
1106       for (std::multimap<ValuePair, ValuePair>::iterator C = QPairRange.first;
1107            C != QPairRange.second; ++C) {
1108         if (C->second == P) {
1109           DEBUG(dbgs()
1110                  << "BBV: rejected to prevent non-trivial cycle formation: "
1111                  << *C->first.first << " <-> " << *C->first.second << "\n");
1112           return true;
1113         }
1114
1115         if (CurrentPairs.count(C->second) && !Visited.count(C->second))
1116           Q.push_back(C->second);
1117       }
1118     } while (!Q.empty());
1119
1120     return false;
1121   }
1122
1123   // This function builds the initial tree of connected pairs with the
1124   // pair J at the root.
1125   void BBVectorize::buildInitialTreeFor(
1126                       std::multimap<Value *, Value *> &CandidatePairs,
1127                       std::vector<Value *> &PairableInsts,
1128                       std::multimap<ValuePair, ValuePair> &ConnectedPairs,
1129                       DenseSet<ValuePair> &PairableInstUsers,
1130                       DenseMap<Value *, Value *> &ChosenPairs,
1131                       DenseMap<ValuePair, size_t> &Tree, ValuePair J) {
1132     // Each of these pairs is viewed as the root node of a Tree. The Tree
1133     // is then walked (depth-first). As this happens, we keep track of
1134     // the pairs that compose the Tree and the maximum depth of the Tree.
1135     SmallVector<ValuePairWithDepth, 32> Q;
1136     // General depth-first post-order traversal:
1137     Q.push_back(ValuePairWithDepth(J, getDepthFactor(J.first)));
1138     do {
1139       ValuePairWithDepth QTop = Q.back();
1140
1141       // Push each child onto the queue:
1142       bool MoreChildren = false;
1143       size_t MaxChildDepth = QTop.second;
1144       VPPIteratorPair qtRange = ConnectedPairs.equal_range(QTop.first);
1145       for (std::multimap<ValuePair, ValuePair>::iterator k = qtRange.first;
1146            k != qtRange.second; ++k) {
1147         // Make sure that this child pair is still a candidate:
1148         bool IsStillCand = false;
1149         VPIteratorPair checkRange =
1150           CandidatePairs.equal_range(k->second.first);
1151         for (std::multimap<Value *, Value *>::iterator m = checkRange.first;
1152              m != checkRange.second; ++m) {
1153           if (m->second == k->second.second) {
1154             IsStillCand = true;
1155             break;
1156           }
1157         }
1158
1159         if (IsStillCand) {
1160           DenseMap<ValuePair, size_t>::iterator C = Tree.find(k->second);
1161           if (C == Tree.end()) {
1162             size_t d = getDepthFactor(k->second.first);
1163             Q.push_back(ValuePairWithDepth(k->second, QTop.second+d));
1164             MoreChildren = true;
1165           } else {
1166             MaxChildDepth = std::max(MaxChildDepth, C->second);
1167           }
1168         }
1169       }
1170
1171       if (!MoreChildren) {
1172         // Record the current pair as part of the Tree:
1173         Tree.insert(ValuePairWithDepth(QTop.first, MaxChildDepth));
1174         Q.pop_back();
1175       }
1176     } while (!Q.empty());
1177   }
1178
1179   // Given some initial tree, prune it by removing conflicting pairs (pairs
1180   // that cannot be simultaneously chosen for vectorization).
1181   void BBVectorize::pruneTreeFor(
1182                       std::multimap<Value *, Value *> &CandidatePairs,
1183                       std::vector<Value *> &PairableInsts,
1184                       std::multimap<ValuePair, ValuePair> &ConnectedPairs,
1185                       DenseSet<ValuePair> &PairableInstUsers,
1186                       std::multimap<ValuePair, ValuePair> &PairableInstUserMap,
1187                       DenseMap<Value *, Value *> &ChosenPairs,
1188                       DenseMap<ValuePair, size_t> &Tree,
1189                       DenseSet<ValuePair> &PrunedTree, ValuePair J,
1190                       bool UseCycleCheck) {
1191     SmallVector<ValuePairWithDepth, 32> Q;
1192     // General depth-first post-order traversal:
1193     Q.push_back(ValuePairWithDepth(J, getDepthFactor(J.first)));
1194     do {
1195       ValuePairWithDepth QTop = Q.pop_back_val();
1196       PrunedTree.insert(QTop.first);
1197
1198       // Visit each child, pruning as necessary...
1199       DenseMap<ValuePair, size_t> BestChildren;
1200       VPPIteratorPair QTopRange = ConnectedPairs.equal_range(QTop.first);
1201       for (std::multimap<ValuePair, ValuePair>::iterator K = QTopRange.first;
1202            K != QTopRange.second; ++K) {
1203         DenseMap<ValuePair, size_t>::iterator C = Tree.find(K->second);
1204         if (C == Tree.end()) continue;
1205
1206         // This child is in the Tree, now we need to make sure it is the
1207         // best of any conflicting children. There could be multiple
1208         // conflicting children, so first, determine if we're keeping
1209         // this child, then delete conflicting children as necessary.
1210
1211         // It is also necessary to guard against pairing-induced
1212         // dependencies. Consider instructions a .. x .. y .. b
1213         // such that (a,b) are to be fused and (x,y) are to be fused
1214         // but a is an input to x and b is an output from y. This
1215         // means that y cannot be moved after b but x must be moved
1216         // after b for (a,b) to be fused. In other words, after
1217         // fusing (a,b) we have y .. a/b .. x where y is an input
1218         // to a/b and x is an output to a/b: x and y can no longer
1219         // be legally fused. To prevent this condition, we must
1220         // make sure that a child pair added to the Tree is not
1221         // both an input and output of an already-selected pair.
1222
1223         // Pairing-induced dependencies can also form from more complicated
1224         // cycles. The pair vs. pair conflicts are easy to check, and so
1225         // that is done explicitly for "fast rejection", and because for
1226         // child vs. child conflicts, we may prefer to keep the current
1227         // pair in preference to the already-selected child.
1228         DenseSet<ValuePair> CurrentPairs;
1229
1230         bool CanAdd = true;
1231         for (DenseMap<ValuePair, size_t>::iterator C2
1232               = BestChildren.begin(), E2 = BestChildren.end();
1233              C2 != E2; ++C2) {
1234           if (C2->first.first == C->first.first ||
1235               C2->first.first == C->first.second ||
1236               C2->first.second == C->first.first ||
1237               C2->first.second == C->first.second ||
1238               pairsConflict(C2->first, C->first, PairableInstUsers,
1239                             UseCycleCheck ? &PairableInstUserMap : 0)) {
1240             if (C2->second >= C->second) {
1241               CanAdd = false;
1242               break;
1243             }
1244
1245             CurrentPairs.insert(C2->first);
1246           }
1247         }
1248         if (!CanAdd) continue;
1249
1250         // Even worse, this child could conflict with another node already
1251         // selected for the Tree. If that is the case, ignore this child.
1252         for (DenseSet<ValuePair>::iterator T = PrunedTree.begin(),
1253              E2 = PrunedTree.end(); T != E2; ++T) {
1254           if (T->first == C->first.first ||
1255               T->first == C->first.second ||
1256               T->second == C->first.first ||
1257               T->second == C->first.second ||
1258               pairsConflict(*T, C->first, PairableInstUsers,
1259                             UseCycleCheck ? &PairableInstUserMap : 0)) {
1260             CanAdd = false;
1261             break;
1262           }
1263
1264           CurrentPairs.insert(*T);
1265         }
1266         if (!CanAdd) continue;
1267
1268         // And check the queue too...
1269         for (SmallVector<ValuePairWithDepth, 32>::iterator C2 = Q.begin(),
1270              E2 = Q.end(); C2 != E2; ++C2) {
1271           if (C2->first.first == C->first.first ||
1272               C2->first.first == C->first.second ||
1273               C2->first.second == C->first.first ||
1274               C2->first.second == C->first.second ||
1275               pairsConflict(C2->first, C->first, PairableInstUsers,
1276                             UseCycleCheck ? &PairableInstUserMap : 0)) {
1277             CanAdd = false;
1278             break;
1279           }
1280
1281           CurrentPairs.insert(C2->first);
1282         }
1283         if (!CanAdd) continue;
1284
1285         // Last but not least, check for a conflict with any of the
1286         // already-chosen pairs.
1287         for (DenseMap<Value *, Value *>::iterator C2 =
1288               ChosenPairs.begin(), E2 = ChosenPairs.end();
1289              C2 != E2; ++C2) {
1290           if (pairsConflict(*C2, C->first, PairableInstUsers,
1291                             UseCycleCheck ? &PairableInstUserMap : 0)) {
1292             CanAdd = false;
1293             break;
1294           }
1295
1296           CurrentPairs.insert(*C2);
1297         }
1298         if (!CanAdd) continue;
1299
1300         // To check for non-trivial cycles formed by the addition of the
1301         // current pair we've formed a list of all relevant pairs, now use a
1302         // graph walk to check for a cycle. We start from the current pair and
1303         // walk the use tree to see if we again reach the current pair. If we
1304         // do, then the current pair is rejected.
1305
1306         // FIXME: It may be more efficient to use a topological-ordering
1307         // algorithm to improve the cycle check. This should be investigated.
1308         if (UseCycleCheck &&
1309             pairWillFormCycle(C->first, PairableInstUserMap, CurrentPairs))
1310           continue;
1311
1312         // This child can be added, but we may have chosen it in preference
1313         // to an already-selected child. Check for this here, and if a
1314         // conflict is found, then remove the previously-selected child
1315         // before adding this one in its place.
1316         for (DenseMap<ValuePair, size_t>::iterator C2
1317               = BestChildren.begin(); C2 != BestChildren.end();) {
1318           if (C2->first.first == C->first.first ||
1319               C2->first.first == C->first.second ||
1320               C2->first.second == C->first.first ||
1321               C2->first.second == C->first.second ||
1322               pairsConflict(C2->first, C->first, PairableInstUsers))
1323             BestChildren.erase(C2++);
1324           else
1325             ++C2;
1326         }
1327
1328         BestChildren.insert(ValuePairWithDepth(C->first, C->second));
1329       }
1330
1331       for (DenseMap<ValuePair, size_t>::iterator C
1332             = BestChildren.begin(), E2 = BestChildren.end();
1333            C != E2; ++C) {
1334         size_t DepthF = getDepthFactor(C->first.first);
1335         Q.push_back(ValuePairWithDepth(C->first, QTop.second+DepthF));
1336       }
1337     } while (!Q.empty());
1338   }
1339
1340   // This function finds the best tree of mututally-compatible connected
1341   // pairs, given the choice of root pairs as an iterator range.
1342   void BBVectorize::findBestTreeFor(
1343                       std::multimap<Value *, Value *> &CandidatePairs,
1344                       std::vector<Value *> &PairableInsts,
1345                       std::multimap<ValuePair, ValuePair> &ConnectedPairs,
1346                       DenseSet<ValuePair> &PairableInstUsers,
1347                       std::multimap<ValuePair, ValuePair> &PairableInstUserMap,
1348                       DenseMap<Value *, Value *> &ChosenPairs,
1349                       DenseSet<ValuePair> &BestTree, size_t &BestMaxDepth,
1350                       size_t &BestEffSize, VPIteratorPair ChoiceRange,
1351                       bool UseCycleCheck) {
1352     for (std::multimap<Value *, Value *>::iterator J = ChoiceRange.first;
1353          J != ChoiceRange.second; ++J) {
1354
1355       // Before going any further, make sure that this pair does not
1356       // conflict with any already-selected pairs (see comment below
1357       // near the Tree pruning for more details).
1358       DenseSet<ValuePair> ChosenPairSet;
1359       bool DoesConflict = false;
1360       for (DenseMap<Value *, Value *>::iterator C = ChosenPairs.begin(),
1361            E = ChosenPairs.end(); C != E; ++C) {
1362         if (pairsConflict(*C, *J, PairableInstUsers,
1363                           UseCycleCheck ? &PairableInstUserMap : 0)) {
1364           DoesConflict = true;
1365           break;
1366         }
1367
1368         ChosenPairSet.insert(*C);
1369       }
1370       if (DoesConflict) continue;
1371
1372       if (UseCycleCheck &&
1373           pairWillFormCycle(*J, PairableInstUserMap, ChosenPairSet))
1374         continue;
1375
1376       DenseMap<ValuePair, size_t> Tree;
1377       buildInitialTreeFor(CandidatePairs, PairableInsts, ConnectedPairs,
1378                           PairableInstUsers, ChosenPairs, Tree, *J);
1379
1380       // Because we'll keep the child with the largest depth, the largest
1381       // depth is still the same in the unpruned Tree.
1382       size_t MaxDepth = Tree.lookup(*J);
1383
1384       DEBUG(if (DebugPairSelection) dbgs() << "BBV: found Tree for pair {"
1385                    << *J->first << " <-> " << *J->second << "} of depth " <<
1386                    MaxDepth << " and size " << Tree.size() << "\n");
1387
1388       // At this point the Tree has been constructed, but, may contain
1389       // contradictory children (meaning that different children of
1390       // some tree node may be attempting to fuse the same instruction).
1391       // So now we walk the tree again, in the case of a conflict,
1392       // keep only the child with the largest depth. To break a tie,
1393       // favor the first child.
1394
1395       DenseSet<ValuePair> PrunedTree;
1396       pruneTreeFor(CandidatePairs, PairableInsts, ConnectedPairs,
1397                    PairableInstUsers, PairableInstUserMap, ChosenPairs, Tree,
1398                    PrunedTree, *J, UseCycleCheck);
1399
1400       size_t EffSize = 0;
1401       for (DenseSet<ValuePair>::iterator S = PrunedTree.begin(),
1402            E = PrunedTree.end(); S != E; ++S)
1403         EffSize += getDepthFactor(S->first);
1404
1405       DEBUG(if (DebugPairSelection)
1406              dbgs() << "BBV: found pruned Tree for pair {"
1407              << *J->first << " <-> " << *J->second << "} of depth " <<
1408              MaxDepth << " and size " << PrunedTree.size() <<
1409             " (effective size: " << EffSize << ")\n");
1410       if (MaxDepth >= Config.ReqChainDepth && EffSize > BestEffSize) {
1411         BestMaxDepth = MaxDepth;
1412         BestEffSize = EffSize;
1413         BestTree = PrunedTree;
1414       }
1415     }
1416   }
1417
1418   // Given the list of candidate pairs, this function selects those
1419   // that will be fused into vector instructions.
1420   void BBVectorize::choosePairs(
1421                       std::multimap<Value *, Value *> &CandidatePairs,
1422                       std::vector<Value *> &PairableInsts,
1423                       std::multimap<ValuePair, ValuePair> &ConnectedPairs,
1424                       DenseSet<ValuePair> &PairableInstUsers,
1425                       DenseMap<Value *, Value *>& ChosenPairs) {
1426     bool UseCycleCheck =
1427      CandidatePairs.size() <= Config.MaxCandPairsForCycleCheck;
1428     std::multimap<ValuePair, ValuePair> PairableInstUserMap;
1429     for (std::vector<Value *>::iterator I = PairableInsts.begin(),
1430          E = PairableInsts.end(); I != E; ++I) {
1431       // The number of possible pairings for this variable:
1432       size_t NumChoices = CandidatePairs.count(*I);
1433       if (!NumChoices) continue;
1434
1435       VPIteratorPair ChoiceRange = CandidatePairs.equal_range(*I);
1436
1437       // The best pair to choose and its tree:
1438       size_t BestMaxDepth = 0, BestEffSize = 0;
1439       DenseSet<ValuePair> BestTree;
1440       findBestTreeFor(CandidatePairs, PairableInsts, ConnectedPairs,
1441                       PairableInstUsers, PairableInstUserMap, ChosenPairs,
1442                       BestTree, BestMaxDepth, BestEffSize, ChoiceRange,
1443                       UseCycleCheck);
1444
1445       // A tree has been chosen (or not) at this point. If no tree was
1446       // chosen, then this instruction, I, cannot be paired (and is no longer
1447       // considered).
1448
1449       DEBUG(if (BestTree.size() > 0)
1450               dbgs() << "BBV: selected pairs in the best tree for: "
1451                      << *cast<Instruction>(*I) << "\n");
1452
1453       for (DenseSet<ValuePair>::iterator S = BestTree.begin(),
1454            SE2 = BestTree.end(); S != SE2; ++S) {
1455         // Insert the members of this tree into the list of chosen pairs.
1456         ChosenPairs.insert(ValuePair(S->first, S->second));
1457         DEBUG(dbgs() << "BBV: selected pair: " << *S->first << " <-> " <<
1458                *S->second << "\n");
1459
1460         // Remove all candidate pairs that have values in the chosen tree.
1461         for (std::multimap<Value *, Value *>::iterator K =
1462                CandidatePairs.begin(); K != CandidatePairs.end();) {
1463           if (K->first == S->first || K->second == S->first ||
1464               K->second == S->second || K->first == S->second) {
1465             // Don't remove the actual pair chosen so that it can be used
1466             // in subsequent tree selections.
1467             if (!(K->first == S->first && K->second == S->second))
1468               CandidatePairs.erase(K++);
1469             else
1470               ++K;
1471           } else {
1472             ++K;
1473           }
1474         }
1475       }
1476     }
1477
1478     DEBUG(dbgs() << "BBV: selected " << ChosenPairs.size() << " pairs.\n");
1479   }
1480
1481   std::string getReplacementName(Instruction *I, bool IsInput, unsigned o,
1482                      unsigned n = 0) {
1483     if (!I->hasName())
1484       return "";
1485
1486     return (I->getName() + (IsInput ? ".v.i" : ".v.r") + utostr(o) +
1487              (n > 0 ? "." + utostr(n) : "")).str();
1488   }
1489
1490   // Returns the value that is to be used as the pointer input to the vector
1491   // instruction that fuses I with J.
1492   Value *BBVectorize::getReplacementPointerInput(LLVMContext& Context,
1493                      Instruction *I, Instruction *J, unsigned o,
1494                      bool FlipMemInputs) {
1495     Value *IPtr, *JPtr;
1496     unsigned IAlignment, JAlignment;
1497     int64_t OffsetInElmts;
1498
1499     // Note: the analysis might fail here, that is why FlipMemInputs has
1500     // been precomputed (OffsetInElmts must be unused here).
1501     (void) getPairPtrInfo(I, J, IPtr, JPtr, IAlignment, JAlignment,
1502                           OffsetInElmts);
1503
1504     // The pointer value is taken to be the one with the lowest offset.
1505     Value *VPtr;
1506     if (!FlipMemInputs) {
1507       VPtr = IPtr;
1508     } else {
1509       VPtr = JPtr;
1510     }
1511
1512     Type *ArgTypeI = cast<PointerType>(IPtr->getType())->getElementType();
1513     Type *ArgTypeJ = cast<PointerType>(JPtr->getType())->getElementType();
1514     Type *VArgType = getVecTypeForPair(ArgTypeI, ArgTypeJ);
1515     Type *VArgPtrType = PointerType::get(VArgType,
1516       cast<PointerType>(IPtr->getType())->getAddressSpace());
1517     return new BitCastInst(VPtr, VArgPtrType, getReplacementName(I, true, o),
1518                         /* insert before */ FlipMemInputs ? J : I);
1519   }
1520
1521   void BBVectorize::fillNewShuffleMask(LLVMContext& Context, Instruction *J,
1522                      unsigned MaskOffset, unsigned NumInElem,
1523                      unsigned NumInElem1, unsigned IdxOffset,
1524                      std::vector<Constant*> &Mask) {
1525     unsigned NumElem1 = cast<VectorType>(J->getType())->getNumElements();
1526     for (unsigned v = 0; v < NumElem1; ++v) {
1527       int m = cast<ShuffleVectorInst>(J)->getMaskValue(v);
1528       if (m < 0) {
1529         Mask[v+MaskOffset] = UndefValue::get(Type::getInt32Ty(Context));
1530       } else {
1531         unsigned mm = m + (int) IdxOffset;
1532         if (m >= (int) NumInElem1)
1533           mm += (int) NumInElem;
1534
1535         Mask[v+MaskOffset] =
1536           ConstantInt::get(Type::getInt32Ty(Context), mm);
1537       }
1538     }
1539   }
1540
1541   // Returns the value that is to be used as the vector-shuffle mask to the
1542   // vector instruction that fuses I with J.
1543   Value *BBVectorize::getReplacementShuffleMask(LLVMContext& Context,
1544                      Instruction *I, Instruction *J) {
1545     // This is the shuffle mask. We need to append the second
1546     // mask to the first, and the numbers need to be adjusted.
1547
1548     Type *ArgTypeI = I->getType();
1549     Type *ArgTypeJ = J->getType();
1550     Type *VArgType = getVecTypeForPair(ArgTypeI, ArgTypeJ);
1551
1552     unsigned NumElemI = cast<VectorType>(ArgTypeI)->getNumElements();
1553
1554     // Get the total number of elements in the fused vector type.
1555     // By definition, this must equal the number of elements in
1556     // the final mask.
1557     unsigned NumElem = cast<VectorType>(VArgType)->getNumElements();
1558     std::vector<Constant*> Mask(NumElem);
1559
1560     Type *OpTypeI = I->getOperand(0)->getType();
1561     unsigned NumInElemI = cast<VectorType>(OpTypeI)->getNumElements();
1562     Type *OpTypeJ = J->getOperand(0)->getType();
1563     unsigned NumInElemJ = cast<VectorType>(OpTypeJ)->getNumElements();
1564
1565     // The fused vector will be:
1566     // -----------------------------------------------------
1567     // | NumInElemI | NumInElemJ | NumInElemI | NumInElemJ |
1568     // -----------------------------------------------------
1569     // from which we'll extract NumElem total elements (where the first NumElemI
1570     // of them come from the mask in I and the remainder come from the mask
1571     // in J.
1572
1573     // For the mask from the first pair...
1574     fillNewShuffleMask(Context, I, 0,        NumInElemJ, NumInElemI,
1575                        0,          Mask);
1576
1577     // For the mask from the second pair...
1578     fillNewShuffleMask(Context, J, NumElemI, NumInElemI, NumInElemJ,
1579                        NumInElemI, Mask);
1580
1581     return ConstantVector::get(Mask);
1582   }
1583
1584   bool BBVectorize::expandIEChain(LLVMContext& Context, Instruction *I,
1585                                   Instruction *J, unsigned o, Value *&LOp,
1586                                   unsigned numElemL,
1587                                   Type *ArgTypeL, Type *ArgTypeH,
1588                                   unsigned IdxOff) {
1589     bool ExpandedIEChain = false;
1590     if (InsertElementInst *LIE = dyn_cast<InsertElementInst>(LOp)) {
1591       // If we have a pure insertelement chain, then this can be rewritten
1592       // into a chain that directly builds the larger type.
1593       bool PureChain = true;
1594       InsertElementInst *LIENext = LIE;
1595       do {
1596         if (!isa<UndefValue>(LIENext->getOperand(0)) &&
1597             !isa<InsertElementInst>(LIENext->getOperand(0))) {
1598           PureChain = false;
1599           break;
1600         }
1601       } while ((LIENext =
1602                  dyn_cast<InsertElementInst>(LIENext->getOperand(0))));
1603
1604       if (PureChain) {
1605         SmallVector<Value *, 8> VectElemts(numElemL,
1606           UndefValue::get(ArgTypeL->getScalarType()));
1607         InsertElementInst *LIENext = LIE;
1608         do {
1609           unsigned Idx =
1610             cast<ConstantInt>(LIENext->getOperand(2))->getSExtValue();
1611           VectElemts[Idx] = LIENext->getOperand(1);
1612         } while ((LIENext =
1613                    dyn_cast<InsertElementInst>(LIENext->getOperand(0))));
1614
1615         LIENext = 0;
1616         Value *LIEPrev = UndefValue::get(ArgTypeH);
1617         for (unsigned i = 0; i < numElemL; ++i) {
1618           if (isa<UndefValue>(VectElemts[i])) continue;
1619           LIENext = InsertElementInst::Create(LIEPrev, VectElemts[i],
1620                              ConstantInt::get(Type::getInt32Ty(Context),
1621                                               i + IdxOff),
1622                              getReplacementName(I, true, o, i+1));
1623           LIENext->insertBefore(J);
1624           LIEPrev = LIENext;
1625         }
1626
1627         LOp = LIENext ? (Value*) LIENext : UndefValue::get(ArgTypeH);
1628         ExpandedIEChain = true;
1629       }
1630     }
1631
1632     return ExpandedIEChain;
1633   }
1634
1635   // Returns the value to be used as the specified operand of the vector
1636   // instruction that fuses I with J.
1637   Value *BBVectorize::getReplacementInput(LLVMContext& Context, Instruction *I,
1638                      Instruction *J, unsigned o, bool FlipMemInputs) {
1639     Value *CV0 = ConstantInt::get(Type::getInt32Ty(Context), 0);
1640     Value *CV1 = ConstantInt::get(Type::getInt32Ty(Context), 1);
1641
1642     // Compute the fused vector type for this operand
1643     Type *ArgTypeI = I->getOperand(o)->getType();
1644     Type *ArgTypeJ = J->getOperand(o)->getType();
1645     VectorType *VArgType = getVecTypeForPair(ArgTypeI, ArgTypeJ);
1646
1647     Instruction *L = I, *H = J;
1648     Type *ArgTypeL = ArgTypeI, *ArgTypeH = ArgTypeJ;
1649     if (FlipMemInputs) {
1650       L = J;
1651       H = I;
1652       ArgTypeL = ArgTypeJ;
1653       ArgTypeH = ArgTypeI;
1654     }
1655
1656     unsigned numElemL;
1657     if (ArgTypeL->isVectorTy())
1658       numElemL = cast<VectorType>(ArgTypeL)->getNumElements();
1659     else
1660       numElemL = 1;
1661
1662     unsigned numElemH;
1663     if (ArgTypeH->isVectorTy())
1664       numElemH = cast<VectorType>(ArgTypeH)->getNumElements();
1665     else
1666       numElemH = 1;
1667
1668     Value *LOp = L->getOperand(o);
1669     Value *HOp = H->getOperand(o);
1670     unsigned numElem = VArgType->getNumElements();
1671
1672     // First, we check if we can reuse the "original" vector outputs (if these
1673     // exist). We might need a shuffle.
1674     ExtractElementInst *LEE = dyn_cast<ExtractElementInst>(LOp);
1675     ExtractElementInst *HEE = dyn_cast<ExtractElementInst>(HOp);
1676     ShuffleVectorInst *LSV = dyn_cast<ShuffleVectorInst>(LOp);
1677     ShuffleVectorInst *HSV = dyn_cast<ShuffleVectorInst>(HOp);
1678
1679     // FIXME: If we're fusing shuffle instructions, then we can't apply this
1680     // optimization. The input vectors to the shuffle might be a different
1681     // length from the shuffle outputs. Unfortunately, the replacement
1682     // shuffle mask has already been formed, and the mask entries are sensitive
1683     // to the sizes of the inputs.
1684     bool IsSizeChangeShuffle =
1685       isa<ShuffleVectorInst>(L) &&
1686         (LOp->getType() != L->getType() || HOp->getType() != H->getType());
1687
1688     if ((LEE || LSV) && (HEE || HSV) && !IsSizeChangeShuffle) {
1689       // We can have at most two unique vector inputs.
1690       bool CanUseInputs = true;
1691       Value *I1, *I2 = 0;
1692       if (LEE) {
1693         I1 = LEE->getOperand(0);
1694       } else {
1695         I1 = LSV->getOperand(0);
1696         I2 = LSV->getOperand(1);
1697         if (I2 == I1 || isa<UndefValue>(I2))
1698           I2 = 0;
1699       }
1700
1701       if (HEE) {
1702         Value *I3 = HEE->getOperand(0);
1703         if (!I2 && I3 != I1)
1704           I2 = I3;
1705         else if (I3 != I1 && I3 != I2)
1706           CanUseInputs = false;
1707       } else {
1708         Value *I3 = HSV->getOperand(0);
1709         if (!I2 && I3 != I1)
1710           I2 = I3;
1711         else if (I3 != I1 && I3 != I2)
1712           CanUseInputs = false;
1713
1714         if (CanUseInputs) {
1715           Value *I4 = HSV->getOperand(1);
1716           if (!isa<UndefValue>(I4)) {
1717             if (!I2 && I4 != I1)
1718               I2 = I4;
1719             else if (I4 != I1 && I4 != I2)
1720               CanUseInputs = false;
1721           }
1722         }
1723       }
1724
1725       if (CanUseInputs) {
1726         unsigned LOpElem =
1727           cast<VectorType>(cast<Instruction>(LOp)->getOperand(0)->getType())
1728             ->getNumElements();
1729         unsigned HOpElem =
1730           cast<VectorType>(cast<Instruction>(HOp)->getOperand(0)->getType())
1731             ->getNumElements();
1732
1733         // We have one or two input vectors. We need to map each index of the
1734         // operands to the index of the original vector.
1735         SmallVector<std::pair<int, int>, 8>  II(numElem);
1736         for (unsigned i = 0; i < numElemL; ++i) {
1737           int Idx, INum;
1738           if (LEE) {
1739             Idx =
1740               cast<ConstantInt>(LEE->getOperand(1))->getSExtValue();
1741             INum = LEE->getOperand(0) == I1 ? 0 : 1;
1742           } else {
1743             Idx = LSV->getMaskValue(i);
1744             if (Idx < (int) LOpElem) {
1745               INum = LSV->getOperand(0) == I1 ? 0 : 1;
1746             } else {
1747               Idx -= LOpElem;
1748               INum = LSV->getOperand(1) == I1 ? 0 : 1;
1749             }
1750           }
1751
1752           II[i] = std::pair<int, int>(Idx, INum);
1753         }
1754         for (unsigned i = 0; i < numElemH; ++i) {
1755           int Idx, INum;
1756           if (HEE) {
1757             Idx =
1758               cast<ConstantInt>(HEE->getOperand(1))->getSExtValue();
1759             INum = HEE->getOperand(0) == I1 ? 0 : 1;
1760           } else {
1761             Idx = HSV->getMaskValue(i);
1762             if (Idx < (int) HOpElem) {
1763               INum = HSV->getOperand(0) == I1 ? 0 : 1;
1764             } else {
1765               Idx -= HOpElem;
1766               INum = HSV->getOperand(1) == I1 ? 0 : 1;
1767             }
1768           }
1769
1770           II[i + numElemL] = std::pair<int, int>(Idx, INum);
1771         }
1772
1773         // We now have an array which tells us from which index of which
1774         // input vector each element of the operand comes.
1775         VectorType *I1T = cast<VectorType>(I1->getType());
1776         unsigned I1Elem = I1T->getNumElements();
1777
1778         if (!I2) {
1779           // In this case there is only one underlying vector input. Check for
1780           // the trivial case where we can use the input directly.
1781           if (I1Elem == numElem) {
1782             bool ElemInOrder = true;
1783             for (unsigned i = 0; i < numElem; ++i) {
1784               if (II[i].first != (int) i && II[i].first != -1) {
1785                 ElemInOrder = false;
1786                 break;
1787               }
1788             }
1789
1790             if (ElemInOrder)
1791               return I1;
1792           }
1793
1794           // A shuffle is needed.
1795           std::vector<Constant *> Mask(numElem);
1796           for (unsigned i = 0; i < numElem; ++i) {
1797             int Idx = II[i].first;
1798             if (Idx == -1)
1799               Mask[i] = UndefValue::get(Type::getInt32Ty(Context));
1800             else
1801               Mask[i] = ConstantInt::get(Type::getInt32Ty(Context), Idx);
1802           }
1803
1804           Instruction *S =
1805             new ShuffleVectorInst(I1, UndefValue::get(I1T),
1806                                   ConstantVector::get(Mask),
1807                                   getReplacementName(I, true, o));
1808           S->insertBefore(J);
1809           return S;
1810         }
1811
1812         VectorType *I2T = cast<VectorType>(I2->getType());
1813         unsigned I2Elem = I2T->getNumElements();
1814
1815         // This input comes from two distinct vectors. The first step is to
1816         // make sure that both vectors are the same length. If not, the
1817         // smaller one will need to grow before they can be shuffled together.
1818         if (I1Elem < I2Elem) {
1819           std::vector<Constant *> Mask(I2Elem);
1820           unsigned v = 0;
1821           for (; v < I1Elem; ++v)
1822             Mask[v] = ConstantInt::get(Type::getInt32Ty(Context), v);
1823           for (; v < I2Elem; ++v)
1824             Mask[v] = UndefValue::get(Type::getInt32Ty(Context));
1825
1826           Instruction *NewI1 =
1827             new ShuffleVectorInst(I1, UndefValue::get(I1T),
1828                                   ConstantVector::get(Mask),
1829                                   getReplacementName(I, true, o, 1));
1830           NewI1->insertBefore(J);
1831           I1 = NewI1;
1832           I1T = I2T;
1833           I1Elem = I2Elem;
1834         } else if (I1Elem > I2Elem) {
1835           std::vector<Constant *> Mask(I1Elem);
1836           unsigned v = 0;
1837           for (; v < I2Elem; ++v)
1838             Mask[v] = ConstantInt::get(Type::getInt32Ty(Context), v);
1839           for (; v < I1Elem; ++v)
1840             Mask[v] = UndefValue::get(Type::getInt32Ty(Context));
1841
1842           Instruction *NewI2 =
1843             new ShuffleVectorInst(I2, UndefValue::get(I2T),
1844                                   ConstantVector::get(Mask),
1845                                   getReplacementName(I, true, o, 1));
1846           NewI2->insertBefore(J);
1847           I2 = NewI2;
1848           I2T = I1T;
1849           I2Elem = I1Elem;
1850         }
1851
1852         // Now that both I1 and I2 are the same length we can shuffle them
1853         // together (and use the result).
1854         std::vector<Constant *> Mask(numElem);
1855         for (unsigned v = 0; v < numElem; ++v) {
1856           if (II[v].first == -1) {
1857             Mask[v] = UndefValue::get(Type::getInt32Ty(Context));
1858           } else {
1859             int Idx = II[v].first + II[v].second * I1Elem;
1860             Mask[v] = ConstantInt::get(Type::getInt32Ty(Context), Idx);
1861           }
1862         }
1863
1864         Instruction *NewOp =
1865           new ShuffleVectorInst(I1, I2, ConstantVector::get(Mask),
1866                                 getReplacementName(I, true, o));
1867         NewOp->insertBefore(J);
1868         return NewOp;
1869       }
1870     }
1871
1872     Type *ArgType = ArgTypeL;
1873     if (numElemL < numElemH) {
1874       if (numElemL == 1 && expandIEChain(Context, I, J, o, HOp, numElemH,
1875                                          ArgTypeL, VArgType, 1)) {
1876         // This is another short-circuit case: we're combining a scalar into
1877         // a vector that is formed by an IE chain. We've just expanded the IE
1878         // chain, now insert the scalar and we're done.
1879
1880         Instruction *S = InsertElementInst::Create(HOp, LOp, CV0,
1881                                                getReplacementName(I, true, o));
1882         S->insertBefore(J);
1883         return S;
1884       } else if (!expandIEChain(Context, I, J, o, LOp, numElemL, ArgTypeL,
1885                                 ArgTypeH)) {
1886         // The two vector inputs to the shuffle must be the same length,
1887         // so extend the smaller vector to be the same length as the larger one.
1888         Instruction *NLOp;
1889         if (numElemL > 1) {
1890
1891           std::vector<Constant *> Mask(numElemH);
1892           unsigned v = 0;
1893           for (; v < numElemL; ++v)
1894             Mask[v] = ConstantInt::get(Type::getInt32Ty(Context), v);
1895           for (; v < numElemH; ++v)
1896             Mask[v] = UndefValue::get(Type::getInt32Ty(Context));
1897
1898           NLOp = new ShuffleVectorInst(LOp, UndefValue::get(ArgTypeL),
1899                                        ConstantVector::get(Mask),
1900                                        getReplacementName(I, true, o, 1));
1901         } else {
1902           NLOp = InsertElementInst::Create(UndefValue::get(ArgTypeH), LOp, CV0,
1903                                            getReplacementName(I, true, o, 1));
1904         }
1905
1906         NLOp->insertBefore(J);
1907         LOp = NLOp;
1908       }
1909
1910       ArgType = ArgTypeH;
1911     } else if (numElemL > numElemH) {
1912       if (numElemH == 1 && expandIEChain(Context, I, J, o, LOp, numElemL,
1913                                          ArgTypeH, VArgType)) {
1914         Instruction *S =
1915           InsertElementInst::Create(LOp, HOp,
1916                                     ConstantInt::get(Type::getInt32Ty(Context),
1917                                                      numElemL),
1918                                     getReplacementName(I, true, o));
1919         S->insertBefore(J);
1920         return S;
1921       } else if (!expandIEChain(Context, I, J, o, HOp, numElemH, ArgTypeH,
1922                                 ArgTypeL)) {
1923         Instruction *NHOp;
1924         if (numElemH > 1) {
1925           std::vector<Constant *> Mask(numElemL);
1926           unsigned v = 0;
1927           for (; v < numElemH; ++v)
1928             Mask[v] = ConstantInt::get(Type::getInt32Ty(Context), v);
1929           for (; v < numElemL; ++v)
1930             Mask[v] = UndefValue::get(Type::getInt32Ty(Context));
1931
1932           NHOp = new ShuffleVectorInst(HOp, UndefValue::get(ArgTypeH),
1933                                        ConstantVector::get(Mask),
1934                                        getReplacementName(I, true, o, 1));
1935         } else {
1936           NHOp = InsertElementInst::Create(UndefValue::get(ArgTypeL), HOp, CV0,
1937                                            getReplacementName(I, true, o, 1));
1938         }
1939
1940         NHOp->insertBefore(J);
1941         HOp = NHOp;
1942       }
1943     }
1944
1945     if (ArgType->isVectorTy()) {
1946       unsigned numElem = cast<VectorType>(VArgType)->getNumElements();
1947       std::vector<Constant*> Mask(numElem);
1948       for (unsigned v = 0; v < numElem; ++v) {
1949         unsigned Idx = v;
1950         // If the low vector was expanded, we need to skip the extra
1951         // undefined entries.
1952         if (v >= numElemL && numElemH > numElemL)
1953           Idx += (numElemH - numElemL);
1954         Mask[v] = ConstantInt::get(Type::getInt32Ty(Context), Idx);
1955       }
1956
1957       Instruction *BV = new ShuffleVectorInst(LOp, HOp,
1958                                               ConstantVector::get(Mask),
1959                                               getReplacementName(I, true, o));
1960       BV->insertBefore(J);
1961       return BV;
1962     }
1963
1964     Instruction *BV1 = InsertElementInst::Create(
1965                                           UndefValue::get(VArgType), LOp, CV0,
1966                                           getReplacementName(I, true, o, 1));
1967     BV1->insertBefore(I);
1968     Instruction *BV2 = InsertElementInst::Create(BV1, HOp, CV1,
1969                                           getReplacementName(I, true, o, 2));
1970     BV2->insertBefore(J);
1971     return BV2;
1972   }
1973
1974   // This function creates an array of values that will be used as the inputs
1975   // to the vector instruction that fuses I with J.
1976   void BBVectorize::getReplacementInputsForPair(LLVMContext& Context,
1977                      Instruction *I, Instruction *J,
1978                      SmallVector<Value *, 3> &ReplacedOperands,
1979                      bool FlipMemInputs) {
1980     unsigned NumOperands = I->getNumOperands();
1981
1982     for (unsigned p = 0, o = NumOperands-1; p < NumOperands; ++p, --o) {
1983       // Iterate backward so that we look at the store pointer
1984       // first and know whether or not we need to flip the inputs.
1985
1986       if (isa<LoadInst>(I) || (o == 1 && isa<StoreInst>(I))) {
1987         // This is the pointer for a load/store instruction.
1988         ReplacedOperands[o] = getReplacementPointerInput(Context, I, J, o,
1989                                 FlipMemInputs);
1990         continue;
1991       } else if (isa<CallInst>(I)) {
1992         Function *F = cast<CallInst>(I)->getCalledFunction();
1993         unsigned IID = F->getIntrinsicID();
1994         if (o == NumOperands-1) {
1995           BasicBlock &BB = *I->getParent();
1996
1997           Module *M = BB.getParent()->getParent();
1998           Type *ArgTypeI = I->getType();
1999           Type *ArgTypeJ = J->getType();
2000           Type *VArgType = getVecTypeForPair(ArgTypeI, ArgTypeJ);
2001
2002           ReplacedOperands[o] = Intrinsic::getDeclaration(M,
2003             (Intrinsic::ID) IID, VArgType);
2004           continue;
2005         } else if (IID == Intrinsic::powi && o == 1) {
2006           // The second argument of powi is a single integer and we've already
2007           // checked that both arguments are equal. As a result, we just keep
2008           // I's second argument.
2009           ReplacedOperands[o] = I->getOperand(o);
2010           continue;
2011         }
2012       } else if (isa<ShuffleVectorInst>(I) && o == NumOperands-1) {
2013         ReplacedOperands[o] = getReplacementShuffleMask(Context, I, J);
2014         continue;
2015       }
2016
2017       ReplacedOperands[o] =
2018         getReplacementInput(Context, I, J, o, FlipMemInputs);
2019     }
2020   }
2021
2022   // This function creates two values that represent the outputs of the
2023   // original I and J instructions. These are generally vector shuffles
2024   // or extracts. In many cases, these will end up being unused and, thus,
2025   // eliminated by later passes.
2026   void BBVectorize::replaceOutputsOfPair(LLVMContext& Context, Instruction *I,
2027                      Instruction *J, Instruction *K,
2028                      Instruction *&InsertionPt,
2029                      Instruction *&K1, Instruction *&K2,
2030                      bool FlipMemInputs) {
2031     if (isa<StoreInst>(I)) {
2032       AA->replaceWithNewValue(I, K);
2033       AA->replaceWithNewValue(J, K);
2034     } else {
2035       Type *IType = I->getType();
2036       Type *JType = J->getType();
2037
2038       VectorType *VType = getVecTypeForPair(IType, JType);
2039       unsigned numElem = VType->getNumElements();
2040
2041       unsigned numElemI, numElemJ;
2042       if (IType->isVectorTy())
2043         numElemI = cast<VectorType>(IType)->getNumElements();
2044       else
2045         numElemI = 1;
2046
2047       if (JType->isVectorTy())
2048         numElemJ = cast<VectorType>(JType)->getNumElements();
2049       else
2050         numElemJ = 1;
2051
2052       if (IType->isVectorTy()) {
2053         std::vector<Constant*> Mask1(numElemI), Mask2(numElemI);
2054         for (unsigned v = 0; v < numElemI; ++v) {
2055           Mask1[v] = ConstantInt::get(Type::getInt32Ty(Context), v);
2056           Mask2[v] = ConstantInt::get(Type::getInt32Ty(Context), numElemJ+v);
2057         }
2058
2059         K1 = new ShuffleVectorInst(K, UndefValue::get(VType),
2060                                    ConstantVector::get(
2061                                      FlipMemInputs ? Mask2 : Mask1),
2062                                    getReplacementName(K, false, 1));
2063       } else {
2064         Value *CV0 = ConstantInt::get(Type::getInt32Ty(Context), 0);
2065         Value *CV1 = ConstantInt::get(Type::getInt32Ty(Context), numElem-1);
2066         K1 = ExtractElementInst::Create(K, FlipMemInputs ? CV1 : CV0,
2067                                           getReplacementName(K, false, 1));
2068       }
2069
2070       if (JType->isVectorTy()) {
2071         std::vector<Constant*> Mask1(numElemJ), Mask2(numElemJ);
2072         for (unsigned v = 0; v < numElemJ; ++v) {
2073           Mask1[v] = ConstantInt::get(Type::getInt32Ty(Context), v);
2074           Mask2[v] = ConstantInt::get(Type::getInt32Ty(Context), numElemI+v);
2075         }
2076
2077         K2 = new ShuffleVectorInst(K, UndefValue::get(VType),
2078                                    ConstantVector::get(
2079                                      FlipMemInputs ? Mask1 : Mask2),
2080                                    getReplacementName(K, false, 2));
2081       } else {
2082         Value *CV0 = ConstantInt::get(Type::getInt32Ty(Context), 0);
2083         Value *CV1 = ConstantInt::get(Type::getInt32Ty(Context), numElem-1);
2084         K2 = ExtractElementInst::Create(K, FlipMemInputs ? CV0 : CV1,
2085                                           getReplacementName(K, false, 2));
2086       }
2087
2088       K1->insertAfter(K);
2089       K2->insertAfter(K1);
2090       InsertionPt = K2;
2091     }
2092   }
2093
2094   // Move all uses of the function I (including pairing-induced uses) after J.
2095   bool BBVectorize::canMoveUsesOfIAfterJ(BasicBlock &BB,
2096                      std::multimap<Value *, Value *> &LoadMoveSet,
2097                      Instruction *I, Instruction *J) {
2098     // Skip to the first instruction past I.
2099     BasicBlock::iterator L = llvm::next(BasicBlock::iterator(I));
2100
2101     DenseSet<Value *> Users;
2102     AliasSetTracker WriteSet(*AA);
2103     for (; cast<Instruction>(L) != J; ++L)
2104       (void) trackUsesOfI(Users, WriteSet, I, L, true, &LoadMoveSet);
2105
2106     assert(cast<Instruction>(L) == J &&
2107       "Tracking has not proceeded far enough to check for dependencies");
2108     // If J is now in the use set of I, then trackUsesOfI will return true
2109     // and we have a dependency cycle (and the fusing operation must abort).
2110     return !trackUsesOfI(Users, WriteSet, I, J, true, &LoadMoveSet);
2111   }
2112
2113   // Move all uses of the function I (including pairing-induced uses) after J.
2114   void BBVectorize::moveUsesOfIAfterJ(BasicBlock &BB,
2115                      std::multimap<Value *, Value *> &LoadMoveSet,
2116                      Instruction *&InsertionPt,
2117                      Instruction *I, Instruction *J) {
2118     // Skip to the first instruction past I.
2119     BasicBlock::iterator L = llvm::next(BasicBlock::iterator(I));
2120
2121     DenseSet<Value *> Users;
2122     AliasSetTracker WriteSet(*AA);
2123     for (; cast<Instruction>(L) != J;) {
2124       if (trackUsesOfI(Users, WriteSet, I, L, true, &LoadMoveSet)) {
2125         // Move this instruction
2126         Instruction *InstToMove = L; ++L;
2127
2128         DEBUG(dbgs() << "BBV: moving: " << *InstToMove <<
2129                         " to after " << *InsertionPt << "\n");
2130         InstToMove->removeFromParent();
2131         InstToMove->insertAfter(InsertionPt);
2132         InsertionPt = InstToMove;
2133       } else {
2134         ++L;
2135       }
2136     }
2137   }
2138
2139   // Collect all load instruction that are in the move set of a given first
2140   // pair member.  These loads depend on the first instruction, I, and so need
2141   // to be moved after J (the second instruction) when the pair is fused.
2142   void BBVectorize::collectPairLoadMoveSet(BasicBlock &BB,
2143                      DenseMap<Value *, Value *> &ChosenPairs,
2144                      std::multimap<Value *, Value *> &LoadMoveSet,
2145                      Instruction *I) {
2146     // Skip to the first instruction past I.
2147     BasicBlock::iterator L = llvm::next(BasicBlock::iterator(I));
2148
2149     DenseSet<Value *> Users;
2150     AliasSetTracker WriteSet(*AA);
2151
2152     // Note: We cannot end the loop when we reach J because J could be moved
2153     // farther down the use chain by another instruction pairing. Also, J
2154     // could be before I if this is an inverted input.
2155     for (BasicBlock::iterator E = BB.end(); cast<Instruction>(L) != E; ++L) {
2156       if (trackUsesOfI(Users, WriteSet, I, L)) {
2157         if (L->mayReadFromMemory())
2158           LoadMoveSet.insert(ValuePair(L, I));
2159       }
2160     }
2161   }
2162
2163   // In cases where both load/stores and the computation of their pointers
2164   // are chosen for vectorization, we can end up in a situation where the
2165   // aliasing analysis starts returning different query results as the
2166   // process of fusing instruction pairs continues. Because the algorithm
2167   // relies on finding the same use trees here as were found earlier, we'll
2168   // need to precompute the necessary aliasing information here and then
2169   // manually update it during the fusion process.
2170   void BBVectorize::collectLoadMoveSet(BasicBlock &BB,
2171                      std::vector<Value *> &PairableInsts,
2172                      DenseMap<Value *, Value *> &ChosenPairs,
2173                      std::multimap<Value *, Value *> &LoadMoveSet) {
2174     for (std::vector<Value *>::iterator PI = PairableInsts.begin(),
2175          PIE = PairableInsts.end(); PI != PIE; ++PI) {
2176       DenseMap<Value *, Value *>::iterator P = ChosenPairs.find(*PI);
2177       if (P == ChosenPairs.end()) continue;
2178
2179       Instruction *I = cast<Instruction>(P->first);
2180       collectPairLoadMoveSet(BB, ChosenPairs, LoadMoveSet, I);
2181     }
2182   }
2183
2184   // As with the aliasing information, SCEV can also change because of
2185   // vectorization. This information is used to compute relative pointer
2186   // offsets; the necessary information will be cached here prior to
2187   // fusion.
2188   void BBVectorize::collectPtrInfo(std::vector<Value *> &PairableInsts,
2189                                    DenseMap<Value *, Value *> &ChosenPairs,
2190                                    DenseSet<Value *> &LowPtrInsts) {
2191     for (std::vector<Value *>::iterator PI = PairableInsts.begin(),
2192       PIE = PairableInsts.end(); PI != PIE; ++PI) {
2193       DenseMap<Value *, Value *>::iterator P = ChosenPairs.find(*PI);
2194       if (P == ChosenPairs.end()) continue;
2195
2196       Instruction *I = cast<Instruction>(P->first);
2197       Instruction *J = cast<Instruction>(P->second);
2198
2199       if (!isa<LoadInst>(I) && !isa<StoreInst>(I))
2200         continue;
2201
2202       Value *IPtr, *JPtr;
2203       unsigned IAlignment, JAlignment;
2204       int64_t OffsetInElmts;
2205       if (!getPairPtrInfo(I, J, IPtr, JPtr, IAlignment, JAlignment,
2206                           OffsetInElmts) || abs64(OffsetInElmts) != 1)
2207         llvm_unreachable("Pre-fusion pointer analysis failed");
2208
2209       Value *LowPI = (OffsetInElmts > 0) ? I : J;
2210       LowPtrInsts.insert(LowPI);
2211     }
2212   }
2213
2214   // When the first instruction in each pair is cloned, it will inherit its
2215   // parent's metadata. This metadata must be combined with that of the other
2216   // instruction in a safe way.
2217   void BBVectorize::combineMetadata(Instruction *K, const Instruction *J) {
2218     SmallVector<std::pair<unsigned, MDNode*>, 4> Metadata;
2219     K->getAllMetadataOtherThanDebugLoc(Metadata);
2220     for (unsigned i = 0, n = Metadata.size(); i < n; ++i) {
2221       unsigned Kind = Metadata[i].first;
2222       MDNode *JMD = J->getMetadata(Kind);
2223       MDNode *KMD = Metadata[i].second;
2224
2225       switch (Kind) {
2226       default:
2227         K->setMetadata(Kind, 0); // Remove unknown metadata
2228         break;
2229       case LLVMContext::MD_tbaa:
2230         K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD));
2231         break;
2232       case LLVMContext::MD_fpmath:
2233         K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD));
2234         break;
2235       }
2236     }
2237   }
2238
2239   // This function fuses the chosen instruction pairs into vector instructions,
2240   // taking care preserve any needed scalar outputs and, then, it reorders the
2241   // remaining instructions as needed (users of the first member of the pair
2242   // need to be moved to after the location of the second member of the pair
2243   // because the vector instruction is inserted in the location of the pair's
2244   // second member).
2245   void BBVectorize::fuseChosenPairs(BasicBlock &BB,
2246                      std::vector<Value *> &PairableInsts,
2247                      DenseMap<Value *, Value *> &ChosenPairs) {
2248     LLVMContext& Context = BB.getContext();
2249
2250     // During the vectorization process, the order of the pairs to be fused
2251     // could be flipped. So we'll add each pair, flipped, into the ChosenPairs
2252     // list. After a pair is fused, the flipped pair is removed from the list.
2253     std::vector<ValuePair> FlippedPairs;
2254     FlippedPairs.reserve(ChosenPairs.size());
2255     for (DenseMap<Value *, Value *>::iterator P = ChosenPairs.begin(),
2256          E = ChosenPairs.end(); P != E; ++P)
2257       FlippedPairs.push_back(ValuePair(P->second, P->first));
2258     for (std::vector<ValuePair>::iterator P = FlippedPairs.begin(),
2259          E = FlippedPairs.end(); P != E; ++P)
2260       ChosenPairs.insert(*P);
2261
2262     std::multimap<Value *, Value *> LoadMoveSet;
2263     collectLoadMoveSet(BB, PairableInsts, ChosenPairs, LoadMoveSet);
2264
2265     DenseSet<Value *> LowPtrInsts;
2266     collectPtrInfo(PairableInsts, ChosenPairs, LowPtrInsts);
2267
2268     DEBUG(dbgs() << "BBV: initial: \n" << BB << "\n");
2269
2270     for (BasicBlock::iterator PI = BB.getFirstInsertionPt(); PI != BB.end();) {
2271       DenseMap<Value *, Value *>::iterator P = ChosenPairs.find(PI);
2272       if (P == ChosenPairs.end()) {
2273         ++PI;
2274         continue;
2275       }
2276
2277       if (getDepthFactor(P->first) == 0) {
2278         // These instructions are not really fused, but are tracked as though
2279         // they are. Any case in which it would be interesting to fuse them
2280         // will be taken care of by InstCombine.
2281         --NumFusedOps;
2282         ++PI;
2283         continue;
2284       }
2285
2286       Instruction *I = cast<Instruction>(P->first),
2287         *J = cast<Instruction>(P->second);
2288
2289       DEBUG(dbgs() << "BBV: fusing: " << *I <<
2290              " <-> " << *J << "\n");
2291
2292       // Remove the pair and flipped pair from the list.
2293       DenseMap<Value *, Value *>::iterator FP = ChosenPairs.find(P->second);
2294       assert(FP != ChosenPairs.end() && "Flipped pair not found in list");
2295       ChosenPairs.erase(FP);
2296       ChosenPairs.erase(P);
2297
2298       if (!canMoveUsesOfIAfterJ(BB, LoadMoveSet, I, J)) {
2299         DEBUG(dbgs() << "BBV: fusion of: " << *I <<
2300                " <-> " << *J <<
2301                " aborted because of non-trivial dependency cycle\n");
2302         --NumFusedOps;
2303         ++PI;
2304         continue;
2305       }
2306
2307       bool FlipMemInputs = false;
2308       if (isa<LoadInst>(I) || isa<StoreInst>(I))
2309         FlipMemInputs = (LowPtrInsts.find(I) == LowPtrInsts.end());
2310
2311       unsigned NumOperands = I->getNumOperands();
2312       SmallVector<Value *, 3> ReplacedOperands(NumOperands);
2313       getReplacementInputsForPair(Context, I, J, ReplacedOperands,
2314         FlipMemInputs);
2315
2316       // Make a copy of the original operation, change its type to the vector
2317       // type and replace its operands with the vector operands.
2318       Instruction *K = I->clone();
2319       if (I->hasName()) K->takeName(I);
2320
2321       if (!isa<StoreInst>(K))
2322         K->mutateType(getVecTypeForPair(I->getType(), J->getType()));
2323
2324       combineMetadata(K, J);
2325
2326       for (unsigned o = 0; o < NumOperands; ++o)
2327         K->setOperand(o, ReplacedOperands[o]);
2328
2329       // If we've flipped the memory inputs, make sure that we take the correct
2330       // alignment.
2331       if (FlipMemInputs) {
2332         if (isa<StoreInst>(K))
2333           cast<StoreInst>(K)->setAlignment(cast<StoreInst>(J)->getAlignment());
2334         else
2335           cast<LoadInst>(K)->setAlignment(cast<LoadInst>(J)->getAlignment());
2336       }
2337
2338       K->insertAfter(J);
2339
2340       // Instruction insertion point:
2341       Instruction *InsertionPt = K;
2342       Instruction *K1 = 0, *K2 = 0;
2343       replaceOutputsOfPair(Context, I, J, K, InsertionPt, K1, K2,
2344         FlipMemInputs);
2345
2346       // The use tree of the first original instruction must be moved to after
2347       // the location of the second instruction. The entire use tree of the
2348       // first instruction is disjoint from the input tree of the second
2349       // (by definition), and so commutes with it.
2350
2351       moveUsesOfIAfterJ(BB, LoadMoveSet, InsertionPt, I, J);
2352
2353       if (!isa<StoreInst>(I)) {
2354         I->replaceAllUsesWith(K1);
2355         J->replaceAllUsesWith(K2);
2356         AA->replaceWithNewValue(I, K1);
2357         AA->replaceWithNewValue(J, K2);
2358       }
2359
2360       // Instructions that may read from memory may be in the load move set.
2361       // Once an instruction is fused, we no longer need its move set, and so
2362       // the values of the map never need to be updated. However, when a load
2363       // is fused, we need to merge the entries from both instructions in the
2364       // pair in case those instructions were in the move set of some other
2365       // yet-to-be-fused pair. The loads in question are the keys of the map.
2366       if (I->mayReadFromMemory()) {
2367         std::vector<ValuePair> NewSetMembers;
2368         VPIteratorPair IPairRange = LoadMoveSet.equal_range(I);
2369         VPIteratorPair JPairRange = LoadMoveSet.equal_range(J);
2370         for (std::multimap<Value *, Value *>::iterator N = IPairRange.first;
2371              N != IPairRange.second; ++N)
2372           NewSetMembers.push_back(ValuePair(K, N->second));
2373         for (std::multimap<Value *, Value *>::iterator N = JPairRange.first;
2374              N != JPairRange.second; ++N)
2375           NewSetMembers.push_back(ValuePair(K, N->second));
2376         for (std::vector<ValuePair>::iterator A = NewSetMembers.begin(),
2377              AE = NewSetMembers.end(); A != AE; ++A)
2378           LoadMoveSet.insert(*A);
2379       }
2380
2381       // Before removing I, set the iterator to the next instruction.
2382       PI = llvm::next(BasicBlock::iterator(I));
2383       if (cast<Instruction>(PI) == J)
2384         ++PI;
2385
2386       SE->forgetValue(I);
2387       SE->forgetValue(J);
2388       I->eraseFromParent();
2389       J->eraseFromParent();
2390     }
2391
2392     DEBUG(dbgs() << "BBV: final: \n" << BB << "\n");
2393   }
2394 }
2395
2396 char BBVectorize::ID = 0;
2397 static const char bb_vectorize_name[] = "Basic-Block Vectorization";
2398 INITIALIZE_PASS_BEGIN(BBVectorize, BBV_NAME, bb_vectorize_name, false, false)
2399 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
2400 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
2401 INITIALIZE_PASS_END(BBVectorize, BBV_NAME, bb_vectorize_name, false, false)
2402
2403 BasicBlockPass *llvm::createBBVectorizePass(const VectorizeConfig &C) {
2404   return new BBVectorize(C);
2405 }
2406
2407 bool
2408 llvm::vectorizeBasicBlock(Pass *P, BasicBlock &BB, const VectorizeConfig &C) {
2409   BBVectorize BBVectorizer(P, C);
2410   return BBVectorizer.vectorizeBB(BB);
2411 }
2412
2413 //===----------------------------------------------------------------------===//
2414 VectorizeConfig::VectorizeConfig() {
2415   VectorBits = ::VectorBits;
2416   VectorizeBools = !::NoBools;
2417   VectorizeInts = !::NoInts;
2418   VectorizeFloats = !::NoFloats;
2419   VectorizePointers = !::NoPointers;
2420   VectorizeCasts = !::NoCasts;
2421   VectorizeMath = !::NoMath;
2422   VectorizeFMA = !::NoFMA;
2423   VectorizeSelect = !::NoSelect;
2424   VectorizeCmp = !::NoCmp;
2425   VectorizeGEP = !::NoGEP;
2426   VectorizeMemOps = !::NoMemOps;
2427   AlignedOnly = ::AlignedOnly;
2428   ReqChainDepth= ::ReqChainDepth;
2429   SearchLimit = ::SearchLimit;
2430   MaxCandPairsForCycleCheck = ::MaxCandPairsForCycleCheck;
2431   SplatBreaksChain = ::SplatBreaksChain;
2432   MaxInsts = ::MaxInsts;
2433   MaxIter = ::MaxIter;
2434   Pow2LenOnly = ::Pow2LenOnly;
2435   NoMemOpBoost = ::NoMemOpBoost;
2436   FastDep = ::FastDep;
2437 }