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 | |
292 | bool values_equal_for_ipcp_p (tree x, tree y); |
293 | |
294 | #endif /* IPA_CP_H */ |
295 | |