This is an archive of the discontinued LLVM Phabricator instance.

[mlir] Refactor the forward dataflow propagation in SCCP into a generic framework
ClosedPublic

Authored by rriddle on Apr 20 2021, 4:49 PM.

Details

Summary

This revision takes the forward value propagation engine in SCCP and refactors it into a more generalized forward dataflow analysis framework. This framework allows for propagating information about values across the various control flow constructs in MLIR, and removes the need for users to reinvent the traversal (often not as completely). There are a few aspects of the traversal, that were conservative for SCCP, that should be relaxed to support the needs of different value analyses. To keep this revision simple, these conservative behaviors will be left in (Note that this won't produce an incorrect result, but may produce more conservative results than necessary in certain edge cases. e.g. region entry arguments for non-region branch interface operations). The framework also only focuses on computing lattices for values, given the SCCP origins, but this is something to relax as needed in the future.

Given that this logic is already in SCCP, a majority of this commit is NFC. The more interesting parts are the interface glue that clients interact with.

Diff Detail

Event Timeline

rriddle created this revision.Apr 20 2021, 4:49 PM
rriddle requested review of this revision.Apr 20 2021, 4:49 PM
silvas added inline comments.Apr 20 2021, 6:15 PM
mlir/docs/Tutorials/DataFlowAnalysis.md
28

add "for a given Value"?

102

describe axioms:

  1. idempotence: join(x,x) == x
  2. commutativity: join(x,y) == join(y,x)
  3. associativity: join(x,join(y,z)) == join(join(x,y),z)

These imply monotonicity, which is join(x, join(x,y)) == join(x,y) (apply associativity and then idempotence).

145

Strictly speaking, the "lattice" is the set of all possible states of statically known knowledge, but here you use "lattice" to describe just tone of those states (or "elements" of the lattice). I think you need to do some renamings here to clarify the distinction between those two (I think most things need to be renamed to "LatticeElement")

(see e.g. llvm/include/llvm/Analysis/ValueLattice.h ValueLatticeElement -- note the "element")

See also: https://en.wikipedia.org/wiki/Lattice_(order)
Note that since we don't explicitly materialize the notion of "<=" that is part of the mathematical definition, we rely on join(x,y) == y to mean x <= y.

171

typo: is represents.

243

can you explain how we know that we don't need to use tryGetLatticeFor here?

mlir/include/mlir/Analysis/DataFlowAnalysis.h
11

We should probably be specific that this is for forward, sparse dataflow (i.e. only along use-def chains), and only for pessimistic dataflow analysis algorithms, with the slight caveat that it optimistically assumes that predecessor successor args for not-yet-visited blocks are the "most optimistic lattice element" (though we don't explicitly represent that concept in the API).

32

Can you say something like "boolean operators behave as though Change is truthy".

54

should this be in a "detail" namespace? Is there any scenario where a user would use this class?

171

why do you need the distinction between knownValue and optimisticValue? Can't we just have one and initialize it to the pessimistic fixed point?

seems like an artifact of this being a pessimistic but also kind of optimistic dataflow analysis.

This is really exciting and I'm excited to start using it - thanks River! I'll take a deeper look at the API and may ask you a question or two as I try to figure out how to hold it correctly :)

rriddle updated this revision to Diff 340162.Apr 23 2021, 2:13 PM
rriddle marked 6 inline comments as done.

Address most comments

mlir/docs/Tutorials/DataFlowAnalysis.md
145

Yeah, I was being lazy and didn't want to type out Element. Renamed to avoid confusion.

mlir/include/mlir/Analysis/DataFlowAnalysis.h
171

We can't always refine the pessimistic value to something more optimistic. For SCCP a pessimistic state of "no constant" can't refine into a constant state.

silvas accepted this revision.Apr 23 2021, 2:43 PM

I still caught a few places using bare "lattice" (noted some; more exist). There are a lot of cases where you say "lattice value" or "lattice state" as well which probably should all be normalized to "lattice element".

mlir/docs/Tutorials/DataFlowAnalysis.md
28

lattice element.

32

lattice element

46

value -> element

50

this is not a very useful link for this context. Probably better to say that join(x, join(x, y)) == join(x, y) or say (see below).

215

lattice element

216

obtained and join'ed into.

227

lattice state -> lattice elements

229

"also known as the transfer function for the operation".

247

lattice element.

251

lattice element.

274

latticeElement/element variable name is probably better.

mlir/include/mlir/Analysis/DataFlowAnalysis.h
11

Please follow up on this one. For the aid of practitioners familiar with the terms, you can probably just include at the bottom "forward, sparse, pessimistic (except along unreached backedges) and context-insensitive for the interprocedural aspects" (that should be enough for people familiar with the terms).

208

s/lattice value/lattice element/ (here and throughout the patch, for consistency)

Also rename method to getLatticeElementFor (same for tryGetLatticeFor) (can probably drop the "For" as well.)

238

lattice value -> lattice element

251

lattice element.

mlir/lib/Analysis/DataFlowAnalysis.cpp
20

missing 'element'.

40

value -> element

This revision is now accepted and ready to land.Apr 23 2021, 2:43 PM
rriddle updated this revision to Diff 340710.Apr 26 2021, 7:34 PM
rriddle marked 20 inline comments as done.

update

This revision was landed with ongoing or failed builds.Apr 26 2021, 7:40 PM
This revision was automatically updated to reflect the committed changes.

Thanks for the detailed review Sean! Very appreciated.