Re: [patch 1/2] PR27313 Discover non-trapping memory accesses

[Michael Matz <matz at suse dot de>]

Hi,

On Fri, 13 Apr 2007, Richard Henderson wrote:

> I worry about not remembering which memories *never* can trap (e.g. 
> accesses based on static variables) and those that are only 
> conditionally non-trapping, such as the ones you're detecting here.
> 
> A code motion pass may legitimately move a true non-trapping memory 
> access anywhere in the program.  A conditionally non- trapping memory 
> cannot be moved outside of the subgraph dominated by the trapping memory 
> that it is shadowed by.

I initially thought about this problem (an artifact of TREE_THIS_NONTRAP 
being a global flag, but used here in a control dependend fashion), and 
then managed to forget about it during the implementation :-/

The plan in any case was, to only note stores as shadowing other 
accesses.  We can't reorder a load and a store, so even if we mark the 
load as non-trapping it can't happen that it is reordered before the store 
which caused it to be not trapping.  By that reasoning we can also make 
loads (even non-trapping) shadow stores.  I'm not sure if we ever are 
allowed to reorder stores, generally we are not.  So stores also 
can shadow stores.

That leaves the problem of loads directly shadowing loads, which can't be 
done, if we ever reorder loads itself.  I think the patch got away with 
that, because we currently don't do that.

<Thinking while writing>
I also have a hard time to imagine a usefull transformation where a load 
is moved in front of a dominating load, but that dominating load itself is 
not moved.  To reorder loads from the same address we must prove something 
which is equivalent to proving that both loads load the same value:

  x_1 = *p;
  [... everything imaginable ...]
  x_2 = *p;

If x_1 and x_2 have not provably the same value we can't move the x_2 insn
in front of x_1.  But if we can prove that we also have proved that the 
second load is redundant, so again nothing should be reordered.  So if the 
patch as proposed ever generates incorrect code it must be because an 
invalid load reordering occured, or because a transformation determining 
the validity of the reordering did reorder instead of removing the 
redundant load.
</thinking>

Hmm, so I think I've convinced myself now why the patch as proposed is 
relatively safe.  I think it's valid to assume that "stupid" 
transformations as above might exist, in which case the patch as is would 
be unsafe, which I could care for by being more conservative in what is 
allowed to shadow what.  Do you want me to do this (it would complicate 
the pass as possibly two accesses must be tracked, the first store and the 
first load).

> > +  if (TREE_THIS_NOTRAP (node))
> > +    pp_string (buffer, "nt~");

> Some of the other extra info we dump is in [] at the end of
> the line, e.g. "[tail call]".  I'd prefer something like that
> with "[notrap]" than this rather cryptic annotation.

Good suggestion, thanks.


Ciao,
Michael.