From 943389cdd50e8c77d76f64ba9abffa5190e5106a Mon Sep 17 00:00:00 2001
From: C-Elegans <mtnolan2640@gmail.com>
Date: Sun, 15 Jan 2017 09:23:04 -0500
Subject: [PATCH] Fix issue #269, optimize signed compare with 0

add opt_compare pass and add it to opt
for a < 0:
    if a is signed, replace with a[max_bit-1]
for a >= 0:
    if a is signed, replace with ~a[max_bit-1]
---
 passes/opt/Makefile.inc   |  1 +
 passes/opt/opt.cc         |  2 +
 passes/opt/opt_compare.cc | 78 +++++++++++++++++++++++++++++++++++++++
 3 files changed, 81 insertions(+)
 create mode 100644 passes/opt/opt_compare.cc

diff --git a/passes/opt/Makefile.inc b/passes/opt/Makefile.inc
index a8b1537bb..a15c4184d 100644
--- a/passes/opt/Makefile.inc
+++ b/passes/opt/Makefile.inc
@@ -6,6 +6,7 @@ OBJS += passes/opt/opt_reduce.o
 OBJS += passes/opt/opt_rmdff.o
 OBJS += passes/opt/opt_clean.o
 OBJS += passes/opt/opt_expr.o
+OBJS += passes/opt/opt_compare.o
 
 ifneq ($(SMALL),1)
 OBJS += passes/opt/share.o
diff --git a/passes/opt/opt.cc b/passes/opt/opt.cc
index 021c1a03f..b689be480 100644
--- a/passes/opt/opt.cc
+++ b/passes/opt/opt.cc
@@ -128,6 +128,7 @@ struct OptPass : public Pass {
 		{
 			while (1) {
 				Pass::call(design, "opt_expr" + opt_expr_args);
+				Pass::call(design, "opt_compare");
 				Pass::call(design, "opt_merge" + opt_merge_args);
 				design->scratchpad_unset("opt.did_something");
 				Pass::call(design, "opt_rmdff" + opt_rmdff_args);
@@ -141,6 +142,7 @@ struct OptPass : public Pass {
 		else
 		{
 			Pass::call(design, "opt_expr" + opt_expr_args);
+			Pass::call(design, "opt_compare");
 			Pass::call(design, "opt_merge -nomux" + opt_merge_args);
 			while (1) {
 				design->scratchpad_unset("opt.did_something");
diff --git a/passes/opt/opt_compare.cc b/passes/opt/opt_compare.cc
new file mode 100644
index 000000000..15b547e6f
--- /dev/null
+++ b/passes/opt/opt_compare.cc
@@ -0,0 +1,78 @@
+#include "kernel/yosys.h"
+#include "kernel/sigtools.h"
+#include "kernel/utils.h"
+USING_YOSYS_NAMESPACE
+PRIVATE_NAMESPACE_BEGIN
+void replace_le_cell(Cell* cell, Module* module){
+	RTLIL::SigSpec a = cell->getPort("\\A");
+	RTLIL::SigSpec b = cell->getPort("\\B");
+	RTLIL::SigSpec y(RTLIL::State::S0, cell->parameters["\\Y_WIDTH"].as_int());
+	if(b.is_fully_const() && b.is_fully_zero() ){ 
+		if(cell->parameters["\\A_SIGNED"].as_bool()){
+			// a < 0, can be replaced with a[MAX_BIT]
+			log("Found x < 0 (signed), replacing with the last bit\n");
+			int a_width = cell->parameters["\\A_WIDTH"].as_int();
+			if(a_width > 0){
+				y[0] = a[a_width-1];
+				module->connect(cell->getPort("\\Y"), y);
+				module->remove(cell);
+			}
+		}
+	} 
+}
+void replace_ge_cell(Cell* cell, Module* module){
+	RTLIL::SigSpec a = cell->getPort("\\A");
+	RTLIL::SigSpec b = cell->getPort("\\B");
+	RTLIL::SigSpec y = cell->getPort("\\Y");
+	if(b.is_fully_const() && b.is_fully_zero()){
+		if(cell->parameters["\\A_SIGNED"].as_bool()){
+			log("Found x >= 0 (signed), optimizing\n");
+			RTLIL::SigSpec a_prime(RTLIL::State::S0, cell->parameters["\\Y_WIDTH"].as_int());
+			int a_width = cell->parameters["\\A_WIDTH"].as_int();
+			if(a_width > 0){
+				a_prime[0] = a[a_width-1];
+				module->remove(cell);
+				module->addNot("$not", a_prime, y,false);
+			}
+		}
+	}
+}
+void optimize_compares(Design* design, Module* module){
+	log_header(design, "Executing OPT_COMPARE pass.\n");
+	log_push();
+	TopoSort<RTLIL::Cell*, RTLIL::IdString::compare_ptr_by_name<RTLIL::Cell>> cells;
+	for(auto cell: module->cells())
+		if(design->selected(module,cell) && cell->type[0] == '$'){
+			cells.node(cell);
+		}
+	cells.sort();
+	for (auto cell: cells.sorted){
+		if (cell->type == "$lt"){
+			replace_le_cell(cell,module);
+		}
+		else if(cell->type == "$ge"){
+			replace_ge_cell(cell,module);
+		}
+	}
+
+}
+struct OptCompare : public Pass {
+	OptCompare() : Pass("opt_compare") {}
+	virtual void execute(vector<string>, Design* design){
+		for(auto module: design->selected_modules())
+			optimize_compares(design,module);
+	}
+	virtual void help() {
+		log("\n");
+		log("opt_compare\n");
+		log("\n");
+		log("This pass optimizes some signed compares with 0.\n");
+		log("In particular, it replaces a < 0 with the msb of a,\n");
+		log("and a >= 0 with the inverted msb of a.\n");
+		log("\n");
+
+	}
+} OptCompare;
+
+
+PRIVATE_NAMESPACE_END
-- 
2.30.2