If a conditional branch jumps to the same target, remove the condition

[reames]

Summary

Given much of inst combine is restricted to instructions which have one use, getting rid of a use on the condition can help the effectiveness of the optimizer. Also, it allows the condition to potentially be deleted by instcombine rather than waiting for another pass.

I noticed this completely by accident in another test case. It's not anything that actually came from a real workload.

p.s. We should probably do the same thing for switch instructions.

[hfinkel]

LGTM. But, could you also please fix llvm::ConstantFoldTerminator in lib/Transforms/Utils/Local.cpp so that it handles the undef condition and transforms the branch with the undef condition into an unconditional branch. If we don't want to do that, then we should just pick true/false here instead of using undef.

[reames]

@Hal - Unless I'm missing something, this is already handled in
ConstantFoldTerminator.

if (Dest2 == Dest1) {       // Conditional branch to same location?
  // This branch matches something like this:
  //     br bool %cond, label %Dest, label %Dest
  // and changes it into:  br label %Dest

  // Let the basic block know that we are letting go of one copy of it.
  assert(BI->getParent() && "Terminator not inserted in block!");
  Dest1->removePredecessor(BI->getParent());

  // Replace the conditional branch with an unconditional one.
  Builder.CreateBr(Dest1);
  Value *Cond = BI->getCondition();
  BI->eraseFromParent();
  if (DeleteDeadConditions)
    RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
  return true;
}

Given this, I plan to submit as is.

llvm/trunk/lib/Transforms/InstCombine/InstructionCombining.cpp

Instruction *InstCombiner::visitBranchInst(BranchInst &BI) {
   if (match(&BI, m_Br(m_Not(m_Value(X)), TrueDest, FalseDest)) &&
       !isa<Constant>(X)) {
     // Swap Destinations and condition...
     BI.setCondition(X);
     BI.swapSuccessors();
     return &BI;
   }
 
+  // If the condition is irrelevant, remove the use so that other
+  // transforms on the condition become more effective.
+  if (BI.isConditional() &&
+      BI.getSuccessor(0) == BI.getSuccessor(1) &&
+      !isa<UndefValue>(BI.getCondition())) {
+    BI.setCondition(UndefValue::get(BI.getCondition()->getType()));
+    return &BI;
+  }
+
   // Canonicalize fcmp_one -> fcmp_oeq
   FCmpInst::Predicate FPred; Value *Y;
   if (match(&BI, m_Br(m_FCmp(FPred, m_Value(X), m_Value(Y)),
                              TrueDest, FalseDest)) &&
       BI.getCondition()->hasOneUse())
     if (FPred == FCmpInst::FCMP_ONE || FPred == FCmpInst::FCMP_OLE ||
         FPred == FCmpInst::FCMP_OGE) {
       FCmpInst *Cond = cast<FCmpInst>(BI.getCondition());

llvm/trunk/test/Transforms/InstCombine/branch.ll

+; RUN: opt -instcombine -S < %s | FileCheck %s
+
+define i32 @test(i32 %x) {
+; CHECK-LABEL: @test
+entry:
+; CHECK-NOT: icmp
+; CHECK: br i1 undef, 
+  %cmp = icmp ult i32 %x, 7
+  br i1 %cmp, label %merge, label %merge
+merge:
+; CHECK-LABEL: merge:
+; CHECK: ret i32 %x
+  ret i32 %x
+}
+
+