1 package edu.berkeley.fleet.assembler;
2 import edu.berkeley.fleet.api.*;
3 import edu.berkeley.sbp.*;
4 import edu.berkeley.sbp.chr.*;
5 import edu.berkeley.sbp.misc.*;
6 import edu.berkeley.sbp.meta.*;
7 import edu.berkeley.sbp.util.*;
8 import static edu.berkeley.fleet.util.BitManipulations.*;
9 import edu.berkeley.fleet.two.*;
10 import edu.berkeley.fleet.api.Instruction.Set;
11 import static edu.berkeley.fleet.api.Instruction.*;
12 import static edu.berkeley.fleet.api.Instruction.Set.*;
13 import static edu.berkeley.fleet.api.Predicate.*;
14 import edu.berkeley.fleet.two.*;
15 import edu.berkeley.fleet.fpga.*;
16 import edu.berkeley.fleet.interpreter.*;
22 * @author Adam Megacz <megacz@cs.berkeley.edu>
26 private static final BitVector SIGNAL_ZERO = new BitVector(1);
27 private static final BitVector SIGNAL_ONE = new BitVector(1);
29 SIGNAL_ONE.set(0,true);
33 expect = new ArrayList<Long>();
37 //////////////////////////////////////////////////////////////////////////////
40 private ArrayList<String> imports = new ArrayList<String>();
42 private HashMap<String,Ship> shipMap = new HashMap<String,Ship>();
44 // codebags in numerical order
45 private ArrayList<CodeBag> codeBags = new ArrayList<CodeBag>();
46 private HashMap<String,CodeBag> codeBagsByName = new HashMap<String,CodeBag>();
48 private CodeBag getCodeBag(String name) {
49 CodeBag cb = codeBagsByName.get(name);
50 if (cb!=null) return cb;
51 return new CodeBag(name);
54 private static Union grammar;
55 private static synchronized Union getGrammar() throws Exception {
56 if (grammar != null) return grammar;
57 InputStream grammarStream =
58 Parser.class.getClassLoader().getResourceAsStream("edu/berkeley/fleet/assembler/fleet.g");
59 CharParser metaGrammarParser = new CharParser(GrammarAST.getMetaGrammar());
60 Tree<String> parsedGrammar = metaGrammarParser.parse(new CharInput(grammarStream)).expand1();
61 grammar = GrammarAST.buildFromAST(parsedGrammar, "s", new GrammarAST.ImportResolver() {
62 public InputStream getImportStream(String importname) { return null; }
67 // FIXME: this ought to be cached via serialization, I think
68 private static CharParser cp = null;
69 Tree<String> parseIt(Reader r) throws Exception {
71 cp = new CharParser(getGrammar());
72 CharInput ci = new CharInput(r);
73 Forest f = cp.parse(ci);
77 public Instruction[] parse(Reader r) throws Exception {
78 // this needs to be "code bag zero"
79 CodeBag baseCodeBag = new CodeBag();
80 CodeBag rootCodeBag = new CodeBag();
83 if (fleet instanceof Fpga) {
84 dock = ((Fpga)fleet).getUniversalSource();
86 dock = ((Interpreter)fleet).getUniversalSource();
88 baseCodeBag.add(new Set(dock, false, IgnoreOLC, SetDest.DataLatch, (rootCodeBag.getFakeAddress())), true);
89 Tree<String> parsed = (Tree<String>)parseIt(r);
90 walk(parsed, rootCodeBag);
92 // map from arbitrary identifiers to actual addresses
93 int[] codeBagMap = new int[codeBags.size()];
95 for(int i=0; i<codeBags.size(); i++) {
96 CodeBag c = codeBags.get(i);
97 codeBagMap[i] = count;
98 for(Instruction inst : c) {
103 // now write for real
105 ArrayList<Instruction> ret = new ArrayList<Instruction>();
106 for(int i=0; i<codeBags.size(); i++) {
107 CodeBag c = codeBags.get(i);
108 for(int j=0; j<c.size(); j++) {
109 Instruction inst = c.get(j);
110 if (c.isCBD.contains(j)) {
113 lit = FleetTwoFleet.CBD_SIZE.setval(lit, codeBags.get((int)old.immediate).size());
114 lit = FleetTwoFleet.CBD_OFFSET.setval(lit, codeBagMap[(int)old.immediate]);
115 inst = new Set(old.dock, false, IgnoreOLC, SetDest.DataLatch, lit);
121 return (Instruction[])ret.toArray(new Instruction[0]);
124 /** in the first pass, codebags are assigned "addresses" in arbitrary order */
125 void walk(Tree<String> t, CodeBag cb) {
127 String head = t.head();
129 } else if (head.equals("Program")) {
130 for(Tree<String> tc : t.child(0))
133 for(Tree<String> statement : t.child(1))
134 fillCodeBag(statement, cb);
136 } else if (head.equals("#import")) {
139 } else if (head.equals("#ship")) {
140 String name = name(t.child(0));
141 String type = string(t.child(1));
144 if (fleet instanceof FleetWithDynamicShips) {
145 FleetWithDynamicShips dyn = ((FleetWithDynamicShips)fleet);
146 ship = dyn.createShip(type, name);
148 throw new RuntimeException("couldn't find a ship called \""+type+"\"");
150 ship = allocateShip(type);
152 shipMap.put(name, ship);
154 } else if (head.equals("#include")) {
156 walk(parseIt(new InputStreamReader(new FileInputStream(string(t.child(0))))), cb);
157 } catch (Exception e) {
158 throw new RuntimeException(e);
161 } else if (head.equals("#expect")) {
162 expect.add(number(t.child(0)));
163 } else if (head.equals("#skip")) {
169 String string(Tree<String> t) {
171 if (t.head() != null) ret += t.head();
172 for(Tree<String> c : t)
177 String stringBody(Tree<String> t) {
179 for(Tree<String> c : t)
184 String name(Tree<String> t) {
185 return string(t.child(0))+string(t.child(1));
188 Path path(Dock dock, Tree<String> t) {
189 if (!"Dock".equals(t.head()) && !"Destination".equals(t.head()) && !"ShipSpecificLiteral".equals(t.head())) return null;
191 String shipName = name(t.child(0));
192 String portName = name(t.child(1));
193 String subPort = t.size()<3 ? null : name(t.child(2));
194 Ship ship = shipMap.get(shipName);
195 if (ship==null) throw new RuntimeException("no such ship \""+shipName+"\"");
196 Destination ret = null;
199 if (b.getName().equals(portName)) {
203 throw new RuntimeException("no such pump \""+portName+"\"");
204 if (subPort==null) subPort="";
205 if (":i".equals(t.head())) return dock.getPath(bb.getInstructionDestination(),SIGNAL_ZERO);
206 if (":1".equals(t.head())) return dock.getPath(bb.getDataDestination(),SIGNAL_ONE);
207 if (":0".equals(t.head())) return dock.getPath(bb.getDataDestination(),SIGNAL_ZERO);
208 return dock.getPath(bb.getDataDestination(),SIGNAL_ZERO);
211 Dock dock(Tree<String> t) {
212 if (!"Dock".equals(t.head()) && !"Destination".equals(t.head()) && !"ShipSpecificLiteral".equals(t.head()))
213 throw new RuntimeException(t+"");
214 String shipName = name(t.child(0));
215 String portName = name(t.child(1));
216 Ship ship = shipMap.get(shipName);
217 if (ship==null) throw new RuntimeException("no such ship \""+shipName+"\"");
220 if (b.getName().equals(portName))
222 throw new RuntimeException("no such pump \""+portName+"\"");
225 private HashMap<String,Integer> numAllocated = new HashMap<String,Integer>();
227 Ship allocateShip(String shipType) {
229 if (numAllocated.get(shipType) != null)
230 allocated = numAllocated.get(shipType);
231 numAllocated.put(shipType, allocated+1);
232 for(Iterator<Ship> it = fleet.iterator();
236 if (s.getType().equals(shipType)) {
237 if (allocated == 0) return s;
241 throw new RuntimeException("no more ships of type \""+shipType+"\"");
244 private long parseSSL(Tree t) {
245 String shipType = name(t.child(0));
246 String portName = name(t.child(1));
247 Ship chosenship = null;
248 for(Ship ship : fleet) {
249 if (ship.getType().equals(shipType)) {
254 if (chosenship==null) throw new RuntimeException("no ships of type " + shipType);
255 Dock chosenport = chosenship.getDock(portName);
256 Tree specs = t.child(2);
258 for(int i=0; i<specs.size(); i++) {
259 Tree tt = specs.child(i);
260 literal |= resolveLiteral(chosenport, stringBody(tt));
265 private static long resolveLiteral(Dock dd, String s) {
268 boolean hasval = false;
269 if (s.indexOf('=') != -1) {
270 val = Long.parseLong(s.substring(s.indexOf('=')+1));
271 s = s.substring(0, s.indexOf('='));
274 ShipDescription.Constant c = ((FleetTwoDock)dd).getConstant(s);
275 if (c==null) throw new RuntimeException("no constant " + s + " on dock " + dd);
279 ret |= ((~(0xffffffffffffffffL << c.numberWidth)) & val) << c.numberOffset;
283 private static FlagFunction parseFlags(Tree<String> t) {
284 FlagFunction ret = FlagFunction.ZERO;
285 for(int i=0; i<t.size(); i++) {
286 String s = t.child(i).head();
287 if (s.equals("0")) ret = ret.add(FlagFunction.ZERO);
288 if (s.equals("1")) ret = ret.add(FlagFunction.ONE);
289 if (s.equals("a")) ret = ret.add(FlagA);
290 if (s.equals("!a")) ret = ret.add(NotFlagA);
291 if (s.equals("b")) ret = ret.add(FlagB);
292 if (s.equals("!b")) ret = ret.add(NotFlagB);
293 if (s.equals("c")) ret = ret.add(FlagC);
294 if (s.equals("!c")) ret = ret.add(NotFlagC);
299 private int anoncount = 1;
300 void fillCodeBag(Tree<String> t, CodeBag cb) {
301 if (t.head()==null) return;
302 else if (t.head().equals("CodeBagDef")) {
303 CodeBag cb2 = getCodeBag(name(t.child(0)));
304 for(Tree<String> statement : t.child(1))
305 fillCodeBag(statement, cb2);
307 } else if (t.head().equals("Fiber")) {
308 Dock dock = (Dock)dock(t.child(0));
310 OUTER: for(Tree tt : t.child(1)) {
312 Predicate predicate = Default;
313 boolean looping = false;
314 boolean interruptible = false;
315 for(int i=0; i<tt.child(0).size(); i++) {
316 Tree ttt = tt.child(0).child(i);
317 if ("[a]".equals(ttt.head())) predicate = FlagA;
318 if ("[b]".equals(ttt.head())) predicate = FlagB;
319 if ("[c]".equals(ttt.head())) predicate = FlagC;
320 if ("[!a]".equals(ttt.head())) predicate = NotFlagA;
321 if ("[!b]".equals(ttt.head())) predicate = NotFlagB;
322 if ("[!c]".equals(ttt.head())) predicate = NotFlagC;
323 if ("[+]".equals(ttt.head())) predicate = IgnoreOLC;
324 if ("[I]".equals(ttt.head())) interruptible = true;
325 if ("[L]".equals(ttt.head())) looping = true;
328 if ("tail".equals(tt.head())) {
329 cb.add(new Tail(dock));
331 } else if ("setflags".equals(tt.head())) {
332 cb.add(new Set(dock, looping, predicate, parseFlags(tt.child(0)), parseFlags(tt.child(1))));
334 } else if ("tapl".equals(tt.head())) {
335 cb.add(new Set(dock, looping, predicate, SetDest.TAPL, path(dock, tt.child(0))));
337 } else if ("load".equals(tt.head()) && "loop".equals(tt.child(0).head())) {
338 cb.add(new Set(dock, looping, predicate, SetDest.OuterLoopCounter, SetSource.DataLatch));
340 } else if ("load".equals(tt.head()) && "repeat".equals(tt.child(0).head())) {
341 cb.add(new Set(dock, looping, predicate, SetDest.InnerLoopCounter, SetSource.DataLatch));
343 } else if ("*".equals(tt.head())) {
344 cb.add(new Set(dock, looping, predicate, SetDest.InnerLoopCounter, SetSource.Infinity));
346 } else if ("with".equals(tt.head()) && "loop".equals(tt.child(0).head())) {
347 cb.add(new Set(dock, looping, predicate, SetDest.OuterLoopCounter, (number(tt.child(1)))));
349 } else if ("with".equals(tt.head()) && "repeat".equals(tt.child(0).head())) {
350 cb.add(new Set(dock, looping, predicate, SetDest.InnerLoopCounter, (number(tt.child(1)))));
352 } else if ("decrement".equals(tt.head())) {
353 cb.add(new Set(dock, looping, predicate, SetDest.OuterLoopCounter, SetSource.Decrement));
355 } else if ("literal".equals(tt.head())) {
357 if (tt.child(0).head().equals("CodeBagBody")) {
358 Tree<String> tq = tt;
359 CodeBag cb2 = getCodeBag("anon"+(anoncount++));
360 for(Tree<String> statement : tq.child(0))
361 fillCodeBag(statement, cb2);
362 cb.add(new Set(dock, looping, predicate, SetDest.DataLatch, (cb2.getFakeAddress())), true);
364 } else if (tt.child(0).head().equals("Name")) {
365 String refname = name(tt.child(0));
366 CodeBag cb2 = getCodeBag(refname);
367 cb.add(new Set(dock, looping, predicate, SetDest.DataLatch, (cb2.getFakeAddress())), true);
369 } else if (tt.child(0).head().equals("[")) {
370 literal = parseSSL(tt.child(0));
372 literal = number(tt.child(0));
375 if ("int".equals(tt.child(1).head())) {
376 count = (int)number(tt.child(1));
377 } else if ("forever".equals(tt.child(1).head())) {
382 if (FleetTwoFleet.isSmallEnoughToFit(literal)) {
383 cb.add(new Set(dock, looping, predicate, SetDest.DataLatch, (literal)));
385 // FIXME bitwidth hardwired!
386 cb.add(new Shift(dock, looping, predicate, new BitVector(37).set(getField(36, 19, literal))));
387 cb.add(new Shift(dock, looping, predicate, new BitVector(37).set(getField(18, 0, literal))));
393 boolean requeue = false;
394 ttx = tt.child(1).head().equals("Commands") ? tt.child(1) : tt;
395 if ("int".equals(tt.child(2).head())) {
396 count = (int)number(tt.child(2));
398 } else if ("forever".equals(tt.child(2).head())) {
403 if (tt.head().equals("[*]")) {
404 cb.add(new Set(dock, looping, predicate, SetDest.InnerLoopCounter, SetSource.Infinity));
407 } else if (tt.head().equals("int")) {
408 count = (int)number(tt);
411 boolean tokenIn = false;
412 boolean dataIn = false;
413 boolean latch = false;
414 boolean dataOut = false;
415 boolean tokenOut = false;
416 boolean dispatch = false;
417 boolean localLiteral = false;
418 boolean ignoreUntilLast = false;
421 for(int i=0; i<ttx.size(); i++) {
422 Tree ttt = ttx.child(i);
423 if ("wait".equals(ttt.head())) { tokenIn = true; }
424 else if ("nop".equals(ttt.head())) { }
425 else if ("discard".equals(ttt.head())) { dataIn = true; latch = false; }
426 else if ("take".equals(ttt.head())) { dataIn = true; latch = true; }
427 else if ("recv".equals(ttt.head())) { dataIn = true; latch = true; }
428 else if ("collect".equals(ttt.head())) { dataIn = true; latch = true; }
429 else if ("recieve".equals(ttt.head())) { dataIn = true; latch = true; }
430 else if ("send".equals(ttt.head())) { dispatch = true; dataOut = true; }
431 else if ("sendto".equals(ttt.head())) { dataOut = true; path = path(dock, ttt.child(0)); }
432 else if ("deliver".equals(ttt.head())) { dataOut = true; }
433 else if ("notify".equals(ttt.head())) { tokenOut = true; path = path(dock, ttt.child(0)); }
434 else if ("notifyLast".equals(ttt.head())) { tokenOut = true; ignoreUntilLast = true; path = path(dock, ttt.child(0)); }
436 cb.add(new Move(dock, looping, predicate,
437 interruptible, path, tokenIn, dataIn,
438 latch, dispatch, dataOut, tokenOut));
443 private class CodeBag extends ArrayList<Instruction> {
444 public long address = -1;
445 public final String name;
446 private HashSet<Integer> isCBD = new HashSet<Integer>();
447 public CodeBag() { codeBags.add(this); this.name = "root"; }
448 public CodeBag(String name) { codeBags.add(this); codeBagsByName.put(name, this); this.name = name; }
449 public long getFakeAddress() { return codeBags.indexOf(this); }
450 public boolean equals(Object o) { return this==o; }
451 public void add(Instruction i, boolean isCBD) {
452 if (isCBD) this.isCBD.add(size());
458 public static ArrayList<Long> expect;
459 public static boolean skip;
461 private static long number(Tree t) {
463 for(Object c : t.child(2)) ret += ((Tree)c).head();
464 boolean negative = "-".equals(t.child(0).head());
467 if ("0x".equals(t.child(1).head())) val = Long.parseLong(ret, 16);
468 else if ("0b".equals(t.child(1).head())) val = Long.parseLong(ret, 2);
469 else val = Long.parseLong(ret);
470 if (negative) val = -1L * val;
474 * This interface marks Fleets which can create ships on the fly, like the fleeterpreter;
475 * if available, the parser will use this interface to create ships out of #ship definitions.
477 public static interface FleetWithDynamicShips {
478 public Ship createShip(String shiptype, String shipname);