1 | /* IPA predicates. |
2 | Copyright (C) 2003-2017 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 for function_param OP VAL, where VAL is |
26 | IPA invariant. The conditions are then referred by predicates. */ |
27 | |
28 | struct GTY(()) condition |
29 | { |
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; |
44 | }; |
45 | |
46 | /* Information kept about parameter of call site. */ |
47 | struct inline_param_summary |
48 | { |
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. |
54 | |
55 | Value 0 is reserved for compile time invariants. */ |
56 | int change_prob; |
57 | }; |
58 | |
59 | typedef vec<condition, va_gc> *conditions; |
60 | |
61 | /* Predicates are used to repesent function parameters (such as runtime) |
62 | which depend on a context function is called in. |
63 | |
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. |
68 | |
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. |
72 | |
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. */ |
77 | |
78 | typedef uint32_t clause_t; |
79 | class predicate |
80 | { |
81 | public: |
82 | enum predicate_conditions |
83 | { |
84 | false_condition = 0, |
85 | not_inlined_condition = 1, |
86 | first_dynamic_condition = 2 |
87 | }; |
88 | |
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; |
92 | |
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; |
96 | |
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; |
102 | |
103 | |
104 | |
105 | /* Initialize predicate either to true of false depending on P. */ |
106 | inline predicate (bool p = true) |
107 | { |
108 | if (p) |
109 | /* True predicate. */ |
110 | m_clause[0] = 0; |
111 | else |
112 | /* False predicate. */ |
113 | set_to_cond (false_condition); |
114 | } |
115 | |
116 | /* Sanity check that we do not mix pointers to predicates with predicates. */ |
117 | inline predicate (predicate *) |
118 | { |
119 | gcc_unreachable (); |
120 | } |
121 | |
122 | /* Return predicate testing condition I. */ |
123 | static inline predicate predicate_testing_cond (int i) |
124 | { |
125 | class predicate p; |
126 | p.set_to_cond (i + first_dynamic_condition); |
127 | return p; |
128 | } |
129 | |
130 | /* Return predicate testing that function was not inlined. */ |
131 | static predicate not_inlined (void) |
132 | { |
133 | class predicate p; |
134 | p.set_to_cond (not_inlined_condition); |
135 | return p; |
136 | } |
137 | |
138 | /* Compute logical and of predicates. */ |
139 | predicate & operator &= (const predicate &); |
140 | inline predicate operator &(const predicate &p) const |
141 | { |
142 | predicate ret = *this; |
143 | ret &= p; |
144 | return ret; |
145 | } |
146 | |
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; |
150 | |
151 | /* Return true if predicates are known to be equal. */ |
152 | inline bool operator==(const predicate &p2) const |
153 | { |
154 | int i; |
155 | for (i = 0; m_clause[i]; i++) |
156 | { |
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; |
163 | } |
164 | return !p2.m_clause[i]; |
165 | } |
166 | |
167 | /* Return true if predicates are known to be true or false depending |
168 | on COND. */ |
169 | inline bool operator==(const bool cond) const |
170 | { |
171 | if (cond) |
172 | return !m_clause[0]; |
173 | if (m_clause[0] == (1 << false_condition)) |
174 | { |
175 | gcc_checking_assert (!m_clause[1] |
176 | && m_clause[0] == 1 |
177 | << false_condition); |
178 | return true; |
179 | } |
180 | return false; |
181 | } |
182 | |
183 | inline bool operator!=(const predicate &p2) const |
184 | { |
185 | return !(*this == p2); |
186 | } |
187 | |
188 | inline bool operator!=(const bool cond) const |
189 | { |
190 | return !(*this == cond); |
191 | } |
192 | |
193 | /* Evaluate if predicate is known to be false given the clause of possible |
194 | truths. */ |
195 | bool evaluate (clause_t) const; |
196 | |
197 | /* Estimate probability that predicate will be true in a given context. */ |
198 | int probability (conditions, clause_t, vec<inline_param_summary>) const; |
199 | |
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; |
203 | |
204 | /* Return predicate equal to THIS after duplication. */ |
205 | predicate remap_after_duplication (clause_t); |
206 | |
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 &); |
211 | |
212 | void stream_in (struct lto_input_block *); |
213 | void stream_out (struct output_block *); |
214 | |
215 | private: |
216 | static const int max_clauses = 8; |
217 | clause_t m_clause[max_clauses + 1]; |
218 | |
219 | /* Initialize predicate to one testing single condition number COND. */ |
220 | inline void set_to_cond (int cond) |
221 | { |
222 | m_clause[0] = 1 << cond; |
223 | m_clause[1] = 0; |
224 | } |
225 | |
226 | void add_clause (conditions conditions, clause_t); |
227 | }; |
228 | |
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); |
233 | |