defpackage firrtl/passes :
  import core
  import verse
  import firrtl/ir2
  import firrtl/ir-utils
  import firrtl/primops
  import firrtl-main
  import firrtl/errors

;============== Pass List ================
public val standard-passes = to-list $ [
   CheckHighForm(expand-delin)
   TempElimination()
   ToWorkingIR()
   MakeExplicitReset()
   ResolveKinds()
   CheckKinds()
   InferTypes()
   CheckTypes()
   ResolveGenders()
   CheckGenders()
   ExpandAccessors()
   LowerToGround()
   ExpandIndexedConnects()
   ExpandWhens()
   InferWidths()
   Inline()
   SplitExp()
   ToRealIR() ]
;=============== WORKING IR ================================
public definterface Kind
public defstruct WireKind <: Kind 
public defstruct RegKind <: Kind
public defstruct InstanceKind <: Kind
public defstruct ReadAccessorKind <: Kind 
public defstruct WriteAccessorKind <: Kind 
public defstruct PortKind <: Kind
public defstruct NodeKind <: Kind ; All elems except structural memory, wires
public defstruct MemKind <: Kind
public defstruct ModuleKind <: Kind
public defstruct AccessorKind <: Kind

public definterface Gender
public val MALE = new Gender
public val FEMALE = new Gender
public val UNKNOWN-GENDER = new Gender
public val BI-GENDER = new Gender

public defstruct WRef <: Expression :
   name: Symbol
   type: Type with: (as-method => true)
   kind: Kind
   gender: Gender  with: (as-method => true)

public defstruct WSubfield <: Expression :
   exp: Expression
   name: Symbol
   type: Type with: (as-method => true)
   gender: Gender with: (as-method => true)

public defstruct WIndex <: Expression :
   exp: Expression
   value: Int
   type: Type with: (as-method => true)
   gender: Gender with: (as-method => true)

public defstruct WDefAccessor <: Stmt :
   info: FileInfo with: (as-method => true)
   name: Symbol
   source: Expression
   index: Expression
   gender: Gender 

defstruct ConnectToIndexed <: Stmt :
   info: FileInfo with: (as-method => true)
   index: Expression
   locs: List<Expression>
   exp: Expression

defstruct ConnectFromIndexed <: Stmt :
   info: FileInfo with: (as-method => true)
   index: Expression
   loc: Expression
   exps: List<Expression>


;================ WORKING IR UTILS =========================
;defmethod equal? (f1:Flip, f2:Flip) -> True|False :
;   switch fn ([x,y]) : f1 == x and f2 == y :
;      [DEFAULT,DEFAULT] : true
;      [REVERSE,REVERSE] : true
;      else : false

defn plus (g1:Gender,g2:Gender) -> Gender :
   switch fn ([x,y]) : g1 == x and g2 == y :
      [FEMALE,MALE]   : UNKNOWN-GENDER
      [MALE,FEMALE]   : UNKNOWN-GENDER
      [MALE,MALE]     : MALE
      [FEMALE,FEMALE] : FEMALE
      [BI-GENDER,MALE] : MALE
      [BI-GENDER,FEMALE] : FEMALE
      [MALE,BI-GENDER] : MALE
      [FEMALE,BI-GENDER] : FEMALE

defn swap (g:Gender) -> Gender :
   switch {_ == g} :
      UNKNOWN-GENDER : UNKNOWN-GENDER
      MALE : FEMALE
      FEMALE : MALE
      BI-GENDER : BI-GENDER

defn swap (f:Flip) -> Flip :
   switch {_ == f} :
      DEFAULT : REVERSE
      REVERSE : DEFAULT

defn swap (d:Direction) -> Direction :
   switch {_ == d} :
      OUTPUT : INPUT
      INPUT : OUTPUT

public defn times (flip:Flip,d:Direction) -> Direction : flip * d
public defn times (d:Direction,flip:Flip) -> Direction :
   switch {_ == flip} :
      DEFAULT : d
      REVERSE : swap(d)

public defn times (g:Gender,flip:Flip) -> Gender : flip * g
public defn times (flip:Flip,g:Gender) -> Gender :
   switch {_ == flip} :
      DEFAULT : g
      REVERSE : swap(g)

public defn times (f1:Flip,f2:Flip) -> Flip :
   switch {_ == f2} :
      DEFAULT : f1
      REVERSE : swap(f1)
     
defn to-field (p:Port) -> Field :
   if direction(p) == OUTPUT : Field(name(p),DEFAULT,type(p))
   else if direction(p) == INPUT : Field(name(p),REVERSE,type(p))
   else : error("Shouldn't be here")

defn to-dir (g:Gender) -> Direction :
   switch {_ == g} :
      MALE : INPUT
      FEMALE : OUTPUT

defmulti gender (e:Expression) -> Gender
defmethod gender (e:Expression) :
   MALE

defmethod print (o:OutputStream, g:Gender) :
   print{o, _} $
   switch {g == _} :
      MALE : "m"
      FEMALE: "f"
      BI-GENDER : "b"
      UNKNOWN-GENDER: "u"

defmethod info (stmt:Begin) -> FileInfo : FileInfo()
defmethod info (stmt:EmptyStmt) -> FileInfo : FileInfo()

defmethod type (exp:UIntValue) -> Type : UIntType(width(exp))
defmethod type (exp:SIntValue) -> Type : SIntType(width(exp))

;============== DEBUG STUFF =============================
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
public var PRINT-DEBUG : True|False = false
public var PRINT-INFO : 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) :
      (k:WireKind) : "wire"
      (k:RegKind) : "reg"
      (k:AccessorKind) : "accessor"
      (k:PortKind) : "port"
      (k:MemKind) : "mem"
      (k:NodeKind) : "n"
      (k:ModuleKind) : "module"
      (k:InstanceKind) : "inst"
      (k:ReadAccessorKind) : "racc"
      (k:WriteAccessorKind) : "wacc"

defn hasGender (e:?) :
   e typeof WRef|WSubfield|WIndex|WDefAccessor

defn hasWidth (e:?) :
   e typeof UIntType|SIntType|UIntValue|SIntValue

defn hasType (e:?) :
   e typeof Ref|Subfield|Index|DoPrim|WritePort|ReadPort|WRef|WSubfield
      |WIndex|DefWire|DefRegister|DefMemory|Register
      |VectorType|Port|Field

defn hasKind (e:?) :
   e typeof WRef

defn hasInfo (e:?) :
   e typeof Stmt|Port|Circuit|Module

defn any-debug? (e:?) :
   (hasGender(e) and PRINT-GENDERS) or
   (hasType(e) and PRINT-TYPES) or
   (hasWidth(e) and PRINT-WIDTHS) or
   (hasKind(e) and PRINT-KINDS) or
   (hasInfo(e) and PRINT-INFO)

defmethod print-debug (o:OutputStream, e:Expression|Stmt|Type|Port|Field|Module|Circuit) :
   defn wipe-width (t:Type) -> Type : 
     match(t) :
        (t:UIntType) : UIntType(UnknownWidth())
        (t:SIntType) : SIntType(UnknownWidth())
        (t) : t
      
   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 ?) ">"])
   if PRINT-INFO and hasInfo(e): print-all(o,["<i:" info(e as ?) ">"])
      
defmethod print (o:OutputStream, e:WRef) :
   print(o,name(e))
   print-debug(o,e as ?)

defmethod print (o:OutputStream, e:WSubfield) :
   print-all(o,[exp(e) "." name(e)])
   print-debug(o,e as ?)

defmethod print (o:OutputStream, e:WIndex) :
   print-all(o,[exp(e) "[" value(e) "]"])
   print-debug(o,e as ?)

defmethod print (o:OutputStream, s:WDefAccessor) :
   print-all(o,["accessor " name(s) " = " source(s) "[" index(s) "]"])
   print-debug(o,s)

defmethod print (o:OutputStream, c:ConnectToIndexed) :
   print-all(o, [locs(c) "[" index(c) "] := " exp(c)])
   print-debug(o,c as ?)

defmethod print (o:OutputStream, c:ConnectFromIndexed) :
   print-all(o, [loc(c) " := " exps(c) "[" index(c) "]" ])
   print-debug(o,c as ?)

defmethod map (f: Expression -> Expression, e: WSubfield) :
   WSubfield(f(exp(e)), name(e), type(e), gender(e))
defmethod map (f: Expression -> Expression, e: WIndex) :
   WIndex(f(exp(e)), value(e), type(e), gender(e))

defmethod map (f: Expression -> Expression, c:WDefAccessor) :
   WDefAccessor(info(c),name(c), f(source(c)), f(index(c)), gender(c))
defmethod map (f: Expression -> Expression, c:ConnectToIndexed) :
   ConnectToIndexed(info(c),f(index(c)), map(f, locs(c)), f(exp(c)))
defmethod map (f: Expression -> Expression, c:ConnectFromIndexed) :
   ConnectFromIndexed(info(c),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: 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))

;================= Temporary Variable Elimination ========================
; Returns a new Circuit where temporary variables are removed and returns
;   the resulting nested expression
public defstruct TempElimination <: Pass
public defmethod pass (b:TempElimination) -> (Circuit -> Circuit) : temp-elimination
public defmethod name (b:TempElimination) -> String : "Temp Elimination"
public defmethod short-name (b:TempElimination) -> String : "temp-elim"

defn temp-elimination (c:Circuit) :
   val h = HashTable<Symbol,Expression>(symbol-hash)
   defn is-temp? (n:Symbol) -> True|False :
      to-string(n)[0] == 'T'
   defn temp-elim-e (e:Expression) :
      match(map(temp-elim-e,e)) :
         (e:Ref) : 
            if key?(h,name(e)) : h[name(e)]
            else : e
         (e) : e
   defn temp-elim-s (s:Stmt) :
      match(map(temp-elim-e,s)) :
         (s:DefNode) : 
            if is-temp?(name(s)) :
               h[name(s)] = value(s)
               EmptyStmt()
            else : s
         (s) : map(temp-elim-s,s)

   Circuit(info(c),modules*, main(c)) where :
      val modules* =
         for m in modules(c) map :
            match(m) :
               (m:InModule) : InModule(info(m),name(m), ports(m), temp-elim-s(body(m)))
               (m:ExModule) : m

