From a6f26b85b37583ddb43df2217f1774a5cdf90e8d Mon Sep 17 00:00:00 2001 From: Geza Lore Date: Tue, 2 Sep 2025 16:50:40 +0100 Subject: [PATCH] Internals: Improve DFG implementation details (#6355) Large scale refactoring to simplify some of the more obtuse internals of DFG. Remove multiple redundant internal APIs, simplify representation of variables, fix potential unsoundness in circular decomposition. No functional change intended. --- src/V3AstNodeOther.h | 2 +- src/V3Cfg.cpp | 1 + src/V3Cfg.h | 20 +- src/V3CfgBuilder.cpp | 2 +- src/V3Dfg.cpp | 432 +++------ src/V3Dfg.h | 890 ++++++------------ src/V3DfgAstToDfg.cpp | 19 +- src/V3DfgBreakCycles.cpp | 134 +-- src/V3DfgCache.h | 26 +- src/V3DfgColorSCCs.cpp | 7 +- src/V3DfgDecomposition.cpp | 210 +++-- src/V3DfgDfgToAst.cpp | 153 ++- src/V3DfgOptimizer.cpp | 2 +- src/V3DfgPasses.cpp | 30 +- src/V3DfgPatternStats.h | 3 +- src/V3DfgPeephole.cpp | 86 +- src/V3DfgRegularize.cpp | 2 +- src/V3DfgSynthesize.cpp | 525 ++++++----- src/V3DfgVertices.h | 572 ++++++----- src/astgen | 54 +- src/cppcheck-suppressions.txt | 4 +- test_regress/t/t_dfg_synthesis_pre_inline.cpp | 60 ++ test_regress/t/t_dfg_synthesis_pre_inline.py | 100 ++ test_regress/t/t_dfg_synthesis_pre_inline.v | 34 + 24 files changed, 1699 insertions(+), 1669 deletions(-) create mode 100644 test_regress/t/t_dfg_synthesis_pre_inline.cpp create mode 100755 test_regress/t/t_dfg_synthesis_pre_inline.py create mode 100644 test_regress/t/t_dfg_synthesis_pre_inline.v diff --git a/src/V3AstNodeOther.h b/src/V3AstNodeOther.h index 895bc6063fb..d2681c57e89 100644 --- a/src/V3AstNodeOther.h +++ b/src/V3AstNodeOther.h @@ -2617,7 +2617,7 @@ class AstAlways final : public AstNodeProcedure { const VAlwaysKwd m_keyword; public: - AstAlways(FileLine* fl, VAlwaysKwd keyword, AstSenTree* sentreep, AstNode* stmtsp) + AstAlways(FileLine* fl, VAlwaysKwd keyword, AstSenTree* sentreep, AstNode* stmtsp = nullptr) : ASTGEN_SUPER_Always(fl, stmtsp) , m_keyword{keyword} { this->sentreep(sentreep); diff --git a/src/V3Cfg.cpp b/src/V3Cfg.cpp index e671cfd59f5..34a870a602a 100644 --- a/src/V3Cfg.cpp +++ b/src/V3Cfg.cpp @@ -115,6 +115,7 @@ void CfgGraph::rpoBlocks() { // Assign edge IDs size_t edgeCount = 0; for (V3GraphVertex& v : vertices()) { + // cppcheck-suppress constVariableReference // cppcheck is wrong for (V3GraphEdge& e : v.outEdges()) static_cast(e).m_id = edgeCount++; } UASSERT_OBJ(edgeCount == m_nEdges, m_enterp, "Inconsistent edge count"); diff --git a/src/V3Cfg.h b/src/V3Cfg.h index 51c4266591c..ef3e2a8709b 100644 --- a/src/V3Cfg.h +++ b/src/V3Cfg.h @@ -92,15 +92,12 @@ class CfgBlock final : public V3GraphVertex { // STATE CfgGraph* const m_cfgp; // The control flow graph this CfgBlock is under - size_t m_rpoNumber; // Reverse post-order number and unique ID of this CfgBlock + size_t m_rpoNumber = 0; // Reverse post-order number and unique ID of this CfgBlock // V3GraphEdge::user() is set to the unique id by CfgBuilder std::vector m_stmtps; // statements in this CfgBlock // PRIVATE METHODS - // ID (reverse post-order numpber) of this block - inline size_t id(); - inline size_t id() const; // CONSTRUCTOR/DESTRUCTOR - via CfgGraph only inline explicit CfgBlock(CfgGraph* cfgp); @@ -109,6 +106,10 @@ class CfgBlock final : public V3GraphVertex { public: // PUBLIC METHODS + // ID (reverse post-order number) of this block + inline size_t id(); + inline size_t id() const; + // Is this the entry block of the CFG? bool isEnter() const { return inEmpty(); } // Is this the exit block of the CFG? @@ -185,19 +186,20 @@ class CfgEdge final : public V3GraphEdge { // STATE - Immutable after construction, set by CfgBuilder CfgGraph* const m_cfgp; // The control flow graph this CfgEdge is under - size_t m_id; // Unique ID of this vertex + size_t m_id = 0; // Unique ID of this vertex // PRIVATE METHODS - // Unique ID of this CfgEdge - no particular meaning - inline size_t id(); - inline size_t id() const; // CONSTRUCTOR/DESTRUCTOR - via CfgGraph only inline CfgEdge(CfgGraph* graphp, CfgBlock* srcp, CfgBlock* dstp); ~CfgEdge() override = default; public: - // METHODS - all const + // METHODS + + // Unique ID of this CfgEdge - no particular meaning + inline size_t id(); + inline size_t id() const; // Source/destination CfgBlock const CfgBlock* srcp() const { return static_cast(fromp()); } diff --git a/src/V3CfgBuilder.cpp b/src/V3CfgBuilder.cpp index 407c0aba347..1d5379d81d8 100644 --- a/src/V3CfgBuilder.cpp +++ b/src/V3CfgBuilder.cpp @@ -205,7 +205,7 @@ class CfgBuilder final : public VNVisitorConst { while (!unreachableps.empty()) { V3GraphVertex* const vtxp = unreachableps.back(); unreachableps.pop_back(); - for (V3GraphEdge& edge : vtxp->outEdges()) { + for (const V3GraphEdge& edge : vtxp->outEdges()) { --m_cfgp->m_nEdges; if (edge.top()->inSize1()) unreachableps.emplace_back(edge.top()); } diff --git a/src/V3Dfg.cpp b/src/V3Dfg.cpp index b36b27a657b..4d2a8e3429d 100644 --- a/src/V3Dfg.cpp +++ b/src/V3Dfg.cpp @@ -24,15 +24,42 @@ VL_DEFINE_DEBUG_FUNCTIONS; //------------------------------------------------------------------------------ -// DfgGraph +// V3Dfg + +// predicate for supported data types +static bool dfgGraphIsSupportedDTypePacked(const AstNodeDType* dtypep) { + dtypep = dtypep->skipRefp(); + if (const AstBasicDType* const typep = VN_CAST(dtypep, BasicDType)) { + return typep->keyword().isIntNumeric(); + } + if (const AstPackArrayDType* const typep = VN_CAST(dtypep, PackArrayDType)) { + return dfgGraphIsSupportedDTypePacked(typep->subDTypep()); + } + if (const AstNodeUOrStructDType* const typep = VN_CAST(dtypep, NodeUOrStructDType)) { + return typep->packed(); + } + return false; +} + +bool V3Dfg::isSupported(const AstNodeDType* dtypep) { + dtypep = dtypep->skipRefp(); + // Support 1 dimensional unpacked arrays of packed types + if (const AstUnpackArrayDType* const typep = VN_CAST(dtypep, UnpackArrayDType)) { + return dfgGraphIsSupportedDTypePacked(typep->subDTypep()); + } + // Support packed types + return dfgGraphIsSupportedDTypePacked(dtypep); +} + //------------------------------------------------------------------------------ +// DfgGraph DfgGraph::DfgGraph(AstModule* modulep, const string& name) : m_modulep{modulep} , m_name{name} {} DfgGraph::~DfgGraph() { - forEachVertex([](DfgVertex& vtxp) { delete &vtxp; }); + forEachVertex([&](DfgVertex& vtx) { vtx.unlinkDelete(*this); }); } std::unique_ptr DfgGraph::clone() const { @@ -133,40 +160,21 @@ std::unique_ptr DfgGraph::clone() const { // Constants have no inputs // Hook up inputs of cloned variables for (const DfgVertexVar& vtx : m_varVertices) { - // All variable vertices are unary - if (const DfgVertex* const srcp = vtx.srcp()) { - vtxp2clonep.at(&vtx)->as()->srcp(vtxp2clonep.at(srcp)); - } + DfgVertexVar* const cp = vtxp2clonep.at(&vtx)->as(); + if (const DfgVertex* const srcp = vtx.srcp()) cp->srcp(vtxp2clonep.at(srcp)); + if (const DfgVertex* const defp = vtx.defaultp()) cp->defaultp(vtxp2clonep.at(defp)); } // Hook up inputs of cloned operation vertices for (const DfgVertex& vtx : m_opVertices) { if (vtx.is()) { switch (vtx.type()) { - case VDfgType::atSpliceArray: { - const DfgSpliceArray* const vp = vtx.as(); - DfgSpliceArray* const cp = vtxp2clonep.at(vp)->as(); - vp->forEachSourceEdge([&](const DfgEdge& edge, size_t i) { - if (const DfgVertex* const srcp = edge.sourcep()) { - cp->addDriver(vp->driverFileLine(i), // - vp->driverLo(i), // - vtxp2clonep.at(srcp)); - } - }); - break; - } + case VDfgType::atSpliceArray: case VDfgType::atSplicePacked: { - const DfgSplicePacked* const vp = vtx.as(); - DfgSplicePacked* const cp = vtxp2clonep.at(vp)->as(); - vp->forEachSourceEdge([&](const DfgEdge& edge, size_t i) { - if (const DfgVertex* const srcVp = edge.sourcep()) { - DfgVertex* const srcCp = vtxp2clonep.at(srcVp); - UASSERT_OBJ(!srcCp->is(), srcCp, "Cannot clone DfgLogic"); - if (srcVp == vp->defaultp()) { - cp->defaultp(srcCp); - } else { - cp->addDriver(vp->driverFileLine(i), vp->driverLo(i), srcCp); - } - } + const DfgVertexSplice* const vp = vtx.as(); + DfgVertexSplice* const cp = vtxp2clonep.at(vp)->as(); + vp->foreachDriver([&](const DfgVertex& src, uint32_t lo, FileLine* flp) { + cp->addDriver(vtxp2clonep.at(&src), lo, flp); + return false; }); break; } @@ -178,14 +186,8 @@ std::unique_ptr DfgGraph::clone() const { } } else { DfgVertex* const cp = vtxp2clonep.at(&vtx); - const auto oSourceEdges = vtx.sourceEdges(); - auto cSourceEdges = cp->sourceEdges(); - UASSERT_OBJ(oSourceEdges.second == cSourceEdges.second, &vtx, - "Mismatched source count"); - for (size_t i = 0; i < oSourceEdges.second; ++i) { - if (const DfgVertex* const srcp = oSourceEdges.first[i].sourcep()) { - cSourceEdges.first[i].relinkSource(vtxp2clonep.at(srcp)); - } + for (size_t i = 0; i < vtx.nInputs(); ++i) { + cp->inputp(i, vtxp2clonep.at(vtx.inputp(i))); } } } @@ -210,9 +212,12 @@ void DfgGraph::mergeGraphs(std::vector>&& otherps) { // Variabels that are present in 'this', make them use the DfgVertexVar in 'this'. if (DfgVertexVar* const altp = vtxp->nodep()->user2u().to()) { DfgVertex* const srcp = vtxp->srcp(); - UASSERT_OBJ(!srcp || !altp->srcp(), vtxp, "At most one alias should be driven"); + DfgVertex* const defaultp = vtxp->defaultp(); + UASSERT_OBJ(!(srcp || defaultp) || (!altp->srcp() && !altp->defaultp()), vtxp, + "At most one alias should be driven"); vtxp->replaceWith(altp); if (srcp) altp->srcp(srcp); + if (defaultp) altp->defaultp(defaultp); VL_DO_DANGLING(vtxp->unlinkDelete(*otherp), vtxp); continue; } @@ -285,68 +290,53 @@ static const std::string toDotId(const DfgVertex& vtx) { return '"' + cvtToHex(& // Dump one DfgVertex in Graphviz format static void dumpDotVertex(std::ostream& os, const DfgVertex& vtx) { - - if (const DfgVarPacked* const varVtxp = vtx.cast()) { + if (const DfgVertexVar* const varVtxp = vtx.cast()) { const AstNode* const nodep = varVtxp->nodep(); const AstVar* const varp = varVtxp->varp(); os << toDotId(vtx); - os << " [label=\"" << nodep->prettyName() << '\n'; - os << cvtToHex(varVtxp) << '\n'; + // Begin attributes + os << " ["; + // Begin 'label' + os << "label=\""; + // Name + os << nodep->prettyName(); + // Address + os << '\n' << cvtToHex(varVtxp); + // Original variable, if any if (const AstNode* const tmpForp = varVtxp->tmpForp()) { - os << "temporary for: " << tmpForp->prettyName() << "\n"; + if (tmpForp != nodep) os << "\ntemporary for: " << tmpForp->prettyName(); } + // Type and fanout + os << '\n'; varVtxp->dtypep()->dumpSmall(os); - os << " / F" << varVtxp->fanout() << '"'; - + os << " / F" << varVtxp->fanout(); + // End 'label' + os << '"'; + // Shape + if (varVtxp->is()) { + os << ", shape=box"; + } else if (varVtxp->is()) { + os << ", shape=box3d"; + } else { + varVtxp->v3fatalSrc("Unhandled DfgVertexVar sub-type"); // LCOV_EXCL_LINE + } + // Color if (varp->direction() == VDirection::INPUT) { - os << ", shape=box, style=filled, fillcolor=chartreuse2"; // Green + os << ", style=filled, fillcolor=chartreuse2"; // Green } else if (varp->direction() == VDirection::OUTPUT) { - os << ", shape=box, style=filled, fillcolor=cyan2"; // Cyan + os << ", style=filled, fillcolor=cyan2"; // Cyan } else if (varp->direction() == VDirection::INOUT) { - os << ", shape=box, style=filled, fillcolor=darkorchid2"; // Purple + os << ", style=filled, fillcolor=darkorchid2"; // Purple } else if (varVtxp->hasExtRefs()) { - os << ", shape=box, style=filled, fillcolor=firebrick2"; // Red + os << ", style=filled, fillcolor=firebrick2"; // Red } else if (varVtxp->hasModRefs()) { - os << ", shape=box, style=filled, fillcolor=darkorange1"; // Orange + os << ", style=filled, fillcolor=darkorange1"; // Orange } else if (varVtxp->hasDfgRefs()) { - os << ", shape=box, style=filled, fillcolor=gold2"; // Yellow + os << ", style=filled, fillcolor=gold2"; // Yellow } else if (varVtxp->tmpForp()) { - os << ", shape=box, style=filled, fillcolor=gray80"; - } else { - os << ", shape=box"; - } - os << "]\n"; - return; - } - - if (const DfgVarArray* const arrVtxp = vtx.cast()) { - const AstNode* const nodep = arrVtxp->nodep(); - const AstVar* const varp = arrVtxp->varp(); - os << toDotId(vtx); - os << " [label=\"" << nodep->prettyName() << '\n'; - os << cvtToHex(arrVtxp) << '\n'; - if (const AstNode* const tmpForp = arrVtxp->tmpForp()) { - os << "temporary for: " << tmpForp->prettyName() << "\n"; - } - arrVtxp->dtypep()->dumpSmall(os); - os << " / F" << arrVtxp->fanout() << '"'; - if (varp->direction() == VDirection::INPUT) { - os << ", shape=box3d, style=filled, fillcolor=chartreuse2"; // Green - } else if (varp->direction() == VDirection::OUTPUT) { - os << ", shape=box3d, style=filled, fillcolor=cyan2"; // Cyan - } else if (varp->direction() == VDirection::INOUT) { - os << ", shape=box3d, style=filled, fillcolor=darkorchid2"; // Purple - } else if (arrVtxp->hasExtRefs()) { - os << ", shape=box3d, style=filled, fillcolor=firebrick2"; // Red - } else if (arrVtxp->hasModRefs()) { - os << ", shape=box3d, style=filled, fillcolor=darkorange1"; // Orange - } else if (arrVtxp->hasDfgRefs()) { - os << ", shape=box3d, style=filled, fillcolor=gold2"; // Yellow - } else if (arrVtxp->tmpForp()) { - os << ", shape=box3d, style=filled, fillcolor=gray80"; - } else { - os << ", shape=box3d"; + os << ", style=filled, fillcolor=gray95"; } + // End attributes os << "]\n"; return; } @@ -405,8 +395,12 @@ static void dumpDotVertex(std::ostream& os, const DfgVertex& vtx) { os << toDotId(vtx); std::stringstream ss; V3EmitV::debugVerilogForTree(logicp->nodep(), ss); + std::string str = ss.str(); + str = VString::quoteBackslash(str); + str = VString::quoteAny(str, '"', '\\'); + str = VString::replaceSubstr(str, "\n", "\\l"); os << " [label=\""; - os << VString::replaceSubstr(VString::replaceSubstr(ss.str(), "\n", "\\l"), "\"", "\\\""); + os << str; os << "\\n" << cvtToHex(&vtx); os << "\"\n"; os << ", shape=box, style=\"rounded,filled\", fillcolor=cornsilk, nojustify=true"; @@ -427,17 +421,6 @@ static void dumpDotVertex(std::ostream& os, const DfgVertex& vtx) { os << "]\n"; } -// Dump one DfgEdge in Graphviz format -static void dumpDotEdge(std::ostream& os, const DfgEdge& edge, size_t idx) { - UASSERT(edge.sourcep(), "Can't dump unconnected DfgEdge"); - const DfgVertex& sink = *edge.sinkp(); // sink is never nullptr - os << toDotId(*edge.sourcep()) << " -> " << toDotId(sink); - if (sink.arity() > 1 || sink.is()) { - os << " [headlabel=\"" << sink.srcName(idx) << "\"]"; - } - os << '\n'; -} - void DfgGraph::dumpDot(std::ostream& os, const std::string& label, std::function p) const { // This generates a graphviz dump, https://www.graphviz.org @@ -473,12 +456,16 @@ void DfgGraph::dumpDot(std::ostream& os, const std::string& label, dumpDotVertex(os, vtx); }); // Emit all edges - forEachVertex([&](const DfgVertex& vtx) { // + forEachVertex([&](const DfgVertex& vtx) { if (!p(vtx)) return; - vtx.forEachSourceEdge([&](const DfgEdge& e, size_t i) { // - if (!e.sourcep() || !p(*e.sourcep())) return; - dumpDotEdge(os, e, i); - }); + for (size_t i = 0; i < vtx.nInputs(); ++i) { + DfgVertex* const srcp = vtx.inputp(i); + if (!srcp) continue; + if (!p(*srcp)) continue; + os << toDotId(*srcp) << " -> " << toDotId(vtx); + os << " [headlabel=\"" << vtx.srcName(i) << "\"]"; + os << '\n'; + } }); // Footer @@ -527,9 +514,15 @@ dfgGraphCollectCone(const std::vector& vtxps) { if (!resp->insert(vtxp).second) continue; // Enqueue all siblings of this vertex. if VL_CONSTEXPR_CXX17 (T_SinksNotSources) { - vtxp->forEachSink([&](const DfgVertex& sink) { queue.push_back(&sink); }); + vtxp->foreachSink([&](const DfgVertex& sink) { + queue.push_back(&sink); + return false; + }); } else { - vtxp->forEachSource([&](const DfgVertex& src) { queue.push_back(&src); }); + vtxp->foreachSource([&](const DfgVertex& src) { + queue.push_back(&src); + return false; + }); } } // Done @@ -546,73 +539,8 @@ DfgGraph::sinkCone(const std::vector& vtxps) const { return dfgGraphCollectCone(vtxps); } -// predicate for supported data types -static bool dfgGraphIsSupportedDTypePacked(const AstNodeDType* dtypep) { - dtypep = dtypep->skipRefp(); - if (const AstBasicDType* const typep = VN_CAST(dtypep, BasicDType)) { - return typep->keyword().isIntNumeric(); - } - if (const AstPackArrayDType* const typep = VN_CAST(dtypep, PackArrayDType)) { - return dfgGraphIsSupportedDTypePacked(typep->subDTypep()); - } - if (const AstNodeUOrStructDType* const typep = VN_CAST(dtypep, NodeUOrStructDType)) { - return typep->packed(); - } - return false; -} - -bool DfgGraph::isSupported(const AstNodeDType* dtypep) { - dtypep = dtypep->skipRefp(); - // Support 1 dimensional unpacked arrays of packed types - if (const AstUnpackArrayDType* const typep = VN_CAST(dtypep, UnpackArrayDType)) { - return dfgGraphIsSupportedDTypePacked(typep->subDTypep()); - } - // Support packed types - return dfgGraphIsSupportedDTypePacked(dtypep); -} - -//------------------------------------------------------------------------------ -// DfgEdge -//------------------------------------------------------------------------------ - -void DfgEdge::unlinkSource() { - if (!m_sourcep) return; -#ifdef VL_DEBUG - { - DfgEdge* currp = m_sourcep->m_sinksp; - while (currp) { - if (currp == this) break; - currp = currp->m_nextp; - } - UASSERT(currp, "'m_sourcep' does not have this edge as sink"); - } -#endif - // Relink pointers of predecessor and successor - if (m_prevp) m_prevp->m_nextp = m_nextp; - if (m_nextp) m_nextp->m_prevp = m_prevp; - // If head of list in source, update source's head pointer - if (m_sourcep->m_sinksp == this) m_sourcep->m_sinksp = m_nextp; - // Mark source as unconnected - m_sourcep = nullptr; - // Clear links. This is not strictly necessary, but might catch bugs. - m_prevp = nullptr; - m_nextp = nullptr; -} - -void DfgEdge::relinkSource(DfgVertex* newSourcep) { - // Unlink current source, if any - unlinkSource(); - // Link new source - m_sourcep = newSourcep; - // Prepend to sink list in source - m_nextp = newSourcep->m_sinksp; - if (m_nextp) m_nextp->m_prevp = this; - newSourcep->m_sinksp = this; -} - //------------------------------------------------------------------------------ // DfgVertex -//------------------------------------------------------------------------------ DfgVertex::DfgVertex(DfgGraph& dfg, VDfgType type, FileLine* flp, AstNodeDType* dtypep) : m_filelinep{flp} @@ -621,12 +549,6 @@ DfgVertex::DfgVertex(DfgGraph& dfg, VDfgType type, FileLine* flp, AstNodeDType* dfg.addVertex(*this); } -DfgVertex::~DfgVertex() {} - -bool DfgVertex::selfEquals(const DfgVertex& that) const { return true; } - -V3Hash DfgVertex::selfHash() const { return V3Hash{}; } - bool DfgVertex::equals(const DfgVertex& that, EqualsCache& cache) const { // If same vertex, then equal if (this == &that) return true; @@ -638,13 +560,7 @@ bool DfgVertex::equals(const DfgVertex& that, EqualsCache& cache) const { if (this->dtypep() != that.dtypep()) return false; // If different number of inputs, then not equal - auto thisPair = this->sourceEdges(); - const DfgEdge* const thisSrcEdgesp = thisPair.first; - const size_t thisArity = thisPair.second; - auto thatPair = that.sourceEdges(); - const DfgEdge* const thatSrcEdgesp = thatPair.first; - const size_t thatArity = thatPair.second; - if (thisArity != thatArity) return false; + if (this->nInputs() != that.nInputs()) return false; // Check vertex specifics if (!this->selfEquals(that)) return false; @@ -655,16 +571,17 @@ bool DfgVertex::equals(const DfgVertex& that, EqualsCache& cache) const { // Note: the recursive invocation can cause a re-hash but that will not invalidate references uint8_t& result = cache[key]; if (!result) { - result = 2; // Assume equals - for (size_t i = 0; i < thisArity; ++i) { - const DfgVertex* const thisSrcVtxp = thisSrcEdgesp[i].m_sourcep; - const DfgVertex* const thatSrcVtxp = thatSrcEdgesp[i].m_sourcep; - if (thisSrcVtxp == thatSrcVtxp) continue; - if (!thisSrcVtxp || !thatSrcVtxp || !thisSrcVtxp->equals(*thatSrcVtxp, cache)) { - result = 1; // Mark not equal - break; + const bool equal = [&]() { + for (size_t i = 0; i < nInputs(); ++i) { + const DfgVertex* const ap = this->inputp(i); + const DfgVertex* const bp = that.inputp(i); + if (!ap && !bp) continue; + if (!ap || !bp) return false; + if (!ap->equals(*bp, cache)) return false; } - } + return true; + }(); + result = (static_cast(equal) << 1) | 1; } return result >> 1; } @@ -678,17 +595,11 @@ V3Hash DfgVertex::hash() { // variables, which we rely on. if (!is()) { hash += m_type; - if (const AstUnpackArrayDType* const adtypep = VN_CAST(dtypep(), UnpackArrayDType)) { - hash += adtypep->elementsConst(); - // TODO: maybe include sub-dtype, but not hugely important at the moment - } else { - hash += width(); - } - const auto pair = sourceEdges(); - const DfgEdge* const edgesp = pair.first; - const size_t nEdges = pair.second; - // Sources must always be connected in well-formed graphs - for (size_t i = 0; i < nEdges; ++i) hash += edgesp[i].m_sourcep->hash(); + hash += size(); + foreachSource([&](DfgVertex& vtx) { + hash += vtx.hash(); + return false; + }); } result = hash; } @@ -697,7 +608,10 @@ V3Hash DfgVertex::hash() { uint32_t DfgVertex::fanout() const { uint32_t result = 0; - forEachSinkEdge([&](const DfgEdge&) { ++result; }); + foreachSink([&](const DfgVertex&) { + ++result; + return false; + }); return result; } @@ -708,51 +622,52 @@ DfgVertexVar* DfgVertex::getResultVar() { // Inspect existing variables written by this vertex, and choose one DfgVertexVar* resp = nullptr; // cppcheck-has-bug-suppress constParameter - this->forEachSink([&resp](DfgVertex& sink) { + this->foreachSink([&resp](DfgVertex& sink) { DfgVertexVar* const varp = sink.cast(); - if (!varp) return; + if (!varp) return false; // First variable found if (!resp) { resp = varp; - return; + return false; } // Prefer those variables that must be kept anyway if (resp->hasExtRefs() != varp->hasExtRefs()) { if (!resp->hasExtRefs()) resp = varp; - return; + return false; } if (resp->hasModWrRefs() != varp->hasModWrRefs()) { if (!resp->hasModWrRefs()) resp = varp; - return; + return false; } if (resp->hasDfgRefs() != varp->hasDfgRefs()) { if (!resp->hasDfgRefs()) resp = varp; - return; + return false; } // Prefer those that already have module references if (resp->hasModRdRefs() != varp->hasModRdRefs()) { if (!resp->hasModRdRefs()) resp = varp; - return; + return false; } // Prefer real variabels over temporaries if (!resp->tmpForp() != !varp->tmpForp()) { if (resp->tmpForp()) resp = varp; - return; + return false; } // Prefer the earlier one in source order const FileLine& oldFlp = *(resp->fileline()); const FileLine& newFlp = *(varp->fileline()); if (const int cmp = oldFlp.operatorCompare(newFlp)) { if (cmp > 0) resp = varp; - return; + return false; } // Prefer the one with the lexically smaller name if (const int cmp = resp->nodep()->name().compare(varp->nodep()->name())) { if (cmp > 0) resp = varp; - return; + return false; } // 'resp' and 'varp' are all the same, keep using the existing 'resp' + return false; }); return resp; } @@ -777,14 +692,16 @@ AstScope* DfgVertex::scopep(ScopeCache& cache, bool tryResultVar) VL_MT_DISABLED resultr = reinterpret_cast(1); // Find scope based on sources, falling back on the root scope AstScope* const rootp = v3Global.rootp()->topScopep()->scopep(); - AstScope* foundp = rootp; - const auto edges = sourceEdges(); - for (size_t i = 0; i < edges.second; ++i) { - const DfgEdge& edge = edges.first[i]; - foundp = edge.sourcep()->scopep(cache, true); - if (foundp != rootp) break; - } - resultr = foundp; + AstScope* foundp = nullptr; + foreachSource([&](DfgVertex& src) { + AstScope* const scp = src.scopep(cache, true); + if (scp != rootp) { + foundp = scp; + return true; + } + return false; + }); + resultr = foundp ? foundp : rootp; } // Die on a graph circular through operation vertices @@ -796,80 +713,15 @@ AstScope* DfgVertex::scopep(ScopeCache& cache, bool tryResultVar) VL_MT_DISABLED } void DfgVertex::unlinkDelete(DfgGraph& dfg) { - // Unlink source edges - forEachSourceEdge([](DfgEdge& edge, size_t) { edge.unlinkSource(); }); // Unlink sink edges - forEachSinkEdge([](DfgEdge& edge) { edge.unlinkSource(); }); + while (!m_sinks.empty()) m_sinks.frontp()->unlinkSrcp(); // Remove from graph dfg.removeVertex(*this); - // Delete + // Delete - this will unlink sources delete this; } -void DfgVertex::replaceWith(DfgVertex* newSorucep) { - while (m_sinksp) m_sinksp->relinkSource(newSorucep); -} - -//------------------------------------------------------------------------------ -// Vertex classes -//------------------------------------------------------------------------------ - -// DfgConst ---------- - -bool DfgConst::selfEquals(const DfgVertex& that) const { - return num().isCaseEq(that.as()->num()); -} - -V3Hash DfgConst::selfHash() const { return num().toHash(); } - -// DfgSel ---------- - -bool DfgSel::selfEquals(const DfgVertex& that) const { return lsb() == that.as()->lsb(); } - -V3Hash DfgSel::selfHash() const { return V3Hash{lsb()}; } - -// DfgVertexSplice ---------- - -bool DfgVertexSplice::selfEquals(const DfgVertex& that) const { - const DfgVertexSplice* const thatp = that.as(); - if (!defaultp() != !thatp->defaultp()) return false; - const size_t arity = this->arity(); - for (size_t i = 0; i < arity; ++i) { - if (i == 0 && defaultp()) continue; - if (driverLo(i) != thatp->driverLo(i)) return false; - } - return true; -} - -V3Hash DfgVertexSplice::selfHash() const { - V3Hash hash; - const size_t arity = this->arity(); - for (size_t i = 0; i < arity; ++i) { - if (i == 0 && defaultp()) continue; - hash += driverLo(i); - } - return hash; -} - -// DfgVertexVar ---------- - -bool DfgVertexVar::selfEquals(const DfgVertex& that) const { - UASSERT_OBJ(nodep()->type() == that.as()->nodep()->type(), this, - "Both DfgVertexVar should be scoped or unscoped"); - UASSERT_OBJ(nodep() != that.as()->nodep(), this, - "There should only be one DfgVertexVar for a given AstVar or AstVarScope"); - return false; -} - -V3Hash DfgVertexVar::selfHash() const { - V3Hash hash; - hash += nodep()->name(); - hash += varp()->varType(); - return hash; -} - //------------------------------------------------------------------------------ // DfgVisitor -//------------------------------------------------------------------------------ #include "V3Dfg__gen_visitor_defns.h" // From ./astgen diff --git a/src/V3Dfg.h b/src/V3Dfg.h index c76cc8bf2a3..bab4a0498f9 100644 --- a/src/V3Dfg.h +++ b/src/V3Dfg.h @@ -59,8 +59,6 @@ class DfgVertex; class DfgGraph; class DfgVisitor; -//------------------------------------------------------------------------------ - // Specialization of std::hash for a std::pair for use below template <> struct std::hash> final { @@ -72,9 +70,74 @@ struct std::hash> final { } }; +namespace V3Dfg { +//----------------------------------------------------------------------- +// Functions for compatibility tests + +// Returns true if the given data type can be represented in the graph +bool isSupported(const AstNodeDType* dtypep) VL_MT_DISABLED; + +// Returns true if variable can be represented in the graph +inline bool isSupported(const AstVar* varp) { + if (varp->isIfaceRef()) return false; // Cannot handle interface references + if (varp->delayp()) return false; // Cannot handle delayed variables + if (varp->isSc()) return false; // SystemC variables are special and rare, we can ignore + if (varp->dfgMultidriven()) return false; // Discovered as multidriven on earlier DFG run + return isSupported(varp->dtypep()); +} + +// Returns true if variable can be represented in the graph +inline bool isSupported(const AstVarScope* vscp) { + const AstNodeModule* const modp = vscp->scopep()->modp(); + if (VN_IS(modp, Module)) { + // Regular module supported + } else if (const AstIface* const ifacep = VN_CAST(modp, Iface)) { + // Interfaces supported if there are no virtual interfaces for + // them, otherwise they cannot be resovled statically. + if (ifacep->hasVirtualRef()) return false; + } else { + return false; // Anything else (package, class, etc) not supported + } + // Check the AstVar + return isSupported(vscp->varp()); +} + +//----------------------------------------------------------------------- +// Functions for data types + +// Some data types are interned, in order to facilitate type comparison +// via pointer compariosn. These are functoins to construct the canonical +// DFG data types + +// Returns data type used to represent any packed value of the given 'width'. +inline AstNodeDType* dtypePacked(uint32_t width) { + return v3Global.rootp()->typeTablep()->findLogicDType(width, width, VSigning::UNSIGNED); +} + +// Returns data type used to represent any array with the given type and number of elements. +inline AstNodeDType* dtypeArray(AstNodeDType* subDtypep, uint32_t size) { + UASSERT_OBJ(isSupported(subDtypep), subDtypep, "Unsupported element type"); + FileLine* const flp = subDtypep->fileline(); + AstRange* const rangep = new AstRange{flp, static_cast(size - 1), 0}; + AstNodeDType* const dtypep = new AstUnpackArrayDType{flp, subDtypep, rangep}; + v3Global.rootp()->typeTablep()->addTypesp(dtypep); + return dtypep; +} + +// Return data type used to represent the type of 'nodep' when converted to a DfgVertex +inline AstNodeDType* toDfgDType(const AstNodeDType* dtypep) { + dtypep = dtypep->skipRefp(); + UASSERT_OBJ(isSupported(dtypep), dtypep, "Unsupported dtype"); + // For simplicity, all packed types are represented with a fixed type + if (const AstUnpackArrayDType* const uatp = VN_CAST(dtypep, UnpackArrayDType)) { + return dtypeArray(toDfgDType(uatp->subDTypep()), uatp->elementsConst()); + } + return dtypePacked(dtypep->width()); +} +} //namespace V3Dfg + //------------------------------------------------------------------------------ -// Dataflow vertex type enum -//------------------------------------------------------------------------------ +// Dataflow graph vertex type enum class VDfgType final { public: @@ -93,37 +156,37 @@ inline std::ostream& operator<<(std::ostream& os, const VDfgType& t) { return os //------------------------------------------------------------------------------ // Dataflow graph edge -//------------------------------------------------------------------------------ - class DfgEdge final { friend class DfgVertex; - DfgEdge* m_nextp = nullptr; // Next edge in sink list - DfgEdge* m_prevp = nullptr; // Previous edge in sink list - DfgVertex* m_sourcep = nullptr; // The source vertex driving this edge - // Note that the sink vertex owns the edge, so it is immutable, but because we want to be able - // to allocate these as arrays, we use a default constructor + 'init' method to set m_sinkp. - DfgVertex* const m_sinkp = nullptr; // The sink vertex + DfgVertex* m_srcp = nullptr; // The source vertex driving this edge - might be unconnected + DfgVertex* const m_dstp; // The vertex driven by this edge, which owns this edge, so immutable + V3ListLinks m_links; // V3List links in the list of sinks of m_srcp + + DfgEdge() = delete; + VL_UNCOPYABLE(DfgEdge); + VL_UNMOVABLE(DfgEdge); + + V3ListLinks& links() { return m_links; } + using List = V3List; public: - DfgEdge() {} - void init(DfgVertex* sinkp) { const_cast(m_sinkp) = sinkp; } + explicit DfgEdge(DfgVertex* dstp) + : m_dstp{dstp} {} + ~DfgEdge() { unlinkSrcp(); } // The source (driver) of this edge - DfgVertex* sourcep() const { return m_sourcep; } + DfgVertex* srcp() const { return m_srcp; } // The sink (consumer) of this edge - DfgVertex* sinkp() const { return m_sinkp; } + DfgVertex* dstp() const { return m_dstp; } // Remove driver of this edge - void unlinkSource() VL_MT_DISABLED; + inline void unlinkSrcp(); // Relink this edge to be driven from the given new source vertex - void relinkSource(DfgVertex* newSourcep) VL_MT_DISABLED; + inline void relinkSrcp(DfgVertex* srcp); }; //------------------------------------------------------------------------------ // Dataflow graph vertex -//------------------------------------------------------------------------------ - -// Base data flow graph vertex class DfgVertex VL_NOT_FINAL { friend class DfgGraph; friend class DfgEdge; @@ -132,10 +195,10 @@ class DfgVertex VL_NOT_FINAL { using UserDataStorage = void*; // Storage allocated for user data // STATE - V3ListLinks m_links; // V3List links + V3ListLinks m_links; // V3List links in the DfgGraph + std::vector> m_inputps; // Input edges, as vector, for fast indexing + DfgEdge::List m_sinks; // List of sink edges of this vertex -protected: - DfgEdge* m_sinksp = nullptr; // List of sinks of this vertex FileLine* const m_filelinep; // Source location AstNodeDType* m_dtypep; // Data type of the result of this vertex - mutable for efficiency DfgGraph* m_graphp; // The containing DfgGraph @@ -143,13 +206,17 @@ class DfgVertex VL_NOT_FINAL { uint32_t m_userCnt = 0; // User data generation number UserDataStorage m_userDataStorage = nullptr; // User data storage - // CONSTRUCTOR - DfgVertex(DfgGraph& dfg, VDfgType type, FileLine* flp, AstNodeDType* dtypep) VL_MT_DISABLED; + // METHODS + // Visitor accept method + virtual void accept(DfgVisitor& v) = 0; -public: - virtual ~DfgVertex() VL_MT_DISABLED; + // Part of Vertex equality only dependent on this vertex + virtual bool selfEquals(const DfgVertex& that) const = 0; -private: + // Part of Vertex hash only dependent on this vertex + virtual V3Hash selfHash() const = 0; + + // Acessor for type List V3ListLinks& links() { return m_links; } public: @@ -157,60 +224,60 @@ class DfgVertex VL_NOT_FINAL { template using List = V3List; - // METHODS -private: - // Visitor accept method - virtual void accept(DfgVisitor& v) = 0; - - // Part of Vertex equality only dependent on this vertex - virtual bool selfEquals(const DfgVertex& that) const VL_MT_DISABLED; +protected: + // CONSTRUCTOR + DfgVertex(DfgGraph& dfg, VDfgType type, FileLine* flp, AstNodeDType* dtypep) VL_MT_DISABLED; + // Use unlinkDelete instead + virtual ~DfgVertex() VL_MT_DISABLED = default; - // Part of Vertex hash only dependent on this vertex - virtual V3Hash selfHash() const VL_MT_DISABLED; + // Create a new input edge and return it + DfgEdge* newInput() { + m_inputps.emplace_back(new DfgEdge{this}); + return m_inputps.back().get(); + } + // Unlink all inputs and reset to no inputs + void resetInputs() { m_inputps.clear(); } public: + // Get input 'i' + DfgVertex* inputp(size_t i) const { return m_inputps[i]->srcp(); } + // Relink input 'i' + void inputp(size_t i, DfgVertex* vtxp) { m_inputps[i]->relinkSrcp(vtxp); } + // The number of inputs this vertex has. Some might be unconnected. + size_t nInputs() const { return m_inputps.size(); } + + // The type of this vertex + VDfgType type() const { return m_type; } + // Source location + FileLine* fileline() const { return m_filelinep; } // The data type of the result of the vertex AstNodeDType* dtypep() const { return m_dtypep; } - // Is it a packed type (instead of an array) bool isPacked() const { return VN_IS(dtypep(), BasicDType); } - - // Source location - FileLine* fileline() const { return m_filelinep; } - - // The type of this vertex - VDfgType type() const { return m_type; } - - // Retrieve user data, constructing it fresh on first try. - template - inline T& user(); - - // Retrieve user data, must be current. - template - inline const T& getUser() const; - - // Retrieve user data, must be current. - template - T& getUser() { - return const_cast(const_cast(this)->getUser()); - } - - // Set user data, becomes current. - template - inline void setUser(T value); - // Width of result uint32_t width() const { UASSERT_OBJ(isPacked(), this, "non-packed has no 'width()'"); return dtypep()->width(); } - // Number of sub-elements in result vertex uint32_t size() const { if (isPacked()) return dtypep()->width(); return VN_AS(dtypep(), UnpackArrayDType)->elementsConst(); } + // Retrieve user data, constructing it fresh on first try. + template + T_User& user(); + // Retrieve user data, must be current. + template + const T_User& getUser() const; + // Retrieve user data, must be current. + template + T_User& getUser(); + // Set user data, becomes current. + template + void setUser(T_User value); + // Cache type for 'equals' below using EqualsCache = std::unordered_map, uint8_t>; @@ -231,20 +298,11 @@ class DfgVertex VL_NOT_FINAL { // Uses user data for caching hashes V3Hash hash() VL_MT_DISABLED; - // Source edges of this vertex - virtual std::pair sourceEdges() = 0; - - // Source edges of this vertex - virtual std::pair sourceEdges() const = 0; - - // Arity (number of sources) of this vertex - size_t arity() const { return sourceEdges().second; } - // Predicate: has 1 or more sinks - bool hasSinks() const { return m_sinksp != nullptr; } + bool hasSinks() const { return !m_sinks.empty(); } // Predicate: has 2 or more sinks - bool hasMultipleSinks() const { return m_sinksp && m_sinksp->m_nextp; } + bool hasMultipleSinks() const { return m_sinks.hasMultipleElements(); } // Fanout (number of sinks) of this vertex (expensive to compute) uint32_t fanout() const VL_MT_DISABLED; @@ -267,69 +325,64 @@ class DfgVertex VL_NOT_FINAL { // If the node has a single sink, return it, otherwise return nullptr DfgVertex* singleSink() const { - return m_sinksp && !m_sinksp->m_nextp ? m_sinksp->m_sinkp : nullptr; + return m_sinks.hasSingleElement() ? m_sinks.frontp()->dstp() : nullptr; } // First sink of the vertex, if any, otherwise nullptr - DfgVertex* firtsSinkp() const { return m_sinksp ? m_sinksp->m_sinkp : nullptr; } + DfgVertex* firtsSinkp() { return m_sinks.empty() ? nullptr : m_sinks.frontp()->dstp(); } // Unlink from container (graph or builder), then delete this vertex void unlinkDelete(DfgGraph& dfg) VL_MT_DISABLED; // Relink all sinks to be driven from the given new source - void replaceWith(DfgVertex* newSourcep) VL_MT_DISABLED; - - // Calls given function 'f' for each source vertex of this vertex - // Unconnected source edges are not iterated. - inline void forEachSource(std::function f) VL_MT_DISABLED; - - // Calls given function 'f' for each source vertex of this vertex - // Unconnected source edges are not iterated. - inline void forEachSource(std::function f) const VL_MT_DISABLED; - - // Calls given function 'f' for each source edge of this vertex. Also passes source index. - inline void forEachSourceEdge(std::function f) VL_MT_DISABLED; - - // Calls given function 'f' for each source edge of this vertex. Also passes source index. - inline void - forEachSourceEdge(std::function f) const VL_MT_DISABLED; - - // Calls given function 'f' for each sink vertex of this vertex - // Unlinking/deleting the given sink during iteration is safe, but not other sinks of this - // vertex. - inline void forEachSink(std::function f) VL_MT_DISABLED; - - // Calls given function 'f' for each sink vertex of this vertex - inline void forEachSink(std::function f) const VL_MT_DISABLED; - - // Calls given function 'f' for each sink edge of this vertex. - // Unlinking/deleting the given sink during iteration is safe, but not other sinks of this - // vertex. - inline void forEachSinkEdge(std::function f) VL_MT_DISABLED; - - // Calls given function 'f' for each sink edge of this vertex. - inline void forEachSinkEdge(std::function f) const VL_MT_DISABLED; - - // Returns first source edge which satisfies the given predicate 'p', or nullptr if no such - // sink vertex exists - inline const DfgEdge* - findSourceEdge(std::function p) const VL_MT_DISABLED; - - // Returns first sink vertex of type 'Vertex' which satisfies the given predicate 'p', - // or nullptr if no such sink vertex exists - template - inline Vertex* findSink(std::function p) const VL_MT_DISABLED; + void replaceWith(DfgVertex* vtxp) { + while (!m_sinks.empty()) m_sinks.frontp()->relinkSrcp(vtxp); + } + + // Calls given function 'f' for each source vertex of this vertex. If 'f' + // returns true, further sources are not iterated and this method returns + // true itself. Unconnected source edges are not iterated. + bool foreachSource(std::function f) { + for (const std::unique_ptr& edgep : m_inputps) { + if (DfgVertex* const srcp = edgep->srcp()) { + if (f(*srcp)) return true; + } + } + return false; + } - // Returns first sink vertex of type 'Vertex', or nullptr if no such sink vertex exists. - // This is a special case of 'findSink' above with the predicate always true. - template - inline Vertex* findSink() const VL_MT_DISABLED; + // Calls given function 'f' for each source vertex of this vertex. If 'f' + // returns true, further sources are not iterated and this method returns + // true itself. Unconnected source edges are not iterated. + bool foreachSource(std::function f) const { + for (const std::unique_ptr& edgep : m_inputps) { + if (DfgVertex* const srcp = edgep->srcp()) { + if (f(*srcp)) return true; + } + } + return false; + } - // Is this a DfgConst that is all zeroes - inline bool isZero() const VL_MT_DISABLED; + // Calls given function 'f' for each sink vertex of this vertex. If 'f' + // returns true, further sinks are not iterated and this method returns + // true itself. Unlinking/deleting the given sink during iteration is safe, + // but not other sinks of this vertex. + bool foreachSink(std::function f) { + for (const DfgEdge* const edgep : m_sinks.unlinkable()) { + if (f(*edgep->dstp())) return true; + } + return false; + } - // Is this a DfgConst that is all ones - inline bool isOnes() const VL_MT_DISABLED; + // Calls given function 'f' for each sink vertex of this vertex. If 'f' + // returns true, further sinks are not iterated and this method returns + // true itself. + bool foreachSink(std::function f) const { + for (const DfgEdge& edge : m_sinks) { + if (f(*edge.dstp())) return true; + } + return false; + } // Methods that allow DfgVertex to participate in error reporting/messaging void v3errorEnd(std::ostringstream& str) const VL_RELEASE(V3Error::s().m_mutex) { @@ -387,211 +440,30 @@ class DfgVertex VL_NOT_FINAL { } // Human-readable vertex type as string for debugging - const string typeName() const { return m_type.ascii(); } + std::string typeName() const { return m_type.ascii(); } // Human-readable name for source operand with given index for debugging - virtual const string srcName(size_t idx) const = 0; + virtual std::string srcName(size_t idx) const = 0; }; -//------------------------------------------------------------------------------ -// Dfg vertex visitor -//------------------------------------------------------------------------------ - +// DfgVertex visitor class DfgVisitor VL_NOT_FINAL { public: // Dispatch to most specific 'visit' method on 'vtxp' void iterate(DfgVertex* vtxp) { vtxp->accept(*this); } - + // Least specific visit method is abstract virtual void visit(DfgVertex* nodep) = 0; #include "V3Dfg__gen_visitor_decls.h" // From ./astgen }; -//------------------------------------------------------------------------------ -// DfgVertex sub-types follow -//------------------------------------------------------------------------------ - -// Include macros generated by 'astgen'. These include DFGGEN_MEMBERS_ -// for each DfgVertex sub-type. The generated members include boilerplate -// methods related to cloning, visitor dispatch, and other functionality. -// For precise details please read the generated macros. -#include "V3Dfg__gen_macros.h" - -//------------------------------------------------------------------------------ -// Implementation of dataflow graph vertices with a fixed number of sources -//------------------------------------------------------------------------------ - -template -class DfgVertexWithArity VL_NOT_FINAL : public DfgVertex { - static_assert(1 <= N_Arity && N_Arity <= 4, "N_Arity must be between 1 and 4 inclusive"); - - std::array m_srcs; // Source edges - -protected: - DfgVertexWithArity(DfgGraph& dfg, VDfgType type, FileLine* flp, AstNodeDType* dtypep) - : DfgVertex{dfg, type, flp, dtypep} { - // Initialize source edges - for (size_t i = 0; i < N_Arity; ++i) m_srcs[i].init(this); - } - - ~DfgVertexWithArity() override = default; - -public: - std::pair sourceEdges() final override { // - return {m_srcs.data(), N_Arity}; - } - std::pair sourceEdges() const final override { - return {m_srcs.data(), N_Arity}; - } - - template - DfgEdge* sourceEdge() { - static_assert(N_Index < N_Arity, "Source index out of range"); - return &m_srcs[N_Index]; - } - - template - const DfgEdge* sourceEdge() const { - static_assert(N_Index < N_Arity, "Source index out of range"); - return &m_srcs[N_Index]; - } - - template - DfgVertex* source() const { - static_assert(N_Index < N_Arity, "Source index out of range"); - return m_srcs[N_Index].sourcep(); - } - - template - void relinkSource(DfgVertex* newSourcep) { - static_assert(N_Index < N_Arity, "Source index out of range"); - UASSERT_OBJ(m_srcs[N_Index].sinkp() == this, this, "Inconsistent"); - m_srcs[N_Index].relinkSource(newSourcep); - } -}; - -class DfgVertexUnary VL_NOT_FINAL : public DfgVertexWithArity<1> { -protected: - DfgVertexUnary(DfgGraph& dfg, VDfgType type, FileLine* flp, AstNodeDType* dtypep) - : DfgVertexWithArity<1>{dfg, type, flp, dtypep} {} - -public: - ASTGEN_MEMBERS_DfgVertexUnary; - - // Named getter/setter for sources - DfgVertex* srcp() const { return source<0>(); } - void srcp(DfgVertex* vtxp) { relinkSource<0>(vtxp); } -}; - -class DfgVertexBinary VL_NOT_FINAL : public DfgVertexWithArity<2> { -protected: - DfgVertexBinary(DfgGraph& dfg, VDfgType type, FileLine* flp, AstNodeDType* dtypep) - : DfgVertexWithArity<2>{dfg, type, flp, dtypep} {} - -public: - ASTGEN_MEMBERS_DfgVertexBinary; - - // Named getter/setter for sources - DfgVertex* lhsp() const { return source<0>(); } - void lhsp(DfgVertex* vtxp) { relinkSource<0>(vtxp); } - DfgVertex* rhsp() const { return source<1>(); } - void rhsp(DfgVertex* vtxp) { relinkSource<1>(vtxp); } -}; - -class DfgVertexTernary VL_NOT_FINAL : public DfgVertexWithArity<3> { -protected: - DfgVertexTernary(DfgGraph& dfg, VDfgType type, FileLine* flp, AstNodeDType* dtypep) - : DfgVertexWithArity<3>{dfg, type, flp, dtypep} {} - -public: - ASTGEN_MEMBERS_DfgVertexTernary; -}; - -//------------------------------------------------------------------------------ -// Implementation of dataflow graph vertices with a variable number of sources -//------------------------------------------------------------------------------ - -class DfgVertexVariadic VL_NOT_FINAL : public DfgVertex { - DfgEdge* m_srcsp; // The source edges - uint32_t m_srcCnt = 0; // Number of sources used - uint32_t m_srcCap; // Number of sources allocated - - // Allocate a new source edge array - DfgEdge* allocSources(size_t n) { - DfgEdge* const srcsp = new DfgEdge[n]; - for (size_t i = 0; i < n; ++i) srcsp[i].init(this); - return srcsp; - } - - // Double the capacity of m_srcsp - void growSources() { - m_srcCap *= 2; - DfgEdge* const newsp = allocSources(m_srcCap); - for (size_t i = 0; i < m_srcCnt; ++i) { - DfgEdge* const oldp = m_srcsp + i; - // Skip over unlinked source edge - if (!oldp->sourcep()) continue; - // New edge driven from the same vertex as the old edge - newsp[i].relinkSource(oldp->sourcep()); - // Unlink the old edge, it will be deleted - oldp->unlinkSource(); - } - // Delete old source edges - delete[] m_srcsp; - // Keep hold of new source edges - m_srcsp = newsp; - } - -protected: - DfgVertexVariadic(DfgGraph& dfg, VDfgType type, FileLine* flp, AstNodeDType* dtypep, - uint32_t initialCapacity) - : DfgVertex{dfg, type, flp, dtypep} - , m_srcsp{allocSources(initialCapacity)} - , m_srcCap{initialCapacity} {} - - ~DfgVertexVariadic() override { delete[] m_srcsp; }; - - DfgEdge* addSource() { - if (m_srcCnt == m_srcCap) growSources(); - return m_srcsp + m_srcCnt++; - } - - void resetSources() { - // #ifdef VL_DEBUG TODO: DEBUG ONLY - for (uint32_t i = 0; i < m_srcCnt; ++i) { - UASSERT_OBJ(!m_srcsp[i].sourcep(), m_srcsp[i].sourcep(), "Connected source"); - } - // #endif - m_srcCnt = 0; - } - - void clearSources() { - for (uint32_t i = 0; i < m_srcCnt; ++i) { - UASSERT_OBJ(m_srcsp[i].sourcep(), this, "Unconnected source"); - m_srcsp[i].unlinkSource(); - } - m_srcCnt = 0; - } - - ASTGEN_MEMBERS_DfgVertexVariadic; - - DfgEdge* sourceEdge(size_t idx) const { return &m_srcsp[idx]; } - DfgVertex* source(size_t idx) const { return m_srcsp[idx].sourcep(); } - -public: - std::pair sourceEdges() override { return {m_srcsp, m_srcCnt}; } - std::pair sourceEdges() const override { return {m_srcsp, m_srcCnt}; } -}; - // DfgVertex subclasses #include "V3DfgVertices.h" -// The rest of the DfgVertex subclasses are generated by 'astgen' from AstNodeExpr nodes -#include "V3Dfg__gen_auto_classes.h" +// Specializations of privateTypeTest +#include "V3Dfg__gen_type_tests.h" // From ./astgen //------------------------------------------------------------------------------ // Dataflow graph -//------------------------------------------------------------------------------ - class DfgGraph final { friend class DfgVertex; @@ -649,10 +521,6 @@ class DfgGraph final { // METHODS public: - // Add DfgVertex to this graph (assumes not yet contained). - inline void addVertex(DfgVertex& vtx); - // Remove DfgVertex form this graph (assumes it is contained). - inline void removeVertex(DfgVertex& vtx); // Number of vertices in this graph size_t size() const { return m_size; } // Parent module - or nullptr when run after V3Scope @@ -677,13 +545,51 @@ class DfgGraph final { DfgVertex::List& opVertices() { return m_opVertices; } const DfgVertex::List& opVertices() const { return m_opVertices; } + // Add DfgVertex to this graph (assumes not yet contained). + void addVertex(DfgVertex& vtx) { + // Note: changes here need to be replicated in DfgGraph::mergeGraphs + ++m_size; + if (DfgConst* const cVtxp = vtx.cast()) { + m_constVertices.linkBack(cVtxp); + } else if (DfgVertexVar* const vVtxp = vtx.cast()) { + m_varVertices.linkBack(vVtxp); + } else { + m_opVertices.linkBack(&vtx); + } + vtx.m_userCnt = 0; + vtx.m_graphp = this; + } + + // Remove DfgVertex form this graph (assumes it is contained). + void removeVertex(DfgVertex& vtx) { + // Note: changes here need to be replicated in DfgGraph::mergeGraphs + --m_size; + if (DfgConst* const cVtxp = vtx.cast()) { + m_constVertices.unlink(cVtxp); + } else if (DfgVertexVar* const vVtxp = vtx.cast()) { + m_varVertices.unlink(vVtxp); + } else { + m_opVertices.unlink(&vtx); + } + vtx.m_userCnt = 0; + vtx.m_graphp = nullptr; + } + // Calls given function 'f' for each vertex in the graph. It is safe to manipulate any vertices // in the graph, or to delete/unlink the vertex passed to 'f' during iteration. It is however // not safe to delete/unlink any vertex in the same graph other than the one passed to 'f'. - inline void forEachVertex(std::function f); + void forEachVertex(std::function f) { + for (DfgVertexVar* const vtxp : m_varVertices.unlinkable()) f(*vtxp); + for (DfgConst* const vtxp : m_constVertices.unlinkable()) f(*vtxp); + for (DfgVertex* const vtxp : m_opVertices.unlinkable()) f(*vtxp); + } // 'const' variant of 'forEachVertex'. No mutation allowed. - inline void forEachVertex(std::function f) const; + void forEachVertex(std::function f) const { + for (const DfgVertexVar& vtx : m_varVertices) f(vtx); + for (const DfgConst& vtx : m_constVertices) f(vtx); + for (const DfgVertex& vtx : m_opVertices) f(vtx); + } // Return an identical, independent copy of this graph. Vertex and edge order might differ. std::unique_ptr clone() const VL_MT_DISABLED; @@ -747,102 +653,62 @@ class DfgGraph final { // Returns the set of vertices in the downstream cones of the given vertices std::unique_ptr> sinkCone(const std::vector&) const VL_MT_DISABLED; +}; - //----------------------------------------------------------------------- - // Static methods for data types - - // Some data types are interned, in order to facilitate type comparison - // via pointer compariosn. These are functoins to construct the canonical - // DFG data types - - // Returns data type used to represent any packed value of the given 'width'. - static AstNodeDType* dtypePacked(uint32_t width) { - return v3Global.rootp()->typeTablep()->findLogicDType(width, width, VSigning::UNSIGNED); - } +//------------------------------------------------------------------------------ +// Inline method definitions - // Returns data type used to represent any array with the given type and number of elements. - static AstNodeDType* dtypeArray(AstNodeDType* subDtypep, uint32_t size) { - UASSERT_OBJ(isSupported(subDtypep), subDtypep, "Unsupported element type"); - FileLine* const flp = subDtypep->fileline(); - AstRange* const rangep = new AstRange{flp, static_cast(size - 1), 0}; - AstNodeDType* const dtypep = new AstUnpackArrayDType{flp, subDtypep, rangep}; - v3Global.rootp()->typeTablep()->addTypesp(dtypep); - return dtypep; - } +// DfgEdge {{{ - // Return data type used to represent the type of 'nodep' when converted to a DfgVertex - static AstNodeDType* toDfgDType(const AstNodeDType* dtypep) { - dtypep = dtypep->skipRefp(); - UASSERT_OBJ(isSupported(dtypep), dtypep, "Unsupported dtype"); - // For simplicity, all packed types are represented with a fixed type - if (const AstUnpackArrayDType* const uatp = VN_CAST(dtypep, UnpackArrayDType)) { - return dtypeArray(toDfgDType(uatp->subDTypep()), uatp->elementsConst()); - } - return dtypePacked(dtypep->width()); - } - - //----------------------------------------------------------------------- - // Static methods for compatibility tests - - // Returns true if the given data type can be represented in the graph - static bool isSupported(const AstNodeDType* dtypep) VL_MT_DISABLED; - - // Returns true if variable can be represented in the graph - static bool isSupported(const AstVar* varp) { - if (varp->isIfaceRef()) return false; // Cannot handle interface references - if (varp->delayp()) return false; // Cannot handle delayed variables - if (varp->isSc()) return false; // SystemC variables are special and rare, we can ignore - if (varp->dfgMultidriven()) return false; // Discovered as multidriven on earlier DFG run - return isSupported(varp->dtypep()); +void DfgEdge::unlinkSrcp() { + if (!m_srcp) return; +#ifdef VL_DEBUG + bool contained = false; + for (const DfgEdge& edge : m_srcp->m_sinks) { + if (&edge != this) continue; + contained = true; + break; } + UASSERT_OBJ(contained, m_srcp, "'m_srcp' does not have this as sink"); +#endif + m_srcp->m_sinks.unlink(this); + m_srcp = nullptr; +} - // Returns true if variable can be represented in the graph - static bool isSupported(const AstVarScope* vscp) { - AstNodeModule* const modp = vscp->scopep()->modp(); - if (VN_IS(modp, Module)) { - // Regular module supported - } else if (AstIface* const ifacep = VN_CAST(modp, Iface)) { - // Interfaces supported if there are no virtual interfaces for - // them, otherwise they cannot be resovled statically. - if (ifacep->hasVirtualRef()) return false; - } else { - return false; // Anything else (package, class, etc) not supported - } - // Check the AstVar - return isSupported(vscp->varp()); - } -}; +void DfgEdge::relinkSrcp(DfgVertex* srcp) { + // Unlink current source, if any + unlinkSrcp(); + m_srcp = srcp; + if (m_srcp) m_srcp->m_sinks.linkFront(this); +} -// Specializations of privateTypeTest -#include "V3Dfg__gen_type_tests.h" // From ./astgen +// }}} -//------------------------------------------------------------------------------ -// Inline method definitions - for DfgVertex -//------------------------------------------------------------------------------ +// DfgVertex {{{ -template -T& DfgVertex::user() { - static_assert(sizeof(T) <= sizeof(UserDataStorage), - "Size of user data type 'T' is too large for allocated storage"); - static_assert(alignof(T) <= alignof(UserDataStorage), - "Alignment of user data type 'T' is larger than allocated storage"); - T* const storagep = reinterpret_cast(&m_userDataStorage); +template +T_User& DfgVertex::user() { + static_assert(sizeof(T_User) <= sizeof(UserDataStorage), + "Size of user data type 'T_User' is too large for allocated storage"); + static_assert(alignof(T_User) <= alignof(UserDataStorage), + "Alignment of user data type 'T_User' is larger than allocated storage"); + T_User* const storagep = reinterpret_cast(&m_userDataStorage); const uint32_t userCurrent = m_graphp->m_userCurrent; UDEBUGONLY(UASSERT_OBJ(userCurrent, this, "DfgVertex user data used without reserving");); if (m_userCnt != userCurrent) { m_userCnt = userCurrent; - new (storagep) T{}; + new (storagep) T_User{}; } return *storagep; } -template -const T& DfgVertex::getUser() const { - static_assert(sizeof(T) <= sizeof(UserDataStorage), - "Size of user data type 'T' is too large for allocated storage"); - static_assert(alignof(T) <= alignof(UserDataStorage), - "Alignment of user data type 'T' is larger than allocated storage"); - const T* const storagep = reinterpret_cast(&m_userDataStorage); +template +const T_User& DfgVertex::getUser() const { + static_assert(sizeof(T_User) <= sizeof(UserDataStorage), + "Size of user data type 'T_User' is too large for allocated storage"); + static_assert(alignof(T_User) <= alignof(UserDataStorage), + "Alignment of user data type 'T_User' is larger than allocated storage"); + const T_User* const storagep = reinterpret_cast(&m_userDataStorage); #if VL_DEBUG const uint32_t userCurrent = m_graphp->m_userCurrent; UASSERT_OBJ(userCurrent, this, "DfgVertex user data used without reserving"); @@ -851,13 +717,18 @@ const T& DfgVertex::getUser() const { return *storagep; } -template -void DfgVertex::setUser(T value) { - static_assert(sizeof(T) <= sizeof(UserDataStorage), - "Size of user data type 'T' is too large for allocated storage"); - static_assert(alignof(T) <= alignof(UserDataStorage), - "Alignment of user data type 'T' is larger than allocated storage"); - T* const storagep = reinterpret_cast(&m_userDataStorage); +template +T_User& DfgVertex::getUser() { + return const_cast(const_cast(this)->getUser()); +} + +template +void DfgVertex::setUser(T_User value) { + static_assert(sizeof(T_User) <= sizeof(UserDataStorage), + "Size of user data type 'T_User' is too large for allocated storage"); + static_assert(alignof(T_User) <= alignof(UserDataStorage), + "Alignment of user data type 'T_User' is larger than allocated storage"); + T_User* const storagep = reinterpret_cast(&m_userDataStorage); const uint32_t userCurrent = m_graphp->m_userCurrent; #if VL_DEBUG UASSERT_OBJ(userCurrent, this, "DfgVertex user data used without reserving"); @@ -866,207 +737,6 @@ void DfgVertex::setUser(T value) { *storagep = value; } -void DfgVertex::forEachSource(std::function f) { - const auto pair = sourceEdges(); - const DfgEdge* const edgesp = pair.first; - const size_t nEdges = pair.second; - for (size_t i = 0; i < nEdges; ++i) { - if (DfgVertex* const sourcep = edgesp[i].m_sourcep) f(*sourcep); - } -} - -void DfgVertex::forEachSource(std::function f) const { - const auto pair = sourceEdges(); - const DfgEdge* const edgesp = pair.first; - const size_t nEdges = pair.second; - for (size_t i = 0; i < nEdges; ++i) { - if (DfgVertex* const sourcep = edgesp[i].m_sourcep) f(*sourcep); - } -} - -void DfgVertex::forEachSink(std::function f) { - for (const DfgEdge *edgep = m_sinksp, *nextp; edgep; edgep = nextp) { - nextp = edgep->m_nextp; - f(*edgep->m_sinkp); - } -} - -void DfgVertex::forEachSink(std::function f) const { - for (const DfgEdge* edgep = m_sinksp; edgep; edgep = edgep->m_nextp) f(*edgep->m_sinkp); -} - -void DfgVertex::forEachSourceEdge(std::function f) { - const auto pair = sourceEdges(); - DfgEdge* const edgesp = pair.first; - const size_t nEdges = pair.second; - for (size_t i = 0; i < nEdges; ++i) f(edgesp[i], i); -} - -void DfgVertex::forEachSourceEdge(std::function f) const { - const auto pair = sourceEdges(); - const DfgEdge* const edgesp = pair.first; - const size_t nEdges = pair.second; - for (size_t i = 0; i < nEdges; ++i) f(edgesp[i], i); -} - -void DfgVertex::forEachSinkEdge(std::function f) { - for (DfgEdge *edgep = m_sinksp, *nextp; edgep; edgep = nextp) { - nextp = edgep->m_nextp; - f(*edgep); - } -} - -void DfgVertex::forEachSinkEdge(std::function f) const { - for (DfgEdge *edgep = m_sinksp, *nextp; edgep; edgep = nextp) { - nextp = edgep->m_nextp; - f(*edgep); - } -} - -const DfgEdge* DfgVertex::findSourceEdge(std::function p) const { - const auto pair = sourceEdges(); - const DfgEdge* const edgesp = pair.first; - const size_t nEdges = pair.second; - for (size_t i = 0; i < nEdges; ++i) { - const DfgEdge& edge = edgesp[i]; - if (p(edge, i)) return &edge; - } - return nullptr; -} - -template -Vertex* DfgVertex::findSink(std::function p) const { - static_assert(std::is_base_of::value, - "'Vertex' must be subclass of 'DfgVertex'"); - for (DfgEdge* edgep = m_sinksp; edgep; edgep = edgep->m_nextp) { - if (Vertex* const sinkp = edgep->m_sinkp->cast()) { - if (p(*sinkp)) return sinkp; - } - } - return nullptr; -} - -template -Vertex* DfgVertex::findSink() const { - static_assert(!std::is_same::value, - "'Vertex' must be proper subclass of 'DfgVertex'"); - return findSink([](const Vertex&) { return true; }); -} - -bool DfgVertex::isZero() const { - if (const DfgConst* const constp = cast()) return constp->isZero(); - return false; -} - -bool DfgVertex::isOnes() const { - if (const DfgConst* const constp = cast()) return constp->isOnes(); - return false; -} - -//------------------------------------------------------------------------------ -// Inline method definitions - for DfgConst -//------------------------------------------------------------------------------ - -DfgConst::DfgConst(DfgGraph& dfg, FileLine* flp, const V3Number& num) - : DfgVertex{dfg, dfgType(), flp, DfgGraph::dtypePacked(num.width())} - , m_num{num} {} -DfgConst::DfgConst(DfgGraph& dfg, FileLine* flp, uint32_t width, uint32_t value) - : DfgVertex{dfg, dfgType(), flp, DfgGraph::dtypePacked(width)} - , m_num{flp, static_cast(width), value} {} - -//------------------------------------------------------------------------------ -// Inline method definitions - for DfgVertexSplice -//------------------------------------------------------------------------------ - -DfgVertex* DfgVertexSplice::wholep() const { - if (defaultp()) return nullptr; - if (arity() != 1) return nullptr; - if (driverLo(0) != 0) return nullptr; - DfgVertex* const srcp = DfgVertexVariadic::source(1); - if (srcp->size() != size()) return nullptr; - if (const DfgUnitArray* const uap = srcp->cast()) { - if (const DfgVertexSplice* sp = uap->srcp()->cast()) { - if (!sp->wholep()) return nullptr; - } - } - return srcp; -} - -//------------------------------------------------------------------------------ -// Inline method definitions - for DfgVertexVar -//------------------------------------------------------------------------------ - -DfgVertexVar::DfgVertexVar(DfgGraph& dfg, VDfgType type, AstVar* varp) - : DfgVertexUnary{dfg, type, varp->fileline(), DfgGraph::toDfgDType(varp->dtypep())} - , m_varp{varp} - , m_varScopep{nullptr} { - UASSERT_OBJ(dfg.modulep(), varp, "Un-scoped DfgVertexVar created in scoped DfgGraph"); - UASSERT_OBJ(!m_varp->isSc(), varp, "SystemC variable is not representable by DfgVertexVar"); - // Increment reference count - varp->user1(varp->user1() + 0x10); - UASSERT_OBJ((varp->user1() >> 4) > 0, varp, "Reference count overflow"); -} -DfgVertexVar::DfgVertexVar(DfgGraph& dfg, VDfgType type, AstVarScope* vscp) - : DfgVertexUnary{dfg, type, vscp->fileline(), DfgGraph::toDfgDType(vscp->varp()->dtypep())} - , m_varp{vscp->varp()} - , m_varScopep{vscp} { - UASSERT_OBJ(!dfg.modulep(), vscp, "Scoped DfgVertexVar created in un-scoped DfgGraph"); - UASSERT_OBJ(!m_varp->isSc(), vscp, "SystemC variable is not representable by DfgVertexVar"); - // Increment reference count - vscp->user1(vscp->user1() + 0x10); - UASSERT_OBJ((vscp->user1() >> 4) > 0, vscp, "Reference count overflow"); -} - -DfgVertexVar::~DfgVertexVar() { - // Decrement reference count - // cppcheck-suppress shadowFunction - AstNode* const nodep = this->nodep(); - nodep->user1(nodep->user1() - 0x10); - UASSERT_OBJ((nodep->user1() >> 4) >= 0, nodep, "Reference count underflow"); -} - -//------------------------------------------------------------------------------ -// Inline method definitions - for DfgGraph -//------------------------------------------------------------------------------ - -void DfgGraph::addVertex(DfgVertex& vtx) { - // Note: changes here need to be replicated in DfgGraph::mergeGraph - ++m_size; - if (DfgConst* const cVtxp = vtx.cast()) { - m_constVertices.linkBack(cVtxp); - } else if (DfgVertexVar* const vVtxp = vtx.cast()) { - m_varVertices.linkBack(vVtxp); - } else { - m_opVertices.linkBack(&vtx); - } - vtx.m_userCnt = 0; - vtx.m_graphp = this; -} - -void DfgGraph::removeVertex(DfgVertex& vtx) { - // Note: changes here need to be replicated in DfgGraph::mergeGraph - --m_size; - if (DfgConst* const cVtxp = vtx.cast()) { - m_constVertices.unlink(cVtxp); - } else if (DfgVertexVar* const vVtxp = vtx.cast()) { - m_varVertices.unlink(vVtxp); - } else { - m_opVertices.unlink(&vtx); - } - vtx.m_userCnt = 0; - vtx.m_graphp = nullptr; -} - -void DfgGraph::forEachVertex(std::function f) { - for (DfgVertexVar* const vtxp : m_varVertices.unlinkable()) f(*vtxp); - for (DfgConst* const vtxp : m_constVertices.unlinkable()) f(*vtxp); - for (DfgVertex* const vtxp : m_opVertices.unlinkable()) f(*vtxp); -} - -void DfgGraph::forEachVertex(std::function f) const { - for (const DfgVertexVar& vtx : m_varVertices) f(vtx); - for (const DfgConst& vtx : m_constVertices) f(vtx); - for (const DfgVertex& vtx : m_opVertices) f(vtx); -} +// }}} #endif diff --git a/src/V3DfgAstToDfg.cpp b/src/V3DfgAstToDfg.cpp index 18df9a1b082..bdc19039474 100644 --- a/src/V3DfgAstToDfg.cpp +++ b/src/V3DfgAstToDfg.cpp @@ -46,6 +46,7 @@ class AstToDfgVisitor final : public VNVisitor { // STATE DfgGraph& m_dfg; // The graph being built V3DfgAstToDfgContext& m_ctx; // The context for stats + AstScope* m_scopep = nullptr; // The current scope, iff T_Scoped // METHODS static Variable* getTarget(const AstVarRef* refp) { @@ -104,7 +105,7 @@ class AstToDfgVisitor final : public VNVisitor { if (VN_IS(vrefp, VarXRef)) return true; if (vrefp->access().isReadOnly()) return false; Variable* const varp = getTarget(VN_AS(vrefp, VarRef)); - if (!DfgGraph::isSupported(varp)) return true; + if (!V3Dfg::isSupported(varp)) return true; if (!varp->user3SetOnce()) resp->emplace_back(getVarVertex(varp)); return false; }); @@ -126,7 +127,7 @@ class AstToDfgVisitor final : public VNVisitor { if (VN_IS(vrefp, VarXRef)) return true; if (vrefp->access().isWriteOnly()) return false; Variable* const varp = getTarget(VN_AS(vrefp, VarRef)); - if (!DfgGraph::isSupported(varp)) return true; + if (!V3Dfg::isSupported(varp)) return true; if (!varp->user3SetOnce()) resp->emplace_back(getVarVertex(varp)); return false; }); @@ -152,7 +153,7 @@ class AstToDfgVisitor final : public VNVisitor { std::unique_ptr> resp{new std::vector{}}; resp->reserve(varps->size()); for (Variable* const varp : *varps) { - if (!DfgGraph::isSupported(varp)) { + if (!V3Dfg::isSupported(varp)) { ++m_ctx.m_nonRepVar; return nullptr; } @@ -188,7 +189,7 @@ class AstToDfgVisitor final : public VNVisitor { const std::unique_ptr> iVarpsp = gatherRead(nodep); if (!iVarpsp) return false; // Create the DfgLogic - DfgLogic* const logicp = new DfgLogic{m_dfg, nodep}; + DfgLogic* const logicp = new DfgLogic{m_dfg, nodep, m_scopep}; // Connect it up connect(*logicp, *iVarpsp, *oVarpsp); // Done @@ -218,7 +219,7 @@ class AstToDfgVisitor final : public VNVisitor { const std::unique_ptr> iVarpsp = gatherLive(*cfgp); if (!iVarpsp) return false; // Create the DfgLogic - DfgLogic* const logicp = new DfgLogic{m_dfg, nodep, std::move(cfgp)}; + DfgLogic* const logicp = new DfgLogic{m_dfg, nodep, m_scopep, std::move(cfgp)}; // Connect it up connect(*logicp, *iVarpsp, *oVarpsp); // Done @@ -241,7 +242,11 @@ class AstToDfgVisitor final : public VNVisitor { } } void visit(AstTopScope* nodep) override { iterate(nodep->scopep()); } - void visit(AstScope* nodep) override { iterateChildren(nodep); } + void visit(AstScope* nodep) override { + VL_RESTORER(m_scopep); + m_scopep = nodep; + iterateChildren(nodep); + } void visit(AstActive* nodep) override { if (nodep->hasCombo()) { iterateChildren(nodep); @@ -268,6 +273,8 @@ class AstToDfgVisitor final : public VNVisitor { , m_ctx{ctx} { iterate(&root); } + VL_UNCOPYABLE(AstToDfgVisitor); + VL_UNMOVABLE(AstToDfgVisitor); public: static void apply(DfgGraph& dfg, RootType& root, V3DfgAstToDfgContext& ctx) { diff --git a/src/V3DfgBreakCycles.cpp b/src/V3DfgBreakCycles.cpp index aab0f1eab67..c2b35a92b50 100644 --- a/src/V3DfgBreakCycles.cpp +++ b/src/V3DfgBreakCycles.cpp @@ -68,6 +68,7 @@ class TraceDriver final : public DfgVisitor { const bool m_aggressive; // Trace aggressively, creating intermediate ops uint32_t m_lsb = 0; // LSB to extract from the currently visited Vertex uint32_t m_msb = 0; // MSB to extract from the currently visited Vertex + DfgVertex* m_defaultp = nullptr; // When tracing a variable, this is its 'defaultp', if any // Result of tracing the currently visited Vertex. Use SET_RESULT below! DfgVertex* m_resp = nullptr; std::vector m_newVtxps; // New vertices created during the traversal @@ -108,7 +109,7 @@ class TraceDriver final : public DfgVisitor { "Should only create Const, Sel, Concat, Exend Vertices without aggressive mode"); if VL_CONSTEXPR_CXX17 (std::is_same::value) { - DfgConst* const vtxp = new DfgConst{m_dfg, refp->fileline(), width}; + DfgConst* const vtxp = new DfgConst{m_dfg, refp->fileline(), width, 0}; vtxp->template setUser(0); m_newVtxps.emplace_back(vtxp); return reinterpret_cast(vtxp); @@ -118,7 +119,7 @@ class TraceDriver final : public DfgVisitor { // Vertex is DfgConst, in which case this code is unreachable ... using Vtx = typename std::conditional::value, DfgSel, Vertex>::type; - AstNodeDType* const dtypep = DfgGraph::dtypePacked(width); + AstNodeDType* const dtypep = V3Dfg::dtypePacked(width); Vtx* const vtxp = new Vtx{m_dfg, refp->fileline(), dtypep}; vtxp->template setUser(0); m_newVtxps.emplace_back(vtxp); @@ -158,9 +159,13 @@ class TraceDriver final : public DfgVisitor { // Trace the vertex onStackr = true; - if (vtxp->getUser() != m_component) { - // If the currently traced vertex is in a different component, - // then we found what we were looking for. + // If the currently traced vertex is in a different component, then we + // found what we were looking for. However, keep going past a splice, + // or a unit as they cannot be use directly (they must always feed into + // a variable, so we can't make them drive arbitrary logic) + if (vtxp->getUser() != m_component // + && !vtxp->is() // + && !vtxp->is()) { if (msb != vtxp->width() - 1 || lsb != 0) { // Apply a Sel to extract the relevant bits if only a part is needed DfgSel* const selp = make(vtxp, msb - lsb + 1); @@ -294,30 +299,25 @@ class TraceDriver final : public DfgVisitor { , m_msb{msb} {} }; std::vector drivers; - DfgVertex* const defaultp = vtxp->defaultp(); // Look at all the drivers, one might cover the whole range, but also gathe all drivers - const auto pair = vtxp->sourceEdges(); - bool tryWholeDefault = defaultp; - for (size_t i = 0; i < pair.second; ++i) { - DfgVertex* const srcp = pair.first[i].sourcep(); - if (srcp == defaultp) continue; - - const uint32_t lsb = vtxp->driverLo(i); - const uint32_t msb = lsb + srcp->width() - 1; - drivers.emplace_back(srcp, lsb, msb); + bool tryWholeDefault = m_defaultp; + const bool done = vtxp->foreachDriver([&](DfgVertex& src, uint32_t lsb) { + const uint32_t msb = lsb + src.width() - 1; + drivers.emplace_back(&src, lsb, msb); // Check if this driver covers any of the bits, then we can't use whole default if (m_msb >= lsb && msb >= m_lsb) tryWholeDefault = false; // If it does not cover the whole searched bit range, move on - if (m_lsb < lsb || msb < m_msb) continue; + if (m_lsb < lsb || msb < m_msb) return false; // Driver covers whole search range, trace that and we are done - SET_RESULT(trace(srcp, m_msb - lsb, m_lsb - lsb)); - return; - } + SET_RESULT(trace(&src, m_msb - lsb, m_lsb - lsb)); + return true; + }); + if (done) return; // Trace the default driver if no other drivers cover the searched range - if (defaultp && tryWholeDefault) { - SET_RESULT(trace(defaultp, m_msb, m_lsb)); + if (tryWholeDefault) { + SET_RESULT(trace(m_defaultp, m_msb, m_lsb)); return; } @@ -336,8 +336,8 @@ class TraceDriver final : public DfgVisitor { if (driver.m_lsb > m_msb) break; // Gap below this driver, trace default to fill it if (driver.m_lsb > m_lsb) { - if (!defaultp) return; - DfgVertex* const termp = trace(defaultp, driver.m_lsb - 1, m_lsb); + if (!m_defaultp) return; + DfgVertex* const termp = trace(m_defaultp, driver.m_lsb - 1, m_lsb); if (!termp) return; termps.emplace_back(termp); m_lsb = driver.m_lsb; @@ -351,8 +351,8 @@ class TraceDriver final : public DfgVisitor { m_lsb = lim + 1; } if (m_msb >= m_lsb) { - if (!defaultp) return; - DfgVertex* const termp = trace(defaultp, m_msb, m_lsb); + if (!m_defaultp) return; + DfgVertex* const termp = trace(m_defaultp, m_msb, m_lsb); if (!termp) return; termps.emplace_back(termp); } @@ -374,6 +374,8 @@ class TraceDriver final : public DfgVisitor { } void visit(DfgVarPacked* vtxp) override { + VL_RESTORER(m_defaultp); + m_defaultp = vtxp->defaultp(); if (DfgVertex* const srcp = vtxp->srcp()) { SET_RESULT(trace(srcp, m_msb, m_lsb)); return; @@ -719,17 +721,30 @@ class IndependentBits final : public DfgVisitor { void visit(DfgSplicePacked* vtxp) override { // Combine the masks of all drivers V3Number& m = MASK(vtxp); - DfgVertex* const defaultp = vtxp->defaultp(); - if (defaultp) m = MASK(defaultp); - vtxp->forEachSourceEdge([&](DfgEdge& edge, size_t i) { - const DfgVertex* const srcp = edge.sourcep(); - if (srcp == defaultp) return; - m.opSelInto(MASK(srcp), vtxp->driverLo(i), srcp->width()); + vtxp->foreachDriver([&](DfgVertex& src, uint32_t lo) { + m.opSelInto(MASK(&src), lo, src.width()); + return false; }); } void visit(DfgVarPacked* vtxp) override { - if (DfgVertex* const srcp = vtxp->srcp()) MASK(vtxp) = MASK(srcp); + DfgVertex* const srcp = vtxp->srcp(); + if (srcp && srcp->is()) return; + + V3Number& m = MASK(vtxp); + DfgVertex* const defaultp = vtxp->defaultp(); + if (defaultp) m = MASK(defaultp); + if (!srcp) return; + + if (DfgSplicePacked* const splicep = srcp->cast()) { + splicep->foreachDriver([&](DfgVertex& src, uint32_t lo) { + m.opSelInto(MASK(&src), lo, src.width()); + return false; + }); + return; + } + + m = MASK(srcp); } void visit(DfgArraySel* vtxp) override { @@ -924,8 +939,9 @@ class IndependentBits final : public DfgVisitor { if (VN_IS(currp->dtypep(), UnpackArrayDType)) { // For an unpacked array vertex, just enque it's sinks. // (There can be no loops through arrays directly) - currp->forEachSink([&](DfgVertex& vtx) { + currp->foreachSink([&](DfgVertex& vtx) { if (vtx.getUser() == m_component) workList.emplace_back(&vtx); + return false; }); continue; } @@ -940,8 +956,9 @@ class IndependentBits final : public DfgVisitor { // If mask changed, enqueue sinks if (!prevMask.isCaseEq(maskCurr)) { - currp->forEachSink([&](DfgVertex& vtx) { + currp->foreachSink([&](DfgVertex& vtx) { if (vtx.getUser() == m_component) workList.emplace_back(&vtx); + return false; }); // Check the mask only ever contrects (no bit goes 0 -> 1) @@ -977,20 +994,21 @@ class FixUpSelDrivers final { static size_t fixUpSelSinks(DfgGraph& dfg, DfgVertex* vtxp) { size_t nImprovements = 0; const uint64_t component = vtxp->getUser(); - vtxp->forEachSink([&](DfgVertex& sink) { + vtxp->foreachSink([&](DfgVertex& sink) { // Ignore if sink is not part of same cycle - if (sink.getUser() != component) return; + if (sink.getUser() != component) return false; // Only handle Sel DfgSel* const selp = sink.cast(); - if (!selp) return; + if (!selp) return false; // Try to find the driver of the selected bits outside the cycle DfgVertex* const fixp = TraceDriver::apply(dfg, vtxp, selp->lsb(), selp->width(), false); - if (!fixp) return; + if (!fixp) return false; // Found an out-of-cycle driver. We can replace this sel with that. selp->replaceWith(fixp); selp->unlinkDelete(dfg); ++nImprovements; + return false; }); return nImprovements; } @@ -998,25 +1016,25 @@ class FixUpSelDrivers final { static size_t fixUpArraySelSinks(DfgGraph& dfg, DfgVertex* vtxp) { size_t nImprovements = 0; const uint64_t component = vtxp->getUser(); - vtxp->forEachSink([&](DfgVertex& sink) { + vtxp->foreachSink([&](DfgVertex& sink) { // Ignore if sink is not part of same cycle - if (sink.getUser() != component) return; + if (sink.getUser() != component) return false; // Only handle ArraySels DfgArraySel* const aselp = sink.cast(); - if (!aselp) return; + if (!aselp) return false; // First, try to fix up the whole word - DfgVertex* const fixp = TraceDriver::apply(dfg, aselp, 0, aselp->width(), false); - if (fixp) { + if (DfgVertex* const fixp = TraceDriver::apply(dfg, aselp, 0, aselp->width(), false)) { // Found an out-of-cycle driver for the whole ArraySel aselp->replaceWith(fixp); aselp->unlinkDelete(dfg); ++nImprovements; - } else { - // Attempt to fix up piece-wise at Sels applied to the ArraySel - nImprovements += fixUpSelSinks(dfg, aselp); - // Remove if became unused - if (!aselp->hasSinks()) aselp->unlinkDelete(dfg); + return false; } + // Attempt to fix up piece-wise at Sels applied to the ArraySel + nImprovements += fixUpSelSinks(dfg, aselp); + // Remove if became unused + if (!aselp->hasSinks()) aselp->unlinkDelete(dfg); + return false; }); return nImprovements; } @@ -1045,16 +1063,17 @@ class FixUpIndependentRanges final { // Returns a bitmask set if that bit of 'vtxp' is used (has a sink) static V3Number computeUsedBits(DfgVertex* vtxp) { V3Number result{vtxp->fileline(), static_cast(vtxp->width()), 0}; - vtxp->forEachSink([&result](DfgVertex& sink) { + vtxp->foreachSink([&result](DfgVertex& sink) { // If used via a Sel, mark the selected bits used if (const DfgSel* const selp = sink.cast()) { uint32_t lsb = selp->lsb(); uint32_t msb = lsb + selp->width() - 1; for (uint32_t i = lsb; i <= msb; ++i) result.setBit(i, '1'); - return; + return false; } // Used without a Sel, so all bits are used result.setAllBits1(); + return false; }); return result; } @@ -1097,7 +1116,7 @@ class FixUpIndependentRanges final { } // Fall back on using the part of the variable (if dependent, or trace failed) if (!termp) { - AstNodeDType* const dtypep = DfgGraph::dtypePacked(width); + AstNodeDType* const dtypep = V3Dfg::dtypePacked(width); DfgSel* const selp = new DfgSel{dfg, vtxp->fileline(), dtypep}; // Same component as 'vtxp', as reads 'vtxp' and will replace 'vtxp' selp->setUser(vtxp->getUser()); @@ -1155,7 +1174,7 @@ class FixUpIndependentRanges final { nImprovements += gatherTerms(termps, dfg, vtxp, indpBits, msb, lsb); } else { // The range is not used, just use constant 0 as a placeholder - DfgConst* const constp = new DfgConst{dfg, flp, msb - lsb + 1}; + DfgConst* const constp = new DfgConst{dfg, flp, msb - lsb + 1, 0}; constp->setUser(0); termps.emplace_back(constp); } @@ -1178,7 +1197,7 @@ class FixUpIndependentRanges final { for (size_t i = 1; i < termps.size(); ++i) { DfgVertex* const termp = termps[i]; const uint32_t catWidth = replacementp->width() + termp->width(); - AstNodeDType* const dtypep = DfgGraph::dtypePacked(catWidth); + AstNodeDType* const dtypep = V3Dfg::dtypePacked(catWidth); DfgConcat* const catp = new DfgConcat{dfg, flp, dtypep}; catp->rhsp(replacementp); catp->lhsp(termp); @@ -1220,17 +1239,18 @@ class FixUpIndependentRanges final { } else if (varp->is()) { // For array variables, fix up element-wise const uint64_t component = varp->getUser(); - varp->forEachSink([&](DfgVertex& sink) { + varp->foreachSink([&](DfgVertex& sink) { // Ignore if sink is not part of same cycle - if (sink.getUser() != component) return; + if (sink.getUser() != component) return false; // Only handle ArraySels with constant index DfgArraySel* const aselp = sink.cast(); - if (!aselp) return; - if (!aselp->bitp()->is()) return; + if (!aselp) return false; + if (!aselp->bitp()->is()) return false; // Fix up the word nImprovements += fixUpPacked(dfg, aselp); // Remove if became unused if (!aselp->hasSinks()) aselp->unlinkDelete(dfg); + return false; }); } diff --git a/src/V3DfgCache.h b/src/V3DfgCache.h index 44c773fd18d..4075b42e44b 100644 --- a/src/V3DfgCache.h +++ b/src/V3DfgCache.h @@ -230,19 +230,19 @@ inline void setOperands(DfgSel* vtxp, DfgVertex* fromp, uint32_t lsb) { } inline void setOperands(DfgVertexUnary* vtxp, DfgVertex* src0p) { // - vtxp->relinkSource<0>(src0p); + vtxp->inputp(0, src0p); } inline void setOperands(DfgVertexBinary* vtxp, DfgVertex* src0p, DfgVertex* src1p) { - vtxp->relinkSource<0>(src0p); - vtxp->relinkSource<1>(src1p); + vtxp->inputp(0, src0p); + vtxp->inputp(1, src1p); } inline void setOperands(DfgVertexTernary* vtxp, DfgVertex* src0p, DfgVertex* src1p, DfgVertex* src2p) { - vtxp->relinkSource<0>(src0p); - vtxp->relinkSource<1>(src1p); - vtxp->relinkSource<2>(src2p); + vtxp->inputp(0, src0p); + vtxp->inputp(1, src1p); + vtxp->inputp(2, src2p); } // Get or create (and insert) vertex with given operands @@ -265,19 +265,18 @@ inline void cache(CacheSel& cache, DfgSel* vtxp) { } inline void cache(CacheUnary& cache, DfgVertexUnary* vtxp) { - DfgVertexUnary*& entrypr = getEntry(cache, vtxp->dtypep(), vtxp->source<0>()); + DfgVertexUnary*& entrypr = getEntry(cache, vtxp->dtypep(), vtxp->inputp(0)); if (!entrypr) entrypr = vtxp; } inline void cache(CacheBinary& cache, DfgVertexBinary* vtxp) { - DfgVertexBinary*& entrypr - = getEntry(cache, vtxp->dtypep(), vtxp->source<0>(), vtxp->source<1>()); + DfgVertexBinary*& entrypr = getEntry(cache, vtxp->dtypep(), vtxp->inputp(0), vtxp->inputp(1)); if (!entrypr) entrypr = vtxp; } inline void cache(CacheTernary& cache, DfgVertexTernary* vtxp) { DfgVertexTernary*& entrypr - = getEntry(cache, vtxp->dtypep(), vtxp->source<0>(), vtxp->source<1>(), vtxp->source<2>()); + = getEntry(cache, vtxp->dtypep(), vtxp->inputp(0), vtxp->inputp(1), vtxp->inputp(2)); if (!entrypr) entrypr = vtxp; } @@ -288,18 +287,17 @@ inline void invalidateByValue(CacheSel& cache, const DfgSel* vtxp) { } inline void invalidateByValue(CacheUnary& cache, const DfgVertexUnary* vtxp) { - const auto it = find(cache, vtxp->dtypep(), vtxp->source<0>()); + const auto it = find(cache, vtxp->dtypep(), vtxp->inputp(0)); if (it != cache.end() && it->second == vtxp) cache.erase(it); } inline void invalidateByValue(CacheBinary& cache, const DfgVertexBinary* vtxp) { - const auto it = find(cache, vtxp->dtypep(), vtxp->source<0>(), vtxp->source<1>()); + const auto it = find(cache, vtxp->dtypep(), vtxp->inputp(0), vtxp->inputp(1)); if (it != cache.end() && it->second == vtxp) cache.erase(it); } inline void invalidateByValue(CacheTernary& cache, const DfgVertexTernary* vtxp) { - const auto it - = find(cache, vtxp->dtypep(), vtxp->source<0>(), vtxp->source<1>(), vtxp->source<2>()); + const auto it = find(cache, vtxp->dtypep(), vtxp->inputp(0), vtxp->inputp(1), vtxp->inputp(2)); if (it != cache.end() && it->second == vtxp) cache.erase(it); } diff --git a/src/V3DfgColorSCCs.cpp b/src/V3DfgColorSCCs.cpp index c43566f7631..6caa0b957ad 100644 --- a/src/V3DfgColorSCCs.cpp +++ b/src/V3DfgColorSCCs.cpp @@ -55,7 +55,7 @@ class ColorStronglyConnectedComponents final { const size_t rootIndex = vtxState.index = ++m_index; // Visit children - vtx.forEachSink([&](DfgVertex& child) { + vtx.foreachSink([&](DfgVertex& child) { VertexState& childSatate = child.user(); // If the child has not yet been visited, then continue traversal if (childSatate.index == UNASSIGNED) visitColorSCCs(child, childSatate); @@ -63,6 +63,7 @@ class ColorStronglyConnectedComponents final { if (childSatate.component == UNASSIGNED) { if (vtxState.index > childSatate.index) vtxState.index = childSatate.index; } + return false; }); if (vtxState.index == rootIndex) { @@ -73,7 +74,7 @@ class ColorStronglyConnectedComponents final { || m_stack.back()->getUser().index < rootIndex; // We also need a separate component for vertices that drive themselves (which can // happen for input like 'assign a = a'), as we want to extract them (they are cyclic). - const bool drivesSelf = vtx.findSink([&vtx](const DfgVertex& sink) { // + const bool drivesSelf = vtx.foreachSink([&](const DfgVertex& sink) { // return &vtx == &sink; }); @@ -107,7 +108,7 @@ class ColorStronglyConnectedComponents final { for (DfgVertexVar& vtx : m_dfg.varVertices()) { VertexState& vtxState = vtx.user(); // If it has no input or no outputs, it cannot be part of a non-trivial SCC. - if (vtx.arity() == 0 || !vtx.hasSinks()) { + if ((!vtx.srcp() && !vtx.defaultp()) || !vtx.hasSinks()) { UDEBUGONLY(UASSERT_OBJ(vtxState.index == UNASSIGNED || vtxState.component == 0, &vtx, "Non circular variable must be in a trivial SCC");); vtxState.index = 0; diff --git a/src/V3DfgDecomposition.cpp b/src/V3DfgDecomposition.cpp index 6f2aa82fb2b..c73d1b9799c 100644 --- a/src/V3DfgDecomposition.cpp +++ b/src/V3DfgDecomposition.cpp @@ -65,8 +65,14 @@ class SplitIntoComponents final { item.user() = m_componentCounter; // Enqueue all sources and sinks of this vertex. - item.forEachSource([&](DfgVertex& src) { queue.push_back(&src); }); - item.forEachSink([&](DfgVertex& dst) { queue.push_back(&dst); }); + item.foreachSource([&](DfgVertex& src) { + queue.push_back(&src); + return false; + }); + item.foreachSink([&](DfgVertex& dst) { + queue.push_back(&dst); + return false; + }); } while (!queue.empty()); // Done with this component @@ -118,21 +124,6 @@ std::vector> DfgGraph::splitIntoComponents(const std:: } class ExtractCyclicComponents final { - // TYPES - // We reuse the DfgVertex::user state set by V3DfgPasses::colorStronglyConnectedComponents. - // We sneak an extra flag into the MSB to indicate the vertex was merged already. - class VertexState final { - uint64_t& m_userr; - - public: - explicit VertexState(DfgVertex& vtx) - : m_userr{vtx.getUser()} {} - bool merged() const { return m_userr >> 63; } - void setMerged() { m_userr |= 1ULL << 63; } - uint64_t component() const { return m_userr & ~(1ULL << 63); } - void component(uint64_t value) { m_userr = (m_userr & (1ULL << 63)) | value; } - }; - // STATE DfgGraph& m_dfg; // The input graph const std::string m_prefix; // Component name prefix @@ -143,45 +134,86 @@ class ExtractCyclicComponents final { std::unordered_map> m_clones; // METHODS - void visitMergeSCCs(DfgVertex& vtx, uint64_t targetComponent) { - VertexState vtxState{vtx}; - - // Move on if already visited - if (vtxState.merged()) return; - - // Visiting vertex - vtxState.setMerged(); - - // Assign vertex to the target component - vtxState.component(targetComponent); + void addVertexAndExpandSiblings(DfgVertex& vtx, uint64_t component) { + // Do not go past a variable, we will partition the graph there + if (vtx.is()) return; + // Don't need to recurse if the vertex is already in the same component, + // it was either marked through an earlier traversal, in which case it + // was processed recursively, or it will be processed later. + if (vtx.getUser() == component) return; + // Because all cycles are through a variable, we can't reach another SCC. + UASSERT_OBJ(!vtx.getUser(), &vtx, "Cycle without variable involvement"); + // Put this vertex in the component, and continue recursively + vtx.setUser(component); + expandSiblings(vtx, component); + } - // Visit all neighbors. We stop at variable boundaries, - // which is where we will split the graphs - vtx.forEachSource([this, targetComponent](DfgVertex& other) { - if (other.is()) return; - visitMergeSCCs(other, targetComponent); + void expandSiblings(DfgVertex& vtx, uint64_t component) { + UASSERT_OBJ(vtx.getUser() == component, &vtx, "Traversal didn't stop"); + vtx.foreachSink([&](DfgVertex& v) { + addVertexAndExpandSiblings(v, component); + return false; }); - vtx.forEachSink([this, targetComponent](DfgVertex& other) { - if (other.is()) return; - visitMergeSCCs(other, targetComponent); + vtx.foreachSource([&](DfgVertex& v) { + addVertexAndExpandSiblings(v, component); + return false; }); } - void mergeSCCs() { - // Ensure that component boundaries are always at variables, by merging SCCs. Merging stops - // at variable boundaries, so we don't need to iterate variables. Constants are reachable - // from their sinks, or are unused, so we don't need to iterate them either. + void expandComponents() { + // Important fact that we will assume below: There are no path between + // any two SCCs that do not go through a variable before reaching the + // destination SCC. That is, to get from one SCC to another, you must + // go through a variable that is not part of the destination SCC. This + // holds because no operation vertex can have multiple sinks at this + // point (constants have no inputs, so they are not in an SCC). + if (m_doExpensiveChecks) { + for (DfgVertex& vtx : m_dfg.opVertices()) { + UASSERT_OBJ(!vtx.hasMultipleSinks(), &vtx, "Operation has multiple sinks"); + } + } + + // We will break the graph at variable boundaries, but we want both + // 'srcp', and 'defaultp' to be in the same component, so for each + // cyclic variable, put both its 'srcp' and 'defaultp' into the same + // component if they are not variables themselves. The assertions below + // must hold because of the assumption above. + for (DfgVertexVar& vtx : m_dfg.varVertices()) { + const uint64_t varComponent = vtx.getUser(); + if (!varComponent) continue; + if (DfgVertex* const srcp = vtx.srcp()) { + if (!srcp->is()) { + const uint64_t srcComponent = srcp->getUser(); + UASSERT_OBJ(!srcComponent || srcComponent == varComponent, srcp, + "Cycle through 'srcp' that does not go through variable."); + srcp->setUser(varComponent); + } + } + if (DfgVertex* const defp = vtx.defaultp()) { + if (!defp->is()) { + const uint64_t defComponent = defp->getUser(); + UASSERT_OBJ(!defComponent || defComponent == varComponent, defp, + "Cycle through 'defaultp' that does not go through variable"); + defp->setUser(varComponent); + } + } + } + + // To ensure all component boundaries are at variables, expand + // components to include all reachable non-variable vertices. Constants + // are reachable from their sinks, so only need to process op vertices. + // We do this by staring a DFS from each vertex that is part of an + // component and add all reachable non-variable vertices to the same. for (DfgVertex& vtx : m_dfg.opVertices()) { - // Start DFS from each vertex that is in a non-trivial SCC, and merge everything - // that is reachable from it into this component. - if (const uint64_t target = VertexState{vtx}.component()) visitMergeSCCs(vtx, target); + if (const uint64_t targetComponent = vtx.getUser()) { + expandSiblings(vtx, targetComponent); + } } } // Retrieve clone of vertex in the given component - DfgVertexVar& getClone(DfgVertexVar& vtx, uint64_t component) { - UASSERT_OBJ(VertexState{vtx}.component() != component, &vtx, - "Vertex is in that component"); + DfgVertexVar* getClone(DfgVertexVar& vtx, uint64_t component) { + UASSERT_OBJ(vtx.getUser() != component, &vtx, "Vertex is in that component"); DfgVertexVar*& clonep = m_clones[&vtx][component]; if (!clonep) { if (DfgVarPacked* const pVtxp = vtx.cast()) { @@ -201,40 +233,52 @@ class ExtractCyclicComponents final { clonep->setUser(component); clonep->tmpForp(vtx.tmpForp()); } - return *clonep; + return clonep; } // Fix edges that cross components void fixEdges(DfgVertexVar& vtx) { - const uint64_t component = VertexState{vtx}.component(); - - // Fix up sources in a different component - vtx.forEachSourceEdge([&](DfgEdge& edge, size_t) { - DfgVertex* const srcp = edge.sourcep(); - if (!srcp) return; - const uint64_t sourceComponent = VertexState{*srcp}.component(); - // Same component is OK - if (sourceComponent == component) return; - // Relink the source to write the clone - edge.unlinkSource(); - getClone(vtx, sourceComponent).srcp(srcp); + const uint64_t component = vtx.getUser(); + + // Fix up srcp and dstp (they must be the same component, or variable) + if (DfgVertex* const sp = vtx.srcp()) { + const uint64_t srcComponent = sp->getUser(); + if (srcComponent != component) { + UASSERT_OBJ(sp->is(), &vtx, "'srcp' in different component"); + getClone(vtx, srcComponent)->srcp(sp); + vtx.srcp(nullptr); + } + } + if (DfgVertex* const dp = vtx.defaultp()) { + const uint64_t defaultComponent = dp->getUser(); + if (defaultComponent != component) { + UASSERT_OBJ(dp->is(), &vtx, "'defaultp' in different component"); + getClone(vtx, defaultComponent)->defaultp(dp); + vtx.defaultp(nullptr); + } + } + // Fix up sinks in a different component to read the clone + std::vector sinkps; + vtx.foreachSink([&](DfgVertex& sink) { + sinkps.emplace_back(&sink); + return false; }); - - // Fix up sinks in a different component - vtx.forEachSinkEdge([&](DfgEdge& edge) { - const uint64_t sinkComponent = VertexState{*edge.sinkp()}.component(); + for (DfgVertex* const sinkp : sinkps) { + const uint64_t sinkComponent = sinkp->getUser(); // Same component is OK - if (sinkComponent == component) return; - // Relink the sink to read the clone - edge.relinkSource(&getClone(vtx, sinkComponent)); - }); + if (sinkComponent == component) continue; + DfgVertex* const clonep = getClone(vtx, sinkComponent); + for (size_t i = 0; i < sinkp->nInputs(); ++i) { + if (sinkp->inputp(i) == &vtx) sinkp->inputp(i, clonep); + } + } } template void moveVertices(DfgVertex::List& list) { for (DfgVertex* const vtxp : list.unlinkable()) { DfgVertex& vtx = *vtxp; - if (const uint64_t component = VertexState{vtx}.component()) { + if (const uint64_t component = vtx.getUser()) { m_dfg.removeVertex(vtx); m_components[component - 1]->addVertex(vtx); } @@ -242,20 +286,15 @@ class ExtractCyclicComponents final { } void checkEdges(DfgGraph& dfg) const { - // Check that: - // - Edges only cross components at variable boundaries - // - Variable vertex sources are all connected. + // Check that edges only cross components at variable boundaries dfg.forEachVertex([&](DfgVertex& vtx) { - const uint64_t component = VertexState{vtx}.component(); - vtx.forEachSource([&](DfgVertex& src) { - if (src.is()) return; // OK to cross at variables - UASSERT_OBJ(component == VertexState{src}.component(), &vtx, - "Edge crossing components without variable involvement"); - }); - vtx.forEachSink([&](DfgVertex& snk) { - if (snk.is()) return; // OK to cross at variables - UASSERT_OBJ(component == VertexState{snk}.component(), &vtx, + if (vtx.is()) return; + const uint64_t component = vtx.getUser(); + vtx.foreachSink([&](DfgVertex& snk) { + if (snk.is()) return false; // OK to cross at variables + UASSERT_OBJ(component == snk.getUser(), &vtx, "Edge crossing components without variable involvement"); + return false; }); }); } @@ -267,11 +306,13 @@ class ExtractCyclicComponents final { // Check that each edge connects to a vertex that is within the same graph dfg.forEachVertex([&](const DfgVertex& vtx) { - vtx.forEachSource([&](const DfgVertex& src) { + vtx.foreachSource([&](const DfgVertex& src) { UASSERT_OBJ(vertices.count(&src), &vtx, "Source vertex not in graph"); + return false; }); - vtx.forEachSink([&](const DfgVertex& snk) { + vtx.foreachSink([&](const DfgVertex& snk) { UASSERT_OBJ(vertices.count(&snk), &snk, "Sink vertex not in graph"); + return false; }); }); } @@ -319,14 +360,13 @@ class ExtractCyclicComponents final { : m_dfg{dfg} , m_prefix{dfg.name() + (label.empty() ? "" : "-") + label + "-component-"} { // DfgVertex::user is set to the SCC number by colorStronglyConnectedComponents, - // Then we use VertexState to handle the MSB as an extra flag. const auto userDataInUse = dfg.userDataInUse(); // Find all the non-trivial SCCs (and trivial cycles) in the graph const uint32_t numNonTrivialSCCs = V3DfgPasses::colorStronglyConnectedComponents(dfg); // If the graph was acyclic (which should be the common case), then we are done. if (!numNonTrivialSCCs) return; - // Ensure that component boundaries are always at variables, by merging SCCs - mergeSCCs(); + // Ensure that component boundaries are always at variables, by expanding SCCs + expandComponents(); // Extract the components extractComponents(numNonTrivialSCCs); } diff --git a/src/V3DfgDfgToAst.cpp b/src/V3DfgDfgToAst.cpp index 3894534b6f0..63d1f3c1483 100644 --- a/src/V3DfgDfgToAst.cpp +++ b/src/V3DfgDfgToAst.cpp @@ -92,32 +92,23 @@ class DfgToAstVisitor final : DfgVisitor { const VNUser2InUse m_user2InUse; // TYPES - using VariableType = std::conditional_t; - struct Assignment final { - FileLine* m_flp; - AstNodeExpr* m_lhsp; - AstNodeExpr* m_rhsp; - Assignment() = delete; - Assignment(FileLine* flp, AstNodeExpr* lhsp, AstNodeExpr* m_rhsp) - : m_flp{flp} - , m_lhsp{lhsp} - , m_rhsp{m_rhsp} {} - }; + using Variable = std::conditional_t; + using Container = std::conditional_t; // STATE AstModule* const m_modp; // The parent/result module - This is nullptr when T_Scoped V3DfgDfgToAstContext& m_ctx; // The context for stats AstNodeExpr* m_resultp = nullptr; // The result node of the current traversal - std::vector m_assignments; // Assignments to currently rendered variable - std::vector m_defaults; // Default assignments to currently rendered variable + AstAlways* m_alwaysp = nullptr; // Process to add assignments to, if have a default driver + Container* m_containerp = nullptr; // The AstNodeModule or AstActive to insert assigns into // METHODS - static VariableType* getNode(const DfgVertexVar* vtxp) { + static Variable* getNode(const DfgVertexVar* vtxp) { if VL_CONSTEXPR_CXX17 (T_Scoped) { - return reinterpret_cast(vtxp->varScopep()); + return reinterpret_cast(vtxp->varScopep()); } else { - return reinterpret_cast(vtxp->varp()); + return reinterpret_cast(vtxp->varp()); } } @@ -158,49 +149,57 @@ class DfgToAstVisitor final : DfgVisitor { return resultp; } - void convertDriver(std::vector& assignments, FileLine* flp, AstNodeExpr* lhsp, - DfgVertex* driverp) { + void createAssignment(FileLine* flp, AstNodeExpr* lhsp, DfgVertex* driverp) { + // Keep track of statisticss + ++m_ctx.m_resultEquations; + // Render the driver + AstNodeExpr* const rhsp = convertDfgVertexToAstNodeExpr(driverp); + // Update LHS locations to reflect the location of the original driver + lhsp->foreach([&](AstNode* nodep) { nodep->fileline(flp); }); + + // If using a process, add Assign there + if (m_alwaysp) { + m_alwaysp->addStmtsp(new AstAssign{flp, lhsp, rhsp}); + return; + } + + // Otherwise create an AssignW + m_containerp->addStmtsp(new AstAssignW{flp, lhsp, rhsp}); + } + + void convertDriver(FileLine* flp, AstNodeExpr* lhsp, DfgVertex* driverp) { if (DfgSplicePacked* const sPackedp = driverp->cast()) { - // Render defaults first - if (DfgVertex* const defaultp = sPackedp->defaultp()) { - convertDriver(m_defaults, flp, lhsp, defaultp); - } - // Render partial assignments of packed value - sPackedp->forEachSourceEdge([&](const DfgEdge& edge, size_t i) { - DfgVertex* const srcp = edge.sourcep(); - if (srcp == sPackedp->defaultp()) return; + // Partial assignment of packed value + sPackedp->foreachDriver([&](DfgVertex& src, uint32_t lo, FileLine* dflp) { // Create Sel - FileLine* const dflp = sPackedp->driverFileLine(i); - AstConst* const lsbp = new AstConst{dflp, sPackedp->driverLo(i)}; - const int width = static_cast(srcp->width()); + AstConst* const lsbp = new AstConst{dflp, lo}; + const int width = static_cast(src.width()); AstSel* const nLhsp = new AstSel{dflp, lhsp->cloneTreePure(false), lsbp, width}; // Convert source - convertDriver(assignments, dflp, nLhsp, srcp); + convertDriver(dflp, nLhsp, &src); // Delete Sel - was cloned VL_DO_DANGLING(nLhsp->deleteTree(), nLhsp); + return false; }); return; } if (DfgSpliceArray* const sArrayp = driverp->cast()) { - UASSERT_OBJ(!sArrayp->defaultp(), flp, "Should not have a default assignment yet"); // Partial assignment of array variable - sArrayp->forEachSourceEdge([&](const DfgEdge& edge, size_t i) { - DfgVertex* const driverp = edge.sourcep(); - UASSERT_OBJ(driverp, sArrayp, "Should have removed undriven sources"); - UASSERT_OBJ(driverp->size() == 1, driverp, "We only handle single elements"); + sArrayp->foreachDriver([&](DfgVertex& src, uint32_t lo, FileLine* dflp) { + UASSERT_OBJ(src.size() == 1, &src, "We only handle single elements"); // Create ArraySel - FileLine* const dflp = sArrayp->driverFileLine(i); - AstConst* const idxp = new AstConst{dflp, sArrayp->driverLo(i)}; + AstConst* const idxp = new AstConst{dflp, lo}; AstArraySel* const nLhsp = new AstArraySel{dflp, lhsp->cloneTreePure(false), idxp}; // Convert source - if (const DfgUnitArray* const uap = driverp->cast()) { - convertDriver(assignments, dflp, nLhsp, uap->srcp()); + if (const DfgUnitArray* const uap = src.cast()) { + convertDriver(dflp, nLhsp, uap->srcp()); } else { - convertDriver(assignments, dflp, nLhsp, driverp); + convertDriver(dflp, nLhsp, &src); } // Delete ArraySel - was cloned VL_DO_DANGLING(nLhsp->deleteTree(), nLhsp); + return false; }); return; } @@ -210,17 +209,14 @@ class DfgToAstVisitor final : DfgVisitor { AstConst* const idxp = new AstConst{flp, 0}; AstArraySel* const nLhsp = new AstArraySel{flp, lhsp->cloneTreePure(false), idxp}; // Convert source - convertDriver(assignments, flp, nLhsp, uap->srcp()); + convertDriver(flp, nLhsp, uap->srcp()); // Delete ArraySel - was cloned VL_DO_DANGLING(nLhsp->deleteTree(), nLhsp); return; } // Base case: assign vertex to current lhs - AstNodeExpr* const rhsp = convertDfgVertexToAstNodeExpr(driverp); - assignments.emplace_back(flp, lhsp->cloneTreePure(false), rhsp); - ++m_ctx.m_resultEquations; - return; + createAssignment(flp, lhsp->cloneTreePure(false), driverp); } // VISITORS @@ -258,7 +254,7 @@ class DfgToAstVisitor final : DfgVisitor { #include "V3Dfg__gen_dfg_to_ast.h" // Constructor - explicit DfgToAstVisitor(DfgGraph& dfg, V3DfgDfgToAstContext& ctx) + DfgToAstVisitor(DfgGraph& dfg, V3DfgDfgToAstContext& ctx) : m_modp{dfg.modulep()} , m_ctx{ctx} { // Convert the graph back to combinational assignments @@ -266,55 +262,42 @@ class DfgToAstVisitor final : DfgVisitor { // The graph must have been regularized, so we only need to render assignments for (DfgVertexVar& vtx : dfg.varVertices()) { // If there is no driver (this vertex is an input to the graph), then nothing to do. - if (!vtx.srcp()) continue; + if (!vtx.srcp()) { + UASSERT_OBJ(!vtx.defaultp(), &vtx, "Only default driver on variable"); + continue; + } ++m_ctx.m_outputVariables; // Render variable assignments FileLine* const flp = vtx.driverFileLine() ? vtx.driverFileLine() : vtx.fileline(); AstVarRef* const lhsp = new AstVarRef{flp, getNode(&vtx), VAccess::WRITE}; - convertDriver(m_assignments, flp, lhsp, vtx.srcp()); - // convetDriver always clones lhsp - VL_DO_DANGLING(lhsp->deleteTree(), lhsp); - if (m_defaults.empty()) { - // If there are no default assignments, render each driver as an AssignW - for (const Assignment& a : m_assignments) { - AstAssignW* const assignp = new AstAssignW{a.m_flp, a.m_lhsp, a.m_rhsp}; - a.m_lhsp->foreach([&a](AstNode* nodep) { nodep->fileline(a.m_flp); }); - if VL_CONSTEXPR_CXX17 (T_Scoped) { - // Add it to the scope holding the target variable - getCombActive(vtx.varScopep()->scopep())->addStmtsp(assignp); - } else { - // Add it to the parent module of the DfgGraph - m_modp->addStmtsp(assignp); - } - } + VL_RESTORER(m_containerp); + if VL_CONSTEXPR_CXX17 (T_Scoped) { + // Add it to the scope holding the target variable + AstActive* const activep = getCombActive(vtx.varScopep()->scopep()); + m_containerp = reinterpret_cast(activep); } else { + // Add it to the parent module of the DfgGraph + m_containerp = reinterpret_cast(m_modp); + } + + // If there is a default value, render all drivers under an AstAlways + VL_RESTORER(m_alwaysp); + if (DfgVertex* const defaultp = vtx.defaultp()) { ++m_ctx.m_outputVariablesWithDefault; - // If there are default assignments, render all drivers under an AstAlways - AstAlways* const alwaysp - = new AstAlways{vtx.fileline(), VAlwaysKwd::ALWAYS_COMB, nullptr, nullptr}; - if VL_CONSTEXPR_CXX17 (T_Scoped) { - // Add it to the scope holding the target variable - getCombActive(vtx.varScopep()->scopep())->addStmtsp(alwaysp); - } else { - // Add it to the parent module of the DfgGraph - m_modp->addStmtsp(alwaysp); - } - for (const Assignment& a : m_defaults) { - AstAssign* const assignp = new AstAssign{a.m_flp, a.m_lhsp, a.m_rhsp}; - a.m_lhsp->foreach([&a](AstNode* nodep) { nodep->fileline(a.m_flp); }); - alwaysp->addStmtsp(assignp); - } - for (const Assignment& a : m_assignments) { - AstAssign* const assignp = new AstAssign{a.m_flp, a.m_lhsp, a.m_rhsp}; - a.m_lhsp->foreach([&a](AstNode* nodep) { nodep->fileline(a.m_flp); }); - alwaysp->addStmtsp(assignp); - } + m_alwaysp = new AstAlways{vtx.fileline(), VAlwaysKwd::ALWAYS_COMB, nullptr}; + m_containerp->addStmtsp(m_alwaysp); + // The default assignment needs to go first + createAssignment(vtx.fileline(), lhsp->cloneTreePure(false), defaultp); } - m_assignments.clear(); - m_defaults.clear(); + + // Render the drivers + convertDriver(flp, lhsp, vtx.srcp()); + + // convetDriver always clones lhsp + VL_DO_DANGLING(lhsp->deleteTree(), lhsp); } } diff --git a/src/V3DfgOptimizer.cpp b/src/V3DfgOptimizer.cpp index 451a7884191..e435775b05e 100644 --- a/src/V3DfgOptimizer.cpp +++ b/src/V3DfgOptimizer.cpp @@ -324,7 +324,7 @@ class DataflowOptimize final { // Mark interfaces that might be referenced by a virtual interface if (v3Global.hasVirtIfaces()) { - netlistp->typeTablep()->foreach([](AstIfaceRefDType* nodep) { + netlistp->typeTablep()->foreach([](const AstIfaceRefDType* nodep) { if (!nodep->isVirtual()) return; nodep->ifaceViaCellp()->setHasVirtualRef(); }); diff --git a/src/V3DfgPasses.cpp b/src/V3DfgPasses.cpp index 005e6e66bbc..72f882ad325 100644 --- a/src/V3DfgPasses.cpp +++ b/src/V3DfgPasses.cpp @@ -84,8 +84,7 @@ void V3DfgPasses::inlineVars(DfgGraph& dfg) { for (DfgVertexVar& vtx : dfg.varVertices()) { if (DfgVarPacked* const varp = vtx.cast()) { if (varp->hasSinks() && varp->isDrivenFullyByDfg()) { - DfgVertex* const driverp = varp->srcp(); - varp->forEachSinkEdge([=](DfgEdge& edge) { edge.relinkSource(driverp); }); + varp->replaceWith(varp->srcp()); } } } @@ -148,16 +147,17 @@ void V3DfgPasses::removeUnused(DfgGraph& dfg) { if (varp->hasDfgRefs()) continue; } // Add sources of unused vertex to work list - vtxp->forEachSource([&](DfgVertex& src) { + vtxp->foreachSource([&](DfgVertex& src) { // We only remove actual operation vertices and synthesis temporaries in this loop - if (src.is()) return; + if (src.is()) return false; const DfgVertexVar* const varp = src.cast(); - if (varp && !varp->tmpForp()) return; + if (varp && !varp->tmpForp()) return false; // If already in work list then nothing to do - if (src.getUser()) return; + if (src.getUser()) return false; // Actually add to work list. src.setUser(workListp); workListp = &src; + return false; }); // Remove the unused vertex vtxp->unlinkDelete(dfg); @@ -214,10 +214,13 @@ void V3DfgPasses::binToOneHot(DfgGraph& dfg, V3DfgBinToOneHotContext& ctx) { if (DfgVertex* const sinkp = vtxp->singleSink()) { if (sinkp->is()) return useOk(sinkp, !inv); } - return !vtxp->findSink([vtxp, inv](const DfgCond& sink) { - if (sink.condp() != vtxp) return false; - return inv ? sink.thenp()->is() : sink.elsep()->is(); + const bool condTree = vtxp->foreachSink([&](const DfgVertex& sink) { + const DfgCond* const condp = sink.cast(); + if (!condp) return false; + if (condp->condp() != vtxp) return false; + return inv ? condp->thenp()->is() : condp->elsep()->is(); }); + return !condTree; }; // Look at all comparison nodes and build the 'Val2Terms' map for each source vertex @@ -306,7 +309,7 @@ void V3DfgPasses::binToOneHot(DfgGraph& dfg, V3DfgBinToOneHotContext& ctx) { // Required data types AstNodeDType* const idxDTypep = srcp->dtypep(); - AstNodeDType* const bitDTypep = DfgGraph::dtypePacked(1); + AstNodeDType* const bitDTypep = V3Dfg::dtypePacked(1); AstUnpackArrayDType* const tabDTypep = new AstUnpackArrayDType{ flp, bitDTypep, new AstRange{flp, static_cast(nBits - 1), 0}}; v3Global.rootp()->typeTablep()->addTypesp(tabDTypep); @@ -438,10 +441,11 @@ void V3DfgPasses::eliminateVars(DfgGraph& dfg, V3DfgEliminateVarsContext& ctx) { const auto addToWorkList = [&](DfgVertex& vtx) { // If already in work list then nothing to do DfgVertex*& nextInWorklistp = vtx.user(); - if (nextInWorklistp) return; + if (nextInWorklistp) return false; // Actually add to work list. nextInWorklistp = workListp; workListp = &vtx; + return false; }; // List of variables (AstVar or AstVarScope) we are replacing @@ -467,7 +471,7 @@ void V3DfgPasses::eliminateVars(DfgGraph& dfg, V3DfgEliminateVarsContext& ctx) { // Remove unused non-variable vertices if (!vtxp->is() && !vtxp->hasSinks()) { // Add sources of removed vertex to work list - vtxp->forEachSource(addToWorkList); + vtxp->foreachSource(addToWorkList); // Remove the unused vertex vtxp->unlinkDelete(dfg); continue; @@ -517,7 +521,7 @@ void V3DfgPasses::eliminateVars(DfgGraph& dfg, V3DfgEliminateVarsContext& ctx) { } // Add sources of redundant variable to the work list - vtxp->forEachSource(addToWorkList); + vtxp->foreachSource(addToWorkList); // Remove the redundant variable vtxp->unlinkDelete(dfg); } diff --git a/src/V3DfgPatternStats.h b/src/V3DfgPatternStats.h index d9597d00b70..666c5bcb682 100644 --- a/src/V3DfgPatternStats.h +++ b/src/V3DfgPatternStats.h @@ -118,9 +118,10 @@ class V3DfgPatternStats final { } // Operands - vtx.forEachSource([&](const DfgVertex& src) { + vtx.foreachSource([&](const DfgVertex& src) { ss << ' '; if (render(ss, src, depth - 1)) deep = true; + return false; }); // S-expression end ss << ')'; diff --git a/src/V3DfgPeephole.cpp b/src/V3DfgPeephole.cpp index 96c85791133..4af6f06c8e5 100644 --- a/src/V3DfgPeephole.cpp +++ b/src/V3DfgPeephole.cpp @@ -131,7 +131,7 @@ class V3DfgPeephole final : public DfgVisitor { // STATE DfgGraph& m_dfg; // The DfgGraph being visited V3DfgPeepholeContext& m_ctx; // The config structure - AstNodeDType* const m_bitDType = DfgGraph::dtypePacked(1); // Common, so grab it up front + AstNodeDType* const m_bitDType = V3Dfg::dtypePacked(1); // Common, so grab it up front // Head of work list. Note that we want all next pointers in the list to be non-zero (including // that of the last element). This allows as to do two important things: detect if an element // is in the list by checking for a non-zero next pointer, and easy prefetching without @@ -163,11 +163,17 @@ class V3DfgPeephole final : public DfgVisitor { } void addSourcesToWorkList(DfgVertex* vtxp) { - vtxp->forEachSource([&](DfgVertex& src) { addToWorkList(&src); }); + vtxp->foreachSource([&](DfgVertex& src) { + addToWorkList(&src); + return false; + }); } void addSinksToWorkList(DfgVertex* vtxp) { - vtxp->forEachSink([&](DfgVertex& src) { addToWorkList(&src); }); + vtxp->foreachSink([&](DfgVertex& src) { + addToWorkList(&src); + return false; + }); } void deleteVertex(DfgVertex* vtxp) { @@ -179,8 +185,6 @@ class V3DfgPeephole final : public DfgVisitor { // Otherwise we can delete it now. // Remove from cache m_cache.invalidateByValue(vtxp); - // Unlink source edges - vtxp->forEachSourceEdge([](DfgEdge& edge, size_t) { edge.unlinkSource(); }); // Should not have sinks UASSERT_OBJ(!vtxp->hasSinks(), vtxp, "Should not delete used vertex"); // @@ -197,21 +201,29 @@ class V3DfgPeephole final : public DfgVisitor { // Add replacement to the work list addToWorkList(replacementp); // Replace vertex with the replacement - vtxp->forEachSink([&](DfgVertex& sink) { m_cache.invalidateByValue(&sink); }); + vtxp->foreachSink([&](DfgVertex& sink) { + m_cache.invalidateByValue(&sink); + return false; + }); vtxp->replaceWith(replacementp); - replacementp->forEachSink([&](DfgVertex& sink) { m_cache.cache(&sink); }); + replacementp->foreachSink([&](DfgVertex& sink) { + m_cache.cache(&sink); + return false; + }); // Vertex is now unused, so delete it deleteVertex(vtxp); } // Shorthand - static AstNodeDType* dtypePacked(uint32_t width) { return DfgGraph::dtypePacked(width); } + static AstNodeDType* dtypePacked(uint32_t width) { return V3Dfg::dtypePacked(width); } // Create a 32-bit DfgConst vertex DfgConst* makeI32(FileLine* flp, uint32_t val) { return new DfgConst{m_dfg, flp, 32, val}; } // Create a DfgConst vertex with the given width and value zero - DfgConst* makeZero(FileLine* flp, uint32_t width) { return new DfgConst{m_dfg, flp, width}; } + DfgConst* makeZero(FileLine* flp, uint32_t width) { + return new DfgConst{m_dfg, flp, width, 0}; + } // Create a new vertex of the given type template @@ -246,6 +258,16 @@ class V3DfgPeephole final : public DfgVisitor { return aConstp->num().isCaseEq(bConstp->num()); } + static bool isZero(const DfgVertex* vtxp) { + if (const DfgConst* const constp = vtxp->cast()) return constp->isZero(); + return false; + } + + static bool isOnes(const DfgVertex* vtxp) { + if (const DfgConst* const constp = vtxp->cast()) return constp->isOnes(); + return false; + } + // Note: If any of the following transformers return true, then the vertex was replaced and the // caller must not do any further changes, so the caller must check the return value, otherwise // there will be hard to debug issues. @@ -271,8 +293,8 @@ class V3DfgPeephole final : public DfgVisitor { VL_ATTR_WARN_UNUSED_RESULT bool foldBinary(Vertex* vtxp) { static_assert(std::is_base_of::value, "Must invoke on binary"); static_assert(std::is_final::value, "Must invoke on final class"); - if (DfgConst* const lhsp = vtxp->lhsp()->template cast()) { - if (DfgConst* const rhsp = vtxp->rhsp()->template cast()) { + if (DfgConst* const lhsp = vtxp->inputp(0)->template cast()) { + if (DfgConst* const rhsp = vtxp->inputp(1)->template cast()) { APPLYING(FOLD_BINARY) { DfgConst* const resultp = makeZero(vtxp->fileline(), vtxp->width()); foldOp(resultp->num(), lhsp->num(), rhsp->num()); @@ -642,7 +664,7 @@ class V3DfgPeephole final : public DfgVisitor { static_assert(std::is_base_of::value, "Must invoke on binary"); static_assert(std::is_final::value, "Must invoke on final class"); if (const DfgConcat* const concatp = vtxp->rhsp()->template cast()) { - if (concatp->lhsp()->isZero()) { // Drop redundant zero extension + if (isZero(concatp->lhsp())) { // Drop redundant zero extension APPLYING(REMOVE_REDUNDANT_ZEXT_ON_RHS_OF_SHIFT) { Shift* const replacementp = make(vtxp, vtxp->lhsp(), concatp->rhsp()); replace(vtxp, replacementp); @@ -919,27 +941,25 @@ class V3DfgPeephole final : public DfgVisitor { // Must be a splice, otherwise it would have been inlined DfgSplicePacked* const splicep = varp->srcp()->as(); - const auto pair = splicep->sourceEdges(); - for (size_t i = 0; i < pair.second; ++i) { - DfgVertex* const driverp = pair.first[i].sourcep(); - // Ignore default, we won't select into that for now ... - if (driverp == splicep->defaultp()) continue; - - const uint32_t dLsb = splicep->driverLo(i); - const uint32_t dMsb = dLsb + driverp->width() - 1; + DfgSel* replacementp = nullptr; + splicep->foreachDriver([&](DfgVertex& src, const uint32_t dLsb) { + const uint32_t dMsb = dLsb + src.width() - 1; // If it does not cover the whole searched bit range, move on - if (lsb < dLsb || dMsb < msb) continue; + if (lsb < dLsb || dMsb < msb) return false; + // Replace with sel from driver + replacementp = make(vtxp, &src, lsb - dLsb); + return true; + }); + if (replacementp) { // Replace with sel from driver APPLYING(PUSH_SEL_THROUGH_SPLICE) { - DfgSel* const replacementp = make(vtxp, driverp, lsb - dLsb); replace(vtxp, replacementp); // Special case just for this pattern: delete temporary if became unsued if (!varp->hasSinks() && !varp->hasDfgRefs()) { addToWorkList(splicep); // So it can be delete itself if unused VL_DO_DANGLING(varp->unlinkDelete(m_dfg), varp); // Delete it } - return; } } } @@ -1086,7 +1106,7 @@ class V3DfgPeephole final : public DfgVisitor { if (DfgConcat* const lhsConcatp = lhsp->cast()) { if (DfgConcat* const rhsConcatp = rhsp->cast()) { if (lhsConcatp->lhsp()->dtypep() == rhsConcatp->lhsp()->dtypep()) { - if (lhsConcatp->lhsp()->isZero() && rhsConcatp->rhsp()->isZero()) { + if (isZero(lhsConcatp->lhsp()) && isZero(rhsConcatp->rhsp())) { APPLYING(REPLACE_OR_OF_CONCAT_ZERO_LHS_AND_CONCAT_RHS_ZERO) { DfgConcat* const replacementp = make(vtxp, rhsConcatp->lhsp(), lhsConcatp->rhsp()); @@ -1094,7 +1114,7 @@ class V3DfgPeephole final : public DfgVisitor { return; } } - if (lhsConcatp->rhsp()->isZero() && rhsConcatp->lhsp()->isZero()) { + if (isZero(lhsConcatp->rhsp()) && isZero(rhsConcatp->lhsp())) { APPLYING(REPLACE_OR_OF_CONCAT_LHS_ZERO_AND_CONCAT_ZERO_RHS) { DfgConcat* const replacementp = make(vtxp, lhsConcatp->lhsp(), rhsConcatp->rhsp()); @@ -1261,7 +1281,7 @@ class V3DfgPeephole final : public DfgVisitor { FileLine* const flp = vtxp->fileline(); - if (lhsp->isZero()) { + if (isZero(lhsp)) { DfgConst* const lConstp = lhsp->as(); if (DfgSel* const rSelp = rhsp->cast()) { if (vtxp->dtypep() == rSelp->fromp()->dtypep() @@ -1276,7 +1296,7 @@ class V3DfgPeephole final : public DfgVisitor { } } - if (rhsp->isZero()) { + if (isZero(rhsp)) { DfgConst* const rConstp = rhsp->as(); if (DfgSel* const lSelp = lhsp->cast()) { if (vtxp->dtypep() == lSelp->fromp()->dtypep() && lSelp->lsb() == 0) { @@ -1561,14 +1581,14 @@ class V3DfgPeephole final : public DfgVisitor { if (condp->dtypep() != m_bitDType) return; - if (condp->isOnes()) { + if (isOnes(condp)) { APPLYING(REMOVE_COND_WITH_TRUE_CONDITION) { replace(vtxp, thenp); return; } } - if (condp->isZero()) { + if (isZero(condp)) { APPLYING(REMOVE_COND_WITH_FALSE_CONDITION) { replace(vtxp, elsep); return; @@ -1689,7 +1709,7 @@ class V3DfgPeephole final : public DfgVisitor { } if (vtxp->dtypep() == m_bitDType) { - if (thenp->isZero()) { // a ? 0 : b becomes ~a & b + if (isZero(thenp)) { // a ? 0 : b becomes ~a & b APPLYING(REPLACE_COND_WITH_THEN_BRANCH_ZERO) { DfgNot* const notp = make(vtxp, condp); DfgAnd* const repalcementp = make(vtxp, notp, elsep); @@ -1704,21 +1724,21 @@ class V3DfgPeephole final : public DfgVisitor { return; } } - if (thenp->isOnes()) { // a ? 1 : b becomes a | b + if (isOnes(thenp)) { // a ? 1 : b becomes a | b APPLYING(REPLACE_COND_WITH_THEN_BRANCH_ONES) { DfgOr* const repalcementp = make(vtxp, condp, elsep); replace(vtxp, repalcementp); return; } } - if (elsep->isZero()) { // a ? b : 0 becomes a & b + if (isZero(elsep)) { // a ? b : 0 becomes a & b APPLYING(REPLACE_COND_WITH_ELSE_BRANCH_ZERO) { DfgAnd* const repalcementp = make(vtxp, condp, thenp); replace(vtxp, repalcementp); return; } } - if (elsep->isOnes()) { // a ? b : 1 becomes ~a | b + if (isOnes(elsep)) { // a ? b : 1 becomes ~a | b APPLYING(REPLACE_COND_WITH_ELSE_BRANCH_ONES) { DfgNot* const notp = make(vtxp, condp); DfgOr* const repalcementp = make(vtxp, notp, thenp); diff --git a/src/V3DfgRegularize.cpp b/src/V3DfgRegularize.cpp index e050e8dc8d4..07bab617396 100644 --- a/src/V3DfgRegularize.cpp +++ b/src/V3DfgRegularize.cpp @@ -63,7 +63,7 @@ class DfgRegularize final { // This is an op that requires a result variable. Ensure it is // assigned to one, and redirect other sinks read that variable. if (DfgVertexVar* const varp = vtx.getResultVar()) { - varp->sourceEdge<0>()->unlinkSource(); + varp->srcp(nullptr); vtx.replaceWith(varp); varp->srcp(&vtx); } else { diff --git a/src/V3DfgSynthesize.cpp b/src/V3DfgSynthesize.cpp index e36a4e91e30..16d3badadd9 100644 --- a/src/V3DfgSynthesize.cpp +++ b/src/V3DfgSynthesize.cpp @@ -39,7 +39,7 @@ namespace { // automatically. For the few special cases, we provide specializations below template T_Vertex* makeVertex(const T_Node* nodep, DfgGraph& dfg) { - return new T_Vertex{dfg, nodep->fileline(), DfgGraph::toDfgDType(nodep->dtypep())}; + return new T_Vertex{dfg, nodep->fileline(), V3Dfg::toDfgDType(nodep->dtypep())}; } template <> @@ -48,7 +48,7 @@ DfgArraySel* makeVertex(const AstArraySel* nodep, DfgG // See t_bitsel_wire_array_bad if (VN_IS(nodep->fromp(), Const)) return nullptr; if (!VN_IS(nodep->fromp()->dtypep()->skipRefp(), UnpackArrayDType)) return nullptr; - return new DfgArraySel{dfg, nodep->fileline(), DfgGraph::toDfgDType(nodep->dtypep())}; + return new DfgArraySel{dfg, nodep->fileline(), V3Dfg::toDfgDType(nodep->dtypep())}; } } // namespace @@ -77,6 +77,8 @@ class AstToDfgConverter final : public VNVisitor { bool m_foundUnhandled = false; // Found node not implemented as DFG or not implemented 'visit' bool m_converting = false; // We are trying to convert some logic at the moment + size_t m_nUnpack = 0; // Sequence numbers for temporaries + // METHODS static Variable* getTarget(const AstVarRef* refp) { // TODO: remove the useless reinterpret_casts when C++17 'if constexpr' actually works @@ -107,7 +109,7 @@ class AstToDfgConverter final : public VNVisitor { ++m_ctx.m_conv.nonRepImpure; } // Check node has supported dtype - if (!DfgGraph::isSupported(nodep->dtypep())) { + if (!V3Dfg::isSupported(nodep->dtypep())) { m_foundUnhandled = true; ++m_ctx.m_conv.nonRepDType; } @@ -119,7 +121,7 @@ class AstToDfgConverter final : public VNVisitor { // Cannot represent cross module references if (nodep->classOrPackagep()) return false; // Check target - return DfgGraph::isSupported(getTarget(nodep)); + return V3Dfg::isSupported(getTarget(nodep)); } // Given an RValue expression, return the equivalent Vertex, or nullptr if not representable. @@ -163,7 +165,7 @@ class AstToDfgConverter final : public VNVisitor { } // Create new one - DfgVertexVar* const newp = createTmp(m_dfg, *m_logicp, tgtp, "SynthAssign"); + DfgVertexVar* const newp = createTmp(*m_logicp, tgtp, "SynthAssign"); m_updatesp->emplace_back(tgtp, newp); // Create the Splice driver for the new temporary @@ -223,16 +225,16 @@ class AstToDfgConverter final : public VNVisitor { // Ensure the Splice driver exists for this element if (!splicep->driverAt(index)) { FileLine* const flp = nodep->fileline(); - AstNodeDType* const dtypep = DfgGraph::toDfgDType(nodep->dtypep()); + AstNodeDType* const dtypep = V3Dfg::toDfgDType(nodep->dtypep()); if (VN_IS(dtypep, BasicDType)) { DfgSplicePacked* const newp = make(flp, dtypep); - AstNodeDType* const uaDtypep = DfgGraph::dtypeArray(dtypep, 1); + AstNodeDType* const uaDtypep = V3Dfg::dtypeArray(dtypep, 1); DfgUnitArray* const uap = make(flp, uaDtypep); uap->srcp(newp); - splicep->addDriver(flp, index, uap); + splicep->addDriver(uap, index, flp); } else if (VN_IS(dtypep, UnpackArrayDType)) { DfgSpliceArray* const newp = make(flp, dtypep); - splicep->addDriver(flp, index, newp); + splicep->addDriver(newp, index, flp); } else { nodep->v3fatalSrc("Unhandled AstNodeDType sub-type"); // LCOV_EXCL_LINE } @@ -267,64 +269,73 @@ class AstToDfgConverter final : public VNVisitor { , m_rhsp{rhsp} {} }; + // Simplify the LHS, to get rid of things like SEL(CONCAT(_, _), _) + lhsp = VN_AS(V3Const::constifyExpensiveEdit(lhsp), NodeExpr); + + // Assigning compound expressions to a concatenated LHS requires a temporary + // to avoid multiple use of the expression + if (VN_IS(lhsp, Concat) && !vtxp->is() && !vtxp->is()) { + const size_t n = ++m_nUnpack; + DfgVertexVar* const tmpp = createTmp(*m_logicp, flp, vtxp->dtypep(), "Unpack", n); + tmpp->srcp(vtxp); + vtxp = tmpp; + } + // Convert each concatenation LHS separately, gather all assignments // we need to do into 'assignments', return true if all LValues // converted successfully. std::vector assignments; - const std::function convertAllLValues - = [&](AstNodeExpr* lhsp, DfgVertex* vtxp) -> bool { - // Simplify the LHS, to get rid of things like SEL(CONCAT(_, _), _) - lhsp = VN_AS(V3Const::constifyExpensiveEdit(lhsp), NodeExpr); - - // Concatenation on the LHS, convert each parts - if (AstConcat* const concatp = VN_CAST(lhsp, Concat)) { - AstNodeExpr* const cLhsp = concatp->lhsp(); + const std::function convertAllLValues + = [&](AstNodeExpr* subp, uint32_t lsb) -> bool { + // Concatenation on the LHS, convert each part + if (AstConcat* const concatp = VN_CAST(subp, Concat)) { AstNodeExpr* const cRhsp = concatp->rhsp(); - // Convert Left of concat - FileLine* const lFlp = cLhsp->fileline(); - AstNodeDType* const lDtp = DfgGraph::toDfgDType(cLhsp->dtypep()); - DfgSel* const lVtxp = make(lFlp, lDtp); - lVtxp->fromp(vtxp); - lVtxp->lsb(cRhsp->width()); - if (!convertAllLValues(cLhsp, lVtxp)) return false; + AstNodeExpr* const cLhsp = concatp->lhsp(); // Convert Rigth of concat - FileLine* const rFlp = cRhsp->fileline(); - AstNodeDType* const rDtp = DfgGraph::toDfgDType(cRhsp->dtypep()); - DfgSel* const rVtxp = make(rFlp, rDtp); - rVtxp->fromp(vtxp); - rVtxp->lsb(0); - return convertAllLValues(cRhsp, rVtxp); + if (!convertAllLValues(cRhsp, lsb)) return false; + // Convert Left of concat + return convertAllLValues(cLhsp, lsb + cRhsp->width()); } // Non-concatenation, convert the LValue - const auto pair = convertLValue(lhsp); + const auto pair = convertLValue(subp); if (!pair.first) return false; - assignments.emplace_back(pair.first, pair.second, vtxp); + + // If whole lhs, just use it + if (subp == lhsp) { + assignments.emplace_back(pair.first, pair.second, vtxp); + return true; + } + + // Otherwise select the relevant bits + DfgSel* const selp = make(subp->fileline(), V3Dfg::toDfgDType(subp->dtypep())); + selp->fromp(vtxp); + selp->lsb(lsb); + assignments.emplace_back(pair.first, pair.second, selp); return true; }; // Convert the given LHS assignment, give up if any LValues failed to convert - if (!convertAllLValues(lhsp, vtxp)) return false; + if (!convertAllLValues(lhsp, 0)) return false; // All successful, connect the drivers for (const Assignment& item : assignments) { if (DfgSplicePacked* const spp = item.m_lhsp->template cast()) { - spp->addDriver(flp, item.m_idx, item.m_rhsp); + spp->addDriver(item.m_rhsp, item.m_idx, flp); } else if (DfgSpliceArray* const sap = item.m_lhsp->template cast()) { AstUnpackArrayDType* const lDtp = VN_AS(sap->dtypep(), UnpackArrayDType); const AstNodeDType* const lEleDtp = lDtp->subDTypep(); AstNodeDType* const rDtp = item.m_rhsp->dtypep(); if (lEleDtp->isSame(rDtp)) { // RHS is assigning an element of this array. Need a DfgUnitArray adapter. - AstNodeDType* const uaDtp = DfgGraph::dtypeArray(rDtp, 1); - DfgUnitArray* const uap = make(flp, uaDtp); + DfgUnitArray* const uap = make(flp, V3Dfg::dtypeArray(rDtp, 1)); uap->srcp(item.m_rhsp); - sap->addDriver(flp, item.m_idx, uap); + sap->addDriver(uap, item.m_idx, flp); } else { // RHS is assigning an array (or array slice). Should be the same element type. const AstNodeDType* const rEleDtp = VN_AS(rDtp, UnpackArrayDType)->subDTypep(); UASSERT_OBJ(lEleDtp->isSame(rEleDtp), item.m_rhsp, "Mismatched array types"); - sap->addDriver(flp, item.m_idx, item.m_rhsp); + sap->addDriver(item.m_rhsp, item.m_idx, flp); } } else { item.m_lhsp->v3fatalSrc("Unhandled DfgVertexSplice sub-type"); // LCOV_EXCL_LINE @@ -377,14 +388,14 @@ class AstToDfgConverter final : public VNVisitor { FileLine* const flp = nodep->fileline(); DfgVertex* vtxp = nullptr; if (const AstConst* const constp = VN_CAST(nodep->lsbp(), Const)) { - DfgSel* const selp = make(flp, DfgGraph::toDfgDType(nodep->dtypep())); + DfgSel* const selp = make(flp, V3Dfg::toDfgDType(nodep->dtypep())); selp->fromp(nodep->fromp()->user2u().to()); selp->lsb(constp->toUInt()); vtxp = selp; } else { iterate(nodep->lsbp()); if (m_foundUnhandled) return; - DfgMux* const muxp = make(flp, DfgGraph::toDfgDType(nodep->dtypep())); + DfgMux* const muxp = make(flp, V3Dfg::toDfgDType(nodep->dtypep())); muxp->fromp(nodep->fromp()->user2u().to()); muxp->lsbp(nodep->lsbp()->user2u().to()); vtxp = muxp; @@ -397,16 +408,26 @@ class AstToDfgConverter final : public VNVisitor { public: // PUBLIC METHODS + // Create temporay variable capable of holding the given type + DfgVertexVar* createTmp(DfgLogic& logic, FileLine* flp, AstNodeDType* dtypep, + const std::string& prefix, size_t tmpCount) { + const std::string name = m_dfg.makeUniqueName(prefix, tmpCount); + DfgVertexVar* const vtxp = m_dfg.makeNewVar(flp, name, dtypep, logic.scopep()); + logic.synth().emplace_back(vtxp); + vtxp->varp()->isInternal(true); + vtxp->tmpForp(vtxp->nodep()); + return vtxp; + } + // Create a new temporary variable capable of holding 'varp' - static DfgVertexVar* createTmp(DfgGraph& dfg, DfgLogic& logic, Variable* varp, - const std::string& prefix) { + DfgVertexVar* createTmp(DfgLogic& logic, Variable* varp, const std::string& prefix) { AstVar* const astVarp = T_Scoped ? reinterpret_cast(varp)->varp() : reinterpret_cast(varp); const std::string prfx = prefix + "_" + astVarp->name(); - const std::string name = dfg.makeUniqueName(prfx, astVarp->user3Inc()); - AstNodeDType* const dtypep = DfgGraph::toDfgDType(astVarp->dtypep()); - AstScope* const scp = T_Scoped ? reinterpret_cast(varp)->scopep() : nullptr; - DfgVertexVar* const vtxp = dfg.makeNewVar(astVarp->fileline(), name, dtypep, scp); + const std::string name = m_dfg.makeUniqueName(prfx, astVarp->user3Inc()); + FileLine* const flp = astVarp->fileline(); + AstNodeDType* const dtypep = V3Dfg::toDfgDType(astVarp->dtypep()); + DfgVertexVar* const vtxp = m_dfg.makeNewVar(flp, name, dtypep, logic.scopep()); logic.synth().emplace_back(vtxp); vtxp->varp()->isInternal(true); vtxp->tmpForp(varp); @@ -429,7 +450,7 @@ class AstToDfgConverter final : public VNVisitor { AstNodeExpr* const lhsp = nodep->lhsp(); AstNodeExpr* const rhsp = nodep->rhsp(); // Check data types are compatible. - if (!DfgGraph::isSupported(lhsp->dtypep()) || !DfgGraph::isSupported(rhsp->dtypep())) { + if (!V3Dfg::isSupported(lhsp->dtypep()) || !V3Dfg::isSupported(rhsp->dtypep())) { ++m_ctx.m_conv.nonRepDType; return false; } @@ -486,17 +507,17 @@ class AstToDfgSynthesize final { // Represents a [potentially partial] driver of a variable struct Driver final { - FileLine* m_flp = nullptr; // Location of driver in source + DfgVertex* m_vtxp = nullptr; // Driving vertex uint32_t m_lo = 0; // Low index of driven range (internal, not Verilog) uint32_t m_hi = 0; // High index of driven range (internal, not Verilog) - DfgVertex* m_vtxp = nullptr; // Driving vertex + FileLine* m_flp = nullptr; // Location of driver in source Driver() = default; - Driver(FileLine* flp, uint32_t lo, DfgVertex* vtxp) - : m_flp{flp} + Driver(DfgVertex* vtxp, uint32_t lo, FileLine* flp) + : m_vtxp{vtxp} , m_lo{lo} , m_hi{lo + vtxp->size() - 1} - , m_vtxp{vtxp} {} + , m_flp{flp} {} operator bool() const { return m_vtxp != nullptr; } bool operator<(const Driver& other) const { @@ -512,13 +533,15 @@ class AstToDfgSynthesize final { DfgGraph& m_dfg; // The graph being built V3DfgSynthesisContext& m_ctx; // The context for stats AstToDfgConverter m_converter; // The convert instance to use for each construct + size_t m_nBranchCond = 0; // Sequence numbers for temporaries + size_t m_nPathPred = 0; // Sequence numbers for temporaries // STATE - for current DfgLogic being synthesized DfgLogic* m_logicp = nullptr; // Current logic vertex we are synthesizing CfgBlockMap m_bbToISymTab; // Map from CfgBlock -> input symbol table CfgBlockMap m_bbToOSymTab; // Map from CfgBlock -> output symbol table - CfgBlockMap m_bbToCondp; // Map from CfgBlock -> terminating branch condition - CfgEdgeMap m_edgeToPredicatep; // Map CfgGraphEdge -> path predicate to get there + CfgBlockMap m_bbToCondp; // Map from CfgBlock -> terminating branch condition + CfgEdgeMap m_edgeToPredicatep; // Map CfgGraphEdge -> path predicate to there CfgDominatorTree m_domTree; // The dominator tree of the current CFG // STATE - Some debug aid @@ -536,8 +559,9 @@ class AstToDfgSynthesize final { // If we have the debugged logic, compute the vertices feeding its outputs if (VL_UNLIKELY(m_debugLogicp)) { std::vector outputs; - m_debugLogicp->forEachSink([&outputs](const DfgVertex& v) { // + m_debugLogicp->foreachSink([&outputs](const DfgVertex& v) { outputs.emplace_back(v.singleSink()->as()); + return false; }); m_debugOSrcConep = m_dfg.sourceCone(outputs); } @@ -574,65 +598,58 @@ class AstToDfgSynthesize final { } // Gather all drivers of a resolved variable - static std::pair, DfgVertex*> gatherDrivers(const DfgVertexSplice* vtxp) { + static std::vector gatherDrivers(DfgVertexSplice* vtxp) { // Collect them all, check if they are sorted std::vector drivers; - drivers.reserve(vtxp->arity()); - DfgVertex* const defaultp = vtxp->defaultp(); + drivers.reserve(vtxp->nInputs()); bool sorted = true; - vtxp->forEachSourceEdge([&](const DfgEdge& edge, size_t i) { - DfgVertex* const driverp = edge.sourcep(); - UASSERT_OBJ(driverp, vtxp, "Should not have created undriven sources"); - // Ignore default driver - if (driverp == defaultp) return; + vtxp->foreachDriver([&](DfgVertex& src, uint32_t lo, FileLine* flp) { // Collect the driver - drivers.emplace_back(vtxp->driverFileLine(i), vtxp->driverLo(i), driverp); + drivers.emplace_back(&src, lo, flp); // Check if drivers are sorted - most often they are const size_t n = drivers.size(); if (n >= 2 && drivers[n - 1] < drivers[n - 2]) sorted = false; + return false; }); // Sort if unsorted if (!sorted) std::stable_sort(drivers.begin(), drivers.end()); // Done - return {std::move(drivers), defaultp}; + return drivers; } // Gather all synthesized drivers of an unresolved variable - static std::vector gatherDriversUnresolved(const DfgUnresolved* vtxp) { + static std::vector gatherDriversUnresolved(DfgUnresolved* vtxp) { std::vector drivers; - drivers.reserve(vtxp->arity()); + drivers.reserve(vtxp->nInputs()); // For better locations in error reporting, we unpick concatenations // which are sometimes introduced by combinint assignments in V3Const. - const std::function gather - = [&](FileLine* flp, uint32_t lo, DfgVertex* vtxp) -> void { + const std::function gather + = [&](DfgVertex* vtxp, uint32_t lo, FileLine* flp) -> void { if (DfgConcat* const concatp = vtxp->cast()) { DfgVertex* const rhsp = concatp->rhsp(); - gather(rhsp->fileline(), lo, rhsp); + gather(rhsp, lo, rhsp->fileline()); DfgVertex* const lhsp = concatp->lhsp(); - gather(lhsp->fileline(), lo + rhsp->width(), lhsp); + gather(lhsp, lo + rhsp->width(), lhsp->fileline()); return; } - drivers.emplace_back(flp, lo, vtxp); + drivers.emplace_back(vtxp, lo, flp); }; // Gather all synthesized drivers - vtxp->forEachSource([&](const DfgVertex& src) { + vtxp->foreachSource([&](DfgVertex& src) { // Can ignore the original DfgLogic - if (src.is()) return; - + if (src.is()) return false; // Synthesized drivers must be a splice at this point - const DfgVertexSplice* const splicep = src.as(); - splicep->forEachSourceEdge([&](const DfgEdge& edge, size_t i) { - DfgVertex* const driverp = edge.sourcep(); - UASSERT_OBJ(driverp, splicep, "Should not have created undriven sources"); - // Ignore the default driver, it's the feedback in circular logic - if (driverp == splicep->defaultp()) return; - // Collect the driver - gather(splicep->driverFileLine(i), splicep->driverLo(i), driverp); + DfgVertexSplice* const splicep = src.as(); + // Collect the driver + splicep->foreachDriver([&](DfgVertex& src, uint32_t lo, FileLine* flp) { + gather(&src, lo, flp); + return false; }); + return false; }); // Sort the drivers @@ -657,23 +674,16 @@ class AstToDfgSynthesize final { const DfgUnitArray* const bUap = b.m_vtxp->template cast(); if (!bUap) return {false, false}; // ... and are themeselves partial - const DfgSplicePacked* const aSp = aUap->srcp()->template cast(); + DfgSplicePacked* const aSp = aUap->srcp()->template cast(); if (!aSp) return {false, false}; - const DfgSplicePacked* const bSp = bUap->srcp()->template cast(); + DfgSplicePacked* const bSp = bUap->srcp()->template cast(); if (!bSp) return {false, false}; UASSERT_OBJ(aSp->dtypep()->isSame(bSp->dtypep()), &var, "DTypes should match"); // Gather drivers of a - std::vector aDrivers; - DfgVertex* aDefaultp = nullptr; - std::tie(aDrivers, aDefaultp) = gatherDrivers(aSp); - UASSERT_OBJ(!aDefaultp, aSp, "Should not have default driver here"); - + std::vector aDrivers = gatherDrivers(aSp); // Gather drivers of b - std::vector bDrivers; - DfgVertex* bDefaultp = nullptr; - std::tie(bDrivers, bDefaultp) = gatherDrivers(bSp); - UASSERT_OBJ(!bDefaultp, bSp, "Should not have default driver here"); + std::vector bDrivers = gatherDrivers(bSp); // Merge them std::vector abDrivers; @@ -692,7 +702,7 @@ class AstToDfgSynthesize final { // Successfully resolved. Needs a new splice and unit. FileLine* const flp = var.fileline(); DfgSplicePacked* const splicep = make(flp, aSp->dtypep()); - for (const Driver& d : abDrivers) splicep->addDriver(d.m_flp, d.m_lo, d.m_vtxp); + for (const Driver& d : abDrivers) splicep->addDriver(d.m_vtxp, d.m_lo, d.m_flp); DfgUnitArray* const uap = make(flp, aUap->dtypep()); uap->srcp(splicep); a.m_vtxp = uap; @@ -830,7 +840,7 @@ class AstToDfgSynthesize final { } // Coalesce Adjacent ranges, - const auto dtypep = DfgGraph::dtypePacked(iD.m_vtxp->width() + jD.m_vtxp->width()); + const auto dtypep = V3Dfg::dtypePacked(iD.m_vtxp->width() + jD.m_vtxp->width()); DfgConcat* const concatp = make(iD.m_flp, dtypep); concatp->rhsp(iD.m_vtxp); concatp->lhsp(jD.m_vtxp); @@ -857,7 +867,7 @@ class AstToDfgSynthesize final { } else { var.v3fatalSrc("Unhandled DfgVertexVar sub-type"); // LCOV_EXCL_LINE } - for (const Driver& d : newDrivers) splicep->addDriver(d.m_flp, d.m_lo, d.m_vtxp); + for (const Driver& d : newDrivers) splicep->addDriver(d.m_vtxp, d.m_lo, d.m_flp); return splicep; } @@ -865,7 +875,7 @@ class AstToDfgSynthesize final { // we generally cannot synthesize the construct, as we will likely need to // introduce intermediate values that would not be updated. static bool hasExternallyWrittenVariable(DfgLogic& vtx) { - return vtx.findSink([](const DfgVertex& sink) -> bool { + return vtx.foreachSink([&](const DfgVertex& sink) { // 'sink' is a splice (for which 'vtxp' is an unresolved driver), // which drives the target variable. const DfgVertexVar* varp = sink.singleSink()->as(); @@ -879,18 +889,17 @@ class AstToDfgSynthesize final { // Initialzie input symbol table of entry CfgBlock void initializeEntrySymbolTable(SymTab& iSymTab) { - m_logicp->forEachSource([&](DfgVertex& src) { + m_logicp->foreachSource([&](DfgVertex& src) { DfgVertexVar* const vvp = src.as(); Variable* const varp = reinterpret_cast(vvp->nodep()); iSymTab[varp] = vvp; + return false; }); } // Join variable drivers across a control flow confluence (insert muxes ...) - DfgVertexVar* joinDrivers(Variable* varp, DfgVertex* predicatep, // + DfgVertexVar* joinDrivers(Variable* varp, DfgVertexVar* predicatep, // DfgVertexVar* thenp, DfgVertexVar* elsep) { - UASSERT_OBJ(!predicatep->is(), predicatep, "joinDrivers with cons predicate"); - AstNode* const thenVarp = thenp->tmpForp() ? thenp->tmpForp() : thenp->nodep(); AstNode* const elseVarp = elsep->tmpForp() ? elsep->tmpForp() : elsep->nodep(); UASSERT_OBJ(thenVarp == elseVarp, varp, "Attempting to join unrelated variables"); @@ -916,14 +925,12 @@ class AstToDfgSynthesize final { } // Gather drivers of 'thenp' - only if 'thenp' is not an input to the synthesized block - std::vector tDrivers; - DfgVertex* tDefaultp = nullptr; - std::tie(tDrivers, tDefaultp) = gatherDrivers(thenp->srcp()->as()); + DfgVertex* const tDefaultp = thenp->defaultp(); + std::vector tDrivers = gatherDrivers(thenp->srcp()->as()); // Gather drivers of 'elsep' - only if 'thenp' is not an input to the synthesized block - std::vector eDrivers; - DfgVertex* eDefaultp = nullptr; - std::tie(eDrivers, eDefaultp) = gatherDrivers(elsep->srcp()->as()); + DfgVertex* const eDefaultp = elsep->defaultp(); + std::vector eDrivers = gatherDrivers(elsep->srcp()->as()); // Default drivers should be the same or not present on either UASSERT_OBJ(tDefaultp == eDefaultp, varp, "Different default drivers"); @@ -932,7 +939,7 @@ class AstToDfgSynthesize final { FileLine* const flp = predicatep->fileline(); // Create a fresh temporary for the joined value - DfgVertexVar* const joinp = m_converter.createTmp(m_dfg, *m_logicp, varp, "SynthJoin"); + DfgVertexVar* const joinp = m_converter.createTmp(*m_logicp, varp, "SynthJoin"); DfgVertexSplice* const joinSplicep = make(flp, joinp->dtypep()); joinp->srcp(joinSplicep); @@ -949,7 +956,7 @@ class AstToDfgSynthesize final { condp->condp(predicatep); condp->thenp(thenp); condp->elsep(elsep); - joinSplicep->addDriver(tDrivers[0].m_flp, 0, condp); + joinSplicep->addDriver(condp, 0, tDrivers[0].m_flp); // Done return joinp; @@ -972,7 +979,7 @@ class AstToDfgSynthesize final { return nullptr; } - AstNodeDType* const dtypep = DfgGraph::dtypePacked(tDriver.m_hi - tDriver.m_lo + 1); + AstNodeDType* const dtypep = V3Dfg::dtypePacked(tDriver.m_hi - tDriver.m_lo + 1); DfgCond* const condp = make(flp, dtypep); condp->condp(predicatep); @@ -989,18 +996,18 @@ class AstToDfgSynthesize final { condp->elsep(elseSelp); // Add it as a driver to the join - joinSplicep->addDriver(tDriver.m_flp, tDriver.m_lo, condp); + joinSplicep->addDriver(condp, tDriver.m_lo, tDriver.m_flp); } // If there was a default driver, add it to te join - if (tDefaultp) joinSplicep->defaultp(tDefaultp); + if (tDefaultp) joinp->defaultp(tDefaultp); // Done return joinp; } // Merge 'thenSymTab' into 'elseSymTab' using the given predicate to join values - bool joinSymbolTables(SymTab& elseSymTab, DfgVertex* predicatep, const SymTab& thenSymTab) { + bool joinSymbolTables(SymTab& elseSymTab, DfgVertexVar* predicatep, const SymTab& thenSymTab) { // Give up if something is not assigned on all paths ... Latch? if (thenSymTab.size() != elseSymTab.size()) { ++m_ctx.m_synt.nonSynLatch; @@ -1029,7 +1036,7 @@ class AstToDfgSynthesize final { // Given two joining control flow edges, compute how to join their symbols. // Returns the predicaete to join over, and the 'then' and 'else' blocks. - std::tuple // + std::tuple // howToJoin(const CfgEdge* const ap, const CfgEdge* const bp) { // Find the closest common dominator of the two paths const CfgBlock* const domp = m_domTree.closestCommonDominator(ap->srcp(), bp->srcp()); @@ -1096,7 +1103,7 @@ class AstToDfgSynthesize final { // We also have a simpler job if there are 2 predecessors if (bb.isTwoWayJoin()) { - DfgVertex* predicatep = nullptr; + DfgVertexVar* predicatep = nullptr; const CfgBlock* thenp = nullptr; const CfgBlock* elsep = nullptr; std::tie(predicatep, thenp, elsep) @@ -1112,10 +1119,10 @@ class AstToDfgSynthesize final { // Gather predecessors struct Predecessor final { const CfgBlock* m_bbp; // Predeccessor block - DfgVertex* m_predicatep; // Predicate predecessor reached this block with + DfgVertexVar* m_predicatep; // Predicate predecessor reached this block with const SymTab* m_oSymTabp; // Output symbol table or predecessor Predecessor() = delete; - Predecessor(const CfgBlock* bbp, DfgVertex* predicatep, const SymTab* oSymTabp) + Predecessor(const CfgBlock* bbp, DfgVertexVar* predicatep, const SymTab* oSymTabp) : m_bbp{bbp} , m_predicatep{predicatep} , m_oSymTabp{oSymTabp} {} @@ -1126,7 +1133,7 @@ class AstToDfgSynthesize final { for (const V3GraphEdge& edge : bb.inEdges()) { const CfgEdge& cfgEdge = static_cast(edge); const CfgBlock* const predecessorp = cfgEdge.srcp(); - DfgVertex* const predicatep = m_edgeToPredicatep[cfgEdge]; + DfgVertexVar* const predicatep = m_edgeToPredicatep[cfgEdge]; const SymTab* const oSymTabp = &m_bbToOSymTab[predecessorp]; res.emplace_back(predecessorp, predicatep, oSymTabp); } @@ -1142,7 +1149,7 @@ class AstToDfgSynthesize final { joined = *predecessors[0].m_oSymTabp; // Join over all other predecessors for (size_t i = 1; i < predecessors.size(); ++i) { - DfgVertex* const predicatep = predecessors[i].m_predicatep; + DfgVertexVar* const predicatep = predecessors[i].m_predicatep; const SymTab& oSymTab = *predecessors[i].m_oSymTabp; if (!joinSymbolTables(joined, predicatep, oSymTab)) return false; } @@ -1150,67 +1157,34 @@ class AstToDfgSynthesize final { return true; } - // Gieven the drivers of a variable after converting a single statement - // 'newp', add drivers from 'oldp' that were not reassigned be drivers - // in newp. This computes the total result of all previous assignments. - bool incorporatePreviousValue(Variable* varp, const DfgVertexVar* newp, DfgVertexVar* oldp) { - UASSERT_OBJ(newp->srcp(), varp, "Assigned variable has no driver"); - - // Easy if there is no old value... - if (!oldp) return true; - - // New driver was not yet coalesced, so should always be a splice - DfgVertexSplice* const nSplicep = newp->srcp()->as(); - - // If the old value is the real variable we just computed the new value for, - // then it is the circular feedback into the synthesized block, add it as default driver. - if (oldp->nodep() == varp) { - if (!nSplicep->wholep()) nSplicep->defaultp(oldp); - return true; - } - - UASSERT_OBJ(oldp->srcp(), varp, "Previously assigned variable has no driver"); - - // Can't do arrays yet - if (VN_IS(newp->dtypep(), UnpackArrayDType)) { - ++m_ctx.m_synt.nonSynArray; - return false; - } - - // Gather drivers of 'newp' - they are in incresing range order with no overlaps - std::vector nDrivers; - DfgVertex* nDefaultp = nullptr; - std::tie(nDrivers, nDefaultp) = gatherDrivers(newp->srcp()->as()); - UASSERT_OBJ(!nDrivers.empty(), varp, "Should have a proper driver"); - UASSERT_OBJ(!nDefaultp, varp, "Should not have a default after conversion"); - + std::vector computePropagatedDrivers(const std::vector& newDrivers, + DfgVertexVar* oldp) { // Gather drivers of 'oldp' - they are in incresing range order with no overlaps - std::vector oDrivers; - DfgVertex* oDefaultp = nullptr; - std::tie(oDrivers, oDefaultp) = gatherDrivers(oldp->srcp()->as()); - UASSERT_OBJ(!oDrivers.empty(), varp, "Should have a proper driver"); + std::vector oldDrivers = gatherDrivers(oldp->srcp()->as()); + UASSERT_OBJ(!oldDrivers.empty(), oldp, "Should have a proper driver"); // Additional drivers of 'newp' propagated from 'oldp' - std::vector pDrivers; + std::vector propagatedDrivers; // Add bits between 'msb' and 'lsb' from 'oldp' to 'pDrivers' - const auto addToPDriver = [&](FileLine* const flp, uint32_t msb, uint32_t lsb) { - UASSERT_OBJ(pDrivers.empty() || lsb > pDrivers.back().m_hi, flp, "Non ascending"); - DfgSel* const selp = make(flp, DfgGraph::dtypePacked(msb - lsb + 1)); + const auto addOldDriver = [&](FileLine* const flp, uint32_t msb, uint32_t lsb) { + UASSERT_OBJ(propagatedDrivers.empty() || lsb > propagatedDrivers.back().m_hi, flp, + "Drivers should be in ascending order"); + DfgSel* const selp = make(flp, V3Dfg::dtypePacked(msb - lsb + 1)); selp->lsb(lsb); selp->fromp(oldp); - pDrivers.emplace_back(flp, lsb, selp); + propagatedDrivers.emplace_back(selp, lsb, flp); }; // Incorporate old drivers - for (const Driver& oDriver : oDrivers) { + for (const Driver& oDriver : oldDrivers) { FileLine* const flp = oDriver.m_flp; // Range to consider inserting, we will adjust oldLo as we process drivers uint32_t oldLo = oDriver.m_lo; const uint32_t oldHi = oDriver.m_hi; // Loop for now, can move to bisection search if this is a problem, shouldn't be ... - for (const Driver& nDriver : nDrivers) { + for (const Driver& nDriver : newDrivers) { UASSERT_OBJ(oldHi >= oldLo, flp, "Should have stopped iteration"); // If new driver is entirely below old driver, move on to if (nDriver.m_hi < oldLo) continue; @@ -1220,7 +1194,7 @@ class AstToDfgSynthesize final { // There is an overlap between 'oDriver' and 'nDriver'. // Insert the low bits and adjust the insertion range. // The rest will take care of itself on subsequent iterations. - if (oldLo < nDriver.m_lo) addToPDriver(flp, nDriver.m_lo - 1, oldLo); + if (oldLo < nDriver.m_lo) addOldDriver(flp, nDriver.m_lo - 1, oldLo); oldLo = nDriver.m_hi + 1; // Stop if no more bits remaining in the old driver @@ -1228,13 +1202,50 @@ class AstToDfgSynthesize final { } // Insert remaining bits if any - if (oldHi >= oldLo) addToPDriver(flp, oldHi, oldLo); + if (oldHi >= oldLo) addOldDriver(flp, oldHi, oldLo); } + return propagatedDrivers; + } + + // Given the drivers of a variable after converting a single statement + // 'newp', add drivers from 'oldp' that were not reassigned be drivers + // in newp. This computes the total result of all previous assignments. + bool incorporatePreviousValue(Variable* varp, DfgVertexVar* newp, DfgVertexVar* oldp) { + UASSERT_OBJ(newp->srcp(), varp, "Assigned variable has no driver"); + + // Easy if there is no old value... + if (!oldp) return true; + + // New driver was not yet coalesced, so should always be a splice + DfgVertexSplice* const nSplicep = newp->srcp()->as(); + + // If the old value is the real variable we just computed the new value for, + // then it is the circular feedback into the synthesized block, add it as default driver. + if (oldp->nodep() == varp) { + if (!nSplicep->wholep()) newp->defaultp(oldp); + return true; + } + + UASSERT_OBJ(oldp->srcp(), varp, "Previously assigned variable has no driver"); + + // Can't do arrays yet + if (VN_IS(newp->dtypep(), UnpackArrayDType)) { + ++m_ctx.m_synt.nonSynArray; + return false; + } + + // Gather drivers of 'newp' - they are in incresing range order with no overlaps + UASSERT_OBJ(!newp->defaultp(), newp, "Converted value should not have default"); + std::vector nDrivers = gatherDrivers(newp->srcp()->as()); + UASSERT_OBJ(!nDrivers.empty(), newp, "Should have a proper driver"); + + // Additional drivers of 'newp' propagated from 'oldp' + std::vector pDrivers = computePropagatedDrivers(nDrivers, oldp); + if (!pDrivers.empty()) { - // Need to merge propagated sources, so unlink and reset the splice - nSplicep->forEachSourceEdge([](DfgEdge& edge, size_t) { edge.unlinkSource(); }); - nSplicep->resetSources(); + // Need to merge propagated sources, so reset the splice + nSplicep->resetDrivers(); // Merge drivers - they are both sorted and non-overlapping std::vector drivers; drivers.reserve(nDrivers.size() + pDrivers.size()); @@ -1243,11 +1254,11 @@ class AstToDfgSynthesize final { // Coalesce adjacent ranges coalesceDrivers(drivers); // Reinsert drivers in order - for (const Driver& d : drivers) nSplicep->addDriver(d.m_flp, d.m_lo, d.m_vtxp); + for (const Driver& d : drivers) nSplicep->addDriver(d.m_vtxp, d.m_lo, d.m_flp); } // If the old had a default, add to the new one too, unless redundant - if (oDefaultp && !nSplicep->wholep()) nSplicep->defaultp(oDefaultp); + if (oldp->defaultp() && !nSplicep->wholep()) newp->defaultp(oldp->defaultp()); // Done return true; @@ -1287,18 +1298,19 @@ class AstToDfgSynthesize final { // The new, potentially partially assigned value DfgVertexVar* const newp = pair.second; // Normalize drivers within this statement, bail if multidriven - std::vector drivers; - DfgVertex* dfltp = nullptr; - std::tie(drivers, dfltp) = gatherDrivers(newp->srcp()->as()); - UASSERT_OBJ(!dfltp, varp, "Conversion should not add default driver"); + DfgVertexSplice* const srcp = newp->srcp()->as(); + std::vector drivers = gatherDrivers(srcp); const bool single = drivers.size() == 1; if (!normalizeDrivers(*newp, drivers)) { getAstVar(varp)->setDfgMultidriven(); ++m_ctx.m_synt.nonSynMultidrive; return false; } - // If there were more than one driver (often not), replace in case coalesced - if (!single) newp->srcp(makeSplice(*newp, drivers)); + // If there were more than one driver (often not), re-add in case coalesced + if (!single) { + srcp->resetDrivers(); + for (const Driver& d : drivers) srcp->addDriver(d.m_vtxp, d.m_lo, d.m_flp); + } // The old value, if any DfgVertexVar* const oldp = varp->user2u().template to(); // Inncorporate old value into the new value @@ -1316,23 +1328,20 @@ class AstToDfgSynthesize final { if (AstIf* const ifp = VN_CAST(stmtp, If)) { UASSERT_OBJ(ifp == stmtps.back(), ifp, "Branch should be last statement"); // Convert condition, give up if failed - DfgVertex* const condp = m_converter.convert(*m_logicp, ifp->condp()); + DfgVertex* condp = m_converter.convert(*m_logicp, ifp->condp()); if (!condp) { ++m_ctx.m_synt.nonSynConv; return false; } - // - if (condp->width() == 1) { - // Single bit condition can be use directly - condpr = condp; - } else { - // Multi bit condition: use 'condp != 0' + // Single bit condition can be use directly, otherwise: use 'condp != 0' + if (condp->width() != 1) { FileLine* const flp = condp->fileline(); - DfgNeq* const neqp = make(flp, DfgGraph::dtypePacked(1)); + DfgNeq* const neqp = make(flp, V3Dfg::dtypePacked(1)); neqp->lhsp(make(flp, condp->width(), 0U)); neqp->rhsp(condp); - condpr = neqp; + condp = neqp; } + condpr = condp; continue; } @@ -1367,30 +1376,50 @@ class AstToDfgSynthesize final { return resp; }(); + size_t n = m_nPathPred++; // Sequence number for temporaries + AstNodeDType* const dtypep = predp->dtypep(); + + const auto mkTmp = [&](FileLine* flp, const char* name, DfgVertex* srcp) { + std::string prefix; + prefix += "_BB"; + prefix += std::to_string(bb.id()); + prefix += "_"; + prefix += name; + DfgVertexVar* const tmpp = m_converter.createTmp(*m_logicp, flp, dtypep, prefix, n); + tmpp->srcp(srcp); + return tmpp; + }; + + // Assign it to a variable in case it's used multiple times + DfgVertexVar* const pInp = mkTmp(predp->fileline(), "PathIn", predp); + // For uncondional branches, the successor predicate edge is the same if (!bb.isBranch()) { - m_edgeToPredicatep[bb.takenEdgep()] = predp; + m_edgeToPredicatep[bb.takenEdgep()] = mkTmp(pInp->fileline(), "Goto", pInp); return; } // For branches, we need to factor in the branch condition DfgVertex* const condp = m_bbToCondp[bb]; FileLine* const flp = condp->fileline(); - AstNodeDType* const dtypep = condp->dtypep(); // Single bit // Predicate for taken branch: 'predp & condp' - DfgAnd* const takenPredp = make(flp, dtypep); - takenPredp->lhsp(predp); - takenPredp->rhsp(condp); - m_edgeToPredicatep[bb.takenEdgep()] = takenPredp; + { + DfgAnd* const takenPredp = make(flp, dtypep); + takenPredp->lhsp(pInp); + takenPredp->rhsp(condp); + m_edgeToPredicatep[bb.takenEdgep()] = mkTmp(flp, "Taken", takenPredp); + } // Predicate for untaken branch: 'predp & ~condp' - DfgAnd* const untknPredp = make(flp, dtypep); - untknPredp->lhsp(predp); - DfgNot* const notp = make(flp, dtypep); - notp->srcp(condp); - untknPredp->rhsp(notp); - m_edgeToPredicatep[bb.untknEdgep()] = untknPredp; + { + DfgAnd* const untknPredp = make(flp, dtypep); + untknPredp->lhsp(pInp); + DfgNot* const notp = make(flp, dtypep); + notp->srcp(condp); + untknPredp->rhsp(notp); + m_edgeToPredicatep[bb.untknEdgep()] = mkTmp(flp, "Untkn", untknPredp); + } } // Add the synthesized values as drivers to the output variables of the current DfgLogic @@ -1400,7 +1429,7 @@ class AstToDfgSynthesize final { // These LHS forms can happen after some earlier tranforms. We // should just run V3Const on them earlier, but we will do belt and // braces and check here too. We can't touch any output variables if so. - const bool missing = m_logicp->findSink([&](const DfgVertex& sink) -> bool { + const bool missing = m_logicp->foreachSink([&](const DfgVertex& sink) { const DfgUnresolved* const unresolvedp = sink.as(); AstNode* const tgtp = unresolvedp->singleSink()->as()->nodep(); // cppcheck-suppress constVariablePointer @@ -1413,16 +1442,41 @@ class AstToDfgSynthesize final { } // Add sinks to read the computed values for the target variables - m_logicp->forEachSink([&](DfgVertex& sink) { + bool hasUsedArrayOutput = false; + m_logicp->foreachSink([&](DfgVertex& sink) { DfgUnresolved* const unresolvedp = sink.as(); AstNode* const tgtp = unresolvedp->singleSink()->as()->nodep(); // cppcheck-suppress constVariablePointer Variable* const varp = reinterpret_cast(tgtp); DfgVertexVar* const resp = oSymTab.at(varp); UASSERT_OBJ(resp->srcp(), resp, "Undriven result"); - unresolvedp->addDriver(resp->srcp()->as()); + + // If the output is not used further in the synthesized logic itself, + // then resp will be deleted before we return, so we can just use + // its splice directly without ending up with a multi-use operation. + if (!resp->hasSinks()) { + unresolvedp->addDriver(resp->srcp()->as()); + return false; + } + + // TODO: computePropagatedDrivers cannot handle arrays, should + // never happen with AssignW + if (!resp->isPacked()) { + if (!hasUsedArrayOutput) ++m_ctx.m_synt.nonSynArray; + hasUsedArrayOutput = true; + return false; + } + + // We need to add a new splice to avoid multi-use of the original splice + DfgSplicePacked* const splicep + = new DfgSplicePacked{m_dfg, resp->fileline(), resp->dtypep()}; + // Drivers are the same + const std::vector drivers = computePropagatedDrivers({}, resp); + for (const Driver& d : drivers) splicep->addDriver(d.m_vtxp, d.m_lo, d.m_flp); + unresolvedp->addDriver(splicep); + return false; }); - return true; + return !hasUsedArrayOutput; } // Synthesize the given AstAssignW. Returns true on success. @@ -1481,13 +1535,13 @@ class AstToDfgSynthesize final { } // Initialize maps needed for non-trivial CFGs m_domTree = CfgDominatorTree{cfg}; - m_edgeToPredicatep = cfg.makeEdgeMap(); + m_edgeToPredicatep = cfg.makeEdgeMap(); } // Initialize CfgMaps m_bbToISymTab = cfg.makeBlockMap(); m_bbToOSymTab = cfg.makeBlockMap(); - m_bbToCondp = cfg.makeBlockMap(); + m_bbToCondp = cfg.makeBlockMap(); // Synthesize all blocks for (const V3GraphVertex& vtx : cfg.vertices()) { @@ -1495,12 +1549,20 @@ class AstToDfgSynthesize final { // Prepare the input symbol table of this block (enter, or join predecessor blocks) if (!createInputSymbolTable(bb)) return false; // Synthesize this block - if (!synthesizeBasicBlock(m_bbToOSymTab[bb], // - m_bbToCondp[bb], // - bb.stmtps(), // - m_bbToISymTab[bb])) { + DfgVertex* condp = nullptr; + if (!synthesizeBasicBlock(m_bbToOSymTab[bb], condp, bb.stmtps(), m_bbToISymTab[bb])) { return false; } + // Create a temporary for the branch condition as it might be used multiple times + if (condp) { + FileLine* const flp = condp->fileline(); + AstNodeDType* const dtypep = condp->dtypep(); + const std::string prefix = "_BB" + std::to_string(bb.id()) + "_Cond"; + const size_t n = m_nBranchCond++; + DfgVertexVar* const vp = m_converter.createTmp(*m_logicp, flp, dtypep, prefix, n); + vp->srcp(condp); + m_bbToCondp[bb] = vp; + } // Set the path predicates on the successor edges assignPathPredicates(bb); } @@ -1539,9 +1601,10 @@ class AstToDfgSynthesize final { // Gather all logic driving this unresolved driver std::vector logicps; - logicps.reserve(vtxp->arity()); - vtxp->forEachSource([&](DfgVertex& src) { + logicps.reserve(vtxp->nInputs()); + vtxp->foreachSource([&](DfgVertex& src) { if (DfgLogic* const p = src.cast()) logicps.emplace_back(p); + return false; }); // Delete the unresolved driver @@ -1592,8 +1655,8 @@ class AstToDfgSynthesize final { if (!unresolvedp) break; // Stop when reached the synthesized temporaries // Check if any driver have failed to synthesize - const bool failed = unresolvedp->findSourceEdge([&](const DfgEdge& e, size_t) -> bool { - DfgLogic* const driverp = e.sourcep()->cast(); + const bool failed = unresolvedp->foreachSource([&](DfgVertex& src) { + DfgLogic* const driverp = src.cast(); return driverp && driverp->synth().empty(); }); // Revert all logic involved @@ -1610,14 +1673,16 @@ class AstToDfgSynthesize final { // Compute resolved drivers of all variablees for (DfgVertexVar& var : m_dfg.varVertices()) { if (!var.srcp()) continue; - const DfgUnresolved* const unresolvedp = var.srcp()->cast(); + DfgUnresolved* const unresolvedp = var.srcp()->cast(); if (!unresolvedp) break; // Stop when reached the synthesized temporaries // Resolve the synthesized drivers DfgVertexSplice* const resolvedp = [&]() -> DfgVertexSplice* { // All synthesized drivers were normalized already, // so if there is only one, it can be used directly - if (const auto p = unresolvedp->singleSource()) return p->as(); + if (unresolvedp->nInputs() == 1) { + return unresolvedp->inputp(0)->as(); + } // Otherwise gather the synthesized drivers std::vector drivers = gatherDriversUnresolved(unresolvedp); // Normalize them, make resolved driver if all good @@ -1673,8 +1738,9 @@ class AstToDfgSynthesize final { } else { // Not synthesized. Logic stays in Ast. Mark source variables //as read in module. Outputs already marked by revertTransivelyAndRemove. - logicp->forEachSource([](DfgVertex& src) { // + logicp->foreachSource([](DfgVertex& src) { // src.as()->setHasModRdRefs(); + return false; }); } @@ -1698,7 +1764,7 @@ class AstToDfgSynthesize final { } // It should alway have drivers - UASSERT_OBJ(splicep->arity(), splicep, "Splice with no drivers"); + UASSERT_OBJ(splicep->nInputs(), splicep, "Splice with no drivers"); // If redundant, remove it if (DfgVertex* const wholep = splicep->wholep()) { @@ -1715,6 +1781,18 @@ class AstToDfgSynthesize final { UINFO(5, "Step 6: Remove all unused vertices"); V3DfgPasses::removeUnused(m_dfg); debugDump("synth-rmunused"); + + // No operation vertex should have multiple sinks. Cyclic decomoposition + // depends on this and it can easily be ensured by using temporaries. + // Also, all sources should be connected at this point + if (v3Global.opt.debugCheck()) { + for (DfgVertex& vtx : m_dfg.opVertices()) { + UASSERT_OBJ(!vtx.hasMultipleSinks(), &vtx, "Operation has multiple sinks"); + for (size_t i = 0; i < vtx.nInputs(); ++i) { + UASSERT_OBJ(vtx.inputp(i), &vtx, "Unconnected source operand"); + } + } + } } // CONSTRUCTOR @@ -1763,13 +1841,13 @@ void V3DfgPasses::synthesize(DfgGraph& dfg, V3DfgContext& ctx) { const DfgUnresolved* const unresolvedp = var.srcp()->as(); // Inspect drivers to figure out if we should synthesize them - const bool doIt = unresolvedp->findSourceEdge([](const DfgEdge& edge, size_t) -> bool { - const DfgLogic* const logicp = edge.sourcep()->as(); - // Synthesize continuous assignments (this is the earlier behaviour) - if (VN_IS(logicp->nodep(), AssignW)) return true; + const bool doIt = unresolvedp->foreachSource([&](const DfgVertex& src) { + const DfgLogic* const logicp = src.as(); + // Synthesize continuous assignments (this is the earlier behaviour). // Synthesize always blocks with no more than 4 basic blocks and 4 edges // These are usually simple branches (if (rst) ... else ...), or close to it - return logicp->cfg().nBlocks() <= 4 && logicp->cfg().nEdges() <= 4; + return VN_IS(logicp->nodep(), AssignW) // + || (logicp->cfg().nBlocks() <= 4 && logicp->cfg().nEdges() <= 4); }); if (doIt) varps.emplace_back(&var); } @@ -1777,9 +1855,10 @@ void V3DfgPasses::synthesize(DfgGraph& dfg, V3DfgContext& ctx) { // Gather all drivers of the selected variables const VNUser2InUse user2InUse; // AstNode (logic) -> bool: already collected for (const DfgVertexVar* const varp : varps) { - varp->srcp()->as()->forEachSource([&](DfgVertex& source) { + varp->srcp()->as()->foreachSource([&](DfgVertex& source) { DfgLogic* const logicp = source.as(); if (!logicp->nodep()->user2Inc()) logicps.emplace_back(logicp); + return false; }); } } diff --git a/src/V3DfgVertices.h b/src/V3DfgVertices.h index 316f2c3ae1a..b445ac0aa79 100644 --- a/src/V3DfgVertices.h +++ b/src/V3DfgVertices.h @@ -36,39 +36,101 @@ #define VL_NOT_FINAL // This #define fixes broken code folding in the CLion IDE #endif -// === Abstract base node types (DfgVertex*) =================================== +// Include macros generated by 'astgen'. These include DFGGEN_MEMBERS_ +// for each DfgVertex sub-type. The generated members include boilerplate +// methods related to cloning, visitor dispatch, and other functionality. +// For precise details please read the generated macros. +#include "V3Dfg__gen_macros.h" + +//------------------------------------------------------------------------------ +// Variable vertices - represent a variables + +class DfgVertexVar VL_NOT_FINAL : public DfgVertex { + // Represents a variable. It has 2 optional inputs, 'srcp' and 'defaultp'. -class DfgVertexVar VL_NOT_FINAL : public DfgVertexUnary { AstVar* const m_varp; // The AstVar associated with this vertex (not owned by this vertex) AstVarScope* const m_varScopep; // The AstVarScope associated with this vertex (not owned) // Location of driver of this variable. Only used for converting back to Ast. Might be nullptr. FileLine* m_driverFileLine = nullptr; - // If this DfgVertexVar is a synthesized temporary, this is the Var/VarScope it stands for. + // If this DfgVertexVar is a synthesized temporary, this is the original Var/VarScope it stands + // for. It might point to m_varp/m_varScopep itself to indicate it's a temporary without an + // associated input Var/VarScope. AstNode* m_tmpForp = nullptr; - bool selfEquals(const DfgVertex& that) const final VL_MT_DISABLED; - V3Hash selfHash() const final VL_MT_DISABLED; + bool selfEquals(const DfgVertex& that) const final { + UASSERT_OBJ(nodep() != that.as()->nodep(), this, + "There should only be one DfgVertexVar for a given AstVar/AstVarScope"); + return false; + } + + V3Hash selfHash() const final { + V3Hash hash; + hash += nodep()->name(); + hash += varp()->varType(); + return hash; + } + + DfgVertexVar(DfgGraph& dfg, VDfgType type, AstVar* varp, AstVarScope* vscp) + : DfgVertex{dfg, type, varp->fileline(), V3Dfg::toDfgDType(varp->dtypep())} + , m_varp{varp} + , m_varScopep{vscp} { +#ifdef VL_DEBUG + if (v3Global.rootp()->topScopep()) { + UASSERT_OBJ(vscp, varp, "Un-scoped DfgVertexVar created in scoped DfgGraph"); + } else { + UASSERT_OBJ(!vscp, varp, "Scoped DfgVertexVar created in un-scoped DfgGraph"); + } + UASSERT_OBJ(V3Dfg::isSupported(dtypep()), varp, "Not representable by DfgVertexVar"); +#endif + // Increment reference count + AstNode* const variablep = nodep(); + variablep->user1(variablep->user1() + 0x10); + UASSERT_OBJ((variablep->user1() >> 4) > 0, variablep, "Reference count overflow"); + // Allocate sources + newInput(); + newInput(); + } + +protected: + DfgVertexVar(DfgGraph& dfg, VDfgType type, AstVar* varp) + : DfgVertexVar{dfg, type, varp, nullptr} {} + DfgVertexVar(DfgGraph& dfg, VDfgType type, AstVarScope* vscp) + : DfgVertexVar{dfg, type, vscp->varp(), vscp} {} public: - inline DfgVertexVar(DfgGraph& dfg, VDfgType type, AstVar* varp); - inline DfgVertexVar(DfgGraph& dfg, VDfgType type, AstVarScope* vscp); - inline ~DfgVertexVar(); + ~DfgVertexVar() { + // Decrement reference count + AstNode* const variablep = nodep(); + variablep->user1(variablep->user1() - 0x10); + UASSERT_OBJ((variablep->user1() >> 4) >= 0, variablep, "Reference count underflow"); + } ASTGEN_MEMBERS_DfgVertexVar; - const std::string srcName(size_t) const override { return ""; } + // The driver of the variable. Might be nullptr if driven exernally (input to DfgGraph). + DfgVertex* srcp() const { return inputp(0); } + void srcp(DfgVertex* vtxp) { inputp(0, vtxp); } + // The default value of the variable. This defines the parts not driven by 'srcp', maybe null + DfgVertex* defaultp() const { return inputp(1); } + void defaultp(DfgVertex* vtxp) { inputp(1, vtxp); } + + std::string srcName(size_t idx) const override final { return idx ? "defaultp" : "srcp"; } + // The Ast variable this vertex representess AstVar* varp() const { return m_varp; } AstVarScope* varScopep() const { return m_varScopep; } AstNode* nodep() const { return m_varScopep ? static_cast(m_varScopep) : static_cast(m_varp); } - FileLine* driverFileLine() const { return m_driverFileLine; } - void driverFileLine(FileLine* flp) { m_driverFileLine = flp; } - + // If this is a temporary, the Ast variable it stands for, or same as + // 'nodep()' if it's a temporary with no associated original Ast variable. AstNode* tmpForp() const { return m_tmpForp; } void tmpForp(AstNode* nodep) { m_tmpForp = nodep; } + // Location of driver of variable (only used if 'srcp' is not a splice) + FileLine* driverFileLine() const { return m_driverFileLine; } + void driverFileLine(FileLine* flp) { m_driverFileLine = flp; } + bool isDrivenFullyByDfg() const { return srcp() && !srcp()->is() && !varp()->isForced() && !varp()->isSigUserRWPublic(); @@ -105,200 +167,133 @@ class DfgVertexVar VL_NOT_FINAL : public DfgVertexUnary { return false; } }; -class DfgVertexSplice VL_NOT_FINAL : public DfgVertexVariadic { -protected: - struct DriverData final { - FileLine* m_flp; // Location of this driver - uint32_t m_lo; // Low index of range driven by this driver - DriverData() = delete; - DriverData(FileLine* flp, uint32_t lo) - : m_flp{flp} - , m_lo{lo} {} - }; - std::vector m_driverData; // Additional data associated with each driver - bool selfEquals(const DfgVertex& that) const override VL_MT_DISABLED; - V3Hash selfHash() const override VL_MT_DISABLED; +class DfgVarArray final : public DfgVertexVar { + friend class DfgVertex; + friend class DfgVisitor; public: - DfgVertexSplice(DfgGraph& dfg, VDfgType type, FileLine* flp, AstNodeDType* dtypep) - : DfgVertexVariadic{dfg, type, flp, dtypep, 2u} { - // Add optional source for 'defaultp' - addSource(); - } - ASTGEN_MEMBERS_DfgVertexSplice; - - std::pair sourceEdges() const override { - const std::pair pair = DfgVertexVariadic::sourceEdges(); - UASSERT_OBJ(pair.second > 0, this, "default driver edge is missing"); - // If it has a default driver that's it - if (pair.first->sourcep()) return pair; - // Otherwise there is one less source - return {pair.first + 1, pair.second - 1}; - } - std::pair sourceEdges() override { - const auto pair = const_cast(this)->sourceEdges(); - return {const_cast(pair.first), pair.second}; + DfgVarArray(DfgGraph& dfg, AstVar* varp) + : DfgVertexVar{dfg, dfgType(), varp} { + UASSERT_OBJ(VN_IS(dtypep(), UnpackArrayDType), varp, "Non array DfgVarArray"); } - - // Named getter/setter for optional default driver - DfgVertex* defaultp() const { return DfgVertexVariadic::source(0); } - void defaultp(DfgVertex* vtxp) { - UASSERT_OBJ(!vtxp->is(), vtxp, "default driver can't be a DfgLogic"); - const bool found = findSourceEdge([vtxp](const DfgEdge& e, size_t) -> bool { // - return e.sourcep() == vtxp; - }); - UASSERT_OBJ(!found, this, "adding existing driver as default"); - DfgVertexVariadic::sourceEdge(0)->relinkSource(vtxp); + DfgVarArray(DfgGraph& dfg, AstVarScope* vscp) + : DfgVertexVar{dfg, dfgType(), vscp} { + UASSERT_OBJ(VN_IS(dtypep(), UnpackArrayDType), vscp, "Non array DfgVarArray"); } + ASTGEN_MEMBERS_DfgVarArray; +}; - // Add resolved driver - void addDriver(FileLine* flp, uint32_t lo, DfgVertex* vtxp) { - UASSERT_OBJ(!vtxp->is(), vtxp, "addDriver called with DfgLogic"); - UASSERT_OBJ(vtxp != defaultp(), this, "adding default driver as resolved"); - m_driverData.emplace_back(flp, lo); - DfgVertexVariadic::addSource()->relinkSource(vtxp); - } +class DfgVarPacked final : public DfgVertexVar { + friend class DfgVertex; + friend class DfgVisitor; - FileLine* driverFileLine(size_t idx) const { - UASSERT_OBJ(!defaultp() || idx > 0, this, "'driverFileLine' called on default driver"); - if (defaultp()) --idx; - return m_driverData.at(idx).m_flp; +public: + DfgVarPacked(DfgGraph& dfg, AstVar* varp) + : DfgVertexVar{dfg, dfgType(), varp} { + UASSERT_OBJ(!VN_IS(dtypep(), UnpackArrayDType), varp, "Array DfgVarPacked"); } - - uint32_t driverLo(size_t idx) const { - UASSERT_OBJ(!defaultp() || idx > 0, this, "'driverLo' called on default driver"); - if (defaultp()) --idx; - const DriverData& dd = m_driverData.at(idx); - return dd.m_lo; + DfgVarPacked(DfgGraph& dfg, AstVarScope* vscp) + : DfgVertexVar{dfg, dfgType(), vscp} { + UASSERT_OBJ(!VN_IS(dtypep(), UnpackArrayDType), vscp, "Array DfgVarPacked"); } + ASTGEN_MEMBERS_DfgVarPacked; +}; - DfgVertex* driverAt(size_t idx) const { - const DfgEdge* const edgep = findSourceEdge([this, idx](const DfgEdge& e, size_t i) { // - // Don't pick the default driver - if (i == 0 && defaultp()) return false; - return driverLo(i) == idx; - }); - return edgep ? edgep->sourcep() : nullptr; - } +//------------------------------------------------------------------------------ +// Nullary vertices - 0 inputs - // If drives the whole result explicitly (not through defaultp), this is - // the actual driver this DfgVertexSplice can be replaced with. - inline DfgVertex* wholep() const; +class DfgVertexNullary VL_NOT_FINAL : public DfgVertex { +protected: + DfgVertexNullary(DfgGraph& dfg, VDfgType type, FileLine* flp, AstNodeDType* dtypep) + : DfgVertex{dfg, type, flp, dtypep} {} - // cppcheck-suppress duplInheritedMember - void resetSources() { - m_driverData.clear(); - // Unlink default driver - DfgVertex* const dp = defaultp(); - DfgVertexVariadic::sourceEdge(0)->unlinkSource(); - // Reset DfgVertexVariadic sources - DfgVertexVariadic::resetSources(); - // Add back the default driver if present - DfgEdge* const edgep = DfgVertexVariadic::addSource(); - if (dp) edgep->relinkSource(dp); - } - - const std::string srcName(size_t idx) const override { - if (idx == 0 && defaultp()) return "default"; - const uint32_t lo = driverLo(idx); - const uint32_t hi = lo + DfgVertexVariadic::source(idx + !defaultp())->size() - 1; - return '[' + std::to_string(hi) + ':' + std::to_string(lo) + ']'; - } +public: + ASTGEN_MEMBERS_DfgVertexNullary; + std::string srcName(size_t) const override final { V3ERROR_NA_RETURN(""); } }; -// === Concrete node types ===================================================== - -// === DfgVertex === -class DfgConst final : public DfgVertex { +class DfgConst final : public DfgVertexNullary { friend class DfgVertex; friend class DfgVisitor; V3Number m_num; // Constant value - bool selfEquals(const DfgVertex& that) const override VL_MT_DISABLED; - V3Hash selfHash() const override VL_MT_DISABLED; + bool selfEquals(const DfgVertex& that) const override { + return num().isCaseEq(that.as()->num()); + } + V3Hash selfHash() const override { return num().toHash(); } public: - inline DfgConst(DfgGraph& dfg, FileLine* flp, const V3Number& num); - inline DfgConst(DfgGraph& dfg, FileLine* flp, uint32_t width, uint32_t value = 0); + DfgConst(DfgGraph& dfg, FileLine* flp, const V3Number& num) + : DfgVertexNullary{dfg, dfgType(), flp, V3Dfg::dtypePacked(num.width())} + , m_num{num} {} + DfgConst(DfgGraph& dfg, FileLine* flp, uint32_t width, uint32_t value) + : DfgVertexNullary{dfg, dfgType(), flp, V3Dfg::dtypePacked(width)} + , m_num{flp, static_cast(width), value} {} + ASTGEN_MEMBERS_DfgConst; V3Number& num() { return m_num; } const V3Number& num() const { return m_num; } - size_t toSizeT() const { - if VL_CONSTEXPR_CXX17 (sizeof(size_t) > sizeof(uint32_t)) { - return static_cast(num().toUQuad()); - } - return static_cast(num().toUInt()); - } - - uint32_t toU32() const { return static_cast(num().toUInt()); } + size_t toSizeT() const { return static_cast(num().toUQuad()); } + uint32_t toU32() const { return num().toUInt(); } - // cppcheck-suppress duplInheritedMember bool isZero() const { return num().isEqZero(); } - // cppcheck-suppress duplInheritedMember bool isOnes() const { return num().isEqAllOnes(width()); } // Does this DfgConst have the given value? Note this is not easy to answer if wider than 32. bool hasValue(uint32_t value) const { return !num().isFourState() && num().edataWord(0) == value && num().mostSetBitP1() <= 32; } - - std::pair sourceEdges() override { return {nullptr, 0}; } - std::pair sourceEdges() const override { return {nullptr, 0}; } - const string srcName(size_t) const override { // LCOV_EXCL_START - VL_UNREACHABLE; - return ""; - } // LCOV_EXCL_STOP }; -// === DfgVertexBinary === -class DfgMux final : public DfgVertexBinary { - // AstSel is ternary, but the 'widthp' is always constant and is hence redundant, and - // 'lsbp' is very often constant. As AstSel is fairly common, we special case as a DfgSel for - // the constant 'lsbp', and as 'DfgMux` for the non-constant 'lsbp'. -public: - DfgMux(DfgGraph& dfg, FileLine* flp, AstNodeDType* dtypep) - : DfgVertexBinary{dfg, dfgType(), flp, dtypep} {} - ASTGEN_MEMBERS_DfgMux; +//------------------------------------------------------------------------------ +// Unary vertices - 1 inputs - DfgVertex* fromp() const { return source<0>(); } - void fromp(DfgVertex* vtxp) { relinkSource<0>(vtxp); } - DfgVertex* lsbp() const { return source<1>(); } - void lsbp(DfgVertex* vtxp) { relinkSource<1>(vtxp); } +class DfgVertexUnary VL_NOT_FINAL : public DfgVertex { +protected: + DfgVertexUnary(DfgGraph& dfg, VDfgType type, FileLine* flp, AstNodeDType* dtypep) + : DfgVertex{dfg, type, flp, dtypep} { + newInput(); + } - const string srcName(size_t idx) const override { return idx ? "lsbp" : "fromp"; } +public: + ASTGEN_MEMBERS_DfgVertexUnary; + DfgVertex* srcp() const { return inputp(0); } + void srcp(DfgVertex* vtxp) { inputp(0, vtxp); } + std::string srcName(size_t) const override final { return ""; } }; -// === DfgVertexUnary === - class DfgSel final : public DfgVertexUnary { - // AstSel is ternary, but the 'widthp' is always constant and is hence redundant, and - // 'lsbp' is very often constant. As AstSel is fairly common, we special case as a DfgSel for - // the constant 'lsbp', and as 'DfgMux` for the non-constant 'lsbp'. + // AstSel is binary, but 'lsbp' is very often constant. As AstSel is fairly + // common, we special case as a DfgSel for the constant 'lsbp', and as + // 'DfgMux` for the non-constant 'lsbp'. uint32_t m_lsb = 0; // The LSB index - bool selfEquals(const DfgVertex& that) const override VL_MT_DISABLED; - V3Hash selfHash() const override VL_MT_DISABLED; + bool selfEquals(const DfgVertex& that) const override { + return lsb() == that.as()->lsb(); + } + V3Hash selfHash() const override { return V3Hash{lsb()}; } public: DfgSel(DfgGraph& dfg, FileLine* flp, AstNodeDType* dtypep) : DfgVertexUnary{dfg, dfgType(), flp, dtypep} {} ASTGEN_MEMBERS_DfgSel; - DfgVertex* fromp() const { return source<0>(); } - void fromp(DfgVertex* vtxp) { relinkSource<0>(vtxp); } + DfgVertex* fromp() const { return srcp(); } + void fromp(DfgVertex* vtxp) { srcp(vtxp); } uint32_t lsb() const { return m_lsb; } void lsb(uint32_t value) { m_lsb = value; } - - const string srcName(size_t) const override { return "fromp"; } }; class DfgUnitArray final : public DfgVertexUnary { // This is a type adapter for modeling arrays. It's a single element array, // with the value of the single element being the source operand. + bool selfEquals(const DfgVertex&) const final { return true; } + V3Hash selfHash() const final { return V3Hash{}; } + public: DfgUnitArray(DfgGraph& dfg, FileLine* flp, AstNodeDType* dtypep) : DfgVertexUnary{dfg, dfgType(), flp, dtypep} { @@ -306,116 +301,273 @@ class DfgUnitArray final : public DfgVertexUnary { UASSERT_OBJ(this->size() == 1, flp, "DfgUnitArray must have a single element"); } ASTGEN_MEMBERS_DfgUnitArray; +}; - const std::string srcName(size_t) const override { return ""; } +//------------------------------------------------------------------------------ +// Binary vertices - 2 inputs + +class DfgVertexBinary VL_NOT_FINAL : public DfgVertex { +protected: + DfgVertexBinary(DfgGraph& dfg, VDfgType type, FileLine* flp, AstNodeDType* dtypep) + : DfgVertex{dfg, type, flp, dtypep} { + newInput(); + newInput(); + } + +public: + ASTGEN_MEMBERS_DfgVertexBinary; }; -// === DfgVertexVar === -class DfgVarArray final : public DfgVertexVar { - friend class DfgVertex; - friend class DfgVisitor; +class DfgMux final : public DfgVertexBinary { + // AstSel is binary, but 'lsbp' is very often constant. As AstSel is fairly + // common, we special case as a DfgSel for the constant 'lsbp', and as + // 'DfgMux` for the non-constant 'lsbp'. + bool selfEquals(const DfgVertex&) const override { return true; } + V3Hash selfHash() const override { return V3Hash{}; } public: - DfgVarArray(DfgGraph& dfg, AstVar* varp) - : DfgVertexVar{dfg, dfgType(), varp} { - UASSERT_OBJ(VN_IS(dtypep(), UnpackArrayDType), varp, "Non array DfgVarArray"); + DfgMux(DfgGraph& dfg, FileLine* flp, AstNodeDType* dtypep) + : DfgVertexBinary{dfg, dfgType(), flp, dtypep} {} + ASTGEN_MEMBERS_DfgMux; + + DfgVertex* fromp() const { return inputp(0); } + void fromp(DfgVertex* vtxp) { inputp(0, vtxp); } + DfgVertex* lsbp() const { return inputp(1); } + void lsbp(DfgVertex* vtxp) { inputp(1, vtxp); } + + std::string srcName(size_t idx) const override { return idx ? "lsbp" : "fromp"; } +}; + +//------------------------------------------------------------------------------ +// Ternary vertices - 3 inputs + +class DfgVertexTernary VL_NOT_FINAL : public DfgVertex { +protected: + DfgVertexTernary(DfgGraph& dfg, VDfgType type, FileLine* flp, AstNodeDType* dtypep) + : DfgVertex{dfg, type, flp, dtypep} { + newInput(); + newInput(); + newInput(); } - DfgVarArray(DfgGraph& dfg, AstVarScope* vscp) - : DfgVertexVar{dfg, dfgType(), vscp} { - UASSERT_OBJ(VN_IS(dtypep(), UnpackArrayDType), vscp, "Non array DfgVarArray"); + +public: + ASTGEN_MEMBERS_DfgVertexTernary; +}; + +//------------------------------------------------------------------------------ +// Variadic vertices - variable number of inputs + +class DfgVertexVariadic VL_NOT_FINAL : public DfgVertex { +protected: + DfgVertexVariadic(DfgGraph& dfg, VDfgType type, FileLine* flp, AstNodeDType* dtypep) + : DfgVertex{dfg, type, flp, dtypep} {} + +public: + ASTGEN_MEMBERS_DfgVertexVariadic; +}; + +class DfgVertexSplice VL_NOT_FINAL : public DfgVertexVariadic { + // Represents a partial update to a varibale + + struct DriverData final { + uint32_t m_lo; // Low index of range driven by this driver + FileLine* m_flp; // Location of this driver + DriverData() = delete; + DriverData(uint32_t lo, FileLine* flp) + : m_lo{lo} + , m_flp{flp} {} + }; + std::vector m_driverData; // Additional data associated with each driver + + bool selfEquals(const DfgVertex& that) const override final { + const DfgVertexSplice* const thatp = that.as(); + for (size_t i = 0; i < nInputs(); ++i) { + if (m_driverData[i].m_lo != thatp->m_driverData[i].m_lo) return false; + } + return true; + } + V3Hash selfHash() const override final { + V3Hash hash; + const size_t n = nInputs(); + for (size_t i = 0; i < n; ++i) hash += m_driverData[i].m_lo; + return hash; + } + +protected: + DfgVertexSplice(DfgGraph& dfg, VDfgType type, FileLine* flp, AstNodeDType* dtypep) + : DfgVertexVariadic{dfg, type, flp, dtypep} {} + +public: + ASTGEN_MEMBERS_DfgVertexSplice; + + // Add driver + void addDriver(DfgVertex* vtxp, uint32_t lo, FileLine* flp) { + UASSERT_OBJ(!vtxp->is(), vtxp, "addDriver called with DfgLogic"); + m_driverData.emplace_back(lo, flp); + newInput()->relinkSrcp(vtxp); + } + + void resetDrivers() { + resetInputs(); + m_driverData.clear(); + } + + std::string srcName(size_t idx) const override final { + const uint32_t lo = m_driverData[idx].m_lo; + const uint32_t hi = lo + inputp(idx)->size() - 1; + return '[' + std::to_string(hi) + ':' + std::to_string(lo) + ']'; + } + + FileLine* driverFileLine(size_t idx) const { return m_driverData.at(idx).m_flp; } + + DfgVertex* driverAt(size_t idx) { + const size_t n = nInputs(); + for (size_t i = 0; i < n; ++i) { + if (m_driverData[i].m_lo == idx) return inputp(i); + } + return nullptr; + } + + const DfgVertex* driverAt(size_t idx) const { + for (const DriverData& dd : m_driverData) { + if (dd.m_lo == idx) return inputp(idx); + } + return nullptr; + } + + // If drives the whole result explicitly (not through defaultp), this is + // the actual driver this DfgVertexSplice can be replaced with. + DfgVertex* wholep() { + if (nInputs() != 1) return nullptr; + if (m_driverData[0].m_lo != 0) return nullptr; + DfgVertex* const vtxp = inputp(0); + if (vtxp->size() != size()) return nullptr; + if (const DfgUnitArray* const uap = vtxp->cast()) { + if (DfgVertexSplice* const splicep = uap->srcp()->cast()) { + if (!splicep->wholep()) return nullptr; + } + } + return vtxp; + } + + bool foreachDriver(std::function f) { + const size_t n = nInputs(); + for (size_t i = 0; i < n; ++i) { + if (f(*inputp(i), m_driverData[i].m_lo, m_driverData[i].m_flp)) return true; + } + return false; + } + bool foreachDriver(std::function f) const { + const size_t n = nInputs(); + for (size_t i = 0; i < n; ++i) { + if (f(*inputp(i), m_driverData[i].m_lo, m_driverData[i].m_flp)) return true; + } + return false; + } + bool foreachDriver(std::function f) { + const size_t n = nInputs(); + for (size_t i = 0; i < n; ++i) { + if (f(*inputp(i), m_driverData[i].m_lo)) return true; + } + return false; + } + bool foreachDriver(std::function f) const { + const size_t n = nInputs(); + for (size_t i = 0; i < n; ++i) { + if (f(*inputp(i), m_driverData[i].m_lo)) return true; + } + return false; } - ASTGEN_MEMBERS_DfgVarArray; }; -class DfgVarPacked final : public DfgVertexVar { + +class DfgSpliceArray final : public DfgVertexSplice { friend class DfgVertex; friend class DfgVisitor; public: - DfgVarPacked(DfgGraph& dfg, AstVar* varp) - : DfgVertexVar{dfg, dfgType(), varp} { - UASSERT_OBJ(!VN_IS(dtypep(), UnpackArrayDType), varp, "Array DfgVarPacked"); + DfgSpliceArray(DfgGraph& dfg, FileLine* flp, AstNodeDType* dtypep) + : DfgVertexSplice{dfg, dfgType(), flp, dtypep} { + UASSERT_OBJ(VN_IS(dtypep, UnpackArrayDType), flp, "Non array DfgSpliceArray"); } - DfgVarPacked(DfgGraph& dfg, AstVarScope* vscp) - : DfgVertexVar{dfg, dfgType(), vscp} { - UASSERT_OBJ(!VN_IS(dtypep(), UnpackArrayDType), vscp, "Array DfgVarPacked"); + ASTGEN_MEMBERS_DfgSpliceArray; +}; + +class DfgSplicePacked final : public DfgVertexSplice { + friend class DfgVertex; + friend class DfgVisitor; + +public: + DfgSplicePacked(DfgGraph& dfg, FileLine* flp, AstNodeDType* dtypep) + : DfgVertexSplice{dfg, dfgType(), flp, dtypep} { + UASSERT_OBJ(!VN_IS(dtypep, UnpackArrayDType), flp, "Array DfgSplicePacked"); } - ASTGEN_MEMBERS_DfgVarPacked; + ASTGEN_MEMBERS_DfgSplicePacked; }; -// === DfgVertexVariadic === class DfgLogic final : public DfgVertexVariadic { // Generic vertex representing a whole combinational process AstNode* const m_nodep; // The Ast logic represented by this vertex + AstScope* const m_scopep; // The AstScope m_nodep is under, iff scoped const std::unique_ptr m_cfgp; // Vertices this logic was synthesized into. Excluding variables std::vector m_synth; + // Used very early, should never be needed + bool selfEquals(const DfgVertex&) const final { V3ERROR_NA_RETURN(false); } + V3Hash selfHash() const final { V3ERROR_NA_RETURN(V3Hash{}); } + public: - DfgLogic(DfgGraph& dfg, AstAssignW* nodep) - : DfgVertexVariadic{dfg, dfgType(), nodep->fileline(), nullptr, 1u} + DfgLogic(DfgGraph& dfg, AstAssignW* nodep, AstScope* scopep) + : DfgVertexVariadic{dfg, dfgType(), nodep->fileline(), nullptr} , m_nodep{nodep} + , m_scopep{scopep} , m_cfgp{nullptr} {} - DfgLogic(DfgGraph& dfg, AstAlways* nodep, std::unique_ptr cfgp) - : DfgVertexVariadic{dfg, dfgType(), nodep->fileline(), nullptr, 1u} + DfgLogic(DfgGraph& dfg, AstAlways* nodep, AstScope* scopep, std::unique_ptr cfgp) + : DfgVertexVariadic{dfg, dfgType(), nodep->fileline(), nullptr} , m_nodep{nodep} + , m_scopep{scopep} , m_cfgp{std::move(cfgp)} {} ASTGEN_MEMBERS_DfgLogic; - void addInput(DfgVertexVar* varp) { addSource()->relinkSource(varp); } + std::string srcName(size_t) const override final { return ""; } + // Can only be driven by DfgVertexVar + void addInput(DfgVertexVar* varp) { newInput()->relinkSrcp(varp); } + + // Accessors AstNode* nodep() const { return m_nodep; } + AstScope* scopep() const { return m_scopep; } CfgGraph& cfg() { return *m_cfgp; } const CfgGraph& cfg() const { return *m_cfgp; } std::vector& synth() { return m_synth; } const std::vector& synth() const { return m_synth; } - - const std::string srcName(size_t) const override { return ""; } }; class DfgUnresolved final : public DfgVertexVariadic { // Represents a collection of unresolved variable drivers before synthesis + bool selfEquals(const DfgVertex&) const final { return true; } + V3Hash selfHash() const final { return V3Hash{}; } + public: DfgUnresolved(DfgGraph& dfg, const DfgVertexVar* vtxp) - : DfgVertexVariadic{dfg, dfgType(), vtxp->fileline(), vtxp->dtypep(), 1u} {} + : DfgVertexVariadic{dfg, dfgType(), vtxp->fileline(), vtxp->dtypep()} {} ASTGEN_MEMBERS_DfgUnresolved; - // Can only be driven by DfgLogic or DfgVertexSplice - void addDriver(DfgLogic* vtxp) { addSource()->relinkSource(vtxp); } - void addDriver(DfgVertexSplice* vtxp) { addSource()->relinkSource(vtxp); } + std::string srcName(size_t) const override final { return ""; } - // cppcheck-suppress duplInheritedMember - void clearSources() { DfgVertexVariadic::clearSources(); } - - DfgVertex* singleSource() const { return arity() == 1 ? source(0) : nullptr; } - - const std::string srcName(size_t) const override { return ""; } + // Can only be driven by DfgLogic or DfgVertexSplice + void addDriver(DfgLogic* vtxp) { newInput()->relinkSrcp(vtxp); } + void addDriver(DfgVertexSplice* vtxp) { newInput()->relinkSrcp(vtxp); } }; -// === DfgVertexSplice === -class DfgSpliceArray final : public DfgVertexSplice { - friend class DfgVertex; - friend class DfgVisitor; - -public: - DfgSpliceArray(DfgGraph& dfg, FileLine* flp, AstNodeDType* dtypep) - : DfgVertexSplice{dfg, dfgType(), flp, dtypep} { - UASSERT_OBJ(VN_IS(dtypep, UnpackArrayDType), flp, "Non array DfgSpliceArray"); - } - ASTGEN_MEMBERS_DfgSpliceArray; -}; -class DfgSplicePacked final : public DfgVertexSplice { - friend class DfgVertex; - friend class DfgVisitor; +//------------------------------------------------------------------------------ +// The rest of the vertex types are generated by 'astgen' from AstNodeExpr +#include "V3Dfg__gen_auto_classes.h" -public: - DfgSplicePacked(DfgGraph& dfg, FileLine* flp, AstNodeDType* dtypep) - : DfgVertexSplice{dfg, dfgType(), flp, dtypep} { - UASSERT_OBJ(!VN_IS(dtypep, UnpackArrayDType), flp, "Array DfgSplicePacked"); - } - ASTGEN_MEMBERS_DfgSplicePacked; -}; +//------------------------------------------------------------------------------ +// Inline method definitions #endif diff --git a/src/astgen b/src/astgen index d36d6fd5921..57d17bb8dff 100755 --- a/src/astgen +++ b/src/astgen @@ -678,6 +678,10 @@ def check_types(sortedTypes, prefix, abstractPrefix): sys.exit("%Error: Non-final {b} subclasses must be named {b}*: {p}{n}".format( b=baseClass, p=prefix, n=node.name)) + # Skip ordering check for Dfg + if prefix == "Dfg": + return + # Check ordering of node definitions hasOrderingError = False @@ -1169,6 +1173,9 @@ def write_dfg_macros(filename): " ").format(**fmt).replace("\n", " \\\n")) for node in DfgVertexList: + if node.isRoot: + continue + fh.write("#define ASTGEN_MEMBERS_Dfg{t} \\\n".format(t=node.name)) if node.isLeaf: @@ -1183,22 +1190,24 @@ def write_dfg_macros(filename): for n in range(1, node.arity + 1): name, _, _, _ = node.getOp(n) emitBlock('''\ - DfgVertex* {name}() const {{ return source<{n}>(); }} - void {name}(DfgVertex* vtxp) {{ relinkSource<{n}>(vtxp); }} + DfgVertex* {name}() const {{ return inputp({n}); }} + void {name}(DfgVertex* vtxp) {{ inputp({n}, vtxp); }} ''', name=name, n=n - 1) - operandNames = tuple(node.getOp(n)[0] for n in range(1, node.arity + 1)) - if operandNames: - emitBlock('''\ - const std::string srcName(size_t idx) const override {{ - static const char* names[{a}] = {{ {ns} }}; - return names[idx]; - }} - ''', - a=node.arity, - ns=", ".join(map(lambda _: '"' + _ + '"', operandNames))) + if node.isLeaf and node.arity > 1: + operandNames = tuple(node.getOp(n)[0] for n in range(1, node.arity + 1)) + if operandNames: + emitBlock('''\ + std::string srcName(size_t idx) const override final {{ + static const char* names[{a}] = {{ {ns} }}; + return names[idx]; + }} + ''', + a=node.arity, + ns=", ".join(map(lambda _: '"' + _ + '"', operandNames))) + fh.write(" static_assert(true, \"\")\n") # Swallowing the semicolon @@ -1215,6 +1224,8 @@ def write_dfg_auto_classes(filename): emitBlock('''\ class Dfg{t} final : public Dfg{s} {{ + bool selfEquals(const DfgVertex&) const final {{ return true; }} + V3Hash selfHash() const final {{ return V3Hash{{}}; }} public: Dfg{t}(DfgGraph& dfg, FileLine* flp, AstNodeDType* dtypep) : Dfg{s}{{dfg, dfgType(), flp, dtypep}} {{}} @@ -1275,12 +1286,12 @@ def write_dfg_ast_to_dfg(filename): fh.write(" m_foundUnhandled = true;\n") fh.write(" ++m_ctx.m_conv.nonRepNode;\n") fh.write(" return;\n") - fh.write(" }\n\n") - fh.write(" m_logicp->synth().emplace_back(vtxp);") + fh.write(" }\n") + fh.write(" m_logicp->synth().emplace_back(vtxp);\n\n") for i in range(node.arity): fh.write( - " vtxp->relinkSource<{i}>(nodep->op{j}p()->user2u().to());\n". - format(i=i, j=i + 1)) + " vtxp->inputp({i}, nodep->op{j}p()->user2u().to());\n".format( + i=i, j=i + 1)) fh.write("\n") fh.write(" nodep->user2p(vtxp);\n") fh.write("}\n") @@ -1296,7 +1307,7 @@ def write_dfg_dfg_to_ast(filename): fh.write("void visit(Dfg{t}* vtxp) override {{\n".format(t=node.name)) for i in range(node.arity): fh.write( - " AstNodeExpr* const op{j}p = convertDfgVertexToAstNodeExpr(vtxp->source<{i}>());\n" + " AstNodeExpr* const op{j}p = convertDfgVertexToAstNodeExpr(vtxp->inputp({i}));\n" .format(i=i, j=i + 1)) fh.write(" m_resultp = makeNode(vtxp".format(t=node.name)) for i in range(node.arity): @@ -1355,14 +1366,6 @@ check_types(AstNodeList, "Ast", "Node") # Set up the root DfgVertex type and some other hand-written base types. # These are standalone so we don't need to parse the sources for this. DfgVertices["Vertex"] = Node("Vertex", None) -DfgVertices["VertexUnary"] = Node("VertexUnary", DfgVertices["Vertex"]) -DfgVertices["Vertex"].addSubClass(DfgVertices["VertexUnary"]) -DfgVertices["VertexBinary"] = Node("VertexBinary", DfgVertices["Vertex"]) -DfgVertices["Vertex"].addSubClass(DfgVertices["VertexBinary"]) -DfgVertices["VertexTernary"] = Node("VertexTernary", DfgVertices["Vertex"]) -DfgVertices["Vertex"].addSubClass(DfgVertices["VertexTernary"]) -DfgVertices["VertexVariadic"] = Node("VertexVariadic", DfgVertices["Vertex"]) -DfgVertices["Vertex"].addSubClass(DfgVertices["VertexVariadic"]) # AstNodeExpr that are not representable in Dfg DfgIgnored = ( @@ -1424,6 +1427,7 @@ DfgIgnored = ( "ReplicateN", "SubstrN", "ToLowerN", + "ToStringN", "ToUpperN", # Effectful "PostAdd", diff --git a/src/cppcheck-suppressions.txt b/src/cppcheck-suppressions.txt index 3d416bba9b2..431056957da 100644 --- a/src/cppcheck-suppressions.txt +++ b/src/cppcheck-suppressions.txt @@ -39,7 +39,9 @@ unusedPrivateFunction:src/V3Const.cpp // These are all inappropriate constVariablePointer:src/V3DfgPeephole.cpp constParameterPointer:src/V3DfgPeephole.cpp - +// Class in non-copyable +noCopyConstructor:src/V3DfgDfgToAst.cpp +noOperatorEq:src/V3DfgDfgToAst.cpp // TODO: these need fixing/signing off in source constParameterPointer:src/V3EmitCFunc.cpp diff --git a/test_regress/t/t_dfg_synthesis_pre_inline.cpp b/test_regress/t/t_dfg_synthesis_pre_inline.cpp new file mode 100644 index 00000000000..0664397e10e --- /dev/null +++ b/test_regress/t/t_dfg_synthesis_pre_inline.cpp @@ -0,0 +1,60 @@ +// +// DESCRIPTION: Verilator: DFG optimizer equivalence testing +// +// This file ONLY is placed under the Creative Commons Public Domain, for +// any use, without warranty, 2022 by Geza Lore. +// SPDX-License-Identifier: CC0-1.0 +// + +#include +#include + +#include +#include +#include + +void rngUpdate(uint64_t& x) { + x ^= x << 13; + x ^= x >> 7; + x ^= x << 17; +} + +int main(int, char**) { + // Create contexts + VerilatedContext ctx; + + // Create models + Vref ref{&ctx}; + Vopt opt{&ctx}; + + uint64_t rand_a = 0x5aef0c8dd70a4497; + uint64_t rand_b = 0xf0c0a8dd75ae4497; + uint64_t srand_a = 0x00fa8dcc7ae4957; + uint64_t srand_b = 0x0fa8dc7ae3c9574; + + for (size_t n = 0; n < 200000; ++n) { + // Update rngs + rngUpdate(rand_a); + rngUpdate(rand_b); + rngUpdate(srand_a); + rngUpdate(srand_b); + + // Assign inputs + ref.rand_a = opt.rand_a = rand_a; + ref.rand_b = opt.rand_b = rand_b; + ref.srand_a = opt.srand_a = srand_a; + ref.srand_b = opt.srand_b = srand_b; + + // Evaluate both models + ref.eval(); + opt.eval(); + + // Check equivalence +#include "checks.h" + + // increment time + ctx.timeInc(1); + } + + std::cout << "*-* All Finished *-*\n"; +} diff --git a/test_regress/t/t_dfg_synthesis_pre_inline.py b/test_regress/t/t_dfg_synthesis_pre_inline.py new file mode 100755 index 00000000000..011b93e99cd --- /dev/null +++ b/test_regress/t/t_dfg_synthesis_pre_inline.py @@ -0,0 +1,100 @@ +#!/usr/bin/env python3 +# DESCRIPTION: Verilator: Verilog Test driver/expect definition +# +# Copyright 2025 by Wilson Snyder. This program is free software; you +# can redistribute it and/or modify it under the terms of either the GNU +# Lesser General Public License Version 3 or the Perl Artistic License +# Version 2.0. +# SPDX-License-Identifier: LGPL-3.0-only OR Artistic-2.0 + +import vltest_bootstrap + +test.scenarios('vlt_all') +test.sim_time = 2000000 + +root = ".." + +if not os.path.exists(root + "/.git"): + test.skip("Not in a git repository") + +# Generate the equivalence checks and declaration boilerplate +rdFile = test.top_filename +plistFile = test.obj_dir + "/portlist.vh" +pdeclFile = test.obj_dir + "/portdecl.vh" +checkFile = test.obj_dir + "/checks.h" +nAlwaysSynthesized = 0 +nAlwaysNotSynthesized = 0 +nAlwaysReverted = 0 +with open(rdFile, 'r', encoding="utf8") as rdFh, \ + open(plistFile, 'w', encoding="utf8") as plistFh, \ + open(pdeclFile, 'w', encoding="utf8") as pdeclFh, \ + open(checkFile, 'w', encoding="utf8") as checkFh: + for line in rdFh: + if re.search(r'^\s*always.*//\s*nosynth$', line): + nAlwaysNotSynthesized += 1 + elif re.search(r'^\s*always.*//\s*revert$', line): + nAlwaysReverted += 1 + elif re.search(r'^\s*always', line): + nAlwaysSynthesized += 1 + line = line.split("//")[0] + m = re.search(r'`signal\((\w+),', line) + if not m: + continue + sig = m.group(1) + plistFh.write(sig + ",\n") + pdeclFh.write("output " + sig + ";\n") + checkFh.write("if (ref." + sig + " != opt." + sig + ") {\n") + checkFh.write(" std::cout << \"Mismatched " + sig + "\" << std::endl;\n") + checkFh.write(" std::cout << \"Ref: 0x\" << std::hex << (ref." + sig + + " + 0) << std::endl;\n") + checkFh.write(" std::cout << \"Opt: 0x\" << std::hex << (opt." + sig + + " + 0) << std::endl;\n") + checkFh.write(" std::exit(1);\n") + checkFh.write("}\n") + +# Compile un-optimized +test.compile(verilator_flags2=[ + "--stats", + "--build", + "-fno-dfg", + "+incdir+" + test.obj_dir, + "-Mdir", test.obj_dir + "/obj_ref", + "--prefix", "Vref", + "-Wno-UNOPTFLAT" +]) # yapf:disable + +test.file_grep_not(test.obj_dir + "/obj_ref/Vref__stats.txt", r'DFG.*Synthesis') + +# Compile optimized - also builds executable +test.compile(verilator_flags2=[ + "--stats", + "--build", + "--fdfg-synthesize-all", + "-fno-dfg-post-inline", + "-fno-dfg-scoped", + "--exe", + "+incdir+" + test.obj_dir, + "-Mdir", test.obj_dir + "/obj_opt", + "--prefix", "Vopt", + "-fno-const-before-dfg", # Otherwise V3Const makes testing painful + "-fno-split", # Dfg will take care of it + "--debug", "--debugi", "0", "--dumpi-tree", "0", + "-CFLAGS \"-I .. -I ../obj_ref\"", + "../obj_ref/Vref__ALL.a", + "../../t/" + test.name + ".cpp" +]) # yapf:disable + +test.file_grep(test.obj_dir + "/obj_opt/Vopt__stats.txt", + r'DFG pre inline Synthesis, synt / always blocks considered\s+(\d+)$', + nAlwaysSynthesized + nAlwaysReverted + nAlwaysNotSynthesized) +test.file_grep(test.obj_dir + "/obj_opt/Vopt__stats.txt", + r'DFG pre inline Synthesis, synt / always blocks synthesized\s+(\d+)$', + nAlwaysSynthesized + nAlwaysReverted) +test.file_grep(test.obj_dir + "/obj_opt/Vopt__stats.txt", + r'DFG pre inline Synthesis, synt / reverted \(multidrive\)\s+(\d)$', + nAlwaysReverted) + +# Execute test to check equivalence +test.execute(executable=test.obj_dir + "/obj_opt/Vopt") + +test.passes() diff --git a/test_regress/t/t_dfg_synthesis_pre_inline.v b/test_regress/t/t_dfg_synthesis_pre_inline.v new file mode 100644 index 00000000000..5c00f54c8c5 --- /dev/null +++ b/test_regress/t/t_dfg_synthesis_pre_inline.v @@ -0,0 +1,34 @@ +// DESCRIPTION: Verilator: Verilog Test module +// +// This file ONLY is placed under the Creative Commons Public Domain, for +// any use, without warranty, 2025 by Geza Lore. +// SPDX-License-Identifier: CC0-1.0 + +`define signal(name, expr) wire [$bits(expr)-1:0] ``name = expr + +module t ( +`include "portlist.vh" // Boilerplate generated by t_dfg_break_cycles.py + rand_a, rand_b, srand_a, srand_b +); + +`include "portdecl.vh" // Boilerplate generated by t_dfg_break_cycles.py + + input rand_a; + input rand_b; + input srand_a; + input srand_b; + wire logic [63:0] rand_a; + wire logic [63:0] rand_b; + wire logic signed [63:0] srand_a; + wire logic signed [63:0] srand_b; + + ////////////////////////////////////////////////////////////////////////// + + logic concat_lhs_a; + logic concat_lhs_b; + always_comb begin + {concat_lhs_a, concat_lhs_b} = rand_a[1:0] + rand_b[1:0]; + end + `signal(CONCAT_LHS, {concat_lhs_a, concat_lhs_b}); + +endmodule