local refs

[Stephen Weeks]

I think I can clear stuff up by explaining the how the thread
primitives are used.  In fact, I can even guarantee what I want with
the type system.  Let's have two types of threads: preThread and
thread.  A preThread is only ever used to create a thread (by copying)
-- it never runs.  A thread only ever runs -- it is not copied.

	    val copyCurrent: unit -> preThread
	    val copyToThread: preThread -> thread
	    val current: unit -> thread
	    val switchTo: thread -> unit

copyCurrent takes the current thread and copies it to make a
preThread.  At any later point, this preThread can be copied to create
a runnable thread.  This runnable thread can be switchTo'ed, which is,
in fact, the only primitive operation on threads.  current is only
used to get access to the current thread so it can be saved away in a
data structure.

copyCurrent can be used to implement both threads and continuations.
To implement continuations, callcc uses copyCurrent and throw uses
copyToThread followed by switchTo.  To implement threads, the library
does a copyCurrent at the beginning of the program to stash away a
baseline thread that can later be used by Thread.spawn, which will
copyToThread the baseline thread.

Hopefully, this makes clear the fact that threads cannot be copied
except by using copyCurrent, and hence the following worries
unfounded.

> Yuck.  It seems as though the presence of Thread_copy makes _every_
> program point reachable (and _dynamically_ reachable; not just forward in 
> the whole-program control flow graph, but also "backwards" along returns
> and raises) from _any_ Thread_copyCurrent has the potential for being the
> origin of multiple executions.

> This is crappy!!  Maybe I'm missing something about the semantics of
> threaded programs; do I really have the ability to make arbitrary copies
> of an executing thread, at arbitrary points (modulo where the backend will
> really put in interrupt points), and start them running?  Somebody please
> tell me it's not this bad!

BTW, there is still the usual mess with separating copyCurrent and
copyToThread into two pieces, one that does the copy, and the other
that extracts it from saved.  But that's an orthogonal issue.


Now, for other questions.

> I don't know.  See my previous e-mail -- I might have the intended
> semantics of threads all wrong.  Currently, I'm thinking in SSA, so I'm
> thinking of arbitrary uses of primitives in arbitrary SSA programs.
> You're suggesting above that "this specific case is OK" because "this is
> the only time/way it's used".

You're right, that's what I was doing, and it should be avoided if at
all possible.  Hopefully the types above avoid it.  Notice however
that we do rely on the correctness of basis library code in other
situations, e.g., in how we handle bounds checking.

> The other aspect that is missing is atomicBegin/End, which really do
> demark single-threaded portions of the program.  Of course, those are
> FFI's, so I don't know how useful they are, but it would be trivial to
> turn them into Prim.t's that are implemented as FFI's.

I'm not sure why this is relevant.  The fact that a region is atomic
does not have any connection with whether it's labels are
multiThreaded or multUse.

Here are my new rules.

Ref localization rule:
You can localize a global ref if all uses are within a single function
and the function is not multi-used.

Ref flattening rule:
A local ref can be flattened if all uses are assigns or derefs and it
all uses that are live across a call to Thread_copyCurrent are of the
same flavor.
(which I believe is your original definition, modulo terminology :-)

The reasoning behind the flattening rule is that even if blocks are
multiThreaded, because threads cannot be copied at arbitrary points, a
ref can only be shared if a copyCurrent happens in the thread after
the ref's creation.

Assuming this flattening rule is OK, then flattening should work in
programs that use threads (as MLton unfortunately still does), which
will have a call to Thread.copyCurrent at the beginning of the
program.  With the exception of possibly a couple of refs within main,
all local refs should be flattenable.  

Unfortunately, the existence of the Thread.copyCurrent at the
beginning of the program kills localization, since every label and
function (except for main) become multi-used.  One possible fix to
this would be to have a new primitive for creating a raw thread that
is only used by Thread.spawn, hence removing the copyCurrent from the
beginning of the program (leaving copyCurrent only used by callcc).
But I'm not sure offhand what that primitive should look like.  I
think I'll sleep on it.  Over and out.