The loop blocking transformation

The loop blocking transformation decomposes a do-loop statement into blocks of a constant blocking factor (the step is multiplied by this factor). The knowledge of the sign of the outer loop step is necessary to obtain an efficient blocking. This information can be computed automatically or can be specified by the user. The blocking factor must be greater than 1. When it is applied to a perfect nest of loops, the outer loop can be blocked in the body of the inner loop of the specified level.  

$\vartriangleright$ Example 65:  A loop blocking transformation applied to the loop of index i with a level of 2 and a blocking factor of 4.

  DO i = 1,m 
    DO j = 1,n 
      F(i,j,k)
    ENDDO
  ENDDO

$\longrightarrow$

  DO Ti=1,m,4
    DO j = 1,n 
      DO i = Ti,MIN(Ti+4-1,m)
        F(i,j,k)
      ENDDO
    ENDDO
  ENDDO

The loop blocking transformation is generally followed by a loop interchanging or a loop transformation.

  $\blacktriangleright$ Fits:Blocking:Check(LOOP,DIAGMESG,FACTOR,LEVEL)

 
This function checks if the loop blocking transformation can be applied.

• LOOP (input AST) is the outer do-loop
• DIAGMESG (output STRING) is a diagnostic string for the user
• FACTOR (input INT) is the blocking factor.
• LEVEL (input/output INT) the depth of the inner loop where the blocking is applied. Use 0 to block in the outer loop.
• The function returns an error code (return INT):
  • 1 if all is correct
  • 0 if OUTLOOP is not a perfect nest of do-loops of level LEVEL.
  • -1 if FACTOR is lower or equal to 0.
  • -3 if the bounds or the step of one of the inner loops depend on the outer loop index.

  $\blacktriangleright$ Fits:Blocking:Advice(LOOP,DIAGMESG,FACTOR,LEVEL)

 
This function emits a diagnostic about the interest of the loop blocking transformation

• LOOP (input AST) is the outer do-loop
• DIAGMESG (output STRING) is a diagnostic string for the user
• FACTOR (input INT) is the blocking factor.
• LEVEL (input/output INT) the depth of the inner loop where the blocking is applied. Use 0 to block in the outer loop.
• The function returns a diagnostic code (return INT) :
  • 1 if the transformation is recommended
  • 0 if the transformation may be interesting
  • -1 if the transformation in not recommended

  $\blacktriangleright$ Fits:Blocking:Safe(LOOP,DIAGMESG,FACTOR,LEVEL)

 
This function emits a diagnostic about the code produced by the loop blocking transformation

• LOOP (input AST) is the outer do-loop
• DIAGMESG (output STRING) is a diagnostic string for the user
• FACTOR (input INT) is the blocking factor.
• LEVEL (input/output INT) the depth of the inner loop where the blocking is applied. Use 0 to block in the outer loop.
• The function returns a diagnostic code (return INT):
  • 1 if the transformation is safe
  • 0 if the transformation may be safe. More information is given by the text in DIAGMESG.
  • -1 if the transformation is not safe

  $\blacktriangleright$ Fits:Blocking:Apply(DESC,FACTOR,LEVEL)

 
This function applies the loop blocking transformation.

• DESC (input LOOPDESC) is the descriptor of the outer loop.
• VERBOSE (input INT) is the comment level
• FACTOR (input INT) is the blocking factor.
• LEVEL (input/output INT) the depth of the inner loop where the blocking is applied. Use 0 to block in the outer loop.
• The function returns the new outer loop (return AST).