\chapter{Long immediates review}
\label{cha:limm-review}

This chapter will evaluate the implementation of long immediates as
described in chapter~\ref{cha:limm-impl}. This will be done by means
of a quantitative benchmark which will evaluate instruction count and
code size . Also, this chapter will present a comparison with an
equivalent, independent, implementation of long immediates. Lastly,
motivations and guidelines for future work on the long immediates
support are given.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Performance review}

This section will give a quantitative review of the ``resource
variant''. First, an overview on the used benchmark suite and the
machine descriptions are given. Then, the actual data is presented in
several graphs. Subsection~\ref{ssec:datareview} will draw some
conclusions from the gathered results.

\subsection{The benchmark suite}

The implementation was tested with four different machine
configurations. The relevant parts of those machine descriptions can be
found in appendix~\ref{app:machs}. A quick overview on the specifics
of these mach files:

\begin{compactenumerate}
\item {\tt mach.pcomp}, the PcomP architecture for which this
implementation was written originally. It features 6 buses, and 3
immediate registers. Two 20-bit immediate registers can be written in
the same cycle via slot 4 and 5, or one 32-bit immediate register can
be written via a concatenated slot 4 and 5. (note that slots are
counted from zero, so slot 4 and 5 are the two most significant
buses).
\item {\tt mach.one}, the PcomP architecture with only 1 32-bit
immediate register, which is written from slot 5
\item {\tt mach.small}, a small architecture with 3 buses and 1 32-bit 
immediate register.
\item {\tt mach.big}, an architecture with 8 buses and 2 independent
32-bit immediate registers.
\end{compactenumerate}

These 4 machine descriptions were benchmarked against the new
``resource variant'' and against the old implementation with dedicated
move slots. For the old implementation, the same number of dedicated
move slots were added to the machine description as the number of
immediate registers in the new variant. The benchmark suite consists
of the following benchmarks:

\begin{itemize}
\item arfreq
\item g722main
\item music
\item radproc
\item edge
\item expand
\item flatten
\item smooth
\item cjpeg
\item djpeg
\item go
\item compress
\item m88ksim
\end{itemize}

The tests were conducted to measure the code-size, measured in number
of instructions. This means that in the new implementation, the number 
of instructions will increase, since normally a dedicated
immediate slot was used, where now the immediates are scheduled in the 
instruction stream itself. But since the dedicated slots are not
needed anymore, the instruction-word size will decrease. Therefore
also the multiplication of number of instructions and the
instruction-word size is presented. This metric gives a real
indication of the achieved improvement in terms of program memory
savings.


The exact metrics of the 4 machine descriptions are presented in
table~\ref{tab:machsizes}.


\begin{table}[htb]
\begin{center}
\small
\begin{tabular}{|l|r|r|r|r|r|}
\hline
{} & {\bf number of } & {\bf move slot } &
		   {\bf } & {\bf dedicated } & 
	   	   {\bf total width incl. }\\
{\bf mach file} & {\bf move slots} & {\bf width} &
		   {\bf total width } & {\bf  fields} & 
	   	   {\bf  ded. fields}\\

\hline\hline
{\tt mach.pcomp} & 6 & 20 & 120 & 32 & 152\\
{\tt mach.one}   & 6 & 20 & 120 & 32 & 152\\
{\tt mach.small} & 3 & 32 & 96  & 32 & 128\\
{\tt mach.big}   & 8 & 32 & 256 & 64 & 320\\
\hline
\end{tabular}
\end{center}
\caption{Metrics of machine descriptions}
\label{tab:machsizes}
\end{table}


\subsection{The results}


The four tables~\ref{bench:pcomp}~to~\ref{bench:big} will show the
instruction count increase, and the total code-size when the
instruction count is multiplied by the instruction word length in
bits. Both sets of measurements are also presented relative to the old
implementation.  Each table shows the results for one machine
description. Note that not all benchmarks are represented in each
machine description. Since the MOVE framework is a project still in
development, not all benchmarks could complete correctly. In that case
that benchmark is removed from the suite for that machine description.

\clearpage

\begin{table}[htb]
\begin{center}
\small
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
{}              & {\bf old} & {\bf old} &
		  {\bf new} & {\bf new} &
		  {\bf relative} & 
		  {\bf relative}\\
{\bf benchmark} & {\bf instr.count} & {\bf codesize} &
		  {\bf instr.count} & {\bf codesize} &
		  {\bf instr.count} & 
		  {\bf codesize}\\
