Compiler Optimizations (Software)

• They provide efficient mapping of the program to the machine
  • Constantly replace easy arithmetic with constant values
  • Allocate registers for the variables of interest
  • removes code that will never be executed
  • the asymptomatic efficiency never really increases

Compiler Optimization Process

1. Code is sent to the compiler
2. The compiler creates an abstract syntax tree, with arguments and function calls (code)
3. The compiler creates an intermediate representation control data flow graph (similar to assembly)
   1. They have abstract instructions, infinite registers…
4. Optimizations occur to the CDFG ^
5. Code Generation → chooses registers, choosing instructions, choosing assembly layout

Limitations of Compilers

• the compiler cannot change any of the behavior within the program
• Behavior that seems obvious to the programmer can be obfuscated by languages and coding styles (data ranges more limited than what type represents)
• Most of the analysis is performed only within the individual procedures because analyisis of the entire program might be too expensive to look over
• Compilers do not know some of the dynamic inputs at run time

void cs33fun(char* Midterm, char* Grade, int* Final, int n) {
	for (int i = 0; i < (strlen(Midterm)); i++) { //can move strlen midterm
		strcat(Grade, Midterm); // cannot move out (essential for logic)
		for (int j = 0; j < n; j++)
			for (int k = 0; k < i; k++)
				Final[j] += strlen(Grade); // cannot move this outside since changes over iter.
																	// we can move it after the first loop
	}
}

Useful General Optimizations

Code Motion: When the compiler will go ahead and reduce the number of times the code needs to be compiled.

void set_row(double *a,   
  double *b, long i, long n)
{
    long j;
    for (j = 0; j < n; j++)
	a[n*i+j] = b[j];
}

// Optimized
long j;
int ni = n*i;
for (j = 0; j < n; j++)
     a[ni+j] = b[j];

Reduction in Strength: Replace a costly operation with a simpler one (multiplication to shifting)

Share Common Subexpressions: Reuse some of the portions of the expressions so that it will not have to repeat the calculations

/* Sum neighbors of i,j */
up =    val[(i-1)*n + j  ];
down =  val[(i+1)*n + j  ];
left =  val[i*n     + j-1];
right = val[i*n     + j+1];
sum = up + down + left + right;

// Optimized
long inj = i*n + j; // optimized line
up =    val[inj - n];
down =  val[inj + n];
left =  val[inj - 1];
right = val[inj + 1];
sum = up + down + left + right;