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