xref: /PHP-8.3/Zend/Optimizer/scdf.h (revision 49c1e6eb)
1 /*
2    +----------------------------------------------------------------------+
3    | Zend Engine, Call Graph                                              |
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 #ifndef _SCDF_H
20 #define _SCDF_H
21 
22 #include "zend_bitset.h"
23 
24 typedef struct _scdf_ctx {
25 	zend_op_array *op_array;
26 	zend_ssa *ssa;
27 	zend_bitset instr_worklist;
28 	/* Represent phi-instructions through the defining var */
29 	zend_bitset phi_var_worklist;
30 	zend_bitset block_worklist;
31 	zend_bitset executable_blocks;
32 	/* 1 bit per edge, see scdf_edge(cfg, from, to) */
33 	zend_bitset feasible_edges;
34 	uint32_t instr_worklist_len;
35 	uint32_t phi_var_worklist_len;
36 	uint32_t block_worklist_len;
37 
38 	struct {
39 		void (*visit_instr)(
40 			struct _scdf_ctx *scdf, zend_op *opline, zend_ssa_op *ssa_op);
41 		void (*visit_phi)(
42 			struct _scdf_ctx *scdf, zend_ssa_phi *phi);
43 		void (*mark_feasible_successors)(
44 			struct _scdf_ctx *scdf, int block_num, zend_basic_block *block,
45 			zend_op *opline, zend_ssa_op *ssa_op);
46 	} handlers;
47 } scdf_ctx;
48 
49 void scdf_init(zend_optimizer_ctx *ctx, scdf_ctx *scdf, zend_op_array *op_array, zend_ssa *ssa);
50 void scdf_solve(scdf_ctx *scdf, const char *name);
51 
52 uint32_t scdf_remove_unreachable_blocks(scdf_ctx *scdf);
53 
54 /* Add uses to worklist */
scdf_add_to_worklist(scdf_ctx * scdf,int var_num)55 static inline void scdf_add_to_worklist(scdf_ctx *scdf, int var_num) {
56 	const zend_ssa *ssa = scdf->ssa;
57 	const zend_ssa_var *var = &ssa->vars[var_num];
58 	int use;
59 	zend_ssa_phi *phi;
60 	FOREACH_USE(var, use) {
61 		zend_bitset_incl(scdf->instr_worklist, use);
62 	} FOREACH_USE_END();
63 	FOREACH_PHI_USE(var, phi) {
64 		zend_bitset_incl(scdf->phi_var_worklist, phi->ssa_var);
65 	} FOREACH_PHI_USE_END();
66 }
67 
68 /* This should usually not be necessary, however it's used for type narrowing. */
scdf_add_def_to_worklist(scdf_ctx * scdf,int var_num)69 static inline void scdf_add_def_to_worklist(scdf_ctx *scdf, int var_num) {
70 	const zend_ssa_var *var = &scdf->ssa->vars[var_num];
71 	if (var->definition >= 0) {
72 		zend_bitset_incl(scdf->instr_worklist, var->definition);
73 	} else if (var->definition_phi) {
74 		zend_bitset_incl(scdf->phi_var_worklist, var_num);
75 	}
76 }
77 
scdf_edge(const zend_cfg * cfg,int from,int to)78 static inline uint32_t scdf_edge(const zend_cfg *cfg, int from, int to) {
79 	const zend_basic_block *to_block = cfg->blocks + to;
80 	int i;
81 
82 	for (i = 0; i < to_block->predecessors_count; i++) {
83 		uint32_t edge = to_block->predecessor_offset + i;
84 
85 		if (cfg->predecessors[edge] == from) {
86 			return edge;
87 		}
88 	}
89 	ZEND_UNREACHABLE();
90 }
91 
scdf_is_edge_feasible(const scdf_ctx * scdf,int from,int to)92 static inline bool scdf_is_edge_feasible(const scdf_ctx *scdf, int from, int to) {
93 	uint32_t edge = scdf_edge(&scdf->ssa->cfg, from, to);
94 	return zend_bitset_in(scdf->feasible_edges, edge);
95 }
96 
97 void scdf_mark_edge_feasible(scdf_ctx *scdf, int from, int to);
98 
99 #endif
100