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 | 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: 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 zend_bool underflow;
29 zend_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 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 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);
150 int zend_ssa_compute_use_def_chains(zend_arena **arena, const zend_op_array *op_array, zend_ssa *ssa);
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_instr(zend_ssa *ssa, zend_op *opline, zend_ssa_op *ssa_op);
155 void zend_ssa_remove_phi(zend_ssa *ssa, zend_ssa_phi *phi);
156 void zend_ssa_remove_uses_of_var(zend_ssa *ssa, int var_num);
157 void zend_ssa_remove_block(zend_op_array *op_array, zend_ssa *ssa, int b);
158 void zend_ssa_rename_var_uses(zend_ssa *ssa, int old_var, int new_var, zend_bool update_types);
159
_zend_ssa_remove_def(zend_ssa_var * var)160 static zend_always_inline void _zend_ssa_remove_def(zend_ssa_var *var)
161 {
162 ZEND_ASSERT(var->definition >= 0);
163 ZEND_ASSERT(var->use_chain < 0);
164 ZEND_ASSERT(!var->phi_use_chain);
165 var->definition = -1;
166 }
167
zend_ssa_remove_result_def(zend_ssa * ssa,zend_ssa_op * ssa_op)168 static zend_always_inline void zend_ssa_remove_result_def(zend_ssa *ssa, zend_ssa_op *ssa_op)
169 {
170 zend_ssa_var *var = &ssa->vars[ssa_op->result_def];
171 _zend_ssa_remove_def(var);
172 ssa_op->result_def = -1;
173 }
174
zend_ssa_remove_op1_def(zend_ssa * ssa,zend_ssa_op * ssa_op)175 static zend_always_inline void zend_ssa_remove_op1_def(zend_ssa *ssa, zend_ssa_op *ssa_op)
176 {
177 zend_ssa_var *var = &ssa->vars[ssa_op->op1_def];
178 _zend_ssa_remove_def(var);
179 ssa_op->op1_def = -1;
180 }
181
zend_ssa_remove_op2_def(zend_ssa * ssa,zend_ssa_op * ssa_op)182 static zend_always_inline void zend_ssa_remove_op2_def(zend_ssa *ssa, zend_ssa_op *ssa_op)
183 {
184 zend_ssa_var *var = &ssa->vars[ssa_op->op2_def];
185 _zend_ssa_remove_def(var);
186 ssa_op->op2_def = -1;
187 }
188
END_EXTERN_C()189 END_EXTERN_C()
190
191 static zend_always_inline int zend_ssa_next_use(const zend_ssa_op *ssa_op, int var, int use)
192 {
193 ssa_op += use;
194 if (ssa_op->op1_use == var) {
195 return ssa_op->op1_use_chain;
196 } else if (ssa_op->op2_use == var) {
197 return ssa_op->op2_use_chain;
198 } else {
199 return ssa_op->res_use_chain;
200 }
201 }
202
zend_ssa_next_use_phi(const zend_ssa * ssa,int var,const zend_ssa_phi * p)203 static zend_always_inline zend_ssa_phi* zend_ssa_next_use_phi(const zend_ssa *ssa, int var, const zend_ssa_phi *p)
204 {
205 if (p->pi >= 0) {
206 return p->use_chains[0];
207 } else {
208 int j;
209 for (j = 0; j < ssa->cfg.blocks[p->block].predecessors_count; j++) {
210 if (p->sources[j] == var) {
211 return p->use_chains[j];
212 }
213 }
214 }
215 return NULL;
216 }
217
zend_ssa_is_no_val_use(const zend_op * opline,const zend_ssa_op * ssa_op,int var)218 static zend_always_inline zend_bool zend_ssa_is_no_val_use(const zend_op *opline, const zend_ssa_op *ssa_op, int var)
219 {
220 if (opline->opcode == ZEND_ASSIGN
221 || opline->opcode == ZEND_UNSET_CV
222 || opline->opcode == ZEND_BIND_GLOBAL
223 || opline->opcode == ZEND_BIND_STATIC) {
224 return ssa_op->op1_use == var && ssa_op->op2_use != var;
225 }
226 if (opline->opcode == ZEND_FE_FETCH_R || opline->opcode == ZEND_FE_FETCH_RW) {
227 return ssa_op->op2_use == var && ssa_op->op1_use != var;
228 }
229 if (ssa_op->result_use == var
230 && opline->opcode != ZEND_ADD_ARRAY_ELEMENT
231 && opline->opcode != ZEND_ADD_ARRAY_UNPACK) {
232 return ssa_op->op1_use != var && ssa_op->op2_use != var;
233 }
234 return 0;
235 }
236
zend_ssa_rename_defs_of_instr(zend_ssa * ssa,zend_ssa_op * ssa_op)237 static zend_always_inline void zend_ssa_rename_defs_of_instr(zend_ssa *ssa, zend_ssa_op *ssa_op) {
238 /* Rename def to use if possible. Mark variable as not defined otherwise. */
239 if (ssa_op->op1_def >= 0) {
240 if (ssa_op->op1_use >= 0) {
241 zend_ssa_rename_var_uses(ssa, ssa_op->op1_def, ssa_op->op1_use, 1);
242 }
243 ssa->vars[ssa_op->op1_def].definition = -1;
244 ssa_op->op1_def = -1;
245 }
246 if (ssa_op->op2_def >= 0) {
247 if (ssa_op->op2_use >= 0) {
248 zend_ssa_rename_var_uses(ssa, ssa_op->op2_def, ssa_op->op2_use, 1);
249 }
250 ssa->vars[ssa_op->op2_def].definition = -1;
251 ssa_op->op2_def = -1;
252 }
253 if (ssa_op->result_def >= 0) {
254 if (ssa_op->result_use >= 0) {
255 zend_ssa_rename_var_uses(ssa, ssa_op->result_def, ssa_op->result_use, 1);
256 }
257 ssa->vars[ssa_op->result_def].definition = -1;
258 ssa_op->result_def = -1;
259 }
260 }
261
262 #define NUM_PHI_SOURCES(phi) \
263 ((phi)->pi >= 0 ? 1 : (ssa->cfg.blocks[(phi)->block].predecessors_count))
264
265 /* FOREACH_USE and FOREACH_PHI_USE explicitly support "continue"
266 * and changing the use chain of the current element */
267 #define FOREACH_USE(var, use) do { \
268 int _var_num = (var) - ssa->vars, next; \
269 for (use = (var)->use_chain; use >= 0; use = next) { \
270 next = zend_ssa_next_use(ssa->ops, _var_num, use);
271 #define FOREACH_USE_END() \
272 } \
273 } while (0)
274
275 #define FOREACH_PHI_USE(var, phi) do { \
276 int _var_num = (var) - ssa->vars; \
277 zend_ssa_phi *next_phi; \
278 for (phi = (var)->phi_use_chain; phi; phi = next_phi) { \
279 next_phi = zend_ssa_next_use_phi(ssa, _var_num, phi);
280 #define FOREACH_PHI_USE_END() \
281 } \
282 } while (0)
283
284 #define FOREACH_PHI_SOURCE(phi, source) do { \
285 zend_ssa_phi *_phi = (phi); \
286 int _i, _end = NUM_PHI_SOURCES(phi); \
287 for (_i = 0; _i < _end; _i++) { \
288 ZEND_ASSERT(_phi->sources[_i] >= 0); \
289 source = _phi->sources[_i];
290 #define FOREACH_PHI_SOURCE_END() \
291 } \
292 } while (0)
293
294 #define FOREACH_PHI(phi) do { \
295 int _i; \
296 for (_i = 0; _i < ssa->cfg.blocks_count; _i++) { \
297 phi = ssa->blocks[_i].phis; \
298 for (; phi; phi = phi->next) {
299 #define FOREACH_PHI_END() \
300 } \
301 } \
302 } while (0)
303
304 #define FOREACH_BLOCK(block) do { \
305 int _i; \
306 for (_i = 0; _i < ssa->cfg.blocks_count; _i++) { \
307 (block) = &ssa->cfg.blocks[_i]; \
308 if (!((block)->flags & ZEND_BB_REACHABLE)) { \
309 continue; \
310 }
311 #define FOREACH_BLOCK_END() \
312 } \
313 } while (0)
314
315 /* Does not support "break" */
316 #define FOREACH_INSTR_NUM(i) do { \
317 zend_basic_block *_block; \
318 FOREACH_BLOCK(_block) { \
319 uint32_t _end = _block->start + _block->len; \
320 for ((i) = _block->start; (i) < _end; (i)++) {
321 #define FOREACH_INSTR_NUM_END() \
322 } \
323 } FOREACH_BLOCK_END(); \
324 } while (0)
325
326 #endif /* ZEND_SSA_H */
327
