[SimplifyCFG] Cost required selects

[samparker]

Summary

Before we speculatively execute a basic block, query the cost of inserting the necessary select instructions against the phi folding threshold. For non-trivial insertions, a more accurate decision can probably be made during machine if-conversion.

[RKSimon]

llvm/test/Transforms/SimplifyCFG/ARM/select-costs.ll

87

Can you cleanup/reduce this test case any further?

[lebedev.ri]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1994

I do not understand what is going on in this function.
Why are we comparing each separate cost with threshold,
instead of accumulating the costs and comparing that?

2016

if (CostOfSelects > PHINodeFoldingThreshold * TargetTransformInfo::TCC_Basic)

[samparker]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1994

Hmm, I hadn't noticed that. Certainly happy to look into that next.

[samparker]

• Reduced test case further
• Now multiplying cost by TTI::Basic.

[samparker]

ping

[fhahn]

llvm/test/Transforms/SimplifyCFG/ARM/select-costs.ll

4

I think it would be good to also add a triple for which we hoist the code, to ensure the test keeps testing what we want.

[samparker]

Cheers, added a run for armv8a.

[mkazantsev]

llvm/test/Transforms/SimplifyCFG/ARM/select-costs.ll

1

I also don't quite get what this is about. I'd suggest the following:

• Check in this test as is, without review, with current auto-generated checks;
• Diff in patch will show what changed.

[samparker]

Rebased after precommitting the test.

[mkazantsev]

Looks good

[samparker]

@mkazantsev I made a change before committing this, as I modified the patch that this depended upon. I've now added logic to query for CodeSize instead of SizeAndLatency when we have minsize as well as adding a minsize test so the logic is still tested.

[lebedev.ri]

I guess it's an improvement for ARM, but the cost-modelling still looks bogus to me there.
It defies the point. We should calculate the single total cost of speculation,
and compare it once with the threshold, not compute parts of the cost
and compare them separately with the threshold each time.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2097–2098

here too

2155–2160

and here

[samparker]

I agree and I'm just about to upload a couple more patches, one to cover the points you just raised.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

for (Instruction &CurI : reverse(BrBB->instructionsWithoutDebug())) {
     }
   }
 
   return nullptr;
 }
 
 /// Speculate a conditional basic block flattening the CFG.
 ///
 /// Note that this is a very risky transform currently. Speculating
 /// instructions like this is most often not desirable. Instead, there is an MI
 /// pass which can do it with full awareness of the resource constraints.
 /// However, some cases are "obvious" and we should do directly. An example of
 /// this is speculating a single, reasonably cheap instruction.
 ///
 /// There is only one distinct advantage to flattening the CFG at the IR level:
 /// it makes very common but simplistic optimizations such as are common in
 /// instcombine and the DAG combiner more powerful by removing CFG edges and
 /// modeling their effects with easier to reason about SSA value graphs.
 ///
 ///
 /// An illustration of this transform is turning this IR:
 /// \code
 ///   BB:
 ///     %cmp = icmp ult %x, %y
 ///     br i1 %cmp, label %EndBB, label %ThenBB
 ///   ThenBB:
 ///     %sub = sub %x, %y
 ///     br label BB2
 ///   EndBB:
 ///     %phi = phi [ %sub, %ThenBB ], [ 0, %EndBB ]
 ///     ...
 /// \endcode
 ///
 /// Into this IR:
 /// \code
 ///   BB:
 ///     %cmp = icmp ult %x, %y
 ///     %sub = sub %x, %y
 ///     %cond = select i1 %cmp, 0, %sub
 ///     ...
 /// \endcode
 ///
 /// \returns true if the conditional block is removed.
 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);
 
+  // Check how expensive it will be to insert the necessary selects.
+  unsigned CostOfSelects = 0;
+  for (PHINode &PN : EndBB->phis()) {
+    unsigned OrigI = PN.getBasicBlockIndex(BB);
+    unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
+    Value *OrigV = PN.getIncomingValue(OrigI);
+    Value *ThenV = PN.getIncomingValue(ThenI);
+    if (OrigV != ThenV)
+      CostOfSelects +=
+          TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(), nullptr,
+                                 TargetTransformInfo::TCK_SizeAndLatency);
+  }
+  if (CostOfSelects > PHINodeFoldingThreshold * TargetTransformInfo::TCC_Basic)
+    return false;
+
   // 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;
   }
   assert(EndBB == BI->getSuccessor(!Invert) && "No edge from to end block");
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)
       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
