Page MenuHomePhabricator

InstCombine: constant comparison involving ashr is wrongly simplified (PR20945).
AbandonedPublic

Authored by andreadb on Sep 15 2014, 8:53 AM.

Details

Summary

Example:

;;;;
define i32 @negative_constants(i32 %B) {
entry:

%shr = ashr i32 -9, %B
%cmp = icmp ne i32 %shr, -5
br i1 %cmp, label %if.then, label %return

if.then:

br label %return

return:

%retval = phi i32 [ 0, %if.then ], [ 42, %entry ]
ret i32 %retval

}
;;;

The instruction combiner wrongly thinks that statement 'ashr i32 -9, %B' can never evaluate to -5. Therefore, it wrongly assumes that %cmp would always be 'true' and the branch to 'if.then' would always be taken.

In this reproducible, if %B is equal to 1, then %cmp is 'false' (since %shr would be equal to -5).
Therefore, it is not safe to fold %cmp to 'true'. What instead should be done is converting the comparison between %shr and -5 into a comparison between %B and 1. This would allow us to get rid of the arithmetic shift (and eventually simplify the CFG folding the compare-and-branch into a single select of either 0 or 42).

This is a regression introduced by revision 213678. This bug seems to affect only the case where constants are both negative values.

Please let me know if ok to submit.

Thanks,
Andrea

Diff Detail

Event Timeline

andreadb updated this revision to Diff 13712.Sep 15 2014, 8:53 AM
andreadb retitled this revision from to InstCombine: constant comparison involving ashr is wrongly simplified (PR20945)..
andreadb updated this object.
andreadb edited the test plan for this revision. (Show Details)
andreadb added reviewers: suyog, dexonsmith, hfinkel.
andreadb added a subscriber: Unknown Object (MLST).
suyog edited edge metadata.Sep 15 2014, 11:31 PM

Hi Andrea,

Thanks for pointing out the bug. I went through the code and the example and
i agree that we need to revert the canonicalization if both AP1 and AP2 are negative.
Your patch seems ok to me, though i would like others to approve it.

Also i had few suggestions for comments and test case in the patch which i noted inline
(feel free to edit if they seem good to you).

I would like Duncan to review this for final commit as we had worked on the original patch.

lib/Transforms/InstCombine/InstCombineCompares.cpp
1126

This comment can be made crisp. Something like - Revert the canonicalization if both AP1 and AP2 are negative,
as (-AP2 >> Shift == -AP1) is not equal to (AP2 >> Shift == AP1)

1129

This comment can be removed.

test/Transforms/InstCombine/icmp-shr.ll
704

This test case can be simplified (exclude if-else part as patch focuses on icmp result)

; CHECK-LABEL: @negative_constants(
; CHECK: icmp eq i32 %B, 1
define i1 @negative_constants(i32 %B) {
  %shr = ashr i32 -9, %B
  %cmp = icmp ne i32 %shr, -5
  ret i1 %cmp
}

Hi Suyog,

Thanks for the useful comments/suggestions!
I will upload another patch soon.

lib/Transforms/InstCombine/InstCombineCompares.cpp
1126

Ah yes. I was not very happy about my original comment here... I like your suggestion. I will fix.

1129

I will fix it.

test/Transforms/InstCombine/icmp-shr.ll
704

True. I will upload a new patch with the simplified test case (I will also address the other comments).

andreadb updated this revision to Diff 13741.Sep 16 2014, 3:25 AM
andreadb edited edge metadata.

Updated patch that addresses the comments from Suyog.

andreadb updated this revision to Diff 13759.Sep 16 2014, 12:58 PM

Hi Duncan,

Here is an updated patch which I think/hope addresses all your comments.

There is one main difference with respect to what you suggested (see below)

Then change this to:

if (!IsNegative && AP1.ugt(AP2))
  // Right-shifting won't increase the magnitude.
  return getConstant(false);

That check should also take into account the case where 'IsAShr' is false, AP2 is negative and AP1 is positive.
Otherwise, it would have failed for the following case:

{code}
define i1 @foo(i8 %a) {

%shr = lshr exact i8 -128, %a
%cmp = icmp eq i8 %shr, 1
ret i1 %cmp

}
{code}

Please let me know what you think.
Thanks,
Andrea

andreadb updated this revision to Diff 13764.Sep 16 2014, 2:58 PM

I don't think that case exists. lshr deals with unsigned numbers.
There's no such thing as a negative unsigned number. For lshr, it's
easier to think about numbers as bitstrings.

Otherwise, it would have failed for the following case:

{code}
define i1 @foo(i8 %a) {

%shr = lshr exact i8 -128, %a
%cmp = icmp eq i8 %shr, 1
ret i1 %cmp

}
{code}

In binary, this translates to:

define i1 @foo(i8 %a) {
  %shr = lshr exact i8 0b10000000, %a
  %cmp = icmp eq i8 %shr, 0b00000001
  ret i1 %cmp
}

AFAICT, this transformation should produce:

define i1 @foo(i8 %a) {
  %cmp = icmp eq i8 %a, 7
  ret i1 %cmp
}

Does it do something else? What? Can you add this as a testcase?

Sorry, you are right.
That test does exactly what you said (i.e. it produces the compare between %a and 7).
Btw, that is from test 'icmp-shr.ll'. It is function @exact_lshr_eq_opposite_msb.
I think I was probably using the wrong compiler when I saw that test case failing.. sorry for the noise.

Please let me know what you think.
Thanks,
Andrea

http://reviews.llvm.org/D5356

Files:

lib/Transforms/InstCombine/InstCombineCompares.cpp
test/Transforms/InstCombine/icmp-shr.ll

<D5356.13759.patch>

+ if (!IsAShr) {
+ bool IsAP1Negative = AP1.isNegative();
+ bool IsAP2Negative = AP2.isNegative();
+ if (IsAP1Negative && IsAP2Negative)
+ Logical shift by a non-zero quantity always changes the sign bit of a
+
negative number.
+ return getConstant(false);
+ if (IsAP1Negative)
+ Logical shift never affects the sign of a positive number.
+ return getConstant(false);
+ if (!IsAP2Negative && AP1.ugt(AP2))
+
Right-shifting will not increase the value.
+ return getConstant(false);
+ }

This new logic doesn't make sense to me. Note that isNegative() just
tells you whether the MSB is set to 1. How is the MSB relevant here?
(It certainly isn't a sign bit.)

I agree it is not relevant.
Again, sorry for the confusion.

Here is an updated patch.
-Andrea

dexonsmith resigned from this revision.Aug 25 2019, 8:21 AM
andreadb abandoned this revision.Aug 25 2019, 8:36 AM