tp: implement dominator tree intrinsic and corresponding macro
This CL adds the implementation of a "dominator tree" macro to the
standard library, backed by a new table function intrinsic in C++
implementing the Lengauer-Tarjan algorithm to compute the dominator tree
from a directed flow-graph.
This CL also brings a new approach to how we can make use of table
function infrastructure to operate on full tables by making use of the
`RepeatedField` function. This can potentially be even further improved
in the future but for now, this makes the user-facing API very nice.
This approach should be used on upcoming work like interval_intersect/
interval_set_difference etc.
Change-Id: Iecdc6a4b7eccc76ff46e0681bda9d16b745d2614
diff --git a/BUILD b/BUILD
index 98e75c6..e38a6df 100644
--- a/BUILD
+++ b/BUILD
@@ -2187,6 +2187,8 @@
"src/trace_processor/perfetto_sql/intrinsics/table_functions/connected_flow.h",
"src/trace_processor/perfetto_sql/intrinsics/table_functions/descendant.cc",
"src/trace_processor/perfetto_sql/intrinsics/table_functions/descendant.h",
+ "src/trace_processor/perfetto_sql/intrinsics/table_functions/dominator_tree.cc",
+ "src/trace_processor/perfetto_sql/intrinsics/table_functions/dominator_tree.h",
"src/trace_processor/perfetto_sql/intrinsics/table_functions/experimental_annotated_stack.cc",
"src/trace_processor/perfetto_sql/intrinsics/table_functions/experimental_annotated_stack.h",
"src/trace_processor/perfetto_sql/intrinsics/table_functions/experimental_counter_dur.cc",
@@ -2307,6 +2309,14 @@
],
)
+# GN target: //src/trace_processor/perfetto_sql/stdlib/graphs:graphs
+perfetto_filegroup(
+ name = "src_trace_processor_perfetto_sql_stdlib_graphs_graphs",
+ srcs = [
+ "src/trace_processor/perfetto_sql/stdlib/graphs/dominator_tree.sql",
+ ],
+)
+
# GN target: //src/trace_processor/perfetto_sql/stdlib/intervals:intervals
perfetto_filegroup(
name = "src_trace_processor_perfetto_sql_stdlib_intervals_intervals",
@@ -2356,6 +2366,7 @@
":src_trace_processor_perfetto_sql_stdlib_chrome_chrome_sql",
":src_trace_processor_perfetto_sql_stdlib_common_common",
":src_trace_processor_perfetto_sql_stdlib_experimental_experimental",
+ ":src_trace_processor_perfetto_sql_stdlib_graphs_graphs",
":src_trace_processor_perfetto_sql_stdlib_intervals_intervals",
":src_trace_processor_perfetto_sql_stdlib_linux_linux",
":src_trace_processor_perfetto_sql_stdlib_pkvm_pkvm",