\chapter{Endianness implementation}
\label{cha:endianness-impl}


This chapter will explain how the MOVE framework was made
endianness-independent. The previous chapter explained the issues
concerning endianness, and this chapter will deploy the guidelines
from that chapter on the MOVE framework, to make it host-platform
independent as well as move-target independent.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The MOVE framework}

The MOVE framework consists of roughly two parts: the front-end and
the back-end. This can be visualized in figure~\ref{fig:sf}. The
front-end consists of a standard freely available compiler, the GNU C
Compiler, including its tools like assembler, linker and auxiliary
tools. This compiler can be easily ported to other architectures by
means of writing a new architecture plug-in. The tools related to the
compiler, the so-called binary tools, include an assembler, linker and
various other tools that operate on the binary. These tools were
ported to the MOVE architecture by rewriting the ``m68k'' assembly
format to fit the MOVE specification. Lastly, a system library, also
called the C-library, is needed. This library does not need any MOVE
specific changes, but it does have some endianness dependencies that
need to be resolved. The adaptations needed to make the front-end
endianness independent can be found in section~\ref{sec:endfront}

The back-end consists of the scheduler tools, including a simulator,
scheduler and various auxiliary tools that help the simulator and the
scheduler, like a design-space explorer, a call-graph visualizer and a
tool to view the assembly code in a human readable form. The
adaptation needed to make the back-end endianness independent can be
found in section~\ref{sec:endback}

The approach taken was to make the whole framework first
host-endianness independent. This alone would allow us to deploy the
MOVE framework on Linux platforms instead of Sparc platforms, even if
there was no problem of target endianness (i.e. the Move architecture
has only one endianness, e.g. big, and only the endianness of the host 
has to be taken into account). This port was done
in such a way, that further work on making the framework
target-endianness independent, would be straightforward and trivial.
Another requirement was that the host-endianness dependencies would be 
compile-time invisible, so that there would be no need to set
compile-time switches to help the framework determine what kind of
host platform is was compiled on. This was achieved through the use of 
the predefines that the compiler sets: e.g. {\tt \_\_i386} is set during 
building and installation on an Intel platform.

Target endianness was implemented in such a way that a single switch
in the two Makefiles is sufficient, one for the front-end and one for the
back-end. This would require a recompile for each target. This was
considered not a problem, since the MOVE framework's directory layout
also included a directory for pre-compiled libraries, which would be
target-endianness dependent anyway. A new tree for either little or
big-endian targets, including compiler-binaries and libraries for each
target, is then created.


First, some defines are set to indicate the host and target endianness:
\begin{itemize}
\item If the host platform is big-endian (check {\tt \_\_sun} flag, a
preprocessor predefine that is always set on Sparc machines),
then the define {\tt HOST\_BIG\_ENDIAN} is set to {\tt 1} and the define
{\tt HOST\_LITTLE\_ENDIAN} is set to {\tt 0}. Else, the host platform is
little endian, and both defines get their inverse value.
\item If the target architecture is little-endian (check setting in {\tt
config.h} for the back-end, a Makefile directive in the front-end) then
the define {\tt TARGET\_LITTLE\_ENDIAN} is set to {\tt 1} and the define
{\tt TARGET\_BIG\_ENDIAN} is set to {\tt 0}. Else, the target
architecture is big endian, and both defines get their inverse value.
\end{itemize}

Note that we explicitly set all preprocessor defines to a value,
instead of just defining or undefining them. 
Now that these 4 defines are set throughout the whole framework, in a
uniform way, we can easily check for these values whenever we
encounter a dependency.

A couple of extra defines are derived from the four mentioned
above. In many cases, e.g. cases were we have both target- and
host-endianness dependencies, we want to have a way to check whether
the two endiannesses are the same or different. Therefore we add one
more preprocessor define, {\tt SWAP\_ENDIANESS}. This define is set to
{\tt 1} when the endiannesses are different, and set to {\tt 0}
when they are the same. Since converting from little to big endianness
is the same as converting from big endianness to little, this define
comes in handy whenever we have encounter a structure that is both
dependent on the host and the target platform's endianness.

Endianness in files on disk can be divided in two variants. One
variant is a file that contains target-dependent information. This
includes the serial binary and the parallel binary. The other variant
is a file that does not contain target-dependent information, like the
profiling files of the back-end. These files are always stored in a
big-endian way. To process structures in files that
have a target-endianness dependency, and of course implicitly also a
host-endianness dependency, we now can use the {\tt SWAP\_ENDIANESS}
define to read and write these files correctly. To process files that
only have a host-endianness dependency, we can use the {\tt
HOST\_BIG\_ENDIAN} or its inverse, the {\tt HOST\_LITTLE\_ENDIAN} define.

