New const function detection code and infinite loops.

[Jan Hubicka]

> 
> 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.
Yes, thats exactly what I am doing now. I will send the patch this
evening as soon as I return from the library.

This just votes for the importance of some extra warning I've already
implemented. (I suggest -Whints and document it as enabling various hints
detected by compiler to optimize the code).
It may ask for adding const/pure attributes to functions that seems to be
const/pure and have one of following properties:
1) can not be proved to be finite.
2) are used before defined.
3) are public.
4) are recursive.
And user might from time to time enable this warning and think about
using the attributes.

Also might ask for adding noreturn attribute and doing some other stuff.
(I already also have the noreturn detecting code - fairly easy and it
match even in few places in gcc, where noreturn is used).
> 
> 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.
In gcc sources there are about 1/3 of 200 detected "pure" functions
disabled (1 const function) because of possible infinite loop.
Once I get around problem of detecting recursive calls (how can I detect
from CALL_INSN that it is calling function itself) I think more of them
will arise, because there are actually quite a lot recursive predicates in
gcc.
But I think it is ratio was can happily live with.
Also I report only function that mets conditions described above, so some
static functions are not counted to this ration.

Honza