[X86] PR34149 Suboptimal codegen for fast minnum and maxnum.

[jbhateja]

Summary

Perform DAG combining of FMIN/MAXNUM based on Fast-Math flags which are propagated
from Instruction to SDNode.

[spatel]

The way you're transferring the flags from the IR to the node works for this particular case, but I'd prefer that we clean that up as a preliminary step for this patch if possible. The existing flags transfer code is limited because we started with SDNodeFlags only on binary operators. So there's a different blob of code to handle flags in SelectionDAGBuilder::visitBinary(). Can we unify that? Is it possible to handle this for all opcodes/nodes in SelectionDAGBuilder::visit()?

[spatel]

I might be missing some context here. If we have fast/nnan on these calls, then can't we simplify this in IR to fmp+select and not have to deal with this in the backend? The intrinsics only exist to make sure that NaN behavior in IR meets the higher level standards, so if we have nnan, then we don't need the intrinsic?

[jbhateja]

• Consolidating Instruction->SDNode Flags propagation in one class.

[jbhateja]

In D37616#865418, @spatel wrote:

I might be missing some context here. If we have fast/nnan on these calls, then can't we simplify this in IR to fmp+select and not have to deal with this in the backend? The intrinsics only exist to make sure that NaN behavior in IR meets the higher level standards, so if we have nnan, then we don't need the intrinsic?

Intrinsic function defer code geneation/expansion to backend this give backend control over geneating efficient code as per specific target. As of now SelectionDAGBuilder boils down intrinsic call to fminnum (or fminnan if target supports it and nnan is true) which is then handled by different targets differently.

[spatel]

In D37616#865798, @jbhateja wrote:

In D37616#865418, @spatel wrote:

I might be missing some context here. If we have fast/nnan on these calls, then can't we simplify this in IR to fmp+select and not have to deal with this in the backend? The intrinsics only exist to make sure that NaN behavior in IR meets the higher level standards, so if we have nnan, then we don't need the intrinsic?

Intrinsic function defer code geneation/expansion to backend this give backend control over geneating efficient code as per specific target.

It's incorrect that intrinsics are passed unaltered to the backend for expansion/optimization. See the optimizations for both generic and target-specific intrinsics in InstCombiner::visitCallInst().

Again, I may be missing some context - who created this IR? Creating a 'call fast llvm.maxnum()' just doesn't make sense to me, so if we can fix that in IR, we should do that. The intrinsic inhibits the large number of potential optimizations for fcmp+select that we have in IR. No target should benefit from having extra NaN semantics requirements provided by the intrinsic that are then overridden by FMF.

Please split the FlagsAcquirer diff into a separate patch.

[jbhateja]

In D37616#865981, @spatel wrote:

In D37616#865798, @jbhateja wrote:

In D37616#865418, @spatel wrote:

I might be missing some context here. If we have fast/nnan on these calls, then can't we simplify this in IR to fmp+select and not have to deal with this in the backend? The intrinsics only exist to make sure that NaN behavior in IR meets the higher level standards, so if we have nnan, then we don't need the intrinsic?

Intrinsic function defer code geneation/expansion to backend this give backend control over geneating efficient code as per specific target.

It's incorrect that intrinsics are passed unaltered to the backend for expansion/optimization. See the optimizations for both generic and target-specific intrinsics in InstCombiner::visitCallInst().

Again, I may be missing some context - who created this IR? Creating a 'call fast llvm.maxnum()' just doesn't make sense to me, so if we can fix that in IR, we should do that. The intrinsic inhibits the large number of potential optimizations for fcmp+select that we have in IR. No target should benefit from having extra NaN semantics requirements provided by the intrinsic that are then overridden by FMF.

Please split the FlagsAcquirer diff into a separate patch.

Your point of not genrating call fast @llvm.minnum in the first place and instead fcmp+setcc should have been generated is valid. But, its still a valid IR syntactically and semantically which could be thrown at backend.

Please consider following case which is being compiled for arm( -mcpu=cortex-r52 -march=arm test.ll -mattr=fp-armv8)

define <4 x double> @CASEA(<4 x double> %x, <4 x double> %y) {

%z = call fast <4 x double> @llvm.minnum.v4f64(<4 x double> %x, <4 x double> %y) readnone
ret <4 x double> %z

}

define <4 x double> @CASEB(<4 x double> %x, <4 x double> %y) {

%c = fcmp ule <4 x double> %x, %y
%z = select <4 x i1> %c, <4 x double> %x, <4 x double> %y
ret <4 x double> %z

}

