diff --git a/clang/include/clang/Analysis/Analyses/Dominators.h b/clang/include/clang/Analysis/Analyses/Dominators.h
--- a/clang/include/clang/Analysis/Analyses/Dominators.h
+++ b/clang/include/clang/Analysis/Analyses/Dominators.h
@@ -31,6 +31,7 @@
 public:
   using ParentType = CFG;
   using BlockRef = CFGBlock *;
+  using InstructionRef = void;
   using ValueRef = void;
 
   static llvm::CfgBlockRef wrapRef(BlockRef block) {
diff --git a/llvm/include/llvm/CodeGen/MachineCfgTraits.h b/llvm/include/llvm/CodeGen/MachineCfgTraits.h
--- a/llvm/include/llvm/CodeGen/MachineCfgTraits.h
+++ b/llvm/include/llvm/CodeGen/MachineCfgTraits.h
@@ -27,11 +27,15 @@
 public:
   using ParentType = MachineFunction;
   using BlockRef = MachineBasicBlock *;
+  using InstructionRef = MachineInstr *;
   using ValueRef = Register;
 
   static CfgBlockRef wrapRef(BlockRef block) {
     return makeOpaque<CfgBlockRefTag>(block);
   }
+  static CfgInstructionRef wrapRef(InstructionRef instruction) {
+    return makeOpaque<CfgInstructionRefTag>(instruction);
+  }
   static CfgValueRef wrapRef(ValueRef value) {
     // Physical registers are unsupported by design.
     assert(!value.isValid() || value.isVirtual());
@@ -48,6 +52,9 @@
   static BlockRef unwrapRef(CfgBlockRef block) {
     return static_cast<BlockRef>(getOpaque(block));
   }
+  static InstructionRef unwrapRef(CfgInstructionRef instruction) {
+    return static_cast<InstructionRef>(getOpaque(instruction));
+  }
   static ValueRef unwrapRef(CfgValueRef value) {
     uintptr_t wrapped = reinterpret_cast<uintptr_t>(getOpaque(value));
     return Register(wrapped);
@@ -87,6 +94,12 @@
             const_blockref_iterator(function->end())};
   }
 
+  static bool comesBefore(MachineInstr *, MachineInstr *) {
+    // Currently no efficient implementation possible, so prefer not to
+    // provide one at all. We don't want to lay a subtle performance trap here.
+    llvm_unreachable("not implemented");
+  }
+
   static auto predecessors(MachineBasicBlock *block) {
     return block->predecessors();
   }
@@ -156,6 +169,7 @@
 
     void printBlockName(raw_ostream &out, MachineBasicBlock *block) const;
     void printValue(raw_ostream &out, Register value) const;
+    void printInstruction(raw_ostream &out, MachineInstr *instruction) const;
 
   private:
     MachineRegisterInfo *m_regInfo;
diff --git a/llvm/include/llvm/IR/CFG.h b/llvm/include/llvm/IR/CFG.h
--- a/llvm/include/llvm/IR/CFG.h
+++ b/llvm/include/llvm/IR/CFG.h
@@ -407,17 +407,24 @@
 public:
   using ParentType = Function;
   using BlockRef = BasicBlock *;
+  using InstructionRef = Instruction *;
   using ValueRef = Value *;
 
   static CfgBlockRef wrapRef(BlockRef block) {
     return makeOpaque<CfgBlockRefTag>(block);
   }
+  static CfgInstructionRef wrapRef(InstructionRef instruction) {
+    return makeOpaque<CfgInstructionRefTag>(instruction);
+  }
   static CfgValueRef wrapRef(ValueRef block) {
     return makeOpaque<CfgValueRefTag>(block);
   }
   static BlockRef unwrapRef(CfgBlockRef block) {
     return static_cast<BlockRef>(getOpaque(block));
   }
+  static InstructionRef unwrapRef(CfgInstructionRef instruction) {
+    return static_cast<InstructionRef>(getOpaque(instruction));
+  }
   static ValueRef unwrapRef(CfgValueRef block) {
     return static_cast<ValueRef>(getOpaque(block));
   }
@@ -460,6 +467,10 @@
     return {block_iterator(function->begin()), block_iterator(function->end())};
   }
 
