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