com php-src: Initial implementation of Escape Analysis (disabled yet).: ext/opcache/Optimizer/dfa_pass.c ext/opcache/Optimizer/es cape_analysis.c
ext/opcache/Optimizer/zend_dump.c e xt/opcache/Optimizer/zend_optimizer_internal.h ext/opca che/Optimizer/zend_ssa.h ext/opcache/config.m4 ext/
opcache/config.w32

From: Date: Tue, 22 Aug 2017 13:55:03 +0000
Subject: com php-src: Initial implementation of Escape Analysis (disabled yet).: ext/opcache/Optimizer/dfa_pass.c ext/opcache/Optimizer/es cape_analysis.c
ext/opcache/Optimizer/zend_dump.c e xt/opcache/Optimizer/zend_optimizer_internal.h ext/opca che/Optimizer/zend_ssa.h ext/opcache/config.m4 ext/
opcache/config.w32
Groups: php.cvs 
Request: Send a blank email to php-cvs+get-99129@lists.php.net to get a copy of this message
Commit: 3cb6407e8647d3193d89d2f9dbf27836aa15a856 Author: Dmitry Stogov <dmitry@zend.com> Tue, 22 Aug 2017 16:55:03 +0300 Parents: 1fdfcc2bb0d18cc1a2ae3ab8bd985165bbef504d Branches: master Link: http://git.php.net/?p=php-src.git;a=commitdiff;h=3cb6407e8647d3193d89d2f9dbf27836aa15a856 Log: Initial implementation of Escape Analysis (disabled yet). Changed paths: M ext/opcache/Optimizer/dfa_pass.c A ext/opcache/Optimizer/escape_analysis.c M ext/opcache/Optimizer/zend_dump.c M ext/opcache/Optimizer/zend_optimizer_internal.h M ext/opcache/Optimizer/zend_ssa.h M ext/opcache/config.m4 M ext/opcache/config.w32

