This is an archive of the discontinued LLVM Phabricator instance.

[MLIR][analysis] Fix call op handling in sparse backward dataflow
ClosedPublic

Authored by srishti-pm on Aug 7 2023, 2:08 AM.

Details

Summary

Currently, data in AbstractSparseBackwardDataFlowAnalysis is
considered to flow one-to-one, in order, from the operands of an op
implementing CallOpInterface to the arguments of the function it is
calling.

This understanding of the data flow is inaccurate. The operands of such
an op that forward to the function arguments are obtained using a
method provided by CallOpInterface called getArgOperands().

This commit fixes this bug by using getArgOperands() instead of
getOperands() to get the mapping from operands to function arguments
because not all operands necessarily forward to the function arguments
and even if they do, they don't necessarily have to be in the order in
which they appear in the op. The operands that don't get forwarded are
handled by the newly introduced visitCallOperand() function, which
works analogous to the visitBranchOperand() function.

This fix is also propagated to liveness analysis that earlier relied on
this incorrect implementation of the sparse backward dataflow analysis
framework and corrects some incorrect assumptions made in it.

Extra cleanup: Improved a comment and removed an unnecessary code line.

Signed-off-by: Srishti Srivastava <srishtisrivastava.ai@gmail.com>

Diff Detail

Event Timeline

srishti-pm created this revision.Aug 7 2023, 2:08 AM
Herald added a project: Restricted Project. · View Herald Transcript
srishti-pm requested review of this revision.Aug 7 2023, 2:08 AM
matthiaskramm added inline comments.Aug 7 2023, 6:38 AM
mlir/lib/Analysis/DataFlow/LivenessAnalysis.cpp
59–60

I'm having a bit of difficulty parsing this sentence. Could you rephrase/clarify?

114

Is this still correct if the called block only produces non-live values?

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

I know the intention is the same as in unforwarded branch operands, but a call is a not a branch.

Add (or rename to) a new function, "visitNonForwardedOperand", "visitInternalOperand", or some such thing?

srishti-pm added inline comments.Aug 7 2023, 2:43 PM
mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp
441

Okay. Shall I just call it visitCallOperand()?

srishti-pm marked an inline comment as done.Aug 7 2023, 2:46 PM
srishti-pm added inline comments.
mlir/lib/Analysis/DataFlow/LivenessAnalysis.cpp
114

I think so, yes.

So, this is what I thought:-

A function call affects the stack. So, even when a function doesn't return any live results or have any live arguments, it still affects the memory. And thus, a non-forwarded call op operand should always be live. What do you think?

matthiaskramm added inline comments.Aug 7 2023, 3:16 PM
mlir/lib/Analysis/DataFlow/LivenessAnalysis.cpp
114

I'd argue that stack/memory are architecture specific, and we're at a level of compilation where we're not reasoning about machine-level semantics yet.

After all, we also do inlining, and that also affects the stack (moreover, the stack level of non-dead code!), but we consider that OK.

With that in mind, I think the correct thing to do here is to derive the liveness of each non-forwarded operand by doing the disjunction (meet) of the liveness of all forwarded operands.

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

Not sure. visitCallOperand() makes it sound like this would be called for all operands of a call?

srishti-pm updated this revision to Diff 547984.Aug 7 2023, 3:43 PM
srishti-pm marked an inline comment as done.

Address comments.

srishti-pm added inline comments.Aug 7 2023, 3:47 PM
mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp
441

I thought it would be analogous to the visitBranchOperand() function which is only called for the non-forwarded operands of a branch instruction. Or should I modify the naming of both these functions to visitNonForwardedBranchOperand() and visitNonForwardedCallOperand(), respectively?

// Visit operands on branch instructions that are not forwarded.
virtual void visitBranchOperand(OpOperand &operand) = 0;

// Visit operands on call instructions that are not forwarded.
virtual void visitCallOperand(OpOperand &operand) = 0;
srishti-pm marked an inline comment as done.Aug 7 2023, 3:50 PM
srishti-pm added inline comments.
mlir/lib/Analysis/DataFlow/LivenessAnalysis.cpp
59–60

Done.

114

Got it. Working on this.

srishti-pm marked an inline comment as done.Aug 7 2023, 4:35 PM
srishti-pm added inline comments.
mlir/lib/Analysis/DataFlow/LivenessAnalysis.cpp
114

With that in mind, I think the correct thing to do here is to derive the liveness of each non-forwarded operand by doing the disjunction (meet) of the liveness of all forwarded operands.

Actually, shouldn't a non-forwarded call op operand be live when a result of the call op is live or the function it calls have an op with memory effects? Its liveness will be independent of the liveness of the forwarded operands, right?

matthiaskramm added inline comments.Aug 7 2023, 6:30 PM
mlir/lib/Analysis/DataFlow/LivenessAnalysis.cpp
114

You're right, of course. The results determine the liveness.
And good point about memory effects. Unfortunately, that'll have to be recursive: If the function calls any other function which has memory effects, that also means it's live.

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

Ok, that's fair. No objection to your naming proposal!

srishti-pm marked 3 inline comments as done.Aug 8 2023, 2:05 AM
srishti-pm marked an inline comment as done.Aug 8 2023, 2:08 AM
srishti-pm marked an inline comment as done.Aug 9 2023, 11:28 AM
srishti-pm added inline comments.
mlir/lib/Analysis/DataFlow/LivenessAnalysis.cpp
114

Marked all non-forwarded call operands "live" conservatively based on our internal discussion. It won't allow very aggressive optimizations but at least it will be safe for optimization (marking something "live" is safer than marking it "non-live").

srishti-pm marked an inline comment as done.Aug 9 2023, 11:37 AM

Rebased to main.

All comments given so far in this patch have been addressed.

Awaiting more review comments and/or approval.

matthiaskramm accepted this revision.Aug 9 2023, 11:48 AM
This revision is now accepted and ready to land.Aug 9 2023, 11:48 AM
jcai19 accepted this revision.Aug 9 2023, 2:22 PM
jcai19 added inline comments.
mlir/include/mlir/Analysis/DataFlow/LivenessAnalysis.h
46

It's not quite clear to me what is 1.b

mlir/lib/Analysis/DataFlow/LivenessAnalysis.cpp
58

I don't fully understand this condition. It reads as if the value is an operand and a block?

jcai19 added inline comments.Aug 9 2023, 2:24 PM
mlir/include/mlir/Analysis/DataFlow/LivenessAnalysis.h
46

It's not quite clear to me what is 1.b

Please ignore.

srishti-pm added a reviewer: mehdi_amini.
srishti-pm updated this revision to Diff 548811.Aug 9 2023, 4:26 PM
srishti-pm marked 3 inline comments as done.

Address Jian's comments.

mlir/lib/Analysis/DataFlow/LivenessAnalysis.cpp
58

Fixed the language to make it clearer.

All comments are addressed here and it is approved by two reviewers. Will wait one more day before landing this in case other reviewers would like to suggest changes too :)

srishti-pm edited the summary of this revision. (Show Details)Aug 9 2023, 4:38 PM
srishti-pm edited the summary of this revision. (Show Details)Aug 9 2023, 5:14 PM

Rebased to main.