gcc/analyzer/program-point.cc

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