[SimplifyCFG] mergeConditionalStoreToAddress(): consider cost, not instruction count

[lebedev.ri]

Summary

As it can be see in the changed test, while div is really costly,
we were speculating it. This does not seem correct.

Also, the old code would run for every single insturuction in BB,
instead of eagerly bailing out as soon as there are too many instructions.

This function still has a problem that PHINodeFoldingThreshold is
per-basic-block, while it should be for all the basic blocks.

[lebedev.ri]

@efriedma ping

[xbolva00]

Any stats for this patch from your rawspeed?

[lebedev.ri]

In D67315#1674195, @xbolva00 wrote:

Any stats for this patch from your rawspeed?

Didn't look; this patch only exists because of @efriedma's D65148#1661691 + D65148#1662019

[lebedev.ri]

On Wed, Sep 18, 2019 at 9:02 PM James Molloy via Phabricator <[e-mail]> wrote:

jmolloy accepted this revision.
This revision is now accepted and ready to land.

Note: i don't know that this is the correct thing to do.
The old "cost" calculation seems, wrong?

[saugustine]

When running test/Transforms/SimplifyCFG/merge-cond-stores-2.ll.test under address sanitizer, this revision creates a stack-use-after-scope failure at llvm/lib/Transforms/Utils/SimplifyCFG.cpp:3008:13:

==2292==ERROR: AddressSanitizer: stack-use-after-scope on address 0x7f8214d0a180 at pc 0x5609bb711de8 bp 0x7ffe8bc79080 sp 0x7ffe8bc79078
READ of size 8 at 0x7f8214d0a180 thread T0
    #0 0x5609bb711de7 in llvm::StoreInst* const* std::__u::find<llvm::StoreInst* const*, llvm::StoreInst*>(llvm::StoreInst* const*, llvm::StoreInst* const*, llvm::StoreInst* const&) include/c++/v1/algorithm:919:13
    #1 0x5609bb6fc7a1 in mergeConditionalStoreToAddress(llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::Value*, bool, bool, llvm::DataLayout const&, llvm::TargetTransformInfo const&)::$_12::operator()(llvm::BasicBlock*, llvm::ArrayRef<llvm::StoreInst*>) const lib/Transforms/Utils/SimplifyCFG.cpp:3008:13
    #2 0x5609bb6fb8c3 in mergeConditionalStoreToAddress(llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::Value*, bool, bool, llvm::DataLayout const&, llvm::TargetTransformInfo const&) lib/Transforms/Utils/SimplifyCFG.cpp:3027:43
    #3 0x5609bb6f2e84 in mergeConditionalStores(llvm::BranchInst*, llvm::BranchInst*, llvm::DataLayout const&, llvm::TargetTransformInfo const&) lib/Transforms/Utils/SimplifyCFG.cpp:3210:16
    #4 0x5609bb6f0e1c in SimplifyCondBranchToCondBranch(llvm::BranchInst*, llvm::BranchInst*, llvm::DataLayout const&, llvm::TargetTransformInfo const&) lib/Transforms/Utils/SimplifyCFG.cpp:3277:26
    #5 0x5609bb6e2db2 in (anonymous namespace)::SimplifyCFGOpt::SimplifyCondBranch(llvm::BranchInst*, llvm::IRBuilder<llvm::ConstantFolder, llvm::IRBuilderDefaultInserter>&) lib/Transforms/Utils/SimplifyCFG.cpp:5949:13
    #6 0x5609bb6e0122 in (anonymous namespace)::SimplifyCFGOpt::simplifyOnce(llvm::BasicBlock*) lib/Transforms/Utils/SimplifyCFG.cpp:6089:11
    #7 0x5609bb6dfc9c in (anonymous namespace)::SimplifyCFGOpt::run(llvm::BasicBlock*) lib/Transforms/Utils/SimplifyCFG.cpp:6124:16
    #8 0x5609bb6dfb6a in llvm::simplifyCFG(llvm::BasicBlock*, llvm::TargetTransformInfo const&, llvm::SimplifyCFGOptions const&, llvm::SmallPtrSetImpl<llvm::BasicBlock*>*) lib/Transforms/Utils/SimplifyCFG.cpp:6135:8
    #9 0x5609bb2167b1 in iterativelySimplifyCFG(llvm::Function&, llvm::TargetTransformInfo const&, llvm::SimplifyCFGOptions const&) lib/Transforms/Scalar/SimplifyCFGPass.cpp:163:11
    #10 0x5609bb2156dc in simplifyFunctionCFG(llvm::Function&, llvm::TargetTransformInfo const&, llvm::SimplifyCFGOptions const&) lib/Transforms/Scalar/SimplifyCFGPass.cpp:177:18
    #11 0x5609bc3833b9 in llvm::FPPassManager::runOnFunction(llvm::Function&) lib/IR/LegacyPassManager.cpp:1648:27
    #12 0x5609bc3837c2 in llvm::FPPassManager::runOnModule(llvm::Module&) lib/IR/LegacyPassManager.cpp:1685:16
    #13 0x5609bc384138 in (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) lib/IR/LegacyPassManager.cpp:1750:27