Instruction selector does not generates vminnm for CASEB where as same is generated for CASEA.
As of now SelectionDAGBuilder generates fminnum (or fminnnan) SDNode for llvm.minnum intrinsic.
Thus different targets lowers fminnum (SDNode) differently.

So handling for fast math with intrinsic here should be fine ?

Otherwise, I can put Acquirer in a seperate patch.

[spatel]

In D37616#865983, @jbhateja wrote:

In D37616#865981, @spatel wrote:

In D37616#865798, @jbhateja wrote:

In D37616#865418, @spatel wrote:

I might be missing some context here. If we have fast/nnan on these calls, then can't we simplify this in IR to fmp+select and not have to deal with this in the backend? The intrinsics only exist to make sure that NaN behavior in IR meets the higher level standards, so if we have nnan, then we don't need the intrinsic?

Intrinsic function defer code geneation/expansion to backend this give backend control over geneating efficient code as per specific target.

It's incorrect that intrinsics are passed unaltered to the backend for expansion/optimization. See the optimizations for both generic and target-specific intrinsics in InstCombiner::visitCallInst().

Again, I may be missing some context - who created this IR? Creating a 'call fast llvm.maxnum()' just doesn't make sense to me, so if we can fix that in IR, we should do that. The intrinsic inhibits the large number of potential optimizations for fcmp+select that we have in IR. No target should benefit from having extra NaN semantics requirements provided by the intrinsic that are then overridden by FMF.

Please split the FlagsAcquirer diff into a separate patch.

Your point of not genrating call fast @llvm.minnum in the first place and instead fcmp+setcc should have been generated is valid. But, its still a valid IR syntactically and semantically which could be thrown at backend.

