[SimplifyCFG] Teach merge conditional stores to handle cases where the PostBB has more than 2 predecessors by inserting a new block for the store.

[craig.topper]

Summary

Currently merge conditional stores can't handle cases where PostBB (the block we need to move the store to) has more than 2 predecessors.

This patch removes that restriction by creating a new block with only the 2 predecessors we care about and an unconditional branch to the original block. This provides a place to put the store.

[craig.topper]

Ping

[craig.topper]

Ping * 2

[efriedma]

Do you know how much impact this has, in the sense of making this transform trigger more often in benchmarks?

lib/Transforms/Utils/SimplifyCFG.cpp

2975

You might want to explicitly note what is known about the terminators of QTB/QFB here; pred_begin can return a block multiple times in cases where a terminator contains multiple uses of a successor. (I don't think you can hit that case here, but it took me a few minutes to convince myself.)

[craig.topper]

This didn't affect the resulting binary of most of the benchmarks in the set we normally look at. Out of the few that did change, one showed a perf improvement. The rest looked to be in the noise.

[craig.topper]

Add additional comment

[efriedma]

LGTM

I completely forgot about this, sorry about the delay.

lib/Transforms/Utils/SimplifyCFG.cpp

if (QTB)
     for (auto &I : *QTB)
       if (&I != QStore && I.mayReadOrWriteMemory())
         return false;
   for (auto I = BasicBlock::iterator(PStore), E = PStore->getParent()->end();
        I != E; ++I)
     if (&*I != PStore && I->mayReadOrWriteMemory())
       return false;
 
+  // If PostBB has more than two predecessors, we need to split it so we can
+  // sink the store.
+  if (std::next(pred_begin(PostBB), 2) != pred_end(PostBB)) {
+    // We know that QFB's only successor is PostBB. And QFB has a single
+    // predecessor. If QTB exists, then its only successor is also PostBB.
+    // If QTB does not exist, then QFB's only predecessor has a conditional
+    // branch to QFB and PostBB.
+    BasicBlock *TruePred = QTB ? QTB : QFB->getSinglePredecessor();
+    BasicBlock *NewBB = SplitBlockPredecessors(PostBB, { QFB, TruePred},
+                                               "condstore.split");
+    if (!NewBB)
+      return false;
+    PostBB = NewBB;
+  }
+
   // OK, we're going to sink the stores to PostBB. The store has to be
   // conditional though, so first create the predicate.
   Value *PCond = cast<BranchInst>(PFB->getSinglePredecessor()->getTerminator())
                      ->getCondition();
   Value *QCond = cast<BranchInst>(QFB->getSinglePredecessor()->getTerminator())
                      ->getCondition();
 
   Value *PPHI = ensureValueAvailableInSuccessor(PStore->getValueOperand(),
auto HasOnePredAndOneSucc = [](BasicBlock *BB, BasicBlock *P, BasicBlock *S) {
     return BB->getSinglePredecessor() == P && BB->getSingleSuccessor() == S;
   };
   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))
+  if (!QBI->getParent()->hasNUses(2))
     return false;
 
   // OK, this is a sequence of two diamonds or triangles.
   // Check if there are stores in PTB or PFB that are repeated in QTB or QFB.
   SmallPtrSet<Value *, 4> PStoreAddresses, QStoreAddresses;
   for (auto *BB : {PTB, PFB}) {
     if (!BB)
       continue;

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

no2:
   call void @f()
   %z3 = sub i32 %z2, %b
   br label %end
 
 end:
   %z4 = phi i32 [ %z3, %no2 ], [ 3, %yes2 ]
   ret i32 %z4
 }
+
+; This test has an out if over the two triangles. This requires creating a new BB to hold the store.
+define void @test_outer_if(i32* %p, i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @test_outer_if(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[X3:%.*]] = icmp eq i32 [[C:%.*]], 0
+; CHECK-NEXT:    br i1 [[X3]], label [[END:%.*]], label [[CONTINUE:%.*]]
+; CHECK:       continue:
+; CHECK-NEXT:    [[X1:%.*]] = icmp ne i32 [[A:%.*]], 0
+; CHECK-NEXT:    [[X2:%.*]] = icmp eq i32 [[B:%.*]], 0
+; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[X2]], true
+; CHECK-NEXT:    [[TMP1:%.*]] = or i1 [[X1]], [[TMP0]]
+; CHECK-NEXT:    br i1 [[TMP1]], label [[TMP2:%.*]], label [[END]]
+; CHECK:         [[NOT_X2:%.*]] = xor i1 [[X2]], true
+; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = zext i1 [[NOT_X2]] to i32
+; CHECK-NEXT:    store i32 [[SPEC_SELECT]], i32* [[P:%.*]], align 4
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %x3 = icmp eq i32 %c, 0
+  br i1 %x3, label %end, label %continue
+continue:
+  %x1 = icmp eq i32 %a, 0
+  br i1 %x1, label %fallthrough, label %yes1
+yes1:
+  store i32 0, i32* %p
+  br label %fallthrough
+  fallthrough:
+  %x2 = icmp eq i32 %b, 0
+  br i1 %x2, label %end, label %yes2
+yes2:
+  store i32 1, i32* %p
+  br label %end
+end:
+  ret void
+}
+