GCC Middle and Back End API Reference
ipa-cp.h
Go to the documentation of this file.
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>
29{
30public:
31 /* Aggregate offset of the source, negative if the source is scalar value of
32 the argument itself. */
34 /* The incoming edge that brought the value. */
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. */
40 /* Next pointer in a linked list of sources of a value. */
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
51{
52public:
53 /* Time benefit and that specializing the function for this value would bring
54 about in this function alone. */
56 /* Time benefit that specializing the function for this value can bring about
57 in it's callees. */
59 /* Size cost that specializing the function for this value would bring about
60 in this function alone. */
62 /* Size cost that specializing the function for this value can bring about in
63 it's callees. */
65};
66
67/* Describes one particular value stored in struct ipcp_lattice. */
68
69template <typename valtype>
71{
72public:
73 /* The actual value for the given parameter. */
75 /* The list of sources from which this value originates. */
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. */
85 /* A specialized node created for this value, NULL if none has been (so far)
86 created. */
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. */
101 /* True if this value is currently on the topo-sort stack. */
102 bool on_stack = false;
103
106
107 /* Return true if both THIS value and O feed into each other. */
108
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
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>
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. */
138 /* Number of known values and types in this lattice. */
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 ();
151 int src_idx = 0, HOST_WIDE_INT offset = -1,
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. */
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. */
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
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 ();
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:
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. */
223
224 bool meet_with_1 (widest_int, widest_int, unsigned, bool);
226};
227
228/* Lattice of value ranges. */
229
231{
232public:
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
249{
250 if (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
264{
265public:
266 /* Lattice describing the value of the parameter itself. */
268 /* Lattice describing the polymorphic contexts of a parameter. */
270 /* Lattices describing aggregate parts. */
272 /* Lattice describing known bits. */
274 /* Lattice describing 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). */
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
293
294#endif /* IPA_CP_H */
Definition value-range.h:682
void set_type(tree type)
Definition value-range.h:782
Definition cgraph.h:1696
Definition ipa-cp.h:196
bool bottom_p() const
Definition ipa-cp.h:198
bool constant_p() const
Definition ipa-cp.h:200
widest_int m_mask
Definition ipa-cp.h:222
widest_int get_mask() const
Definition ipa-cp.h:206
bool set_to_bottom()
Definition ipa-cp.cc:827
@ IPA_BITS_VARYING
Definition ipa-cp.h:216
@ IPA_BITS_CONSTANT
Definition ipa-cp.h:216
@ IPA_BITS_UNDEFINED
Definition ipa-cp.h:216
bool meet_with(ipcp_bits_lattice &other, unsigned, signop, enum tree_code, tree, bool)
Definition ipa-cp.cc:929
bool meet_with_1(widest_int, widest_int, unsigned, bool)
Definition ipa-cp.cc:886
widest_int m_value
Definition ipa-cp.h:222
void get_value_and_mask(tree, widest_int *, widest_int *)
Definition ipa-cp.cc:863
bool known_nonzero_p() const
Definition ipa-cp.cc:853
bool top_p() const
Definition ipa-cp.h:199
enum ipcp_bits_lattice::@50 m_lattice_val
widest_int get_value() const
Definition ipa-cp.h:205
void print(FILE *)
Definition ipa-cp.cc:301
bool set_to_constant(widest_int, widest_int)
Definition ipa-cp.cc:841
Definition ipa-cp.h:264
ipcp_lattice< tree > itself
Definition ipa-cp.h:267
ipcp_vr_lattice m_value_range
Definition ipa-cp.h:275
bool aggs_bottom
Definition ipa-cp.h:286
ipcp_bits_lattice bits_lattice
Definition ipa-cp.h:273
bool aggs_contain_variable
Definition ipa-cp.h:283
ipcp_agg_lattice * aggs
Definition ipa-cp.h:271
int aggs_count
Definition ipa-cp.h:277
ipcp_lattice< ipa_polymorphic_call_context > ctxlat
Definition ipa-cp.h:269
bool virt_call
Definition ipa-cp.h:289
bool aggs_by_ref
Definition ipa-cp.h:280
Definition ipa-cp.h:51
int local_size_cost
Definition ipa-cp.h:61
sreal local_time_benefit
Definition ipa-cp.h:55
sreal prop_time_benefit
Definition ipa-cp.h:58
int prop_size_cost
Definition ipa-cp.h:64
Definition ipa-cp.h:71
void add_source(cgraph_edge *cs, ipcp_value *src_val, int src_idx, HOST_WIDE_INT offset)
Definition ipa-cp.cc:1939
valtype value
Definition ipa-cp.h:74
ipcp_value * topo_next
Definition ipa-cp.h:84
int dfs
Definition ipa-cp.h:90
bool self_recursion_generated_p()
Definition ipa-cp.h:118
bool same_scc(const ipcp_value< valtype > *o)
Definition ipa-cp.h:109
int low_link
Definition ipa-cp.h:91
int scc_no
Definition ipa-cp.h:94
ipcp_value_source< valtype > * sources
Definition ipa-cp.h:76
ipcp_value * next
Definition ipa-cp.h:78
unsigned self_recursion_generated_level
Definition ipa-cp.h:100
ipcp_value * scc_next
Definition ipa-cp.h:81
bool on_stack
Definition ipa-cp.h:102
cgraph_node * spec_node
Definition ipa-cp.h:87
Definition ipa-cp.h:231
bool meet_with_1(const vrange &other_vr)
Definition ipa-cp.cc:767
bool meet_with(const vrange &p_vr)
Definition ipa-cp.cc:758
Value_Range m_vr
Definition ipa-cp.h:233
void print(FILE *f)
Definition ipa-cp.cc:318
void init(tree type)
Definition ipa-cp.h:248
bool bottom_p() const
Definition ipa-cp.cc:799
bool top_p() const
Definition ipa-cp.cc:790
bool set_to_bottom()
Definition ipa-cp.cc:808
Definition sreal.h:41
Definition value-range.h:76
union tree_node * tree
Definition coretypes.h:97
tree_code
Definition genmatch.cc:347
T * ggc_alloc(ALONE_CXX_MEM_STAT_INFO)
Definition ggc.h:184
bool values_equal_for_ipcp_p(tree x, tree y)
Definition ipa-cp.cc:205
rtx offset
Definition postreload.cc:691
signop
Definition signop.h:28
Definition cgraph.h:875
Definition ipa-cp.h:161
HOST_WIDE_INT offset
Definition ipa-cp.h:164
HOST_WIDE_INT size
Definition ipa-cp.h:167
struct ipcp_agg_lattice * next
Definition ipa-cp.h:169
Definition ipa-cp.h:132
bool set_to_bottom()
Definition ipa-cp.cc:707
bool is_single_const()
Definition ipa-cp.cc:194
ipcp_value< valtype > * values
Definition ipa-cp.h:137
bool bottom
Definition ipa-cp.h:144
bool add_value(valtype newval, cgraph_edge *cs, ipcp_value< valtype > *src_val=NULL, int src_idx=0, HOST_WIDE_INT offset=-1, ipcp_value< valtype > **val_p=NULL, unsigned same_lat_gen_level=0)
Definition ipa-cp.cc:1997
bool contains_variable
Definition ipa-cp.h:141
void print(FILE *f, bool dump_sources, bool dump_benefits)
Definition ipa-cp.cc:239
bool set_contains_variable()
Definition ipa-cp.cc:719
int values_count
Definition ipa-cp.h:139
Definition ipa-cp.h:29
ipcp_value_source * next
Definition ipa-cp.h:41
ipcp_value< valtype > * val
Definition ipa-cp.h:39
HOST_WIDE_INT offset
Definition ipa-cp.h:33
int index
Definition ipa-cp.h:45
cgraph_edge * cs
Definition ipa-cp.h:35
Definition gengtype.h:252
#define NULL
Definition system.h:50
const T2 & y
Definition wide-int.h:3870