Coverage Report

Created: 2025-06-13 06:43

/src/php-src/Zend/Optimizer/ssa_integrity.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
   +----------------------------------------------------------------------+
3
   | Zend Engine, SSA validation                                          |
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: Nikita Popov <nikic@php.net>                                |
16
   +----------------------------------------------------------------------+
17
*/
18
19
#include "Optimizer/zend_optimizer_internal.h"
20
21
/* The ssa_verify_integrity() function ensures that that certain invariants of the SSA form and
22
 * CFG are upheld and prints messages to stderr if this is not the case. */
23
24
5.68M
static inline bool is_in_use_chain(zend_ssa *ssa, int var, int check) {
25
5.68M
  int use;
26
24.0M
  FOREACH_USE(&ssa->vars[var], use) {
27
24.0M
    if (use == check) {
28
5.68M
      return 1;
29
5.68M
    }
30
24.0M
  } FOREACH_USE_END();
31
0
  return 0;
32
5.68M
}
33
34
1.57M
static inline bool is_in_phi_use_chain(zend_ssa *ssa, int var, zend_ssa_phi *check) {
35
1.57M
  zend_ssa_phi *phi;
36
3.43M
  FOREACH_PHI_USE(&ssa->vars[var], phi) {
37
3.43M
    if (phi == check) {
38
1.57M
      return 1;
39
1.57M
    }
40
3.43M
  } FOREACH_PHI_USE_END();
41
0
  return 0;
42
1.57M
}
43
44
5.67M
static inline bool is_used_by_op(zend_ssa *ssa, int op, int check) {
45
5.67M
  zend_ssa_op *ssa_op = &ssa->ops[op];
46
5.67M
  return (ssa_op->op1_use == check)
47
5.67M
    || (ssa_op->op2_use == check)
48
5.67M
    || (ssa_op->result_use == check);
49
5.67M
}
50
51
4.38M
static inline bool is_defined_by_op(zend_ssa *ssa, int op, int check) {
52
4.38M
  zend_ssa_op *ssa_op = &ssa->ops[op];
53
4.38M
  return (ssa_op->op1_def == check)
54
4.38M
    || (ssa_op->op2_def == check)
55
4.38M
    || (ssa_op->result_def == check);
56
4.38M
}
57
58
1.57M
static inline bool is_in_phi_sources(zend_ssa *ssa, zend_ssa_phi *phi, int check) {
59
1.57M
  int source;
60
6.04M
  FOREACH_PHI_SOURCE(phi, source) {
61
6.04M
    if (source == check) {
62
1.57M
      return 1;
63
1.57M
    }
64
6.04M
  } FOREACH_PHI_SOURCE_END();
65
0
  return 0;
66
1.57M
}
67
68
1.11M
static inline bool is_in_predecessors(zend_cfg *cfg, zend_basic_block *block, int check) {
69
1.11M
  int i, *predecessors = &cfg->predecessors[block->predecessor_offset];
70
1.48M
  for (i = 0; i < block->predecessors_count; i++) {
71
1.48M
    if (predecessors[i] == check) {
72
1.11M
      return 1;
73
1.11M
    }
74
1.48M
  }
75
0
  return 0;
76
1.11M
}
77
78
1.10M
static inline bool is_in_successors(zend_basic_block *block, int check) {
79
1.10M
  int s;
80
1.48M
  for (s = 0; s < block->successors_count; s++) {
81
1.48M
    if (block->successors[s] == check) {
82
1.10M
      return 1;
83
1.10M
    }
84
1.48M
  }
85
0
  return 0;
86
1.10M
}
87
88
20.8M
static inline bool is_var_type(uint8_t type) {
89
20.8M
  return (type & (IS_CV|IS_VAR|IS_TMP_VAR)) != 0;
90
20.8M
}
91
92
5.68M
static inline bool is_defined(const zend_ssa *ssa, const zend_op_array *op_array, int var) {
93
5.68M
  const zend_ssa_var *ssa_var = &ssa->vars[var];
94
5.68M
  return ssa_var->definition >= 0 || ssa_var->definition_phi || var < op_array->last_var;
95
5.68M
}
96
97
0
#define FAIL(...) do { \
98
0
  if (status == SUCCESS) { \
99
0
    fprintf(stderr, "\nIn function %s::%s (%s):\n", \
100
0
      op_array->scope ? ZSTR_VAL(op_array->scope->name) : "", \
101
0
      op_array->function_name ? ZSTR_VAL(op_array->function_name) : "{main}", extra); \
102
0
  } \
