1/* Interprocedural constant propagation
2 Copyright (C) 2024 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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
23template <typename valtype> class ipcp_value;
24
25/* Describes a particular source for an IPA-CP value. */
26
27template <typename valtype>
28struct ipcp_value_source
29{
30public:
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
50class ipcp_value_base
51{
52public:
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
69template <typename valtype>
70class ipcp_value : public ipcp_value_base
71{
72public:
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
130template <typename valtype>
131struct ipcp_lattice
132{
133public:
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
160struct ipcp_agg_lattice : public ipcp_lattice<tree>
161{
162public:
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
195class ipcp_bits_lattice
196{
197public:
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
215private:
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
230class ipcp_vr_lattice
231{
232public:
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
243private:
244 bool meet_with_1 (const vrange &other_vr);
245};
246
247inline void
248ipcp_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
263class ipcp_param_lattices
264{
265public:
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
292bool values_equal_for_ipcp_p (tree x, tree y);
293
294#endif /* IPA_CP_H */
295

source code of gcc/ipa-cp.h