verilog: support recursive functions using ternary expressions

This adds a mechanism for marking certain portions of elaboration as
occurring within unevaluated ternary branches. To enable elaboration of
the overall ternary, this also adds width detection for these
unelaborated function calls.

3 files changed, 119 insertions, 19 deletions

diff --git a/frontends/ast/ast.h b/frontends/ast/ast.h
index d8818df31..8cc7b474f 100644
--- a/frontends/ast/ast.h
+++ b/frontends/ast/ast.h
@@ -270,6 +270,9 @@ namespace AST
 		bool is_simple_const_expr();
 		std::string process_format_str(const std::string &sformat, int next_arg, int stage, int width_hint, bool sign_hint);
 
+		bool is_recursive_function() const;
+		std::pair<AstNode*, AstNode*> get_tern_choice();
+
 		// create a human-readable text representation of the AST (for debugging)
 		void dumpAst(FILE *f, std::string indent) const;
 		void dumpVlog(FILE *f, std::string indent) const;
diff --git a/frontends/ast/genrtlil.cc b/frontends/ast/genrtlil.cc
index 24f5e1bef..713e34eb1 100644
--- a/frontends/ast/genrtlil.cc
+++ b/frontends/ast/genrtlil.cc
@@ -944,6 +944,41 @@ void AstNode::detectSignWidthWorker(int &width_hint, bool &sign_hint, bool *foun
 			}
 			break;
 		}
+		if (current_scope.count(str))
+		{
+			// This width detection is needed for function calls which are
+			// unelaborated, which currently only applies to calls to recursive
+			// functions reached by unevaluated ternary branches.
+			const AstNode *func = current_scope.at(str);
+			if (func->type != AST_FUNCTION)
+				log_file_error(filename, location.first_line, "Function call to %s resolved to something that isn't a function!\n", RTLIL::unescape_id(str).c_str());
+			const AstNode *wire = nullptr;
+			for (const AstNode *child : func->children)
+				if (child->str == func->str) {
+					wire = child;
+					break;
+				}
+			log_assert(wire && wire->type == AST_WIRE);
+			sign_hint = wire->is_signed;
+			width_hint = 1;
+			if (!wire->children.empty())
+			{
+				log_assert(wire->children.size() == 1);
+				const AstNode *range = wire->children.at(0);
+				log_assert(range->type == AST_RANGE && range->children.size() == 2);
+				AstNode *left = range->children.at(0)->clone();
+				AstNode *right = range->children.at(1)->clone();
+				while (left->simplify(true, false, false, 1, -1, false, true)) { }
+				while (right->simplify(true, false, false, 1, -1, false, true)) { }
+				if (left->type != AST_CONSTANT || right->type != AST_CONSTANT)
+					log_file_error(filename, location.first_line, "Function %s has non-constant width!",
+							RTLIL::unescape_id(str).c_str());
+				width_hint = abs(int(left->asInt(true) - right->asInt(true)));
+				delete left;
+				delete right;
+			}
+			break;
+		}
 		YS_FALLTHROUGH
 
 	// everything should have been handled above -> print error if not.
diff --git a/frontends/ast/simplify.cc b/frontends/ast/simplify.cc
index 402b7257b..3c315f7ff 100644
--- a/frontends/ast/simplify.cc
+++ b/frontends/ast/simplify.cc
@@ -575,6 +575,8 @@ bool AstNode::simplify(bool const_fold, bool at_zero, bool in_lvalue, int stage,
 		deep_recursion_warning = false;
 	}
 
+	static bool unevaluated_tern_branch = false;
+
 	AstNode *newNode = NULL;
 	bool did_something = false;
 
