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