Merge branch 'master' of github.com:ucb-bar/firrtl into parser

Conflicts:
	TODO
	src/main/stanza/passes.stanza

7 files changed, 210 insertions, 60 deletions

diff --git a/TODO b/TODO
index 32f0bf21..ee27c94f 100644
--- a/TODO
+++ b/TODO
@@ -6,8 +6,11 @@
 on-reset
 Make instances always male, flip the bundles on declaration
 dlsh,drsh
+<<<<<<< HEAD
 move Infer-Widths to before vec expansion?
 Add Unit Tests for each pass
+=======
+>>>>>>> 5a2a495ce88eec9e2e79cfbfe7f5548cede25874
    
 ======== Update Core ==========
 Add source locaters
@@ -24,8 +27,12 @@ Well-formed high firrtl
    UInt only has positive ints
    No combinational loops
    cannot connect to a pad, or a register. only connct to a reference
+<<<<<<< HEAD
    onreset can only handle a register
    all references are declared
+=======
+   expression in pad must be a ground type
+>>>>>>> 5a2a495ce88eec9e2e79cfbfe7f5548cede25874
 After adding dynamic assertions, insert bounds check with accessor expansion
 Well-formed low firrtl
    All things only assigned to once
@@ -38,13 +45,19 @@ Width inference
 
 ======== Other Passes ========
 constant folding (partial eval) pass
+   Get rid of unnecessary pads
+   push pad into literal
 common subexpression elimination pass
+deadcode elimination
 Verilog backend
+Eliminate skips
 
 ======== Consultations ========
 Stephen:
    width equality
       pin stephen on an example
+Patrick: 
+   move Infer-Widths to before vec expansion?
 
 ======== Think About ========
 subword accesses
@@ -57,7 +70,6 @@ Multi-streams for print statements/asserts (Jack)
 Consider def female node. (Patrick) 
 Talk to palmer/patrick about how writing passes is going to be supported
 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
@@ -103,3 +115,11 @@ Schedulable
    Nack
 Scheduler
 
+======== Notes ========
+Only for MUXES can width inference go backwards:
+  reg r : UInt<5>
+  r := MUX(p,UInt<?>(1),UInt<?>(2))
+  ==>
+  reg r : UInt<5>
+  r := MUX(p,UInt<5>(1),UInt<5>(2))
+
diff --git a/src/main/stanza/ir-utils.stanza b/src/main/stanza/ir-utils.stanza
index 507ccf94..67dfc89d 100644
--- a/src/main/stanza/ir-utils.stanza
+++ b/src/main/stanza/ir-utils.stanza
@@ -303,7 +303,7 @@ 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:DefMemory) : DefMemory(name(c),f(type(c)) as VectorType)
       (c) : c
 
 public defmulti mapr<?T> (f: Width -> Width, t:?T&Type) -> T
diff --git a/src/main/stanza/passes.stanza b/src/main/stanza/passes.stanza
index 25c18b0b..4057c3b8 100644
--- a/src/main/stanza/passes.stanza
+++ b/src/main/stanza/passes.stanza
@@ -800,6 +800,12 @@ defn lower (body:Stmt, table:HashTable<Symbol,List<KeyValue<Expression,Flip>>>)
             val exps = expand-expr(exp(e))
             val len = num-elems(type(e))
             headn(tailn(exps,len * value(e)),len)
+         (e:Pad) : 
+            val v = key(expand-expr(value(e))[0])
+            list(KeyValue(Pad(v,width(e),type(e)),DEFAULT))
+         (e:DoPrim) :
+            val args = for x in args(e) map : key(expand-expr(x)[0])
+            list(KeyValue(DoPrim(op(e),args,consts(e),type(e)),DEFAULT))
          (e) : list(KeyValue(e, DEFAULT))
 
    ;println-debug(table)
@@ -1016,20 +1022,25 @@ val one = UIntValue(1,IntWidth(1))
 defmethod equal? (e1:Expression,e2:Expression) -> True|False :
    match(e1,e2) :
       (e1:UIntValue,e2:UIntValue) : 
