Line data Source code
1 : /* Support for simple predicate analysis.
2 :
3 : Copyright (C) 2021-2026 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 937 : predicate (bool empty_val) : m_preds (vNULL), m_cval (empty_val) { }
49 :
50 : /* Copy. */
51 151 : predicate (const predicate &rhs) : m_preds (vNULL) { *this = rhs; }
52 :
53 : ~predicate ();
54 :
55 : /* Assign. */
56 : predicate& operator= (const predicate &);
57 :
58 3619 : bool is_empty () const
59 : {
60 3324 : return m_preds.is_empty ();
61 : }
62 :
63 526 : bool is_true () const
64 : {
65 1159 : return is_empty () && m_cval;
66 : }
67 :
68 526 : bool is_false () const
69 : {
70 1051 : return is_empty () && !m_cval;
71 : }
72 :
73 526 : bool empty_val () const
74 : {
75 526 : return m_cval;
76 : }
77 :
78 459 : const pred_chain_union chain () const
79 : {
80 459 : 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 : bool drop_conjuncts_implied_by (const vec<pred_info> &);
95 :
96 : private:
97 :
98 : bool includes (const pred_chain &) const;
99 : void push_pred (const pred_info &);
100 :
101 : /* Normalization functions. */
102 : void normalize (pred_chain *, pred_info, tree_code, pred_chain *,
103 : hash_set<tree> *);
104 : void normalize (const pred_info &);
105 : void normalize (const pred_chain &);
106 :
107 : /* Simplification functions. */
108 : bool simplify_2 ();
109 : bool simplify_3 ();
110 : bool simplify_4 ();
111 :
112 : /* Representation of the predicate expression(s). The predicate is
113 : m_cval || m_preds[0] || ... */
114 : pred_chain_union m_preds;
115 : bool m_cval;
116 : };
117 :
118 : /* Represents a complex Boolean predicate expression. */
119 761 : class uninit_analysis
120 : {
121 : public:
122 : /* Base function object type used to determine whether an expression
123 : is of interest. */
124 : struct func_t
125 : {
126 : typedef unsigned phi_arg_set_t;
127 :
128 : /* Return a bitset of PHI arguments of interest. By default returns
129 : bitset with a bit set for each argument. Should be called in
130 : the overridden function first and, if nonzero, the result then
131 : refined as appropriate. */
132 : virtual phi_arg_set_t phi_arg_set (gphi *);
133 :
134 : /* Maximum number of PHI arguments supported by phi_arg_set(). */
135 : static constexpr unsigned max_phi_args =
136 : sizeof (phi_arg_set_t) * CHAR_BIT;
137 : };
138 :
139 : /* Construct with the specified EVAL object. */
140 761 : uninit_analysis (func_t &eval)
141 761 : : m_phi_def_preds (false), m_eval (eval) { }
142 :
143 : /* Copy. */
144 : uninit_analysis (const uninit_analysis &rhs) = delete;
145 :
146 : /* Assign. */
147 : uninit_analysis& operator= (const uninit_analysis&) = delete;
148 :
149 : /* Return true if the use by a statement in the basic block of
150 : a PHI operand is ruled out (i.e., guarded) by *THIS. */
151 : bool is_use_guarded (gimple *, basic_block, gphi *, unsigned);
152 :
153 : private:
154 : bool is_use_guarded (gimple *, basic_block, gphi *, unsigned,
155 : hash_set<gphi *> *);
156 : bool prune_phi_opnds (gphi *, unsigned, gphi *, tree, tree_code,
157 : hash_set<gphi *> *, bitmap *, unsigned &);
158 : bool overlap (gphi *, unsigned, hash_set<gphi *> *, const predicate &);
159 :
160 : void collect_phi_def_edges (gphi *, basic_block, vec<edge> *,
161 : hash_set<gimple *> *);
162 : bool init_from_phi_def (gphi *);
163 : bool init_use_preds (predicate &, basic_block, basic_block);
164 :
165 :
166 : /* Representation of the predicate expression(s). */
167 : predicate m_phi_def_preds;
168 : /* Callback to evaluate an operand. Return true if it's interesting. */
169 : func_t &m_eval;
170 : };
171 :
172 : /* Bit mask handling macros. */
173 : #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
174 : #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
175 : #define MASK_EMPTY(mask) (mask == 0)
176 :
177 : #endif // GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED
|
