[C11-atomic] gimple atomic statements

Here is my first step in promoting the __atomic builtins into gimple 
statements.  I originally planned this as tree codes, but when 
prototyped it became obvious that a gimple statement was a far superior 
solution since we also need to deal with LHS and memory address issues.

Motivations are many-fold, but primarily it makes manipulating atomics 
easier and exposes more of their side effects to the optimizers.  In 
particular we can now expose both return values of the compare and swap 
when implementing compare_exchange and get more efficient code 
generation. (soon :-)   It is item number 3 on my 4.8 task list: 
http://gcc.gnu.org/wiki/Atomic/GCCMM/gcc4.8.

This first step adds a GIMPLE_ATOMIC statement class which handles all 
the __atomic built-in calls. Right after the cfg is built, all built-in 
__atomic calls are converted to gimple_atomic statements.  I considered 
doing the conversion right in the gimplifier, but elected to leave it as 
a pass for the time being.  This then  passes through all the optimizers 
to cfgexpand, where they are then converted directly into rtl.

This currently  produces the same code that the builtins do in 4.7.  I 
expect that I missed a few places in the optimizers where they aren't 
properly treated as barriers yet,  but I'll get to tracking those down 
in a bit.

I also have not implemented non-integral atomics yet, nor do I issuing 
library calls when inline expansion cannot be done.  That's next... I 
just want to get the basics checked into the branch.

I expect to be able to wrap the __sync routines into this as well, 
eliminating all the atomic and sync builtin expansion code, keeping 
everything in one easy statement class.   Then I'll add the _Atomic type 
qualifier to the parser, and have that simply translate expressions 
involving those types into gimple_atomic statements at the same time 
calls are converted.

This bootstraps on x86_64-unknown-linux-gnu, and the only testsuite 
regressions are one involving issuing library calls.  There is a 
toolchain build problem with libjava however... During libjava 
construction there ends up being files which cant be created due to 
permission problems in .svn directories ...   Pretty darn weird, but 
I'll look into it later when the atomic gimple support is complete, if 
the problem it still exists then.

Anyone see anything obviously flawed about the approach?

Andrew

On Tue, Apr 3, 2012 at 9:40 PM, Andrew MacLeod <amacleod@redhat.com> wrote:
> Here is my first step in promoting the __atomic builtins into gimple
> statements.  I originally planned this as tree codes, but when prototyped it
> became obvious that a gimple statement was a far superior solution since we
> also need to deal with LHS and memory address issues.
>
> Motivations are many-fold, but primarily it makes manipulating atomics
> easier and exposes more of their side effects to the optimizers.  In
> particular we can now expose both return values of the compare and swap when
> implementing compare_exchange and get more efficient code generation. (soon
> :-)   It is item number 3 on my 4.8 task list:
> http://gcc.gnu.org/wiki/Atomic/GCCMM/gcc4.8.
>
> This first step adds a GIMPLE_ATOMIC statement class which handles all the
> __atomic built-in calls. Right after the cfg is built, all built-in __atomic
> calls are converted to gimple_atomic statements.  I considered doing the
> conversion right in the gimplifier, but elected to leave it as a pass for
> the time being.  This then  passes through all the optimizers to cfgexpand,
> where they are then converted directly into rtl.
>
> This currently  produces the same code that the builtins do in 4.7.  I
> expect that I missed a few places in the optimizers where they aren't
> properly treated as barriers yet,  but I'll get to tracking those down in a
> bit.
>
> I also have not implemented non-integral atomics yet, nor do I issuing
> library calls when inline expansion cannot be done.  That's next... I just
> want to get the basics checked into the branch.
>
> I expect to be able to wrap the __sync routines into this as well,
> eliminating all the atomic and sync builtin expansion code, keeping
> everything in one easy statement class.   Then I'll add the _Atomic type
> qualifier to the parser, and have that simply translate expressions
> involving those types into gimple_atomic statements at the same time calls
> are converted.
>
> This bootstraps on x86_64-unknown-linux-gnu, and the only testsuite
> regressions are one involving issuing library calls.  There is a toolchain
> build problem with libjava however... During libjava construction there ends
> up being files which cant be created due to permission problems in .svn
> directories ...   Pretty darn weird, but I'll look into it later when the
> atomic gimple support is complete, if the problem it still exists then.
>
> Anyone see anything obviously flawed about the approach?

The fact that you need to touch every place that wants to look at memory
accesses shows that you are doing it wrong.  Instead my plan was to
force _all_ memory accesses to GIMPLE_ASSIGNs (yes, including those
we have now in calls).  You're making a backwards step in my eyes.

What do you think is "easier" when you use a GIMPLE_ATOMIC
(why do you need a fntype field?!  Should the type not be available
via the operand types?!)

Your tree-cfg.c parts need to be filled in.  They are the specification of
GIMPLE_ATOMIC - at the moment you allow any garbage.

Similar to how I dislike the choice of adding GIMPLE_TRANSACTION
instead of using builtin functions I dislike this.

I suppose you do not want to use builtins because for primitive types you
end up with multiple statements for something "atomic"?

