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 || type == IS_VAR || type == IS_TMP_VAR;
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