;================= Bring to Working IR ========================
; Returns a new Circuit with Refs, Subfields, Indexes and DefAccessors 
;   replaced with IR-internal nodes that contain additional 
;   information (kind, gender)
public defstruct ToWorkingIR <: Pass
public defmethod pass (b:ToWorkingIR) -> (Circuit -> Circuit) : to-working-ir
public defmethod name (b:ToWorkingIR) -> String : "Working IR"
public defmethod short-name (b:ToWorkingIR) -> String : "to-working-ir"

defn to-working-ir (c:Circuit) :
   defn to-exp (e:Expression) :
      match(map(to-exp,e)) :
         (e:Ref) : WRef(name(e), type(e), NodeKind(), UNKNOWN-GENDER)
         (e:Subfield) : WSubfield(exp(e), name(e), type(e), UNKNOWN-GENDER)
         (e:Index) : WIndex(exp(e), value(e), type(e), UNKNOWN-GENDER)
         (e) : e
   defn to-stmt (s:Stmt) :
      match(map(to-exp,s)) :
         (s:DefAccessor) : WDefAccessor(info(s),name(s),source(s),index(s), UNKNOWN-GENDER)
         (s) : map(to-stmt,s)

   Circuit(info(c),modules*, main(c)) where :
      val modules* =
         for m in modules(c) map :
            match(m) :
               (m:InModule) : InModule(info(m),name(m), ports(m), to-stmt(body(m)))
               (m:ExModule) : m

;=============== MAKE EXPLICIT RESET =======================
; All modules have an implicit reset signal - however, the 
;   programmer can explicitly reference this signal if desired.
;   This pass makes all implicit resets explicit while
;   preserving any previously explicit resets
; If reset is not explicitly passed to instantiations, then this
;   pass autmatically connects the parent module's reset to the
;   instantiation's reset
public defstruct MakeExplicitReset <: Pass
public defmethod pass (b:MakeExplicitReset) -> (Circuit -> Circuit) : make-explicit-reset
public defmethod name (b:MakeExplicitReset) -> String : "Make Explicit Reset"
public defmethod short-name (b:MakeExplicitReset) -> String : "make-explicit-reset"

defn make-explicit-reset (c:Circuit) :
   defn find-explicit (c:Circuit) -> List<Symbol> :
      defn explicit? (m:Module) -> True|False :
         for p in ports(m) any? :
            name(p) == `reset
      val explicit-reset = Vector<Symbol>()
      for m in modules(c) do:
         if explicit?(m) : add(explicit-reset,name(m))
      to-list(explicit-reset)

   defn make-explicit (m:Module, explicit-reset:List<Symbol>) -> Module :
      defn route-reset (s:Stmt) -> Stmt :
         match(s) :
            (s:DefInstance) : 
               val iref = WSubfield(WRef(name(s), UnknownType(), InstanceKind(), UNKNOWN-GENDER),`reset,UnknownType(),UNKNOWN-GENDER)
               val pref = WRef(`reset, UnknownType(), PortKind(), MALE)
               Begin(to-list([s,Connect(info(s),iref,pref)]))
            (s) : map(route-reset,s)

      var ports! = ports(m)
      if not contains?(explicit-reset,name(m)) :
         ports! = append(ports(m),list(Port(FileInfo(),`reset,INPUT,UIntType(IntWidth(1)))))
      match(m) :
         (m:InModule) : 
            val body! = route-reset(body(m))
            InModule(info(m),name(m),ports!,body!)
         (m:ExModule) : ExModule(info(m),name(m),ports!)
      
   defn make-explicit-reset (m:Module, c:Circuit) -> Module :
      val explicit-reset = find-explicit(c)
      make-explicit(m,explicit-reset)

   Circuit(info(c),modules*, main(c)) where :
      val modules* = 
         for m in modules(c) map :
            make-explicit-reset(m,c)

;=============== Resolve Kinds =============================
; It is useful for the compiler to know information about 
;   objects referenced. This information is stored in the kind
;   field in WRef. This pass walks the graph and returns a new
;   Circuit where all WRef kinds are resolved
public defstruct ResolveKinds <: Pass
public defmethod pass (b:ResolveKinds) -> (Circuit -> Circuit) : resolve-kinds
public defmethod name (b:ResolveKinds) -> String : "Resolve Kinds"
public defmethod short-name (b:ResolveKinds) -> String : "resolve-kinds"

defn resolve-kinds (c:Circuit) :
   defn resolve (body:Stmt, kinds:HashTable<Symbol,Kind>) :
      defn resolve-stmt (s:Stmt) -> Stmt :
         map{resolve-expr,_} $
         map(resolve-stmt,s)

      defn resolve-expr (e:Expression) -> Expression :
         match(e) :
            (e:WRef) : WRef(name(e),type(e),kinds[name(e)],gender(e))
            (e) : map(resolve-expr,e)

      resolve-stmt(body)

   defn find (m:Module, kinds:HashTable<Symbol,Kind>) :
      defn find-stmt (s:Stmt) -> Stmt :
         match(s) :
            (s:DefWire) : kinds[name(s)] = NodeKind()
            (s:DefNode) : kinds[name(s)] = NodeKind()
            (s:DefRegister) : kinds[name(s)] = RegKind()
            (s:DefInstance) : kinds[name(s)] = InstanceKind()
            (s:DefMemory) : kinds[name(s)] = MemKind()
            (s:WDefAccessor) : kinds[name(s)] = AccessorKind()
            (s) : false
         map(find-stmt,s)

      kinds[name(m)] = ModuleKind()
      for p in ports(m) do :
         kinds[name(p)] = PortKind()
      match(m) : 
         (m:InModule) : find-stmt(body(m))
         (m:ExModule) : false
    
   defn resolve-kinds (m:Module, c:Circuit) -> Module :
      val kinds = HashTable<Symbol,Kind>(symbol-hash)
      for m in modules(c) do :
         kinds[name(m)] = ModuleKind()
      find(m,kinds)   
      match(m) : 
         (m:InModule) : 
            val body! = resolve(body(m),kinds)
            InModule(info(m),name(m),ports(m),body!)
         (m:ExModule) : ExModule(info(m),name(m),ports(m))

   Circuit(info(c),modules*, main(c)) where :
      val modules* = 
         for m in modules(c) map :
            resolve-kinds(m,c)

;============== INFER TYPES ================================
; This pass infers the type field in all IR nodes by updating
;   and passing an environment to all statements in pre-order
;   traversal, and resolving types in expressions in post-
;   order traversal.
; Type propagation for primary ops are defined here.
; Notable cases: LetRec requires updating environment before
;   resolving the subexpressions in its elements.
; Type errors are not checked in this pass, as this is
;   postponed for a later/earlier pass.
public defstruct InferTypes <: Pass
public defmethod pass (b:InferTypes) -> (Circuit -> Circuit) : infer-types
public defmethod name (b:InferTypes) -> String : "Infer Types"
public defmethod short-name (b:InferTypes) -> String : "infer-types"

defn type (m:Module) -> Type : 
   BundleType(for p in ports(m) map : to-field(p))

defn get-type (b:Symbol,l:List<KeyValue<Symbol,Type>>) -> Type :
   val ma  = for kv in l find : b == key(kv)
   if ma != false : 
      val ret = value(ma as KeyValue<Symbol,Type>)
      ret
   else :
      UnknownType()

defn bundle-field-type (v:Type,s:Symbol) -> Type :
   match(v) :
      (v:BundleType) : 
         val ft = for p in fields(v) find : name(p) == s
         if ft != false : type(ft as Field)
         else : UnknownType()
      (v) : UnknownType()

defn get-vector-subtype (v:Type) -> Type :
   match(v) :
      (v:VectorType) : type(v)
      (v) : UnknownType()

defn infer-exp-types (e:Expression, l:List<KeyValue<Symbol,Type>>) -> Expression :
   val r = map(infer-exp-types{_,l},e)
   match(r) :
      (e:WRef) : WRef(name(e), get-type(name(e),l),kind(e),gender(e))
      (e:WSubfield) : WSubfield(exp(e),name(e), bundle-field-type(type(exp(e)),name(e)),gender(e))
      (e:WIndex) : WIndex(exp(e),value(e), get-vector-subtype(type(exp(e))),gender(e))
      (e:DoPrim) : lower-and-type-primop(e)
         ;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:UIntValue|SIntValue) : e

defn infer-types (s:Stmt, l:List<KeyValue<Symbol,Type>>) -> [Stmt List<KeyValue<Symbol,Type>>] :
   match(map(infer-exp-types{_,l},s)) :
      (s:Begin) : 
         var env = l
         val body* = 
            for s in body(s) map :
               val [s*,l*] = infer-types(s,env)
               env = l*
               s*
         [Begin(body*),env]
      (s:DefWire) : [s,List(name(s) => type(s),l)]
      (s:DefRegister) : [s,List(name(s) => type(s),l)]
      (s:DefMemory) : [s,List(name(s) => type(s),l)]
      (s:DefInstance) : [s, List(name(s) => type(module(s)),l)]
      (s:DefNode) : [s, List(name(s) => type(value(s)),l)]
      (s:WDefAccessor) : [s, List(name(s) => get-vector-subtype(type(source(s))),l)]
      (s:Conditionally) : 
        val [s*,l*] = infer-types(conseq(s),l)
        val [s**,l**] = infer-types(alt(s),l)
        [Conditionally(info(s),pred(s),s*,s**),l]
      (s:Connect|BulkConnect|OnReset|EmptyStmt) : [s,l]