So, please tell us why the current scheme does not work and how the
new scheme overcomes this (that's entirely missing in your proposal...)

Thanks,
Richard.

> Andrew
>
>

On 04/04/2012 04:45 AM, Richard Guenther wrote:
> I suppose you do not want to use builtins because for primitive types you
> end up with multiple statements for something "atomic"?

The primary motivation is that builtins cannot return two values.

Our current builtin returns one of the two values by reference, as
one would do from plain old C.  Even though we drop the reference
when we convert from gimple to rtl, this is not good enough to clean
up the variable we forced to a stack slot.

I suggested a specialized GIMPLE_ATOMIC opcode instead of doing a
totally generalized GIMPLE_ASSIGN_N, returning N values.


r~

On 04/04/2012 04:45 AM, Richard Guenther wrote:
>
> The fact that you need to touch every place that wants to look at memory
> accesses shows that you are doing it wrong.  Instead my plan was to
> force _all_ memory accesses to GIMPLE_ASSIGNs (yes, including those
> we have now in calls).  You're making a backwards step in my eyes.
I'm not sure I understand what you are saying, or at least I don't know 
what this plan you are talking about is...   Are you saying that you are 
planning to change gimple so that none of the gimple statement types 
other than GIMPLE_ASSIGN ever see an ADDR_EXPR or memory reference?     
Seems like that change, when it happens, would simply affect 
GIMPLE_ATOMIC like all the other gimple classes.  And if it was done 
before I tried to merge the branch, would fall on me to fix.  Right now, 
I'm just handling what the compiler sends my way...  A bunch of places 
need to understand a new gimple_statement kind...
> What do you think is "easier" when you use a GIMPLE_ATOMIC
> (why do you need a fntype field?!  Should the type not be available
> via the operand types?!)

This is a WIP... that fntype fields is there for simplicity..   and 
no... you can do a 1 byte atomic operation on a full word object if you 
want by using __atomic_store_1 ()... so you can't just look at the 
object. We might be able to sort that type out eventually if all the 
casts are correct, but until everything is finished, this is safer.  I'm 
actually hoping eventually to not have a bunch of casts on the params, 
they are just there to get around the builtin's type-checking system.. 
we should be able to  just take care of required promotions at expansion 
time and do type-checking during verification.

>
> Your tree-cfg.c parts need to be filled in.  They are the specification of
> GIMPLE_ATOMIC - at the moment you allow any garbage.

well of course.... this isnt suppose to be a final patch, its to get the 
core changes into a branch while I continue working on it.  There are a 
number of parts that aren't filled in or flushed out yet.   Once its all 
working and what is expected is well defined, then I'll fill in the 
verification stuff.

> Similar to how I dislike the choice of adding GIMPLE_TRANSACTION
> instead of using builtin functions I dislike this.
>
> I suppose you do not want to use builtins because for primitive types you
> end up with multiple statements for something "atomic"?
builtins are just more awkward to work with, and don't support more than 
1 result.
compare_and swap was the worst case.. it has 2 results and that does not 
map to a built in function very well. we struggled all last fall with 
how to do it efficiently, and eventually gave up. given:

   int p = 1;
   bool ret;
   ret = __atomic_compare_exchange_n (&flag2, &p, 0, 0, 
__ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST);
   return ret;

with GCC 4.7 we currently end up generating

   p = 1;
   ret_1 = __atomic_compare_exchange_4 (&flag2, &p, 0, 0, 5, 5);
   return ret_1;

Note this actually requires leaving a local (p) on the stack, and 
reduces the optimizations that can be performed on it, even though there 
isn't really a need.

By going to a gimple statement, we can expose both results properly, and 
this ends up generating

   (ret_3, cmpxchg.2_4) = atomic_compare_exchange_strong <&flag2, 1, 0, 
SEQ_CST, SEQ_CST>
   return ret_3;

and during expansion to RTL, can trivially see that cmpxchg.2_4 is not 
used, and generate the really efficient compare and swap pattern which 
only produces a boolean result.   if only cmpxchg.2_4 were used, we can 
generate the C&S pattern which only returns the result.  Only if we see 
both are actually used do we have to fall back to the much uglier 
pattern we have that produces both results.  Currently we always 
generate this pattern.

Next, we have the C11 atomic type qualifier which needs to be 
implemented.  Every reference to this variable is going to have to be 
expanded into one or more atomic operations of some sort.  Yes, I 
probably could do that by emitting built-in functions, but they are a 
bit more unwieldy, its far simpler to just create gimple_statements.

I discovered last fall that when I tried to translate one built-in 
function into another form that dealing with parameters and all the call 
bits was a pain.  Especially when the library call I need to emit had a 
different number of parameters than the built-in did.   A GIMPLE_ATOMIC 
statement makes all of this trivial.

I also hope that when done, I can also remove all the ugly built-in 
overload code that was created for __sync and continues to be used by 
__atomic.  This would clean up where we have to take func_n and turn it 
into a func_1 or func_2 or whatever.  We also had to bend over and issue 
a crap load of different casts early to squeeze all the parameters into 
the 'proper' form for the builtins. This made it more awkward to dig 
down and find the things being operated on and manipulate them. The 
type-checking code is not a thing of beauty either.   Expansion of 
GIMPLE_ATOMIC should take care of cleaning all that up.

So bottom line, a GIMPLE_ATOMIC statement is just an object that is much 
easier to work with.  It cleans up both initial creation and rtl 
generation, as well as being easier to manipulate. It also encompasses 
an entire class of operations that are becoming more integral *if* we 
can make them efficient, and I hope to actually do some optimizations on 
them eventually.  I had a discussion last fall with Linus about what we 
needed to be able to do to them in order for the kernel to use __atomic 
instead of their home-rolled solutions.  Could I do everything with 
builtins? sure... its just more awkward and this approach seems cleaner 
to me.

I wasn't excited about creating a new gimple statement, but it seemed 
the best solution to my issues. In the end, I think this works very 
cleanly.  Im certainly open to better solutions. If there is a plan to 
change gimple in some way that this doesnt work with, then it would be 
good to know what that plan is.

Andrew

On Wed, Apr 4, 2012 at 3:26 PM, Richard Henderson <rth@redhat.com> wrote:
> On 04/04/2012 04:45 AM, Richard Guenther wrote:
>> I suppose you do not want to use builtins because for primitive types you
>> end up with multiple statements for something "atomic"?
>
> The primary motivation is that builtins cannot return two values.
>
> Our current builtin returns one of the two values by reference, as
> one would do from plain old C.  Even though we drop the reference
> when we convert from gimple to rtl, this is not good enough to clean
> up the variable we forced to a stack slot.

If that is the only reason you can return two values by using a complex
or vector type (that would be only an IL implementation detail as far
as I can see).
We use that trick to get sincos () "sane" in our IL as well.

Are there other reasons to go with a new GIMPLE code?

> I suggested a specialized GIMPLE_ATOMIC opcode instead of doing a
> totally generalized GIMPLE_ASSIGN_N, returning N values.

We already support multiple SSA defs btw, there is just no operand slot for
it that is properly named or handled by the operand scanner.  Thus, a
new GIMPLE_ASSIGN sub-code class would do, too (of course nobody
expects multiple DEFs here thus it would not be a very good idea to do
that, IMHO).

Richard.

>
> r~

On 04/04/2012 09:28 AM, Andrew MacLeod wrote:
>
>
> I wasn't excited about creating a new gimple statement, but it seemed 
> the best solution to my issues. In the end, I think this works very 
> cleanly.  Im certainly open to better solutions. If there is a plan to 
> change gimple in some way that this doesnt work with, then it would be 
> good to know what that plan is.
>
btw, I did start my prototyping of this by creating atomic tree codes 
for each of the atomic buitins rather than a gimple atomic, but found 
that did not integrate very well (I forget exactly what the issue was 
now... something to do with when I was trying to translate them from 
bultins to treecodes), so I evolved to a gimple statement which gave me 
more control over things.

  If gimple is going to change somehow that will make this work better, 
I'm also fine with doing that.  i still have some of that code laying 
around.  OR I can go back and revisit it to remember exactly what the 
issue was.

Andrew

Im not sure what happened to my original reply, so I'll resend it..


On 04/04/2012 09:28 AM, Andrew MacLeod wrote:
On 04/04/2012 04:45 AM, Richard Guenther wrote:
>
> The fact that you need to touch every place that wants to look at memory
> accesses shows that you are doing it wrong.  Instead my plan was to
> force _all_ memory accesses to GIMPLE_ASSIGNs (yes, including those
> we have now in calls).  You're making a backwards step in my eyes.
I'm not sure I understand what you are saying, or at least I don't know 
what this plan you are talking about is...   Are you saying that you are 
planning to change gimple so that none of the gimple statement types 
other than GIMPLE_ASSIGN ever see an ADDR_EXPR or memory reference?     
Seems like that change, when it happens, would simply affect 
GIMPLE_ATOMIC like all the other gimple classes.  And if it was done 
before I tried to merge the branch, would fall on me to fix.  Right now, 
I'm just handling what the compiler sends my way...  A bunch of places 
need to understand a new gimple_statement kind...
> What do you think is "easier" when you use a GIMPLE_ATOMIC
> (why do you need a fntype field?!  Should the type not be available
> via the operand types?!)

This is a WIP... that fntype fields is there for simplicity..   and 
no... you can do a 1 byte atomic operation on a full word object if you 
want by using __atomic_store_1 ()... so you can't just look at the 
object. We might be able to sort that type out eventually if all the 
casts are correct, but until everything is finished, this is safer.  I'm 
actually hoping eventually to not have a bunch of casts on the params, 
they are just there to get around the builtin's type-checking system.. 
we should be able to  just take care of required promotions at expansion 
time and do type-checking during verification.

>
> Your tree-cfg.c parts need to be filled in.  They are the 
> specification of
> GIMPLE_ATOMIC - at the moment you allow any garbage.

well of course.... this isnt suppose to be a final patch, its to get the 
core changes into a branch while I continue working on it.  There are a 
number of parts that aren't filled in or flushed out yet.   Once its all 
working and what is expected is well defined, then I'll fill in the 
verification stuff.

> Similar to how I dislike the choice of adding GIMPLE_TRANSACTION
> instead of using builtin functions I dislike this.
>
> I suppose you do not want to use builtins because for primitive types you
> end up with multiple statements for something "atomic"?
builtins are just more awkward to work with, and don't support more than 
1 result.
compare_and swap was the worst case.. it has 2 results and that does not 
map to a built in function very well. we struggled all last fall with 
how to do it efficiently, and eventually gave up. given:

   int p = 1;
   bool ret;
   ret = __atomic_compare_exchange_n (&flag2, &p, 0, 0, 
__ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST);
   return ret;

with GCC 4.7 we currently end up generating

   p = 1;
   ret_1 = __atomic_compare_exchange_4 (&flag2, &p, 0, 0, 5, 5);
   return ret_1;

Note this actually requires leaving a local (p) on the stack, and 
reduces the optimizations that can be performed on it, even though there 
isn't really a need.

By going to a gimple statement, we can expose both results properly, and 
this ends up generating

   (ret_3, cmpxchg.2_4) = atomic_compare_exchange_strong <&flag2, 1, 0, 
SEQ_CST, SEQ_CST>
   return ret_3;

and during expansion to RTL, can trivially see that cmpxchg.2_4 is not 
used, and generate the really efficient compare and swap pattern which 
only produces a boolean result.   if only cmpxchg.2_4 were used, we can 
generate the C&S pattern which only returns the result.  Only if we see 
both are actually used do we have to fall back to the much uglier 
pattern we have that produces both results.  Currently we always 
generate this pattern.

Next, we have the C11 atomic type qualifier which needs to be 
implemented.  Every reference to this variable is going to have to be 
expanded into one or more atomic operations of some sort.  Yes, I 
probably could do that by emitting built-in functions, but they are a 
bit more unwieldy, its far simpler to just create gimple_statements.

I discovered last fall that when I tried to translate one built-in 
function into another form that dealing with parameters and all the call 
bits was a pain.  Especially when the library call I need to emit had a 
different number of parameters than the built-in did.   A GIMPLE_ATOMIC 
statement makes all of this trivial.

I also hope that when done, I can also remove all the ugly built-in 
overload code that was created for __sync and continues to be used by 
__atomic.  This would clean up where we have to take func_n and turn it 
into a func_1 or func_2 or whatever.  We also had to bend over and issue 
a crap load of different casts early to squeeze all the parameters into 
the 'proper' form for the builtins. This made it more awkward to dig 
down and find the things being operated on and manipulate them. The 
type-checking code is not a thing of beauty either.   Expansion of 
GIMPLE_ATOMIC should take care of cleaning all that up.

So bottom line, a GIMPLE_ATOMIC statement is just an object that is much 
easier to work with.  It cleans up both initial creation and rtl 
generation, as well as being easier to manipulate. It also encompasses 
an entire class of operations that are becoming more integral *if* we 
can make them efficient, and I hope to actually do some optimizations on 
them eventually.  I had a discussion last fall with Linus about what we 
needed to be able to do to them in order for the kernel to use __atomic 
instead of their home-rolled solutions.  Could I do everything with 
builtins? sure... its just more awkward and this approach seems cleaner 
to me.

I wasn't excited about creating a new gimple statement, but it seemed 
the best solution to my issues. In the end, I think this works very 
cleanly.  Im certainly open to better solutions. If there is a plan to 
change gimple in some way that this doesnt work with, then it would be 
good to know what that plan is.

Andrew



>

On 04/04/2012 09:46 AM, Richard Guenther wrote:
> If that is the only reason you can return two values by using a complex
> or vector type (that would be only an IL implementation detail as far
> as I can see).
> We use that trick to get sincos () "sane" in our IL as well.

That would work if the two values were of the same type, as they
are with sincos.  In the case of compare_exchange, they are not.



r~

On Wed, Apr 4, 2012 at 3:28 PM, Andrew MacLeod <amacleod@redhat.com> wrote:
> On 04/04/2012 04:45 AM, Richard Guenther wrote:
>>
>>
>> The fact that you need to touch every place that wants to look at memory
>> accesses shows that you are doing it wrong.  Instead my plan was to
>> force _all_ memory accesses to GIMPLE_ASSIGNs (yes, including those
>> we have now in calls).  You're making a backwards step in my eyes.
>
> I'm not sure I understand what you are saying, or at least I don't know what
> this plan you are talking about is...   Are you saying that you are planning
> to change gimple so that none of the gimple statement types other than
> GIMPLE_ASSIGN ever see an ADDR_EXPR or memory reference?

A memory reference, yes.  And at most one, thus no aggregate copies
anymore.

>     Seems like that
> change, when it happens, would simply affect GIMPLE_ATOMIC like all the
> other gimple classes.  And if it was done before I tried to merge the
> branch, would fall on me to fix.  Right now, I'm just handling what the
> compiler sends my way...  A bunch of places need to understand a new
> gimple_statement kind...

I'm not sure if I ever will end up finishing the above I just wanted
to mention it.

>> What do you think is "easier" when you use a GIMPLE_ATOMIC
>> (why do you need a fntype field?!  Should the type not be available
>> via the operand types?!)
>
>
> This is a WIP... that fntype fields is there for simplicity..   and no...
> you can do a 1 byte atomic operation on a full word object if you want by
> using __atomic_store_1 ()... so you can't just look at the object. We might
> be able to sort that type out eventually if all the casts are correct, but
> until everything is finished, this is safer.  I'm actually hoping eventually
> to not have a bunch of casts on the params, they are just there to get
> around the builtin's type-checking system.. we should be able to  just take
> care of required promotions at expansion time and do type-checking during
> verification.

Oh, so you rather need a size or a mode specified, not a "fntype"?

>
>
>>
>> Your tree-cfg.c parts need to be filled in.  They are the specification of
>> GIMPLE_ATOMIC - at the moment you allow any garbage.
>
>
> well of course.... this isnt suppose to be a final patch, its to get the
> core changes into a branch while I continue working on it.  There are a
> number of parts that aren't filled in or flushed out yet.   Once its all
> working and what is expected is well defined, then I'll fill in the
> verification stuff.
>
>
>> Similar to how I dislike the choice of adding GIMPLE_TRANSACTION
>> instead of using builtin functions I dislike this.
>>
>> I suppose you do not want to use builtins because for primitive types you
>> end up with multiple statements for something "atomic"?
>
> builtins are just more awkward to work with, and don't support more than 1
> result.
> compare_and swap was the worst case.. it has 2 results and that does not map
> to a built in function very well. we struggled all last fall with how to do
> it efficiently, and eventually gave up. given:
>
>  int p = 1;
>  bool ret;
>  ret = __atomic_compare_exchange_n (&flag2, &p, 0, 0, __ATOMIC_SEQ_CST,
> __ATOMIC_SEQ_CST);
>  return ret;
>
> with GCC 4.7 we currently end up generating
>
>  p = 1;
>  ret_1 = __atomic_compare_exchange_4 (&flag2, &p, 0, 0, 5, 5);
>  return ret_1;
>
> Note this actually requires leaving a local (p) on the stack, and reduces
> the optimizations that can be performed on it, even though there isn't
> really a need.

You could use a vector, complex or aggregate return.

> By going to a gimple statement, we can expose both results properly, and
> this ends up generating
>
>  (ret_3, cmpxchg.2_4) = atomic_compare_exchange_strong <&flag2, 1, 0,
> SEQ_CST, SEQ_CST>
>  return ret_3;

In the example you only ever use address operands (not memory operands)
to the GIMPLE_ATOMIC - is that true in all cases?  Is the result always
non-memory?

I suppose the GIMPLE_ATOMICs are still optimization barriers for all
memory, not just that possibly referenced by them?

> and during expansion to RTL, can trivially see that cmpxchg.2_4 is not used,
> and generate the really efficient compare and swap pattern which only
> produces a boolean result.

I suppose gimple stmt folding could transform it as well?

>   if only cmpxchg.2_4 were used, we can generate
> the C&S pattern which only returns the result.  Only if we see both are
> actually used do we have to fall back to the much uglier pattern we have
> that produces both results.  Currently we always generate this pattern.
>
> Next, we have the C11 atomic type qualifier which needs to be implemented.
>  Every reference to this variable is going to have to be expanded into one
> or more atomic operations of some sort.  Yes, I probably could do that by
> emitting built-in functions, but they are a bit more unwieldy, its far
> simpler to just create gimple_statements.

As I understand you first generate builtins anyway and then lower them?
Or are you planning on emitting those for GENERIC as well?  Remember
GENERIC is not GIMPLE, so you'd need new tree codes anyway ;)
Or do you plan to make __atomic integral part of GENERIC and thus
do this lowering during gimplification?

> I discovered last fall that when I tried to translate one built-in function
> into another form that dealing with parameters and all the call bits was a
> pain.  Especially when the library call I need to emit had a different
> number of parameters than the built-in did.   A GIMPLE_ATOMIC statement
> makes all of this trivial.

Trivial?  Surely only as trivial as providing functions that do the task for
atomics - something which you can do for re-writing atomic builtins as well ...

> I also hope that when done, I can also remove all the ugly built-in overload
> code that was created for __sync and continues to be used by __atomic.

But the builtins will stay for our users consumption and libstdc++ use, no?

> This
> would clean up where we have to take func_n and turn it into a func_1 or
> func_2 or whatever.  We also had to bend over and issue a crap load of
> different casts early to squeeze all the parameters into the 'proper' form
> for the builtins. This made it more awkward to dig down and find the things
> being operated on and manipulate them. The type-checking code is not a thing
> of beauty either.   Expansion of GIMPLE_ATOMIC should take care of cleaning
> all that up.

You have internal functions now that are "untyped", I suppose atomics would
map to those easier given they are never emitted as calls but always explicitely
expanded.

> So bottom line, a GIMPLE_ATOMIC statement is just an object that is much
> easier to work with.

Yes, I see that it is easier to work with for you.  All other statements will
see GIMPLE_ATOMICs as blockers for their work though, even if they
already deal with calls just fine - that's why I most of the time suggest
to use builtins (or internal fns) to do things (I bet you forgot to update
enough predicates ...).  Can GIMPLE_ATOMICs throw with -fnon-call-exceptions?
I suppose yes.  One thing you missed at least ;)

>  It cleans up both initial creation and rtl generation,
> as well as being easier to manipulate. It also encompasses an entire class
> of operations that are becoming more integral *if* we can make them
> efficient, and I hope to actually do some optimizations on them eventually.
>  I had a discussion last fall with Linus about what we needed to be able to
> do to them in order for the kernel to use __atomic instead of their
> home-rolled solutions.  Could I do everything with builtins? sure... its
> just more awkward and this approach seems cleaner to me.

Cleaner if you look at it in isolation - messy if you consider that not only
things working with atomics need to (not) deal with these new stmt kind.

Richard.

> I wasn't excited about creating a new gimple statement, but it seemed the
> best solution to my issues. In the end, I think this works very cleanly.  Im
> certainly open to better solutions. If there is a plan to change gimple in
> some way that this doesnt work with, then it would be good to know what that
> plan is.
>
> Andrew
>
>
>
>

On Wed, Apr 4, 2012 at 4:32 PM, Richard Henderson <rth@redhat.com> wrote:
> On 04/04/2012 09:46 AM, Richard Guenther wrote:
>> If that is the only reason you can return two values by using a complex
>> or vector type (that would be only an IL implementation detail as far
>> as I can see).
>> We use that trick to get sincos () "sane" in our IL as well.
>
> That would work if the two values were of the same type, as they
> are with sincos.  In the case of compare_exchange, they are not.

You can return an aggregate then (or adjust the IL so that they do have the
same type and only fix that up during expansion).

Richard.

>
>
> r~

On 04/04/2012 10:33 AM, Richard Guenther wrote:
> On Wed, Apr 4, 2012 at 3:28 PM, Andrew MacLeod<amacleod@redhat.com>  wrote:
> This is a WIP... that fntype fields is there for simplicity..   and no...
> you can do a 1 byte atomic operation on a full word object if you want by
>
> Oh, so you rather need a size or a mode specified, not a "fntype"?

yes, poorly named perhaps as I created things... its just a type node at 
the moment that indicates the size being operated on that I collected 
from the builtin in function.

>
> In the example you only ever use address operands (not memory operands)
> to the GIMPLE_ATOMIC - is that true in all cases?  Is the result always
> non-memory?
The atomic address can be any arbitrary memory location... I haven't 
gotten to that yet.  its commonly just an address so I'm working with 
that first as proof of concept. When it gets something else it'll trap 
and I'll know :-)

