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