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