Results are always non-memory, other than the side effects of the atomic 
contents changing and having to up date the second parameter to the 
compare_exchange routine.  The generic routines for arbitary structures 
(not added in yet), actually just work with blocks of memory, but they 
are all handled by addresses and the functions themselves are typically 
void.  I was planning on folding them right into the existing 
atomic_kinds as well... I can recognize from the type that it wont map 
to a integral type.  I needed separate builtins in 4.7  for them since 
the parameter list was different.
> I suppose the GIMPLE_ATOMICs are still optimization barriers for all
> memory, not just that possibly referenced by them?

yes, depending on the memory model used.  It can force synchronization 
with other CPUs/threads which will have the appearence of changing any 
shared memory location.  Various guarantees are made about whether those 
changes are visible to this thread after an atomic operation so we can't 
reuse shared values in those cases.  Various guarantees are made about 
what changes this thread has made are visible to other CPUs/threads at 
an atomic call as well, so that precludes moving stores downward in some 
models.
>
>> and during expansion to RTL, can trivially see that cmpxchg.2_4 is not used,
>> and generate the really efficient compare and swap pattern which only
>> produces a boolean result.
> I suppose gimple stmt folding could transform it as well?
it could if I provided gimple statements for the 3 different forms of 
C&S. I was planning to just leave it this way since its the interface 
being forced by C++11 as well as C11... and then just emit the 
appropriate RTL for this one C&S type.  The RTL patterns are already 
defined for the 2 easy cases for the __sync routines. the third one was 
added for __atomic.  Its possible that the process of integrating the 
__sync routines with GIMPLE_ATOMIC will indicate its better to add those 
forms as atomic_kinds and then gimple_fold_stmt could take care of it as 
well.   Maybe that is just a good idea anyway...  I'll keep it in mind.

>
>>    if only cmpxchg.2_4 were used, we can generate
>> the C&S pattern which only returns the result.  Only if we see both are
>> actually used do we have to fall back to the much uglier pattern we have
>> that produces both results.  Currently we always generate this pattern.
>>
>> Next, we have the C11 atomic type qualifier which needs to be implemented.
>>   Every reference to this variable is going to have to be expanded into one
>> or more atomic operations of some sort.  Yes, I probably could do that by
>> emitting built-in functions, but they are a bit more unwieldy, its far
>> simpler to just create gimple_statements.
> As I understand you first generate builtins anyway and then lower them?
> Or are you planning on emitting those for GENERIC as well?  Remember
> GENERIC is not GIMPLE, so you'd need new tree codes anyway ;)
> Or do you plan to make __atomic integral part of GENERIC and thus
> do this lowering during gimplification?
I was actually thinking about doing it during gimplification... I hadnt 
gotten as far as figuring out what to do with the functions from the 
front end yet.  I dont know that code well, but I was in fact hoping 
there was a way to 'recognize' the function names easily and avoid built 
in functions completely...

The C parser is going to have to understand the set of C11 routine names 
for all these anyway.. I figured there was something in there that could 
be done.


>> I also hope that when done, I can also remove all the ugly built-in overload
>> code that was created for __sync and continues to be used by __atomic.
> But the builtins will stay for our users consumption and libstdc++ use, no?

well, the names must remain exposed and recognizable since they are 'out 
there'.  Maybe under the covers I can just leave them as normal calls 
and then during gimplification simply recognize the names and generate 
GIMPLE_ATOMIC statements directly from the CALL_EXPR.  That would be 
ideal.  That way there are no builtins any more.


>> So bottom line, a GIMPLE_ATOMIC statement is just an object that is much
>> easier to work with.
> Yes, I see that it is easier to work with for you.  All other statements will
> see GIMPLE_ATOMICs as blockers for their work though, even if they
> already deal with calls just fine - that's why I most of the time suggest
> to use builtins (or internal fns) to do things (I bet you forgot to update
> enough predicates ...).  Can GIMPLE_ATOMICs throw with -fnon-call-exceptions?
> I suppose yes.  One thing you missed at least ;)

Not that I am aware of, they are 'noexcept'.  But I'm sure I've missed 
more than a few things so far.  Im pretty early in the process :-)
>
>>   It cleans up both initial creation and rtl generation,
>> as well as being easier to manipulate. It also encompasses an entire class
>> of operations that are becoming more integral *if* we can make them
>> efficient, and I hope to actually do some optimizations on them eventually.
>>   I had a discussion last fall with Linus about what we needed to be able to
>> do to them in order for the kernel to use __atomic instead of their
>> home-rolled solutions.  Could I do everything with builtins? sure... its
>> just more awkward and this approach seems cleaner to me.
> Cleaner if you look at it in isolation - messy if you consider that not only
> things working with atomics need to (not) deal with these new stmt kind.

They can affect shared memory in some ways like a call, but don't have 
many of the other attributes of call.  They are really more like an 
assignment or other operation with arbitrary shared memory side 
effects.  I do hope to be able to teach the optimizers the 
directionality of the memory model restrictions.  ie, ACQUIRE is only a 
barrier to hoisting shared memory code...  stores can be moved downward 
past this mode. RELEASE is only a barrier to sinking code.   RELAXED is 
no barrier at all to code motion.  In fact, a relaxed store is barely 
different than a real store... but there is a slight difference so we 
can't make it a normal store :-P.

By teaching the other parts of the compiler about a GIMPLE_ ATOMIC, we 
could hopefully lessen their impact eventually.

Andrew

On Wed, Apr 4, 2012 at 5:50 PM, Andrew MacLeod <amacleod@redhat.com> wrote:
> On 04/04/2012 10:33 AM, Richard Guenther wrote:
>>
>> On Wed, Apr 4, 2012 at 3:28 PM, Andrew MacLeod<amacleod@redhat.com>
>>  wrote:
>> This is a WIP... that fntype fields is there for simplicity..   and no...
>> you can do a 1 byte atomic operation on a full word object if you want by
>>
>> Oh, so you rather need a size or a mode specified, not a "fntype"?
>
>
> yes, poorly named perhaps as I created things... its just a type node at the
> moment that indicates the size being operated on that I collected from the
> builtin in function.

Ok.  Remember that you should use non-tree things if you can in GIMPLE
land.  This probably means that both the size and the memmodel "operands"
should be

+ struct GTY(()) gimple_statement_atomic
+ {
+   /* [ WORD 1-8 ]  */
+   struct gimple_statement_with_memory_ops_base membase;
+
+   /* [ WORD 9 ] */
+   enum gimple_atomic_kind kind;
+
     enum gimple_atomic_memmodel memmodel;

     unsigned size;

and not be trees in the ops array.  Even more, both kind and memmodel
should probably go in membase.base.subcode

>> In the example you only ever use address operands (not memory operands)
>> to the GIMPLE_ATOMIC - is that true in all cases?  Is the result always
>> non-memory?
>
> The atomic address can be any arbitrary memory location... I haven't gotten
> to that yet.  its commonly just an address so I'm working with that first as
> proof of concept. When it gets something else it'll trap and I'll know :-)

Ok.  Please try to avoid memory operands and stick to address operands ;)
You can make tree-ssa-operands.c not consider ADDR_EXPRs in the
address operands, similar to the ADDR_EXPRs in MEM_REF operand zero.

> Results are always non-memory, other than the side effects of the atomic
> contents changing and having to up date the second parameter to the
> compare_exchange routine.  The generic routines for arbitary structures (not
> added in yet), actually just work with blocks of memory, but they are all
> handled by addresses and the functions themselves are typically void.  I was
> planning on folding them right into the existing atomic_kinds as well... I
> can recognize from the type that it wont map to a integral type.  I needed
> separate builtins in 4.7  for them since the parameter list was different.
>
>> I suppose the GIMPLE_ATOMICs are still optimization barriers for all
>> memory, not just that possibly referenced by them?
>
>
> yes, depending on the memory model used.  It can force synchronization with
> other CPUs/threads which will have the appearence of changing any shared
> memory location.  Various guarantees are made about whether those changes
> are visible to this thread after an atomic operation so we can't reuse
> shared values in those cases.  Various guarantees are made about what
> changes this thread has made are visible to other CPUs/threads at an atomic
> call as well, so that precludes moving stores downward in some models.
>
>>
>>> and during expansion to RTL, can trivially see that cmpxchg.2_4 is not
>>> used,
>>> and generate the really efficient compare and swap pattern which only
>>> produces a boolean result.
>>
>> I suppose gimple stmt folding could transform it as well?
>
> it could if I provided gimple statements for the 3 different forms of C&S. I
> was planning to just leave it this way since its the interface being forced
> by C++11 as well as C11... and then just emit the appropriate RTL for this
> one C&S type.  The RTL patterns are already defined for the 2 easy cases for
> the __sync routines. the third one was added for __atomic.  Its possible
> that the process of integrating the __sync routines with GIMPLE_ATOMIC will
> indicate its better to add those forms as atomic_kinds and then
> gimple_fold_stmt could take care of it as well.   Maybe that is just a good
> idea anyway...  I'll keep it in mind.
>
>
>>
>>>   if only cmpxchg.2_4 were used, we can generate
>>> the C&S pattern which only returns the result.  Only if we see both are
>>> actually used do we have to fall back to the much uglier pattern we have
>>> that produces both results.  Currently we always generate this pattern.
>>>
>>> Next, we have the C11 atomic type qualifier which needs to be
>>> implemented.
>>>  Every reference to this variable is going to have to be expanded into
>>> one
>>> or more atomic operations of some sort.  Yes, I probably could do that by
>>> emitting built-in functions, but they are a bit more unwieldy, its far
>>> simpler to just create gimple_statements.
>>
>> As I understand you first generate builtins anyway and then lower them?
>> Or are you planning on emitting those for GENERIC as well?  Remember
>> GENERIC is not GIMPLE, so you'd need new tree codes anyway ;)
>> Or do you plan to make __atomic integral part of GENERIC and thus
>> do this lowering during gimplification?
>
> I was actually thinking about doing it during gimplification... I hadnt
> gotten as far as figuring out what to do with the functions from the front
> end yet.  I dont know that code well, but I was in fact hoping there was a
> way to 'recognize' the function names easily and avoid built in functions
> completely...

Heh ... you'd still need a GENERIC representation then.  Possibly
a ATOMIC_OP tree may do.

> The C parser is going to have to understand the set of C11 routine names for
> all these anyway.. I figured there was something in there that could be
> done.
>
>
>
>>> I also hope that when done, I can also remove all the ugly built-in
>>> overload
>>> code that was created for __sync and continues to be used by __atomic.
>>
>> But the builtins will stay for our users consumption and libstdc++ use,
>> no?
>
>
> well, the names must remain exposed and recognizable since they are 'out
> there'.  Maybe under the covers I can just leave them as normal calls and
> then during gimplification simply recognize the names and generate
> GIMPLE_ATOMIC statements directly from the CALL_EXPR.  That would be ideal.
>  That way there are no builtins any more.

I suppose my question was whether the frontends need to do sth about the
__atomic keyword or if that is simply translated to some type flag - or
is that keyword applying to operations, not to objects or types?

>
>
>>> So bottom line, a GIMPLE_ATOMIC statement is just an object that is much
>>> easier to work with.
>>
>> Yes, I see that it is easier to work with for you.  All other statements
>> will
>> see GIMPLE_ATOMICs as blockers for their work though, even if they
>> already deal with calls just fine - that's why I most of the time suggest
>> to use builtins (or internal fns) to do things (I bet you forgot to update
>> enough predicates ...).  Can GIMPLE_ATOMICs throw with
>> -fnon-call-exceptions?
>> I suppose yes.  One thing you missed at least ;)
>
>
> Not that I am aware of, they are 'noexcept'.  But I'm sure I've missed more
> than a few things so far.  Im pretty early in the process :-)

What about compare-exchange on a pointer dereference? The pointer
dereference surely can trap, so it can throw with -fnon-call-exceptions.  No?

>>
>>>  It cleans up both initial creation and rtl generation,
>>> as well as being easier to manipulate. It also encompasses an entire
>>> class
>>> of operations that are becoming more integral *if* we can make them
>>> efficient, and I hope to actually do some optimizations on them
>>> eventually.
>>>  I had a discussion last fall with Linus about what we needed to be able
>>> to
>>> do to them in order for the kernel to use __atomic instead of their
>>> home-rolled solutions.  Could I do everything with builtins? sure... its
>>> just more awkward and this approach seems cleaner to me.
>>
>> Cleaner if you look at it in isolation - messy if you consider that not
>> only
>> things working with atomics need to (not) deal with these new stmt kind.
>
>
> They can affect shared memory in some ways like a call, but don't have many
> of the other attributes of call.  They are really more like an assignment or
> other operation with arbitrary shared memory side effects.  I do hope to be
> able to teach the optimizers the directionality of the memory model
> restrictions.  ie, ACQUIRE is only a barrier to hoisting shared memory
> code...  stores can be moved downward past this mode. RELEASE is only a
> barrier to sinking code.   RELAXED is no barrier at all to code motion.  In
> fact, a relaxed store is barely different than a real store... but there is
> a slight difference so we can't make it a normal store :-P.
>
> By teaching the other parts of the compiler about a GIMPLE_ ATOMIC, we could
> hopefully lessen their impact eventually.

Ok.  I suppose having a GIMPLE_ATOMIC is fine then.

+ /* In tree-atomic.c.  */
+ extern bool expand_gimple_atomic_load (gimple);

err, gimple-atomic.c please ;)

+ /* Return the expression field of atomic operation GS.  */
+
+ static inline tree
+ gimple_atomic_expr (const_gimple gs)
+ {
+   GIMPLE_CHECK (gs, GIMPLE_ATOMIC);
+   gcc_assert (gimple_atomic_has_expr (gs));
+   return gimple_op (gs, 2);
+ }

err - what's "expression" in this context?  I hope it's not an arbitrary
tcc_expression tree?!

+ static inline bool
+ gimple_atomic_has_fail_order (const_gimple gs)
+ {
+   return gimple_atomic_kind (gs) == GIMPLE_ATOMIC_COMPARE_EXCHANGE;
+ }

