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 /* Representation of inline parameters that do depend on context function is
  23    inlined into (i.e. known constant values of function parameters.
  24
  25    Conditions that are interesting for function body are collected into CONDS
  26    vector.  They are of simple for  function_param OP VAL, where VAL is
  27    IPA invariant.  The conditions are then referred by predicates.  */
  28
  29 typedef struct GTY(()) condition
  30   {
  31     /* If agg_contents is set, this is the offset from which the used data was
  32        loaded.  */
  33     HOST_WIDE_INT offset;
  34     tree val;
  35     int operand_num;
  36     ENUM_BITFIELD(tree_code) code : 16;
  37     /* Set if the used data were loaded from an aggregate parameter or from
  38        data received by reference.  */
  39     unsigned agg_contents : 1;
  40     /* If agg_contents is set, this differentiates between loads from data
  41        passed by reference and by value.  */
  42     unsigned by_ref : 1;
  43   } condition;
  44
  45 /* Inline hints are reasons why inline heuristics should preffer inlining given function.
  46    They are represtented as bitmap of the following values.  */
  47 enum inline_hints_vals {
  48   INLINE_HINT_indirect_call = 1,
  49   INLINE_HINT_loop_iterations = 2,
  50   INLINE_HINT_loop_stride = 4
  51 };
  52 typedef int inline_hints;
  53
  54 DEF_VEC_O (condition);
  55 DEF_VEC_ALLOC_O (condition, gc);
  56
  57 typedef VEC(condition,gc) *conditions;
  58
  59 /* Representation of predicates i.e. formulas using conditions defined
  60    above.  Predicates are simple logical formulas in conjunctive-disjunctive
  61    form.
  62
  63    Predicate is array of clauses terminated by 0.  Every clause must be true
  64    in order to make predicate true.
  65    Clauses are represented as bitmaps of conditions. One of conditions
  66    must be true in order for clause to be true.  */
  67
  68 #define MAX_CLAUSES 8
  69 typedef unsigned int clause_t;
  70 struct GTY(()) predicate
  71 {
  72   clause_t clause[MAX_CLAUSES + 1];
  73 };
  74
  75 /* Represnetation of function body size and time depending on the inline
  76    context.  We keep simple array of record, every containing of predicate
  77    and time/size to account.
  78
  79    We keep values scaled up, so fractional sizes and times can be
  80    accounted.  */
  81 #define INLINE_SIZE_SCALE 2
  82 #define INLINE_TIME_SCALE (CGRAPH_FREQ_BASE * 2)
  83 typedef struct GTY(()) size_time_entry
  84 {
  85   struct predicate predicate;
  86   int size;
  87   int time;
  88 } size_time_entry;
  89 DEF_VEC_O (size_time_entry);
  90 DEF_VEC_ALLOC_O (size_time_entry, gc);
  91
  92 /* Function inlining information.  */
  93 struct GTY(()) inline_summary
  94 {
  95   /* Information about the function body itself.  */
  96
  97   /* Estimated stack frame consumption by the function.  */
  98   HOST_WIDE_INT estimated_self_stack_size;
  99   /* Size of the function body.  */
 100   int self_size;
 101   /* Time of the function body.  */
 102   int self_time;
 103
 104   /* False when there something makes inlining impossible (such as va_arg).  */
 105   unsigned inlinable : 1;
 106
 107   /* Information about function that will result after applying all the
 108      inline decisions present in the callgraph.  Generally kept up to
 109      date only for functions that are not inline clones. */
 110
 111   /* Estimated stack frame consumption by the function.  */
 112   HOST_WIDE_INT estimated_stack_size;
 113   /* Expected offset of the stack frame of inlined function.  */
 114   HOST_WIDE_INT stack_frame_offset;
 115   /* Estimated size of the function after inlining.  */
 116   int time;
 117   int size;
 118
 119   /* Conditional size/time information.  The summaries are being
 120      merged during inlining.  */
 121   conditions conds;
 122   VEC(size_time_entry,gc) *entry;
 123
 124   /* Predicate on when some loop in the function becomes to have known
 125      bounds.   */
 126   struct predicate * GTY((skip)) loop_iterations;
 127   /* Predicate on when some loop in the function becomes to have known
 128      stride.   */
 129   struct predicate * GTY((skip)) loop_stride;
 130 };
 131
 132
 133 typedef struct inline_summary inline_summary_t;
 134 DEF_VEC_O(inline_summary_t);
 135 DEF_VEC_ALLOC_O(inline_summary_t,gc);
 136 extern GTY(()) VEC(inline_summary_t,gc) *inline_summary_vec;
 137
 138 /* Information kept about parameter of call site.  */
 139 struct inline_param_summary
 140 {
 141   /* REG_BR_PROB_BASE based probability that parameter will change in between
 142      two invocation of the calls.
 143      I.e. loop invariant parameters
 144      REG_BR_PROB_BASE/estimated_iterations and regular
 145      parameters REG_BR_PROB_BASE.
 146
 147      Value 0 is reserved for compile time invariants. */
 148   int change_prob;
 149 };
 150 typedef struct inline_param_summary inline_param_summary_t;
 151 DEF_VEC_O(inline_param_summary_t);
 152 DEF_VEC_ALLOC_O(inline_param_summary_t,heap);
 153
 154 /* Information kept about callgraph edges.  */
 155 struct inline_edge_summary
 156 {
 157   /* Estimated size and time of the call statement.  */
 158   int call_stmt_size;
 159   int call_stmt_time;
 160   /* Depth of loop nest, 0 means no nesting.  */
 161   unsigned short int loop_depth;
 162   struct predicate *predicate;
 163   /* Array indexed by parameters.
 164      0 means that parameter change all the time, REG_BR_PROB_BASE means
 165      that parameter is constant.  */
 166   VEC (inline_param_summary_t, heap) *param;
 167 };
 168
 169 typedef struct inline_edge_summary inline_edge_summary_t;
 170 DEF_VEC_O(inline_edge_summary_t);
 171 DEF_VEC_ALLOC_O(inline_edge_summary_t,heap);
 172 extern VEC(inline_edge_summary_t,heap) *inline_edge_summary_vec;
 173
 174 typedef struct edge_growth_cache_entry
 175 {
 176   int time, size;
 177   inline_hints hints;
 178 } edge_growth_cache_entry;
 179 DEF_VEC_O(edge_growth_cache_entry);
 180 DEF_VEC_ALLOC_O(edge_growth_cache_entry,heap);
 181
 182 extern VEC(int,heap) *node_growth_cache;
 183 extern VEC(edge_growth_cache_entry,heap) *edge_growth_cache;
 184
 185 /* In ipa-inline-analysis.c  */
 186 void debug_inline_summary (struct cgraph_node *);
 187 void dump_inline_summaries (FILE *f);
 188 void dump_inline_summary (FILE *f, struct cgraph_node *node);
 189 void dump_inline_hints (FILE *f, inline_hints);
 190 void inline_generate_summary (void);
 191 void inline_read_summary (void);
 192 void inline_write_summary (void);
 193 void inline_free_summary (void);
 194 void initialize_inline_failed (struct cgraph_edge *);
 195 int estimate_time_after_inlining (struct cgraph_node *, struct cgraph_edge *);
 196 int estimate_size_after_inlining (struct cgraph_node *, struct cgraph_edge *);
 197 void estimate_ipcp_clone_size_and_time (struct cgraph_node *,
 198                                         VEC (tree, heap) *known_vals,
 199                                         VEC (tree, heap) *known_binfos,
 200                                         int *, int *);
 201 int do_estimate_growth (struct cgraph_node *);
 202 void inline_merge_summary (struct cgraph_edge *edge);
 203 void inline_update_overall_summary (struct cgraph_node *node);
 204 int do_estimate_edge_size (struct cgraph_edge *edge);
 205 int do_estimate_edge_time (struct cgraph_edge *edge);
 206 inline_hints do_estimate_edge_hints (struct cgraph_edge *edge);
 207 void initialize_growth_caches (void);
 208 void free_growth_caches (void);
 209 void compute_inline_parameters (struct cgraph_node *, bool);
 210
 211 /* In ipa-inline-transform.c  */
 212 bool inline_call (struct cgraph_edge *, bool, VEC (cgraph_edge_p, heap) **, int *, bool);
 213 unsigned int inline_transform (struct cgraph_node *);
 214 void clone_inlined_nodes (struct cgraph_edge *e, bool, bool, int *);
 215
 216 extern int ncalls_inlined;
 217 extern int nfunctions_inlined;
 218
 219 static inline struct inline_summary *
 220 inline_summary (struct cgraph_node *node)
 221 {
 222   return &VEC_index (inline_summary_t, inline_summary_vec, node->uid);
 223 }
 224
 225 static inline struct inline_edge_summary *
 226 inline_edge_summary (struct cgraph_edge *edge)
 227 {
 228   return &VEC_index (inline_edge_summary_t,
 229                     inline_edge_summary_vec, edge->uid);
 230 }
 231
 232 /* Return estimated unit growth after inlning all calls to NODE.
 233    Quick accesors to the inline growth caches.
 234    For convenience we keep zero 0 as unknown.  Because growth
 235    can be both positive and negative, we simply increase positive
 236    growths by 1. */
 237 static inline int
 238 estimate_growth (struct cgraph_node *node)
 239 {
 240   int ret;
 241   if ((int)VEC_length (int, node_growth_cache) <= node->uid
 242       || !(ret = VEC_index (int, node_growth_cache, node->uid)))
 243     return do_estimate_growth (node);
 244   return ret - (ret > 0);
 245 }
 246
 247
 248 /* Return estimated size of the inline sequence of EDGE.  */
 249
 250 static inline int
 251 estimate_edge_size (struct cgraph_edge *edge)
 252 {
 253   int ret;
 254   if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache) <= edge->uid
 255       || !(ret = VEC_index (edge_growth_cache_entry,
 256                             edge_growth_cache,
 257                             edge->uid).size))
 258     return do_estimate_edge_size (edge);
 259   return ret - (ret > 0);
 260 }
 261
 262 /* Return estimated callee growth after inlining EDGE.  */
 263
 264 static inline int
 265 estimate_edge_growth (struct cgraph_edge *edge)
 266 {
 267 #ifdef ENABLE_CHECKING
 268   gcc_checking_assert (inline_edge_summary (edge)->call_stmt_size);
 269 #endif
 270   return (estimate_edge_size (edge)
 271           - inline_edge_summary (edge)->call_stmt_size);
 272 }
 273
 274 /* Return estimated callee runtime increase after inlning
 275    EDGE.  */
 276
 277 static inline int
 278 estimate_edge_time (struct cgraph_edge *edge)
 279 {
 280   int ret;
 281   if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache) <= edge->uid
 282       || !(ret = VEC_index (edge_growth_cache_entry,
 283                             edge_growth_cache,
 284                             edge->uid).time))
 285     return do_estimate_edge_time (edge);
 286   return ret - (ret > 0);
 287 }
 288
 289
 290 /* Return estimated callee runtime increase after inlning
 291    EDGE.  */
 292
 293 static inline inline_hints
 294 estimate_edge_hints (struct cgraph_edge *edge)
 295 {
 296   inline_hints ret;
 297   if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache) <= edge->uid
 298       || !(ret = VEC_index (edge_growth_cache_entry,
 299                             edge_growth_cache,
 300                             edge->uid).hints))
 301     return do_estimate_edge_hints (edge);
 302   return ret - 1;
 303 }
 304
 305
 306 /* Reset cached value for NODE.  */
 307
 308 static inline void
 309 reset_node_growth_cache (struct cgraph_node *node)
 310 {
 311   if ((int)VEC_length (int, node_growth_cache) > node->uid)
 312     VEC_replace (int, node_growth_cache, node->uid, 0);
 313 }
 314
 315 /* Reset cached value for EDGE.  */
 316
 317 static inline void
 318 reset_edge_growth_cache (struct cgraph_edge *edge)
 319 {
 320   if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache) > edge->uid)
 321     {
 322       struct edge_growth_cache_entry zero = {0, 0, 0};
 323       VEC_replace (edge_growth_cache_entry, edge_growth_cache, edge->uid, zero);
 324     }
 325 }