induction variable elimination

[YZhan69]

It seems induction variable elimination is a well known compiler transformation, but I can't get ICC to do it, nor with GCC.

https://www.cs.utexas.edu/~pingali/CS380C/2013/lectures/strengthReduction.pdf

Here's my test program:

int main(int argc, char **argv)
{
  typedef int64_t /*int32_t*/ LoopType;
  LoopType REPEATS = 1000000, N = atoi(argv[1]);
  int16_t *data = (int16_t *)alloca(N * sizeof(int16_t));
  for (int j = 0; j < REPEATS; ++j)
  {
    for (LoopType i = 0; i < N; i += (LoopType)8)
    {
      __m128i d = _mm_loadu_si128((__m128i *)&data);
      d = _mm_add_epi16(d, d);
      _mm_storeu_si128((__m128i *)&data, d);
    }
  }
  return data[5];
}

assembly code for inner most loop:

..B1.4:                         # Preds ..B1.2 ..B1.4
        movdqu    (%rsi), %xmm0                                 #50.30
        incq      %rdi                                          #53.5
        paddw     %xmm0, %xmm0                                  #56.11
        movdqu    %xmm0, (%rsi)                                 #50.30
        addq      $16, %rsi                                     #53.5
        cmpq      %rdx, %rdi                                    #53.5
        jb        ..B1.4        # Prob 82%                      #53.5

What I want is for the compiler to replace the loop counter i with the pointer expression &data. I recognize there's a gotcha (overflow) that prevents the compiler from doing that transform. But I also found out GCC has a flag -funsafe-loop-optimizations that assumes overflow won't happen.

But that didn't help. I've tried compiling the code above with both ICC 14 and GCC 4.9 and it always results in 2 induction variables (usually 7 instructions) compared to 6 if I manually use a pointer as the loop condition.

I've tried changing the loop type from int64 to int32 and changing the for loop to a do - while (1 fewer branch) but that didn't help either.

Performance wise, I found there's no difference from saving 1 instruction:

output of Linux perf for N = 32768

    8,687,218,116 cycles                    #    2.103 GHz
       485,770,953 stalled-cycles-frontend   #    5.59% frontend cycles idle
        29,257,198 stalled-cycles-backend    #    0.34% backend  cycles idle
    28,684,643,143 instructions                   #    3.30  insns per cycle

output of Linux perf for N = 32768, after replacing loop condition i with pointer

  8,292,816,300 cycles                    #    2.102 GHz
       102,773,625 stalled-cycles-frontend   #    1.24% frontend cycles idle
        29,845,621 stalled-cycles-backend    #    0.36% backend  cycles idle
    24,586,051,519 instructions              #    2.96  insns per cycle
 

This makes sense because instruction level parallelism means the extra add won't increase the critical path. But it will free up a register which is a good thing. 

I also realize that if you have > 1 array expression in your loop, then induction variable elimination wouldn't help reduce # instructions, since it would be cheaper to have 1 counter and use register + register addressing for array indexing.

So it seems the benefit of induction variable elimination is limited. Can someone confirm whether or not induction variable is implemented in ICC or any other compiler? I want to know because I have to decide whether to manually do this optimization to the detriment of readability, or keep using counters and hope that some future compiler will be able to optimize it.

[Kittur_G_Intel]

Hi,
The compiler can’t guarantee that N times the base address is a reasonable value to compare against and hence the induction variable is required. The only way you could eliminate the increment of the base address is by using a scale/index but that’s not possible since there’s no 16x scale. 
_Kittur

[jimdempseyatthecove]

Try:

int main(int argc, char **argv)
{
  typedef int64_t /*int32_t*/ LoopType;
  LoopType REPEATS = 1000000, N = atoi(argv[1]);
  int16_t *data = (int16_t *)alloca(N * sizeof(int16_t));
  for (int j = 0; j < REPEATS; ++j)
  {
    __m128i * from, beyond;
    from = (__m128i *)&data[0];
    beyond = (__m128i *)&data;
    
    for (__m128i* p = from; p < beyond; ++p)
    {
      __m128i d = _mm_loadu_si128(p);
      d = _mm_add_epi16(d, d);
      _mm_storeu_si128(p, d);
    }
  }
  return data[5];
}

Jim Dempsey

[jimdempseyatthecove]

Or:

int main(int argc, char **argv)
{
  typedef int64_t /*int32_t*/ LoopType;
  LoopType REPEATS = 1000000, N = atoi(argv[1]);
  int16_t *data = (int16_t *)alloca(N * sizeof(int16_t));
  for (int j = 0; j < REPEATS; ++j)
  {
    __m128i * from, beyond;
    from = (__m128i *)&data[0];
    beyond = (__m128i *)&data;
    LoopType count = beyond - from;
    for (LoopType i = 0; i < count; ++i)
    {
      __m128i d = _mm_loadu_si128(&from);
      d = _mm_add_epi16(d, d);
      _mm_storeu_si128(&from, d);
    }
  }
  return data[5];
}

You may find the second format will unroll the inner loop.

Jim Dempsey