diff --git a/llvm/include/llvm/Analysis/AliasAnalysis.h b/llvm/include/llvm/Analysis/AliasAnalysis.h
--- a/llvm/include/llvm/Analysis/AliasAnalysis.h
+++ b/llvm/include/llvm/Analysis/AliasAnalysis.h
@@ -59,7 +59,6 @@
 class BasicAAResult;
 class BasicBlock;
 class DominatorTree;
-class OrderedBasicBlock;
 class Value;
 
 /// The possible results of an alias query.
@@ -689,19 +688,16 @@
 
   /// Return information about whether a particular call site modifies
   /// or reads the specified memory location \p MemLoc before instruction \p I
-  /// in a BasicBlock. An ordered basic block \p OBB can be used to speed up
-  /// instruction ordering queries inside the BasicBlock containing \p I.
+  /// in a BasicBlock.
   /// Early exits in callCapturesBefore may lead to ModRefInfo::Must not being
   /// set.
   ModRefInfo callCapturesBefore(const Instruction *I,
-                                const MemoryLocation &MemLoc, DominatorTree *DT,
-                                OrderedBasicBlock *OBB = nullptr);
+                                const MemoryLocation &MemLoc, DominatorTree *DT);
 
   /// A convenience wrapper to synthesize a memory location.
   ModRefInfo callCapturesBefore(const Instruction *I, const Value *P,
-                                LocationSize Size, DominatorTree *DT,
-                                OrderedBasicBlock *OBB = nullptr) {
-    return callCapturesBefore(I, MemoryLocation(P, Size), DT, OBB);
+                                LocationSize Size, DominatorTree *DT) {
+    return callCapturesBefore(I, MemoryLocation(P, Size), DT);
   }
 
   /// @}
diff --git a/llvm/include/llvm/Analysis/CaptureTracking.h b/llvm/include/llvm/Analysis/CaptureTracking.h
--- a/llvm/include/llvm/Analysis/CaptureTracking.h
+++ b/llvm/include/llvm/Analysis/CaptureTracking.h
@@ -20,7 +20,6 @@
   class DataLayout;
   class Instruction;
   class DominatorTree;
-  class OrderedBasicBlock;
 
   /// The default value for MaxUsesToExplore argument. It's relatively small to
   /// keep the cost of analysis reasonable for clients like BasicAliasAnalysis,
@@ -53,14 +52,12 @@
   /// it or not.  The boolean StoreCaptures specified whether storing the value
   /// (or part of it) into memory anywhere automatically counts as capturing it
   /// or not. Captures by the provided instruction are considered if the
-  /// final parameter is true. An ordered basic block in \p OBB could be used
-  /// to speed up capture-tracker queries.
+  /// final parameter is true.
   /// MaxUsesToExplore specifies how many uses should the analysis explore for
   /// one value before giving up due too "too many uses".
   bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures,
                                   bool StoreCaptures, const Instruction *I,
                                   const DominatorTree *DT, bool IncludeI = false,
-                                  OrderedBasicBlock *OBB = nullptr,
                                   unsigned MaxUsesToExplore = DefaultMaxUsesToExplore);
 
   /// This callback is used in conjunction with PointerMayBeCaptured. In
diff --git a/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h b/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h
--- a/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h
+++ b/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -384,8 +384,7 @@
   ///
   /// See the class comment for more details. It is illegal to call this on
   /// non-memory instructions.
-  MemDepResult getDependency(Instruction *QueryInst,
-                             OrderedBasicBlock *OBB = nullptr);
+  MemDepResult getDependency(Instruction *QueryInst);
 
   /// Perform a full dependency query for the specified call, returning the set
   /// of blocks that the value is potentially live across.
@@ -451,14 +450,12 @@
                                         BasicBlock::iterator ScanIt,
                                         BasicBlock *BB,
                                         Instruction *QueryInst = nullptr,
-                                        unsigned *Limit = nullptr,
-                                        OrderedBasicBlock *OBB = nullptr);
+                                        unsigned *Limit = nullptr);
 
   MemDepResult
   getSimplePointerDependencyFrom(const MemoryLocation &MemLoc, bool isLoad,
                                  BasicBlock::iterator ScanIt, BasicBlock *BB,
-                                 Instruction *QueryInst, unsigned *Limit,
-                                 OrderedBasicBlock *OBB);
+                                 Instruction *QueryInst, unsigned *Limit);
 
   /// This analysis looks for other loads and stores with invariant.group
   /// metadata and the same pointer operand. Returns Unknown if it does not
diff --git a/llvm/include/llvm/Analysis/OrderedBasicBlock.h b/llvm/include/llvm/Analysis/OrderedBasicBlock.h
deleted file mode 100644
--- a/llvm/include/llvm/Analysis/OrderedBasicBlock.h
+++ /dev/null
@@ -1,74 +0,0 @@
-//===- llvm/Analysis/OrderedBasicBlock.h --------------------- -*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-// This file defines the OrderedBasicBlock class. OrderedBasicBlock maintains
-// an interface where clients can query if one instruction comes before another
-// in a BasicBlock. Since BasicBlock currently lacks a reliable way to query
-// relative position between instructions one can use OrderedBasicBlock to do
-// such queries. OrderedBasicBlock is lazily built on a source BasicBlock and
-// maintains an internal Instruction -> Position map. A OrderedBasicBlock
-// instance should be discarded whenever the source BasicBlock changes.
-//
-// It's currently used by the CaptureTracker in order to find relative
-// positions of a pair of instructions inside a BasicBlock.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_ORDEREDBASICBLOCK_H
-#define LLVM_ANALYSIS_ORDEREDBASICBLOCK_H
-
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/IR/BasicBlock.h"
-
-namespace llvm {
-
-class Instruction;
-class BasicBlock;
-
-class OrderedBasicBlock {
-private:
-  /// Map a instruction to its position in a BasicBlock.
-  SmallDenseMap<const Instruction *, unsigned, 32> NumberedInsts;
-
-  /// Keep track of last instruction inserted into \p NumberedInsts.
-  /// It speeds up queries for uncached instructions by providing a start point
-  /// for new queries in OrderedBasicBlock::comesBefore.
-  BasicBlock::const_iterator LastInstFound;
-
-  /// The position/number to tag the next instruction to be found.
-  unsigned NextInstPos;
-
-  /// The source BasicBlock to map.
-  const BasicBlock *BB;
-
-  /// Given no cached results, find if \p A comes before \p B in \p BB.
-  /// Cache and number out instruction while walking \p BB.
-  bool comesBefore(const Instruction *A, const Instruction *B);
-
-public:
-  OrderedBasicBlock(const BasicBlock *BasicB);
-
-  /// Find out whether \p A dominates \p B, meaning whether \p A
-  /// comes before \p B in \p BB. This is a simplification that considers
-  /// cached instruction positions and ignores other basic blocks, being
-  /// only relevant to compare relative instructions positions inside \p BB.
-  /// Returns false for A == B.
-  bool dominates(const Instruction *A, const Instruction *B);
-
-  /// Remove \p from the ordering, if it is present.
-  void eraseInstruction(const Instruction *I);
-
-  /// Replace \p Old with \p New in the ordering. \p New is assigned the
-  /// numbering of \p Old, so it must be inserted at the same position in the
-  /// IR.
-  void replaceInstruction(const Instruction *Old, const Instruction *New);
-};
-
-} // End llvm namespace
-
-#endif
diff --git a/llvm/include/llvm/Analysis/OrderedInstructions.h b/llvm/include/llvm/Analysis/OrderedInstructions.h
--- a/llvm/include/llvm/Analysis/OrderedInstructions.h
+++ b/llvm/include/llvm/Analysis/OrderedInstructions.h
@@ -9,10 +9,9 @@
 // This file defines an efficient way to check for dominance relation between 2
 // instructions.
 //
