1 /*
2 +----------------------------------------------------------------------+
3 | Zend Engine, SSA - Static Single Assignment Form |
4 +----------------------------------------------------------------------+
5 | Copyright (c) 1998-2018 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@zend.com> |
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 struct _zend_ssa_var {
96 int var; /* original var number; op.var for CVs and following numbers for VARs and TMP_VARs */
97 int scc; /* strongly connected component */
98 int definition; /* opcode that defines this value */
99 zend_ssa_phi *definition_phi; /* phi that defines this value */
100 int use_chain; /* uses of this value, linked through opN_use_chain */
101 zend_ssa_phi *phi_use_chain; /* uses of this value in Phi, linked through use_chain */
102 zend_ssa_phi *sym_use_chain; /* uses of this value in Pi constaints */
103 unsigned int no_val : 1; /* value doesn't mater (used as op1 in ZEND_ASSIGN) */
104 unsigned int scc_entry : 1;
105 } zend_ssa_var;
106
107 typedef struct _zend_ssa_var_info {
108 uint32_t type; /* inferred type (see zend_inference.h) */
109 zend_ssa_range range;
110 zend_class_entry *ce;
111 unsigned int has_range : 1;
112 unsigned int is_instanceof : 1; /* 0 - class == "ce", 1 - may be child of "ce" */
113 unsigned int recursive : 1;
114 unsigned int use_as_double : 1;
115 } zend_ssa_var_info;
116
117 typedef struct _zend_ssa {
118 zend_cfg cfg; /* control flow graph */
119 int rt_constants; /* run-time or compile-time */
120 int vars_count; /* number of SSA variables */
121 zend_ssa_block *blocks; /* array of SSA blocks */
122 zend_ssa_op *ops; /* array of SSA instructions */
123 zend_ssa_var *vars; /* use/def chain of SSA variables */
124 int sccs; /* number of SCCs */
125 zend_ssa_var_info *var_info;
126 } zend_ssa;
127
128 BEGIN_EXTERN_C()
129
130 int zend_build_ssa(zend_arena **arena, const zend_script *script, const zend_op_array *op_array, uint32_t build_flags, zend_ssa *ssa, uint32_t *func_flags);
131 int zend_ssa_compute_use_def_chains(zend_arena **arena, const zend_op_array *op_array, zend_ssa *ssa);
132 int zend_ssa_unlink_use_chain(zend_ssa *ssa, int op, int var);
133
END_EXTERN_C()134 END_EXTERN_C()
135
136 static zend_always_inline int zend_ssa_next_use(const zend_ssa_op *ssa_op, int var, int use)
137 {
138 ssa_op += use;
139 if (ssa_op->result_use == var) {
140 return ssa_op->res_use_chain;
141 }
142 return (ssa_op->op1_use == var) ? ssa_op->op1_use_chain : ssa_op->op2_use_chain;
143 }
144
zend_ssa_next_use_phi(const zend_ssa * ssa,int var,const zend_ssa_phi * p)145 static zend_always_inline zend_ssa_phi* zend_ssa_next_use_phi(const zend_ssa *ssa, int var, const zend_ssa_phi *p)
146 {
147 if (p->pi >= 0) {
148 return p->use_chains[0];
149 } else {
150 int j;
151 for (j = 0; j < ssa->cfg.blocks[p->block].predecessors_count; j++) {
152 if (p->sources[j] == var) {
153 return p->use_chains[j];
154 }
155 }
156 }
157 return NULL;
158 }
159
160 #endif /* ZEND_SSA_H */
161
162 /*
163 * Local variables:
164 * tab-width: 4
165 * c-basic-offset: 4
166 * indent-tabs-mode: t
167 * End:
168 */
169