defn infer-types (m:Module, l:List<KeyValue<Symbol,Type>>) -> Module :
   val ptypes = 
      for p in ports(m) map :
         name(p) => type(p)
   println-all-debug(append(ptypes,l))
   match(m) :
      (m:InModule) :
         val [s,l*] = infer-types(body(m),append(ptypes, l))
         InModule(info(m),name(m),ports(m),s)
      (m:ExModule) : m

defn infer-types (c:Circuit) -> Circuit :
   val l = 
      for m in modules(c) map :
         name(m) => BundleType(map(to-field,ports(m)))
   println-all-debug(l)
   Circuit{info(c), _, main(c) } $ 
      for m in modules(c) map :
         infer-types(m,l)
    
;============= RESOLVE ACCESSOR GENDER  ============================
; To ensure a proper circuit, we must ensure that assignments
;   only work on expressions that can be assigned to. Similarly,
;   we must ensure that only expressions that can be read from
;   are used to assign from. This invariant requires each 
;   expression's gender to be inferred.
; Various elements can be bi-gender (e.g. wires) and can 
;   thus be treated as either female or male. Conversely, some
;   elements are single-gender (e.g. accessors, ports). 
; Because accessor gender is not known during declaration, 
;   this pass requires iterating until a fixed point is reached.
public defstruct ResolveGenders <: Pass
public defmethod pass (b:ResolveGenders) -> (Circuit -> Circuit) : resolve-genders
public defmethod name (b:ResolveGenders) -> String : "Resolve Genders"
public defmethod short-name (b:ResolveGenders) -> String : "resolve-genders"

; Notes
; Is there a case where an incorrect gender would cause a weird result in resolving an accessor gender, such that a following gender check is wrong/right which it shouldn't be?

; I don't think so, because there is no way for resolving an accessor gender to change something from wrong -> right, so it will always fail in the gender check.
; As such, it doesn't matter what the accessor gender gets resolved to, as it will fail anyways

; In the example below, FIRRTL will say accessor gender could not be resolved. Once this is fixed, then we will error "Cannot connect from an output, out"
;    output out : UInt
;    accessor x = m[i]
;    x := out
;    out := x

defn bundle-field-flip (n:Symbol,t:Type) -> Flip :
   match(t) :
      (b:BundleType) : 
          val field = for f in fields(b) find : name(f) == n
          match(field):
                   (f:Field) : flip(f)
                   (f) : error(string-join(["Could not find " n " in bundle "]))
      (b) : error(string-join(["Accessing subfield " n " on a non-Bundle type."]))

defn resolve-genders (c:Circuit) :
   defn resolve-module (m:Module, genders:HashTable<Symbol,Gender>) -> Module :
      var done? = true

      defn resolve-iter (m:Module) -> Module : 
         match(m) :
            (m:InModule) :
               val body* = resolve-stmt(body(m))
               InModule(info(m),name(m),ports(m),body*)
            (m:ExModule) : m

      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
         match(entry) :
            (e:KeyValue<Symbol,Gender>) :
               val value = value(e)
               if      value == UNKNOWN-GENDER and g == UNKNOWN-GENDER : g
               else if value != UNKNOWN-GENDER and g == UNKNOWN-GENDER : value
               else if value == UNKNOWN-GENDER and g != UNKNOWN-GENDER : force-gender(n,g)
               else : value
            (e:False) : force-gender(n,g)
            
      defn resolve-stmt (s:Stmt) -> Stmt :
         match(s) :
            (s:DefWire) :
               get-gender(name(s),BI-GENDER)
               s
            (s:DefRegister) :
               get-gender(name(s),BI-GENDER)
               s
            (s:DefMemory) :
               get-gender(name(s),BI-GENDER)
               s
            (s:DefNode) : 
               DefNode(info(s),name(s),resolve-expr(value(s),get-gender(name(s),MALE)))
            (s:DefInstance) :
               get-gender(name(s),MALE)
               DefInstance(info(s),name(s),resolve-expr(module(s),MALE))
            (s:WDefAccessor) : 
               val gender* = get-gender(name(s),UNKNOWN-GENDER)
               val index* = resolve-expr(index(s),MALE)
               val source* = resolve-expr(source(s),gender*)
               WDefAccessor(info(s),name(s),source*,index*,gender*)
            (s:Connect) : 
               Connect(info(s),resolve-expr(loc(s),FEMALE),resolve-expr(exp(s),MALE))
            (s:BulkConnect) : 
               BulkConnect(info(s),resolve-expr(loc(s),FEMALE),resolve-expr(exp(s),MALE))
            (s:OnReset) : 
               OnReset(info(s),resolve-expr(loc(s),FEMALE),resolve-expr(exp(s),MALE))
            (s:Conditionally) :
               val pred* = resolve-expr(pred(s),MALE)
               val conseq* = resolve-stmt(conseq(s))
               val alt* = resolve-stmt(alt(s))
               Conditionally(info(s),pred*,conseq*,alt*)
            (s) : map(resolve-stmt,s)

      defn resolve-expr (e:Expression,desired:Gender) -> Expression :
         match(e) :
            (e:WRef) : 
               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-flip = bundle-field-flip(name(e),type(exp(e)))
               val exp* = resolve-expr(exp(e),field-flip * desired)
               val gender* = field-flip * 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{_,MALE},e)

      var module* = resolve-iter(m)
      println-debug(genders)
      while not done? : 
        done? = true
        module* = resolve-iter(m)
        ;println-debug(genders)
      module*
    
   defn resolve-genders (m:Module, c:Circuit) -> Module :
      val genders = HashTable<Symbol,Gender>(symbol-hash)
      resolve-module(m,genders)

   Circuit(info(c),modules*, main(c)) where :
      val modules* = 
         for m in modules(c) map :
            resolve-genders(m,c)

;;============== EXPAND ACCESSORS ================================
; This pass expands non-memory accessors into ConnectToIndexed or
;   ConnectFromIndexed. All elements of the vector are 
;   explicitly written out, then indexed. Depending on the gender
;   of the accessor, it is transformed into ConnectToIndexed (male) or
;   ConnectFromIndexed (female)
; Eg:
public defstruct ExpandAccessors <: Pass
public defmethod pass (b:ExpandAccessors) -> (Circuit -> Circuit) : expand-accessors
public defmethod name (b:ExpandAccessors) -> String : "Expand Accessors"
public defmethod short-name (b:ExpandAccessors) -> String : "expand-accessors"

defn expand-vector (e:Expression) -> List<Expression> :
   val t = type(e) as VectorType
   for i in 0 to size(t) map-append :
      list(WIndex(e,i,type(t),gender(e as ?))) ;always be WRef|WSubfield|WIndex

defn expand-stmt (s:Stmt) -> Stmt :
   match(s) :
      (s:WDefAccessor) : 
         println-all-debug(["Matched WDefAcc with " name(s)])
         val mem? = match(source(s)) :
            (e:WRef) : kind(e) typeof MemKind
            (e) : false
         if mem? : s
         else :
            val vtype = type(type(source(s)) as VectorType)
            val wire = DefWire(info(s),name(s),vtype)
            switch {gender(s) == _} :
               MALE : Begin{list(wire,_)} $ ConnectFromIndexed(
                  info(s),
                  index(s),
                  WRef(name(wire),vtype,NodeKind(),FEMALE),
                  expand-vector(source(s)))
               FEMALE: Begin{list(wire,_)} $ ConnectToIndexed(
                  info(s),
                  index(s),
                  expand-vector(source(s)),
                  WRef(name(wire),vtype,NodeKind(),MALE))
      (s) : map(expand-stmt,s)

defn expand-accessors (c:Circuit) :
   Circuit(info(c),modules*, main(c)) where :
      val modules* = 
         for m in modules(c) map :
            match(m) :
               (m:InModule) : InModule(info(m),name(m),ports(m),expand-stmt(body(m)))
               (m:ExModule) : m

;;=============== LOWERING TO GROUND TYPES =============================
; All non-ground (elevated) types (Vectors, Bundles) are expanded out to
;   individual ground types.
; This pass involves filling a table mapping the name of elevated types
;   to the lowered ground expression names and genders. This allows
;   references to be resolved.
public defstruct LowerToGround <: Pass
public defmethod pass (b:LowerToGround) -> (Circuit -> Circuit) : lower-to-ground
public defmethod name (b:LowerToGround) -> String : "Lower To Ground"
public defmethod short-name (b:LowerToGround) -> String : "lower-to-ground"

defstruct EF :
   exp : Expression
   flip : Flip

defmethod print (o:OutputStream,e:EF) :
   print-all(o, ["EF(" exp(e) "," flip(e) ")"])
   
defmethod print (o:OutputStream,e:NTF) :
   print-all(o, ["NTF(" name(e) "," type(e) "," flip(e) ")"])

defstruct NTF :
   name : Symbol
   type : Type
   flip : Flip

defn num-elems (t:Type) -> Int :
   match(t) :
      (t:BundleType) : 
         var sum = 0
         for f in fields(t) do : 
            sum = sum + num-elems(type(f))
         sum
      (t:VectorType) : size(t) * num-elems(type(t))
      (t) : 1

defn index-of-elem (t:BundleType, s:Symbol) -> Int :
   var sum = 0
   label<Int> ret : 
      for f in fields(t) do :
         if s == name(f) : ret(sum)
         else : sum = sum + num-elems(type(f))
      error("Shouldn't be here")

defn generate-entry (n:Symbol,t:Type) -> List<NTF> :
   defn uniquify (n*:Symbol) -> Symbol : symbol-join([n expand-delin n*])
   match(t) :
      (t:BundleType) : 
         for f in fields(t) map-append :
            val es = generate-entry(name(f),type(f))
            for e in es map :
               NTF(uniquify(name(e)),type(e),flip(e) * flip(f))
      (t:VectorType) :
         for i in 0 to size(t) map-append :
            val es = generate-entry(to-symbol(i),type(t))
            for e in es map :
               NTF(uniquify(name(e)),type(e),flip(e))
      (t) : list $ NTF(n,t,DEFAULT)

