Line data Source code
1 : /* IPA predicates.
2 : Copyright (C) 2003-2026 Free Software Foundation, Inc.
3 : Contributed by Jan Hubicka
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it under
8 : the terms of the GNU General Public License as published by the Free
9 : Software Foundation; either version 3, or (at your option) any later
10 : version.
11 :
12 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along 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. */
34 : struct 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 :
46 : typedef vec<expr_eval_op, va_gc> *expr_eval_ops;
47 :
48 : struct 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. */
70 : struct 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 4083462 : bool equal_to (const inline_param_summary &other) const
83 : {
84 4083462 : return change_prob == other.change_prob
85 4067108 : && points_to_local_or_readonly_memory
86 4067108 : == other.points_to_local_or_readonly_memory
87 4083462 : && points_to_possible_sra_candidate
88 4057562 : == other.points_to_possible_sra_candidate;
89 : }
90 14339908 : bool useless_p (void) const
91 : {
92 14339908 : return change_prob == REG_BR_PROB_BASE
93 5267664 : && !points_to_local_or_readonly_memory
94 19362285 : && !points_to_possible_sra_candidate;
95 : }
96 : };
97 :
98 : typedef 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 :
117 : typedef uint32_t clause_t;
118 : class ipa_predicate
119 : {
120 : public:
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 1109430710 : inline ipa_predicate (bool p = true)
149 1026624627 : {
150 1109430710 : if (p)
151 : /* True predicate. */
152 916021248 : m_clause[0] = 0;
153 : else
154 : /* False predicate. */
155 132855134 : 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 21385968 : static inline ipa_predicate predicate_testing_cond (int i)
166 : {
167 21385968 : ipa_predicate p;
168 21385968 : p.set_to_cond (i + first_dynamic_condition);
169 21385968 : return p;
170 : }
171 :
172 : /* Return predicate testing that function was not inlined. */
173 21894202 : static ipa_predicate not_inlined (void)
174 : {
175 21894202 : ipa_predicate p;
176 21894202 : p.set_to_cond (not_inlined_condition);
177 7126596 : return p;
178 : }
179 :
180 : /* Compute logical and of ipa_predicates. */
181 : ipa_predicate & operator &= (const ipa_predicate &);
182 357862908 : inline ipa_predicate operator &(const ipa_predicate &p) const
183 : {
184 357862908 : ipa_predicate ret = *this;
185 343095302 : ret &= p;
186 343095302 : 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 756398005 : inline bool operator==(const ipa_predicate &p2) const
195 : {
196 756398005 : int i;
197 908193514 : for (i = 0; m_clause[i]; i++)
198 : {
199 531157439 : gcc_checking_assert (i < max_clauses);
200 531157439 : gcc_checking_assert (m_clause[i] > m_clause[i + 1]);
201 531157439 : gcc_checking_assert (!p2.m_clause[i]
202 : || p2.m_clause[i] > p2.m_clause[i + 1]);
203 531157439 : if (m_clause[i] != p2.m_clause[i])
204 : return false;
205 : }
206 377036075 : return !p2.m_clause[i];
207 : }
208 :
209 : /* Return true if predicates are known to be true or false depending
210 : on COND. */
211 2485726428 : inline bool operator==(const bool cond) const
212 : {
213 2485726428 : if (cond)
214 1133658737 : return !m_clause[0];
215 1352067691 : if (m_clause[0] == (1 << false_condition))
216 : {
217 162596552 : gcc_checking_assert (!m_clause[1]
218 : && m_clause[0] == 1
219 : << false_condition);
220 : return true;
221 : }
222 : return false;
223 : }
224 :
225 80466517 : inline bool operator!=(const ipa_predicate &p2) const
226 : {
227 80466517 : return !(*this == p2);
228 : }
229 :
230 282252222 : inline bool operator!=(const bool cond) const
231 : {
232 282252222 : 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 :
260 : private:
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 169008708 : inline void set_to_cond (int cond)
266 : {
267 169008708 : m_clause[0] = 1 << cond;
268 168920365 : m_clause[1] = 0;
269 88343 : }
270 :
271 : void add_clause (conditions conditions, clause_t);
272 : };
273 :
274 : void dump_condition (FILE *f, conditions conditions, int cond);
275 : ipa_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);
|
