[mips] Sign-extend i32 values truncated from previously zero-extended i32 values.

[vkalintiris]

Summary

This is a special case for MIPS64 because the architecture requires
properly 32-bit sign-extended values in the register containers.

Additionaly, we merge consecutive trunc + AssertZExt nodes in order
to avoid unnecessary sign-extensions when the extension comes from a
type smaller than i32.

[vkalintiris]

Avoid C++ DAG-to-DAG transformations by using tablegen's PatFrag for AssertZexts widening from types less than i32.

[dsanders]

lib/Target/Mips/Mips64InstrInfo.td

516 ↗

(On Diff #53390)

Could you add a comment explaining why this isn't valid for the i32 case?

lib/Target/Mips/MipsISelLowering.cpp

823 ↗

(On Diff #53390)

Some closing parenthesis are missing on the LHS.

823–827 ↗

(On Diff #53390)

The code implements the right behaviour but I think the expressions in the comment may be inside-out and the usage of 'outer' and 'inner' are the opposite way around to what I'd expect ('outer' is used for N->getOperand(0)->getOperand(0)). Shouldn't the first expression be?:

(AssertZext:i32 (trunc:i32 (AssertZext:i64 X, i32)), i8)
  -> (trunc:i32 (AssertZext X, i8))

Also, I don't think the test cases cover this dag combine rule at the moment. assertzext-trunc.ll doesn't trigger the assertzext/trunc/assertzext case we've looked at before. divrem.ll and octeon_popcnt.ll used to trigger it but don't anymore because of the change to make the arguments signext.

[vkalintiris]

Use wider/narrower semantics for nested AssertZext nodes and add a new test case.

lib/Target/Mips/MipsISelLowering.cpp

823–827 ↗

(On Diff #53390)

Shouldn't the first expression be?:

(AssertZext:i32 (trunc:i32 (AssertZext:i64 X, i32)), i8)

-> (trunc:i32 (AssertZext X, i8))

That's correct, I swapped the VTs accidentally.

Also, I don't think the test cases cover this dag combine rule at the moment.

It's covered (albeit implicitly) by llvm-ir/{udiv,lshr}.ll and mips64-f128.ll. I copied the IR that triggers this behaviour from llvm-ir/udiv.ll to assertzext-trunc.ll.

[dsanders]

LGTM with a change to the new comment.

lib/Target/Mips/Mips64InstrInfo.td

516 ↗

(On Diff #53526)

We need to be explicit about what it means to be 'properly sign-extended' since the correct behaviour is likely to be counter-intuitive to most readers. If you were to ask what the register representation of the uint32_t value 0x80000000 is on a 64-bit MIPS, I doubt many people would answer 0xFFFFFFFF80000000.

llvm/trunk/lib/Target/Mips/Mips64InstrInfo.td

def PowerOf2HI : PatLeaf<(imm), [{
   if (N->getValueType(0) == MVT::i64) {
     uint64_t Imm = N->getZExtValue();
     return isPowerOf2_64(Imm) && (Imm & 0xffffffff00000000) == Imm;
   }
   else
     return false;
 }]>;
 
+def assertzext_lt_i32 : PatFrag<(ops node:$src), (assertzext node:$src), [{
+  return cast<VTSDNode>(N->getOperand(1))->getVT().bitsLT(MVT::i32);
+}]>;
+
 //===----------------------------------------------------------------------===//
 // Instructions specific format
 //===----------------------------------------------------------------------===//
 let usesCustomInserter = 1 in {
   def ATOMIC_LOAD_ADD_I64  : Atomic2Ops<atomic_load_add_64, GPR64>;
   def ATOMIC_LOAD_SUB_I64  : Atomic2Ops<atomic_load_sub_64, GPR64>;
   def ATOMIC_LOAD_AND_I64  : Atomic2Ops<atomic_load_and_64, GPR64>;
   def ATOMIC_LOAD_OR_I64   : Atomic2Ops<atomic_load_or_64, GPR64>;

 defm : SetlePats<GPR64, SLT64, SLTu64>;
 defm : SetgtPats<GPR64, SLT64, SLTu64>;
 defm : SetgePats<GPR64, SLT64, SLTu64>;
 defm : SetgeImmPats<GPR64, SLTi64, SLTiu64>;
 
 // truncate
 def : MipsPat<(trunc (assertsext GPR64:$src)),
               (EXTRACT_SUBREG GPR64:$src, sub_32)>;
-def : MipsPat<(trunc (assertzext GPR64:$src)),
+// The forward compatibility strategy employed by MIPS requires us to treat
+// values as being sign extended to an infinite number of bits. This allows
+// existing software to run without modification on any future MIPS
+// implementation (e.g. 128-bit, or 1024-bit). Being compatible with this
+// strategy requires that truncation acts as a sign-extension for values being
+// fed into instructions operating on 32-bit values. Such instructions have
+// undefined results if this is not true.
+// For our case, this means that we can't issue an extract_subreg for nodes
+// such as (trunc:i32 (assertzext:i64 X, i32)), because the sign-bit of the
+// lower subreg would not be replicated into the upper half.
+def : MipsPat<(trunc (assertzext_lt_i32 GPR64:$src)),
               (EXTRACT_SUBREG GPR64:$src, sub_32)>;
 def : MipsPat<(i32 (trunc GPR64:$src)),
               (SLL (EXTRACT_SUBREG GPR64:$src, sub_32), 0)>;
 
 // variable shift instructions patterns
 def : MipsPat<(shl GPR64:$rt, (i32 (trunc GPR64:$rs))),
               (DSLLV GPR64:$rt, (EXTRACT_SUBREG GPR64:$rs, sub_32))>;
 def : MipsPat<(srl GPR64:$rt, (i32 (trunc GPR64:$rs))),

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

MipsTargetLowering::MipsTargetLowering(const MipsTargetMachine &TM,
   setOperationAction(ISD::TRAP, MVT::Other, Legal);
 
   setTargetDAGCombine(ISD::SDIVREM);
   setTargetDAGCombine(ISD::UDIVREM);
   setTargetDAGCombine(ISD::SELECT);
   setTargetDAGCombine(ISD::AND);
   setTargetDAGCombine(ISD::OR);
   setTargetDAGCombine(ISD::ADD);
+  setTargetDAGCombine(ISD::AssertZext);
 
   setMinFunctionAlignment(Subtarget.isGP64bit() ? 3 : 2);
 
   // The arguments on the stack are defined in terms of 4-byte slots on O32
   // and 8-byte slots on N32/N64.
   setMinStackArgumentAlignment((ABI.IsN32() || ABI.IsN64()) ? 8 : 4);
 
   setStackPointerRegisterToSaveRestore(ABI.IsN64() ? Mips::SP_64 : Mips::SP);
static SDValue performADDCombine(SDNode *N, SelectionDAG &DAG,
   EVT ValTy = N->getValueType(0);
   SDLoc DL(N);
 
   SDValue Add1 = DAG.getNode(ISD::ADD, DL, ValTy, N->getOperand(0),
                              Add.getOperand(0));
   return DAG.getNode(ISD::ADD, DL, ValTy, Add1, Lo);
 }
 
+static SDValue performAssertZextCombine(SDNode *N, SelectionDAG &DAG,
+                                        TargetLowering::DAGCombinerInfo &DCI,
+                                        const MipsSubtarget &Subtarget) {
+  SDValue N0 = N->getOperand(0);
+  EVT NarrowerVT = cast<VTSDNode>(N->getOperand(1))->getVT();
+
+  if (N0.getOpcode() != ISD::TRUNCATE)
+    return SDValue();
+
+  if (N0.getOperand(0).getOpcode() != ISD::AssertZext)
+    return SDValue();
+
+  // fold (AssertZext (trunc (AssertZext x))) -> (trunc (AssertZext x))
+  // if the type of the extension of the innermost AssertZext node is
+  // smaller from that of the outermost node, eg:
+  // (AssertZext:i32 (trunc:i32 (AssertZext:i64 X, i32)), i8)
+  //   -> (trunc:i32 (AssertZext X, i8))
+  SDValue WiderAssertZext = N0.getOperand(0);
+  EVT WiderVT = cast<VTSDNode>(WiderAssertZext->getOperand(1))->getVT();
+
+  if (NarrowerVT.bitsLT(WiderVT)) {
+    SDValue NewAssertZext = DAG.getNode(
+        ISD::AssertZext, SDLoc(N), WiderAssertZext.getValueType(),
+        WiderAssertZext.getOperand(0), DAG.getValueType(NarrowerVT));
+    return DAG.getNode(ISD::TRUNCATE, SDLoc(N), N->getValueType(0),
+                       NewAssertZext);
+  }
+
+  return SDValue();
+}
+
 SDValue  MipsTargetLowering::PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI)
   const {
   SelectionDAG &DAG = DCI.DAG;
   unsigned Opc = N->getOpcode();
 
   switch (Opc) {
   default: break;
   case ISD::SDIVREM:
   case ISD::UDIVREM:
     return performDivRemCombine(N, DAG, DCI, Subtarget);
   case ISD::SELECT:
     return performSELECTCombine(N, DAG, DCI, Subtarget);
   case MipsISD::CMovFP_F:
   case MipsISD::CMovFP_T:
     return performCMovFPCombine(N, DAG, DCI, Subtarget);
   case ISD::AND:
     return performANDCombine(N, DAG, DCI, Subtarget);
   case ISD::OR:
     return performORCombine(N, DAG, DCI, Subtarget);
   case ISD::ADD:
     return performADDCombine(N, DAG, DCI, Subtarget);
+  case ISD::AssertZext:
+    return performAssertZextCombine(N, DAG, DCI, Subtarget);
   }
 
   return SDValue();
 }
 
 bool MipsTargetLowering::isCheapToSpeculateCttz() const {
   return Subtarget.hasMips32();
 }

llvm/trunk/test/CodeGen/Mips/assertzext-trunc.ll

+; RUN: llc < %s -march=mips64 -mcpu=mips3 | FileCheck %s \
+; RUN:   -check-prefix=ALL -check-prefix=PRE-R6
+; RUN: llc < %s -march=mips64 -mcpu=mips4 | FileCheck %s \
+; RUN:   -check-prefix=ALL -check-prefix=PRE-R6
+; RUN: llc < %s -march=mips64 -mcpu=mips64 | FileCheck %s \
+; RUN:   -check-prefix=ALL -check-prefix=PRE-R6
+; RUN: llc < %s -march=mips64 -mcpu=mips64r2 | FileCheck %s \
+; RUN:   -check-prefix=ALL -check-prefix=PRE-R6
+; RUN: llc < %s -march=mips64 -mcpu=mips64r3 | FileCheck %s \
+; RUN:   -check-prefix=ALL -check-prefix=PRE-R6
+; RUN: llc < %s -march=mips64 -mcpu=mips64r5 | FileCheck %s \
+; RUN:   -check-prefix=ALL -check-prefix=PRE-R6
+; RUN: llc < %s -march=mips64 -mcpu=mips64r6 | FileCheck %s \
+; RUN:   -check-prefix=ALL -check-prefix=R6
+
+; Check that we don't emit redundant SLLs for sequences of
+; (AssertZext:i32 (trunc:i32 (AssertZext:i64 X, i32)), i8)
+define zeroext i8 @udiv_i8(i8 zeroext %a, i8 zeroext %b) {
+entry:
+; ALL-LABEL: udiv_i8:
+
+  ; PRE-R6-NOT:   sll     {{.*}}
+  ; PRE-R6:       divu    $zero, $4, $5
+  ; PRE-R6:       teq     $5, $zero, 7
+  ; PRE-R6:       mflo    $2
+
+  ; R6-NOT:       sll     {{.*}}
+  ; R6:           divu    $2, $4, $5
+  ; R6:           teq     $5, $zero, 7
+
+  %r = udiv i8 %a, %b
+  ret i8 %r
+}
+
+; Check that we do sign-extend when we have a (trunc:i32 (AssertZext:i64 X, i32))
+define i64 @foo1(i64 zeroext %var) {
+entry:
+; ALL-LABEL: foo1:
+
+  %shr = lshr i64 %var, 32
+  %cmp = icmp eq i64 %shr, 0
+  br i1 %cmp, label %if.end6, label %if.then
+
+  ; ALL:    dsrl   $[[T0:[0-9]+]], $4, 32
+  ; ALL:    sll    $[[T1:[0-9]+]], $[[T0]], 0
+  if.then:                                          ; preds = %entry
+  %conv = trunc i64 %shr to i32
+  %cmp2 = icmp slt i32 %conv, 0
+  br i1 %cmp2, label %if.then4, label %if.else
+
+  if.then4:                                         ; preds = %if.then
+  %add = add i64 %var, 16
+  br label %if.end6
+
+  if.else:                                          ; preds = %if.then
+  %add5 = add i64 %var, 32
+  br label %if.end6
+
+  if.end6:                                          ; preds = %entry, %if.then4, %if.else
+  %var.addr.0 = phi i64 [ %add, %if.then4 ], [ %add5, %if.else ], [ %var, %entry ]
+  ret i64 %var.addr.0
+}

llvm/trunk/test/CodeGen/Mips/divrem.ll

 ; ACC64:         mfhi $2
 
 ; ALL: .end srem1
 
   %rem = srem i32 %a0, %a1
   ret i32 %rem
 }
 
-define i32 @udiv1(i32 zeroext %a0, i32 zeroext %a1) nounwind readnone {
+define i32 @udiv1(i32 signext %a0, i32 signext %a1) nounwind readnone {
 entry:
 ; ALL-LABEL: udiv1:
 
 ; ACC32:         divu $zero, $4, $5
 ; ACC32-TRAP:    teq $5, $zero, 7
 
 ; ACC64:         divu $zero, $4, $5
 ; ACC64-TRAP:    teq $5, $zero, 7

 ; ACC32:         mflo $2
 ; ACC64:         mflo $2
 
 ; ALL: .end udiv1
   %div = udiv i32 %a0, %a1
   ret i32 %div
 }
 
-define i32 @urem1(i32 zeroext %a0, i32 zeroext %a1) nounwind readnone {
+define i32 @urem1(i32 signext %a0, i32 signext %a1) nounwind readnone {
 entry:
 ; ALL-LABEL: urem1:
 
 ; ACC32:         divu $zero, $4, $5
 ; ACC32-TRAP:    teq $5, $zero, 7
 
 ; ACC64:         divu $zero, $4, $5
 ; ACC64-TRAP:    teq $5, $zero, 7

 ; ALL: .end sdivrem1
 
   %rem = srem i32 %a0, %a1
   store i32 %rem, i32* %r, align 4
   %div = sdiv i32 %a0, %a1
   ret i32 %div
 }
 
-define i32 @udivrem1(i32 zeroext %a0, i32 zeroext %a1, i32* nocapture %r) nounwind {
+define i32 @udivrem1(i32 signext %a0, i32 signext %a1, i32* nocapture %r) nounwind {
 entry:
 ; ALL-LABEL: udivrem1:
 
 ; ACC32:         divu $zero, $4, $5
 ; ACC32-TRAP:    teq $5, $zero, 7
 ; NOCHECK-NOT:   teq
 ; ACC32:         mflo $2
 ; ACC32:         mfhi $[[R0:[0-9]+]]

llvm/trunk/test/CodeGen/Mips/octeon_popcnt.ll

define i16 @cnt16(i16 %x) nounwind readnone {
   ret i16 %cnt
 ; OCTEON-LABEL: cnt16:
 ; OCTEON: jr   $ra
 ; OCTEON: pop  $2, [[R1:\$[0-9]+]]
 ; MIPS64-LABEL: cnt16:
 ; MIPS64-NOT: pop
 }
 
-define i32 @cnt32(i32 zeroext %x) nounwind readnone {
+define i32 @cnt32(i32 signext %x) nounwind readnone {
   %cnt = tail call i32 @llvm.ctpop.i32(i32 %x)
   ret i32 %cnt
 ; OCTEON-LABEL: cnt32:
 ; OCTEON: jr   $ra
 ; OCTEON: pop  $2, $4
 ; MIPS64-LABEL: cnt32:
 ; MIPS64-NOT: pop
 }