llvm-project
llvm-project copied to clipboard
llvm
[MLIR] backward dataflow
MLIR currently supports forward dataflow (Analysis/Dataflow/{Dense,Sparse}Analysis.h), but not backward dataflow.
The latter would e.g. be needed for removing unused arguments and results from functions. For example, it would allow us to remove %2 from
func private @recursive(%1, %2) {
SomeOp(%1)
call @recursive %1, %2
}
by propagating liveness upwards (starting from SomeOp and the callers of the function). Similarly, if we know all the callers we can remove %2 from f below:
func @f(%1, %2) {
return %1, %2
}
%c, %unused = f(%a, %b)
Backward dataflow can likely use DataFlowFramework.h, for symmetry with forward dataflow.
If this isn't something that should be done urgently, and this isnt worked on already, I'd like to try to make this analysis pass
Yeah, this one's up for grabs, as far as I can tell. Glad to hear you'll take it on, Ofek! Happy hacking. :) Let me know if I can help with anything.
hello, https://github.com/llvm/llvm-project/blob/main/mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp seems to implement a lot of stuff already. mostly what I need is to make all the visit functions depth-first, correct? if thats true, seems like a waste of space not to reuse some stuff. that would be a bigger change, though. what do you think?
I agree, you could (re)use DenseAnalysis.cpp, make it bidirectional. What pattern were you thinking of using for determining the direction? Overloads? "if (this->forward) {...} else {...}"? Some kind of visitor interface?
Overloads do sound nice, or maybe a initializeBackward and initializeForward and the solver handles that?
Not sure the solver should be direction-aware. Direction seems more a property of the callgraph / lattice, not of the solver. (Then again, the solver comments say the analysis starts at the top level operation...)
It still makes sense to start at the top and call the function recursively. I said the solver could do it just because it'd be a nice syntax, but I agree. How would you do it?
I've been wondering whether we need the concept of a "direction boolean" (or overload) at all.
Suppose our lattice elements support both join() and meet(), and both setEntryState() and setExitState(). In that case, dataflow could just always do its analysis bidirectionally, relying on the "*IfChanged" logic to terminate. Disadvantage is that you'd do unnecessary calls to either join() or meet(), for most analyses. (Also, there's some refactoring that would need to be done, since what's currently called join() is actually meet())
@silvasean made an attempt to write a backward analysis in TorchMLIR at some point, but I didn't hear much so I assumed he managed to make it work.
The framework is direction agnostic. The "top-level" operation is just the scope of the analysis the framework should care about. Analyses are free to visit the nested operations in whatever order works for them. The sparse and dense analyses, however, are coded as being forward. The idea is that you could write a BackwardDenseDataFlowAnalysis that looks quite similar to the current forward one.
I've been wondering whether we need the concept of a "direction boolean" (or overload) at all.
Suppose our lattice elements support both join() and meet(), and both setEntryState() and setExitState(). In that case, dataflow could just always do its analysis bidirectionally, relying on the "*IfChanged" logic to terminate. Disadvantage is that you'd do unnecessary calls to either join() or meet(), for most analyses. (Also, there's some refactoring that would need to be done, since what's currently called join() is actually meet())
@matthiaskramm can you elaborate more on what you mean with a concrete example? I think I sort of understand what you're getting at. I'm not opposed to adding a meet function for the sake of completeness.
So with a different class, how will you not duplicate a lot of code (it's not that much, but still mostly duplicated)?
So with a different class, how will you not duplicate a lot of code (it's not that much, but still mostly duplicated)?
Some code can probably be factored out, but still a lot will be duplicated or otherwise look very similar. I'm not advocating this approach, by the way, but I am saying that in theory that is one way it could be done.
Having one analysis that does both (forwards or backwards or even both at the same time) would be very cool.
I'm fine with that approach as long as it can be done without pulling out too much of the implementation code out into the public header files (maybe by explicitly instantiating the templates for backward and forward). Feel free to tag me as a reviewer on any of your patches.
can you elaborate more on what you mean with a concrete example?
Currently the dense analysis implements join as:
void join(Lattice *lhs, const Lattice &rhs) {
propagateIfChanged(lhs, lhs->join(rhs));
}
(Sparse analysis is similar)
You would replace that with
void joinAndMeet(Lattice *lhs, Lattice *rhs) {
propagateIfChanged(lhs, lhs->meet(*rhs));
propagateIfChanged(rhs, rhs->join(*lhs));
}
so what do you think? Im not sure whether to use your (mattihas') solution or a template. the start/stop based solution is quite cool, but as you said, it would add multiple additional meets/joins
I like the template idea, it's the one that incurs the smallest performance penalty, and is also probably the one that's easiest to reason about.
Sure, it'd be easier to do anyways. Probably explicitly instantiating the templates in the definition of the methods is the nicest way. Thanks
hmm, visitOperation doesnt look like it needs to be changed at all, except for the join/meet part, which could be even cut out with another method called joinOrMeet. what pattern should be used here?
Can you post a draft patch to phabricator? It might be easier to look at there
hmm, sorry, I think I should start by implementing the backward analysis by itself in another source file, then try and merge it with the forward implementation. also, seems like I need to do some work with the predecessors, as I need the successors, not the predecessors... or do I?
In theory, there could be a way to (somehow) turn the predecessor graph into a successor graph. But the most straightforward implementation likely computes the successors directly. (You might need some CallGraph changes)
I think you can ignore the interprocedural bit for now. It makes things a little too complicated. The predecessor state can be augment to include the other direction, but this might slow things down
so whatever is using predecessor state I can leave alone and just use? I didnt know whether I should do that..
okay. Im a little sick currently and really cant do this in a reasonable amount of time. Im sorry that I wasted your time and Ill contribute in other areas. if there'll be a patch for this Id be happy to have a look (not to review, Im not qualified) as this is still a cool place of code and if I find something that I can do Ill register into it
Played around with this a little more. The idea of making the analysis bidirectional in all cases, while enticing, suffers from the problem that the dataflow framework makes some unidirectional assumptions, e.g. that the querying state depends on the query. Also, always running bidirectional would incur a performance regression for the default (forward) case.
A more promising direction seems to be: Add a Backwards(Sparse)DataFlowAnalysis class that walks in the opposite direction (uses getDefiningOp instead of getUsers, etc.), but use the same Lattice class (that has both meet and join). If true bidirectional analysis is required (e.g. for type inference), the user can just hook both analyses into the solver and subscribe them to each other.
Draft implementation in https://reviews.llvm.org/D137648 (no blocks yet)
Notes:
- This uses one extra pointer in the lattice elements for the forward case, because of the (empty) virtual meet function. There's possibly some template (or multi-inheritance) magic one could do here, but it won't help readability, so not sure whether it's worth it?
- Names are a bit long. "AbstractSparseBackwardDataFlowAnalysis" is quite a mouthful.