Re: Functions that are CSEable but not pure

[Richard Guenther <richard dot guenther at gmail dot com>]

On Wed, Oct 3, 2012 at 9:00 PM, Jason Merrill <jason@redhat.com> wrote:
> In C++ there is a common idiom called "initialize on first use".  In its
> simplest form it looks like
>
> int& lazy_i()
> {
>   static int i = init;
>   return i;
> }
>
> If the initialization is expensive or order-sensitive, this is a useful
> alternative to initialization on load
> (http://www.parashift.com/c++-faq/static-init-order-on-first-use.html).
>
> An interesting property of such functions is that they only have
> side-effects the first time they are called, so subsequent calls can be
> optimized away to just use the return value of the first call.

If the result is not needed, are we allowed to remove a call to this
function?  Basically, is the function allowed to "detect" if it was
called before?
If we can remove it, thus the function may not exploit knowledge on wheter
it was called before then we can also perform partial redundancy elimination in

 if ()
   lazy_i ();
 lazy_i ();

so I really hope we can also DCE these calls - otherwise their property would
be really weird, as CSE also involves a "DCE" piece:

 i = lazy_i ();
j = lazy_j ();

->
  i = lazy_i ();
  lazy_j ();
  j = i;

->

 i = lazy_i ();
 j = i;

But if we are allowed to DCE a lazy_i call with unused result then it really is
"pure".  Basically with this property we consider the static variable
it writes to
as local, as it cannot be inspected in any other way than by calling the
function or inspecting its return value.

So - what's wrong with using pure?  That it doesn't "feel" correct?
The I suppose
we should simply re-word its definition ;)

> Currently there is no way to express this in GCC so that the optimizers know
> that multiple calls are redundant.  Marking the function as pure causes
> calls to be CSEd as desired, but also asserts that the first call has no
> side-effects, which is not the case.
>
> My implementation of dynamic initialization of TLS variables as mandated by
> the C++11 and OpenMP standards uses this idiom implicitly, so I'd really
> like to be able to optimize away multiple calls.
>
> Right now we have the following ECF flags (among others):
>
> const = no read, no write, no side-effects, cseable
> pure = no write, no side-effects, cseable
> novops = no read, no write

note that I consider novops a red-herring.  novops is basically
'const' volatile, but we don't have  a volatile flag on calls (we
have it, but that's for the store to the result).  I'd rather get rid
of novops ...

> looping_const_or_pure = wait, actually there are side-effects
>
> Seems like the difference between novops and looping_const_or_pure is
> whether calls are subject to CSE.  Is that right?

No, novops and looping_const_or_pure tell you whether they are subject
to DCE, all const/pure functions are subject to CSE, novops functions
are not (as said above, novops is really a volatile const).

> Rather than checking these flag bundles, it seems to me that we ought to
> break them up into
>
> no reads
> no writes
> no side-effects
> cseable side-effects

no side-effects and cseable side-effects doesn't sound like a good
distinction to me - side-effects are not 'cse'-able or they would not
be side-effects.  But I suppose it all boils down to my question above,
where the PRE case is really the most interesting (can the formerly
second call "detect" it used the initialized path or the non-initialized
path?)

> So const      would be noread|nowrite|noside
>    pure       would be nowrite|noside
> const|looping would be noread|nowrite|cseside
> pure|looping  would be nowrite|cseside
>    novops     would be noread|nowrite
>
> and the behavior I want would be just cseside.
>
> Does this make sense?  Anyone more familiar with this area of the code want
> to implement it for me?  :}

I'd say it's already implemented, just poorly documented.  Use pure!

Richard.

> Jason