src/edu/berkeley/fleet/loops/LoopFactory.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 /**
  12  *
  13  *  A helper class for building loops of instructions.
  14  *
  15  *  This class abstracts away:
  16  *    - The maximum size of a loop
  17  *    - The maximum length of a "one shot" instruction sequence
  18  *    - The looping/oneshot bit
  19  *    - The outer loop counter
  20  *    - The inner loop counter (opportunities to use it are auto-detected)
  21  *
  22  *  It also performs various optimizations and provides a more
  23  *  convenient way of managing the predicate/interruptible fields.
  24  *
  25  *  To get the most compact coding, the components of a Move should be
  26  *  performed in this order when possible, with no intervening commands:
  27  *
  28  *    1. recvToken()
  29  *    2. recv()/collect()
  30  *    3. sendToken()
  31  *    4. deliver()/send()
  32  *
  33  */
  34 public class LoopFactory {
  35
  36     public final Dock dock;
  37     public final String friendlyName;
  38     public final int count;
  39     public final boolean torpedoable;
  40
  41     private final Context ctx;
  42     private LoopFactory next = null;
  43     private ArrayList<Instruction> instructions = new ArrayList<Instruction>();
  44
  45     /**
  46      *  Creates a new loop.
  47      *   @arg dock         the dock at which to execute the instructions
  48      *   @arg friendlyName a descriptive string for debugging the compiler
  49      *   @arg prev         a loop for which this is the successor loop (if any)
  50      *   @arg count        the number of times to execute this loop; <tt>0</tt> means continue until torpedoed
  51      */
  52     public LoopFactory(Context ctx, Dock dock, int count) {
  53         this(ctx, dock, count, count==0, dock.toString(), null);
  54     }
  55     public LoopFactory(Context ctx, Dock dock, int count, boolean torpedoable) {
  56         this(ctx, dock, count, torpedoable, dock.toString(), null);
  57     }
  58     public LoopFactory(Context ctx, Dock dock, int count, String friendlyName) {
  59         this(ctx, dock, count, count==0, friendlyName);
  60     }
  61     public LoopFactory(Context ctx, Dock dock, int count, boolean torpedoable, String friendlyName) {
  62         this(ctx, dock, count, torpedoable, friendlyName, null);
  63     }
  64     private LoopFactory(Context ctx, Dock dock, int count, boolean torpedoable, String friendlyName, LoopFactory prev) {
  65         this.ctx = ctx;
  66         this.dock = dock;
  67         this.count = count;
  68         if (count==0 && !torpedoable)
  69             throw new RuntimeException("count==0 loops must be torpedoable");
  70         this.torpedoable = torpedoable;
  71         this.friendlyName = friendlyName;
  72         ctx.loopFactories.add(this);
  73         if (ctx.startupLoopFactories.get(dock) == null)
  74             ctx.startupLoopFactories.put(dock, this);
  75         if (prev != null) {
  76             if (prev.getNext() != null) throw new RuntimeException();
  77             prev.setNext(this);
  78         }
  79     }
  80
  81     public LoopFactory makeNext(int new_count) { return makeNext(new_count, null); }
  82     public LoopFactory makeNext(int new_count, String newFriendlyName) { return makeNext(new_count, new_count==0, newFriendlyName); }
  83     public LoopFactory makeNext(int new_count, boolean newTorpedoable) { return makeNext(new_count, newTorpedoable, null); }
  84     public LoopFactory makeNext(int new_count, boolean newTorpedoable, String newFriendlyName) {
  85         if (next != null) throw new RuntimeException("loop already has a successor");
  86         return new LoopFactory(ctx, dock, new_count, newTorpedoable, newFriendlyName, this);
  87     }
  88     public LoopFactory getNext() { return next; }
  89     private void setNext(LoopFactory next) {
  90         if (this.next != null) throw new RuntimeException("attempt to setNext() twice");
  91         this.next = next;
  92     }
  93
  94
  95     // Building Loops //////////////////////////////////////////////////////////////////////////////
  96
  97     Predicate   predicate = Predicate.Default;
  98     boolean     pending_interruptible = false;
  99     boolean     pending_recvToken = false;
 100     boolean     pending_recvOrCollect = false;
 101     boolean     pending_latchData = false;
 102     boolean     pending_latchPath = false;
 103     boolean     pending_sendToken = false;
 104     Path        pending_path = null;
 105
 106     void flush_pending() { flush_pending(false); }
 107     void flush_pending(boolean pending_dataOut) {
 108         if (!pending_recvToken &&
 109             !pending_recvOrCollect &&
 110             !pending_sendToken &&
 111             !pending_dataOut) {
 112             if (pending_interruptible)
 113                 throw new RuntimeException("abortLoopIfTorpedoPresent() must be followed immediately by a Move");
 114         } else {
 115             instructions.add(new Move(dock,
 116                                       count!=1,
 117                                       predicate,
 118                                       pending_interruptible,
 119                                       pending_path==null ? null : pending_path,
 120                                       pending_recvToken,
 121                                       pending_recvOrCollect,
 122                                       pending_latchData,
 123                                       pending_latchPath,
 124                                       pending_dataOut,
 125                                       pending_sendToken));
 126         }
 127         pending_interruptible = false;
 128         pending_recvToken = false;
 129         pending_recvOrCollect = false;
 130         pending_latchData = false;
 131         pending_latchPath = false;
 132         pending_sendToken = false;
 133         pending_path = null;
 134     }
 135
 136     public void interruptibleNop() {
 137         flush_pending();
 138         instructions.add(new Move(dock,
 139                                   count!=1,
 140                                   predicate,
 141                                   true,
 142                                   null,
 143                                   false,
 144                                   false,
 145                                   false,
 146                                   false,
 147                                   false,
 148                                   false));
 149     }
 150
 151     /** sets the predicate which will be applied to subsequent instructions, or null for the default predicate */
 152     public void setPredicate(Predicate p) {
 153         if (p==null) p = Predicate.Default;
 154         if (predicate==p) return;
 155         flush_pending();
 156         predicate = p;
 157     }
 158
 159     /** must be followed immediately by a move-based instruction */
 160     public void abortLoopIfTorpedoPresent() {
 161         flush_pending();
 162         if (!torpedoable)
 163             throw new RuntimeException("invocation of abortLoopIfTorpedoPresent() in a non-torpedoable LoopFactory");
 164         pending_interruptible = true;
 165     }
 166
 167     /** [either] */
 168     public void recvToken() {
 169         if (pending_recvToken || pending_recvOrCollect || pending_sendToken) flush_pending();
 170         pending_recvToken = true;
 171     }
 172
 173     /** [inboxes only] */
 174     public void recv(boolean latchData, boolean latchPath) {
 175         if (!dock.isInputDock()) throw new RuntimeException("recv() may only be used at input docks");
 176         if (pending_recvOrCollect || pending_sendToken) flush_pending();
 177         pending_recvOrCollect = true;
 178         pending_latchData = latchData;
 179         pending_latchPath = latchPath;
 180     }
 181
 182     /** [outboxes only], will fuse with previous instruction if it was a recvToken() */
 183     public void collect(boolean latchData, boolean latchPath) {
 184         if (!dock.isOutputDock()) throw new RuntimeException("collect() may only be used at output docks");
 185         if (pending_recvOrCollect || pending_sendToken) flush_pending();
 186         pending_recvOrCollect = true;
 187         pending_latchData = latchData;
 188         pending_latchPath = latchPath;
 189     }
 190
 191     /** [either], will fuse with previous instruction if it was a recvToken(), recv(), or collect() */
 192     public void sendToken(Destination dest) { sendToken(dest, null); }
 193     public void sendToken(Destination dest, BitVector signal) {
 194         if (pending_sendToken) flush_pending();
 195         pending_path = dock.getPath(dest, signal);
 196         pending_sendToken = true;
 197     }
 198
 199     /** [inboxes only], will fuse with previous instruction if it was a sendToken() */
 200     public void deliver() {
 201         if (!dock.isInputDock()) throw new RuntimeException("deliver() may only be used at input docks");
 202         flush_pending(true);
 203     }
 204
 205     /** [inboxes only], will fuse with previous instruction if it was a sendToken() */
 206     public void flush() {
 207         if (!dock.isInputDock()) throw new RuntimeException("flush() may only be used at input docks");
 208         flush_pending();
 209         instructions.add(new Instruction.Flush(dock, count!=1, predicate));
 210     }
 211
 212     /** [outboxes only], will fuse with previous instruction if it was a sendToken() */
 213     public void sendWord(Destination dest) { sendWord(dest, null); }
 214     public void sendWord(Destination dest, BitVector signal) {
 215         if (!dock.isOutputDock()) throw new RuntimeException("sendWord() may only be used at output docks");
 216         if (pending_sendToken) flush_pending();
 217         pending_path = dock.getPath(dest, signal);
 218         flush_pending(true);
 219     }
 220
 221     /** sets the data latch to a literal value */
 222     public void literal(BitVector literal) {
 223         // FIXME: code duplication here
 224         // FEATURE: be more intelligent here to avoid shifts if possible?
 225         int counter = 0;
 226         while(counter < dock.getShip().getFleet().getWordWidth()) counter += ctx.fleet.getShiftWidth();
 227         while(counter > 0) {
 228             BitVector temp = new BitVector(dock.getShip().getFleet().getShiftWidth());
 229             for(int i=counter-1; i>=counter-ctx.fleet.getShiftWidth(); i--)
 230                 if (i<literal.length())
 231                     temp.set(i-(counter-ctx.fleet.getShiftWidth()), literal.get(i));
 232             instructions.add(new Shift(dock, count!=1, predicate, temp));
 233             counter -= ctx.fleet.getShiftWidth();
 234         }
 235     }
 236
 237     /** sets the data latch to a literal value */
 238     public void literal(long literal) {
 239         flush_pending();
 240         if (((FleetTwoFleet)ctx.fleet).isSmallEnoughToFit(literal)) {
 241             instructions.add(new Instruction.Set(dock, count!=1, predicate, SetDest.DataLatch, literal));
 242         } else {
 243             int counter = 0;
 244             int extra = 0;
 245             while(counter < dock.getShip().getFleet().getWordWidth()) { extra++; counter += ctx.fleet.getShiftWidth(); }
 246             warn("literal " + literal + " requires " + extra + " instructions");
 247             while(counter > 0) {
 248                 instructions.add(new Shift(dock, count!=1, predicate,
 249                                            new BitVector(dock.getShip().getFleet().getWordWidth())
 250                                            .set(getField(counter-1, counter-ctx.fleet.getShiftWidth(), literal))));
 251                 counter -= ctx.fleet.getShiftWidth();
 252             }
 253         }
 254     }
 255
 256     /** sets the flags */
 257     public void setFlags(Instruction.Set.FlagFunction newFlagA, Instruction.Set.FlagFunction newFlagB) {
 258         flush_pending();
 259         instructions.add(new Instruction.Set(dock,
 260                                              count!=1,
 261                                              predicate,
 262                                              newFlagA,
 263                                              newFlagB));
 264     }
 265
 266     /** abort the loop immediately (if predicate is met) and invoke the successor loop */
 267     public void abort() {
 268         flush_pending();
 269         instructions.add(new Instruction.Set(dock,
 270                                              count!=1,
 271                                              predicate,
 272                                              SetDest.OuterLoopCounter,
 273                                              0));
 274     }
 275
 276     public void abortAndInvoke(LoopFactory lf) {
 277         throw new RuntimeException("not implemented");
 278     }
 279
 280     // Emitting Code //////////////////////////////////////////////////////////////////////////////
 281
 282     void optimize() {
 283         flush_pending();
 284         // FEATURE: find loops of 1 instruction, use ILC
 285         // FEATURE: find sequences of >2 adjacent identical instructions, replace with use of ILC
 286         // FEATURE: after optimizing, find single-instruction loops, replace with use of ILC
 287         // FEATURE: consider doing loop unrolling if two copies of the loop fit in the instruction buffer...
 288         // FEATURE: clever instruction re-oredering?
 289     }
 290
 291     /**
 292      *  The code emitted by this method makes the following assumptions:
 293      *
 294      *   - The instructions emitted are dispatched in order
 295      *   - At the time of dispatch, the dock must be pre-quiescent.
 296      *
 297      */
 298     public void emit(ArrayList<Instruction> ic) {
 299         emit(ic, dock.getInstructionFifoSize());
 300     }
 301     private void emit(ArrayList<Instruction> ic, int capacity) {
 302         flush_pending();
 303         optimize();
 304
 305         // the number of instructions after and including the first blocking instruction
 306         int numInstructionsNotIncludingNonblockingPrefix = 0;
 307         int loopSize = 0;
 308         boolean blockingInstructionEncountered = false;
 309
 310         // Set the OLC (it might previously have been zero)
 311         ic.add(new Set(dock, false, Predicate.IgnoreFlagD, SetDest.OuterLoopCounter, count==0 ? 1 : count));
 312         if (count!=1) {
 313             ic.add(new Instruction.Head(dock));
 314         }
 315
 316         for(Instruction i : instructions) {
 317             if (i instanceof Move && (((Move)i).tokenIn || ((Move)i).dataIn))
 318                 blockingInstructionEncountered = true;
 319             if (blockingInstructionEncountered)
 320                 numInstructionsNotIncludingNonblockingPrefix++;
 321             loopSize++;
 322             ic.add(i);
 323         }
 324
 325         if (count==1) {
 326             if (numInstructionsNotIncludingNonblockingPrefix > capacity)
 327                 throw new RuntimeException("instruction sequence is too long for instruction fifo at " + dock);
 328         } else {
 329             if (count != 0) {
 330                 ic.add(new Instruction.Set(dock, true, Predicate.Default, SetDest.OuterLoopCounter, SetSource.Decrement));
 331                 if (blockingInstructionEncountered)
 332                     numInstructionsNotIncludingNonblockingPrefix++;
 333                 loopSize++;
 334             }
 335         }
 336         if (count!=1)
 337             ic.add(new Instruction.Abort(dock, Predicate.FlagD));
 338         if (ctx.autoflush && next==null && dock.isInputDock())
 339             ic.add(new Instruction.Flush(dock, true, Predicate.FlagD));
 340
 341         // FIXME: need to somehow deal with count!=0 loops that are
 342         // torpedoable; they need to wait for a torpedo to arrive
 343         // after exhausting their count.
 344
 345         if (count!=1) {
 346             ic.add(new Instruction.Tail(dock));
 347             if (loopSize > capacity)
 348                 throw new RuntimeException("instruction loop is too long for instruction fifo");
 349         }
 350
 351         if (next != null) {
 352             if (count != 1) throw new RuntimeException("no support for successor loops when count!=1 yet");
 353             next.emit(ic, capacity - loopSize);
 354         }
 355     }
 356
 357     void warn(String warning) {
 358         System.err.println("warning: " + warning);
 359     }
 360
 361     // Helpers //////////////////////////////////////////////////////////////////////////////
 362
 363     public void recvWord() { recv(true, false); }
 364     public void recvPath() { recv(false, true); }
 365     public void recvPacket() { recv(true, true); }
 366     public void collectWord() { collect(true, false); }
 367     public void collectPath() { collect(false, true); }
 368     public void collectPacket() { collect(true, true); }
 369
 370 }