]>
Commit | Line | Data |
---|---|---|
c8742849 MJ |
1 | /* Interprocedural constant propagation |
2 | Copyright (C) 2024 Free Software Foundation, Inc. | |
3 | ||
4 | This file is part of GCC. | |
5 | ||
6 | GCC is free software; you can redistribute it and/or modify it under | |
7 | the terms of the GNU General Public License as published by the Free | |
8 | Software Foundation; either version 3, or (at your option) any later | |
9 | version. | |
10 | ||
11 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
12 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 | for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
17 | along with GCC; see the file COPYING3. If not see | |
18 | <http://www.gnu.org/licenses/>. */ | |
19 | ||
20 | #ifndef IPA_CP_H | |
21 | #define IPA_CP_H | |
22 | ||
23 | template <typename valtype> class ipcp_value; | |
24 | ||
25 | /* Describes a particular source for an IPA-CP value. */ | |
26 | ||
27 | template <typename valtype> | |
28 | struct ipcp_value_source | |
29 | { | |
30 | public: | |
31 | /* Aggregate offset of the source, negative if the source is scalar value of | |
32 | the argument itself. */ | |
33 | HOST_WIDE_INT offset; | |
34 | /* The incoming edge that brought the value. */ | |
35 | cgraph_edge *cs; | |
36 | /* If the jump function that resulted into his value was a pass-through or an | |
37 | ancestor, this is the ipcp_value of the caller from which the described | |
38 | value has been derived. Otherwise it is NULL. */ | |
39 | ipcp_value<valtype> *val; | |
40 | /* Next pointer in a linked list of sources of a value. */ | |
41 | ipcp_value_source *next; | |
42 | /* If the jump function that resulted into his value was a pass-through or an | |
43 | ancestor, this is the index of the parameter of the caller the jump | |
44 | function references. */ | |
45 | int index; | |
46 | }; | |
47 | ||
48 | /* Common ancestor for all ipcp_value instantiations. */ | |
49 | ||
50 | class ipcp_value_base | |
51 | { | |
52 | public: | |
53 | /* Time benefit and that specializing the function for this value would bring | |
54 | about in this function alone. */ | |
55 | sreal local_time_benefit = 0; | |
56 | /* Time benefit that specializing the function for this value can bring about | |
57 | in it's callees. */ | |
58 | sreal prop_time_benefit = 0; | |
59 | /* Size cost that specializing the function for this value would bring about | |
60 | in this function alone. */ | |
61 | int local_size_cost = 0; | |
62 | /* Size cost that specializing the function for this value can bring about in | |
63 | it's callees. */ | |
64 | int prop_size_cost = 0; | |
65 | }; | |
66 | ||
67 | /* Describes one particular value stored in struct ipcp_lattice. */ | |
68 | ||
69 | template <typename valtype> | |
70 | class ipcp_value : public ipcp_value_base | |
71 | { | |
72 | public: | |
73 | /* The actual value for the given parameter. */ | |
74 | valtype value; | |
75 | /* The list of sources from which this value originates. */ | |
76 | ipcp_value_source <valtype> *sources = nullptr; | |
77 | /* Next pointers in a linked list of all values in a lattice. */ | |
78 | ipcp_value *next = nullptr; | |
79 | /* Next pointers in a linked list of values in a strongly connected component | |
80 | of values. */ | |
81 | ipcp_value *scc_next = nullptr; | |
82 | /* Next pointers in a linked list of SCCs of values sorted topologically | |
83 | according their sources. */ | |
84 | ipcp_value *topo_next = nullptr; | |
85 | /* A specialized node created for this value, NULL if none has been (so far) | |
86 | created. */ | |
87 | cgraph_node *spec_node = nullptr; | |
88 | /* Depth first search number and low link for topological sorting of | |
89 | values. */ | |
90 | int dfs = 0; | |
91 | int low_link = 0; | |
92 | /* SCC number to identify values which recursively feed into each other. | |
93 | Values in the same SCC have the same SCC number. */ | |
94 | int scc_no = 0; | |
95 | /* Non zero if the value is generated from another value in the same lattice | |
96 | for a self-recursive call, the actual number is how many times the | |
97 | operation has been performed. In the unlikely event of the value being | |
98 | present in two chains fo self-recursive value generation chains, it is the | |
99 | maximum. */ | |
100 | unsigned self_recursion_generated_level = 0; | |
101 | /* True if this value is currently on the topo-sort stack. */ | |
102 | bool on_stack = false; | |
103 | ||
104 | void add_source (cgraph_edge *cs, ipcp_value *src_val, int src_idx, | |
105 | HOST_WIDE_INT offset); | |
106 | ||
107 | /* Return true if both THIS value and O feed into each other. */ | |
108 | ||
109 | bool same_scc (const ipcp_value<valtype> *o) | |
110 | { | |
111 | return o->scc_no == scc_no; | |
112 | } | |
113 | ||
114 | /* Return true, if a this value has been generated for a self-recursive call as | |
115 | a result of an arithmetic pass-through jump-function acting on a value in | |
116 | the same lattice function. */ | |
117 | ||
118 | bool self_recursion_generated_p () | |
119 | { | |
120 | return self_recursion_generated_level > 0; | |
121 | } | |
122 | }; | |
123 | ||
124 | /* Lattice describing potential values of a formal parameter of a function, or | |
125 | a part of an aggregate. TOP is represented by a lattice with zero values | |
126 | and with contains_variable and bottom flags cleared. BOTTOM is represented | |
127 | by a lattice with the bottom flag set. In that case, values and | |
128 | contains_variable flag should be disregarded. */ | |
129 | ||
130 | template <typename valtype> | |
131 | struct ipcp_lattice | |
132 | { | |
133 | public: | |
134 | /* The list of known values and types in this lattice. Note that values are | |
135 | not deallocated if a lattice is set to bottom because there may be value | |
136 | sources referencing them. */ | |
137 | ipcp_value<valtype> *values = nullptr; | |
138 | /* Number of known values and types in this lattice. */ | |
139 | int values_count = 0; | |
140 | /* The lattice contains a variable component (in addition to values). */ | |
141 | bool contains_variable = false; | |
142 | /* The value of the lattice is bottom (i.e. variable and unusable for any | |
143 | propagation). */ | |
144 | bool bottom = false; | |
145 | ||
146 | inline bool is_single_const (); | |
147 | inline bool set_to_bottom (); | |
148 | inline bool set_contains_variable (); | |
149 | bool add_value (valtype newval, cgraph_edge *cs, | |
150 | ipcp_value<valtype> *src_val = NULL, | |
151 | int src_idx = 0, HOST_WIDE_INT offset = -1, | |
152 | ipcp_value<valtype> **val_p = NULL, | |
153 | unsigned same_lat_gen_level = 0); | |
154 | void print (FILE * f, bool dump_sources, bool dump_benefits); | |
155 | }; | |
156 | ||
157 | /* Lattice of tree values with an offset to describe a part of an | |
158 | aggregate. */ | |
159 | ||
160 | struct ipcp_agg_lattice : public ipcp_lattice<tree> | |
161 | { | |
162 | public: | |
163 | /* Offset that is being described by this lattice. */ | |
164 | HOST_WIDE_INT offset = 0; | |
165 | /* Size so that we don't have to re-compute it every time we traverse the | |
166 | list. Must correspond to TYPE_SIZE of all lat values. */ | |
167 | HOST_WIDE_INT size = 0; | |
168 | /* Next element of the linked list. */ | |
169 | struct ipcp_agg_lattice *next = nullptr; | |
170 | }; | |
171 | ||
172 | /* Lattice of known bits, only capable of holding one value. | |
173 | Bitwise constant propagation propagates which bits of a | |
174 | value are constant. | |
175 | For eg: | |
176 | int f(int x) | |
177 | { | |
178 | return some_op (x); | |
179 | } | |
180 | ||
181 | int f1(int y) | |
182 | { | |
183 | if (cond) | |
184 | return f (y & 0xff); | |
185 | else | |
186 | return f (y & 0xf); | |
187 | } | |
188 | ||
189 | In the above case, the param 'x' will always have all | |
190 | the bits (except the bits in lsb) set to 0. | |
191 | Hence the mask of 'x' would be 0xff. The mask | |
192 | reflects that the bits in lsb are unknown. | |
193 | The actual propagated value is given by m_value & ~m_mask. */ | |
194 | ||
195 | class ipcp_bits_lattice | |
196 | { | |
197 | public: | |
198 | bool bottom_p () const { return m_lattice_val == IPA_BITS_VARYING; } | |
199 | bool top_p () const { return m_lattice_val == IPA_BITS_UNDEFINED; } | |
200 | bool constant_p () const { return m_lattice_val == IPA_BITS_CONSTANT; } | |
201 | bool set_to_bottom (); | |
202 | bool set_to_constant (widest_int, widest_int); | |
203 | bool known_nonzero_p () const; | |
204 | ||
205 | widest_int get_value () const { return m_value; } | |
206 | widest_int get_mask () const { return m_mask; } | |
207 | ||
208 | bool meet_with (ipcp_bits_lattice& other, unsigned, signop, | |
209 | enum tree_code, tree, bool); | |
210 | ||
211 | bool meet_with (widest_int, widest_int, unsigned); | |
212 | ||
213 | void print (FILE *); | |
214 | ||
215 | private: | |
216 | enum { IPA_BITS_UNDEFINED, IPA_BITS_CONSTANT, IPA_BITS_VARYING } | |
217 | m_lattice_val = IPA_BITS_UNDEFINED; | |
218 | ||
219 | /* Similar to ccp_lattice_t, mask represents which bits of value are constant. | |
220 | If a bit in mask is set to 0, then the corresponding bit in | |
221 | value is known to be constant. */ | |
222 | widest_int m_value, m_mask; | |
223 | ||
224 | bool meet_with_1 (widest_int, widest_int, unsigned, bool); | |
225 | void get_value_and_mask (tree, widest_int *, widest_int *); | |
226 | }; | |
227 | ||
228 | /* Lattice of value ranges. */ | |
229 | ||
230 | class ipcp_vr_lattice | |
231 | { | |
232 | public: | |
233 | Value_Range m_vr; | |
234 | ||
235 | inline bool bottom_p () const; | |
236 | inline bool top_p () const; | |
237 | inline bool set_to_bottom (); | |
238 | bool meet_with (const vrange &p_vr); | |
239 | bool meet_with (const ipcp_vr_lattice &other); | |
240 | void init (tree type); | |
241 | void print (FILE * f); | |
242 | ||
243 | private: | |
244 | bool meet_with_1 (const vrange &other_vr); | |
245 | }; | |
246 | ||
247 | inline void | |
248 | ipcp_vr_lattice::init (tree type) | |
249 | { | |
250 | if (type) | |
251 | m_vr.set_type (type); | |
252 | ||
253 | // Otherwise m_vr will default to unsupported_range. | |
254 | } | |
255 | ||
256 | /* Structure containing lattices for a parameter itself and for pieces of | |
257 | aggregates that are passed in the parameter or by a reference in a parameter | |
258 | plus some other useful flags. | |
259 | ||
260 | Even after construction, m_value_range parts still need to be initialized | |
261 | with the type they represent with the init method. */ | |
262 | ||
263 | class ipcp_param_lattices | |
264 | { | |
265 | public: | |
266 | /* Lattice describing the value of the parameter itself. */ | |
267 | ipcp_lattice<tree> itself; | |
268 | /* Lattice describing the polymorphic contexts of a parameter. */ | |
269 | ipcp_lattice<ipa_polymorphic_call_context> ctxlat; | |
270 | /* Lattices describing aggregate parts. */ | |
271 | ipcp_agg_lattice *aggs = nullptr; | |
272 | /* Lattice describing known bits. */ | |
273 | ipcp_bits_lattice bits_lattice; | |
274 | /* Lattice describing value range. */ | |
275 | ipcp_vr_lattice m_value_range; | |
276 | /* Number of aggregate lattices */ | |
277 | int aggs_count = 0; | |
278 | /* True if aggregate data were passed by reference (as opposed to by | |
279 | value). */ | |
280 | bool aggs_by_ref = false; | |
281 | /* All aggregate lattices contain a variable component (in addition to | |
282 | values). */ | |
283 | bool aggs_contain_variable = false; | |
284 | /* The value of all aggregate lattices is bottom (i.e. variable and unusable | |
285 | for any propagation). */ | |
286 | bool aggs_bottom = false; | |
287 | ||
288 | /* There is a virtual call based on this parameter. */ | |
289 | bool virt_call = false; | |
290 | }; | |
291 | ||
11628614 MJ |
292 | bool values_equal_for_ipcp_p (tree x, tree y); |
293 | ||
24853cd8 AH |
294 | /* Return TRUE if IPA supports ranges of TYPE. */ |
295 | ||
296 | static inline bool | |
297 | ipa_supports_p (tree type) | |
298 | { | |
d7bb8eaa | 299 | return irange::supports_p (type); |
24853cd8 AH |
300 | } |
301 | ||
c8742849 | 302 | #endif /* IPA_CP_H */ |