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                                       predicate,
 117                                       pending_interruptible,
 118                                       pending_path==null ? null : pending_path,
 119                                       pending_recvToken,
 120                                       pending_recvOrCollect,
 121                                       pending_latchData,
 122                                       pending_latchPath,
 123                                       pending_dataOut,
 124                                       pending_sendToken));
 125         }
 126         pending_interruptible = false;
 127         pending_recvToken = false;
 128         pending_recvOrCollect = false;
 129         pending_latchData = false;
 130         pending_latchPath = false;
 131         pending_sendToken = false;
 132         pending_path = null;
 133     }
 134
 135     public void interruptibleNop() {
 136         flush_pending();
 137         instructions.add(new Move(dock,
 138                                   predicate,
 139                                   true,
 140                                   null,
 141                                   false,
 142                                   false,
 143                                   false,
 144                                   false,
 145                                   false,
 146                                   false));
 147     }
 148
 149     /** sets the predicate which will be applied to subsequent instructions, or null for the default predicate */
 150     public void setPredicate(Predicate p) {
 151         if (p==null) p = Predicate.Default;
 152         if (predicate==p) return;
 153         flush_pending();
 154         predicate = p;
 155     }
 156
 157     /** must be followed immediately by a move-based instruction */
 158     public void abortLoopIfTorpedoPresent() {
 159         flush_pending();
 160         if (!torpedoable)
 161             throw new RuntimeException("invocation of abortLoopIfTorpedoPresent() in a non-torpedoable LoopFactory");
 162         pending_interruptible = true;
 163     }
 164
 165     /** [either] */
 166     public void recvToken() {
 167         if (pending_recvToken || pending_recvOrCollect || pending_sendToken) flush_pending();
 168         pending_recvToken = true;
 169     }
 170
 171     /** [inboxes only] */
 172     public void recv(boolean latchData, boolean latchPath) {
 173         if (!dock.isInputDock()) throw new RuntimeException("recv() may only be used at input docks");
 174         if (pending_recvOrCollect || pending_sendToken) flush_pending();
 175         pending_recvOrCollect = true;
 176         pending_latchData = latchData;
 177         pending_latchPath = latchPath;
 178     }
 179
 180     /** [outboxes only], will fuse with previous instruction if it was a recvToken() */
 181     public void collect(boolean latchData, boolean latchPath) {
 182         if (!dock.isOutputDock()) throw new RuntimeException("collect() may only be used at output docks");
 183         if (pending_recvOrCollect || pending_sendToken) flush_pending();
 184         pending_recvOrCollect = true;
 185         pending_latchData = latchData;
 186         pending_latchPath = latchPath;
 187     }
 188
 189     /** [either], will fuse with previous instruction if it was a recvToken(), recv(), or collect() */
 190     public void sendToken(Destination dest) { sendToken(dest, null); }
 191     public void sendToken(Destination dest, BitVector signal) {
 192         if (pending_sendToken) flush_pending();
 193         pending_path = dock.getPath(dest, signal);
 194         pending_sendToken = true;
 195     }
 196
 197     /** [inboxes only], will fuse with previous instruction if it was a sendToken() */
 198     public void deliver() {
 199         if (!dock.isInputDock()) throw new RuntimeException("deliver() may only be used at input docks");
 200         flush_pending(true);
 201     }
 202
 203     /** [inboxes only], will fuse with previous instruction if it was a sendToken() */
 204     public void flush() {
 205         if (!dock.isInputDock()) throw new RuntimeException("flush() may only be used at input docks");
 206         flush_pending();
 207         instructions.add(new Instruction.Flush(dock, predicate));
 208     }
 209
 210     /** [outboxes only], will fuse with previous instruction if it was a sendToken() */
 211     public void sendWord(Destination dest) { sendWord(dest, null); }
 212     public void sendWord(Destination dest, BitVector signal) {
 213         if (!dock.isOutputDock()) throw new RuntimeException("sendWord() may only be used at output docks");
 214         if (pending_sendToken) flush_pending();
 215         pending_path = dock.getPath(dest, signal);
 216         flush_pending(true);
 217     }
 218
 219     /** sets the data latch to a literal value */
 220     public void literal(BitVector literal) {
 221         // FIXME: code duplication here
 222         // FEATURE: be more intelligent here to avoid shifts if possible?
 223         int counter = 0;
 224         while(counter < dock.getShip().getFleet().getWordWidth()) counter += ctx.fleet.getShiftWidth();
 225         while(counter > 0) {
 226             BitVector temp = new BitVector(dock.getShip().getFleet().getShiftWidth());
 227             for(int i=counter-1; i>=counter-ctx.fleet.getShiftWidth(); i--)
 228                 if (i<literal.length())
 229                     temp.set(i-(counter-ctx.fleet.getShiftWidth()), literal.get(i));
 230             instructions.add(new Shift(dock, predicate, temp));
 231             counter -= ctx.fleet.getShiftWidth();
 232         }
 233     }
 234
 235     /** sets the data latch to a literal value */
 236     public void literal(long literal) {
 237         flush_pending();
 238         if (((FleetTwoFleet)ctx.fleet).isSmallEnoughToFit(literal)) {
 239             instructions.add(new Instruction.Set(dock, predicate, SetDest.DataLatch, literal));
 240         } else {
 241             int counter = 0;
 242             int extra = 0;
 243             while(counter < dock.getShip().getFleet().getWordWidth()) { extra++; counter += ctx.fleet.getShiftWidth(); }
 244             warn("literal " + literal + " requires " + extra + " instructions");
 245             while(counter > 0) {
 246                 instructions.add(new Shift(dock, predicate,
 247                                            new BitVector(dock.getShip().getFleet().getWordWidth())
 248                                            .set(getField(counter-1, counter-ctx.fleet.getShiftWidth(), literal))));
 249                 counter -= ctx.fleet.getShiftWidth();
 250             }
 251         }
 252     }
 253
 254     /** sets the flags */
 255     public void setFlags(Instruction.Set.FlagFunction newFlagA, Instruction.Set.FlagFunction newFlagB) {
 256         flush_pending();
 257         instructions.add(new Instruction.Set(dock,
 258                                              predicate,
 259                                              newFlagA,
 260                                              newFlagB));
 261     }
 262
 263     /** abort the loop immediately (if predicate is met) and invoke the successor loop */
 264     public void abort() {
 265         flush_pending();
 266         instructions.add(new Instruction.Set(dock,
 267                                              predicate,
 268                                              SetDest.OuterLoopCounter,
 269                                              0));
 270     }
 271
 272     public void abortAndInvoke(LoopFactory lf) {
 273         throw new RuntimeException("not implemented");
 274     }
 275
 276     // Emitting Code //////////////////////////////////////////////////////////////////////////////
 277
 278     void optimize() {
 279         flush_pending();
 280         // FEATURE: find loops of 1 instruction, use ILC
 281         // FEATURE: find sequences of >2 adjacent identical instructions, replace with use of ILC
 282         // FEATURE: after optimizing, find single-instruction loops, replace with use of ILC
 283         // FEATURE: consider doing loop unrolling if two copies of the loop fit in the instruction buffer...
 284         // FEATURE: clever instruction re-oredering?
 285     }
 286
 287     /**
 288      *  The code emitted by this method makes the following assumptions:
 289      *
 290      *   - The instructions emitted are dispatched in order
 291      *   - At the time of dispatch, the dock must be pre-quiescent.
 292      *
 293      */
 294     public void emit(ArrayList<Instruction> ic) {
 295         emit(ic, dock.getInstructionFifoSize());
 296     }
 297     private void emit(ArrayList<Instruction> ic, int capacity) {
 298         flush_pending();
 299         optimize();
 300
 301         // the number of instructions after and including the first blocking instruction
 302         int numInstructionsNotIncludingNonblockingPrefix = 0;
 303         int loopSize = 0;
 304         boolean blockingInstructionEncountered = false;
 305
 306         // Set the OLC (it might previously have been zero)
 307         ic.add(new Set(dock, Predicate.IgnoreFlagD, SetDest.OuterLoopCounter, count==0 ? 1 : count));
 308         if (count!=1) {
 309             ic.add(new Instruction.Head(dock));
 310         }
 311
 312         for(Instruction i : instructions) {
 313             if (i instanceof Move && (((Move)i).tokenIn || ((Move)i).dataIn))
 314                 blockingInstructionEncountered = true;
 315             if (blockingInstructionEncountered)
 316                 numInstructionsNotIncludingNonblockingPrefix++;
 317             loopSize++;
 318             ic.add(i);
 319         }
 320
 321         if (count==1) {
 322             if (numInstructionsNotIncludingNonblockingPrefix > capacity)
 323                 throw new RuntimeException("instruction sequence is too long for instruction fifo at " + dock);
 324         } else {
 325             if (count != 0) {
 326                 ic.add(new Instruction.Set(dock, Predicate.Default, SetDest.OuterLoopCounter, SetSource.Decrement));
 327                 if (blockingInstructionEncountered)
 328                     numInstructionsNotIncludingNonblockingPrefix++;
 329                 loopSize++;
 330             }
 331         }
 332         if (count!=1)
 333             ic.add(new Instruction.Abort(dock, Predicate.FlagD));
 334         if (ctx.autoflush && next==null && dock.isInputDock())
 335             ic.add(new Instruction.Flush(dock, Predicate.FlagD));
 336
 337         // FIXME: need to somehow deal with count!=0 loops that are
 338         // torpedoable; they need to wait for a torpedo to arrive
 339         // after exhausting their count.
 340
 341         if (count!=1) {
 342             ic.add(new Instruction.Tail(dock));
 343             if (loopSize > capacity)
 344                 throw new RuntimeException("instruction loop is too long for instruction fifo");
 345         }
 346
 347         if (next != null) {
 348             if (count != 1) throw new RuntimeException("no support for successor loops when count!=1 yet");
 349             next.emit(ic, capacity - loopSize);
 350         }
 351     }
 352
 353     void warn(String warning) {
 354         System.err.println("warning: " + warning);
 355     }
 356
 357     // Helpers //////////////////////////////////////////////////////////////////////////////
 358
 359     public void recvWord() { recv(true, false); }
 360     public void recvPath() { recv(false, true); }
 361     public void recvPacket() { recv(true, true); }
 362     public void collectWord() { collect(true, false); }
 363     public void collectPath() { collect(false, true); }
 364     public void collectPacket() { collect(true, true); }
 365
 366 }