btw, these kind of predicates look superfluous to me - if they are true
exactly for one atomic kind then users should use the predicate to
test for that specific atomic kind, not for some random field presence.

+ /* Return the arithmetic operation tree code for atomic operation GS.  */
+
+ static inline enum tree_code
+ gimple_atomic_op_code (const_gimple gs)
+ {
+   GIMPLE_CHECK (gs, GIMPLE_ATOMIC);
+   gcc_assert (gimple_atomic_kind (gs) == GIMPLE_ATOMIC_FETCH_OP ||
+             gimple_atomic_kind (gs) == GIMPLE_ATOMIC_OP_FETCH);
+   return (enum tree_code) gs->gsbase.subcode;
+ }

now, what was it with this "expression" thing again?  Btw, ||s go to the
next line.  subcode should be the atomic kind - it seems that you glob
too much into GIMPLE_ATOMIC and that you maybe should sub-class
GIMPLE_ATOMIC properly via the subcode field.  You'd have an
gimple_atomic_base which fences could use for example.

All asserts in inline functions should be gcc_checking_asserts.

+ gimple
+ gimple_build_atomic_load (tree type, tree target, tree order)
+ {
+   gimple s = gimple_build_with_ops (GIMPLE_ATOMIC, ERROR_MARK, 3);
+   gimple_atomic_set_kind (s, GIMPLE_ATOMIC_LOAD);
+   gimple_atomic_set_order (s, order);
+   gimple_atomic_set_target (s, target);
+   gimple_atomic_set_type (s, type);
+   gimple_set_has_volatile_ops (s, true);

you should have a gimple_build_atomic_raw function that takes all
operands and the atomic kind, avoiding the need for all the repeated
calls of gimple_atomic_set_* as well as avoid all the repeated checking
this causes.

+   else if (is_gimple_atomic (stmt))
+     {
+       tree t;
+       if (visit_store)
+         {
+         for (i = 0; i < gimple_atomic_num_lhs (stmt); i++)
+           {
+             t = gimple_atomic_lhs (stmt, i);
+             if (t)
+               {
+                 t = get_base_loadstore (t);
+                 if (t)
+                   ret |= visit_store (stmt, t, data);
+               }

I thought results are always registers?  The walk_stmt_load_store_addr_ops
looks wrong to me.  As the loads/stores are implicit (you only have addresses)
you have to adjust all callers of walk_stmt_load_store_addr_ops to handle
atomics specially as they expect to come along all loads/stores that way.
Those also handle calls and asms (for "memory" clobber) specially.


+     case GIMPLE_ATOMIC:
+       /* Atomic operations are memory barriers in both directions for now.  */
+       add_virtual_operand (stmt, opf_def | opf_use);

It's surely not relevant that "in both directions for now" but instead that
"Atomic operations have side-effects on memory."

+       for (n = 0; n < gimple_atomic_num_lhs (stmt); n++)
+       get_expr_operands (stmt, gimple_atomic_lhs_ptr (stmt, n), opf_def);
+       for (n = 0; n < gimple_atomic_num_rhs (stmt); n++)
+       get_expr_operands (stmt, gimple_op_ptr (stmt, n), opf_use);
+       break;

Do address-takens in operands make the addresses escape?  If not
you should pass opf_non_addressable as well.

Index: tree-ssa-alias.c
===================================================================
*** tree-ssa-alias.c    (revision 186098)
--- tree-ssa-alias.c    (working copy)
*************** ref_maybe_used_by_stmt_p (gimple stmt, t
*** 1440,1445 ****
--- 1440,1447 ----
      }
    else if (is_gimple_call (stmt))
      return ref_maybe_used_by_call_p (stmt, ref);
+   else if (is_gimple_atomic (stmt))
+     return true;

please add a comment before these atomic handlings that we assume
they are using/clobbering all refs because they are considered memory
optimization barriers.  Btw, does this apply to non-address-taken automatic
references?  I suppose not.  Consider:

int foo()
{
  struct s;
  atomic_fence();
  s.a = 1;
  atomic_fence();
  return s.a;
}

we still should be able to optimize this to return 1, no?  At least SRA will
happily do similar things in a non-flow-sensitive way.  Please add a FIXME
to the alias predicates at least, or even better fix this missed optimization.
There is no need to establish "backwards missed-optimization compatibility"
just like we do for asms.

*************** stmt_kills_ref_p_1 (gimple stmt, ao_ref
*** 1814,1819 ****
--- 1818,1825 ----
        }
      }

+   if (is_gimple_atomic (stmt))
+     return true;

that's for sure wrong ;)  It should return false.

Index: tree-ssa-sink.c
===================================================================
*** tree-ssa-sink.c     (revision 186098)
--- tree-ssa-sink.c     (working copy)
*************** is_hidden_global_store (gimple stmt)
*** 145,150 ****
--- 145,154 ----
      {
        tree lhs;

+       /* Don't optimize across an atomic operation.  */
+       if (is_gimple_atomic (stmt))
+         return true;
+

that's bogus, too (really all uses of is_hidden_global_store should go away).
Please look into the few callers of this function and  handle atomics in
a correct way explicitely.

+         else if (is_gimple_atomic (stmt))
+           {
+             unsigned n;
+
+             /* We may be able to lessen this with more relaxed memory
+                models, but for now, its a full barrier.  */
+             mark_all_reaching_defs_necessary (stmt);
+
+             for (n = 0; n < gimple_atomic_num_rhs (stmt); n++)
+               {
+                 tree t = gimple_op (stmt, n);
+                 if (TREE_CODE (t) != SSA_NAME &&
+                     TREE_CODE (t) != INTEGER_CST &&
+                     !is_gimple_min_invariant (t) &&
+                     !ref_may_be_aliased (t))
+                   mark_aliased_reaching_defs_necessary (stmt, t);
+               }
+           }

for sure atomics do not make non-aliased automatic variable stores necessary.
At least I hope so.  As there are only addresses in the atomic ops the
code looks wrong to me (and &&s go to the next line ...).  As you are
marking everything needed anway you can just remove the bogus loop
completely.

+     case GIMPLE_ATOMIC:
+       /* Treat this like a call for now, it may expand into a call.  */
+       if (gimple_atomic_kind (stmt) != GIMPLE_ATOMIC_FENCE)
+       cost = gimple_num_ops (stmt) *
+              estimate_move_cost (TREE_TYPE (gimple_atomic_target (stmt)));
+       else
+         cost = 1;
+       break;

for sure this counts way too many "ops".  There is at most a single
memory operand as far as I understand.  A size/speed cost of 1 for
a FENCE is also too low.

I miss handling of GIMPLE_ATOMICs in tree-ssa-structalias.c.

Richard.

> Andrew
>

On 04/05/2012 05:14 AM, Richard Guenther wrote:
>
> Ok.  I suppose having a GIMPLE_ATOMIC is fine then.
>
Thanks for all the feedback, I haven't really had to play in gimple land 
much lately. Some of those routines I guessed at what to do in order to 
get through initial compilation and your comments help clear those up 
too :-)

I will address everything next week since I doubt I will get to them 
before the long weekend arrives here.

Andrew

Richard Guenther <richard.guenther@gmail.com> writes:
>> They can affect shared memory in some ways like a call, but don't have many
>> of the other attributes of call.  They are really more like an assignment or
>> other operation with arbitrary shared memory side effects.  I do hope to be
>> able to teach the optimizers the directionality of the memory model
>> restrictions.  ie, ACQUIRE is only a barrier to hoisting shared memory
>> code...  stores can be moved downward past this mode. RELEASE is only a
>> barrier to sinking code.   RELAXED is no barrier at all to code motion.  In
>> fact, a relaxed store is barely different than a real store... but there is
>> a slight difference so we can't make it a normal store :-P.
>>
>> By teaching the other parts of the compiler about a GIMPLE_ ATOMIC, we could
>> hopefully lessen their impact eventually.
>
> Ok.  I suppose having a GIMPLE_ATOMIC is fine then.

Just for my own education really, but: does this mean that there'd
be unnecessary pessimisation in representing the thing as a call?
The interleaved load/store internal fns are really assignments too,
so if calls aren't right for that kind of operation, maybe we need
to replace the internal fns with something else.  Or at least come
up with some new call properties.

Which is a roundabout way of wondering what the main difficulties
would be in attaching things like directionality to a call.

Not arguing for anything here, just an onlooker wanting to understand. :-)

(BTW, it sounds like restricting memory accesses to GIMPLE_ASSIGN
might cause trouble for the interleave load/store stuff too.)

Richard

On Fri, Apr 6, 2012 at 10:13 AM, Richard Sandiford
<rdsandiford@googlemail.com> wrote:
> Richard Guenther <richard.guenther@gmail.com> writes:
>>> They can affect shared memory in some ways like a call, but don't have many
>>> of the other attributes of call.  They are really more like an assignment or
>>> other operation with arbitrary shared memory side effects.  I do hope to be
>>> able to teach the optimizers the directionality of the memory model
>>> restrictions.  ie, ACQUIRE is only a barrier to hoisting shared memory
>>> code...  stores can be moved downward past this mode. RELEASE is only a
>>> barrier to sinking code.   RELAXED is no barrier at all to code motion.  In
>>> fact, a relaxed store is barely different than a real store... but there is
>>> a slight difference so we can't make it a normal store :-P.
>>>
>>> By teaching the other parts of the compiler about a GIMPLE_ ATOMIC, we could
>>> hopefully lessen their impact eventually.
>>
>> Ok.  I suppose having a GIMPLE_ATOMIC is fine then.
>
> Just for my own education really, but: does this mean that there'd
> be unnecessary pessimisation in representing the thing as a call?

No, there are not.  They are more pessimized than GIMPLE_ASSIGNs
(unless you handle them specially in a few places).  But the same is
true for GIMPLE_ATOMIC.  The question is one of convenience as
far as I understand.  In general I would like to avoid new GIMPLE codes,
especially "random" ones.  You can do everything with builtins or
internal functions just fine.

> The interleaved load/store internal fns are really assignments too,
> so if calls aren't right for that kind of operation, maybe we need
> to replace the internal fns with something else.  Or at least come
> up with some new call properties.

What missed optimizations do you see?

> Which is a roundabout way of wondering what the main difficulties
> would be in attaching things like directionality to a call.

Directionality?

> Not arguing for anything here, just an onlooker wanting to understand. :-)
>
> (BTW, it sounds like restricting memory accesses to GIMPLE_ASSIGN
> might cause trouble for the interleave load/store stuff too.)

Well.  In the end my plan was to have a GIMPLE_LOAD and GIMPLE_STORE
stmt, where the load would load to an SSA name and the store would store from
a constant or an SSA name.  Advantages would be simplified data-flow analysis
and things like aggregate copy propagation and value-numbering for free.  It
would also be easier to attach special data / properties to the now
single load / store
sites (where in calls you can have an arbitrary number of loads at
least).  Whatever
special property the interleaved load/store has would be stored there, too.  The
idea was to be able to fold most of the implicit information about
loads/stores that
are in the MEM_REF /COMPONENT_REF / ARRAY_REF trees into proper "gimple"
level information, like having an array of index, stride tuples for
(multidimensional)
array accesses.  Think of it like a place where we can properly embed the
MEM_ATTRs we have on the RTL side for example.  That's much easier if
there were loads/stores only in very defined places.

Richard.

Richard Guenther <richard.guenther@gmail.com> writes:
> On Fri, Apr 6, 2012 at 10:13 AM, Richard Sandiford
> <rdsandiford@googlemail.com> wrote:
>> Richard Guenther <richard.guenther@gmail.com> writes:
>>>> They can affect shared memory in some ways like a call, but don't have many
>>>> of the other attributes of call.  They are really more like an assignment or
>>>> other operation with arbitrary shared memory side effects.  I do hope to be
>>>> able to teach the optimizers the directionality of the memory model
>>>> restrictions.  ie, ACQUIRE is only a barrier to hoisting shared memory
>>>> code...  stores can be moved downward past this mode. RELEASE is only a
>>>> barrier to sinking code.   RELAXED is no barrier at all to code motion.  In
>>>> fact, a relaxed store is barely different than a real store... but there is
>>>> a slight difference so we can't make it a normal store :-P.
>>>>
>>>> By teaching the other parts of the compiler about a GIMPLE_ ATOMIC, we could
>>>> hopefully lessen their impact eventually.
>>>
>>> Ok.  I suppose having a GIMPLE_ATOMIC is fine then.
>>
>> Just for my own education really, but: does this mean that there'd
>> be unnecessary pessimisation in representing the thing as a call?
>
> No, there are not.  They are more pessimized than GIMPLE_ASSIGNs
> (unless you handle them specially in a few places).  But the same is
> true for GIMPLE_ATOMIC.  The question is one of convenience as
> far as I understand.  In general I would like to avoid new GIMPLE codes,
> especially "random" ones.  You can do everything with builtins or
> internal functions just fine.
>
>> The interleaved load/store internal fns are really assignments too,
>> so if calls aren't right for that kind of operation, maybe we need
>> to replace the internal fns with something else.  Or at least come
>> up with some new call properties.
>
> What missed optimizations do you see?

None. :-)  But...

>> Which is a roundabout way of wondering what the main difficulties
>> would be in attaching things like directionality to a call.
>
> Directionality?

[See above.]

...I was asking in the context quoted above, which seemed to be the bit
that convinced you GIMPLE_ATOMIC would be OK after all.  And the two
main reasons in the bit quoted above seemed to be that GIMPLE_ATOMIC
was more like GIMPLE_ASSIGN (which is true of the current internal
fns too, and was why I was interested) and that we wanted to add the
directionality of the memory model (which seemed at face value like
something that could be attached to a call).

