From 98a23c0c1fe018c0899d26da5bfd18fb1e0bcab5 Mon Sep 17 00:00:00 2001 From: Albert Magyar Date: Thu, 6 Feb 2020 16:29:58 -0800 Subject: Better register const prop through speculative de-optimization * Fixes #1240 * Add failing reg const prop test case from #1240 --- .../firrtl/transforms/ConstantPropagation.scala | 8 ++++++++ .../firrtlTests/ConstantPropagationTests.scala | 23 ++++++++++++++++++++++ 2 files changed, 31 insertions(+) diff --git a/src/main/scala/firrtl/transforms/ConstantPropagation.scala b/src/main/scala/firrtl/transforms/ConstantPropagation.scala index 66cf24b8..ad784559 100644 --- a/src/main/scala/firrtl/transforms/ConstantPropagation.scala +++ b/src/main/scala/firrtl/transforms/ConstantPropagation.scala @@ -490,6 +490,12 @@ class ConstantPropagation extends Transform with ResolvedAnnotationPaths { * NonConstant values. When encountering a node reference, it expands the node by to its * RHS assignment and recurses. * + * @note Some optimization of Mux trees turn 1-bit mux operators into boolean operators. This + * can stifle register constant propagations, which looks at drivers through value-preserving + * Muxes and Connects only. By speculatively expanding some 1-bit Or and And operations into + * muxes, we can obtain the best possible insight on the value of the mux with a simple peephole + * de-optimization that does not actually appear in the output code. + * * @return a RegCPEntry describing the constant prop-compatible sources driving this expression */ def regConstant(e: Expression): RegCPEntry = e match { @@ -498,6 +504,8 @@ class ConstantPropagation extends Transform with ResolvedAnnotationPaths { case WRef(nodeName, _, NodeKind, _) if nodeMap.contains(nodeName) => nodeRegCPEntries.getOrElseUpdate(nodeName, { regConstant(nodeMap(nodeName)) }) case Mux(_, tval, fval, _) => regConstant(tval).resolve(regConstant(fval)) + case DoPrim(Or, Seq(a, b), Nil, BoolType) => regConstant(Mux(a, one, b, BoolType)) + case DoPrim(And, Seq(a, b), Nil, BoolType) => regConstant(Mux(a, b, zero, BoolType)) case _ => RegCPEntry(NonConstant, NonConstant) } diff --git a/src/test/scala/firrtlTests/ConstantPropagationTests.scala b/src/test/scala/firrtlTests/ConstantPropagationTests.scala index af186cda..99b8c2f0 100644 --- a/src/test/scala/firrtlTests/ConstantPropagationTests.scala +++ b/src/test/scala/firrtlTests/ConstantPropagationTests.scala @@ -1148,6 +1148,29 @@ class ConstantPropagationIntegrationSpec extends LowTransformSpec { execute(input, check, Seq.empty) } + "Const prop of registers" should "do limited speculative expansion of optimized muxes to absorb bigger cones" in { + val input = + """circuit Top : + | module Top : + | input clock : Clock + | input reset : UInt<1> + | input en : UInt<1> + | output out : UInt<1> + | reg r : UInt<1>, clock + | when en : + | r <= UInt<1>(1) + | out <= r""".stripMargin + val check = + """circuit Top : + | module Top : + | input clock : Clock + | input reset : UInt<1> + | input en : UInt<1> + | output out : UInt<1> + | out <= UInt<1>("h1")""".stripMargin + execute(input, check, Seq.empty) + } + "A register with constant reset and all connection to either itself or the same constant" should "be replaced with that constant" in { val input = """circuit Top : -- cgit v1.2.3 From 71240a3c832160c66483e91c85223db5b74cea2b Mon Sep 17 00:00:00 2001 From: Albert Magyar Date: Fri, 7 Feb 2020 00:26:33 -0800 Subject: Refactor handling of reg const prop entries to cover more cases --- .../firrtl/transforms/ConstantPropagation.scala | 43 ++++++++++++++-------- 1 file changed, 27 insertions(+), 16 deletions(-) diff --git a/src/main/scala/firrtl/transforms/ConstantPropagation.scala b/src/main/scala/firrtl/transforms/ConstantPropagation.scala index ad784559..f450f6a6 100644 --- a/src/main/scala/firrtl/transforms/ConstantPropagation.scala +++ b/src/main/scala/firrtl/transforms/ConstantPropagation.scala @@ -87,6 +87,7 @@ object ConstantPropagation { // fact that a constant propagation loop can include both self-assignments and consistent literals. private case class RegCPEntry(r: ConstPropBinding[String], l: ConstPropBinding[Literal]) { def resolve(that: RegCPEntry) = RegCPEntry(r.resolve(that.r), l.resolve(that.l)) + def nonConstant: Boolean = r == NonConstant || l == NonConstant } } @@ -498,28 +499,38 @@ class ConstantPropagation extends Transform with ResolvedAnnotationPaths { * * @return a RegCPEntry describing the constant prop-compatible sources driving this expression */ - def regConstant(e: Expression): RegCPEntry = e match { - case lit: Literal => RegCPEntry(UnboundConstant, BoundConstant(lit)) - case WRef(regName, _, RegKind, _) => RegCPEntry(BoundConstant(regName), UnboundConstant) + + val unbound = RegCPEntry(UnboundConstant, UnboundConstant) + val selfBound = RegCPEntry(BoundConstant(lname), UnboundConstant) + + def zero = passes.RemoveValidIf.getGroundZero(ltpe) + def regConstant(e: Expression, baseCase: RegCPEntry): RegCPEntry = e match { + case lit: Literal => baseCase.resolve(RegCPEntry(UnboundConstant, BoundConstant(lit))) + case WRef(regName, _, RegKind, _) => baseCase.resolve(RegCPEntry(BoundConstant(regName), UnboundConstant)) case WRef(nodeName, _, NodeKind, _) if nodeMap.contains(nodeName) => - nodeRegCPEntries.getOrElseUpdate(nodeName, { regConstant(nodeMap(nodeName)) }) - case Mux(_, tval, fval, _) => regConstant(tval).resolve(regConstant(fval)) - case DoPrim(Or, Seq(a, b), Nil, BoolType) => regConstant(Mux(a, one, b, BoolType)) - case DoPrim(And, Seq(a, b), Nil, BoolType) => regConstant(Mux(a, b, zero, BoolType)) - case _ => RegCPEntry(NonConstant, NonConstant) + val cached = nodeRegCPEntries.getOrElseUpdate(nodeName, { regConstant(nodeMap(nodeName), unbound) }) + baseCase.resolve(cached) + case Mux(_, tval, fval, _) => + regConstant(tval, baseCase).resolve(regConstant(fval, baseCase)) + case DoPrim(Or, Seq(a, b), _, BoolType) => + val aSel = regConstant(Mux(a, one, b, BoolType), baseCase) + if (!aSel.nonConstant) aSel else regConstant(Mux(b, one, a, BoolType), baseCase) + case DoPrim(And, Seq(a, b), _, BoolType) => + val aSel = regConstant(Mux(a, b, zero, BoolType), baseCase) + if (!aSel.nonConstant) aSel else regConstant(Mux(b, a, zero, BoolType), baseCase) + case _ => + RegCPEntry(NonConstant, NonConstant) } // Updates nodeMap after analyzing the returned value from regConstant - def updateNodeMapIfConstant(e: Expression): Unit = regConstant(e) match { - case RegCPEntry(BoundConstant(`lname`), litBinding) => litBinding match { - case UnboundConstant => nodeMap(lname) = padCPExp(zero) // only self-assigns -> replace with zero - case BoundConstant(lit) => nodeMap(lname) = padCPExp(lit) // self + lit assigns -> replace with lit - case _ => - } - case RegCPEntry(UnboundConstant, BoundConstant(lit)) => nodeMap(lname) = padCPExp(lit) // only lit assigns + def updateNodeMapIfConstant(e: Expression): Unit = regConstant(e, selfBound) match { + case RegCPEntry(UnboundConstant, UnboundConstant) => nodeMap(lname) = padCPExp(zero) + case RegCPEntry(BoundConstant(_), UnboundConstant) => nodeMap(lname) = padCPExp(zero) + case RegCPEntry(UnboundConstant, BoundConstant(lit)) => nodeMap(lname) = padCPExp(lit) + case RegCPEntry(BoundConstant(_), BoundConstant(lit)) => nodeMap(lname) = padCPExp(lit) case _ => } - def zero = passes.RemoveValidIf.getGroundZero(ltpe) + def padCPExp(e: Expression) = constPropExpression(nodeMap, instMap, constSubOutputs)(pad(e, ltpe)) asyncResetRegs.get(lname) match { -- cgit v1.2.3 From ec365cece903de078c8c673348574a7b3b2ab7d4 Mon Sep 17 00:00:00 2001 From: Albert Magyar Date: Fri, 7 Feb 2020 00:27:07 -0800 Subject: Add extra 'de-optimization' opportunity for register const prop test --- src/test/scala/firrtlTests/ConstantPropagationTests.scala | 12 +++++++----- 1 file changed, 7 insertions(+), 5 deletions(-) diff --git a/src/test/scala/firrtlTests/ConstantPropagationTests.scala b/src/test/scala/firrtlTests/ConstantPropagationTests.scala index 99b8c2f0..ef52507f 100644 --- a/src/test/scala/firrtlTests/ConstantPropagationTests.scala +++ b/src/test/scala/firrtlTests/ConstantPropagationTests.scala @@ -1153,18 +1153,20 @@ class ConstantPropagationIntegrationSpec extends LowTransformSpec { """circuit Top : | module Top : | input clock : Clock - | input reset : UInt<1> | input en : UInt<1> | output out : UInt<1> - | reg r : UInt<1>, clock + | reg r1 : UInt<1>, clock + | reg r2 : UInt<1>, clock + | when en : + | r1 <= UInt<1>(1) + | r2 <= UInt<1>(0) | when en : - | r <= UInt<1>(1) - | out <= r""".stripMargin + | r2 <= r2 + | out <= xor(r1, r2)""".stripMargin val check = """circuit Top : | module Top : | input clock : Clock - | input reset : UInt<1> | input en : UInt<1> | output out : UInt<1> | out <= UInt<1>("h1")""".stripMargin -- cgit v1.2.3