Daily bump.
[official-gcc.git] / gcc / ipa-predicate.h
blobac52b54aa368ac1959896c49d9c96feb718512d5
1 /* IPA predicates.
2 Copyright (C) 2003-2021 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
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.
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.
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/>. */
21 /* Representation of inline parameters that do depend on context function is
22 inlined into (i.e. known constant values of function parameters.
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. */
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
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;
46 typedef vec<expr_eval_op, va_gc> *expr_eval_ops;
48 struct GTY(()) condition
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;
69 /* Information kept about parameter of call site. */
70 struct inline_param_summary
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.
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
83 return change_prob == other.change_prob
84 && points_to_local_or_readonly_memory
85 == other.points_to_local_or_readonly_memory;
87 bool useless_p (void) const
89 return change_prob == REG_BR_PROB_BASE
90 && !points_to_local_or_readonly_memory;
94 typedef vec<condition, va_gc> *conditions;
96 /* Predicates are used to represent function parameters (such as runtime)
97 which depend on a context function is called in.
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.
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.
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. */
113 typedef uint32_t clause_t;
114 class predicate
116 public:
117 enum predicate_conditions
119 false_condition = 0,
120 not_inlined_condition = 1,
121 first_dynamic_condition = 2
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;
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;
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;
140 /* Initialize predicate either to true of false depending on P. */
141 inline predicate (bool p = true)
143 if (p)
144 /* True predicate. */
145 m_clause[0] = 0;
146 else
147 /* False predicate. */
148 set_to_cond (false_condition);
151 /* Sanity check that we do not mix pointers to predicates with predicates. */
152 inline predicate (predicate *)
154 gcc_unreachable ();
157 /* Return predicate testing condition I. */
158 static inline predicate predicate_testing_cond (int i)
160 class predicate p;
161 p.set_to_cond (i + first_dynamic_condition);
162 return p;
165 /* Return predicate testing that function was not inlined. */
166 static predicate not_inlined (void)
168 class predicate p;
169 p.set_to_cond (not_inlined_condition);
170 return p;
173 /* Compute logical and of predicates. */
174 predicate & operator &= (const predicate &);
175 inline predicate operator &(const predicate &p) const
177 predicate ret = *this;
178 ret &= p;
179 return ret;
182 /* Compute logical or of predicates. This is not operator because
183 extra parameter CONDITIONS is needed */
184 predicate or_with (conditions, const predicate &) const;
186 /* Return true if predicates are known to be equal. */
187 inline bool operator==(const predicate &p2) const
189 int i;
190 for (i = 0; m_clause[i]; i++)
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;
199 return !p2.m_clause[i];
202 /* Return true if predicates are known to be true or false depending
203 on COND. */
204 inline bool operator==(const bool cond) const
206 if (cond)
207 return !m_clause[0];
208 if (m_clause[0] == (1 << false_condition))
210 gcc_checking_assert (!m_clause[1]
211 && m_clause[0] == 1
212 << false_condition);
213 return true;
215 return false;
218 inline bool operator!=(const predicate &p2) const
220 return !(*this == p2);
223 inline bool operator!=(const bool cond) const
225 return !(*this == cond);
228 /* Evaluate if predicate is known to be false given the clause of possible
229 truths. */
230 bool evaluate (clause_t) const;
232 /* Estimate probability that predicate will be true in a given context. */
233 int probability (conditions, clause_t, vec<inline_param_summary>) const;
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;
239 /* Return predicate equal to THIS after duplication. */
240 predicate remap_after_duplication (clause_t);
242 /* Return predicate equal to THIS after inlining. */
243 predicate remap_after_inlining (class ipa_fn_summary *,
244 class ipa_node_params *params_summary,
245 class ipa_fn_summary *,
246 const vec<int> &, const vec<HOST_WIDE_INT> &,
247 clause_t, const predicate &);
249 void stream_in (class lto_input_block *);
250 void stream_out (struct output_block *);
252 private:
253 static const int max_clauses = 8;
254 clause_t m_clause[max_clauses + 1];
256 /* Initialize predicate to one testing single condition number COND. */
257 inline void set_to_cond (int cond)
259 m_clause[0] = 1 << cond;
260 m_clause[1] = 0;
263 void add_clause (conditions conditions, clause_t);
266 void dump_condition (FILE *f, conditions conditions, int cond);
267 predicate add_condition (class ipa_fn_summary *summary,
268 class ipa_node_params *params_summary,
269 int operand_num,
270 tree type, struct agg_position_info *aggpos,
271 enum tree_code code, tree val,
272 expr_eval_ops param_ops = NULL);