\chapter{The resource variant}
\label{cha:limm-impl}


This chapter will explain the implementation of the new long immediate
encoding, the ``resource variant'', in the MOVE scheduler. During
the discussion of the implementation, various design decisions will be
explained and motivated.

First, in section~\ref{sec:internal} some basic information on the
MOVE scheduler will be discussed, so the context of the implementation
will be clear. In section~\ref{sec:proposal} the actual proposal of
new data structures and algorithms for the ``resource variant'' will
be discussed.

For an extensive reference to the MOVE scheduler's algorithms and
data structures, please read \cite{johanreport}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Internal workings of the MOVE scheduler}
\label{sec:internal}

Before we can start a discussion on the long immediate implementation,
an understanding of the compiler internals is needed. The whole
package ``MOVE compiler'' consists of several parts. Please refer to
section~\ref{sssec:sf} and in particular figure~\ref{fig:sf} to get a
broad understanding of the compiler trajectory. In the next paragraphs 
we will discuss each part of the compiler and how immediates fit in.


\subsection{GCC front-end}
The front-end of the compiler trajectory is based upon GCC,
version~2.7.0. It has been ported to a generic MOVE target. This
target is representing intermediate move assembly code, packed in a
binary format loosely based on the m68k a.out binary format. It
features a serial stream of move instructions, working on a virtual
machines that has enough registers to avoid spilling. The source field 
in the binary format is 32 bits wide, and as such the problem of
``long immediates'' is void here, as all immediates fit in the source
field of the move. Here we assume the MOVE architecture has a maximum
width of 32 bits, an assumption that holds throughout the whole MOVE
framework at this point.

The front-end does not know anything about the immediate sizes of
the target machine, and as such, can not distinguish between ``short'' 
and ``long'' immediates. This is not needed, since the front-end has
no idea on how the instruction stream will be after scheduling. The
problems stated in section~\ref{ssec:requirements} do not apply here.

It is not needed to explain the inner workings any further, it
suffices to note that the emitted binary contains the immediate in the 
source field of the move, annotated with a flag that indicates whether
the source field contains an immediate or a socket.

The a.out instruction format is the following:


{\small
\begin{verbatim}
#if HOST_LITTLE_ENDIAN
        short dst;
        char imm;	// the immediate flag
        char grd;
#else
        char grd;
        char imm;	// the immediate flag
        short dst;
#endif
        int src;
\end{verbatim}
}



\subsection{Scheduler}

For a more in-depth working of the scheduler, please
read~\cite{scheduleralg}. What will be discussed here is an overview on 
the scheduler's workings focused on the immediate support.

