Proposal for inter-procedural loops fusion.

[Ajit Kumar Agarwal <ajit dot kumar dot agarwal at xilinx dot com>]

Hello All:

I am proposing the inter-procedural Loop fusion. Generally the Loops adjacent to each other and the conformable
Candidates of loop fusions are done with respect to intra-procedural loops. The whole program analysis needs to
Be done with array sections analysis across the procedure calls to fuse the loops across the procedure calls. 

In the example given in Fig(1) the doubly nested loops in routine sub1 will be a candidates of fusing the doubly
Nested loops in routine sub2 in Fig(2). The main calls routine sub1 and sub2 and the loops in routine sub1 and sub2
Can be fused. The array section analysis and dependence analysis is done on the regions across the procedure calls
For loops in sub1 and sub2. 

Here is the proposal for loop fusion across the procedure calls. Normally loop peeling is done to make the candidate
For Loop fusion and the sub2 function the loops can also be peeled. 

In the examples given below the array A and array B are global variables in order to happen the loops fusion across
the procedure calls.

The below examples are extracted from the articles on the following.

"Inter-procedure loop fusion, array compaction and rotation" by John Ng et.al

Examples:

program main
common /s/ A(N),B(N) 
call sub1() 
call sub2()
Âend 
Subroutine sub1() common /s/ A(N),B(N)Â
do j=1,N 
 do i=1,NÂ
  ÂA(i+1, j) = j -i 
  enddoÂ
enddo
do i=1,NÂ
A(1,i) = i * 2
enddo
Âdo i=1,N
A(i+1,n+1) = A(i+1,1)
Âenddo
end /* sub1 */

Fig (1)

ÂSubroutine sub2() common /s/ A(N),B(N)
Âdo j=1,N
  do i=1,N
   ÂB(i,j) = A(i+1,j+1) +A(i,j+1) + A(i,j) +A(i+1,j)Â
  Âenddo
enddo
ÂendÂ

Fig (2).

Thoughts Please?

Thanks & Regards
Ajit