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