[llvm-dev] RFC: Introducing CfgTraits and type-erased CfgInterface / CfgBlockRef / CfgValueRef
Nicolai Hähnle via llvm-dev
llvm-dev at lists.llvm.org
Thu Jul 2 15:46:39 PDT 2020
This is a request for comment on a series of patches which introduce a
new way of writing algorithms that are generic over different types of CFG.
What is this?
This series of patches introduces a set of classes and templates for:
1. Working on basic blocks and values generically, in particular with
the same algorithm implementation on both LLVM IR and MachineIR (in SSA
2. Doing so using type erasure, i.e. the bulk of the algorithm you're
writing doesn't have to be a template (at the cost of using some virtual
The second point is achieved by
a) having algorithms refer to blocks and values using CfgBlockRef and
CfgValueRef types which wrap a `void *` whose interpretation depends on
the concrete CFG (for example, CfgValueRef wraps a `Value *` for LLVM IR
but a `Register` for MachineIR), and
b) querying the CFG via virtual methods in a CfgInterface interface class.
Please take a look at the following Phabricator reviews and related
changes you can navigate to via the "Stack" tab:
1. https://reviews.llvm.org/D83088: Introduces the classes and templates
that enable this new way of writing analyses (CfgTraits, CfgInterface,
2. https://reviews.llvm.org/D83089: Refactors the dominator tree
implementation so that algorithms that operate on CfgBlockRef will be
able to use a standard dominator tree as input. The calculation of
dominator trees remains unchanged as a template.
3. https://reviews.llvm.org/D83094: Adds a GenericCycleInfo analysis as
a first "full" user of the CfgInterface machinery. Unlike LoopInfo, this
analysis computes a nesting of both reducible and irreducible loops
(based on Havlak (1997)).
The concrete need that prompted this development is a reworking of the
control flow lowering in the AMDGPU backend. Part of this rework is a
new divergence/uniformity analysis that can be used on both LLVM IR and
MachineIR. This analysis has to be able to operate generically on both
basic blocks and values.
If you're interested in this larger context, feel free to take a look
There are still some missing bits and pieces and more cleanup to be done
for the parts which are not yet on Phabricator. I am going to tackle
those over the next weeks.
Templates vs. interfaces
At a high level, there are two parts to the proposed framework:
- CfgTraits, which provide generic operations on concrete CFG types. For
example, CfgTraits allow iterating over all values defined in a block.
The implementations of CfgTraits are typically used as template parameters.
- CfgInterface, which provides generic operations on opaque, type-erased
objects of type CfgBlockRef and CfgValueRef.
It is this second part which enables generic algorithms to be written
using virtual method-based interfaces instead of as templates.
Both approaches for writing generic algorithms have their advantages and
disadvantages. Templates don't have the (direct and indirect) runtime
overhead of virtual methods. Code that uses abstract interfaces is
easier to maintain and causes less binary bloat. It is not always clear
what the right trade-off is.
Existing generic analyses are all written as templates. It's not clear
to me how conscious that choice was, or whether the alternatives were
ever fully explored, but in any case I am not proposing to change the
already chosen trade-off there. Instead, I am proposing that we make the
alternative _possible_, and I have a whole set of analyses that are
implemented using this alternative waiting to be upstreamed.
What about MLIR / other CFGs?
While I personally only work in LLVM IR and MachineIR and my changes
only provide the minimum required to ensure that dominator trees
continue to work for everything else, the framework is designed with
other CFGs in mind. In particular, since `mlir::Value` is pointer-sized,
it shouldn't be too much effort to allow it to be wrapped in a
CfgValueRef as well. This would enable analyses written on CfgTraits /
CfgInterface (such as my upcoming divergence/uniformity analysis) to be
used from MLIR as well.
Lerne, wie die Welt wirklich ist,
Aber vergiss niemals, wie sie sein sollte.
More information about the llvm-dev