Optimization Techniques Used by IBM C and C++ Compilers

Technique

Description of Technique
Value Numbering Involves constant propagation, expression elimination, and folding of several instructions into a single instruction.
Branch Optimizations Rearranges the program code to minimize branching logic and to combine physically separate blocks of code.
Common Subexpression Elimination In common expressions, the same value is recalculated in a subsequent expression. The duplicate expression can be eliminated by using the previous value. This step is done even for intermediate expressions within expressions. For example, if your program contains the following statements: 
a = c + d;
    .
    .
    .
f = c + d + e;

the common expression c + d is saved from its first evaluation and is used in the subsequent statement to determine the value of f.

Code Motion If variables used in a computation within a loop are not altered within the loop, the calculation can be performed outside of the loop and the results used within the loop.
Invariant IF Code Floating (Unswitching) Removes invariant branching code from loops to make more opportunity for other optimizations.

For example, in the following code segment, the condition test and the conditional assignment: 

if (a[i]>100.0) b[i]=a[i]-3.7;
    x+=a[j]+b[i];

do not change during execution of the inner loop. 

for (i=0;i<1000;i++) {
   for (j=0;j<1000;j++) {
      if (a[i]>100.0) b[i]=a[i]-3.7;
      x+=a[j]+b[i];
   }
}

The compiler translates the code into a machine-language loop that executes as: 

for (i=0;i<1000;i++) {
   if (a[i]<100.00) {
      for (j=0;j<1000;j++) {
         b[i]=a[i]-3.7;
         x+=a[j]+b[i];
      }
   }
   else {
      for (j=0;j<1000;j++) {
         x+=a[j]+b[i];
      }
   }
}
Reassociation Rearranges the sequence of calculations in an array-subscript expression, producing more candidates for common-expression elimination.
Strength Reduction Replaces less efficient instructions with more efficient ones. For example, in array subscripting, an add instruction replaces a multiply instruction.
Constant Propagation Constants used in an expression are combined, and new ones are generated. Some implicit conversions between integer and floating-point types are done.
Store Motion Moves store instructions out of loops.
Dead Store Elimination Eliminates stores when the value stored is never referred to again. For example, if two stores to the same location have no intervening load, the first store is unnecessary and is removed.
Dead Code Elimination Eliminates code that cannot be reached or code whose results are not subsequently used.
Inlining
( -Q option )		 Replaces function calls with actual program code.
Instruction Scheduling Reorders instructions to minimize execution time.
Interprocedural Analysis
( -qipa option )		 Uncovers relationships across function calls, and eliminates loads, stores, and computations that cannot be eliminated with more straightforward optimizations.
Global Register Allocation Allocates variables and expressions to available hardware registers using a graph coloring algorithm.

The -O and -Q compiler options also determine the types of inlining to be used.


Program Optimization with IBM C and C++ Compilers
Special Handling of Math and String Library Functions


Writing Optimized Code


ipa Compiler Option
-O Compiler Option
-Q Compiler Option