From 03849aaa4e9c3859d39aa2e2573a0f69d6b3eb7f Mon Sep 17 00:00:00 2001
From: Sanjay Patel <spatel@rotateright.com>
Date: Wed, 11 Nov 2015 17:24:56 +0000
Subject: [PATCH] [MIPS] add overrides for isCheapToSpeculateCttz() and
 isCheapToSpeculateCtlz()

MIPS32 has instructions for efficient count-leading/trailing-zeros, so this should be
considered a cheap operation (and therefore fair game for speculation) for any MIPS32
implementation.

The net result of allowing this speculation for the regression tests in this patch is
that we get this code:

ctlz:
  jr  $ra
  clz  $2, $4

cttz:
  addiu  $1, $4, -1
  not  $2, $4
  and  $1, $2, $1
  clz  $1, $1
  addiu  $2, $zero, 32
  jr  $ra
  subu  $2, $2, $1

Instead of:

ctlz:
  beqz  $4, $BB0_2
  addiu  $2, $zero, 32
  clz  $2, $4
$BB0_2:
  jr  $ra
  nop

cttz:
  beqz  $4, $BB1_2
  addiu  $2, $zero, 32
  addiu  $1, $4, -1
  not  $2, $4
  and  $1, $2, $1
  clz  $1, $1
  addiu  $2, $zero, 32
  subu  $2, $2, $1
$BB1_2:
  jr  $ra
  nop

See D14469 for the larger motivation.

Differential Revision: http://reviews.llvm.org/D14500



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@252755 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Target/Mips/MipsISelLowering.cpp          |  8 ++++
 lib/Target/Mips/MipsISelLowering.h            |  3 ++
 test/Transforms/SimplifyCFG/Mips/cttz-ctlz.ll | 43 +++++++++++++++++++
 .../Transforms/SimplifyCFG/Mips/lit.local.cfg |  5 +++
 4 files changed, 59 insertions(+)
 create mode 100644 test/Transforms/SimplifyCFG/Mips/cttz-ctlz.ll
 create mode 100644 test/Transforms/SimplifyCFG/Mips/lit.local.cfg

diff --git a/lib/Target/Mips/MipsISelLowering.cpp b/lib/Target/Mips/MipsISelLowering.cpp
index 66c495bc3e9..142d14a13a2 100644
--- a/lib/Target/Mips/MipsISelLowering.cpp
+++ b/lib/Target/Mips/MipsISelLowering.cpp
@@ -834,6 +834,14 @@ SDValue  MipsTargetLowering::PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI)
   return SDValue();
 }
 
+bool MipsTargetLowering::isCheapToSpeculateCttz() const {
+  return Subtarget.hasMips32();
+}
+
+bool MipsTargetLowering::isCheapToSpeculateCtlz() const {
+  return Subtarget.hasMips32();
+}
+
 void
 MipsTargetLowering::LowerOperationWrapper(SDNode *N,
                                           SmallVectorImpl<SDValue> &Results,
diff --git a/lib/Target/Mips/MipsISelLowering.h b/lib/Target/Mips/MipsISelLowering.h
index 8e2cb0b4a6c..b33e125b81b 100644
--- a/lib/Target/Mips/MipsISelLowering.h
+++ b/lib/Target/Mips/MipsISelLowering.h
@@ -235,6 +235,9 @@ namespace llvm {
       return MVT::i32;
     }
 
+    bool isCheapToSpeculateCttz() const override;
+    bool isCheapToSpeculateCtlz() const override;
+
     void LowerOperationWrapper(SDNode *N,
                                SmallVectorImpl<SDValue> &Results,
                                SelectionDAG &DAG) const override;
diff --git a/test/Transforms/SimplifyCFG/Mips/cttz-ctlz.ll b/test/Transforms/SimplifyCFG/Mips/cttz-ctlz.ll
new file mode 100644
index 00000000000..b4bfb51dd14
--- /dev/null
+++ b/test/Transforms/SimplifyCFG/Mips/cttz-ctlz.ll
@@ -0,0 +1,43 @@
+; RUN: opt -S -simplifycfg -mtriple=mips-linux-gnu < %s | FileCheck %s
+
+define i32 @ctlz(i32 %A) {
+; CHECK-LABEL: @ctlz(
+; CHECK: [[ICMP:%[A-Za-z0-9]+]] = icmp eq i32 %A, 0
+; CHECK-NEXT: [[CTZ:%[A-Za-z0-9]+]] = tail call i32 @llvm.ctlz.i32(i32 %A, i1 true)
+; CHECK-NEXT: [[SEL:%[A-Za-z0-9.]+]] = select i1 [[ICMP]], i32 32, i32 [[CTZ]]
+; CHECK-NEXT: ret i32 [[SEL]]
+entry:
+  %tobool = icmp eq i32 %A, 0
+  br i1 %tobool, label %cond.end, label %cond.true
+
+cond.true:
+  %0 = tail call i32 @llvm.ctlz.i32(i32 %A, i1 true)
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %0, %cond.true ], [ 32, %entry ]
+  ret i32 %cond
+}
+
+define i32 @cttz(i32 %A) {
+; CHECK-LABEL: @cttz(
+; CHECK: [[ICMP:%[A-Za-z0-9]+]] = icmp eq i32 %A, 0
+; CHECK-NEXT: [[CTZ:%[A-Za-z0-9]+]] = tail call i32 @llvm.cttz.i32(i32 %A, i1 true)
+; CHECK-NEXT: [[SEL:%[A-Za-z0-9.]+]] = select i1 [[ICMP]], i32 32, i32 [[CTZ]]
+; CHECK-NEXT: ret i32 [[SEL]]
+entry:
+  %tobool = icmp eq i32 %A, 0
+  br i1 %tobool, label %cond.end, label %cond.true
+
+cond.true:
+  %0 = tail call i32 @llvm.cttz.i32(i32 %A, i1 true)
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %0, %cond.true ], [ 32, %entry ]
+  ret i32 %cond
+}
+
+declare i32 @llvm.ctlz.i32(i32, i1)
+declare i32 @llvm.cttz.i32(i32, i1)
+
diff --git a/test/Transforms/SimplifyCFG/Mips/lit.local.cfg b/test/Transforms/SimplifyCFG/Mips/lit.local.cfg
new file mode 100644
index 00000000000..683bfdccb74
--- /dev/null
+++ b/test/Transforms/SimplifyCFG/Mips/lit.local.cfg
@@ -0,0 +1,5 @@
+config.suffixes = ['.ll']
+
+targets = set(config.root.targets_to_build.split())
+if not 'Mips' in targets:
+    config.unsupported = True
-- 
2.34.1