/*****************************************************************************
			        Type definitions
*****************************************************************************/

/* Unit
 *
 * This is what information we need about a Unit.
 */
Type Unit {
	Int			Id;		/* Identifier */

	/* These must be lists so that we can correlate names with values */
	List<Name>		ContextVariables; /* Set of variables in context */
	List<Name>		LiveVariables;	/* Set of incoming live static
						   variables not in context */
	List<Name>		StaticVariables; /* Set of static variables known
						    following unit setup
						    computations */

	CachePolicy		Policy;		/* Cache policy */
	DAG<BB>			CFG;		/* DAG of instructions (some IR) */
	List<Edge>		Successors;	/* List of successor units */
};

/* Edge
 *
 * Abstract inter-unit edge information.
 */
Type Edge {
	Unit			Destination;
	Int			SuccessorNum;	/* which successor of the branch */
	SpecializeTime		Policy;		/* Eager or lazy */
	List<Variable>		VariablesPromoted; /* D->S promos occur on edges */
};

/* SpecializeTime
 *
 * Inter-unit edge classification.
 */
Type SpecializeTime { Eager | Lazy };

/* CachePolicy
 *
 * Whatever type of cache policy we decide to allow.
 */
Type CachePolicy {
	/* CacheAll, Cache(n), replacement policy? */
};

/* BB
 *
 * IR for a basic block.
 */
Type BB {
	List<Operation>		Operations;

	.
	. /* whatever other information is needed for codegen  */
	.
};

/* Operation
 *
 * IR for an operation.
 */
Type Operation {
	OpType			Op;
	List<Operand>		Operands;
	List<Variable>		Results;

	BindingTime		OpBT;
	List<BindingTime>	OperandBTs;
	List<BindingTime>	ResultBTs;

	.
	. /* whatever other information is needed for codegen  */
	.
};

/* BindingTime
 *
 * Per-operation and per-operand binding time annotation.
 */
Type BindingTime { Static | Dynamic };

/* Variable
 *
 * IR for a variable.
 */
Type Variable {
	Name			VariableName;
	DataType		VariableType;
	.
	. /* whatever other information is needed for codegen  */
	.
};

/* Operand
 *
 * An Operand can either be a variable or a constant.
 */
Type Operand { Variable | Value };

/* OpType
 *
 * Type of operations in the IR.
 */
Type OpType { Call | Jump | Beq | Add | ... };

/* EmitOperand
 *
 * Lists of Operands are useful for varargs.
 */
Type EmitOperand { Operand | List<Operand> };


/*****************************************************************************
		     Primitive declarations/definitions
*****************************************************************************/

/* CacheInsert
 *
 * Inserts the location of a version of a unit into the cache with the key
 * (UnitId, Context).
 */
Function CacheInsert
Input:
	Int			UnitId;
	List<Value>		Context;
	Address			UnitAddress;
	CachePolicy		Policy;
Output:
	Void
	/* side-effects the code cache */

/* CacheLookup
 *
 * Retrieves the location from the cache of the code keyed by (UnitId, Context).
 */
Function CacheLookup
Input:
	Int			UnitId;
	List<Value>		Context;
Output:
	Bool			UnitFound;
	Address			UnitAddress;

/* RequiresLookup
 *
 * Queries cache policy to determine whether a cache lookup is needed or not.
 */
Function RequiresLookup
Input:
	CachePolicy		Policy;
Output:
	Bool			Required;

/* ValueListBuild
 *
 * Constructs a list of values of the static variables listed in NewVariables.
 * The variables listed in NewVariables must be present in either the
 * OldVariables or AdditionalVariables list (but not in both).  The list
 * of values, NewValues, is then constructed from the corresponding values in
 * OldValues and AdditionalValues.
 */
Function ValueListBuild
Input:
	List<Name>		OldVariables;
	List<Value>		OldValues;
	List<Name>		AdditionalVariables;
	List<Value>		AdditionalValues;
	List<Name>		NewVariables;
Output:
	List<Value>		NewValues;

/* EmitOperation
 *
 * Emits machine instruction(s) corresponding to the specified operation.
 */
Function EmitOperation
Input:
	OpType			Op;
	List<EmitOperand>	Operands;
	List<Variable>		Results;
Output:
	Address			OperationAddr;
	/* also side-effects the writable instruction space and pointer */

/* ReduceAndReisdualize
 *
 * Residualizes the specified unit using the values of the static variables
 * provided by Context and OtherLiveVariables.  Returns the address of the
 * residual code, a list of branches to other units that require patching
 * (in the same order as Unit.Successors), and the values of all known
 * static variables (because the static variables are in SSA form, one list
 * suffices for all out edges).
 */
