1/* IPA function body analysis.
2 Copyright (C) 2003-2023 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#ifndef GCC_IPA_SUMMARY_H
22#define GCC_IPA_SUMMARY_H
23
24#include "sreal.h"
25#include "ipa-predicate.h"
26
27
28/* Hints are reasons why IPA heuristics should prefer specializing given
29 function. They are represented as bitmap of the following values. */
30enum ipa_hints_vals {
31 /* When specialization turns indirect call into a direct call,
32 it is good idea to do so. */
33 INLINE_HINT_indirect_call = 1,
34 /* Inlining may make loop iterations or loop stride known. It is good idea
35 to do so because it enables loop optimizations. */
36 INLINE_HINT_loop_iterations = 2,
37 INLINE_HINT_loop_stride = 4,
38 /* Inlining within same strongly connected component of callgraph is often
39 a loss due to increased stack frame usage and prologue setup costs. */
40 INLINE_HINT_same_scc = 8,
41 /* Inlining functions in strongly connected component is not such a great
42 win. */
43 INLINE_HINT_in_scc = 16,
44 /* If function is declared inline by user, it may be good idea to inline
45 it. Set by simple_edge_hints in ipa-inline-analysis.cc. */
46 INLINE_HINT_declared_inline = 32,
47 /* Programs are usually still organized for non-LTO compilation and thus
48 if functions are in different modules, inlining may not be so important.
49 Set by simple_edge_hints in ipa-inline-analysis.cc. */
50 INLINE_HINT_cross_module = 64,
51 /* We know that the callee is hot by profile. */
52 INLINE_HINT_known_hot = 128,
53 /* There is builtin_constant_p dependent on parameter which is usually
54 a strong hint to inline. */
55 INLINE_HINT_builtin_constant_p = 256
56};
57
58typedef int ipa_hints;
59
60/* Simple description of whether a memory load or a condition refers to a load
61 from an aggregate and if so, how and where from in the aggregate.
62 Individual fields have the same meaning like fields with the same name in
63 struct condition. */
64
65struct agg_position_info
66{
67 HOST_WIDE_INT offset;
68 bool agg_contents;
69 bool by_ref;
70};
71
72/* Representation of function body size and time depending on the call
73 context. We keep simple array of record, every containing of predicate
74 and time/size to account. */
75class size_time_entry
76{
77public:
78 /* Predicate for code to be executed. */
79 ipa_predicate exec_predicate;
80 /* Predicate for value to be constant and optimized out in a specialized copy.
81 When deciding on specialization this makes it possible to see how much
82 the executed code paths will simplify. */
83 ipa_predicate nonconst_predicate;
84 int size;
85 sreal time;
86};
87
88/* Summary about function and stack frame sizes. We keep this info
89 for inline clones and also for WPA streaming. For this reason this is not
90 part of ipa_fn_summary which exists only for offline functions. */
91class ipa_size_summary
92{
93public:
94 /* Estimated stack frame consumption by the function. */
95 HOST_WIDE_INT estimated_self_stack_size;
96 /* Size of the function body. */
97 int self_size;
98 /* Estimated size of the function after inlining. */
99 int size;
100
101 ipa_size_summary ()
102 : estimated_self_stack_size (0), self_size (0), size (0)
103 {
104 }
105};
106
107/* Structure to capture how frequently some interesting events occur given a
108 particular predicate. The structure is used to estimate how often we
109 encounter loops with known iteration count or stride in various
110 contexts. */
111
112struct GTY(()) ipa_freqcounting_predicate
113{
114 /* The described event happens with this frequency... */
115 sreal freq;
116 /* ...when this predicate evaluates to false. */
117 ipa_predicate * GTY((skip)) predicate;
118};
119
120/* Function inlining information. */
121class GTY(()) ipa_fn_summary
122{
123public:
124 /* Keep all field empty so summary dumping works during its computation.
125 This is useful for debugging. */
126 ipa_fn_summary ()
127 : min_size (0),
128 inlinable (false), single_caller (false),
129 fp_expressions (false), safe_to_inline_to_always_inline (0),
130 target_info (0), estimated_stack_size (false),
131 time (0), conds (NULL),
132 size_time_table (), call_size_time_table (vNULL),
133 loop_iterations (NULL), loop_strides (NULL),
134 builtin_constant_p_parms (vNULL),
135 growth (0), scc_no (0)
136 {
137 }
138
139 /* Copy constructor. */
140 ipa_fn_summary (const ipa_fn_summary &s)
141 : min_size (s.min_size),
142 inlinable (s.inlinable), single_caller (s.single_caller),
143 fp_expressions (s.fp_expressions),
144 target_info (s.target_info),
145 estimated_stack_size (s.estimated_stack_size),
146 time (s.time), conds (s.conds), size_time_table (),
147 call_size_time_table (vNULL),
148 loop_iterations (s.loop_iterations), loop_strides (s.loop_strides),
149 builtin_constant_p_parms (s.builtin_constant_p_parms),
150 growth (s.growth), scc_no (s.scc_no)
151 {}
152
153 /* Default constructor. */
154 ~ipa_fn_summary ();
155
156 /* Information about the function body itself. */
157
158 /* Minimal size increase after inlining. */
159 int min_size;
160
161 /* False when there something makes inlining impossible (such as va_arg). */
162 unsigned inlinable : 1;
163 /* True wen there is only one caller of the function before small function
164 inlining. */
165 unsigned int single_caller : 1;
166 /* True if function contains any floating point expressions. */
167 unsigned int fp_expressions : 1;
168 /* Cache for analysis of can_early_inline_edge_p. */
169 unsigned int safe_to_inline_to_always_inline : 2;
170 /* Like fp_expressions field above, but it's to hold some target specific
171 information, such as some target specific isa flags. Note that for
172 offloading target compilers, this field isn't streamed. */
173 unsigned int target_info;
174
175 /* Information about function that will result after applying all the
176 inline decisions present in the callgraph. Generally kept up to
177 date only for functions that are not inline clones. */
178
179 /* Estimated stack frame consumption by the function. */
180 HOST_WIDE_INT estimated_stack_size;
181 /* Estimated runtime of function after inlining. */
182 sreal GTY((skip)) time;
183
184 /* Conditional size/time information. The summaries are being
185 merged during inlining. */
186 conditions conds;
187 /* Normal code is accounted in size_time_table, while calls are
188 accounted in call_size_time_table. This is because calls
189 are often adjusted by IPA optimizations and thus this summary
190 is generated from call summary information when needed. */
191 auto_vec<size_time_entry> GTY((skip)) size_time_table;
192 /* Unlike size_time_table that is initialized for all summaries
193 call_size_time_table is allocated only for functions with
194 many calls. Use effecient vl_ptr storage. */
195 vec<size_time_entry, va_heap, vl_ptr> GTY((skip)) call_size_time_table;
196
197 /* Predicates on when some loops in the function can have known bounds. */
198 vec<ipa_freqcounting_predicate, va_gc> *loop_iterations;
199 /* Predicates on when some loops in the function can have known strides. */
200 vec<ipa_freqcounting_predicate, va_gc> *loop_strides;
201 /* Parameters tested by builtin_constant_p. */
202 vec<int, va_heap, vl_ptr> GTY((skip)) builtin_constant_p_parms;
203 /* Estimated growth for inlining all copies of the function before start
204 of small functions inlining.
205 This value will get out of date as the callers are duplicated, but
206 using up-to-date value in the badness metric mean a lot of extra
207 expenses. */
208 int growth;
209 /* Number of SCC on the beginning of inlining process. */
210 int scc_no;
211
212 /* Record time and size under given predicates. */
213 void account_size_time (int, sreal, const ipa_predicate &,
214 const ipa_predicate &,
215 bool call = false);
216
217 /* We keep values scaled up, so fractional sizes can be accounted. */
218 static const int size_scale = 2;
219 /* Maximal size of size_time_table before we start to be conservative. */
220 static const int max_size_time_table_size = 256;
221};
222
223class GTY((user)) ipa_fn_summary_t:
224 public fast_function_summary <ipa_fn_summary *, va_gc>
225{
226public:
227 ipa_fn_summary_t (symbol_table *symtab):
228 fast_function_summary <ipa_fn_summary *, va_gc> (symtab) {}
229
230 static ipa_fn_summary_t *create_ggc (symbol_table *symtab)
231 {
232 class ipa_fn_summary_t *summary
233 = new (ggc_alloc_no_dtor<ipa_fn_summary_t> ()) ipa_fn_summary_t (symtab);
234 summary->disable_insertion_hook ();
235 return summary;
236 }
237
238 /* Remove ipa_fn_summary for all callees of NODE. */
239 void remove_callees (cgraph_node *node);
240
241 void insert (cgraph_node *, ipa_fn_summary *) final override;
242 void remove (cgraph_node *node, ipa_fn_summary *) final override
243 {
244 remove_callees (node);
245 }
246
247 void duplicate (cgraph_node *src, cgraph_node *dst,
248 ipa_fn_summary *src_data, ipa_fn_summary *dst_data)
249 final override;
250};
251
252extern GTY(()) fast_function_summary <ipa_fn_summary *, va_gc>
253 *ipa_fn_summaries;
254
255class ipa_size_summary_t:
256 public fast_function_summary <ipa_size_summary *, va_heap>
257{
258public:
259 ipa_size_summary_t (symbol_table *symtab):
260 fast_function_summary <ipa_size_summary *, va_heap> (symtab)
261 {
262 disable_insertion_hook ();
263 }
264
265 void duplicate (cgraph_node *, cgraph_node *,
266 ipa_size_summary *src_data,
267 ipa_size_summary *dst_data) final override
268 {
269 *dst_data = *src_data;
270 }
271};
272extern fast_function_summary <ipa_size_summary *, va_heap>
273 *ipa_size_summaries;
274
275/* Information kept about callgraph edges. */
276class ipa_call_summary
277{
278public:
279 /* Keep all field empty so summary dumping works during its computation.
280 This is useful for debugging. */
281 ipa_call_summary ()
282 : predicate (NULL), param (vNULL), call_stmt_size (0), call_stmt_time (0),
283 loop_depth (0), is_return_callee_uncaptured (false)
284 {
285 }
286
287 /* Copy constructor. */
288 ipa_call_summary (const ipa_call_summary &s):
289 predicate (s.predicate), param (s.param), call_stmt_size (s.call_stmt_size),
290 call_stmt_time (s.call_stmt_time), loop_depth (s.loop_depth),
291 is_return_callee_uncaptured (s.is_return_callee_uncaptured)
292 {
293 }
294
295 /* Default destructor. */
296 ~ipa_call_summary ();
297
298 ipa_predicate *predicate;
299 /* Vector indexed by parameters. */
300 vec<inline_param_summary> param;
301 /* Estimated size and time of the call statement. */
302 int call_stmt_size;
303 int call_stmt_time;
304 /* Depth of loop nest, 0 means no nesting. */
305 unsigned int loop_depth;
306 /* Indicates whether the caller returns the value of it's callee. */
307 bool is_return_callee_uncaptured;
308};
309
310class ipa_call_summary_t: public fast_call_summary <ipa_call_summary *, va_heap>
311{
312public:
313 ipa_call_summary_t (symbol_table *symtab):
314 fast_call_summary <ipa_call_summary *, va_heap> (symtab) {}
315
316 /* Hook that is called by summary when an edge is duplicated. */
317 void duplicate (cgraph_edge *src, cgraph_edge *dst,
318 ipa_call_summary *src_data,
319 ipa_call_summary *dst_data) final override;
320};
321
322/* Estimated execution times, code sizes and other information about the
323 code executing a call described by ipa_call_context. */
324
325struct ipa_call_estimates
326{
327 /* Estimated size needed to execute call in the given context. */
328 int size;
329
330 /* Minimal size needed for the call that is + independent on the call context
331 and can be used for fast estimates. */
332 int min_size;
333
334 /* Estimated time needed to execute call in the given context. */
335 sreal time;
336
337 /* Estimated time needed to execute the function when not ignoring
338 computations known to be constant in this context. */
339 sreal nonspecialized_time;
340
341 /* Further discovered reasons why to inline or specialize the give calls. */
342 ipa_hints hints;
343
344 /* Frequency how often a loop with known number of iterations is encountered.
345 Calculated with hints. */
346 sreal loops_with_known_iterations;
347
348 /* Frequency how often a loop with known strides is encountered. Calculated
349 with hints. */
350 sreal loops_with_known_strides;
351};
352
353class ipa_cached_call_context;
354
355/* This object describe a context of call. That is a summary of known
356 information about its parameters. Main purpose of this context is
357 to give more realistic estimations of function runtime, size and
358 inline hints. */
359class ipa_call_context
360{
361public:
362 ipa_call_context (cgraph_node *node,
363 clause_t possible_truths,
364 clause_t nonspec_possible_truths,
365 vec<inline_param_summary> inline_param_summary,
366 ipa_auto_call_arg_values *arg_values);
367 ipa_call_context ()
368 : m_node(NULL)
369 {
370 }
371 void estimate_size_and_time (ipa_call_estimates *estimates,
372 bool est_times = true, bool est_hints = true);
373 bool equal_to (const ipa_call_context &);
374 bool exists_p ()
375 {
376 return m_node != NULL;
377 }
378private:
379 /* Called function. */
380 cgraph_node *m_node;
381 /* Clause describing what predicate conditionals can be satisfied
382 in this context if function is inlined/specialized. */
383 clause_t m_possible_truths;
384 /* Clause describing what predicate conditionals can be satisfied
385 in this context if function is kept offline. */
386 clause_t m_nonspec_possible_truths;
387 /* Inline summary maintains info about change probabilities. */
388 vec<inline_param_summary> m_inline_param_summary;
389
390 /* Even after having calculated clauses, the information about argument
391 values is used to resolve indirect calls. */
392 ipa_call_arg_values m_avals;
393
394 friend ipa_cached_call_context;
395};
396
397/* Variant of ipa_call_context that is stored in a cache over a longer period
398 of time. */
399
400class ipa_cached_call_context : public ipa_call_context
401{
402public:
403 void duplicate_from (const ipa_call_context &ctx);
404 void release ();
405};
406
407extern fast_call_summary <ipa_call_summary *, va_heap> *ipa_call_summaries;
408
409/* In ipa-fnsummary.cc */
410void ipa_debug_fn_summary (struct cgraph_node *);
411void ipa_dump_fn_summaries (FILE *f);
412void ipa_dump_fn_summary (FILE *f, struct cgraph_node *node);
413void ipa_dump_hints (FILE *f, ipa_hints);
414void ipa_free_fn_summary (void);
415void ipa_free_size_summary (void);
416void inline_analyze_function (struct cgraph_node *node);
417void estimate_ipcp_clone_size_and_time (struct cgraph_node *node,
418 ipa_auto_call_arg_values *avals,
419 ipa_call_estimates *estimates);
420void ipa_merge_fn_summary_after_inlining (struct cgraph_edge *edge);
421void ipa_update_overall_fn_summary (struct cgraph_node *node, bool reset = true);
422void compute_fn_summary (struct cgraph_node *, bool);
423bool refs_local_or_readonly_memory_p (tree);
424bool points_to_local_or_readonly_memory_p (tree);
425
426
427void evaluate_properties_for_edge (struct cgraph_edge *e,
428 bool inline_p,
429 clause_t *clause_ptr,
430 clause_t *nonspec_clause_ptr,
431 ipa_auto_call_arg_values *avals,
432 bool compute_contexts);
433
434void ipa_fnsummary_cc_finalize (void);
435HOST_WIDE_INT ipa_get_stack_frame_offset (struct cgraph_node *node);
436void ipa_remove_from_growth_caches (struct cgraph_edge *edge);
437
438/* Return true if EDGE is a cross module call. */
439
440inline bool
441cross_module_call_p (struct cgraph_edge *edge)
442{
443 /* Here we do not want to walk to alias target becuase ICF may create
444 cross-unit aliases. */
445 if (edge->caller->unit_id == edge->callee->unit_id)
446 return false;
447 /* If the call is to a (former) comdat function or s symbol with mutiple
448 extern inline definitions then treat is as in-module call. */
449 if (edge->callee->merged_extern_inline || edge->callee->merged_comdat
450 || DECL_COMDAT (edge->callee->decl))
451 return false;
452 return true;
453}
454
455#endif /* GCC_IPA_FNSUMMARY_H */
456

source code of gcc/ipa-fnsummary.h