/src/php-src/Zend/Optimizer/zend_call_graph.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | +----------------------------------------------------------------------+ |
3 | | | Zend Engine, Call Graph | |
4 | | +----------------------------------------------------------------------+ |
5 | | | Copyright (c) The PHP Group | |
6 | | +----------------------------------------------------------------------+ |
7 | | | This source file is subject to version 3.01 of the PHP license, | |
8 | | | that is bundled with this package in the file LICENSE, and is | |
9 | | | available through the world-wide-web at the following url: | |
10 | | | https://www.php.net/license/3_01.txt | |
11 | | | If you did not receive a copy of the PHP license and are unable to | |
12 | | | obtain it through the world-wide-web, please send a note to | |
13 | | | license@php.net so we can mail you a copy immediately. | |
14 | | +----------------------------------------------------------------------+ |
15 | | | Authors: Dmitry Stogov <dmitry@php.net> | |
16 | | +----------------------------------------------------------------------+ |
17 | | */ |
18 | | |
19 | | #include "zend_compile.h" |
20 | | #include "zend_extensions.h" |
21 | | #include "Optimizer/zend_optimizer.h" |
22 | | #include "zend_optimizer_internal.h" |
23 | | #include "zend_inference.h" |
24 | | #include "zend_call_graph.h" |
25 | | #include "zend_func_info.h" |
26 | | #include "zend_inference.h" |
27 | | #include "zend_call_graph.h" |
28 | | |
29 | | static void zend_op_array_calc(zend_op_array *op_array, void *context) |
30 | 109k | { |
31 | 109k | zend_call_graph *call_graph = context; |
32 | 109k | call_graph->op_arrays_count++; |
33 | 109k | } |
34 | | |
35 | | static void zend_op_array_collect(zend_op_array *op_array, void *context) |
36 | 109k | { |
37 | 109k | zend_call_graph *call_graph = context; |
38 | 109k | zend_func_info *func_info = call_graph->func_infos + call_graph->op_arrays_count; |
39 | | |
40 | 109k | ZEND_SET_FUNC_INFO(op_array, func_info); |
41 | 109k | call_graph->op_arrays[call_graph->op_arrays_count] = op_array; |
42 | 109k | func_info->num = call_graph->op_arrays_count; |
43 | 109k | call_graph->op_arrays_count++; |
44 | 109k | } |
45 | | |
46 | | ZEND_API void zend_analyze_calls(zend_arena **arena, zend_script *script, uint32_t build_flags, zend_op_array *op_array, zend_func_info *func_info) |
47 | 109k | { |
48 | 109k | zend_op *opline = op_array->opcodes; |
49 | 109k | zend_op *end = opline + op_array->last; |
50 | 109k | zend_function *func; |
51 | 109k | zend_call_info *call_info; |
52 | 109k | int call = 0; |
53 | 109k | zend_call_info **call_stack; |
54 | 109k | ALLOCA_FLAG(use_heap); |
55 | 109k | bool is_prototype; |
56 | | |
57 | 109k | call_stack = do_alloca((op_array->last / 2) * sizeof(zend_call_info*), use_heap); |
58 | 109k | call_info = NULL; |
59 | 2.63M | while (opline != end) { |
60 | 2.52M | switch (opline->opcode) { |
61 | 110k | case ZEND_INIT_FCALL: |
62 | 155k | case ZEND_INIT_METHOD_CALL: |
63 | 160k | case ZEND_INIT_STATIC_METHOD_CALL: |
64 | 161k | case ZEND_INIT_PARENT_PROPERTY_HOOK_CALL: |
65 | 161k | call_stack[call] = call_info; |
66 | 161k | func = zend_optimizer_get_called_func( |
67 | 161k | script, op_array, opline, &is_prototype); |
68 | 161k | if (func) { |
69 | 114k | call_info = zend_arena_calloc(arena, 1, sizeof(zend_call_info) + (sizeof(zend_send_arg_info) * ((int)opline->extended_value - 1))); |
70 | 114k | call_info->caller_op_array = op_array; |
71 | 114k | call_info->caller_init_opline = opline; |
72 | 114k | call_info->caller_call_opline = NULL; |
73 | 114k | call_info->callee_func = func; |
74 | 114k | call_info->num_args = opline->extended_value; |
75 | 114k | call_info->next_callee = func_info->callee_info; |
76 | 114k | call_info->is_prototype = is_prototype; |
77 | 114k | call_info->is_frameless = false; |
78 | 114k | func_info->callee_info = call_info; |
79 | | |
80 | 114k | if (build_flags & ZEND_CALL_TREE) { |
81 | 0 | call_info->next_caller = NULL; |
82 | 114k | } else if (func->type == ZEND_INTERNAL_FUNCTION |
83 | 114k | || func->op_array.filename != script->filename) { |
84 | 91.3k | call_info->next_caller = NULL; |
85 | 91.3k | } else { |
86 | 23.0k | zend_func_info *callee_func_info = ZEND_FUNC_INFO(&func->op_array); |
87 | 23.0k | if (callee_func_info) { |
88 | 22.9k | call_info->next_caller = callee_func_info->caller_info; |
89 | 22.9k | callee_func_info->caller_info = call_info; |
90 | 22.9k | } else { |
91 | 22 | call_info->next_caller = NULL; |
92 | 22 | } |
93 | 23.0k | } |
94 | 114k | } else { |
95 | 46.6k | call_info = NULL; |
96 | 46.6k | } |
97 | 161k | call++; |
98 | 161k | break; |
99 | 4.51k | case ZEND_INIT_FCALL_BY_NAME: |
100 | 7.03k | case ZEND_INIT_NS_FCALL_BY_NAME: |
101 | 11.7k | case ZEND_INIT_DYNAMIC_CALL: |
102 | 82.6k | case ZEND_NEW: |
103 | 83.8k | case ZEND_INIT_USER_CALL: |
104 | 83.8k | call_stack[call] = call_info; |
105 | 83.8k | call_info = NULL; |
106 | 83.8k | call++; |
107 | 83.8k | break; |
108 | 0 | case ZEND_FRAMELESS_ICALL_0: |
109 | 0 | case ZEND_FRAMELESS_ICALL_1: |
110 | 0 | case ZEND_FRAMELESS_ICALL_2: |
111 | 0 | case ZEND_FRAMELESS_ICALL_3: { |
112 | 0 | func = ZEND_FLF_FUNC(opline); |
113 | 0 | zend_call_info *call_info = zend_arena_calloc(arena, 1, sizeof(zend_call_info)); |
114 | 0 | call_info->caller_op_array = op_array; |
115 | 0 | call_info->caller_init_opline = opline; |
116 | 0 | call_info->caller_call_opline = NULL; |
117 | 0 | call_info->callee_func = func; |
118 | 0 | call_info->num_args = ZEND_FLF_NUM_ARGS(opline->opcode); |
119 | 0 | call_info->next_callee = func_info->callee_info; |
120 | 0 | call_info->is_prototype = false; |
121 | 0 | call_info->is_frameless = true; |
122 | 0 | call_info->next_caller = NULL; |
123 | 0 | func_info->callee_info = call_info; |
124 | 0 | break; |
125 | 0 | } |
126 | 233k | case ZEND_DO_FCALL: |
127 | 233k | case ZEND_DO_ICALL: |
128 | 244k | case ZEND_DO_UCALL: |
129 | 244k | case ZEND_DO_FCALL_BY_NAME: |
130 | 244k | case ZEND_CALLABLE_CONVERT: |
131 | 244k | func_info->flags |= ZEND_FUNC_HAS_CALLS; |
132 | 244k | if (call_info) { |
133 | 114k | call_info->caller_call_opline = opline; |
134 | 114k | } |
135 | 244k | call--; |
136 | 244k | call_info = call_stack[call]; |
137 | 244k | break; |
138 | 70.6k | case ZEND_SEND_VAL: |
139 | 121k | case ZEND_SEND_VAR: |
140 | 150k | case ZEND_SEND_VAL_EX: |
141 | 226k | case ZEND_SEND_VAR_EX: |
142 | 227k | case ZEND_SEND_FUNC_ARG: |
143 | 230k | case ZEND_SEND_REF: |
144 | 230k | case ZEND_SEND_VAR_NO_REF: |
145 | 234k | case ZEND_SEND_VAR_NO_REF_EX: |
146 | 237k | case ZEND_SEND_USER: |
147 | 237k | if (call_info) { |
148 | 124k | if (opline->op2_type == IS_CONST) { |
149 | 1.83k | call_info->named_args = 1; |
150 | 1.83k | break; |
151 | 1.83k | } |
152 | | |
153 | 122k | uint32_t num = opline->op2.num; |
154 | 122k | if (num > 0) { |
155 | 122k | num--; |
156 | 122k | } |
157 | 122k | call_info->arg_info[num].opline = opline; |
158 | 122k | } |
159 | 235k | break; |
160 | 235k | case ZEND_SEND_ARRAY: |
161 | 1.42k | case ZEND_SEND_UNPACK: |
162 | 1.42k | if (call_info) { |
163 | 973 | call_info->send_unpack = 1; |
164 | 973 | } |
165 | 1.42k | break; |
166 | 2.52M | } |
167 | 2.52M | opline++; |
168 | 2.52M | } |
169 | 109k | free_alloca(call_stack, use_heap); |
170 | 109k | } |
171 | | |
172 | | static bool zend_is_indirectly_recursive(zend_op_array *root, zend_op_array *op_array, zend_bitset visited) |
173 | 25.3k | { |
174 | 25.3k | zend_func_info *func_info; |
175 | 25.3k | zend_call_info *call_info; |
176 | 25.3k | bool ret = 0; |
177 | | |
178 | 25.3k | if (op_array == root) { |
179 | 0 | return 1; |
180 | 0 | } |
181 | | |
182 | 25.3k | func_info = ZEND_FUNC_INFO(op_array); |
183 | 25.3k | if (zend_bitset_in(visited, func_info->num)) { |
184 | 1.65k | return 0; |
185 | 1.65k | } |
186 | 23.7k | zend_bitset_incl(visited, func_info->num); |
187 | 23.7k | call_info = func_info->caller_info; |
188 | 26.6k | while (call_info) { |
189 | 2.90k | if (zend_is_indirectly_recursive(root, call_info->caller_op_array, visited)) { |
190 | 0 | call_info->recursive = 1; |
191 | 0 | ret = 1; |
192 | 0 | } |
193 | 2.90k | call_info = call_info->next_caller; |
194 | 2.90k | } |
195 | 23.7k | return ret; |
196 | 25.3k | } |
197 | | |
198 | | static void zend_analyze_recursion(zend_call_graph *call_graph) |
199 | 67.3k | { |
200 | 67.3k | zend_op_array *op_array; |
201 | 67.3k | zend_func_info *func_info; |
202 | 67.3k | zend_call_info *call_info; |
203 | 67.3k | int i; |
204 | 67.3k | int set_len = zend_bitset_len(call_graph->op_arrays_count); |
205 | 67.3k | zend_bitset visited; |
206 | 67.3k | ALLOCA_FLAG(use_heap); |
207 | | |
208 | 67.3k | visited = ZEND_BITSET_ALLOCA(set_len, use_heap); |
209 | 176k | for (i = 0; i < call_graph->op_arrays_count; i++) { |
210 | 109k | op_array = call_graph->op_arrays[i]; |
211 | 109k | func_info = call_graph->func_infos + i; |
212 | 109k | call_info = func_info->caller_info; |
213 | 132k | for (; call_info; call_info = call_info->next_caller) { |
214 | 22.9k | if (call_info->is_prototype) { |
215 | | /* Might be calling an overridden child method and not actually recursive. */ |
216 | 292 | continue; |
217 | 292 | } |
218 | 22.6k | if (call_info->caller_op_array == op_array) { |
219 | 195 | call_info->recursive = 1; |
220 | 195 | func_info->flags |= ZEND_FUNC_RECURSIVE | ZEND_FUNC_RECURSIVE_DIRECTLY; |
221 | 22.4k | } else { |
222 | 22.4k | memset(visited, 0, sizeof(zend_ulong) * set_len); |
223 | 22.4k | if (zend_is_indirectly_recursive(op_array, call_info->caller_op_array, visited)) { |
224 | 0 | call_info->recursive = 1; |
225 | 0 | func_info->flags |= ZEND_FUNC_RECURSIVE | ZEND_FUNC_RECURSIVE_INDIRECTLY; |
226 | 0 | } |
227 | 22.4k | } |
228 | 22.6k | } |
229 | 109k | } |
230 | | |
231 | 67.3k | free_alloca(visited, use_heap); |
232 | 67.3k | } |
233 | | |
234 | | static void zend_sort_op_arrays(zend_call_graph *call_graph) |
235 | 67.3k | { |
236 | 67.3k | (void) call_graph; |
237 | | |
238 | | // TODO: perform topological sort of cyclic call graph |
239 | 67.3k | } |
240 | | |
241 | | ZEND_API void zend_build_call_graph(zend_arena **arena, zend_script *script, zend_call_graph *call_graph) /* {{{ */ |
242 | 67.3k | { |
243 | 67.3k | call_graph->op_arrays_count = 0; |
244 | 67.3k | zend_foreach_op_array(script, zend_op_array_calc, call_graph); |
245 | | |
246 | 67.3k | call_graph->op_arrays = (zend_op_array**)zend_arena_calloc(arena, call_graph->op_arrays_count, sizeof(zend_op_array*)); |
247 | 67.3k | call_graph->func_infos = (zend_func_info*)zend_arena_calloc(arena, call_graph->op_arrays_count, sizeof(zend_func_info)); |
248 | 67.3k | call_graph->op_arrays_count = 0; |
249 | 67.3k | zend_foreach_op_array(script, zend_op_array_collect, call_graph); |
250 | 67.3k | } |
251 | | /* }}} */ |
252 | | |
253 | | ZEND_API void zend_analyze_call_graph(zend_arena **arena, zend_script *script, zend_call_graph *call_graph) /* {{{ */ |
254 | 67.3k | { |
255 | 67.3k | int i; |
256 | | |
257 | 176k | for (i = 0; i < call_graph->op_arrays_count; i++) { |
258 | 109k | zend_analyze_calls(arena, script, 0, call_graph->op_arrays[i], call_graph->func_infos + i); |
259 | 109k | } |
260 | 67.3k | zend_analyze_recursion(call_graph); |
261 | 67.3k | zend_sort_op_arrays(call_graph); |
262 | 67.3k | } |
263 | | /* }}} */ |
264 | | |
265 | | ZEND_API zend_call_info **zend_build_call_map(zend_arena **arena, zend_func_info *info, const zend_op_array *op_array) /* {{{ */ |
266 | 109k | { |
267 | 109k | zend_call_info **map, *call; |
268 | 109k | if (!info->callee_info) { |
269 | | /* Don't build call map if function contains no calls */ |
270 | 65.9k | return NULL; |
271 | 65.9k | } |
272 | | |
273 | 43.1k | map = zend_arena_calloc(arena, sizeof(zend_call_info *), op_array->last); |
274 | 157k | for (call = info->callee_info; call; call = call->next_callee) { |
275 | 114k | int i; |
276 | 114k | map[call->caller_init_opline - op_array->opcodes] = call; |
277 | 114k | if (call->caller_call_opline) { |
278 | 114k | map[call->caller_call_opline - op_array->opcodes] = call; |
279 | 114k | } |
280 | 114k | if (!call->is_frameless) { |
281 | 236k | for (i = 0; i < call->num_args; i++) { |
282 | 122k | if (call->arg_info[i].opline) { |
283 | 122k | map[call->arg_info[i].opline - op_array->opcodes] = call; |
284 | 122k | } |
285 | 122k | } |
286 | 114k | } |
287 | 114k | } |
288 | 43.1k | return map; |
289 | 109k | } |
290 | | /* }}} */ |