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

;============== Pass List ================
public val standard-passes = to-list $ [
   ;CheckHighForm()
   ;TempElimination()
   ToWorkingIR()
   ResolveKinds()
   ;CheckKinds()
   InferTypes()
   ;CheckTypes()
   ResolveGenders()
   ;CheckGenders()
   ;ExpandAccessors()
   ;LowerToGround()
   ;ExpandIndexedConnects()
   ;InlineIndexed()
   ExpandWhens()
   InferWidths()
   ;Inline()
   SplitExp()
   ;CheckLowForm()
   ;ToRealIR() 
   ;Pad() 
   ]
;=============== WORKING IR ================================
public definterface Kind
public defstruct WireKind <: Kind 
public defstruct PoisonKind <: Kind 
public defstruct RegKind <: Kind
public defstruct InstanceKind <: Kind
public defstruct PortKind <: Kind
public defstruct NodeKind <: Kind
public defstruct MemKind <: Kind :
   ports : List<Symbol>
public defstruct ExpKind <: 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 with: (as-method => true)
   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 WSubIndex <: Expression :
   exp: Expression
   value: Int
   type: Type with: (as-method => true)
   gender: Gender with: (as-method => true)
public defstruct WSubAccess <: Expression :
   exp: Expression
   index: Expression
   type: Type with: (as-method => true)
   gender: Gender with: (as-method => true)
defstruct WIndexer <: Expression :
   exps: List<Expression>
   index: Expression
   type: Type with: (as-method => true)
   gender : Gender with: (as-method => true)
defstruct WVoid <: Expression
defstruct WDefInstance <: Stmt :
   info: FileInfo with: (as-method => true)
   name: Symbol
   module: Symbol
   type: Type

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

defn get-gender (s:Stmt|Port) -> Gender :
   match(s) :
      (s:DefWire|DefRegister) : BI-GENDER
      (s:WDefInstance|DefNode|DefInstance|DefPoison) : MALE
      (s:Begin|Connect|BulkConnect|Stop|Print|Empty) : UNKNOWN-GENDER
      (p:Port) :
         switch { _ == direction(p) } :
            INPUT : MALE
            OUTPUT : FEMALE

defmulti kind (e:Expression) -> Kind
defmethod kind (e:Expression) : ExpKind()

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

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

defn get-type (s:Stmt) -> Type :
   match(s) :
      (s:DefWire|DefPoison|DefRegister|WDefInstance) : type(s)
      (s:DefNode) : type(value(s))
      (s:DefMemory) : 
         val data-type = data-type(s)
         val depth = depth(s)
         ; Fields
         val addr = Field(`addr,DEFAULT,UIntType(IntWidth(ceil-log2(depth))))
         val en = Field(`en,DEFAULT,BoolType())
         val clk = Field(`clk,DEFAULT,ClockType())
         val rdata = Field(`data,REVERSE,data-type)
         val wdata = Field(`data,DEFAULT,data-type)
         val wmask = match(data-type) :
            (t:VectorType) : Field(`mask,DEFAULT,VectorType(BoolType(),size(t)))
            (t:BundleType) : 
               val fields* = for f in fields(t) map :
                  Field(name(f),flip(f),BoolType())
               Field(`mask, DEFAULT, BundleType(fields*))
         val ren = Field(`ren,DEFAULT,UIntType(IntWidth(1)))
         val wen = Field(`wen,DEFAULT,UIntType(IntWidth(1)))
         val raddr = Field(`raddr,DEFAULT,UIntType(IntWidth(ceil-log2(depth))))
         val waddr = Field(`waddr,DEFAULT,UIntType(IntWidth(ceil-log2(depth))))

         val read-type = BundleType(to-list([rdata,addr,en,clk]))
         val write-type = BundleType(to-list([wdata,wmask,addr,en,clk]))
         val readwrite-type = BundleType(to-list([wdata,wmask,waddr,wen,rdata,raddr,ren,clk]))

         val mem-fields = Vector<Field>()
         for x in readers(s) do :
            add(mem-fields,Field(x,DEFAULT,read-type))
         for x in writers(s) do :
            add(mem-fields,Field(x,DEFAULT,write-type))
         for x in readwriters(s) do :
            add(mem-fields,Field(x,DEFAULT,readwrite-type))
         BundleType(to-list(mem-fields))
      (s:DefInstance) : UnknownType()
      (s:Begin|Connect|BulkConnect|Stop|Print|Empty) : UnknownType()

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:WSubField,e2:WSubField) : 
         (name(e1) == name(e2)) and (exp(e1) == exp(e2))
      (e1:WSubIndex,e2:WSubIndex) : 
         (value(e1) == value(e2)) and (exp(e1) == exp(e2))
      (e1:WSubAccess,e2:WSubAccess) : 
         (index(e1) == index(e2)) and (exp(e1) == exp(e2))
      (e1:WVoid,e2:WVoid) : true
      (e1:WIndexer,e2:WIndexer) : 
         var bool = (length(exps(e1)) == length(exps(e2)))
         for (e1* in exps(e1),e2* in exps(e2)) do :
            bool = bool and (e1* == e2*)
         bool and (index(e1) == index(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

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

;============== 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

;========= TO TURN OFF ===========

var old-PRINT-TYPES : True|False = false
var old-PRINT-KINDS : True|False = false
var old-PRINT-WIDTHS : True|False = false
var old-PRINT-TWIDTHS : True|False = false
var old-PRINT-GENDERS : True|False = false
var old-PRINT-CIRCUITS : True|False = false
var old-PRINT-DEBUG : True|False = false
var old-PRINT-INFO : True|False = false
defmethod turn-off-debug (x:False) :
   old-PRINT-TYPES = PRINT-TYPES
   old-PRINT-KINDS = PRINT-KINDS
   old-PRINT-WIDTHS = PRINT-WIDTHS
   old-PRINT-TWIDTHS = PRINT-TWIDTHS
   old-PRINT-GENDERS = PRINT-GENDERS
   old-PRINT-CIRCUITS = PRINT-CIRCUITS
   old-PRINT-DEBUG = PRINT-DEBUG
   old-PRINT-INFO = PRINT-INFO
defmethod turn-on-debug (x:False) :
   PRINT-TYPES = old-PRINT-TYPES
   PRINT-KINDS = old-PRINT-KINDS
   PRINT-WIDTHS = old-PRINT-WIDTHS
   PRINT-TWIDTHS = old-PRINT-TWIDTHS
   PRINT-GENDERS = old-PRINT-GENDERS
   PRINT-CIRCUITS = old-PRINT-CIRCUITS
   PRINT-DEBUG = old-PRINT-DEBUG
   PRINT-INFO = old-PRINT-INFO

;=== ThePrinters ===

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:PoisonKind) : "poison"
      (k:RegKind) : "reg"
      (k:PortKind) : "port"
      (k:MemKind) : "mem"
      (k:NodeKind) : "node"
      (k:InstanceKind) : "inst"
      (k:ExpKind) : "exp"

defn hasGender (e:?) :
   e typeof Expression

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

defn hasType (e:?) :
   e typeof Expression|DefWire|DefRegister|DefPoison
      |VectorType|Port|UIntValue|SIntValue

defn hasKind (e:?) :
   e typeof Expression

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:WSubIndex) :
   print-all(o,[exp(e) "[" value(e) "]"])
   print-debug(o,e as ?)
defmethod print (o:OutputStream, e:WSubAccess) :
   print-all(o,[exp(e) "[" index(e) "]"])
   print-debug(o,e as ?)
defmethod print (o:OutputStream, e:WVoid) :
   print(o,"VOID")
   print-debug(o,e as ?)
defmethod print (o:OutputStream, c:WIndexer) :
   print-all(o, [exps(c) "[" index(c) "]"])
   print-debug(o,c as ?)
defmethod print (o:OutputStream, c:WDefInstance) :
   print-all(o, ["inst " name(c) " of " module(c) " : " type(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: WSubIndex) :
   WSubIndex(f(exp(e)), value(e), type(e), gender(e))
defmethod map (f: Expression -> Expression, e: WSubAccess) :
   WSubAccess(f(exp(e)), f(index(e)), type(e), gender(e))

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: WSubIndex) :
   WSubIndex(exp(e), value(e), f(type(e)), gender(e))
defmethod map (f: Type -> Type, e: WSubAccess) :
   WSubAccess(exp(e), index(e), f(type(e)), gender(e))

defmethod map (f: Type -> Type, s: WDefInstance) :
   WDefInstance(info(s),name(s),module(s),f(type(s)))

;================ WIDTH LIBRARY ====================

public val ONE = IntWidth(1)
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) ")"])

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)

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
;================ WORKING IR UTILS =========================
;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

; These functions do not error, but return Unknown Type
defn module-type (m:Module) -> Type : 
   BundleType(for p in ports(m) map : to-field(p))
defn 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 sub-type (v:Type) -> Type :
   match(v) :
      (v:VectorType) : type(v)
      (v) : UnknownType()
defn field-flip (v:Type,s:Symbol) -> Flip :
   match(v) :
      (v:BundleType) : 
         val ft = for p in fields(v) find : name(p) == s
         if ft != false : flip(ft as Field)
         else : DEFAULT ;This will get caught later
      (v) : DEFAULT

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
defn to-gender (d:Direction) -> Gender :
   switch {_ == d} :
      INPUT: MALE
      OUTPUT: FEMALE

;================= Remove Special Characters ========================
; Returns a new Circuit where all names have all special characters 
;    removed, except _.
;
;public defstruct RemoveSpecialChars <: Pass 
;public defmethod pass (b:RemoveSpecialChars) -> (Circuit -> Circuit) : remove-special-chars
;public defmethod name (b:RemoveSpecialChars) -> String : "Remove Special Characters"
;public defmethod short-name (b:RemoveSpecialChars) -> String : "rem-spec-chars"
;
;;------------ Helper Functions -------------
;
;defn get-new-string (n:Char) -> String :
;   switch {n == _} :
;      '_' : "__"
;      '~' : "$A"
;      '!' : "$B"
;      '@' : "$C"
;      '#' : "$D"
;      '$' : "$E"
;      '%' : "$F"
;      '^' : "$G"
;      '*' : "$H"
;      '-' : "$I"
;      '+' : "$J"
;      '=' : "$K"
;      '?' : "$L"
;      '/' : "$M"
;      else : to-string(n)
;
;;------------ Pass ------------------
;
;defn remove-special-chars (c:Circuit) :
;   defn rename (n:Symbol) -> Symbol :
;      val v = Vector<String>()
;      for c in to-string(n) do :
;         add(v,get-new-string(c))
;      val n* = symbol-join(v)
;      if key?(v-keywords,n*) : 
;         symbol-join([n* `_])
;      else :
;         n*
;   defn rename-t (t:Type) -> Type :
;      match(t) :
;         (t:BundleType) : BundleType $
;            for f in fields(t) map :
;               Field(rename(name(f)),flip(f),rename-t(type(f)))
;         (t:VectorType) : VectorType(rename-t(type(t)),size(t))
;         (t) : t
;   defn rename-e (e:Expression) -> Expression :
;      match(e) :
;         (e:Ref) : Ref(rename(name(e)),rename-t(type(e)))
;         (e:Subfield) : Subfield(rename-e(exp(e)),rename(name(e)),rename-t(type(e)))
;         (e:Index) : Index(rename-e(exp(e)),value(e),rename-t(type(e)))
;         (e:DoPrim) : DoPrim{op(e),_,consts(e),rename-t(type(e))} $ for x in args(e) map : rename-e(x)
;         (e:UIntValue) : e
;         (e:SIntValue) : e
;   defn rename-s (s:Stmt) -> Stmt :
;      match(s) :
;         (s:DefWire) : DefWire(info(s),rename(name(s)),rename-t(type(s)))
;         (s:DefPoison) : DefPoison(info(s),rename(name(s)),rename-t(type(s)))
;         (s:DefRegister) : DefRegister(info(s),rename(name(s)),rename-t(type(s)),rename-e(clock(s)),rename-e(reset(s)))
;         (s:WDefInstance) : WDefInstance(info(s),rename(name(s)),rename-e(module(s)))
;         (s:DefMemory) : DefMemory(info(s),rename(name(s)),rename-t(type(s)),seq?(s),rename-e(clock(s)),size(s))
;         (s:DefNode) : DefNode(info(s),rename(name(s)),rename-e(value(s)))
;         (s:DefAccessor) : DefAccessor(info(s),rename(name(s)),rename-e(source(s)),rename-e(index(s)),acc-dir(s))
;         (s:Conditionally) : Conditionally(info(s),rename-e(pred(s)),rename-s(conseq(s)),rename-s(alt(s)))
;         (s:Begin) : Begin $ for b in body(s) map : rename-s(b)
;         (s:OnReset) : OnReset(info(s),rename-e(loc(s)),rename-e(exp(s)))
;         (s:BulkConnect) : BulkConnect(info(s),rename-e(loc(s)),rename-e(exp(s)))
;         (s:Connect) : Connect(info(s),rename-e(loc(s)),rename-e(exp(s)))
;         (s:EmptyStmt) : s
;         (s:StopStmt) : s
;         (s:PrintfStmt) : PrintfStmt(info(s),string(s),map(rename-e,args(s)))
;
;   Circuit(info(c),modules*, rename(main(c))) where :
;      val modules* =
;         for m in modules(c) map :
;            match(m) :
;               (m:InModule) : 
;                  val ports* = for p in ports(m) map :
;                     Port(info(p),rename(name(p)),direction(p),rename-t(type(p)))
;                  InModule(info(m),rename(name(m)), ports*, rename-s(body(m)))
;               (m:ExModule) : m


