What is a reduction variable? Can anyone give me some examples?

Here's a simple C-like example of calculating the sum of an array:

int x = 0;
for (int i = 0; i < n; i++) {
    x += a[i];
}

      

        
        
        
      

    

In this example

• i
  
  - induction variable - at each iteration it changes by some constant. It could be +1
  
  (like in the example above) or *2
  
  or /3
  
  etc., but the key is that the number is the same in all iterations.

  In other words, at each iteration i_new = i_old op constant
  
  , where op
  
  there +
  
  , *
  
  etc., and audio op
  
  not constant
  
  are not changed between iterations.

• x
  
  is a decrement variable - it accumulates data from one iteration to the next. It always has some initialization ( x = 0
  
  in this case), and although the accumulated data may be different in each iteration, the statement remains the same.

  In other words, at each iteration x_new = x_old op data
  
  and op
  
  remains unchanged in all iterations (although it data
  
  may change).

Many languages have a special syntax for doing something like this - often called "fold" or "shrink" or "accumulate" (and have other names), but in the LLVM IR context, the induction variable will be represented by the phi node in the loop between the binary operation inside the loop and the initialization value before it.

Commutative * operations on reduction variables (eg add) are especially interesting to the optimizing compiler because they seem to show a stronger dependency between iterations than they actually do; for example, the above example could be rewritten to vectorized form - by adding, say, 4 numbers at a time, and then a little loop to add the final vector into one value.

_{* there are actually more conditions that need to be met by the reduction variable before such vector navigation can be applied, but which is really outside the scope here}