[ARM] Use __rt_div functions for DIVREM on Windows

[mstorsjo]

Summary

This avoids falling back to calling out to the GCC rem functions (moddi3, umoddi3) when targeting Windows.

The rt_div functions have flipped the two arguments compared to the aeabi_divmod functions.

Contrary to the existing calls to division functions (and to what MSVC does), this doesn't add any check for division by zero (why does it have to, other than the fact that MSVC does it?)

In practice, the __rt_div family of functions check that themselves though, so I'm unsure why MSVC and clang needs to include it in the calling code.

Calls to rt_div functions for division aren't merged with calls to the same function with the same parameters for the remainder, which is more wasteful than a div + mls as before, but avoids calls to moddi3.

[rengolin]

Hi Martin,

The fact that divmod-eabi.ll changes is an indication that the interaction between the Dag nodes and the values they produce is weird. I suggest you walk through the back-end and print the Dag before and after the transformations.

One thing that, unfortunately, happens is that Div/Mod patters are passed multiple times over the same nodes, as they get converted from Div/Mod to Divmod, etc. This is particular to ARM and EABI, and may be getting in the way of your lowering. I can't imagine why, since it also returns two values, so it may be some corner case no one knew about.

divmod-eabi.ll is a good first approach to the problem, but you will probably have more corner cases, so please add them to the same file as you add a windows test to it.

cheers,
--renato

lib/Target/ARM/ARMISelLowering.cpp

959

hasDivide makes sense, but is unrelated and may break some expectations I don't know about. I'd leave it for later, since this shouldn't hit here if the sub-arch has divide anyway.

964–982

I'd have put this in a separate if block, since the function names are *all* different.

12206–12207

This is not about windows or not, it's about rt_div instead of eabi_divmod. Please, make it dependent on the RT type (not OS).

Also, this induction fiddling is confusing. The easiest thing to do is to swap the two first arguments before the loop. It's clear and precise.

[mstorsjo]

I tested to extend this by removing the current custom code for SDIV/UDIV for windows, and divmod-eabi.ll now looks better (it produces two calls to __rt_sdiv instead of three).

