Finished resolve genders

9 files changed, 236 insertions, 108 deletions

diff --git a/TODO b/TODO
index e122c35c..0f31afde 100644
--- a/TODO
+++ b/TODO
@@ -1,19 +1,12 @@
 
 TODO 
-   Figure out how types and widths propogate for all updated primops
-   Write infer-types pass
+   Figure out how widths propogate for all updated primops
    Remove letrec. Add to expressions: Register(input,en), ReadPort(mem,index,enable), WritePort(mem,index,enable)
    Add bit-reduce-and etc to primops
    Write pass to rename identifiers (alpha-transform)
    Update spec
-      change concrete syntactical names of structural elements
-      change direction names for bundle fields
       add new field for sequential or combinational
-      play with non-implicit growth
-      remove generics, add all combinations (adduu, addus, addss, ...)
       add assertions
-      add convert to primop
-      remove type from node in statement
    Future questions to address in spec:
       Introduction – motivation, and intended usage
       Philosophical justifications for all constructs
diff --git a/notes/annotations/hello.c b/notes/annotations/hello.c
new file mode 100644
index 00000000..db37785d
--- /dev/null
+++ b/notes/annotations/hello.c
@@ -0,0 +1,7 @@
+#include <stdio.h>
+
+int main (int a) {
+   for( int i = 0; i < a; i++) {
+      return printf("Hello World\n");
+   }
+}
diff --git a/notes/annotations/hello.ll b/notes/annotations/hello.ll
new file mode 100644
index 00000000..3b0381e1
--- /dev/null
+++ b/notes/annotations/hello.ll
@@ -0,0 +1,30 @@
+; ModuleID = 'hello.c'
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.9.0"
+
+@.str = private unnamed_addr constant [13 x i8] c"Hello World\0A\00", align 1
+
+; Function Attrs: nounwind ssp uwtable
+define i32 @main(i32 %a) #0 {
+  %1 = icmp sgt i32 %a, 0
+  br i1 %1, label %2, label %4
+
+; <label>:2                                       ; preds = %0
+  %3 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([13 x i8]* @.str, i64 0, i64 0)) #2
+  br label %4
+
+; <label>:4                                       ; preds = %2, %0
+  %.0 = phi i32 [ %3, %2 ], [ 0, %0 ]
+  ret i32 %.0
+}
+
+; Function Attrs: nounwind
+declare i32 @printf(i8* nocapture readonly, ...) #1
+
+attributes #0 = { nounwind ssp uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { nounwind "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { nounwind }
+
+!llvm.ident = !{!0}
+
+!0 = metadata !{metadata !"Apple LLVM version 6.0 (clang-600.0.56) (based on LLVM 3.5svn)"}
diff --git a/spec/spec.tex b/spec/spec.tex
index fc8a8129..0eb6e627 100644
--- a/spec/spec.tex
+++ b/spec/spec.tex
@@ -36,31 +36,28 @@
                 &\vert &\kws{SInt}(\pd{width})                                                        &\text{Signed Integer}\\
                 &\vert &\bundleT{\pd{field*}}                                                         &\text{Bundle}\\
                 &\vert &\pds{type}[\ints]                                                             &\text{Vector}\\
-\pd{field}      &=     &\pd{side} \id \kw{:} \pd{type}                                         &\text{Bundle Field}\\
-\pd{side}       &=     &\kws{female} \vert \kws{male}                                                 &\text{Female/Male}\\
+\pd{field}      &=     &\pd{gender} \id \kw{:} \pd{type}                                              &\text{Bundle Field}\\
+\pd{gender}     &=     &\kws{female} \vert \kws{male}                                                 &\text{Gender}\\
 \pd{width}      &=     &\ints                                                                         &\text{Known Integer Width}\\
                 &\vert &\kw{?}                                                                        &\text{Unknown Width}\\
 \pd{stmt}       &=     &\info \kw{wire} \id \kw{:} \pd{type}                                          &\text{Wire Declaration}\\
                 &\vert &\info \kw{reg} \id \kw{:} \pd{type}                                           &\text{Register Declaration}\\
                 &\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{node} \id  = \pd{exp}                                               &\text{Node Declaration}\\
                 &\vert &\info \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 \kw{letrec :} \pd{elem*} \kw{in :} \pd{stmt}                            &\text{Let with Recursive Definitions}\\
                 &\vert &\info (\pd{stmt*})                                                            &\text{Statement Group}\\
                 &\vert &\info \kw{skip}                                                               &\text{Empty Statement}\\
