Re: Loop unroll fixes

[Bernd Schmidt <bernds at redhat dot com>]

Before we close this flame war, let my try to add something constructive.

On Fri, 14 Sep 2001, David Edelsohn wrote:

> 	The following has nothing to do with unrolling.  A do-while loop
> with != condition is generated wrong.
>
> extern int m[];
> int i = c;
>
> do {
>   m[i] = 0;
> } while (++i != c);
>
> performs one, fixed iteration on PowerPC, never comparing i and c.  The
> reality is GCC cannot determine when this loop will terminate.  GCC
> applies the "bogus iteration count" rule to set the iteration count to
> one, which does not apply to this type of test.

I've complained about missing documentation for the patches, so let me try
to suggest how this patch should have been described:

  The doloop.c transformation tries to change the exit test of the loop.
  It computes (or emits code to compute) the number of iterations, preloads
  this number into a register, and changes the loop so that this register
  is used as a counter.

  (The following is slightly simplified to deal only with loops where the
  increment is 1.  It should apply equally to other kinds of loops.)

  Normally, the iteration count is equal to (final_value - initial_value) of
  the register used as the loop counter before the transformation.  However,
  it is possible that the exit condition is true immediately (e.g. in the
  case
    i = 5;
    do {} while (i < 4);
  In the case of a do-while loop, this means that the loop is executed
  exactly once, so we must make sure that we take this into account when
  computing the number of iterations.  At the end of doloop_modify_runtime
  there is code that will emit code to detect this case and set the
  iteration count to 1 at runtime if we find that we have a loop of this
  form.

  This fails for the testcase [*]

  extern int m[];
  int i = c;

  do {
    m[i] = 0;
  } while (++i != c);

  The new test we emit before the loop sets the iteration count to 1, which
  is wrong.
  [**] We do not need this kind of test for a NE type loop, since the exit
  condition can only become true if the loop is entered with
    (final_value - initial_value) == 1,
  but in that case, we don't need to explicitly set the iteration count to
  1, since the earlier code has already done that.

Now, let's discuss this.  A few notes first:
[*]  A better testcase would be something that can be compiled and run.
     The given testcase is not a complete program, and if it were, it would
     segfault.  It's also invalid since there's a signed integer overflow
     involved.
[**] This is where there's a fault in the logic.  The question that needs to
     be asked is "why doesn't the added test do the right thing", not "can
     we make it go away in this case"?  These are separate questions, and to
     fix the bug, you have to answer the first.

The missing piece to replace the part marked [**] would read something like
  It fails because it's wrong to compare the initial value to the final
  value - at the end of the first iteration, the loop counter (I) has
  already been incremented once, so the comparison we emit is not the same
  one that would happen naturally - it compares two different values.  For
  this and similar loops, we must increment the initial value once before
  doing the comparison.

When submitting a patch, it is always a good idea to give a kind of
"walkthrough".  Submitters should never assume that even a person who is
listed as the maintainer of a particular area has ever looked at the
specific piece of code that is being changed.  GCC is too big for this.
People should make sure that their explanation contains all the relevant
facts (e.g. in this case, why do we emit the extra test anyway - what
does it do?)

If that information is missing, the review will become harder, since
the reviewer will have to duplicate the analysis for h{im,er}self.  It's
easier to follow a well-written argument and to only make sure that every
logical step is correct.  It should also help the patch writer - if it's
hard to write down a logical argument, that may mean that the patch isn't
correct.

For me, this sort of thing can help reduce the time required for review
from hours to minutes (if it makes any sense - not if it contains flaws
in the reasoning, of course).  Of course, it puts additional burden on
the submitters, but it's IMO time better spent than additional testing on
a zillion of platforms - that won't detect problems like this one.


Bernd

>  Index: doloop.c
>  ===================================================================
>  RCS file: /cvs/gcc/gcc/gcc/doloop.c,v
>  retrieving revision 1.3.4.1
>  diff -u -r1.3.4.1 doloop.c
>  --- doloop.c   2001/05/12 20:32:26     1.3.4.1
>  +++ doloop.c   2001/07/16 21:09:42
>  @@ -661,7 +634,7 @@
>        not executed before the start of the loop.  We need to determine
>        if the loop will terminate after the first pass and to limit the
>        iteration count to one if necessary.  */
>  -  if (! loop->vtop)
>  +  if (! loop->vtop && comparison_code != NE)
>       {
>         rtx label;
>