\hline\hline
arfreq      &  988   & 150176 & 1005  & 120600 & 101.72 & 80.30\\
g722main    &  4057  & 616664 & 4214  & 505680 & 103.87 & 82.00\\
music       &  4085  & 620920 & 4163  & 499560 & 101.91 & 80.45\\
radproc     &  2613  & 397176 & 2675  & 321000 & 102.37 & 80.82\\
edge        &  4192  & 637184 & 4332  & 519840 & 103.33 & 81.58\\
expand      &  3926  & 596752 & 4029  & 483480 & 102.62 & 81.01\\
flatten     &  3269  & 496888 & 3373  & 404760 & 103.18 & 81.45\\
smooth      &  2950  & 448400 & 3067  & 368040 & 103.96 & 82.07\\
cjpeg       &  8409  & 1278168& 8556  & 1026720& 101.75 & 80.32\\
djpeg       &  9824  & 1493248&  9996 & 1199520& 101.75 & 80.32\\
%go         &  40860 & &       & & & \\ 
compress    &  3571  & 542792 & 3696  & 443520 & 103.50 & 81.71\\
%m88ksim    &  11989 & &       & & & \\
\hline
{\bf averages}& & & & & 102.72\% & 81.10\% \\  
\hline
\end{tabular}
\end{center}
\caption{{\tt mach.pcomp } benchmark results}
\label{bench:pcomp}
\end{table}


\begin{table}[htb]
\begin{center}
\small
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
{}              & {\bf old} & {\bf old} &
		  {\bf new} & {\bf new} &
		  {\bf relative} & 
		  {\bf relative}\\
{\bf benchmark} & {\bf instr.count} & {\bf codesize} &
		  {\bf instr.count} & {\bf codesize} &
		  {\bf instr.count} & 
		  {\bf codesize}\\
\hline\hline

arfreq	&	984	&	149568	&	997	&	119640	&	101,32	&	79,99	\\
%g722main&	4097	&	622744	&		&	0	&	0	&	0	\\				
%music	&	4092	&	621984	&		&	0	&	0	&	0	\\				
radproc	&	2617	&	397784	&	2658	&	318960	&	101,56	&	80,18	\\
edge	&	4255	&	646760	&	4354	&	522480	&	102,32	&	80,78	\\			
expand	&	4004	&	608608	&	4023	&	482760	&	100,47	&	79,32	\\			
flatten	&	3330	&	506160	&	3360	&	403200	&	100,90	&	79,65	\\			
smooth	&	3001	&	456152	&	3040	&	364800	&	101,29	&	79,97	\\			
cjpeg	&	8425	&	1280600	&	8511	&	1021320	&	101,02	&	79,75	\\			
djpeg	&	9855	&	1497960	&	9979	&	1197480	&	101,25	&	79,94	\\			
go	&	41035	&	6237320	&	41618	&	4994160	&	101,42	&	80,06	\\			
compress&	3602	&	547504	&	3661	&	439320	&	101,63	&	80,24	\\
m88ksim	&	12060	&	1833120	&	12155	&	1458600	&	100,78	&	79,56	\\		
\hline
{\bf averages}& & & & & 101.27\% & 79.95\% \\  
\hline
\end{tabular}
\end{center}
\caption{{\tt mach.one } benchmark results}
\label{bench:one}
\end{table}

\clearpage

\begin{table}[htb]
\begin{center}
\small
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
{}              & {\bf old} & {\bf old} &
		  {\bf new} & {\bf new} &
		  {\bf relative} & 
		  {\bf relative}\\
{\bf benchmark} & {\bf instr.count} & {\bf codesize} &
		  {\bf instr.count} & {\bf codesize} &
		  {\bf instr.count} & 
		  {\bf codesize}\\
\hline\hline

arfreq	&	1160	&	148480	&	1237	&	118752	&	106,64	&	79,98	\\
%g722main&	5367	&	686976	&		&	0	&	0,00	&	0,00	\\
%music	&	5895	&	754560	&		&	0	&	0,00	&	0,00	\\
%radproc&	3101	&	396928	&	2844	&	273024	&	91,71	&	68,78	\\
%edge	&	5599	&	716672	&		&	0	&	0,00	&	0,00	\\
expand	&	4947	&	633216	&	5250	&	504000	&	106,12	&	79,59	\\
flatten	&	4209	&	538752	&	4600	&	441600	&	109,29	&	81,97	\\
smooth	&	3943	&	504704	&	4270	&	409920	&	108,29	&	81,22	\\
cjpeg	&	11042	&	1413376	&	11517	&	1105632	&	104,30	&	78,23	\\
%djpeg	&	12549	&	1606272	&		&		&	0,00	&	0,00	\\
%go	&		&		&		&		&		&		\\
compress&	4357	&	557696	&	4638	&	445248	&	106,45	&	79,84	\\
%m88ksim&		&		&		&		&		&		\\
\hline
{\bf averages}& & & & & 106.85\% & 80.14\% \\  
\hline
\end{tabular}
\end{center}
\caption{{\tt mach.small } benchmark results}
\label{bench:small}
\end{table}


