/src/php-src/Zend/Optimizer/scdf.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | +----------------------------------------------------------------------+ |
3 | | | Zend Engine, Sparse Conditional Data Flow Propagation Framework | |
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: Nikita Popov <nikic@php.net> | |
16 | | +----------------------------------------------------------------------+ |
17 | | */ |
18 | | |
19 | | #include "Optimizer/zend_optimizer_internal.h" |
20 | | #include "Optimizer/scdf.h" |
21 | | |
22 | | /* This defines a generic framework for sparse conditional dataflow propagation. The algorithm is |
23 | | * based on "Sparse conditional constant propagation" by Wegman and Zadeck. We're using a |
24 | | * generalized implementation as described in chapter 8.3 of the SSA book. |
25 | | * |
26 | | * Every SSA variable is associated with an element on a finite-height lattice, those value can only |
27 | | * ever be lowered during the operation of the algorithm. If a value is lowered all instructions and |
28 | | * phis using that value need to be reconsidered (this is done by adding the variable to a |
29 | | * worklist). For phi functions the result is computed by applying the meet operation to the |
30 | | * operands. This continues until a fixed point is reached. |
31 | | * |
32 | | * The algorithm is control-flow sensitive: All blocks except the start block are initially assumed |
33 | | * to be unreachable. When considering a branch instruction, we determine the feasible successors |
34 | | * based on the current state of the variable lattice. If a new edge becomes feasible we either have |
35 | | * to mark the successor block executable and consider all instructions in it, or, if the target is |
36 | | * already executable, we only have to reconsider the phi functions (as we only consider phi |
37 | | * operands which are associated with a feasible edge). |
38 | | * |
39 | | * The generic framework requires the definition of three functions: |
40 | | * * visit_instr() should recompute the lattice values of all SSA variables defined by an |
41 | | * instruction. |
42 | | * * visit_phi() should recompute the lattice value of the SSA variable defined by the phi. While |
43 | | * doing this it should only consider operands for which scfg_is_edge_feasible() returns true. |
44 | | * * get_feasible_successors() should determine the feasible successors for a branch instruction. |
45 | | * Note that this callback only needs to handle conditional branches (with two successors). |
46 | | */ |
47 | | |
48 | | #if 0 |
49 | | #define DEBUG_PRINT(...) fprintf(stderr, __VA_ARGS__) |
50 | | #else |
51 | | #define DEBUG_PRINT(...) |
52 | | #endif |
53 | | |
54 | 211k | void scdf_mark_edge_feasible(scdf_ctx *scdf, int from, int to) { |
55 | 211k | uint32_t edge = scdf_edge(&scdf->ssa->cfg, from, to); |
56 | | |
57 | 211k | if (zend_bitset_in(scdf->feasible_edges, edge)) { |
58 | | /* We already handled this edge */ |
59 | 3.25k | return; |
60 | 3.25k | } |
61 | | |
62 | 207k | DEBUG_PRINT("Marking edge %d->%d feasible\n", from, to); |
63 | 207k | zend_bitset_incl(scdf->feasible_edges, edge); |
64 | | |
65 | 207k | if (!zend_bitset_in(scdf->executable_blocks, to)) { |
66 | 197k | if (!zend_bitset_in(scdf->block_worklist, to)) { |
67 | 140k | DEBUG_PRINT("Adding block %d to worklist\n", to); |
68 | 140k | } |
69 | 197k | zend_bitset_incl(scdf->block_worklist, to); |
70 | 197k | } else { |
71 | | /* Block is already executable, only a new edge became feasible. |
72 | | * Reevaluate phi nodes to account for changed source operands. */ |
73 | 10.4k | zend_ssa_block *ssa_block = &scdf->ssa->blocks[to]; |
74 | 10.4k | zend_ssa_phi *phi; |
75 | 36.0k | for (phi = ssa_block->phis; phi; phi = phi->next) { |
76 | 25.6k | zend_bitset_excl(scdf->phi_var_worklist, phi->ssa_var); |
77 | 25.6k | scdf->handlers.visit_phi(scdf, phi); |
78 | 25.6k | } |
79 | 10.4k | } |
80 | 207k | } |
81 | | |
82 | 74.1k | void scdf_init(zend_optimizer_ctx *ctx, scdf_ctx *scdf, zend_op_array *op_array, zend_ssa *ssa) { |
83 | 74.1k | scdf->op_array = op_array; |
84 | 74.1k | scdf->ssa = ssa; |
85 | | |
86 | 74.1k | scdf->instr_worklist_len = zend_bitset_len(op_array->last); |
87 | 74.1k | scdf->phi_var_worklist_len = zend_bitset_len(ssa->vars_count); |
88 | 74.1k | scdf->block_worklist_len = zend_bitset_len(ssa->cfg.blocks_count); |
89 | | |
90 | 74.1k | scdf->instr_worklist = zend_arena_calloc(&ctx->arena, |
91 | 74.1k | scdf->instr_worklist_len + scdf->phi_var_worklist_len + 2 * scdf->block_worklist_len + zend_bitset_len(ssa->cfg.edges_count), |
92 | 74.1k | sizeof(zend_ulong)); |
93 | | |
94 | 74.1k | scdf->phi_var_worklist = scdf->instr_worklist + scdf->instr_worklist_len; |
95 | 74.1k | scdf->block_worklist = scdf->phi_var_worklist + scdf->phi_var_worklist_len; |
96 | 74.1k | scdf->executable_blocks = scdf->block_worklist + scdf->block_worklist_len; |
97 | 74.1k | scdf->feasible_edges = scdf->executable_blocks + scdf->block_worklist_len; |
98 | | |
99 | 74.1k | zend_bitset_incl(scdf->block_worklist, 0); |
100 | 74.1k | zend_bitset_incl(scdf->executable_blocks, 0); |
101 | 74.1k | } |
102 | | |
103 | 74.1k | void scdf_solve(scdf_ctx *scdf, const char *name) { |
104 | 74.1k | zend_ssa *ssa = scdf->ssa; |
105 | 74.1k | DEBUG_PRINT("Start SCDF solve (%s)\n", name); |
106 | 151k | while (!zend_bitset_empty(scdf->instr_worklist, scdf->instr_worklist_len) |
107 | 151k | || !zend_bitset_empty(scdf->phi_var_worklist, scdf->phi_var_worklist_len) |
108 | 151k | || !zend_bitset_empty(scdf->block_worklist, scdf->block_worklist_len) |
109 | 77.1k | ) { |
110 | 77.1k | int i; |
111 | 82.2k | while ((i = zend_bitset_pop_first(scdf->phi_var_worklist, scdf->phi_var_worklist_len)) >= 0) { |
112 | 5.14k | zend_ssa_phi *phi = ssa->vars[i].definition_phi; |
113 | 5.14k | ZEND_ASSERT(phi); |
114 | 5.14k | if (zend_bitset_in(scdf->executable_blocks, phi->block)) { |
115 | 4.08k | scdf->handlers.visit_phi(scdf, phi); |
116 | 4.08k | } |
117 | 5.14k | } |
118 | | |
119 | 86.7k | while ((i = zend_bitset_pop_first(scdf->instr_worklist, scdf->instr_worklist_len)) >= 0) { |
120 | 9.66k | int block_num = ssa->cfg.map[i]; |
121 | 9.66k | if (zend_bitset_in(scdf->executable_blocks, block_num)) { |
122 | 7.84k | zend_basic_block *block = &ssa->cfg.blocks[block_num]; |
123 | 7.84k | zend_op *opline = &scdf->op_array->opcodes[i]; |
124 | 7.84k | zend_ssa_op *ssa_op = &ssa->ops[i]; |
125 | 7.84k | if (opline->opcode == ZEND_OP_DATA) { |
126 | 24 | opline--; |
127 | 24 | ssa_op--; |
128 | 24 | } |
129 | 7.84k | scdf->handlers.visit_instr(scdf, opline, ssa_op); |
130 | 7.84k | if (i == block->start + block->len - 1) { |
131 | 3.01k | if (block->successors_count == 1) { |
132 | 1.21k | scdf_mark_edge_feasible(scdf, block_num, block->successors[0]); |
133 | 1.80k | } else if (block->successors_count > 1) { |
134 | 1.79k | scdf->handlers.mark_feasible_successors(scdf, block_num, block, opline, ssa_op); |
135 | 1.79k | } |
136 | 3.01k | } |
137 | 7.84k | } |
138 | 9.66k | } |
139 | | |
140 | 292k | while ((i = zend_bitset_pop_first(scdf->block_worklist, scdf->block_worklist_len)) >= 0) { |
141 | | /* This block is now live. Interpret phis and instructions in it. */ |
142 | 214k | zend_basic_block *block = &ssa->cfg.blocks[i]; |
143 | 214k | zend_ssa_block *ssa_block = &ssa->blocks[i]; |
144 | | |
145 | 214k | DEBUG_PRINT("Pop block %d from worklist\n", i); |
146 | 214k | zend_bitset_incl(scdf->executable_blocks, i); |
147 | | |
148 | 214k | { |
149 | 214k | zend_ssa_phi *phi; |
150 | 390k | for (phi = ssa_block->phis; phi; phi = phi->next) { |
151 | 176k | zend_bitset_excl(scdf->phi_var_worklist, phi->ssa_var); |
152 | 176k | scdf->handlers.visit_phi(scdf, phi); |
153 | 176k | } |
154 | 214k | } |
155 | | |
156 | 214k | if (block->len == 0) { |
157 | | /* Zero length blocks don't have a last instruction that would normally do this */ |
158 | 139 | scdf_mark_edge_feasible(scdf, i, block->successors[0]); |
159 | 214k | } else { |
160 | 214k | zend_op *opline = NULL; |
161 | 214k | int j, end = block->start + block->len; |
162 | 1.55M | for (j = block->start; j < end; j++) { |
163 | 1.34M | opline = &scdf->op_array->opcodes[j]; |
164 | 1.34M | zend_bitset_excl(scdf->instr_worklist, j); |
165 | 1.34M | if (opline->opcode != ZEND_OP_DATA) { |
166 | 1.32M | scdf->handlers.visit_instr(scdf, opline, &ssa->ops[j]); |
167 | 1.32M | } |
168 | 1.34M | } |
169 | 214k | if (block->successors_count == 1) { |
170 | 71.0k | scdf_mark_edge_feasible(scdf, i, block->successors[0]); |
171 | 143k | } else if (block->successors_count > 1) { |
172 | 68.8k | ZEND_ASSERT(opline && "Should have opline in non-empty block"); |
173 | 68.8k | if (opline->opcode == ZEND_OP_DATA) { |
174 | 0 | opline--; |
175 | 0 | j--; |
176 | 0 | } |
177 | 68.8k | scdf->handlers.mark_feasible_successors(scdf, i, block, opline, &ssa->ops[j-1]); |
178 | 68.8k | } |
179 | 214k | } |
180 | 214k | } |
181 | 77.1k | } |
182 | 74.1k | } |
183 | | |
184 | | /* If a live range starts in a reachable block and ends in an unreachable block, we should |
185 | | * not eliminate the latter. While it cannot be reached, the FREE opcode of the loop var |
186 | | * is necessary for the correctness of temporary compaction. */ |
187 | | static bool is_live_loop_var_free( |
188 | 724 | scdf_ctx *scdf, const zend_op *opline, const zend_ssa_op *ssa_op) { |
189 | 724 | if (!zend_optimizer_is_loop_var_free(opline)) { |
190 | 680 | return false; |
191 | 680 | } |
192 | | |
193 | 44 | int var = ssa_op->op1_use; |
194 | 44 | if (var < 0) { |
195 | 0 | return false; |
196 | 0 | } |
197 | | |
198 | 44 | zend_ssa_var *ssa_var = &scdf->ssa->vars[var]; |
199 | 44 | uint32_t def_block; |
200 | 44 | if (ssa_var->definition >= 0) { |
201 | 12 | def_block = scdf->ssa->cfg.map[ssa_var->definition]; |
202 | 32 | } else { |
203 | 32 | def_block = ssa_var->definition_phi->block; |
204 | 32 | } |
205 | 44 | return zend_bitset_in(scdf->executable_blocks, def_block); |
206 | 44 | } |
207 | | |
208 | 1.69k | static bool kept_alive_by_loop_var_free(scdf_ctx *scdf, const zend_basic_block *block) { |
209 | 1.69k | const zend_op_array *op_array = scdf->op_array; |
210 | 1.69k | const zend_cfg *cfg = &scdf->ssa->cfg; |
211 | 1.69k | if (!(cfg->flags & ZEND_FUNC_FREE_LOOP_VAR)) { |
212 | 1.38k | return false; |
213 | 1.38k | } |
214 | | |
215 | 959 | for (uint32_t i = block->start; i < block->start + block->len; i++) { |
216 | 666 | if (is_live_loop_var_free(scdf, &op_array->opcodes[i], &scdf->ssa->ops[i])) { |
217 | 22 | return true; |
218 | 22 | } |
219 | 666 | } |
220 | 293 | return false; |
221 | 315 | } |
222 | | |
223 | 22 | static uint32_t cleanup_loop_var_free_block(scdf_ctx *scdf, zend_basic_block *block) { |
224 | 22 | zend_ssa *ssa = scdf->ssa; |
225 | 22 | const zend_op_array *op_array = scdf->op_array; |
226 | 22 | const zend_cfg *cfg = &ssa->cfg; |
227 | 22 | int block_num = block - cfg->blocks; |
228 | 22 | uint32_t removed_ops = 0; |
229 | | |
230 | | /* Removes phi nodes */ |
231 | 24 | for (zend_ssa_phi *phi = ssa->blocks[block_num].phis; phi; phi = phi->next) { |
232 | 2 | zend_ssa_remove_uses_of_var(ssa, phi->ssa_var); |
233 | 2 | zend_ssa_remove_phi(ssa, phi); |
234 | 2 | } |
235 | | |
236 | 80 | for (uint32_t i = block->start; i < block->start + block->len; i++) { |
237 | 58 | zend_op *opline = &op_array->opcodes[i]; |
238 | 58 | zend_ssa_op *ssa_op = &scdf->ssa->ops[i]; |
239 | 58 | if (opline->opcode == ZEND_NOP |
240 | 58 | || is_live_loop_var_free(scdf, opline, ssa_op)) { |
241 | 22 | continue; |
242 | 22 | } |
243 | | |
244 | | /* While we have to preserve the loop var free, we can still remove other instructions |
245 | | * in the block. */ |
246 | 36 | zend_ssa_remove_defs_of_instr(ssa, ssa_op); |
247 | 36 | zend_ssa_remove_instr(ssa, opline, ssa_op); |
248 | 36 | removed_ops++; |
249 | 36 | } |
250 | | |
251 | 22 | zend_ssa_remove_block_from_cfg(ssa, block_num); |
252 | | |
253 | 22 | return removed_ops; |
254 | 22 | } |
255 | | |
256 | | /* Removes unreachable blocks. This will remove both the instructions (and phis) in the |
257 | | * blocks, as well as remove them from the successor / predecessor lists and mark them |
258 | | * unreachable. Blocks already marked unreachable are not removed. */ |
259 | 74.1k | uint32_t scdf_remove_unreachable_blocks(scdf_ctx *scdf) { |
260 | 74.1k | zend_ssa *ssa = scdf->ssa; |
261 | 74.1k | int i; |
262 | 74.1k | uint32_t removed_ops = 0; |
263 | 290k | for (i = 0; i < ssa->cfg.blocks_count; i++) { |
264 | 216k | zend_basic_block *block = &ssa->cfg.blocks[i]; |
265 | 216k | if (!zend_bitset_in(scdf->executable_blocks, i) && (block->flags & ZEND_BB_REACHABLE)) { |
266 | 1.69k | if (!kept_alive_by_loop_var_free(scdf, block)) { |
267 | 1.67k | removed_ops += block->len; |
268 | 1.67k | zend_ssa_remove_block(scdf->op_array, ssa, i); |
269 | 1.67k | } else { |
270 | 22 | removed_ops += cleanup_loop_var_free_block(scdf, block); |
271 | 22 | } |
272 | 1.69k | } |
273 | 216k | } |
274 | 74.1k | return removed_ops; |
275 | 74.1k | } |