gcc/analyzer/supergraph.h

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