...

[lebedev.ri]

In D67315#1674722, @saugustine wrote:

When running test/Transforms/SimplifyCFG/merge-cond-stores-2.ll.test under address sanitizer, this revision creates a stack-use-after-scope failure at llvm/lib/Transforms/Utils/SimplifyCFG.cpp:3008:13:

Does this still happen after rL372262?

==2292==ERROR: AddressSanitizer: stack-use-after-scope on address 0x7f8214d0a180 at pc 0x5609bb711de8 bp 0x7ffe8bc79080 sp 0x7ffe8bc79078
READ of size 8 at 0x7f8214d0a180 thread T0
    #0 0x5609bb711de7 in llvm::StoreInst* const* std::__u::find<llvm::StoreInst* const*, llvm::StoreInst*>(llvm::StoreInst* const*, llvm::StoreInst* const*, llvm::StoreInst* const&) include/c++/v1/algorithm:919:13
    #1 0x5609bb6fc7a1 in mergeConditionalStoreToAddress(llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::Value*, bool, bool, llvm::DataLayout const&, llvm::TargetTransformInfo const&)::$_12::operator()(llvm::BasicBlock*, llvm::ArrayRef<llvm::StoreInst*>) const lib/Transforms/Utils/SimplifyCFG.cpp:3008:13
    #2 0x5609bb6fb8c3 in mergeConditionalStoreToAddress(llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::Value*, bool, bool, llvm::DataLayout const&, llvm::TargetTransformInfo const&) lib/Transforms/Utils/SimplifyCFG.cpp:3027:43
    #3 0x5609bb6f2e84 in mergeConditionalStores(llvm::BranchInst*, llvm::BranchInst*, llvm::DataLayout const&, llvm::TargetTransformInfo const&) lib/Transforms/Utils/SimplifyCFG.cpp:3210:16
    #4 0x5609bb6f0e1c in SimplifyCondBranchToCondBranch(llvm::BranchInst*, llvm::BranchInst*, llvm::DataLayout const&, llvm::TargetTransformInfo const&) lib/Transforms/Utils/SimplifyCFG.cpp:3277:26
    #5 0x5609bb6e2db2 in (anonymous namespace)::SimplifyCFGOpt::SimplifyCondBranch(llvm::BranchInst*, llvm::IRBuilder<llvm::ConstantFolder, llvm::IRBuilderDefaultInserter>&) lib/Transforms/Utils/SimplifyCFG.cpp:5949:13
    #6 0x5609bb6e0122 in (anonymous namespace)::SimplifyCFGOpt::simplifyOnce(llvm::BasicBlock*) lib/Transforms/Utils/SimplifyCFG.cpp:6089:11
    #7 0x5609bb6dfc9c in (anonymous namespace)::SimplifyCFGOpt::run(llvm::BasicBlock*) lib/Transforms/Utils/SimplifyCFG.cpp:6124:16
    #8 0x5609bb6dfb6a in llvm::simplifyCFG(llvm::BasicBlock*, llvm::TargetTransformInfo const&, llvm::SimplifyCFGOptions const&, llvm::SmallPtrSetImpl<llvm::BasicBlock*>*) lib/Transforms/Utils/SimplifyCFG.cpp:6135:8
    #9 0x5609bb2167b1 in iterativelySimplifyCFG(llvm::Function&, llvm::TargetTransformInfo const&, llvm::SimplifyCFGOptions const&) lib/Transforms/Scalar/SimplifyCFGPass.cpp:163:11
    #10 0x5609bb2156dc in simplifyFunctionCFG(llvm::Function&, llvm::TargetTransformInfo const&, llvm::SimplifyCFGOptions const&) lib/Transforms/Scalar/SimplifyCFGPass.cpp:177:18
    #11 0x5609bc3833b9 in llvm::FPPassManager::runOnFunction(llvm::Function&) lib/IR/LegacyPassManager.cpp:1648:27
    #12 0x5609bc3837c2 in llvm::FPPassManager::runOnModule(llvm::Module&) lib/IR/LegacyPassManager.cpp:1685:16
    #13 0x5609bc384138 in (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) lib/IR/LegacyPassManager.cpp:1750:27