For a good understanding on how the Long Immediate algorithms hook in
the Scheduler, algorithm~\ref{alg:scheduler} will briefly give an
overview on the main loop of the scheduler. The algorithm iterates
through each dependency-free move in each basic block of each
procedure of the program, and will try to schedule that move. (A move
is a node in the scheduler's Data Dependency Graph). To schedule,
cycles are searched for enough resources, including units, sockets,
and buses. If all requirements are met, a schedule is successful and
a next node will be scheduled.

This is of course a gross simplification of the algorithm, but it
shows in what steps a move is scheduled. For ease of understanding,
issues like register allocation, backtracking or importing are left
out, since they're not related to the long immediate implementation.

\begin{algorithm}[htb]
\caption{Scheduler algorithm}
\label{alg:scheduler}
\begin{algorithmic}[1]
%
\FORALL{procedure in program}
\FORALL{basic block in procedure}
\STATE $switch$ (scheduling scope)
\FORALL{node = GetReadyOperation}
\STATE $switch$ (type of operation)
\FORALL{moves belonging to $node \rightarrow operation$}
\STATE compute $min\_cycle$ and $max\_cycle$ of move
\FOR{cycle = $max\_cycle$ downto $min\_cycle$}
\FORALL{units that can handle operation}
\FORALL{sockets that are connected to unit}
\STATE check various resources ({\tt FindMoveBus()})
\FORALL{movebuses connected to socket}
\STATE tentatively assign operation to this movebus
\IF{movebuses are allocatable ({\tt AssignMBusses()})}
\STATE \textbf{return} SUCCESS
\ENDIF
\ENDFOR
\ENDFOR
\ENDFOR
\ENDFOR
\ENDFOR
\ENDFOR
\ENDFOR
\ENDFOR
%

\end{algorithmic}
\end{algorithm}


%What is important to understand in the ``resource variant'', is that
%the immediate write is scheduled atomically with the immediate
%read, namely after all resource demands for the immediate read are
%met. This means that the functionality for scheduling the long
%immediate write will be put inside the most inner loop, right after
%all other resource demands are all met, i.e. right after the most
%inner ``movebuses are allocatable''.




\subsection{Simulator}

The simulator can be split in two parts: A so-called ``serial''
simulator and a ``parallel'' simulator. 

The serial simulator simulates the serial code as it was read in by
the binary reader. This is nothing more than the exact binary code
that the front-end emits. As we already discussed above, all
immediates are considered equal and ``short''. Since the serial
simulator only works on the code emitted by the front-end, unaltered
by the scheduler, the immediate problem does not apply here, just as
it didn't apply to the front-end of the MOVE compiler. All back-end
code that works with serial MOVE code, uses the MOVE code as provided
by the GCC front-end, i.e. immediates always fit in the source field.

The parallel simulator simulates the code after it has been
scheduled. It  performs a cycle-accurate simulation of the
scheduled ``VLIW''-like code. 
Algorithm~\ref{alg:simulatepar} shows the current parallel simulator
algorithm. Note that the {\tt while(not quit)} loop will be broken
when an exit statement in the code is detected and the {\tt quit} flag 
is set (in a different function).

\begin{algorithm}[htb]
\caption{SimulatePar(Proc*, int offset)}
\label{alg:simulatepar}
\begin{algorithmic}[1]
%
\STATE instruction = SkipEntryInstructions(proc,offset)
\STATE block = instruction->blck
\WHILE{{\bf not} quit}
	\FORALL{move in instruction}
		\STATE get src value from either register, immediate
			or functional unit 
		\STATE put value on movebus
	\ENDFOR
	\FORALL{move in instruction}
		\STATE get value from movebus
		\IF{register type == operand/trigger register} 
			\STATE feed value to operand/trigger register
		\ENDIF
		\IF{register type == jump/call/trap}
			\STATE set jump latency counters
		\ENDIF
	\ENDFOR
	\STATE advance functional unit pipelines with one cycle
	\STATE update jump latency counters
	\IF{one of the jump counters == 0}
		\STATE jump accordingly to address
	\ELSE
		\STATE instruction++
	\ENDIF
	\IF{end of basic block reached}
		\STATE get default successor block and make it current
		\STATE instruction = first instruction from new block
	\ENDIF
\ENDWHILE
\end{algorithmic}
\end{algorithm}


As you can see the simulator is not completely cycle-accurate because
immediates are read from the source field of the move, instead
of making a distinction between short and long immediates. Short immediates
are indeed read from the source field. Long immediates however are
read from the immediate slot that was concatenated at the end of the
instruction. Even without a new implementation, a better way to handle 
this would be decoupling the use of the immediate and the process of
reading the immediate value from the instruction stream and storing it 
in a so called ``immediate register''. This register is then read when 
the immediate is used (which is for now, always in the same cycle).


\subsection{Binary writer}

The binary writing was also developed at NEC, concurrent with the
initial work on the long immediates. Various hierarchical {\tt
OutputBinary()} functions iterate through the whole program.

{\tt OutputBinary(ostream \&, Insn *)} is the function that is
responsible for outputting instruction words. It is called for every
instruction in a basic block. This function has always included some
support for the new long immediate implementation, because it was
developed when the initial data structures were already specified.
The original algorithm of {\tt OutputBinary(ostream \&, Insn *)} can
be read in algorithm~\ref{alg:outputbin}
%The binary writer uses a so-called {\tt map} file to get parameters on 
%the the binary mapping. This {\tt map} file is generated automatically 
%from the {\tt mach} file by the {\tt mapgen} utility. The mapgen
%utility was developed after the {\tt mach} file format for long
%immediates was defined (see section~\ref{ssec:machfile}, so its
%implementation will not be discussed here.


\begin{algorithm}[htb]
\caption{OutputBinary(ostream \&, Insn *)}
\label{alg:outputbin}
\begin{algorithmic}[1]
%
\STATE allocate a {\tt BitArray} to hold the bits for this instruction 
	word
\FORALL{moves in this instruction}
	\STATE call {\tt OutputBinary(ostream \&, Move*)}
	\STATE add this slot to the list of occupied slots
\ENDFOR
\FORALL{slots not in list of occupied slots}
	\STATE encode a {\tt NOP} to this field
\ENDFOR
\end{algorithmic}
\end{algorithm}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The resource variant}
\label{sec:proposal}

In this section, the new implementation of immediates in the MOVE
framework will be discussed. Certain design decisions imposed by the
list of requirements in the previous chapter will be explained.
Basically, the following implementation method is chosen:
(figure~\ref{fig:limm-impl} illustrates this implementation)

\begin{compactenumerate}
\item Just as in the existing method, placing the immediate in the
instruction stream and using the value from the immediate register are 
decoupled. We call the former action the ``IReg Write'' (immediate
register write) or ``Immediate Define'' and the latter action the
``IReg Read'' or ``Immediate Use''.
\item The dedicated immediate slot at the end of an instruction word
can be replaced by  reserved slots for immediates
in the instruction stream. Certain move slots in the instruction word
now can either be a move, an immediate or a part of an immediate. 
\item To bookkeep this, every instruction word gets a tag, usually of
the length of a couple of bits. The tag is called Long Immediate
Control Tag, or ``LIT'' when abbreviated. This tag specifies which move slots
contain immediates and to which Immediate Register they are written
\item The new Long Immediate Control Tag logically contains a 
list of so called ``Long Immediate Micro Operations'', which basically
specifies a bit mask that indicates which move slots are occupied by
immediate bits in that cycle, and to what immediate registers these
slots are written. One LIT tag can contain multiple micro operations,
and this way a LIT can write more than one Immediate Register at a time.
\item When the Instruction Fetch Unit reads the tag, and immediates
are detected, the Unit fills the appropriate Immediate Register with
the value from the instruction word. One immediate can be constructed
out of multiple move slots. In this case, the move slots making up
that one immediate must be scheduled in the same cycle.
\item There is no need to use the immediate in the same cycle. The
Immediate Registers are part of the state of the machine.
\item When the immediate is used, the source socket will be that of
the appropriate Immediate Register, and its value will be placed 
on the move busses.
\item Although a long immediate occupies a move slot, it is not
represented in the move list of a cycle. (the move list is the data
structure that holds a list of moves per cycle in the scheduler). A
long immediate is only defined by the presence of a LIT tag at that
cycle.

\end{compactenumerate}


\begin{figure}[htb]
\centerline{\epsfbox{fig/newlimm.eps}}
\caption{Scheduling of long immediates}
\label{fig:limm-impl}
\end{figure}



\subsection{GCC front-end}
As explained in the previous section, the front-end needs no
adaptations for the new long immediate format.

\subsection{Binary reader}
The binary reader needs no adaptations either, since immediates are
processed and converted only by the scheduler. As said, all serial
MOVE code in the back-end has its immediates in the source field of
the move.

\subsection{Mach file}
\label{ssec:machfile}

The MOVE framework uses various auxiliary files during scheduling. One
of the most important ones is the {\tt mach} file, the machine
description file. This file specifies how many movebuses, how many
sockets, which functional units, etcetera, a specific instance of the
target architecture has. 

This file also specifies how many Immediate Registers the specific
architecture has. This used to be a very simple specification, because
it only had to specify the number of Immediate Registers and their
size and socket. The place in the instruction stream where the
immediate bits would end up was already determined, in a
dedicated immediate field next to the instruction word.

Now the {\tt mach} file has to specify:

\begin{compactenumerate}
\item How many immediate registers there are, together with their
sockets, size and whether they are signed or unsigned (this is
identical to the old situation)
\item The specification of the LIT tag, which indicates how Immediate
Registers are written, by means of the so called ``micro operations''.
\end{compactenumerate}

An example of the old format and the new format follow, after which a
formal specification of the new format will be presented. This example 
reflects the PcomP specification.

The old format specifies three immediate registers, and implies three
dedicated fields:
\begin{verbatim}
ImmediateUnits
{
        i1              32, signed, ir_1;
        i2              20, signed, ir_2;
        i3              20, signed, ir_3;
}
\end{verbatim}

The new format specifies the same three immediate registers, but now
the ``Control'' field specifies how these three immediate registers
can be written to, by means of an encoding in the LIT tag:
\begin{verbatim}
LongImmediate
{
 Registers:
    i0  20, signed, ir_0; 
    i1  20, signed, ir_1;
    i2  32, signed, ir_2;
 Control:
    {};
    i0 20 : { 4 };
    i1 20 : { 5 };
    i0 20 : { 4 }, i1 20: { 5 }, i2 32: {4,5};
}
\end{verbatim}






The long immediate specification is specified in the {\tt
LongImmediate} block. Inside, the following formal specification is
used:

The first part, which is similar to the existing format, is introduced
by '\texttt{Registers:}' and contains lines of the format:
\begin{verbatim}
    <ir_name><immediate_length>,<immediate_signed>,<sock_name>;
\end{verbatim}
%
the second part is introduced by '\texttt{Control:}' and contains
lines of the format:
\begin{verbatim}
    [<ir_name>:]{[<slot_num>[,...]]}[,...];
\end{verbatim}
%
the labels have the following meanings:
%
\begin{align}{immediate\_length}
\item[ir\_name]%
    A string which gives the name of the immediate register.
\item[immediate\_length]%
    An integer which indicates the length of the immediate register.
\item[immediate\_signed]%
    A member of the set \{signed,unsigned\} which indicates whether the
    immediate bits should be sign- or zero-extended to
    \emph{immediate\_length}.
\item[sock\_name]%
    The name of the socket to which the immediate register is connected.
\item[slot\_num]%
    An integer which indicates the instruction field (move slot or
    immediate reserved field) from which the immediate bits are read.  A
    comma separated list of field numbers specifies that the immediate is
    constructed by concatenating the field contents. This integer is
    counted from zero.
\end{align}


Each line of the control part can contain one or more comma-separated
elements.  An element, called \emph{micro-operation}, specifies three
things: (1) the destination immediate register, (2) a number before ':',
which specifies the number of significant bits contained in the instruction
field(s), (3) the list of fields from which the immediate bits are read.
Bits from these fields are concatenated to form one long immediate.

An important special case is the empty line, in which no immediate register 
and no field list is present.  This line represents a ``no-operation'',
whereby no immediate register is written (reserved fields are wasted, but
move slots are all available for transport programming).  An empty line
\emph{must} be present if there is more than one line in the control
part. This specifies that no immediates are written in that cycle.



\subsection{Data structures}

The MOVE scheduler uses four main data structures to hold the state of
the machine, the program and the scheduling. They will be introduced
here and the changes needed by the new long immediate implementation
are mentioned. 

For a complete reference to the changed data
structures, see appendix~\ref{app:limm-datastructures}.


\subsubsection{Mach}
The {\tt Mach} class contains the machine description. The class is
defined in file {\tt mach.h}. It completely
describes the target machine. 

\paragraph*{LImmControl}
The {\tt Mach} class is augmented with a structure called {\tt immctrl}
of type {\tt LImmControl}. This is the class that implements the tag
in each instruction that gives information on what move slots in the
novelist represent immediates or parts thereof, and whether they are
signed or not.  Its data members are:
\begin{itemize}
\item \textbf{\texttt{int slots}}, which defines the bit mask
of written slots. The {\tt int slots} member is nothing more than an
OR'd mask of individual bit masks of each Micro Operation.
\item \textbf{\texttt{ LImmMOpList mops}}, which contains a list of
Micro Operations.  
\end{itemize}

\paragraph*{LImmMOp}
Class \textbf{\texttt{ LImmMOp}} is the atomic ``Long Immediate Micro Operation''
that writes to an Ireg from a certain bit mask. Its main members:
\begin{itemize}
\item \textbf{\texttt{ nbits}}, which specifies how many bits this operation can write.
\item \textbf{\texttt{ slots}}, which contains the bit mask that specifies which
move slots contain immediates bits.
\end{itemize}

\paragraph*{IReg}
Class \textbf{\texttt{ IReg}} is the class that implements the Immediate
Register. It is amended with a data members and three member functions
to read that data.  The data member is:
\begin{itemize}
\item \textbf{\texttt{ LImmMOpList mops}}, which
lists all Micro Operations that can write to this IReg. 
\end{itemize}
The member functions are:
\begin{itemize}
\item \textbf{\texttt{ IsImmediateFits(Move*)}} and \textbf{\texttt{
IsNotImmediateFits(Move*)}}, which take a {\tt Move} and return a boolean
indicating if the immediate in that Move fits in the IReg
\item \textbf{\texttt{ LImmMOpIter~PossibleEncoding(int size)}}, which
returns a pointer to
the first micro operation that can write this IReg and encodes at
least {\tt size} bits.
\end{itemize}



\subsubsection{Prog}
The {\tt Prog} data structure holds the scheduled information of the
program. Its substructures are {\tt Proc}, {\tt Blck}, {\tt Insn} and
{\tt Move}, for respectively the procedures, the basic blocks, the
instruction words and the individual moves.

\begin{itemize}
\item We now amend the {\tt Insn}
with a pointer to one \textbf{\texttt {LImmControl}} instance, to implement the presence
of the LIT tag. This way, a scheduled instruction has the necessary
information to know which move slots are occupied by immediates by
means of the {\tt slots} member of the LImmControl class.
\item We also amend the {\tt Insn} with a list of data flow edges \textbf{\texttt{DFlow}}
of immediate uses, so we have an easy way to find the use (i.e. {\tt
IReg} read) or uses of an immediate.
\item The {\tt Move} class is augmented with a back-pointer 
to the \textbf{\texttt{Insn}} where the immediate was defined.
\end{itemize}



\subsubsection{RTabEntry}
The {\tt RTabEntry} data structure holds all resource information on each
cycle during scheduling. This includes state like occupied sockets,
move busses, immediate registers and state of the function units in
that cycle. It also provides functions to claim or release resources.

\begin{itemize}
\item The {\tt RTabEntry} structure is also amended by a
\textbf{\texttt{ LImmControl} }
pointer. This way, a cycle under scheduling has all the necessary
information on the use of immediates in that cycle.
\item Also, the {\tt RTabEntry} structure's functions that operate on
\textbf{\texttt{IReg}s} are extended so that the array that holds the
occupation of {\tt IReg}s now is implemented with a reference counter
instead of a boolean. This eases the amount of work needed if
immediate-sharing is ever implemented. Immediate-sharing means that a
long immediate is only defined once in the instruction stream and only
once written to the {\tt IReg}, but used multiple times by subsequent
reads from this {\tt IReg}. More information on this in
section~\ref{sec:immsharing}.
\end{itemize}


\subsubsection{DDG}
The {\tt DDG} is the Data Dependency Graph and holds all interrelations
between moves and basic blocks during scheduling. A move is
represented by the class {\tt Node} and a basic block is represented
by the class {\tt SNode}. Since we have implemented the long
immediates as nothing more than a presence of a LIT tag, there is no
need to change the {\tt Node} or {\tt SNode} classes.





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Scheduler algorithms}