\begin{table}[htb]
\begin{center}
\small
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
{}              & {\bf old} & {\bf old} &
		  {\bf new} & {\bf new} &
		  {\bf relative} & 
		  {\bf relative}\\
{\bf benchmark} & {\bf instr.count} & {\bf codesize} &
		  {\bf instr.count} & {\bf codesize} &
		  {\bf instr.count} & 
		  {\bf codesize}\\
\hline\hline

arfreq	&	1078	&	344960	&	1082	&	276992	&	100,37	&	80,30	\\
g722main&	4503	&	1440960	&	4550	&	1164800	&	101,04	&	80,83	\\
music	&	4676	&	1496320	&	4693	&	1201408	&	100,36	&	80,29	\\
radproc	&	2852	&	912640	&	2844	&	728064	&	99,72	&	79,78	\\
edge	&	5190	&	1660800	&	5245	&	1342720	&	101,06	&	80,85	\\
expand	&	4689	&	1500480	&	4810	&	1231360	&	102,58	&	82,06	\\
flatten	&	4041	&	1293120	&	4162	&	1065472	&	102,99	&	82,40	\\
smooth	&	3745	&	1198400	&	3823	&	978688	&	102,08	&	81,67	\\
cjpeg	&	9112	&	2915840	&	9199	&	2354944	&	100,95	&	80,76	\\
%djpeg	&	10561	&	3379520	&		&	0	&	0,00	&	0,00	\\
go	&	46043	&	14733760&	46339	&	11862784&	100,64	&	80,51	\\
compress&	4103	&	1312960	&	4115	&	1053440	&	100,29	&	80,23	\\
%m88ksim&	13713	&	4388160	&		&	0	&	0,00	&	0,00	\\


\hline
{\bf averages}& & & & & 101.10\% & 80.88\% \\  
\hline
\end{tabular}
\end{center}
\caption{{\tt mach.big } benchmark results}
\label{bench:big}
\end{table}

\clearpage


\subsection{Conclusions}
\label{ssec:datareview}

From the benchmarks we can observe the following:

\begin{itemize}
\item The instruction count increases in the new implementation. This
is expected behavior, since now the immediates have to take up space
normally occupied by moves.
\item The average increase is about 1 to 3\% for fairly large
architectures. This number is relatively low, since the average share
of immediate-moves in the instruction stream is much higher than
that. This means that most immediates were encoded in unoccupied
move slots. This is also backed by the fact that in fairly large
machines, with e.g. 6 buses, the last 2 or 3 buses only achieve a
utilization of about 20\%. 
\item The {\tt mach.small} architecture, with only 3 buses, has to
take a 6\% increase in cycle count. The move bus
utilization is much higher or efficient in small
architectures. Therefore immediates cannot always be scheduled in
unoccupied slots and extra instructions have to be added.
\item Since the immediates now are scheduled in the move slots,
the dedicated move fields can go away. This results in an
average of a 20\% shorter instruction word. This can also be observed
from table~\ref{tab:machsizes}. Since the average instruction count
increase is relatively low, the effective gain of this implementation
is the removal of the dedicated move fields.
\end{itemize}

We can finally conclude that the ``resource variant'' implementation
of the long immediates in the MOVE framework has resulted in an
implementation where there is a clean hook for scheduling immediates
in the code, without cluttering the code base with extra support for
immediates in various parts of the code. The main hook where the
implementation comes into play is in {\tt FindImmMoveBus}. The
quantitative results indicate that the average increase in cycle count
is relatively very low compared to the number of moves that have an
immediate in its source field. This increase in cycle count is
completely overshadowed by the reduction in code size since we do not
need a dedicated move field anymore. The real efficiency gained thus
is a 1\% increase in execution time against a 20\% (average) decrease
in code size. Especially in environments where MOVE is deployed,
e.g. embedded systems, the emphasis lies on the code size and not so
much on the execution time.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Future work}
\label{sec:future}

The design space of Long Immediates in MOVE is not completely exhausted
yet. Also, other tools, like {\tt explore} can benefit from a long
immediate implementation. These issues will be discussed in this
section. 

