gcc/ipa-inline.h

   1 /* Inlining decision heuristics.
   2    Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010, 2011
   3    Free Software Foundation, Inc.
   4    Contributed by Jan Hubicka
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "ipa-prop.h"
  23
  24 /* Representation of inline parameters that do depend on context function is
  25    inlined into (i.e. known constant values of function parameters.
  26
  27    Conditions that are interesting for function body are collected into CONDS
  28    vector.  They are of simple for  function_param OP VAL, where VAL is
  29    IPA invariant.  The conditions are then referred by predicates.  */
  30
  31 typedef struct GTY(()) condition
  32   {
  33     /* If agg_contents is set, this is the offset from which the used data was
  34        loaded.  */
  35     HOST_WIDE_INT offset;
  36     tree val;
  37     int operand_num;
  38     ENUM_BITFIELD(tree_code) code : 16;
  39     /* Set if the used data were loaded from an aggregate parameter or from
  40        data received by reference.  */
  41     unsigned agg_contents : 1;
  42     /* If agg_contents is set, this differentiates between loads from data
  43        passed by reference and by value.  */
  44     unsigned by_ref : 1;
  45   } condition;
  46
  47 /* Inline hints are reasons why inline heuristics should preffer inlining given
  48    function.  They are represtented as bitmap of the following values.  */
  49 enum inline_hints_vals {
  50   /* When inlining turns indirect call into a direct call,
  51      it is good idea to do so.  */
  52   INLINE_HINT_indirect_call = 1,
  53   /* Inlining may make loop iterations or loop stride known.  It is good idea
  54      to do so because it enables loop optimizatoins.  */
  55   INLINE_HINT_loop_iterations = 2,
  56   INLINE_HINT_loop_stride = 4,
  57   /* Inlining withing same strongly connected component of callgraph is often
  58      a loss due to increased stack frame usage and prologue setup costs.  */
  59   INLINE_HINT_same_scc = 8,
  60   /* Inlining functions in strongly connected component is not such a great
  61      win.  */
  62   INLINE_HINT_in_scc = 16,
  63   /* If function is declared inline by user, it may be good idea to inline
  64      it.  */
  65   INLINE_HINT_declared_inline = 32,
  66   /* Programs are usually still organized for non-LTO compilation and thus
  67      if functions are in different modules, inlining may not be so important.
  68    */
  69   INLINE_HINT_cross_module = 64,
  70   /* If array indexes of loads/stores become known there may be room for
  71      futher optimization.  */
  72   INLINE_HINT_array_index = 128
  73 };
  74 typedef int inline_hints;
  75
  76 DEF_VEC_O (condition);
  77 DEF_VEC_ALLOC_O (condition, gc);
  78
  79 typedef VEC(condition,gc) *conditions;
  80
  81 /* Representation of predicates i.e. formulas using conditions defined
  82    above.  Predicates are simple logical formulas in conjunctive-disjunctive
  83    form.
  84
  85    Predicate is array of clauses terminated by 0.  Every clause must be true
  86    in order to make predicate true.
  87    Clauses are represented as bitmaps of conditions. One of conditions
  88    must be true in order for clause to be true.  */
  89
  90 #define MAX_CLAUSES 8
  91 typedef unsigned int clause_t;
  92 struct GTY(()) predicate
  93 {
  94   clause_t clause[MAX_CLAUSES + 1];
  95 };
  96
  97 /* Represnetation of function body size and time depending on the inline
  98    context.  We keep simple array of record, every containing of predicate
  99    and time/size to account.
 100
 101    We keep values scaled up, so fractional sizes and times can be
 102    accounted.  */
 103 #define INLINE_SIZE_SCALE 2
 104 #define INLINE_TIME_SCALE (CGRAPH_FREQ_BASE * 2)
 105 typedef struct GTY(()) size_time_entry
 106 {
 107   struct predicate predicate;
 108   int size;
 109   int time;
 110 } size_time_entry;
 111 DEF_VEC_O (size_time_entry);
 112 DEF_VEC_ALLOC_O (size_time_entry, gc);
 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
 126   /* False when there something makes inlining impossible (such as va_arg).  */
 127   unsigned inlinable : 1;
 128
 129   /* Information about function that will result after applying all the
 130      inline decisions present in the callgraph.  Generally kept up to
 131      date only for functions that are not inline clones. */
 132
 133   /* Estimated stack frame consumption by the function.  */
 134   HOST_WIDE_INT estimated_stack_size;
 135   /* Expected offset of the stack frame of inlined function.  */
 136   HOST_WIDE_INT stack_frame_offset;
 137   /* Estimated size of the function after inlining.  */
 138   int time;
 139   int size;
 140
 141   /* Conditional size/time information.  The summaries are being
 142      merged during inlining.  */
 143   conditions conds;
 144   VEC(size_time_entry,gc) *entry;
 145
 146   /* Predicate on when some loop in the function becomes to have known
 147      bounds.   */
 148   struct predicate * GTY((skip)) loop_iterations;
 149   /* Predicate on when some loop in the function becomes to have known
 150      stride.   */
 151   struct predicate * GTY((skip)) loop_stride;
 152   /* Predicate on when some array indexes become constants.  */
 153   struct predicate * GTY((skip)) array_index;
 154   /* Estimated growth for inlining all copies of the function before start
 155      of small functions inlining.
 156      This value will get out of date as the callers are duplicated, but
 157      using up-to-date value in the badness metric mean a lot of extra
 158      expenses.  */
 159   int growth;
 160   /* Number of SCC on the beggining of inlining process.  */
 161   int scc_no;
 162 };
 163
 164
 165 typedef struct inline_summary inline_summary_t;
 166 DEF_VEC_O(inline_summary_t);
 167 DEF_VEC_ALLOC_O(inline_summary_t,gc);
 168 extern GTY(()) VEC(inline_summary_t,gc) *inline_summary_vec;
 169
 170 /* Information kept about parameter of call site.  */
 171 struct inline_param_summary
 172 {
 173   /* REG_BR_PROB_BASE based probability that parameter will change in between
 174      two invocation of the calls.
 175      I.e. loop invariant parameters
 176      REG_BR_PROB_BASE/estimated_iterations and regular
 177      parameters REG_BR_PROB_BASE.
 178
 179      Value 0 is reserved for compile time invariants. */
 180   int change_prob;
 181 };
 182 typedef struct inline_param_summary inline_param_summary_t;
 183 DEF_VEC_O(inline_param_summary_t);
 184 DEF_VEC_ALLOC_O(inline_param_summary_t,heap);
 185
 186 /* Information kept about callgraph edges.  */
 187 struct inline_edge_summary
 188 {
 189   /* Estimated size and time of the call statement.  */
 190   int call_stmt_size;
 191   int call_stmt_time;
 192   /* Depth of loop nest, 0 means no nesting.  */
 193   unsigned short int loop_depth;
 194   struct predicate *predicate;
 195   /* Array indexed by parameters.
 196      0 means that parameter change all the time, REG_BR_PROB_BASE means
 197      that parameter is constant.  */
 198   VEC (inline_param_summary_t, heap) *param;
 199 };
 200
 201 typedef struct inline_edge_summary inline_edge_summary_t;
 202 DEF_VEC_O(inline_edge_summary_t);
 203 DEF_VEC_ALLOC_O(inline_edge_summary_t,heap);
 204 extern VEC(inline_edge_summary_t,heap) *inline_edge_summary_vec;
 205
 206 typedef struct edge_growth_cache_entry
 207 {
 208   int time, size;
 209   inline_hints hints;
 210 } edge_growth_cache_entry;
 211 DEF_VEC_O(edge_growth_cache_entry);
 212 DEF_VEC_ALLOC_O(edge_growth_cache_entry,heap);
 213
 214 extern VEC(int,heap) *node_growth_cache;
 215 extern VEC(edge_growth_cache_entry,heap) *edge_growth_cache;
 216
 217 /* In ipa-inline-analysis.c  */
 218 void debug_inline_summary (struct cgraph_node *);
 219 void dump_inline_summaries (FILE *f);
 220 void dump_inline_summary (FILE *f, struct cgraph_node *node);
 221 void dump_inline_hints (FILE *f, inline_hints);
 222 void inline_generate_summary (void);
 223 void inline_read_summary (void);
 224 void inline_write_summary (void);
 225 void inline_free_summary (void);
 226 void initialize_inline_failed (struct cgraph_edge *);
 227 int estimate_time_after_inlining (struct cgraph_node *, struct cgraph_edge *);
 228 int estimate_size_after_inlining (struct cgraph_node *, struct cgraph_edge *);
 229 void estimate_ipcp_clone_size_and_time (struct cgraph_node *,
 230                                         VEC (tree, heap) *, VEC (tree, heap) *,
 231                                         VEC (ipa_agg_jump_function_p, heap) *,
 232                                         int *, int *, inline_hints *);
 233 int do_estimate_growth (struct cgraph_node *);
 234 void inline_merge_summary (struct cgraph_edge *edge);
 235 void inline_update_overall_summary (struct cgraph_node *node);
 236 int do_estimate_edge_size (struct cgraph_edge *edge);
 237 int do_estimate_edge_time (struct cgraph_edge *edge);
 238 inline_hints do_estimate_edge_hints (struct cgraph_edge *edge);
 239 void initialize_growth_caches (void);
 240 void free_growth_caches (void);
 241 void compute_inline_parameters (struct cgraph_node *, bool);
 242
 243 /* In ipa-inline-transform.c  */
 244 bool inline_call (struct cgraph_edge *, bool, VEC (cgraph_edge_p, heap) **, int *, bool);
 245 unsigned int inline_transform (struct cgraph_node *);
 246 void clone_inlined_nodes (struct cgraph_edge *e, bool, bool, int *);
 247
 248 extern int ncalls_inlined;
 249 extern int nfunctions_inlined;
 250
 251 static inline struct inline_summary *
 252 inline_summary (struct cgraph_node *node)
 253 {
 254   return &VEC_index (inline_summary_t, inline_summary_vec, node->uid);
 255 }
 256
 257 static inline struct inline_edge_summary *
 258 inline_edge_summary (struct cgraph_edge *edge)
 259 {
 260   return &VEC_index (inline_edge_summary_t,
 261                     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)VEC_length (int, node_growth_cache) <= node->uid
 274       || !(ret = VEC_index (int, 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)VEC_length (edge_growth_cache_entry, edge_growth_cache) <= edge->uid
 287       || !(ret = VEC_index (edge_growth_cache_entry,
 288                             edge_growth_cache,
 289                             edge->uid).size))
 290     return do_estimate_edge_size (edge);
 291   return ret - (ret > 0);
 292 }
 293
 294 /* Return estimated callee growth after inlining EDGE.  */
 295
 296 static inline int
 297 estimate_edge_growth (struct cgraph_edge *edge)
 298 {
 299 #ifdef ENABLE_CHECKING
 300   gcc_checking_assert (inline_edge_summary (edge)->call_stmt_size);
 301 #endif
 302   return (estimate_edge_size (edge)
 303           - inline_edge_summary (edge)->call_stmt_size);
 304 }
 305
 306 /* Return estimated callee runtime increase after inlning
 307    EDGE.  */
 308
 309 static inline int
 310 estimate_edge_time (struct cgraph_edge *edge)
 311 {
 312   int ret;
 313   if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache) <= edge->uid
 314       || !(ret = VEC_index (edge_growth_cache_entry,
 315                             edge_growth_cache,
 316                             edge->uid).time))
 317     return do_estimate_edge_time (edge);
 318   return ret - (ret > 0);
 319 }
 320
 321
 322 /* Return estimated callee runtime increase after inlning
 323    EDGE.  */
 324
 325 static inline inline_hints
 326 estimate_edge_hints (struct cgraph_edge *edge)
 327 {
 328   inline_hints ret;
 329   if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache) <= edge->uid
 330       || !(ret = VEC_index (edge_growth_cache_entry,
 331                             edge_growth_cache,
 332                             edge->uid).hints))
 333     return do_estimate_edge_hints (edge);
 334   return ret - 1;
 335 }
 336
 337
 338 /* Reset cached value for NODE.  */
 339
 340 static inline void
 341 reset_node_growth_cache (struct cgraph_node *node)
 342 {
 343   if ((int)VEC_length (int, node_growth_cache) > node->uid)
 344     VEC_replace (int, node_growth_cache, node->uid, 0);
 345 }
 346
 347 /* Reset cached value for EDGE.  */
 348
 349 static inline void
 350 reset_edge_growth_cache (struct cgraph_edge *edge)
 351 {
 352   if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache) > edge->uid)
 353     {
 354       struct edge_growth_cache_entry zero = {0, 0, 0};
 355       VEC_replace (edge_growth_cache_entry, edge_growth_cache, edge->uid, zero);
 356     }
 357 }