CfgTraits: add CfgInstructionRef

[nhaehnle]

Summary

In CFGs where a single instruction can define multiple values, the
distinction is significant.

Change-Id: Ic15e8e34428ea71023cd644739b1114cebab9594

[arsenm]

llvm/include/llvm/CodeGen/MachineCfgTraits.h

100

llvm_unreachable?

[nhaehnle]

• use llvm_unreachable

[nhaehnle]

llvm/include/llvm/CodeGen/MachineCfgTraits.h

100

Makes sense, done.

[arsenm]

LGTM

clang/include/clang/Analysis/Analyses/Dominators.h

 
 namespace clang {
 
 /// Partial CFG traits for MLIR's CFG, without a value type.
 class CfgTraitsBase : public llvm::CfgTraitsBase {
 public:
   using ParentType = CFG;
   using BlockRef = CFGBlock *;
+  using InstructionRef = void;
   using ValueRef = void;
 
   static llvm::CfgBlockRef wrapRef(BlockRef block) {
     return makeOpaque<llvm::CfgBlockRefTag>(block);
   }
   static BlockRef unwrapRef(llvm::CfgBlockRef block) {
     return static_cast<BlockRef>(getOpaque(block));
   }

llvm/include/llvm/CodeGen/MachineCfgTraits.h

 #include "llvm/Support/CfgTraits.h"
 
 namespace llvm {
 
 class MachineCfgTraitsBase : public CfgTraitsBase {
 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());
     uintptr_t wrapped = value.id();
     assert((wrapped != 0) == value.isValid());
 
     // Guard against producing values reserved for DenseMap markers. This is de
     // facto impossible, because it'd require 2^31 virtual registers to be in
     // use on a 32-bit architecture.
     assert(wrapped != (uintptr_t)-1 && wrapped != (uintptr_t)-2);
 
     return makeOpaque<CfgValueRefTag>(reinterpret_cast<void *>(wrapped));
   }
   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);
   }
 };
 
 /// \brief CFG traits for Machine IR in SSA form.
 class MachineCfgTraits
public:
   };
 
   static iterator_range<const_blockref_iterator>
   blocks(MachineFunction *function) {
     return {const_blockref_iterator(function->begin()),
             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();
   }
   static auto successors(MachineBasicBlock *block) {
     return block->successors();
   }
 
   /// Get the defining block of a value.
public:
   }
 
   struct Printer {
     explicit Printer(const MachineCfgTraits &traits)
         : m_regInfo(traits.m_regInfo) {}
 
     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;
   };
 };
 
 template <> struct CfgTraitsFor<MachineBasicBlock> {
   using CfgTraits = MachineCfgTraits;
 };
 
 } // namespace llvm
 
 #endif // LLVM_CODEGEN_MACHINECFGTRAITS_H

llvm/include/llvm/IR/CFG.h

 //===----------------------------------------------------------------------===//
 // LLVM IR CfgTraits
 //===----------------------------------------------------------------------===//
 
 class IrCfgTraitsBase : public CfgTraitsBase {
 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));
   }
 };
 
 /// \brief CFG traits for LLVM IR.
 class IrCfgTraits : public CfgTraits<IrCfgTraitsBase, IrCfgTraits> {
 public:
struct block_iterator
 
     BasicBlock *operator*() const { return &Base::operator*(); }
   };
 
   static iterator_range<block_iterator> blocks(Function *function) {
     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>;
 
     value_iterator() = default;
 
     explicit value_iterator(BasicBlock::iterator i) : Base(i) {}
 
     ValueRef operator*() const { return &Base::operator*(); }
   };
 
   static iterator_range<value_iterator> blockdefs(BlockRef block) {
     return {value_iterator(block->begin()), value_iterator(block->end())};
   }
 
   struct Printer {
     explicit Printer(const IrCfgTraits &);
     ~Printer();
 
     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;
 
     void ensureModuleSlotTracker(const Function &function) const;
   };
 };
 
 template <> struct CfgTraitsFor<BasicBlock> { using CfgTraits = IrCfgTraits; };
 
 } // end namespace llvm
 
 #endif // LLVM_IR_CFG_H

llvm/include/llvm/Support/CfgTraits.h

 };
 
 class CfgParentRefTag;
 using CfgParentRef = CfgOpaqueType<CfgParentRefTag>;
 
 class CfgBlockRefTag;
 using CfgBlockRef = CfgOpaqueType<CfgBlockRefTag>;
 
+class CfgInstructionRefTag;
+using CfgInstructionRef = CfgOpaqueType<CfgInstructionRefTag>;
+
 class CfgValueRefTag;
 using CfgValueRef = CfgOpaqueType<CfgValueRefTag>;
 
 /// \brief Base class for CFG traits
 ///
 /// Derive from this base class to define the mapping between opaque types and
 /// concrete CFG types. Then derive from \ref CfgTraits to implement
 /// operations such as traversal of the CFG.
