Refactor reciprocal square root estimate into target-independent function (part 1).

[spatel]

Summary

This is purely a plumbing patch. No functional changes intended.

The ultimate goal is to allow targets other than PowerPC (certainly X86 and Aarch64) to turn this:

y = C / sqrt(x)

into:

y = C * rsqrte(x)

using whatever HW magic they can use. See http://llvm.org/bugs/show_bug.cgi?id=20900 .

Currently, this is guarded by unsafe-fp-math, but I'm not sure if that's necessary in all cases.

The first step is to add a target hook for RSQRTE, take the already target-independent code selfishly hoarded by PPC, and put it into DAGCombiner. That's this patch.

Next steps:

1. The code in DAGCombiner::BuildRSQRTE() should be refactored further, but see note below.
2. Logic in PPCTargetLowering::BuildRSQRTE() should be hoisted into DAGCombiner.
3. X86 and AArch64 overrides for TargetLowering.BuildRSQRTE() should be added.

Note: when first creating this patch I accidentally wiped out the FP_EXTEND and FP_ROUND cases...and 'make check' still passed. The existing PPC tests in test/CodeGen/PowerPC/recipest.ll are inadequate. I didn't want to alter this code too much from the existing PPC version and risk screwing up some untested functionality.

[chandlerc]

Looks like a trivially good refactoring. Looking forward to the cleanup to the function, I agree it could be better. =]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

7012–7014

You can make SqrtOp a condition variable now, I fixed SDValue to support this:

if (SDValue SqrtOp = BuildRSQRTE(N))
  return SqrtOp;

[spatel]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

7012–7014

Nice! There's a lot more where that came from...

[spatel]

Closed by commit rL218219 (authored by @spatel).

include/llvm/Target/TargetLowering.h

SDValue BuildUDIV(SDNode *N, const APInt &Divisor, SelectionDAG &DAG,
                     bool IsAfterLegalization,
                     std::vector<SDNode *> *Created) const;
   virtual SDValue BuildSDIVPow2(SDNode *N, const APInt &Divisor,
                                 SelectionDAG &DAG,
                                 std::vector<SDNode *> *Created) const {
     return SDValue();
   }
 
+  virtual SDValue BuildRSQRTE(SDValue Op, DAGCombinerInfo &DCI) const {
+    return SDValue();
+  }
+
   //===--------------------------------------------------------------------===//
   // Legalization utility functions
   //
 
   /// Expand a MUL into two nodes.  One that computes the high bits of
   /// the result and one that computes the low bits.
   /// \param HiLoVT The value type to use for the Lo and Hi nodes.
   /// \param LL Low bits of the LHS of the MUL.  You can use this parameter

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

private:
 
     SDValue SimplifyNodeWithTwoResults(SDNode *N, unsigned LoOp,
                                          unsigned HiOp);
     SDValue CombineConsecutiveLoads(SDNode *N, EVT VT);
     SDValue ConstantFoldBITCASTofBUILD_VECTOR(SDNode *, EVT);
     SDValue BuildSDIV(SDNode *N);
     SDValue BuildSDIVPow2(SDNode *N);
     SDValue BuildUDIV(SDNode *N);
+    SDValue BuildRSQRTE(SDNode *N);
     SDValue MatchBSwapHWordLow(SDNode *N, SDValue N0, SDValue N1,
                                bool DemandHighBits = true);
     SDValue MatchBSwapHWord(SDNode *N, SDValue N0, SDValue N1);
     SDNode *MatchRotatePosNeg(SDValue Shifted, SDValue Pos, SDValue Neg,
                               SDValue InnerPos, SDValue InnerNeg,
                               unsigned PosOpcode, unsigned NegOpcode,
                               SDLoc DL);
     SDNode *MatchRotate(SDValue LHS, SDValue RHS, SDLoc DL);
if (VT.isVector()) {
     SDValue FoldedVOp = SimplifyVBinOp(N);
     if (FoldedVOp.getNode()) return FoldedVOp;
   }
 
   // fold (fdiv c1, c2) -> c1/c2
   if (N0CFP && N1CFP)
     return DAG.getNode(ISD::FDIV, SDLoc(N), VT, N0, N1);
 
