[SimplifyCFG] allow speculation of exactly one expensive instruction (PR24818)

[spatel]

Summary

This is the last general step to allow more IR-level speculation with a safety harness in place in CodeGenPrepare.

The intent is to restore the behavior enabled by:
http://reviews.llvm.org/rL228826

but prevent bad performance such as:
https://llvm.org/bugs/show_bug.cgi?id=24818

Earlier patches in this sequence:
D12882 (disable SimplifyCFG speculation for expensive instructions)
D13297 (have CGP despeculate expensive ops)
D14630 (have CGP despeculate special versions of cttz/ctlz)

As shown in the test cases, we only have two instructions currently affected: ctz for some x86 and fdiv generally. Allowing exactly one expensive instruction is a bit of a hack, but it lines up with what is currently implemented in CGP. If we make the despeculation more general in CGP, we can make the speculation here more liberal.

A follow-up patch will adjust the cost for sqrt and possibly other typically expensive math intrinsics (currently everything is cheap by default). GPU targets would likely want to override those expensive default costs (just as they probably should already override the cost of div/rem) because just about any math is cheaper than control-flow on those targets.

[spatel]

Ping.

[jmolloy]

Hi Sanjay,

Just a couple of comments.

James

lib/Transforms/Utils/SimplifyCFG.cpp

307 ↗

(On Diff #41806)

I think !empty() is a quicker predicate than size(). I also think as Depth is an integer and you're using it in integer context, "Depth > 0" would be more explanatory.

I think this is the sort of heuristic that it would be good to get as a cl::opt.

[spatel]

Patch updated based on James' feedback:

1. Fixed check to use !empty() rather than size().
2. Fixed check to specify 'Depth > 0' since it's an integer.
3. Added cl::opt override to disable this.

[spatel]

Patch updated:
The cl::opt check in the last rev was wrong. Added another run and checks to the fdiv test to make sure it's right this time.

[jmolloy]

LGTM now, thanks!

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

cl::desc("Hoist conditional stores even if an unconditional store does not "
              "precede - hoist multiple conditional stores into a single "
              "predicated store"));
 
 static cl::opt<bool> MergeCondStoresAggressively(
     "simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false),
     cl::desc("When merging conditional stores, do so even if the resultant "
              "basic blocks are unlikely to be if-converted as a result"));
 
