gcc/symbol-summary.h

   1 /* Callgraph summary data structure.
   2    Copyright (C) 2014-2018 Free Software Foundation, Inc.
   3    Contributed by Martin Liska
   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_SYMBOL_SUMMARY_H
  22 #define GCC_SYMBOL_SUMMARY_H
  23
  24 /* We want to pass just pointer types as argument for function_summary
  25    template class.  */
  26
  27 template <class T>
  28 class function_summary
  29 {
  30 private:
  31   function_summary();
  32 };
  33
  34 /* Function summary is a helper class that is used to associate a data structure
  35    related to a callgraph node.  Typical usage can be seen in IPA passes which
  36    create a temporary pass-related structures.  The summary class registers
  37    hooks that are triggered when a new node is inserted, duplicated and deleted.
  38    A user of a summary class can ovewrite virtual methods than are triggered by
  39    the summary if such hook is triggered.  Apart from a callgraph node, the user
  40    is given a data structure tied to the node.
  41
  42    The function summary class can work both with a heap-allocated memory and
  43    a memory gained by garbage collected memory.  */
  44
  45 template <class T>
  46 class GTY((user)) function_summary <T *>
  47 {
  48 public:
  49   /* Default construction takes SYMTAB as an argument.  */
  50   function_summary (symbol_table *symtab, bool ggc = false);
  51
  52   /* Destructor.  */
  53   virtual ~function_summary ()
  54   {
  55     release ();
  56   }
  57
  58   /* Destruction method that can be called for GGT purpose.  */
  59   void release ();
  60
  61   /* Traverses all summarys with a function F called with
  62      ARG as argument.  */
  63   template<typename Arg, bool (*f)(const T &, Arg)>
  64   void traverse (Arg a) const
  65   {
  66     m_map.traverse <f> (a);
  67   }
  68
  69   /* Basic implementation of insert operation.  */
  70   virtual void insert (cgraph_node *, T *) {}
  71
  72   /* Basic implementation of removal operation.  */
  73   virtual void remove (cgraph_node *, T *) {}
  74
  75   /* Basic implementation of duplication operation.  */
  76   virtual void duplicate (cgraph_node *, cgraph_node *, T *, T *) {}
  77
  78   /* Allocates new data that are stored within map.  */
  79   T* allocate_new ()
  80   {
  81     /* Call gcc_internal_because we do not want to call finalizer for
  82        a type T.  We call dtor explicitly.  */
  83     return m_ggc ? new (ggc_internal_alloc (sizeof (T))) T () : new T () ;
  84   }
  85
  86   /* Release an item that is stored within map.  */
  87   void release (T *item);
  88
  89   /* Getter for summary callgraph node pointer.  If a summary for a node
  90      does not exist it will be created.  */
  91   T* get_create (cgraph_node *node)
  92   {
  93     return get (node->get_uid (), true);
  94   }
  95
  96   /* Getter for summary callgraph node pointer.  */
  97   T* get (cgraph_node *node)
  98   {
  99     return get (node->get_uid (), false);
 100   }
 101
 102   /* Return number of elements handled by data structure.  */
 103   size_t elements ()
 104   {
 105     return m_map.elements ();
 106   }
 107
 108   /* Return true if a summary for the given NODE already exists.  */
 109   bool exists (cgraph_node *node)
 110   {
 111     return m_map.get (node->get_uid ()) != NULL;
 112   }
 113
 114   /* Enable insertion hook invocation.  */
 115   void enable_insertion_hook ()
 116   {
 117     m_insertion_enabled = true;
 118   }
 119
 120   /* Enable insertion hook invocation.  */
 121   void disable_insertion_hook ()
 122   {
 123     m_insertion_enabled = false;
 124   }
 125
 126   /* Symbol insertion hook that is registered to symbol table.  */
 127   static void symtab_insertion (cgraph_node *node, void *data);
 128
 129   /* Symbol removal hook that is registered to symbol table.  */
 130   static void symtab_removal (cgraph_node *node, void *data);
 131
 132   /* Symbol duplication hook that is registered to symbol table.  */
 133   static void symtab_duplication (cgraph_node *node, cgraph_node *node2,
 134                                   void *data);
 135
 136 protected:
 137   /* Indication if we use ggc summary.  */
 138   bool m_ggc;
 139
 140 private:
 141   typedef int_hash <int, 0, -1> map_hash;
 142
 143   /* Getter for summary callgraph ID.  */
 144   T *get (int uid, bool lazy_insert);
 145
 146   /* Indicates if insertion hook is enabled.  */
 147   bool m_insertion_enabled;
 148   /* Indicates if the summary is released.  */
 149   bool m_released;
 150   /* Main summary store, where summary ID is used as key.  */
 151   hash_map <map_hash, T *> m_map;
 152   /* Internal summary insertion hook pointer.  */
 153   cgraph_node_hook_list *m_symtab_insertion_hook;
 154   /* Internal summary removal hook pointer.  */
 155   cgraph_node_hook_list *m_symtab_removal_hook;
 156   /* Internal summary duplication hook pointer.  */
 157   cgraph_2node_hook_list *m_symtab_duplication_hook;
 158   /* Symbol table the summary is registered to.  */
 159   symbol_table *m_symtab;
 160
 161   template <typename U> friend void gt_ggc_mx (function_summary <U *> * const &);
 162   template <typename U> friend void gt_pch_nx (function_summary <U *> * const &);
 163   template <typename U> friend void gt_pch_nx (function_summary <U *> * const &,
 164       gt_pointer_operator, void *);
 165 };
 166
 167 template <typename T>
 168 function_summary<T *>::function_summary (symbol_table *symtab, bool ggc):
 169   m_ggc (ggc), m_insertion_enabled (true), m_released (false), m_map (13, ggc),
 170   m_symtab (symtab)
 171 {
 172   m_symtab_insertion_hook
 173     = symtab->add_cgraph_insertion_hook (function_summary::symtab_insertion,
 174                                          this);
 175
 176   m_symtab_removal_hook
 177     = symtab->add_cgraph_removal_hook (function_summary::symtab_removal, this);
 178   m_symtab_duplication_hook
 179     = symtab->add_cgraph_duplication_hook (function_summary::symtab_duplication,
 180                                            this);
 181 }
 182
 183 template <typename T>
 184 void
 185 function_summary<T *>::release ()
 186 {
 187   if (m_released)
 188     return;
 189
 190   m_symtab->remove_cgraph_insertion_hook (m_symtab_insertion_hook);
 191   m_symtab->remove_cgraph_removal_hook (m_symtab_removal_hook);
 192   m_symtab->remove_cgraph_duplication_hook (m_symtab_duplication_hook);
 193
 194   /* Release all summaries.  */
 195   typedef typename hash_map <map_hash, T *>::iterator map_iterator;
 196   for (map_iterator it = m_map.begin (); it != m_map.end (); ++it)
 197     release ((*it).second);
 198
 199   m_released = true;
 200 }
 201
 202 template <typename T>
 203 void
 204 function_summary<T *>::release (T *item)
 205 {
 206   if (m_ggc)
 207     {
 208       item->~T ();
 209       ggc_free (item);
 210     }
 211   else
 212     delete item;
 213 }
 214
 215 template <typename T>
 216 void
 217 function_summary<T *>::symtab_insertion (cgraph_node *node, void *data)
 218 {
 219   gcc_checking_assert (node->get_uid ());
 220   function_summary *summary = (function_summary <T *> *) (data);
 221
 222   if (summary->m_insertion_enabled)
 223     summary->insert (node, summary->get_create (node));
 224 }
 225
 226 template <typename T>
 227 void
 228 function_summary<T *>::symtab_removal (cgraph_node *node, void *data)
 229 {
 230   gcc_checking_assert (node->get_uid ());
 231   function_summary *summary = (function_summary <T *> *) (data);
 232
 233   int uid = node->get_uid ();
 234   T **v = summary->m_map.get (uid);
 235
 236   if (v)
 237     {
 238       summary->remove (node, *v);
 239
 240       if (!summary->m_ggc)
 241         delete (*v);
 242
 243       summary->m_map.remove (uid);
 244     }
 245 }
 246
 247 template <typename T>
 248 void
 249 function_summary<T *>::symtab_duplication (cgraph_node *node,
 250                                            cgraph_node *node2, void *data)
 251 {
 252   function_summary *summary = (function_summary <T *> *) (data);
 253   T *v = summary->get (node);
 254
 255   if (v)
 256     {
 257       /* This load is necessary, because we insert a new value!  */
 258       T *duplicate = summary->allocate_new ();
 259       summary->m_map.put (node2->get_uid (), duplicate);
 260       summary->duplicate (node, node2, v, duplicate);
 261     }
 262 }
 263
 264 template <typename T>
 265 T*
 266 function_summary<T *>::get (int uid, bool lazy_insert)
 267 {
 268   gcc_checking_assert (uid > 0);
 269
 270   if (lazy_insert)
 271     {
 272       bool existed;
 273       T **v = &m_map.get_or_insert (uid, &existed);
 274       if (!existed)
 275         *v = allocate_new ();
 276
 277       return *v;
 278     }
 279   else
 280     {
 281       T **v = m_map.get (uid);
 282       return v == NULL ? NULL : *v;
 283     }
 284 }
 285
 286 template <typename T>
 287 void
 288 gt_ggc_mx(function_summary<T *>* const &summary)
 289 {
 290   gcc_checking_assert (summary->m_ggc);
 291   gt_ggc_mx (&summary->m_map);
 292 }
 293
 294 template <typename T>
 295 void
 296 gt_pch_nx(function_summary<T *>* const &summary)
 297 {
 298   gcc_checking_assert (summary->m_ggc);
 299   gt_pch_nx (&summary->m_map);
 300 }
 301
 302 template <typename T>
 303 void
 304 gt_pch_nx(function_summary<T *>* const& summary, gt_pointer_operator op,
 305           void *cookie)
 306 {
 307   gcc_checking_assert (summary->m_ggc);
 308   gt_pch_nx (&summary->m_map, op, cookie);
 309 }
 310
 311 /* An impossible class templated by non-pointers so, which makes sure that only
 312    summaries gathering pointers can be created.  */
 313
 314 template <class T>
 315 class call_summary
 316 {
 317 private:
 318   call_summary();
 319 };
 320
 321 /* Class to store auxiliary information about call graph edges.  */
 322
 323 template <class T>
 324 class GTY((user)) call_summary <T *>
 325 {
 326 public:
 327   /* Default construction takes SYMTAB as an argument.  */
 328   call_summary (symbol_table *symtab, bool ggc = false): m_ggc (ggc),
 329     m_initialize_when_cloning (false), m_map (13, ggc), m_released (false),
 330     m_symtab (symtab)
 331   {
 332     m_symtab_removal_hook =
 333       symtab->add_edge_removal_hook
 334       (call_summary::symtab_removal, this);
 335     m_symtab_duplication_hook =
 336       symtab->add_edge_duplication_hook
 337       (call_summary::symtab_duplication, this);
 338   }
 339
 340   /* Destructor.  */
 341   virtual ~call_summary ()
 342   {
 343     release ();
 344   }
 345
 346   /* Destruction method that can be called for GGT purpose.  */
 347   void release ();
 348
 349   /* Traverses all summarys with a function F called with
 350      ARG as argument.  */
 351   template<typename Arg, bool (*f)(const T &, Arg)>
 352   void traverse (Arg a) const
 353   {
 354     m_map.traverse <f> (a);
 355   }
 356
 357   /* Basic implementation of removal operation.  */
 358   virtual void remove (cgraph_edge *, T *) {}
 359
 360   /* Basic implementation of duplication operation.  */
 361   virtual void duplicate (cgraph_edge *, cgraph_edge *, T *, T *) {}
 362
 363   /* Allocates new data that are stored within map.  */
 364   T* allocate_new ()
 365   {
 366     /* Call gcc_internal_because we do not want to call finalizer for
 367        a type T.  We call dtor explicitly.  */
 368     return m_ggc ? new (ggc_internal_alloc (sizeof (T))) T () : new T () ;
 369   }
 370
 371   /* Release an item that is stored within map.  */
 372   void release (T *item);
 373
 374   /* Getter for summary callgraph edge pointer.
 375      If a summary for an edge does not exist, it will be created.  */
 376   T* get_create (cgraph_edge *edge)
 377   {
 378     return get (edge->get_uid (), true);
 379   }
 380
 381   /* Getter for summary callgraph edge pointer.  */
 382   T* get (cgraph_edge *edge)
 383   {
 384     return get (edge->get_uid (), false);
 385   }
 386
 387   /* Remove edge from summary.  */
 388   void remove (cgraph_edge *edge)
 389   {
 390     int uid = edge->get_uid ();
 391     T **v = m_map.get (uid);
 392     if (v)
 393       {
 394         m_map.remove (uid);
 395         release (*v);
 396       }
 397   }
 398
 399   /* Return number of elements handled by data structure.  */
 400   size_t elements ()
 401   {
 402     return m_map.elements ();
 403   }
 404
 405   /* Return true if a summary for the given EDGE already exists.  */
 406   bool exists (cgraph_edge *edge)
 407   {
 408     return m_map.get (edge->get_uid ()) != NULL;
 409   }
 410
 411   /* Symbol removal hook that is registered to symbol table.  */
 412   static void symtab_removal (cgraph_edge *edge, void *data);
 413
 414   /* Symbol duplication hook that is registered to symbol table.  */
 415   static void symtab_duplication (cgraph_edge *edge1, cgraph_edge *edge2,
 416                                   void *data);
 417
 418 protected:
 419   /* Indication if we use ggc summary.  */
 420   bool m_ggc;
 421
 422   /* Initialize summary for an edge that is cloned.  */
 423   bool m_initialize_when_cloning;
 424
 425 private:
 426   typedef int_hash <int, 0, -1> map_hash;
 427
 428   /* Getter for summary callgraph ID.  */
 429   T *get (int uid, bool lazy_insert);
 430
 431   /* Main summary store, where summary ID is used as key.  */
 432   hash_map <map_hash, T *> m_map;
 433   /* Internal summary removal hook pointer.  */
 434   cgraph_edge_hook_list *m_symtab_removal_hook;
 435   /* Internal summary duplication hook pointer.  */
 436   cgraph_2edge_hook_list *m_symtab_duplication_hook;
 437   /* Indicates if the summary is released.  */
 438   bool m_released;
 439   /* Symbol table the summary is registered to.  */
 440   symbol_table *m_symtab;
 441
 442   template <typename U> friend void gt_ggc_mx (call_summary <U *> * const &);
 443   template <typename U> friend void gt_pch_nx (call_summary <U *> * const &);
 444   template <typename U> friend void gt_pch_nx (call_summary <U *> * const &,
 445       gt_pointer_operator, void *);
 446 };
 447
 448 template <typename T>
 449 T*
 450 call_summary<T *>::get (int uid, bool lazy_insert)
 451 {
 452   gcc_checking_assert (uid > 0);
 453
 454   if (lazy_insert)
 455     {
 456       bool existed;
 457       T **v = &m_map.get_or_insert (uid, &existed);
 458       if (!existed)
 459         *v = allocate_new ();
 460
 461       return *v;
 462     }
 463   else
 464     {
 465       T **v = m_map.get (uid);
 466       return v == NULL ? NULL : *v;
 467     }
 468 }
 469
 470 template <typename T>
 471 void
 472 call_summary<T *>::release ()
 473 {
 474   if (m_released)
 475     return;
 476
 477   m_symtab->remove_edge_removal_hook (m_symtab_removal_hook);
 478   m_symtab->remove_edge_duplication_hook (m_symtab_duplication_hook);
 479
 480   /* Release all summaries.  */
 481   typedef typename hash_map <map_hash, T *>::iterator map_iterator;
 482   for (map_iterator it = m_map.begin (); it != m_map.end (); ++it)
 483     release ((*it).second);
 484
 485   m_released = true;
 486 }
 487
 488 template <typename T>
 489 void
 490 call_summary<T *>::release (T *item)
 491 {
 492   if (m_ggc)
 493     {
 494       item->~T ();
 495       ggc_free (item);
 496     }
 497   else
 498     delete item;
 499 }
 500
 501 template <typename T>
 502 void
 503 call_summary<T *>::symtab_removal (cgraph_edge *edge, void *data)
 504 {
 505   call_summary *summary = (call_summary <T *> *) (data);
 506
 507   int h_uid = edge->get_uid ();
 508   T **v = summary->m_map.get (h_uid);
 509
 510   if (v)
 511     {
 512       summary->remove (edge, *v);
 513       summary->release (*v);
 514       summary->m_map.remove (h_uid);
 515     }
 516 }
 517
 518 template <typename T>
 519 void
 520 call_summary<T *>::symtab_duplication (cgraph_edge *edge1,
 521                                        cgraph_edge *edge2, void *data)
 522 {
 523   call_summary *summary = (call_summary <T *> *) (data);
 524   T *edge1_summary = NULL;
 525
 526   if (summary->m_initialize_when_cloning)
 527     edge1_summary = summary->get_create (edge1);
 528   else
 529     {
 530       T **v = summary->m_map.get (edge1->get_uid ());
 531       if (v)
 532         {
 533           /* This load is necessary, because we insert a new value!  */
 534           edge1_summary = *v;
 535         }
 536     }
 537
 538   if (edge1_summary)
 539     {
 540       T *duplicate = summary->allocate_new ();
 541       summary->m_map.put (edge2->get_uid (), duplicate);
 542       summary->duplicate (edge1, edge2, edge1_summary, duplicate);
 543     }
 544 }
 545
 546 template <typename T>
 547 void
 548 gt_ggc_mx(call_summary<T *>* const &summary)
 549 {
 550   gcc_checking_assert (summary->m_ggc);
 551   gt_ggc_mx (&summary->m_map);
 552 }
 553
 554 template <typename T>
 555 void
 556 gt_pch_nx(call_summary<T *>* const &summary)
 557 {
 558   gcc_checking_assert (summary->m_ggc);
 559   gt_pch_nx (&summary->m_map);
 560 }
 561
 562 template <typename T>
 563 void
 564 gt_pch_nx(call_summary<T *>* const& summary, gt_pointer_operator op,
 565           void *cookie)
 566 {
 567   gcc_checking_assert (summary->m_ggc);
 568   gt_pch_nx (&summary->m_map, op, cookie);
 569 }
 570
 571 #endif  /* GCC_SYMBOL_SUMMARY_H  */