This is an archive of the discontinued LLVM Phabricator instance.

Differential D43695

[IPSCCP] do not break musttail invariant (PR36485)
ClosedPublic

Authored by indutny on Feb 23 2018, 2:08 PM.

Details

Reviewers
davide
sanjoy
bruno
• dberlin
fhahn
efriedma
Commits
rG3318c1d6a771: Merging r326404:
rG3762a089d741: [IPSCCP] do not break musttail invariant (PR36485)
rL329855: Merging r326404:
rL326404: [IPSCCP] do not break musttail invariant (PR36485)
Summary

Do not replace results of musttail calls with a constant if the
call itself can't be removed.

Do not zap returns of musttail callees, if the call site can't be
removed and replaced with a constant.

Do not zap returns of musttail-calling blocks, this breaks
invariant too.

Diff Detail

Event Timeline

indutny created this revision.Feb 23 2018, 2:08 PM
indutny updated this revision to Diff 135713.Feb 23 2018, 3:04 PM

Move test file into a proper directory.

indutny added a comment.Feb 23 2018, 6:05 PM

A question: what is backport policy of LLVM project? I'd love to see this fix in 5.0.0 .

indutny updated this revision to Diff 135760.Feb 23 2018, 6:19 PM
indutny removed a reviewer: llvm-commits.
indutny added a subscriber: llvm-commits.

Removed FileCheck from the test. It's enough if it doesn't crash, there's nothing to validate.

junbuml added a subscriber: junbuml.Feb 26 2018, 9:17 AM
indutny added a comment.Feb 26 2018, 9:51 PM

I think I've "under-implemented" the fix here. First of all, it doesn't mark callees overdefined, which leads to zapped return value. Second, it basically kills whole optimization because of musttail call site.

What would be the proper implementation in this case? I've few ideas, but I could easily underestimate the scope of the problem.

fhahn added reviewers: fhahn, efriedma.Feb 27 2018, 1:28 AM
fhahn added a subscriber: fhahn.

Thanks for the patch! Unless I miss something, we might be able to continue using the more precise lattice value while solving and only handle it when doing the actual replacement. Eli, it would be great if you could have a quick look and see if that makes sense.

Removed FileCheck from the test. It's enough if it doesn't crash, there's nothing to validate.

Could you add some checks again, checking the musttail calls are preserved? Otherwise, we could do lots of things to "not crash".

lib/Transforms/Scalar/SCCP.cpp
1234

This is not the place where the actual replacement happens. I think we could keep the lattice value for the musttail call here and continue using it for solving. The replacement happens in tryToReplaceWithConstant. We could check for musttail calls there and do the replacement there.

This way, in case we can determine the return value of a function containing musttail calls, we still can use the return value at the callsite while solving.

Also, in case the musttail callee has no side effects, the call will be removed (D38856), and we could replace the result with the constant.

indutny updated this revision to Diff 136135.Feb 27 2018, 12:27 PM
indutny marked an inline comment as done.

I've addressed your feedback, and covered more erroneous cases in my patch now.

Thank you!

indutny retitled this revision from [IPSCCP] mark musttail calls overdefined (PR36485) to [IPSCCP] do not break musttail invariant (PR36485).Feb 27 2018, 12:29 PM
indutny edited the summary of this revision. (Show Details)
efriedma accepted this revision.Feb 28 2018, 12:45 PM

LGTM

This revision is now accepted and ready to land.Feb 28 2018, 12:45 PM
indutny added a comment.Feb 28 2018, 12:48 PM

Thank you!

efriedma added a comment.Feb 28 2018, 1:09 PM

Oh, forgot to ask; do you have commit access? If not, I can commit for you.

fhahn accepted this revision.Feb 28 2018, 1:10 PM

Thanks for updating the patch and thanks Eli for having a look. LGTM too

indutny added a comment.Feb 28 2018, 1:13 PM

