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