[SimplifyCFG] Accumulate cost against budget

[samparker]

Summary

As highlighted in D82438, the speculation cost isn't accumulated in SpeculativelyExecuteBB. So now include the selects, the speculated instruction and any constant expressions against the set threshold.

[lebedev.ri]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2099–2104

Please add a new cl::opt for that.
I believe, the threshold should be the branch misprediction cost,
i.e. if it takes less cost (latency) to execute the branch
then to wrongly predict that it won't be executed,
but then rewind and execute it anyways, we should just execute it.

So i'd go with 20.

[samparker]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2099–2104

Most of the cost modelling framework actually tries to assume that branches are always predicated though, and I don't understand why making arbitrary decisions about machine details would be a good idea here. Plus, it's also completely irrelevant to code size... It would seem to be better to query the latency / size of the branch, but I highly doubt that would produce results that anyone would want...

[lebedev.ri]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2179

Ah, so this transform basically never fires then,

2183

I'm not sure what is going on here.

[lebedev.ri]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2099–2104

I'll rephrase: given that the cost modelling logic changed,
the remaining value of PHINodeFoldingThreshold is completely wrong.

[samparker]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2099–2104

Okay... so I guess we need to start at: What is the purpose of this code? I think it's trying to convert any number of phis and speculate, at most, a single instruction (and maybe try to figure out something with constexprs). If PHINodeFoldingThreshold is supposed to represent the cost of a cmp + sel, this doesn't feel completely broken to me but the threshold could just be PHINodeFoldingThreshold * NumPHIs?

[lebedev.ri]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2099–2104

I have no idea, it's you who is changing/fixing this,
you should know how it works, so you tell me :)

I'm just saying that since the entire cost-modelling logic
changed from "let's just ensure that every single instruction
is below some threshold, and ignore total cost"
to "let's count the total cost", it is pretty obvious
that using the old threshold as-is makes no sense.

[samparker]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2099–2104

Yeah, so I think multiplying by the number of phis should bring us back inline with what we were doing before.

[samparker]

Rebased after reorganising the two parts of code that evaluate phis. The budget now allows a basic cost for each phi within the block, plus a basic cost for the one instruction that we may speculate.

[samparker]

Ping.

[lebedev.ri]

Please do address my review comments.

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

 #include <utility>
 #include <vector>
 
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "simplifycfg"
 
