[Mips] Use UADDO/ADDCARRY instead of ADDC/ADDE

[deadalnix]

Summary

This changes the DAG to DAG to lower from UADDO/ADDCARRY. It involves some trickery to make sure we do not materialize the carry when it comes from ADDSC.

The spec doesn't mention if ADDWC clear with 20, however, code clearing it was removed as The carry now always comes from a ADDSC and previous version of the code did not seems to worry about bit 20 being set in that case, so my assumption is that this is the proper thing to do.

[sdardis]

I take it that this patch is dependent on D47703 ?

[deadalnix]

Absolutely.

[sdardis]

The legalization of unsigned i128 addition (rL334094 for the test) looks strange to me in that the determination of the overflow from the first addition is done with setccs. They appear to be originating from the expansion of setcc of an illegal type.

I'm not entirely convinced on performing addsc/addwc sequences over addsc/(multiple addwc) sequences. The overflow bit for the addwc has to be cleared after reading it so that the next addwc in either type of expansion delivers the correct result. At which point you might as well shift that bit into the carry bit in the dsp control register and perform addwc again.

Some additional comments inline.

lib/Target/Mips/MipsSEISelDAGToDAG.cpp

255

I realised that I got this wrong when I wrote it. This code should be using 0x1f to read the entire register.

295

This has to be materialized into a register as addsc doesn't have an immediate form, use ADDiu, -1 to materialize it.

310

You also need to clear bit 20 in the dsp control register after performing a addwc. On page 40 of the MIPS DSP AFP (MD00374-2B-MIPS32DSP-AFP-03.01.pdf) , it notes that the over/underflow flags are sticky.

[deadalnix]

lib/Target/Mips/MipsSEISelDAGToDAG.cpp

310

Question is, does addsc clean the flag register ? If yes, then we are good, if not, then existing code is broken as well.

[sdardis]

lib/Target/Mips/MipsSEISelDAGToDAG.cpp

310

By the spec from my reading, addsc only writes the carry bit (bit 13) on every execution and bit 20 is untouched.

[atanasyan]

I do not see any test cases in this patch. Is it intended?

[deadalnix]

@atanasyan The behavior is not supposed to change in any way, so test cases should not change. However, there are doubt about semantic for which there is no test case today.

lib/Target/Mips/MicroMips32r6InstrInfo.td

 //===----------------------------------------------------------------------===//
 //
 // MicroMips arbitrary patterns that map to one or more instructions
 //
 //===----------------------------------------------------------------------===//
 
 def : MipsPat<(store GPRMM16:$src, addrimm4lsl2:$addr),
               (SW16_MMR6 GPRMM16:$src, addrimm4lsl2:$addr)>, ISA_MICROMIPS32R6;
-def : MipsPat<(subc GPR32:$lhs, GPR32:$rhs),
-              (SUBU_MMR6 GPR32:$lhs, GPR32:$rhs)>, ISA_MICROMIPS32R6;
 
 def : MipsPat<(select i32:$cond, i32:$t, i32:$f),
               (OR_MM (SELNEZ_MMR6 i32:$t, i32:$cond),
                      (SELEQZ_MMR6 i32:$f, i32:$cond))>,
               ISA_MICROMIPS32R6;
 def : MipsPat<(select i32:$cond, i32:$t, immz),
               (SELNEZ_MMR6 i32:$t, i32:$cond)>,
               ISA_MICROMIPS32R6;

lib/Target/Mips/MicroMipsInstrInfo.td

def : MipsPat<(store GPRMM16:$src, addrimm4lsl2:$addr),
                 (SW16_MM GPRMM16:$src, addrimm4lsl2:$addr)>;
   def : MipsPat<(store GPR32:$src, addr:$addr),
                 (SW_MM GPR32:$src, addr:$addr)>;
 
   def : MipsPat<(load addrimm4lsl2:$addr),
                 (LW16_MM addrimm4lsl2:$addr)>;
   def : MipsPat<(load addr:$addr),
                 (LW_MM addr:$addr)>;
