[InstCombine] try to pull 'not' of select into compare operands

[spatel]

Summary

not (select Cond, (cmp TPred, ?, ?), FVal --> select Cond, (cmp TPred', ?, ?), (not FVal)

(If both sides of the select are cmps, we can remove an instruction.)

We have a more general 'isFreeToInvert' analysis, but I'm not seeing a way to use that more widely without inducing infinite looping (opposing transforms).
Here, we flip the compare predicate directly, so we should not have any danger by creating extra intermediate 'not' ops.

Alive proofs:
https://rise4fun.com/Alive/jKa

Name: both select values are compares - invert predicates
  %tcmp = icmp sle i32 %x, %y  
  %fcmp = icmp ugt i32 %z, %w
  %sel = select i1 %cond, i1 %tcmp, i1 %fcmp
  %not = xor i1 %sel, true
=>
  %tcmp_not = icmp sgt i32 %x, %y  
  %fcmp_not = icmp ule i32 %z, %w
  %not = select i1 %cond, i1 %tcmp_not, i1 %fcmp_not
  
Name: false val is compare - invert/not 
  %fcmp = icmp ugt i32 %z, %w
  %sel = select i1 %cond, i1 %tcmp, i1 %fcmp
  %not = xor i1 %sel, true
=>
  %tcmp_not = xor i1 %tcmp, -1  
  %fcmp_not = icmp ule i32 %z, %w
  %not = select i1 %cond, i1 %tcmp_not, i1 %fcmp_not

[xbolva00]

Looks good

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

3287

InvertedTPred?

I almost missed the “ ‘ “.

3304

Maybe small lambda would help here to improve this almost same code?

[lebedev.ri]

Looks good to me in principle, the case where we get rid of not is good,
but i'm not sure about the case where we only manage to sink it into one of the hands.
To me that seems to be the opposite of the current general canonicalizaion we do.
(Do we need Inverter logic, that handles sinking of inversions as far as possible?)

I agree that it is a throughput improvement for final assembly, but not sure about IR.
Is there some bigger pattern (of which this pattern is part of)
which shows why this is the correct IR canonicalization?

[spatel]

In D72007#1804065, @lebedev.ri wrote:

Looks good to me in principle, the case where we get rid of not is good,
but i'm not sure about the case where we only manage to sink it into one of the hands.
To me that seems to be the opposite of the current general canonicalizaion we do.

The general 'not cmp' canonicalization is the same as this? See around line 3090:

// not (cmp A, B) = !cmp A, B
CmpInst::Predicate Pred;
if (match(&I, m_Not(m_OneUse(m_Cmp(Pred, m_Value(), m_Value()))))) {
  cast<CmpInst>(Op0)->setPredicate(CmpInst::getInversePredicate(Pred));
  return replaceInstUsesWith(I, Op0);
}

(Do we need Inverter logic, that handles sinking of inversions as far as possible?)

That would be similar to D68408 (did negator hit a roadblock?), so it could be an enhancement there.

I agree that it is a throughput improvement for final assembly, but not sure about IR.
Is there some bigger pattern (of which this pattern is part of)
which shows why this is the correct IR canonicalization?

The app where I noticed this allowed eliminating the 'not' (the select had 2 cmps), but I've lost track of that larger example. So that case seems uncontroversial - we are able to remove an instruction.

I can reduce the scope of this patch to only handle that case, but then we will have a missing canonicalization for the more general case (1 cmp). Pulling the 'not' ahead of the select seems more likely to allow follow-on folding, so that's why I chose that as canonical. I can propose that separately or drop it if that's not a convincing argument.

[lebedev.ri]

In D72007#1804132, @spatel wrote:

In D72007#1804065, @lebedev.ri wrote:

Looks good to me in principle, the case where we get rid of not is good,
but i'm not sure about the case where we only manage to sink it into one of the hands.
To me that seems to be the opposite of the current general canonicalizaion we do.

The general 'not cmp' canonicalization is the same as this? See around line 3090:

// not (cmp A, B) = !cmp A, B
CmpInst::Predicate Pred;
if (match(&I, m_Not(m_OneUse(m_Cmp(Pred, m_Value(), m_Value()))))) {
  cast<CmpInst>(Op0)->setPredicate(CmpInst::getInversePredicate(Pred));
  return replaceInstUsesWith(I, Op0);
}

No, i'm not talking about clear-win cases where that allows to eliminate not/neg,
but about the cases where there is no change in instruction count.

(Do we need Inverter logic, that handles sinking of inversions as far as possible?)

That would be similar to D68408, so it could be an enhancement there.

I would personally say that *if* we have an Inverter, then generally, outside of it,
in the cases where there is no decrease in instruction count,
we should be consistently *hoisting* not/neg.
But clearly we are not there (yet?), so the solution is not as obvious.

(did negator hit a roadblock?)

Yeah, it got too powerful and hit/exposed another conflicting canonicalization,
so i've stopped for now. I think it will need some kind of pattern blacklisting :/

I agree that it is a throughput improvement for final assembly, but not sure about IR.
Is there some bigger pattern (of which this pattern is part of)
which shows why this is the correct IR canonicalization?

The app where I noticed this allowed eliminating the 'not' (the select had 2 cmps), but I've lost track of that larger example. So that case seems uncontroversial - we are able to remove an instruction.

I can reduce the scope of this patch to only handle that case, but then we will have a missing canonicalization for the more general case (1 cmp). Pulling the 'not' ahead of the select seems more likely to allow follow-on folding, so that's why I chose that as canonical. I can propose that separately or drop it if that's not a convincing argument.

The clear-win case LG; the other case where we only sink it, but not *necessarily* eliminate it,
while it doesn't look obviously-bad to me, it isn't immediately obvious to me that it is the correct direction.

[spatel]

Patch updated:
Only do the transform if both arms of the select are cmps. Defer canonicalization of single cmp pattern (see TODO comments).

[lebedev.ri]

LG
I wonder if this will expose some inverse canonicalization (i hope instcombine will still endlessly loop/assert), but i can't think of any right now.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (SelectPatternResult::isMinOrMax(SPF)) {
           isFreeToInvert(RHS, !RHS->hasNUsesOrMore(3))) {
         Value *NotLHS = Builder.CreateNot(LHS);
         Value *NotRHS = Builder.CreateNot(RHS);
         return SelectInst::Create(
             Builder.CreateICmp(getInverseMinMaxPred(SPF), NotLHS, NotRHS),
             NotLHS, NotRHS);
       }
     }
