import edu.berkeley.fleet.api.Instruction.Set.*;
import static edu.berkeley.fleet.util.BitManipulations.*;
-// FIXME: is it legitimate to send a torpedo to a count==1 loop?
-// FIXME: is it legitimate to send a torpedo to a count>1 loop?
/**
*
* A helper class for building loops of instructions.
*/
public class LoopFactory {
- // FIXME: vet this to see if it is sensible
- private boolean instructionFifoSizeCheckDisabled = false;
- public void disableInstructionFifoOverflowCheck() { instructionFifoSizeCheckDisabled = true; }
-
public final Dock dock;
public final String friendlyName;
public final int count;
+ public final boolean torpedoable;
- private final Context ctx;
- private Predicate predicate = Predicate.Default;
+ private final CodeBag ctx;
private LoopFactory next = null;
private ArrayList<Instruction> instructions = new ArrayList<Instruction>();
* @arg prev a loop for which this is the successor loop (if any)
* @arg count the number of times to execute this loop; <tt>0</tt> means continue until torpedoed
*/
- public LoopFactory(Context ctx, Dock dock, int count) {
- this(ctx, dock, count, dock.toString(), null);
+ LoopFactory(CodeBag ctx, Dock dock, int count) {
+ this(ctx, dock, count, count==0, dock.toString(), null);
+ }
+ LoopFactory(CodeBag ctx, Dock dock, int count, boolean torpedoable) {
+ this(ctx, dock, count, torpedoable, dock.toString(), null);
+ }
+ LoopFactory(CodeBag ctx, Dock dock, int count, String friendlyName) {
+ this(ctx, dock, count, count==0, friendlyName);
}
- public LoopFactory(Context ctx, Dock dock, int count, String friendlyName) {
- this(ctx, dock, count, friendlyName, null);
+ LoopFactory(CodeBag ctx, Dock dock, int count, boolean torpedoable, String friendlyName) {
+ this(ctx, dock, count, torpedoable, friendlyName, null);
}
- private LoopFactory(Context ctx, Dock dock, int count, String friendlyName, LoopFactory prev) {
+ private LoopFactory(CodeBag ctx, Dock dock, int count, boolean torpedoable, String friendlyName, LoopFactory prev) {
this.ctx = ctx;
this.dock = dock;
this.count = count;
+ if (count==0 && !torpedoable)
+ throw new RuntimeException("count==0 loops must be torpedoable");
+ this.torpedoable = torpedoable;
this.friendlyName = friendlyName;
ctx.loopFactories.add(this);
if (ctx.startupLoopFactories.get(dock) == null)
}
public LoopFactory makeNext(int new_count) { return makeNext(new_count, null); }
- public LoopFactory makeNext(int new_count, String newFriendlyName) {
+ public LoopFactory makeNext(int new_count, String newFriendlyName) { return makeNext(new_count, new_count==0, newFriendlyName); }
+ public LoopFactory makeNext(int new_count, boolean newTorpedoable) { return makeNext(new_count, newTorpedoable, null); }
+ public LoopFactory makeNext(int new_count, boolean newTorpedoable, String newFriendlyName) {
if (next != null) throw new RuntimeException("loop already has a successor");
- return new LoopFactory(ctx, dock, new_count, newFriendlyName, this);
+ return new LoopFactory(ctx, dock, new_count, newTorpedoable, newFriendlyName, this);
}
public LoopFactory getNext() { return next; }
private void setNext(LoopFactory next) {
if (this.next != null) throw new RuntimeException("attempt to setNext() twice");
+ if (ctx.isSealed()) throw new RuntimeException("context already sealed");
this.next = next;
}
// Building Loops //////////////////////////////////////////////////////////////////////////////
+ Predicate predicate = Predicate.Default;
boolean pending_interruptible = false;
boolean pending_recvToken = false;
boolean pending_recvOrCollect = false;
boolean pending_sendToken = false;
Path pending_path = null;
+ private void addInstruction(Instruction inst) {
+ if (ctx.isSealed()) throw new RuntimeException("context already sealed");
+ instructions.add(inst);
+ }
+
void flush_pending() { flush_pending(false); }
void flush_pending(boolean pending_dataOut) {
if (!pending_recvToken &&
!pending_recvOrCollect &&
!pending_sendToken &&
!pending_dataOut) {
+ /*
if (pending_interruptible)
- throw new RuntimeException("abortLoopIfTorpedoPresent() must be followed immediately by a Move");
+ throw new RuntimeException("abortLoopIfTorpedoPresent() must be followed immediately by a Move (in LoopFactory for dock " + dock + ")");
+ */
} else {
- instructions.add(new Move(dock,
- count!=1,
+ addInstruction(new Move(dock,
predicate,
pending_interruptible,
pending_path==null ? null : pending_path,
public void interruptibleNop() {
flush_pending();
- instructions.add(new Move(dock,
- count!=1,
+ addInstruction(new Move(dock,
predicate,
true,
null,
/** must be followed immediately by a move-based instruction */
public void abortLoopIfTorpedoPresent() {
flush_pending();
- //if (count!=0) throw new RuntimeException("currently, only forever-loops may be sensitive to torpedoes");
+ if (!torpedoable)
+ throw new RuntimeException("invocation of abortLoopIfTorpedoPresent() in a non-torpedoable LoopFactory");
pending_interruptible = true;
}
pending_path = dock.getPath(dest, signal);
pending_sendToken = true;
}
+ public void sendToken(Dock dock) { sendToken(dock.getDataDestination()); }
+ public void sendToken(Dock dock, BitVector signal) { sendToken(dock.getDataDestination(), signal); }
+
+ public void sendTorpedo(Dock dock) { sendToken(dock.getInstructionDestination()); }
/** [inboxes only], will fuse with previous instruction if it was a sendToken() */
public void deliver() {
public void flush() {
if (!dock.isInputDock()) throw new RuntimeException("flush() may only be used at input docks");
flush_pending();
- instructions.add(new Instruction.Flush(dock, count!=1, predicate));
+ addInstruction(new Instruction.Flush(dock, predicate));
}
/** [outboxes only], will fuse with previous instruction if it was a sendToken() */
public void sendWord(Destination dest, BitVector signal) {
if (!dock.isOutputDock()) throw new RuntimeException("sendWord() may only be used at output docks");
if (pending_sendToken) flush_pending();
- pending_path = dock.getPath(dest, signal);
+ pending_path = dest==null ? null : dock.getPath(dest, signal);
flush_pending(true);
}
+ public void sendWord(Dock dock) { sendWord(dock.getDataDestination()); }
+ public void sendWord(Dock dock, BitVector signal) { sendWord(dock.getDataDestination(), signal); }
+ public void sendPacket() { sendWord((Destination)null); }
+
+ public void literal(String constantName) {
+ literal(dock.getConstant(constantName));
+ }
/** sets the data latch to a literal value */
- public void literal(BitVector literal) {
- // FIXME: code duplication here
- // FIXME: be more intelligent here to avoid shifts if possible?
+ public void literal(final DeferredBitVector literal) {
+ flush_pending();
+ if (literal instanceof BitVector) {
+ BitVector bv = (BitVector)literal;
+ boolean can_use_set = true;
+ for(int i=ctx.fleet.getSetWidth(); i<bv.length(); i++)
+ if (bv.get(i)!=bv.get(ctx.fleet.getSetWidth()-1)) {
+ can_use_set = false;
+ break;
+ }
+ if (can_use_set) {
+ addInstruction(new Instruction.Set(dock, predicate, SetDest.DataLatch, bv.toLong()));
+ return;
+ }
+ }
+
int counter = 0;
while(counter < dock.getShip().getFleet().getWordWidth()) counter += ctx.fleet.getShiftWidth();
while(counter > 0) {
- BitVector temp = new BitVector(dock.getShip().getFleet().getShiftWidth());
- for(int i=counter-1; i>=counter-ctx.fleet.getShiftWidth(); i--)
- if (i<literal.length())
- temp.set(i-(counter-ctx.fleet.getShiftWidth()), literal.get(i));
- instructions.add(new Shift(dock, count!=1, predicate, temp));
+ final int counter_f = counter;
+ DeferredBitVector temp = new DeferredBitVector() {
+ public BitVector getBitVector() {
+ BitVector bv = literal.getBitVector();
+ BitVector ret = new BitVector(dock.getShip().getFleet().getShiftWidth());
+ for(int i=counter_f-1; i>=counter_f-ctx.fleet.getShiftWidth(); i--)
+ if (i<bv.length())
+ ret.set(i-(counter_f-ctx.fleet.getShiftWidth()), bv.get(i));
+ return ret;
+ }
+ };
+ Shift shift = new Shift(dock, predicate, temp);
+ addInstruction(shift);
counter -= ctx.fleet.getShiftWidth();
}
}
/** sets the data latch to a literal value */
public void literal(long literal) {
- flush_pending();
- if (((FleetTwoFleet)ctx.fleet).isSmallEnoughToFit(literal)) {
- instructions.add(new Instruction.Set(dock, count!=1, predicate, SetDest.DataLatch, literal));
- } else {
- int counter = 0;
- int extra = 0;
- while(counter < dock.getShip().getFleet().getWordWidth()) { extra++; counter += ctx.fleet.getShiftWidth(); }
- warn("literal " + literal + " requires " + extra + " instructions");
- while(counter > 0) {
- instructions.add(new Shift(dock, count!=1, predicate,
- new BitVector(dock.getShip().getFleet().getWordWidth())
- .set(getField(counter-1, counter-ctx.fleet.getShiftWidth(), literal))));
- counter -= ctx.fleet.getShiftWidth();
- }
- }
+ literal(new BitVector(ctx.fleet.getWordWidth()).set(literal));
+ }
+
+ /** sets the data latch to a code bag descriptor */
+ public void literal(CodeBag cb) {
+ literal(cb.getDescriptor());
}
/** sets the flags */
public void setFlags(Instruction.Set.FlagFunction newFlagA, Instruction.Set.FlagFunction newFlagB) {
flush_pending();
- instructions.add(new Instruction.Set(dock,
- count!=1,
+ addInstruction(new Instruction.Set(dock,
predicate,
newFlagA,
newFlagB));
}
- // FIXME: what if we're using an ILC-loop?
/** abort the loop immediately (if predicate is met) and invoke the successor loop */
public void abort() {
flush_pending();
- instructions.add(new Instruction.Set(dock,
- count!=1,
+ addInstruction(new Instruction.Set(dock,
predicate,
SetDest.OuterLoopCounter,
0));
}
- public void abortAndInvoke(LoopFactory lf) {
- throw new RuntimeException("not implemented");
- }
-
// Emitting Code //////////////////////////////////////////////////////////////////////////////
void optimize() {
flush_pending();
- // FEATURE: find loops of 1 instruction, use ILC
// FEATURE: find sequences of >2 adjacent identical instructions, replace with use of ILC
- // FEATURE: after optimizing, find single-instruction loops, replace with use of ILC
+ // (requires Instruction.equals() be implemented)
// FEATURE: consider doing loop unrolling if two copies of the loop fit in the instruction buffer...
// FEATURE: clever instruction re-oredering?
}
*
*/
public void emit(ArrayList<Instruction> ic) {
+ emit(ic, dock.getInstructionFifoSize());
+ }
+ private void emit(ArrayList<Instruction> ic, int capacity) {
flush_pending();
optimize();
- // FIXME: if this loop is a count==1 loop, we can emit the successor loop along with it...
-
// the number of instructions after and including the first blocking instruction
int numInstructionsNotIncludingNonblockingPrefix = 0;
int loopSize = 0;
boolean blockingInstructionEncountered = false;
// Set the OLC (it might previously have been zero)
- ic.add(new Set(dock, false, Predicate.IgnoreFlagD, SetDest.OuterLoopCounter, count==0 ? 1 : count));
- if (count!=1) {
+ ic.add(new Set(dock, Predicate.IgnoreFlagD, SetDest.OuterLoopCounter, count==0 ? 1 : count));
+
+ boolean olc_loop = count!=1;
+ /*
+ if (count != 1 &&
+ (count==0 || count <= 63) &&
+ instructions.size()==1 &&
+ (instructions.get(0) instanceof Instruction.Move)) {
+ olc_loop = false;
+ if (count==0)
+ ic.add(new Instruction.Set(dock, Predicate.Default,
+ SetDest.InnerLoopCounter, SetSource.Infinity));
+ else
+ ic.add(new Instruction.Set(dock, Predicate.Default,
+ SetDest.InnerLoopCounter, count));
+ }
+ */
+
+ if (olc_loop) {
ic.add(new Instruction.Head(dock));
}
- for(Instruction i : instructions) {
- if (i instanceof Move && (((Move)i).tokenIn || ((Move)i).dataIn))
- blockingInstructionEncountered = true;
- if (blockingInstructionEncountered)
- numInstructionsNotIncludingNonblockingPrefix++;
- loopSize++;
- ic.add(i);
+ boolean firstTime = true;
+ while(true) {
+ for(Instruction i : instructions) {
+ if (!firstTime && i.predicate==Predicate.FlagD) continue;
+ if (i instanceof Move && (((Move)i).tokenIn || ((Move)i).dataIn))
+ blockingInstructionEncountered = true;
+ if (blockingInstructionEncountered)
+ numInstructionsNotIncludingNonblockingPrefix++;
+ loopSize++;
+ ic.add(i);
+ }
+ if (count!=0) break;
+ if (instructions.size()+loopSize+3 > capacity) break;
+ firstTime = false;
+ break;
+ //System.out.println("packing the loop!");
}
- if (count==1) {
- if (!instructionFifoSizeCheckDisabled &&
- numInstructionsNotIncludingNonblockingPrefix > dock.getInstructionFifoSize())
- throw new RuntimeException("instruction sequence is too long for instruction fifo at " + dock);
+ if (!olc_loop) {
+ if (numInstructionsNotIncludingNonblockingPrefix > capacity)
+ throw new RuntimeException("instruction sequence is too long for instruction fifo at " +
+ dock + " ("+numInstructionsNotIncludingNonblockingPrefix+">"+capacity+")");
} else {
if (count != 0) {
- ic.add(new Instruction.Set(dock, true, Predicate.Default, SetDest.OuterLoopCounter, SetSource.Decrement));
+ ic.add(new Instruction.Set(dock, Predicate.Default, SetDest.OuterLoopCounter, SetSource.Decrement));
if (blockingInstructionEncountered)
numInstructionsNotIncludingNonblockingPrefix++;
loopSize++;
}
}
- if (count!=1) {
+ if (olc_loop) {
ic.add(new Instruction.Abort(dock, Predicate.FlagD));
+ loopSize++;
}
- if (ctx.autoflush && !"Debug".equals(dock.getShip().getType()) && next==null) {
- if (dock.isInputDock())
- ic.add(new Instruction.Flush(dock, true, Predicate.FlagD));
+ if (ctx.autoflush && next==null && dock.isInputDock()) {
+ ic.add(new Instruction.Flush(dock, Predicate.FlagD));
+ loopSize++;
}
- if (count!=1) {
+
+ // FIXME: need to somehow deal with count!=0 loops that are
+ // torpedoable; they need to wait for a torpedo to arrive
+ // after exhausting their count.
+
+ if (olc_loop) {
ic.add(new Instruction.Tail(dock));
- if (!instructionFifoSizeCheckDisabled &&
- loopSize > dock.getInstructionFifoSize())
- throw new RuntimeException("instruction loop is too long for instruction fifo");
+ if (loopSize > capacity)
+ throw new RuntimeException("instruction loop is too long for instruction fifo at " +
+ dock + " ("+loopSize+">"+capacity+")");
}
if (next != null) {
- if (count != 1) throw new RuntimeException("no support for successor loops when count!=1 yet");
- // FIXME: must include check based on reduced FIFO capacity
- // FIXME: review this
- next.emit(ic);
+ if (!olc_loop) {
+ next.emit(ic, capacity - numInstructionsNotIncludingNonblockingPrefix);
+ } else {
+ //next.emit(ic, capacity - loopSize);
+ throw new RuntimeException("no support for successor loops when count!=1 yet");
+ }
}
}
projects / fleet.git / blobdiff