xref: /PHP-8.4/Zend/Optimizer/ssa_integrity.c (revision 7585cf69)
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(uint8_t type)88 static inline bool is_var_type(uint8_t type) {
89 	return (type & (IS_CV|IS_VAR|IS_TMP_VAR)) != 0;
90 }
91 
is_defined(const zend_ssa * ssa,const zend_op_array * op_array,int var)92 static inline bool is_defined(const zend_ssa *ssa, const zend_op_array *op_array, int var) {
93 	const zend_ssa_var *ssa_var = &ssa->vars[var];
94 	return ssa_var->definition >= 0 || ssa_var->definition_phi || var < op_array->last_var;
95 }
96 
97 #define FAIL(...) do { \
98 	if (status == SUCCESS) { \
99 		fprintf(stderr, "\nIn function %s::%s (%s):\n", \
100 			op_array->scope ? ZSTR_VAL(op_array->scope->name) : "", \
101 			op_array->function_name ? ZSTR_VAL(op_array->function_name) : "{main}", extra); \
102 	} \
103 	fprintf(stderr, __VA_ARGS__); \
104 	status = FAILURE; \
105 } while (0)
106 
107 #define VARFMT "%d (%s%s)"
108 #define VAR(i) \
109 	(i), (ssa->vars[i].var < op_array->last_var ? "CV $" : "TMP"), \
110 	(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 
ssa_verify_integrity(zend_op_array * op_array,zend_ssa * ssa,const char * extra)116 void ssa_verify_integrity(zend_op_array *op_array, zend_ssa *ssa, const char *extra) {
117 	zend_cfg *cfg = &ssa->cfg;
118 	zend_ssa_phi *phi;
119 	int i;
120 	zend_result status = SUCCESS;
121 
122 	/* Vars */
123 	for (i = 0; i < ssa->vars_count; i++) {
124 		zend_ssa_var *var = &ssa->vars[i];
125 		int use;
126 		uint32_t type = ssa->var_info[i].type;
127 
128 		if (var->definition < 0 && !var->definition_phi && i > op_array->last_var) {
129 			if (var->use_chain >= 0) {
130 				FAIL("var " VARFMT " without def has op uses\n", VAR(i));
131 			}
132 			if (var->phi_use_chain) {
133 				FAIL("var " VARFMT " without def has phi uses\n", VAR(i));
134 			}
135 		}
136 		if (var->definition >= 0 && var->definition_phi) {
137 			FAIL("var " VARFMT " has both def and def_phi\n", VAR(i));
138 		}
139 		if (var->definition >= 0) {
140 			if (!is_defined_by_op(ssa, var->definition, i)) {
141 				FAIL("var " VARFMT " not defined by op " INSTRFMT "\n",
142 						VAR(i), INSTR(var->definition));
143 			}
144 		}
145 		if (var->definition_phi) {
146 			if (var->definition_phi->ssa_var != i) {
147 				FAIL("var " VARFMT " not defined by given phi\n", VAR(i));
148 			}
149 		}
150 
151 		/* Floyd's cycle detection algorithm, applied for use chain. */
152 		use = var->use_chain;
153 		int second_use = use;
154 		while (use >= 0 && second_use >= 0) {
155 			use = zend_ssa_next_use(ssa->ops, var - ssa->vars, use);
156 			second_use = zend_ssa_next_use(ssa->ops, var - ssa->vars, second_use);
157 			if (second_use < 0) {
158 				break;
159 			}
160 			second_use = zend_ssa_next_use(ssa->ops, var - ssa->vars, second_use);
161 			if (use == second_use) {
162 				FAIL("cycle in uses of " VARFMT "\n", VAR(i));
163 				goto finish;
164 			}
165 		}
166 
167 		FOREACH_USE(var, use) {
168 			if (!is_used_by_op(ssa, use, i)) {
169 				fprintf(stderr, "var " VARFMT " not in uses of op %d\n", VAR(i), use);
170 			}
171 		} FOREACH_USE_END();
172 
173 		/* Floyd's cycle detection algorithm, applied for phi nodes. */
174 		phi = var->phi_use_chain;
175 		zend_ssa_phi *second_phi = phi;
176 		while (phi && second_phi) {
177 			phi = zend_ssa_next_use_phi(ssa, var - ssa->vars, phi);
178 			second_phi = zend_ssa_next_use_phi(ssa, var - ssa->vars, second_phi);
179 			if (!second_phi) {
180 				break;
181 			}
182 			second_phi = zend_ssa_next_use_phi(ssa, var - ssa->vars, second_phi);
183 			if (phi == second_phi) {
184 				FAIL("cycle in phi uses of " VARFMT "\n", VAR(i));
185 				goto finish;
186 			}
187 		}
188 
189 		FOREACH_PHI_USE(var, phi) {
190 			if (!is_in_phi_sources(ssa, phi, i)) {
191 				FAIL("var " VARFMT " not in phi sources of %d\n", VAR(i), phi->ssa_var);
192 			}
193 		} FOREACH_PHI_USE_END();
194 
195 		if ((type & (MAY_BE_ARRAY_KEY_ANY-MAY_BE_ARRAY_EMPTY)) && !(type & MAY_BE_ARRAY_OF_ANY)) {
196 			FAIL("var " VARFMT " has array key type but not value type\n", VAR(i));
197 		}
198 		if ((type & MAY_BE_ARRAY_OF_ANY) && !(type & (MAY_BE_ARRAY_KEY_ANY-MAY_BE_ARRAY_EMPTY))) {
199 			FAIL("var " VARFMT " has array value type but not key type\n", VAR(i));
200 		}
201 		if ((type & MAY_BE_REF) && ssa->var_info[i].ce) {
202 			FAIL("var " VARFMT " may be ref but has ce\n", VAR(i));
203 		}
204 	}
205 
206 	/* Instructions */
207 	FOREACH_INSTR_NUM(i) {
208 		zend_ssa_op *ssa_op = &ssa->ops[i];
209 		zend_op *opline = &op_array->opcodes[i];
210 		if (is_var_type(opline->op1_type)) {
211 			if (ssa_op->op1_use < 0 && ssa_op->op1_def < 0) {
212 				FAIL("var op1 of " INSTRFMT " does not use/def an ssa var\n", INSTR(i));
213 			}
214 		} else {
215 			if (ssa_op->op1_use >= 0 || ssa_op->op1_def >= 0) {
216 				FAIL("non-var op1 of " INSTRFMT " uses or defs an ssa var\n", INSTR(i));
217 			}
218 		}
219 		if (is_var_type(opline->op2_type)) {
220 			if (ssa_op->op2_use < 0 && ssa_op->op2_def < 0) {
221 				FAIL("var op2 of " INSTRFMT " does not use/def an ssa var\n", INSTR(i));
222 			}
223 		} else {
224 			if (ssa_op->op2_use >= 0 || ssa_op->op2_def >= 0) {
225 				FAIL("non-var op2 of " INSTRFMT " uses or defs an ssa var\n", INSTR(i));
226 			}
227 		}
228 		if (is_var_type(opline->result_type)) {
229 			if (ssa_op->result_use < 0 && ssa_op->result_def < 0) {
230 				FAIL("var result of " INSTRFMT " does not use/def an ssa var\n", INSTR(i));
231 			}
232 		} else {
233 			if (ssa_op->result_use >= 0 || ssa_op->result_def >= 0) {
234 				FAIL("non-var result of " INSTRFMT " uses or defs an ssa var\n", INSTR(i));
235 			}
236 		}
237 
238 		if (ssa_op->op1_use >= 0) {
239 			if (ssa_op->op1_use >= ssa->vars_count) {
240 				FAIL("op1 use %d out of range\n", ssa_op->op1_use);
241 			}
242 			if (!is_defined(ssa, op_array, ssa_op->op1_use)) {
243 				FAIL("op1 use of " VARFMT " in " INSTRFMT " is not defined\n",
244 						VAR(ssa_op->op1_use), INSTR(i));
245 			}
246 			if (!is_in_use_chain(ssa, ssa_op->op1_use, i)) {
247 				FAIL("op1 use of " VARFMT " in " INSTRFMT " not in use chain\n",
248 						VAR(ssa_op->op1_use), INSTR(i));
249 			}
250 			if (VAR_NUM(opline->op1.var) != ssa->vars[ssa_op->op1_use].var) {
251 				FAIL("op1 use of " VARFMT " does not match op %d of " INSTRFMT "\n",
252 						VAR(ssa_op->op1_use), VAR_NUM(opline->op1.var), INSTR(i));
253 			}
254 		}
255 		if (ssa_op->op2_use >= 0) {
256 			if (ssa_op->op2_use >= ssa->vars_count) {
257 				FAIL("op2 use %d out of range\n", ssa_op->op2_use);
258 			}
259 			if (!is_defined(ssa, op_array, ssa_op->op2_use)) {
260 				FAIL("op2 use of " VARFMT " in " INSTRFMT " is not defined\n",
261 						VAR(ssa_op->op2_use), INSTR(i));
262 			}
263 			if (!is_in_use_chain(ssa, ssa_op->op2_use, i)) {
264 				FAIL("op2 use of " VARFMT " in " INSTRFMT " not in use chain\n",
265 						VAR(ssa_op->op2_use), INSTR(i));
266 			}
267 			if (VAR_NUM(opline->op2.var) != ssa->vars[ssa_op->op2_use].var) {
268 				FAIL("op2 use of " VARFMT " does not match op %d of " INSTRFMT "\n",
269 						VAR(ssa_op->op2_use), VAR_NUM(opline->op2.var), INSTR(i));
270 			}
271 		}
272 		if (ssa_op->result_use >= 0) {
273 			if (ssa_op->result_use >= ssa->vars_count) {
274 				FAIL("result use %d out of range\n", ssa_op->result_use);
275 			}
276 			if (!is_defined(ssa, op_array, ssa_op->result_use)) {
277 				FAIL("result use of " VARFMT " in " INSTRFMT " is not defined\n",
278 						VAR(ssa_op->result_use), INSTR(i));
279 			}
280 			if (!is_in_use_chain(ssa, ssa_op->result_use, i)) {
281 				FAIL("result use of " VARFMT " in " INSTRFMT " not in use chain\n",
282 					VAR(ssa_op->result_use), INSTR(i));
283 			}
284 			if (VAR_NUM(opline->result.var) != ssa->vars[ssa_op->result_use].var) {
285 				FAIL("result use of " VARFMT " does not match op %d of " INSTRFMT "\n",
286 						VAR(ssa_op->result_use), VAR_NUM(opline->result.var), INSTR(i));
287 			}
288 		}
289 		if (ssa_op->op1_def >= 0) {
290 			if (ssa_op->op1_def >= ssa->vars_count) {
291 				FAIL("op1 def %d out of range\n", ssa_op->op1_def);
292 			}
293 			if (ssa->vars[ssa_op->op1_def].definition != i) {
294 				FAIL("op1 def of " VARFMT " in " INSTRFMT " invalid\n",
295 						VAR(ssa_op->op1_def), INSTR(i));
296 			}
297 			if (VAR_NUM(opline->op1.var) != ssa->vars[ssa_op->op1_def].var) {
298 				FAIL("op1 def of " VARFMT " does not match op %d of " INSTRFMT "\n",
299 						VAR(ssa_op->op1_def), VAR_NUM(opline->op1.var), INSTR(i));
300 			}
301 		}
302 		if (ssa_op->op2_def >= 0) {
303 			if (ssa_op->op2_def >= ssa->vars_count) {
304 				FAIL("op2 def %d out of range\n", ssa_op->op2_def);
305 			}
306 			if (ssa->vars[ssa_op->op2_def].definition != i) {
307 				FAIL("op2 def of " VARFMT " in " INSTRFMT " invalid\n",
308 						VAR(ssa_op->op2_def), INSTR(i));
309 			}
310 			if (VAR_NUM(opline->op2.var) != ssa->vars[ssa_op->op2_def].var) {
311 				FAIL("op2 def of " VARFMT " does not match op %d of " INSTRFMT "\n",
312 						VAR(ssa_op->op2_def), VAR_NUM(opline->op2.var), INSTR(i));
313 			}
314 		}
315 		if (ssa_op->result_def >= 0) {
316 			if (ssa_op->result_def >= ssa->vars_count) {
317 				FAIL("result def %d out of range\n", ssa_op->result_def);
318 			}
319 			if (ssa->vars[ssa_op->result_def].definition != i) {
320 				FAIL("result def of " VARFMT " in " INSTRFMT " invalid\n",
321 						VAR(ssa_op->result_def), INSTR(i));
322 			}
323 			if (VAR_NUM(opline->result.var) != ssa->vars[ssa_op->result_def].var) {
324 				FAIL("result def of " VARFMT " does not match op %d of " INSTRFMT "\n",
325 						VAR(ssa_op->result_def), VAR_NUM(opline->result.var), INSTR(i));
326 			}
327 		}
328 	} FOREACH_INSTR_NUM_END();
329 
330 	/* Phis */
331 	FOREACH_PHI(phi) {
332 		unsigned num_sources = NUM_PHI_SOURCES(phi);
333 		for (i = 0; i < num_sources; i++) {
334 			int source = phi->sources[i];
335 			if (source < 0) {
336 				FAIL(VARFMT " negative source\n", VAR(phi->ssa_var));
337 			}
338 			if (!is_in_phi_use_chain(ssa, source, phi)) {
339 				FAIL(VARFMT " not in phi use chain of %d\n", VAR(phi->ssa_var), source);
340 			}
341 			if (ssa->vars[source].var != ssa->vars[phi->ssa_var].var) {
342 				FAIL(VARFMT " source of phi for " VARFMT "\n", VAR(source), VAR(phi->ssa_var));
343 			}
344 			if (phi->use_chains[i]) {
345 				int j;
346 				for (j = i + 1; j < num_sources; j++) {
347 					if (phi->sources[j] == source && phi->use_chains[j]) {
348 						FAIL("use chain for source " VARFMT " of phi " VARFMT
349 							" at %d despite earlier use\n", VAR(source), VAR(phi->ssa_var), j);
350 					}
351 				}
352 			}
353 		}
354 		if (ssa->vars[phi->ssa_var].definition_phi != phi) {
355 			FAIL(VARFMT " does not define this phi\n", VAR(phi->ssa_var));
356 		}
357 	} FOREACH_PHI_END();
358 
359 	/* Blocks */
360 	for (i = 0; i < cfg->blocks_count; i++) {
361 		zend_basic_block *block = &cfg->blocks[i];
362 		int *predecessors = &cfg->predecessors[block->predecessor_offset];
363 		int s, j;
364 
365 		if (i != 0 && block->start < (block-1)->start + (block-1)->len) {
366 			FAIL("Block %d start %d smaller previous end %d\n",
367 				i, block->start, (block-1)->start + (block-1)->len);
368 		}
369 		if (i != cfg->blocks_count-1 && block->start + block->len > (block+1)->start) {
370 			FAIL("Block %d end %d greater next start %d\n",
371 				i, block->start + block->len, (block+1)->start);
372 		}
373 
374 		for (j = block->start; j < block->start + block->len; j++) {
375 			if (cfg->map[j] != i) {
376 				FAIL("Instr " INSTRFMT " not associated with block %d\n", INSTR(j), i);
377 			}
378 		}
379 
380 		if (!(block->flags & ZEND_BB_REACHABLE)) {
381 			if (ssa->blocks[i].phis) {
382 				FAIL("Unreachable block %d has phis\n", i);
383 			}
384 			continue;
385 		}
386 
387 		for (s = 0; s < block->successors_count; s++) {
388 			zend_basic_block *next_block;
389 			if (block->successors[s] < 0) {
390 				FAIL("Successor number %d of %d negative", s, i);
391 			}
392 			next_block = &cfg->blocks[block->successors[s]];
393 			if (!(next_block->flags & ZEND_BB_REACHABLE)) {
394 				FAIL("Successor %d of %d not reachable\n", block->successors[s], i);
395 			}
396 			if (!is_in_predecessors(cfg, next_block, i)) {
397 				FAIL("Block %d predecessors missing %d\n", block->successors[s], i);
398 			}
399 		}
400 
401 		for (j = 0; j < block->predecessors_count; j++) {
402 			if (predecessors[j] >= 0) {
403 				int k;
404 				zend_basic_block *prev_block = &cfg->blocks[predecessors[j]];
405 				if (!(prev_block->flags & ZEND_BB_REACHABLE)) {
406 					FAIL("Predecessor %d of %d not reachable\n", predecessors[j], i);
407 				}
408 				if (!is_in_successors(prev_block, i)) {
409 					FAIL("Block %d successors missing %d\n", predecessors[j], i);
410 				}
411 				for (k = 0; k < block->predecessors_count; k++) {
412 					if (k != j && predecessors[k] == predecessors[j]) {
413 						FAIL("Block %d has duplicate predecessor %d\n", i, predecessors[j]);
414 					}
415 				}
416 			}
417 		}
418 	}
419 
420 finish:
421 	if (status == FAILURE) {
422 		zend_dump_op_array(op_array, ZEND_DUMP_SSA, "at SSA integrity verification", ssa);
423 		ZEND_ASSERT(0 && "SSA integrity verification failed");
424 	}
425 }
426