\subsection{Exploration}
{\tt explore} is a tool that evaluates different machine
configurations in order to come up with an optimal (cost/performance
wise) MOVE configuration for a certain application. A short
introduction into optimization of a move configuration through
exploration is given in chapter~\ref{cha:move} and especially
section~\ref{sec:optimizer}. 

Since long immediates are part of the real MOVE configuration now,
instead of the old implementation of fixed fields alongside the
instruction word, exploration should evaluate different long immediate
combinations.

Since the design of long immediates in MOVE is so extremely flexible,
an implementation of long immediates in {\tt explore} should be
designed very carefully. The design space is quite large:

\begin{compactenumerate}
\item Different move slots can be used as immediate bit field
\item Move slots can be concatenated to form larger immediates
\item Different immediate registers can write to different move slots
\item A certain cycle can combine various writes to immediate
registers
\end{compactenumerate}

Because of all these degrees of freedom, an enormous design space can
be evaluated. During an implementation, a designer should carefully
choose with degrees of freedom are useful for
exploration. Quick-and-dirty tests can probably reveal which changes
in the machine configuration have a big impact and, as such, will be
suitable for exploration.



\subsection{Immediate sharing}
\label{sec:immsharing}

Immediate sharing is the concept of writing to an immediate register
once, and reading from that immediate register many
times. Figure~\ref{fig:limm-sharing} tries to visualize this.

Currently, the algorithms are designed in such a way, that an
immediate write and read are coupled together. The scheduling
algorithm schedules the read (a {\tt i0~->~dst} move), after which a
suitable slot, where the immediate will be written to an immediate
register, will be found. The check whether an immediate register
resource is available is done through the functions{\tt
RTab::IsBusy(IReg*)} and {\tt RTab::IsFree(IReg*)}. Currently, these
functions will return a notion of ``busy'' if the immediate register
resource is occupied. 

Already implemented, however, is the function {\tt RTab::IsBusy(IReg*, 
int val)}, which will return a notion of ``free'', even if the
immediate resource is busy, but the {\tt val} value matches the value
already in the immediate register. This way, resource checking by
means of {\tt RTab::IsBusy(IReg*, int val)} provides a way to share
immediates in immediate registers. 

The functions {\tt RTab::Claim(IReg*)} and {\tt RTab::Release(IReg*)}
both have provisions for immediate sharing. Instead of a boolean value 
that indicates ``busy'', a reference counter is used.

As can be seen, the data structures and functions are already suited
for a long immediate sharing implementation. What is needed is
adaptation of the main algorithms to take advantage of this. 

\begin{figure}[ht]
\centerline{\epsfxsize=10cm \epsfbox{fig/limmsharing.eps}}
\caption{Sharing of long immediates}
\label{fig:limm-sharing}
\end{figure}

To get an idea how effective sharing of long immediates is, the
following test was conducted: Every time a long immediate is tried for 
a schedule, a call to {\tt RTab::IsBusy(Ireg*, int val)} is done. A
counter was kept how many time this call returned ``false'', while the 
actual value in the immediate register was the same as the immediate
value under schedule. This counter effectively counts the number of
times that immediate sharing was possible. Another counter tallied the 
total number of tries for immediate sharing. These two counters give
an idea of the frequency of possible immediate sharings. The result
for an extensive benchmark consisting of 30 tests resulted in an
overall frequency of about 0.5\% to 1.0\%. 



\subsection{Region scheduling of immediates}

Region scheduling is the concept of moving moves to predecessor
blocks, in order to take advantage of possible empty slots in those
predecessors. For more information on region scheduling, also known as 
interbasicblock scheduling, see \cite{cor:phd} and \cite{jan:phd}.

Region scheduling normally applies automatically to moves. Immediate
writes are not real moves, however, but nothing more than a resource
occupied, and accounted for by the Long Immediate Tag. This makes it
impossible for the scheduler to transparently ''import''~\footnote{the
concept of placing moves in predecessor blocks} immediate writes in
predecessor blocks.
Figure~\ref{fig:limm-import} visualizes the concept of importing long
immediates.
However, an algorithm analogous to the already existing import
routines can be developed for the immediate writes.

The function {\tt ScheduleLImm()} is responsible for finding a
suitable cycle. Normally a loop from a certain {\tt max\_cycle} down
to cycle zero tries to find a suitable cycle. If we reach cycle zero,
and no suitable cycle is found, {\tt ScheduleLImm()} returns {\tt
false}. Instead of returning false, code analogous to {\tt
SchedulOp()} and {\tt SchedulOp2()} can be constructed: If no suitable 
cycle is found, try to import the immediate write in all predecessors
of the current block.

