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