[cpp-threads] Alternatives to SC (dependency-based)

[Paul E. McKenney]

On Mon, Jan 29, 2007 at 09:11:30PM -0800, Hans Boehm wrote:
> 
> On Mon, 29 Jan 2007, Paul E. McKenney wrote:
> 
> > > 2) I do not believe that any ordering constraints based on dependencies
> > > are viable at this level.  I agree that they would be useful.  But all
> > > attempts at definition have failed, typically because they end up
> > > imposing compilation constraints on compilation units that do not
> > > use atomics.  Peter and I have been through long discussions of this
> > > that are in the archives.  I will try to post a summary shortly.
> > > The nice thing about atomics with acquire and release ordering constraints
> > > is that none of this matters.  (This does not mean that dependency-based
> > > oredring is useless at the machine level.  It is critical for implementing
> > > Java final fields.  But there the compiler knows what it's doing and
> > > the dependency doesn't span compilation units.  The JSR133 effort
> > > arrived at a similar conclusion for explicit dependency-based ordering.)
> >
> > I am OK with requiring the programmer to mark dependencies that matter,
> > as is done via rcu_dereference() usage in the Linux kernel.  Then any
> > unmarked dependency is the compiler's to do with as it will.
> >
> > Does this work for you?
>
> I think that marking the original load doesn't help much, since
> it already needs to be marked as atomic in this world.

On all machines but Alpha, all the compiler need do is to fetch *r1 only
once.  It can spill the value of *r1 to a local temporary as Doug suggested
in an earlier email, but it cannot refetch from *r1.  On Alpha, the compiler
also needs to emit at least an rmb() (LoadLoad in SPARC parlance).

> I haven't thought very much about making something like this work
> in environments in which the dependent reference is limited to a
> field of the object returned by the first load.  In general, it's
> at least nearly impossible to define what constitutes a dependent
> load.  Is the second load in
> 
> if (*r1) r2 = *r3
> 
> (everything starting with r is a local "register" variable) dependent
> on the first?

An admittedly simple-minded way to proceed is to refuse to hoist any
part of the "rt = *r3" before the load from *r1, and additionally as
noted above to avoid refetching *r1.

>               If so, how about
> 
> if (*r1) r2 = *r3; else r2 = *r3;
> 
> ?

The same thing applies, right?  Fetch *r1, on Alpha do a memory barrier,
then do "r2 = *r3".  If *r1 is marked, you don't get to optimize it away.
Of course, if these were all normal variables, the compiler could simply
do "r2 = *r3", dropping the reference to *r1 completely.

						Thanx, Paul