[LSV] Use OrderedBasicBlock instead of rolling it ourselves. [NFC]

[jlebar]

Summary

In getVectorizablePrefix, this is less efficient (because we have to
iterate over the BB twice), but boy is it simpler. Given how much
trouble we've had here, I think the simplicity gain is worthwhile.

In reorder(), this is actually more efficient, as
DominatorTree::dominates iterates over the BB from the beginning when
the two instructions are in the same BB.

[asbirlea]

LGTM. (Nice..)

llvm/trunk/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/OrderedBasicBlock.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
bool Vectorizer::isConsecutiveAccess(Value *A, Value *B) {
   const SCEV *OffsetSCEVA = SE.getSCEV(OpA);
   const SCEV *OffsetSCEVB = SE.getSCEV(OpB);
   const SCEV *One = SE.getConstant(APInt(BitWidth, 1));
   const SCEV *X2 = SE.getAddExpr(OffsetSCEVA, One);
   return X2 == OffsetSCEVB;
 }
 
 void Vectorizer::reorder(Instruction *I) {
+  OrderedBasicBlock OBB(I->getParent());
   SmallPtrSet<Instruction *, 16> InstructionsToMove;
   SmallVector<Instruction *, 16> Worklist;
 
   Worklist.push_back(I);
   while (!Worklist.empty()) {
     Instruction *IW = Worklist.pop_back_val();
     int NumOperands = IW->getNumOperands();
     for (int i = 0; i < NumOperands; i++) {
       Instruction *IM = dyn_cast<Instruction>(IW->getOperand(i));
       if (!IM || IM->getOpcode() == Instruction::PHI)
         continue;
 
-      if (!DT.dominates(IM, I)) {
+      // If IM is in another BB, no need to move it, because this pass only
+      // vectorizes instructions within one BB.
+      if (IM->getParent() != I->getParent())
+        continue;
+
+      if (!OBB.dominates(IM, I)) {
         InstructionsToMove.insert(IM);
         Worklist.push_back(IM);
-        assert(IM->getParent() == IW->getParent() &&
-               "Instructions to move should be in the same basic block");
       }
     }
   }
 
   // All instructions to move should follow I. Start from I, not from begin().
   for (auto BBI = I->getIterator(), E = I->getParent()->end(); BBI != E;
        ++BBI) {
     if (!InstructionsToMove.count(&*BBI))
Vectorizer::splitOddVectorElts(ArrayRef<Instruction *> Chain,
   unsigned NumRight = (SizeInBytes % 4) / ElemSizeInBytes;
   unsigned NumLeft = Chain.size() - NumRight;
   return std::make_pair(Chain.slice(0, NumLeft), Chain.slice(NumLeft));
 }
 
 ArrayRef<Instruction *>
 Vectorizer::getVectorizablePrefix(ArrayRef<Instruction *> Chain) {
   // These are in BB order, unlike Chain, which is in address order.
-  SmallVector<std::pair<Instruction *, unsigned>, 16> MemoryInstrs;
-  SmallVector<std::pair<Instruction *, unsigned>, 16> ChainInstrs;
+  SmallVector<Instruction *, 16> MemoryInstrs;
+  SmallVector<Instruction *, 16> ChainInstrs;
 
   bool IsLoadChain = isa<LoadInst>(Chain[0]);
   DEBUG({
     for (Instruction *I : Chain) {
       if (IsLoadChain)
         assert(isa<LoadInst>(I) &&
                "All elements of Chain must be loads, or all must be stores.");
       else
         assert(isa<StoreInst>(I) &&
                "All elements of Chain must be loads, or all must be stores.");
     }
   });
 
-  unsigned InstrIdx = 0;
   for (Instruction &I : make_range(getBoundaryInstrs(Chain))) {
-    ++InstrIdx;
     if (isa<LoadInst>(I) || isa<StoreInst>(I)) {
       if (!is_contained(Chain, &I))
-        MemoryInstrs.push_back({&I, InstrIdx});
+        MemoryInstrs.push_back(&I);
       else
-        ChainInstrs.push_back({&I, InstrIdx});
+        ChainInstrs.push_back(&I);
     } else if (IsLoadChain && (I.mayWriteToMemory() || I.mayThrow())) {
       DEBUG(dbgs() << "LSV: Found may-write/throw operation: " << I << '\n');
       break;
     } else if (!IsLoadChain && (I.mayReadOrWriteMemory() || I.mayThrow())) {
       DEBUG(dbgs() << "LSV: Found may-read/write/throw operation: " << I
                    << '\n');
       break;
     }
   }
 
+  OrderedBasicBlock OBB(Chain[0]->getParent());
+
   // Loop until we find an instruction in ChainInstrs that we can't vectorize.
-  unsigned ChainInstrIdx, ChainInstrsLen;
-  for (ChainInstrIdx = 0, ChainInstrsLen = ChainInstrs.size();
-       ChainInstrIdx < ChainInstrsLen; ++ChainInstrIdx) {
-    Instruction *ChainInstr = ChainInstrs[ChainInstrIdx].first;
-    unsigned ChainInstrLoc = ChainInstrs[ChainInstrIdx].second;
+  unsigned ChainInstrIdx = 0;
+  for (unsigned E = ChainInstrs.size(); ChainInstrIdx < E; ++ChainInstrIdx) {
+    Instruction *ChainInstr = ChainInstrs[ChainInstrIdx];
     bool AliasFound = false;
-    for (auto EntryMem : MemoryInstrs) {
-      Instruction *MemInstr = EntryMem.first;
-      unsigned MemInstrLoc = EntryMem.second;
+    for (Instruction *MemInstr : MemoryInstrs) {
       if (isa<LoadInst>(MemInstr) && isa<LoadInst>(ChainInstr))
         continue;
 
       // We can ignore the alias as long as the load comes before the store,
       // because that means we won't be moving the load past the store to
       // vectorize it (the vectorized load is inserted at the location of the
       // first load in the chain).
       if (isa<StoreInst>(MemInstr) && isa<LoadInst>(ChainInstr) &&
-          ChainInstrLoc < MemInstrLoc)
+          OBB.dominates(ChainInstr, MemInstr))
         continue;
 
       // Same case, but in reverse.
       if (isa<LoadInst>(MemInstr) && isa<StoreInst>(ChainInstr) &&
-          ChainInstrLoc > MemInstrLoc)
+          OBB.dominates(MemInstr, ChainInstr))
         continue;
 
       if (!AA.isNoAlias(MemoryLocation::get(MemInstr),
                         MemoryLocation::get(ChainInstr))) {
         DEBUG({
           dbgs() << "LSV: Found alias:\n"
                     "  Aliasing instruction and pointer:\n"
                  << "  " << *MemInstr << '\n'
Vectorizer::getVectorizablePrefix(ArrayRef<Instruction *> Chain) {
   // ChainInstrs[0, ChainInstrIdx).  This is the largest vectorizable prefix of
   // Chain.  (Recall that Chain is in address order, but ChainInstrs is in BB
   // order.)
   auto VectorizableChainInstrs =
       makeArrayRef(ChainInstrs.data(), ChainInstrIdx);
   unsigned ChainIdx, ChainLen;
   for (ChainIdx = 0, ChainLen = Chain.size(); ChainIdx < ChainLen; ++ChainIdx) {
     Instruction *I = Chain[ChainIdx];
-    if (none_of(VectorizableChainInstrs,
-                [I](std::pair<Instruction *, unsigned> CI) {
-                  return I == CI.first;
-                }))
+    if (!is_contained(VectorizableChainInstrs, I))
       break;
   }
   return Chain.slice(0, ChainIdx);
 }
 
 std::pair<InstrListMap, InstrListMap>
 Vectorizer::collectInstructions(BasicBlock *BB) {
   InstrListMap LoadRefs;