ashr, lshr, shl, udiv should have an 'isexact' bit indicating it is known to only shift out zeros

[lattner]

Bugzilla Link	8862
Resolution	FIXED
Resolved on	Feb 09, 2011 23:39
Version	trunk
OS	All
Blocks	llvm/llvm-bugzilla-archive#8882 llvm/llvm-bugzilla-archive#8942
CC	@lattner,@sunfishcode

Extended Description

Instcombine should compile this identity function to return X:

define i32 @​test(i32 %X) {
%A = sdiv exact i32 %X, 4
%B = mul i32 %A, 4
ret i32 %B
}

instead we get:

define i32 @​test(i32 %X) {
%A1 = and i32 %X, -4
ret i32 %A1
}

This is because it simplifies the sdiv into an ashr instruction, which loses information. This sort of thing comes up when handling array/pointer difference stuff.

To fix this, SDISel whould lower sdiv exact into ashr, instcombine should handle sdiv's as aggressively as ashr's, and then we should stop canonicalizing ashr to sdiv in instcombine.

[lattner]

Another, possibly better, solution is to add an "isexact" sort of bit to the ashr instruction. This would indicate that no bits get shifted out, and would make just as much sense for left and right logical shifts.

[lattner]

*** Bug llvm/llvm-bugzilla-archive#8882 has been marked as a duplicate of this bug. ***

[lattner]

llvm/llvm-bugzilla-archive#8882 is an example that shows the need for this bit for SHL. SCEV has an example where it knows that udivs are exact (see r123139) and we'd like to be able to represent this too.

[lattner]

This is largely in now, I have a bunch of instcombine changes to detangle from each other and plan to submit them later this afternoon.

[lattner]

This is now implemented in a series of patches leading up to r125267.

We now have get:

$ opt -instcombine -S
define i32 @​test(i32 %X) {
%A = sdiv exact i32 %X, 4
%B = mul i32 %A, 4
ret i32 %B
}
^D
; ModuleID = ''

define i32 @​test(i32 %X) {
ret i32 %X
}

[lattner]

mentioned in issue llvm/llvm-bugzilla-archive#8882

[lattner]

mentioned in issue llvm/llvm-bugzilla-archive#8942