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