path: root/src/main/scala/firrtl/Utils.scala

/*
Copyright (c) 2014 - 2016 The Regents of the University of
California (Regents). All Rights Reserved.  Redistribution and use in
source and binary forms, with or without modification, are permitted
provided that the following conditions are met:
   * Redistributions of source code must retain the above
     copyright notice, this list of conditions and the following
     two paragraphs of disclaimer.
   * Redistributions in binary form must reproduce the above
     copyright notice, this list of conditions and the following
     two paragraphs of disclaimer in the documentation and/or other materials
     provided with the distribution.
   * Neither the name of the Regents nor the names of its contributors
     may be used to endorse or promote products derived from this
     software without specific prior written permission.
IN NO EVENT SHALL REGENTS BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT,
SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS,
ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
REGENTS HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
REGENTS SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE. THE SOFTWARE AND ACCOMPANYING DOCUMENTATION, IF
ANY, PROVIDED HEREUNDER IS PROVIDED "AS IS". REGENTS HAS NO OBLIGATION
TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
MODIFICATIONS.
*/
// Utility functions for FIRRTL IR

/* TODO
 *  - Adopt style more similar to Chisel3 Emitter?
 */

/* TODO Richard
 *  - add new IR nodes to all Util functions
 */

package firrtl

import scala.collection.mutable.StringBuilder
import java.io.PrintWriter
import com.typesafe.scalalogging.LazyLogging
import WrappedExpression._
import firrtl.WrappedType._
import firrtl.Mappers._
import firrtl.PrimOps._
import firrtl.ir._
import scala.collection.mutable.ArrayBuffer
import scala.collection.mutable.LinkedHashMap
//import scala.reflect.runtime.universe._

class FIRRTLException(str: String) extends Exception(str)

object Utils extends LazyLogging {
  private[firrtl] def time[R](name: String)(block: => R): R = {
    logger.info(s"Starting $name")
    val t0 = System.nanoTime()
    val result = block
    val t1 = System.nanoTime()
    logger.info(s"Finished $name")
    val timeMillis = (t1 - t0) / 1000000.0
    logger.info(f"$name took $timeMillis%.1f ms\n")
    result
  }

  /** Removes all [[firrtl.ir.Empty]] statements and condenses
   * [[firrtl.ir.Block]] statements.
    */
  def squashEmpty(s: Statement): Statement = s map squashEmpty match {
    case Block(stmts) =>
      val newStmts = stmts filter (_ != EmptyStmt)
      newStmts.size match {
        case 0 => EmptyStmt
        case 1 => newStmts.head
        case _ => Block(newStmts)
      }
    case s => s
  }

  /** Indent the results of [[ir.FirrtlNode.serialize]] */
  def indent(str: String) = str replaceAllLiterally ("\n", "\n  ")
  def serialize(bi: BigInt): String =
    if (bi < BigInt(0)) "\"h" + bi.toString(16).substring(1) + "\""
    else "\"h" + bi.toString(16) + "\""

   implicit class WithAs[T](x: T) {
     import scala.reflect._
     def as[O: ClassTag]: Option[O] = x match {
       case o: O => Some(o)
       case _ => None }
     def typeof[O: ClassTag]: Boolean = x match {
       case o: O => true
       case _ => false }
   }
   implicit def toWrappedExpression (x:Expression) = new WrappedExpression(x)
   def ceil_log2(x: BigInt): BigInt = (x-1).bitLength
   def ceil_log2(x: Int): Int = scala.math.ceil(scala.math.log(x) / scala.math.log(2)).toInt
   def max(a: BigInt, b: BigInt): BigInt = if (a >= b) a else b
   def min(a: BigInt, b: BigInt): BigInt = if (a >= b) b else a
   def pow_minus_one(a: BigInt, b: BigInt): BigInt = a.pow(b.toInt) - 1
   val gen_names = Map[String,Int]()
   val delin = "_"
   val BoolType = UIntType(IntWidth(1))
   val one  = UIntLiteral(BigInt(1),IntWidth(1))
   val zero = UIntLiteral(BigInt(0),IntWidth(1))
   def uint (i:Int) : UIntLiteral = {
      val num_bits = req_num_bits(i)
      val w = IntWidth(scala.math.max(1,num_bits - 1))
      UIntLiteral(BigInt(i),w)
   }
   def req_num_bits (i: Int) : Int = {
      val ix = if (i < 0) ((-1 * i) - 1) else i
      ceil_log2(ix + 1) + 1
   }
   def AND (e1:WrappedExpression,e2:WrappedExpression) : Expression = {
      if (e1 == e2) e1.e1
      else if ((e1 == we(zero)) | (e2 == we(zero))) zero
      else if (e1 == we(one)) e2.e1
      else if (e2 == we(one)) e1.e1
      else DoPrim(And,Seq(e1.e1,e2.e1),Seq(),UIntType(IntWidth(1)))
   }
   