;================= 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) :
;   defn is-temp? (n:Symbol) -> True|False :
;      to-string(n)[0] == 'T'
;   defn temp-elim (m:InModule) : 
;      val h = HashTable<Symbol,Expression>(symbol-hash)
;      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)
;      InModule(info(m),name(m), ports(m), temp-elim-s(body(m)))
;
;   Circuit(info(c),modules*, main(c)) where :
;      val modules* =
;         for m in modules(c) map :
;            match(m) :
;               (m:InModule) : temp-elim(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) -> 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:SubIndex) : WSubIndex(exp(e), value(e), type(e), UNKNOWN-GENDER)
         (e:SubAccess) : WSubAccess(exp(e), index(e), type(e), UNKNOWN-GENDER)
         (e) : e
   defn to-stmt (s:Stmt) -> Stmt : 
      match(map(to-exp,s)) :
         (s:DefInstance) : WDefInstance(info(s),name(s),module(s),UnknownType())
         (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

;=============== 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)] = WireKind()
            (s:DefPoison) : kinds[name(s)] = PoisonKind()
            (s:DefNode) : kinds[name(s)] = NodeKind()
            (s:DefRegister) : kinds[name(s)] = RegKind()
            (s:WDefInstance) : kinds[name(s)] = InstanceKind()
            (s:DefMemory) : kinds[name(s)] = MemKind(append-all([readers(s) writers(s) readwriters(s)]))
            (s) : false
         map(find-stmt,s)

      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)
      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.



; ------------------ Utils -------------------------

defn set-type (s:Stmt,t:Type) -> Stmt :
   match(s) :
      (s:DefWire) : DefWire(info(s),name(s),t)
      (s:DefRegister) : DefRegister(info(s),name(s),t,clock(s),reset(s),init(s))
      (s:DefMemory) : DefMemory(info(s),name(s),t,depth(s),write-latency(s),read-latency(s),readers(s),writers(s),readwriters(s))
      (s:DefNode) : s
      (s:DefPoison) : DefPoison(info(s),name(s),t)


; ------------------ 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 infer-types (c:Circuit) -> Circuit :
   val module-types = HashTable<Symbol,Type>(symbol-hash)
   defn infer-types (m:Module) -> Module :
      val types = HashTable<Symbol,Type>(symbol-hash)
      defn infer-types-e (e:Expression) -> Expression :
         match(map(infer-types-e,e)) :
            (e:WRef) : WRef(name(e), types[name(e)],kind(e),gender(e))
            (e:WSubField) : WSubField(exp(e),name(e),field-type(type(exp(e)),name(e)),gender(e))
            (e:WSubIndex) : WSubIndex(exp(e),value(e),sub-type(type(exp(e))),gender(e))
            (e:WSubAccess) : WSubAccess(exp(e),index(e),sub-type(type(exp(e))),gender(e))
            (e:DoPrim) : set-primop-type(e)
            (e:UIntValue|SIntValue) : e
      defn infer-types-s (s:Stmt) -> Stmt :
         match(map(infer-types-e,s)) :
            (s:DefWire|DefPoison|DefRegister|DefMemory|DefNode) : 
               val t = remove-unknowns(get-type(s))
               types[name(s)] = t
               set-type(s,t)
            (s:WDefInstance) :
               types[name(s)] = module-types[module(s)]
               WDefInstance(info(s),name(s),module(s),module-types[module(s)])
            (s) : map(infer-types-s,s)
      for p in ports(m) do :
         types[name(p)] = type(p)
      match(m) :
         (m:InModule) :
            val s* = infer-types-s(body(m))
            InModule(info(m),name(m),ports(m),s*)
         (m:ExModule) : m

   ; MAIN
   val modules* = 
      for m in modules(c) map :
         val ports* = 
            for p in ports(m) map : 
               Port(info(p),name(p),direction(p),remove-unknowns(type(p)))
         match(m) :
            (m:InModule) : InModule(info(m),name(m),ports*,body(m))
            (m:ExModule) : ExModule(info(m),name(m),ports*)

   for m in modules* do :
      module-types[name(m)] = module-type(m)
   Circuit{info(c), _, main(c) } $ 
      for m in modules* map :
         infer-types(m)

;============= RESOLVE 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). 
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"

defn resolve-genders (c:Circuit) :
   defn resolve-e (e:Expression,g:Gender) -> Expression :
      match(e) :
         (e:WRef) : WRef(name(e),type(e),kind(e),g)
         (e:WSubField) : 
            val exp* = 
               switch { _ == field-flip(type(exp(e)),name(e)) } :
                  DEFAULT : resolve-e(exp(e),g)
                  REVERSE : resolve-e(exp(e),swap(g))
            WSubField(exp*,name(e),type(e),g)
         (e:WSubIndex) : 
            val exp* = resolve-e(exp(e),g)
            WSubIndex(exp*,value(e),type(e),g)
         (e:WSubAccess) : 
            val exp* = resolve-e(exp(e),g)
            val index* = resolve-e(index(e),MALE)
            WSubAccess(exp*,index*,type(e),g)
         (e:WIndexer) :
            val exps* = map(resolve-e{_,g},exps(e))
            val index* = resolve-e(index(e),MALE)
            WIndexer(exps*,index*,type(e),g)
         (e) : map(resolve-e{_,g},e)
         
   defn resolve-s (s:Stmt) -> Stmt :
      match(s) :
         (s:Connect) : 
            val loc* = resolve-e(loc(s),FEMALE)
            val exp* = resolve-e(exp(s),MALE)
            Connect(info(s),loc*,exp*)
         (s:BulkConnect) :
            val loc* = resolve-e(loc(s),FEMALE)
            val exp* = resolve-e(exp(s),MALE)
            BulkConnect(info(s),loc*,exp*)
         (s) : 
            map{resolve-s,_} $ map(resolve-e{_,MALE},s)
   Circuit(info(c),modules*, main(c)) where :
      val modules* = 
         for m in modules(c) map :
            match(m) :
               (m:InModule) :
                  val body* = resolve-s(body(m))
                  InModule(info(m),name(m),ports(m),body*)
               (m:ExModule) : m

;;============== EXPAND ACCESSORS ================================
; This pass expands non-memory accessors into DecFromIndexer or
;   ConnectFromIndexed. All elements of the vector are 
;   explicitly written out, then indexed. Depending on the gender
;   of the accessor, it is transformed into DecFromIndexer (male) or
;   DecToIndexer (female)

public defstruct ExpandAccesses <: Pass
public defmethod pass (b:ExpandAccesses) -> (Circuit -> Circuit) : expand-accesses
public defmethod name (b:ExpandAccesses) -> String : "Expand Accesses"
public defmethod short-name (b:ExpandAccesses) -> String : "expand-accesses"

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

defn expand-accesses (c:Circuit) :
   defn expand-e (e:Expression) -> Expression :
      match(map(expand-e,e)) :
         (e:WSubAccess) : 
            val ls = expand-vector(exp(e),gender(e))
            WIndexer(ls,index(e),type(e),gender(e))
         (e) : e
                  
   defn expand-s (s:Stmt) -> Stmt :
      map{expand-s,_} $ map(expand-e,s)

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


;================ EXPAND CONNECTS ==================
public defstruct ExpandConnects <: Pass
public defmethod pass (b:ExpandConnects) -> (Circuit -> Circuit) : expand-connects
public defmethod name (b:ExpandConnects) -> String : "Expand Connects"
public defmethod short-name (b:ExpandConnects) -> String : "expand-connects"

;---------------- UTILS ------------------
defn get-size (e:Expression) -> Int : get-size(type(e))
defn get-size (t:Type) -> Int :
   match(t) :
      (t:BundleType) : 
         var sum = 0
         for f in fields(t) do : 
            sum = sum + get-size(type(f))
         sum
      (t:VectorType) : size(t) * get-size(type(t))
      (t) : 1
