[InstCombine] Add new rule for MIN(MAX(~A, ~B), ~C) et. al.

[sanjoy]

Summary

Optimizing these well are especially interesting for IRCE since it
"clamps" values by generating this sort of pattern through SCEV
expressions.

Depends on D9352.

[majnemer]

lib/Transforms/InstCombine/InstCombineSelect.cpp

24 ↗

(On Diff #24660)

getInverseMinMaxSelectPattern would be more conforming to the coding standards.

40 ↗

(On Diff #24660)

Let's call this generateMinMaxSelectPattern instead.

43–57 ↗

(On Diff #24660)

It might be late but why the lambda? I guess it makes the control flow a little nicer. How about we just split it out to another function?

902 ↗

(On Diff #24660)

Can we kill this newline?

903 ↗

(On Diff #24660)

The other transforms are a little more concrete in that they are described with a specific SelectPatternFlavor and an actual value for the constant. I think the abstract pattern would still be good to keep around though.

Speaking of which, I'm going to have to admit that I am not quite sure what ~! means exactly.

[sanjoy]

lib/Transforms/InstCombine/InstCombineSelect.cpp

24 ↗

(On Diff #24660)

done

40 ↗

(On Diff #24660)

done

43–57 ↗

(On Diff #24660)

How about we just split it out to another function?

done

902 ↗

(On Diff #24660)

done

903 ↗

(On Diff #24660)

The abstract pattern does not abstract over very much. :) I'll just document the four possibilities explicitly.

[sanjoy]

• address review comments

[majnemer]

LGTM

llvm/trunk/lib/Transforms/InstCombine/InstCombineSelect.cpp

 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/IR/PatternMatch.h"
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "instcombine"
 
+static SelectPatternFlavor
+getInverseMinMaxSelectPattern(SelectPatternFlavor SPF) {
+  switch (SPF) {
+  default:
+    llvm_unreachable("unhandled!");
+
+  case SPF_SMIN:
+    return SPF_SMAX;
+  case SPF_UMIN:
+    return SPF_UMAX;
+  case SPF_SMAX:
+    return SPF_SMIN;
+  case SPF_UMAX:
+    return SPF_UMIN;
+  }
+}
+
+static CmpInst::Predicate getICmpPredicateForMinMax(SelectPatternFlavor SPF) {
+  switch (SPF) {
+  default:
+    llvm_unreachable("unhandled!");
+
+  case SPF_SMIN:
+    return ICmpInst::ICMP_SLT;
+  case SPF_UMIN:
+    return ICmpInst::ICMP_ULT;
+  case SPF_SMAX:
+    return ICmpInst::ICMP_SGT;
+  case SPF_UMAX:
+    return ICmpInst::ICMP_UGT;
+  }
+}
+
+static Value *generateMinMaxSelectPattern(InstCombiner::BuilderTy *Builder,
+                                          SelectPatternFlavor SPF, Value *A,
+                                          Value *B) {
+  CmpInst::Predicate Pred = getICmpPredicateForMinMax(SPF);
+  return Builder->CreateSelect(Builder->CreateICmp(Pred, A, B), A, B);
+}
+
 /// MatchSelectPattern - Pattern match integer [SU]MIN, [SU]MAX, and ABS idioms,
 /// returning the kind and providing the out parameter results if we
 /// successfully match.
 static SelectPatternFlavor
 MatchSelectPattern(Value *V, Value *&LHS, Value *&RHS) {
   SelectInst *SI = dyn_cast<SelectInst>(V);
   if (!SI) return SPF_UNKNOWN;
 
Instruction *InstCombiner::FoldSPFofSPF(Instruction *Inner,
   // NABS(ABS(X)) -> NABS(X)
   if ((SPF1 == SPF_ABS && SPF2 == SPF_NABS) ||
       (SPF1 == SPF_NABS && SPF2 == SPF_ABS)) {
     SelectInst *SI = cast<SelectInst>(Inner);
     Value *NewSI = Builder->CreateSelect(
         SI->getCondition(), SI->getFalseValue(), SI->getTrueValue());
     return ReplaceInstUsesWith(Outer, NewSI);
   }
+
+  auto IsFreeOrProfitableToInvert =
+      [&](Value *V, Value *&NotV, bool &ElidesXor) {
+    if (match(V, m_Not(m_Value(NotV)))) {
+      // If V has at most 2 uses then we can get rid of the xor operation
+      // entirely.
+      ElidesXor |= !V->hasNUsesOrMore(3);
+      return true;
+    }
+
+    if (IsFreeToInvert(V, !V->hasNUsesOrMore(3))) {
+      NotV = nullptr;
+      return true;
+    }
+
+    return false;
+  };
+
+  Value *NotA, *NotB, *NotC;
+  bool ElidesXor = false;
+
+  // MIN(MIN(~A, ~B), ~C) == ~MAX(MAX(A, B), C)
+  // MIN(MAX(~A, ~B), ~C) == ~MAX(MIN(A, B), C)
+  // MAX(MIN(~A, ~B), ~C) == ~MIN(MAX(A, B), C)
+  // MAX(MAX(~A, ~B), ~C) == ~MIN(MIN(A, B), C)
+  //
+  // This transform is performance neutral if we can elide at least one xor from
+  // the set of three operands, since we'll be tacking on an xor at the very
+  // end.
+  if (IsFreeOrProfitableToInvert(A, NotA, ElidesXor) &&
+      IsFreeOrProfitableToInvert(B, NotB, ElidesXor) &&
+      IsFreeOrProfitableToInvert(C, NotC, ElidesXor) && ElidesXor) {
+    if (!NotA)
+      NotA = Builder->CreateNot(A);
+    if (!NotB)
+      NotB = Builder->CreateNot(B);
+    if (!NotC)
+      NotC = Builder->CreateNot(C);
+
+    Value *NewInner = generateMinMaxSelectPattern(
+        Builder, getInverseMinMaxSelectPattern(SPF1), NotA, NotB);
+    Value *NewOuter = Builder->CreateNot(generateMinMaxSelectPattern(
+        Builder, getInverseMinMaxSelectPattern(SPF2), NewInner, NotC));
+    return ReplaceInstUsesWith(Outer, NewOuter);
+  }
+
   return nullptr;
 }
 
 /// foldSelectICmpAnd - If one of the constants is zero (we know they can't
 /// both be) and we have an icmp instruction with zero, and we have an 'and'
 /// with the non-constant value and a power of two we can turn the select
 /// into a shift on the result of the 'and'.
 static Value *foldSelectICmpAnd(const SelectInst &SI, ConstantInt *TrueVal,

llvm/trunk/test/Transforms/InstCombine/max-of-nots.ll

entry:
   %not_y = sub i32 -1, %y
   %cmp = icmp sgt i32 %not_value, %not_y
 ; CHECK: %not_value = sub i32 3, %x
 ; CHECK: %cmp = icmp sgt i32 %not_value, %not_y
   %not_min = select i1 %cmp, i32 %not_value, i32 %not_y
   %min = sub i32 -1, %not_min
   ret i32 %min
 }
+
+define i32 @max_of_nots(i32 %x, i32 %y) {
+; CHECK-LABEL: @max_of_nots(
+; CHECK-NEXT: icmp
+; CHECK-NEXT: select
+; CHECK-NEXT: icmp
+; CHECK-NEXT: select
+; CHECK-NEXT: xor
+; CHECK-NEXT: ret
+  %c0 = icmp sgt i32 %y, 0
+  %xor_y = xor i32 %y, -1
+  %s0 = select i1 %c0, i32 %xor_y, i32 -1
+  %xor_x = xor i32 %x, -1
+  %c1 = icmp slt i32 %s0, %xor_x
+  %smax96 = select i1 %c1, i32 %xor_x, i32 %s0
+  ret i32 %smax96
+}