More problematic are files that contain both target-dependent data
(apply target-endianness) and target-independent (apply
host-endianness) data. The serial binary, for instance, also contains
various structures that have nothing to do with the program, but are
necessary for a correct binary. Care must be taken that the routines
that operate on these files can recognize the various structures and
process them correctly. The approach taken is to have all
host-endianness dependencies written out in big-endian on disk. This
corresponds with the format on disk that the legacy tools used. The
target-endianness is stored either little or big endian, and a tag (in
this case the binary-header) is used to differentiate between the two
forms of target-endianness.


To visualize the cross platform requirements on the front-end, please
look at figure~\ref{fig:end}. This will show that every step in the
process should be able to read either output from a platform with the
same endianness, as well as output from a platform with a different
endianness. This figure shows the trajectory for one
target-endianness. To list all possible cross-relationships, one
should duplicate this figure for another target-endianness. These two
figures, each representing a target-endianness, then would be
completely unrelated. 
For example, a linker compiled to link big-endian move code
cannot read little-endian move code.

\begin{figure}[htb]
   \centerline{\epsfxsize=10cm \epsfbox{fig/endianess.eps}}
   \caption{The front-end on both endianness platforms}
   \label{fig:end}
\end{figure}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The MOVE front-end}
\label{sec:endfront}

The front-end consists of the GCC compiler, version 2.7.0, and the
{\tt bintools} distribution, version 1.38, together with a standard
BSD C-library. All three components can be
made endianness independent on their own, as long as the interface
format is clearly defined. We have three interface formats that we have 
to deal with:

\begin{compactenumerate}
\item plain text assembly code ({\tt .s} files)
\item non-linked object files ({\tt .o} files)
\item linked binaries (no suffix)
\end{compactenumerate}

Regarding host-endianness dependencies, we impose the requirement on
these two latter formats that they are independent of the
host-endianness. This results in the property that a file can be
created on one platform, and read back by another platform, without
any problems.

The first format, the plain text assembly, has no host-endianness
dependencies, since it is plain text. Plain text is stored
sequentially on disk, and has no endianness at all. The other two do
have dependencies, because the object format deploys both bit-fields
as well as byte-ordering within a word.

Regarding target-endianness dependencies, we impose the requirement on 
these three formats that the binary formats all use the same
encodings, so that there is no format difference between the data in
an object and the data in a binary. This also makes sure that object
files archived in a library can be linked against other object files
without worrying whether a certain routine came from a stand-alone
object file or a library.

Target-endianness can be divided up in two parts: The actual
instructions and the helper information, such as the symbol table and
the relocation table. The choices made for the various types of
endianness for these various kinds of data inside an object file,
will be further explained in subsection~\ref{ssec:bintools}, which
deals with the port of the assembler, linker and binary tools.



\subsection{GCC}

Since GCC version 2.7.0 is already host-endianness independent, no
code changes were needed. Target-endianness is controlled by some
directives in the so called ``target-description macros'', as defined
the the {\tt machine.h} file of GCC. The relevant macros are {\tt
BITS\_BIG\_ENDIAN}, {\tt BYTES\_BIG\_ENDIAN} and {\tt
WORDS\_BIG\_ENDIAN}~\cite{gccman}. For little-endian targets, all
three defines are set to zero, and for big-endian targets all three
defines are set to one.

Since GCC outputs plain text {\tt .s}-files, the assembly doesn't need 
to care about most endianness problems. A word will be represented as
its decimal equivalent in ASCII, and it's the assembler's job to
encode this in 4 bytes. What does matter is bitfields within a byte,
which will be implemented by the compiler by shifting the byte several 
bits, as well as accessing bytes within a word explicitly in C. This
is also handled by the compiler by outputting code that shifts a word
several bytes in order to be able to access the right byte in a
word. All the compiler needs is the three above-mentioned switches to
take care of these cases. This concludes the port of both the
target-endianness as well as the host-endianness dependencies of the
GCC compiler.


\subsection{Assembler, linker and auxiliary binary tools}
\label{ssec:bintools}

The version of the {\tt bintools}~\footnote{the common name for the group of
assembler, linker and other tools} used in the MOVE framework is
version~1.38. This is unfortunately a very old version, and completely 
obsolete. There are two major drawbacks with this version: 
The architecture format is not easily changed, instead, for each port,
a complete implementation of the tools exist, instead of a
configurable plugin, like GCC-2.7.0 or the newer versions of {\tt
bintools}. The second drawback is that host-endianness independence is 
not implied, like it is in GCC-2.7.0 or the newer versions of {\tt
bintools}.

