[MIPS] For vectors, select `add %x, C` as `sub %x, -C` if it results in inline immediate

[lebedev.ri]

Summary

As discussed in https://reviews.llvm.org/D62341#1515637,
for MIPS add %x, -1 isn't optimal. Unlike X86 there
are no fastpaths to matearialize such -1/1 vector constants,
and sub %x, 1 results in better codegen,
so undo canonicalization

[Petar.Avramovic]

This patch targets very specific values(1,-1) but there are more. The trick for D62341 is that msa vector add/sub imm accept 5 bit unsigned imm, so it is ok to switch from add imm to sub imm (also sub to add) if it changes imm form negative to positive. I think it is cleanest to have some hook and ask target if it would like to transform sub into add (add to sub) with imm.

[lebedev.ri]

Thank you for taking a look.

In D66805#1647228, @Petar.Avramovic wrote:

This patch targets very specific values(1,-1) but there are more. The trick for D62341 is that msa vector add/sub imm accept 5 bit unsigned imm, so it is ok to switch from add imm to sub imm (also sub to add) if it changes imm form negative to positive.

Yeah, i have found that in ISA manual since posting the patch.

I think it is cleanest to have some hook and ask target if it would like to transform sub into add (add to sub) with imm.

I understand where this is coming from but no, that will not be ok.
The whole point of D62341 is that we really don't want sub %x, C in DAGCombine,
so while we could hide it behind target hook, that defies the whole purpose.
So this needs to be undone per-target in *ISelDAGToDAG.cpp.

[Petar.Avramovic]

Oh, I see. Then we have to undo combines here. Let's what for Simon.

[lebedev.ri]

Forgot to mention, this sub %X, C -> add %X, -C transform is already always being performed
by InstCombine in middle-end, so such undo transform is needed regardless of what DAGCombine does.

[lebedev.ri]

Generalize the check, do not limit the transform to -1 specifically,
but rather all splat immediates if negating results in inline immediate (5-bit unsigned)

[lebedev.ri]

Rebased.

[atanasyan]

LGTM

[lebedev.ri]

In D66805#1655408, @atanasyan wrote:

LGTM

Thank you for the review!

[lebedev.ri]

llvm/test/CodeGen/Mips/msa/arithmetic.ll

220–241

Hm, this one didn't get recovered by the patch.

[atanasyan]

llvm/test/CodeGen/Mips/msa/arithmetic.ll

220–241

I saw this regression. Unfortunately I could not quickly create a fix for it. As far as I remember, the problem is in this statement auto *BVN = dyn_cast<BuildVectorSDNode>(C). In @sub_v2i64_i the second operand (i.e. C) is a bitcast and dyn_cast<BuildVectorSDNode> returns zero. Right now I do not have a time to dig it. Maybe next week.

[lebedev.ri]

llvm/test/CodeGen/Mips/msa/arithmetic.ll

220–241

Honestly i didn't notice that it didn't address all of the patterns until now.
We get:

t10: v2i64 = add t7, t16
  t7: v2i64,ch = load<(load 16 from %ir.a)> t0, t4, undef:i32
    t4: i32,ch = CopyFromReg t0, Register:i32 %1
      t3: i32 = Register %1
    t6: i32 = undef
  t16: v2i64 = bitcast t15
    t15: v4i32 = BUILD_VECTOR Constant:i32<-1>, Constant:i32<-31>, Constant:i32<-1>, Constant:i32<-31>
      t14: i32 = Constant<-1>
      t13: i32 = Constant<-31>
      t14: i32 = Constant<-1>
      t13: i32 = Constant<-31>

So yes, this because of a bitcast.
Even if we look past it, isConstantSplat() will say "no, not a splat".
This likely means something else other than isConstantSplat() should be used here.

llvm/lib/Target/Mips/MipsISelDAGToDAG.h

private:
   virtual bool selectVSplatUimmInvPow2(SDValue N, SDValue &Imm) const;
   /// Select constant vector splats whose value is a run of set bits
   /// ending at the most significant bit
   virtual bool selectVSplatMaskL(SDValue N, SDValue &Imm) const;
   /// Select constant vector splats whose value is a run of set bits
   /// starting at bit zero.
   virtual bool selectVSplatMaskR(SDValue N, SDValue &Imm) const;
 
+  /// Convert vector addition with vector subtraction if that allows to encode
+  /// constant as an immediate and thus avoid extra 'ldi' instruction.
+  /// add X, <-1, -1...> --> sub X, <1, 1...>
+  bool selectVecAddAsVecSubIfProfitable(SDNode *Node);
+
   void Select(SDNode *N) override;
 
   virtual bool trySelect(SDNode *Node) = 0;
 
   // getImm - Return a target constant with the specified value.
   inline SDValue getImm(const SDNode *Node, uint64_t Imm) {
     return CurDAG->getTargetConstant(Imm, SDLoc(Node), Node->getValueType(0));
   }

llvm/lib/Target/Mips/MipsISelDAGToDAG.cpp

