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/Android.bp b/Android.bp
index 084cb61..2f1dc27 100644
--- a/Android.bp
+++ b/Android.bp
@@ -11649,6 +11649,7 @@
"src/trace_processor/perfetto_sql/intrinsics/table_functions/ancestor.cc",
"src/trace_processor/perfetto_sql/intrinsics/table_functions/connected_flow.cc",
"src/trace_processor/perfetto_sql/intrinsics/table_functions/descendant.cc",
+ "src/trace_processor/perfetto_sql/intrinsics/table_functions/dominator_tree.cc",
"src/trace_processor/perfetto_sql/intrinsics/table_functions/experimental_annotated_stack.cc",
"src/trace_processor/perfetto_sql/intrinsics/table_functions/experimental_counter_dur.cc",
"src/trace_processor/perfetto_sql/intrinsics/table_functions/experimental_flamegraph.cc",
@@ -11766,6 +11767,7 @@
"src/trace_processor/perfetto_sql/stdlib/experimental/slices.sql",
"src/trace_processor/perfetto_sql/stdlib/experimental/thread_executing_span.sql",
"src/trace_processor/perfetto_sql/stdlib/experimental/thread_state_flattened.sql",
+ "src/trace_processor/perfetto_sql/stdlib/graphs/dominator_tree.sql",
"src/trace_processor/perfetto_sql/stdlib/intervals/overlap.sql",
"src/trace_processor/perfetto_sql/stdlib/linux/cpu_idle.sql",
"src/trace_processor/perfetto_sql/stdlib/pkvm/hypervisor.sql",
