Fixed performance bug in expand-when where equality between the consequence and alternate were always assumed different, causing a huge blow-up in logic

3 files changed, 78 insertions, 22 deletions

diff --git a/TODO b/TODO
index 818b78c3..614aaa85 100644
--- a/TODO
+++ b/TODO
@@ -27,6 +27,7 @@ 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
+   expression in pad must be a ground type
 After adding dynamic assertions, insert bounds check with accessor expansion
 Well-formed low firrtl
    All things only assigned to once
diff --git a/src/main/stanza/passes.stanza b/src/main/stanza/passes.stanza
index 6c347dff..4cd494df 100644
--- a/src/main/stanza/passes.stanza
+++ b/src/main/stanza/passes.stanza
@@ -1011,20 +1011,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 :
@@ -1292,7 +1297,9 @@ defn build-tables (s:Stmt,
          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:SymbolicValue) : 
+                     if c == a : c
+                     else : SVMux(pred(s),c,a)
                   (c:SymbolicValue,a:False) :
                      if kinds[i] typeof WireKind|InstanceKind|NodeKind : c
                      else : SVMux(pred(s),c,SVNul())
@@ -1300,12 +1307,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-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)
+         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)
@@ -1328,18 +1335,19 @@ defn expand-whens (m:Module) -> Module :
          stmts[name(p)] = DefWire(name(p),type(p))
          
    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-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(assign,kinds,stmts,decs,enables))
 
@@ -1404,6 +1412,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)
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,?)