gcc/ipa-inline.h

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