From c0cdd22c72fab47a3c37b5a8401763995cadaa77 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Nicolai=20H=C3=A4hnle?= Date: Tue, 20 Oct 2020 13:50:52 +0200 Subject: [PATCH] Introduce CfgTraits abstraction The CfgTraits abstraction simplfies writing algorithms that are generic over the type of CFG, and enables writing such algorithms as regular non-template code that operates on opaque references to CFG blocks and values. Implementations of CfgTraits provide operations on the concrete CFG types, e.g. `IrCfgTraits::BlockRef` is `BasicBlock *`. CfgInterface is an abstract base class which provides operations on opaque types CfgBlockRef and CfgValueRef. Those opaque types encapsulate a `void *`, but the meaning depends on the concrete CFG type. For example, MachineCfgTraits -- for use with MachineIR in SSA form -- encodes a Register inside CfgValueRef. Converting between concrete references and opaque/generic ones is done by CfgTraits::{fromGeneric,toGeneric}. Convenience methods CfgTraits::{un}wrap{Iterator,Range} are available as well. Writing algorithms in terms of CfgInterface adds some overhead (virtual method calls, plus in same cases it removes the opportunity to inline iterators), but can be much more convenient since generic algorithms can be written as non-templates. This patch adds implementations of CfgTraits for all CFGs on which dominator trees are calculated, so that the dominator tree can be ported to this machinery. Only IrCfgTraits (LLVM IR) and MachineCfgTraits (Machine IR in SSA form) are complete, the other implementations are limited to the absolute minimum required to make the upcoming dominator tree changes work. v5: - fix MachineCfgTraits::blockdef_iterator and allow it to iterate over the instructions in a bundle - use MachineBasicBlock::printName v6: - implement predecessors/successors for all CfgTraits implementations - fix error in unwrapRange - rename toGeneric/fromGeneric into wrapRef/unwrapRef to have naming that is consistent with {wrap,unwrap}{Iterator,Range} - use getVRegDef instead of getUniqueVRegDef v7: - std::forward fix in wrapping_iterator - fix typos v8: - cleanup operators on CfgOpaqueType - address other review comments Change-Id: Ia75f4f268fded33fca11218a7d578c9aec1f3f4d Differential Revision: https://reviews.llvm.org/D83088 --- clang/include/clang/Analysis/Analyses/Dominators.h | 91 +++- llvm/include/llvm/CodeGen/MachineCfgTraits.h | 171 ++++++++ llvm/include/llvm/IR/CFG.h | 93 ++++ llvm/include/llvm/Support/CfgTraits.h | 474 +++++++++++++++++++++ llvm/lib/CodeGen/CMakeLists.txt | 1 + llvm/lib/CodeGen/MachineCfgTraits.cpp | 30 ++ llvm/lib/IR/CFG.cpp | 56 +++ llvm/lib/IR/CMakeLists.txt | 1 + llvm/lib/Support/CMakeLists.txt | 1 + llvm/lib/Support/CfgTraits.cpp | 14 + llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h | 33 ++ mlir/include/mlir/IR/Dominance.h | 38 ++ 12 files changed, 1002 insertions(+), 1 deletion(-) create mode 100644 llvm/include/llvm/CodeGen/MachineCfgTraits.h create mode 100644 llvm/include/llvm/Support/CfgTraits.h create mode 100644 llvm/lib/CodeGen/MachineCfgTraits.cpp create mode 100644 llvm/lib/IR/CFG.cpp create mode 100644 llvm/lib/Support/CfgTraits.cpp diff --git a/clang/include/clang/Analysis/Analyses/Dominators.h b/clang/include/clang/Analysis/Analyses/Dominators.h index 25a5ba9..e09ff04 100644 --- a/clang/include/clang/Analysis/Analyses/Dominators.h +++ b/clang/include/clang/Analysis/Analyses/Dominators.h @@ -18,11 +18,100 @@ #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/iterator.h" -#include "llvm/Support/GenericIteratedDominanceFrontier.h" +#include "llvm/Support/CfgTraits.h" #include "llvm/Support/GenericDomTree.h" #include "llvm/Support/GenericDomTreeConstruction.h" +#include "llvm/Support/GenericIteratedDominanceFrontier.h" #include "llvm/Support/raw_ostream.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 ValueRef = void; + + static llvm::CfgBlockRef wrapRef(BlockRef block) { + return makeOpaque(block); + } + static BlockRef unwrapRef(llvm::CfgBlockRef block) { + return static_cast(getOpaque(block)); + } +}; + +class CfgTraits : public llvm::CfgTraits { +public: + static ParentType *getBlockParent(CFGBlock *block) { + return block->getParent(); + } + + // Clang's CFG contains null pointers for unreachable successors, e.g. when an + // if statement's condition is always false, it's 'then' branch is represented + // with a nullptr. Account for this in the predecessors / successors + // iteration. + template struct skip_null_iterator; + + template + using skip_null_iterator_base = + llvm::iterator_adaptor_base, + BaseIteratorT, + std::bidirectional_iterator_tag>; + + template + struct skip_null_iterator : skip_null_iterator_base { + using Base = skip_null_iterator_base; + + skip_null_iterator() = default; + skip_null_iterator(BaseIteratorT it, BaseIteratorT end) + : Base(it), m_end(end) { + forward(); + } + + skip_null_iterator &operator++() { + ++this->I; + forward(); + return *this; + } + + skip_null_iterator &operator--() { + do { + --this->I; + } while (!*this->I); + return *this; + } + + private: + BaseIteratorT m_end; + + void forward() { + while (this->I != m_end && !*this->I) + ++this->I; + } + }; + + static auto predecessors(CFGBlock *block) { + auto range = llvm::inverse_children(block); + using iterator = skip_null_iterator; + return llvm::make_range(iterator(range.begin(), range.end()), + iterator(range.end(), range.end())); + } + + static auto successors(CFGBlock *block) { + auto range = llvm::children(block); + using iterator = skip_null_iterator; + return llvm::make_range(iterator(range.begin(), range.end()), + iterator(range.end(), range.end())); + } +}; + +} // namespace clang + +template <> struct llvm::CfgTraitsFor { + using CfgTraits = clang::CfgTraits; +}; + // FIXME: There is no good reason for the domtree to require a print method // which accepts an LLVM Module, so remove this (and the method's argument that // needs it) when that is fixed. diff --git a/llvm/include/llvm/CodeGen/MachineCfgTraits.h b/llvm/include/llvm/CodeGen/MachineCfgTraits.h new file mode 100644 index 0000000..ed6fa58 --- /dev/null +++ b/llvm/include/llvm/CodeGen/MachineCfgTraits.h @@ -0,0 +1,171 @@ +//===- MachineCfgTraits.h - Traits for Machine IR CFGs ----------*- 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 +// +//===----------------------------------------------------------------------===// +/// \file +/// +/// This file defines the MachineCfgTraits to allow generic CFG algorithms to +/// operate on MachineIR in SSA form. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_MACHINECFGTRAITS_H +#define LLVM_CODEGEN_MACHINECFGTRAITS_H + +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/Support/CfgTraits.h" + +namespace llvm { + +class MachineCfgTraitsBase : public CfgTraitsBase { +public: + using ParentType = MachineFunction; + using BlockRef = MachineBasicBlock *; + using ValueRef = Register; + + static CfgBlockRef wrapRef(BlockRef block) { + return makeOpaque(block); + } + 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(reinterpret_cast(wrapped)); + } + static BlockRef unwrapRef(CfgBlockRef block) { + return static_cast(getOpaque(block)); + } + static ValueRef unwrapRef(CfgValueRef value) { + uintptr_t wrapped = reinterpret_cast(getOpaque(value)); + return Register(wrapped); + } +}; + +/// \brief CFG traits for Machine IR in SSA form. +class MachineCfgTraits + : public CfgTraits { +private: + MachineRegisterInfo *m_regInfo; + +public: + explicit MachineCfgTraits(MachineFunction *parent) + : m_regInfo(&parent->getRegInfo()) {} + + static MachineFunction *getBlockParent(MachineBasicBlock *block) { + return block->getParent(); + } + + struct const_blockref_iterator + : iterator_adaptor_base { + using Base = iterator_adaptor_base; + + const_blockref_iterator() = default; + + explicit const_blockref_iterator(MachineFunction::iterator i) : Base(i) {} + + MachineBasicBlock *operator*() const { return &Base::operator*(); } + }; + + static iterator_range + blocks(MachineFunction *function) { + return {const_blockref_iterator(function->begin()), + const_blockref_iterator(function->end())}; + } + + static auto predecessors(MachineBasicBlock *block) { + return block->predecessors(); + } + static auto successors(MachineBasicBlock *block) { + return block->successors(); + } + + /// Get the defining block of a value. + MachineBasicBlock *getValueDefBlock(ValueRef value) const { + if (!value) + return nullptr; + return m_regInfo->getVRegDef(value)->getParent(); + } + + struct blockdef_iterator + : iterator_facade_base { + private: + MachineBasicBlock::instr_iterator m_instr; + MachineInstr::mop_iterator m_def; + + public: + blockdef_iterator() = default; + + explicit blockdef_iterator(MachineBasicBlock &block) + : m_instr(block.instr_begin()) { + if (m_instr != block.end()) + m_def = m_instr->defs().begin(); + } + blockdef_iterator(MachineBasicBlock &block, bool) + : m_instr(block.instr_end()), m_def() {} + + bool operator==(const blockdef_iterator &rhs) const { + return m_instr == rhs.m_instr && m_def == rhs.m_def; + } + + Register operator*() const { + assert(m_def->isReg() && !m_def->getSubReg() && m_def->isDef()); + return m_def->getReg(); + } + + blockdef_iterator &operator++() { + ++m_def; + + while (m_def == m_instr->defs().end()) { + ++m_instr; + if (m_instr.isEnd()) { + m_def = {}; + return *this; + } + + m_def = m_instr->defs().begin(); + } + + return *this; + } + }; + + static auto blockdefs(MachineBasicBlock *block) { + return llvm::make_range(blockdef_iterator(*block), + blockdef_iterator(*block, true)); + } + + 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; + + private: + MachineRegisterInfo *m_regInfo; + }; +}; + +template <> struct CfgTraitsFor { + using CfgTraits = MachineCfgTraits; +}; + +} // namespace llvm + +#endif // LLVM_CODEGEN_MACHINECFGTRAITS_H diff --git a/llvm/include/llvm/IR/CFG.h b/llvm/include/llvm/IR/CFG.h index f798b1a..51188c3 100644 --- a/llvm/include/llvm/IR/CFG.h +++ b/llvm/include/llvm/IR/CFG.h @@ -25,6 +25,7 @@ #include "llvm/IR/Function.h" #include "llvm/IR/Value.h" #include "llvm/Support/Casting.h" +#include "llvm/Support/CfgTraits.h" #include #include #include @@ -398,6 +399,98 @@ template <> struct GraphTraits> : } }; +//===----------------------------------------------------------------------===// +// LLVM IR CfgTraits +//===----------------------------------------------------------------------===// + +class IrCfgTraitsBase : public CfgTraitsBase { +public: + using ParentType = Function; + using BlockRef = BasicBlock *; + using ValueRef = Value *; + + static CfgBlockRef wrapRef(BlockRef block) { + return makeOpaque(block); + } + static CfgValueRef wrapRef(ValueRef block) { + return makeOpaque(block); + } + static BlockRef unwrapRef(CfgBlockRef block) { + return static_cast(getOpaque(block)); + } + static ValueRef unwrapRef(CfgValueRef block) { + return static_cast(getOpaque(block)); + } +}; + +/// \brief CFG traits for LLVM IR. +class IrCfgTraits : public CfgTraits { +public: + explicit IrCfgTraits(Function * /*parent*/) {} + + static Function *getBlockParent(BasicBlock *block) { + return block->getParent(); + } + + static auto predecessors(BasicBlock *block) { + return llvm::predecessors(block); + } + static auto successors(BasicBlock *block) { return llvm::successors(block); } + + /// Get the defining block of a value if it is an instruction, or null + /// otherwise. + static BlockRef getValueDefBlock(ValueRef value) { + if (auto *instruction = dyn_cast(value)) + return instruction->getParent(); + return nullptr; + } + + struct block_iterator + : iterator_adaptor_base { + using Base = iterator_adaptor_base; + + block_iterator() = default; + + explicit block_iterator(Function::iterator i) : Base(i) {} + + BasicBlock *operator*() const { return &Base::operator*(); } + }; + + static iterator_range blocks(Function *function) { + return {block_iterator(function->begin()), block_iterator(function->end())}; + } + + struct value_iterator + : iterator_adaptor_base { + using Base = iterator_adaptor_base; + + value_iterator() = default; + + explicit value_iterator(BasicBlock::iterator i) : Base(i) {} + + ValueRef operator*() const { return &Base::operator*(); } + }; + + static iterator_range 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; + + private: + mutable std::unique_ptr m_moduleSlotTracker; + + void ensureModuleSlotTracker(const Function &function) const; + }; +}; + +template <> struct CfgTraitsFor { using CfgTraits = IrCfgTraits; }; + } // end namespace llvm #endif // LLVM_IR_CFG_H diff --git a/llvm/include/llvm/Support/CfgTraits.h b/llvm/include/llvm/Support/CfgTraits.h new file mode 100644 index 0000000..aa71ae3 --- /dev/null +++ b/llvm/include/llvm/Support/CfgTraits.h @@ -0,0 +1,474 @@ +//===- CfgTraits.h - Traits for generically working on CFGs -----*- 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 +// +//===----------------------------------------------------------------------===// +/// \file +/// +/// This file defines a traits template \ref CfgTraits as well as the +/// \ref CfgInterface abstract interface and \ref CfgInterfaceImpl that help +/// in writing algorithms that are generic over CFGs, e.g. operating on both +/// LLVM IR and MachineIR. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_CFGTRAITS_H +#define LLVM_SUPPORT_CFGTRAITS_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMapInfo.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/Printable.h" + +namespace llvm { + +template class CfgOpaqueType; + +template +bool operator==(CfgOpaqueType lhs, CfgOpaqueType rhs); +template +bool operator<(CfgOpaqueType lhs, CfgOpaqueType rhs); + +/// \brief Type-erased references to CFG objects (blocks, values). +/// +/// Use CfgTraits::{wrapRef, unwrapRef} to wrap and unwrap concrete object +/// references. +/// +/// The most common use is to hold a pointer, but arbitrary uintptr_t values +/// may be stored by CFGs. Note that 0, -1, and -2 have special interpretations: +/// * 0 / nullptr: default-constructed value; evaluates to false in boolean +/// contexts. +/// * -1: dense map empty marker +/// * -2: dense map tombstone +template class CfgOpaqueType { + friend class CfgTraitsBase; + friend struct DenseMapInfo>; + template friend class CfgTraits; + template + friend bool operator==(CfgOpaqueType, CfgOpaqueType); + template + friend bool operator<(CfgOpaqueType, CfgOpaqueType); + + void *ptr = nullptr; + + explicit CfgOpaqueType(void *ptr) : ptr(ptr) {} + void *get() const { return ptr; } + +public: + CfgOpaqueType() = default; + + explicit operator bool() const { return ptr != nullptr; } +}; + +template +bool operator==(CfgOpaqueType lhs, CfgOpaqueType rhs) { + return lhs.get() == rhs.get(); +} + +template +bool operator!=(CfgOpaqueType lhs, CfgOpaqueType rhs) { + return !(lhs == rhs); +} + +template +bool operator<(CfgOpaqueType lhs, CfgOpaqueType rhs) { + return lhs.get() < rhs.get(); +} + +template struct DenseMapInfo> { + using Type = CfgOpaqueType; + + static Type getEmptyKey() { + uintptr_t val = static_cast(-1); + return Type(reinterpret_cast(val)); + } + + static Type getTombstoneKey() { + uintptr_t val = static_cast(-2); + return Type(reinterpret_cast(val)); + } + + static unsigned getHashValue(Type val) { + return llvm::DenseMapInfo::getHashValue(val.get()); + } + static bool isEqual(Type lhs, Type rhs) { return lhs == rhs; } +}; + +class CfgParentRefTag; +using CfgParentRef = CfgOpaqueType; + +class CfgBlockRefTag; +using CfgBlockRef = CfgOpaqueType; + +class CfgValueRefTag; +using CfgValueRef = CfgOpaqueType; + +/// \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. +class CfgTraitsBase { +protected: + template static auto makeOpaque(void *ptr) { + CfgOpaqueType ref; + ref.ptr = ptr; + return ref; + } + + template static void *getOpaque(CfgOpaqueType opaque) { + return opaque.ptr; + } + +public: + // To be implemented by derived classes: + // + // - The type of the "parent" of the CFG, e.g. `llvm::Function` + // using ParentType = ...; + // + // - 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 CfgValueRef wrapRef(ValueRef); + // static BlockRef unwrapRef(CfgBlockRef); + // 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 +class CfgTraits : public BaseTraits { +public: + using typename BaseTraits::BlockRef; + 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); + + // Find the parent for a given block. + // static ParentType *getBlockParent(BlockRef block); + + // Iterate over blocks in the CFG containing the given block in an arbitrary + // order (start with entry block, return a range of iterators dereferencing + // to BlockRef): + // static auto blocks(ParentType *parent); + + // Iterate over the predecessors / successors of a block (return a range + // 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); + + // 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; + // }; + + ///@} + + static CfgParentRef wrapRef(ParentType *parent) { + return CfgParentRef{parent}; + } + + static ParentType *unwrapRef(CfgParentRef parent) { + return static_cast(parent.get()); + } + + using BaseTraits::unwrapRef; + using BaseTraits::wrapRef; + + template struct unwrapping_iterator; + + template + using unwrapping_iterator_base = iterator_adaptor_base< + unwrapping_iterator, BaseIteratorT, + typename std::iterator_traits::iterator_category, + // value_type + decltype(BaseTraits::unwrapRef(*std::declval())), + typename std::iterator_traits::difference_type, + // pointer (not really usable, but we need to put something here) + decltype(BaseTraits::unwrapRef(*std::declval())) *, + // reference (not a true reference, because operator* doesn't return one) + decltype(BaseTraits::unwrapRef(*std::declval()))>; + + template + struct unwrapping_iterator : unwrapping_iterator_base { + using Base = unwrapping_iterator_base; + + unwrapping_iterator() = default; + explicit unwrapping_iterator(BaseIteratorT &&it) + : Base(std::forward(it)) {} + + auto operator*() const { return BaseTraits::unwrapRef(*this->I); } + }; + + template struct wrapping_iterator; + + template + using wrapping_iterator_base = iterator_adaptor_base< + wrapping_iterator, BaseIteratorT, + typename std::iterator_traits::iterator_category, + // value_type + decltype(BaseTraits::wrapRef(*std::declval())), + typename std::iterator_traits::difference_type, + // pointer (not really usable, but we need to put something here) + decltype(BaseTraits::wrapRef(*std::declval())) *, + // reference (not a true reference, because operator* doesn't return one) + decltype(BaseTraits::wrapRef(*std::declval()))>; + + template + struct wrapping_iterator : wrapping_iterator_base { + using Base = wrapping_iterator_base; + + wrapping_iterator() = default; + explicit wrapping_iterator(BaseIteratorT &&it) + : Base(std::forward(it)) {} + + auto operator*() const { return BaseTraits::wrapRef(*this->I); } + }; + + /// Convert an iterator of CfgBlockRef or CfgValueRef into an iterator of + /// BlockRef or ValueRef. + template static auto unwrapIterator(IteratorT &&it) { + return unwrapping_iterator(std::forward(it)); + } + + /// Convert a range of CfgBlockRef or CfgValueRef into a range of + /// BlockRef or ValueRef. + template static auto unwrapRange(RangeT &&range) { + return llvm::make_range( + unwrapIterator(adl_begin(std::forward(range))), + unwrapIterator(adl_end(std::forward(range)))); + } + + /// Convert an iterator of BlockRef or ValueRef into an iterator of + /// CfgBlockRef or CfgValueRef. + template static auto wrapIterator(IteratorT &&it) { + return wrapping_iterator(std::forward(it)); + } + + /// Convert a range of BlockRef or ValueRef into a range of CfgBlockRef or + /// CfgValueRef. + template static auto wrapRange(RangeT &&range) { + return llvm::make_range( + wrapIterator(adl_begin(std::forward(range))), + wrapIterator(adl_end(std::forward(range)))); + } +}; + +/// \brief Obtain CfgTraits given the basic block type. +/// +/// This template is provided to ease the transition to the use of CfgTraits. +/// Existing templates e.g. over the basic block type can use this to derive +/// the appropriate CfgTraits implementation via +/// typename CfgTraitsFor::CfgTraits. +template struct CfgTraitsFor; +// Specializations need to include: +// using CfgTraits = ...; + +class CfgPrinter; + +/// \brief Type-erased "CFG traits" +/// +/// Non-template algorithms that operate generically over CFG types can use this +/// interface to query for CFG-specific functionality. +/// +/// Note: This interface should only be implemented by \ref CfgInterfaceImpl. +class CfgInterface { + virtual void anchor(); + +public: + virtual ~CfgInterface() = default; + + /// Escape-hatch for obtaining a printer e.g. in debug code. Prefer to + /// explicitly pass a CfgPrinter where possible. + virtual std::unique_ptr makePrinter() const = 0; + + virtual CfgParentRef getBlockParent(CfgBlockRef block) const = 0; + + virtual void appendBlocks(CfgParentRef parent, + SmallVectorImpl &list) const = 0; + + virtual void appendPredecessors(CfgBlockRef block, + SmallVectorImpl &list) const = 0; + virtual void appendSuccessors(CfgBlockRef block, + SmallVectorImpl &list) const = 0; + virtual ArrayRef + getPredecessors(CfgBlockRef block, + SmallVectorImpl &store) const = 0; + virtual ArrayRef + getSuccessors(CfgBlockRef block, + SmallVectorImpl &store) const = 0; + + virtual void appendBlockDefs(CfgBlockRef block, + SmallVectorImpl &list) const = 0; + virtual CfgBlockRef getValueDefBlock(CfgValueRef value) const = 0; +}; + +/// \brief Type-erased "CFG printer" +/// +/// Separate from CfgInterface because some CFG printing requires tracking +/// expensive data structures, and we'd like to avoid the cost of +/// (conditionally) tearing them down in the common case. +class CfgPrinter { + virtual void anchor(); + +protected: + const CfgInterface &m_iface; + + CfgPrinter(const CfgInterface &iface) : m_iface(iface) {} + +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; + + 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); }); + } +}; + +template class CfgPrinterImpl; + +/// \brief Implementation of type-erased "CFG traits" +/// +/// Note: Do not specialize this template; adjust the CfgTraits type instead +/// where necessary. +template +class CfgInterfaceImpl final : public CfgInterface, + private CfgTraitsT { // empty base optimization +public: + using CfgTraits = CfgTraitsT; + using BlockRef = typename CfgTraits::BlockRef; + using ValueRef = typename CfgTraits::ValueRef; + using ParentType = typename CfgTraits::ParentType; + + friend CfgPrinterImpl; + +public: + explicit CfgInterfaceImpl(ParentType *parent) : CfgTraits(parent) {} + + std::unique_ptr makePrinter() const final { + return std::make_unique>(*this); + } + + CfgParentRef getBlockParent(CfgBlockRef block) const final { + return CfgTraits::wrapRef( + CfgTraits::getBlockParent(CfgTraits::unwrapRef(block))); + } + + void appendBlocks(CfgParentRef parent, + SmallVectorImpl &list) const final { + auto range = CfgTraits::blocks(CfgTraits::unwrapRef(parent)); + list.insert(list.end(), CfgTraits::wrapIterator(std::begin(range)), + CfgTraits::wrapIterator(std::end(range))); + } + + void appendPredecessors(CfgBlockRef block, + SmallVectorImpl &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 &list) const final { + auto range = CfgTraits::successors(CfgTraits::unwrapRef(block)); + list.insert(list.end(), CfgTraits::wrapIterator(std::begin(range)), + CfgTraits::wrapIterator(std::end(range))); + } + ArrayRef + getPredecessors(CfgBlockRef block, + SmallVectorImpl &store) const final { + // TODO: Can this be optimized for concrete CFGs that already have the + // "right" in-memory representation of predecessors / successors? + store.clear(); + appendPredecessors(block, store); + return store; + } + ArrayRef + getSuccessors(CfgBlockRef block, + SmallVectorImpl &store) const final { + // TODO: Can this be optimized for concrete CFGs that already have the + // "right" in-memory representation of predecessors / successors? + store.clear(); + appendSuccessors(block, store); + return store; + } + + void appendBlockDefs(CfgBlockRef block, + SmallVectorImpl &list) const final { + auto range = CfgTraits::blockdefs(CfgTraits::unwrapRef(block)); + list.insert(list.end(), CfgTraits::wrapIterator(std::begin(range)), + CfgTraits::wrapIterator(std::end(range))); + } + + CfgBlockRef getValueDefBlock(CfgValueRef value) const final { + return CfgTraits::wrapRef( + CfgTraits::getValueDefBlock(CfgTraits::unwrapRef(value))); + } +}; + +/// \brief Implementation of type-erased "CFG traits" +/// +/// Note: Do not specialize this template; adjust the CfgTraits type instead +/// where necessary. +template +class CfgPrinterImpl : public CfgPrinter, + private CfgTraitsT::Printer { // empty base optimization +public: + using CfgTraits = CfgTraitsT; + using BlockRef = typename CfgTraits::BlockRef; + using ValueRef = typename CfgTraits::ValueRef; + +public: + explicit CfgPrinterImpl(const CfgInterfaceImpl &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)); + } +}; + +} // namespace llvm + +#endif // LLVM_SUPPORT_CFGTRAITS_H diff --git a/llvm/lib/CodeGen/CMakeLists.txt b/llvm/lib/CodeGen/CMakeLists.txt index 617692a..7ffc429 100644 --- a/llvm/lib/CodeGen/CMakeLists.txt +++ b/llvm/lib/CodeGen/CMakeLists.txt @@ -71,6 +71,7 @@ add_llvm_component_library(LLVMCodeGen MachineBlockFrequencyInfo.cpp MachineBlockPlacement.cpp MachineBranchProbabilityInfo.cpp + MachineCfgTraits.cpp MachineCombiner.cpp MachineCopyPropagation.cpp MachineCSE.cpp diff --git a/llvm/lib/CodeGen/MachineCfgTraits.cpp b/llvm/lib/CodeGen/MachineCfgTraits.cpp new file mode 100644 index 0000000..d869a8a --- /dev/null +++ b/llvm/lib/CodeGen/MachineCfgTraits.cpp @@ -0,0 +1,30 @@ +//===- MachineCycleInfo.cpp - Cycle Info for Machine IR ---------*- 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 +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/MachineCfgTraits.h" + +#include "llvm/IR/BasicBlock.h" + +using namespace llvm; + +void MachineCfgTraits::Printer::printValue(raw_ostream &out, + Register value) const { + out << printReg(value, m_regInfo->getTargetRegisterInfo(), 0, m_regInfo); + + if (value) { + out << ": "; + + MachineInstr *instr = m_regInfo->getUniqueVRegDef(value); + instr->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 new file mode 100644 index 0000000..039d7f7f --- /dev/null +++ b/llvm/lib/IR/CFG.cpp @@ -0,0 +1,56 @@ +//===- CFG.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 +// +//===----------------------------------------------------------------------===// + +#include "llvm/IR/CFG.h" + +#include "llvm/IR/ModuleSlotTracker.h" + +using namespace llvm; + +IrCfgTraits::Printer::Printer(const IrCfgTraits &) {} +IrCfgTraits::Printer::~Printer() {} + +void IrCfgTraits::Printer::printValue(raw_ostream &out, ValueRef value) const { + if (!m_moduleSlotTracker) { + const Function *function = nullptr; + + if (auto *instruction = dyn_cast(value)) { + function = instruction->getParent()->getParent(); + } else if (auto *argument = dyn_cast(value)) { + function = argument->getParent(); + } + + if (function) + ensureModuleSlotTracker(*function); + } + + if (m_moduleSlotTracker) { + value->print(out, *m_moduleSlotTracker, true); + } else { + value->print(out, true); + } +} + +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); + } +} + +void IrCfgTraits::Printer::ensureModuleSlotTracker( + const Function &function) const { + if (!m_moduleSlotTracker) { + m_moduleSlotTracker = + std::make_unique(function.getParent(), false); + m_moduleSlotTracker->incorporateFunction(function); + } +} diff --git a/llvm/lib/IR/CMakeLists.txt b/llvm/lib/IR/CMakeLists.txt index 49805d5..43d9af1 100644 --- a/llvm/lib/IR/CMakeLists.txt +++ b/llvm/lib/IR/CMakeLists.txt @@ -4,6 +4,7 @@ add_llvm_component_library(LLVMCore Attributes.cpp AutoUpgrade.cpp BasicBlock.cpp + CFG.cpp Comdat.cpp ConstantFold.cpp ConstantRange.cpp diff --git a/llvm/lib/Support/CMakeLists.txt b/llvm/lib/Support/CMakeLists.txt index 24b0fc7..cbe32d9 100644 --- a/llvm/lib/Support/CMakeLists.txt +++ b/llvm/lib/Support/CMakeLists.txt @@ -97,6 +97,7 @@ add_llvm_component_library(LLVMSupport BranchProbability.cpp BuryPointer.cpp CachePruning.cpp + CfgTraits.cpp circular_raw_ostream.cpp Chrono.cpp COM.cpp diff --git a/llvm/lib/Support/CfgTraits.cpp b/llvm/lib/Support/CfgTraits.cpp new file mode 100644 index 0000000..330c511d --- /dev/null +++ b/llvm/lib/Support/CfgTraits.cpp @@ -0,0 +1,14 @@ +//===- CfgTraits.cpp - Traits for generically working on CFGs ---*- 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 +// +//===----------------------------------------------------------------------===// + +#include "llvm/Support/CfgTraits.h" + +using namespace llvm; + +void CfgInterface::anchor() {} +void CfgPrinter::anchor() {} diff --git a/llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h b/llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h index a42ebc9..34193c9 100644 --- a/llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h +++ b/llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h @@ -18,9 +18,42 @@ #include "VPlan.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/IR/Dominators.h" +#include "llvm/Support/CfgTraits.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 ValueRef = void; + + static CfgBlockRef wrapRef(BlockRef block) { + return makeOpaque(block); + } + static BlockRef unwrapRef(CfgBlockRef block) { + return static_cast(getOpaque(block)); + } +}; + +class VPCfgTraits : public CfgTraits { +public: + static VPRegionBlock *getBlockParent(VPBlockBase *block) { + return block->getParent(); + } + + static auto predecessors(VPBlockBase *block) { + return llvm::inverse_children(block); + } + + static auto successors(VPBlockBase *block) { + return llvm::children(block); + } +}; + +template <> struct CfgTraitsFor { using CfgTraits = VPCfgTraits; }; + /// Template specialization of the standard LLVM dominator tree utility for /// VPBlockBases. using VPDominatorTree = DomTreeBase; diff --git a/mlir/include/mlir/IR/Dominance.h b/mlir/include/mlir/IR/Dominance.h index 4a281bf..24d7183 100644 --- a/mlir/include/mlir/IR/Dominance.h +++ b/mlir/include/mlir/IR/Dominance.h @@ -10,8 +10,46 @@ #define MLIR_IR_DOMINANCE_H #include "mlir/IR/RegionGraphTraits.h" +#include "llvm/Support/CfgTraits.h" #include "llvm/Support/GenericDomTree.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 ValueRef = void; + + static llvm::CfgBlockRef wrapRef(BlockRef block) { + return makeOpaque(block); + } + static BlockRef unwrapRef(llvm::CfgBlockRef block) { + return static_cast(getOpaque(block)); + } +}; + +class CfgTraits : public llvm::CfgTraits { +public: + static Region *getBlockParent(Block *block) { return block->getParent(); } + + static auto predecessors(Block *block) { + return llvm::inverse_children(block); + } + + static auto successors(Block *block) { + return llvm::children(block); + } +}; + +} // namespace mlir + +template <> +struct llvm::CfgTraitsFor { + using CfgTraits = mlir::CfgTraits; +}; + extern template class llvm::DominatorTreeBase; extern template class llvm::DominatorTreeBase; -- 2.7.4