From a4f7aa2b81a021f21a49bd4059d051bc0f949880 Mon Sep 17 00:00:00 2001 From: azidar Date: Wed, 22 Apr 2015 15:24:18 -0700 Subject: Switched to stricter primop width constraints. Implemented Pad. Added some missing primops --- TODO | 9 ++ src/main/stanza/firrtl-ir.stanza | 4 + src/main/stanza/firrtl-test-main.stanza | 1 + src/main/stanza/ir-parser.stanza | 16 ++- src/main/stanza/ir-utils.stanza | 4 + src/main/stanza/passes.stanza | 196 ++++++++++++++++------------- src/main/stanza/primop.stanza | 214 +++++++++++++++++--------------- test/passes/infer-widths/gcd.fir | 2 +- test/passes/infer-widths/simple.fir | 10 +- test/passes/jacktest/SIntOps.fir | 52 ++++++++ test/passes/jacktest/UIntOps.fir | 47 +++++++ test/passes/jacktest/gcd.fir | 4 +- test/passes/jacktest/risc.fir | 2 +- 13 files changed, 363 insertions(+), 198 deletions(-) create mode 100644 test/passes/jacktest/SIntOps.fir create mode 100644 test/passes/jacktest/UIntOps.fir diff --git a/TODO b/TODO index bf847a6f..4a099d94 100644 --- a/TODO +++ b/TODO @@ -8,8 +8,10 @@ Parser Error if incorrectly assign stuff, like use = instead of := Update parser and update tests Change all primops to be strict on data widths +Add pad! Make instances always male, flip the bundles on declaration dlsh,drsh +move Infer-Widths to before vec expansion? ======== Update Core ========== Add source locaters @@ -25,6 +27,8 @@ Well-formed high firrtl Subfields are only on bundles, before type inference Can only connect to a Ref or Subfield or Index UInt only has positive ints + No combinational loops + cannot connect to a pad, or a register. only connct to a reference After adding dynamic assertions, insert bounds check with accessor expansion Well-formed low firrtl All things only assigned to once @@ -32,6 +36,7 @@ Well-formed low firrtl ======== Other Passes ======== constant folding (partial eval) pass common subexpression elimination pass +Verilog backend ======== Consultations ======== Stephen: @@ -52,6 +57,10 @@ Figure out how widths propogate for all updated primops (Adam) Add partial bulk connect (Scott, Stephen) Add FIFOs to the IR (Palmer) Think about supporting generic primops on bundles and vecs (Adam) (wait until front-end more completed) +Union Types +Enums? +Convert to scala +Firrtl interpreter (in scala) ======== Update Spec ======== Add Not to spec diff --git a/src/main/stanza/firrtl-ir.stanza b/src/main/stanza/firrtl-ir.stanza index d4d12400..f14378cc 100644 --- a/src/main/stanza/firrtl-ir.stanza +++ b/src/main/stanza/firrtl-ir.stanza @@ -161,6 +161,10 @@ public defstruct Register <: Expression : type: Type with: (as-method => true) value: Expression enable: Expression +public defstruct Pad <: Expression : + value: Expression + width: Width + type: Type with: (as-method => true) public definterface Stmt public defstruct DefWire <: Stmt : ;LOW diff --git a/src/main/stanza/firrtl-test-main.stanza b/src/main/stanza/firrtl-test-main.stanza index 54fcb7f9..f929455d 100644 --- a/src/main/stanza/firrtl-test-main.stanza +++ b/src/main/stanza/firrtl-test-main.stanza @@ -25,6 +25,7 @@ defn set-printvars! (p:List) : if contains(p,'T') : PRINT-TWIDTHS = true if contains(p,'g') : PRINT-GENDERS = true if contains(p,'c') : PRINT-CIRCUITS = true + if contains(p,'d') : PRINT-DEBUG = true ;firrtl -i gcd.fir -o gcd.flo -x qabcefghipjklmno -p c defn main () : diff --git a/src/main/stanza/ir-parser.stanza b/src/main/stanza/ir-parser.stanza index 6ec0c4d2..1772d773 100644 --- a/src/main/stanza/ir-parser.stanza +++ b/src/main/stanza/ir-parser.stanza @@ -203,13 +203,19 @@ defsyntax firrtl : operators[`bit-or-reduce] = BIT-OR-REDUCE-OP operators[`bit-xor-reduce] = BIT-XOR-REDUCE-OP + defrule width : + width = (?) : + UnknownWidth() + width = (?width:#int) : + IntWidth(ut(width)) + defrule exp-form : - exp-form = (UInt (@do ?value:#int ?width:#int)) : - UIntValue(ut(value), IntWidth(ut(width))) + exp-form = (UInt (@do ?value:#int ?width:#width)) : + UIntValue(ut(value), width) exp-form = (UInt (@do ?value:#int)) : UIntValue(ut(value), UnknownWidth()) - exp-form = (SInt (@do ?value:#int ?width:#int)) : - SIntValue(ut(value), IntWidth(ut(width))) + exp-form = (SInt (@do ?value:#int ?width:#width)) : + SIntValue(ut(value), width) exp-form = (SInt (@do ?value:#int)) : SIntValue(ut(value), UnknownWidth()) exp-form = (WritePort (@do ?mem:#exp ?index:#exp ?enable:#exp)) : @@ -218,6 +224,8 @@ defsyntax firrtl : ReadPort(mem, index, UnknownType(), enable) exp-form = (Register (@do ?value:#exp ?enable:#exp)) : Register(UnknownType(),value,enable) + exp-form = (Pad (@do ?value:#exp ?width:#width)) : + Pad(value,width,UnknownType()) exp-form = (?op:#symbol (@do ?es:#exp ... ?ints:#int ...)) : println("Op-symbol is:~" % [op]) match(get?(operators, ut(op), false)) : diff --git a/src/main/stanza/ir-utils.stanza b/src/main/stanza/ir-utils.stanza index 2df09b8e..86fe56d1 100644 --- a/src/main/stanza/ir-utils.stanza +++ b/src/main/stanza/ir-utils.stanza @@ -150,6 +150,7 @@ defmethod print (o:OutputStream, e:Expression) : (e:ReadPort) : print-all(o, ["ReadPort(" mem(e) ", " index(e) ", " enable(e) ")"]) (e:WritePort) : print-all(o, ["WritePort(" mem(e) ", " index(e) ", " enable(e) ")"]) (e:Register) : print-all(o, ["Register(" value(e) ", " enable(e) ")"]) + (e:Pad) : print-all(o, ["Pad(" value(e) ", " width(e) ")"]) print-debug(o,e) defmethod print (o:OutputStream, c:Stmt) : @@ -246,6 +247,7 @@ defmethod map (f: Expression -> Expression, e:Expression) -> Expression : (e:ReadPort) : ReadPort(f(mem(e)), f(index(e)), type(e), f(enable(e))) (e:WritePort) : WritePort(f(mem(e)), f(index(e)), type(e), f(enable(e))) (e:Register) : Register(type(e),f(value(e)),f(enable(e))) + (e:Pad) : Pad(f(value(e)),width(e),type(e)) (e) : e public defmulti map (f: Expression -> Expression, c:?T&Stmt) -> T @@ -270,6 +272,7 @@ 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:Pad) : Pad(value(c),f(width(c)),type(c)) (c) : c public defmulti map (f: Width -> Width, c:?T&Type) -> T @@ -289,6 +292,7 @@ defmethod map (f: Type -> Type, c:Expression) -> Expression : (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:Pad) : Pad(value(c),width(c),f(type(c))) (c) : c public defmulti map (f: Type -> Type, c:?T&Stmt) -> T diff --git a/src/main/stanza/passes.stanza b/src/main/stanza/passes.stanza index 5864e8bb..588b4b73 100644 --- a/src/main/stanza/passes.stanza +++ b/src/main/stanza/passes.stanza @@ -155,7 +155,17 @@ 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 +public var PRINT-DEBUG : True|False = false ;=== Printers === + +public defn println-all-debug (l:?) -> False : + if PRINT-DEBUG : println-all(l) + else : false + +public defn println-debug (s:?) -> False : + if PRINT-DEBUG : println(s) + else : false + defmethod print (o:OutputStream, k:Kind) : print{o, _} $ match(k) : @@ -175,12 +185,12 @@ 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 + e typeof UIntType|SIntType|UIntValue|SIntValue|Pad defn hasType (e:Expression|Stmt|Type|Port|Field) : e typeof Ref|Subfield|Index|DoPrim|WritePort|ReadPort|WRef|WSubfield |WIndex|DefWire|DefRegister|DefMemory|Register - |VectorType|Port|Field|WRegInit + |VectorType|Port|Field|WRegInit|Pad defn hasKind (e:Expression|Stmt|Type|Port|Field) : e typeof WRef @@ -446,6 +456,8 @@ defn infer-exp-types (e:Expression, l:List>) -> Expression ;DoPrim(op(e),args(e),consts(e),get-primop-rettype(e)) (e:ReadPort) : ReadPort(mem(e),index(e),get-vector-subtype(type(mem(e))),enable(e)) (e:WritePort) : WritePort(mem(e),index(e),get-vector-subtype(type(mem(e))),enable(e)) + (e:Register) : Register(type(value(e)),value(e),enable(e)) + (e:Pad) : Pad(value(e),width(e),type(value(e))) (e:UIntValue|SIntValue) : e defn infer-types (s:Stmt, l:List>) -> [Stmt List>] : @@ -474,7 +486,7 @@ defn infer-types (m:Module, l:List>) -> Module : val ptypes = for p in ports(m) map : name(p) => type(p) - ;println-all(append(ptypes,l)) + println-all-debug(append(ptypes,l)) val [s,l*] = infer-types(body(m),append(ptypes, l)) Module(name(m),ports(m),s) @@ -482,7 +494,7 @@ defn infer-types (c:Circuit) -> Circuit : val l = for m in modules(c) map : name(m) => BundleType(map(to-field,ports(m))) - ;println-all(l) + println-all-debug(l) Circuit{ _, main(c) } $ for m in modules(c) map : infer-types(m,l) @@ -587,11 +599,11 @@ defn resolve-genders (c:Circuit) : (e) : map(resolve-expr{_,MALE},e) var module* = resolve-iter(m) - ;println(genders) + println-debug(genders) while not done? : done? = true module* = resolve-iter(m) - ;println(genders) + ;println-debug(genders) module* defn resolve-genders (m:Module, c:Circuit) -> Module : @@ -619,7 +631,7 @@ defn expand-vector (e:Expression) -> List : defn expand-stmt (s:Stmt) -> Stmt : match(s) : (s:WDefAccessor) : - ;println-all(["Matched WDefAcc with " name(s)]) + println-all-debug(["Matched WDefAcc with " name(s)]) val mem? = match(source(s)) : (e:WRef) : kind(e) typeof MemKind (e) : false @@ -715,11 +727,11 @@ defn lower (body:Stmt, table:HashTable>>) lower-stmt(s*) (s:Connect) : Begin{_} $ for (l in expand-expr(loc(s)), r in expand-expr(exp(s))) map : - println(s) + println-debug(s) val lgender = calc-gender(FEMALE,loc(s)) * value(l) val rgender = calc-gender(MALE,exp(s)) * value(r) - println(loc(s)) - println(exp(s)) + println-debug(loc(s)) + println-debug(exp(s)) switch fn ([x,y]) : lgender == x and rgender == y : [FEMALE,MALE] : Connect(key(l),key(r)) [MALE,FEMALE] : Connect(key(r),key(l)) @@ -779,7 +791,7 @@ defn lower (body:Stmt, table:HashTable>>) headn(tailn(exps,len * value(e)),len) (e) : list(KeyValue(e, DEFAULT)) - ;println(table) + ;println-debug(table) lower-stmt(body) defn get-entries (n:Symbol,t:Type) -> List> : @@ -955,7 +967,7 @@ defn initialize-registers (c:Circuit) : defn explicit-init-scope (s:Stmt) -> Stmt : val h = HashTable(symbol-hash) using-init(s,h) - ;println(h) + ;println-debug(h) val [s* t] = rename(s,h) add-when(s*,t) @@ -1262,7 +1274,7 @@ defn build-tables (s:Stmt, add(decs,s) for f in fields(type(module(s)) as BundleType) do : val n = to-symbol("~.~" % [name(s),name(f)]) ; only on inputs - ;println-all(["In DefInst adding: " n]) + println-all-debug(["In DefInst adding: " n]) kinds[n] = InstanceKind() assign[n] = SVNul() stmts[n] = s @@ -1282,12 +1294,12 @@ defn build-tables (s:Stmt, 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 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) + ;println-debug("TABLE-C") + ;for x in assign-c do : println-debug(x) + ;println-debug("TABLE-A") + ;for x in assign-a do : println-debug(x) + ;println-debug("TABLE") + ;for x in assign do : println-debug(x) (s:Connect) : val key* = match(loc(s)) : (e:WRef) : name(e) @@ -1314,14 +1326,14 @@ defn expand-whens (m:Module) -> Module : 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-debug("Assigns") + ;for x in assign do : println-debug(x) + ;println-debug("Kinds") + ;for x in kinds do : println-debug(x) + ;println-debug("Decs") + ;for x in decs do : println-debug(x) + ;println-debug("Enables") + ;for x in enables do : println-debug(x) Module(name(m),ports(m),expand-whens(assign,kinds,stmts,decs,enables)) @@ -1412,30 +1424,30 @@ defn solve-constraints (l:List) -> HashTable : val v = Vector() for w* in args(w) do : match(w*) : - (w:MaxWidth) : - for x in args(w) do : add(v,x) - (w) : add(v,w) + (w*:MaxWidth) : + for x in args(w*) do : add(v,x) + (w*) : add(v,w*) MaxWidth(unique(v)) (w) : w defn substitute (w:Width,h:HashTable) -> Width : - ;println-all(["Substituting for [" w "]"]) + ;println-all-debug(["Substituting for [" w "]"]) val w* = simplify(w) - ;println-all(["After Simplify: [" w "]"]) + ;println-all-debug(["After Simplify: [" w* "]"]) match(map(substitute{_,h},simplify(w))) : (w:VarWidth) : - ;println("matched varwidth!") + ;println-debug("matched varwidth!") if contains?(name(w),h) : - ;println("Contained!") - ;println-all(["Width: " w]) - ;println-all(["Accessed: " h[name(w)]]) + ;println-debug("Contained!") + ;println-all-debug(["Width: " w]) + ;println-all-debug(["Accessed: " h[name(w)]]) val t = simplify(substitute(h[name(w)],h)) ;val t = h[name(w)] - ;println-all(["Width after sub: " t]) + ;println-all-debug(["Width after sub: " t]) h[name(w)] = t t else : w (w): - ;println-all(["not varwidth!" w]) + ;println-all-debug(["not varwidth!" w]) w defn b-sub (w:Width,h:HashTable) -> Width: match(map(b-sub{_,h},w)) : @@ -1444,11 +1456,11 @@ defn solve-constraints (l:List) -> HashTable : else : w (w) : w defn remove-cycle (n:Symbol,w:Width) -> Width : - ;println-all(["Removing cycle for " n " inside " w]) + ;println-all-debug(["Removing cycle for " n " inside " w]) val w* = match(map(remove-cycle{n,_},w)) : (w:MaxWidth) : MaxWidth(to-list(filter({_ != VarWidth(n)},args(w)))) (w) : w - ;println-all(["After removing cycle for " n ", returning " w*]) + ;println-all-debug(["After removing cycle for " n ", returning " w*]) w* defn self-rec? (n:Symbol,w:Width) -> True|False : var has? = false @@ -1467,7 +1479,7 @@ defn solve-constraints (l:List) -> HashTable : if length(l) == 0 : 0 else : apply(head(l),apply-l(tail(l),f),f) defn max (a:Int,b:Int) -> Int : - if a > b : a + if a >= b : a else : b defn solve (w:Width) -> Int|False : match(w) : @@ -1490,55 +1502,55 @@ defn solve-constraints (l:List) -> HashTable : ; 2) Remove Cycles ; 3) Move to solved if not self-recursive val u = make-unique(l) - ;println("======== UNIQUE CONSTRAINTS ========") - ;for x in u do : println(x) - ;println("====================================") + ;println-debug("======== UNIQUE CONSTRAINTS ========") + ;for x in u do : println-debug(x) + ;println-debug("====================================") val f = HashTable(symbol-hash) val o = Vector() for x in u do : - ;println("==== SOLUTIONS TABLE ====") - ;for x in f do : println(x) - ;println("=========================") + ;println-debug("==== SOLUTIONS TABLE ====") + ;for x in f do : println-debug(x) + ;println-debug("=========================") val [n e] = [key(x) value(x)] val e-sub = substitute(e,f) - ;println(["Solving " n " => " e]) - ;println(["After Substitute: " n " => " e-sub]) - ;println("==== SOLUTIONS TABLE (Post Substitute) ====") - ;for x in f do : println(x) - ;println("=========================") + ;println-debug(["Solving " n " => " e]) + ;println-debug(["After Substitute: " n " => " e-sub]) + ;println-debug("==== SOLUTIONS TABLE (Post Substitute) ====") + ;for x in f do : println-debug(x) + ;println-debug("=========================") val e* = remove-cycle{n,_} $ e-sub - ;println(["After Remove Cycle: " n " => " e*]) + ;println-debug(["After Remove Cycle: " n " => " e*]) if not self-rec?(n,e*) : - ;println-all(["Not rec!: " n " => " e*]) - ;println-all(["Adding [" n "=>" e* "] to Solutions Table"]) + ;println-all-debug(["Not rec!: " n " => " e*]) + ;println-all-debug(["Adding [" n "=>" e* "] to Solutions Table"]) add(o,n) f[n] = e* - ;println("Forward Solved Constraints") - ;for x in f do : println(x) + ;println-debug("Forward Solved Constraints") + ;for x in f do : println-debug(x) ; Backwards Solve val b = HashTable(symbol-hash) for i in (length(o) - 1) through 0 by -1 do : val n = o[i] - ;println-all(["SOLVE BACK: [" n " => " f[n] "]"]) - ;println("==== SOLUTIONS TABLE ====") - ;for x in b do : println(x) - ;println("=========================") + ;println-all-debug(["SOLVE BACK: [" n " => " f[n] "]"]) + ;println-debug("==== SOLUTIONS TABLE ====") + ;for x in b do : println-debug(x) + ;println-debug("=========================") val e* = simplify(b-sub(f[n],b)) - ;println-all(["BACK RETURN: [" n " => " e* "]"]) + ;println-all-debug(["BACK RETURN: [" n " => " e* "]"]) b[n] = e* - ;println("==== SOLUTIONS TABLE (Post backsolve) ====") - ;for x in b do : println(x) - ;println("=========================") + ;println-debug("==== SOLUTIONS TABLE (Post backsolve) ====") + ;for x in b do : println-debug(x) + ;println-debug("=========================") ; Evaluate val e = evaluate(b) - ;println("Evaluated Constraints") - ;for x in e do : println(x) + ;println-debug("Evaluated Constraints") + ;for x in e do : println-debug(x) e public defn width! (t:Type) -> Width : @@ -1549,7 +1561,6 @@ public defn width! (t:Type) -> Width : public defn width! (e:Expression) -> Width : width!(type(e)) defn gen-constraints (m:Module, h:HashTable, v:Vector) -> Module: - defn gen-constraints-s (s:Stmt) -> Stmt : match(map(gen-constraints-s,s)) : (s:DefWire) : DefWire(name(s),h[name(s)]) @@ -1570,6 +1581,15 @@ defn gen-constraints (m:Module, h:HashTable, v:Vector) -> Mod (e:WSubfield) : WSubfield(exp(e),name(e),bundle-field-type(type(exp(e)),name(e)),gender(e)) (e:WIndex) : error("Shouldn't be here") (e:DoPrim) : DoPrim(op(e),args(e),consts(e),primop-gen-constraints(e,v)) + (e:Pad) : + val value-w = width!(value(e)) + val pad-w = remove-unknowns-w(width(e)) + ;add(v,WGeq(pad-w, IntWidth(0))) + val pad-t = match(type(e)) : + (t:UIntType) : UIntType(pad-w) + (t:SIntType) : SIntType(pad-w) + (t) : error("Shouldn't be here") + Pad(value(e),pad-w,pad-t) (e:ReadPort) : ReadPort(mem(e),index(e),type(type(mem(e)) as VectorType),enable(e)) (e:WritePort) : WritePort(mem(e),index(e),type(type(mem(e)) as VectorType),enable(e)) (e:Register) : Register(type(value(e)),value(e),enable(e)) @@ -1610,13 +1630,13 @@ defn build-environment (c:Circuit,m:Module,h:HashTable) -> HashTabl defn replace-var-widths (c:Circuit,h:HashTable) -> Circuit : defn replace-var-widths-w (w:Width) -> Width : - ;println-all(["REPLACE: " w]) + println-all-debug(["REPLACE: " w]) val w* = match(w) : (w:VarWidth) : if key?(h,name(w)) : IntWidth(h[name(w)]) else: w (w) : w - ;println-all(["WITH: " w*]) + println-all-debug(["WITH: " w*]) w* val modules* = for m in modules(c) map : @@ -1639,29 +1659,27 @@ defn infer-widths (c:Circuit) -> Circuit : for x in t do : t0[key(x)] = value(x) - ;val c* = remove-unknown-widths(c) - ;println(c*) val v = Vector() val ports* = HashTable(symbol-hash) for m in modules(c) do : ports*[name(m)] = remove-unknowns(BundleType(map(to-field,ports(m)))) val modules* = for m in modules(c) map : - ;println-all(["====== MODULE(" name(m) ") ENV ======"]) + println-all-debug(["====== MODULE(" name(m) ") ENV ======"]) val h = build-environment(c,m,deepcopy(ports*)) - ;for x in h do: println(x) - ;println-all(["====================================="]) + for x in h do: println-debug(x) + println-all-debug(["====================================="]) val m* = gen-constraints(m,h,v) - ;println-all(["====== MODULE(" name(m) ") ======"]) - ;println(m*) - ;println-all(["====================================="]) + println-all-debug(["====== MODULE(" name(m) ") ======"]) + println-debug(m*) + println-all-debug(["====================================="]) m* - ;println("======== ALL CONSTRAINTS ========") - ;for x in v do : println(x) - ;println("=================================") + println-debug("======== ALL CONSTRAINTS ========") + for x in v do : println-debug(x) + println-debug("=================================") val h = solve-constraints(to-list(v)) - ;println("======== SOLVED CONSTRAINTS ========") - ;for x in h do : println(x) - ;println("====================================") + println-debug("======== SOLVED CONSTRAINTS ========") + for x in h do : println-debug(x) + println-debug("====================================") replace-var-widths(Circuit(modules*,main(c)),h) @@ -1738,7 +1756,7 @@ defn split-exp (c:Circuit) : false defn split-exp-e (e:Expression,v:Vector,n:Symbol|False) -> Expression : match(map(split-exp-e{_,v,n},e)): - (e:Subfield|DoPrim|ReadPort|Register|WritePort) : + (e:Subfield|DoPrim|Pad|ReadPort|Register|WritePort) : val n* = if n typeof False : gensym(`T) else : to-symbol $ string-join $ [n as Symbol gensym(`#)] @@ -1836,6 +1854,8 @@ defn flo-op-name (op:PrimOp) -> String : MUX-SS-OP : "mux" PAD-U-OP : "rsh" ;; todo: signed version PAD-S-OP : "rsh" ;; todo: signed version + NEG-U-OP : "neg" + NEG-S-OP : "neg" ;AS-UINT-U-OP : ;AS-UINT-S-OP : ;AS-SINT-U-OP : @@ -1889,6 +1909,8 @@ defn emit! (e:Expression,top:Symbol) : (e:SIntValue) : emit-all([value(e) "'" sane-width(width(e))], top) (e:Subfield) : emit-all([exp(e) "/" name(e)], top) (e:Index) : emit-all([exp(e) "/" value(e)], top) + (e:Pad) : + emit-all(["rsh'" prim-width(type(e)) " " value(e) " " width(e)], top) (e:Register) : emit-all(["reg'" prim-width(type(e)) " " enable(e) " " value(e)], top) (e:ReadPort) : @@ -1910,8 +1932,8 @@ defn emit! (e:Expression,top:Symbol) : ;; emit-all([flo-op-name(op(e)) "'" w " " args(e)[0] " " consts(e)[1]], top) else : emit-all([flo-op-name(op(e)) "'" prim-width(type(e))], top) - if op(e) == PAD-OP : - emit-all([" " args(e)[0] " 0"], top) + if (op(e) == PAD-U-OP) or (op(e) == PAD-S-OP) : + emit-all([" " args(e)[0] " " consts(e)[0]], top) else : for arg in args(e) do : print(" ") diff --git a/src/main/stanza/primop.stanza b/src/main/stanza/primop.stanza index b42380e6..14589135 100644 --- a/src/main/stanza/primop.stanza +++ b/src/main/stanza/primop.stanza @@ -248,106 +248,116 @@ public defn lower-and-type-primop (e:DoPrim) -> DoPrim : BIT-XOR-REDUCE-OP: DoPrim(op(e),args(e),consts(e),u()) public defn primop-gen-constraints (e:DoPrim,v:Vector) -> Type : - defn add-c (w:Width) -> Type: - val w* = VarWidth(gensym(`w)) - add(v,WGeq(w*,w)) - add(v,WGeq(w,w*)) - match(type(e)) : - (t:UIntType) : UIntType(w*) - (t:SIntType) : SIntType(w*) - (t) : error("Shouldn't be here") - defn wpc (l:List,c:List) : - add-c(PlusWidth(width!(l[0]),IntWidth(c[0]))) - defn wmc (l:List,c:List) : - add-c(MinusWidth(width!(l[0]),IntWidth(c[0]))) - defn maxw (l:List) : - add-c(MaxWidth(map(width!,l))) - defn cons (ls:List) : - val l = width!(ls[0]) - val r = width!(ls[1]) - add(v,WGeq(l,r)) - add(v,WGeq(r,l)) - add-c(l) - add-c(r) - defn mp1 (l:List) : - add-c(PlusWidth(MaxWidth(list(width!(l[0]),width!(l[1]))),IntWidth(1))) - defn sum (l:List) : - add-c(PlusWidth(width!(l[0]),width!(l[1]))) + defn all-equal (ls:List) -> Width : + if length(ls) == 1 : width!(ls[0]) + else : + val m = MaxWidth(map(width!,ls)) + for (l in ls) do : + add(v,WGeq(width!(l),m)) + m + ;defn new-width (w:Width) -> Width: + ; val w* = VarWidth(gensym(`w)) + ; add(v,WGeq(w*,w)) + ; ;add(v,WGeq(w,w*)) + ; w* + ;defn width-plus-const (l:List,c:List) -> Width : + ; new-width(PlusWidth(width!(l[0]),IntWidth(c[0]))) + ;defn width-minus-const (l:List,c:List) -> Width : + ; new-width(MinusWidth(width!(l[0]),IntWidth(c[0]))) + ;defn max-width (l:List) -> Width : + ; new-width(MaxWidth(map(width!,l))) + ;defn max-plus-one (l:List) -> Width : + ; new-width(PlusWidth(MaxWidth(list(width!(l[0]),width!(l[1]))),IntWidth(1))) + ;defn sum (l:List) -> Width : + ; new-width(PlusWidth(width!(l[0]),width!(l[1]))) + + println-all-debug(["Looking at " op(e) " with inputs " args(e)]) + val all-args-not-equal = list(MUX-UU-OP,MUX-SS-OP,CONCAT-OP) + ;val consts-gte-args = list(PAD-U-OP,PAD-S-OP) + + val w* = + if not contains?(all-args-not-equal,op(e)) : + val max-args-w = all-equal(args(e)) + switch {op(e) == _} : + ADD-UU-OP : PlusWidth(max-args-w,IntWidth(1)) + ADD-US-OP : PlusWidth(max-args-w,IntWidth(1)) + ADD-SU-OP : PlusWidth(max-args-w,IntWidth(1)) + ADD-SS-OP : PlusWidth(max-args-w,IntWidth(1)) + SUB-UU-OP : PlusWidth(max-args-w,IntWidth(1)) + SUB-US-OP : PlusWidth(max-args-w,IntWidth(1)) + SUB-SU-OP : PlusWidth(max-args-w,IntWidth(1)) + SUB-SS-OP : PlusWidth(max-args-w,IntWidth(1)) + MUL-UU-OP : PlusWidth(max-args-w,max-args-w) + MUL-US-OP : PlusWidth(max-args-w,max-args-w) + MUL-SU-OP : PlusWidth(max-args-w,max-args-w) + MUL-SS-OP : PlusWidth(max-args-w,max-args-w) + DIV-UU-OP : max-args-w + DIV-US-OP : PlusWidth(max-args-w,IntWidth(1)) + DIV-SU-OP : max-args-w + DIV-SS-OP : PlusWidth(max-args-w,IntWidth(1)) + ADD-WRAP-UU-OP : max-args-w + ADD-WRAP-US-OP : max-args-w + ADD-WRAP-SU-OP : max-args-w + ADD-WRAP-SS-OP : max-args-w + SUB-WRAP-UU-OP : max-args-w + SUB-WRAP-US-OP : max-args-w + SUB-WRAP-SU-OP : max-args-w + SUB-WRAP-SS-OP : max-args-w + LESS-UU-OP : IntWidth(1) + LESS-US-OP : IntWidth(1) + LESS-SU-OP : IntWidth(1) + LESS-SS-OP : IntWidth(1) + LESS-EQ-UU-OP : IntWidth(1) + LESS-EQ-US-OP : IntWidth(1) + LESS-EQ-SU-OP : IntWidth(1) + LESS-EQ-SS-OP : IntWidth(1) + GREATER-UU-OP : IntWidth(1) + GREATER-US-OP : IntWidth(1) + GREATER-SU-OP : IntWidth(1) + GREATER-SS-OP : IntWidth(1) + GREATER-EQ-UU-OP : IntWidth(1) + GREATER-EQ-US-OP : IntWidth(1) + GREATER-EQ-SU-OP : IntWidth(1) + GREATER-EQ-SS-OP : IntWidth(1) + EQUAL-UU-OP : IntWidth(1) + EQUAL-SS-OP : IntWidth(1) + NEQUAL-UU-OP : IntWidth(1) + NEQUAL-SS-OP : IntWidth(1) + PAD-U-OP : IntWidth(consts(e)[0]) + PAD-S-OP : IntWidth(consts(e)[0]) + NEG-U-OP : IntWidth(1) + NEG-S-OP : IntWidth(1) + AS-UINT-U-OP : max-args-w + AS-UINT-S-OP : max-args-w + AS-SINT-U-OP : max-args-w + AS-SINT-S-OP : max-args-w + SHIFT-LEFT-U-OP : PlusWidth(max-args-w,IntWidth(consts(e)[0])) + SHIFT-LEFT-S-OP : PlusWidth(max-args-w,IntWidth(consts(e)[0])) + SHIFT-RIGHT-U-OP : MinusWidth(max-args-w,IntWidth(consts(e)[0])) + SHIFT-RIGHT-S-OP : MinusWidth(max-args-w,IntWidth(consts(e)[0])) + CONVERT-U-OP : PlusWidth(max-args-w,IntWidth(1)) + CONVERT-S-OP : max-args-w + BIT-NOT-OP : max-args-w + BIT-AND-OP : max-args-w + BIT-OR-OP : max-args-w + BIT-XOR-OP : max-args-w + BIT-SELECT-OP : IntWidth(1) + BITS-SELECT-OP : IntWidth(consts(e)[0] - consts(e)[1]) + else : + switch {op(e) == _} : + MUX-UU-OP : + add(v,WGeq(width!(args(e)[0]),IntWidth(1))) + all-equal(tail(args(e))) + MUX-SS-OP : + add(v,WGeq(width!(args(e)[0]),IntWidth(1))) + all-equal(tail(args(e))) + CONCAT-OP : + PlusWidth(width!(args(e)[0]),width!(args(e)[1])) + + val w-var = VarWidth(gensym(`w)) + add(v,WGeq(w-var,w*)) + match(type(e)) : + (t:UIntType) : UIntType(w-var) + (t:SIntType) : SIntType(w-var) + (t) : error("Shouldn't be here") - ;println-all(["Looking at " op(e) " with inputs " args(e)]) - switch {op(e) == _} : - ADD-UU-OP : mp1(args(e)) - ADD-US-OP : mp1(args(e)) - ADD-SU-OP : mp1(args(e)) - ADD-SS-OP : mp1(args(e)) - SUB-UU-OP : mp1(args(e)) - SUB-US-OP : mp1(args(e)) - SUB-SU-OP : mp1(args(e)) - SUB-SS-OP : mp1(args(e)) - MUL-UU-OP : sum(args(e)) - MUL-US-OP : sum(args(e)) - MUL-SU-OP : sum(args(e)) - MUL-SS-OP : sum(args(e)) - ;(p:DIV-UU-OP) : - ;(p:DIV-US-OP) : - ;(p:DIV-SU-OP) : - ;(p:DIV-SS-OP) : - ;(p:MOD-UU-OP) : - ;(p:MOD-US-OP) : - ;(p:MOD-SU-OP) : - ;(p:MOD-SS-OP) : - ;(p:QUO-UU-OP) : - ;(p:QUO-US-OP) : - ;(p:QUO-SU-OP) : - ;(p:QUO-SS-OP) : - ;(p:REM-UU-OP) : - ;(p:REM-US-OP) : - ;(p:REM-SU-OP) : - ;(p:REM-SS-OP) : - ADD-WRAP-UU-OP : maxw(args(e)) - ADD-WRAP-US-OP : maxw(args(e)) - ADD-WRAP-SU-OP : maxw(args(e)) - ADD-WRAP-SS-OP : maxw(args(e)) - SUB-WRAP-UU-OP : maxw(args(e)) - SUB-WRAP-US-OP : maxw(args(e)) - SUB-WRAP-SU-OP : maxw(args(e)) - SUB-WRAP-SS-OP : maxw(args(e)) - LESS-UU-OP : add-c(IntWidth(1)) - LESS-US-OP : add-c(IntWidth(1)) - LESS-SU-OP : add-c(IntWidth(1)) - LESS-SS-OP : add-c(IntWidth(1)) - LESS-EQ-UU-OP : add-c(IntWidth(1)) - LESS-EQ-US-OP : add-c(IntWidth(1)) - LESS-EQ-SU-OP : add-c(IntWidth(1)) - LESS-EQ-SS-OP : add-c(IntWidth(1)) - GREATER-UU-OP : add-c(IntWidth(1)) - GREATER-US-OP : add-c(IntWidth(1)) - GREATER-SU-OP : add-c(IntWidth(1)) - GREATER-SS-OP : add-c(IntWidth(1)) - GREATER-EQ-UU-OP : add-c(IntWidth(1)) - GREATER-EQ-US-OP : add-c(IntWidth(1)) - GREATER-EQ-SU-OP : add-c(IntWidth(1)) - GREATER-EQ-SS-OP : add-c(IntWidth(1)) - EQUAL-UU-OP : add-c(IntWidth(1)) - EQUAL-SS-OP : add-c(IntWidth(1)) - MUX-UU-OP : cons(args(e)) - MUX-SS-OP : cons(args(e)) - PAD-U-OP : add-c(IntWidth(consts(e)[0])) - PAD-S-OP : add-c(IntWidth(consts(e)[0])) - AS-UINT-U-OP : add-c(width!(args(e)[0])) - AS-UINT-S-OP : add-c(width!(args(e)[0])) - AS-SINT-U-OP : add-c(width!(args(e)[0])) - AS-SINT-S-OP : add-c(width!(args(e)[0])) - SHIFT-LEFT-U-OP : wpc(args(e),consts(e)) - SHIFT-LEFT-S-OP : wpc(args(e),consts(e)) - SHIFT-RIGHT-U-OP : wmc(args(e),consts(e)) - SHIFT-RIGHT-S-OP : wmc(args(e),consts(e)) - CONVERT-U-OP : add-c(PlusWidth(width!(args(e)[0]),IntWidth(1))) - CONVERT-S-OP : add-c(width!(args(e)[0])) - BIT-NOT-OP : maxw(args(e)) - BIT-AND-OP : maxw(args(e)) - BIT-OR-OP : maxw(args(e)) - BIT-XOR-OP : maxw(args(e)) - CONCAT-OP : sum(args(e)) - BIT-SELECT-OP : add-c(IntWidth(1)) - BITS-SELECT-OP : add-c(IntWidth(consts(e)[0] - consts(e)[1])) diff --git a/test/passes/infer-widths/gcd.fir b/test/passes/infer-widths/gcd.fir index a550326b..864852fb 100644 --- a/test/passes/infer-widths/gcd.fir +++ b/test/passes/infer-widths/gcd.fir @@ -1,4 +1,4 @@ -; RUN: firrtl -i %s -o %s.flo -x abcdefghijkl -p cT | tee %s.out | FileCheck %s +; RUN: firrtl -i %s -o %s.flo -x abcdefghijkl -p cTd | tee %s.out | FileCheck %s ;CHECK: Infer Widths circuit top : diff --git a/test/passes/infer-widths/simple.fir b/test/passes/infer-widths/simple.fir index 432030d5..50eb5452 100644 --- a/test/passes/infer-widths/simple.fir +++ b/test/passes/infer-widths/simple.fir @@ -1,4 +1,4 @@ -; RUN: firrtl -i %s -o %s.flo -x abcdefghijkl -p cT | tee %s.out | FileCheck %s +; RUN: firrtl -i %s -o %s.flo -x abcdefghijkl -p cTwd | tee %s.out | FileCheck %s ;CHECK: Infer Widths circuit top : @@ -6,6 +6,14 @@ circuit top : wire e : UInt(30) reg y : UInt y := e + + wire a : UInt(20) + wire b : UInt(10) + wire c : UInt + wire z : UInt + + z := mux(c,Pad(a,?),Pad(b,?)) + ; CHECK: Finished Infer Widths diff --git a/test/passes/jacktest/SIntOps.fir b/test/passes/jacktest/SIntOps.fir new file mode 100644 index 00000000..45ea68f2 --- /dev/null +++ b/test/passes/jacktest/SIntOps.fir @@ -0,0 +1,52 @@ +; RUN: firrtl -i %s -o %s.flo -x X -p cTwd | tee %s.out | FileCheck %s +; CHECK: Done! + +circuit SIntOps : + module SIntOps : + input b : SInt(16) + input a : SInt(16) + output addout : SInt(16) + output subout : SInt(16) + output timesout : SInt(16) + output divout : SInt(16) + output modout : SInt(16) + output lshiftout : SInt(16) + output rshiftout : SInt(16) + output lessout : UInt(1) + output greatout : UInt(1) + output eqout : UInt(1) + output noteqout : UInt(1) + output lesseqout : UInt(1) + output greateqout : UInt(1) + output negout : SInt(16) + + node T_35 = add-wrap(a, b) + addout := T_35 + node T_36 = sub-wrap(a, b) + subout := T_36 + node T_37 = mul(a, b) + node T_38 = bits(T_37, 15, 0) + timesout := T_38 + node T_39 = div(a, b) + divout := T_39 + node T_40 = div(a, b) + modout := T_40 + node T_41 = shl(a, 12) + node T_42 = bits(T_41, 15, 0) + lshiftout := T_42 + node T_43 = shr(a, 8) + rshiftout := T_43 + node T_44 = lt(a, b) + lessout := T_44 + node T_45 = gt(a, b) + greatout := T_45 + node T_46 = eq(a, b) + eqout := T_46 + node T_47 = neq(a, b) + noteqout := T_47 + node T_48 = leq(a, b) + lesseqout := T_48 + node T_49 = geq(a, b) + greateqout := T_49 + node T_50 = neg(a) + negout := T_50 diff --git a/test/passes/jacktest/UIntOps.fir b/test/passes/jacktest/UIntOps.fir new file mode 100644 index 00000000..bb3e6293 --- /dev/null +++ b/test/passes/jacktest/UIntOps.fir @@ -0,0 +1,47 @@ +; RUN: firrtl -i %s -o %s.flo -x X -p cTwd | tee %s.out | FileCheck %s +; CHECK: Done! + +circuit UIntOps : + module UIntOps : + input b : UInt(16) + input a : UInt(16) + output addout : UInt(16) + output subout : UInt(16) + output timesout : UInt(16) + output divout : UInt(16) + output modout : UInt(16) + output lshiftout : UInt(16) + output rshiftout : UInt(16) + output lessout : UInt(1) + output greatout : UInt(1) + output eqout : UInt(1) + output noteqout : UInt(1) + output lesseqout : UInt(1) + output greateqout : UInt(1) + + node T_31 = add-wrap(a, b) + addout := T_31 + node T_32 = sub-wrap(a, b) + subout := T_32 + node T_33 = mul(a, b) + timesout := T_33 + node T_34 = div(a, b) + divout := T_34 + node T_35 = div(a, b) + modout := T_35 + node T_36 = shl(a, 12) + lshiftout := T_36 + node T_37 = shr(a, 8) + rshiftout := T_37 + node T_38 = lt(a, b) + lessout := T_38 + node T_39 = gt(a, b) + greatout := T_39 + node T_40 = eq(a, b) + eqout := T_40 + node T_41 = neq(a, b) + noteqout := T_41 + node T_42 = leq(a, b) + lesseqout := T_42 + node T_43 = geq(a, b) + greateqout := T_43 diff --git a/test/passes/jacktest/gcd.fir b/test/passes/jacktest/gcd.fir index 92c6eb46..2d97ee8d 100644 --- a/test/passes/jacktest/gcd.fir +++ b/test/passes/jacktest/gcd.fir @@ -1,4 +1,4 @@ -; RUN: firrtl -i %s -o %s.flo -x X -p cw | tee %s.out | FileCheck %s +; RUN: firrtl -i %s -o %s.flo -x X -p cTwd | tee %s.out | FileCheck %s ;CHECK: To Flo circuit GCD : @@ -23,7 +23,7 @@ circuit GCD : y := b z := x node T_20 = UInt(0, 1) - node T_21 = eq(y, T_20) + node T_21 = eq(y, Pad(T_20,?)) v := T_21 ;CHECK: Finished To Flo diff --git a/test/passes/jacktest/risc.fir b/test/passes/jacktest/risc.fir index a7d35bf6..0a13e5c0 100644 --- a/test/passes/jacktest/risc.fir +++ b/test/passes/jacktest/risc.fir @@ -1,4 +1,4 @@ -; RUN: firrtl -i %s -o %s.flo -x X -p c | tee %s.out | FileCheck %s +; RUN: firrtl -i %s -o %s.flo -x X -p cTwd | tee %s.out | FileCheck %s ; CHECK: Expand Whens circuit Risc : -- cgit v1.2.3 From 7f8758420a2a46d7cf19441e9fbd1dba82cae612 Mon Sep 17 00:00:00 2001 From: azidar Date: Thu, 23 Apr 2015 11:43:11 -0700 Subject: Fixed Pad inference bug --- TODO | 8 ++++++-- src/main/stanza/passes.stanza | 2 +- test/passes/jacktest/gcd2.fir | 26 ++++++++++++++++++++++++++ 3 files changed, 33 insertions(+), 3 deletions(-) create mode 100644 test/passes/jacktest/gcd2.fir diff --git a/TODO b/TODO index 4a099d94..818b78c3 100644 --- a/TODO +++ b/TODO @@ -7,8 +7,6 @@ on-reset Parser Error if incorrectly assign stuff, like use = instead of := Update parser and update tests -Change all primops to be strict on data widths -Add pad! Make instances always male, flip the bundles on declaration dlsh,drsh move Infer-Widths to before vec expansion? @@ -32,6 +30,12 @@ Well-formed high firrtl After adding dynamic assertions, insert bounds check with accessor expansion Well-formed low firrtl All things only assigned to once +Width inference + No names + No Unknowns + All widths are positive + Pad's width is greater than value's width + pad's width is greater than value's width ======== Other Passes ======== constant folding (partial eval) pass diff --git a/src/main/stanza/passes.stanza b/src/main/stanza/passes.stanza index 588b4b73..50d2831a 100644 --- a/src/main/stanza/passes.stanza +++ b/src/main/stanza/passes.stanza @@ -1584,7 +1584,7 @@ defn gen-constraints (m:Module, h:HashTable, v:Vector) -> Mod (e:Pad) : val value-w = width!(value(e)) val pad-w = remove-unknowns-w(width(e)) - ;add(v,WGeq(pad-w, IntWidth(0))) + add(v,WGeq(pad-w, value-w)) val pad-t = match(type(e)) : (t:UIntType) : UIntType(pad-w) (t:SIntType) : SIntType(pad-w) diff --git a/test/passes/jacktest/gcd2.fir b/test/passes/jacktest/gcd2.fir new file mode 100644 index 00000000..e6700122 --- /dev/null +++ b/test/passes/jacktest/gcd2.fir @@ -0,0 +1,26 @@ +; RUN: firrtl -i %s -o %s.flo -x X -p cTwd | tee %s.out | FileCheck %s +;CHECK: To Flo +circuit GCD : + module GCD : + input b : UInt(16) + input a : UInt(16) + input e : UInt(1) + output z : UInt(16) + output v : UInt(1) + + reg x : UInt(16) + reg y : UInt(16) + node T_17 = gt(Pad(x,?), Pad(y,?)) + when T_17 : + node T_18 = sub-wrap(Pad(x,?), Pad(y,?)) + x := T_18 + else : + node T_19 = sub-wrap(Pad(y,?), Pad(x,?)) + y := T_19 + when e : + x := a + y := b + z := x + node T_20 = UInt(0, 1) + node T_21 = eq(Pad(y,?), Pad(T_20,?)) + v := T_21 -- cgit v1.2.3