defn expand-expr (e:Expression) -> List<EF> :
   defn inst? (e:Expression) -> True|False :
      match(e) :
         (e:WRef) : kind(e) == InstanceKind()
         (e) : false
   match(e) :
      (e:WRef) : 
         if inst?(e) : 
            for f in fields(type(e) as BundleType) map-append :
               for x in generate-entry(name(f),type(f)) map :
                  EF(WSubfield(e,name(x),type(x),gender(e)),flip(f) * flip(x))
         else :
            for x in generate-entry(name(e),type(e)) map :
               EF(WRef(name(x),type(x),kind(e),gender(e)), flip(x))
      (e:WSubfield) : 
         val f = {_ as Field} $
            for f in fields(type(exp(e)) as BundleType) find : name(f) == name(e)
         if inst?(exp(e)) : 
            ;; println-all(["here with " exp(e)])
            for x in generate-entry(name(f),type(f)) map :
               EF(WSubfield(exp(e),name(x),type(x),gender(e)),flip(x))
         else :
            val exps = expand-expr(exp(e))
            val begin = index-of-elem(type(exp(e)) as BundleType,name(e))
            val len = num-elems(type(e))
            val ret = headn(tailn(exps,begin),len)
            for r in ret map : EF(exp(r),flip(r) * flip(f))
      (e:WIndex) :
         val exps = expand-expr(exp(e))
         val len = num-elems(type(e))
         headn(tailn(exps,len * value(e)),len)
      ;(e:Pad) : 
         ;val v = exp(head(expand-expr(value(e))))
         ;list(EF(Pad(v,width(e),type(e)),DEFAULT))
      (e:DoPrim) :
         val args = for x in args(e) map : exp(head(expand-expr(x)))
         list(EF(DoPrim(op(e),args,consts(e),type(e)),DEFAULT))
      (e) : list(EF(e,DEFAULT))

defn lower-ports (ports:List<Port>) -> List<Port> :
   for p in ports map-append :
      for x in generate-entry(name(p),type(p)) map :
         Port(info(p),name(x),direction(p) * flip(x),type(x))

defn type (s:WDefAccessor) -> Type : type(type(source(s)) as VectorType)
defn size (s:DefMemory) -> Int : size(type(s))
defn size (s:WDefAccessor) -> Int : size(type(source(s)) as VectorType)
defn base-name (e:Expression) -> Symbol :
   match(e) : 
      (e:WRef) : name(e)
      (e:WSubfield) : base-name(exp(e))
      (e:WIndex) : base-name(exp(e))

defn set-gender (e:Expression,g:Gender,f:Flip) -> Expression :
   match(e) : 
      (e:WRef) : WRef(name(e),type(e),kind(e),g)
      (e:WSubfield) : WSubfield(set-gender(exp(e),g * f,DEFAULT),name(e),type(e),g)
      (e) : e

defn lower (body:Stmt) -> Stmt :
   defn lower-stmt (s:Stmt) -> Stmt :
      ;; println(s)
      match(s) :
         (s:DefWire) : Begin $
            for x in generate-entry(name(s),type(s)) map :
               DefWire(info(s),name(x),type(x))
         (s:DefRegister) : Begin{_} $
            for x in generate-entry(name(s),type(s)) map :
               DefRegister(info(s),name(x),type(x))
         (s:DefInstance) : 
            val fields = 
               for f in fields(type(module(s)) as BundleType) map-append :
                  val etfs = generate-entry(name(f),type(f))
                  for etf in etfs map : 
                     Field(name(etf),flip(etf) * flip(f),type(etf))
            val m = module(s) as WRef
            DefInstance(info(s),name(s),WRef(name(m),BundleType(fields),kind(m),gender(m)))
         (s:DefNode) : Begin $
            for x in expand-expr(value(s)) map : 
               DefNode(info(s),name(s),exp(x))
         (s:DefMemory) : Begin $ 
            for x in generate-entry(name(s),type(type(s))) map :
               DefMemory(info(s),name(x),VectorType(type(x),size(s)), seq?(s))
         (s:WDefAccessor) : 
            val ls = generate-entry(name(s),type(s))
            val rs = generate-entry(name(source(s) as WRef),type(s))
            Begin $ for (l in ls, r in rs) map:
               if flip(r) == REVERSE : error("Shouldn't be here")
               val memref = WRef(name(r),VectorType(type(r),size(s)),MemKind(),gender(s))
               WDefAccessor(info(s),name(l),memref,index(s),gender(s))
         (s:OnReset|Connect) : Begin $
            for (l in expand-expr(loc(s)), r in expand-expr(exp(s))) map :
               val lgender = FEMALE * flip(l)
               val rgender = MALE * flip(r)
               val l* = set-gender(exp(l),lgender,flip(l))
               val r* = set-gender(exp(r),rgender,flip(r))
               println-all-debug(["Left: " l " with Gender: " lgender])
               println-all-debug(["Right: " r " with Gender: " rgender])
               switch fn ([x,y]) : lgender == x and rgender == y :
                  [FEMALE,MALE]  : 
                     if s typeof Connect : Connect(info(s),l*,r*)
                     else : OnReset(info(s),l*,r*)
                  [MALE,FEMALE]  : 
                     if s typeof Connect : Connect(info(s),r*,l*)
                     else : OnReset(info(s),r*,l*)
         (s:BulkConnect) :
            val ls-fake = generate-entry(`null,type(loc(s)))
            val rs-fake = generate-entry(`null,type(exp(s)))
            val ls = expand-expr(loc(s))
            val rs = expand-expr(exp(s))
            val ls* = Vector<EF>()
            val rs* = Vector<EF>()
            for (l-fake in ls-fake,l in ls) do :
               for (r-fake in rs-fake, r in rs) do :
                  if name(l-fake) == name(r-fake) and flip(l-fake) == flip(r-fake) and type(l-fake) == type(r-fake) :
                     add(ls*,l)
                     add(rs*,r)
            Begin $ for (l in to-list(ls*), r in to-list(rs*)) map :
               val lgender = FEMALE * flip(l)
               val rgender = MALE * flip(r)
               val l* = set-gender(exp(l),lgender,flip(l))
               val r* = set-gender(exp(r),rgender,flip(r))
               println-all-debug(["Left: " l " with Gender: " lgender])
               println-all-debug(["Right: " r " with Gender: " rgender])
               switch fn ([x,y]) : lgender == x and rgender == y :
                  [FEMALE,MALE]  : Connect(info(s),l*,r*)
                  [MALE,FEMALE]  : Connect(info(s),r*,l*)
         (s:ConnectFromIndexed) : Begin(ls) where :
            val ctable = HashTable<Symbol,Vector<EF>>(symbol-hash)
            for e in exps(s) do :
               for (r in expand-expr(e),l in expand-expr(loc(s))) do :
                  val n = name(exp(l) as WRef)
                  val x = get?(ctable,n,Vector<EF>())
                  add(x,r)
                  ctable[n] = x
            val ls = for l in expand-expr(loc(s)) map :
                  val n = name(exp(l) as WRef)
                  val lgender = FEMALE * flip(l)
                  for x in ctable[n] do : 
                     if (flip(x) * MALE) == lgender : error("Shouldn't be here")
                  val rgender = lgender * REVERSE
                  val l* = set-gender(exp(l),lgender,flip(l))
                  val exps = to-list $ for e in ctable[n] map : set-gender(exp(e),rgender,flip(e))
                  switch fn ([x,y]) : lgender == x and rgender == y :
                     [FEMALE,MALE]   : ConnectFromIndexed(info(s),index(s),l*,exps)
                     [MALE,FEMALE]   : ConnectToIndexed(info(s),index(s),exps,l*)
         (s:ConnectToIndexed) : Begin(ls) where :
            val ctable = HashTable<Symbol,Vector<EF>>(symbol-hash)
            for e in locs(s) do :
               for (l in expand-expr(e),r in expand-expr(exp(s))) do :
                  val n = name(exp(r) as WRef)
                  val x = get?(ctable,n,Vector<EF>())
                  add(x,l)
                  ctable[n] = x
            val ls = for r in expand-expr(exp(s)) map :
                  val n = name(exp(r) as WRef)
                  val rgender = MALE * flip(r)
                  for x in ctable[n] do : 
                     if (flip(x) * FEMALE) == rgender : error("Shouldn't be here")
                  val lgender = rgender * REVERSE
                  val r* = set-gender(exp(r),rgender,flip(r))
                  val locs = to-list $ for e in ctable[n] map : set-gender(exp(e),lgender,flip(e))
                  switch fn ([x,y]) : lgender == x and rgender == y :
                     [FEMALE,MALE]   : ConnectToIndexed(info(s),index(s),locs,r*)
                     [MALE,FEMALE]   : ConnectFromIndexed(info(s),index(s),r*,locs)
         (s:Conditionally) : 
            Conditionally(info(s),exp(head $ expand-expr(pred(s))),lower-stmt(conseq(s)),lower-stmt(alt(s)))
         (s:Begin|EmptyStmt) : map(lower-stmt,s)

   lower-stmt(body)

defn lower-module (c:Circuit,m:Module) -> Module : 
   val ports* = lower-ports(ports(m))
   match(m) :
      (m:InModule) :
         val body* = lower(body(m))
         InModule(info(m),name(m),ports*,body*)
      (m:ExModule) :
         ExModule(info(m),name(m),ports*)

defn lower-to-ground (c:Circuit) -> Circuit :
   Circuit(info(c),modules*, main(c)) where :
      val modules* = 
         for m in modules(c) map :
            lower-module(c,m)


;;=========== CONVERT MULTI CONNECTS to WHEN ================
; This pass converts ConnectToIndexed and ConnectFromIndexed
;   into a series of when statements. TODO what about initial
;   values?
public defstruct ExpandIndexedConnects <: Pass
public defmethod pass (b:ExpandIndexedConnects) -> (Circuit -> Circuit) : expand-connect-indexed
public defmethod name (b:ExpandIndexedConnects) -> String : "Expand Indexed Connects"
public defmethod short-name (b:ExpandIndexedConnects) -> String : "expand-indexed-connects"

