Page MenuHomePhabricator

[InstSimplify] fold select of bools using bitwise logic
Needs RevisionPublic

Authored by spatel on Apr 10 2020, 5:57 AM.

Details

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

Diff Detail

Event Timeline

spatel created this revision.Apr 10 2020, 5:57 AM
nikic added a comment.Apr 10 2020, 6:33 AM

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

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?

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!

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.

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 added a comment.Apr 10 2020, 8:45 AM

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.

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.

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.

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 accepted this revision.Apr 13 2020, 8:52 AM
// 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.

This revision is now accepted and ready to land.Apr 13 2020, 8:52 AM

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 accepted this revision.Apr 13 2020, 10:08 AM

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 requested changes to this revision.Apr 13 2020, 10:27 AM

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

This revision now requires changes to proceed.Apr 13 2020, 10:27 AM

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.

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.