src/edu/berkeley/fleet/loops/Context.java

   1 package edu.berkeley.fleet.loops;
   2 import java.util.*;
   3 import java.net.*;
   4 import edu.berkeley.fleet.two.*;
   5 import edu.berkeley.fleet.api.*;
   6 import edu.berkeley.fleet.api.Instruction.*;
   7 import edu.berkeley.fleet.api.Instruction.Set;
   8 import edu.berkeley.fleet.api.Instruction.Set.*;
   9 import static edu.berkeley.fleet.util.BitManipulations.*;
  10
  11 // QUESTION: does each dock mentioned by a context have a linear chain
  12 // of loops, or can it branch?
  13
  14 //    - or should we use "sub-contexts" for that
  15 //        - advantage: it lets us convey the fact that a bunch of loops are dispatched together
  16 //    - should loops have an "invoke context" opcode?
  17
  18 /**
  19  *  A Context is a collection of Loops which obey these rules:
  20  *
  21  *    - A Context has exclusive control of all docks mentioned by any of its Loops.
  22  *    - A Context includes a "starting loop" for every dock it mentions.
  23  *    - When a Context is spawned, it starts the "starting loop" on all of its docks.
  24  *    - A loop may or may not have a successor.
  25  *    - Control may transfer only two ways:
  26  *        - If a loop has a successor, control will transfer to the successor when the loop finishes.
  27  *        - A loop may explicitly transfer control to another loop via abortAndInvoke().  The
  28  *          invoked loop must belong to the same Dock and the same Context.
  29  *    - A Context finishes when all of its docks have finished executing a loop with no successor.
  30  *
  31  *  Definitions:
  32  *    - A Move instruction is a blocking instruction if either its   tokenIn or dataIn bits are set.
  33  *    - All other instructions  are non-blocking.
  34  *    - A dock is quiescent if its instruction ring is empty.
  35  *    - A dock is pre-quiescent if
  36  *        - all instructions which remain in the target dock's instruction
  37  *          fifo are nonblocking instructions,
  38  *        - either the docks' OLC=0 or all instructions which remain
  39  *          in its instruction fifo are one-shot instructions
  40  *        - after executing these remaining instructions, the dock's hatch is open
  41  */
  42 public class Context {
  43     private HashMap<Dock,LoopFactory> startupLoopFactories = new HashMap<Dock,LoopFactory>();
  44     private HashSet<LoopFactory> loopFactories = new HashSet<LoopFactory>();
  45
  46     public final Fleet fleet;
  47     public Context(Fleet fleet) { this.fleet = fleet; }
  48
  49     private boolean autoflush = false;
  50     public void setAutoflush(boolean a) { this.autoflush = a; }
  51
  52     // FIXME: ability for a group of Contexts to share an "allocation
  53     // pool" because they will run concurrently.
  54     public HashSet<Ship>             allocatedShips       = new HashSet<Ship>();
  55
  56     public Ship allocateShip(String name) {
  57         for(int i=0; ; i++) {
  58             Ship ship = fleet.getShip(name, i);
  59             if (ship==null)
  60                 throw new RuntimeException("no more ships of type " + name);
  61             if (allocatedShips.contains(ship)) continue;
  62             allocatedShips.add(ship);
  63             return ship;
  64         }
  65     }
  66
  67     // FIXME: is it legitimate to send a torpedo to a count==1 loop?
  68     // FIXME: is it legitimate to send a torpedo to a count>1  loop?
  69     /**
  70      *
  71      *  A helper class for building loops of instructions.
  72      *
  73      *  This class abstracts away:
  74      *    - The maximum size of a loop
  75      *    - The maximum length of a "one shot" instruction sequence
  76      *    - The looping/oneshot bit
  77      *    - The outer loop counter
  78      *    - The inner loop counter (opportunities to use it are auto-detected)
  79      *
  80      *  It also performs various optimizations and provides a more
  81      *  convenient way of managing the predicate/interruptible fields.
  82      *
  83      *  To get the most compact coding, the components of a Move should be
  84      *  performed in this order when possible, with no intervening commands:
  85      *
  86      *    1. recvToken()
  87      *    2. recv()/collect()
  88      *    3. sendToken()
  89      *    4. deliver()/send()
  90      *
  91      */
  92     public class LoopFactory {
  93
  94     // FIXME: vet this to see if it is sensible
  95     private boolean instructionFifoSizeCheckDisabled = false;
  96     public void disableInstructionFifoOverflowCheck() { instructionFifoSizeCheckDisabled = true; }
  97
  98         public final Dock dock;
  99         public final String friendlyName;
 100         public final int count;
 101         private Predicate predicate = Predicate.Default;
 102         private LoopFactory next = null;
 103         private ArrayList<Instruction> instructions = new ArrayList<Instruction>();
 104
 105         /**
 106          *  Creates a new loop.
 107          *   @arg dock         the dock at which to execute the instructions
 108          *   @arg friendlyName a descriptive string for debugging the compiler
 109          *   @arg prev         a loop for which this is the successor loop (if any)
 110          *   @arg count        the number of times to execute this loop; <tt>0</tt> means continue until torpedoed
 111          */
 112         public LoopFactory(Dock dock, int count) { this(dock, count, dock.toString(), null); }
 113         public LoopFactory(Dock dock, int count, String friendlyName) { this(dock, count, friendlyName, null); }
 114         private LoopFactory(Dock dock, int count, String friendlyName, LoopFactory prev) {
 115             this.dock = dock;
 116             this.count = count;
 117             this.friendlyName = friendlyName;
 118             Context.this.loopFactories.add(this);
 119             if (Context.this.startupLoopFactories.get(dock) == null)
 120                 Context.this.startupLoopFactories.put(dock, this);
 121             if (prev != null) {
 122                 if (prev.getNext() != null) throw new RuntimeException();
 123                 prev.setNext(this);
 124             }
 125         }
 126
 127         public LoopFactory makeNext(int new_count) { return makeNext(new_count, null); }
 128         public LoopFactory makeNext(int new_count, String newFriendlyName) {
 129             if (next != null) throw new RuntimeException("loop already has a successor");
 130             return new LoopFactory(dock, new_count, newFriendlyName, this);
 131         }
 132         public LoopFactory getNext() { return next; }
 133         private void setNext(LoopFactory next) {
 134             if (this.next != null) throw new RuntimeException("attempt to setNext() twice");
 135             this.next = next;
 136         }
 137
 138
 139         // Building Loops //////////////////////////////////////////////////////////////////////////////
 140
 141         boolean     pending_interruptible = false;
 142         boolean     pending_recvToken = false;
 143         boolean     pending_recvOrCollect = false;
 144         boolean     pending_latchData = false;
 145         boolean     pending_latchPath = false;
 146         boolean     pending_sendToken = false;
 147         Path        pending_path = null;
 148
 149         void flush_pending() { flush_pending(false); }
 150         void flush_pending(boolean pending_dataOut) {
 151             if (!pending_recvToken &&
 152                 !pending_recvOrCollect &&
 153                 !pending_sendToken &&
 154                 !pending_dataOut) {
 155                 if (pending_interruptible)
 156                     throw new RuntimeException("abortLoopIfTorpedoPresent() must be followed immediately by a Move");
 157             } else {
 158                 instructions.add(new Move(dock,
 159                                           count!=1,
 160                                           predicate,
 161                                           pending_interruptible,
 162                                           pending_path==null ? null : pending_path,
 163                                           pending_recvToken,
 164                                           pending_recvOrCollect,
 165                                           pending_latchData,
 166                                           pending_latchPath,
 167                                           pending_dataOut,
 168                                           pending_sendToken));
 169             }
 170             pending_interruptible = false;
 171             pending_recvToken = false;
 172             pending_recvOrCollect = false;
 173             pending_latchData = false;
 174             pending_latchPath = false;
 175             pending_sendToken = false;
 176             pending_path = null;
 177         }
 178
 179         public void interruptibleNop() {
 180             flush_pending();
 181             instructions.add(new Move(dock,
 182                                       count!=1,
 183                                       predicate,
 184                                       true,
 185                                       null,
 186                                       false,
 187                                       false,
 188                                       false,
 189                                       false,
 190                                       false,
 191                                       false));
 192         }
 193
 194         /** sets the predicate which will be applied to subsequent instructions, or null for the default predicate */
 195         public void setPredicate(Predicate p) {
 196             if (p==null) p = Predicate.Default;
 197             if (predicate==p) return;
 198             flush_pending();
 199             predicate = p;
 200         }
 201
 202         /** must be followed immediately by a move-based instruction */
 203         public void abortLoopIfTorpedoPresent() {
 204             flush_pending();
 205             //if (count!=0) throw new RuntimeException("currently, only forever-loops may be sensitive to torpedoes");
 206             pending_interruptible = true;
 207         }
 208
 209         /** [either] */
 210         public void recvToken() {
 211             if (pending_recvToken || pending_recvOrCollect || pending_sendToken) flush_pending();
 212             pending_recvToken = true;
 213         }
 214
 215         /** [inboxes only] */
 216         public void recv(boolean latchData, boolean latchPath) {
 217             if (!dock.isInputDock()) throw new RuntimeException("recv() may only be used at input docks");
 218             if (pending_recvOrCollect || pending_sendToken) flush_pending();
 219             pending_recvOrCollect = true;
 220             pending_latchData = latchData;
 221             pending_latchPath = latchPath;
 222         }
 223
 224         /** [outboxes only], will fuse with previous instruction if it was a recvToken() */
 225         public void collect(boolean latchData, boolean latchPath) {
 226             if (!dock.isOutputDock()) throw new RuntimeException("collect() may only be used at output docks");
 227             if (pending_recvOrCollect || pending_sendToken) flush_pending();
 228             pending_recvOrCollect = true;
 229             pending_latchData = latchData;
 230             pending_latchPath = latchPath;
 231         }
 232
 233         /** [either], will fuse with previous instruction if it was a recvToken(), recv(), or collect() */
 234         public void sendToken(Destination dest) { sendToken(dest, null); }
 235         public void sendToken(Destination dest, BitVector signal) {
 236             if (pending_sendToken) flush_pending();
 237             pending_path = dock.getPath(dest, signal);
 238             pending_sendToken = true;
 239         }
 240
 241         /** [inboxes only], will fuse with previous instruction if it was a sendToken() */
 242         public void deliver() {
 243             if (!dock.isInputDock()) throw new RuntimeException("deliver() may only be used at input docks");
 244             flush_pending(true);
 245         }
 246
 247         /** [inboxes only], will fuse with previous instruction if it was a sendToken() */
 248         public void flush() {
 249             if (!dock.isInputDock()) throw new RuntimeException("flush() may only be used at input docks");
 250             flush_pending();
 251             instructions.add(new Instruction.Flush(dock, count!=1, predicate));
 252         }
 253
 254         /** [outboxes only], will fuse with previous instruction if it was a sendToken() */
 255         public void sendWord(Destination dest) { sendWord(dest, null); }
 256         public void sendWord(Destination dest, BitVector signal) {
 257             if (!dock.isOutputDock()) throw new RuntimeException("sendWord() may only be used at output docks");
 258             if (pending_sendToken) flush_pending();
 259             pending_path = dock.getPath(dest, signal);
 260             flush_pending(true);
 261         }
 262
 263         /** sets the data latch to a literal value */
 264         public void literal(BitVector literal) {
 265             // FIXME: code duplication here
 266             // FIXME: be more intelligent here to avoid shifts if possible?
 267             int counter = 0;
 268             while(counter < dock.getShip().getFleet().getWordWidth()) counter += fleet.getShiftWidth();
 269             while(counter > 0) {
 270                 BitVector temp = new BitVector(dock.getShip().getFleet().getShiftWidth());
 271                 for(int i=counter-1; i>=counter-fleet.getShiftWidth(); i--)
 272                     if (i<literal.length())
 273                         temp.set(i-(counter-fleet.getShiftWidth()), literal.get(i));
 274                 instructions.add(new Shift(dock, count!=1, predicate, temp));
 275                 counter -= fleet.getShiftWidth();
 276             }
 277         }
 278
 279         /** sets the data latch to a literal value */
 280         public void literal(long literal) {
 281             flush_pending();
 282             if (((FleetTwoFleet)fleet).isSmallEnoughToFit(literal)) {
 283                 instructions.add(new Instruction.Set(dock, count!=1, predicate, SetDest.DataLatch, literal));
 284             } else {
 285                 int counter = 0;
 286                 int extra = 0;
 287                 while(counter < dock.getShip().getFleet().getWordWidth()) { extra++; counter += fleet.getShiftWidth(); }
 288                 warn("literal " + literal + " requires " + extra + " instructions");
 289                 while(counter > 0) {
 290                     instructions.add(new Shift(dock, count!=1, predicate,
 291                                                new BitVector(dock.getShip().getFleet().getWordWidth())
 292                                                .set(getField(counter-1, counter-fleet.getShiftWidth(), literal))));
 293                     counter -= fleet.getShiftWidth();
 294                 }
 295             }
 296         }
 297
 298         /** sets the flags */
 299         public void setFlags(Instruction.Set.FlagFunction newFlagA, Instruction.Set.FlagFunction newFlagB) {
 300             flush_pending();
 301             instructions.add(new Instruction.Set(dock,
 302                                                  count!=1,
 303                                                  predicate,
 304                                                  newFlagA,
 305                                                  newFlagB));
 306         }
 307
 308         // FIXME: what if we're using an ILC-loop?
 309         /** abort the loop immediately (if predicate is met) and invoke the successor loop */
 310         public void abort() {
 311             flush_pending();
 312             instructions.add(new Instruction.Set(dock,
 313                                                  count!=1,
 314                                                  predicate,
 315                                                  SetDest.OuterLoopCounter,
 316                                                  0));
 317         }
 318
 319         public void abortAndInvoke(LoopFactory lf) {
 320             throw new RuntimeException("not implemented");
 321         }
 322
 323         // Emitting Code //////////////////////////////////////////////////////////////////////////////
 324
 325         void optimize() {
 326             flush_pending();
 327             // FEATURE: find loops of 1 instruction, use ILC
 328             // FEATURE: find sequences of >2 adjacent identical instructions, replace with use of ILC
 329             // FEATURE: after optimizing, find single-instruction loops, replace with use of ILC
 330             // FEATURE: consider doing loop unrolling if two copies of the loop fit in the instruction buffer...
 331             // FEATURE: clever instruction re-oredering?
 332         }
 333
 334         /**
 335          *  The code emitted by this method makes the following assumptions:
 336          *
 337          *   - The instructions emitted are dispatched in order
 338          *   - At the time of dispatch, the dock must be pre-quiescent.
 339          *
 340          */
 341         public void emit(ArrayList<Instruction> ic) {
 342             flush_pending();
 343             optimize();
 344
 345             // FIXME: if this loop is a count==1 loop, we can emit the successor loop along with it...
 346
 347             // the number of instructions after and including the first blocking instruction
 348             int numInstructionsNotIncludingNonblockingPrefix = 0;
 349             int loopSize = 0;
 350             boolean blockingInstructionEncountered = false;
 351
 352             // Set the OLC (it might previously have been zero)
 353             ic.add(new Set(dock, false, Predicate.IgnoreFlagD, SetDest.OuterLoopCounter, count==0 ? 1 : count));
 354             if (count!=1) {
 355                 ic.add(new Instruction.Head(dock));
 356             }
 357
 358             for(Instruction i : instructions) {
 359                 if (i instanceof Move && (((Move)i).tokenIn || ((Move)i).dataIn))
 360                     blockingInstructionEncountered = true;
 361                 if (blockingInstructionEncountered)
 362                     numInstructionsNotIncludingNonblockingPrefix++;
 363                 loopSize++;
 364                 ic.add(i);
 365             }
 366
 367             if (count==1) {
 368                 if (!instructionFifoSizeCheckDisabled &&
 369                     numInstructionsNotIncludingNonblockingPrefix > dock.getInstructionFifoSize())
 370                     throw new RuntimeException("instruction sequence is too long for instruction fifo at " + dock);
 371             } else {
 372                 if (count != 0) {
 373                     ic.add(new Instruction.Set(dock, true, Predicate.Default, SetDest.OuterLoopCounter, SetSource.Decrement));
 374                     if (blockingInstructionEncountered)
 375                         numInstructionsNotIncludingNonblockingPrefix++;
 376                     loopSize++;
 377                 }
 378             }
 379             if (count!=1) {
 380                 ic.add(new Instruction.Abort(dock, Predicate.FlagD));
 381             }
 382             if (autoflush && !"Debug".equals(dock.getShip().getType()) && next==null) {
 383                 if (dock.isInputDock())
 384                     ic.add(new Instruction.Flush(dock, true, Predicate.FlagD));
 385             }
 386             if (count!=1) {
 387                 ic.add(new Instruction.Tail(dock));
 388                 if (!instructionFifoSizeCheckDisabled &&
 389                     loopSize > dock.getInstructionFifoSize())
 390                     throw new RuntimeException("instruction loop is too long for instruction fifo");
 391             }
 392
 393             if (next != null) {
 394                 if (count != 1) throw new RuntimeException("no support for successor loops when count!=1 yet");
 395                 // FIXME: must include check based on reduced FIFO capacity
 396                 // FIXME: review this
 397                 next.emit(ic);
 398             }
 399         }
 400
 401         void warn(String warning) {
 402             System.err.println("warning: " + warning);
 403         }
 404
 405         // Helpers //////////////////////////////////////////////////////////////////////////////
 406
 407         public void recvWord() { recv(true, false); }
 408         public void recvPath() { recv(false, true); }
 409         public void recvPacket() { recv(true, true); }
 410         public void collectWord() { collect(true, false); }
 411         public void collectPath() { collect(false, true); }
 412         public void collectPacket() { collect(true, true); }
 413
 414     }
 415
 416     public void emit(ArrayList<Instruction> ic) {
 417         for(LoopFactory lf : startupLoopFactories.values())
 418             lf.emit(ic);
 419     }
 420
 421 }