GCC Middle and Back End API Reference
ipa-predicate.h
Go to the documentation of this file.
1/* IPA predicates.
2 Copyright (C) 2003-2024 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. */
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
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). */
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. */
67};
68
69/* Information kept about parameter of call site. */
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. */
96};
97
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;
119{
120public:
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. */
156 }
157
158 /* Sanity check that we do not mix pointers to predicates with predicates. */
160 {
162 }
163
164 /* Return predicate testing condition I. */
166 {
169 return p;
170 }
171
172 /* Return predicate testing that function was not inlined. */
174 {
177 return p;
178 }
179
180 /* Compute logical and of ipa_predicates. */
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 */
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 {
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 {
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. */
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. */
248
249 /* Return ipa_predicate equal to THIS after inlining. */
251 ipa_node_params *params_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;
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
272};
273
274void dump_condition (FILE *f, conditions conditions, int cond);
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);
Definition ipa-fnsummary.h:122
Definition ipa-prop.h:618
Definition ipa-predicate.h:119
ipa_predicate & operator&=(const ipa_predicate &)
Definition ipa-predicate.cc:177
static const int max_clauses
Definition ipa-predicate.h:261
bool operator==(const bool cond) const
Definition ipa-predicate.h:211
void dump(FILE *f, conditions, bool nl=true) const
Definition ipa-predicate.cc:459
void stream_in(lto_input_block *)
Definition ipa-predicate.cc:600
void add_clause(conditions conditions, clause_t)
Definition ipa-predicate.cc:74
void stream_out(output_block *)
Definition ipa-predicate.cc:621
bool evaluate(clause_t) const
Definition ipa-predicate.cc:236
static ipa_predicate not_inlined(void)
Definition ipa-predicate.h:173
bool operator!=(const ipa_predicate &p2) const
Definition ipa-predicate.h:225
clause_t m_clause[max_clauses+1]
Definition ipa-predicate.h:262
static const tree_code not_sra_candidate
Definition ipa-predicate.h:144
bool operator==(const ipa_predicate &p2) const
Definition ipa-predicate.h:194
ipa_predicate(bool p=true)
Definition ipa-predicate.h:148
ipa_predicate or_with(conditions, const ipa_predicate &) const
Definition ipa-predicate.cc:210
ipa_predicate remap_after_duplication(clause_t)
Definition ipa-predicate.cc:488
int probability(conditions, clause_t, vec< inline_param_summary >) const
Definition ipa-predicate.cc:260
predicate_conditions
Definition ipa-predicate.h:122
@ first_dynamic_condition
Definition ipa-predicate.h:125
@ false_condition
Definition ipa-predicate.h:123
@ not_inlined_condition
Definition ipa-predicate.h:124
static ipa_predicate predicate_testing_cond(int i)
Definition ipa-predicate.h:165
static const tree_code changed
Definition ipa-predicate.h:140
static const int num_conditions
Definition ipa-predicate.h:130
void set_to_cond(int cond)
Definition ipa-predicate.h:265
static const tree_code is_not_constant
Definition ipa-predicate.h:134
bool operator!=(const bool cond) const
Definition ipa-predicate.h:230
ipa_predicate remap_after_inlining(class ipa_fn_summary *, ipa_node_params *params_summary, ipa_fn_summary *, const vec< int > &, const vec< HOST_WIDE_INT > &, clause_t, const ipa_predicate &)
Definition ipa-predicate.cc:515
ipa_predicate operator&(const ipa_predicate &p) const
Definition ipa-predicate.h:182
ipa_predicate(ipa_predicate *)
Definition ipa-predicate.h:159
Definition lto-streamer.h:338
bool debug
Definition collect-utils.cc:34
#define GTY(x)
Definition coretypes.h:41
union tree_node * tree
Definition coretypes.h:97
tree_code
Definition genmatch.cc:992
uint32_t clause_t
Definition ipa-predicate.h:117
vec< expr_eval_op, va_gc > * expr_eval_ops
Definition ipa-predicate.h:46
ipa_predicate add_condition(ipa_fn_summary *summary, ipa_node_params *params_summary, int operand_num, tree type, struct agg_position_info *aggpos, enum tree_code code, tree val, expr_eval_ops param_ops=NULL)
Definition ipa-predicate.cc:640
void dump_condition(FILE *f, conditions conditions, int cond)
Definition ipa-predicate.cc:321
vec< condition, va_gc > * conditions
Definition ipa-predicate.h:98
i
Definition poly-int.h:776
#define REG_BR_PROB_BASE
Definition profile-count.h:73
Definition ipa-fnsummary.h:66
Definition ipa-predicate.h:49
tree val
Definition ipa-predicate.h:55
enum tree_code code
Definition ipa-predicate.h:57
expr_eval_ops param_ops
Definition ipa-predicate.h:66
int operand_num
Definition ipa-predicate.h:56
unsigned agg_contents
Definition ipa-predicate.h:60
tree type
Definition ipa-predicate.h:54
unsigned by_ref
Definition ipa-predicate.h:63
HOST_WIDE_INT offset
Definition ipa-predicate.h:52
Definition ipa-predicate.h:35
enum tree_code code
Definition ipa-predicate.h:43
tree val[2]
Definition ipa-predicate.h:39
tree type
Definition ipa-predicate.h:37
unsigned index
Definition ipa-predicate.h:41
Definition ipa-predicate.h:71
unsigned points_to_possible_sra_candidate
Definition ipa-predicate.h:81
bool equal_to(const inline_param_summary &other) const
Definition ipa-predicate.h:82
bool useless_p(void) const
Definition ipa-predicate.h:90
unsigned points_to_local_or_readonly_memory
Definition ipa-predicate.h:80
short change_prob
Definition ipa-predicate.h:79
Definition lto-streamer.h:709
Definition gengtype.h:252
Definition vec.h:450
#define NULL
Definition system.h:50
#define gcc_unreachable()
Definition system.h:841
#define DEBUG_FUNCTION
Definition system.h:1236
#define gcc_checking_assert(EXPR)
Definition system.h:821