[UnifyFunctionExitNodes] Fix Modified status for unreachable blocks

[dstenb]

Summary

If a function had at most one return block, the pass would return false
regardless if an unified unreachable block was created.

This patch fixes that by refactoring runOnFunction into two separate
helper functions for handling the unreachable blocks respectively the
return blocks, as suggested by @bjope in a review comment.

This was caught using the check introduced by D80916.

[dstenb]

Gentle ping. I was not sure which reviews to add to this one, since the code has mostly remained unchanged since its original introduction in 2004, except for it being affected by wider changes.

[bjope]

llvm/lib/Transforms/Utils/UnifyFunctionExitNodes.cpp

42–43

Slightly unrelated, but this looks wrong.

I assume it is describing what this function is returning (not what the singular exit node for the function being compiled is returning). But either way it is incorrect.

As this is an ordinary runOnFunction method I don't think it need to say anything special about what it returns (or it should say whatever other runOnFunction methods are saying).

43

One idea (a bit larger refactoring) is to split this function by adding two new helpers, so the code in runOnFunction would look like:

{
  bool Changed = false;
  Changed |= unifyUnreachableBlocks();
  Changed |= unifyReturnBlocks();
  return Changed;
}

That would be nice since there doesn't seem to really be any dependency between the handling of unreachable and return blocks. And you wouldn't need to care about Changed status from one analysis inside the other.

[dstenb]

Address review comments.

[dstenb]

llvm/lib/Transforms/Utils/UnifyFunctionExitNodes.cpp

43

That seems worthwhile! I did that in the latest diff.

[bjope]

llvm/lib/Transforms/Utils/UnifyFunctionExitNodes.cpp

104

Assuming intention was to do return Changed; here.

llvm/test/Transforms/UnifyFunctionExitNodes/unreachable-blocks-status.ll

4

I guess one would have neeed to enable EXPENSIVE_CHECKS for this test case to fail in the past (but only since the check was addded to EXPENSIVE_CHECKS). Could it be worth the trouble to use -debug-pass=Details and check that the pass returns that it has modified both @foo and @bar? In some sense getting rid of the dependency to EXPENSIVE_CHECKS.

On the other hand, I'm not sure if -debug-pass=Details works with new-pm. But mergereturn has not been ported to the new-pm either, so I'm not sure about the future plans for the pass. Maybe we shouldn't spend too much time here. So I'm happy either way.

[serge-sans-paille]

LGTM

llvm/test/Transforms/UnifyFunctionExitNodes/unreachable-blocks-status.ll

4

I think the test is fine as is, if it was triggering the error before that patch under EXPENSIVE_CHECKS

[dstenb]

llvm/lib/Transforms/Utils/UnifyFunctionExitNodes.cpp

104

Yes, thanks! I'll fix it when landing.

