gcc/analyzer/supergraph.h

   1 /* "Supergraph" classes that combine CFGs and callgraph into one digraph.
   2    Copyright (C) 2019-2021 Free Software Foundation, Inc.
   3    Contributed by David Malcolm <dmalcolm@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 General Public License 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_ANALYZER_SUPERGRAPH_H
  22 #define GCC_ANALYZER_SUPERGRAPH_H
  23
  24 using namespace ana;
  25
  26 namespace ana {
  27
  28 /* Forward decls, using indentation to show inheritance.  */
  29
  30 class supergraph;
  31 class supernode;
  32 class superedge;
  33   class callgraph_superedge;
  34     class call_superedge;
  35     class return_superedge;
  36   class cfg_superedge;
  37     class switch_cfg_superedge;
  38 class supercluster;
  39 class dot_annotator;
  40
  41 class logger;
  42
  43 /* An enum for discriminating between superedge subclasses.  */
  44
  45 enum edge_kind
  46 {
  47   SUPEREDGE_CFG_EDGE,
  48   SUPEREDGE_CALL,
  49   SUPEREDGE_RETURN,
  50   SUPEREDGE_INTRAPROCEDURAL_CALL
  51 };
  52
  53 /* Flags for controlling the appearance of .dot dumps.  */
  54
  55 enum supergraph_dot_flags
  56 {
  57   SUPERGRAPH_DOT_SHOW_BBS = (1 << 0)
  58 };
  59
  60 /* A traits struct describing the family of node, edge and digraph
  61    classes for supergraphs.  */
  62
  63 struct supergraph_traits
  64 {
  65   typedef supernode node_t;
  66   typedef superedge edge_t;
  67   typedef supergraph graph_t;
  68   struct dump_args_t
  69   {
  70     dump_args_t (enum supergraph_dot_flags flags,
  71                  const dot_annotator *node_annotator)
  72     : m_flags (flags),
  73       m_node_annotator (node_annotator)
  74     {}
  75
  76     enum supergraph_dot_flags m_flags;
  77     const dot_annotator *m_node_annotator;
  78   };
  79   typedef supercluster cluster_t;
  80 };
  81
  82 /* A class to manage the setting and restoring of statement uids.  */
  83
  84 class saved_uids
  85 {
  86 public:
  87   void make_uid_unique (gimple *stmt);
  88   void restore_uids () const;
  89
  90 private:
  91   auto_vec<std::pair<gimple *, unsigned> > m_old_stmt_uids;
  92 };
  93
  94 /* A "supergraph" is a directed graph formed by joining together all CFGs,
  95    linking them via interprocedural call and return edges.
  96
  97    Basic blocks are split at callsites, so that a call statement occurs
  98    twice: once at the end of a supernode, and a second instance at the
  99    start of the next supernode (to handle the return).  */
 100
 101 class supergraph : public digraph<supergraph_traits>
 102 {
 103 public:
 104   supergraph (logger *logger);
 105   ~supergraph ();
 106
 107   supernode *get_node_for_function_entry (function *fun) const
 108   {
 109     return get_node_for_block (ENTRY_BLOCK_PTR_FOR_FN (fun));
 110   }
 111
 112   supernode *get_node_for_function_exit (function *fun) const
 113   {
 114     return get_node_for_block (EXIT_BLOCK_PTR_FOR_FN (fun));
 115   }
 116
 117   supernode *get_node_for_block (basic_block bb) const
 118   {
 119     return *const_cast <bb_to_node_t &> (m_bb_to_initial_node).get (bb);
 120   }
 121
 122   /* Get the supernode containing the second half of the gcall *
 123      at an interprocedural call, within the caller.  */
 124   supernode *get_caller_next_node (cgraph_edge *edge) const
 125   {
 126     return (*const_cast <cgraph_edge_to_node_t &>
 127               (m_cgraph_edge_to_caller_next_node).get (edge));
 128   }
 129
 130   call_superedge *get_edge_for_call (cgraph_edge *edge) const
 131   {
 132     return (*const_cast <cgraph_edge_to_call_superedge_t &>
 133               (m_cgraph_edge_to_call_superedge).get (edge));
 134   }
 135
 136   return_superedge *get_edge_for_return (cgraph_edge *edge) const
 137   {
 138     return (*const_cast <cgraph_edge_to_return_superedge_t &>
 139               (m_cgraph_edge_to_return_superedge).get (edge));
 140   }
 141
 142   superedge *get_intraprocedural_edge_for_call (cgraph_edge *edge) const
 143   {
 144     return (*const_cast <cgraph_edge_to_intraproc_superedge_t &>
 145               (m_cgraph_edge_to_intraproc_superedge).get (edge));
 146   }
 147
 148   cfg_superedge *get_edge_for_cfg_edge (edge e) const
 149   {
 150     return (*const_cast <cfg_edge_to_cfg_superedge_t &>
 151               (m_cfg_edge_to_cfg_superedge).get (e));
 152   }
 153
 154   supernode *get_supernode_for_stmt (const gimple *stmt) const
 155   {
 156     return (*const_cast <stmt_to_node_t &>(m_stmt_to_node_t).get
 157             (const_cast <gimple *> (stmt)));
 158   }
 159
 160   void dump_dot_to_pp (pretty_printer *pp, const dump_args_t &) const;
 161   void dump_dot_to_file (FILE *fp, const dump_args_t &) const;
 162   void dump_dot (const char *path, const dump_args_t &) const;
 163
 164   json::object *to_json () const;
 165
 166   int num_nodes () const { return m_nodes.length (); }
 167   int num_edges () const { return m_edges.length (); }
 168
 169   supernode *get_node_by_index (int idx) const
 170   {
 171     return m_nodes[idx];
 172   }
 173
 174   unsigned get_num_snodes (const function *fun) const
 175   {
 176     function_to_num_snodes_t &map
 177       = const_cast <function_to_num_snodes_t &>(m_function_to_num_snodes);
 178     return *map.get (fun);
 179   }
 180
 181 private:
 182   supernode *add_node (function *fun, basic_block bb, gcall *returning_call,
 183                        gimple_seq phi_nodes);
 184   cfg_superedge *add_cfg_edge (supernode *src, supernode *dest, ::edge e);
 185   call_superedge *add_call_superedge (supernode *src, supernode *dest,
 186                                       cgraph_edge *cedge);
 187   return_superedge *add_return_superedge (supernode *src, supernode *dest,
 188                                           cgraph_edge *cedge);
 189
 190   /* Data.  */
 191
 192   typedef ordered_hash_map<basic_block, supernode *> bb_to_node_t;
 193   bb_to_node_t m_bb_to_initial_node;
 194   bb_to_node_t m_bb_to_final_node;
 195
 196   typedef ordered_hash_map<cgraph_edge *, supernode *> cgraph_edge_to_node_t;
 197   cgraph_edge_to_node_t m_cgraph_edge_to_caller_prev_node;
 198   cgraph_edge_to_node_t m_cgraph_edge_to_caller_next_node;
 199
 200   typedef ordered_hash_map< ::edge, cfg_superedge *>
 201     cfg_edge_to_cfg_superedge_t;
 202   cfg_edge_to_cfg_superedge_t m_cfg_edge_to_cfg_superedge;
 203
 204   typedef ordered_hash_map<cgraph_edge *, call_superedge *>
 205     cgraph_edge_to_call_superedge_t;
 206   cgraph_edge_to_call_superedge_t m_cgraph_edge_to_call_superedge;
 207
 208   typedef ordered_hash_map<cgraph_edge *, return_superedge *>
 209     cgraph_edge_to_return_superedge_t;
 210   cgraph_edge_to_return_superedge_t m_cgraph_edge_to_return_superedge;
 211
 212   typedef ordered_hash_map<cgraph_edge *, superedge *>
 213     cgraph_edge_to_intraproc_superedge_t;
 214   cgraph_edge_to_intraproc_superedge_t m_cgraph_edge_to_intraproc_superedge;
 215
 216   typedef ordered_hash_map<gimple *, supernode *> stmt_to_node_t;
 217   stmt_to_node_t m_stmt_to_node_t;
 218
 219   typedef hash_map<const function *, unsigned> function_to_num_snodes_t;
 220   function_to_num_snodes_t m_function_to_num_snodes;
 221
 222   saved_uids m_stmt_uids;
 223 };
 224
 225 /* A node within a supergraph.  */
 226
 227 class supernode : public dnode<supergraph_traits>
 228 {
 229  public:
 230   supernode (function *fun, basic_block bb, gcall *returning_call,
 231              gimple_seq phi_nodes, int index)
 232   : m_fun (fun), m_bb (bb), m_returning_call (returning_call),
 233     m_phi_nodes (phi_nodes), m_index (index)
 234   {}
 235
 236   function *get_function () const { return m_fun; }
 237
 238   bool entry_p () const
 239   {
 240     return m_bb == ENTRY_BLOCK_PTR_FOR_FN (m_fun);
 241   }
 242
 243   bool return_p () const
 244   {
 245     return m_bb == EXIT_BLOCK_PTR_FOR_FN (m_fun);
 246   }
 247
 248   void dump_dot (graphviz_out *gv, const dump_args_t &args) const OVERRIDE;
 249   void dump_dot_id (pretty_printer *pp) const;
 250
 251   json::object *to_json () const;
 252
 253   location_t get_start_location () const;
 254   location_t get_end_location () const;
 255
 256   /* Returns iterator at the start of the list of phi nodes, if any.  */
 257   gphi_iterator start_phis ()
 258   {
 259     gimple_seq *pseq = &m_phi_nodes;
 260
 261     /* Adapted from gsi_start_1. */
 262     gphi_iterator i;
 263
 264     i.ptr = gimple_seq_first (*pseq);
 265     i.seq = pseq;
 266     i.bb = i.ptr ? gimple_bb (i.ptr) : NULL;
 267
 268     return i;
 269   }
 270
 271   gcall *get_returning_call () const
 272   {
 273     return m_returning_call;
 274   }
 275
 276   gimple *get_last_stmt () const
 277   {
 278     if (m_stmts.length () == 0)
 279       return NULL;
 280     return m_stmts[m_stmts.length () - 1];
 281   }
 282
 283   gcall *get_final_call () const
 284   {
 285     gimple *stmt = get_last_stmt ();
 286     if (stmt == NULL)
 287       return NULL;
 288     return dyn_cast<gcall *> (stmt);
 289   }
 290
 291   unsigned int get_stmt_index (const gimple *stmt) const;
 292
 293   function * const m_fun; // alternatively could be stored as runs of indices within the supergraph
 294   const basic_block m_bb;
 295   gcall * const m_returning_call; // for handling the result of a returned call
 296   gimple_seq m_phi_nodes; // ptr to that of the underlying BB, for the first supernode for the BB
 297   auto_vec<gimple *> m_stmts;
 298   const int m_index; /* unique within the supergraph as a whole.  */
 299 };
 300
 301 /* An abstract base class encapsulating an edge within a supergraph.
 302    Edges can be CFG edges, or calls/returns for callgraph edges.  */
 303
 304 class superedge : public dedge<supergraph_traits>
 305 {
 306  public:
 307   virtual ~superedge () {}
 308
 309   void dump (pretty_printer *pp) const;
 310   void dump () const;
 311   void dump_dot (graphviz_out *gv, const dump_args_t &args) const;
 312
 313   virtual void dump_label_to_pp (pretty_printer *pp,
 314                                  bool user_facing) const = 0;
 315
 316   json::object *to_json () const;
 317
 318   enum edge_kind get_kind () const { return m_kind; }
 319
 320   virtual cfg_superedge *dyn_cast_cfg_superedge () { return NULL; }
 321   virtual const cfg_superedge *dyn_cast_cfg_superedge () const { return NULL; }
 322   virtual const switch_cfg_superedge *dyn_cast_switch_cfg_superedge () const { return NULL; }
 323   virtual callgraph_superedge *dyn_cast_callgraph_superedge () { return NULL; }
 324   virtual const callgraph_superedge *dyn_cast_callgraph_superedge () const { return NULL; }
 325   virtual call_superedge *dyn_cast_call_superedge () { return NULL; }
 326   virtual const call_superedge *dyn_cast_call_superedge () const { return NULL; }
 327   virtual return_superedge *dyn_cast_return_superedge () { return NULL; }
 328   virtual const return_superedge *dyn_cast_return_superedge () const { return NULL; }
 329
 330   ::edge get_any_cfg_edge () const;
 331   cgraph_edge *get_any_callgraph_edge () const;
 332
 333   char *get_description (bool user_facing) const;
 334
 335  protected:
 336   superedge (supernode *src, supernode *dest, enum edge_kind kind)
 337   : dedge<supergraph_traits> (src, dest),
 338     m_kind (kind)
 339   {}
 340
 341  public:
 342   const enum edge_kind m_kind;
 343 };
 344
 345 /* An ID representing an expression at a callsite:
 346    either a parameter index, or the return value (or unknown).  */
 347
 348 class callsite_expr
 349 {
 350  public:
 351   callsite_expr () : m_val (-1) {}
 352
 353   static callsite_expr from_zero_based_param (int idx)
 354   {
 355     return callsite_expr (idx + 1);
 356   }
 357
 358   static callsite_expr from_return_value ()
 359   {
 360     return callsite_expr (0);
 361   }
 362
 363   bool param_p () const
 364   {
 365     return m_val > 0;
 366   }
 367
 368   bool return_value_p () const
 369   {
 370     return m_val == 0;
 371   }
 372
 373  private:
 374   callsite_expr (int val) : m_val (val) {}
 375
 376   int m_val; /* 1-based parm, 0 for return value, or -1 for "unknown".  */
 377 };
 378
 379 /* A subclass of superedge with an associated callgraph edge (either a
 380    call or a return).  */
 381
 382 class callgraph_superedge : public superedge
 383 {
 384  public:
 385   callgraph_superedge (supernode *src, supernode *dst, enum edge_kind kind,
 386                        cgraph_edge *cedge)
 387   : superedge (src, dst, kind),
 388     m_cedge (cedge)
 389   {}
 390
 391   void dump_label_to_pp (pretty_printer *pp, bool user_facing) const
 392     FINAL OVERRIDE;
 393
 394   callgraph_superedge *dyn_cast_callgraph_superedge () FINAL OVERRIDE
 395   {
 396     return this;
 397   }
 398   const callgraph_superedge *dyn_cast_callgraph_superedge () const
 399     FINAL OVERRIDE
 400   {
 401     return this;
 402   }
 403
 404   function *get_callee_function () const;
 405   function *get_caller_function () const;
 406   tree get_callee_decl () const;
 407   tree get_caller_decl () const;
 408   gcall *get_call_stmt () const;
 409   tree get_arg_for_parm (tree parm, callsite_expr *out) const;
 410   tree get_parm_for_arg (tree arg, callsite_expr *out) const;
 411   tree map_expr_from_caller_to_callee (tree caller_expr,
 412                                        callsite_expr *out) const;
 413   tree map_expr_from_callee_to_caller (tree callee_expr,
 414                                        callsite_expr *out) const;
 415
 416   cgraph_edge *const m_cedge;
 417 };
 418
 419 } // namespace ana
 420
 421 template <>
 422 template <>
 423 inline bool
 424 is_a_helper <const callgraph_superedge *>::test (const superedge *sedge)
 425 {
 426   return (sedge->get_kind () == SUPEREDGE_INTRAPROCEDURAL_CALL
 427           || sedge->get_kind () == SUPEREDGE_CALL
 428           || sedge->get_kind () == SUPEREDGE_RETURN);
 429 }
 430
 431 namespace ana {
 432
 433 /* A subclass of superedge representing an interprocedural call.  */
 434
 435 class call_superedge : public callgraph_superedge
 436 {
 437  public:
 438   call_superedge (supernode *src, supernode *dst, cgraph_edge *cedge)
 439   : callgraph_superedge (src, dst, SUPEREDGE_CALL, cedge)
 440   {}
 441
 442   call_superedge *dyn_cast_call_superedge () FINAL OVERRIDE
 443   {
 444     return this;
 445   }
 446   const call_superedge *dyn_cast_call_superedge () const FINAL OVERRIDE
 447   {
 448     return this;
 449   }
 450
 451   return_superedge *get_edge_for_return (const supergraph &sg) const
 452   {
 453     return sg.get_edge_for_return (m_cedge);
 454   }
 455 };
 456
 457 } // namespace ana
 458
 459 template <>
 460 template <>
 461 inline bool
 462 is_a_helper <const call_superedge *>::test (const superedge *sedge)
 463 {
 464   return sedge->get_kind () == SUPEREDGE_CALL;
 465 }
 466
 467 namespace ana {
 468
 469 /* A subclass of superedge represesnting an interprocedural return.  */
 470
 471 class return_superedge : public callgraph_superedge
 472 {
 473  public:
 474   return_superedge (supernode *src, supernode *dst, cgraph_edge *cedge)
 475   : callgraph_superedge (src, dst, SUPEREDGE_RETURN, cedge)
 476   {}
 477
 478   return_superedge *dyn_cast_return_superedge () FINAL OVERRIDE { return this; }
 479   const return_superedge *dyn_cast_return_superedge () const FINAL OVERRIDE
 480   {
 481     return this;
 482   }
 483
 484   call_superedge *get_edge_for_call (const supergraph &sg) const
 485   {
 486     return sg.get_edge_for_call (m_cedge);
 487   }
 488 };
 489
 490 } // namespace ana
 491
 492 template <>
 493 template <>
 494 inline bool
 495 is_a_helper <const return_superedge *>::test (const superedge *sedge)
 496 {
 497   return sedge->get_kind () == SUPEREDGE_RETURN;
 498 }
 499
 500 namespace ana {
 501
 502 /* A subclass of superedge that corresponds to a CFG edge.  */
 503
 504 class cfg_superedge : public superedge
 505 {
 506  public:
 507   cfg_superedge (supernode *src, supernode *dst, ::edge e)
 508   : superedge (src, dst, SUPEREDGE_CFG_EDGE),
 509     m_cfg_edge (e)
 510   {}
 511
 512   void dump_label_to_pp (pretty_printer *pp, bool user_facing) const OVERRIDE;
 513   cfg_superedge *dyn_cast_cfg_superedge () FINAL OVERRIDE { return this; }
 514   const cfg_superedge *dyn_cast_cfg_superedge () const FINAL OVERRIDE { return this; }
 515
 516   ::edge get_cfg_edge () const { return m_cfg_edge; }
 517   int get_flags () const { return m_cfg_edge->flags; }
 518   int true_value_p () const { return get_flags () & EDGE_TRUE_VALUE; }
 519   int false_value_p () const { return get_flags () & EDGE_FALSE_VALUE; }
 520   int back_edge_p () const { return get_flags () & EDGE_DFS_BACK; }
 521
 522   size_t get_phi_arg_idx () const;
 523   tree get_phi_arg (const gphi *phi) const;
 524
 525  private:
 526   const ::edge m_cfg_edge;
 527 };
 528
 529 } // namespace ana
 530
 531 template <>
 532 template <>
 533 inline bool
 534 is_a_helper <const cfg_superedge *>::test (const superedge *sedge)
 535 {
 536   return sedge->get_kind () == SUPEREDGE_CFG_EDGE;
 537 }
 538
 539 namespace ana {
 540
 541 /* A subclass for edges from switch statements, retaining enough
 542    information to identify the pertinent cases, and for adding labels
 543    when rendering via graphviz.  */
 544
 545 class switch_cfg_superedge : public cfg_superedge {
 546  public:
 547   switch_cfg_superedge (supernode *src, supernode *dst, ::edge e);
 548
 549   const switch_cfg_superedge *dyn_cast_switch_cfg_superedge () const
 550     FINAL OVERRIDE
 551   {
 552     return this;
 553   }
 554
 555   void dump_label_to_pp (pretty_printer *pp, bool user_facing) const
 556     FINAL OVERRIDE;
 557
 558   gswitch *get_switch_stmt () const
 559   {
 560     return as_a <gswitch *> (m_src->get_last_stmt ());
 561   }
 562
 563   const vec<tree> &get_case_labels () const { return m_case_labels; }
 564
 565 private:
 566   auto_vec<tree> m_case_labels;
 567 };
 568
 569 } // namespace ana
 570
 571 template <>
 572 template <>
 573 inline bool
 574 is_a_helper <const switch_cfg_superedge *>::test (const superedge *sedge)
 575 {
 576   return sedge->dyn_cast_switch_cfg_superedge () != NULL;
 577 }
 578
 579 namespace ana {
 580
 581 /* Base class for adding additional content to the .dot output
 582    for a supergraph.  */
 583
 584 class dot_annotator
 585 {
 586  public:
 587   virtual ~dot_annotator () {}
 588   virtual bool add_node_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
 589                                      const supernode &n ATTRIBUTE_UNUSED,
 590                                      bool within_table ATTRIBUTE_UNUSED)
 591     const
 592   {
 593     return false;
 594   }
 595   virtual void add_stmt_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
 596                                      const gimple *stmt ATTRIBUTE_UNUSED,
 597                                      bool within_row ATTRIBUTE_UNUSED)
 598     const {}
 599   virtual bool add_after_node_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
 600                                            const supernode &n ATTRIBUTE_UNUSED)
 601     const
 602   {
 603     return false;
 604   }
 605 };
 606
 607 extern cgraph_edge *supergraph_call_edge (function *fun, gimple *stmt);
 608
 609 } // namespace ana
 610
 611 #endif /* GCC_ANALYZER_SUPERGRAPH_H */