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 : predicate (const predicate &rhs) : m_preds (vNULL) { *this = rhs; }
52 :
53 : ~predicate ();
54 :
55 : /* Assign. */
56 : predicate& operator= (const predicate &);
57 :
58 3603 : bool is_empty () const
59 : {
60 3314 : return m_preds.is_empty ();
61 : }
62 :
63 522 : bool is_true () const
64 : {
65 1151 : return is_empty () && m_cval;
66 : }
67 :
68 522 : bool is_false () const
69 : {
70 1043 : return is_empty () && !m_cval;
71 : }
72 :
73 522 : bool empty_val () const
74 : {
75 522 : return m_cval;
76 : }
77 :
78 457 : const pred_chain_union chain () const
79 : {
80 457 : 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 761 : 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 761 : uninit_analysis (func_t &eval)
139 761 : : 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 *, unsigned &);
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
|