   def OR (e1:WrappedExpression,e2:WrappedExpression) : Expression = {
      if (e1 == e2) e1.e1
      else if ((e1 == we(one)) | (e2 == we(one))) one
      else if (e1 == we(zero)) e2.e1
      else if (e2 == we(zero)) e1.e1
      else DoPrim(Or,Seq(e1.e1,e2.e1),Seq(),UIntType(IntWidth(1)))
   }
   def EQV (e1:Expression,e2:Expression) : Expression = { DoPrim(Eq,Seq(e1,e2),Seq(),e1.tpe) }
   def NOT (e1:WrappedExpression) : Expression = {
      if (e1 == we(one)) zero
      else if (e1 == we(zero)) one
      else DoPrim(Eq,Seq(e1.e1,zero),Seq(),UIntType(IntWidth(1)))
   }

   
   //def MUX (p:Expression,e1:Expression,e2:Expression) : Expression = {
   //   Mux(p,e1,e2,mux_type(e1.tpe,e2.tpe))
   //}

   def create_mask (dt:Type) : Type = {
      dt match {
         case t:VectorType => VectorType(create_mask(t.tpe),t.size)
         case t:BundleType => {
            val fieldss = t.fields.map { f => Field(f.name,f.flip,create_mask(f.tpe)) }
            BundleType(fieldss)
         }
         case t:UIntType => BoolType
         case t:SIntType => BoolType
      }
   }
   def create_exps (n:String, t:Type) : Seq[Expression] =
      create_exps(WRef(n,t,ExpKind(),UNKNOWNGENDER))
   def create_exps (e:Expression) : Seq[Expression] = e match {
      case (e:Mux) =>
         val e1s = create_exps(e.tval)
         val e2s = create_exps(e.fval)
         (e1s,e2s).zipped map ((e1,e2) => Mux(e.cond,e1,e2,mux_type_and_widths(e1,e2)))
      case (e:ValidIf) => create_exps(e.value) map (e1 => ValidIf(e.cond,e1,e1.tpe))
      case (e) => e.tpe match {
         case (_:GroundType) => Seq(e)
         case (t:BundleType) => (t.fields foldLeft Seq[Expression]())((exps, f) =>
            exps ++ create_exps(WSubField(e,f.name,f.tpe,times(gender(e), f.flip))))
         case (t:VectorType) => ((0 until t.size) foldLeft Seq[Expression]())((exps, i) =>
            exps ++ create_exps(WSubIndex(e,i,t.tpe,gender(e))))
      }
   }

   def get_flip (t:Type, i:Int, f:Orientation) : Orientation = {
     if (i >= get_size(t)) error("Shouldn't be here")
     t match {
       case (_: GroundType) => f
       case (t: BundleType) => 
         val (_, flip) = ((t.fields foldLeft (i, None: Option[Orientation])){
            case ((n, ret), x) if n < get_size(x.tpe) => ret match {
              case None => (n, Some(get_flip(x.tpe,n,times(x.flip,f))))
              case Some(_) => (n, ret)
            }
            case ((n, ret), x) => (n - get_size(x.tpe), ret)
         })
         flip.get
       case (t: VectorType) => 
         val (_, flip) = (((0 until t.size) foldLeft (i, None: Option[Orientation])){
           case ((n, ret), x) if n < get_size(t.tpe) => ret match {
             case None => (n, Some(get_flip(t.tpe,n,f)))
             case Some(_) => (n, ret)
           }
           case ((n, ret), x) => (n - get_size(t.tpe), ret)
         })
         flip.get
     }
   }
  
   def get_point (e:Expression) : Int = e match {
     case (e: WRef) => 0
     case (e: WSubField) => e.exp.tpe match {case b: BundleType =>
       (b.fields takeWhile (_.name != e.name) foldLeft 0)(
         (point, f) => point + get_size(f.tpe))
     }
     case (e: WSubIndex) => e.value * get_size(e.tpe)
     case (e: WSubAccess) => get_point(e.exp)
   }