-  def : MipsPat<(subc GPR32:$lhs, GPR32:$rhs),
-                (SUBu_MM GPR32:$lhs, GPR32:$rhs)>;
 
   def : MipsPat<(i32 (extloadi1  addr:$src)), (LBu_MM addr:$src)>,
         ISA_MICROMIPS;
 
   def : MipsPat<(i32 (extloadi8  addr:$src)), (LBu_MM addr:$src)>,
         ISA_MICROMIPS;
 
   def : MipsPat<(i32 (extloadi16 addr:$src)), (LHu_MM addr:$src)>,

lib/Target/Mips/Mips64InstrInfo.td

 
 // Sign extend in register
 def : MipsPat<(i64 (sext_inreg GPR64:$src, i32)),
               (SLL64_64 GPR64:$src)>;
 
 // bswap MipsPattern
 def : MipsPat<(bswap GPR64:$rt), (DSHD (DSBH GPR64:$rt))>, ISA_MIPS64R2;
 
-// Carry pattern
-let AdditionalPredicates = [NotInMicroMips] in {
-  def : MipsPat<(subc GPR64:$lhs, GPR64:$rhs),
-                (DSUBu GPR64:$lhs, GPR64:$rhs)>;
-  def : MipsPat<(addc GPR64:$lhs, GPR64:$rhs),
-                (DADDu GPR64:$lhs, GPR64:$rhs)>, ASE_NOT_DSP;
-  def : MipsPat<(addc GPR64:$lhs, immSExt16:$imm),
-                (DADDiu GPR64:$lhs, imm:$imm)>, ASE_NOT_DSP;
-}
-
 // Octeon bbit0/bbit1 MipsPattern
 def : MipsPat<(brcond (i32 (seteq (and i64:$lhs, PowerOf2LO:$mask), 0)), bb:$dst),
               (BBIT0 i64:$lhs, (Log2LO PowerOf2LO:$mask), bb:$dst)>, ASE_MIPS64_CNMIPS;
 def : MipsPat<(brcond (i32 (seteq (and i64:$lhs, PowerOf2HI:$mask), 0)), bb:$dst),
               (BBIT032 i64:$lhs, (Log2HI PowerOf2HI:$mask), bb:$dst)>, ASE_MIPS64_CNMIPS;
 def : MipsPat<(brcond (i32 (setne (and i64:$lhs, PowerOf2LO:$mask), 0)), bb:$dst),
               (BBIT1 i64:$lhs, (Log2LO PowerOf2LO:$mask), bb:$dst)>, ASE_MIPS64_CNMIPS;
 def : MipsPat<(brcond (i32 (setne (and i64:$lhs, PowerOf2HI:$mask), 0)), bb:$dst),

lib/Target/Mips/MipsDSPInstrInfo.td

 def : DSPBinPat<SUBQ_PH, v2i16, sub>;
 def : DSPBinPat<MUL_PH, v2i16, int_mips_mul_ph, HasDSPR2>;
 def : DSPBinPat<MUL_PH, v2i16, mul, HasDSPR2>;
 def : DSPBinPat<ADDU_QB, v4i8, int_mips_addu_qb>;
 def : DSPBinPat<ADDU_QB, v4i8, add>;
 def : DSPBinPat<SUBU_QB, v4i8, int_mips_subu_qb>;
 def : DSPBinPat<SUBU_QB, v4i8, sub>;
 def : DSPBinPat<ADDSC, i32, int_mips_addsc>;
-def : DSPBinPat<ADDSC, i32, addc>;
 def : DSPBinPat<ADDWC, i32, int_mips_addwc>;
-def : DSPBinPat<ADDWC, i32, adde>;
 
 // Shift immediate patterns.
 class DSPShiftPat<Instruction Inst, ValueType ValTy, SDPatternOperator Node,
                   SDPatternOperator Imm, Predicate Pred = HasDSP> :
   DSPPat<(Node ValTy:$a, Imm:$shamt), (Inst ValTy:$a, Imm:$shamt), Pred>;
 
 def : DSPShiftPat<SHLL_PH, v2i16, MipsSHLL_DSP, imm>;
 def : DSPShiftPat<SHRA_PH, v2i16, MipsSHRA_DSP, imm>;

