[GlobalISel] Combine select + fcmp to fminnum/fmaxnum/fminimum/fmaximum

[paquette]

Summary

This is a partial port of the code used by the SelectionDAGBuilder to translate selects.

In particular, see matchSelectPattern in ValueTracking.cpp. This is a GISel-equivalent of the portion which handles fminnum/fmaxnum/fminimum/fmaximum.

I tried to set it up so it'd be easy to add the non-FP cases. Those are simpler. On the AArch64-end, it seems like the FP cases are more important for perf right now, so I bit the bullet and went at the more complicated problem. :)

I elected to do this as a post-legalize combine rather than in the IRTranslator because

• Deciding which fmax/fmin to use can depend on legalization rules
• Philosophically-speaking (TM), putting it in a combine just feels cleaner
• Being able to enable/disable the combine is handy

Another option would be to use the ValueTracking code in the IRTranslator and match what SelectionDAGBuilder::visitSelect does. I think that may be somewhat annoying since we'd need to write lowerings back into the selects in the legalizer. I'm not strongly opposed to the approach.

We'd also want to be careful with vector selects once that's implemented, which explicitly check if a vector select is legal on the target. That'd probably need a hook.

From what I can tell, doing this as a combine is probably a cleaner option long-term.

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

5797–5798

The 0 behavior is specified as ordering -0<0 for FMAXIMUM/FMINIMUM

5831

Leftover debug printing

[paquette]

• Allow 0 for G_FMAXIMUM/G_FMINIMUM cases
• Remove debug code

[tschuett]

llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h

811

I prefer enum class for new code, but it is up to you.

[aemerson]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

5722

Can this be the actual Predicate type instead of unsigned?

5750–5753

What's the reason for choosing this particular ordering of legality checks such that we prefer G_FMINNUM?

[paquette]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

5750–5753

I was just matching the behaviour in SelectionDAGBuilder so I'm not entirely sure:

