Branch data Line data Source code
1 : : /* Support for simple predicate analysis.
2 : :
3 : : Copyright (C) 2021-2024 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 : 876 : 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 : 3213 : bool is_empty () const
59 : : {
60 : 2932 : return m_preds.is_empty ();
61 : : }
62 : :
63 : 475 : bool is_true () const
64 : : {
65 : 1055 : return is_empty () && m_cval;
66 : : }
67 : :
68 : 475 : bool is_false () const
69 : : {
70 : 949 : return is_empty () && !m_cval;
71 : : }
72 : :
73 : 475 : bool empty_val () const
74 : : {
75 : 475 : return m_cval;
76 : : }
77 : :
78 : 400 : const pred_chain_union chain () const
79 : : {
80 : 400 : 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 : 727 : 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 : 727 : uninit_analysis (func_t &eval)
139 : 727 : : 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
|