-// This interface dispatches to appropriate dominance check given 2
-// instructions, i.e. in case the instructions are in the same basic block,
-// OrderedBasicBlock (with instruction numbering and caching) are used.
-// Otherwise, dominator tree is used.
+// FIXME: This is really just a convenience wrapper to check dominance between
+// two arbitrary instructions in different basic blocks. We should fold it into
+// DominatorTree, which is the more widely used interface.
 //
 //===----------------------------------------------------------------------===//
 
@@ -20,17 +19,12 @@
 #define LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H
 
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/Analysis/OrderedBasicBlock.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Operator.h"
 
 namespace llvm {
 
 class OrderedInstructions {
-  /// Used to check dominance for instructions in same basic block.
-  mutable DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>>
-      OBBMap;
-
   /// The dominator tree of the parent function.
   DominatorTree *DT;
 
@@ -51,12 +45,6 @@
   /// or if the first instruction comes before the second in the same basic
   /// block.
   bool dfsBefore(const Instruction *, const Instruction *) const;
-
-  /// Invalidate the OrderedBasicBlock cache when its basic block changes.
-  /// i.e. If an instruction is deleted or added to the basic block, the user
-  /// should call this function to invalidate the OrderedBasicBlock cache for
-  /// this basic block.
-  void invalidateBlock(const BasicBlock *BB) { OBBMap.erase(BB); }
 };
 
 } // end namespace llvm
diff --git a/llvm/include/llvm/IR/BasicBlock.h b/llvm/include/llvm/IR/BasicBlock.h
--- a/llvm/include/llvm/IR/BasicBlock.h
+++ b/llvm/include/llvm/IR/BasicBlock.h
@@ -402,7 +402,9 @@
 
   /// Returns true if there are any uses of this basic block other than
   /// direct branches, switches, etc. to it.
-  bool hasAddressTaken() const { return getSubclassDataFromValue() != 0; }
+  bool hasAddressTaken() const {
+    return getBasicBlockBits().BlockAddressRefCount != 0;
+  }
 
   /// Update all phi nodes in this basic block to refer to basic block \p New
   /// instead of basic block \p Old.
@@ -437,16 +439,61 @@
 
   Optional<uint64_t> getIrrLoopHeaderWeight() const;
 
+  /// Returns true if the Order field of child Instructions is valid.
+  bool isInstrOrderValid() const {
+    return getBasicBlockBits().InstrOrderValid;
+  }
+
+  /// Mark instruction ordering invalid. Done on every instruction insert.
+  void invalidateOrders() {
+    validateInstrOrdering();
+    BasicBlockBits Bits = getBasicBlockBits();
+    Bits.InstrOrderValid = false;
+    setBasicBlockBits(Bits);
+  }
+
+  /// Renumber instructions and mark the ordering as valid.
+  void renumberInstructions();
+
+  /// Returns false if the instruction ordering is incorrect in an debug build.
+  /// Always returns true when assertions are disabled. The method does not
+  /// assert internally so that we get better location info.
+  void validateInstrOrdering() const;
+
 private:
+  /// Bitfield to help interpret the bits in Value::SubclassData.
+  struct BasicBlockBits {
+    unsigned short BlockAddressRefCount : 15;
+    unsigned short InstrOrderValid : 1;
+  };
+
+  /// Safely reinterpret the subclass data bits to a more useful form.
+  BasicBlockBits getBasicBlockBits() const {
+    static_assert(sizeof(BasicBlockBits) == sizeof(unsigned short),
+                  "too many bits for Value::SubclassData");
+    unsigned short ValueData = getSubclassDataFromValue();
+    BasicBlockBits AsBits;
+    memcpy(&AsBits, &ValueData, sizeof(AsBits));
+    return AsBits;
+  }
+
+  /// Reinterpret our subclass bits and store them back into Value.
+  void setBasicBlockBits(BasicBlockBits AsBits) {
+    unsigned short D;
+    memcpy(&D, &AsBits, sizeof(D));
+    Value::setValueSubclassData(D);
+  }
+
   /// Increment the internal refcount of the number of BlockAddresses
   /// referencing this BasicBlock by \p Amt.
   ///
   /// This is almost always 0, sometimes one possibly, but almost never 2, and
   /// inconceivably 3 or more.
   void AdjustBlockAddressRefCount(int Amt) {
-    setValueSubclassData(getSubclassDataFromValue()+Amt);
-    assert((int)(signed char)getSubclassDataFromValue() >= 0 &&
-           "Refcount wrap-around");
+    BasicBlockBits Bits = getBasicBlockBits();
+    Bits.BlockAddressRefCount += Amt;
+    setBasicBlockBits(Bits);
+    assert(Bits.BlockAddressRefCount < 255 && "Refcount wrap-around");
   }
 
   /// Shadow Value::setValueSubclassData with a private forwarding method so
@@ -463,6 +510,12 @@
 /// This assumes that \p It is not at the end of a block.
 BasicBlock::iterator skipDebugIntrinsics(BasicBlock::iterator It);
 
+#ifdef NDEBUG
+/// In release builds, this is a no-op. For !NDEBUG builds, the checks are
+/// implemented in the .cpp file to avoid circular header deps.
+inline void Instruction::validateInstrOrdering() const {}
+#endif
+
 } // end namespace llvm
 
 #endif // LLVM_IR_BASICBLOCK_H
diff --git a/llvm/include/llvm/IR/Instruction.h b/llvm/include/llvm/IR/Instruction.h
--- a/llvm/include/llvm/IR/Instruction.h
+++ b/llvm/include/llvm/IR/Instruction.h
@@ -45,6 +45,10 @@
   BasicBlock *Parent;
   DebugLoc DbgLoc;                         // 'dbg' Metadata cache.
 
+  /// Relative order of this instruction in its parent basic block. Used for
+  /// O(1) local dominance checks between instructions.
+  mutable unsigned Order = 0;
+
   enum {
     /// This is a bit stored in the SubClassData field which indicates whether
     /// this instruction has metadata attached to it or not.
@@ -117,6 +121,13 @@
   /// the basic block that MovePos lives in, right after MovePos.
   void moveAfter(Instruction *MovePos);
 
+  /// Given an instruction Other in the same basic block as this instruction,
+  /// return true if this instruction comes before Other. In this worst case,
+  /// this takes linear time in the number of instructions in the block. The
+  /// results are cached, so in common cases when the block remains unmodified,
+  /// it takes constant time.
+  bool comesBefore(const Instruction *Other) const;
+
   //===--------------------------------------------------------------------===//
   // Subclass classification.
   //===--------------------------------------------------------------------===//
@@ -738,6 +749,7 @@
 
 private:
   friend class SymbolTableListTraits<Instruction>;
+  friend class BasicBlock; // For renumbering.
 
   // Shadow Value::setValueSubclassData with a private forwarding method so that
   // subclasses cannot accidentally use it.
diff --git a/llvm/lib/Analysis/AliasAnalysis.cpp b/llvm/lib/Analysis/AliasAnalysis.cpp
--- a/llvm/lib/Analysis/AliasAnalysis.cpp
+++ b/llvm/lib/Analysis/AliasAnalysis.cpp
@@ -630,16 +630,14 @@
 
 /// Return information about whether a particular call site modifies
 /// or reads the specified memory location \p MemLoc before instruction \p I
-/// in a BasicBlock. An ordered basic block \p OBB can be used to speed up
-/// instruction-ordering queries inside the BasicBlock containing \p I.
+/// in a BasicBlock.
 /// FIXME: this is really just shoring-up a deficiency in alias analysis.
 /// BasicAA isn't willing to spend linear time determining whether an alloca
 /// was captured before or after this particular call, while we are. However,
 /// with a smarter AA in place, this test is just wasting compile time.
 ModRefInfo AAResults::callCapturesBefore(const Instruction *I,
                                          const MemoryLocation &MemLoc,
-                                         DominatorTree *DT,
-                                         OrderedBasicBlock *OBB) {
+                                         DominatorTree *DT) {
   if (!DT)
     return ModRefInfo::ModRef;
 
@@ -655,8 +653,7 @@
 
   if (PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
                                  /* StoreCaptures */ true, I, DT,
-                                 /* include Object */ true,
-                                 /* OrderedBasicBlock */ OBB))
+                                 /* include Object */ true))
     return ModRefInfo::ModRef;
 
   unsigned ArgNo = 0;
diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt
--- a/llvm/lib/Analysis/CMakeLists.txt
+++ b/llvm/lib/Analysis/CMakeLists.txt
@@ -70,7 +70,6 @@
   ObjCARCAnalysisUtils.cpp
   ObjCARCInstKind.cpp
   OptimizationRemarkEmitter.cpp
-  OrderedBasicBlock.cpp
   OrderedInstructions.cpp
   PHITransAddr.cpp
   PhiValues.cpp
diff --git a/llvm/lib/Analysis/CaptureTracking.cpp b/llvm/lib/Analysis/CaptureTracking.cpp
--- a/llvm/lib/Analysis/CaptureTracking.cpp
+++ b/llvm/lib/Analysis/CaptureTracking.cpp
@@ -20,7 +20,6 @@
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CFG.h"
-#include "llvm/Analysis/OrderedBasicBlock.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
@@ -76,8 +75,8 @@
   struct CapturesBefore : public CaptureTracker {
 
     CapturesBefore(bool ReturnCaptures, const Instruction *I, const DominatorTree *DT,
-                   bool IncludeI, OrderedBasicBlock *IC)
-      : OrderedBB(IC), BeforeHere(I), DT(DT),
+                   bool IncludeI)
+      : BeforeHere(I), DT(DT),
         ReturnCaptures(ReturnCaptures), IncludeI(IncludeI), Captured(false) {}
 
     void tooManyUses() override { Captured = true; }
@@ -90,9 +89,7 @@
         return true;
 
       // Compute the case where both instructions are inside the same basic
-      // block. Since instructions in the same BB as BeforeHere are numbered in
-      // 'OrderedBB', avoid using 'dominates' and 'isPotentiallyReachable'
-      // which are very expensive for large basic blocks.
+      // block.
       if (BB == BeforeHere->getParent()) {
         // 'I' dominates 'BeforeHere' => not safe to prune.
         //
@@ -102,7 +99,7 @@
         // UseBB == BB, avoid pruning.
         if (isa<InvokeInst>(BeforeHere) || isa<PHINode>(I) || I == BeforeHere)
           return false;
-        if (!OrderedBB->dominates(BeforeHere, I))
+        if (!BeforeHere->comesBefore(I))
           return false;
 
         // 'BeforeHere' comes before 'I', it's safe to prune if we also
@@ -153,7 +150,6 @@
       return true;
     }
 
-    OrderedBasicBlock *OrderedBB;
     const Instruction *BeforeHere;
     const DominatorTree *DT;
 
@@ -196,31 +192,23 @@
 /// returning the value (or part of it) from the function counts as capturing
 /// it or not.  The boolean StoreCaptures specified whether storing the value
 /// (or part of it) into memory anywhere automatically counts as capturing it
-/// or not. A ordered basic block \p OBB can be used in order to speed up
-/// queries about relative order among instructions in the same basic block.
+/// or not.
 bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures,
                                       bool StoreCaptures, const Instruction *I,
                                       const DominatorTree *DT, bool IncludeI,
-                                      OrderedBasicBlock *OBB,
                                       unsigned MaxUsesToExplore) {
   assert(!isa<GlobalValue>(V) &&
          "It doesn't make sense to ask whether a global is captured.");
-  bool UseNewOBB = OBB == nullptr;
 
   if (!DT)
     return PointerMayBeCaptured(V, ReturnCaptures, StoreCaptures,
                                 MaxUsesToExplore);
-  if (UseNewOBB)
-    OBB = new OrderedBasicBlock(I->getParent());
 
   // TODO: See comment in PointerMayBeCaptured regarding what could be done
   // with StoreCaptures.
 
-  CapturesBefore CB(ReturnCaptures, I, DT, IncludeI, OBB);
+  CapturesBefore CB(ReturnCaptures, I, DT, IncludeI);
   PointerMayBeCaptured(V, &CB, MaxUsesToExplore);
-
-  if (UseNewOBB)
-    delete OBB;
   return CB.Captured;
 }
 