+static cl::opt<bool> SpeculateOneExpensiveInst(
+    "speculate-one-expensive-inst", cl::Hidden, cl::init(true),
+    cl::desc("Allow exactly one expensive instruction to be speculatively "
+             "executed"));
+
 STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps");
 STATISTIC(NumLinearMaps, "Number of switch instructions turned into linear mapping");
 STATISTIC(NumLookupTables, "Number of switch instructions turned into lookup tables");
 STATISTIC(NumLookupTablesHoles, "Number of switch instructions turned into lookup tables (holes checked)");
 STATISTIC(NumTableCmpReuses, "Number of reused switch table lookup compares");
 STATISTIC(NumSinkCommons, "Number of common instructions sunk down to the end block");
 STATISTIC(NumSpeculations, "Number of speculative executed instructions");
 

 /// Select whose cost is 2.
 ///
 /// After this function returns, CostRemaining is decreased by the cost of
 /// V plus its non-dominating operands.  If that cost is greater than
 /// CostRemaining, false is returned and CostRemaining is undefined.
 static bool DominatesMergePoint(Value *V, BasicBlock *BB,
                                 SmallPtrSetImpl<Instruction*> *AggressiveInsts,
                                 unsigned &CostRemaining,
-                                const TargetTransformInfo &TTI) {
+                                const TargetTransformInfo &TTI,
+                                unsigned Depth = 0) {
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I) {
     // Non-instructions all dominate instructions, but not all constantexprs
     // can be executed unconditionally.
     if (ConstantExpr *C = dyn_cast<ConstantExpr>(V))
       if (C->canTrap())
         return false;
     return true;
static bool DominatesMergePoint(Value *V, BasicBlock *BB,
   // Okay, it looks like the instruction IS in the "condition".  Check to
   // see if it's a cheap instruction to unconditionally compute, and if it
   // only uses stuff defined outside of the condition.  If so, hoist it out.
   if (!isSafeToSpeculativelyExecute(I))
     return false;
 
   unsigned Cost = ComputeSpeculationCost(I, TTI);
 
-  if (Cost > CostRemaining)
+  // Allow exactly one instruction to be speculated regardless of its cost
+  // (as long as it is safe to do so).
+  // This is intended to flatten the CFG even if the instruction is a division
+  // or other expensive operation. The speculation of an expensive instruction
+  // is expected to be undone in CodeGenPrepare if the speculation has not
+  // enabled further IR optimizations.
+  if (Cost > CostRemaining &&
+      (!SpeculateOneExpensiveInst || !AggressiveInsts->empty() || Depth > 0))
     return false;
 
-  CostRemaining -= Cost;
+  // Avoid unsigned wrap.
+  CostRemaining = (Cost > CostRemaining) ? 0 : CostRemaining - Cost;
 
   // Okay, we can only really hoist these out if their operands do
   // not take us over the cost threshold.
   for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i)
-    if (!DominatesMergePoint(*i, BB, AggressiveInsts, CostRemaining, TTI))
+    if (!DominatesMergePoint(*i, BB, AggressiveInsts, CostRemaining, TTI,
+                             Depth + 1))
       return false;
   // Okay, it's safe to do this!  Remember this instruction.
   AggressiveInsts->insert(I);
   return true;
 }
 
 /// Extract ConstantInt from value, looking through IntToPtr
 /// and PointerNullValue. Return NULL if value is not a constant int.

