doc/toolchain.tex

   1 \documentclass[10pt,oneside]{article}
   2 \reversemarginpar
   3 \usepackage[titles]{tocloft}
   4 \usepackage{palatino}
   5 \usepackage{wrapfig}
   6 \usepackage{epsfig}
   7 \usepackage{verbatim}
   8 \usepackage{parskip}
   9 \usepackage{register}
  10 \usepackage{bytefield}
  11 \usepackage[colorlinks=true, pdfstartview=FitV, linkcolor=blue, citecolor=blue, urlcolor=blue]{hyperref}
  12 \renewcommand{\ttdefault}{cmtt}
  13 \title{The FleetTwo Toolchain Manual\\{\normalsize A Compiler Writer's View of FleetTwo}}
  14 \author{Adam Megacz}
  15 \begin{document}
  16 \maketitle
  17
  18 \begin{thebibliography}{[GDG01]}
  19 \bibitem[ArchMan]{ArchMan}
  20   {\it The FleetTwo Architecture Manual}
  21 \bibitem[Meg06]{SBP}
  22   Megacz, Adam, {\it Scannerless Boolean Parsing}. Electronic Notes in
  23   Theoretical Computer Science 1368, (Volume 164, Issue 2):
  24   Proceedings of the Sixth Workshop on Language Descriptions, Tools,
  25   and Applications (LDTA 2006)
  26 \end{thebibliography}
  27
  28
  29 \vspace{3cm}
  30 \begin{abstract}
  31 Fleet compilers and tools work primarily with three entities: Ships,
  32 Instructions, and Test Cases.  In order to promote greater
  33 interoperability, the FleetTwo Toolchain defines both a Java API and a
  34 text file format for each of these.
  35 \end{abstract}
  36
  37 \vfill
  38 \fbox{\parbox{5in}{\footnotesize
  39 \begin{center}
  40 The software described in this memo may be obtained using
  41 \href{http://www.darcs.net/}{\tt darcs}, with the command:
  42
  43 {\tt darcs get http://research.cs.berkeley.edu/class/fleet/repos/fleet/}
  44 \end{center}
  45 }}
  46
  47 \pagebreak
  48 \tableofcontents
  49
  50 \pagebreak
  51 \section{Introduction}
  52
  53 Fleet compilers and tools work primarily with three entities: Ships,
  54 Instructions, and Test Cases.  In order to promote greater
  55 interoperability, the FleetTwo Toolchain defines both a Java API and a
  56 textual file format for each of these.
  57
  58 In the case of ships, this takes the form of the {\tt .ship} file
  59 format for describing ships and the {\tt ShipDescription} Java class
  60 which an implementation of Fleet uses to inform the toolchain of what
  61 ships it contains and how they may be used.  The toolchain includes a
  62 library for parsing the textual file format into the Java
  63 representation.
  64
  65 In the case of instructions, and more generally programs, this takes
  66 the form of the {\tt .fleet} assembly language file format for
  67 representing Fleet programs and the {\tt Instruction} and {\tt
  68   CodeBag} Java classes for representing programs and manipulating
  69 them.  A library is provided for parsing Fleet assembly language
  70 programs into {\tt CodeBag}s of {\tt Instruction}s, and for writing
  71 those objects back out as text.
  72
  73 In the case of Test Cases, the FleetTwo Toolchain defines a very
  74 simple debugging interface, {\tt Device}, which lets a program
  75 dispatch a codebag to a running Fleet implementation or emulator and
  76 read back the words which arrive at its {\tt Debug} port.  A test
  77 harness has been written which makes no assumptions about the device
  78 under test other than that it supports this debugging interface and
  79 that it is capable of describing itself via the {\tt ShipDescription}
  80 API.  By meeting these relatively modest requirements, a new Fleet
  81 implementation can immediately take advantage of a great deal of
  82 prebuilt testing infrastructure.  This API has been implemented and is
  83 fully functional for both the software interpreter implementation of
  84 Fleet and the FPGA simulation of Fleet.
  85
  86
  87 \pagebreak
  88 \section{Ships}
  89 \subsection{Ship Description Files (FleetDoc)}
  90
  91 Inspired by JavaDoc, the Fleet software toolchain includes a tool
  92 called {\tt FleetDoc}, which processes {\it ship description files}
  93 with the extension {\tt .ship}.  These files contain sections for:
  94
  95 \begin{itemize}
  96 \item The name of the ship
  97 \item A list of its ports
  98 \item A prose description of the ship
  99 \item A list of the constants associated with a ship
 100 \item Java source code for a software simulation of the ship
 101 \item Verilog source code for an FPGA simulation of the ship
 102 \item A test case for the ship
 103 \item A list of the people who contributed to all of the above
 104 \end{itemize}
 105
 106 Keeping all of this information in a single file ensures that changes
 107 to one item -- such as the list of ports -- are propagated to the
 108 other items -- such as the verilog code for simulation purposes.
 109
 110 Keeping this information in {\it machine-readable} format makes it
 111 possible to automatically generate tools which depend on the precise
 112 details of ship ports without the risk
 113 inherent in manual synchronization.
 114
 115 The latter half of the architecture manual \cite{ArchMan} -- including
 116 the ship diagrams -- is generated automatically from the contents of
 117 the {\tt .ship} files.
 118
 119 \pagebreak
 120 \subsubsection{An Example FleetDoc File}
 121 \begin{verbatim}
 122 ship: BitFifo
 123
 124 == Ports ===========================================================
 125 in:   in
 126 in:   inOp
 127   constant lsbFirst: ....................................1
 128   constant msbFirst: ....................................0
 129   constant drop:     .............................uuuuuu..
 130   constant take:     .......................uuuuuu........
 131 ...
 132
 133 == TeX ==============================================================
 134 The BitFifo internally stores some number of bits in a fifo structure.
 135 Its capacity is guaranteed to be at least two full machine words or
 136 more.
 137 ...
 138
 139 == Fleeterpreter ====================================================
 140 public void service() {
 141   if (box_inOp.dataReadyForShip() && box_in.dataReadyForShip()) {
 142   ...
 143
 144 == FPGA ==============================================================
 145 always @(posedge clk) begin
 146   if (!in_r    && in_a)     in_a    <= 0;
 147   if (!inOp_r  && inOp_a)   inOp_a  <= 0;
 148   ...
 149
 150 == Test ==============================================================
 151 #expect 1
 152 #expect 68719476736
 153 #ship debug        : Debug
 154 #ship bitfifo      : BitFifo
 155
 156 bitfifo.outOp:      literal BitFifo.outOp[take=37]; [*] deliver;
 157 ...
 158
 159 == Contributors =========================================================
 160 Amir Kamil <kamil@cs.berkeley.edu>
 161 Adam Megacz <megacz@cs.berkeley.edu>
 162 \end{verbatim}
 163
 164
 165 \pagebreak
 166 \subsection{Java API for Ship Descriptions}
 167
 168 The FleetTwo toolchain includes a utility for parsing a {\tt .ship}
 169 file into a {\tt ShipDescription}.  There is one {\tt ShipDescription}
 170 for each {\it kind} of ship.  This distinction will become important
 171 later, when we introduce classes to represent {\it instances} of ship
 172 types.
 173
 174 \begin{verbatim}
 175 /** a description of a ship */
 176 public class ShipDescription implements Iterable<DockDescription> {
 177   public String                        getName();
 178   public Iterable<ConstantDescription> getConstantDescriptions();
 179   public Iterable<DockDescription>    getDockDescriptions();
 180 }
 181
 182 /** a description of a valve */
 183 public class DockDescription {
 184   public String           getName();
 185   public boolean          isInbox();
 186   public boolean          isOutbox();
 187   public DockDescription getShortcut();
 188 }
 189
 190 /** a constant declared by a ship */
 191 public class ConstantDescription {
 192   public final long setbits;
 193   public final long clearbits;
 194   public final boolean signExtend;
 195   public final int numberOffset;
 196   public final int numberWidth;
 197 }
 198 \end{verbatim}
 199
 200
 201 \pagebreak
 202 \section{Instructions}
 203 \subsection{Fleet Assembly Language}
 204
 205 The Fleet Assembly language is designed to be a human-readable
 206 depiction of the bits which comprise a Fleet program.
 207
 208 \subsubsection{Formal Grammar}
 209
 210 The formal syntax is given below.  The metagrammar used is that of the
 211 Scannerless Boolean Parser \cite{sbp}.
 212
 213 \verbatiminput{fleet.g}
 214
 215 \subsubsection{Translation To Machine Code}
 216
 217 Please refer to \cite{ArchMan} for the details of the Fleet
 218 instruction encoding.
 219
 220 As shown in the grammar above, the start symbol for the grammar ({\tt
 221   s}) yields a {\tt Program} surrounded by optional whitespace.  A
 222 program is a sequence of {\tt Directive}s followed by a {\tt
 223   CodeBagBody}.  A {\tt CodeBagBody} consists of zero or more
 224 elements, each of which is either a {\tt Fiber} or a (nested) {\tt
 225   CodeBagDef}.
 226
 227 A {\tt Fiber} is a set of {\tt Instruction}s which all share a common
 228 execution point ({\tt Pump}).  Each instruction can be {\tt unclog},
 229 {\tt clog}, {\tt kill}, {\tt literal}, or a set of {\tt Command}s.  It
 230 should be fairly clear how to translate all but the last sort of
 231 instruction into machine code, based on the encodings in
 232 \cite{ArchMan}.  Take particular note of the fact that {\tt literal}s
 233 may have a {\tt RequeueCount} but not a {\tt RepeatCount}.
 234
 235 The repetition count for an instruction is placed in square brackets
 236 and prefixes the instruction.  The requeueing count for an instruction
 237 is placed at the end of the instruction because, {\it conceptually},
 238 requeueing takes place after the instruction executes.
 239
 240 A {\tt Command} is either {\tt wait}, {\tt nop}, {\tt discard}, {\tt
 241   recieve}, {\tt take}, {\tt deliver}, {\tt send}, {\tt sendto}, {\tt
 242   notify}, or {\tt notifyLast}.  These are compiled as shown below:
 243
 244 \begin{itemize}
 245 \item[\tt nop] is not valid in combination with any other command; it sets all control bits to {\tt 0}
 246 \item[\tt wait] is valid only on an output port, and sets {\tt Ti=1}
 247 \item[\tt discard] sets {\tt Di=1,Dc=0}
 248 \item[\tt recieve] is valid only on an input port, and sets {\tt Di=1,Dc=1}
 249 \item[\tt take] is valid only on an output port, and sets {\tt Di=1,Dc=1}
 250 \item[\tt deliver] is valid only on an input port, and sets {\tt Do=1}
 251 \item[\tt sendto] is valid only on an output port, and sets {\tt Do=1}
 252 \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}
 253 \item[\tt notify] sets {\tt To=1} and is not valid in combination with {\tt send} or {\tt sendto}
 254 \item[\tt notifyLast] sets {\tt To=1,Ig=1} and is not valid in combination with {\tt send} or {\tt sendto}
 255 \end{itemize}
 256
 257 It is an error to specify two commands within a single instruction if
 258 both of the commands attempt to set the same bit, even if they attempt
 259 to set it to the same value.
 260
 261 Note that un-named ``anonymous'' codebags may appear as literals.
 262 This means that it is possible to write interesting programs such as
 263 the one below:
 264
 265 \begin{verbatim}
 266 #ship debug  : Debug
 267 #ship memory : Memory
 268
 269 memory.inCBD: literal {
 270     memory.inCBD: literal {
 271         memory.inCBD: literal {
 272             debug.in:
 273               literal 3;
 274               deliver;
 275           }; deliver;
 276       }; deliver;
 277   }; deliver;
 278 \end{verbatim}
 279
 280
 281
 282
 283 \pagebreak
 284 \subsection{Java API for Fleet Machine Code}
 285
 286 \subsection{Ships}
 287 \begin{verbatim}
 288 public abstract class Ship {
 289
 290     /** return the description for this ship */
 291     public ShipDescription getShipDescription();
 292
 293     /** return all pumps which feed this ship; order is NOT significant */
 294     public Iterable<Dock> getDocks();
 295     public Dock getDock(String s);
 296
 297     /** if this is the 4th fifo ship, this method returns 4 */
 298     public int getOrdinal();
 299
 300     /** return the Fleet that this Ship belongs to, if any */
 301     public Device  getDevice();
 302 }
 303 \end{verbatim}
 304
 305 \subsection{Dock}
 306 \begin{verbatim}
 307 public class Dock {
 308
 309     /** the descriptive name of this pump (relative to its ship) */
 310     public abstract String getName();
 311
 312     /** return the Ship to which this Dock belongs */
 313     public abstract Ship   getShip();
 314
 315     /** the maximum number of instructions we can put in the Dock instruction fifo,
 316      *  or Integer.MAX_VALUE if unbounded */
 317     public abstract int getInstructionFifoLength();
 318
 319     /** returns true if this is an inbox */
 320     public abstract boolean isInbox();
 321
 322     /** returns true if this is an outbox */
 323     public abstract boolean isOutbox();
 324
 325     /** return the Dock which is the destination of this Box's shortcut (if any) */
 326     public Destination getShortcut() { return null; }
 327 }
 328 \end{verbatim}
 329
 330 \subsection{Instructions}
 331 \begin{verbatim}
 332 public abstract class Instruction {
 333     public final Pump pump;
 334
 335     public static class UnClog extends Instruction {
 336     }
 337
 338     public static class Clog extends Instruction {
 339     }
 340
 341     public static abstract class CountingInstruction extends Instruction {
 342         public final int count;
 343         public CountingInstruction decrementCount();
 344     }
 345
 346     public static class Kill extends CountingInstruction {
 347     }
 348
 349     public static class Executable extends CountingInstruction {
 350
 351         public final Destination dest;
 352
 353         public final boolean     tokenIn;
 354         public final boolean     dataIn;
 355         public final boolean     latch;
 356         public final boolean     send;
 357         public final boolean     sendTo;
 358         public final boolean     tokenOut;
 359         public final boolean     requeue;
 360         public final boolean     ignoreUntilLast;
 361
 362         public boolean isStanding();
 363     }
 364
 365     public static class Literal extends CountingInstruction {
 366         public final long literal;
 367     }
 368 }
 369 \end{verbatim}
 370
 371 \pagebreak
 372 \section{Test Cases}
 373
 374 \subsection{Test Case File Format}
 375
 376 The test case file format is quite simple -- it is nothing more than a
 377 regular Fleet assembly language program with {\tt \#expect} statements
 378 to indicate the values which should arrive at the {\tt Debug.in} port
 379 if the test runs correctly.
 380
 381 \subsection{Java API for Controlling Device Under Test}
 382
 383 \subsection{The Device}
 384 \begin{verbatim}
 385 public abstract class Device implements Iterable<Ship> {
 386
 387     /** read a machine-formatted instruction from a file (into a Java object) */
 388     public abstract Instruction
 389        readInstruction(DataInputStream is) throws IOException;
 390
 391     /** write a machine-formatted instruction to a file (from a Java object) */
 392     public abstract void
 393        writeInstruction(DataOutputStream os, Instruction instr) throws IOException;
 394
 395     public abstract Iterator<Ship> iterator();
 396
 397     /** if possible, run the given code and create a FleetProcess */
 398     public FleetProcess run(byte[] code);
 399 }
 400 \end{verbatim}
 401
 402 \subsection{A Running Test}
 403
 404 \begin{verbatim}
 405 /** represents a <i>running</i> "slave" fleet with a debug connection */
 406 public abstract class FleetProcess {
 407
 408     /** dumps an instruction into the fetch unit */
 409     public abstract void invokeInstruction(Instruction i);
 410
 411     /** reads a word back from the debug port */
 412     public abstract long readWord();
 413
 414     public final synchronized void terminate();
 415
 416     public final boolean isTerminated();
 417 }
 418 \end{verbatim}
 419
 420 \end{document}