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 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   /* False when there something makes versioning impossible.
  89      Currently computed and used only by ipa-cp.  */
  90   unsigned versionable : 1;
  91
  92   /* Information about function that will result after applying all the
  93      inline decisions present in the callgraph.  Generally kept up to
  94      date only for functions that are not inline clones. */
  95
  96   /* Estimated stack frame consumption by the function.  */
  97   HOST_WIDE_INT estimated_stack_size;
  98   /* Expected offset of the stack frame of inlined function.  */
  99   HOST_WIDE_INT stack_frame_offset;
 100   /* Estimated size of the function after inlining.  */
 101   int time;
 102   int size;
 103
 104   conditions conds;
 105   VEC(size_time_entry,gc) *entry;
 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 typedef struct edge_growth_cache_entry
 114 {
 115   int time, size;
 116 } edge_growth_cache_entry;
 117 DEF_VEC_O(edge_growth_cache_entry);
 118 DEF_VEC_ALLOC_O(edge_growth_cache_entry,heap);
 119
 120 extern VEC(int,heap) *node_growth_cache;
 121 extern VEC(edge_growth_cache_entry,heap) *edge_growth_cache;
 122
 123 /* In ipa-inline-analysis.c  */
 124 void debug_inline_summary (struct cgraph_node *);
 125 void dump_inline_summaries (FILE *f);
 126 void inline_generate_summary (void);
 127 void inline_read_summary (void);
 128 void inline_write_summary (cgraph_node_set, varpool_node_set);
 129 void inline_free_summary (void);
 130 void initialize_inline_failed (struct cgraph_edge *);
 131 int estimate_time_after_inlining (struct cgraph_node *, struct cgraph_edge *);
 132 int estimate_size_after_inlining (struct cgraph_node *, struct cgraph_edge *);
 133 int do_estimate_growth (struct cgraph_node *);
 134 void inline_merge_summary (struct cgraph_edge *edge);
 135 int do_estimate_edge_growth (struct cgraph_edge *edge);
 136 int do_estimate_edge_time (struct cgraph_edge *edge);
 137 void initialize_growth_caches (void);
 138 void free_growth_caches (void);
 139 void compute_inline_parameters (struct cgraph_node *, bool);
 140
 141 /* In ipa-inline-transform.c  */
 142 bool inline_call (struct cgraph_edge *, bool, VEC (cgraph_edge_p, heap) **, int *);
 143 unsigned int inline_transform (struct cgraph_node *);
 144 void clone_inlined_nodes (struct cgraph_edge *e, bool, bool, int *);
 145
 146 extern int ncalls_inlined;
 147 extern int nfunctions_inlined;
 148
 149 static inline struct inline_summary *
 150 inline_summary (struct cgraph_node *node)
 151 {
 152   return VEC_index (inline_summary_t, inline_summary_vec, node->uid);
 153 }
 154
 155
 156 /* Return estimated unit growth after inlning all calls to NODE.
 157    Quick accesors to the inline growth caches.
 158    For convenience we keep zero 0 as unknown.  Because growth
 159    can be both positive and negative, we simply increase positive
 160    growths by 1. */
 161 static inline int
 162 estimate_growth (struct cgraph_node *node)
 163 {
 164   int ret;
 165   if ((int)VEC_length (int, node_growth_cache) <= node->uid
 166       || !(ret = VEC_index (int, node_growth_cache, node->uid)))
 167     return do_estimate_growth (node);
 168   return ret - (ret > 0);
 169 }
 170
 171
 172 /* Return estimated callee growth after inlining EDGE.  */
 173
 174 static inline int
 175 estimate_edge_growth (struct cgraph_edge *edge)
 176 {
 177   int ret;
 178   if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache) <= edge->uid
 179       || !(ret = VEC_index (edge_growth_cache_entry,
 180                             edge_growth_cache,
 181                             edge->uid)->size))
 182     return do_estimate_edge_growth (edge);
 183   return ret - (ret > 0);
 184 }
 185
 186
 187 /* Return estimated callee runtime increase after inlning
 188    EDGE.  */
 189
 190 static inline int
 191 estimate_edge_time (struct cgraph_edge *edge)
 192 {
 193   int ret;
 194   if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache) <= edge->uid
 195       || !(ret = VEC_index (edge_growth_cache_entry,
 196                             edge_growth_cache,
 197                             edge->uid)->size))
 198     return do_estimate_edge_time (edge);
 199   return ret - (ret > 0);
 200 }
 201
 202
 203 /* Reset cached value for NODE.  */
 204
 205 static inline void
 206 reset_node_growth_cache (struct cgraph_node *node)
 207 {
 208   if ((int)VEC_length (int, node_growth_cache) > node->uid)
 209     VEC_replace (int, node_growth_cache, node->uid, 0);
 210 }
 211
 212 /* Reset cached value for EDGE.  */
 213
 214 static inline void
 215 reset_edge_growth_cache (struct cgraph_edge *edge)
 216 {
 217   if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache) > edge->uid)
 218     {
 219       struct edge_growth_cache_entry zero = {0, 0};
 220       VEC_replace (edge_growth_cache_entry, edge_growth_cache, edge->uid, &zero);
 221     }
 222 }