These considerations led to a feasibility study of deploying a newer
version of the tools. A new version of the {\tt bintools} distribution 
was inspected, but porting to the existing MOVE binary format, while
preserving all intermediate formats and the actual serial binary that
the back-end can read, would be a lot of work. On the other hand, some 
work on making these tools host-endianness aware was already in
progress. Conclusion was that a complete new port to the
MOVE binary format would require more work than changing the current
code base. Therefore it was decided the current version 1.38 was to be
changed.

The binary tools consist of the following programs:

\begin{itemize}
\item {\tt as}, the assembler
\item {\tt ld}, the linker/loader
\item {\tt ar}, the library archiver
\item {\tt size}, a utility to print segment sizes
\item {\tt nm}, a utility to print out symbols
\item {\tt objdump}, a utility to dump various segments
\item {\tt ranlib}, a utility to index a library archive
\item {\tt dem}, a utility to demangle C++ symbols
\item {\tt c++-filt}, another utility to demangle C++ symbols
\item {\tt strip}, a utility to strip a binary from its symbols
\end{itemize}

These tools can be divided in three parts, the assembler, the linker
and the rest of the tools.

\subsubsection{The assembler}
The assembler was very straightforward to port. The function {\tt
md\_number\_to\_chars} is responsible for placing a value representing 
a byte, halfword or word in a file stream. It does this by putting each byte
in the correct position in the 4-byte word. For this it uses the C++
{\tt >>} operator, which is already host-endianness safe (the compiler 
will recognize that operator and rearrange bytes and words in order to 
let the {\tt >>} operator be endianness-independent). So the only
consideration is the target endianness. By adding a check for {\tt
TARGET\_LITTLE\_ENDIAN} it was trivial to put the bytes on the right
spot in the word, according to the rules of endianness.

The function {\tt md\_number\_to\_chars} is, amongst others, called
from the routine that emits the text segment. Since the move binary
instruction field encoded in the binary file contains bitfields, the
calls to {\tt md\_number\_to\_chars} are re-ordered in case of a
little endian target.


\subsubsection{The linker}
The linker needs to actually read all various segments of an object,
in order to be able to read the symbol and relocation tables, alter
them and write them back into the final binary. Since this old version
of {\tt ld} processes all sections with direct calls to the Unix
system call to {\tt read(2)} and {\tt write(2)}, it was not directly
possible to swap various bitfields and bytes. These functions read a
whole block at once into a buffer, without the option to swap while
reading.  Therefore for every kind
of segment, new routines called {\tt read\_<segment>} and {\tt
write\_<segment>} are created to be put in place of the actual {\tt
read(2)} and {\tt write(2)} calls. These hooks then read the
corresponding segment in a buffer, process that buffer for endianness
according to the {\tt HOST\_LITTLE\_ENDIAN} and {\tt
TARGET\_LITTLE\_ENDIAN} predefines, as explained in
chapter~\ref{sec:end-overview}, and return the buffer to the calling
routine.

In this fashion, the following routines are defined to serve as hook
for the real {\tt read(2)} and {\tt write(2)} calls:
\begin{itemize}
\item {\tt read\_header}, for the binary header
\item {\tt read\_integer}, for a simple number 
\item {\tt read\_symroot}, for symbol table indexes
\item {\tt read\_symbols}, for symbols
\item {\tt read\_symdef}, for symbol definitions
\item {\tt read\_reloc}, for relocation information
\item {\tt read\_arhdr}, for the archive header
\item {\tt read\_text}, for the text segment
\item {\tt read\_strings}, for simple strings of text
\end{itemize}
Also, their {\tt write\_} counterparts are defined.

These functions read or write the corresponding segment, with
knowledge on where bitfields and other boundaries (such as 16 bit data
that only needs to be swapped on half-word boundaries) on segments
occur, so they can apply the endianess switches correctly.

\subsubsection{Bintools}
The bintools, coming from the same distribution as the linker in the
previous section, suffer from the same drawback that they deploy
direct calls to {\tt read(2)} and {\tt write(2)}. In addition to this,
they also use direct calls to {\tt fread(3)} and {\tt fwrite(3)}. This
means that the list presented in the previous section needs to be
duplicated to also be able to hook all calls to {\tt fread(3)} and
{\tt fwrite(3)}. For the rest, the port of these bintools is
straightforward and implies, just as with the linker, replacing all
occurrences to {\tt read(2)}, {\tt write(2)}, {\tt fread(3)} and {\tt
fwrite(3)} with calls to their corresponding hooks.


\subsection{System libraries}

