[InstSimplify] fold select of bools using bitwise logic

[spatel]

Summary

select Cond, T, false --> Cond & T
select Cond, true, F --> Cond | F

This fixes regressions that would be visible if we remove known poison-unsafe transforms in instcombine mentioned here:
https://reviews.llvm.org/D72396#1810460

I'm not sure yet how to deal with the 'and-not' and 'or-not' variations.

Alive2 example for 1 of the tests:
http://volta.cs.utah.edu:8080/z/Ue2UE3

[nikic]

What is the motivation for having this fold partially (only if recursively simplifiable) in InstSimplify, rather than doing the full fold in InstCombine?

[spatel]

In D77868#1974228, @nikic wrote:

What is the motivation for having this fold partially (only if recursively simplifiable) in InstSimplify, rather than doing the full fold in InstCombine?

If the logic can be simplified, then that makes it poison-safe. Ie, if the logic op simplifies, that means the logic op must be filtering out a poisoned value the same as we would expect of a select. Does that make sense, or do you know of a counter-example?
But not sure if that's the question: handle all 4 of the logic-op possibilities (and-not/or-not) rather than just and/or in instcombine rather than here?

[lebedev.ri]

This fixes regressions that would be visible if we remove known poison-unsafe transforms in instcombine mentioned here:
https://reviews.llvm.org/D72396#1810460

I think the problem is being misunderstood:

----------------------------------------
Name: fval is true
  %s = select i1 %cmp1, i1 %x, i1 1
  ret i1 %s
=>
  %not = xor i1 %cmp1, 1
  %s = or i1 %not, %x
  ret i1 %s

ERROR: Target is more poisonous than source for i1 %s

Example:
i1 %cmp1 = #x0 (0)
i1 %x = poison
i1 %not = #x1 (1)
Source value: #x1 (1)
Target value: poison


----------------------------------------
Name: fval is false
  %s = select i1 %cmp1, i1 %x, i1 0
  ret i1 %s
=>
  %s = and i1 %cmp1, %x
  ret i1 %s

ERROR: Target is more poisonous than source for i1 %s

Example:
i1 %cmp1 = #x0 (0)
i1 %x = poison
Source value: #x0 (0)
Target value: poison


----------------------------------------
Name: tval is true
  %s = select i1 %cmp1, i1 1, i1 %x
  ret i1 %s
=>
  %s = or i1 %cmp1, %x
  ret i1 %s

ERROR: Target is more poisonous than source for i1 %s

Example:
i1 %cmp1 = #x1 (1)
i1 %x = poison
Source value: #x1 (1)
Target value: poison


----------------------------------------
Name: tval is false
  %s = select i1 %cmp1, i1 0, i1 %x
  ret i1 %s
=>
  %not = xor i1 %cmp1, 1
  %s = and i1 %not, %x
  ret i1 %s

ERROR: Target is more poisonous than source for i1 %s

Example:
i1 %cmp1 = #x1 (1)
i1 %x = poison
i1 %not = #x0 (0)
Source value: #x0 (0)
Target value: poison

----------------------------------------
Name: fval is true
  %s = select i1 %cmp1, i1 %x, i1 1
  ret i1 %s
=>
  %not = xor i1 %cmp1, 1
  %frozen_x = freeze i1 %x
  %s = or i1 %not, %frozen_x
  ret i1 %s

Done: 1
Transformation seems to be correct!

----------------------------------------
Name: fval is false
  %s = select i1 %cmp1, i1 %x, i1 0
  ret i1 %s
=>
  %frozen_x = freeze i1 %x
  %s = and i1 %cmp1, %frozen_x
  ret i1 %s

Done: 1
Transformation seems to be correct!

----------------------------------------
Name: tval is true
  %s = select i1 %cmp1, i1 1, i1 %x
  ret i1 %s
=>
  %frozen_x = freeze i1 %x
  %s = or i1 %cmp1, %frozen_x
  ret i1 %s

Done: 1
Transformation seems to be correct!

----------------------------------------
Name: tval is false
  %s = select i1 %cmp1, i1 0, i1 %x
  ret i1 %s
