[SimplifyCFG] Extend SimplifyResume to handle phi of trivial landing pad.

[• chenli]

Summary

This is a fix of D13718. D13718 was committed but then reverted because of the following bug:
https://llvm.org/bugs/show_bug.cgi?id=25299

This patch fixes the issue shown in the bug.

[reames]

lib/Transforms/Utils/SimplifyCFG.cpp

2959

This is at the wrong point. We should be checking that the terminator is a unconditional branch before considering the basic block trivial.

[majnemer]

lib/Transforms/Utils/SimplifyCFG.cpp

2986

!TrivialUnwindBlocks.empty()

[• chenli]

Update w.r.t Philip's and David's comments.

[majnemer]

lib/Transforms/Utils/SimplifyCFG.cpp

3242

Please do not evaluate getNumIncomingValues each time through the loop, consider writing this like:

for (unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End; ++Idx) {

3295

Isn't this BB && pred_empty(BB) ? Also, the braces are superfluous.

test/Transforms/SimplifyCFG/bug-25299.ll

1

No FileCheck?

[• chenli]

lib/Transforms/Utils/SimplifyCFG.cpp

3242

Will do. But I think the compiler should be able to optimize this.

3295

Will do.

test/Transforms/SimplifyCFG/bug-25299.ll

1

The only purpose of this test is to verify there's no crash. The other test should be able to catch miscompiles. But I can definitely add FileCheck if it's useful in general.

[• chenli]

First, fix the issues mentioned by David.

Second, the previous patch turned out to have a bug by running some of my own local tests. The patch tried to erase all unreachable landing pad blocks, but this invalidated the iteration of SimplifyCFG pass.

if (SimplifyCFG(&*BBIt++, TTI, BonusInstThreshold, AC)) {
  LocalChange = true;
  ++NumSimpl;
}

The next block has been iterated before processing the current block (in this case it is the resume block). If the next block turns out to be an unreachable landing pad block deleted by processing the resume block, the iteration will be broken. Therefore, we can only erase the current block in SimplifyCFG.

The updated patch fixes this problem, and modify the test’s block layout to catch this bug if it happens.

[reames]

lib/Transforms/Utils/SimplifyCFG.cpp

3221

Given how divergent the two cases have gotten, I think we should split the two cases. The code duplication is relatively minor compared to the simplification of the complexity.

3277

I think this can be more clearly written as:
if (PhiLPInst)

while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
    BB->removePredecessor(TrivialBB, false);

Right?

[• chenli]

lib/Transforms/Utils/SimplifyCFG.cpp

3221

Will do.

3277

Yes, but this won't exist after we separate the two cases :)

[• chenli]

Update patch w.r.t Philip's suggestions.

[• chenli]

ping...

[reames]

All of my comments this time around are minor. I think we can probably get this in after one last round of cleanup.

p.s. Sorry for the prolonged period without response.

lib/Transforms/Utils/SimplifyCFG.cpp

3216

Stale comment.

3221

Naming wise, unique isn't quite right. You could have a phi early in the value chain with a modification of it being resumed. I think it would make a lot more sense to lift the check for landing pad here to form an else if...

3286

minor wording: "if it has no", to "since it has no"

3292

Hm, what about an empty phi in an unreachable block? I think you're probably guarded from getting here, but adding an assert to make that clear would be good.

[• chenli]

lib/Transforms/Utils/SimplifyCFG.cpp

3292

I didn't quite get this. If the resume block has no predecessor and become unreachable, it should contains an empty phi. Do you mean I should assert the empty phi is there?

[• chenli]

Update patch w.r.t. Philip's comments.

[reames]

LGTM

lib/Transforms/Utils/SimplifyCFG.cpp

if (Weights.size() == 1 + SI->getNumCases()) {
       TrueWeight = (uint32_t)Weights[SI->findCaseValue(TrueVal).
                                      getSuccessorIndex()];
       FalseWeight = (uint32_t)Weights[SI->findCaseValue(FalseVal).
                                       getSuccessorIndex()];
     }
   }
 
   // Perform the actual simplification.
   return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB,
                                     TrueWeight, FalseWeight);
 }
 
 // Replaces
 //   (indirectbr (select cond, blockaddress(@fn, BlockA),
 //                             blockaddress(@fn, BlockB)))
 // with
 //   (br cond, BlockA, BlockB).
