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.*;
11 // QUESTION: does each dock mentioned by a context have a linear chain
12 // of loops, or can it branch?
14 // - or should we use "sub-contexts" for that
15 // - advantage: it lets us convey the fact that a bunch of loops are dispatched together
16 // - should loops have an "invoke context" opcode?
19 * A Context is a collection of Loops which obey these rules:
21 * - A Context has exclusive control of all docks mentioned by any of its Loops.
22 * - A Context includes a "starting loop" for every dock it mentions.
23 * - When a Context is spawned, it starts the "starting loop" on all of its docks.
24 * - A loop may or may not have a successor.
25 * - Control may transfer only two ways:
26 * - If a loop has a successor, control will transfer to the successor when the loop finishes.
27 * - A loop may explicitly transfer control to another loop via abortAndInvoke(). The
28 * invoked loop must belong to the same Dock and the same Context.
29 * - A Context finishes when all of its docks have finished executing a loop with no successor.
32 * - A Move instruction is a blocking instruction if either its tokenIn or dataIn bits are set.
33 * - All other instructions are non-blocking.
34 * - A dock is quiescent if its instruction ring is empty.
35 * - A dock is pre-quiescent if
36 * - all instructions which remain in the target dock's instruction
37 * fifo are nonblocking instructions,
38 * - either the docks' OLC=0 or all instructions which remain
39 * in its instruction fifo are one-shot instructions
40 * - after executing these remaining instructions, the dock's hatch is open
42 public class Context {
43 private HashMap<Dock,LoopFactory> startupLoopFactories = new HashMap<Dock,LoopFactory>();
44 private HashSet<LoopFactory> loopFactories = new HashSet<LoopFactory>();
46 public final Fleet fleet;
47 public Context(Fleet fleet) { this.fleet = fleet; }
49 private boolean autoflush = false;
50 public void setAutoflush(boolean a) { this.autoflush = a; }
52 // FIXME: ability for a group of Contexts to share an "allocation
53 // pool" because they will run concurrently.
54 public HashSet<Ship> allocatedShips = new HashSet<Ship>();
56 public Ship allocateShip(String name) {
58 Ship ship = fleet.getShip(name, i);
60 throw new RuntimeException("no more ships of type " + name);
61 if (allocatedShips.contains(ship)) continue;
62 allocatedShips.add(ship);
67 // FIXME: is it legitimate to send a torpedo to a count==1 loop?
68 // FIXME: is it legitimate to send a torpedo to a count>1 loop?
71 * A helper class for building loops of instructions.
73 * This class abstracts away:
74 * - The maximum size of a loop
75 * - The maximum length of a "one shot" instruction sequence
76 * - The looping/oneshot bit
77 * - The outer loop counter
78 * - The inner loop counter (opportunities to use it are auto-detected)
80 * It also performs various optimizations and provides a more
81 * convenient way of managing the predicate/interruptible fields.
83 * To get the most compact coding, the components of a Move should be
84 * performed in this order when possible, with no intervening commands:
92 public class LoopFactory {
94 // FIXME: vet this to see if it is sensible
95 private boolean instructionFifoSizeCheckDisabled = false;
96 public void disableInstructionFifoOverflowCheck() { instructionFifoSizeCheckDisabled = true; }
98 public final Dock dock;
99 public final String friendlyName;
100 public final int count;
101 private Predicate predicate = Predicate.Default;
102 private LoopFactory next = null;
103 private ArrayList<Instruction> instructions = new ArrayList<Instruction>();
106 * Creates a new loop.
107 * @arg dock the dock at which to execute the instructions
108 * @arg friendlyName a descriptive string for debugging the compiler
109 * @arg prev a loop for which this is the successor loop (if any)
110 * @arg count the number of times to execute this loop; <tt>0</tt> means continue until torpedoed
112 public LoopFactory(Dock dock, int count) { this(dock, count, dock.toString(), null); }
113 public LoopFactory(Dock dock, int count, String friendlyName) { this(dock, count, friendlyName, null); }
114 private LoopFactory(Dock dock, int count, String friendlyName, LoopFactory prev) {
117 this.friendlyName = friendlyName;
118 Context.this.loopFactories.add(this);
119 if (Context.this.startupLoopFactories.get(dock) == null)
120 Context.this.startupLoopFactories.put(dock, this);
122 if (prev.getNext() != null) throw new RuntimeException();
127 public LoopFactory makeNext(int new_count) { return makeNext(new_count, null); }
128 public LoopFactory makeNext(int new_count, String newFriendlyName) {
129 if (next != null) throw new RuntimeException("loop already has a successor");
130 return new LoopFactory(dock, new_count, newFriendlyName, this);
132 public LoopFactory getNext() { return next; }
133 private void setNext(LoopFactory next) {
134 if (this.next != null) throw new RuntimeException("attempt to setNext() twice");
139 // Building Loops //////////////////////////////////////////////////////////////////////////////
141 boolean pending_interruptible = false;
142 boolean pending_recvToken = false;
143 boolean pending_recvOrCollect = false;
144 boolean pending_latchData = false;
145 boolean pending_latchPath = false;
146 boolean pending_sendToken = false;
147 Path pending_path = null;
149 void flush_pending() { flush_pending(false); }
150 void flush_pending(boolean pending_dataOut) {
151 if (!pending_recvToken &&
152 !pending_recvOrCollect &&
153 !pending_sendToken &&
155 if (pending_interruptible)
156 throw new RuntimeException("abortLoopIfTorpedoPresent() must be followed immediately by a Move");
158 instructions.add(new Move(dock,
161 pending_interruptible,
162 pending_path==null ? null : pending_path,
164 pending_recvOrCollect,
170 pending_interruptible = false;
171 pending_recvToken = false;
172 pending_recvOrCollect = false;
173 pending_latchData = false;
174 pending_latchPath = false;
175 pending_sendToken = false;
179 public void interruptibleNop() {
181 instructions.add(new Move(dock,
194 /** sets the predicate which will be applied to subsequent instructions, or null for the default predicate */
195 public void setPredicate(Predicate p) {
196 if (p==null) p = Predicate.Default;
197 if (predicate==p) return;
202 /** must be followed immediately by a move-based instruction */
203 public void abortLoopIfTorpedoPresent() {
205 //if (count!=0) throw new RuntimeException("currently, only forever-loops may be sensitive to torpedoes");
206 pending_interruptible = true;
210 public void recvToken() {
211 if (pending_recvToken || pending_recvOrCollect || pending_sendToken) flush_pending();
212 pending_recvToken = true;
215 /** [inboxes only] */
216 public void recv(boolean latchData, boolean latchPath) {
217 if (!dock.isInputDock()) throw new RuntimeException("recv() may only be used at input docks");
218 if (pending_recvOrCollect || pending_sendToken) flush_pending();
219 pending_recvOrCollect = true;
220 pending_latchData = latchData;
221 pending_latchPath = latchPath;
224 /** [outboxes only], will fuse with previous instruction if it was a recvToken() */
225 public void collect(boolean latchData, boolean latchPath) {
226 if (!dock.isOutputDock()) throw new RuntimeException("collect() may only be used at output docks");
227 if (pending_recvOrCollect || pending_sendToken) flush_pending();
228 pending_recvOrCollect = true;
229 pending_latchData = latchData;
230 pending_latchPath = latchPath;
233 /** [either], will fuse with previous instruction if it was a recvToken(), recv(), or collect() */
234 public void sendToken(Destination dest) { sendToken(dest, null); }
235 public void sendToken(Destination dest, BitVector signal) {
236 if (pending_sendToken) flush_pending();
237 pending_path = dock.getPath(dest, signal);
238 pending_sendToken = true;
241 /** [inboxes only], will fuse with previous instruction if it was a sendToken() */
242 public void deliver() {
243 if (!dock.isInputDock()) throw new RuntimeException("deliver() may only be used at input docks");
247 /** [inboxes only], will fuse with previous instruction if it was a sendToken() */
248 public void flush() {
249 if (!dock.isInputDock()) throw new RuntimeException("flush() may only be used at input docks");
251 instructions.add(new Instruction.Flush(dock, count!=1, predicate));
254 /** [outboxes only], will fuse with previous instruction if it was a sendToken() */
255 public void sendWord(Destination dest) { sendWord(dest, null); }
256 public void sendWord(Destination dest, BitVector signal) {
257 if (!dock.isOutputDock()) throw new RuntimeException("sendWord() may only be used at output docks");
258 if (pending_sendToken) flush_pending();
259 pending_path = dock.getPath(dest, signal);
263 /** sets the data latch to a literal value */
264 public void literal(BitVector literal) {
265 // FIXME: code duplication here
266 // FIXME: be more intelligent here to avoid shifts if possible?
268 while(counter < dock.getShip().getFleet().getWordWidth()) counter += fleet.getShiftWidth();
270 BitVector temp = new BitVector(dock.getShip().getFleet().getShiftWidth());
271 for(int i=counter-1; i>=counter-fleet.getShiftWidth(); i--)
272 if (i<literal.length())
273 temp.set(i-(counter-fleet.getShiftWidth()), literal.get(i));
274 instructions.add(new Shift(dock, count!=1, predicate, temp));
275 counter -= fleet.getShiftWidth();
279 /** sets the data latch to a literal value */
280 public void literal(long literal) {
282 if (((FleetTwoFleet)fleet).isSmallEnoughToFit(literal)) {
283 instructions.add(new Instruction.Set(dock, count!=1, predicate, SetDest.DataLatch, literal));
287 while(counter < dock.getShip().getFleet().getWordWidth()) { extra++; counter += fleet.getShiftWidth(); }
288 warn("literal " + literal + " requires " + extra + " instructions");
290 instructions.add(new Shift(dock, count!=1, predicate,
291 new BitVector(dock.getShip().getFleet().getWordWidth())
292 .set(getField(counter-1, counter-fleet.getShiftWidth(), literal))));
293 counter -= fleet.getShiftWidth();
298 /** sets the flags */
299 public void setFlags(Instruction.Set.FlagFunction newFlagA, Instruction.Set.FlagFunction newFlagB) {
301 instructions.add(new Instruction.Set(dock,
308 // FIXME: what if we're using an ILC-loop?
309 /** abort the loop immediately (if predicate is met) and invoke the successor loop */
310 public void abort() {
312 instructions.add(new Instruction.Set(dock,
315 SetDest.OuterLoopCounter,
319 public void abortAndInvoke(LoopFactory lf) {
320 throw new RuntimeException("not implemented");
323 // Emitting Code //////////////////////////////////////////////////////////////////////////////
327 // FEATURE: find loops of 1 instruction, use ILC
328 // FEATURE: find sequences of >2 adjacent identical instructions, replace with use of ILC
329 // FEATURE: after optimizing, find single-instruction loops, replace with use of ILC
330 // FEATURE: consider doing loop unrolling if two copies of the loop fit in the instruction buffer...
331 // FEATURE: clever instruction re-oredering?
335 * The code emitted by this method makes the following assumptions:
337 * - The instructions emitted are dispatched in order
338 * - At the time of dispatch, the dock must be pre-quiescent.
341 public void emit(ArrayList<Instruction> ic) {
345 // FIXME: if this loop is a count==1 loop, we can emit the successor loop along with it...
347 // the number of instructions after and including the first blocking instruction
348 int numInstructionsNotIncludingNonblockingPrefix = 0;
350 boolean blockingInstructionEncountered = false;
352 // Set the OLC (it might previously have been zero)
353 ic.add(new Set(dock, false, Predicate.IgnoreFlagD, SetDest.OuterLoopCounter, count==0 ? 1 : count));
355 ic.add(new Instruction.Head(dock));
358 for(Instruction i : instructions) {
359 if (i instanceof Move && (((Move)i).tokenIn || ((Move)i).dataIn))
360 blockingInstructionEncountered = true;
361 if (blockingInstructionEncountered)
362 numInstructionsNotIncludingNonblockingPrefix++;
368 if (!instructionFifoSizeCheckDisabled &&
369 numInstructionsNotIncludingNonblockingPrefix > dock.getInstructionFifoSize())
370 throw new RuntimeException("instruction sequence is too long for instruction fifo at " + dock);
373 ic.add(new Instruction.Set(dock, true, Predicate.Default, SetDest.OuterLoopCounter, SetSource.Decrement));
374 if (blockingInstructionEncountered)
375 numInstructionsNotIncludingNonblockingPrefix++;
380 ic.add(new Instruction.Abort(dock, Predicate.FlagD));
382 if (autoflush && !"Debug".equals(dock.getShip().getType()) && next==null) {
383 if (dock.isInputDock())
384 ic.add(new Instruction.Flush(dock, true, Predicate.FlagD));
387 ic.add(new Instruction.Tail(dock));
388 if (!instructionFifoSizeCheckDisabled &&
389 loopSize > dock.getInstructionFifoSize())
390 throw new RuntimeException("instruction loop is too long for instruction fifo");
394 if (count != 1) throw new RuntimeException("no support for successor loops when count!=1 yet");
395 // FIXME: must include check based on reduced FIFO capacity
396 // FIXME: review this
401 void warn(String warning) {
402 System.err.println("warning: " + warning);
405 // Helpers //////////////////////////////////////////////////////////////////////////////
407 public void recvWord() { recv(true, false); }
408 public void recvPath() { recv(false, true); }
409 public void recvPacket() { recv(true, true); }
410 public void collectWord() { collect(true, false); }
411 public void collectPath() { collect(false, true); }
412 public void collectPacket() { collect(true, true); }
416 public void emit(ArrayList<Instruction> ic) {
417 for(LoopFactory lf : startupLoopFactories.values())