@@ -1091,7 +1093,6 @@ bool AstNode::simplify(bool const_fold, bool at_zero, bool in_lvalue, int stage,
 		break;
 
 	case AST_TERNARY:
-		detect_width_simple = true;
 		child_0_is_self_determined = true;
 		break;
 
@@ -1124,6 +1125,24 @@ bool AstNode::simplify(bool const_fold, bool at_zero, bool in_lvalue, int stage,
 		detectSignWidth(width_hint, sign_hint);
 
 	if (type == AST_TERNARY) {
+		if (width_hint < 0) {
+			while (!children[0]->basic_prep && children[0]->simplify(true, false, in_lvalue, stage, -1, false, in_param))
+				did_something = true;
+
+			bool backup_unevaluated_tern_branch = unevaluated_tern_branch;
+			AstNode *chosen = get_tern_choice().first;
+
+			unevaluated_tern_branch = backup_unevaluated_tern_branch || chosen == children[2];
+			while (!children[1]->basic_prep && children[1]->simplify(false, false, in_lvalue, stage, -1, false, in_param))
+				did_something = true;
+
+			unevaluated_tern_branch = backup_unevaluated_tern_branch || chosen == children[1];
+			while (!children[2]->basic_prep && children[2]->simplify(false, false, in_lvalue, stage, -1, false, in_param))
+				did_something = true;
+
+			unevaluated_tern_branch = backup_unevaluated_tern_branch;
+			detectSignWidth(width_hint, sign_hint);
+		}
 		int width_hint_left, width_hint_right;
 		bool sign_hint_left, sign_hint_right;
 		bool found_real_left, found_real_right;
@@ -1187,6 +1206,7 @@ bool AstNode::simplify(bool const_fold, bool at_zero, bool in_lvalue, int stage,
 	for (size_t i = 0; i < children.size(); i++) {
 		bool did_something_here = true;
 		bool backup_flag_autowire = flag_autowire;
+		bool backup_unevaluated_tern_branch = unevaluated_tern_branch;
 		if ((type == AST_GENFOR || type == AST_FOR) && i >= 3)
 			break;
 		if ((type == AST_GENIF || type == AST_GENCASE) && i >= 1)
@@ -1199,6 +1219,10 @@ bool AstNode::simplify(bool const_fold, bool at_zero, bool in_lvalue, int stage,
 			break;
 		if (type == AST_DEFPARAM && i == 0)
 			flag_autowire = true;
+		if (type == AST_TERNARY && i > 0 && !unevaluated_tern_branch) {
+			AstNode *chosen = get_tern_choice().first;
+			unevaluated_tern_branch = chosen && chosen != children[i];
+		}
 		while (did_something_here && i < children.size()) {
 			bool const_fold_here = const_fold, in_lvalue_here = in_lvalue;
 			int width_hint_here = width_hint;
@@ -1238,6 +1262,7 @@ bool AstNode::simplify(bool const_fold, bool at_zero, bool in_lvalue, int stage,
 			did_something = true;
 		}
 		flag_autowire = backup_flag_autowire;
+		unevaluated_tern_branch = backup_unevaluated_tern_branch;
 	}
 	for (auto &attr : attributes) {
 		while (attr.second->simplify(true, false, false, stage, -1, false, true))
@@ -3177,6 +3202,8 @@ skip_dynamic_range_lvalue_expansion:;
 		std::string prefix = sstr.str();
 
 		AstNode *decl = current_scope[str];
+		if (unevaluated_tern_branch && decl->is_recursive_function())
+			goto replace_fcall_later;
 		decl = decl->clone();
 		decl->replace_result_wire_name_in_function(str, "$result"); // enables recursion
 		decl->expand_genblock(prefix);
@@ -3610,24 +3637,9 @@ replace_fcall_later:;
 		case AST_TERNARY:
 			if (children[0]->isConst())
 			{
-				bool found_sure_true = false;
-				bool found_maybe_true = false;
-
-				if (children[0]->type == AST_CONSTANT)
-					for (auto &bit : children[0]->bits) {
-						if (bit == RTLIL::State::S1)
-							found_sure_true = true;
-						if (bit > RTLIL::State::S1)
-							found_maybe_true = true;
-					}
-				else
-					found_sure_true = children[0]->asReal(sign_hint) != 0;
-
-				AstNode *choice = NULL, *not_choice = NULL;
-				if (found_sure_true)
-					choice = children[1], not_choice = children[2];
-				else if (!found_maybe_true)
-					choice = children[2], not_choice = children[1];
+				auto pair = get_tern_choice();
+				AstNode *choice = pair.first;
+				AstNode *not_choice = pair.second;
 
 				if (choice != NULL) {
 					if (choice->type == AST_CONSTANT) {
@@ -4845,4 +4857,54 @@ void AstNode::allocateDefaultEnumValues()
 	}
 }
 
+bool AstNode::is_recursive_function() const
+{
+	std::set<const AstNode *> visited;
+	std::function<bool(const AstNode *node)> visit = [&](const AstNode *node) {
+		if (visited.count(node))
+			return node == this;
+		visited.insert(node);
+		if (node->type == AST_FCALL) {
+			auto it = current_scope.find(node->str);
+			if (it != current_scope.end() && visit(it->second))
+				return true;
+		}
+		for (const AstNode *child : node->children) {
+			if (visit(child))
+				return true;
+		}
+		return false;
+	};
+
+	log_assert(type == AST_FUNCTION);
+	return visit(this);
+}
+
+std::pair<AstNode*, AstNode*> AstNode::get_tern_choice()
+{
+	if (!children[0]->isConst())
+		return {};
+
+	bool found_sure_true = false;
+	bool found_maybe_true = false;
+
+	if (children[0]->type == AST_CONSTANT)
+		for (auto &bit : children[0]->bits) {
+			if (bit == RTLIL::State::S1)
+				found_sure_true = true;
+			if (bit > RTLIL::State::S1)
+				found_maybe_true = true;
+		}
+	else
+		found_sure_true = children[0]->asReal(true) != 0;
+
+	AstNode *choice = nullptr, *not_choice = nullptr;
+	if (found_sure_true)
+		choice = children[1], not_choice = children[2];
+	else if (!found_maybe_true)
+		choice = children[2], not_choice = children[1];
+
+	return {choice, not_choice};
+}
+
 YOSYS_NAMESPACE_END