=>
  %not = xor i1 %cmp1, 1
  %frozen_x = freeze i1 %x
  %s = and i1 %not, %frozen_x
  ret i1 %s

Done: 1
Transformation seems to be correct!

[spatel]

In D77868#1974358, @lebedev.ri wrote:

This fixes regressions that would be visible if we remove known poison-unsafe transforms in instcombine mentioned here:
https://reviews.llvm.org/D72396#1810460

I think the problem is being misunderstood:

%frozen_x = freeze i1 %x

Ah, yes I know we could introduce freeze (or predicate with isGuaranteedNotToBeUndefOrPoison()?), but I thought we're not ready to introduce that as part of canonicalization because it would cause too much perf fallout currently.

[lebedev.ri]

In D77868#1974376, @spatel wrote:

In D77868#1974358, @lebedev.ri wrote:

This fixes regressions that would be visible if we remove known poison-unsafe transforms in instcombine mentioned here:
https://reviews.llvm.org/D72396#1810460

I think the problem is being misunderstood:

%frozen_x = freeze i1 %x

Ah, yes I know we could introduce freeze (or predicate with isGuaranteedNotToBeUndefOrPoison()?), but I thought we're not ready to introduce that as part of canonicalization because it would cause too much perf fallout currently.

Sure, yes. I'm just pointing out that the medium-to-long-term goal for
such 'miscompilations' is freezing potentially-poison operands,
not removal of the problematic transforms. It doesn't mean we shouldn't
see what other missed folds we uncover when we try to as-if remove those folds though.

[nikic]

In D77868#1974322, @spatel wrote:

In D77868#1974228, @nikic wrote:

What is the motivation for having this fold partially (only if recursively simplifiable) in InstSimplify, rather than doing the full fold in InstCombine?

If the logic can be simplified, then that makes it poison-safe. Ie, if the logic op simplifies, that means the logic op must be filtering out a poisoned value the same as we would expect of a select. Does that make sense, or do you know of a counter-example?

Sorry, my original question didn't make sense... I'm having a really hard time convincing myself that this is correct though. If we simplify to a constant, that's obviously correct. If we simplify to some value on which the select condition depends, then it's also correct (as the condition does not block poison). But can't it also happen that we simplify to a value that the select operand depends on, but the condition does not? I wasn't able to come up with a specific example, but I'm not immediately seeing why that couldn't happen, in principle.

[aqjune]

I think what @nikic said is correct:

// select Cond, T, false --> Cond & T
if (match(F, m_ZeroInt()))
  return SimplifyAndInst(Cond, T, Q);

If Cond is false and T is poison, the select is constantly false, but SimplifyAndInst(Cond, T, Q) can exploit the fact that T is poison regardless of Cond.

To address this, T should not be poison if Cond isn't poison. T = undef is okay, because undef & false is false.
It will be great if there is an analysis like 'is X poison when Y is poison?', but I guess it doesn't exist in ValueTracking yet.
We can use isGuaranteedNotToBeUndefOrPoison now, to check whether T is never poison.
If we have isGuaranteedNotToBePoison, which checks poison only, the optimization can be more aggressive.

[aqjune]

Maybe I can write a simple version of bool isPoisonIf(Value *X, Value *PoisonAssumedVal) into ValueTracking which returns true if X is poison, given that PoisonAssumedVal is already poison.
Then, the optimizing part can be rewritten as:

// select Cond, T, false --> Cond & T
if (match(F, m_ZeroInt()) && isPoisonIf(Cond, T))
  return SimplifyAndInst(Cond, T, Q);

This will also support folding select (icmp X, C1), (icmp X, C2), false, because (icmp X, C1) is poison if (icmp X, C2) was poison.

[spatel]

In D77868#1974597, @aqjune wrote:

I think what @nikic said is correct:

// select Cond, T, false --> Cond & T
if (match(F, m_ZeroInt()))
  return SimplifyAndInst(Cond, T, Q);