103
0
  fprintf(stderr, __VA_ARGS__); \
104
0
  status = FAILURE; \
105
0
} while (0)
106
107
#define VARFMT "%d (%s%s)"
108
#define VAR(i) \
109
0
  (i), (ssa->vars[i].var < op_array->last_var ? "CV $" : "TMP"), \
110
0
  (ssa->vars[i].var < op_array->last_var ? ZSTR_VAL(op_array->vars[ssa->vars[i].var]) : "")
111
112
#define INSTRFMT "%d (%s)"
113
#define INSTR(i) \
114
  (i), (zend_get_opcode_name(op_array->opcodes[i].opcode))
115
116
376k
void ssa_verify_integrity(zend_op_array *op_array, zend_ssa *ssa, const char *extra) {
117
376k
  zend_cfg *cfg = &ssa->cfg;
118
376k
  zend_ssa_phi *phi;
119
376k
  int i;
120
376k
  zend_result status = SUCCESS;
121
122
  /* Vars */
123
6.32M
  for (i = 0; i < ssa->vars_count; i++) {
124
5.95M
    zend_ssa_var *var = &ssa->vars[i];
125
5.95M
    int use;
126
5.95M
    uint32_t type = ssa->var_info[i].type;
127
128
5.95M
    if (var->definition < 0 && !var->definition_phi && i > op_array->last_var) {
129
92.7k
      if (var->use_chain >= 0) {
130
0
        FAIL("var " VARFMT " without def has op uses\n", VAR(i));
131
0
      }
132
92.7k
      if (var->phi_use_chain) {
133
0
        FAIL("var " VARFMT " without def has phi uses\n", VAR(i));
134
0
      }
135
92.7k
    }
136
5.95M
    if (var->definition >= 0 && var->definition_phi) {
137
0
      FAIL("var " VARFMT " has both def and def_phi\n", VAR(i));
138
0
    }
139
5.95M
    if (var->definition >= 0) {
140
4.38M
      if (!is_defined_by_op(ssa, var->definition, i)) {
141
0
        FAIL("var " VARFMT " not defined by op " INSTRFMT "\n",
142
0
            VAR(i), INSTR(var->definition));
143
0
      }
144
4.38M
    }
145
5.95M
    if (var->definition_phi) {
146
926k
      if (var->definition_phi->ssa_var != i) {
147
0
        FAIL("var " VARFMT " not defined by given phi\n", VAR(i));
148
0
      }
149
926k
    }
150
151
    /* Floyd's cycle detection algorithm, applied for use chain. */
152
5.95M
    use = var->use_chain;
153
5.95M
    int second_use = use;
154
6.55M
    while (use >= 0 && second_use >= 0) {
155
5.06M
      use = zend_ssa_next_use(ssa->ops, var - ssa->vars, use);
156
5.06M
      second_use = zend_ssa_next_use(ssa->ops, var - ssa->vars, second_use);
157
5.06M
      if (second_use < 0) {
158
4.46M
        break;
159
4.46M
      }
160
604k
      second_use = zend_ssa_next_use(ssa->ops, var - ssa->vars, second_use);
161
604k
      if (use == second_use) {
162
0
        FAIL("cycle in uses of " VARFMT "\n", VAR(i));
163
0
        goto finish;
164
0
      }
165
604k
    }
166
167
11.6M
    FOREACH_USE(var, use) {
168
11.6M
      if (!is_used_by_op(ssa, use, i)) {
169
0
        fprintf(stderr, "var " VARFMT " not in uses of op %d\n", VAR(i), use);
170
0
      }
171
11.6M
    } FOREACH_USE_END();
172
173
    /* Floyd's cycle detection algorithm, applied for phi nodes. */
174
5.95M
    phi = var->phi_use_chain;
175
5.95M
    zend_ssa_phi *second_phi = phi;
176
6.22M
    while (phi && second_phi) {
177
1.30M
      phi = zend_ssa_next_use_phi(ssa, var - ssa->vars, phi);
178
1.30M
      second_phi = zend_ssa_next_use_phi(ssa, var - ssa->vars, second_phi);
179
1.30M
      if (!second_phi) {
180
1.03M
        break;
181
1.03M
      }
182
268k
      second_phi = zend_ssa_next_use_phi(ssa, var - ssa->vars, second_phi);
183
268k
      if (phi == second_phi) {
184
0
        FAIL("cycle in phi uses of " VARFMT "\n", VAR(i));
185
0
        goto finish;
186
0
      }
187
268k
    }
188
189
7.52M
    FOREACH_PHI_USE(var, phi) {
190
7.52M
      if (!is_in_phi_sources(ssa, phi, i)) {
191
0
        FAIL("var " VARFMT " not in phi sources of %d\n", VAR(i), phi->ssa_var);
192
0
      }
193
7.52M
    } FOREACH_PHI_USE_END();
194
195
5.95M
    if ((type & (MAY_BE_ARRAY_KEY_ANY-MAY_BE_ARRAY_EMPTY)) && !(type & MAY_BE_ARRAY_OF_ANY)) {
196
0
      FAIL("var " VARFMT " has array key type but not value type\n", VAR(i));
197
0
    }
198
5.95M
    if ((type & MAY_BE_ARRAY_OF_ANY) && !(type & (MAY_BE_ARRAY_KEY_ANY-MAY_BE_ARRAY_EMPTY))) {
199
0
      FAIL("var " VARFMT " has array value type but not key type\n", VAR(i));
200
0
    }
201
5.95M
    if ((type & MAY_BE_REF) && ssa->var_info[i].ce) {
202
0
      FAIL("var " VARFMT " may be ref but has ce\n", VAR(i));
203
0
    }
204
5.95M
  }
205
206
  /* Instructions */
207
9.98M
  FOREACH_INSTR_NUM(i) {
208
9.98M
    zend_ssa_op *ssa_op = &ssa->ops[i];
209
9.98M
    zend_op *opline = &op_array->opcodes[i];
210
9.98M
    if (is_var_type(opline->op1_type)) {
211
4.18M
      if (ssa_op->op1_use < 0 && ssa_op->op1_def < 0) {
212
0
        FAIL("var op1 of " INSTRFMT " does not use/def an ssa var\n", INSTR(i));
213
0
      }
214
4.18M
    } else {
215
2.78M
      if (ssa_op->op1_use >= 0 || ssa_op->op1_def >= 0) {
216
0
        FAIL("non-var op1 of " INSTRFMT " uses or defs an ssa var\n", INSTR(i));
217
0
      }
218
2.78M
    }
219
9.98M
    if (is_var_type(opline->op2_type)) {
220
1.41M
      if (ssa_op->op2_use < 0 && ssa_op->op2_def < 0) {
221
0
        FAIL("var op2 of " INSTRFMT " does not use/def an ssa var\n", INSTR(i));
222
0
      }
223
5.55M
    } else {
224
5.55M
      if (ssa_op->op2_use >= 0 || ssa_op->op2_def >= 0) {
225
0
        FAIL("non-var op2 of " INSTRFMT " uses or defs an ssa var\n", INSTR(i));
226
0
      }
227
5.55M
    }
228
9.98M
    if (is_var_type(opline->result_type)) {
229
3.84M
      if (ssa_op->result_use < 0 && ssa_op->result_def < 0) {
230
0
        FAIL("var result of " INSTRFMT " does not use/def an ssa var\n", INSTR(i));
231
0
      }
232
3.84M
    } else {
233
3.12M
      if (ssa_op->result_use >= 0 || ssa_op->result_def >= 0) {
234
0
        FAIL("non-var result of " INSTRFMT " uses or defs an ssa var\n", INSTR(i));
235
0
      }
236
3.12M
    }
237
238
9.98M
    if (ssa_op->op1_use >= 0) {
239
4.18M
      if (ssa_op->op1_use >= ssa->vars_count) {
240
0
        FAIL("op1 use %d out of range\n", ssa_op->op1_use);
241
0
      }
242
4.18M
      if (!is_defined(ssa, op_array, ssa_op->op1_use)) {
243
0
        FAIL("op1 use of " VARFMT " in " INSTRFMT " is not defined\n",
244
0
            VAR(ssa_op->op1_use), INSTR(i));
245
0
      }
246
4.18M
      if (!is_in_use_chain(ssa, ssa_op->op1_use, i)) {
247
0
        FAIL("op1 use of " VARFMT " in " INSTRFMT " not in use chain\n",
248
0
            VAR(ssa_op->op1_use), INSTR(i));
249
0
      }
250
4.18M
      if (VAR_NUM(opline->op1.var) != ssa->vars[ssa_op->op1_use].var) {
251
0
        FAIL("op1 use of " VARFMT " does not match op %d of " INSTRFMT "\n",
252
0
            VAR(ssa_op->op1_use), VAR_NUM(opline->op1.var), INSTR(i));
253
0
      }
254
4.18M
    }
255
9.98M
    if (ssa_op->op2_use >= 0) {
256
1.40M
      if (ssa_op->op2_use >= ssa->vars_count) {
257
0
        FAIL("op2 use %d out of range\n", ssa_op->op2_use);
258
0
      }
259
1.40M
      if (!is_defined(ssa, op_array, ssa_op->op2_use)) {
260
0
        FAIL("op2 use of " VARFMT " in " INSTRFMT " is not defined\n",
261
0
            VAR(ssa_op->op2_use), INSTR(i));
262
0
      }
263
1.40M
      if (!is_in_use_chain(ssa, ssa_op->op2_use, i)) {
264
0
        FAIL("op2 use of " VARFMT " in " INSTRFMT " not in use chain\n",
265
0
            VAR(ssa_op->op2_use), INSTR(i));
266
0
      }
267
1.40M
      if (VAR_NUM(opline->op2.var) != ssa->vars[ssa_op->op2_use].var) {
268
0
        FAIL("op2 use of " VARFMT " does not match op %d of " INSTRFMT "\n",
269
0
            VAR(ssa_op->op2_use), VAR_NUM(opline->op2.var), INSTR(i));
270
0
      }
271
1.40M
    }
272
9.98M
    if (ssa_op->result_use >= 0) {
273
88.0k
      if (ssa_op->result_use >= ssa->vars_count) {
274
0
        FAIL("result use %d out of range\n", ssa_op->result_use);
275
0
      }
276
88.0k
      if (!is_defined(ssa, op_array, ssa_op->result_use)) {
277
0
        FAIL("result use of " VARFMT " in " INSTRFMT " is not defined\n",
278
0
            VAR(ssa_op->result_use), INSTR(i));
279
0
      }
280
88.0k
      if (!is_in_use_chain(ssa, ssa_op->result_use, i)) {
281
0
        FAIL("result use of " VARFMT " in " INSTRFMT " not in use chain\n",
282
0
          VAR(ssa_op->result_use), INSTR(i));
283
0
      }
284
88.0k
      if (VAR_NUM(opline->result.var) != ssa->vars[ssa_op->result_use].var) {
285
0
        FAIL("result use of " VARFMT " does not match op %d of " INSTRFMT "\n",
286
0
            VAR(ssa_op->result_use), VAR_NUM(opline->result.var), INSTR(i));
287
0
      }
288
88.0k
    }
289
9.98M
    if (ssa_op->op1_def >= 0) {
290
515k
      if (ssa_op->op1_def >= ssa->vars_count) {
291
0
        FAIL("op1 def %d out of range\n", ssa_op->op1_def);
292
0
      }
293
515k
      if (ssa->vars[ssa_op->op1_def].definition != i) {
294
0
        FAIL("op1 def of " VARFMT " in " INSTRFMT " invalid\n",
295
0
            VAR(ssa_op->op1_def), INSTR(i));
296
0
      }
297
515k
      if (VAR_NUM(opline->op1.var) != ssa->vars[ssa_op->op1_def].var) {
298
0
        FAIL("op1 def of " VARFMT " does not match op %d of " INSTRFMT "\n",
299
0
            VAR(ssa_op->op1_def), VAR_NUM(opline->op1.var), INSTR(i));
300
0
      }
301
515k
    }
302
9.98M
    if (ssa_op->op2_def >= 0) {
303
24.0k
      if (ssa_op->op2_def >= ssa->vars_count) {
304
0
        FAIL("op2 def %d out of range\n", ssa_op->op2_def);
305
0
      }
306
24.0k
      if (ssa->vars[ssa_op->op2_def].definition != i) {
307
0
        FAIL("op2 def of " VARFMT " in " INSTRFMT " invalid\n",
308
0
            VAR(ssa_op->op2_def), INSTR(i));
309
0
      }
310
24.0k
      if (VAR_NUM(opline->op2.var) != ssa->vars[ssa_op->op2_def].var) {
311
0
        FAIL("op2 def of " VARFMT " does not match op %d of " INSTRFMT "\n",
312
0
            VAR(ssa_op->op2_def), VAR_NUM(opline->op2.var), INSTR(i));
313
0
      }
314
24.0k
    }
315
9.98M
    if (ssa_op->result_def >= 0) {
316
3.84M
      if (ssa_op->result_def >= ssa->vars_count) {
317
0
        FAIL("result def %d out of range\n", ssa_op->result_def);
318
0
      }
319
3.84M
      if (ssa->vars[ssa_op->result_def].definition != i) {
320
0
        FAIL("result def of " VARFMT " in " INSTRFMT " invalid\n",
321
0
            VAR(ssa_op->result_def), INSTR(i));
322
0
      }
323
3.84M
      if (VAR_NUM(opline->result.var) != ssa->vars[ssa_op->result_def].var) {
324
0
        FAIL("result def of " VARFMT " does not match op %d of " INSTRFMT "\n",
325
0
            VAR(ssa_op->result_def), VAR_NUM(opline->result.var), INSTR(i));
326
0
      }
327
3.84M
    }
328
9.98M
  } FOREACH_INSTR_NUM_END();
329
330
  /* Phis */
331
2.44M
  FOREACH_PHI(phi) {
332
2.44M
    unsigned num_sources = NUM_PHI_SOURCES(phi);
333
2.50M
    for (i = 0; i < num_sources; i++) {
334
1.57M
      int source = phi->sources[i];
335
1.57M
      if (source < 0) {
336
0
        FAIL(VARFMT " negative source\n", VAR(phi->ssa_var));
337
0
      }
338
1.57M
      if (!is_in_phi_use_chain(ssa, source, phi)) {
339
0
        FAIL(VARFMT " not in phi use chain of %d\n", VAR(phi->ssa_var), source);
340
0
      }
341
1.57M
      if (ssa->vars[source].var != ssa->vars[phi->ssa_var].var) {
342
0
        FAIL(VARFMT " source of phi for " VARFMT "\n", VAR(source), VAR(phi->ssa_var));
343
0
      }
344
1.57M
      if (phi->use_chains[i]) {
345
271k
        int j;
346
525k
        for (j = i + 1; j < num_sources; j++) {
347
254k
          if (phi->sources[j] == source && phi->use_chains[j]) {
348
0
            FAIL("use chain for source " VARFMT " of phi " VARFMT
349
0
              " at %d despite earlier use\n", VAR(source), VAR(phi->ssa_var), j);
350
0
          }
351
254k
        }
352
271k
      }
353
1.57M
    }
354
2.44M
    if (ssa->vars[phi->ssa_var].definition_phi != phi) {
355
0
      FAIL(VARFMT " does not define this phi\n", VAR(phi->ssa_var));
356
0
    }
357
2.44M
  } FOREACH_PHI_END();
358
359
  /* Blocks */
360
1.51M
  for (i = 0; i < cfg->blocks_count; i++) {
361
1.13M
    zend_basic_block *block = &cfg->blocks[i];
362
1.13M
    int *predecessors = &cfg->predecessors[block->predecessor_offset];
363
1.13M
    int s, j;
364
365
1.13M
    if (i != 0 && block->start < (block-1)->start + (block-1)->len) {
366
0
      FAIL("Block %d start %d smaller previous end %d\n",
367
0
        i, block->start, (block-1)->start + (block-1)->len);
368
0
    }
369
1.13M
    if (i != cfg->blocks_count-1 && block->start + block->len > (block+1)->start) {
370
0
      FAIL("Block %d end %d greater next start %d\n",
371
0
        i, block->start + block->len, (block+1)->start);
372
0
    }
373
374
8.11M
    for (j = block->start; j < block->start + block->len; j++) {
375
6.97M
      if (cfg->map[j] != i) {
376
0
        FAIL("Instr " INSTRFMT " not associated with block %d\n", INSTR(j), i);
377
0
      }
378
6.97M
    }
379
380
1.13M
    if (!(block->flags & ZEND_BB_REACHABLE)) {
381
12.1k
      if (ssa->blocks[i].phis) {
382
0
        FAIL("Unreachable block %d has phis\n", i);
383
0
      }
384
12.1k
      continue;
385
12.1k
    }
386
387
2.23M
    for (s = 0; s < block->successors_count; s++) {
388
1.11M
      zend_basic_block *next_block;
389
1.11M
      if (block->successors[s] < 0) {
390
0
        FAIL("Successor number %d of %d negative", s, i);
391
0
      }
392
1.11M
      next_block = &cfg->blocks[block->successors[s]];
393
1.11M
      if (!(next_block->flags & ZEND_BB_REACHABLE)) {
394
0
        FAIL("Successor %d of %d not reachable\n", block->successors[s], i);
395
0
      }
396
1.11M
      if (!is_in_predecessors(cfg, next_block, i)) {
397
0
        FAIL("Block %d predecessors missing %d\n", block->successors[s], i);
398
0
      }
399
1.11M
    }
400
401
2.23M
    for (j = 0; j < block->predecessors_count; j++) {
402
1.10M
      if (predecessors[j] >= 0) {
403
1.10M
        int k;
404
1.10M
        zend_basic_block *prev_block = &cfg->blocks[predecessors[j]];
405
1.10M
        if (!(prev_block->flags & ZEND_BB_REACHABLE)) {
406
0
          FAIL("Predecessor %d of %d not reachable\n", predecessors[j], i);
407
0
        }
408
1.10M
        if (!is_in_successors(prev_block, i)) {
409
0
          FAIL("Block %d successors missing %d\n", predecessors[j], i);
410
0
        }
411
2.96M
        for (k = 0; k < block->predecessors_count; k++) {
412
1.85M
          if (k != j && predecessors[k] == predecessors[j]) {
413
0
            FAIL("Block %d has duplicate predecessor %d\n", i, predecessors[j]);
414
0
          }
415
1.85M
        }
416
1.10M
      }
417
1.10M
    }
418
1.12M
  }
419
420
376k
finish:
421
376k
  if (status == FAILURE) {
422
0
    zend_dump_op_array(op_array, ZEND_DUMP_SSA, "at SSA integrity verification", ssa);
423
0
    ZEND_ASSERT(0 && "SSA integrity verification failed");
424
0
  }
425
376k
}