>> Not arguing for anything here, just an onlooker wanting to understand. :-)
>>
>> (BTW, it sounds like restricting memory accesses to GIMPLE_ASSIGN
>> might cause trouble for the interleave load/store stuff too.)
>
> Well.  In the end my plan was to have a GIMPLE_LOAD and GIMPLE_STORE
> stmt, where the load would load to an SSA name and the store would store from
> a constant or an SSA name.  Advantages would be simplified data-flow analysis
> and things like aggregate copy propagation and value-numbering for free.  It
> would also be easier to attach special data / properties to the now
> single load / store
> sites (where in calls you can have an arbitrary number of loads at
> least).  Whatever
> special property the interleaved load/store has would be stored there, too.  The
> idea was to be able to fold most of the implicit information about
> loads/stores that
> are in the MEM_REF /COMPONENT_REF / ARRAY_REF trees into proper "gimple"
> level information, like having an array of index, stride tuples for
> (multidimensional)
> array accesses.  Think of it like a place where we can properly embed the
> MEM_ATTRs we have on the RTL side for example.  That's much easier if
> there were loads/stores only in very defined places.

Ah, OK, so there'd still be a single gimple stmt (GIMPLE_LOAD or GIMPLE_STORE),
and that stmt would do the interleaving too?  Sounds good.  I was worried at
first that we'd have two separate stmts (e.g. a load and an interleave)
which was what the internal fns were supposed to avoid.

Thanks,
Richard

On Tue, Apr 10, 2012 at 3:14 PM, Richard Sandiford
<rdsandiford@googlemail.com> wrote:
> Richard Guenther <richard.guenther@gmail.com> writes:
>> On Fri, Apr 6, 2012 at 10:13 AM, Richard Sandiford
>> <rdsandiford@googlemail.com> wrote:
>>> Richard Guenther <richard.guenther@gmail.com> writes:
>>>>> They can affect shared memory in some ways like a call, but don't have many
>>>>> of the other attributes of call.  They are really more like an assignment or
>>>>> other operation with arbitrary shared memory side effects.  I do hope to be
>>>>> able to teach the optimizers the directionality of the memory model
>>>>> restrictions.  ie, ACQUIRE is only a barrier to hoisting shared memory
>>>>> code...  stores can be moved downward past this mode. RELEASE is only a
>>>>> barrier to sinking code.   RELAXED is no barrier at all to code motion.  In
>>>>> fact, a relaxed store is barely different than a real store... but there is
>>>>> a slight difference so we can't make it a normal store :-P.
>>>>>
>>>>> By teaching the other parts of the compiler about a GIMPLE_ ATOMIC, we could
>>>>> hopefully lessen their impact eventually.
>>>>
>>>> Ok.  I suppose having a GIMPLE_ATOMIC is fine then.
>>>
>>> Just for my own education really, but: does this mean that there'd
>>> be unnecessary pessimisation in representing the thing as a call?
>>
>> No, there are not.  They are more pessimized than GIMPLE_ASSIGNs
>> (unless you handle them specially in a few places).  But the same is
>> true for GIMPLE_ATOMIC.  The question is one of convenience as
>> far as I understand.  In general I would like to avoid new GIMPLE codes,
>> especially "random" ones.  You can do everything with builtins or
>> internal functions just fine.
>>
>>> The interleaved load/store internal fns are really assignments too,
>>> so if calls aren't right for that kind of operation, maybe we need
>>> to replace the internal fns with something else.  Or at least come
>>> up with some new call properties.
>>
>> What missed optimizations do you see?
>
> None. :-)  But...
>
>>> Which is a roundabout way of wondering what the main difficulties
>>> would be in attaching things like directionality to a call.
>>
>> Directionality?
>
> [See above.]
>
> ...I was asking in the context quoted above, which seemed to be the bit
> that convinced you GIMPLE_ATOMIC would be OK after all.  And the two
> main reasons in the bit quoted above seemed to be that GIMPLE_ATOMIC
> was more like GIMPLE_ASSIGN (which is true of the current internal
> fns too, and was why I was interested) and that we wanted to add the
> directionality of the memory model (which seemed at face value like
> something that could be attached to a call).
>
>>> Not arguing for anything here, just an onlooker wanting to understand. :-)
>>>
>>> (BTW, it sounds like restricting memory accesses to GIMPLE_ASSIGN
>>> might cause trouble for the interleave load/store stuff too.)
>>
>> Well.  In the end my plan was to have a GIMPLE_LOAD and GIMPLE_STORE
>> stmt, where the load would load to an SSA name and the store would store from
>> a constant or an SSA name.  Advantages would be simplified data-flow analysis
>> and things like aggregate copy propagation and value-numbering for free.  It
>> would also be easier to attach special data / properties to the now
>> single load / store
>> sites (where in calls you can have an arbitrary number of loads at
>> least).  Whatever
>> special property the interleaved load/store has would be stored there, too.  The
>> idea was to be able to fold most of the implicit information about
>> loads/stores that
>> are in the MEM_REF /COMPONENT_REF / ARRAY_REF trees into proper "gimple"
>> level information, like having an array of index, stride tuples for
>> (multidimensional)
>> array accesses.  Think of it like a place where we can properly embed the
>> MEM_ATTRs we have on the RTL side for example.  That's much easier if
>> there were loads/stores only in very defined places.
>
> Ah, OK, so there'd still be a single gimple stmt (GIMPLE_LOAD or GIMPLE_STORE),
> and that stmt would do the interleaving too?

Well, whatever we'd like to add (part of the atomic stuff would fit here, too,
just not the operation part like increment).

Richard.

>  Sounds good.  I was worried at
> first that we'd have two separate stmts (e.g. a load and an interleave)
> which was what the internal fns were supposed to avoid.



> Thanks,
> Richard

On 04/05/2012 05:14 AM, Richard Guenther wrote:
>
> Ok.  Remember that you should use non-tree things if you can in GIMPLE
> land.  This probably means that both the size and the memmodel "operands"
> should be
>
> + struct GTY(()) gimple_statement_atomic
> + {
> +   /* [ WORD 1-8 ]  */
> +   struct gimple_statement_with_memory_ops_base membase;
> +
> +   /* [ WORD 9 ] */
> +   enum gimple_atomic_kind kind;
> +
>       enum gimple_atomic_memmodel memmodel;
>
>       unsigned size;
>
> and not be trees in the ops array.  Even more, both kind and memmodel
> should probably go in membase.base.subcode

I'm using subcode now for for the fetch_op and op_fetch operation when 
we actually need a tree code for plus, sub, and, etc...  so I am 
utilizing that field. Since the 'kind' field is present in ALL node, and 
the tree code was only needed in some, it looked cleaner to utilize the 
subcode field for the 'sometimes' field so that it wouldnt be an obvious 
wasted field in all the non-fetch nodes.  In the end it amounts to the 
same thing, but just looked cleaner :-)   I could change if it you felt 
strongly about it and use subcode for the kind and create a tree_code 
field in the object for the operation.

Since integral atomics are always of an unsigned type ,  I could switch 
over and use 'unsigned size' instead of 'tree fntype' for them (I will 
rename it), but then things may  be more complicated when dealing with 
generic atomics...  those can be structure or array types and I was 
planning to allow leaving the type in case I discover something useful I 
can do with it.  It may ultimately turn out that the real type isn't 
going to matter, in which case I will remove it and replace it with an 
unsigned int for size.

And the reason memmodel is a tree is because, as ridiculous as it seems, 
it can ultimately be a runtime value.    Even barring that, it shows up 
as a variable after inlining before various propagation engines run, 
especially in the  C++ templates.  So it must be a tree.

>> I was actually thinking about doing it during gimplification... I hadnt
>> gotten as far as figuring out what to do with the functions from the front
>> end yet.  I dont know that code well, but I was in fact hoping there was a
>> way to 'recognize' the function names easily and avoid built in functions
>> completely...
> Heh ... you'd still need a GENERIC representation then.  Possibly
> a ATOMIC_OP tree may do.
possibly...   or maybe a single generic atomic_builtin with a kind and a 
variable list of  parameters.

> well, the names must remain exposed and recognizable since they are 'out
> there'.  Maybe under the covers I can just leave them as normal calls and
> then during gimplification simply recognize the names and generate
> GIMPLE_ATOMIC statements directly from the CALL_EXPR.  That would be ideal.
>   That way there are no builtins any more.
> I suppose my question was whether the frontends need to do sth about the
> __atomic keyword or if that is simply translated to some type flag - or
> is that keyword applying to operations, not to objects or types?
>
The _Atomic keyword is a type modifier like const or volatile.  So 
during gimplification I'll also look for all occurrences of variables in 
normal expressions which have that bit set in the type,  then translate 
the expression to utilize the new gimple atomic node.  so

_Atomic int var = 0;
  var += 4;
  foo (var);

would become

  __atomic_add_fetch (&var, 4, SEQ_CST);
  D.123 = __atomic_load (&var, SEQ_CST);
foo (D.123);




>>
>>>> So bottom line, a GIMPLE_ATOMIC statement is just an object that is much
>>>> easier to work with.
>>> Yes, I see that it is easier to work with for you.  All other statements
>>> will
>>> see GIMPLE_ATOMICs as blockers for their work though, even if they
>>> already deal with calls just fine - that's why I most of the time suggest
>>> to use builtins (or internal fns) to do things (I bet you forgot to update
>>> enough predicates ...).  Can GIMPLE_ATOMICs throw with
>>> -fnon-call-exceptions?
>>> I suppose yes.  One thing you missed at least ;)
>>
>> Not that I am aware of, they are 'noexcept'.  But I'm sure I've missed more
>> than a few things so far.  Im pretty early in the process :-)
> What about compare-exchange on a pointer dereference? The pointer
> dereference surely can trap, so it can throw with -fnon-call-exceptions.  No?
in theory *any* gimple atomic operation could end up being expanded as a 
library call, so I will have to ensure they are treated as calls because 
of things like that.

These are all things I will focus on once all the basic functionality is 
there.  This patch is not meant to be fully flushed out, I just wanted 
some eyes on it before I checked it into the branch so i dont carry this 
huge patch set around when making changes.  When I get things functional 
in the branch  I'll revisit all this and any of the other implementation 
comments I don't get to and then submit another patch for review.
>
> + /* Return the expression field of atomic operation GS.  */
> +
> + static inline tree
> + gimple_atomic_expr (const_gimple gs)
> + {
> +   GIMPLE_CHECK (gs, GIMPLE_ATOMIC);
> +   gcc_assert (gimple_atomic_has_expr (gs));
> +   return gimple_op (gs, 2);
> + }
>
> err - what's "expression" in this context?  I hope it's not an arbitrary
> tcc_expression tree?!

Its just the 'expression' parameter of atomic operations which have it, 
like  store , fetch_add, or exchange. It would normally be an SSA_NAME 
or const.  I suppose we coud call it 'value' or something if expression 
is confusing.


>
> + /* Return the arithmetic operation tree code for atomic operation GS.  */
> +
> + static inline enum tree_code
> + gimple_atomic_op_code (const_gimple gs)
> + {
> +   GIMPLE_CHECK (gs, GIMPLE_ATOMIC);
> +   gcc_assert (gimple_atomic_kind (gs) == GIMPLE_ATOMIC_FETCH_OP ||
> +             gimple_atomic_kind (gs) == GIMPLE_ATOMIC_OP_FETCH);
> +   return (enum tree_code) gs->gsbase.subcode;
> + }
>
> now, what was it with this "expression" thing again?  Btw, ||s go to the
> next line.  subcode should be the atomic kind - it seems that you glob
> too much into GIMPLE_ATOMIC and that you maybe should sub-class
> GIMPLE_ATOMIC properly via the subcode field.  You'd have an
> gimple_atomic_base which fences could use for example.

I was trying to make it simple and utilize the variable length ops array 
to handle the variable stuff :-) It took many attempts to arrive at this 
layout.

They don't really break down well into sub-components.  I wanted to use 
a single routine to access a given field for all atomic kinds, so 
gimple_atomic_target(),  gimple_atomic_lhs(), and gimple_atomic_expr() 
just work .  The problem is that they don't break down into a tree 
structure, but more of a multiple-inheritance type thing.

LOAD has a LHS and a TARGET, no EXPR
STORE has no LHS, but has a TARGET and EXPR
EXCHANGE has a LHS, a TARGET and an EXPR
FENCE has no target or anything else.
COMPARE_EXCHANGE has 2 LHS, a TARGET, and an EXPR, not to mention an 
additional memorder

I set it up so that the variable length array always stores a given 
parameter at the same offset, and also allows for contiguous trees in 
the array to represent all the LHS or RHS parameters for easy generic 
operand scanning or whatever.  And each statement type only allocated 
the right amount of memory required.

I planned to add a comment to the description showing the layout of the 
various nodes:
/*
   LOAD         | ORDER | TARGET | LHS  |
    STORE        | ORDER | TARGET | EXPR |
    EXCHANGE     | ORDER | TARGET | EXPR | LHS      |
    COMPARE_EXCHG| ORDER | TARGET | EXPR | EXPECTED | FAIL_ORDER | LHS2 
| LHS1 |
    FETCH        | ORDER | TARGET | EXPR | LHS      |
    TEST_AND_SET | ORDER | TARGET | LHS  |
    CLEAR        | ORDER | TARGET |
    FENCE        | ORDER |


This allows all the RHS values to be contiguous for bulk processing like 
operands, and located at the same index for an easy access routine.  The 
LHS is viewed from right to left, and allows more than 1 value  as 
required by compare_exchange.  They also are contiguous for generic 
access, and a single LHS routine can also be used to access those values.
*/

Is that OK?     it seemed better than trying to map it to some sort of 
hierarchical structure it doesn't really fit into.

Andrew

On 04/05/2012 05:14 AM, Richard Guenther wrote:
> + static inline bool
> + gimple_atomic_has_fail_order (const_gimple gs)
> + {
> +   return gimple_atomic_kind (gs) == GIMPLE_ATOMIC_COMPARE_EXCHANGE;
> + }
>
> btw, these kind of predicates look superfluous to me - if they are true
> exactly for one atomic kind then users should use the predicate to
> test for that specific atomic kind, not for some random field presence.

