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 class CallGraph { 28 public: 29 // Creates a call graph corresponding to the given SPIR-V module. 30 explicit CallGraph(opt::IRContext* context); 31 32 // Returns a mapping from each function to its number of distinct callers. GetFunctionInDegree()33 const std::map<uint32_t, uint32_t>& GetFunctionInDegree() const { 34 return function_in_degree_; 35 } 36 37 // Returns the ids of the functions that |function_id| directly invokes. GetDirectCallees(uint32_t function_id)38 const std::set<uint32_t>& GetDirectCallees(uint32_t function_id) const { 39 return call_graph_edges_.at(function_id); 40 } 41 42 // Returns the ids of the functions that |function_id| directly or indirectly 43 // invokes. 44 std::set<uint32_t> GetIndirectCallees(uint32_t function_id) const; 45 46 private: 47 // Pushes the direct callees of |function_id| on to |queue|. 48 void PushDirectCallees(uint32_t function_id, 49 std::queue<uint32_t>* queue) const; 50 51 // Maps each function id to the ids of its immediate callees. 52 std::map<uint32_t, std::set<uint32_t>> call_graph_edges_; 53 54 // For each function id, stores the number of distinct functions that call 55 // the function. 56 std::map<uint32_t, uint32_t> function_in_degree_; 57 }; 58 59 } // namespace fuzz 60 } // namespace spvtools 61 62 #endif // SOURCE_FUZZ_CALL_GRAPH_H_ 63