static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) {
 
   // Perform the actual simplification.
   return SimplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB,
                                     0, 0);
 }
 
 /// This is called when we find an icmp instruction
 /// (a seteq/setne with a constant) as the only instruction in a
 /// block that ends with an uncond branch.  We are looking for a very specific
 /// pattern that occurs when "A == 1 || A == 2 || A == 3" gets simplified.  In
 /// this case, we merge the first two "or's of icmp" into a switch, but then the
 /// default value goes to an uncond block with a seteq in it, we get something
 /// like:
 ///
 ///   switch i8 %A, label %DEFAULT [ i8 1, label %end    i8 2, label %end ]
 /// DEFAULT:
 ///   %tmp = icmp eq i8 %A, 92
static bool SimplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder,
   // Erase the old branch instruction.
   EraseTerminatorInstAndDCECond(BI);
 
   DEBUG(dbgs() << "  ** 'icmp' chain result is:\n" << *BB << '\n');
   return true;
 }
 
 bool SimplifyCFGOpt::SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder) {
   // If this is a trivial landing pad that just continues unwinding the caught
   // exception then zap the landing pad, turning its invokes into calls.
   BasicBlock *BB = RI->getParent();
   LandingPadInst *LPInst = dyn_cast<LandingPadInst>(BB->getFirstNonPHI());
-  if (RI->getValue() != LPInst)
-    // Not a landing pad, or the resume is not unwinding the exception that
-    // caused control to branch here.
+
+  // If RI->getValue() is a landing pad, check if the first instruction is
+  // the same landing pad that caused control to branch here. If RI->getValue
+  // is a phi of landing pad, check its predecessor blocks to see if any of
+  // them contains a trivial landing pad.
+  if (RI->getValue() != LPInst && !isa<PHINode>(RI->getValue()))
     return false;
 
-  // Check that there are no other instructions except for debug intrinsics.
-  BasicBlock::iterator I = LPInst->getIterator(), E = RI->getIterator();
+  // Check that there are no other instructions except for debug intrinsics
+  // between the landing pad (or phi of landing pad) and resume instruction.
+  BasicBlock::iterator I = cast<Instruction>(RI->getValue()), E = RI;
   while (++I != E)
     if (!isa<DbgInfoIntrinsic>(I))
       return false;
 
+  SmallSet<BasicBlock *, 4> TrivialUnwindBlocks;
+  auto *PhiLPInst = dyn_cast<PHINode>(RI->getValue());
+  if (!PhiLPInst) {
+    // Landing pad is in current block, which has already been checked.
+    TrivialUnwindBlocks.insert(BB);
+  } else {
+    // Check incoming blocks to see if any of them are trivial.
+    for (unsigned i = 0; i < PhiLPInst->getNumIncomingValues(); i++) {
+      auto *IncomingBB = PhiLPInst->getIncomingBlock(i);
+      auto *IncomingValue = PhiLPInst->getIncomingValue(i);
+
+      // If the block has other successors, we can not delete it because
+      // it has other dependents.
+      if (IncomingBB->getUniqueSuccessor() != BB)
+        continue;
+
+      auto *LandingPad =
+          dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI());
+      // Not the landing pad that caused the control to branch here.
+      if (IncomingValue != LandingPad)
+        continue;
+
+      bool isTrivial = true;
+
+      I = IncomingBB->getFirstNonPHI();
+      E = IncomingBB->getTerminator();
+      while (++I != E)
+        if (!isa<DbgInfoIntrinsic>(I)) {
+          isTrivial = false;
+          break;
+        }
+
+      if (isTrivial)
+        TrivialUnwindBlocks.insert(IncomingBB);
+    }
+  }
+
   // Turn all invokes that unwind here into calls and delete the basic block.