defn get-flip (t:Type, i:Int, f:Flip) -> Flip :
   if i >= get-size(t) : error("Shouldn't be here")
   match(t) :
      (t:UIntType|SIntType|ClockType) : f
      (t:BundleType) : label<Flip> ret : 
         var n = i
         for x in fields(t) do :
            if n < get-size(type(x)) : 
               ret(get-flip(type(x),n,flip(x) * f))
            else : 
               n = n - get-size(type(x))
         error("Shouldn't be here")
      (t:VectorType) : label<Flip> ret : 
         var n = i
         for j in 0 to size(t) do :
            if n < get-size(type(t)) : 
               ret(get-flip(type(t),n,f))
            else : 
               n = n - get-size(type(t))
         error("Shouldn't be here")
defn get-point (e:Expression) -> Int :
   match(e) :
      (e:WRef) : 0
      (e:WSubField) : 
         var i = -1 
         for f in fields(type(exp(e)) as BundleType) find :
            i = i + 1
            name(f) == name(e)
         get-point(exp(e)) + i
      (e:WSubIndex) :
         get-point(exp(e)) + value(e)
      (e:WIndexer) :
         get-point(exps(e)[0])
defn get-valid-points (t1:Type,t2:Type,flip1:Flip,flip2:Flip) -> List<[Int,Int]> :
   match(t1,t2) :
      (t1:UIntType,t2:UIntType) : 
         if flip1 == flip2 : list([0, 0])
         else: list()
      (t1:SIntType,t2:SIntType) :
         if flip1 == flip2 : list([0, 0])
         else: list()
      (t1:BundleType,t2:BundleType) :
         val points = Vector<[Int,Int]>()
         for i in 0 to length(fields(t1)) do :
            for j in 0 to length(fields(t2)) do :
               val f1 = fields(t1)[i]
               val f2 = fields(t2)[j]
               if name(f1) == name(f2) :
                  val ls = get-valid-points(type(f1),type(f2),flip1 * flip(f1),
                     flip2 * flip(f2)) 
                  for x in ls do :
                     add(points,[x[0] + i, x[1] + j])
         to-list(points)
      (t1:VectorType,t2:VectorType) :
         val points = Vector<[Int,Int]>()
         for i in 0 to min(size(t1),size(t2)) do :
            val ls = get-valid-points(type(t1),type(t2),flip1,flip2)
            for x in ls do :
               add(points,[x[0] + i, x[1] + i])
         to-list(points)
defn create-exps (n:Symbol, t:Type) -> List<Expression> :
   create-exps(WRef(n,t,ExpKind(),UNKNOWN-GENDER))
defn create-exps (e:WRef|WSubField|WSubIndex) -> List<Expression> :
   match(type(e)) : 
      (t:UIntType|SIntType|ClockType) : list(e)
      (t:BundleType) : 
         for f in fields(t) map-append :
            create-exps(WSubField(e,name(f),type(f),gender(e) * flip(f)))
      (t:VectorType) :
         for i in 0 to size(t) map-append :
            create-exps(WSubIndex(e,i,type(t),gender(e)))

;---------------- Pass ---------------------

defn expand-connects (c:Circuit) -> Circuit :
   defn expand-connects (m:InModule) -> InModule :
      val exp-lib = HashTable<Symbol,List<Expression>>(symbol-hash)
      defn create-lib (s:Stmt) -> Stmt :
         match(s) :
            (s:DefWire|DefRegister|WDefInstance|DefNode|DefPoison) : ;TODO Memories?
               exp-lib[name(s)] = create-exps(name(s),get-type(s))
               s
            (s) : map(create-lib,s)
      defn expand-e (e:Expression, point:Int) -> Expression :
         defn lookup-exp (e:Expression, point:Int) -> Expression :
            match(e) :
               (e:WRef) : exp-lib[name(e)][point]
               (e:WSubField|WSubIndex) : lookup-exp(exp(e), point + get-point(e))
               (e) : error("Shouldn't be here")
         match(e) :
            (e:WRef|WSubField|WSubIndex) : lookup-exp(e,point)
            (e:WIndexer) : 
               val exps* = 
                  for e* in exps(e) map :
                     expand-e(e*,point)
               WIndexer(exps*,index(e),type(exps*[0]),gender(exps*[0]))
            (e:DoPrim) : e
            (e) : e
      defn expand-s (s:Stmt) -> Stmt :
         match(s) :
            (s:Connect) :
               val n = get-size(loc(s))
               val connects = Vector<Stmt>()
               for i in 0 to n do :
                  val loc* = expand-e(loc(s),i)
                  val exp* = expand-e(exp(s),i)
                  add{connects,_} $
                     switch { _ == get-flip(type(loc(s)),i,DEFAULT) } :
                        DEFAULT : Connect(info(s),loc*,exp*)
                        REVERSE : Connect(info(s),exp*,loc*)
               Begin(to-list(connects))
            (s:BulkConnect) :
               val ls = get-valid-points(type(loc(s)),type(exp(s)),DEFAULT,DEFAULT)
               val connects = Vector<Stmt>()
               for x in ls do :
                  val loc* = expand-e(loc(s),x[0])
                  val exp* = expand-e(exp(s),x[1])
                  add{connects,_} $
                     switch { _ == get-flip(type(loc(s)),x[0],DEFAULT) } :
                        DEFAULT : Connect(info(s),loc*,exp*)
                        REVERSE : Connect(info(s),exp*,loc*)
               Begin(to-list(connects))
            (s) : map(expand-s,s)

      for p in ports(m) do :
         exp-lib[name(p)] = create-exps(name(p),type(p))
      create-lib(body(m))
      InModule(info(m),name(m),ports(m),expand-s(body(m)))

   Circuit(info(c),modules*, main(c)) where :
      val modules* = 
         for m in modules(c) map :
            match(m) :
               (m:ExModule) : m
               (m:InModule) : expand-connects(m)


;;;================ REPLACE INDEXERS =========================
; This pass inlines all accessors to non-memory vector typed
;   components.

public defstruct ReplaceIndexers <: Pass
public defmethod pass (b:ReplaceIndexers) -> (Circuit -> Circuit) : replace-indexer
public defmethod name (b:ReplaceIndexers) -> String : "Replace Indexer"
public defmethod short-name (b:ReplaceIndexers) -> String : "replace-indexers"