-\pd{elem}       &=     &\info \kw{reg} \id \kw{:} \pd{type} = \kws{Register}(\pds{exp}, \pds{exp})    &\text{Structural Register}\\
-                &\vert &\info \kw{node} \id \kw{:} \pd{type} = \pd{exp}                               &\text{Structural Node}\\
-                &\vert &\info \kw{mem} \id \kw{:} \pd{type} =                                         &\text{Structural Memory}\\
-                &      &\kws{Memory}(\kws{WritePort}(\pds{exp}, \pds{exp}, \pds{exp})\text{*})  &\\
-                &\vert &\info \kw{inst} \id = \ids(\kws{Input}(\ids,\pds{exp})\text{*})               &\text{Structural Instance}\\
 \pd{exp}        &=     &\info \kws{UInt}(\ints, \pds{width})                                          &\text{Literal Unsigned Integer}\\
                 &\vert &\info \kws{SInt}(\ints, \pds{width})                                          &\text{Literal Signed Integer}\\
                 &\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}\\
 \end{array}
 \]
 \[
@@ -68,7 +65,6 @@
                 &\vert &\info \pds{pad!}(\pds{exp}, \pds{width})                                      &\text{Generic Pad to Width}\\
                 &\vert &\info \pds{pad!-u}(\pds{exp}, \pds{width})                                    &\text{Unsigned Pad to Width}\\
                 &\vert &\info \pds{pad!-s}(\pds{exp}, \pds{width})                                    &\text{Signed Pad to Width}\\
-                &\vert &\info \kws{ReadPort}(\ids, \pds{exp})                                         &\text{Structural Read Port}\\
                 &\vert &\info \pds{primop}(\pds{exp*}, \ints\text{*})                                 &\text{Primitive Operation}\\
 \pd{info}       &=     &\text{filename } \kw{:} \text{line} . \text{col}                              &\text{File Location}\\
                 &\vert &\kw{noinfo}                                                                   &\text{No File Location}\\
diff --git a/src/main/stanza/passes.stanza b/src/main/stanza/passes.stanza
index a0cf1aa3..222c386e 100644
--- a/src/main/stanza/passes.stanza
+++ b/src/main/stanza/passes.stanza
@@ -30,25 +30,25 @@ defstruct WRef <: Expression :
    name: Symbol
    type: Type [multi => false]
    kind: Kind
-   gender: Gender 
+   gender: Gender  [multi => false]
 
 defstruct WSubfield <: Expression :
    exp: Expression
    name: Symbol
    type: Type [multi => false]
-   gender: Gender
+   gender: Gender [multi => false]
 
 defstruct WIndex <: Expression :
    exp: Expression
    value: Int
    type: Type [multi => false]
-   gender: Gender
+   gender: Gender [multi => false]
 
 defstruct WDefAccessor <: Stmt :
    name: Symbol
    source: Expression
    index: Expression
-   gender: Gender
+   gender: Gender 
 
 ;================ WORKING IR UTILS =========================
 
@@ -67,6 +67,10 @@ defn to-field (p:Port) -> Field :
    else if direction(p) == INPUT : Field(name(p),MALE,type(p))
    else : Field(name(p),UNKNOWN-GENDER,type(p))
 
+defmulti gender (e:Expression) -> Gender
+defmethod gender (e:Expression) :
+   MALE ; TODO, why was this OUTPUT before? It makes sense as male, not female
+
 ;============== DEBUG STUFF =============================
 public var PRINT-TYPES : True|False = false
 public var PRINT-KINDS : True|False = false
@@ -573,110 +577,102 @@ defn infer-types (c:Circuit) -> Circuit :
 ; Because accessor gender is not known during declaration, 
 ;   this pass requires iterating until a fixed point is reached.
 
-defn resolve-accessor-genders (c:Circuit) :
-   defn resolve (body:Stmt, genders:HashTable<Symbol,Gender>) :
-      println(genders)
-      defn resolve-stmt (s:Stmt) -> Stmt :
-         match(map(resolve-expr,s)) :
-            (s:WDefAccessor) : 
-               println(genders[name(s)])
-               WDefAccessor(name(s),source(s),index(s),genders[name(s)])
-            (s) : map(resolve-stmt,s)
-      defn resolve-expr (e:Expression) -> Expression :
-         match(map(resolve-expr,e)) :
-            (e:WRef) : WRef(name(e),type(e),kind(e),genders[name(e)])
-            (e:WSubfield) : 
-               val field = for f in fields(type(e) as BundleType) find :
-                  name(f) == name(e)
-               find-expr-gender(exp(e), gender(field as Field) * desired) * gender(field as Field)
-            (e:WIndex) : find-expr-gender(exp(e),desired)
-            (e:WSubfield) : WSubfield(exp(e),name(e),type(e),genders[name(e)])
-            (e:WIndex) : WIndex(exp(e),value(e),type(e)[name(e)])
-            (e) : e
-      resolve-stmt(body)
-
-   defn find-module (m:Module, genders:HashTable<Symbol,Gender>) -> HashTable<Symbol,Gender> :
-      if find-iter(m,genders) : genders
-      else : find-module(m,genders)
-   defn find-iter (m:Module, genders:HashTable<Symbol,Gender>) -> True|False : 
+defn resolve-genders (c:Circuit) :
+   defn resolve-module (m:Module, genders:HashTable<Symbol,Gender>) -> Module :
       var done? = true
-      println(genders)
-      defn try-add (n:Symbol,g:Gender) -> Gender :
+
+      defn resolve-iter (m:Module) -> Module : 
+         val body* = resolve-stmt(body(m))
+         Module(name(m),ports(m),body*)
+
+      defn get-gender (n:Symbol,g:Gender) -> Gender :
+         defn force-gender (n:Symbol,g:Gender) -> Gender : 
+            genders[n] = g
+            done? = false
+            g
          val entry = for kv in genders find :
             key(kv) == n
          label<Gender> myret :
-            if entry == false :
-               genders[n] = g
-               done? = false
-               myret(g)
-            else :
-               val value = value(entry as KeyValue<Symbol,Gender>)
-               if value == UNKNOWN-GENDER and g == UNKNOWN-GENDER : myret(g)
-               if value != UNKNOWN-GENDER and g == UNKNOWN-GENDER : myret(value)
-               if value == UNKNOWN-GENDER and g != UNKNOWN-GENDER : 
-                  genders[n] = g
-                  done? = false
-                  myret(g)
-               if value != UNKNOWN-GENDER and g != UNKNOWN-GENDER : myret(value)
-            UNKNOWN-GENDER
+            match(entry) :
+               (e:KeyValue<Symbol,Gender>) :
+                  val value = value(e)
+                  if      value == UNKNOWN-GENDER and g == UNKNOWN-GENDER : myret(g)
+                  else if value != UNKNOWN-GENDER and g == UNKNOWN-GENDER : myret(value)
+                  else if value == UNKNOWN-GENDER and g != UNKNOWN-GENDER : myret(force-gender(n,g))
+                  else : myret(value)
+               (e:False) : myret(force-gender(n,g))
             
-      defn find-stmt (s:Stmt) -> Stmt :
+      defn resolve-stmt (s:Stmt) -> Stmt :
          match(s) :
             (s:DefWire) :
-               genders[name(s)] = BI-GENDER
+               get-gender(name(s),BI-GENDER)
+               s
             (s:DefRegister) :
-               genders[name(s)] = BI-GENDER
-            (s:DefInstance) : 
-               genders[name(s)] = MALE
-            (s:DefMemory) : 
-               genders[name(s)] = BI-GENDER
-            (s:DefNode) :
-               try-add(name(s),find-expr-gender(value(s),UNKNOWN-GENDER))
+               get-gender(name(s),BI-GENDER)
+               s
+            (s:DefMemory) :
+               get-gender(name(s),BI-GENDER)
+               s
+            (s:DefNode) : 
+               get-gender(name(s),MALE)
+               s
+            (s:DefInstance) :
+               get-gender(name(s),FEMALE)
+               DefInstance(name(s),resolve-expr(module(s),FEMALE))
             (s:WDefAccessor) : 
-               find-expr-gender(index(s),MALE)
-               val sourcegender = find-expr-gender(source(s),try-add(name(s),UNKNOWN-GENDER))
-               val mygender = try-add(name(s),sourcegender)
-               println-all(["For " name(s) " got " mygender])
-               mygender
+               val gender* = get-gender(name(s),UNKNOWN-GENDER)
+               val index* = resolve-expr(index(s),MALE)
+               val source* = resolve-expr(source(s),gender*)
+               WDefAccessor(name(s),source*,index*,gender*)
             (s:Connect) : 
-               find-expr-gender(loc(s),FEMALE)
-               find-expr-gender(exp(s),MALE)
+               Connect(resolve-expr(loc(s),FEMALE),resolve-expr(exp(s),MALE))
             (s:Conditionally) :
-               find-expr-gender(pred(s),MALE)
-            (s) : s
-         map(find-stmt,s)
+               val pred* = resolve-expr(pred(s),MALE)
+               val conseq* = resolve-stmt(conseq(s))
+               val alt* = resolve-stmt(conseq(s))
+               Conditionally(pred*,conseq*,alt*)
+            (s) : map(resolve-stmt,s)
 
-      defn find-expr-gender (e:Expression,desired:Gender) -> Gender :
+      defn resolve-expr (e:Expression,desired:Gender) -> Expression :
+         defn bundle-field-gender (n:Symbol,t:Type) -> Gender :
+            match(t) :
+               (b:BundleType) : 
+                   val field = for f in fields(b) find :
+                                  name(f) == n
+                   match(field):
+                            (f:Field) : gender(f)
+                            (f) : UNKNOWN-GENDER
+               (b) : UNKNOWN-GENDER
+            
          match(e) :
             (e:WRef) : 
-               val added = try-add(name(e),desired)
-               if added == BI-GENDER :
-                  desired
-               else : added
+               val gender = get-gender(name(e),desired)
+               WRef{name(e),type(e),kind(e),_} $
+                  if gender == BI-GENDER : desired
+                  else : gender
             (e:WSubfield) : 
-               val field = for f in fields(type(e) as BundleType) find :
-                  name(f) == name(e)
-               find-expr-gender(exp(e), gender(field as Field) * desired) * gender(field as Field)
-            (e:WIndex) : find-expr-gender(exp(e),desired)
-            (e:UIntValue) : MALE
-            (e:SIntValue) : MALE
-            (e:DoPrim) : MALE
-            (e:ReadPort) : MALE
-            (e:Null) : MALE
-            (e) : MALE
-
-      for p in ports(m) do :
-         genders[name(p)] = gender(to-field(p))
-      find-stmt(body(m))
-      done?
+               val field-gender = bundle-field-gender(name(e),type(exp(e)))
+               val exp* = resolve-expr(exp(e),field-gender * desired)
+               val gender* = field-gender * gender(exp*)
+               WSubfield(exp*,name(e),type(e),gender*)
+            (e:WIndex) : 
+               val exp* = resolve-expr(exp(e),desired)
+               val gender* = gender(exp*)
+               WIndex(exp*,value(e),type(e),gender*)
+            (e) : map(resolve-expr{_,desired},e)
+
+      var module* = resolve-iter(m)
+      while not done? : 
+        done? = true
+        module* = resolve-iter(m)
+      module*
     
    defn resolve-genders (m:Module, c:Circuit) -> Module :
       val genders = HashTable<Symbol,Gender>(symbol-hash)
       for m in modules(c) do :
-         genders[name(m)] = FEMALE ;; TODO Should I add this?
-      find-module(m,genders)
-      val body* = resolve(body(m),genders)
-      Module(name(m),ports(m),body*)
+         genders[name(m)] = FEMALE
+      resolve-module(m,genders)
+      
 
    Circuit(modules*, main(c)) where :
       val modules* = 
@@ -2014,7 +2010,7 @@ public defn run-passes (c: Circuit, p: List<Char>) :
    if contains(p,'c') : do-stage("Make Explicit Reset", make-explicit-reset)
    if contains(p,'d') : do-stage("Initialize Registers", initialize-registers)
    if contains(p,'e') : do-stage("Infer Types", infer-types)
-   if contains(p,'f') : do-stage("Resolve Accessor Genders", resolve-accessor-genders)
+   if contains(p,'f') : do-stage("Resolve Genders", resolve-genders)
    ;if contains(p,'g') : do-stage("Expand Accessors", expand-accessors)
    ;if contains(p,'h') : do-stage("Flatten Bundles", flatten-bundles)
    ;if contains(p,'i') : do-stage("Expand Bundles", expand-bundles)
diff --git a/test/passes/resolve-genders/accessor.fir b/test/passes/resolve-genders/accessor.fir
new file mode 100644
index 00000000..c6e2a905
--- /dev/null
+++ b/test/passes/resolve-genders/accessor.fir
@@ -0,0 +1,19 @@
+; RUN: firrtl %s abcdef cg | tee %s.out | FileCheck %s
+
+;CHECK: Resolve Genders
+circuit top :
+   module top :
+      wire m : UInt(32)[10][10][10]
+      wire i : UInt
+      accessor a = m[i] ;CHECK: accessor a = m@<g:male>[i@<g:male>]@<g:male>
+      accessor b = a[i] ;CHECK: accessor b = a@<g:male>[i@<g:male>]@<g:male>
+      accessor c = b[i] ;CHECK: accessor c = b@<g:male>[i@<g:male>]@<g:male>
+      wire j : UInt
+      j := c
+
+      accessor x = m[i] ;CHECK: accessor x = m@<g:female>[i@<g:male>]@<g:female>
+      accessor y = x[i] ;CHECK: accessor y = x@<g:female>[i@<g:male>]@<g:female>
+      accessor z = y[i] ;CHECK: accessor z = y@<g:female>[i@<g:male>]@<g:female>
+      z := j
+
+; CHECK: Finished Resolve Genders
diff --git a/test/passes/resolve-genders/bulk.fir b/test/passes/resolve-genders/bulk.fir
new file mode 100644
index 00000000..0276715f
--- /dev/null
+++ b/test/passes/resolve-genders/bulk.fir
@@ -0,0 +1,14 @@
+; RUN: firrtl %s abcdef cg | tee %s.out | FileCheck %s
+
+;CHECK: Resolve Genders
+circuit top :
+   module source :
+      output bundle : { male data : UInt(16), female ready : UInt(1) }
+   module sink :
+      input bundle : { male data : UInt(16), female ready : UInt(1) }
+   module top :
+      inst src of source
+      inst snk of sink
+      snk.bundle := src.bundle
+
+; CHECK: Finished Resolve Genders
diff --git a/test/passes/resolve-genders/gcd.fir b/test/passes/resolve-genders/gcd.fir
new file mode 100644
index 00000000..7e0a22c0
--- /dev/null
+++ b/test/passes/resolve-genders/gcd.fir
@@ -0,0 +1,52 @@
+; RUN: firrtl %s abcdef cg | tee %s.out | FileCheck %s
+
+;CHECK: Resolve Genders
+circuit top :
+   module subtracter :
+      input x : UInt
+      input y : UInt
+      output z : UInt
+      z := sub-wrap(x, y)
+      ;CHECK: z@<g:female> := sub-wrap(x@<g:male>, y@<g:male>)
+   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
+; CHECK: reg x : UInt
+      x.init := UInt(0)
+      y.init := UInt(42)
+      when gt(x, y) :
+      ;CHECK: when gt(x@<g:male>, y@<g:male>) :
+         inst s of subtracter
+         ;CHECK: inst s of subtracter@<g:female>
+         s.x := x
+         s.y := y
+         x := s.z
+         ;CHECK: s@<g:female>.x@<g:female> := x@<g:male>
+         ;CHECK: s@<g:female>.y@<g:female> := y@<g:male>
+         ;CHECK: x@<g:female> := s@<g:female>.z@<g:male>
+      else :
+         inst s2 of subtracter
+         s2.x := x
+         s2.y := y
+         y := s2.z
+      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 Resolve Genders
diff --git a/test/passes/resolve-genders/ports.fir b/test/passes/resolve-genders/ports.fir
new file mode 100644
index 00000000..ea92cd24
--- /dev/null
+++ b/test/passes/resolve-genders/ports.fir
@@ -0,0 +1,21 @@
+; RUN: firrtl %s abcdef cg | tee %s.out | FileCheck %s
+
+;CHECK: Resolve Genders
+circuit top :
+   module source :
+      output data : UInt(16)
+      input ready : UInt(1)
+      data := UInt(16)
+   module sink :
+      input data : UInt(16)
+      output ready : UInt(1)
+   module top: 
+      wire connect : { male data : UInt(16), female ready: UInt(1) }
+      inst src of source         ;CHECK: inst src of source@<g:female>
+      inst snk of sink           ;CHECK: inst snk of sink@<g:female>
+      connect.data := src.data   ;CHECK: connect@<g:female>.data@<g:female> := src@<g:female>.data@<g:male>
+      src.ready := connect.ready ;CHECK: src@<g:female>.ready@<g:female> := connect@<g:female>.ready@<g:male>
+      snk.data := connect.data   ;CHECK: snk@<g:female>.data@<g:female> := connect@<g:male>.data@<g:male>
+      connect.ready := snk.ready ;CHECK: connect@<g:male>.ready@<g:female> := snk@<g:female>.ready@<g:male>
+
+; CHECK: Finished Resolve Genders