+  static bool comesBefore(Instruction *lhs, Instruction *rhs) {
+    return lhs->comesBefore(rhs);
+  }
+
   struct value_iterator
       : iterator_adaptor_base<value_iterator, BasicBlock::iterator> {
     using Base = iterator_adaptor_base<value_iterator, BasicBlock::iterator>;
@@ -481,6 +492,7 @@
 
     void printBlockName(raw_ostream &out, BlockRef block) const;
     void printValue(raw_ostream &out, ValueRef value) const;
+    void printInstruction(raw_ostream &out, InstructionRef instruction) const;
 
   private:
     mutable std::unique_ptr<ModuleSlotTracker> m_moduleSlotTracker;
diff --git a/llvm/include/llvm/Support/CfgTraits.h b/llvm/include/llvm/Support/CfgTraits.h
--- a/llvm/include/llvm/Support/CfgTraits.h
+++ b/llvm/include/llvm/Support/CfgTraits.h
@@ -79,6 +79,9 @@
 class CfgBlockRefTag;
 using CfgBlockRef = CfgOpaqueType<CfgBlockRefTag>;
 
+class CfgInstructionRefTag;
+using CfgInstructionRef = CfgOpaqueType<CfgInstructionRefTag>;
+
 class CfgValueRefTag;
 using CfgValueRef = CfgOpaqueType<CfgValueRefTag>;
 
@@ -113,8 +116,10 @@
   //
   // - Static methods for converting BlockRef and ValueRef to and from
   //   static CfgBlockRef wrapRef(BlockRef);
+  //   static CfgInstructionRef wrapRef(InstructionRef);
   //   static CfgValueRef wrapRef(ValueRef);
   //   static BlockRef unwrapRef(CfgBlockRef);
+  //   static InstructionRef unwrapRef(CfgInstructionRef);
   //   static ValueRef unwrapRef(CfgValueRef);
 };
 
@@ -133,6 +138,7 @@
 class CfgTraits : public BaseTraits {
 public:
   using typename BaseTraits::BlockRef;
+  using typename BaseTraits::InstructionRef;
   using typename BaseTraits::ParentType;
   using typename BaseTraits::ValueRef;
 
@@ -159,6 +165,10 @@
   // a range of iterators dereferencing to ValueRef):
   //   static auto blockdefs(BlockRef block);
 
+  // Given two instructions in the same block, this returns true if lhs is
+  // strictly before rhs.
+  //   static bool comesBefore(InstructionRef lhs, InstructionRef rhs);
+
   // Get the block in which a given value is defined. Returns a null-like
   // BlockRef if the value is not defined in a block (e.g. it is a constant or
   // function argument).
@@ -168,6 +178,8 @@
   //   explicit Printer(const CfgTraits &traits);
   //   void printBlockName(raw_ostream &out, BlockRef block) const;
   //   void printValue(raw_ostream &out, ValueRef value) const;
+  //   void printInstruction(raw_ostream &out,
+  //                         InstructionRef instruction) const;
   // };
 
   ///@}
@@ -295,6 +307,9 @@
   virtual void appendBlocks(CfgParentRef parent,
                             SmallVectorImpl<CfgBlockRef> &list) const = 0;
 
+  virtual bool comesBefore(CfgInstructionRef lhs,
+                           CfgInstructionRef rhs) const = 0;
+
   virtual void appendPredecessors(CfgBlockRef block,
                                   SmallVectorImpl<CfgBlockRef> &list) const = 0;
   virtual void appendSuccessors(CfgBlockRef block,
@@ -331,6 +346,8 @@
 
   virtual void printBlockName(raw_ostream &out, CfgBlockRef block) const = 0;
   virtual void printValue(raw_ostream &out, CfgValueRef value) const = 0;
+  virtual void printInstruction(raw_ostream &out,
+                                CfgInstructionRef instruction) const = 0;
 
   Printable printableBlockName(CfgBlockRef block) const {
     return Printable(
@@ -340,6 +357,11 @@
     return Printable(
         [this, value](raw_ostream &out) { printValue(out, value); });
   }
+  Printable printableInstruction(CfgInstructionRef instruction) const {
+    return Printable([this, instruction](raw_ostream &out) {
+      printInstruction(out, instruction);
+    });
+  }
 };
 
 template <typename CfgTraitsT> class CfgPrinterImpl;
@@ -378,6 +400,11 @@
                 CfgTraits::wrapIterator(std::end(range)));
   }
 
