|
0
|
1 /* Interprocedural analyses.
|
|
|
2 Copyright (C) 2005, 2007, 2008 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_PROP_H
|
|
|
21 #define IPA_PROP_H
|
|
|
22
|
|
|
23 #include "tree.h"
|
|
|
24 #include "vec.h"
|
|
|
25 #include "cgraph.h"
|
|
|
26
|
|
|
27 /* The following definitions and interfaces are used by
|
|
|
28 interprocedural analyses. */
|
|
|
29
|
|
|
30 /* A jump function for a callsite represents the values passed as actual
|
|
|
31 arguments of the callsite. There are three main types of values :
|
|
|
32 Formal - the caller's formal parameter is passed as an actual argument.
|
|
|
33 Constant - a constant is passed as an actual argument.
|
|
|
34 Unknown - neither of the above.
|
|
|
35 Integer and real constants are represented as IPA_CONST.
|
|
|
36 Finally, IPA_CONST_MEMBER_PTR stands for C++ member pointers constants. */
|
|
|
37 enum jump_func_type
|
|
|
38 {
|
|
|
39 IPA_UNKNOWN = 0, /* newly allocated and zeroed jump functions default */
|
|
|
40 IPA_CONST,
|
|
|
41 IPA_CONST_MEMBER_PTR,
|
|
|
42 IPA_PASS_THROUGH
|
|
|
43 };
|
|
|
44
|
|
|
45 /* All formal parameters in the program have a lattice associated with it
|
|
|
46 computed by the interprocedural stage of IPCP.
|
|
|
47 There are three main values of the lattice:
|
|
|
48 IPA_TOP - unknown,
|
|
|
49 IPA_BOTTOM - non constant,
|
|
|
50 IPA_CONST_VALUE - simple scalar constant,
|
|
|
51 Cval of formal f will have a constant value if all callsites to this
|
|
|
52 function have the same constant value passed to f.
|
|
|
53 Integer and real constants are represented as IPA_CONST. */
|
|
|
54 enum ipa_lattice_type
|
|
|
55 {
|
|
|
56 IPA_BOTTOM,
|
|
|
57 IPA_CONST_VALUE,
|
|
|
58 IPA_TOP
|
|
|
59 };
|
|
|
60
|
|
|
61 /* Structure holding a C++ member pointer constant. Holds a pointer to the
|
|
|
62 method and delta offset. */
|
|
|
63 struct ipa_member_ptr_cst
|
|
|
64 {
|
|
|
65 tree pfn;
|
|
|
66 tree delta;
|
|
|
67 };
|
|
|
68
|
|
|
69 /* Represents a value of a jump function. formal_id is used only in jump
|
|
|
70 function context and represents pass-through parameter (the formal parameter
|
|
|
71 of the caller is passed as argument). constant represents the actual
|
|
|
72 constant in constant jump functions and member_cst holds constant c++ member
|
|
|
73 functions. */
|
|
|
74 union jump_func_value
|
|
|
75 {
|
|
|
76 unsigned int formal_id;
|
|
|
77 tree constant;
|
|
|
78 struct ipa_member_ptr_cst member_cst;
|
|
|
79 };
|
|
|
80
|
|
|
81 /* A jump function for a callsite represents the values passed as actual
|
|
|
82 arguments of the callsite. See enum jump_func_type for the various
|
|
|
83 types of jump functions supported. */
|
|
|
84 struct ipa_jump_func
|
|
|
85 {
|
|
|
86 enum jump_func_type type;
|
|
|
87 union jump_func_value value;
|
|
|
88 };
|
|
|
89
|
|
|
90 /* All formal parameters in the program have a cval computed by
|
|
|
91 the interprocedural stage of IPCP. See enum ipa_lattice_type for
|
|
|
92 the various types of lattices supported */
|
|
|
93 struct ipcp_lattice
|
|
|
94 {
|
|
|
95 enum ipa_lattice_type type;
|
|
|
96 tree constant;
|
|
|
97 };
|
|
|
98
|
|
|
99 /* Represent which DECL tree (or reference to such tree)
|
|
|
100 will be replaced by another tree while versioning. */
|
|
|
101 struct ipa_replace_map
|
|
|
102 {
|
|
|
103 /* The tree that will be replaced. */
|
|
|
104 tree old_tree;
|
|
|
105 /* The new (replacing) tree. */
|
|
|
106 tree new_tree;
|
|
|
107 /* True when a substitution should be done, false otherwise. */
|
|
|
108 bool replace_p;
|
|
|
109 /* True when we replace a reference to old_tree. */
|
|
|
110 bool ref_p;
|
|
|
111 };
|
|
|
112
|
|
|
113 /* Each instance of the following structure describes a statement that calls a
|
|
|
114 function parameter. Those referring to statements within the same function
|
|
|
115 are linked in a list. */
|
|
|
116 struct ipa_param_call_note
|
|
|
117 {
|
|
|
118 /* Linked list's next */
|
|
|
119 struct ipa_param_call_note *next;
|
|
|
120 /* Statement that contains the call to the parameter above. */
|
|
|
121 gimple stmt;
|
|
|
122 /* Index of the parameter that is called. */
|
|
|
123 unsigned int formal_id;
|
|
|
124 /* Expected number of executions: calculated in profile.c. */
|
|
|
125 gcov_type count;
|
|
|
126 /* Expected frequency of executions within the function. see cgraph_edge in
|
|
|
127 cgraph.h for more on this. */
|
|
|
128 int frequency;
|
|
|
129 /* Depth of loop nest, 1 means no loop nest. */
|
|
|
130 int loop_nest;
|
|
|
131 /* Set when we have already found the target to be a compile time constant
|
|
|
132 and turned this into an edge or when the note was found unusable for some
|
|
|
133 reason. */
|
|
|
134 bool processed;
|
|
|
135 };
|
|
|
136
|
|
|
137 /* Structure describing a single formal parameter. */
|
|
|
138 struct ipa_param_descriptor
|
|
|
139 {
|
|
|
140 /* IPA-CP lattice. */
|
|
|
141 struct ipcp_lattice ipcp_lattice;
|
|
|
142 /* PARAM_DECL of this parameter. */
|
|
|
143 tree decl;
|
|
|
144 /* Whether the value parameter has been modified within the function. */
|
|
|
145 unsigned modified : 1;
|
|
|
146 /* Whether the parameter has been used as a call destination. */
|
|
|
147 unsigned called : 1;
|
|
|
148 };
|
|
|
149
|
|
|
150 /* ipa_node_params stores information related to formal parameters of functions
|
|
|
151 and some other information for interprocedural passes that operate on
|
|
|
152 parameters (such as ipa-cp). */
|
|
|
153 struct ipa_node_params
|
|
|
154 {
|
|
|
155 /* Number of formal parameters of this function. When set to 0,
|
|
|
156 this function's parameters would not be analyzed by the different
|
|
|
157 stages of IPA CP. */
|
|
|
158 int param_count;
|
|
|
159 /* Pointer to an array of structures describing individual formal
|
|
|
160 parameters. */
|
|
|
161 struct ipa_param_descriptor *params;
|
|
|
162 /* List of structures enumerating calls to a formal parameter. */
|
|
|
163 struct ipa_param_call_note *param_calls;
|
|
|
164 /* Only for versioned nodes this field would not be NULL,
|
|
|
165 it points to the node that IPA cp cloned from. */
|
|
|
166 struct cgraph_node *ipcp_orig_node;
|
|
|
167 /* Meaningful only for original functions. Expresses the
|
|
|
168 ratio between the direct calls and sum of all invocations of
|
|
|
169 this function (given by profiling info). It is used to calculate
|
|
|
170 the profiling information of the original function and the versioned
|
|
|
171 one. */
|
|
|
172 gcov_type count_scale;
|
|
|
173
|
|
|
174 /* Whether this function is called with variable number of actual
|
|
|
175 arguments. */
|
|
|
176 unsigned called_with_var_arguments : 1;
|
|
|
177 /* Whether the modification analysis has already been performed. */
|
|
|
178 unsigned modification_analysis_done : 1;
|
|
|
179 /* Whether the param uses analysis has already been performed. */
|
|
|
180 unsigned uses_analysis_done : 1;
|
|
|
181 };
|
|
|
182
|
|
|
183 /* ipa_node_params access functions. Please use these to access fields that
|
|
|
184 are or will be shared among various passes. */
|
|
|
185
|
|
|
186 /* Set the number of formal parameters. */
|
|
|
187
|
|
|
188 static inline void
|
|
|
189 ipa_set_param_count (struct ipa_node_params *info, int count)
|
|
|
190 {
|
|
|
191 info->param_count = count;
|
|
|
192 }
|
|
|
193
|
|
|
194 /* Return the number of formal parameters. */
|
|
|
195
|
|
|
196 static inline int
|
|
|
197 ipa_get_param_count (struct ipa_node_params *info)
|
|
|
198 {
|
|
|
199 return info->param_count;
|
|
|
200 }
|
|
|
201
|
|
|
202 /* Return the declaration of Ith formal parameter of the function corresponding
|
|
|
203 to INFO. Note there is no setter function as this array is built just once
|
|
|
204 using ipa_initialize_node_params. */
|
|
|
205
|
|
|
206 static inline tree
|
|
|
207 ipa_get_param (struct ipa_node_params *info, int i)
|
|
|
208 {
|
|
|
209 return info->params[i].decl;
|
|
|
210 }
|
|
|
211
|
|
|
212 /* Return the modification flag corresponding to the Ith formal parameter of
|
|
|
213 the function associated with INFO. Note that there is no setter method as
|
|
|
214 the goal is to set all flags when building the array in
|
|
|
215 ipa_detect_param_modifications. */
|
|
|
216
|
|
|
217 static inline bool
|
|
|
218 ipa_is_param_modified (struct ipa_node_params *info, int i)
|
|
|
219 {
|
|
|
220 return info->params[i].modified;
|
|
|
221 }
|
|
|
222
|
|
|
223 /* Return the called flag corresponding to the Ith formal parameter of the
|
|
|
224 function associated with INFO. Note that there is no setter method as the
|
|
|
225 goal is to set all flags when building the array in
|
|
|
226 ipa_detect_called_params. */
|
|
|
227
|
|
|
228 static inline bool
|
|
|
229 ipa_is_param_called (struct ipa_node_params *info, int i)
|
|
|
230 {
|
|
|
231 return info->params[i].called;
|
|
|
232 }
|
|
|
233
|
|
|
234 /* Flag this node as having callers with variable number of arguments. */
|
|
|
235
|
|
|
236 static inline void
|
|
|
237 ipa_set_called_with_variable_arg (struct ipa_node_params *info)
|
|
|
238 {
|
|
|
239 info->called_with_var_arguments = 1;
|
|
|
240 }
|
|
|
241
|
|
|
242 /* Have we detected this node was called with variable number of arguments? */
|
|
|
243
|
|
|
244 static inline bool
|
|
|
245 ipa_is_called_with_var_arguments (struct ipa_node_params *info)
|
|
|
246 {
|
|
|
247 return info->called_with_var_arguments;
|
|
|
248 }
|
|
|
249
|
|
|
250
|
|
|
251
|
|
|
252 /* ipa_edge_args stores information related to a callsite and particularly
|
|
|
253 its arguments. It is pointed to by a field in the
|
|
|
254 callsite's corresponding cgraph_edge. */
|
|
|
255 struct ipa_edge_args
|
|
|
256 {
|
|
|
257 /* Number of actual arguments in this callsite. When set to 0,
|
|
|
258 this callsite's parameters would not be analyzed by the different
|
|
|
259 stages of IPA CP. */
|
|
|
260 int argument_count;
|
|
|
261 /* Array of the callsite's jump function of each parameter. */
|
|
|
262 struct ipa_jump_func *jump_functions;
|
|
|
263 };
|
|
|
264
|
|
|
265 /* ipa_edge_args access functions. Please use these to access fields that
|
|
|
266 are or will be shared among various passes. */
|
|
|
267
|
|
|
268 /* Set the number of actual arguments. */
|
|
|
269
|
|
|
270 static inline void
|
|
|
271 ipa_set_cs_argument_count (struct ipa_edge_args *args, int count)
|
|
|
272 {
|
|
|
273 args->argument_count = count;
|
|
|
274 }
|
|
|
275
|
|
|
276 /* Return the number of actual arguments. */
|
|
|
277
|
|
|
278 static inline int
|
|
|
279 ipa_get_cs_argument_count (struct ipa_edge_args *args)
|
|
|
280 {
|
|
|
281 return args->argument_count;
|
|
|
282 }
|
|
|
283
|
|
|
284 /* Returns a pointer to the jump function for the ith argument. Please note
|
|
|
285 there is no setter function as jump functions are all set up in
|
|
|
286 ipa_compute_jump_functions. */
|
|
|
287
|
|
|
288 static inline struct ipa_jump_func *
|
|
|
289 ipa_get_ith_jump_func (struct ipa_edge_args *args, int i)
|
|
|
290 {
|
|
|
291 return &args->jump_functions[i];
|
|
|
292 }
|
|
|
293
|
|
|
294 /* Vectors need to have typedefs of structures. */
|
|
|
295 typedef struct ipa_node_params ipa_node_params_t;
|
|
|
296 typedef struct ipa_edge_args ipa_edge_args_t;
|
|
|
297
|
|
|
298 /* Types of vectors holding the infos. */
|
|
|
299 DEF_VEC_O (ipa_node_params_t);
|
|
|
300 DEF_VEC_ALLOC_O (ipa_node_params_t, heap);
|
|
|
301 DEF_VEC_O (ipa_edge_args_t);
|
|
|
302 DEF_VEC_ALLOC_O (ipa_edge_args_t, heap);
|
|
|
303
|
|
|
304 /* Vector where the parameter infos are actually stored. */
|
|
|
305 extern VEC (ipa_node_params_t, heap) *ipa_node_params_vector;
|
|
|
306 /* Vector where the parameter infos are actually stored. */
|
|
|
307 extern VEC (ipa_edge_args_t, heap) *ipa_edge_args_vector;
|
|
|
308
|
|
|
309 /* Return the associated parameter/argument info corresponding to the given
|
|
|
310 node/edge. */
|
|
|
311 #define IPA_NODE_REF(NODE) (VEC_index (ipa_node_params_t, \
|
|
|
312 ipa_node_params_vector, (NODE)->uid))
|
|
|
313 #define IPA_EDGE_REF(EDGE) (VEC_index (ipa_edge_args_t, \
|
|
|
314 ipa_edge_args_vector, (EDGE)->uid))
|
|
|
315 /* This macro checks validity of index returned by
|
|
|
316 ipa_get_param_decl_index function. */
|
|
|
317 #define IS_VALID_JUMP_FUNC_INDEX(I) ((I) != -1)
|
|
|
318
|
|
|
319 /* Creating and freeing ipa_node_params and ipa_edge_args. */
|
|
|
320 void ipa_create_all_node_params (void);
|
|
|
321 void ipa_create_all_edge_args (void);
|
|
|
322 void ipa_free_edge_args_substructures (struct ipa_edge_args *);
|
|
|
323 void ipa_free_node_params_substructures (struct ipa_node_params *);
|
|
|
324 void ipa_free_all_node_params (void);
|
|
|
325 void ipa_free_all_edge_args (void);
|
|
|
326 void free_all_ipa_structures_after_ipa_cp (void);
|
|
|
327 void free_all_ipa_structures_after_iinln (void);
|
|
|
328 void ipa_register_cgraph_hooks (void);
|
|
|
329
|
|
|
330 /* This function ensures the array of node param infos is big enough to
|
|
|
331 accommodate a structure for all nodes and reallocates it if not. */
|
|
|
332
|
|
|
333 static inline void
|
|
|
334 ipa_check_create_node_params (void)
|
|
|
335 {
|
|
|
336 if (!ipa_node_params_vector)
|
|
|
337 ipa_node_params_vector = VEC_alloc (ipa_node_params_t, heap,
|
|
|
338 cgraph_max_uid);
|
|
|
339
|
|
|
340 if (VEC_length (ipa_node_params_t, ipa_node_params_vector)
|
|
|
341 <= (unsigned) cgraph_max_uid)
|
|
|
342 VEC_safe_grow_cleared (ipa_node_params_t, heap,
|
|
|
343 ipa_node_params_vector, cgraph_max_uid + 1);
|
|
|
344 }
|
|
|
345
|
|
|
346 /* This function ensures the array of edge arguments infos is big enough to
|
|
|
347 accommodate a structure for all edges and reallocates it if not. */
|
|
|
348
|
|
|
349 static inline void
|
|
|
350 ipa_check_create_edge_args (void)
|
|
|
351 {
|
|
|
352 if (!ipa_edge_args_vector)
|
|
|
353 ipa_edge_args_vector = VEC_alloc (ipa_edge_args_t, heap,
|
|
|
354 cgraph_edge_max_uid);
|
|
|
355
|
|
|
356 if (VEC_length (ipa_edge_args_t, ipa_edge_args_vector)
|
|
|
357 <= (unsigned) cgraph_edge_max_uid)
|
|
|
358 VEC_safe_grow_cleared (ipa_edge_args_t, heap, ipa_edge_args_vector,
|
|
|
359 cgraph_edge_max_uid + 1);
|
|
|
360 }
|
|
|
361
|
|
|
362 /* Returns true if the array of edge infos is large enough to accommodate an
|
|
|
363 info for EDGE. The main purpose of this function is that debug dumping
|
|
|
364 function can check info availability without causing reallocations. */
|
|
|
365
|
|
|
366 static inline bool
|
|
|
367 ipa_edge_args_info_available_for_edge_p (struct cgraph_edge *edge)
|
|
|
368 {
|
|
|
369 return ((unsigned) edge->uid < VEC_length (ipa_edge_args_t,
|
|
|
370 ipa_edge_args_vector));
|
|
|
371 }
|
|
|
372
|
|
|
373 /* A function list element. It is used to create a temporary worklist used in
|
|
|
374 the propagation stage of IPCP. (can be used for more IPA optimizations) */
|
|
|
375 struct ipa_func_list
|
|
|
376 {
|
|
|
377 struct cgraph_node *node;
|
|
|
378 struct ipa_func_list *next;
|
|
|
379 };
|
|
|
380
|
|
|
381 /* ipa_func_list interface. */
|
|
|
382 struct ipa_func_list *ipa_init_func_list (void);
|
|
|
383 void ipa_push_func_to_list (struct ipa_func_list **, struct cgraph_node *);
|
|
|
384 struct cgraph_node *ipa_pop_func_from_list (struct ipa_func_list **);
|
|
|
385
|
|
|
386 /* Callsite related calculations. */
|
|
|
387 void ipa_compute_jump_functions (struct cgraph_edge *);
|
|
|
388 void ipa_count_arguments (struct cgraph_edge *);
|
|
|
389
|
|
|
390 /* Function formal parameters related computations. */
|
|
|
391 void ipa_initialize_node_params (struct cgraph_node *node);
|
|
|
392 void ipa_detect_param_modifications (struct cgraph_node *);
|
|
|
393 void ipa_analyze_params_uses (struct cgraph_node *);
|
|
|
394 bool ipa_propagate_indirect_call_infos (struct cgraph_edge *cs,
|
|
|
395 VEC (cgraph_edge_p, heap) **new_edges);
|
|
|
396
|
|
|
397 /* Debugging interface. */
|
|
|
398 void ipa_print_node_params (FILE *, struct cgraph_node *node);
|
|
|
399 void ipa_print_all_params (FILE *);
|
|
|
400 void ipa_print_node_jump_functions (FILE *f, struct cgraph_node *node);
|
|
|
401 void ipa_print_all_jump_functions (FILE * f);
|
|
|
402
|
|
|
403 #endif /* IPA_PROP_H */
|
