Page MenuHomePhabricator

Introduce CfgTraits abstraction
Needs ReviewPublic

Authored by nhaehnle on Jul 2 2020, 2:08 PM.

Details

Summary

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.

Change-Id: Ia75f4f268fded33fca11218a7d578c9aec1f3f4d

Diff Detail

Event Timeline

nhaehnle created this revision.Jul 2 2020, 2:08 PM
Herald added a reviewer: aartbik. · View Herald Transcript
Herald added projects: Restricted Project, Restricted Project, Restricted Project. · View Herald Transcript
arsenm added inline comments.Jul 3 2020, 7:56 AM
llvm/include/llvm/CodeGen/MachineCfgTraits.h
134

!= return early?

137–139

I've been thinking about more aggressively using bundles around call sites to handle waterfall looping around divergent calls with SGPR arguments

llvm/lib/CodeGen/MachineCfgTraits.cpp
28–30

I think this should be added to MachineBasicBlock. The same logic is already repeated in MIRPrinter (and the MBB dump function uses a different prefix)

33

Single quotes around .

nhaehnle updated this revision to Diff 275811.Mon, Jul 6, 1:02 PM
nhaehnle marked 4 inline comments as done.
  • fix MachineCfgTraits::blockdef_iterator and allow it to iterate over the instructions in a bundle
  • use MachineBasicBlock::printName
nhaehnle added inline comments.Mon, Jul 6, 1:05 PM
llvm/include/llvm/CodeGen/MachineCfgTraits.h
134

The logic is actually subtly broken in the presence of instructions without defs, I just didn't notice it because it currently affects only debug printing logic. Going to fix it.

137–139

Hmm, so what's the correct iteration behavior in the presence of bundles? Iterate over all instructions in the bundle (which is that MachineBasicBlock::instr_iterator does) and only iterate over explicit defs? I think that's what makes the most sense, and what I'm going with for now...

llvm/lib/CodeGen/MachineCfgTraits.cpp
28–30
arsenm added inline comments.Mon, Jul 6, 1:51 PM
llvm/include/llvm/CodeGen/MachineCfgTraits.h
137–139

I don't think this actually needs to specially consider bundles. The BUNDLE itself is supposed to have the uses/defs that cover all the uses/defs inside the bundle. You shouldn't need to worry about the individual instructions

nhaehnle marked an inline comment as done.Fri, Jul 10, 9:01 AM
nhaehnle added inline comments.
llvm/include/llvm/CodeGen/MachineCfgTraits.h
137–139

This is what should be there with the last change :)

arsenm added inline comments.Fri, Jul 17, 10:43 AM
llvm/include/llvm/CodeGen/MachineCfgTraits.h
45

I feel like there should be a better way to do this; we should probably have an assert where virtual registers are created

102

I think regular getVRegDef is preferable for SSA MIR

nhaehnle marked 3 inline comments as done.Fri, Jul 24, 8:40 AM
nhaehnle added inline comments.
llvm/include/llvm/CodeGen/MachineCfgTraits.h
45

The reason for doing it here is that this is the place where the reinterpret happens. If the check is elsewhere, it's easy to miss by a user of this.

102

Fixed locally.

nhaehnle updated this revision to Diff 280481.Fri, Jul 24, 9:12 AM
nhaehnle marked an inline comment as done.
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
arsenm added inline comments.Tue, Jul 28, 8:02 AM
clang/include/clang/Analysis/Analyses/Dominators.h
50

Missing space nullpointers, missing s succesors

51

s/it's/its/