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.*;
12 * @author Adam Megacz <megacz@cs.berkeley.edu>
17 expect = new ArrayList<Long>();
21 //////////////////////////////////////////////////////////////////////////////
24 private ArrayList<String> imports = new ArrayList<String>();
26 private HashMap<String,Ship> shipMap = new HashMap<String,Ship>();
28 // codebags in numerical order
29 private ArrayList<CodeBag> codeBags = new ArrayList<CodeBag>();
30 private HashMap<String,CodeBag> codeBagsByName = new HashMap<String,CodeBag>();
32 private CodeBag getCodeBag(String name) {
33 CodeBag cb = codeBagsByName.get(name);
34 if (cb!=null) return cb;
35 return new CodeBag(name);
38 private static Union grammar;
39 private static synchronized Union getGrammar() throws Exception {
40 if (grammar != null) return grammar;
41 InputStream grammarStream =
42 Parser.class.getClassLoader().getResourceAsStream("edu/berkeley/fleet/assembler/fleet.g");
43 CharParser metaGrammarParser = new CharParser(GrammarAST.getMetaGrammar());
44 Tree<String> parsedGrammar = metaGrammarParser.parse(new CharInput(grammarStream)).expand1();
45 grammar = GrammarAST.buildFromAST(parsedGrammar, "s", new GrammarAST.ImportResolver() {
46 public InputStream getImportStream(String importname) { return null; }
51 Tree<String> parse(Reader r) throws Exception {
52 return new CharParser(getGrammar()).parse(new CharInput(r)).expand1();
55 public void parse(Reader r, OutputStream out) throws Exception {
56 // this needs to be "code bag zero"
57 CodeBag baseCodeBag = new CodeBag();
58 CodeBag rootCodeBag = new CodeBag();
60 baseCodeBag.add(new Instruction.CodeBagDescriptor(null, rootCodeBag.getFakeAddress(), 1));
61 walk((Tree<String>)parse(r), rootCodeBag);
62 if (fleet instanceof edu.berkeley.fleet.fpga.Fpga)
63 ((edu.berkeley.fleet.fpga.Fpga)fleet).dumpFabric(true);
65 // map from arbitrary identifiers to actual addresses
66 int[] codeBagMap = new int[codeBags.size()];
67 ByteArrayOutputStream baos = new ByteArrayOutputStream();
68 DataOutputStream dos = new DataOutputStream(baos);
70 for(int i=0; i<codeBags.size(); i++) {
71 CodeBag c = codeBags.get(i);
73 codeBagMap[i] = count;
74 for(Instruction inst : c) {
75 fleet.writeInstruction(dos, inst);
81 dos = new DataOutputStream(out);
83 for(int i=0; i<codeBags.size(); i++) {
84 CodeBag c = codeBags.get(i);
86 for(Instruction inst : c) {
87 if (inst instanceof Instruction.CodeBagDescriptor) {
89 Instruction.CodeBagDescriptor old = (Instruction.CodeBagDescriptor)inst;
90 int offset = codeBagMap[(int)old.offset];// - count;
91 inst = new Instruction.CodeBagDescriptor(old.pump,
93 codeBags.get((int)old.offset).size());
95 fleet.writeInstruction(dos, inst);
104 /** in the first pass, codebags are assigned "addresses" in arbitrary order */
105 void walk(Tree<String> t, CodeBag cb) {
107 String head = t.head();
109 } else if (head.equals("Program")) {
110 for(Tree<String> tc : t.child(0))
113 for(Tree<String> statement : t.child(1))
114 fillCodeBag(statement, cb);
116 } else if (head.equals("#import")) {
119 } else if (head.equals("#ship")) {
120 String name = name(t.child(0));
121 String type = string(t.child(1));
124 if (fleet instanceof Fleet.WithDynamicShips) {
125 Fleet.WithDynamicShips dyn = ((Fleet.WithDynamicShips)fleet);
126 ship = dyn.createShip(type, name);
128 throw new RuntimeException("couldn't find a ship called \""+type+"\"");
130 ship = allocateShip(type);
132 shipMap.put(name, ship);
134 } else if (head.equals("#include")) {
136 walk(parse(new InputStreamReader(new FileInputStream(string(t.child(0))))), cb);
137 } catch (Exception e) {
138 throw new RuntimeException(e);
141 } else if (head.equals("#expect")) {
142 expect.add(number(t.child(0)));
143 } else if (head.equals("#skip")) {
149 String string(Tree<String> t) {
151 if (t.head() != null) ret += t.head();
152 for(Tree<String> c : t)
157 String stringBody(Tree<String> t) {
159 for(Tree<String> c : t)
164 String name(Tree<String> t) {
165 return string(t.child(0))+string(t.child(1));
168 Destination portReference(Tree<String> t) {
169 if (!"Pump".equals(t.head()) && !"Destination".equals(t.head()) && !"ShipSpecificLiteral".equals(t.head())) return null;
170 String shipName = name(t.child(0));
171 String portName = name(t.child(1));
172 String subPort = t.size()<3 ? null : name(t.child(2));
173 Ship ship = shipMap.get(shipName);
174 if (ship==null) throw new RuntimeException("no such ship \""+shipName+"\"");
175 Destination ret = null;
177 for(Pump b : ship.getPumps())
178 if (b.getName().equals(portName)) {
182 throw new RuntimeException("no such pump \""+portName+"\"");
183 if (subPort==null) subPort="";
184 for(Destination d : bb.getDestinations())
185 if (d.getDestinationName().equals(subPort))
188 throw new RuntimeException("no such pump \""+portName+"\" on ships of type \""+ship.getType()+"\"");
192 Pump pump(Tree<String> t) {
193 if (!"Pump".equals(t.head()) && !"Destination".equals(t.head()) && !"ShipSpecificLiteral".equals(t.head()))
194 throw new RuntimeException(t+"");
195 String shipName = name(t.child(0));
196 String portName = name(t.child(1));
197 Ship ship = shipMap.get(shipName);
198 if (ship==null) throw new RuntimeException("no such ship \""+shipName+"\"");
200 for(Pump b : ship.getPumps())
201 if (b.getName().equals(portName))
203 throw new RuntimeException("no such pump \""+portName+"\"");
206 private HashMap<String,Integer> numAllocated = new HashMap<String,Integer>();
208 Ship allocateShip(String shipType) {
210 if (numAllocated.get(shipType) != null)
211 allocated = numAllocated.get(shipType);
212 numAllocated.put(shipType, allocated+1);
213 for(Iterator<Ship> it = fleet.iterator();
217 if (s.getType().equals(shipType)) {
218 if (allocated == 0) return s;
222 throw new RuntimeException("no more ships of type \""+shipType+"\"");
225 private long parseSSL(Tree t) {
226 String shipType = name(t.child(0));
227 String portName = name(t.child(1));
228 Ship chosenship = null;
229 for(Ship ship : fleet) {
230 if (ship.getType().equals(shipType)) {
235 Pump chosenport = chosenship.getPump(portName);
236 Tree specs = t.child(2);
238 for(int i=0; i<specs.size(); i++) {
239 Tree tt = specs.child(i);
240 literal |= chosenport.resolveLiteral(stringBody(tt));
245 private int anoncount = 1;
246 void fillCodeBag(Tree<String> t, CodeBag cb) {
247 if (t.head()==null) return;
248 else if (t.head().equals("CodeBagDef")) {
249 CodeBag cb2 = getCodeBag(name(t.child(0)));
250 for(Tree<String> statement : t.child(1))
251 fillCodeBag(statement, cb2);
253 } else if (t.head().equals("Fiber")) {
254 Pump pump = (Pump)pump(t.child(0));
256 OUTER: for(Tree tt : t.child(1)) {
258 if ("unclog".equals(tt.head())) {
259 cb.add(new Instruction.UnClog(pump));
261 } else if ("clog".equals(tt.head())) {
262 cb.add(new Instruction.Clog(pump));
264 } else if ("kill".equals(tt.head())) {
265 count = tt.size()==0 ? 1 : (int)number(tt.child(0));
266 cb.add(new Instruction.Kill(pump, count));
268 } else if ("massacre".equals(tt.head())) {
269 cb.add(new Instruction.Massacre(pump));
271 } else if ("literal".equals(tt.head())) {
273 if (tt.child(0).head().equals("CodeBagBody")) {
274 Tree<String> tq = tt;
275 CodeBag cb2 = getCodeBag("anon"+(anoncount++));
276 for(Tree<String> statement : tq.child(0))
277 fillCodeBag(statement, cb2);
278 cb.add(new Instruction.CodeBagDescriptor(pump, cb2.getFakeAddress(), 0));
280 } else if (tt.child(0).head().equals("Name")) {
281 String refname = name(tt.child(0));
282 CodeBag cb2 = getCodeBag(refname);
283 cb.add(new Instruction.CodeBagDescriptor(pump, cb2.getFakeAddress(), 0));
285 } else if (tt.child(0).head().equals("[")) {
286 literal = parseSSL(tt.child(0));
288 literal = number(tt.child(0));
291 if ("int".equals(tt.child(1).head())) {
292 count = (int)number(tt.child(1));
293 } else if ("forever".equals(tt.child(1).head())) {
296 cb.add(new Instruction.LocalLiteral(pump, literal, count));
300 boolean requeue = false;
301 ttx = tt.child(1).head().equals("Commands") ? tt.child(1) : tt;
302 if ("int".equals(tt.child(2).head())) {
303 count = (int)number(tt.child(2));
305 } else if ("forever".equals(tt.child(2).head())) {
310 if (tt.head().equals("[*]")) {
313 } else if (tt.head().equals("int")) {
314 count = (int)number(tt);
317 boolean tokenIn = false;
318 boolean dataIn = false;
319 boolean latch = false;
320 boolean dataOut = false;
321 boolean tokenOut = false;
322 boolean dataOutDest = false;
323 boolean localLiteral = false;
324 boolean ignoreUntilLast = false;
326 Destination dest = null;
327 for(int i=0; i<ttx.size(); i++) {
328 Tree ttt = ttx.child(i);
329 if ("wait".equals(ttt.head())) { tokenIn = true; }
330 else if ("nop".equals(ttt.head())) { }
331 else if ("kill".equals(ttt.head())) {
332 cb.add(new Instruction.Kill(pump, count));
335 else if ("discard".equals(ttt.head())) { dataIn = true; latch = false; }
336 else if ("take".equals(ttt.head())) { dataIn = true; latch = true; }
337 else if ("recieve".equals(ttt.head())) { dataIn = true; latch = true; }
338 else if ("send".equals(ttt.head())) { dataOutDest = true; }
339 else if ("sendto".equals(ttt.head())) { dataOut = true; dest = portReference(ttt.child(0)); }
340 else if ("deliver".equals(ttt.head())) { dataOut = true; }
341 else if ("notify".equals(ttt.head())) { tokenOut = true; dest = portReference(ttt.child(0)); }
342 else if ("notifyLast".equals(ttt.head())) { tokenOut = true; ignoreUntilLast = true; dest = portReference(ttt.child(0)); }
344 cb.add(new Instruction.Move(pump,
345 dest, count, tokenIn, dataIn,
346 latch, dataOutDest, dataOut, tokenOut, requeue, ignoreUntilLast));
351 private class CodeBag extends ArrayList<Instruction> {
352 public long address = -1;
353 public final String name;
354 public CodeBag() { codeBags.add(this); this.name = "root"; }
355 public CodeBag(String name) { codeBags.add(this); codeBagsByName.put(name, this); this.name = name; }
356 public long getFakeAddress() { return codeBags.indexOf(this); }
357 public boolean equals(Object o) { return this==o; }
361 public static ArrayList<Long> expect;
362 public static boolean skip;
364 private static long number(Tree t) {
366 for(Object c : t.child(2)) ret += ((Tree)c).head();
367 boolean negative = "-".equals(t.child(0).head());
370 if ("0x".equals(t.child(1).head())) val = Long.parseLong(ret, 16);
371 else if ("0b".equals(t.child(1).head())) val = Long.parseLong(ret, 2);
372 else val = Long.parseLong(ret);
373 if (negative) val = -1L * val;