gcc/ipa-inline.h

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