src/edu/berkeley/fleet/ir/Context.java

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