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