If Cond is false and T is poison, the select is constantly false, but SimplifyAndInst(Cond, T, Q) can exploit the fact that T is poison regardless of Cond.

To address this, T should not be poison if Cond isn't poison. T = undef is okay, because undef & false is false.

I still do not see how this can go wrong in practice. If InstSimplify can prove that T is poison, then doesn't it always manifest that knowledge by saying T is undef?
Looking at it another way (see if you can spot a logic flaw):

1. Assume T is poison.
2. Assume InstSimplify fails to simplify T to undef or constant.
3. For poison T' (either T or some other poisoned value) to leak through as the result, InstSimplify must prove that Cond & T' == T'.
4. So InstSimplify must prove that Cond == true or Cond == T'.
5. If Cond == T', there's no problem (if Cond is poison, the select is poison).
6. Therefore -- for there to be a problem -- we must prove that Cond is true.
7. If we can prove that Cond is true, then that guarantees that value T' can't depend on Cond (nothing depends on Cond - it simplifies to constant true).

[nlopes]

In D77868#1977808, @spatel wrote:

// select Cond, T, false --> Cond & T
if (match(F, m_ZeroInt()))
  return SimplifyAndInst(Cond, T, Q);

I still do not see how this can go wrong in practice. If InstSimplify can prove that T is poison, then doesn't it always manifest that knowledge by saying T is undef?
Looking at it another way (see if you can spot a logic flaw):

1. Assume T is poison.
2. Assume InstSimplify fails to simplify T to undef or constant.
3. For poison T' (either T or some other poisoned value) to leak through as the result, InstSimplify must prove that Cond & T' == T'.
4. So InstSimplify must prove that Cond == true or Cond == T'.
5. If Cond == T', there's no problem (if Cond is poison, the select is poison).
6. Therefore -- for there to be a problem -- we must prove that Cond is true.
7. If we can prove that Cond is true, then that guarantees that value T' can't depend on Cond (nothing depends on Cond - it simplifies to constant true).

I agree with your reasoning, and that this patch is correct.
The crucial piece of information that was missing, for me at least, is that SimplifyAndInst() doesn't create an 'and' instruction if it fails to simplify (it just returns null). Also, it doesn't create new instructions (it could also create a mask or smth like that, but that doesn't happen either).
Given this, LGTM, thanks.

[nikic]

Let me try to give a specific example. Let's say we're looking at the select Cond, T, false --> Cond & T case and have:

Cond = X ult 10
T = (X +nuw 1) ult 11

In this case, InstSimplify would be permitted to fold Cond & T to T: http://volta.cs.utah.edu:8080/z/KcVHTj

However, it would not be legal to perform the same transform for the select: http://volta.cs.utah.edu:8080/z/tM_9UA

Now, InstSimplify doesn't perform this particular fold (and it makes little sense to fold Cond & T to T rather than Cond in this example), but I think this illustrates that the transform is not inherently safe.

[lebedev.ri]

lg

llvm/lib/Analysis/InstructionSimplify.cpp

3983–3989

I would recommend making this more obvious:

// select Cond, T, false --> Cond & T
if (match(F, m_ZeroInt()))
  if(Value* V = SimplifyAndInst(Cond, T, Q))
    return V;

// select Cond, true, F --> Cond | F
if (match(T, m_One()))
  if(Value* V = SimplifyOrInst(Cond, F, Q))
    return V;

[nikic]

I think I have an actual example of a miscompile now: http://volta.cs.utah.edu:8080/z/VBAN4q

This fold does exist in InstSimplify: https://godbolt.org/z/7n3oQ8

[spatel]

In D77868#1978197, @nikic wrote:

I think I have an actual example of a miscompile now: http://volta.cs.utah.edu:8080/z/VBAN4q

This fold does exist in InstSimplify: https://godbolt.org/z/7n3oQ8

Thanks! That looks indisputable. I'll add that test to prevent tripping again. I almost had the variation with 'fcmp uno' in the tests here, but didn't imagine the pattern with non-constant extra operand.

So the problem in my sequence of simplifications is at step #4. We do not have to prove that Cond is true or the same as T independently of T itself. The bitwise logic relationship may simplify via implication.

[aqjune]

To partially support this optimization, my patch D78152 might be of help. It contains impliesPoison(X, Y), which returns true if Y is poison given that X is poison.
With D76010 and making propagatesFullPoison return true on fcmp, tests in InstSimplify/select.ll except x | (x & y) --> x are supported.
To support the case, I think we need to separately enumerate such optimizations that are safe for select.

To check whether using impliesPoison affects compilation time, I ran CTMark after applying D76010, D78152, and making propagatesFullPoison return true on fcmp.
It has ~0.5% increase in compilation time. If you think this is too much, I can tweak D78152 to make it faster.

ctmark.csv684 BDownload

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/lib/Analysis/InstructionSimplify.cpp

if (HasNoSignedZeros || (match(T, m_APFloat(C)) && C->isNonZero()) ||
     // (F != T) ? T : F --> T
     if (Pred == FCmpInst::FCMP_UNE)
       return T;
   }
 
   return nullptr;
 }
 
