gcc/ipa-fnsummary.h

   1 /* IPA function body analysis.
   2    Copyright (C) 2003-2024 Free Software Foundation, Inc.
   3    Contributed by Jan Hubicka
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along 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.  */
  30 enum 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.cc.  */
  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.cc.   */
  50   INLINE_HINT_cross_module = 64,
  51   /* We know that the callee is hot by profile.  */
  52   INLINE_HINT_known_hot = 128,
  53   /* There is builtin_constant_p dependent on parameter which is usually
  54      a strong hint to inline.  */
  55   INLINE_HINT_builtin_constant_p = 256
  56 };
  57
  58 typedef int ipa_hints;
  59
  60 /* Simple description of whether a memory load or a condition refers to a load
  61    from an aggregate and if so, how and where from in the aggregate.
  62    Individual fields have the same meaning like fields with the same name in
  63    struct condition.  */
  64
  65 struct agg_position_info
  66 {
  67   HOST_WIDE_INT offset;
  68   bool agg_contents;
  69   bool by_ref;
  70 };
  71
  72 /* Representation of function body size and time depending on the call
  73    context.  We keep simple array of record, every containing of predicate
  74    and time/size to account.  */
  75 class size_time_entry
  76 {
  77 public:
  78   /* Predicate for code to be executed.  */
  79   ipa_predicate exec_predicate;
  80   /* Predicate for value to be constant and optimized out in a specialized copy.
  81      When deciding on specialization this makes it possible to see how much
  82      the executed code paths will simplify.  */
  83   ipa_predicate nonconst_predicate;
  84   int size;
  85   sreal time;
  86 };
  87
  88 /* Summary about function and stack frame sizes.  We keep this info
  89    for inline clones and also for WPA streaming. For this reason this is not
  90    part of ipa_fn_summary which exists only for offline functions.  */
  91 class ipa_size_summary
  92 {
  93 public:
  94   /* Estimated stack frame consumption by the function.  */
  95   HOST_WIDE_INT estimated_self_stack_size;
  96   /* Size of the function body.  */
  97   int self_size;
  98   /* Estimated size of the function after inlining.  */
  99   int size;
 100
 101   ipa_size_summary ()
 102   : estimated_self_stack_size (0), self_size (0), size (0)
 103   {
 104   }
 105 };
 106
 107 /* Structure to capture how frequently some interesting events occur given a
 108    particular predicate.  The structure is used to estimate how often we
 109    encounter loops with known iteration count or stride in various
 110    contexts.  */
 111
 112 struct GTY(()) ipa_freqcounting_predicate
 113 {
 114   /* The described event happens with this frequency... */
 115   sreal freq;
 116   /* ...when this predicate evaluates to false. */
 117   ipa_predicate * GTY((skip)) predicate;
 118 };
 119
 120 /* Function inlining information.  */
 121 class GTY(()) ipa_fn_summary
 122 {
 123 public:
 124   /* Keep all field empty so summary dumping works during its computation.
 125      This is useful for debugging.  */
 126   ipa_fn_summary ()
 127     : min_size (0),
 128       inlinable (false), single_caller (false),
 129       fp_expressions (false), safe_to_inline_to_always_inline (0),
 130       target_info (0), estimated_stack_size (false),
 131       time (0), conds (NULL),
 132       size_time_table (), call_size_time_table (vNULL),
 133       loop_iterations (NULL), loop_strides (NULL),
 134       builtin_constant_p_parms (vNULL),
 135       growth (0), scc_no (0)
 136   {
 137   }
 138
 139   /* Copy constructor.  */
 140   ipa_fn_summary (const ipa_fn_summary &s)
 141     : min_size (s.min_size),
 142     inlinable (s.inlinable), single_caller (s.single_caller),
 143     fp_expressions (s.fp_expressions),
 144     target_info (s.target_info),
 145     estimated_stack_size (s.estimated_stack_size),
 146     time (s.time), conds (s.conds), size_time_table (),
 147     call_size_time_table (vNULL),
 148     loop_iterations (s.loop_iterations), loop_strides (s.loop_strides),
 149     builtin_constant_p_parms (s.builtin_constant_p_parms),
 150     growth (s.growth), scc_no (s.scc_no)
 151   {}
 152
 153   /* Default constructor.  */
 154   ~ipa_fn_summary ();
 155
 156   /* Information about the function body itself.  */
 157
 158   /* Minimal size increase after inlining.  */
 159   int min_size;
 160
 161   /* False when there something makes inlining impossible (such as va_arg).  */
 162   unsigned inlinable : 1;
 163   /* True wen there is only one caller of the function before small function
 164      inlining.  */
 165   unsigned int single_caller : 1;
 166   /* True if function contains any floating point expressions.  */
 167   unsigned int fp_expressions : 1;
 168   /* Cache for analysis of can_early_inline_edge_p.  */
 169   unsigned int safe_to_inline_to_always_inline : 2;
 170   /* Like fp_expressions field above, but it's to hold some target specific
 171      information, such as some target specific isa flags.  Note that for
 172      offloading target compilers, this field isn't streamed.  */
 173   unsigned int target_info;
 174
 175   /* Information about function that will result after applying all the
 176      inline decisions present in the callgraph.  Generally kept up to
 177      date only for functions that are not inline clones. */
 178
 179   /* Estimated stack frame consumption by the function.  */
 180   HOST_WIDE_INT estimated_stack_size;
 181   /* Estimated runtime of function after inlining.  */
 182   sreal GTY((skip)) time;
 183
 184   /* Conditional size/time information.  The summaries are being
 185      merged during inlining.  */
 186   conditions conds;
 187   /* Normal code is accounted in size_time_table, while calls are
 188      accounted in call_size_time_table.  This is because calls
 189      are often adjusted by IPA optimizations and thus this summary
 190      is generated from call summary information when needed.  */
 191   auto_vec<size_time_entry> GTY((skip)) size_time_table;
 192   /* Unlike size_time_table that is initialized for all summaries
 193      call_size_time_table is allocated only for functions with
 194      many calls.  Use effecient vl_ptr storage.  */
 195   vec<size_time_entry, va_heap, vl_ptr> GTY((skip)) call_size_time_table;
 196
 197   /* Predicates on when some loops in the function can have known bounds.  */
 198   vec<ipa_freqcounting_predicate, va_gc> *loop_iterations;
 199   /* Predicates on when some loops in the function can have known strides.  */
 200   vec<ipa_freqcounting_predicate, va_gc> *loop_strides;
 201   /* Parameters tested by builtin_constant_p.  */
 202   vec<int, va_heap, vl_ptr> GTY((skip)) builtin_constant_p_parms;
 203   /* Estimated growth for inlining all copies of the function before start
 204      of small functions inlining.
 205      This value will get out of date as the callers are duplicated, but
 206      using up-to-date value in the badness metric mean a lot of extra
 207      expenses.  */
 208   int growth;
 209   /* Number of SCC on the beginning of inlining process.  */
 210   int scc_no;
 211
 212   /* Record time and size under given predicates.  */
 213   void account_size_time (int, sreal, const ipa_predicate &,
 214                           const ipa_predicate &,
 215                           bool call = false);
 216
 217   /* We keep values scaled up, so fractional sizes can be accounted.  */
 218   static const int size_scale = 2;
 219   /* Maximal size of size_time_table before we start to be conservative.  */
 220   static const int max_size_time_table_size = 256;
 221 };
 222
 223 class GTY((user)) ipa_fn_summary_t:
 224   public fast_function_summary <ipa_fn_summary *, va_gc>
 225 {
 226 public:
 227   ipa_fn_summary_t (symbol_table *symtab):
 228     fast_function_summary <ipa_fn_summary *, va_gc> (symtab) {}
 229
 230   static ipa_fn_summary_t *create_ggc (symbol_table *symtab)
 231   {
 232     class ipa_fn_summary_t *summary
 233       = new (ggc_alloc_no_dtor<ipa_fn_summary_t> ()) ipa_fn_summary_t (symtab);
 234     summary->disable_insertion_hook ();
 235     return summary;
 236   }
 237
 238   /* Remove ipa_fn_summary for all callees of NODE.  */
 239   void remove_callees (cgraph_node *node);
 240
 241   void insert (cgraph_node *, ipa_fn_summary *) final override;
 242   void remove (cgraph_node *node, ipa_fn_summary *) final override
 243   {
 244     remove_callees (node);
 245   }
 246
 247   void duplicate (cgraph_node *src, cgraph_node *dst,
 248                   ipa_fn_summary *src_data, ipa_fn_summary *dst_data)
 249     final override;
 250 };
 251
 252 extern GTY(()) fast_function_summary <ipa_fn_summary *, va_gc>
 253   *ipa_fn_summaries;
 254
 255 class ipa_size_summary_t:
 256   public fast_function_summary <ipa_size_summary *, va_heap>
 257 {
 258 public:
 259   ipa_size_summary_t (symbol_table *symtab):
 260     fast_function_summary <ipa_size_summary *, va_heap> (symtab)
 261   {
 262     disable_insertion_hook ();
 263   }
 264
 265   void duplicate (cgraph_node *, cgraph_node *,
 266                   ipa_size_summary *src_data,
 267                   ipa_size_summary *dst_data) final override
 268   {
 269     *dst_data = *src_data;
 270   }
 271 };
 272 extern fast_function_summary <ipa_size_summary *, va_heap>
 273   *ipa_size_summaries;
 274
 275 /* Information kept about callgraph edges.  */
 276 class ipa_call_summary
 277 {
 278 public:
 279   /* Keep all field empty so summary dumping works during its computation.
 280      This is useful for debugging.  */
 281   ipa_call_summary ()
 282     : predicate (NULL), param (vNULL), call_stmt_size (0), call_stmt_time (0),
 283       loop_depth (0), is_return_callee_uncaptured (false)
 284     {
 285     }
 286
 287   /* Copy constructor.  */
 288   ipa_call_summary (const ipa_call_summary &s):
 289     predicate (s.predicate), param (s.param), call_stmt_size (s.call_stmt_size),
 290     call_stmt_time (s.call_stmt_time), loop_depth (s.loop_depth),
 291     is_return_callee_uncaptured (s.is_return_callee_uncaptured)
 292   {
 293   }
 294
 295   /* Default destructor.  */
 296   ~ipa_call_summary ();
 297
 298   ipa_predicate *predicate;
 299   /* Vector indexed by parameters.  */
 300   vec<inline_param_summary> param;
 301   /* Estimated size and time of the call statement.  */
 302   int call_stmt_size;
 303   int call_stmt_time;
 304   /* Depth of loop nest, 0 means no nesting.  */
 305   unsigned int loop_depth;
 306   /* Indicates whether the caller returns the value of it's callee.  */
 307   bool is_return_callee_uncaptured;
 308 };
 309
 310 class ipa_call_summary_t: public fast_call_summary <ipa_call_summary *, va_heap>
 311 {
 312 public:
 313   ipa_call_summary_t (symbol_table *symtab):
 314     fast_call_summary <ipa_call_summary *, va_heap> (symtab) {}
 315
 316   /* Hook that is called by summary when an edge is duplicated.  */
 317   void duplicate (cgraph_edge *src, cgraph_edge *dst,
 318                   ipa_call_summary *src_data,
 319                   ipa_call_summary *dst_data) final override;
 320 };
 321
 322 /* Estimated execution times, code sizes and other information about the
 323    code executing a call described by ipa_call_context.  */
 324
 325 struct ipa_call_estimates
 326 {
 327   /* Estimated size needed to execute call in the given context. */
 328   int size;
 329
 330   /* Minimal size needed for the call that is + independent on the call context
 331      and can be used for fast estimates.  */
 332   int min_size;
 333
 334   /* Estimated time needed to execute call in the given context. */
 335   sreal time;
 336
 337   /* Estimated time needed to execute the function when not ignoring
 338      computations known to be constant in this context.  */
 339   sreal nonspecialized_time;
 340
 341   /* Further discovered reasons why to inline or specialize the give calls.  */
 342   ipa_hints hints;
 343
 344   /* Frequency how often a loop with known number of iterations is encountered.
 345      Calculated with hints.  */
 346   sreal loops_with_known_iterations;
 347
 348   /* Frequency how often a loop with known strides is encountered.  Calculated
 349      with hints.  */
 350   sreal loops_with_known_strides;
 351 };
 352
 353 class ipa_cached_call_context;
 354
 355 /* This object describe a context of call.  That is a summary of known
 356    information about its parameters.  Main purpose of this context is
 357    to give more realistic estimations of function runtime, size and
 358    inline hints.  */
 359 class ipa_call_context
 360 {
 361 public:
 362   ipa_call_context (cgraph_node *node,
 363                     clause_t possible_truths,
 364                     clause_t nonspec_possible_truths,
 365                     vec<inline_param_summary> inline_param_summary,
 366                     ipa_auto_call_arg_values *arg_values);
 367   ipa_call_context ()
 368   : m_node(NULL)
 369   {
 370   }
 371   void estimate_size_and_time (ipa_call_estimates *estimates,
 372                                bool est_times = true, bool est_hints = true);
 373   bool equal_to (const ipa_call_context &);
 374   bool exists_p ()
 375   {
 376     return m_node != NULL;
 377   }
 378 private:
 379   /* Called function.  */
 380   cgraph_node *m_node;
 381   /* Clause describing what predicate conditionals can be satisfied
 382      in this context if function is inlined/specialized.  */
 383   clause_t m_possible_truths;
 384   /* Clause describing what predicate conditionals can be satisfied
 385      in this context if function is kept offline.  */
 386   clause_t m_nonspec_possible_truths;
 387   /* Inline summary maintains info about change probabilities.  */
 388   vec<inline_param_summary> m_inline_param_summary;
 389
 390   /* Even after having calculated clauses, the information about argument
 391      values is used to resolve indirect calls.  */
 392   ipa_call_arg_values m_avals;
 393
 394   friend ipa_cached_call_context;
 395 };
 396
 397 /* Variant of ipa_call_context that is stored in a cache over a longer period
 398    of time.  */
 399
 400 class ipa_cached_call_context : public ipa_call_context
 401 {
 402 public:
 403   void duplicate_from (const ipa_call_context &ctx);
 404   void release ();
 405 };
 406
 407 extern fast_call_summary <ipa_call_summary *, va_heap> *ipa_call_summaries;
 408
 409 /* In ipa-fnsummary.cc  */
 410 void ipa_debug_fn_summary (struct cgraph_node *);
 411 void ipa_dump_fn_summaries (FILE *f);
 412 void ipa_dump_fn_summary (FILE *f, struct cgraph_node *node);
 413 void ipa_dump_hints (FILE *f, ipa_hints);
 414 void ipa_free_fn_summary (void);
 415 void ipa_free_size_summary (void);
 416 void inline_analyze_function (struct cgraph_node *node);
 417 void estimate_ipcp_clone_size_and_time (struct cgraph_node *node,
 418                                         ipa_auto_call_arg_values *avals,
 419                                         ipa_call_estimates *estimates);
 420 void ipa_merge_fn_summary_after_inlining (struct cgraph_edge *edge);
 421 void ipa_update_overall_fn_summary (struct cgraph_node *node, bool reset = true);
 422 void compute_fn_summary (struct cgraph_node *, bool);
 423 bool refs_local_or_readonly_memory_p (tree);
 424 bool points_to_local_or_readonly_memory_p (tree);
 425
 426
 427 void evaluate_properties_for_edge (struct cgraph_edge *e,
 428                                    bool inline_p,
 429                                    clause_t *clause_ptr,
 430                                    clause_t *nonspec_clause_ptr,
 431                                    ipa_auto_call_arg_values *avals,
 432                                    bool compute_contexts);
 433
 434 void ipa_fnsummary_cc_finalize (void);
 435 HOST_WIDE_INT ipa_get_stack_frame_offset (struct cgraph_node *node);
 436 void ipa_remove_from_growth_caches (struct cgraph_edge *edge);
 437
 438 /* Return true if EDGE is a cross module call.  */
 439
 440 inline bool
 441 cross_module_call_p (struct cgraph_edge *edge)
 442 {
 443   /* Here we do not want to walk to alias target becuase ICF may create
 444      cross-unit aliases.  */
 445   if (edge->caller->unit_id == edge->callee->unit_id)
 446     return false;
 447   /* If the call is to a (former) comdat function or s symbol with mutiple
 448      extern inline definitions then treat is as in-module call.  */
 449   if (edge->callee->merged_extern_inline || edge->callee->merged_comdat
 450       || DECL_COMDAT (edge->callee->decl))
 451     return false;
 452   return true;
 453 }
 454
 455 #endif /* GCC_IPA_FNSUMMARY_H */