| 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. |
| 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. |
| 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. |
| 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. |
| 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_ |