public defn replace-indexer (c:Circuit) -> Circuit :
   defn mux-chain (exps:List<Expression>,i:Int,index:Expression) -> Expression :
      if length(exps) == 1 : head(exps)
      else : MUX(EQV(uint(i),index),head(exps),mux-chain(tail(exps),i + 1,index))
   defn when-chain (exps:List<Expression>,e:Expression,index:Expression,info:FileInfo) -> Stmt :
      val stmts = Vector<Stmt>()
      for (x in exps,i in 0 to length(exps)) do :
         add(stmts,Conditionally(info,EQV(uint(i),index),Connect(info,x,e),Empty()))
      Begin(to-list(stmts))
   defn replace-e (e:Expression) -> Expression :
      match(map(replace-e,e)) :
         (e:WIndexer) : 
            if gender(e) == MALE : mux-chain(exps(e),0,index(e))
            else : e ;is handled in replace-s
         (e) : e
   defn replace-s (s:Stmt) -> Stmt :
      match(map(replace-e,s)) :
         (s:Connect) :
            match(loc(s)) :
               (e:WIndexer) : when-chain(exps(e),exp(s),index(e),info(s))
               (e) : s
         (s) : map(replace-s, s)
   Circuit{info(c),_,main(c)} $
      for m in modules(c) map :
         match(m) :
            (m:ExModule) : m
            (m:InModule) : InModule(info(m),name(m),ports(m),replace-s(body(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"

; ========== Expand When Utilz ==========

defn get-entries (hash:HashTable<Expression,Expression>,exps:Streamable<Expression>) -> HashTable<Expression,Expression> :
   val hash* = HashTable<Expression,Expression>(exp-hash)
   for e in exps do :
      val value = get?(hash,e,false)
      match(value) :
         (value:Expression) : hash*[e] = value
         (value:False) : false
   hash*
defn get-female-refs (n:Symbol,t:Type,g:Gender) -> List<Expression> :
   val exps = create-exps(WRef(n,t,ExpKind(),g))
   val exps* = Vector<Expression>()
   for i in 0 to length(exps) do :
      switch { _ == get-gender(t,i,g)} :
         BI-GENDER : add(exps*,exps[i])
         FEMALE : add(exps*,exps[i])
         else : false
   to-list(exps*)
defn get-gender (t:Type, i:Int, g:Gender) -> Gender :
   val f = get-flip(t,i,DEFAULT)
   g * f
defn print-hash (h:HashTable<Expression,Expression>) :
   for x in h do :
      println(x)

; ------------ Pass -------------------
defn expand-whens (c:Circuit) -> Circuit :
   defn void-all (m:InModule) -> InModule :
      defn void-all-s (s:Stmt) -> Stmt :
         match(s) : 
            (s:DefWire|DefRegister|WDefInstance|DefMemory) : 
               val voids = Vector<Stmt>()
               for e in get-female-refs(name(s),get-type(s),get-gender(s)) do :
                  add(voids,Connect(info(s),e,WVoid()))
               Begin(List(s,to-list(voids)))
            (s) : map(void-all-s,s)
      val voids = Vector<Stmt>()
      for p in ports(m) do :
         for e in get-female-refs(name(p),type(p),get-gender(p)) do :
            add(voids,Connect(info(p),e,WVoid()))
      val body* = void-all-s(body(m))
      InModule(info(m),name(m),ports(m),Begin(list(Begin(to-list(voids)),body*)))

   defn expand-whens (m:InModule) -> [HashTable<Expression,Expression> Vector<Stmt>] :
      val simlist = Vector<Stmt>()
      defn expand-whens (s:Stmt,netlist:HashTable<Expression,Expression>,p:Expression) -> Stmt :
         match(s) : 
            (s:Connect) : netlist[loc(s)] = exp(s)
            (s:Conditionally) :
               val exps = Vector<Expression>()
               defn prefetch (s:Stmt) -> Stmt: 
                  match(s) :
                     (s:Connect) : 
                        add(exps,loc(s))
                        s
                     (s) : map(prefetch,s)
               prefetch(conseq(s))
               val c-netlist = get-entries(netlist,exps)
               expand-whens(conseq(s),c-netlist,AND(p,pred(s)))
               expand-whens(alt(s),netlist,AND(p,NOT(pred(s))))
               for lvalue in keys(c-netlist) do :
                  val value = get?(netlist,lvalue,false)
                  match(value) :
                     (value:Expression) :
                        netlist[lvalue] = MUX(pred(s),c-netlist[lvalue],value)
                     (value:False) :
                        netlist[lvalue] = c-netlist[lvalue]
            (s:Print|Stop) : add(simlist,Conditionally(info(s),p,s,Empty()))
            (s) : map(expand-whens{_,netlist,p},s)
         s
      val netlist = HashTable<Expression,Expression>(exp-hash)
      expand-whens(body(m),netlist,one)

      [ netlist simlist ]

   defn create-module (netlist:HashTable<Expression,Expression>,simlist:Vector<Stmt>,m:InModule) -> InModule :
      val stmts = Vector<Stmt>()
      defn replace-void (e:Expression,rvalue:Expression) -> Expression :
         match(rvalue) :
            (rv:WVoid) : e
            (rv) : map(replace-void{e,_},rv)
      defn create (s:Stmt) -> Stmt :
         match(s) :
            (s:DefWire|DefRegister|WDefInstance|DefMemory) : 
               add(stmts,s)
               for e in get-female-refs(name(s),get-type(s),get-gender(s)) do :
                  val rvalue = 
                     if s typeof DefRegister : replace-void(e,netlist[e])
                     else : netlist[e]
                  add(stmts,Connect(info(s),e,rvalue))
            (s:DefPoison|DefNode|Stop|Print) : 
               add(stmts,s)
            (s) : map(create,s)
         s
      create(body(m))
      for p in ports(m) do :
         for e in get-female-refs(name(p),type(p),get-gender(p)) do :
            add(stmts,Connect(info(p),e,netlist[e]))
      for x in simlist do :
         add(stmts,x)
      InModule(info(m),name(m),ports(m),Begin(to-list(stmts)))

   val voided-modules = 
      for m in modules(c) map :
         match(m) :
            (m:ExModule) : m
            (m:InModule) : 
               val m* = void-all(m as InModule)
               m*
   val modules* =
      for m in voided-modules map :
         match(m) :
            (m:ExModule) : m
            (m:InModule) : 
               val [netlist simlist] = expand-whens(m)
               create-module(netlist,simlist,m)
   Circuit(info(c),modules*,main(c))


;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 ===========



;Can either check initialization here or in separate pass
;defn expand-whens (c:Circuit)
;   
;   Circuit(info(c),modules*, main(c)) where :
;      val modules* = 
;         for m in modules(c) map :
;            expand-whens(m)





; 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.

;---------------- Helper Functions --------------
;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>, rsignals:HashTable<Symbol,Expression>) -> HashTable<Symbol,SymbolicValue> :
;   val table = HashTable<Symbol,SymbolicValue>(symbol-hash)
;   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) : 
;               if r typeof SVNul : a
;               else : SVMux(rsignals[i],r,a)
;            (a:SymbolicValue,r:False) : a
;            (a:False,r:SymbolicValue) : SVMux(rsignals[i],r,SVNul())
;            (a:False,r:False) : error("Shouldn't be here")
;   table
;
;defn mark (vs:Vector<[Stmt,Expression]>,pred:Expression) -> False :
;   for i in 0 to length(vs) do :
;      val [s,e] = vs[i]
;      vs[i] = [s, AND(e,pred)]
;
;; ------ Print Debug Info ------
;defn print-table (t:HashTable<Symbol,SymbolicValue>,s:String) :
;   println-debug(s)
;   for x in t do : println-debug(x)
;
;
;defn build-tables (s:Stmt, 
;                   assign:HashTable<Symbol,SymbolicValue>,
;                   resets:HashTable<Symbol,SymbolicValue>,
;                   flattn:HashTable<Symbol,True|False>,
;                   rsignals:HashTable<Symbol,Expression>,
;                   simuls:Vector<[Stmt,Expression]>,
;                   ) -> False :
;   match(s) :
;      (s:DefWire) :
;         assign[name(s)] = SVNul()
;         flattn[name(s)] = true
;      (s:DefRegister) : 
;         assign[name(s)] = SVNul()
;         flattn[name(s)] = true
;         rsignals[name(s)] = reset(s)
;         resets[name(s)] = SVNul()
;      (s:DefAccessor) : 
;         assign[name(s)] = SVNul()
;         flattn[name(s)] = false
;      (s:WDefInstance) : ;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)
;         val simuls-c = Vector<[Stmt,Expression]>()
;         val simuls-a = Vector<[Stmt,Expression]>()
;         build-tables(conseq(s),assign-c,resets-c,flattn,rsignals,simuls-c)
;         build-tables(alt(s),assign-a,resets-a,flattn,rsignals,simuls-a)
;         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
;
;         mark(simuls-c,pred(s))
;         mark(simuls-a,DoPrim(BIT-NOT-OP,list(pred(s)),list(),UIntType(IntWidth(1))))
;         add-all(simuls,simuls-c)
;         add-all(simuls,simuls-a)
;         
;         print-table(assign-c,"TABLE-C")
;         print-table(assign-a,"TABLE-A")
;         print-table(assign,"TABLE")
;         print-table(resets-c,"RESET-C")
;         print-table(resets-a,"RESET-A")
;         print-table(resets,"RESET")
;      (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,rsignals,simuls)
;      (s:StopStmt|PrintfStmt) : 
;         add(simuls,[s one])
;      (s:DefMemory|DefPoison|DefNode|EmptyStmt) : false
;
;
;defn mark-referenced (referenced?:HashTable<Symbol,True>, s:Stmt) -> False :
;   defn mark-referenced-e (e:Expression) -> Expression :
;      match(map(mark-referenced-e,e)) :
;         (e:WRef) : 
;            referenced?[name(e)] = true
;            e
;         (e) : e
;   do(mark-referenced{referenced?,_:Stmt},s)
;   map(mark-referenced-e,s)
;   false
;
;defn mark-referenced (referenced?:HashTable<Symbol,True>, sv:SymbolicValue) -> SymbolicValue :
;   defn mark-referenced-e (e:Expression) -> Expression :
;      match(map(mark-referenced-e,e)) :
;         (e:WRef) : 
;            referenced?[name(e)] = true
;            e
;         (e) : e
;   map{mark-referenced-e,_} $ map(mark-referenced{referenced?,_:SymbolicValue},sv)
;
;defn is-referenced? (referenced?:HashTable<Symbol,True>, s:Stmt) -> True|False :
;   match(s) :
;      (s:DefPoison|DefWire|DefRegister|DefAccessor|DefMemory|DefNode) : key?(referenced?,name(s))
;      (s:WDefInstance) : true
;      (s:PrintfStmt|StopStmt|Conditionally) : true
;               
;;--------------- Expand Whens Pass -------------------
;
;public defn expand-whens (c:Circuit) -> Circuit :
;
;   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 not has-nul?(table[name(p)]) : 
;               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) : 
;            add(decs,s)
;         (s:DefMemory) : 
;            add(decs,s)
;         (s:DefPoison) : 
;            add(decs,s)
;         (s:DefWire) : 
;            add(decs,s)
;            val ref = WRef(name(s),type(s),NodeKind(),FEMALE)
;            if not has-nul?(table[name(s)]) : 
;               add{cons,_} $ Connect(info(s),ref,to-exp(table[name(s)]) as Expression)
;         (s:DefRegister) : 
;            add(decs,s)
;            val e = to-exp(table[name(s)])
;            match(e) : 
;               (e:Expression) : 
;                  val ref = WRef(name(s),type(s),NodeKind(),FEMALE)
;                  val en = to-exp(optimize $ get-write-enable(table[name(s)])) as Expression
;                  if en == one : 
;                     add{cons,_} $ Connect(info(s),ref,e)
;                  else :
;                     add{cons,_} $ Conditionally(info(s),en,Connect(info(s),ref,e),EmptyStmt())
;               (e:False) : false
;         (s:DefAccessor) : 
;            add(decs,s)
;            val t = type(s)
;            val n = name(s)
;            if gender(s) == FEMALE :
;               val ref = WRef(n,t,WriteAccessorKind(),FEMALE)
;               val e = to-exp(table[n])
;               match(e) :
;                  (e:Expression) : 
;                     val en = (to-exp $ optimize $ get-write-enable(table[n])) as Expression
;                     if en == one : 
;                        add{cons,_} $ Connect(info(s),ref,e)
;                     else :
;                        add{cons,_} $ Conditionally(info(s),en,Connect(info(s),ref,e),EmptyStmt())
;                  (e:False) : false
;         (s:WDefInstance) : 
;            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 not has-nul?(table[n]) : 
;                        add{cons,_} $ Connect(info(s),sref,to-exp(table[n]) as Expression)
;         (s:Connect|Conditionally|OnReset|Begin|EmptyStmt|StopStmt|PrintfStmt) : false
;      s
;   
;   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)
;            val rsignals = HashTable<Symbol,Expression>(symbol-hash)
;            val simuls = Vector<[Stmt,Expression]>()
;   
;            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,rsignals,simuls)
;            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,rsignals)
;            ;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)
;
;            for se in simuls do :
;               val [s e] = se
;               if e == one : add(decs,s)
;               else : add(decs,Conditionally(info(s),e,s,EmptyStmt()))
;
;            val referenced? = HashTable<Symbol,True>(symbol-hash)
;            for x in table do :
;               mark-referenced(referenced?,value(x))
;               if value(x) != SVNul() :
;                  referenced?[key(x)] = true
;            for x in decs do :
;               mark-referenced(referenced?,x)
;            val decs* = Vector<Stmt>()
;            for x in decs do :
;               if is-referenced?(referenced?,x) : add(decs*,x)
;               
;            InModule(info(m),name(m),ports(m),Begin(to-list(append(decs*,to-list(cons)))))
;
;   val c* = Circuit(info(c),modules*, main(c)) where :
;      val modules* = 
;         for m in modules(c) map :
;            expand-whens(m)
;   ;throw(PassExceptions(errors)) when not empty?(errors)
;   c*

;;================ Module Duplication ==================
; Duplicates modules so that no module is instantiated 
;   more than once.

