source: src/router/php7/ext/opcache/Optimizer/zend_cfg.c @ 31874

Last change on this file since 31874 was 31874, checked in by brainslayer, 6 weeks ago

update php

File size: 25.6 KB
Line 
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
27static 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        zend_basic_block *blocks = cfg->blocks;
33
34        while (1) {
35                b->flags |= ZEND_BB_REACHABLE;
36                successor_0 = b->successors[0];
37                if (successor_0 >= 0) {
38                        successor_1 = b->successors[1];
39                        if (successor_1 >= 0) {
40                                b0 = blocks + successor_0;
41                                b0->flags |= ZEND_BB_TARGET;
42                                if (!(b0->flags & ZEND_BB_REACHABLE)) {
43                                        zend_mark_reachable(opcodes, cfg, b0);
44                                }
45
46                                ZEND_ASSERT(b->len != 0);
47                                opcode = opcodes[b->start + b->len - 1].opcode;
48                                b = blocks + successor_1;
49                                if (opcode == ZEND_JMPZNZ) {
50                                        b->flags |= ZEND_BB_TARGET;
51                                } else {
52                                        b->flags |= ZEND_BB_FOLLOW;
53                                }
54                        } else if (b->len != 0) {
55                                opcode = opcodes[b->start + b->len - 1].opcode;
56                                b = blocks + successor_0;
57                                if (opcode == ZEND_JMP) {
58                                        b->flags |= ZEND_BB_TARGET;
59                                } else {
60                                        b->flags |= ZEND_BB_FOLLOW;
61
62                                        if (cfg->split_at_calls) {
63                                                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                                                        b->flags |= ZEND_BB_ENTRY;
71                                                }
72                                        }
73                                        if (cfg->split_at_recv) {
74                                                if (opcode == ZEND_RECV ||
75                                                    opcode == ZEND_RECV_INIT) {
76                                                        b->flags |= ZEND_BB_RECV_ENTRY;
77                                                }
78                                        }
79                                }
80                        } else {
81                                b = blocks + successor_0;
82                                b->flags |= ZEND_BB_FOLLOW;
83                        }
84                        if (b->flags & ZEND_BB_REACHABLE) return;
85                } else {
86                        b->flags |= ZEND_BB_EXIT;
87                        return;
88                }
89        }
90}
91/* }}} */
92
93static void zend_mark_reachable_blocks(const zend_op_array *op_array, zend_cfg *cfg, int start) /* {{{ */
94{
95        zend_basic_block *blocks = cfg->blocks;
96
97        blocks[start].flags = ZEND_BB_START;
98        zend_mark_reachable(op_array->opcodes, cfg, blocks + start);
99
100        if (op_array->last_live_range || op_array->last_try_catch) {
101                zend_basic_block *b;
102                int j, changed;
103                uint32_t *block_map = cfg->map;
104
105                do {
106                        changed = 0;
107
108                        /* Add live range paths */
109                        for (j = 0; j < op_array->last_live_range; j++) {
110                                zend_live_range *live_range = &op_array->live_range[j];
111                                if (live_range->var == (uint32_t)-1) {
112                                        /* this live range already removed */
113                                        continue;
114                                }
115                                b = blocks + block_map[live_range->start];
116                                if (b->flags & ZEND_BB_REACHABLE) {
117                                        while (b->len > 0 && op_array->opcodes[b->start].opcode == ZEND_NOP) {
118                                            /* check if NOP breaks incorrect smart branch */
119                                                if (b->len == 2
120                                                 && (op_array->opcodes[b->start + 1].opcode == ZEND_JMPZ
121                                                  || op_array->opcodes[b->start + 1].opcode == ZEND_JMPNZ)
122                                                 && (op_array->opcodes[b->start + 1].op1_type & (IS_CV|IS_CONST))
123                                                 && b->start > 0
124                                                 && zend_is_smart_branch(op_array->opcodes + b->start - 1)) {
125                                                        break;
126                                                }
127                                                b->start++;
128                                                b->len--;
129                                        }
130                                        if (b->len == 0 && (uint32_t)b->successors[0] == block_map[live_range->end]) {
131                                                /* mark as removed (empty live range) */
132                                                live_range->var = (uint32_t)-1;
133                                                continue;
134                                        }
135                                        b->flags |= ZEND_BB_GEN_VAR;
136                                        b = blocks + block_map[live_range->end];
137                                        b->flags |= ZEND_BB_KILL_VAR;
138                                        if (!(b->flags & (ZEND_BB_REACHABLE|ZEND_BB_UNREACHABLE_FREE))) {
139                                                if (cfg->split_at_live_ranges) {
140                                                        changed = 1;
141                                                        zend_mark_reachable(op_array->opcodes, cfg, b);
142                                                } else {
143                                                        ZEND_ASSERT(b->start == live_range->end);
144                                                        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                        for (j = 0; j < op_array->last_try_catch; j++) {
154
155                                /* check for jumps into the middle of try block */
156                                b = blocks + block_map[op_array->try_catch_array[j].try_op];
157                                if (!(b->flags & ZEND_BB_REACHABLE)) {
158                                        zend_basic_block *end;
159
160                                        if (op_array->try_catch_array[j].catch_op) {
161                                                end = blocks + block_map[op_array->try_catch_array[j].catch_op];
162                                                while (b != end) {
163                                                        if (b->flags & ZEND_BB_REACHABLE) {
164                                                                op_array->try_catch_array[j].try_op = b->start;
165                                                                break;
166                                                        }
167                                                        b++;
168                                                }
169                                        }
170                                        b = blocks + block_map[op_array->try_catch_array[j].try_op];
171                                        if (!(b->flags & ZEND_BB_REACHABLE)) {
172                                                if (op_array->try_catch_array[j].finally_op) {
173                                                        end = blocks + block_map[op_array->try_catch_array[j].finally_op];
174                                                        while (b != end) {
175                                                                if (b->flags & ZEND_BB_REACHABLE) {
176                                                                        op_array->try_catch_array[j].try_op = op_array->try_catch_array[j].catch_op;
177                                                                        changed = 1;
178                                                                        zend_mark_reachable(op_array->opcodes, cfg, blocks + block_map[op_array->try_catch_array[j].try_op]);
179                                                                        break;
180                                                                }
181                                                                b++;
182                                                        }
183                                                }
184                                        }
185                                }
186
187                                b = blocks + block_map[op_array->try_catch_array[j].try_op];
188                                if (b->flags & ZEND_BB_REACHABLE) {
189                                        b->flags |= ZEND_BB_TRY;
190                                        if (op_array->try_catch_array[j].catch_op) {
191                                                b = blocks + block_map[op_array->try_catch_array[j].catch_op];
192                                                b->flags |= ZEND_BB_CATCH;
193                                                if (!(b->flags & ZEND_BB_REACHABLE)) {
194                                                        changed = 1;
195                                                        zend_mark_reachable(op_array->opcodes, cfg, b);
196                                                }
197                                        }
198                                        if (op_array->try_catch_array[j].finally_op) {
199                                                b = blocks + block_map[op_array->try_catch_array[j].finally_op];
200                                                b->flags |= ZEND_BB_FINALLY;
201                                                if (!(b->flags & ZEND_BB_REACHABLE)) {
202                                                        changed = 1;
203                                                        zend_mark_reachable(op_array->opcodes, cfg, b);
204                                                }
205                                        }
206                                        if (op_array->try_catch_array[j].finally_end) {
207                                                b = blocks + block_map[op_array->try_catch_array[j].finally_end];
208                                                b->flags |= ZEND_BB_FINALLY_END;
209                                                if (!(b->flags & ZEND_BB_REACHABLE)) {
210                                                        changed = 1;
211                                                        zend_mark_reachable(op_array->opcodes, cfg, b);
212                                                }
213                                        }
214                                } else {
215                                        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                                        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                                        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                } while (changed);
227        }
228}
229/* }}} */
230
231void zend_cfg_remark_reachable_blocks(const zend_op_array *op_array, zend_cfg *cfg) /* {{{ */
232{
233        zend_basic_block *blocks = cfg->blocks;
234        int i;
235        int start = 0;
236
237        for (i = 0; i < cfg->blocks_count; i++) {
238                if (blocks[i].flags & ZEND_BB_REACHABLE) {
239                        start = i;
240                        i++;
241                        break;
242                }
243        }
244
245        /* clear all flags */
246        for (i = 0; i < cfg->blocks_count; i++) {
247                blocks[i].flags = 0;
248        }
249
250        zend_mark_reachable_blocks(op_array, cfg, start);
251}
252/* }}} */
253
254static void record_successor(zend_basic_block *blocks, int pred, int n, int succ)
255{
256        blocks[pred].successors[n] = succ;
257}
258
259static void initialize_block(zend_basic_block *block) {
260        block->flags = 0;
261        block->successors[0] = -1;
262        block->successors[1] = -1;
263        block->predecessors_count = 0;
264        block->predecessor_offset = -1;
265        block->idom = -1;
266        block->loop_header = -1;
267        block->level = -1;
268        block->children = -1;
269        block->next_child = -1;
270}
271
272#define BB_START(i) do { \
273                if (!block_map[i]) { blocks_count++;} \
274                block_map[i]++; \
275        } while (0)
276
277int 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        uint32_t flags = 0;
280        uint32_t i;
281        int j;
282        uint32_t *block_map;
283        zend_function *fn;
284        int blocks_count = 0;
285        zend_basic_block *blocks;
286        zval *zv;
287        zend_bool extra_entry_block = 0;
288
289        cfg->split_at_live_ranges = (build_flags & ZEND_CFG_SPLIT_AT_LIVE_RANGES) != 0;
290        cfg->split_at_calls = (build_flags & ZEND_CFG_STACKLESS) != 0;
291        cfg->split_at_recv = (build_flags & ZEND_CFG_RECV_ENTRY) != 0 && (op_array->fn_flags & ZEND_ACC_HAS_TYPE_HINTS) == 0;
292
293        cfg->map = block_map = zend_arena_calloc(arena, op_array->last, sizeof(uint32_t));
294        if (!block_map) {
295                return FAILURE;
296        }
297
298        /* Build CFG, Step 1: Find basic blocks starts, calculate number of blocks */
299        BB_START(0);
300        for (i = 0; i < op_array->last; i++) {
301                zend_op *opline = op_array->opcodes + i;
302                switch(opline->opcode) {
303                        case ZEND_RECV:
304                        case ZEND_RECV_INIT:
305                                if (build_flags & ZEND_CFG_RECV_ENTRY) {
306                                        BB_START(i + 1);
307                                }
308                                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                                if (i + 1 < op_array->last) {
315                                        BB_START(i + 1);
316                                }
317                                break;
318                        case ZEND_INCLUDE_OR_EVAL:
319                                flags |= ZEND_FUNC_INDIRECT_VAR_ACCESS;
320                        case ZEND_GENERATOR_CREATE:
321                        case ZEND_YIELD:
322                        case ZEND_YIELD_FROM:
323                                if (build_flags & ZEND_CFG_STACKLESS) {
324                                        BB_START(i + 1);
325                                }
326                                break;
327                        case ZEND_DO_FCALL:
328                        case ZEND_DO_UCALL:
329                        case ZEND_DO_FCALL_BY_NAME:
330                                flags |= ZEND_FUNC_HAS_CALLS;
331                                if (build_flags & ZEND_CFG_STACKLESS) {
332                                        BB_START(i + 1);
333                                }
334                                break;
335                        case ZEND_DO_ICALL:
336                                flags |= ZEND_FUNC_HAS_CALLS;
337                                break;
338                        case ZEND_INIT_FCALL:
339                        case ZEND_INIT_NS_FCALL_BY_NAME:
340                                zv = CRT_CONSTANT(opline->op2);
341                                if (opline->opcode == ZEND_INIT_NS_FCALL_BY_NAME) {
342                                        /* The third literal is the lowercased unqualified name */
343                                        zv += 2;
344                                }
345                                if ((fn = zend_hash_find_ptr(EG(function_table), Z_STR_P(zv))) != NULL) {
346                                        if (fn->type == ZEND_INTERNAL_FUNCTION) {
347                                                flags |= zend_optimizer_classify_function(
348                                                        Z_STR_P(zv), opline->extended_value);
349                                        }
350                                }
351                                break;
352                        case ZEND_FAST_CALL:
353                                BB_START(OP_JMP_ADDR(opline, opline->op1) - op_array->opcodes);
354                                BB_START(i + 1);
355                                break;
356                        case ZEND_FAST_RET:
357                                if (i + 1 < op_array->last) {
358                                        BB_START(i + 1);
359                                }
360                                break;
361                        case ZEND_JMP:
362                                BB_START(OP_JMP_ADDR(opline, opline->op1) - op_array->opcodes);
363                                if (i + 1 < op_array->last) {
364                                        BB_START(i + 1);
365                                }
366                                break;
367                        case ZEND_JMPZNZ:
368                                BB_START(OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes);
369                                BB_START(ZEND_OFFSET_TO_OPLINE_NUM(op_array, opline, opline->extended_value));
370                                if (i + 1 < op_array->last) {
371                                        BB_START(i + 1);
372                                }
373                                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                                BB_START(OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes);
382                                BB_START(i + 1);
383                                break;
384                        case ZEND_CATCH:
385                                if (!opline->result.num) {
386                                        BB_START(ZEND_OFFSET_TO_OPLINE_NUM(op_array, opline, opline->extended_value));
387                                }
388                                BB_START(i + 1);
389                                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                                BB_START(ZEND_OFFSET_TO_OPLINE_NUM(op_array, opline, opline->extended_value));
395                                BB_START(i + 1);
396                                break;
397                        case ZEND_FE_RESET_R:
398                        case ZEND_FE_RESET_RW:
399                                BB_START(OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes);
400                                BB_START(i + 1);
401                                break;
402                        case ZEND_UNSET_VAR:
403                        case ZEND_ISSET_ISEMPTY_VAR:
404                                if (((opline->extended_value & ZEND_FETCH_TYPE_MASK) == ZEND_FETCH_LOCAL) &&
405                                    !(opline->extended_value & ZEND_QUICK_SET)) {
406                                        flags |= ZEND_FUNC_INDIRECT_VAR_ACCESS;
407                                } else if (((opline->extended_value & ZEND_FETCH_TYPE_MASK) == ZEND_FETCH_GLOBAL ||
408                                            (opline->extended_value & ZEND_FETCH_TYPE_MASK) == ZEND_FETCH_GLOBAL_LOCK) &&
409                                           !op_array->function_name) {
410                                        flags |= ZEND_FUNC_INDIRECT_VAR_ACCESS;
411                                }
412                                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                                if ((opline->extended_value & ZEND_FETCH_TYPE_MASK) == ZEND_FETCH_LOCAL) {
420                                        flags |= ZEND_FUNC_INDIRECT_VAR_ACCESS;
421                                } else if (((opline->extended_value & ZEND_FETCH_TYPE_MASK) == ZEND_FETCH_GLOBAL ||
422                                            (opline->extended_value & ZEND_FETCH_TYPE_MASK) == ZEND_FETCH_GLOBAL_LOCK) &&
423                                           !op_array->function_name) {
424                                        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        if ((build_flags & ZEND_CFG_NO_ENTRY_PREDECESSORS)
432                        && op_array->last > 0 && block_map[0] > 1) {
433                extra_entry_block = 1;
434        }
435
436        if (cfg->split_at_live_ranges) {
437                for (j = 0; j < op_array->last_live_range; j++) {
438                        BB_START(op_array->live_range[j].start);
439                        BB_START(op_array->live_range[j].end);
440                }
441        }
442
443        if (op_array->last_try_catch) {
444                for (j = 0; j < op_array->last_try_catch; j++) {
445                        BB_START(op_array->try_catch_array[j].try_op);
446                        if (op_array->try_catch_array[j].catch_op) {
447                                BB_START(op_array->try_catch_array[j].catch_op);
448                        }
449                        if (op_array->try_catch_array[j].finally_op) {
450                                BB_START(op_array->try_catch_array[j].finally_op);
451                        }
452                        if (op_array->try_catch_array[j].finally_end) {
453                                BB_START(op_array->try_catch_array[j].finally_end);
454                        }
455                }
456        }
457
458        blocks_count += extra_entry_block;
459        cfg->blocks_count = blocks_count;
460
461        /* Build CFG, Step 2: Build Array of Basic Blocks */
462        cfg->blocks = blocks = zend_arena_calloc(arena, sizeof(zend_basic_block), blocks_count);
463        if (!blocks) {
464                return FAILURE;
465        }
466
467        blocks_count = -1;
468
469        if (extra_entry_block) {
470                initialize_block(&blocks[0]);
471                blocks[0].start = 0;
472                blocks[0].len = 0;
473                blocks_count++;
474        }
475
476        for (i = 0; i < op_array->last; i++) {
477                if (block_map[i]) {
478                        if (blocks_count >= 0) {
479                                blocks[blocks_count].len = i - blocks[blocks_count].start;
480                        }
481                        blocks_count++;
482                        initialize_block(&blocks[blocks_count]);
483                        blocks[blocks_count].start = i;
484                }
485                block_map[i] = blocks_count;
486        }
487
488        blocks[blocks_count].len = i - blocks[blocks_count].start;
489        blocks_count++;
490
491        /* Build CFG, Step 3: Calculate successors */
492        for (j = 0; j < blocks_count; j++) {
493                zend_op *opline;
494                if (blocks[j].len == 0) {
495                        record_successor(blocks, j, 0, j + 1);
496                        continue;
497                }
498
499                opline = op_array->opcodes + blocks[j].start + blocks[j].len - 1;
500                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                                break;
508                        case ZEND_JMP:
509                                record_successor(blocks, j, 0, block_map[OP_JMP_ADDR(opline, opline->op1) - op_array->opcodes]);
510                                break;
511                        case ZEND_JMPZNZ:
512                                record_successor(blocks, j, 0, block_map[OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes]);
513                                record_successor(blocks, j, 1, block_map[ZEND_OFFSET_TO_OPLINE_NUM(op_array, opline, opline->extended_value)]);
514                                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                                record_successor(blocks, j, 0, block_map[OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes]);
523                                record_successor(blocks, j, 1, j + 1);
524                                break;
525                        case ZEND_CATCH:
526                                if (!opline->result.num) {
527                                        record_successor(blocks, j, 0, block_map[ZEND_OFFSET_TO_OPLINE_NUM(op_array, opline, opline->extended_value)]);
528                                        record_successor(blocks, j, 1, j + 1);
529                                } else {
530                                        record_successor(blocks, j, 0, j + 1);
531                                }
532                                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                                record_successor(blocks, j, 0, block_map[ZEND_OFFSET_TO_OPLINE_NUM(op_array, opline, opline->extended_value)]);
538                                record_successor(blocks, j, 1, j + 1);
539                                break;
540                        case ZEND_FE_RESET_R:
541                        case ZEND_FE_RESET_RW:
542                                record_successor(blocks, j, 0, block_map[OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes]);
543                                record_successor(blocks, j, 1, j + 1);
544                                break;
545                        case ZEND_FAST_CALL:
546                                record_successor(blocks, j, 0, block_map[OP_JMP_ADDR(opline, opline->op1) - op_array->opcodes]);
547                                record_successor(blocks, j, 1, j + 1);
548                                break;
549                        default:
550                                record_successor(blocks, j, 0, j + 1);
551                                break;
552                }
553        }
554
555        /* Build CFG, Step 4, Mark Reachable Basic Blocks */
556        zend_mark_reachable_blocks(op_array, cfg, 0);
557
558        if (func_flags) {
559                *func_flags |= flags;
560        }
561
562        return SUCCESS;
563}
564/* }}} */
565
566int zend_cfg_build_predecessors(zend_arena **arena, zend_cfg *cfg) /* {{{ */
567{
568        int j, edges;
569        zend_basic_block *b;
570        zend_basic_block *blocks = cfg->blocks;
571        zend_basic_block *end = blocks + cfg->blocks_count;
572        int *predecessors;
573
574        edges = 0;
575        for (b = blocks; b < end; b++) {
576                b->predecessors_count = 0;
577        }
578        for (b = blocks; b < end; b++) {
579                if (!(b->flags & ZEND_BB_REACHABLE)) {
580                        b->successors[0] = -1;
581                        b->successors[1] = -1;
582                        b->predecessors_count = 0;
583                } else {
584                        if (b->successors[0] >= 0) {
585                                edges++;
586                                blocks[b->successors[0]].predecessors_count++;
587                                if (b->successors[1] >= 0 && b->successors[1] != b->successors[0]) {
588                                        edges++;
589                                        blocks[b->successors[1]].predecessors_count++;
590                                }
591                        }
592                }
593        }
594
595        cfg->predecessors = predecessors = (int*)zend_arena_calloc(arena, sizeof(int), edges);
596
597        if (!predecessors) {
598                return FAILURE;
599        }
600
601        edges = 0;
602        for (b = blocks; b < end; b++) {
603                if (b->flags & ZEND_BB_REACHABLE) {
604                        b->predecessor_offset = edges;
605                        edges += b->predecessors_count;
606                        b->predecessors_count = 0;
607                }
608        }
609
610        for (j = 0; j < cfg->blocks_count; j++) {
611                if (blocks[j].flags & ZEND_BB_REACHABLE) {
612                        if (blocks[j].successors[0] >= 0) {
613                                zend_basic_block *b = blocks + blocks[j].successors[0];
614                                predecessors[b->predecessor_offset + b->predecessors_count] = j;
615                                b->predecessors_count++;
616                                if (blocks[j].successors[1] >= 0
617                                                && blocks[j].successors[1] != blocks[j].successors[0]) {
618                                        zend_basic_block *b = blocks + blocks[j].successors[1];
619                                        predecessors[b->predecessor_offset + b->predecessors_count] = j;
620                                        b->predecessors_count++;
621                                }
622                        }
623                }
624        }
625
626        return SUCCESS;
627}
628/* }}} */
629
630/* Computes a postorder numbering of the CFG */
631static void compute_postnum_recursive(
632                int *postnum, int *cur, const zend_cfg *cfg, int block_num) /* {{{ */
633{
634        zend_basic_block *block = &cfg->blocks[block_num];
635        if (postnum[block_num] != -1) {
636                return;
637        }
638
639        postnum[block_num] = -2; /* Marker for "currently visiting" */
640        if (block->successors[0] >= 0) {
641                compute_postnum_recursive(postnum, cur, cfg, block->successors[0]);
642                if (block->successors[1] >= 0) {
643                        compute_postnum_recursive(postnum, cur, cfg, block->successors[1]);
644                }
645        }
646        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. */
652int zend_cfg_compute_dominators_tree(const zend_op_array *op_array, zend_cfg *cfg) /* {{{ */
653{
654        zend_basic_block *blocks = cfg->blocks;
655        int blocks_count = cfg->blocks_count;
656        int j, k, changed;
657
658        ALLOCA_FLAG(use_heap)
659        int *postnum = do_alloca(sizeof(int) * cfg->blocks_count, use_heap);
660        memset(postnum, -1, sizeof(int) * cfg->blocks_count);
661        j = 0;
662        compute_postnum_recursive(postnum, &j, cfg, 0);
663
664        /* FIXME: move declarations */
665        blocks[0].idom = 0;
666        do {
667                changed = 0;
668                /* Iterating in RPO here would converge faster */
669                for (j = 1; j < blocks_count; j++) {
670                        int idom = -1;
671
672                        if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
673                                continue;
674                        }
675                        for (k = 0; k < blocks[j].predecessors_count; k++) {
676                                int pred = cfg->predecessors[blocks[j].predecessor_offset + k];
677
678                                if (idom < 0) {
679                                        if (blocks[pred].idom >= 0)
680                                                idom = pred;
681                                        continue;
682                                }
683
684                                if (blocks[pred].idom >= 0) {
685                                        while (idom != pred) {
686                                                while (postnum[pred] < postnum[idom]) pred = blocks[pred].idom;
687                                                while (postnum[idom] < postnum[pred]) idom = blocks[idom].idom;
688                                        }
689                                }
690                        }
691
692                        if (idom >= 0 && blocks[j].idom != idom) {
693                                blocks[j].idom = idom;
694                                changed = 1;
695                        }
696                }
697        } while (changed);
698        blocks[0].idom = -1;
699
700        for (j = 1; j < blocks_count; j++) {
701                if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
702                        continue;
703                }
704                if (blocks[j].idom >= 0) {
705                        /* Sort by block number to traverse children in pre-order */
706                        if (blocks[blocks[j].idom].children < 0 ||
707                            j < blocks[blocks[j].idom].children) {
708                                blocks[j].next_child = blocks[blocks[j].idom].children;
709                                blocks[blocks[j].idom].children = j;
710                        } else {
711                                int k = blocks[blocks[j].idom].children;
712                                while (blocks[k].next_child >=0 && j > blocks[k].next_child) {
713                                        k = blocks[k].next_child;
714                                }
715                                blocks[j].next_child = blocks[k].next_child;
716                                blocks[k].next_child = j;
717                        }
718                }
719        }
720
721        for (j = 0; j < blocks_count; j++) {
722                int idom = blocks[j].idom, level = 0;
723                if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
724                        continue;
725                }
726                while (idom >= 0) {
727                        level++;
728                        if (blocks[idom].level >= 0) {
729                                level += blocks[idom].level;
730                                break;
731                        } else {
732                                idom = blocks[idom].idom;
733                        }
734                }
735                blocks[j].level = level;
736        }
737
738        free_alloca(postnum, use_heap);
739        return SUCCESS;
740}
741/* }}} */
742
743static int dominates(zend_basic_block *blocks, int a, int b) /* {{{ */
744{
745        while (blocks[b].level > blocks[a].level) {
746                b = blocks[b].idom;
747        }
748        return a == b;
749}
750/* }}} */
751
752typedef struct {
753        int id;
754        int level;
755} block_info;
756static int compare_block_level(const block_info *a, const block_info *b) {
757        return b->level - a->level;
758}
759static void swap_blocks(block_info *a, block_info *b) {
760        block_info tmp = *a;
761        *a = *b;
762        *b = tmp;
763}
764
765int 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 depth, time;
769        zend_basic_block *blocks = cfg->blocks;
770        int *entry_times, *exit_times;
771        zend_worklist work;
772        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        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        entry_times = do_alloca(2 * sizeof(int) * cfg->blocks_count, tree_use_heap);
783        exit_times = entry_times + cfg->blocks_count;
784        memset(entry_times, -1, 2 * sizeof(int) * cfg->blocks_count);
785
786        zend_worklist_push(&work, 0);
787        time = 0;
788        while (zend_worklist_len(&work)) {
789        next:
790                i = zend_worklist_peek(&work);
791                if (entry_times[i] == -1) {
792                        entry_times[i] = time++;
793                }
794                /* Visit blocks immediately dominated by i. */
795                for (j = blocks[i].children; j >= 0; j = blocks[j].next_child) {
796                        if (zend_worklist_push(&work, j)) {
797                                goto next;
798                        }
799                }
800                /* Visit join edges.  */
801                for (j = 0; j < 2; j++) {
802                        int succ = blocks[i].successors[j];
803                        if (succ < 0) {
804                                continue;
805                        } else if (blocks[succ].idom == i) {
806                                continue;
807                        } else if (zend_worklist_push(&work, succ)) {
808                                goto next;
809                        }
810                }
811                exit_times[i] = time++;
812                zend_worklist_pop(&work);
813        }
814
815        /* Sort blocks by decreasing level, which is the order in which we want to process them */
816        sorted_blocks = do_alloca(sizeof(block_info) * cfg->blocks_count, sorted_blocks_use_heap);
817        for (i = 0; i < cfg->blocks_count; i++) {
818                sorted_blocks[i].id = i;
819                sorted_blocks[i].level = blocks[i].level;
820        }
821        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        for (n = 0; n < cfg->blocks_count; n++) {
828                i = sorted_blocks[n].id;
829
830                zend_bitset_clear(work.visited, zend_bitset_len(cfg->blocks_count));
831                for (j = 0; j < blocks[i].predecessors_count; j++) {
832                        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                        if (blocks[i].idom == pred) {
837                                continue;
838                        }
839
840                        /* In a loop back-edge (back-join edge), the successor dominates
841                           the predecessor.  */
842                        if (dominates(blocks, i, pred)) {
843                                blocks[i].flags |= ZEND_BB_LOOP_HEADER;
844                                flag &= ~ZEND_FUNC_NO_LOOPS;
845                                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                                if (entry_times[pred] > entry_times[i] && exit_times[pred] < exit_times[i]) {
850                                        blocks[i].flags |= ZEND_BB_IRREDUCIBLE_LOOP;
851                                        flag |= ZEND_FUNC_IRREDUCIBLE;
852                                        flag &= ~ZEND_FUNC_NO_LOOPS;
853                                }
854                        }
855                }
856                while (zend_worklist_len(&work)) {
857                        j = zend_worklist_pop(&work);
858                        if (blocks[j].loop_header < 0 && j != i) {
859                                blocks[j].loop_header = i;
860                                for (k = 0; k < blocks[j].predecessors_count; k++) {
861                                        zend_worklist_push(&work, cfg->predecessors[blocks[j].predecessor_offset + k]);
862                                }
863                        }
864                }
865        }
866
867        free_alloca(sorted_blocks, sorted_blocks_use_heap);
868        free_alloca(entry_times, tree_use_heap);
869        ZEND_WORKLIST_FREE_ALLOCA(&work, list_use_heap);
870        *flags |= flag;
871
872        return SUCCESS;
873}
874/* }}} */
875
876/*
877 * Local variables:
878 * tab-width: 4
879 * c-basic-offset: 4
880 * indent-tabs-mode: t
881 * End:
882 */
Note: See TracBrowser for help on using the repository browser.