PHP  
 PHP: Test and Code Coverage Analysis
downloads | QA | documentation | faq | getting help | mailing lists | reporting bugs | php.net sites | links | my php.net 
 

LCOV - code coverage report
Current view: top level - ext/opcache/Optimizer - zend_cfg.c (source / functions) Hit Total Coverage
Test: PHP Code Coverage Lines: 403 463 87.0 %
Date: 2017-10-15 Functions: 13 13 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*
       2             :    +----------------------------------------------------------------------+
       3             :    | Zend Engine, CFG - Control Flow Graph                                |
       4             :    +----------------------------------------------------------------------+
       5             :    | Copyright (c) 1998-2017 The PHP Group                                |
       6             :    +----------------------------------------------------------------------+
       7             :    | This source file is subject to version 3.01 of the PHP license,      |
       8             :    | that is bundled with this package in the file LICENSE, and is        |
       9             :    | available through the world-wide-web at the following url:           |
      10             :    | http://www.php.net/license/3_01.txt                                  |
      11             :    | If you did not receive a copy of the PHP license and are unable to   |
      12             :    | obtain it through the world-wide-web, please send a note to          |
      13             :    | license@php.net so we can mail you a copy immediately.               |
      14             :    +----------------------------------------------------------------------+
      15             :    | Authors: Dmitry Stogov <dmitry@zend.com>                             |
      16             :    +----------------------------------------------------------------------+
      17             : */
      18             : 
      19             : #include "php.h"
      20             : #include "zend_compile.h"
      21             : #include "zend_cfg.h"
      22             : #include "zend_func_info.h"
      23             : #include "zend_worklist.h"
      24             : #include "zend_optimizer.h"
      25             : #include "zend_optimizer_internal.h"
      26             : 
      27        4737 : static void zend_mark_reachable(zend_op *opcodes, zend_cfg *cfg, zend_basic_block *b) /* {{{ */
      28             : {
      29             :         zend_uchar opcode;
      30             :         zend_basic_block *b0;
      31             :         int successor_0, successor_1;
      32        4737 :         zend_basic_block *blocks = cfg->blocks;
      33             : 
      34             :         while (1) {
      35        8192 :                 b->flags |= ZEND_BB_REACHABLE;
      36        8192 :                 successor_0 = b->successors[0];
      37        8192 :                 if (successor_0 >= 0) {
      38        4023 :                         successor_1 = b->successors[1];
      39        4023 :                         if (successor_1 >= 0) {
      40        1425 :                                 b0 = blocks + successor_0;
      41        1425 :                                 b0->flags |= ZEND_BB_TARGET;
      42        1425 :                                 if (!(b0->flags & ZEND_BB_REACHABLE)) {
      43        1057 :                                         zend_mark_reachable(opcodes, cfg, b0);
      44             :                                 }
      45             : 
      46             :                                 ZEND_ASSERT(b->len != 0);
      47        1425 :                                 opcode = opcodes[b->start + b->len - 1].opcode;
      48        1425 :                                 b = blocks + successor_1;
      49        1425 :                                 if (opcode == ZEND_JMPZNZ) {
      50          42 :                                         b->flags |= ZEND_BB_TARGET;
      51             :                                 } else {
      52        1383 :                                         b->flags |= ZEND_BB_FOLLOW;
      53             :                                 }
      54        2598 :                         } else if (b->len != 0) {
      55        2355 :                                 opcode = opcodes[b->start + b->len - 1].opcode;
      56        2355 :                                 b = blocks + successor_0;
      57        2355 :                                 if (opcode == ZEND_JMP) {
      58         492 :                                         b->flags |= ZEND_BB_TARGET;
      59             :                                 } else {
      60        1863 :                                         b->flags |= ZEND_BB_FOLLOW;
      61             : 
      62        1863 :                                         if (cfg->split_at_calls) {
      63           0 :                                                 if (opcode == ZEND_INCLUDE_OR_EVAL ||
      64             :                                                     opcode == ZEND_GENERATOR_CREATE ||
      65             :                                                     opcode == ZEND_YIELD ||
      66             :                                                     opcode == ZEND_YIELD_FROM ||
      67             :                                                     opcode == ZEND_DO_FCALL ||
      68             :                                                     opcode == ZEND_DO_UCALL ||
      69             :                                                     opcode == ZEND_DO_FCALL_BY_NAME) {
      70           0 :                                                         b->flags |= ZEND_BB_ENTRY;
      71             :                                                 }
      72             :                                         }
      73        1863 :                                         if (cfg->split_at_recv) {
      74           0 :                                                 if (opcode == ZEND_RECV ||
      75             :                                                     opcode == ZEND_RECV_INIT) {
      76           0 :                                                         b->flags |= ZEND_BB_RECV_ENTRY;
      77             :                                                 }
      78             :                                         }
      79             :                                 }
      80             :                         } else {
      81         243 :                                 b = blocks + successor_0;
      82         243 :                                 b->flags |= ZEND_BB_FOLLOW;
      83             :                         }
      84        4023 :                         if (b->flags & ZEND_BB_REACHABLE) return;
      85             :                 } else {
      86        4169 :                         b->flags |= ZEND_BB_EXIT;
      87        4169 :                         return;
      88             :                 }
      89        3455 :         }
      90             : }
      91             : /* }}} */
      92             : 
      93        3616 : static void zend_mark_reachable_blocks(const zend_op_array *op_array, zend_cfg *cfg, int start) /* {{{ */
      94             : {
      95        3616 :         zend_basic_block *blocks = cfg->blocks;
      96             : 
      97        3616 :         blocks[start].flags = ZEND_BB_START;
      98        3616 :         zend_mark_reachable(op_array->opcodes, cfg, blocks + start);
      99             : 
     100        3616 :         if (op_array->last_live_range || op_array->last_try_catch) {
     101             :                 zend_basic_block *b;
     102             :                 int j, changed;
     103         511 :                 uint32_t *block_map = cfg->map;
     104             : 
     105             :                 do {
     106         563 :                         changed = 0;
     107             : 
     108             :                         /* Add live range paths */
     109        1648 :                         for (j = 0; j < op_array->last_live_range; j++) {
     110        1085 :                                 zend_live_range *live_range = &op_array->live_range[j];
     111        1085 :                                 if (live_range->var == (uint32_t)-1) {
     112             :                                         /* this live range already removed */
     113           0 :                                         continue;
     114             :                                 }
     115        1085 :                                 b = blocks + block_map[live_range->start];
     116        1085 :                                 if (b->flags & ZEND_BB_REACHABLE) {
     117        2108 :                                         while (b->len > 0 && op_array->opcodes[b->start].opcode == ZEND_NOP) {
     118             :                                             /* check if NOP breaks incorrect smart branch */
     119          28 :                                                 if (b->len == 2
     120          28 :                                                  && (op_array->opcodes[b->start + 1].opcode == ZEND_JMPZ
     121           0 :                                                   || op_array->opcodes[b->start + 1].opcode == ZEND_JMPNZ)
     122           0 :                                                  && (op_array->opcodes[b->start + 1].op1_type & (IS_CV|IS_CONST))
     123             :                                                  && b->start > 0
     124           0 :                                                  && zend_is_smart_branch(op_array->opcodes + b->start - 1)) {
     125           0 :                                                         break;
     126             :                                                 }
     127          28 :                                                 b->start++;
     128          28 :                                                 b->len--;
     129             :                                         }
     130        1040 :                                         if (b->len == 0 && (uint32_t)b->successors[0] == block_map[live_range->end]) {
     131             :                                                 /* mark as removed (empty live range) */
     132           0 :                                                 live_range->var = (uint32_t)-1;
     133           0 :                                                 continue;
     134             :                                         }
     135        1040 :                                         b->flags |= ZEND_BB_GEN_VAR;
     136        1040 :                                         b = blocks + block_map[live_range->end];
     137        1040 :                                         b->flags |= ZEND_BB_KILL_VAR;
     138        1040 :                                         if (!(b->flags & (ZEND_BB_REACHABLE|ZEND_BB_UNREACHABLE_FREE))) {
     139           0 :                                                 if (cfg->split_at_live_ranges) {
     140           0 :                                                         changed = 1;
     141           0 :                                                         zend_mark_reachable(op_array->opcodes, cfg, b);
     142             :                                                 } else {
     143             :                                                         ZEND_ASSERT(b->start == live_range->end);
     144           0 :                                                         b->flags |= ZEND_BB_UNREACHABLE_FREE;
     145             :                                                 }
     146             :                                         }
     147             :                                 } else {
     148             :                                         ZEND_ASSERT(!(blocks[block_map[live_range->end]].flags & ZEND_BB_REACHABLE));
     149             :                                 }
     150             :                         }
     151             : 
     152             :                         /* Add exception paths */
     153         711 :                         for (j = 0; j < op_array->last_try_catch; j++) {
     154             : 
     155             :                                 /* check for jumps into the middle of try block */
     156         148 :                                 b = blocks + block_map[op_array->try_catch_array[j].try_op];
     157         148 :                                 if (!(b->flags & ZEND_BB_REACHABLE)) {
     158             :                                         zend_basic_block *end;
     159             : 
     160          16 :                                         if (op_array->try_catch_array[j].catch_op) {
     161          16 :                                                 end = blocks + block_map[op_array->try_catch_array[j].catch_op];
     162          48 :                                                 while (b != end) {
     163          16 :                                                         if (b->flags & ZEND_BB_REACHABLE) {
     164           0 :                                                                 op_array->try_catch_array[j].try_op = b->start;
     165           0 :                                                                 break;
     166             :                                                         }
     167          16 :                                                         b++;
     168             :                                                 }
     169             :                                         }
     170          16 :                                         b = blocks + block_map[op_array->try_catch_array[j].try_op];
     171          16 :                                         if (!(b->flags & ZEND_BB_REACHABLE)) {
     172          16 :                                                 if (op_array->try_catch_array[j].finally_op) {
     173           0 :                                                         end = blocks + block_map[op_array->try_catch_array[j].finally_op];
     174           0 :                                                         while (b != end) {
     175           0 :                                                                 if (b->flags & ZEND_BB_REACHABLE) {
     176           0 :                                                                         op_array->try_catch_array[j].try_op = op_array->try_catch_array[j].catch_op;
     177           0 :                                                                         changed = 1;
     178           0 :                                                                         zend_mark_reachable(op_array->opcodes, cfg, blocks + block_map[op_array->try_catch_array[j].try_op]);
     179           0 :                                                                         break;
     180             :                                                                 }
     181           0 :                                                                 b++;
     182             :                                                         }
     183             :                                                 }
     184             :                                         }
     185             :                                 }
     186             : 
     187         148 :                                 b = blocks + block_map[op_array->try_catch_array[j].try_op];
     188         148 :                                 if (b->flags & ZEND_BB_REACHABLE) {
     189         132 :                                         b->flags |= ZEND_BB_TRY;
     190         132 :                                         if (op_array->try_catch_array[j].catch_op) {
     191         128 :                                                 b = blocks + block_map[op_array->try_catch_array[j].catch_op];
     192         128 :                                                 b->flags |= ZEND_BB_CATCH;
     193         128 :                                                 if (!(b->flags & ZEND_BB_REACHABLE)) {
     194          64 :                                                         changed = 1;
     195          64 :                                                         zend_mark_reachable(op_array->opcodes, cfg, b);
     196             :                                                 }
     197             :                                         }
     198         132 :                                         if (op_array->try_catch_array[j].finally_op) {
     199           4 :                                                 b = blocks + block_map[op_array->try_catch_array[j].finally_op];
     200           4 :                                                 b->flags |= ZEND_BB_FINALLY;
     201           4 :                                                 if (!(b->flags & ZEND_BB_REACHABLE)) {
     202           0 :                                                         changed = 1;
     203           0 :                                                         zend_mark_reachable(op_array->opcodes, cfg, b);
     204             :                                                 }
     205             :                                         }
     206         132 :                                         if (op_array->try_catch_array[j].finally_end) {
     207           4 :                                                 b = blocks + block_map[op_array->try_catch_array[j].finally_end];
     208           4 :                                                 b->flags |= ZEND_BB_FINALLY_END;
     209           4 :                                                 if (!(b->flags & ZEND_BB_REACHABLE)) {
     210           0 :                                                         changed = 1;
     211           0 :                                                         zend_mark_reachable(op_array->opcodes, cfg, b);
     212             :                                                 }
     213             :                                         }
     214             :                                 } else {
     215          16 :                                         if (op_array->try_catch_array[j].catch_op) {
     216             :                                                 ZEND_ASSERT(!(blocks[block_map[op_array->try_catch_array[j].catch_op]].flags & ZEND_BB_REACHABLE));
     217             :                                         }
     218          16 :                                         if (op_array->try_catch_array[j].finally_op) {
     219             :                                                 ZEND_ASSERT(!(blocks[block_map[op_array->try_catch_array[j].finally_op]].flags & ZEND_BB_REACHABLE));
     220             :                                         }
     221          16 :                                         if (op_array->try_catch_array[j].finally_end) {
     222             :                                                 ZEND_ASSERT(!(blocks[block_map[op_array->try_catch_array[j].finally_end]].flags & ZEND_BB_REACHABLE));
     223             :                                         }
     224             :                                 }
     225             :                         }
     226         563 :                 } while (changed);
     227             :         }
     228        3616 : }
     229             : /* }}} */
     230             : 
     231        2178 : void zend_cfg_remark_reachable_blocks(const zend_op_array *op_array, zend_cfg *cfg) /* {{{ */
     232             : {
     233        2178 :         zend_basic_block *blocks = cfg->blocks;
     234             :         int i;
     235        2178 :         int start = 0;
     236             : 
     237        2178 :         for (i = 0; i < cfg->blocks_count; i++) {
     238        2178 :                 if (blocks[i].flags & ZEND_BB_REACHABLE) {
     239        2178 :                         start = i;
     240        2178 :                         i++;
     241        2178 :                         break;
     242             :                 }
     243             :         }
     244             : 
     245             :         /* clear all flags */
     246        9126 :         for (i = 0; i < cfg->blocks_count; i++) {
     247        6948 :                 blocks[i].flags = 0;
     248             :         }
     249             : 
     250        2178 :         zend_mark_reachable_blocks(op_array, cfg, start);
     251        2178 : }
     252             : /* }}} */
     253             : 
     254        2159 : static void record_successor(zend_basic_block *blocks, int pred, int n, int succ)
     255             : {
     256        2159 :         blocks[pred].successors[n] = succ;
     257        2159 : }
     258             : 
     259        3499 : static void initialize_block(zend_basic_block *block) {
     260        3499 :         block->flags = 0;
     261        3499 :         block->successors[0] = -1;
     262        3499 :         block->successors[1] = -1;
     263        3499 :         block->predecessors_count = 0;
     264        3499 :         block->predecessor_offset = -1;
     265        3499 :         block->idom = -1;
     266        3499 :         block->loop_header = -1;
     267        3499 :         block->level = -1;
     268        3499 :         block->children = -1;
     269        3499 :         block->next_child = -1;
     270        3499 : }
     271             : 
     272             : #define BB_START(i) do { \
     273             :                 if (!block_map[i]) { blocks_count++;} \
     274             :                 block_map[i]++; \
     275             :         } while (0)
     276             : 
     277        1438 : int zend_build_cfg(zend_arena **arena, const zend_op_array *op_array, uint32_t build_flags, zend_cfg *cfg, uint32_t *func_flags) /* {{{ */
     278             : {
     279        1438 :         uint32_t flags = 0;
     280             :         uint32_t i;
     281             :         int j;
     282             :         uint32_t *block_map;
     283             :         zend_function *fn;
     284        1438 :         int blocks_count = 0;
     285             :         zend_basic_block *blocks;
     286             :         zval *zv;
     287        1438 :         zend_bool extra_entry_block = 0;
     288             : 
     289        1438 :         cfg->split_at_live_ranges = (build_flags & ZEND_CFG_SPLIT_AT_LIVE_RANGES) != 0;
     290        1438 :         cfg->split_at_calls = (build_flags & ZEND_CFG_STACKLESS) != 0;
     291        1438 :         cfg->split_at_recv = (build_flags & ZEND_CFG_RECV_ENTRY) != 0 && (op_array->fn_flags & ZEND_ACC_HAS_TYPE_HINTS) == 0;
     292             : 
     293        2876 :         cfg->map = block_map = zend_arena_calloc(arena, op_array->last, sizeof(uint32_t));
     294        1438 :         if (!block_map) {
     295           0 :                 return FAILURE;
     296             :         }
     297             : 
     298             :         /* Build CFG, Step 1: Find basic blocks starts, calculate number of blocks */
     299        1438 :         BB_START(0);
     300       19714 :         for (i = 0; i < op_array->last; i++) {
     301       18276 :                 zend_op *opline = op_array->opcodes + i;
     302       18276 :                 switch(opline->opcode) {
     303             :                         case ZEND_RECV:
     304             :                         case ZEND_RECV_INIT:
     305         115 :                                 if (build_flags & ZEND_CFG_RECV_ENTRY) {
     306           0 :                                         BB_START(i + 1);
     307             :                                 }
     308         115 :                                 break;
     309             :                         case ZEND_RETURN:
     310             :                         case ZEND_RETURN_BY_REF:
     311             :                         case ZEND_GENERATOR_RETURN:
     312             :                         case ZEND_EXIT:
     313             :                         case ZEND_THROW:
     314        1940 :                                 if (i + 1 < op_array->last) {
     315         502 :                                         BB_START(i + 1);
     316             :                                 }
     317        1940 :                                 break;
     318             :                         case ZEND_INCLUDE_OR_EVAL:
     319         240 :                                 flags |= ZEND_FUNC_INDIRECT_VAR_ACCESS;
     320             :                         case ZEND_GENERATOR_CREATE:
     321             :                         case ZEND_YIELD:
     322             :                         case ZEND_YIELD_FROM:
     323         240 :                                 if (build_flags & ZEND_CFG_STACKLESS) {
     324           0 :                                         BB_START(i + 1);
     325             :                                 }
     326         240 :                                 break;
     327             :                         case ZEND_DO_FCALL:
     328             :                         case ZEND_DO_UCALL:
     329             :                         case ZEND_DO_FCALL_BY_NAME:
     330         520 :                                 flags |= ZEND_FUNC_HAS_CALLS;
     331         520 :                                 if (build_flags & ZEND_CFG_STACKLESS) {
     332           0 :                                         BB_START(i + 1);
     333             :                                 }
     334         520 :                                 break;
     335             :                         case ZEND_DO_ICALL:
     336        2255 :                                 flags |= ZEND_FUNC_HAS_CALLS;
     337        2255 :                                 break;
     338             :                         case ZEND_INIT_FCALL:
     339             :                         case ZEND_INIT_NS_FCALL_BY_NAME:
     340        2326 :                                 zv = CRT_CONSTANT(opline->op2);
     341        2326 :                                 if (opline->opcode == ZEND_INIT_NS_FCALL_BY_NAME) {
     342             :                                         /* The third literal is the lowercased unqualified name */
     343           4 :                                         zv += 2;
     344             :                                 }
     345        4652 :                                 if ((fn = zend_hash_find_ptr(EG(function_table), Z_STR_P(zv))) != NULL) {
     346        2259 :                                         if (fn->type == ZEND_INTERNAL_FUNCTION) {
     347        2259 :                                                 flags |= zend_optimizer_classify_function(
     348             :                                                         Z_STR_P(zv), opline->extended_value);
     349             :                                         }
     350             :                                 }
     351        2326 :                                 break;
     352             :                         case ZEND_FAST_CALL:
     353           2 :                                 BB_START(OP_JMP_ADDR(opline, opline->op1) - op_array->opcodes);
     354           2 :                                 BB_START(i + 1);
     355           2 :                                 break;
     356             :                         case ZEND_FAST_RET:
     357           1 :                                 if (i + 1 < op_array->last) {
     358           1 :                                         BB_START(i + 1);
     359             :                                 }
     360           1 :                                 break;
     361             :                         case ZEND_JMP:
     362         365 :                                 BB_START(OP_JMP_ADDR(opline, opline->op1) - op_array->opcodes);
     363         365 :                                 if (i + 1 < op_array->last) {
     364         365 :                                         BB_START(i + 1);
     365             :                                 }
     366         365 :                                 break;
     367             :                         case ZEND_JMPZNZ:
     368          22 :                                 BB_START(OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes);
     369          22 :                                 BB_START(ZEND_OFFSET_TO_OPLINE_NUM(op_array, opline, opline->extended_value));
     370          22 :                                 if (i + 1 < op_array->last) {
     371          22 :                                         BB_START(i + 1);
     372             :                                 }
     373          22 :                                 break;
     374             :                         case ZEND_JMPZ:
     375             :                         case ZEND_JMPNZ:
     376             :                         case ZEND_JMPZ_EX:
     377             :                         case ZEND_JMPNZ_EX:
     378             :                         case ZEND_JMP_SET:
     379             :                         case ZEND_COALESCE:
     380             :                         case ZEND_ASSERT_CHECK:
     381         555 :                                 BB_START(OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes);
     382         555 :                                 BB_START(i + 1);
     383         555 :                                 break;
     384             :                         case ZEND_CATCH:
     385          18 :                                 if (!opline->result.num) {
     386           0 :                                         BB_START(ZEND_OFFSET_TO_OPLINE_NUM(op_array, opline, opline->extended_value));
     387             :                                 }
     388          18 :                                 BB_START(i + 1);
     389          18 :                                 break;
     390             :                         case ZEND_DECLARE_ANON_CLASS:
     391             :                         case ZEND_DECLARE_ANON_INHERITED_CLASS:
     392             :                         case ZEND_FE_FETCH_R:
     393             :                         case ZEND_FE_FETCH_RW:
     394          12 :                                 BB_START(ZEND_OFFSET_TO_OPLINE_NUM(op_array, opline, opline->extended_value));
     395          12 :                                 BB_START(i + 1);
     396          12 :                                 break;
     397             :                         case ZEND_FE_RESET_R:
     398             :                         case ZEND_FE_RESET_RW:
     399          10 :                                 BB_START(OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes);
     400          10 :                                 BB_START(i + 1);
     401          10 :                                 break;
     402             :                         case ZEND_UNSET_VAR:
     403             :                         case ZEND_ISSET_ISEMPTY_VAR:
     404          12 :                                 if (((opline->extended_value & ZEND_FETCH_TYPE_MASK) == ZEND_FETCH_LOCAL) &&
     405           6 :                                     !(opline->extended_value & ZEND_QUICK_SET)) {
     406           0 :                                         flags |= ZEND_FUNC_INDIRECT_VAR_ACCESS;
     407          12 :                                 } else if (((opline->extended_value & ZEND_FETCH_TYPE_MASK) == ZEND_FETCH_GLOBAL ||
     408           6 :                                             (opline->extended_value & ZEND_FETCH_TYPE_MASK) == ZEND_FETCH_GLOBAL_LOCK) &&
     409           0 :                                            !op_array->function_name) {
     410           0 :                                         flags |= ZEND_FUNC_INDIRECT_VAR_ACCESS;
     411             :                                 }
     412           6 :                                 break;
     413             :                         case ZEND_FETCH_R:
     414             :                         case ZEND_FETCH_W:
     415             :                         case ZEND_FETCH_RW:
     416             :                         case ZEND_FETCH_FUNC_ARG:
     417             :                         case ZEND_FETCH_IS:
     418             :                         case ZEND_FETCH_UNSET:
     419         782 :                                 if ((opline->extended_value & ZEND_FETCH_TYPE_MASK) == ZEND_FETCH_LOCAL) {
     420           0 :                                         flags |= ZEND_FUNC_INDIRECT_VAR_ACCESS;
     421        1564 :                                 } else if (((opline->extended_value & ZEND_FETCH_TYPE_MASK) == ZEND_FETCH_GLOBAL ||
     422           0 :                                             (opline->extended_value & ZEND_FETCH_TYPE_MASK) == ZEND_FETCH_GLOBAL_LOCK) &&
     423         782 :                                            !op_array->function_name) {
     424         782 :                                         flags |= ZEND_FUNC_INDIRECT_VAR_ACCESS;
     425             :                                 }
     426             :                                 break;
     427             :                 }
     428             :         }
     429             : 
     430             :         /* If the entry block has predecessors, we may need to split it */
     431        2862 :         if ((build_flags & ZEND_CFG_NO_ENTRY_PREDECESSORS)
     432        1424 :                         && op_array->last > 0 && block_map[0] > 1) {
     433           0 :                 extra_entry_block = 1;
     434             :         }
     435             : 
     436        1438 :         if (cfg->split_at_live_ranges) {
     437         947 :                 for (j = 0; j < op_array->last_live_range; j++) {
     438         221 :                         BB_START(op_array->live_range[j].start);
     439         221 :                         BB_START(op_array->live_range[j].end);
     440             :                 }
     441             :         }
     442             : 
     443        1438 :         if (op_array->last_try_catch) {
     444          33 :                 for (j = 0; j < op_array->last_try_catch; j++) {
     445          19 :                         BB_START(op_array->try_catch_array[j].try_op);
     446          19 :                         if (op_array->try_catch_array[j].catch_op) {
     447          18 :                                 BB_START(op_array->try_catch_array[j].catch_op);
     448             :                         }
     449          19 :                         if (op_array->try_catch_array[j].finally_op) {
     450           1 :                                 BB_START(op_array->try_catch_array[j].finally_op);
     451             :                         }
     452          19 :                         if (op_array->try_catch_array[j].finally_end) {
     453           1 :                                 BB_START(op_array->try_catch_array[j].finally_end);
     454             :                         }
     455             :                 }
     456             :         }
     457             : 
     458        1438 :         blocks_count += extra_entry_block;
     459        1438 :         cfg->blocks_count = blocks_count;
     460             : 
     461             :         /* Build CFG, Step 2: Build Array of Basic Blocks */
     462        2876 :         cfg->blocks = blocks = zend_arena_calloc(arena, sizeof(zend_basic_block), blocks_count);
     463        1438 :         if (!blocks) {
     464           0 :                 return FAILURE;
     465             :         }
     466             : 
     467        1438 :         blocks_count = -1;
     468             : 
     469        1438 :         if (extra_entry_block) {
     470           0 :                 initialize_block(&blocks[0]);
     471           0 :                 blocks[0].start = 0;
     472           0 :                 blocks[0].len = 0;
     473           0 :                 blocks_count++;
     474             :         }
     475             : 
     476       19714 :         for (i = 0; i < op_array->last; i++) {
     477       18276 :                 if (block_map[i]) {
     478        3499 :                         if (blocks_count >= 0) {
     479        2061 :                                 blocks[blocks_count].len = i - blocks[blocks_count].start;
     480             :                         }
     481        3499 :                         blocks_count++;
     482        3499 :                         initialize_block(&blocks[blocks_count]);
     483        3499 :                         blocks[blocks_count].start = i;
     484             :                 }
     485       18276 :                 block_map[i] = blocks_count;
     486             :         }
     487             : 
     488        1438 :         blocks[blocks_count].len = i - blocks[blocks_count].start;
     489        1438 :         blocks_count++;
     490             : 
     491             :         /* Build CFG, Step 3: Calculate successors */
     492        4937 :         for (j = 0; j < blocks_count; j++) {
     493             :                 zend_op *opline;
     494        3499 :                 if (blocks[j].len == 0) {
     495           0 :                         record_successor(blocks, j, 0, j + 1);
     496           0 :                         continue;
     497             :                 }
     498             : 
     499        3499 :                 opline = op_array->opcodes + blocks[j].start + blocks[j].len - 1;
     500        3499 :                 switch (opline->opcode) {
     501             :                         case ZEND_FAST_RET:
     502             :                         case ZEND_RETURN:
     503             :                         case ZEND_RETURN_BY_REF:
     504             :                         case ZEND_GENERATOR_RETURN:
     505             :                         case ZEND_EXIT:
     506             :                         case ZEND_THROW:
     507        1941 :                                 break;
     508             :                         case ZEND_JMP:
     509         365 :                                 record_successor(blocks, j, 0, block_map[OP_JMP_ADDR(opline, opline->op1) - op_array->opcodes]);
     510         365 :                                 break;
     511             :                         case ZEND_JMPZNZ:
     512          22 :                                 record_successor(blocks, j, 0, block_map[OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes]);
     513          22 :                                 record_successor(blocks, j, 1, block_map[ZEND_OFFSET_TO_OPLINE_NUM(op_array, opline, opline->extended_value)]);
     514          22 :                                 break;
     515             :                         case ZEND_JMPZ:
     516             :                         case ZEND_JMPNZ:
     517             :                         case ZEND_JMPZ_EX:
     518             :                         case ZEND_JMPNZ_EX:
     519             :                         case ZEND_JMP_SET:
     520             :                         case ZEND_COALESCE:
     521             :                         case ZEND_ASSERT_CHECK:
     522         555 :                                 record_successor(blocks, j, 0, block_map[OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes]);
     523         555 :                                 record_successor(blocks, j, 1, j + 1);
     524         555 :                                 break;
     525             :                         case ZEND_CATCH:
     526          18 :                                 if (!opline->result.num) {
     527           0 :                                         record_successor(blocks, j, 0, block_map[ZEND_OFFSET_TO_OPLINE_NUM(op_array, opline, opline->extended_value)]);
     528           0 :                                         record_successor(blocks, j, 1, j + 1);
     529             :                                 } else {
     530          18 :                                         record_successor(blocks, j, 0, j + 1);
     531             :                                 }
     532          18 :                                 break;
     533             :                         case ZEND_DECLARE_ANON_CLASS:
     534             :                         case ZEND_DECLARE_ANON_INHERITED_CLASS:
     535             :                         case ZEND_FE_FETCH_R:
     536             :                         case ZEND_FE_FETCH_RW:
     537          12 :                                 record_successor(blocks, j, 0, block_map[ZEND_OFFSET_TO_OPLINE_NUM(op_array, opline, opline->extended_value)]);
     538          12 :                                 record_successor(blocks, j, 1, j + 1);
     539          12 :                                 break;
     540             :                         case ZEND_FE_RESET_R:
     541             :                         case ZEND_FE_RESET_RW:
     542          10 :                                 record_successor(blocks, j, 0, block_map[OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes]);
     543          10 :                                 record_successor(blocks, j, 1, j + 1);
     544          10 :                                 break;
     545             :                         case ZEND_FAST_CALL:
     546           2 :                                 record_successor(blocks, j, 0, block_map[OP_JMP_ADDR(opline, opline->op1) - op_array->opcodes]);
     547           2 :                                 record_successor(blocks, j, 1, j + 1);
     548           2 :                                 break;
     549             :                         default:
     550         574 :                                 record_successor(blocks, j, 0, j + 1);
     551             :                                 break;
     552             :                 }
     553             :         }
     554             : 
     555             :         /* Build CFG, Step 4, Mark Reachable Basic Blocks */
     556        1438 :         zend_mark_reachable_blocks(op_array, cfg, 0);
     557             : 
     558        1438 :         if (func_flags) {
     559         712 :                 *func_flags |= flags;
     560             :         }
     561             : 
     562        1438 :         return SUCCESS;
     563             : }
     564             : /* }}} */
     565             : 
     566         437 : int zend_cfg_build_predecessors(zend_arena **arena, zend_cfg *cfg) /* {{{ */
     567             : {
     568             :         int j, edges;
     569             :         zend_basic_block *b;
     570         437 :         zend_basic_block *blocks = cfg->blocks;
     571         437 :         zend_basic_block *end = blocks + cfg->blocks_count;
     572             :         int *predecessors;
     573             : 
     574         437 :         edges = 0;
     575        1227 :         for (b = blocks; b < end; b++) {
     576         790 :                 b->predecessors_count = 0;
     577             :         }
     578        1227 :         for (b = blocks; b < end; b++) {
     579         790 :                 if (!(b->flags & ZEND_BB_REACHABLE)) {
     580           0 :                         b->successors[0] = -1;
     581           0 :                         b->successors[1] = -1;
     582           0 :                         b->predecessors_count = 0;
     583             :                 } else {
     584         790 :                         if (b->successors[0] >= 0) {
     585         279 :                                 edges++;
     586         279 :                                 blocks[b->successors[0]].predecessors_count++;
     587         279 :                                 if (b->successors[1] >= 0 && b->successors[1] != b->successors[0]) {
     588         202 :                                         edges++;
     589         202 :                                         blocks[b->successors[1]].predecessors_count++;
     590             :                                 }
     591             :                         }
     592             :                 }
     593             :         }
     594             : 
     595         874 :         cfg->predecessors = predecessors = (int*)zend_arena_calloc(arena, sizeof(int), edges);
     596             : 
     597         437 :         if (!predecessors) {
     598           0 :                 return FAILURE;
     599             :         }
     600             : 
     601         437 :         edges = 0;
     602        1227 :         for (b = blocks; b < end; b++) {
     603         790 :                 if (b->flags & ZEND_BB_REACHABLE) {
     604         790 :                         b->predecessor_offset = edges;
     605         790 :                         edges += b->predecessors_count;
     606         790 :                         b->predecessors_count = 0;
     607             :                 }
     608             :         }
     609             : 
     610        1227 :         for (j = 0; j < cfg->blocks_count; j++) {
     611         790 :                 if (blocks[j].flags & ZEND_BB_REACHABLE) {
     612         790 :                         if (blocks[j].successors[0] >= 0) {
     613         279 :                                 zend_basic_block *b = blocks + blocks[j].successors[0];
     614         279 :                                 predecessors[b->predecessor_offset + b->predecessors_count] = j;
     615         279 :                                 b->predecessors_count++;
     616         483 :                                 if (blocks[j].successors[1] >= 0
     617         204 :                                                 && blocks[j].successors[1] != blocks[j].successors[0]) {
     618         202 :                                         zend_basic_block *b = blocks + blocks[j].successors[1];
     619         202 :                                         predecessors[b->predecessor_offset + b->predecessors_count] = j;
     620         202 :                                         b->predecessors_count++;
     621             :                                 }
     622             :                         }
     623             :                 }
     624             :         }
     625             : 
     626         437 :         return SUCCESS;
     627             : }
     628             : /* }}} */
     629             : 
     630             : /* Computes a postorder numbering of the CFG */
     631         920 : static void compute_postnum_recursive(
     632             :                 int *postnum, int *cur, const zend_cfg *cfg, int block_num) /* {{{ */
     633             : {
     634         920 :         zend_basic_block *block = &cfg->blocks[block_num];
     635         920 :         if (postnum[block_num] != -1) {
     636         130 :                 return;
     637             :         }
     638             : 
     639         790 :         postnum[block_num] = -2; /* Marker for "currently visiting" */
     640         790 :         if (block->successors[0] >= 0) {
     641         279 :                 compute_postnum_recursive(postnum, cur, cfg, block->successors[0]);
     642         279 :                 if (block->successors[1] >= 0) {
     643         204 :                         compute_postnum_recursive(postnum, cur, cfg, block->successors[1]);
     644             :                 }
     645             :         }
     646         790 :         postnum[block_num] = (*cur)++;
     647             : }
     648             : /* }}} */
     649             : 
     650             : /* Computes dominator tree using algorithm from "A Simple, Fast Dominance Algorithm" by
     651             :  * Cooper, Harvey and Kennedy. */
     652         437 : int zend_cfg_compute_dominators_tree(const zend_op_array *op_array, zend_cfg *cfg) /* {{{ */
     653             : {
     654         437 :         zend_basic_block *blocks = cfg->blocks;
     655         437 :         int blocks_count = cfg->blocks_count;
     656             :         int j, k, changed;
     657             : 
     658             :         ALLOCA_FLAG(use_heap)
     659         437 :         int *postnum = do_alloca(sizeof(int) * cfg->blocks_count, use_heap);
     660         437 :         memset(postnum, -1, sizeof(int) * cfg->blocks_count);
     661         437 :         j = 0;
     662         437 :         compute_postnum_recursive(postnum, &j, cfg, 0);
     663             : 
     664             :         /* FIXME: move declarations */
     665         437 :         blocks[0].idom = 0;
     666             :         do {
     667         517 :                 changed = 0;
     668             :                 /* Iterating in RPO here would converge faster */
     669        1313 :                 for (j = 1; j < blocks_count; j++) {
     670         796 :                         int idom = -1;
     671             : 
     672         796 :                         if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
     673           0 :                                 continue;
     674             :                         }
     675        1887 :                         for (k = 0; k < blocks[j].predecessors_count; k++) {
     676        1091 :                                 int pred = cfg->predecessors[blocks[j].predecessor_offset + k];
     677             : 
     678        1091 :                                 if (idom < 0) {
     679         811 :                                         if (blocks[pred].idom >= 0)
     680         762 :                                                 idom = pred;
     681         811 :                                         continue;
     682             :                                 }
     683             : 
     684         280 :                                 if (blocks[pred].idom >= 0) {
     685         780 :                                         while (idom != pred) {
     686         264 :                                                 while (postnum[pred] < postnum[idom]) pred = blocks[pred].idom;
     687         264 :                                                 while (postnum[idom] < postnum[pred]) idom = blocks[idom].idom;
     688             :                                         }
     689             :                                 }
     690             :                         }
     691             : 
     692         796 :                         if (idom >= 0 && blocks[j].idom != idom) {
     693         353 :                                 blocks[j].idom = idom;
     694         353 :                                 changed = 1;
     695             :                         }
     696             :                 }
     697         517 :         } while (changed);
     698         437 :         blocks[0].idom = -1;
     699             : 
     700         790 :         for (j = 1; j < blocks_count; j++) {
     701         353 :                 if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
     702           0 :                         continue;
     703             :                 }
     704         353 :                 if (blocks[j].idom >= 0) {
     705             :                         /* Sort by block number to traverse children in pre-order */
     706         706 :                         if (blocks[blocks[j].idom].children < 0 ||
     707         137 :                             j < blocks[blocks[j].idom].children) {
     708         216 :                                 blocks[j].next_child = blocks[blocks[j].idom].children;
     709         216 :                                 blocks[blocks[j].idom].children = j;
     710             :                         } else {
     711         137 :                                 int k = blocks[blocks[j].idom].children;
     712         282 :                                 while (blocks[k].next_child >=0 && j > blocks[k].next_child) {
     713           8 :                                         k = blocks[k].next_child;
     714             :                                 }
     715         137 :                                 blocks[j].next_child = blocks[k].next_child;
     716         137 :                                 blocks[k].next_child = j;
     717             :                         }
     718             :                 }
     719             :         }
     720             : 
     721        1227 :         for (j = 0; j < blocks_count; j++) {
     722         790 :                 int idom = blocks[j].idom, level = 0;
     723         790 :                 if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
     724           0 :                         continue;
     725             :                 }
     726        1593 :                 while (idom >= 0) {
     727         366 :                         level++;
     728         366 :                         if (blocks[idom].level >= 0) {
     729         353 :                                 level += blocks[idom].level;
     730         353 :                                 break;
     731             :                         } else {
     732          13 :                                 idom = blocks[idom].idom;
     733             :                         }
     734             :                 }
     735         790 :                 blocks[j].level = level;
     736             :         }
     737             : 
     738         437 :         free_alloca(postnum, use_heap);
     739         437 :         return SUCCESS;
     740             : }
     741             : /* }}} */
     742             : 
     743         136 : static int dominates(zend_basic_block *blocks, int a, int b) /* {{{ */
     744             : {
     745         451 :         while (blocks[b].level > blocks[a].level) {
     746         179 :                 b = blocks[b].idom;
     747             :         }
     748         136 :         return a == b;
     749             : }
     750             : /* }}} */
     751             : 
     752             : typedef struct {
     753             :         int id;
     754             :         int level;
     755             : } block_info;
     756        1085 : static int compare_block_level(const block_info *a, const block_info *b) {
     757        1085 :         return b->level - a->level;
     758             : }
     759        1151 : static void swap_blocks(block_info *a, block_info *b) {
     760        1151 :         block_info tmp = *a;
     761        1151 :         *a = *b;
     762        1151 :         *b = tmp;
     763        1151 : }
     764             : 
     765         437 : int zend_cfg_identify_loops(const zend_op_array *op_array, zend_cfg *cfg, uint32_t *flags) /* {{{ */
     766             : {
     767             :         int i, j, k, n;
     768             :         int time;
     769         437 :         zend_basic_block *blocks = cfg->blocks;
     770             :         int *entry_times, *exit_times;
     771             :         zend_worklist work;
     772         437 :         int flag = ZEND_FUNC_NO_LOOPS;
     773             :         block_info *sorted_blocks;
     774             :         ALLOCA_FLAG(list_use_heap)
     775             :         ALLOCA_FLAG(tree_use_heap)
     776             :         ALLOCA_FLAG(sorted_blocks_use_heap)
     777             : 
     778         437 :         ZEND_WORKLIST_ALLOCA(&work, cfg->blocks_count, list_use_heap);
     779             : 
     780             :         /* We don't materialize the DJ spanning tree explicitly, as we are only interested in ancestor
     781             :          * queries. These are implemented by checking entry/exit times of the DFS search. */
     782         437 :         entry_times = do_alloca(2 * sizeof(int) * cfg->blocks_count, tree_use_heap);
     783         437 :         exit_times = entry_times + cfg->blocks_count;
     784         437 :         memset(entry_times, -1, 2 * sizeof(int) * cfg->blocks_count);
     785             : 
     786         437 :         zend_worklist_push(&work, 0);
     787         437 :         time = 0;
     788        1664 :         while (zend_worklist_len(&work)) {
     789             :         next:
     790        1143 :                 i = zend_worklist_peek(&work);
     791        1143 :                 if (entry_times[i] == -1) {
     792         790 :                         entry_times[i] = time++;
     793             :                 }
     794             :                 /* Visit blocks immediately dominated by i. */
     795        1596 :                 for (j = blocks[i].children; j >= 0; j = blocks[j].next_child) {
     796         741 :                         if (zend_worklist_push(&work, j)) {
     797         288 :                                 goto next;
     798             :                         }
     799             :                 }
     800             :                 /* Visit join edges.  */
     801        2442 :                 for (j = 0; j < 2; j++) {
     802        1652 :                         int succ = blocks[i].successors[j];
     803        1652 :                         if (succ < 0) {
     804        1097 :                                 continue;
     805         555 :                         } else if (blocks[succ].idom == i) {
     806         353 :                                 continue;
     807         202 :                         } else if (zend_worklist_push(&work, succ)) {
     808          65 :                                 goto next;
     809             :                         }
     810             :                 }
     811         790 :                 exit_times[i] = time++;
     812         790 :                 zend_worklist_pop(&work);
     813             :         }
     814             : 
     815             :         /* Sort blocks by decreasing level, which is the order in which we want to process them */
     816         437 :         sorted_blocks = do_alloca(sizeof(block_info) * cfg->blocks_count, sorted_blocks_use_heap);
     817        1227 :         for (i = 0; i < cfg->blocks_count; i++) {
     818         790 :                 sorted_blocks[i].id = i;
     819         790 :                 sorted_blocks[i].level = blocks[i].level;
     820             :         }
     821         437 :         zend_sort(sorted_blocks, cfg->blocks_count, sizeof(block_info),
     822             :                 (compare_func_t) compare_block_level, (swap_func_t) swap_blocks);
     823             : 
     824             :         /* Identify loops.  See Sreedhar et al, "Identifying Loops Using DJ
     825             :            Graphs".  */
     826             : 
     827        1227 :         for (n = 0; n < cfg->blocks_count; n++) {
     828         790 :                 i = sorted_blocks[n].id;
     829             : 
     830         790 :                 zend_bitset_clear(work.visited, zend_bitset_len(cfg->blocks_count));
     831        1271 :                 for (j = 0; j < blocks[i].predecessors_count; j++) {
     832         481 :                         int pred = cfg->predecessors[blocks[i].predecessor_offset + j];
     833             : 
     834             :                         /* A join edge is one for which the predecessor does not
     835             :                            immediately dominate the successor.  */
     836         481 :                         if (blocks[i].idom == pred) {
     837         345 :                                 continue;
     838             :                         }
     839             : 
     840             :                         /* In a loop back-edge (back-join edge), the successor dominates
     841             :                            the predecessor.  */
     842         136 :                         if (dominates(blocks, i, pred)) {
     843          22 :                                 blocks[i].flags |= ZEND_BB_LOOP_HEADER;
     844          22 :                                 flag &= ~ZEND_FUNC_NO_LOOPS;
     845          22 :                                 zend_worklist_push(&work, pred);
     846             :                         } else {
     847             :                                 /* Otherwise it's a cross-join edge.  See if it's a branch
     848             :                                    to an ancestor on the DJ spanning tree.  */
     849         114 :                                 if (entry_times[pred] > entry_times[i] && exit_times[pred] < exit_times[i]) {
     850           0 :                                         blocks[i].flags |= ZEND_BB_IRREDUCIBLE_LOOP;
     851           0 :                                         flag |= ZEND_FUNC_IRREDUCIBLE;
     852           0 :                                         flag &= ~ZEND_FUNC_NO_LOOPS;
     853             :                                 }
     854             :                         }
     855             :                 }
     856        1645 :                 while (zend_worklist_len(&work)) {
     857          65 :                         j = zend_worklist_pop(&work);
     858         130 :                         while (blocks[j].loop_header >= 0) {
     859           0 :                                 j = blocks[j].loop_header;
     860             :                         }
     861          65 :                         if (j != i) {
     862          47 :                                 blocks[j].loop_header = i;
     863          98 :                                 for (k = 0; k < blocks[j].predecessors_count; k++) {
     864          51 :                                         zend_worklist_push(&work, cfg->predecessors[blocks[j].predecessor_offset + k]);
     865             :                                 }
     866             :                         }
     867             :                 }
     868             :         }
     869             : 
     870         437 :         free_alloca(sorted_blocks, sorted_blocks_use_heap);
     871         437 :         free_alloca(entry_times, tree_use_heap);
     872         437 :         ZEND_WORKLIST_FREE_ALLOCA(&work, list_use_heap);
     873         437 :         *flags |= flag;
     874             : 
     875         437 :         return SUCCESS;
     876             : }
     877             : /* }}} */
     878             : 
     879             : /*
     880             :  * Local variables:
     881             :  * tab-width: 4
     882             :  * c-basic-offset: 4
     883             :  * indent-tabs-mode: t
     884             :  * End:
     885             :  */

Generated by: LCOV version 1.10

Generated at Sun, 15 Oct 2017 12:26:23 +0000 (8 days ago)

Copyright © 2005-2017 The PHP Group
All rights reserved.