[for,suggestions] : How do we know a loop is the peeled version?

Hi,

Just found that many optimizations (prefetch, loop unrolling) are performed on the peeled loops.
This causes code size and compilation time increase without benefit.

MODULE kinds
   INTEGER, PARAMETER :: RK8 = SELECTED_REAL_KIND(15, 300)
END MODULE kinds
! --------------------------------------------------------------------
PROGRAM TEST_FPU  ! A number-crunching benchmark using matrix inversion.
USE kinds         ! Implemented by:    David Frank  Dave_Frank@hotmail.com
IMPLICIT NONE     ! Gauss  routine by: Tim Prince   N8TM@aol.com
                  ! Crout  routine by: James Van Buskirk  torsop@ix.netcom.com
                  ! Lapack routine by: Jos Bergervoet bergervo@IAEhv.nl

REAL(RK8) :: pool(101, 101,1000), a(101, 101)
INTEGER :: i

      DO i = 1,1000
         a = pool(:,:,i)         ! get next matrix to invert
      END DO

END PROGRAM TEST_FPU

For this example (-O3 -fprefetch-loop-arrays -funroll-loops), the vectorizer peels the loop.
And the prefetching and loop unrolling are performed on the peeled loops.

In the attached patch, the vectorizer marked the loop as peeled, and the prefetching
gives up. However, the RTL unroller could not get this information and still unroll the peeled
loop.

I need suggestion: How the optimizer recognizes that the loop is the peeled version (preloop or postloop)?

Thanks,

Changpeng

Hi,

> Just found that many optimizations (prefetch, loop unrolling) are performed on the peeled loops.
> This causes code size and compilation time increase without benefit.
> 
> MODULE kinds
>    INTEGER, PARAMETER :: RK8 = SELECTED_REAL_KIND(15, 300)
> END MODULE kinds
> ! --------------------------------------------------------------------
> PROGRAM TEST_FPU  ! A number-crunching benchmark using matrix inversion.
> USE kinds         ! Implemented by:    David Frank  Dave_Frank@hotmail.com
> IMPLICIT NONE     ! Gauss  routine by: Tim Prince   N8TM@aol.com
>                   ! Crout  routine by: James Van Buskirk  torsop@ix.netcom.com
>                   ! Lapack routine by: Jos Bergervoet bergervo@IAEhv.nl
> 
> REAL(RK8) :: pool(101, 101,1000), a(101, 101)
> INTEGER :: i
> 
>       DO i = 1,1000
>          a = pool(:,:,i)         ! get next matrix to invert
>       END DO
> 
> END PROGRAM TEST_FPU
> 
> For this example (-O3 -fprefetch-loop-arrays -funroll-loops), the vectorizer peels the loop.
> And the prefetching and loop unrolling are performed on the peeled loops.
> 
> In the attached patch, the vectorizer marked the loop as peeled, and the prefetching
> gives up. However, the RTL unroller could not get this information and still unroll the peeled
> loop.
> 
> I need suggestion: How the optimizer recognizes that the loop is the peeled version (preloop or postloop)?

instead of the "peeled" flag, it might be better to make sure that the latter optimizers know that
the peeled loop does not roll enough (set nb_iterations_upper_bound/nb_iterations_estimate).

Passing the information from gimple to rtl loop optimizer is a long-standing problem.  One possibility is
to keep the information about the loops up-to-date between the optimizers (few years ago, I made
sure that this is possible up to tree->rtl expansion, so making this work again should not be too hard;
handling the expansion and rtl passes might be a little more challenging, but not terribly so).
A less involved solution is to drop some notes in the instruction stream at the end of gimple loop
optimizer, and pick them up in the rtl one,

Zdenek

Hi,

An additional problem is that after a loop is completely-unrolled, the loop structure
seems not destroyed. And thus later optimization passes may still be performed 
on these non-existence loops.


Changpeng

>>instead of the "peeled" flag, it might be better to make sure that the latter optimizers know that
>>the peeled loop does not roll enough (set nb_iterations_upper_bound/nb_iterations_estimate).

The problem is that we don't know exactly how many iterations are peeled. 
For example, in vect_do_peeling_for_alignment:

niters_of_prolog_loop = vect_gen_niters_for_prolog_loop (loop_vinfo, ni_name,
							   &wide_prolog_niters);

We could not give a constant estimation of the upper-bound.

Also, any bounds you set will be erased after dce.

>>Passing the information from gimple to rtl loop optimizer is a long-standing problem.  One possibility is
>>to keep the information about the loops up-to-date between the optimizers (few years ago, I made
>>sure that this is possible up to tree->rtl expansion, so making this work again should not be too hard;
>>handling the expansion and rtl passes might be a little more challenging, but not terribly so).
>>A less involved solution is to drop some notes in the instruction stream at the end of gimple loop
>>optimizer, and pick them up in the rtl one,

Could you please give some details.

Thnaks,

Changpeng

>Zdenek

Hi,

> An additional problem is that after a loop is completely-unrolled, the loop structure
> seems not destroyed. And thus later optimization passes may still be performed 
> on these non-existence loops.

if that is so, that would be a bug; but I am fairly sure that is not the case
(verify_loop_structure catches this kind of problems, and it is being run all over
the place).  IIRC, complete loop unrolling only replaces the exit condition of the
loop by if (0), and the loop gets physically removed in the following cfg cleanup,

Zdenek

Hi,

> 
> >>instead of the "peeled" flag, it might be better to make sure that the latter optimizers know that
> >>the peeled loop does not roll enough (set nb_iterations_upper_bound/nb_iterations_estimate).
> 
> The problem is that we don't know exactly how many iterations are peeled. 
> For example, in vect_do_peeling_for_alignment:
> 
> niters_of_prolog_loop = vect_gen_niters_for_prolog_loop (loop_vinfo, ni_name,
> 							   &wide_prolog_niters);
> 
> We could not give a constant estimation of the upper-bound.

surely there is some upper bound on the number of iterations of the loop (if it
is used to ensure alignment, it cannot be more than the value of the alignment
divided by the step of the memory reference?).  For nb_iterations_estimate, you do
not even have to be sure you are correct, it just needs to be a reasonable guess.

> Also, any bounds you set will be erased after dce.

So is anything else that you attach to loop structure, at the moment, so this still
is not an argument for having "peeled" flag.

> >>Passing the information from gimple to rtl loop optimizer is a long-standing problem.  One possibility is
> >>to keep the information about the loops up-to-date between the optimizers (few years ago, I made
> >>sure that this is possible up to tree->rtl expansion, so making this work again should not be too hard;
> >>handling the expansion and rtl passes might be a little more challenging, but not terribly so).
> >>A less involved solution is to drop some notes in the instruction stream at the end of gimple loop
> >>optimizer, and pick them up in the rtl one,
> 
> Could you please give some details.

I recall having a proof-of-concept patch for this; I will try to find it,

Zdenek

Thanks!

 I am not defending "peeled" flag proposal. Instead, I used the patch to illustrate
the problem.

Anyway, I opened bug 44794 for this problem.
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44794

Have a wonderful weekend.

Changpeng