diff --git a/ext/opcache/Optimizer/dfa_pass.c b/ext/opcache/Optimizer/dfa_pass.c index 9dbd4d1..e7619f2 100644 --- a/ext/opcache/Optimizer/dfa_pass.c +++ b/ext/opcache/Optimizer/dfa_pass.c @@ -39,6 +39,10 @@ # include "ssa_integrity.c" #endif +#ifndef HAVE_ESCAPE_ANALYSIS +# define HAVE_ESCAPE_ANALYSIS 0 +#endif + int zend_dfa_analyze_op_array(zend_op_array *op_array, zend_optimizer_ctx *ctx, zend_ssa *ssa, uint32_t *flags) { uint32_t build_flags; @@ -107,6 +111,12 @@ int zend_dfa_analyze_op_array(zend_op_array *op_array, zend_optimizer_ctx *ctx, return FAILURE; } +#if HAVE_ESCAPE_ANALYSIS + if (zend_ssa_escape_analysis(op_array, ssa) != SUCCESS) { + return FAILURE; + } +#endif + if (zend_ssa_find_sccs(op_array, ssa) != SUCCESS){ return FAILURE; } diff --git a/ext/opcache/Optimizer/escape_analysis.c b/ext/opcache/Optimizer/escape_analysis.c new file mode 100644 index 0000000..0d316b3 --- /dev/null +++ b/ext/opcache/Optimizer/escape_analysis.c @@ -0,0 +1,461 @@ +/* + +----------------------------------------------------------------------+ + | Zend OPcache, Escape Analysis | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2017 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@zend.com> | + +----------------------------------------------------------------------+ +*/ + +#include "php.h" +#include "Optimizer/zend_optimizer.h" +#include "Optimizer/zend_optimizer_internal.h" +#include "zend_bitset.h" +#include "zend_cfg.h" +#include "zend_ssa.h" +#include "zend_dump.h" + +/* + * T. Kotzmann and H. Mossenbock. Escape analysis in the context of dynamic + * compilation and deoptimization. In Proceedings of the International + * Conference on Virtual Execution Environments, pages 111-120, Chicago, + * June 2005 + */ + +static zend_always_inline void union_find_init(int *parent, int *size, int count) /* {{{ */ +{ + int i; + + for (i = 0; i < count; i++) { + parent[i] = i; + size[i] = 1; + } +} +/* }}} */ + +static zend_always_inline int union_find_root(int *parent, int i) /* {{{ */ +{ + int p = parent[i]; + + while (i != p) { + p = parent[p]; + parent[i] = p; + i = p; + p = parent[i]; + } + return i; +} +/* }}} */ + +static zend_always_inline void union_find_unite(int *parent, int *size, int i, int j) /* {{{ */ +{ + int r1 = union_find_root(parent, i); + int r2 = union_find_root(parent, j); + + if (r1 != r2) { + if (size[r1] < size[r2]) { + parent[r1] = r2; + size[r2] += size[r1]; + } else { + parent[r2] = r1; + size[r1] += size[r2]; + } + } +} +/* }}} */ + +static int zend_build_equi_escape_sets(int *parent, zend_op_array *op_array, zend_ssa *ssa) /* {{{ */ +{ + zend_ssa_var *ssa_vars = ssa->vars; + int ssa_vars_count = ssa->vars_count; + zend_ssa_phi *p; + int i, j; + int *size; + ALLOCA_FLAG(use_heap) + + size = do_alloca(sizeof(int) * ssa_vars_count, use_heap); + if (!size) { + return FAILURE; + } + union_find_init(parent, size, ssa_vars_count); + + for (i = 0; i < ssa_vars_count; i++) { + if (ssa_vars[i].no_val) { + /* skip */ + } else if (ssa_vars[i].definition_phi) { + p = ssa_vars[i].definition_phi; + if (p->pi >= 0) { + union_find_unite(parent, size, i, p->sources[0]); + } else { + for (j = 0; j < ssa->cfg.blocks[p->block].predecessors_count; j++) { + union_find_unite(parent, size, i, p->sources[j]); + } + } + } else if (ssa_vars[i].definition >= 0) { + int def = ssa_vars[i].definition; + zend_ssa_op *op = ssa->ops + def; + zend_op *opline = op_array->opcodes + def; + + if (op->op1_def >= 0) { + if (op->op1_use >= 0) { + if (opline->opcode != ZEND_ASSIGN) { + union_find_unite(parent, size, op->op1_def, op->op1_use); + } + } + if (opline->opcode == ZEND_ASSIGN && op->op2_use >= 0) { + union_find_unite(parent, size, op->op1_def, op->op2_use); + } + } + if (op->op2_def >= 0) { + if (op->op2_use >= 0) { + union_find_unite(parent, size, op->op2_def, op->op2_use); + } + } + if (op->result_def >= 0) { + if (op->result_use >= 0) { + if (opline->opcode != ZEND_QM_ASSIGN) { + union_find_unite(parent, size, op->result_def, op->result_use); + } + } + if (opline->opcode == ZEND_QM_ASSIGN && op->op1_use >= 0) { + union_find_unite(parent, size, op->result_def, op->op1_use); + } + if (opline->opcode == ZEND_ASSIGN && op->op2_use >= 0) { + union_find_unite(parent, size, op->result_def, op->op2_use); + } + if (opline->opcode == ZEND_ASSIGN && op->op1_def >= 0) { + union_find_unite(parent, size, op->result_def, op->op1_def); + } + } + } + } + + for (i = 0; i < ssa_vars_count; i++) { + parent[i] = union_find_root(parent, i); + } + + free_alloca(size, use_heap); + + return SUCCESS; +} +/* }}} */ + +static inline zend_class_entry *get_class_entry(const zend_script *script, zend_string *lcname) /* {{{ */ +{ + zend_class_entry *ce = script ? zend_hash_find_ptr(&script->class_table, lcname) : NULL; + if (ce) { + return ce; + } + + ce = zend_hash_find_ptr(CG(class_table), lcname); + if (ce && ce->type == ZEND_INTERNAL_CLASS) { + return ce; + } + + return NULL; +} +/* }}} */ + +static int is_allocation_def(zend_op_array *op_array, zend_ssa *ssa, int def, int var) /* {{{ */ +{ + zend_ssa_op *op = ssa->ops + def; + zend_op *opline = op_array->opcodes + def; + + if (op->result_def == var) { + switch (opline->opcode) { + case ZEND_INIT_ARRAY: + return 1; + case ZEND_NEW: + /* objects with destructors should escape */ + if (opline->op1_type == IS_CONST) { + zend_class_entry *ce = get_class_entry(NULL, Z_STR_P(CRT_CONSTANT_EX(op_array, opline->op1, ssa->rt_constants)+1)); + if (ce && !ce->create_object && + !ce->destructor && !ce->__get && !ce->__set) { + return 1; + } + } + break; + case ZEND_QM_ASSIGN: + if (opline->op1_type == IS_CONST + && Z_TYPE_P(CRT_CONSTANT_EX(op_array, opline->op1, ssa->rt_constants)) == IS_ARRAY) { + return 1; + } + break; + } + } else if (op->op1_def == var) { + switch (opline->opcode) { + case ZEND_ASSIGN: + if (opline->op2_type == IS_CONST + && Z_TYPE_P(CRT_CONSTANT_EX(op_array, opline->op2, ssa->rt_constants)) == IS_ARRAY) { + return 1; + } + break; +#if 0 + // TODO: implicit object/array allocation + case ZEND_ASSIGN_DIM: + case ZEND_ASSIGN_OBJ: + return 1; + case ZEND_ASSIGN_ADD: + case ZEND_ASSIGN_SUB: + case ZEND_ASSIGN_MUL: + case ZEND_ASSIGN_DIV: + case ZEND_ASSIGN_MOD: + case ZEND_ASSIGN_SL: + case ZEND_ASSIGN_SR: + case ZEND_ASSIGN_CONCAT: + case ZEND_ASSIGN_BW_OR: + case ZEND_ASSIGN_BW_AND: + case ZEND_ASSIGN_BW_XOR: + case ZEND_ASSIGN_POW: + if (opline->extended_value) { + return 1; + } + break; +#endif + } + } + + return 0; +} +/* }}} */ + +static int is_escape_use(zend_op_array *op_array, zend_ssa *ssa, int use, int var) /* {{{ */ +{ + zend_ssa_op *op = ssa->ops + use; + zend_op *opline = op_array->opcodes + use; + + if (op->op1_use == var) { + switch (opline->opcode) { + case ZEND_ASSIGN: + /* no_val */ + break; + case ZEND_QM_ASSIGN: +#if 0 + if (opline->op1_type == IS_CV) { + /* array duplication */ + return 1; + } +#endif + break; + case ZEND_FETCH_DIM_R: + case ZEND_FETCH_OBJ_R: +// case ZEND_FETCH_DIM_W: +// case ZEND_FETCH_OBJ_W: + case ZEND_FETCH_DIM_RW: + case ZEND_FETCH_OBJ_RW: + case ZEND_FETCH_DIM_IS: + case ZEND_FETCH_OBJ_IS: +// case ZEND_FETCH_DIM_FUNC_ARG: +// case ZEND_FETCH_OBJ_FUNC_ARG: +// case ZEND_FETCH_DIM_UNSET: +// case ZEND_FETCH_OBJ_UNSET: + break; + case ZEND_ASSIGN_ADD: + case ZEND_ASSIGN_SUB: + case ZEND_ASSIGN_MUL: + case ZEND_ASSIGN_DIV: + case ZEND_ASSIGN_MOD: + case ZEND_ASSIGN_SL: + case ZEND_ASSIGN_SR: + case ZEND_ASSIGN_CONCAT: + case ZEND_ASSIGN_BW_OR: + case ZEND_ASSIGN_BW_AND: + case ZEND_ASSIGN_BW_XOR: + case ZEND_ASSIGN_POW: + if (!opline->extended_value) { + return 1; + } + /* break missing intentionally */ + case ZEND_ASSIGN_DIM: + case ZEND_ASSIGN_OBJ: + break; + default: + return 1; + } + } + + if (op->op2_use == var) { + switch (opline->opcode) { + case ZEND_ASSIGN_DIM: + case ZEND_ASSIGN_OBJ: + /* reference dependencies processed separately */ + break; + case ZEND_ASSIGN: +#if 0 + if (opline->op2_type == IS_CV) { + /* array duplication */ + return 1; + } +#endif + break; + default: + return 1; + } + } + + if (op->result_use == var) { + switch (opline->opcode) { + case ZEND_ASSIGN: + case ZEND_QM_ASSIGN: + case ZEND_INIT_ARRAY: + case ZEND_ADD_ARRAY_ELEMENT: + break; + default: + return 1; + } + } + + return 0; +} +/* }}} */ + +int zend_ssa_escape_analysis(zend_op_array *op_array, zend_ssa *ssa) /* {{{ */ +{ + zend_ssa_var *ssa_vars = ssa->vars; + int ssa_vars_count = ssa->vars_count; + int i, root, use; + int *ees; + zend_bool has_allocations; + int num_non_escaped; + ALLOCA_FLAG(use_heap) + + if (!ssa->vars) { + return SUCCESS; + } + + has_allocations = 0; + for (i = 0; i < ssa_vars_count; i++) { + if (ssa_vars[i].definition >= 0) { + if (is_allocation_def(op_array, ssa, ssa_vars[i].definition, i)) { + has_allocations = 1; + } + } + } + if (!has_allocations) { + return SUCCESS; + } + + + /* 1. Build EES (Equi-Esape Sets) */ + ees = do_alloca(sizeof(int) * ssa->vars_count, use_heap); + if (!ees) { + return FAILURE; + } + + if (zend_build_equi_escape_sets(ees, op_array, ssa) != SUCCESS) { + return FAILURE; + } + + /* 2. Identify Allocations */ + num_non_escaped = 0; + for (i = 0; i < ssa_vars_count; i++) { + if (ssa_vars[i].definition >= 0) { + root = ees[i]; + if (ssa_vars[root].escape_state == ESCAPE_STATE_UNKNOWN) { + if (is_allocation_def(op_array, ssa, ssa_vars[i].definition, i)) { + ssa_vars[root].escape_state = ESCAPE_STATE_NO_ESCAPE; + num_non_escaped++; + } else { + ssa_vars[root].escape_state = ESCAPE_STATE_GLOBAL_ESCAPE; + } + } + } + } + + /* 3. Mark escaped EES */ + if (num_non_escaped) { + for (i = 0; i < ssa_vars_count; i++) { + if (ssa_vars[i].use_chain >= 0) { + root = ees[i]; + if (ssa_vars[root].escape_state == ESCAPE_STATE_NO_ESCAPE) { + FOREACH_USE(ssa->vars + i, use) { + if (is_escape_use(op_array, ssa, use, i)) { + ssa_vars[root].escape_state = ESCAPE_STATE_GLOBAL_ESCAPE; + num_non_escaped--; + if (num_non_escaped == 0) { + i = ssa_vars_count; + } + break; + } + } FOREACH_USE_END(); + } + } + } + } + + /* 4. Process referential dependencies */ + if (num_non_escaped) { + zend_bool changed; + + do { + changed = 0; + for (i = 0; i < ssa_vars_count; i++) { + if (ssa_vars[i].use_chain >= 0) { + root = ees[i]; + if (ssa_vars[root].escape_state == ESCAPE_STATE_NO_ESCAPE) { + FOREACH_USE(ssa->vars + i, use) { + zend_ssa_op *op = ssa->ops + use; + zend_op *opline = op_array->opcodes + use; + + if ((opline->opcode == ZEND_ASSIGN_DIM || + opline->opcode == ZEND_ASSIGN_OBJ) && + op->op2_use == i && + op->op1_use >= 0) { + int root2 = ees[op->op1_use]; + + if (ssa_vars[root2].escape_state == ESCAPE_STATE_UNKNOWN || + ssa_vars[root2].escape_state > ssa_vars[root].escape_state) { + if (ssa_vars[root2].escape_state == ESCAPE_STATE_UNKNOWN) { + ssa_vars[root].escape_state = ESCAPE_STATE_GLOBAL_ESCAPE; + } else { + ssa_vars[root].escape_state = ssa_vars[root2].escape_state; + } + if (ssa_vars[root].escape_state == ESCAPE_STATE_GLOBAL_ESCAPE) { + num_non_escaped--; + if (num_non_escaped == 0) { + i = ssa_vars_count; + changed = 0; + } + break; + } else { + changed = 1; + } + } + } + } FOREACH_USE_END(); + } + } + } + } while (changed); + } + + /* 5. Propagate values of escape sets to variables */ + for (i = 0; i < ssa_vars_count; i++) { + root = ees[i]; + if (i != root) { + ssa_vars[i].escape_state = ssa_vars[root].escape_state; + } + } + + free_alloca(ees, use_heap); + + return SUCCESS; +} +/* }}} */ + +/* + * Local variables: + * tab-width: 4 + * c-basic-offset: 4 + * indent-tabs-mode: t + * End: + */ diff --git a/ext/opcache/Optimizer/zend_dump.c b/ext/opcache/Optimizer/zend_dump.c index 364c7b1..54270be 100644 --- a/ext/opcache/Optimizer/zend_dump.c +++ b/ext/opcache/Optimizer/zend_dump.c @@ -320,9 +320,12 @@ static void zend_dump_ssa_var(const zend_op_array *op_array, const zend_ssa *ssa zend_dump_var(op_array, (var_num < op_array->last_var ? IS_CV : var_type), var_num); if (ssa_var_num >= 0 && ssa->vars) { - if (ssa_var_num >= 0 && ssa->vars[ssa_var_num].no_val) { + if (ssa->vars[ssa_var_num].no_val) { fprintf(stderr, " NOVAL"); } + if (ssa->vars[ssa_var_num].escape_state == ESCAPE_STATE_NO_ESCAPE) { + fprintf(stderr, " NOESC"); + } if (ssa->var_info) { zend_dump_ssa_var_info(ssa, ssa_var_num, dump_flags); if (ssa->var_info[ssa_var_num].has_range) { diff --git a/ext/opcache/Optimizer/zend_optimizer_internal.h b/ext/opcache/Optimizer/zend_optimizer_internal.h index aa37456..657be9b 100644 --- a/ext/opcache/Optimizer/zend_optimizer_internal.h +++ b/ext/opcache/Optimizer/zend_optimizer_internal.h @@ -114,5 +114,6 @@ void zend_optimizer_shift_jump(zend_op_array *op_array, zend_op *opline, uint32_ zend_uchar zend_compound_assign_to_binary_op(zend_uchar opcode); int sccp_optimize_op_array(zend_optimizer_ctx *ctx, zend_op_array *op_arrya, zend_ssa *ssa, zend_call_info **call_map); int dce_optimize_op_array(zend_op_array *op_array, zend_ssa *ssa, zend_bool reorder_dtor_effects); +int zend_ssa_escape_analysis(zend_op_array *op_array, zend_ssa *ssa); #endif diff --git a/ext/opcache/Optimizer/zend_ssa.h b/ext/opcache/Optimizer/zend_ssa.h index f5855f2..7a73d22 100644 --- a/ext/opcache/Optimizer/zend_ssa.h +++ b/ext/opcache/Optimizer/zend_ssa.h @@ -99,6 +99,13 @@ typedef enum _zend_ssa_alias_kind { HTTP_RESPONSE_HEADER_ALIAS } zend_ssa_alias_kind; +typedef enum _zend_ssa_escape_state { + ESCAPE_STATE_UNKNOWN, + ESCAPE_STATE_NO_ESCAPE, + ESCAPE_STATE_FUNCTION_ESCAPE, + ESCAPE_STATE_GLOBAL_ESCAPE +} zend_ssa_escape_state; + typedef struct _zend_ssa_var { int var; /* original var number; op.var for CVs and following numbers for VARs and TMP_VARs */ int scc; /* strongly connected component */ @@ -110,6 +117,7 @@ typedef struct _zend_ssa_var { unsigned int no_val : 1; /* value doesn't mater (used as op1 in ZEND_ASSIGN) */ unsigned int scc_entry : 1; zend_ssa_alias_kind alias : 2; /* value may be changed indirectly */ + zend_ssa_escape_state escape_state : 2; } zend_ssa_var; typedef struct _zend_ssa_var_info { diff --git a/ext/opcache/config.m4 b/ext/opcache/config.m4 index 7b500f0..8098f3d 100644 --- a/ext/opcache/config.m4 +++ b/ext/opcache/config.m4 @@ -413,6 +413,7 @@ fi Optimizer/sccp.c \ Optimizer/scdf.c \ Optimizer/dce.c \ + Optimizer/escape_analysis.c \ Optimizer/compact_vars.c \ Optimizer/zend_dump.c, shared,,-DZEND_ENABLE_STATIC_TSRMLS_CACHE=1,,yes) diff --git a/ext/opcache/config.w32 b/ext/opcache/config.w32 index c2b757d..3c293c7 100644 --- a/ext/opcache/config.w32 +++ b/ext/opcache/config.w32 @@ -23,7 +23,7 @@ if (PHP_OPCACHE != "no") { zend_shared_alloc.c \ shared_alloc_win32.c", true, "/DZEND_ENABLE_STATIC_TSRMLS_CACHE=1"); - ADD_SOURCES(configure_module_dirname + "/Optimizer", "zend_optimizer.c pass1_5.c pass2.c pass3.c optimize_func_calls.c block_pass.c optimize_temp_vars_5.c nop_removal.c compact_literals.c zend_cfg.c zend_dfg.c dfa_pass.c zend_ssa.c zend_inference.c zend_func_info.c zend_call_graph.c sccp.c scdf.c dce.c compact_vars.c zend_dump.c", "opcache", "OptimizerObj"); + ADD_SOURCES(configure_module_dirname + "/Optimizer", "zend_optimizer.c pass1_5.c pass2.c pass3.c optimize_func_calls.c block_pass.c optimize_temp_vars_5.c nop_removal.c compact_literals.c zend_cfg.c zend_dfg.c dfa_pass.c zend_ssa.c zend_inference.c zend_func_info.c zend_call_graph.c sccp.c scdf.c dce.c escape_analysis.c compact_vars.c zend_dump.c", "opcache", "OptimizerObj"); ADD_FLAG('CFLAGS_OPCACHE', "/I " + configure_module_dirname);
« previous php.cvs (#99129) next »