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
@@ -644,19 +644,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
@@ -19,7 +19,6 @@
   class Use;
   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,
@@ -52,14 +51,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/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
@@ -388,7 +388,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's successors to refer to basic
   /// block \p New instead of to it.
@@ -415,16 +417,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
@@ -441,6 +488,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.
   //===--------------------------------------------------------------------===//
@@ -727,6 +738,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
@@ -541,16 +541,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;
 
@@ -566,8 +564,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
@@ -68,7 +68,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"
@@ -60,8 +59,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; }
@@ -74,9 +73,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.
         //
@@ -86,7 +83,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
@@ -137,7 +134,6 @@
       return true;
     }
 
-    OrderedBasicBlock *OrderedBB;
     const Instruction *BeforeHere;
     const DominatorTree *DT;
 
@@ -180,31 +176,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
@@ -103,18 +103,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"
@@ -487,12 +486,6 @@
 
   const DataLayout &DL = BB->getModule()->getDataLayout();
 
-  // Create a numbered basic block 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 OBB(BB);
-
   // 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 {
@@ -682,7 +675,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.
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,87 +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);
-}
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, 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
@@ -491,3 +497,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/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
@@ -1073,8 +1073,7 @@
   const DataLayout &DL = BB.getModule()->getDataLayout();
   bool MadeChange = false;
 
-  // FIXME: Maybe change this to use some abstraction like OrderedBasicBlock?
-  // The current OrderedBasicBlock can't deal with mutation at the moment.
+  // FIXME: Don't maintain our own ordering. Use Instruction::comesBefore.
   size_t LastThrowingInstIndex = 0;
   DenseMap<Instruction*, size_t> InstrOrdering;
   size_t InstrIndex = 1;
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
@@ -49,7 +49,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/Transforms/Utils/Local.h"
@@ -487,7 +486,6 @@
 }
 
 void Vectorizer::reorder(Instruction *I) {
-  OrderedBasicBlock OBB(I->getParent());
   SmallPtrSet<Instruction *, 16> InstructionsToMove;
   SmallVector<Instruction *, 16> Worklist;
 
@@ -505,7 +503,7 @@
       if (IM->getParent() != I->getParent())
         continue;
 
-      if (!OBB.dominates(IM, I)) {
+      if (!IM->comesBefore(I)) {
         InstructionsToMove.insert(IM);
         Worklist.push_back(IM);
       }
@@ -621,8 +619,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;
@@ -632,14 +628,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);
@@ -658,12 +654,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),
@@ -689,7 +685,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
@@ -22,7 +22,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>
@@ -126,5 +128,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.