yeah, a previous incarnation artifact, removed.
>
> All asserts in inline functions should be gcc_checking_asserts.
indeed.
>
>
> you should have a gimple_build_atomic_raw function that takes all
> operands and the atomic kind, avoiding the need for all the repeated
> calls of gimple_atomic_set_* as well as avoid all the repeated checking
> this causes.
as well. done.

>
> +   else if (is_gimple_atomic (stmt))
> +     {
> +       tree t;
> +       if (visit_store)
> +         {
> +         for (i = 0; i<  gimple_atomic_num_lhs (stmt); i++)
> +           {
> +             t = gimple_atomic_lhs (stmt, i);
> +             if (t)
> +               {
> +                 t = get_base_loadstore (t);
> +                 if (t)
> +                   ret |= visit_store (stmt, t, data);
> +               }
>
> I thought results are always registers?  The walk_stmt_load_store_addr_ops
> looks wrong to me.  As the loads/stores are implicit (you only have addresses)
> you have to adjust all callers of walk_stmt_load_store_addr_ops to handle
> atomics specially as they expect to come along all loads/stores that way.
> Those also handle calls and asms (for "memory" clobber) specially.

hmm, yeah they always return a value.     I was just copying the 
gimple_call code...  Why would we need to do this processing  for a 
GIMPLE_CALL lhs and not a GIMPLE_ATOMIC lhs?   And the RHS processing is 
the same as for a is_gimple_call as well...  it was lifted from the code 
immediately following.,..  I tried to write all this code to return the 
same values as would have been returned had it actually been a  built-in 
__sync or __atomic call like we have today.  Once I had them all, then 
we could actually make any improvements based on our known side effect 
limits.

I guess I don't understand the rest of the comment about why I need to 
do something different here than with a call...
> Index: tree-ssa-alias.c
> ===================================================================
> *** tree-ssa-alias.c    (revision 186098)
> --- tree-ssa-alias.c    (working copy)
> *************** ref_maybe_used_by_stmt_p (gimple stmt, t
> *** 1440,1445 ****
> --- 1440,1447 ----
>        }
>      else if (is_gimple_call (stmt))
>        return ref_maybe_used_by_call_p (stmt, ref);
> +   else if (is_gimple_atomic (stmt))
> +     return true;
>
> please add a comment before these atomic handlings that we assume
> they are using/clobbering all refs because they are considered memory
> optimization barriers.  Btw, does this apply to non-address-taken automatic
> references?  I suppose not.  Consider:
>
> int foo()
> {
>    struct s;
>    atomic_fence();
>    s.a = 1;
>    atomic_fence();
>    return s.a;
> }
>
> we still should be able to optimize this to return 1, no?  At least SRA will
yes, locals can do anything they want since they aren't visible to other 
processes.  at the moment, we'll leave those fences in because we dont 
optimize atomics at all, but  "in the fullness of time" this will be 
optimized to:
int foo()
{
   atomic_fence()
   return 1;
}

at the moment we produce:

int foo()
{
   atomic_fence()
   atomic_fence()
   return 1;
}

>
> *************** stmt_kills_ref_p_1 (gimple stmt, ao_ref
> *** 1814,1819 ****
> --- 1818,1825 ----
>          }
>        }
>
> +   if (is_gimple_atomic (stmt))
> +     return true;
>
> that's for sure wrong ;)  It should return false.

err, yeah. oops.
>
> Index: tree-ssa-sink.c
> ===================================================================
> *** tree-ssa-sink.c     (revision 186098)
> --- tree-ssa-sink.c     (working copy)
> *************** is_hidden_global_store (gimple stmt)
> *** 145,150 ****
> --- 145,154 ----
>        {
>          tree lhs;
>
> +       /* Don't optimize across an atomic operation.  */
> +       if (is_gimple_atomic (stmt))
> +         return true;
> +
>
> that's bogus, too (really all uses of is_hidden_global_store should go away).
> Please look into the few callers of this function and  handle atomics in
> a correct way explicitely.
All atomic operations will have a VDEF so in theory it should be fine to 
ignore.  There are only 2 uses:
   DCE already has code added to handle them, and
   DSE handles it through ref_maybe_used_by_stmt_p.

removed.


>
> +         else if (is_gimple_atomic (stmt))
> +           {
> +             unsigned n;
> +
> +             /* We may be able to lessen this with more relaxed memory
> +                models, but for now, its a full barrier.  */
> +             mark_all_reaching_defs_necessary (stmt);
> +
> +             for (n = 0; n<  gimple_atomic_num_rhs (stmt); n++)
> +               {
> +                 tree t = gimple_op (stmt, n);
> +                 if (TREE_CODE (t) != SSA_NAME&&
> +                     TREE_CODE (t) != INTEGER_CST&&
> +                     !is_gimple_min_invariant (t)&&
> +                     !ref_may_be_aliased (t))
> +                   mark_aliased_reaching_defs_necessary (stmt, t);
> +               }
> +           }
>
> for sure atomics do not make non-aliased automatic variable stores necessary.
> At least I hope so.  As there are only addresses in the atomic ops the
> code looks wrong to me (and&&s go to the next line ...).  As you are
> marking everything needed anway you can just remove the bogus loop
> completely.
I was simply copying the code path that was followed for gimple_call 
which handled the old __sync_ and __atomic builtins...  this is what 
that code did.  there are addresses in the atomic ops, but the 
functionality of those operands can dereference and store or load from 
those address...?
ie  the generic
   atomic_store (&atomic, &expr)
dereferences  *expr and stores it into *atomic...

I figured whatever I can see as a function call argument to __atomic_* 
would be seeable in a GIMPLE_ATOMIC position as well...?


> +     case GIMPLE_ATOMIC:
> +       /* Treat this like a call for now, it may expand into a call.  */
> +       if (gimple_atomic_kind (stmt) != GIMPLE_ATOMIC_FENCE)
> +       cost = gimple_num_ops (stmt) *
> +              estimate_move_cost (TREE_TYPE (gimple_atomic_target (stmt)));
> +       else
> +         cost = 1;
> +       break;
>
> for sure this counts way too many "ops".  There is at most a single
> memory operand as far as I understand.  A size/speed cost of 1 for
> a FENCE is also too low.
These were just fillers values to get it to compile until I had time to 
understand the proper way to find these values.  I thought there were 
just instruction count guesses, and again mimiced what the gimple_call 
code did.

> I miss handling of GIMPLE_ATOMICs in tree-ssa-structalias.c.
>
>
No doubt I havent gotten there yet because it did cause a compilation 
failure :-) :-)

Andrew

On Thu, Apr 26, 2012 at 7:53 PM, Andrew MacLeod <amacleod@redhat.com> wrote:
> On 04/05/2012 05:14 AM, Richard Guenther wrote:
>>
>>
>> Ok.  Remember that you should use non-tree things if you can in GIMPLE
>> land.  This probably means that both the size and the memmodel "operands"
>> should be
>>
>> + struct GTY(()) gimple_statement_atomic
>> + {
>> +   /* [ WORD 1-8 ]  */
>> +   struct gimple_statement_with_memory_ops_base membase;
>> +
>> +   /* [ WORD 9 ] */
>> +   enum gimple_atomic_kind kind;
>> +
>>      enum gimple_atomic_memmodel memmodel;
>>
>>      unsigned size;
>>
>> and not be trees in the ops array.  Even more, both kind and memmodel
>> should probably go in membase.base.subcode
>
>
> I'm using subcode now for for the fetch_op and op_fetch operation when we
> actually need a tree code for plus, sub, and, etc...  so I am utilizing that
> field. Since the 'kind' field is present in ALL node, and the tree code was
> only needed in some, it looked cleaner to utilize the subcode field for the
> 'sometimes' field so that it wouldnt be an obvious wasted field in all the
> non-fetch nodes.  In the end it amounts to the same thing, but just looked
> cleaner :-)   I could change if it you felt strongly about it and use
> subcode for the kind and create a tree_code field in the object for the
> operation.
>
> Since integral atomics are always of an unsigned type ,  I could switch over
> and use 'unsigned size' instead of 'tree fntype' for them (I will rename
> it), but then things may  be more complicated when dealing with generic
> atomics...  those can be structure or array types and I was planning to
> allow leaving the type in case I discover something useful I can do with it.
>  It may ultimately turn out that the real type isn't going to matter, in
> which case I will remove it and replace it with an unsigned int for size.

So it eventually will support variable-size types?

> And the reason memmodel is a tree is because, as ridiculous as it seems, it
> can ultimately be a runtime value.    Even barring that, it shows up as a
> variable after inlining before various propagation engines run, especially
> in the  C++ templates.  So it must be a tree.

Ick.  That sounds gross.  So, if it ends up a variable at the time we generate
assembly we use a "conservative" constant value for it?

>
>>> I was actually thinking about doing it during gimplification... I hadnt
>>> gotten as far as figuring out what to do with the functions from the
>>> front
>>> end yet.  I dont know that code well, but I was in fact hoping there was
>>> a
>>> way to 'recognize' the function names easily and avoid built in functions
>>> completely...
>>
>> Heh ... you'd still need a GENERIC representation then.  Possibly
>> a ATOMIC_OP tree may do.
>
> possibly...   or maybe a single generic atomic_builtin with a kind and a
> variable list of  parameters.
>
>
>> well, the names must remain exposed and recognizable since they are 'out
>> there'.  Maybe under the covers I can just leave them as normal calls and
>> then during gimplification simply recognize the names and generate
>> GIMPLE_ATOMIC statements directly from the CALL_EXPR.  That would be
>> ideal.
>>  That way there are no builtins any more.
>> I suppose my question was whether the frontends need to do sth about the
>> __atomic keyword or if that is simply translated to some type flag - or
>> is that keyword applying to operations, not to objects or types?
>>
> The _Atomic keyword is a type modifier like const or volatile.  So during
> gimplification I'll also look for all occurrences of variables in normal
> expressions which have that bit set in the type,  then translate the
> expression to utilize the new gimple atomic node.  so
>
> _Atomic int var = 0;
>  var += 4;
>  foo (var);
>
> would become
>
>  __atomic_add_fetch (&var, 4, SEQ_CST);
>  D.123 = __atomic_load (&var, SEQ_CST);
> foo (D.123);

Hmm, ok.  So you are changing GENERIC in fact.  I suppose _Atomic is
restricted to global variables.  Can I attach _Atomic to allocated storage
via pointer casts?

Consider writing up semantics of _Atomic into generic.texi please.

>
>
>
>
>>>
>>>>> So bottom line, a GIMPLE_ATOMIC statement is just an object that is
>>>>> much
>>>>> easier to work with.
>>>>
>>>> Yes, I see that it is easier to work with for you.  All other statements
>>>> will
>>>> see GIMPLE_ATOMICs as blockers for their work though, even if they
>>>> already deal with calls just fine - that's why I most of the time
>>>> suggest
>>>> to use builtins (or internal fns) to do things (I bet you forgot to
>>>> update
>>>> enough predicates ...).  Can GIMPLE_ATOMICs throw with
>>>> -fnon-call-exceptions?
>>>> I suppose yes.  One thing you missed at least ;)
>>>
>>>
>>> Not that I am aware of, they are 'noexcept'.  But I'm sure I've missed
>>> more
>>> than a few things so far.  Im pretty early in the process :-)
>>
>> What about compare-exchange on a pointer dereference? The pointer
>> dereference surely can trap, so it can throw with -fnon-call-exceptions.
>>  No?
>
> in theory *any* gimple atomic operation could end up being expanded as a
> library call, so I will have to ensure they are treated as calls because of
> things like that.

Well, they are calls with a very well-defined set of side-effects.  Otherwise
not representing them as calls would be a waste of time.  Thus, no - they
do not need to be considered "calls" everywhere (well, treating them the
same as calls should be conservative) but treating them as "atomics" even
if they were expanded as calls needs to be correct.

> These are all things I will focus on once all the basic functionality is
> there.  This patch is not meant to be fully flushed out, I just wanted some
> eyes on it before I checked it into the branch so i dont carry this huge
> patch set around when making changes.  When I get things functional in the
> branch  I'll revisit all this and any of the other implementation comments I
> don't get to and then submit another patch for review.

Ok, I see.

>>
>> + /* Return the expression field of atomic operation GS.  */
>> +
>> + static inline tree
>> + gimple_atomic_expr (const_gimple gs)
>> + {
>> +   GIMPLE_CHECK (gs, GIMPLE_ATOMIC);
>> +   gcc_assert (gimple_atomic_has_expr (gs));
>> +   return gimple_op (gs, 2);
>> + }
>>
>> err - what's "expression" in this context?  I hope it's not an arbitrary
>> tcc_expression tree?!
>
>
> Its just the 'expression' parameter of atomic operations which have it, like
>  store , fetch_add, or exchange. It would normally be an SSA_NAME or const.
>  I suppose we coud call it 'value' or something if expression is confusing.

Or even 'op'.