diff --git a/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp b/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp
--- a/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp
+++ b/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp
@@ -104,18 +104,14 @@
                                                         const BasicBlock *BB) {
   if (isSpecialInstruction(Inst))
     FirstSpecialInsts.erase(BB);
-  OI.invalidateBlock(BB);
 }
 
 void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) {
   if (isSpecialInstruction(Inst))
     FirstSpecialInsts.erase(Inst->getParent());
-  OI.invalidateBlock(Inst->getParent());
 }
 
 void InstructionPrecedenceTracking::clear() {
-  for (auto It : FirstSpecialInsts)
-    OI.invalidateBlock(It.first);
   FirstSpecialInsts.clear();
 #ifndef NDEBUG
   // The map should be valid after clearing (at least empty).
diff --git a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
--- a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -23,7 +23,6 @@
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryLocation.h"
-#include "llvm/Analysis/OrderedBasicBlock.h"
 #include "llvm/Analysis/PHITransAddr.h"
 #include "llvm/Analysis/PhiValues.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
@@ -250,8 +249,7 @@
 
 MemDepResult MemoryDependenceResults::getPointerDependencyFrom(
     const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
-    BasicBlock *BB, Instruction *QueryInst, unsigned *Limit,
-    OrderedBasicBlock *OBB) {
+    BasicBlock *BB, Instruction *QueryInst, unsigned *Limit) {
   MemDepResult InvariantGroupDependency = MemDepResult::getUnknown();
   if (QueryInst != nullptr) {
     if (auto *LI = dyn_cast<LoadInst>(QueryInst)) {
@@ -262,7 +260,7 @@
     }
   }
   MemDepResult SimpleDep = getSimplePointerDependencyFrom(
-      MemLoc, isLoad, ScanIt, BB, QueryInst, Limit, OBB);
+      MemLoc, isLoad, ScanIt, BB, QueryInst, Limit);
   if (SimpleDep.isDef())
     return SimpleDep;
   // Non-local invariant group dependency indicates there is non local Def
@@ -363,8 +361,7 @@
 
 MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom(
     const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
-    BasicBlock *BB, Instruction *QueryInst, unsigned *Limit,
-    OrderedBasicBlock *OBB) {
+    BasicBlock *BB, Instruction *QueryInst, unsigned *Limit) {
   bool isInvariantLoad = false;
 
   unsigned DefaultLimit = getDefaultBlockScanLimit();
@@ -411,15 +408,6 @@
 
   const DataLayout &DL = BB->getModule()->getDataLayout();
 
-  // If the caller did not provide an ordered basic block,
-  // create one to lazily compute and cache instruction
-  // positions inside a BB. This is used to provide fast queries for relative
-  // position between two instructions in a BB and can be used by
-  // AliasAnalysis::callCapturesBefore.
-  OrderedBasicBlock OBBTmp(BB);
-  if (!OBB)
-    OBB = &OBBTmp;
-
   // Return "true" if and only if the instruction I is either a non-simple
   // load or a non-simple store.
   auto isNonSimpleLoadOrStore = [](Instruction *I) -> bool {
@@ -609,7 +597,7 @@
     ModRefInfo MR = AA.getModRefInfo(Inst, MemLoc);
     // If necessary, perform additional analysis.
     if (isModAndRefSet(MR))
-      MR = AA.callCapturesBefore(Inst, MemLoc, &DT, OBB);
+      MR = AA.callCapturesBefore(Inst, MemLoc, &DT);
     switch (clearMust(MR)) {
     case ModRefInfo::NoModRef:
       // If the call has no effect on the queried pointer, just ignore it.
@@ -635,8 +623,7 @@
   return MemDepResult::getNonFuncLocal();
 }
 
-MemDepResult MemoryDependenceResults::getDependency(Instruction *QueryInst,
-                                                    OrderedBasicBlock *OBB) {
+MemDepResult MemoryDependenceResults::getDependency(Instruction *QueryInst) {
   Instruction *ScanPos = QueryInst;
 
   // Check for a cached result
@@ -676,7 +663,7 @@
 
       LocalCache =
           getPointerDependencyFrom(MemLoc, isLoad, ScanPos->getIterator(),
-                                   QueryParent, QueryInst, nullptr, OBB);
+                                   QueryParent, QueryInst, nullptr);
     } else if (auto *QueryCall = dyn_cast<CallBase>(QueryInst)) {
       bool isReadOnly = AA.onlyReadsMemory(QueryCall);
       LocalCache = getCallDependencyFrom(QueryCall, isReadOnly,
diff --git a/llvm/lib/Analysis/OrderedBasicBlock.cpp b/llvm/lib/Analysis/OrderedBasicBlock.cpp
deleted file mode 100644
--- a/llvm/lib/Analysis/OrderedBasicBlock.cpp
+++ /dev/null
@@ -1,111 +0,0 @@
-//===- OrderedBasicBlock.cpp --------------------------------- -*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-// This file implements the OrderedBasicBlock class. OrderedBasicBlock
-// maintains an interface where clients can query if one instruction comes
-// before another in a BasicBlock. Since BasicBlock currently lacks a reliable
-// way to query relative position between instructions one can use
-// OrderedBasicBlock to do such queries. OrderedBasicBlock is lazily built on a
-// source BasicBlock and maintains an internal Instruction -> Position map. A
-// OrderedBasicBlock instance should be discarded whenever the source
-// BasicBlock changes.
-//
-// It's currently used by the CaptureTracker in order to find relative
-// positions of a pair of instructions inside a BasicBlock.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Analysis/OrderedBasicBlock.h"
-#include "llvm/IR/Instruction.h"
-using namespace llvm;
-
-OrderedBasicBlock::OrderedBasicBlock(const BasicBlock *BasicB)
-    : NextInstPos(0), BB(BasicB) {
-  LastInstFound = BB->end();
-}
-
-/// Given no cached results, find if \p A comes before \p B in \p BB.
-/// Cache and number out instruction while walking \p BB.
-bool OrderedBasicBlock::comesBefore(const Instruction *A,
-                                    const Instruction *B) {
-  const Instruction *Inst = nullptr;
-  assert(!(LastInstFound == BB->end() && NextInstPos != 0) &&
-         "Instruction supposed to be in NumberedInsts");
-  assert(A->getParent() == BB && "Instruction supposed to be in the block!");
-  assert(B->getParent() == BB && "Instruction supposed to be in the block!");
-
-  // Start the search with the instruction found in the last lookup round.
-  auto II = BB->begin();
-  auto IE = BB->end();
-  if (LastInstFound != IE)
-    II = std::next(LastInstFound);
-
-  // Number all instructions up to the point where we find 'A' or 'B'.
-  for (; II != IE; ++II) {
-    Inst = cast<Instruction>(II);
-    NumberedInsts[Inst] = NextInstPos++;
-    if (Inst == A || Inst == B)
-      break;
-  }
-
-  assert(II != IE && "Instruction not found?");
-  assert((Inst == A || Inst == B) && "Should find A or B");
-  LastInstFound = II;
-  return Inst != B;
-}
-
-/// Find out whether \p A dominates \p B, meaning whether \p A
-/// comes before \p B in \p BB. This is a simplification that considers
-/// cached instruction positions and ignores other basic blocks, being
-/// only relevant to compare relative instructions positions inside \p BB.
-bool OrderedBasicBlock::dominates(const Instruction *A, const Instruction *B) {
-  assert(A->getParent() == B->getParent() &&
-         "Instructions must be in the same basic block!");
-  assert(A->getParent() == BB && "Instructions must be in the tracked block!");
-
-  // First we lookup the instructions. If they don't exist, lookup will give us
-  // back ::end(). If they both exist, we compare the numbers. Otherwise, if NA
-  // exists and NB doesn't, it means NA must come before NB because we would
-  // have numbered NB as well if it didn't. The same is true for NB. If it
-  // exists, but NA does not, NA must come after it. If neither exist, we need
-  // to number the block and cache the results (by calling comesBefore).
-  auto NAI = NumberedInsts.find(A);
-  auto NBI = NumberedInsts.find(B);
-  if (NAI != NumberedInsts.end() && NBI != NumberedInsts.end())
-    return NAI->second < NBI->second;
-  if (NAI != NumberedInsts.end())
-    return true;
-  if (NBI != NumberedInsts.end())
-    return false;
-
-  return comesBefore(A, B);
-}
-
-void OrderedBasicBlock::eraseInstruction(const Instruction *I) {
-  if (LastInstFound != BB->end() && I == &*LastInstFound) {
-    if (LastInstFound == BB->begin()) {
-      LastInstFound = BB->end();
-      NextInstPos = 0;
-    } else
-      LastInstFound--;
-  }
-
-  NumberedInsts.erase(I);
-}
-
-void OrderedBasicBlock::replaceInstruction(const Instruction *Old,
-                                           const Instruction *New) {
-  auto OI = NumberedInsts.find(Old);
-  if (OI == NumberedInsts.end())
-    return;
-
-  NumberedInsts.insert({New, OI->second});
-  if (LastInstFound != BB->end() && Old == &*LastInstFound)
-    LastInstFound = New->getIterator();
-  NumberedInsts.erase(Old);
-}
diff --git a/llvm/lib/Analysis/OrderedInstructions.cpp b/llvm/lib/Analysis/OrderedInstructions.cpp
--- a/llvm/lib/Analysis/OrderedInstructions.cpp
+++ b/llvm/lib/Analysis/OrderedInstructions.cpp
@@ -18,16 +18,11 @@
   assert(InstA->getParent() == InstB->getParent() &&
          "Instructions must be in the same basic block");
 
-  const BasicBlock *IBB = InstA->getParent();
-  auto OBB = OBBMap.find(IBB);
-  if (OBB == OBBMap.end())
-    OBB = OBBMap.insert({IBB, std::make_unique<OrderedBasicBlock>(IBB)}).first;
-  return OBB->second->dominates(InstA, InstB);
+  return InstA->comesBefore(InstB);
 }
 
-/// Given 2 instructions, use OrderedBasicBlock to check for dominance relation
-/// if the instructions are in the same basic block, Otherwise, use dominator
-/// tree.
+/// Given 2 instructions, check for dominance relation if the instructions are
+/// in the same basic block. Otherwise, use dominator tree.
 bool OrderedInstructions::dominates(const Instruction *InstA,
                                     const Instruction *InstB) const {
   // Use ordered basic block to do dominance check in case the 2 instructions
diff --git a/llvm/lib/IR/BasicBlock.cpp b/llvm/lib/IR/BasicBlock.cpp
--- a/llvm/lib/IR/BasicBlock.cpp
+++ b/llvm/lib/IR/BasicBlock.cpp
@@ -33,6 +33,10 @@
   return getType()->getContext();
 }
 
+template <> void llvm::invalidateParentIListOrdering(BasicBlock *BB) {
+  BB->invalidateOrders();
+}
+
 // Explicit instantiation of SymbolTableListTraits since some of the methods
 // are not in the public header file...
 template class llvm::SymbolTableListTraits<Instruction>;
@@ -61,6 +65,8 @@
 }
 
 BasicBlock::~BasicBlock() {
+  validateInstrOrdering();
+
   // If the address of the block is taken and it is being deleted (e.g. because
   // it is dead), this means that there is either a dangling constant expr
   // hanging off the block, or an undefined use of the block (source code
@@ -506,3 +512,29 @@
     ++It;
   return It;
 }
+
+void BasicBlock::renumberInstructions() {
+  unsigned Order = 0;
+  for (Instruction &I : *this)
+    I.Order = Order++;
+
+  // Set the bit to indicate that the instruction order valid and cached.
+  BasicBlockBits Bits = getBasicBlockBits();
+  Bits.InstrOrderValid = true;
+  setBasicBlockBits(Bits);
+}
+
+#ifndef NDEBUG
+/// In asserts builds, this checks the numbering. In non-asserts builds, it
+/// is defined as an inline function returning true in BasicBlock.h.
+void BasicBlock::validateInstrOrdering() const {
+  if (!isInstrOrderValid())
+    return;
+  const Instruction *Prev = nullptr;
+  for (const Instruction &I : *this) {
+    assert((!Prev || Prev->comesBefore(&I)) &&
+           "cached instruction ordering is incorrect");
+    Prev = &I;
+  }
+}
+#endif
diff --git a/llvm/lib/IR/Instruction.cpp b/llvm/lib/IR/Instruction.cpp
--- a/llvm/lib/IR/Instruction.cpp
+++ b/llvm/lib/IR/Instruction.cpp
@@ -97,6 +97,15 @@
   BB.getInstList().splice(I, getParent()->getInstList(), getIterator());
 }
 
+bool Instruction::comesBefore(const Instruction *Other) const {
+  assert(Parent && Other->Parent &&
+         "instructions without BB parents have no order");
+  assert(Parent == Other->Parent && "cross-BB instruction order comparison");
+  if (!Parent->isInstrOrderValid())
+    Parent->renumberInstructions();
+  return Order < Other->Order;
+}
+
 void Instruction::setHasNoUnsignedWrap(bool b) {
   cast<OverflowingBinaryOperator>(this)->setHasNoUnsignedWrap(b);
 }
diff --git a/llvm/lib/IR/SymbolTableListTraitsImpl.h b/llvm/lib/IR/SymbolTableListTraitsImpl.h
--- a/llvm/lib/IR/SymbolTableListTraitsImpl.h
+++ b/llvm/lib/IR/SymbolTableListTraitsImpl.h
@@ -20,6 +20,11 @@
 
 namespace llvm {
 
+/// Notify basic blocks when an instruction is inserted.
+template <typename ParentClass>
+inline void invalidateParentIListOrdering(ParentClass *Parent) {}
+template <> void invalidateParentIListOrdering(BasicBlock *BB);
+
 /// setSymTabObject - This is called when (f.e.) the parent of a basic block
 /// changes.  This requires us to remove all the instruction symtab entries from
 /// the current function and reinsert them into the new function.
@@ -64,6 +69,7 @@
   assert(!V->getParent() && "Value already in a container!!");
   ItemParentClass *Owner = getListOwner();
   V->setParent(Owner);
+  invalidateParentIListOrdering(Owner);
   if (V->hasName())
     if (ValueSymbolTable *ST = getSymTab(Owner))
       ST->reinsertValue(V);
@@ -81,8 +87,13 @@
 template <typename ValueSubClass>
 void SymbolTableListTraits<ValueSubClass>::transferNodesFromList(
     SymbolTableListTraits &L2, iterator first, iterator last) {
-  // We only have to do work here if transferring instructions between BBs
-  ItemParentClass *NewIP = getListOwner(), *OldIP = L2.getListOwner();
+  // Transfering nodes, even within the same BB, invalidates the ordering. The
+  // list that we removed the nodes from still has a valid ordering.
+  ItemParentClass *NewIP = getListOwner();
+  invalidateParentIListOrdering(NewIP);
+
+  // Nothing else needs to be done if we're reording nodes within the same list.
+  ItemParentClass *OldIP = L2.getListOwner();
   if (NewIP == OldIP)
     return;
 
diff --git a/llvm/lib/Target/ARM/ARMParallelDSP.cpp b/llvm/lib/Target/ARM/ARMParallelDSP.cpp
--- a/llvm/lib/Target/ARM/ARMParallelDSP.cpp
+++ b/llvm/lib/Target/ARM/ARMParallelDSP.cpp
@@ -20,7 +20,6 @@
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/LoopAccessAnalysis.h"
-#include "llvm/Analysis/OrderedBasicBlock.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicsARM.h"
@@ -352,7 +351,6 @@
   SmallVector<Instruction*, 8> Writes;
   LoadPairs.clear();
   WideLoads.clear();
-  OrderedBasicBlock OrderedBB(BB);
 
   // Collect loads and instruction that may write to memory. For now we only
   // record loads which are simple, sign-extended and have a single user.
@@ -384,7 +382,7 @@
       if (!isModOrRefSet(intersectModRef(AA->getModRefInfo(Write, ReadLoc),
           ModRefInfo::ModRef)))
         continue;
-      if (OrderedBB.dominates(Write, Read))
+      if (Write->comesBefore(Read))
         RAWDeps[Read].insert(Write);
     }
   }
@@ -392,8 +390,9 @@
   // Check whether there's not a write between the two loads which would
   // prevent them from being safely merged.
   auto SafeToPair = [&](LoadInst *Base, LoadInst *Offset) {
-    LoadInst *Dominator = OrderedBB.dominates(Base, Offset) ? Base : Offset;
-    LoadInst *Dominated = OrderedBB.dominates(Base, Offset) ? Offset : Base;
+    bool BaseFirst = Base->comesBefore(Offset);
+    LoadInst *Dominator = BaseFirst ? Base : Offset;
+    LoadInst *Dominated = BaseFirst ? Offset : Base;
 
     if (RAWDeps.count(Dominated)) {
       InstSet &WritesBefore = RAWDeps[Dominated];
@@ -401,7 +400,7 @@
       for (auto Before : WritesBefore) {
         // We can't move the second load backward, past a write, to merge
         // with the first load.
-        if (OrderedBB.dominates(Dominator, Before))
+        if (Dominator->comesBefore(Before))
           return false;
       }
     }
@@ -705,12 +704,11 @@
   }
 
   // Roughly sort the mul pairs in their program order.
-  OrderedBasicBlock OrderedBB(R.getRoot()->getParent());
-  llvm::sort(R.getMulPairs(), [&OrderedBB](auto &PairA, auto &PairB) {
-               const Instruction *A = PairA.first->Root;
-               const Instruction *B = PairB.first->Root;
-               return OrderedBB.dominates(A, B);
-             });
+  llvm::sort(R.getMulPairs(), [](auto &PairA, auto &PairB) {
+    const Instruction *A = PairA.first->Root;
+    const Instruction *B = PairB.first->Root;
+    return A->comesBefore(B);
+  });
 
   IntegerType *Ty = IntegerType::get(M->getContext(), 32);
   for (auto &Pair : R.getMulPairs()) {
diff --git a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
--- a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
+++ b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
@@ -31,7 +31,6 @@
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
-#include "llvm/Analysis/OrderedBasicBlock.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
@@ -118,7 +117,7 @@
 static void
 deleteDeadInstruction(Instruction *I, BasicBlock::iterator *BBI,
                       MemoryDependenceResults &MD, const TargetLibraryInfo &TLI,
-                      InstOverlapIntervalsTy &IOL, OrderedBasicBlock &OBB,
+                      InstOverlapIntervalsTy &IOL,
                       MapVector<Instruction *, bool> &ThrowableInst,
                       SmallSetVector<const Value *, 16> *ValueSet = nullptr) {
   SmallVector<Instruction*, 32> NowDeadInsts;
@@ -161,7 +160,6 @@
 
     if (ValueSet) ValueSet->remove(DeadInst);
     IOL.erase(DeadInst);
-    OBB.eraseInstruction(DeadInst);
 
     if (NewIter == DeadInst->getIterator())
       NewIter = DeadInst->eraseFromParent();
@@ -687,7 +685,7 @@
 static bool handleFree(CallInst *F, AliasAnalysis *AA,
                        MemoryDependenceResults *MD, DominatorTree *DT,
                        const TargetLibraryInfo *TLI,
-                       InstOverlapIntervalsTy &IOL, OrderedBasicBlock &OBB,
+                       InstOverlapIntervalsTy &IOL,
                        MapVector<Instruction *, bool> &ThrowableInst) {
   bool MadeChange = false;
 
@@ -722,7 +720,7 @@
 
       // DCE instructions only used to calculate that store.
       BasicBlock::iterator BBI(Dependency);
-      deleteDeadInstruction(Dependency, &BBI, *MD, *TLI, IOL, OBB,
+      deleteDeadInstruction(Dependency, &BBI, *MD, *TLI, IOL,
                             ThrowableInst);
       ++NumFastStores;
       MadeChange = true;
@@ -780,7 +778,7 @@
 static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA,
                            MemoryDependenceResults *MD,
                            const TargetLibraryInfo *TLI,
-                           InstOverlapIntervalsTy &IOL, OrderedBasicBlock &OBB,
+                           InstOverlapIntervalsTy &IOL,
                            MapVector<Instruction *, bool> &ThrowableInst) {
   bool MadeChange = false;
 
@@ -842,7 +840,7 @@
                    << '\n');
 
         // DCE instructions only used to calculate that store.
-        deleteDeadInstruction(Dead, &BBI, *MD, *TLI, IOL, OBB, ThrowableInst,
+        deleteDeadInstruction(Dead, &BBI, *MD, *TLI, IOL, ThrowableInst,
                               &DeadStackObjects);
         ++NumFastStores;
         MadeChange = true;
@@ -854,7 +852,7 @@
     if (isInstructionTriviallyDead(&*BBI, TLI)) {
       LLVM_DEBUG(dbgs() << "DSE: Removing trivially dead instruction:\n  DEAD: "
                         << *&*BBI << '\n');
-      deleteDeadInstruction(&*BBI, &BBI, *MD, *TLI, IOL, OBB, ThrowableInst,
+      deleteDeadInstruction(&*BBI, &BBI, *MD, *TLI, IOL, ThrowableInst,
                             &DeadStackObjects);
       ++NumFastOther;
       MadeChange = true;
@@ -1061,7 +1059,6 @@
                                const DataLayout &DL,
                                const TargetLibraryInfo *TLI,
                                InstOverlapIntervalsTy &IOL,
-                               OrderedBasicBlock &OBB,
                                MapVector<Instruction *, bool> &ThrowableInst) {
   // Must be a store instruction.
   StoreInst *SI = dyn_cast<StoreInst>(Inst);
@@ -1078,7 +1075,7 @@
           dbgs() << "DSE: Remove Store Of Load from same pointer:\n  LOAD: "
                  << *DepLoad << "\n  STORE: " << *SI << '\n');
 
-      deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, OBB, ThrowableInst);
+      deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, ThrowableInst);
       ++NumRedundantStores;
       return true;
     }
@@ -1096,7 +1093,7 @@
           dbgs() << "DSE: Remove null store to the calloc'ed object:\n  DEAD: "
                  << *Inst << "\n  OBJECT: " << *UnderlyingPointer << '\n');
 
-      deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, OBB, ThrowableInst);
+      deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, ThrowableInst);
       ++NumRedundantStores;
       return true;
     }
