This is an archive of the discontinued LLVM Phabricator instance.

[mlir] An implementation of sparse data-flow analysis

Authored by Mogball on Jun 6 2022, 11:32 AM.



This patch introduces a (forward) sparse data-flow analysis implemented with the data-flow analysis framework. The analysis interacts with liveness information that can be provided by dead-code analysis to be conditional. This patch re-implements SCCP using dead-code analysis and (conditional) constant propagation analyses.

Depends on D127064

Diff Detail

Event Timeline

Mogball created this revision.Jun 6 2022, 11:32 AM
Herald added a project: Restricted Project. · View Herald Transcript
Mogball requested review of this revision.Jun 6 2022, 11:32 AM
Mogball updated this revision to Diff 434557.Jun 6 2022, 12:02 PM

add comment blocks

Mogball edited the summary of this revision. (Show Details)
Mogball updated this revision to Diff 434873.Jun 7 2022, 10:23 AM


Mogball updated this revision to Diff 436581.Jun 13 2022, 3:00 PM

add code blocks

phisiart accepted this revision.Jun 24 2022, 12:47 AM
phisiart added inline comments.
570 ↗(On Diff #436581)

Maybe move this to a dedicated file SparseConstantPropagation.{h,cpp}?

493 ↗(On Diff #436581)

My guess is that we are not using getOrCreateFor to create a dependency here because the dependency is already handled by blockContentSubscribe, right?

If so, can we claim that Executable never uses the "default" dependency management (AnalysisState::dependents)?

If so, can we unify the dependency management approaches?

One potential approach is that AnalysisState exposes two callbacks:

  • onGet(DataFlowAnalysis *analysis, ProgramPoint pointBeingVisited)

    This unifies the behaviors of getOrCreateFor, blockContentSubscribe, useDefSubscribe.
  • onUpdate()

    This unifies the current onUpdate and the default behavior in propagateIfChanged.
581–582 ↗(On Diff #436581)
for (auto &[operand, lattice] : llvm::zip(call.getArgOperands(), argLattices))
  join(lattice, *getLatticeElementFor(block, operand));

This requires C++17, though. If MLIR codebase allows C++17, can we change all such zip-for loops?

This revision is now accepted and ready to land.Jun 24 2022, 12:47 AM
phisiart added inline comments.Jun 24 2022, 1:09 AM
493 ↗(On Diff #436581)

Ugh, just saw that in the next patch AbstractDenseDataFlowAnalysis::visitOperation() calls getOrCreateFor<Executable>(...).

Feel free to discard this comment, then. However, I do hope that dependency management can be more unified, in some way...

Mogball marked an inline comment as done.Jun 24 2022, 10:54 AM
Mogball added inline comments.
493 ↗(On Diff #436581)

On average, I would describe the *subscribe functions as being performance hacks.

All analysis states have the "generic" dependency management method (a hash map), but this state and AbstractLattice have another layer of dependency management that is more efficient with respect to certain kinds of analyses. I will admit this is a little weird.

Unifying the dependency management would be:

  1. Each analysis state is entirely responsible for managing its dependencies.
  2. Certain states, such as AbstractLattice and Executable, would implement an addDependency hook that has a different contract: "if this state is updated, the dependent analyses are re-invoked on all users of the value/operations in the block".

But I worry this constricts dependency management too much. What happens if an analysis needs to be depend on Executable in a different way? Its dependency management would have to be updated... Although it is true here that I am modifying Executable just to make a few analyses run faster, that's why I called it a hack 😆

AbstractDenseAnalysis could be changed to use blockContentSubscribe actually. I might be worrying too much about over-constraining the API. I'll do another iteration to try to address the dependency management.

581–582 ↗(On Diff #436581)

Not yet, unfortunately.

Have you updated with the next iteration you mentioned in the comment? Want to make sure I'm not reviewing something stale.

570 ↗(On Diff #436581)

+1. Can we please avoid having this file be a collection of all of the analyses/states/etc.? I'm wary of ending up in the state of the Attributor from LLVM which is currently ~5k lines. We should chunk things up and using a nested directory should help prevent blowing up Analysis/

Mogball updated this revision to Diff 441208.Jun 29 2022, 5:04 PM
Mogball marked an inline comment as done.

Update file splitting

rriddle accepted this revision.Jul 6 2022, 2:29 AM
rriddle added inline comments.

If this is a block

This always passes in a block? What do you mean here?


Can we have a static assert for this?


Can we merge these two functions? i.e. markPessimisticFixpoint(ArrayRef<AbstractSparseLattice *> lattices)? I don't think the separation really buys anything. Also, please drop the trivial braces.


What does a failure here signify? I'd rather not emit an error like this if it's going to be opaque.

Mogball updated this revision to Diff 442974.Jul 7 2022, 10:14 AM
Mogball marked 4 inline comments as done.

review comments

Mogball updated this revision to Diff 442976.Jul 7 2022, 10:16 AM

review comments

This revision was landed with ongoing or failed builds.Jul 7 2022, 10:17 AM
This revision was automatically updated to reflect the committed changes.