EDA开源仿真工具verilator入门2:主要数据结构介绍

本节将介绍下verilator所用到的主要数据结构。

AstNode

AstNode类：

class AstNode VL_NOT_FINAL {// v ASTNODE_PREFETCH depends on below ordering of membersAstNode* m_nextp = nullptr;  // Next peer in the parent's listAstNode* m_backp = nullptr;  // Node that points to this one (via next/op1/op2/...)AstNode* m_op1p = nullptr;  // Generic pointer 1AstNode* m_op2p = nullptr;  // Generic pointer 2AstNode* m_op3p = nullptr;  // Generic pointer 3AstNode* m_op4p = nullptr;  // Generic pointer 4AstNode** m_iterpp= nullptr;  // Pointer to node iterating on, change it if we replace this node.const VNType m_type;  // Node sub-type identifier// ^ ASTNODE_PREFETCH depends on above ordering of members// VNType is 2 bytes, so we can stick another 6 bytes after it to utilize what would// otherwise be padding (on a 64-bit system). We stick the attribute flags, broken state,// and the clone count here.

AST（抽象语法树）在最顶层由类AstNode表示，AstNode是抽象类，其派生类对应某个单一元件或者多组元件。例如：

AstGenerate:对应的是一个generate block；

AstNodeFTask:对应functions和tasks，进一步会生成派生类：AstFunc和AstTask；

AstNode有一个重要特性type hierarchy（类型层次结构），即所有子类如果不是final，那么其必须是抽象类，并且类名前缀为AstNode*。astgen脚本就是基于此（后面会介绍）。

每个AstNode有4个指向子节点的指针，可以通过op1p-op4p方法来访问。这些方法在继承类中会被更具体的方法调用，例如AstIf类（处理if表达式），ifsp调用op2p给出对应then语句block的AST指针，elsesp调用op3p给出对应else语句block的AST指针，当然不存在的话，指针为空。

AstNode具有下一个（next）和前一个（previous） AST的概念，例如一个block中的next语句和previous语句。这类语句的AST指针可以通过back和next的方法获取。

AstNetlist在树结构的最顶端，所以检查这个类是判断是否在树结构顶端的标准方法。

为了方便，每一个函数或者方法使用变量指针nodep指向当前处理的AstNode。

VNVisitor

VNVisitor类：

class VNVisitor VL_NOT_FINAL : public VNDeleter {friend class AstNode;public:/// Call visit()s on nodepvoid iterate(AstNode* nodep);/// Call visit()s on nodepvoid iterateNull(AstNode* nodep);/// Call visit()s on nodep's childrenvoid iterateChildren(AstNode* nodep);/// Call visit()s on nodep's children in backp() ordervoid iterateChildrenBackwards(AstNode* nodep);/// Call visit()s on const nodep's childrenvoid iterateChildrenConst(AstNode* nodep);/// Call visit()s on nodep (maybe nullptr) and nodep's nextp() listvoid iterateAndNextNull(AstNode* nodep);/// Call visit()s on const nodep (maybe nullptr) and nodep's nextp() listvoid iterateAndNextConstNull(AstNode* nodep);/// Call visit()s on const nodep (maybe nullptr) and nodep's nextp() list, in reverse ordervoid iterateAndNextConstNullBackwards(AstNode* nodep);/// Return edited nodep; see comments in V3Ast.cppAstNode* iterateSubtreeReturnEdits(AstNode* nodep);#include "V3Ast__gen_visitor.h"  // From ./astgen// Things like://  virtual void visit(AstBreak* nodep) { visit((AstNodeStmt*)(nodep)); }//  virtual void visit(AstNodeStmt* nodep) { visit((AstNode*)(nodep)); }
};

遍历（passes，扫描所有代码的语法树）是通过AST访问者（visitor）类实现的，这些通过抽象类VNVisitor的子类实现，每一个遍历创建一个visitor类的实例来执行方法实现遍历。

V3Graph

V3Graph类：

class V3Graph VL_NOT_FINAL {
private:// MEMBERSV3List m_vertices;  // All verticesstatic int s_debug;protected:friend class V3GraphVertex;friend class V3GraphEdge;friend class GraphAcyc;// METHODSdouble orderDFSIterate(V3GraphVertex* vertexp);void dumpEdge(std::ostream& os, V3GraphVertex* vertexp, V3GraphEdge* edgep);void verticesUnlink() { m_vertices.reset(); }// ACCESSORSstatic int debug();public:V3Graph();virtual ~V3Graph();static void debug(int level) { s_debug = level; }virtual string dotRankDir() const { return "TB"; }  // rankdir for dot plotting// METHODSvoid clear();  // Empty it of all vertices/edges, as if making a new objectvoid clearColors();bool empty() const { return m_vertices.empty(); }V3GraphVertex* verticesBeginp() const { return m_vertices.begin(); }// METHODS - ALGORITHMS/// Assign same color to all vertices in the same weakly connected component/// Thus different color if there's no edges between the two subgraphsvoid weaklyConnected(V3EdgeFuncP edgeFuncp);/// Assign same color to all vertices that are strongly connected/// Thus different color if there's no directional circuit within the subgraphs./// (I.E. all loops will occur within each color, not between them.)void stronglyConnected(V3EdgeFuncP edgeFuncp);/// Assign a ordering number to all vertexes in a tree./// All nodes with no inputs will get rank 1void rank(V3EdgeFuncP edgeFuncp);void rank();/// Sort all vertices and edges using the V3GraphVertex::sortCmp() functionvoid sortVertices();/// Sort all edges and edges using the V3GraphEdge::sortCmp() functionvoid sortEdges();/// Order all vertices by rank and fanout, lowest first/// Sort all vertices by rank and fanout, lowest first/// Sort all edges by weight, lowest first/// Side-effect: assigns ranks to every node.void order();// Similar to order() but does not assign ranks. Caller must// ensure that the graph has been ranked ahead of the call.void orderPreRanked();/// Make acyclical (into a tree) by breaking a minimal subset of cutable edges.void acyclic(V3EdgeFuncP edgeFuncp);/// Remove any redundant edges, weights become MAX of any other weightvoid removeRedundantEdges(V3EdgeFuncP edgeFuncp);/// Remove any redundant edges, weights become SUM of any other weightvoid removeRedundantEdgesSum(V3EdgeFuncP edgeFuncp);/// Remove any transitive edges.  E.g. if have edges A->B, B->C, and A->C/// then A->C is a "transitive" edge; it's implied by the first two/// (assuming the DAG is a dependency graph.)/// This algorithm can be expensive.void removeTransitiveEdges();/// Call loopsVertexCb on any one loop starting where specifiedvoid reportLoops(V3EdgeFuncP edgeFuncp, V3GraphVertex* vertexp);/// Build a subgraph of all loops starting where specifiedvoid subtreeLoops(V3EdgeFuncP edgeFuncp, V3GraphVertex* vertexp, V3Graph* loopGraphp);/// Debuggingvoid dump(std::ostream& os = std::cout);void dumpDotFile(const string& filename, bool colorAsSubgraph) const;void dumpDotFilePrefixed(const string& nameComment, bool colorAsSubgraph = false) const;void dumpDotFilePrefixedAlways(const string& nameComment, bool colorAsSubgraph = false) const;void userClearVertices();void userClearEdges();static void selfTest();// CALLBACKSvirtual void loopsMessageCb(V3GraphVertex* vertexp);virtual void loopsVertexCb(V3GraphVertex* vertexp);
};

一些遍历（passes）算法是通过图算法实现的，类V3Graph用来表示这些图。这些图是有向的，算法用来操纵图并把图结构输出生成 `GraphViz `__ dot格式的文件，V3Graph.h提供了这个类的文档。

V3GraphVertex

V3GraphVertex类：

class V3GraphVertex VL_NOT_FINAL {// Vertices may be a 'gate'/wire statement OR a variable
protected:friend class V3Graph;friend class V3GraphEdge;friend class GraphAcyc;friend class GraphAlgRank;V3ListEnt m_vertices;  // All vertices, linked listV3List m_outs;  // Outbound edges,linked listV3List m_ins;  // Inbound edges, linked listdouble m_fanout;  // Order fanoutuint32_t m_color;  // Color of the nodeuint32_t m_rank;  // Rank of edgeunion {void* m_userp;  // Marker for some algorithmsuint32_t m_user;  // Marker for some algorithms};// METHODSvoid verticesPushBack(V3Graph* graphp);// ACCESSORSvoid fanout(double fanout) { m_fanout = fanout; }void inUnlink() { m_ins.reset(); }  // Low level; normally unlinkDelete is what you wantvoid outUnlink() { m_outs.reset(); }  // Low level; normally unlinkDelete is what you want
protected:// CONSTRUCTORSV3GraphVertex(V3Graph* graphp, const V3GraphVertex& old);public:explicit V3GraphVertex(V3Graph* graphp);//! Clone copy constructor. Doesn't copy edges or user/userp.virtual V3GraphVertex* clone(V3Graph* graphp) const {return new V3GraphVertex(graphp, *this);}virtual ~V3GraphVertex() = default;void unlinkEdges(V3Graph* graphp);void unlinkDelete(V3Graph* graphp);// ACCESSORSvirtual string name() const { return ""; }virtual string dotColor() const { return "black"; }virtual string dotShape() const { return ""; }virtual string dotStyle() const { return ""; }virtual string dotName() const { return ""; }virtual string dotRank() const { return ""; }virtual uint32_t rankAdder() const { return 1; }virtual FileLine* fileline() const { return nullptr; }  // nullptr for unknownvirtual int sortCmp(const V3GraphVertex* rhsp) const {// LHS goes first if of lower rank, or lower fanoutif (m_rank < rhsp->m_rank) return -1;if (m_rank > rhsp->m_rank) return 1;if (m_fanout < rhsp->m_fanout) return -1;if (m_fanout > rhsp->m_fanout) return 1;return 0;}uint32_t color() const { return m_color; }void color(uint32_t color) { m_color = color; }uint32_t rank() const { return m_rank; }void rank(uint32_t rank) { m_rank = rank; }double fanout() const { return m_fanout; }void user(uint32_t user) { m_user = user; }uint32_t user() const { return m_user; }void userp(void* userp) { m_userp = userp; }void* userp() const { return m_userp; }// ITERATORSV3GraphVertex* verticesNextp() const { return m_vertices.nextp(); }V3GraphEdge* inBeginp() const { return m_ins.begin(); }bool inEmpty() const { return inBeginp() == nullptr; }bool inSize1() const;uint32_t inHash() const;V3GraphEdge* outBeginp() const { return m_outs.begin(); }bool outEmpty() const { return outBeginp() == nullptr; }bool outSize1() const;uint32_t outHash() const;V3GraphEdge* beginp(GraphWay way) const { return way.forward() ? outBeginp() : inBeginp(); }// METHODS/// Error reportingvoid v3errorEnd(std::ostringstream& str) const;void v3errorEndFatal(std::ostringstream& str) const;/// Edges are routed around this vertex to point from "from" directly to "to"void rerouteEdges(V3Graph* graphp);/// Find the edge connecting ap and bp, where bp is wayward from ap./// If edge is not found returns nullptr. O(edges) performance.V3GraphEdge* findConnectingEdgep(GraphWay way, const V3GraphVertex* waywardp);
};

V3GraphVertex类是图结构中点对应的基类，Vertex有三个属性：fanout(扇出)、color（点着色）和rank（边排序），这三个属性很有可能用在对图做排序的算法中。此外，还提供了一个通用的user/userp成员变量，用来标记某个算法。

提供了虚拟函数来说明name、color、shape和style特征来输出到dot文件。通常V3GraphVertex的派生类会重写这些方法。

Iterators被用来访问入边和出边，通常的调用形式：

for (V3GraphEdge *edgep = vertexp->inBeginp();edgep;edgep = edgep->inNextp()) {

V3GraphEdge

V3GraphEdge类：

class V3GraphEdge VL_NOT_FINAL {// Wires/variables aren't edges.  Edges have only a single to/from vertex
public:// ENUMSenum Cutable : uint8_t { NOT_CUTABLE = false, CUTABLE = true };  // For passing to V3GraphEdge
protected:friend class V3Graph;friend class V3GraphVertex;friend class GraphAcyc;friend class GraphAcycEdge;V3ListEnt m_outs;  // Next Outbound edge for same vertex (linked list)V3ListEnt m_ins;  // Next Inbound edge for same vertex (linked list)//V3GraphVertex* m_fromp;  // Vertices pointing to this edgeV3GraphVertex* m_top;  // Vertices this edge points toint m_weight;  // Weight of the connectionbool m_cutable;  // Interconnect may be broken in order sortingunion {void* m_userp;  // Marker for some algorithmsuint64_t m_user;  // Marker for some algorithms};// METHODSvoid init(V3Graph* graphp, V3GraphVertex* fromp, V3GraphVertex* top, int weight,bool cutable = false);void cut() { m_weight = 0; }  // 0 weight is same as disconnectedvoid outPushBack();void inPushBack();// CONSTRUCTORS
protected:V3GraphEdge(V3Graph* graphp, V3GraphVertex* fromp, V3GraphVertex* top,const V3GraphEdge& old) {init(graphp, fromp, top, old.m_weight, old.m_cutable);}public://! Add DAG from one node to the specified nodeV3GraphEdge(V3Graph* graphp, V3GraphVertex* fromp, V3GraphVertex* top, int weight,bool cutable = false) {init(graphp, fromp, top, weight, cutable);}//! Clone copy constructor.  Doesn't copy existing vertices or user/userp.virtual V3GraphEdge* clone(V3Graph* graphp, V3GraphVertex* fromp, V3GraphVertex* top) const {return new V3GraphEdge(graphp, fromp, top, *this);}virtual ~V3GraphEdge() = default;// METHODSvirtual string name() const { return m_fromp->name() + "->" + m_top->name(); }virtual string dotLabel() const { return ""; }virtual string dotColor() const { return cutable() ? "yellowGreen" : "red"; }virtual string dotStyle() const { return cutable() ? "dashed" : ""; }virtual int sortCmp(const V3GraphEdge* rhsp) const {if (!m_weight || !rhsp->m_weight) return 0;return top()->sortCmp(rhsp->top());}void unlinkDelete();V3GraphEdge* relinkFromp(V3GraphVertex* newFromp);// ACCESSORSint weight() const { return m_weight; }void weight(int weight) { m_weight = weight; }bool cutable() const { return m_cutable; }void cutable(bool cutable) { m_cutable = cutable; }void userp(void* user) { m_userp = user; }void* userp() const { return m_userp; }void user(uint64_t user) { m_user = user; }uint64_t user() const { return m_user; }V3GraphVertex* fromp() const { return m_fromp; }V3GraphVertex* top() const { return m_top; }V3GraphVertex* closerp(GraphWay way) const { return way.forward() ? fromp() : top(); }V3GraphVertex* furtherp(GraphWay way) const { return way.forward() ? top() : fromp(); }// STATIC ACCESSORSstatic bool followNotCutable(const V3GraphEdge* edgep) { return !edgep->m_cutable; }static bool followAlwaysTrue(const V3GraphEdge*) { return true; }// ITERATORSV3GraphEdge* outNextp() const { return m_outs.nextp(); }V3GraphEdge* inNextp() const { return m_ins.nextp(); }V3GraphEdge* nextp(GraphWay way) const { return way.forward() ? outNextp() : inNextp(); }
};

V3GraphEdge是图结构中有向边的基类，有两个属性：权重（weight）和是否可裁剪（cutable），与V3GraphVertex类似，还提供了一个通用的user/userp成员变量，用来标记某个算法。

访问函数（Accessor）fromp和top分别返回入节点和出节点。提供了虚拟函数来说明label、color和style特征来输出到dot文件。通常V3GraphVertex的派生类会重写这些方法。

V3GraphAlg

GraphAlg类：

template   // Or sometimes const V3Graph
class GraphAlg VL_NOT_FINAL {
protected:T_Graph* const m_graphp;  // Graph we're operating uponconst V3EdgeFuncP m_edgeFuncp;  // Function that says we follow this edge// CONSTRUCTORSGraphAlg(T_Graph* graphp, V3EdgeFuncP edgeFuncp): m_graphp{graphp}, m_edgeFuncp{edgeFuncp} {}~GraphAlg() = default;// METHODSinline bool followEdge(V3GraphEdge* edgep) {return (edgep->weight() && (m_edgeFuncp)(edgep));}
};

GraphAlg是图算法的基类，其执行了一种bool型的followEdge方法来判断是否跟随（follow）一条边，如果改图的边大于0并且edgeFuncp函数（构造函数传入）返回为真那么followEdge函数返回真。

这节先说到这里。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！