;public defstruct ModuleDuplication <: Pass 
;public defmethod pass (b:ModuleDuplication) -> (Circuit -> Circuit) : module-duplication
;public defmethod name (b:ModuleDuplication) -> String : "Module Duplication"
;public defmethod short-name (b:ModuleDuplication) -> String : "mod-dup"
;
;;------------ Helper Functions -------------
;
;;------------ Pass ------------------
;
;public defn module-duplication (c:Circuit) :
;   val modules* = Vector<Module>()
;   val m-names = HashTable<Symbol,Int>(symbol-hash)
;   defn rename (n:Symbol) -> Symbol :
;      val int = get?(m-names,n,0)
;      m-names[n] = int + 1
;      val n* = symbol-join([n module-expand-delin int])
;      val m = for x in modules(c) find : name(x) == n
;      match(m) :
;         (m:InModule) : add(modules*,InModule(info(m),n*, ports(m), rename-s(body(m))))
;         (m:ExModule) : add(modules*,ExModule(info(m),n*, ports(m)))
;         (m:False) : error("Shouldn't be here")
;      n*
;
;   defn rename-e (e:Expression) -> Expression :
;      match(e) :
;         (e:Ref) : Ref(rename(name(e)),type(e))
;         (e) : error("Shouldn't be here")
;   defn rename-s (s:Stmt) -> Stmt :
;      match(s) :
;         (s:WDefInstance) : WDefInstance(info(s),name(s),rename-e(module(s)))
;         (s) : map(rename-s,s)
;
;   val top = for m in modules(c) find : name(m) == main(c)
;   match(top) :
;      (m:InModule) : add(modules*,InModule(info(m),name(m), ports(m), rename-s(body(m))))
;      (m:ExModule) : m
;      (m:False) : error("Shouldn't be here")
;      
;   Circuit(info(c),to-list(modules*), main(c)) 
;
;
;;;================ Deadcode Elimination ===================
;; Walks the circuit, starting from the outputs from the top 
;;   level module. All components that are not reached are
;;   deleted
;
;public defstruct DeadcodeElimination <: Pass 
;public defmethod pass (b:DeadcodeElimination) -> (Circuit -> Circuit) : deadcode-elimination
;public defmethod name (b:DeadcodeElimination) -> String : "Deadcode Elimination"
;public defmethod short-name (b:DeadcodeElimination) -> String : "deadcode-elim"
;
;;------------ Helper Functions -------------
;
;;------------ Pass ------------------
;
;public defn deadcode-elimination (c:Circuit) : c
;
;;;================ 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 definterface Constraint
public defstruct WGeq <: Constraint :
   loc : Width
   exp : Width
public defmethod print (o:OutputStream, c:WGeq) :
   print-all(o,[ loc(c) " >= " exp(c)])
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(plus(width(w1),width(w2)))
               (w1,w2) : w
         (w:MinusWidth) : 
            match(arg1(w),arg2(w)) :
               (w1:IntWidth,w2:IntWidth) : IntWidth(minus(width(w1),width(w2)))
               (w1,w2) : w
         (w:ExpWidth) : 
            match(arg1(w)) :
               (w1:IntWidth) : IntWidth(pow(to-long(2),width(w1)) - to-long(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:MinusWidth) :
            if arg1(w) == VarWidth(n) : arg1(w)
            else : 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:ClockType) : IntWidth(1)
      (t) : error("No width!")
public defn width! (e:Expression) -> Width : width!(type(e))

defn reduce-var-widths (c:Circuit,h:HashTable<Symbol,Width>) -> Circuit :
   defn evaluate (w:Width) -> Width :
      defn apply (a:Long|False,f:(Long) -> Long) -> Long|False :
         if a typeof Long : f(a as Long)
         else : false
      defn apply (a:Long|False,b:Long|False, f: (Long,Long) -> Long) -> Long|False :
         if a typeof Long and b typeof Long : f(a as Long, b as Long)
         else : false
      defn apply-l (l:List<Long|False>,f:(Long,Long) -> Long) -> Long|False :
         if length(l) == 0 : to-long(0)
         else : apply(head(l),apply-l(tail(l),f),f)
      defn max (a:Long,b:Long) -> Long :
         if a >= b : a
         else : b
      defn solve (w:Width) -> False|Long :
         match(w) :
            (w:VarWidth) : 
               val w* = get?(h,name(w),false)
               match(w*) : 
                  (w:VarWidth) : false
                  (w:False) : false
                  (w) : solve(w as Width)
            (w:MaxWidth) : apply-l(map(solve,args(w)),max)
            (w:PlusWidth) : apply(solve(arg1(w)),solve(arg2(w)),{plus(_,_)})
            (w:MinusWidth) : apply(solve(arg1(w)),solve(arg2(w)),{minus(_,_)})
            (w:ExpWidth) : apply(to-long(2),solve(arg1(w)),{minus(pow(_,_),to-long(1))})
            (w:IntWidth) : width(w)
            (w) : 
               println(w)
               error("Shouldn't be here")
   
      val s = solve(w)
      match(s) :
         (s:Long) : IntWidth(s)
         (s) : 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 infer-widths (c:Circuit) -> Circuit :
   val v = Vector<WGeq>()
   defn constrain (w1:Width,w2:Width) -> False : constrain(w1,w2,DEFAULT)
   defn constrain (w1:Width,w2:Width,f:Flip) -> False :
      switch { _ == f } :
         DEFAULT : add(v,WGeq(w1,w2))
         REVERSE : add(v,WGeq(w2,w1))
   defn get-constraints (t1:Type,t2:Type,f:Flip) -> False :
      match(t1,t2) :
         (t1:UIntType,t2:UIntType) : constrain(width(t1),width(t2))
         (t1:SIntType,t2:SIntType) : constrain(width(t1),width(t2))
         (t1:BundleType,t2:BundleType) : 
            for (f1 in fields(t1),f2 in fields(t2)) do :
               get-constraints(type(f1),type(f2),flip(f1) * f)
         (t1:VectorType,t2:VectorType) :
            get-constraints(type(t1),type(t2),f)
   defn get-constraints-e (e:Expression) -> Expression :
      match(map(get-constraints-e,e)) :
         (e:DoPrim) : 
            if op(e) == MUX-OP : 
               constrain(width!(args(e)[0]),ONE)
               constrain(ONE,width!(args(e)[0]))
            e
         (e) : e
   defn get-constraints (s:Stmt) -> Stmt :
      match(map(get-constraints-e,s)) : 
         (s:Connect) : 
            constrain(width!(loc(s)),width!(exp(s)))
            s
         (s:DefRegister) :
            constrain(width!(reset(s)),ONE)
            constrain(ONE,width!(reset(s)))
            get-constraints(type(s),type(init(s)),DEFAULT)
            s
         (s:Conditionally) : 
            add(v,WGeq(width!(pred(s)),ONE))
            add(v,WGeq(ONE,width!(pred(s))))
            map(get-constraints,s)
         (s) : map(get-constraints,s)
   
   for m in modules(c) do :
      match(m) :
         (m:InModule) : get-constraints(body(m))
         (m) : false
   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(c),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:WDefInstance) : 