...

llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp

if (PredBB != BB)
           AlternativeV ? AlternativeV : UndefValue::get(V->getType()), PredBB);
   return PHI;
 }
 
 static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB,
                                            BasicBlock *QTB, BasicBlock *QFB,
                                            BasicBlock *PostBB, Value *Address,
                                            bool InvertPCond, bool InvertQCond,
-                                           const DataLayout &DL) {
-  auto IsaBitcastOfPointerType = [](const Instruction &I) {
-    return Operator::getOpcode(&I) == Instruction::BitCast &&
-           I.getType()->isPointerTy();
-  };
-
-  // If we're not in aggressive mode, we only optimize if we have some
-  // confidence that by optimizing we'll allow P and/or Q to be if-converted.
-  auto IsWorthwhile = [&](BasicBlock *BB) {
-    if (!BB)
-      return true;
-    // Heuristic: if the block can be if-converted/phi-folded and the
-    // instructions inside are all cheap (arithmetic/GEPs), it's worthwhile to
-    // thread this store.
-    unsigned N = 0;
-    for (auto &I : BB->instructionsWithoutDebug()) {
-      // Cheap instructions viable for folding.
-      if (isa<BinaryOperator>(I) || isa<GetElementPtrInst>(I) ||
-          isa<StoreInst>(I))
-        ++N;
-      // Free instructions.
-      else if (I.isTerminator() || IsaBitcastOfPointerType(I))
-        continue;
-      else
-        return false;
-    }
-    // The store we want to merge is counted in N, so add 1 to make sure
-    // we're counting the instructions that would be left.
-    return N <= (PHINodeFoldingThreshold + 1);
-  };
-
-  if (!MergeCondStoresAggressively &&
-      (!IsWorthwhile(PTB) || !IsWorthwhile(PFB) || !IsWorthwhile(QTB) ||
-       !IsWorthwhile(QFB)))
-    return false;
-
+                                           const DataLayout &DL,
+                                           const TargetTransformInfo &TTI) {
   // For every pointer, there must be exactly two stores, one coming from
   // PTB or PFB, and the other from QTB or QFB. We don't support more than one
   // store (to any address) in PTB,PFB or QTB,QFB.
   // FIXME: We could relax this restriction with a bit more work and performance
   // testing.
   StoreInst *PStore = findUniqueStoreInBlocks(PTB, PFB);
   StoreInst *QStore = findUniqueStoreInBlocks(QTB, QFB);
   if (!PStore || !QStore)
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 we're not in aggressive mode, we only optimize if we have some
+  // confidence that by optimizing we'll allow P and/or Q to be if-converted.
+  auto IsWorthwhile = [&](BasicBlock *BB, ArrayRef<StoreInst *> FreeStores) {
+    if (!BB)
+      return true;
+    // Heuristic: if the block can be if-converted/phi-folded and the
+    // instructions inside are all cheap (arithmetic/GEPs), it's worthwhile to
+    // thread this store.
+    int BudgetRemaining =
+        PHINodeFoldingThreshold * TargetTransformInfo::TCC_Basic;
+    for (auto &I : BB->instructionsWithoutDebug()) {
+      // Consider terminator instruction to be free.
+      if (I.isTerminator())
+        continue;
+      // If this is one the stores that we want to speculate out of this BB,
+      // then don't count it's cost, consider it to be free.
+      if (auto *S = dyn_cast<StoreInst>(&I))
+        if (llvm::find(FreeStores, S))
+          continue;
+      // Else, we have a white-list of instructions that we are ak speculating.
+      if (!isa<BinaryOperator>(I) && !isa<GetElementPtrInst>(I))
+        return false; // Not in white-list - not worthwhile folding.
+      // And finally, if this is a non-free instruction that we are okay
+      // speculating, ensure that we consider the speculation budget.
+      BudgetRemaining -= TTI.getUserCost(&I);
+      if (BudgetRemaining < 0)
+        return false; // Eagerly refuse to fold as soon as we're out of budget.
+    }
+    assert(BudgetRemaining >= 0 &&
+           "When we run out of budget we will eagerly return from within the "
+           "per-instruction loop.");
+    return true;
+  };
+
+  ArrayRef<StoreInst *> FreeStores = {PStore, QStore};
+  if (!MergeCondStoresAggressively &&
+      (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
+       !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
+    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();
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB,
 
   QStore->eraseFromParent();
   PStore->eraseFromParent();
 
   return true;
 }
 
 static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI,
-                                   const DataLayout &DL) {
+                                   const DataLayout &DL,
+                                   const TargetTransformInfo &TTI) {
   // The intention here is to find diamonds or triangles (see below) where each
   // conditional block contains a store to the same address. Both of these
   // stores are conditional, so they can't be unconditionally sunk. But it may
   // be profitable to speculatively sink the stores into one merged store at the
   // end, and predicate the merged store on the union of the two conditions of
   // PBI and QBI.
   //
   // This can reduce the number of stores executed if both of the conditions are
static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI,
   set_intersect(PStoreAddresses, QStoreAddresses);
   // set_intersect mutates PStoreAddresses in place. Rename it here to make it
   // clear what it contains.
   auto &CommonAddresses = PStoreAddresses;
 
   bool Changed = false;
   for (auto *Address : CommonAddresses)
     Changed |= mergeConditionalStoreToAddress(
-        PTB, PFB, QTB, QFB, PostBB, Address, InvertPCond, InvertQCond, DL);
+        PTB, PFB, QTB, QFB, PostBB, Address, InvertPCond, InvertQCond, DL, TTI);
   return Changed;
 }
 
 /// If we have a conditional branch as a predecessor of another block,
 /// this function tries to simplify it.  We know
 /// that PBI and BI are both conditional branches, and BI is in one of the
 /// successor blocks of PBI - PBI branches to BI.
 static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI,
