Add an instcombine rule to optimize max(~a,~b) to ~min(a, b) when profitable

[sanjoy]

Summary

This case is interesting because ScalarEvolutionExpander lowers min(a, b) as ~max(~a,~b). I think the profitability heuristics can be made more clever/aggressive, but this is a start.

A clang bootstrapped with this change passes make check. The rule fires 159 times.

[majnemer]

lib/Transforms/InstCombine/InstCombineSelect.cpp

1169–1172

Can we improve isFreeToInvert and just use that instead?

1183–1184

This doesn't look formatted correctly, can you please run clang-format on this?

[filcab]

lib/Transforms/InstCombine/InstCombineSelect.cpp

1182

We do this test here, but the calculation for Profitable only cares about Not.
Do we really need this (or should we just check for this in the Porfitable calculation too)?

[sanjoy]

lib/Transforms/InstCombine/InstCombineSelect.cpp

1182

The Profitable check is intentionally more restrictive. You don't gain or lose anything if you compute (-1-Const) - A instead of Const + A, so there is no penalty. But the profitable check is specifically about figuring out if computing ~V instead of V *gains* you anything -- if V was xor P, -1 then you can now get away without actually computing the xor. The profitability check has to be stronger than a break-even since this rule introduces a not and that extra work has to be justified.

[sanjoy]

Address review comments.

[majnemer]

lib/Transforms/InstCombine/InstCombineInternal.h

85 ↗

