diff options
Diffstat (limited to 'Zend/Optimizer/zend_call_graph.c')
| -rw-r--r-- | Zend/Optimizer/zend_call_graph.c | 271 |
1 files changed, 271 insertions, 0 deletions
diff --git a/Zend/Optimizer/zend_call_graph.c b/Zend/Optimizer/zend_call_graph.c new file mode 100644 index 0000000000..b0f3247cd7 --- /dev/null +++ b/Zend/Optimizer/zend_call_graph.c @@ -0,0 +1,271 @@ +/* + +----------------------------------------------------------------------+ + | 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: | + | http://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 "php.h" +#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 int 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: + call_stack[call] = call_info; + func = zend_optimizer_get_called_func( + script, op_array, opline, &is_prototype); + /* TODO: Support prototypes? */ + if (func && !is_prototype) { + 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; + func_info->callee_info = call_info; + + if (build_flags & ZEND_CALL_TREE) { + call_info->next_caller = NULL; + } else if (func->type == ZEND_INTERNAL_FUNCTION) { + 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_DO_FCALL: + case ZEND_DO_ICALL: + case ZEND_DO_UCALL: + case ZEND_DO_FCALL_BY_NAME: + 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; + case ZEND_EXIT: + /* In this case the DO_CALL opcode may have been dropped + * and caller_call_opline will be NULL. */ + break; + } + opline++; + } + free_alloca(call_stack, use_heap); + return SUCCESS; +} + +static int 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; + int 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; + while (call_info) { + 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; + } + } + call_info = call_info->next_caller; + } + } + + 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 int 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); + + return SUCCESS; +} +/* }}} */ + +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; + } + 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; +} +/* }}} */ |