-// Chosen as 2 so as to be cheap, but still to have enough power to fold
-// a select, so the "clamp" idiom (of a min followed by a max) will be caught.
-// To catch this, we need to fold a compare and a select, hence '2' being the
-// minimum reasonable default.
+/// The cost of converting each phi to a select, with the total cost allowed
+/// for the block is this value multiplied by the total number of phis, plus
+/// one to allow the speculation of a single instruction.
 static cl::opt<unsigned> PHINodeFoldingThreshold(
-    "phi-node-folding-threshold", cl::Hidden, cl::init(2),
+    "phi-node-folding-threshold", cl::Hidden, cl::init(1),
     cl::desc(
-        "Control the amount of phi node folding to perform (default = 2)"));
+        "Control the amount of phi node folding to perform (default = 1)"));
 
 static cl::opt<unsigned> TwoEntryPHINodeFoldingThreshold(
     "two-entry-phi-node-folding-threshold", cl::Hidden, cl::init(4),
     cl::desc("Control the maximal total instruction cost that we are willing "
              "to speculatively execute to fold a 2-entry PHI node into a "
              "select (default = 4)"));
 
 static cl::opt<bool> DupRet(
for (PHINode &PN : EndBB->phis()) {
     if (!OrigCE && !ThenCE)
       continue; // Known safe and cheap.
 
     if ((ThenCE && !isSafeToSpeculativelyExecute(ThenCE)) ||
         (OrigCE && !isSafeToSpeculativelyExecute(OrigCE)))
       return false;
     unsigned OrigCost = OrigCE ? ComputeSpeculationCost(OrigCE, TTI) : 0;
     unsigned ThenCost = ThenCE ? ComputeSpeculationCost(ThenCE, TTI) : 0;
-    unsigned MaxCost =
-        2 * PHINodeFoldingThreshold * TargetTransformInfo::TCC_Basic;
-    if (OrigCost + ThenCost > MaxCost)
-      return false;
+    BudgetRemaining -= OrigCost + ThenCost;
 
     // Account for the cost of an unfolded ConstantExpr which could end up
     // getting expanded into Instructions.
     // FIXME: This doesn't account for how many operations are combined in the
     // constant expression.
     ++SpeculatedInstructions;
     if (SpeculatedInstructions > 1)
       return false;
bool SimplifyCFGOpt::SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB,
                                             const TargetTransformInfo &TTI) {
   // Be conservative for now. FP select instruction can often be expensive.
   Value *BrCond = BI->getCondition();
   if (isa<FCmpInst>(BrCond))
     return false;
 
   BasicBlock *BB = BI->getParent();
   BasicBlock *EndBB = ThenBB->getTerminator()->getSuccessor(0);
-  int BudgetRemaining =
-    PHINodeFoldingThreshold * TargetTransformInfo::TCC_Basic;
+
+  // Enable the cost of speculating a single basic instruction plus a basic cost
+  // for each phi in the block.
+  unsigned NumPHIs = std::distance(EndBB->phis().begin(), EndBB->phis().end());
+  int BudgetRemaining = TargetTransformInfo::TCC_Basic +
+    (TargetTransformInfo::TCC_Basic * NumPHIs * PHINodeFoldingThreshold);
 
   // If ThenBB is actually on the false edge of the conditional branch, remember
   // to swap the select operands later.
   bool Invert = false;
   if (ThenBB != BI->getSuccessor(0)) {
     assert(ThenBB == BI->getSuccessor(1) && "No edge from 'if' block?");
     Invert = true;
   }
for (BasicBlock::iterator BBI = ThenBB->begin(),
     if (SpeculatedInstructions > 1)
       return false;
 
     // Don't hoist the instruction if it's unsafe or expensive.
     if (!isSafeToSpeculativelyExecute(I) &&
         !(HoistCondStores && (SpeculatedStoreValue = isSafeToSpeculateStore(
                                   I, BB, ThenBB, EndBB))))
       return false;
-    if (!SpeculatedStoreValue &&
-        ComputeSpeculationCost(I, TTI) >
-            PHINodeFoldingThreshold * TargetTransformInfo::TCC_Basic)
+    if (!SpeculatedStoreValue) {
+      BudgetRemaining -= ComputeSpeculationCost(I, TTI);
+      if (BudgetRemaining < 0)
         return false;
+    }
 
     // Store the store speculation candidate.
     if (SpeculatedStoreValue)
       SpeculatedStore = cast<StoreInst>(I);
 
     // Do not hoist the instruction if any of its operands are defined but not
     // used in BB. The transformation will prevent the operand from
     // being sunk into the use block.
bool SimplifyCFGOpt::SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB,
   // speculation. Note, while we iterate over a DenseMap here, we are summing
   // and so iteration order isn't significant.
   for (SmallDenseMap<Instruction *, unsigned, 4>::iterator
            I = SinkCandidateUseCounts.begin(),
            E = SinkCandidateUseCounts.end();
        I != E; ++I)
     if (I->first->hasNUses(I->second)) {
       ++SpeculatedInstructions;
       if (SpeculatedInstructions > 1)
         return false;
     }
 
   // Check that we can insert the selects and that it's not too expensive to do
   // so.
   bool Convert = SpeculatedStore != nullptr;
   Convert |= validateAndCostRequiredSelects(BB, ThenBB, EndBB,
                                             SpeculatedInstructions,
                                             BudgetRemaining, TTI);
   if (!Convert || BudgetRemaining < 0)
     return false;