bool MipsDAGToDAGISel::selectVSplatMaskL(SDValue N, SDValue &Imm) const {
   return false;
 }
 
 bool MipsDAGToDAGISel::selectVSplatMaskR(SDValue N, SDValue &Imm) const {
   llvm_unreachable("Unimplemented function.");
   return false;
 }
 
+/// Convert vector addition with vector subtraction if that allows to encode
+/// constant as an immediate and thus avoid extra 'ldi' instruction.
+/// add X, <-1, -1...> --> sub X, <1, 1...>
+bool MipsDAGToDAGISel::selectVecAddAsVecSubIfProfitable(SDNode *Node) {
+  assert(Node->getOpcode() == ISD::ADD && "Should only get 'add' here.");
+
+  EVT VT = Node->getValueType(0);
+  assert(VT.isVector() && "Should only be called for vectors.");
+
+  SDValue X = Node->getOperand(0);
+  SDValue C = Node->getOperand(1);
+
+  auto *BVN = dyn_cast<BuildVectorSDNode>(C);
+  if (!BVN)
+    return false;
+
+  APInt SplatValue, SplatUndef;
+  unsigned SplatBitSize;
+  bool HasAnyUndefs;
+
+  if (!BVN->isConstantSplat(SplatValue, SplatUndef, SplatBitSize, HasAnyUndefs,
+                            8, !Subtarget->isLittle()))
+    return false;
+
+  auto IsInlineConstant = [](const APInt &Imm) { return Imm.isIntN(5); };
+
+  if (IsInlineConstant(SplatValue))
+    return false; // Can already be encoded as an immediate.
+
+  APInt NegSplatValue = 0 - SplatValue;
+  if (!IsInlineConstant(NegSplatValue))
+    return false; // Even if we negate it it won't help.
+
+  SDLoc DL(Node);
+
+  SDValue NegC = CurDAG->FoldConstantArithmetic(
+      ISD::SUB, DL, VT, CurDAG->getConstant(0, DL, VT).getNode(), C.getNode());
+  assert(NegC && "Constant-folding failed!");
+  SDValue NewNode = CurDAG->getNode(ISD::SUB, DL, VT, X, NegC);
+
+  ReplaceNode(Node, NewNode.getNode());
+  SelectCode(NewNode.getNode());
+  return true;
+}
+
 /// Select instructions not customized! Used for
 /// expanded, promoted and normal instructions
 void MipsDAGToDAGISel::Select(SDNode *Node) {
   unsigned Opcode = Node->getOpcode();
 
   // If we have a custom node, we already have selected!
   if (Node->isMachineOpcode()) {
     LLVM_DEBUG(errs() << "== "; Node->dump(CurDAG); errs() << "\n");
     Node->setNodeId(-1);
     return;
   }
 
   // See if subclasses can handle this node.
   if (trySelect(Node))
     return;
 
   switch(Opcode) {
   default: break;
 
+  case ISD::ADD:
+    if (Node->getSimpleValueType(0).isVector() &&
+        selectVecAddAsVecSubIfProfitable(Node))
+      return;
+    break;
+
   // Get target GOT address.
   case ISD::GLOBAL_OFFSET_TABLE:
     ReplaceNode(Node, getGlobalBaseReg());
     return;
 
 #ifndef NDEBUG
   case ISD::LOAD:
   case ISD::STORE:

llvm/test/CodeGen/Mips/msa/arithmetic.ll

; ALL-NEXT:    st.d $w0, 0($4)
   store <2 x i64> %3, <2 x i64>* %c
   ret void
 }
 
 define void @sub_v16i8_i(<16 x i8>* %c, <16 x i8>* %a) nounwind {
 ; ALL-LABEL: sub_v16i8_i:
 ; ALL:       # %bb.0:
 ; ALL-NEXT:    ld.b $w0, 0($5)
-; ALL-NEXT:    ldi.b $w1, -1
-; ALL-NEXT:    addv.b $w0, $w0, $w1
+; ALL-NEXT:    subvi.b $w0, $w0, 1
 ; ALL-NEXT:    jr $ra
 ; ALL-NEXT:    st.b $w0, 0($4)
   %1 = load <16 x i8>, <16 x i8>* %a
   %2 = sub <16 x i8> %1, <i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1,
               i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1>
   store <16 x i8> %2, <16 x i8>* %c
   ret void
 }
 
 define void @sub_v8i16_i(<8 x i16>* %c, <8 x i16>* %a) nounwind {
 ; ALL-LABEL: sub_v8i16_i:
 ; ALL:       # %bb.0:
-; ALL-NEXT:    ldi.b $w0, -1
-; ALL-NEXT:    ld.h $w1, 0($5)
-; ALL-NEXT:    addv.h $w0, $w1, $w0
+; ALL-NEXT:    ld.h $w0, 0($5)
+; ALL-NEXT:    subvi.h $w0, $w0, 1
 ; ALL-NEXT:    jr $ra
 ; ALL-NEXT:    st.h $w0, 0($4)
   %1 = load <8 x i16>, <8 x i16>* %a
   %2 = sub <8 x i16> %1, <i16 1, i16 1, i16 1, i16 1,
               i16 1, i16 1, i16 1, i16 1>
   store <8 x i16> %2, <8 x i16>* %c
   ret void
 }
 
 define void @sub_v4i32_i(<4 x i32>* %c, <4 x i32>* %a) nounwind {
 ; ALL-LABEL: sub_v4i32_i:
 ; ALL:       # %bb.0:
-; ALL-NEXT:    ldi.b $w0, -1
-; ALL-NEXT:    ld.w $w1, 0($5)
-; ALL-NEXT:    addv.w $w0, $w1, $w0
+; ALL-NEXT:    ld.w $w0, 0($5)
+; ALL-NEXT:    subvi.w $w0, $w0, 1
 ; ALL-NEXT:    jr $ra
 ; ALL-NEXT:    st.w $w0, 0($4)
   %1 = load <4 x i32>, <4 x i32>* %a
   %2 = sub <4 x i32> %1, <i32 1, i32 1, i32 1, i32 1>
   store <4 x i32> %2, <4 x i32>* %c
   ret void
 }
 
 define void @sub_v2i64_i(<2 x i64>* %c, <2 x i64>* %a) nounwind {
 ; MIPS-LABEL: sub_v2i64_i:
 ; MIPS:       # %bb.0:
 ; MIPS-NEXT:    ldi.b $w0, -1
 ; MIPS-NEXT:    shf.w $w0, $w0, 177
 ; MIPS-NEXT:    ld.d $w1, 0($5)
 ; MIPS-NEXT:    addv.d $w0, $w1, $w0
 ; MIPS-NEXT:    jr $ra
 ; MIPS-NEXT:    st.d $w0, 0($4)
 ;
 ; MIPSEL-LABEL: sub_v2i64_i:
 ; MIPSEL:       # %bb.0:
 ; MIPSEL-NEXT:    ldi.b $w0, -1
 ; MIPSEL-NEXT:    ld.d $w1, 0($5)
 ; MIPSEL-NEXT:    addv.d $w0, $w1, $w0
 ; MIPSEL-NEXT:    jr $ra
 ; MIPSEL-NEXT:    st.d $w0, 0($4)
   %1 = load <2 x i64>, <2 x i64>* %a
   %2 = sub <2 x i64> %1, <i64 1, i64 1>
   store <2 x i64> %2, <2 x i64>* %c
   ret void
 }
 
 define void @mul_v16i8(<16 x i8>* %c, <16 x i8>* %a, <16 x i8>* %b) nounwind {
 ; ALL-LABEL: mul_v16i8:
 ; ALL:       # %bb.0:
 ; ALL-NEXT:    ld.b $w0, 0($6)
 ; ALL-NEXT:    ld.b $w1, 0($5)
 ; ALL-NEXT:    mulv.b $w0, $w1, $w0
 ; ALL-NEXT:    jr $ra

llvm/test/CodeGen/Mips/msa/i5-s.ll

 declare <8 x i16> @llvm.mips.subvi.h(<8 x i16>, i32) nounwind
 
 @llvm_mips_subvi_w_ARG1 = global <4 x i32> <i32 0, i32 1, i32 2, i32 3>, align 16
 @llvm_mips_subvi_w_RES  = global <4 x i32> <i32 0, i32 0, i32 0, i32 0>, align 16
 
 define void @llvm_mips_subvi_w_test() nounwind {
 ; ALL-LABEL: llvm_mips_subvi_w_test:
 ; ALL:       # %bb.0: # %entry
-; ALL-NEXT:    lui $1, %hi(llvm_mips_subvi_w_ARG1)
-; ALL-NEXT:    addiu $1, $1, %lo(llvm_mips_subvi_w_ARG1)
-; ALL-NEXT:    ld.w $w0, 0($1)
-; ALL-NEXT:    ldi.w $w1, -14
-; ALL-NEXT:    addv.w $w0, $w0, $w1
 ; ALL-NEXT:    lui $1, %hi(llvm_mips_subvi_w_RES)
 ; ALL-NEXT:    addiu $1, $1, %lo(llvm_mips_subvi_w_RES)
+; ALL-NEXT:    lui $2, %hi(llvm_mips_subvi_w_ARG1)
+; ALL-NEXT:    addiu $2, $2, %lo(llvm_mips_subvi_w_ARG1)
+; ALL-NEXT:    ld.w $w0, 0($2)
+; ALL-NEXT:    subvi.w $w0, $w0, 14
 ; ALL-NEXT:    jr $ra
 ; ALL-NEXT:    st.w $w0, 0($1)
 entry:
   %0 = load <4 x i32>, <4 x i32>* @llvm_mips_subvi_w_ARG1
   %1 = tail call <4 x i32> @llvm.mips.subvi.w(<4 x i32> %0, i32 14)
   store <4 x i32> %1, <4 x i32>* @llvm_mips_subvi_w_RES
   ret void
 }