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