[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
>>     operand the array index rather than the gep operand? If you prove
that the
>>     narrow indices are disjoint, then the extended indices must be
>>     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
>>     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...
> 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
> 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

*src = ((sext i32 {0,+,4}<%for.body3> to i64) +*
*       ((zext i32 %n to i64) * (sext i32 {0,+,2}<%for.cond1.preheader> to
*dst = ((sext i32 {1,+,6}<%for.body3> to i64) +*
*       ((zext i32 %n to i64) * (sext i32 {0,+,8}<%for.cond1.preheader> to

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];*
*    }*


*src = (sext i32 {{0,+,(2 * %n)}<%for.cond1.preheader>,+,4}<%for.body3> to
*dst = (sext i32 {{1,+,(8 * %n)}<%for.cond1.preheader>,+,6}<%for.body3> to

which is susceptible to Andy's idea of removing identical sign extensions
before starting.

-------------- 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