1 /* Inlining decision heuristics.
2 Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Representation of inline parameters that do depend on context function is
23 inlined into (i.e. known constant values of function parameters.
25 Conditions that are interesting for function body are collected into CONDS
26 vector. They are of simple for function_param OP VAL, where VAL is
27 IPA invariant. The conditions are then refered by predicates. */
29 typedef struct GTY(()) condition
36 DEF_VEC_O (condition
);
37 DEF_VEC_ALLOC_O (condition
, gc
);
39 typedef VEC(condition
,gc
) *conditions
;
41 /* Representation of predicates i.e. formulas using conditions defined
42 above. Predicates are simple logical formulas in conjunctive-disjunctive
45 Predicate is array of clauses terminated by 0. Every clause must be true
46 in order to make predicate true.
47 Clauses are represented as bitmaps of conditions. One of conditions
48 must be true in order for clause to be true. */
52 struct GTY(()) predicate
54 clause_t clause
[MAX_CLAUSES
+ 1];
57 /* Represnetation of function body size and time depending on the inline
58 context. We keep simple array of record, every containing of predicate
59 and time/size to account.
61 We keep values scaled up, so fractional sizes and times can be
63 #define INLINE_SIZE_SCALE 2
64 #define INLINE_TIME_SCALE (CGRAPH_FREQ_BASE * 2)
65 typedef struct GTY(()) size_time_entry
67 struct predicate predicate
;
71 DEF_VEC_O (size_time_entry
);
72 DEF_VEC_ALLOC_O (size_time_entry
, gc
);
74 /* Function inlining information. */
75 struct GTY(()) inline_summary
77 /* Information about the function body itself. */
79 /* Estimated stack frame consumption by the function. */
80 HOST_WIDE_INT estimated_self_stack_size
;
81 /* Size of the function body. */
83 /* Time of the function body. */
86 /* False when there something makes inlining impossible (such as va_arg). */
87 unsigned inlinable
: 1;
88 /* False when there something makes versioning impossible.
89 Currently computed and used only by ipa-cp. */
90 unsigned versionable
: 1;
92 /* Information about function that will result after applying all the
93 inline decisions present in the callgraph. Generally kept up to
94 date only for functions that are not inline clones. */
96 /* Estimated stack frame consumption by the function. */
97 HOST_WIDE_INT estimated_stack_size
;
98 /* Expected offset of the stack frame of inlined function. */
99 HOST_WIDE_INT stack_frame_offset
;
100 /* Estimated size of the function after inlining. */
104 /* Conditional size/time information. The summaries are being
105 merged during inlining. */
107 VEC(size_time_entry
,gc
) *entry
;
110 typedef struct inline_summary inline_summary_t
;
111 DEF_VEC_O(inline_summary_t
);
112 DEF_VEC_ALLOC_O(inline_summary_t
,gc
);
113 extern GTY(()) VEC(inline_summary_t
,gc
) *inline_summary_vec
;
115 /* Information kept about callgraph edges. */
116 struct inline_edge_summary
118 /* Estimated size and time of the call statement. */
121 /* Depth of loop nest, 0 means no nesting. */
122 unsigned short int loop_depth
;
123 struct predicate
*predicate
;
126 typedef struct inline_edge_summary inline_edge_summary_t
;
127 DEF_VEC_O(inline_edge_summary_t
);
128 DEF_VEC_ALLOC_O(inline_edge_summary_t
,heap
);
129 extern VEC(inline_edge_summary_t
,heap
) *inline_edge_summary_vec
;
131 typedef struct edge_growth_cache_entry
134 } edge_growth_cache_entry
;
135 DEF_VEC_O(edge_growth_cache_entry
);
136 DEF_VEC_ALLOC_O(edge_growth_cache_entry
,heap
);
138 extern VEC(int,heap
) *node_growth_cache
;
139 extern VEC(edge_growth_cache_entry
,heap
) *edge_growth_cache
;
141 /* In ipa-inline-analysis.c */
142 void debug_inline_summary (struct cgraph_node
*);
143 void dump_inline_summaries (FILE *f
);
144 void inline_generate_summary (void);
145 void inline_read_summary (void);
146 void inline_write_summary (cgraph_node_set
, varpool_node_set
);
147 void inline_free_summary (void);
148 void initialize_inline_failed (struct cgraph_edge
*);
149 int estimate_time_after_inlining (struct cgraph_node
*, struct cgraph_edge
*);
150 int estimate_size_after_inlining (struct cgraph_node
*, struct cgraph_edge
*);
151 int do_estimate_growth (struct cgraph_node
*);
152 void inline_merge_summary (struct cgraph_edge
*edge
);
153 int do_estimate_edge_growth (struct cgraph_edge
*edge
);
154 int do_estimate_edge_time (struct cgraph_edge
*edge
);
155 void initialize_growth_caches (void);
156 void free_growth_caches (void);
157 void compute_inline_parameters (struct cgraph_node
*, bool);
159 /* In ipa-inline-transform.c */
160 bool inline_call (struct cgraph_edge
*, bool, VEC (cgraph_edge_p
, heap
) **, int *);
161 unsigned int inline_transform (struct cgraph_node
*);
162 void clone_inlined_nodes (struct cgraph_edge
*e
, bool, bool, int *);
164 extern int ncalls_inlined
;
165 extern int nfunctions_inlined
;
167 static inline struct inline_summary
*
168 inline_summary (struct cgraph_node
*node
)
170 return VEC_index (inline_summary_t
, inline_summary_vec
, node
->uid
);
173 static inline struct inline_edge_summary
*
174 inline_edge_summary (struct cgraph_edge
*edge
)
176 return VEC_index (inline_edge_summary_t
,
177 inline_edge_summary_vec
, edge
->uid
);
180 /* Return estimated unit growth after inlning all calls to NODE.
181 Quick accesors to the inline growth caches.
182 For convenience we keep zero 0 as unknown. Because growth
183 can be both positive and negative, we simply increase positive
186 estimate_growth (struct cgraph_node
*node
)
189 if ((int)VEC_length (int, node_growth_cache
) <= node
->uid
190 || !(ret
= VEC_index (int, node_growth_cache
, node
->uid
)))
191 return do_estimate_growth (node
);
192 return ret
- (ret
> 0);
196 /* Return estimated callee growth after inlining EDGE. */
199 estimate_edge_growth (struct cgraph_edge
*edge
)
202 if ((int)VEC_length (edge_growth_cache_entry
, edge_growth_cache
) <= edge
->uid
203 || !(ret
= VEC_index (edge_growth_cache_entry
,
206 return do_estimate_edge_growth (edge
);
207 return ret
- (ret
> 0);
211 /* Return estimated callee runtime increase after inlning
215 estimate_edge_time (struct cgraph_edge
*edge
)
218 if ((int)VEC_length (edge_growth_cache_entry
, edge_growth_cache
) <= edge
->uid
219 || !(ret
= VEC_index (edge_growth_cache_entry
,
222 return do_estimate_edge_time (edge
);
223 return ret
- (ret
> 0);
227 /* Reset cached value for NODE. */
230 reset_node_growth_cache (struct cgraph_node
*node
)
232 if ((int)VEC_length (int, node_growth_cache
) > node
->uid
)
233 VEC_replace (int, node_growth_cache
, node
->uid
, 0);
236 /* Reset cached value for EDGE. */
239 reset_edge_growth_cache (struct cgraph_edge
*edge
)
241 if ((int)VEC_length (edge_growth_cache_entry
, edge_growth_cache
) > edge
->uid
)
243 struct edge_growth_cache_entry zero
= {0, 0};
244 VEC_replace (edge_growth_cache_entry
, edge_growth_cache
, edge
->uid
, &zero
);