(On Diff #20492)

I think you are missing a "to" between "intends" and "remove".

88 ↗

(On Diff #20492)

Is WillInvertAllUses ever different from V->hasOneUse()? If not, I think it would be nicer to have this function not take the extra argument and just compute the predicate locally.

[sanjoy]

lib/Transforms/InstCombine/InstCombineInternal.h

85 ↗

(On Diff #20492)

Yup, will fix.

88 ↗

(On Diff #20492)

The new uses of IsFreeToInvert (in InstCombineSelect) have WillInvertAllUses as V->hasNUses(2).

[majnemer]

LGTM

lib/Transforms/InstCombine/InstCombineSelect.cpp

if (Instruction *FI = dyn_cast<Instruction>(FalseVal))
         }
       }
 
   // See if we can fold the select into one of our operands.
   if (SI.getType()->isIntegerTy()) {
     if (Instruction *FoldI = FoldSelectIntoOp(SI, TrueVal, FalseVal))
       return FoldI;
 
+    Value *LHS, *RHS, *LHS2, *RHS2;
+    SelectPatternFlavor SPF = MatchSelectPattern(&SI, LHS, RHS);
+
     // MAX(MAX(a, b), a) -> MAX(a, b)
     // MIN(MIN(a, b), a) -> MIN(a, b)
     // MAX(MIN(a, b), a) -> a
     // MIN(MAX(a, b), a) -> a
-    Value *LHS, *RHS, *LHS2, *RHS2;
-    if (SelectPatternFlavor SPF = MatchSelectPattern(&SI, LHS, RHS)) {
+    if (SPF) {
       if (SelectPatternFlavor SPF2 = MatchSelectPattern(LHS, LHS2, RHS2))
         if (Instruction *R = FoldSPFofSPF(cast<Instruction>(LHS),SPF2,LHS2,RHS2,
                                           SI, SPF, RHS))
           return R;
       if (SelectPatternFlavor SPF2 = MatchSelectPattern(RHS, LHS2, RHS2))
         if (Instruction *R = FoldSPFofSPF(cast<Instruction>(RHS),SPF2,LHS2,RHS2,
                                           SI, SPF, LHS))
           return R;
     }
 
+    // MAX(~a, ~b) -> ~MIN(a, b)
+    if (SPF == SPF_SMAX || SPF == SPF_UMAX) {
+
+      // Is it free to change the ICmpInst and the SelectInst using V to use ~V
+      // instead?
+      auto IsFreeToInvert = [](Value *V) {
+        if (match(V, m_Not(m_Value())))
+          return true;
+
+        // If the `V` is of the form `A + Constant` then `-1 - V` can be folded
+        // into `(-1 - Constant) -A`.
+        //
+        // TODO: we can be smarter on the hasNUses(2) part if needed.
+        BinaryOperator *BO = dyn_cast<BinaryOperator>(V);
+        if (BO && V->hasNUses(2))
+          if (BO->getOpcode() == Instruction::Add ||
+              BO->getOpcode() == Instruction::Sub)
+            return isa<Constant>(BO->getOperand(0)) ||
+              isa<Constant>(BO->getOperand(1));
+
+        return false;
+      };
+
+      if (IsFreeToInvert(LHS) && IsFreeToInvert(RHS)) {
+        // Even when using `a` instead of `~a` and `b` instead of `~b` is free,
+        // the transform itself is a pessimization unless the extra bitwise not
+        // on the select can be justified.  TODO: we can be smarter here,
+        // especially in recognizing chains of smin / umin operations.
+
+        bool Profitable =
+          (LHS->hasNUses(2) && match(LHS, m_Not(m_Value()))) ||
+          (RHS->hasNUses(2) && match(RHS, m_Not(m_Value()))) ||
+          (SI.hasOneUse() && match(*SI.user_begin(), m_Not(m_Value())));
+
+        if (Profitable) {
+          Value *NewLHS = Builder->CreateNot(LHS);
+          Value *NewRHS = Builder->CreateNot(RHS);
+          Value *NewCmp = SPF == SPF_SMAX ?
+            Builder->CreateICmpSLT(NewLHS, NewRHS) :
+            Builder->CreateICmpULT(NewLHS, NewRHS);
+          Value *NewSI = Builder->CreateNot(
+            Builder->CreateSelect(NewCmp, NewLHS, NewRHS));
+          return ReplaceInstUsesWith(SI, NewSI);
+        }
+      }
+    }
+
     // TODO.
     // ABS(-X) -> ABS(X)
   }
 
   // See if we can fold the select into a phi node if the condition is a select.
   if (isa<PHINode>(SI.getCondition()))
     // The true/false values have to be live in the PHI predecessor's blocks.
     if (CanSelectOperandBeMappingIntoPredBlock(TrueVal, SI) &&

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

+; RUN: opt -S -instcombine < %s | FileCheck %s
+
+define i32 @compute_min_2(i32 %x, i32 %y) {
+; CHECK-LABEL: compute_min_2
+ entry:
+  %not_x = sub i32 -1, %x
+  %not_y = sub i32 -1, %y
+  %cmp = icmp sgt i32 %not_x, %not_y
+  %not_min = select i1 %cmp, i32 %not_x, i32 %not_y
+  %min = sub i32 -1, %not_min
+  ret i32 %min
+
+; CHECK: %0 = icmp slt i32 %x, %y
+; CHECK-NEXT: %1 = select i1 %0, i32 %x, i32 %y
+; CHECK-NEXT: ret i32 %1
+}
+
+define i32 @compute_min_3(i32 %x, i32 %y, i32 %z) {
+; CHECK-LABEL: compute_min_3
+ entry:
+  %not_x = sub i32 -1, %x
+  %not_y = sub i32 -1, %y
+  %not_z = sub i32 -1, %z
+  %cmp_1 = icmp sgt i32 %not_x, %not_y
+  %not_min_1 = select i1 %cmp_1, i32 %not_x, i32 %not_y
+  %cmp_2 = icmp sgt i32 %not_min_1, %not_z
+  %not_min_2 = select i1 %cmp_2, i32 %not_min_1, i32 %not_z
+  %min = sub i32 -1, %not_min_2
+  ret i32 %min
+
+; CHECK: %0 = icmp slt i32 %x, %y
+; CHECK-NEXT: %1 = select i1 %0, i32 %x, i32 %y
+; CHECK-NEXT: %2 = icmp slt i32 %1, %z
+; CHECK-NEXT: %3 = select i1 %2, i32 %1, i32 %z
+; CHECK-NEXT: ret i32 %3
+}
+
+define i32 @compute_min_arithmetic(i32 %x, i32 %y) {
+; CHECK-LABEL: compute_min_arithmetic
+ entry:
+  %not_value = sub i32 3, %x
+  %not_y = sub i32 -1, %y
+  %cmp = icmp sgt i32 %not_value, %not_y
+  %not_min = select i1 %cmp, i32 %not_value, i32 %not_y
+  ret i32 %not_min
+
+; CHECK: %0 = add i32 %x, -4
+; CHECK-NEXT: %1 = icmp slt i32 %0, %y
+; CHECK-NEXT: %2 = select i1 %1, i32 %0, i32 %y
+; CHECK-NEXT: %3 = xor i32 %2, -1
+; CHECK-NEXT: ret i32 %3
+}
+
+declare void @fake_use(i32)
+
+define i32 @compute_min_pessimization(i32 %x, i32 %y) {
+; CHECK-LABEL: compute_min_pessimization
+ entry:
+  %not_value = sub i32 3, %x
+  call void @fake_use(i32 %not_value)
+  %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
+}