>
>
>>
>> + /* Return the arithmetic operation tree code for atomic operation GS.
>>  */
>> +
>> + static inline enum tree_code
>> + gimple_atomic_op_code (const_gimple gs)
>> + {
>> +   GIMPLE_CHECK (gs, GIMPLE_ATOMIC);
>> +   gcc_assert (gimple_atomic_kind (gs) == GIMPLE_ATOMIC_FETCH_OP ||
>> +             gimple_atomic_kind (gs) == GIMPLE_ATOMIC_OP_FETCH);
>> +   return (enum tree_code) gs->gsbase.subcode;
>> + }
>>
>> now, what was it with this "expression" thing again?  Btw, ||s go to the
>> next line.  subcode should be the atomic kind - it seems that you glob
>> too much into GIMPLE_ATOMIC and that you maybe should sub-class
>> GIMPLE_ATOMIC properly via the subcode field.  You'd have an
>> gimple_atomic_base which fences could use for example.
>
>
> I was trying to make it simple and utilize the variable length ops array to
> handle the variable stuff :-) It took many attempts to arrive at this
> layout.
>
> They don't really break down well into sub-components.  I wanted to use a
> single routine to access a given field for all atomic kinds, so
> gimple_atomic_target(),  gimple_atomic_lhs(), and gimple_atomic_expr() just
> work .  The problem is that they don't break down into a tree structure, but
> more of a multiple-inheritance type thing.
>
> LOAD has a LHS and a TARGET, no EXPR
> STORE has no LHS, but has a TARGET and EXPR
> EXCHANGE has a LHS, a TARGET and an EXPR
> FENCE has no target or anything else.
> COMPARE_EXCHANGE has 2 LHS, a TARGET, and an EXPR, not to mention an
> additional memorder

Looks like a hieararchy "no target or anything else" -> "target" ->
"expr" -> "memorder" would work, with only "lhs" being optional and
present everywhere.
Of course the hierarchy only makes sense for things that are not trees
(I was thinking of memorder originally - but that thought fell apart).
 So in the
end apart from abstracting a base for FENCE the flat hieararchy makes sense
(all but FENCE have a type / size).

> I set it up so that the variable length array always stores a given
> parameter at the same offset, and also allows for contiguous trees in the
> array to represent all the LHS or RHS parameters for easy generic operand
> scanning or whatever.  And each statement type only allocated the right
> amount of memory required.
>
> I planned to add a comment to the description showing the layout of the
> various nodes:
> /*
>  LOAD         | ORDER | TARGET | LHS  |
>   STORE        | ORDER | TARGET | EXPR |
>   EXCHANGE     | ORDER | TARGET | EXPR | LHS      |
>   COMPARE_EXCHG| ORDER | TARGET | EXPR | EXPECTED | FAIL_ORDER | LHS2 | LHS1
> |
>   FETCH        | ORDER | TARGET | EXPR | LHS      |
>   TEST_AND_SET | ORDER | TARGET | LHS  |
>   CLEAR        | ORDER | TARGET |
>   FENCE        | ORDER |
>
>
> This allows all the RHS values to be contiguous for bulk processing like
> operands, and located at the same index for an easy access routine.  The LHS
> is viewed from right to left, and allows more than 1 value  as required by
> compare_exchange.  They also are contiguous for generic access, and a single
> LHS routine can also be used to access those values.
> */
>
> Is that OK?     it seemed better than trying to map it to some sort of
> hierarchical structure it doesn't really fit into.

I suppose it's ok.  Please consider making a base available for FENCE
(does FENCE have a memorder?)

Richard.

> Andrew
>
>
>

On Thu, Apr 26, 2012 at 10:07 PM, Andrew MacLeod <amacleod@redhat.com> wrote:
> On 04/05/2012 05:14 AM, Richard Guenther wrote:
>>
>> + static inline bool
>> + gimple_atomic_has_fail_order (const_gimple gs)
>> + {
>> +   return gimple_atomic_kind (gs) == GIMPLE_ATOMIC_COMPARE_EXCHANGE;
>> + }
>>
>> btw, these kind of predicates look superfluous to me - if they are true
>> exactly for one atomic kind then users should use the predicate to
>> test for that specific atomic kind, not for some random field presence.
>
>
> yeah, a previous incarnation artifact, removed.
>
>>
>> All asserts in inline functions should be gcc_checking_asserts.
>
> indeed.
>
>>
>>
>> you should have a gimple_build_atomic_raw function that takes all
>> operands and the atomic kind, avoiding the need for all the repeated
>> calls of gimple_atomic_set_* as well as avoid all the repeated checking
>> this causes.
>
> as well. done.
>
>
>>
>> +   else if (is_gimple_atomic (stmt))
>> +     {
>> +       tree t;
>> +       if (visit_store)
>> +         {
>> +         for (i = 0; i<  gimple_atomic_num_lhs (stmt); i++)
>> +           {
>> +             t = gimple_atomic_lhs (stmt, i);
>> +             if (t)
>> +               {
>> +                 t = get_base_loadstore (t);
>> +                 if (t)
>> +                   ret |= visit_store (stmt, t, data);
>> +               }
>>
>> I thought results are always registers?  The walk_stmt_load_store_addr_ops
>> looks wrong to me.  As the loads/stores are implicit (you only have
>> addresses)
>> you have to adjust all callers of walk_stmt_load_store_addr_ops to handle
>> atomics specially as they expect to come along all loads/stores that way.
>> Those also handle calls and asms (for "memory" clobber) specially.
>
>
> hmm, yeah they always return a value.     I was just copying the gimple_call
> code...  Why would we need to do this processing  for a GIMPLE_CALL lhs and
> not a GIMPLE_ATOMIC lhs?

GIMPLE_CALL lhs can be memory if the call returns an aggregate, similar
GIMPLE_CALL arguments can be memory if they are aggregate.

Can this be the case for atomics as well?

>   And the RHS processing is the same as for a
> is_gimple_call as well...  it was lifted from the code immediately
> following.,..  I tried to write all this code to return the same values as
> would have been returned had it actually been a  built-in __sync or __atomic
> call like we have today.  Once I had them all, then we could actually make
> any improvements based on our known side effect limits.
>
> I guess I don't understand the rest of the comment about why I need to do
> something different here than with a call...

Well, all callers that use walk_stmt_load_store/addr_ops need to handle
non-explicit loads/stores represented by the stmt.  For calls this includes
the loads and stores the callee may perform.  For atomics this includes .... ?
(depends on whether the operand of an atomic-load is a pointer or an object,
I suppose it is a pointer for the following) For atomic this includes the
implicit load of *{address operand} which will _not_ be returned by
walk_stmt_load_store/addr_ops.  Thus callers that expect to see all loads/stores
(like ipa-pure-const.c) need to explicitely handle atomics similar to how they
handle calls and asms (if only in a very conservative way).  Similar the
alias oracle needs to handle them (obviously).

>> Index: tree-ssa-alias.c
>> ===================================================================
>> *** tree-ssa-alias.c    (revision 186098)
>> --- tree-ssa-alias.c    (working copy)
>> *************** ref_maybe_used_by_stmt_p (gimple stmt, t
>> *** 1440,1445 ****
>> --- 1440,1447 ----
>>       }
>>     else if (is_gimple_call (stmt))
>>       return ref_maybe_used_by_call_p (stmt, ref);
>> +   else if (is_gimple_atomic (stmt))
>> +     return true;
>>
>> please add a comment before these atomic handlings that we assume
>> they are using/clobbering all refs because they are considered memory
>> optimization barriers.  Btw, does this apply to non-address-taken
>> automatic
>> references?  I suppose not.  Consider:
>>
>> int foo()
>> {
>>   struct s;
>>   atomic_fence();
>>   s.a = 1;
>>   atomic_fence();
>>   return s.a;
>> }
>>
>> we still should be able to optimize this to return 1, no?  At least SRA
>> will
>
> yes, locals can do anything they want since they aren't visible to other
> processes.  at the moment, we'll leave those fences in because we dont
> optimize atomics at all, but  "in the fullness of time" this will be
> optimized to:
> int foo()
> {
>  atomic_fence()
>  return 1;
> }
>
> at the moment we produce:
>
> int foo()
> {
>  atomic_fence()
>  atomic_fence()
>  return 1;
>
> }

Which is inconsistend with the alias-oracle implementation.  Please fix it
to at _least_ not consider non-aliased locals.  You can look at the call
handling for how to do this - where you can also see how to do even better
by using points-to information from the pointer operand of the atomics
that specify the memory loaded/stored.  You don't want to hide all your
implementation bugs by making the alias oracle stupid ;)

>>
>> *************** stmt_kills_ref_p_1 (gimple stmt, ao_ref
>> *** 1814,1819 ****
>> --- 1818,1825 ----
>>         }
>>       }
>>
>> +   if (is_gimple_atomic (stmt))
>> +     return true;
>>
>> that's for sure wrong ;)  It should return false.
>
>
> err, yeah. oops.
>
>>
>> Index: tree-ssa-sink.c
>> ===================================================================
>> *** tree-ssa-sink.c     (revision 186098)
>> --- tree-ssa-sink.c     (working copy)
>> *************** is_hidden_global_store (gimple stmt)
>> *** 145,150 ****
>> --- 145,154 ----
>>       {
>>         tree lhs;
>>
>> +       /* Don't optimize across an atomic operation.  */
>> +       if (is_gimple_atomic (stmt))
>> +         return true;
>> +
>>
>> that's bogus, too (really all uses of is_hidden_global_store should go
>> away).
>> Please look into the few callers of this function and  handle atomics in
>> a correct way explicitely.
>
> All atomic operations will have a VDEF so in theory it should be fine to
> ignore.

Ignore?  Returning 'false' would be ignoring them.  Why do all atomic
operations have a VDEF?  At least atomic loads are not considered
stores, are they?

>  There are only 2 uses:
>  DCE already has code added to handle them, and
>  DSE handles it through ref_maybe_used_by_stmt_p.

Yes.  And eventually what matters for both callers should be folded into them
(let me put that somewhere ontop of my TODO ...)

For example DCE would happily remove atomic loads if they look like

 result-SSA-name = ATOMIC-LOAD <ptr-SSA-name>;

if result-SSA-name is not used anywhere.  And I don't see why we should
not be allowed to do this?  Returning true from the above function will
make DCE not remove it.

> removed.
>
>
>>
>> +         else if (is_gimple_atomic (stmt))
>> +           {
>> +             unsigned n;
>> +
>> +             /* We may be able to lessen this with more relaxed memory
>> +                models, but for now, its a full barrier.  */
>> +             mark_all_reaching_defs_necessary (stmt);
>> +
>> +             for (n = 0; n<  gimple_atomic_num_rhs (stmt); n++)
>> +               {
>> +                 tree t = gimple_op (stmt, n);
>> +                 if (TREE_CODE (t) != SSA_NAME&&
>> +                     TREE_CODE (t) != INTEGER_CST&&
>> +                     !is_gimple_min_invariant (t)&&
>> +                     !ref_may_be_aliased (t))
>> +                   mark_aliased_reaching_defs_necessary (stmt, t);
>> +               }
>> +           }
>>
>> for sure atomics do not make non-aliased automatic variable stores
>> necessary.
>> At least I hope so.  As there are only addresses in the atomic ops the
>> code looks wrong to me (and&&s go to the next line ...).  As you are
>>
>> marking everything needed anway you can just remove the bogus loop
>> completely.
>
> I was simply copying the code path that was followed for gimple_call which
> handled the old __sync_ and __atomic builtins...  this is what that code
> did.  there are addresses in the atomic ops, but the functionality of those
> operands can dereference and store or load from those address...?
> ie  the generic
>  atomic_store (&atomic, &expr)
> dereferences  *expr and stores it into *atomic...

Sure.  But it only can ever load/store from aliased variables (not
non-address-taken
local automatics).  That we did not handle this for the __sync_ atomics very
well is no excuse to not handle it well for atomics ;)

> I figured whatever I can see as a function call argument to __atomic_* would
> be seeable in a GIMPLE_ATOMIC position as well...?

Yes.  But you know - compared to a random call - there are no other side-effects
on memory.

>> +     case GIMPLE_ATOMIC:
>> +       /* Treat this like a call for now, it may expand into a call.  */
>> +       if (gimple_atomic_kind (stmt) != GIMPLE_ATOMIC_FENCE)
>> +       cost = gimple_num_ops (stmt) *
>> +              estimate_move_cost (TREE_TYPE (gimple_atomic_target
>> (stmt)));
>> +       else
>> +         cost = 1;
>> +       break;
>>
>> for sure this counts way too many "ops".  There is at most a single
>> memory operand as far as I understand.  A size/speed cost of 1 for
>> a FENCE is also too low.
>
> These were just fillers values to get it to compile until I had time to
> understand the proper way to find these values.  I thought there were just
> instruction count guesses, and again mimiced what the gimple_call code did.

Sure, still it does not make sense to account for "move" cost of the memorder
operand the same as for the "move" cost of the eventual load/store that
happens.  If it's a filler just fill in 'cost = 10' with a comment.

>
>> I miss handling of GIMPLE_ATOMICs in tree-ssa-structalias.c.
>>
>>
> No doubt I havent gotten there yet because it did cause a compilation
> failure :-) :-)

;)  It will only cause ICEs and miscompiles.

Richard.

> Andrew

On 04/27/2012 04:37 AM, Richard Guenther wrote:
> Since integral atomics are always of an unsigned type ,  I could switch over
> and use 'unsigned size' instead of 'tree fntype' for them (I will rename
> it), but then things may  be more complicated when dealing with generic
> atomics...  those can be structure or array types and I was planning to
> allow leaving the type in case I discover something useful I can do with it.
>   It may ultimately turn out that the real type isn't going to matter, in
> which case I will remove it and replace it with an unsigned int for size.
> So it eventually will support variable-size types?
we support arbitrary sized objects now for exchange, compare_exchange, 
load, and store. I just havent added the support to gimple_atomic yet.  
Thats next on my list.
>> And the reason memmodel is a tree is because, as ridiculous as it seems, it
>> can ultimately be a runtime value.    Even barring that, it shows up as a
>> variable after inlining before various propagation engines run, especially
>> in the  C++ templates.  So it must be a tree.
> Ick.  That sounds gross.  So, if it ends up a variable at the time we generate
> assembly we use a "conservative" constant value for it?
Indeed,  ICK,  and yes, I make it SEQ_CST at compile time if a variable 
value gets all the way through to codegen.
> Hmm, ok. So you are changing GENERIC in fact. I suppose _Atomic is 
> restricted to global variables. Can I attach _Atomic to allocated 
> storage via pointer casts? Consider writing up semantics of _Atomic 
> into generic.texi please.

