parser graph generation support for graphs backend

p4lang · antoninbas · Oct 30, 2017 · Oct 13, 2017 · Oct 13, 2017 · Oct 13, 2017
commit 098e4048310ac69ca3125009e7882e7b55bdfd75
diff --git a/backends/graphs/CMakeLists.txt b/backends/graphs/CMakeLists.txt
@@ -15,10 +15,11 @@
 set (GRAPHS_SRCS
   graphs.cpp
   controls.cpp
+  parser.cpp
   )
 
 set (GRAPHS_HDRS
-  controls.h
+  graphs.h
   )
 
 add_cpplint_files(${CMAKE_CURRENT_SOURCE_DIR} "${GRAPHS_SRCS};${GRAPHS_HDRS}")

diff --git a/backends/graphs/README.md b/backends/graphs/README.md
@@ -1,7 +1,7 @@
 # Graphs Backend
 
 This backend produces visual representations of a P4 program as dot files. For
-now it only supports the generation of graphs for top-level control blocks.
+now it only supports the generation of graphs for top-level control and parser blocks.
 
 ## Dependencies
 
@@ -26,6 +26,12 @@ test program:
 
 ![Flowlet switching ingress graph](resources/flowlet_switching-bmv2.ingress.png)
 
+Here is the graph generated for the parser block of the
+[flowlet_switching-bmv2.p4](../../testdata/p4_16_samples/flowlet_switching-bmv2.p4)
+test program:
+
+![Flowlet switching ingress graph](resources/flowlet_switching-bmv2.parser.png)
+
 For a more complex example, you can look at the control graph generated for the
 egress control of
 [switch.p4](https://github.com/p4lang/switch/tree/f219b4f4e25c2db581f3b91c8da94a7c3ac701a7/p4src)

diff --git a/backends/graphs/controls.cpp b/backends/graphs/controls.cpp
@@ -14,7 +14,7 @@ See the License for the specific language governing permissions and
 limitations under the License.
 */
 
-#include "controls.h"
+#include "graphs.h"
 
 #include <boost/graph/graphviz.hpp>
 
@@ -67,6 +67,18 @@ class EdgeSwitch : public EdgeTypeIface {
     const IR::Expression *labelExpr;
 };
 
+class EdgeSelect : public EdgeTypeIface {
+ public:
+    explicit EdgeSelect(const cstring labelExpr)
+        : labelExpr(labelExpr) { }
+    cstring label() const override {
+        return labelExpr;
+    };
+
+ private:
+    const cstring labelExpr;
+};
+
 using Graph = ControlGraphs::Graph;
 
 Graph *ControlGraphs::ControlStack::pushBack(Graph &currentSubgraph, const cstring &name) {

diff --git a/backends/graphs/graphs.cpp b/backends/graphs/graphs.cpp
@@ -26,7 +26,7 @@ limitations under the License.
 #include "frontends/p4/evaluator/evaluator.h"
 #include "frontends/p4/frontend.h"
 
-#include "controls.h"
+#include "graphs.h"
 
 namespace graphs {
 
@@ -66,6 +66,7 @@ class Options : public CompilerOptions {
      }
 };
 
+
 }  // namespace graphs
 
 int main(int argc, char *const argv[]) {
@@ -117,5 +118,9 @@ int main(int argc, char *const argv[]) {
     graphs::ControlGraphs cgen(&midEnd.refMap, &midEnd.typeMap, options.graphsDir);
     top->getMain()->apply(cgen);
 
+    LOG1("Generating parser graphs");
+    graphs::ParserGraphs pgen(&midEnd.refMap, &midEnd.typeMap, options.graphsDir);
+    top->getMain()->apply(pgen);
+
     return ::errorCount() > 0;
 }
diff --git a/backends/graphs/controls.h → backends/graphs/graphs.h b/backends/graphs/controls.h → backends/graphs/graphs.h
@@ -149,6 +149,78 @@ class ControlGraphs : public Inspector {
     boost::optional<cstring> instanceName{};
 };
 
+
+class ParserGraphs : public Inspector {
+ public:
+    enum class VertexType {
+        HEADER,
+        PARSER,
+		DEFAULT,
+		STATEMENTS
+    };
+    struct Vertex {
+        cstring name;
+        VertexType type;
+    };
+    class GraphAttributeSetter;
+    // The boost graph support for graphviz subgraphs is not very intuitive. In
+    // particular the write_graphviz code assumes the existence of a lot of
+    // properties. See
+    // https://stackoverflow.com/questions/29312444/how-to-write-graphviz-subgraphs-with-boostwrite-graphviz
+    // for more information.
+    using GraphvizAttributes = std::map<cstring, cstring>;
+    using vertexProperties =
+        boost::property<boost::vertex_attribute_t, GraphvizAttributes,
+        Vertex>;
+    using edgeProperties =
+        boost::property<boost::edge_attribute_t, GraphvizAttributes,
+        boost::property<boost::edge_name_t, cstring,
+        boost::property<boost::edge_index_t, int> > >;
+    using graphProperties =
+        boost::property<boost::graph_name_t, cstring,
+        boost::property<boost::graph_graph_attribute_t, GraphvizAttributes,
+        boost::property<boost::graph_vertex_attribute_t, GraphvizAttributes,
+        boost::property<boost::graph_edge_attribute_t, GraphvizAttributes> > > >;
+    using Graph_ = boost::adjacency_list<boost::setS, boost::vecS, boost::directedS,
+                                         vertexProperties, edgeProperties,
+                                         graphProperties>;
+    using Graph = boost::subgraph<Graph_>;
+    using vertex_t = boost::graph_traits<Graph>::vertex_descriptor;
+
+    using Parents = std::vector<std::pair<vertex_t, EdgeTypeIface *> >;
+
+    ParserGraphs(P4::ReferenceMap *refMap, P4::TypeMap *typeMap, const cstring &graphsDir);
+
+    vertex_t add_vertex(const cstring &name, VertexType type);
+    vertex_t add_and_connect_vertex(const cstring &name, VertexType type);
+    void add_edge(const vertex_t &from, const vertex_t &to, const cstring &name);
+
+    bool preorder(const IR::PackageBlock *block) override;
+    bool preorder(const IR::ParserBlock *block) override;
+    bool preorder(const IR::P4Parser *pars) override;
+    bool preorder(const IR::ParserState *state) override;
+
+    void writeGraphToFile(const Graph &g, const cstring &name);
+
+	cstring stringRepr(mpz_class value, unsigned bytes);
+	void convertSimpleKey(const IR::Expression* keySet,
+						mpz_class& value, mpz_class& mask);
+	unsigned combine(const IR::Expression* keySet,
+					const IR::ListExpression* select,
+					mpz_class& value, mpz_class& mask);
+
+ private:
+    P4::ReferenceMap *refMap; P4::TypeMap *typeMap;
+    const cstring graphsDir;
+    Graph *g{nullptr};
+    vertex_t begin_v{};
+    vertex_t end_v{};
+    vertex_t accept_v{};
+    Parents parents{};
+    Parents defParents{};
+    boost::optional<cstring> instanceName{};
+};
+
 }  // namespace graphs
 
 #endif  // _BACKENDS_GRAPHS_CONTROLS_H_