lib/Target/Mips/MipsInstrInfo.td

 // Small immediates
 def : MipsPat<(VT ORiPred:$imm), (ORiOp ZEROReg, imm:$imm)>;
 def : MipsPat<(VT immSExt16:$imm), (ADDiuOp ZEROReg, imm:$imm)>;
 }
 
 let AdditionalPredicates = [NotInMicroMips] in
   defm : MaterializeImms<i32, ZERO, ADDiu, LUi, ORi>;
 
-// Carry MipsPatterns
-let AdditionalPredicates = [NotInMicroMips] in {
-  def : MipsPat<(subc GPR32:$lhs, GPR32:$rhs),
-                (SUBu GPR32:$lhs, GPR32:$rhs)>;
-}
-def : MipsPat<(addc GPR32:$lhs, GPR32:$rhs),
-              (ADDu GPR32:$lhs, GPR32:$rhs)>, ASE_NOT_DSP;
-def : MipsPat<(addc  GPR32:$src, immSExt16:$imm),
-              (ADDiu GPR32:$src, imm:$imm)>, ASE_NOT_DSP;
-
 // Support multiplication for pre-Mips32 targets that don't have
 // the MUL instruction.
 def : MipsPat<(mul GPR32:$lhs, GPR32:$rhs),
               (PseudoMFLO (PseudoMULT GPR32:$lhs, GPR32:$rhs))>,
       ISA_MIPS1_NOT_32R6_64R6;
 
 // SYNC
 def : MipsPat<(MipsSync (i32 immz)),

lib/Target/Mips/MipsSEISelDAGToDAG.h

private:
   unsigned getMSACtrlReg(const SDValue RegIdx) const;
 
   bool replaceUsesWithZeroReg(MachineRegisterInfo *MRI, const MachineInstr&);
 
   std::pair<SDNode *, SDNode *> selectMULT(SDNode *N, unsigned Opc,
                                            const SDLoc &dl, EVT Ty, bool HasLo,
                                            bool HasHi);
 
-  void selectAddE(SDNode *Node, const SDLoc &DL) const;
+  void selectADDCARRY(SDNode *Node, const SDLoc &DL);
 
   bool selectAddrFrameIndex(SDValue Addr, SDValue &Base, SDValue &Offset) const;
   bool selectAddrFrameIndexOffset(SDValue Addr, SDValue &Base, SDValue &Offset,
                                   unsigned OffsetBits,
                                   unsigned ShiftAmount) const;
 
   bool selectAddrRegImm(SDValue Addr, SDValue &Base,
                         SDValue &Offset) const override;

lib/Target/Mips/MipsSEISelDAGToDAG.cpp

for (auto &MI: MBB) {
         break;
       default:
         replaceUsesWithZeroReg(MRI, MI);
       }
     }
   }
 }
 
