1251876Speter/* "Supergraph" classes that combine CFGs and callgraph into one digraph. 2251876Speter Copyright (C) 2019-2022 Free Software Foundation, Inc. 3251876Speter Contributed by David Malcolm <dmalcolm@redhat.com>. 4251876Speter 5251876SpeterThis file is part of GCC. 6251876Speter 7251876SpeterGCC is free software; you can redistribute it and/or modify it 8251876Speterunder the terms of the GNU General Public License as published by 9251876Speterthe Free Software Foundation; either version 3, or (at your option) 10251876Speterany later version. 11251876Speter 12251876SpeterGCC is distributed in the hope that it will be useful, but 13251876SpeterWITHOUT ANY WARRANTY; without even the implied warranty of 14251876SpeterMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15251876SpeterGeneral Public License for more details. 16251876Speter 17251876SpeterYou should have received a copy of the GNU General Public License 18251876Speteralong with GCC; see the file COPYING3. If not see 19251876Speter<http://www.gnu.org/licenses/>. */ 20251876Speter 21251876Speter#ifndef GCC_ANALYZER_SUPERGRAPH_H 22251876Speter#define GCC_ANALYZER_SUPERGRAPH_H 23251876Speter 24251876Speterusing namespace ana; 25251876Speter 26251876Speternamespace ana { 27251876Speter 28251876Speter/* Forward decls, using indentation to show inheritance. */ 29251876Speter 30251876Speterclass supergraph; 31251876Speterclass supernode; 32251876Speterclass superedge; 33251876Speter class callgraph_superedge; 34251876Speter class call_superedge; 35251876Speter class return_superedge; 36251876Speter class cfg_superedge; 37251876Speter class switch_cfg_superedge; 38251876Speterclass supercluster; 39251876Speterclass dot_annotator; 40251876Speter 41251876Speterclass logger; 42251876Speter 43251876Speter/* An enum for discriminating between superedge subclasses. */ 44251876Speter 45251876Speterenum edge_kind 46251876Speter{ 47251876Speter SUPEREDGE_CFG_EDGE, 48251876Speter SUPEREDGE_CALL, 49251876Speter SUPEREDGE_RETURN, 50251876Speter SUPEREDGE_INTRAPROCEDURAL_CALL 51251876Speter}; 52251876Speter 53251876Speter/* Flags for controlling the appearance of .dot dumps. */ 54251876Speter 55251876Speterenum supergraph_dot_flags 56251876Speter{ 57251876Speter SUPERGRAPH_DOT_SHOW_BBS = (1 << 0) 58251876Speter}; 59251876Speter 60251876Speter/* A traits struct describing the family of node, edge and digraph 61251876Speter classes for supergraphs. */ 62251876Speter 63251876Speterstruct supergraph_traits 64251876Speter{ 65251876Speter typedef supernode node_t; 66251876Speter typedef superedge edge_t; 67251876Speter typedef supergraph graph_t; 68251876Speter struct dump_args_t 69251876Speter { 70251876Speter dump_args_t (enum supergraph_dot_flags flags, 71251876Speter const dot_annotator *node_annotator) 72251876Speter : m_flags (flags), 73251876Speter m_node_annotator (node_annotator) 74251876Speter {} 75251876Speter 76251876Speter enum supergraph_dot_flags m_flags; 77251876Speter const dot_annotator *m_node_annotator; 78251876Speter }; 79251876Speter typedef supercluster cluster_t; 80251876Speter}; 81251876Speter 82251876Speter/* A class to manage the setting and restoring of statement uids. */ 83251876Speter 84251876Speterclass saved_uids 85251876Speter{ 86251876Speterpublic: 87251876Speter void make_uid_unique (gimple *stmt); 88251876Speter void restore_uids () const; 89251876Speter 90251876Speterprivate: 91251876Speter auto_vec<std::pair<gimple *, unsigned> > m_old_stmt_uids; 92251876Speter}; 93251876Speter 94251876Speter/* A "supergraph" is a directed graph formed by joining together all CFGs, 95251876Speter linking them via interprocedural call and return edges. 96251876Speter 97251876Speter Basic blocks are split at callsites, so that a call statement occurs 98251876Speter twice: once at the end of a supernode, and a second instance at the 99251876Speter start of the next supernode (to handle the return). */ 100251876Speter 101251876Speterclass supergraph : public digraph<supergraph_traits> 102251876Speter{ 103251876Speterpublic: 104251876Speter supergraph (logger *logger); 105251876Speter ~supergraph (); 106251876Speter 107251876Speter supernode *get_node_for_function_entry (function *fun) const 108251876Speter { 109251876Speter return get_node_for_block (ENTRY_BLOCK_PTR_FOR_FN (fun)); 110251876Speter } 111251876Speter 112251876Speter supernode *get_node_for_function_exit (function *fun) const 113251876Speter { 114251876Speter return get_node_for_block (EXIT_BLOCK_PTR_FOR_FN (fun)); 115251876Speter } 116251876Speter 117251876Speter supernode *get_node_for_block (basic_block bb) const 118251876Speter { 119251876Speter return *const_cast <bb_to_node_t &> (m_bb_to_initial_node).get (bb); 120251876Speter } 121251876Speter 122251876Speter /* Get the supernode containing the second half of the gcall * 123251876Speter at an interprocedural call, within the caller. */ 124251876Speter supernode *get_caller_next_node (cgraph_edge *edge) const 125251876Speter { 126251876Speter return (*const_cast <cgraph_edge_to_node_t &> 127251876Speter (m_cgraph_edge_to_caller_next_node).get (edge)); 128251876Speter } 129251876Speter 130251876Speter call_superedge *get_edge_for_call (cgraph_edge *edge) const 131251876Speter { 132251876Speter return (*const_cast <cgraph_edge_to_call_superedge_t &> 133251876Speter (m_cgraph_edge_to_call_superedge).get (edge)); 134251876Speter } 135251876Speter 136251876Speter return_superedge *get_edge_for_return (cgraph_edge *edge) const 137251876Speter { 138251876Speter return (*const_cast <cgraph_edge_to_return_superedge_t &> 139251876Speter (m_cgraph_edge_to_return_superedge).get (edge)); 140251876Speter } 141251876Speter 142251876Speter superedge *get_intraprocedural_edge_for_call (cgraph_edge *edge) const 143251876Speter { 144251876Speter return (*const_cast <cgraph_edge_to_intraproc_superedge_t &> 145251876Speter (m_cgraph_edge_to_intraproc_superedge).get (edge)); 146251876Speter } 147251876Speter 148251876Speter cfg_superedge *get_edge_for_cfg_edge (edge e) const 149251876Speter { 150251876Speter return (*const_cast <cfg_edge_to_cfg_superedge_t &> 151251876Speter (m_cfg_edge_to_cfg_superedge).get (e)); 152251876Speter } 153251876Speter 154251876Speter supernode *get_supernode_for_stmt (const gimple *stmt) const 155251876Speter { 156251876Speter return (*const_cast <stmt_to_node_t &>(m_stmt_to_node_t).get 157251876Speter (const_cast <gimple *> (stmt))); 158251876Speter } 159251876Speter 160251876Speter void dump_dot_to_pp (pretty_printer *pp, const dump_args_t &) const; 161251876Speter void dump_dot_to_file (FILE *fp, const dump_args_t &) const; 162251876Speter void dump_dot (const char *path, const dump_args_t &) const; 163251876Speter 164251876Speter json::object *to_json () const; 165251876Speter 166251876Speter int num_nodes () const { return m_nodes.length (); } 167251876Speter int num_edges () const { return m_edges.length (); } 168251876Speter 169251876Speter supernode *get_node_by_index (int idx) const 170251876Speter { 171251876Speter return m_nodes[idx]; 172251876Speter } 173251876Speter 174251876Speter unsigned get_num_snodes (const function *fun) const 175251876Speter { 176251876Speter function_to_num_snodes_t &map 177251876Speter = const_cast <function_to_num_snodes_t &>(m_function_to_num_snodes); 178251876Speter return *map.get (fun); 179251876Speter } 180251876Speter 181251876Speterprivate: 182251876Speter supernode *add_node (function *fun, basic_block bb, gcall *returning_call, 183251876Speter gimple_seq phi_nodes); 184251876Speter cfg_superedge *add_cfg_edge (supernode *src, supernode *dest, ::edge e); 185251876Speter call_superedge *add_call_superedge (supernode *src, supernode *dest, 186251876Speter cgraph_edge *cedge); 187251876Speter return_superedge *add_return_superedge (supernode *src, supernode *dest, 188251876Speter cgraph_edge *cedge); 189251876Speter 190251876Speter /* Data. */ 191251876Speter 192251876Speter typedef ordered_hash_map<basic_block, supernode *> bb_to_node_t; 193251876Speter bb_to_node_t m_bb_to_initial_node; 194251876Speter bb_to_node_t m_bb_to_final_node; 195251876Speter 196251876Speter typedef ordered_hash_map<cgraph_edge *, supernode *> cgraph_edge_to_node_t; 197251876Speter cgraph_edge_to_node_t m_cgraph_edge_to_caller_prev_node; 198251876Speter cgraph_edge_to_node_t m_cgraph_edge_to_caller_next_node; 199251876Speter 200251876Speter typedef ordered_hash_map< ::edge, cfg_superedge *> 201251876Speter cfg_edge_to_cfg_superedge_t; 202251876Speter cfg_edge_to_cfg_superedge_t m_cfg_edge_to_cfg_superedge; 203251876Speter 204251876Speter typedef ordered_hash_map<cgraph_edge *, call_superedge *> 205251876Speter cgraph_edge_to_call_superedge_t; 206251876Speter cgraph_edge_to_call_superedge_t m_cgraph_edge_to_call_superedge; 207251876Speter 208251876Speter typedef ordered_hash_map<cgraph_edge *, return_superedge *> 209251876Speter cgraph_edge_to_return_superedge_t; 210251876Speter cgraph_edge_to_return_superedge_t m_cgraph_edge_to_return_superedge; 211251876Speter 212251876Speter typedef ordered_hash_map<cgraph_edge *, superedge *> 213251876Speter cgraph_edge_to_intraproc_superedge_t; 214251876Speter cgraph_edge_to_intraproc_superedge_t m_cgraph_edge_to_intraproc_superedge; 215251876Speter 216251876Speter typedef ordered_hash_map<gimple *, supernode *> stmt_to_node_t; 217251876Speter stmt_to_node_t m_stmt_to_node_t; 218251876Speter 219251876Speter typedef hash_map<const function *, unsigned> function_to_num_snodes_t; 220251876Speter function_to_num_snodes_t m_function_to_num_snodes; 221251876Speter 222251876Speter saved_uids m_stmt_uids; 223251876Speter}; 224251876Speter 225251876Speter/* A node within a supergraph. */ 226251876Speter 227251876Speterclass supernode : public dnode<supergraph_traits> 228251876Speter{ 229251876Speter public: 230251876Speter supernode (function *fun, basic_block bb, gcall *returning_call, 231251876Speter gimple_seq phi_nodes, int index) 232251876Speter : m_fun (fun), m_bb (bb), m_returning_call (returning_call), 233251876Speter m_phi_nodes (phi_nodes), m_index (index) 234251876Speter {} 235251876Speter 236251876Speter function *get_function () const { return m_fun; } 237251876Speter 238251876Speter bool entry_p () const 239251876Speter { 240251876Speter return m_bb == ENTRY_BLOCK_PTR_FOR_FN (m_fun); 241251876Speter } 242251876Speter 243251876Speter bool return_p () const 244251876Speter { 245251876Speter return m_bb == EXIT_BLOCK_PTR_FOR_FN (m_fun); 246251876Speter } 247251876Speter 248251876Speter void dump_dot (graphviz_out *gv, const dump_args_t &args) const OVERRIDE; 249251876Speter void dump_dot_id (pretty_printer *pp) const; 250251876Speter 251251876Speter json::object *to_json () const; 252251876Speter 253251876Speter location_t get_start_location () const; 254251876Speter location_t get_end_location () const; 255251876Speter 256251876Speter /* Returns iterator at the start of the list of phi nodes, if any. */ 257251876Speter gphi_iterator start_phis () 258251876Speter { 259251876Speter gimple_seq *pseq = &m_phi_nodes; 260251876Speter 261251876Speter /* Adapted from gsi_start_1. */ 262251876Speter gphi_iterator i; 263251876Speter 264251876Speter i.ptr = gimple_seq_first (*pseq); 265251876Speter i.seq = pseq; 266251876Speter i.bb = i.ptr ? gimple_bb (i.ptr) : NULL; 267251876Speter 268251876Speter return i; 269251876Speter } 270251876Speter 271251876Speter gcall *get_returning_call () const 272251876Speter { 273251876Speter return m_returning_call; 274251876Speter } 275251876Speter 276251876Speter gimple *get_last_stmt () const 277251876Speter { 278251876Speter if (m_stmts.length () == 0) 279251876Speter return NULL; 280251876Speter return m_stmts[m_stmts.length () - 1]; 281251876Speter } 282251876Speter 283251876Speter gcall *get_final_call () const 284251876Speter { 285251876Speter gimple *stmt = get_last_stmt (); 286251876Speter if (stmt == NULL) 287251876Speter return NULL; 288251876Speter return dyn_cast<gcall *> (stmt); 289251876Speter } 290251876Speter 291251876Speter unsigned int get_stmt_index (const gimple *stmt) const; 292251876Speter 293251876Speter function * const m_fun; // alternatively could be stored as runs of indices within the supergraph 294251876Speter const basic_block m_bb; 295251876Speter gcall * const m_returning_call; // for handling the result of a returned call 296251876Speter gimple_seq m_phi_nodes; // ptr to that of the underlying BB, for the first supernode for the BB 297251876Speter auto_vec<gimple *> m_stmts; 298251876Speter const int m_index; /* unique within the supergraph as a whole. */ 299251876Speter}; 300251876Speter 301251876Speter/* An abstract base class encapsulating an edge within a supergraph. 302251876Speter Edges can be CFG edges, or calls/returns for callgraph edges. */ 303251876Speter 304251876Speterclass superedge : public dedge<supergraph_traits> 305251876Speter{ 306251876Speter public: 307251876Speter virtual ~superedge () {} 308251876Speter 309251876Speter void dump (pretty_printer *pp) const; 310251876Speter void dump () const; 311251876Speter void dump_dot (graphviz_out *gv, const dump_args_t &args) const; 312251876Speter 313251876Speter virtual void dump_label_to_pp (pretty_printer *pp, 314251876Speter bool user_facing) const = 0; 315251876Speter 316251876Speter json::object *to_json () const; 317251876Speter 318251876Speter enum edge_kind get_kind () const { return m_kind; } 319251876Speter 320251876Speter virtual cfg_superedge *dyn_cast_cfg_superedge () { return NULL; } 321251876Speter virtual const cfg_superedge *dyn_cast_cfg_superedge () const { return NULL; } 322251876Speter virtual const switch_cfg_superedge *dyn_cast_switch_cfg_superedge () const { return NULL; } 323251876Speter virtual callgraph_superedge *dyn_cast_callgraph_superedge () { return NULL; } 324251876Speter virtual const callgraph_superedge *dyn_cast_callgraph_superedge () const { return NULL; } 325251876Speter virtual call_superedge *dyn_cast_call_superedge () { return NULL; } 326251876Speter virtual const call_superedge *dyn_cast_call_superedge () const { return NULL; } 327251876Speter virtual return_superedge *dyn_cast_return_superedge () { return NULL; } 328251876Speter virtual const return_superedge *dyn_cast_return_superedge () const { return NULL; } 329251876Speter 330251876Speter ::edge get_any_cfg_edge () const; 331251876Speter cgraph_edge *get_any_callgraph_edge () const; 332251876Speter 333251876Speter char *get_description (bool user_facing) const; 334251876Speter 335251876Speter protected: 336251876Speter superedge (supernode *src, supernode *dest, enum edge_kind kind) 337251876Speter : dedge<supergraph_traits> (src, dest), 338251876Speter m_kind (kind) 339251876Speter {} 340251876Speter 341251876Speter public: 342251876Speter const enum edge_kind m_kind; 343251876Speter}; 344251876Speter 345251876Speter/* An ID representing an expression at a callsite: 346251876Speter either a parameter index, or the return value (or unknown). */ 347251876Speter 348251876Speterclass callsite_expr 349251876Speter{ 350251876Speter public: 351251876Speter callsite_expr () : m_val (-1) {} 352251876Speter 353251876Speter static callsite_expr from_zero_based_param (int idx) 354251876Speter { 355251876Speter return callsite_expr (idx + 1); 356251876Speter } 357251876Speter 358251876Speter static callsite_expr from_return_value () 359251876Speter { 360251876Speter return callsite_expr (0); 361251876Speter } 362251876Speter 363251876Speter bool param_p () const 364251876Speter { 365251876Speter return m_val > 0; 366251876Speter } 367251876Speter 368251876Speter bool return_value_p () const 369251876Speter { 370251876Speter return m_val == 0; 371251876Speter } 372251876Speter 373251876Speter private: 374251876Speter callsite_expr (int val) : m_val (val) {} 375251876Speter 376251876Speter int m_val; /* 1-based parm, 0 for return value, or -1 for "unknown". */ 377251876Speter}; 378251876Speter 379251876Speter/* A subclass of superedge with an associated callgraph edge (either a 380251876Speter call or a return). */ 381251876Speter 382251876Speterclass callgraph_superedge : public superedge 383251876Speter{ 384251876Speter public: 385251876Speter callgraph_superedge (supernode *src, supernode *dst, enum edge_kind kind, 386251876Speter cgraph_edge *cedge) 387251876Speter : superedge (src, dst, kind), 388251876Speter m_cedge (cedge) 389251876Speter {} 390251876Speter 391251876Speter void dump_label_to_pp (pretty_printer *pp, bool user_facing) const 392251876Speter FINAL OVERRIDE; 393251876Speter 394251876Speter callgraph_superedge *dyn_cast_callgraph_superedge () FINAL OVERRIDE 395251876Speter { 396251876Speter return this; 397251876Speter } 398251876Speter const callgraph_superedge *dyn_cast_callgraph_superedge () const 399251876Speter FINAL OVERRIDE 400251876Speter { 401251876Speter return this; 402251876Speter } 403251876Speter 404251876Speter function *get_callee_function () const; 405 function *get_caller_function () const; 406 tree get_callee_decl () const; 407 tree get_caller_decl () const; 408 gcall *get_call_stmt () const; 409 tree get_arg_for_parm (tree parm, callsite_expr *out) const; 410 tree get_parm_for_arg (tree arg, callsite_expr *out) const; 411 tree map_expr_from_caller_to_callee (tree caller_expr, 412 callsite_expr *out) const; 413 tree map_expr_from_callee_to_caller (tree callee_expr, 414 callsite_expr *out) const; 415 416 cgraph_edge *const m_cedge; 417}; 418 419} // namespace ana 420 421template <> 422template <> 423inline bool 424is_a_helper <const callgraph_superedge *>::test (const superedge *sedge) 425{ 426 return (sedge->get_kind () == SUPEREDGE_INTRAPROCEDURAL_CALL 427 || sedge->get_kind () == SUPEREDGE_CALL 428 || sedge->get_kind () == SUPEREDGE_RETURN); 429} 430 431namespace ana { 432 433/* A subclass of superedge representing an interprocedural call. */ 434 435class call_superedge : public callgraph_superedge 436{ 437 public: 438 call_superedge (supernode *src, supernode *dst, cgraph_edge *cedge) 439 : callgraph_superedge (src, dst, SUPEREDGE_CALL, cedge) 440 {} 441 442 call_superedge *dyn_cast_call_superedge () FINAL OVERRIDE 443 { 444 return this; 445 } 446 const call_superedge *dyn_cast_call_superedge () const FINAL OVERRIDE 447 { 448 return this; 449 } 450 451 return_superedge *get_edge_for_return (const supergraph &sg) const 452 { 453 return sg.get_edge_for_return (m_cedge); 454 } 455}; 456 457} // namespace ana 458 459template <> 460template <> 461inline bool 462is_a_helper <const call_superedge *>::test (const superedge *sedge) 463{ 464 return sedge->get_kind () == SUPEREDGE_CALL; 465} 466 467namespace ana { 468 469/* A subclass of superedge represesnting an interprocedural return. */ 470 471class return_superedge : public callgraph_superedge 472{ 473 public: 474 return_superedge (supernode *src, supernode *dst, cgraph_edge *cedge) 475 : callgraph_superedge (src, dst, SUPEREDGE_RETURN, cedge) 476 {} 477 478 return_superedge *dyn_cast_return_superedge () FINAL OVERRIDE { return this; } 479 const return_superedge *dyn_cast_return_superedge () const FINAL OVERRIDE 480 { 481 return this; 482 } 483 484 call_superedge *get_edge_for_call (const supergraph &sg) const 485 { 486 return sg.get_edge_for_call (m_cedge); 487 } 488}; 489 490} // namespace ana 491 492template <> 493template <> 494inline bool 495is_a_helper <const return_superedge *>::test (const superedge *sedge) 496{ 497 return sedge->get_kind () == SUPEREDGE_RETURN; 498} 499 500namespace ana { 501 502/* A subclass of superedge that corresponds to a CFG edge. */ 503 504class cfg_superedge : public superedge 505{ 506 public: 507 cfg_superedge (supernode *src, supernode *dst, ::edge e) 508 : superedge (src, dst, SUPEREDGE_CFG_EDGE), 509 m_cfg_edge (e) 510 {} 511 512 void dump_label_to_pp (pretty_printer *pp, bool user_facing) const OVERRIDE; 513 cfg_superedge *dyn_cast_cfg_superedge () FINAL OVERRIDE { return this; } 514 const cfg_superedge *dyn_cast_cfg_superedge () const FINAL OVERRIDE { return this; } 515 516 ::edge get_cfg_edge () const { return m_cfg_edge; } 517 int get_flags () const { return m_cfg_edge->flags; } 518 int true_value_p () const { return get_flags () & EDGE_TRUE_VALUE; } 519 int false_value_p () const { return get_flags () & EDGE_FALSE_VALUE; } 520 int back_edge_p () const { return get_flags () & EDGE_DFS_BACK; } 521 522 size_t get_phi_arg_idx () const; 523 tree get_phi_arg (const gphi *phi) const; 524 525 private: 526 const ::edge m_cfg_edge; 527}; 528 529} // namespace ana 530 531template <> 532template <> 533inline bool 534is_a_helper <const cfg_superedge *>::test (const superedge *sedge) 535{ 536 return sedge->get_kind () == SUPEREDGE_CFG_EDGE; 537} 538 539namespace ana { 540 541/* A subclass for edges from switch statements, retaining enough 542 information to identify the pertinent cases, and for adding labels 543 when rendering via graphviz. */ 544 545class switch_cfg_superedge : public cfg_superedge { 546 public: 547 switch_cfg_superedge (supernode *src, supernode *dst, ::edge e); 548 549 const switch_cfg_superedge *dyn_cast_switch_cfg_superedge () const 550 FINAL OVERRIDE 551 { 552 return this; 553 } 554 555 void dump_label_to_pp (pretty_printer *pp, bool user_facing) const 556 FINAL OVERRIDE; 557 558 gswitch *get_switch_stmt () const 559 { 560 return as_a <gswitch *> (m_src->get_last_stmt ()); 561 } 562 563 const vec<tree> &get_case_labels () const { return m_case_labels; } 564 565private: 566 auto_vec<tree> m_case_labels; 567}; 568 569} // namespace ana 570 571template <> 572template <> 573inline bool 574is_a_helper <const switch_cfg_superedge *>::test (const superedge *sedge) 575{ 576 return sedge->dyn_cast_switch_cfg_superedge () != NULL; 577} 578 579namespace ana { 580 581/* Base class for adding additional content to the .dot output 582 for a supergraph. */ 583 584class dot_annotator 585{ 586 public: 587 virtual ~dot_annotator () {} 588 virtual bool add_node_annotations (graphviz_out *gv ATTRIBUTE_UNUSED, 589 const supernode &n ATTRIBUTE_UNUSED, 590 bool within_table ATTRIBUTE_UNUSED) 591 const 592 { 593 return false; 594 } 595 virtual void add_stmt_annotations (graphviz_out *gv ATTRIBUTE_UNUSED, 596 const gimple *stmt ATTRIBUTE_UNUSED, 597 bool within_row ATTRIBUTE_UNUSED) 598 const {} 599 virtual bool add_after_node_annotations (graphviz_out *gv ATTRIBUTE_UNUSED, 600 const supernode &n ATTRIBUTE_UNUSED) 601 const 602 { 603 return false; 604 } 605}; 606 607extern cgraph_edge *supergraph_call_edge (function *fun, gimple *stmt); 608 609} // namespace ana 610 611#endif /* GCC_ANALYZER_SUPERGRAPH_H */ 612