You may wish to select certain procedures to be inlined or not to be inlined by using the inlining options.

---

Note: You can use the inline keyword and pragmas in C++ or C to specifically identify routines to call sites to inline. The inliner's heuristics decides whether to inline any cases not covered by the -INLINE options.

---

In all cases, once a call is selected for inlining, a number of tests are applied to verify its suitability. These tests may prevent its inlining regardless of user specification: for instance, if the callee is a C varargs routine, or parameter types do not match.

This option performs IPA alias analysis. That is, it determines which global variables and formal parameters are referenced or modified by each call, and which global variables are passed to reference formal parameters. This analysis is used for other IPA analyses, including constant propagation and address-taken analysis. This option is ON by default.

This option performs IPA address-taken analysis. That is, it determines which global variables and formal parameters have their addresses taken in ways that may produce aliases. This analysis is used for other IPA analyses, especially constant propagation. Its effectiveness is very limited without -IPA:alias=ON . This option is ON by default.

The order of loops in a nest can affect the number of cache misses, the number of instructions in the inner loop, and the ability to schedule an inner loop. Consider the following loop nest example.

do i   
  do j    
    do k      
      a(j,k) = a(j,k) + b(i,k)

As written, the loop suffers from several possible performance problems. First, each iteration of the k loop requires two loads and one store. Second, if the loop bounds are sufficiently large, every memory reference will result in a cache miss.

Interchanging the loops improves performance.

do k
   do j
     do i
       a(j,k) = a(j,k) + b(i,k)

Since a(j,k) is loop invariant, only one load is needed in every iteration. Also, b(i,k) is “stride-1,” successive loads of b(i,k) come from successive memory locations. Since each cache miss brings in a contiguous cache line of data, typically 4-16 elements, stride-1 references incur a cache miss every 4-16 iterations. In contrast, the references in the original loop are not in stride-1 order. Each iteration of the inner loop causes two cache misses; one for a(j,k) and one for b(i,k).

In a real loop, different factors may affect different loop ordering. For example, choosing i for the inner loop may improve cache behavior while choosing j may eliminate a recurrence. LNO uses a performance model that considers these factors. It then orders the loops to minimize the overall execution time estimate.

Cache blocking and outer loop unrolling are two closely related optimizations used to improve cache reuse, register reuse, and minimize recurrences. Consider matrix multiplication in the following example.

do i=1,10000
   do j=1,10000
    do k=1,10000
      c(i,j) = c(i,j) + a(i,k)*b(k,j)

Given the original loop ordering, each iteration of the inner loop requires two loads. The compiler uses loop unrolling, that is, register blocking, to minimize the number of loads.

do i=1,10000
   do j=1,10000,2
    do k=1,10000
      c(i,j) = c(i,j) + a(i,k)*b(k,j)
      c(i,j+1) = c(i,j+1) + a(i,k)*b(k,j+1)

Storing the value of a(i,k) in a register avoids the second load of a(i,k). Now the inner loop only requires three loads for two iterations. Unrolling the j loop even further, or unrolling the i loop as well, further decrease the amount of loads required. How much is the ideal amount to unroll? Unrolling more decreases the amount of loads but not the amount of floating point operations. At some point, the execution time of each iteration is limited by the floating point operations. There is no point in unrolling further. LNO uses its performance model to choose a set of unrolling factors that minimizes the overall execution time estimate.

Given the original matrix multiply loop, each iteration of the i loop reuses the entire b matrix. However, with sufficiently large loop limits, the matrix b will not remain in the cache across iterations of the i loop. Thus in each iteration, you have to bring the entire matrix into the cache. You can “cache block” the loop to improve cache behavior.

do tilej=1,10000,Bj
   do tilek=1,10000,Bk
    do i=1,10000
     do j=tilej,MIN(tilej+Bj-1,10000)
       do k=tilek,MIN(tilek+Bk-1,10000)
         c(i,j) = c(i,j) + a(i,k)*b(k,j)