llvm/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h

 #define LLVM_TRANSFORMS_UTILS_UNIFYFUNCTIONEXITNODES_H
 
 #include "llvm/Pass.h"
 
 namespace llvm {
 
 class BasicBlock;
 
-struct UnifyFunctionExitNodes : public FunctionPass {
+class UnifyFunctionExitNodes : public FunctionPass {
+  bool unifyUnreachableBlocks(Function &F);
+  bool unifyReturnBlocks(Function &F);
+
 public:
   static char ID; // Pass identification, replacement for typeid
   UnifyFunctionExitNodes();
 
   // We can preserve non-critical-edgeness when we unify function exit nodes
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   bool runOnFunction(Function &F) override;
 };
 
 Pass *createUnifyFunctionExitNodesPass();
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_UNIFYFUNCTIONEXITNODES_H

llvm/lib/Transforms/Utils/UnifyFunctionExitNodes.cpp

 }
 
 void UnifyFunctionExitNodes::getAnalysisUsage(AnalysisUsage &AU) const{
   // We preserve the non-critical-edgeness property
   AU.addPreservedID(BreakCriticalEdgesID);
   // This is a cluster of orthogonal Transforms
   AU.addPreservedID(LowerSwitchID);
 }
 
-// UnifyAllExitNodes - Unify all exit nodes of the CFG by creating a new
-// BasicBlock, and converting all returns to unconditional branches to this
-// new basic block.  The singular exit node is returned.
-//
-// If there are no return stmts in the Function, a null pointer is returned.
-//
-bool UnifyFunctionExitNodes::runOnFunction(Function &F) {
-  // Loop over all of the blocks in a function, tracking all of the blocks that
-  // return.
-  //
-  std::vector<BasicBlock*> ReturningBlocks;
+bool UnifyFunctionExitNodes::unifyUnreachableBlocks(Function &F) {
   std::vector<BasicBlock*> UnreachableBlocks;
+
   for (BasicBlock &I : F)
-    if (isa<ReturnInst>(I.getTerminator()))
-      ReturningBlocks.push_back(&I);
-    else if (isa<UnreachableInst>(I.getTerminator()))
+    if (isa<UnreachableInst>(I.getTerminator()))
       UnreachableBlocks.push_back(&I);
 
-  // Then unreachable blocks.
-  if (UnreachableBlocks.size() > 1) {
-    BasicBlock *UnreachableBlock = BasicBlock::Create(F.getContext(),
-                                          "UnifiedUnreachableBlock", &F);
-    new UnreachableInst(F.getContext(), UnreachableBlock);
+  if (UnreachableBlocks.size() <= 1)
+    return false;
+
+  BasicBlock *UnreachableBlock =
+      BasicBlock::Create(F.getContext(), "UnifiedUnreachableBlock", &F);
 
-    for (BasicBlock *BB : UnreachableBlocks) {
-      BB->getInstList().pop_back();  // Remove the unreachable inst.
-      BranchInst::Create(UnreachableBlock, BB);
-    }
-  }
+    BB->getInstList().pop_back(); // Remove the unreachable inst.
+
+  return true;
 
-  // There is nothing more to do if we do not have multiple return blocks.
+bool UnifyFunctionExitNodes::unifyReturnBlocks(Function &F) {
+  std::vector<BasicBlock *> ReturningBlocks;
+
+  for (BasicBlock &I : F)
+    if (isa<ReturnInst>(I.getTerminator()))
+      ReturningBlocks.push_back(&I);
+
   if (ReturningBlocks.size() <= 1)
     return false;
 
-  // Otherwise, we need to insert a new basic block into the function, add a PHI
-  // nodes (if the function returns values), and convert all of the return
-  // instructions into unconditional branches.
-  //
+  // Insert a new basic block into the function, add PHI nodes (if the function
+  // returns values), and convert all of the return instructions into
+  // unconditional branches.
   BasicBlock *NewRetBlock = BasicBlock::Create(F.getContext(),
                                                "UnifiedReturnBlock", &F);
 
   PHINode *PN = nullptr;
   if (F.getReturnType()->isVoidTy()) {
     ReturnInst::Create(F.getContext(), nullptr, NewRetBlock);
   } else {
     // If the function doesn't return void... add a PHI node to the block...
     PN = PHINode::Create(F.getReturnType(), ReturningBlocks.size(),
                          "UnifiedRetVal");
     NewRetBlock->getInstList().push_back(PN);
     ReturnInst::Create(F.getContext(), PN, NewRetBlock);
   }
 
   // Loop over all of the blocks, replacing the return instruction with an
   // unconditional branch.
-  //
   for (BasicBlock *BB : ReturningBlocks) {
     // Add an incoming element to the PHI node for every return instruction that
     // is merging into this new block...
     if (PN)
       PN->addIncoming(BB->getTerminator()->getOperand(0), BB);
 
     BB->getInstList().pop_back();  // Remove the return insn
     BranchInst::Create(NewRetBlock, BB);
   }
+
   return true;
 }
+
+// Unify all exit nodes of the CFG by creating a new BasicBlock, and converting
+// all returns to unconditional branches to this new basic block. Also, unify
+// all unreachable blocks.
+bool UnifyFunctionExitNodes::runOnFunction(Function &F) {
+  bool Changed = false;
+  Changed |= unifyUnreachableBlocks(F);
+  Changed |= unifyReturnBlocks(F);
+  return Changed;
+}

llvm/test/Transforms/UnifyFunctionExitNodes/unreachable-blocks-status.ll

+; RUN: opt -mergereturn -S < %s | FileCheck %s
+
+; The pass did previously not report the correct Modified status in the case
+; where a function had at most one return block, and an unified unreachable
+; block was created. This was caught by the pass return status check that is
+; hidden under EXPENSIVE_CHECKS.
+
+; CHECK: for.foo.body2:
+; CHECK-NEXT: br label %UnifiedUnreachableBlock
+
+; CHECK: for.foo.end:
+; CHECK-NEXT: br label %UnifiedUnreachableBlock
+
+; CHECK: UnifiedUnreachableBlock:
+; CHECK-NEXT: unreachable
+
+define i32 @foo() {
+entry:
+  br label %for.foo.cond
+
+for.foo.cond:                                         ; preds = %entry
+  br i1 false, label %for.foo.body, label %for.foo.end3
+
+for.foo.body:                                         ; preds = %for.foo.cond
+  br label %for.foo.cond1
+
+for.foo.cond1:                                        ; preds = %for.foo.body
+  br i1 false, label %for.foo.body2, label %for.foo.end
+
+for.foo.body2:                                        ; preds = %for.foo.cond1
+  unreachable
+
+for.foo.end:                                          ; preds = %for.foo.cond1
+  unreachable
+
+for.foo.end3:                                         ; preds = %for.foo.cond
+  ret i32 undef
+}
+
+; CHECK: for.bar.body2:
+; CHECK-NEXT: br label %UnifiedUnreachableBlock
+
+; CHECK: for.bar.end:
+; CHECK-NEXT: br label %UnifiedUnreachableBlock
+
+; CHECK: UnifiedUnreachableBlock:
+; CHECK-NEXT: unreachable
+
+define void @bar() {
+entry:
+  br label %for.bar.cond
+
+for.bar.cond:                                         ; preds = %entry
+  br i1 false, label %for.bar.body, label %for.bar.end
+
+for.bar.body:                                         ; preds = %for.bar.cond
+  br label %for.bar.cond1
+
+for.bar.cond1:                                        ; preds = %for.bar.body
+  br i1 false, label %for.bar.body2, label %for.bar.end
+
+for.bar.body2:                                        ; preds = %for.bar.cond1
+  unreachable
+
+for.bar.end:                                          ; preds = %for.bar.cond1
+  unreachable
+}