\begin{figure}[ht]
\centerline{\epsfxsize=10cm \epsfbox{fig/importlimm.eps}}
\caption{Importing of long immediates}
\label{fig:limm-import}
\end{figure}

To get an idea how effective importing could be, the following test
was conducted: Every time a long immediate is tried for schedule, a
counter is incremented every time the main loop in {\tt ScheduleLImm}
(see algorithm~\ref{alg:schedulelimm}) fails. This means the loop hit
the ceiling of a basic block, after which importing to predecessors
could be deployed. Another counter keeps the total number of tries for
immediate sharing. These two counters give an idea of the frequency of
importing possibilities. The result for an extensive benchmark
consisting of 30 tests, done with various machine descriptions and
various benchmarks, resulted in an overall frequency of 5\% to
10\%. This means that in 5 to 10 percent of the cases a schedule in
that basic block with that specific set of sockets, immediate
registers and move buses failed. Most probably another combination 
of those sockets, immediate registers and move buses could be
scheduled correctly, without the need to resort to importing. This
observation is backed by the fact that usually in over 75\% of the
immediate schedules, the write is scheduled in the same cycle as the
read, keeping the immediate register only busy for that one cycle.


\subsection{Conclusions}

Although the immediate implementation could still be extended, tests
show that the extra efficiency achieved by implementing ``importing''
and ``sharing'' of immediate writes seem low compared to the already
achieved benefits obtained by removing the dedicated move
slots. The implementation of long-immediate exploration in the 
{\tt explore} tools however will be a valuable addition to the
framework, since this will give the designer the ability to make an
architecture description that is as optimal as possible. For instance, 
an extra immediate register might boost performance by enabling the
scheduling of more than one immediate in one cycle, but one has to
consider the fact that in hardware this register might be expensive. 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{The pseudo-move variant}
\label{cha:pseudo}

The long immediate implementation as discussed in the previous
chapters (the ``resource variant'') is not the only implementation
done on the MOVE framework. Parallel to this implementation, primarily
driven by the PcomP architecture (see chapter~\ref{cha:introduction}),
TNO-FEL had a need for its own implementation. This section will
discuss the motivation behind that implementation, and a brief
overview of it. This implementation, dubbed the ``pseudo-move''
variant will be compared to the ``resource variant'' implementation,
both qualitative, by comparing the algorithms and drawing conclusions,
and quantitatively, by benchmarking both implementations.


\section{Implementation}

The implementation discussed in this report has an important paradigm: 
``Try to make the implementation as stand-alone as possible, so existing 
code won't have to be changed a lot.'' This decision was made because
the current source of the scheduler was considered to be quite
difficult to understand in the short amount of time that was
available. Also, because of many non-documented inter-dependencies of
data structures in the source, at first sight obvious changes to the
scheduler might result in bugs in completely different parts of the
scheduler. That this assumption didn't hold in the end, can be read in 
chapter~\ref{cha:conclusions}.

The implementation of TNO-FEL used another paradigm: ``Implement as
obvious as possible, in order to get the implementation done quick,
even if that means making changes to various fundamental
data structures''.



Basically, the ``pseudo-move'' implementation is the following:
\begin{compactenumerate}
\item Before scheduling, transform a move containing an immediate in a 
separate operation that writes to a virtual register, and a move that
reads this virtual register instead of the immediate directly. A data
dependency is then added to link the two operations. Note that while
the ``immediate read'' move still is a real move,  the ``immediate 
write'' move is a pseudo move, since it doesn't represent a real
transport during execution, but merely an encoding of bits.
\item A new operation {\tt IMMEDIATE} is defined, as well as the flags 
{\tt IMMEDIATE} and {\tt LONG\_IMMEDIATE} for the {\tt Node} and {\tt
Move} classes.
\item During scheduling, the operation {\tt IMMEDIATE} is handled on
the same level  as other classes  of operations like {\tt COPY},  {\tt
OPERATION}, {\tt JUMP}  and {\tt CALL}. The  moves  that make up  this
operation; at least   one immediate write  and  exactly one  immediate
read; are  all treated  as real  moves, appearing  in move   lists and
eligible for optimizations like importing.
\item The last step is performed after scheduling and will distribute
the bits of the immediate over all ``immediate write'' moves, so the
binary writer knows what bits to write to what fields. Interesting
detail is that also the ``immediate write'' move can store a couple
of bits in the unused opcode field of the ``immediate register''
address.

\end{compactenumerate}