case SPNB_RETURNS_ANY: {
  if (TLI.isOperationLegalOrCustom(ISD::FMINNUM, VT))
    Opc = ISD::FMINNUM;
  else if (TLI.isOperationLegalOrCustom(ISD::FMINIMUM, VT))
    Opc = ISD::FMINIMUM;

Maybe @arsenm knows better since I think he wrote the original code. (https://reviews.llvm.org/rGfabab4b7dd7d4ccefec2bb6cd405044429637ba6)

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

5750–5753

FMINIMUM/FMAXIMUM are not widely used/available. The DAG version is more strict in checking for isLegalOrCustom, whereas here you're forming them before legalize anyway.

I think this should follow that and look for some positive legality only. The trickier case I'm worried about is on vector types which will be split later. We probably should have a utility that looks like the getTypeAction loop for finding the ultimate legalized type

[arsenm]

Reverse ping

[aemerson]

Second reverse ping.

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

5750–5753

Since this is handling RETURNS_ANY before legalization seems fine to me?

[paquette]

rebase + check isLegal + use enum class

[aemerson]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

5941

You can just cast to GSelect and use the convenience methods.

[foad]

Just curious: why do we need to do this in isel? Is there a reason it cannot or does not get done at the IR level?

[arsenm]

In D116702#3678812, @foad wrote:

Just curious: why do we need to do this in isel? Is there a reason it cannot or does not get done at the IR level?

I think this is one where we need both. First, selects are likely to appear out of legalization. Second, the IR doesn't have the full range of min/max opcodes (it doesn't have the _IEEE versions, and the intrinsics were incorrectly named)

llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h

 
 #ifndef LLVM_CODEGEN_GLOBALISEL_COMBINERHELPER_H
 #define LLVM_CODEGEN_GLOBALISEL_COMBINERHELPER_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/CodeGen/Register.h"
 #include "llvm/Support/LowLevelTypeImpl.h"
+#include "llvm/IR/InstrTypes.h"
 #include <functional>
 
 namespace llvm {
 
 class GISelChangeObserver;
 class APFloat;
 class APInt;
 class GPtrAdd;
public:
   bool matchSelectToLogical(MachineInstr &MI, BuildFnTy &MatchInfo);
 
   bool matchCombineFMinMaxNaN(MachineInstr &MI, unsigned &Info);
 
   /// Transform G_ADD(x, G_SUB(y, x)) to y.
   /// Transform G_ADD(G_SUB(y, x), x) to y.
   bool matchAddSubSameReg(MachineInstr &MI, Register &Src);
 
+  /// \returns true if it is possible to simplify a select instruction \p MI
+  /// to a min/max instruction of some sort.
+  bool matchSimplifySelectToMinMax(MachineInstr &MI, BuildFnTy &MatchInfo);
+
 private:
   /// Given a non-indexed load or store instruction \p MI, find an offset that
   /// can be usefully and legally folded into it as a post-indexing operation.
   ///
   /// \returns true if a candidate is found.
   bool findPostIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base,
                               Register &Offset);
 
findLoadOffsetsForLoadOrCombine(
       SmallDenseMap<int64_t, int64_t, 8> &MemOffset2Idx,
       const SmallVector<Register, 8> &RegsToVisit,
       const unsigned MemSizeInBits);
 
   /// Examines the G_PTR_ADD instruction \p PtrAdd and determines if performing
   /// a re-association of its operands would break an existing legal addressing
   /// mode that the address computation currently represents.
   bool reassociationCanBreakAddressingModePattern(MachineInstr &PtrAdd);
+
+  /// Behavior when a floating point min/max is given one NaN and one
+  /// non-NaN as input.
+  enum class SelectPatternNaNBehaviour {
+    NOT_APPLICABLE = 0, /// NaN behavior not applicable.
+    RETURNS_NAN,        /// Given one NaN input, returns the NaN.
+    RETURNS_OTHER,      /// Given one NaN input, returns the non-NaN.
+    RETURNS_ANY /// Given one NaN input, can return either (or both operands are
+                /// known non-NaN.)
+  };
+
+  /// \returns which of \p LHS and \p RHS would be the result of a non-equality
+  /// floating point comparison where one of \p LHS and \p RHS may be NaN.
+  ///
+  /// If both \p LHS and \p RHS may be NaN, returns
+  /// SelectPatternNaNBehaviour::NOT_APPLICABLE.
+  SelectPatternNaNBehaviour
+  computeRetValAgainstNaN(Register LHS, Register RHS,
+                          bool IsOrderedComparison) const;
+
+  /// Determines the floating point min/max opcode which should be used for
+  /// a G_SELECT fed by a G_FCMP with predicate \p Pred.
+  ///
+  /// \returns 0 if this G_SELECT should not be combined to a floating point
+  /// min or max. If it should be combined, returns one of
+  ///
+  /// * G_FMAXNUM
+  /// * G_FMAXIMUM
+  /// * G_FMINNUM
+  /// * G_FMINIMUM
+  ///
+  /// Helper function for matchFPSelectToMinMax.
+  unsigned getFPMinMaxOpcForSelect(CmpInst::Predicate Pred, LLT DstTy,
+                                   SelectPatternNaNBehaviour VsNaNRetVal) const;
+
+  /// Handle floating point cases for matchSimplifySelectToMinMax.
+  ///
+  /// E.g.
+  ///
+  /// select (fcmp uge x, 1.0) x, 1.0 -> fmax x, 1.0
+  /// select (fcmp uge x, 1.0) 1.0, x -> fminnm x, 1.0
+  bool matchFPSelectToMinMax(Register Dst, Register Cond, Register TrueVal,
+                             Register FalseVal, BuildFnTy &MatchInfo);
 };
 } // namespace llvm
 
 #endif

llvm/include/llvm/Target/GlobalISel/Combine.td

 // Transform (add (sub y, x), x) -> y
 def add_sub_reg: GICombineRule <
   (defs root:$root, register_matchinfo:$matchinfo),
   (match (wip_match_opcode G_ADD):$root,
          [{ return Helper.matchAddSubSameReg(*${root}, ${matchinfo}); }]),
   (apply [{ return Helper.replaceSingleDefInstWithReg(*${root},
                                                       ${matchinfo}); }])>;
 