@@ -1110,7 +1107,6 @@
   const DataLayout &DL = BB.getModule()->getDataLayout();
   bool MadeChange = false;
 
-  OrderedBasicBlock OBB(&BB);
   MapVector<Instruction *, bool> ThrowableInst;
 
   // A map of interval maps representing partially-overwritten value parts.
@@ -1120,7 +1116,7 @@
   for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
     // Handle 'free' calls specially.
     if (CallInst *F = isFreeCall(&*BBI, TLI)) {
-      MadeChange |= handleFree(F, AA, MD, DT, TLI, IOL, OBB, ThrowableInst);
+      MadeChange |= handleFree(F, AA, MD, DT, TLI, IOL, ThrowableInst);
       // Increment BBI after handleFree has potentially deleted instructions.
       // This ensures we maintain a valid iterator.
       ++BBI;
@@ -1139,14 +1135,14 @@
       continue;
 
     // eliminateNoopStore will update in iterator, if necessary.
-    if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL, OBB,
+    if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL,
                            ThrowableInst)) {
       MadeChange = true;
       continue;
     }
 
     // If we find something that writes memory, get its memory dependence.
-    MemDepResult InstDep = MD->getDependency(Inst, &OBB);
+    MemDepResult InstDep = MD->getDependency(Inst);
 
     // Ignore any store where we can't find a local dependence.
     // FIXME: cross-block DSE would be fun. :)
