1 | /* Support for simple predicate analysis. |
2 | |
3 | Copyright (C) 2021-2023 Free Software Foundation, Inc. |
4 | Contributed by Martin Sebor <msebor@redhat.com> |
5 | |
6 | This file is part of GCC. |
7 | |
8 | GCC is free software; you can redistribute it and/or modify |
9 | it under the terms of the GNU General Public License as published by |
10 | the Free Software Foundation; either version 3, or (at your option) |
11 | any later version. |
12 | |
13 | GCC is distributed in the hope that it will be useful, |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
16 | GNU General Public License for more details. |
17 | |
18 | You should have received a copy of the GNU General Public License |
19 | along with GCC; see the file COPYING3. If not see |
20 | <http://www.gnu.org/licenses/>. */ |
21 | |
22 | #ifndef GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED |
23 | #define GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED |
24 | |
25 | |
26 | /* Represents a simple Boolean predicate. */ |
27 | struct pred_info |
28 | { |
29 | tree pred_lhs; |
30 | tree pred_rhs; |
31 | enum tree_code cond_code; |
32 | bool invert; |
33 | }; |
34 | |
35 | /* The type to represent a sequence of predicates grouped |
36 | with .AND. operation. */ |
37 | typedef vec<pred_info, va_heap, vl_ptr> pred_chain; |
38 | |
39 | /* The type to represent a sequence of pred_chains grouped |
40 | with .OR. operation. */ |
41 | typedef vec<pred_chain, va_heap, vl_ptr> pred_chain_union; |
42 | |
43 | /* Represents a complex Boolean predicate expression. */ |
44 | class predicate |
45 | { |
46 | public: |
47 | /* Construct with the specified EVAL object. */ |
48 | predicate (bool empty_val) : m_preds (vNULL), m_cval (empty_val) { } |
49 | |
50 | /* Copy. */ |
51 | predicate (const predicate &rhs) : m_preds (vNULL) { *this = rhs; } |
52 | |
53 | ~predicate (); |
54 | |
55 | /* Assign. */ |
56 | predicate& operator= (const predicate &); |
57 | |
58 | bool is_empty () const |
59 | { |
60 | return m_preds.is_empty (); |
61 | } |
62 | |
63 | bool is_true () const |
64 | { |
65 | return is_empty () && m_cval; |
66 | } |
67 | |
68 | bool is_false () const |
69 | { |
70 | return is_empty () && !m_cval; |
71 | } |
72 | |
73 | bool empty_val () const |
74 | { |
75 | return m_cval; |
76 | } |
77 | |
78 | const pred_chain_union chain () const |
79 | { |
80 | return m_preds; |
81 | } |
82 | |
83 | void init_from_control_deps (const vec<edge> *, unsigned, bool); |
84 | |
85 | void dump (FILE *) const; |
86 | void dump (FILE *, gimple *, const char *) const; |
87 | void debug () const; |
88 | |
89 | void normalize (gimple * = NULL, bool = false); |
90 | void simplify (gimple * = NULL, bool = false); |
91 | |
92 | bool superset_of (const predicate &) const; |
93 | |
94 | private: |
95 | |
96 | bool includes (const pred_chain &) const; |
97 | void push_pred (const pred_info &); |
98 | |
99 | /* Normalization functions. */ |
100 | void normalize (pred_chain *, pred_info, tree_code, pred_chain *, |
101 | hash_set<tree> *); |
102 | void normalize (const pred_info &); |
103 | void normalize (const pred_chain &); |
104 | |
105 | /* Simplification functions. */ |
106 | bool simplify_2 (); |
107 | bool simplify_3 (); |
108 | bool simplify_4 (); |
109 | |
110 | /* Representation of the predicate expression(s). The predicate is |
111 | m_cval || m_preds[0] || ... */ |
112 | pred_chain_union m_preds; |
113 | bool m_cval; |
114 | }; |
115 | |
116 | /* Represents a complex Boolean predicate expression. */ |
117 | class uninit_analysis |
118 | { |
119 | public: |
120 | /* Base function object type used to determine whether an expression |
121 | is of interest. */ |
122 | struct func_t |
123 | { |
124 | typedef unsigned phi_arg_set_t; |
125 | |
126 | /* Return a bitset of PHI arguments of interest. By default returns |
127 | bitset with a bit set for each argument. Should be called in |
128 | the overriden function first and, if nonzero, the result then |
129 | refined as appropriate. */ |
130 | virtual phi_arg_set_t phi_arg_set (gphi *); |
131 | |
132 | /* Maximum number of PHI arguments supported by phi_arg_set(). */ |
133 | static constexpr unsigned max_phi_args = |
134 | sizeof (phi_arg_set_t) * CHAR_BIT; |
135 | }; |
136 | |
137 | /* Construct with the specified EVAL object. */ |
138 | uninit_analysis (func_t &eval) |
139 | : m_phi_def_preds (false), m_eval (eval) { } |
140 | |
141 | /* Copy. */ |
142 | uninit_analysis (const uninit_analysis &rhs) = delete; |
143 | |
144 | /* Assign. */ |
145 | uninit_analysis& operator= (const uninit_analysis&) = delete; |
146 | |
147 | /* Return true if the use by a statement in the basic block of |
148 | a PHI operand is ruled out (i.e., guarded) by *THIS. */ |
149 | bool is_use_guarded (gimple *, basic_block, gphi *, unsigned); |
150 | |
151 | private: |
152 | bool is_use_guarded (gimple *, basic_block, gphi *, unsigned, |
153 | hash_set<gphi *> *); |
154 | bool prune_phi_opnds (gphi *, unsigned, gphi *, tree, tree_code, |
155 | hash_set<gphi *> *, bitmap *); |
156 | bool overlap (gphi *, unsigned, hash_set<gphi *> *, const predicate &); |
157 | |
158 | void collect_phi_def_edges (gphi *, basic_block, vec<edge> *, |
159 | hash_set<gimple *> *); |
160 | bool init_from_phi_def (gphi *); |
161 | bool init_use_preds (predicate &, basic_block, basic_block); |
162 | |
163 | |
164 | /* Representation of the predicate expression(s). */ |
165 | predicate m_phi_def_preds; |
166 | /* Callback to evaluate an operand. Return true if it's interesting. */ |
167 | func_t &m_eval; |
168 | }; |
169 | |
170 | /* Bit mask handling macros. */ |
171 | #define MASK_SET_BIT(mask, pos) mask |= (1 << pos) |
172 | #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos)) |
173 | #define MASK_EMPTY(mask) (mask == 0) |
174 | |
175 | #endif // GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED |
176 | |