/src/php-src/Zend/Optimizer/zend_call_graph.c

Source (jump to first uncovered line)
/*
   +----------------------------------------------------------------------+
   | Zend Engine, Call Graph                                              |
   +----------------------------------------------------------------------+
   | Copyright (c) The PHP Group                                          |
   +----------------------------------------------------------------------+
   | This source file is subject to version 3.01 of the PHP license,      |
   | that is bundled with this package in the file LICENSE, and is        |
   | available through the world-wide-web at the following url:           |
   | https://www.php.net/license/3_01.txt                                 |
   | If you did not receive a copy of the PHP license and are unable to   |
   | obtain it through the world-wide-web, please send a note to          |
   | license@php.net so we can mail you a copy immediately.               |
   +----------------------------------------------------------------------+
   | Authors: Dmitry Stogov <dmitry@php.net>                              |
   +----------------------------------------------------------------------+
*/

#include "zend_compile.h"
#include "zend_extensions.h"
#include "Optimizer/zend_optimizer.h"
#include "zend_optimizer_internal.h"
#include "zend_inference.h"
#include "zend_call_graph.h"
#include "zend_func_info.h"
#include "zend_inference.h"
#include "zend_call_graph.h"

static void zend_op_array_calc(zend_op_array *op_array, void *context)
{
  zend_call_graph *call_graph = context;
  call_graph->op_arrays_count++;
}

static void zend_op_array_collect(zend_op_array *op_array, void *context)
{
  zend_call_graph *call_graph = context;
  zend_func_info *func_info = call_graph->func_infos + call_graph->op_arrays_count;

  ZEND_SET_FUNC_INFO(op_array, func_info);
  call_graph->op_arrays[call_graph->op_arrays_count] = op_array;
  func_info->num = call_graph->op_arrays_count;
  call_graph->op_arrays_count++;
}

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)
{
  zend_op *opline = op_array->opcodes;
  zend_op *end = opline + op_array->last;
  zend_function *func;
  zend_call_info *call_info;
  int call = 0;
  zend_call_info **call_stack;
  ALLOCA_FLAG(use_heap);
  bool is_prototype;

  call_stack = do_alloca((op_array->last / 2) * sizeof(zend_call_info*), use_heap);
  call_info = NULL;
  while (opline != end) {
    switch (opline->opcode) {
      case ZEND_INIT_FCALL:
      case ZEND_INIT_METHOD_CALL:
      case ZEND_INIT_STATIC_METHOD_CALL:
      case ZEND_INIT_PARENT_PROPERTY_HOOK_CALL:
        call_stack[call] = call_info;
        func = zend_optimizer_get_called_func(
          script, op_array, opline, &is_prototype);
        if (func) {
          call_info = zend_arena_calloc(arena, 1, sizeof(zend_call_info) + (sizeof(zend_send_arg_info) * ((int)opline->extended_value - 1)));
          call_info->caller_op_array = op_array;
          call_info->caller_init_opline = opline;
          call_info->caller_call_opline = NULL;
          call_info->callee_func = func;
          call_info->num_args = opline->extended_value;
          call_info->next_callee = func_info->callee_info;
          call_info->is_prototype = is_prototype;
          call_info->is_frameless = false;
          func_info->callee_info = call_info;

          if (build_flags & ZEND_CALL_TREE) {
            call_info->next_caller = NULL;
          } else if (func->type == ZEND_INTERNAL_FUNCTION
           || func->op_array.filename != script->filename) {
            call_info->next_caller = NULL;
          } else {
            zend_func_info *callee_func_info = ZEND_FUNC_INFO(&func->op_array);
            if (callee_func_info) {
              call_info->next_caller = callee_func_info->caller_info;
              callee_func_info->caller_info = call_info;
            } else {
              call_info->next_caller = NULL;
            }
          }
        } else {
          call_info = NULL;
        }
        call++;
        break;
      case ZEND_INIT_FCALL_BY_NAME:
      case ZEND_INIT_NS_FCALL_BY_NAME:
      case ZEND_INIT_DYNAMIC_CALL:
      case ZEND_NEW:
      case ZEND_INIT_USER_CALL:
        call_stack[call] = call_info;
        call_info = NULL;
        call++;
        break;
      case ZEND_FRAMELESS_ICALL_0:
      case ZEND_FRAMELESS_ICALL_1:
      case ZEND_FRAMELESS_ICALL_2:
      case ZEND_FRAMELESS_ICALL_3: {
        func = ZEND_FLF_FUNC(opline);
        zend_call_info *call_info = zend_arena_calloc(arena, 1, sizeof(zend_call_info));
        call_info->caller_op_array = op_array;
        call_info->caller_init_opline = opline;
        call_info->caller_call_opline = NULL;
        call_info->callee_func = func;
        call_info->num_args = ZEND_FLF_NUM_ARGS(opline->opcode);
        call_info->next_callee = func_info->callee_info;
        call_info->is_prototype = false;
        call_info->is_frameless = true;
        call_info->next_caller = NULL;
        func_info->callee_info = call_info;
        break;
      }
      case ZEND_DO_FCALL:
      case ZEND_DO_ICALL:
      case ZEND_DO_UCALL:
      case ZEND_DO_FCALL_BY_NAME:
      case ZEND_CALLABLE_CONVERT:
        func_info->flags |= ZEND_FUNC_HAS_CALLS;
        if (call_info) {
          call_info->caller_call_opline = opline;
        }
        call--;
        call_info = call_stack[call];
        break;
      case ZEND_SEND_VAL:
      case ZEND_SEND_VAR:
      case ZEND_SEND_VAL_EX:
      case ZEND_SEND_VAR_EX:
      case ZEND_SEND_FUNC_ARG:
      case ZEND_SEND_REF:
      case ZEND_SEND_VAR_NO_REF:
      case ZEND_SEND_VAR_NO_REF_EX:
      case ZEND_SEND_USER:
        if (call_info) {
          if (opline->op2_type == IS_CONST) {
            call_info->named_args = 1;
            break;
          }

          uint32_t num = opline->op2.num;
          if (num > 0) {
            num--;
          }
          call_info->arg_info[num].opline = opline;
        }
        break;
      case ZEND_SEND_ARRAY:
      case ZEND_SEND_UNPACK:
        if (call_info) {
          call_info->send_unpack = 1;
        }
        break;
    }
    opline++;
  }
  free_alloca(call_stack, use_heap);
}

