Daily bump.
[official-gcc.git] / gcc / ipa-predicate.h
blob6d4881952a2b9f02b63d32d521f0d02af37f7a77
1 /* IPA predicates.
2 Copyright (C) 2003-2017 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 for function_param OP VAL, where VAL is
26 IPA invariant. The conditions are then referred by predicates. */
28 struct GTY(()) condition
30 /* If agg_contents is set, this is the offset from which the used data was
31 loaded. */
32 HOST_WIDE_INT offset;
33 /* Size of the access reading the data (or the PARM_DECL SSA_NAME). */
34 HOST_WIDE_INT size;
35 tree val;
36 int operand_num;
37 ENUM_BITFIELD(tree_code) code : 16;
38 /* Set if the used data were loaded from an aggregate parameter or from
39 data received by reference. */
40 unsigned agg_contents : 1;
41 /* If agg_contents is set, this differentiates between loads from data
42 passed by reference and by value. */
43 unsigned by_ref : 1;
46 /* Information kept about parameter of call site. */
47 struct inline_param_summary
49 /* REG_BR_PROB_BASE based probability that parameter will change in between
50 two invocation of the calls.
51 I.e. loop invariant parameters
52 REG_BR_PROB_BASE/estimated_iterations and regular
53 parameters REG_BR_PROB_BASE.
55 Value 0 is reserved for compile time invariants. */
56 int change_prob;
59 typedef vec<condition, va_gc> *conditions;
61 /* Predicates are used to repesent function parameters (such as runtime)
62 which depend on a context function is called in.
64 Predicates are logical formulas in conjunctive-disjunctive form consisting
65 of clauses which are bitmaps specifying a set of condition that must
66 be true for a clause to be satisfied. Physically they are represented as
67 array of clauses terminated by 0.
69 In order to make predicate (possibly) true, all of its clauses must
70 be (possibly) true. To make clause (possibly) true, one of conditions
71 it mentions must be (possibly) true.
73 There are fixed bounds on number of clauses and conditions and all the
74 manipulation functions are conservative in positive direction. I.e. we
75 may lose precision by thinking that predicate may be true even when it
76 is not. */
78 typedef uint32_t clause_t;
79 class predicate
81 public:
82 enum predicate_conditions
84 false_condition = 0,
85 not_inlined_condition = 1,
86 first_dynamic_condition = 2
89 /* Maximal number of conditions predicate can reffer to. This is limited
90 by using clause_t to be 32bit. */
91 static const int num_conditions = 32;
93 /* Special condition code we use to represent test that operand is compile
94 time constant. */
95 static const tree_code is_not_constant = ERROR_MARK;
97 /* Special condition code we use to represent test that operand is not changed
98 across invocation of the function. When operand IS_NOT_CONSTANT it is
99 always CHANGED, however i.e. loop invariants can be NOT_CHANGED given
100 percentage of executions even when they are not compile time constants. */
101 static const tree_code changed = IDENTIFIER_NODE;
105 /* Initialize predicate either to true of false depending on P. */
106 inline predicate (bool p = true)
108 if (p)
109 /* True predicate. */
110 m_clause[0] = 0;
111 else
112 /* False predicate. */
113 set_to_cond (false_condition);
116 /* Sanity check that we do not mix pointers to predicates with predicates. */
117 inline predicate (predicate *)
119 gcc_unreachable ();
122 /* Return predicate testing condition I. */
123 static inline predicate predicate_testing_cond (int i)
125 class predicate p;
126 p.set_to_cond (i + first_dynamic_condition);
127 return p;
130 /* Return predicate testing that function was not inlined. */
131 static predicate not_inlined (void)
133 class predicate p;
134 p.set_to_cond (not_inlined_condition);
135 return p;
138 /* Compute logical and of predicates. */
139 predicate & operator &= (const predicate &);
140 inline predicate operator &(const predicate &p) const
142 predicate ret = *this;
143 ret &= p;
144 return ret;
147 /* Compute logical or of predicates. This is not operator because
148 extra parameter CONDITIONS is needed */
149 predicate or_with (conditions, const predicate &) const;
151 /* Return true if predicates are known to be equal. */
152 inline bool operator==(const predicate &p2) const
154 int i;
155 for (i = 0; m_clause[i]; i++)
157 gcc_checking_assert (i < max_clauses);
158 gcc_checking_assert (m_clause[i] > m_clause[i + 1]);
159 gcc_checking_assert (!p2.m_clause[i]
160 || p2.m_clause[i] > p2.m_clause[i + 1]);
161 if (m_clause[i] != p2.m_clause[i])
162 return false;
164 return !p2.m_clause[i];
167 /* Return true if predicates are known to be true or false depending
168 on COND. */
169 inline bool operator==(const bool cond) const
171 if (cond)
172 return !m_clause[0];
173 if (m_clause[0] == (1 << false_condition))
175 gcc_checking_assert (!m_clause[1]
176 && m_clause[0] == 1
177 << false_condition);
178 return true;
180 return false;
183 inline bool operator!=(const predicate &p2) const
185 return !(*this == p2);
188 inline bool operator!=(const bool cond) const
190 return !(*this == cond);
193 /* Evaluate if predicate is known to be false given the clause of possible
194 truths. */
195 bool evaluate (clause_t) const;
197 /* Estimate probability that predicate will be true in a given context. */
198 int probability (conditions, clause_t, vec<inline_param_summary>) const;
200 /* Dump predicate to F. Output newline if nl. */
201 void dump (FILE *f, conditions, bool nl=true) const;
202 void DEBUG_FUNCTION debug (conditions) const;
204 /* Return predicate equal to THIS after duplication. */
205 predicate remap_after_duplication (clause_t);
207 /* Return predicate equal to THIS after inlining. */
208 predicate remap_after_inlining (struct ipa_fn_summary *,
209 struct ipa_fn_summary *,
210 vec<int>, vec<int>, clause_t, const predicate &);
212 void stream_in (struct lto_input_block *);
213 void stream_out (struct output_block *);
215 private:
216 static const int max_clauses = 8;
217 clause_t m_clause[max_clauses + 1];
219 /* Initialize predicate to one testing single condition number COND. */
220 inline void set_to_cond (int cond)
222 m_clause[0] = 1 << cond;
223 m_clause[1] = 0;
226 void add_clause (conditions conditions, clause_t);
229 void dump_condition (FILE *f, conditions conditions, int cond);
230 predicate add_condition (struct ipa_fn_summary *summary, int operand_num,
231 HOST_WIDE_INT size, struct agg_position_info *aggpos,
232 enum tree_code code, tree val);