Coverage Report

Created: 2025-06-13 06:43

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