1 /* IPA predicates.
2 Copyright (C) 2003-2023 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 bool equal_to (const inline_param_summary &other) const
82 {
83 return change_prob == other.change_prob
84 && points_to_local_or_readonly_memory
85 == other.points_to_local_or_readonly_memory;
86 }
87 bool useless_p (void) const
88 {
89 return change_prob == REG_BR_PROB_BASE
90 && !points_to_local_or_readonly_memory;
91 }
92 };
93
94 typedef vec<condition, va_gc> *conditions;
95
96 /* Predicates are used to represent function parameters (such as runtime)
97 which depend on a context function is called in.
98
99 Predicates are logical formulas in conjunctive-disjunctive form consisting
100 of clauses which are bitmaps specifying a set of condition that must
101 be true for a clause to be satisfied. Physically they are represented as
102 array of clauses terminated by 0.
103
104 In order to make predicate (possibly) true, all of its clauses must
105 be (possibly) true. To make clause (possibly) true, one of conditions
106 it mentions must be (possibly) true.
107
108 There are fixed bounds on number of clauses and conditions and all the
109 manipulation functions are conservative in positive direction. I.e. we
110 may lose precision by thinking that predicate may be true even when it
111 is not. */
112
113 typedef uint32_t clause_t;
114 class ipa_predicate
115 {
116 public:
117 enum predicate_conditions
118 {
119 false_condition = 0,
120 not_inlined_condition = 1,
121 first_dynamic_condition = 2
122 };
123
124 /* Maximal number of conditions predicate can refer to. This is limited
125 by using clause_t to be 32bit. */
126 static const int num_conditions = 32;
127
128 /* Special condition code we use to represent test that operand is compile
129 time constant. */
130 static const tree_code is_not_constant = ERROR_MARK;
131
132 /* Special condition code we use to represent test that operand is not changed
133 across invocation of the function. When operand IS_NOT_CONSTANT it is
134 always CHANGED, however i.e. loop invariants can be NOT_CHANGED given
135 percentage of executions even when they are not compile time constants. */
136 static const tree_code changed = IDENTIFIER_NODE;
137
138
139
140 /* Initialize predicate either to true of false depending on P. */
141 inline ipa_predicate (bool p = true)
142 {
143 if (p)
144 /* True predicate. */
145 m_clause[0] = 0;
146 else
147 /* False predicate. */
148 set_to_cond (false_condition);
149 }
150
151 /* Sanity check that we do not mix pointers to predicates with predicates. */
152 inline ipa_predicate (ipa_predicate *)
153 {
154 gcc_unreachable ();
155 }
156
157 /* Return predicate testing condition I. */
158 static inline ipa_predicate predicate_testing_cond (int i)
159 {
160 ipa_predicate p;
161 p.set_to_cond (i + first_dynamic_condition);
162 return p;
163 }
164
165 /* Return predicate testing that function was not inlined. */
166 static ipa_predicate not_inlined (void)
167 {
168 ipa_predicate p;
169 p.set_to_cond (not_inlined_condition);
170 return p;
171 }
172
173 /* Compute logical and of ipa_predicates. */
174 ipa_predicate & operator &= (const ipa_predicate &);
175 inline ipa_predicate operator &(const ipa_predicate &p) const
176 {
177 ipa_predicate ret = *this;
178 ret &= p;
179 return ret;
180 }
181
182 /* Compute logical or of ipa_predicates. This is not operator because
183 extra parameter CONDITIONS is needed */
184 ipa_predicate or_with (conditions, const ipa_predicate &) const;
185
186 /* Return true if ipa_predicates are known to be equal. */
187 inline bool operator==(const ipa_predicate &p2) const
188 {
189 int i;
190 for (i = 0; m_clause[i]; i++)
191 {
192 gcc_checking_assert (i < max_clauses);
193 gcc_checking_assert (m_clause[i] > m_clause[i + 1]);
194 gcc_checking_assert (!p2.m_clause[i]
195 || p2.m_clause[i] > p2.m_clause[i + 1]);
196 if (m_clause[i] != p2.m_clause[i])
197 return false;
198 }
199 return !p2.m_clause[i];
200 }
201
202 /* Return true if predicates are known to be true or false depending
203 on COND. */
204 inline bool operator==(const bool cond) const
205 {
206 if (cond)
207 return !m_clause[0];
208 if (m_clause[0] == (1 << false_condition))
209 {
210 gcc_checking_assert (!m_clause[1]
211 && m_clause[0] == 1
212 << false_condition);
213 return true;
214 }
215 return false;
216 }
217
218 inline bool operator!=(const ipa_predicate &p2) const
219 {
220 return !(*this == p2);
221 }
222
223 inline bool operator!=(const bool cond) const
224 {
225 return !(*this == cond);
226 }
227
228 /* Evaluate if predicate is known to be false given the clause of possible
229 truths. */
230 bool evaluate (clause_t) const;
231
232 /* Estimate probability that predicate will be true in a given context. */
233 int probability (conditions, clause_t, vec<inline_param_summary>) const;
234
235 /* Dump predicate to F. Output newline if nl. */
236 void dump (FILE *f, conditions, bool nl=true) const;
237 void DEBUG_FUNCTION debug (conditions) const;
238
239 /* Return ipa_predicate equal to THIS after duplication. */
240 ipa_predicate remap_after_duplication (clause_t);
241
242 /* Return ipa_predicate equal to THIS after inlining. */
243 ipa_predicate remap_after_inlining (class ipa_fn_summary *,
244 ipa_node_params *params_summary,
245 ipa_fn_summary *,
246 const vec<int> &,
247 const vec<HOST_WIDE_INT> &,
248 clause_t, const ipa_predicate &);
249
250 void stream_in (lto_input_block *);
251 void stream_out (output_block *);
252
253 private:
254 static const int max_clauses = 8;
255 clause_t m_clause[max_clauses + 1];
256
257 /* Initialize predicate to one testing single condition number COND. */
258 inline void set_to_cond (int cond)
259 {
260 m_clause[0] = 1 << cond;
261 m_clause[1] = 0;
262 }
263
264 void add_clause (conditions conditions, clause_t);
265 };
266
267 void dump_condition (FILE *f, conditions conditions, int cond);
268 ipa_predicate add_condition (ipa_fn_summary *summary,
269 ipa_node_params *params_summary,
270 int operand_num,
271 tree type, struct agg_position_info *aggpos,
272 enum tree_code code, tree val,
273 expr_eval_ops param_ops = NULL);