The GNU C Library is endianness independent, except at one
point. There are different ways of encoding floating point
numbers. They are:

\begin{compactenumerate}
\item{\bf vax} for the VAX D\_floating format
\item{\bf tahoe} for the TAHOE double format
\item{\bf national} for IEEE machines whose floating point
implementation has similar byte ordering as the NATIONAL 32016 with
32081
\item{\bf ieee} for other IEEE machines
\end{compactenumerate}

A comparison with floating point implementations on other
architectures learned that big-endian IEEE machines use the ``ieee''
format, while little-endian IEEE machines use the ``national''
format. The {\tt makelibs} script that generates the {\tt libm} library, the math
part of the C-library, was changed so that when the
libraries were compiled for a little-endian MOVE target, the
``national'' encoding would be used. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The MOVE back-end}
\label{sec:endback}

The back-end communicates with the front-end through only one thing,
namely the binary. As explained in the previous section, the
host-endianness of the platform where the framework runs on does not
matter, only the target-endianness of the MOVE architecture will
influence the contents of the binary.

Also, it was noted that tools could be run from any host
platform. That means files written to disk between runs of various
parts of the back-end should be host-endianness independent, too.
The files we are dealing here with are:

\begin{compactenumerate}
\item {\em the serial binary} that is produced by the front-end
\item {\em profiling} data that is written to disk
\item {\em the parallel binary} that is produced by the scheduler
\item {\em the parallel assembly} that is produced by the scheduler
\end{compactenumerate}

Subsection~\ref{ssec:end-binread} will deal with the reading of the
serial binary, subsection~\ref{ssec:end-sched} with the scheduling of
the MOVE code, subsection~\ref{ssec:end-simul} will deal with the
profiling files and subsection~\ref{ssec:end-writebin} will deal with
the write of the parallel binary. The parallel assembly file is just
plain text and has no endianness dependencies.


\subsection{Binary reader}
\label{ssec:end-binread}

The binary reader is, endianness-wise, the trickiest part of the
back-end. It has the task of reading the binary generated by the GNU
front-end and convert it into internal data
structures. With respect to endianness, this means two things: 

\begin{compactenumerate}
\item The binary must be read  independent from the {\bf host endianness}. That
means that in parts where there is no target-endianness dependency,
the define {\tt HOST\_LITTLE\_ENDIAN} must be checked, and a byte swap must
occur if the host endianness is different from the endianness of the
structure on disk (which is always big endian, like it was in the
legacy framework). 
\item The binary must be read independent from the {\bf target
endianness}. That means that in parts where there is a
target-endianness dependency, the define {\tt SWAP\_ENDIANNESS} must be
checked, and a byte swap must occur if the host endianness is different
from the endianness of the structure on disk (which can be either way,
depending on the target architecture).
\end{compactenumerate}

As mentioned in subsection~\ref{ssec:bintools}, the serial binary
contains various different sections.  The class {\tt AOut} takes care
of reading in the binary, section by section.
%For
%reference, appendix~\ref{app:aout} describes all data structures
%related to endianness in the {\tt AOut} class.
The following structures needed adaptation on endianness

\begin{itemize}
\item the header, which contains bitfields. The header does not
contain any target-dependent code, so only {\tt HOST\_LITTLE\_ENDIAN}
is checked for the bitfields. However, the assembler output routines
swap everything. As discussed during the front-end discussion, the
{\tt md\_numbers\_to\_chars} is called for every segment, even the
segments that contain no target-dependent information.
This is because of the old version of the
assembler. Therefore we still need a {\tt SWAP\_ENDIANESS} check on
the whole header, also on the parts that do not contain any
target-endianness dependencies.
\item the text and data parts are both host and target endianness
dependent. Therefore these are read in using the {\tt SWAP\_ENDIANESS}
directive. The moves themselves are stored as bitfields in a word, so
we need to guard them with a {\tt HOST\_LITTLE\_ENDIAN} check and swap
accordingly. 
\item the relocation data is stored on disk, independent of the
target, always in big-endian format., 
therefore only {\tt HOST\_LITTLE\_ENDIAN} is checked. Inside the
relocation data, we also have to deal with bitfields, so also on those 
bitfields a {\tt HOST\_LITTLE\_ENDIAN} check is required.
\item the symbols data are stored as strings on disk. These strings
are endianess independent. The only caveat here is that the symbol
also contains a word with bitfields. This word needs a {\tt SWAP\_ENDIANESS}
check. (not a {\tt HOST\_LITTLE\_ENDIAN} check like other bitfields,
since the whole data is not swapped on byte ordering during read, as
the other are)
\end{itemize}


