Optimizing compiler. Loop optimizations

Some example estimation for loop unswitching effectivenes:

int main() {
float x[1000],y[1000];
int i,repeat,p;

for(i=0;i<1000;i++) { y[i] = i; x[i] = 1; }

for(repeat=0;repeat<3000000;repeat++) {
p=repeat%10>5;
#ifdef PERF
  if(p) {
    for(i=0;i<1000;i++) {
      x[i]=x[i]+y[i];
      y[i]++;     }
  }
    else {
      for(i=0;i<1000;i++) {
        x[i]=x[i]+y[i];     }
    }
#else
  for(i=0;i<1000;i++) {
    x[i]=x[i]+y[i];
    if(p) {
      y[i]++;      }   }
#endif
}
printf("x[123]= %f\n",x[123]);
}

Loop distribution and loop fusion are inverse optimizations. The compiler must have heuristics to estimate the profit of such optimizations.

Loop distribution can increase performance by improving memory reference. It can be applied if a loop is working with many different arrays.

If there are a lot of different invariants inside the loop than loop distribution can improve register usage.

Loop distribution can be useful for auto parallelization or vectorization.

Loop fusion can be beneficial for small loops because of improving the instructional parallelism level and data reusability.

Different microprocessors have different criteria for profitability of this optimizations.

Loop peeling (splitting) is an optimization, which tries to simplify the loop detaching the extreme iterations.

This optimization can be useful for loop fusion.

Loop unrolling is an optimization designed to reduce the loop iteration number by merging several iterations. The goal of loop unrolling is to reduce loop control instructions and branch penalties. This optimization can improve instruction parallelism and reusability of data. Main disadvantage of this optimization is code expansion.

Complete unrolling is applied to small loops and can be very effective. As a general rule in the case of nested loops, inner loops are unrolled.

Loop interchange is a loop optimization, which changes the order of iteration variables. The major purpose of loop interchange is to improve the cache performance for accessing array elements.

INTEGER,PARAMETER :: N=100
INTEGER,PARAMETER :: REPEAT=1000
INTEGER :: A(N,N,N), B(N,N,N)
INTEGER :: REP,I,J,K

A=1
B=1

DO REP=1,REPEAT

  DO I=1,N
    DO J=1,N
      DO K=1,N
        A(J,K,I) = A(J,K,I)+B(J,K,I)
      END DO
    END DO
  END DO

END DO

PRINT *,A(1,1,1)
END

Loop blocking is a loop optimization which divides a loop iteration space into smaller chunks or blocks, so the loop data stays in the cache until it is reused. The partitioning of loop iteration space leads to partitioning the array used, so array elements fit the cache better, it enhancing cache reuse and decreasing required cache size.

INTEGER, PARAMETER :: N=2000
 INTEGER :: BF,BN,I,J,K,I1,J1,K1
 DOUBLE PRECISION, ALLOCATABLE :: A(:,:),B(:,:),C(:,:)

 ALLOCATE(A(N,N),B(N,N),C(N,N)) 
 A=1
 B=-1 

#ifdef PERF
 BF=8
 BN=N/BF
 DO I1=1,BF
  DO J1=1,BF
   DO K1=1,BF
    DO I=1+BN*(I1-1),MIN(BN*I1,N)
     DO J=1+BN*(J1-1),MIN(BN*J1,N) 
      DO K=1+BN*(K1-1),MIN(BN*K1,N)
        C(J,I) = C(J,I) + A(I,K)*B(K,J)
      END DO
     END DO
    END DO
   END DO
  END DO
 END DO   

#else

 DO I=1,N
  DO J=1,N
   DO K=1,N
    C(J,I) = C(J,I) + A(I,K)*B(K,J)
   END DO
  END DO
 END DO 
#endif

 PRINT *,C(1:100,700:800)
END

Strength reduction

Expressions, which are a linear function of the iteration counts can be calculated by adding the constant to the value at the previous iteration.

In addition to these optimizations, there are other, sometimes very complex:

The compiler in each case should prove the correctness of the optimization and determine its profit.

Dependence

The calculations are equivalent if they calculate the same data and output the same values in the same order.

Each task can be calculated with different sequences of instructions (some of which may be more effective than the others) if they are equivalent. Optimization which change sequence of instructions is called permutational.

What features of the task instructions could cause wrong results because of instruction permutation?

Dependence is a connection between the statement of the program. A couple of statements <S1,S2> are dependent, if S2 should be performed after S1 in order to maintain the same result.

S1 PI = 3.14
S2 R = 5
S3 AREA = PI * R ** 2

<S1,S2,S3> Equivalent <S2,S1,S3>

So there are two dependencies. <S1,S3>, <S2,S3>

The concept of linear dependence in the code is simple, but to get real benefits from the changes we need to extend this concept for loops and arrays.

DO I = 1, N
S1 A (I) = B (I) + 1
S2 B (I +1) = A (I) - 5
END DO 

There is a dependence <S2,S1> <S1,S2> for all iterations except the first.

These dependencies are an example of data dependences.

