gcc/analyzer/supergraph.h

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