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