Previously, all divisions included a check for whether the divisor is zero (with an udf.w #349 instruction in case of a division by zero), while when I made it work in the same way as __aeabi_idivmod I don't get those.

I'll upload the updated patch for further comments and clarifications.

lib/Target/ARM/ARMISelLowering.cpp

964–982

I chose putting it here since it shares the code for all the setLibcallCallingConv below anyway, instead of duplicating all the 15 lines of shared code above and below. But you'd still prefer me to duplicate all of it including setOperationAction(), HasStandaloneRem and setLibcallCallingConv?

12206–12207

How do I find the RT type here - I didn't find it within ARMSubtarget on a quick look at least.

And how would I go about to swap the two arguments? N is a const SDNode here - is it ok to make it mutable and swap the arguments there?

[mstorsjo]

Now the output from divmod-eabi.ll makes more sense (I still need to update the test references though).

[rengolin]

Given that all of these changes are related to isTargetWindows everywhere, the assumption is that this can only work for windows. Once someone wants to use rt_div on non-Windows, we'll need to come up with a isWeirdABI which Windows and and that taget are members of, just like isEABI and others. So, for now, isWindows is ok.

Just a few more inline comments, and the tests and it should be good.

lib/Target/ARM/ARMISelLowering.cpp

964–982

Ah, makes sense. Looks good this way.

12206–12207

No, don't change the SDNode, just std::swap the two arguments in Args after the loop.

[mstorsjo]

In D24076#541117, @rengolin wrote:

Just a few more inline comments, and the tests and it should be good.

Actually, it turned out to be harder than this after all. With the current diff, div+rem gets nicely merged into one rt_sdiv call, but a lone div becomes a divsi3 instead.

Given all the changes back and forth in this area in the last year (see SVN revisions 248561, 253865, 254158, 263714 or git mirror commits 64ed61ca6b, ee5418798, 937e2d588c, a944db98cd) I'm a bit hesitant to change this further without input from @compnerd. I'll update the patch to a state which works (and doesn't produce calls to divsi3 or similar), but which doesn't merge the div+rem calls in all cases, and write a bug report for the actual issue that I'm trying to work around (LLVM producing calls to moddi3 which is unavailable on windows).

[mstorsjo]

Updated to a working patch

[mstorsjo]

Filed a plain bug report on the original issue at https://llvm.org/bugs/show_bug.cgi?id=30378 since it seems like my attempt at this won't be completable easily.

test/CodeGen/ARM/divmod-eabi.ll

159 ↗

(On Diff #71309)

Here, the old test reference even shows a call to __moddi3, which is not available on ARM/Windows.

[rengolin]

Right, the change now looks good, but I'll let @compnerd approve, since I'm not that well versed in the Windows ABI.

[mstorsjo]

In D24076#560523, @rengolin wrote:

Right, the change now looks good, but I'll let @compnerd approve, since I'm not that well versed in the Windows ABI.

FWIW, one of the remaining issues is that I don't (currently) add the DBZCHK (division by zero check) before the __rt_div calls for divrem or rem. I can add that as well (I got a patch for it locally). But IMO the question remains whether we should add that at all. MSVC does add it (both for div and rem, which are calls to the same function), but the actual implementations of the functions also do similar checks internally, so it feels redundant. But I guess the ABI of those functions mandate that the caller checks it.

The current implementation of DBZCHK also has got an issue, that it issues a CBZ, but later passes may move the branch target might out of range, see https://llvm.org/bugs/show_bug.cgi?id=30356 and the function EmitLowered__dbzchk.

If we can remove DBZCHK altogether, it'd be easy, but I'm not sure how to fix the current one.

[mstorsjo]

Added DBZCHK for the divrem/rem calls as well.

[compnerd]

lib/Target/ARM/ARMISelLowering.cpp

959

Wow, this is getting unwieldy. I wonder if its easier to negate the condition.

964–983

Not your fault since you are replicating what is there, but I think that refactoring this a slight bit will be nicer:

for (const auto &LC : {RTLIB::SDIVREM_I8, RTLIB::SDIVREM_I16, RTLIB::SDIVREM_I32})
  setLibcallName(LC, Subtarget->isTargetWindows() ? "__rt_sdiv" : "__aeabi_idivmod");
setLibcallName(RTLIB::SDIVREM_I64, Subtarget->isTargetWindows() ? "__rt_sdiv64" : "__aeabi_ldivmod");
for (const auto &LC : {RTLIB::UDIVREM_I8, RTLIB::UDIVREM_I16, RTLIB::UDIVREM_I32})
  setLibcallName(LC, Subtarget->isTargetWindows() ? "__rt_udiv" : "__aeabi_uidivmod");
setLibcallName(RTLIB::UDIVREM_I64, Subtarget->isTargetWindows() ? "__rt_udiv64" : " __aeabi_uldivmod");

12282

Sink this inside the if condition, as it is unused otherwise.

12294

How about doing a trivial static function ExtractDenominator or even better, create a WinDBZCheckDenominator to handle the duplication of the DBZ check.

static SDValue WinDBZCheckDenominator(SDNode *N, SDValue InChain) {
  SDLoc DL(N);
  Value *Op = N->getOperand(1);
  if (N->getValueType(0) == MVT::32)
    return DAG.getNode(ARMISD::WIN__DBZCHK, DL, MVT::Other, InChain, Op);
  SDValue Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, DL, MVT::i32, Op),
                           DAG.getConstant(0, DL, MVT::i32));
  SDValue Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, DL, MVT::i32, Op),
                           DAG.getConstant(1, DL, MVT::i32));
  return DAG.getNode(ARMISD::WIN__DBZCHK, DL, MVT::Other, InChain,
                     DAG.getNode(ISD::OR, DL, MVT::i32, Lo, Hi));
}

test/CodeGen/ARM/Windows/dbzchk.ll

