Inlining: Don't re-map simplified cloned instructions.
ClosedPublic

Authored by iteratee on Jun 2 2017, 1:53 PM.

Details

Summary

When simplifying an instruction that has been re-mapped, it should never
simplify to an instruction in the original function. In the edge case
where we are inlining a function into itself, the existing code led to
incorrect behavior. It would double-map an instruction: map-simplify-map.
The last map was incorrect, because the mapped instruction simplified to an instruction in the original portion of the function. An incoming value.
mapping this instruction would select the mapped version of this instruction in the newly inlined portion of the function. This wasn't correct, and would create uses not dominated by defs.

Replace the incorrect code with an assert verifying
that we never expect simplification to produce an instruction in the old
function, unless the functions are the same.

Diff Detail

Repository
rL LLVM
iteratee created this revision.Jun 2 2017, 1:53 PM
eraman added a comment.Jun 6 2017, 3:52 PM

From the summary:

When simplifying an instruction that has been re-mapped, it should never

simplify to an instruction in the original function.
This looks reasonable to me

In the edge case

where we are inlining a function into itself, the existing code led to
incorrect behavior.

The SimpleInliner doesn't do recursive inlining AFAIK. I thought there was a check in InlineFunction as well to disallow this, but I don't see it. So I guess a recursive call may get inlined. It is not obvious to me what the incorrect behavior is in that case. Could you please explain what causes the incorrect behavior?

Replace the incorrect code with an assert verifying

that we never expect simplification to produce an instruction in the old
function, unless the functions are the same.

The asserts look reasonable to me. I don't understand the intention of the original code though.

lib/Transforms/Utils/CloneFunction.cpp
457 ↗(On Diff #101273)

Unrelated change?

chandlerc accepted this revision.Jun 6 2017, 5:08 PM

I wrote this, but also have no memory of the intent. I'm pretty sure I was worried about something that could not in fact happen. I'm happy moving to an assert to check that in fact it does not happen. =]

LGTM with the suggestion from Easwaran and myself applied (and without the unrelated change).

lib/Transforms/Utils/CloneFunction.cpp
313 ↗(On Diff #101273)

Just use isa<...> here...

This revision is now accepted and ready to land.Jun 6 2017, 5:08 PM
iteratee edited the summary of this revision. (Show Details)Jun 7 2017, 10:51 AM
iteratee added inline comments.
lib/Transforms/Utils/CloneFunction.cpp
457 ↗(On Diff #101273)

Not unrelated. If you're inlining a function into itself, end() changes. I can make it a separate patch if you'd like, but I put it in this patch on purpose.

chandlerc requested changes to this revision.Jun 7 2017, 2:58 PM

I forgot to mention this: this needs a test case that would fail/crash before the patch. =]

lib/Transforms/Utils/CloneFunction.cpp
457 ↗(On Diff #101273)

I'd make it a separate patch (or update the patch description to talk about it).

But I also don't think this is quite correct -- even the new version computes the end iterator once and caches it, so I'm not sure how this fixes the issue cited.

This revision now requires changes to proceed.Jun 7 2017, 2:58 PM
iteratee added inline comments.Jun 7 2017, 3:11 PM
lib/Transforms/Utils/CloneFunction.cpp
457 ↗(On Diff #101273)

This isn't necessary for correctness, so I'll submit it separately. It removes unnecessary work.

What happens is that the blocks are batch cloned and then inserted. None of the new blocks are in the map, so nothing bad happens, but it's easier to reason about that if you don't visit the new blocks in the first place.

iteratee abandoned this revision.Jun 8 2017, 3:29 PM

No longer needed because of https://reviews.llvm.org/D34017

No longer needed because of https://reviews.llvm.org/D34017

I mean, it may not do *bad* things any more, but it still seems like an improvement? We shouldn't be doing the thing we're doing. Moving to an assert seems better?

https://reviews.llvm.org/D34017 prevents recursive inline from happening. But even with recursive inlining, it should not trigger compiler error. I think this patch is still needed to fix the underlying issue?

iteratee reclaimed this revision.Jun 21 2017, 11:18 AM

Chandler, After r305934 A test for this isn't possible. We should still commit the fix.

This revision now requires changes to proceed.Jun 21 2017, 11:18 AM

Sure, comments inline...

lib/Transforms/Utils/CloneFunction.cpp
313 ↗(On Diff #101273)

Still outstanding.

457 ↗(On Diff #101273)

I'll note that as currently written, this still walks from begin to end of OldFunc, which I'm pretty sure is what the old code did as well. Maybe I'm missing something, but this looks like a no-op change...

iteratee updated this revision to Diff 103437.Jun 21 2017, 12:02 PM
iteratee marked 2 inline comments as done.
iteratee added inline comments.Jun 21 2017, 12:02 PM
lib/Transforms/Utils/CloneFunction.cpp
457 ↗(On Diff #101273)

I'll pull it out separately, but explain it here.

458 ↗(On Diff #101273)

This line makes it a No-Op when we encounter the blocks added below.

The goal of the change was to make it so you don't have to find this line and do the reasoning yourself.

463 ↗(On Diff #101273)

You're missing this line here. When OldFunc == NewFunc, this line changes End.

sanjoy added inline comments.Jun 21 2017, 11:24 PM
lib/Transforms/Utils/CloneFunction.cpp
329 ↗(On Diff #103437)

You should be able to use cast<> instead of dyn_cast<>.

iteratee updated this revision to Diff 104074.Jun 26 2017, 6:58 PM

Use cast instead of dyn_cast

iteratee marked an inline comment as done.Jun 26 2017, 6:58 PM
chandlerc accepted this revision.Jun 27 2017, 1:36 AM

LGTM, thanks for cleaning this up even after the proximate issue was fixed!

This revision is now accepted and ready to land.Jun 27 2017, 1:36 AM
This revision was automatically updated to reflect the committed changes.
davide added a subscriber: davide.Jun 30 2017, 4:21 PM

This actually seem to happen, i.e. we hit this assertion. We have an end-to-end (i.e. C test) that reduces to:

define void @patatino() {
for.cond:
  br label %for.body

for.body:
  %tobool = icmp eq i32 5, 0
  %sel = select i1 %tobool, i32 0, i32 2
  br i1 undef, label %cleanup1.thread, label %cleanup1

cleanup1.thread:
  ret void

cleanup1:
  %cleanup.dest2 = phi i32 [ %sel, %for.body ]
  %switch = icmp ult i32 %cleanup.dest2, 1
  ret void
}

define void @main() {
entry:
  call void @patatino()
  ret void
}

crashing with opt -inline as when we call SimplifyInstruction

%switch = icmp ult i32 %cleanup.dest2, 1

simplifies to

%tobool = icmp eq i32 5, 0

This simplification, if something, is a little peculiar, as I expected that to just be simplified to false.

I looked at this more closely, and I personally don't see anything wrong with the code as-is.
We happen to have an instruction that simplifies to a different instruction in the original function (mainly because instsimplify does some hazy threading over select/phis), so maybe this assertion is too strict?
Kyle, what do you think?

If this got dropped I'm sorry.

This can be reverted.