defn expand-connect-indexed-stmt (s: Stmt,sh:HashTable<Symbol,Int>) -> Stmt :
   defn equality (e1:Expression,e2:Expression) -> Expression :
      DoPrim(EQUAL-OP,list(e1,e2),List(),UIntType(UnknownWidth()))
   defn get-name (e:Expression) -> Symbol :
      match(e) :
         (e:WRef) : symbol-join([name(e) gen-delin])
         (e:WSubfield) : symbol-join([get-name(exp(e)) `. name(e) gen-delin])
         (e:WIndex) : symbol-join([get-name(exp(e)) `. to-symbol(value(e)) gen-delin])
         (e) : `T
   match(s) :
      (s:ConnectToIndexed) : Begin $
         if length(locs(s)) == 0 : list(EmptyStmt())
         else :
            val ref = WRef(firrtl-gensym(get-name(index(s)),sh),type(index(s)),NodeKind(),UNKNOWN-GENDER)
            append(
               list(DefNode(info(s),name(ref),index(s)))
               to-list $
                  for (i in 0 to false, l in locs(s)) stream : Conditionally(
                     info(s),
                     equality(ref,UIntValue(i,UnknownWidth())),
                     Connect(info(s),l,exp(s)),
                     EmptyStmt()
                  )
               )
      (s:ConnectFromIndexed) : Begin $
         if length(exps(s)) == 0 : list(EmptyStmt())
         else :
            val ref = WRef(firrtl-gensym(get-name(index(s)),sh),type(index(s)),NodeKind(),UNKNOWN-GENDER)
            append(
               list(Connect(info(s),loc(s),head(exps(s))),DefNode(info(s),name(ref),index(s)))
               to-list $
                  for (i in 1 to false, e in tail(exps(s))) stream : Conditionally(
                     info(s),
                     equality(ref,UIntValue(i,UnknownWidth())),
                     Connect(info(s),loc(s),e),
                     EmptyStmt()
                  )
            )
      (s) : map(expand-connect-indexed-stmt{_,sh},s)
  
defn expand-connect-indexed (m: Module) -> Module :
   match(m) :
      (m:InModule) : 
         val sh = get-sym-hash(m)
         InModule(info(m),name(m),ports(m),expand-connect-indexed-stmt(body(m),sh))
      (m:ExModule) : m

defn expand-connect-indexed (c: Circuit) -> Circuit :
  Circuit(info(c),modules*, main(c)) where :
     val modules* = 
        for m in modules(c) map :
           expand-connect-indexed(m)

;;================ EXPAND WHENS =============================
; This pass does three things: remove last connect semantics,
;   remove conditional blocks, and eliminate concept of scoping.
; First, we scan the circuit to build a table mapping references
;   to the final assigned value, represented with SymbolicValues.
;   Within a scope, we remove the last connect symantics to get
;   the final value. When leaving a scope, the resulting table
;   is merged with the parent scope by using the SVMux.
;   We also collect the kind of reference to know how to declare
;   it in a following stage.
; Second, we use the table to declare each reference, then
;   assign to each once. This is relatively straightforward 
;   except calculating the WritePort/ReadPort enables.
; Finally, we scan the table to remove redundant values
; The WritePort enable is calculated by returning 1 for all conditions
;   for which the corresponding symbolic value is not SVNul.
; The ReadPort enable is calcuated by scanning all entries in
;   the table for when this is referenced (a read). All conditions
;   are accumulated and OR'ed together.
public defstruct ExpandWhens <: Pass
public defmethod pass (b:ExpandWhens) -> (Circuit -> Circuit) : expand-whens
public defmethod name (b:ExpandWhens) -> String : "Expand Whens"
public defmethod short-name (b:ExpandWhens) -> String : "expand-whens"

; ======== Expression Computation Library ===========

val zero = UIntValue(0,IntWidth(1))
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) : width(e1) == width(e2)
         else : false
      (e1:SIntValue,e2:SIntValue) : 
         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: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 :
   if e1 == e2 : e1
   else if e1 == zero or e2 == zero : zero
   else if e1 == one : e2
   else if e2 == one : e1
   else : DoPrim(BIT-AND-OP,list(e1,e2),list(),UIntType(IntWidth(1)))

defn OR (e1:Expression,e2:Expression) -> Expression :
   if e1 == e2 : e1
   else if e1 == one or e2 == one : one
   else if e1 == zero : e2
   else if e2 == zero : e1
   else : DoPrim(BIT-OR-OP,list(e1,e2),list(),UIntType(IntWidth(1)))

defn NOT (e1:Expression) -> Expression :
   if e1 == one : zero
   else if e1 == zero : one
   else : DoPrim(EQUAL-OP,list(e1,zero),list(),UIntType(IntWidth(1)))

defn children (e:Expression) -> List<Expression> :
   val es = Vector<Expression>()
   defn f (e:Expression) :
      add(es,e)
      e
   map(f,e)
   to-list(es)
   
; ======= Symbolic Value Library ==========
public definterface SymbolicValue
public defstruct SVExp <: SymbolicValue :
   exp : Expression
public defstruct SVMux <: SymbolicValue :
   pred : Expression
   conseq : SymbolicValue
   alt : SymbolicValue
public defstruct SVNul <: SymbolicValue

defmethod print (o:OutputStream, sv:SymbolicValue) :
   match(sv) :
      (sv: SVExp) : print(o, exp(sv))
      (sv: SVMux) : print-all(o, ["(" pred(sv) " ? " conseq(sv) " : " alt(sv) ")"])
      (sv: SVNul) : print(o, "SVNUL")

defmulti map<?T> (f: SymbolicValue -> SymbolicValue, sv:?T&SymbolicValue) -> T 
defmethod map (f: SymbolicValue -> SymbolicValue, sv:SymbolicValue) -> SymbolicValue :
   match(sv) :
      (sv: SVMux) : SVMux(pred(sv),f(conseq(sv)),f(alt(sv)))
      (sv) : sv

defn do (f:SymbolicValue -> ?, s:SymbolicValue) -> False :
   for x in s map :
      f(x)
      x
   false
defn dor (f:SymbolicValue -> ?, e:SymbolicValue) -> False :
   do(f,e)
   for x in e map :
      dor(f,x)
      x
   false

defmethod equal? (a:SymbolicValue,b:SymbolicValue) -> True|False :
   match(a,b) :
      (a:SVNul,b:SVNul) : true
      (a:SVExp,b:SVExp) : exp(a) == exp(b)
      (a:SVMux,b:SVMux) : pred(a) == pred(b) and conseq(a) == conseq(b) and alt(a) == alt(b)
      (a,b) : false

;TODO add invert to primop
defn optimize (sv:SymbolicValue) -> SymbolicValue :
   match(map(optimize,sv)) :
      (sv:SVMux) : 
         if conseq(sv) == alt(sv) : conseq(sv)
         else : 
            match(conseq(sv),alt(sv)) :
               (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 ==========

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|False :
   match(remove-nul(sv)) :
      (sv:SVMux) : 
         DoPrim(MUX-OP,
                list(pred(sv),to-exp(conseq(sv)) as Expression,to-exp(alt(sv)) as Expression),
                list(),
                UIntType(IntWidth(1)))
      (sv:SVExp) : exp(sv)
      (sv:SVNul) : false
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?

; 1) Build Table, Build Declaration List

; assign: holds the symbolic value of a wref.
; resets: holds the symbolic value of connections under reset
; stmts:  Used to hold the orignal type, as well as the mem/index for Write/ReadPorts
; kinds:  Used to know the kind of reference, so we know whether we should error if it isn't initialized. We also know how we should declare the refernce.
; enables:Calculated off of assigns.

defn expand-whens (ports:List<Port>, table:HashTable<Symbol,SymbolicValue>,cons:Vector<Stmt>) -> False :
   for p in ports do :
      if direction(p) == OUTPUT :
         val ref = WRef(name(p),type(p),PortKind(),FEMALE)
         if has-nul?(table[name(p)]) : 
            println("Uninitialized: ~" % [to-string(name(p))]);TODO actually collect error
         else : add{cons,_} $ Connect(FileInfo(),ref,to-exp(table[name(p)]) as Expression)

defn expand-whens (s:Stmt, table:HashTable<Symbol,SymbolicValue>,decs:Vector<Stmt>,cons:Vector<Stmt>) -> Stmt :
   match(map(expand-whens{_,table,decs,cons},s)) : 
      (s:DefNode|DefMemory) : add(decs,s)
      (s:DefWire) : 
         add(decs,s)
         val ref = WRef(name(s),type(s),NodeKind(),FEMALE)
         if has-nul?(table[name(s)]) : 
            println("Uninitialized: ~" % [to-string(name(s))]);TODO actually collect error
         else : add{cons,_} $ Connect(info(s),ref,to-exp(table[name(s)]) as Expression)
      (s:DefRegister) : 
         val e = to-exp(table[name(s)])
         match(e) : 
            (e:Expression) : 
               add{decs,_} $ DefWire(info(s),name(s),type(s))
               val ref = WRef(name(s),type(s),NodeKind(),FEMALE)
               add{cons,_} $ Connect(info(s),ref,Register(type(s),e,to-exp(optimize $ get-write-enable(table[name(s)])) as Expression))
            (e:False) : false
      (s:WDefAccessor) : 
         val t = type(type(source(s)) as VectorType)
         val n = name(s)
            switch {_ == gender(s)} :
               MALE : 
                  add{decs,_} $ DefWire(info(s),n,t)
                  val ref = WRef(n,t,WriteAccessorKind(),FEMALE)
                  add{cons,_} $ Connect(info(s),ref,ReadPort(source(s),index(s),t,get-read-enable(n,table)))
               FEMALE :
                  add(decs,DefWire(info(s),n,t))
                  val ref = WRef(n,t,WriteAccessorKind(),MALE)
                  val enable = (to-exp $ optimize $ get-write-enable(table[n])) as Expression
                  val wp = WritePort(source(s),index(s),t,enable as Expression)
                  val e = to-exp(table[n])
                  add{cons,_} $ Connect(info(s),wp,ref)
                  match(e) :
                     (e:False) : 
                        println("Uninitialized: ~" % [to-string(n)]) ;TODO actually collect error
                     (e:Expression) : 
                        add{cons,_} $ Connect(info(s),ref,e)
      (s:DefInstance) : 
         add(decs,s)
            for f in fields(type(module(s)) as BundleType) map :
               if flip(f) == REVERSE : 
                  val n = to-symbol("~.~" % [name(s),name(f)]) ; only on inputs
                  val x = to-symbol(split(to-string(n),'.')[0])
                  val f = to-symbol(split(to-string(n),'.')[1])
                  val ref = WRef(x,type(module(s)),InstanceKind(),FEMALE)
                  val sref = WSubfield(ref,f,bundle-field-type(type(module(s)),f),FEMALE)
                  if has-nul?(table[n]) : 
                     println("Uninitialized: ~" % [to-string(n)]);TODO actually collect error
                  else : add{cons,_} $ Connect(info(s),sref,to-exp(table[n]) as Expression)
      (s:Connect|Conditionally|OnReset|Begin|EmptyStmt) : false
   s

defn get-read-enable (sym:Symbol,table:HashTable<Symbol,SymbolicValue>) -> Expression :
   defn get-single-read-enable (sym:Symbol,sv:SymbolicValue) -> Expression :
      defn active (e:Expression) -> True|False : 
         match(e) :
            (e:WRef) : name(e) == sym
            (e) : reduce-or{_} $ map(active,children(e))
            (e) : false
      match(sv) : 
         (sv: SVNul) : zero
         (sv: SVExp) : 
            if active(exp(sv)) : one 
            else : zero
         (sv: SVMux) : 
            val e0 = get-single-read-enable(sym,SVExp(pred(sv)))
            val e1 = get-single-read-enable(sym,conseq(sv))
            val e2 = get-single-read-enable(sym,alt(sv))
            if e1 == e2 : OR(e0,e1)
            else : OR(e0,OR(AND(pred(sv),e1),AND(NOT(pred(sv)),e2)))
   reduce-or $ to-list $ for y in table stream : get-single-read-enable(sym,value(y))

defn get-write-enable (sv:SymbolicValue) -> SymbolicValue :
   match(map(get-write-enable,sv)) :
      (sv: SVExp) : SVExp(one)
      (sv: SVNul) : SVExp(zero)
      (sv) : sv

defn merge-resets (assign:HashTable<Symbol,SymbolicValue>, resets:HashTable<Symbol,SymbolicValue>) -> HashTable<Symbol,SymbolicValue> :
   val table = HashTable<Symbol,SymbolicValue>(symbol-hash)
   val reset = WRef(`reset, UnknownType(), PortKind(), MALE)
   for i in get-unique-keys(list(assign,resets)) do :
      table[i] = match(get?(assign,i,false),get?(resets,i,false)) : 
            (a:SymbolicValue,r:SymbolicValue) : SVMux(reset,r,a)
            (a:SymbolicValue,r:False) : a
            (a:False,r:SymbolicValue) : SVMux(reset,r,SVNul())
            (a:False,r:False) : error("Shouldn't be here")
   table

