Page MenuHomePhabricator

[ConstantFold] Fold more operations to poison
ClosedPublic

Authored by aqjune on Nov 28 2020, 11:55 AM.

Details

Summary

This patch folds more operations to poison.

Alive2 proof: https://alive2.llvm.org/ce/z/mxcb9G (it does not contain tests about div/rem because they fold to poison when raising UB)

Diff Detail

Event Timeline

aqjune created this revision.Nov 28 2020, 11:55 AM
aqjune requested review of this revision.Nov 28 2020, 11:55 AM
aqjune retitled this revision from [ConstProp] Fold more operations to poison to [ConstantFold] Fold more operations to poison.Nov 28 2020, 11:55 AM
aqjune updated this revision to Diff 308184.Nov 28 2020, 12:03 PM

minor simplification

aqjune added inline comments.Nov 28 2020, 12:15 PM
llvm/test/Transforms/InstCombine/partally-redundant-left-shift-input-masking-after-truncation-variant-c.ll
113

This change is valid.
Take the first element of T5 for example:
Since it is poison, either t1's first element should be poison or t5's shift should overflow (t2[0] >= 32).
t1's first element is non-poison if 0 <= nbits[0] < 32.
Therefore, (0 <= nbits[0] < 32) should imply (t2[0] >= 32).
Since t2[0] = nbits[0] - 64 (using 2's complement), this expression is always true.

aqjune updated this revision to Diff 308200.Nov 28 2020, 11:58 PM

update clang/test/Frontend/fixed_point_unary.c

It seems unsigned _Fract type can only represent [0.0, 1.0)? I tried to find a relevant sentence from http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1169.pdf , but couldn't.

Herald added a project: Restricted Project. · View Herald TranscriptNov 28 2020, 11:58 PM
Herald added a subscriber: cfe-commits. · View Herald Transcript
nikic accepted this revision.Nov 29 2020, 2:08 AM

LGTM

This revision is now accepted and ready to land.Nov 29 2020, 2:08 AM
This revision was landed with ongoing or failed builds.Nov 29 2020, 4:20 AM
This revision was automatically updated to reflect the committed changes.

Hi,

I'm seeing a miscompile with this patch. I'm not very good at the semantic differences between undef and poison so I don't know really where it goes wrong.

Before Early CSE I see this in the input:

entry:
  %cmp1 = icmp uge i16 1015, 16, !dbg !9
  %shr = lshr i16 -1, 1015
  %cmp2 = icmp ugt i16 2, %shr
  %or.cond = or i1 %cmp1, %cmp2, !dbg !10
  br i1 %or.cond, label %if.then3, label %if.else4, !dbg !10

This corresponds to the following C-code:

int16_t y1 = 1022;
uint16_t res1 = 0;
if (y1 < 0)
  res1 = 0;
else
  res1 = 1015;

if ((res1 >= 16) || (2 > (65535u >> res1)))
  res2 = 42;
else
  res2 = 1;

So in the C input, the right shift is guarded and won't be carried out if res1 is too large to avoid UB, but in the ll file the lshr is executed unconditionally.

Then after Early CSE I instead get

entry:
  br i1 poison, label %if.then3, label %if.else4, !dbg !9

So I suppose, with this patch the lshr will result in poison, and that poison will then make both %cmp2 and %or.cond be poison. And then we don't know where to jump so res2 gets the wrong value.

I'm not very good at poison semantics, but it seems to me that either the input to ewarly cse is invalid, or the patch has broken the semantics of "or"?

Hi,

It seems it is related to two optimizations:
(1) select i1 x, true, y -> or i1 x, y
(2) or i1 x, poison -> poison

Semantically, the first one is broken. It needs to freeze y. But, it will introduce a lot of freeze instructions. The clang patches that introduce noundef to function arguments is still ongoing.
Another workaround is to weaken (2) to or i1 x, poison -> x. This fixes the miscompilation; I'll push a commit that does this.

--- a/llvm/lib/IR/ConstantFold.cpp
+++ b/llvm/lib/IR/ConstantFold.cpp
@@ -1105,7 +1105,10 @@ Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode, Constant *C1,
   }
 
   // Binary operations propagate poison.
