[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

2926

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.

2932

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.

2937

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

2951

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

2930

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

2959

Blocks that will be deleted...

2961

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

2966–2967

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

2968

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

[• chenli]

lib/Transforms/Utils/SimplifyCFG.cpp

2968

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

2957–2964

use auto * here.

2968

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

1 ↗

(On Diff #38476)

Why does this test also need the -gvn pass?

[• chenli]

test/Transforms/SimplifyCFG/bug-25299.ll

1 ↗

(On Diff #38476)

-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, E = RI;
+  // 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;
+  if (RI->getValue() == LPInst) {
+    // Landing pad is in current block, which has already been checked.
+    TrivialUnwindBlocks.push_back(BB);
+  } else {
+    // Check all incoming blocks to see if they are trivial.
+    auto *PhiLPInst = cast<PHINode>(RI->getValue());
+    for (unsigned i = 0; i < PhiLPInst->getNumIncomingValues(); i++) {
+      auto *IncomingBB = PhiLPInst->getIncomingBlock(i);
+      auto *IncomingLP = PhiLPInst->getIncomingValue(i);
+
+      // Not the landing pad that caused the control to branch here.
+      if (IncomingLP != IncomingBB->getFirstNonPHI())
+        continue;
+
+      // Assume the block is trivial. Invalidate if we prove it's not later.
+      TrivialUnwindBlocks.push_back(IncomingBB);
+
+      I = IncomingBB->getFirstNonPHI();
+      E = IncomingBB->getTerminator();
+      while (++I != E)
+        if (!isa<DbgInfoIntrinsic>(I)) {
+          // If it turns out not trivial, remove it
+          // from the list.
+          TrivialUnwindBlocks.pop_back();
+          break;
+        }
+    }
+    // Blocks those would be deleted should also be removed
+    // from the phi node.
+    for (auto IncomingBB : TrivialUnwindBlocks) {
+      PhiLPInst->removeIncomingValue(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) {
+    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.
-  BB->eraseFromParent();
-  return true;
+    TrivialBB->eraseFromParent();
+  }
+
+  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
   // simplified does not continue to the caller, each predecessor will be

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(...)