/*
* 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;
// Process a format string and arguments for $display, $write, $sprintf, etc
std::string AstNode::process_format_str(const std::string &sformat, int next_arg, int stage, int width_hint, bool sign_hint) {
// Other arguments are placeholders. Process the string as we go through it
std::string sout;
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, location.first_line, "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;
}
bool got_len = false;
bool got_zlen = false;
int len_value = 0;
while ('0' <= cformat && cformat <= '9')
{
if (!got_len && cformat == '0')
got_zlen = true;
got_len = true;
len_value = 10*len_value + (cformat - '0');
cformat = sformat[++i];
}
// 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':
if (got_len && len_value != 0)
goto unsupported_format;
YS_FALLTHROUGH
case 'x':
case 'X':
if (next_arg >= GetSize(children))
log_file_error(filename, location.first_line, "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, location.first_line, "Failed to evaluate system task `%s' with non-constant argument.\n", str.c_str());
break;
case 'm':
case 'M':
if (got_len)
goto unsupported_format;
break;
case 'l':
case 'L':
if (got_len)
goto unsupported_format;
break;
default:
unsupported_format:
log_file_error(filename, location.first_line, "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':
sout += stringf("%d", node_arg->bitsAsConst().as_int());
break;
case 'x':
case 'X':
{
Const val = node_arg->bitsAsConst();
while (GetSize(val) % 4 != 0)
val.bits.push_back(State::S0);
int len = GetSize(val) / 4;
for (int i = len; i < len_value; i++)
sout += got_zlen ? '0' : ' ';
for (int i = len-1; i >= 0; i--) {
Const digit = val.extract(4*i, 4);
if (digit.is_fully_def())
sout += stringf(cformat == 'x' ? "%x" : "%X", digit.as_int());
else
sout += cformat == 'x' ? "x" : "X";
}
}
break;
case 'm':
case 'M':
sout += log_id(current_module->name);
break;
case 'l':
case 'L':
sout += log_id(current_module->name);
break;
default:
log_abort();
}
}
// not a format specifier
else
sout += sformat[i];
}
return sout;
}
void AstNode::annotateTypedEnums(AstNode *template_node)
{
//check if enum
if (template_node->attributes.count(ID::enum_type)) {
//get reference to enum node:
std::string enum_type = template_node->attributes[ID::enum_type]->str.c_str();
// log("enum_type=%s (count=%lu)\n", enum_type.c_str(), current_scope.count(enum_type));
// log("current scope:\n");
// for (auto &it : current_scope)
// log(" %s\n", it.first.c_str());
log_assert(current_scope.count(enum_type) == 1);
AstNode *enum_node = current_scope.at(enum_type);
log_assert(enum_node->type == AST_ENUM);
while (enum_node->simplify(true, false, false, 1, -1, false, true)) { }
//get width from 1st enum item:
log_assert(enum_node->children.size() >= 1);
AstNode *enum_item0 = enum_node->children[0];
log_assert(enum_item0->type == AST_ENUM_ITEM);
int width;
if (!enum_item0->range_valid)
width = 1;
else if (enum_item0->range_swapped)
width = enum_item0->range_right - enum_item0->range_left + 1;
else
width = enum_item0->range_left - enum_item0->range_right + 1;
log_assert(width > 0);
//add declared enum items:
for (auto enum_item : enum_node->children){
log_assert(enum_item->type == AST_ENUM_ITEM);
//get is_signed
bool is_signed;
if (enum_item->children.size() == 1){
is_signed = false;
} else if (enum_item->children.size() == 2){
log_assert(enum_item->children[1]->type == AST_RANGE);
is_signed = enum_item->children[1]->is_signed;
} else {
log_error("enum_item children size==%lu, expected 1 or 2 for %s (%s)\n",
enum_item->children.size(),
enum_item->str.c_str(), enum_node->str.c_str()
);
}
//start building attribute string
std::string enum_item_str = "\\enum_value_";
//get enum item value
if(enum_item->children[0]->type != AST_CONSTANT){
log_error("expected const, got %s for %s (%s)\n",
type2str(enum_item->children[0]->type).c_str(),
enum_item->str.c_str(), enum_node->str.c_str()
);
}
RTLIL::Const val = enum_item->children[0]->bitsAsConst(width, is_signed);
enum_item_str.append(val.as_string());
//set attribute for available val to enum item name mappings
attributes[enum_item_str.c_str()] = mkconst_str(enum_item->str);
}
}
}
static bool name_has_dot(const std::string &name, std::string &struct_name)
{
// check if plausible struct member name \sss.mmm
std::string::size_type pos;
if (name.substr(0, 1) == "\\" && (pos = name.find('.', 0)) != std::string::npos) {
struct_name = name.substr(0, pos);
return true;
}
return false;
}
static AstNode *make_range(int left, int right, bool is_signed = false)
{
// generate a pre-validated range node for a fixed signal range.
auto range = new AstNode(AST_RANGE);
range->range_left = left;
range->range_right = right;
range->range_valid = true;
range->children.push_back(AstNode::mkconst_int(left, true));
range->children.push_back(AstNode::mkconst_int(right, true));
range->is_signed = is_signed;
return range;
}
static int range_width(AstNode *node, AstNode *rnode)
{
log_assert(rnode->type==AST_RANGE);
if (!rnode->range_valid) {
log_file_error(node->filename, node->location.first_line, "Size must be constant in packed struct/union member %s\n", node->str.c_str());
}
// note: range swapping has already been checked for
return rnode->range_left - rnode->range_right + 1;
}
[[noreturn]] static void struct_array_packing_error(AstNode *node)
{
log_file_error(node->filename, node->location.first_line, "Unpacked array in packed struct/union member %s\n", node->str.c_str());
}
static void save_struct_array_width(AstNode *node, int width)
{
// stash the stride for the array
node->multirange_dimensions.push_back(width);
}
static int get_struct_array_width(AstNode *node)
{
// the stride for the array, 1 if not an array
return (node->multirange_dimensions.empty() ? 1 : node->multirange_dimensions.back());
}
static int size_packed_struct(AstNode *snode, int base_offset)
{
// Struct members will be laid out in the structure contiguously from left to right.
// Union members all have zero offset from the start of the union.
// Determine total packed size and assign offsets. Store these in the member node.
bool is_union = (snode->type == AST_UNION);
int offset = 0;
int packed_width = -1;
// examine members from last to first
for (auto it = snode->children.rbegin(); it != snode->children.rend(); ++it) {
auto node = *it;
int width;
if (node->type == AST_STRUCT || node->type == AST_UNION) {
// embedded struct or union
width = size_packed_struct(node, base_offset + offset);
}
else {
log_assert(node->type == AST_STRUCT_ITEM);
if (node->children.size() > 0 && node->children[0]->type == AST_RANGE) {
// member width e.g. bit [7:0] a
width = range_width(node, node->children[0]);
if (node->children.size() == 2) {
if (node->children[1]->type == AST_RANGE) {
// unpacked array e.g. bit [63:0] a [0:3]
auto rnode = node->children[1];
int array_count = range_width(node, rnode);
if (array_count == 1) {
// C-type array size e.g. bit [63:0] a [4]
array_count = rnode->range_left;
}
save_struct_array_width(node, width);
width *= array_count;
}
else {
// array element must be single bit for a packed array
struct_array_packing_error(node);
}
}
// range nodes are now redundant
node->children.clear();
}
else if (node->children.size() == 1 && node->children[0]->type == AST_MULTIRANGE) {
// packed 2D array, e.g. bit [3:0][63:0] a
auto rnode = node->children[0];
if (rnode->children.size() != 2) {
// packed arrays can only be 2D
struct_array_packing_error(node);
}
int array_count = range_width(node, rnode->children[0]);
width = range_width(node, rnode->children[1]);
save_struct_array_width(node, width);
width *= array_count;
// range nodes are now redundant
node->children.clear();
}
else if (node->range_left < 0) {
// 1 bit signal: bit, logic or reg
width = 1;
}
else {
// already resolved and compacted
width = node->range_left - node->range_right + 1;
}
if (is_union) {
node->range_right = base_offset;
node->range_left = base_offset + width - 1;
}
else {
node->range_right = base_offset + offset;
node->range_left = base_offset + offset + width - 1;
}
node->range_valid = true;
}
if (is_union) {
// check that all members have the same size
if (packed_width == -1) {
// first member
packed_width = width;
}
else {
if (packed_width != width) {
log_file_error(node->filename, node->location.first_line, "member %s of a packed union has %d bits, expecting %d\n", node->str.c_str(), width, packed_width);
}
}
}
else {
offset += width;
}
}
return (is_union ? packed_width : offset);
}
[[noreturn]] static void struct_op_error(AstNode *node)
{
log_file_error(node->filename, node->location.first_line, "Unsupported operation for struct/union member %s\n", node->str.c_str()+1);
}
static AstNode *node_int(int ival)
{
return AstNode::mkconst_int(ival, true);
}
static AstNode *multiply_by_const(AstNode *expr_node, int stride)
{
return new AstNode(AST_MUL, expr_node, node_int(stride));
}
static AstNode *offset_indexed_range(int offset, int stride, AstNode *left_expr, AstNode *right_expr)
{
// adjust the range expressions to add an offset into the struct
// and maybe index using an array stride
auto left = left_expr->clone();
auto right = right_expr->clone();
if (stride > 1) {
// newleft = (left + 1) * stride - 1
left = new AstNode(AST_SUB, multiply_by_const(new AstNode(AST_ADD, left, node_int(1)), stride), node_int(1));
// newright = right * stride
right = multiply_by_const(right, stride);
}
// add the offset
if (offset) {
left = new AstNode(AST_ADD, node_int(offset), left);
right = new AstNode(AST_ADD, node_int(offset), right);
}
return new AstNode(AST_RANGE, left, right);
}
static AstNode *make_struct_index_range(AstNode *node, AstNode *rnode, int stride, int offset)
{
// generate a range node to perform either bit or array indexing
if (rnode->children.size() == 1) {
// index e.g. s.a[i]
return offset_indexed_range(offset, stride, rnode->children[0], rnode->children[0]);
}
else if (rnode->children.size() == 2) {
// slice e.g. s.a[i:j]
return offset_indexed_range(offset, stride, rnode->children[0], rnode->children[1]);
}
else {
struct_op_error(node);
}
}
static AstNode *slice_range(AstNode *rnode, AstNode *snode)
{
// apply the bit slice indicated by snode to the range rnode
log_assert(rnode->type==AST_RANGE);
auto left = rnode->children[0];
auto right = rnode->children[1];
log_assert(snode->type==AST_RANGE);
auto slice_left = snode->children[0];
auto slice_right = snode->children[1];
auto width = new AstNode(AST_SUB, slice_left->clone(), slice_right->clone());
right = new AstNode(AST_ADD, right->clone(), slice_right->clone());
left = new AstNode(AST_ADD, right->clone(), width);
return new AstNode(AST_RANGE, left, right);
}
static AstNode *make_struct_member_range(AstNode *node, AstNode *member_node)
{
// Work out the range in the packed array that corresponds to a struct member
// taking into account any range operations applicable to the current node
// such as array indexing or slicing
int range_left = member_node->range_left;
int range_right = member_node->range_right;
if (node->children.empty()) {
// no range operations apply, return the whole width
return make_range(range_left, range_right);
}
int stride = get_struct_array_width(member_node);
if (node->children.size() == 1 && node->children[0]->type == AST_RANGE) {
// bit or array indexing e.g. s.a[2] or s.a[1:0]
return make_struct_index_range(node, node->children[0], stride, range_right);
}
else if (node->children.size() == 1 && node->children[0]->type == AST_MULTIRANGE) {
// multirange, i.e. bit slice after array index, e.g. s.a[i][p:q]
log_assert(stride > 1);
auto mrnode = node->children[0];
auto element_range = make_struct_index_range(node, mrnode->children[0], stride, range_right);
// then apply bit slice range
auto range = slice_range(element_range, mrnode->children[1]);
delete element_range;
return range;
}
else {
struct_op_error(node);
}
}
static void add_members_to_scope(AstNode *snode, std::string name)
{
// add all the members in a struct or union to local scope
// in case later referenced in assignments
log_assert(snode->type==AST_STRUCT || snode->type==AST_UNION);
for (auto *node : snode->children) {
if (node->type != AST_STRUCT_ITEM) {
// embedded struct or union
add_members_to_scope(node, name + "." + node->str);
}
else {
auto member_name = name + "." + node->str;
current_scope[member_name] = node;
}
}
}
static int get_max_offset(AstNode *node)
{
// get the width from the MS member in the struct
// as members are laid out from left to right in the packed wire
log_assert(node->type==AST_STRUCT || node->type==AST_UNION);
while (node->type != AST_STRUCT_ITEM) {
node = node->children[0];
}
return node->range_left;
}
static AstNode *make_packed_struct(AstNode *template_node, std::string &name)
{
// create a wire for the packed struct
auto wnode = new AstNode(AST_WIRE);
wnode->str = name;
wnode->is_logic = true;
wnode->range_valid = true;
wnode->is_signed = template_node->is_signed;
int offset = get_max_offset(template_node);
auto range = make_range(offset, 0);
wnode->children.push_back(range);
// make sure this node is the one in scope for this name
current_scope[name] = wnode;
// add all the struct members to scope under the wire's name
add_members_to_scope(template_node, name);
return wnode;
}
// check if a node or its children contains an assignment to the given variable
static bool node_contains_assignment_to(const AstNode* node, const AstNode* var)
{
if (node->type == AST_ASSIGN_EQ || node->type == AST_ASSIGN_LE) {
// current node is iteslf an assignment
log_assert(node->children.size() >= 2);
const AstNode* lhs = node->children[0];
if (lhs->type == AST_IDENTIFIER && lhs->str == var->str)
return false;
}
for (const AstNode* child : node->children) {
// if this child shadows the given variable
if (child != var && child->str == var->str && child->type == AST_WIRE)
break; // skip the remainder of this block/scope
// depth-first short circuit
if (!node_contains_assignment_to(child, var))
return false;
}
return true;
}
static std::string prefix_id(const std::string &prefix, const std::string &str)
{
log_assert(!prefix.empty() && (prefix.front() == '$' || prefix.front() == '\\'));
log_assert(!str.empty() && (str.front() == '$' || str.front() == '\\'));
log_assert(prefix.back() == '.');
if (str.front() == '\\')
return prefix + str.substr(1);
return prefix + str;
}
// 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 overly long or deeply nested expressions, or excessive recursion?\n");
deep_recursion_warning = false;
}
static bool unevaluated_tern_branch = 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(), location.first_line, 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(ID::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(ID::nomem2reg))
continue;
if (mem->get_bool_attribute(ID::nomeminit) || get_bool_attribute(ID::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;
for (auto &it : node->attributes)
if (it.first != ID::mem2reg)
reg->attributes.emplace(it.first, it.second->clone());
reg->filename = node->filename;
reg->location = node->location;
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;
// 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, location.first_line, "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, location.first_line, "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, location.first_line, "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, location.first_line, "Failed to evaluate system task `%s' with non-constant 1st argument.\n", str.c_str());
std::string sformat = node_string->bitsAsConst().decode_string();
std::string sout = process_format_str(sformat, 1, stage, width_hint, sign_hint);
// 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_ENUM_ITEM || type == AST_DEFPARAM || type == AST_PARASET || type == AST_RANGE || type == AST_PREFIX || type == AST_TYPEDEF)