@@ -1197,7 +1193,7 @@
       // If the underlying object is a non-escaping memory allocation, any store
       // to it is dead along the unwind edge. Otherwise, we need to preserve
       // the store.
-      if (LastThrowing && OBB.dominates(DepWrite, LastThrowing)) {
+      if (LastThrowing && DepWrite->comesBefore(LastThrowing)) {
         const Value* Underlying = GetUnderlyingObject(DepLoc.Ptr, DL);
         bool IsStoreDeadOnUnwind = isa<AllocaInst>(Underlying);
         if (!IsStoreDeadOnUnwind) {
@@ -1228,13 +1224,13 @@
                             << "\n  KILLER: " << *Inst << '\n');
 
           // Delete the store and now-dead instructions that feed it.
-          deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL, OBB,
+          deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL,
                                 ThrowableInst);
           ++NumFastStores;
           MadeChange = true;
 
           // We erased DepWrite; start over.
-          InstDep = MD->getDependency(Inst, &OBB);
+          InstDep = MD->getDependency(Inst);
           continue;
         } else if ((OR == OW_End && isShortenableAtTheEnd(DepWrite)) ||
                    ((OR == OW_Begin &&
@@ -1307,13 +1303,10 @@
             SI->copyMetadata(*DepWrite, MDToKeep);
             ++NumModifiedStores;
 
-            // Remove earlier, wider, store
-            OBB.replaceInstruction(DepWrite, SI);
-
             // Delete the old stores and now-dead instructions that feed them.
-            deleteDeadInstruction(Inst, &BBI, *MD, *TLI, IOL, OBB,
+            deleteDeadInstruction(Inst, &BBI, *MD, *TLI, IOL,
                                   ThrowableInst);
-            deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL, OBB,
+            deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL,
                                   ThrowableInst);
             MadeChange = true;
 
@@ -1349,7 +1342,7 @@
   // If this block ends in a return, unwind, or unreachable, all allocas are
   // dead at its end, which means stores to them are also dead.
   if (BB.getTerminator()->getNumSuccessors() == 0)
-    MadeChange |= handleEndBlock(BB, AA, MD, TLI, IOL, OBB, ThrowableInst);
+    MadeChange |= handleEndBlock(BB, AA, MD, TLI, IOL, ThrowableInst);
 
   return MadeChange;
 }
diff --git a/llvm/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp b/llvm/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp
--- a/llvm/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp
+++ b/llvm/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp
@@ -50,7 +50,6 @@
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/MemoryLocation.h"
-#include "llvm/Analysis/OrderedBasicBlock.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
@@ -502,7 +501,6 @@
 }
 
 void Vectorizer::reorder(Instruction *I) {
-  OrderedBasicBlock OBB(I->getParent());
   SmallPtrSet<Instruction *, 16> InstructionsToMove;
   SmallVector<Instruction *, 16> Worklist;
 
@@ -520,7 +518,7 @@
       if (IM->getParent() != I->getParent())
         continue;
 
-      if (!OBB.dominates(IM, I)) {
+      if (!IM->comesBefore(I)) {
         InstructionsToMove.insert(IM);
         Worklist.push_back(IM);
       }
@@ -636,8 +634,6 @@
     }
   }
 
-  OrderedBasicBlock OBB(Chain[0]->getParent());
-
   // Loop until we find an instruction in ChainInstrs that we can't vectorize.
   unsigned ChainInstrIdx = 0;
   Instruction *BarrierMemoryInstr = nullptr;
@@ -647,14 +643,14 @@
 
     // If a barrier memory instruction was found, chain instructions that follow
     // will not be added to the valid prefix.
-    if (BarrierMemoryInstr && OBB.dominates(BarrierMemoryInstr, ChainInstr))
+    if (BarrierMemoryInstr && BarrierMemoryInstr->comesBefore(ChainInstr))
       break;
 
     // Check (in BB order) if any instruction prevents ChainInstr from being
     // vectorized. Find and store the first such "conflicting" instruction.
     for (Instruction *MemInstr : MemoryInstrs) {
       // If a barrier memory instruction was found, do not check past it.
-      if (BarrierMemoryInstr && OBB.dominates(BarrierMemoryInstr, MemInstr))
+      if (BarrierMemoryInstr && BarrierMemoryInstr->comesBefore(MemInstr))
         break;
 
       auto *MemLoad = dyn_cast<LoadInst>(MemInstr);
@@ -673,12 +669,12 @@
       // vectorize it (the vectorized load is inserted at the location of the
       // first load in the chain).
       if (isa<StoreInst>(MemInstr) && ChainLoad &&
-          (IsInvariantLoad(ChainLoad) || OBB.dominates(ChainLoad, MemInstr)))
+          (IsInvariantLoad(ChainLoad) || ChainLoad->comesBefore(MemInstr)))
         continue;
 
       // Same case, but in reverse.
       if (MemLoad && isa<StoreInst>(ChainInstr) &&
-          (IsInvariantLoad(MemLoad) || OBB.dominates(MemLoad, ChainInstr)))
+          (IsInvariantLoad(MemLoad) || MemLoad->comesBefore(ChainInstr)))
         continue;
 
       if (!AA.isNoAlias(MemoryLocation::get(MemInstr),
@@ -704,7 +700,7 @@
     // the basic block.
     if (IsLoadChain && BarrierMemoryInstr) {
       // The BarrierMemoryInstr is a store that precedes ChainInstr.
-      assert(OBB.dominates(BarrierMemoryInstr, ChainInstr));
+      assert(BarrierMemoryInstr->comesBefore(ChainInstr));
       break;
     }
   }
diff --git a/llvm/unittests/Analysis/CMakeLists.txt b/llvm/unittests/Analysis/CMakeLists.txt
--- a/llvm/unittests/Analysis/CMakeLists.txt
+++ b/llvm/unittests/Analysis/CMakeLists.txt
@@ -25,7 +25,6 @@
   LoopInfoTest.cpp
   MemoryBuiltinsTest.cpp
   MemorySSATest.cpp
-  OrderedBasicBlockTest.cpp
   OrderedInstructionsTest.cpp
   PhiValuesTest.cpp
   ProfileSummaryInfoTest.cpp
diff --git a/llvm/unittests/Analysis/CaptureTrackingTest.cpp b/llvm/unittests/Analysis/CaptureTrackingTest.cpp
--- a/llvm/unittests/Analysis/CaptureTrackingTest.cpp
+++ b/llvm/unittests/Analysis/CaptureTrackingTest.cpp
@@ -7,7 +7,6 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/CaptureTracking.h"
-#include "llvm/Analysis/OrderedBasicBlock.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
@@ -62,14 +61,13 @@
 
     BasicBlock *EntryBB = &F->getEntryBlock();
     DominatorTree DT(*F);
-    OrderedBasicBlock OBB(EntryBB);
 
     Instruction *Ret = EntryBB->getTerminator();
     ASSERT_TRUE(isa<ReturnInst>(Ret));
-    ASSERT_FALSE(PointerMayBeCapturedBefore(Arg, true, true, Ret, &DT, false, 
-                                            &OBB, FalseMaxUsesLimit));
+    ASSERT_FALSE(PointerMayBeCapturedBefore(Arg, true, true, Ret, &DT, false,
+                                            FalseMaxUsesLimit));
     ASSERT_TRUE(PointerMayBeCapturedBefore(Arg, true, true, Ret, &DT, false,
-                                           &OBB, TrueMaxUsesLimit));
+                                           TrueMaxUsesLimit));
   };
 
   Test("test_few_uses", 6, 4);
