1/* IPA predicates.
2 Copyright (C) 2003-2017 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 for function_param OP VAL, where VAL is
26 IPA invariant. The conditions are then referred by predicates. */
27
28struct 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. */
47struct 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
59typedef 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
78typedef uint32_t clause_t;
79class predicate
80{
81public:
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
215private:
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
229void dump_condition (FILE *f, conditions conditions, int cond);
230predicate 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