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 "analyzer/call-string.h"
  28 #include "ordered-hash-map.h"
  29 #include "options.h"
  30 #include "cgraph.h"
  31 #include "function.h"
  32 #include "cfg.h"
  33 #include "basic-block.h"
  34 #include "gimple.h"
  35 #include "gimple-iterator.h"
  36 #include "digraph.h"
  37 #include "analyzer/analyzer.h"
  38 #include "analyzer/analyzer-logging.h"
  39 #include "analyzer/supergraph.h"
  40 #include "analyzer/program-point.h"
  41 #include "sbitmap.h"
  42 #include "tristate.h"
  43 #include "selftest.h"
  44 #include "analyzer/region-model.h"
  45 #include "analyzer/sm.h"
  46 #include "analyzer/program-state.h"
  47 #include "alloc-pool.h"
  48 #include "fibonacci_heap.h"
  49 #include "diagnostic-event-id.h"
  50 #include "analyzer/pending-diagnostic.h"
  51 #include "analyzer/diagnostic-manager.h"
  52 #include "shortest-paths.h"
  53 #include "analyzer/exploded-graph.h"
  54 #include "analyzer/analysis-plan.h"
  55
  56 #if ENABLE_ANALYZER
  57
  58 namespace ana {
  59
  60 /* Get a string for PK.  */
  61
  62 const char *
  63 point_kind_to_string (enum point_kind pk)
  64 {
  65   switch (pk)
  66     {
  67     default:
  68       gcc_unreachable ();
  69     case PK_ORIGIN:
  70       return "PK_ORIGIN";
  71     case PK_BEFORE_SUPERNODE:
  72       return "PK_BEFORE_SUPERNODE";
  73     case PK_BEFORE_STMT:
  74       return "PK_BEFORE_STMT";
  75     case PK_AFTER_SUPERNODE:
  76       return "PK_AFTER_SUPERNODE";
  77     case PK_EMPTY:
  78       return "PK_EMPTY";
  79     case PK_DELETED:
  80       return "PK_DELETED";
  81     }
  82 }
  83
  84 /* class function_point.  */
  85
  86 /* Print this function_point to PP.  */
  87
  88 void
  89 function_point::print (pretty_printer *pp, const format &f) const
  90 {
  91   switch (get_kind ())
  92     {
  93     default:
  94       gcc_unreachable ();
  95
  96     case PK_ORIGIN:
  97       pp_printf (pp, "origin");
  98       break;
  99
 100     case PK_BEFORE_SUPERNODE:
 101       {
 102         if (m_from_edge)
 103           pp_printf (pp, "before SN: %i (from SN: %i)",
 104                      m_supernode->m_index, m_from_edge->m_src->m_index);
 105         else
 106           pp_printf (pp, "before SN: %i (NULL from-edge)",
 107                      m_supernode->m_index);
 108         f.spacer (pp);
 109         for (gphi_iterator gpi
 110                = const_cast<supernode *>(get_supernode ())->start_phis ();
 111              !gsi_end_p (gpi); gsi_next (&gpi))
 112           {
 113             const gphi *phi = gpi.phi ();
 114             pp_gimple_stmt_1 (pp, phi, 0, (dump_flags_t)0);
 115           }
 116       }
 117       break;
 118
 119     case PK_BEFORE_STMT:
 120       pp_printf (pp, "before (SN: %i stmt: %i): ", m_supernode->m_index,
 121                  m_stmt_idx);
 122       f.spacer (pp);
 123       pp_gimple_stmt_1 (pp, get_stmt (), 0, (dump_flags_t)0);
 124       if (f.m_newlines)
 125         {
 126           pp_newline (pp);
 127           print_source_line (pp);
 128         }
 129       break;
 130
 131     case PK_AFTER_SUPERNODE:
 132       pp_printf (pp, "after SN: %i", m_supernode->m_index);
 133       break;
 134     }
 135 }
 136
 137 /* Generate a hash value for this function_point.  */
 138
 139 hashval_t
 140 function_point::hash () const
 141 {
 142   inchash::hash hstate;
 143   if (m_supernode)
 144     hstate.add_int (m_supernode->m_index);
 145   hstate.add_ptr (m_from_edge);
 146   hstate.add_int (m_stmt_idx);
 147   hstate.add_int (m_kind);
 148   return hstate.end ();
 149 }
 150
 151 /* Get the gimple stmt for this function_point, if any.  */
 152
 153 const gimple *
 154 function_point::get_stmt () const
 155 {
 156   if (m_kind == PK_BEFORE_STMT)
 157     return m_supernode->m_stmts[m_stmt_idx];
 158   else if (m_kind == PK_AFTER_SUPERNODE)
 159     return m_supernode->get_last_stmt ();
 160   else
 161     return NULL;
 162 }
 163
 164 /* Get a location for this function_point, if any.  */
 165
 166 location_t
 167 function_point::get_location () const
 168 {
 169   const gimple *stmt = get_stmt ();
 170   if (stmt)
 171     return stmt->location;
 172
 173   return UNKNOWN_LOCATION;
 174 }
 175
 176 /* A subclass of diagnostic_context for use by
 177    program_point::print_source_line.  */
 178
 179 class debug_diagnostic_context : public diagnostic_context
 180 {
 181 public:
 182   debug_diagnostic_context ()
 183   {
 184     diagnostic_initialize (this, 0);
 185     show_line_numbers_p = true;
 186     show_caret = true;
 187   }
 188   ~debug_diagnostic_context ()
 189   {
 190     diagnostic_finish (this);
 191   }
 192 };
 193
 194 /* Print the source line (if any) for this function_point to PP.  */
 195
 196 void
 197 function_point::print_source_line (pretty_printer *pp) const
 198 {
 199   const gimple *stmt = get_stmt ();
 200   if (!stmt)
 201     return;
 202   // TODO: monospace font
 203   debug_diagnostic_context tmp_dc;
 204   gcc_rich_location richloc (stmt->location);
 205   diagnostic_show_locus (&tmp_dc, &richloc, DK_ERROR);
 206   pp_string (pp, pp_formatted_text (tmp_dc.printer));
 207 }
 208
 209 /* class program_point.  */
 210
 211 /* Print this program_point to PP.  */
 212
 213 void
 214 program_point::print (pretty_printer *pp, const format &f) const
 215 {
 216   pp_string (pp, "callstring: ");
 217   m_call_string.print (pp);
 218   f.spacer (pp);
 219
 220   m_function_point.print (pp, f);
 221 }
 222
 223 /* Dump this point to stderr.  */
 224
 225 DEBUG_FUNCTION void
 226 program_point::dump () const
 227 {
 228   pretty_printer pp;
 229   pp_show_color (&pp) = pp_show_color (global_dc->printer);
 230   pp.buffer->stream = stderr;
 231   print (&pp, format (true));
 232   pp_flush (&pp);
 233 }
 234
 235 /* Generate a hash value for this program_point.  */
 236
 237 hashval_t
 238 program_point::hash () const
 239 {
 240   inchash::hash hstate;
 241   hstate.merge_hash (m_function_point.hash ());
 242   hstate.merge_hash (m_call_string.hash ());
 243   return hstate.end ();
 244 }
 245
 246 /* Get the function * at DEPTH within the call stack.  */
 247
 248 function *
 249 program_point::get_function_at_depth (unsigned depth) const
 250 {
 251   gcc_assert (depth <= m_call_string.length ());
 252   if (depth == m_call_string.length ())
 253     return m_function_point.get_function ();
 254   else
 255     return m_call_string[depth]->get_caller_function ();
 256 }
 257
 258 /* Assert that this object is sane.  */
 259
 260 void
 261 program_point::validate () const
 262 {
 263   /* Skip this in a release build.  */
 264 #if !CHECKING_P
 265   return;
 266 #endif
 267
 268   m_call_string.validate ();
 269   /* The "callee" of the final entry in the callstring should be the
 270      function of the m_function_point.  */
 271   if (m_call_string.length () > 0)
 272     gcc_assert (m_call_string[m_call_string.length () - 1]->get_callee_function ()
 273                 == get_function ());
 274 }
 275
 276 /* Check to see if SUCC is a valid edge to take (ensuring that we have
 277    interprocedurally valid paths in the exploded graph, and enforcing
 278    recursion limits).
 279
 280    Update the call string if SUCC is a call or a return.
 281
 282    Return true if SUCC can be taken, or false otherwise.
 283
 284    This is the "point" half of exploded_node::on_edge.  */
 285
 286 bool
 287 program_point::on_edge (exploded_graph &eg,
 288                         const superedge *succ)
 289 {
 290   logger * const logger = eg.get_logger ();
 291   LOG_FUNC (logger);
 292   switch (succ->m_kind)
 293     {
 294     case SUPEREDGE_CFG_EDGE:
 295       {
 296         const cfg_superedge *cfg_sedge = as_a <const cfg_superedge *> (succ);
 297
 298         /* Reject abnormal edges; we special-case setjmp/longjmp.  */
 299         if (cfg_sedge->get_flags () & EDGE_ABNORMAL)
 300           return false;
 301       }
 302       break;
 303
 304     case SUPEREDGE_CALL:
 305       {
 306         const call_superedge *call_sedge = as_a <const call_superedge *> (succ);
 307
 308         if (eg.get_analysis_plan ().use_summary_p (call_sedge->m_cedge))
 309           {
 310             if (logger)
 311               logger->log ("rejecting call edge: using summary instead");
 312             return false;
 313           }
 314
 315         /* Add the callsite to the call string.  */
 316         m_call_string.push_call (eg.get_supergraph (), call_sedge);
 317
 318         /* Impose a maximum recursion depth and don't analyze paths
 319            that exceed it further.
 320            This is something of a blunt workaround, but it only
 321            applies to recursion (and mutual recursion), not to
 322            general call stacks.  */
 323         if (m_call_string.calc_recursion_depth ()
 324             > param_analyzer_max_recursion_depth)
 325           {
 326             if (logger)
 327               logger->log ("rejecting call edge: recursion limit exceeded");
 328             // TODO: issue a sorry for this?
 329             return false;
 330           }
 331       }
 332       break;
 333
 334     case SUPEREDGE_RETURN:
 335       {
 336         /* Require that we return to the call site in the call string.  */
 337         if (m_call_string.empty_p ())
 338           {
 339             if (logger)
 340               logger->log ("rejecting return edge: empty call string");
 341             return false;
 342           }
 343         const return_superedge *top_of_stack = m_call_string.pop ();
 344         if (top_of_stack != succ)
 345           {
 346             if (logger)
 347               logger->log ("rejecting return edge: return to wrong callsite");
 348             return false;
 349           }
 350       }
 351       break;
 352
 353     case SUPEREDGE_INTRAPROCEDURAL_CALL:
 354       {
 355         const callgraph_superedge *cg_sedge
 356           = as_a <const callgraph_superedge *> (succ);
 357         /* Consider turning this edge into a use of an
 358            interprocedural summary.  */
 359         if (eg.get_analysis_plan ().use_summary_p (cg_sedge->m_cedge))
 360           {
 361             if (logger)
 362               logger->log ("using function summary for %qE in %qE",
 363                            cg_sedge->get_callee_decl (),
 364                            cg_sedge->get_caller_decl ());
 365             return true;
 366           }
 367         else
 368           {
 369             /* Otherwise, we ignore these edges  */
 370             if (logger)
 371               logger->log ("rejecting interprocedural edge");
 372             return false;
 373           }
 374       }
 375     }
 376
 377   return true;
 378 }
 379
 380 /* Comparator for program points within the same supernode,
 381    for implementing worklist::key_t comparison operators.
 382    Return negative if POINT_A is before POINT_B
 383    Return positive if POINT_A is after POINT_B
 384    Return 0 if they are equal.  */
 385
 386 int
 387 function_point::cmp_within_supernode_1 (const function_point &point_a,
 388                                         const function_point &point_b)
 389 {
 390   gcc_assert (point_a.get_supernode () == point_b.get_supernode ());
 391
 392   switch (point_a.m_kind)
 393     {
 394     default:
 395       gcc_unreachable ();
 396     case PK_BEFORE_SUPERNODE:
 397       switch (point_b.m_kind)
 398         {
 399         default:
 400           gcc_unreachable ();
 401         case PK_BEFORE_SUPERNODE:
 402           {
 403             int a_src_idx = -1;
 404             int b_src_idx = -1;
 405             if (point_a.m_from_edge)
 406               a_src_idx = point_a.m_from_edge->m_src->m_index;
 407             if (point_b.m_from_edge)
 408               b_src_idx = point_b.m_from_edge->m_src->m_index;
 409             return a_src_idx - b_src_idx;
 410           }
 411           break;
 412
 413         case PK_BEFORE_STMT:
 414         case PK_AFTER_SUPERNODE:
 415           return -1;
 416         }
 417       break;
 418     case PK_BEFORE_STMT:
 419       switch (point_b.m_kind)
 420         {
 421         default:
 422           gcc_unreachable ();
 423         case PK_BEFORE_SUPERNODE:
 424           return 1;
 425
 426         case PK_BEFORE_STMT:
 427           return point_a.m_stmt_idx - point_b.m_stmt_idx;
 428
 429         case PK_AFTER_SUPERNODE:
 430           return -1;
 431         }
 432       break;
 433     case PK_AFTER_SUPERNODE:
 434       switch (point_b.m_kind)
 435         {
 436         default:
 437           gcc_unreachable ();
 438         case PK_BEFORE_SUPERNODE:
 439         case PK_BEFORE_STMT:
 440           return 1;
 441
 442         case PK_AFTER_SUPERNODE:
 443           return 0;
 444         }
 445       break;
 446     }
 447 }
 448
 449 /* Comparator for program points within the same supernode,
 450    for implementing worklist::key_t comparison operators.
 451    Return negative if POINT_A is before POINT_B
 452    Return positive if POINT_A is after POINT_B
 453    Return 0 if they are equal.  */
 454
 455 int
 456 function_point::cmp_within_supernode (const function_point &point_a,
 457                                       const function_point &point_b)
 458 {
 459   int result = cmp_within_supernode_1 (point_a, point_b);
 460
 461   /* Check that the ordering is symmetric  */
 462 #if CHECKING_P
 463   int reversed = cmp_within_supernode_1 (point_b, point_a);
 464   gcc_assert (reversed == -result);
 465 #endif
 466
 467   return result;
 468 }
 469
 470 #if CHECKING_P
 471
 472 namespace selftest {
 473
 474 /* Verify that function_point::operator== works as expected.  */
 475
 476 static void
 477 test_function_point_equality ()
 478 {
 479   const supernode *snode = NULL;
 480
 481   function_point a = function_point (snode, NULL, 0,
 482                                      PK_BEFORE_SUPERNODE);
 483   function_point b = function_point::before_supernode (snode, NULL);
 484   ASSERT_EQ (a, b);
 485 }
 486
 487 /* Verify that function_point::cmp_within_supernode works as expected.  */
 488
 489 static void
 490 test_function_point_ordering ()
 491 {
 492   const supernode *snode = NULL;
 493   const call_string call_string;
 494
 495   /* Populate an array with various points within the same
 496      snode, in order.  */
 497   auto_vec<function_point> points;
 498   points.safe_push (function_point::before_supernode (snode, NULL));
 499   points.safe_push (function_point::before_stmt (snode, 0));
 500   points.safe_push (function_point::before_stmt (snode, 1));
 501   points.safe_push (function_point::after_supernode (snode));
 502
 503   /* Check all pairs.  */
 504   unsigned i;
 505   function_point *point_a;
 506   FOR_EACH_VEC_ELT (points, i, point_a)
 507     {
 508       unsigned j;
 509       function_point *point_b;
 510       FOR_EACH_VEC_ELT (points, j, point_b)
 511         {
 512           int cmp = function_point::cmp_within_supernode (*point_a, *point_b);
 513           if (i == j)
 514             ASSERT_EQ (cmp, 0);
 515           if (i < j)
 516             ASSERT_TRUE (cmp < 0);
 517           if (i > j)
 518             ASSERT_TRUE (cmp > 0);
 519         }
 520     }
 521 }
 522
 523 /* Verify that program_point::operator== works as expected.  */
 524
 525 static void
 526 test_program_point_equality ()
 527 {
 528   const supernode *snode = NULL;
 529
 530   const call_string cs;
 531
 532   program_point a = program_point::before_supernode (snode, NULL,
 533                                                      cs);
 534
 535   program_point b = program_point::before_supernode (snode, NULL,
 536                                                      cs);
 537
 538   ASSERT_EQ (a, b);
 539   // TODO: verify with non-empty callstrings, with different edges
 540 }
 541
 542 /* Run all of the selftests within this file.  */
 543
 544 void
 545 analyzer_program_point_cc_tests ()
 546 {
 547   test_function_point_equality ();
 548   test_function_point_ordering ();
 549   test_program_point_equality ();
 550 }
 551
 552 } // namespace selftest
 553
 554 #endif /* CHECKING_P */
 555
 556 } // namespace ana
 557
 558 #endif /* #if ENABLE_ANALYZER */