diff options
| -rw-r--r-- | .gitignore | 4 | ||||
| -rw-r--r-- | Makefile | 8 | ||||
| -rw-r--r-- | notes/initialize-register-explanation.txt | 81 | ||||
| -rw-r--r-- | notes/stanza-cheatsheet.txt | 9 | ||||
| -rw-r--r-- | src/main/stanza/firrtl-ir.stanza | 1 | ||||
| -rw-r--r-- | src/main/stanza/firrtl-main.stanza | 2 | ||||
| -rw-r--r-- | src/main/stanza/ir-utils.stanza | 6 | ||||
| -rw-r--r-- | src/main/stanza/passes.stanza | 256 | ||||
| -rw-r--r-- | test/hello.fir (renamed from test/unit/hello.fir) | 0 | ||||
| -rw-r--r-- | test/passes/initialize-register/begin.fir | 22 | ||||
| -rw-r--r-- | test/passes/initialize-register/when.fir | 40 | ||||
| -rw-r--r-- | test/passes/make-explicit-reset/abc.fir | 27 | ||||
| -rw-r--r-- | test/passes/resolve-kinds/ab.fir (renamed from test/unit/gcd.fir) | 0 | ||||
| -rw-r--r-- | test/simple.fir (renamed from test/unit/simple.fir) | 0 | ||||
| -rw-r--r-- | test/syntax/letrec-non-struct.fir | 9 |
15 files changed, 341 insertions, 124 deletions
@@ -12,3 +12,7 @@ src/main/stanza/firrtl-main utils/bin/firrtl test/unit/Output test/unit/*.out +spec/spec.aux +spec/spec.log +spec/spec.pdf +spec/spec.synctex.gz @@ -13,5 +13,9 @@ build: # Runs single test check: - cd $(test_dir) && lit -v . --path=$(root_dir)/utils/bin/ - cat $(test_dir)/unit/gcd.fir.out + cd $(test_dir)/passes && lit -v . --path=$(root_dir)/utils/bin/ + +clean: + rm -f $(test_dir)/passes/*/*.out + rm -f $(test_dir)/passes/*.out + rm -f $(test_dir)/*/*.out diff --git a/notes/initialize-register-explanation.txt b/notes/initialize-register-explanation.txt new file mode 100644 index 00000000..27bbde52 --- /dev/null +++ b/notes/initialize-register-explanation.txt @@ -0,0 +1,81 @@ +reg r: UInt(16) + +=> + +reg r: UInt(16) +wire r_init : UInt(16) +r_init := NULL + +when reset : + r := r_init + +=============== + +reg r: UInt(16) +r.init := UInt(0) + +=> + +reg r: UInt(16) +wire r_init : UInt(16) +r_init := NULL +r_init := UInt(0) +when reset : + r := r_init + +=> + +reg r: UInt(16) +wire r_init2 : UInt(16) +r_init2 := NULL +wire r_init : UInt(16) +r_init := NULL +r_init := UInt(0) +when reset : + r := r_init +when reset : + r := r_init2 + + +====== + +We continue to simplify from the previous example. Here's the input we had (but with the incorrect lines removed). + +reg r: UInt(16) +wire r_init2 : UInt(16) +r_init2 := NULL +wire r_init : UInt(16) +r_init := NULL +r_init := UInt(0) +when reset : + r := r_init +when reset : + r := r_init2 + +One of the following passes will turn wires into nodes, by scanning to see what they are connected to. + +reg r: UInt(16) +node r_init2 = NULL +node r_init = UInt(0) +when reset : + r := r_init +when reset : + r := r_init2 + +Another pass will compute the final value connected to the register, expressed as a bunch of muxes. The default value for a register is set to itself. + +node r_init2 = NULL +node r_init = UInt(0) +reg r:UInt(16) = Mux(reset, r_init2, Mux(reset, r_init, r)) + +Next we inline all the nodes with NULL in them, to arrive at the final expression for the register. + +reg r:UInt(16) = Mux(reset, NULL, Mux(reset, r_init, r)) + +NULL's do nothing, so any expression of the form Mux(a, NULL, b) can be simplified to b. Arriving finally at: + +reg r:UInt(16) = Mux(reset, r_init, r) + +which is what we wanted. + + diff --git a/notes/stanza-cheatsheet.txt b/notes/stanza-cheatsheet.txt index d8f5c070..09342997 100644 --- a/notes/stanza-cheatsheet.txt +++ b/notes/stanza-cheatsheet.txt @@ -46,3 +46,12 @@ a typeof T a and b a or b a as T + + +append(list1,list2) -> list1,list2 +List(x,list) -> x,list +list() -> empty +list(a) -> a +list(a,b) -> a,b + +println-all([a b c]) diff --git a/src/main/stanza/firrtl-ir.stanza b/src/main/stanza/firrtl-ir.stanza index 53902c1c..9ec4b666 100644 --- a/src/main/stanza/firrtl-ir.stanza +++ b/src/main/stanza/firrtl-ir.stanza @@ -65,6 +65,7 @@ public defstruct ReadPort <: Expression : mem: Expression index: Expression type: Type [multi => false] +public defstruct Null <: Expression public definterface Stmt public defstruct LetRec <: Stmt : diff --git a/src/main/stanza/firrtl-main.stanza b/src/main/stanza/firrtl-main.stanza index 29edbc14..1f87b1da 100644 --- a/src/main/stanza/firrtl-main.stanza +++ b/src/main/stanza/firrtl-main.stanza @@ -23,7 +23,7 @@ defn main () : val args = split(arg,' ') val lexed = lex-file(args[1]) val c = parse-firrtl(lexed) - println(c) + ;println(c) run-passes(c,to-list(args[2])) main() diff --git a/src/main/stanza/ir-utils.stanza b/src/main/stanza/ir-utils.stanza index 7edbcb1c..7fe61ff2 100644 --- a/src/main/stanza/ir-utils.stanza +++ b/src/main/stanza/ir-utils.stanza @@ -55,6 +55,7 @@ defmethod print (o:OutputStream, e:Expression) : print-all(o, join(concat(args(e), consts(e)), ", ")) print(o, ")") (e:ReadPort) : print-all(o, ["ReadPort(" mem(e) ", " index(e) ")"]) + (e:Null) : print-all(o, ["Null"]) defmethod print (o:OutputStream, c:Stmt) : match(c) : @@ -227,7 +228,7 @@ defmethod children (c:Stmt) : (c:Begin) : body(c) (c) : List() -;=================== STRING OPS =============================== +;=================== ADAM OPS =============================== public defn split (s:String,c:Char) -> List<String> : val empty = "" defn next-word (s:String,i:Int) -> String|False : @@ -249,3 +250,6 @@ public defn contains (l:List<Char>, c:Char) : if x == c : myret(true) false +public defn merge!<?K,?V> (a:HashTable<?K,?V>, b:HashTable<K,V>) : + for e in b do : + a[key(e)] = value(e) diff --git a/src/main/stanza/passes.stanza b/src/main/stanza/passes.stanza index 8c25342d..eb9151ab 100644 --- a/src/main/stanza/passes.stanza +++ b/src/main/stanza/passes.stanza @@ -152,7 +152,7 @@ defn resolve-kinds (c:Circuit) : kinds[name(p)] = PortKind() find-stmt(body(m)) - defn resolve-module (m:Module, c:Circuit) -> Module : + defn resolve-kinds (m:Module, c:Circuit) -> Module : val kinds = HashTable<Symbol,Kind>(symbol-hash) for m in modules(c) do : kinds[name(m)] = ModuleKind() @@ -163,126 +163,140 @@ defn resolve-kinds (c:Circuit) : Circuit(modules*, main(c)) where : val modules* = for m in modules(c) map : - resolve-module(m,c) + resolve-kinds(m,c) -;=============== MAKE RESET EXPLICIT ======================= -defn make-explicit-reset (c:Circuit) : - defn reset-instances (c:Stmt, reset?: List<Symbol>) -> Stmt : - match(c) : - (c:DefInstance) : - val module = module(c) as WRef - if contains?(reset?, name(module)) : - c - else : - Begin $ list(c, Connect(WField(inst, `reset, UnknownType(), UNKNOWN-DIR), reset)) where : - val inst = WRef(name(c), UnknownType(), InstanceKind(), UNKNOWN-DIR) - val reset = WRef(`reset, UnknownType(), PortKind(), UNKNOWN-DIR) - (c) : - map(reset-instances{_:Stmt, reset?}, c) - - defn make-explicit-reset (m:Module, reset-list: List<Symbol>) : - val reset? = contains?(reset-list, name(m)) - - ;Add reset port if necessary - val ports* = - if reset? : - ports(m) - else : - val reset = Port(`reset, INPUT, UIntType(IntWidth(1))) - List(reset, ports(m)) +;=============== MAKE EXPLICIT RESET ======================= +; All modules have an implicit reset signal - however, the +; programmer can explicitly reference this signal if desired. +; This pass makes all implicit resets explicit while +; preserving any previously explicit resets +; If reset is not explicitly passed to instantiations, then this +; pass autmatically connects the parent module's reset to the +; instantiation's reset - ;Reset Instances - val body* = reset-instances(body(m), reset-list) - val m* = Module(name(m), ports*, body*) +defn make-explicit-reset (c:Circuit) : + defn find-explicit (c:Circuit) -> List<Symbol> : + defn explicit? (m:Module) -> True|False : + for p in ports(m) any? : + name(p) == `reset + val explicit-reset = Vector<Symbol>() + for m in modules(c) do: + if explicit?(m) : add(explicit-reset,name(m)) + to-list(explicit-reset) - ;Initialize registers if necessary - if reset? : m* - else : initialize-registers(m*) + defn make-explicit (m:Module, explicit-reset:List<Symbol>) -> Module : + defn route-reset (s:Stmt) -> Stmt : + match(s) : + (s:DefInstance) : + val iref = WField(WRef(name(s), UnknownType(), InstanceKind(), UNKNOWN-DIR),`reset,UnknownType(),UNKNOWN-DIR) + val pref = WRef(`reset, UnknownType(), PortKind(), INPUT) + Begin(to-list([s,Connect(iref,pref)])) + (s) : map(route-reset,s) + + var ports! = ports(m) + if not contains?(explicit-reset,name(m)) : + ports! = append(ports(m),list(Port(`reset,INPUT,UIntType(IntWidth(1))))) + val body! = route-reset(body(m)) + Module(name(m),ports!,body!) + + defn make-explicit-reset (m:Module, c:Circuit) -> Module : + val explicit-reset = find-explicit(c) + make-explicit(m,explicit-reset) Circuit(modules*, main(c)) where : - defn reset? (m:Module) : - for p in ports(m) any? : - name(p) == `reset - val reset-list = to-list(stream(name, filter(reset?, modules(c)))) - val modules* = map(make-explicit-reset{_, reset-list}, modules(c)) + val modules* = + for m in modules(c) map : + make-explicit-reset(m,c) ;======= MAKE EXPLICIT REGISTER INITIALIZATION ============= -defn initialize-registers (m:Module) : - ;=== Initializing Expressions === - defn init-exps (inits: List<KeyValue<Symbol,Expression>>) : - if empty?(inits) : - EmptyStmt() - else : - Conditionally(reset, Begin(map(connect, inits)), EmptyStmt()) where : - val reset = WRef(`reset, UnknownType(), PortKind(), UNKNOWN-DIR) - defn connect (init: KeyValue<Symbol, Expression>) : - val reg-ref = WRef(key(init), UnknownType(), RegKind(), UNKNOWN-DIR) - Connect(reg-ref, value(init)) - - defn initialize-registers (c: Stmt - inits: List<KeyValue<Symbol,Expression>>) -> - [Stmt, List<KeyValue<Symbol,Expression>>] : - ;=== Rename Expressions === - defn rename (e:Expression) : +; This pass replaces the reg.init construct by creating a new +; wire that holds the value at initialization. This wire +; is then connected to the register conditionally on reset, +; at the end of that register's scope. +; If a register has no inital value, the wire is connected to +; a NULL node. Later passes will remove these with the base +; case Mux(reset,NULL,a) -> a, and Mux(reset,a,NULL) -> a. +; This ensures proper behavior if this pass is run multiple +; times. + +defn initialize-registers (c:Circuit) : + defn add-when (s:Stmt,renames:HashTable<Symbol,Symbol>) -> Stmt : + Begin(list(s,when-reset)) where : + var inits = List<Stmt>() + for kv in renames do : + val refreg = WRef(key(kv),UnknownType(),RegKind(),UNKNOWN-DIR) + val refwire = WRef(value(kv),UnknownType(),NodeKind(),UNKNOWN-DIR) + val connect = Connect(refreg,refwire) + inits = append(inits,list(connect)) + val pred = WRef(`reset, UnknownType(), PortKind(), UNKNOWN-DIR) + val when-reset = Conditionally(pred,Begin(inits),Begin(List<Stmt>())) + defn rename (s:Stmt,l:HashTable<Symbol, Symbol>) -> Stmt : + defn rename-stmt (s:Stmt) -> Stmt : + map{rename-expr,_} $ + map(rename-stmt,s) + defn rename-expr (e:Expression) -> Expression : match(e) : - (e:WField) : - switch {name(e) == _} : - `init : - if reg?(exp(e)) : init-wire(exp(e)) - else : map(rename, e) - else : map(rename, e) - (e) : map(rename, e) - defn reg? (e:Expression) : + (e:WField) : + if name(e) == `init and register?(exp(e)) : + ;TODO Error if l does not contain register + val new-name = l[name(exp(e) as WRef)] + WRef(new-name,UnknownType(),NodeKind(),UNKNOWN-DIR) + else : e + (e) : map(rename-expr,e) + defn register? (e:Expression) -> True|False : match(e) : (e:WRef) : kind(e) typeof RegKind (e) : false - defn init-wire (e:Expression) : - lookup!(inits, name(e as WRef)) - ;=== Driver === - match(c) : - (c:DefRegister) : - [new-command, list(init-entry)] where : - val wire-name = gensym() - val wire-ref = WRef(wire-name, UnknownType(), NodeKind(), UNKNOWN-DIR) - val reg-ref = WRef(name(c), UnknownType(), RegKind(), UNKNOWN-DIR) - val def-init-wire = DefWire(wire-name, type(c)) - val init-wire = Connect(wire-ref, reg-ref) - val init-reg = Connect(reg-ref, wire-ref) - val new-command = Begin(to-list([c, def-init-wire, init-wire, init-reg])) - val init-entry = name(c) => wire-ref - (c:Conditionally) : - val pred* = rename(pred(c)) - val [conseq* con-inits] = initialize-registers(conseq(c), inits) - val [alt* alt-inits] = initialize-registers(alt(c), inits) - val c* = Conditionally(pred*, conseq+inits, alt+inits) where : - val conseq+inits = Begin(list(conseq*, init-exps(con-inits))) - val alt+inits = Begin(list(alt*, init-exps(alt-inits))) - [c*, List()] - (c:LetRec) : - val c* = map(rename, c) - val [body*, body-inits] = initialize-registers(body(c), inits) - val new-command = - LetRec(entries(c*), body+inits) where : - val body+inits = Begin(list(body*, init-exps(body-inits))) - [new-command, List()] - (c:Begin) : - var inits-in:List<KeyValue<Symbol,Expression>> = inits - var inits-out:List<KeyValue<Symbol,Expression>> = List() - val body* = - for c in body(c) map : - val [c* inits*] = initialize-registers(c, inits-in) - inits-in = append(inits*, inits-in) - inits-out = append(inits*, inits-out) - c* - [Begin(body*), inits-out] - (c) : - val c* = map(rename, c) - [c*, List()] + rename-stmt(s) + + defn initialize-registers (s:Stmt) -> [Stmt,HashTable<Symbol, Symbol>] : + val empty-hash = HashTable<Symbol,Symbol>(symbol-hash) + match(s) : + (s:Begin) : + var body! = List<Stmt>() + var renames = HashTable<Symbol,Symbol>(symbol-hash) + for s in body(s) do : + val [s!,renames!] = initialize-registers(s) + body! = append(body!,list(s!)) + merge!(renames,renames!) + [Begin(body!),renames] + (s:DefRegister) : + val wire-name = gensym() + val renames = HashTable<Symbol, Symbol>(symbol-hash) + renames[name(s)] = wire-name + [Begin(body!),renames] where : + val defreg = s + val defwire = DefWire(wire-name,type(s)) + val conwire = Connect(WRef(wire-name,type(s),NodeKind(),UNKNOWN-DIR),Null()) + val body! = list(defreg,defwire,conwire) + (s:Conditionally) : + [Conditionally(pred(s),initialize-scope(conseq(s)),initialize-scope(alt(s))),empty-hash] + ;TODO Add Letrec + (s) : [s,empty-hash] + + + defn initialize-scope (s:Stmt) -> Stmt : + defn run-initialize (s:Stmt) -> Stmt : + val [s!,renames] = initialize-registers(s) + val s!! = rename(s!,renames) + val s!!! = add-when(s!!,renames) + s!!! + match(s) : + (s:Begin) : run-initialize(s) + (s:DefRegister) : run-initialize(s) + (s:Conditionally) : run-initialize(s) + ;TODO Add Letrec + (s) : s + + defn initialize-scope (m:Module) -> Module : + Module(name(m), ports(m), body!) where : + val body! = initialize-scope(body(m)) - Module(name(m), ports(m), body+inits) where : - val [body*, inits] = initialize-registers(body(m), List()) - val body+inits = Begin(list(body*, init-exps(inits))) + Circuit(modules*, main(c)) where : + val modules* = + for m in modules(c) map : + initialize-scope(m) ;============== INFER TYPES ================================ @@ -1870,21 +1884,23 @@ public defn run-passes (c: Circuit, p: List<Char>) : println(name) c* = f(c*) - + ; Early passes: + ; If modules have a reset defined, must be an INPUT and UInt(1) if contains(p,'a') : do-stage("Working IR", to-working-ir) if contains(p,'b') : do-stage("Resolve Kinds", resolve-kinds) if contains(p,'c') : do-stage("Make Explicit Reset", make-explicit-reset) - if contains(p,'d') : do-stage("Infer Types", infer-types) - if contains(p,'e') : do-stage("Infer Directions", infer-directions) - if contains(p,'f') : do-stage("Expand Accessors", expand-accessors) - if contains(p,'g') : do-stage("Flatten Bundles", flatten-bundles) - if contains(p,'h') : do-stage("Expand Bundles", expand-bundles) - if contains(p,'i') : do-stage("Expand Multi Connects", expand-multi-connects) - if contains(p,'j') : do-stage("Expand Whens", expand-whens) - if contains(p,'k') : do-stage("Structural Form", structural-form) - if contains(p,'l') : do-stage("Infer Widths", infer-widths) - if contains(p,'m') : do-stage("Pad Widths", pad-widths) - if contains(p,'n') : do-stage("Inline Instances", inline-instances) + if contains(p,'d') : do-stage("Initialize Registers", initialize-registers) + if contains(p,'e') : do-stage("Infer Types", infer-types) + if contains(p,'f') : do-stage("Infer Directions", infer-directions) + if contains(p,'g') : do-stage("Expand Accessors", expand-accessors) + if contains(p,'h') : do-stage("Flatten Bundles", flatten-bundles) + if contains(p,'i') : do-stage("Expand Bundles", expand-bundles) + if contains(p,'j') : do-stage("Expand Multi Connects", expand-multi-connects) + if contains(p,'k') : do-stage("Expand Whens", expand-whens) + if contains(p,'l') : do-stage("Structural Form", structural-form) + if contains(p,'m') : do-stage("Infer Widths", infer-widths) + if contains(p,'n') : do-stage("Pad Widths", pad-widths) + if contains(p,'o') : do-stage("Inline Instances", inline-instances) println(c*) println("\n\n\n\n") diff --git a/test/unit/hello.fir b/test/hello.fir index 4a905ab9..4a905ab9 100644 --- a/test/unit/hello.fir +++ b/test/hello.fir diff --git a/test/passes/initialize-register/begin.fir b/test/passes/initialize-register/begin.fir new file mode 100644 index 00000000..9d4de49e --- /dev/null +++ b/test/passes/initialize-register/begin.fir @@ -0,0 +1,22 @@ +; RUN: firrtl %s abcd | tee %s.out | FileCheck %s + + circuit top : + module top : + input a : UInt(16) + input b : UInt(16) + output z : UInt + + reg r1 : UInt +; CHECK: wire [[R1:gen[0-9]*]] : UInt +; CHECK: n:[[R1]] := Null + + reg r2 : UInt + r2.init := UInt(0) +; CHECK: wire [[R2:gen[0-9]*]] : UInt +; CHECK-NOT: reg:r2 := n:[[R2]] +; CHECK: n:[[R2]] := Null +; CHECK: n:[[R2]] := UInt(0) + +; CHECK: when port:reset : +; CHECK-DAG: reg:r1 := n:[[R1]] +; CHECK-DAG: reg:r2 := n:[[R2]] diff --git a/test/passes/initialize-register/when.fir b/test/passes/initialize-register/when.fir new file mode 100644 index 00000000..e4749abe --- /dev/null +++ b/test/passes/initialize-register/when.fir @@ -0,0 +1,40 @@ +; RUN: firrtl %s abcd | tee %s.out | FileCheck %s +; CHECK: circuit top : + circuit top : + module top : + input a : UInt(16) + input b : UInt(16) + output z : UInt + when greater(1, 2) : + reg r1: UInt + r1.init := UInt(12) +; CHECK: wire [[R1:gen[0-9]*]] : UInt +; CHECK-NOT: reg:r1 := n:[[R1]] +; CHECK: n:[[R1]] := Null +; CHECK: n:[[R1]] := UInt(12) +; CHECK-NOT: r1.init := UInt(12) + reg r2: UInt +; CHECK: wire [[R2:gen[0-9]*]] : UInt +; CHECK-NOT: reg:r2 := n:[[R2]] +; CHECK: n:[[R2]] := Null + +; CHECK: when port:reset : +; CHECK-DAG: reg:r2 := n:[[R2]] +; CHECK-DAG: reg:r1 := n:[[R1]] + else : + reg r1: UInt + r1.init := UInt(12) +; CHECK: wire [[R1:gen[0-9]*]] : UInt +; CHECK-NOT: reg:r1 := n:[[R1]] +; CHECK: n:[[R1]] := Null +; CHECK: n:[[R1]] := UInt(12) +; CHECK-NOT: r1.init := UInt(12) + + reg r2: UInt +; CHECK: wire [[R2:gen[0-9]*]] : UInt +; CHECK-NOT: reg:r2 := n:[[R2]] +; CHECK: n:[[R2]] := Null + +; CHECK: when port:reset : +; CHECK-DAG: reg:r2 := n:[[R2]] +; CHECK-DAG: reg:r1 := n:[[R1]] diff --git a/test/passes/make-explicit-reset/abc.fir b/test/passes/make-explicit-reset/abc.fir new file mode 100644 index 00000000..caed07ab --- /dev/null +++ b/test/passes/make-explicit-reset/abc.fir @@ -0,0 +1,27 @@ +; RUN: firrtl %s abc | tee %s.out | FileCheck %s + +circuit top : + module A : + ;CHECK: input reset : UInt(1) + input x : UInt(16) + output y : UInt(16) + inst b of B + ;CHECK: inst:b.reset := port:reset + module B : + input reset : UInt(1) + ;CHECK: input reset : UInt(1) + input x : UInt(16) + output y : UInt(16) + inst c of C + ;CHECK: inst:c.reset := port:reset + module C : + ;CHECK: input reset : UInt(1) + input a : UInt(16) + input b : UInt(16) + module top : + ;CHECK: input reset : UInt(1) + input a : UInt(16) + input b : UInt(16) + output z : UInt + inst a of A + ;CHECK: inst:a.reset := port:reset diff --git a/test/unit/gcd.fir b/test/passes/resolve-kinds/ab.fir index e6f28c21..e6f28c21 100644 --- a/test/unit/gcd.fir +++ b/test/passes/resolve-kinds/ab.fir diff --git a/test/unit/simple.fir b/test/simple.fir index d00f8f7a..d00f8f7a 100644 --- a/test/unit/simple.fir +++ b/test/simple.fir diff --git a/test/syntax/letrec-non-struct.fir b/test/syntax/letrec-non-struct.fir new file mode 100644 index 00000000..37fb2123 --- /dev/null +++ b/test/syntax/letrec-non-struct.fir @@ -0,0 +1,9 @@ +; RUN: firrtl %s | tee %s.out | FileCheck %s +circuit top: + module top: + input x : UInt(16) + output y : UInt(16) + letrec: + reg r : UInt(10) + in: + r := UInt(11) |