1/* Inlining decision heuristics. 2 Copyright (C) 2003-2015 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_INLINE_H 22#define GCC_IPA_INLINE_H 23 24 25/* Representation of inline parameters that do depend on context function is 26 inlined into (i.e. known constant values of function parameters. 27 28 Conditions that are interesting for function body are collected into CONDS 29 vector. They are of simple for function_param OP VAL, where VAL is 30 IPA invariant. The conditions are then referred by predicates. */ 31 32struct GTY(()) condition 33{ 34 /* If agg_contents is set, this is the offset from which the used data was 35 loaded. */ 36 HOST_WIDE_INT offset; 37 /* Size of the access reading the data (or the PARM_DECL SSA_NAME). */ 38 HOST_WIDE_INT size; 39 tree val; 40 int operand_num; 41 ENUM_BITFIELD(tree_code) code : 16; 42 /* Set if the used data were loaded from an aggregate parameter or from 43 data received by reference. */ 44 unsigned agg_contents : 1; 45 /* If agg_contents is set, this differentiates between loads from data 46 passed by reference and by value. */ 47 unsigned by_ref : 1; 48}; 49 50/* Inline hints are reasons why inline heuristics should preffer inlining given 51 function. They are represtented as bitmap of the following values. */ 52enum inline_hints_vals { 53 /* When inlining turns indirect call into a direct call, 54 it is good idea to do so. */ 55 INLINE_HINT_indirect_call = 1, 56 /* Inlining may make loop iterations or loop stride known. It is good idea 57 to do so because it enables loop optimizatoins. */ 58 INLINE_HINT_loop_iterations = 2, 59 INLINE_HINT_loop_stride = 4, 60 /* Inlining within same strongly connected component of callgraph is often 61 a loss due to increased stack frame usage and prologue setup costs. */ 62 INLINE_HINT_same_scc = 8, 63 /* Inlining functions in strongly connected component is not such a great 64 win. */ 65 INLINE_HINT_in_scc = 16, 66 /* If function is declared inline by user, it may be good idea to inline 67 it. */ 68 INLINE_HINT_declared_inline = 32, 69 /* Programs are usually still organized for non-LTO compilation and thus 70 if functions are in different modules, inlining may not be so important. 71 */ 72 INLINE_HINT_cross_module = 64, 73 /* If array indexes of loads/stores become known there may be room for 74 further optimization. */ 75 INLINE_HINT_array_index = 128, 76 /* We know that the callee is hot by profile. */ 77 INLINE_HINT_known_hot = 256 78}; 79typedef int inline_hints; 80 81 82typedef vec<condition, va_gc> *conditions; 83 84/* Representation of predicates i.e. formulas using conditions defined 85 above. Predicates are simple logical formulas in conjunctive-disjunctive 86 form. 87 88 Predicate is array of clauses terminated by 0. Every clause must be true 89 in order to make predicate true. 90 Clauses are represented as bitmaps of conditions. One of conditions 91 must be true in order for clause to be true. */ 92 93#define MAX_CLAUSES 8 94typedef unsigned int clause_t; 95struct GTY(()) predicate 96{ 97 clause_t clause[MAX_CLAUSES + 1]; 98}; 99 100/* Represnetation of function body size and time depending on the inline 101 context. We keep simple array of record, every containing of predicate 102 and time/size to account. 103 104 We keep values scaled up, so fractional sizes and times can be 105 accounted. */ 106#define INLINE_SIZE_SCALE 2 107#define INLINE_TIME_SCALE (CGRAPH_FREQ_BASE * 2) 108struct GTY(()) size_time_entry 109{ 110 struct predicate predicate; 111 int size; 112 int time; 113}; 114 115/* Function inlining information. */ 116struct GTY(()) inline_summary 117{ 118 /* Information about the function body itself. */ 119 120 /* Estimated stack frame consumption by the function. */ 121 HOST_WIDE_INT estimated_self_stack_size; 122 /* Size of the function body. */ 123 int self_size; 124 /* Time of the function body. */ 125 int self_time; 126 /* Minimal size increase after inlining. */ 127 int min_size; 128 129 /* False when there something makes inlining impossible (such as va_arg). */ 130 unsigned inlinable : 1; 131 /* True when function contains cilk spawn (and thus we can not inline 132 into it). */ 133 unsigned contains_cilk_spawn : 1; 134 /* True wen there is only one caller of the function before small function 135 inlining. */ 136 unsigned int single_caller : 1; 137 138 /* Information about function that will result after applying all the 139 inline decisions present in the callgraph. Generally kept up to 140 date only for functions that are not inline clones. */ 141 142 /* Estimated stack frame consumption by the function. */ 143 HOST_WIDE_INT estimated_stack_size; 144 /* Expected offset of the stack frame of inlined function. */ 145 HOST_WIDE_INT stack_frame_offset; 146 /* Estimated size of the function after inlining. */ 147 int time; 148 int size; 149 150 /* Conditional size/time information. The summaries are being 151 merged during inlining. */ 152 conditions conds; 153 vec<size_time_entry, va_gc> *entry; 154 155 /* Predicate on when some loop in the function becomes to have known 156 bounds. */ 157 struct predicate * GTY((skip)) loop_iterations; 158 /* Predicate on when some loop in the function becomes to have known 159 stride. */ 160 struct predicate * GTY((skip)) loop_stride; 161 /* Predicate on when some array indexes become constants. */ 162 struct predicate * GTY((skip)) array_index; 163 /* Estimated growth for inlining all copies of the function before start 164 of small functions inlining. 165 This value will get out of date as the callers are duplicated, but 166 using up-to-date value in the badness metric mean a lot of extra 167 expenses. */ 168 int growth; 169 /* Number of SCC on the beginning of inlining process. */ 170 int scc_no; 171}; 172 173class GTY((user)) inline_summary_t: public function_summary <inline_summary *> 174{ 175public: 176 inline_summary_t (symbol_table *symtab, bool ggc): 177 function_summary <inline_summary *> (symtab, ggc) {} 178 179 static inline_summary_t *create_ggc (symbol_table *symtab) 180 { 181 struct inline_summary_t *summary = new (ggc_cleared_alloc <inline_summary_t> ()) 182 inline_summary_t(symtab, true); 183 summary->disable_insertion_hook (); 184 return summary; 185 } 186 187 188 virtual void insert (cgraph_node *, inline_summary *); 189 virtual void remove (cgraph_node *node, inline_summary *); 190 virtual void duplicate (cgraph_node *src, cgraph_node *dst, 191 inline_summary *src_data, inline_summary *dst_data); 192}; 193 194extern GTY(()) function_summary <inline_summary *> *inline_summaries; 195 196/* Information kept about parameter of call site. */ 197struct inline_param_summary 198{ 199 /* REG_BR_PROB_BASE based probability that parameter will change in between 200 two invocation of the calls. 201 I.e. loop invariant parameters 202 REG_BR_PROB_BASE/estimated_iterations and regular 203 parameters REG_BR_PROB_BASE. 204 205 Value 0 is reserved for compile time invariants. */ 206 int change_prob; 207}; 208 209/* Information kept about callgraph edges. */ 210struct inline_edge_summary 211{ 212 /* Estimated size and time of the call statement. */ 213 int call_stmt_size; 214 int call_stmt_time; 215 /* Depth of loop nest, 0 means no nesting. */ 216 unsigned short int loop_depth; 217 struct predicate *predicate; 218 /* Array indexed by parameters. 219 0 means that parameter change all the time, REG_BR_PROB_BASE means 220 that parameter is constant. */ 221 vec<inline_param_summary> param; 222}; 223 224/* Need a typedef for inline_edge_summary because of inline function 225 'inline_edge_summary' below. */ 226typedef struct inline_edge_summary inline_edge_summary_t; 227extern vec<inline_edge_summary_t> inline_edge_summary_vec; 228 229struct edge_growth_cache_entry 230{ 231 int time, size; 232 inline_hints hints; 233}; 234 235extern vec<edge_growth_cache_entry> edge_growth_cache; 236 237/* In ipa-inline-analysis.c */ 238void debug_inline_summary (struct cgraph_node *); 239void dump_inline_summaries (FILE *f); 240void dump_inline_summary (FILE *f, struct cgraph_node *node); 241void dump_inline_hints (FILE *f, inline_hints); 242void inline_generate_summary (void); 243void inline_read_summary (void); 244void inline_write_summary (void); 245void inline_free_summary (void); 246void inline_analyze_function (struct cgraph_node *node); 247void initialize_inline_failed (struct cgraph_edge *); 248int estimate_time_after_inlining (struct cgraph_node *, struct cgraph_edge *); 249int estimate_size_after_inlining (struct cgraph_node *, struct cgraph_edge *); 250void estimate_ipcp_clone_size_and_time (struct cgraph_node *, 251 vec<tree>, 252 vec<ipa_polymorphic_call_context>, 253 vec<ipa_agg_jump_function_p>, 254 int *, int *, inline_hints *); 255int estimate_growth (struct cgraph_node *); 256bool growth_likely_positive (struct cgraph_node *, int); 257void inline_merge_summary (struct cgraph_edge *edge); 258void inline_update_overall_summary (struct cgraph_node *node); 259int do_estimate_edge_size (struct cgraph_edge *edge); 260int do_estimate_edge_time (struct cgraph_edge *edge); 261inline_hints do_estimate_edge_hints (struct cgraph_edge *edge); 262void initialize_growth_caches (void); 263void free_growth_caches (void); 264void compute_inline_parameters (struct cgraph_node *, bool); 265bool speculation_useful_p (struct cgraph_edge *e, bool anticipate_inlining); 266unsigned int early_inliner (function *fun); 267bool inline_account_function_p (struct cgraph_node *node); 268 269 270/* In ipa-inline-transform.c */ 271bool inline_call (struct cgraph_edge *, bool, vec<cgraph_edge *> *, int *, bool, 272 bool *callee_removed = NULL); 273unsigned int inline_transform (struct cgraph_node *); 274void clone_inlined_nodes (struct cgraph_edge *e, bool, bool, int *, 275 int freq_scale); 276 277extern int ncalls_inlined; 278extern int nfunctions_inlined; 279 280static inline struct inline_edge_summary * 281inline_edge_summary (struct cgraph_edge *edge) 282{ 283 return &inline_edge_summary_vec[edge->uid]; 284} 285 286 287/* Return estimated size of the inline sequence of EDGE. */ 288 289static inline int 290estimate_edge_size (struct cgraph_edge *edge) 291{ 292 int ret; 293 if ((int)edge_growth_cache.length () <= edge->uid 294 || !(ret = edge_growth_cache[edge->uid].size)) 295 return do_estimate_edge_size (edge); 296 return ret - (ret > 0); 297} 298 299/* Return estimated callee growth after inlining EDGE. */ 300 301static inline int 302estimate_edge_growth (struct cgraph_edge *edge) 303{ 304#ifdef ENABLE_CHECKING 305 gcc_checking_assert (inline_edge_summary (edge)->call_stmt_size 306 || !edge->callee->analyzed); 307#endif 308 return (estimate_edge_size (edge) 309 - inline_edge_summary (edge)->call_stmt_size); 310} 311 312/* Return estimated callee runtime increase after inlning 313 EDGE. */ 314 315static inline int 316estimate_edge_time (struct cgraph_edge *edge) 317{ 318 int ret; 319 if ((int)edge_growth_cache.length () <= edge->uid 320 || !(ret = edge_growth_cache[edge->uid].time)) 321 return do_estimate_edge_time (edge); 322 return ret - (ret > 0); 323} 324 325 326/* Return estimated callee runtime increase after inlning 327 EDGE. */ 328 329static inline inline_hints 330estimate_edge_hints (struct cgraph_edge *edge) 331{ 332 inline_hints ret; 333 if ((int)edge_growth_cache.length () <= edge->uid 334 || !(ret = edge_growth_cache[edge->uid].hints)) 335 return do_estimate_edge_hints (edge); 336 return ret - 1; 337} 338 339/* Reset cached value for EDGE. */ 340 341static inline void 342reset_edge_growth_cache (struct cgraph_edge *edge) 343{ 344 if ((int)edge_growth_cache.length () > edge->uid) 345 { 346 struct edge_growth_cache_entry zero = {0, 0, 0}; 347 edge_growth_cache[edge->uid] = zero; 348 } 349} 350 351#endif /* GCC_IPA_INLINE_H */ 352