[llvm-dev] [RFC] Writing loop transformations on the right representation is more productive

[Renato Golin via llvm-dev]

On Thu, 16 Jan 2020 at 06:27, Chris Lattner via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> Ah yes, I see what you mean.  One way to do that is to represent multiple options as an op with region for each option.  This means you only fork the part of the IR that you’re producing variants of.  I think this is the red/green tree technique you mentioned, but I’m not sure.

IIUC. the green tree is a lighter version of the tree (leaner memory
footprint) but still entire tree. It's ok to lose that info because
you don't usually need that for your transformations, and you can
always go back to the red tree (via pointer in the green tree) to ask
harder questions. Managing the semantics of the two becomes
non-trivial when you start adding and replacing nodes, there's a point
where you can't go back anymore to the red tree in the same way.

What I referred to as "journalling" is what you propose here. Add
metadata to the actual graph and during the heuristic search, only
clone those. If you make sure you can append those nodes to the graph,
and guarantee that the extra nodes are composable (ie semantically
valid in any order they may be applied), then having the original
graph + any intermediate state is valid. Therefore, keeping only the
extra nodes, and copying them along to try different routes, becomes
even cheaper than a green tree.

If those extra nodes are an MLIR dialect, with defined semantics and
structured composition, then using them in an heuristics search
produces semantically valid intermediate states and lightens the
burden of proof for every little step.