   /** Returns true if t, or any subtype, contains a flipped field
     * @param t [[firrtl.ir.Type]]
     * @return if t contains [[firrtl.ir.Flip]]
     */
   def hasFlip(t: Type): Boolean = t match {
     case t: BundleType =>
       (t.fields exists (_.flip == Flip)) ||
       (t.fields exists (f => hasFlip(f.tpe)))
     case t: VectorType => hasFlip(t.tpe)
     case _ => false
   }

//============== TYPES ================
   def mux_type (e1:Expression,e2:Expression) : Type = mux_type(e1.tpe,e2.tpe)
   def mux_type (t1:Type,t2:Type) : Type = {
      if (wt(t1) == wt(t2)) {
         (t1,t2) match { 
            case (t1:UIntType,t2:UIntType) => UIntType(UnknownWidth)
            case (t1:SIntType,t2:SIntType) => SIntType(UnknownWidth)
            case (t1:VectorType,t2:VectorType) => VectorType(mux_type(t1.tpe,t2.tpe),t1.size)
            case (t1:BundleType,t2:BundleType) => 
               BundleType((t1.fields,t2.fields).zipped.map((f1,f2) => {
                  Field(f1.name,f1.flip,mux_type(f1.tpe,f2.tpe))
               }))
         }
      } else UnknownType
   }
   def mux_type_and_widths (e1:Expression,e2:Expression) : Type = mux_type_and_widths(e1.tpe,e2.tpe)
   def mux_type_and_widths (t1:Type,t2:Type) : Type = {
      def wmax (w1:Width,w2:Width) : Width = {
         (w1,w2) match {
            case (w1:IntWidth,w2:IntWidth) => IntWidth(w1.width.max(w2.width))
            case (w1,w2) => MaxWidth(Seq(w1,w2))
         }
      }
      val wt1 = new WrappedType(t1)
      val wt2 = new WrappedType(t2)
      if (wt1 == wt2) {
         (t1,t2) match {
            case (t1:UIntType,t2:UIntType) => UIntType(wmax(t1.width,t2.width))
            case (t1:SIntType,t2:SIntType) => SIntType(wmax(t1.width,t2.width))
            case (t1:VectorType,t2:VectorType) => VectorType(mux_type_and_widths(t1.tpe,t2.tpe),t1.size)
            case (t1:BundleType,t2:BundleType) => BundleType((t1.fields zip t2.fields).map{case (f1, f2) => Field(f1.name,f1.flip,mux_type_and_widths(f1.tpe,f2.tpe))})
         }
      } else UnknownType
   }
   def module_type (m:DefModule) : Type = {
      BundleType(m.ports.map(p => p.toField))
   }
   def sub_type (v:Type) : Type = {
      v match {
         case v:VectorType => v.tpe
         case v => UnknownType
      }
   }
   def field_type (v:Type,s:String) : Type = {
      v match {
         case v:BundleType => {
            val ft = v.fields.find(p => p.name == s)
            ft match {
               case ft:Some[Field] => ft.get.tpe
               case ft => UnknownType
            }
         }
         case v => UnknownType
      }
   }
   
////=====================================
   def widthBANG (t:Type) : Width = {
      t match {
         case g: GroundType => g.width
         case t => error("No width!")
      }
   }
   def long_BANG (t:Type) : Long = {
      (t) match {
         case g: GroundType => 
           g.width match {
             case IntWidth(x) => x.toLong
             case _ => throw new FIRRTLException(s"Expecting IntWidth, got: ${g.width}")
           }
         case (t:BundleType) => {
            var w = 0
            for (f <- t.fields) { w = w + long_BANG(f.tpe).toInt }
            w
         }
         case (t:VectorType) => t.size * long_BANG(t.tpe)
      }
   }
// =================================
   def error(str:String) = throw new FIRRTLException(str)

   implicit class FirrtlNodeUtils(node: FirrtlNode) {
     def getType(): Type = 
       node match {
         case e: Expression => e.getType
         case s: Statement => s.getType
         //case f: Field => f.getType
         case t: Type => t.getType
         case p: Port => p.getType
         case _ => UnknownType
       }
   }

//// =============== EXPANSION FUNCTIONS ================
   def get_size(t: Type) : Int = t match {
     case (t: BundleType) => (t.fields foldLeft 0)(
       (sum, f) => sum + get_size(f.tpe))
     case (t: VectorType) => t.size * get_size(t.tpe)
     case (t) => 1
   }

   def get_valid_points (t1: Type, t2: Type, flip1: Orientation, flip2: Orientation) : Seq[(Int,Int)] = {
     //;println_all(["Inside with t1:" t1 ",t2:" t2 ",f1:" flip1 ",f2:" flip2])
     (t1, t2) match {
       case (t1: UIntType, t2: UIntType) => if (flip1 == flip2) Seq((0, 0)) else Nil
       case (t1: SIntType, t2: SIntType) => if (flip1 == flip2) Seq((0, 0)) else Nil
       case (t1: BundleType, t2: BundleType) =>
         def emptyMap = Map[String, (Type, Orientation, Int)]()
         val t1_fields = ((t1.fields foldLeft (emptyMap, 0)){case ((map, ilen), f1) =>
           (map + (f1.name -> (f1.tpe, f1.flip, ilen)), ilen + get_size(f1.tpe))})._1
         ((t2.fields foldLeft (Seq[(Int, Int)](), 0)){case ((points, jlen), f2) =>
           t1_fields get f2.name match {
             case None => (points, jlen + get_size(f2.tpe))
             case Some((f1_tpe, f1_flip, ilen))=>
               val f1_times = times(flip1, f1_flip)
               val f2_times = times(flip2, f2.flip)
               val ls = get_valid_points(f1_tpe, f2.tpe, f1_times, f2_times)
               (points ++ (ls map {case (x, y) => (x + ilen, y + jlen)}), jlen + get_size(f2.tpe))
           }
         })._1
       case (t1: VectorType, t2: VectorType) =>
         val size = math.min(t1.size, t2.size)
         (((0 until size) foldLeft (Seq[(Int, Int)](), 0, 0)){case ((points, ilen, jlen), _) =>
           val ls = get_valid_points(t1.tpe, t2.tpe, flip1, flip2)
           (points ++ (ls map {case (x, y) => ((x + ilen), (y + jlen))}),
             ilen + get_size(t1.tpe), jlen + get_size(t2.tpe))
         })._1
       case (ClockType, ClockType) => if (flip1 == flip2) Seq((0, 0)) else Nil
       case _ => error("shouldn't be here")
     }
   }

// =========== GENDER/FLIP UTILS ============
   def swap (g:Gender) : Gender = {
      g match {
         case UNKNOWNGENDER => UNKNOWNGENDER
         case MALE => FEMALE
         case FEMALE => MALE
         case BIGENDER => BIGENDER
      }
   }
   def swap (d:Direction) : Direction = {
      d match {
         case Output => Input
         case Input => Output
      }
   }
   def swap (f:Orientation) : Orientation = {
      f match {
         case Default => Flip
         case Flip => Default
      }
   }
   def to_dir (g:Gender) : Direction = {
      g match {
         case MALE => Input
         case FEMALE => Output
      }
   }
   def to_gender (d:Direction) : Gender = {
      d match {
         case Input => MALE
         case Output => FEMALE
      }
   }
  def toGender(f: Orientation): Gender = f match {
    case Default => FEMALE
    case Flip => MALE
  }
  def toFlip(g: Gender): Orientation = g match {
    case MALE => Flip
    case FEMALE => Default
  }

   def field_flip (v:Type,s:String) : Orientation = {
      v match {
         case v:BundleType => {
            val ft = v.fields.find {p => p.name == s}
            ft match {
               case ft:Some[Field] => ft.get.flip
               case ft => Default
            }
         }
         case v => Default
      }
   }
   def get_field (v:Type,s:String) : Field = {
      v match {
         case v:BundleType => {
            val ft = v.fields.find {p => p.name == s}
            ft match {
               case ft:Some[Field] => ft.get
               case ft => error("Shouldn't be here"); Field("blah",Default,UnknownType)
            }
         }
         case v => error("Shouldn't be here"); Field("blah",Default,UnknownType)
      }
   }
   def times (flip:Orientation, d:Direction) : Direction = times(flip, d)
   def times (d:Direction,flip:Orientation) : Direction = {
      flip match {
         case Default => d
         case Flip => swap(d)
      }
   }
   def times (g: Gender, d: Direction): Direction = times(d, g)
   def times (d: Direction, g: Gender): Direction = g match {
     case FEMALE => d
     case MALE => swap(d) // MALE == INPUT == REVERSE
   }

