1 package edu.berkeley.fleet.loops;
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.*;
13 * A helper class for building loops of instructions.
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)
22 * It also performs various optimizations and provides a more
23 * convenient way of managing the predicate/interruptible fields.
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:
34 public class LoopFactory {
36 public final Dock dock;
37 public final String friendlyName;
38 public final int count;
39 public final boolean torpedoable;
41 private final CodeBag ctx;
42 private LoopFactory next = null;
43 private ArrayList<Instruction> instructions = new ArrayList<Instruction>();
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
52 LoopFactory(CodeBag ctx, Dock dock, int count) {
53 this(ctx, dock, count, count==0, dock.toString(), null);
55 LoopFactory(CodeBag ctx, Dock dock, int count, boolean torpedoable) {
56 this(ctx, dock, count, torpedoable, dock.toString(), null);
58 LoopFactory(CodeBag ctx, Dock dock, int count, String friendlyName) {
59 this(ctx, dock, count, count==0, friendlyName);
61 LoopFactory(CodeBag ctx, Dock dock, int count, boolean torpedoable, String friendlyName) {
62 this(ctx, dock, count, torpedoable, friendlyName, null);
64 private LoopFactory(CodeBag ctx, Dock dock, int count, boolean torpedoable, String friendlyName, LoopFactory prev) {
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);
76 if (prev.getNext() != null) throw new RuntimeException();
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);
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");
96 // Building Loops //////////////////////////////////////////////////////////////////////////////
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;
107 private void addInstruction(Instruction inst) {
108 if (ctx.isSealed()) throw new RuntimeException("context already sealed");
109 instructions.add(inst);
112 void flush_pending() { flush_pending(false); }
113 void flush_pending(boolean pending_dataOut) {
114 if (!pending_recvToken &&
115 !pending_recvOrCollect &&
116 !pending_sendToken &&
119 if (pending_interruptible)
120 throw new RuntimeException("abortLoopIfTorpedoPresent() must be followed immediately by a Move (in LoopFactory for dock " + dock + ")");
123 addInstruction(new Move(dock,
125 pending_interruptible,
126 pending_path==null ? null : pending_path,
128 pending_recvOrCollect,
134 pending_interruptible = false;
135 pending_recvToken = false;
136 pending_recvOrCollect = false;
137 pending_latchData = false;
138 pending_latchPath = false;
139 pending_sendToken = false;
143 public void interruptibleNop() {
145 addInstruction(new Move(dock,
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;
165 /** must be followed immediately by a move-based instruction */
166 public void abortLoopIfTorpedoPresent() {
169 throw new RuntimeException("invocation of abortLoopIfTorpedoPresent() in a non-torpedoable LoopFactory");
170 pending_interruptible = true;
174 public void recvToken() {
175 if (pending_recvToken || pending_recvOrCollect || pending_sendToken) flush_pending();
176 pending_recvToken = true;
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;
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;
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;
204 public void sendToken(Dock dock) { sendToken(dock.getDataDestination()); }
205 public void sendToken(Dock dock, BitVector signal) { sendToken(dock.getDataDestination(), signal); }
207 public void sendTorpedo(Dock dock) { sendToken(dock.getInstructionDestination()); }
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");
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");
219 addInstruction(new Instruction.Flush(dock, predicate));
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);
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); }
234 public void literal(String constantName) {
235 literal(dock.getConstant(constantName));
238 /** sets the data latch to a literal value */
239 public void literal(final DeferredBitVector literal) {
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)) {
250 addInstruction(new Instruction.Set(dock, predicate, SetDest.DataLatch, bv.toLong()));
256 while(counter < dock.getShip().getFleet().getWordWidth()) counter += ctx.fleet.getShiftWidth();
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--)
265 ret.set(i-(counter_f-ctx.fleet.getShiftWidth()), bv.get(i));
269 Shift shift = new Shift(dock, predicate, temp);
270 addInstruction(shift);
271 counter -= ctx.fleet.getShiftWidth();
275 /** sets the data latch to a literal value */
276 public void literal(long literal) {
277 literal(new BitVector(ctx.fleet.getWordWidth()).set(literal));
280 /** sets the data latch to a code bag descriptor */
281 public void literal(CodeBag cb) {
282 literal(cb.getDescriptor());
285 /** sets the flags */
286 public void setFlags(Instruction.Set.FlagFunction newFlagA, Instruction.Set.FlagFunction newFlagB) {
288 addInstruction(new Instruction.Set(dock,
294 /** abort the loop immediately (if predicate is met) and invoke the successor loop */
295 public void abort() {
297 addInstruction(new Instruction.Set(dock,
299 SetDest.OuterLoopCounter,
303 // Emitting Code //////////////////////////////////////////////////////////////////////////////
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?
314 * The code emitted by this method makes the following assumptions:
316 * - The instructions emitted are dispatched in order
317 * - At the time of dispatch, the dock must be pre-quiescent.
320 public void emit(ArrayList<Instruction> ic) {
321 emit(ic, dock.getInstructionFifoSize());
323 private void emit(ArrayList<Instruction> ic, int capacity) {
327 // the number of instructions after and including the first blocking instruction
328 int numInstructionsNotIncludingNonblockingPrefix = 0;
330 boolean blockingInstructionEncountered = false;
332 // Set the OLC (it might previously have been zero)
333 ic.add(new Set(dock, Predicate.IgnoreFlagD, SetDest.OuterLoopCounter, count==0 ? 1 : count));
335 boolean olc_loop = count!=1;
338 (count==0 || count <= 63) &&
339 instructions.size()==1 &&
340 (instructions.get(0) instanceof Instruction.Move)) {
343 ic.add(new Instruction.Set(dock, Predicate.Default,
344 SetDest.InnerLoopCounter, SetSource.Infinity));
346 ic.add(new Instruction.Set(dock, Predicate.Default,
347 SetDest.InnerLoopCounter, count));
352 ic.add(new Instruction.Head(dock));
355 boolean firstTime = 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++;
367 if (instructions.size()+loopSize+3 > capacity) break;
370 //System.out.println("packing the loop!");
374 if (numInstructionsNotIncludingNonblockingPrefix > capacity)
375 throw new RuntimeException("instruction sequence is too long for instruction fifo at " + dock);
378 ic.add(new Instruction.Set(dock, Predicate.Default, SetDest.OuterLoopCounter, SetSource.Decrement));
379 if (blockingInstructionEncountered)
380 numInstructionsNotIncludingNonblockingPrefix++;
385 ic.add(new Instruction.Abort(dock, Predicate.FlagD));
388 if (ctx.autoflush && next==null && dock.isInputDock()) {
389 ic.add(new Instruction.Flush(dock, Predicate.FlagD));
393 // FIXME: need to somehow deal with count!=0 loops that are
394 // torpedoable; they need to wait for a torpedo to arrive
395 // after exhausting their count.
398 ic.add(new Instruction.Tail(dock));
399 if (loopSize > capacity)
400 throw new RuntimeException("instruction loop is too long for instruction fifo at " + dock);
405 next.emit(ic, capacity - numInstructionsNotIncludingNonblockingPrefix);
407 //next.emit(ic, capacity - loopSize);
408 throw new RuntimeException("no support for successor loops when count!=1 yet");
413 void warn(String warning) {
414 System.err.println("warning: " + warning);
417 // Helpers //////////////////////////////////////////////////////////////////////////////
419 public void recvWord() { recv(true, false); }
420 public void recvPath() { recv(false, true); }
421 public void recvPacket() { recv(true, true); }
422 public void collectWord() { collect(true, false); }
423 public void collectPath() { collect(false, true); }
424 public void collectPacket() { collect(true, true); }