By appropriately choosing Bi and Bk, b remains in the cache across iterations of i, and the total number of cache misses is greatly reduced.

LNO automatically caches tile loops with block sizes appropriate for the target machine. When compiling for an SGI R8000, LNO uses a single level of blocking. When compiling for an SGI systems (such as R4000, R5000, R10000, or R12000) that contain multi-level caches, LNO uses multiple levels of blocking where appropriate.

LNO attempts to fuse multiple loop nests to improve cache behavior, to lower the number of memory references, and to enable other optimizations. Consider the following example.

do i=1,n
   do j=1,n
     a(i,j) = b(i,j) + b(i,j-1) + b(i,j+1)

do i=1,n
   do j=1,n
     b(i,j) = a(i,j) + a(i,j-1) + a(i,j+1)

In each loop, you need to do one store and one load in every iteration (the remaining loads are eliminated by the software pipeliner). If n is sufficiently large, in each loop you need to bring the entire a and b matrices into the cache.

LNO fuses the two nests and creates the following single nest:

do i=1,n
   a(i,1) = b(i,0) + b(i,1) + b(i,2)
   do j=2,n
     a(i,j) = b(i,j) + b(i,j-1) + b(i,j+1)
     b(i,j-1) = a(i,j-2) + a(i,j-1) + a(i,j)
   end do
   b(i,n) = a(i,n-1) + a(i,n) + a(i,n+1)
end do

Fusing the loops eliminates half of the cache misses and half of the memory references. Fusion can also enable other optimizations. Consider the following example:

do i
    do j1
      S1
    end do
    do j2
      S2
    end do
  end do

By fusing the two inner loops, other transformations are enabled such as loop interchange and cache blocking.

do j
    do i
      S1
      S2
    end do
end do

As an enabling transformation, LNO always tries to use loop fusion (or fission, discussed in the following subsection) to create larger perfectly nested loops. In other cases, LNO decides whether or not to fuse two loops by using a heuristic based on loop sizes and the number of variables common to both loops.

To fuse aggressively, use -LNO:fusion=2.

The opposite of fusing loops is distributing loops into multiple pieces, or loop fission. As with fusion, fission is useful as an enabling transformation. Consider this example again:

do i
    do j1
      S1   
    end do
    do j2
      S2
    end do
end do

Using loop fission, as shown in the following example, also enables loop interchange and blocking.

do i1
    do j1
      S1
    end do
end do
do i2
    do j2
      S2
    end do
end do

Loop fission is also useful to reduce register pressure in large inner loops. LNO uses a model to estimate whether or not an inner loop is suffering from register pressure. If it decides that register pressure is a problem, fission is attempted. LNO uses a heuristic to decide on how to divide the statements among the resultant loops.

Loop fission can potentially lead to the introduction of temporary arrays. Consider the following loop.

do i=1,n
    s = ..
    .. = s
end do

If you want to split the loop so that the two statements are in different loops, you need to scalar expand s.

do i=1,n
    tmp_s(i) = ..
end do
do i=1,n
    .. = tmp_s(i)
end do

Space for tmp_s is allocated on the stack to minimize allocation time. If n is very large, scalar expansion can lead to increased memory usage, so the compiler blocks scalar expanded loops. Consider the following example:

do se_tile=1,n,b
     do i=se_tile,MIN(se_tile+b-1,n)
      tmp_s(i) = ..
    end do
     do i=se_tile,MIN(se_tile+b-1,n)
      .. = tmp_s(i)
    end do
end do

Related to loop fission is vectorization of intrinsics. The SGI math libraries support vector versions of many intrinsic functions that are faster than the regular versions. That is, it is faster, per element, to compute n cosines than to compute a single cosine. LNO attempts to split vectorizable intrinsics into their own loops. If successful, each such loop is collapsed into a single call to the corresponding vector intrinsic.

The MIPS IV instruction set supports a data prefetch instruction that initiates a fetch of the specified data item into the cache. By prefetching a likely cache miss sufficiently ahead of the actual reference, you can increase the tolerance for cache misses. In programs limited by memory latency, prefetching can change the bottleneck from hardware latency time to the hardware bandwidth. By default, prefetching is enabled at -O3 for the R10000.

