From f243aaf9856fcbfdb08a59ff08f22cf48647cfc0 Mon Sep 17 00:00:00 2001 From: Dmitry Stogov Date: Fri, 11 Dec 2015 17:24:55 +0300 Subject: [PATCH] Added e-SSA based DFA optimisation framework (incomplete) --- ext/opcache/Optimizer/block_pass.c | 2 +- ext/opcache/Optimizer/dfa_pass.c | 117 +++ ext/opcache/Optimizer/zend_cfg.c | 219 ++++- ext/opcache/Optimizer/zend_cfg.h | 17 +- ext/opcache/Optimizer/zend_dfg.c | 248 +++++ ext/opcache/Optimizer/zend_dfg.h | 59 ++ ext/opcache/Optimizer/zend_dump.c | 156 ++-- ext/opcache/Optimizer/zend_dump.h | 1 + ext/opcache/Optimizer/zend_optimizer.c | 10 + ext/opcache/Optimizer/zend_optimizer.h | 7 +- .../Optimizer/zend_optimizer_internal.h | 1 + ext/opcache/Optimizer/zend_ssa.c | 879 ++++++++++++++++++ ext/opcache/Optimizer/zend_ssa.h | 116 +++ ext/opcache/Optimizer/zend_worklist.h | 129 +++ ext/opcache/config.m4 | 3 + ext/opcache/config.w32 | 2 +- 16 files changed, 1885 insertions(+), 81 deletions(-) create mode 100644 ext/opcache/Optimizer/dfa_pass.c create mode 100644 ext/opcache/Optimizer/zend_dfg.c create mode 100644 ext/opcache/Optimizer/zend_dfg.h create mode 100644 ext/opcache/Optimizer/zend_ssa.c create mode 100644 ext/opcache/Optimizer/zend_ssa.h create mode 100644 ext/opcache/Optimizer/zend_worklist.h diff --git a/ext/opcache/Optimizer/block_pass.c b/ext/opcache/Optimizer/block_pass.c index a61ca9c0a3..b240254ab9 100644 --- a/ext/opcache/Optimizer/block_pass.c +++ b/ext/opcache/Optimizer/block_pass.c @@ -1794,7 +1794,7 @@ void optimize_cfg(zend_op_array *op_array, zend_optimizer_ctx *ctx) } /* Eliminate unreachable basic blocks */ - zend_remark_reachable_blocks(op_array, &cfg); + zend_cfg_remark_reachable_blocks(op_array, &cfg); /* Merge Blocks */ zend_merge_blocks(op_array, &cfg); diff --git a/ext/opcache/Optimizer/dfa_pass.c b/ext/opcache/Optimizer/dfa_pass.c new file mode 100644 index 0000000000..9297659083 --- /dev/null +++ b/ext/opcache/Optimizer/dfa_pass.c @@ -0,0 +1,117 @@ +/* + +----------------------------------------------------------------------+ + | Zend OPcache | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2015 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 | + +----------------------------------------------------------------------+ +*/ + +#include "php.h" +#include "Optimizer/zend_optimizer.h" +#include "Optimizer/zend_optimizer_internal.h" +#include "zend_API.h" +#include "zend_constants.h" +#include "zend_execute.h" +#include "zend_vm.h" +#include "zend_bitset.h" +#include "zend_cfg.h" +#include "zend_ssa.h" +#include "zend_dump.h" + +#ifndef HAVE_DFA_PASS +# define HAVE_DFA_PASS 0 +#endif + +void optimize_dfa(zend_op_array *op_array, zend_optimizer_ctx *ctx) +{ + void *checkpoint; + uint32_t flags; + zend_cfg cfg; + zend_ssa ssa; + +#if !HAVE_DFA_PASS + return; +#endif + + /* Build SSA */ + checkpoint = zend_arena_checkpoint(ctx->arena); + + if (zend_build_cfg(&ctx->arena, op_array, 0, 0, &cfg, &flags) != SUCCESS) { + zend_arena_release(&ctx->arena, checkpoint); + return; + } + + if (flags & ZEND_FUNC_TOO_DYNAMIC) { + zend_arena_release(&ctx->arena, checkpoint); + return; + } + + if (zend_cfg_build_predecessors(&ctx->arena, &cfg) != SUCCESS) { + zend_arena_release(&ctx->arena, checkpoint); + return; + } + + if (ctx->debug_level & ZEND_DUMP_DFA_CFG) { + zend_dump_op_array(op_array, &cfg, 0, "dfa cfg"); + } + + /* Compute Dominators Tree */ + if (zend_cfg_compute_dominators_tree(op_array, &cfg) != SUCCESS) { + zend_arena_release(&ctx->arena, checkpoint); + return; + } + + /* Identify reducible and irreducible loops */ + if (zend_cfg_identify_loops(op_array, &cfg, &flags) != SUCCESS) { + zend_arena_release(&ctx->arena, checkpoint); + return; + } + + if (ctx->debug_level & ZEND_DUMP_DFA_DOMINATORS) { + int j; + + fprintf(stderr, "DOMINATORS-TREE:\n"); + for (j = 0; j < cfg.blocks_count; j++) { + zend_basic_block *b = cfg.blocks + j; + if (b->flags & ZEND_BB_REACHABLE) { + zend_dump_block_info(&cfg, j, 0); + } + } + } + + if (zend_build_ssa(&ctx->arena, op_array, &cfg, 0, &ssa, &flags) != SUCCESS) { + zend_arena_release(&ctx->arena, checkpoint); + return; + } + + if (ctx->debug_level & ZEND_DUMP_BEFORE_DFA_PASS) { + zend_dump_op_array(op_array, &cfg, ZEND_DUMP_UNREACHABLE, "before dfa pass"); + } + + //TODO: ??? + + if (ctx->debug_level & ZEND_DUMP_AFTER_DFA_PASS) { + zend_dump_op_array(op_array, &cfg, 0, "after dfa pass"); + } + + /* Destroy SSA */ + zend_arena_release(&ctx->arena, checkpoint); +} + +/* + * Local variables: + * tab-width: 4 + * c-basic-offset: 4 + * indent-tabs-mode: t + * End: + */ diff --git a/ext/opcache/Optimizer/zend_cfg.c b/ext/opcache/Optimizer/zend_cfg.c index 77e5dc1942..8fc31ec77b 100644 --- a/ext/opcache/Optimizer/zend_cfg.c +++ b/ext/opcache/Optimizer/zend_cfg.c @@ -19,8 +19,9 @@ #include "php.h" #include "zend_compile.h" #include "zend_cfg.h" +#include "zend_worklist.h" -static void zend_mark_reachable(zend_op *opcodes, zend_basic_block *blocks, zend_basic_block *b) +static void zend_mark_reachable(zend_op *opcodes, zend_basic_block *blocks, zend_basic_block *b) /* {{{ */ { zend_uchar opcode; zend_basic_block *b0; @@ -72,8 +73,9 @@ static void zend_mark_reachable(zend_op *opcodes, zend_basic_block *blocks, zend } } } +/* }}} */ -static void zend_mark_reachable_blocks(zend_op_array *op_array, zend_cfg *cfg, int start) +static void zend_mark_reachable_blocks(zend_op_array *op_array, zend_cfg *cfg, int start) /* {{{ */ { zend_basic_block *blocks = cfg->blocks; @@ -195,8 +197,9 @@ static void zend_mark_reachable_blocks(zend_op_array *op_array, zend_cfg *cfg, i } while (changed); } } +/* }}} */ -void zend_remark_reachable_blocks(zend_op_array *op_array, zend_cfg *cfg) +void zend_cfg_remark_reachable_blocks(zend_op_array *op_array, zend_cfg *cfg) /* {{{ */ { zend_basic_block *blocks = cfg->blocks; int i; @@ -217,6 +220,7 @@ void zend_remark_reachable_blocks(zend_op_array *op_array, zend_cfg *cfg) zend_mark_reachable_blocks(op_array, cfg, start); } +/* }}} */ static void record_successor(zend_basic_block *blocks, int pred, int n, int succ) { @@ -282,11 +286,7 @@ int zend_build_cfg(zend_arena **arena, zend_op_array *op_array, int rt_constants flags |= ZEND_FUNC_HAS_CALLS; break; case ZEND_INIT_FCALL: - if (rt_constants) { - zv = RT_CONSTANT(op_array, opline->op2); - } else { - zv = CT_CONSTANT_EX(op_array, opline->op2.constant); - } + zv = CRT_CONSTANT(opline->op2); if ((fn = zend_hash_find_ptr(EG(function_table), Z_STR_P(zv))) != NULL) { if (fn->type == ZEND_INTERNAL_FUNCTION) { if (Z_STRLEN_P(zv) == sizeof("extract")-1 && @@ -377,11 +377,7 @@ int zend_build_cfg(zend_arena **arena, zend_op_array *op_array, int rt_constants case ZEND_DECLARE_LAMBDA_FUNCTION: { //??? zend_op_array *lambda_op_array; //??? -//??? if (rt_constants) { -//??? zv = RT_CONSTANT(op_array, opline->op1); -//??? } else { -//??? zv = CT_CONSTANT_EX(op_array, opline->op1.constant); -//??? } +//??? zv = CRT_CONSTANT(opline->op1); //??? if (ctx->main_script && //??? (lambda_op_array = zend_hash_find_ptr(&ctx->main_script->function_table, Z_STR_P(zv))) != NULL) { //??? if (lambda_op_array->type == ZEND_USER_FUNCTION && @@ -606,6 +602,203 @@ int zend_cfg_build_predecessors(zend_arena **arena, zend_cfg *cfg) /* {{{ */ } /* }}} */ +int zend_cfg_compute_dominators_tree(zend_op_array *op_array, zend_cfg *cfg) /* {{{ */ +{ + zend_basic_block *blocks = cfg->blocks; + int blocks_count = cfg->blocks_count; + int j, k, changed; + + /* FIXME: move declarations */ + blocks[0].idom = 0; + do { + changed = 0; + for (j = 1; j < blocks_count; j++) { + int idom = -1; + + if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) { + continue; + } + for (k = 0; k < blocks[j].predecessors_count; k++) { + int pred = cfg->predecessors[blocks[j].predecessor_offset + k]; + + if (idom < 0) { + if (blocks[pred].idom >= 0) + idom = pred; + continue; + } + + if (blocks[pred].idom >= 0) { + while (idom != pred) { + while (pred > idom) pred = blocks[pred].idom; + while (idom > pred) idom = blocks[idom].idom; + } + } + } + + if (idom >= 0 && blocks[j].idom != idom) { + blocks[j].idom = idom; + changed = 1; + } + } + } while (changed); + blocks[0].idom = -1; + + for (j = 1; j < blocks_count; j++) { + if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) { + continue; + } + if (blocks[j].idom >= 0) { + /* Sort by block number to traverse children in pre-order */ + if (blocks[blocks[j].idom].children < 0 || + j < blocks[blocks[j].idom].children) { + blocks[j].next_child = blocks[blocks[j].idom].children; + blocks[blocks[j].idom].children = j; + } else { + int k = blocks[blocks[j].idom].children; + while (blocks[k].next_child >=0 && j > blocks[k].next_child) { + k = blocks[k].next_child; + } + blocks[j].next_child = blocks[k].next_child; + blocks[k].next_child = j; + } + } + } + + for (j = 0; j < blocks_count; j++) { + int idom = blocks[j].idom, level = 0; + if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) { + continue; + } + while (idom >= 0) { + level++; + if (blocks[idom].level >= 0) { + level += blocks[idom].level; + break; + } else { + idom = blocks[idom].idom; + } + } + blocks[j].level = level; + } + + return SUCCESS; +} +/* }}} */ + +static int dominates(zend_basic_block *blocks, int a, int b) /* {{{ */ +{ + while (blocks[b].level > blocks[a].level) { + b = blocks[b].idom; + } + return a == b; +} +/* }}} */ + +int zend_cfg_identify_loops(zend_op_array *op_array, zend_cfg *cfg, uint32_t *flags) /* {{{ */ +{ + int i, j, k; + int depth; + zend_basic_block *blocks = cfg->blocks; + int *dj_spanning_tree; + zend_worklist work; + int flag = ZEND_FUNC_NO_LOOPS; + + ZEND_WORKLIST_ALLOCA(&work, cfg->blocks_count); + dj_spanning_tree = alloca(sizeof(int) * cfg->blocks_count); + + for (i = 0; i < cfg->blocks_count; i++) { + dj_spanning_tree[i] = -1; + } + zend_worklist_push(&work, 0); + while (zend_worklist_len(&work)) { + next: + i = zend_worklist_peek(&work); + /* Visit blocks immediately dominated by i. */ + for (j = blocks[i].children; j >= 0; j = blocks[j].next_child) { + if (zend_worklist_push(&work, j)) { + dj_spanning_tree[j] = i; + goto next; + } + } + /* Visit join edges. */ + for (j = 0; j < 2; j++) { + int succ = blocks[i].successors[j]; + if (succ < 0) { + continue; + } else if (blocks[succ].idom == i) { + continue; + } else if (zend_worklist_push(&work, succ)) { + dj_spanning_tree[succ] = i; + goto next; + } + } + zend_worklist_pop(&work); + } + + /* Identify loops. See Sreedhar et al, "Identifying Loops Using DJ + Graphs". */ + + for (i = 0, depth = 0; i < cfg->blocks_count; i++) { + if (blocks[i].level > depth) { + depth = blocks[i].level; + } + } + for (; depth >= 0; depth--) { + for (i = 0; i < cfg->blocks_count; i++) { + if (blocks[i].level != depth) { + continue; + } + zend_bitset_clear(work.visited, zend_bitset_len(cfg->blocks_count)); + for (j = 0; j < blocks[i].predecessors_count; j++) { + int pred = cfg->predecessors[blocks[i].predecessor_offset + j]; + + /* A join edge is one for which the predecessor does not + immediately dominate the successor. */ + if (blocks[i].idom == pred) { + continue; + } + + /* In a loop back-edge (back-join edge), the successor dominates + the predecessor. */ + if (dominates(blocks, i, pred)) { + blocks[i].flags |= ZEND_BB_LOOP_HEADER; + flag &= ~ZEND_FUNC_NO_LOOPS; + zend_worklist_push(&work, pred); + } else { + /* Otherwise it's a cross-join edge. See if it's a branch + to an ancestor on the dominator spanning tree. */ + int dj_parent = pred; + while (dj_parent >= 0) { + if (dj_parent == i) { + /* An sp-back edge: mark as irreducible. */ + blocks[i].flags |= ZEND_BB_IRREDUCIBLE_LOOP; + flag |= ZEND_FUNC_IRREDUCIBLE; + flag &= ~ZEND_FUNC_NO_LOOPS; + break; + } else { + dj_parent = dj_spanning_tree[dj_parent]; + } + } + } + } + while (zend_worklist_len(&work)) { + j = zend_worklist_pop(&work); + if (blocks[j].loop_header < 0 && j != i) { + blocks[j].loop_header = i; + for (k = 0; k < blocks[j].predecessors_count; k++) { + zend_worklist_push(&work, cfg->predecessors[blocks[j].predecessor_offset + k]); + } + } + } + } + } + + *flags |= flag; + + return SUCCESS; +} +/* }}} */ + /* * Local variables: * tab-width: 4 diff --git a/ext/opcache/Optimizer/zend_cfg.h b/ext/opcache/Optimizer/zend_cfg.h index dcfaa3fbc1..4bd2899346 100644 --- a/ext/opcache/Optimizer/zend_cfg.h +++ b/ext/opcache/Optimizer/zend_cfg.h @@ -23,6 +23,8 @@ #define ZEND_FUNC_TOO_DYNAMIC (1<<0) #define ZEND_FUNC_HAS_CALLS (1<<1) #define ZEND_FUNC_VARARG (1<<2) +#define ZEND_FUNC_NO_LOOPS (1<<3) +#define ZEND_FUNC_IRREDUCIBLE (1<<4) /* zend_basic_bloc.flags */ #define ZEND_BB_START (1<<0) /* fist block */ @@ -93,11 +95,20 @@ typedef struct _zend_cfg { uint32_t *map; } zend_cfg; +#define CRT_CONSTANT(node) \ + (rt_constants ? \ + RT_CONSTANT(op_array, (node)) \ + : \ + CT_CONSTANT_EX(op_array, (node).constant) \ + ) + BEGIN_EXTERN_C() -int zend_build_cfg(zend_arena **arena, zend_op_array *op_array, int rt_constants, int stackless, zend_cfg *cfg, uint32_t *func_flags); -void zend_remark_reachable_blocks(zend_op_array *op_array, zend_cfg *cfg); -int zend_cfg_build_predecessors(zend_arena **arena, zend_cfg *cfg); +int zend_build_cfg(zend_arena **arena, zend_op_array *op_array, int rt_constants, int stackless, zend_cfg *cfg, uint32_t *func_flags); +void zend_cfg_remark_reachable_blocks(zend_op_array *op_array, zend_cfg *cfg); +int zend_cfg_build_predecessors(zend_arena **arena, zend_cfg *cfg); +int zend_cfg_compute_dominators_tree(zend_op_array *op_array, zend_cfg *cfg); +int zend_cfg_identify_loops(zend_op_array *op_array, zend_cfg *cfg, uint32_t *flags); END_EXTERN_C() diff --git a/ext/opcache/Optimizer/zend_dfg.c b/ext/opcache/Optimizer/zend_dfg.c new file mode 100644 index 0000000000..a8007ed7ea --- /dev/null +++ b/ext/opcache/Optimizer/zend_dfg.c @@ -0,0 +1,248 @@ +/* + +----------------------------------------------------------------------+ + | Zend Engine, DFG - Data Flow Graph | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2015 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 | + +----------------------------------------------------------------------+ +*/ + +#include "php.h" +#include "zend_compile.h" +#include "zend_dfg.h" + +int zend_build_dfg(zend_op_array *op_array, zend_cfg *cfg, zend_dfg *dfg) /* {{{ */ +{ + int set_size; + zend_basic_block *blocks = cfg->blocks; + int blocks_count = cfg->blocks_count; + zend_bitset tmp, gen, def, use, in, out; + zend_op *opline; + uint32_t k; + int j, changed; + + /* FIXME: can we use "gen" instead of "def" for flow analyzing? */ + set_size = dfg->size; + tmp = dfg->tmp; + gen = dfg->gen; + def = dfg->def; + use = dfg->use; + in = dfg->in; + out = dfg->out; + + /* Collect "gen", "def" and "use" sets */ + for (j = 0; j < blocks_count; j++) { + if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) { + continue; + } + for (k = blocks[j].start; k <= blocks[j].end; k++) { + opline = op_array->opcodes + k; + if (opline->opcode != ZEND_OP_DATA) { + zend_op *next = opline + 1; + if (k < blocks[j].end && + next->opcode == ZEND_OP_DATA) { + if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { + if (!DFG_ISSET(def, set_size, j, EX_VAR_TO_NUM(next->op1.var))) { + DFG_SET(use, set_size, j, EX_VAR_TO_NUM(next->op1.var)); + } + } + if (next->op2_type == IS_CV) { + if (!DFG_ISSET(def, set_size, j,EX_VAR_TO_NUM(next->op2.var))) { + DFG_SET(use, set_size, j, EX_VAR_TO_NUM(next->op2.var)); + } + } else if (next->op2_type == IS_VAR || + next->op2_type == IS_TMP_VAR) { + /* ZEND_ASSIGN_??? use the second operand + of the following OP_DATA instruction as + a temporary variable */ + switch (opline->opcode) { + case ZEND_ASSIGN_DIM: + case ZEND_ASSIGN_OBJ: + 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: + break; + default: + if (!DFG_ISSET(def, set_size, j, EX_VAR_TO_NUM(next->op2.var))) { + DFG_SET(use, set_size, j, EX_VAR_TO_NUM(next->op2.var)); + } + } + } + } + if (opline->op1_type == IS_CV) { + switch (opline->opcode) { + case ZEND_ASSIGN: + case ZEND_ASSIGN_REF: + case ZEND_BIND_GLOBAL: + case ZEND_SEND_VAR_EX: + case ZEND_SEND_REF: + case ZEND_SEND_VAR_NO_REF: + case ZEND_FE_RESET_R: + case ZEND_FE_RESET_RW: + case ZEND_ADD_ARRAY_ELEMENT: + case ZEND_INIT_ARRAY: + if (!DFG_ISSET(use, set_size, j, EX_VAR_TO_NUM(opline->op1.var))) { + // FIXME: include into "use" to ...? + DFG_SET(use, set_size, j, EX_VAR_TO_NUM(opline->op1.var)); + DFG_SET(def, set_size, j, EX_VAR_TO_NUM(opline->op1.var)); + } + DFG_SET(gen, set_size, j, EX_VAR_TO_NUM(opline->op1.var)); + 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: + case ZEND_PRE_INC: + case ZEND_PRE_DEC: + case ZEND_POST_INC: + case ZEND_POST_DEC: + case ZEND_ASSIGN_DIM: + case ZEND_ASSIGN_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_OBJ_W: + case ZEND_FETCH_OBJ_RW: + case ZEND_FETCH_OBJ_FUNC_ARG: + case ZEND_FETCH_OBJ_UNSET: + DFG_SET(gen, set_size, j, EX_VAR_TO_NUM(opline->op1.var)); + default: + if (!DFG_ISSET(def, set_size, j, EX_VAR_TO_NUM(opline->op1.var))) { + DFG_SET(use, set_size, j, EX_VAR_TO_NUM(opline->op1.var)); + } + } + } else if (opline->op1_type == IS_VAR || + opline->op1_type == IS_TMP_VAR) { + if (!DFG_ISSET(def, set_size, j, EX_VAR_TO_NUM(opline->op1.var))) { + DFG_SET(use, set_size, j, EX_VAR_TO_NUM(opline->op1.var)); + } + } + if (opline->op2_type == IS_CV) { + switch (opline->opcode) { + case ZEND_ASSIGN: + case ZEND_ASSIGN_REF: + case ZEND_FE_FETCH_R: + case ZEND_FE_FETCH_RW: + if (!DFG_ISSET(use, set_size, j, EX_VAR_TO_NUM(opline->op2.var))) { + // FIXME: include into "use" to ...? + DFG_SET(use, set_size, j, EX_VAR_TO_NUM(opline->op2.var)); + DFG_SET(def, set_size, j, EX_VAR_TO_NUM(opline->op2.var)); + } + DFG_SET(gen, set_size, j, EX_VAR_TO_NUM(opline->op2.var)); + break; + default: + if (!DFG_ISSET(def, set_size, j, EX_VAR_TO_NUM(opline->op2.var))) { + DFG_SET(use, set_size, j, EX_VAR_TO_NUM(opline->op2.var)); + } + break; + } + } else if (opline->op2_type == IS_VAR || + opline->op2_type == IS_TMP_VAR) { + if (opline->opcode == ZEND_FE_FETCH_R || opline->opcode == ZEND_FE_FETCH_RW) { + if (!DFG_ISSET(use, set_size, j, EX_VAR_TO_NUM(opline->op2.var))) { + DFG_SET(def, set_size, j, EX_VAR_TO_NUM(opline->op2.var)); + } + DFG_SET(gen, set_size, j, EX_VAR_TO_NUM(opline->op2.var)); + } else { + if (!DFG_ISSET(def, set_size, j, EX_VAR_TO_NUM(opline->op2.var))) { + DFG_SET(use, set_size, j, EX_VAR_TO_NUM(opline->op2.var)); + } + } + } + if (opline->result_type == IS_CV) { + if (!DFG_ISSET(use, set_size, j, EX_VAR_TO_NUM(opline->result.var))) { + DFG_SET(def, set_size, j, EX_VAR_TO_NUM(opline->result.var)); + } + DFG_SET(gen, set_size, j, EX_VAR_TO_NUM(opline->result.var)); + } else if (opline->result_type == IS_VAR || + opline->result_type == IS_TMP_VAR) { + if (!DFG_ISSET(use, set_size, j, EX_VAR_TO_NUM(opline->result.var))) { + DFG_SET(def, set_size, j, EX_VAR_TO_NUM(opline->result.var)); + } + DFG_SET(gen, set_size, j, EX_VAR_TO_NUM(opline->result.var)); + } + if ((opline->opcode == ZEND_FE_FETCH_R || opline->opcode == ZEND_FE_FETCH_RW) && opline->result_type == IS_TMP_VAR) { + if (!DFG_ISSET(use, set_size, j, EX_VAR_TO_NUM(next->result.var))) { + DFG_SET(def, set_size, j, EX_VAR_TO_NUM(next->result.var)); + } + DFG_SET(gen, set_size, j, EX_VAR_TO_NUM(next->result.var)); + } + } + } + } + + /* Calculate "in" and "out" sets */ + do { + changed = 0; + for (j = 0; j < blocks_count; j++) { + if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) { + continue; + } + if (blocks[j].successors[0] >= 0) { + zend_bitset_copy(DFG_BITSET(out, set_size, j), DFG_BITSET(in, set_size, blocks[j].successors[0]), set_size); + if (blocks[j].successors[1] >= 0) { + zend_bitset_union(DFG_BITSET(out, set_size, j), DFG_BITSET(in, set_size, blocks[j].successors[1]), 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); + changed = 1; + } + } + } while (changed); + +//???D if (ZCG(accel_directives).jit_debug & JIT_DEBUG_DUMP_LIVENESS) { +//???D fprintf(stderr, "Variable Liveness\n"); +//???D for (j = 0; j < blocks_count; j++) { +//???D fprintf(stderr, " BB%d:\n", j); +//???D zend_jit_dump_var_set(op_array, "gen", dfg->gen + (j * dfg->size)); +//???D zend_jit_dump_var_set(op_array, "def", dfg->def + (j * dfg->size)); +//???D zend_jit_dump_var_set(op_array, "use", dfg->use + (j * dfg->size)); +//???D zend_jit_dump_var_set(op_array, "in ", dfg->in + (j * dfg->size)); +//???D zend_jit_dump_var_set(op_array, "out", dfg->out + (j * dfg->size)); +//???D } +//???D } + + return SUCCESS; +} +/* }}} */ + +/* + * Local variables: + * tab-width: 4 + * c-basic-offset: 4 + * indent-tabs-mode: t + * End: + */ diff --git a/ext/opcache/Optimizer/zend_dfg.h b/ext/opcache/Optimizer/zend_dfg.h new file mode 100644 index 0000000000..6fe8a1ab6d --- /dev/null +++ b/ext/opcache/Optimizer/zend_dfg.h @@ -0,0 +1,59 @@ +/* + +----------------------------------------------------------------------+ + | Zend Engine, DFG - Data Flow Graph | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2015 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 | + +----------------------------------------------------------------------+ +*/ + +#ifndef ZEND_DFG_H +#define ZEND_DFG_H + +#include "zend_bitset.h" +#include "zend_cfg.h" + +typedef struct _zend_dfg { + int vars; + uint32_t size; + zend_bitset tmp; + zend_bitset gen; + zend_bitset def; + zend_bitset use; + zend_bitset in; + zend_bitset out; +} zend_dfg; + +#define DFG_BITSET(set, set_size, block_num) \ + ((set) + ((block_num) * (set_size))) + +#define DFG_SET(set, set_size, block_num, var_num) \ + zend_bitset_incl(DFG_BITSET(set, set_size, block_num), (var_num)) + +#define DFG_ISSET(set, set_size, block_num, var_num) \ + zend_bitset_in(DFG_BITSET(set, set_size, block_num), (var_num)) + +BEGIN_EXTERN_C() + +int zend_build_dfg(zend_op_array *op_array, zend_cfg *cfg, zend_dfg *dfg); + +END_EXTERN_C() + +#endif /* ZEND_DFG_H */ + +/* + * 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 8971fac0c7..c7d5d95dd2 100644 --- a/ext/opcache/Optimizer/zend_dump.c +++ b/ext/opcache/Optimizer/zend_dump.c @@ -341,6 +341,99 @@ static void zend_dump_op(const zend_op_array *op_array, const zend_basic_block * fprintf(stderr, "\n"); } +void zend_dump_block_info(const zend_cfg *cfg, int n, uint32_t dump_flags) +{ + zend_basic_block *b = cfg->blocks + n; + int printed = 0; + + fprintf(stderr, "BB%d:", n); + if (b->flags & ZEND_BB_START) { + fprintf(stderr, " start"); + } + if (b->flags & ZEND_BB_FOLLOW) { + fprintf(stderr, " follow"); + } + if (b->flags & ZEND_BB_TARGET) { + fprintf(stderr, " target"); + } + if (b->flags & ZEND_BB_EXIT) { + fprintf(stderr, " exit"); + } + if (b->flags & ZEND_BB_ENTRY) { + fprintf(stderr, " entry"); + } + if (b->flags & ZEND_BB_TRY) { + fprintf(stderr, " try"); + } + if (b->flags & ZEND_BB_CATCH) { + fprintf(stderr, " catch"); + } + if (b->flags & ZEND_BB_FINALLY) { + fprintf(stderr, " finally"); + } + if (b->flags & ZEND_BB_FINALLY_END) { + fprintf(stderr, " finally_end"); + } + if (b->flags & ZEND_BB_GEN_VAR) { + fprintf(stderr, " gen_var"); + } + if (b->flags & ZEND_BB_KILL_VAR) { + fprintf(stderr, " kill_var"); + } + if ((dump_flags & ZEND_DUMP_UNREACHABLE) & !(b->flags & ZEND_BB_REACHABLE)) { + fprintf(stderr, " unreachable"); + } + if (b->flags & ZEND_BB_LOOP_HEADER) { + fprintf(stderr, " loop_header"); + } + if (b->flags & ZEND_BB_IRREDUCIBLE_LOOP) { + fprintf(stderr, " irreducible"); + } + fprintf(stderr, "\n"); + + if (b->predecessors_count) { + int *p = cfg->predecessors + b->predecessor_offset; + int *end = p + b->predecessors_count; + + fprintf(stderr, " ; from=(BB%d", *p); + for (p++; p < end; p++) { + fprintf(stderr, ", BB%d", *p); + } + fprintf(stderr, ")\n"); + } + + if (b->successors[0] != -1) { + fprintf(stderr, " ; to=(BB%d", b->successors[0]); + printed = 1; + if (b->successors[1] != -1) { + fprintf(stderr, ", BB%d", b->successors[1]); + } + } + if (printed) { + fprintf(stderr, ")\n"); + } + + if (b->idom >= 0) { + fprintf(stderr, " ; idom=%d\n", b->idom); + } + if (b->level >= 0) { + fprintf(stderr, " ; level=%d\n", b->level); + } + if (b->loop_header >= 0) { + fprintf(stderr, " ; loop_header=%d\n", b->level); + } + if (b->children >= 0) { + int j = b->children; + fprintf(stderr, " ; children=(BB%d", j); + j = cfg->blocks[j].next_child; + while (j >= 0) { + fprintf(stderr, ", BB%d", j); + j = cfg->blocks[j].next_child; + } + fprintf(stderr, ")\n"); + } +} + void zend_dump_op_array(const zend_op_array *op_array, const zend_cfg *cfg, uint32_t dump_flags, const char *msg) { int i; @@ -373,69 +466,8 @@ void zend_dump_op_array(const zend_op_array *op_array, const zend_cfg *cfg, uint if ((dump_flags & ZEND_DUMP_UNREACHABLE) || (b->flags & ZEND_BB_REACHABLE)) { const zend_op *opline; const zend_op *end; - int printed = 0; - - fprintf(stderr, "BB%d:", n); - if (b->flags & ZEND_BB_START) { - fprintf(stderr, " start"); - } - if (b->flags & ZEND_BB_FOLLOW) { - fprintf(stderr, " follow"); - } - if (b->flags & ZEND_BB_TARGET) { - fprintf(stderr, " target"); - } - if (b->flags & ZEND_BB_EXIT) { - fprintf(stderr, " exit"); - } - if (b->flags & ZEND_BB_ENTRY) { - fprintf(stderr, " entry"); - } - if (b->flags & ZEND_BB_TRY) { - fprintf(stderr, " try"); - } - if (b->flags & ZEND_BB_CATCH) { - fprintf(stderr, " catch"); - } - if (b->flags & ZEND_BB_FINALLY) { - fprintf(stderr, " finally"); - } - if (b->flags & ZEND_BB_FINALLY_END) { - fprintf(stderr, " finally_end"); - } - if (b->flags & ZEND_BB_GEN_VAR) { - fprintf(stderr, " gen_var"); - } - if (b->flags & ZEND_BB_KILL_VAR) { - fprintf(stderr, " kill_var"); - } - if ((dump_flags & ZEND_DUMP_UNREACHABLE) & !(b->flags & ZEND_BB_REACHABLE)) { - fprintf(stderr, " unreachable"); - } - - if (b->predecessors_count) { - int *p = cfg->predecessors + b->predecessor_offset; - int *end = p + b->predecessors_count; - - fprintf(stderr, " from=(BB%d", *p); - for (p++; p < end; p++) { - fprintf(stderr, ", BB%d", *p); - } - fprintf(stderr, ")"); - } - - if (b->successors[0] != -1) { - fprintf(stderr, " to=(BB%d", b->successors[0]); - printed = 1; - if (b->successors[1] != -1) { - fprintf(stderr, ", BB%d", b->successors[1]); - } - } - if (printed) { - fprintf(stderr, ")"); - } - fprintf(stderr, "\n"); + zend_dump_block_info(cfg, n, dump_flags); if (!(b->flags & ZEND_BB_EMPTY)) { opline = op_array->opcodes + b->start; end = op_array->opcodes + b->end + 1; diff --git a/ext/opcache/Optimizer/zend_dump.h b/ext/opcache/Optimizer/zend_dump.h index 551c834300..e879d950eb 100644 --- a/ext/opcache/Optimizer/zend_dump.h +++ b/ext/opcache/Optimizer/zend_dump.h @@ -24,6 +24,7 @@ BEGIN_EXTERN_C() void zend_dump_op_array(const zend_op_array *op_array, const zend_cfg *cfg, uint32_t dump_flags, const char *msg); +void zend_dump_block_info(const zend_cfg *cfg, int n, uint32_t dump_flags); END_EXTERN_C() diff --git a/ext/opcache/Optimizer/zend_optimizer.c b/ext/opcache/Optimizer/zend_optimizer.c index 3aaae5b915..fd7e367037 100644 --- a/ext/opcache/Optimizer/zend_optimizer.c +++ b/ext/opcache/Optimizer/zend_optimizer.c @@ -610,6 +610,16 @@ static void zend_optimize(zend_op_array *op_array, } } + /* pass 6: + * - DFA optimization + */ + if (ZEND_OPTIMIZER_PASS_6 & ctx->optimization_level) { + optimize_dfa(op_array, ctx); + if (ctx->debug_level & ZEND_DUMP_AFTER_PASS_6) { + zend_dump_op_array(op_array, NULL, 1, "after pass 6"); + } + } + /* pass 9: * - Optimize temp variables usage */ diff --git a/ext/opcache/Optimizer/zend_optimizer.h b/ext/opcache/Optimizer/zend_optimizer.h index c1013013ce..c991c37c1f 100644 --- a/ext/opcache/Optimizer/zend_optimizer.h +++ b/ext/opcache/Optimizer/zend_optimizer.h @@ -30,7 +30,7 @@ #define ZEND_OPTIMIZER_PASS_3 (1<<2) /* ++, +=, series of jumps */ #define ZEND_OPTIMIZER_PASS_4 (1<<3) /* INIT_FCALL_BY_NAME -> DO_FCALL */ #define ZEND_OPTIMIZER_PASS_5 (1<<4) /* CFG based optimization */ -#define ZEND_OPTIMIZER_PASS_6 (1<<5) +#define ZEND_OPTIMIZER_PASS_6 (1<<5) /* DFA based optimization */ #define ZEND_OPTIMIZER_PASS_7 (1<<6) #define ZEND_OPTIMIZER_PASS_8 (1<<7) #define ZEND_OPTIMIZER_PASS_9 (1<<8) /* TMP VAR usage */ @@ -67,6 +67,11 @@ #define ZEND_DUMP_AFTER_BLOCK_PASS (1<<19) #define ZEND_DUMP_BLOCK_PASS_VARS (1<<20) +#define ZEND_DUMP_BEFORE_DFA_PASS (1<<21) +#define ZEND_DUMP_AFTER_DFA_PASS (1<<22) +#define ZEND_DUMP_DFA_CFG (1<<23) +#define ZEND_DUMP_DFA_DOMINATORS (1<<24) + typedef struct _zend_script { zend_string *filename; zend_op_array main_op_array; diff --git a/ext/opcache/Optimizer/zend_optimizer_internal.h b/ext/opcache/Optimizer/zend_optimizer_internal.h index b41fe9f9e6..3bf96165e7 100644 --- a/ext/opcache/Optimizer/zend_optimizer_internal.h +++ b/ext/opcache/Optimizer/zend_optimizer_internal.h @@ -97,6 +97,7 @@ void zend_optimizer_pass2(zend_op_array *op_array); void zend_optimizer_pass3(zend_op_array *op_array); void optimize_func_calls(zend_op_array *op_array, zend_optimizer_ctx *ctx); void optimize_cfg(zend_op_array *op_array, zend_optimizer_ctx *ctx); +void optimize_dfa(zend_op_array *op_array, zend_optimizer_ctx *ctx); void optimize_temporary_variables(zend_op_array *op_array, zend_optimizer_ctx *ctx); void zend_optimizer_nop_removal(zend_op_array *op_array); void zend_optimizer_compact_literals(zend_op_array *op_array, zend_optimizer_ctx *ctx); diff --git a/ext/opcache/Optimizer/zend_ssa.c b/ext/opcache/Optimizer/zend_ssa.c new file mode 100644 index 0000000000..e49da38cb2 --- /dev/null +++ b/ext/opcache/Optimizer/zend_ssa.c @@ -0,0 +1,879 @@ +/* + +----------------------------------------------------------------------+ + | Zend Engine, SSA - Static Single Assignment Form | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2015 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 | + +----------------------------------------------------------------------+ +*/ + +#include "php.h" +#include "zend_compile.h" +#include "zend_dfg.h" +#include "zend_ssa.h" + +static int needs_pi(zend_op_array *op_array, zend_cfg *cfg, zend_dfg *dfg, zend_ssa *ssa, int from, int to, int var) /* {{{ */ +{ + if (from == to || cfg->blocks[to].predecessors_count != 1) { + zend_ssa_phi *p = ssa->blocks[to].phis; + while (p) { + if (p->pi < 0 && p->var == var) { + return 1; + } + p = p->next; + } + return 0; + } + return DFG_ISSET(dfg->in, dfg->size, to, var); +} +/* }}} */ + +static int add_pi(zend_arena **arena, zend_op_array *op_array, zend_cfg *cfg, zend_dfg *dfg, zend_ssa *ssa, int from, int to, int var, int min_var, int max_var, long min, long max, char underflow, char overflow, char negative) /* {{{ */ +{ + if (needs_pi(op_array, cfg, dfg, ssa, from, to, var)) { + zend_ssa_phi *phi = zend_arena_calloc(arena, 1, + sizeof(zend_ssa_phi) + + sizeof(int) * cfg->blocks[to].predecessors_count + + sizeof(void*) * cfg->blocks[to].predecessors_count); + + if (!phi) { + return FAILURE; + } + phi->sources = (int*)(((char*)phi) + sizeof(zend_ssa_phi)); + memset(phi->sources, 0xff, sizeof(int) * cfg->blocks[to].predecessors_count); + phi->use_chains = (zend_ssa_phi**)(((char*)phi->sources) + sizeof(int) * cfg->blocks[to].predecessors_count); + + phi->pi = from; + phi->constraint.min_var = min_var; + phi->constraint.max_var = max_var; + phi->constraint.min_ssa_var = -1; + phi->constraint.max_ssa_var = -1; + phi->constraint.range.min = min; + phi->constraint.range.max = max; + phi->constraint.range.underflow = underflow; + phi->constraint.range.overflow = overflow; + phi->constraint.negative = negative ? NEG_INIT : NEG_NONE; + phi->var = var; + phi->ssa_var = -1; + phi->next = ssa->blocks[to].phis; + ssa->blocks[to].phis = phi; + } + return SUCCESS; +} +/* }}} */ + +static int zend_ssa_rename(zend_op_array *op_array, zend_cfg *cfg, zend_ssa *ssa, int *var, int n) /* {{{ */ +{ + zend_basic_block *blocks = cfg->blocks; + zend_ssa_block *ssa_blocks = ssa->blocks; + zend_ssa_op *ssa_ops = ssa->ops; + int ssa_vars_count = ssa->vars_count; + int i, j; + uint32_t k; + zend_op *opline; + int *tmp = NULL; + + // FIXME: Can we optimize this copying out in some cases? + if (blocks[n].next_child >= 0) { + tmp = alloca(sizeof(int) * (op_array->last_var + op_array->T)); + memcpy(tmp, var, sizeof(int) * (op_array->last_var + op_array->T)); + var = tmp; + } + + if (ssa_blocks[n].phis) { + zend_ssa_phi *phi = ssa_blocks[n].phis; + do { + if (phi->ssa_var < 0) { + phi->ssa_var = ssa_vars_count; + var[phi->var] = ssa_vars_count; + ssa_vars_count++; + } else { + var[phi->var] = phi->ssa_var; + } + phi = phi->next; + } while (phi); + } + + for (k = blocks[n].start; k <= blocks[n].end; k++) { + opline = op_array->opcodes + k; + if (opline->opcode != ZEND_OP_DATA) { + zend_op *next = opline + 1; + if (k < blocks[n].end && + next->opcode == ZEND_OP_DATA) { + if (next->op1_type == IS_CV) { + ssa_ops[k + 1].op1_use = var[EX_VAR_TO_NUM(next->op1.var)]; + //USE_SSA_VAR(next->op1.var); + } else if (next->op1_type == IS_VAR || + next->op1_type == IS_TMP_VAR) { + ssa_ops[k + 1].op1_use = var[EX_VAR_TO_NUM(next->op1.var)]; + //USE_SSA_VAR(op_array->last_var + next->op1.var); + } + if (next->op2_type == IS_CV) { + ssa_ops[k + 1].op2_use = var[EX_VAR_TO_NUM(next->op2.var)]; + //USE_SSA_VAR(next->op2.var); + } else if (next->op2_type == IS_VAR || + next->op2_type == IS_TMP_VAR) { + /* ZEND_ASSIGN_??? use the second operand + of the following OP_DATA instruction as + a temporary variable */ + switch (opline->opcode) { + case ZEND_ASSIGN_DIM: + case ZEND_ASSIGN_OBJ: + 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: + break; + default: + ssa_ops[k + 1].op2_use = var[EX_VAR_TO_NUM(next->op2.var)]; + //USE_SSA_VAR(op_array->last_var + next->op2.var); + } + } + } + if (opline->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { + ssa_ops[k].op1_use = var[EX_VAR_TO_NUM(opline->op1.var)]; + //USE_SSA_VAR(op_array->last_var + opline->op1.var) + } + if (opline->opcode == ZEND_FE_FETCH_R || opline->opcode == ZEND_FE_FETCH_RW) { + if (opline->op2_type == IS_CV) { + ssa_ops[k].op2_use = var[EX_VAR_TO_NUM(opline->op2.var)]; + } + ssa_ops[k].op2_def = ssa_vars_count; + var[EX_VAR_TO_NUM(opline->op2.var)] = ssa_vars_count; + ssa_vars_count++; + //NEW_SSA_VAR(opline->op2.var) + } else if (opline->op2_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { + ssa_ops[k].op2_use = var[EX_VAR_TO_NUM(opline->op2.var)]; + //USE_SSA_VAR(op_array->last_var + opline->op2.var) + } + switch (opline->opcode) { + case ZEND_ASSIGN: + if (opline->op1_type == IS_CV) { + ssa_ops[k].op1_def = ssa_vars_count; + var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count; + ssa_vars_count++; + //NEW_SSA_VAR(opline->op1.var) + } + if (opline->op2_type == IS_CV) { + ssa_ops[k].op2_def = ssa_vars_count; + var[EX_VAR_TO_NUM(opline->op2.var)] = ssa_vars_count; + ssa_vars_count++; + //NEW_SSA_VAR(opline->op2.var) + } + break; + case ZEND_ASSIGN_REF: +//TODO: ??? + if (opline->op1_type == IS_CV) { + ssa_ops[k].op1_def = ssa_vars_count; + var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count; + ssa_vars_count++; + //NEW_SSA_VAR(opline->op1.var) + } + if (opline->op2_type == IS_CV) { + ssa_ops[k].op2_def = ssa_vars_count; + var[EX_VAR_TO_NUM(opline->op2.var)] = ssa_vars_count; + ssa_vars_count++; + //NEW_SSA_VAR(opline->op2.var) + } + break; + case ZEND_BIND_GLOBAL: + if (opline->op1_type == IS_CV) { + ssa_ops[k].op1_def = ssa_vars_count; + var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count; + ssa_vars_count++; + //NEW_SSA_VAR(opline->op1.var) + } + break; + case ZEND_ASSIGN_DIM: + case ZEND_ASSIGN_OBJ: + if (opline->op1_type == IS_CV) { + ssa_ops[k].op1_def = ssa_vars_count; + var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count; + ssa_vars_count++; + //NEW_SSA_VAR(opline->op1.var) + } + if (next->op1_type == IS_CV) { + ssa_ops[k + 1].op1_def = ssa_vars_count; + var[EX_VAR_TO_NUM(next->op1.var)] = ssa_vars_count; + ssa_vars_count++; + //NEW_SSA_VAR(next->op1.var) + } + break; + case ZEND_ADD_ARRAY_ELEMENT: + ssa_ops[k].result_use = var[EX_VAR_TO_NUM(opline->result.var)]; + case ZEND_INIT_ARRAY: + if (opline->op1_type == IS_CV) { + ssa_ops[k].op1_def = ssa_vars_count; + var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count; + ssa_vars_count++; + //NEW_SSA_VAR(opline+->op1.var) + } + break; + case ZEND_SEND_VAR_NO_REF: + case ZEND_SEND_VAR_EX: + case ZEND_SEND_REF: + case ZEND_FE_RESET_R: + case ZEND_FE_RESET_RW: +//TODO: ??? + if (opline->op1_type == IS_CV) { + ssa_ops[k].op1_def = ssa_vars_count; + var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count; + ssa_vars_count++; + //NEW_SSA_VAR(opline->op1.var) + } + 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: + case ZEND_PRE_INC: + case ZEND_PRE_DEC: + case ZEND_POST_INC: + case ZEND_POST_DEC: + if (opline->op1_type == IS_CV) { + ssa_ops[k].op1_def = ssa_vars_count; + var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count; + ssa_vars_count++; + //NEW_SSA_VAR(opline->op1.var) + } + break; + case ZEND_UNSET_VAR: + if (opline->extended_value & ZEND_QUICK_SET) { + ssa_ops[k].op1_def = ssa_vars_count; + var[EX_VAR_TO_NUM(opline->op1.var)] = EX_VAR_TO_NUM(opline->op1.var); + ssa_vars_count++; + } + break; + 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_OBJ_W: + case ZEND_FETCH_OBJ_RW: + case ZEND_FETCH_OBJ_FUNC_ARG: + case ZEND_FETCH_OBJ_UNSET: + if (opline->op1_type == IS_CV) { + ssa_ops[k].op1_def = ssa_vars_count; + var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count; + ssa_vars_count++; + //NEW_SSA_VAR(opline->op1.var) + } + break; + default: + break; + } + if (opline->result_type == IS_CV) { + ssa_ops[k].result_def = ssa_vars_count; + var[EX_VAR_TO_NUM(opline->result.var)] = ssa_vars_count; + ssa_vars_count++; + //NEW_SSA_VAR(opline->result.var) + } else if (opline->result_type == IS_VAR || + opline->result_type == IS_TMP_VAR) { + ssa_ops[k].result_def = ssa_vars_count; + var[EX_VAR_TO_NUM(opline->result.var)] = ssa_vars_count; + ssa_vars_count++; + //NEW_SSA_VAR(op_array->last_var + opline->result.var) + } + } + } + + for (i = 0; i < 2; i++) { + int succ = blocks[n].successors[i]; + if (succ >= 0) { + zend_ssa_phi *p; + for (p = ssa_blocks[succ].phis; p; p = p->next) { + if (p->pi == n) { + /* e-SSA Pi */ + if (p->constraint.min_var >= 0) { + p->constraint.min_ssa_var = var[p->constraint.min_var]; + } + if (p->constraint.max_var >= 0) { + p->constraint.max_ssa_var = var[p->constraint.max_var]; + } + for (j = 0; j < blocks[succ].predecessors_count; j++) { + p->sources[j] = var[p->var]; + } + if (p->ssa_var < 0) { + p->ssa_var = ssa_vars_count; + ssa_vars_count++; + } + } else if (p->pi < 0) { + /* Normal Phi */ + for (j = 0; j < blocks[succ].predecessors_count; j++) + if (cfg->predecessors[blocks[succ].predecessor_offset + j] == n) { + break; + } + ZEND_ASSERT(j < blocks[succ].predecessors_count); + p->sources[j] = var[p->var]; + } + } + for (p = ssa_blocks[succ].phis; p && (p->pi >= 0); p = p->next) { + if (p->pi == n) { + zend_ssa_phi *q = p->next; + while (q) { + if (q->pi < 0 && q->var == p->var) { + for (j = 0; j < blocks[succ].predecessors_count; j++) { + if (cfg->predecessors[blocks[succ].predecessor_offset + j] == n) { + break; + } + } + ZEND_ASSERT(j < blocks[succ].predecessors_count); + q->sources[j] = p->ssa_var; + } + q = q->next; + } + } + } + } + } + + ssa->vars_count = ssa_vars_count; + + j = blocks[n].children; + while (j >= 0) { + // FIXME: Tail call optimization? + if (zend_ssa_rename(op_array, cfg, ssa, var, j) != SUCCESS) + return FAILURE; + j = blocks[j].next_child; + } + + return SUCCESS; +} +/* }}} */ + +int zend_build_ssa(zend_arena **arena, zend_op_array *op_array, zend_cfg *cfg, int rt_constants, zend_ssa *ssa, uint32_t *func_flags) /* {{{ */ +{ + zend_basic_block *blocks = cfg->blocks; + zend_ssa_block *ssa_blocks; + int blocks_count = cfg->blocks_count; + uint32_t set_size; + zend_bitset tmp, gen, in; + int *var = 0; + int i, j, k, changed; + zend_dfg dfg; + + ssa_blocks = zend_arena_calloc(arena, blocks_count, sizeof(zend_ssa_block)); + if (!ssa_blocks) { + return FAILURE; + } + ssa->blocks = ssa_blocks; + + /* Compute Variable Liveness */ + dfg.vars = op_array->last_var + op_array->T; + dfg.size = set_size = zend_bitset_len(dfg.vars); + dfg.tmp = alloca((set_size * sizeof(zend_ulong)) * (blocks_count * 5 + 1)); + memset(dfg.tmp, 0, (set_size * sizeof(zend_ulong)) * (blocks_count * 5 + 1)); + dfg.gen = dfg.tmp + set_size; + dfg.def = dfg.gen + set_size * blocks_count; + dfg.use = dfg.def + set_size * blocks_count; + dfg.in = dfg.use + set_size * blocks_count; + dfg.out = dfg.in + set_size * blocks_count; + + if (zend_build_dfg(op_array, cfg, &dfg) != SUCCESS) { + return FAILURE; + } + + tmp = dfg.tmp; + gen = dfg.gen; + in = dfg.in; + + /* SSA construction, Step 1: Propagate "gen" sets in merge points */ + do { + changed = 0; + for (j = 0; j < blocks_count; j++) { + if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) { + continue; + } + if (j >= 0 && (blocks[j].predecessors_count > 1 || j == 0)) { + zend_bitset_copy(tmp, gen + (j * set_size), set_size); + for (k = 0; k < blocks[j].predecessors_count; k++) { + i = cfg->predecessors[blocks[j].predecessor_offset + k]; + while (i != blocks[j].idom) { + zend_bitset_union_with_intersection(tmp, tmp, gen + (i * set_size), in + (j * set_size), set_size); + i = blocks[i].idom; + } + } + if (!zend_bitset_equal(gen + (j * set_size), tmp, set_size)) { + zend_bitset_copy(gen + (j * set_size), tmp, set_size); + changed = 1; + } + } + } + } while (changed); + + /* SSA construction, Step 2: Phi placement based on Dominance Frontiers */ + var = alloca(sizeof(int) * (op_array->last_var + op_array->T)); + if (!var) { + return FAILURE; + } + zend_bitset_clear(tmp, set_size); + + for (j = 0; j < blocks_count; j++) { + if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) { + continue; + } + if (blocks[j].predecessors_count > 1) { + zend_bitset_clear(tmp, set_size); + if (blocks[j].flags & ZEND_BB_IRREDUCIBLE_LOOP) { + /* Prevent any values from flowing into irreducible loops by + replacing all incoming values with explicit phis. The + register allocator depends on this property. */ + zend_bitset_copy(tmp, in + (j * set_size), set_size); + } else { + for (k = 0; k < blocks[j].predecessors_count; k++) { + i = cfg->predecessors[blocks[j].predecessor_offset + k]; + while (i != blocks[j].idom) { + zend_bitset_union_with_intersection(tmp, tmp, gen + (i * set_size), in + (j * set_size), set_size); + i = blocks[i].idom; + } + } + } + + if (!zend_bitset_empty(tmp, set_size)) { + i = op_array->last_var + op_array->T; + while (i > 0) { + i--; + if (zend_bitset_in(tmp, i)) { + zend_ssa_phi *phi = zend_arena_calloc(arena, 1, + sizeof(zend_ssa_phi) + + sizeof(int) * blocks[j].predecessors_count + + sizeof(void*) * blocks[j].predecessors_count); + + if (!phi) + return FAILURE; + phi->sources = (int*)(((char*)phi) + sizeof(zend_ssa_phi)); + memset(phi->sources, 0xff, sizeof(int) * blocks[j].predecessors_count); + phi->use_chains = (zend_ssa_phi**)(((char*)phi->sources) + sizeof(int) * cfg->blocks[j].predecessors_count); + + phi->pi = -1; + phi->var = i; + phi->ssa_var = -1; + phi->next = ssa_blocks[j].phis; + ssa_blocks[j].phis = phi; + } + } + } + } + } + + /* e-SSA construction: Pi placement (Pi is actually a Phi with single + * source and constraint). + * Order of Phis is importent, Pis must be placed before Phis + */ + for (j = 0; j < blocks_count; j++) { + zend_op *opline = op_array->opcodes + cfg->blocks[j].end; + int bt; /* successor block number if a condition is true */ + int bf; /* successor block number if a condition is false */ + + if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) { + continue; + } + /* the last instruction of basic block is conditional branch, + * based on comparison of CV(s) + */ + switch (opline->opcode) { + case ZEND_JMPZ: + if (cfg->blocks[cfg->blocks[j].successors[0]].start == OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes) { + bf = cfg->blocks[j].successors[0]; + bt = cfg->blocks[j].successors[1]; + } else { + bt = cfg->blocks[j].successors[0]; + bf = cfg->blocks[j].successors[1]; + } + break; + case ZEND_JMPNZ: + if (cfg->blocks[cfg->blocks[j].successors[0]].start == OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes) { + bt = cfg->blocks[j].successors[0]; + bf = cfg->blocks[j].successors[1]; + } else { + bf = cfg->blocks[j].successors[0]; + bt = cfg->blocks[j].successors[1]; + } + break; + case ZEND_JMPZNZ: + if (cfg->blocks[cfg->blocks[j].successors[0]].start == OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes) { + bf = cfg->blocks[j].successors[0]; + bt = cfg->blocks[j].successors[1]; + } else { + bt = cfg->blocks[j].successors[0]; + bf = cfg->blocks[j].successors[1]; + } + break; + default: + continue; + } + if (opline->op1_type == IS_TMP_VAR && + ((opline-1)->opcode == ZEND_IS_EQUAL || + (opline-1)->opcode == ZEND_IS_NOT_EQUAL || + (opline-1)->opcode == ZEND_IS_SMALLER || + (opline-1)->opcode == ZEND_IS_SMALLER_OR_EQUAL) && + opline->op1.var == (opline-1)->result.var) { + int var1 = -1; + int var2 = -1; + long val1 = 0; + long val2 = 0; +// long val = 0; + + if ((opline-1)->op1_type == IS_CV) { + var1 = EX_VAR_TO_NUM((opline-1)->op1.var); + } else if ((opline-1)->op1_type == IS_TMP_VAR) { + zend_op *op = opline; + while (op != op_array->opcodes) { + op--; + if (op->result_type == IS_TMP_VAR && + op->result.var == (opline-1)->op1.var) { + if (op->opcode == ZEND_POST_DEC) { + if (op->op1_type == IS_CV) { + var1 = EX_VAR_TO_NUM(op->op1.var); + val2--; + } + } else if (op->opcode == ZEND_POST_INC) { + if (op->op1_type == IS_CV) { + var1 = EX_VAR_TO_NUM(op->op1.var); + val2++; + } + } else if (op->opcode == ZEND_ADD) { + if (op->op1_type == IS_CV && + op->op2_type == IS_CONST && + Z_TYPE_P(CRT_CONSTANT(op->op2)) == IS_LONG) { + var1 = EX_VAR_TO_NUM(op->op1.var); + val2 -= Z_LVAL_P(CRT_CONSTANT(op->op2)); + } else if (op->op2_type == IS_CV && + op->op1_type == IS_CONST && + Z_TYPE_P(CRT_CONSTANT(op->op1)) == IS_LONG) { + var1 = EX_VAR_TO_NUM(op->op2.var); + val2 -= Z_LVAL_P(CRT_CONSTANT(op->op1)); + } + } else if (op->opcode == ZEND_SUB) { + if (op->op1_type == IS_CV && + op->op2_type == IS_CONST && + Z_TYPE_P(CRT_CONSTANT(op->op2)) == IS_LONG) { + var1 = EX_VAR_TO_NUM(op->op1.var); + val2 += Z_LVAL_P(CRT_CONSTANT(op->op2)); + } + } + break; + } + } + } + + if ((opline-1)->op2_type == IS_CV) { + var2 = EX_VAR_TO_NUM((opline-1)->op2.var); + } else if ((opline-1)->op2_type == IS_TMP_VAR) { + zend_op *op = opline; + while (op != op_array->opcodes) { + op--; + if (op->result_type == IS_TMP_VAR && + op->result.var == (opline-1)->op2.var) { + if (op->opcode == ZEND_POST_DEC) { + if (op->op1_type == IS_CV) { + var2 = EX_VAR_TO_NUM(op->op1.var); + val1--; + } + } else if (op->opcode == ZEND_POST_INC) { + if (op->op1_type == IS_CV) { + var2 = EX_VAR_TO_NUM(op->op1.var); + val1++; + } + } else if (op->opcode == ZEND_ADD) { + if (op->op1_type == IS_CV && + op->op2_type == IS_CONST && + Z_TYPE_P(CRT_CONSTANT(op->op2)) == IS_LONG) { + var2 = EX_VAR_TO_NUM(op->op1.var); + val1 -= Z_LVAL_P(CRT_CONSTANT(op->op2)); + } else if (op->op2_type == IS_CV && + op->op1_type == IS_CONST && + Z_TYPE_P(CRT_CONSTANT(op->op1)) == IS_LONG) { + var2 = EX_VAR_TO_NUM(op->op2.var); + val1 -= Z_LVAL_P(CRT_CONSTANT(op->op1)); + } + } else if (op->opcode == ZEND_SUB) { + if (op->op1_type == IS_CV && + op->op2_type == IS_CONST && + Z_TYPE_P(CRT_CONSTANT(op->op2)) == IS_LONG) { + var2 = EX_VAR_TO_NUM(op->op1.var); + val1 += Z_LVAL_P(CRT_CONSTANT(op->op2)); + } + } + break; + } + } + } + + if (var1 >= 0 && var2 >= 0) { + int tmp = val1; + val1 -= val2; + val2 -= tmp; + } else if (var1 >= 0 && var2 < 0) { + if ((opline-1)->op2_type == IS_CONST && + Z_TYPE_P(CRT_CONSTANT((opline-1)->op2)) == IS_LONG) { + val2 += Z_LVAL_P(CRT_CONSTANT((opline-1)->op2)); + } else if ((opline-1)->op2_type == IS_CONST && + Z_TYPE_P(CRT_CONSTANT((opline-1)->op2)) == IS_FALSE) { + val2 += 0; + } else if ((opline-1)->op2_type == IS_CONST && + Z_TYPE_P(CRT_CONSTANT((opline-1)->op2)) == IS_TRUE) { + val2 += 12; + } else { + var1 = -1; + } + } else if (var1 < 0 && var2 >= 0) { + if ((opline-1)->op1_type == IS_CONST && + Z_TYPE_P(CRT_CONSTANT((opline-1)->op1)) == IS_LONG) { + val1 += Z_LVAL_P(CRT_CONSTANT((opline-1)->op1)); + } else if ((opline-1)->op1_type == IS_CONST && + Z_TYPE_P(CRT_CONSTANT((opline-1)->op1)) == IS_FALSE) { + val1 += 0; + } else if ((opline-1)->op1_type == IS_CONST && + Z_TYPE_P(CRT_CONSTANT((opline-1)->op1)) == IS_TRUE) { + val1 += 1; + } else { + var2 = -1; + } + } + + if (var1 >= 0) { + if ((opline-1)->opcode == ZEND_IS_EQUAL) { + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bt, var1, var2, var2, val2, val2, 0, 0, 0) != SUCCESS) { + return FAILURE; + } + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bf, var1, var2, var2, val2, val2, 0, 0, 1) != SUCCESS) { + return FAILURE; + } + } else if ((opline-1)->opcode == ZEND_IS_NOT_EQUAL) { + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bf, var1, var2, var2, val2, val2, 0, 0, 0) != SUCCESS) { + return FAILURE; + } + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bt, var1, var2, var2, val2, val2, 0, 0, 1) != SUCCESS) { + return FAILURE; + } + } else if ((opline-1)->opcode == ZEND_IS_SMALLER) { + if (val2 > LONG_MIN) { + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bt, var1, -1, var2, LONG_MIN, val2-1, 1, 0, 0) != SUCCESS) { + return FAILURE; + } + } + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bf, var1, var2, -1, val2, LONG_MAX, 0, 1, 0) != SUCCESS) { + return FAILURE; + } + } else if ((opline-1)->opcode == ZEND_IS_SMALLER_OR_EQUAL) { + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bt, var1, -1, var2, LONG_MIN, val2, 1, 0, 0) != SUCCESS) { + return FAILURE; + } + if (val2 < LONG_MAX) { + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bf, var1, var2, -1, val2+1, LONG_MAX, 0, 1, 0) != SUCCESS) { + return FAILURE; + } + } + } + } + if (var2 >= 0) { + if((opline-1)->opcode == ZEND_IS_EQUAL) { + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bt, var2, var1, var1, val1, val1, 0, 0, 0) != SUCCESS) { + return FAILURE; + } + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bf, var2, var1, var1, val1, val1, 0, 0, 1) != SUCCESS) { + return FAILURE; + } + } else if ((opline-1)->opcode == ZEND_IS_NOT_EQUAL) { + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bf, var2, var1, var1, val1, val1, 0, 0, 0) != SUCCESS) { + return FAILURE; + } + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bt, var2, var1, var1, val1, val1, 0, 0, 1) != SUCCESS) { + return FAILURE; + } + } else if ((opline-1)->opcode == ZEND_IS_SMALLER) { + if (val1 < LONG_MAX) { + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bt, var2, var1, -1, val1+1, LONG_MAX, 0, 1, 0) != SUCCESS) { + return FAILURE; + } + } + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bf, var2, -1, var1, LONG_MIN, val1, 1, 0, 0) != SUCCESS) { + return FAILURE; + } + } else if ((opline-1)->opcode == ZEND_IS_SMALLER_OR_EQUAL) { + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bt, var2, var1, -1, val1, LONG_MAX, 0 ,1, 0) != SUCCESS) { + return FAILURE; + } + if (val1 > LONG_MIN) { + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bf, var2, -1, var1, LONG_MIN, val1-1, 1, 0, 0) != SUCCESS) { + return FAILURE; + } + } + } + } + } else if (opline->op1_type == IS_TMP_VAR && + ((opline-1)->opcode == ZEND_POST_INC || + (opline-1)->opcode == ZEND_POST_DEC) && + opline->op1.var == (opline-1)->result.var && + (opline-1)->op1_type == IS_CV) { + int var = EX_VAR_TO_NUM((opline-1)->op1.var); + + if ((opline-1)->opcode == ZEND_POST_DEC) { + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bf, var, -1, -1, -1, -1, 0, 0, 0) != SUCCESS) { + return FAILURE; + } + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bt, var, -1, -1, -1, -1, 0, 0, 1) != SUCCESS) { + return FAILURE; + } + } else if ((opline-1)->opcode == ZEND_POST_INC) { + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bf, var, -1, -1, 1, 1, 0, 0, 0) != SUCCESS) { + return FAILURE; + } + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bt, var, -1, -1, 1, 1, 0, 0, 1) != SUCCESS) { + return FAILURE; + } + } + } else if (opline->op1_type == IS_VAR && + ((opline-1)->opcode == ZEND_PRE_INC || + (opline-1)->opcode == ZEND_PRE_DEC) && + opline->op1.var == (opline-1)->result.var && + (opline-1)->op1_type == IS_CV) { + int var = EX_VAR_TO_NUM((opline-1)->op1.var); + + if ((opline-1)->opcode == ZEND_PRE_DEC) { + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bf, var, -1, -1, 0, 0, 0, 0, 0) != SUCCESS) { + return FAILURE; + } + /* speculative */ + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bt, var, -1, -1, 0, 0, 0, 0, 1) != SUCCESS) { + return FAILURE; + } + } else if ((opline-1)->opcode == ZEND_PRE_INC) { + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bf, var, -1, -1, 0, 0, 0, 0, 0) != SUCCESS) { + return FAILURE; + } + /* speculative */ + if (add_pi(arena, op_array, cfg, &dfg, ssa, j, bt, var, -1, -1, 0, 0, 0, 0, 1) != SUCCESS) { + return FAILURE; + } + } + } + } + + /* SSA construction, Step ?: Phi after Pi placement based on Dominance Frontiers */ + for (j = 0; j < blocks_count; j++) { + if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) { + continue; + } + if (blocks[j].predecessors_count > 1) { + zend_bitset_clear(tmp, set_size); + if (blocks[j].flags & ZEND_BB_IRREDUCIBLE_LOOP) { + /* Prevent any values from flowing into irreducible loops by + replacing all incoming values with explicit phis. The + register allocator depends on this property. */ + zend_bitset_copy(tmp, in + (j * set_size), set_size); + } else { + for (k = 0; k < blocks[j].predecessors_count; k++) { + i = cfg->predecessors[blocks[j].predecessor_offset + k]; + while (i != blocks[j].idom) { + zend_ssa_phi *p = ssa_blocks[i].phis; + while (p) { + if (p) { + if (p->pi >= 0) { + if (zend_bitset_in(in + (j * set_size), p->var) && + !zend_bitset_in(gen + (i * set_size), p->var)) { + zend_bitset_incl(tmp, p->var); + } + } else { + zend_bitset_excl(tmp, p->var); + } + } + p = p->next; + } + i = blocks[i].idom; + } + } + } + + if (!zend_bitset_empty(tmp, set_size)) { + i = op_array->last_var + op_array->T; + while (i > 0) { + i--; + if (zend_bitset_in(tmp, i)) { + zend_ssa_phi **pp = &ssa_blocks[j].phis; + while (*pp) { + if ((*pp)->pi <= 0 && (*pp)->var == i) { + break; + } + pp = &(*pp)->next; + } + if (*pp == NULL) { + zend_ssa_phi *phi = zend_arena_calloc(arena, 1, + sizeof(zend_ssa_phi) + + sizeof(int) * blocks[j].predecessors_count + + sizeof(void*) * blocks[j].predecessors_count); + + if (!phi) + return FAILURE; + phi->sources = (int*)(((char*)phi) + sizeof(zend_ssa_phi)); + memset(phi->sources, 0xff, sizeof(int) * blocks[j].predecessors_count); + phi->use_chains = (zend_ssa_phi**)(((char*)phi->sources) + sizeof(int) * cfg->blocks[j].predecessors_count); + + phi->pi = -1; + phi->var = i; + phi->ssa_var = -1; + phi->next = NULL; + *pp = phi; + } + } + } + } + } + } + +//???D if (ZCG(accel_directives).jit_debug & JIT_DEBUG_DUMP_PHI) { +//???D zend_jit_dump(op_array, JIT_DUMP_PHI_PLACEMENT); +//???D } + + /* SSA construction, Step 3: Renaming */ + ssa->ops = zend_arena_calloc(arena, op_array->last, sizeof(zend_ssa_op)); + memset(ssa->ops, 0xff, op_array->last * sizeof(zend_ssa_op)); + memset(var, 0xff, (op_array->last_var + op_array->T) * sizeof(int)); + /* Create uninitialized SSA variables for each CV */ + for (j = 0; j < op_array->last_var; j++) { + var[j] = j; + } + ssa->vars_count = op_array->last_var; + if (zend_ssa_rename(op_array, cfg, ssa, var, 0) != SUCCESS) { + return FAILURE; + } + + return SUCCESS; +} +/* }}} */ + +/* + * Local variables: + * tab-width: 4 + * c-basic-offset: 4 + * indent-tabs-mode: t + * End: + */ diff --git a/ext/opcache/Optimizer/zend_ssa.h b/ext/opcache/Optimizer/zend_ssa.h new file mode 100644 index 0000000000..1e248e8597 --- /dev/null +++ b/ext/opcache/Optimizer/zend_ssa.h @@ -0,0 +1,116 @@ +/* + +----------------------------------------------------------------------+ + | Zend Engine, SSA - Static Single Assignment Form | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2015 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 | + +----------------------------------------------------------------------+ +*/ + +#ifndef ZEND_SSA_H +#define ZEND_SSA_H + +#include "zend_cfg.h" + +typedef struct _zend_ssa_range { + zend_long min; + zend_long max; + zend_bool underflow; + zend_bool overflow; +} zend_ssa_range; + +typedef enum _zend_ssa_negative_lat { + NEG_NONE = 0, + NEG_INIT = 1, + NEG_INVARIANT = 2, + NEG_USE_LT = 3, + NEG_USE_GT = 4, + NEG_UNKNOWN = 5 +} zend_ssa_negative_lat; + +/* Special kind of SSA Phi function used in eSSA */ +typedef struct _zend_ssa_pi_range { + zend_ssa_range range; /* simple range constraint */ + int min_var; + int max_var; + int min_ssa_var; /* ((min_var>0) ? MIN(ssa_var) : 0) + range.min */ + int max_ssa_var; /* ((man_var>0) ? MAX(ssa_var) : 0) + range.man */ + zend_ssa_negative_lat negative; +} zend_ssa_pi_range; + +/* SSA Phi - ssa_var = Phi(source0, source1, ...sourceN) */ +typedef struct _zend_ssa_phi zend_ssa_phi; +struct _zend_ssa_phi { + zend_ssa_phi *next; /* next Phi in the same BB */ + int pi; /* if >= 0 this is actually a e-SSA Pi */ + zend_ssa_pi_range constraint; /* e-SSA Pi constraint */ + int var; /* Original CV, VAR or TMP variable index */ + int ssa_var; /* SSA variable index */ + int block; /* current BB index */ + int visited; /* flag to avoid recursive processing */ + zend_ssa_phi **use_chains; + zend_ssa_phi *sym_use_chain; + int *sources; /* Array of SSA IDs that produce this var. + As many as this block has + predecessors. */ +}; + +typedef struct _zend_ssa_block { + zend_ssa_phi *phis; +} zend_ssa_block; + +typedef struct _zend_ssa_op { + int op1_use; + int op2_use; + int result_use; + int op1_def; + int op2_def; + int result_def; + int op1_use_chain; + int op2_use_chain; + int res_use_chain; +} zend_ssa_op; + +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 */ + int definition; /* opcode that defines this value */ + zend_ssa_phi *definition_phi; /* phi that defines this value */ + int use_chain; /* uses of this value, linked through opN_use_chain */ + zend_ssa_phi *phi_use_chain; /* uses of this value in Phi, linked through use_chain */ + zend_ssa_phi *sym_use_chain; /* uses of this value in Pi constaints */ + unsigned int no_val : 1; /* value doesn't mater (used as op1 in ZEND_ASSIGN) */ + unsigned int scc_entry : 1; +} zend_ssa_var; + +typedef struct _zend_ssa { + int vars_count; /* number of SSA variables */ + zend_ssa_block *blocks; /* array of SSA blocks */ + zend_ssa_op *ops; /* array of SSA instructions */ + zend_ssa_var *vars; /* use/def chain of SSA variables */ +} zend_ssa; + +BEGIN_EXTERN_C() + +int zend_build_ssa(zend_arena **arena, zend_op_array *op_array, zend_cfg *cfg, int rt_constants, zend_ssa *ssa, uint32_t *func_flags); + +END_EXTERN_C() + +#endif /* ZEND_SSA_H */ + +/* + * Local variables: + * tab-width: 4 + * c-basic-offset: 4 + * indent-tabs-mode: t + * End: + */ diff --git a/ext/opcache/Optimizer/zend_worklist.h b/ext/opcache/Optimizer/zend_worklist.h new file mode 100644 index 0000000000..13aab4fb8f --- /dev/null +++ b/ext/opcache/Optimizer/zend_worklist.h @@ -0,0 +1,129 @@ +/* + +----------------------------------------------------------------------+ + | Zend OPcache JIT | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2014 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: Andy Wingo | + +----------------------------------------------------------------------+ +*/ + +/* $Id:$ */ + +#ifndef _ZEND_WORKLIST_H_ +#define _ZEND_WORKLIST_H_ + +#include "zend_arena.h" +#include "zend_bitset.h" + +typedef struct _zend_worklist_stack { + int *buf; + int len; + int capacity; +} zend_worklist_stack; + +#define ZEND_WORKLIST_STACK_ALLOCA(s, _len) do { \ + (s)->buf = (int*)alloca(sizeof(int) * _len); \ + (s)->len = 0; \ + (s)->capacity = _len; \ + } while (0) + +static inline int zend_worklist_stack_prepare(zend_arena **arena, zend_worklist_stack *stack, int len) +{ + ZEND_ASSERT(len >= 0); + + stack->buf = (int*)zend_arena_calloc(arena, sizeof(*stack->buf), len); + if (!stack->buf) { + return FAILURE; + } + stack->len = 0; + stack->capacity = len; + + return SUCCESS; +} + +static inline void zend_worklist_stack_push(zend_worklist_stack *stack, int i) +{ + ZEND_ASSERT(stack->len < stack->capacity); + stack->buf[stack->len++] = i; +} + +static inline int zend_worklist_stack_peek(zend_worklist_stack *stack) +{ + ZEND_ASSERT(stack->len); + return stack->buf[stack->len - 1]; +} + +static inline int zend_worklist_stack_pop(zend_worklist_stack *stack) +{ + ZEND_ASSERT(stack->len); + return stack->buf[--stack->len]; +} + +typedef struct _zend_worklist { + zend_bitset visited; + zend_worklist_stack stack; +} zend_worklist; + +#define ZEND_WORKLIST_ALLOCA(w, _len) do { \ + (w)->visited = (zend_bitset)alloca(sizeof(zend_ulong) * zend_bitset_len(_len)); \ + memset((w)->visited, 0, sizeof(zend_ulong) * zend_bitset_len(_len)); \ + ZEND_WORKLIST_STACK_ALLOCA(&(w)->stack, _len); \ + } while (0) + +static inline int zend_worklist_prepare(zend_arena **arena, zend_worklist *worklist, int len) +{ + ZEND_ASSERT(len >= 0); + worklist->visited = (zend_bitset)zend_arena_calloc(arena, sizeof(zend_ulong), zend_bitset_len(len)); + if (!worklist->visited) { + return FAILURE; + } + return zend_worklist_stack_prepare(arena, &worklist->stack, len); +} + +static inline int zend_worklist_len(zend_worklist *worklist) +{ + return worklist->stack.len; +} + +static inline int zend_worklist_push(zend_worklist *worklist, int i) +{ + ZEND_ASSERT(i >= 0 && i < worklist->stack.capacity); + + if (zend_bitset_in(worklist->visited, i)) { + return 0; + } + + zend_bitset_incl(worklist->visited, i); + zend_worklist_stack_push(&worklist->stack, i); + return 1; +} + +static inline int zend_worklist_peek(zend_worklist *worklist) +{ + return zend_worklist_stack_peek(&worklist->stack); +} + +static inline int zend_worklist_pop(zend_worklist *worklist) +{ + /* Does not clear visited flag */ + return zend_worklist_stack_pop(&worklist->stack); +} + +#endif /* _ZEND_WORKLIST_H_ */ + +/* + * Local variables: + * tab-width: 4 + * c-basic-offset: 4 + * indent-tabs-mode: t + * End: + */ diff --git a/ext/opcache/config.m4 b/ext/opcache/config.m4 index b2d733a1e3..9c73b3bc61 100644 --- a/ext/opcache/config.m4 +++ b/ext/opcache/config.m4 @@ -404,6 +404,9 @@ fi Optimizer/nop_removal.c \ Optimizer/compact_literals.c \ Optimizer/zend_cfg.c \ + Optimizer/zend_dfg.c \ + Optimizer/dfa_pass.c \ + Optimizer/zend_ssa.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 7354a6ee6d..38cfb64be2 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_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_dump.c", "opcache", "OptimizerObj"); ADD_FLAG('CFLAGS_OPCACHE', "/I " + configure_module_dirname); -- 2.40.0