Figure~\ref{fig:pseudomove} will visualize the transformation of the
moves. {\tt i0} here represent any immediate register, since this will 
change during scheduling anyway. {\t r33} here represent any virtual
register. Later on, this virtual register will be assigned to a real
register by the register allocator.

\begin{figure}[h]
\centerline{\epsfxsize=8cm \epsfbox{fig/pseudomove.eps}}
\caption{Transformation to immediate operation}
\label{fig:pseudomove}
\end{figure}


This is all implemented via a couple of routines in the scheduler
source and a new machfile format.
The machfile format is altered to incorporate the movebus where the
immediate bits of that particular immediate register are read from,
and it is augmented with a field that specify how many immediate bits
can be stored in the source field of the ``immediate use''
move. Although that source field contains the encoding for an
immediate register, e.g. ``i0'', this immediate register has no
further opcode specifications, so some bits remain available for
immediate bits. An example of an old and a new section of {\tt
ImmediateUnits} is the following:

Old format:
\begin{verbatim}
ImmediateUnits
{
  i0  16, signed, i0_r;
}
\end{verbatim}

New format:
\begin{verbatim}
ImmediateUnits
{
  i0  16, signed, {m2,m3}, 3, i0_r;
}
\end{verbatim}

As you can see, the new format specifies in what move slot the
immediate bits are written (in this case from slots that server
movebus {\tt m2} and {\tt m3}), and an integer specifying how many
immediate bits can be stored in the opcode field of the source field
of the immediate use (in this case 3 bits).


Algorithm~\ref{alg:buildlongimmediates} will show how a
move containing immediate bits is converted into a new operation, the
original move and a data dependency between them.
The {\tt BuildLongImmediates} is called for every move during the
computation of the the data flow information in routine {\tt
ComputeDFlowInfo}.


\begin{algorithm}
\caption{BuildLongImmediates (*Move)}
\label{alg:buildlongimmediates}
\begin{algorithmic}[1]
%
\STATE // compute the number of slots needed for this immediate 
\FORALL{move slot}
	\IF{move slot can contain immediate bits}
		\STATE increment nr\_of\_slots\_needed
		\STATE decrement immediate with width of move
				slot
	\ENDIF
	\IF{immediate width reaches zero}
		\STATE {\bf break}
	\ENDIF
\ENDFOR
\STATE // make the new operation
\STATE make new r\_move and r\_insn
\STATE set r\_move to {\tt org\_guard:i0->free\_virtual\_register}
\STATE set r\_move to ``IMMEDIATE RESULT'' type
\STATE add r\_move to r\_insn
\STATE insert r\_insn to current block
\FORALL{nr\_of\_slots\_needed}
	\STATE make new i\_move and i\_insn
	\STATE set i\_move to {\tt org\_guard:imm\_val->i0}
	\STATE set i\_move to ``LONG IMMEDIATE'' type
	\STATE add i\_move to i\_insn
	\STATE insert i\_insn to current block
\ENDFOR
\STATE // link both operations together
\IF{original move was a ``COPY'' move}
	\STATE bypass now, delete original move completely
\ELSE
	\STATE clear ``IMMEDIATE'' flag from original move
	\STATE set source field of original move to the free virtual register
	\STATE add data flow dependency between r\_move and the original move
		via the virtual register
\ENDIF
\end{algorithmic}
\end{algorithm}

During scheduling, the routines {\tt ScheduleInterBasicBlock} and {\tt 
ScheduleIntraBasicBlock} are responsible for dispatching to schedule
functions based on the operation type. We know have a new operation,
the immediate operation. Every operation is scheduled from its
``hook'', for a normal operation the trigger move, and in this case
the ``immediate write'' move. If the two dispatch routines encounter
such a move, they will dispatch to a new routine, {\tt
ScheduleLongImmediate}. The {\tt ScheduleLongImmediate} routine and
its helper routines are based on the {\tt ScheduleOperation}
routines. The analog of the trigger move is the ``immediate read''
move and the analog of the operand moves are the pseudo moves that
represents the ``immediate write''. Now normal scheduling of the new
operation can proceed.


After scheduling, a routine called {\tt AssignLongImmediates} is
called. This routine is responsible for assigning parts of the
bitfields of an immediate to the various ``immediate write'' pseudo
moves \emph{and} to the empty opcode-field bits of the ``immediate
register'' source field of the ``immediate read'' move. The
``immediate'' moves have a special field {\tt imm\_val} for this
purpose, which is used during binary write when the actual bits are
written into the binary stream.
Algorithm~\ref{alg:assignlongimmediates} will give an overview of this
algorithm.