defn build-tables (s:Stmt, 
                   assign:HashTable<Symbol,SymbolicValue>,
                   resets:HashTable<Symbol,SymbolicValue>,
                   flattn:HashTable<Symbol,True|False>,
                   ) -> False :
   match(s) :
      (s:DefWire) :
         assign[name(s)] = SVNul()
         flattn[name(s)] = true
      (s:DefRegister|WDefAccessor) : 
         assign[name(s)] = SVNul()
         flattn[name(s)] = false
      (s:DefInstance) : ;TODO only add instance input ports. This probably involves correcting instance genders
         for f in fields(type(module(s)) as BundleType) do :
            if flip(f) == REVERSE : 
               println-all-debug(["Instance: " s " has input " f])
               val n = to-symbol("~.~" % [name(s),name(f)]) ; only on inputs
               assign[n] = SVNul()
               flattn[n] = true
      (s:Conditionally) :
         defn combine (flattn:HashTable<Symbol,True|False>,
                       table-c:HashTable<Symbol,SymbolicValue>,
                       table-a:HashTable<Symbol,SymbolicValue>,
                       i:Symbol) -> SymbolicValue|False :
            match(get?(table-c,i,false),get?(table-a,i,false)) : 
                  (c:SymbolicValue,a:SymbolicValue) : 
                     if c == a : c
                     else : SVMux(pred(s),c,a)
                  (c:SymbolicValue,a:False) : 
                     if flattn[i] : c
                     else : SVMux(pred(s),c,SVNul())
                  (c:False,a:SymbolicValue) :
                     if flattn[i] : a
                     else : SVMux(pred(s),SVNul(),a)
                  (c:False,a:False) : false

         val assign-c = deepcopy(assign)
         val assign-a = deepcopy(assign)
         val resets-c = deepcopy(resets)
         val resets-a = deepcopy(resets)
         build-tables(conseq(s),assign-c,resets-c,flattn)
         build-tables(alt(s),assign-a,resets-a,flattn)
         for i in get-unique-keys(list(assign-c,assign-a)) do :
            assign[i] = combine(flattn,assign-c,assign-a,i) as SymbolicValue
            val r = combine(flattn,resets-c,resets-a,i)
            match(r) : 
               (r:SymbolicValue) : resets[i] = r
               (r) : false
         ;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|OnReset) : 
         val key* = match(loc(s)) :
            (e:WRef) : name(e)
            (e:WSubfield) : symbol-join([name(exp(e) as ?) `. name(e)])
            (e) : error("Shouldn't be here with ~" % [e])
         if s typeof Connect : assign[key*] = SVExp(exp(s))
         if s typeof OnReset : resets[key*] = SVExp(exp(s))
      (s:Begin) : for s* in body(s) do: build-tables(s*,assign,resets,flattn)
      (s:DefMemory|DefNode|EmptyStmt) : false
         
defn expand-whens (m:Module) -> Module :
   match(m) :
      (m:ExModule) : m
      (m:InModule) : 
         val assign = HashTable<Symbol,SymbolicValue>(symbol-hash)
         val resets = HashTable<Symbol,SymbolicValue>(symbol-hash)
         val flattn = HashTable<Symbol,True|False>(symbol-hash)

         for p in ports(m) do :
            if direction(p) == OUTPUT :
               assign[name(p)] = SVNul()
               flattn[name(p)] = false
               
         build-tables(body(m),assign,resets,flattn)
         for x in assign do : assign[key(x)] = optimize(value(x))
         for x in resets do : resets[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("====== Resets ======")
         for x in resets do : println-debug(x)

         val table = merge-resets(assign,resets)
         println-debug("====== Table ======")
         for x in table do : println-debug(x)
         val decs = Vector<Stmt>()
         val cons = Vector<Stmt>()
         expand-whens(ports(m),table,cons)
         expand-whens(body(m),table,decs,cons)
         InModule(info(m),name(m),ports(m),Begin(append(to-list(decs),to-list(cons))))

defn expand-whens (c:Circuit) -> Circuit :
   Circuit(info(c),modules*, main(c)) where :
      val modules* = 
         for m in modules(c) map :
            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.
; Low FIRRTL Pass.
public defstruct InferWidths <: Pass
public defmethod pass (b:InferWidths) -> (Circuit -> Circuit) : infer-widths
public defmethod name (b:InferWidths) -> String : "Infer Widths"
public defmethod short-name (b:InferWidths) -> String : "infer-widths"

public defstruct VarWidth <: Width :
   name: Symbol
public defstruct PlusWidth <: Width :
   arg1 : Width
   arg2 : Width
public defstruct MinusWidth <: Width :
   arg1 : Width
   arg2 : Width
public defstruct MaxWidth <: Width :
   args : List<Width>
public defstruct ExpWidth <: Width :
   arg1 : Width

val width-name-hash = HashTable<Symbol,Int>(symbol-hash)

public defmulti map<?T> (f: Width -> Width, w:?T&Width) -> T
defmethod map (f: Width -> Width, w:Width) -> Width :
   match(w) :
      (w:MaxWidth) : MaxWidth(map(f,args(w)))
      (w:PlusWidth) : PlusWidth(f(arg1(w)),f(arg2(w)))
      (w:MinusWidth) : MinusWidth(f(arg1(w)),f(arg2(w)))
      (w:ExpWidth) : ExpWidth(f(arg1(w)))
      (w) : w

public defmethod print (o:OutputStream, w:VarWidth) :
   print(o,name(w))
public defmethod print (o:OutputStream, w:MaxWidth) :
   print-all(o,["max" args(w)])
public defmethod print (o:OutputStream, w:PlusWidth) :
   print-all(o,[ arg1(w) " + " arg2(w)])
public defmethod print (o:OutputStream, w:MinusWidth) :
   print-all(o,[ arg1(w) " - " arg2(w)])
public defmethod print (o:OutputStream, w:ExpWidth) :
   print-all(o,[ "exp(" arg1(w) ")"])

public definterface Constraint
public defstruct WGeq <: Constraint :
   loc : Width
   exp : Width
public defmethod print (o:OutputStream, c:WGeq) :
   print-all(o,[ loc(c) " >= " exp(c)])
defmethod equal? (w1:Width,w2:Width) -> True|False :
   match(w1,w2) :
      (w1:VarWidth,w2:VarWidth) : name(w1) == name(w2)
      (w1:MaxWidth,w2:MaxWidth) : 
         label<True|False> ret :
            if not length(args(w1)) == length(args(w2)) : ret(false)
            else :
               for w in args(w1) do :
                  if not contains?(args(w2),w) : ret(false)
               ret(true)
      (w1:IntWidth,w2:IntWidth) : width(w1) == width(w2)
      (w1:PlusWidth,w2:PlusWidth) : 
         (arg1(w1) == arg1(w2) and arg2(w1) == arg2(w2)) or (arg1(w1) == arg2(w2) and arg2(w1) == arg1(w2))
      (w1:MinusWidth,w2:MinusWidth) :
         (arg1(w1) == arg1(w2) and arg2(w1) == arg2(w2)) or (arg1(w1) == arg2(w2) and arg2(w1) == arg1(w2))
      (w1:ExpWidth,w2:ExpWidth) : arg1(w1) == arg1(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)
   else : false

   
defn solve-constraints (l:List<WGeq>) -> HashTable<Symbol,Width> :
   defn contains? (n:Symbol,h:HashTable<Symbol,?>) -> True|False : key?(h,n)
   defn make-unique (ls:List<WGeq>) -> HashTable<Symbol,Width> :
      val h = HashTable<Symbol,Width>(symbol-hash)
      for g in ls do :
         match(loc(g)) :
            (w:VarWidth) :
               val n = name(w)
               if contains?(n,h) : h[n] = MaxWidth(list(exp(g),h[n]))
               else : h[n] = exp(g)
            (w) : w
      h
   defn simplify (w:Width) -> Width :
      match(map(simplify,w)) :
         (w:MaxWidth) : 
            val v = Vector<Width>()
            for w* in args(w) do :
               match(w*) :
                  (w*:MaxWidth) : 
                     for x in args(w*) do : add(v,x)
                  (w*) : add(v,w*)
            MaxWidth(unique(v))
         (w:PlusWidth) : 
            match(arg1(w),arg2(w)) :
               (w1:IntWidth,w2:IntWidth) : IntWidth(width(w1) + width(w2))
               (w1,w2) : w
         (w:MinusWidth) : 
            match(arg1(w),arg2(w)) :
               (w1:IntWidth,w2:IntWidth) : IntWidth(width(w1) - width(w2))
               (w1,w2) : w
         (w:ExpWidth) : 
            match(arg1(w)) :
               (w1:IntWidth) : IntWidth(pow(2,width(w1)) - 1)
               (w1) : w
         (w) : w
   defn substitute (w:Width,h:HashTable<Symbol,Width>) -> Width :
      ;println-all-debug(["Substituting for [" w "]"])
      val w* = simplify(w)
      ;println-all-debug(["After Simplify: [" w* "]"])
      match(map(substitute{_,h},simplify(w))) :
         (w:VarWidth) : 
            ;println-debug("matched varwidth!")
            if contains?(name(w),h) : 
               ;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-debug(["Width after sub: " t])
               h[name(w)] = t
               t
            else : w
         (w): 
            ;println-all-debug(["not varwidth!" w])
            w
   defn b-sub (w:Width,h:HashTable<Symbol,Width>) -> Width:
      match(map(b-sub{_,h},w)) :
         (w:VarWidth) : 
            if key?(h,name(w)) : h[name(w)]
            else : w
         (w) : w
   defn remove-cycle (n:Symbol,w:Width) -> Width :
      ;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-debug(["After removing cycle for " n ", returning " w*])
      w*
   defn self-rec? (n:Symbol,w:Width) -> True|False :
      var has? = false
      defn look (w:Width) -> Width :
         match(map(look,w)) :
            (w:VarWidth) : if name(w) == n : has? = true
            (w) : w
         w
      look(w)
      has?
       
   ; Forward solve
   ; Returns a solved list where each constraint undergoes:
   ;  1) Continuous Solving (using triangular solving)
   ;  2) Remove Cycles
   ;  3) Move to solved if not self-recursive
   val u = make-unique(l)
   println-debug("======== UNIQUE CONSTRAINTS ========")
   for x in u do : println-debug(x)
   println-debug("====================================")

   val f = HashTable<Symbol,Width>(symbol-hash)
   val o = Vector<Symbol>()
   for x in u do :
      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-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-debug(["After Remove Cycle: " n " => " e*])
      if not self-rec?(n,e*) : 
         ;println-all-debug(["Not rec!: " n " => " e*])
         ;println-all-debug(["Adding [" n "=>" e* "] to Solutions Table"])
         add(o,n)
         f[n] = e*

   println-debug("Forward Solved Constraints")
   for x in f do : println-debug(x)

   ; Backwards Solve
   val b = HashTable<Symbol,Width>(symbol-hash)
   for i in (length(o) - 1) through 0 by -1 do :
      val n = o[i]
      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-debug(["BACK RETURN: [" n " => " e* "]"])
      b[n] = e*
      println-debug("==== SOLUTIONS TABLE (Post backsolve) ====")
      for x in b do : println-debug(x)
      println-debug("=========================")
   b
   
public defn width! (t:Type) -> Width :
   match(t) :
      (t:UIntType) : width(t)
      (t:SIntType) : width(t)
      (t) : error("No width!")
public defn width! (e:Expression) -> Width : width!(type(e))

defn gen-constraints (m:Module, h:HashTable<Symbol,Type>, v:Vector<WGeq>) -> Module:
   defn gen-constraints-s (s:Stmt) -> Stmt :
      match(map(gen-constraints-s,s)) :
         (s:DefWire) : DefWire(info(s),name(s),h[name(s)])
         (s:DefInstance) : DefInstance(info(s),name(s),gen-constraints(module(s)))
         (s:DefMemory) : DefMemory(info(s),name(s),h[name(s)] as VectorType,seq?(s))
         (s:DefNode) : 
            val l = h[name(s)]
            val r = gen-constraints(value(s))
            add(v,WGeq(width!(l),width!(type(r))))
            add(v,WGeq(width!(type(r)),width!(l)))
            DefNode(info(s),name(s),r)
         (s:Connect) : 
            val l = gen-constraints(loc(s))
            val e = gen-constraints(exp(s))
            add(v,WGeq(width!(type(l)),width!(type(e))))
            add(v,WGeq(width!(type(e)),width!(type(l))))
            Connect(info(s),l,e)
         (s) : s

   defn gen-constraints (e:Expression) -> Expression :
      match(map(gen-constraints,e)) :
         (e:WRef) : WRef(name(e),h[name(e)],kind(e),gender(e))
         (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, value-w))
         ;   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))
         (e:UIntValue) : 
            match(width(e)) :
               (w:UnknownWidth) : 
                  val w* = VarWidth(firrtl-gensym(`w,width-name-hash))
                  add(v,WGeq(w*,IntWidth(ceil-log2(value(e)))))
                  UIntValue(value(e),w*)
               (w) : e
         (e:SIntValue) : 
            match(width(e)) :
               (w:UnknownWidth) : 
                  val w* = VarWidth(firrtl-gensym(`w,width-name-hash))
                  add(v,WGeq(w*,IntWidth(1 + ceil-log2(abs(value(e))))))
                  SIntValue(value(e),w*)
               (w) : e
         (e) : e

   val ports* = 
      for p in ports(m) map : Port(info(p),name(p),direction(p),h[name(p)])
         
   match(m) :
      (m:ExModule) : ExModule(info(m),name(m),ports*)
      (m:InModule) : InModule(info(m),name(m),ports*,gen-constraints-s(body(m)))

defn build-environment (c:Circuit,m:Module,h:HashTable<Symbol,Type>) -> HashTable<Symbol,Type> :
   defn build-environment (s:Stmt) -> False :
      match(s) :
         (s:DefWire) : h[name(s)] = remove-unknowns(type(s))
         (s:DefInstance) : h[name(s)] = h[name(module(s) as WRef)]
         (s:DefMemory) : h[name(s)] = remove-unknowns(type(s))
         (s:DefNode) : h[name(s)] = remove-unknowns(type(value(s)))
         (s) : false
      do(build-environment,s)
   for p in ports(m) do :
      h[name(p)] = bundle-field-type(h[name(m)],name(p))

   match(m) :
      (m:ExModule) : false
      (m:InModule) : build-environment(body(m))
   h
         
defn reduce-var-widths (c:Circuit,h:HashTable<Symbol,Width>) -> Circuit :
   defn evaluate (w:Width) -> Width :
      defn apply (a:Int|False,f:(Int) -> Int) -> Int|False :
         if a typeof Int : f(a as Int)
         else : 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)
         else : false
      defn apply-l (l:List<Int|False>,f:(Int,Int) -> Int) -> Int|False :
         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
         else : b
      defn solve (w:Width) -> Int|False :
         match(w) :
            (w:VarWidth) : 
               val w* = h[name(w)]
               if w* typeof VarWidth : false
               else : solve(w*)
            (w:MaxWidth) : apply-l(map(solve,args(w)),max)
            (w:PlusWidth) : apply(solve(arg1(w)),solve(arg2(w)),{_ + _})
            (w:MinusWidth) : apply(solve(arg1(w)),solve(arg2(w)),{_ - _})
            (w:ExpWidth) : apply(2,solve(arg1(w)),{pow(_,_) - 1})
            (w:IntWidth) : width(w)
            (w) : error("Shouldn't be here")
   
      val s = solve(w)
      if s typeof Int : IntWidth(s as Int)
      else : w

   defn reduce-var-widths-w (w:Width) -> Width :
      println-all-debug(["REPLACE: " w])
      val w* = evaluate(w)
      println-all-debug(["WITH: " w*])
      w*

   val modules* = for m in modules(c) map :
      val ports* = for p in ports(m) map :
         Port(info(p),name(p),direction(p),mapr(reduce-var-widths-w,type(p)))

      match(m) :
         (m:ExModule) : ExModule(info(m),name(m),ports*)
         (m:InModule) : InModule(info(m),name(m),ports*,mapr(reduce-var-widths-w,body(m)))

   Circuit(info(c),modules*,main(c))

defn remove-unknowns-w (w:Width) -> Width :
   match(w) :
      (w:UnknownWidth) : VarWidth(firrtl-gensym(`w,width-name-hash))
      (w) : w