;           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) inline-delin name(e)]),type(e),k,gender(e))
;               (k:MemKind) : e
;         (e) : e
;   defn rename (ref:Symbol,n:Symbol) -> Symbol : symbol-join([n inline-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) inline-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:DefPoison) : DefPoison(info(s),rename(name(s),n),type(s))
;         (s:DefRegister) : DefRegister(info(s),rename(name(s),n),type(s),clock(s),reset(s))
;         (s:WDefInstance) : error("Shouldn't be here")
;         (s:DefMemory) : DefMemory(info(s),rename(name(s),n),type(s),seq?(s),clock(s),size(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))
;
;;================= 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:WSubIndex) : error("Shouldn't be here")
;         (e) : e
;   defn to-stmt (s:Stmt) :
;     match(map(to-exp,s)) :
;        (e:DecFromIndexer) : error("Shouldn't be here")
;        (e:DecToIndexer) : 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
;
;
;;================= 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 split-exp (m:InModule) -> InModule :
   val v = Vector<Stmt>()
   val sh = get-sym-hash(m,keys(v-keywords))
   defn split-exp-s (s:Stmt) -> Stmt :
      val base = match(s) :
         (s:Connect) : lowered-name(loc(s))
         (s:DefNode) : name(s)
         (s:DefRegister) : name(s)
         (s) : `F
      defn split (e:Expression) -> Expression :
         val n = firrtl-gensym(base,sh)
         add(v,DefNode(info(s),n,e))
         WRef(n,type(e),kind(e),gender(e))
      defn split-exp-e (e:Expression,i:Int) -> Expression :
         match(map(split-exp-e{_,i + 1},e)) :
            (e:DoPrim) :
               if i > 0 : split(e)
               else : e
            (e) : e
      map{split-exp-e{_,0},_} $ map(split-exp-s,s)
   split-exp-s(body(m))
   InModule(info(m),name(m),ports(m),Begin(to-list(v)))

defn split-exp (c:Circuit) -> Circuit :
   val modules* = for m in modules(c) map :
      match(m) :
         (m:InModule) : split-exp(m)
         (m:ExModule) : m
   Circuit(info(c),modules*,main(c))

;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(e) :
;            (e:DoPrim) : 
;               ;var all-same-type? = true
;               ;for x in args(e) do :
;               ;   if type(x) != type(e) : all-same-type? = false
;               ;all-same-type? = false
;               ;if not all-same-type? : 
;                  ;val n* = 
;                  ;   if n typeof False : firrtl-gensym(`F,sh)
;                  ;   else : firrtl-gensym(symbol-join([n as Symbol temp-delin]),sh)
;                  val n* = 
;                     if n typeof False : firrtl-gensym(`F,sh)
;                     else : firrtl-gensym(n as Symbol,sh)
;                  add(v,DefNode(info,n*,map(split-exp-e{_,n,info},e)))
;                  Ref(n*,type(e))
;               ;else : e
;            (e) : map(split-exp-e{_,n,info},e)
;      defn f (s:Stmt) -> False: split-exp-s(s,v,sh)
;      match(s) :
;         (s:Begin) : 
;            do(f,s)
;         (s:Conditionally) : 
;            ;Predicate
;            val pred* = map(split-exp-e{_,full-name(pred(s)),info(s)},pred(s))
;
;            ;Connect TODO Broken for stop/printf
;            match(conseq(s)) :
;               (c:Connect) :
;                  val exp* = map(split-exp-e{_,full-name(loc(c)),info(c)},exp(c))
;                  val conseq* = Connect(info(c),loc(c),exp*)
;                  add(v,Conditionally(info(s),pred*,conseq*,alt(s)))
;               (c:PrintfStmt) :
;                  val args* = for x in args(c) map :
;                     map(split-exp-e{_,false,info(c)},x)
;                  val conseq* = PrintfStmt(info(c),string(c),args*)
;                  add(v,Conditionally(info(s),pred*,conseq*,alt(s)))
;               (c:StopStmt) :
;                  add(v,Conditionally(info(s),pred*,c,alt(s)))
;         (s:Connect) : 
;            val exp* = map(split-exp-e{_,full-name(loc(s)),info(s)},exp(s))
;            add(v,Connect(info(s),loc(s),exp*))
;         (s:PrintfStmt) : 
;            val args* = for x in args(s) map :
;               map(split-exp-e{_,false,info(s)},x)
;            add(v,PrintfStmt(info(s),string(s),args*))
;         (s:DefNode) : 
;            val exp* = map(split-exp-e{_,name(s),info(s)},value(s))
;            add(v,DefNode(info(s),name(s),exp*))
;         (s) : add(v,map(split-exp-e{_,false,info(s)},s))
;      false
;
;   ;val start-time = current-time-us()
;   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,keys(v-keywords))
;               ;val before = current-time-us() - start-time
;               ;println-all(["Before split: " before])
;               split-exp-s(body(m),v,sh)
;               ;val now = current-time-us() - start-time
;               ;println-all(["After split: " now])
;               ;println-all(["Diff: " now - before])
;               InModule(info(m),name(m),ports(m),Begin(to-list(v)))
;            (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)
;               ;println(st)
;               ;println(substring(st,length(os),length(st)))
;               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-type (t:Type) -> Type :
;      match(map(to-type,t)) :
;         (t:BundleType) : BundleType $ 
;            for f in fields(t) map : Field(rename(name(f)),flip(f),type(f))
;         (t) : t
;   defn to-exp (e:Expression) -> Expression :
;      map{to-type,_} $ 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 :
;     map{to-type,_} $ match(map(to-exp,s)) :
;        (s:DefWire) : DefWire(info(s),rename(name(s)),type(s))
;        (s:DefPoison) : DefPoison(info(s),rename(name(s)),type(s))
;        (s:DefRegister) : DefRegister(info(s),rename(name(s)),type(s),clock(s),reset(s))
;        (s:WDefInstance) : WDefInstance(info(s),rename(name(s)),module(s))
;        (s:DefMemory) : DefMemory(info(s),rename(name(s)),type(s),seq?(s),clock(s),size(s))
;        (s:DefNode) : DefNode(info(s),rename(name(s)),value(s))
;        (s:DefAccessor) : DefAccessor(info(s),rename(name(s)),source(s),index(s),acc-dir(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
;
;
;;========== Pad Widths ==================
;
;public defstruct Pad <: Pass
;public defmethod pass (b:Pad) -> (Circuit -> Circuit) : pad-widths
;public defmethod name (b:Pad) -> String : "Pad Widths"
;
;;------------ Helper Functions --------------
;defn int-width! (t:Type) -> Long :
;   match(width!(t)) :
;      (w:IntWidth) : width(w)
;      (w) : error("Non-int width")
;
;defn set-width (desired:Long,t:Type) -> Type :
;   match(t) :
;      (t:UIntType) : UIntType(IntWidth(desired))
;      (t:SIntType) : SIntType(IntWidth(desired))
;      (t) : error("Non-ground type")
;
;defn lmax (l1:Long, l2:Long) -> Long :
;   if l1 > l2 : l1
;   else : l2
;
;;------------- Pad Widths -------------------
;
;defn pad-widths-e (desired:Long,e:Expression) -> Expression :
;   defn trim (desired:Long, e:Expression) :
;     ;; println-all(["TRIM " desired " e " e])
;     DoPrim(BITS-SELECT-OP,list(e),list(to-int(to-string(desired)) - 1, 0),set-width(desired,type(e)))
;   defn pad (desired:Long, e:Expression) :
;     ;; println-all(["PAD " desired " e " e])
;     DoPrim(PAD-OP,list(e),list(to-int $ to-string(desired)),set-width(desired,type(e)))
;   defn trim-pad (desired:Long, e:Expression) :
;     val i = int-width!(type(e))
;     if i > desired : trim(desired, e)
;     else if i == desired : e
;     else : pad(desired, e)
;   defn self-pad-widths-e (e:Expression) -> Expression :
;     pad-widths-e(int-width!(type(e)), e)
;   ;; println-all(["PAD-E " desired " " e])
;   match(e) :
;      (e:DoPrim) :
;         val new-desired = reduce(lmax, to-long(0), map(int-width!{type(_)}, args(e)))
;         ;; println-all(["  NEW DESIRED " new-desired])
;         val e* =
;           if contains?([CONCAT-OP, DYN-SHIFT-RIGHT-OP, DYN-SHIFT-LEFT-OP], op(e)) :
;             DoPrim(op(e), map(self-pad-widths-e, args(e)), consts(e), type(e))
;           else if contains?([MUX-OP], op(e)) :
;             DoPrim(op(e), list(pad-widths-e(to-long(1), args(e)[0]), pad-widths-e(new-desired, args(e)[1]), pad-widths-e(new-desired, args(e)[2])), consts(e), type(e))
;           else :
;             map(pad-widths-e{new-desired,_},e)
;         trim-pad(desired, e*)
;      (e:Ref|Subfield|Index) : 
;         trim-pad(desired, e)
;      (e:UIntValue) : 
;         val i = int-width!(type(e))
;         if i > desired : trim(desired, e)
;         else : UIntValue(value(e),IntWidth(desired))
;      (e:SIntValue) : 
;         val i = int-width!(type(e))
;         if i > desired : trim(desired, e)
;         else : SIntValue(value(e),IntWidth(desired))
;      (e) : error(to-string $ e)
;
;defn pad-widths-s (s:Stmt) -> Stmt :
;   ;; println-all(["PAD-S " s])
;   match(map(pad-widths-s,s)) :
;      (s:Connect) : 
;         val i = int-width!(type(loc(s)))
;         val loc* = pad-widths-e(i,loc(s))
;         val exp* = pad-widths-e(i,exp(s))
;         Connect(info(s),loc*,exp*)
;      (s:PrintfStmt) : 
;         val args* = for x in args(s) map :
;            val i = int-width!(type(x))
;            pad-widths-e(i,x)
;         PrintfStmt(info(s),string(s),args*)
;      (s:DefNode) : 
;         val i = int-width!(type(value(s)))
;         val exp* = pad-widths-e(i,value(s))
;         DefNode(info(s),name(s),exp*)
;      (s:Conditionally) : 
;         val i = int-width!(type(pred(s)))
;         val pred* = pad-widths-e(i,pred(s))
;         Conditionally(info(s),pred*,conseq(s),alt(s))
;      (s) : s
;
;public defn pad-widths (c:Circuit) -> Circuit :
;   Circuit{info(c),_,main(c)} $
;      for m in modules(c) map :
;         match(m) :
;            (m:ExModule) : m
;            (m:InModule) : InModule(info(m),name(m),ports(m),pad-widths-s(body(m)))
;
;
;;============= Constant Propagation ================
;
public defstruct ConstProp <: Pass
public defmethod pass (b:ConstProp) -> (Circuit -> Circuit) : const-prop
public defmethod name (b:ConstProp) -> String : "Constant Propagation"
public defmethod short-name (b:ConstProp) -> String : "const-prop"

defn const-prop-e (e:Expression) -> Expression :
   match(map(const-prop-e,e)) :
      (e:DoPrim) : 
         switch {op(e) == _} :
            SHIFT-RIGHT-OP :
               match(args(e)[0]) :
                  (x:UIntValue) : 
                     val b = rsh(value(x),consts(e)[0])
                     UIntValue(b,width(type(e) as UIntType))
                  (x:SIntValue) : 
                     val b = rsh(value(x),consts(e)[0])
                     SIntValue(b,width(type(e) as SIntType))
                  (x) : e
            BITS-SELECT-OP : 
               match(args(e)[0]) :
                  (x:UIntValue) : 
                     val b = bits(value(x),consts(e)[0] + 1,consts(e)[1])
                     UIntValue(b,width(type(e) as UIntType))
                  (x) : e
            BIT-SELECT-OP : 
               match(args(e)[0]) :
                  (x:UIntValue) : 
                     val i = bit(value(x),consts(e)[0])
                     UIntValue(i,width(type(e) as UIntType))
                  (x) : e
            else : e
      (e) : e

defn const-prop-s (s:Stmt) -> Stmt :
   map{const-prop-e,_} $ map(const-prop-s,s)

public defn const-prop (c:Circuit) -> Circuit :
   Circuit{info(c),_,main(c)} $
      for m in modules(c) map :
         match(m) :
            (m:ExModule) : m
            (m:InModule) : InModule(info(m),name(m),ports(m),const-prop-s(body(m)))

;============= Condense Mems ================
;
;public defstruct CondenseMems <: Pass
;public defmethod pass (b:CondenseMems) -> (Circuit -> Circuit) : condense-mems
;public defmethod name (b:CondenseMems) -> String : "Condense Mems"
;public defmethod short-name (b:CondenseMems) -> String : "condense-mems"
;
;;------------- Utils ---------------
;
;defn concat (es:List<Expression>) -> Expression :
;   if length(es) == 1 : head(es)
;   else : CAT(head(es),cat(tail(es)))
;defn cast (t:Type,e:Expression) -> Expression :
;   match(t) :
;      (t:UIntType) : e
;      (t:SIntType) : DoPrim(AS-SINT-OP,list(e),list(),SIntType(get-width(t)))
;defn get-width-index (e:Expression) -> Long :
;   match(e) :
;      (e:WRef) : 0
;      (e:WSubField) :
;         var w = get-width-index(exp(e))
;         var found? = false
;         for f in fields(type(exp(e)) as BundleType) do :
;            if name(f) == name(e) :
;               found? = true
;            if found? == false :
;               w = w + get-width(type(f))
;         w
;      (e:WSubIndex) :
;         get-width-index(exp(e)) + get-width(type(e)) * value(e)
;defn root-ref (e:Expression) -> Expression :
;   match(e) :
;      (e:WRef) : e
;      (e:WSubField|WSubIndex) : root-ref(e)
;defn flatten (e:Expression) -> Expression :
;   match(e) :
;      (e:WRef) : e
;      (e:WSubField|WSubIndex) : 
;         val base = get-width-index(e)
;         val off = get-width(type(e))
;         DoPrim(BITS-SELECT-OP,list(root-ref(e)),list(base,off),UIntType(IntWidth(off)))
;         
;;------------- Pass ------------------

;defn condense-mems (m:InModule) -> InModule :
;   val mem-assigns = HashTable<Expression,Expression>(exp-hash)
;   defn collect-mems (s:Stmt) -> Stmt :
;      match(s) :
;         (s:Connect) : 
;   defn condense-mems-e (e:Expression) -> Expression :
;      val e* = match(e) :
;         (e:WRef|WSubField|WSubIndex) : 
;            if (kind(e) typeof MemKind) : cast(type(e),flatten(e))
;            else : e
;         (e:UIntValue|SIntValue) : e
;         (e:DoPrim) : map(condense-mems-e,e)
;   defn condense-mems (s:Stmt) -> Stmt :
;      match(s) :
;         (s:DefMemory) : 
;            val stmts = Vector<Stmt>()
;            val s* = map(flatten,s)
;            add(stmts,s*)
;            val mem = WRef(name(s),type(s),MemKind(),UNKNOWN-GENDER)
;            for f in fields(type(s) as BundleType) do :
;               val data-name = 
;                  if contains?(writers(s),name(f)) : `data
;                  else if contains(readwriters(s),name(f)) : `wdata
;                  else : false
;               match(data-name) :
;                  (f:False) : false
;                  (n:Symbol) :
;                     val port = WSubField(mem,name(f),type(f),UNKNOWN-GENDER)
;                     val es = create-exps(WSubField(port,n,field-type(type(port),n),UNKNOWN-GENDER))
;                     val e* = concat $ for e in es map :
;                        map(condense-mems-e,mem-assigns[e])
;                     add(stmts,Connect(info(s),WSubField(port,n,data-type(s*),UNKNOWN-GENDER),e*))
;            Begin(to-list(stmts))
;         (s:Connect) : 
;            if kind(loc(s)) typeof MemKind : EmptyStmt()
;            else : map(condense-mems-e, s)
;         (s) : map{condense-mems,_} $ map(condense-mems-e, s)
;   InModule(info(m),name(m),ports(m),condense-mems(body(m)))
;
;defn condense-mems (c:Circuit) -> Circuit :
;   Circuit{info(c),_,main(c)} $
;      for m in modules(c) map :
;         match(m) :
;            (m:ExModule) : m
;            (m:InModule) : condense-mems(m)

;============= Lower Types ================
;
public defstruct LowerTypes <: Pass
public defmethod pass (b:LowerTypes) -> (Circuit -> Circuit) : lower-types
public defmethod name (b:LowerTypes) -> String : "Lower Types"
public defmethod short-name (b:LowerTypes) -> String : "lower-types"

;------------- Utils ---------------
defn is-ground? (t:Type) -> True|False :
   match(t) :
      (t:UIntType|SIntType) : true
      (t) : false
defn mport? (ex:Expression) -> True|False :
   match(kind(ex)) :
      (k:MemKind) : match(ex) : 
         (ex:WRef|WSubIndex) : false
         (ex:WSubField) :
            var yes? = switch { _ == name(ex) } :
                  `wdata : true
                  `rdata : true
                  `data : true
                  `wmask : true
                  else : false
            yes? and match(exp(ex)) :
               (e:WSubField) : 
                  contains?(ports(kind(e) as MemKind),name(e)) and (exp(e) typeof WRef)
               (e) : false
         (ex) : false
      (k) : false
defn substitute (e:Expression, s:Symbol) -> Expression :
   match(e) :
      (e:WRef) : WRef(merge(name(e),s,`_),UnknownType(),kind(e),gender(e))
      (e) : map(substitute{_,s},e)
