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

[iteratee]

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.

[eraman]

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

Unrelated change?

[chandlerc]

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

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

[iteratee]

lib/Transforms/Utils/CloneFunction.cpp

457

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]

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

lib/Transforms/Utils/CloneFunction.cpp

457

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.

[iteratee]

lib/Transforms/Utils/CloneFunction.cpp

457

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]

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

[chandlerc]

In D33850#776482, @iteratee wrote:

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?

[danielcdh]

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]

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

[chandlerc]

Sure, comments inline...

lib/Transforms/Utils/CloneFunction.cpp

313

Still outstanding.

457

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]

lib/Transforms/Utils/CloneFunction.cpp

457

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

458

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

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

[sanjoy]

lib/Transforms/Utils/CloneFunction.cpp

314

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

[iteratee]

Use cast instead of dyn_cast

[chandlerc]

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

[davide]

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.

[davide]

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?

[iteratee]

If this got dropped I'm sorry.

This can be reverted.

lib/Transforms/Utils/CloneFunction.cpp

if (!isa<PHINode>(NewInst)) {
       RemapInstruction(NewInst, VMap,
                        ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges);
 
       // If we can simplify this instruction to some other value, simply add
       // a mapping to that value rather than inserting a new instruction into
       // the basic block.
       if (Value *V =
               SimplifyInstruction(NewInst, BB->getModule()->getDataLayout())) {
-        // On the off-chance that this simplifies to an instruction in the old
-        // function, map it back into the new function.
-        if (Value *MappedV = VMap.lookup(V))
-          V = MappedV;
+        assert((dyn_cast<Instruction>(V) == nullptr ||
+                dyn_cast<Instruction>(V)->getParent() == nullptr ||
+                dyn_cast<Instruction>(V)->getFunction() != OldFunc ||
+                OldFunc == NewFunc) &&
+               "Simplified Instruction should not be in the old function.");
 
         if (!NewInst->mayHaveSideEffects()) {
           VMap[&*II] = V;
           NewInst->deleteValue();
           continue;
         }
       }
     }
#endif
   }
   
   // Loop over all of the basic blocks in the old function.  If the block was
   // reachable, we have cloned it and the old block is now in the value map:
   // insert it into the new function in the right order.  If not, ignore it.
   //
   // Defer PHI resolution until rest of function is resolved.
   SmallVector<const PHINode*, 16> PHIToResolve;
-  for (const BasicBlock &BI : *OldFunc) {
+  for (const BasicBlock &BI : make_range(OldFunc->begin(), OldFunc->end())) {
     Value *V = VMap.lookup(&BI);
     BasicBlock *NewBB = cast_or_null<BasicBlock>(V);
     if (!NewBB) continue;  // Dead block.
 
     // Add the new block to the new function.
     NewFunc->getBasicBlockList().push_back(NewBB);
 
     // Handle PHI nodes specially, as we have to remove references to dead
     // blocks.
     for (BasicBlock::const_iterator I = BI.begin(), E = BI.end(); I != E; ++I) {
       // PHI nodes may have been remapped to non-PHI nodes by the caller or
       // during the cloning process.
       if (const PHINode *PN = dyn_cast<PHINode>(I)) {
         if (isa<PHINode>(VMap[PN]))