[TTI] Teach the cost heuristic how to query TLI to check if a zext/trunc is "free" for the target.

[andreadb]

Summary

Now that SimplifyCFG uses TTI for the cost heuristic, we can teach BasicTTIImpl how to query TLI in order to get a more accurate cost for truncates and zero-extends.

Before this patch, the basic cost heuristic (see TargetTransformInfoImplCRTPBase) would have conservatively returned a 'default' TCC_Basic for all zero-extends, and TCC_Free for truncates on native types.

This patch improves that logic so that we query TLI if available to get more accurate answers. If TLI is available, then we know we can call methods 'isZExtFree' and 'isTruncateFree' to check if a zext/trunc is free for the target.

Added more test cases in SimplifyCFG/X86/speculate-cttz-ctlz.ll. With this change, SimplifuCFG is now able to speculate a "cheap" cttz/ctlz immediately followed by a free zext/trunc.

This patch would make redundant the logic originally added in CodeGenPrepare at r225274 (reviewed here: D6853).
I plan to send other patches to remove that logic from CodeGenPrepare.

Please let me know if ok to submit.
Thanks,
Andrea

[hfinkel]

LGTM.

include/llvm/Analysis/TargetTransformInfoImpl.h

424 ↗

(On Diff #19819)

Remove the comment; we're not delegating to the "fully generic" version any more.

[andreadb]

Thanks Hal,

I removed the invalid comment from 'TargetTransformInfoImpl.h' and committed the patch at revision 228923.

-Andrea

llvm/trunk/include/llvm/Analysis/TargetTransformInfoImpl.h

unsigned getUserCost(const User *U) {
     if (const CastInst *CI = dyn_cast<CastInst>(U)) {
       // Result of a cmp instruction is often extended (to be used by other
       // cmp instructions, logical or return instructions). These are usually
       // nop on most sane targets.
       if (isa<CmpInst>(CI->getOperand(0)))
         return TTI::TCC_Free;
     }
 
-    // Otherwise delegate to the fully generic implementations.
-    return getOperationCost(
+    return static_cast<T *>(this)->getOperationCost(
         Operator::getOpcode(U), U->getType(),
         U->getNumOperands() == 1 ? U->getOperand(0)->getType() : nullptr);
   }
 };
 }
 
 #endif

llvm/trunk/include/llvm/CodeGen/BasicTTIImpl.h

public:
   }
 
   unsigned getFPOpCost(Type *Ty) {
     // By default, FP instructions are no more expensive since they are
     // implemented in HW.  Target specific TTI can override this.
     return TargetTransformInfo::TCC_Basic;
   }
 
+  unsigned getOperationCost(unsigned Opcode, Type *Ty, Type *OpTy) {
+    const TargetLoweringBase *TLI = getTLI();
+    switch (Opcode) {
+    default: break;
+    case Instruction::Trunc: {
+      if (TLI->isTruncateFree(OpTy, Ty))
+        return TargetTransformInfo::TCC_Free;
+      return TargetTransformInfo::TCC_Basic;
+    }
+    case Instruction::ZExt: {
+      if (TLI->isZExtFree(OpTy, Ty))
+        return TargetTransformInfo::TCC_Free;
+      return TargetTransformInfo::TCC_Basic;
+    }
+    }
+
+    return BaseT::getOperationCost(Opcode, Ty, OpTy);
+  }
+
   void getUnrollingPreferences(Loop *L, TTI::UnrollingPreferences &UP) {
     // This unrolling functionality is target independent, but to provide some
     // motivation for its intended use, for x86:
 
     // According to the Intel 64 and IA-32 Architectures Optimization Reference
     // Manual, Intel Core models and later have a loop stream detector (and
     // associated uop queue) that can benefit from partial unrolling.
     // The relevant requirements are:

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

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
 }
 