Yes, I have a start on implementing _Atomic which adds the bit to the 
type.  And no, it isn't restricted to globals... it just indicates said 
hunk of memory must be accessed in an atomic manner.   You can use it on 
automatics if you want...

I believe _Atomic can also be used in casts as well.  so an atomic call 
may have to be injected into a dereference expression as well to load or 
update memory.

I'll update .texi along with the patch when I get to it.



> Well, they are calls with a very well-defined set of side-effects. 
> Otherwise not representing them as calls would be a waste of time. 
> Thus, no - they do not need to be considered "calls" everywhere (well, 
> treating them the same as calls should be conservative) but treating 
> them as "atomics" even if they were expanded as calls needs to be 
> correct. 

Yeah, I was starting with them as calls just to be conservative and get 
the same behaviour, then refine them by examining each GIMPLE_ATOMIC use 
in detail.
> Looks like a hieararchy "no target or anything else" ->  "target" ->
> "expr" ->  "memorder" would work, with only "lhs" being optional and
> present everywhere.
> Of course the hierarchy only makes sense for things that are not trees
> (I was thinking of memorder originally - but that thought fell apart).
>   So in the
> end apart from abstracting a base for FENCE the flat hieararchy makes sense
> (all but FENCE have a type / size).
Is it really worth it to have 2 different types of gimple_atomic nodes 
in order to avoid having an unused type field in atomic_fence?  
Atomic_fence has an order field, so it requires the use of op[0] in 
order for gimple_atomic_order() to work properly, we can't have all the 
other gimple nodes inherit from that, so we'd need a base which 
basically has just the KIND in it, and target/no-target nodes inherit 
from that.  So we'd have:

                     /    gimple_atomic_fence
atomic_base
                     \   gimple_atomic_all_others

then all the checks for is_gimple_atomic() have to look for both 
gimple_atomic_all_others and gimple_atomic_fence.


Perhaps a better option is to shift all the operands by one since the 
type is a tree... ie, if there is a a target, there is also a type entry, so
op[0] remains ORDER,
op[1] is the newly inserted TYPE
op[2] then becomes the TARGET,
op[3...] ,when present, are all shifted over by one.

the type can be removed from the structure and now there would be no 
wastage.  Is that reasonable?

Andrew

On 04/27/2012 04:52 AM, Richard Guenther wrote:
> hmm, yeah they always return a value.     I was just copying the gimple_call
> code...  Why would we need to do this processing  for a GIMPLE_CALL lhs and
> not a GIMPLE_ATOMIC lhs?
> GIMPLE_CALL lhs can be memory if the call returns an aggregate, similar
> GIMPLE_CALL arguments can be memory if they are aggregate.
>
> Can this be the case for atomics as well?

Ahhhh. point taken.  No.  No aggregates can ever be returned by an 
atomic, so yes, I can trim that out then.
When generic atomics are used to handle aggregates, it's all handled by 
pointer parameters and the function is usually  void, except for 
compare_exchange which returns a boolean.
>
>>    And the RHS processing is the same as for a
>> is_gimple_call as well...  it was lifted from the code immediately
>> following.,..  I tried to write all this code to return the same values as
>> would have been returned had it actually been a  built-in __sync or __atomic
>> call like we have today.  Once I had them all, then we could actually make
>> any improvements based on our known side effect limits.
>>
>> I guess I don't understand the rest of the comment about why I need to do
>> something different here than with a call...
> Well, all callers that use walk_stmt_load_store/addr_ops need to handle
> non-explicit loads/stores represented by the stmt.  For calls this includes
> the loads and stores the callee may perform.  For atomics this includes .... ?
the only implicit thing a normal atomic operation can do is load or 
store the TARGET.
When the type is an aggregate, then the EXPR (soon to be op :-) and/or 
EXPECTED field may also be loaded or stored indrectly as all the 
parameters become pointers.  When I add that code I will reflect that 
properly.
> (depends on whether the operand of an atomic-load is a pointer or an object,
> I suppose it is a pointer for the following) For atomic this includes the
> implicit load of *{address operand} which will _not_ be returned by
> walk_stmt_load_store/addr_ops.  Thus callers that expect to see all loads/stores
> (like ipa-pure-const.c) need to explicitely handle atomics similar to how they
> handle calls and asms (if only in a very conservative way).  Similar the
> alias oracle needs to handle them (obviously).
OK, I understand better :-)
>> yes, locals can do anything they want since they aren't visible to other
>> processes.  at the moment, we'll leave those fences in because we dont
>> optimize atomics at all, but  "in the fullness of time" this will be
>> optimized to:
>> int foo()
>> {
>>   atomic_fence()
>>   return 1;
>> }
>>
>> at the moment we produce:
>>
>> int foo()
>> {
>>   atomic_fence()
>>   atomic_fence()
>>   return 1;
>>
>> }
> Which is inconsistend with the alias-oracle implementation.  Please fix it
> to at _least_ not consider non-aliased locals.  You can look at the call
> handling for how to do this - where you can also see how to do even better
> by using points-to information from the pointer operand of the atomics
> that specify the memory loaded/stored.  You don't want to hide all your
> implementation bugs by making the alias oracle stupid ;)
I'm too transparently lazy obviously :-)  I'll look at it :-)
>
> All atomic operations will have a VDEF so in theory it should be fine to
> ignore.
> Ignore?  Returning 'false' would be ignoring them.  Why do all atomic
> operations have a VDEF?  At least atomic loads are not considered
> stores, are they?
very true, and neither do fences...  But we can't move any shared memory 
load or store past them, so making them all VDEFS prevents that 
activity.  Once gimple_atomic is working properly, it might be possible 
to go back and adjust places. In particular, we may be able to allow 
directional movement based on the memory order.  seq_cst will always 
block motion in both directions, but the acquire model allows shared 
memory accesses to be sunk, and the release model allows shared memory 
access to be hoisted. relaxed allows both..  We may be able to get this 
behaviour through appropriate uses of VDEFs and VUSES...  or maybe it 
will be through a more basic understanding of GIMPLE_ATOMIC in the 
appropriate places.  I will visit that once everything is working 
conservatively.

>>   There are only 2 uses:
>>   DCE already has code added to handle them, and
>>   DSE handles it through ref_maybe_used_by_stmt_p.
> Yes.  And eventually what matters for both callers should be folded into them
> (let me put that somewhere ontop of my TODO ...)
>
> For example DCE would happily remove atomic loads if they look like
>
>   result-SSA-name = ATOMIC-LOAD<ptr-SSA-name>;
>
> if result-SSA-name is not used anywhere.  And I don't see why we should
> not be allowed to do this?  Returning true from the above function will
> make DCE not remove it.
at the moment, we are NOT allowed to remove any atomic operation. There 
are synchronization side effects and the only way we can remove such a 
statement is by analyzing the atomic operations in relation to each 
other. (ie, 2 loads from the same atomic with no other intervening 
atomic operation may make the first one dead if the memory orders are 
compatible)

I will also revisit this once we have a set of operations and conditions 
upon which we can operate. It may be possible to simply remove this 
load, but for the moment it stays.  My optimization wiki page indicates 
that a dead atomic load might be removable.. I just haven't had 
confirmation from 'experts' on atomic operations yet, so I won't act on 
that yet.



>> I was simply copying the code path that was followed for gimple_call 
>> which handled the old __sync_ and __atomic builtins...  this is what 
>> that code did.  there are addresses in the atomic ops, but the 
>> functionality of those operands can dereference and store or load 
>> from those address...? ie  the generic  atomic_store (&atomic, &expr) 
>> dereferences  *expr and stores it into *atomic... 
> Sure.  But it only can ever load/store from aliased variables (not
> non-address-taken
> local automatics).  That we did not handle this for the __sync_ atomics very
> well is no excuse to not handle it well for atomics ;)
absolutely.  And Im going to be rolling all the __sync builtins as well 
eventually as well.  I was just explaining where the code came from, not 
that its optimal :-)  I'll remove the bogus loop :-)
>> These were just fillers values to get it to compile until I had time to
>> understand the proper way to find these values.  I thought there were just
>> instruction count guesses, and again mimiced what the gimple_call code did.
> Sure, still it does not make sense to account for "move" cost of the memorder
> operand the same as for the "move" cost of the eventual load/store that
> happens.  If it's a filler just fill in 'cost = 10' with a comment.
will do.
>
>>> I miss handling of GIMPLE_ATOMICs in tree-ssa-structalias.c.
>>>
>>>
>> No doubt I havent gotten there yet because it did cause a compilation
>> failure :-) :-)
> ;)  It will only cause ICEs and miscompiles.
err, I meant to say did NOT ICE.  I'll have a look at what I need in 
tree-ssa-structalias.c

Thanks
Andrew

On Fri, Apr 27, 2012 at 2:31 PM, Andrew MacLeod <amacleod@redhat.com> wrote:
> On 04/27/2012 04:37 AM, Richard Guenther wrote:
>>
>> Since integral atomics are always of an unsigned type ,  I could switch
>> over
>> and use 'unsigned size' instead of 'tree fntype' for them (I will rename
>> it), but then things may  be more complicated when dealing with generic
>> atomics...  those can be structure or array types and I was planning to
>> allow leaving the type in case I discover something useful I can do with
>> it.
>>  It may ultimately turn out that the real type isn't going to matter, in
>> which case I will remove it and replace it with an unsigned int for size.
>> So it eventually will support variable-size types?
>
> we support arbitrary sized objects now for exchange, compare_exchange, load,
> and store. I just havent added the support to gimple_atomic yet.  Thats next
> on my list.
>
>>> And the reason memmodel is a tree is because, as ridiculous as it seems,
>>> it
>>> can ultimately be a runtime value.    Even barring that, it shows up as a
>>> variable after inlining before various propagation engines run,
>>> especially
>>> in the  C++ templates.  So it must be a tree.
>>
>> Ick.  That sounds gross.  So, if it ends up a variable at the time we
>> generate
>> assembly we use a "conservative" constant value for it?
>
> Indeed,  ICK,  and yes, I make it SEQ_CST at compile time if a variable
> value gets all the way through to codegen.
>
>> Hmm, ok. So you are changing GENERIC in fact. I suppose _Atomic is
>> restricted to global variables. Can I attach _Atomic to allocated storage
>> via pointer casts? Consider writing up semantics of _Atomic into
>> generic.texi please.
>
>
> Yes, I have a start on implementing _Atomic which adds the bit to the type.
>  And no, it isn't restricted to globals... it just indicates said hunk of
> memory must be accessed in an atomic manner.   You can use it on automatics
> if you want...
>
> I believe _Atomic can also be used in casts as well.  so an atomic call may
> have to be injected into a dereference expression as well to load or update
> memory.
>
> I'll update .texi along with the patch when I get to it.
>
>
>
>
>> Well, they are calls with a very well-defined set of side-effects.
>> Otherwise not representing them as calls would be a waste of time. Thus, no
>> - they do not need to be considered "calls" everywhere (well, treating them
>> the same as calls should be conservative) but treating them as "atomics"
>> even if they were expanded as calls needs to be correct.
>
>
> Yeah, I was starting with them as calls just to be conservative and get the
> same behaviour, then refine them by examining each GIMPLE_ATOMIC use in
> detail.
>
>> Looks like a hieararchy "no target or anything else" ->  "target" ->
>> "expr" ->  "memorder" would work, with only "lhs" being optional and
>> present everywhere.
>> Of course the hierarchy only makes sense for things that are not trees
>> (I was thinking of memorder originally - but that thought fell apart).
>>  So in the
>> end apart from abstracting a base for FENCE the flat hieararchy makes
>> sense
>> (all but FENCE have a type / size).
>
> Is it really worth it to have 2 different types of gimple_atomic nodes in
> order to avoid having an unused type field in atomic_fence?  Atomic_fence
> has an order field, so it requires the use of op[0] in order for
> gimple_atomic_order() to work properly, we can't have all the other gimple
> nodes inherit from that, so we'd need a base which basically has just the
> KIND in it, and target/no-target nodes inherit from that.  So we'd have:
>
>                    /    gimple_atomic_fence
> atomic_base
>                    \   gimple_atomic_all_others
>
> then all the checks for is_gimple_atomic() have to look for both
> gimple_atomic_all_others and gimple_atomic_fence.
>
>
> Perhaps a better option is to shift all the operands by one since the type
> is a tree... ie, if there is a a target, there is also a type entry, so
> op[0] remains ORDER,
> op[1] is the newly inserted TYPE
> op[2] then becomes the TARGET,
> op[3...] ,when present, are all shifted over by one.
>
> the type can be removed from the structure and now there would be no
> wastage.  Is that reasonable?

types in ops is a bad idea (tried that once - heh), it wrecks too much generic
code.

Richard.

> Andrew

On 05/03/2012 05:59 AM, Richard Guenther wrote:
>
>> the type can be removed from the structure and now there would be no
>> wastage.  Is that reasonable?
> types in ops is a bad idea (tried that once - heh), it wrecks too much generic
> code.
>
heh, no doubt.  As I Iooked at handling the generic atomics, looks like 
Im going to restructure it anyway a bit, and it will actually match what 
you were looking for in the first place.  the generic functions deal 
with slabs of memory, so instead of a LHS, they pass in a pointer for 
the result. as well as any other values like the RHS expression value.

so now I expect to see something more along the lines of

gimple_atomic_base  { kind,  order }

gimple_atomic_target_base : gimple_atomic_base { type, target }

gimple_atomic : gimple_atomic_target_base { ops[] }

gimple_atomic_generic : gimple_atomic_target_base { return_val;  ops[] }


so FENCEs will be gimple_atomic_base,
all the rest of the normal ones will be gimple_atomic
and the generi oness will be gimple_atomic_generic

or something like that. It aint working yet so it isnt in stone and 
those are just preliminary names, but it will have a proper hierarchy of 
some sort. :-)

Andrew