LNO runs a pass that estimates which references will be cache misses and inserts prefetches for those misses. Based on the miss latency, the code generator later schedules the prefetches ahead of their corresponding references.

By default, for misses in the primary cache, the code generator moves loads early in the schedule ahead of their use, exploiting the out-of-order execution feature of the R10000 to hide the latency of the primary miss. For misses in the secondary cache, explicit prefetch instructions are generated.

Prefetching is limited to array references in well behaved loops. As loop bounds are frequently unknown at compile time, it is usually not possible to know for certain whether a reference will miss. The algorithm therefore uses heuristics to guess.

Prefetching can improve performance in compute-intensive operations where data is too large to fit in the cache. Conversely, prefetching will not help performance in a memory-bound loop where data fits in the cache.

Software pipelining attempts to improve performance by executing statements from multiple iterations of a loop in parallel. This is difficult when loops contain conditional statements. Consider the following example:

do i = 1,n
   if (t(i) .gt. 0.0) then
     a(i) = 2.0*b(i-1)
   end do
end do

Ignoring the if statement, software pipelining may move up the load of b(i-1), effectively executing it in parallel with earlier iterations of the multiply. Given the conditional, this is not strictly possible. The code generator will often if convert such loops, essentially executing the body of the if on every iteration. The if conversion does not work well when the if is frequently not taken. An alternative is to gather-scatter the loop, so the loop is divided as follows:

inc = 0 do i = 1,n
   tmp(inc) = i
   if (t(i) .gt. 0.0) then
     inc = inc + 1
   end do