   def times (g:Gender,flip:Orientation) : Gender = times(flip, g)
   def times (flip:Orientation, g:Gender) : Gender = {
      flip match {
         case Default => g
         case Flip => swap(g)
      }
   }
   def times (f1:Orientation, f2:Orientation) : Orientation = {
      f2 match {
         case Default => f1
         case Flip => swap(f1)
      }
   }


// =========== ACCESSORS =========
   def info (s:Statement) : Info = {
      s match {
         case s:DefWire => s.info
         case s:DefRegister => s.info
         case s:DefInstance => s.info
         case s:WDefInstance => s.info
         case s:DefMemory => s.info
         case s:DefNode => s.info
         case s:Conditionally => s.info
         case s:PartialConnect => s.info
         case s:Connect => s.info
         case s:IsInvalid => s.info
         case s:Stop => s.info
         case s:Print => s.info
         case s:Block => NoInfo
         case EmptyStmt => NoInfo
      }
   }
   def gender (e:Expression) : Gender = {
     e match {
        case e:WRef => e.gender
        case e:WSubField => e.gender
        case e:WSubIndex => e.gender
        case e:WSubAccess => e.gender
        case e:DoPrim => MALE
        case e:UIntLiteral => MALE
        case e:SIntLiteral => MALE
        case e:Mux => MALE
        case e:ValidIf => MALE
        case e:WInvalid => MALE
        case e => println(e); error("Shouldn't be here")
    }}
   def get_gender (s:Statement) : Gender =
     s match {
       case s:DefWire => BIGENDER
       case s:DefRegister => BIGENDER
       case s:WDefInstance => MALE
       case s:DefNode => MALE
       case s:DefInstance => MALE
       case s:DefMemory => MALE
       case s:Block => UNKNOWNGENDER
       case s:Connect => UNKNOWNGENDER
       case s:PartialConnect => UNKNOWNGENDER
       case s:Stop => UNKNOWNGENDER
       case s:Print => UNKNOWNGENDER
       case EmptyStmt => UNKNOWNGENDER
       case s:IsInvalid => UNKNOWNGENDER
     }
   def get_gender (p:Port) : Gender =
     if (p.direction == Input) MALE else FEMALE
   def kind (e:Expression) : Kind =
      e match {
         case e:WRef => e.kind
         case e:WSubField => kind(e.exp)
         case e:WSubIndex => kind(e.exp)
         case e => ExpKind()
      }
   def get_type (s:Statement) : Type = {
      s match {
       case s:DefWire => s.tpe
       case s:DefRegister => s.tpe
       case s:DefNode => s.value.tpe
       case s:DefMemory => {
          val depth = s.depth
          val addr = Field("addr",Default,UIntType(IntWidth(scala.math.max(ceil_log2(depth), 1))))
          val en = Field("en",Default,BoolType)
          val clk = Field("clk",Default,ClockType)
          val def_data = Field("data",Default,s.dataType)
          val rev_data = Field("data",Flip,s.dataType)
          val mask = Field("mask",Default,create_mask(s.dataType))
          val wmode = Field("wmode",Default,UIntType(IntWidth(1)))
          val rdata = Field("rdata",Flip,s.dataType)
          val wdata = Field("wdata",Default,s.dataType)
          val wmask = Field("wmask",Default,create_mask(s.dataType))
          val read_type = BundleType(Seq(rev_data,addr,en,clk))
          val write_type = BundleType(Seq(def_data,mask,addr,en,clk))
          val readwrite_type = BundleType(Seq(wmode,rdata,wdata,wmask,addr,en,clk))

          val mem_fields = ArrayBuffer[Field]()
          s.readers.foreach {x => mem_fields += Field(x,Flip,read_type)}
          s.writers.foreach {x => mem_fields += Field(x,Flip,write_type)}
          s.readwriters.foreach {x => mem_fields += Field(x,Flip,readwrite_type)}
          BundleType(mem_fields)
       }
       case s:DefInstance => UnknownType
       case s:WDefInstance => s.tpe
       case _ => UnknownType
    }}
   def get_name (s:Statement) : String = {
      s match {
       case s:DefWire => s.name
       case s:DefRegister => s.name
       case s:DefNode => s.name
       case s:DefMemory => s.name
       case s:DefInstance => s.name
       case s:WDefInstance => s.name
       case _ => error("Shouldn't be here"); "blah"
    }}
   def get_info (s:Statement) : Info = {
      s match {
       case s:DefWire => s.info
       case s:DefRegister => s.info
       case s:DefInstance => s.info
       case s:WDefInstance => s.info
       case s:DefMemory => s.info
       case s:DefNode => s.info
       case s:Conditionally => s.info
       case s:PartialConnect => s.info
       case s:Connect => s.info
       case s:IsInvalid => s.info
       case s:Stop => s.info
       case s:Print => s.info
       case _ => NoInfo
    }}

  /** Splits an Expression into root Ref and tail
    *
    * @example
    *   Given:   SubField(SubIndex(SubField(Ref("a", UIntType(IntWidth(32))), "b"), 2), "c")
    *   Returns: (Ref("a"), SubField(SubIndex(Ref("b"), 2), "c"))
    *   a.b[2].c -> (a, b[2].c)
    * @example
    *   Given:   SubField(SubIndex(Ref("b"), 2), "c")
    *   Returns: (Ref("b"), SubField(SubIndex(EmptyExpression, 2), "c"))
    *   b[2].c -> (b, EMPTY[2].c)
    * @note This function only supports WRef, WSubField, and WSubIndex
    */
  def splitRef(e: Expression): (WRef, Expression) = e match {
    case e: WRef => (e, EmptyExpression)
    case e: WSubIndex =>
      val (root, tail) = splitRef(e.exp)
      (root, WSubIndex(tail, e.value, e.tpe, e.gender))
    case e: WSubField =>
      val (root, tail) = splitRef(e.exp)
      tail match {
        case EmptyExpression => (root, WRef(e.name, e.tpe, root.kind, e.gender))
        case exp => (root, WSubField(tail, e.name, e.tpe, e.gender))
      }
  }

  /** Adds a root reference to some SubField/SubIndex chain */
  def mergeRef(root: WRef, body: Expression): Expression = body match {
    case e: WRef =>
      WSubField(root, e.name, e.tpe, e.gender)
    case e: WSubIndex =>
      WSubIndex(mergeRef(root, e.exp), e.value, e.tpe, e.gender)
    case e: WSubField =>
      WSubField(mergeRef(root, e.exp), e.name, e.tpe, e.gender)
    case EmptyExpression => root
  }