+def select_to_minmax: GICombineRule<
+  (defs root:$root, build_fn_matchinfo:$info),
+  (match (wip_match_opcode G_SELECT):$root,
+         [{ return Helper.matchSimplifySelectToMinMax(*${root}, ${info}); }]),
+  (apply [{ Helper.applyBuildFn(*${root}, ${info}); }])>;
+
 // FIXME: These should use the custom predicate feature once it lands.
 def undef_combines : GICombineGroup<[undef_to_fp_zero, undef_to_int_zero,
                                      undef_to_negative_one,
                                      binop_left_undef_to_zero,
                                      binop_right_undef_to_undef,
                                      propagate_undef_any_op,
                                      propagate_undef_all_ops,
                                      propagate_undef_shuffle_mask,

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

if ((mi_match(RHSReg, MRI, m_GFPExt(m_GFNeg(m_MInstr(FMulMI)))) ||
     };
     return true;
   }
 
   return false;
 }
 
 bool CombinerHelper::matchSelectToLogical(MachineInstr &MI,
                                           BuildFnTy &MatchInfo) {
   GSelect &Sel = cast<GSelect>(MI);
   Register DstReg = Sel.getReg(0);
   Register Cond = Sel.getCondReg();
   Register TrueReg = Sel.getTrueReg();
   Register FalseReg = Sel.getFalseReg();
 
   auto *TrueDef = getDefIgnoringCopies(TrueReg, MRI);
   auto *FalseDef = getDefIgnoringCopies(FalseReg, MRI);
bool CombinerHelper::matchSelectToLogical(MachineInstr &MI,
   if (Cond == TrueReg || (MaybeCstTrue && MaybeCstTrue->isOne())) {
     MatchInfo = [=](MachineIRBuilder &MIB) {
       MIB.buildOr(DstReg, Cond, FalseReg);
     };
     return true;
   }
 
   // select Cond, T, Cond --> and Cond, T
   // select Cond, T, 0    --> and Cond, T
   auto MaybeCstFalse = isConstantOrConstantSplatVector(*FalseDef, MRI);
   if (Cond == FalseReg || (MaybeCstFalse && MaybeCstFalse->isZero())) {
     MatchInfo = [=](MachineIRBuilder &MIB) {
       MIB.buildAnd(DstReg, Cond, TrueReg);
     };
     return true;
   }
 
  // select Cond, T, 1 --> or (not Cond), T
   if (MaybeCstFalse && MaybeCstFalse->isOne()) {
     MatchInfo = [=](MachineIRBuilder &MIB) {
case TargetOpcode::G_FMAXIMUM:
     PropagateNaN = true;
     break;
   }
 
   auto MatchNaN = [&](unsigned Idx) {
     Register MaybeNaNReg = MI.getOperand(Idx).getReg();
     const ConstantFP *MaybeCst = getConstantFPVRegVal(MaybeNaNReg, MRI);
     if (!MaybeCst || !MaybeCst->getValueAPF().isNaN())
       return false;
     IdxToPropagate = PropagateNaN ? Idx : (Idx == 1 ? 2 : 1);
     return true;
   };
 
   return MatchNaN(1) || MatchNaN(2);
 }
 
 bool CombinerHelper::matchAddSubSameReg(MachineInstr &MI, Register &Src) {
   assert(MI.getOpcode() == TargetOpcode::G_ADD && "Expected a G_ADD");
   Register LHS = MI.getOperand(1).getReg();
   Register RHS = MI.getOperand(2).getReg();
 
   // Helper lambda to check for opportunities for
   // A + (B - A) -> B
   // (B - A) + A -> B
   auto CheckFold = [&](Register MaybeSub, Register MaybeSameReg) {
     Register Reg;
     return mi_match(MaybeSub, MRI, m_GSub(m_Reg(Src), m_Reg(Reg))) &&
            Reg == MaybeSameReg;
   };
   return CheckFold(LHS, RHS) || CheckFold(RHS, LHS);
 }
 
+unsigned CombinerHelper::getFPMinMaxOpcForSelect(
+    CmpInst::Predicate Pred, LLT DstTy,
+    SelectPatternNaNBehaviour VsNaNRetVal) const {
+  assert(VsNaNRetVal != SelectPatternNaNBehaviour::NOT_APPLICABLE &&
+         "Expected a NaN behaviour?");
+  // Choose an opcode based off of legality or the behaviour when one of the
+  // LHS/RHS may be NaN.
+  switch (Pred) {
+  default:
+    return 0;
+  case CmpInst::FCMP_UGT:
+  case CmpInst::FCMP_UGE:
+  case CmpInst::FCMP_OGT:
+  case CmpInst::FCMP_OGE:
+    if (VsNaNRetVal == SelectPatternNaNBehaviour::RETURNS_OTHER)
+      return TargetOpcode::G_FMAXNUM;
+    if (VsNaNRetVal == SelectPatternNaNBehaviour::RETURNS_NAN)
+      return TargetOpcode::G_FMAXIMUM;
+    if (isLegal({TargetOpcode::G_FMAXNUM, {DstTy}}))
+      return TargetOpcode::G_FMAXNUM;
+    if (isLegal({TargetOpcode::G_FMAXIMUM, {DstTy}}))
+      return TargetOpcode::G_FMAXIMUM;
+    return 0;
+  case CmpInst::FCMP_ULT:
+  case CmpInst::FCMP_ULE:
+  case CmpInst::FCMP_OLT:
+  case CmpInst::FCMP_OLE:
+    if (VsNaNRetVal == SelectPatternNaNBehaviour::RETURNS_OTHER)
+      return TargetOpcode::G_FMINNUM;
+    if (VsNaNRetVal == SelectPatternNaNBehaviour::RETURNS_NAN)
+      return TargetOpcode::G_FMINIMUM;
+    if (isLegal({TargetOpcode::G_FMINNUM, {DstTy}}))
+      return TargetOpcode::G_FMINNUM;
+    if (!isLegal({TargetOpcode::G_FMINIMUM, {DstTy}}))
+      return 0;
+    return TargetOpcode::G_FMINIMUM;
+  }
+}
+
+CombinerHelper::SelectPatternNaNBehaviour
+CombinerHelper::computeRetValAgainstNaN(Register LHS, Register RHS,
+                                        bool IsOrderedComparison) const {
+  bool LHSSafe = isKnownNeverNaN(LHS, MRI);
+  bool RHSSafe = isKnownNeverNaN(RHS, MRI);
+  // Completely unsafe.
+  if (!LHSSafe && !RHSSafe)
+    return SelectPatternNaNBehaviour::NOT_APPLICABLE;
+  if (LHSSafe && RHSSafe)
+    return SelectPatternNaNBehaviour::RETURNS_ANY;
+  // An ordered comparison will return false when given a NaN, so it
+  // returns the RHS.
+  if (IsOrderedComparison)
+    return LHSSafe ? SelectPatternNaNBehaviour::RETURNS_NAN
+                   : SelectPatternNaNBehaviour::RETURNS_OTHER;
+  // An unordered comparison will return true when given a NaN, so it
+  // returns the LHS.
+  return LHSSafe ? SelectPatternNaNBehaviour::RETURNS_OTHER
+                 : SelectPatternNaNBehaviour::RETURNS_NAN;
+}
+
+bool CombinerHelper::matchFPSelectToMinMax(Register Dst, Register Cond,
+                                           Register TrueVal, Register FalseVal,
+                                           BuildFnTy &MatchInfo) {
+  // Match: select (fcmp cond x, y) x, y
+  //        select (fcmp cond x, y) y, x
+  // And turn it into fminnum/fmaxnum or fmin/fmax based off of the condition.
+  LLT DstTy = MRI.getType(Dst);
+  // Bail out early on pointers, since we'll never want to fold to a min/max.
+  // TODO: Handle vectors.
+  if (DstTy.isPointer() || DstTy.isVector())
+    return false;
+  // Match a floating point compare with a less-than/greater-than predicate.
+  // TODO: Allow multiple users of the compare if they are all selects.
+  CmpInst::Predicate Pred;
+  Register CmpLHS, CmpRHS;
+  if (!mi_match(Cond, MRI,
+                m_OneNonDBGUse(
+                    m_GFCmp(m_Pred(Pred), m_Reg(CmpLHS), m_Reg(CmpRHS)))) ||
+      CmpInst::isEquality(Pred))
+    return false;
+  SelectPatternNaNBehaviour ResWithKnownNaNInfo =
+      computeRetValAgainstNaN(CmpLHS, CmpRHS, CmpInst::isOrdered(Pred));
+  if (ResWithKnownNaNInfo == SelectPatternNaNBehaviour::NOT_APPLICABLE)
+    return false;
+  if (TrueVal == CmpRHS && FalseVal == CmpLHS) {
+    std::swap(CmpLHS, CmpRHS);
+    Pred = CmpInst::getSwappedPredicate(Pred);
+    if (ResWithKnownNaNInfo == SelectPatternNaNBehaviour::RETURNS_NAN)
+      ResWithKnownNaNInfo = SelectPatternNaNBehaviour::RETURNS_OTHER;
+    else if (ResWithKnownNaNInfo == SelectPatternNaNBehaviour::RETURNS_OTHER)
+      ResWithKnownNaNInfo = SelectPatternNaNBehaviour::RETURNS_NAN;
+  }
+  if (TrueVal != CmpLHS || FalseVal != CmpRHS)
+    return false;
+  // Decide what type of max/min this should be based off of the predicate.
+  unsigned Opc = getFPMinMaxOpcForSelect(Pred, DstTy, ResWithKnownNaNInfo);
+  if (!Opc || !isLegal({Opc, {DstTy}}))
+    return false;
+  // Comparisons between signed zero and zero may have different results...
+  // unless we have fmaximum/fminimum. In that case, we know -0 < 0.
+  if (Opc != TargetOpcode::G_FMAXIMUM && Opc != TargetOpcode::G_FMINIMUM) {
+    // We don't know if a comparison between two 0s will give us a consistent
+    // result. Be conservative and only proceed if at least one side is
+    // non-zero.
+    auto KnownNonZeroSide = getFConstantVRegValWithLookThrough(CmpLHS, MRI);
+    if (!KnownNonZeroSide || !KnownNonZeroSide->Value.isNonZero()) {
+      KnownNonZeroSide = getFConstantVRegValWithLookThrough(CmpRHS, MRI);
+      if (!KnownNonZeroSide || !KnownNonZeroSide->Value.isNonZero())
+        return false;
+    }
+  }
+  MatchInfo = [=](MachineIRBuilder &B) {
+    B.buildInstr(Opc, {Dst}, {CmpLHS, CmpRHS});
+  };
+  return true;
+}
+
+bool CombinerHelper::matchSimplifySelectToMinMax(MachineInstr &MI,
+                                                 BuildFnTy &MatchInfo) {
+  // TODO: Handle integer cases.
+  assert(MI.getOpcode() == TargetOpcode::G_SELECT);
+  // Condition may be fed by a truncated compare.
+  Register Cond = MI.getOperand(1).getReg();
+  Register MaybeTrunc;
+  if (mi_match(Cond, MRI, m_OneNonDBGUse(m_GTrunc(m_Reg(MaybeTrunc)))))
+    Cond = MaybeTrunc;
+  Register Dst = MI.getOperand(0).getReg();
+  Register TrueVal = MI.getOperand(2).getReg();
+  Register FalseVal = MI.getOperand(3).getReg();
+  return matchFPSelectToMinMax(Dst, Cond, TrueVal, FalseVal, MatchInfo);
+}
+
 bool CombinerHelper::tryCombine(MachineInstr &MI) {
   if (tryCombineCopy(MI))
     return true;
   if (tryCombineExtendingLoads(MI))
     return true;
   if (tryCombineIndexedLoadStore(MI))
     return true;
   return false;
 }

llvm/lib/Target/AArch64/AArch64Combine.td

: GICombinerHelper<"AArch64GenPostLegalizerCombinerHelper",
                         redundant_and, xor_of_and_with_same_reg,
                         extractvecelt_pairwise_add, redundant_or,
                         mul_const, redundant_sext_inreg,
                         form_bitfield_extract, rotate_out_of_range,
                         icmp_to_true_false_known_bits, merge_unmerge,
                         select_combines, fold_merge_to_zext,
                         constant_fold, identity_combines,
                         ptr_add_immed_chain, overlapping_and,
-                        split_store_zero_128, undef_combines]> {
+                        split_store_zero_128, undef_combines,
+                        select_to_minmax]> {
   let DisableRuleOption = "aarch64postlegalizercombiner-disable-rule";
 }