Fix problems with the reachability pass.

Signed-off-by: fruffy <fruffy@nyu.edu>
p4lang · Jul 9, 2024 · 2c33e75 · 2c33e75
1 parent 5be356c
commit 2c33e75
Show file tree

Hide file tree

Showing 5 changed files with 145 additions and 85 deletions.
diff --git a/backends/p4tools/common/compiler/reachability.cpp b/backends/p4tools/common/compiler/reachability.cpp
@@ -1,13 +1,14 @@
 #include "backends/p4tools/common/compiler/reachability.h"
 
 #include <cstddef>
-#include <functional>
 #include <iostream>
 #include <list>
 #include <string>
 #include <utility>
 #include <vector>
 
+#include "backends/p4tools/common/lib/table_utils.h"
+#include "frontends/common/resolveReferences/resolveReferences.h"
 #include "ir/declaration.h"
 #include "ir/indexed_vector.h"
 #include "ir/vector.h"
@@ -54,57 +55,78 @@ bool P4ProgramDCGCreator::preorder(const IR::ConstructorCallExpression *callExpr
     return true;
 }
 
-bool P4ProgramDCGCreator::preorder(const IR::MethodCallExpression *method) {
-    // Check for application of a table.
-    CHECK_NULL(method->method);
-    if (const auto *path = method->method->to<IR::PathExpression>()) {
-        const auto *currentControl = findOrigCtxt<IR::P4Control>();
-        if (currentControl != nullptr) {
-            const auto *decl = currentControl->getDeclByName(path->path->name.name);
-            if (decl != nullptr) {
-                if (const auto *action = decl->to<IR::P4Action>()) {
-                    for (const auto *arg : *method->arguments) {
-                        visit(arg);
-                    }
-                    addEdge(method);
-                    visit(action);
-                    return false;
-                }
-            }
-        }
-    }
-    if (!method->method->is<IR::Member>()) {
-        return true;
-    }
-    const auto *member = method->method->to<IR::Member>();
-    for (const auto *arg : *method->arguments) {
+bool P4ProgramDCGCreator::preorder(const IR::MethodCallExpression *call) {
+    CHECK_NULL(call->method);
+    for (const auto *arg : *call->arguments) {
         visit(arg);
     }
-    // Do not anylyse tables apply and value set index methods.
-    if (member->member != IR::IApply::applyMethodName && member->member.originalName != "index") {
-        return true;
+    if (call->method->type->is<IR::Type_Action>()) {
+        const auto *path = call->method->checkedTo<IR::PathExpression>();
+        const auto *action = getDeclaration(path->path, true)->checkedTo<IR::P4Action>();
+        addEdge(call);
+        visit(action);
+        return false;
     }
-    if (const auto *pathExpr = member->expr->to<IR::PathExpression>()) {
-        const auto *currentControl = findOrigCtxt<IR::P4Control>();
-        if (currentControl != nullptr) {
-            const auto *decl = currentControl->getDeclByName(pathExpr->path->name.name);
-            visit(decl->checkedTo<IR::P4Table>());
+    if (call->method->type->is<IR::Type_Method>()) {
+        if (const auto *path = call->method->to<IR::PathExpression>()) {
+            const auto *method = getDeclaration(path->path, true)->checkedTo<IR::Method>();
+            visit(method);
             return false;
         }
-        const auto *parser = findOrigCtxt<IR::P4Parser>();
-        if (parser != nullptr) {
-            const auto *decl = parser->getDeclByName(pathExpr->path->name.name);
-            visit(decl->checkedTo<IR::Declaration_Instance>());
-            return true;
+        if (const auto *method = call->method->to<IR::Member>()) {
+            // Case where call->method is a Member expression. For table invocations, the
+            // qualifier of the member determines the table being invoked. For extern calls,
+            // the qualifier determines the extern object containing the method being invoked.
+            BUG_CHECK(method->expr, "Method call has unexpected format: %1%", call);
+
+            // Handle table calls.
+            if (method->expr->type->is<IR::Type_Table>()) {
+                const auto *tableDecl =
+                    getDeclaration(method->expr->checkedTo<IR::PathExpression>()->path, true)
+                        ->checkedTo<IR::P4Table>();
+                visit(tableDecl);
+                return false;
+            }
+
+            // Handle extern calls. They may also be of Type_SpecializedCanonical.
+            if (method->expr->type->is<IR::Type_Extern>() ||
+                method->expr->type->is<IR::Type_SpecializedCanonical>()) {
+                // TODO: This is the wrong place to analyze parser value sets.
+                // They should be handled in the select expression.
+                if (method->member.originalName == "index") {
+                    const auto *decl =
+                        getDeclaration(method->expr->checkedTo<IR::PathExpression>()->path, true)
+                            ->checkedTo<IR::Declaration_Instance>();
+                    visit(decl);
+                }
+                return false;
+            }
+
+            // Handle calls to header methods.
+            if (method->expr->type->is<IR::Type_Header>() ||
+                method->expr->type->is<IR::Type_HeaderUnion>()) {
+                if (method->member == "isValid" || method->member == "setInvalid" ||
+                    method->member == "setValid") {
+                    return false;
+                }
+                BUG("Unknown method call on header instance: %1%", call);
+            }
+
+            if (method->expr->type->is<IR::Type_Stack>()) {
+                if (method->member == "push_front" || method->member == "pop_front") {
+                    return false;
+                }
+                BUG("Unknown method call on stack instance: %1%", call);
+            }
+
+            BUG("Unknown method member expression: %1% of type %2%", method->expr,
+                method->expr->type);
         }
-        return true;
-    }
-    const auto *type = member->expr->type;
-    if (const auto *tableType = type->to<IR::Type_Table>()) {
-        visit(tableType->table);
-        return false;
+
+        BUG("Unknown method call: %1% of type %2%", call->method, call->method->node_type_name());
     }
-    return true;
+
+    BUG("Unsupported method call type for %1%: %2%", call, call->method->type);
 }
 
 bool P4ProgramDCGCreator::preorder(const IR::MethodCallStatement *method) {
@@ -133,7 +155,6 @@ bool P4ProgramDCGCreator::preorder(const IR::P4Parser *parser) {
 
 bool P4ProgramDCGCreator::preorder(const IR::P4Table *table) {
     addEdge(table, table->name);
-    DCGVertexTypeSet prevSet;
     if (table->annotations != nullptr) {
         for (const auto *annotation : table->annotations->annotations) {
             visit(annotation);
@@ -148,20 +169,35 @@ bool P4ProgramDCGCreator::preorder(const IR::P4Table *table) {
             }
         }
     }
+    TableUtils::TableProperties properties;
+
+    TableUtils::checkTableImmutability(*table, properties);
+
     auto storedSet = prev;
-    const auto *entryList = table->getEntries();
-    if (entryList != nullptr) {
-        for (const auto *entry : entryList->entries) {
-            prev = storedSet;
-            visit(entry);
+    DCGVertexTypeSet prevSet;
+    if (properties.tableIsImmutable && properties.defaultIsImmutable) {
+        const auto *entryList = table->getEntries();
+        if (entryList != nullptr) {
+            for (const auto *entry : entryList->entries) {
+                prev = storedSet;
+                visit(entry);
+                prevSet.insert(prev.begin(), prev.end());
+            }
+        } else if (wasImplementations) {
             prevSet.insert(prev.begin(), prev.end());
         }
-    } else if (wasImplementations) {
+        prev = storedSet;
+        visit(table->getDefaultAction());
         prevSet.insert(prev.begin(), prev.end());
+        prev = prevSet;
+        return false;
     }
-    prev = storedSet;
-    visit(table->getDefaultAction());
-    prevSet.insert(prev.begin(), prev.end());
+    for (const auto *action : table->getActionList()->actionList) {
+        prev = storedSet;
+        visit(action);
+        prevSet.insert(prev.begin(), prev.end());
+    }
+
     prev = prevSet;
     return false;
 }
@@ -179,16 +215,18 @@ bool P4ProgramDCGCreator::preorder(const IR::ParserState *parserState) {
     }
     if (parserState->selectExpression != nullptr) {
         if (const auto *pathExpr = parserState->selectExpression->to<IR::PathExpression>()) {
-            if (pathExpr->path->name.name == IR::ParserState::accept ||
-                pathExpr->path->name.name == IR::ParserState::reject) {
-                addEdge(parserState->selectExpression);
-                return true;
+            const auto *declaration = getDeclaration(pathExpr->path)->checkedTo<IR::ParserState>();
+
+            BUG_CHECK(declaration != nullptr, "Parser state not found: %1%",
+                      pathExpr->path->name.name);
+            if (visited.count(declaration) != 0U) {
+                addEdge(declaration, declaration->name);
+                return false;
             }
+            visit(declaration);
+        } else {
+            visit(parserState->selectExpression);
         }
-        if (visited.count(parserState->selectExpression) != 0U) {
-            return false;
-        }
-        visit(parserState->selectExpression);
     }
     return false;
 }
@@ -220,8 +258,9 @@ bool P4ProgramDCGCreator::preorder(const IR::P4Program *program) {
             // declaration instance.
             auto filter = [pathExpr](const IR::IDeclaration *d) {
                 CHECK_NULL(d);
-                if (const auto *decl = d->to<IR::Declaration_Instance>())
+                if (const auto *decl = d->to<IR::Declaration_Instance>()) {
                     return pathExpr->path->name == decl->name;
+                }
                 return false;
             };
             // Convert the declaration instance into a constructor-call expression.
@@ -234,7 +273,7 @@ bool P4ProgramDCGCreator::preorder(const IR::P4Program *program) {
     }
     this->prev = {program};
     for (const auto *arg : v) {
-        // Apply to the arguments.,
+        // Visit the blocks in order of the constructor arguments.
         visit(arg);
     }
     return false;
@@ -248,7 +287,7 @@ bool P4ProgramDCGCreator::preorder(const IR::P4ValueSet *valueSet) {
 bool P4ProgramDCGCreator::preorder(const IR::SelectExpression *selectExpression) {
     visit(selectExpression->select);
     DCGVertexTypeSet prevSet;
-    const auto *currentParser = findOrigCtxt<IR::P4Parser>();
+    const auto *currentParser = findContext<IR::P4Parser>();
     BUG_CHECK(currentParser != nullptr, "Null parser pointer");
     auto storedSet = prev;
     for (const auto *selectCase : selectExpression->selectCases) {
@@ -278,6 +317,8 @@ bool P4ProgramDCGCreator::preorder(const IR::IfStatement *ifStatement) {
         prev = storedSet;
         visit(ifStatement->ifFalse);
         next.insert(prev.begin(), prev.end());
+    } else {
+        next.insert(storedSet.begin(), storedSet.end());
     }
     prev = next;
     return false;
@@ -317,7 +358,7 @@ bool P4ProgramDCGCreator::preorder(const IR::StatOrDecl *statOrDecl) {
     return true;
 }
 
-void P4ProgramDCGCreator::addEdge(const DCGVertexType *vertex, IR::ID vertexName) {
+void P4ProgramDCGCreator::addEdge(const DCGVertexType *vertex, const IR::ID &vertexName) {
     LOG1("Add edge : " << prev.size() << "(" << *prev.begin() << ") : " << vertex);
     for (const auto *p : prev) {
         dcg->calls(p, vertex);

diff --git a/backends/p4tools/common/compiler/reachability.h b/backends/p4tools/common/compiler/reachability.h
@@ -7,8 +7,8 @@
 #include <unordered_map>
 #include <unordered_set>
 #include <utility>
-#include <vector>
 
+#include "frontends/common/resolveReferences/resolveReferences.h"
 #include "frontends/p4/callGraph.h"
 #include "ir/id.h"
 #include "ir/ir.h"
@@ -34,7 +34,7 @@ class ExtendedCallGraph : public P4::CallGraph<T> {
     /// Function adds current vertex to a hash which allows to get access
     /// for vertexes from string in DCG.
     /// If name is empty then it doesn't hash it.
-    void addToHash(T vertex, IR::ID name) {
+    void addToHash(T vertex, const IR::ID &name) {
         if (name.name.size() == 0) {
             return;
         }
@@ -51,7 +51,7 @@ class ExtendedCallGraph : public P4::CallGraph<T> {
             cstring newName = name.name.before(prev);
             i = hash.find(newName);
             if (i == hash.end()) {
-                addToHash(vertex, (newName.size() ? IR::ID(newName) : IR::ID()));
+                addToHash(vertex, ((newName.size() != 0U) ? IR::ID(newName) : IR::ID()));
             }
         }
     }
@@ -87,7 +87,7 @@ class ExtendedCallGraph : public P4::CallGraph<T> {
 using NodesCallGraph = ExtendedCallGraph<DCGVertexType *>;
 
 /// The main class for building control flow DCG.
-class P4ProgramDCGCreator : public Inspector {
+class P4ProgramDCGCreator : public Inspector, private P4::ResolutionContext {
     NodesCallGraph *dcg;
     DCGVertexTypeSet prev;
     std::unordered_set<const DCGVertexType *> visited;
@@ -98,7 +98,7 @@ class P4ProgramDCGCreator : public Inspector {
 
     bool preorder(const IR::Annotation *annotation) override;
     bool preorder(const IR::ConstructorCallExpression *callExpr) override;
-    bool preorder(const IR::MethodCallExpression *method) override;
+    bool preorder(const IR::MethodCallExpression *call) override;
     bool preorder(const IR::MethodCallStatement *method) override;
     bool preorder(const IR::P4Action *action) override;
     bool preorder(const IR::P4Parser *parser) override;
@@ -115,7 +115,7 @@ class P4ProgramDCGCreator : public Inspector {
  protected:
     /// Function add edge to current @vertex in DCG.
     /// The edge is a pair (@prev, @vertex).
-    void addEdge(const DCGVertexType *vertex, IR::ID vertexName = IR::ID());
+    void addEdge(const DCGVertexType *vertex, const IR::ID &vertexName = IR::ID());
 };
 
 /// The main data for reachability engine.

diff --git a/backends/p4tools/modules/smith/common/statements.cpp b/backends/p4tools/modules/smith/common/statements.cpp
@@ -14,7 +14,6 @@
 #include "backends/p4tools/modules/smith/core/target.h"
 #include "backends/p4tools/modules/smith/util/util.h"
 #include "ir/indexed_vector.h"
-#include "ir/ir-generated.h"
 #include "ir/irutils.h"
 #include "ir/vector.h"
 #include "lib/cstring.h"

diff --git a/backends/p4tools/modules/testgen/targets/bmv2/test/small-step/reachability.cpp b/backends/p4tools/modules/testgen/targets/bmv2/test/small-step/reachability.cpp
@@ -5,14 +5,15 @@
 #include <cstdlib>
 #include <filesystem>
 #include <fstream>
-#include <functional>
 
 #include "backends/p4tools/common/compiler/midend.h"
 #include "frontends/common/options.h"
 #include "frontends/common/parseInput.h"
 #include "frontends/common/parser_options.h"
 #include "frontends/common/resolveReferences/referenceMap.h"
 #include "frontends/p4/frontend.h"
+#include "frontends/p4/toP4/toP4.h"
+#include "frontends/p4/typeChecking/typeChecker.h"
 #include "frontends/p4/typeMap.h"
 #include "ir/declaration.h"
 #include "ir/ir.h"
@@ -69,6 +70,8 @@ ReturnedInfo loadExampleForReachability(const char *curFile) {
     P4::TypeMap typeMap;
     P4Tools::MidEnd midEnd(options);
     program = program->apply(midEnd);
+    // Need a last round of type checking.
+    program = program->apply(P4::TypeChecking(&refMap, &typeMap, true));
     auto *currentDCG = new P4Tools::NodesCallGraph("NodesCallGraph");
     P4Tools::P4ProgramDCGCreator dcgCreator(currentDCG);
     program->apply(dcgCreator);
@@ -384,12 +387,14 @@ void callTestgen(const char *inputFile, const char *behavior, const char *path,
     }
 }
 
-bool checkResultingSTF(std::list<std::list<std::string>> identifiersList, std::string path) {
-    std::ostringstream resDir;
-    resDir << buildPath << path;
-    for (const auto &f : std::filesystem::directory_iterator(resDir.str())) {
-        std::string fpath = f.path().c_str();
-        if (fpath.rfind(".stf") == std::string::npos) {
+bool checkResultingSTF(const std::list<std::list<std::string>> &identifiersList,
+                       const std::filesystem::path &path) {
+    std::filesystem::path resDir = std::filesystem::path(buildPath) / path;
+    if (!std::filesystem::exists(resDir)) {
+        return false;
+    }
+    for (const auto &f : std::filesystem::directory_iterator(resDir)) {
+        if (f.path().extension() != ".stf") {
             // Not a STF file.
             continue;
         }