[rtlopt] runtime iterations unrolling fix

[rtlopt] runtime iterations unrolling fix

[Jan Hubicka]

Zdenek,
the test to disable exit conditional in peeled copy of loop body is
reversed compared to the comment.  I guess the comment is what 
you've intended so I've changed it.  Still I am not able to come with
testcase when we need exit test in all copies.  Can you enlighten me?
(the testcase I was fixing was:
int a[100000];
int q = 267;
main ()
{
  int i;
  for (i = 0; i < q; i++)
    a[i] = 0;
}

Honza

Fri Oct 25 23:32:09 CEST 2002  Jan Hubicka  <jh@suse.cz>
	* unroll.c (unroll_loop_runtime_iterations): Fix.
*** loop-unroll.c.old1	Sat Oct 26 01:44:17 2002
--- loop-unroll.c	Sat Oct 26 01:43:45 2002
*************** unroll_loop_runtime_iterations (loops, l
*** 381,387 ****
  	 number of iterations.  Also, in case of postincrement we do
  	 not know whether we should not exit before reaching the loop.  */
        sbitmap_zero (wont_exit);
!       if (desc->postincr && (i || desc->cond == NE))
  	SET_BIT (wont_exit, 1);
  
        if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
--- 381,387 ----
  	 number of iterations.  Also, in case of postincrement we do
  	 not know whether we should not exit before reaching the loop.  */
        sbitmap_zero (wont_exit);
!       if (!desc->postincr && (i || desc->cond == NE))
  	SET_BIT (wont_exit, 1);
  
        if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),

Re: [rtlopt] runtime iterations unrolling fix

[Zdenek Dvorak]

Hello,

> the test to disable exit conditional in peeled copy of loop body is
> reversed compared to the comment.  I guess the comment is what you've
> intended so I've changed it.  Still I am not able to come with
> testcase when we need exit test in all copies.  Can you enlighten me?

thinking about it, I come to belief the comment is the thing that is wrong --
suppose that we have a preincr loop, that means we are
trying to arrange things so that the exit from loop body is in the last
block of the loop; it is, we must arrange that after entering the body,
there will be -1 (mod # of unrollings) iterations left. I must have
tests for exit in every copy (in preconditioning), as we may exit
in some of these copies (in case the loops rolls less than # of
unrollings times).

So I will revert the change and fix the comment.

Did the code as it was cause some problem?

Zdenek

Re: [rtlopt] runtime iterations unrolling fix

[Jan Hubicka]

> Hello,
> 
> > the test to disable exit conditional in peeled copy of loop body is
> > reversed compared to the comment.  I guess the comment is what you've
> > intended so I've changed it.  Still I am not able to come with
> > testcase when we need exit test in all copies.  Can you enlighten me?
> 
> thinking about it, I come to belief the comment is the thing that is wrong --
> suppose that we have a preincr loop, that means we are
> trying to arrange things so that the exit from loop body is in the last
> block of the loop; it is, we must arrange that after entering the body,
> there will be -1 (mod # of unrollings) iterations left. I must have
> tests for exit in every copy (in preconditioning), as we may exit
> in some of these copies (in case the loops rolls less than # of
> unrollings times).
> 
> So I will revert the change and fix the comment.
> 
> Did the code as it was cause some problem?
I see what are you shooting for now, but it seems to be quite
unnecesarily expensive way to do so.
We have two problems - one problem is the case where loop is
paradoxical, then we need one of the original exit tests to bail out in
very first iteration.
In the other cases we know the number of iterations to be valid, but
still it can be set up in a way that the unrolled loops will iterate 0
times, if I understand it correctly, you are keeping the exit test just
for this case.
It would be better to base exit condition only on the number of
iterations that is anyway readilly available - keep the
(niter&nuroll==x) tests in the peeled copies, removing exit tests and
add one extra testst (niter >= nunroll) just preconditioning the loop.

Then we will execute in worst case npeelings+2 tests instead of
2*npeelings.

Honza
> 
> Zdenek

Re: [rtlopt] runtime iterations unrolling fix

[Zdenek Dvorak]

Hello,

> > > the test to disable exit conditional in peeled copy of loop body is
> > > reversed compared to the comment.  I guess the comment is what you've
> > > intended so I've changed it.  Still I am not able to come with
> > > testcase when we need exit test in all copies.  Can you enlighten me?
> > 
> > thinking about it, I come to belief the comment is the thing that is wrong --
> > suppose that we have a preincr loop, that means we are
> > trying to arrange things so that the exit from loop body is in the last
> > block of the loop; it is, we must arrange that after entering the body,
> > there will be -1 (mod # of unrollings) iterations left. I must have
> > tests for exit in every copy (in preconditioning), as we may exit
> > in some of these copies (in case the loops rolls less than # of
> > unrollings times).
> > 
> > So I will revert the change and fix the comment.
> > 
> > Did the code as it was cause some problem?
> I see what are you shooting for now, but it seems to be quite
> unnecesarily expensive way to do so.
> We have two problems - one problem is the case where loop is
> paradoxical, then we need one of the original exit tests to bail out in
> very first iteration.
> In the other cases we know the number of iterations to be valid, but
> still it can be set up in a way that the unrolled loops will iterate 0
> times, if I understand it correctly, you are keeping the exit test just
> for this case.
> It would be better to base exit condition only on the number of
> iterations that is anyway readilly available - keep the
> (niter&nuroll==x) tests in the peeled copies, removing exit tests and
> add one extra testst (niter >= nunroll) just preconditioning the loop.
> 
> Then we will execute in worst case npeelings+2 tests instead of
> 2*npeelings.

This will not work; there are two basic problems:
1) niter may come out negative due to overflow and then the last
comparison won't work.
2) more importantly, the exit does not neccesarily have to be at the end
of loop body (I use preincrement/postincremet test as a cheap heuristic
to where to place the loop exit, but there is no garantee). It would be
probably useful ta handle the common special case where it is
true in some way simmilar to what you suggest (handling (1) somehow).

Btw: the code in cfgloopanal.c:count_loop_iterations looks a bit strange to me:

if (stride != const1_rtx
    && (simplify_gen_binary (UMOD, GET_MODE (desc->var), exp, stride)
           != const0_rtx))
  return NULL;

how could the second part be not satisfied?

Should not we increase exp by stride rather than by 1 a few lines below?

Zdenek

Re: [rtlopt] runtime iterations unrolling fix

[Jan Hubicka]

> Hello,
> 
> > > > the test to disable exit conditional in peeled copy of loop body is
> > > > reversed compared to the comment.  I guess the comment is what you've
> > > > intended so I've changed it.  Still I am not able to come with
> > > > testcase when we need exit test in all copies.  Can you enlighten me?
> > > 
> > > thinking about it, I come to belief the comment is the thing that is wrong --
> > > suppose that we have a preincr loop, that means we are
> > > trying to arrange things so that the exit from loop body is in the last
> > > block of the loop; it is, we must arrange that after entering the body,
> > > there will be -1 (mod # of unrollings) iterations left. I must have
> > > tests for exit in every copy (in preconditioning), as we may exit
> > > in some of these copies (in case the loops rolls less than # of
> > > unrollings times).
> > > 
> > > So I will revert the change and fix the comment.
> > > 
> > > Did the code as it was cause some problem?
> > I see what are you shooting for now, but it seems to be quite
> > unnecesarily expensive way to do so.
> > We have two problems - one problem is the case where loop is
> > paradoxical, then we need one of the original exit tests to bail out in
> > very first iteration.
> > In the other cases we know the number of iterations to be valid, but
> > still it can be set up in a way that the unrolled loops will iterate 0
> > times, if I understand it correctly, you are keeping the exit test just
> > for this case.
> > It would be better to base exit condition only on the number of
> > iterations that is anyway readilly available - keep the
> > (niter&nuroll==x) tests in the peeled copies, removing exit tests and
> > add one extra testst (niter >= nunroll) just preconditioning the loop.
> > 
> > Then we will execute in worst case npeelings+2 tests instead of
> > 2*npeelings.
> 
> This will not work; there are two basic problems:
> 1) niter may come out negative due to overflow and then the last
> comparison won't work.

When niter is unsigned, it should not overflow (when properly defined)

> 2) more importantly, the exit does not neccesarily have to be at the end
> of loop body (I use preincrement/postincremet test as a cheap heuristic
> to where to place the loop exit, but there is no garantee). It would be
> probably useful ta handle the common special case where it is
> true in some way simmilar to what you suggest (handling (1) somehow).

I see, that is problem I missed.  OK, handling the special (most common)
case would be definitly usefull here. 
Please add some comments there to avoid others from the same naive
"improvements" :)
> 
> Btw: the code in cfgloopanal.c:count_loop_iterations looks a bit strange to me:
> 
> if (stride != const1_rtx
>     && (simplify_gen_binary (UMOD, GET_MODE (desc->var), exp, stride)
>            != const0_rtx))
>   return NULL;
> 
> how could the second part be not satisfied?

For loop like
for (i=1;i!=2;i+=3)
where we will exit eventually, but not after the niter count we compute.
> 
> Should not we increase exp by stride rather than by 1 a few lines below?
Yes, I guess so.
for (i=0;i<=4;i+=4)
should get misscompiled by current code.

Honza
> 
> Zdenek

Re: [rtlopt] runtime iterations unrolling fix

[Zdenek Dvorak]

Hello,

> > Should not we increase exp by stride rather than by 1 a few lines below?
> Yes, I guess so.
> for (i=0;i<=4;i+=4)
> should get misscompiled by current code.

I just found out that the code was correct as it was :-( I should not
try to fix something that works...

I will correct my mistake together with the patch to improve
preconditioning for preincr loops.

Zdenek