defn collect (e:Expression, s:Symbol) -> Expression :
   match(e) :
      (e:WSubField) : 
         if mport?(exp(e)) : substitute(e,s)
         else : collect(e,merge(name(e),s,`_))
      (e:WSubIndex) : collect(e,merge(to-symbol(value(e)),s,`_))
      (e) : e
defn lower-mem (e:Expression) -> Expression :
   match(e) :
      (e:WSubField) : collect(exp(e),name(e))
      (e:WSubIndex) : collect(exp(e),to-symbol(value(e)))
      (e) : e

defn merge (a:Symbol,b:Symbol,x:Symbol) -> Symbol : symbol-join([a x b])
defn lowered-name (e:Expression) -> Symbol :
   match(e) :
      (e:WRef) : name(e)
      (e:WSubField) : merge(lowered-name(exp(e)),name(e),`_)
      (e:WSubIndex) : merge(lowered-name(exp(e)),to-symbol(value(e)),`_)
defn root-ref (e:Expression) -> Expression :
   match(e) :
      (e:WRef) : e
      (e:WSubField|WSubIndex) : root-ref(e)

;------------- Pass ------------------

defn lower-types (s:Stmt) -> Stmt :
   defn lower-types-e (e:Expression) -> Expression :
      match(e) : 
         (e:WRef|UIntValue|SIntValue) : e
         (e:WSubField) : 
            match(kind(e)) :
               (k:InstanceKind) : 
                  val temp = lowered-name(WRef(name(e),UnknownType(),InstanceKind(),MALE))
                  WSubField(root-ref(e),temp,type(e),gender(e))
               (k:MemKind) : lower-mem(e)
               (k) : WRef(lowered-name(e),type(e),kind(e),gender(e))
         (e:WSubIndex) : WRef(lowered-name(e),type(e),kind(e),gender(e))
         (e:DoPrim) : map(lower-types-e,e)
   match(map(lower-types-e,s)) :
      (s:DefWire|DefRegister|DefPoison) :
         if is-ground?(type(s)) : s
         else :
            val es = create-exps(name(s),type(s))
            Begin $ for e in es map :
               defn replace-type (t:Type) -> Type : type(e)
               defn replace-name (n:Symbol) -> Symbol : lowered-name(e)
               map{replace-name,_} $ map(replace-type,s)
      (s:WDefInstance) :
         val fields* = for f in fields(type(s) as BundleType) map-append :
            val es = create-exps(WRef(name(f),type(f),ExpKind(),flip(f) * MALE))
            for e in es map :
               switch { _ == gender(e) } :
                  MALE : Field(lowered-name(e),DEFAULT,type(f))
                  FEMALE : Field(lowered-name(e),REVERSE,type(f))
         WDefInstance(info(s),name(s),module(s),BundleType(fields*))
      (s:DefMemory) :
         if is-ground?(data-type(s)) : s
         else :
            val es = create-exps(name(s),data-type(s))
            Begin $ for e in es map :
               DefMemory(info(s),merge(name(s),lowered-name(e),`_),type(e),depth(s),write-latency(s),read-latency(s),readers(s),writers(s),readwriters(s))
      (s) : map(lower-types,s)

defn lower-types (c:Circuit) -> Circuit :
   Circuit{info(c),_,main(c)} $
      for m in modules(c) map :
         val ports* = 
            for p in ports(m) map-append :
               val es = create-exps(WRef(name(p),type(p),PortKind(),to-gender(direction(p))))
               for e in es map :
                  Port(info(p),lowered-name(e),to-dir(gender(e)),type(e))
         match(m) :
            (m:ExModule) : ExModule(info(m),name(m),ports*)
            (m:InModule) : InModule(info(m),name(m),ports*,lower-types(body(m)))

;============ VERILOG ==============

public defstruct Verilog <: Pass :
   with-output: (() -> False) -> False  
public defmethod pass (b:Verilog) -> (Circuit -> Circuit) : emit-verilog{with-output(b),_}
public defmethod name (b:Verilog) -> String : "To Verilog"
public defmethod short-name (b:Verilog) -> String : "To Verilog"

;============ Utilz =============
defstruct VIndent
defstruct VRandom
val tab = VIndent()
val ran = VRandom()
defn escape (s:String) -> String :
   val s* = Vector<String>()
   add(s*,"\"");"
   var percent = false
   for c in s do :
      if c == '\n' :
         add(s*,"\\n")
      else :
         if c == 'x' and percent :
            add(s*,"h")
         else : add(s*,to-string(c))
      percent = c == '%'
   add(s*,"\"");"
   string-join(s*)
defn remove-root (ex:Expression) -> Expression :
   match(exp(ex as WSubField)) :
      (e:WSubField) : remove-root(e)
      (e:WRef) : WRef(name(ex as WSubField),type(ex),InstanceKind(),UNKNOWN-GENDER)
defn !empty? (s:Vector) -> True|False :
   if length(s) == 0 : false
   else : true
defn long! (t:Type) -> Long :
   match(t) :
      (t:UIntType|SIntType) : width(width(t) as IntWidth)
      (t:BundleType) : 
         var w = to-long(0)
         for f in fields(t) do :
            w = w + long!(type(f))
         w
      (t:VectorType) : to-long(size(t)) * long!(type(t))
   
defn rand-string (t:Type) -> Streamable : 
   val w* = ((long!(t) + to-long(31)) / to-long(32))
   ["{" w* "{" ran "}};"]
defn emit (x:?) : emit(x,0)
defn emit (x:?, top:Int) :
   match(x) :
      (e:Expression) :
         turn-off-debug(false)
         match(e) :
            (e:DoPrim) : op-print(e)
            (e:WRef) : print(e)
            ;(e:WSubField) : print-all([exp(e) `_ name(f)])
            (e:WSubAccess) : print(e)
            (e:WSubIndex) : print(e)
            (e:UIntValue|SIntValue) : v-print(e)
         turn-on-debug(false)
      (t:Type) :
         match(t) :
            (t:UIntType|SIntType) : 
               val w = long!(t) - to-long(1)
               if w >= to-long(0) : print-all(["[" w ":0]"])
               else : ""
      (s:Symbol) : print(s)
      (i:Int) : print(i)
      (s:String) : print(s)
      (t:VIndent) : print("   ")
      (r:VRandom) : print("$random")
      (s:Streamable) : 
         for x in s do :
            emit(x, top + 1)
         if top == 0 : print("\n")

;------------- PASS -----------------
defn v-print (e:UIntValue|SIntValue) :
   val str = to-string(value(e))
   val out = substring(str,1,length(str) - 1)
   print $ string-join $ match(e) :
      (e:UIntValue) : [long!(type(e)) "'" out]
      (e:SIntValue) : [long!(type(e)) "'s" out]
