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 #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
  30 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 };
  45
  46 /* Inline hints are reasons why inline heuristics should preffer inlining given
  47    function.  They are represtented as bitmap of the following values.  */
  48 enum 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 within 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      further optimization.  */
  71   INLINE_HINT_array_index = 128,
  72   /* We know that the callee is hot by profile.  */
  73   INLINE_HINT_known_hot = 256
  74 };
  75 typedef int inline_hints;
  76
  77
  78 typedef vec<condition, va_gc> *conditions;
  79
  80 /* Representation of predicates i.e. formulas using conditions defined
  81    above.  Predicates are simple logical formulas in conjunctive-disjunctive
  82    form.
  83
  84    Predicate is array of clauses terminated by 0.  Every clause must be true
  85    in order to make predicate true.
  86    Clauses are represented as bitmaps of conditions. One of conditions
  87    must be true in order for clause to be true.  */
  88
  89 #define MAX_CLAUSES 8
  90 typedef unsigned int clause_t;
  91 struct GTY(()) predicate
  92 {
  93   clause_t clause[MAX_CLAUSES + 1];
  94 };
  95
  96 /* Represnetation of function body size and time depending on the inline
  97    context.  We keep simple array of record, every containing of predicate
  98    and time/size to account.
  99
 100    We keep values scaled up, so fractional sizes and times can be
 101    accounted.  */
 102 #define INLINE_SIZE_SCALE 2
 103 #define INLINE_TIME_SCALE (CGRAPH_FREQ_BASE * 2)
 104 struct GTY(()) size_time_entry
 105 {
 106   struct predicate predicate;
 107   int size;
 108   int time;
 109 };
 110
 111 /* Function inlining information.  */
 112 struct GTY(()) inline_summary
 113 {
 114   /* Information about the function body itself.  */
 115
 116   /* Estimated stack frame consumption by the function.  */
 117   HOST_WIDE_INT estimated_self_stack_size;
 118   /* Size of the function body.  */
 119   int self_size;
 120   /* Time of the function body.  */
 121   int self_time;
 122   /* Minimal size increase after inlining.  */
 123   int min_size;
 124
 125   /* False when there something makes inlining impossible (such as va_arg).  */
 126   unsigned inlinable : 1;
 127
 128   /* Information about function that will result after applying all the
 129      inline decisions present in the callgraph.  Generally kept up to
 130      date only for functions that are not inline clones. */
 131
 132   /* Estimated stack frame consumption by the function.  */
 133   HOST_WIDE_INT estimated_stack_size;
 134   /* Expected offset of the stack frame of inlined function.  */
 135   HOST_WIDE_INT stack_frame_offset;
 136   /* Estimated size of the function after inlining.  */
 137   int time;
 138   int size;
 139
 140   /* Conditional size/time information.  The summaries are being
 141      merged during inlining.  */
 142   conditions conds;
 143   vec<size_time_entry, va_gc> *entry;
 144
 145   /* Predicate on when some loop in the function becomes to have known
 146      bounds.   */
 147   struct predicate * GTY((skip)) loop_iterations;
 148   /* Predicate on when some loop in the function becomes to have known
 149      stride.   */
 150   struct predicate * GTY((skip)) loop_stride;
 151   /* Predicate on when some array indexes become constants.  */
 152   struct predicate * GTY((skip)) array_index;
 153   /* Estimated growth for inlining all copies of the function before start
 154      of small functions inlining.
 155      This value will get out of date as the callers are duplicated, but
 156      using up-to-date value in the badness metric mean a lot of extra
 157      expenses.  */
 158   int growth;
 159   /* Number of SCC on the beginning of inlining process.  */
 160   int scc_no;
 161 };
 162
 163 /* Need a typedef for inline_summary because of inline function
 164    'inline_summary' below.  */
 165 typedef struct inline_summary inline_summary_t;
 166 extern GTY(()) vec<inline_summary_t, va_gc> *inline_summary_vec;
 167
 168 /* Information kept about parameter of call site.  */
 169 struct inline_param_summary
 170 {
 171   /* REG_BR_PROB_BASE based probability that parameter will change in between
 172      two invocation of the calls.
 173      I.e. loop invariant parameters
 174      REG_BR_PROB_BASE/estimated_iterations and regular
 175      parameters REG_BR_PROB_BASE.
 176
 177      Value 0 is reserved for compile time invariants. */
 178   int change_prob;
 179 };
 180
 181 /* Information kept about callgraph edges.  */
 182 struct inline_edge_summary
 183 {
 184   /* Estimated size and time of the call statement.  */
 185   int call_stmt_size;
 186   int call_stmt_time;
 187   /* Depth of loop nest, 0 means no nesting.  */
 188   unsigned short int loop_depth;
 189   struct predicate *predicate;
 190   /* Array indexed by parameters.
 191      0 means that parameter change all the time, REG_BR_PROB_BASE means
 192      that parameter is constant.  */
 193   vec<inline_param_summary> param;
 194 };
 195
 196 /* Need a typedef for inline_edge_summary because of inline function
 197    'inline_edge_summary' below.  */
 198 typedef struct inline_edge_summary inline_edge_summary_t;
 199 extern vec<inline_edge_summary_t> inline_edge_summary_vec;
 200
 201 struct edge_growth_cache_entry
 202 {
 203   int time, size;
 204   inline_hints hints;
 205 };
 206
 207 extern vec<int> node_growth_cache;
 208 extern vec<edge_growth_cache_entry> edge_growth_cache;
 209
 210 /* In ipa-inline-analysis.c  */
 211 void debug_inline_summary (struct cgraph_node *);
 212 void dump_inline_summaries (FILE *f);
 213 void dump_inline_summary (FILE *f, struct cgraph_node *node);
 214 void dump_inline_hints (FILE *f, inline_hints);
 215 void inline_generate_summary (void);
 216 void inline_read_summary (void);
 217 void inline_write_summary (void);
 218 void inline_free_summary (void);
 219 void inline_analyze_function (struct cgraph_node *node);
 220 void initialize_inline_failed (struct cgraph_edge *);
 221 int estimate_time_after_inlining (struct cgraph_node *, struct cgraph_edge *);
 222 int estimate_size_after_inlining (struct cgraph_node *, struct cgraph_edge *);
 223 void estimate_ipcp_clone_size_and_time (struct cgraph_node *,
 224                                         vec<tree>,  vec<tree>,
 225                                         vec<ipa_agg_jump_function_p>,
 226                                         int *, int *, inline_hints *);
 227 int do_estimate_growth (struct cgraph_node *);
 228 bool growth_likely_positive (struct cgraph_node *, int);
 229 void inline_merge_summary (struct cgraph_edge *edge);
 230 void inline_update_overall_summary (struct cgraph_node *node);
 231 int do_estimate_edge_size (struct cgraph_edge *edge);
 232 int do_estimate_edge_time (struct cgraph_edge *edge);
 233 inline_hints do_estimate_edge_hints (struct cgraph_edge *edge);
 234 void initialize_growth_caches (void);
 235 void free_growth_caches (void);
 236 void compute_inline_parameters (struct cgraph_node *, bool);
 237 bool speculation_useful_p (struct cgraph_edge *e, bool anticipate_inlining);
 238
 239 /* In ipa-inline-transform.c  */
 240 bool inline_call (struct cgraph_edge *, bool, vec<cgraph_edge_p> *, int *, bool,
 241                   bool *callee_removed = NULL);
 242 unsigned int inline_transform (struct cgraph_node *);
 243 void clone_inlined_nodes (struct cgraph_edge *e, bool, bool, int *,
 244                           int freq_scale);
 245
 246 extern int ncalls_inlined;
 247 extern int nfunctions_inlined;
 248
 249 static inline struct inline_summary *
 250 inline_summary (struct cgraph_node *node)
 251 {
 252   return &(*inline_summary_vec)[node->uid];
 253 }
 254
 255 static inline struct inline_edge_summary *
 256 inline_edge_summary (struct cgraph_edge *edge)
 257 {
 258   return &inline_edge_summary_vec[edge->uid];
 259 }
 260
 261 /* Return estimated unit growth after inlning all calls to NODE.
 262    Quick accesors to the inline growth caches.
 263    For convenience we keep zero 0 as unknown.  Because growth
 264    can be both positive and negative, we simply increase positive
 265    growths by 1. */
 266 static inline int
 267 estimate_growth (struct cgraph_node *node)
 268 {
 269   int ret;
 270   if ((int)node_growth_cache.length () <= node->uid
 271       || !(ret = node_growth_cache[node->uid]))
 272     return do_estimate_growth (node);
 273   return ret - (ret > 0);
 274 }
 275
 276
 277 /* Return estimated size of the inline sequence of EDGE.  */
 278
 279 static inline int
 280 estimate_edge_size (struct cgraph_edge *edge)
 281 {
 282   int ret;
 283   if ((int)edge_growth_cache.length () <= edge->uid
 284       || !(ret = edge_growth_cache[edge->uid].size))
 285     return do_estimate_edge_size (edge);
 286   return ret - (ret > 0);
 287 }
 288
 289 /* Return estimated callee growth after inlining EDGE.  */
 290
 291 static inline int
 292 estimate_edge_growth (struct cgraph_edge *edge)
 293 {
 294 #ifdef ENABLE_CHECKING
 295   gcc_checking_assert (inline_edge_summary (edge)->call_stmt_size
 296                        || !edge->callee->analyzed);
 297 #endif
 298   return (estimate_edge_size (edge)
 299           - inline_edge_summary (edge)->call_stmt_size);
 300 }
 301
 302 /* Return estimated callee runtime increase after inlning
 303    EDGE.  */
 304
 305 static inline int
 306 estimate_edge_time (struct cgraph_edge *edge)
 307 {
 308   int ret;
 309   if ((int)edge_growth_cache.length () <= edge->uid
 310       || !(ret =  edge_growth_cache[edge->uid].time))
 311     return do_estimate_edge_time (edge);
 312   return ret - (ret > 0);
 313 }
 314
 315
 316 /* Return estimated callee runtime increase after inlning
 317    EDGE.  */
 318
 319 static inline inline_hints
 320 estimate_edge_hints (struct cgraph_edge *edge)
 321 {
 322   inline_hints ret;
 323   if ((int)edge_growth_cache.length () <= edge->uid
 324       || !(ret = edge_growth_cache[edge->uid].hints))
 325     return do_estimate_edge_hints (edge);
 326   return ret - 1;
 327 }
 328
 329
 330 /* Reset cached value for NODE.  */
 331
 332 static inline void
 333 reset_node_growth_cache (struct cgraph_node *node)
 334 {
 335   if ((int)node_growth_cache.length () > node->uid)
 336     node_growth_cache[node->uid] = 0;
 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 }