Page MenuHomePhabricator

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

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




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.


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.

Diff Detail


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.


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

Closed by commit rL219406 (authored by adibiagio).