Line data Source code
1 : /* Interprocedural constant propagation
2 : Copyright (C) 2024-2026 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 20745 : bool same_scc (const ipcp_value<valtype> *o)
110 : {
111 20745 : 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 190449 : bool self_recursion_generated_p ()
119 : {
120 190449 : 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 57279 : 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 57279 : 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 6758230 : bool bottom_p () const { return m_lattice_val == IPA_BITS_VARYING; }
199 94878 : bool top_p () const { return m_lattice_val == IPA_BITS_UNDEFINED; }
200 583989 : 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 : bool set_recipient_only ();
205 22697 : bool recipient_only_p () const {return m_recipient_only; }
206 :
207 113850 : widest_int get_value () const { return m_value; }
208 113850 : widest_int get_mask () const { return m_mask; }
209 :
210 : bool meet_with (ipcp_bits_lattice& other, unsigned, signop,
211 : enum tree_code, tree, bool);
212 :
213 : bool meet_with (widest_int, widest_int, unsigned);
214 :
215 : void print (FILE *);
216 :
217 : private:
218 : enum { IPA_BITS_UNDEFINED, IPA_BITS_CONSTANT, IPA_BITS_VARYING }
219 : m_lattice_val = IPA_BITS_UNDEFINED;
220 :
221 : /* Set to true if the lattice is valid only as a recipient of propagatad
222 : values but cannot be used as source of propagation because there may be
223 : unknown callers. */
224 : bool m_recipient_only;
225 :
226 : /* Similar to ccp_lattice_t, mask represents which bits of value are constant.
227 : If a bit in mask is set to 0, then the corresponding bit in
228 : value is known to be constant. */
229 : widest_int m_value, m_mask;
230 :
231 : bool meet_with_1 (widest_int, widest_int, unsigned, bool);
232 : void get_value_and_mask (tree, widest_int *, widest_int *);
233 : };
234 :
235 : /* Lattice of value ranges. */
236 :
237 4640088 : class ipcp_vr_lattice
238 : {
239 : public:
240 : value_range m_vr;
241 : /* Set to true if the lattice is valid only as a recipient of propagatad
242 : values but cannot be used as source of propagation because there may be
243 : unknown callers. */
244 : bool m_recipient_only;
245 :
246 : inline bool bottom_p () const;
247 : inline bool top_p () const;
248 : inline bool set_to_bottom ();
249 : bool set_recipient_only ();
250 16952 : bool recipient_only_p () const {return m_recipient_only; }
251 : bool meet_with (const vrange &p_vr);
252 : bool meet_with (const ipcp_vr_lattice &other);
253 : void init (tree type);
254 : void print (FILE * f);
255 :
256 : private:
257 : bool meet_with_1 (const vrange &other_vr);
258 : };
259 :
260 : inline void
261 2320044 : ipcp_vr_lattice::init (tree type)
262 : {
263 2098710 : if (type)
264 2320044 : m_vr.set_type (type);
265 :
266 : // Otherwise m_vr will default to unsupported_range.
267 2320044 : m_recipient_only = false;
268 : }
269 :
270 : /* Structure containing lattices for a parameter itself and for pieces of
271 : aggregates that are passed in the parameter or by a reference in a parameter
272 : plus some other useful flags.
273 :
274 : Even after construction, m_value_range parts still need to be initialized
275 : with the type they represent with the init method. */
276 :
277 2320044 : class ipcp_param_lattices
278 : {
279 : public:
280 : /* Lattice describing the value of the parameter itself. */
281 : ipcp_lattice<tree> itself;
282 : /* Lattice describing the polymorphic contexts of a parameter. */
283 : ipcp_lattice<ipa_polymorphic_call_context> ctxlat;
284 : /* Lattices describing aggregate parts. */
285 : ipcp_agg_lattice *aggs = nullptr;
286 : /* Lattice describing known bits. */
287 : ipcp_bits_lattice bits_lattice;
288 : /* Lattice describing value range. */
289 : ipcp_vr_lattice m_value_range;
290 : /* Number of aggregate lattices */
291 : int aggs_count = 0;
292 : /* True if aggregate data were passed by reference (as opposed to by
293 : value). */
294 : bool aggs_by_ref = false;
295 : /* All aggregate lattices contain a variable component (in addition to
296 : values). */
297 : bool aggs_contain_variable = false;
298 : /* The value of all aggregate lattices is bottom (i.e. variable and unusable
299 : for any propagation). */
300 : bool aggs_bottom = false;
301 :
302 : /* There is a virtual call based on this parameter. */
303 : bool virt_call = false;
304 : };
305 :
306 : bool values_equal_for_ipcp_p (tree x, tree y);
307 :
308 : /* Return TRUE if IPA supports ranges of TYPE. */
309 :
310 : static inline bool
311 23110396 : ipa_vr_supported_type_p (tree type)
312 : {
313 12239465 : return irange::supports_p (type) || prange::supports_p (type);
314 : }
315 :
316 : class ipa_vr;
317 :
318 : bool ipa_vr_operation_and_type_effects (vrange &dst_vr,
319 : const vrange &src_vr,
320 : enum tree_code operation,
321 : tree dst_type, tree src_type);
322 : bool ipa_vr_operation_and_type_effects (vrange &dst_vr,
323 : const ipa_vr &src_vr,
324 : enum tree_code operation,
325 : tree dst_type, tree src_type);
326 :
327 :
328 :
329 : #endif /* IPA_CP_H */
|