Concluding we can say that in general, only target-dependent data like
the text and data segments, are both checked against host and target
dependencies. Therefore we have to guard these reads with a {\tt
SWAP\_ENDIANESS}. Other non-target related data need only to be
guarded with {\tt HOST\_LITTLE\_ENDIAN}. Bitfields, however, must be
also checked against host endianness at all times.  This check is
implemented by changing the declaration of the structure at
compile-time to match the bitfield-ordering of that specific
endianness.




\subsection{Scheduler}
\label{ssec:end-sched}

The scheduler is responsible for taking the internal data-structure
representing the serial binary, and converting it into another
data-structure that represents the parallel binary. This involves
various steps but none of these steps work on the actual
data in the binary. Values like addresses are already put in the
data structures in a correct way by the binary reader, and the binary
writer is responsible for converting the structures back into a binary.
Therefore, the scheduling algorithms do no need any adaptations with
respect to endianness dependencies.


\subsection{Simulator}
\label{ssec:end-simul}

Simulation generates profiling information, like frequency count and
memory dependencies. This profiling data can be written to disk to be
used in subsequent runs of the scheduler or simulator. Therefore care
must be taken when writing and reading these files. The routines {\tt
Prog::SaveProfile}, {\tt Prog::ReadProfile}, {\tt Prog::LoadMDeps},
{\tt Prog::SaveMDeps} and {\tt Prog::MDepsExists} are therefore
guarded with checks on {\tt HOST\_LITTLE\_ENDIAN} to make sure the
profiling data is written to disk in a host independent fashion
(namely big-endian), so profiling data can be used across platforms.


The simulator itself does not operate on files. It, however, has other
dependencies on endianness.  The simulator has to make sure it can
offer the program under simulation an environment that is a correct
image of the actual target platform. This means that parts of the
simulator that represent a feature of the target platform, like the
memory, the register files, the buses, have a target-endianness
dependency. Most parts, however, have only one way to access them,
e.g. register files and buses can only be written to by whole words at
once, without the possibility to access smaller parts of these
words. If one wants a smaller part of a register, this would already
have been addressed in the actual move assembly, that the GCC
front-end has generated correctly already. In other words, these
components of the target architecture are word-addressable and nothing
else.

The memory is the big exception here. Memory, although usually written
to in whole words, is byte-addressable. Also, the MOVE architecture
provides operations to access half-words and bytes in memory. This
means every write or read to or from memory needs to be split up in
bytes, which will then be written to the memory in a fashion depending
on the target-endianness of the architecture.

Specifically, the memory class {\tt SimMem} has member functions like
{\tt SimMem::WriteW}, {\tt SimMem::WriteH}, {\tt SimMem::WriteB}, {\tt
SimMem::WriteS} and {\tt SimMem::WriteD} for respectively writing
words, halfwords, bytes, single-precision floats and double-precision
floats. Also, their read-counterparts are present.
These functions all work by first getting a whole 32-bit quantity from memory,
then byte swap depending on the {\tt SWAP\_ENDIANESS} predefine, and
either read or write the correct (part of a) word. The implementation
of the {\tt SimMem} class can be found in appendix~\ref{app:end}.



\subsection{Binary writer}
\label{ssec:end-writebin}

The binary writer's job is to convert the internal data structure of
the program into two files: a readable assembly output, usually called
{\tt b.txt}, and a parallel binary, suitable for feeding to an actual
chip, called {\tt b.out}. The data structures itself have no
endianness dependencies, and the assembly output is plain text. The
focus here lies on the parallel binary.

We assume that by setting the target endianness, we also specify the
bit-order of the instruction stream. This means that if we write out a
little-endian binary, both the byte-ordering in the instruction word
(which can be fairly large, e.g. 128 bits for PcomP), and the
bit-ordering per byte is little endian.

For the implementation this means, that we have to make the routine
that outputs the so called {\tt BitArray} endianness
aware.  The {\tt BitArray} represents the actual move instruction word 
bits. This routine is the {\tt OutputBinary(ostream \&os, Insn *insn)} 
routine. This routine is  responsible for allocating the {\tt
BitArray}. Class {\tt BitArray} is already overloaded with the {\tt
<<}~operator. The change is that this overload function is altered to
make it target-endianness aware, so that it can bit-swap the entire
instruction word, if necessary.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusions}

The port of the MOVE framework to be both host and target-endianness
independent is completed with success. The tools compile without any
compile time options given on both big and little-endian hosts. The
distribution is altered so that one compile-time switch will make both 
the front-end as the back-end target-endianness aware. This
distribution then can be installed in a parallel directory tree on the 
same machine and a simple change to the shell's default search path can
let the tools switch between the little and big-endian targets.

