ipa-inline.h revision 1.1.1.1
1/* Inlining decision heuristics. 2 Copyright (C) 2003-2013 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#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 30typedef struct GTY(()) condition 31 { 32 /* If agg_contents is set, this is the offset from which the used data was 33 loaded. */ 34 HOST_WIDE_INT offset; 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. */ 48enum inline_hints_vals { 49 /* When inlining turns indirect call into a direct call, 50 it is good idea to do so. */ 51 INLINE_HINT_indirect_call = 1, 52 /* Inlining may make loop iterations or loop stride known. It is good idea 53 to do so because it enables loop optimizatoins. */ 54 INLINE_HINT_loop_iterations = 2, 55 INLINE_HINT_loop_stride = 4, 56 /* Inlining withing same strongly connected component of callgraph is often 57 a loss due to increased stack frame usage and prologue setup costs. */ 58 INLINE_HINT_same_scc = 8, 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. */ 64 INLINE_HINT_declared_inline = 32, 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 */ 68 INLINE_HINT_cross_module = 64, 69 /* If array indexes of loads/stores become known there may be room for 70 futher optimization. */ 71 INLINE_HINT_array_index = 128 72}; 73typedef int inline_hints; 74 75 76typedef vec<condition, va_gc> *conditions; 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 88typedef unsigned int clause_t; 89struct 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) 102typedef struct GTY(()) size_time_entry 103{ 104 struct predicate predicate; 105 int size; 106 int time; 107} size_time_entry; 108 109/* Function inlining information. */ 110struct 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; 120 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; 139 vec<size_time_entry, va_gc> *entry; 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 beggining of inlining process. */ 156 int scc_no; 157}; 158 159 160typedef struct inline_summary inline_summary_t; 161extern GTY(()) vec<inline_summary_t, va_gc> *inline_summary_vec; 162 163/* Information kept about parameter of call site. */ 164struct inline_param_summary 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}; 175typedef struct inline_param_summary inline_param_summary_t; 176 177/* Information kept about callgraph edges. */ 178struct 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. */ 189 vec<inline_param_summary_t> param; 190}; 191 192typedef struct inline_edge_summary inline_edge_summary_t; 193extern vec<inline_edge_summary_t> inline_edge_summary_vec; 194 195typedef struct edge_growth_cache_entry 196{ 197 int time, size; 198 inline_hints hints; 199} edge_growth_cache_entry; 200 201extern vec<int> node_growth_cache; 202extern vec<edge_growth_cache_entry> edge_growth_cache; 203 204/* In ipa-inline-analysis.c */ 205void debug_inline_summary (struct cgraph_node *); 206void dump_inline_summaries (FILE *f); 207void dump_inline_summary (FILE *f, struct cgraph_node *node); 208void dump_inline_hints (FILE *f, inline_hints); 209void inline_generate_summary (void); 210void inline_read_summary (void); 211void inline_write_summary (void); 212void inline_free_summary (void); 213void initialize_inline_failed (struct cgraph_edge *); 214int estimate_time_after_inlining (struct cgraph_node *, struct cgraph_edge *); 215int estimate_size_after_inlining (struct cgraph_node *, struct cgraph_edge *); 216void estimate_ipcp_clone_size_and_time (struct cgraph_node *, 217 vec<tree>, vec<tree>, 218 vec<ipa_agg_jump_function_p>, 219 int *, int *, inline_hints *); 220int do_estimate_growth (struct cgraph_node *); 221void inline_merge_summary (struct cgraph_edge *edge); 222void inline_update_overall_summary (struct cgraph_node *node); 223int do_estimate_edge_size (struct cgraph_edge *edge); 224int do_estimate_edge_time (struct cgraph_edge *edge); 225inline_hints do_estimate_edge_hints (struct cgraph_edge *edge); 226void initialize_growth_caches (void); 227void free_growth_caches (void); 228void compute_inline_parameters (struct cgraph_node *, bool); 229 230/* In ipa-inline-transform.c */ 231bool inline_call (struct cgraph_edge *, bool, vec<cgraph_edge_p> *, int *, bool); 232unsigned int inline_transform (struct cgraph_node *); 233void clone_inlined_nodes (struct cgraph_edge *e, bool, bool, int *); 234 235extern int ncalls_inlined; 236extern int nfunctions_inlined; 237 238static inline struct inline_summary * 239inline_summary (struct cgraph_node *node) 240{ 241 return &(*inline_summary_vec)[node->uid]; 242} 243 244static inline struct inline_edge_summary * 245inline_edge_summary (struct cgraph_edge *edge) 246{ 247 return &inline_edge_summary_vec[edge->uid]; 248} 249 250/* Return estimated unit growth after inlning all calls to NODE. 251 Quick accesors to the inline growth caches. 252 For convenience we keep zero 0 as unknown. Because growth 253 can be both positive and negative, we simply increase positive 254 growths by 1. */ 255static inline int 256estimate_growth (struct cgraph_node *node) 257{ 258 int ret; 259 if ((int)node_growth_cache.length () <= node->uid 260 || !(ret = node_growth_cache[node->uid])) 261 return do_estimate_growth (node); 262 return ret - (ret > 0); 263} 264 265 266/* Return estimated size of the inline sequence of EDGE. */ 267 268static inline int 269estimate_edge_size (struct cgraph_edge *edge) 270{ 271 int ret; 272 if ((int)edge_growth_cache.length () <= edge->uid 273 || !(ret = edge_growth_cache[edge->uid].size)) 274 return do_estimate_edge_size (edge); 275 return ret - (ret > 0); 276} 277 278/* Return estimated callee growth after inlining EDGE. */ 279 280static inline int 281estimate_edge_growth (struct cgraph_edge *edge) 282{ 283#ifdef ENABLE_CHECKING 284 gcc_checking_assert (inline_edge_summary (edge)->call_stmt_size); 285#endif 286 return (estimate_edge_size (edge) 287 - inline_edge_summary (edge)->call_stmt_size); 288} 289 290/* Return estimated callee runtime increase after inlning 291 EDGE. */ 292 293static inline int 294estimate_edge_time (struct cgraph_edge *edge) 295{ 296 int ret; 297 if ((int)edge_growth_cache.length () <= edge->uid 298 || !(ret = edge_growth_cache[edge->uid].time)) 299 return do_estimate_edge_time (edge); 300 return ret - (ret > 0); 301} 302 303 304/* Return estimated callee runtime increase after inlning 305 EDGE. */ 306 307static inline inline_hints 308estimate_edge_hints (struct cgraph_edge *edge) 309{ 310 inline_hints ret; 311 if ((int)edge_growth_cache.length () <= edge->uid 312 || !(ret = edge_growth_cache[edge->uid].hints)) 313 return do_estimate_edge_hints (edge); 314 return ret - 1; 315} 316 317 318/* Reset cached value for NODE. */ 319 320static inline void 321reset_node_growth_cache (struct cgraph_node *node) 322{ 323 if ((int)node_growth_cache.length () > node->uid) 324 node_growth_cache[node->uid] = 0; 325} 326 327/* Reset cached value for EDGE. */ 328 329static inline void 330reset_edge_growth_cache (struct cgraph_edge *edge) 331{ 332 if ((int)edge_growth_cache.length () > edge->uid) 333 { 334 struct edge_growth_cache_entry zero = {0, 0, 0}; 335 edge_growth_cache[edge->uid] = zero; 336 } 337} 338