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