[𝘀𝗽𝗿] initial version

Created using spr 1.3.7

src/trace_processor/plugins/dominator_tree/dominator_tree.cc

diff --git a/src/trace_processor/plugins/dominator_tree/dominator_tree.cc b/src/trace_processor/plugins/dominator_tree/dominator_tree.cc
index 674346c..fd15ef5 100644
--- a/src/trace_processor/plugins/dominator_tree/dominator_tree.cc
+++ b/src/trace_processor/plugins/dominator_tree/dominator_tree.cc
@@ -89,13 +89,18 @@
     }
   }
 
-  // Returns the TreeNumber for a given Node.
+  // Returns the semi-dominator TreeNumber for a given Node. v must satisfy
+  // IsInTree(v).
   TreeNumber GetSemiDominator(Node v) const {
-    // Note: if you happen to see this check failing, it's likely a problem that
-    // the graph has nodes which are not reachable from the root node.
     return *GetStateForNode(v).semi_dominator;
   }
 
+  // Returns whether the given node was visited by RunDfs and is therefore
+  // part of the DFS spanning tree.
+  bool IsInTree(Node v) const {
+    return GetStateForNode(v).semi_dominator.has_value();
+  }
+
   // Returns the number of nodes in the tree (== the number of nodes in
   // the graph.)
   uint32_t node_count_in_tree() const {
@@ -149,8 +154,14 @@
     a = ancestor;
   }
 
-  // Corresponds to the "Eval" function in the paper.
-  Node GetMinSemiDominatorToAncestor(Node vertex, const Graph& graph) {
+  // Corresponds to the "Eval" function in the paper. Returns nullopt if
+  // `vertex` was not visited by the graph's DFS; such a node has no
+  // meaningful semi-dominator to report.
+  std::optional<Node> GetMinSemiDominatorToAncestor(Node vertex,
+                                                    const Graph& graph) {
+    if (!graph.IsInTree(vertex)) {
+      return std::nullopt;
+    }
     NodeState& state = GetStateForNode(vertex);
     if (!state.ancestor) {
       return vertex;
@@ -239,9 +250,12 @@
     Node w = GetNodeForTreeNumber(TreeNumber{i});
     NodeState& w_state = GetStateForNode(w);
     for (Node v : w_state.predecessors) {
-      Node u = forest.GetMinSemiDominatorToAncestor(v, *this);
+      auto u = forest.GetMinSemiDominatorToAncestor(v, *this);
+      if (!u) {
+        continue;
+      }
       w_state.semi_dominator =
-          std::min(*w_state.semi_dominator, GetSemiDominator(u));
+          std::min(*w_state.semi_dominator, GetSemiDominator(*u));
     }
     NodeState& semi_dominator_state =
         GetStateForNode(GetNodeForTreeNumber(*w_state.semi_dominator));
@@ -253,7 +267,10 @@
 
     NodeState& w_parent_state = GetStateForNode(w_parent);
     for (Node v : w_parent_state.self_as_semi_dominator) {
-      Node u = forest.GetMinSemiDominatorToAncestor(v, *this);
+      // v is always in-tree: it was pushed onto some node's
+      // self_as_semi_dominator list in an earlier iteration of this loop,
+      // which only runs over tree nodes.
+      Node u = *forest.GetMinSemiDominatorToAncestor(v, *this);
       NodeState& v_state = GetStateForNode(v);
       v_state.dominator =
           GetSemiDominator(u) < v_state.semi_dominator ? u : w_parent;

test/trace_processor/diff_tests/stdlib/graphs/dominator_tree_tests.py

diff --git a/test/trace_processor/diff_tests/stdlib/graphs/dominator_tree_tests.py b/test/trace_processor/diff_tests/stdlib/graphs/dominator_tree_tests.py
index 1287b7c..e664349 100644
--- a/test/trace_processor/diff_tests/stdlib/graphs/dominator_tree_tests.py
+++ b/test/trace_processor/diff_tests/stdlib/graphs/dominator_tree_tests.py
@@ -159,6 +159,31 @@
         12,10
         """))
 
+  def test_unreachable_predecessor(self):
+    return DiffTestBlueprint(
+        trace=DataPath('counters.json'),
+        query="""
+          INCLUDE PERFETTO MODULE graphs.dominator_tree;
+
+          CREATE PERFETTO TABLE foo AS
+          SELECT NULL AS source_node_id, NULL AS dest_node_id WHERE FALSE
+          UNION ALL
+          VALUES (0, 1), (1, 2), (2, 3)
+          UNION ALL
+          VALUES (99, 2), (98, 99);
+
+          SELECT *
+          FROM graph_dominator_tree!(foo, 0)
+          ORDER BY node_id;
+        """,
+        out=Csv("""
+        "node_id","dominator_node_id"
+        0,"[NULL]"
+        1,0
+        2,1
+        3,2
+        """))
+
   def test_forest(self):
     return DiffTestBlueprint(
         trace=DataPath('counters.json'),