I don't see the point of this argument. There are an infinite number of valid IR patterns that we can send to the backend, but the main point of the IR optimizer is to limit that set, so we don't have to increase the complexity of the backend. That's what I'm requesting here: solve this in IR, so the backend never has to worry about it. I'll ask again: who is producing this IR or these nodes? If I'm missing some scenario in which this pattern can be created in the backend, then I agree that we will have to handle it there (but still not the target-specific way you've proposed). If not, let's not add unnecessary code.

Please consider following case which is being compiled for arm( -mcpu=cortex-r52 -march=arm test.ll -mattr=fp-armv8)

define <4 x double> @CASEA(<4 x double> %x, <4 x double> %y) {

%z = call fast <4 x double> @llvm.minnum.v4f64(<4 x double> %x, <4 x double> %y) readnone
ret <4 x double> %z

}

define <4 x double> @CASEB(<4 x double> %x, <4 x double> %y) {

%c = fcmp ule <4 x double> %x, %y
%z = select <4 x i1> %c, <4 x double> %x, <4 x double> %y
ret <4 x double> %z

}

Instruction selector does not generates vminnm for CASEB where as same is generated for CASEA.
As of now SelectionDAGBuilder generates fminnum (or fminnnan) SDNode for llvm.minnum intrinsic.
Thus different targets lowers fminnum (SDNode) differently.

I acknowledge there may be other bugs here, but I think the ARM backend is behaving correctly for the example as shown (cc'ing @efriedma for expertise).

If we want to create equivalent patterns for these 2 examples, then we must add 'fast' to the fcmp in the 2nd case:

%c = fcmp fast ule <4 x double> %x, %y

If we do that, we see that the ARM backend is still behaving correctly and optimally to produce vminnm:

$ ./llc -o - minnum.ll -mcpu=cortex-r52 -march=arm -mattr=fp-armv8 | egrep 'CASE|minnm'
_CASEA:
vminnm.f64 d25, d22, d17
vminnm.f64 d24, d23, d16
vminnm.f64 d17, d21, d19
vminnm.f64 d16, d20, d18
_CASEB:
vminnm.f64 d25, d22, d17
vminnm.f64 d24, d23, d16
vminnm.f64 d17, d21, d19
vminnm.f64 d16, d20, d18

[asbirlea]

FWIW, we've seen a similar case of min/maxnum being generated in the IR and leading to suboptimal codegen.
The solution was replacing the IR generated with fcmp+select (coupled with D27846). Seems like the right approach to avoid adding complexity to the backend.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

public:
   SDValue getCopyFromRegs(const Value *V, Type *Ty);
 
   // resolveDanglingDebugInfo - if we saw an earlier dbg_value referring to V,
   // generate the debug data structures now that we've seen its definition.
   void resolveDanglingDebugInfo(const Value *V, SDValue Val);
   SDValue getValue(const Value *V);
   bool findValue(const Value *V) const;
 
+  // returns DAG node of SDValue present in NodeMap for 
+  // a given Value.
+  SDNode * getDAGNode(const Value *);
+
   SDValue getNonRegisterValue(const Value *V);
   SDValue getValueImpl(const Value *V);
 
   void setValue(const Value *V, SDValue NewN) {
     SDValue &N = NodeMap[V];
     assert(!N.getNode() && "Already set a value for this node!");
     N = NewN;
   }

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

 static unsigned LimitFloatPrecision;
 
 static cl::opt<unsigned, true>
 LimitFPPrecision("limit-float-precision",
                  cl::desc("Generate low-precision inline sequences "
                           "for some float libcalls"),
                  cl::location(LimitFloatPrecision),
                  cl::init(0));
+
+static bool isVectorReductionOp(const User *I);
+
+/// This class is used for propagating Flags from Instruction to SDNode.
+/// These flags are later used by accessing SDNode during different
+/// DAG phases.
+class SDNodeFlagsAcquirer {
+public:
+   SDNodeFlagsAcquirer(const Instruction * I, SelectionDAGBuilder *SDB):
+                       Instr(I), SelDB(SDB) {}
+
+  ~SDNodeFlagsAcquirer() {
+      SDNode * Node = SelDB->getDAGNode(Instr);
+      if (Node) {
+        SDNodeFlags Flags = Node->getFlags();
+
+        if (isa<FPMathOperator>(*Instr)) { 
+          Flags.setNoNaNs(Instr->hasNoNaNs());
+          Flags.setNoInfs(Instr->hasNoInfs());
+          Flags.setUnsafeAlgebra(Instr->hasUnsafeAlgebra());
+          Flags.setNoSignedZeros(Instr->hasNoSignedZeros());
+          Flags.setAllowContract(Instr->hasAllowContract());
+          Flags.setAllowReciprocal(Instr->hasAllowReciprocal());
+        }
+
+        if (const OverflowingBinaryOperator *OFBinOp =
+            dyn_cast<const OverflowingBinaryOperator>(Instr)) {
+          Flags.setNoSignedWrap(OFBinOp->hasNoSignedWrap());
+          Flags.setNoUnsignedWrap(OFBinOp->hasNoUnsignedWrap());
+        }
+
+        if (const PossiblyExactOperator *ExactOp =
+            dyn_cast<const PossiblyExactOperator>(Instr))
+          Flags.setExact(ExactOp->isExact());
+
+        if (isVectorReductionOp(Instr))
+          Flags.setVectorReduction(true);
+
+        Node->setFlags(Flags);
+      }
+   }
+
+private:
+   const Instruction * Instr;     
+   SelectionDAGBuilder *SelDB;
+};
+
 // Limit the width of DAG chains. This is important in general to prevent
 // DAG-based analysis from blowing up. For example, alias analysis and
 // load clustering may not complete in reasonable time. It is difficult to
 // recognize and avoid this situation within each individual analysis, and
 // future analyses are likely to have the same behavior. Limiting DAG width is
 // the safe approach and will be especially important with global DAGs.
 //
 // MaxParallelChains default is arbitrarily high to avoid affecting
SDValue SelectionDAGBuilder::getControlRoot() {
   Root = DAG.getNode(ISD::TokenFactor, getCurSDLoc(), MVT::Other,
                      PendingExports);
   PendingExports.clear();
   DAG.setRoot(Root);
   return Root;
 }
 
 void SelectionDAGBuilder::visit(const Instruction &I) {
+  SDNodeFlagsAcquirer Flags(&I,this);
+
   // Set up outgoing PHI node register values before emitting the terminator.
   if (isa<TerminatorInst>(&I)) {
     HandlePHINodesInSuccessorBlocks(I.getParent());
   }
 
   // Increase the SDNodeOrder if dealing with a non-debug instruction.
   if (!isa<DbgInfoIntrinsic>(I))
     ++SDNodeOrder;
if (It != FuncInfo.ValueMap.end()) {
     Result = RFV.getCopyFromRegs(DAG, FuncInfo, getCurSDLoc(), Chain, nullptr,
                                  V);
     resolveDanglingDebugInfo(V, Result);
   }
 
   return Result;
 }
 
+SDNode * SelectionDAGBuilder::getDAGNode(const Value *V) {
+  if (NodeMap.find(V) == NodeMap.end())
+    return nullptr;
+  return NodeMap[V].getNode();
+}
+
 /// getValue - Return an SDValue for the given Value.
 SDValue SelectionDAGBuilder::getValue(const Value *V) {
   // If we already have an SDValue for this value, use it. It's important
   // to do this first, so that we don't create a CopyFromReg if we already
   // have a regular SDValue.
   SDValue &N = NodeMap[V];
   if (N.getNode()) return N;
 
static bool isVectorReductionOp(const User *I) {
   }
   return ReduxExtracted;
 }
 
 void SelectionDAGBuilder::visitBinary(const User &I, unsigned OpCode) {
   SDValue Op1 = getValue(I.getOperand(0));
   SDValue Op2 = getValue(I.getOperand(1));
 
-  bool nuw = false;
-  bool nsw = false;
-  bool exact = false;
-  bool vec_redux = false;
-  FastMathFlags FMF;
-
-  if (const OverflowingBinaryOperator *OFBinOp =
-          dyn_cast<const OverflowingBinaryOperator>(&I)) {
-    nuw = OFBinOp->hasNoUnsignedWrap();
-    nsw = OFBinOp->hasNoSignedWrap();
-  }
-  if (const PossiblyExactOperator *ExactOp =
-          dyn_cast<const PossiblyExactOperator>(&I))
-    exact = ExactOp->isExact();
-  if (const FPMathOperator *FPOp = dyn_cast<const FPMathOperator>(&I))
-    FMF = FPOp->getFastMathFlags();
-
-  if (isVectorReductionOp(&I)) {
-    vec_redux = true;
+  if (isVectorReductionOp(&I))
     DEBUG(dbgs() << "Detected a reduction operation:" << I << "\n");
-  }
-
-  SDNodeFlags Flags;
-  Flags.setExact(exact);
-  Flags.setNoSignedWrap(nsw);
-  Flags.setNoUnsignedWrap(nuw);
-  Flags.setVectorReduction(vec_redux);
-  Flags.setAllowReciprocal(FMF.allowReciprocal());
-  Flags.setAllowContract(FMF.allowContract());
-  Flags.setNoInfs(FMF.noInfs());
-  Flags.setNoNaNs(FMF.noNaNs());
-  Flags.setNoSignedZeros(FMF.noSignedZeros());
-  Flags.setUnsafeAlgebra(FMF.unsafeAlgebra());
 
   SDValue BinNodeValue = DAG.getNode(OpCode, getCurSDLoc(), Op1.getValueType(),
-                                     Op1, Op2, Flags);
+                                     Op1, Op2);
   setValue(&I, BinNodeValue);
 }
 
 void SelectionDAGBuilder::visitShift(const User &I, unsigned Opcode) {
   SDValue Op1 = getValue(I.getOperand(0));
   SDValue Op2 = getValue(I.getOperand(1));
 
   EVT ShiftTy = DAG.getTargetLoweringInfo().getShiftAmountTy(
bool SelectionDAGBuilder::visitBinaryFloatCall(const CallInst &I,
   SDValue Tmp0 = getValue(I.getArgOperand(0));
   SDValue Tmp1 = getValue(I.getArgOperand(1));
   EVT VT = Tmp0.getValueType();
   setValue(&I, DAG.getNode(Opcode, getCurSDLoc(), VT, Tmp0, Tmp1));
   return true;
 }
 
 void SelectionDAGBuilder::visitCall(const CallInst &I) {
+
   // Handle inline assembly differently.
   if (isa<InlineAsm>(I.getCalledValue())) {
     visitInlineAsm(&I);
     return;
   }
 
   MachineModuleInfo &MMI = DAG.getMachineFunction().getMMI();
   computeUsesVAFloatArgument(I, MMI);

lib/Target/X86/X86ISelLowering.cpp

   // The SSE FP max/min instructions were not designed for this case, but rather
   // to implement:
   //   Min = Op1 < Op0 ? Op1 : Op0
   //   Max = Op1 > Op0 ? Op1 : Op0
   //
   // So they always return Op0 if either input is a NaN. However, we can still
   // use those instructions for fmaxnum by selecting away a NaN input.
 
-  // If either operand is NaN, the 2nd source operand (Op0) is passed through.
-  auto MinMaxOp = N->getOpcode() == ISD::FMAXNUM ? X86ISD::FMAX : X86ISD::FMIN;
-  SDValue MinOrMax = DAG.getNode(MinMaxOp, DL, VT, Op1, Op0);
-  SDValue IsOp0Nan = DAG.getSetCC(DL, SetCCType , Op0, Op0, ISD::SETUO);
+  SDNodeFlags Flags = N->getFlags();
+  bool FastMathFlag = Flags.hasUnsafeAlgebra() || Flags.hasNoNaNs();
 
-  // If Op0 is a NaN, select Op1. Otherwise, select the max. If both operands
-  // are NaN, the NaN value of Op1 is the result.
-  return DAG.getSelect(DL, VT, IsOp0Nan, Op1, MinOrMax);
+   if (!FastMathFlag) {
+     // If either operand is NaN, the 2nd source operand (Op0) is passed through.
+     auto MinMaxOp = N->getOpcode() == ISD::FMAXNUM ? X86ISD::FMAX : X86ISD::FMIN;
+     SDValue MinOrMax = DAG.getNode(MinMaxOp, DL, VT, Op1, Op0);
+     SDValue IsOp0Nan = DAG.getSetCC(DL, SetCCType , Op0, Op0, ISD::SETUO);
+
+     // If Op0 is a NaN, select Op1. Otherwise, select the max. If both operands
+     // are NaN, the NaN value of Op1 is the result.
+     return DAG.getSelect(DL, VT, IsOp0Nan, Op1, MinOrMax);
+   } else {
+     // FastMath assume operands and result are not a NaN.
+     auto MinMaxOp = N->getOpcode() == ISD::FMAXNUM ? ISD::SETUGE : ISD::SETULE;
+     SDValue CCRes = DAG.getSetCC(DL, SetCCType , Op0, Op1, MinMaxOp);
+
+     return DAG.getSelect(DL, VT, CCRes, Op0, Op1);
+   }
 }
 
 /// Do target-specific dag combines on X86ISD::ANDNP nodes.
 static SDValue combineAndnp(SDNode *N, SelectionDAG &DAG,
                             TargetLowering::DAGCombinerInfo &DCI,
                             const X86Subtarget &Subtarget) {
   // ANDNP(0, x) -> x
   if (ISD::isBuildVectorAllZeros(N->getOperand(0).getNode()))

test/CodeGen/X86/pr34149.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 
 ; RUN: llc < %s -mtriple=x86_64-unknown-linux-gnu -mcpu=haswell | FileCheck %s
 
 declare <4 x double> @llvm.minnum.v4f64(<4 x double> %x, <4 x double> %y)
 declare <4 x double> @llvm.maxnum.v4f64(<4 x double> %x, <4 x double> %y)
 
 define <4 x double> @via_minnum(<4 x double> %x, <4 x double> %y) {
 ; CHECK-LABEL: via_minnum:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    vminpd %ymm0, %ymm1, %ymm2
-; CHECK-NEXT:    vcmpunordpd %ymm0, %ymm0, %ymm0
-; CHECK-NEXT:    vblendvpd %ymm0, %ymm1, %ymm2, %ymm0
+; CHECK-NEXT:    vminpd %ymm0, %ymm1, %ymm0
 ; CHECK-NEXT:    retq
   %z = call fast <4 x double> @llvm.minnum.v4f64(<4 x double> %x, <4 x double> %y) readnone
   ret <4 x double> %z
 }
 
 define <4 x double> @via_maxnum(<4 x double> %x, <4 x double> %y) {
 ; CHECK-LABEL: via_maxnum:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    vmaxpd %ymm0, %ymm1, %ymm2
-; CHECK-NEXT:    vcmpunordpd %ymm0, %ymm0, %ymm0
-; CHECK-NEXT:    vblendvpd %ymm0, %ymm1, %ymm2, %ymm0
+; CHECK-NEXT:    vmaxpd %ymm0, %ymm1, %ymm0
 ; CHECK-NEXT:    retq
   %z = call fast <4 x double> @llvm.maxnum.v4f64(<4 x double> %x, <4 x double> %y) readnone
   ret <4 x double> %z
 }
 
 define <4 x double> @via_fcmp(<4 x double> %x, <4 x double> %y) {
 ; CHECK-LABEL: via_fcmp:
 ; CHECK:       # BB#0:
 ; CHECK-NEXT:    vminpd %ymm0, %ymm1, %ymm0
 ; CHECK-NEXT:    retq
   %c = fcmp ule <4 x double> %x, %y
   %z = select <4 x i1> %c, <4 x double> %x, <4 x double> %y
   ret <4 x double> %z
 }