gcc/analyzer/supergraph.h

   1 /* "Supergraph" classes that combine CFGs and callgraph into one digraph.
   2    Copyright (C) 2019-2022 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 (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 (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   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   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   function * const m_fun; // alternatively could be stored as runs of indices within the supergraph
 301   const basic_block m_bb;
 302   gcall * const m_returning_call; // for handling the result of a returned call
 303   gimple_seq m_phi_nodes; // ptr to that of the underlying BB, for the first supernode for the BB
 304   auto_vec<gimple *> m_stmts;
 305   const int m_index; /* unique within the supergraph as a whole.  */
 306 };
 307
 308 /* An abstract base class encapsulating an edge within a supergraph.
 309    Edges can be CFG edges, or calls/returns for callgraph edges.  */
 310
 311 class superedge : public dedge<supergraph_traits>
 312 {
 313  public:
 314   virtual ~superedge () {}
 315
 316   void dump (pretty_printer *pp) const;
 317   void dump () const;
 318   void dump_dot (graphviz_out *gv, const dump_args_t &args)
 319     const final override;
 320
 321   virtual void dump_label_to_pp (pretty_printer *pp,
 322                                  bool user_facing) const = 0;
 323
 324   json::object *to_json () const;
 325
 326   enum edge_kind get_kind () const { return m_kind; }
 327
 328   virtual cfg_superedge *dyn_cast_cfg_superedge () { return NULL; }
 329   virtual const cfg_superedge *dyn_cast_cfg_superedge () const { return NULL; }
 330   virtual const switch_cfg_superedge *dyn_cast_switch_cfg_superedge () const { return NULL; }
 331   virtual callgraph_superedge *dyn_cast_callgraph_superedge () { return NULL; }
 332   virtual const callgraph_superedge *dyn_cast_callgraph_superedge () const { return NULL; }
 333   virtual call_superedge *dyn_cast_call_superedge () { return NULL; }
 334   virtual const call_superedge *dyn_cast_call_superedge () const { return NULL; }
 335   virtual return_superedge *dyn_cast_return_superedge () { return NULL; }
 336   virtual const return_superedge *dyn_cast_return_superedge () const { return NULL; }
 337
 338   ::edge get_any_cfg_edge () const;
 339   cgraph_edge *get_any_callgraph_edge () const;
 340
 341   label_text get_description (bool user_facing) const;
 342
 343  protected:
 344   superedge (supernode *src, supernode *dest, enum edge_kind kind)
 345   : dedge<supergraph_traits> (src, dest),
 346     m_kind (kind)
 347   {}
 348
 349  public:
 350   const enum edge_kind m_kind;
 351 };
 352
 353 /* An ID representing an expression at a callsite:
 354    either a parameter index, or the return value (or unknown).  */
 355
 356 class callsite_expr
 357 {
 358  public:
 359   callsite_expr () : m_val (-1) {}
 360
 361   static callsite_expr from_zero_based_param (int idx)
 362   {
 363     return callsite_expr (idx + 1);
 364   }
 365
 366   static callsite_expr from_return_value ()
 367   {
 368     return callsite_expr (0);
 369   }
 370
 371   bool param_p () const
 372   {
 373     return m_val > 0;
 374   }
 375
 376   bool return_value_p () const
 377   {
 378     return m_val == 0;
 379   }
 380
 381  private:
 382   callsite_expr (int val) : m_val (val) {}
 383
 384   int m_val; /* 1-based parm, 0 for return value, or -1 for "unknown".  */
 385 };
 386
 387 /* A subclass of superedge with an associated callgraph edge (either a
 388    call or a return).  */
 389
 390 class callgraph_superedge : public superedge
 391 {
 392  public:
 393   callgraph_superedge (supernode *src, supernode *dst, enum edge_kind kind,
 394                        cgraph_edge *cedge)
 395   : superedge (src, dst, kind),
 396     m_cedge (cedge)
 397   {}
 398
 399   void dump_label_to_pp (pretty_printer *pp, bool user_facing) const
 400     final override;
 401
 402   callgraph_superedge *dyn_cast_callgraph_superedge () final override
 403   {
 404     return this;
 405   }
 406   const callgraph_superedge *dyn_cast_callgraph_superedge () const
 407     final override
 408   {
 409     return this;
 410   }
 411
 412   function *get_callee_function () const;
 413   function *get_caller_function () const;
 414   tree get_callee_decl () const;
 415   tree get_caller_decl () const;
 416   gcall *get_call_stmt () const;
 417   tree get_arg_for_parm (tree parm, callsite_expr *out) const;
 418   tree get_parm_for_arg (tree arg, callsite_expr *out) const;
 419   tree map_expr_from_caller_to_callee (tree caller_expr,
 420                                        callsite_expr *out) const;
 421   tree map_expr_from_callee_to_caller (tree callee_expr,
 422                                        callsite_expr *out) const;
 423
 424   cgraph_edge *const m_cedge;
 425 };
 426
 427 } // namespace ana
 428
 429 template <>
 430 template <>
 431 inline bool
 432 is_a_helper <const callgraph_superedge *>::test (const superedge *sedge)
 433 {
 434   return (sedge->get_kind () == SUPEREDGE_INTRAPROCEDURAL_CALL
 435           || sedge->get_kind () == SUPEREDGE_CALL
 436           || sedge->get_kind () == SUPEREDGE_RETURN);
 437 }
 438
 439 namespace ana {
 440
 441 /* A subclass of superedge representing an interprocedural call.  */
 442
 443 class call_superedge : public callgraph_superedge
 444 {
 445  public:
 446   call_superedge (supernode *src, supernode *dst, cgraph_edge *cedge)
 447   : callgraph_superedge (src, dst, SUPEREDGE_CALL, cedge)
 448   {}
 449
 450   call_superedge *dyn_cast_call_superedge () final override
 451   {
 452     return this;
 453   }
 454   const call_superedge *dyn_cast_call_superedge () const final override
 455   {
 456     return this;
 457   }
 458
 459   return_superedge *get_edge_for_return (const supergraph &sg) const
 460   {
 461     return sg.get_edge_for_return (m_cedge);
 462   }
 463 };
 464
 465 } // namespace ana
 466
 467 template <>
 468 template <>
 469 inline bool
 470 is_a_helper <const call_superedge *>::test (const superedge *sedge)
 471 {
 472   return sedge->get_kind () == SUPEREDGE_CALL;
 473 }
 474
 475 namespace ana {
 476
 477 /* A subclass of superedge represesnting an interprocedural return.  */
 478
 479 class return_superedge : public callgraph_superedge
 480 {
 481  public:
 482   return_superedge (supernode *src, supernode *dst, cgraph_edge *cedge)
 483   : callgraph_superedge (src, dst, SUPEREDGE_RETURN, cedge)
 484   {}
 485
 486   return_superedge *dyn_cast_return_superedge () final override { return this; }
 487   const return_superedge *dyn_cast_return_superedge () const final override
 488   {
 489     return this;
 490   }
 491
 492   call_superedge *get_edge_for_call (const supergraph &sg) const
 493   {
 494     return sg.get_edge_for_call (m_cedge);
 495   }
 496 };
 497
 498 } // namespace ana
 499
 500 template <>
 501 template <>
 502 inline bool
 503 is_a_helper <const return_superedge *>::test (const superedge *sedge)
 504 {
 505   return sedge->get_kind () == SUPEREDGE_RETURN;
 506 }
 507
 508 namespace ana {
 509
 510 /* A subclass of superedge that corresponds to a CFG edge.  */
 511
 512 class cfg_superedge : public superedge
 513 {
 514  public:
 515   cfg_superedge (supernode *src, supernode *dst, ::edge e)
 516   : superedge (src, dst, SUPEREDGE_CFG_EDGE),
 517     m_cfg_edge (e)
 518   {}
 519
 520   void dump_label_to_pp (pretty_printer *pp, bool user_facing) const override;
 521   cfg_superedge *dyn_cast_cfg_superedge () final override { return this; }
 522   const cfg_superedge *dyn_cast_cfg_superedge () const final override { return this; }
 523
 524   ::edge get_cfg_edge () const { return m_cfg_edge; }
 525   int get_flags () const { return m_cfg_edge->flags; }
 526   int true_value_p () const { return get_flags () & EDGE_TRUE_VALUE; }
 527   int false_value_p () const { return get_flags () & EDGE_FALSE_VALUE; }
 528   int back_edge_p () const { return get_flags () & EDGE_DFS_BACK; }
 529
 530   size_t get_phi_arg_idx () const;
 531   tree get_phi_arg (const gphi *phi) const;
 532
 533  private:
 534   const ::edge m_cfg_edge;
 535 };
 536
 537 } // namespace ana
 538
 539 template <>
 540 template <>
 541 inline bool
 542 is_a_helper <const cfg_superedge *>::test (const superedge *sedge)
 543 {
 544   return sedge->get_kind () == SUPEREDGE_CFG_EDGE;
 545 }
 546
 547 namespace ana {
 548
 549 /* A subclass for edges from switch statements, retaining enough
 550    information to identify the pertinent cases, and for adding labels
 551    when rendering via graphviz.  */
 552
 553 class switch_cfg_superedge : public cfg_superedge {
 554  public:
 555   switch_cfg_superedge (supernode *src, supernode *dst, ::edge e);
 556
 557   const switch_cfg_superedge *dyn_cast_switch_cfg_superedge () const
 558     final override
 559   {
 560     return this;
 561   }
 562
 563   void dump_label_to_pp (pretty_printer *pp, bool user_facing) const
 564     final override;
 565
 566   gswitch *get_switch_stmt () const
 567   {
 568     return as_a <gswitch *> (m_src->get_last_stmt ());
 569   }
 570
 571   const vec<tree> &get_case_labels () const { return m_case_labels; }
 572
 573   bool implicitly_created_default_p () const;
 574
 575 private:
 576   auto_vec<tree> m_case_labels;
 577 };
 578
 579 } // namespace ana
 580
 581 template <>
 582 template <>
 583 inline bool
 584 is_a_helper <const switch_cfg_superedge *>::test (const superedge *sedge)
 585 {
 586   return sedge->dyn_cast_switch_cfg_superedge () != NULL;
 587 }
 588
 589 namespace ana {
 590
 591 /* Base class for adding additional content to the .dot output
 592    for a supergraph.  */
 593
 594 class dot_annotator
 595 {
 596  public:
 597   virtual ~dot_annotator () {}
 598   virtual bool add_node_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
 599                                      const supernode &n ATTRIBUTE_UNUSED,
 600                                      bool within_table ATTRIBUTE_UNUSED)
 601     const
 602   {
 603     return false;
 604   }
 605   virtual void add_stmt_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
 606                                      const gimple *stmt ATTRIBUTE_UNUSED,
 607                                      bool within_row ATTRIBUTE_UNUSED)
 608     const {}
 609   virtual bool add_after_node_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
 610                                            const supernode &n ATTRIBUTE_UNUSED)
 611     const
 612   {
 613     return false;
 614   }
 615 };
 616
 617 extern cgraph_edge *supergraph_call_edge (function *fun, const gimple *stmt);
 618 extern function *get_ultimate_function_for_cgraph_edge (cgraph_edge *edge);
 619
 620 } // namespace ana
 621
 622 #endif /* GCC_ANALYZER_SUPERGRAPH_H */