/*
* yosys -- Yosys Open SYnthesis Suite
*
* Copyright (C) 2012 Clifford Wolf <clifford@clifford.at>
*
* Permission to use, copy, modify, and/or distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*
* ---
*
* This is the AST frontend library.
*
* The AST frontend library is not a frontend on it's own but provides a
* generic abstract syntax tree (AST) abstraction for HDL code and can be
* used by HDL frontends. See "ast.h" for an overview of the API and the
* Verilog frontend for an usage example.
*
*/
#include "kernel/log.h"
#include "libs/sha1/sha1.h"
#include "frontends/verilog/verilog_frontend.h"
#include "ast.h"
#include <sstream>
#include <stdarg.h>
#include <stdlib.h>
#include <math.h>
YOSYS_NAMESPACE_BEGIN
using namespace AST;
using namespace AST_INTERNAL;
// convert the AST into a simpler AST that has all parameters substituted by their
// values, unrolled for-loops, expanded generate blocks, etc. when this function
// is done with an AST it can be converted into RTLIL using genRTLIL().
//
// this function also does all name resolving and sets the id2ast member of all
// nodes that link to a different node using names and lexical scoping.
bool AstNode::simplify(bool const_fold, bool at_zero, bool in_lvalue, int stage, int width_hint, bool sign_hint, bool in_param)
{
static int recursion_counter = 0;
static bool deep_recursion_warning = false;
if (recursion_counter++ == 1000 && deep_recursion_warning) {
log_warning("Deep recursion in AST simplifier.\nDoes this design contain insanely long expressions?\n");
deep_recursion_warning = false;
}
AstNode *newNode = NULL;
bool did_something = false;
#if 0
log("-------------\n");
log("AST simplify[%d] depth %d at %s:%d on %s %p:\n", stage, recursion_counter, filename.c_str(), linenum, type2str(type).c_str(), this);
log("const_fold=%d, at_zero=%d, in_lvalue=%d, stage=%d, width_hint=%d, sign_hint=%d, in_param=%d\n",
int(const_fold), int(at_zero), int(in_lvalue), int(stage), int(width_hint), int(sign_hint), int(in_param));
// dumpAst(NULL, "> ");
#endif
if (stage == 0)
{
log_assert(type == AST_MODULE || type == AST_INTERFACE);
deep_recursion_warning = true;
while (simplify(const_fold, at_zero, in_lvalue, 1, width_hint, sign_hint, in_param)) { }
if (!flag_nomem2reg && !get_bool_attribute("\\nomem2reg"))
{
dict<AstNode*, pool<std::string>> mem2reg_places;
dict<AstNode*, uint32_t> mem2reg_candidates, dummy_proc_flags;
uint32_t flags = flag_mem2reg ? AstNode::MEM2REG_FL_ALL : 0;
mem2reg_as_needed_pass1(mem2reg_places, mem2reg_candidates, dummy_proc_flags, flags);
pool<AstNode*> mem2reg_set;
for (auto &it : mem2reg_candidates)
{
AstNode *mem = it.first;
uint32_t memflags = it.second;
bool this_nomeminit = flag_nomeminit;
log_assert((memflags & ~0x00ffff00) == 0);
if (mem->get_bool_attribute("\\nomem2reg"))
continue;
if (mem->get_bool_attribute("\\nomeminit") || get_bool_attribute("\\nomeminit"))
this_nomeminit = true;
if (memflags & AstNode::MEM2REG_FL_FORCED)
goto silent_activate;
if (memflags & AstNode::MEM2REG_FL_EQ2)
goto verbose_activate;
if (memflags & AstNode::MEM2REG_FL_SET_ASYNC)
goto verbose_activate;
if ((memflags & AstNode::MEM2REG_FL_SET_INIT) && (memflags & AstNode::MEM2REG_FL_SET_ELSE) && this_nomeminit)
goto verbose_activate;
if (memflags & AstNode::MEM2REG_FL_CMPLX_LHS)
goto verbose_activate;
if ((memflags & AstNode::MEM2REG_FL_CONST_LHS) && !(memflags & AstNode::MEM2REG_FL_VAR_LHS))
goto verbose_activate;
// log("Note: Not replacing memory %s with list of registers (flags=0x%08lx).\n", mem->str.c_str(), long(memflags));
continue;
verbose_activate:
if (mem2reg_set.count(mem) == 0) {
std::string message = stringf("Replacing memory %s with list of registers.", mem->str.c_str());
bool first_element = true;
for (auto &place : mem2reg_places[it.first]) {
message += stringf("%s%s", first_element ? " See " : ", ", place.c_str());
first_element = false;
}
log_warning("%s\n", message.c_str());
}
silent_activate:
// log("Note: Replacing memory %s with list of registers (flags=0x%08lx).\n", mem->str.c_str(), long(memflags));
mem2reg_set.insert(mem);
}
for (auto node : mem2reg_set)
{
int mem_width, mem_size, addr_bits;
node->meminfo(mem_width, mem_size, addr_bits);
int data_range_left = node->children[0]->range_left;
int data_range_right = node->children[0]->range_right;
if (node->children[0]->range_swapped)
std::swap(data_range_left, data_range_right);
for (int i = 0; i < mem_size; i++) {
AstNode *reg = new AstNode(AST_WIRE, new AstNode(AST_RANGE,
mkconst_int(data_range_left, true), mkconst_int(data_range_right, true)));
reg->str = stringf("%s[%d]", node->str.c_str(), i);
reg->is_reg = true;
reg->is_signed = node->is_signed;
children.push_back(reg);
while (reg->simplify(true, false, false, 1, -1, false, false)) { }
}
}
AstNode *async_block = NULL;
while (mem2reg_as_needed_pass2(mem2reg_set, this, NULL, async_block)) { }
vector<AstNode*> delnodes;
mem2reg_remove(mem2reg_set, delnodes);
for (auto node : delnodes)
delete node;
}
while (simplify(const_fold, at_zero, in_lvalue, 2, width_hint, sign_hint, in_param)) { }
recursion_counter--;
return false;
}
current_filename = filename;
set_line_num(linenum);
// we do not look inside a task or function
// (but as soon as a task or function is instantiated we process the generated AST as usual)
if (type == AST_FUNCTION || type == AST_TASK) {
recursion_counter--;
return false;
}
// deactivate all calls to non-synthesis system tasks
// note that $display, $finish, and $stop are used for synthesis-time DRC so they're not in this list
if ((type == AST_FCALL || type == AST_TCALL) && (str == "$strobe" || str == "$monitor" || str == "$time" ||
str == "$dumpfile" || str == "$dumpvars" || str == "$dumpon" || str == "$dumpoff" || str == "$dumpall")) {
log_file_warning(filename, linenum, "Ignoring call to system %s %s.\n", type == AST_FCALL ? "function" : "task", str.c_str());
delete_children();
str = std::string();
}
if ((type == AST_TCALL) && (str == "$display" || str == "$write") && (!current_always || current_always->type != AST_INITIAL)) {
log_file_warning(filename, linenum, "System task `%s' outside initial block is unsupported.\n", str.c_str());
delete_children();
str = std::string();
}
// print messages if this a call to $display() or $write()
// This code implements only a small subset of Verilog-2005 $display() format specifiers,
// but should be good enough for most uses
if ((type == AST_TCALL) && ((str == "$display") || (str == "$write")))
{
int nargs = GetSize(children);
if (nargs < 1)
log_file_error(filename, linenum, "System task `%s' got %d arguments, expected >= 1.\n",
str.c_str(), int(children.size()));
// First argument is the format string
AstNode *node_string = children[0];
while (node_string->simplify(true, false, false, stage, width_hint, sign_hint, false)) { }
if (node_string->type != AST_CONSTANT)
log_file_error(filename, linenum, "Failed to evaluate system task `%s' with non-constant 1st argument.\n", str.c_str());
std::string sformat = node_string->bitsAsConst().decode_string();
// Other arguments are placeholders. Process the string as we go through it
std::string sout;
int next_arg = 1;
for (size_t i = 0; i < sformat.length(); i++)
{
// format specifier
if (sformat[i] == '%')
{
// If there's no next character, that's a problem
if (i+1 >= sformat.length())
log_file_error(filename, linenum, "System task `%s' called with `%%' at end of string.\n", str.c_str());
char cformat = sformat[++i];
// %% is special, does not need a matching argument
if (cformat == '%')
{
sout += '%';
continue;
}
// Simplify the argument
AstNode *node_arg = nullptr;
// Everything from here on depends on the format specifier
switch (cformat)
{
case 's':
case 'S':
case 'd':
case 'D':
case 'x':
case 'X':
if (next_arg >= GetSize(children))
log_file_error(filename, linenum, "Missing argument for %%%c format specifier in system task `%s'.\n",
cformat, str.c_str());
node_arg = children[next_arg++];
while (node_arg->simplify(true, false, false, stage, width_hint, sign_hint, false)) { }
if (node_arg->type != AST_CONSTANT)
log_file_error(filename, linenum, "Failed to evaluate system task `%s' with non-constant argument.\n", str.c_str());
break;
case 'm':
case 'M':
break;
default:
log_file_error(filename, linenum, "System task `%s' called with invalid/unsupported format specifier.\n", str.c_str());
break;
}
switch (cformat)
{
case 's':
case 'S':
sout += node_arg->bitsAsConst().decode_string();
break;
case 'd':
case 'D':
{
char tmp[128];
snprintf(tmp, sizeof(tmp), "%d", node_arg->bitsAsConst().as_int());
sout += tmp;
}
break;
case 'x':
case 'X':
{
char tmp[128];
snprintf(tmp, sizeof(tmp), "%x", node_arg->bitsAsConst().as_int());
sout += tmp;
}
break;
case 'm':
case 'M':
sout += log_id(current_module->name);
break;
default:
log_abort();
}
}
// not a format specifier
else
sout += sformat[i];
}
// Finally, print the message (only include a \n for $display, not for $write)
log("%s", sout.c_str());
if (str == "$display")
log("\n");
delete_children();
str = std::string();
}
// activate const folding if this is anything that must be evaluated statically (ranges, parameters, attributes, etc.)
if (type == AST_WIRE || type == AST_PARAMETER || type == AST_LOCALPARAM || type == AST_DEFPARAM || type == AST_PARASET || type == AST_RANGE || type == AST_PREFIX)
const_fold = true;
if (type == AST_IDENTIFIER && current_scope.count(str) > 0 && (current_scope[str]->type == AST_PARAMETER || current_scope[str]->type == AST_LOCALPARAM))
const_fold = true;
// in certain cases a function must be evaluated constant. this is what in_param controls.
if (type == AST_PARAMETER || type == AST_LOCALPARAM || type == AST_DEFPARAM || type == AST_PARASET || type == AST_PREFIX)
in_param = true;
std::map<std::string, AstNode*> backup_scope;
// create name resolution entries for all objects with names
// also merge multiple declarations for the same wire (e.g. "output foobar; reg foobar;")
if (type == AST_MODULE) {
current_scope.clear();
std::map<std::string, AstNode*> this_wire_scope;
for (size_t i = 0; i < children.size(); i++) {
AstNode *node = children[i];
if (node->type == AST_WIRE) {
if (node->children.size() == 1 && node->children[0]->type == AST_RANGE) {
for (auto c : node->children[0]->children) {
if (!c->is_simple_const_expr()) {
if (attributes.count("\\dynports"))
delete attributes.at("\\dynports");
attributes["\\dynports"] = AstNode::mkconst_int(1, true);
}
}
}
if (this_wire_scope.count(node->str) > 0) {
AstNode *first_node = this_wire_scope[node->str];
if (first_node->is_input && node->is_reg)
goto wires_are_incompatible;
if (!node->is_input && !node->is_output && node->is_reg && node->children.size() == 0)
goto wires_are_compatible;
if (first_node->children.size() == 0 && node->children.size() == 1 && node->children[0]->type == AST_RANGE) {
AstNode *r = node->children[0];
if (r->range_valid && r->range_left == 0 && r->range_right == 0) {
delete r;
node->children.pop_back();
}
}
if (first_node->children.size() != node->children.size())
goto wires_are_incompatible;
for (size_t j = 0; j < node->children.size(); j++) {
AstNode *n1 = first_node->children[j], *n2 = node->children[j];
if (n1->type == AST_RANGE && n2->type == AST_RANGE && n1->range_valid && n2->range_valid) {
if (n1->range_left != n2->range_left)
goto wires_are_incompatible;
if (n1->range_right != n2->range_right)
goto wires_are_incompatible;
} else if (*n1 != *n2)
goto wires_are_incompatible;
}
if (first_node->range_left != node->range_left)
goto wires_are_incompatible;
if (first_node->range_right != node->range_right)
goto wires_are_incompatible;
if (first_node->port_id == 0 && (node->is_input || node->is_output))
goto wires_are_incompatible;
wires_are_compatible:
if (node->is_input)
first_node->is_input = true;
if (node->is_output)
first_node->is_output = true;
if (node->is_reg)
first_node->is_reg = true;
if (node->is_logic)
first_node->is_logic = true;
if (node->is_signed)
first_node->is_signed = true;
for (auto &it : node->attributes) {
if (first_node->attributes.count(it.first) > 0)
delete first_node->attributes[it.first];
first_node->attributes[it.first] = it.second->clone();
}
children.erase(children.begin()+(i--));
did_something = true;
delete node;
continue;
wires_are_incompatible:
if (stage > 1)
log_file_error(filename, linenum, "Incompatible re-declaration of wire %s.\n", node->str.c_str());
continue;
}
this_wire_scope[node->str] = node;
}
if (node->type == AST_PARAMETER || node->type == AST_LOCALPARAM || node->type == AST_WIRE || node->type == AST_AUTOWIRE || node->type == AST_GENVAR ||
node->type == AST_MEMORY || node->type == AST_FUNCTION || node->type == AST_TASK || node->type == AST_DPI_FUNCTION || node->type == AST_CELL) {
backup_scope[node->str] = current_scope[node->str];
current_scope[node->str] = node;
}
}
for (size_t i = 0; i < children.size(); i++) {
AstNode *node = children[i];
if (node->type == AST_PARAMETER || node->type == AST_LOCALPARAM || node->type == AST_WIRE || node->type == AST_AUTOWIRE || node->type == AST_MEMORY)
while (node->simplify(true, false, false, 1, -1, false, node->type == AST_PARAMETER || node->type == AST_LOCALPARAM))
did_something = true;
}
}
auto backup_current_block = current_block;
auto backup_current_block_child = current_block_child;
auto backup_current_top_block = current_top_block;
auto backup_current_always = current_always;
auto backup_current_always_clocked = current_always_clocked;
if (type == AST_ALWAYS || type == AST_INITIAL)
{
if (current_always != nullptr)
log_file_error(filename, linenum, "Invalid nesting of always blocks and/or initializations.\n");
current_always = this;
current_always_clocked = false;
if (type == AST_ALWAYS)
for (auto child : children) {
if (child->type == AST_POSEDGE || child->type == AST_NEGEDGE)
current_always_clocked = true;
if (child->type == AST_EDGE && GetSize(child->children) == 1 &&
child->children[0]->type == AST_IDENTIFIER && child->children[0]->str == "\\$global_clock")
current_always_clocked = true;
}
}
int backup_width_hint = width_hint;
bool backup_sign_hint = sign_hint;
bool detect_width_simple = false;
bool child_0_is_self_determined = false;
bool child_1_is_self_determined = false;
bool child_2_is_self_determined = false;
bool children_are_self_determined = false;
bool reset_width_after_children = false;
switch (type)
{
case AST_ASSIGN_EQ:
case AST_ASSIGN_LE:
case AST_ASSIGN:
while (!children[0]->basic_prep && children[0]->simplify(false, false, true, stage, -1, false, in_param) == true)
did_something = true;
while (!children[1]->basic_prep && children[1]->simplify(false, false, false, stage, -1, false, in_param) == true)
did_something = true;
children[0]->detectSignWidth(backup_width_hint, backup_sign_hint);
children[1]->detectSignWidth(width_hint, sign_hint);
width_hint = max(width_hint, backup_width_hint);
child_0_is_self_determined = true;
// test only once, before optimizations and memory mappings but after assignment LHS was mapped to an identifier
if (children[0]->id2ast && !children[0]->was_checked) {
if ((type == AST_ASSIGN_LE || type == AST_ASSIGN_EQ) && children[0]->id2ast->is_logic)
children[0]->id2ast->is_reg = true; // if logic type is used in a block asignment
if ((type == AST_ASSIGN_LE || type == AST_ASSIGN_EQ) && !children[0]->id2ast->is_reg)
log_warning("wire '%s' is assigned in a block at %s:%d.\n", children[0]->str.c_str(), filename.c_str(), linenum);
if (type == AST_ASSIGN && children[0]->id2ast->is_reg) {
bool is_rand_reg = false;
if (children[1]->type == AST_FCALL) {
if (children[1]->str == "\\$anyconst")
is_rand_reg = true;
if (children[1]->str == "\\$anyseq")
is_rand_reg = true;
if (children[1]->str == "\\$allconst")
is_rand_reg = true;
if (children[1]->str == "\\$allseq")
is_rand_reg = true;
}
if (!is_rand_reg)
log_warning("reg '%s' is assigned in a continuous assignment at %s:%d.\n", children[0]->str.c_str(), filename.c_str(), linenum);
}
children[0]->was_checked = true;
}
break;
case AST_PARAMETER:
case AST_LOCALPARAM:
while (!children[0]->basic_prep && children[0]->simplify(false, false, false, stage, -1, false, true) == true)
did_something = true;
children[0]->detectSignWidth(width_hint, sign_hint);
if (children.size() > 1 && children[1]->type == AST_RANGE) {
while (!children[1]->basic_prep && children[1]->simplify(false, false, false, stage, -1, false, true) == true)
did_something = true;
if (!children[1]->range_valid)
log_file_error(filename, linenum, "Non-constant width range on parameter decl.\n");
width_hint = max(width_hint, children[1]->range_left - children[1]->range_right + 1);
}
break;
case AST_TO_BITS:
case AST_TO_SIGNED:
case AST_TO_UNSIGNED:
case AST_CONCAT:
case AST_REPLICATE:
case AST_REDUCE_AND:
case AST_REDUCE_OR:
case AST_REDUCE_XOR:
case AST_REDUCE_XNOR:
case AST_REDUCE_BOOL:
detect_width_simple = true;
children_are_self_determined = true;
break;
case AST_NEG:
case AST_BIT_NOT:
case AST_POS:
case AST_BIT_AND:
case AST_BIT_OR:
case AST_BIT_XOR:
case AST_BIT_XNOR:
case AST_ADD:
case AST_SUB:
case AST_MUL:
case AST_DIV:
case AST_MOD:
detect_width_simple = true;
break;
case AST_SHIFT_LEFT:
case AST_SHIFT_RIGHT:
case AST_SHIFT_SLEFT:
case AST_SHIFT_SRIGHT:
case AST_POW:
detect_width_simple = true;
child_1_is_self_determined = true;
break;
case AST_LT:
case AST_LE:
case AST_EQ:
case AST_NE:
case AST_EQX:
case AST_NEX:
case AST_GE:
case AST_GT:
width_hint = -1;
sign_hint = true;
for (auto child : children) {
while (!child->basic_prep && child->simplify(false, false, in_lvalue, stage, -1, false, in_param) == true)
did_something = true;
child->detectSignWidthWorker(width_hint, sign_hint);
}
reset_width_after_children = true;
break;
case AST_LOGIC_AND:
case AST_LOGIC_OR:
case AST_LOGIC_NOT:
detect_width_simple = true;
children_are_self_determined = true;
break;
case AST_TERNARY:
detect_width_simple = true;
child_0_is_self_determined = true;
break;
case AST_MEMRD:
detect_width_simple = true;
children_are_self_determined = true;
break;
case AST_FCALL:
case AST_TCALL:
children_are_self_determined = true;
break;
default:
width_hint = -1;
sign_hint = false;
}
if (detect_width_simple && width_hint < 0) {
if (type == AST_REPLICATE)
while (children[0]->simplify(true, false, in_lvalue, stage, -1, false, true) == true)
did_something = true;
for (auto child : children)
while (!child->basic_prep && child->simplify(false, false, in_lvalue, stage, -1, false, in_param) == true)
did_something = true;
detectSignWidth(width_hint, sign_hint);
}
if (type == AST_FCALL && str == "\\$past")
detectSignWidth(width_hint, sign_hint);
if (type == AST_TERNARY) {
int width_hint_left, width_hint_right;
bool sign_hint_left, sign_hint_right;
bool found_real_left, found_real_right;
children[1]->detectSignWidth(width_hint_left, sign_hint_left, &found_real_left);
children[2]->detectSignWidth(width_hint_right, sign_hint_right, &found_real_right);
if (found_real_left || found_real_right) {
child_1_is_self_determined = true;
child_2_is_self_determined = true;
}
}
if (type == AST_CONDX && children.size() > 0 && children.at(0)->type == AST_CONSTANT) {
for (auto &bit : children.at(0)->bits)
if (bit == State::Sz || bit == State::Sx)
bit = State::Sa;
}
if (type == AST_CONDZ && children.size() > 0 && children.at(0)->type == AST_CONSTANT) {
for (auto &bit : children.at(0)->bits)
if (bit == State::Sz)
bit = State::Sa;
}
if (const_fold && type == AST_CASE)
{
while (children[0]->simplify(const_fold, at_zero, in_lvalue, stage, width_hint, sign_hint, in_param)) { }
if (children[0]->type == AST_CONSTANT && children[0]->bits_only_01()) {
std::vector<AstNode*> new_children;
new_children.push_back(children[0]);
for (int i = 1; i < GetSize(children); i++) {
AstNode *child = children[i];
log_assert(child->type == AST_COND || child->type == AST_CONDX || child->type == AST_CONDZ);
for (auto v : child->children) {
if (v->type == AST_DEFAULT)
goto keep_const_cond;
if (v->type == AST_BLOCK)
continue;
while (v->simplify(const_fold, at_zero, in_lvalue, stage, width_hint, sign_hint, in_param)) { }
if (v->type == AST_CONSTANT && v->bits_only_01()) {
if (v->bits == children[0]->bits) {
while (i+1 < GetSize(children))
delete children[++i];