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