xref: /PHP-7.2/ext/opcache/Optimizer/scdf.c (revision 7a7ec01a)
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