GCC Middle and Back End API Reference
ipa-inline.h
Go to the documentation of this file.
1 /* Inlining decision heuristics.
2  Copyright (C) 2003-2013 Free Software Foundation, Inc.
3  Contributed by Jan Hubicka
4 
5 This file is part of GCC.
6 
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11 
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16 
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20 
21 #include "ipa-prop.h"
22 
23 /* Representation of inline parameters that do depend on context function is
24  inlined into (i.e. known constant values of function parameters.
25 
26  Conditions that are interesting for function body are collected into CONDS
27  vector. They are of simple for function_param OP VAL, where VAL is
28  IPA invariant. The conditions are then referred by predicates. */
29 
30 typedef struct GTY(()) condition
31  {
32  /* If agg_contents is set, this is the offset from which the used data was
33  loaded. */
35  tree val;
36  int operand_num;
37  ENUM_BITFIELD(tree_code) code : 16;
38  /* Set if the used data were loaded from an aggregate parameter or from
39  data received by reference. */
40  unsigned agg_contents : 1;
41  /* If agg_contents is set, this differentiates between loads from data
42  passed by reference and by value. */
43  unsigned by_ref : 1;
44  } condition;
45 
46 /* Inline hints are reasons why inline heuristics should preffer inlining given
47  function. They are represtented as bitmap of the following values. */
49  /* When inlining turns indirect call into a direct call,
50  it is good idea to do so. */
52  /* Inlining may make loop iterations or loop stride known. It is good idea
53  to do so because it enables loop optimizatoins. */
56  /* Inlining within same strongly connected component of callgraph is often
57  a loss due to increased stack frame usage and prologue setup costs. */
59  /* Inlining functions in strongly connected component is not such a great
60  win. */
61  INLINE_HINT_in_scc = 16,
62  /* If function is declared inline by user, it may be good idea to inline
63  it. */
65  /* Programs are usually still organized for non-LTO compilation and thus
66  if functions are in different modules, inlining may not be so important.
67  */
69  /* If array indexes of loads/stores become known there may be room for
70  further optimization. */
72 };
73 typedef int inline_hints;
74 
75 
77 
78 /* Representation of predicates i.e. formulas using conditions defined
79  above. Predicates are simple logical formulas in conjunctive-disjunctive
80  form.
81 
82  Predicate is array of clauses terminated by 0. Every clause must be true
83  in order to make predicate true.
84  Clauses are represented as bitmaps of conditions. One of conditions
85  must be true in order for clause to be true. */
86 
87 #define MAX_CLAUSES 8
88 typedef unsigned int clause_t;
89 struct GTY(()) predicate
90 {
91  clause_t clause[MAX_CLAUSES + 1];
92 };
93 
94 /* Represnetation of function body size and time depending on the inline
95  context. We keep simple array of record, every containing of predicate
96  and time/size to account.
97 
98  We keep values scaled up, so fractional sizes and times can be
99  accounted. */
100 #define INLINE_SIZE_SCALE 2
101 #define INLINE_TIME_SCALE (CGRAPH_FREQ_BASE * 2)
102 typedef struct GTY(()) size_time_entry
103 {
104  struct predicate predicate;
105  int size;
106  int time;
108 
109 /* Function inlining information. */
110 struct GTY(()) inline_summary
111 {
112  /* Information about the function body itself. */
113 
114  /* Estimated stack frame consumption by the function. */
115  HOST_WIDE_INT estimated_self_stack_size;
116  /* Size of the function body. */
117  int self_size;
118  /* Time of the function body. */
119  int self_time;
121  /* False when there something makes inlining impossible (such as va_arg). */
122  unsigned inlinable : 1;
123 
124  /* Information about function that will result after applying all the
125  inline decisions present in the callgraph. Generally kept up to
126  date only for functions that are not inline clones. */
127 
128  /* Estimated stack frame consumption by the function. */
129  HOST_WIDE_INT estimated_stack_size;
130  /* Expected offset of the stack frame of inlined function. */
131  HOST_WIDE_INT stack_frame_offset;
132  /* Estimated size of the function after inlining. */
133  int time;
134  int size;
135 
136  /* Conditional size/time information. The summaries are being
137  merged during inlining. */
138  conditions conds;
140 
141  /* Predicate on when some loop in the function becomes to have known
142  bounds. */
143  struct predicate * GTY((skip)) loop_iterations;
144  /* Predicate on when some loop in the function becomes to have known
145  stride. */
146  struct predicate * GTY((skip)) loop_stride;
147  /* Predicate on when some array indexes become constants. */
148  struct predicate * GTY((skip)) array_index;
149  /* Estimated growth for inlining all copies of the function before start
150  of small functions inlining.
151  This value will get out of date as the callers are duplicated, but
152  using up-to-date value in the badness metric mean a lot of extra
153  expenses. */
154  int growth;
155  /* Number of SCC on the beginning of inlining process. */
156  int scc_no;
157 };
160 typedef struct inline_summary inline_summary_t;
161 extern GTY(()) vec<inline_summary_t, va_gc> *inline_summary_vec;
162 
163 /* Information kept about parameter of call site. */
165 {
166  /* REG_BR_PROB_BASE based probability that parameter will change in between
167  two invocation of the calls.
168  I.e. loop invariant parameters
169  REG_BR_PROB_BASE/estimated_iterations and regular
170  parameters REG_BR_PROB_BASE.
171 
172  Value 0 is reserved for compile time invariants. */
173  int change_prob;
174 };
176 
177 /* Information kept about callgraph edges. */
178 struct inline_edge_summary
179 {
180  /* Estimated size and time of the call statement. */
181  int call_stmt_size;
182  int call_stmt_time;
183  /* Depth of loop nest, 0 means no nesting. */
184  unsigned short int loop_depth;
185  struct predicate *predicate;
186  /* Array indexed by parameters.
187  0 means that parameter change all the time, REG_BR_PROB_BASE means
188  that parameter is constant. */
190 };
194 
195 typedef struct edge_growth_cache_entry
196 {
197  int time, size;
198  inline_hints hints;
200 
203 
204 /* In ipa-inline-analysis.c */
205 void debug_inline_summary (struct cgraph_node *);
206 void dump_inline_summaries (FILE *f);
207 void dump_inline_summary (FILE *f, struct cgraph_node *node);
209 void inline_generate_summary (void);
210 void inline_read_summary (void);
211 void inline_write_summary (void);
213 void initialize_inline_failed (struct cgraph_edge *);
214 int estimate_time_after_inlining (struct cgraph_node *, struct cgraph_edge *);
215 int estimate_size_after_inlining (struct cgraph_node *, struct cgraph_edge *);
219  int *, int *, inline_hints *);
222 void inline_update_overall_summary (struct cgraph_node *node);
227 void free_growth_caches (void);
228 void compute_inline_parameters (struct cgraph_node *, bool);
229 bool speculation_useful_p (struct cgraph_edge *e, bool anticipate_inlining);
230 
231 /* In ipa-inline-transform.c */
232 bool inline_call (struct cgraph_edge *, bool, vec<cgraph_edge_p> *, int *, bool);
233 unsigned int inline_transform (struct cgraph_node *);
234 void clone_inlined_nodes (struct cgraph_edge *e, bool, bool, int *);
236 extern int ncalls_inlined;
237 extern int nfunctions_inlined;
238 
239 static inline struct inline_summary *
240 inline_summary (struct cgraph_node *node)
241 {
242  return &(*inline_summary_vec)[node->uid];
243 }
244 
245 static inline struct inline_edge_summary *
247 {
248  return &inline_edge_summary_vec[edge->uid];
249 }
250 
251 /* Return estimated unit growth after inlning all calls to NODE.
252  Quick accesors to the inline growth caches.
253  For convenience we keep zero 0 as unknown. Because growth
254  can be both positive and negative, we simply increase positive
255  growths by 1. */
256 static inline int
257 estimate_growth (struct cgraph_node *node)
258 {
259  int ret;
260  if ((int)node_growth_cache.length () <= node->uid
261  || !(ret = node_growth_cache[node->uid]))
262  return do_estimate_growth (node);
263  return ret - (ret > 0);
264 }
265 
266 
267 /* Return estimated size of the inline sequence of EDGE. */
268 
269 static inline int
271 {
272  int ret;
273  if ((int)edge_growth_cache.length () <= edge->uid
274  || !(ret = edge_growth_cache[edge->uid].size))
275  return do_estimate_edge_size (edge);
276  return ret - (ret > 0);
277 }
278 
279 /* Return estimated callee growth after inlining EDGE. */
280 
281 static inline int
282 estimate_edge_growth (struct cgraph_edge *edge)
283 {
284 #ifdef ENABLE_CHECKING
286 #endif
287  return (estimate_edge_size (edge)
289 }
290 
291 /* Return estimated callee runtime increase after inlning
292  EDGE. */
293 
294 static inline int
295 estimate_edge_time (struct cgraph_edge *edge)
296 {
297  int ret;
298  if ((int)edge_growth_cache.length () <= edge->uid
299  || !(ret = edge_growth_cache[edge->uid].time))
300  return do_estimate_edge_time (edge);
301  return ret - (ret > 0);
302 }
303 
304 
305 /* Return estimated callee runtime increase after inlning
306  EDGE. */
307 
308 static inline inline_hints
309 estimate_edge_hints (struct cgraph_edge *edge)
310 {
312  if ((int)edge_growth_cache.length () <= edge->uid
313  || !(ret = edge_growth_cache[edge->uid].hints))
314  return do_estimate_edge_hints (edge);
315  return ret - 1;
316 }
317 
318 
319 /* Reset cached value for NODE. */
320 
321 static inline void
323 {
324  if ((int)node_growth_cache.length () > node->uid)
325  node_growth_cache[node->uid] = 0;
326 }
327 
328 /* Reset cached value for EDGE. */
329 
330 static inline void
332 {
333  if ((int)edge_growth_cache.length () > edge->uid)
334  {
335  struct edge_growth_cache_entry zero = {0, 0, 0};
336  edge_growth_cache[edge->uid] = zero;
337  }
338 }