-         if value(e1) == value(e2) : 
-            match(width(e1), width(e2)) :
-               (w1:IntWidth,w2:IntWidth) : width(w1) == width(w2)
-               (w1,w2) : false
+         if value(e1) == value(e2) : width(e1) == width(e2)
          else : false
       (e1:SIntValue,e2:SIntValue) : 
-         if value(e1) == value(e2) : 
-            match(width(e1), width(e2)) :
-               (w1:IntWidth,w2:IntWidth) : width(w1) == width(w2)
+         if value(e1) == value(e2) : width(e1) == width(e2)
          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:Pad,e2:Pad) : width(e1) == width(e2) and value(e1) == value(e2)
+      (e1:DoPrim,e2:DoPrim) : 
+         var are-equal? = op(e1) == op(e2)
+         for (x in args(e1),y in args(e2)) do :
+            if not x == y : 
+               are-equal? = false
+         for (x in consts(e1),y in consts(e2)) do :
+            if not x == y : 
+               are-equal? = false
+         are-equal?
       (e1,e2) : false
 
 defn AND (e1:Expression,e2:Expression) -> Expression :
@@ -1351,14 +1362,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-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)
+   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(body(m),assign,resets))
 
@@ -1423,6 +1434,7 @@ defmethod equal? (w1:Width,w2:Width) -> True|False :
                   if not contains?(args(w2),w) : ret(false)
                ret(true)
       (w1:IntWidth,w2:IntWidth) : width(w1) == width(w2)
+      (w1:UnknownWidth,w2:UnknownWidth) : true
       (w1,w2) : false
 defn apply (a:Int|False,b:Int|False, f: (Int,Int) -> Int) -> Int|False :
    if a typeof Int and b typeof Int : f(a as Int, b as Int)
