This is an archive of the discontinued LLVM Phabricator instance.

[mlir] Add Dead Code Analysis
ClosedPublic

Authored by Mogball on Jun 4 2022, 7:45 PM.

Details

Summary

This patch implements the analysis state classes needed for sparse data-flow analysis and implements a dead-code analysis using those states to determine liveness of blocks, control-flow edges, region predecessors, and function callsites.

Depends on D126751

Diff Detail

Event Timeline

Mogball created this revision.Jun 4 2022, 7:45 PM
Herald added a project: Restricted Project. · View Herald Transcript
Mogball requested review of this revision.Jun 4 2022, 7:45 PM
rriddle added inline comments.Jun 4 2022, 8:41 PM
mlir/include/mlir/Analysis/DataFlowFramework.h
52

Thanks for adding these comment blocks, can you merge these into the base commit?

Mogball updated this revision to Diff 434507.Jun 6 2022, 9:25 AM
Mogball marked an inline comment as done.

comoment blocks

Mogball updated this revision to Diff 434871.Jun 7 2022, 10:22 AM

clang-format

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

add code blocks

phisiart accepted this revision.Jun 23 2022, 10:24 PM
phisiart added inline comments.
mlir/include/mlir/Analysis/SparseDataFlowAnalysis.h
33 ↗(On Diff #436580)

I feel like "lattice" is a generic term and shouldn't be limited to sparse analyses. Can we rename this to AbstractSparseLattice?

49 ↗(On Diff #436580)

I don't think we have time to discuss/address this, so just a comment here:

The concepts of pessimistic/optimistic fixpoint and known/optimistic value are really uncommon, and we probably should get rid of it...

53 ↗(On Diff #436580)

As discussed earlier today, can we remove markOptimisticFixpoint() since it's not used? (I personally think that the pessimistic value should never change.)

325 ↗(On Diff #436580)

know

332 ↗(On Diff #436580)

knownPredecessors?

342 ↗(On Diff #436580)

Note that there's inconsistency in the naming style.

GenericProgramPointBase<...> : GenericProgramPoint
Lattice<...> : AbstractLattice

Can we converge to a single naming style?

371 ↗(On Diff #436580)

Can we move this to a separate file, maybe DeadCodeAnalysis.{h,cpp}? Likewise we probably need a ConstantPropagationAnalysis.{h,cpp}.

DeadCodeAnalysis is not a sparse analysis, right? I personally think that it's hard to classify it as either sparse or dense, and it does not inherit from SparseDataFlowAnalysis in the next patch.

Even if it is a sparse analysis, I still think it's worthwhile to create a dedicated file for it.

This revision is now accepted and ready to land.Jun 23 2022, 10:24 PM
Mogball marked an inline comment as done.Jun 24 2022, 10:32 AM
Mogball added inline comments.
mlir/include/mlir/Analysis/SparseDataFlowAnalysis.h
33 ↗(On Diff #436580)

SG

49 ↗(On Diff #436580)

These concepts came from the original SCCP paper that developed the idea of an optimistic analysis. The idea of an optimistic value is, for an analysis, given its current, limited view of the IR, it is the best guess the analysis can provide to the state. If later, a conflicting value is discovered, it falls back to a value that is guaranteed to be true.

It's possible this concept is tied too much to SCCP (e.g. in integer range analysis, the pessimistic fixpoint is actually (-inf, +inf), and so having a "known" and "optimistic" value isn't needed).

53 ↗(On Diff #436580)

Yes. It's not used anywhere and it wasn't used in many places in the previous framework too.

342 ↗(On Diff #436580)

This naming style is consistent with the rest of MLIR.

Roughly speaking:

  1. *Base refers to a concrete implementation of a class, where the implementing class is what's meant to be used. For example, GenericProgramPoint * is never used anywhere in the code, but CFGEdge is.
  2. Abstract* means the class is closer to the notion of an abstract class, where subclasses override virtual functions but code is written to manipulate Abstract*.
Mogball updated this revision to Diff 440405.Jun 27 2022, 3:00 PM
Mogball marked 5 inline comments as done.

review comments

rriddle requested changes to this revision.Jun 29 2022, 12:06 AM

Looks fairly good, a lot seems to be adapted from other places so much of it isn't too surprising.

mlir/include/mlir/Analysis/SparseDataFlowAnalysis.h
180 ↗(On Diff #436580)

Drop the braces here.

202 ↗(On Diff #436580)

We should move these into a nested namespace, we shouldn't pollute mlir with such generally named things as these.

218 ↗(On Diff #436580)
289 ↗(On Diff #436580)

Will note that the name "Predecessor" here was quite confusing because I expected this to be about Blocks, not operations. Can you clarify further what it means to be a "predecessor" here?

307–309 ↗(On Diff #436580)

You could also use std::exchange here to drop a line.

371 ↗(On Diff #436580)

+1 here! I would also start a new DataFlowAnalysis/ directory to hold these things.

mlir/lib/Analysis/SparseDataFlowAnalysis.cpp
52–54 ↗(On Diff #436580)

nit: Ifs with nested fors need braces.

353–354 ↗(On Diff #436580)
This revision now requires changes to proceed.Jun 29 2022, 12:06 AM
Mogball updated this revision to Diff 441081.Jun 29 2022, 10:53 AM
Mogball marked 8 inline comments as done.

Split SparseDataFlowAnalysis.h/cpp into

DataFlow/ConstantPropagationAnalysis
DataFlow/DeadCodeAnalysis
DataFlow/SparseAnalysis

rriddle accepted this revision.Jun 30 2022, 2:47 AM
rriddle added inline comments.
mlir/include/mlir/Analysis/DataFlow/DeadCodeAnalysis.h
21

Do we need all of these includes? Can you forward declare instead?

This revision is now accepted and ready to land.Jun 30 2022, 2:47 AM
Mogball updated this revision to Diff 441510.Jun 30 2022, 1:50 PM
Mogball marked an inline comment as done.

trim includes

This revision was landed with ongoing or failed builds.Jun 30 2022, 1:51 PM
This revision was automatically updated to reflect the committed changes.