1 // Copyright (c) 2020 Google LLC 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef SOURCE_FUZZ_CALL_GRAPH_H_ 16 #define SOURCE_FUZZ_CALL_GRAPH_H_ 17 18 #include <map> 19 #include <set> 20 21 #include "source/opt/ir_context.h" 22 23 namespace spvtools { 24 namespace fuzz { 25 26 // Represents the acyclic call graph of a SPIR-V module. 27 // The module is assumed to be recursion-free, so there are no cycles in the 28 // graph. This class is immutable, so it will need to be recomputed if the 29 // module changes. 30 class CallGraph { 31 public: 32 // Creates a call graph corresponding to the given SPIR-V module. 33 explicit CallGraph(opt::IRContext* context); 34 35 // Returns a mapping from each function to its number of distinct callers. GetFunctionInDegree()36 const std::map<uint32_t, uint32_t>& GetFunctionInDegree() const { 37 return function_in_degree_; 38 } 39 40 // Returns the ids of the functions that |function_id| directly invokes. GetDirectCallees(uint32_t function_id)41 const std::set<uint32_t>& GetDirectCallees(uint32_t function_id) const { 42 return call_graph_edges_.at(function_id); 43 } 44 45 // Returns the ids of the functions that |function_id| directly or indirectly 46 // invokes. 47 std::set<uint32_t> GetIndirectCallees(uint32_t function_id) const; 48 49 // Returns the ids of all the functions in the graph in a topological order, 50 // in relation to the function calls, which are assumed to be recursion-free. GetFunctionsInTopologicalOrder()51 const std::vector<uint32_t>& GetFunctionsInTopologicalOrder() const { 52 return functions_in_topological_order_; 53 } 54 55 // Returns the maximum loop nesting depth from which |function_id| can be 56 // called. This is computed inter-procedurally (i.e. if main calls A from 57 // depth 2 and A calls B from depth 1, the result will be 3 for A). 58 // This is a static analysis, so it's not necessarily true that the depth 59 // returned can actually be reached at runtime. GetMaxCallNestingDepth(uint32_t function_id)60 uint32_t GetMaxCallNestingDepth(uint32_t function_id) const { 61 return function_max_loop_nesting_depth_.at(function_id); 62 } 63 64 private: 65 // Computes |call_graph_edges_| and |function_in_degree_|. For each pair (A, 66 // B) of functions such that there is at least a function call from A to B, 67 // adds, to |call_to_max_depth|, a mapping from (A, B) to the maximum loop 68 // nesting depth (within A) of any such function call. 69 void BuildGraphAndGetDepthOfFunctionCalls( 70 opt::IRContext* context, 71 std::map<std::pair<uint32_t, uint32_t>, uint32_t>* call_to_max_depth); 72 73 // Computes a topological order of the functions in the graph, writing the 74 // result to |functions_in_topological_order_|. Assumes that the function 75 // calls are recursion-free and that |function_in_degree_| has been computed. 76 void ComputeTopologicalOrderOfFunctions(); 77 78 // Computes |function_max_loop_nesting_depth_| so that each function is mapped 79 // to the maximum loop nesting depth from which it can be called, as described 80 // by the comment to GetMaxCallNestingDepth. Assumes that |call_graph_edges_| 81 // and |functions_in_topological_order_| have been computed, and that 82 // |call_to_max_depth| contains a mapping for each edge in the graph. 83 void ComputeInterproceduralFunctionCallDepths( 84 const std::map<std::pair<uint32_t, uint32_t>, uint32_t>& 85 call_to_max_depth); 86 87 // Pushes the direct callees of |function_id| on to |queue|. 88 void PushDirectCallees(uint32_t function_id, 89 std::queue<uint32_t>* queue) const; 90 91 // Maps each function id to the ids of its immediate callees. 92 std::map<uint32_t, std::set<uint32_t>> call_graph_edges_; 93 94 // For each function id, stores the number of distinct functions that call 95 // the function. 96 std::map<uint32_t, uint32_t> function_in_degree_; 97 98 // Stores the ids of the functions in a topological order, 99 // in relation to the function calls, which are assumed to be recursion-free. 100 std::vector<uint32_t> functions_in_topological_order_; 101 102 // For each function id, stores the maximum loop nesting depth that the 103 // function can be called from. 104 std::map<uint32_t, uint32_t> function_max_loop_nesting_depth_; 105 }; 106 107 } // namespace fuzz 108 } // namespace spvtools 109 110 #endif // SOURCE_FUZZ_CALL_GRAPH_H_ 111