gcc/analyzer/state-purge.cc

   1 /* Classes for purging state at function_points.
   2    Copyright (C) 2019-2020 Free Software Foundation, Inc.
   3    Contributed by David Malcolm <dmalcolm@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tree.h"
  25 #include "timevar.h"
  26 #include "tree-ssa-alias.h"
  27 #include "function.h"
  28 #include "basic-block.h"
  29 #include "gimple.h"
  30 #include "stringpool.h"
  31 #include "tree-vrp.h"
  32 #include "gimple-ssa.h"
  33 #include "tree-ssanames.h"
  34 #include "tree-phinodes.h"
  35 #include "options.h"
  36 #include "ssa-iterators.h"
  37 #include "diagnostic-core.h"
  38 #include "gimple-pretty-print.h"
  39 #include "function.h"
  40 #include "analyzer/analyzer.h"
  41 #include "analyzer/call-string.h"
  42 #include "digraph.h"
  43 #include "ordered-hash-map.h"
  44 #include "cfg.h"
  45 #include "gimple-iterator.h"
  46 #include "cgraph.h"
  47 #include "analyzer/supergraph.h"
  48 #include "analyzer/program-point.h"
  49 #include "analyzer/analyzer-logging.h"
  50 #include "analyzer/state-purge.h"
  51
  52 #if ENABLE_ANALYZER
  53
  54 /* state_purge_map's ctor.  Walk all SSA names in all functions, building
  55    a state_purge_per_ssa_name instance for each.  */
  56
  57 state_purge_map::state_purge_map (const supergraph &sg,
  58                                   logger *logger)
  59 : log_user (logger), m_sg (sg)
  60 {
  61   LOG_FUNC (logger);
  62
  63   auto_timevar tv (TV_ANALYZER_STATE_PURGE);
  64
  65   cgraph_node *node;
  66   FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
  67   {
  68     function *fun = node->get_fun ();
  69     if (logger)
  70       log ("function: %s", function_name (fun));
  71     tree name;
  72     unsigned int i;;
  73     FOR_EACH_SSA_NAME (i, name, fun)
  74       {
  75         /* For now, don't bother tracking the .MEM SSA names.  */
  76         if (tree var = SSA_NAME_VAR (name))
  77           if (TREE_CODE (var) == VAR_DECL)
  78             if (VAR_DECL_IS_VIRTUAL_OPERAND (var))
  79               continue;
  80         m_map.put (name, new state_purge_per_ssa_name (*this, name, fun));
  81       }
  82   }
  83 }
  84
  85 /* state_purge_map's dtor.  */
  86
  87 state_purge_map::~state_purge_map ()
  88 {
  89   for (iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
  90     delete (*iter).second;
  91 }
  92
  93 /* state_purge_per_ssa_name's ctor.
  94
  95    Locate all uses of VAR within FUN.
  96    Walk backwards from each use, marking program points, until
  97    we reach the def stmt, populating m_points_needing_var.
  98
  99    We have to track program points rather than
 100    just stmts since there could be empty basic blocks on the way.  */
 101
 102 state_purge_per_ssa_name::state_purge_per_ssa_name (const state_purge_map &map,
 103                                                     tree name,
 104                                                     function *fun)
 105 : m_points_needing_name (), m_name (name), m_fun (fun)
 106 {
 107   LOG_FUNC (map.get_logger ());
 108
 109   if (map.get_logger ())
 110     {
 111       map.log ("SSA name: %qE within %qD", name, fun->decl);
 112
 113       /* Show def stmt.  */
 114       const gimple *def_stmt = SSA_NAME_DEF_STMT (name);
 115       pretty_printer pp;
 116       pp_gimple_stmt_1 (&pp, def_stmt, 0, (dump_flags_t)0);
 117       map.log ("def stmt: %s", pp_formatted_text (&pp));
 118     }
 119
 120   auto_vec<function_point> worklist;
 121
 122   /* Add all immediate uses of name to the worklist.
 123      Compare with debug_immediate_uses.  */
 124   imm_use_iterator iter;
 125   use_operand_p use_p;
 126   FOR_EACH_IMM_USE_FAST (use_p, iter, name)
 127     {
 128       if (USE_STMT (use_p))
 129         {
 130           const gimple *use_stmt = USE_STMT (use_p);
 131           if (map.get_logger ())
 132             {
 133               pretty_printer pp;
 134               pp_gimple_stmt_1 (&pp, use_stmt, 0, (dump_flags_t)0);
 135               map.log ("used by stmt: %s", pp_formatted_text (&pp));
 136             }
 137
 138           const supernode *snode
 139             = map.get_sg ().get_supernode_for_stmt (use_stmt);
 140
 141           /* If it's a use within a phi node, then we care about
 142              which in-edge we came from.  */
 143           if (use_stmt->code == GIMPLE_PHI)
 144             {
 145               for (gphi_iterator gpi
 146                      = const_cast<supernode *> (snode)->start_phis ();
 147                    !gsi_end_p (gpi); gsi_next (&gpi))
 148                 {
 149                   gphi *phi = gpi.phi ();
 150                   if (phi == use_stmt)
 151                     {
 152                       /* Find arguments (and thus in-edges) which use NAME.  */
 153                       for (unsigned arg_idx = 0;
 154                            arg_idx < gimple_phi_num_args (phi);
 155                            ++arg_idx)
 156                         {
 157                           if (name == gimple_phi_arg (phi, arg_idx)->def)
 158                             {
 159                               edge in_edge = gimple_phi_arg_edge (phi, arg_idx);
 160                               const superedge *in_sedge
 161                                 = map.get_sg ().get_edge_for_cfg_edge (in_edge);
 162                               function_point point
 163                                 = function_point::before_supernode
 164                                 (snode, in_sedge);
 165                               add_to_worklist (point, &worklist,
 166                                                map.get_logger ());
 167                               m_points_needing_name.add (point);
 168                             }
 169                         }
 170                     }
 171                 }
 172             }
 173           else
 174             {
 175               function_point point = before_use_stmt (map, use_stmt);
 176               add_to_worklist (point, &worklist, map.get_logger ());
 177               m_points_needing_name.add (point);
 178
 179               /* We also need to add uses for conditionals and switches,
 180                  where the stmt "happens" at the after_supernode, for filtering
 181                  the out-edges.  */
 182               if (use_stmt == snode->get_last_stmt ())
 183                 {
 184                   if (map.get_logger ())
 185                     map.log ("last stmt in BB");
 186                   function_point point
 187                     = function_point::after_supernode (snode);
 188                   add_to_worklist (point, &worklist, map.get_logger ());
 189                   m_points_needing_name.add (point);
 190                 }
 191               else
 192                 if (map.get_logger ())
 193                   map.log ("not last stmt in BB");
 194             }
 195         }
 196     }
 197
 198   /* Process worklist by walking backwards until we reach the def stmt.  */
 199   {
 200     log_scope s (map.get_logger (), "processing worklist");
 201     while (worklist.length () > 0)
 202       {
 203         function_point point = worklist.pop ();
 204         process_point (point, &worklist, map);
 205     }
 206   }
 207
 208   if (map.get_logger ())
 209     {
 210       map.log ("%qE in %qD is needed to process:", name, fun->decl);
 211       for (point_set_t::iterator iter = m_points_needing_name.begin ();
 212            iter != m_points_needing_name.end ();
 213            ++iter)
 214         {
 215           map.start_log_line ();
 216           map.get_logger ()->log_partial ("  point: ");
 217           (*iter).print (map.get_logger ()->get_printer (), format (false));
 218           map.end_log_line ();
 219         }
 220     }
 221 }
 222
 223 /* Return true if the SSA name is needed at POINT.  */
 224
 225 bool
 226 state_purge_per_ssa_name::needed_at_point_p (const function_point &point) const
 227 {
 228   return const_cast <point_set_t &> (m_points_needing_name).contains (point);
 229 }
 230
 231 /* Get the function_point representing immediately before USE_STMT.
 232    Subroutine of ctor.  */
 233
 234 function_point
 235 state_purge_per_ssa_name::before_use_stmt (const state_purge_map &map,
 236                                            const gimple *use_stmt)
 237 {
 238   gcc_assert (use_stmt->code != GIMPLE_PHI);
 239
 240   const supernode *supernode
 241     = map.get_sg ().get_supernode_for_stmt (use_stmt);
 242   unsigned int stmt_idx = supernode->get_stmt_index (use_stmt);
 243   return function_point::before_stmt (supernode, stmt_idx);
 244 }
 245
 246 /* Add POINT to *WORKLIST if the point has not already been seen.
 247    Subroutine of ctor.  */
 248
 249 void
 250 state_purge_per_ssa_name::add_to_worklist (const function_point &point,
 251                                            auto_vec<function_point> *worklist,
 252                                            logger *logger)
 253 {
 254   LOG_FUNC (logger);
 255   if (logger)
 256     {
 257       logger->start_log_line ();
 258       logger->log_partial ("point: '");
 259       point.print (logger->get_printer (), format (false));
 260       logger->log_partial ("' for worklist for %qE", m_name);
 261       logger->end_log_line ();
 262     }
 263
 264   gcc_assert (point.get_function () == m_fun);
 265   if (point.get_from_edge ())
 266     gcc_assert (point.get_from_edge ()->get_kind () == SUPEREDGE_CFG_EDGE);
 267
 268   if (m_points_needing_name.contains (point))
 269     {
 270       if (logger)
 271         logger->log ("already seen for %qE", m_name);
 272     }
 273   else
 274     {
 275       if (logger)
 276         logger->log ("not seen; adding to worklist for %qE", m_name);
 277       m_points_needing_name.add (point);
 278       worklist->safe_push (point);
 279     }
 280 }
 281
 282 /* Process POINT, popped from WORKLIST.
 283    Iterate over predecessors of POINT, adding to WORKLIST.  */
 284
 285 void
 286 state_purge_per_ssa_name::process_point (const function_point &point,
 287                                          auto_vec<function_point> *worklist,
 288                                          const state_purge_map &map)
 289 {
 290   logger *logger = map.get_logger ();
 291   LOG_FUNC (logger);
 292   if (logger)
 293     {
 294       logger->start_log_line ();
 295       logger->log_partial ("considering point: '");
 296       point.print (logger->get_printer (), format (false));
 297       logger->log_partial ("' for %qE", m_name);
 298       logger->end_log_line ();
 299     }
 300
 301   gimple *def_stmt = SSA_NAME_DEF_STMT (m_name);
 302
 303   const supernode *snode = point.get_supernode ();
 304
 305   switch (point.get_kind ())
 306     {
 307     default:
 308       gcc_unreachable ();
 309
 310     case PK_ORIGIN:
 311       break;
 312
 313     case PK_BEFORE_SUPERNODE:
 314       {
 315         for (gphi_iterator gpi
 316                = const_cast<supernode *> (snode)->start_phis ();
 317              !gsi_end_p (gpi); gsi_next (&gpi))
 318           {
 319             gphi *phi = gpi.phi ();
 320             if (phi == def_stmt)
 321               {
 322                 if (logger)
 323                   logger->log ("def stmt within phis; terminating");
 324                 return;
 325               }
 326           }
 327
 328         /* Add given pred to worklist.  */
 329         if (point.get_from_edge ())
 330           {
 331             gcc_assert (point.get_from_edge ()->m_src);
 332             add_to_worklist
 333               (function_point::after_supernode (point.get_from_edge ()->m_src),
 334                worklist, logger);
 335           }
 336         else
 337           {
 338             /* Add any intraprocedually edge for a call.  */
 339             if (snode->m_returning_call)
 340               {
 341                 cgraph_edge *cedge
 342                   = supergraph_call_edge (snode->m_fun,
 343                                           snode->m_returning_call);
 344                 gcc_assert (cedge);
 345                 superedge *sedge
 346                   = map.get_sg ().get_intraprocedural_edge_for_call (cedge);
 347                 gcc_assert (sedge);
 348                 add_to_worklist
 349                   (function_point::after_supernode (sedge->m_src),
 350                    worklist, logger);
 351               }
 352           }
 353       }
 354       break;
 355
 356     case PK_BEFORE_STMT:
 357       {
 358         if (def_stmt == point.get_stmt ())
 359           {
 360             if (logger)
 361               logger->log ("def stmt; terminating");
 362             return;
 363           }
 364         if (point.get_stmt_idx () > 0)
 365           add_to_worklist (function_point::before_stmt
 366                              (snode, point.get_stmt_idx () - 1),
 367                            worklist, logger);
 368         else
 369         {
 370           /* Add before_supernode to worklist.  This captures the in-edge,
 371              so we have to do it once per in-edge.  */
 372           unsigned i;
 373           superedge *pred;
 374           FOR_EACH_VEC_ELT (snode->m_preds, i, pred)
 375             add_to_worklist (function_point::before_supernode (snode,
 376                                                                pred),
 377                              worklist, logger);
 378         }
 379       }
 380       break;
 381
 382     case PK_AFTER_SUPERNODE:
 383       {
 384         if (snode->m_stmts.length ())
 385           add_to_worklist
 386             (function_point::before_stmt (snode,
 387                                           snode->m_stmts.length () - 1),
 388              worklist, logger);
 389         else
 390           {
 391             /* Add before_supernode to worklist.  This captures the in-edge,
 392                so we have to do it once per in-edge.  */
 393             unsigned i;
 394             superedge *pred;
 395             FOR_EACH_VEC_ELT (snode->m_preds, i, pred)
 396               add_to_worklist (function_point::before_supernode (snode,
 397                                                                  pred),
 398                                worklist, logger);
 399             /* If it's the initial BB, add it, to ensure that we
 400                have "before supernode" for the initial ENTRY block, and don't
 401                erroneously purge SSA names for initial values of parameters.  */
 402             if (snode->entry_p ())
 403               {
 404                 add_to_worklist
 405                   (function_point::before_supernode (snode, NULL),
 406                    worklist, logger);
 407               }
 408           }
 409       }
 410       break;
 411     }
 412 }
 413
 414 /* class state_purge_annotator : public dot_annotator.  */
 415
 416 /* Implementation of dot_annotator::add_node_annotations vfunc for
 417    state_purge_annotator.
 418
 419    Add an additional record showing which names are purged on entry
 420    to the supernode N.  */
 421
 422 void
 423 state_purge_annotator::add_node_annotations (graphviz_out *gv,
 424                                              const supernode &n) const
 425 {
 426   if (m_map == NULL)
 427     return;
 428
 429   pretty_printer *pp = gv->get_pp ();
 430
 431    pp_printf (pp, "annotation_for_node_%i", n.m_index);
 432    pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
 433               "lightblue");
 434    pp_write_text_to_stream (pp);
 435
 436    // FIXME: passing in a NULL in-edge means we get no hits
 437    function_point before_supernode
 438      (function_point::before_supernode (&n, NULL));
 439
 440    for (state_purge_map::iterator iter = m_map->begin ();
 441         iter != m_map->end ();
 442         ++iter)
 443      {
 444        tree name = (*iter).first;
 445        state_purge_per_ssa_name *per_name_data = (*iter).second;
 446        if (per_name_data->get_function () == n.m_fun)
 447          {
 448            if (per_name_data->needed_at_point_p (before_supernode))
 449              pp_printf (pp, "%qE needed here", name);
 450            else
 451              pp_printf (pp, "%qE not needed here", name);
 452          }
 453        pp_newline (pp);
 454      }
 455
 456    pp_string (pp, "\"];\n\n");
 457    pp_flush (pp);
 458 }
 459
 460 /* Print V to GV as a comma-separated list in braces within a <TR>,
 461    titling it with TITLE.
 462
 463    Subroutine of state_purge_annotator::add_stmt_annotations.  */
 464
 465 static void
 466 print_vec_of_names (graphviz_out *gv, const char *title,
 467                     const auto_vec<tree> &v)
 468 {
 469   pretty_printer *pp = gv->get_pp ();
 470   tree name;
 471   unsigned i;
 472   gv->begin_tr ();
 473   pp_printf (pp, "%s: {", title);
 474   FOR_EACH_VEC_ELT (v, i, name)
 475     {
 476       if (i > 0)
 477         pp_string (pp, ", ");
 478       pp_printf (pp, "%qE", name);
 479     }
 480   pp_printf (pp, "}");
 481   pp_write_text_as_html_like_dot_to_stream (pp);
 482   gv->end_tr ();
 483   pp_newline (pp);
 484 }
 485
 486 /* Implementation of dot_annotator::add_stmt_annotations for
 487    state_purge_annotator.
 488
 489    Add text showing which names are purged at STMT.  */
 490
 491 void
 492 state_purge_annotator::add_stmt_annotations (graphviz_out *gv,
 493                                              const gimple *stmt) const
 494 {
 495   if (m_map == NULL)
 496     return;
 497
 498   if (stmt->code == GIMPLE_PHI)
 499     return;
 500
 501   pretty_printer *pp = gv->get_pp ();
 502
 503   pp_newline (pp);
 504
 505   const supernode *supernode = m_map->get_sg ().get_supernode_for_stmt (stmt);
 506   unsigned int stmt_idx = supernode->get_stmt_index (stmt);
 507   function_point before_stmt
 508     (function_point::before_stmt (supernode, stmt_idx));
 509
 510   auto_vec<tree> needed;
 511   auto_vec<tree> not_needed;
 512   for (state_purge_map::iterator iter = m_map->begin ();
 513        iter != m_map->end ();
 514        ++iter)
 515     {
 516       tree name = (*iter).first;
 517       state_purge_per_ssa_name *per_name_data = (*iter).second;
 518       if (per_name_data->get_function () == supernode->m_fun)
 519         {
 520           if (per_name_data->needed_at_point_p (before_stmt))
 521             needed.safe_push (name);
 522           else
 523             not_needed.safe_push (name);
 524         }
 525     }
 526
 527   print_vec_of_names (gv, "needed here", needed);
 528   print_vec_of_names (gv, "not needed here", not_needed);
 529 }
 530
 531 #endif /* #if ENABLE_ANALYZER */