This is an archive of the discontinued LLVM Phabricator instance.

[mlir] Implement backward dataflow.
ClosedPublic

Authored by matthiaskramm on Nov 29 2022, 11:22 AM.

Details

Summary

This enables interprocedural lifeness analysis, very busy expression
analysis, etc.

Diff Detail

Event Timeline

matthiaskramm created this revision.Nov 29 2022, 11:22 AM
Herald added a project: Restricted Project. · View Herald Transcript
matthiaskramm requested review of this revision.Nov 29 2022, 11:22 AM
matthiaskramm retitled this revision from [mlir] Implement backwards dataflow. to [mlir] Implement backward dataflow..Nov 29 2022, 11:26 AM

Very exciting. I'll take a closer look soon

Mogball added inline comments.Dec 3 2022, 3:55 AM
mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h
131

Can you clarity that meet is a co-op rather than "the method doesn't exist"? The latter doesn't seem accurate

131

No-op*

137

Can you look at uses of llvm::is_detected and use that here instead?

342

Can you file an issue to rename the other one to AbstractSparseForwardAnalysis? I think you can name this one AbstractSparseBackwardAnalysis instead for brevity.

350

Is this comment still accurate?

386

Same here. Result vs operand

393

Please use backticks when naming using op ASM names in doc comments

mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp
356

Please drop trivial braces

360

Can you spell out both these autos?

363

Can you please spell out this auto? Auto should only be used if the type can be found on the RHS of the assignment, e.g. from cast or dyn_cast. Please do this for all autos.

364

I'm not sure this is correct. This propagates an update to all users of the result. You want to propagate an update to all operands of the defining operation.

376

I don't think you need a BitVector since the forwarded operands are contiguous

377

With C++17 you can use a structured binding

414

Please use a structured binding if you can

424

Is this correct? I think you should start from all blocks that terminate with a ReturnLike operation

435

Can you name this something more general than "yield"? Like "terminator"

444

Same here. The forwarded arguments are required to be contiguous

485

Can you merge these branches?

542

Can you just delete this function then?

matthiaskramm added inline comments.Dec 5 2022, 8:54 AM
mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp
444

Thanks for the thorough review! Will send an updated version later this week.

For the BitVector, wouldn't implementations of RegionBranchTerminatorOpInterface be able to create an OperandRange that's unrelated (in terms of order) to the OperandRange of the op? Or can we assume nobody does that?

Mogball added inline comments.Dec 5 2022, 10:15 AM
mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp
444

OperandRange has to be contiguous

Addressed review comments.

matthiaskramm marked 17 inline comments as done.Dec 6 2022, 10:58 AM
matthiaskramm added inline comments.
mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp
364

Good catch. We need to use a getLatticeElementFor(...) on the results. Also added a test.

376

If there are multiple successors, then there might be multiple (discontiguous) ranges of operands. Those ranges might overlap, so we can't even use some kind of interval logic.

Added comments. Also, moved one of the BitVectors out of the loop.

424

Removed this code, since it was a no-op. We do indeed start from the ReturnLikes, but only in public functions.

444

See above. The way I understand it, each set of forwarded arguments is contiguous, but there might be more than one, and each of them is an arbitrary subsequence of the terminator's operands.

Mogball added inline comments.Dec 9 2022, 4:15 PM
mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h
98

I wouldn't use const in a type alias

409

Can you actually make the analysis carry a SymbolTableCollection & and require a reference be passed in through the constructor?

mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp
309
385
402

question: why do you need to re-visit this operation if the operand updates? Is it because it might change the successors?

444

It's not normally the case, and in fact I'm not sure if such an operation would be well-formed given how the RegionBranchOpInterface has been implemented, but I don't mind the defensive coding -- it makes sense to me. Thanks.

444–445
480

can you spell out this auto?

485
519

This seems like a common pattern. Can you refactor it into a helper?

521
mlir/test/lib/Analysis/DataFlow/TestBackwardDataFlowAnalysis.cpp
23

could you just make this a struct?

26–28
75

please spell out these autos

89
118

please use a structured binding

125

same here

matthiaskramm marked 3 inline comments as done.

Address review comments.

  • Factor Operands -> OpOperands code into function
  • Pass SymbolTableCollection to the analysis
  • Weed out remaining "auto"s, use structured bindings in test
matthiaskramm marked 14 inline comments as done.

Cosmetic fixes.

  • Change two more instances of "auto it" to structured bindings.
  • Fix whitespace in class definition.
  • use Twice for string construction.
Mogball accepted this revision.Dec 12 2022, 10:20 PM

LGTM. Awesome job

This revision is now accepted and ready to land.Dec 12 2022, 10:20 PM
This revision was automatically updated to reflect the committed changes.