  case class DeclarationNotFoundException(msg: String) extends FIRRTLException(msg)

  /** Gets the root declaration of an expression
    *
    * @param m    the [[firrtl.ir.Module]] to search
    * @param expr the [[firrtl.ir.Expression]] that refers to some declaration
    * @return the [[firrtl.ir.IsDeclaration]] of `expr`
    * @throws DeclarationNotFoundException if no declaration of `expr` is found
    */
  def getDeclaration(m: Module, expr: Expression): IsDeclaration = {
    def getRootDecl(name: String)(s: Statement): Option[IsDeclaration] = s match {
      case decl: IsDeclaration => if (decl.name == name) Some(decl) else None
      case c: Conditionally =>
        val m = (getRootDecl(name)(c.conseq), getRootDecl(name)(c.alt))
        (m: @unchecked) match {
          case (Some(decl), None) => Some(decl)
          case (None, Some(decl)) => Some(decl)
          case (None, None) => None
        }
      case begin: Block =>
        val stmts = begin.stmts flatMap getRootDecl(name) // can we short circuit?
        if (stmts.nonEmpty) Some(stmts.head) else None
      case _ => None
    }
    expr match {
      case (_: WRef | _: WSubIndex | _: WSubField) =>
        val (root, tail) = splitRef(expr)
        val rootDecl = m.ports find (_.name == root.name) match {
          case Some(decl) => decl
          case None =>
            getRootDecl(root.name)(m.body) match {
              case Some(decl) => decl
              case None => throw new DeclarationNotFoundException(s"[module ${m.name}]  Reference ${expr.serialize} not declared!")
            }
        }
        rootDecl
      case e => throw new FIRRTLException(s"getDeclaration does not support Expressions of type ${e.getClass}")
    }
  }

// =============== RECURISVE MAPPERS ===================
   def mapr (f: Width => Width, t:Type) : Type = {
      def apply_t (t:Type) : Type = t map (apply_t) map (f)
      apply_t(t)
   }
   def mapr (f: Width => Width, s:Statement) : Statement = {
      def apply_t (t:Type) : Type = mapr(f,t)
      def apply_e (e:Expression) : Expression = e map (apply_e) map (apply_t) map (f)
      def apply_s (s:Statement) : Statement = s map (apply_s) map (apply_e) map (apply_t)
      apply_s(s)
   }
   val ONE = IntWidth(1)
   //def digits (s:String) : Boolean {
   //   val digits = "0123456789"
   //   var yes:Boolean = true
   //   for (c <- s) {
   //      if !digits.contains(c) : yes = false
   //   }
   //   yes
   //}
   //def generated (s:String) : Option[Int] = {
   //   (1 until s.length() - 1).find{
   //      i => {
   //         val sub = s.substring(i + 1)
   //         s.substring(i,i).equals("_") & digits(sub) & !s.substring(i - 1,i-1).equals("_")
   //      }
   //   }
   //}
   //def get-sym-hash (m:InModule) : LinkedHashMap[String,Int] = { get-sym-hash(m,Seq()) }
   //def get-sym-hash (m:InModule,keywords:Seq[String]) : LinkedHashMap[String,Int] = {
   //   val sym-hash = LinkedHashMap[String,Int]()
   //   for (k <- keywords) { sym-hash += (k -> 0) }
   //   def add-name (s:String) : String = {
   //      val sx = to-string(s)
   //      val ix = generated(sx)
   //      ix match {
   //         case (i:False) => {
   //            if (sym_hash.contains(s)) {
   //               val num = sym-hash(s)
   //               sym-hash += (s -> max(num,0))
   //            } else {
   //               sym-hash += (s -> 0)
   //            }
   //         }
   //         case (i:Int) => {
   //            val name = sx.substring(0,i)
   //            val digit = to-int(substring(sx,i + 1))
   //            if key?(sym-hash,name) :
   //               val num = sym-hash[name]
   //               sym-hash[name] = max(num,digit)
   //            else :
   //               sym-hash[name] = digit
   //         }
   //      s
   //         
   //   defn to-port (p:Port) : add-name(name(p))
   //   defn to-stmt (s:Stmt) -> Stmt :
   //     map{to-stmt,_} $ map(add-name,s)
   //
   //   to-stmt(body(m))
   //   map(to-port,ports(m))
   //   sym-hash
   implicit class StmtUtils(stmt: Statement) {

     def getType(): Type =
       stmt match {
         case s: DefWire    => s.tpe
         case s: DefRegister => s.tpe
         case s: DefMemory  => s.dataType
         case _ => UnknownType
       }

     def getInfo: Info =
       stmt match {
         case s: DefWire => s.info
         case s: DefRegister => s.info
         case s: DefInstance => s.info
         case s: DefMemory => s.info
         case s: DefNode => s.info
         case s: Conditionally => s.info
         case s: PartialConnect => s.info
         case s: Connect => s.info
         case s: IsInvalid => s.info
         case s: Stop => s.info
         case s: Print => s.info
         case _ => NoInfo
       }
   }