-  for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) {
+  for (auto *TrivialBB : TrivialUnwindBlocks) {
+    // Blocks that will be deleted should also be removed from the phi node.
+    // Note there could be multiple edges to the resume block, and we need
+    // to remove them all.
+    while (PhiLPInst && PhiLPInst->getBasicBlockIndex(TrivialBB) != -1) {
+      BB->removePredecessor(TrivialBB, true);
+    }
+
+    for (pred_iterator PI = pred_begin(TrivialBB), PE = pred_end(TrivialBB);
+         PI != PE;) {
       BasicBlock *Pred = *PI++;
       removeUnwindEdge(Pred);
     }
 
     // The landingpad is now unreachable.  Zap it.
+    if (TrivialBB == BB)
+      BB = nullptr;
+    TrivialBB->eraseFromParent();
+  }
+
+  // Delete the resume block if all its predecessors have been deleted, and we
+  // haven't already deleted it above when deleting the landing pad blocks.
+  if (BB && pred_begin(BB) == pred_end(BB)) {
     BB->eraseFromParent();
-  return true;
+  }
+
+  return !TrivialUnwindBlocks.empty();
 }
 
 bool SimplifyCFGOpt::SimplifyCleanupReturn(CleanupReturnInst *RI) {
   // If this is a trivial cleanup pad that executes no instructions, it can be
   // eliminated.  If the cleanup pad continues to the caller, any predecessor
   // that is an EH pad will be updated to continue to the caller and any
   // predecessor that terminates with an invoke instruction will have its invoke
   // instruction converted to a call instruction.  If the cleanup pad being

test/Transforms/SimplifyCFG/bug-25299.ll

+; RUN: opt < %s -simplifycfg -disable-output
+
+;; Test case for bug 25299, contributed by David Majnemer.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @f(i1 %B) personality i1 undef {
+entry:
+  invoke void @g()
+          to label %continue unwind label %unwind
+
+unwind:                                           ; preds = %entry
+  %tmp101 = landingpad { i8*, i32 }
+          cleanup
+  br i1 %B, label %resume, label %then
+
+then:                                             ; preds = %cleanup1
+  br label %resume
+
+resume:                                           ; preds = %cleanup2, %then, %cleanup1, %unwind
+  %tmp104 = phi { i8*, i32 } [ %tmp101, %then ], [ %tmp106, %cleanup2 ], [ %tmp101, %unwind ]
+  resume { i8*, i32 } %tmp104
+
+continue:                                         ; preds = %entry, %continue
+  invoke void @g()
+          to label %continue unwind label %cleanup2
+
+cleanup2:                                         ; preds = %continue
+  %tmp106 = landingpad { i8*, i32 }
+          cleanup
+  br label %resume
+}
+
+declare void @g()
 No newline at end of file

test/Transforms/SimplifyCFG/invoke_unwind.ll

; CHECK-NEXT: ret i32 0
                         to label %1 unwind label %Rethrow
         ret i32 0
 Rethrow:
         %exn = landingpad {i8*, i32}
                  catch i8* null
         resume { i8*, i32 } %exn
 }
 
+declare i64 @dummy1()
+declare i64 @dummy2()
+
+; This testcase checks to see if simplifycfg pass can convert two invoke 
+; instructions to call instructions if they share a common trivial unwind
+; block.
+define i64 @test2(i1 %cond) personality i32 (...)* @__gxx_personality_v0 {
+entry:
+; CHECK-LABEL: @test2(
+; CHECK: %call1 = call i64 @dummy1()
+; CHECK: %call2 = call i64 @dummy2()
+; CHECK-NOT: resume { i8*, i32 } %lp
+  br i1 %cond, label %br1, label %br2
+
+br1:
+  %call1 = invoke i64 @dummy1()
+          to label %invoke.cont unwind label %lpad1
+          
+br2: 
+  %call2 = invoke i64 @dummy2()
+          to label %invoke.cont unwind label %lpad2
+          
+invoke.cont:
+  %c = phi i64 [%call1, %br1], [%call2, %br2]
+  ret i64 %c 
+  
+  
+lpad1:
+  %0 = landingpad { i8*, i32 }
+          cleanup
+  br label %rethrow 
+
+lpad2:
+  %1 = landingpad { i8*, i32 }
+          cleanup
+  br label %rethrow
+
+rethrow:
+  %lp = phi { i8*, i32 } [%0, %lpad1], [%1, %lpad2]
+  resume { i8*, i32 } %lp
+}
+
 declare i32 @__gxx_personality_v0(...)