+
+    // Pull 'not' into operands of select if both operands are one-use compares.
+    // Inverting the predicates eliminates the 'not' operation.
+    // Example:
+    //     not (select ?, (cmp TPred, ?, ?), (cmp FPred, ?, ?) -->
+    //     select ?, (cmp InvTPred, ?, ?), (cmp InvFPred, ?, ?)
+    // TODO: Canonicalize by hoisting 'not' into an arm of the select if only
+    //       1 select operand is a cmp?
+    if (auto *Sel = dyn_cast<SelectInst>(Op0)) {
+      auto *CmpT = dyn_cast<CmpInst>(Sel->getTrueValue());
+      auto *CmpF = dyn_cast<CmpInst>(Sel->getFalseValue());
+      if (CmpT && CmpF && CmpT->hasOneUse() && CmpF->hasOneUse()) {
+        CmpT->setPredicate(CmpT->getInversePredicate());
+        CmpF->setPredicate(CmpF->getInversePredicate());
+        return replaceInstUsesWith(I, Sel);
+      }
+    }
   }
 
   if (Instruction *NewXor = sinkNotIntoXor(I, Builder))
     return NewXor;
 
   return nullptr;
 }

llvm/test/Transforms/InstCombine/not.ll

 ;
   %a = add <2 x i32> %x, <i32 42, i32 123>
   %r = xor <2 x i32> %a, <i32 -1, i32 -1>
   ret <2 x i32> %r
 }
 
 define i1 @not_select_cmp_cmp(i32 %x, i32 %y, float %z, float %w, i1 %cond) {
 ; CHECK-LABEL: @not_select_cmp_cmp(
-; CHECK-NEXT:    [[CMPT:%.*]] = icmp sle i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMPF:%.*]] = fcmp ugt float [[Z:%.*]], [[W:%.*]]
+; CHECK-NEXT:    [[CMPT:%.*]] = icmp sgt i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[CMPF:%.*]] = fcmp ole float [[Z:%.*]], [[W:%.*]]
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i1 [[CMPT]], i1 [[CMPF]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[SEL]], true
-; CHECK-NEXT:    ret i1 [[NOT]]
+; CHECK-NEXT:    ret i1 [[SEL]]
 ;
   %cmpt = icmp sle i32 %x, %y
   %cmpf = fcmp ugt float %z, %w
   %sel = select i1 %cond, i1 %cmpt, i1 %cmpf
   %not = xor i1 %sel, true
   ret i1 %not
 }
 
 declare void @use1(i1)
 
+; TODO: Missed canonicalization - hoist 'not'?
+
 define i1 @not_select_cmp_cmp_extra_use1(i32 %x, i32 %y, float %z, float %w, i1 %cond) {
 ; CHECK-LABEL: @not_select_cmp_cmp_extra_use1(
 ; CHECK-NEXT:    [[CMPT:%.*]] = icmp sle i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use1(i1 [[CMPT]])
 ; CHECK-NEXT:    [[CMPF:%.*]] = fcmp ugt float [[Z:%.*]], [[W:%.*]]
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i1 [[CMPT]], i1 [[CMPF]]
 ; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[SEL]], true
 ; CHECK-NEXT:    ret i1 [[NOT]]
 ;
   %cmpt = icmp sle i32 %x, %y
   call void @use1(i1 %cmpt)
   %cmpf = fcmp ugt float %z, %w
   %sel = select i1 %cond, i1 %cmpt, i1 %cmpf
   %not = xor i1 %sel, true
   ret i1 %not
 }
 
