gcc/ipa-fnsummary.h

   1 /* IPA function body analysis.
   2    Copyright (C) 2003-2019 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.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
  55 typedef 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
  62 struct 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.  */
  72 class GTY(()) size_time_entry
  73 {
  74 public:
  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.  */
  88 class ipa_size_summary
  89 {
  90 public:
  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   /* Copy constructor.  */
 103   ipa_size_summary (const ipa_size_summary &s)
 104   : estimated_self_stack_size (0), self_size (s.self_size), size (s.size)
 105   {
 106   }
 107 };
 108
 109 /* Function inlining information.  */
 110 class GTY(()) ipa_fn_summary
 111 {
 112 public:
 113   /* Keep all field empty so summary dumping works during its computation.
 114      This is useful for debugging.  */
 115   ipa_fn_summary ()
 116     : min_size (0),
 117       inlinable (false), single_caller (false),
 118       fp_expressions (false), estimated_stack_size (false),
 119       time (0), conds (NULL),
 120       size_time_table (NULL), call_size_time_table (NULL), loop_iterations (NULL),
 121       loop_stride (NULL), growth (0), scc_no (0)
 122   {
 123   }
 124
 125   /* Copy constructor.  */
 126   ipa_fn_summary (const ipa_fn_summary &s)
 127     : min_size (s.min_size),
 128     inlinable (s.inlinable), single_caller (s.single_caller),
 129     fp_expressions (s.fp_expressions),
 130     estimated_stack_size (s.estimated_stack_size),
 131     time (s.time), conds (s.conds), size_time_table (s.size_time_table),
 132     call_size_time_table (NULL),
 133     loop_iterations (s.loop_iterations), loop_stride (s.loop_stride),
 134     growth (s.growth), scc_no (s.scc_no)
 135   {}
 136
 137   /* Default constructor.  */
 138   ~ipa_fn_summary ();
 139
 140   /* Information about the function body itself.  */
 141
 142   /* Minimal size increase after inlining.  */
 143   int min_size;
 144
 145   /* False when there something makes inlining impossible (such as va_arg).  */
 146   unsigned inlinable : 1;
 147   /* True wen there is only one caller of the function before small function
 148      inlining.  */
 149   unsigned int single_caller : 1;
 150   /* True if function contains any floating point expressions.  */
 151   unsigned int fp_expressions : 1;
 152
 153   /* Information about function that will result after applying all the
 154      inline decisions present in the callgraph.  Generally kept up to
 155      date only for functions that are not inline clones. */
 156
 157   /* Estimated stack frame consumption by the function.  */
 158   HOST_WIDE_INT estimated_stack_size;
 159   /* Estimated runtime of function after inlining.  */
 160   sreal GTY((skip)) time;
 161
 162   /* Conditional size/time information.  The summaries are being
 163      merged during inlining.  */
 164   conditions conds;
 165   /* Normal code is accounted in size_time_table, while calls are
 166      accounted in call_size_time_table.  This is because calls
 167      are often adjusted by IPA optimizations and thus this summary
 168      is generated from call summary information when needed.  */
 169   vec<size_time_entry, va_gc> *size_time_table;
 170   vec<size_time_entry, va_gc> *call_size_time_table;
 171
 172   /* Predicate on when some loop in the function becomes to have known
 173      bounds.   */
 174   predicate * GTY((skip)) loop_iterations;
 175   /* Predicate on when some loop in the function becomes to have known
 176      stride.   */
 177   predicate * GTY((skip)) loop_stride;
 178   /* Estimated growth for inlining all copies of the function before start
 179      of small functions inlining.
 180      This value will get out of date as the callers are duplicated, but
 181      using up-to-date value in the badness metric mean a lot of extra
 182      expenses.  */
 183   int growth;
 184   /* Number of SCC on the beginning of inlining process.  */
 185   int scc_no;
 186
 187   /* Record time and size under given predicates.  */
 188   void account_size_time (int, sreal, const predicate &, const predicate &,
 189                           bool call = false);
 190
 191   /* We keep values scaled up, so fractional sizes can be accounted.  */
 192   static const int size_scale = 2;
 193   /* Maximal size of size_time_table before we start to be conservative.  */
 194   static const int max_size_time_table_size = 256;
 195 };
 196
 197 class GTY((user)) ipa_fn_summary_t:
 198   public fast_function_summary <ipa_fn_summary *, va_gc>
 199 {
 200 public:
 201   ipa_fn_summary_t (symbol_table *symtab):
 202     fast_function_summary <ipa_fn_summary *, va_gc> (symtab) {}
 203
 204   static ipa_fn_summary_t *create_ggc (symbol_table *symtab)
 205   {
 206     class ipa_fn_summary_t *summary
 207       = new (ggc_alloc_no_dtor<ipa_fn_summary_t> ()) ipa_fn_summary_t (symtab);
 208     summary->disable_insertion_hook ();
 209     return summary;
 210   }
 211
 212   /* Remove ipa_fn_summary for all callees of NODE.  */
 213   void remove_callees (cgraph_node *node);
 214
 215   virtual void insert (cgraph_node *, ipa_fn_summary *);
 216   virtual void remove (cgraph_node *node, ipa_fn_summary *)
 217   {
 218     remove_callees (node);
 219   }
 220
 221   virtual void duplicate (cgraph_node *src, cgraph_node *dst,
 222                           ipa_fn_summary *src_data, ipa_fn_summary *dst_data);
 223 };
 224
 225 extern GTY(()) fast_function_summary <ipa_fn_summary *, va_gc>
 226   *ipa_fn_summaries;
 227
 228 class ipa_size_summary_t:
 229   public fast_function_summary <ipa_size_summary *, va_gc>
 230 {
 231 public:
 232   ipa_size_summary_t (symbol_table *symtab):
 233     fast_function_summary <ipa_size_summary *, va_gc> (symtab) {}
 234
 235   static ipa_size_summary_t *create_ggc (symbol_table *symtab)
 236   {
 237     class ipa_size_summary_t *summary = new (ggc_alloc <ipa_size_summary_t> ())
 238       ipa_size_summary_t (symtab);
 239     summary->disable_insertion_hook ();
 240     return summary;
 241   }
 242 };
 243 extern fast_function_summary <ipa_size_summary *, va_heap>
 244   *ipa_size_summaries;
 245
 246 /* Information kept about callgraph edges.  */
 247 class ipa_call_summary
 248 {
 249 public:
 250   /* Keep all field empty so summary dumping works during its computation.
 251      This is useful for debugging.  */
 252   ipa_call_summary ()
 253     : predicate (NULL), param (vNULL), call_stmt_size (0), call_stmt_time (0),
 254       loop_depth (0), is_return_callee_uncaptured (false)
 255     {
 256     }
 257
 258   /* Copy constructor.  */
 259   ipa_call_summary (const ipa_call_summary &s):
 260     predicate (s.predicate), param (s.param), call_stmt_size (s.call_stmt_size),
 261     call_stmt_time (s.call_stmt_time), loop_depth (s.loop_depth),
 262     is_return_callee_uncaptured (s.is_return_callee_uncaptured)
 263   {
 264   }
 265
 266   /* Default destructor.  */
 267   ~ipa_call_summary ();
 268
 269   class predicate *predicate;
 270   /* Vector indexed by parameters.  */
 271   vec<inline_param_summary> param;
 272   /* Estimated size and time of the call statement.  */
 273   int call_stmt_size;
 274   int call_stmt_time;
 275   /* Depth of loop nest, 0 means no nesting.  */
 276   unsigned int loop_depth;
 277   /* Indicates whether the caller returns the value of it's callee.  */
 278   bool is_return_callee_uncaptured;
 279 };
 280
 281 class ipa_call_summary_t: public fast_call_summary <ipa_call_summary *, va_heap>
 282 {
 283 public:
 284   ipa_call_summary_t (symbol_table *symtab):
 285     fast_call_summary <ipa_call_summary *, va_heap> (symtab) {}
 286
 287   /* Hook that is called by summary when an edge is duplicated.  */
 288   virtual void duplicate (cgraph_edge *src, cgraph_edge *dst,
 289                           ipa_call_summary *src_data,
 290                           ipa_call_summary *dst_data);
 291 };
 292
 293 /* This object describe a context of call.  That is a summary of known
 294    information about its parameters.  Main purpose of this context is
 295    to give more realistic estimations of function runtime, size and
 296    inline hints.  */
 297 class ipa_call_context
 298 {
 299 public:
 300   ipa_call_context (cgraph_node *node,
 301                     clause_t possible_truths,
 302                     clause_t nonspec_possible_truths,
 303                     vec<tree> known_vals,
 304                     vec<ipa_polymorphic_call_context> known_contexts,
 305                     vec<ipa_agg_value_set> known_aggs,
 306                     vec<inline_param_summary> m_inline_param_summary);
 307   ipa_call_context ()
 308   : m_node(NULL)
 309   {
 310   }
 311   void estimate_size_and_time (int *ret_size, int *ret_min_size,
 312                                sreal *ret_time,
 313                                sreal *ret_nonspecialized_time,
 314                                ipa_hints *ret_hints);
 315   void duplicate_from (const ipa_call_context &ctx);
 316   void release (bool all = false);
 317   bool equal_to (const ipa_call_context &);
 318   bool exists_p ()
 319   {
 320     return m_node != NULL;
 321   }
 322 private:
 323   /* Called function.  */
 324   cgraph_node *m_node;
 325   /* Clause describing what predicate conditionals can be satisfied
 326      in this context if function is inlined/specialized.  */
 327   clause_t m_possible_truths;
 328   /* Clause describing what predicate conditionals can be satisfied
 329      in this context if function is kept offline.  */
 330   clause_t m_nonspec_possible_truths;
 331   /* Inline summary maintains info about change probabilities.  */
 332   vec<inline_param_summary> m_inline_param_summary;
 333
 334   /* The following is used only to resolve indirect calls.  */
 335
 336   /* Vector describing known values of parameters.  */
 337   vec<tree> m_known_vals;
 338   /* Vector describing known polymorphic call contexts.  */
 339   vec<ipa_polymorphic_call_context> m_known_contexts;
 340   /* Vector describing known aggregate values.  */
 341   vec<ipa_agg_value_set> m_known_aggs;
 342 };
 343
 344 extern fast_call_summary <ipa_call_summary *, va_heap> *ipa_call_summaries;
 345
 346 /* In ipa-fnsummary.c  */
 347 void ipa_debug_fn_summary (struct cgraph_node *);
 348 void ipa_dump_fn_summaries (FILE *f);
 349 void ipa_dump_fn_summary (FILE *f, struct cgraph_node *node);
 350 void ipa_dump_hints (FILE *f, ipa_hints);
 351 void ipa_free_fn_summary (void);
 352 void ipa_free_size_summary (void);
 353 void inline_analyze_function (struct cgraph_node *node);
 354 void estimate_ipcp_clone_size_and_time (struct cgraph_node *,
 355                                         vec<tree>,
 356                                         vec<ipa_polymorphic_call_context>,
 357                                         vec<ipa_agg_value_set>,
 358                                         int *, sreal *, sreal *,
 359                                         ipa_hints *);
 360 void ipa_merge_fn_summary_after_inlining (struct cgraph_edge *edge);
 361 void ipa_update_overall_fn_summary (struct cgraph_node *node, bool reset = true);
 362 void compute_fn_summary (struct cgraph_node *, bool);
 363
 364
 365 void evaluate_properties_for_edge (struct cgraph_edge *e,
 366                                    bool inline_p,
 367                                    clause_t *clause_ptr,
 368                                    clause_t *nonspec_clause_ptr,
 369                                    vec<tree> *known_vals_ptr,
 370                                    vec<ipa_polymorphic_call_context>
 371                                    *known_contexts_ptr,
 372                                    vec<ipa_agg_value_set> *);
 373
 374 void ipa_fnsummary_c_finalize (void);
 375 HOST_WIDE_INT ipa_get_stack_frame_offset (struct cgraph_node *node);
 376 void ipa_remove_from_growth_caches (struct cgraph_edge *edge);
 377
 378 /* Return true if EDGE is a cross module call.  */
 379
 380 static inline bool
 381 cross_module_call_p (struct cgraph_edge *edge)
 382 {
 383   /* Here we do not want to walk to alias target becuase ICF may create
 384      cross-unit aliases.  */
 385   if (edge->caller->unit_id == edge->callee->unit_id)
 386     return false;
 387   /* If the call is to a (former) comdat function or s symbol with mutiple
 388      extern inline definitions then treat is as in-module call.  */
 389   if (edge->callee->merged_extern_inline || edge->callee->merged_comdat
 390       || DECL_COMDAT (edge->callee->decl))
 391     return false;
 392   return true;
 393 }
 394
 395 #endif /* GCC_IPA_FNSUMMARY_H */