[LLVMdev] sign extensions, SCEVs, and wrap flags
Preston Briggs
preston.briggs at gmail.com
Fri Sep 21 17:28:26 PDT 2012
>> Are all your array indices uniformly sign-extended?
>> I don't know if this is a good idea, but why can't you consider the
sext
>> operand the array index rather than the gep operand? If you prove
that the
>> narrow indices are disjoint, then the extended indices must be
disjoint.
>> SCEV operations should work fine on the narrow indices which
shouldn't have
>> any impure type casting operations.
>>
>> This can all be avoided by limiting your optimization to code that
uses
>> pointer-size loop counters!
>>
>> The array indices are out of my control; depends on the code people
>> write. If they'd use long ints for everything, life would be good; but
ints happen.
>
> I thought array indices were promoted to a larger size when possible...
This
> came up with Ada where loops with i8 counters are quite common. Dan added
> logic to boost the size of the loop counters, but perhaps it doesn't
promote
> them beyond i32, or doesn't apply here for some reason?
Here's an example I ran into today.
*void miv7(int n, int A[][n], int *B) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
A[2*i][4*j] = i;
*B++ = A[8*i][6*j + 1];
}
}*
If I look at the store to A (src) and the load from A (dst), I see the
following:
*src = ((sext i32 {0,+,4}<%for.body3> to i64) +*
* ((zext i32 %n to i64) * (sext i32 {0,+,2}<%for.cond1.preheader> to
i64)))*
*dst = ((sext i32 {1,+,6}<%for.body3> to i64) +*
* ((zext i32 %n to i64) * (sext i32 {0,+,8}<%for.cond1.preheader> to
i64)))*
I speculate that some earlier analysis decided that since n is used as an
array bound, it much be >= 0, and therefore unsigned.
If n, i, and j are all declared as long ints, I get the much cleaner
*src = {{0,+,(2 * %n)}<%for.cond1.preheader>,+,4}<%for.body3>*
*dst = {{1,+,(8 * %n)}<%for.cond1.preheader>,+,6}<%for.body3>*
which I can analyze accurately.
The manually linearized version
*void miv8(int n, int *A, int *B) {*
* for (int i = 0; i < n; i++)*
* for (int j = 0; j < n; j++) {*
* A[n*2*i + 4*j] = i;*
* *B++ = A[n*8*i + 6*j + 1];*
* }*
*}*
yields
*src = (sext i32 {{0,+,(2 * %n)}<%for.cond1.preheader>,+,4}<%for.body3> to
i64)*
*dst = (sext i32 {{1,+,(8 * %n)}<%for.cond1.preheader>,+,6}<%for.body3> to
i64)*
which is susceptible to Andy's idea of removing identical sign extensions
before starting.
Preston
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120921/d561cd59/attachment.html>
More information about the llvm-dev
mailing list