defn op-print (doprim:DoPrim) :
   defn cast-if (e:Expression) -> ? :
      val signed? = for x in args(doprim) any? : type(x) typeof SIntType
      if not signed? : e
      else : match(type(e)) :
         (t:SIntType) : ["$signed(" e ")"]
         (t:UIntType) :  ["$signed({1'b0," e "})"]
   defn cast (e:Expression) -> ? :
      match(type(doprim)) :
         (t:UIntType) : e
         (t:SIntType) : ["$signed(" e ")"]
   defn a0 () -> Expression : args(doprim)[0]
   defn a1 () -> Expression : args(doprim)[1]
   defn a2 () -> Expression : args(doprim)[2]
   defn c0 () -> Int : consts(doprim)[0]
   defn c1 () -> Int : consts(doprim)[1]

   print $ string-join $ switch {_ == op(doprim)} :
      ADD-OP : [cast-if(a0()) " + " cast-if(a1())]
      SUB-OP : [cast-if(a0()) " - " cast-if(a1())]
      MUL-OP : [cast-if(a0()) " * " cast-if(a1()) ]
      DIV-OP : [cast-if(a0()) " / " cast-if(a1()) ]
      MOD-OP : [cast-if(a0()) " % " cast-if(a1()) ]
      QUO-OP : [cast-if(a0()) " / " cast-if(a1()) ]
      REM-OP : [cast-if(a0()) " % " cast-if(a1()) ]
      ADD-WRAP-OP : [cast-if(a0()), " + " cast-if(a1())]
      SUB-WRAP-OP : [cast-if(a0()), " - " cast-if(a1())]
      LESS-OP : [cast-if(a0()) " < " cast-if(a1())]
      LESS-EQ-OP : [cast-if(a0()) " <= " cast-if(a1())]
      GREATER-OP : [cast-if(a0()) " > " cast-if(a1())]
      GREATER-EQ-OP : [cast-if(a0()) " >= " cast-if(a1())]
      NEQUIV-OP : [cast-if(a0()) " != " cast-if(a1())]
      EQUIV-OP : [cast-if(a0()) " == " cast-if(a1())]
      NEQUAL-OP : [cast-if(a0()) " != " cast-if(a1())]
      EQUAL-OP : [cast-if(a0()) " == " cast-if(a1())]
      MUX-OP : [a0() " ? " cast(a1()) " : " cast(a2())]
      PAD-OP : 
         val w = long!(type(a0()))
         val diff = (to-long(c0()) - w)
         if w == to-long(0) : [ a0() ]
         else : match(type(doprim)) :
            (t:SIntType) : ["{{" diff "{" a0() "[" w - to-long(1) "]}}, " a0() " }"]
            (t) : ["{{" diff "'d0 }, " a0() " }"]
      AS-UINT-OP : ["$unsigned(" emit(a0()) ")"]
      AS-SINT-OP : ["$signed(" emit(a0()) ")"]
      DYN-SHIFT-LEFT-OP : [cast(a0()) " << " emit(a1())]
      DYN-SHIFT-RIGHT-OP : 
         match(type(doprim)) :
            (t:SIntType) : [cast(a0()) " >>> " a1()]
            (t) : [cast(a0()) " >> " a1()]
      SHIFT-LEFT-OP : [cast(a0()) " << " c0()]
      SHIFT-RIGHT-OP : [cast(a0()) "[" long!(type(a0())) - to-long(1) ":" c0() "]"]
      NEG-OP : ["-{" cast(a0()) "}"]
      CONVERT-OP : 
         match(type(a0())) :
            (t:UIntType) : ["{1'b0," cast(a0()) "}"]
            (t:SIntType) : [cast(a0())]
      BIT-NOT-OP : ["~ " cast(a0())]
      BIT-AND-OP : [cast(a0()) " & " cast(a1())]
      BIT-OR-OP : [cast(a0()) " | " cast(a1())]
      BIT-XOR-OP : [cast(a0()) " ^ " cast(a1())]
      CONCAT-OP : ["{" cast(a0()) "," cast(a1()) "}"]
      BIT-SELECT-OP : [cast(a0()) "[" c0() "]"]
      BITS-SELECT-OP : [cast(a0()) "[" c0() ":" c1() "]"]
      BIT-AND-REDUCE-OP : 
         val v = Vector<Streamable>()
         for b in 0 to to-int(long!(type(doprim))) do :
            add(v,[cast(a0()) "[" b "]"])
         join(v," & ")
      BIT-OR-REDUCE-OP : 
         val v = Vector<Streamable>()
         for b in 0 to to-int(long!(type(doprim))) do :
            add(v,[cast(a0() ) "[" b "]"])
         join(v," | ")
      BIT-XOR-REDUCE-OP : 
         val v = Vector<Streamable>()
         for b in 0 to to-int(long!(type(doprim))) do :
            add(v,[cast(a0() ) "[" b "]"])
         join(v," ^ ")

defn emit-verilog (m:InModule) -> Module :
   val netlist = HashTable<Expression,Expression>(exp-hash)
   val simlist = Vector<Stmt>()
   val namehash = get-sym-hash(m,keys(v-keywords))
   defn build-netlist (s:Stmt) -> Stmt :
      match(s) :
         (s:Connect) : netlist[loc(s)] = exp(s)
         (s:Conditionally) : add(simlist,s)
         (s:DefNode) : 
            val e = WRef(name(s),get-type(s),NodeKind(),MALE)
            netlist[e] = value(s)
         (s) : map(build-netlist,s)
      s

   val declares = Vector<Streamable>()
   val at-clock = HashTable<Expression,Vector<Streamable>>(exp-hash)
   val initials = Vector<Streamable>()
   val simulates = Vector<Streamable>()
   defn declare (b:Symbol,n:Symbol,t:Type) : 
      add(declares,[b t n ";"])
   defn assign (e:Expression,value:Expression) : 
      add(declares,["assign " e " = " value])
   defn update-reset (e:Expression,clk:Expression,reset?:Expression,init:Expression) :
      add(at-clock[clk],["if(" reset? ") begin"])
      add(at-clock[clk],[tab e " <= " init])
      add(at-clock[clk],["end else"])
      add(at-clock[clk],[tab e " <= " netlist[e]])
      add(at-clock[clk],["end"])
   defn update (e:Expression,clk:Expression,en:Expression) :
      add(at-clock[clk],["if(" en ") begin"])
      add(at-clock[clk],[tab e " <= " netlist[e]])
      add(at-clock[clk],["end"])
   defn initialize (e:Expression) :
      add(initials,[e " = " rand-string(type(e))])
   defn initialize-mem (e:Expression,i:Int) :
      add(initials,["for (initvar = 0; initvar < " i "; initvar = initvar+1)"])
      val index = WRef(`initvar,UnknownType(),ExpKind(),UNKNOWN-GENDER)
      add(initials,[tab WSubAccess(e,index,UnknownType(),FEMALE), " = " rand-string(type(e))])
   defn instantiate (n:Symbol,m:Symbol,es:List<Expression>) :
      add(declares,[m " " n " ("])
      for (e in es,i in 1 to false) do :
         val s = [tab "." remove-root(e) "(" netlist[e] ")"]
         if i == length(es) : add(declares,[s ","])
         else : add(declares,s)
      add(declares,[");"])
   defn simulate (clk:Expression,en:Expression,s:Streamable) :
      add(at-clock[clk],["`ifndef SYNTHESIS"])
      add(at-clock[clk],[tab "if(" en ") begin"])
      add(at-clock[clk],[tab tab s])
      add(at-clock[clk],[tab "end"])
      add(at-clock[clk],["`endif"])
   defn stop (ret:Int) -> Streamable :
      ["$fdisplay(32/'h80000002," ret ");$finish;"]
   defn printf (str:String,args:List<Expression>) -> Streamable :
      val str* = join(List(escape(str),args),",")
      ["$fdisplay(32/'h80000002," str* ");"]
   defn delay (e:Expression, n:Int) -> Expression :
      var e* = e
      for i in 0 to n do :
         val name = firrtl-gensym(lowered-name(e),namehash)
         declare(`reg,name,type(e))
         val e** = WRef(name,type(e),ExpKind(),UNKNOWN-GENDER)
         assign(e**,e*)
         e* = e**
      e*

   defn build-streams (s:Stmt) -> Stmt :
      match(s) :
         (s:DefWire) : 
            val es = create-exps(WRef(name(s),type(s),WireKind(),BI-GENDER))
            for e in es do : 
               declare(`wire,lowered-name(e),type(e))
               assign(e,netlist[e])
         (s:DefRegister) :
            val es = create-exps(WRef(name(s),type(s),RegKind(),BI-GENDER))
            for e in es do : 
               declare(`reg,lowered-name(e),type(e))
               update-reset(e,clock(s),reset(s),init(s))
               initialize(e)
         (s:DefPoison) :
            val es = create-exps(WRef(name(s),type(s),PoisonKind(),MALE))
            for e in es do :
               declare(`wire,lowered-name(e),type(e))
               initialize(e)
         (s:DefNode) :
            declare(`wire,name(s),type(value(s)))
            assign(WRef(name(s),type(value(s)),NodeKind(),MALE),value(s))
         (s:Conditionally) :
            match(conseq(s)) :
               (c:Stop) : simulate(clk(c),pred(s),stop(ret(c)))
               (c:Print) : simulate(clk(c),pred(s),printf(string(c),args(c)))
         (s:Stop) : simulate(clk(s),one,stop(ret(s)))
         (s:Print) : simulate(clk(s),one,printf(string(s),args(s)))
         (s:WDefInstance) :
            val es = create-exps(WRef(name(s),type(s),InstanceKind(),BI-GENDER))
            instantiate(name(s),module(s),es)
         (s:DefMemory) : ;TODO expand bundle in declaration, lots of thinking todo
            declare(`reg,name(s),VectorType(data-type(s),depth(s)))
            val mem = WRef(name(s),get-type(s),MemKind(append-all([readers(s) writers(s) readwriters(s)])),BI-GENDER)
            initialize-mem(mem,depth(s))
            
            for r in readers(s) do :
               val port = HashTable<Symbol,Expression>(symbol-hash)
               for f in fields(get-type(s) as BundleType) do :
                  port[name(f)] = WSubField(mem,name(f),type(f),UNKNOWN-GENDER)
               val addr* = delay(port[`addr],read-latency(s))
               val en* = delay(port[`en],read-latency(s))
               val e = port[`rdata]
               netlist[e] = WSubAccess(mem,addr*,type(port[`rdata]),FEMALE)
               update(e,port[`clk],en*)

            for w in writers(s) do :
               val port = HashTable<Symbol,Expression>(symbol-hash)
               for f in fields(get-type(s) as BundleType) do : 
                  port[name(f)] = WSubField(mem,name(f),type(f),UNKNOWN-GENDER)
               val addr* = delay(port[`addr],write-latency(s) - 1)
               val en* = delay(port[`en],write-latency(s) - 1)
               val wmask* = delay(port[`wmask],write-latency(s) - 1)
               val e = WSubAccess(port[`wdata],addr*,type(port[`wdata]),FEMALE)
               update(e,port[`clk],AND(en*,wmask*))

            for rw in readwriters(s) do :
               val port = HashTable<Symbol,Expression>(symbol-hash)
               for f in fields(get-type(s) as BundleType) do :
                  port[name(f)] = WSubField(mem,name(f),type(f),UNKNOWN-GENDER)
               val raddr* = delay(port[`raddr],read-latency(s))
               val ren* = delay(port[`ren],read-latency(s))
               val re = port[`rdata]
               netlist[re] = WSubAccess(mem,raddr*,type(port[`rdata]),FEMALE)
               update(re,port[`clk],ren*)

               val waddr* = delay(port[`waddr],write-latency(s) - 1)
               val wen* = delay(port[`wen],write-latency(s) - 1)
               val wmask* = delay(port[`wmask],write-latency(s) - 1)
               val we = WSubAccess(port[`wdata],waddr*,type(port[`wdata]),FEMALE)
               update(we,port[`clk],AND(wen*,wmask*))
         (s:Begin) : map(build-streams,s)
      s

   defn emit-streams () :
      if !empty?(declares) :
         for x in declares do :
            emit(x)

      if !empty?(initials) :
         emit(["`ifndef SYNTHESIS"])
         emit(["  integer initvar;"])
         emit(["  initial begin"])
         emit(["    #0.002;"])
         for x in initials do :
            emit([tab x])
         emit(["  end"])
         emit(["`endif"])

      for clk-stream in at-clock do :
         if !empty?(value(clk-stream)) :
            emit(["always @(posedge " key(clk-stream) " ) begin"])
            for x in value(clk-stream) do :
               emit([tab x])
            emit(["end"])

   build-netlist(body(m))
   build-streams(body(m))
   emit-streams()
   m

defn emit-verilog (with-output:(() -> False) -> False, c:Circuit) :
   with-output $ fn () :
      for m in modules(c) do :
         match(m) :
            (m:InModule) : emit-verilog(m)
            (m:ExModule) : false
   c