Branch data Line data Source code
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 : 13868 : bool same_scc (const ipcp_value<valtype> *o)
110 : : {
111 : 13868 : 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 : 62320 : bool self_recursion_generated_p ()
119 : : {
120 : 62320 : 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 : 42625 : 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 : 42625 : 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 : 6037804 : bool bottom_p () const { return m_lattice_val == IPA_BITS_VARYING; }
199 : 81168 : bool top_p () const { return m_lattice_val == IPA_BITS_UNDEFINED; }
200 : 2465110 : 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 : 102502 : widest_int get_value () const { return m_value; }
206 : 102502 : 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 : 4226890 : 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 : 2113445 : ipcp_vr_lattice::init (tree type)
249 : : {
250 : 1921641 : if (type)
251 : 2113445 : 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 : 2113445 : 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 */
|