-void MipsSEDAGToDAGISel::selectAddE(SDNode *Node, const SDLoc &DL) const {
-  SDValue InFlag = Node->getOperand(2);
-  unsigned Opc = InFlag.getOpcode();
-  SDValue LHS = Node->getOperand(0), RHS = Node->getOperand(1);
-  EVT VT = LHS.getValueType();
+static SDValue extractCarryFlag(SDNode *N, unsigned Position,
+                                SelectionDAG *DAG) {
+  SDLoc DL(N);
+
+  SDValue CstOne = DAG->getTargetConstant(1, DL, MVT::i32);
+  SDValue OuFlag = DAG->getTargetConstant(Position, DL, MVT::i32);
+
+  // Extract the value of the carry flag. The usage of 1 here with
+  // MipsISD::RDDSP corresponds to reading/writing the entire control
+  // register to a GPR.
+  SDNode *DSPCtrlField =
+      DAG->getMachineNode(Mips::RDDSP, DL, MVT::i32, MVT::Glue, CstOne,
+                          SDValue(N, 1));
 
-  // In the base case, we can rely on the carry bit from the addsc
-  // instruction.
-  if (Opc == ISD::ADDC) {
-    SDValue Ops[3] = {LHS, RHS, InFlag};
-    CurDAG->SelectNodeTo(Node, Mips::ADDWC, VT, MVT::Glue, Ops);
-    return;
-  }
+  SDNode *CarryNode =
+      DAG->getMachineNode(Mips::EXT, DL, MVT::i32, SDValue(DSPCtrlField, 0),
+                         OuFlag, CstOne);
+  return SDValue(CarryNode, 0);
 
-  assert(Opc == ISD::ADDE && "ISD::ADDE not in a chain of ADDE nodes!");
-
-  // The more complex case is when there is a chain of ISD::ADDE nodes like:
-  // (adde (adde (adde (addc a b) c) d) e).
-  //
-  // The addwc instruction does not write to the carry bit, instead it writes
-  // to bit 20 of the dsp control register. To match this series of nodes, each
-  // intermediate adde node must be expanded to write the carry bit before the
-  // addition.
-
-  // Start by reading the overflow field for addsc and moving the value to the
-  // carry field. The usage of 1 here with MipsISD::RDDSP / Mips::WRDSP
-  // corresponds to reading/writing the entire control register to/from a GPR.
-
-  SDValue CstOne = CurDAG->getTargetConstant(1, DL, MVT::i32);
-
-  SDValue OuFlag = CurDAG->getTargetConstant(20, DL, MVT::i32);
-
-  SDNode *DSPCtrlField =
-      CurDAG->getMachineNode(Mips::RDDSP, DL, MVT::i32, MVT::Glue, CstOne, InFlag);
+void MipsSEDAGToDAGISel::selectADDCARRY(SDNode *Node, const SDLoc &DL) {
+  SDValue LHS = Node->getOperand(0);
+  SDValue RHS = Node->getOperand(1);
+  SDValue CarryIn = Node->getOperand(2);
 
-  SDNode *Carry = CurDAG->getMachineNode(
-      Mips::EXT, DL, MVT::i32, SDValue(DSPCtrlField, 0), OuFlag, CstOne);
+  EVT VT = LHS.getValueType();
 
-  SDValue Ops[4] = {SDValue(DSPCtrlField, 0),
-                    CurDAG->getTargetConstant(6, DL, MVT::i32), CstOne,
-                    SDValue(Carry, 0)};
-  SDNode *DSPCFWithCarry = CurDAG->getMachineNode(Mips::INS, DL, MVT::i32, Ops);
+  SDNode *CarryNode;
+  if (CarryIn.getOpcode() == ISD::UADDO && CarryIn.getResNo() == 1 &&
+      CarryIn.hasOneUse()) {
+    // In the base case, we can rely on the carry bit from the addsc
+    // instruction.
+    SDValue CarryLHS = CarryIn.getOperand(0);
+    SDValue CarryRHS = CarryIn.getOperand(1);
 
-  // My reading of the MIPS DSP 3.01 specification isn't as clear as I
-  // would like about whether bit 20 always gets overwritten by addwc.
-  // Hence take an extremely conservative view and presume it's sticky. We
-  // therefore need to clear it.
+    CarryNode =
+        CurDAG->getMachineNode(Mips::ADDSC, SDLoc(CarryIn),
+                               CarryIn.getValueType(), MVT::Glue,
+                               CarryLHS, CarryRHS);
+
+    // Also replace add result to avoid selecting that node twice.
+    SDValue UAddOResult = CarryIn.getValue(0);
+    if (!UAddOResult.use_empty())
+      ReplaceUses(UAddOResult, SDValue(CarryNode, 0));
+  } else {
+    // In more coplex cases, we recreate the carry using (ADDSC Carry, -1).
+    EVT CarryVT = CarryIn.getValueType();
+    SDValue CstAllOnes = CurDAG->getTargetConstant(-1, DL, CarryVT);
+    CarryNode = CurDAG->getMachineNode(Mips::ADDSC, DL, CarryVT, MVT::Glue,
+                                       CarryIn, CstAllOnes);
+  }
 
-  SDValue Zero = CurDAG->getRegister(Mips::ZERO, MVT::i32);
+  SDValue Ops[3] = {LHS, RHS, SDValue(CarryNode, 1)};
+  SDNode *Result =
+      CurDAG->getMachineNode(Mips::ADDWC, DL, VT, MVT::Glue, Ops);
 
-  SDValue InsOps[4] = {Zero, OuFlag, CstOne, SDValue(DSPCFWithCarry, 0)};
-  SDNode *DSPCtrlFinal = CurDAG->getMachineNode(Mips::INS, DL, MVT::i32, InsOps);
+  if (!SDValue(Node, 0).use_empty())
+    ReplaceUses(SDValue(Node, 0), SDValue(Result, 0));
 
-  SDNode *WrDSP = CurDAG->getMachineNode(Mips::WRDSP, DL, MVT::Glue,
-                                         SDValue(DSPCtrlFinal, 0), CstOne);
+  if (!SDValue(Node, 1).use_empty()) {
+    // The addwc instruction does not write to the carry bit, instead it writes
+    // to bit 20 of the dsp control register.
+    ReplaceUses(SDValue(Node, 1), extractCarryFlag(Result, 20, CurDAG));
+  }
 
-  SDValue Operands[3] = {LHS, RHS, SDValue(WrDSP, 0)};
-  CurDAG->SelectNodeTo(Node, Mips::ADDWC, VT, MVT::Glue, Operands);
+  CurDAG->RemoveDeadNode(Node);
+  return;
 }
 
 /// Match frameindex
 bool MipsSEDAGToDAGISel::selectAddrFrameIndex(SDValue Addr, SDValue &Base,
                                               SDValue &Offset) const {
   if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr)) {
     EVT ValTy = Addr.getValueType();
 
bool MipsSEDAGToDAGISel::trySelect(SDNode *Node) {
 
   ///
   // Instruction Selection not handled by the auto-generated
   // tablegen selection should be handled here.
   ///
   switch(Opcode) {
   default: break;
 
-  case ISD::ADDE: {
-    selectAddE(Node, DL);
+  case ISD::UADDO: {
+    SDValue LHS = Node->getOperand(0);
+    SDValue RHS = Node->getOperand(1);
+
+    EVT VT = LHS.getValueType();
+
+    SDNode *Result =
+        CurDAG->getMachineNode(Mips::ADDSC, DL, VT, MVT::Glue, LHS, RHS);
+
+    if (!SDValue(Node, 0).use_empty())
+      ReplaceUses(SDValue(Node, 0), SDValue(Result, 0));
+
+    if (!SDValue(Node, 1).use_empty()) {
+      // The addsc instruction does write to the carry bit, namely, it writes
+      // to bit 6 of the dsp control register.
+      ReplaceUses(SDValue(Node, 1), extractCarryFlag(Result, 6, CurDAG));
+    }
+
+    CurDAG->RemoveDeadNode(Node);
+    return true;
+  }
+
+  case ISD::ADDCARRY: {
+    selectADDCARRY(Node, DL);
     return true;
   }
 
   case ISD::ConstantFP: {
     ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(Node);
     if (Node->getValueType(0) == MVT::f64 && CN->isExactlyValue(+0.0)) {
       if (Subtarget->isGP64bit()) {
         SDValue Zero = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), DL,

lib/Target/Mips/MipsSEISelLowering.cpp

if (Subtarget.hasDSP()) {
 
     setTargetDAGCombine(ISD::SHL);
     setTargetDAGCombine(ISD::SRA);
     setTargetDAGCombine(ISD::SRL);
     setTargetDAGCombine(ISD::SETCC);
     setTargetDAGCombine(ISD::VSELECT);
 
     if (Subtarget.hasMips32r2()) {
-      setOperationAction(ISD::ADDC, MVT::i32, Legal);
-      setOperationAction(ISD::ADDE, MVT::i32, Legal);
+      setOperationAction(ISD::UADDO, MVT::i32, Legal);
+      setOperationAction(ISD::ADDCARRY, MVT::i32, Legal);
     }
   }
 
   if (Subtarget.hasDSPR2())
     setOperationAction(ISD::MUL, MVT::v2i16, Legal);
 
   if (Subtarget.hasMSA()) {
     addMSAIntType(MVT::v16i8, &Mips::MSA128BRegClass);