1 /*
2 +----------------------------------------------------------------------+
3 | Zend Engine, e-SSA based Type & Range Inference |
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_INFERENCE_H
20 #define ZEND_INFERENCE_H
21
22 #include "zend_optimizer.h"
23 #include "zend_ssa.h"
24 #include "zend_bitset.h"
25
26 /* Bitmask for type inference (zend_ssa_var_info.type) */
27 #include "zend_type_info.h"
28
29 #define MAY_BE_PACKED_GUARD (1<<27) /* needs packed array guard */
30 #define MAY_BE_CLASS_GUARD (1<<27) /* needs class guard */
31 #define MAY_BE_GUARD (1<<28) /* needs type guard */
32 //#define MAY_BE_IN_REG (1<<29) /* deprecated and not used */
33
34 //TODO: remome MAY_BE_RC1, MAY_BE_RCN???
35 #define MAY_BE_RC1 (1<<30) /* may be non-reference with refcount == 1 */
36 #define MAY_BE_RCN (1u<<31) /* may be non-reference with refcount > 1 */
37
38 #define MAY_HAVE_DTOR \
39 (MAY_BE_OBJECT|MAY_BE_RESOURCE \
40 |MAY_BE_ARRAY_OF_ARRAY|MAY_BE_ARRAY_OF_OBJECT|MAY_BE_ARRAY_OF_RESOURCE)
41
42 #define DEFINE_SSA_OP_HAS_RANGE(opN) \
43 static zend_always_inline zend_bool _ssa_##opN##_has_range(const zend_op_array *op_array, const zend_ssa *ssa, const zend_op *opline, const zend_ssa_op *ssa_op) \
44 { \
45 if (opline->opN##_type == IS_CONST) { \
46 zval *zv = CRT_CONSTANT(opline->opN); \
47 return (Z_TYPE_P(zv) == IS_LONG || Z_TYPE_P(zv) == IS_TRUE || Z_TYPE_P(zv) == IS_FALSE || Z_TYPE_P(zv) == IS_NULL); \
48 } else { \
49 return (opline->opN##_type != IS_UNUSED && \
50 ssa->var_info && \
51 ssa_op->opN##_use >= 0 && \
52 ssa->var_info[ssa_op->opN##_use].has_range); \
53 } \
54 return 0; \
55 } \
56
57 #define DEFINE_SSA_OP_MIN_RANGE(opN) \
58 static zend_always_inline zend_long _ssa_##opN##_min_range(const zend_op_array *op_array, const zend_ssa *ssa, const zend_op *opline, const zend_ssa_op *ssa_op) \
59 { \
60 if (opline->opN##_type == IS_CONST) { \
61 zval *zv = CRT_CONSTANT(opline->opN); \
62 if (Z_TYPE_P(zv) == IS_LONG) { \
63 return Z_LVAL_P(zv); \
64 } else if (Z_TYPE_P(zv) == IS_TRUE) { \
65 return 1; \
66 } else if (Z_TYPE_P(zv) == IS_FALSE) { \
67 return 0; \
68 } else if (Z_TYPE_P(zv) == IS_NULL) { \
69 return 0; \
70 } \
71 } else if (opline->opN##_type != IS_UNUSED && \
72 ssa->var_info && \
73 ssa_op->opN##_use >= 0 && \
74 ssa->var_info[ssa_op->opN##_use].has_range) { \
75 return ssa->var_info[ssa_op->opN##_use].range.min; \
76 } \
77 return ZEND_LONG_MIN; \
78 } \
79
80 #define DEFINE_SSA_OP_MAX_RANGE(opN) \
81 static zend_always_inline zend_long _ssa_##opN##_max_range(const zend_op_array *op_array, const zend_ssa *ssa, const zend_op *opline, const zend_ssa_op *ssa_op) \
82 { \
83 if (opline->opN##_type == IS_CONST) { \
84 zval *zv = CRT_CONSTANT(opline->opN); \
85 if (Z_TYPE_P(zv) == IS_LONG) { \
86 return Z_LVAL_P(zv); \
87 } else if (Z_TYPE_P(zv) == IS_TRUE) { \
88 return 1; \
89 } else if (Z_TYPE_P(zv) == IS_FALSE) { \
90 return 0; \
91 } else if (Z_TYPE_P(zv) == IS_NULL) { \
92 return 0; \
93 } \
94 } else if (opline->opN##_type != IS_UNUSED && \
95 ssa->var_info && \
96 ssa_op->opN##_use >= 0 && \
97 ssa->var_info[ssa_op->opN##_use].has_range) { \
98 return ssa->var_info[ssa_op->opN##_use].range.max; \
99 } \
100 return ZEND_LONG_MAX; \
101 } \
102
103 #define DEFINE_SSA_OP_RANGE_UNDERFLOW(opN) \
104 static zend_always_inline char _ssa_##opN##_range_underflow(const zend_op_array *op_array, const zend_ssa *ssa, const zend_op *opline, const zend_ssa_op *ssa_op) \
105 { \
106 if (opline->opN##_type == IS_CONST) { \
107 zval *zv = CRT_CONSTANT(opline->opN); \
108 if (Z_TYPE_P(zv) == IS_LONG || Z_TYPE_P(zv) == IS_TRUE || Z_TYPE_P(zv) == IS_FALSE || Z_TYPE_P(zv) == IS_NULL) { \
109 return 0; \
110 } \
111 } else if (opline->opN##_type != IS_UNUSED && \
112 ssa->var_info && \
113 ssa_op->opN##_use >= 0 && \
114 ssa->var_info[ssa_op->opN##_use].has_range) { \
115 return ssa->var_info[ssa_op->opN##_use].range.underflow; \
116 } \
117 return 1; \
118 } \
119
120 #define DEFINE_SSA_OP_RANGE_OVERFLOW(opN) \
121 static zend_always_inline char _ssa_##opN##_range_overflow(const zend_op_array *op_array, const zend_ssa *ssa, const zend_op *opline, const zend_ssa_op *ssa_op) \
122 { \
123 if (opline->opN##_type == IS_CONST) { \
124 zval *zv = CRT_CONSTANT(opline->opN); \
125 if (Z_TYPE_P(zv) == IS_LONG || Z_TYPE_P(zv) == IS_TRUE || Z_TYPE_P(zv) == IS_FALSE || Z_TYPE_P(zv) == IS_NULL) { \
126 return 0; \
127 } \
128 } else if (opline->opN##_type != IS_UNUSED && \
129 ssa->var_info && \
130 ssa_op->opN##_use >= 0 && \
131 ssa->var_info[ssa_op->opN##_use].has_range) { \
132 return ssa->var_info[ssa_op->opN##_use].range.overflow; \
133 } \
134 return 1; \
135 } \
136
137 DEFINE_SSA_OP_HAS_RANGE(op1)
DEFINE_SSA_OP_MIN_RANGE(op1)138 DEFINE_SSA_OP_MIN_RANGE(op1)
139 DEFINE_SSA_OP_MAX_RANGE(op1)
140 DEFINE_SSA_OP_RANGE_UNDERFLOW(op1)
141 DEFINE_SSA_OP_RANGE_OVERFLOW(op1)
142 DEFINE_SSA_OP_HAS_RANGE(op2)
143 DEFINE_SSA_OP_MIN_RANGE(op2)
144 DEFINE_SSA_OP_MAX_RANGE(op2)
145 DEFINE_SSA_OP_RANGE_UNDERFLOW(op2)
146 DEFINE_SSA_OP_RANGE_OVERFLOW(op2)
147
148 #define OP1_HAS_RANGE() (_ssa_op1_has_range (op_array, ssa, opline, ssa_op))
149 #define OP1_MIN_RANGE() (_ssa_op1_min_range (op_array, ssa, opline, ssa_op))
150 #define OP1_MAX_RANGE() (_ssa_op1_max_range (op_array, ssa, opline, ssa_op))
151 #define OP1_RANGE_UNDERFLOW() (_ssa_op1_range_underflow (op_array, ssa, opline, ssa_op))
152 #define OP1_RANGE_OVERFLOW() (_ssa_op1_range_overflow (op_array, ssa, opline, ssa_op))
153 #define OP2_HAS_RANGE() (_ssa_op2_has_range (op_array, ssa, opline, ssa_op))
154 #define OP2_MIN_RANGE() (_ssa_op2_min_range (op_array, ssa, opline, ssa_op))
155 #define OP2_MAX_RANGE() (_ssa_op2_max_range (op_array, ssa, opline, ssa_op))
156 #define OP2_RANGE_UNDERFLOW() (_ssa_op2_range_underflow (op_array, ssa, opline, ssa_op))
157 #define OP2_RANGE_OVERFLOW() (_ssa_op2_range_overflow (op_array, ssa, opline, ssa_op))
158
159 static zend_always_inline uint32_t _const_op_type(const zval *zv) {
160 if (Z_TYPE_P(zv) == IS_CONSTANT_AST) {
161 return MAY_BE_RC1 | MAY_BE_RCN | MAY_BE_ANY | MAY_BE_ARRAY_KEY_ANY | MAY_BE_ARRAY_OF_ANY;
162 } else if (Z_TYPE_P(zv) == IS_ARRAY) {
163 HashTable *ht = Z_ARRVAL_P(zv);
164 uint32_t tmp = MAY_BE_ARRAY;
165 zend_string *str;
166 zval *val;
167
168 if (Z_REFCOUNTED_P(zv)) {
169 tmp |= MAY_BE_RC1 | MAY_BE_RCN;
170 } else {
171 tmp |= MAY_BE_RCN;
172 }
173
174 ZEND_HASH_FOREACH_STR_KEY_VAL(ht, str, val) {
175 if (str) {
176 tmp |= MAY_BE_ARRAY_KEY_STRING;
177 } else {
178 tmp |= MAY_BE_ARRAY_KEY_LONG;
179 }
180 tmp |= 1 << (Z_TYPE_P(val) + MAY_BE_ARRAY_SHIFT);
181 } ZEND_HASH_FOREACH_END();
182 if (HT_IS_PACKED(ht)) {
183 tmp &= ~MAY_BE_ARRAY_HASH;
184 }
185 return tmp;
186 } else {
187 uint32_t tmp = (1 << Z_TYPE_P(zv));
188
189 if (Z_REFCOUNTED_P(zv)) {
190 tmp |= MAY_BE_RC1 | MAY_BE_RCN;
191 } else if (Z_TYPE_P(zv) == IS_STRING) {
192 tmp |= MAY_BE_RCN;
193 }
194 return tmp;
195 }
196 }
197
get_ssa_var_info(const zend_ssa * ssa,int ssa_var_num)198 static zend_always_inline uint32_t get_ssa_var_info(const zend_ssa *ssa, int ssa_var_num)
199 {
200 if (ssa->var_info && ssa_var_num >= 0) {
201 return ssa->var_info[ssa_var_num].type;
202 } else {
203 return MAY_BE_UNDEF | MAY_BE_RC1 | MAY_BE_RCN | MAY_BE_REF | MAY_BE_INDIRECT | MAY_BE_ANY | MAY_BE_ARRAY_KEY_ANY | MAY_BE_ARRAY_OF_ANY | MAY_BE_ARRAY_OF_REF;
204 }
205 }
206
207 #define DEFINE_SSA_OP_INFO(opN) \
208 static zend_always_inline uint32_t _ssa_##opN##_info(const zend_op_array *op_array, const zend_ssa *ssa, const zend_op *opline, const zend_ssa_op *ssa_op) \
209 { \
210 if (opline->opN##_type == IS_CONST) { \
211 return _const_op_type(CRT_CONSTANT(opline->opN)); \
212 } else { \
213 return get_ssa_var_info(ssa, ssa->var_info ? ssa_op->opN##_use : -1); \
214 } \
215 } \
216
217 #define DEFINE_SSA_OP_DEF_INFO(opN) \
218 static zend_always_inline uint32_t _ssa_##opN##_def_info(const zend_op_array *op_array, const zend_ssa *ssa, const zend_op *opline, const zend_ssa_op *ssa_op) \
219 { \
220 return get_ssa_var_info(ssa, ssa->var_info ? ssa_op->opN##_def : -1); \
221 } \
222
223
224 DEFINE_SSA_OP_INFO(op1)
DEFINE_SSA_OP_INFO(op2)225 DEFINE_SSA_OP_INFO(op2)
226 DEFINE_SSA_OP_INFO(result)
227 DEFINE_SSA_OP_DEF_INFO(op1)
228 DEFINE_SSA_OP_DEF_INFO(op2)
229 DEFINE_SSA_OP_DEF_INFO(result)
230
231 #define OP1_INFO() (_ssa_op1_info(op_array, ssa, opline, ssa_op))
232 #define OP2_INFO() (_ssa_op2_info(op_array, ssa, opline, ssa_op))
233 #define OP1_DATA_INFO() (_ssa_op1_info(op_array, ssa, (opline+1), (ssa_op+1)))
234 #define OP2_DATA_INFO() (_ssa_op2_info(op_array, ssa, (opline+1), (ssa_op+1)))
235 #define RES_USE_INFO() (_ssa_result_info(op_array, ssa, opline, ssa_op))
236 #define OP1_DEF_INFO() (_ssa_op1_def_info(op_array, ssa, opline, ssa_op))
237 #define OP2_DEF_INFO() (_ssa_op2_def_info(op_array, ssa, opline, ssa_op))
238 #define OP1_DATA_DEF_INFO() (_ssa_op1_def_info(op_array, ssa, (opline+1), (ssa_op+1)))
239 #define OP2_DATA_DEF_INFO() (_ssa_op2_def_info(op_array, ssa, (opline+1), (ssa_op+1)))
240 #define RES_INFO() (_ssa_result_def_info(op_array, ssa, opline, ssa_op))
241
242 static zend_always_inline zend_bool zend_add_will_overflow(zend_long a, zend_long b) {
243 return (b > 0 && a > ZEND_LONG_MAX - b)
244 || (b < 0 && a < ZEND_LONG_MIN - b);
245 }
zend_sub_will_overflow(zend_long a,zend_long b)246 static zend_always_inline zend_bool zend_sub_will_overflow(zend_long a, zend_long b) {
247 return (b > 0 && a < ZEND_LONG_MIN + b)
248 || (b < 0 && a > ZEND_LONG_MAX + b);
249 }
250
251 BEGIN_EXTERN_C()
252
253 int zend_ssa_find_false_dependencies(const zend_op_array *op_array, zend_ssa *ssa);
254 int zend_ssa_find_sccs(const zend_op_array *op_array, zend_ssa *ssa);
255 int zend_ssa_inference(zend_arena **raena, const zend_op_array *op_array, const zend_script *script, zend_ssa *ssa, zend_long optimization_level);
256
257 uint32_t zend_array_element_type(uint32_t t1, zend_uchar op_type, int write, int insert);
258
259 int zend_inference_calc_range(const zend_op_array *op_array, zend_ssa *ssa, int var, int widening, int narrowing, zend_ssa_range *tmp);
260 int zend_inference_propagate_range(const zend_op_array *op_array, zend_ssa *ssa, zend_op *opline, zend_ssa_op* ssa_op, int var, zend_ssa_range *tmp);
261 void zend_inference_init_range(const zend_op_array *op_array, zend_ssa *ssa, int var, zend_bool underflow, zend_long min, zend_long max, zend_bool overflow);
262 int zend_inference_narrowing_meet(zend_ssa_var_info *var_info, zend_ssa_range *r);
263 int zend_inference_widening_meet(zend_ssa_var_info *var_info, zend_ssa_range *r);
264 void zend_inference_check_recursive_dependencies(zend_op_array *op_array);
265
266 int zend_infer_types_ex(const zend_op_array *op_array, const zend_script *script, zend_ssa *ssa, zend_bitset worklist, zend_long optimization_level);
267
268 uint32_t zend_fetch_arg_info_type(
269 const zend_script *script, zend_arg_info *arg_info, zend_class_entry **pce);
270 void zend_init_func_return_info(const zend_op_array *op_array,
271 const zend_script *script,
272 zend_ssa_var_info *ret);
273 void zend_func_return_info(const zend_op_array *op_array,
274 const zend_script *script,
275 int recursive,
276 int widening,
277 zend_ssa_var_info *ret);
278
279 int zend_may_throw_ex(const zend_op *opline, const zend_ssa_op *ssa_op, const zend_op_array *op_array, zend_ssa *ssa, uint32_t t1, uint32_t t2);
280 int zend_may_throw(const zend_op *opline, const zend_ssa_op *ssa_op, const zend_op_array *op_array, zend_ssa *ssa);
281
282 int zend_update_type_info(const zend_op_array *op_array,
283 zend_ssa *ssa,
284 const zend_script *script,
285 zend_op *opline,
286 zend_ssa_op *ssa_op,
287 const zend_op **ssa_opcodes,
288 zend_long optimization_level);
289
290 END_EXTERN_C()
291
292 #endif /* ZEND_INFERENCE_H */
293