   implicit class FlipUtils(f: Orientation) {
     def flip(): Orientation = {
       f match {
         case Flip => Default
         case Default => Flip
       }
     }
         
     def toDirection(): Direction = {
       f match {
         case Default => Output
         case Flip => Input
       }
     }
   }

   implicit class FieldUtils(field: Field) {
     def flip(): Field = Field(field.name, field.flip.flip, field.tpe)

     def getType(): Type = field.tpe
     def toPort(info: Info = NoInfo): Port =
       Port(info, field.name, field.flip.toDirection, field.tpe)
   }

   implicit class TypeUtils(t: Type) {
     def isGround: Boolean = t match {
       case (_: UIntType | _: SIntType | ClockType) => true
       case (_: BundleType | _: VectorType) => false
     }
     def isAggregate: Boolean = !t.isGround

     def getType(): Type = 
       t match {
         case v: VectorType => v.tpe
         case tpe: Type => UnknownType
       }

     def wipeWidth(): Type = 
       t match {
         case t: UIntType => UIntType(UnknownWidth)
         case t: SIntType => SIntType(UnknownWidth)
         case _ => t
       }
   }

   implicit class DirectionUtils(d: Direction) {
     def toFlip(): Orientation = {
       d match {
         case Input => Flip
         case Output => Default
       }
     }
   }
  
  implicit class PortUtils(p: Port) {
    def getType(): Type = p.tpe
    def toField(): Field = Field(p.name, p.direction.toFlip, p.tpe)
  }