Now that we have all extensions to the data structures explained, we
will explain the modifications made to the existing algorithms and we
will discuss all new algorithms. As stated in the list of
requirements, our goal was to interfere as less as possible with the
existing algorithms. This is done mainly by two design decisions:

\begin{compactenumerate}
\item All scheduling of long immediates is done after the long
immediate use is scheduled. The last step in scheduling a move is
finding a movebus for it. So in {\tt FindImmMoveBus} we add the hook
that will schedule the IReg Write.
\item All operations performed on the list of moves in a cycle do not
know about the presence of a long immediate, since it is not in the
move list at all. It turns out the only place where allocation of moves 
into slots is done is during the {\tt Marriage} function (which is
called from {\tt RTabEntry::AssignMBusses()}). This function is called
with a testing-flag, which is true when this function is called during 
scheduling and false when this function is called after scheduling,
during placement. By replacing the real move list (implemented by the
{\tt cand} mask and {\tt nmoves} index) with a pseudo list that
includes bit masks for long immediates, we have a atomic and
stand-alone way to check for resource requirements of movebuses.
\end{compactenumerate}

The rest of this section will discuss the algorithms used during
scheduling and unscheduling.

%A complete reference of all relevant procedures can be found in
%Appendix~\ref{app:limm-alg}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Scheduling}

