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