New const function detection code and infinite loops.

[Jan Hubicka]

On Mon, 23 Aug 1999, Mark Mitchell wrote:

> 
>   Well and for example following function:
> 
>   int funct(int b)
>   {
>     while(b&1) b+=2;
>     return b;
>   }
>   main()
>   { 
>     funct(1);
>   }
>   despite the fact, that function is complette nonsence, it still contains
>   infinite loop (for certain input values), but will be marked as const by
>   the detection code.
> 
> If I follow, you're saying that some part of the compiler works like
> this:
>  
>   1. A `const' function is one that doesn't read or write any global
>      memory.  This is automatically detected, and `funct' is marked
>      as `const'.
>   2. Therefore, a `const' function has no side-effects.
>   3. Therefore, if the value of a `const' function is not used, the
>      call to the `const' function can be omitted.
Thats exactly what I do have in mind.
> 
> The GCC documentation for the `const' attribute says:
> 
>   Many functions do not examine any values except their arguments,
>   and have no effects except the return value.
> 
> As you note, running forever *is* an effect.  Therefore, `funct' is
> not `const'.  Therefore, the const-detection code should not detect
> this case.  It could be conservative by not including any function
> with a loop (including a goto), or a function call.  (Because a
Thats what my finitary detection code does. Except that it allows calls
to other const functions (that are guaranteed to be finitary)
> function call could indicate recursion.  I guess you could technically
> ignore function calls; if that's the way by which you get infinite
> looping then you'll get a stack overflow, which is undefined behavior,
> which means that you can do anything you want.  But, I think it would
> be better to treat function calls like potential loops.)
Recursive calls to function itself are detected as calls to nonconst
function, so it behaves exactly like you suggest.
> 
> Some other attribute (I think this is the `pure' attribute) *does*
> apply to such functions.  It says that this function may have loop
> forever, but is guaranteed to return the same value whenever it is
> called with the same arguments, and does not affect global memory.
My current implementation is to handle "pure" functions as const functions
with one extra input parametter (memory). So function will get removed
too.  Thats way I am documenting it in the patch and I think this is clean
interpretation as long as it is documented in this way.
We probably don;t have to worry much about optimizing calls to infinite
functions. Needless to say that I don't see clean way how to avoid CSE
to removing such functions.

In future I would like to implement some data structure collecting
information about function. I think it can contain bitmask of set
registers, so some registers that are not set in called functions may
be kept alive across function call to reduce non caller save register
pressure.
It also can contain flag "modify memory" that can be detected even for
(possibly) infinite functions and CSE can consult it and flush tables only
whenpresent.

So call will look like as normal call (not CONST_CALL) so it will not be
CSeed and loop optimized, but CSE will be still improved.
(later we possibly might prepare exact list of modified/read memory
addreses when easily determinable to improve CSE even more)

But I still don't know how to associate such datastructure with function
call. May I rely on the fact that function call insn numbers don't cahnge?
(so calls.c may do the trick in separate array?)
> So, you can turn `funct (1) + funct (1)' into `2 * funct(1)', or even
> `funct (1)', if you're not using the value.
> 
> (BTW, technically, your program has undefined behavior because `b'
> will overflow.  If you made `b' an unsigned int, the behavior would be
> defined.)
OK. It was meant just as demonstration. Sorry for the bug :)

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