This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Fix wrong folding of constant comparisons involving ashr and negative values (PR21222).
ClosedPublic

Authored by andreadb on Oct 9 2014, 3:57 AM.

Details

Summary

Hi,

Here is a case where the instruction combiner wrongly folds an 'icmp' instruction.
;;
define i1 @test(i32 %B) {

%shr = ashr i32 -93, %B
%cmp = icmp eq i32 %shr, -2
ret i1 %cmp

}
;;

Function @test returns true when %B is equal to 6 (that is because -93 >> 6 = -2).
However, the Instruction Combiner wrongly thinks that there is no 'B' that solves equation: -93 >> B == -2.
Consequently, the entire body of function @test is wrongly folded into a return i1 false.

The problem is in the folding logic located in method InstCombiner::FoldICmpCstShrCst (InstCombineCompares.cpp) which wrongly computes the distance between two negative values.

With:

AP1 < 0
AP2 < 0
AP2 != 0
AP1 != 0
AP1 > AP2

The distance between AP2 and AP1 (i.e. the distance between the highest bits set) is wrongly computed as:

(-AP2).logBase2() - (-AP1).logBase2()

It should be computed instead taking the ones' complement of AP2 and AP1:

(~AP2).logBase2() - (~AP1).logBase2()

This patch fixes the problem with the wrong folding of icmp.

Please let me know if ok to submit.
Thanks!
Andrea

Diff Detail

Repository
rL LLVM

Event Timeline

andreadb updated this revision to Diff 14646.Oct 9 2014, 3:57 AM
andreadb retitled this revision from to [InstCombine] Fix wrong folding of constant comparisons involving ashr and negative values (PR21222)..
andreadb updated this object.
andreadb edited the test plan for this revision. (Show Details)
andreadb added reviewers: dexonsmith, suyog, hfinkel.
andreadb added subscribers: Unknown Object (MLST), test.
suyog edited edge metadata.Oct 9 2014, 5:12 AM

Hi Andrea,

Thanks for investigating and fixing the bug.
I agree with your point that distance should be calculated using one's compliment
instead of two's compliment.

LGTM.

Diffusion closed this revision.Oct 9 2014, 5:52 AM
Diffusion updated this revision to Diff 14649.

Closed by commit rL219406 (authored by adibiagio).