[MIPS] add overrides for isCheapToSpeculateCttz() and isCheapToSpeculateCtlz()

[spatel]

Summary

MIPS is using the default TLI cost settings for count-leading/trailing-zeros. I think these are considered cheap operations (and therefore fair game for speculation) for any MIPS implementation.

The net result of allowing this speculation for the MIPS regression tests in this patch is that we get this branchless 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.

[vkalintiris]

Thank you for tackling this. I have only two minor comments.

lib/Target/Mips/MipsISelLowering.h

238–244 ↗

(On Diff #39708)

pre-MIPS32 ISAs don't have dedicated leading/trailing bit counting instructions. We should return true only if Subtarget.hasMips32() is true.

test/Transforms/SimplifyCFG/Mips/cttz-ctlz.ll

1 ↗

(On Diff #39708)

Can you provide a full triple, eg. mips-linux-gnu?

[dsanders]

It will LGTM with the changes Vasileios has requested.

test/Transforms/SimplifyCFG/Mips/cttz-ctlz.ll

1 ↗

(On Diff #39708)

If you don't want to specify the full triple you could use -march=mips

[spatel]

Thanks, Vasileios and Daniel!

Patch updated:

1. Fixed to check that Subtarget.hasMips32().
2. Specified triple as "mips-linux-gnu"; note: I don't think we can just specify an arch here because that won't initialize the target machine for 'opt'.

[dsanders]

LGTM, thanks.

2. Specified triple as "mips-linux-gnu"; note: I don't think we can just specify an arch here because that won't initialize the target machine for 'opt'.

It will but the way it does it is a bit weird in my opinion. It takes the default target triple and swaps the first component for the value of -march as long as llvm::Triple recognizes it. This can potentially lead to some odd triples like mips-pc-windows-msvc but they work in many parts of LLVM.

llvm/trunk/lib/Target/Mips/MipsISelLowering.h

public:
     /// or null if the target does not support "fast" ISel.
     FastISel *createFastISel(FunctionLoweringInfo &funcInfo,
                              const TargetLibraryInfo *libInfo) const override;
 
     MVT getScalarShiftAmountTy(const DataLayout &, EVT) const override {
       return MVT::i32;
     }
 
+    bool isCheapToSpeculateCttz() const override;
+    bool isCheapToSpeculateCtlz() const override;
+
     void LowerOperationWrapper(SDNode *N,
                                SmallVectorImpl<SDValue> &Results,
                                SelectionDAG &DAG) const override;
 
     /// LowerOperation - Provide custom lowering hooks for some operations.
     SDValue LowerOperation(SDValue Op, SelectionDAG &DAG) const override;
 
     /// ReplaceNodeResults - Replace the results of node with an illegal result

llvm/trunk/lib/Target/Mips/MipsISelLowering.cpp

case ISD::OR:
     return performORCombine(N, DAG, DCI, Subtarget);
   case ISD::ADD:
     return performADDCombine(N, DAG, DCI, Subtarget);
   }
 
   return SDValue();
 }
 
+bool MipsTargetLowering::isCheapToSpeculateCttz() const {
+  return Subtarget.hasMips32();
+}
+
+bool MipsTargetLowering::isCheapToSpeculateCtlz() const {
+  return Subtarget.hasMips32();
+}
+
 void
 MipsTargetLowering::LowerOperationWrapper(SDNode *N,
                                           SmallVectorImpl<SDValue> &Results,
                                           SelectionDAG &DAG) const {
   SDValue Res = LowerOperation(SDValue(N, 0), DAG);
 
   for (unsigned I = 0, E = Res->getNumValues(); I != E; ++I)
     Results.push_back(Res.getValue(I));

llvm/trunk/test/Transforms/SimplifyCFG/Mips/cttz-ctlz.ll

+; 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)
+

llvm/trunk/test/Transforms/SimplifyCFG/Mips/lit.local.cfg

+config.suffixes = ['.ll']
+
+targets = set(config.root.targets_to_build.split())
+if not 'Mips' in targets:
+    config.unsupported = True