[SimplifyCFG] Fix a debug invariant bug in FoldBranchToCommonDest()

[dstenb]

Summary

Fix a case where FoldBranchToCommonDest() would bail out from doing CSE
when encountering a debug intrinsic. Handle that by skipping past the
debug intrinsics.

Also, as a minor refactoring, rename checkCSEInPredecessor() to
tryCSEWithPredecessor() to make it a bit more clear that the function
may remove instructions.

[davide]

lib/Transforms/Utils/SimplifyCFG.cpp

2580–2585

Can Cond be a DbgInfoIntrinsic here?

[vsk]

lib/Transforms/Utils/SimplifyCFG.cpp

2559

Can this simply be written as: for (auto &Curr : BB->instructionsWithoutDebug())?

[dstenb]

lib/Transforms/Utils/SimplifyCFG.cpp

2559

As we may erase instructions, I don't think we can use a range-based for loop here.

2580–2585

I guess that Cond is guaranteed to be a CmpInst or BinaryOperator here, based on the guard on line 2575.

[fhahn]

lib/Transforms/Utils/SimplifyCFG.cpp

2559

Yep, unfortunately this is quite a widespread pattern which prevents us from using range-based loops.... Maybe there's something nicer/ more generic we could do in such cases, but I think that would require some further investigation.

test/Transforms/SimplifyCFG/fold-branch-debuginvariant.ll

7

Could you use CHECK-LABEL here and for bb2?

8

nit: IMO it is slightly clearer when matching the operands too: and i1 false, false would

[dstenb]

Addressed comments!

[dstenb]

Any more comments on this?

[fhahn]

LGTM, thanks. Please wait a bit with committing in case @davide (or anybody else) has any more comments.

[davide]

lg

[dstenb]

Thanks for the reviews! I'll submit this shortly.

lib/Transforms/Utils/SimplifyCFG.cpp

static bool SimplifyCondBranchToTwoReturns(BranchInst *BI,
 
   EraseTerminatorInstAndDCECond(BI);
 
   return true;
 }
 
 /// Return true if the given instruction is available
 /// in its predecessor block. If yes, the instruction will be removed.
-static bool checkCSEInPredecessor(Instruction *Inst, BasicBlock *PB) {
+static bool tryCSEWithPredecessor(Instruction *Inst, BasicBlock *PB) {
   if (!isa<BinaryOperator>(Inst) && !isa<CmpInst>(Inst))
     return false;
   for (Instruction &I : *PB) {
     Instruction *PBI = &I;
     // Check whether Inst and PBI generate the same value.
     if (Inst->isIdenticalTo(PBI)) {
       Inst->replaceAllUsesWith(PBI);
       Inst->eraseFromParent();
else {
     // BB has a single predecessor and BB's successor is also its predecessor's
     // successor. If such pattern exists, check for CSE between BB and its
     // predecessor.
     if (BasicBlock *PB = BB->getSinglePredecessor())
       if (BranchInst *PBI = dyn_cast<BranchInst>(PB->getTerminator()))
         if (PBI->isConditional() &&
             (BI->getSuccessor(0) == PBI->getSuccessor(0) ||
              BI->getSuccessor(0) == PBI->getSuccessor(1))) {
-          for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
+          for (auto I = BB->instructionsWithoutDebug().begin(),
+                    E = BB->instructionsWithoutDebug().end();
+               I != E;) {
             Instruction *Curr = &*I++;
             if (isa<CmpInst>(Curr)) {
               Cond = Curr;
               break;
             }
             // Quit if we can't remove this instruction.
-            if (!checkCSEInPredecessor(Curr, PB))
+            if (!tryCSEWithPredecessor(Curr, PB))
               return false;
           }
         }
 
     if (!Cond)
       return false;
   }
 
   if (!Cond || (!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) ||
       Cond->getParent() != BB || !Cond->hasOneUse())
     return false;
 
   // Make sure the instruction after the condition is the cond branch.
   BasicBlock::iterator CondIt = ++Cond->getIterator();
 
   // Ignore dbg intrinsics.
   while (isa<DbgInfoIntrinsic>(CondIt))
     ++CondIt;
 
   if (&*CondIt != BI)
     return false;
 
   // Only allow this transformation if computing the condition doesn't involve
   // too many instructions and these involved instructions can be executed
   // unconditionally. We denote all involved instructions except the condition
   // as "bonus instructions", and only allow this transformation when the
   // number of the bonus instructions does not exceed a certain threshold.

test/Transforms/SimplifyCFG/fold-branch-debuginvariant.ll

+; RUN: opt < %s -simplifycfg -S | FileCheck %s
+; RUN: opt < %s -strip-debug -simplifycfg -S | FileCheck %s
+
+; Verify that the and.2 instruction is eliminated even in the presence of a
+; preceding debug intrinsic.
+
+; CHECK: bb1:
+; CHECK: and i1
+; CHECK: bb2:
+; CHECK-NOT: and i1
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: norecurse nounwind
+define void @foo() local_unnamed_addr #0 !dbg !4 {
+bb1:
+  %and.1 = and i1 false, false
+  %cmp = icmp eq i16 0, 0
+  br i1 %cmp, label %bb2, label %bb3
+
+bb2:                                              ; preds = %bb1
+  call void @llvm.dbg.value(metadata i16 0, metadata !8, metadata !DIExpression()), !dbg !9
+  %and.2 = and i1 false, false
+  br label %bb3
+
+bb3:                                              ; preds = %bb2, %bb1
+  ret void
+}
+
+; Function Attrs: nounwind readnone speculatable
+declare void @llvm.dbg.value(metadata, metadata, metadata) #1
+
+attributes #0 = { norecurse nounwind }
+attributes #1 = { nounwind readnone speculatable }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C, file: !1, producer: "Foo", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, retainedTypes: !2, globals: !2)
+!1 = !DIFile(filename: "foo.c", directory: "/")
+!2 = !{}
+!3 = !{i32 2, !"Debug Info Version", i32 3}
+!4 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 10, type: !5, isLocal: false, isDefinition: true, scopeLine: 10, isOptimized: false, unit: !0, retainedNodes: !2)
+!5 = !DISubroutineType(types: !6)
+!6 = !{null, !7}
+!7 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!8 = !DILocalVariable(name: "p_1", arg: 1, scope: !4, line: 4, type: !7)
+!9 = distinct !DILocation(line: 11, column: 3, scope: !4)