Branch data Line data Source code
1 : : /* IPA predicates.
2 : : Copyright (C) 2003-2025 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 : 3318383 : bool equal_to (const inline_param_summary &other) const
83 : : {
84 : 3318383 : return change_prob == other.change_prob
85 : 3304778 : && points_to_local_or_readonly_memory
86 : 3304778 : == other.points_to_local_or_readonly_memory
87 : 3318383 : && points_to_possible_sra_candidate
88 : 3276542 : == other.points_to_possible_sra_candidate;
89 : : }
90 : 11933198 : bool useless_p (void) const
91 : : {
92 : 11933198 : return change_prob == REG_BR_PROB_BASE
93 : : && !points_to_local_or_readonly_memory
94 : 11933198 : && !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 : 1035159489 : inline ipa_predicate (bool p = true)
149 : 959100817 : {
150 : 1035159489 : if (p)
151 : : /* True predicate. */
152 : 859761728 : m_clause[0] = 0;
153 : : else
154 : : /* False predicate. */
155 : 121130540 : 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 : 18869622 : static inline ipa_predicate predicate_testing_cond (int i)
166 : : {
167 : 18869622 : ipa_predicate p;
168 : 18869622 : p.set_to_cond (i + first_dynamic_condition);
169 : 18869622 : return p;
170 : : }
171 : :
172 : : /* Return predicate testing that function was not inlined. */
173 : 20593343 : static ipa_predicate not_inlined (void)
174 : : {
175 : 20593343 : ipa_predicate p;
176 : 20593343 : p.set_to_cond (not_inlined_condition);
177 : 20593343 : return p;
178 : : }
179 : :
180 : : /* Compute logical and of ipa_predicates. */
181 : : ipa_predicate & operator &= (const ipa_predicate &);
182 : 341522126 : inline ipa_predicate operator &(const ipa_predicate &p) const
183 : : {
184 : 341522126 : ipa_predicate ret = *this;
185 : 327673916 : ret &= p;
186 : 327673916 : 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 : 713446789 : inline bool operator==(const ipa_predicate &p2) const
195 : : {
196 : 713446789 : int i;
197 : 853975961 : for (i = 0; m_clause[i]; i++)
198 : : {
199 : 494933325 : gcc_checking_assert (i < max_clauses);
200 : 494933325 : gcc_checking_assert (m_clause[i] > m_clause[i + 1]);
201 : 494933325 : gcc_checking_assert (!p2.m_clause[i]
202 : : || p2.m_clause[i] > p2.m_clause[i + 1]);
203 : 494933325 : if (m_clause[i] != p2.m_clause[i])
204 : : return false;
205 : : }
206 : 359042636 : return !p2.m_clause[i];
207 : : }
208 : :
209 : : /* Return true if predicates are known to be true or false depending
210 : : on COND. */
211 : 2282140947 : inline bool operator==(const bool cond) const
212 : : {
213 : 2282140947 : if (cond)
214 : 1024022332 : return !m_clause[0];
215 : 1258118615 : if (m_clause[0] == (1 << false_condition))
216 : : {
217 : 146688688 : gcc_checking_assert (!m_clause[1]
218 : : && m_clause[0] == 1
219 : : << false_condition);
220 : : return true;
221 : : }
222 : : return false;
223 : : }
224 : :
225 : 76793279 : inline bool operator!=(const ipa_predicate &p2) const
226 : : {
227 : 76793279 : return !(*this == p2);
228 : : }
229 : :
230 : 266562458 : inline bool operator!=(const bool cond) const
231 : : {
232 : 266562458 : 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 : 160593505 : inline void set_to_cond (int cond)
266 : : {
267 : 160593505 : m_clause[0] = 1 << cond;
268 : 160519474 : m_clause[1] = 0;
269 : 74031 : }
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);
|
