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 VEC (tree, heap) *known_binfos, 173 int *, int *); 174 int do_estimate_growth (struct cgraph_node *); 175 void inline_merge_summary (struct cgraph_edge *edge); 176 int do_estimate_edge_growth (struct cgraph_edge *edge); 177 int do_estimate_edge_time (struct cgraph_edge *edge); 178 void initialize_growth_caches (void); 179 void free_growth_caches (void); 180 void compute_inline_parameters (struct cgraph_node *, bool); 181 182 /* In ipa-inline-transform.c */ 183 bool inline_call (struct cgraph_edge *, bool, VEC (cgraph_edge_p, heap) **, int *); 184 unsigned int inline_transform (struct cgraph_node *); 185 void clone_inlined_nodes (struct cgraph_edge *e, bool, bool, int *); 186 187 extern int ncalls_inlined; 188 extern int nfunctions_inlined; 189 190 static inline struct inline_summary * 191 inline_summary (struct cgraph_node *node) 192 { 193 return VEC_index (inline_summary_t, inline_summary_vec, node->uid); 194 } 195 196 static inline struct inline_edge_summary * 197 inline_edge_summary (struct cgraph_edge *edge) 198 { 199 return VEC_index (inline_edge_summary_t, 200 inline_edge_summary_vec, edge->uid); 201 } 202 203 /* Return estimated unit growth after inlning all calls to NODE. 204 Quick accesors to the inline growth caches. 205 For convenience we keep zero 0 as unknown. Because growth 206 can be both positive and negative, we simply increase positive 207 growths by 1. */ 208 static inline int 209 estimate_growth (struct cgraph_node *node) 210 { 211 int ret; 212 if ((int)VEC_length (int, node_growth_cache) <= node->uid 213 || !(ret = VEC_index (int, node_growth_cache, node->uid))) 214 return do_estimate_growth (node); 215 return ret - (ret > 0); 216 } 217 218 219 /* Return estimated callee growth after inlining EDGE. */ 220 221 static inline int 222 estimate_edge_growth (struct cgraph_edge *edge) 223 { 224 int ret; 225 if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache) <= edge->uid 226 || !(ret = VEC_index (edge_growth_cache_entry, 227 edge_growth_cache, 228 edge->uid)->size)) 229 return do_estimate_edge_growth (edge); 230 return ret - (ret > 0); 231 } 232 233 234 /* Return estimated callee runtime increase after inlning 235 EDGE. */ 236 237 static inline int 238 estimate_edge_time (struct cgraph_edge *edge) 239 { 240 int ret; 241 if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache) <= edge->uid 242 || !(ret = VEC_index (edge_growth_cache_entry, 243 edge_growth_cache, 244 edge->uid)->time)) 245 return do_estimate_edge_time (edge); 246 return ret - (ret > 0); 247 } 248 249 250 /* Reset cached value for NODE. */ 251 252 static inline void 253 reset_node_growth_cache (struct cgraph_node *node) 254 { 255 if ((int)VEC_length (int, node_growth_cache) > node->uid) 256 VEC_replace (int, node_growth_cache, node->uid, 0); 257 } 258 259 /* Reset cached value for EDGE. */ 260 261 static inline void 262 reset_edge_growth_cache (struct cgraph_edge *edge) 263 { 264 if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache) > edge->uid) 265 { 266 struct edge_growth_cache_entry zero = {0, 0}; 267 VEC_replace (edge_growth_cache_entry, edge_growth_cache, edge->uid, &zero); 268 } 269 } 270