-                                           const DataLayout &DL) {
+                                           const DataLayout &DL,
+                                           const TargetTransformInfo &TTI) {
   assert(PBI->isConditional() && BI->isConditional());
   BasicBlock *BB = BI->getParent();
 
   // If this block ends with a branch instruction, and if there is a
   // predecessor that ends on a branch of the same condition, make
   // this conditional branch redundant.
   if (PBI->getCondition() == BI->getCondition() &&
       PBI->getSuccessor(0) != PBI->getSuccessor(1)) {
static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI,
 
   if (auto *CE = dyn_cast<ConstantExpr>(BI->getCondition()))
     if (CE->canTrap())
       return false;
 
   // If both branches are conditional and both contain stores to the same
   // address, remove the stores from the conditionals and create a conditional
   // merged store at the end.
-  if (MergeCondStores && mergeConditionalStores(PBI, BI, DL))
+  if (MergeCondStores && mergeConditionalStores(PBI, BI, DL, TTI))
     return true;
 
   // If this is a conditional branch in an empty block, and if any
   // predecessors are a conditional branch to one of our destinations,
   // fold the conditions into logical ops and one cond br.
 
   // Ignore dbg intrinsics.
   if (&*BB->instructionsWithoutDebug().begin() != BI)
if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition()))
     if (PN->getParent() == BI->getParent())
       if (FoldCondBranchOnPHI(BI, DL, Options.AC))
         return requestResimplify();
 
   // Scan predecessor blocks for conditional branches.
   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
     if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
       if (PBI != BI && PBI->isConditional())
