1/* IPA function body analysis. 2 Copyright (C) 2003-2020 Free Software Foundation, Inc. 3 Contributed by Jan Hubicka 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 3, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING3. If not see 19<http://www.gnu.org/licenses/>. */ 20 21#ifndef GCC_IPA_SUMMARY_H 22#define GCC_IPA_SUMMARY_H 23 24#include "sreal.h" 25#include "ipa-predicate.h" 26 27 28/* Hints are reasons why IPA heuristics should prefer specializing given 29 function. They are represented as bitmap of the following values. */ 30enum ipa_hints_vals { 31 /* When specialization turns indirect call into a direct call, 32 it is good idea to do so. */ 33 INLINE_HINT_indirect_call = 1, 34 /* Inlining may make loop iterations or loop stride known. It is good idea 35 to do so because it enables loop optimizations. */ 36 INLINE_HINT_loop_iterations = 2, 37 INLINE_HINT_loop_stride = 4, 38 /* Inlining within same strongly connected component of callgraph is often 39 a loss due to increased stack frame usage and prologue setup costs. */ 40 INLINE_HINT_same_scc = 8, 41 /* Inlining functions in strongly connected component is not such a great 42 win. */ 43 INLINE_HINT_in_scc = 16, 44 /* If function is declared inline by user, it may be good idea to inline 45 it. Set by simple_edge_hints in ipa-inline-analysis.c. */ 46 INLINE_HINT_declared_inline = 32, 47 /* Programs are usually still organized for non-LTO compilation and thus 48 if functions are in different modules, inlining may not be so important. 49 Set by simple_edge_hints in ipa-inline-analysis.c. */ 50 INLINE_HINT_cross_module = 64, 51 /* We know that the callee is hot by profile. */ 52 INLINE_HINT_known_hot = 128 53}; 54 55typedef int ipa_hints; 56 57/* Simple description of whether a memory load or a condition refers to a load 58 from an aggregate and if so, how and where from in the aggregate. 59 Individual fields have the same meaning like fields with the same name in 60 struct condition. */ 61 62struct agg_position_info 63{ 64 HOST_WIDE_INT offset; 65 bool agg_contents; 66 bool by_ref; 67}; 68 69/* Representation of function body size and time depending on the call 70 context. We keep simple array of record, every containing of predicate 71 and time/size to account. */ 72class GTY(()) size_time_entry 73{ 74public: 75 /* Predicate for code to be executed. */ 76 predicate exec_predicate; 77 /* Predicate for value to be constant and optimized out in a specialized copy. 78 When deciding on specialization this makes it possible to see how much 79 the executed code paths will simplify. */ 80 predicate nonconst_predicate; 81 int size; 82 sreal GTY((skip)) time; 83}; 84 85/* Summary about function and stack frame sizes. We keep this info 86 for inline clones and also for WPA streaming. For this reason this is not 87 part of ipa_fn_summary which exists only for offline functions. */ 88class ipa_size_summary 89{ 90public: 91 /* Estimated stack frame consumption by the function. */ 92 HOST_WIDE_INT estimated_self_stack_size; 93 /* Size of the function body. */ 94 int self_size; 95 /* Estimated size of the function after inlining. */ 96 int size; 97 98 ipa_size_summary () 99 : estimated_self_stack_size (0), self_size (0), size (0) 100 { 101 } 102}; 103 104/* Function inlining information. */ 105class GTY(()) ipa_fn_summary 106{ 107public: 108 /* Keep all field empty so summary dumping works during its computation. 109 This is useful for debugging. */ 110 ipa_fn_summary () 111 : min_size (0), 112 inlinable (false), single_caller (false), 113 fp_expressions (false), estimated_stack_size (false), 114 time (0), conds (NULL), 115 size_time_table (NULL), call_size_time_table (NULL), loop_iterations (NULL), 116 loop_stride (NULL), growth (0), scc_no (0) 117 { 118 } 119 120 /* Copy constructor. */ 121 ipa_fn_summary (const ipa_fn_summary &s) 122 : min_size (s.min_size), 123 inlinable (s.inlinable), single_caller (s.single_caller), 124 fp_expressions (s.fp_expressions), 125 estimated_stack_size (s.estimated_stack_size), 126 time (s.time), conds (s.conds), size_time_table (s.size_time_table), 127 call_size_time_table (NULL), 128 loop_iterations (s.loop_iterations), loop_stride (s.loop_stride), 129 growth (s.growth), scc_no (s.scc_no) 130 {} 131 132 /* Default constructor. */ 133 ~ipa_fn_summary (); 134 135 /* Information about the function body itself. */ 136 137 /* Minimal size increase after inlining. */ 138 int min_size; 139 140 /* False when there something makes inlining impossible (such as va_arg). */ 141 unsigned inlinable : 1; 142 /* True wen there is only one caller of the function before small function 143 inlining. */ 144 unsigned int single_caller : 1; 145 /* True if function contains any floating point expressions. */ 146 unsigned int fp_expressions : 1; 147 148 /* Information about function that will result after applying all the 149 inline decisions present in the callgraph. Generally kept up to 150 date only for functions that are not inline clones. */ 151 152 /* Estimated stack frame consumption by the function. */ 153 HOST_WIDE_INT estimated_stack_size; 154 /* Estimated runtime of function after inlining. */ 155 sreal GTY((skip)) time; 156 157 /* Conditional size/time information. The summaries are being 158 merged during inlining. */ 159 conditions conds; 160 /* Normal code is accounted in size_time_table, while calls are 161 accounted in call_size_time_table. This is because calls 162 are often adjusted by IPA optimizations and thus this summary 163 is generated from call summary information when needed. */ 164 vec<size_time_entry, va_gc> *size_time_table; 165 vec<size_time_entry, va_gc> *call_size_time_table; 166 167 /* Predicate on when some loop in the function becomes to have known 168 bounds. */ 169 predicate * GTY((skip)) loop_iterations; 170 /* Predicate on when some loop in the function becomes to have known 171 stride. */ 172 predicate * GTY((skip)) loop_stride; 173 /* Estimated growth for inlining all copies of the function before start 174 of small functions inlining. 175 This value will get out of date as the callers are duplicated, but 176 using up-to-date value in the badness metric mean a lot of extra 177 expenses. */ 178 int growth; 179 /* Number of SCC on the beginning of inlining process. */ 180 int scc_no; 181 182 /* Record time and size under given predicates. */ 183 void account_size_time (int, sreal, const predicate &, const predicate &, 184 bool call = false); 185 186 /* We keep values scaled up, so fractional sizes can be accounted. */ 187 static const int size_scale = 2; 188 /* Maximal size of size_time_table before we start to be conservative. */ 189 static const int max_size_time_table_size = 256; 190}; 191 192class GTY((user)) ipa_fn_summary_t: 193 public fast_function_summary <ipa_fn_summary *, va_gc> 194{ 195public: 196 ipa_fn_summary_t (symbol_table *symtab): 197 fast_function_summary <ipa_fn_summary *, va_gc> (symtab) {} 198 199 static ipa_fn_summary_t *create_ggc (symbol_table *symtab) 200 { 201 class ipa_fn_summary_t *summary 202 = new (ggc_alloc_no_dtor<ipa_fn_summary_t> ()) ipa_fn_summary_t (symtab); 203 summary->disable_insertion_hook (); 204 return summary; 205 } 206 207 /* Remove ipa_fn_summary for all callees of NODE. */ 208 void remove_callees (cgraph_node *node); 209 210 virtual void insert (cgraph_node *, ipa_fn_summary *); 211 virtual void remove (cgraph_node *node, ipa_fn_summary *) 212 { 213 remove_callees (node); 214 } 215 216 virtual void duplicate (cgraph_node *src, cgraph_node *dst, 217 ipa_fn_summary *src_data, ipa_fn_summary *dst_data); 218}; 219 220extern GTY(()) fast_function_summary <ipa_fn_summary *, va_gc> 221 *ipa_fn_summaries; 222 223class ipa_size_summary_t: 224 public fast_function_summary <ipa_size_summary *, va_heap> 225{ 226public: 227 ipa_size_summary_t (symbol_table *symtab): 228 fast_function_summary <ipa_size_summary *, va_heap> (symtab) 229 { 230 disable_insertion_hook (); 231 } 232 233 virtual void duplicate (cgraph_node *, cgraph_node *, 234 ipa_size_summary *src_data, 235 ipa_size_summary *dst_data) 236 { 237 *dst_data = *src_data; 238 } 239}; 240extern fast_function_summary <ipa_size_summary *, va_heap> 241 *ipa_size_summaries; 242 243/* Information kept about callgraph edges. */ 244class ipa_call_summary 245{ 246public: 247 /* Keep all field empty so summary dumping works during its computation. 248 This is useful for debugging. */ 249 ipa_call_summary () 250 : predicate (NULL), param (vNULL), call_stmt_size (0), call_stmt_time (0), 251 loop_depth (0), is_return_callee_uncaptured (false) 252 { 253 } 254 255 /* Copy constructor. */ 256 ipa_call_summary (const ipa_call_summary &s): 257 predicate (s.predicate), param (s.param), call_stmt_size (s.call_stmt_size), 258 call_stmt_time (s.call_stmt_time), loop_depth (s.loop_depth), 259 is_return_callee_uncaptured (s.is_return_callee_uncaptured) 260 { 261 } 262 263 /* Default destructor. */ 264 ~ipa_call_summary (); 265 266 class predicate *predicate; 267 /* Vector indexed by parameters. */ 268 vec<inline_param_summary> param; 269 /* Estimated size and time of the call statement. */ 270 int call_stmt_size; 271 int call_stmt_time; 272 /* Depth of loop nest, 0 means no nesting. */ 273 unsigned int loop_depth; 274 /* Indicates whether the caller returns the value of it's callee. */ 275 bool is_return_callee_uncaptured; 276}; 277 278class ipa_call_summary_t: public fast_call_summary <ipa_call_summary *, va_heap> 279{ 280public: 281 ipa_call_summary_t (symbol_table *symtab): 282 fast_call_summary <ipa_call_summary *, va_heap> (symtab) {} 283 284 /* Hook that is called by summary when an edge is duplicated. */ 285 virtual void duplicate (cgraph_edge *src, cgraph_edge *dst, 286 ipa_call_summary *src_data, 287 ipa_call_summary *dst_data); 288}; 289 290/* This object describe a context of call. That is a summary of known 291 information about its parameters. Main purpose of this context is 292 to give more realistic estimations of function runtime, size and 293 inline hints. */ 294class ipa_call_context 295{ 296public: 297 ipa_call_context (cgraph_node *node, 298 clause_t possible_truths, 299 clause_t nonspec_possible_truths, 300 vec<tree> known_vals, 301 vec<ipa_polymorphic_call_context> known_contexts, 302 vec<ipa_agg_value_set> known_aggs, 303 vec<inline_param_summary> m_inline_param_summary); 304 ipa_call_context () 305 : m_node(NULL) 306 { 307 } 308 void estimate_size_and_time (int *ret_size, int *ret_min_size, 309 sreal *ret_time, 310 sreal *ret_nonspecialized_time, 311 ipa_hints *ret_hints); 312 void duplicate_from (const ipa_call_context &ctx); 313 void release (bool all = false); 314 bool equal_to (const ipa_call_context &); 315 bool exists_p () 316 { 317 return m_node != NULL; 318 } 319private: 320 /* Called function. */ 321 cgraph_node *m_node; 322 /* Clause describing what predicate conditionals can be satisfied 323 in this context if function is inlined/specialized. */ 324 clause_t m_possible_truths; 325 /* Clause describing what predicate conditionals can be satisfied 326 in this context if function is kept offline. */ 327 clause_t m_nonspec_possible_truths; 328 /* Inline summary maintains info about change probabilities. */ 329 vec<inline_param_summary> m_inline_param_summary; 330 331 /* The following is used only to resolve indirect calls. */ 332 333 /* Vector describing known values of parameters. */ 334 vec<tree> m_known_vals; 335 /* Vector describing known polymorphic call contexts. */ 336 vec<ipa_polymorphic_call_context> m_known_contexts; 337 /* Vector describing known aggregate values. */ 338 vec<ipa_agg_value_set> m_known_aggs; 339}; 340 341extern fast_call_summary <ipa_call_summary *, va_heap> *ipa_call_summaries; 342 343/* In ipa-fnsummary.c */ 344void ipa_debug_fn_summary (struct cgraph_node *); 345void ipa_dump_fn_summaries (FILE *f); 346void ipa_dump_fn_summary (FILE *f, struct cgraph_node *node); 347void ipa_dump_hints (FILE *f, ipa_hints); 348void ipa_free_fn_summary (void); 349void ipa_free_size_summary (void); 350void inline_analyze_function (struct cgraph_node *node); 351void estimate_ipcp_clone_size_and_time (struct cgraph_node *, 352 vec<tree>, 353 vec<ipa_polymorphic_call_context>, 354 vec<ipa_agg_value_set>, 355 int *, sreal *, sreal *, 356 ipa_hints *); 357void ipa_merge_fn_summary_after_inlining (struct cgraph_edge *edge); 358void ipa_update_overall_fn_summary (struct cgraph_node *node, bool reset = true); 359void compute_fn_summary (struct cgraph_node *, bool); 360 361 362void evaluate_properties_for_edge (struct cgraph_edge *e, 363 bool inline_p, 364 clause_t *clause_ptr, 365 clause_t *nonspec_clause_ptr, 366 vec<tree> *known_vals_ptr, 367 vec<ipa_polymorphic_call_context> 368 *known_contexts_ptr, 369 vec<ipa_agg_value_set> *); 370 371void ipa_fnsummary_c_finalize (void); 372HOST_WIDE_INT ipa_get_stack_frame_offset (struct cgraph_node *node); 373void ipa_remove_from_growth_caches (struct cgraph_edge *edge); 374 375/* Return true if EDGE is a cross module call. */ 376 377static inline bool 378cross_module_call_p (struct cgraph_edge *edge) 379{ 380 /* Here we do not want to walk to alias target becuase ICF may create 381 cross-unit aliases. */ 382 if (edge->caller->unit_id == edge->callee->unit_id) 383 return false; 384 /* If the call is to a (former) comdat function or s symbol with mutiple 385 extern inline definitions then treat is as in-module call. */ 386 if (edge->callee->merged_extern_inline || edge->callee->merged_comdat 387 || DECL_COMDAT (edge->callee->decl)) 388 return false; 389 return true; 390} 391 392#endif /* GCC_IPA_FNSUMMARY_H */ 393