+  bool comesBefore(CfgInstructionRef lhs, CfgInstructionRef rhs) const final {
+    return CfgTraits::comesBefore(CfgTraits::unwrapRef(lhs),
+                                  CfgTraits::unwrapRef(rhs));
+  }
+
   void appendPredecessors(CfgBlockRef block,
                           SmallVectorImpl<CfgBlockRef> &list) const final {
     auto range = CfgTraits::predecessors(CfgTraits::unwrapRef(block));
@@ -444,6 +471,11 @@
   void printValue(raw_ostream &out, CfgValueRef value) const final {
     CfgTraits::Printer::printValue(out, CfgTraits::unwrapRef(value));
   }
+  void printInstruction(raw_ostream &out,
+                        CfgInstructionRef instruction) const final {
+    CfgTraits::Printer::printInstruction(out,
+                                         CfgTraits::unwrapRef(instruction));
+  }
 };
 
 } // namespace llvm
diff --git a/llvm/lib/CodeGen/MachineCfgTraits.cpp b/llvm/lib/CodeGen/MachineCfgTraits.cpp
--- a/llvm/lib/CodeGen/MachineCfgTraits.cpp
+++ b/llvm/lib/CodeGen/MachineCfgTraits.cpp
@@ -24,6 +24,11 @@
   }
 }
 
+void MachineCfgTraits::Printer::printInstruction(
+    raw_ostream &out, MachineInstr *instruction) const {
+  instruction->print(out);
+}
+
 void MachineCfgTraits::Printer::printBlockName(raw_ostream &out,
                                                MachineBasicBlock *block) const {
   block->printName(out);
diff --git a/llvm/lib/IR/CFG.cpp b/llvm/lib/IR/CFG.cpp
--- a/llvm/lib/IR/CFG.cpp
+++ b/llvm/lib/IR/CFG.cpp
@@ -36,6 +36,11 @@
   }
 }
 
+void IrCfgTraits::Printer::printInstruction(raw_ostream &out,
+                                            InstructionRef instruction) const {
+  printValue(out, instruction);
+}
+
 void IrCfgTraits::Printer::printBlockName(raw_ostream &out,
                                           BlockRef block) const {
   if (block->hasName()) {
diff --git a/llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h b/llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
--- a/llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
+++ b/llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
@@ -27,6 +27,7 @@
 public:
   using ParentType = VPRegionBlock;
   using BlockRef = VPBlockBase *;
+  using InstructionRef = void;
   using ValueRef = void;
 
   static CfgBlockRef wrapRef(BlockRef block) {
diff --git a/mlir/include/mlir/IR/Dominance.h b/mlir/include/mlir/IR/Dominance.h
--- a/mlir/include/mlir/IR/Dominance.h
+++ b/mlir/include/mlir/IR/Dominance.h
@@ -20,6 +20,7 @@
 public:
   using ParentType = Region;
   using BlockRef = Block *;
+  using InstructionRef = void;
   using ValueRef = void;
 
   static llvm::CfgBlockRef wrapRef(BlockRef block) {