[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

3351

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

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

3354

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

test/Transforms/SimplifyCFG/bug-25299.ll

2

No FileCheck?

[• chenli]

lib/Transforms/Utils/SimplifyCFG.cpp

3351

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

3354

Will do.

test/Transforms/SimplifyCFG/bug-25299.ll

2

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

3335

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.

3351

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

3335

Will do.

3351

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

3243–3244

Stale comment.

3248

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

3313

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

3319

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

3319

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

class SimplifyCFGOpt {
   bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
                                                      BasicBlock *Pred,
                                                      IRBuilder<> &Builder);
   bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
                                            IRBuilder<> &Builder);
 
   bool SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder);
   bool SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder);
+  bool SimplifySingleResume(ResumeInst *RI);
+  bool SimplifyCommonResume(ResumeInst *RI);
   bool SimplifyCleanupReturn(CleanupReturnInst *RI);
   bool SimplifyUnreachable(UnreachableInst *UI);
   bool SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder);
   bool SimplifyIndirectBr(IndirectBrInst *IBI);
   bool SimplifyUncondBranch(BranchInst *BI, IRBuilder <> &Builder);
   bool SimplifyCondBranch(BranchInst *BI, IRBuilder <>&Builder);
 
 public:
static bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond,
 
   EraseTerminatorInstAndDCECond(OldTerm);
   return true;
 }
 
 // Replaces
 //   (switch (select cond, X, Y)) on constant X, Y
 // with a branch - conditional if X and Y lead to distinct BBs,
 // unconditional otherwise.
 static bool SimplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select) {
   // Check for constant integer values in the select.
   ConstantInt *TrueVal = dyn_cast<ConstantInt>(Select->getTrueValue());
   ConstantInt *FalseVal = dyn_cast<ConstantInt>(Select->getFalseValue());
   if (!TrueVal || !FalseVal)
     return false;
 
   // Find the relevant condition and destinations.
if (HasWeights) {
     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
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.
+  if (isa<PHINode>(RI->getValue()))
+    return SimplifyCommonResume(RI);
+  else if (isa<LandingPadInst>(RI->getParent()->getFirstNonPHI()) &&
+           RI->getValue() == RI->getParent()->getFirstNonPHI())
+    // The resume must unwind the exception that caused control to branch here.
+    return SimplifySingleResume(RI);
+}
+
+// Simplify resume that is shared by several landing pads (phi of landing pad).
+bool SimplifyCFGOpt::SimplifyCommonResume(ResumeInst *RI) {
   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.
+
+  // Check that there are no other instructions except for debug intrinsics
+  // between the phi of landing pads (RI->getValue()) and resume instruction.
+  BasicBlock::iterator I = cast<Instruction>(RI->getValue())->getIterator(),
+                   E = RI->getIterator();
+  while (++I != E)
+    if (!isa<DbgInfoIntrinsic>(I))
       return false;
 
+  SmallSet<BasicBlock *, 4> TrivialUnwindBlocks;
+  auto *PhiLPInst = cast<PHINode>(RI->getValue());
+
+  // Check incoming blocks to see if any of them are trivial.
+  for (unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues();
+       Idx != End; Idx++) {
+    auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
+    auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
+
+    // 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()->getIterator();
+    E = IncomingBB->getTerminator()->getIterator();
+    while (++I != E)
+      if (!isa<DbgInfoIntrinsic>(I)) {
+        isTrivial = false;
+        break;
+      }
+
+    if (isTrivial)
+      TrivialUnwindBlocks.insert(IncomingBB);
+  }
+
+  // If no trivial unwind blocks, don't do any simplifications.
+  if (TrivialUnwindBlocks.empty()) return false;
+
+  // Turn all invokes that unwind here into calls.
+  for (auto *TrivialBB : TrivialUnwindBlocks) {
+    // Blocks that will be simplified should 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->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);
+    }
+
+    // In each SimplifyCFG run, only the current processed block can be erased.
+    // Otherwise, it will break the iteration of SimplifyCFG pass. So instead
+    // of erasing TrivialBB, we only remove the branch to the common resume
+    // block so that we can later erase the resume block since it has no
+    // predecessors.
+    TrivialBB->getTerminator()->eraseFromParent();
+    new UnreachableInst(RI->getContext(), TrivialBB);
+  }
+
+  // Delete the resume block if all its predecessors have been removed.
+  if (pred_empty(BB))
+    BB->eraseFromParent();
+
+  return !TrivialUnwindBlocks.empty();
+}
+
+// Simplify resume that is only used by a single (non-phi) landing pad.
+bool SimplifyCFGOpt::SimplifySingleResume(ResumeInst *RI) {
+  BasicBlock *BB = RI->getParent();
+  LandingPadInst *LPInst = dyn_cast<LandingPadInst>(BB->getFirstNonPHI());
+  assert (RI->getValue() == LPInst &&
+          "Resume must unwind the exception that caused control to here");
+
   // Check that there are no other instructions except for debug intrinsics.
   BasicBlock::iterator I = LPInst->getIterator(), E = RI->getIterator();
   while (++I != E)
     if (!isa<DbgInfoIntrinsic>(I))
       return false;
 
   // 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;) {
     BasicBlock *Pred = *PI++;
     removeUnwindEdge(Pred);
   }
 
   // The landingpad is now unreachable.  Zap it.
   BB->eraseFromParent();
   return true;
 }
 
 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
   // updated to continue to the unwind destination of the cleanup pad being

test/Transforms/SimplifyCFG/bug-25299.ll

+; RUN: opt < %s -simplifycfg -S | FileCheck %s
+
+;; 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:
+;CHECK: entry
+;CHECK-NEXT: call void @g()
+  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 ]
+;CHECK-NOT: resume { i8*, i32 } %tmp104
+  resume { i8*, i32 } %tmp104
+
+continue:                                         ; preds = %entry, %continue
+;CHECK: continue:                                         ; preds = %entry, %continue
+;CHECK-NEXT: call void @g()
+  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 @test3(i1 %cond) personality i32 (...)* @__gxx_personality_v0 {
+entry:
+; CHECK-LABEL: @test3(
+; 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 
+
+rethrow:
+  %lp = phi { i8*, i32 } [%0, %lpad1], [%1, %lpad2]
+  resume { i8*, i32 } %lp
+  
+lpad2:
+  %1 = landingpad { i8*, i32 }
+          cleanup
+  br label %rethrow
+}
+
 declare i32 @__gxx_personality_v0(...)