Because the optimizations the compilers can perform interact with each other, and because no two programs are alike, it is impossible to specify a fixed set of options that give the best results in all cases. Nevertheless, the following is a good set of compiler flags to start with:

-n32 -mips4 -O2 -OPT:IEEE_arithmetic=3 -lfastm -lm

The meaning of these options is as follows:

The -n32 and -mips4 options are discussed in “Selecting an ABI and ISA” in Chapter 3; the library choice under “libfastm Library” in Chapter 3. The others are discussed in the topics in this chapter.

Using this set of flags for all modules of a large program suite may produce acceptable performance. If so, tuning is complete. Otherwise, the performance-critical modules will require compilation with higher levels of optimization than -O2. These levels are discussed under “Setting Optimization Level with -On”.

The compilers have many options that are specified in the conventional UNIX fashion, as a hyphen followed by a word. For example, optimization level -O2; ABI level -n32; separate compilation of a module -c; request assembler source file -S. These options are all documented in the compiler man pages cc(1) , f77(1) , f90(1) . (You will find that it is useful to keep a printed copy of your compiler's man page near your keyboard.)

The compilers categorize other options into groups. These groups of options are documented in separate man pages. The option groups are listed in Table 5-1.

The syntax for an option within a group is:

-group:option[=value][:option[=value]]...

You can specify a group heading more than once; the effects are cumulative. For example,

cc -CLIST:linelength=120:show=ON -TARG:platform=ip27 -TARG:isa=mips4

Many of the grouped options are documented in this and the following chapters. All compiler options mentioned are in the index under the heading “compiler option.”

The compiler has defaults for all options, but often they are not what you might expect. For example, the compiler optimizes the generated code for a particular hardware type as specified with the -TARG option group (detailed later in “Setting Target System with -TARG”). The default for the target hardware is not, as you might expect, the system on which the compiler runs, but the Power Challenge R10000—as of release 7.2.1. The default might change in a later release.

You can alter the compiler's choice of defaults for some, but not all, options by changing the file /etc/compiler.defaults, as documented in the MIPSpro Compiling and Performance Tuning Guide and the cc(1) documents listed in “Related Documents”. However, this changes the defaults for all compilations by all users on that system.

Because at least some defaults are in the control of the administrator of the system, you cannot be certain of the compiler's defaults on any given system. As a result, the only way to be certain of consistent results is to specify all important compiler options on every compile. The only convenient way of doing this is with a Makefile.

You want to use the many compiler options consistently, regardless of which computer you use to run the compilation; also, you want to experiment with alternative options in a controlled way. The best way to avoid confusion and to get consistent results is to use a Makefile in which you define all important compiler options as variables. Example C-4 shows a starting point for a Makefile.

For a straightforward program, a Makefile like the one in Example C-4 may be all you need. To use it, create a directory for your program and move the source files into the directory. Create a file named Makefile containing the lines of Example C-4. Edit the file and fill in the lines that define EXEC (the program name) and FOBJS and COBJS, the names of the component object files.

To build the program, enter

% make 

The make program compiles the source modules into object modules using the compiler flags specified in the variables defined in the first few lines, then links the executable program.

To remove the executable and objects, so as to force recompilation of all files, use

% make clean 

You can override the Makefile setting of any of the variables by specifying its value on the command line. For example, if the OLEVEL variable does not permit debugging (-Ofast=ip27 does not), you can compile a debugging version with the following commands:

% make clean; make OLEVEL="-O0 -g3"

You can add extra compilation options with the DEFINES variable. For example,

% make DEFINES="-DDEBUG -OPT:alias=restrict" 

The basic optimization flag is -On, where n is 0, 1, 2, 3, or fast. This flag controls which optimizations the compiler will attempt: the higher the optimization level, the more aggressive the optimizations that will be tried. In general, the higher the optimization level, the longer compilation takes.

Although the R10000, R8000, and R5000 CPUs all support the MIPS IV ISA (see “Selecting an ABI and ISA” in Chapter 3), their internal hardware implementations are quite different.

The compiler does not simply choose the machine instructions to be executed, which would be the same for any MIPS IV CPU. It carefully schedules the sequence of instructions so that the CPU will make best use of its parallel functional units. The ideal sequence is different for each of the CPUs that support MIPS IV. Code scheduled for one chip runs correctly, but not necessarily in optimal time, on another.

You can instruct the compiler to generate code optimized for a particular chip by using the CPU-type flags on the compiler's command line. These flags, when used while linking, cause libraries optimized for the specified chip, if available, to be linked. Specially optimized versions of libfastm exist for some CPUs (see the libfastm man page).

You can also specify the target chip using an alternative flag, -TARG:processor=N. This flag tells the compiler to generate code optimized for the specified chip. However, the flag is ignored at link time, so it does not affect which libraries are linked. If -r10000 has been used, -TARG:proc=r10000 is unnecessary.

In addition to specifying the target chip, you can also specify the target processor board. This gives the compiler information about hardware parameters such as cache sizes, which can be used in some optimizations. You can specify the target platform with the -TARG:platform=ipxx flag. For SN0, use -TARG:platform=ip27.

The -Ofast=ip27 flag implies the flags -r10000, -TARG:proc=r10000, and -TARG:platform=ip27.

For some applications, control of numeric error is paramount, and the programmer devotes great care to ordering arithmetic operations so that the finite precision of computer registers will not introduce and propagate errors. The IEEE 754 standard for floating-point arithmetic is conservatively designed to preserve accuracy, at the expense of speed if necessary, and conformance to it is a key element of a numerically-sensitive program—especially a program that must produce identical answers in different environments.

Many other programs and programmers are less concerned about preserving every bit of precision and more interested in getting answers that are in adequate agreement, as fast as possible. Two compiler options control these issues.

The nuances of mathematical accuracy are discussed in depth in the math(3) man page. The compiler options discussed in this section are detailed in the opt(5) man page.

do i = 1, n 
   b(i) = a(i)/c 
enddo 

tmp = 1.0/c 
do i = 1, n 
   b(i) = a(i)*tmp 
enddo 

sum = 0.0 
do i = 1, n 
   sum = sum + a(i) 
enddo 

sum1 = 0.0 
sum2 = 0.0 
do i = 1, n-1, 2 
   sum1 = sum1 + a(i) 
   sum2 = sum2 + a(i+1) 
enddo 
do j= i, n 
   sum1 = sum1 + a(j) 
enddo 
sum = sum1 + sum2 

% cc -n32 -mips4 -Ofast=ip27 -OPT:roundoff=2 ...   

Consider the loop in Example 5-3, which implements the vector operation conventionally called DAXPY.

do i = 1, n 
   y(i) = y(i) + a*x(i) 
enddo  

This adds a vector multiplied by a scalar to a second vector, overwriting the second vector. Each iteration of the loop requires the following instructions:

The superscalar architecture of the CPU can execute up to four instructions per cycle. These time-slots can be filled by any combination of the following:

In addition, most instructions are pipelined, and have associated pipeline latencies ranging from one cycle to dozens. Software pipelining is a compiler technique for optimally filling the superscalar time slots. The compiler figures out how best to schedule the instructions to fill up as many superscalar slots as possible, in order to run the loop at top speed.

In software pipelining, each loop iteration is broken up into instructions, as was done in the preceding examples for DAXPY. The iterations are then overlapped in time in an attempt to keep all the functional units busy. Of course, this is not always possible. For example, a loop that does no floating point will not use the floating-point adder or multiplier. And some units are forced to remain idle on some cycles because they have to wait for instructions with long pipeline latencies, or because only four instructions can be selected from the above menu. In addition, the compiler has to generate code to fill the pipeline on the first and second iterations, and code to wind down the operation on the last iteration, as well as special-case code to handle the event that the loop requires only 1 or 2 iterations.

The central part of the generated loop, meant to be executed many times, executes with the pipeline full and tries to keep it that way. The compiler can determine the minimum number of cycles required for this steady-state portion of the loop, and it tries to schedule the instructions so that this minimum-time performance is approached as the number of iterations in a loop increases.

In calculating the minimum number of cycles required for the loop, the compiler assumes that all data are in cache (specifically, in the primary data cache). If the data are not in cache, the loop takes longer to execute. (In this case, the compiler can generate additional instructions to prefetch data from memory into the cache before they are needed. See “Understanding Prefetching” in Chapter 6.) The remainder of this discussion of software pipelining considers only in-cache data. This may be unrealistic, but it is easier to determine if the software pipeline steady-state has achieved the peak rate that the loop is capable of.

To see how effective software pipelining is, return to the DAXPY example (Example 5-3) and consider its instruction schedule. The CPU is capable of, at most, one memory instruction and one multiply-add per cycle. Because three memory operations are done for each multiply-add, the optimal performance for this loop is one-third of the peak floating-point rate of the CPU.

In creating an instruction schedule, the compiler has to consider many hardware restrictions. The following is a sample of the restrictions that affect the DAXPY loop:

Based on these considerations, the best schedule for an iteration of the basic DAXPY loop (Example 5-3) is shown in Table 5-2:

The simple schedule for this loop achieves two floating-point operations (multiply and add, in one instruction) each seven cycles, or one-seventh of the potential peak.

This schedule can be improved only by unrolling the loop so that it calculates two vector elements per iteration, as shown in Example 5-4.

do i = 1, n-1, 2
   y(i+0) = y(i+0) + a*x(i+0)
   y(i+1) = y(i+1) + a*x(i+1)
enddo
do j= i, n
   y(j+0) = y(j+0) + a*x(j+0)
enddo 

The best schedule for the steady-state part of the unrolled loop is shown in Table 5-3

This loop achieves four floating point operations in eight cycles, or one-fourth of peak; it is closer to the nominal rate for this loop, one-third of peak, but still not perfect.

A compiler-generated software pipeline schedule for the DAXPY loop is shown in Example 5-5.

[ code to initially load registers omitted ] 
loop: 
        Cycle  0:       ld y4 
        Cycle  1:       st y0 
        Cycle  2:       st y1 
        Cycle  3:       st y2 
        Cycle  4:       st y3 
        Cycle  5:       ld x5 
        Cycle  6:       ld y5 
        Cycle  7:       ld x6 
        Cycle  8:       ld x7                   madd4 
        Cycle  9:       ld y6                   madd5 
        Cycle 10:       ld y7   y+=4            madd6 
        Cycle 11:       ld x0          bne out  madd7 
        Cycle  0:       ld y0 
        Cycle  1:       st y4 
        Cycle  2:       st y5 
        Cycle  3:       st y6 
        Cycle  4:       st y7 
        Cycle  5:       ld x1 
        Cycle  6:       ld y1 
        Cycle  7:       ld x2 
        Cycle  8:       ld x3                   madd0 
        Cycle  9:       ld y2                   madd1 
        Cycle 10:       ld y3   y+=4            madd2 
        Cycle 11:       ld x4          beq loop madd3 
out: 
[ code to store final results omitted] 

This schedule is based on unrolling the loop four times. It achieves eight floating point operations in twelve cycles, or one-third of peak, so its performance is optimal. This schedule consists of two blocks of 12 cycles. Each 12-cycle block is called a replication since the same code pattern repeats for each block. Each replication accomplishes four iterations of the loop, containing four madds and 12 memory operations, as well as a pointer increment and a branch, so each replication achieves the nominal peak calculation rate. Iterations of the loop are spread out over the replications in a pipeline so that the superscalar slots are filled up.

Figure 5-1 shows the memory operations and madds for 12 iterations of the DAXPY loop. Time, in cycles, runs horizontally across the diagram.

Figure 5-1. DAXPY Software Pipeline Schedule

Cycles 0 through 8 fill the software pipeline. This is the windup stage; it was omitted from Example 5-5 for brevity. Cycles 9 through 20 make up the first replication; cycles 21 through 32, the second replication; and so on. The compiler has unrolled the loop four times, so each replication completes four iterations. Each iteration is spread out over several cycles: 15 for the first of the four unrolled iterations, 10 for the second, and 9 for each of the third and fourth iterations. Because only one memory operation can be executed per cycle, the four iterations must be offset from one another, and it takes 18 cycles to complete all four of them. Two replications are required to contain the full 18 cycles of work for the four iterations.

A test at the end of each iteration determines if all possible groups of four iterations have been started. If not, execution drops through to the next replication or branches back to the first replication at the beginning of the loop. If all groups of four iterations have begun, execution jumps out to code that finishes the in-progress iterations. This is the wind-down code; for brevity it was omitted from Example 5-5.  

To help you determine how effective the compiler has been at software pipelining, the compiler can generate a report card for each loop. You can request that these report cards be written to a listing file, or assembler output can be generated to see them.

As an example, once again consider the DAXPY loop, as in Example 5-6.

      subroutine daxpy(n,a,x,y) 
      integer n 
      real*8 a, x(n), y(n) 
      do i = 1, n 
         y(i) = y(i) + a*x(i) 
      enddo 
      return 
      end  

The software pipelining report card is produced as part of the assembler file that is an optional output of a compilation. Use the -S compiler flag to generate an assembler file; the report card will be mixed in with the assembly code, as follows (the flag -LNO:opt=0 prevents certain cache optimizations that would obscure the current study of software pipelining):

% f77 -n32 -mips4 -O3 -OPT:IEEE_arithmetic=3 -LNO:opt=0 -S daxpy.f 

An assembly listing is voluminous and confusing. You can use the shell script swplist (shown in Example C-5), which generates the assembler listing, extracts the report cards, and inserts each into a source listing file just above the loop it pertains to. The listing file is given the same name as the file compiled, but with the extension .swp. swplist is used with the same options one uses to compile:

% swplist -n32 -mips4 -O3 -OPT:IEEE_arithmetic=3 -LNO:opt=0 -c daxpy.f

The report card generated by either of these methods resembles Example 5-7.

 #<swps> 
 #<swps> Pipelined loop line 1 steady state 
 #<swps> 
 #<swps>    50 estimated iterations before pipelining 
 #<swps>     2 unrollings before pipelining 
 #<swps>     6 cycles per 2 iterations 
 #<swps>     4 flops        ( 33% of peak) (madds count as 2) 
 #<swps>     2 flops        ( 16% of peak) (madds count as 1) 
 #<swps>     2 madds        ( 33% of peak) 
 #<swps>     6 mem refs     (100% of peak) 
 #<swps>     3 integer ops  ( 25% of peak) 
 #<swps>    11 instructions ( 45% of peak) 
 #<swps>     1 short trip threshold 
 #<swps>     5 integer registers used. 
 #<swps>     9 float registers used. 
 #<swps> 

The report card tells you how effectively the CPU's hardware resources are being used in the schedule generated for the loop. There are lines showing how many instructions of each type there are per replication and what percentage of each resource's peak utilization has been achieved.

The report card in Example 5-7 is for the loop starting at line 1 of the source file (this line number may be approximate). The loop was unrolled two times and then software pipelined. The schedule generated by the compiler requires six cycles per replication, and each replication completes two iterations because of the unrolling.

The steady-state performance of the loop is 33% of the floating-point peak. The “madds count as 2” line counts floating-point operations. This indicates how fast the CPU can run this loop on an absolute scale. The peak rate of the CPU is two floating-point operations per cycle, or twice the CPU clock rate. Because this loop reaches 33% of peak, it has an absolute rate of two-thirds the CPU clock, or 133 MFLOPS in a 200 MHz CPU.

Alternatively, the “madds count as 1” line counts floating-point instructions. Since the floating point work in most loops does not consist entirely of madd instructions, this count indicates how much of the floating point capability of the chip is being utilized in the loop given its particular mix of floating point instructions. A 100% utilization here, even if the floating point operation rate is less than 100% of peak, means that the chip is running as fast as it can in this loop.

For the R10000 CPU, which has an adder unit and a multiplier, this line does not provide much additional information beyond the “madds count as 2” line. In fact, the utilization percentage is misleading in this example, because both of the floating-point instructions in the replication are actually madds, and these use both the adder and the multiplier. Here, the instruction is counted as if it simply uses one of the units. On an R8000 CPU—for which there are two complete floating point units, each capable of add, multiply, and madd instructions—this line provides better information. You can easily see cases in which the chip's floating point units are 100% utilized even though the CPU is not sustaining two floating-point operations per unit per cycle.

Each software pipeline replication described in Example 5-7 contains six memory references, the most possible in this many cycles (shown as “100% of peak”). Thus, this loop is memory-constrained. Sometimes that's unavoidable, and no additional (non-memory) resources can make the loop run faster. But in other situations, loops can be rewritten to reduce the number of memory operations, and in these cases performance can be improved. An example of such a loop is presented later.

Example 5-7 shows that only three integer operations are used (presumably a branch and two pointer increments). The total number of instructions for the replication is 11, so there are plenty of free superscalar slots—the theoretical limit would be 24, or 4 per cycle.

The report card indicates that there is a “short trip threshold” of one. This means that, for loops with fewer than one group of two iterations, a separate, non-pipelined piece of code is used. Building up and draining the pipeline imposes some overhead, so pipelining is avoided for very short loops.

Finally, Example 5-7 reports that five integer registers and nine floating-point registers were required by the compiler to schedule the code. Availability of registers is not an issue in this case, but bigger and more complicated loops require more registers, sometimes more than the CPU provides. In these cases, the compiler must either introduce some scratch memory locations to hold intermediate results, increasing the number of load and store operations for the loop, or stretch out the loop to allow greater reuse of the existing registers. When these problems occur, splitting the loop into smaller pieces can often eliminate them.

This report card provides you with valuable information. If a loop is running well, that is validated by the information it contains. If the speed of the loop is disappointing, it provides clues as to what should be done—either via the use of additional compiler flags or by modifying the code—to improve the performance.

 #<swpf> Loop line 1 wasn't pipelined because: 
 #<swpf>       Function call in the loop body 
 #<swpf> 

The problem with a pointer is that it might point to anything, including a named variable or the value also addressed by a different pointer. The possibility of “aliasing”—the possibility that two unrelated names might refer to the identical memory—creates uncertainty that requires the compiler to make the most conservative assumptions about dependencies caused by dereferencing pointer variables.

Without assurance from the programmer, the compiler needs to be cautious and assume that any two pointers can point to the same location in memory. This caution removes many optimization opportunities, particularly for loops. When this is not the case, you can use the -OPT:alias= flag. The many possible aliasing models are detailed in the opt(5) man page.

When you are sure that different pointer variables never point to overlapping regions of memory, use the -OPT:alias=restrict to allow the compiler to generate the best-performing code. If you use this flag to compile code in which different pointers can alias the same data, incorrect code can be generated. That would not be a compiler problem; you provided the compiler with false information.

As an example, consider the C implementation of DAXPY in Example 5-8.

void 
daxpy(int n, double a, double *x, double *y) 
{ 
   int i; 
#pragma unroll(1)
   for (i=0; i<n; i++) { 
      y[i] += a * x[i]; 
   } 
} 

When Example 5-8 (including a pragma to prevent automatic unrolling) is compiled with the following command, it produces the software pipelining message as shown in Example 5-9:

% swplist -n32 -mips4 -O3 -OPT:IEEE_arithmetic=3 -LNO:opt=0 -c example5-8.c 

(The -LNO:opt=0 option is used to prevent certain cache optimizations that would obscure this study of software pipelining performance.)

 #<swps> Pipelined loop line 5 steady state 
 #<swps> 
 #<swps>   100 estimated iterations before pipelining 
 #<swps>       Not unrolled before pipelining 
 #<swps>     9 cycles per iteration 
 #<swps>     2 flops        ( 11% of peak) (madds count as 2) 
 #<swps>     1 flop         (  5% of peak) (madds count as 1) 
 #<swps>     1 madd         ( 11% of peak) 
 #<swps>     3 mem refs     ( 33% of peak) 
 #<swps>     3 integer ops  ( 16% of peak) 
 #<swps>     7 instructions ( 19% of peak) 
 #<swps>     1 short trip threshold 
 #<swps>     4 integer registers used. 
 #<swps>     3 float registers used. 
 #<swps>
 #<swps>     3 min cycles required for resources 
 #<swps>     8 cycles required for recurrence(s) 
 #<swps>     3 operations in largest recurrence 
 #<swps>     9 cycles in minimum schedule found 

Note: If the #pragma unroll(1) is deleted from the example, the compiler automatically unrolls the loop to a depth of 2 and the following output is obtained:

#<swpf> Loop line 3 wasn't pipelined -- MII (16) exceeded 8 (it is no longer profitable to pipeline this loop).

The compiler cannot determine the data dependencies between x and y, and has to assume that storing into y[i] could modify some element of x. The compiler therefore produces a schedule that is more than twice as slow as is ideal.

When the #pragma unroll(1) line is deleted from Example 5-8 and compiler option -OPT:alias=restrict is added to the swplist command, the report resembles Example 5-10.

 #<swps> Pipelined loop line 3 steady state 
 #<swps> 
 #<swps>    50 estimated iterations before pipelining 
 #<swps>     2 unrollings before pipelining 
 #<swps>     6 cycles per 2 iterations 
 #<swps>     4 flops        ( 33% of peak) (madds count as 2) 
 #<swps>     2 flops        ( 16% of peak) (madds count as 1) 
 #<swps>     2 madds        ( 33% of peak) 
 #<swps>     6 mem refs     (100% of peak) 
 #<swps>     3 integer ops  ( 25% of peak) 
 #<swps>    11 instructions ( 45% of peak) 
 #<swps>     1 short trip threshold 
 #<swps>     5 integer registers used. 
 #<swps>     9 float registers used. 

Because it knows that the x and y arrays are nonoverlapping, the compiler can generate an ideal schedule. As long as this subroutine has been specified so that this assumption is correct, the code is valid and runs significantly faster.

  for ( i=1; i< size_x1-1 ;i++) 
    for ( j=1; j< size_x2-1 ;j++) 
       for ( k=1; k< size_x3-1 ;k++) 
        { 
          out3 = weight3*(    field_in[i-1][j-1][k-1] 
                            + field_in[i+1][j-1][k-1] 
                            + field_in[i-1][j+1][k-1] 
                            + field_in[i+1][j+1][k-1] 
                            + field_in[i-1][j-1][k+1] 
                            + field_in[i+1][j-1][k+1] 
                            + field_in[i-1][j+1][k+1] 
                            + field_in[i+1][j+1][k+1] ); 
          out2 = weight2*(    field_in[i  ][j-1][k-1] 
                            + field_in[i-1][j  ][k-1] 
                            + field_in[i+1][j  ][k-1] 
                            + field_in[i  ][j+1][k-1] 
                            + field_in[i-1][j-1][k  ] 
                            + field_in[i+1][j-1][k  ] 
                            + field_in[i-1][j+1][k  ] 
                            + field_in[i+1][j+1][k  ] 
                            + field_in[i  ][j-1][k+1] 
                            + field_in[i-1][j  ][k+1] 
                            + field_in[i+1][j  ][k+1] 
                            + field_in[i  ][j+1][k+1] ); 
          out1 = weight1*(    field_in[i  ][j  ][k-1] 
                            + field_in[i  ][j  ][k+1] 
                            + field_in[i  ][j+1][k  ] 
                            + field_in[i+1][j  ][k  ] 
                            + field_in[i-1][j  ][k  ] 
                            + field_in[i  ][j-1][k  ] ); 
          out0 = weight0*     field_in[i  ][j  ][k  ]; 
          field_out[i][j][k] = out0+out1+out2+out3; 
        } 

double ***field_out; 
double ***field_in; 

% swplist -n32 -mips4 -Ofast=ip27 -OPT:IEEE_arithmetic=3:alias=restrict -c stencil.c 

 #<swps> Pipelined loop line 9 steady state 
 #<swps> 
 #<swps>   100 estimated iterations before pipelining 
 #<swps>       Not unrolled before pipelining 
 #<swps>    38 cycles per iteration 
 #<swps>    30 flops        ( 39% of peak) (madds count as 2) 
 #<swps>    27 flops        ( 35% of peak) (madds count as 1) 
 #<swps>     3 madds        (  7% of peak) 
 #<swps>    28 mem refs     (73% of peak) 
 #<swps>    11 integer ops  ( 14% of peak) 
 #<swps>    66 instructions ( 43% of peak) 
 #<swps>     2 short trip threshold 
 #<swps>    13 integer registers used. 
 #<swps>    17 float registers used. 
 #<swps> 
 #<swps>    28 min cycles required for resources. 
 #<swps>    17 float registers used. 

 #<swps> 
 #<swps> Pipelined loop line 5 steady state 
 #<swps> 
 #<swps>   100 estimated iterations before pipelining 
 #<swps>       Not unrolled before pipelining 
 #<swps>    28 cycles per iteration 
 #<swps>    30 flops        ( 53% of peak) (madds count as 2) 
 #<swps>    27 flops        ( 48% of peak) (madds count as 1) 
 #<swps>     3 madds        ( 10% of peak) 
 #<swps>    28 mem refs     (100% of peak) 
 #<swps>    11 integer ops  ( 19% of peak) 
 #<swps>    66 instructions ( 58% of peak) 
 #<swps>     2 short trip threshold 
 #<swps>    15 integer registers used. 
 #<swps>    17 float registers used. 
 #<swps> 

In some situations, code ambiguity goes beyond pointer aliasing. Consider the loop in Example 5-14.  

void idaxpy( 
int     n, 
double  a, 
double  *x, 
double  *y, 
int     *index) 
{ 
  int   i; 
  for (i=0; i<n; i++) { 
    y[index[i]] += a * x[index[i]]; 
  } 
} 

You have seen this DAXPY operation before, except here the vector elements are chosen indirectly through an index array. (The same technique could as easily be used in Fortran.) Assume that the vectors x and y do not overlap; and compile as before (again with -LNO:opt=0 only to clarify the results).

% swplist -n32 -mips4 -Ofast=ip27 -OPT:IEEE_arithmetic=3:alias=restrict -LNO:opt=0 -c idaxpy.c

The results, as shown in Example 5-15, are less than optimal.

#<swps> Pipelined loop line 7 steady state 
 #<swps>    50 estimated iterations before pipelining 
 #<swps>     2 unrollings before pipelining 
 #<swps>    10 cycles per 2 iterations 
 #<swps>     4 flops        ( 20% of peak) (madds count as 2) 
 #<swps>     2 flops        ( 10% of peak) (madds count as 1) 
 #<swps>     2 madds        ( 20% of peak) 
 #<swps>     8 mem refs     ( 80% of peak) 
 #<swps>     8 integer ops  ( 40% of peak) 
 #<swps>    18 instructions ( 45% of peak) 
 #<swps>     1 short trip threshold 
 #<swps>    10 integer registers used. 
 #<swps>     4 float registers used. 
 #<swps> 
 #<swps>     8 min cycles required for resources 
 #<swps>    10 cycles in minimum schedule found 

When run at optimal speed, this loop should be constrained by loads and stores. In that case, the memory references would be at 100% of peak. The problem is that, since the values of the index array are unknown, there could be data dependencies between loop iterations for the vector y. For example, if index[i] = 1 for all i, all iterations would update the same vector element. In general, if the values in index are not a permutation of unique integers from 0 to n-1 (1 to n, in Fortran), it could happen that a value stored on one iteration could be referenced on the next. In that case, the best pipelined code could produce a wrong answer.

If you know that the values of the array index are such that no dependencies will occur, you can inform the compiler of this via the ivdep compiler directive. For a Fortran program, the directive looks like Example 5-16.  

 cdir$ ivdep 
       do i = 1, n 
          y(ind(i)) = y(ind(i)) + a * x(ind(i)) 
       enddo 

In C, the directive is a pragma and is used as shown in Example 5-17.

#pragma ivdep 
   for (i=0; i<n; i++) { 
      y[index[i]] += a * x[index[i]]; 
   } 

With this change, the schedule is improved by 25%, as shown in Example 5-18.

 #<swps>    50 estimated iterations before pipelining 
 #<swps>     2 unrollings before pipelining 
 #<swps>     8 cycles per 2 iterations 
 #<swps>     4 flops        ( 25% of peak) (madds count as 2) 
 #<swps>     2 flops        ( 12% of peak) (madds count as 1) 
 #<swps>     2 madds        ( 25% of peak) 
 #<swps>     8 mem refs     (100% of peak) 
 #<swps>     8 integer ops  ( 50% of peak) 
 #<swps>    18 instructions ( 56% of peak) 
 #<swps>     2 short trip threshold 
 #<swps>    18 integer registers used. 
 #<swps>     6 float registers used. 

The ivdep pragma gives the compiler permission to ignore the dependencies that are possible from one iteration to the next. As long as those dependencies do not actually occur, the code produces correct answers. But if they do in fact occur, the output can be wrong. Just as when misusing the alias models, this is a case of user error.

There are a few subtleties in how the ivdep directive works. First, note that the directive applies only to inner loops. Second, it applies only to dependencies that are carried by the loop. Consider the code segment in Example 5-19.

do i= 1, n
   a(index(1,i)) = b(i)
   a(index(2,i)) = c(i)
enddo

Two types of dependencies are possible in this loop. If index(1,i) is the same as index(1,i+k), or if index(2,i) is the same as index(2,i+k), for some value of k such that i+k is in the range 1 to n, there is a loop-carried dependency. Because the code is in a loop, some element of a will be stored into twice, inappropriately. (If the loop is parallelized, you cannot predict which assignment will take effect.)

If index(1,i) is the same as index(2,i) for some value of i, there is a non-loop-carried dependency. Some element of a will be assigned from both b and c, and this would happen whether the code was in a loop or not.

In Example 5-17 there is a potential loop-carried dependency. The ivdep directive informs the compiler that the dependency is not actually present—there are no duplicate values in the index array. But if the compiler detects a potential non-loop-carried dependency (a dependency between statements in one iteration), the ivdep directive does not instruct the compiler to ignore these potential dependencies. To force even these dependencies to be overlooked, extend the behavior of the ivdep directive by using the -OPT:liberal_ivdep=ON flag. When this flag is used, an ivdep directive means to ignore all dependencies in a loop.

With either variant of ivdep, the compiler issues a warning when the directive has instructed it to break an obvious dependence.

   for (i=1; i<n; i++) { 
      a[i] = a[i-1] + 3; 
   } 

In Example 5-20 the dependence is real. Forcing the compiler to ignore it almost certainly produces incorrect code. Nevertheless, an ivdep pragma breaks the dependence, and the compiler issues a warning and then schedules the code so that the iterations are carried out independently.

One more variant of ivdep is enabled with the flag -OPT:cray_ivdep=ON. This instructs the compiler to use the semantics that Cray Research specified when it originated this directive for its vectorizing compilers. That is, only “lexically backward” loop-carried dependencies are broken. Example 5-20 is an instance of a lexically backwards dependence. Example 5-21 is not.

  for (i=0; i<=n; i++) { 
     a[i] = a[i+1] + 3; 
  } 

Here, the dependence is from the load (a[i+1]) to the store (a[i]), and the load comes lexically before the store. In this case, a Cray semantics ivdep directive would not break the dependence.  

The freedom of C looping syntax, as compared to Fortran loops, presents the compiler with some challenges. You provide extra information by specifying an alias model and the ivdep pragma, and these allow you to achieve good performance from C despite the language semantics. But a few other things can be done to improve the speed of programs written in C.

Global variables can sometimes cause performance problems, because it is difficult for the compiler to determine whether they alias other variables. If loops involving global variables do not software pipeline as efficiently as they should, you can often cure the problem by making local copies of the global variables.

Another problem arises from using dereferenced pointers in loop tests.

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

The loop in Example 5-22 will not software pipeline, because the compiler cannot tell whether the value addressed by n will change during the loop. If you know that this value is loop-invariant, you can inform the compiler by creating a temporary scalar variable to use in the loop test, as shown in Example 5-23.

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

When -OPT:alias=restrict is used, the loop in Example 5-23 should now pipeline comparably to Example 5-10.

Example 5-24 shows a different case of loop-invariant pointers leading to aliasing problems.

void sub1( 
   double  **dInputToHidden, 
   double   *HiddenDelta, 
   double   *Input, 
   double  **InputToHidden, 
   double    alpha, 
   double    eta, 
   int NumberofInputs, 
   int NumberofHidden) 
{ 
   int i, j; 
   for (i=0; i<NumberofInputs; i++) { 
      for (j=0; j<NumberofHidden; j++) { 
         dInputToHidden[i][j] = alpha * dInputToHidden[i][j]
                              + eta * HiddenDelta[j] * Input[i]; 
      InputToHidden[i][j] += dInputToHidden[i][j]; 
      } 
   } 
} 

This loop is similar to a DAXPY; after pipelining it should be memory bound with about a 50% floating-point utilization. But compiling with -OPT:alias=disjoint does not quite achieve this level of performance.

 #<swps> Pipelined loop line 10 steady state 
 #<swps>
 #<swps>   100 estimated iterations before pipelining 
 #<swps>       Not unrolled before pipelining 
 #<swps>     9 cycles per iteration 
 #<swps>     5 flops        ( 27% of peak) (madds count as 2) 
 #<swps>     4 flops        ( 22% of peak) (madds count as 1) 
 #<swps>     1 madd         ( 11% of peak) 
 #<swps>     5 mem refs     (55% of peak) 
 #<swps>     4 integer ops  ( 22% of peak) 
 #<swps>    13 instructions ( 36% of peak) 
 #<swps>     2 short trip threshold 
 #<swps>     6 integer registers used. 
 #<swps>     9 float registers used. 
 #<swps> 
 #<swps>     5 min cycles required for resources
 #<swps>     8 cycles required for recurrence(s)
 #<swps>     3 operations in largest recurrence
 #<swps>     9 cycles in minimum schedule found

The problem is the pointers indexed by i; they cause the compiler to see dependencies that aren't there. This problem can be fixed by hoisting the invariants out of the inner loop, as shown in the emphasized statements in Example 5-26.

void sub2( 
   double  **dInputToHidden, 
   double   *HiddenDelta, 
   double   *Input, 
   double  **InputToHidden, 
   double    alpha, 
   double    eta, 
   int NumberofInputs, 
   int NumberofHidden) 
{ 
   int i, j; 
   double *dInputToHiddeni, *InputToHiddeni, Inputi;
   for (i=0; i<NumberofInputs; i++) {
      dInputToHiddeni = dInputToHidden[i];
      InputToHiddeni = InputToHidden[i];
      Inputi = Input[i];
      for (j=0; j<NumberofHidden; j++) { 
         dInputToHiddeni[j] = alpha * dInputToHiddeni[j]
                            + eta * HiddenDelta[j] * Inputi; 
         InputToHiddeni[j] += dInputToHiddeni[j] ; 
      } 
   } 
} 

When the loop is written this way, the compiler can see that dInputToHidden[i], InputToHidden[i], and Input[i] will not change during execution of the inner loop, so it can schedule that loop more aggressively, resulting in 5 cycles per iteration rather than 9.

 #<swps> Pipelined loop line 16 steady state 
 #<swps>   100 estimated iterations before pipelining 
 #<swps>       Not unrolled before pipelining 
 #<swps>     5 cycles per iteration 
 #<swps>     5 flops        ( 50% of peak) (madds count as 2) 
 #<swps>     4 flops        ( 40% of peak) (madds count as 1) 
 #<swps>     1 madd         ( 20% of peak) 
 #<swps>     5 mem refs     (100% of peak) 
 #<swps>     4 integer ops  ( 40% of peak) 
 #<swps>    13 instructions ( 65% of peak) 
 #<swps>     3 short trip threshold 
 #<swps>     8 integer registers used. 
 #<swps>     9 float registers used. 

When extra information is conveyed to the compiler, it can generate faster code. One useful bit of information that the compiler can sometimes exploit is knowledge of which hardware exceptions can be ignored. An exception is an event that requires intervention by the operating system. Examples include floating-point exceptions such as divide by zero, and memory access exceptions such as segmentation fault. Any program can choose which exceptions it will pay attention to and which it will ignore. For example, floating-point underflows generate exceptions, but their effect on the numeric results is usually negligible, so they are typically ignored by flushing them to zero (via hardware). Divide by zero is generally enabled because it usually indicates a fatal error in the program.

if (x .ne. 0.0) b = 1.0/x 

tmp = 1.0/x 
if (x .ne. 0.0) b = tmp 

The compiler tries to schedule looping and branching code for the CPU so that the CPU's speculative execution will be most effective. When scheduling code, the question arises: how often will a branch be taken? The compiler has only the source code, so it can only schedule branches based on heuristics (that is, on educated guesses). An example of a heuristic is the guess that the conditional branch that closes a loop is taken much more often than not. Another is that the then-part of an if is used more often than it is skipped.

As described under “Creating a Compiler Feedback File” in Chapter 4, you can create a file containing exact counts of the use of branches during a run of a program. Then you can feed this file to the compiler when you next compile the program. The compiler uses these counts to control how it schedules code around conditional branches.

After you create a feedback file, you pass it to the compiler using the -fb filename option. You would pass the feedback file for the entire program when compiling any module of that program, or you can pass it for the compilation of only the critical modules. The feedback information is optional, and the compiler ignores it when the statement numbers in the feedback file do not match the source code as it presently exists.

One difficulty with feedback files is that they must be created from a non-optimized executable. When the executable program is compiled with optimization, the simple relationship between executable code and source statements is lost. If you compile with -fb and the compiler issues a warning about mismatched statement numbers, the cause is that the feedback file came from a trace of an optimized program.

The proper sequence to make use a feedback file is as follows:

This rather elaborate process is best reserved for the final compilation before releasing a completed program.

IPA is easy to use. Use an optimization level of -O2 or -O3 and add -IPA to both the compile and link steps when building your program. Alternatively, use -Ofast for both compile and link steps; this optimization flag enables IPA.

One key feature of IPA is inlining, the replacement of a call to a routine with the code of that routine. This feature can improve performance in several ways:

But there are some disadvantages to inlining:

Thus, inlining does not always improve program execution time. As a result, there are flags you can use to control which routines will be inlined.

Inlining is available in FORTRAN 77, Fortran 90/95, C, and C++. There are a few restrictions on inlining. The following types of routines cannot be inlined:

IPA supports two types of inlining: manual and automatic. The manual (also known as standalone) inliner is invoked with the -INLINE option group. It has been provided to support the C++ inline keyword but can also be used for C and Fortran programs using the command-line option. It inlines only the routines that you specify and they must be located in the same source file as the routine into which they are inlined. The automatic inliner is invoked whenever -IPA (or -Ofast) is used. It uses heuristics to decide which routines will be beneficial to inline, so you don't need to specify these explicitly. It can inline routines from any files that have been compiled with -IPA.

      subroutine zfftp ( z, n, w, s ) 
      real*8 z(0:2*n-1), w(2*(n-1)), s(0:2*n-1) 
      integer n 
      integer iw, i, m, j, k 
      real*8 w1r, w1i, w2r, w2i, w3r, w3i 
      iw = 1 
c     First iteration of outermost loop over k&m: n = 4*km. 
      i = 0 
      m = 1 

      k = n/4 
      if (k .gt. 1) then 
         do j = 0, k-1 
            call load4(w(iw),iw,w1r,w1i,w2r,w2i,w3r,w3i) 
            call radix4pa(z(2*(j+0*k)),z(2*(j+1*k)), 
     &                    z(2*(j+2*k)),z(2*(j+3*k)), 
     &                    s(2*(4*j+0)),s(2*(4*j+1)), 
     &                    s(2*(4*j+2)),s(2*(4*j+3)), 
     &                    w1r,w1i,w2r,w2i,w3r,w3i) 
         enddo 
         i = i + 1 
         m = m * 4 
         k = k / 4 
      endif 
c ...
      return 
      end 

      subroutine load4 ( w, iw, w1r, w1i, w2r, w2i, w3r, w3i ) 
      real*8 w(0:5), w1r, w1i, w2r, w2i, w3r, w3i 
      integer iw 
c 
      w1r = w(0) 
      w1i = w(1) 
      w2r = w(2) 
      w2i = w(3) 
      w3r = w(4) 
      w3i = w(5) 
      iw = iw + 6 
      return 
      end 
c--------------------------------------------------------------------- 
      subroutine radix4pa ( c0, c1, c2, c3, y0, y1, y2, y3, 
     &                      w1r, w1i, w2r, w2i, w3r, w3i ) 
      real*8 c0(0:1), c1(0:1), c2(0:1), c3(0:1) 
      real*8 y0(0:1), y1(0:1), y2(0:1), y3(0:1) 
      real*8 w1r, w1i, w2r, w2i, w3r, w3i 
c 
      real*8 d0r, d0i, d1r, d1i, d2r, d2i, d3r, d3i 
      real*8 t1r, t1i, t2r, t2i, t3r, t3i 
c 
      d0r = c0(0) + c2(0) 
      d0i = c0(1) + c2(1) 
      d1r = c0(0) - c2(0) 
      d1i = c0(1) - c2(1) 
      d2r = c1(0) + c3(0) 
      d2i = c1(1) + c3(1) 
      d3r = c3(1) - c1(1) 
      d3i = c1(0) - c3(0) 
      t1r = d1r + d3r 
      t1i = d1i + d3i 
      t2r = d0r - d2r 
      t2i = d0i - d2i 
      t3r = d1r - d3r 
      t3i = d1i - d3i 
      y0(0) = d0r + d2r 
      y0(1) = d0i + d2i 
      y1(0) = w1r*t1r - w1i*t1i 
      y1(1) = w1r*t1i + w1i*t1r 
      y2(0) = w2r*t2r - w2i*t2i 
      y2(1) = w2r*t2i + w2i*t2r 
      y3(0) = w3r*t3r - w3i*t3i 
      y3(1) = w3r*t3i + w3i*t3r 
      return 
      end 

% f77 -n32 -mips4 -O3 -r10000 -OPT:IEEE_arithmetic=3:roundoff=3 -INLINE:must=load4,radix4pa -flist -c fft.f 

  k = (n / 4) 
  IF(k .GT. 1) THEN 
    _ab0 = ((n / 4) + -1) 
    DO j = 0, _ab0, l 
      d0r = (z((j * 2) + 1) + z(((j +(k * 2)) * 2) + 1))
      d0i = (z((j * 2) + 2) + z(((j +(k * 2)) * 2) + 2))
      d1r = (z((j * 2) + 1) - z(((j +(k * 2)) * 2) + 1))
      d1i = (z((j * 2) + 2) - z(((j +(k * 2)) * 2) + 2))
      d2r = (z(((k + j) * 2) + 1) + z(((j +(k * 3)) * 2) + 1))
      d2i = (z(((k + j) * 2) + 2) + z(((j +(k * 3)) * 2) + 2))
      d3r = (z(((j +(k * 3)) * 2) + 2) - z(((k + j) * 2) + 2))
      d3i = (z(((k + j) * 2) + 1) - z(((j +(k * 3)) * 2) + 1))
      t1r = (d1r + d3r)
      t1i = (d1i + d3i)
      t2r = (d0r - d2r)
      t2i = (d0i - d2i)
      t3r = (d1r - d3r)
      t3i = (d1i - d3i)
      s((j * 8) + 1) = (d0r + d2r)
      s((j * 8) + 2) = (d0i + d2i)
      s((j * 8) + 3) = ((w((j * 6) + 1) * t1r) -(w((j * 6) + 2) * t1i))
      s((j * 8) + 4) = ((w((j * 6) + 2) * t1r) +(w((j * 6) + 1) * t1i))
      s((j * 8) + 5) = ((w((j * 6) + 3) * t2r) -(w((j * 6) + 4) * t2i))
      s((j * 8) + 6) = ((w((j * 6) + 3) * t2i) +(w((j * 6) + 4) * t2r))
      s((j * 8) + 7) = ((w((j * 6) + 5) * t3r) -(w((j * 6) + 6) * t3i))
      s((j * 8) + 8) = ((w((j * 6) + 5) * t3i) +(w((j * 6) + 6) * t3r))
    END DO 
  ENDIF 
  RETURN 

Using Automatic Inlining

Automatic inlining is a feature of IPA. The compiler performs inlining on must subroutine calls, but no longer considers inlining to be beneficial when it increases the size of the program by 100% or more, or if the extra code causes the Olimit option to be exceeded. This option specifies the maximum size, in basic blocks, of a routine that the compiler will optimize. Generally, you do not need to worry about this limit because, if it is exceeded, the compiler will print a warning message instructing you to recompile using the flag -OPT:Olimit=nn.

If one of these limits is exceeded, IPA will restrict the inlining rather than not do any at all. It decides which routines will remain inlined on the basis of their location in the call hierarchy. Routines at the lowest depth in the call graph are inlined first, followed by routines higher up in the hierarchy. This is illustrated in Figure 5-2.

Figure 5-2. Inlining and the Call Hierarchy

The call tree for a small program is shown on the left. At the lowest depth, leaf routines (those that do not call any other routine) are inlined. In Figure 5-2, the routine E is inlined into routines D and C. At the next level, D is inlined into B and C is inlined into A. At the last level, which for this program is the top level, B is inlined into A. IPA stops automatic inlining at the level that causes the program size to double, or the level that exceeds the Olimit option.

You can increase or decrease the amount of automatic inlining with these three options:

-IPA:space=n	The largest acceptable percentage increase in code size. The default is 100 (100%).
-IPA:forcedepth=n	All routines at depth n or less in the call graph must be inlined, regardless of the space limit.
-IPA:inline=off	Turns off automatic inlining altogether.

Automatic inlining inlines the calls to load4 and radix4pa in Example 5-30. But because most of IPA's actions are not performed until the link stage, you don't get a .w2f file with which to verify this until the link has been completed.

The -INLINE:must and -INLINE:never flags work in conjunction with automatic inlining. To block automatic inlining of specific routines, name them in an -INLINE:never list. To require inlining of specific routines regardless of code size or their position in the call graph, name them in an -INLINE:must list.  

The -IPA option, whether given explicitly on compile and link lines or implicitly via -Ofast, is designed to work fairly automatically. Nevertheless, you can do a few things to enhance interprocedural analysis.

IPA needs to know which routines are being called in order to do its analysis, so it is limited by programming constructs that obscure the call graph. The use of function pointers, virtual functions, and C++ exception handling are all examples of things that limit interprocedural analysis.

The optimizations that IPA performs other than inlining should always benefit performance. Although inlining can often significantly improve performance, it can also hurt it, so it pays to experiment with the flags available for controlling automatic inlining.