From 8de2e863af4233aca0a0ca0eef4477d216f7a227 Mon Sep 17 00:00:00 2001 From: Zachary Snow Date: Fri, 12 Feb 2021 14:25:34 -0500 Subject: [PATCH] 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. --- frontends/ast/ast.h | 3 ++ frontends/ast/genrtlil.cc | 35 +++++++++++++ frontends/ast/simplify.cc | 100 ++++++++++++++++++++++++++++++-------- tests/various/fib_tern.v | 70 ++++++++++++++++++++++++++ tests/various/fib_tern.ys | 6 +++ 5 files changed, 195 insertions(+), 19 deletions(-) create mode 100644 tests/various/fib_tern.v create mode 100644 tests/various/fib_tern.ys 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 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 visited; + std::function 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::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 diff --git a/tests/various/fib_tern.v b/tests/various/fib_tern.v new file mode 100644 index 000000000..fefde74ce --- /dev/null +++ b/tests/various/fib_tern.v @@ -0,0 +1,70 @@ +module gate( + off, fib0, fib1, fib2, fib3, fib4, fib5, fib6, fib7, fib8, fib9 +); + input wire signed [31:0] off; + + function automatic blah( + input x + ); + blah = x; + endfunction + + function automatic integer fib( + input integer k + ); + fib = k == 0 + ? 0 + : k == 1 + ? 1 + : fib(k - 1) + fib(k - 2); + endfunction + + function automatic integer fib_wrap( + input integer k, + output integer o + ); + o = off + fib(k); + endfunction + + output integer fib0; + output integer fib1; + output integer fib2; + output integer fib3; + output integer fib4; + output integer fib5; + output integer fib6; + output integer fib7; + output integer fib8; + output integer fib9; + + initial begin : blk + integer unused; + unused = fib_wrap(0, fib0); + unused = fib_wrap(1, fib1); + unused = fib_wrap(2, fib2); + unused = fib_wrap(3, fib3); + unused = fib_wrap(4, fib4); + unused = fib_wrap(5, fib5); + unused = fib_wrap(6, fib6); + unused = fib_wrap(7, fib7); + unused = fib_wrap(8, fib8); + unused = fib_wrap(9, fib9); + end +endmodule + +module gold( + off, fib0, fib1, fib2, fib3, fib4, fib5, fib6, fib7, fib8, fib9 +); + input wire signed [31:0] off; + + output integer fib0 = off + 0; + output integer fib1 = off + 1; + output integer fib2 = off + 1; + output integer fib3 = off + 2; + output integer fib4 = off + 3; + output integer fib5 = off + 5; + output integer fib6 = off + 8; + output integer fib7 = off + 13; + output integer fib8 = off + 21; + output integer fib9 = off + 34; +endmodule diff --git a/tests/various/fib_tern.ys b/tests/various/fib_tern.ys new file mode 100644 index 000000000..e5bf186e1 --- /dev/null +++ b/tests/various/fib_tern.ys @@ -0,0 +1,6 @@ +read_verilog fib_tern.v +hierarchy +proc +equiv_make gold gate equiv +equiv_simple +equiv_status -assert -- 2.30.2