property lists

[Stephen Weeks]

> 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).

Should the live variable list be a property at all?  If it lives throughout the
whole backend maybe it should be a record element in the block record.

> 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.

This would be solved if you made the live variable list a record element.
Another possibility -- one thing that is missing somewhere between
nondestructable and destructable -- call it "removable" -- where you get a
remove operation that removes a particular property from a list without clearing
the whole list.  Then you don't have to pay the extra cost for destructable.  If
you want this, let me know and I'll add it.  It's trivial to do so.

> 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?

That's all setMultiple does is introduce the ref wrapper, so either way is
fine.

> 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.)

Shoot.  If you let me know where it's still conservative, I'll look into it.

> However, after adding overflow checking, I introduce new blocks without
> having any idea what's live into or out of those blocks.

Could you explain a bit more about how this can happen?

> 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.

I'd like to get to the bottom of this, because we're spending a *huge* fraction
of compile time in the backend's allocate registers and the code generator's
simplify phases in computing live variables.  It's a shame to duplicate work.

> 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.)

It's near the top of my todo list to speed up the allocate registers pass.  I'll 
let you know if I learn anything when I do it.