Re: New const function detection code and infinite loops.

[Mark Mitchell <mark at codesourcery dot com>]

  The current const detection code in the mainline sources will not
  mark f as const since it is externally visable and void type.  It
  will however mark f as const in the following example:

    static int f() {
      while (1);
      return 0;
    }

    int main () {
      f();
      abort();
    }

  I take it that this example is also guaranteed not to call abort according
  to the ANSI C standard?

That is my reading.  Essentially, calling a function does not have
special semantics; this code is essentially equivalent to:

  int main () {
    while (1);	
    0;
    abort ();
  }

There is nothing in this program which has undefined behavior.  So, I
think that we must not call abort.

  I can prepare a patch to fix the problem (Jan, let me know if you're already
  handling this).  BTW, is it easily provable that a loop will always
  terminate, or must we simply avoid marking the function as const if
  any type of loop construct is present?

It's of course in general impossible to prove that a loop will
terminate.  But, some simple and common cases are provable.  If the
loop simply increments a counter, which is not written elsewhere, and
checks that the counter is less than some value, and the counter will
not overflow before it reaches this value, then it is guaranteed to
terminate.  I'm not sure it's worth worrying about here, though.  I
would vote for just bailing whenever a loop is seen, at least for now.
The programmer can always use __attribute__ ((const)) if they really
know what they're doing.

I *can* imagine cases where doing the loop thing would be a win:

  int f(int x, int y)
  {
    while (x--)
      y *= y;
    return y;
  }

which does repeated squaring, or some such, is a `const' function, and
is guaranteed not to loop forever.  I just doubt that detecting this
case is the low-hanging fruit in terms of getting better code out of
GCC.

  I guess this raises for me a more general question of how loops (any type
  of loop) should be handled.  Loops create delays (infinite loops merely
  create infinite delays :-).  At what point is a delay considered an
  observable event that is part of the program's behavior and should not
  be changed by the compiler?  Granted an infinite loop is somewhat a
  special case.

>From a standards point of view, it's not a sliding scale.  The
standard says nothing about time (although the C++ standard library
does have a few complexity constraints on algorithms).  (That's why
bad optimizing compilers are just as correct as good optimizing
compilers.)  So the compiler can insert and remove delays as it sees
fit.  But, there's nothing in the standards that says a compiler can
remove an infinite loop, or insert one; the constraint is that
*eventually* the program must do what it supposed to do, and no more.

--
Mark Mitchell                   mark@codesourcery.com
CodeSourcery, LLC               http://www.codesourcery.com