1 /*
2 +----------------------------------------------------------------------+
3 | Zend Engine, CFG - Control Flow Graph |
4 +----------------------------------------------------------------------+
5 | Copyright (c) 1998-2018 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
zend_mark_reachable(zend_op * opcodes,zend_cfg * cfg,zend_basic_block * b)27 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 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
zend_mark_reachable_blocks(const zend_op_array * op_array,zend_cfg * cfg,int start)93 static 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
zend_cfg_remark_reachable_blocks(const zend_op_array * op_array,zend_cfg * cfg)231 void 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
record_successor(zend_basic_block * blocks,int pred,int n,int succ)254 static void record_successor(zend_basic_block *blocks, int pred, int n, int succ)
255 {
256 blocks[pred].successors[n] = succ;
257 }
258
initialize_block(zend_basic_block * block)259 static 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
zend_build_cfg(zend_arena ** arena,const zend_op_array * op_array,uint32_t build_flags,zend_cfg * cfg,uint32_t * func_flags)277 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 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
zend_cfg_build_predecessors(zend_arena ** arena,zend_cfg * cfg)566 int 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 */
compute_postnum_recursive(int * postnum,int * cur,const zend_cfg * cfg,int block_num)631 static 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. */
zend_cfg_compute_dominators_tree(const zend_op_array * op_array,zend_cfg * cfg)652 int 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
dominates(zend_basic_block * blocks,int a,int b)743 static 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
752 typedef struct {
753 int id;
754 int level;
755 } block_info;
compare_block_level(const block_info * a,const block_info * b)756 static int compare_block_level(const block_info *a, const block_info *b) {
757 return b->level - a->level;
758 }
swap_blocks(block_info * a,block_info * b)759 static void swap_blocks(block_info *a, block_info *b) {
760 block_info tmp = *a;
761 *a = *b;
762 *b = tmp;
763 }
764
zend_cfg_identify_loops(const zend_op_array * op_array,zend_cfg * cfg,uint32_t * flags)765 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 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 while (blocks[j].loop_header >= 0) {
859 j = blocks[j].loop_header;
860 }
861 if (j != i) {
862 blocks[j].loop_header = i;
863 for (k = 0; k < blocks[j].predecessors_count; k++) {
864 zend_worklist_push(&work, cfg->predecessors[blocks[j].predecessor_offset + k]);
865 }
866 }
867 }
868 }
869
870 free_alloca(sorted_blocks, sorted_blocks_use_heap);
871 free_alloca(entry_times, tree_use_heap);
872 ZEND_WORKLIST_FREE_ALLOCA(&work, list_use_heap);
873 *flags |= flag;
874
875 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 */
886
