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 CodeBag 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     LoopFactory(CodeBag ctx, Dock dock, int count) {
  53         this(ctx, dock, count, count==0, dock.toString(), null);
  54     }
  55     LoopFactory(CodeBag ctx, Dock dock, int count, boolean torpedoable) {
  56         this(ctx, dock, count, torpedoable, dock.toString(), null);
  57     }
  58     LoopFactory(CodeBag ctx, Dock dock, int count, String friendlyName) {
  59         this(ctx, dock, count, count==0, friendlyName);
  60     }
  61     LoopFactory(CodeBag ctx, Dock dock, int count, boolean torpedoable, String friendlyName) {
  62         this(ctx, dock, count, torpedoable, friendlyName, null);
  63     }
  64     private LoopFactory(CodeBag 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         if (ctx.isSealed()) throw new RuntimeException("context already sealed");
  92         this.next = next;
  93     }
  94
  95
  96     // Building Loops //////////////////////////////////////////////////////////////////////////////
  97
  98     Predicate   predicate = Predicate.Default;
  99     boolean     pending_interruptible = false;
 100     boolean     pending_recvToken = false;
 101     boolean     pending_recvOrCollect = false;
 102     boolean     pending_latchData = false;
 103     boolean     pending_latchPath = false;
 104     boolean     pending_sendToken = false;
 105     Path        pending_path = null;
 106
 107     private void addInstruction(Instruction inst) {
 108         if (ctx.isSealed()) throw new RuntimeException("context already sealed");
 109         instructions.add(inst);
 110     }
 111
 112     void flush_pending() { flush_pending(false); }
 113     void flush_pending(boolean pending_dataOut) {
 114         if (!pending_recvToken &&
 115             !pending_recvOrCollect &&
 116             !pending_sendToken &&
 117             !pending_dataOut) {
 118             /*
 119             if (pending_interruptible)
 120                 throw new RuntimeException("abortLoopIfTorpedoPresent() must be followed immediately by a Move (in LoopFactory for dock " + dock + ")");
 121             */
 122         } else {
 123             addInstruction(new Move(dock,
 124                                       predicate,
 125                                       pending_interruptible,
 126                                       pending_path==null ? null : pending_path,
 127                                       pending_recvToken,
 128                                       pending_recvOrCollect,
 129                                       pending_latchData,
 130                                       pending_latchPath,
 131                                       pending_dataOut,
 132                                       pending_sendToken));
 133         }
 134         pending_interruptible = false;
 135         pending_recvToken = false;
 136         pending_recvOrCollect = false;
 137         pending_latchData = false;
 138         pending_latchPath = false;
 139         pending_sendToken = false;
 140         pending_path = null;
 141     }
 142
 143     public void interruptibleNop() {
 144         flush_pending();
 145         addInstruction(new Move(dock,
 146                                   predicate,
 147                                   true,
 148                                   null,
 149                                   false,
 150                                   false,
 151                                   false,
 152                                   false,
 153                                   false,
 154                                   false));
 155     }
 156
 157     /** sets the predicate which will be applied to subsequent instructions, or null for the default predicate */
 158     public void setPredicate(Predicate p) {
 159         if (p==null) p = Predicate.Default;
 160         if (predicate==p) return;
 161         flush_pending();
 162         predicate = p;
 163     }
 164
 165     /** must be followed immediately by a move-based instruction */
 166     public void abortLoopIfTorpedoPresent() {
 167         flush_pending();
 168         if (!torpedoable)
 169             throw new RuntimeException("invocation of abortLoopIfTorpedoPresent() in a non-torpedoable LoopFactory");
 170         pending_interruptible = true;
 171     }
 172
 173     /** [either] */
 174     public void recvToken() {
 175         if (pending_recvToken || pending_recvOrCollect || pending_sendToken) flush_pending();
 176         pending_recvToken = true;
 177     }
 178
 179     /** [inboxes only] */
 180     public void recv(boolean latchData, boolean latchPath) {
 181         if (!dock.isInputDock()) throw new RuntimeException("recv() may only be used at input docks");
 182         if (pending_recvOrCollect || pending_sendToken) flush_pending();
 183         pending_recvOrCollect = true;
 184         pending_latchData = latchData;
 185         pending_latchPath = latchPath;
 186     }
 187
 188     /** [outboxes only], will fuse with previous instruction if it was a recvToken() */
 189     public void collect(boolean latchData, boolean latchPath) {
 190         if (!dock.isOutputDock()) throw new RuntimeException("collect() may only be used at output docks");
 191         if (pending_recvOrCollect || pending_sendToken) flush_pending();
 192         pending_recvOrCollect = true;
 193         pending_latchData = latchData;
 194         pending_latchPath = latchPath;
 195     }
 196
 197     /** [either], will fuse with previous instruction if it was a recvToken(), recv(), or collect() */
 198     public void sendToken(Destination dest) { sendToken(dest, null); }
 199     public void sendToken(Destination dest, BitVector signal) {
 200         if (pending_sendToken) flush_pending();
 201         pending_path = dock.getPath(dest, signal);
 202         pending_sendToken = true;
 203     }
 204     public void sendToken(Dock dock) { sendToken(dock.getDataDestination()); }
 205     public void sendToken(Dock dock, BitVector signal) { sendToken(dock.getDataDestination(), signal); }
 206
 207     public void sendTorpedo(Dock dock) { sendToken(dock.getInstructionDestination()); }
 208
 209     /** [inboxes only], will fuse with previous instruction if it was a sendToken() */
 210     public void deliver() {
 211         if (!dock.isInputDock()) throw new RuntimeException("deliver() may only be used at input docks");
 212         flush_pending(true);
 213     }
 214
 215     /** [inboxes only], will fuse with previous instruction if it was a sendToken() */
 216     public void flush() {
 217         if (!dock.isInputDock()) throw new RuntimeException("flush() may only be used at input docks");
 218         flush_pending();
 219         addInstruction(new Instruction.Flush(dock, predicate));
 220     }
 221
 222     /** [outboxes only], will fuse with previous instruction if it was a sendToken() */
 223     public void sendWord(Destination dest) { sendWord(dest, null); }
 224     public void sendWord(Destination dest, BitVector signal) {
 225         if (!dock.isOutputDock()) throw new RuntimeException("sendWord() may only be used at output docks");
 226         if (pending_sendToken) flush_pending();
 227         pending_path = dest==null ? null : dock.getPath(dest, signal);
 228         flush_pending(true);
 229     }
 230     public void sendWord(Dock dock) { sendWord(dock.getDataDestination()); }
 231     public void sendWord(Dock dock, BitVector signal) { sendWord(dock.getDataDestination(), signal); }
 232     public void sendPacket() { sendWord((Destination)null); }
 233
 234     public void literal(String constantName) {
 235         literal(dock.getConstant(constantName));
 236     }
 237
 238     /** sets the data latch to a literal value */
 239     public void literal(final DeferredBitVector literal) {
 240         flush_pending();
 241         if (literal instanceof BitVector) {
 242             BitVector bv = (BitVector)literal;
 243             boolean can_use_set = true;
 244             for(int i=ctx.fleet.getSetWidth(); i<bv.length(); i++)
 245                 if (bv.get(i)!=bv.get(ctx.fleet.getSetWidth()-1)) {
 246                     can_use_set = false;
 247                     break;
 248                 }
 249             if (can_use_set) {
 250                 addInstruction(new Instruction.Set(dock, predicate, SetDest.DataLatch, bv.toLong()));
 251                 return;
 252             }
 253         }
 254
 255         int counter = 0;
 256         while(counter < dock.getShip().getFleet().getWordWidth()) counter += ctx.fleet.getShiftWidth();
 257         while(counter > 0) {
 258             final int counter_f = counter;
 259             DeferredBitVector temp = new DeferredBitVector() {
 260                     public BitVector getBitVector() {
 261                         BitVector bv = literal.getBitVector();
 262                         BitVector ret = new BitVector(dock.getShip().getFleet().getShiftWidth());
 263                         for(int i=counter_f-1; i>=counter_f-ctx.fleet.getShiftWidth(); i--)
 264                             if (i<bv.length())
 265                                 ret.set(i-(counter_f-ctx.fleet.getShiftWidth()), bv.get(i));
 266                         return ret;
 267                     }
 268                 };
 269             Shift shift = new Shift(dock, predicate, temp);
 270             addInstruction(shift);
 271             counter -= ctx.fleet.getShiftWidth();
 272         }
 273     }
 274
 275     /** sets the data latch to a literal value */
 276     public void literal(long literal) {
 277         literal(new BitVector(ctx.fleet.getWordWidth()).set(literal));
 278     }
 279
 280     /** sets the data latch to a code bag descriptor */
 281     public void literal(CodeBag cb) {
 282         literal(cb.getDescriptor());
 283     }
 284
 285     /** sets the flags */
 286     public void setFlags(Instruction.Set.FlagFunction newFlagA, Instruction.Set.FlagFunction newFlagB) {
 287         flush_pending();
 288         addInstruction(new Instruction.Set(dock,
 289                                              predicate,
 290                                              newFlagA,
 291                                              newFlagB));
 292     }
 293
 294     /** abort the loop immediately (if predicate is met) and invoke the successor loop */
 295     public void abort() {
 296         flush_pending();
 297         addInstruction(new Instruction.Set(dock,
 298                                              predicate,
 299                                              SetDest.OuterLoopCounter,
 300                                              0));
 301     }
 302
 303     // Emitting Code //////////////////////////////////////////////////////////////////////////////
 304
 305     void optimize() {
 306         flush_pending();
 307         // FEATURE: find sequences of >2 adjacent identical instructions, replace with use of ILC
 308         //          (requires Instruction.equals() be implemented)
 309         // FEATURE: consider doing loop unrolling if two copies of the loop fit in the instruction buffer...
 310         // FEATURE: clever instruction re-oredering?
 311     }
 312
 313     /**
 314      *  The code emitted by this method makes the following assumptions:
 315      *
 316      *   - The instructions emitted are dispatched in order
 317      *   - At the time of dispatch, the dock must be pre-quiescent.
 318      *
 319      */
 320     public void emit(ArrayList<Instruction> ic) {
 321         emit(ic, dock.getInstructionFifoSize());
 322     }
 323     private void emit(ArrayList<Instruction> ic, int capacity) {
 324         flush_pending();
 325         optimize();
 326
 327         // the number of instructions after and including the first blocking instruction
 328         int numInstructionsNotIncludingNonblockingPrefix = 0;
 329         int loopSize = 0;
 330         boolean blockingInstructionEncountered = false;
 331
 332         // Set the OLC (it might previously have been zero)
 333         ic.add(new Set(dock, Predicate.IgnoreFlagD, SetDest.OuterLoopCounter, count==0 ? 1 : count));
 334
 335         boolean olc_loop = count!=1;
 336         /*
 337         if (count != 1 &&
 338             (count==0 || count <= 63) &&
 339             instructions.size()==1 &&
 340             (instructions.get(0) instanceof Instruction.Move)) {
 341             olc_loop = false;
 342             if (count==0)
 343                 ic.add(new Instruction.Set(dock, Predicate.Default,
 344                                            SetDest.InnerLoopCounter, SetSource.Infinity));
 345             else
 346                 ic.add(new Instruction.Set(dock, Predicate.Default,
 347                                            SetDest.InnerLoopCounter, count));
 348         }
 349         */
 350
 351         if (olc_loop) {
 352             ic.add(new Instruction.Head(dock));
 353         }
 354
 355         boolean firstTime = true;
 356         while(true) {
 357             for(Instruction i : instructions) {
 358                 if (!firstTime && i.predicate==Predicate.FlagD) continue;
 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             if (count!=0) break;
 367             if (instructions.size()+loopSize+3 > capacity) break;
 368             firstTime = false;
 369             break;
 370             //System.out.println("packing the loop!");
 371         }
 372
 373         if (!olc_loop) {
 374             if (numInstructionsNotIncludingNonblockingPrefix > capacity)
 375                 throw new RuntimeException("instruction sequence is too long for instruction fifo at " +
 376                                            dock + " ("+numInstructionsNotIncludingNonblockingPrefix+">"+capacity+")");
 377         } else {
 378             if (count != 0) {
 379                 ic.add(new Instruction.Set(dock, Predicate.Default, SetDest.OuterLoopCounter, SetSource.Decrement));
 380                 if (blockingInstructionEncountered)
 381                     numInstructionsNotIncludingNonblockingPrefix++;
 382                 loopSize++;
 383             }
 384         }
 385         if (olc_loop) {
 386             ic.add(new Instruction.Abort(dock, Predicate.FlagD));
 387             loopSize++;
 388         }
 389         if (ctx.autoflush && next==null && dock.isInputDock()) {
 390             ic.add(new Instruction.Flush(dock, Predicate.FlagD));
 391             loopSize++;
 392         }
 393
 394         // FIXME: need to somehow deal with count!=0 loops that are
 395         // torpedoable; they need to wait for a torpedo to arrive
 396         // after exhausting their count.
 397
 398         if (olc_loop) {
 399             ic.add(new Instruction.Tail(dock));
 400             if (loopSize > capacity)
 401                 throw new RuntimeException("instruction loop is too long for instruction fifo at " +
 402                                            dock + " ("+loopSize+">"+capacity+")");
 403         }
 404
 405         if (next != null) {
 406             if (!olc_loop) {
 407                 next.emit(ic, capacity - numInstructionsNotIncludingNonblockingPrefix);
 408             } else {
 409                 //next.emit(ic, capacity - loopSize);
 410                 throw new RuntimeException("no support for successor loops when count!=1 yet");
 411             }
 412         }
 413     }
 414
 415     void warn(String warning) {
 416         System.err.println("warning: " + warning);
 417     }
 418
 419     // Helpers //////////////////////////////////////////////////////////////////////////////
 420
 421     public void recvWord() { recv(true, false); }
 422     public void recvPath() { recv(false, true); }
 423     public void recvPacket() { recv(true, true); }
 424     public void collectWord() { collect(true, false); }
 425     public void collectPath() { collect(false, true); }
 426     public void collectPacket() { collect(true, true); }
 427
 428 }