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 ↗

(On Diff #20488)

Can we improve isFreeToInvert and just use that instead?

1183–1184 ↗

(On Diff #20488)

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

[filcab]

lib/Transforms/InstCombine/InstCombineSelect.cpp

1182 ↗

(On Diff #20488)

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 ↗

(On Diff #20488)

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

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

 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Transforms/Utils/CmpInstAnalysis.h"
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "instcombine"
 
-/// isFreeToInvert - Return true if the specified value is free to invert (apply
-/// ~ to).  This happens in cases where the ~ can be eliminated.
-static inline bool isFreeToInvert(Value *V) {
-  // ~(~(X)) -> X.
-  if (BinaryOperator::isNot(V))
-    return true;
-
-  // Constants can be considered to be not'ed values.
-  if (isa<ConstantInt>(V))
-    return true;
-
-  // Compares can be inverted if they have a single use.
-  if (CmpInst *CI = dyn_cast<CmpInst>(V))
-    return CI->hasOneUse();
-
-  return false;
-}
-
 static inline Value *dyn_castNotVal(Value *V) {
   // If this is not(not(x)) don't return that this is a not: we want the two
   // not's to be folded first.
   if (BinaryOperator::isNot(V)) {
     Value *Operand = BinaryOperator::getNotArgument(V);
-    if (!isFreeToInvert(Operand))
+    if (!IsFreeToInvert(Operand, Operand->hasOneUse()))
       return Operand;
   }
 
   // Constants can be considered to be not'ed values...
   if (ConstantInt *C = dyn_cast<ConstantInt>(V))
     return ConstantInt::get(C->getType(), ~C->getValue());
   return nullptr;
 }
if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(NotOp)) {
                                Op0I->getOperand(1)->getName()+".not");
           if (Op0I->getOpcode() == Instruction::And)
             return BinaryOperator::CreateOr(Op0NotVal, NotY);
           return BinaryOperator::CreateAnd(Op0NotVal, NotY);
         }
 
         // ~(X & Y) --> (~X | ~Y) - De Morgan's Law
         // ~(X | Y) === (~X & ~Y) - De Morgan's Law
-        if (isFreeToInvert(Op0I->getOperand(0)) &&
-            isFreeToInvert(Op0I->getOperand(1))) {
+        if (IsFreeToInvert(Op0I->getOperand(0),
+                           Op0I->getOperand(0)->hasOneUse()) &&
+            IsFreeToInvert(Op0I->getOperand(1),
+                           Op0I->getOperand(1)->hasOneUse())) {
           Value *NotX =
             Builder->CreateNot(Op0I->getOperand(0), "notlhs");
           Value *NotY =
             Builder->CreateNot(Op0I->getOperand(1), "notrhs");
           if (Op0I->getOpcode() == Instruction::And)
             return BinaryOperator::CreateOr(NotX, NotY);
           return BinaryOperator::CreateAnd(NotX, NotY);
         }

llvm/trunk/lib/Transforms/InstCombine/InstCombineInternal.h

 static inline Constant *AddOne(Constant *C) {
   return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
 }
 /// \brief Subtract one from a Constant
 static inline Constant *SubOne(Constant *C) {
   return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1));
 }
 
+/// \brief Return true if the specified value is free to invert (apply ~ to).
+/// This happens in cases where the ~ can be eliminated.  If WillInvertAllUses
+/// is true, work under the assumption that the caller intends to remove all
+/// uses of V and only keep uses of ~V.
+///
+static inline bool IsFreeToInvert(Value *V, bool WillInvertAllUses) {
+  // ~(~(X)) -> X.
+  if (BinaryOperator::isNot(V))
+    return true;
+
+  // Constants can be considered to be not'ed values.
+  if (isa<ConstantInt>(V))
+    return true;
+
+  // Compares can be inverted if all of their uses are being modified to use the
+  // ~V.
+  if (isa<CmpInst>(V))
+    return WillInvertAllUses;
+
+  // If `V` is of the form `A + Constant` then `-1 - V` can be folded into `(-1
+  // - Constant) - A` if we are willing to invert all of the uses.
+  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
+    if (BO->getOpcode() == Instruction::Add ||
+        BO->getOpcode() == Instruction::Sub)
+      if (isa<Constant>(BO->getOperand(0)) || isa<Constant>(BO->getOperand(1)))
+        return WillInvertAllUses;
+
+  return false;
+}
+
 /// \brief An IRBuilder inserter that adds new instructions to the instcombine
 /// worklist.
 class LLVM_LIBRARY_VISIBILITY InstCombineIRInserter
     : public IRBuilderDefaultInserter<true> {
   InstCombineWorklist &Worklist;
   AssumptionCache *AC;
 
 public:

llvm/trunk/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) {
+      if (IsFreeToInvert(LHS, LHS->hasNUses(2)) &&
+          IsFreeToInvert(RHS, RHS->hasNUses(2))) {
+
+        // This transform adds a xor operation and that extra cost needs to be
+        // justified.  We look for simplifications that will result from
+        // applying this rule:
+
+        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) &&

llvm/trunk/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
+}