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