gcc/analyzer/program-point.cc

   1 /* Classes for representing locations within the program.
   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 "gimple-pretty-print.h"
  26 #include "gcc-rich-location.h"
  27 #include "json.h"
  28 #include "analyzer/call-string.h"
  29 #include "ordered-hash-map.h"
  30 #include "options.h"
  31 #include "cgraph.h"
  32 #include "function.h"
  33 #include "cfg.h"
  34 #include "basic-block.h"
  35 #include "gimple.h"
  36 #include "gimple-iterator.h"
  37 #include "digraph.h"
  38 #include "analyzer/analyzer.h"
  39 #include "analyzer/analyzer-logging.h"
  40 #include "analyzer/supergraph.h"
  41 #include "analyzer/program-point.h"
  42 #include "sbitmap.h"
  43 #include "bitmap.h"
  44 #include "tristate.h"
  45 #include "selftest.h"
  46 #include "analyzer/store.h"
  47 #include "analyzer/region-model.h"
  48 #include "analyzer/sm.h"
  49 #include "analyzer/program-state.h"
  50 #include "alloc-pool.h"
  51 #include "fibonacci_heap.h"
  52 #include "diagnostic-event-id.h"
  53 #include "analyzer/pending-diagnostic.h"
  54 #include "analyzer/diagnostic-manager.h"
  55 #include "shortest-paths.h"
  56 #include "analyzer/exploded-graph.h"
  57 #include "analyzer/analysis-plan.h"
  58
  59 #if ENABLE_ANALYZER
  60
  61 namespace ana {
  62
  63 /* Get a string for PK.  */
  64
  65 const char *
  66 point_kind_to_string (enum point_kind pk)
  67 {
  68   switch (pk)
  69     {
  70     default:
  71       gcc_unreachable ();
  72     case PK_ORIGIN:
  73       return "PK_ORIGIN";
  74     case PK_BEFORE_SUPERNODE:
  75       return "PK_BEFORE_SUPERNODE";
  76     case PK_BEFORE_STMT:
  77       return "PK_BEFORE_STMT";
  78     case PK_AFTER_SUPERNODE:
  79       return "PK_AFTER_SUPERNODE";
  80     case PK_EMPTY:
  81       return "PK_EMPTY";
  82     case PK_DELETED:
  83       return "PK_DELETED";
  84     }
  85 }
  86
  87 /* class function_point.  */
  88
  89 function_point::function_point (const supernode *supernode,
  90                                 const superedge *from_edge,
  91                                 unsigned stmt_idx,
  92                                 enum point_kind kind)
  93 : m_supernode (supernode), m_from_edge (from_edge),
  94   m_stmt_idx (stmt_idx), m_kind (kind)
  95 {
  96   if (from_edge)
  97     {
  98       gcc_checking_assert (m_kind == PK_BEFORE_SUPERNODE);
  99       gcc_checking_assert (from_edge->get_kind () == SUPEREDGE_CFG_EDGE);
 100     }
 101   if (stmt_idx)
 102     gcc_checking_assert (m_kind == PK_BEFORE_STMT);
 103 }
 104
 105 /* Print this function_point to PP.  */
 106
 107 void
 108 function_point::print (pretty_printer *pp, const format &f) const
 109 {
 110   switch (get_kind ())
 111     {
 112     default:
 113       gcc_unreachable ();
 114
 115     case PK_ORIGIN:
 116       pp_printf (pp, "origin");
 117       break;
 118
 119     case PK_BEFORE_SUPERNODE:
 120       {
 121         if (m_from_edge)
 122           pp_printf (pp, "before SN: %i (from SN: %i)",
 123                      m_supernode->m_index, m_from_edge->m_src->m_index);
 124         else
 125           pp_printf (pp, "before SN: %i (NULL from-edge)",
 126                      m_supernode->m_index);
 127         f.spacer (pp);
 128         for (gphi_iterator gpi
 129                = const_cast<supernode *>(get_supernode ())->start_phis ();
 130              !gsi_end_p (gpi); gsi_next (&gpi))
 131           {
 132             const gphi *phi = gpi.phi ();
 133             pp_gimple_stmt_1 (pp, phi, 0, (dump_flags_t)0);
 134           }
 135       }
 136       break;
 137
 138     case PK_BEFORE_STMT:
 139       pp_printf (pp, "before (SN: %i stmt: %i): ", m_supernode->m_index,
 140                  m_stmt_idx);
 141       f.spacer (pp);
 142       pp_gimple_stmt_1 (pp, get_stmt (), 0, (dump_flags_t)0);
 143       if (f.m_newlines)
 144         {
 145           pp_newline (pp);
 146           print_source_line (pp);
 147         }
 148       break;
 149
 150     case PK_AFTER_SUPERNODE:
 151       pp_printf (pp, "after SN: %i", m_supernode->m_index);
 152       break;
 153     }
 154 }
 155
 156 /* Generate a hash value for this function_point.  */
 157
 158 hashval_t
 159 function_point::hash () const
 160 {
 161   inchash::hash hstate;
 162   if (m_supernode)
 163     hstate.add_int (m_supernode->m_index);
 164   hstate.add_ptr (m_from_edge);
 165   hstate.add_int (m_stmt_idx);
 166   hstate.add_int (m_kind);
 167   return hstate.end ();
 168 }
 169
 170 /* Get the function at this point, if any.  */
 171
 172 function *
 173 function_point::get_function () const
 174 {
 175   if (m_supernode)
 176     return m_supernode->m_fun;
 177   else
 178     return NULL;
 179 }
 180
 181 /* Get the gimple stmt for this function_point, if any.  */
 182
 183 const gimple *
 184 function_point::get_stmt () const
 185 {
 186   if (m_kind == PK_BEFORE_STMT)
 187     return m_supernode->m_stmts[m_stmt_idx];
 188   else if (m_kind == PK_AFTER_SUPERNODE)
 189     return m_supernode->get_last_stmt ();
 190   else
 191     return NULL;
 192 }
 193
 194 /* Get a location for this function_point, if any.  */
 195
 196 location_t
 197 function_point::get_location () const
 198 {
 199   const gimple *stmt = get_stmt ();
 200   if (stmt)
 201     return stmt->location;
 202   if (m_kind == PK_BEFORE_SUPERNODE)
 203     return m_supernode->get_start_location ();
 204   else if (m_kind == PK_AFTER_SUPERNODE)
 205     return m_supernode->get_end_location ();
 206   else
 207     return UNKNOWN_LOCATION;
 208 }
 209
 210 /* Create a function_point representing the entrypoint of function FUN.  */
 211
 212 function_point
 213 function_point::from_function_entry (const supergraph &sg, function *fun)
 214 {
 215   return before_supernode (sg.get_node_for_function_entry (fun), NULL);
 216 }
 217
 218 /* Create a function_point representing entering supernode SUPERNODE,
 219    having reached it via FROM_EDGE (which could be NULL).  */
 220
 221 function_point
 222 function_point::before_supernode (const supernode *supernode,
 223                                   const superedge *from_edge)
 224 {
 225   if (from_edge && from_edge->get_kind () != SUPEREDGE_CFG_EDGE)
 226     from_edge = NULL;
 227   return function_point (supernode, from_edge, 0, PK_BEFORE_SUPERNODE);
 228 }
 229
 230 /* A subclass of diagnostic_context for use by
 231    program_point::print_source_line.  */
 232
 233 class debug_diagnostic_context : public diagnostic_context
 234 {
 235 public:
 236   debug_diagnostic_context ()
 237   {
 238     diagnostic_initialize (this, 0);
 239     show_line_numbers_p = true;
 240     show_caret = true;
 241   }
 242   ~debug_diagnostic_context ()
 243   {
 244     diagnostic_finish (this);
 245   }
 246 };
 247
 248 /* Print the source line (if any) for this function_point to PP.  */
 249
 250 void
 251 function_point::print_source_line (pretty_printer *pp) const
 252 {
 253   const gimple *stmt = get_stmt ();
 254   if (!stmt)
 255     return;
 256   // TODO: monospace font
 257   debug_diagnostic_context tmp_dc;
 258   gcc_rich_location richloc (stmt->location);
 259   diagnostic_show_locus (&tmp_dc, &richloc, DK_ERROR);
 260   pp_string (pp, pp_formatted_text (tmp_dc.printer));
 261 }
 262
 263 /* class program_point.  */
 264
 265 /* Print this program_point to PP.  */
 266
 267 void
 268 program_point::print (pretty_printer *pp, const format &f) const
 269 {
 270   pp_string (pp, "callstring: ");
 271   m_call_string.print (pp);
 272   f.spacer (pp);
 273
 274   m_function_point.print (pp, f);
 275 }
 276
 277 /* Dump this point to stderr.  */
 278
 279 DEBUG_FUNCTION void
 280 program_point::dump () const
 281 {
 282   pretty_printer pp;
 283   pp_show_color (&pp) = pp_show_color (global_dc->printer);
 284   pp.buffer->stream = stderr;
 285   print (&pp, format (true));
 286   pp_flush (&pp);
 287 }
 288
 289 /* Return a new json::object of the form
 290    {"kind"  : str,
 291     "snode_idx" : int (optional), the index of the supernode,
 292     "from_edge_snode_idx" : int (only for kind=='PK_BEFORE_SUPERNODE'),
 293     "stmt_idx": int (only for kind=='PK_BEFORE_STMT',
 294     "call_string": object for the call_string}.  */
 295
 296 json::object *
 297 program_point::to_json () const
 298 {
 299   json::object *point_obj = new json::object ();
 300
 301   point_obj->set ("kind",
 302                   new json::string (point_kind_to_string (get_kind ())));
 303
 304   if (get_supernode ())
 305     point_obj->set ("snode_idx",
 306                     new json::integer_number (get_supernode ()->m_index));
 307
 308   switch (get_kind ())
 309     {
 310     default: break;
 311     case PK_BEFORE_SUPERNODE:
 312       if (const superedge *sedge = get_from_edge ())
 313         point_obj->set ("from_edge_snode_idx",
 314                         new json::integer_number (sedge->m_src->m_index));
 315       break;
 316     case PK_BEFORE_STMT:
 317       point_obj->set ("stmt_idx", new json::integer_number (get_stmt_idx ()));
 318       break;
 319     }
 320
 321   point_obj->set ("call_string", m_call_string.to_json ());
 322
 323   return point_obj;
 324 }
 325
 326 /* Generate a hash value for this program_point.  */
 327
 328 hashval_t
 329 program_point::hash () const
 330 {
 331   inchash::hash hstate;
 332   hstate.merge_hash (m_function_point.hash ());
 333   hstate.merge_hash (m_call_string.hash ());
 334   return hstate.end ();
 335 }
 336
 337 /* Get the function * at DEPTH within the call stack.  */
 338
 339 function *
 340 program_point::get_function_at_depth (unsigned depth) const
 341 {
 342   gcc_assert (depth <= m_call_string.length ());
 343   if (depth == m_call_string.length ())
 344     return m_function_point.get_function ();
 345   else
 346     return m_call_string[depth]->get_caller_function ();
 347 }
 348
 349 /* Assert that this object is sane.  */
 350
 351 void
 352 program_point::validate () const
 353 {
 354   /* Skip this in a release build.  */
 355 #if !CHECKING_P
 356   return;
 357 #endif
 358
 359   m_call_string.validate ();
 360   /* The "callee" of the final entry in the callstring should be the
 361      function of the m_function_point.  */
 362   if (m_call_string.length () > 0)
 363     gcc_assert (m_call_string[m_call_string.length () - 1]->get_callee_function ()
 364                 == get_function ());
 365 }
 366
 367 /* Check to see if SUCC is a valid edge to take (ensuring that we have
 368    interprocedurally valid paths in the exploded graph, and enforcing
 369    recursion limits).
 370
 371    Update the call string if SUCC is a call or a return.
 372
 373    Return true if SUCC can be taken, or false otherwise.
 374
 375    This is the "point" half of exploded_node::on_edge.  */
 376
 377 bool
 378 program_point::on_edge (exploded_graph &eg,
 379                         const superedge *succ)
 380 {
 381   logger * const logger = eg.get_logger ();
 382   LOG_FUNC (logger);
 383   switch (succ->m_kind)
 384     {
 385     case SUPEREDGE_CFG_EDGE:
 386       {
 387         const cfg_superedge *cfg_sedge = as_a <const cfg_superedge *> (succ);
 388
 389         /* Reject abnormal edges; we special-case setjmp/longjmp.  */
 390         if (cfg_sedge->get_flags () & EDGE_ABNORMAL)
 391           return false;
 392       }
 393       break;
 394
 395     case SUPEREDGE_CALL:
 396       {
 397         const call_superedge *call_sedge = as_a <const call_superedge *> (succ);
 398
 399         if (eg.get_analysis_plan ().use_summary_p (call_sedge->m_cedge))
 400           {
 401             if (logger)
 402               logger->log ("rejecting call edge: using summary instead");
 403             return false;
 404           }
 405
 406         /* Add the callsite to the call string.  */
 407         m_call_string.push_call (eg.get_supergraph (), call_sedge);
 408
 409         /* Impose a maximum recursion depth and don't analyze paths
 410            that exceed it further.
 411            This is something of a blunt workaround, but it only
 412            applies to recursion (and mutual recursion), not to
 413            general call stacks.  */
 414         if (m_call_string.calc_recursion_depth ()
 415             > param_analyzer_max_recursion_depth)
 416           {
 417             if (logger)
 418               logger->log ("rejecting call edge: recursion limit exceeded");
 419             // TODO: issue a sorry for this?
 420             return false;
 421           }
 422       }
 423       break;
 424
 425     case SUPEREDGE_RETURN:
 426       {
 427         /* Require that we return to the call site in the call string.  */
 428         if (m_call_string.empty_p ())
 429           {
 430             if (logger)
 431               logger->log ("rejecting return edge: empty call string");
 432             return false;
 433           }
 434         const return_superedge *top_of_stack = m_call_string.pop ();
 435         if (top_of_stack != succ)
 436           {
 437             if (logger)
 438               logger->log ("rejecting return edge: return to wrong callsite");
 439             return false;
 440           }
 441       }
 442       break;
 443
 444     case SUPEREDGE_INTRAPROCEDURAL_CALL:
 445       {
 446         const callgraph_superedge *cg_sedge
 447           = as_a <const callgraph_superedge *> (succ);
 448         /* Consider turning this edge into a use of an
 449            interprocedural summary.  */
 450         if (eg.get_analysis_plan ().use_summary_p (cg_sedge->m_cedge))
 451           {
 452             if (logger)
 453               logger->log ("using function summary for %qE in %qE",
 454                            cg_sedge->get_callee_decl (),
 455                            cg_sedge->get_caller_decl ());
 456             return true;
 457           }
 458         else
 459           {
 460             /* Otherwise, we ignore these edges  */
 461             if (logger)
 462               logger->log ("rejecting interprocedural edge");
 463             return false;
 464           }
 465       }
 466     }
 467
 468   return true;
 469 }
 470
 471 /* Comparator for program points within the same supernode,
 472    for implementing worklist::key_t comparison operators.
 473    Return negative if POINT_A is before POINT_B
 474    Return positive if POINT_A is after POINT_B
 475    Return 0 if they are equal.  */
 476
 477 int
 478 function_point::cmp_within_supernode_1 (const function_point &point_a,
 479                                         const function_point &point_b)
 480 {
 481   gcc_assert (point_a.get_supernode () == point_b.get_supernode ());
 482
 483   switch (point_a.m_kind)
 484     {
 485     default:
 486       gcc_unreachable ();
 487     case PK_BEFORE_SUPERNODE:
 488       switch (point_b.m_kind)
 489         {
 490         default:
 491           gcc_unreachable ();
 492         case PK_BEFORE_SUPERNODE:
 493           {
 494             int a_src_idx = -1;
 495             int b_src_idx = -1;
 496             if (point_a.m_from_edge)
 497               a_src_idx = point_a.m_from_edge->m_src->m_index;
 498             if (point_b.m_from_edge)
 499               b_src_idx = point_b.m_from_edge->m_src->m_index;
 500             return a_src_idx - b_src_idx;
 501           }
 502           break;
 503
 504         case PK_BEFORE_STMT:
 505         case PK_AFTER_SUPERNODE:
 506           return -1;
 507         }
 508       break;
 509     case PK_BEFORE_STMT:
 510       switch (point_b.m_kind)
 511         {
 512         default:
 513           gcc_unreachable ();
 514         case PK_BEFORE_SUPERNODE:
 515           return 1;
 516
 517         case PK_BEFORE_STMT:
 518           return point_a.m_stmt_idx - point_b.m_stmt_idx;
 519
 520         case PK_AFTER_SUPERNODE:
 521           return -1;
 522         }
 523       break;
 524     case PK_AFTER_SUPERNODE:
 525       switch (point_b.m_kind)
 526         {
 527         default:
 528           gcc_unreachable ();
 529         case PK_BEFORE_SUPERNODE:
 530         case PK_BEFORE_STMT:
 531           return 1;
 532
 533         case PK_AFTER_SUPERNODE:
 534           return 0;
 535         }
 536       break;
 537     }
 538 }
 539
 540 /* Comparator for program points within the same supernode,
 541    for implementing worklist::key_t comparison operators.
 542    Return negative if POINT_A is before POINT_B
 543    Return positive if POINT_A is after POINT_B
 544    Return 0 if they are equal.  */
 545
 546 int
 547 function_point::cmp_within_supernode (const function_point &point_a,
 548                                       const function_point &point_b)
 549 {
 550   int result = cmp_within_supernode_1 (point_a, point_b);
 551
 552   /* Check that the ordering is symmetric  */
 553 #if CHECKING_P
 554   int reversed = cmp_within_supernode_1 (point_b, point_a);
 555   gcc_assert (reversed == -result);
 556 #endif
 557
 558   return result;
 559 }
 560
 561 /* Comparator for imposing an order on function_points.  */
 562
 563 int
 564 function_point::cmp (const function_point &point_a,
 565                      const function_point &point_b)
 566 {
 567   int idx_a = point_a.m_supernode ? point_a.m_supernode->m_index : -1;
 568   int idx_b = point_b.m_supernode ? point_b.m_supernode->m_index : -1;
 569   if (int cmp_idx = idx_a - idx_b)
 570     return cmp_idx;
 571   gcc_assert (point_a.m_supernode == point_b.m_supernode);
 572   if (point_a.m_supernode)
 573     return cmp_within_supernode (point_a, point_b);
 574   else
 575     return 0;
 576 }
 577
 578 /* Comparator for use by vec<function_point>::qsort.  */
 579
 580 int
 581 function_point::cmp_ptr (const void *p1, const void *p2)
 582 {
 583   const function_point *fp1 = (const function_point *)p1;
 584   const function_point *fp2 = (const function_point *)p2;
 585   return cmp (*fp1, *fp2);
 586 }
 587
 588 /* For PK_BEFORE_STMT, go to next stmt (or to PK_AFTER_SUPERNODE).  */
 589
 590 void
 591 function_point::next_stmt ()
 592 {
 593   gcc_assert (m_kind == PK_BEFORE_STMT);
 594   if (++m_stmt_idx == m_supernode->m_stmts.length ())
 595     {
 596       m_kind = PK_AFTER_SUPERNODE;
 597       m_stmt_idx = 0;
 598     }
 599 }
 600
 601 /* For those program points for which there is a uniquely-defined
 602    successor, return it.  */
 603
 604 program_point
 605 program_point::get_next () const
 606 {
 607   switch (m_function_point.get_kind ())
 608     {
 609     default:
 610       gcc_unreachable ();
 611     case PK_ORIGIN:
 612     case PK_AFTER_SUPERNODE:
 613       gcc_unreachable (); /* Not uniquely defined.  */
 614     case PK_BEFORE_SUPERNODE:
 615       if (get_supernode ()->m_stmts.length () > 0)
 616         return before_stmt (get_supernode (), 0, get_call_string ());
 617       else
 618         return after_supernode (get_supernode (), get_call_string ());
 619     case PK_BEFORE_STMT:
 620       {
 621         unsigned next_idx = get_stmt_idx ();
 622         if (next_idx < get_supernode ()->m_stmts.length ())
 623           return before_stmt (get_supernode (), next_idx, get_call_string ());
 624         else
 625           return after_supernode (get_supernode (), get_call_string ());
 626       }
 627     }
 628 }
 629
 630 #if CHECKING_P
 631
 632 namespace selftest {
 633
 634 /* Verify that function_point::operator== works as expected.  */
 635
 636 static void
 637 test_function_point_equality ()
 638 {
 639   const supernode *snode = NULL;
 640
 641   function_point a = function_point (snode, NULL, 0,
 642                                      PK_BEFORE_SUPERNODE);
 643   function_point b = function_point::before_supernode (snode, NULL);
 644   ASSERT_EQ (a, b);
 645 }
 646
 647 /* Verify that function_point::cmp_within_supernode works as expected.  */
 648
 649 static void
 650 test_function_point_ordering ()
 651 {
 652   const supernode *snode = NULL;
 653   const call_string call_string;
 654
 655   /* Populate an array with various points within the same
 656      snode, in order.  */
 657   auto_vec<function_point> points;
 658   points.safe_push (function_point::before_supernode (snode, NULL));
 659   points.safe_push (function_point::before_stmt (snode, 0));
 660   points.safe_push (function_point::before_stmt (snode, 1));
 661   points.safe_push (function_point::after_supernode (snode));
 662
 663   /* Check all pairs.  */
 664   unsigned i;
 665   function_point *point_a;
 666   FOR_EACH_VEC_ELT (points, i, point_a)
 667     {
 668       unsigned j;
 669       function_point *point_b;
 670       FOR_EACH_VEC_ELT (points, j, point_b)
 671         {
 672           int cmp = function_point::cmp_within_supernode (*point_a, *point_b);
 673           if (i == j)
 674             ASSERT_EQ (cmp, 0);
 675           if (i < j)
 676             ASSERT_TRUE (cmp < 0);
 677           if (i > j)
 678             ASSERT_TRUE (cmp > 0);
 679         }
 680     }
 681 }
 682
 683 /* Verify that program_point::operator== works as expected.  */
 684
 685 static void
 686 test_program_point_equality ()
 687 {
 688   const supernode *snode = NULL;
 689
 690   const call_string cs;
 691
 692   program_point a = program_point::before_supernode (snode, NULL,
 693                                                      cs);
 694
 695   program_point b = program_point::before_supernode (snode, NULL,
 696                                                      cs);
 697
 698   ASSERT_EQ (a, b);
 699   // TODO: verify with non-empty callstrings, with different edges
 700 }
 701
 702 /* Run all of the selftests within this file.  */
 703
 704 void
 705 analyzer_program_point_cc_tests ()
 706 {
 707   test_function_point_equality ();
 708   test_function_point_ordering ();
 709   test_program_point_equality ();
 710 }
 711
 712 } // namespace selftest
 713
 714 #endif /* CHECKING_P */
 715
 716 } // namespace ana
 717
 718 #endif /* #if ENABLE_ANALYZER */