]>
Commit | Line | Data |
---|---|---|
94c12ffa MS |
1 | /* Support for simple predicate analysis. |
2 | ||
aeee4812 | 3 | Copyright (C) 2021-2023 Free Software Foundation, Inc. |
94c12ffa MS |
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 | ||
94c12ffa MS |
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: | |
94c12ffa | 47 | /* Construct with the specified EVAL object. */ |
abf05583 | 48 | predicate (bool empty_val) : m_preds (vNULL), m_cval (empty_val) { } |
94c12ffa MS |
49 | |
50 | /* Copy. */ | |
cd1216d5 | 51 | predicate (const predicate &rhs) : m_preds (vNULL) { *this = rhs; } |
94c12ffa MS |
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 | ||
abf05583 RB |
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 | ||
94c12ffa MS |
78 | const pred_chain_union chain () const |
79 | { | |
80 | return m_preds; | |
81 | } | |
82 | ||
40f34788 | 83 | void init_from_control_deps (const vec<edge> *, unsigned, bool); |
94c12ffa | 84 | |
5642197c RB |
85 | void dump (FILE *) const; |
86 | void dump (FILE *, gimple *, const char *) const; | |
87 | void debug () const; | |
94c12ffa MS |
88 | |
89 | void normalize (gimple * = NULL, bool = false); | |
90 | void simplify (gimple * = NULL, bool = false); | |
91 | ||
94c12ffa | 92 | bool superset_of (const predicate &) const; |
94c12ffa | 93 | |
cd1216d5 | 94 | private: |
94c12ffa | 95 | |
cd1216d5 | 96 | bool includes (const pred_chain &) const; |
94c12ffa MS |
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> *); | |
94c12ffa MS |
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 | ||
abf05583 RB |
110 | /* Representation of the predicate expression(s). The predicate is |
111 | m_cval || m_preds[0] || ... */ | |
94c12ffa | 112 | pred_chain_union m_preds; |
abf05583 | 113 | bool m_cval; |
cd1216d5 RB |
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 | ||
cd1216d5 RB |
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) | |
abf05583 | 139 | : m_phi_def_preds (false), m_eval (eval) { } |
cd1216d5 RB |
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 &); | |
cd1216d5 RB |
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; | |
94c12ffa MS |
166 | /* Callback to evaluate an operand. Return true if it's interesting. */ |
167 | func_t &m_eval; | |
94c12ffa MS |
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 |