I don't have commit access yet. Would greatly appreciate if you could land it for me. Thank you!

davide accepted this revision.Feb 28 2018, 4:58 PM

LGTM too. Sorry I'm a little behind with reviews because life took over.

Closed by commit rL326404: [IPSCCP] do not break musttail invariant (PR36485) (authored by rnk). · Explain WhyFeb 28 2018, 5:21 PM
This revision was automatically updated to reflect the committed changes.
indutny added a comment.Feb 28 2018, 6:21 PM

Thank you, everyone!

Revision Contents

PathSize
lib/
Transforms/
Scalar/
4 lines
test/
Transforms/
IPConstantProp/
28 lines

Diff 135713

lib/Transforms/Scalar/SCCP.cpp

Show First 20 Lines • Show All 1,223 Lines • ▼ Show 20 LinesCallOverdefined:
} else { } else {
DenseMap<Function*, LatticeVal>::iterator TFRVI = TrackedRetVals.find(F); DenseMap<Function*, LatticeVal>::iterator TFRVI = TrackedRetVals.find(F);
if (TFRVI == TrackedRetVals.end()) if (TFRVI == TrackedRetVals.end())
goto CallOverdefined; // Not tracking this callee. goto CallOverdefined; // Not tracking this callee.
// If so, propagate the return value of the callee into this call result. // If so, propagate the return value of the callee into this call result.
mergeInValue(I, TFRVI->second); mergeInValue(I, TFRVI->second);
} }
// Replacing `musttail` instructions with constant breaks `musttail` semantics
if (CS.isMustTailCall())
fhahnUnsubmitted
Done
ReplyInline Actions

This is not the place where the actual replacement happens. I think we could keep the lattice value for the musttail call here and continue using it for solving. The replacement happens in tryToReplaceWithConstant. We could check for musttail calls there and do the replacement there.

This way, in case we can determine the return value of a function containing musttail calls, we still can use the return value at the callsite while solving.

Also, in case the musttail callee has no side effects, the call will be removed (D38856), and we could replace the result with the constant.

fhahn: This is not the place where the actual replacement happens. I think we could keep the lattice…
return markOverdefined(I);
} }
void SCCPSolver::Solve() { void SCCPSolver::Solve() {
// Process the work lists until they are empty! // Process the work lists until they are empty!
while (!BBWorkList.empty() || !InstWorkList.empty() || while (!BBWorkList.empty() || !InstWorkList.empty() ||
!OverdefinedInstWorkList.empty()) { !OverdefinedInstWorkList.empty()) {
// Process the overdefined instruction's work list first, which drives other // Process the overdefined instruction's work list first, which drives other
// things to overdefined more quickly. // things to overdefined more quickly.
▲ Show 20 Lines • Show All 806 Lines • Show Last 20 Lines

test/Transforms/IPConstantProp/musttail-call.ll

  • This file was added.
; RUN: opt < %s -ipsccp -S | FileCheck %s
; PR36485
declare i32 @external()
define i8* @start(i8* %p, i8* %endp, i32 %match) {
%i0 = icmp ne i8* %p, %endp
br i1 %i0, label %b0_has_data, label %b1_no_data
b0_has_data:
%i2 = load i8, i8* %p
switch i8 %i2, label %b2_switch_otherwise [ i8 32, label %b3_case_32 ]
b1_no_data:
%i3 = bitcast i8* (i8*, i8*, i32)* @start to i8*
ret i8* %i3
b2_switch_otherwise:
%i4 = musttail call i8* @start(i8* %p, i8* %endp, i32 0)
ret i8* %i4
b3_case_32:
%i5 = musttail call i8* @invoke(i8* %p, i8* %endp, i32 0)
ret i8* %i5
}
define internal i8* @invoke(i8* %p, i8* %endp, i32 %match) {
%i1 = call i32 @external()
%i2 = musttail call i8* @start(i8* %p, i8* %endp, i32 0)
ret i8* %i2
}