This is an archive of the discontinued LLVM Phabricator instance.

[mlir] An implementation of dense data-flow analysis
ClosedPublic

Authored by Mogball on Jun 6 2022, 7:13 PM.

Details

Summary

This patch introduces an implementation of dense data-flow analysis. Dense
data-flow analysis attaches a lattice before and after the execution of every
operation. The lattice state is propagated across operations by a user-defined
transfer function. The state is joined across control-flow and callgraph edges.

Thge patch provides an example pass that uses both a dense and a sparse analysis
together.

Depends on D127139

Diff Detail

Event Timeline

Mogball created this revision.Jun 6 2022, 7:13 PM
Herald added a project: Restricted Project. · View Herald Transcript
Mogball requested review of this revision.Jun 6 2022, 7:13 PM
Mogball updated this revision to Diff 434874.Jun 7 2022, 10:23 AM

clang-format

Mogball updated this revision to Diff 436582.Jun 13 2022, 3:01 PM

add code blocks

phisiart accepted this revision.Jun 24 2022, 1:59 AM
phisiart added inline comments.
mlir/include/mlir/Analysis/DenseDataFlowAnalysis.h
31

We can actually see that AbstractDenseLattice is a base class of AbstractLattice (reset == markPessimisticFixpoint ).

Can we (1) rename AbstractLattice to AbstractSparseLattice; (2) rename AbstractDenseLattice to AbstractLattice; (3) let the new AbstractLattice be a base class of the new AbstractSparseLattice?

mlir/lib/Analysis/DenseDataFlowAnalysis.cpp
44

When I was playing with DenseDataFlowAnalysis, I didn't know that it depends on Executable. This hidden dependency means that any DenseDataFlowAnalysis must either (1) run alongside DeadCodeAnalysis, or (2) manually initialize Executable::setLive on all blocks.

Nothing to do now, but in the future can we make this more explicit?

One possible approach might be:

Each analysis must register all state types that it reads and writes (maybe through template arguments or TypeIDs). For example, DenseDataFlowAnalysis reads {Executable, PredecessorState, LatticeT}, and writes {LatticeT}.

Moreover, DenseDataFlowAnalysis could specify that Executable is optional, and if no other analysis writes Executable, DenseDataFlowAnalysis would assume always Executable::isLive.

This revision is now accepted and ready to land.Jun 24 2022, 1:59 AM
Mogball added inline comments.Jun 24 2022, 11:01 AM
mlir/include/mlir/Analysis/DenseDataFlowAnalysis.h
31

I can give it a go.

mlir/lib/Analysis/DenseDataFlowAnalysis.cpp
44

Each analysis must register all state types that it reads and writes (maybe through template arguments or TypeIDs). For example, DenseDataFlowAnalysis reads {Executable, PredecessorState, LatticeT}, and writes {LatticeT}.

This makes sense to me if there was some functional reason for an analysis to state its inputs. If it's readability, a comment will suffice. Also, dependencies can be dynamic.

Moreover, DenseDataFlowAnalysis could specify that Executable is optional, and if no other analysis writes Executable, DenseDataFlowAnalysis would assume always Executable::isLive.

This is what nudging is for! Although, following recent discussion on the discourse, I believe the new formulation would say Reduce(intersect, Liveness({})) => true

Mogball updated this revision to Diff 441209.Jun 29 2022, 5:08 PM

Split files

rriddle accepted this revision.Jul 6 2022, 2:33 AM
rriddle added inline comments.
mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h
31–33 ↗(On Diff #441209)

nit: Can you sink this next to the join method?

mlir/include/mlir/Analysis/DataFlow/DenseAnalysis.h
130 ↗(On Diff #441209)

Can we static assert this?

Mogball updated this revision to Diff 443073.Jul 7 2022, 3:12 PM
Mogball marked 2 inline comments as done.

review comments

This revision was landed with ongoing or failed builds.Jul 7 2022, 3:12 PM
This revision was automatically updated to reflect the committed changes.