\begin{algorithm}
\caption{AssignLongImmediates}
\label{alg:assignlongimmediates}
\begin{algorithmic}[1]
%
\FORALL{procedures in program}
\FORALL{long immediate operations in procedure}
	\FORALL{moves in this operation}
		\IF{move is an immediate read move}
			\STATE assign bits to ireg opcode field (write 
				value of bits in the {\tt imm\_val} field)
			\STATE adjust remaining immediate value by shifting
		\ENDIF
		\IF{move is an immediate write move}
			\STATE calculate maximum number of bits that
				this move slot can contain
			\STATE assign bits to this move slot (write
				value of bits in the {\tt imm\_val} field)
			\STATE adjust remaining immediate value by
				shifting
		\ENDIF
	\ENDFOR
\ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}



\section{Qualitative comparison}
\label{ssec:pseudo-qual}

The advantages of this implementation over the ``resource variant'' 
are:

\begin{compactenumerate}
\item Since the immediate writes are real moves, they can be treated
as such by the scheduler.
\item Importing of immediate writes to other basic blocks is possible.
\end{compactenumerate}

The disadvantages of the ``pseudo move'' implementation are:

\begin{compactenumerate}
\item This solution adds one more move to the list of move than the
``resource variant''. This disadvantage can be canceled out if the
move from the original operation is bypassed by the immediate write
in the ``immediate operation''.
\item The ``resource variant'' has more flexibility in the writing of
immediate registers, since the {\tt mach} file format has been altered 
a lot to accommodate for a wide range of possible encoding formats,
specified by the LIT tag.
\item Sharing of immediate values is not possible in the ``pseudo
move'' variant.
\end{compactenumerate}

The next subsection will evaluate both implementations, showing
whether above mentioned advantages and disadvantages are indeed proven 
right.


%These considerations can be evaluated to draw some conclusions on the
%performance between the two implementations. They will be either
%confirmed or denied by the real benchmarks, performed on the two
%implementations, in section~\ref{ssec:pseudobenchmark}
%FIXME bad paragraph above

\section{Quantitative comparison}
\label{ssec:pseudobenchmark}

The two implementations ``resource variant'' and ``pseudo-move
variant'' are both benchmarked against the same suite. This suite is a
subset of the suite used for the evaluation of the
implementation. Only three mach-files were taken into consideration
and the set of benchmarks was not as extensive as in the ``resource
variant'' review.
Only instruction counts were taken into account, since
the codesize reduction due to the dedicated immediate fields is the
same for both
implementations. Tables~\ref{comp:pcomp}~to~\ref{comp:small} will give
the results between both implementations and a relative figure that
indicates which implementation achieves a lower instruction-count
increase. Since the two code bases are otherwise very different, it is
unwise to try to compare the raw instruction counts. For instance, the
compiler used to implement the ``resource variant'' has much more
bug fixes and is developed further than the compiler used to implement
the ``pseudo-move variant''. Other than that, the compiler parameters
were kept the same as much as possible. Used options include
``interbasicblock scheduling'', ``early'' register allocation, and a
machine format with at least 32 general purpose registers and a fully
connected transportation network. For the machfiles, see
appendix~\ref{app:machs}.



The tables consist of the following columns:
\begin{compactenumerate}
\item The instruction counts of the ``resource variant'', both
without (old) and with (new) long immediate implementation
\item The instruction counts of the ``pseudo-move variant'', both
without (old) and with (new) long immediate implementation
\item Relative increase in instruction count for both the ``resource
variant'' and the ``pseudo-move'' variant.
\end{compactenumerate}

\clearpage


\begin{table}[htb]
\begin{center}
\small
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
{}              & {\bf old resource} & {\bf new resource} &
		  {\bf old ps.-move} & {\bf new ps.-move} &
		  {\bf resource relative} & 
		  {\bf ps.-move relative}\\
{\bf benchmark} & {\bf instr.count} & {\bf instr.count} &
		  {\bf instr.count} & {\bf instr.count} &
		  {\bf instr.count} & 
		  {\bf instr.count}\\
\hline\hline
arfreq	&	991	&		1014	&	1166		&		1168		&	102.32	&	100.17	\\
edge	&	4338	&		4453	&	3852		&		3971		&	102.65	&	103.09	\\
flatten	&	3554	&		3616	&	3695		&		3751		&	101.74	&	101.52	\\
smooth	&	3216	&		3273	&	3138		&		3212		&	101.77	&	102.36	\\
cjpeg	&	8571	&		8749	&	9192		&		9318		&	102.07	&	101.37	\\
\hline
{\bf averages}& & & & & 102.11\% & 101.70\% \\  
\hline
\end{tabular}
\end{center}
\caption{{\tt mach.pcomp } comparison}
\label{comp:pcomp}
\end{table}