   val v_keywords = Map[String,Boolean]() +
      ("alias" -> true) +
      ("always" -> true) +
      ("always_comb" -> true) +
      ("always_ff" -> true) +
      ("always_latch" -> true) +
      ("and" -> true) +
      ("assert" -> true) +
      ("assign" -> true) +
      ("assume" -> true) +
      ("attribute" -> true) +
      ("automatic" -> true) +
      ("before" -> true) +
      ("begin" -> true) +
      ("bind" -> true) +
      ("bins" -> true) +
      ("binsof" -> true) +
      ("bit" -> true) +
      ("break" -> true) +
      ("buf" -> true) +
      ("bufif0" -> true) +
      ("bufif1" -> true) +
      ("byte" -> true) +
      ("case" -> true) +
      ("casex" -> true) +
      ("casez" -> true) +
      ("cell" -> true) +
      ("chandle" -> true) +
      ("class" -> true) +
      ("clocking" -> true) +
      ("cmos" -> true) +
      ("config" -> true) +
      ("const" -> true) +
      ("constraint" -> true) +
      ("context" -> true) +
      ("continue" -> true) +
      ("cover" -> true) +
      ("covergroup" -> true) +
      ("coverpoint" -> true) +
      ("cross" -> true) +
      ("deassign" -> true) +
      ("default" -> true) +
      ("defparam" -> true) +
      ("design" -> true) +
      ("disable" -> true) +
      ("dist" -> true) +
      ("do" -> true) +
      ("edge" -> true) +
      ("else" -> true) +
      ("end" -> true) +
      ("endattribute" -> true) +
      ("endcase" -> true) +
      ("endclass" -> true) +
      ("endclocking" -> true) +
      ("endconfig" -> true) +
      ("endfunction" -> true) +
      ("endgenerate" -> true) +
      ("endgroup" -> true) +
      ("endinterface" -> true) +
      ("endmodule" -> true) +
      ("endpackage" -> true) +
      ("endprimitive" -> true) +
      ("endprogram" -> true) +
      ("endproperty" -> true) +
      ("endspecify" -> true) +
      ("endsequence" -> true) +
      ("endtable" -> true) +
      ("endtask" -> true) +
      ("enum" -> true) +
      ("event" -> true) +
      ("expect" -> true) +
      ("export" -> true) +
      ("extends" -> true) +
      ("extern" -> true) +
      ("final" -> true) +
      ("first_match" -> true) +
      ("for" -> true) +
      ("force" -> true) +
      ("foreach" -> true) +
      ("forever" -> true) +
      ("fork" -> true) +
      ("forkjoin" -> true) +
      ("function" -> true) +
      ("generate" -> true) +
      ("genvar" -> true) +
      ("highz0" -> true) +
      ("highz1" -> true) +
      ("if" -> true) +
      ("iff" -> true) +
      ("ifnone" -> true) +
      ("ignore_bins" -> true) +
      ("illegal_bins" -> true) +
      ("import" -> true) +
      ("incdir" -> true) +
      ("include" -> true) +
      ("initial" -> true) +
      ("initvar" -> true) +
      ("inout" -> true) +
      ("input" -> true) +
      ("inside" -> true) +
      ("instance" -> true) +
      ("int" -> true) +
      ("integer" -> true) +
      ("interconnect" -> true) +
      ("interface" -> true) +
      ("intersect" -> true) +
      ("join" -> true) +
      ("join_any" -> true) +
      ("join_none" -> true) +
      ("large" -> true) +
      ("liblist" -> true) +
      ("library" -> true) +
      ("local" -> true) +
      ("localparam" -> true) +
      ("logic" -> true) +
      ("longint" -> true) +
      ("macromodule" -> true) +
      ("matches" -> true) +
      ("medium" -> true) +
      ("modport" -> true) +
      ("module" -> true) +
      ("nand" -> true) +
      ("negedge" -> true) +
      ("new" -> true) +
      ("nmos" -> true) +
      ("nor" -> true) +
      ("noshowcancelled" -> true) +
      ("not" -> true) +
      ("notif0" -> true) +
      ("notif1" -> true) +
      ("null" -> true) +
      ("or" -> true) +
      ("output" -> true) +
      ("package" -> true) +
      ("packed" -> true) +
      ("parameter" -> true) +
      ("pmos" -> true) +
      ("posedge" -> true) +
      ("primitive" -> true) +
      ("priority" -> true) +
      ("program" -> true) +
      ("property" -> true) +
      ("protected" -> true) +
      ("pull0" -> true) +
      ("pull1" -> true) +
      ("pulldown" -> true) +
      ("pullup" -> true) +
      ("pulsestyle_onevent" -> true) +
      ("pulsestyle_ondetect" -> true) +
      ("pure" -> true) +
      ("rand" -> true) +
      ("randc" -> true) +
      ("randcase" -> true) +
      ("randsequence" -> true) +
      ("rcmos" -> true) +
      ("real" -> true) +
      ("realtime" -> true) +
      ("ref" -> true) +
      ("reg" -> true) +
      ("release" -> true) +
      ("repeat" -> true) +
      ("return" -> true) +
      ("rnmos" -> true) +
      ("rpmos" -> true) +
      ("rtran" -> true) +
      ("rtranif0" -> true) +
      ("rtranif1" -> true) +
      ("scalared" -> true) +
      ("sequence" -> true) +
      ("shortint" -> true) +
      ("shortreal" -> true) +
      ("showcancelled" -> true) +
      ("signed" -> true) +
      ("small" -> true) +
      ("solve" -> true) +
      ("specify" -> true) +
      ("specparam" -> true) +
      ("static" -> true) +
      ("strength" -> true) +
      ("string" -> true) +
      ("strong0" -> true) +
      ("strong1" -> true) +
      ("struct" -> true) +
      ("super" -> true) +
      ("supply0" -> true) +
      ("supply1" -> true) +
      ("table" -> true) +
      ("tagged" -> true) +
      ("task" -> true) +
      ("this" -> true) +
      ("throughout" -> true) +
      ("time" -> true) +
      ("timeprecision" -> true) +
      ("timeunit" -> true) +
      ("tran" -> true) +
      ("tranif0" -> true) +
      ("tranif1" -> true) +
      ("tri" -> true) +
      ("tri0" -> true) +
      ("tri1" -> true) +
      ("triand" -> true) +
      ("trior" -> true) +
      ("trireg" -> true) +
      ("type" -> true) +
      ("typedef" -> true) +
      ("union" -> true) +
      ("unique" -> true) +
      ("unsigned" -> true) +
      ("use" -> true) +
      ("var" -> true) +
      ("vectored" -> true) +
      ("virtual" -> true) +
      ("void" -> true) +
      ("wait" -> true) +
      ("wait_order" -> true) +
      ("wand" -> true) +
      ("weak0" -> true) +
      ("weak1" -> true) +
      ("while" -> true) +
      ("wildcard" -> true) +
      ("wire" -> true) +
      ("with" -> true) +
      ("within" -> true) +
      ("wor" -> true) +
      ("xnor" -> true) +
      ("xor" -> true) +
      ("SYNTHESIS" -> true) +
      ("PRINTF_COND" -> true) +
      ("VCS" -> true)
}

object MemoizedHash {
  implicit def convertTo[T](e: T): MemoizedHash[T] = new MemoizedHash(e)
  implicit def convertFrom[T](f: MemoizedHash[T]): T = f.t
}

class MemoizedHash[T](val t: T) {
  override lazy val hashCode = t.hashCode
  override def equals(that: Any) = that match {
    case x: MemoizedHash[_] => t equals x.t
    case _ => false
  }
}