1-- 2-- Copyright 2024 The Android Open Source Project 3-- 4-- Licensed under the Apache License, Version 2.0 (the "License"); 5-- you may not use this file except in compliance with the License. 6-- You may obtain a copy of the License at 7-- 8-- https://www.apache.org/licenses/LICENSE-2.0 9-- 10-- Unless required by applicable law or agreed to in writing, software 11-- distributed under the License is distributed on an "AS IS" BASIS, 12-- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13-- See the License for the specific language governing permissions and 14-- limitations under the License. 15 16-- Given a table containing a directed flow-graph and an entry node, computes 17-- the "dominator tree" for the graph. See [1] for an explanation of what a 18-- dominator tree is. 19-- 20-- [1] https://en.wikipedia.org/wiki/Dominator_(graph_theory) 21-- 22-- Example usage on traces containing heap graphs: 23-- ``` 24-- CREATE PERFETTO VIEW dominator_compatible_heap_graph AS 25-- -- Extract the edges from the heap graph which correspond to references 26-- -- between objects. 27-- SELECT 28-- owner_id AS source_node_id, 29-- owned_id as dest_node_id 30-- FROM heap_graph_reference 31-- JOIN heap_graph_object owner on heap_graph_reference.owner_id = owner.id 32-- WHERE owned_id IS NOT NULL AND owner.reachable 33-- UNION ALL 34-- -- Since a Java heap graph is a "forest" structure, we need to add a dummy 35-- -- "root" node which connects all the roots of the forest into a single 36-- -- connected component. 37-- SELECT 38-- (SELECT max(id) + 1 FROM heap_graph_object) as source_node_id, 39-- id 40-- FROM heap_graph_object 41-- WHERE root_type IS NOT NULL; 42-- 43-- SELECT * 44-- FROM graph_dominator_tree!( 45-- dominator_compatible_heap_graph, 46-- (SELECT max(id) + 1 FROM heap_graph_object) 47-- ); 48-- ``` 49CREATE PERFETTO MACRO graph_dominator_tree( 50 -- A table/view/subquery corresponding to a directed flow-graph on which the 51 -- dominator tree should be computed. This table must have the columns 52 -- "source_node_id" and "dest_node_id" corresponding to the two nodes on 53 -- either end of the edges in the graph. 54 -- 55 -- Note: the columns must contain uint32 similar to ids in trace processor 56 -- tables (i.e. the values should be relatively dense and close to zero). The 57 -- implementation makes assumptions on this for performance reasons and, if 58 -- this criteria is not, can lead to enormous amounts of memory being 59 -- allocated. 60 -- 61 -- Note: this means that the graph *must* be a single fully connected 62 -- component with |root_node_id| (see below) being the "entry node" for this 63 -- component. Specifically, all nodes *must* be reachable by following paths 64 -- from the root node. Failing to adhere to this property will result in 65 -- undefined behaviour. 66 -- 67 -- If working with a "forest"-like structure, a dummy node should be added which 68 -- links all the roots of the forest together into a single component; an example 69 -- of this can be found in the heap graph example query above. 70 graph_table TableOrSubquery, 71 -- The entry node to |graph_table| which will be the root of the dominator 72 -- tree. 73 root_node_id Expr 74) 75-- The returned table has the schema (node_id UINT32, dominator_node_id UINT32). 76-- |node_id| is the id of the node from the input graph and |dominator_node_id| 77-- is the id of the node in the input flow-graph which is the "dominator" of 78-- |node_id|. 79RETURNS TableOrSubquery AS 80( 81 -- Rename the generic columns of __intrinsic_table_ptr to the actual columns. 82 SELECT c0 AS node_id, c1 AS dominator_node_id 83 FROM __intrinsic_table_ptr(( 84 -- Aggregate function to perform a DFS on the nodes on the input graph. 85 SELECT __intrinsic_dominator_tree(g.source_node_id, g.dest_node_id, $root_node_id) 86 FROM $graph_table g 87 )) 88 -- Bind the dynamic columns in the |__intrinsic_table_ptr| to the columns of 89 -- the dominator tree table. 90 WHERE __intrinsic_table_ptr_bind(c0, 'node_id') 91 AND __intrinsic_table_ptr_bind(c1, 'dominator_node_id') 92); 93