+/// Try to simplify a select of boolean values where one of the true/false arms
+/// of the select is a true/false constant. The more general transform from
+/// select to logic op is not valid because 'select' may block poison that a
+/// logic op would allow to flow through.
+static Value *foldSelectOfBools(Value *Cond, Value *T, Value *F,
+                                const SimplifyQuery &Q) {
+  Type *Ty = Cond->getType();
+  assert(Ty->isIntOrIntVectorTy(1) && "Expected bool condition for select");
+  assert(T->getType() == F->getType() && "Mismatched select types");
+  if (Ty != T->getType())
+    return nullptr;
+
+  // select Cond, T, false --> Cond & T
+  if (match(F, m_ZeroInt()))
+    return SimplifyAndInst(Cond, T, Q);
+
+  // select Cond, true, F --> Cond | F
+  if (match(T, m_One()))
+    return SimplifyOrInst(Cond, F, Q);
+
+  return nullptr;
+}
+
 /// Given operands for a SelectInst, see if we can fold the result.
 /// If not, this returns null.
 static Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
                                  const SimplifyQuery &Q, unsigned MaxRecurse) {
   if (auto *CondC = dyn_cast<Constant>(Cond)) {
     if (auto *TrueC = dyn_cast<Constant>(TrueVal))
       if (auto *FalseC = dyn_cast<Constant>(FalseVal))
         return ConstantFoldSelectInstruction(CondC, TrueC, FalseC);
if (Value *V =
     return V;
 
   if (Value *V = simplifySelectWithFCmp(Cond, TrueVal, FalseVal, Q))
     return V;
 
   if (Value *V = foldSelectWithBinaryOp(Cond, TrueVal, FalseVal))
     return V;
 
+  if (Value *V = foldSelectOfBools(Cond, TrueVal, FalseVal, Q))
+    return V;
+
   Optional<bool> Imp = isImpliedByDomCondition(Cond, Q.CxtI, Q.DL);
   if (Imp)
     return *Imp ? TrueVal : FalseVal;
 
   return nullptr;
 }
 
 Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,

llvm/test/Transforms/InstSimplify/select.ll

 ; CHECK-NEXT:    ret i32* [[GEP]]
 ;
   %cond = icmp ne i64 %n, 0
   %gep = getelementptr i32, i32* %base, i64 %n
   %r = select i1 %cond, i32* %gep, i32* %base
   ret i32* %r
 }
 
+; X < 92 && X < 11 --> X < 11
+
 define i1 @and_cmps(i32 %x) {
 ; CHECK-LABEL: @and_cmps(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[X:%.*]], 92
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[X]], 11
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[CMP1]], i1 [[CMP2]], i1 false
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[X:%.*]], 11
+; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %cmp1 = icmp slt i32 %x, 92
   %cmp2 = icmp slt i32 %x, 11
   %r = select i1 %cmp1, i1 %cmp2, i1 false
   ret i1 %r
 }
 
