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 #include "source/fuzz/call_graph.h" 16 17 #include <queue> 18 19 namespace spvtools { 20 namespace fuzz { 21 CallGraph(opt::IRContext * context)22CallGraph::CallGraph(opt::IRContext* context) { 23 // Initialize function in-degree and call graph edges to 0 and empty. 24 for (auto& function : *context->module()) { 25 function_in_degree_[function.result_id()] = 0; 26 call_graph_edges_[function.result_id()] = std::set<uint32_t>(); 27 } 28 29 // Consider every function. 30 for (auto& function : *context->module()) { 31 // Avoid considering the same callee of this function multiple times by 32 // recording known callees. 33 std::set<uint32_t> known_callees; 34 // Consider every function call instruction in every block. 35 for (auto& block : function) { 36 for (auto& instruction : block) { 37 if (instruction.opcode() != SpvOpFunctionCall) { 38 continue; 39 } 40 // Get the id of the function being called. 41 uint32_t callee = instruction.GetSingleWordInOperand(0); 42 if (known_callees.count(callee)) { 43 // We have already considered a call to this function - ignore it. 44 continue; 45 } 46 // Increase the callee's in-degree and add an edge to the call graph. 47 function_in_degree_[callee]++; 48 call_graph_edges_[function.result_id()].insert(callee); 49 // Mark the callee as 'known'. 50 known_callees.insert(callee); 51 } 52 } 53 } 54 } 55 PushDirectCallees(uint32_t function_id,std::queue<uint32_t> * queue) const56void CallGraph::PushDirectCallees(uint32_t function_id, 57 std::queue<uint32_t>* queue) const { 58 for (auto callee : GetDirectCallees(function_id)) { 59 queue->push(callee); 60 } 61 } 62 GetIndirectCallees(uint32_t function_id) const63std::set<uint32_t> CallGraph::GetIndirectCallees(uint32_t function_id) const { 64 std::set<uint32_t> result; 65 std::queue<uint32_t> queue; 66 PushDirectCallees(function_id, &queue); 67 68 while (!queue.empty()) { 69 auto next = queue.front(); 70 queue.pop(); 71 if (result.count(next)) { 72 continue; 73 } 74 result.insert(next); 75 PushDirectCallees(next, &queue); 76 } 77 return result; 78 } 79 80 } // namespace fuzz 81 } // namespace spvtools 82