static bool zend_is_indirectly_recursive(zend_op_array *root, zend_op_array *op_array, zend_bitset visited)
{
  zend_func_info *func_info;
  zend_call_info *call_info;
  bool ret = 0;

  if (op_array == root) {
    return 1;
  }

  func_info = ZEND_FUNC_INFO(op_array);
  if (zend_bitset_in(visited, func_info->num)) {
    return 0;
  }
  zend_bitset_incl(visited, func_info->num);
  call_info = func_info->caller_info;
  while (call_info) {
    if (zend_is_indirectly_recursive(root, call_info->caller_op_array, visited)) {
      call_info->recursive = 1;
      ret = 1;
    }
    call_info = call_info->next_caller;
  }
  return ret;
}

static void zend_analyze_recursion(zend_call_graph *call_graph)
{
  zend_op_array *op_array;
  zend_func_info *func_info;
  zend_call_info *call_info;
  int i;
  int set_len = zend_bitset_len(call_graph->op_arrays_count);
  zend_bitset visited;
  ALLOCA_FLAG(use_heap);

  visited = ZEND_BITSET_ALLOCA(set_len, use_heap);
  for (i = 0; i < call_graph->op_arrays_count; i++) {
    op_array = call_graph->op_arrays[i];
    func_info = call_graph->func_infos + i;
    call_info = func_info->caller_info;
    for (; call_info; call_info = call_info->next_caller) {
      if (call_info->is_prototype) {
        /* Might be calling an overridden child method and not actually recursive. */
        continue;
      }
      if (call_info->caller_op_array == op_array) {
        call_info->recursive = 1;
        func_info->flags |= ZEND_FUNC_RECURSIVE | ZEND_FUNC_RECURSIVE_DIRECTLY;
      } else {
        memset(visited, 0, sizeof(zend_ulong) * set_len);
        if (zend_is_indirectly_recursive(op_array, call_info->caller_op_array, visited)) {
          call_info->recursive = 1;
          func_info->flags |= ZEND_FUNC_RECURSIVE | ZEND_FUNC_RECURSIVE_INDIRECTLY;
        }
      }
    }
  }

  free_alloca(visited, use_heap);
}

static void zend_sort_op_arrays(zend_call_graph *call_graph)
{
  (void) call_graph;

  // TODO: perform topological sort of cyclic call graph
}

ZEND_API void zend_build_call_graph(zend_arena **arena, zend_script *script, zend_call_graph *call_graph) /* {{{ */
{
  call_graph->op_arrays_count = 0;
  zend_foreach_op_array(script, zend_op_array_calc, call_graph);

  call_graph->op_arrays = (zend_op_array**)zend_arena_calloc(arena, call_graph->op_arrays_count, sizeof(zend_op_array*));
  call_graph->func_infos = (zend_func_info*)zend_arena_calloc(arena, call_graph->op_arrays_count, sizeof(zend_func_info));
  call_graph->op_arrays_count = 0;
  zend_foreach_op_array(script, zend_op_array_collect, call_graph);
}
/* }}} */

ZEND_API void zend_analyze_call_graph(zend_arena **arena, zend_script *script, zend_call_graph *call_graph) /* {{{ */
{
  int i;

  for (i = 0; i < call_graph->op_arrays_count; i++) {
    zend_analyze_calls(arena, script, 0, call_graph->op_arrays[i], call_graph->func_infos + i);
  }
  zend_analyze_recursion(call_graph);
  zend_sort_op_arrays(call_graph);
}
/* }}} */

ZEND_API zend_call_info **zend_build_call_map(zend_arena **arena, zend_func_info *info, const zend_op_array *op_array) /* {{{ */
{
  zend_call_info **map, *call;
  if (!info->callee_info) {
    /* Don't build call map if function contains no calls */
    return NULL;
  }

  map = zend_arena_calloc(arena, sizeof(zend_call_info *), op_array->last);
  for (call = info->callee_info; call; call = call->next_callee) {
    int i;
    map[call->caller_init_opline - op_array->opcodes] = call;
    if (call->caller_call_opline) {
      map[call->caller_call_opline - op_array->opcodes] = call;
    }
    if (!call->is_frameless) {
      for (i = 0; i < call->num_args; i++) {
        if (call->arg_info[i].opline) {
          map[call->arg_info[i].opline - op_array->opcodes] = call;
        }
      }
    }
  }
  return map;
}
/* }}} */

Coverage Report

Created: 2025-06-13 06:43

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		/* }}} */