[SimplifyCFG] Fix the determination of PostBB in conditional store merging to handle the targets on the second branch being commuted

[craig.topper]

Summary

Currently we choose PostBB as the single successor of QFB, but its possible that QTB's single successor is QFB which would make QFB the correct choice.

[jmolloy]

LGTM, thanks! Looks like the rest of the code was written with this in mind, but I never got around to it.

James

[jmolloy]

test/Transforms/SimplifyCFG/merge-cond-stores.ll

40

Probably can remove this TODO now?

[craig.topper]

test/Transforms/SimplifyCFG/merge-cond-stores.ll

40

Yeah. That was my intention when I put in the TODO but forgot. Thank!

lib/Transforms/Utils/SimplifyCFG.cpp

static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI) {
   // a true condition, as in the diagram above.
   //
   BasicBlock *PTB = PBI->getSuccessor(0);
   BasicBlock *PFB = PBI->getSuccessor(1);
   BasicBlock *QTB = QBI->getSuccessor(0);
   BasicBlock *QFB = QBI->getSuccessor(1);
   BasicBlock *PostBB = QFB->getSingleSuccessor();
 
+  // Make sure we have a good guess for PostBB. If QTB's only successor is
+  // QFB, then QFB is a better PostBB.
+  if (QTB->getSingleSuccessor() == QFB)
+    PostBB = QFB;
+
+  // If we couldn't find a good PostBB, stop.
+  if (!PostBB)
+    return false;
+
   bool InvertPCond = false, InvertQCond = false;
   // Canonicalize fallthroughs to the true branches.
   if (PFB == QBI->getParent()) {
     std::swap(PFB, PTB);
     InvertPCond = true;
   }
   if (QFB == PostBB) {
     std::swap(QFB, QTB);
     InvertQCond = true;
   }
 
   // From this point on we can assume PTB or QTB may be fallthroughs but PFB
   // and QFB may not. Model fallthroughs as a nullptr block.
   if (PTB == QBI->getParent())
     PTB = nullptr;
   if (QTB == PostBB)
     QTB = nullptr;
 
   // Legality bailouts. We must have at least the non-fallthrough blocks and
   // the post-dominating block, and the non-fallthroughs must only have one
   // predecessor.
   auto HasOnePredAndOneSucc = [](BasicBlock *BB, BasicBlock *P, BasicBlock *S) {
     return BB->getSinglePredecessor() == P && BB->getSingleSuccessor() == S;
   };
-  if (!PostBB ||
-      !HasOnePredAndOneSucc(PFB, PBI->getParent(), QBI->getParent()) ||
+  if (!HasOnePredAndOneSucc(PFB, PBI->getParent(), QBI->getParent()) ||
       !HasOnePredAndOneSucc(QFB, QBI->getParent(), PostBB))
     return false;
   if ((PTB && !HasOnePredAndOneSucc(PTB, PBI->getParent(), QBI->getParent())) ||
       (QTB && !HasOnePredAndOneSucc(QTB, QBI->getParent(), PostBB)))
     return false;
   if (!PostBB->hasNUses(2) || !QBI->getParent()->hasNUses(2))
     return false;
 

test/Transforms/SimplifyCFG/merge-cond-stores.ll

yes2:
   store i32 1, i32* %p
   br label %end
 
 end:
   ret void
 }
 
 ; This is the same as test_simple, but the branch target order has been swapped
 ; TODO: This test should succeed and end up if-converted.
 define void @test_simple_commuted(i32* %p, i32 %a, i32 %b) {
 ; CHECK-LABEL: @test_simple_commuted(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X1:%.*]] = icmp eq i32 [[A:%.*]], 0
-; CHECK-NEXT:    br i1 [[X1]], label [[YES1:%.*]], label [[FALLTHROUGH:%.*]]
-; CHECK:       yes1:
-; CHECK-NEXT:    store i32 0, i32* [[P:%.*]], align 4
-; CHECK-NEXT:    br label [[FALLTHROUGH]]
-; CHECK:       fallthrough:
 ; CHECK-NEXT:    [[X2:%.*]] = icmp eq i32 [[B:%.*]], 0
-; CHECK-NEXT:    br i1 [[X2]], label [[YES2:%.*]], label [[END:%.*]]
-; CHECK:       yes2:
-; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
-; CHECK-NEXT:    br label [[END]]
-; CHECK:       end:
-; CHECK-NEXT:    ret void
+; CHECK-NEXT:    [[TMP0:%.*]] = or i1 [[X1]], [[X2]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[TMP1:%.*]], label [[TMP2:%.*]]
+; CHECK:         [[DOT:%.*]] = zext i1 [[X2]] to i32
+; CHECK-NEXT:    store i32 [[DOT]], i32* [[P:%.*]], align 4
+; CHECK-NEXT:    br label [[TMP2]]
+; CHECK:         ret void
 ;
 entry:
   %x1 = icmp eq i32 %a, 0
   br i1 %x1, label %yes1, label %fallthrough
 
 yes1:
   store i32 0, i32* %p
   br label %fallthrough