Add support for right shift by amount larger than argument width

6 files changed, 77 insertions, 14 deletions

diff --git a/src/main/scala/firrtl/Compiler.scala b/src/main/scala/firrtl/Compiler.scala
index 782d43cb..aa3eeace 100644
--- a/src/main/scala/firrtl/Compiler.scala
+++ b/src/main/scala/firrtl/Compiler.scala
@@ -73,6 +73,7 @@ object VerilogCompiler extends Compiler {
     RemoveAccesses,
     ExpandWhens,
     CheckInitialization,   
+    Legalize,
     ConstProp,
     ResolveKinds,
     InferTypes,
diff --git a/src/main/scala/firrtl/Emitter.scala b/src/main/scala/firrtl/Emitter.scala
index e9c90fd6..4b88f526 100644
--- a/src/main/scala/firrtl/Emitter.scala
+++ b/src/main/scala/firrtl/Emitter.scala
@@ -211,7 +211,11 @@ object VerilogEmitter extends Emitter {
             }
          }
          case SHIFT_LEFT_OP => Seq(cast(a0())," << ",c0())
-         case SHIFT_RIGHT_OP => Seq(a0(),"[", long_BANG(tpe(a0())) - 1,":",c0(),"]")
+         case SHIFT_RIGHT_OP => {
+           if (c0 >= long_BANG(tpe(a0)))
+             error("Verilog emitter does not support SHIFT_RIGHT >= arg width")
+           Seq(a0(),"[", long_BANG(tpe(a0())) - 1,":",c0(),"]")
+         }
          case NEG_OP => Seq("-{",cast(a0()),"}")
          case CONVERT_OP => {
             tpe(a0()) match {
diff --git a/src/main/scala/firrtl/IR.scala b/src/main/scala/firrtl/IR.scala
index ce22f010..17b16052 100644
--- a/src/main/scala/firrtl/IR.scala
+++ b/src/main/scala/firrtl/IR.scala
@@ -42,7 +42,7 @@ case class FileInfo(file: String, line: Int, column: Int) extends Info {
   override def toString(): String = s"$file@$line.$column"
 }
 
-case class FIRRTLException(str:String) extends Exception
+case class FIRRTLException(str: String) extends Exception(str)
 
 trait AST {
   def serialize: String = firrtl.Serialize.serialize(this)
@@ -110,7 +110,24 @@ case class Stop(info: Info, ret: Int, clk: Expression, en: Expression) extends S
 case class Print(info: Info, string: String, args: Seq[Expression], clk: Expression, en: Expression) extends Stmt
 case class Empty() extends Stmt
 
-trait Width extends AST 
+trait Width extends AST {
+  def +(x: Width): Width = (this, x) match {
+    case (a: IntWidth, b: IntWidth) => IntWidth(a.width + b.width)
+    case _ => UnknownWidth()
+  }
+  def -(x: Width): Width = (this, x) match {
+    case (a: IntWidth, b: IntWidth) => IntWidth(a.width - b.width)
+    case _ => UnknownWidth()
+  }
+  def max(x: Width): Width = (this, x) match {
+    case (a: IntWidth, b: IntWidth) => IntWidth(a.width max b.width)
+    case _ => UnknownWidth()
+  }
+  def min(x: Width): Width = (this, x) match {
+    case (a: IntWidth, b: IntWidth) => IntWidth(a.width min b.width)
+    case _ => UnknownWidth()
+  }
+}
 case class IntWidth(width: BigInt) extends Width 
 case class UnknownWidth() extends Width
 
diff --git a/src/main/scala/firrtl/PrimOps.scala b/src/main/scala/firrtl/PrimOps.scala
index 8a2865bb..ed3752f9 100644
--- a/src/main/scala/firrtl/PrimOps.scala
+++ b/src/main/scala/firrtl/PrimOps.scala
@@ -254,8 +254,8 @@ object PrimOps extends LazyLogging {
          }
          case SHIFT_RIGHT_OP => {
             val t = (t1()) match {
-               case (t1:UIntType) => UIntType(MINUS(w1(),c1()))
-               case (t1:SIntType) => SIntType(MINUS(w1(),c1()))
+               case (t1:UIntType) => UIntType(MAX(MINUS(w1(),c1()),ONE))
+               case (t1:SIntType) => SIntType(MAX(MINUS(w1(),c1()),ONE))
                case (t1) => UnknownType()
             }
             DoPrim(o,a,c,t)
diff --git a/src/main/scala/firrtl/passes/Passes.scala b/src/main/scala/firrtl/passes/Passes.scala
index 7490c479..1e8ceae2 100644
--- a/src/main/scala/firrtl/passes/Passes.scala
+++ b/src/main/scala/firrtl/passes/Passes.scala
@@ -1128,24 +1128,63 @@ object ExpandWhens extends Pass {
    }
 }
 
+// Replace shr by amount >= arg width with 0 for UInts and MSB for SInts
+// TODO replace UInt with zero-width wire instead
+object Legalize extends Pass {
+  def name = "Legalize"
+  def legalizeShiftRight (e: DoPrim): Expression = e.op match {
+    case SHIFT_RIGHT_OP => {
+      val amount = e.consts(0).toInt
+      val width = long_BANG(tpe(e.args(0)))
+      lazy val msb = width - 1
+      if (amount >= width) {
+        e.tpe match {
+          case t: UIntType => UIntValue(0, IntWidth(1))
+          case t: SIntType =>
+            DoPrim(BITS_SELECT_OP, e.args, Seq(msb, msb), SIntType(IntWidth(1)))
+          case t => error(s"Unsupported type ${t} for Primop Shift Right")
+        }
+      } else {
+        e
+      }
+    }
+    case _ => e
+  }
+  def run (c: Circuit): Circuit = {
+    def legalizeE (e: Expression): Expression = {
+      e map (legalizeE) match {
+        case e: DoPrim => legalizeShiftRight(e)
+        case e => e
+      }
+    }
+    def legalizeS (s: Stmt): Stmt = s map (legalizeS) map (legalizeE)
+    def legalizeM (m: Module): Module = m map (legalizeS)
+    Circuit(c.info, c.modules.map(legalizeM), c.main)
+  }
+}
+
 object ConstProp extends Pass {
    def name = "Constant Propogation"
    var mname = ""
+
    def const_prop_e (e:Expression) : Expression = {
       e map (const_prop_e) match {
          case (e:DoPrim) => {
             e.op match {
                case SHIFT_RIGHT_OP => {
-                  (e.args(0)) match {
-                     case (x:UIntValue) => {
-                        val b = x.value >> e.consts(0).toInt
-                        UIntValue(b,tpe(e).as[UIntType].get.width)
+                  val amount = e.consts(0).toInt
+                  e.args(0) match {
+                     case x: UIntValue => {
+                        val v = x.value >> amount
+                        val w = (x.width - IntWidth(amount)) max IntWidth(1)
+                        UIntValue(v, w)
                      }
-                     case (x:SIntValue) => {
-                        val b = x.value >> e.consts(0).toInt
-                        SIntValue(b,tpe(e).as[SIntType].get.width)
+                     case x: SIntValue => { // take sign bit if shift amount is larger than arg width
+                        val v = x.value >> amount
+                        val w = (x.width - IntWidth(amount)) max IntWidth(1)
+                        SIntValue(v, w)
                      }
-                     case (x) => e
+                     case _ => e
                   }
                }
                case BITS_SELECT_OP => {
diff --git a/src/test/scala/firrtlTests/IntegrationSpec.scala b/src/test/scala/firrtlTests/IntegrationSpec.scala
index eb5a7fa1..e9afd739 100644
--- a/src/test/scala/firrtlTests/IntegrationSpec.scala
+++ b/src/test/scala/firrtlTests/IntegrationSpec.scala
@@ -8,7 +8,9 @@ class IntegrationSpec extends FirrtlPropSpec {
 
   case class Test(name: String, dir: String)
 
-  val runTests = Seq(Test("GCDTester", "/integration"))
+  val runTests = Seq(Test("GCDTester", "/integration"),
+                     Test("RightShiftTester", "/integration"))
+      
 
   runTests foreach { test =>
     property(s"${test.name} should execute correctly") {