X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=doc%2Ftoolchain.tex;h=3a6e3dc8b425dc3c07fbe400b39dccf0ea7300b8;hb=aee85d3dd0435554e14e03b97f268752843a441f;hp=091bc6073a623c860972a4bc5a6b7ff8aabe5542;hpb=20e2056f1af4e3a1c10eb1e95a0bc8ee4e870159;p=fleet.git diff --git a/doc/toolchain.tex b/doc/toolchain.tex index 091bc60..3a6e3dc 100644 --- a/doc/toolchain.tex +++ b/doc/toolchain.tex @@ -10,22 +10,28 @@ \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}} +\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 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. +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 @@ -44,17 +50,17 @@ The software described in this memo may be obtained using \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. +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 (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. +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 @@ -64,21 +70,22 @@ 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. +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{Representing Ships} +\section{Ships} \subsection{Ship Description Files (FleetDoc)} Inspired by JavaDoc, the Fleet software toolchain includes a tool @@ -93,7 +100,7 @@ with the extension {\tt .ship}. These files contain sections for: \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 +\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 @@ -102,7 +109,7 @@ 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 +details of ship ports without the risk inherent in manual synchronization. The latter half of the architecture manual \cite{ArchMan} -- including @@ -158,15 +165,50 @@ Adam Megacz \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 { + public String getName(); + public Iterable getConstantDescriptions(); + public Iterable 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{Representing Machine Code} +\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 formal syntax is given below. The metagrammar used is that of the +Scannerless Boolean Parser \cite{sbp}. \verbatiminput{fleet.g} @@ -183,7 +225,7 @@ 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}, +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 @@ -200,29 +242,27 @@ A {\tt Command} is either {\tt wait}, {\tt nop}, {\tt discard}, {\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 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 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 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). +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. +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 @@ -243,9 +283,138 @@ memory.inCBD: literal { \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 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 { + + /** 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 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 running "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}