[TTI] improved cost heuristic for cttz/ctlz calls.

[andreadb]

Summary

This is a follow-up of the patch committed by James at r228826 (see D7506).

Now that SimplifyCFG uses TargetTransformInfo for cost analysis, we have to fix the cost heuristic for intrinsic calls to cttz/ctlz.

Revision r224899 (reviewed here: D6728) added two new hooks to TLI to let targets define whether cttz/ctlz are cheap or not. For example, on x86, ctlz is very expensive if the target doesn't have feature LZCNT.

This patch defines method getIntrinsicCost in BasicTTIImpl: now BasicTTIImpl queries TLI to check how expensive is a call to cttz/ctlz for the target.

I added some test cases in Transforms/SimplifyCFG/X86 to verify that SimplifyCFG only speculates cttz/ctlz when those are "cheap" for the target. I also removed a test case in SimplifyCFG/SpeculativelyExec.ll since it is not profitable to speculate a slow call to cttz even if we pass flag -phi-node-folding-threshold=2 to opt.

Please let me know if ok to submit.

P.s. The long term goal (if possible) is to migrate the logic added in CodeGenPrepare at r224899 into SimplifyCFG.

[hfinkel]

LGTM.

[andreadb]

Hi Hal,
Thanks for the quick review!
Committed revision 228829.

include/llvm/CodeGen/BasicTTIImpl.h

bool isTruncateFree(Type *Ty1, Type *Ty2) {
     return getTLI()->isTruncateFree(Ty1, Ty2);
   }
 
   bool isTypeLegal(Type *Ty) {
     EVT VT = getTLI()->getValueType(Ty);
     return getTLI()->isTypeLegal(VT);
   }
 
+  unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
+                            ArrayRef<const Value *> Arguments) {
+    return BaseT::getIntrinsicCost(IID, RetTy, Arguments);
+  }
+
+  unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
+                            ArrayRef<Type *> ParamTys) {
+    if (IID == Intrinsic::cttz) {
+      if (getTLI()->isCheapToSpeculateCttz())
+        return TargetTransformInfo::TCC_Basic;
+      return TargetTransformInfo::TCC_Expensive;
+    }
+
+    if (IID == Intrinsic::ctlz) {
+       if (getTLI()->isCheapToSpeculateCtlz())
+        return TargetTransformInfo::TCC_Basic;
+      return TargetTransformInfo::TCC_Expensive;
+    }
+
+    return BaseT::getIntrinsicCost(IID, RetTy, ParamTys);
+  }
+
   unsigned getJumpBufAlignment() { return getTLI()->getJumpBufAlignment(); }
 
   unsigned getJumpBufSize() { return getTLI()->getJumpBufSize(); }
 
   bool shouldBuildLookupTables() {
     const TargetLoweringBase *TLI = getTLI();
     return TLI->isOperationLegalOrCustom(ISD::BR_JT, MVT::Other) ||
            TLI->isOperationLegalOrCustom(ISD::BRIND, MVT::Other);

test/Transforms/SimplifyCFG/SpeculativeExec.ll

bb2:    ; preds = bb1
   br label %bb3
 
 bb3:    ; preds = %bb2, %entry
   %tmp4 = phi i32 [ %b, %entry ], [ %a, %bb1 ], [ %tmp3, %bb2 ]
         %tmp5 = sub i32 %tmp4, 1
   ret i32 %tmp5
 }
 
-declare i8 @llvm.cttz.i8(i8, i1)
-
-define i8 @test2(i8 %a) {
-; CHECK-LABEL: @test2(
-  br i1 undef, label %bb_true, label %bb_false
-bb_true:
-  %b = tail call i8 @llvm.cttz.i8(i8 %a, i1 false)
-  br label %join
-bb_false:
-  br label %join
-join:
-  %c = phi i8 [%b, %bb_true], [%a, %bb_false]
-; CHECK: select
-  ret i8 %c
-}
-
 define i8* @test4(i1* %dummy, i8* %a, i8* %b) {
 ; Test that we don't speculate an arbitrarily large number of unfolded constant
 ; expressions.
 ; CHECK-LABEL: @test4(
 
 entry:
   %cond1 = load volatile i1* %dummy
   br i1 %cond1, label %if, label %end

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: 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: 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: 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: 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: 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: 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
+
+cond.end:                                         ; preds = %entry, %cond.true
+  %cond = phi i16 [ %0, %cond.true ], [ 16, %entry ]
+  ret i16 %cond
+}
+
+declare i64 @llvm.ctlz.i64(i64, i1)
+declare i32 @llvm.ctlz.i32(i32, i1)
+declare i16 @llvm.ctlz.i16(i16, i1)
+declare i64 @llvm.cttz.i64(i64, i1)
+declare i32 @llvm.cttz.i32(i32, i1)
+declare i16 @llvm.cttz.i16(i16, i1)