diff options
| -rw-r--r-- | .gitignore | 2 | ||||
| -rw-r--r-- | TODO | 25 | ||||
| -rw-r--r-- | notes/chisel.04.06.15.txt | 207 | ||||
| -rw-r--r-- | notes/memory.txt | 40 | ||||
| -rw-r--r-- | spec/spec.pdf | bin | 0 -> 144166 bytes | |||
| -rw-r--r-- | spec/spec.tex | 11 | ||||
| -rw-r--r-- | src/main/stanza/firrtl-test-main.stanza | 1 | ||||
| -rw-r--r-- | src/main/stanza/ir-utils.stanza | 184 | ||||
| -rw-r--r-- | src/main/stanza/passes.stanza | 699 | ||||
| -rw-r--r-- | test/passes/expand-whens/partial-init.fir | 9 | ||||
| -rw-r--r-- | test/passes/infer-widths/gcd.fir | 45 | ||||
| -rw-r--r-- | test/passes/jacktest/bundlewire.fir | 20 | ||||
| -rw-r--r-- | test/passes/jacktest/vecshift.fir | 24 |
13 files changed, 786 insertions, 481 deletions
@@ -8,6 +8,7 @@ */*/*.swp */*/*/*.swp src/lib/stanzam +src/lib/stanza src/*/__MACOSX src/main/stanza/firrtl-main utils/bin/firrtl @@ -17,5 +18,4 @@ test/passes/*.out test/passes/*/*.out spec/spec.aux spec/spec.log -spec/spec.pdf spec/spec.synctex.gz @@ -1,5 +1,24 @@ TODO change parser to use <> syntax (and update all tests) + think about on-reset + make instances always male, flip the bundles on declaration + write out FIFO example pass + write out diff mem examples and how we will support it + instances can be bulk connected -> change := semantics to: + F := M -> F := M (legal) + M := F -> M := F (legal) + M := M -> (illegal) + F := F -> (illegal) + B := B -> F := M (legal) + F := U -> F := M (legal) + M := U -> M := F (legal) + U := M -> F := M (legal) + U := F -> M := F (legal) + U := U -> U := U (legal) + Address this in gender inference pass, when see M := F, replace with F := M + What if Instances were Male always? And its type is the flipped version of module?? + + talk to palmer/patrick about how writing passes is going to be supported Write lowering step for primops Figure out how widths propogate for all updated primops (Adam) @@ -16,6 +35,7 @@ TODO Update spec add new field for sequential or combinational add assertions + cannot connect directly to a mem (loc can never contain a mem) Future questions to address in spec: Introduction – motivation, and intended usage Philosophical justifications for all constructs @@ -49,3 +69,8 @@ defnode n = e ==> wire n e := n + + + +Front-end needs to guarantee unique names per module. +FIRRTL rule: No name can be a prefix of any other name. diff --git a/notes/chisel.04.06.15.txt b/notes/chisel.04.06.15.txt new file mode 100644 index 00000000..67f80aa5 --- /dev/null +++ b/notes/chisel.04.06.15.txt @@ -0,0 +1,207 @@ +=================================== +Supporting Memory Variety in FIRRTL +=================================== + +----------- Masks? ------------------ + +== High FIRRTL == +mem m : { tag : UInt<10> data : UInt<128> }[32] +accessor w = m[i] + +== Low FIRRTL == +mem m : { tag : UInt<10> data : UInt<128> }[32] +wire w#tag : UInt<10> +wire w#data : UInt<128> +WritePort(m.tag,i,en*) := w#tag +WritePort(m.data,i,en*) := w#data + +== Example Backend == ;Keep merged mem for masks, easy because mem declaration preserves bundle type +mem m : UInt<138>[32] +wire w : UInt<138> +wire w#tag : UInt<10> +wire w#data : UInt<128> +w := concat(w#tag,w#concat) +MaskedWritePort(m,i,mask*) := w ; mask* calculated from enables and mem declaration + +== Example Backend == ;Split mem, easy because accessors are bundle-expanded +mem m#tag : UInt<10>[32] +mem m#data : UInt<128>[32] +wire w#tag : UInt<10> +WritePort(m#tag,i,en*) := w#tag +wire w#data : UInt<128> +WritePort(m#data,i,en*) := w#data + + +--------- Combination/Sequential Reads? ---------- + +== High FIRRTL == +cmem m-com : UInt<128>[32] +smem m-seq : UInt<128>[32] + +== Low FIRRTL == +cmem m-com : UInt<128>[32] ;FIRRTL does nothing +smem m-seq : UInt<128>[32] + + +--------- Read&Write Ports? --------------- + +read accessor r = m[i] +write accessor w = m[i] +readwrite accessor rw = m[i] +? accessor u = m[i] /can infer read, write, but not readwrite + + +== Chisel == +val m = Mem(UInt(128),32) +val rw = ReadWritePort(m,index) + +== High FIRRTL == +mem m : UInt<128>[32] +readwrite accessor rw = m[index] + +== Low FIRRTL == +mem m<1> : UInt<128>[32] ;r/w ports are always synchronous because writes always synchronous +wire rw : UInt<128> +rw := ReadWritePort(m,index,ren*,wen*) + +== Backends == + ; Example of read/write to same address, can handle differently in BRAM's on FPGA, + but is undefined for SRAMs. (Specifically for Synchronous). + +----------- Notes ----------------- + + Catch-all is to always use black boxes + We are not absorbing registers! + User registers the address input, and chisel is allowed to retime the register into the address + Not firrtl's job to autotune - that is the library writer (ASIC backend? FIRRTL library?) + e.g. FPGA backend is an executable that iterates and does DSE + + + +================================ +Supporting Annotations in FIRRTL +================================ + +Example pass: +We have a decoupled interface in Chisel - {data:UInt, valid:UInt, flip ready:UInt} - and want +to test our design by adding a random number of buffers between every bulk connect of this type. + +== High FIRRTL == +wire a : { data : UInt<32>, valid : UInt<1>, flip ready : UInt<1> } +wire b : { data : UInt<32>, valid : UInt<1>, flip ready : UInt<1> } +b := a + +== Low FIRRTL, no FIFO PASS == +wire a#data : UInt<32> +wire a#valid : UInt<1> +wire a#ready : UInt<1> +wire b#data : UInt<32> +wire b#valid : UInt<1> +wire b#ready : UInt<1> +b#data := a#data +b#valid := a#valid +a#ready := b#ready + +== High FIRRTL after FIFO Pass == +wire a : { data : UInt, valid : UInt, flip ready : UInt } +reg r : { data : UInt, valid : UInt, flip ready : UInt } +wire b : { data : UInt, valid : UInt, flip ready : UInt } +r := a +b := r + +== Low FIRRTL after FIFO Pass == +wire a#data : UInt<32> +wire a#valid : UInt<1> +wire a#ready : UInt<1> +wire b#data : UInt<32> +wire b#valid : UInt<1> +wire b#ready : UInt<1> +reg r#data : UInt<32> +reg r#valid : UInt<1> +reg r#ready : UInt<1> +r#data := a#data +r#valid := a#valid +a#ready := r#ready +b#data := r#data +b#valid := r#valid +r#ready := b#ready + +-------- Option 1: Only Unique IDs -------- +FIRRTL provides no support for annotations, except guaranteeing that each node has a unique id. +------------------------------------------- +Generator Pass Structure: + Walk tree and build hashtable of symbol => boolean, where each reference's id matches a symbol, and the boolean is true if the type of the reference matches the decoupled interface. + +Consumer Pass Structure: + Walk tree and for any ':=', check if both references are in table. If so, insert a random number of buffers + +Points: + + Very simple to implement. + - If generator operates on high firrtl and consumer operates on low firrtl, bundle-expansion breaks the consumer pass. Whose fault is it?? + - Can't pass annotations from front-end to back-end in the tree, but in auxilliary data structure, which can become out of date. + +TLDR: Onus is on generator pass to make it robust. Middle passes can screw things up. Easiest. + +-------- Option 2: Typed Annotations --------- +FIRRTL has (order of) 10 types of annotations with known propagation properties; each pass must state which types of annotations are preserved, which are generated, and which are broken. +---------------------------------------------- +Generator Pass Structure: + Walk tree and annotate all nodes that match the decoupled interface with an annotation type that propagates through bundle expansion + +Consumer Pass Structure: + Walk tree and for an ':=', check if both references contain generated annotation. If so, insert a random number of buffers. + +Points: + + Clear assignment of blame - notion of support for annotations can keep passes/people responsible + - Requires thinking critically about all types of annotations that will be needed. Adds additional work to every pass. + - Pass complexity is associated with number of annotation types, not actual pass algorithm + +TLDR: Onus is shared between all passes. May limit types of annotations. Strong assignment of blame. + +-------- Option 3: History Trees ---------- +FIRRTL records all graph transformations (think git), where nodes have pointers to deleted/replaced nodes. A pass can walk the history graph to understand how previous passes mutated the graph (and its annotations). +------------------------------------------- +Generator Pass Structure: + Walk tree and annotate all nodes that match the decoupled interface. + +Consumer Pass Structure: + Walk tree and for an ':=', look at both node's history to find any ancestor node which was annotated. If so, insert random number of buffers. + +Points: + + Intermediate passes can be oblivious to all annotations. + - Hard to write consumer pass correctly, because arbitrary passes could really mess with the graph. Need significant FIRRTL support for maintaining history table, and all passes must correctly use API to ensure history is indeed correct. Hard to assign blame. + - If ever restructure upstream passes, could very easily break downstream passes because can depend on history as well as the tree + +TLDR: Onus is on consumer pass. Requires significant support from FIRRTL. + +--------- Option 4: Annotation Propogation Passes ---------- +Each FIRRTL pass constructs a table mapping unique id nodes from the old circuit to a list of unique id nodes in the new circuit. The annotation writer writes a pass that uses this table, the old circuit, and the new circuit to create a new circuit with the correct annotations. +------------------------------------------------------------ +Generator Pass Structure: + Walk tree and annotate all nodes that match the decoupled interface +Propagation Pass Structure: + Per row in the annotation table, add the annotation from the old circuit's id to each node in the new circuit that match the list of nodes. +Consumer Pass Structure: + Walk tree and for each ':=', look at both node's annotations and, if contains correct annotation, insert random number of buffers. +Points: + + Passes remain simple - only need to create table + + Simple passes makes writing the annotation propogation pass easier + - Up to annotation writer to validate whether a pass's constructed annotation table is correct + + + + + +Debug info +Tagged Decoupled +Layout ideas +Daisy chains +Simulation annotations +Probability distribution of values +After inlining, what module things came from + + +Inline Module +ensure_combinational Module +throw/catch exceptions (more fanciful); on wire declaration + diff --git a/notes/memory.txt b/notes/memory.txt new file mode 100644 index 00000000..22fb95dc --- /dev/null +++ b/notes/memory.txt @@ -0,0 +1,40 @@ +Whats resonable to express, how this relates to hardware + +Catch-all? Can always use black boxes + +Read/write ports? explicitly call it out in front end, and have a r/w accessor + Can infer from enables that they are mutually exclusive in some cases, in general need SAT solver + Writer often wants a r/w port to always be generated + r/w ports are always synchronous because writes always synchronous + Example of read/write to same address, can handle differently in BRAM's on FPGA, but is undefined for SRAMs. (Specifically for Synchronous). + In this case, it is backend speciifc, so should not be in chisel code. + +Don't have both synchronous and asynchronous reads on the same memory +Declaring the memory itself to have delay? - have node for seq, and node for combinational. Could have >1 delay, but not often used. Boolean for now (0 or 1) + +Absorbing registers should stop - register the address input, and chisel is allowed to retime the register into the address + +Not firrtl's job to autotune - that is the library writer (ASIC backend? FIRRTL library?) + e.g. FPGA backend is an executable that iterates and does DSE + +Masks? + Front-end generates mem's of type bundles or vec for enable granularity. + Lowering does not expand these. + Backends treat these differently. + How do we do this? Try not expanding mems, but expanding accessors. + e.g. + +mem m : { tag : UInt<10> data : UInt<128> } +accessor r = m[i] +accessor w = m[i] + +==> + +mem m : { tag : UInt<10> data : UInt<128> } +accessor r#tag = m.tag[i] +accessor r#data = m.data[i] +accessor w#tag = m.tag[i] +accessor w#data = m.data[i] + + +Eliminate flips from bundles in mems, must error. diff --git a/spec/spec.pdf b/spec/spec.pdf Binary files differnew file mode 100644 index 00000000..f8a00185 --- /dev/null +++ b/spec/spec.pdf diff --git a/spec/spec.tex b/spec/spec.tex index 0eb6e627..a246b663 100644 --- a/spec/spec.tex +++ b/spec/spec.tex @@ -38,6 +38,8 @@ &\vert &\pds{type}[\ints] &\text{Vector}\\ \pd{field} &= &\pd{gender} \id \kw{:} \pd{type} &\text{Bundle Field}\\ \pd{gender} &= &\kws{female} \vert \kws{male} &\text{Gender}\\ +\pd{vptype} &= &\kws{read} \vert \kws{write} \vert \kws{rdwr} &\text{Known Vector Port-Type}\\ + &\vert &\kw{?} &\text{Unknown Vector Port-Type}\\ \pd{width} &= &\ints &\text{Known Integer Width}\\ &\vert &\kw{?} &\text{Unknown Width}\\ \pd{stmt} &= &\info \kw{wire} \id \kw{:} \pd{type} &\text{Wire Declaration}\\ @@ -45,7 +47,7 @@ &\vert &\info \kw{mem} \id \kw{:} \pd{type} &\text{Memory Declaration}\\ &\vert &\info \kw{inst} \id \kw{of} \id &\text{Instance Declaration}\\ &\vert &\info \kw{node} \id = \pd{exp} &\text{Node Declaration}\\ - &\vert &\info \kw{accessor} \id = \pds{exp}[\pds{exp}] &\text{Accessor Declaration}\\ + &\vert &\info \pd{vptype} \kw{accessor} \id = \pds{exp}[\pds{exp}] &\text{Accessor Declaration}\\ &\vert &\info \pd{exp} \kw{:=} \pd{exp} &\text{Connect}\\ &\vert &\info \kw{when} \pd{exp} \kw{:} \pd{stmt} \kw{else :} \pd{stmt} &\text{Conditional}\\ &\vert &\info (\pd{stmt*}) &\text{Statement Group}\\ @@ -55,9 +57,10 @@ &\vert &\info \id &\text{Reference}\\ &\vert &\info \pds{exp}.\id &\text{Subfield}\\ &\vert &\info \pds{exp}.\ints &\text{Subindex}\\ - &\vert &\info \kws{Register}(\pds{exp}, \pds{exp}) &\text{Structural Register}\\ - &\vert &\info \kws{WritePort}(\id, \pds{exp}, \pds{exp}) &\text{Structural Write Port}\\ - &\vert &\info \kws{ReadPort}(\id, \pds{exp}, \pds{exp}) &\text{Structural Read Port}\\ + &\vert &\info \kws{Register}(\pds{exp}, \pds{exp}) &\text{Register}\\ + &\vert &\info \kws{WritePort}(\id, \pds{exp}, \pds{exp}) &\text{Write Port}\\ + &\vert &\info \kws{ReadPort}(\id, \pds{exp}, \pds{exp}) &\text{Read Port}\\ + &\vert &\info \kws{ReadWritePort}(\id, \pds{exp}, \pds{exp}) &\text{ReadWrite Port}\\ \end{array} \] \[ diff --git a/src/main/stanza/firrtl-test-main.stanza b/src/main/stanza/firrtl-test-main.stanza index e9cff931..f7d84600 100644 --- a/src/main/stanza/firrtl-test-main.stanza +++ b/src/main/stanza/firrtl-test-main.stanza @@ -22,6 +22,7 @@ defn set-printvars! (p:List<Char>) : if contains(p,'t') : PRINT-TYPES = true if contains(p,'k') : PRINT-KINDS = true if contains(p,'w') : PRINT-WIDTHS = true + if contains(p,'T') : PRINT-TWIDTHS = true if contains(p,'g') : PRINT-GENDERS = true if contains(p,'c') : PRINT-CIRCUITS = true diff --git a/src/main/stanza/ir-utils.stanza b/src/main/stanza/ir-utils.stanza index 0fe5ef5b..5e03ab54 100644 --- a/src/main/stanza/ir-utils.stanza +++ b/src/main/stanza/ir-utils.stanza @@ -254,89 +254,123 @@ defmethod map (f: Stmt -> Stmt, c:Stmt) -> Stmt : (c:Begin) : Begin(map(f, body(c))) (c) : c -;================= HELPER FUNCTIONS USING MAP =================== -public defmulti do (f:Expression -> ?, e:Expression) -> False -defmethod do (f:Expression -> ?, e:Expression) -> False : - for x in e map : - f(x) - x - false - -public defmulti do (f:Expression -> ?, s:Stmt) -> False -defmethod do (f:Expression -> ?, s:Stmt) -> False : - defn f* (x:Expression) : - f(x) - x - map(f*,s) - false - -public defmulti do (f:Stmt -> ?, s:Stmt) -> False -defmethod do (f:Stmt -> ?, s:Stmt) -> False : - defn f* (x:Stmt) : - f(x) - x - map(f*,s) - false - -public defmulti dor (f:Expression -> ?, e:Expression) -> False -defmethod dor (f:Expression -> ?, e:Expression) -> False : - f(e) - for x in e map : - dor(f,x) - x - false +public defmulti map<?T> (f: Width -> Width, c:?T&Expression) -> T +defmethod map (f: Width -> Width, c:Expression) -> Expression : + match(c) : + (c:UIntValue) : UIntValue(value(c),f(width(c))) + (c:SIntValue) : SIntValue(value(c),f(width(c))) + (c) : c -public defmulti dor (f:Expression -> ?, s:Stmt) -> False -defmethod dor (f:Expression -> ?, s:Stmt) -> False : - defn f* (x:Expression) : - dor(f,x) - x - map(f*,s) - false +public defmulti map<?T> (f: Width -> Width, c:?T&Type) -> T +defmethod map (f: Width -> Width, c:Type) -> Type : + match(c) : + (c:UIntType) : UIntType(f(width(c))) + (c:SIntType) : SIntType(f(width(c))) + (c) : c -public defmulti dor (f:Stmt -> ?, s:Stmt) -> False -defmethod dor (f:Stmt -> ?, s:Stmt) -> False : - f(s) - defn f* (x:Stmt) : - dor(f,x) - x - map(f*,s) - false +public defmulti map<?T> (f: Type -> Type, c:?T&Expression) -> T +defmethod map (f: Type -> Type, c:Expression) -> Expression : + match(c) : + (c:Ref) : Ref(name(c),f(type(c))) + (c:Subfield) : Subfield(exp(c),name(c),f(type(c))) + (c:Index) : Index(exp(c),value(c),f(type(c))) + (c:DoPrim) : DoPrim(op(c),args(c),consts(c),f(type(c))) + (c:ReadPort) : ReadPort(mem(c),index(c),f(type(c)),enable(c)) + (c:WritePort) : WritePort(mem(c),index(c),f(type(c)),enable(c)) + (c:Register) : Register(f(type(c)),value(c),enable(c)) + (c) : c -public defmulti sub-exps (s:Expression|Stmt) -> List<Expression> -defmethod sub-exps (e:Expression) -> List<Expression> : - val l = Vector<Expression>() - defn f (x:Expression) : add(l,x) - do(f,e) - to-list(l) -defmethod sub-exps (e:Stmt) -> List<Expression> : - val l = Vector<Expression>() - defn f (x:Expression) : add(l,x) - do(f,e) - to-list(l) +public defmulti map<?T> (f: Type -> Type, c:?T&Stmt) -> T +defmethod map (f: Type -> Type, c:Stmt) -> Stmt : + match(c) : + (c:DefWire) : DefWire(name(c),f(type(c))) + (c:DefRegister) : DefRegister(name(c),f(type(c))) + (c:DefMemory) : DefRegister(name(c),f(type(c))) + (c) : c -public defmulti sub-stmts (s:Stmt) -> List<Stmt> -defmethod sub-stmts (s:Stmt) : - val l = Vector<Stmt>() - defn f (x:Stmt) : add(l,x) - do(f,s) - to-list(l) +;================= HELPER FUNCTIONS USING MAP =================== +; These don't work properly.. +;public defmulti do (f:Expression -> ?, e:Expression) -> False +;defmethod do (f:Expression -> ?, e:Expression) -> False : +; for x in e map : +; f(x) +; x +; false +; +;public defmulti do (f:Expression -> ?, s:Stmt) -> False +;defmethod do (f:Expression -> ?, s:Stmt) -> False : +; defn f* (x:Expression) : +; f(x) +; x +; map(f*,s) +; false +; +;public defmulti do (f:Stmt -> ?, s:Stmt) -> False +;defmethod do (f:Stmt -> ?, s:Stmt) -> False : +; defn f* (x:Stmt) : +; f(x) +; x +; map(f*,s) +; false +; +;public defmulti dor (f:Expression -> ?, e:Expression) -> False +;defmethod dor (f:Expression -> ?, e:Expression) -> False : +; f(e) +; for x in e map : +; dor(f,x) +; x +; false +; +;public defmulti dor (f:Expression -> ?, s:Stmt) -> False +;defmethod dor (f:Expression -> ?, s:Stmt) -> False : +; defn f* (x:Expression) : +; dor(f,x) +; x +; map(f*,s) +; false +; +;public defmulti dor (f:Stmt -> ?, s:Stmt) -> False +;defmethod dor (f:Stmt -> ?, s:Stmt) -> False : +; f(s) +; defn f* (x:Stmt) : +; dor(f,x) +; x +; map(f*,s) +; false +; +;public defmulti sub-exps (s:Expression|Stmt) -> List<Expression> +;defmethod sub-exps (e:Expression) -> List<Expression> : +; val l = Vector<Expression>() +; defn f (x:Expression) : add(l,x) +; do(f,e) +; to-list(l) +;defmethod sub-exps (e:Stmt) -> List<Expression> : +; val l = Vector<Expression>() +; defn f (x:Expression) : add(l,x) +; do(f,e) +; to-list(l) +; +;public defmulti sub-stmts (s:Stmt) -> List<Stmt> +;defmethod sub-stmts (s:Stmt) : +; val l = Vector<Stmt>() +; defn f (x:Stmt) : add(l,x) +; do(f,s) +; to-list(l) ;=================== ADAM OPS =============================== public defn split (s:String,c:Char) -> List<String> : - val empty = "" - defn next-word (s:String,i:Int) -> String|False : - if i == length(s) : false - else: - if (s[i] == c): substring(s,0,i) - else: next-word(s,i + 1) - - val next-str = next-word(s,0) - if next-str == false : list() - else if next-str == empty : split(substring(s,1,length(s)),c) + if not contains(to-list(s),c) : list(s) else : - val str = next-str as String - List(str,split(substring(s,length(str)+1,length(s)),c)) + val index = label<Int> ret : + var i = 0 + for c* in to-list(s) do : + if c* == c : ret(i) + else : + i = i + 1 + ret(0) + val h = substring(s,0,index) + val t = substring(s,index + 1,length(s)) + List(h,split(t,c)) public defn contains (l:List<Char>, c:Char) : label<True|False> myret : diff --git a/src/main/stanza/passes.stanza b/src/main/stanza/passes.stanza index 2c0ad0ec..82187b7e 100644 --- a/src/main/stanza/passes.stanza +++ b/src/main/stanza/passes.stanza @@ -15,16 +15,18 @@ defn PassException (msg:String) : ;=============== WORKING IR ================================ definterface Kind +defstruct WireKind <: Kind defstruct RegKind <: Kind -defstruct AccessorKind <: Kind +defstruct InstanceKind <: Kind +defstruct ReadAccessorKind <: Kind +defstruct WriteAccessorKind <: Kind defstruct PortKind <: Kind -defstruct MemKind <: Kind defstruct NodeKind <: Kind ; All elems except structural memory, wires + +defstruct MemKind <: Kind defstruct ModuleKind <: Kind -defstruct InstanceKind <: Kind defstruct StructuralMemKind <: Kind ; Separate kind because need special treatment -defstruct ReadAccessorKind <: Kind -defstruct WriteAccessorKind <: Kind +defstruct AccessorKind <: Kind public definterface Gender public val MALE = new Gender @@ -150,12 +152,14 @@ defmethod type (exp:SIntValue) -> Type : SIntType(width(exp)) public var PRINT-TYPES : True|False = false public var PRINT-KINDS : True|False = false public var PRINT-WIDTHS : True|False = false +public var PRINT-TWIDTHS : True|False = false public var PRINT-GENDERS : True|False = false public var PRINT-CIRCUITS : True|False = false ;=== Printers === defmethod print (o:OutputStream, k:Kind) : print{o, _} $ match(k) : + (k:WireKind) : "wire" (k:RegKind) : "reg" (k:AccessorKind) : "accessor" (k:PortKind) : "port" @@ -171,7 +175,7 @@ defn hasGender (e:Expression|Stmt|Type|Port|Field) : e typeof WRef|WSubfield|WIndex|WDefAccessor|WRegInit defn hasWidth (e:Expression|Stmt|Type|Port|Field) : - e typeof UIntType|SIntType|UIntValue|SIntValue|WRegInit + e typeof UIntType|SIntType|UIntValue|SIntValue defn hasType (e:Expression|Stmt|Type|Port|Field) : e typeof Ref|Subfield|Index|DoPrim|WritePort|ReadPort|WRef|WSubfield @@ -185,6 +189,7 @@ defn any-debug? (e:Expression|Stmt|Type|Port|Field) : (hasGender(e) and PRINT-GENDERS) or (hasType(e) and PRINT-TYPES) or (hasWidth(e) and PRINT-WIDTHS) or + (hasType(e) and PRINT-WIDTHS) or (hasKind(e) and PRINT-KINDS) defmethod print-debug (o:OutputStream, e:Expression|Stmt|Type|Port|Field) : @@ -197,6 +202,7 @@ defmethod print-debug (o:OutputStream, e:Expression|Stmt|Type|Port|Field) : if any-debug?(e) : print(o,"@") if PRINT-KINDS and hasKind(e) : print-all(o,["<k:" kind(e as ?) ">"]) if PRINT-TYPES and hasType(e) : print-all(o,["<t:" wipe-width(type(e as ?)) ">"]) + if PRINT-TWIDTHS and hasType(e): print-all(o,["<t:" type(e as ?) ">"]) if PRINT-WIDTHS and hasWidth(e): print-all(o,["<w:" width(e as ?) ">"]) if PRINT-GENDERS and hasGender(e): print-all(o,["<g:" gender(e as ?) ">"]) @@ -241,6 +247,15 @@ defmethod map (f: Expression -> Expression, c:ConnectToIndexed) : defmethod map (f: Expression -> Expression, c:ConnectFromIndexed) : ConnectFromIndexed(f(index(c)), f(loc(c)), map(f, exps(c))) +defmethod map (f: Type -> Type, e: WRef) : + WRef(name(e), f(type(e)), kind(e), gender(e)) +defmethod map (f: Type -> Type, e: WRegInit) : + WRegInit(reg(e), name(e), f(type(e)), gender(e)) +defmethod map (f: Type -> Type, e: WSubfield) : + WSubfield(exp(e), name(e), f(type(e)), gender(e)) +defmethod map (f: Type -> Type, e: WIndex) : + WIndex(exp(e), value(e), f(type(e)), gender(e)) + ;================= Bring to Working IR ======================== ; Returns a new Circuit with Refs, Subfields, Indexes and DefAccessors ; replaced with IR-internal nodes that contain additional @@ -768,7 +783,7 @@ defn lower (body:Stmt, table:HashTable<Symbol,List<KeyValue<Expression,Flip>>>) (s:DefNode) : val s* = Begin $ list( DefWire(name(s),type(value(s))), - Connect(WRef(name(s),type(value(s)),NodeKind(),UNKNOWN-GENDER),value(s))) + Connect(WRef(name(s),type(value(s)),NodeKind(),FEMALE),value(s))) lower-stmt(s*) (s:Connect) : Begin{_} $ for (l in expand-expr(loc(s)), r in expand-expr(exp(s))) map : @@ -836,7 +851,7 @@ defn lower (body:Stmt, table:HashTable<Symbol,List<KeyValue<Expression,Flip>>>) defn get-entries (n:Symbol,t:Type) -> List<KeyValue<WRef,Flip>> : defn uniquify (w:WRef) -> WRef : - val name* = symbol-join([n "#" name(w)]) + val name* = symbol-join([n "$" name(w)]) WRef(name*,type(w),kind(w),gender(w)) match(t) : (t:BundleType) : @@ -953,7 +968,7 @@ defn expand-connect-indexed (c: Circuit) -> Circuit : ; times. defn initialize-registers (c:Circuit) : - defn to-wire-name (y:Symbol) : to-symbol("~#init" % [y]) + defn to-wire-name (y:Symbol) : to-symbol("~$init" % [y]) defn add-when (s:Stmt,h:HashTable<Symbol,Type>) -> Stmt : var inits = List<Stmt>() for kv in h do : @@ -1048,6 +1063,7 @@ defmethod equal? (e1:Expression,e2:Expression) -> True|False : if value(e1) == value(e2) : match(width(e1), width(e2)) : (w1:IntWidth,w2:IntWidth) : width(w1) == width(w2) + (w1,w2) : false else : false (e1:SIntValue,e2:SIntValue) : if value(e1) == value(e2) : @@ -1055,6 +1071,7 @@ defmethod equal? (e1:Expression,e2:Expression) -> True|False : (w1:IntWidth,w2:IntWidth) : width(w1) == width(w2) else : false (e1:WRef,e2:WRef) : name(e1) == name(e2) + ;(e1:DoPrim,e2:DoPrim) : TODO (e1:WRegInit,e2:WRegInit) : reg(e1) == reg(e2) and name(e1) == name(e2) (e1:WSubfield,e2:WSubfield) : name(e1) == name(e2) (e1,e2) : false @@ -1080,7 +1097,10 @@ defn NOT (e1:Expression) -> Expression : defn children (e:Expression) -> List<Expression> : val es = Vector<Expression>() - do(add{es,_},e) + defn f (e:Expression) : + add(es,e) + e + map(f,e) to-list(es) @@ -1137,97 +1157,112 @@ defn optimize (sv:SymbolicValue) -> SymbolicValue : (c:SVExp,a:SVExp) : if exp(c) == one and exp(a) == zero : SVExp(pred(sv)) else if exp(c) == zero and exp(a) == one : SVExp(NOT(pred(sv))) + else if exp(c) == exp(a) : c else : sv (c,a) : sv (sv) : sv ; ========== Expand When Utilz ========== -defstruct SSV : - stmt : Stmt - sv : SymbolicValue - -defmethod print (o:OutputStream, ssv:SSV) : - print-all(o, ["[ {" stmt(ssv) "} :: {" sv(ssv) "} ]"]) -defn new-table () -> HashTable<Symbol,SSV> : HashTable<Symbol,SSV>(symbol-hash) +defn deepcopy (t:HashTable<Symbol,SymbolicValue>) -> HashTable<Symbol,SymbolicValue> : + t0 where : + val t0 = HashTable<Symbol,SymbolicValue>(symbol-hash) + for x in t do : + t0[key(x)] = value(x) +defn get-unique-keys (ts:List<HashTable<Symbol,SymbolicValue>>) -> Vector<Symbol> : + t0 where : + val t0 = Vector<Symbol>() + for v in ts do : + for t in v do : + val duplicate? = for x in t0 any? : x == key(t) + if not duplicate? : add(t0,key(t)) +defn has-nul? (sv:SymbolicValue) -> True|False : + var has? = false + if sv typeof SVNul : has? = true + for x in sv dor : + if x typeof SVNul : has? = true + has? +defn remove-nul (sv:SymbolicValue) -> SymbolicValue : + match(map(remove-nul,sv)) : + (sv:SVMux) : + match(conseq(sv),alt(sv)) : + (c,a:SVNul) : c + (c:SVNul,a) : a + (c,a) : sv + (sv) : sv +defn to-exp (sv:SymbolicValue) -> Expression : + match(remove-nul(sv)) : + (sv:SVMux) : + DoPrim(MUX-UU-OP, + list(pred(sv),to-exp(conseq(sv)),to-exp(alt(sv))), + list(), + UIntType(IntWidth(1))) + (sv:SVExp) : exp(sv) + (sv) : error("Shouldn't be here") +defn reduce-or (l:List<True|False>) -> True|False : + if length(l) == 0 : false + else : head(l) or reduce-or(tail(l)) +defn reduce-or (l:List<Expression>) -> Expression : + if length(l) == 0 : zero + else : OR(head(l) reduce-or(tail(l))) ; ========= Expand When Pass =========== +; TODO: replace stmt with wr (WRefs). The KIND of wref will help figure out what to emit as far as +; declarations, especially with not declaring anything for ports. We need WRefs, and not just Kinds, +; because we need the name of the symbolic expression. I think? Or maybe we can use the key? -defn expand-whens-stmt (table:HashTable<Symbol,SSV>,enables:HashTable<Symbol,SymbolicValue>) -> Stmt : - defn has-nul? (sv:SymbolicValue) -> True|False : - var has? = false - if sv typeof SVNul : has? = true - for x in sv dor : - if x typeof SVNul : has? = true - has? - defn remove-nul (sv:SymbolicValue) -> SymbolicValue : - match(map(remove-nul,sv)) : - (sv:SVMux) : - match(conseq(sv),alt(sv)) : - (c,a:SVNul) : c - (c:SVNul,a) : a - (c,a) : sv - (sv) : sv - defn to-exp (sv:SymbolicValue) -> Expression : - match(remove-nul(sv)) : - (sv:SVMux) : - DoPrim(MUX-UU-OP, - list(pred(sv),to-exp(conseq(sv)),to-exp(alt(sv))), - list(), - UIntType(IntWidth(1))) - (sv:SVExp) : exp(sv) - (sv) : error("Shouldn't be here") +; 1) Build Table, Build Declaration List + +defn expand-whens (assign:HashTable<Symbol,SymbolicValue>, + kinds:HashTable<Symbol,Kind>, + stmts:HashTable<Symbol,Stmt>, + decs:Vector<Stmt>, + enables:HashTable<Symbol,SymbolicValue>) -> Stmt : - val declarations = Vector<Stmt>() - val connections = Vector<Stmt>() - for x in table do : - val [sym ssv] = [key(x) value(x)] - match(stmt(ssv)) : - (s:WDefAccessor) : - val ty = type(type(source(s)) as VectorType) - add(declarations,DefWire(sym,ty)) - switch {_ == gender(s)} : - FEMALE : - add{connections,_} $ - Connect{_,WRef(sym,ty,NodeKind(),MALE)} $ - WritePort(source(s),index(s),ty,to-exp(enables[sym])) - val sv* = remove-nul(sv(ssv)) - if sv* == SVNul : println("Uninitialized: ~" % [to-string(s)]) - else : - add{connections,_} $ - Connect{_,to-exp(sv*)} $ - WRef(name(stmt(ssv) as ?), UnknownType(), NodeKind(), FEMALE) - MALE : - add{connections,_} $ - Connect{WRef(sym,ty,NodeKind(),FEMALE),_} $ - ReadPort(source(s),index(s),ty,to-exp(enables[sym])) - (s:DefRegister) : - val sv* = remove-nul(sv(ssv)) - val exp* = - if sv* typeof SVNul : WRef(sym,type(s),NodeKind(),MALE) - else : to-exp(sv*) - add(declarations,s) - add{connections,_} $ - Connect{WRef(sym,type(s),NodeKind(),FEMALE),_} $ - Register(type(s),exp*,to-exp(enables[sym])) - (s) : - add(declarations,stmt(value(x))) - if has-nul?(sv(ssv)) : println("Uninitialized: ~" % [to-string(s)]);TODO actually collect error - else : - add{connections,_} $ - Connect{_,to-exp(sv(ssv))} $ - WRef(name(stmt(ssv) as ?), UnknownType(), NodeKind(), FEMALE) - - Begin(append(to-list(declarations),to-list(connections))) - -defn get-enables (table:HashTable<Symbol,SSV>) -> HashTable<Symbol,SymbolicValue> : - defn reduce-or (l:List<True|False>) -> True|False : - if length(l) == 0 : false - else : head(l) or reduce-or(tail(l)) - defn reduce-or (l:List<Expression>) -> Expression : - if length(l) == 0 : zero - else : OR(head(l) reduce-or(tail(l))) - + for x in assign do : + val [n sv] = [key(x) value(x)] + match(kinds[n]) : + (k:WriteAccessorKind) : + ;First create WritePort and assign from accessor-turned-wire + val s = stmts[n] as WDefAccessor + val t = type(type(source(s)) as VectorType) + val ref = WRef(n,t,k,MALE) + val wp = WritePort(source(s),index(s),t,to-exp(enables[n])) + add(decs,Connect(wp,ref)) + ;If initialized, assign input to accessor-turned-wire + val sv = remove-nul(assign[n]) + if sv == SVNul : println("Uninitialized: ~" % [to-string(n)]) ;TODO actually collect error + else : add(decs,Connect(ref,to-exp(sv))) + (k:ReadAccessorKind) : + val s = stmts[n] as WDefAccessor + val t = type(type(source(s)) as VectorType) + val ref = WRef(n,t,k,FEMALE) + val rp = ReadPort(source(s),index(s),t,to-exp(enables[n])) + add(decs,Connect(ref,rp)) + (k:RegKind) : + val s = stmts[n] as DefRegister + val ref = WRef(n,type(s),k,FEMALE) + val sv = remove-nul(assign[n]) + val reg = + if sv typeof SVNul : Register(type(s),UIntValue(0,width(type(s) as ?)),zero) + else : Register(type(s),to-exp(sv),to-exp(enables[n])) + add(decs,Connect(ref,reg)) + (k:InstanceKind) : + val s = stmts[n] as DefInstance + val x = split(to-string(n),'.') + val f = to-symbol(split(to-string(n),'.')[1]) + val ref = WSubfield(module(s),f,bundle-field-type(type(module(s)),f),FEMALE) + if has-nul?(assign[n]) : println("Uninitialized: ~" % [to-string(n)]);TODO actually collect error + else : add(decs,Connect(ref,to-exp(assign[n]))) + (k) : + val s = stmts[n] as DefWire + val ref = WRef(n,type(s),k,FEMALE) + if has-nul?(assign[n]) : println("Uninitialized: ~" % [to-string(n)]);TODO actually collect error + else : add(decs,Connect(ref,to-exp(assign[n]))) + Begin(to-list(decs)) + +defn get-enables (assign:HashTable<Symbol,SymbolicValue>, + kinds:HashTable<Symbol,Kind>) -> HashTable<Symbol,SymbolicValue> : defn get-read-enable (sym:Symbol,sv:SymbolicValue) -> Expression : defn active (e:Expression) -> True|False : match(e) : @@ -1253,97 +1288,108 @@ defn get-enables (table:HashTable<Symbol,SSV>) -> HashTable<Symbol,SymbolicValue (sv) : sv val enables = HashTable<Symbol,SymbolicValue>(symbol-hash) - for x in table do : + for x in assign do : val sym = key(x) - match(stmt(value(x))) : - (s:WDefAccessor) : switch {_ == gender(s)} : - FEMALE : enables[sym] = get-write-enable(sv(value(x))) - MALE : enables[sym] = SVExp{_} $ reduce-or{_} $ to-list{_} $ - for y in table stream : - get-read-enable(sym,sv(value(y))) - (s:DefRegister) : enables[sym] = get-write-enable(sv(value(x))) - (s) : s + match(kinds[sym]) : + (k:ReadAccessorKind) : + enables[sym] = SVExp{_} $ reduce-or{_} $ to-list{_} $ + for y in assign stream : + get-read-enable(sym,value(y)) + (k:WriteAccessorKind) : enables[sym] = get-write-enable(value(x)) + (k:RegKind) : enables[sym] = get-write-enable(value(x)) + (k) : k enables - -defn build-table (s:Stmt, table:HashTable<Symbol,SSV>) -> False : - println("=====================") + +defn build-tables (s:Stmt, + assign:HashTable<Symbol,SymbolicValue>, + kinds:HashTable<Symbol,Kind>, + decs:Vector<Stmt>, + stmts:HashTable<Symbol,Stmt>) -> False : match(s) : - (s:DefWire) : table[name(s)] = SSV(s SVNul()) - (s:DefNode) : table[name(s)] = SSV(s SVNul()) - (s:DefRegister) : table[name(s)] = SSV(s SVNul()) - (s:WDefAccessor) : table[name(s)] = SSV(s SVNul()) + (s:DefWire) : + add(decs,s) + kinds[name(s)] = WireKind() + assign[name(s)] = SVNul() + stmts[name(s)] = s + (s:DefNode) : add(decs,s) + (s:DefRegister) : + add(decs,DefWire(name(s),type(s))) + kinds[name(s)] = RegKind() + assign[name(s)] = SVNul() + stmts[name(s)] = s + (s:WDefAccessor) : + add(decs,DefWire(name(s),type(type(source(s)) as VectorType))) + assign[name(s)] = SVNul() + kinds[name(s)] = switch {_ == gender(s)} : + MALE : ReadAccessorKind() + FEMALE : WriteAccessorKind() + stmts[name(s)] = s (s:DefInstance) : + add(decs,s) for f in fields(type(module(s)) as BundleType) do : - table[to-symbol("~.~" % [name(s),name(f)])] = SSV(s SVNul()) - (s:DefMemory) : table[name(s)] = SSV(s SVNul()) + val n = to-symbol("~.~" % [name(s),name(f)]) ; only on inputs + ;println-all(["In DefInst adding: " n]) + kinds[n] = InstanceKind() + assign[n] = SVNul() + stmts[n] = s + (s:DefMemory) : add(decs,s) (s:Conditionally) : - defn deepcopy (t:HashTable<Symbol,SSV>) -> HashTable<Symbol,SSV> : - t0 where : - val t0 = new-table() - for x in t do : - t0[key(x)] = SSV(stmt(value(x)),sv(value(x))) - defn get (t:HashTable<Symbol,SSV>,i:Symbol) -> SSV|False : - val kv = for x in t find : i == key(x) - match(kv) : - (e:False) : false - (e:KeyValue<Symbol,SSV>) : value(e) - defn get-unique-keys (ts:List<HashTable<Symbol,SSV>>) -> Vector<Symbol> : - t0 where : - val t0 = Vector<Symbol>() - for v in ts do : - for t in v do : - val duplicate? = for x in t0 any? : x == key(t) - if not duplicate? : add(t0,key(t)) - val table-c = deepcopy(table) - val table-a = deepcopy(table) - build-table(conseq(s),table-c) - build-table(alt(s),table-a) - for i in get-unique-keys(list(table-c,table-a)) do : - table[i] = match(get(table-c,i),get(table-a,i)) : - (c:SSV,a:SSV) : SSV(stmt(c),SVMux(pred(s),sv(c),sv(a))) - (c:SSV,a:False) : - if stmt(c) typeof DefWire|DefInstance : - SSV(stmt(c),sv(c)) - else : SSV(stmt(c),SVMux(pred(s),sv(c),SVNul())) - (c:False,a:SSV) : - if stmt(a) typeof DefWire|DefInstance : - SSV(stmt(a),sv(a)) - else : SSV(stmt(a),SVMux(pred(s),SVNul(),sv(a))) + val assign-c = deepcopy(assign) + val assign-a = deepcopy(assign) + build-tables(conseq(s),assign-c,kinds,decs,stmts) + build-tables(alt(s),assign-a,kinds,decs,stmts) + for i in get-unique-keys(list(assign-c,assign-a)) do : + assign[i] = match(get?(assign-c,i,false),get?(assign-a,i,false)) : ;TODO add to syntax highlighting + (c:SymbolicValue,a:SymbolicValue) : SVMux(pred(s),c,a) + (c:SymbolicValue,a:False) : + if kinds[i] typeof WireKind|InstanceKind|NodeKind : c + else : SVMux(pred(s),c,SVNul()) + (c:False,a:SymbolicValue) : + if kinds[i] typeof WireKind|InstanceKind|NodeKind : a + else : SVMux(pred(s),SVNul(),a) (c:False,a:False) : error("Shouldn't be here") - println("TABLE-C") - for x in table-c do : println(x) - println("TABLE-A") - for x in table-a do : println(x) - println("TABLE") - for x in table do : println(x) + ;println("TABLE-C") + ;for x in assign-c do : println(x) + ;println("TABLE-A") + ;for x in assign-a do : println(x) + ;println("TABLE") + ;for x in assign do : println(x) (s:Connect) : val key* = match(loc(s)) : (e:WRef) : name(e) - (e:WSubfield) : to-symbol("~.~" % [name(exp(e) as WRef),name(e)]) + (e:WSubfield) : symbol-join([name(exp(e) as ?) `. name(e)]) (e) : error("Shouldn't be here with ~" % [e]) - table[key*] = SSV(stmt(table[key*]) SVExp(exp(s))); TODO, need to check all references are declared before this point - (s:Begin) : for s* in body(s) do: build-table(s*,table) + assign[key*] = SVExp(exp(s)); TODO, need to check all references are declared before this point + (s:Begin) : for s* in body(s) do: build-tables(s*,assign,kinds,decs,stmts) (s) : false defn expand-whens (m:Module) -> Module : - val table = new-table() - build-table(body(m),table) - val table* = HashTable<Symbol,SSV>(symbol-hash) - for x in table do : table*[key(x)] = SSV(stmt(value(x)) optimize(sv(value(x)))) - val enables = get-enables(table*) - val enables* = HashTable<Symbol,SymbolicValue>(symbol-hash) - for x in enables do : enables*[key(x)] = optimize(value(x)) + val assign = HashTable<Symbol,SymbolicValue>(symbol-hash) + val decs = Vector<Stmt>() + val kinds = HashTable<Symbol,Kind>(symbol-hash) + val stmts = HashTable<Symbol,Stmt>(symbol-hash) + + for p in ports(m) do : + if direction(p) == OUTPUT : + assign[name(p)] = SVNul() + kinds[name(p)] = PortKind() + stmts[name(p)] = DefWire(name(p),type(p)) - println("Original Table") - for x in table do : println(x) - println("Optimized Table") - for x in table* do : println(x) - println("Enable Table") + build-tables(body(m),assign,kinds,decs,stmts) + for x in assign do : assign[key(x)] = optimize(value(x)) + val enables = get-enables(assign,kinds) + for x in enables do : enables[key(x)] = optimize(value(x)) + + println("Assigns") + for x in assign do : println(x) + println("Kinds") + for x in kinds do : println(x) + println("Decs") + for x in decs do : println(x) + println("Enables") for x in enables do : println(x) - println("Optimized Enable Table") - for x in enables* do : println(x) - Module(name(m),ports(m),expand-whens-stmt(table*,enables*)) + Module(name(m),ports(m),expand-whens(assign,kinds,stmts,decs,enables)) defn expand-whens (c:Circuit) -> Circuit : Circuit(modules*, main(c)) where : @@ -1352,248 +1398,100 @@ defn expand-whens (c:Circuit) -> Circuit : expand-whens(m) +;;================ INFER WIDTHS ============================= +; First, you replace all unknown widths with a unique width +; variable. +; Then, you collect all width constraints. +; Then, you solve width constraints. +; Finally, you replace all width variables with the solved +; widths. - -;;================ EXPAND WHENS ============================= -;definterface SymbolicValue -;defstruct ExpValue <: SymbolicValue : -; exp: Expression -;defstruct WhenValue <: SymbolicValue : -; pred: Expression -; conseq: SymbolicValue -; alt: SymbolicValue -;defstruct VoidValue <: SymbolicValue -; -;defmethod print (o:OutputStream, sv:SymbolicValue) : -; match(sv) : -; (sv:VoidValue) : print(o, "VOID") -; (sv:WhenValue) : print-all(o, ["(" pred(sv) "? " conseq(sv) " : " alt(sv) ")"]) -; (sv:ExpValue) : print(o, exp(sv)) -; -;defn key-eqv? (e1:Expression, e2:Expression) : -; match(e1, e2) : -; (e1:WRef, e2:WRef) : -; name(e1) == name(e2) -; (e1:WSubfield, e2:WSubfield) : -; name(e1) == name(e2) and -; key-eqv?(exp(e1), exp(e2)) -; (e1, e2) : -; false -; -;defn merge-env (pred: Expression, -; con-env: List<KeyValue<Expression,SymbolicValue>>, -; alt-env: List<KeyValue<Expression,SymbolicValue>>) : -; val merged = Vector<KeyValue<Expression, SymbolicValue>>() -; defn new-key? (k:Expression) : -; for entry in merged none? : -; key-eqv?(key(entry), k) -; -; defn sv (env:List<KeyValue<Expression,SymbolicValue>>, k:Expression) : -; for entry in env search : -; if key-eqv?(key(entry), k) : -; value(entry) -; -; for k in stream(key, concat(con-env, alt-env)) do : -; if new-key?(k) : -; match(sv(con-env, k), sv(alt-env, k)) : -; (a:SymbolicValue, b:SymbolicValue) : -; if a == b : -; add(merged, k => a) -; else : -; add(merged, k => WhenValue(pred, a, b)) -; (a:SymbolicValue, b:False) : -; add(merged, k => a) -; (a:False, b:SymbolicValue) : -; add(merged, k => b) -; (a:False, b:False) : -; false -; -; to-list(merged) -; -;defn simplify-env (env: List<KeyValue<Expression,SymbolicValue>>) : -; val merged = Vector<KeyValue<Expression, SymbolicValue>>() -; defn new-key? (k:Expression) : -; for entry in merged none? : -; key-eqv?(key(entry), k) -; for entry in env do : -; if new-key?(key(entry)) : -; add(merged, entry) -; to-list(merged) -; -;defn expand-whens (m:Module) : -; val commands = Vector<Stmt>() -; val elements = Vector<KeyValue<Symbol,Element>>() -; defn eval (c:Stmt, env:List<KeyValue<Expression,SymbolicValue>>) -> -; List<KeyValue<Expression,SymbolicValue>> : -; match(c) : -; (c:LetRec) : -; do(add{elements, _}, entries(c)) -; eval(body(c), env) -; (c:DefWire) : -; add(commands, c) -; val wire-ref = WRef(name(c), type(c), NodeKind(), INPUT) -; List(wire-ref => VoidValue(), env) -; (c:DefRegister) : -; add(commands, c) -; val reg-ref = WRef(name(c), type(c), RegKind(), INPUT) -; List(reg-ref => VoidValue(), env) -; (c:DefInstance) : -; add(commands, c) -; val entries = let : -; val module-type = type(module(c)) as BundleType -; val input-ports = to-list $ -; for p in ports(module-type) filter : -; gender(p) == INPUT -; val inst-ref = WRef(name(c), module-type, InstanceKind(), OUTPUT) -; for p in input-ports map : -; WSubfield(inst-ref, name(p), type(p), INPUT) => VoidValue() -; append(entries, env) -; (c:DefMemory) : -; add(commands, c) -; env -; (c:WDefAccessor) : -; add(commands, c) -; if dir(c) == INPUT : -; val access-ref = WRef(name(c), type(source(c)), AccessorKind(), dir(c)) -; List(access-ref => VoidValue(), env) -; else : -; env -; (c:Conditionally) : -; val con-env = eval(conseq(c), env) -; val alt-env = eval(alt(c), env) -; merge-env(pred(c), con-env, alt-env) -; (c:Begin) : -; var env:List<KeyValue<Expression,SymbolicValue>> = env -; for c in body(c) do : -; env = eval(c, env) -; env -; (c:Connect) : -; List(loc(c) => ExpValue(exp(c)), env) -; (c:EmptyStmt) : -; env -; -; defn convert-symbolic (key:Expression, sv:SymbolicValue) : -; match(sv) : -; (sv:VoidValue) : -; throw $ PassException $ string-join $ [ -; "No default value for " key "."] -; (sv:ExpValue) : -; exp(sv) -; (sv:WhenValue) : -; defn multiplex-exp (pred:Expression, conseq:Expression, alt:Expression) : -; DoPrim(MUX-OP, list(pred, conseq, alt), List(), type(conseq)) -; multiplex-exp(pred(sv), -; convert-symbolic(key, conseq(sv)) -; convert-symbolic(key, alt(sv))) -; -; ;Compute final environment -; val env0 = let : -; val output-ports = to-list $ -; for p in ports(m) filter : -; gender(p) == OUTPUT -; for p in output-ports map : -; val port-ref = WRef(name(p), type(p), PortKind(), INPUT) -; port-ref => VoidValue() -; val env* = simplify-env(eval(body(m), env0)) -; -; ;Make new body -; val body* = Begin(list(defs, LetRec(elems, connections))) where : -; val defs = Begin(to-list(commands)) -; val elems = to-list(elements) -; val connections = Begin $ -; for entry in env* map : -; val sv = convert-symbolic(key(entry), value(entry)) -; Connect(key(entry), sv) -; -; ;Final module -; Module(name(m), ports(m), body*) -; -;defn expand-whens (c:Circuit) : -; val modules* = map(expand-whens, modules(c)) -; Circuit(modules*, main(c)) +;defstruct VarWidth <: Width : +; name: Symbol ; +;defmethod print (o:OutputStream, w:VarWidth) : +; print(o,name(w)) ; -;;================ STRUCTURAL FORM ========================== +;;defn remove-var-widths (c:Circuit) -> Circuit : ; -;defn structural-form (m:Module) : -; val elements = Vector<(() -> KeyValue<Symbol,Element>)>() -; val connected = HashTable<Symbol, Expression>(symbol-hash) -; val write-accessors = HashTable<Symbol, List<WDefAccessor>>(symbol-hash) -; val read-accessors = HashTable<Symbol, WDefAccessor>(symbol-hash) -; val inst-ports = HashTable<Symbol, List<KeyValue<Symbol, Expression>>>(symbol-hash) -; val port-connects = Vector<Connect>() +;;defn solve-constraints (l:List<WCon>) -> HashTable<Symbol,Int> : +; +;defn gen-constraints (m:Module) -> List<WCon> : +; val v = Vector<WCon>() +; val h = HashTable<Symbol,Width>(symbol-hash) ; -; defn scan (c:Stmt) : -; match(c) : -; (c:Connect) : -; match(loc(c)) : -; (loc:WRef) : -; match(kind(loc)) : -; (k:PortKind) : add(port-connects, c) -; (k) : connected[name(loc)] = exp(c) -; (loc:WSubfield) : -; val inst = exp(loc) as WRef -; val entry = name(loc) => exp(c) -; inst-ports[name(inst)] = List(entry, get?(inst-ports, name(inst), List())) -; (c:LetRec) : -; for e in entries(c) do : -; add(elements, {e}) -; scan(body(c)) -; (c:DefWire) : -; add{elements, _} $ fn () : -; name(c) => Node(type(c), connected[name(c)]) -; (c:DefRegister) : -; add{elements, _} $ fn () : -; val one = UIntValue(1, UnknownWidth()) -; name(c) => Register(type(c), connected[name(c)], one) -; (c:DefInstance) : -; add{elements, _} $ fn () : -; name(c) => Instance(UnknownType(), module(c), inst-ports[name(c)]) -; (c:DefMemory) : -; add{elements, _} $ fn () : -; val ports = for a in get?(write-accessors, name(c), List()) map : -; val one = UIntValue(1, UnknownWidth()) -; WritePort(index(a), connected[name(a)], one) -; name(c) => Memory(type(c), ports) -; (c:WDefAccessor) : -; val mem = source(c) as WRef -; switch {dir(c) == _} : -; INPUT : -; write-accessors[name(mem)] = List(c, -; get?(write-accessors, name(mem), List())) -; OUTPUT : -; read-accessors[name(c)] = c -; (c) : -; do(scan, children(c)) ; -; defn make-read-ports (e:Expression) : +; defn get-width (e:Expression) -> Width : ; match(e) : -; (e:WRef) : -; match(kind(e)) : -; (k:AccessorKind) : -; val accessor = read-accessors[name(e)] -; ReadPort(source(accessor), index(accessor), type(e)) -; (k) : e -; (e) : map(make-read-ports, e) -; -; Module(name(m), ports(m), body*) where : -; scan(body(m)) -; val elems = to-list $ -; for e in elements stream : -; val entry = e() -; key(entry) => map(make-read-ports, value(entry)) -; val connect-ports = Begin $ to-list $ -; for c in port-connects stream : -; Connect(loc(c), make-read-ports(exp(c))) -; val body* = -; if empty?(elems) : connect-ports -; else : LetRec(elems, connect-ports) -; -;defn structural-form (c:Circuit) : -; val modules* = map(structural-form, modules(c)) -; Circuit(modules*, main(c)) -; +; (e:WRef) : +; val w = get-width(type(e)) +; add(v,WGeq(w,h[name(e)])) +; add(v,WGeq(h[name(e)],w)) +; w +; (e:WSubfield) : ;assumes only subfields are instances +; add(v,WGeq(w, +; defn gen-constraints (s:Stmt) -> Stmt : +; match(map(gen-constraints,s)) : +; +; +;defn remove-unknown-widths (c:Circuit) -> Circuit : +; defn remove-unknown-widths-wid (w:Width) -> Width : +; match(w) : +; (w:UnknownWidth) : VarWidth(gensym(`w)) +; (w) : w +; defn remove-unknown-widths-type (t:Type) -> Type : +; map{remove-unknown-widths-wid,_} $ +; map(remove-unknown-widths-type,t) +; defn remove-unknown-widths-exp (e:Expression) -> Expression : +; map{remove-unknown-widths-wid,_} $ +; map{remove-unknown-widths-type,_} $ +; map(remove-unknown-widths-exp,e) +; defn remove-unknown-widths-stmt (s:Stmt) -> Stmt : +; map{remove-unknown-widths-type,_} $ +; map{remove-unknown-widths-exp,_} $ +; map(remove-unknown-widths-stmt,s) +; val modules* = for m in modules(c) map : +; Module{name(m),_,body(m)} $ +; for p in ports(m) map : +; Port(name(p),direction(p),remove-unknown-widths-type(type(p))) ; +; val modules** = for m in modules* map : +; Module(name(m),ports(m),remove-unknown-widths-stmt(body(m))) +; Circuit(modules**,main(c)) +; +;defn infer-widths (c:Circuit) -> Circuit : +; val c* = remove-unknown-widths(c) +; c* +; ;val l = gen-constraints(c*) +; ;val h = solve-constraints(l) +; ;replace-var-widths(c*,h) + + + + + + + + + + + + + + + + + + + + + + + + + + + ;;==================== WIDTH INFERENCE ====================== ;defstruct WidthVar <: Width : ; name: Symbol @@ -2400,8 +2298,7 @@ public defn run-passes (c: Circuit, p: List<Char>) : if contains(p,'i') : do-stage("Expand Indexed Connects", expand-connect-indexed) if contains(p,'p') : do-stage("Initialize Registers", initialize-registers) if contains(p,'j') : 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,'k') : 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) diff --git a/test/passes/expand-whens/partial-init.fir b/test/passes/expand-whens/partial-init.fir new file mode 100644 index 00000000..b1da7410 --- /dev/null +++ b/test/passes/expand-whens/partial-init.fir @@ -0,0 +1,9 @@ +; RUN: firrtl %s abcefghipj c | tee %s.out | FileCheck %s + +; CHECK: Expand Whens +circuit top : + module top : + reg r : UInt(1)[10] + r.init.3 := UInt(0) + +; CHECK: Finished Expand Whens diff --git a/test/passes/infer-widths/gcd.fir b/test/passes/infer-widths/gcd.fir new file mode 100644 index 00000000..3e1a02f5 --- /dev/null +++ b/test/passes/infer-widths/gcd.fir @@ -0,0 +1,45 @@ +; RUN: firrtl %s abcefghipjk cT | tee %s.out | FileCheck %s + +;CHECK: Infer Widths +circuit top : + module subtracter : + input x : UInt + input y : UInt + output q : UInt + q := sub-wrap(x, y) + module gcd : + input a : UInt(16) + input b : UInt(16) + input e : UInt(1) + output z : UInt(16) + output v : UInt(1) + reg x : UInt + reg y : UInt + x.init := UInt(0) + y.init := UInt(42) + when gt(x, y) : + inst s of subtracter + s.x := x + s.y := y + x := s.q + else : + inst s2 of subtracter + s2.x := x + s2.y := y + y := s2.q + when e : + x := a + y := b + v := equal(v, UInt(0)) + z := x + module top : + input a : UInt(16) + input b : UInt(16) + output z : UInt + inst i of gcd + i.a := a + i.b := b + i.e := UInt(1) + z := i.z + +; CHECK: Finished Infer Widths diff --git a/test/passes/jacktest/bundlewire.fir b/test/passes/jacktest/bundlewire.fir new file mode 100644 index 00000000..0d0f0377 --- /dev/null +++ b/test/passes/jacktest/bundlewire.fir @@ -0,0 +1,20 @@ +; RUN: firrtl %s abcefghipj c | tee %s.out | FileCheck %s + +; CHECK: Expand Whens + +circuit BundleWire : + module BundleWire : + output in : { y : UInt(32), x : UInt(32) } + output outs : { y : UInt(32), x : UInt(32) }[4] + + wire coords : { y : UInt(32), x : UInt(32) }[4] + coords.0 := in + outs.0 := coords.0 + coords.1 := in + outs.1 := coords.1 + coords.2 := in + outs.2 := coords.2 + coords.3 := in + outs.3 := coords.3 + +; CHECK: Finished Expand Whens diff --git a/test/passes/jacktest/vecshift.fir b/test/passes/jacktest/vecshift.fir new file mode 100644 index 00000000..9910064d --- /dev/null +++ b/test/passes/jacktest/vecshift.fir @@ -0,0 +1,24 @@ +; RUN: firrtl %s abcefghipj c | tee %s.out | FileCheck %s + +; CHECK: Expand Whens + +circuit VecShiftRegister : + module VecShiftRegister : + input load : UInt(1) + output out : UInt(4) + input shift : UInt(1) + input ins : UInt(4)[4] + + reg delays : UInt(4)[4] + when load : + delays.0 := ins.0 + delays.1 := ins.1 + delays.2 := ins.2 + delays.3 := ins.3 + else : when shift : + delays.0 := ins.0 + delays.1 := delays.0 + delays.2 := delays.1 + delays.3 := delays.2 + out := delays.3 +; CHECK: Finished Expand Whens |