gcc/ipa-inline.h

   1 /* Inlining decision heuristics.
   2    Copyright (C) 2003-2016 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 #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
  32 struct 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.  */
  52 enum 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 };
  79 typedef int inline_hints;
  80
  81
  82 typedef 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
  94 typedef unsigned int clause_t;
  95 struct 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)
 108 struct GTY(()) size_time_entry
 109 {
 110   struct predicate predicate;
 111   int size;
 112   int time;
 113 };
 114
 115 /* Function inlining information.  */
 116 struct 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   /* True if function contains any floating point expressions.  */
 138   unsigned int fp_expressions : 1;
 139
 140   /* Information about function that will result after applying all the
 141      inline decisions present in the callgraph.  Generally kept up to
 142      date only for functions that are not inline clones. */
 143
 144   /* Estimated stack frame consumption by the function.  */
 145   HOST_WIDE_INT estimated_stack_size;
 146   /* Expected offset of the stack frame of inlined function.  */
 147   HOST_WIDE_INT stack_frame_offset;
 148   /* Estimated size of the function after inlining.  */
 149   int time;
 150   int size;
 151
 152   /* Conditional size/time information.  The summaries are being
 153      merged during inlining.  */
 154   conditions conds;
 155   vec<size_time_entry, va_gc> *entry;
 156
 157   /* Predicate on when some loop in the function becomes to have known
 158      bounds.   */
 159   struct predicate * GTY((skip)) loop_iterations;
 160   /* Predicate on when some loop in the function becomes to have known
 161      stride.   */
 162   struct predicate * GTY((skip)) loop_stride;
 163   /* Predicate on when some array indexes become constants.  */
 164   struct predicate * GTY((skip)) array_index;
 165   /* Estimated growth for inlining all copies of the function before start
 166      of small functions inlining.
 167      This value will get out of date as the callers are duplicated, but
 168      using up-to-date value in the badness metric mean a lot of extra
 169      expenses.  */
 170   int growth;
 171   /* Number of SCC on the beginning of inlining process.  */
 172   int scc_no;
 173 };
 174
 175 class GTY((user)) inline_summary_t: public function_summary <inline_summary *>
 176 {
 177 public:
 178   inline_summary_t (symbol_table *symtab, bool ggc):
 179     function_summary <inline_summary *> (symtab, ggc) {}
 180
 181   static inline_summary_t *create_ggc (symbol_table *symtab)
 182   {
 183     struct inline_summary_t *summary = new (ggc_cleared_alloc <inline_summary_t> ())
 184       inline_summary_t(symtab, true);
 185     summary->disable_insertion_hook ();
 186     return summary;
 187   }
 188
 189
 190   virtual void insert (cgraph_node *, inline_summary *);
 191   virtual void remove (cgraph_node *node, inline_summary *);
 192   virtual void duplicate (cgraph_node *src, cgraph_node *dst,
 193                           inline_summary *src_data, inline_summary *dst_data);
 194 };
 195
 196 extern GTY(()) function_summary <inline_summary *> *inline_summaries;
 197
 198 /* Information kept about parameter of call site.  */
 199 struct inline_param_summary
 200 {
 201   /* REG_BR_PROB_BASE based probability that parameter will change in between
 202      two invocation of the calls.
 203      I.e. loop invariant parameters
 204      REG_BR_PROB_BASE/estimated_iterations and regular
 205      parameters REG_BR_PROB_BASE.
 206
 207      Value 0 is reserved for compile time invariants. */
 208   int change_prob;
 209 };
 210
 211 /* Information kept about callgraph edges.  */
 212 struct inline_edge_summary
 213 {
 214   /* Estimated size and time of the call statement.  */
 215   int call_stmt_size;
 216   int call_stmt_time;
 217   /* Depth of loop nest, 0 means no nesting.  */
 218   unsigned short int loop_depth;
 219   struct predicate *predicate;
 220   /* Array indexed by parameters.
 221      0 means that parameter change all the time, REG_BR_PROB_BASE means
 222      that parameter is constant.  */
 223   vec<inline_param_summary> param;
 224 };
 225
 226 /* Need a typedef for inline_edge_summary because of inline function
 227    'inline_edge_summary' below.  */
 228 typedef struct inline_edge_summary inline_edge_summary_t;
 229 extern vec<inline_edge_summary_t> inline_edge_summary_vec;
 230
 231 struct edge_growth_cache_entry
 232 {
 233   int time, size;
 234   inline_hints hints;
 235 };
 236
 237 extern vec<edge_growth_cache_entry> edge_growth_cache;
 238
 239 /* In ipa-inline-analysis.c  */
 240 void debug_inline_summary (struct cgraph_node *);
 241 void dump_inline_summaries (FILE *f);
 242 void dump_inline_summary (FILE *f, struct cgraph_node *node);
 243 void dump_inline_hints (FILE *f, inline_hints);
 244 void inline_generate_summary (void);
 245 void inline_read_summary (void);
 246 void inline_write_summary (void);
 247 void inline_free_summary (void);
 248 void inline_analyze_function (struct cgraph_node *node);
 249 void initialize_inline_failed (struct cgraph_edge *);
 250 int estimate_time_after_inlining (struct cgraph_node *, struct cgraph_edge *);
 251 int estimate_size_after_inlining (struct cgraph_node *, struct cgraph_edge *);
 252 void estimate_ipcp_clone_size_and_time (struct cgraph_node *,
 253                                         vec<tree>,
 254                                         vec<ipa_polymorphic_call_context>,
 255                                         vec<ipa_agg_jump_function_p>,
 256                                         int *, int *, inline_hints *);
 257 int estimate_growth (struct cgraph_node *);
 258 bool growth_likely_positive (struct cgraph_node *, int);
 259 void inline_merge_summary (struct cgraph_edge *edge);
 260 void inline_update_overall_summary (struct cgraph_node *node);
 261 int do_estimate_edge_size (struct cgraph_edge *edge);
 262 int do_estimate_edge_time (struct cgraph_edge *edge);
 263 inline_hints do_estimate_edge_hints (struct cgraph_edge *edge);
 264 void initialize_growth_caches (void);
 265 void free_growth_caches (void);
 266 void compute_inline_parameters (struct cgraph_node *, bool);
 267 bool speculation_useful_p (struct cgraph_edge *e, bool anticipate_inlining);
 268 unsigned int early_inliner (function *fun);
 269 bool inline_account_function_p (struct cgraph_node *node);
 270
 271
 272 /* In ipa-inline-transform.c  */
 273 bool inline_call (struct cgraph_edge *, bool, vec<cgraph_edge *> *, int *, bool,
 274                   bool *callee_removed = NULL);
 275 unsigned int inline_transform (struct cgraph_node *);
 276 void clone_inlined_nodes (struct cgraph_edge *e, bool, bool, int *,
 277                           int freq_scale);
 278
 279 extern int ncalls_inlined;
 280 extern int nfunctions_inlined;
 281
 282 static inline struct inline_edge_summary *
 283 inline_edge_summary (struct cgraph_edge *edge)
 284 {
 285   return &inline_edge_summary_vec[edge->uid];
 286 }
 287
 288
 289 /* Return estimated size of the inline sequence of EDGE.  */
 290
 291 static inline int
 292 estimate_edge_size (struct cgraph_edge *edge)
 293 {
 294   int ret;
 295   if ((int)edge_growth_cache.length () <= edge->uid
 296       || !(ret = edge_growth_cache[edge->uid].size))
 297     return do_estimate_edge_size (edge);
 298   return ret - (ret > 0);
 299 }
 300
 301 /* Return estimated callee growth after inlining EDGE.  */
 302
 303 static inline int
 304 estimate_edge_growth (struct cgraph_edge *edge)
 305 {
 306   gcc_checking_assert (inline_edge_summary (edge)->call_stmt_size
 307                        || !edge->callee->analyzed);
 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
 315 static inline int
 316 estimate_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
 329 static inline inline_hints
 330 estimate_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
 341 static inline void
 342 reset_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 */