public:
   // - The type of block references in the CFG, e.g. `llvm::BasicBlock *`
   //   using BlockRef = ...;
   //
   // - The type of value references in the CFG, e.g. `llvm::Value *`
   //   using ValueRef = ...;
   //
   // - 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);
 };
 
 /// \brief CFG traits
 ///
 /// Implement CFG traits by:
 ///  - Deriving from CfgTraitsBase to designate block and value types and
 ///    implementing wrapRef / unwrapRef
 ///  - Deriving from CfgTraits using CRTP and implement / override additional
 ///    methods for CFG traversal, printing, etc.
 ///
 /// This somewhat surprising two-step helps with the implementation of
 /// (un)wrapping_iterators.
 ///
 template <typename BaseTraits, typename FullTraits>
 class CfgTraits : public BaseTraits {
 public:
   using typename BaseTraits::BlockRef;
+  using typename BaseTraits::InstructionRef;
   using typename BaseTraits::ParentType;
   using typename BaseTraits::ValueRef;
 
   /// Functionality to be provided by implementations:
   ///@{
 
   // Constructor: initialize from a pointer to the parent.
   //   explicit CfgTraits(ParentType *parent);
public:
   // of iterators dereferencing to BlockRef):
   //   static auto predecessors(BlockRef block);
   //   static auto successors(BlockRef block);
 
   // Iterate over the values defined in a basic block in program order (return
   // 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).
   //   BlockRef getValueDefBlock(ValueRef value) const;
 
   // struct Printer {
   //   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;
   // };
 
   ///@}
 
   static CfgParentRef wrapRef(ParentType *parent) {
     return CfgParentRef{parent};
   }
 
public:
   /// explicitly pass a CfgPrinter where possible.
   virtual std::unique_ptr<CfgPrinter> makePrinter() const = 0;
 
   virtual CfgParentRef getBlockParent(CfgBlockRef block) const = 0;
 
   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,
                                 SmallVectorImpl<CfgBlockRef> &list) const = 0;
   virtual ArrayRef<CfgBlockRef>
   getPredecessors(CfgBlockRef block,
                   SmallVectorImpl<CfgBlockRef> &store) const = 0;
   virtual ArrayRef<CfgBlockRef>

 
 public:
   virtual ~CfgPrinter() {}
 
   const CfgInterface &interface() const { return m_iface; }
 
   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(
         [this, block](raw_ostream &out) { printBlockName(out, block); });
   }
   Printable printableValue(CfgValueRef value) const {
     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;
 
 /// \brief Implementation of type-erased "CFG traits"
 ///
 /// Note: Do not specialize this template; adjust the CfgTraits type instead
 /// where necessary.
public:
 
   void appendBlocks(CfgParentRef parent,
                     SmallVectorImpl<CfgBlockRef> &list) const final {
     auto range = CfgTraits::blocks(CfgTraits::unwrapRef(parent));
     list.insert(list.end(), CfgTraits::wrapIterator(std::begin(range)),
                 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));
     list.insert(list.end(), CfgTraits::wrapIterator(std::begin(range)),
                 CfgTraits::wrapIterator(std::end(range)));
   }
   void appendSuccessors(CfgBlockRef block,
                         SmallVectorImpl<CfgBlockRef> &list) const final {
explicit CfgPrinterImpl(const CfgInterfaceImpl<CfgTraits> &impl)
       : CfgPrinter(impl), CfgTraitsT::Printer(impl) {}
 
   void printBlockName(raw_ostream &out, CfgBlockRef block) const final {
     CfgTraits::Printer::printBlockName(out, CfgTraits::unwrapRef(block));
   }
   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
 
 #endif // LLVM_SUPPORT_CFGTRAITS_H

llvm/lib/CodeGen/MachineCfgTraits.cpp

void MachineCfgTraits::Printer::printValue(raw_ostream &out,
   if (value) {
     out << ": ";
 
     MachineInstr *instr = m_regInfo->getUniqueVRegDef(value);
     instr->print(out);
   }
 }
 
+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);
 }

llvm/lib/IR/CFG.cpp

void IrCfgTraits::Printer::printValue(raw_ostream &out, ValueRef value) const {
 
   if (m_moduleSlotTracker) {
     value->print(out, *m_moduleSlotTracker, true);
   } else {
     value->print(out, true);
   }
 }
 
+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()) {
     out << block->getName();
   } else {
     ensureModuleSlotTracker(*block->getParent());
     out << m_moduleSlotTracker->getLocalSlot(block);
   }

llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h

 
 namespace llvm {
 
 /// Partial CFG traits for VPlan's CFG, without a value type.
 class VPCfgTraitsBase : public CfgTraitsBase {
 public:
   using ParentType = VPRegionBlock;
   using BlockRef = VPBlockBase *;
+  using InstructionRef = void;
   using ValueRef = void;
 
   static CfgBlockRef wrapRef(BlockRef block) {
     return makeOpaque<CfgBlockRefTag>(block);
   }
   static BlockRef unwrapRef(CfgBlockRef block) {
     return static_cast<BlockRef>(getOpaque(block));
   }

mlir/include/mlir/IR/Dominance.h

 
 namespace mlir {
 
 /// Partial CFG traits for MLIR's CFG, without a value type.
 class CfgTraitsBase : public llvm::CfgTraitsBase {
 public:
   using ParentType = Region;
   using BlockRef = Block *;
+  using InstructionRef = void;
   using ValueRef = void;
 
   static llvm::CfgBlockRef wrapRef(BlockRef block) {
     return makeOpaque<llvm::CfgBlockRefTag>(block);
   }
   static BlockRef unwrapRef(llvm::CfgBlockRef block) {
     return static_cast<BlockRef>(getOpaque(block));
   }