S1 IF (T.NE.0) THEN
S2 A = A / T
S3 ENDIF

This is an example of control dependence. S2 can not be evaluated before S1.

Definition:

There is a data dependence between statement S1 and S2 if and only if

Dependencies are classified as follows:

True dependence (flow dependence)
 S1 X = ...
 S2 ... = X
Represented as S1?S2 (? - delta) 

Antidependence
  S1 ... = X
  S2 X = ...
S1?-S2 

Output dependence 
S1 X = ...
S2 X = ...
S1?0S2

Loops

Loop dependencies can be more complicated

DO I = 1, N
S1 A (I +1) = A (I) + B (I)
END DO 

S1 depends on itself at the previous iteration

DO I = 1, N
S1 A (I +2) = A (I) + B (I)
 END DO 

Normalized loop is usually used for analysis. Such loop starts from 1 to N with step 1. Any loop can be normalized (converted to normalized form).

Nested loops

If we have a nested loop. Then the iteration vector I of some iteration is a vector of integers, each of which represents the value of the iteration variable for each loop in the nesting order.

I = {i1, i2, ..., in}

There is a loop dependency between the statements S1 and S2 in the set of nested loops, if and only if:

Now our task is to link the equivalence of two computational processes (in our case, before and after compiler optimization) with the definition of dependence. All loop optimizations discussed earlier are permutational (reordering) transformations. These transformations change the order of the instructions.

The fundamental dependency theorem:

Each optimization which preserves the dependencies in the program (i.e. does not change the order of the dependent claims) produces equivalent calculation.

Accordingly, some transformation is valid in this program if it preserves all the dependencies in the program.

How to determine the dependences in the case of a single array?

Assume that we have a set of nested loops

DO i1 = 1, N1
  DO i2 = 1, N2
    ...
      DO in = 1, Nn
S1 A (f1 (i1, ..., in), ..., fm (i1, ..., in)) =
        A (g1 (i1, ..., in), ..., gm (i1, ..., in))
      END DO
    ...
  END DO
END DO 

Dependence exists if and only if there are iteration vectors I and J, such that

I <J and the following system of equations:

fi (I) = gi (J)

can be solved

Example:

DO I = 1, N
  A (I +1) = A (I) + B
END DO
I +1 = I + x

Dependency evaluation is complicated computational task even for single array usage.

Optimizing compiler uses different methods for proving permissibility of different permutational optimizations. In case when loop contains a lot of different arrays and pointers, this task can be very hard. Estimation can be used instead of precise calculation.

Alias analysis

Alias analysis is a technique used to determine if a storage location may be accessed in more than one way. Two pointers are said to be aliased if they point to the same location.

In order to properly find the dependence in the program is important to remove any memory ambiguity. That is, to identify all objects that may overlap in memory.

Optimizing compiler uses all possible information for decision making:

If there are objects which compiler can not prove to have different locations, then compiler needs to act conservatively and forbid permutation optimization.

File sub.c

int sub(int *a, float *b, int n) {
int i;
for(i=0;i<n;i++) {
   a[i]=0;
}
for(i=0;i<n;i++){
   b[i]=0.0;
} 
}

File main.c

#include <stdio.h>
#include <stdlib.h>

extern void sub(int *a,float *b, int n);
int main(){
int *a;
float *b;
a=(int*)malloc(100*sizeof(int));
b=(float*)malloc(100*sizeof(int));

sub(a,b,100);
printf("%d;%f\n",a[0],b[0]);
}

icc main.c 2.c –O3 
2.c(3): (col. 1) remark: LOOP WAS VECTORIZED.
2.c(6): (col. 1) remark: LOOP WAS VECTORIZED.

icc main.c 2.c –O3 –ansi-alias
2.c(3): (col. 1) remark: FUSED LOOP WAS VECTORIZED.

What's the difference?

-[no-]ansi-alias enable/disable(DEFAULT) use of ANSI aliasing rules in optimizations; user asserts that the program adheres to these rules.

ANSI aliasing rules require that the pointers can refer only to the objects of the same or compatible type. This means in practice that the pointers of incompatible type can not address the same memory.

Using –anti-alias option at compile time allows compiler to perform more aggressive optimizations.

There are special attributes in C/C++ language to facilitate the work of the compiler with the alias analysis. Pointers can be declared as restrict. This attribute means that only a pointer or an expression based on this pointer can refer to memory which is related with this pointer.

int sub (int * a, float * b, int n)
=>
int sub (int * restrict a, float * restrict b, int n)

Fortran language has stronger rules for pointers. Although the language has pointers to arrays, but each array, which can be referenced through the pointer must be explicitly declared as TARGET. By default, function arguments can’t refer to the same location. These rules simplify alias analysis.

Compiler contains special option to show the results of different optimizations /Qopt-report[:n]

Example:

LOOP INTERCHANGE in loops at line: 8 9 
Loopnest permutation ( 1 2 ) --< ( 2 1 )
Fusion loop partitions: (loop line numbers)
Fused Loops: ( 9 14 )