+; Repeat with vector types.
+
 define <2 x i1> @and_cmps_vector(<2 x i32> %x) {
 ; CHECK-LABEL: @and_cmps_vector(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt <2 x i32> [[X:%.*]], <i32 92, i32 92>
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt <2 x i32> [[X]], <i32 11, i32 11>
-; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[CMP1]], <2 x i1> [[CMP2]], <2 x i1> zeroinitializer
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt <2 x i32> [[X:%.*]], <i32 11, i32 11>
+; CHECK-NEXT:    ret <2 x i1> [[CMP2]]
 ;
   %cmp1 = icmp slt <2 x i32> %x, <i32 92, i32 92>
   %cmp2 = icmp slt <2 x i32> %x, <i32 11, i32 11>
   %r = select <2 x i1> %cmp1, <2 x i1> %cmp2, <2 x i1> <i1 false, i1 false>
   ret <2 x i1> %r
 }
 
+; Is %x a NAN?
+
 define i1 @or_cmps(float %x) {
 ; CHECK-LABEL: @or_cmps(
-; CHECK-NEXT:    [[CMP1:%.*]] = fcmp uno float [[X:%.*]], 4.200000e+01
-; CHECK-NEXT:    [[CMP2:%.*]] = fcmp uno float [[X]], 5.200000e+01
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[CMP1]], i1 true, i1 [[CMP2]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[CMP2:%.*]] = fcmp uno float [[X:%.*]], 5.200000e+01
+; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %cmp1 = fcmp uno float %x, 42.0
   %cmp2 = fcmp uno float %x, 52.0
   %r = select i1 %cmp1, i1 true, i1 %cmp2
   ret i1 %r
 }
 
+; x | (x & y) --> x
+
 define <2 x i1> @or_logic_vector(<2 x i1> %x, <2 x i1> %y) {
 ; CHECK-LABEL: @or_logic_vector(
-; CHECK-NEXT:    [[A:%.*]] = and <2 x i1> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[X]], <2 x i1> <i1 true, i1 true>, <2 x i1> [[A]]
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    ret <2 x i1> [[X:%.*]]
 ;
   %a = and <2 x i1> %x, %y
   %r = select <2 x i1> %x, <2 x i1> <i1 true, i1 true>, <2 x i1> %a
   ret <2 x i1> %r
 }
 
+; TODO: This reduces to 'false'.
+
 define i1 @and_not_cmps(i32 %x) {
 ; CHECK-LABEL: @and_not_cmps(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[X:%.*]], 92
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[X]], 11
 ; CHECK-NEXT:    [[R:%.*]] = select i1 [[CMP1]], i1 false, i1 [[CMP2]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %cmp1 = icmp slt i32 %x, 92
   %cmp2 = icmp slt i32 %x, 11
   %r = select i1 %cmp1, i1 false, i1 %cmp2
   ret i1 %r
 }
 
+; Negative test (but instcombine can reduce it).
+
 define i1 @or_not_cmps(i32 %x) {
 ; CHECK-LABEL: @or_not_cmps(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[X:%.*]], 92
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[X]], 11
 ; CHECK-NEXT:    [[R:%.*]] = select i1 [[CMP1]], i1 [[CMP2]], i1 true
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %cmp1 = icmp slt i32 %x, 92
   %cmp2 = icmp slt i32 %x, 11
   %r = select i1 %cmp1, i1 %cmp2, i1 true
   ret i1 %r
 }
 
+; TODO: Could look through a cast and fold to %s?
+
 define i8 @and_cmps_wrong_type(i32 %x) {
 ; CHECK-LABEL: @and_cmps_wrong_type(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[X:%.*]], 92
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[X]], 11
 ; CHECK-NEXT:    [[S:%.*]] = sext i1 [[CMP2]] to i8
 ; CHECK-NEXT:    [[R:%.*]] = select i1 [[CMP1]], i8 [[S]], i8 0
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %cmp1 = icmp slt i32 %x, 92
   %cmp2 = icmp slt i32 %x, 11
   %s = sext i1 %cmp2 to i8
   %r = select i1 %cmp1, i8 %s, i8 0
   ret i8 %r
 }