Introduce CfgTraits abstraction
authorNicolai Hähnle <nicolai.haehnle@amd.com>
Tue, 20 Oct 2020 11:50:52 +0000 (13:50 +0200)
committerNicolai Hähnle <nicolai.haehnle@amd.com>
Tue, 20 Oct 2020 11:50:52 +0000 (13:50 +0200)
commitc0cdd22c72fab47a3c37b5a8401763995cadaa77
treebfccd709e0c824ea08309804212d5cba1d6f9024
parent84048e234f8f0d81871caab842dbed84b84aa86f
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
12 files changed:
clang/include/clang/Analysis/Analyses/Dominators.h
llvm/include/llvm/CodeGen/MachineCfgTraits.h [new file with mode: 0644]
llvm/include/llvm/IR/CFG.h
llvm/include/llvm/Support/CfgTraits.h [new file with mode: 0644]
llvm/lib/CodeGen/CMakeLists.txt
llvm/lib/CodeGen/MachineCfgTraits.cpp [new file with mode: 0644]
llvm/lib/IR/CFG.cpp [new file with mode: 0644]
llvm/lib/IR/CMakeLists.txt
llvm/lib/Support/CMakeLists.txt
llvm/lib/Support/CfgTraits.cpp [new file with mode: 0644]
llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
mlir/include/mlir/IR/Dominance.h