1 /*
2 +----------------------------------------------------------------------+
3 | Zend Engine, Sparse Conditional Data Flow Propagation Framework |
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: Nikita Popov <nikic@php.net> |
16 +----------------------------------------------------------------------+
17 */
18
19 #include "ZendAccelerator.h"
20 #include "Optimizer/zend_optimizer_internal.h"
21 #include "Optimizer/scdf.h"
22
23 /* This defines a generic framework for sparse conditional dataflow propagation. The algorithm is
24 * based on "Sparse conditional constant propagation" by Wegman and Zadeck. We're using a
25 * generalized implementation as described in chapter 8.3 of the SSA book.
26 *
27 * Every SSA variable is associated with an element on a finite-height lattice, those value can only
28 * ever be lowered during the operation of the algorithm. If a value is lowered all instructions and
29 * phis using that value need to be reconsidered (this is done by adding the variable to a
30 * worklist). For phi functions the result is computed by applying the meet operation to the
31 * operands. This continues until a fixed point is reached.
32 *
33 * The algorithm is control-flow sensitive: All blocks except the start block are initially assumed
34 * to be unreachable. When considering a branch instruction, we determine the feasible successors
35 * based on the current state of the variable lattice. If a new edge becomes feasible we either have
36 * to mark the successor block executable and consider all instructions in it, or, if the target is
37 * already executable, we only have to reconsider the phi functions (as we only consider phi
38 * operands which are associated with a feasible edge).
39 *
40 * The generic framework requires the definition of three functions:
41 * * visit_instr() should recompute the lattice values of all SSA variables defined by an
42 * instruction.
43 * * visit_phi() should recompute the lattice value of the SSA variable defined by the phi. While
44 * doing this it should only consider operands for which scfg_is_edge_feasible() returns true.
45 * * get_feasible_successors() should determine the feasible successors for a branch instruction.
46 * Note that this callback only needs to handle conditional branches (with two successors).
47 */
48
49 #if 0
50 #define DEBUG_PRINT(...) fprintf(stderr, __VA_ARGS__)
51 #else
52 #define DEBUG_PRINT(...)
53 #endif
54
scdf_mark_edge_feasible(scdf_ctx * scdf,int from,int to)55 void scdf_mark_edge_feasible(scdf_ctx *scdf, int from, int to) {
56 uint32_t edge = scdf_edge(&scdf->ssa->cfg, from, to);
57
58 if (zend_bitset_in(scdf->feasible_edges, edge)) {
59 /* We already handled this edge */
60 return;
61 }
62
63 DEBUG_PRINT("Marking edge %d->%d feasible\n", from, to);
64 zend_bitset_incl(scdf->feasible_edges, edge);
65
66 if (!zend_bitset_in(scdf->executable_blocks, to)) {
67 if (!zend_bitset_in(scdf->block_worklist, to)) {
68 DEBUG_PRINT("Adding block %d to worklist\n", to);
69 }
70 zend_bitset_incl(scdf->block_worklist, to);
71 } else {
72 /* Block is already executable, only a new edge became feasible.
73 * Reevaluate phi nodes to account for changed source operands. */
74 zend_ssa_block *ssa_block = &scdf->ssa->blocks[to];
75 zend_ssa_phi *phi;
76 for (phi = ssa_block->phis; phi; phi = phi->next) {
77 zend_bitset_excl(scdf->phi_var_worklist, phi->ssa_var);
78 scdf->handlers.visit_phi(scdf, phi);
79 }
80 }
81 }
82
scdf_init(zend_optimizer_ctx * ctx,scdf_ctx * scdf,zend_op_array * op_array,zend_ssa * ssa)83 void scdf_init(zend_optimizer_ctx *ctx, scdf_ctx *scdf, zend_op_array *op_array, zend_ssa *ssa) {
84 scdf->op_array = op_array;
85 scdf->ssa = ssa;
86
87 scdf->instr_worklist_len = zend_bitset_len(op_array->last);
88 scdf->phi_var_worklist_len = zend_bitset_len(ssa->vars_count);
89 scdf->block_worklist_len = zend_bitset_len(ssa->cfg.blocks_count);
90
91 scdf->instr_worklist = zend_arena_calloc(&ctx->arena,
92 scdf->instr_worklist_len + scdf->phi_var_worklist_len + 2 * scdf->block_worklist_len + zend_bitset_len(ssa->cfg.edges_count),
93 sizeof(zend_ulong));
94
95 scdf->phi_var_worklist = scdf->instr_worklist + scdf->instr_worklist_len;
96 scdf->block_worklist = scdf->phi_var_worklist + scdf->phi_var_worklist_len;
97 scdf->executable_blocks = scdf->block_worklist + scdf->block_worklist_len;
98 scdf->feasible_edges = scdf->executable_blocks + scdf->block_worklist_len;
99
100 zend_bitset_incl(scdf->block_worklist, 0);
101 zend_bitset_incl(scdf->executable_blocks, 0);
102 }
103
scdf_solve(scdf_ctx * scdf,const char * name)104 void scdf_solve(scdf_ctx *scdf, const char *name) {
105 zend_ssa *ssa = scdf->ssa;
106 DEBUG_PRINT("Start SCDF solve (%s)\n", name);
107 while (!zend_bitset_empty(scdf->instr_worklist, scdf->instr_worklist_len)
108 || !zend_bitset_empty(scdf->phi_var_worklist, scdf->phi_var_worklist_len)
109 || !zend_bitset_empty(scdf->block_worklist, scdf->block_worklist_len)
110 ) {
111 int i;
112 while ((i = zend_bitset_pop_first(scdf->phi_var_worklist, scdf->phi_var_worklist_len)) >= 0) {
113 zend_ssa_phi *phi = ssa->vars[i].definition_phi;
114 ZEND_ASSERT(phi);
115 if (zend_bitset_in(scdf->executable_blocks, phi->block)) {
116 scdf->handlers.visit_phi(scdf, phi);
117 }
118 }
119
120 while ((i = zend_bitset_pop_first(scdf->instr_worklist, scdf->instr_worklist_len)) >= 0) {
121 int block_num = ssa->cfg.map[i];
122 if (zend_bitset_in(scdf->executable_blocks, block_num)) {
123 zend_basic_block *block = &ssa->cfg.blocks[block_num];
124 zend_op *opline = &scdf->op_array->opcodes[i];
125 zend_ssa_op *ssa_op = &ssa->ops[i];
126 if (opline->opcode == ZEND_OP_DATA) {
127 opline--;
128 ssa_op--;
129 }
130 scdf->handlers.visit_instr(scdf, opline, ssa_op);
131 if (i == block->start + block->len - 1) {
132 if (block->successors_count == 1) {
133 scdf_mark_edge_feasible(scdf, block_num, block->successors[0]);
134 } else if (block->successors_count > 1) {
135 scdf->handlers.mark_feasible_successors(scdf, block_num, block, opline, ssa_op);
136 }
137 }
138 }
139 }
140
141 while ((i = zend_bitset_pop_first(scdf->block_worklist, scdf->block_worklist_len)) >= 0) {
142 /* This block is now live. Interpret phis and instructions in it. */
143 zend_basic_block *block = &ssa->cfg.blocks[i];
144 zend_ssa_block *ssa_block = &ssa->blocks[i];
145
146 DEBUG_PRINT("Pop block %d from worklist\n", i);
147 zend_bitset_incl(scdf->executable_blocks, i);
148
149 {
150 zend_ssa_phi *phi;
151 for (phi = ssa_block->phis; phi; phi = phi->next) {
152 zend_bitset_excl(scdf->phi_var_worklist, phi->ssa_var);
153 scdf->handlers.visit_phi(scdf, phi);
154 }
155 }
156
157 if (block->len == 0) {
158 /* Zero length blocks don't have a last instruction that would normally do this */
159 scdf_mark_edge_feasible(scdf, i, block->successors[0]);
160 } else {
161 zend_op *opline;
162 int j, end = block->start + block->len;
163 for (j = block->start; j < end; j++) {
164 opline = &scdf->op_array->opcodes[j];
165 zend_bitset_excl(scdf->instr_worklist, j);
166 if (opline->opcode != ZEND_OP_DATA) {
167 scdf->handlers.visit_instr(scdf, opline, &ssa->ops[j]);
168 }
169 }
170 if (block->successors_count == 1) {
171 scdf_mark_edge_feasible(scdf, i, block->successors[0]);
172 } else if (block->successors_count > 1) {
173 if (opline->opcode == ZEND_OP_DATA) {
174 opline--;
175 j--;
176 }
177 scdf->handlers.mark_feasible_successors(scdf, i, block, opline, &ssa->ops[j-1]);
178 }
179 }
180 }
181 }
182 }
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. */
kept_alive_by_live_range(scdf_ctx * scdf,uint32_t block)187 static zend_bool kept_alive_by_live_range(scdf_ctx *scdf, uint32_t block) {
188 uint32_t i;
189 const zend_op_array *op_array = scdf->op_array;
190 const zend_cfg *cfg = &scdf->ssa->cfg;
191 for (i = 0; i < op_array->last_live_range; i++) {
192 zend_live_range *live_range = &op_array->live_range[i];
193 uint32_t start_block = cfg->map[live_range->start];
194 uint32_t end_block = cfg->map[live_range->end];
195
196 if (end_block == block && start_block != block
197 && zend_bitset_in(scdf->executable_blocks, start_block)) {
198 return 1;
199 }
200 }
201 return 0;
202 }
203
204 /* Removes unreachable blocks. This will remove both the instructions (and phis) in the
205 * blocks, as well as remove them from the successor / predecessor lists and mark them
206 * unreachable. Blocks already marked unreachable are not removed. */
scdf_remove_unreachable_blocks(scdf_ctx * scdf)207 int scdf_remove_unreachable_blocks(scdf_ctx *scdf) {
208 zend_ssa *ssa = scdf->ssa;
209 int i;
210 int removed_ops = 0;
211
212 for (i = 0; i < ssa->cfg.blocks_count; i++) {
213 if (!zend_bitset_in(scdf->executable_blocks, i)
214 && (ssa->cfg.blocks[i].flags & ZEND_BB_REACHABLE)
215 && !kept_alive_by_live_range(scdf, i)) {
216 removed_ops += ssa->cfg.blocks[i].len;
217 zend_ssa_remove_block(scdf->op_array, ssa, i);
218 }
219 }
220 return removed_ops;
221 }
222
