********************************************************************************
********************************************************************************
********************************************************************************

To: spin-comp@thistle.cs.washington.edu
Subject: Context & Caching
Date: Wed, 01 Oct 1997 10:02:41 PDT
From: Brian Grant <grant@thistle.cs.washington.edu>

There is a significant problem with the way we compute the cache context
in the PEPM paper.  Variables with the CacheOneUnchecked cache policy
(including all derived static variables) do not contribute to the cache
context.  However, it is possible that the root variables from which some of
these variables are derived are not in the cache context.  That is, they
have been dropped from the StaticVarInfo set because they are no longer live,
though they are still represented in the Division.  It must be the case 
for any derived static variable that either it is in the context or its
root(s) are.

There are numerous possible solutions to this problem.

1) Keep the root variables in the context; don't filter a root variable from
   the StaticVarInfo if any static variables are derived from it.  This
   requires us to keep track of the TEMPs from which all static variables
   are derived, in addition to which VARs (which is all we currently track).
   This distinction between TEMPs and VARs wasn't made in the PEPM paper
   because it is a Multiflow implementation detail.

2) Put derived static variables in the context: transfer the strongest cache
   policy of the root variables to each derived variable.  This intuitively
   seems like the right thing to do: include exactly the variables we
   specialize on in the cache context.  However, it makes it difficult to
   determine where unit boundaries should fall.  The cache context would grow
   at nearly every static operation.

3) Kill derived static variables when their roots are removed from the
   StaticVarInfo.  Given our experience with UsedVars, I expect this would
   kill nearly all of the derived static variables, so it is definitely out.

What I propose for the long term is a scheme that is more complicated than
these, but has the potential to be more efficient because it passes more
information to GEgen.  In the near term, I suggest we implement #1.

Why did we exclude derive static variables from the cache context?  We were
hoping to save the cost of including them in the cache lookup.  This cost is,
roughly, a load and an add.  However, if we have to pass the value of a root
variable that is not live, that cost is a store and a load.  This observation
is what drives my long-term proposal:

In the BTA:
-- Transfer the strongest cache policies of the roots to derived static
   variables, as in option #2 above, but mark them so that GEgen can tell that
   they are derived.
-- Keep track of root TEMPs as in #1 above.
-- Save the cache policies of root variables (TEMPs) removed from the
   StaticVarInfo; e.g., these roots can be put in a RootVarInfo set.  A root
   stays in this set as long as there are TEMPs derived from it in the
   StaticVarInfo.

In GEgen:
-- Derived static variables all of whose root variables are in StaticVarInfo
   can be given the cache policy CacheOneUnchecked and excluded from the
   cache context.
-- Determine unit boundaries the same way we do now; that is, ignore derived
   variables for the purpose of determining significant context changes
-- Find the optimal set of variables to include in the context given that
   root variables are somewhat more expensive than derived variables (store vs.
   add):
	- Build a graph with weighted nodes for dead roots and their derived
	  variables, connecting each derived variable to its root.
	- Find a vertex cover of minimal weight (ok, so this is NP hard); this
	  cover is the set of variables to include in the cache context at the
	  unit boundary.

This isn't quite right, however, since once a root variable is excluded from
a context, it can't be used in downstream contexts because its value will be
lost.  I'll think about that later (much later)...

Detail you can ignore:
We may need to save the cache policies and roots of demoted variables at the
point where they are demoted in case we need to construct a context at the
where a live static variable is made dynamic.

--Brian