for (PHINode &PN : EndBB->phis()) {
     ConstantExpr *OrigCE = dyn_cast<ConstantExpr>(OrigV);
     ConstantExpr *ThenCE = dyn_cast<ConstantExpr>(ThenV);
     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;
 
     // 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;

llvm/test/Transforms/SimplifyCFG/ARM/select-costs.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -mtriple=thumbv8.1m.main -simplifycfg -S %s -o - | FileCheck %s --check-prefix=V8M
 ; RUN: opt -mtriple=thumbv8m.main -simplifycfg -S %s -o - | FileCheck %s --check-prefix=V8M
 ; RUN: opt -mtriple=thumbv8m.base -simplifycfg -S %s -o - | FileCheck %s --check-prefix=V8M
 ; RUN: opt -mtriple=armv8a -simplifycfg -S %s -o - | FileCheck %s --check-prefix=V8A
 
 ; Test that the phis from for.inc.preheader aren't hoisted into sw.bb92 because
 ; the cost is too great - we can make a better decision later on.
 define i32 @multiple_spec_select_costs(i8* %a, i32* %idx, i8 %in) {
 ; V8M-LABEL: @multiple_spec_select_costs(
 ; V8M-NEXT:  entry:
 ; V8M-NEXT:    [[GEP_A_2:%.*]] = getelementptr inbounds i8, i8* [[A:%.*]], i32 2
 ; V8M-NEXT:    [[INCDEC_PTR109_C4:%.*]] = getelementptr inbounds i8, i8* [[A]], i32 3
 ; V8M-NEXT:    [[ZERO:%.*]] = icmp ne i8 [[IN:%.*]], 0
 ; V8M-NEXT:    br i1 [[ZERO]], label [[FOR_INC_PREHEADER:%.*]], label [[SW_BB92:%.*]]
 ; V8M:       sw.bb92:
 ; V8M-NEXT:    [[C_OFF_I150:%.*]] = add i8 [[IN]], -48
 ; V8M-NEXT:    [[UGT_9:%.*]] = icmp ugt i8 [[C_OFF_I150]], 9
-; V8M-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[UGT_9]], i1 false, i1 true
-; V8M-NEXT:    [[SPEC_SELECT1:%.*]] = select i1 [[UGT_9]], i32 1, i32 7
+; V8M-NEXT:    br i1 [[UGT_9]], label [[FOR_INC_PREHEADER]], label [[SELECT_UNFOLD198:%.*]]
+; V8M:       select.unfold198:
 ; V8M-NEXT:    br label [[FOR_INC_PREHEADER]]
 ; V8M:       for.inc.preheader:
-; V8M-NEXT:    [[STR_PH_0:%.*]] = phi i8* [ [[GEP_A_2]], [[ENTRY:%.*]] ], [ [[INCDEC_PTR109_C4]], [[SW_BB92]] ]
-; V8M-NEXT:    [[CMP:%.*]] = phi i1 [ false, [[ENTRY]] ], [ [[SPEC_SELECT]], [[SW_BB92]] ]
-; V8M-NEXT:    [[PHI_RES:%.*]] = phi i32 [ 1, [[ENTRY]] ], [ [[SPEC_SELECT1]], [[SW_BB92]] ]
+; V8M-NEXT:    [[STR_PH_0:%.*]] = phi i8* [ [[INCDEC_PTR109_C4]], [[SELECT_UNFOLD198]] ], [ [[INCDEC_PTR109_C4]], [[SW_BB92]] ], [ [[GEP_A_2]], [[ENTRY:%.*]] ]
+; V8M-NEXT:    [[CMP:%.*]] = phi i1 [ true, [[SELECT_UNFOLD198]] ], [ false, [[SW_BB92]] ], [ false, [[ENTRY]] ]
+; V8M-NEXT:    [[PHI_RES:%.*]] = phi i32 [ 7, [[SELECT_UNFOLD198]] ], [ 1, [[SW_BB92]] ], [ 1, [[ENTRY]] ]
 ; V8M-NEXT:    br label [[FOR_INC:%.*]]
 ; V8M:       for.inc:
 ; V8M-NEXT:    [[STR_PH_1:%.*]] = phi i8* [ [[INCDEC_PTR109:%.*]], [[FOR_BODY:%.*]] ], [ [[STR_PH_0]], [[FOR_INC_PREHEADER]] ]
 ; V8M-NEXT:    [[INCDEC_PTR109]] = getelementptr inbounds i8, i8* [[STR_PH_1]], i32 1
 ; V8M-NEXT:    [[LOAD_1:%.*]] = load i8, i8* [[INCDEC_PTR109]], align 1
 ; V8M-NEXT:    [[TOBOOL:%.*]] = icmp ne i8 [[LOAD_1]], 0
 ; V8M-NEXT:    [[AND:%.*]] = and i1 [[CMP]], [[TOBOOL]]
 ; V8M-NEXT:    br i1 [[AND]], label [[FOR_BODY]], label [[EXIT:%.*]]
sw.bb92:
   br i1 %ugt.9, label %for.inc.preheader, label %select.unfold198
 
 select.unfold198:
   br label %for.inc.preheader
 
 for.inc.preheader:
   %str.ph.0 = phi i8* [ %incdec.ptr109.c4, %select.unfold198 ], [ %incdec.ptr109.c4, %sw.bb92 ], [ %gep.a.2, %entry ]
   %cmp = phi i1 [ true, %select.unfold198 ], [ false, %sw.bb92 ], [ false, %entry ]
   %phi.res = phi i32 [ 7, %select.unfold198 ], [ 1, %sw.bb92 ], [ 1, %entry ]
   br label %for.inc
 
 for.inc:
   %str.ph.1 = phi i8* [ %incdec.ptr109, %for.body ], [ %str.ph.0, %for.inc.preheader ]
   %incdec.ptr109 = getelementptr inbounds i8, i8* %str.ph.1, i32 1
   %load.1 = load i8, i8* %incdec.ptr109, align 1
   %tobool = icmp ne i8 %load.1, 0
   %and = and i1 %cmp, %tobool