-        if (SimplifyCondBranchToCondBranch(PBI, BI, DL))
+        if (SimplifyCondBranchToCondBranch(PBI, BI, DL, TTI))
           return requestResimplify();
 
   // Look for diamond patterns.
   if (MergeCondStores)
     if (BasicBlock *PrevBB = allPredecessorsComeFromSameSource(BB))
       if (BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
         if (PBI != BI && PBI->isConditional())
-          if (mergeConditionalStores(PBI, BI, DL))
+          if (mergeConditionalStores(PBI, BI, DL, TTI))
             return requestResimplify();
 
   return false;
 }
 
 /// Check if passing a value to an instruction will cause undefined behavior.
 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) {
   Constant *C = dyn_cast<Constant>(V);

llvm/trunk/test/Transforms/SimplifyCFG/X86/merge-cond-stores-cost.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -simplifycfg -mtriple=x86_64-unknown-unknown < %s -simplifycfg-merge-cond-stores=true -simplifycfg-merge-cond-stores-aggressively=false -phi-node-folding-threshold=2 -S | FileCheck %s
 
 define void @test_costly(i32* %p, i32 %a, i32 %b, i32 %c, i32 %d) {
 ; CHECK-LABEL: @test_costly(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X1:%.*]] = icmp eq i32 [[A:%.*]], 0
 ; CHECK-NEXT:    br i1 [[X1]], label [[FALLTHROUGH:%.*]], label [[YES1:%.*]]
 ; CHECK:       yes1:
 ; CHECK-NEXT:    [[VAL0:%.*]] = sdiv i32 [[D:%.*]], [[C:%.*]]
+; CHECK-NEXT:    store i32 [[VAL0]], i32* [[P:%.*]]
 ; CHECK-NEXT:    br label [[FALLTHROUGH]]
 ; CHECK:       fallthrough:
-; CHECK-NEXT:    [[SIMPLIFYCFG_MERGE:%.*]] = phi i32 [ [[VAL0]], [[YES1]] ], [ undef, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[X2:%.*]] = icmp eq i32 [[B:%.*]], 0
 ; CHECK-NEXT:    br i1 [[X2]], label [[END:%.*]], label [[YES2:%.*]]
 ; CHECK:       yes2:
 ; CHECK-NEXT:    [[VAL1:%.*]] = sdiv i32 [[C]], [[D]]
+; CHECK-NEXT:    store i32 [[VAL1]], i32* [[P]]
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[SIMPLIFYCFG_MERGE1:%.*]] = phi i32 [ [[VAL1]], [[YES2]] ], [ [[SIMPLIFYCFG_MERGE]], [[FALLTHROUGH]] ]
-; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[X1]], true
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[X2]], true
-; CHECK-NEXT:    [[TMP2:%.*]] = or i1 [[TMP0]], [[TMP1]]
-; CHECK-NEXT:    br i1 [[TMP2]], label [[TMP3:%.*]], label [[TMP4:%.*]]
-; CHECK:       3:
-; CHECK-NEXT:    store i32 [[SIMPLIFYCFG_MERGE1]], i32* [[P:%.*]], align 4
-; CHECK-NEXT:    br label [[TMP4]]
-; CHECK:       4:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %x1 = icmp eq i32 %a, 0
   br i1 %x1, label %fallthrough, label %yes1
 
 yes1:
   %val0 = sdiv i32 %d, %c