diff --git a/llvm/unittests/Analysis/OrderedBasicBlockTest.cpp b/llvm/unittests/Analysis/OrderedBasicBlockTest.cpp
deleted file mode 100644
--- a/llvm/unittests/Analysis/OrderedBasicBlockTest.cpp
+++ /dev/null
@@ -1,57 +0,0 @@
-//===- OrderedBasicBlockTest.cpp - OrderedBasicBlock unit tests -----------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Analysis/OrderedBasicBlock.h"
-#include "llvm/AsmParser/Parser.h"
-#include "llvm/IR/BasicBlock.h"
-#include "llvm/IR/Function.h"
-#include "llvm/IR/LLVMContext.h"
-#include "llvm/IR/Module.h"
-#include "llvm/Support/DataTypes.h"
-#include "llvm/Support/SourceMgr.h"
-#include "gtest/gtest.h"
-
-namespace llvm {
-namespace {
-
-class OrderedBasicBlockTest : public testing::Test {
-protected:
-  LLVMContext C;
-
-  std::unique_ptr<Module> makeLLVMModule() {
-    const char *ModuleString = R"(define i32 @f(i32 %x) {
-                                    %add = add i32 %x, 42
-                                    ret i32 %add
-                                  })";
-    SMDiagnostic Err;
-    auto foo = parseAssemblyString(ModuleString, Err, C);
-    return foo;
-  }
-};
-
-TEST_F(OrderedBasicBlockTest, Basic) {
-  auto M = makeLLVMModule();
-  Function *F = M->getFunction("f");
-  BasicBlock::iterator I = F->front().begin();
-  Instruction *Add = &*I++;
-  Instruction *Ret = &*I++;
-
-  OrderedBasicBlock OBB(&F->front());
-  // Intentionally duplicated to verify cached and uncached are the same.
-  EXPECT_FALSE(OBB.dominates(Add, Add));
-  EXPECT_FALSE(OBB.dominates(Add, Add));
-  EXPECT_TRUE(OBB.dominates(Add, Ret));
-  EXPECT_TRUE(OBB.dominates(Add, Ret));
-  EXPECT_FALSE(OBB.dominates(Ret, Add));
-  EXPECT_FALSE(OBB.dominates(Ret, Add));
-  EXPECT_FALSE(OBB.dominates(Ret, Ret));
-  EXPECT_FALSE(OBB.dominates(Ret, Ret));
-}
-
-} // end anonymous namespace
-} // end namespace llvm
diff --git a/llvm/unittests/IR/BasicBlockTest.cpp b/llvm/unittests/IR/BasicBlockTest.cpp
--- a/llvm/unittests/IR/BasicBlockTest.cpp
+++ b/llvm/unittests/IR/BasicBlockTest.cpp
@@ -8,11 +8,13 @@
 
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/NoFolder.h"
+#include "llvm/Support/SourceMgr.h"
 #include "gmock/gmock-matchers.h"
 #include "gtest/gtest.h"
 #include <memory>
