nhaehnle updated this revision to Diff 284195.
nhaehnle marked 2 inline comments as done.
nhaehnle added a comment.
v7:
- std::forward fix in wrapping_iterator
- fix typos
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D83088/new/
https://reviews.llvm.org/D83088
Files:
clang/include/clang/Analysis/Analyses/Dominators.h
llvm/include/llvm/CodeGen/MachineCfgTraits.h
llvm/include/llvm/IR/CFG.h
llvm/include/llvm/Support/CfgTraits.h
llvm/lib/CodeGen/CMakeLists.txt
llvm/lib/CodeGen/MachineCfgTraits.cpp
llvm/lib/IR/CFG.cpp
llvm/lib/IR/CMakeLists.txt
llvm/lib/Support/CMakeLists.txt
llvm/lib/Support/CfgTraits.cpp
llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
mlir/include/mlir/IR/Dominance.h
Index: mlir/include/mlir/IR/Dominance.h
===================================================================
--- mlir/include/mlir/IR/Dominance.h
+++ 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<llvm::CfgBlockRefTag>(block);
+ }
+ static BlockRef unwrapRef(llvm::CfgBlockRef block) {
+ return static_cast<BlockRef>(getOpaque(block));
+ }
+};
+
+class CfgTraits : public llvm::CfgTraits<CfgTraitsBase, CfgTraits> {
+public:
+ static Region *getBlockParent(Block *block) { return block->getParent(); }
+
+ static auto predecessors(Block *block) {
+ return llvm::inverse_children<Block *>(block);
+ }
+
+ static auto successors(Block *block) {
+ return llvm::children<Block *>(block);
+ }
+};
+
+} // namespace mlir
+
+template <>
+struct llvm::CfgTraitsFor<mlir::Block> {
+ using CfgTraits = mlir::CfgTraits;
+};
+
extern template class llvm::DominatorTreeBase<mlir::Block, false>;
extern template class llvm::DominatorTreeBase<mlir::Block, true>;
Index: llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
===================================================================
--- llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
+++ 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<CfgBlockRefTag>(block);
+ }
+ static BlockRef unwrapRef(CfgBlockRef block) {
+ return static_cast<BlockRef>(getOpaque(block));
+ }
+};
+
+class VPCfgTraits : public CfgTraits<VPCfgTraitsBase, VPCfgTraits> {
+public:
+ static VPRegionBlock *getBlockParent(VPBlockBase *block) {
+ return block->getParent();
+ }
+
+ static auto predecessors(VPBlockBase *block) {
+ return llvm::inverse_children<VPBlockBase *>(block);
+ }
+
+ static auto successors(VPBlockBase *block) {
+ return llvm::children<VPBlockBase *>(block);
+ }
+};
+
+template <> struct CfgTraitsFor<VPBlockBase> { using CfgTraits = VPCfgTraits; };
+
/// Template specialization of the standard LLVM dominator tree utility for
/// VPBlockBases.
using VPDominatorTree = DomTreeBase<VPBlockBase>;
Index: llvm/lib/Support/CfgTraits.cpp
===================================================================
--- /dev/null
+++ 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() {}
Index: llvm/lib/Support/CMakeLists.txt
===================================================================
--- llvm/lib/Support/CMakeLists.txt
+++ llvm/lib/Support/CMakeLists.txt
@@ -71,6 +71,7 @@
BranchProbability.cpp
BuryPointer.cpp
CachePruning.cpp
+ CfgTraits.cpp
circular_raw_ostream.cpp
Chrono.cpp
COM.cpp
Index: llvm/lib/IR/CMakeLists.txt
===================================================================
--- llvm/lib/IR/CMakeLists.txt
+++ llvm/lib/IR/CMakeLists.txt
@@ -4,6 +4,7 @@
Attributes.cpp
AutoUpgrade.cpp
BasicBlock.cpp
+ CFG.cpp
Comdat.cpp
ConstantFold.cpp
ConstantRange.cpp
Index: llvm/lib/IR/CFG.cpp
===================================================================
--- /dev/null
+++ 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<Instruction>(value)) {
+ function = instruction->getParent()->getParent();
+ } else if (auto *argument = dyn_cast<Argument>(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<ModuleSlotTracker>(function.getParent(), false);
+ m_moduleSlotTracker->incorporateFunction(function);
+ }
+}
Index: llvm/lib/CodeGen/MachineCfgTraits.cpp
===================================================================
--- /dev/null
+++ 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);
+}
Index: llvm/lib/CodeGen/CMakeLists.txt
===================================================================
--- llvm/lib/CodeGen/CMakeLists.txt
+++ llvm/lib/CodeGen/CMakeLists.txt
@@ -72,6 +72,7 @@
MachineBlockFrequencyInfo.cpp
MachineBlockPlacement.cpp
MachineBranchProbabilityInfo.cpp
+ MachineCfgTraits.cpp
MachineCombiner.cpp
MachineCopyPropagation.cpp
MachineCSE.cpp
Index: llvm/include/llvm/Support/CfgTraits.h
===================================================================
--- /dev/null
+++ llvm/include/llvm/Support/CfgTraits.h
@@ -0,0 +1,451 @@
+//===- 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 {
+
+/// \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 <typename Tag> class CfgOpaqueType {
+ friend class CfgTraitsBase;
+ friend struct DenseMapInfo<CfgOpaqueType<Tag>>;
+ template <typename BaseTraits, typename FullTraits> friend class CfgTraits;
+
+ void *ptr = nullptr;
+
+ explicit CfgOpaqueType(void *ptr) : ptr(ptr) {}
+ void *get() const { return ptr; }
+
+public:
+ CfgOpaqueType() = default;
+
+ operator bool() const { return ptr != nullptr; }
+
+ bool operator==(CfgOpaqueType other) const { return ptr == other.ptr; }
+ bool operator!=(CfgOpaqueType other) const { return ptr != other.ptr; }
+};
+
+template <typename Tag> struct DenseMapInfo<CfgOpaqueType<Tag>> {
+ using Type = CfgOpaqueType<Tag>;
+
+ static Type getEmptyKey() {
+ uintptr_t val = static_cast<uintptr_t>(-1);
+ return Type(reinterpret_cast<void *>(val));
+ }
+
+ static Type getTombstoneKey() {
+ uintptr_t val = static_cast<uintptr_t>(-2);
+ return Type(reinterpret_cast<void *>(val));
+ }
+
+ static unsigned getHashValue(Type val) {
+ return llvm::DenseMapInfo<void *>::getHashValue(val.get());
+ }
+ static bool isEqual(Type lhs, Type rhs) { return lhs == rhs; }
+};
+
+class CfgParentRefTag;
+using CfgParentRef = CfgOpaqueType<CfgParentRefTag>;
+
+class CfgBlockRefTag;
+using CfgBlockRef = CfgOpaqueType<CfgBlockRefTag>;
+
+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.
+class CfgTraitsBase {
+protected:
+ template <typename Tag> static auto makeOpaque(void *ptr) {
+ CfgOpaqueType<Tag> ref;
+ ref.ptr = ptr;
+ return ref;
+ }
+
+ template <typename Tag> static void *getOpaque(CfgOpaqueType<Tag> 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 <typename BaseTraits, typename FullTraits>
+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<ParentType *>(parent.get());
+ }
+
+ using BaseTraits::unwrapRef;
+ using BaseTraits::wrapRef;
+
+ template <typename BaseIteratorT> struct unwrapping_iterator;
+
+ template <typename BaseIteratorT>
+ using unwrapping_iterator_base = iterator_adaptor_base<
+ unwrapping_iterator<BaseIteratorT>, BaseIteratorT,
+ typename std::iterator_traits<BaseIteratorT>::iterator_category,
+ // value_type
+ decltype(BaseTraits::unwrapRef(*std::declval<BaseIteratorT>())),
+ typename std::iterator_traits<BaseIteratorT>::difference_type,
+ // pointer (not really usable, but we need to put something here)
+ decltype(BaseTraits::unwrapRef(*std::declval<BaseIteratorT>())) *,
+ // reference (not a true reference, because operator* doesn't return one)
+ decltype(BaseTraits::unwrapRef(*std::declval<BaseIteratorT>()))>;
+
+ template <typename BaseIteratorT>
+ struct unwrapping_iterator : unwrapping_iterator_base<BaseIteratorT> {
+ using Base = unwrapping_iterator_base<BaseIteratorT>;
+
+ unwrapping_iterator() = default;
+ explicit unwrapping_iterator(BaseIteratorT &&it)
+ : Base(std::forward<BaseIteratorT>(it)) {}
+
+ auto operator*() const { return BaseTraits::unwrapRef(*this->I); }
+ };
+
+ template <typename BaseIteratorT> struct wrapping_iterator;
+
+ template <typename BaseIteratorT>
+ using wrapping_iterator_base = iterator_adaptor_base<
+ wrapping_iterator<BaseIteratorT>, BaseIteratorT,
+ typename std::iterator_traits<BaseIteratorT>::iterator_category,
+ // value_type
+ decltype(BaseTraits::wrapRef(*std::declval<BaseIteratorT>())),
+ typename std::iterator_traits<BaseIteratorT>::difference_type,
+ // pointer (not really usable, but we need to put something here)
+ decltype(BaseTraits::wrapRef(*std::declval<BaseIteratorT>())) *,
+ // reference (not a true reference, because operator* doesn't return one)
+ decltype(BaseTraits::wrapRef(*std::declval<BaseIteratorT>()))>;
+
+ template <typename BaseIteratorT>
+ struct wrapping_iterator : wrapping_iterator_base<BaseIteratorT> {
+ using Base = wrapping_iterator_base<BaseIteratorT>;
+
+ wrapping_iterator() = default;
+ explicit wrapping_iterator(BaseIteratorT &&it)
+ : Base(std::forward<BaseIteratorT>(it)) {}
+
+ auto operator*() const { return BaseTraits::wrapRef(*this->I); }
+ };
+
+ /// Convert an iterator of CfgBlockRef or CfgValueRef into an iterator of
+ /// BlockRef or ValueRef.
+ template <typename IteratorT> static auto unwrapIterator(IteratorT &&it) {
+ return unwrapping_iterator<IteratorT>(std::forward<IteratorT>(it));
+ }
+
+ /// Convert a range of CfgBlockRef or CfgValueRef into a range of
+ /// BlockRef or ValueRef.
+ template <typename RangeT> static auto unwrapRange(RangeT &&range) {
+ return llvm::make_range(
+ unwrapIterator(adl_begin(std::forward<RangeT>(range))),
+ unwrapIterator(adl_end(std::forward<RangeT>(range))));
+ }
+
+ /// Convert an iterator of BlockRef or ValueRef into an iterator of
+ /// CfgBlockRef or CfgValueRef.
+ template <typename IteratorT> static auto wrapIterator(IteratorT &&it) {
+ return wrapping_iterator<IteratorT>(std::forward<IteratorT>(it));
+ }
+
+ /// Convert a range of BlockRef or ValueRef into a range of CfgBlockRef or
+ /// CfgValueRef.
+ template <typename RangeT> static auto wrapRange(RangeT &&range) {
+ return llvm::make_range(
+ wrapIterator(adl_begin(std::forward<RangeT>(range))),
+ wrapIterator(adl_end(std::forward<RangeT>(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<BlockT>::CfgTraits.
+template <typename CfgRelatedTypeT> struct CfgTraitsFor {
+ // 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() {}
+
+ /// Escape-hatch for obtaining a printer e.g. in debug code. Prefer to
+ /// 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 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>
+ getSuccessors(CfgBlockRef block,
+ SmallVectorImpl<CfgBlockRef> &store) const = 0;
+
+ virtual void appendBlockDefs(CfgBlockRef block,
+ SmallVectorImpl<CfgValueRef> &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 <typename CfgTraitsT> class CfgPrinterImpl;
+
+/// \brief Implementation of type-erased "CFG traits"
+///
+/// Note: Do not specialize this template; adjust the CfgTraits type instead
+/// where necessary.
+template <typename CfgTraitsT>
+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<CfgTraits>;
+
+public:
+ explicit CfgInterfaceImpl(ParentType *parent) : CfgTraits(parent) {}
+
+ std::unique_ptr<CfgPrinter> makePrinter() const final {
+ return std::make_unique<CfgPrinterImpl<CfgTraits>>(*this);
+ }
+
+ CfgParentRef getBlockParent(CfgBlockRef block) const final {
+ return CfgTraits::wrapRef(
+ CfgTraits::getBlockParent(CfgTraits::unwrapRef(block)));
+ }
+
+ 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)));
+ }
+
+ 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 {
+ auto range = CfgTraits::successors(CfgTraits::unwrapRef(block));
+ list.insert(list.end(), CfgTraits::wrapIterator(std::begin(range)),
+ CfgTraits::wrapIterator(std::end(range)));
+ }
+ ArrayRef<CfgBlockRef>
+ getPredecessors(CfgBlockRef block,
+ SmallVectorImpl<CfgBlockRef> &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<CfgBlockRef>
+ getSuccessors(CfgBlockRef block,
+ SmallVectorImpl<CfgBlockRef> &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<CfgValueRef> &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 <typename CfgTraitsT>
+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<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));
+ }
+};
+
+} // namespace llvm
+
+#endif // LLVM_SUPPORT_CFGTRAITS_H
Index: llvm/include/llvm/IR/CFG.h
===================================================================
--- llvm/include/llvm/IR/CFG.h
+++ 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 <cassert>
#include <cstddef>
#include <iterator>
@@ -398,6 +399,98 @@
}
};
+//===----------------------------------------------------------------------===//
+// LLVM IR CfgTraits
+//===----------------------------------------------------------------------===//
+
+class IrCfgTraitsBase : public CfgTraitsBase {
+public:
+ using ParentType = Function;
+ using BlockRef = BasicBlock *;
+ using ValueRef = Value *;
+
+ static CfgBlockRef wrapRef(BlockRef block) {
+ return makeOpaque<CfgBlockRefTag>(block);
+ }
+ static CfgValueRef wrapRef(ValueRef block) {
+ return makeOpaque<CfgValueRefTag>(block);
+ }
+ static BlockRef unwrapRef(CfgBlockRef block) {
+ return static_cast<BlockRef>(getOpaque(block));
+ }
+ static ValueRef unwrapRef(CfgValueRef block) {
+ return static_cast<ValueRef>(getOpaque(block));
+ }
+};
+
+/// \brief CFG traits for LLVM IR.
+class IrCfgTraits : public CfgTraits<IrCfgTraitsBase, IrCfgTraits> {
+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<Instruction>(value))
+ return instruction->getParent();
+ return nullptr;
+ }
+
+ struct block_iterator
+ : iterator_adaptor_base<block_iterator, Function::iterator> {
+ using Base = iterator_adaptor_base<block_iterator, Function::iterator>;
+
+ block_iterator() = default;
+
+ explicit block_iterator(Function::iterator i) : Base(i) {}
+
+ BasicBlock *operator*() const { return &Base::operator*(); }
+ };
+
+ static iterator_range<block_iterator> blocks(Function *function) {
+ return {block_iterator(function->begin()), block_iterator(function->end())};
+ }
+
+ 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;
+
+ 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
Index: llvm/include/llvm/CodeGen/MachineCfgTraits.h
===================================================================
--- /dev/null
+++ 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<CfgBlockRefTag>(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<CfgValueRefTag>(reinterpret_cast<void *>(wrapped));
+ }
+ static BlockRef unwrapRef(CfgBlockRef block) {
+ return static_cast<BlockRef>(getOpaque(block));
+ }
+ 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 CfgTraits<MachineCfgTraitsBase, MachineCfgTraits> {
+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<const_blockref_iterator,
+ MachineFunction::iterator> {
+ using Base = iterator_adaptor_base<const_blockref_iterator,
+ MachineFunction::iterator>;
+
+ const_blockref_iterator() = default;
+
+ explicit const_blockref_iterator(MachineFunction::iterator i) : Base(i) {}
+
+ MachineBasicBlock *operator*() const { return &Base::operator*(); }
+ };
+
+ static iterator_range<const_blockref_iterator>
+ 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<blockdef_iterator, std::forward_iterator_tag,
+ Register> {
+ 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<MachineBasicBlock> {
+ using CfgTraits = MachineCfgTraits;
+};
+
+} // namespace llvm
+
+#endif // LLVM_CODEGEN_MACHINECFGTRAITS_H
Index: clang/include/clang/Analysis/Analyses/Dominators.h
===================================================================
--- clang/include/clang/Analysis/Analyses/Dominators.h
+++ 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<llvm::CfgBlockRefTag>(block);
+ }
+ static BlockRef unwrapRef(llvm::CfgBlockRef block) {
+ return static_cast<BlockRef>(getOpaque(block));
+ }
+};
+
+class CfgTraits : public llvm::CfgTraits<CfgTraitsBase, 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 <typename BaseIteratorT> struct skip_null_iterator;
+
+ template <typename BaseIteratorT>
+ using skip_null_iterator_base =
+ llvm::iterator_adaptor_base<skip_null_iterator<BaseIteratorT>,
+ BaseIteratorT,
+ std::bidirectional_iterator_tag>;
+
+ template <typename BaseIteratorT>
+ struct skip_null_iterator : skip_null_iterator_base<BaseIteratorT> {
+ using Base = skip_null_iterator_base<BaseIteratorT>;
+
+ 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<CFGBlock *>(block);
+ using iterator = skip_null_iterator<decltype(range.begin())>;
+ return llvm::make_range(iterator(range.begin(), range.end()),
+ iterator(range.end(), range.end()));
+ }
+
+ static auto successors(CFGBlock *block) {
+ auto range = llvm::children<CFGBlock *>(block);
+ using iterator = skip_null_iterator<decltype(range.begin())>;
+ return llvm::make_range(iterator(range.begin(), range.end()),
+ iterator(range.end(), range.end()));
+ }
+};
+
+} // namespace clang
+
+template <> struct llvm::CfgTraitsFor<clang::CFGBlock> {
+ 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.
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