The main algorithm associated with the long immediate implementation
is the immediate write scheduling algorithm. We will present all 
algorithms and helper functions here.

The name ``resource variant'' already indicates that immediates are not
represented by (pseudo-)moves but only by a resource claim in the {\tt
RTabEntry} table. An immediate in the serial code (e.g. {\tt
\#456~->~add\_o}) is split in half: {\tt i??~->~add\_o} (the immediate
use) and {\tt
\#456~->~i??} (the immediate write)~\footnote{{\tt \#456} here
represents an arbitrary immediate larger than the maximum size for a
short immediate, and {\tt i??} represents an arbitrary immediate
register}.

This split will be made in the inner-most loop of the scheduling
algorithm, which is {\tt FindImmMoveBus()}

The overall algorithm is presented first in
algorithm~\ref{alg:overallsched}, after which various parts will be
explained in detail. This algorithm can be compared to
algorithm~\ref{alg:findimmmovebus} and differs from it in the
following ways: After the resources on the immediate register are
checked, and a possible move bus allocation (with the candidate mask
relating to the chosen immediate register), there is not commit yet,
but a tentative assignment. From that point, a cycle from the current
cycle down to cycle zero is searched in which the immediate bits can
be written. For each cycle on in that write-read (def-use) chain, the
resources on the immediate registers are checked, and a check for a
suitable encoding is checked. The latter is done by tentatively
assigning a new LIT tag and see if the movebuses in that cycle are
still allocatable, as well as a check if all existing immediate writes 
in that cycle are still preserved. If all these checks succeed, the
immediate write and immediate use are declared ``final'', and the
function will return ``success'' on the schedule of that immediate.



\begin{algorithm}[htb]
\caption{Overall scheduling of long immediates}
\label{alg:overallsched}
\begin{algorithmic}
%
\STATE FindImmMoveBus()
\STATE try to fit immediate in src field as short immediate
\IF{{\bf not} fits} %// try to schedule a long immediate
\FORALL {iregs}
\STATE assign socket of ireg to source socket
\STATE check resources on ireg
\IF{possible allocation for immediate use found}
	\STATE tentatively claim resources for immediate use
	\FOR{this cycle downto mincycle}
		\STATE check if ireg is still free
		\STATE check if encoding is available
		\STATE tentatively assign LIT tag
		\IF{movebuses allocatable}
			\STATE commit schedule of immediate use and write
			\STATE {\bf return} SUCCESS
		\ENDIF
	\ENDFOR
\ENDIF
\ENDFOR
\ENDIF
\STATE {\bf return} FAILURE

\end{algorithmic}
\end{algorithm}


The implementation for this algorithm has been coded in 5 functions:

\begin{compactenumerate}
\item {\tt FindImmMoveBus}, taking care of the search for an Immediate 
Register and claiming all resources for the immediate use.
\item {\tt ScheduleLImm}, taking care of iterating through the cycles
and checking on ireg resources in cycles between the read and write of 
the immediate.
\item {\tt FindIRegWriteBus}, taking care of tentatively assigning a
LIT tag and claiming the Immediate Registers in the path between the
read and write of the immediate.
\item {\tt IsLImmControlValidSubset} which can determine if a
tentatively assigned LIT tag indeed encodes all bits needed for the
immediates currently under scheduling {\em and} still encodes
immediates that were already scheduled in that cycle
\item {\tt RTabEntry::AssignMBusses}, a function now extended with
functionality that makes sure that long immediate fields also are
taking into considerations when a move list is mapped on move buses.
\end{compactenumerate}

We will now go into detail on each of these 5 functions.

\paragraph*{FindImmMoveBus}
In {\tt FindImmMoveBus()} an immediate register is chosen and {\tt
ScheduleLImm} is called. If this returns with a success return code,
the immediate register is claimed and scheduling is successful.
The pseudo code is can be read in algorithm~\ref{alg:findimmmovebusnew}.

\begin{algorithm}[htb]
\caption{FindImmMoveBus(move, cycle)}
\label{alg:findimmmovebusnew}
\begin{algorithmic}
%
\STATE try to fit immediate in src field as short immediate
\IF{{\bf not} fits // try to schedule a long immediate }
\FORALL {ireg}
\STATE replace src\_sock with socket of ireg
\STATE check resources on ireg
\IF{possible allocation for immediate use found}
	\STATE add ireg to list of possible iregs
\ENDIF
\ENDFOR
\FORALL {iregs in possible-iregs-list}
	\STATE tentatively claim resources for immediate use
	\STATE call ScheduleLImm
	\IF{ ScheduleLImm succeeds}
		\STATE make iregs resource claim permanent
		\STATE {\bf return} SUCCESS
	\ENDIF
\ENDFOR
\ENDIF
\end{algorithmic}
\end{algorithm}

\paragraph*{ScheduleLImm}

The {\tt ScheduleLImm} function is responsible for iterating through
all cycles in order to find a suitable cycle for the immediate write,
i.e. a cycle where the immediate bits can be encoded. To check if a
certain cycle is suitable, it first checks if the Immediate Register
that was chosen is still available and then checks if the resources
for the immediate write by calling {\tt FindIRegWriteBus}.
The pseudo code for this algorithm can be found in
algorithm~\ref{alg:schedulelimm}.

\begin{algorithm}[htb]
\caption{ScheduleLImm(read\_node, ireg)}
\label{alg:schedulelimm}
\begin{algorithmic}
%
\FOR{cycle = read\_node->cycle downto zero}
	\IF {ireg in this cycle is busy}
		\STATE {\bf return} FAILURE
	\ENDIF
	\IF {FindIRegWriteBus succeeds}
		\STATE {\bf return} SUCCESS
	\ENDIF
\ENDFOR
\STATE {\bf return} FAILURE

\end{algorithmic}
\end{algorithm}



\paragraph*{FindIRegWriteBus}

The function {\tt FindIRegWriteBus} takes care of choosing a suitable
LIT tag. It can do this by upgrading an already existing LIT to one
that encodes the micro operations as specified by the existing LIT as
well as the micro operation that can write to the immediate register
currently under scheduling. It does this by means of the function {\tt 
IsLImmControlValidSubset}. If these tests all succeed, it tentatively assigns 
that LIT tag to the cycle and checks if all the movebuses are still
allocatable. If all this succeeds, this function returns a success
return value. 
The pseudo code for {\tt FindIRegWriteBus} can be found in
algorithm~\ref{alg:findiregwritebus}.

\begin{algorithm}[htb]
\caption{FindIRegWriteBus(write\_cycle, read\_cycle, ireg)}
\label{alg:findiregwritebus}
\begin{algorithmic}
%
\IF{current LIT already writes this ireg (as a side effect)}
	\STATE {\bf return} FAILURE
\ENDIF
\FOR{all micro operations that write this ireg and can encode enough
	bits for this immediate}
	\STATE fetch the accompanying LIT tag
	\IF{{\bf not} IsLImmControlValidSubset}	
		\STATE {\bf continue} with next micro operation
	\ELSE
		\STATE tentatively assign new LIT tag
		\IF{move buses are allocatable // call AssignMBusses}
			\FOR{cycle = write\_cycle downto read\_cycle}
				\STATE claim RTabEntry->ireg
			\ENDFOR
			\STATE {\bf return} SUCCESS
		\ELSE
			\STATE revert to old LIT tag
		\ENDIF
	\ENDIF
\ENDFOR
\STATE {\bf return} FAILURE

\end{algorithmic}
\end{algorithm}


\paragraph*{IsLImmControlValidSubset}

The function {\tt IsLImmControlValidSubset} is perhaps one of the  
trickier algorithms discussed here. It takes three arguments, two LIT
tags and an immediate register.
It has two tasks. One is to check if a certain LIT tag can encode all
immediate registers that another LIT tag can encode, plus the
immediate register passed to the function.
The other one is its dual, namely to check if a certain LIT tag can
encode all immediate registers that another LIT tag can encode, {\em
except} the immediate register passed to the function. 
Both tasks can be done by the same function, and you can get the
dual function by swapping the two LIT tags on the argument list.
Pseudo code for {\tt IsLImmControlValidSubset} can be found in
algorithm~\ref{alg:islimmcontrolvalidsubset}.

\begin{algorithm}[htb]
\caption{IsLImmControlValidSubset(LIT super, LIT sub, ireg cur)}
\label{alg:islimmcontrolvalidsubset}
\begin{algorithmic}
%
\FORALL{iregs}

\IF{this ireg is not written by sub}
	\IF{this ireg is written by super}
		\IF{this ireg is the ``cur'' ireg {\bf and} this ireg
		    is busy}
			\STATE {\bf return} FAILURE // super LIT defines too much
		\ELSE
			\STATE {\bf continue} // this is the ireg
					that was supposed to be added
		\ENDIF
	\ELSE
		\STATE {\bf continue} // this ireg is not involved at
					all
	\ENDIF
\ELSE 
\STATE // this ireg is written by sub
\IF{this ireg is not written by super}
	\STATE {\bf return} FAILURE // super LIT is not a superset
\ELSE
	\STATE // current ireg is written by both LITs
	\IF{the micro operations from both the super and the sub LIT
		can encode the same number of bits}
		\STATE {\bf continue} // this ireg has passed the
					compliance test
	\ENDIF
\ENDIF
\ENDIF
\ENDFOR 

\STATE // at this point we have checked all iregs for compliance
\STATE // and they all passed
\STATE {\bf return} SUCCESS


\end{algorithmic}
\end{algorithm}




\paragraph*{AssignMBusses}

The member function {\tt RTabEntry::AssignMBusses} is responsible for 
checking if a certain set of moves, together with their constraints on 
connectivity of their sockets to move buses, can be mapped on the move 
buses. For this, it uses the ``Marriage'' algorithm, also known as the
``Bi-partite Graph Matching Algorithm''.

Each move in the move list has a mask that indicates which move buses
it can be scheduled on. (this is because normally, a MOVE processor has 
no full connectivity between sockets and move buses.)

In the original situation, one would call the marriage function with
the graph of edges between move buses and moves, and see if one can
find a bi-partite mapping of this graph.

The problem we now have is that long immediate writes, although not
part of the move list, do occupy slots in the instruction word, or
equivalently, buses on the transportation network. For this, the {\tt
AssignMBusses} function is extended with a small routine that
temporarily adds a mask for each long immediate write, thus creating a 
``pseudo move'', before calling the marriage function. 

Since the mask for this slot only contains the slot itself, this will
be the only mapping  the ``Marriage'' function can find. The
result is that the Marriage function cannot map any other move on this 
bus anymore, which is exactly the desired behavior.

After the marriage function is called, these ``pseudo moves'' are
removed, in order to restore the original move list and masks.

The new pseudo code for this function can be found in
algorithm~\ref{alg:assignmbusses}.

\begin{algorithm}[htb]
\caption{AssignMBusses(RTabEntry)}
\label{alg:assignmbusses}
\begin{algorithmic}
%
\FORALL{move buses}
	\IF{move bus is in the {\tt slots} list of the LIT tag}
		\STATE add mask with this bus to the set of mask
		\STATE increment the number of moves in this list
	\ENDIF
\ENDFOR
\STATE perform the marriage function
\STATE restore the old move list

\end{algorithmic}
\end{algorithm}






\subsubsection{Unscheduling}
During scheduling, it is possible that the scheduler needs to come
back on previous decisions to schedule. During bypassing, for
instance, the bypassed node is declared ``dead'', or ``killed'', but
if the bypass doesn't succeed in the end, that node needs to be
declared  ``unkilled''.


\paragraph*{KillNode}
The process of unscheduling nodes is done by the function {\tt
KillNode()} Normally, unscheduling a node involved releasing all
resources occupied by that node. Note that although resources in the
{\tt RTabEntry} table are released, but all information on these
resources is still preserved in the data members of the {\tt
Move}. These data members include the {\tt cand} mask for the
movebuses, the {\tt src\_sock} and the {\tt dst\_sock} and finally the
{\tt ireg} which indicates what Immediate Register was used. The
process of unscheduling nodes is done by the function {\tt KillNode()}

The extension made to {\tt KillNode()} is that, instead of just releasing
the Immediate Register in the current cycle, we also look up where the
immediate write was performed and we release all resources (LIT tag,
immediate register claims) related to this immediate read.
For this, we define a helper function {\tt LookupIRegWrite}.


\paragraph*{LookupIRegWrite}

The function {\tt LookupIRegWrite} will find a defining cycle for a
given ireg, and will optionally release all resources associated with
this immediate read. It can be views as the dual of {\tt
FindIRegWriteBus}. 

It will do this by iterating through the cycles from the read node
downwards. We release (if asked) all immediate registers found, until
we find a cycle that has a LIT tag that writes to the immediate
register in question. At that point, we (if asked) downgrade the LIT
tag to another tag that still writes to all immediate registers that
the original did, except for the immediate register that is being
released. Here we can profit from the dual functionality of {\tt
IsLImmControlValidSubset}.

The pseudo code for {\tt LookupIRegWrite} can be found in
algorithm~\ref{alg:lookupiregwrite}. The algorithm takes as
in-arguments the ireg that needs to be released, the read-node and a
boolean that indicates whether we are only looking up the write or
that we are actually releasing all resources associated with this
ireg. The function returns the {\tt snode} (basic block) and the cycle 
where the LIT tag was found.

\begin{algorithm}[htb]
\caption{LookupIRegWrite(read-node, bool release, cycle, snode)}
\label{alg:lookupiregwrite}
\begin{algorithmic}
%
\STATE write-cycle = cycle
\FOR{cycle = write-cycle downto zero}
	\IF{release}
		\STATE release ireg in this cycle
	\ENDIF
	\FORALL{micro ops from LIT tag in this cycle}
		\IF{this micro op writes to the ireg}
			\STATE we found the defining cycle
			\FORALL{LIT tags}
				\IF {IsLImmControlValidSubset(current LIT, new LIT, ireg)}
					\STATE assign new LIT
					\STATE {\bf return} SUCCESS
				\ENDIF
			\ENDFOR
			\IF{no suitable LIT tag to downgrade found}
				\STATE {\bf abort} // this cannot
							happen
			\ENDIF
		\ENDIF
	\ENDFOR
\ENDFOR
\IF{no defining cycle found yet}
	\STATE {\bf abort} // this cannot happen
\ENDIF


\end{algorithmic}
\end{algorithm}







\paragraph*{UnkillNode}

Because killed moves are simple marked ``dead'', but not actually
removed from the schedule, it's very easy to reschedule
deleted nodes. The function {\tt UnkillNode()} just claims back all
resources used by the {\tt Move} to be unkilled in the
corresponding {\tt RTabEntry()}. 

A relevant problem of the new long immediate encoding is that it
makes immediate registers a multiple-cycle resource, like general
purpose registers, and multiple-cycle resources are more difficult to
manage. When the
def-use chain of the immediate write and use are killed, a release 
of the resources implicates that all information on where the
immediate write was scheduled is lost.

That's why {\tt UnkillNode()} has to completely reschedule the long
immediate write by calling {\tt ScheduleLImm()}. The scheduler
requires that any node that has been marked ``dead'' can be
successfully unkilled, this means that this call to
{\tt ScheduleLImm()} can not fail. Fortunately, this is impossible,
since it the state of resources between a {\tt KillNode()} and an {\tt
UnkillNode()} will not change.

Scheduling will be aborted when {\tt ScheduleLImm()} fails, but
this has never been observed in any benchmark, so it is assumed that
the assumption in the previous paragraph holds.



\subsection{Simulator algorithms}
During the discussion of the working of the simulator it became clear
that only the parallel simulator needs adaptation.
The parallel simulator function {\tt SimulatePar()} was extended with
a global array {\tt ireg[]} that represents the state of the Immediate 
Registers. For each cycle this array contains the values of the
various Immediate Registers. The algorithm is also changed:

\begin{compactenumerate}
\item At the beginning of each cycle, a check for a LIT is done, and
if found, the {\tt ireg[]} array is filled with the appropriate
values. This concludes the ``immediate write'' stage.
Actual values of immediates are found by following the {\tt DFlw
iruses} field of the {\tt Insn}. Since this is the exact same way that 
we build the binary in the binary writer stage, this method represents 
a valid way of looking up actual immediate values.
\item During the processing of each move, when an immediate source is
detected, the original action was to put the value of the src-field of 
that move on the movebus. This behavior is still valid for long
immediates, since the internal representation stores the value of the
immediate in the source field,
even if the socket related to that src-field now is an immediate
register socket. We now split this case in two separate cases: If the
immediate is a short immediate (no presence of a {\tt move->ireg}
pointer), we just copy the value of the src-field to the movebus; but
if the immediate was a long immediate, the appropriate value from the
{\tt ireg[]} array is read and put on the movebus. This concludes the
``immediate read'' stage.
\end{compactenumerate}

Because the only architectural visible change to the system was the
presence of Immediate Registers, the adaptation to the parallel
simulator was very straightforward.

The changes to the algorithm are explained in
algorithm~\ref{alg:parsimnew}, please refer to
algorithm~\ref{alg:simulatepar} for the original algorithm.


\begin{algorithm}[htb]
\caption{SimulatePar(Proc*, int offset)}
\label{alg:parsimnew}
\begin{algorithmic}[1]
%
\STATE instruction = SkipEntryInstructions(proc,offset)
\STATE block = instruction->blck
\WHILE{{\bf not} quit}
	\STATE {\em write immediate bits from long immediate 
		fields in {\tt ireg[]}}
	\FORALL{move in instruction}
		\IF{\em move is a long immediate read}
			\STATE {\em get src value from {\tt ireg[]}}
		\ELSE
			\STATE get src value from either register or
				functional unit 
		\ENDIF
		\STATE put value on movebus
	\ENDFOR
	\FORALL{move in instruction}
		\STATE get value from movebus
		\IF{register type == operand/trigger register} 
			\STATE feed value to operand/trigger register
		\ENDIF
		\IF{register type == jump/call/trap}
			\STATE set jump latency counters
		\ENDIF
	\ENDFOR
	\STATE pass ``clock pulse'' to functional units
	\STATE update jump latency counters
	\IF{one of the jump counters == 0}
		\STATE jump accordingly to address
	\ELSE
		\STATE instruction++
	\ENDIF
	\IF{end of basic block reached}
		\STATE get default successor block and make it current
		\STATE instruction = first instruction from new block
	\ENDIF
\ENDWHILE
\end{algorithmic}
\end{algorithm}




\subsection{Binary writer}

The binary writer's classes need to be extended with functionality for
writing the LIT tag at the beginning of the move instruction word, and 
with functionality for filling move slots with actual bits if this
move slot contains immediate bits.

The {\tt mapgen} utility  checks the {\tt mach}-file for Long
Immediates and extends the size of an instruction word to accommodate
for dedicated immediate fields, i.e. immediate fields that are not
shared with the normal move slots.


The initial version of {\tt OutputBinary(ostream \&, Insn *)}
first allocates a {\tt BitArray} that represents the instruction word
and uses {\tt OutputBinary(ostream \&, Move *, BitArray \&)} to fill all 
move slots. After that, it fetches the {\tt LImmControl} tag from the
current {\tt Insn}. The functionality is extended by an algorithm that
will compute which move slots actually contain immediate bits and it
will fill those fields with the value from {\tt insn->iruses} (the
list of pointers to the moves that this instruction encodes immediate
bits for).
The new  {\tt OutputBinary(ostream \&, Insn *)} will be shown in
algorithm~\ref{alg:outputbinnew}. Please compare to the original
implementation as shown in algorithm~\ref{alg:outputbin}.


\begin{algorithm}[htb]
\caption{OutputBinary(ostream \&, Insn *)}
\label{alg:outputbinnew}
\begin{algorithmic}[1]
%
\STATE allocate a {\tt BitArray} to hold the bits for this instruction 
	word

\STATE // we first encode all long immediate bits in the {\tt BitArray}
\FORALL{iruses pointers in this instruction}
	\STATE look up value to be encoded from src field in
		iruses->move
	\STATE look up slots that write this ireg in this cycle
	\STATE add slots to the list of occupied slots
	\STATE encode bits into instruction stream.
\ENDFOR		


\FORALL{moves in this instruction}
	\STATE call {\tt OutputBinary(ostream \&, Move*)}
	\STATE add this slot to the list of occupied slots
\ENDFOR
\FORALL{slots not in list of occupied slots}
	\STATE encode a {\tt NOP} to this field
\ENDFOR 
\end{algorithmic}
\end{algorithm}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