Function ReduceAndResidualize
Input:
	Unit			Unit;
	List<Value>		Context;
	List<Value>		OtherLiveVariables;
Output:
	Address			ResidualAddr;
	List<Address>		OutBranches;
	List<Value>		KnownStaticVariables;
	/* also side-effects the writable instruction space and pointer */

/* BackPatch
 *
 * Patch the specified branch, if needed.  Passing additional information,
 * such as jump-table location (if applicable) or information about other
 * successors, could speed up this routine.
 */
Function BackPatch
Input:
	Address			BranchAddr;
	Int			SuccessorNum;
	Address			DestinationAddr;
Output:
	Void
	/* also side-effects the writable instruction space */

/* Specialize
 *
 * Residualize the specified unit and all eager successors if the unit
 * isn't in the cache.  Emit callbacks for all lazy successors.  Callbacks
 * are spliced out, but the instruction cache need not be flushed because
 * the jump following the callback is still valid.
 */
Function Specialize
Input:
	Unit			Unit;
	Bool			Patch;
	Address			BranchAddr;
	Int			SuccessorNum;
	List<Value>		Context;
	List<Value>		OtherLiveVariables;
Output:
	Address			UnitAddr;
	/* also side-effects the writable instruction space and pointer */
{
    If (RequiresLookup(Unit.Policy)) {
        (Found, UnitAddr) = CacheLookup(Unit.Id, Context);
    } Else {
	/* If no lookup is required, we'll always generate the code */
	Found = False;
    }

    If (! Found) {
        (UnitAddr, OutBranches, KnownStaticVariables) =
            ReduceAndResidualize(Unit, Context, OtherLiveVariables);

        CacheInsert(Unit.Id, Context, UnitAddr, Unit.Policy);

        If (Patch) {
            BackPatch(BranchAddr, SuccessorNum, UnitAddr);
        }

	/* The Edge and BranchAddr lists must be correlated */
        Foreach (Edge, BranchAddr) In (Unit.Successors, OutBranches) {

            If (Edge.Policy == Eager) {

                Specialize(Edge.Destination, True,
                       BranchAddr, Edge.SuccessorNum,
		       ValueListBuild(Unit.StaticVariables, KnownStaticVariables,
				      (), (), Edge.Destination.ContextVariables),
		       ValueListBuild(Unit.StaticVariables, KnownStaticVariables,
				      (), (), Edge.Destination.LiveVariables));

            } Else {

                If (! Empty(Edge.VariablesPromoted)) {

		    /* This just takes a list of variables and produces a list
		       of their names */
		    PromotedNames = Map(Edge.VariablesPromoted, .Name);

		    /* Incorporate the promoted variables into the context */
                    CallbackAddr = EmitOperation(Call,
                            (ValueListBuild,
			     Unit.StaticVariables, KnownStaticVariables,
			     PromotedNames, Edge.VariablesPromoted,
                             Edge.Destination.ContextVariables),
                            (Variable("NewContext", List<Value>, ...)));

		    /* Generate the callback to the specializer */
                    Nil = EmitOperation(Call,
                            (Specialize,
                             Edge.Destination,
			     ! RequiresLookup(Edge.Destination.Policy),
                             BranchAddr, Edge.SuccessorNum,
                             Variable("NewContext", List<Value>, ...),
			     ValueListBuild(Unit.StaticVariables,
					    KnownStaticVariables, (), (),
					    Edge.Destination.LiveVariables)),
                            (Variable("NextPC", Address)));

                } Else {

		    /* Generate the callback to the specializer */
                    CallbackAddr = EmitOperation(Call,
                            (Specialize,
                             Edge.Destination, True,
                             BranchAddr, Edge.SuccessorNum,
			     ValueListBuild(Unit.StaticVariables,
					    KnownStaticVariables, (), (),
					    Edge.Destination.ContextVariables),
			     ValueListBuild(Unit.StaticVariables,
					    KnownStaticVariables, (), (),
					    Edge.Destination.LiveVariables)),
                            (Variable("NextPC", Address, ...)));

                }

		/* Emit the jump to the residual */
                Nil = EmitOperation(Jump, (Variable("NextPC", Address, ...)), ());

		/* Link in the callback */
		BackPatch(BranchAddr, SuccessorNum, CallbackAddr);

            }
        }
    } Else {

	/* Back-patching may be required even if we find the code in the cache */
        If (Patch) {
            BackPatch(BranchAddr, SuccessorNum, UnitAddr);
        }

    }

    Return UnitAddr;
};