Re: Language-independent functions-as-trees representation

[Jason Merrill <jason at redhat dot com>]

On Thu, 29 Aug 2002 14:35:32 -0700, Richard Henderson <rth@redhat.com> wrote:

> Consider
>
> 	while (foo() == bar())
> 	  baz();
>
> 	LOOP_EXPR
> 	  T.1 = foo();
> 	  T.2 = bar();
> 	  EXIT_EXPR T.1 != T.2;
> 	  baz();
>
> vs
>
> 	do {
> 	  baz();
> 	} while (foo() == bar());
>
> 	LOOP_EXPR
> 	  baz();
> 	  T.1 = foo();
> 	  T.2 = bar();
> 	  EXIT_EXPR T.1 != T.2;
>
> One thing I do note here is that loop rotation cannot be done
> easily and correctly with things in this form.  I fixed a bug
> with that just this year.  See
>
> 2002-01-30  Richard Henderson  <rth@redhat.com>
>
>         PR opt/5076
>         * rtl.h (NOTE_INSN_LOOP_END_TOP_COND): New.
>         * rtl.c (note_insn_name): Update.
>         * emit-rtl.c (remove_unnecessary_notes): Kill it.
>         * stmt.c (expand_end_loop): Kill jump opt code.  Use LOOP_END_TOP_COND
>         to perform loop rotation.
>         (expand_exit_loop_top_cond): New.
>         * tree.h (expand_exit_loop_top_cond): Declare it.
>         * c-semantics.c (genrtl_while_stmt): Use it.
>         (genrtl_for_stmt): Likewise.
>
> I don't see that the problem encountered at the rtl level 
> will be any different at the tree level.  This might be evidence
> for retaining distinct WHILE and DO_WHILE nodes and dispensing
> with plain LOOP_EXPR.

I don't think so; we can set a flag on the EXIT_EXPR/GOTO_EXPR that would
work just like LOOP_END_TOP_COND does for RTL.

However, I don't see any reason why you can't just arbitrarily move the
first basic block in the loop to the bottom.  If the branch happens to come
from something like 'if (!foo) break;' rather than a loop condition, that's
fine; it would be tested just as often.  The problem in opt/5076 seems to
have to do with not knowing the full extent of the loop; this
representation doesn't have that problem.  Even if the testcase were

int
main (void)
{
  int iNbr = 1;
  int test = 0;
  while (true)    /* was test == 0 */
    {
      inc ();
      if (iNbr == 0)
        break;
      else
        {
          inc ();
          iNbr--;
        }
      test = 1;
    }
  if (count != 2)
    abort ();
  return 0;
}

We could rotate it to

  goto first;
  while (true)
    {
      inc ();
      iNbr--;
      test = 1;
    first:
      inc ();
      if (iNbr == 0)
        break;
    }

or just suppress rotation because the break condition has an 'else' clause.

As we discussed on Thursday, this would be complicated by a cleanup for a
C++ condition declaration, but as long as all the code to be moved is at
the same nesting level, I don't see any reason why it would be a problem.

Jason