property lists

Matthew Fluet fluet@CS.Cornell.EDU
Wed, 29 Nov 2000 23:46:25 -0500 (EST)


> Also, I've changed the implementation and interface for properties.
> There are now two independent choices to make when creating a property. 
>        1. Do you want it to be destructable (yes or no).
>        2. How do you want it to be assignable (not at all, set once, or set).
> So, there are now 6 different possible ways of creating a property.  The
> reason for all of this mess is that there are performance implications to
> make a property destructable (an extra list element) and performance
> implications to make it assignable more than once (an extra ref cell). 
> So, if at all possible, you should choose to make your property not
> destructable and not assignable, or at the worst assignable but not
> destructable. 

I've been trying to choose the best property type for the different lists
that I create.  I've gotten rid of a couple of destroys and scaled a few
back to SetOnce.  I'm still a little unsure of whether or not I should
leave some of these other properties as destructable or not.  Here's the
overall situation:

The translate phase creates a property mapping block labels to a live
variable list.  I've made this property non-destructable, because the
processing of each chunk needs to update this property.  Also, I've made
it SetMultiple, because the live variable list needs to be updated during
the simplify phase (footnote on this below).

The simplify phase creates a number of different properties, each mapping
block labels to some value.  The caveat here is that the simplify phase
only processes a chunk at a time, so each time these properties are
created, they are associated with (almost) disjoint sets of labels.  These
are the properties that I think should be destructable, because I can't
just iterate over all the blocks at the end of the simplify phase and
clear the properties of the labels, because that would clear the live
variables list, which is needed for processing other chunks.

Then I have a short answer question: for a property that I know needs to
be updated multiple times, is it better to make it SetNone or SetOnce and
make the value a ref  or  is it better to make it SetMultiple?


The footnote on the live variable lists:  In reality, because a chunks are
processed one at a time, the live variable lists are never fully
initialized until the final chunk is translated, by which time all the
other chunks have been emitted.  This isn't really a problem, because no
temporaries are live across chunks, so the default empty list is actually
correct when one chunk asks for the live variables at the beginning of a
block in another chunk.  

Second footnote:  The live variable lists are updated during the simplify
phase when I verify that the all of the liveness information is correct.
Previously, I hadn't needed to do this, I just assumed that the values
filled in in backend.fun were correct.  (Steve and I wrestled with this at
the end of the summer when we first added the liveness calculation to
backend.fun.  It's correct, although in some cases it overly conservative,
claiming that variables are live into a block when they don't need to be.)
However, after adding overflow checking, I introduce new blocks without
having any idea what's live into or out of those blocks.  Therefore, I had
to compute the liveness at least at these blocks, and I figured I would
verify and fix any other blocks at the same time.  If overflow checking is
off, then 90% of the time, it's just verification.  But some programs
(including a self-compile) do require some clean-up to actually get the
correct live variables.  This is unfortunately a somewhat expensive
operation, taking more than a quarter of the total time spent in the
simplify phase.  (But, I've been working on optimizing it, so it's down to
about half the time it was previously.  Actually taking the fixed point in
a more intelligent way with working lists, etc. will probably speed it up
a bit more.)