10000 Make node iteration stricter · verilator/verilator@56b0afd · GitHub
[go: up one dir, main page]
Skip to content

Commit 56b0afd

Browse files
gezaloregezalore
committed
Make node iteration stricter
This is a prep patch for an experiment on removing m_iterpp (which I have in a hacked up form, and does not actually help much, 1.2% memory saving, yay...). Even if we don't land that, I think we want these changes that makes iteration a little bit stricter. Notably, there are assertions (only under VL_DEBUG, due to being in hot code), that ensure that we don't recursively iterate the same node. We used to do this in a few places (which I fixed), but this is generally not safe due to the recursive all to iterateAndNext overwriting m_iterpp, and hence any subsequent edits would be unsafe. Apart from the direct recursion, we also need to prevent addHereThisAsNext from updating the iteration pointer. I think this is a good thing. Previously it used to force iteration to restart on the nodes inserted *before* the currently iterated node, which would also mean that the currently iterated node would then be visited again, as it became a successor of the inserted node. With this patch, iteration continues with the edited node only if it's replacing the current node, or if the new node is a successor (nextp) of the current node, but not if the edit is adding the node before the current node. I fixed the few places (V3Premit, V3Task) where we used to rely on the old behaviour. The fix is simply to explicitly iterate the new nodes you insert before the current node. Patch is performance neutral.
1 parent 95c4ade commit 56b0afd

File tree

5 files changed

+85
-76
lines changed

5 files changed

+85
-76
lines changed

‎src/V3Ast.cpp