end do
do i = 1,inc
   a(tmp(i)) = 2.0*b((tmp(i)-1)
end do

The code generator will if convert the first loop; however, no need exists to if convert the second one. The second loop can be effectively software pipelined without having to execute unnecessary multiplies.

The following pragmas/directives control fission and fusion.

The following pragmas/directives control blocking and permutation transformations.

For example:

            subroutine amat(x,y,z,n,m,mm)
            real*8 x(100,100), y(100,100), z(100,100)
            do k = 1, n
          C*$* BLOCKING SIZE 20
               do j = 1, m
          C*$* BLOCKING SIZE 20
                 do i = 1, mm
                   z(i,k) = z(i,k) + x(i,j)*y(j,k)
                 enddo
               enddo
             enddo
             end

In this example, the compiler makes 20x20 blocks when blocking. However, the compiler can block the loop nest such that loop k is not included in the tile. If it did not, add the following pragma just before the k loop.

          C*$* BLOCKING SIZE (0) 

This pragma suggests that the compiler generates a nest like:

            subroutine amat(x,y,z,n,m,mm)
             real*8 x(100,100), y(100,100), z(100,100)
             do jj = 1, m, 20
               do ii = 1, mm, 20
                 do k = 1, n
                   do j = jj, MIN(m, jj+19)
                     do i = ii, MIN(mm, ii+19)
                       z(i,k) = z(i,k) + x(i,j)*y(j,k)
                     enddo 
                  enddo
                 enddo
               enddo
             enddo
             end

Finally, you can apply a INTERCHANGE pragma to the same nest as a BLOCKING SIZE pragma. The BLOCKING SIZE applies to the loop it directly precedes only, and moves with that loop when an interchange is applied.

For example, the following code:

            C*$* UNROLL (2)
               DO i = 1, 10
                DO j = 1, 10
                 a(i,j) = a(i,j) + b(i,j)
                END DO
               END DO

becomes:

              DO i = 1, 10, 2
                DO j = 1, 10
                 a(i,j) = a(i,j) + b(i,j)
                 a(i+1,j) = a(i+1,j) + b(i+1,j)
                END DO
               END DO

and not:

              DO i = 1, 10, 2
                DO j = 1, 10
                 a(i,j) = a(i,j) + b(i,j)
                END DO
             DO j = 1, 10
                 a(i+1,j) = a(i+1,j) + b(i+1,j)
                END DO
               END DO

The UNROLL pragma again is attached to the given loop, so that if an INTERCHANGE is performed, the corresponding loop is still unrolled. That is, the example above is equivalent to:

            C*$* INTERCHANGE i,j
               DO j = 1, 10
            C*$* UNROLL 2
                DO i = 1, 10
                 a(i,j) = a(i,j) + b(i,j)
                END DO
               END DO

The following pragmas/directives control prefetch operations.

The effect of this pragma is:

The following pragmas and/or directives control fill and/or alignment of symbols. This section uses the term pragma when describing either a pragma or a directive.

The align_symbol pragma aligns the start of the named symbol at the specified alignment. The fill_symbol pragma pads the named symbol.

int x;  /* x is a global or a common block variable */
#pragma align_symbol (x, 32) 

/* x will start at a 32-byte boundary */

#pragma align_symbol (x, 2)
/* Error: cannot request alignment lower than the natural
   * alignment of the symbol.
   */

double y; /* y is a global, common, or local */
#pragma fill_symbol (y, L2cacheline)
/* allocate extra storage both before and after “y” so
 * that “y” is within an L2cacheline (128 bytes) all by
 * itself. Can be useful to avoid false-sharing between 
 * multipleprocessors for cacheline containing “y”.
 */ 

The following pragmas/directives control dependence analysis.

        CDIR$ IVDEP
          do i = 1,n
             b(k) = b(k) + a(i)
          enddo

       CDIR$ IVDEP
          do i=1,n
             a(i) = a(i-1) + 3.0
          enddo

       CDIR$ IVDEP
          do i=1,n
             a(b(i)) = a(b(i)) + 3.0
          enddo

        CDIR$ IVDEP
          do i = 1,n
             a(i) = b(i)
             c(i) = a(i) + 3.0
          enddo

        CDIR$ IVDEP
          do i=1,n
             a(i) = a(i-1) + 3.0
          enddo

        CDIR$ IVDEP
          do i=1,n
             a(i) = a(i+1) + 3.0
          enddo

Other options exist that allow finer control of floating point behavior than is provided by -OPT:roundoff. The options may be used to obtain finer control, but they may disappear or change in future compiler releases.

The preceding options can change the results of floating point calculations, causing less accuracy (especially -OPT:IEEE_arithmetic), different results due to expression rearrangement (-OPT:roundoff ), or NaN/Inf results in new cases. Note that in some such cases, the new results may not be worse (that is, less accurate) than the old, they just may be different. For instance, doing a sum reduction by adding the terms in a different order is likely to produce a different result. Typically, that result is not less accurate, unless the original order was carefully chosen to minimize roundoff.

If you encounter such effects when using these options (including -O3, which enables -OPT:roundoff=2 by default), first attempt to identify the cause by forcing the safe levels of the options: -OPT:IEEE_arithmetic=1:roundoff=0. When you do this, do not have the following options explicitly enabled:

If using the safe levels works, you can either use the safe levels or, if you are dealing with performance-critical code, you can use the more specific options (for example, div_split, fast_complex , and so forth) to selectively disable optimizations. Then you can identify the source code that is sensitive and eliminate the problem. Or, you can avoid the problematic optimizations.

Consider the Fortran statement, a(i) = b(i). At -O0, the value of i is kept in memory and is loaded before each use. This statement uses two loads of i. The code generator local optimizer replaces the second load of i with a copy of the first load, and then it uses copy-propagation and dead code removal to eliminate the copy. Comparing .s files for the -O0 and -O1 versions shows:

The .s file for -O0:

lw $3,20($sp)                   #  load address of i
lw $3,0($3)                     #  load i
addiu $3,$3,-1                  #  i - 1
sll $3,$3,3                     #  8 * (i-1)
lw $4,12($sp)                   #  load base address for b
addu $3,$3,$4                   #  address for b(i)
ldc1 $f0,0($3)                  #  load b
lw $1,20($sp)                   #  load address of i
lw $1,0($1)                     #  load i
addiu $1,$1,-1                  #  i - 1
sll $1,$1,3                     #  8 * (i-1)
lw $2,4($sp)                    #  load base address for a
addu $1,$1,$2                   #  address for a(i)
sdc1 $f0,0($1)                  #  store a

The .s file for -O1:

lw $1,0($6)                     #  load i
lw $4,12($sp)                   #  load base address for b
addiu $3,$1,-1                  #  i - 1
sll $3,$3,3                     #  8 * (i-1)
lw $2,4($sp)                    #  load base address for a
addu $3,$3,$4                   #  address for b(i)
addiu $1,$1,-1                  #  i - 1
ldc1 $f0,0($3)                  #  load b
sll $1,$1,3                     #  8 * (i-1)
addu $1,$1,$2                   #  address for a(i)
sdc1 $f0,0($1)                  #  store a

The .s file for -O2 (using OPT to perform scalar optimization) produces optimized code:

lw $1,0($6)                     # load i
sll $1,$1,3                     # 8 * i
addu $2,$1,$5                   # address of b(i+1)
ldc1 $f0,-8($2)                 # load b(i)
addu $1,$1,$4                   # address of a(i+1)
sdc1 $f0,-8($1)                 # store a(i)

The if conversion transformation converts control-flow into conditional assignments. For example, consider the following code before if conversion. Note that expr1 and expr2 are arbitrary expressions without calls or possible side effects. For example, if expr1 is i++, the following example would be wrong because ` i' would not be updated.

if ( cond )
      a = expr1;
else
      a = expr2;

After if conversion, the code looks like this:

tmp1 = expr1;
tmp2 = expr2;
a = (cond) ? tmp1 : tmp2;

Performing if conversion results in the following benefits:

In the preceding code that was if converted, the expressions, expr1 and expr2, are unconditionally evaluated. This can conceivably result in the generation of exceptions that do not occur without if conversion. An operation that is conditionalized in the source, but is unconditionally executed in the object, is called a speculated operation. Even if the -TENV:X level prohibits speculating an operation, it may be possible to if convert. For information about the -TENV option, see the appropriate compiler man page.

For example, suppose expr1 = x + y; is a floating point add, and X=1. Speculating FLOPs is not allowed (to avoid false overflow exceptions). Define x_safe and y_safe by x_safe = (cond)? x : 1.0; y_safe = (cond) ? y : 1.0;. Then unconditionally evaluating tmp1 = x_safe + y_safe; cannot generate any spurious exception. Similarly, if X < 4, and expr1 contains a load (for example, expr1 = *p), it is illegal to speculate the dereference of p. But, defining p_safe = (cond) ? p : known_safe_address; and then tmp1 = *p_safe; cannot generate a spurious memory exception.

Notice that with -TENV:X=2, it is legal to speculate FLOPs, but not legal to speculate memory references. So expr1 = *p + y; can be speculated to tmp1 = *p_safe + y;. If *known_safe_address is uninitialized, there can be spurious floating point exceptions associated with this code. In particular, on some MIPS platforms (for example, R10000) if the input to a FLOP is a denormalized number, then a trap will occur. Therefore, by default, the code generator initializes *known_safe_address to 1.0.

Four main types of cross-iteration optimizations include:

In this example, unrolling 4 times converts this code:

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

to this code:

for ( i = 0; i < (n % 4); i++ ) { 
   a[i] = b[i]; 
} 
for ( j = 0; j < (n / 4); j++ ) { 
   a[i+0] = b[i+0]; 
   a[i+1] = b[i+1]; 
   a[i+2] = b[i+2]; 
   a[i+3] = b[i+3]; 
   i += 4; 
}

Loop unrolling:

Recurrence breaking offers multiple benefits. Before the recurrences are broken (see both of the following examples), the compiler waits for the prior iteration's add to complete (four cycles on the R8000) before starting the next one, so four cycles per iteration occur.

When the compiler interleaves the reduction, each add must still wait for the prior iteration's add to complete, but four of these are done at one time, then partial sums are combined on exiting the loop. The four iterations are done in four cycles, or one cycle per iteration, quadruple the speed.

With back substitution, each iteration depends on the result from two iterations back (not the prior iteration), so four cycles per two iterations occur, or two cycles per iteration (double the speed).

---

Note: The compiler actually interleaves and back-substitutes these examples even more than shown below, for even greater benefit (3 cycles/4 iterations for the R8000 in both cases). These examples are simple for purposes of exposition.

---

Two types of recurrence breaking are reduction interleaving and back substitution:

Software pipelining schedules innermost loops to keep the hardware pipeline full. For information about software pipelining, see the MIPSpro 64-Bit Porting and Transition Guide. Also, for a general discussion of instruction level parallelism, refer to B.R.Rau and J.A.Fisher, “Instruction Level Parallelism,” Kluwer Academic Publishers, 1993 (reprinted from the Journal of Supercomputing, Volume 7, Number 1/2).

The global code motion phase performs various code motion transformations in order to reduce the overall execution time of a program. The global code motion phase is useful because it does the following:

The benefits of global code motion include the following:

The steps performed by the code generator at -O2 and -O3 include:

At several points in this process local optimizations are performed, since many of the transformations performed can expose additional opportunities. It is also important to note that many transformations require legality checks that depend on alias information. There are three sources of alias information:

At the -O3 level of optimization, with -r10000, LNO generates prefetches for memory references that are likely to miss either the L1 (primary) or the L2 (secondary) cache. The code generator generates prefetch operations for L2 prefetches, and implements L1 prefetches as follows: makes sure that loads that had associated L1 prefetches are issued at least 8 cycles before their results are used.

It is often possible to reduce prefetch overhead by eliminating some of the corresponding prefetches from different replications. For example, suppose a prefetch is only required on every fourth iteration of a loop, because four consecutive iterations will load from the same cache line. If the loop is replicated four times by software pipelining, then there is no need for a prefetch in each replication, so three of the four corresponding prefetches are pruned away.

The original software pipelining schedule has room for a prefetch in each replication, and the number of cycles for this schedule is what is described in the software pipelining notes as “cycles per iteration.” The number of memory references listed in the software pipelining notes (“mem refs”) is the number of memory references including prefetches in Replication 0. If some of the prefetches have been pruned away from replication 0, the notes will overstate the number of cycles per iteration while understating the number of memory references per iteration.

Some choices that the code generator makes are decided based on information about the frequency with which different basic blocks are executed. By default, the code generator makes guesses about these frequencies based on the program structure. This information is available in the .s file. The frequency printed for each block is the predicted number of times that block will be executed each time the PU is entered.

The frequency guesses are replaced with the measured frequencies. Currently the information guides if-conversion, some loop unrolling decisions (unrelated to the trip count estimate), global code motion, control flow optimizations, global spill and restore placement, global register allocation, instruction alignment, and delay slot filling. Average loop trip-counts can be derived from feedback information. Trip count estimates are used to guide decisions about how much to unroll and whether or not to software pipeline.

In your programs, use tables rather than if-then-else or switch statements. For example, consider this code:

typedef enum { BLUE, GREEN, RED, NCOLORS } COLOR;

Instead of:

switch ( c ) {
     case CASE0: x = 5; break;
     case CASE1: x = 10; break;
     case CASE2: x = 1; break;
}

Use:

static int Mapping[NCOLORS] = { 5, 10, 1 };
...
x = Mapping[c];

As an optimizing technique, the compiler puts the first eight parameters of a parameter list into registers where they may remain during execution of the called routine. Therefore, always declare, as the first eight parameters, those variables that are most frequently manipulated in the called routine.

Use 32-bit or 64-bit scalar variables instead of smaller ones. This practice can take more data space. However, it produces more efficient code because the MIPS instruction set is optimized for 32-bit and 64-bit data.

The following suggestions apply to C and C++ programs:

The following suggestions apply to C++ programs: