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

Renato Golin via llvm-dev llvm-dev at lists.llvm.org
Thu Jan 16 01:55:33 PST 2020

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.

More information about the llvm-dev mailing list