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