xref: /PHP-8.1/Zend/Optimizer/zend_ssa.h (revision c3766c08)
1 /*
2    +----------------------------------------------------------------------+
3    | Zend Engine, SSA - Static Single Assignment Form                     |
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: Dmitry Stogov <dmitry@php.net>                              |
16    +----------------------------------------------------------------------+
17 */
18 
19 #ifndef ZEND_SSA_H
20 #define ZEND_SSA_H
21 
22 #include "zend_optimizer.h"
23 #include "zend_cfg.h"
24 
25 typedef struct _zend_ssa_range {
26 	zend_long              min;
27 	zend_long              max;
28 	bool              underflow;
29 	bool              overflow;
30 } zend_ssa_range;
31 
32 typedef enum _zend_ssa_negative_lat {
33 	NEG_NONE      = 0,
34 	NEG_INIT      = 1,
35 	NEG_INVARIANT = 2,
36 	NEG_USE_LT    = 3,
37 	NEG_USE_GT    = 4,
38 	NEG_UNKNOWN   = 5
39 } zend_ssa_negative_lat;
40 
41 /* Special kind of SSA Phi function used in eSSA */
42 typedef struct _zend_ssa_range_constraint {
43 	zend_ssa_range         range;       /* simple range constraint */
44 	int                    min_var;
45 	int                    max_var;
46 	int                    min_ssa_var; /* ((min_var>0) ? MIN(ssa_var) : 0) + range.min */
47 	int                    max_ssa_var; /* ((max_var>0) ? MAX(ssa_var) : 0) + range.max */
48 	zend_ssa_negative_lat  negative;
49 } zend_ssa_range_constraint;
50 
51 typedef struct _zend_ssa_type_constraint {
52 	uint32_t               type_mask;   /* Type mask to intersect with */
53 	zend_class_entry      *ce;          /* Class entry for instanceof constraints */
54 } zend_ssa_type_constraint;
55 
56 typedef union _zend_ssa_pi_constraint {
57 	zend_ssa_range_constraint range;
58 	zend_ssa_type_constraint type;
59 } zend_ssa_pi_constraint;
60 
61 /* SSA Phi - ssa_var = Phi(source0, source1, ...sourceN) */
62 typedef struct _zend_ssa_phi zend_ssa_phi;
63 struct _zend_ssa_phi {
64 	zend_ssa_phi          *next;          /* next Phi in the same BB */
65 	int                    pi;            /* if >= 0 this is actually a e-SSA Pi */
66 	zend_ssa_pi_constraint constraint;    /* e-SSA Pi constraint */
67 	int                    var;           /* Original CV, VAR or TMP variable index */
68 	int                    ssa_var;       /* SSA variable index */
69 	int                    block;         /* current BB index */
70 	int                    visited : 1;   /* flag to avoid recursive processing */
71 	int                    has_range_constraint : 1;
72 	zend_ssa_phi         **use_chains;
73 	zend_ssa_phi          *sym_use_chain;
74 	int                   *sources;       /* Array of SSA IDs that produce this var.
75 									         As many as this block has
76 									         predecessors.  */
77 };
78 
79 typedef struct _zend_ssa_block {
80 	zend_ssa_phi          *phis;
81 } zend_ssa_block;
82 
83 typedef struct _zend_ssa_op {
84 	int                    op1_use;
85 	int                    op2_use;
86 	int                    result_use;
87 	int                    op1_def;
88 	int                    op2_def;
89 	int                    result_def;
90 	int                    op1_use_chain;
91 	int                    op2_use_chain;
92 	int                    res_use_chain;
93 } zend_ssa_op;
94 
95 typedef enum _zend_ssa_alias_kind {
96 	NO_ALIAS,
97 	SYMTABLE_ALIAS,
98 	HTTP_RESPONSE_HEADER_ALIAS
99 } zend_ssa_alias_kind;
100 
101 typedef enum _zend_ssa_escape_state {
102 	ESCAPE_STATE_UNKNOWN,
103 	ESCAPE_STATE_NO_ESCAPE,
104 	ESCAPE_STATE_FUNCTION_ESCAPE,
105 	ESCAPE_STATE_GLOBAL_ESCAPE
106 } zend_ssa_escape_state;
107 
108 typedef struct _zend_ssa_var {
109 	int                    var;            /* original var number; op.var for CVs and following numbers for VARs and TMP_VARs */
110 	int                    scc;            /* strongly connected component */
111 	int                    definition;     /* opcode that defines this value */
112 	zend_ssa_phi          *definition_phi; /* phi that defines this value */
113 	int                    use_chain;      /* uses of this value, linked through opN_use_chain */
114 	zend_ssa_phi          *phi_use_chain;  /* uses of this value in Phi, linked through use_chain */
115 	zend_ssa_phi          *sym_use_chain;  /* uses of this value in Pi constraints */
116 	unsigned int           no_val : 1;     /* value doesn't matter (used as op1 in ZEND_ASSIGN) */
117 	unsigned int           scc_entry : 1;
118 	unsigned int           alias : 2;  /* value may be changed indirectly */
119 	unsigned int           escape_state : 2;
120 } zend_ssa_var;
121 
122 typedef struct _zend_ssa_var_info {
123 	uint32_t               type; /* inferred type (see zend_inference.h) */
124 	zend_ssa_range         range;
125 	zend_class_entry      *ce;
126 	unsigned int           has_range : 1;
127 	unsigned int           is_instanceof : 1; /* 0 - class == "ce", 1 - may be child of "ce" */
128 	unsigned int           recursive : 1;
129 	unsigned int           use_as_double : 1;
130 	unsigned int           delayed_fetch_this : 1;
131 	unsigned int           avoid_refcounting : 1;
132 	unsigned int           guarded_reference : 1;
133 	unsigned int           indirect_reference : 1; /* IS_INDIRECT returned by FETCH_DIM_W/FETCH_OBJ_W */
134 } zend_ssa_var_info;
135 
136 typedef struct _zend_ssa {
137 	zend_cfg               cfg;            /* control flow graph             */
138 	int                    vars_count;     /* number of SSA variables        */
139 	int                    sccs;           /* number of SCCs                 */
140 	zend_ssa_block        *blocks;         /* array of SSA blocks            */
141 	zend_ssa_op           *ops;            /* array of SSA instructions      */
142 	zend_ssa_var          *vars;           /* use/def chain of SSA variables */
143 	zend_ssa_var_info     *var_info;
144 } zend_ssa;
145 
146 BEGIN_EXTERN_C()
147 
148 ZEND_API int zend_build_ssa(zend_arena **arena, const zend_script *script, const zend_op_array *op_array, uint32_t build_flags, zend_ssa *ssa);
149 ZEND_API int zend_ssa_compute_use_def_chains(zend_arena **arena, const zend_op_array *op_array, zend_ssa *ssa);
150 ZEND_API int zend_ssa_rename_op(const zend_op_array *op_array, const zend_op *opline, uint32_t k, uint32_t build_flags, int ssa_vars_count, zend_ssa_op *ssa_ops, int *var);
151 int zend_ssa_unlink_use_chain(zend_ssa *ssa, int op, int var);
152 
153 void zend_ssa_remove_predecessor(zend_ssa *ssa, int from, int to);
154 void zend_ssa_remove_defs_of_instr(zend_ssa *ssa, zend_ssa_op *ssa_op);
155 void zend_ssa_remove_instr(zend_ssa *ssa, zend_op *opline, zend_ssa_op *ssa_op);
156 void zend_ssa_remove_phi(zend_ssa *ssa, zend_ssa_phi *phi);
157 void zend_ssa_remove_uses_of_var(zend_ssa *ssa, int var_num);
158 void zend_ssa_remove_block(zend_op_array *op_array, zend_ssa *ssa, int b);
159 void zend_ssa_rename_var_uses(zend_ssa *ssa, int old_var, int new_var, bool update_types);
160 void zend_ssa_remove_block_from_cfg(zend_ssa *ssa, int b);
161 
_zend_ssa_remove_def(zend_ssa_var * var)162 static zend_always_inline void _zend_ssa_remove_def(zend_ssa_var *var)
163 {
164 	ZEND_ASSERT(var->definition >= 0);
165 	ZEND_ASSERT(var->use_chain < 0);
166 	ZEND_ASSERT(!var->phi_use_chain);
167 	var->definition = -1;
168 }
169 
zend_ssa_remove_result_def(zend_ssa * ssa,zend_ssa_op * ssa_op)170 static zend_always_inline void zend_ssa_remove_result_def(zend_ssa *ssa, zend_ssa_op *ssa_op)
171 {
172 	zend_ssa_var *var = &ssa->vars[ssa_op->result_def];
173 	_zend_ssa_remove_def(var);
174 	ssa_op->result_def = -1;
175 }
176 
zend_ssa_remove_op1_def(zend_ssa * ssa,zend_ssa_op * ssa_op)177 static zend_always_inline void zend_ssa_remove_op1_def(zend_ssa *ssa, zend_ssa_op *ssa_op)
178 {
179 	zend_ssa_var *var = &ssa->vars[ssa_op->op1_def];
180 	_zend_ssa_remove_def(var);
181 	ssa_op->op1_def = -1;
182 }
183 
zend_ssa_remove_op2_def(zend_ssa * ssa,zend_ssa_op * ssa_op)184 static zend_always_inline void zend_ssa_remove_op2_def(zend_ssa *ssa, zend_ssa_op *ssa_op)
185 {
186 	zend_ssa_var *var = &ssa->vars[ssa_op->op2_def];
187 	_zend_ssa_remove_def(var);
188 	ssa_op->op2_def = -1;
189 }
190 
END_EXTERN_C()191 END_EXTERN_C()
192 
193 static zend_always_inline int zend_ssa_next_use(const zend_ssa_op *ssa_op, int var, int use)
194 {
195 	ssa_op += use;
196 	if (ssa_op->op1_use == var) {
197 		return ssa_op->op1_use_chain;
198 	} else if (ssa_op->op2_use == var) {
199 		return ssa_op->op2_use_chain;
200 	} else {
201 		return ssa_op->res_use_chain;
202 	}
203 }
204 
zend_ssa_next_use_phi(const zend_ssa * ssa,int var,const zend_ssa_phi * p)205 static zend_always_inline zend_ssa_phi* zend_ssa_next_use_phi(const zend_ssa *ssa, int var, const zend_ssa_phi *p)
206 {
207 	if (p->pi >= 0) {
208 		return p->use_chains[0];
209 	} else {
210 		int j;
211 		for (j = 0; j < ssa->cfg.blocks[p->block].predecessors_count; j++) {
212 			if (p->sources[j] == var) {
213 				return p->use_chains[j];
214 			}
215 		}
216 	}
217 	return NULL;
218 }
219 
zend_ssa_is_no_val_use(const zend_op * opline,const zend_ssa_op * ssa_op,int var)220 static zend_always_inline bool zend_ssa_is_no_val_use(const zend_op *opline, const zend_ssa_op *ssa_op, int var)
221 {
222 	if (opline->opcode == ZEND_ASSIGN
223 			 || opline->opcode == ZEND_UNSET_CV
224 			 || opline->opcode == ZEND_BIND_GLOBAL
225 			 || opline->opcode == ZEND_BIND_STATIC) {
226 		return ssa_op->op1_use == var && ssa_op->op2_use != var;
227 	}
228 	if (opline->opcode == ZEND_FE_FETCH_R || opline->opcode == ZEND_FE_FETCH_RW) {
229 		return ssa_op->op2_use == var && ssa_op->op1_use != var;
230 	}
231 	if (ssa_op->result_use == var
232 			&& opline->opcode != ZEND_ADD_ARRAY_ELEMENT
233 			&& opline->opcode != ZEND_ADD_ARRAY_UNPACK) {
234 		return ssa_op->op1_use != var && ssa_op->op2_use != var;
235 	}
236 	return 0;
237 }
238 
zend_ssa_rename_defs_of_instr(zend_ssa * ssa,zend_ssa_op * ssa_op)239 static zend_always_inline void zend_ssa_rename_defs_of_instr(zend_ssa *ssa, zend_ssa_op *ssa_op) {
240 	/* Rename def to use if possible. Mark variable as not defined otherwise. */
241 	if (ssa_op->op1_def >= 0) {
242 		if (ssa_op->op1_use >= 0) {
243 			zend_ssa_rename_var_uses(ssa, ssa_op->op1_def, ssa_op->op1_use, 1);
244 		}
245 		ssa->vars[ssa_op->op1_def].definition = -1;
246 		ssa_op->op1_def = -1;
247 	}
248 	if (ssa_op->op2_def >= 0) {
249 		if (ssa_op->op2_use >= 0) {
250 			zend_ssa_rename_var_uses(ssa, ssa_op->op2_def, ssa_op->op2_use, 1);
251 		}
252 		ssa->vars[ssa_op->op2_def].definition = -1;
253 		ssa_op->op2_def = -1;
254 	}
255 	if (ssa_op->result_def >= 0) {
256 		if (ssa_op->result_use >= 0) {
257 			zend_ssa_rename_var_uses(ssa, ssa_op->result_def, ssa_op->result_use, 1);
258 		}
259 		ssa->vars[ssa_op->result_def].definition = -1;
260 		ssa_op->result_def = -1;
261 	}
262 }
263 
264 #define NUM_PHI_SOURCES(phi) \
265 	((phi)->pi >= 0 ? 1 : (ssa->cfg.blocks[(phi)->block].predecessors_count))
266 
267 /* FOREACH_USE and FOREACH_PHI_USE explicitly support "continue"
268  * and changing the use chain of the current element */
269 #define FOREACH_USE(var, use) do { \
270 	int _var_num = (var) - ssa->vars, next; \
271 	for (use = (var)->use_chain; use >= 0; use = next) { \
272 		next = zend_ssa_next_use(ssa->ops, _var_num, use);
273 #define FOREACH_USE_END() \
274 	} \
275 } while (0)
276 
277 #define FOREACH_PHI_USE(var, phi) do { \
278 	int _var_num = (var) - ssa->vars; \
279 	zend_ssa_phi *next_phi; \
280 	for (phi = (var)->phi_use_chain; phi; phi = next_phi) { \
281 		next_phi = zend_ssa_next_use_phi(ssa, _var_num, phi);
282 #define FOREACH_PHI_USE_END() \
283 	} \
284 } while (0)
285 
286 #define FOREACH_PHI_SOURCE(phi, source) do { \
287 	zend_ssa_phi *_phi = (phi); \
288 	int _i, _end = NUM_PHI_SOURCES(phi); \
289 	for (_i = 0; _i < _end; _i++) { \
290 		ZEND_ASSERT(_phi->sources[_i] >= 0); \
291 		source = _phi->sources[_i];
292 #define FOREACH_PHI_SOURCE_END() \
293 	} \
294 } while (0)
295 
296 #define FOREACH_PHI(phi) do { \
297 	int _i; \
298 	for (_i = 0; _i < ssa->cfg.blocks_count; _i++) { \
299 		phi = ssa->blocks[_i].phis; \
300 		for (; phi; phi = phi->next) {
301 #define FOREACH_PHI_END() \
302 		} \
303 	} \
304 } while (0)
305 
306 #define FOREACH_BLOCK(block) do { \
307 	int _i; \
308 	for (_i = 0; _i < ssa->cfg.blocks_count; _i++) { \
309 		(block) = &ssa->cfg.blocks[_i]; \
310 		if (!((block)->flags & ZEND_BB_REACHABLE)) { \
311 			continue; \
312 		}
313 #define FOREACH_BLOCK_END() \
314 	} \
315 } while (0)
316 
317 /* Does not support "break" */
318 #define FOREACH_INSTR_NUM(i) do { \
319 	zend_basic_block *_block; \
320 	FOREACH_BLOCK(_block) { \
321 		uint32_t _end = _block->start + _block->len; \
322 		for ((i) = _block->start; (i) < _end; (i)++) {
323 #define FOREACH_INSTR_NUM_END() \
324 		} \
325 	} FOREACH_BLOCK_END(); \
326 } while (0)
327 
328 #endif /* ZEND_SSA_H */
329