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

Source
/*
   +----------------------------------------------------------------------+
   | Zend Engine, Call Graph                                              |
   +----------------------------------------------------------------------+
   | Copyright © The PHP Group and Contributors.                          |
   +----------------------------------------------------------------------+
   | This source file is subject to the Modified BSD License that is      |
   | bundled with this package in the file LICENSE, and is available      |
   | through the World Wide Web at <https://www.php.net/license/>.        |
   |                                                                      |
   | SPDX-License-Identifier: BSD-3-Clause                                |
   +----------------------------------------------------------------------+
   | 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"

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 = true;
            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 = true;
        }
        break;
    }
    opline++;
  }
  free_alloca(call_stack, use_heap);
}

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

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

  func_info = ZEND_FUNC_INFO(op_array);
  if (zend_bitset_in(visited, func_info->num)) {
    return false;
  }
  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 = true;
      ret = true;
    }
    call_info = call_info->next_caller;
  }
  return ret;
}

static void zend_analyze_recursion(zend_call_graph *call_graph)
{
  const zend_op_array *op_array;
  zend_func_info *func_info;
  zend_call_info *call_info;
  uint32_t 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 (uint32_t 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 = true;
        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 = true;
          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) /* {{{ */
{
  for (uint32_t 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, const 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) {
    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 (uint32_t 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: 2026-06-02 06:40

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