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
is_in_use_chain(zend_ssa * ssa,int var,int check)24 static inline bool is_in_use_chain(zend_ssa *ssa, int var, int check) {
25 int use;
26 FOREACH_USE(&ssa->vars[var], use) {
27 if (use == check) {
28 return 1;
29 }
30 } FOREACH_USE_END();
31 return 0;
32 }
33
is_in_phi_use_chain(zend_ssa * ssa,int var,zend_ssa_phi * check)34 static inline bool is_in_phi_use_chain(zend_ssa *ssa, int var, zend_ssa_phi *check) {
35 zend_ssa_phi *phi;
36 FOREACH_PHI_USE(&ssa->vars[var], phi) {
37 if (phi == check) {
38 return 1;
39 }
40 } FOREACH_PHI_USE_END();
41 return 0;
42 }
43
is_used_by_op(zend_ssa * ssa,int op,int check)44 static inline bool is_used_by_op(zend_ssa *ssa, int op, int check) {
45 zend_ssa_op *ssa_op = &ssa->ops[op];
46 return (ssa_op->op1_use == check)
47 || (ssa_op->op2_use == check)
48 || (ssa_op->result_use == check);
49 }
50
is_defined_by_op(zend_ssa * ssa,int op,int check)51 static inline bool is_defined_by_op(zend_ssa *ssa, int op, int check) {
52 zend_ssa_op *ssa_op = &ssa->ops[op];
53 return (ssa_op->op1_def == check)
54 || (ssa_op->op2_def == check)
55 || (ssa_op->result_def == check);
56 }
57
is_in_phi_sources(zend_ssa * ssa,zend_ssa_phi * phi,int check)58 static inline bool is_in_phi_sources(zend_ssa *ssa, zend_ssa_phi *phi, int check) {
59 int source;
60 FOREACH_PHI_SOURCE(phi, source) {
61 if (source == check) {
62 return 1;
63 }
64 } FOREACH_PHI_SOURCE_END();
65 return 0;
66 }
67
is_in_predecessors(zend_cfg * cfg,zend_basic_block * block,int check)68 static inline bool is_in_predecessors(zend_cfg *cfg, zend_basic_block *block, int check) {
69 int i, *predecessors = &cfg->predecessors[block->predecessor_offset];
70 for (i = 0; i < block->predecessors_count; i++) {
71 if (predecessors[i] == check) {
72 return 1;
73 }
74 }
75 return 0;
76 }
77
is_in_successors(zend_basic_block * block,int check)78 static inline bool is_in_successors(zend_basic_block *block, int check) {
79 int s;
80 for (s = 0; s < block->successors_count; s++) {
81 if (block->successors[s] == check) {
82 return 1;
83 }
84 }
85 return 0;
86 }
87
is_var_type(zend_uchar type)88 static inline bool is_var_type(zend_uchar type) {
89 return (type & (IS_CV|IS_VAR|IS_TMP_VAR)) != 0;
90 }
91
92 #define FAIL(...) do { \
93 if (status == SUCCESS) { \
94 fprintf(stderr, "\nIn function %s::%s (%s):\n", \
95 op_array->scope ? ZSTR_VAL(op_array->scope->name) : "", \
96 op_array->function_name ? ZSTR_VAL(op_array->function_name) : "{main}", extra); \
97 } \
98 fprintf(stderr, __VA_ARGS__); \
99 status = FAILURE; \
100 } while (0)
101
102 #define VARFMT "%d (%s%s)"
103 #define VAR(i) \
104 (i), (ssa->vars[i].var < op_array->last_var ? "CV $" : "TMP"), \
105 (ssa->vars[i].var < op_array->last_var ? ZSTR_VAL(op_array->vars[ssa->vars[i].var]) : "")
106
107 #define INSTRFMT "%d (%s)"
108 #define INSTR(i) \
109 (i), (zend_get_opcode_name(op_array->opcodes[i].opcode))
110
ssa_verify_integrity(zend_op_array * op_array,zend_ssa * ssa,const char * extra)111 int ssa_verify_integrity(zend_op_array *op_array, zend_ssa *ssa, const char *extra) {
112 zend_cfg *cfg = &ssa->cfg;
113 zend_ssa_phi *phi;
114 int i, status = SUCCESS;
115
116 /* Vars */
117 for (i = 0; i < ssa->vars_count; i++) {
118 zend_ssa_var *var = &ssa->vars[i];
119 int use, c;
120 uint32_t type = ssa->var_info[i].type;
121
122 if (var->definition < 0 && !var->definition_phi && i > op_array->last_var) {
123 if (var->use_chain >= 0) {
124 FAIL("var " VARFMT " without def has op uses\n", VAR(i));
125 }
126 if (var->phi_use_chain) {
127 FAIL("var " VARFMT " without def has phi uses\n", VAR(i));
128 }
129 }
130 if (var->definition >= 0 && var->definition_phi) {
131 FAIL("var " VARFMT " has both def and def_phi\n", VAR(i));
132 }
133 if (var->definition >= 0) {
134 if (!is_defined_by_op(ssa, var->definition, i)) {
135 FAIL("var " VARFMT " not defined by op " INSTRFMT "\n",
136 VAR(i), INSTR(var->definition));
137 }
138 }
139 if (var->definition_phi) {
140 if (var->definition_phi->ssa_var != i) {
141 FAIL("var " VARFMT " not defined by given phi\n", VAR(i));
142 }
143 }
144
145 c = 0;
146 FOREACH_USE(var, use) {
147 if (++c > 10000) {
148 FAIL("cycle in uses of " VARFMT "\n", VAR(i));
149 return status;
150 }
151 if (!is_used_by_op(ssa, use, i)) {
152 fprintf(stderr, "var " VARFMT " not in uses of op %d\n", VAR(i), use);
153 }
154 } FOREACH_USE_END();
155
156 c = 0;
157 FOREACH_PHI_USE(var, phi) {
158 if (++c > 10000) {
159 FAIL("cycle in phi uses of " VARFMT "\n", VAR(i));
160 return status;
161 }
162 if (!is_in_phi_sources(ssa, phi, i)) {
163 FAIL("var " VARFMT " not in phi sources of %d\n", VAR(i), phi->ssa_var);
164 }
165 } FOREACH_PHI_USE_END();
166
167 if ((type & MAY_BE_ARRAY_KEY_ANY) && !(type & MAY_BE_ARRAY_OF_ANY)) {
168 FAIL("var " VARFMT " has array key type but not value type\n", VAR(i));
169 }
170 if ((type & MAY_BE_ARRAY_OF_ANY) && !(type & MAY_BE_ARRAY_KEY_ANY)) {
171 FAIL("var " VARFMT " has array value type but not key type\n", VAR(i));
172 }
173 }
174
175 /* Instructions */
176 FOREACH_INSTR_NUM(i) {
177 zend_ssa_op *ssa_op = &ssa->ops[i];
178 zend_op *opline = &op_array->opcodes[i];
179 if (is_var_type(opline->op1_type)) {
180 if (ssa_op->op1_use < 0 && ssa_op->op1_def < 0) {
181 FAIL("var op1 of " INSTRFMT " does not use/def an ssa var\n", INSTR(i));
182 }
183 } else {
184 if (ssa_op->op1_use >= 0 || ssa_op->op1_def >= 0) {
185 FAIL("non-var op1 of " INSTRFMT " uses or defs an ssa var\n", INSTR(i));
186 }
187 }
188 if (is_var_type(opline->op2_type)) {
189 if (ssa_op->op2_use < 0 && ssa_op->op2_def < 0) {
190 FAIL("var op2 of " INSTRFMT " does not use/def an ssa var\n", INSTR(i));
191 }
192 } else {
193 if (ssa_op->op2_use >= 0 || ssa_op->op2_def >= 0) {
194 FAIL("non-var op2 of " INSTRFMT " uses or defs an ssa var\n", INSTR(i));
195 }
196 }
197 if (is_var_type(opline->result_type)) {
198 if (ssa_op->result_use < 0 && ssa_op->result_def < 0) {
199 FAIL("var result of " INSTRFMT " does not use/def an ssa var\n", INSTR(i));
200 }
201 } else {
202 if (ssa_op->result_use >= 0 || ssa_op->result_def >= 0) {
203 FAIL("non-var result of " INSTRFMT " uses or defs an ssa var\n", INSTR(i));
204 }
205 }
206
207 if (ssa_op->op1_use >= 0) {
208 if (ssa_op->op1_use >= ssa->vars_count) {
209 FAIL("op1 use %d out of range\n", ssa_op->op1_use);
210 }
211 if (!is_in_use_chain(ssa, ssa_op->op1_use, i)) {
212 FAIL("op1 use of " VARFMT " in " INSTRFMT " not in use chain\n",
213 VAR(ssa_op->op1_use), INSTR(i));
214 }
215 if (VAR_NUM(opline->op1.var) != ssa->vars[ssa_op->op1_use].var) {
216 FAIL("op1 use of " VARFMT " does not match op %d of " INSTRFMT "\n",
217 VAR(ssa_op->op1_use), VAR_NUM(opline->op1.var), INSTR(i));
218 }
219 }
220 if (ssa_op->op2_use >= 0) {
221 if (ssa_op->op2_use >= ssa->vars_count) {
222 FAIL("op2 use %d out of range\n", ssa_op->op2_use);
223 }
224 if (!is_in_use_chain(ssa, ssa_op->op2_use, i)) {
225 FAIL("op2 use of " VARFMT " in " INSTRFMT " not in use chain\n",
226 VAR(ssa_op->op2_use), INSTR(i));
227 }
228 if (VAR_NUM(opline->op2.var) != ssa->vars[ssa_op->op2_use].var) {
229 FAIL("op2 use of " VARFMT " does not match op %d of " INSTRFMT "\n",
230 VAR(ssa_op->op2_use), VAR_NUM(opline->op2.var), INSTR(i));
231 }
232 }
233 if (ssa_op->result_use >= 0) {
234 if (ssa_op->result_use >= ssa->vars_count) {
235 FAIL("result use %d out of range\n", ssa_op->result_use);
236 }
237 if (!is_in_use_chain(ssa, ssa_op->result_use, i)) {
238 FAIL("result use of " VARFMT " in " INSTRFMT " not in use chain\n",
239 VAR(ssa_op->result_use), INSTR(i));
240 }
241 if (VAR_NUM(opline->result.var) != ssa->vars[ssa_op->result_use].var) {
242 FAIL("result use of " VARFMT " does not match op %d of " INSTRFMT "\n",
243 VAR(ssa_op->result_use), VAR_NUM(opline->result.var), INSTR(i));
244 }
245 }
246 if (ssa_op->op1_def >= 0) {
247 if (ssa_op->op1_def >= ssa->vars_count) {
248 FAIL("op1 def %d out of range\n", ssa_op->op1_def);
249 }
250 if (ssa->vars[ssa_op->op1_def].definition != i) {
251 FAIL("op1 def of " VARFMT " in " INSTRFMT " invalid\n",
252 VAR(ssa_op->op1_def), INSTR(i));
253 }
254 if (VAR_NUM(opline->op1.var) != ssa->vars[ssa_op->op1_def].var) {
255 FAIL("op1 def of " VARFMT " does not match op %d of " INSTRFMT "\n",
256 VAR(ssa_op->op1_def), VAR_NUM(opline->op1.var), INSTR(i));
257 }
258 }
259 if (ssa_op->op2_def >= 0) {
260 if (ssa_op->op2_def >= ssa->vars_count) {
261 FAIL("op2 def %d out of range\n", ssa_op->op2_def);
262 }
263 if (ssa->vars[ssa_op->op2_def].definition != i) {
264 FAIL("op2 def of " VARFMT " in " INSTRFMT " invalid\n",
265 VAR(ssa_op->op2_def), INSTR(i));
266 }
267 if (VAR_NUM(opline->op2.var) != ssa->vars[ssa_op->op2_def].var) {
268 FAIL("op2 def of " VARFMT " does not match op %d of " INSTRFMT "\n",
269 VAR(ssa_op->op2_def), VAR_NUM(opline->op2.var), INSTR(i));
270 }
271 }
272 if (ssa_op->result_def >= 0) {
273 if (ssa_op->result_def >= ssa->vars_count) {
274 FAIL("result def %d out of range\n", ssa_op->result_def);
275 }
276 if (ssa->vars[ssa_op->result_def].definition != i) {
277 FAIL("result def of " VARFMT " in " INSTRFMT " invalid\n",
278 VAR(ssa_op->result_def), INSTR(i));
279 }
280 if (VAR_NUM(opline->result.var) != ssa->vars[ssa_op->result_def].var) {
281 FAIL("result def of " VARFMT " does not match op %d of " INSTRFMT "\n",
282 VAR(ssa_op->result_def), VAR_NUM(opline->result.var), INSTR(i));
283 }
284 }
285 } FOREACH_INSTR_NUM_END();
286
287 /* Phis */
288 FOREACH_PHI(phi) {
289 unsigned num_sources = NUM_PHI_SOURCES(phi);
290 for (i = 0; i < num_sources; i++) {
291 int source = phi->sources[i];
292 if (source < 0) {
293 FAIL(VARFMT " negative source\n", VAR(phi->ssa_var));
294 }
295 if (!is_in_phi_use_chain(ssa, source, phi)) {
296 FAIL(VARFMT " not in phi use chain of %d\n", VAR(phi->ssa_var), source);
297 }
298 if (ssa->vars[source].var != ssa->vars[phi->ssa_var].var) {
299 FAIL(VARFMT " source of phi for " VARFMT "\n", VAR(source), VAR(phi->ssa_var));
300 }
301 if (phi->use_chains[i]) {
302 int j;
303 for (j = i + 1; j < num_sources; j++) {
304 if (phi->sources[j] == source && phi->use_chains[j]) {
305 FAIL("use chain for source " VARFMT " of phi " VARFMT
306 " at %d despite earlier use\n", VAR(source), VAR(phi->ssa_var), j);
307 }
308 }
309 }
310 }
311 if (ssa->vars[phi->ssa_var].definition_phi != phi) {
312 FAIL(VARFMT " does not define this phi\n", VAR(phi->ssa_var));
313 }
314 } FOREACH_PHI_END();
315
316 /* Blocks */
317 for (i = 0; i < cfg->blocks_count; i++) {
318 zend_basic_block *block = &cfg->blocks[i];
319 int *predecessors = &cfg->predecessors[block->predecessor_offset];
320 int s, j;
321
322 if (i != 0 && block->start < (block-1)->start + (block-1)->len) {
323 FAIL("Block %d start %d smaller previous end %d\n",
324 i, block->start, (block-1)->start + (block-1)->len);
325 }
326 if (i != cfg->blocks_count-1 && block->start + block->len > (block+1)->start) {
327 FAIL("Block %d end %d greater next start %d\n",
328 i, block->start + block->len, (block+1)->start);
329 }
330
331 for (j = block->start; j < block->start + block->len; j++) {
332 if (cfg->map[j] != i) {
333 FAIL("Instr " INSTRFMT " not associated with block %d\n", INSTR(j), i);
334 }
335 }
336
337 if (!(block->flags & ZEND_BB_REACHABLE)) {
338 if (ssa->blocks[i].phis) {
339 FAIL("Unreachable block %d has phis\n", i);
340 }
341 continue;
342 }
343
344 for (s = 0; s < block->successors_count; s++) {
345 zend_basic_block *next_block;
346 if (block->successors[s] < 0) {
347 FAIL("Successor number %d of %d negative", s, i);
348 }
349 next_block = &cfg->blocks[block->successors[s]];
350 if (!(next_block->flags & ZEND_BB_REACHABLE)) {
351 FAIL("Successor %d of %d not reachable\n", block->successors[s], i);
352 }
353 if (!is_in_predecessors(cfg, next_block, i)) {
354 FAIL("Block %d predecessors missing %d\n", block->successors[s], i);
355 }
356 }
357
358 for (j = 0; j < block->predecessors_count; j++) {
359 if (predecessors[j] >= 0) {
360 int k;
361 zend_basic_block *prev_block = &cfg->blocks[predecessors[j]];
362 if (!(prev_block->flags & ZEND_BB_REACHABLE)) {
363 FAIL("Predecessor %d of %d not reachable\n", predecessors[j], i);
364 }
365 if (!is_in_successors(prev_block, i)) {
366 FAIL("Block %d successors missing %d\n", predecessors[j], i);
367 }
368 for (k = 0; k < block->predecessors_count; k++) {
369 if (k != j && predecessors[k] == predecessors[j]) {
370 FAIL("Block %d has duplicate predecessor %d\n", i, predecessors[j]);
371 }
372 }
373 }
374 }
375 }
376
377 return status;
378 }
379