-  if (isa<PoisonValue>(C1) || isa<PoisonValue>(C2))
+  bool PoisonFold = !C1->getType()->isIntegerTy(1) || 
+      (Opcode != Instruction::Or && Opcode != Instruction::And &&
+       Opcode != Instruction::Xor);
+  if (PoisonFold && (isa<PoisonValue>(C1) || isa<PoisonValue>(C2)))
     return PoisonValue::get(C1->getType());
 
   // Handle scalar UndefValue and scalable vector UndefValue. Fixed-length
uabelho added a comment.EditedNov 30 2020, 5:27 AM

Hi,

It seems it is related to two optimizations:
(1) select i1 x, true, y -> or i1 x, y
(2) or i1 x, poison -> poison

Semantically, the first one is broken. It needs to freeze y. But, it will introduce a lot of freeze instructions. The clang patches that introduce noundef to function arguments is still ongoing.
Another workaround is to weaken (2) to or i1 x, poison -> x. This fixes the miscompilation; I'll push a commit that does this.

Should langref also be updated to describe this? Or does it already?
I just found this
"An instruction that depends on a poison value, produces a poison value itself."
here
http://llvm.org/docs/LangRef.html#poison-values

Should langref also be updated to describe this? Or does it already?
I just found this
"An instruction that depends on a poison value, produces a poison value itself."
here
http://llvm.org/docs/LangRef.html#poison-values

I think "Values other than phi nodes and select instructions depend on their operands." was supposed to say that. :)

Should langref also be updated to describe this? Or does it already?
I just found this
"An instruction that depends on a poison value, produces a poison value itself."
here
http://llvm.org/docs/LangRef.html#poison-values

I think "Values other than phi nodes and select instructions depend on their operands." was supposed to say that. :)

I see. Ok, thanks!

We bisected a test failure to this (https://bugs.chromium.org/p/angleproject/issues/detail?id=5500#c17). Can you expand a bit on what this patch means in practice? I'm guessing it makes UB in C++ code have bad effects more often? If so, what type of UB?

aqjune added a comment.Jan 6 2021, 4:02 PM

We bisected a test failure to this (https://bugs.chromium.org/p/angleproject/issues/detail?id=5500#c17). Can you expand a bit on what this patch means in practice? I'm guessing it makes UB in C++ code have bad effects more often? If so, what type of UB?

This patch makes the result of erroneous operations in source to participate in constant folding in more eager manner.
BTW, I am aware that this patch interacts with existing old (but hard to fix) bug in LLVM and miscompiles codes in certain code that has conditional branch + shifts. https://bugs.llvm.org/show_bug.cgi?id=48353 has more context.
Do you think your bug is related to this bug report?

aqjune added a comment.Jan 6 2021, 4:03 PM

To fix the old bug quite a few patches in LLVM have landed so far and it is still ongoing.

It turned out to be UB in our code as far as I can tell, see https://bugs.chromium.org/p/angleproject/issues/detail?id=5500#c36 and the follow-on.

(If this is known to trigger an existing bug more often, it might still be a good idea to undo it until that existing bug is fixed? But we're not affected by this existing bug as far as I can tell, so this is just a suggestion.)

aqjune added a comment.Jan 7 2021, 8:58 PM

It turned out to be UB in our code as far as I can tell, see https://bugs.chromium.org/p/angleproject/issues/detail?id=5500#c36 and the follow-on.

(If this is known to trigger an existing bug more often, it might still be a good idea to undo it until that existing bug is fixed? But we're not affected by this existing bug as far as I can tell, so this is just a suggestion.)

I don't know the policy of LLVM in this case, but it sounds legit. LLVM branching date is also near. @nikic May I ask your opinion?
BTW, shift operation is continually causing this problem interestingly - I guess shift operation with large shift amount hasn't been treated as 'that bad' for some reason.

RKSimon added a subscriber: RKSimon.Feb 3 2021, 1:45 AM

https://bugs.llvm.org/show_bug.cgi?id=49005 seems to be due to this (either directly or it has unearthed an existing problem)

aqjune added a comment.Feb 3 2021, 7:36 AM

https://bugs.llvm.org/show_bug.cgi?id=49005 seems to be due to this (either directly or it has unearthed an existing problem)

I reverted this commit; I'll reland this after the underlying problem is resolved.
I'll push the revert commit to 12.x branch as well.