LCOV - code coverage report
Current view: top level - gcc/analyzer - supergraph.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 80.2 % 621 498
Test Date: 2024-11-30 13:30:02 Functions: 84.8 % 46 39
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* "Supergraph" classes that combine CFGs and callgraph into one digraph.
       2                 :             :    Copyright (C) 2019-2024 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                 :             : #include "config.h"
      22                 :             : #include "system.h"
      23                 :             : #include "coretypes.h"
      24                 :             : #include "tree.h"
      25                 :             : #include "tm.h"
      26                 :             : #include "toplev.h"
      27                 :             : #include "hash-table.h"
      28                 :             : #include "vec.h"
      29                 :             : #include "ggc.h"
      30                 :             : #include "basic-block.h"
      31                 :             : #include "function.h"
      32                 :             : #include "gimple.h"
      33                 :             : #include "gimple-iterator.h"
      34                 :             : #include "gimple-fold.h"
      35                 :             : #include "tree-eh.h"
      36                 :             : #include "gimple-expr.h"
      37                 :             : #include "is-a.h"
      38                 :             : #include "timevar.h"
      39                 :             : #include "gimple-pretty-print.h"
      40                 :             : #include "tree-pretty-print.h"
      41                 :             : #include "graphviz.h"
      42                 :             : #include "cgraph.h"
      43                 :             : #include "tree-dfa.h"
      44                 :             : #include "bitmap.h"
      45                 :             : #include "cfganal.h"
      46                 :             : #include "function.h"
      47                 :             : #include "analyzer/analyzer.h"
      48                 :             : #include "ordered-hash-map.h"
      49                 :             : #include "options.h"
      50                 :             : #include "cgraph.h"
      51                 :             : #include "cfg.h"
      52                 :             : #include "digraph.h"
      53                 :             : #include "tree-cfg.h"
      54                 :             : #include "analyzer/supergraph.h"
      55                 :             : #include "analyzer/analyzer-logging.h"
      56                 :             : #include "make-unique.h"
      57                 :             : 
      58                 :             : #if ENABLE_ANALYZER
      59                 :             : 
      60                 :             : namespace ana {
      61                 :             : 
      62                 :             : /* Get the function of the ultimate alias target being called at EDGE,
      63                 :             :    if any.  */
      64                 :             : 
      65                 :             : function *
      66                 :      115395 : get_ultimate_function_for_cgraph_edge (cgraph_edge *edge)
      67                 :             : {
      68                 :      115395 :   cgraph_node *ultimate_node = edge->callee->ultimate_alias_target ();
      69                 :      115395 :   if (!ultimate_node)
      70                 :             :     return NULL;
      71                 :      115395 :   return ultimate_node->get_fun ();
      72                 :             : }
      73                 :             : 
      74                 :             : /* Get the cgraph_edge, but only if there's an underlying function body.  */
      75                 :             : 
      76                 :             : cgraph_edge *
      77                 :      365421 : supergraph_call_edge (function *fun, const gimple *stmt)
      78                 :             : {
      79                 :      451314 :   const gcall *call = dyn_cast<const gcall *> (stmt);
      80                 :      101009 :   if (!call)
      81                 :             :     return NULL;
      82                 :      101009 :   cgraph_edge *edge
      83                 :      101009 :     = cgraph_node::get (fun->decl)->get_edge (const_cast <gimple *> (stmt));
      84                 :      101009 :   if (!edge)
      85                 :             :     return NULL;
      86                 :       98707 :   if (!edge->callee)
      87                 :             :     return NULL; /* e.g. for a function pointer.  */
      88                 :       97330 :   if (!get_ultimate_function_for_cgraph_edge (edge))
      89                 :             :     return NULL;
      90                 :             :   return edge;
      91                 :             : }
      92                 :             : 
      93                 :             : /* class saved_uids.
      94                 :             : 
      95                 :             :    In order to ensure consistent results without relying on the ordering
      96                 :             :    of pointer values we assign a uid to each gimple stmt, globally unique
      97                 :             :    across all functions.
      98                 :             : 
      99                 :             :    Normally, the stmt uids are a scratch space that each pass can freely
     100                 :             :    assign its own values to.  However, in the case of LTO, the uids are
     101                 :             :    used to associate call stmts with callgraph edges between the WPA phase
     102                 :             :    (where the analyzer runs in LTO mode) and the LTRANS phase; if the
     103                 :             :    analyzer changes them in the WPA phase, it leads to errors when
     104                 :             :    streaming the code back in at LTRANS.
     105                 :             :    lto_prepare_function_for_streaming has code to renumber the stmt UIDs
     106                 :             :    when the code is streamed back out, but for some reason this isn't
     107                 :             :    called for clones.
     108                 :             : 
     109                 :             :    Hence, as a workaround, this class has responsibility for tracking
     110                 :             :    the original uids and restoring them once the pass is complete
     111                 :             :    (in the supergraph dtor).  */
     112                 :             : 
     113                 :             : /* Give STMT a globally unique uid, storing its original uid so it can
     114                 :             :    later be restored.  */
     115                 :             : 
     116                 :             : void
     117                 :      129254 : saved_uids::make_uid_unique (gimple *stmt)
     118                 :             : {
     119                 :      129254 :   unsigned next_uid = m_old_stmt_uids.length ();
     120                 :      129254 :   unsigned old_stmt_uid = stmt->uid;
     121                 :      129254 :   stmt->uid = next_uid;
     122                 :      129254 :   m_old_stmt_uids.safe_push
     123                 :      129254 :     (std::pair<gimple *, unsigned> (stmt, old_stmt_uid));
     124                 :      129254 : }
     125                 :             : 
     126                 :             : /* Restore the saved uids of all stmts.  */
     127                 :             : 
     128                 :             : void
     129                 :        3197 : saved_uids::restore_uids () const
     130                 :             : {
     131                 :        3197 :   unsigned i;
     132                 :        3197 :   std::pair<gimple *, unsigned> *pair;
     133                 :      132451 :   FOR_EACH_VEC_ELT (m_old_stmt_uids, i, pair)
     134                 :      129254 :     pair->first->uid = pair->second;
     135                 :        3197 : }
     136                 :             : 
     137                 :             : /* supergraph's ctor.  Walk the callgraph, building supernodes for each
     138                 :             :    CFG basic block, splitting the basic blocks at callsites.  Join
     139                 :             :    together the supernodes with interprocedural and intraprocedural
     140                 :             :    superedges as appropriate.
     141                 :             :    Assign UIDs to the gimple stmts.  */
     142                 :             : 
     143                 :        3197 : supergraph::supergraph (logger *logger)
     144                 :             : {
     145                 :        3197 :   auto_timevar tv (TV_ANALYZER_SUPERGRAPH);
     146                 :             : 
     147                 :        3197 :   LOG_FUNC (logger);
     148                 :             : 
     149                 :             :   /* First pass: make supernodes (and assign UIDs to the gimple stmts).  */
     150                 :        3197 :   {
     151                 :             :     /* Sort the cgraph_nodes?  */
     152                 :        3197 :     cgraph_node *node;
     153                 :       12934 :     FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
     154                 :             :     {
     155                 :        9737 :       function *fun = node->get_fun ();
     156                 :             : 
     157                 :             :       /* Ensure that EDGE_DFS_BACK is correct for every CFG edge in
     158                 :             :          the supergraph (by doing it per-function).  */
     159                 :        9737 :       auto_cfun sentinel (fun);
     160                 :        9737 :       mark_dfs_back_edges ();
     161                 :             : 
     162                 :        9737 :       const int start_idx = m_nodes.length ();
     163                 :             : 
     164                 :        9737 :       basic_block bb;
     165                 :       65203 :       FOR_ALL_BB_FN (bb, fun)
     166                 :             :         {
     167                 :             :           /* The initial supernode for the BB gets the phi nodes (if any).  */
     168                 :       55466 :           supernode *node_for_stmts = add_node (fun, bb, NULL, phi_nodes (bb));
     169                 :       55466 :           m_bb_to_initial_node.put (bb, node_for_stmts);
     170                 :       64522 :           for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);
     171                 :        9056 :                gsi_next (&gpi))
     172                 :             :             {
     173                 :        9056 :               gimple *stmt = gsi_stmt (gpi);
     174                 :        9056 :               m_stmt_to_node_t.put (stmt, node_for_stmts);
     175                 :        9056 :               m_stmt_uids.make_uid_unique (stmt);
     176                 :             :             }
     177                 :             : 
     178                 :             :           /* Append statements from BB to the current supernode, splitting
     179                 :             :              them into a new supernode at each call site; such call statements
     180                 :             :              appear in both supernodes (representing call and return).  */
     181                 :       55466 :           gimple_stmt_iterator gsi;
     182                 :      232958 :           for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     183                 :             :             {
     184                 :      122026 :               gimple *stmt = gsi_stmt (gsi);
     185                 :             :               /* Discard debug stmts here, so we don't have to check for
     186                 :             :                  them anywhere within the analyzer.  */
     187                 :      122026 :               if (is_gimple_debug (stmt))
     188                 :        1828 :                 continue;
     189                 :      120198 :               node_for_stmts->m_stmts.safe_push (stmt);
     190                 :      120198 :               m_stmt_to_node_t.put (stmt, node_for_stmts);
     191                 :      120198 :               m_stmt_uids.make_uid_unique (stmt);
     192                 :      120198 :               if (cgraph_edge *edge = supergraph_call_edge (fun, stmt))
     193                 :             :                 {
     194                 :        3331 :                   m_cgraph_edge_to_caller_prev_node.put(edge, node_for_stmts);
     195                 :        3331 :                   node_for_stmts = add_node (fun, bb, as_a <gcall *> (stmt),
     196                 :             :                                              NULL);
     197                 :        3331 :                   m_cgraph_edge_to_caller_next_node.put (edge, node_for_stmts);
     198                 :             :                 }
     199                 :             :                else
     200                 :             :                 {
     201                 :             :                   // maybe call is via a function pointer
     202                 :      155173 :                   if (gcall *call = dyn_cast<gcall *> (stmt))
     203                 :             :                   {
     204                 :       34975 :                     cgraph_edge *edge
     205                 :       34975 :                       = cgraph_node::get (fun->decl)->get_edge (stmt);
     206                 :       34975 :                     if (!edge || !edge->callee)
     207                 :             :                     {
     208                 :         739 :                       supernode *old_node_for_stmts = node_for_stmts;
     209                 :         739 :                       node_for_stmts = add_node (fun, bb, call, NULL);
     210                 :             : 
     211                 :         739 :                       superedge *sedge
     212                 :             :                         = new callgraph_superedge (old_node_for_stmts,
     213                 :             :                                                    node_for_stmts,
     214                 :             :                                                    SUPEREDGE_INTRAPROCEDURAL_CALL,
     215                 :         739 :                                                    NULL);
     216                 :         739 :                       add_edge (sedge);
     217                 :             :                     }
     218                 :             :                   }
     219                 :             :                 }
     220                 :             :             }
     221                 :             : 
     222                 :       55466 :           m_bb_to_final_node.put (bb, node_for_stmts);
     223                 :             :         }
     224                 :             : 
     225                 :        9737 :       const unsigned num_snodes = m_nodes.length () - start_idx;
     226                 :        9737 :       m_function_to_num_snodes.put (fun, num_snodes);
     227                 :             : 
     228                 :        9737 :       if (logger)
     229                 :             :         {
     230                 :           2 :           const int end_idx = m_nodes.length () - 1;
     231                 :           2 :           logger->log ("SN: %i...%i: function %qD",
     232                 :             :                        start_idx, end_idx, fun->decl);
     233                 :             :         }
     234                 :             :     }
     235                 :             :   }
     236                 :             : 
     237                 :             :   /* Second pass: make superedges.  */
     238                 :        3197 :   {
     239                 :             :     /* Make superedges for CFG edges.  */
     240                 :        3197 :     for (bb_to_node_t::iterator iter = m_bb_to_final_node.begin ();
     241                 :      117322 :          iter != m_bb_to_final_node.end ();
     242                 :       55466 :          ++iter)
     243                 :             :       {
     244                 :       55466 :         basic_block bb = (*iter).first;
     245                 :       55466 :         supernode *src_supernode = (*iter).second;
     246                 :             : 
     247                 :       55466 :         ::edge cfg_edge;
     248                 :       55466 :         int idx;
     249                 :       55466 :         if (bb->succs)
     250                 :      112150 :           FOR_EACH_VEC_ELT (*bb->succs, idx, cfg_edge)
     251                 :             :             {
     252                 :       56684 :               basic_block dest_cfg_block = cfg_edge->dest;
     253                 :       56684 :               supernode *dest_supernode
     254                 :       56684 :                 = *m_bb_to_initial_node.get (dest_cfg_block);
     255                 :       56684 :               cfg_superedge *cfg_sedge
     256                 :       56684 :                 = add_cfg_edge (src_supernode, dest_supernode, cfg_edge);
     257                 :       56684 :               m_cfg_edge_to_cfg_superedge.put (cfg_edge, cfg_sedge);
     258                 :             :             }
     259                 :             :       }
     260                 :             : 
     261                 :             :     /* Make interprocedural superedges for calls.  */
     262                 :        3197 :     {
     263                 :        3197 :       for (cgraph_edge_to_node_t::iterator iter
     264                 :        3197 :              = m_cgraph_edge_to_caller_prev_node.begin ();
     265                 :       10791 :            iter != m_cgraph_edge_to_caller_prev_node.end ();
     266                 :        3331 :            ++iter)
     267                 :             :         {
     268                 :        3331 :           cgraph_edge *edge = (*iter).first;
     269                 :        3331 :           supernode *caller_prev_supernode = (*iter).second;
     270                 :        3331 :           function* callee_fn = get_ultimate_function_for_cgraph_edge (edge);
     271                 :        3331 :           if (!callee_fn || !callee_fn->cfg)
     272                 :           0 :             continue;
     273                 :        3331 :           basic_block callee_cfg_block = ENTRY_BLOCK_PTR_FOR_FN (callee_fn);
     274                 :        3331 :           supernode *callee_supernode
     275                 :        3331 :             = *m_bb_to_initial_node.get (callee_cfg_block);
     276                 :        3331 :           call_superedge *sedge
     277                 :        3331 :             = add_call_superedge (caller_prev_supernode,
     278                 :             :                                   callee_supernode,
     279                 :        3331 :                                   edge);
     280                 :        3331 :           m_cgraph_edge_to_call_superedge.put (edge, sedge);
     281                 :             :         }
     282                 :             :     }
     283                 :             : 
     284                 :             :     /* Make interprocedural superedges for returns.  */
     285                 :        3197 :     {
     286                 :        3197 :       for (cgraph_edge_to_node_t::iterator iter
     287                 :        3197 :              = m_cgraph_edge_to_caller_next_node.begin ();
     288                 :       10791 :            iter != m_cgraph_edge_to_caller_next_node.end ();
     289                 :        3331 :            ++iter)
     290                 :             :         {
     291                 :        3331 :           cgraph_edge *edge = (*iter).first;
     292                 :        3331 :           supernode *caller_next_supernode = (*iter).second;
     293                 :        3331 :           function* callee_fn = get_ultimate_function_for_cgraph_edge (edge);
     294                 :        3331 :           if (!callee_fn || !callee_fn->cfg)
     295                 :           0 :             continue;
     296                 :        3331 :           basic_block callee_cfg_block = EXIT_BLOCK_PTR_FOR_FN (callee_fn);
     297                 :        3331 :           supernode *callee_supernode
     298                 :        3331 :             = *m_bb_to_initial_node.get (callee_cfg_block);
     299                 :        3331 :           return_superedge *sedge
     300                 :        3331 :             = add_return_superedge (callee_supernode,
     301                 :             :                                     caller_next_supernode,
     302                 :        3331 :                                     edge);
     303                 :        3331 :           m_cgraph_edge_to_return_superedge.put (edge, sedge);
     304                 :             :         }
     305                 :             :     }
     306                 :             : 
     307                 :             :     /* Make intraprocedural superedges linking the two halves of a call.  */
     308                 :        3197 :     {
     309                 :        3197 :       for (cgraph_edge_to_node_t::iterator iter
     310                 :        3197 :              = m_cgraph_edge_to_caller_prev_node.begin ();
     311                 :       10791 :            iter != m_cgraph_edge_to_caller_prev_node.end ();
     312                 :        3331 :            ++iter)
     313                 :             :         {
     314                 :        3331 :           cgraph_edge *edge = (*iter).first;
     315                 :        3331 :           supernode *caller_prev_supernode = (*iter).second;
     316                 :        3331 :           supernode *caller_next_supernode
     317                 :        3331 :             = *m_cgraph_edge_to_caller_next_node.get (edge);
     318                 :        3331 :           superedge *sedge
     319                 :             :             = new callgraph_superedge (caller_prev_supernode,
     320                 :             :                                        caller_next_supernode,
     321                 :             :                                        SUPEREDGE_INTRAPROCEDURAL_CALL,
     322                 :        3331 :                                        edge);
     323                 :        3331 :           add_edge (sedge);
     324                 :        3331 :           m_cgraph_edge_to_intraproc_superedge.put (edge, sedge);
     325                 :             :         }
     326                 :             : 
     327                 :             :     }
     328                 :             :   }
     329                 :        3197 : }
     330                 :             : 
     331                 :             : /* supergraph's dtor.  Reset stmt uids.  */
     332                 :             : 
     333                 :        3197 : supergraph::~supergraph ()
     334                 :             : {
     335                 :        3197 :   m_stmt_uids.restore_uids ();
     336                 :        3197 : }
     337                 :             : 
     338                 :             : /* Dump this graph in .dot format to PP, using DUMP_ARGS.
     339                 :             :    Cluster the supernodes by function, then by BB from original CFG.  */
     340                 :             : 
     341                 :             : void
     342                 :          12 : supergraph::dump_dot_to_pp (pretty_printer *pp,
     343                 :             :                             const dump_args_t &dump_args) const
     344                 :             : {
     345                 :          12 :   graphviz_out gv (pp);
     346                 :             : 
     347                 :          12 :   pp_string (pp, "digraph \"");
     348                 :          12 :   pp_write_text_to_stream (pp);
     349                 :          12 :   pp_string (pp, "supergraph");
     350                 :          12 :   pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
     351                 :          12 :   pp_string (pp, "\" {\n");
     352                 :          12 :   gv.indent ();
     353                 :             : 
     354                 :          12 :   gv.println ("overlap=false;");
     355                 :          12 :   gv.println ("compound=true;");
     356                 :             : 
     357                 :             :   /* TODO: maybe (optionally) sub-subdivide by TU, for LTO; see also:
     358                 :             :      https://gcc-python-plugin.readthedocs.io/en/latest/_images/sample-supergraph.png
     359                 :             :   */
     360                 :             : 
     361                 :             :   /* Break out the supernodes into clusters by function.  */
     362                 :          12 :   {
     363                 :          12 :     cgraph_node *node;
     364                 :          48 :     FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
     365                 :             :     {
     366                 :          36 :       function *fun = node->get_fun ();
     367                 :          36 :       gcc_assert (fun);
     368                 :          36 :       const char *funcname = function_name (fun);
     369                 :          36 :       gv.println ("subgraph \"cluster_%s\" {",
     370                 :             :                   funcname);
     371                 :          36 :       gv.indent ();
     372                 :          36 :       pp_printf (pp,
     373                 :             :                  ("style=\"dashed\";"
     374                 :             :                   " color=\"black\";"
     375                 :             :                   " label=\"%s\";\n"),
     376                 :             :                  funcname);
     377                 :             : 
     378                 :             :       /* Break out the nodes into clusters by BB from original CFG.  */
     379                 :          36 :       {
     380                 :          36 :         basic_block bb;
     381                 :         252 :         FOR_ALL_BB_FN (bb, fun)
     382                 :             :           {
     383                 :         216 :             if (dump_args.m_flags & SUPERGRAPH_DOT_SHOW_BBS)
     384                 :             :               {
     385                 :           0 :                 gv.println ("subgraph \"cluster_%s_bb_%i\" {",
     386                 :             :                             funcname, bb->index);
     387                 :           0 :                 gv.indent ();
     388                 :           0 :                 pp_printf (pp,
     389                 :             :                            ("style=\"dashed\";"
     390                 :             :                             " color=\"black\";"
     391                 :             :                             " label=\"bb: %i\";\n"),
     392                 :             :                            bb->index);
     393                 :             :               }
     394                 :             : 
     395                 :             :             // TODO: maybe keep an index per-function/per-bb to speed this up???
     396                 :             :             int i;
     397                 :             :             supernode *n;
     398                 :        4320 :             FOR_EACH_VEC_ELT (m_nodes, i, n)
     399                 :        4104 :               if (n->m_fun == fun && n->m_bb == bb)
     400                 :         228 :                 n->dump_dot (&gv, dump_args);
     401                 :             : 
     402                 :         216 :             if (dump_args.m_flags & SUPERGRAPH_DOT_SHOW_BBS)
     403                 :             :               {
     404                 :             :                 /* Terminate per-bb "subgraph" */
     405                 :           0 :                 gv.outdent ();
     406                 :           0 :                 gv.println ("}");
     407                 :             :               }
     408                 :             :           }
     409                 :             :       }
     410                 :             : 
     411                 :             :       /* Add an invisible edge from ENTRY to EXIT, to improve the graph layout.  */
     412                 :          36 :       pp_string (pp, "\t");
     413                 :          36 :       get_node_for_function_entry (*fun)->dump_dot_id (pp);
     414                 :          36 :       pp_string (pp, ":s -> ");
     415                 :          36 :       get_node_for_function_exit (*fun)->dump_dot_id (pp);
     416                 :          36 :       pp_string (pp, ":n [style=\"invis\",constraint=true];\n");
     417                 :             : 
     418                 :             :       /* Terminate per-function "subgraph" */
     419                 :          36 :       gv.outdent ();
     420                 :          36 :       gv.println ("}");
     421                 :             :     }
     422                 :             :   }
     423                 :             : 
     424                 :             :   /* Superedges.  */
     425                 :             :   int i;
     426                 :             :   superedge *e;
     427                 :         264 :   FOR_EACH_VEC_ELT (m_edges, i, e)
     428                 :         252 :     e->dump_dot (&gv, dump_args);
     429                 :             : 
     430                 :             :   /* Terminate "digraph" */
     431                 :          12 :   gv.outdent ();
     432                 :          12 :   gv.println ("}");
     433                 :          12 : }
     434                 :             : 
     435                 :             : /* Dump this graph in .dot format to FP, using DUMP_ARGS.  */
     436                 :             : 
     437                 :             : void
     438                 :          12 : supergraph::dump_dot_to_file (FILE *fp, const dump_args_t &dump_args) const
     439                 :             : {
     440                 :          12 :   std::unique_ptr<pretty_printer> pp (global_dc->clone_printer ());
     441                 :          12 :   pp_show_color (pp.get ()) = 0;
     442                 :             :   /* %qE in logs for SSA_NAMEs should show the ssa names, rather than
     443                 :             :      trying to prettify things by showing the underlying var.  */
     444                 :          12 :   pp_format_decoder (pp.get ()) = default_tree_printer;
     445                 :             : 
     446                 :          12 :   pp->set_output_stream (fp);
     447                 :          12 :   dump_dot_to_pp (pp.get (), dump_args);
     448                 :          12 :   pp_flush (pp.get ());
     449                 :          12 : }
     450                 :             : 
     451                 :             : /* Dump this graph in .dot format to PATH, using DUMP_ARGS.  */
     452                 :             : 
     453                 :             : void
     454                 :          12 : supergraph::dump_dot (const char *path, const dump_args_t &dump_args) const
     455                 :             : {
     456                 :          12 :   FILE *fp = fopen (path, "w");
     457                 :          12 :   dump_dot_to_file (fp, dump_args);
     458                 :          12 :   fclose (fp);
     459                 :          12 : }
     460                 :             : 
     461                 :             : /* Return a new json::object of the form
     462                 :             :    {"nodes" : [objs for snodes],
     463                 :             :     "edges" : [objs for sedges]}.  */
     464                 :             : 
     465                 :             : std::unique_ptr<json::object>
     466                 :           0 : supergraph::to_json () const
     467                 :             : {
     468                 :           0 :   auto sgraph_obj = ::make_unique<json::object> ();
     469                 :             : 
     470                 :             :   /* Nodes.  */
     471                 :           0 :   {
     472                 :           0 :     auto nodes_arr = ::make_unique<json::array> ();
     473                 :           0 :     unsigned i;
     474                 :           0 :     supernode *n;
     475                 :           0 :     FOR_EACH_VEC_ELT (m_nodes, i, n)
     476                 :           0 :       nodes_arr->append (n->to_json ());
     477                 :           0 :     sgraph_obj->set ("nodes", std::move (nodes_arr));
     478                 :           0 :   }
     479                 :             : 
     480                 :             :   /* Edges.  */
     481                 :           0 :   {
     482                 :           0 :     auto edges_arr = ::make_unique<json::array> ();
     483                 :           0 :     unsigned i;
     484                 :           0 :     superedge *n;
     485                 :           0 :     FOR_EACH_VEC_ELT (m_edges, i, n)
     486                 :           0 :       edges_arr->append (n->to_json ());
     487                 :           0 :     sgraph_obj->set ("edges", std::move (edges_arr));
     488                 :           0 :   }
     489                 :             : 
     490                 :           0 :   return sgraph_obj;
     491                 :             : }
     492                 :             : 
     493                 :             : /* Create a supernode for BB within FUN and add it to this supergraph.
     494                 :             : 
     495                 :             :    If RETURNING_CALL is non-NULL, the supernode represents the resumption
     496                 :             :    of the basic block after returning from that call.
     497                 :             : 
     498                 :             :    If PHI_NODES is non-NULL, this is the initial supernode for the basic
     499                 :             :    block, and is responsible for any handling of the phi nodes.  */
     500                 :             : 
     501                 :             : supernode *
     502                 :       59536 : supergraph::add_node (function *fun, basic_block bb, gcall *returning_call,
     503                 :             :                       gimple_seq phi_nodes)
     504                 :             : {
     505                 :       59536 :   supernode *n = new supernode (fun, bb, returning_call, phi_nodes,
     506                 :      115879 :                                 m_nodes.length ());
     507                 :       59536 :   m_nodes.safe_push (n);
     508                 :       59536 :   return n;
     509                 :             : }
     510                 :             : 
     511                 :             : /* Create a new cfg_superedge from SRC to DEST for the underlying CFG edge E,
     512                 :             :    adding it to this supergraph.
     513                 :             : 
     514                 :             :    If the edge is for a switch statement, create a switch_cfg_superedge
     515                 :             :    subclass.  */
     516                 :             : 
     517                 :             : cfg_superedge *
     518                 :       56684 : supergraph::add_cfg_edge (supernode *src, supernode *dest, ::edge e)
     519                 :             : {
     520                 :             :   /* Special-case switch edges.  */
     521                 :       56684 :   gimple *stmt = src->get_last_stmt ();
     522                 :       56684 :   cfg_superedge *new_edge;
     523                 :       56684 :   if (stmt && stmt->code == GIMPLE_SWITCH)
     524                 :        3005 :     new_edge = new switch_cfg_superedge (src, dest, e);
     525                 :             :   else
     526                 :       53679 :     new_edge = new cfg_superedge (src, dest, e);
     527                 :       56684 :   add_edge (new_edge);
     528                 :       56684 :   return new_edge;
     529                 :             : }
     530                 :             : 
     531                 :             : /* Create and add a call_superedge representing an interprocedural call
     532                 :             :    from SRC to DEST, using CEDGE.  */
     533                 :             : 
     534                 :             : call_superedge *
     535                 :        3331 : supergraph::add_call_superedge (supernode *src, supernode *dest,
     536                 :             :                                 cgraph_edge *cedge)
     537                 :             : {
     538                 :        3331 :   call_superedge *new_edge = new call_superedge (src, dest, cedge);
     539                 :        3331 :   add_edge (new_edge);
     540                 :        3331 :   return new_edge;
     541                 :             : }
     542                 :             : 
     543                 :             : /* Create and add a return_superedge representing returning from an
     544                 :             :    interprocedural call, returning from SRC to DEST, using CEDGE.  */
     545                 :             : 
     546                 :             : return_superedge *
     547                 :        3331 : supergraph::add_return_superedge (supernode *src, supernode *dest,
     548                 :             :                                   cgraph_edge *cedge)
     549                 :             : {
     550                 :        3331 :   return_superedge *new_edge = new return_superedge (src, dest, cedge);
     551                 :        3331 :   add_edge (new_edge);
     552                 :        3331 :   return new_edge;
     553                 :             : }
     554                 :             : 
     555                 :             : /* Implementation of dnode::dump_dot vfunc for supernodes.
     556                 :             : 
     557                 :             :    Write a cluster for the node, and within it a .dot node showing
     558                 :             :    the phi nodes and stmts.  Call into any node annotator from ARGS to
     559                 :             :    potentially add other records to the cluster.  */
     560                 :             : 
     561                 :             : void
     562                 :         228 : supernode::dump_dot (graphviz_out *gv, const dump_args_t &args) const
     563                 :             : {
     564                 :         228 :   gv->println ("subgraph cluster_node_%i {",
     565                 :         228 :                m_index);
     566                 :         228 :   gv->indent ();
     567                 :             : 
     568                 :         228 :   gv->println("style=\"solid\";");
     569                 :         228 :   gv->println("color=\"black\";");
     570                 :         228 :   gv->println("fillcolor=\"lightgrey\";");
     571                 :         228 :   gv->println("label=\"sn: %i (bb: %i)\";", m_index, m_bb->index);
     572                 :             : 
     573                 :         228 :   pretty_printer *pp = gv->get_pp ();
     574                 :             : 
     575                 :         228 :   if (args.m_node_annotator)
     576                 :         152 :     args.m_node_annotator->add_node_annotations (gv, *this, false);
     577                 :             : 
     578                 :         228 :   gv->write_indent ();
     579                 :         228 :   dump_dot_id (pp);
     580                 :         228 :   pp_printf (pp,
     581                 :             :              " [shape=none,margin=0,style=filled,fillcolor=%s,label=<",
     582                 :             :              "lightgrey");
     583                 :         228 :   pp_string (pp, "<TABLE BORDER=\"0\">");
     584                 :         228 :   pp_write_text_to_stream (pp);
     585                 :             : 
     586                 :         228 :   bool had_row = false;
     587                 :             : 
     588                 :             :   /* Give any annotator the chance to add its own per-node TR elements. */
     589                 :         228 :   if (args.m_node_annotator)
     590                 :         152 :     if (args.m_node_annotator->add_node_annotations (gv, *this, true))
     591                 :         228 :       had_row = true;
     592                 :             : 
     593                 :         228 :   if (m_returning_call)
     594                 :             :     {
     595                 :          12 :       gv->begin_trtd ();
     596                 :          12 :       pp_string (pp, "returning call: ");
     597                 :          12 :       gv->end_tdtr ();
     598                 :             : 
     599                 :          12 :       gv->begin_tr ();
     600                 :          12 :       gv->begin_td ();
     601                 :          12 :       pp_gimple_stmt_1 (pp, m_returning_call, 0, (dump_flags_t)0);
     602                 :          12 :       pp_write_text_as_html_like_dot_to_stream (pp);
     603                 :          12 :       gv->end_td ();
     604                 :             :       /* Give any annotator the chance to add per-stmt TD elements to
     605                 :             :          this row.  */
     606                 :          12 :       if (args.m_node_annotator)
     607                 :           8 :         args.m_node_annotator->add_stmt_annotations (gv, m_returning_call,
     608                 :             :                                                      true);
     609                 :          12 :       gv->end_tr ();
     610                 :             : 
     611                 :             :       /* Give any annotator the chance to add per-stmt TR elements.  */
     612                 :          12 :       if (args.m_node_annotator)
     613                 :           8 :         args.m_node_annotator->add_stmt_annotations (gv, m_returning_call,
     614                 :             :                                                      false);
     615                 :          12 :       pp_newline (pp);
     616                 :             : 
     617                 :          12 :       had_row = true;
     618                 :             :     }
     619                 :             : 
     620                 :         228 :   if (entry_p ())
     621                 :             :     {
     622                 :          36 :       pp_string (pp, "<TR><TD>ENTRY</TD></TR>");
     623                 :          36 :       pp_newline (pp);
     624                 :          36 :       had_row = true;
     625                 :             :     }
     626                 :             : 
     627                 :         228 :   if (return_p ())
     628                 :             :     {
     629                 :          36 :       pp_string (pp, "<TR><TD>EXIT</TD></TR>");
     630                 :          36 :       pp_newline (pp);
     631                 :          36 :       had_row = true;
     632                 :             :     }
     633                 :             : 
     634                 :             :   /* Phi nodes.  */
     635                 :         228 :   for (gphi_iterator gpi = const_cast<supernode *> (this)->start_phis ();
     636                 :         264 :        !gsi_end_p (gpi); gsi_next (&gpi))
     637                 :             :     {
     638                 :          36 :       const gimple *stmt = gsi_stmt (gpi);
     639                 :          36 :       gv->begin_tr ();
     640                 :          36 :       gv->begin_td ();
     641                 :          36 :       pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
     642                 :          36 :       pp_write_text_as_html_like_dot_to_stream (pp);
     643                 :          36 :       gv->end_td ();
     644                 :             :       /* Give any annotator the chance to add per-phi TD elements to
     645                 :             :          this row.  */
     646                 :          36 :       if (args.m_node_annotator)
     647                 :          24 :         args.m_node_annotator->add_stmt_annotations (gv, stmt, true);
     648                 :          36 :       gv->end_tr ();
     649                 :             : 
     650                 :             :       /* Give any annotator the chance to add per-phi TR elements.  */
     651                 :          36 :       if (args.m_node_annotator)
     652                 :          24 :         args.m_node_annotator->add_stmt_annotations (gv, stmt, false);
     653                 :             : 
     654                 :          36 :       pp_newline (pp);
     655                 :          36 :       had_row = true;
     656                 :             :     }
     657                 :             : 
     658                 :             :   /* Statements.  */
     659                 :             :   int i;
     660                 :             :   gimple *stmt;
     661                 :         585 :   FOR_EACH_VEC_ELT (m_stmts, i, stmt)
     662                 :             :     {
     663                 :         357 :       gv->begin_tr ();
     664                 :         357 :       gv->begin_td ();
     665                 :         357 :       pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
     666                 :         357 :       pp_write_text_as_html_like_dot_to_stream (pp);
     667                 :         357 :       gv->end_td ();
     668                 :             :       /* Give any annotator the chance to add per-stmt TD elements to
     669                 :             :          this row.  */
     670                 :         357 :       if (args.m_node_annotator)
     671                 :         238 :         args.m_node_annotator->add_stmt_annotations (gv, stmt, true);
     672                 :         357 :       gv->end_tr ();
     673                 :             : 
     674                 :             :       /* Give any annotator the chance to add per-stmt TR elements.  */
     675                 :         357 :       if (args.m_node_annotator)
     676                 :         238 :         args.m_node_annotator->add_stmt_annotations (gv, stmt, false);
     677                 :             : 
     678                 :         357 :       pp_newline (pp);
     679                 :         357 :       had_row = true;
     680                 :             :     }
     681                 :             : 
     682                 :             :   /* Give any annotator the chance to add additional per-node TR elements
     683                 :             :      to the end of the TABLE. */
     684                 :         228 :   if (args.m_node_annotator)
     685                 :         152 :     if (args.m_node_annotator->add_after_node_annotations (gv, *this))
     686                 :             :       had_row = true;
     687                 :             : 
     688                 :             :   /* Graphviz requires a TABLE element to have at least one TR
     689                 :             :      (and each TR to have at least one TD).  */
     690                 :         152 :   if (!had_row)
     691                 :             :     {
     692                 :           8 :       pp_string (pp, "<TR><TD>(empty)</TD></TR>");
     693                 :           8 :       pp_newline (pp);
     694                 :             :     }
     695                 :             : 
     696                 :         228 :   pp_string (pp, "</TABLE>>];\n\n");
     697                 :         228 :   pp_flush (pp);
     698                 :             : 
     699                 :             :   /* Terminate "subgraph" */
     700                 :         228 :   gv->outdent ();
     701                 :         228 :   gv->println ("}");
     702                 :         228 : }
     703                 :             : 
     704                 :             : /* Write an ID for this node to PP, for use in .dot output.  */
     705                 :             : 
     706                 :             : void
     707                 :         804 : supernode::dump_dot_id (pretty_printer *pp) const
     708                 :             : {
     709                 :         804 :   pp_printf (pp, "node_%i", m_index);
     710                 :         804 : }
     711                 :             : 
     712                 :             : /* Return a new json::object of the form
     713                 :             :    {"idx": int,
     714                 :             :     "fun": optional str
     715                 :             :     "bb_idx": int,
     716                 :             :     "returning_call": optional str,
     717                 :             :     "phis": [str],
     718                 :             :     "stmts" : [str]}.  */
     719                 :             : 
     720                 :             : std::unique_ptr<json::object>
     721                 :           0 : supernode::to_json () const
     722                 :             : {
     723                 :           0 :   auto snode_obj = ::make_unique<json::object> ();
     724                 :             : 
     725                 :           0 :   snode_obj->set_integer ("idx", m_index);
     726                 :           0 :   snode_obj->set_integer ("bb_idx", m_bb->index);
     727                 :           0 :   if (function *fun = get_function ())
     728                 :           0 :     snode_obj->set_string ("fun", function_name (fun));
     729                 :             : 
     730                 :           0 :   if (m_returning_call)
     731                 :             :     {
     732                 :           0 :       pretty_printer pp;
     733                 :           0 :       pp_format_decoder (&pp) = default_tree_printer;
     734                 :           0 :       pp_gimple_stmt_1 (&pp, m_returning_call, 0, (dump_flags_t)0);
     735                 :           0 :       snode_obj->set_string ("returning_call", pp_formatted_text (&pp));
     736                 :           0 :     }
     737                 :             : 
     738                 :             :   /* Phi nodes.  */
     739                 :           0 :   {
     740                 :           0 :     auto phi_arr = ::make_unique<json::array> ();
     741                 :           0 :     for (gphi_iterator gpi = const_cast<supernode *> (this)->start_phis ();
     742                 :           0 :          !gsi_end_p (gpi); gsi_next (&gpi))
     743                 :             :       {
     744                 :           0 :         const gimple *stmt = gsi_stmt (gpi);
     745                 :           0 :         pretty_printer pp;
     746                 :           0 :         pp_format_decoder (&pp) = default_tree_printer;
     747                 :           0 :         pp_gimple_stmt_1 (&pp, stmt, 0, (dump_flags_t)0);
     748                 :           0 :         phi_arr->append_string (pp_formatted_text (&pp));
     749                 :           0 :       }
     750                 :           0 :     snode_obj->set ("phis", std::move (phi_arr));
     751                 :           0 :   }
     752                 :             : 
     753                 :             :   /* Statements.  */
     754                 :           0 :   {
     755                 :           0 :     auto stmt_arr = ::make_unique<json::array> ();
     756                 :           0 :     int i;
     757                 :           0 :     gimple *stmt;
     758                 :           0 :     FOR_EACH_VEC_ELT (m_stmts, i, stmt)
     759                 :             :       {
     760                 :           0 :         pretty_printer pp;
     761                 :           0 :         pp_format_decoder (&pp) = default_tree_printer;
     762                 :           0 :         pp_gimple_stmt_1 (&pp, stmt, 0, (dump_flags_t)0);
     763                 :           0 :         stmt_arr->append_string (pp_formatted_text (&pp));
     764                 :           0 :       }
     765                 :           0 :     snode_obj->set ("stmts", std::move (stmt_arr));
     766                 :           0 :   }
     767                 :             : 
     768                 :           0 :   return snode_obj;
     769                 :             : }
     770                 :             : 
     771                 :             : /* Get a location_t for the start of this supernode.  */
     772                 :             : 
     773                 :             : location_t
     774                 :       20981 : supernode::get_start_location () const
     775                 :             : {
     776                 :       20981 :   if (m_returning_call
     777                 :       20981 :       && get_pure_location (m_returning_call->location) != UNKNOWN_LOCATION)
     778                 :           0 :     return m_returning_call->location;
     779                 :             : 
     780                 :             :   int i;
     781                 :             :   gimple *stmt;
     782                 :       22184 :   FOR_EACH_VEC_ELT (m_stmts, i, stmt)
     783                 :       15518 :     if (get_pure_location (stmt->location) != UNKNOWN_LOCATION)
     784                 :       14315 :       return stmt->location;
     785                 :             : 
     786                 :        6666 :   if (entry_p ())
     787                 :             :     {
     788                 :             :       // TWEAK: show the decl instead; this leads to more readable output:
     789                 :        5169 :       return DECL_SOURCE_LOCATION (m_fun->decl);
     790                 :             : 
     791                 :             :       return m_fun->function_start_locus;
     792                 :             :     }
     793                 :        1497 :   if (return_p ())
     794                 :        1055 :     return m_fun->function_end_locus;
     795                 :             : 
     796                 :             :   /* We have no locations for stmts.  If we have a single out-edge that's
     797                 :             :      a CFG edge, the goto_locus of that edge is a better location for this
     798                 :             :      than UNKNOWN_LOCATION.  */
     799                 :         442 :   if (m_succs.length () == 1)
     800                 :         400 :     if (const cfg_superedge *cfg_sedge = m_succs[0]->dyn_cast_cfg_superedge ())
     801                 :         400 :       return cfg_sedge->get_goto_locus ();
     802                 :             : 
     803                 :             :   return UNKNOWN_LOCATION;
     804                 :             : }
     805                 :             : 
     806                 :             : /* Get a location_t for the end of this supernode.  */
     807                 :             : 
     808                 :             : location_t
     809                 :          62 : supernode::get_end_location () const
     810                 :             : {
     811                 :          62 :   int i;
     812                 :          62 :   gimple *stmt;
     813                 :          62 :   FOR_EACH_VEC_ELT_REVERSE (m_stmts, i, stmt)
     814                 :           0 :     if (get_pure_location (stmt->location) != UNKNOWN_LOCATION)
     815                 :           0 :       return stmt->location;
     816                 :             : 
     817                 :          62 :   if (m_returning_call
     818                 :          62 :       && get_pure_location (m_returning_call->location) != UNKNOWN_LOCATION)
     819                 :           0 :     return m_returning_call->location;
     820                 :             : 
     821                 :          62 :   if (entry_p ())
     822                 :           0 :     return m_fun->function_start_locus;
     823                 :          62 :   if (return_p ())
     824                 :           5 :     return m_fun->function_end_locus;
     825                 :             : 
     826                 :             :   /* If we have a single out-edge that's a CFG edge, use the goto_locus of
     827                 :             :      that edge.  */
     828                 :          57 :   if (m_succs.length () == 1)
     829                 :          57 :     if (const cfg_superedge *cfg_sedge = m_succs[0]->dyn_cast_cfg_superedge ())
     830                 :          57 :       return cfg_sedge->get_goto_locus ();
     831                 :             : 
     832                 :             :   return UNKNOWN_LOCATION;
     833                 :             : }
     834                 :             : 
     835                 :             : /* Given STMT within this supernode, return its index within m_stmts.  */
     836                 :             : 
     837                 :             : unsigned int
     838                 :       81286 : supernode::get_stmt_index (const gimple *stmt) const
     839                 :             : {
     840                 :       81286 :   unsigned i;
     841                 :       81286 :   gimple *iter_stmt;
     842                 :    12436676 :   FOR_EACH_VEC_ELT (m_stmts, i, iter_stmt)
     843                 :    12436676 :     if (iter_stmt == stmt)
     844                 :       81286 :       return i;
     845                 :           0 :   gcc_unreachable ();
     846                 :             : }
     847                 :             : 
     848                 :             : /* Get any label_decl for this supernode, or NULL_TREE if there isn't one.  */
     849                 :             : 
     850                 :             : tree
     851                 :          79 : supernode::get_label () const
     852                 :             : {
     853                 :          79 :   if (m_stmts.length () == 0)
     854                 :             :     return NULL_TREE;
     855                 :          79 :   const glabel *label_stmt = dyn_cast<const glabel *> (m_stmts[0]);
     856                 :          79 :   if (!label_stmt)
     857                 :             :     return NULL_TREE;
     858                 :          79 :   return gimple_label_label (label_stmt);
     859                 :             : }
     860                 :             : 
     861                 :             : /* Get a string for PK.  */
     862                 :             : 
     863                 :             : static const char *
     864                 :           8 : edge_kind_to_string (enum edge_kind kind)
     865                 :             : {
     866                 :           8 :   switch (kind)
     867                 :             :     {
     868                 :           0 :     default:
     869                 :           0 :       gcc_unreachable ();
     870                 :             :     case SUPEREDGE_CFG_EDGE:
     871                 :             :       return "SUPEREDGE_CFG_EDGE";
     872                 :           0 :     case SUPEREDGE_CALL:
     873                 :           0 :       return "SUPEREDGE_CALL";
     874                 :           0 :     case SUPEREDGE_RETURN:
     875                 :           0 :       return "SUPEREDGE_RETURN";
     876                 :           0 :     case SUPEREDGE_INTRAPROCEDURAL_CALL:
     877                 :           0 :       return "SUPEREDGE_INTRAPROCEDURAL_CALL";
     878                 :             :     }
     879                 :             : };
     880                 :             : 
     881                 :             : /* Dump this superedge to PP.  */
     882                 :             : 
     883                 :             : void
     884                 :           0 : superedge::dump (pretty_printer *pp) const
     885                 :             : {
     886                 :           0 :   pp_printf (pp, "edge: SN: %i -> SN: %i", m_src->m_index, m_dest->m_index);
     887                 :           0 :   label_text desc (get_description (false));
     888                 :           0 :   if (strlen (desc.get ()) > 0)
     889                 :             :     {
     890                 :           0 :       pp_space (pp);
     891                 :           0 :       pp_string (pp, desc.get ());
     892                 :             :     }
     893                 :           0 : }
     894                 :             : 
     895                 :             : /* Dump this superedge to stderr.  */
     896                 :             : 
     897                 :             : DEBUG_FUNCTION void
     898                 :           0 : superedge::dump () const
     899                 :             : {
     900                 :           0 :   tree_dump_pretty_printer pp (stderr);
     901                 :           0 :   dump (&pp);
     902                 :           0 :   pp_newline (&pp);
     903                 :           0 : }
     904                 :             : 
     905                 :             : /* Implementation of dedge::dump_dot for superedges.
     906                 :             :    Write a .dot edge to GV representing this superedge.  */
     907                 :             : 
     908                 :             : void
     909                 :         252 : superedge::dump_dot (graphviz_out *gv, const dump_args_t &) const
     910                 :             : {
     911                 :         252 :   const char *style = "\"solid,bold\"";
     912                 :         252 :   const char *color = "black";
     913                 :         252 :   int weight = 10;
     914                 :         252 :   const char *constraint = "true";
     915                 :             : 
     916                 :         252 :   switch (m_kind)
     917                 :             :     {
     918                 :           0 :     default:
     919                 :           0 :       gcc_unreachable ();
     920                 :             :     case SUPEREDGE_CFG_EDGE:
     921                 :             :       break;
     922                 :          12 :     case SUPEREDGE_CALL:
     923                 :          12 :       color = "red";
     924                 :          12 :       break;
     925                 :          12 :     case SUPEREDGE_RETURN:
     926                 :          12 :       color = "green";
     927                 :          12 :       break;
     928                 :          12 :     case SUPEREDGE_INTRAPROCEDURAL_CALL:
     929                 :          12 :       style = "\"dotted\"";
     930                 :          12 :       break;
     931                 :             :     }
     932                 :             : 
     933                 :             :   /* Adapted from graph.cc:draw_cfg_node_succ_edges.  */
     934                 :         252 :   if (::edge cfg_edge = get_any_cfg_edge ())
     935                 :             :     {
     936                 :         216 :       if (cfg_edge->flags & EDGE_FAKE)
     937                 :             :         {
     938                 :             :           style = "dotted";
     939                 :             :           color = "green";
     940                 :             :           weight = 0;
     941                 :             :         }
     942                 :         216 :       else if (cfg_edge->flags & EDGE_DFS_BACK)
     943                 :             :         {
     944                 :             :           style = "\"dotted,bold\"";
     945                 :             :           color = "blue";
     946                 :             :           weight = 10;
     947                 :             :         }
     948                 :         192 :       else if (cfg_edge->flags & EDGE_FALLTHRU)
     949                 :             :         {
     950                 :          96 :           color = "blue";
     951                 :          96 :           weight = 100;
     952                 :             :         }
     953                 :             : 
     954                 :         216 :       if (cfg_edge->flags & EDGE_ABNORMAL)
     955                 :           0 :         color = "red";
     956                 :             :     }
     957                 :             : 
     958                 :         252 :   gv->write_indent ();
     959                 :             : 
     960                 :         252 :   pretty_printer *pp = gv->get_pp ();
     961                 :             : 
     962                 :         252 :   m_src->dump_dot_id (pp);
     963                 :         252 :   pp_string (pp, " -> ");
     964                 :         252 :   m_dest->dump_dot_id (pp);
     965                 :         252 :   pp_printf (pp,
     966                 :             :              (" [style=%s, color=%s, weight=%d, constraint=%s,"
     967                 :             :               " ltail=\"cluster_node_%i\", lhead=\"cluster_node_%i\""
     968                 :             :               " headlabel=\""),
     969                 :             :              style, color, weight, constraint,
     970                 :         252 :              m_src->m_index, m_dest->m_index);
     971                 :             : 
     972                 :         252 :   dump_label_to_pp (pp, false);
     973                 :             : 
     974                 :         252 :   pp_printf (pp, "\"];\n");
     975                 :         252 : }
     976                 :             : 
     977                 :             : /* Return a new json::object of the form
     978                 :             :    {"kind"   : str,
     979                 :             :     "src_idx": int, the index of the source supernode,
     980                 :             :     "dst_idx": int, the index of the destination supernode,
     981                 :             :     "desc"   : str.  */
     982                 :             : 
     983                 :             : std::unique_ptr<json::object>
     984                 :           8 : superedge::to_json () const
     985                 :             : {
     986                 :           8 :   auto sedge_obj = ::make_unique<json::object> ();
     987                 :           8 :   sedge_obj->set_string ("kind", edge_kind_to_string (m_kind));
     988                 :           8 :   sedge_obj->set_integer ("src_idx", m_src->m_index);
     989                 :           8 :   sedge_obj->set_integer ("dst_idx", m_dest->m_index);
     990                 :             : 
     991                 :           8 :   {
     992                 :           8 :     pretty_printer pp;
     993                 :           8 :     pp_format_decoder (&pp) = default_tree_printer;
     994                 :           8 :     dump_label_to_pp (&pp, false);
     995                 :           8 :     sedge_obj->set_string ("desc", pp_formatted_text (&pp));
     996                 :           8 :   }
     997                 :             : 
     998                 :           8 :   return sedge_obj;
     999                 :             : }
    1000                 :             : 
    1001                 :             : /* If this is an intraprocedural superedge, return the associated
    1002                 :             :    CFG edge.  Otherwise, return NULL.  */
    1003                 :             : 
    1004                 :             : ::edge
    1005                 :         258 : superedge::get_any_cfg_edge () const
    1006                 :             : {
    1007                 :         258 :   if (const cfg_superedge *sub = dyn_cast_cfg_superedge ())
    1008                 :         222 :     return sub->get_cfg_edge ();
    1009                 :             :   return NULL;
    1010                 :             : }
    1011                 :             : 
    1012                 :             : /* If this is an interprocedural superedge, return the associated
    1013                 :             :    cgraph_edge *.  Otherwise, return NULL.  */
    1014                 :             : 
    1015                 :             : cgraph_edge *
    1016                 :        8356 : superedge::get_any_callgraph_edge () const
    1017                 :             : {
    1018                 :        8356 :   if (const callgraph_superedge *sub = dyn_cast_callgraph_superedge ())
    1019                 :        8356 :     return sub->m_cedge;
    1020                 :             :   return NULL;
    1021                 :             : }
    1022                 :             : 
    1023                 :             : /* Build a description of this superedge (e.g. "true" for the true
    1024                 :             :    edge of a conditional, or "case 42:" for a switch case).
    1025                 :             : 
    1026                 :             :    If USER_FACING is false, the result also contains any underlying
    1027                 :             :    CFG edge flags. e.g. " (flags FALLTHRU | DFS_BACK)".  */
    1028                 :             : 
    1029                 :             : label_text
    1030                 :       15133 : superedge::get_description (bool user_facing) const
    1031                 :             : {
    1032                 :       15133 :   pretty_printer pp;
    1033                 :       15133 :   dump_label_to_pp (&pp, user_facing);
    1034                 :       15133 :   return label_text::take (xstrdup (pp_formatted_text (&pp)));
    1035                 :       15133 : }
    1036                 :             : 
    1037                 :             : /* Implementation of superedge::dump_label_to_pp for non-switch CFG
    1038                 :             :    superedges.
    1039                 :             : 
    1040                 :             :    For true/false edges, print "true" or "false" to PP.
    1041                 :             : 
    1042                 :             :    If USER_FACING is false, also print flags on the underlying CFG edge to
    1043                 :             :    PP.  */
    1044                 :             : 
    1045                 :             : void
    1046                 :       15123 : cfg_superedge::dump_label_to_pp (pretty_printer *pp,
    1047                 :             :                                  bool user_facing) const
    1048                 :             : {
    1049                 :       15123 :   if (true_value_p ())
    1050                 :        3848 :     pp_printf (pp, "true");
    1051                 :       11275 :   else if (false_value_p ())
    1052                 :        3227 :     pp_printf (pp, "false");
    1053                 :             : 
    1054                 :       15123 :   if (user_facing)
    1055                 :             :     return;
    1056                 :             : 
    1057                 :             :   /* Express edge flags as a string with " | " separator.
    1058                 :             :      e.g. " (flags FALLTHRU | DFS_BACK)".  */
    1059                 :         451 :   if (get_flags ())
    1060                 :             :     {
    1061                 :         390 :       pp_string (pp, " (flags ");
    1062                 :         390 :       bool seen_flag = false;
    1063                 :             : #define DEF_EDGE_FLAG(NAME,IDX)                 \
    1064                 :             :   do {                                          \
    1065                 :             :     if (get_flags () & EDGE_##NAME)                 \
    1066                 :             :       {                                         \
    1067                 :             :         if (seen_flag)                          \
    1068                 :             :           pp_string (pp, " | ");                      \
    1069                 :             :         pp_printf (pp, "%s", (#NAME));                \
    1070                 :             :         seen_flag = true;                       \
    1071                 :             :       }                                         \
    1072                 :             :   } while (0);
    1073                 :             : #include "cfg-flags.def"
    1074                 :             : #undef DEF_EDGE_FLAG
    1075                 :         390 :       pp_string (pp, ")");
    1076                 :             :     }
    1077                 :             : 
    1078                 :         451 :   if (m_cfg_edge->goto_locus > BUILTINS_LOCATION)
    1079                 :         338 :     pp_string (pp, " (has goto_locus)");
    1080                 :             : 
    1081                 :             :   /* Otherwise, no label.  */
    1082                 :             : }
    1083                 :             : 
    1084                 :             : /* Get the index number for this edge for use in phi stmts
    1085                 :             :    in its destination.  */
    1086                 :             : 
    1087                 :             : size_t
    1088                 :       87542 : cfg_superedge::get_phi_arg_idx () const
    1089                 :             : {
    1090                 :       87542 :   return m_cfg_edge->dest_idx;
    1091                 :             : }
    1092                 :             : 
    1093                 :             : /* Get the phi argument for PHI for this CFG edge.  */
    1094                 :             : 
    1095                 :             : tree
    1096                 :       76646 : cfg_superedge::get_phi_arg (const gphi *phi) const
    1097                 :             : {
    1098                 :       76646 :   size_t index = get_phi_arg_idx ();
    1099                 :       76646 :   return gimple_phi_arg_def (phi, index);
    1100                 :             : }
    1101                 :             : 
    1102                 :        3005 : switch_cfg_superedge::switch_cfg_superedge (supernode *src,
    1103                 :             :                                             supernode *dst,
    1104                 :        3005 :                                             ::edge e)
    1105                 :        3005 : : cfg_superedge (src, dst, e)
    1106                 :             : {
    1107                 :             :   /* Populate m_case_labels with all cases which go to DST.  */
    1108                 :        3005 :   const gswitch *gswitch = get_switch_stmt ();
    1109                 :      542604 :   for (unsigned i = 0; i < gimple_switch_num_labels (gswitch); i++)
    1110                 :             :     {
    1111                 :      539599 :       tree case_ = gimple_switch_label (gswitch, i);
    1112                 :      539599 :       basic_block bb = label_to_block (src->get_function (),
    1113                 :      539599 :                                        CASE_LABEL (case_));
    1114                 :      539599 :       if (bb == dst->m_bb)
    1115                 :        3573 :         m_case_labels.safe_push (case_);
    1116                 :             :     }
    1117                 :        3005 : }
    1118                 :             : 
    1119                 :             : /* Implementation of superedge::dump_label_to_pp for CFG superedges for
    1120                 :             :    "switch" statements.
    1121                 :             : 
    1122                 :             :    Print "case VAL:", "case LOWER ... UPPER:", or "default:" to PP.  */
    1123                 :             : 
    1124                 :             : void
    1125                 :         414 : switch_cfg_superedge::dump_label_to_pp (pretty_printer *pp,
    1126                 :             :                                         bool user_facing ATTRIBUTE_UNUSED) const
    1127                 :             : {
    1128                 :         414 :   if (user_facing)
    1129                 :             :     {
    1130                 :         834 :       for (unsigned i = 0; i < m_case_labels.length (); ++i)
    1131                 :             :         {
    1132                 :         420 :           if (i > 0)
    1133                 :           6 :             pp_string (pp, ", ");
    1134                 :         420 :           tree case_label = m_case_labels[i];
    1135                 :         420 :           gcc_assert (TREE_CODE (case_label) == CASE_LABEL_EXPR);
    1136                 :         420 :           tree lower_bound = CASE_LOW (case_label);
    1137                 :         420 :           tree upper_bound = CASE_HIGH (case_label);
    1138                 :         420 :           if (lower_bound)
    1139                 :             :             {
    1140                 :         165 :               pp_printf (pp, "case ");
    1141                 :         165 :               dump_generic_node (pp, lower_bound, 0, (dump_flags_t)0, false);
    1142                 :         165 :               if (upper_bound)
    1143                 :             :                 {
    1144                 :          12 :                   pp_printf (pp, " ... ");
    1145                 :          12 :                   dump_generic_node (pp, upper_bound, 0, (dump_flags_t)0,
    1146                 :             :                                      false);
    1147                 :             :                 }
    1148                 :         165 :               pp_printf (pp, ":");
    1149                 :             :             }
    1150                 :             :           else
    1151                 :         255 :             pp_printf (pp, "default:");
    1152                 :             :         }
    1153                 :             :     }
    1154                 :             :   else
    1155                 :             :     {
    1156                 :           0 :       pp_character (pp, '{');
    1157                 :           0 :       for (unsigned i = 0; i < m_case_labels.length (); ++i)
    1158                 :             :         {
    1159                 :           0 :           if (i > 0)
    1160                 :           0 :             pp_string (pp, ", ");
    1161                 :           0 :           tree case_label = m_case_labels[i];
    1162                 :           0 :           gcc_assert (TREE_CODE (case_label) == CASE_LABEL_EXPR);
    1163                 :           0 :           tree lower_bound = CASE_LOW (case_label);
    1164                 :           0 :           tree upper_bound = CASE_HIGH (case_label);
    1165                 :           0 :           if (lower_bound)
    1166                 :             :             {
    1167                 :           0 :               if (upper_bound)
    1168                 :             :                 {
    1169                 :           0 :                   pp_character (pp, '[');
    1170                 :           0 :                   dump_generic_node (pp, lower_bound, 0, (dump_flags_t)0,
    1171                 :             :                                      false);
    1172                 :           0 :                   pp_string (pp, ", ");
    1173                 :           0 :                   dump_generic_node (pp, upper_bound, 0, (dump_flags_t)0,
    1174                 :             :                                      false);
    1175                 :           0 :                   pp_character (pp, ']');
    1176                 :             :                 }
    1177                 :             :               else
    1178                 :           0 :                 dump_generic_node (pp, lower_bound, 0, (dump_flags_t)0, false);
    1179                 :             :             }
    1180                 :             :           else
    1181                 :           0 :             pp_printf (pp, "default");
    1182                 :             :         }
    1183                 :           0 :       pp_character (pp, '}');
    1184                 :           0 :       if (implicitly_created_default_p ())
    1185                 :             :         {
    1186                 :           0 :           pp_string (pp, " IMPLICITLY CREATED");
    1187                 :             :         }
    1188                 :             :     }
    1189                 :         414 : }
    1190                 :             : 
    1191                 :             : /* Return true iff this edge is purely for an implicitly-created "default".  */
    1192                 :             : 
    1193                 :             : bool
    1194                 :         722 : switch_cfg_superedge::implicitly_created_default_p () const
    1195                 :             : {
    1196                 :         722 :   if (m_case_labels.length () != 1)
    1197                 :             :     return false;
    1198                 :             : 
    1199                 :         644 :   tree case_label = m_case_labels[0];
    1200                 :         644 :   gcc_assert (TREE_CODE (case_label) == CASE_LABEL_EXPR);
    1201                 :         644 :   if (CASE_LOW (case_label))
    1202                 :             :     return false;
    1203                 :             : 
    1204                 :             :   /* We have a single "default" case.
    1205                 :             :      Assume that it was implicitly created if it has UNKNOWN_LOCATION.  */
    1206                 :         187 :   return EXPR_LOCATION (case_label) == UNKNOWN_LOCATION;
    1207                 :             : }
    1208                 :             : 
    1209                 :             : /* Implementation of superedge::dump_label_to_pp for interprocedural
    1210                 :             :    superedges.  */
    1211                 :             : 
    1212                 :             : void
    1213                 :          52 : callgraph_superedge::dump_label_to_pp (pretty_printer *pp,
    1214                 :             :                                        bool user_facing ATTRIBUTE_UNUSED) const
    1215                 :             : {
    1216                 :          52 :   switch (m_kind)
    1217                 :             :     {
    1218                 :           0 :     default:
    1219                 :           0 :     case SUPEREDGE_CFG_EDGE:
    1220                 :           0 :       gcc_unreachable ();
    1221                 :             : 
    1222                 :          20 :     case SUPEREDGE_CALL:
    1223                 :          20 :       pp_printf (pp, "call");
    1224                 :          20 :       break;
    1225                 :             : 
    1226                 :          20 :     case SUPEREDGE_RETURN:
    1227                 :          20 :       pp_printf (pp, "return");
    1228                 :          20 :       break;
    1229                 :             : 
    1230                 :          12 :     case SUPEREDGE_INTRAPROCEDURAL_CALL:
    1231                 :          12 :       pp_printf (pp, "intraproc link");
    1232                 :          12 :       break;
    1233                 :             :     }
    1234                 :          52 : }
    1235                 :             : 
    1236                 :             : /* Get the function that was called at this interprocedural call/return
    1237                 :             :    edge.  */
    1238                 :             : 
    1239                 :             : function *
    1240                 :       10364 : callgraph_superedge::get_callee_function () const
    1241                 :             : {
    1242                 :       10364 :   return get_ultimate_function_for_cgraph_edge (m_cedge);
    1243                 :             : }
    1244                 :             : 
    1245                 :             : /* Get the calling function at this interprocedural call/return edge.  */
    1246                 :             : 
    1247                 :             : function *
    1248                 :           0 : callgraph_superedge::get_caller_function () const
    1249                 :             : {
    1250                 :           0 :   return m_cedge->caller->get_fun ();
    1251                 :             : }
    1252                 :             : 
    1253                 :             : /* Get the fndecl that was called at this interprocedural call/return
    1254                 :             :    edge.  */
    1255                 :             : 
    1256                 :             : tree
    1257                 :         931 : callgraph_superedge::get_callee_decl () const
    1258                 :             : {
    1259                 :         931 :   return get_callee_function ()->decl;
    1260                 :             : }
    1261                 :             : 
    1262                 :             : /* Get the gcall * of this interprocedural call/return edge.  */
    1263                 :             : 
    1264                 :             : gcall *
    1265                 :       18122 : callgraph_superedge::get_call_stmt () const
    1266                 :             : {
    1267                 :       18122 :   if (m_cedge)
    1268                 :       18122 :     return m_cedge->call_stmt;
    1269                 :             : 
    1270                 :           0 :   return m_src->get_final_call ();
    1271                 :             : }
    1272                 :             : 
    1273                 :             : /* Get the calling fndecl at this interprocedural call/return edge.  */
    1274                 :             : 
    1275                 :             : tree
    1276                 :           0 : callgraph_superedge::get_caller_decl () const
    1277                 :             : {
    1278                 :           0 :   return get_caller_function ()->decl;
    1279                 :             : }
    1280                 :             : 
    1281                 :             : /* Given PARM_TO_FIND, a PARM_DECL, identify its index (writing it
    1282                 :             :    to *OUT if OUT is non-NULL), and return the corresponding argument
    1283                 :             :    at the callsite.  */
    1284                 :             : 
    1285                 :             : tree
    1286                 :         233 : callgraph_superedge::get_arg_for_parm (tree parm_to_find,
    1287                 :             :                                        callsite_expr *out) const
    1288                 :             : {
    1289                 :         233 :   gcc_assert  (TREE_CODE (parm_to_find) == PARM_DECL);
    1290                 :             : 
    1291                 :         233 :   tree callee = get_callee_decl ();
    1292                 :         233 :   const gcall *call_stmt = get_call_stmt ();
    1293                 :             : 
    1294                 :         233 :   unsigned i = 0;
    1295                 :         257 :   for (tree iter_parm = DECL_ARGUMENTS (callee); iter_parm;
    1296                 :          24 :        iter_parm = DECL_CHAIN (iter_parm), ++i)
    1297                 :             :     {
    1298                 :         222 :       if (i >= gimple_call_num_args (call_stmt))
    1299                 :             :         return NULL_TREE;
    1300                 :         222 :       if (iter_parm == parm_to_find)
    1301                 :             :         {
    1302                 :         198 :           if (out)
    1303                 :         198 :             *out = callsite_expr::from_zero_based_param (i);
    1304                 :         198 :           return gimple_call_arg (call_stmt, i);
    1305                 :             :         }
    1306                 :             :     }
    1307                 :             : 
    1308                 :             :   /* Not found.  */
    1309                 :             :   return NULL_TREE;
    1310                 :             : }
    1311                 :             : 
    1312                 :             : /* Look for a use of ARG_TO_FIND as an argument at this callsite.
    1313                 :             :    If found, return the default SSA def of the corresponding parm within
    1314                 :             :    the callee, and if OUT is non-NULL, write the index to *OUT.
    1315                 :             :    Only the first match is handled.  */
    1316                 :             : 
    1317                 :             : tree
    1318                 :         452 : callgraph_superedge::get_parm_for_arg (tree arg_to_find,
    1319                 :             :                                        callsite_expr *out) const
    1320                 :             : {
    1321                 :         452 :   tree callee = get_callee_decl ();
    1322                 :         452 :   const gcall *call_stmt = get_call_stmt ();
    1323                 :             : 
    1324                 :         452 :   unsigned i = 0;
    1325                 :         777 :   for (tree iter_parm = DECL_ARGUMENTS (callee); iter_parm;
    1326                 :         325 :        iter_parm = DECL_CHAIN (iter_parm), ++i)
    1327                 :             :     {
    1328                 :         409 :       if (i >= gimple_call_num_args (call_stmt))
    1329                 :             :         return NULL_TREE;
    1330                 :         408 :       tree param = gimple_call_arg (call_stmt, i);
    1331                 :         408 :       if (arg_to_find == param)
    1332                 :             :         {
    1333                 :          83 :           if (out)
    1334                 :          83 :             *out = callsite_expr::from_zero_based_param (i);
    1335                 :          83 :           return ssa_default_def (get_callee_function (), iter_parm);
    1336                 :             :         }
    1337                 :             :     }
    1338                 :             : 
    1339                 :             :   /* Not found.  */
    1340                 :             :   return NULL_TREE;
    1341                 :             : }
    1342                 :             : 
    1343                 :             : /* Map caller_expr back to an expr within the callee, or return NULL_TREE.
    1344                 :             :    If non-NULL is returned, populate OUT.  */
    1345                 :             : 
    1346                 :             : tree
    1347                 :         452 : callgraph_superedge::map_expr_from_caller_to_callee (tree caller_expr,
    1348                 :             :                                                      callsite_expr *out) const
    1349                 :             : {
    1350                 :             :   /* Is it an argument (actual param)?  If so, convert to
    1351                 :             :      parameter (formal param).  */
    1352                 :         452 :   tree parm = get_parm_for_arg (caller_expr, out);
    1353                 :         452 :   if (parm)
    1354                 :             :     return parm;
    1355                 :             :   /* Otherwise try return value.  */
    1356                 :         373 :   if (caller_expr == gimple_call_lhs (get_call_stmt ()))
    1357                 :             :     {
    1358                 :          63 :       if (out)
    1359                 :          63 :         *out = callsite_expr::from_return_value ();
    1360                 :          63 :       return DECL_RESULT (get_callee_decl ());
    1361                 :             :     }
    1362                 :             : 
    1363                 :             :   return NULL_TREE;
    1364                 :             : }
    1365                 :             : 
    1366                 :             : /* Map callee_expr back to an expr within the caller, or return NULL_TREE.
    1367                 :             :    If non-NULL is returned, populate OUT.  */
    1368                 :             : 
    1369                 :             : tree
    1370                 :        1120 : callgraph_superedge::map_expr_from_callee_to_caller (tree callee_expr,
    1371                 :             :                                                      callsite_expr *out) const
    1372                 :             : {
    1373                 :        1120 :   if (callee_expr == NULL_TREE)
    1374                 :             :     return NULL_TREE;
    1375                 :             : 
    1376                 :             :   /* If it's a parameter (formal param), get the argument (actual param).  */
    1377                 :         416 :   if (TREE_CODE (callee_expr) == PARM_DECL)
    1378                 :          10 :     return get_arg_for_parm (callee_expr, out);
    1379                 :             : 
    1380                 :             :   /* Similar for the default SSA name of the PARM_DECL.  */
    1381                 :         406 :   if (TREE_CODE (callee_expr) == SSA_NAME
    1382                 :         339 :       && SSA_NAME_IS_DEFAULT_DEF (callee_expr)
    1383                 :         629 :       && TREE_CODE (SSA_NAME_VAR (callee_expr)) == PARM_DECL)
    1384                 :         223 :     return get_arg_for_parm (SSA_NAME_VAR (callee_expr), out);
    1385                 :             : 
    1386                 :             :   /* Otherwise try return value.  */
    1387                 :         183 :   if (callee_expr == DECL_RESULT (get_callee_decl ()))
    1388                 :             :     {
    1389                 :           0 :       if (out)
    1390                 :           0 :         *out = callsite_expr::from_return_value ();
    1391                 :           0 :       return gimple_call_lhs (get_call_stmt ());
    1392                 :             :     }
    1393                 :             : 
    1394                 :             :   return NULL_TREE;
    1395                 :             : }
    1396                 :             : 
    1397                 :             : } // namespace ana
    1398                 :             : 
    1399                 :             : #endif /* #if ENABLE_ANALYZER */
        

Generated by: LCOV version 2.1-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.