blob: 25d56af3191c5ad01a6272e177130ee6e6e94241 [file] [log] [blame]
/* Classes for representing locations within the program.
Copyright (C) 2019-2021 Free Software Foundation, Inc.
Contributed by David Malcolm <dmalcolm@redhat.com>.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.
GCC is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tree.h"
#include "gimple-pretty-print.h"
#include "gcc-rich-location.h"
#include "json.h"
#include "analyzer/call-string.h"
#include "ordered-hash-map.h"
#include "options.h"
#include "cgraph.h"
#include "function.h"
#include "cfg.h"
#include "basic-block.h"
#include "gimple.h"
#include "gimple-iterator.h"
#include "digraph.h"
#include "analyzer/analyzer.h"
#include "analyzer/analyzer-logging.h"
#include "analyzer/supergraph.h"
#include "analyzer/program-point.h"
#include "sbitmap.h"
#include "bitmap.h"
#include "tristate.h"
#include "selftest.h"
#include "analyzer/store.h"
#include "analyzer/region-model.h"
#include "analyzer/sm.h"
#include "analyzer/program-state.h"
#include "alloc-pool.h"
#include "fibonacci_heap.h"
#include "diagnostic-event-id.h"
#include "analyzer/pending-diagnostic.h"
#include "analyzer/diagnostic-manager.h"
#include "shortest-paths.h"
#include "analyzer/exploded-graph.h"
#include "analyzer/analysis-plan.h"
#if ENABLE_ANALYZER
namespace ana {
/* Get a string for PK. */
const char *
point_kind_to_string (enum point_kind pk)
{
switch (pk)
{
default:
gcc_unreachable ();
case PK_ORIGIN:
return "PK_ORIGIN";
case PK_BEFORE_SUPERNODE:
return "PK_BEFORE_SUPERNODE";
case PK_BEFORE_STMT:
return "PK_BEFORE_STMT";
case PK_AFTER_SUPERNODE:
return "PK_AFTER_SUPERNODE";
case PK_EMPTY:
return "PK_EMPTY";
case PK_DELETED:
return "PK_DELETED";
}
}
/* class function_point. */
function_point::function_point (const supernode *supernode,
const superedge *from_edge,
unsigned stmt_idx,
enum point_kind kind)
: m_supernode (supernode), m_from_edge (from_edge),
m_stmt_idx (stmt_idx), m_kind (kind)
{
if (from_edge)
{
gcc_checking_assert (m_kind == PK_BEFORE_SUPERNODE);
gcc_checking_assert (from_edge->get_kind () == SUPEREDGE_CFG_EDGE);
}
if (stmt_idx)
gcc_checking_assert (m_kind == PK_BEFORE_STMT);
}
/* Print this function_point to PP. */
void
function_point::print (pretty_printer *pp, const format &f) const
{
switch (get_kind ())
{
default:
gcc_unreachable ();
case PK_ORIGIN:
pp_printf (pp, "origin");
break;
case PK_BEFORE_SUPERNODE:
{
if (m_from_edge)
{
if (basic_block bb = m_from_edge->m_src->m_bb)
pp_printf (pp, "before SN: %i (from SN: %i (bb: %i))",
m_supernode->m_index, m_from_edge->m_src->m_index,
bb->index);
else
pp_printf (pp, "before SN: %i (from SN: %i)",
m_supernode->m_index, m_from_edge->m_src->m_index);
}
else
pp_printf (pp, "before SN: %i (NULL from-edge)",
m_supernode->m_index);
f.spacer (pp);
for (gphi_iterator gpi
= const_cast<supernode *>(get_supernode ())->start_phis ();
!gsi_end_p (gpi); gsi_next (&gpi))
{
const gphi *phi = gpi.phi ();
pp_gimple_stmt_1 (pp, phi, 0, (dump_flags_t)0);
}
}
break;
case PK_BEFORE_STMT:
pp_printf (pp, "before (SN: %i stmt: %i): ", m_supernode->m_index,
m_stmt_idx);
f.spacer (pp);
pp_gimple_stmt_1 (pp, get_stmt (), 0, (dump_flags_t)0);
if (f.m_newlines)
{
pp_newline (pp);
print_source_line (pp);
}
break;
case PK_AFTER_SUPERNODE:
pp_printf (pp, "after SN: %i", m_supernode->m_index);
break;
}
}
/* Generate a hash value for this function_point. */
hashval_t
function_point::hash () const
{
inchash::hash hstate;
if (m_supernode)
hstate.add_int (m_supernode->m_index);
hstate.add_ptr (m_from_edge);
hstate.add_int (m_stmt_idx);
hstate.add_int (m_kind);
return hstate.end ();
}
/* Get the function at this point, if any. */
function *
function_point::get_function () const
{
if (m_supernode)
return m_supernode->m_fun;
else
return NULL;
}
/* Get the gimple stmt for this function_point, if any. */
const gimple *
function_point::get_stmt () const
{
if (m_kind == PK_BEFORE_STMT)
return m_supernode->m_stmts[m_stmt_idx];
else if (m_kind == PK_AFTER_SUPERNODE)
return m_supernode->get_last_stmt ();
else
return NULL;
}
/* Get a location for this function_point, if any. */
location_t
function_point::get_location () const
{
const gimple *stmt = get_stmt ();
if (stmt)
return stmt->location;
if (m_kind == PK_BEFORE_SUPERNODE)
return m_supernode->get_start_location ();
else if (m_kind == PK_AFTER_SUPERNODE)
return m_supernode->get_end_location ();
else
return UNKNOWN_LOCATION;
}
/* Create a function_point representing the entrypoint of function FUN. */
function_point
function_point::from_function_entry (const supergraph &sg, function *fun)
{
return before_supernode (sg.get_node_for_function_entry (fun), NULL);
}
/* Create a function_point representing entering supernode SUPERNODE,
having reached it via FROM_EDGE (which could be NULL). */
function_point
function_point::before_supernode (const supernode *supernode,
const superedge *from_edge)
{
if (from_edge && from_edge->get_kind () != SUPEREDGE_CFG_EDGE)
from_edge = NULL;
return function_point (supernode, from_edge, 0, PK_BEFORE_SUPERNODE);
}
/* A subclass of diagnostic_context for use by
program_point::print_source_line. */
class debug_diagnostic_context : public diagnostic_context
{
public:
debug_diagnostic_context ()
{
diagnostic_initialize (this, 0);
show_line_numbers_p = true;
show_caret = true;
}
~debug_diagnostic_context ()
{
diagnostic_finish (this);
}
};
/* Print the source line (if any) for this function_point to PP. */
void
function_point::print_source_line (pretty_printer *pp) const
{
const gimple *stmt = get_stmt ();
if (!stmt)
return;
// TODO: monospace font
debug_diagnostic_context tmp_dc;
gcc_rich_location richloc (stmt->location);
diagnostic_show_locus (&tmp_dc, &richloc, DK_ERROR);
pp_string (pp, pp_formatted_text (tmp_dc.printer));
}
/* class program_point. */
/* Print this program_point to PP. */
void
program_point::print (pretty_printer *pp, const format &f) const
{
pp_string (pp, "callstring: ");
m_call_string.print (pp);
f.spacer (pp);
m_function_point.print (pp, f);
}
/* Dump this point to stderr. */
DEBUG_FUNCTION void
program_point::dump () const
{
pretty_printer pp;
pp_show_color (&pp) = pp_show_color (global_dc->printer);
pp.buffer->stream = stderr;
print (&pp, format (true));
pp_flush (&pp);
}
/* Return a new json::object of the form
{"kind" : str,
"snode_idx" : int (optional), the index of the supernode,
"from_edge_snode_idx" : int (only for kind=='PK_BEFORE_SUPERNODE'),
"stmt_idx": int (only for kind=='PK_BEFORE_STMT',
"call_string": object for the call_string}. */
json::object *
program_point::to_json () const
{
json::object *point_obj = new json::object ();
point_obj->set ("kind",
new json::string (point_kind_to_string (get_kind ())));
if (get_supernode ())
point_obj->set ("snode_idx",
new json::integer_number (get_supernode ()->m_index));
switch (get_kind ())
{
default: break;
case PK_BEFORE_SUPERNODE:
if (const superedge *sedge = get_from_edge ())
point_obj->set ("from_edge_snode_idx",
new json::integer_number (sedge->m_src->m_index));
break;
case PK_BEFORE_STMT:
point_obj->set ("stmt_idx", new json::integer_number (get_stmt_idx ()));
break;
}
point_obj->set ("call_string", m_call_string.to_json ());
return point_obj;
}
/* Update the callstack to represent a call from caller to callee.
Generally used to push a custom call to a perticular program point
where we don't have a superedge representing the call. */
void
program_point::push_to_call_stack (const supernode *caller,
const supernode *callee)
{
m_call_string.push_call (callee, caller);
}
/* Pop the topmost call from the current callstack. */
void
program_point::pop_from_call_stack ()
{
m_call_string.pop ();
}
/* Generate a hash value for this program_point. */
hashval_t
program_point::hash () const
{
inchash::hash hstate;
hstate.merge_hash (m_function_point.hash ());
hstate.merge_hash (m_call_string.hash ());
return hstate.end ();
}
/* Get the function * at DEPTH within the call stack. */
function *
program_point::get_function_at_depth (unsigned depth) const
{
gcc_assert (depth <= m_call_string.length ());
if (depth == m_call_string.length ())
return m_function_point.get_function ();
else
return m_call_string[depth].get_caller_function ();
}
/* Assert that this object is sane. */
void
program_point::validate () const
{
/* Skip this in a release build. */
#if !CHECKING_P
return;
#endif
m_call_string.validate ();
/* The "callee" of the final entry in the callstring should be the
function of the m_function_point. */
if (m_call_string.length () > 0)
gcc_assert (m_call_string[m_call_string.length () - 1].get_callee_function ()
== get_function ());
}
/* Check to see if SUCC is a valid edge to take (ensuring that we have
interprocedurally valid paths in the exploded graph, and enforcing
recursion limits).
Update the call string if SUCC is a call or a return.
Return true if SUCC can be taken, or false otherwise.
This is the "point" half of exploded_node::on_edge. */
bool
program_point::on_edge (exploded_graph &eg,
const superedge *succ)
{
logger * const logger = eg.get_logger ();
LOG_FUNC (logger);
switch (succ->m_kind)
{
case SUPEREDGE_CFG_EDGE:
{
const cfg_superedge *cfg_sedge = as_a <const cfg_superedge *> (succ);
/* Reject abnormal edges; we special-case setjmp/longjmp. */
if (cfg_sedge->get_flags () & EDGE_ABNORMAL)
return false;
}
break;
case SUPEREDGE_CALL:
{
const call_superedge *call_sedge = as_a <const call_superedge *> (succ);
if (eg.get_analysis_plan ().use_summary_p (call_sedge->m_cedge))
{
if (logger)
logger->log ("rejecting call edge: using summary instead");
return false;
}
/* Add the callsite to the call string. */
m_call_string.push_call (eg.get_supergraph (), call_sedge);
/* Impose a maximum recursion depth and don't analyze paths
that exceed it further.
This is something of a blunt workaround, but it only
applies to recursion (and mutual recursion), not to
general call stacks. */
if (m_call_string.calc_recursion_depth ()
> param_analyzer_max_recursion_depth)
{
if (logger)
logger->log ("rejecting call edge: recursion limit exceeded");
// TODO: issue a sorry for this?
return false;
}
}
break;
case SUPEREDGE_RETURN:
{
/* Require that we return to the call site in the call string. */
if (m_call_string.empty_p ())
{
if (logger)
logger->log ("rejecting return edge: empty call string");
return false;
}
const call_string::element_t top_of_stack = m_call_string.pop ();
call_string::element_t current_call_string_element (succ->m_dest,
succ->m_src);
if (top_of_stack != current_call_string_element)
{
if (logger)
logger->log ("rejecting return edge: return to wrong callsite");
return false;
}
}
break;
case SUPEREDGE_INTRAPROCEDURAL_CALL:
{
const callgraph_superedge *cg_sedge
= as_a <const callgraph_superedge *> (succ);
/* Consider turning this edge into a use of an
interprocedural summary. */
if (eg.get_analysis_plan ().use_summary_p (cg_sedge->m_cedge))
{
if (logger)
logger->log ("using function summary for %qE in %qE",
cg_sedge->get_callee_decl (),
cg_sedge->get_caller_decl ());
return true;
}
else
{
/* Otherwise, we ignore these edges */
if (logger)
logger->log ("rejecting interprocedural edge");
return false;
}
}
}
return true;
}
/* Comparator for program points within the same supernode,
for implementing worklist::key_t comparison operators.
Return negative if POINT_A is before POINT_B
Return positive if POINT_A is after POINT_B
Return 0 if they are equal. */
int
function_point::cmp_within_supernode_1 (const function_point &point_a,
const function_point &point_b)
{
gcc_assert (point_a.get_supernode () == point_b.get_supernode ());
switch (point_a.m_kind)
{
default:
gcc_unreachable ();
case PK_BEFORE_SUPERNODE:
switch (point_b.m_kind)
{
default:
gcc_unreachable ();
case PK_BEFORE_SUPERNODE:
{
int a_src_idx = -1;
int b_src_idx = -1;
if (point_a.m_from_edge)
a_src_idx = point_a.m_from_edge->m_src->m_index;
if (point_b.m_from_edge)
b_src_idx = point_b.m_from_edge->m_src->m_index;
return a_src_idx - b_src_idx;
}
break;
case PK_BEFORE_STMT:
case PK_AFTER_SUPERNODE:
return -1;
}
break;
case PK_BEFORE_STMT:
switch (point_b.m_kind)
{
default:
gcc_unreachable ();
case PK_BEFORE_SUPERNODE:
return 1;
case PK_BEFORE_STMT:
return point_a.m_stmt_idx - point_b.m_stmt_idx;
case PK_AFTER_SUPERNODE:
return -1;
}
break;
case PK_AFTER_SUPERNODE:
switch (point_b.m_kind)
{
default:
gcc_unreachable ();
case PK_BEFORE_SUPERNODE:
case PK_BEFORE_STMT:
return 1;
case PK_AFTER_SUPERNODE:
return 0;
}
break;
}
}
/* Comparator for program points within the same supernode,
for implementing worklist::key_t comparison operators.
Return negative if POINT_A is before POINT_B
Return positive if POINT_A is after POINT_B
Return 0 if they are equal. */
int
function_point::cmp_within_supernode (const function_point &point_a,
const function_point &point_b)
{
int result = cmp_within_supernode_1 (point_a, point_b);
/* Check that the ordering is symmetric */
#if CHECKING_P
int reversed = cmp_within_supernode_1 (point_b, point_a);
gcc_assert (reversed == -result);
#endif
return result;
}
/* Comparator for imposing an order on function_points. */
int
function_point::cmp (const function_point &point_a,
const function_point &point_b)
{
int idx_a = point_a.m_supernode ? point_a.m_supernode->m_index : -1;
int idx_b = point_b.m_supernode ? point_b.m_supernode->m_index : -1;
if (int cmp_idx = idx_a - idx_b)
return cmp_idx;
gcc_assert (point_a.m_supernode == point_b.m_supernode);
if (point_a.m_supernode)
return cmp_within_supernode (point_a, point_b);
else
return 0;
}
/* Comparator for use by vec<function_point>::qsort. */
int
function_point::cmp_ptr (const void *p1, const void *p2)
{
const function_point *fp1 = (const function_point *)p1;
const function_point *fp2 = (const function_point *)p2;
return cmp (*fp1, *fp2);
}
/* For PK_BEFORE_STMT, go to next stmt (or to PK_AFTER_SUPERNODE). */
void
function_point::next_stmt ()
{
gcc_assert (m_kind == PK_BEFORE_STMT);
if (++m_stmt_idx == m_supernode->m_stmts.length ())
{
m_kind = PK_AFTER_SUPERNODE;
m_stmt_idx = 0;
}
}
/* For those program points for which there is a uniquely-defined
successor, return it. */
program_point
program_point::get_next () const
{
switch (m_function_point.get_kind ())
{
default:
gcc_unreachable ();
case PK_ORIGIN:
case PK_AFTER_SUPERNODE:
gcc_unreachable (); /* Not uniquely defined. */
case PK_BEFORE_SUPERNODE:
if (get_supernode ()->m_stmts.length () > 0)
return before_stmt (get_supernode (), 0, get_call_string ());
else
return after_supernode (get_supernode (), get_call_string ());
case PK_BEFORE_STMT:
{
unsigned next_idx = get_stmt_idx ();
if (next_idx < get_supernode ()->m_stmts.length ())
return before_stmt (get_supernode (), next_idx, get_call_string ());
else
return after_supernode (get_supernode (), get_call_string ());
}
}
}
#if CHECKING_P
namespace selftest {
/* Verify that function_point::operator== works as expected. */
static void
test_function_point_equality ()
{
const supernode *snode = NULL;
function_point a = function_point (snode, NULL, 0,
PK_BEFORE_SUPERNODE);
function_point b = function_point::before_supernode (snode, NULL);
ASSERT_EQ (a, b);
}
/* Verify that function_point::cmp_within_supernode works as expected. */
static void
test_function_point_ordering ()
{
const supernode *snode = NULL;
const call_string call_string;
/* Populate an array with various points within the same
snode, in order. */
auto_vec<function_point> points;
points.safe_push (function_point::before_supernode (snode, NULL));
points.safe_push (function_point::before_stmt (snode, 0));
points.safe_push (function_point::before_stmt (snode, 1));
points.safe_push (function_point::after_supernode (snode));
/* Check all pairs. */
unsigned i;
function_point *point_a;
FOR_EACH_VEC_ELT (points, i, point_a)
{
unsigned j;
function_point *point_b;
FOR_EACH_VEC_ELT (points, j, point_b)
{
int cmp = function_point::cmp_within_supernode (*point_a, *point_b);
if (i == j)
ASSERT_EQ (cmp, 0);
if (i < j)
ASSERT_TRUE (cmp < 0);
if (i > j)
ASSERT_TRUE (cmp > 0);
}
}
}
/* Verify that program_point::operator== works as expected. */
static void
test_program_point_equality ()
{
const supernode *snode = NULL;
const call_string cs;
program_point a = program_point::before_supernode (snode, NULL,
cs);
program_point b = program_point::before_supernode (snode, NULL,
cs);
ASSERT_EQ (a, b);
// TODO: verify with non-empty callstrings, with different edges
}
/* Run all of the selftests within this file. */
void
analyzer_program_point_cc_tests ()
{
test_function_point_equality ();
test_function_point_ordering ();
test_program_point_equality ();
}
} // namespace selftest
#endif /* CHECKING_P */
} // namespace ana
#endif /* #if ENABLE_ANALYZER */