llvm/trunk/test/Transforms/SimplifyCFG/X86/speculate-cttz-ctlz.ll

 ; RUN: opt -S -simplifycfg -mtriple=x86_64-unknown-unknown -mattr=+bmi < %s | FileCheck %s --check-prefix=ALL --check-prefix=BMI
 ; RUN: opt -S -simplifycfg -mtriple=x86_64-unknown-unknown -mattr=+lzcnt < %s | FileCheck %s --check-prefix=ALL --check-prefix=LZCNT
 ; RUN: opt -S -simplifycfg -mtriple=x86_64-unknown-unknown < %s | FileCheck %s --check-prefix=ALL --check-prefix=GENERIC
 
 
 define i64 @test1(i64 %A) {
 ; ALL-LABEL: @test1(
 ; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i64 %A, 0
 ; ALL: [[CTLZ:%[A-Za-z0-9]+]] = tail call i64 @llvm.ctlz.i64(i64 %A, i1 true)
-; LZCNT-NEXT: select i1 [[COND]], i64 64, i64 [[CTLZ]]
-; BMI-NOT: select
-; GENERIC-NOT: select
+; ALL-NEXT: select i1 [[COND]], i64 64, i64 [[CTLZ]]
 ; ALL: ret
 entry:
   %tobool = icmp eq i64 %A, 0
   br i1 %tobool, label %cond.end, label %cond.true
 
 cond.true:                                        ; preds = %entry
   %0 = tail call i64 @llvm.ctlz.i64(i64 %A, i1 true)
   br label %cond.end
 
 cond.end:                                         ; preds = %entry, %cond.true
   %cond = phi i64 [ %0, %cond.true ], [ 64, %entry ]
   ret i64 %cond
 }
 
 define i32 @test2(i32 %A) {
 ; ALL-LABEL: @test2(
 ; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i32 %A, 0
 ; ALL: [[CTLZ:%[A-Za-z0-9]+]] = tail call i32 @llvm.ctlz.i32(i32 %A, i1 true)
-; LZCNT-NEXT: select i1 [[COND]], i32 32, i32 [[CTLZ]]
-; BMI-NOT: select
-; GENERIC-NOT: select
+; ALL-NEXT: select i1 [[COND]], i32 32, i32 [[CTLZ]]
 ; ALL: ret
 entry:
   %tobool = icmp eq i32 %A, 0
   br i1 %tobool, label %cond.end, label %cond.true
 
 cond.true:                                        ; preds = %entry
   %0 = tail call i32 @llvm.ctlz.i32(i32 %A, i1 true)
   br label %cond.end
 
 cond.end:                                         ; preds = %entry, %cond.true
   %cond = phi i32 [ %0, %cond.true ], [ 32, %entry ]
   ret i32 %cond
 }
 
 
 define signext i16 @test3(i16 signext %A) {
 ; ALL-LABEL: @test3(
 ; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i16 %A, 0
 ; ALL: [[CTLZ:%[A-Za-z0-9]+]] = tail call i16 @llvm.ctlz.i16(i16 %A, i1 true)
-; LZCNT-NEXT: select i1 [[COND]], i16 16, i16 [[CTLZ]]
-; BMI-NOT: select
-; GENERIC-NOT: select
+; ALL-NEXT: select i1 [[COND]], i16 16, i16 [[CTLZ]]
 ; ALL: ret
 entry:
   %tobool = icmp eq i16 %A, 0
   br i1 %tobool, label %cond.end, label %cond.true
 
 cond.true:                                        ; preds = %entry
   %0 = tail call i16 @llvm.ctlz.i16(i16 %A, i1 true)
   br label %cond.end
 
 cond.end:                                         ; preds = %entry, %cond.true
   %cond = phi i16 [ %0, %cond.true ], [ 16, %entry ]
   ret i16 %cond
 }
 
 
 define i64 @test1b(i64 %A) {
 ; ALL-LABEL: @test1b(
 ; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i64 %A, 0
 ; ALL: [[CTTZ:%[A-Za-z0-9]+]] = tail call i64 @llvm.cttz.i64(i64 %A, i1 true)
-; BMI-NEXT: select i1 [[COND]], i64 64, i64 [[CTTZ]]
-; LZCNT-NOT: select
-; GENERIC-NOT: select
+; ALL-NEXT: select i1 [[COND]], i64 64, i64 [[CTTZ]]
 ; ALL: ret
 entry:
   %tobool = icmp eq i64 %A, 0
   br i1 %tobool, label %cond.end, label %cond.true
 
 cond.true:                                        ; preds = %entry
   %0 = tail call i64 @llvm.cttz.i64(i64 %A, i1 true)
   br label %cond.end
 
 cond.end:                                         ; preds = %entry, %cond.true
   %cond = phi i64 [ %0, %cond.true ], [ 64, %entry ]
   ret i64 %cond
 }
 
 
 define i32 @test2b(i32 %A) {
 ; ALL-LABEL: @test2b(
 ; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i32 %A, 0
 ; ALL: [[CTTZ:%[A-Za-z0-9]+]] = tail call i32 @llvm.cttz.i32(i32 %A, i1 true)
-; BMI-NEXT: select i1 [[COND]], i32 32, i32 [[CTTZ]]
-; LZCNT-NOT: select
-; GENERIC-NOT: select
+; ALL-NEXT: select i1 [[COND]], i32 32, i32 [[CTTZ]]
 ; ALL: ret
 entry:
   %tobool = icmp eq i32 %A, 0
   br i1 %tobool, label %cond.end, label %cond.true
 
 cond.true:                                        ; preds = %entry
   %0 = tail call i32 @llvm.cttz.i32(i32 %A, i1 true)
   br label %cond.end
 
 cond.end:                                         ; preds = %entry, %cond.true
   %cond = phi i32 [ %0, %cond.true ], [ 32, %entry ]
   ret i32 %cond
 }
 
 
 define signext i16 @test3b(i16 signext %A) {
 ; ALL-LABEL: @test3b(
 ; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i16 %A, 0
 ; ALL: [[CTTZ:%[A-Za-z0-9]+]] = tail call i16 @llvm.cttz.i16(i16 %A, i1 true)
-; BMI-NEXT: select i1 [[COND]], i16 16, i16 [[CTTZ]]
-; LZCNT-NOT: select
-; GENERIC-NOT: select
+; ALL-NEXT: select i1 [[COND]], i16 16, i16 [[CTTZ]]
 ; ALL: ret
 entry:
   %tobool = icmp eq i16 %A, 0
   br i1 %tobool, label %cond.end, label %cond.true
 
 cond.true:                                        ; preds = %entry
   %0 = tail call i16 @llvm.cttz.i16(i16 %A, i1 true)
   br label %cond.end

llvm/trunk/test/Transforms/SimplifyCFG/speculate-math.ll

-; RUN: opt -S -simplifycfg -phi-node-folding-threshold=2 < %s | FileCheck %s
+; RUN: opt -S -simplifycfg < %s | FileCheck %s --check-prefix=EXPENSIVE --check-prefix=ALL
+; RUN: opt -S -simplifycfg -speculate-one-expensive-inst=false < %s | FileCheck %s --check-prefix=CHEAP --check-prefix=ALL
 
 declare float @llvm.sqrt.f32(float) nounwind readonly
 declare float @llvm.fma.f32(float, float, float) nounwind readonly
 declare float @llvm.fmuladd.f32(float, float, float) nounwind readonly
 declare float @llvm.fabs.f32(float) nounwind readonly
 declare float @llvm.minnum.f32(float, float) nounwind readonly
 declare float @llvm.maxnum.f32(float, float) nounwind readonly
 
-; FIXME: This is intended to be a temporary test. As discussed in 
-; D12882, we actually do want to speculate even expensive operations
-; in SimplifyCFG because it can expose more optimizations for other
-; passes. Therefore, we either need to adjust SimplifyCFG's 
-; calculations that use the TTI cost model or use a different cost
-; model for deciding which ops should be speculated in SimplifyCFG. 
-; We should also be using the TTI cost model later - for example in
-; CodeGenPrepare - to potentially undo this speculation.
+; ALL-LABEL: @fdiv_test(
+; EXPENSIVE: select i1 %cmp, double %div, double 0.0
+; CHEAP-NOT: select
 
-; Do not speculate fdiv by default because it is generally expensive. 
-
-; CHECK-LABEL: @fdiv_test(
-; CHECK-NOT: select
 define double @fdiv_test(double %a, double %b) {
 entry:
   %cmp = fcmp ogt double %a, 0.0
   br i1 %cmp, label %cond.true, label %cond.end
 
 cond.true:
   %div = fdiv double %b, %a
   br label %cond.end
 
 cond.end:
   %cond = phi double [ %div, %cond.true ], [ 0.0, %entry ]
   ret double %cond
 }
 
-; CHECK-LABEL: @sqrt_test(
-; CHECK: select
+; ALL-LABEL: @sqrt_test(
+; ALL: select
 define void @sqrt_test(float addrspace(1)* noalias nocapture %out, float %a) nounwind {
 entry:
   %cmp.i = fcmp olt float %a, 0.000000e+00
   br i1 %cmp.i, label %test_sqrt.exit, label %cond.else.i
 
 cond.else.i:                                      ; preds = %entry
   %0 = tail call float @llvm.sqrt.f32(float %a) nounwind readnone
   br label %test_sqrt.exit
 
 test_sqrt.exit:                                   ; preds = %cond.else.i, %entry
   %cond.i = phi float [ %0, %cond.else.i ], [ 0x7FF8000000000000, %entry ]
   store float %cond.i, float addrspace(1)* %out, align 4
   ret void
 }
 
-; CHECK-LABEL: @fabs_test(
-; CHECK: select
+; ALL-LABEL: @fabs_test(
+; ALL: select
 define void @fabs_test(float addrspace(1)* noalias nocapture %out, float %a) nounwind {
 entry:
   %cmp.i = fcmp olt float %a, 0.000000e+00
   br i1 %cmp.i, label %test_fabs.exit, label %cond.else.i
 
 cond.else.i:                                      ; preds = %entry
   %0 = tail call float @llvm.fabs.f32(float %a) nounwind readnone
   br label %test_fabs.exit
 
 test_fabs.exit:                                   ; preds = %cond.else.i, %entry
   %cond.i = phi float [ %0, %cond.else.i ], [ 0x7FF8000000000000, %entry ]
   store float %cond.i, float addrspace(1)* %out, align 4
   ret void
 }
 
-; CHECK-LABEL: @fma_test(
-; CHECK: select
+; ALL-LABEL: @fma_test(
+; ALL: select
 define void @fma_test(float addrspace(1)* noalias nocapture %out, float %a, float %b, float %c) nounwind {
 entry:
   %cmp.i = fcmp olt float %a, 0.000000e+00
   br i1 %cmp.i, label %test_fma.exit, label %cond.else.i
 
 cond.else.i:                                      ; preds = %entry
   %0 = tail call float @llvm.fma.f32(float %a, float %b, float %c) nounwind readnone
   br label %test_fma.exit
 
 test_fma.exit:                                   ; preds = %cond.else.i, %entry
   %cond.i = phi float [ %0, %cond.else.i ], [ 0x7FF8000000000000, %entry ]
   store float %cond.i, float addrspace(1)* %out, align 4
   ret void
 }
 
-; CHECK-LABEL: @fmuladd_test(
-; CHECK: select
+; ALL-LABEL: @fmuladd_test(
+; ALL: select
 define void @fmuladd_test(float addrspace(1)* noalias nocapture %out, float %a, float %b, float %c) nounwind {
 entry:
   %cmp.i = fcmp olt float %a, 0.000000e+00
   br i1 %cmp.i, label %test_fmuladd.exit, label %cond.else.i
 
 cond.else.i:                                      ; preds = %entry
   %0 = tail call float @llvm.fmuladd.f32(float %a, float %b, float %c) nounwind readnone
   br label %test_fmuladd.exit
 
 test_fmuladd.exit:                                   ; preds = %cond.else.i, %entry
   %cond.i = phi float [ %0, %cond.else.i ], [ 0x7FF8000000000000, %entry ]
   store float %cond.i, float addrspace(1)* %out, align 4
   ret void
 }
 
-; CHECK-LABEL: @minnum_test(
-; CHECK: select
+; ALL-LABEL: @minnum_test(
+; ALL: select
 define void @minnum_test(float addrspace(1)* noalias nocapture %out, float %a, float %b) nounwind {
 entry:
   %cmp.i = fcmp olt float %a, 0.000000e+00
   br i1 %cmp.i, label %test_minnum.exit, label %cond.else.i
 
 cond.else.i:                                      ; preds = %entry
   %0 = tail call float @llvm.minnum.f32(float %a, float %b) nounwind readnone
   br label %test_minnum.exit
 
 test_minnum.exit:                                   ; preds = %cond.else.i, %entry
   %cond.i = phi float [ %0, %cond.else.i ], [ 0x7FF8000000000000, %entry ]
   store float %cond.i, float addrspace(1)* %out, align 4
   ret void
 }
 
-; CHECK-LABEL: @maxnum_test(
-; CHECK: select
+; ALL-LABEL: @maxnum_test(
+; ALL: select
 define void @maxnum_test(float addrspace(1)* noalias nocapture %out, float %a, float %b) nounwind {
 entry:
   %cmp.i = fcmp olt float %a, 0.000000e+00
   br i1 %cmp.i, label %test_maxnum.exit, label %cond.else.i
 
 cond.else.i:                                      ; preds = %entry
   %0 = tail call float @llvm.maxnum.f32(float %a, float %b) nounwind readnone
   br label %test_maxnum.exit
 
 test_maxnum.exit:                                   ; preds = %cond.else.i, %entry
   %cond.i = phi float [ %0, %cond.else.i ], [ 0x7FF8000000000000, %entry ]
   store float %cond.i, float addrspace(1)* %out, align 4
   ret void
 }