xref: /php-src/ext/opcache/jit/ir/ir_check.c (revision 71194ea7)
1 /*
2  * IR - Lightweight JIT Compilation Framework
3  * (IR verification)
4  * Copyright (C) 2022 Zend by Perforce.
5  * Authors: Dmitry Stogov <dmitry@php.net>
6  */
7 
8 #include "ir.h"
9 #include "ir_private.h"
10 
ir_consistency_check(void)11 void ir_consistency_check(void)
12 {
13 	IR_ASSERT(IR_UNUSED == 0);
14 	IR_ASSERT(IR_NOP == 0);
15 
16 	IR_ASSERT((int)IR_BOOL   == (int)IR_C_BOOL);
17 	IR_ASSERT((int)IR_U8     == (int)IR_C_U8);
18 	IR_ASSERT((int)IR_U16    == (int)IR_C_U16);
19 	IR_ASSERT((int)IR_U32    == (int)IR_C_U32);
20 	IR_ASSERT((int)IR_U64    == (int)IR_C_U64);
21 	IR_ASSERT((int)IR_ADDR   == (int)IR_C_ADDR);
22 	IR_ASSERT((int)IR_CHAR   == (int)IR_C_CHAR);
23 	IR_ASSERT((int)IR_I8     == (int)IR_C_I8);
24 	IR_ASSERT((int)IR_I16    == (int)IR_C_I16);
25 	IR_ASSERT((int)IR_I32    == (int)IR_C_I32);
26 	IR_ASSERT((int)IR_I64    == (int)IR_C_I64);
27 	IR_ASSERT((int)IR_DOUBLE == (int)IR_C_DOUBLE);
28 	IR_ASSERT((int)IR_FLOAT  == (int)IR_C_FLOAT);
29 
30 	IR_ASSERT((IR_EQ ^ 1) == IR_NE);
31 	IR_ASSERT((IR_LT ^ 3) == IR_GT);
32 	IR_ASSERT((IR_GT ^ 3) == IR_LT);
33 	IR_ASSERT((IR_LE ^ 3) == IR_GE);
34 	IR_ASSERT((IR_GE ^ 3) == IR_LE);
35 	IR_ASSERT((IR_ULT ^ 3) == IR_UGT);
36 	IR_ASSERT((IR_UGT ^ 3) == IR_ULT);
37 	IR_ASSERT((IR_ULE ^ 3) == IR_UGE);
38 	IR_ASSERT((IR_UGE ^ 3) == IR_ULE);
39 
40 	IR_ASSERT(IR_ADD + 1 == IR_SUB);
41 }
42 
ir_check_use_list(const ir_ctx * ctx,ir_ref from,ir_ref to)43 static bool ir_check_use_list(const ir_ctx *ctx, ir_ref from, ir_ref to)
44 {
45 	ir_ref n, j, *p;
46 	ir_use_list *use_list = &ctx->use_lists[from];
47 
48 	n = use_list->count;
49 	for (j = 0, p = &ctx->use_edges[use_list->refs]; j < n; j++, p++) {
50 		if (*p == to) {
51 			return 1;
52 		}
53 	}
54 	return 0;
55 }
56 
ir_check_input_list(const ir_ctx * ctx,ir_ref from,ir_ref to)57 static bool ir_check_input_list(const ir_ctx *ctx, ir_ref from, ir_ref to)
58 {
59 	ir_insn *insn = &ctx->ir_base[to];
60 	ir_ref n, j, *p;
61 
62 	n = ir_input_edges_count(ctx, insn);
63 	for (j = 1, p = insn->ops + 1; j <= n; j++, p++) {
64 		if (*p == from) {
65 			return 1;
66 		}
67 	}
68 	return 0;
69 }
70 
ir_check_domination(const ir_ctx * ctx,ir_ref def,ir_ref use)71 static bool ir_check_domination(const ir_ctx *ctx, ir_ref def, ir_ref use)
72 {
73 	uint32_t b1 = ctx->cfg_map[def];
74 	uint32_t b2 = ctx->cfg_map[use];
75 	ir_block *blocks = ctx->cfg_blocks;
76 	uint32_t b1_depth = blocks[b1].dom_depth;
77 	const ir_block *bb2 = &blocks[b2];
78 
79 	if (b1 == b2) {
80 		return def < use;
81 	}
82 	while (bb2->dom_depth > b1_depth) {
83 		b2 = bb2->dom_parent;
84 		bb2 = &blocks[b2];
85 	}
86 	return b1 == b2;
87 }
88 
ir_check(const ir_ctx * ctx)89 bool ir_check(const ir_ctx *ctx)
90 {
91 	ir_ref i, j, n, *p, use;
92 	ir_insn *insn, *use_insn;
93 	ir_type type;
94 	uint32_t flags;
95 	bool ok = 1;
96 
97 	for (i = IR_UNUSED + 1, insn = ctx->ir_base + i; i < ctx->insns_count;) {
98 		if (insn->op >= IR_LAST_OP) {
99 			fprintf(stderr, "ir_base[%d].op invalid opcode (%d)\n", i, insn->op);
100 			ok = 0;
101 			break;
102 		}
103 		flags = ir_op_flags[insn->op];
104 		n = ir_input_edges_count(ctx, insn);
105 		for (j = 1, p = insn->ops + 1; j <= n; j++, p++) {
106 			use = *p;
107 			if (use != IR_UNUSED) {
108 				if (IR_IS_CONST_REF(use)) {
109 					if (use >= ctx->consts_count) {
110 						fprintf(stderr, "ir_base[%d].ops[%d] constant reference (%d) is out of range\n", i, j, use);
111 						ok = 0;
112 					}
113 				} else {
114 					if (use >= ctx->insns_count) {
115 						fprintf(stderr, "ir_base[%d].ops[%d] insn reference (%d) is out of range\n", i, j, use);
116 						ok = 0;
117 					}
118 					use_insn = &ctx->ir_base[use];
119 					switch (IR_OPND_KIND(flags, j)) {
120 						case IR_OPND_DATA:
121 							if (!(ir_op_flags[use_insn->op] & IR_OP_FLAG_DATA)) {
122 								if (!(ir_op_flags[use_insn->op] & IR_OP_FLAG_MEM)
123 								 || use_insn->type == IR_VOID) {
124 									fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must be DATA\n", i, j, use);
125 									ok = 0;
126 								}
127 							}
128 							if ((ctx->flags2 & IR_LINEAR)
129 							 && use >= i
130 							 && !(insn->op == IR_PHI && ctx->ir_base[insn->op1].op == IR_LOOP_BEGIN)) {
131 								fprintf(stderr, "ir_base[%d].ops[%d] invalid forward reference (%d)\n", i, j, use);
132 								ok = 0;
133 							}
134 							if (flags & IR_OP_FLAG_DATA) {
135 								switch (insn->op) {
136 									case IR_COND:
137 										if (j == 1) {
138 											break;
139 										}
140 										IR_FALLTHROUGH;
141 									case IR_ADD:
142 									case IR_SUB:
143 									case IR_MUL:
144 									case IR_DIV:
145 									case IR_MOD:
146 									case IR_NEG:
147 									case IR_ABS:
148 									case IR_ADD_OV:
149 									case IR_SUB_OV:
150 									case IR_MUL_OV:
151 									case IR_NOT:
152 									case IR_OR:
153 									case IR_AND:
154 									case IR_XOR:
155 									case IR_SHL:
156 									case IR_SHR:
157 									case IR_SAR:
158 									case IR_ROL:
159 									case IR_ROR:
160 									case IR_BSWAP:
161 									case IR_MIN:
162 									case IR_MAX:
163 									case IR_PHI:
164 									case IR_COPY:
165 									case IR_PI:
166 										if (insn->type != use_insn->type) {
167 											if (j == 2
168 											 && (insn->op == IR_SHL
169 											  || insn->op == IR_SHR
170 											  || insn->op == IR_SAR
171 											  || insn->op == IR_ROL
172 											  || insn->op == IR_ROR)
173 											 && ir_type_size[use_insn->type] < ir_type_size[insn->type]) {
174 												/* second argument of SHIFT may be incompatible with result */
175 												break;
176 											}
177 											if (insn->op == IR_NOT && insn->type == IR_BOOL) {
178 												/* boolean not */
179 												break;
180 											}
181 											if (insn->type == IR_ADDR && (use_insn->type == IR_UINTPTR_T || use_insn->type == IR_INTPTR_T)) {
182 												break;
183 											} else if (use_insn->type == IR_ADDR && (insn->type == IR_UINTPTR_T || insn->type == IR_INTPTR_T)) {
184 												break;
185 											}
186 											fprintf(stderr, "ir_base[%d].ops[%d] (%d) type is incompatible with result type (%d != %d)\n",
187 												i, j, use, use_insn->type, insn->type);
188 											ok = 0;
189 										}
190 										break;
191 								}
192 							}
193 							if ((ctx->flags2 & IR_LINEAR)
194 							 && ctx->cfg_map
195 							 && insn->op != IR_PHI
196 							 && !ir_check_domination(ctx, use, i)) {
197 								fprintf(stderr, "ir_base[%d].ops[%d] -> %d, %d doesn't dominate %d\n", i, j, use, use, i);
198 								ok = 0;
199 							}
200 							break;
201 						case IR_OPND_CONTROL:
202 							if (flags & IR_OP_FLAG_BB_START) {
203 								if (!(ir_op_flags[use_insn->op] & IR_OP_FLAG_BB_END)) {
204 									fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must be BB_END\n", i, j, use);
205 									ok = 0;
206 								}
207 							} else {
208 								if (ir_op_flags[use_insn->op] & IR_OP_FLAG_BB_END) {
209 									fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must not be BB_END\n", i, j, use);
210 									ok = 0;
211 								}
212 							}
213 							break;
214 						case IR_OPND_CONTROL_DEP:
215 							if ((ctx->flags2 & IR_LINEAR)
216 							 && use >= i
217 							 && !(insn->op == IR_LOOP_BEGIN)) {
218 								fprintf(stderr, "ir_base[%d].ops[%d] invalid forward reference (%d)\n", i, j, use);
219 								ok = 0;
220 							} else if (insn->op == IR_PHI) {
221 								ir_insn *merge_insn = &ctx->ir_base[insn->op1];
222 								if (merge_insn->op != IR_MERGE && merge_insn->op != IR_LOOP_BEGIN) {
223 									fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must be MERGE or LOOP_BEGIN\n", i, j, use);
224 									ok = 0;
225 								}
226 							}
227 							break;
228 						case IR_OPND_CONTROL_REF:
229 							if (!(ir_op_flags[use_insn->op] & IR_OP_FLAG_CONTROL)) {
230 								fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) must be CONTROL\n", i, j, use);
231 								ok = 0;
232 							}
233 							break;
234 						default:
235 							fprintf(stderr, "ir_base[%d].ops[%d] reference (%d) of unsupported kind\n", i, j, use);
236 							ok = 0;
237 					}
238 				}
239 			} else if ((insn->op == IR_RETURN || insn->op == IR_UNREACHABLE) && j == 2) {
240 				/* pass (function returns void) */
241 			} else if (insn->op == IR_BEGIN && j == 1) {
242 				/* pass (start of unreachable basic block) */
243 			} else if (IR_OPND_KIND(flags, j) != IR_OPND_CONTROL_REF
244 					&& (insn->op != IR_SNAPSHOT || j == 1)) {
245 				fprintf(stderr, "ir_base[%d].ops[%d] missing reference (%d)\n", i, j, use);
246 				ok = 0;
247 			}
248 			if (ctx->use_lists
249 			 && use > 0
250 			 && !ir_check_use_list(ctx, use, i)) {
251 				fprintf(stderr, "ir_base[%d].ops[%d] is not in use list (%d)\n", i, j, use);
252 				ok = 0;
253 			}
254 		}
255 
256 		switch (insn->op) {
257 			case IR_PHI:
258 				if (insn->inputs_count != ctx->ir_base[insn->op1].inputs_count + 1) {
259 					fprintf(stderr, "ir_base[%d] inconsistent PHI inputs_count (%d != %d)\n",
260 						i, insn->inputs_count, ctx->ir_base[insn->op1].inputs_count + 1);
261 					ok = 0;
262 				}
263 				break;
264 			case IR_LOAD:
265 			case IR_STORE:
266 				type = ctx->ir_base[insn->op2].type;
267 				if (type != IR_ADDR
268 				 && (!IR_IS_TYPE_INT(type) || ir_type_size[type] != ir_type_size[IR_ADDR])) {
269 					fprintf(stderr, "ir_base[%d].op2 must have ADDR type (%s)\n",
270 						i, ir_type_name[type]);
271 					ok = 0;
272 				}
273 				break;
274 			case IR_VLOAD:
275 			case IR_VSTORE:
276 				if (ctx->ir_base[insn->op2].op != IR_VAR) {
277 					fprintf(stderr, "ir_base[%d].op2 must be 'VAR' (%s)\n",
278 						i, ir_op_name[ctx->ir_base[insn->op2].op]);
279 					ok = 0;
280 				}
281 				break;
282 			case IR_RETURN:
283 				if (ctx->ret_type != (insn->op2 ? ctx->ir_base[insn->op2].type : IR_VOID)) {
284 					fprintf(stderr, "ir_base[%d].type incompatible return type\n", i);
285 					ok = 0;
286 				}
287 				break;
288 			case IR_TAILCALL:
289 				if (ctx->ret_type != insn->type) {
290 					fprintf(stderr, "ir_base[%d].type incompatible return type\n", i);
291 					ok = 0;
292 				}
293 				break;
294 		}
295 
296 		if (ctx->use_lists) {
297 			ir_use_list *use_list = &ctx->use_lists[i];
298 			ir_ref count;
299 
300 			for (j = 0, p = &ctx->use_edges[use_list->refs]; j < use_list->count; j++, p++) {
301 				use = *p;
302 				if (!ir_check_input_list(ctx, i, use)) {
303 					fprintf(stderr, "ir_base[%d] is in use list of ir_base[%d]\n", use, i);
304 					ok = 0;
305 				}
306 			}
307 
308 			if ((flags & IR_OP_FLAG_CONTROL) && !(flags & IR_OP_FLAG_MEM)) {
309 				switch (insn->op) {
310 					case IR_SWITCH:
311 						/* may have many successors */
312 						if (use_list->count < 1) {
313 							fprintf(stderr, "ir_base[%d].op (SWITCH) must have at least 1 successor (%d)\n", i, use_list->count);
314 							ok = 0;
315 						}
316 						break;
317 					case IR_IF:
318 						if (use_list->count != 2) {
319 							fprintf(stderr, "ir_base[%d].op (IF) must have 2 successors (%d)\n", i, use_list->count);
320 							ok = 0;
321 						}
322 						break;
323 					case IR_UNREACHABLE:
324 					case IR_RETURN:
325 						if (use_list->count == 1) {
326 							/* UNREACHABLE and RETURN may be linked with the following ENTRY by a fake edge */
327 							if (ctx->ir_base[ctx->use_edges[use_list->refs]].op == IR_ENTRY) {
328 								break;
329 							}
330 						}
331 						IR_FALLTHROUGH;
332 					case IR_IJMP:
333 						if (use_list->count != 0) {
334 							fprintf(stderr, "ir_base[%d].op (%s) must not have successors (%d)\n",
335 								i, ir_op_name[insn->op], use_list->count);
336 							ok = 0;
337 						}
338 						break;
339 					default:
340 						/* skip data references */
341 						count = use_list->count;
342 						for (j = 0, p = &ctx->use_edges[use_list->refs]; j < use_list->count; j++, p++) {
343 							use = *p;
344 							if (!(ir_op_flags[ctx->ir_base[use].op] & IR_OP_FLAG_CONTROL)) {
345 								count--;
346 							}
347 						}
348 						if (count != 1) {
349 							if (insn->op == IR_CALL && count == 2) {
350 								/* result of CALL may be used as data in control instruction */
351 								break;
352 							}
353 							if ((insn->op == IR_LOOP_END || insn->op == IR_END) && count == 2) {
354 								/* LOOP_END/END may be linked with the following ENTRY by a fake edge */
355 								if (ctx->ir_base[ctx->use_edges[use_list->refs]].op == IR_ENTRY) {
356 									count--;
357 								}
358 								if (ctx->ir_base[ctx->use_edges[use_list->refs + 1]].op == IR_ENTRY) {
359 									count--;
360 								}
361 								if (count == 1) {
362 									break;
363 								}
364 							}
365 							fprintf(stderr, "ir_base[%d].op (%s) must have 1 successor (%d)\n",
366 								i, ir_op_name[insn->op], count);
367 							ok = 0;
368 						}
369 						break;
370 				}
371 			}
372 		}
373 		n = ir_insn_inputs_to_len(n);
374 		i += n;
375 		insn += n;
376 	}
377 
378 //	if (!ok) {
379 //		ir_dump_codegen(ctx, stderr);
380 //	}
381 	IR_ASSERT(ok);
382 	return ok;
383 }
384