1/* IPA predicates.
2 Copyright (C) 2003-2023 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21/* Representation of inline parameters that do depend on context function is
22 inlined into (i.e. known constant values of function parameters.
23
24 Conditions that are interesting for function body are collected into CONDS
25 vector. They are of simple as kind of a mathematical transformation on
26 function parameter, T(function_param), in which the parameter occurs only
27 once, and other operands are IPA invariant. The conditions are then
28 referred by predicates. */
29
30
31/* A simplified representation of tree node, for unary, binary and ternary
32 operation. Computations on parameter are decomposed to a series of this
33 kind of structure. */
34struct GTY(()) expr_eval_op
35{
36 /* Result type of expression. */
37 tree type;
38 /* Constant operands in expression, there are at most two. */
39 tree val[2];
40 /* Index of parameter operand in expression. */
41 unsigned index : 2;
42 /* Operation code of expression. */
43 ENUM_BITFIELD(tree_code) code : 16;
44};
45
46typedef vec<expr_eval_op, va_gc> *expr_eval_ops;
47
48struct GTY(()) condition
49{
50 /* If agg_contents is set, this is the offset from which the used data was
51 loaded. */
52 HOST_WIDE_INT offset;
53 /* Type of the access reading the data (or the PARM_DECL SSA_NAME). */
54 tree type;
55 tree val;
56 int operand_num;
57 ENUM_BITFIELD(tree_code) code : 16;
58 /* Set if the used data were loaded from an aggregate parameter or from
59 data received by reference. */
60 unsigned agg_contents : 1;
61 /* If agg_contents is set, this differentiates between loads from data
62 passed by reference and by value. */
63 unsigned by_ref : 1;
64 /* A set of sequential operations on the parameter, which can be seen as
65 a mathematical function on the parameter. */
66 expr_eval_ops param_ops;
67};
68
69/* Information kept about parameter of call site. */
70struct inline_param_summary
71{
72 /* REG_BR_PROB_BASE based probability that parameter will change in between
73 two invocation of the calls.
74 I.e. loop invariant parameters
75 REG_BR_PROB_BASE/estimated_iterations and regular
76 parameters REG_BR_PROB_BASE.
77
78 Value 0 is reserved for compile time invariants. */
79 short change_prob;
80 unsigned points_to_local_or_readonly_memory : 1;
81 unsigned points_to_possible_sra_candidate : 1;
82 bool equal_to (const inline_param_summary &other) const
83 {
84 return change_prob == other.change_prob
85 && points_to_local_or_readonly_memory
86 == other.points_to_local_or_readonly_memory
87 && points_to_possible_sra_candidate
88 == other.points_to_possible_sra_candidate;
89 }
90 bool useless_p (void) const
91 {
92 return change_prob == REG_BR_PROB_BASE
93 && !points_to_local_or_readonly_memory
94 && !points_to_possible_sra_candidate;
95 }
96};
97
98typedef vec<condition, va_gc> *conditions;
99
100/* Predicates are used to represent function parameters (such as runtime)
101 which depend on a context function is called in.
102
103 Predicates are logical formulas in conjunctive-disjunctive form consisting
104 of clauses which are bitmaps specifying a set of condition that must
105 be true for a clause to be satisfied. Physically they are represented as
106 array of clauses terminated by 0.
107
108 In order to make predicate (possibly) true, all of its clauses must
109 be (possibly) true. To make clause (possibly) true, one of conditions
110 it mentions must be (possibly) true.
111
112 There are fixed bounds on number of clauses and conditions and all the
113 manipulation functions are conservative in positive direction. I.e. we
114 may lose precision by thinking that predicate may be true even when it
115 is not. */
116
117typedef uint32_t clause_t;
118class ipa_predicate
119{
120public:
121 enum predicate_conditions
122 {
123 false_condition = 0,
124 not_inlined_condition = 1,
125 first_dynamic_condition = 2
126 };
127
128 /* Maximal number of conditions predicate can refer to. This is limited
129 by using clause_t to be 32bit. */
130 static const int num_conditions = 32;
131
132 /* Special condition code we use to represent test that operand is compile
133 time constant. */
134 static const tree_code is_not_constant = ERROR_MARK;
135
136 /* Special condition code we use to represent test that operand is not changed
137 across invocation of the function. When operand IS_NOT_CONSTANT it is
138 always CHANGED, however i.e. loop invariants can be NOT_CHANGED given
139 percentage of executions even when they are not compile time constants. */
140 static const tree_code changed = IDENTIFIER_NODE;
141
142 /* Special condition code we use to check that the parameter is likely SRA
143 candidate. */
144 static const tree_code not_sra_candidate = TREE_LIST;
145
146
147 /* Initialize predicate either to true of false depending on P. */
148 inline ipa_predicate (bool p = true)
149 {
150 if (p)
151 /* True predicate. */
152 m_clause[0] = 0;
153 else
154 /* False predicate. */
155 set_to_cond (false_condition);
156 }
157
158 /* Sanity check that we do not mix pointers to predicates with predicates. */
159 inline ipa_predicate (ipa_predicate *)
160 {
161 gcc_unreachable ();
162 }
163
164 /* Return predicate testing condition I. */
165 static inline ipa_predicate predicate_testing_cond (int i)
166 {
167 ipa_predicate p;
168 p.set_to_cond (i + first_dynamic_condition);
169 return p;
170 }
171
172 /* Return predicate testing that function was not inlined. */
173 static ipa_predicate not_inlined (void)
174 {
175 ipa_predicate p;
176 p.set_to_cond (not_inlined_condition);
177 return p;
178 }
179
180 /* Compute logical and of ipa_predicates. */
181 ipa_predicate & operator &= (const ipa_predicate &);
182 inline ipa_predicate operator &(const ipa_predicate &p) const
183 {
184 ipa_predicate ret = *this;
185 ret &= p;
186 return ret;
187 }
188
189 /* Compute logical or of ipa_predicates. This is not operator because
190 extra parameter CONDITIONS is needed */
191 ipa_predicate or_with (conditions, const ipa_predicate &) const;
192
193 /* Return true if ipa_predicates are known to be equal. */
194 inline bool operator==(const ipa_predicate &p2) const
195 {
196 int i;
197 for (i = 0; m_clause[i]; i++)
198 {
199 gcc_checking_assert (i < max_clauses);
200 gcc_checking_assert (m_clause[i] > m_clause[i + 1]);
201 gcc_checking_assert (!p2.m_clause[i]
202 || p2.m_clause[i] > p2.m_clause[i + 1]);
203 if (m_clause[i] != p2.m_clause[i])
204 return false;
205 }
206 return !p2.m_clause[i];
207 }
208
209 /* Return true if predicates are known to be true or false depending
210 on COND. */
211 inline bool operator==(const bool cond) const
212 {
213 if (cond)
214 return !m_clause[0];
215 if (m_clause[0] == (1 << false_condition))
216 {
217 gcc_checking_assert (!m_clause[1]
218 && m_clause[0] == 1
219 << false_condition);
220 return true;
221 }
222 return false;
223 }
224
225 inline bool operator!=(const ipa_predicate &p2) const
226 {
227 return !(*this == p2);
228 }
229
230 inline bool operator!=(const bool cond) const
231 {
232 return !(*this == cond);
233 }
234
235 /* Evaluate if predicate is known to be false given the clause of possible
236 truths. */
237 bool evaluate (clause_t) const;
238
239 /* Estimate probability that predicate will be true in a given context. */
240 int probability (conditions, clause_t, vec<inline_param_summary>) const;
241
242 /* Dump predicate to F. Output newline if nl. */
243 void dump (FILE *f, conditions, bool nl=true) const;
244 void DEBUG_FUNCTION debug (conditions) const;
245
246 /* Return ipa_predicate equal to THIS after duplication. */
247 ipa_predicate remap_after_duplication (clause_t);
248
249 /* Return ipa_predicate equal to THIS after inlining. */
250 ipa_predicate remap_after_inlining (class ipa_fn_summary *,
251 ipa_node_params *params_summary,
252 ipa_fn_summary *,
253 const vec<int> &,
254 const vec<HOST_WIDE_INT> &,
255 clause_t, const ipa_predicate &);
256
257 void stream_in (lto_input_block *);
258 void stream_out (output_block *);
259
260private:
261 static const int max_clauses = 8;
262 clause_t m_clause[max_clauses + 1];
263
264 /* Initialize predicate to one testing single condition number COND. */
265 inline void set_to_cond (int cond)
266 {
267 m_clause[0] = 1 << cond;
268 m_clause[1] = 0;
269 }
270
271 void add_clause (conditions conditions, clause_t);
272};
273
274void dump_condition (FILE *f, conditions conditions, int cond);
275ipa_predicate add_condition (ipa_fn_summary *summary,
276 ipa_node_params *params_summary,
277 int operand_num,
278 tree type, struct agg_position_info *aggpos,
279 enum tree_code code, tree val,
280 expr_eval_ops param_ops = NULL);
281

source code of gcc/ipa-predicate.h