@@ -129,5 +131,130 @@
   delete V;
 }
 
+TEST(BasicBlockTest, ComesBefore) {
+  const char *ModuleString = R"(define i32 @f(i32 %x) {
+                                  %add = add i32 %x, 42
+                                  ret i32 %add
+                                })";
+  LLVMContext Ctx;
+  SMDiagnostic Err;
+  auto M = parseAssemblyString(ModuleString, Err, Ctx);
+  ASSERT_TRUE(M.get());
+
+  Function *F = M->getFunction("f");
+  BasicBlock &BB = F->front();
+  BasicBlock::iterator I = BB.begin();
+  Instruction *Add = &*I++;
+  Instruction *Ret = &*I++;
+
+  // Intentionally duplicated to verify cached and uncached are the same.
+  EXPECT_FALSE(BB.isInstrOrderValid());
+  EXPECT_FALSE(Add->comesBefore(Add));
+  EXPECT_TRUE(BB.isInstrOrderValid());
+  EXPECT_FALSE(Add->comesBefore(Add));
+  BB.invalidateOrders();
+  EXPECT_FALSE(BB.isInstrOrderValid());
+  EXPECT_TRUE(Add->comesBefore(Ret));
+  EXPECT_TRUE(BB.isInstrOrderValid());
+  EXPECT_TRUE(Add->comesBefore(Ret));
+  BB.invalidateOrders();
+  EXPECT_FALSE(Ret->comesBefore(Add));
+  EXPECT_FALSE(Ret->comesBefore(Add));
+  BB.invalidateOrders();
+  EXPECT_FALSE(Ret->comesBefore(Ret));
+  EXPECT_FALSE(Ret->comesBefore(Ret));
+}
+
+class InstrOrderInvalidationTest : public ::testing::Test {
+protected:
+  void SetUp() override {
+    M.reset(new Module("MyModule", Ctx));
+    Nop = Intrinsic::getDeclaration(M.get(), Intrinsic::donothing);
+    FunctionType *FT = FunctionType::get(Type::getVoidTy(Ctx), {}, false);
+    Function *F = Function::Create(FT, Function::ExternalLinkage, "foo", *M);
+    BB = BasicBlock::Create(Ctx, "entry", F);
+
+    IRBuilder<> Builder(BB);
+    I1 = Builder.CreateCall(Nop);
+    I2 = Builder.CreateCall(Nop);
+    I3 = Builder.CreateCall(Nop);
+    Ret = Builder.CreateRetVoid();
+  }
+
+  LLVMContext Ctx;
+  std::unique_ptr<Module> M;
+  Function *Nop = nullptr;
+  BasicBlock *BB = nullptr;
+  Instruction *I1 = nullptr;
+  Instruction *I2 = nullptr;
+  Instruction *I3 = nullptr;
+  Instruction *Ret = nullptr;
+};
+
+TEST_F(InstrOrderInvalidationTest, InsertInvalidation) {
+  EXPECT_FALSE(BB->isInstrOrderValid());
+  EXPECT_TRUE(I1->comesBefore(I2));
+  EXPECT_TRUE(BB->isInstrOrderValid());
+  EXPECT_TRUE(I2->comesBefore(I3));
+  EXPECT_TRUE(I3->comesBefore(Ret));
+  EXPECT_TRUE(BB->isInstrOrderValid());
+
+  // Invalidate orders.
+  IRBuilder<> Builder(BB, I2->getIterator());
+  Instruction *I1a = Builder.CreateCall(Nop);
+  EXPECT_FALSE(BB->isInstrOrderValid());
+  EXPECT_TRUE(I1->comesBefore(I1a));
+  EXPECT_TRUE(BB->isInstrOrderValid());
+  EXPECT_TRUE(I1a->comesBefore(I2));
+  EXPECT_TRUE(I2->comesBefore(I3));
+  EXPECT_TRUE(I3->comesBefore(Ret));
+  EXPECT_TRUE(BB->isInstrOrderValid());
+}
+
+TEST_F(InstrOrderInvalidationTest, SpliceInvalidation) {
+  EXPECT_TRUE(I1->comesBefore(I2));
+  EXPECT_TRUE(I2->comesBefore(I3));
+  EXPECT_TRUE(I3->comesBefore(Ret));
+  EXPECT_TRUE(BB->isInstrOrderValid());
+
+  // Use Instruction::moveBefore, which uses splice.
+  I2->moveBefore(I1);
+  EXPECT_FALSE(BB->isInstrOrderValid());
+
+  EXPECT_TRUE(I2->comesBefore(I1));
+  EXPECT_TRUE(I1->comesBefore(I3));
+  EXPECT_TRUE(I3->comesBefore(Ret));
+  EXPECT_TRUE(BB->isInstrOrderValid());
+}
+
+TEST_F(InstrOrderInvalidationTest, RemoveNoInvalidation) {
+  // Cache the instruction order.
+  EXPECT_FALSE(BB->isInstrOrderValid());
+  EXPECT_TRUE(I1->comesBefore(I2));
+  EXPECT_TRUE(BB->isInstrOrderValid());
+
+  // Removing does not invalidate instruction order.
+  I2->removeFromParent();
+  I2->deleteValue();
+  I2 = nullptr;
+  EXPECT_TRUE(BB->isInstrOrderValid());
+  EXPECT_TRUE(I1->comesBefore(I3));
+  EXPECT_EQ(std::next(I1->getIterator()), I3->getIterator());
+}
+
+TEST_F(InstrOrderInvalidationTest, EraseNoInvalidation) {
+  // Cache the instruction order.
+  EXPECT_FALSE(BB->isInstrOrderValid());
+  EXPECT_TRUE(I1->comesBefore(I2));
+  EXPECT_TRUE(BB->isInstrOrderValid());
+
+  // Removing does not invalidate instruction order.
+  I2->eraseFromParent();
+  I2 = nullptr;
+  EXPECT_TRUE(BB->isInstrOrderValid());
+  EXPECT_TRUE(I1->comesBefore(I3));
+  EXPECT_EQ(std::next(I1->getIterator()), I3->getIterator());
+}
+
 } // End anonymous namespace.
 } // End llvm namespace.
diff --git a/llvm/utils/gn/secondary/llvm/lib/Analysis/BUILD.gn b/llvm/utils/gn/secondary/llvm/lib/Analysis/BUILD.gn
--- a/llvm/utils/gn/secondary/llvm/lib/Analysis/BUILD.gn
+++ b/llvm/utils/gn/secondary/llvm/lib/Analysis/BUILD.gn
@@ -84,7 +84,6 @@
     "ObjCARCAnalysisUtils.cpp",
     "ObjCARCInstKind.cpp",
     "OptimizationRemarkEmitter.cpp",
-    "OrderedBasicBlock.cpp",
     "OrderedInstructions.cpp",
     "PHITransAddr.cpp",
     "PhiValues.cpp",
diff --git a/llvm/utils/gn/secondary/llvm/unittests/Analysis/BUILD.gn b/llvm/utils/gn/secondary/llvm/unittests/Analysis/BUILD.gn
--- a/llvm/utils/gn/secondary/llvm/unittests/Analysis/BUILD.gn
+++ b/llvm/utils/gn/secondary/llvm/unittests/Analysis/BUILD.gn
@@ -27,7 +27,6 @@
     "LoopInfoTest.cpp",
     "MemoryBuiltinsTest.cpp",
     "MemorySSATest.cpp",
-    "OrderedBasicBlockTest.cpp",
     "OrderedInstructionsTest.cpp",
     "PhiValuesTest.cpp",
     "ProfileSummaryInfoTest.cpp",