revise startCounters()

[fleet.git] / doc / toolchain.tex

\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 FleetTwo}}
\author{Adam Megacz}
\begin{document}
\maketitle

\begin{thebibliography}{[GDG01]}
\bibitem[ArchMan]{ArchMan}
  {\it The FleetTwo Architecture Manual}
\bibitem[Meg06]{SBP}
  Megacz, Adam, {\it Scannerless Boolean Parsing}. Electronic Notes in
  Theoretical Computer Science 1368, (Volume 164, Issue 2):
  Proceedings of the Sixth Workshop on Language Descriptions, Tools,
  and Applications (LDTA 2006)
\end{thebibliography}


\vspace{3cm}
\begin{abstract}
Fleet compilers and tools work primarily with three entities: Ships,
Instructions, and Test Cases.  In order to promote greater
interoperability, the FleetTwo Toolchain defines both a Java API and a
text 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 three 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 of what
ships it contains and how they may be used.  The toolchain includes a
library 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.

In the case of Test Cases, the FleetTwo Toolchain defines a very
simple debugging interface, {\tt Device}, which lets a program
dispatch a codebag to a running Fleet implementation or emulator 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 modest 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{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 people who contributed 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 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}

The FleetTwo toolchain includes a utility for parsing a {\tt .ship}
file into a {\tt ShipDescription}.  There is one {\tt ShipDescription}
for each {\it kind} of ship.  This distinction will become important
later, when we introduce classes to represent {\it instances} of ship
types.

\begin{verbatim}
/** a description of a ship */
public class ShipDescription implements Iterable<DockDescription> {
  public String                        getName();
  public Iterable<ConstantDescription> getConstantDescriptions();
  public Iterable<DockDescription>    getDockDescriptions();
}

/** a description of a valve */
public class DockDescription {
  public String           getName();
  public boolean          isInbox();
  public boolean          isOutbox();
  public DockDescription getShortcut();
}

/** a constant declared by a ship */
public class ConstantDescription {
  public final long setbits;
  public final long clearbits;
  public final boolean signExtend;
  public final int numberOffset;
  public final int numberWidth;
}
\end{verbatim}


\pagebreak
\section{Instructions}
\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.  The metagrammar used is that of the
Scannerless Boolean Parser \cite{sbp}.

\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 {\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 nop] is not valid in combination with any other command; it sets all control bits to {\tt 0}
\item[\tt wait] is valid only on an output port, and sets {\tt Ti=1}
\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 sendto] is valid only on an output port, and sets {\tt Do=1}
\item[\tt send] is valid only on an output port, and sets {\tt Do=1,To=1}\footnote{see \cite{ArchMan} for the special meaning this bit combination has}
\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}
#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}

\subsection{Ships}
\begin{verbatim}
public abstract class Ship {

    /** return the description for this ship */
    public ShipDescription getShipDescription();

    /** return all pumps which feed this ship; order is NOT significant */
    public Iterable<Dock> getDocks();
    public Dock getDock(String s);

    /** if this is the 4th fifo ship, this method returns 4 */
    public int getOrdinal();

    /** return the Fleet that this Ship belongs to, if any */
    public Device  getDevice();
}
\end{verbatim}

\subsection{Dock}
\begin{verbatim}
public class Dock {

    /** the descriptive name of this pump (relative to its ship) */
    public abstract String getName();

    /** return the Ship to which this Dock belongs */
    public abstract Ship   getShip();

    /** the maximum number of instructions we can put in the Dock instruction fifo,
     *  or Integer.MAX_VALUE if unbounded */
    public abstract int getInstructionFifoLength();

    /** returns true if this is an inbox */
    public abstract boolean isInbox();

    /** returns true if this is an outbox */
    public abstract boolean isOutbox();

    /** return the Dock which is the destination of this Box's shortcut (if any) */
    public Destination getShortcut() { return null; }
}            
\end{verbatim}

\subsection{Instructions}
\begin{verbatim}
public abstract class Instruction {
    public final Pump pump;

    public static class UnClog extends Instruction {
    }

    public static class Clog extends Instruction {
    }

    public static abstract class CountingInstruction extends Instruction {
        public final int count;
        public CountingInstruction decrementCount();
    }

    public static class Kill extends CountingInstruction {
    }

    public static class Executable extends CountingInstruction {

        public final Destination dest;

        public final boolean     tokenIn;
        public final boolean     dataIn;
        public final boolean     latch;
        public final boolean     send;
        public final boolean     sendTo;
        public final boolean     tokenOut;
        public final boolean     requeue;
        public final boolean     ignoreUntilLast;

        public boolean isStanding();
    }

    public static class Literal extends CountingInstruction {
        public final long literal;
    }
}
\end{verbatim}

\pagebreak
\section{Test Cases}

\subsection{Test Case File Format}

The test case file format is quite simple -- it is nothing more than a
regular Fleet assembly language program with {\tt \#expect} statements
to indicate the values which should arrive at the {\tt Debug.in} port
if the test runs correctly.

\subsection{Java API for Controlling Device Under Test}

\subsection{The Device}
\begin{verbatim}
public abstract class Device implements Iterable<Ship> {

    /** read a machine-formatted instruction from a file (into a Java object) */
    public abstract Instruction
       readInstruction(DataInputStream is) throws IOException;

    /** write a machine-formatted instruction to a file (from a Java object) */
    public abstract void 
       writeInstruction(DataOutputStream os, Instruction instr) throws IOException;

    public abstract Iterator<Ship> iterator();

    /** if possible, run the given code and create a FleetProcess */
    public FleetProcess run(byte[] code);
}
\end{verbatim}

\subsection{A Running Test}

\begin{verbatim}
/** represents a <i>running</i> "slave" fleet with a debug connection */
public abstract class FleetProcess {

    /** dumps an instruction into the fetch unit */
    public abstract void invokeInstruction(Instruction i);

    /** reads a word back from the debug port */
    public abstract long readWord();

    public final synchronized void terminate();

    public final boolean isTerminated();
}
\end{verbatim}

\end{document}