@@ -1784,7 +1796,7 @@ defn split-exp (c:Circuit) :
          (e:Subfield|DoPrim|Pad|ReadPort|Register|WritePort) : 
             val n* = 
                if n typeof False : gensym(`T)
-               else : to-symbol $ string-join $ [n as Symbol gensym(`#)]
+               else : to-symbol $ string-join $ [n as Symbol gensym(`#)] 
             add(v,DefNode(n*,e))
             WRef(n*,type(e),NodeKind(),UNKNOWN-GENDER)
          (e) : e
@@ -1926,8 +1938,17 @@ defn emit-all (es:Streamable, top:Symbol) :
        (ex) :            print(ex)
 
 defn emit! (e:Expression,top:Symbol) :
+   defn greater-op? (op: PrimOp) -> True|False :
+      contains?([GREATER-OP, GREATER-UU-OP, GREATER-US-OP, GREATER-SU-OP, GREATER-SS-OP], op)
+   defn greater-eq-op? (op: PrimOp) -> True|False :
+      contains?([GREATER-EQ-OP, GREATER-EQ-UU-OP, GREATER-EQ-US-OP, GREATER-EQ-SU-OP, GREATER-EQ-SS-OP], op)     
+   defn less-eq-op? (op: PrimOp) -> True|False :
+      contains?([LESS-EQ-OP, LESS-EQ-UU-OP, LESS-EQ-US-OP, LESS-EQ-SS-OP, LESS-EQ-SS-OP], op)
+   defn less-op? (op: PrimOp) -> True|False :
+      contains?([LESS-OP, LESS-UU-OP, LESS-US-OP, LESS-SS-OP, LESS-SS-OP], op)
    defn cmp-op? (op: PrimOp) -> True|False :
-      contains?([EQUAL-OP, NEQUAL-OP, GREATER-OP, LESS-EQ-OP, LESS-OP, GREATER-EQ-OP], op)
+      greater-op?(op) or greater-eq-op?(op) or less-op?(op) or less-eq-op?(op) or 
+      contains?([EQUAL-OP, EQUAL-UU-OP, EQUAL-SS-OP, NEQUAL-OP, NEQUAL-UU-OP, NEQUAL-SS-OP], op)
    match(e) :
       (e:Ref) :       emit-all([top "::" name(e)], top)
       (e:UIntValue) : emit-all([value(e) "'" sane-width(width(e))], top)
@@ -1935,18 +1956,18 @@ defn emit! (e:Expression,top:Symbol) :
       (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)
+         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)
+         emit-all(["reg'" prim-width(type(e)) " 1 " value(e)], top) ;; enable(e)
       (e:ReadPort) : 
          emit-all(["rd'" prim-width(type(e)) " " enable(e) " " mem(e) " " index(e)], top)
       (e:DoPrim) : 
          if cmp-op?(op(e)) :
            emit-all([flo-op-name(op(e)) "'" prim-width(type(args(e)[0]))], top)
-           if op(e) == GREATER-OP or op(e) == LESS-EQ-OP :
-             emit-all(["  " args(e)[1] " " args(e)[0]], top)
+           if greater-op?(op(e)) or less-eq-op?(op(e)) :
+             emit-all([" " args(e)[1] " " args(e)[0]], top)
            else :
-             emit-all(["  " args(e)[0] " " args(e)[1]], top)
+             emit-all([" " args(e)[0] " " args(e)[1]], top)
          else if op(e) == BIT-SELECT-OP :
            emit-all([flo-op-name(op(e)) "'1 " args(e)[0] " " consts(e)[0]], top)
          else if op(e) == BITS-SELECT-OP :
@@ -1966,29 +1987,40 @@ defn emit! (e:Expression,top:Symbol) :
              for const in consts(e) do :
                print(" ")
                print(const)
-      (e) : print-all(["EMIT(" e ")"])
+      (e) : error("SHOULDN'T EMIT THIS") ;; print-all(["EMIT(" e ")"])
       ;(e) : emit-all(["mov'" prim-width(type(e)) " " e], top) ;TODO, not sure which one is right
 
+defn maybe-mov (e:Expression) -> String :
+   val need-mov? = match(e) :
+      (e:Ref) :       true
+      (e:UIntValue) : true
+      (e:SIntValue) : true
+      (e:Subfield) :  true
+      (e:Index) :     true
+      (e) :           false
+   if need-mov?: "mov " else: ""
+
 defn emit-s (s:Stmt, v:List<Symbol>, top:Symbol) :
    match(s) :
       (s:DefWire) : ""
       (s:DefInstance) : error("Shouldn't be here")
       (s:DefMemory) :
-           val vtype = type(s) as VectorType
-           emit-all([top "::" name(s) " = mem'" prim-width(type(vtype)) " " size(vtype) "\n"], top)
-      (s:DefNode) : emit-all([top "::" name(s) " = " value(s) "\n"], top)
+         val vtype = type(s) as VectorType
+         emit-all([top "::" name(s) " = mem'" prim-width(type(vtype)) " " size(vtype) "\n"], top)
+      (s:DefNode) :
+         if value(s) typeof WritePort :
+            val e = value(s) as WritePort
+            val n = gensym(`F)
+            emit-all([top "::" n " = wr'" prim-width(type(e)) " " enable(e) " " mem(e) " " index(e) " " name(s) "\n"], top)
+         else :
+           emit-all([top "::" name(s) " = " maybe-mov(value(s)) value(s) "\n"], top)
       (s:Begin) : do(emit-s{_, v, top}, body(s))
       (s:Connect) : 
-         if loc(s) typeof WritePort :
-            val e = loc(s) as WritePort
-            val name = gensym(`F)
-            emit-all([top "::" name " = wr'" prim-width(type(e)) " " enable(e) " " top "::" mem(e) " " index(e) " " exp(s) "\n"], top)
+         val n = name(loc(s) as Ref)
+         if contains?(v,n) :
+            emit-all([top "::" n " = out'" prim-width(type(loc(s))) " " exp(s) "\n"], top)
          else :
-            val n = name(loc(s) as Ref)
-            if contains?(v,n) :
-               emit-all([n " = out'" prim-width(type(loc(s))) " " exp(s) "\n"], top)
-            else :
-               emit-all([top "::" n " = " exp(s) "\n"], top)
+            emit-all([top "::" n " = " maybe-mov(exp(s)) exp(s) "\n"], top)
       (s) : s 
 
 defn emit-module (m:Module) :
@@ -2039,10 +2071,3 @@ public defn run-passes (c: Circuit, p: List<Char>,file:String) :
    if contains(p,'X') or contains(p,'F') : do-stage("To Flo", emit-flo{file,_})
 
    println("Done!")
-
-
- ;;  println("Shim for Jonathan's Passes")
- ;;  c* = shim(c*)
- ;;  println("Inline Modules")
- ;;  c* = inline-modules(c*)
- ;  c*
diff --git a/src/main/stanza/primop.stanza b/src/main/stanza/primop.stanza
index 14589135..e88a6b8e 100644
--- a/src/main/stanza/primop.stanza
+++ b/src/main/stanza/primop.stanza
@@ -248,12 +248,12 @@ 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<WGeq>) -> Type :
-   defn all-equal (ls:List<Expression>) -> Width : 
-      if length(ls) == 1 : width!(ls[0])
+   defn all-equal (ls:List<Width>) -> Width : 
+      if length(ls) == 1 : (ls[0])
       else :
-         val m = MaxWidth(map(width!,ls))
+         val m = MaxWidth(ls)
          for (l in ls) do :
-            add(v,WGeq(width!(l),m))
+            add(v,WGeq(l,m))
          m
    ;defn new-width (w:Width) -> Width:
    ;   val w* = VarWidth(gensym(`w))
@@ -275,9 +275,11 @@ public defn primop-gen-constraints (e:DoPrim,v:Vector<WGeq>) -> Type :
    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-var = VarWidth(gensym(`w))
    val w* = 
       if not contains?(all-args-not-equal,op(e)) :
-         val max-args-w = all-equal(args(e))
+         val max-args-w = all-equal(map(width!,args(e)))
          switch {op(e) == _} :
             ADD-UU-OP : PlusWidth(max-args-w,IntWidth(1))
             ADD-US-OP : PlusWidth(max-args-w,IntWidth(1))
@@ -327,34 +329,36 @@ public defn primop-gen-constraints (e:DoPrim,v:Vector<WGeq>) -> Type :
             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)))
+               all-equal(List(w-var,tail(map(width!,args(e)))))
             MUX-SS-OP : 
                add(v,WGeq(width!(args(e)[0]),IntWidth(1)))
-               all-equal(tail(args(e)))
+               all-equal(List(w-var,tail(map(width!,args(e)))))
             CONCAT-OP : 
                PlusWidth(width!(args(e)[0]),width!(args(e)[1]))
+            BIT-NOT-OP : all-equal(List(w-var,map(width!,args(e))))
+            BIT-AND-OP : all-equal(List(w-var,map(width!,args(e))))
+            BIT-OR-OP :  all-equal(List(w-var,map(width!,args(e))))
+            BIT-XOR-OP : all-equal(List(w-var,map(width!,args(e))))
+            BIT-AND-REDUCE-OP : all-equal(List(w-var,map(width!,args(e))))
+            BIT-OR-REDUCE-OP : all-equal(List(w-var,map(width!,args(e))))
+            BIT-XOR-REDUCE-OP : all-equal(List(w-var,map(width!,args(e))))
+            AS-UINT-U-OP : all-equal(List(w-var,map(width!,args(e))))
+            AS-UINT-S-OP : all-equal(List(w-var,map(width!,args(e))))
+            AS-SINT-U-OP : all-equal(List(w-var,map(width!,args(e))))
+            AS-SINT-S-OP : all-equal(List(w-var,map(width!,args(e))))
 
-   val w-var = VarWidth(gensym(`w))
    add(v,WGeq(w-var,w*))
    match(type(e)) :
       (t:UIntType) : UIntType(w-var)
diff --git a/test/passes/jacktest/MemorySearch.fir b/test/passes/jacktest/MemorySearch.fir
new file mode 100644
index 00000000..955d44f2
--- /dev/null
+++ b/test/passes/jacktest/MemorySearch.fir
@@ -0,0 +1,46 @@
+; RUN: firrtl -i %s -o %s.flo -x X -p cd | tee %s.out | FileCheck %s
+; CHECK: Done!
+
+circuit MemorySearch : 
+  module MemorySearch : 
+    input target : UInt(4)
+    output address : UInt(3)
+    input en : UInt(1)
+    output done : UInt(1)
+    
+    node T_35 = UInt(0, 3)
+    reg index : UInt(3)
+    index.init := T_35
+    node T_36 = UInt(0, 1)
+    node T_37 = UInt(4, 3)
+    node T_38 = UInt(15, 4)
+    node T_39 = UInt(14, 4)
+    node T_40 = UInt(2, 2)
+    node T_41 = UInt(5, 3)
+    node T_42 = UInt(13, 4)
+    wire elts : UInt(1)[7]
+    elts.0 := Pad(T_36,?)
+    elts.1 := Pad(T_37,?)
+    elts.2 := Pad(T_38,?)
+    elts.3 := Pad(T_39,?)
+    elts.4 := Pad(T_40,?)
+    elts.5 := Pad(T_41,?)
+    elts.6 := Pad(T_42,?)
+    accessor elt = elts[index]
+    node T_43 = bit-not(en)
+    node T_44 = eq(Pad(elt,?), Pad(target,?))
+    node T_45 = UInt(7, 3)
+    node T_46 = eq(Pad(index,?), Pad(T_45,?))
+    node T_47 = bit-or(T_44, T_46)
+    node end = bit-and(T_43, T_47)
+    when en : 
+      node T_48 = UInt(0, 1)
+      index := Pad(T_48,?)
+    else : 
+      node T_49 = bit-not(end)
+      when T_49 : 
+        node T_50 = UInt(1, 1)
+        node T_51 = add-wrap(Pad(index,?), Pad(T_50,?))
+        index := Pad(T_51,?)
+    done := Pad(end,?)
+    address := Pad(index,?)
diff --git a/test/passes/jacktest/RegisterVecShift.fir b/test/passes/jacktest/RegisterVecShift.fir
new file mode 100644
index 00000000..733e2036
--- /dev/null
+++ b/test/passes/jacktest/RegisterVecShift.fir
@@ -0,0 +1,37 @@
+; RUN: firrtl -i %s -o %s.flo -x X -p cd | tee %s.out | FileCheck %s
+; CHECK: Done!
+
+circuit RegisterVecShift : 
+  module RegisterVecShift : 
+    input load : UInt(1)
+    output out : UInt(4)
+    input shift : UInt(1)
+    input ins : UInt(4)[4]
+    
+    reg delays : UInt(4)[4]
+    when reset : 
+      node T_38 = UInt(0, 4)
+      node T_39 = UInt(0, 4)
+      node T_40 = UInt(0, 4)
+      node T_41 = UInt(0, 4)
+      wire T_42 : UInt(4)[4]
+      T_42.0 := T_38
+      T_42.1 := T_39
+      T_42.2 := T_40
+      T_42.3 := T_41
+      delays := T_42
+    node T_43 = UInt(5, 3)
+    node T_44 = bit-and(Pad(T_43,?), Pad(load,?))
+    node T_45 = UInt(4, 3)
+    node T_46 = eq(Pad(T_44,?), Pad(T_45,?))
+    when T_46 : 
+      delays.0 := Pad(ins.0,?)
+      delays.1 := Pad(ins.1,?)
+      delays.2 := Pad(ins.2,?)
+      delays.3 := Pad(ins.3,?)
+    else : when shift : 
+        delays.0 := Pad(ins.0,?)
+        delays.1 := Pad(delays.0,?)
+        delays.2 := Pad(delays.1,?)
+        delays.3 := Pad(delays.2,?)
+    out := Pad(delays.3,?)
diff --git a/test/passes/jacktest/Tlb.fir b/test/passes/jacktest/Tlb.fir
new file mode 100644
index 00000000..35442ac8
--- /dev/null
+++ b/test/passes/jacktest/Tlb.fir
@@ -0,0 +1,18 @@
+; RUN: firrtl -i %s -o %s.flo -x X -p cTwd | tee %s.out | FileCheck %s
+; CHECK: Done!
+circuit Tbl : 
+  module Tbl : 
+    output o : UInt(16)
+    input i : UInt(16)
+    input d : UInt(16)
+    input we : UInt(1)
+    
+    mem m : UInt(10)[256]
+    node T_12 = UInt(0, 1)
+    o := Pad(T_12,?)
+    when we : 
+      accessor T_13 = m[i]
+      T_13 := Pad(d,?)
+    else : 
+      accessor T_14 = m[i]
+      o := Pad(T_14,?)