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[2i][4j] = i;
B++ = A[8i][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[n2i + 4*j] = i;
B++ = A[n8i + 6j + 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