185 ↗

(On Diff #73448)

Why are you removing the check for the actual dbzchk codegen?

[mstorsjo]

Thanks for the comments, I'll update the patch accordingly.

test/CodeGen/ARM/Windows/dbzchk.ll

185 ↗

(On Diff #73448)

Sorry about that, that change is from an earlier version of the patch where some of the DBZCHKs vanished (when I hadn't added the new ones into REM and DIVREM). I restored this hunk (and some of the ones above as well).

[mstorsjo]

Updated based on the comments.

[compnerd]

test/CodeGen/ARM/Windows/dbzchk.ll

144 ↗

(On Diff #73686)

This is amazing. Glad to see this improved.

test/CodeGen/ARM/divmod-eabi.ll

45 ↗

(On Diff #73686)

Hmm, it would be nice to see that we can still generate the hardware division. But, I don't think that we need to hold up on that.

lib/Target/ARM/ARMISelLowering.cpp

ARMTargetLowering::ARMTargetLowering(const TargetMachine &TM,
   bool hasDivide = Subtarget->isThumb() ? Subtarget->hasDivide()
                                         : Subtarget->hasDivideInARMMode();
   if (!hasDivide) {
     // These are expanded into libcalls if the cpu doesn't have HW divider.
     setOperationAction(ISD::SDIV,  MVT::i32, LibCall);
     setOperationAction(ISD::UDIV,  MVT::i32, LibCall);
   }
 
-  if (Subtarget->isTargetWindows() && !Subtarget->hasDivide()) {
-    setOperationAction(ISD::SDIV, MVT::i32, Custom);
-    setOperationAction(ISD::UDIV, MVT::i32, Custom);
-
-    setOperationAction(ISD::SDIV, MVT::i64, Custom);
-    setOperationAction(ISD::UDIV, MVT::i64, Custom);
-  }
-
   setOperationAction(ISD::SREM,  MVT::i32, Expand);
   setOperationAction(ISD::UREM,  MVT::i32, Expand);
   // Register based DivRem for AEABI (RTABI 4.2)
   if (Subtarget->isTargetAEABI() || Subtarget->isTargetAndroid() ||
-      Subtarget->isTargetGNUAEABI() || Subtarget->isTargetMuslAEABI()) {
+      Subtarget->isTargetGNUAEABI() || Subtarget->isTargetMuslAEABI() ||
+      Subtarget->isTargetWindows()) {
     setOperationAction(ISD::SREM, MVT::i64, Custom);
     setOperationAction(ISD::UREM, MVT::i64, Custom);
     HasStandaloneRem = false;
 
+    if (Subtarget->isTargetWindows()) {
+      setLibcallName(RTLIB::SDIVREM_I8,  "__rt_sdiv");
+      setLibcallName(RTLIB::SDIVREM_I16, "__rt_sdiv");
+      setLibcallName(RTLIB::SDIVREM_I32, "__rt_sdiv");
+      setLibcallName(RTLIB::SDIVREM_I64, "__rt_sdiv64");
+      setLibcallName(RTLIB::UDIVREM_I8,  "__rt_udiv");
+      setLibcallName(RTLIB::UDIVREM_I16, "__rt_udiv");
+      setLibcallName(RTLIB::UDIVREM_I32, "__rt_udiv");
+      setLibcallName(RTLIB::UDIVREM_I64, "__rt_udiv64");
+    } else {
       setLibcallName(RTLIB::SDIVREM_I8,  "__aeabi_idivmod");
       setLibcallName(RTLIB::SDIVREM_I16, "__aeabi_idivmod");
       setLibcallName(RTLIB::SDIVREM_I32, "__aeabi_idivmod");
       setLibcallName(RTLIB::SDIVREM_I64, "__aeabi_ldivmod");
       setLibcallName(RTLIB::UDIVREM_I8,  "__aeabi_uidivmod");
       setLibcallName(RTLIB::UDIVREM_I16, "__aeabi_uidivmod");
       setLibcallName(RTLIB::UDIVREM_I32, "__aeabi_uidivmod");
       setLibcallName(RTLIB::UDIVREM_I64, "__aeabi_uldivmod");
+    }
 
     setLibcallCallingConv(RTLIB::SDIVREM_I8, CallingConv::ARM_AAPCS);
     setLibcallCallingConv(RTLIB::SDIVREM_I16, CallingConv::ARM_AAPCS);
     setLibcallCallingConv(RTLIB::SDIVREM_I32, CallingConv::ARM_AAPCS);
     setLibcallCallingConv(RTLIB::SDIVREM_I64, CallingConv::ARM_AAPCS);
     setLibcallCallingConv(RTLIB::UDIVREM_I8, CallingConv::ARM_AAPCS);
     setLibcallCallingConv(RTLIB::UDIVREM_I16, CallingConv::ARM_AAPCS);
     setLibcallCallingConv(RTLIB::UDIVREM_I32, CallingConv::ARM_AAPCS);
     setLibcallCallingConv(RTLIB::UDIVREM_I64, CallingConv::ARM_AAPCS);
SDValue ARMTargetLowering::LowerWindowsDIVLibCall(SDValue Op, SelectionDAG &DAG,
   CLI.setDebugLoc(dl)
     .setChain(Chain)
     .setCallee(CallingConv::ARM_AAPCS_VFP, VT.getTypeForEVT(*DAG.getContext()),
                ES, std::move(Args));
 
   return LowerCallTo(CLI).first;
 }
 
-SDValue ARMTargetLowering::LowerDIV_Windows(SDValue Op, SelectionDAG &DAG,
-                                            bool Signed) const {
-  assert(Op.getValueType() == MVT::i32 &&
-         "unexpected type for custom lowering DIV");
-  SDLoc dl(Op);
-
-  SDValue DBZCHK = DAG.getNode(ARMISD::WIN__DBZCHK, dl, MVT::Other,
-                               DAG.getEntryNode(), Op.getOperand(1));
-
-  return LowerWindowsDIVLibCall(Op, DAG, Signed, DBZCHK);
-}
-
-void ARMTargetLowering::ExpandDIV_Windows(
-    SDValue Op, SelectionDAG &DAG, bool Signed,
-    SmallVectorImpl<SDValue> &Results) const {
-  const auto &DL = DAG.getDataLayout();
-  const auto &TLI = DAG.getTargetLoweringInfo();
-
-  assert(Op.getValueType() == MVT::i64 &&
-         "unexpected type for custom lowering DIV");
-  SDLoc dl(Op);
-
-  SDValue Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, MVT::i32, Op.getOperand(1),
-                           DAG.getConstant(0, dl, MVT::i32));
-  SDValue Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, MVT::i32, Op.getOperand(1),
-                           DAG.getConstant(1, dl, MVT::i32));
-  SDValue Or = DAG.getNode(ISD::OR, dl, MVT::i32, Lo, Hi);
-
-  SDValue DBZCHK =
-      DAG.getNode(ARMISD::WIN__DBZCHK, dl, MVT::Other, DAG.getEntryNode(), Or);
-
-  SDValue Result = LowerWindowsDIVLibCall(Op, DAG, Signed, DBZCHK);
-
-  SDValue Lower = DAG.getNode(ISD::TRUNCATE, dl, MVT::i32, Result);
-  SDValue Upper = DAG.getNode(ISD::SRL, dl, MVT::i64, Result,
-                              DAG.getConstant(32, dl, TLI.getPointerTy(DL)));
-  Upper = DAG.getNode(ISD::TRUNCATE, dl, MVT::i32, Upper);
-
-  Results.push_back(Lower);
-  Results.push_back(Upper);
-}
-
 static SDValue LowerAtomicLoadStore(SDValue Op, SelectionDAG &DAG) {
   if (isStrongerThanMonotonic(cast<AtomicSDNode>(Op)->getOrdering()))
     // Acquire/Release load/store is not legal for targets without a dmb or
     // equivalent available.
     return SDValue();
 
   // Monotonic load/store is legal for all targets.
   return Op;
SDValue ARMTargetLowering::LowerOperation(SDValue Op, SelectionDAG &DAG) const {
   case ISD::BUILD_VECTOR:  return LowerBUILD_VECTOR(Op, DAG, Subtarget);
   case ISD::VECTOR_SHUFFLE: return LowerVECTOR_SHUFFLE(Op, DAG);
   case ISD::INSERT_VECTOR_ELT: return LowerINSERT_VECTOR_ELT(Op, DAG);
   case ISD::EXTRACT_VECTOR_ELT: return LowerEXTRACT_VECTOR_ELT(Op, DAG);
   case ISD::CONCAT_VECTORS: return LowerCONCAT_VECTORS(Op, DAG);
   case ISD::FLT_ROUNDS_:   return LowerFLT_ROUNDS_(Op, DAG);
   case ISD::MUL:           return LowerMUL(Op, DAG);
   case ISD::SDIV:
-    if (Subtarget->isTargetWindows())
-      return LowerDIV_Windows(Op, DAG, /* Signed */ true);
     return LowerSDIV(Op, DAG);
   case ISD::UDIV:
-    if (Subtarget->isTargetWindows())
-      return LowerDIV_Windows(Op, DAG, /* Signed */ false);
     return LowerUDIV(Op, DAG);
   case ISD::ADDC:
   case ISD::ADDE:
   case ISD::SUBC:
   case ISD::SUBE:          return LowerADDC_ADDE_SUBC_SUBE(Op, DAG);
   case ISD::SADDO:
   case ISD::UADDO:
   case ISD::SSUBO:
case ISD::UDIVREM:
     Results.push_back(Res.getValue(0));
     Results.push_back(Res.getValue(1));
     return;
   case ISD::READCYCLECOUNTER:
     ReplaceREADCYCLECOUNTER(N, Results, DAG, Subtarget);
     return;
   case ISD::UDIV:
   case ISD::SDIV:
-    assert(Subtarget->isTargetWindows() && "can only expand DIV on Windows");
-    return ExpandDIV_Windows(SDValue(N, 0), DAG, N->getOpcode() == ISD::SDIV,
-                             Results);
+    abort();
+    return;
   case ISD::ATOMIC_CMP_SWAP:
     ReplaceCMP_SWAP_64Results(N, Results, DAG);
     return;
   }
   if (Res.getNode())
     Results.push_back(Res);
 }
 
static RTLIB::Libcall getDivRemLibcall(
   case MVT::i16: LC = isSigned ? RTLIB::SDIVREM_I16 : RTLIB::UDIVREM_I16; break;
   case MVT::i32: LC = isSigned ? RTLIB::SDIVREM_I32 : RTLIB::UDIVREM_I32; break;
   case MVT::i64: LC = isSigned ? RTLIB::SDIVREM_I64 : RTLIB::UDIVREM_I64; break;
   }
   return LC;
 }
 
 static TargetLowering::ArgListTy getDivRemArgList(
-    const SDNode *N, LLVMContext *Context) {
+    const SDNode *N, LLVMContext *Context, const ARMSubtarget *Subtarget) {
   assert((N->getOpcode() == ISD::SDIVREM || N->getOpcode() == ISD::UDIVREM ||
           N->getOpcode() == ISD::SREM    || N->getOpcode() == ISD::UREM) &&
          "Unhandled Opcode in getDivRemArgList");
   bool isSigned = N->getOpcode() == ISD::SDIVREM ||
                   N->getOpcode() == ISD::SREM;
   TargetLowering::ArgListTy Args;
   TargetLowering::ArgListEntry Entry;
   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
-    EVT ArgVT = N->getOperand(i).getValueType();
+    unsigned src = Subtarget->isTargetWindows() ? e - 1 - i : i;
+    EVT ArgVT = N->getOperand(src).getValueType();
     Type *ArgTy = ArgVT.getTypeForEVT(*Context);
-    Entry.Node = N->getOperand(i);
+    Entry.Node = N->getOperand(src);
     Entry.Ty = ArgTy;
     Entry.isSExt = isSigned;
     Entry.isZExt = !isSigned;
     Args.push_back(Entry);
   }
   return Args;
 }
 
 SDValue ARMTargetLowering::LowerDivRem(SDValue Op, SelectionDAG &DAG) const {
   assert((Subtarget->isTargetAEABI() || Subtarget->isTargetAndroid() ||
-          Subtarget->isTargetGNUAEABI() || Subtarget->isTargetMuslAEABI()) &&
+          Subtarget->isTargetGNUAEABI() || Subtarget->isTargetMuslAEABI() ||
+          Subtarget->isTargetWindows()) &&
          "Register-based DivRem lowering only");
   unsigned Opcode = Op->getOpcode();
   assert((Opcode == ISD::SDIVREM || Opcode == ISD::UDIVREM) &&
          "Invalid opcode for Div/Rem lowering");
   bool isSigned = (Opcode == ISD::SDIVREM);
   EVT VT = Op->getValueType(0);
   Type *Ty = VT.getTypeForEVT(*DAG.getContext());
 
   RTLIB::Libcall LC = getDivRemLibcall(Op.getNode(),
                                        VT.getSimpleVT().SimpleTy);
   SDValue InChain = DAG.getEntryNode();
 
   TargetLowering::ArgListTy Args = getDivRemArgList(Op.getNode(),
-                                                    DAG.getContext());
+                                                    DAG.getContext(),
+                                                    Subtarget);
 
   SDValue Callee = DAG.getExternalSymbol(getLibcallName(LC),
                                          getPointerTy(DAG.getDataLayout()));
 
   Type *RetTy = (Type*)StructType::get(Ty, Ty, nullptr);
 
   SDLoc dl(Op);
   TargetLowering::CallLoweringInfo CLI(DAG);
SDValue ARMTargetLowering::LowerREM(SDNode *N, SelectionDAG &DAG) const {
   RetTyParams.push_back(RetTyElement);
   RetTyParams.push_back(RetTyElement);
   ArrayRef<Type*> ret = ArrayRef<Type*>(RetTyParams);
   Type *RetTy = StructType::get(*DAG.getContext(), ret);
 
   RTLIB::Libcall LC = getDivRemLibcall(N, N->getValueType(0).getSimpleVT().
                                                              SimpleTy);
   SDValue InChain = DAG.getEntryNode();
-  TargetLowering::ArgListTy Args = getDivRemArgList(N, DAG.getContext());
+  TargetLowering::ArgListTy Args = getDivRemArgList(N, DAG.getContext(),
+                                                    Subtarget);
   bool isSigned = N->getOpcode() == ISD::SREM;
   SDValue Callee = DAG.getExternalSymbol(getLibcallName(LC),
                                          getPointerTy(DAG.getDataLayout()));
 
   // Lower call
   CallLoweringInfo CLI(DAG);
   CLI.setChain(InChain)
      .setCallee(CallingConv::ARM_AAPCS, RetTy, Callee, std::move(Args))
      .setSExtResult(isSigned).setZExtResult(!isSigned).setDebugLoc(SDLoc(N));
   std::pair<SDValue, SDValue> CallResult = LowerCallTo(CLI);
 
   // Return second (rem) result operand (first contains div)
   SDNode *ResNode = CallResult.first.getNode();
   assert(ResNode->getNumOperands() == 2 && "divmod should return two operands");
   return ResNode->getOperand(1);
 }
 
 SDValue
 ARMTargetLowering::LowerDYNAMIC_STACKALLOC(SDValue Op, SelectionDAG &DAG) const {
   assert(Subtarget->isTargetWindows() && "unsupported target platform");
   SDLoc DL(Op);
 
   // Get the inputs.
   SDValue Chain = Op.getOperand(0);
   SDValue Size  = Op.getOperand(1);