diff options
Diffstat (limited to 'Zend/Optimizer/zend_dfg.c')
| -rw-r--r-- | Zend/Optimizer/zend_dfg.c | 333 |
1 files changed, 333 insertions, 0 deletions
diff --git a/Zend/Optimizer/zend_dfg.c b/Zend/Optimizer/zend_dfg.c new file mode 100644 index 0000000000..b059f1f0ea --- /dev/null +++ b/Zend/Optimizer/zend_dfg.c @@ -0,0 +1,333 @@ +/* + +----------------------------------------------------------------------+ + | Zend Engine, DFG - Data Flow 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_dfg.h" + +static zend_always_inline void _zend_dfg_add_use_def_op(const zend_op_array *op_array, const zend_op *opline, uint32_t build_flags, zend_bitset use, zend_bitset def) /* {{{ */ +{ + uint32_t var_num; + const zend_op *next; + + if (opline->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { + var_num = EX_VAR_TO_NUM(opline->op1.var); + if (!zend_bitset_in(def, var_num)) { + zend_bitset_incl(use, var_num); + } + } + if (((opline->op2_type & (IS_VAR|IS_TMP_VAR)) != 0 + && opline->opcode != ZEND_FE_FETCH_R + && opline->opcode != ZEND_FE_FETCH_RW) + || (opline->op2_type == IS_CV)) { + var_num = EX_VAR_TO_NUM(opline->op2.var); + if (!zend_bitset_in(def, var_num)) { + zend_bitset_incl(use, var_num); + } + } + if ((build_flags & ZEND_SSA_USE_CV_RESULTS) + && opline->result_type == IS_CV + && opline->opcode != ZEND_RECV) { + var_num = EX_VAR_TO_NUM(opline->result.var); + if (!zend_bitset_in(def, var_num)) { + zend_bitset_incl(use, var_num); + } + } + + switch (opline->opcode) { + case ZEND_ASSIGN: + if ((build_flags & ZEND_SSA_RC_INFERENCE) && opline->op2_type == IS_CV) { + zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op2.var)); + } + if (opline->op1_type == IS_CV) { +add_op1_def: + zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op1.var)); + } + break; + case ZEND_ASSIGN_REF: + if (opline->op2_type == IS_CV) { + zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op2.var)); + } + if (opline->op1_type == IS_CV) { + goto add_op1_def; + } + break; + case ZEND_ASSIGN_DIM: + case ZEND_ASSIGN_OBJ: + next = opline + 1; + if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { + var_num = EX_VAR_TO_NUM(next->op1.var); + if (!zend_bitset_in(def, var_num)) { + zend_bitset_incl(use, var_num); + } + if (build_flags & ZEND_SSA_RC_INFERENCE && next->op1_type == IS_CV) { + zend_bitset_incl(def, var_num); + } + } + if (opline->op1_type == IS_CV) { + goto add_op1_def; + } + break; + case ZEND_ASSIGN_OBJ_REF: + next = opline + 1; + if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { + var_num = EX_VAR_TO_NUM(next->op1.var); + if (!zend_bitset_in(def, var_num)) { + zend_bitset_incl(use, var_num); + } + if (next->op1_type == IS_CV) { + zend_bitset_incl(def, var_num); + } + } + if (opline->op1_type == IS_CV) { + goto add_op1_def; + } + break; + case ZEND_ASSIGN_STATIC_PROP: + next = opline + 1; + if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { + var_num = EX_VAR_TO_NUM(next->op1.var); + if (!zend_bitset_in(def, var_num)) { + zend_bitset_incl(use, var_num); + } + if ((build_flags & ZEND_SSA_RC_INFERENCE) && next->op1_type == IS_CV) { + zend_bitset_incl(def, var_num); + } + } + break; + case ZEND_ASSIGN_STATIC_PROP_REF: + next = opline + 1; + if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { + var_num = EX_VAR_TO_NUM(next->op1.var); + if (!zend_bitset_in(def, var_num)) { + zend_bitset_incl(use, var_num); + } + if (next->op1_type == IS_CV) { + zend_bitset_incl(def, var_num); + } + } + break; + case ZEND_ASSIGN_STATIC_PROP_OP: + next = opline + 1; + if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { + var_num = EX_VAR_TO_NUM(next->op1.var); + if (!zend_bitset_in(def, var_num)) { + zend_bitset_incl(use, var_num); + } + } + break; + case ZEND_ASSIGN_DIM_OP: + case ZEND_ASSIGN_OBJ_OP: + next = opline + 1; + if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { + var_num = EX_VAR_TO_NUM(next->op1.var); + if (!zend_bitset_in(def, var_num)) { + zend_bitset_incl(use, var_num); + } + } + if (opline->op1_type == IS_CV) { + goto add_op1_def; + } + break; + case ZEND_ASSIGN_OP: + case ZEND_PRE_INC: + case ZEND_PRE_DEC: + case ZEND_POST_INC: + case ZEND_POST_DEC: + case ZEND_BIND_GLOBAL: + case ZEND_BIND_STATIC: + case ZEND_SEND_VAR_NO_REF: + case ZEND_SEND_VAR_NO_REF_EX: + case ZEND_SEND_VAR_EX: + case ZEND_SEND_FUNC_ARG: + case ZEND_SEND_REF: + case ZEND_SEND_UNPACK: + case ZEND_FE_RESET_RW: + case ZEND_MAKE_REF: + case ZEND_PRE_INC_OBJ: + case ZEND_PRE_DEC_OBJ: + case ZEND_POST_INC_OBJ: + case ZEND_POST_DEC_OBJ: + case ZEND_UNSET_DIM: + case ZEND_UNSET_OBJ: + case ZEND_FETCH_DIM_W: + case ZEND_FETCH_DIM_RW: + case ZEND_FETCH_DIM_FUNC_ARG: + case ZEND_FETCH_DIM_UNSET: + case ZEND_FETCH_LIST_W: + if (opline->op1_type == IS_CV) { + goto add_op1_def; + } + break; + case ZEND_SEND_VAR: + case ZEND_CAST: + case ZEND_QM_ASSIGN: + case ZEND_JMP_SET: + case ZEND_COALESCE: + case ZEND_FE_RESET_R: + if ((build_flags & ZEND_SSA_RC_INFERENCE) && opline->op1_type == IS_CV) { + goto add_op1_def; + } + break; + case ZEND_ADD_ARRAY_UNPACK: + var_num = EX_VAR_TO_NUM(opline->result.var); + if (!zend_bitset_in(def, var_num)) { + zend_bitset_incl(use, var_num); + } + break; + case ZEND_ADD_ARRAY_ELEMENT: + var_num = EX_VAR_TO_NUM(opline->result.var); + if (!zend_bitset_in(def, var_num)) { + zend_bitset_incl(use, var_num); + } + /* break missing intentionally */ + case ZEND_INIT_ARRAY: + if (((build_flags & ZEND_SSA_RC_INFERENCE) + || (opline->extended_value & ZEND_ARRAY_ELEMENT_REF)) + && opline->op1_type == IS_CV) { + goto add_op1_def; + } + break; + case ZEND_YIELD: + if (opline->op1_type == IS_CV + && ((op_array->fn_flags & ZEND_ACC_RETURN_REFERENCE) + || (build_flags & ZEND_SSA_RC_INFERENCE))) { + goto add_op1_def; + } + break; + case ZEND_UNSET_CV: + goto add_op1_def; + case ZEND_VERIFY_RETURN_TYPE: + if (opline->op1_type & (IS_TMP_VAR|IS_VAR|IS_CV)) { + goto add_op1_def; + } + break; + case ZEND_FE_FETCH_R: + case ZEND_FE_FETCH_RW: +#if 0 + /* This special case was handled above the switch */ + if (opline->op2_type != IS_CV) { + op2_use = -1; /* not used */ + } +#endif + zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op2.var)); + break; + case ZEND_BIND_LEXICAL: + if ((opline->extended_value & ZEND_BIND_REF) || (build_flags & ZEND_SSA_RC_INFERENCE)) { + zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op2.var)); + } + break; + default: + break; + } + + if (opline->result_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { + zend_bitset_incl(def, EX_VAR_TO_NUM(opline->result.var)); + } +} +/* }}} */ + +ZEND_API void zend_dfg_add_use_def_op(const zend_op_array *op_array, const zend_op *opline, uint32_t build_flags, zend_bitset use, zend_bitset def) /* {{{ */ +{ + _zend_dfg_add_use_def_op(op_array, opline, build_flags, use, def); +} +/* }}} */ + +int zend_build_dfg(const zend_op_array *op_array, const zend_cfg *cfg, zend_dfg *dfg, uint32_t build_flags) /* {{{ */ +{ + int set_size; + zend_basic_block *blocks = cfg->blocks; + int blocks_count = cfg->blocks_count; + zend_bitset tmp, def, use, in, out; + int k; + int j; + + set_size = dfg->size; + tmp = dfg->tmp; + def = dfg->def; + use = dfg->use; + in = dfg->in; + out = dfg->out; + + /* Collect "def" and "use" sets */ + for (j = 0; j < blocks_count; j++) { + zend_op *opline, *end; + zend_bitset b_use, b_def; + + if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) { + continue; + } + + opline = op_array->opcodes + blocks[j].start; + end = opline + blocks[j].len; + b_use = DFG_BITSET(use, set_size, j); + b_def = DFG_BITSET(def, set_size, j); + for (; opline < end; opline++) { + if (opline->opcode != ZEND_OP_DATA) { + _zend_dfg_add_use_def_op(op_array, opline, build_flags, b_use, b_def); + } + } + } + + /* Calculate "in" and "out" sets */ + { + uint32_t worklist_len = zend_bitset_len(blocks_count); + zend_bitset worklist; + ALLOCA_FLAG(use_heap); + worklist = ZEND_BITSET_ALLOCA(worklist_len, use_heap); + memset(worklist, 0, worklist_len * ZEND_BITSET_ELM_SIZE); + for (j = 0; j < blocks_count; j++) { + zend_bitset_incl(worklist, j); + } + while (!zend_bitset_empty(worklist, worklist_len)) { + /* We use the last block on the worklist, because predecessors tend to be located + * before the succeeding block, so this converges faster. */ + j = zend_bitset_last(worklist, worklist_len); + zend_bitset_excl(worklist, j); + + if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) { + continue; + } + if (blocks[j].successors_count != 0) { + zend_bitset_copy(DFG_BITSET(out, set_size, j), DFG_BITSET(in, set_size, blocks[j].successors[0]), set_size); + for (k = 1; k < blocks[j].successors_count; k++) { + zend_bitset_union(DFG_BITSET(out, set_size, j), DFG_BITSET(in, set_size, blocks[j].successors[k]), set_size); + } + } else { + zend_bitset_clear(DFG_BITSET(out, set_size, j), set_size); + } + zend_bitset_union_with_difference(tmp, DFG_BITSET(use, set_size, j), DFG_BITSET(out, set_size, j), DFG_BITSET(def, set_size, j), set_size); + if (!zend_bitset_equal(DFG_BITSET(in, set_size, j), tmp, set_size)) { + zend_bitset_copy(DFG_BITSET(in, set_size, j), tmp, set_size); + + /* Add predecessors of changed block to worklist */ + { + int *predecessors = &cfg->predecessors[blocks[j].predecessor_offset]; + for (k = 0; k < blocks[j].predecessors_count; k++) { + zend_bitset_incl(worklist, predecessors[k]); + } + } + } + } + + free_alloca(worklist, use_heap); + } + + return SUCCESS; +} +/* }}} */ |