10000 Make node iteration stricter by gezalore · Pull Request #4617 · verilator/verilator · GitHub
[go: up one dir, main page]
Skip to content
8000

Make node iteration stricter #4617

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
wants to merge 1 commit into
base: master
Choose a base branch
from
Open

Make node iteration stricter #4617

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
64 changes: 33 additions & 31 deletions src/V3Ast.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -733,6 +733,9 @@ void AstNode::relinkOneLink(AstNode*& pointpr, // Ref to pointer that gets set

void AstNode::addHereThisAsNext(AstNode* newp) {
// {back}->this->{next} becomes {back}->new->this->{next}
// Note: because we insert the new nodes *before* the current node, we do not
// update the iteration pointer (if any), this means the inserted new nodes
// will not be automatically iterated.
UASSERT_OBJ(!newp->backp(), newp, "New node already linked?");
UASSERT_OBJ(this->m_backp, this, "'this' node has no back, already unlinked?");
UASSERT_OBJ(newp->m_headtailp, newp, "m_headtailp not set on new node");
Expand Down Expand Up @@ -774,12 +777,6 @@ void AstNode::addHereThisAsNext(AstNode* newp) {
newp->m_headtailp = tailp;
tailp->m_headtailp = newp;
}
// Iterator fixup
if (newLastp->m_iterpp) *(newLastp->m_iterpp) = this;
if (this->m_iterpp) {
*(this->m_iterpp) = newp;
this->m_iterpp = nullptr;
}
//
debugTreeChange(this, "-addHereThisAsNext: ", __LINE__, true);
}
Expand Down Expand Up @@ -858,6 +855,7 @@ AstNode* AstNode::cloneTree(bool cloneNextLink, bool needPure) {
void AstNode::deleteNode() {
// private: Delete single node. Publicly call deleteTree() instead.
UASSERT(!m_backp, "Delete called on node with backlink still set");
UASSERT(!m_iterpp, "Delete called on node with iterpp still set");
editCountInc();
// Change links of old node so we coredump if used
this->m_nextp = reinterpret_cast<AstNode*>(0x1);
Expand Down Expand Up @@ -958,35 +956,39 @@ void AstNode::iterateAndNext(VNVisitor& v) {
// This is a very hot function
// IMPORTANT: If you replace a node that's the target of this iterator,
// then the NEW node will be iterated on next, it isn't skipped!
// Future versions of this function may require the node to have a back to be iterated;
// there's no lower level reason yet though the back must exist.
AstNode* nodep = this;
#ifdef VL_DEBUG // Otherwise too hot of a function for debug
UASSERT_OBJ(!(nodep && !nodep->m_backp), nodep, "iterateAndNext node has no back");

#ifdef VL_DEBUG
UASSERT_OBJ(m_backp, this, "iterateAndNext called on node which has no m_backp");
UASSERT_OBJ(!m_iterpp, this, "iterateAndNext called on node already under iteration");
#endif
// cppcheck-suppress knownConditionTrueFalse
if (nodep) ASTNODE_PREFETCH(nodep->m_nextp);
while (nodep) { // effectively: if (!this) return; // Callers rely on this
ASTNODE_PREFETCH(m_nextp);

AstNode* nodep = this;
do {

if (nodep->m_nextp) ASTNODE_PREFETCH(nodep->m_nextp->m_nextp);
AstNode* niterp = nodep; // Pointer may get stomped via m_iterpp if the node is edited
// Desirable check, but many places where multiple iterations are OK
// UASSERT_OBJ(!niterp->m_iterpp, niterp, "IterateAndNext under iterateAndNext may miss
// edits"); Optimization note: Doing PREFETCH_RW on m_iterpp is a net even
// cppcheck-suppress nullPointer
niterp->m_iterpp = &niterp;
niterp->accept(v);
// accept may do a replaceNode and change niterp on us...
// niterp maybe nullptr, so need cast if printing
// if (niterp != nodep) UINFO(1,"iterateAndNext edited "<<cvtToHex(nodep)
// <<" now into "<<cvtToHex(niterp)<<endl);
if (!niterp) return; // Perhaps node deleted inside accept
niterp->m_iterpp = nullptr;
if (VL_UNLIKELY(niterp != nodep)) { // Edited node inside accept

// This pointer may get changed via m_iterpp if the current node is edited
AstNode* niterp = nodep;
nodep->m_iterpp = &niterp;
nodep->accept(v);

if (VL_UNLIKELY(niterp != nodep)) {
// Node edited inside 'accept' (may have been deleted entirely)
nodep = niterp;
} else { // Unchanged node (though maybe updated m_next), just continue loop
nodep = niterp->m_nextp;
#ifdef VL_DEBUG
UASSERT_OBJ(!nodep || (nodep->m_iterpp == &niterp), nodep,
"New node already being iterated elsewhere");
#endif
} else {
// Unchanged node (though maybe updated m_next), just continue loop
nodep->m_iterpp = nullptr;
nodep = nodep->m_nextp;
#ifdef VL_DEBUG
UASSERT_OBJ(!nodep || !nodep->m_iterpp, niterp, "Next node already being iterated");
#endif
}
}
} while (nodep);
}

void AstNode::iterateListBackwardsConst(VNVisitorConst& v) {
Expand Down
35 changes: 19 additions & 16 deletions src/V3Const.cpp
View file
Open in desktop
8000
Original file line number Diff line number Diff line change
Expand Up @@ -887,7 +887,7 @@ class ConstVisitor final : public VNVisitor {
// ** must track down everywhere V3Const is called and make sure no overlaps.
// AstVar::user4p -> Used by variable marking/finding
// AstJumpLabel::user4 -> bool. Set when AstJumpGo uses this label
// AstEnum::user4 -> bool. Recursing.
// AstEnumItem::user4 -> bool. Already checked for self references

// STATE
static constexpr bool m_doShort = true; // Remove expressions that short circuit
Expand Down Expand Up @@ -2744,26 +2744,29 @@ class ConstVisitor final : public VNVisitor {
}
void visit(AstEnumItemRef* nodep) override {
iterateChildren(nodep);
UASSERT_OBJ(nodep->itemp(), nodep, "Not linked");
bool did = false;
if (nodep->itemp()->valuep()) {
// if (debug()) nodep->itemp()->valuep()->dumpTree("- visitvaref: ");
if (nodep->itemp()->user4()) {
nodep->v3error("Recursive enum value: " << nodep->itemp()->prettyNameQ());
AstEnumItem* const itemp = nodep->itemp();
UASSERT_OBJ(itemp, nodep, "Not linked");
if (!itemp->user4SetOnce() && itemp->valuep()) {
// Check for recursive self references (this should really not be here..)
const bool isRecursive = itemp->valuep()->exists([&](AstEnumItemRef* refp) { //
return refp->itemp() == itemp;
});
if (isRecursive) {
nodep->v3error("Recursive enum value: " << itemp->prettyNameQ());
} else {
nodep->itemp()->user4(true);
iterateAndNextNull(nodep->itemp()->valuep());
nodep->itemp()->user4(false);
}
if (AstConst* const valuep = VN_CAST(nodep->itemp()->valuep(), Const)) {
const V3Number& num = valuep->num();
VL_DO_DANGLING(replaceNum(nodep, num), nodep);
did = true;
// Simplify the value
iterate(itemp->valuep());
Comment on lines +2757 to +2758
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This may change itemp, so you shouldn't record itemp in a variable. (Generally true throughout V3Width - avoid remembering node pointers across iterate.)

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This is V3Const, and we are iterating the the child node valuep(), not itemp? In this case, we know itemp is not changed as it is an AstEnumItem, which should not ever be changed, only it's childern (the enum vlaue)?

}
}
bool did = false;
if (AstConst* const valuep = VN_CAST(itemp->valuep(), Const)) {
const V3Number& num = valuep->num();
VL_DO_DANGLING(replaceNum(nodep, num), nodep);
did = true;
}
if (!did && m_required) {
nodep->v3error("Expecting expression to be constant, but enum value isn't const: "
<< nodep->itemp()->prettyNameQ());
<< itemp->prettyNameQ());
}
}

Expand Down
4 changes: 4 additions & 0 deletions src/V3Depth.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -66,6 +66,8 @@ class DepthVisitor final : public VNVisitor {
AstAssign* const assp = new AstAssign{
nodep->fileline(), new AstVarRef{nodep->fileline(), varp, VAccess::WRITE}, nodep};
m_stmtp->addHereThisAsNext(assp);
// Process the new assignment, in case it still contains de 6855 ep expressions
visitStmt(assp);
}

// VISITORS
Expand Down Expand Up @@ -95,6 +97,8 @@ class DepthVisitor final : public VNVisitor {
}
void visitStmt(AstNodeStmt* nodep) {
VL_RESTORER(m_stmtp);
VL_RESTORER(m_depth);
VL_RESTORER(m_maxdepth);
{
m_stmtp = nodep;
m_depth = 0;
Expand Down
12 changes: 6 additions & 6 deletions src/V3LinkJump.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -235,15 +235,15 @@ class LinkJumpVisitor final : public VNVisitor {
iterateAndNextNull(nodep->stmtsp());
}
AstNodeExpr* const condp = nodep->condp() ? nodep->condp()->unlinkFrBack() : nullptr;
AstNode* const bodyp = nodep->stmtsp() ? nodep->stmtsp()->unlinkFrBack() : nullptr;
AstWhile* const whilep = new AstWhile{nodep->fileline(), condp, bodyp};
nodep->replaceWith(whilep);
VL_DO_DANGLING(nodep->deleteTree(), nodep);
if (bodyp) {
if (AstNode* const bodyp = nodep->stmtsp() ? nodep->stmtsp()->unlinkFrBack() : nullptr) {
AstNode* const copiedBodyp = bodyp->cloneTree(false);
addPrefixToBlocksRecurse(copiedBodyp);
whilep->addHereThisAsNext(copiedBodyp);
copiedBodyp->addNext(new AstWhile{nodep->fileline(), condp, bodyp});
nodep->replaceWith(copiedBodyp);
} else {
nodep->replaceWith(new AstWhile{nodep->fileline(), condp, nullptr});
}
VL_DO_DANGLING(nodep->deleteTree(), nodep);
}
void visit(AstForeach* nodep) override {
VL_RESTORER(m_loopp);
Expand Down
37 changes: 19 additions & 18 deletions src/V3Premit.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -93,22 +93,6 @@ class PremitVisitor final : public VNVisitor {
}
}

void insertBeforeStmt(AstNode* newp) {
// Insert newp before m_stmtp
if (m_inWhilep) {
// Statements that are needed for the 'condition' in a while
// actually have to be put before & after the loop, since we
// can't do any statements in a while's (cond).
m_inWhilep->addPrecondsp(newp);
} else if (m_inTracep) {
m_inTracep->addPrecondsp(newp);
} else if (m_stmtp) {
m_stmtp->addHereThisAsNext(newp);
} else {
newp->v3fatalSrc("No statement insertion point.");
}
}

void createDeepTemp(AstNodeExpr* nodep, bool noSubst) {
if (nodep->user1SetOnce()) return; // Only add another assignment for this node

Expand All @@ -117,6 +101,7 @@ class PremitVisitor final : public VNVisitor {

FileLine* const fl = nodep->fileline();
AstVar* varp = nullptr;
AstAssign* assignp = nullptr;
AstConst* const constp = VN_CAST(nodep, Const);
const bool useConstPool = constp // Is a constant
&& (constp->width() >= STATIC_CONST_MIN_WIDTH) // Large enough
Expand All @@ -134,14 +119,29 @@ class PremitVisitor final : public VNVisitor {
nodep->dtypep()};
m_cfuncp->addInitsp(varp);
// Put assignment before the referencing statement
insertBeforeStmt(new AstAssign{fl, new AstVarRef{fl, varp, VAccess::WRITE}, nodep});
assignp = new AstAssign{fl, new AstVarRef{fl, varp, VAccess::WRITE}, nodep};
if (m_inWhilep) {
// Statements that are needed for the 'condition' in a while
// actually have to be put before & after the loop, since we
// can't do any statements in a while's (cond).
m_inWhilep->addPrecondsp(assignp);
} else if (m_inTracep) {
m_inTracep->addPrecondsp(assignp);
} else if (m_stmtp) {
m_stmtp->addHereThisAsNext(assignp);
} else {
assignp->v3fatalSrc("No statement insertion point.");
}
}

// Do not remove VarRefs to this in V3Const
if (noSubst) varp->noSubst(true);

// Replace node with VarRef to new Var
relinker.relink(new AstVarRef{fl, varp, VAccess::READ});

// Recursive expressions
if (assignp) iterate(assignp);
}

// VISITORS
Expand Down Expand Up @@ -357,7 +357,8 @@ class PremitVisitor final : public VNVisitor {
iterateChildren(nodep);
// Any strings sent to a display must be var of string data type,
// to avoid passing a pointer to a temporary.
for (AstNodeExpr* expp = nodep->exprsp(); expp; expp = VN_AS(expp->nextp(), NodeExpr)) {
for (AstNodeExpr *expp = nodep->exprsp(), *nextp; expp; expp = nextp) {
nextp = VN_AS(expp->nextp(), NodeExpr);
if (expp->dtypep()->basicp() && expp->dtypep()->basicp()->isString()
&& !VN_IS(expp, VarRef)) {
createDeepTemp(expp, true);
Expand Down
12 changes: 7 additions & 5 deletions src/V3Task.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1391,7 +1391,10 @@ class TaskVisitor final : public VNVisitor {
if (debug() >= 9) nodep->dumpTree("- newstmt: ");
UASSERT_OBJ(m_insStmtp, nodep, "Function call not underneath a statement");
if (debug() >= 9) newp->dumpTree("- newfunc: ");
m_insStmtp->addHereThisAsNext(newp);
AstBegin* const tempp = new AstBegin{nodep->fileline(), "[EditWrapper]", newp};
iterateAndNextNull(newp);
m_insStmtp->addHereThisAsNext(tempp->stmtsp()->unlinkFrBackWithNext());
VL_DO_DANGLING(tempp->deleteTree(), tempp);
}

// VISITORS
Expand Down Expand Up @@ -1552,6 +1555,7 @@ class TaskVisitor final : public VNVisitor {
}
}
void visit(AstWhile* nodep) override {
VL_RESTORER(m_insStmtp);
// Special, as statements need to be put in different places
// Preconditions insert first just before themselves (the normal
// rule for other statement types)
Expand All @@ -1564,23 +1568,21 @@ class TaskVisitor final : public VNVisitor {
m_insStmtp = nullptr; // First thing should be new statement
iterateAndNextNull(nodep->stmtsp());
iterateAndNextNull(nodep->incsp());
// Done the loop
m_insStmtp = nullptr; // Next thing should be new statement
}
void visit(AstNodeFor* nodep) override { // LCOV_EXCL_LINE
nodep->v3fatalSrc(
"For statements should have been converted to while statements in V3Begin.cpp");
}
void visit(AstNodeStmt* nodep) override {
VL_RESTORER(m_insStmtp);
m_insStmtp = nodep;
iterateChildren(nodep);
m_insStmtp = nullptr; // Next thing should be new statement
}
void visit(AstStmtExpr* nodep) override {
VL_RESTORER(m_insStmtp);
m_insStmtp = nodep;
iterateChildren(nodep);
if (!nodep->exprp()) VL_DO_DANGLING(nodep->unlinkFrBack()->deleteTree(), nodep);
m_insStmtp = nullptr; // Next thing should be new statement
}
void visit(AstSenItem* nodep) override {
UASSERT_OBJ(!m_inSensesp, nodep, "Senitem under senitem?");
Expand Down
16 changes: 10 additions & 6 deletions src/V3Width.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2094,16 +2094,20 @@ class WidthVisitor final : public VNVisitor {
// We can't skip this step when width()!=0, as creating a AstVar
// with non-constant range gets size 1, not size 0. So use didWidth().
if (nodep->didWidth()) return;
if (nodep->doingWidth()) { // Early exit if have circular parameter definition
UASSERT_OBJ(nodep->valuep(), nodep, "circular, but without value");
nodep->doingWidth(true);

// Check for recursive initialization
std::function<bool(AstNode*)> isRecursive = [&](AstNode* np) -> bool {
return np && np->exists([&](AstNodeVarRef* refp) {
return refp->varp() == nodep || isRecursive(refp->varp()->valuep());
});
};
Comment on lines +2100 to +2104
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I preferred the old form as if we ever have another way to get to the var twice it will detect, and also IMO was easier to understand. Was this needed to prevent a new assertion?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This is needed because of the assertions: you can't call iterateAndNext on the same node twice (recursively). Doing so was never really safe to do due to the later call stomping m_iterpp hence edits in the higher call would have been borked.

if (isRecursive(nodep->valuep())) {
nodep->v3error("Variable's initial value is circular: " << nodep->prettyNameQ());
pushDeletep(nodep->valuep()->unlinkFrBack());
nodep->valuep(new AstConst{nodep->fileline(), AstConst::BitTrue{}});
nodep->dtypeFrom(nodep->valuep());
nodep->didWidth(true);
return;
}
nodep->doingWidth(true);

// Make sure dtype is sized
nodep->dtypep(iterateEditMoveDTypep(nodep, nodep->subDTypep()));
UASSERT_OBJ(nodep->dtypep(), nodep, "No dtype determined for var");
Expand Down
0