\begin{table}[htb]
\begin{center}
\small
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
{}              & {\bf old resource} & {\bf new resource} &
		  {\bf old ps.-move} & {\bf new ps.-move} &
		  {\bf resource relative} & 
		  {\bf ps.-move relative}\\
{\bf benchmark} & {\bf instr.count} & {\bf instr.count} &
		  {\bf instr.count} & {\bf instr.count} &
		  {\bf instr.count} & 
		  {\bf instr.count}\\
\hline\hline
arfreq	&	993	&		1014	&	1166		&		1166		&	102.11	&	100.00	\\
edge	&	4390	&		4432	&	3870		&		3939		&	100.95	&	101.78	\\
flatten	&	3593	&		3606	&	3670		&		3695		&	100.36	&	100.68	\\
smooth	&	3222	&		3239	&	3111		&		3151		&	100.52	&	101.29	\\
cjpeg	&	8590	&		8678	&	9187		&		9271		&	101.04	&	100.91	\\
\hline
{\bf averages}& & & & & 101.37\% & 100.93\% \\  
\hline
\end{tabular}
\end{center}
\caption{{\tt mach.one } comparison}
\label{comp:one}
\end{table}



\begin{table}[htb]
\begin{center}
\small
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
\large
{}              & {\bf old resource} & {\bf new resource} &
		  {\bf old ps.-move} & {\bf new ps.-move} &
		  {\bf resource relative} & 
		  {\bf ps.-move relative}\\
{\bf benchmark} & {\bf instr.count} & {\bf instr.count} &
		  {\bf instr.count} & {\bf instr.count} &
		  {\bf instr.count} & 
		  {\bf instr.count}\\
\hline\hline  
\small
arfreq	&	1160	&		1249	&	1313		&		1346		&	107.67	&	102.51	\\
edge	&	5677	&		6086	&	5136		&		5384		&	107.20	&	104.82	\\
flatten	&	4500	&		4804	&	4589		&		4795		&	106.75	&	104.49	\\
smooth	&	4215	&		4492	&	4041		&		4242		&	106.57	&	104.97	\\
cjpeg	&	11146	&		111696	&	11924		&		12447		&	104.93	&	104.39	\\
\hline
{\bf averages}& & & & & 106.63\% & 104.24\% \\  
\hline
\end{tabular}
\end{center}
\caption{{\tt mach.small } comparison}
\label{comp:small}
\end{table}




\section{Conclusions}

Several conclusions can be drawn from the previous two subsections. 

\begin{itemize}
\item Both implementation yield about the same increase in cycle
count. Although the ``pseudo move variant'' uses one more move in its
conversion, this move can be bypassed in a lot of cases. Also, we
already saw in the conclusions for the ``resource variant'' that for
fairly large machines, the bus utilization is low enough to be able to 
store the immediate write (and even an extra move in the ``pseudo move 
variant'') without having to add a new instruction. 
\item For small architectures this utilization becomes more of a
problem. You will see that the ``pseudo move'' variant gets a slightly
better efficiency in scheduling, since the immediate write is a normal
move under scheduling, a task for which many optimizations are
written.
\item Because the compiler used for the ``pseudo-move variant'' is not 
as optimized, more ``holes'' in the instruction stream will appear,
which is beneficial for efficient scheduling of long immediates, which can
take advantage of a less dense utilized transportation network

\end{itemize}

We can now re-evaluate the advantages and disadvantages as presented
in subsection~\ref{ssec:pseudo-qual}:

\begin{itemize}
\item The main advantages of the ``resource variant'' are: There
are relatively less adaptations to the existing framework
necessary. Adding a new type of ``move'' to the scheduler involves
adaptations of the code base in several parts of the scheduler.  The
other advantage is that the design space of choosing which move slots
write to which immediate register and when, is much more flexible in
the ``resource variant''. The advantage of the ``resource variant''
that it doesn't need the extra move proved to be invalid for reasons
stated in the previous bullet points.
\item The main advantages of the ``pseudo-move'' is that since the
immediate write is a real move, scheduling of the immediate write can
be more efficient, since much work has already be done on this field.
\item It will be shown in the next section, section~\ref{sec:future},
that the advantages of possible importing and sharing have very few
effect on the achieved cycle counts. Both the ``pseudo move variant'', 
which was able to import, and the ``resource variant'', which was able
to share, could benefit from these two optimizations, but both
optimizations will probably never be implemented.
\end{itemize}



