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

[• chenli]

Summary

Currently SimplifyResume can convert an invoke instruction to a call instruction if its landing pad is trivial. In practice we could have several invoke instructions with trivial landing pads and share a common rethrow block, and in the common rethrow block, all the landing pads join to a phi node. The patch extends SimplifyResume to check the phi of landing pad and their incoming blocks. If any of them is trivial, remove it from the phi node and convert the invoke instruction to a call instruction.

[reames]

The general transform looks reasonable, but I'd suggest possibly tackling this a slightly different way. Rather than explicitly doing the detection of a trivial block and rewrite in a single step, replace the branch to the unified resume with a resume and then let the existing code handle it. Doing it this way could make the change less invasive and easier to reason about. Note that this is a suggestion to think about, not a requirement. If you feel the current approach is easier/better, we can run with this after cleanup.

lib/Transforms/Utils/SimplifyCFG.cpp

2928

This comment is slightly confusing. I thought at first *all* incoming blocks had to be trivial. Wording change to indicate checking for *any* trivial block would be good.

2934

You're not actually checking the input is a landing pad with this check. It could be another PHI. Use a dyn_cast, continue pattern.

2939

Why? Just push the add below the loop. Either use a lambda or a IsOkay condition flag to dedect which case you're in.

2953

Please move this into the loop below.

[• chenli]

In D13718#267109, @reames wrote:

The general transform looks reasonable, but I'd suggest possibly tackling this a slightly different way. Rather than explicitly doing the detection of a trivial block and rewrite in a single step, replace the branch to the unified resume with a resume and then let the existing code handle it. Doing it this way could make the change less invasive and easier to reason about. Note that this is a suggestion to think about, not a requirement. If you feel the current approach is easier/better, we can run with this after cleanup.

I was sort of thinking about a similar approach as you pointed, which was tail duplicating the common resume block to all its predecessors. I worried that if SimplifyResume could not simply all the predecessors, it might not be able to merge them back to a common resume block and would cause code size increment.

[reames]

In D13718#267123, @chenli wrote:

I was sort of thinking about a similar approach as you pointed, which was tail duplicating the common resume block to all its predecessors. I worried that if SimplifyResume could not simply all the predecessors, it might not be able to merge them back to a common resume block and would cause code size increment.

I wouldn't want to blindly tail duplicate the resume. Doing so for a particular scenario (landing pad to resume contains only debug intrinsics) is reasonable, but we definitely want to be able to common suffixes into a shared rethrow and the easiest way to do that is to have a common resume at the end. In other words, we need to establish profitability before doing the transform.

Thinking about it further, I think my suggestion is just a bad idea. Go with the approach you had, let's just cleanup the code to make it clear what's happening.

[• chenli]

Update patch w.r.t Philip's comments

[reames]

lib/Transforms/Utils/SimplifyCFG.cpp

2932

Call this IncomingValue since it's not necessarily a landing pad yet.

2958

Blocks that will be deleted...

2960

Using BasicBlock::removePredecessor is the idiomatic way to do this.

2979–2980

I think that if you're not careful here, you mind end up with a block with a zero entry PHI and no predecessors. You should probably delete that one too.

[• chenli]

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

[reames]

lib/Transforms/Utils/SimplifyCFG.cpp

2981

BB->getParent should always be set? Is this defensive programming (remove it), or a bug (add test case)?

[• chenli]

lib/Transforms/Utils/SimplifyCFG.cpp

2981

We could have already erased BB if it is in TrivialUnwindBlocks. In that case BB becomes a dangling pointer. My code here isn't actually safe though. I should reset BB to nullptr on line 2967 if TrivialBB equals to BB. I will change it.

[• chenli]

Update patch.

[reames]

LGTM w/minor comment addressed.

lib/Transforms/Utils/SimplifyCFG.cpp

2956–2977

use auto * here.

2981

A comment correction is in other. Possibly: have been deleted, and we haven't already deleted it above when deleting the landing pad blocks.

[• chenli]

Update the patch so it does not crash bug 25299.

[majnemer]

test/Transforms/SimplifyCFG/bug-25299.ll

2

Why does this test also need the -gvn pass?

[• chenli]

test/Transforms/SimplifyCFG/bug-25299.ll

2

-gvn is not needed here. I forgot to remove it while testing locally. I will update it now, and thanks for spotting that.

[• chenli]

Correct test command line options.

lib/Transforms/Utils/SimplifyCFG.cpp

static bool SimplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder,
   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;
 
+  SmallVector<BasicBlock *, 4> TrivialUnwindBlocks;
+  auto *PhiLPInst = dyn_cast<PHINode>(RI->getValue());
+  if (!PhiLPInst) {
+    // Landing pad is in current block, which has already been checked.
+    TrivialUnwindBlocks.push_back(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);
+
+      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.push_back(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) {
+    // If the block is not the resume block and it has other successors, we
+    // can not delete it because it has other dependents.
+    if (!PhiLPInst || TrivialBB->getUniqueSuccessor() == BB) {
+      // 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.size() != 0;
 }
 
 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(...)