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