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 | http://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 "php.h"
20 #include "zend_compile.h"
21 #include "zend_extensions.h"
22 #include "Optimizer/zend_optimizer.h"
23 #include "zend_optimizer_internal.h"
24 #include "zend_inference.h"
25 #include "zend_call_graph.h"
26 #include "zend_func_info.h"
27 #include "zend_inference.h"
28 #include "zend_call_graph.h"
29
zend_op_array_calc(zend_op_array * op_array,void * context)30 static void zend_op_array_calc(zend_op_array *op_array, void *context)
31 {
32 zend_call_graph *call_graph = context;
33 call_graph->op_arrays_count++;
34 }
35
zend_op_array_collect(zend_op_array * op_array,void * context)36 static void zend_op_array_collect(zend_op_array *op_array, void *context)
37 {
38 zend_call_graph *call_graph = context;
39 zend_func_info *func_info = call_graph->func_infos + call_graph->op_arrays_count;
40
41 ZEND_SET_FUNC_INFO(op_array, func_info);
42 call_graph->op_arrays[call_graph->op_arrays_count] = op_array;
43 func_info->num = call_graph->op_arrays_count;
44 call_graph->op_arrays_count++;
45 }
46
zend_analyze_calls(zend_arena ** arena,zend_script * script,uint32_t build_flags,zend_op_array * op_array,zend_func_info * func_info)47 int zend_analyze_calls(zend_arena **arena, zend_script *script, uint32_t build_flags, zend_op_array *op_array, zend_func_info *func_info)
48 {
49 zend_op *opline = op_array->opcodes;
50 zend_op *end = opline + op_array->last;
51 zend_function *func;
52 zend_call_info *call_info;
53 int call = 0;
54 zend_call_info **call_stack;
55 ALLOCA_FLAG(use_heap);
56 zend_bool is_prototype;
57
58 call_stack = do_alloca((op_array->last / 2) * sizeof(zend_call_info*), use_heap);
59 call_info = NULL;
60 while (opline != end) {
61 switch (opline->opcode) {
62 case ZEND_INIT_FCALL:
63 case ZEND_INIT_METHOD_CALL:
64 case ZEND_INIT_STATIC_METHOD_CALL:
65 call_stack[call] = call_info;
66 func = zend_optimizer_get_called_func(
67 script, op_array, opline, &is_prototype);
68 /* TODO: Support prototypes? */
69 if (func && !is_prototype) {
70 call_info = zend_arena_calloc(arena, 1, sizeof(zend_call_info) + (sizeof(zend_send_arg_info) * ((int)opline->extended_value - 1)));
71 call_info->caller_op_array = op_array;
72 call_info->caller_init_opline = opline;
73 call_info->caller_call_opline = NULL;
74 call_info->callee_func = func;
75 call_info->num_args = opline->extended_value;
76 call_info->next_callee = func_info->callee_info;
77 func_info->callee_info = call_info;
78
79 if (build_flags & ZEND_CALL_TREE) {
80 call_info->next_caller = NULL;
81 } else if (func->type == ZEND_INTERNAL_FUNCTION) {
82 call_info->next_caller = NULL;
83 } else {
84 zend_func_info *callee_func_info = ZEND_FUNC_INFO(&func->op_array);
85 if (callee_func_info) {
86 call_info->next_caller = callee_func_info->caller_info;
87 callee_func_info->caller_info = call_info;
88 } else {
89 call_info->next_caller = NULL;
90 }
91 }
92 } else {
93 call_info = NULL;
94 }
95 call++;
96 break;
97 case ZEND_INIT_FCALL_BY_NAME:
98 case ZEND_INIT_NS_FCALL_BY_NAME:
99 case ZEND_INIT_DYNAMIC_CALL:
100 case ZEND_NEW:
101 case ZEND_INIT_USER_CALL:
102 call_stack[call] = call_info;
103 call_info = NULL;
104 call++;
105 break;
106 case ZEND_DO_FCALL:
107 case ZEND_DO_ICALL:
108 case ZEND_DO_UCALL:
109 case ZEND_DO_FCALL_BY_NAME:
110 func_info->flags |= ZEND_FUNC_HAS_CALLS;
111 if (call_info) {
112 call_info->caller_call_opline = opline;
113 }
114 call--;
115 call_info = call_stack[call];
116 break;
117 case ZEND_SEND_VAL:
118 case ZEND_SEND_VAR:
119 case ZEND_SEND_VAL_EX:
120 case ZEND_SEND_VAR_EX:
121 case ZEND_SEND_FUNC_ARG:
122 case ZEND_SEND_REF:
123 case ZEND_SEND_VAR_NO_REF:
124 case ZEND_SEND_VAR_NO_REF_EX:
125 case ZEND_SEND_USER:
126 if (call_info) {
127 if (opline->op2_type == IS_CONST) {
128 call_info->named_args = 1;
129 break;
130 }
131
132 uint32_t num = opline->op2.num;
133 if (num > 0) {
134 num--;
135 }
136 call_info->arg_info[num].opline = opline;
137 }
138 break;
139 case ZEND_SEND_ARRAY:
140 case ZEND_SEND_UNPACK:
141 if (call_info) {
142 call_info->send_unpack = 1;
143 }
144 break;
145 case ZEND_EXIT:
146 /* In this case the DO_CALL opcode may have been dropped
147 * and caller_call_opline will be NULL. */
148 break;
149 }
150 opline++;
151 }
152 free_alloca(call_stack, use_heap);
153 return SUCCESS;
154 }
155
zend_is_indirectly_recursive(zend_op_array * root,zend_op_array * op_array,zend_bitset visited)156 static int zend_is_indirectly_recursive(zend_op_array *root, zend_op_array *op_array, zend_bitset visited)
157 {
158 zend_func_info *func_info;
159 zend_call_info *call_info;
160 int ret = 0;
161
162 if (op_array == root) {
163 return 1;
164 }
165
166 func_info = ZEND_FUNC_INFO(op_array);
167 if (zend_bitset_in(visited, func_info->num)) {
168 return 0;
169 }
170 zend_bitset_incl(visited, func_info->num);
171 call_info = func_info->caller_info;
172 while (call_info) {
173 if (zend_is_indirectly_recursive(root, call_info->caller_op_array, visited)) {
174 call_info->recursive = 1;
175 ret = 1;
176 }
177 call_info = call_info->next_caller;
178 }
179 return ret;
180 }
181
zend_analyze_recursion(zend_call_graph * call_graph)182 static void zend_analyze_recursion(zend_call_graph *call_graph)
183 {
184 zend_op_array *op_array;
185 zend_func_info *func_info;
186 zend_call_info *call_info;
187 int i;
188 int set_len = zend_bitset_len(call_graph->op_arrays_count);
189 zend_bitset visited;
190 ALLOCA_FLAG(use_heap);
191
192 visited = ZEND_BITSET_ALLOCA(set_len, use_heap);
193 for (i = 0; i < call_graph->op_arrays_count; i++) {
194 op_array = call_graph->op_arrays[i];
195 func_info = call_graph->func_infos + i;
196 call_info = func_info->caller_info;
197 while (call_info) {
198 if (call_info->caller_op_array == op_array) {
199 call_info->recursive = 1;
200 func_info->flags |= ZEND_FUNC_RECURSIVE | ZEND_FUNC_RECURSIVE_DIRECTLY;
201 } else {
202 memset(visited, 0, sizeof(zend_ulong) * set_len);
203 if (zend_is_indirectly_recursive(op_array, call_info->caller_op_array, visited)) {
204 call_info->recursive = 1;
205 func_info->flags |= ZEND_FUNC_RECURSIVE | ZEND_FUNC_RECURSIVE_INDIRECTLY;
206 }
207 }
208 call_info = call_info->next_caller;
209 }
210 }
211
212 free_alloca(visited, use_heap);
213 }
214
zend_sort_op_arrays(zend_call_graph * call_graph)215 static void zend_sort_op_arrays(zend_call_graph *call_graph)
216 {
217 (void) call_graph;
218
219 // TODO: perform topological sort of cyclic call graph
220 }
221
zend_build_call_graph(zend_arena ** arena,zend_script * script,zend_call_graph * call_graph)222 int zend_build_call_graph(zend_arena **arena, zend_script *script, zend_call_graph *call_graph) /* {{{ */
223 {
224 call_graph->op_arrays_count = 0;
225 zend_foreach_op_array(script, zend_op_array_calc, call_graph);
226
227 call_graph->op_arrays = (zend_op_array**)zend_arena_calloc(arena, call_graph->op_arrays_count, sizeof(zend_op_array*));
228 call_graph->func_infos = (zend_func_info*)zend_arena_calloc(arena, call_graph->op_arrays_count, sizeof(zend_func_info));
229 call_graph->op_arrays_count = 0;
230 zend_foreach_op_array(script, zend_op_array_collect, call_graph);
231
232 return SUCCESS;
233 }
234 /* }}} */
235
zend_analyze_call_graph(zend_arena ** arena,zend_script * script,zend_call_graph * call_graph)236 void zend_analyze_call_graph(zend_arena **arena, zend_script *script, zend_call_graph *call_graph) /* {{{ */
237 {
238 int i;
239
240 for (i = 0; i < call_graph->op_arrays_count; i++) {
241 zend_analyze_calls(arena, script, 0, call_graph->op_arrays[i], call_graph->func_infos + i);
242 }
243 zend_analyze_recursion(call_graph);
244 zend_sort_op_arrays(call_graph);
245 }
246 /* }}} */
247
zend_build_call_map(zend_arena ** arena,zend_func_info * info,const zend_op_array * op_array)248 zend_call_info **zend_build_call_map(zend_arena **arena, zend_func_info *info, const zend_op_array *op_array) /* {{{ */
249 {
250 zend_call_info **map, *call;
251 if (!info->callee_info) {
252 /* Don't build call map if function contains no calls */
253 return NULL;
254 }
255
256 map = zend_arena_calloc(arena, sizeof(zend_call_info *), op_array->last);
257 for (call = info->callee_info; call; call = call->next_callee) {
258 int i;
259 map[call->caller_init_opline - op_array->opcodes] = call;
260 if (call->caller_call_opline) {
261 map[call->caller_call_opline - op_array->opcodes] = call;
262 }
263 for (i = 0; i < call->num_args; i++) {
264 if (call->arg_info[i].opline) {
265 map[call->arg_info[i].opline - op_array->opcodes] = call;
266 }
267 }
268 }
269 return map;
270 }
271 /* }}} */
272