+  if (Options.UnsafeFPMath) {
     // fold (fdiv X, c2) -> fmul X, 1/c2 if losing precision is acceptable.
-  if (N1CFP && Options.UnsafeFPMath) {
+    if (N1CFP) {
       // Compute the reciprocal 1.0 / c2.
       APFloat N1APF = N1CFP->getValueAPF();
       APFloat Recip(N1APF.getSemantics(), 1); // 1.0
       APFloat::opStatus st = Recip.divide(N1APF, APFloat::rmNearestTiesToEven);
       // Only do the transform if the reciprocal is a legal fp immediate that
       // isn't too nasty (eg NaN, denormal, ...).
       if ((st == APFloat::opOK || st == APFloat::opInexact) && // Not too nasty
           (!LegalOperations ||
            // FIXME: custom lowering of ConstantFP might fail (see e.g. ARM
            // backend)... we should handle this gracefully after Legalize.
            // TLI.isOperationLegalOrCustom(llvm::ISD::ConstantFP, VT) ||
            TLI.isOperationLegal(llvm::ISD::ConstantFP, VT) ||
            TLI.isFPImmLegal(Recip, VT)))
         return DAG.getNode(ISD::FMUL, SDLoc(N), VT, N0,
                            DAG.getConstantFP(Recip, VT));
     }
+    // If this division is part of a reciprocal square root,
+    // it may be folded into a target-specific square root estimate intruction.
+    SDValue SqrtOp = BuildRSQRTE(N);
+    if (SqrtOp.getNode())
+      return SqrtOp;
+  }
 
   // (fdiv (fneg X), (fneg Y)) -> (fdiv X, Y)
   if (char LHSNeg = isNegatibleForFree(N0, LegalOperations, TLI, &Options)) {
     if (char RHSNeg = isNegatibleForFree(N1, LegalOperations, TLI, &Options)) {
       // Both can be negated for free, check to see if at least one is cheaper
       // negated.
       if (LHSNeg == 2 || RHSNeg == 2)
         return DAG.getNode(ISD::FDIV, SDLoc(N), VT,
SDValue DAGCombiner::BuildUDIV(SDNode *N) {
   SDValue S =
       TLI.BuildUDIV(N, C->getAPIntValue(), DAG, LegalOperations, &Built);
 
   for (SDNode *N : Built)
     AddToWorklist(N);
   return S;
 }
 
+/// Given an ISD::FDIV node with either a direct or indirect ISD::FSQRT operand,
+/// generate a DAG expression using a reciprocal square root estimate op.
+SDValue DAGCombiner::BuildRSQRTE(SDNode *N) {
+  // Expose the DAG combiner to the target combiner implementations.
+  TargetLowering::DAGCombinerInfo DCI(DAG, Level, false, this);
+  SDLoc DL(N);
+  EVT VT = N->getValueType(0);
+  SDValue N1 = N->getOperand(1);
+
+  if (N1.getOpcode() == ISD::FSQRT) {
+    SDValue RV = TLI.BuildRSQRTE(N1.getOperand(0), DCI);
+    if (RV.getNode()) {
+      DCI.AddToWorklist(RV.getNode());
+      return DAG.getNode(ISD::FMUL, DL, VT, N->getOperand(0), RV);
+    }
+  } else if (N1.getOpcode() == ISD::FP_EXTEND &&
+             N1.getOperand(0).getOpcode() == ISD::FSQRT) {
+    SDValue RV = TLI.BuildRSQRTE(N1.getOperand(0).getOperand(0), DCI);
+    if (RV.getNode()) {
+      DCI.AddToWorklist(RV.getNode());
+      RV = DAG.getNode(ISD::FP_EXTEND, SDLoc(N1), VT, RV);
+      DCI.AddToWorklist(RV.getNode());
+      return DAG.getNode(ISD::FMUL, DL, VT, N->getOperand(0), RV);
+    }
+  } else if (N1.getOpcode() == ISD::FP_ROUND &&
+             N1.getOperand(0).getOpcode() == ISD::FSQRT) {
+    SDValue RV = TLI.BuildRSQRTE(N1.getOperand(0).getOperand(0), DCI);
+    if (RV.getNode()) {
+      DCI.AddToWorklist(RV.getNode());
+      RV = DAG.getNode(ISD::FP_ROUND, SDLoc(N1), VT, RV, N1.getOperand(1));
+      DCI.AddToWorklist(RV.getNode());
+      return DAG.getNode(ISD::FMUL, DL, VT, N->getOperand(0), RV);
+    }
+  }
+
+  return SDValue();
+}
+
 /// Return true if base is a frame index, which is known not to alias with
 /// anything but itself.  Provides base object and offset as results.
 static bool FindBaseOffset(SDValue Ptr, SDValue &Base, int64_t &Offset,
                            const GlobalValue *&GV, const void *&CV) {
   // Assume it is a primitive operation.
   Base = Ptr; Offset = 0; GV = nullptr; CV = nullptr;
 
   // If it's an adding a simple constant then integrate the offset.

lib/Target/PowerPC/PPCISelLowering.h

LowerCall_32SVR4(SDValue Chain, SDValue Callee, CallingConv::ID CallConv,
                      SmallVectorImpl<SDValue> &InVals) const;
 
     SDValue lowerEH_SJLJ_SETJMP(SDValue Op, SelectionDAG &DAG) const;
     SDValue lowerEH_SJLJ_LONGJMP(SDValue Op, SelectionDAG &DAG) const;
 
     SDValue DAGCombineExtBoolTrunc(SDNode *N, DAGCombinerInfo &DCI) const;
     SDValue DAGCombineTruncBoolExt(SDNode *N, DAGCombinerInfo &DCI) const;
     SDValue DAGCombineFastRecip(SDValue Op, DAGCombinerInfo &DCI) const;
-    SDValue DAGCombineFastRecipFSQRT(SDValue Op, DAGCombinerInfo &DCI) const;
+    SDValue BuildRSQRTE(SDValue Op, DAGCombinerInfo &DCI) const;
 
     CCAssignFn *useFastISelCCs(unsigned Flag) const;
   };
 
   namespace PPC {
     FastISel *createFastISel(FunctionLoweringInfo &FuncInfo,
                              const TargetLibraryInfo *LibInfo);
   }

lib/Target/PowerPC/PPCISelLowering.cpp

if ((VT == MVT::f32 && Subtarget.hasFRES()) ||
     }
 
     return Est;
   }
 
   return SDValue();
 }
 
-SDValue PPCTargetLowering::DAGCombineFastRecipFSQRT(SDValue Op,
-                                             DAGCombinerInfo &DCI) const {
+SDValue PPCTargetLowering::BuildRSQRTE(SDValue Op, DAGCombinerInfo &DCI) const {
   if (DCI.isAfterLegalizeVectorOps())
     return SDValue();
 
   EVT VT = Op.getValueType();
 
   if ((VT == MVT::f32 && Subtarget.hasFRSQRTES()) ||
       (VT == MVT::f64 && Subtarget.hasFRSQRTE())  ||
       (VT == MVT::v4f32 && Subtarget.hasAltivec()) ||
SDValue PPCTargetLowering::PerformDAGCombine(SDNode *N,
   case ISD::TRUNCATE:
   case ISD::SETCC:
   case ISD::SELECT_CC:
     return DAGCombineTruncBoolExt(N, DCI);
   case ISD::FDIV: {
     assert(TM.Options.UnsafeFPMath &&
            "Reciprocal estimates require UnsafeFPMath");
 
-    if (N->getOperand(1).getOpcode() == ISD::FSQRT) {
-      SDValue RV =
-        DAGCombineFastRecipFSQRT(N->getOperand(1).getOperand(0), DCI);
-      if (RV.getNode()) {
-        DCI.AddToWorklist(RV.getNode());
-        return DAG.getNode(ISD::FMUL, dl, N->getValueType(0),
-                           N->getOperand(0), RV);
-      }
-    } else if (N->getOperand(1).getOpcode() == ISD::FP_EXTEND &&
-               N->getOperand(1).getOperand(0).getOpcode() == ISD::FSQRT) {
-      SDValue RV =
-        DAGCombineFastRecipFSQRT(N->getOperand(1).getOperand(0).getOperand(0),
-                                 DCI);
-      if (RV.getNode()) {
-        DCI.AddToWorklist(RV.getNode());
-        RV = DAG.getNode(ISD::FP_EXTEND, SDLoc(N->getOperand(1)),
-                         N->getValueType(0), RV);
-        DCI.AddToWorklist(RV.getNode());
-        return DAG.getNode(ISD::FMUL, dl, N->getValueType(0),
-                           N->getOperand(0), RV);
-      }
-    } else if (N->getOperand(1).getOpcode() == ISD::FP_ROUND &&
-               N->getOperand(1).getOperand(0).getOpcode() == ISD::FSQRT) {
-      SDValue RV =
-        DAGCombineFastRecipFSQRT(N->getOperand(1).getOperand(0).getOperand(0),
-                                 DCI);
-      if (RV.getNode()) {
-        DCI.AddToWorklist(RV.getNode());
-        RV = DAG.getNode(ISD::FP_ROUND, SDLoc(N->getOperand(1)),
-                         N->getValueType(0), RV,
-                         N->getOperand(1).getOperand(1));
-        DCI.AddToWorklist(RV.getNode());
-        return DAG.getNode(ISD::FMUL, dl, N->getValueType(0),
-                           N->getOperand(0), RV);
-      }
-    }
-
     SDValue RV = DAGCombineFastRecip(N->getOperand(1), DCI);
     if (RV.getNode()) {
       DCI.AddToWorklist(RV.getNode());
       return DAG.getNode(ISD::FMUL, dl, N->getValueType(0),
                          N->getOperand(0), RV);
     }
 
     }
     break;
   case ISD::FSQRT: {
     assert(TM.Options.UnsafeFPMath &&
            "Reciprocal estimates require UnsafeFPMath");
 
     // Compute this as 1/(1/sqrt(X)), which is the reciprocal of the
     // reciprocal sqrt.
-    SDValue RV = DAGCombineFastRecipFSQRT(N->getOperand(0), DCI);
+    SDValue RV = BuildRSQRTE(N->getOperand(0), DCI);
     if (RV.getNode()) {
       DCI.AddToWorklist(RV.getNode());
       RV = DAGCombineFastRecip(RV, DCI);
       if (RV.getNode()) {
         // Unfortunately, RV is now NaN if the input was exactly 0. Select out
         // this case and force the answer to 0.
 
         EVT VT = RV.getValueType();