\documentclass[10pt,oneside]{article}
\reversemarginpar 
\usepackage[titles]{tocloft}
\usepackage{palatino}
\usepackage{wrapfig}
\usepackage{epsfig}
\usepackage{verbatim}
\usepackage{parskip}
\usepackage{register}
\usepackage{bytefield}
\usepackage[colorlinks=true, pdfstartview=FitV, linkcolor=blue, citecolor=blue, urlcolor=blue]{hyperref}
\renewcommand{\ttdefault}{cmtt}
\title{The FleetTwo Toolchain Manual\\{\normalsize A Compiler Writer's View of Fleet}}
\begin{document}
\maketitle

\begin{thebibliography}{[GDG01]}
\bibitem[ArchMan]{ArchMan}
  {\it The FleetTwo Architecture Manual}
\end{thebibliography}


\vspace{3cm}
\begin{abstract}
Fleet compilers and tools work primarily with representations of two
entities: Ships, Instructions, and Test Cases.  In order to promote
greater interoperability, the FleetTwo Toolchain defines both a Java
API and a textual file format for each of these.
\end{abstract}

\vfill
\fbox{\parbox{5in}{\footnotesize
\begin{center}
The software described in this memo may be obtained using
\href{http://www.darcs.net/}{\tt darcs}, with the command:

{\tt darcs get http://research.cs.berkeley.edu/class/fleet/repos/fleet/}
\end{center}
}}

\pagebreak
\tableofcontents

\pagebreak
\section{Introduction}

Fleet compilers and tools work primarily with representations of two
entities: Ships, Instructions, and Test Cases.  In order to promote
greater interoperability, the FleetTwo Toolchain defines both a Java
API and a textual file format for each of these.

In the case of ships, this takes the form of the {\tt .ship} file
format for describing ships and the {\tt ShipDescription} Java class
which an implementation of Fleet uses to inform the toolchain (such as
the assembler and compiler) of what ships it contains and how they may
be used.  A library is provided for parsing the textual file format
into the Java representation.

In the case of instructions, and more generally programs, this takes
the form of the {\tt .fleet} assembly language file format for
representing Fleet programs and the {\tt Instruction} and {\tt
  CodeBag} Java classes for representing programs and manipulating
them.  A library is provided for parsing Fleet assembly language
programs into {\tt CodeBag}s of {\tt Instruction}s, and for writing
those objects back out as text.

Finally, the FleetTwo Toolchain defines a very simple debugging
interface, {\tt Device}, which lets a program dispatch a codebag to a
running Fleet chip and read back the words which arrive at its {\tt
  Debug} port.  A test harness has been written which makes no
assumptions about the device under test other than that it supports
this debugging interface and that it is capable of describing itself
via the {\tt ShipDescription} API.  By meeting these relatively minor
requirements, a new Fleet implementation can immediately take
advantage of a great deal of prebuilt testing infrastructure.  This
API has been implemented and is fully functional for both the software
interpreter implementation of Fleet and the FPGA simulation of Fleet.


\pagebreak
\section{Representing Ships}
\subsection{Ship Description Files (FleetDoc)}

Inspired by JavaDoc, the Fleet software toolchain includes a tool
called {\tt FleetDoc}, which processes {\it ship description files}
with the extension {\tt .ship}.  These files contain sections for:

\begin{itemize}
\item The name of the ship
\item A list of its ports
\item A prose description of the ship
\item A list of the constants associated with a ship
\item Java source code for a software simulation of the ship
\item Verilog source code for an FPGA simulation of the ship
\item A test case for the ship
\item A list of the contributors to all of the above
\end{itemize}

Keeping all of this information in a single file ensures that changes
to one item -- such as the list of ports -- are propagated to the
other items -- such as the verilog code for simulation purposes.

Keeping this information in {\it machine-readable} format makes it
possible to automatically generate tools which depend on the precise
details of ship ports (such as the Fleet assembler) without the risk
inherent in manual synchronization.

The latter half of the architecture manual \cite{ArchMan} -- including
the ship diagrams -- is generated automatically from the contents of
the {\tt .ship} files.

\pagebreak
\subsubsection{An Example FleetDoc File}
\begin{verbatim}
ship: BitFifo

== Ports ===========================================================
in:   in
in:   inOp
  constant lsbFirst: ....................................1
  constant msbFirst: ....................................0
  constant drop:     .............................uuuuuu..
  constant take:     .......................uuuuuu........
...
  
== TeX ==============================================================
The BitFifo internally stores some number of bits in a fifo structure.
Its capacity is guaranteed to be at least two full machine words or
more.
...

== Fleeterpreter ====================================================
public void service() {
  if (box_inOp.dataReadyForShip() && box_in.dataReadyForShip()) {
  ...

== FPGA ==============================================================
always @(posedge clk) begin
  if (!in_r    && in_a)     in_a    <= 0;
  if (!inOp_r  && inOp_a)   inOp_a  <= 0;
  ...

== Test ==============================================================
#expect 1
#expect 68719476736
#ship debug        : Debug
#ship bitfifo      : BitFifo

bitfifo.outOp:      literal BitFifo.outOp[take=37]; [*] deliver;
...

== Contributors =========================================================
Amir Kamil <kamil@cs.berkeley.edu>
Adam Megacz <megacz@cs.berkeley.edu>
\end{verbatim}


\pagebreak
\subsection{Java API for Ship Descriptions}

\pagebreak
\section{Representing Machine Code}
\subsection{Fleet Assembly Language}

The Fleet Assembly language is designed to be a human-readable
depiction of the bits which comprise a Fleet program.

\subsubsection{Formal Grammar}
The formal syntax is given below:

\verbatiminput{fleet.g}

\subsubsection{Translation To Machine Code}

Please refer to \cite{ArchMan} for the details of the Fleet
instruction encoding.

As shown in the grammar above, the start symbol for the grammar ({\tt
  s}) yields a {\tt Program} surrounded by optional whitespace.  A
program is a sequence of {\tt Directive}s followed by a {\tt
  CodeBagBody}.  A {\tt CodeBagBody} consists of zero or more
elements, each of which is either a {\tt Fiber} or a (nested) {\tt
  CodeBagDef}.

A {\tt Fiber} is a set of {\tt Instruction}s which all share a common
execution point ({\tt Pump}).  Each instruction can be a {\tt unclog},
{\tt clog}, {\tt kill}, {\tt literal}, or a set of {\tt Command}s.  It
should be fairly clear how to translate all but the last sort of
instruction into machine code, based on the encodings in
\cite{ArchMan}.  Take particular note of the fact that {\tt literal}s
may have a {\tt RequeueCount} but not a {\tt RepeatCount}.

The repetition count for an instruction is placed in square brackets
and prefixes the instruction.  The requeueing count for an instruction
is placed at the end of the instruction because, {\it conceptually},
requeueing takes place after the instruction executes.

A {\tt Command} is either {\tt wait}, {\tt nop}, {\tt discard}, {\tt
  recieve}, {\tt take}, {\tt deliver}, {\tt send}, {\tt sendto}, {\tt
  notify}, or {\tt notifyLast}.  These are compiled as shown below:

\begin{itemize}
\item[\tt wait] is valid only on an inbox, and sets {\tt Ti=1}
\item[\tt nop] is not valid in combination with any other command; it sets all control bits to {\tt 0}
\item[\tt discard] sets {\tt Di=1,Dc=0}
\item[\tt recieve] is valid only on an input port, and sets {\tt Di=1,Dc=1}
\item[\tt take] is valid only on an output port, and sets {\tt Di=1,Dc=1}
\item[\tt deliver] is valid only on an input port, and sets {\tt Do=1}
\item[\tt send] is valid only on an output port, and sets {\tt Do=1,To=1}
\item[\tt sendto] is valid only on an output port, and sets {\tt Do=1}
\item[\tt notify] sets {\tt To=1} and is not valid in combination with {\tt send} or {\tt sendto}
\item[\tt notifyLast] sets {\tt To=1,Ig=1} and is not valid in combination with {\tt send} or {\tt sendto}
\end{itemize}

It is an error to specify two commands within a single instruction if
both of the commands attempt to set the same bit (even if they attempt
to set it to the same value).

Note that un-named (``anonymous'') codebags may appear as literals.
This means that it is possible to write interesting programs such as
the one below:

\begin{verbatim}
#expect 3

#ship debug  : Debug
#ship memory : Memory

memory.inCBD: literal {
    memory.inCBD: literal {
        memory.inCBD: literal {
            debug.in:
              literal 3;
              deliver;
          }; deliver;
      }; deliver;
  }; deliver;
\end{verbatim}




\pagebreak
\subsection{Java API for Fleet Machine Code}

\pagebreak
\section{Test Cases}
\subsection{Test Case File Format}
\subsection{Java API for Controlling Device Under Test}

\end{document}