+; TODO: Missed canonicalization - hoist 'not'?
+
 define i1 @not_select_cmp_cmp_extra_use2(i32 %x, i32 %y, float %z, float %w, i1 %cond) {
 ; CHECK-LABEL: @not_select_cmp_cmp_extra_use2(
 ; CHECK-NEXT:    [[CMPT:%.*]] = icmp sle i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[CMPF:%.*]] = fcmp ugt float [[Z:%.*]], [[W:%.*]]
 ; CHECK-NEXT:    call void @use1(i1 [[CMPF]])
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i1 [[CMPT]], i1 [[CMPF]]
 ; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[SEL]], true
 ; CHECK-NEXT:    ret i1 [[NOT]]
 ;
   %cmpt = icmp sle i32 %x, %y
   %cmpf = fcmp ugt float %z, %w
   call void @use1(i1 %cmpf)
   %sel = select i1 %cond, i1 %cmpt, i1 %cmpf
   %not = xor i1 %sel, true
   ret i1 %not
 }
 
+; Negative test - extra uses would require more instructions.
+
 define i1 @not_select_cmp_cmp_extra_use3(i32 %x, i32 %y, float %z, float %w, i1 %cond) {
 ; CHECK-LABEL: @not_select_cmp_cmp_extra_use3(
 ; CHECK-NEXT:    [[CMPT:%.*]] = icmp sle i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use1(i1 [[CMPT]])
 ; CHECK-NEXT:    [[CMPF:%.*]] = fcmp ugt float [[Z:%.*]], [[W:%.*]]
 ; CHECK-NEXT:    call void @use1(i1 [[CMPF]])
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i1 [[CMPT]], i1 [[CMPF]]
 ; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[SEL]], true
 ; CHECK-NEXT:    ret i1 [[NOT]]
 ;
   %cmpt = icmp sle i32 %x, %y
   call void @use1(i1 %cmpt)
   %cmpf = fcmp ugt float %z, %w
   call void @use1(i1 %cmpf)
   %sel = select i1 %cond, i1 %cmpt, i1 %cmpf
   %not = xor i1 %sel, true
   ret i1 %not
 }
 
+; Negative test - extra uses would require more instructions.
+
 define i1 @not_select_cmp_cmp_extra_use4(i32 %x, i32 %y, float %z, float %w, i1 %cond) {
 ; CHECK-LABEL: @not_select_cmp_cmp_extra_use4(
 ; CHECK-NEXT:    [[CMPT:%.*]] = icmp sle i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[CMPF:%.*]] = fcmp ugt float [[Z:%.*]], [[W:%.*]]
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i1 [[CMPT]], i1 [[CMPF]]
 ; CHECK-NEXT:    call void @use1(i1 [[SEL]])
 ; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[SEL]], true
 ; CHECK-NEXT:    ret i1 [[NOT]]
 ;
   %cmpt = icmp sle i32 %x, %y
   %cmpf = fcmp ugt float %z, %w
   %sel = select i1 %cond, i1 %cmpt, i1 %cmpf
   call void @use1(i1 %sel)
   %not = xor i1 %sel, true
   ret i1 %not
 }
 
+; TODO: Missed canonicalization - hoist 'not'?
+
 define i1 @not_select_cmpt(double %x, double %y, i1 %z, i1 %cond) {
 ; CHECK-LABEL: @not_select_cmpt(
 ; CHECK-NEXT:    [[CMPT:%.*]] = fcmp oeq double [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i1 [[CMPT]], i1 [[Z:%.*]]
 ; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[SEL]], true
 ; CHECK-NEXT:    ret i1 [[NOT]]
 ;
   %cmpt = fcmp oeq double %x, %y
   %sel = select i1 %cond, i1 %cmpt, i1 %z
   %not = xor i1 %sel, true
   ret i1 %not
 }
 
+; TODO: Missed canonicalization - hoist 'not'?
+
 define i1 @not_select_cmpf(i1 %x, i32 %z, i32 %w, i1 %cond) {
 ; CHECK-LABEL: @not_select_cmpf(
 ; CHECK-NEXT:    [[CMPF:%.*]] = icmp ugt i32 [[Z:%.*]], [[W:%.*]]
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i1 [[X:%.*]], i1 [[CMPF]]
 ; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[SEL]], true
 ; CHECK-NEXT:    ret i1 [[NOT]]
 ;
   %cmpf = icmp ugt i32 %z, %w