+; The following tests verify that calls to cttz/ctlz are speculated even if
+; basic block %cond.true has an extra zero extend/truncate which is "free"
+; for the target.
+
+define i64 @test1e(i32 %x) {
+; ALL-LABEL: @test1e(
+; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i32 %x, 0
+; ALL: [[CTTZ:%[A-Za-z0-9]+]] = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
+; ALL: [[ZEXT:%[A-Za-z0-9]+]] = zext i32 [[CTTZ]] to i64
+; BMI-NEXT: select i1 [[COND]], i64 32, i64 [[ZEXT]]
+; LZCNT-NOT: select
+; GENERIC-NOT: select
+; ALL: ret
+entry:
+  %tobool = icmp eq i32 %x, 0
+  br i1 %tobool, label %cond.end, label %cond.true
+
+cond.true:                                        ; preds = %entry
+  %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
+  %phitmp2 = zext i32 %0 to i64
+  br label %cond.end
+
+cond.end:                                         ; preds = %entry, %cond.true
+  %cond = phi i64 [ %phitmp2, %cond.true ], [ 32, %entry ]
+  ret i64 %cond
+}
+
+define i32 @test2e(i64 %x) {
+; ALL-LABEL: @test2e(
+; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i64 %x, 0
+; ALL: [[CTTZ:%[A-Za-z0-9]+]] = tail call i64 @llvm.cttz.i64(i64 %x, i1 true)
+; ALL: [[TRUNC:%[A-Za-z0-9]+]] = trunc i64 [[CTTZ]] to i32
+; BMI-NEXT: select i1 [[COND]], i32 64, i32 [[TRUNC]]
+; LZCNT-NOT: select
+; GENERIC-NOT: select
+; ALL: ret
+entry:
+  %tobool = icmp eq i64 %x, 0
+  br i1 %tobool, label %cond.end, label %cond.true
+
+cond.true:                                        ; preds = %entry
+  %0 = tail call i64 @llvm.cttz.i64(i64 %x, i1 true)
+  %cast = trunc i64 %0 to i32
+  br label %cond.end
+
+cond.end:                                         ; preds = %entry, %cond.true
+  %cond = phi i32 [ %cast, %cond.true ], [ 64, %entry ]
+  ret i32 %cond
+}
+
+define i64 @test3e(i32 %x) {
+; ALL-LABEL: @test3e(
+; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i32 %x, 0
+; ALL: [[CTLZ:%[A-Za-z0-9]+]] = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)
+; ALL: [[ZEXT:%[A-Za-z0-9]+]] = zext i32 [[CTLZ]] to i64
+; LZCNT-NEXT: select i1 [[COND]], i64 32, i64 [[ZEXT]]
+; BMI-NOT: select
+; GENERIC-NOT: select
+; ALL: ret
+entry:
+  %tobool = icmp eq i32 %x, 0
+  br i1 %tobool, label %cond.end, label %cond.true
+
+cond.true:                                        ; preds = %entry
+  %0 = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)
+  %phitmp2 = zext i32 %0 to i64
+  br label %cond.end
+
+cond.end:                                         ; preds = %entry, %cond.true
+  %cond = phi i64 [ %phitmp2, %cond.true ], [ 32, %entry ]
+  ret i64 %cond
+}
+
+define i32 @test4e(i64 %x) {
+; ALL-LABEL: @test4e(
+; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i64 %x, 0
+; ALL: [[CTLZ:%[A-Za-z0-9]+]] = tail call i64 @llvm.ctlz.i64(i64 %x, i1 true)
+; ALL: [[TRUNC:%[A-Za-z0-9]+]] = trunc i64 [[CTLZ]] to i32
+; LZCNT-NEXT: select i1 [[COND]], i32 64, i32 [[TRUNC]]
+; BMI-NOT: select
+; GENERIC-NOT: select
+; ALL: ret
+entry:
+  %tobool = icmp eq i64 %x, 0
+  br i1 %tobool, label %cond.end, label %cond.true
+
+cond.true:                                        ; preds = %entry
+  %0 = tail call i64 @llvm.ctlz.i64(i64 %x, i1 true)
+  %cast = trunc i64 %0 to i32
+  br label %cond.end
+
+cond.end:                                         ; preds = %entry, %cond.true
+  %cond = phi i32 [ %cast, %cond.true ], [ 64, %entry ]
+  ret i32 %cond
+}
+
+define i16 @test5e(i64 %x) {
+; ALL-LABEL: @test5e(
+; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i64 %x, 0
+; ALL: [[CTLZ:%[A-Za-z0-9]+]] = tail call i64 @llvm.ctlz.i64(i64 %x, i1 true)
+; ALL: [[TRUNC:%[A-Za-z0-9]+]] = trunc i64 [[CTLZ]] to i16
+; LZCNT-NEXT: select i1 [[COND]], i16 64, i16 [[TRUNC]]
+; BMI-NOT: select
+; GENERIC-NOT: select
+; ALL: ret
+entry:
+  %tobool = icmp eq i64 %x, 0
+  br i1 %tobool, label %cond.end, label %cond.true
+
+cond.true:                                        ; preds = %entry
+  %0 = tail call i64 @llvm.ctlz.i64(i64 %x, i1 true)
+  %cast = trunc i64 %0 to i16
+  br label %cond.end
+
+cond.end:                                         ; preds = %entry, %cond.true
+  %cond = phi i16 [ %cast, %cond.true ], [ 64, %entry ]
+  ret i16 %cond
+}
+
+define i16 @test6e(i32 %x) {
+; ALL-LABEL: @test6e(
+; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i32 %x, 0
+; ALL: [[CTLZ:%[A-Za-z0-9]+]] = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)
+; ALL: [[TRUNC:%[A-Za-z0-9]+]] = trunc i32 [[CTLZ]] to i16
+; LZCNT-NEXT: select i1 [[COND]], i16 32, i16 [[TRUNC]]
+; BMI-NOT: select
+; GENERIC-NOT: select
+; ALL: ret
+entry:
+  %tobool = icmp eq i32 %x, 0
+  br i1 %tobool, label %cond.end, label %cond.true
+
+cond.true:                                        ; preds = %entry
+  %0 = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)
+  %cast = trunc i32 %0 to i16
+  br label %cond.end
+
+cond.end:                                         ; preds = %entry, %cond.true
+  %cond = phi i16 [ %cast, %cond.true ], [ 32, %entry ]
+  ret i16 %cond
+}
+
+define i16 @test7e(i64 %x) {
+; ALL-LABEL: @test7e(
+; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i64 %x, 0
+; ALL: [[CTTZ:%[A-Za-z0-9]+]] = tail call i64 @llvm.cttz.i64(i64 %x, i1 true)
+; ALL: [[TRUNC:%[A-Za-z0-9]+]] = trunc i64 [[CTTZ]] to i16
+; BMI-NEXT: select i1 [[COND]], i16 64, i16 [[TRUNC]]
+; LZCNT-NOT: select
+; GENERIC-NOT: select
+; ALL: ret
+entry:
+  %tobool = icmp eq i64 %x, 0
+  br i1 %tobool, label %cond.end, label %cond.true
+
+cond.true:                                        ; preds = %entry
+  %0 = tail call i64 @llvm.cttz.i64(i64 %x, i1 true)
+  %cast = trunc i64 %0 to i16
+  br label %cond.end
+
+cond.end:                                         ; preds = %entry, %cond.true
+  %cond = phi i16 [ %cast, %cond.true ], [ 64, %entry ]
+  ret i16 %cond
+}
+
+define i16 @test8e(i32 %x) {
+; ALL-LABEL: @test8e(
+; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i32 %x, 0
+; ALL: [[CTTZ:%[A-Za-z0-9]+]] = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
+; ALL: [[TRUNC:%[A-Za-z0-9]+]] = trunc i32 [[CTTZ]] to i16
+; BMI-NEXT: select i1 [[COND]], i16 32, i16 [[TRUNC]]
+; LZCNT-NOT: select
+; GENERIC-NOT: select
+; ALL: ret
+entry:
+  %tobool = icmp eq i32 %x, 0
+  br i1 %tobool, label %cond.end, label %cond.true
+
+cond.true:                                        ; preds = %entry
+  %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
+  %cast = trunc i32 %0 to i16
+  br label %cond.end
+
+cond.end:                                         ; preds = %entry, %cond.true
+  %cond = phi i16 [ %cast, %cond.true ], [ 32, %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)