Lines changed: 30 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -774,12 +774,6 @@ void AstNode::addHereThisAsNext(AstNode* newp) {
774774
newp->m_headtailp = tailp;
775775
tailp->m_headtailp = newp;
776776
}
777-
// Iterator fixup
778-
if (newLastp->m_iterpp) *(newLastp->m_iterpp) = this;
779-
if (this->m_iterpp) {
780-
*(this->m_iterpp) = newp;
781-
this->m_iterpp = nullptr;
782-
}
783777
//
784778
debugTreeChange(this, "-addHereThisAsNext: ", __LINE__, true);
785779
}
@@ -858,6 +852,7 @@ AstNode* AstNode::cloneTree(bool cloneNextLink, bool needPure) {
858852
void AstNode::deleteNode() {
859853
// private: Delete single node. Publicly call deleteTree() instead.
860854
UASSERT(!m_backp, "Delete called on node with backlink still set");
855+
UASSERT(!m_iterpp, "Delete called on node with iterpp still set");
861856
editCountInc();
862857
// Change links of old node so we coredump if used
863858
this->m_nextp = reinterpret_cast<AstNode*>(0x1);
@@ -958,35 +953,39 @@ void AstNode::iterateAndNext(VNVisitor& v) {
958953
// This is a very hot function
959954
// IMPORTANT: If you replace a node that's the target of this iterator,
960955
// then the NEW node will be iterated on next, it isn't skipped!
961-
// Future versions of this function may require the node to have a back to be iterated;
962-
// there's no lower level reason yet though the back must exist.
963-
AstNode* nodep = this;
964-
#ifdef VL_DEBUG // Otherwise too hot of a function for debug
965-
UASSERT_OBJ(!(nodep && !nodep->m_backp), nodep, "iterateAndNext node has no back");
956+
957+
#ifdef VL_DEBUG
958+
UASSERT_OBJ(m_backp, this, "iterateAndNext called on node which has no m_backp");
959+
UASSERT_OBJ(!m_iterpp, this, "iterateAndNext called on node already under iteration");
966960
#endif
967-
// cppcheck-suppress knownConditionTrueFalse
968-
if (nodep) ASTNODE_PREFETCH(nodep->m_nextp);
969-
while (nodep) { // effectively: if (!this) return; // Callers rely on this
961+
ASTNODE_PREFETCH(m_nextp);
962+
963+
AstNode* nodep = this;
964+
do {
965+
970966
if (nodep->m_nextp) ASTNODE_PREFETCH(nodep->m_nextp->m_nextp);
971-
AstNode* niterp = nodep; // Pointer may get stomped via m_iterpp if the node is edited
972-
// Desirable check, but many places where multiple iterations are OK
973-
// UASSERT_OBJ(!niterp->m_iterpp, niterp, "IterateAndNext under iterateAndNext may miss
974-
// edits"); Optimization note: Doing PREFETCH_RW on m_iterpp is a net even
975-
// cppcheck-suppress nullPointer
976-
niterp->m_iterpp = &niterp;
977-
niterp->accept(v);
978-
// accept may do a replaceNode and change niterp on us...
979-
// niterp maybe nullptr, so need cast if printing
980-
// if (niterp != nodep) UINFO(1,"iterateAndNext edited "<<cvtToHex(nodep)
981-
// <<" now into "<<cvtToHex(niterp)<<endl);
982-
if (!niterp) return; // Perhaps node deleted inside accept
983-
niterp->m_iterpp = nullptr;
984-
if (VL_UNLIKELY(niterp != nodep)) { // Edited node inside accept
967+
968+
// This pointer may get changed via m_iterpp if the current node is edited
969+
AstNode* niterp = nodep;
970+
nodep->m_iterpp = &niterp;
971+
nodep->accept(v);
972+
973+
if (VL_UNLIKELY(niterp != nodep)) {
974+
// Node edited inside 'accept' (may have been deleted entirely)
985975
nodep = niterp;
986-
} else { // Unchanged node (though maybe updated m_next), just continue loop
987-
nodep = niterp->m_nextp;
976+
#ifdef VL_DEBUG
977+
UASSERT_OBJ(!nodep || (nodep->m_iterpp == &niterp), nodep,
978+
"New node already being iterated elsewhere");
979+
#endif
980+
} else {
981+
// Unchanged node (though maybe updated m_next), just continue loop
982+
nodep->m_iterpp = nullptr;
983+
nodep = nodep->m_nextp;
984+
#ifdef VL_DEBUG
985+
UASSERT_OBJ(!nodep || !nodep->m_iterpp, niterp, "Next node already being iterated");
986+
#endif
988987
}
989-
}
988+
} while (nodep);
990989
}
991990

992991
void AstNode::iterateListBackwardsConst(VNVisitorConst& v) {

‎src/V3Const.cpp

Lines changed: 19 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -887,7 +887,7 @@ class ConstVisitor final : public VNVisitor {
887887
// ** must track down everywhere V3Const is called and make sure no overlaps.
888888
// AstVar::user4p -> Used by variable marking/finding
889889
// AstJumpLabel::user4 -> bool. Set when AstJumpGo uses this label
890-
// AstEnum::user4 -> bool. Recursing.
890+
// AstEnumItem::user4 -> bool. Already checked for self references
891891

892892
// STATE
893893
static constexpr bool m_doShort = true; // Remove expressions that short circuit
@@ -2744,26 +2744,29 @@ class ConstVisitor final : public VNVisitor {
27442744
}
27452745
void visit(AstEnumItemRef* nodep) override {
27462746
iterateChildren(nodep);
2747-
UASSERT_OBJ(nodep->itemp(), nodep, "Not linked");
2748-
bool did = false;
2749-
if (nodep->itemp()->valuep()) {
2750-
// if (debug()) nodep->itemp()->valuep()->dumpTree("- visitvaref: ");
2751-
if (nodep->itemp()->user4()) {
2752-
nodep->v3error("Recursive enum value: " << nodep->itemp()->prettyNameQ());
2747+
AstEnumItem* const itemp = nodep->itemp();
2748+
UASSERT_OBJ(itemp, nodep, "Not linked");
2749+
if (!itemp->user4SetOnce() && itemp->valuep()) {
2750+
// Check for recursive self references (this should really not be here..)
2751+
const bool isRecursive = itemp->valuep()->exists([&](AstEnumItemRef* refp) { //
2752+
return refp->itemp() == itemp;
2753+
});
2754+
if (isRecursive) {
2755+
nodep->v3error("Recursive enum value: " << itemp->prettyNameQ());
27532756
} else {
2754-
nodep->itemp()->user4(true);
2755-
iterateAndNextNull(nodep->itemp()->valuep());
2756-
nodep->itemp()->user4(false);
2757-
}
2758-
if (AstConst* const valuep = VN_CAST(nodep->itemp()->valuep(), Const)) {
2759-
const V3Number& num = valuep->num();
2760-
VL_DO_DANGLING(replaceNum(nodep, num), nodep);
2761-
did = true;
2757+
// Simplify the value
2758+
iterate(itemp->valuep());
27622759
}
27632760
}
2761+
bool did = false;
2762+
if (AstConst* const valuep = VN_CAST(itemp->valuep(), Const)) {
2763+
const V3Number& num = valuep->num();
2764+
VL_DO_DANGLING(replaceNum(nodep, num), nodep);
2765+
did = true;
2766+
}
27642767
if (!did && m_required) {
27652768
nodep->v3error("Expecting expression to be constant, but enum value isn't const: "
2766-
<< nodep->itemp()->prettyNameQ());
2769+
<< itemp->prettyNameQ());
27672770
}
27682771
}
27692772

‎src/V3Premit.cpp

Lines changed: 19 additions & 18 deletions
< 10000 /tr>
Original file line numberDiff line numberDiff line change
@@ -93,22 +93,6 @@ class PremitVisitor final : public VNVisitor {
9393
}
9494
}
9595

96-
void insertBeforeStmt(AstNode* newp) {
97-
// Insert newp before m_stmtp
98-
if (m_inWhilep) {
99-
// Statements that are needed for the 'condition' in a while
100-
// actually have to be put before & after the loop, since we
101-
// can't do any statements in a while's (cond).
102-
m_inWhilep->addPrecondsp(newp);
103-
} else if (m_inTracep) {
104-
m_inTracep->addPrecondsp(newp);
105-
} else if (m_stmtp) {
106-
m_stmtp->addHereThisAsNext(newp);
107-
} else {
108-
newp->v3fatalSrc("No statement insertion point.");
109-
}
110-
}
111-
11296
void createDeepTemp(AstNodeExpr* nodep, bool noSubst) {
11397
if (nodep->user1SetOnce()) return; // Only add another assignment for this node
11498

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

118102
FileLine* const fl = nodep->fileline();
119103
AstVar* varp = nullptr;
104+
AstAssign* assignp = nullptr;
120105
AstConst* const constp = VN_CAST(nodep, Const);
121106
const bool useConstPool = constp // Is a constant
122107
&& (constp->width() >= STATIC_CONST_MIN_WIDTH) // Large enough
@@ -134,14 +119,29 @@ class PremitVisitor final : public VNVisitor {
134119
nodep->dtypep()};
135120
m_cfuncp->addInitsp(varp);
136121
// Put assignment before the referencing statement
137-
insertBeforeStmt(new AstAssign{fl, new AstVarRef{fl, varp, VAccess::WRITE}, nodep});
122+
assignp = new AstAssign{fl, new AstVarRef{fl, varp, VAccess::WRITE}, nodep};
123+
if (m_inWhilep) {
124+
// Statements that are needed for the 'condition' in a while
125+
// actually have to be put before & after the loop, since we
126+
// can't do any statements in a while's (cond).
127+
m_inWhilep->addPrecondsp(assignp);
128+
} else if (m_inTracep) {
129+
m_inTracep->addPrecondsp(assignp);
130+
} else if (m_stmtp) {
131+
m_stmtp->addHereThisAsNext(assignp);
132+
} else {
133+
assignp->v3fatalSrc("No statement insertion point.");
134+
}
138135
}
139136

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

143140
// Replace node with VarRef to new Var
144141
relinker.relink(new AstVarRef{fl, varp, VAccess::READ});
142+
143+
// Recursive expressions
144+
if (assignp) iterate(assignp);
145145
}
146146

147147
// VISITORS
@@ -357,7 +357,8 @@ class PremitVisitor final : public VNVisitor {
357357
iterateChildren(nodep);
358358
// Any strings sent to a display must be var of string data type,
359359
// to avoid passing a pointer to a temporary.
360-
for (AstNodeExpr* expp = nodep->exprsp(); expp; expp = VN_AS(expp->nextp(), NodeExpr)) {
360+
for (AstNodeExpr *expp = nodep->exprsp(), *nextp; expp; expp = nextp) {
361+
nextp = VN_AS(expp->nextp(), NodeExpr);
361362
if (expp->dtypep()->basicp() && expp->dtypep()->basicp()->isString()
362363
&& !VN_IS(expp, VarRef)) {
363364
createDeepTemp(expp, true);

‎src/V3Task.cpp

Lines changed: 7 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1391,7 +1391,10 @@ class TaskVisitor final : public VNVisitor {
13911391
if (debug() >= 9) nodep->dumpTree("- newstmt: ");
13921392
UASSERT_OBJ(m_insStmtp, nodep, "Function call not underneath a statement");
13931393
if (debug() >= 9) newp->dumpTree("- newfunc: ");
1394-
m_insStmtp->addHereThisAsNext(newp);
1394+
AstBegin* const tempp = new AstBegin{nodep->fileline(), "[EditWrapper]", newp};
1395+
iterateAndNextNull(newp);
1396+
m_insStmtp->addHereThisAsNext(tempp->stmtsp()->unlinkFrBackWithNext());
1397+
VL_DO_DANGLING(tempp->deleteTree(), tempp);
13951398
}
13961399

13971400
// VISITORS
@@ -1552,6 +1555,7 @@ class TaskVisitor final : public VNVisitor {
15521555
}
15531556
}
15541557
void visit(AstWhile* nodep) override {
1558+
VL_RESTORER(m_insStmtp);
15551559
// Special, as statements need to be put in different places
15561560
// Preconditions insert first just before themselves (the normal
15571561
// rule for other statement types)
@@ -1564,23 +1568,21 @@ class TaskVisitor final : public VNVisitor {
15641568
m_insStmtp = nullptr; // First thing should be new statement
15651569
iterateAndNextNull(nodep->stmtsp());
15661570
iterateAndNextNull(nodep->incsp());
1567-
// Done the loop
1568-
m_insStmtp = nullptr; // Next thing should be new statement
15691571
}
15701572
void visit(AstNodeFor* nodep) override { // LCOV_EXCL_LINE
15711573
nodep->v3fatalSrc(
15721574
"For statements should have been converted to while statements in V3Begin.cpp");
15731575
}
15741576
void visit(AstNodeStmt* nodep) override {
1577+
VL_RESTORER(m_insStmtp);
15751578
m_insStmtp = nodep;
15761579
iterateChildren(nodep);
1577-
m_insStmtp = nullptr; // Next thing should be new statement
15781580
}
15791581
void visit(AstStmtExpr* nodep) override {
1582+
VL_RESTORER(m_insStmtp);
15801583
m_insStmtp = nodep;
15811584
iterateChildren(nodep);
15821585
if (!nodep->exprp()) VL_DO_DANGLING(nodep->unlinkFrBack()->deleteTree(), nodep);
1583-
m_insStmtp = nullptr; // Next thing should be new statement
15841586
}
15851587
void visit(AstSenItem* nodep) override {
15861588
UASSERT_OBJ(!m_inSensesp, nodep, "Senitem under senitem?");

‎src/V3Width.cpp

Lines changed: 10 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -2094,16 +2094,20 @@ class WidthVisitor final : public VNVisitor {
20942094
// We can't skip this step when width()!=0, as creating a AstVar
20952095
// with non-constant range gets size 1, not size 0. So use didWidth().
20962096
if (nodep->didWidth()) return;
2097-
if (nodep->doingWidth()) { // Early exit if have circular parameter definition
2098-
UASSERT_OBJ(nodep->valuep(), nodep, "circular, but without value");
2097+
nodep->doingWidth(true);
2098+
2099+
// Check for recursive initialization
2100+
std::function<bool(AstNode*)> isRecursive = [&](AstNode* np) -> bool {
2101+
return np && np->exists([&](AstNodeVarRef* refp) {
2102+
return refp->varp() == nodep || isRecursive(refp->varp()->valuep());
2103+
});
2104+
};
2105+
if (isRecursive(nodep->valuep())) {
20992106
nodep->v3error("Variable's initial value is circular: " << nodep->prettyNameQ());
21002107
pushDeletep(nodep->valuep()->unlinkFrBack());
21012108
nodep->valuep(new AstConst{nodep->fileline(), AstConst::BitTrue{}});
2102-
nodep->dtypeFrom(nodep->valuep());
2103-
nodep->didWidth(true);
2104-
return;
21052109
}
2106-
nodep->doingWidth(true);
2110+
21072111
// Make sure dtype is sized
21082112
nodep->dtypep(iterateEditMoveDTypep(nodep, nodep->subDTypep()));
21092113
UASSERT_OBJ(nodep->dtypep(), nodep, "No dtype determined for var");

0 commit comments

Comments
 (0)
0