defn remove-unknowns (t:Type) -> Type : mapr(remove-unknowns-w,t)

defn infer-widths (c:Circuit) -> Circuit :
   defn deepcopy (t:HashTable<Symbol,Type>) -> HashTable<Symbol,Type> :
      t0 where :
         val t0 = HashTable<Symbol,Type>(symbol-hash)
         for x in t do :
            t0[key(x)] = value(x)
   
   val v = Vector<WGeq>()
   val ports* = HashTable<Symbol,Type>(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-debug(["====== MODULE(" name(m) ") ENV ======"])
      val h = build-environment(c,m,deepcopy(ports*))
      for x in h do: println-debug(x)
      println-all-debug(["====================================="])
      val m* = gen-constraints(m,h,v)
      println-all-debug(["====== MODULE(" name(m) ") ======"])
      println-debug(m*)
      println-all-debug(["====================================="])
      m*
   println-debug("======== ALL CONSTRAINTS ========")
   for x in v do : println-debug(x)
   println-debug("=================================")
   val h = solve-constraints(to-list(v))
   println-debug("======== SOLVED CONSTRAINTS ========")
   for x in h do : println-debug(x)
   println-debug("====================================")
   reduce-var-widths(Circuit(info(c),modules*,main(c)),h)


;================= Inline Instances ========================
; Inlines instances. Assumes module with same name as the
;   Circuit is the top level module
public defstruct Inline <: Pass
public defmethod pass (b:Inline) -> (Circuit -> Circuit) : inline-instances
public defmethod name (b:Inline) -> String : "Inline Instances"
public defmethod short-name (b:Inline) -> String : "inline-instances"

defn inline-instances (c:Circuit) :
   val h = HashTable<Symbol,InModule>(symbol-hash)
   val h-s = HashTable<Symbol,Stmt>(symbol-hash)
   defn inline-inst (s:Stmt) -> Stmt :
      match(map(inline-inst,s)) :
        (s:DefInstance) : 
           val n = name(module(s) as WRef)
           val m = h[n]
           val body* = 
              if key?(h-s,n) : h-s[n]
              else : 
                 val v = Vector<Stmt>()
                 for p in ports(m) do :
                    add(v,DefWire(info(s),name(p),type(p)))
                 add(v,inline-inst(body(m)))
                 Begin(to-list(v))
           h-s[n] = body*
           rename-s(body*,name(s))
        (s) : map(inline-inst-e,s)
   defn inline-inst-e (e:Expression) -> Expression :
      match(map(inline-inst-e,e)) :
         (e:WSubfield) : 
            match(kind(exp(e) as WRef)) :
               (k:InstanceKind) : 
                  WRef(symbol-join([name(exp(e) as WRef) expand-delin name(e)]),type(e),k,gender(e))
               (k:MemKind) : e
         (e) : e
   defn rename (ref:Symbol,n:Symbol) -> Symbol : symbol-join([n expand-delin ref])
   defn rename-e (e:Expression,n:Symbol) -> Expression :
      match(map(rename-e{_,n},e)) :
         (e:WRef) : WRef(rename(name(e),n),type(e),kind(e),gender(e))
         (e:WSubfield) : 
            match(kind(exp(e) as WRef)) :
               (k:InstanceKind) : 
                  WRef(symbol-join([name(exp(e) as WRef) expand-delin name(e)]),type(e),k,gender(e))
               (k:MemKind) : e
         (e) : e
   defn rename-s (s:Stmt,n:Symbol) -> Stmt :
      map{rename-e{_,n},_} $ match(map(rename-s{_,n},s)) :
         (s:DefWire) : DefWire(info(s),rename(name(s),n),type(s))
         (s:DefInstance) : error("Shouldn't be here")
         (s:DefMemory) : DefMemory(info(s),rename(name(s),n),type(s),seq?(s))
         (s:DefNode) : DefNode(info(s),rename(name(s),n),value(s))
         (s) : s
   for m in modules(c) do :
      match(m) : 
         (m:ExModule) : error("Cannot inline with external modules")
         (m:InModule) : h[name(m)] = m
   val top = (for m in modules(c) find : name(m) == main(c)) as InModule
   Circuit(info(c),list(InModule(info(top),name(top),ports(top),inline-inst(body(top)))),main(c))


;================= Split Expressions ========================
; Intended to only work on low firrtl
public defstruct SplitExp <: Pass
public defmethod pass (b:SplitExp) -> (Circuit -> Circuit) : split-exp
public defmethod name (b:SplitExp) -> String : "Split Expressions"
public defmethod short-name (b:SplitExp) -> String : "split-expressions"

defn full-name (e:Expression) -> Symbol :
   match(e) :
      (e:WRef) : name(e)
      (e:WSubfield) : to-symbol $ string-join([full-name(exp(e)) "." name(e)])
      (e) : error("Non-supported expression.")

defn split-exp (c:Circuit) :
   defn split-exp-s (s:Stmt,v:Vector<Stmt>,sh:HashTable<Symbol,Int>) -> False :
      defn split-exp-e (e:Expression,n:Symbol|False,info:FileInfo) -> Expression :
         match(map(split-exp-e{_,n,info},e)) :
            (e:DoPrim) : 
               val n* = 
                  if n typeof False : firrtl-gensym(`T,sh)
                  else : firrtl-gensym(symbol-join([n as Symbol gen-delin]),sh)
               add(v,DefNode(info,n*,e))
               WRef(n*,type(e),NodeKind(),UNKNOWN-GENDER)
            (e) : e
      match(s) :
         (s:Begin) : 
            defn f (s:Stmt) -> False: split-exp-s(s,v,sh)
            do(f,s)
         (s:Conditionally) : error("Shouldn't be here")
         (s:Connect) :
            match(loc(s)) :
               (e:WritePort) : add(v,map(split-exp-e{_,full-name(exp(s)),info(s)},s))
               (e) : add(v,map(split-exp-e{_,full-name(loc(s)),info(s)},s))
         (s:DefNode) : add(v,map(split-exp-e{_,name(s),info(s)},s))
         (s) : add(v,map(split-exp-e{_,false,info(s)},s))
      false

   Circuit{info(c),_,main(c)} $
      for m in modules(c) map :
         match(m) :
            (m:InModule) :
               val v = Vector<Stmt>()
               val sh = get-sym-hash(m)
               split-exp-s(body(m),v,sh)
               InModule(info(m),name(m),ports(m),Begin(to-list(v)))
            (m:ExModule) : m

;================= Bring to Real IR ========================
; Returns a new Circuit with only real IR nodes.
public defstruct ToRealIR <: Pass
public defmethod pass (b:ToRealIR) -> (Circuit -> Circuit) : to-real-ir
public defmethod name (b:ToRealIR) -> String : "Real IR"
public defmethod short-name (b:ToRealIR) -> String : "real-ir"

defn to-real-ir (c:Circuit) :
   defn to-exp (e:Expression) :
      match(map(to-exp,e)) :
         (e:WRef) : Ref(name(e), type(e))
         (e:WSubfield) : Subfield(exp(e),name(e),type(e))
         (e:WIndex) : error("Shouldn't be here")
         (e) : e
   defn to-stmt (s:Stmt) :
     match(map(to-exp,s)) :
        (e:WDefAccessor) : error("Shouldn't be here")
        (e:ConnectToIndexed) : error("Shouldn't be here")
        (e:ConnectFromIndexed) : error("Shouldn't be here")
        (e) : map(to-stmt,e)

   Circuit(info(c),modules*, main(c)) where :
      val modules* =
         for m in modules(c) map :
            match(m) :
               (m:InModule) : InModule(info(m),name(m), ports(m), to-stmt(body(m)))
               (m:ExModule) : m

;================= Special Rename ========================
; Returns a new Circuit with only real IR nodes.
public defstruct SpecialRename <: Pass :
   original-sym : Symbol
   new-sym : Symbol
public defmethod pass (b:SpecialRename) -> (Circuit -> Circuit) : special-rename{original-sym(b),new-sym(b),_:Circuit}
public defmethod name (b:SpecialRename) -> String : "Special Rename"
public defmethod short-name (b:SpecialRename) -> String : "special-rename"

public defn special-rename (original-sym:Symbol,new-sym:Symbol,c:Circuit) :
   defn rename (s:Symbol) -> Symbol :
      val y = Vector<String>()
      val os = to-string $ original-sym
      val ns = to-string $ new-sym
      defn rename (st:String) -> False :
         if st == os : 
            add(y,ns)
         else if length(st) <= length(os) : 
            add(y,st)
         else :
            if substring(st,0,length(os)) == os :
               add(y,ns)
               rename(substring(st,length(os),length(st)))
            else : 
               add(y,substring(st,0,1))
               rename(substring(st,1,length(st)))
      rename(to-string(s))
      to-symbol $ string-join $ to-list(y)
   defn to-exp (e:Expression) -> Expression :
      match(map(to-exp,e)) :
         (e:Ref) : Ref(rename(name(e)), type(e))
         (e:Subfield) : Subfield(exp(e),rename(name(e)),type(e))
         (e) : e
   defn to-stmt (s:Stmt) -> Stmt :
     match(map(to-exp,s)) :
        (s:DefWire) : DefWire(info(s),rename(name(s)),type(s))
        (s:DefRegister) : DefRegister(info(s),rename(name(s)),type(s))
        (s:DefInstance) : DefInstance(info(s),rename(name(s)),module(s))
        (s:DefMemory) : DefMemory(info(s),rename(name(s)),type(s),seq?(s))
        (s:DefNode) : DefNode(info(s),rename(name(s)),value(s))
        (s:DefAccessor) : DefAccessor(info(s),rename(name(s)),source(s),index(s))
        (s) : map(to-stmt,s)

   defn to-port (p:Port) -> Port : Port(info(p),rename(name(p)),direction(p),type(p))

   Circuit(info(c),modules*, main(c)) where :
      val modules* =
         for m in modules(c) map :
            match(m) :
               (m:InModule) : InModule(info(m),name(m), map(to-port,ports(m)), to-stmt(body(m)))
               (m:ExModule) : m