property lists

[Matthew Fluet]

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

Maybe we can move it to the block record.  Currently, backend.fun
calculates the variables live into a block.  But, to actually compute the
liveness of a block, I need to know all the variables live out of the
block; or equivalently, the union of all the variables into all of its
targets.  Initially, I figured I would just property list the live
variables and always be able to get at them.  But, as I think about it a
little more, in the translation from Machine.Block.T to
MachineOutput.Block.T, all the live variables have been calculated, and I
could there use a short lived property list (because theres no reason not
to clear the property lists between the backend and x86-codegen phases) to
fill in a liveOut record in the MachineOutput.Block.T. 

This would be definitely worth pursuing if we hammer out conservative live
in calculations.

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

I know it occurs in a self-compile.  I haven't bothered printing out
warnings when this happens in a while, so I don't know offhand.  But I'll
set up a regression/benchmark test with warnings and let you know where I
see it happening.

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

Sure.  Consider a really simple block from MachineOutput:

L: RI(5) = Int_addCheck(RI(0), RI(2))
   SI(4) = Int_addCheck(RI(5), RI(4))
   jump

and I know that RI(0), RI(2) and RI(4) are live into L, from backend.fun.

At translation into pseudo-x86, this becomes:

L: movl RI(0), OFCT
   addl RI(2), OFCT
   IFF {condition = Overflow,
        true = (handler),
        false = Overflow1}

noOverflow1:
   movl OFCT, RI(5)
   movl RI(5), OFCT
   addl RI(4), OFCT
   IFF {condition = Overflow,
        true = (handler),
        false = Overflow2}

noOverflow2:
   movl OFCT, SI(4)
   jump

So, this is straight translation, before any optimizations.  

For an Int_addCheck, do the add into this overflow check temporary (to
deal with the case I was talking about a few weeks ago: 
SI(4) = Int_addCheck(SI(4), SI(8)),
but if the "pre-add" SI(4) is used in the handler, then I can't do the
add into SI(4)).

The IFF is one of the abstractions of transfers; it branches on a
condition code set by the previous instruction.

So the essential issue is that at translation, I don't know what are the
live variables into or out of noOverflow1.

Recall that during translation, I break up the MachineOutput.Block.t's
into multiple other blocks.  The main occurences are at limitChecks and
array allocation loops.  The nice thing about both of those types of block
breakups was that no psuedo-regs were live across them, so there wasn't
anything to worry about.  Unfortunately, the Int_XChecks are different in
that respect.  I've observed (I don't know if it's a guarantee) that the
handler of the Int_XCheck never has any variables live in.

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