blob: 0794be9a5831f6ab07db6abe79f61602c6e45fb4 [file] [log] [blame]
/* Classes for modeling the state of memory.
Copyright (C) 2019-2020 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 "function.h"
#include "basic-block.h"
#include "gimple.h"
#include "gimple-iterator.h"
#include "diagnostic-core.h"
#include "graphviz.h"
#include "options.h"
#include "cgraph.h"
#include "tree-dfa.h"
#include "stringpool.h"
#include "convert.h"
#include "target.h"
#include "fold-const.h"
#include "tree-pretty-print.h"
#include "diagnostic-color.h"
#include "diagnostic-metadata.h"
#include "tristate.h"
#include "bitmap.h"
#include "selftest.h"
#include "function.h"
#include "analyzer/analyzer.h"
#include "analyzer/analyzer-logging.h"
#include "ordered-hash-map.h"
#include "options.h"
#include "cgraph.h"
#include "cfg.h"
#include "digraph.h"
#include "analyzer/supergraph.h"
#include "sbitmap.h"
#include "analyzer/region-model.h"
#include "analyzer/constraint-manager.h"
#include "diagnostic-event-id.h"
#include "analyzer/sm.h"
#include "diagnostic-event-id.h"
#include "analyzer/sm.h"
#include "analyzer/pending-diagnostic.h"
#include "analyzer/analyzer-selftests.h"
#include "stor-layout.h"
#if ENABLE_ANALYZER
namespace ana {
/* Dump T to PP in language-independent form, for debugging/logging/dumping
purposes. */
static void
dump_tree (pretty_printer *pp, tree t)
{
dump_generic_node (pp, t, 0, TDF_SLIM, 0);
}
/* Dump T to PP in language-independent form in quotes, for
debugging/logging/dumping purposes. */
void
dump_quoted_tree (pretty_printer *pp, tree t)
{
pp_begin_quote (pp, pp_show_color (pp));
dump_tree (pp, t);
pp_end_quote (pp, pp_show_color (pp));
}
/* Equivalent to pp_printf (pp, "%qT", t), to avoid nesting pp_printf
calls within other pp_printf calls.
default_tree_printer handles 'T' and some other codes by calling
dump_generic_node (pp, t, 0, TDF_SLIM, 0);
dump_generic_node calls pp_printf in various places, leading to
garbled output.
Ideally pp_printf could be made to be reentrant, but in the meantime
this function provides a workaround. */
static void
print_quoted_type (pretty_printer *pp, tree t)
{
pp_begin_quote (pp, pp_show_color (pp));
dump_generic_node (pp, t, 0, TDF_SLIM, 0);
pp_end_quote (pp, pp_show_color (pp));
}
/* Dump this path_var to PP (which must support %E for trees).
Express the stack depth using an "@DEPTH" suffix, so e.g. given
void foo (int j);
void bar (int i)
{
foo (i);
}
then:
- the "i" in "bar" would be "(i @ 0)"
- the "j" in "foo" would be "(j @ 1)". */
void
path_var::dump (pretty_printer *pp) const
{
if (m_tree == NULL_TREE)
pp_string (pp, "NULL");
if (CONSTANT_CLASS_P (m_tree))
pp_printf (pp, "%qE", m_tree);
else
pp_printf (pp, "(%qE @ %i)", m_tree, m_stack_depth);
}
/* For use in printing a comma-separated list. */
static void
dump_separator (pretty_printer *pp, bool *is_first)
{
if (!*is_first)
pp_string (pp, ", ");
*is_first = false;
}
/* Concrete subclass of constraint_manager that wires it up to a region_model
(whilst allowing the constraint_manager and region_model to be somewhat
at arms length).
TODO: revisit this; maybe put the region_model * into the constraint_manager
base class. */
class impl_constraint_manager : public constraint_manager
{
public:
impl_constraint_manager (region_model *model)
: constraint_manager (),
m_model (model)
{}
impl_constraint_manager (const impl_constraint_manager &other,
region_model *model)
: constraint_manager (other),
m_model (model)
{}
constraint_manager *clone (region_model *model) const
{
return new impl_constraint_manager (*this, model);
}
tree maybe_get_constant (svalue_id sid) const FINAL OVERRIDE
{
svalue *svalue = m_model->get_svalue (sid);
return svalue->maybe_get_constant ();
}
svalue_id get_sid_for_constant (tree cst) const FINAL OVERRIDE
{
gcc_assert (CONSTANT_CLASS_P (cst));
return m_model->get_rvalue (cst, NULL);
}
int get_num_svalues () const FINAL OVERRIDE
{
return m_model->get_num_svalues ();
}
private:
region_model *m_model;
};
/* class svalue_id. */
/* Print this svalue_id to PP. */
void
svalue_id::print (pretty_printer *pp) const
{
if (null_p ())
pp_printf (pp, "null");
else
pp_printf (pp, "sv%i", m_idx);
}
/* Print this svalue_id in .dot format to PP. */
void
svalue_id::dump_node_name_to_pp (pretty_printer *pp) const
{
gcc_assert (!null_p ());
pp_printf (pp, "svalue_%i", m_idx);
}
/* Assert that this object is valid (w.r.t. MODEL). */
void
svalue_id::validate (const region_model &model) const
{
gcc_assert (null_p () || m_idx < (int)model.get_num_svalues ());
}
/* class region_id. */
/* Print this region_id to PP. */
void
region_id::print (pretty_printer *pp) const
{
if (null_p ())
pp_printf (pp, "null");
else
pp_printf (pp, "r%i", m_idx);
}
/* Print this region_id in .dot format to PP. */
void
region_id::dump_node_name_to_pp (pretty_printer *pp) const
{
gcc_assert (!null_p ());
pp_printf (pp, "region_%i", m_idx);
}
/* Assert that this object is valid (w.r.t. MODEL). */
void
region_id::validate (const region_model &model) const
{
gcc_assert (null_p () || m_idx < (int)model.get_num_regions ());
}
/* class region_id_set. */
region_id_set::region_id_set (const region_model *model)
: m_bitmap (model->get_num_regions ())
{
bitmap_clear (m_bitmap);
}
/* class svalue_id_set. */
svalue_id_set::svalue_id_set ()
: m_bitmap (NULL)
{
bitmap_clear (m_bitmap);
}
/* class svalue and its various subclasses. */
/* class svalue. */
/* svalue's equality operator. Most of the work is done by the
a "compare_fields" implementation on each subclass. */
bool
svalue::operator== (const svalue &other) const
{
enum svalue_kind this_kind = get_kind ();
enum svalue_kind other_kind = other.get_kind ();
if (this_kind != other_kind)
return false;
if (m_type != other.m_type)
return false;
switch (this_kind)
{
default:
gcc_unreachable ();
case SK_REGION:
{
const region_svalue &this_sub
= (const region_svalue &)*this;
const region_svalue &other_sub
= (const region_svalue &)other;
return this_sub.compare_fields (other_sub);
}
break;
case SK_CONSTANT:
{
const constant_svalue &this_sub
= (const constant_svalue &)*this;
const constant_svalue &other_sub
= (const constant_svalue &)other;
return this_sub.compare_fields (other_sub);
}
break;
case SK_UNKNOWN:
{
const unknown_svalue &this_sub
= (const unknown_svalue &)*this;
const unknown_svalue &other_sub
= (const unknown_svalue &)other;
return this_sub.compare_fields (other_sub);
}
break;
case SK_POISONED:
{
const poisoned_svalue &this_sub
= (const poisoned_svalue &)*this;
const poisoned_svalue &other_sub
= (const poisoned_svalue &)other;
return this_sub.compare_fields (other_sub);
}
break;
case SK_SETJMP:
{
const setjmp_svalue &this_sub
= (const setjmp_svalue &)*this;
const setjmp_svalue &other_sub
= (const setjmp_svalue &)other;
return this_sub.compare_fields (other_sub);
}
break;
}
}
/* Generate a hash value for this svalue. Most of the work is done by the
add_to_hash vfunc. */
hashval_t
svalue::hash () const
{
inchash::hash hstate;
if (m_type)
hstate.add_int (TYPE_UID (m_type));
add_to_hash (hstate);
return hstate.end ();
}
/* Print this svalue and its ID to PP. */
void
svalue::print (const region_model &model,
svalue_id this_sid,
pretty_printer *pp) const
{
this_sid.print (pp);
pp_string (pp, ": {");
if (m_type)
{
gcc_assert (TYPE_P (m_type));
pp_string (pp, "type: ");
print_quoted_type (pp, m_type);
pp_string (pp, ", ");
}
/* vfunc. */
print_details (model, this_sid, pp);
pp_string (pp, "}");
}
/* Dump this svalue in the form of a .dot record to PP. */
void
svalue::dump_dot_to_pp (const region_model &model,
svalue_id this_sid,
pretty_printer *pp) const
{
this_sid.dump_node_name_to_pp (pp);
pp_printf (pp, " [label=\"");
pp_write_text_to_stream (pp);
this_sid.print (pp);
pp_string (pp, ": {");
print (model, this_sid, pp);
pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
pp_string (pp, "}\"];");
pp_newline (pp);
}
/* Base implementation of svalue::remap_region_ids vfunc. */
void
svalue::remap_region_ids (const region_id_map &)
{
/* Empty. */
}
/* Base implementation of svalue::walk_for_canonicalization vfunc. */
void
svalue::walk_for_canonicalization (canonicalization *) const
{
/* Empty. */
}
/* Base implementation of svalue::get_child_sid vfunc. */
svalue_id
svalue::get_child_sid (region *parent ATTRIBUTE_UNUSED,
region *child,
region_model &model,
region_model_context *ctxt ATTRIBUTE_UNUSED)
{
svalue *new_child_value = clone ();
if (child->get_type ())
new_child_value->m_type = child->get_type ();
svalue_id new_child_sid = model.add_svalue (new_child_value);
return new_child_sid;
}
/* If this svalue is a constant_svalue, return the underlying tree constant.
Otherwise return NULL_TREE. */
tree
svalue::maybe_get_constant () const
{
if (const constant_svalue *cst_sval = dyn_cast_constant_svalue ())
return cst_sval->get_constant ();
else
return NULL_TREE;
}
/* class region_svalue : public svalue. */
/* Compare the fields of this region_svalue with OTHER, returning true
if they are equal.
For use by svalue::operator==. */
bool
region_svalue::compare_fields (const region_svalue &other) const
{
return m_rid == other.m_rid;
}
/* Implementation of svalue::add_to_hash vfunc for region_svalue. */
void
region_svalue::add_to_hash (inchash::hash &hstate) const
{
inchash::add (m_rid, hstate);
}
/* Implementation of svalue::print_details vfunc for region_svalue. */
void
region_svalue::print_details (const region_model &model ATTRIBUTE_UNUSED,
svalue_id this_sid ATTRIBUTE_UNUSED,
pretty_printer *pp) const
{
if (m_rid.null_p ())
pp_string (pp, "NULL");
else
{
pp_string (pp, "&");
m_rid.print (pp);
}
}
/* Implementation of svalue::dump_dot_to_pp for region_svalue. */
void
region_svalue::dump_dot_to_pp (const region_model &model,
svalue_id this_sid,
pretty_printer *pp) const
{
svalue::dump_dot_to_pp (model, this_sid, pp);
/* If non-NULL, add an edge to the pointed-to region. */
if (!m_rid.null_p ())
{
this_sid.dump_node_name_to_pp (pp);
pp_string (pp, " -> ");
m_rid.dump_node_name_to_pp (pp);
pp_string (pp, ";");
pp_newline (pp);
}
}
/* Implementation of svalue::remap_region_ids vfunc for region_svalue. */
void
region_svalue::remap_region_ids (const region_id_map &map)
{
map.update (&m_rid);
}
/* Merge REGION_SVAL_A and REGION_SVAL_B using MERGER, writing the result
into *MERGED_SID. */
void
region_svalue::merge_values (const region_svalue &region_sval_a,
const region_svalue &region_sval_b,
svalue_id *merged_sid,
tree type,
model_merger *merger)
{
region_id a_rid = region_sval_a.get_pointee ();
region_id b_rid = region_sval_b.get_pointee ();
/* Both are non-NULL. */
gcc_assert (!a_rid.null_p () && !b_rid.null_p ());
/* Have these ptr-values already been merged? */
region_id a_rid_in_m
= merger->m_map_regions_from_a_to_m.get_dst_for_src (a_rid);
region_id b_rid_in_m
= merger->m_map_regions_from_b_to_m.get_dst_for_src (b_rid);
/* "null_p" here means "we haven't seen this ptr-value before".
If we've seen one but not the other, or we have different
regions, then the merged ptr has to be "unknown". */
if (a_rid_in_m != b_rid_in_m)
{
svalue *merged_sval = new unknown_svalue (type);
*merged_sid = merger->m_merged_model->add_svalue (merged_sval);
return;
}
/* Have we seen this yet? If so, reuse the value. */
if (!a_rid_in_m.null_p ())
{
*merged_sid
= merger->m_merged_model->get_or_create_ptr_svalue (type, a_rid_in_m);
return;
}
/* Otherwise we have A/B regions that haven't been referenced yet. */
/* Are the regions the "same", when seen from the tree point-of-view.
If so, create a merged pointer to it. */
path_var pv_a = merger->m_model_a->get_representative_path_var (a_rid);
path_var pv_b = merger->m_model_b->get_representative_path_var (b_rid);
if (pv_a.m_tree
&& pv_a == pv_b)
{
region_id merged_pointee_rid
= merger->m_merged_model->get_lvalue (pv_a, NULL);
*merged_sid
= merger->m_merged_model->get_or_create_ptr_svalue (type,
merged_pointee_rid);
merger->record_regions (a_rid, b_rid, merged_pointee_rid);
return;
}
/* Handle an A/B pair of ptrs that both point at heap regions.
If they both have a heap region in the merger model, merge them. */
region *region_a = merger->m_model_a->get_region (a_rid);
region *region_b = merger->m_model_b->get_region (b_rid);
region_id a_parent_rid = region_a->get_parent ();
region_id b_parent_rid = region_b->get_parent ();
region *parent_region_a = merger->m_model_a->get_region (a_parent_rid);
region *parent_region_b = merger->m_model_b->get_region (b_parent_rid);
if (parent_region_a
&& parent_region_b
&& parent_region_a->get_kind () == RK_HEAP
&& parent_region_b->get_kind () == RK_HEAP)
{
/* We have an A/B pair of ptrs that both point at heap regions. */
/* presumably we want to see if each A/B heap region already
has a merged region, and, if so, is it the same one. */
// This check is above
region_id merged_pointee_rid
= merger->m_merged_model->add_new_malloc_region ();
*merged_sid
= merger->m_merged_model->get_or_create_ptr_svalue
(type, merged_pointee_rid);
merger->record_regions (a_rid, b_rid, merged_pointee_rid);
return;
}
/* Two different non-NULL pointers? Merge to unknown. */
svalue *merged_sval = new unknown_svalue (type);
*merged_sid = merger->m_merged_model->add_svalue (merged_sval);
return;
}
/* Implementation of svalue::walk_for_canonicalization vfunc for
region_svalue. */
void
region_svalue::walk_for_canonicalization (canonicalization *c) const
{
c->walk_rid (m_rid);
}
/* Evaluate the condition LHS OP RHS.
Subroutine of region_model::eval_condition for when we have a pair of
pointers. */
tristate
region_svalue::eval_condition (region_svalue *lhs,
enum tree_code op,
region_svalue *rhs)
{
/* See if they point to the same region. */
/* TODO: what about child regions where the child is the first child
(or descendent)? */
region_id lhs_rid = lhs->get_pointee ();
region_id rhs_rid = rhs->get_pointee ();
switch (op)
{
default:
gcc_unreachable ();
case EQ_EXPR:
if (lhs_rid == rhs_rid)
return tristate::TS_TRUE;
else
return tristate::TS_FALSE;
break;
case NE_EXPR:
if (lhs_rid != rhs_rid)
return tristate::TS_TRUE;
else
return tristate::TS_FALSE;
break;
case GE_EXPR:
case LE_EXPR:
if (lhs_rid == rhs_rid)
return tristate::TS_TRUE;
break;
case GT_EXPR:
case LT_EXPR:
if (lhs_rid == rhs_rid)
return tristate::TS_FALSE;
break;
}
return tristate::TS_UNKNOWN;
}
/* class constant_svalue : public svalue. */
/* Compare the fields of this constant_svalue with OTHER, returning true
if they are equal.
For use by svalue::operator==. */
bool
constant_svalue::compare_fields (const constant_svalue &other) const
{
return m_cst_expr == other.m_cst_expr;
}
/* Implementation of svalue::add_to_hash vfunc for constant_svalue. */
void
constant_svalue::add_to_hash (inchash::hash &hstate) const
{
inchash::add_expr (m_cst_expr, hstate);
}
/* Merge the CST_SVAL_A and CST_SVAL_B using MERGER, writing the id of
the resulting svalue into *MERGED_SID. */
void
constant_svalue::merge_values (const constant_svalue &cst_sval_a,
const constant_svalue &cst_sval_b,
svalue_id *merged_sid,
model_merger *merger)
{
tree cst_a = cst_sval_a.get_constant ();
tree cst_b = cst_sval_b.get_constant ();
svalue *merged_sval;
if (cst_a == cst_b)
{
/* If they are the same constant, merge as that constant value. */
merged_sval = new constant_svalue (cst_a);
}
else
{
/* Otherwise, we have two different constant values.
Merge as an unknown value.
TODO: impose constraints on the value?
(maybe just based on A, to avoid infinite chains) */
merged_sval = new unknown_svalue (TREE_TYPE (cst_a));
}
*merged_sid = merger->m_merged_model->add_svalue (merged_sval);
}
/* Evaluate the condition LHS OP RHS.
Subroutine of region_model::eval_condition for when we have a pair of
constants. */
tristate
constant_svalue::eval_condition (constant_svalue *lhs,
enum tree_code op,
constant_svalue *rhs)
{
tree lhs_const = lhs->get_constant ();
tree rhs_const = rhs->get_constant ();
gcc_assert (CONSTANT_CLASS_P (lhs_const));
gcc_assert (CONSTANT_CLASS_P (rhs_const));
/* Check for comparable types. */
if (types_compatible_p (TREE_TYPE (lhs_const), TREE_TYPE (rhs_const)))
{
tree comparison
= fold_binary (op, boolean_type_node, lhs_const, rhs_const);
if (comparison == boolean_true_node)
return tristate (tristate::TS_TRUE);
if (comparison == boolean_false_node)
return tristate (tristate::TS_FALSE);
}
return tristate::TS_UNKNOWN;
}
/* Implementation of svalue::print_details vfunc for constant_svalue. */
void
constant_svalue::print_details (const region_model &model ATTRIBUTE_UNUSED,
svalue_id this_sid ATTRIBUTE_UNUSED,
pretty_printer *pp) const
{
pp_printf (pp, "%qE", m_cst_expr);
}
/* Implementation of svalue::get_child_sid vfunc for constant_svalue. */
svalue_id
constant_svalue::get_child_sid (region *parent ATTRIBUTE_UNUSED,
region *child,
region_model &model,
region_model_context *ctxt ATTRIBUTE_UNUSED)
{
/* TODO: handle the all-zeroes case by returning an all-zeroes of the
child type. */
/* Otherwise, we don't have a good way to get a child value out of a
constant.
Handle this case by using an unknown value. */
svalue *unknown_sval = new unknown_svalue (child->get_type ());
return model.add_svalue (unknown_sval);
}
/* class unknown_svalue : public svalue. */
/* Compare the fields of this unknown_svalue with OTHER, returning true
if they are equal.
For use by svalue::operator==. */
bool
unknown_svalue::compare_fields (const unknown_svalue &) const
{
/* I *think* we want to return true here, in that when comparing
two region models, we want two peer unknown_svalue instances
to be the "same". */
return true;
}
/* Implementation of svalue::add_to_hash vfunc for unknown_svalue. */
void
unknown_svalue::add_to_hash (inchash::hash &) const
{
/* Empty. */
}
/* Implementation of svalue::print_details vfunc for unknown_svalue. */
void
unknown_svalue::print_details (const region_model &model ATTRIBUTE_UNUSED,
svalue_id this_sid ATTRIBUTE_UNUSED,
pretty_printer *pp) const
{
pp_string (pp, "unknown");
}
/* Get a string for KIND for use in debug dumps. */
const char *
poison_kind_to_str (enum poison_kind kind)
{
switch (kind)
{
default:
gcc_unreachable ();
case POISON_KIND_FREED:
return "freed";
case POISON_KIND_POPPED_STACK:
return "popped stack";
}
}
/* class poisoned_svalue : public svalue. */
/* Compare the fields of this poisoned_svalue with OTHER, returning true
if they are equal.
For use by svalue::operator==. */
bool
poisoned_svalue::compare_fields (const poisoned_svalue &other) const
{
return m_kind == other.m_kind;
}
/* Implementation of svalue::add_to_hash vfunc for poisoned_svalue. */
void
poisoned_svalue::add_to_hash (inchash::hash &hstate) const
{
hstate.add_int (m_kind);
}
/* Implementation of svalue::print_details vfunc for poisoned_svalue. */
void
poisoned_svalue::print_details (const region_model &model ATTRIBUTE_UNUSED,
svalue_id this_sid ATTRIBUTE_UNUSED,
pretty_printer *pp) const
{
pp_printf (pp, "poisoned: %s", poison_kind_to_str (m_kind));
}
/* class setjmp_svalue's implementation is in engine.cc, so that it can use
the declaration of exploded_node. */
/* class region and its various subclasses. */
/* Get a string for KIND for use in debug dumps. */
const char *
region_kind_to_str (enum region_kind kind)
{
switch (kind)
{
default:
gcc_unreachable ();
case RK_PRIMITIVE:
return "primitive";
case RK_STRUCT:
return "struct";
case RK_UNION:
return "union";
case RK_ARRAY:
return "array";
case RK_FRAME:
return "frame";
case RK_GLOBALS:
return "globals";
case RK_CODE:
return "code";
case RK_FUNCTION:
return "function";
case RK_STACK:
return "stack";
case RK_HEAP:
return "heap";
case RK_ROOT:
return "root";
case RK_SYMBOLIC:
return "symbolic";
}
}
/* class region. */
/* Equality operator for region.
After comparing base class fields and kind, the rest of the
comparison is handled off to a "compare_fields" member function
specific to the appropriate subclass. */
bool
region::operator== (const region &other) const
{
if (m_parent_rid != other.m_parent_rid)
return false;
if (m_sval_id != other.m_sval_id)
return false;
if (m_type != other.m_type)
return false;
enum region_kind this_kind = get_kind ();
enum region_kind other_kind = other.get_kind ();
if (this_kind != other_kind)
return false;
/* Compare views. */
if (m_view_rids.length () != other.m_view_rids.length ())
return false;
int i;
region_id *rid;
FOR_EACH_VEC_ELT (m_view_rids, i, rid)
if (! (*rid == other.m_view_rids[i]))
return false;
switch (this_kind)
{
default:
gcc_unreachable ();
case RK_PRIMITIVE:
{
#if 1
return true;
#else
const primitive_region &this_sub
= (const primitive_region &)*this;
const primitive_region &other_sub
= (const primitive_region &)other;
return this_sub.compare_fields (other_sub);
#endif
}
case RK_STRUCT:
{
const struct_region &this_sub
= (const struct_region &)*this;
const struct_region &other_sub
= (const struct_region &)other;
return this_sub.compare_fields (other_sub);
}
case RK_UNION:
{
const union_region &this_sub
= (const union_region &)*this;
const union_region &other_sub
= (const union_region &)other;
return this_sub.compare_fields (other_sub);
}
case RK_ARRAY:
{
const array_region &this_sub
= (const array_region &)*this;
const array_region &other_sub
= (const array_region &)other;
return this_sub.compare_fields (other_sub);
}
case RK_FRAME:
{
const frame_region &this_sub
= (const frame_region &)*this;
const frame_region &other_sub
= (const frame_region &)other;
return this_sub.compare_fields (other_sub);
}
case RK_GLOBALS:
{
const globals_region &this_sub
= (const globals_region &)*this;
const globals_region &other_sub
= (const globals_region &)other;
return this_sub.compare_fields (other_sub);
}
case RK_CODE:
{
const code_region &this_sub
= (const code_region &)*this;
const code_region &other_sub
= (const code_region &)other;
return this_sub.compare_fields (other_sub);
}
case RK_FUNCTION:
{
const function_region &this_sub
= (const function_region &)*this;
const function_region &other_sub
= (const function_region &)other;
return this_sub.compare_fields (other_sub);
}
case RK_STACK:
{
const stack_region &this_sub
= (const stack_region &)*this;
const stack_region &other_sub
= (const stack_region &)other;
return this_sub.compare_fields (other_sub);
}
case RK_ROOT:
{
const root_region &this_sub
= (const root_region &)*this;
const root_region &other_sub
= (const root_region &)other;
return this_sub.compare_fields (other_sub);
}
case RK_SYMBOLIC:
{
const symbolic_region &this_sub
= (const symbolic_region &)*this;
const symbolic_region &other_sub
= (const symbolic_region &)other;
return this_sub.compare_fields (other_sub);
}
case RK_HEAP:
{
const heap_region &this_sub
= (const heap_region &)*this;
const heap_region &other_sub
= (const heap_region &)other;
return this_sub.compare_fields (other_sub);
}
}
}
/* Get the parent region of this region. */
region *
region::get_parent_region (const region_model &model) const
{
return model.get_region (m_parent_rid);
}
/* Set this region's value to RHS_SID (or potentially a variant of it,
for some kinds of casts). */
void
region::set_value (region_model &model, region_id this_rid, svalue_id rhs_sid,
region_model_context *ctxt)
{
/* Handle some kinds of casting. */
if (m_type)
{
svalue *sval = model.get_svalue (rhs_sid);
if (sval->get_type ())
rhs_sid = model.maybe_cast (m_type, rhs_sid, ctxt);
sval = model.get_svalue (rhs_sid);
if (sval->get_type ())
gcc_assert (m_type == sval->get_type ());
}
m_sval_id = rhs_sid;
/* Update views.
If this is a view, it becomes its parent's active view.
If there was already an active views, invalidate its value; otherwise
if the parent itself had a value, invalidate it.
If it's not a view, then deactivate any view that is active on this
region. */
{
if (m_is_view)
become_active_view (model, this_rid);
else
{
deactivate_any_active_view (model);
gcc_assert (m_active_view_rid.null_p ());
}
}
}
/* Make this region (with id THIS_RID) the "active" view of its parent.
Any other active view has its value set to "unknown" and descendent values
cleared.
If there wasn't an active view, then set the parent's value to unknown, and
clear its descendent values (apart from this view). */
void
region::become_active_view (region_model &model, region_id this_rid)
{
gcc_assert (m_is_view);
region *parent_reg = model.get_region (m_parent_rid);
gcc_assert (parent_reg);
region_id old_active_view_rid = parent_reg->m_active_view_rid;
if (old_active_view_rid == this_rid)
{
/* Already the active view: do nothing. */
return;
}
/* We have a change of active view. */
parent_reg->m_active_view_rid = this_rid;
if (old_active_view_rid.null_p ())
{
/* No previous active view, but the parent and its other children
might have values.
If so, invalidate those values - but not that of the new view. */
region_id_set below_region (&model);
model.get_descendents (m_parent_rid, &below_region, this_rid);
for (unsigned i = 0; i < model.get_num_regions (); i++)
{
region_id rid (region_id::from_int (i));
if (below_region.region_p (rid))
{
region *other_reg = model.get_region (rid);
other_reg->m_sval_id = svalue_id::null ();
}
}
region *parent = model.get_region (m_parent_rid);
parent->m_sval_id
= model.add_svalue (new unknown_svalue (parent->get_type ()));
}
else
{
/* If there was an active view, invalidate it. */
region *old_active_view = model.get_region (old_active_view_rid);
old_active_view->deactivate_view (model, old_active_view_rid);
}
}
/* If this region (with id THIS_RID) has an active view, deactivate it,
clearing m_active_view_rid. */
void
region::deactivate_any_active_view (region_model &model)
{
if (m_active_view_rid.null_p ())
return;
region *view = model.get_region (m_active_view_rid);
view->deactivate_view (model, m_active_view_rid);
m_active_view_rid = region_id::null ();
}
/* Clear any values for regions below THIS_RID.
Set the view's value to unknown. */
void
region::deactivate_view (region_model &model, region_id this_view_rid)
{
gcc_assert (is_view_p ());
/* Purge values from old_active_this_view_rid and all its
descendents. Potentially we could use a poison value
for this, but let's use unknown for now. */
region_id_set below_view (&model);
model.get_descendents (this_view_rid, &below_view, region_id::null ());
for (unsigned i = 0; i < model.get_num_regions (); i++)
{
region_id rid (region_id::from_int (i));
if (below_view.region_p (rid))
{
region *other_reg = model.get_region (rid);
other_reg->m_sval_id = svalue_id::null ();
}
}
m_sval_id = model.add_svalue (new unknown_svalue (get_type ()));
}
/* Get a value for this region, either its value if it has one,
or, failing that, "inherit" a value from first ancestor with a
non-null value.
For example, when getting the value for a local variable within
a stack frame that doesn't have one, the frame doesn't have a value
either, but the stack as a whole will have an "uninitialized" poison
value, so inherit that. */
svalue_id
region::get_value (region_model &model, bool non_null,
region_model_context *ctxt)
{
/* If this region has a value, use it. */
if (!m_sval_id.null_p ())
return m_sval_id;
/* Otherwise, "inherit" value from first ancestor with a
non-null value. */
region *parent = model.get_region (m_parent_rid);
if (parent)
{
svalue_id inherited_sid
= parent->get_inherited_child_sid (this, model, ctxt);
if (!inherited_sid.null_p ())
return inherited_sid;
}
/* If a non-null value has been requested, then generate
a new unknown value. Store it, so that repeated reads from this
region will yield the same unknown value. */
if (non_null)
{
svalue_id unknown_sid = model.add_svalue (new unknown_svalue (m_type));
m_sval_id = unknown_sid;
return unknown_sid;
}
return svalue_id::null ();
}
/* Get a value for CHILD, inheriting from this region.
Recurse, so this region will inherit a value if it doesn't already
have one. */
svalue_id
region::get_inherited_child_sid (region *child,
region_model &model,
region_model_context *ctxt)
{
if (m_sval_id.null_p ())
{
/* Recurse. */
if (!m_parent_rid.null_p ())
{
region *parent = model.get_region (m_parent_rid);
m_sval_id = parent->get_inherited_child_sid (this, model, ctxt);
}
}
if (!m_sval_id.null_p ())
{
/* Clone the parent's value, so that attempts to update it
(e.g giving a specific value to an inherited "uninitialized"
value) touch the child, and not the parent. */
svalue *this_value = model.get_svalue (m_sval_id);
svalue_id new_child_sid
= this_value->get_child_sid (this, child, model, ctxt);
if (ctxt)
ctxt->on_inherited_svalue (m_sval_id, new_child_sid);
child->m_sval_id = new_child_sid;
return new_child_sid;
}
return svalue_id::null ();
}
/* Copy from SRC_RID to DST_RID, using CTXT for any issues that occur.
Copy across any value for the region, and handle structs, unions
and arrays recursively. */
void
region_model::copy_region (region_id dst_rid, region_id src_rid,
region_model_context *ctxt)
{
gcc_assert (!dst_rid.null_p ());
gcc_assert (!src_rid.null_p ());
if (dst_rid == src_rid)
return;
region *dst_reg = get_region (dst_rid);
region *src_reg = get_region (src_rid);
/* Copy across any value for the src region itself. */
svalue_id sid = src_reg->get_value (*this, true, ctxt);
set_value (dst_rid, sid, ctxt);
if (dst_reg->get_kind () != src_reg->get_kind ())
return;
/* Copy across child regions for structs, unions, and arrays. */
switch (dst_reg->get_kind ())
{
case RK_PRIMITIVE:
return;
case RK_STRUCT:
{
struct_region *dst_sub = as_a <struct_region *> (dst_reg);
struct_region *src_sub = as_a <struct_region *> (src_reg);
copy_struct_region (dst_rid, dst_sub, src_sub, ctxt);
}
return;
case RK_UNION:
{
union_region *src_sub = as_a <union_region *> (src_reg);
copy_union_region (dst_rid, src_sub, ctxt);
}
return;
case RK_FRAME:
case RK_GLOBALS:
case RK_CODE:
case RK_FUNCTION:
return;
case RK_ARRAY:
{
array_region *dst_sub = as_a <array_region *> (dst_reg);
array_region *src_sub = as_a <array_region *> (src_reg);
copy_array_region (dst_rid, dst_sub, src_sub, ctxt);
}
return;
case RK_STACK:
case RK_HEAP:
case RK_ROOT:
case RK_SYMBOLIC:
return;
}
}
/* Subroutine of region_model::copy_region for copying the child
regions for a struct. */
void
region_model::copy_struct_region (region_id dst_rid,
struct_region *dst_reg,
struct_region *src_reg,
region_model_context *ctxt)
{
for (map_region::iterator_t iter = src_reg->begin ();
iter != src_reg->end (); ++iter)
{
tree src_key = (*iter).first;
region_id src_field_rid = (*iter).second;
region *src_field_reg = get_region (src_field_rid);
region_id dst_field_rid
= dst_reg->get_or_create (this, dst_rid, src_key,
src_field_reg->get_type (), ctxt);
copy_region (dst_field_rid, src_field_rid, ctxt);
}
}
/* Subroutine of region_model::copy_region for copying the active
child region for a union. */
void
region_model::copy_union_region (region_id dst_rid,
union_region *src_reg,
region_model_context *ctxt)
{
region_id src_active_view_rid = src_reg->get_active_view ();
if (src_active_view_rid.null_p ())
return;
region *src_active_view = get_region (src_active_view_rid);
tree type = src_active_view->get_type ();
region_id dst_active_view_rid = get_or_create_view (dst_rid, type, ctxt);
copy_region (dst_active_view_rid, src_active_view_rid, ctxt);
}
/* Subroutine of region_model::copy_region for copying the child
regions for an array. */
void
region_model::copy_array_region (region_id dst_rid,
array_region *dst_reg,
array_region *src_reg,
region_model_context *ctxt)
{
for (array_region::iterator_t iter = src_reg->begin ();
iter != src_reg->end (); ++iter)
{
array_region::key_t src_key = (*iter).first;
region_id src_field_rid = (*iter).second;
region *src_field_reg = get_region (src_field_rid);
region_id dst_field_rid
= dst_reg->get_or_create (this, dst_rid, src_key,
src_field_reg->get_type (), ctxt);
copy_region (dst_field_rid, src_field_rid, ctxt);
}
}
/* Generate a hash value for this region. The work is done by the
add_to_hash vfunc. */
hashval_t
region::hash () const
{
inchash::hash hstate;
add_to_hash (hstate);
return hstate.end ();
}
/* Print a one-liner representation of this region to PP, assuming
that this region is within MODEL and its id is THIS_RID. */
void
region::print (const region_model &model,
region_id this_rid,
pretty_printer *pp) const
{
this_rid.print (pp);
pp_string (pp, ": {");
/* vfunc. */
print_fields (model, this_rid, pp);
pp_string (pp, "}");
}
/* Base class implementation of region::dump_dot_to_pp vfunc. */
void
region::dump_dot_to_pp (const region_model &model,
region_id this_rid,
pretty_printer *pp) const
{
this_rid.dump_node_name_to_pp (pp);
pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
"lightgrey");
pp_write_text_to_stream (pp);
print (model, this_rid, pp);
pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
pp_string (pp, "\"];");
pp_newline (pp);
/* Add edge to svalue. */
if (!m_sval_id.null_p ())
{
this_rid.dump_node_name_to_pp (pp);
pp_string (pp, " -> ");
m_sval_id.dump_node_name_to_pp (pp);
pp_string (pp, ";");
pp_newline (pp);
}
/* Add edge to parent. */
if (!m_parent_rid.null_p ())
{
this_rid.dump_node_name_to_pp (pp);
pp_string (pp, " -> ");
m_parent_rid.dump_node_name_to_pp (pp);
pp_string (pp, ";");
pp_newline (pp);
}
}
/* Dump a tree-like ASCII-art representation of this region to PP. */
void
region::dump_to_pp (const region_model &model,
region_id this_rid,
pretty_printer *pp,
const char *prefix,
bool is_last_child) const
{
print (model, this_rid, pp);
pp_newline (pp);
const char *new_prefix;
if (!m_parent_rid.null_p ())
new_prefix = ACONCAT ((prefix, is_last_child ? " " : "| ", NULL));
else
new_prefix = prefix;
const char *begin_color = colorize_start (pp_show_color (pp), "note");
const char *end_color = colorize_stop (pp_show_color (pp));
char *field_prefix
= ACONCAT ((begin_color, new_prefix, "|:", end_color, NULL));
if (!m_sval_id.null_p ())
{
pp_printf (pp, "%s sval: ", field_prefix);
model.get_svalue (m_sval_id)->print (model, m_sval_id, pp);
pp_newline (pp);
}
if (m_type)
{
pp_printf (pp, "%s type: ", field_prefix);
print_quoted_type (pp, m_type);
pp_newline (pp);
}
/* Find the children. */
auto_vec<region_id> child_rids;
unsigned i;
for (unsigned i = 0; i < model.get_num_regions (); ++i)
{
region_id rid = region_id::from_int (i);
region *child = model.get_region (rid);
if (child->m_parent_rid == this_rid)
child_rids.safe_push (rid);
}
/* Print the children, using dump_child_label to label them. */
region_id *child_rid;
FOR_EACH_VEC_ELT (child_rids, i, child_rid)
{
is_last_child = (i == child_rids.length () - 1);
if (!this_rid.null_p ())
{
const char *tail = is_last_child ? "`-" : "|-";
pp_printf (pp, "%r%s%s%R", "note", new_prefix, tail);
}
dump_child_label (model, this_rid, *child_rid, pp);
model.get_region (*child_rid)->dump_to_pp (model, *child_rid, pp,
new_prefix,
is_last_child);
}
}
/* Base implementation of region::dump_child_label vfunc. */
void
region::dump_child_label (const region_model &model,
region_id this_rid ATTRIBUTE_UNUSED,
region_id child_rid,
pretty_printer *pp) const
{
region *child = model.get_region (child_rid);
if (child->m_is_view)
{
gcc_assert (TYPE_P (child->get_type ()));
if (m_active_view_rid == child_rid)
pp_string (pp, "active ");
else
pp_string (pp, "inactive ");
pp_string (pp, "view as ");
print_quoted_type (pp, child->get_type ());
pp_string (pp, ": ");
}
}
/* Base implementation of region::validate vfunc.
Assert that the fields of "region" are valid; subclasses should
chain up their implementation to this one. */
void
region::validate (const region_model &model) const
{
m_parent_rid.validate (model);
m_sval_id.validate (model);
unsigned i;
region_id *view_rid;
FOR_EACH_VEC_ELT (m_view_rids, i, view_rid)
{
gcc_assert (!view_rid->null_p ());
view_rid->validate (model);
}
m_active_view_rid.validate (model);
}
/* Apply MAP to svalue_ids to this region. This updates the value
for the region (if any). */
void
region::remap_svalue_ids (const svalue_id_map &map)
{
map.update (&m_sval_id);
}
/* Base implementation of region::remap_region_ids vfunc; subclasses should
chain up to this, updating any region_id data. */
void
region::remap_region_ids (const region_id_map &map)
{
map.update (&m_parent_rid);
unsigned i;
region_id *view_rid;
FOR_EACH_VEC_ELT (m_view_rids, i, view_rid)
map.update (view_rid);
map.update (&m_active_view_rid);
}
/* Add a new region with id VIEW_RID as a view of this region. */
void
region::add_view (region_id view_rid, region_model *model)
{
gcc_assert (!view_rid.null_p ());
region *new_view = model->get_region (view_rid);
new_view->m_is_view = true;
gcc_assert (!new_view->m_parent_rid.null_p ());
gcc_assert (new_view->m_sval_id.null_p ());
//gcc_assert (new_view->get_type () != NULL_TREE);
// TODO: this can sometimes be NULL, when viewing through a (void *)
// TODO: the type ought to not be present yet
m_view_rids.safe_push (view_rid);
}
/* Look for a view of type TYPE of this region, returning its id if found,
or null otherwise. */
region_id
region::get_view (tree type, region_model *model) const
{
unsigned i;
region_id *view_rid;
FOR_EACH_VEC_ELT (m_view_rids, i, view_rid)
{
region *view = model->get_region (*view_rid);
gcc_assert (view->m_is_view);
if (view->get_type () == type)
return *view_rid;
}
return region_id::null ();
}
/* region's ctor. */
region::region (region_id parent_rid, svalue_id sval_id, tree type)
: m_parent_rid (parent_rid), m_sval_id (sval_id), m_type (type),
m_view_rids (), m_is_view (false), m_active_view_rid (region_id::null ())
{
gcc_assert (type == NULL_TREE || TYPE_P (type));
}
/* region's copy ctor. */
region::region (const region &other)
: m_parent_rid (other.m_parent_rid), m_sval_id (other.m_sval_id),
m_type (other.m_type), m_view_rids (other.m_view_rids.length ()),
m_is_view (other.m_is_view), m_active_view_rid (other.m_active_view_rid)
{
int i;
region_id *rid;
FOR_EACH_VEC_ELT (other.m_view_rids, i, rid)
m_view_rids.quick_push (*rid);
}
/* Base implementation of region::add_to_hash vfunc; subclasses should
chain up to this. */
void
region::add_to_hash (inchash::hash &hstate) const
{
inchash::add (m_parent_rid, hstate);
inchash::add (m_sval_id, hstate);
hstate.add_ptr (m_type);
// TODO: views
}
/* Base implementation of region::print_fields vfunc. */
void
region::print_fields (const region_model &model ATTRIBUTE_UNUSED,
region_id this_rid ATTRIBUTE_UNUSED,
pretty_printer *pp) const
{
pp_printf (pp, "kind: %qs", region_kind_to_str (get_kind ()));
pp_string (pp, ", parent: ");
m_parent_rid.print (pp);
pp_printf (pp, ", sval: ");
m_sval_id.print (pp);
if (m_type)
{
pp_printf (pp, ", type: ");
print_quoted_type (pp, m_type);
}
}
/* Determine if a pointer to this region must be non-NULL.
Generally, pointers to regions must be non-NULL, but pointers
to symbolic_regions might, in fact, be NULL.
This allows us to simulate functions like malloc and calloc with:
- only one "outcome" from each statement,
- the idea that the pointer is on the heap if non-NULL
- the possibility that the pointer could be NULL
- the idea that successive values returned from malloc are non-equal
- to be able to zero-fill for calloc. */
bool
region::non_null_p (const region_model &model) const
{
/* Look through views to get at the underlying region. */
if (is_view_p ())
return model.get_region (m_parent_rid)->non_null_p (model);
/* Are we within a symbolic_region? If so, it could be NULL. */
if (const symbolic_region *sym_reg = dyn_cast_symbolic_region ())
{
if (sym_reg->m_possibly_null)
return false;
}
return true;
}
/* class primitive_region : public region. */
/* Implementation of region::clone vfunc for primitive_region. */
region *
primitive_region::clone () const
{
return new primitive_region (*this);
}
/* Implementation of region::walk_for_canonicalization vfunc for
primitive_region. */
void
primitive_region::walk_for_canonicalization (canonicalization *) const
{
/* Empty. */
}
/* class map_region : public region. */
/* map_region's copy ctor. */
map_region::map_region (const map_region &other)
: region (other),
m_map (other.m_map)
{
}
/* Compare the fields of this map_region with OTHER, returning true
if they are equal.
For use by region::operator==. */
bool
map_region::compare_fields (const map_region &other) const
{
if (m_map.elements () != other.m_map.elements ())
return false;
for (map_t::iterator iter = m_map.begin ();
iter != m_map.end ();
++iter)
{
tree key = (*iter).first;
region_id e = (*iter).second;
region_id *other_slot = const_cast <map_t &> (other.m_map).get (key);
if (other_slot == NULL)
return false;
if (e != *other_slot)
return false;
}
return true;
}
/* Implementation of region::print_fields vfunc for map_region. */
void
map_region::print_fields (const region_model &model,
region_id this_rid,
pretty_printer *pp) const
{
region::print_fields (model, this_rid, pp);
pp_string (pp, ", map: {");
for (map_t::iterator iter = m_map.begin ();
iter != m_map.end ();
++iter)
{
if (iter != m_map.begin ())
pp_string (pp, ", ");
tree expr = (*iter).first;
region_id child_rid = (*iter).second;
dump_quoted_tree (pp, expr);
pp_string (pp, ": ");
child_rid.print (pp);
}
pp_string (pp, "}");
}
/* Implementation of region::validate vfunc for map_region. */
void
map_region::validate (const region_model &model) const
{
region::validate (model);
for (map_t::iterator iter = m_map.begin ();
iter != m_map.end ();
++iter)
{
region_id child_rid = (*iter).second;
child_rid.validate (model);
}
}
/* Implementation of region::dump_dot_to_pp vfunc for map_region. */
void
map_region::dump_dot_to_pp (const region_model &model,
region_id this_rid,
pretty_printer *pp) const
{
region::dump_dot_to_pp (model, this_rid, pp);
for (map_t::iterator iter = m_map.begin ();
iter != m_map.end ();
++iter)
{
// TODO: add nodes/edges to label things
tree expr = (*iter).first;
region_id child_rid = (*iter).second;
pp_printf (pp, "rid_label_%i [label=\"", child_rid.as_int ());
pp_write_text_to_stream (pp);
pp_printf (pp, "%qE", expr);
pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
pp_string (pp, "\"];");
pp_newline (pp);
pp_printf (pp, "rid_label_%i", child_rid.as_int ());
pp_string (pp, " -> ");
child_rid.dump_node_name_to_pp (pp);
pp_string (pp, ";");
pp_newline (pp);
}
}
/* Implementation of region::dump_child_label vfunc for map_region. */
void
map_region::dump_child_label (const region_model &model,
region_id this_rid,
region_id child_rid,
pretty_printer *pp) const
{
region::dump_child_label (model, this_rid, child_rid, pp);
for (map_t::iterator iter = m_map.begin ();
iter != m_map.end ();
++iter)
{
if (child_rid == (*iter).second)
{
tree key = (*iter).first;
dump_quoted_tree (pp, key);
pp_string (pp, ": ");
}
}
}
/* Look for a child region for KEY within this map_region.
If it doesn't already exist, create a child map_region, using TYPE for
its type.
Return the region_id of the child (whether pre-existing, or
newly-created).
Notify CTXT if we don't know how to handle TYPE. */
region_id
map_region::get_or_create (region_model *model,
region_id this_rid,
tree key,
tree type,
region_model_context *ctxt)
{
gcc_assert (key);
gcc_assert (valid_key_p (key));
region_id *slot = m_map.get (key);
if (slot)
return *slot;
region_id child_rid = model->add_region_for_type (this_rid, type, ctxt);
m_map.put (key, child_rid);
return child_rid;
}
/* Get the region_id for the child region for KEY within this
MAP_REGION, or NULL if there is no such child region. */
region_id *
map_region::get (tree key)
{
gcc_assert (key);
gcc_assert (valid_key_p (key));
region_id *slot = m_map.get (key);
return slot;
}
/* Implementation of region::add_to_hash vfunc for map_region. */
void
map_region::add_to_hash (inchash::hash &hstate) const
{
region::add_to_hash (hstate);
// TODO
}
/* Implementation of region::remap_region_ids vfunc for map_region. */
void
map_region::remap_region_ids (const region_id_map &map)
{
region::remap_region_ids (map);
/* Remap the region ids within the map entries. */
for (map_t::iterator iter = m_map.begin ();
iter != m_map.end (); ++iter)
map.update (&(*iter).second);
}
/* Remove the binding of KEY to its child region (but not the
child region itself).
For use when purging unneeded SSA names. */
void
map_region::unbind (tree key)
{
gcc_assert (key);
gcc_assert (valid_key_p (key));
m_map.remove (key);
}
/* Look for a child region with id CHILD_RID within this map_region.
If one is found, return its tree key, otherwise return NULL_TREE. */
tree
map_region::get_tree_for_child_region (region_id child_rid) const
{
// TODO: do we want to store an inverse map?
for (map_t::iterator iter = m_map.begin ();
iter != m_map.end ();
++iter)
{
tree key = (*iter).first;
region_id r = (*iter).second;
if (r == child_rid)
return key;
}
return NULL_TREE;
}
/* Look for a child region CHILD within this map_region.
If one is found, return its tree key, otherwise return NULL_TREE. */
tree
map_region::get_tree_for_child_region (region *child,
const region_model &model) const
{
// TODO: do we want to store an inverse map?
for (map_t::iterator iter = m_map.begin ();
iter != m_map.end ();
++iter)
{
tree key = (*iter).first;
region_id r = (*iter).second;
if (model.get_region (r) == child)
return key;
}
return NULL_TREE;
}
/* Comparator for trees to impose a deterministic ordering on
T1 and T2. */
static int
tree_cmp (const_tree t1, const_tree t2)
{
gcc_assert (t1);
gcc_assert (t2);
/* Test tree codes first. */
if (TREE_CODE (t1) != TREE_CODE (t2))
return TREE_CODE (t1) - TREE_CODE (t2);
/* From this point on, we know T1 and T2 have the same tree code. */
if (DECL_P (t1))
{
if (DECL_NAME (t1) && DECL_NAME (t2))
return strcmp (IDENTIFIER_POINTER (DECL_NAME (t1)),
IDENTIFIER_POINTER (DECL_NAME (t2)));
else
{
if (DECL_NAME (t1))
return -1;
else if (DECL_NAME (t2))
return 1;
else
return DECL_UID (t1) - DECL_UID (t2);
}
}
switch (TREE_CODE (t1))
{
case SSA_NAME:
{
if (SSA_NAME_VAR (t1) && SSA_NAME_VAR (t2))
{
int var_cmp = tree_cmp (SSA_NAME_VAR (t1), SSA_NAME_VAR (t2));
if (var_cmp)
return var_cmp;
return SSA_NAME_VERSION (t1) - SSA_NAME_VERSION (t2);
}
else
{
if (SSA_NAME_VAR (t1))
return -1;
else if (SSA_NAME_VAR (t2))
return 1;
else
return SSA_NAME_VERSION (t1) - SSA_NAME_VERSION (t2);
}
}
break;
case INTEGER_CST:
return tree_int_cst_compare (t1, t2);
case REAL_CST:
{
const real_value *rv1 = TREE_REAL_CST_PTR (t1);
const real_value *rv2 = TREE_REAL_CST_PTR (t2);
if (real_compare (UNORDERED_EXPR, rv1, rv2))
{
/* Impose an arbitrary order on NaNs relative to other NaNs
and to non-NaNs. */
if (int cmp_isnan = real_isnan (rv1) - real_isnan (rv2))
return cmp_isnan;
if (int cmp_issignaling_nan
= real_issignaling_nan (rv1) - real_issignaling_nan (rv2))
return cmp_issignaling_nan;
return real_isneg (rv1) - real_isneg (rv2);
}
if (real_compare (LT_EXPR, rv1, rv2))
return -1;
if (real_compare (GT_EXPR, rv1, rv2))
return 1;
return 0;
}
case STRING_CST:
return strcmp (TREE_STRING_POINTER (t1),
TREE_STRING_POINTER (t2));
default:
gcc_unreachable ();
break;
}
gcc_unreachable ();
return 0;
}
/* qsort comparator for trees to impose a deterministic ordering on
P1 and P2. */
static int
tree_cmp (const void *p1, const void *p2)
{
const_tree t1 = *(const_tree const *)p1;
const_tree t2 = *(const_tree const *)p2;
return tree_cmp (t1, t2);
}
/* Attempt to merge MAP_REGION_A and MAP_REGION_B into MERGED_MAP_REGION,
which has region_id MERGED_RID, using MERGER.
Return true if the merger is possible, false otherwise. */
bool
map_region::can_merge_p (const map_region *map_region_a,
const map_region *map_region_b,
map_region *merged_map_region,
region_id merged_rid,
model_merger *merger)
{
for (map_t::iterator iter = map_region_a->m_map.begin ();
iter != map_region_a->m_map.end ();
++iter)
{
tree key_a = (*iter).first;
region_id rid_a = (*iter).second;
if (const region_id *slot_b
= const_cast<map_region *>(map_region_b)->m_map.get (key_a))
{
region_id rid_b = *slot_b;
region *child_region_a = merger->get_region_a <region> (rid_a);
region *child_region_b = merger->get_region_b <region> (rid_b);
gcc_assert (child_region_a->get_type ()
== child_region_b->get_type ());
gcc_assert (child_region_a->get_kind ()
== child_region_b->get_kind ());
region_id child_merged_rid
= merged_map_region->get_or_create (merger->m_merged_model,
merged_rid,
key_a,
child_region_a->get_type (),
NULL);
region *child_merged_region
= merger->m_merged_model->get_region (child_merged_rid);
/* Consider values. */
svalue_id child_a_sid = child_region_a->get_value_direct ();
svalue_id child_b_sid = child_region_b->get_value_direct ();
svalue_id child_merged_sid;
if (!merger->can_merge_values_p (child_a_sid, child_b_sid,
&child_merged_sid))
return false;
if (!child_merged_sid.null_p ())
child_merged_region->set_value (*merger->m_merged_model,
child_merged_rid,
child_merged_sid,
NULL);
if (map_region *map_region_a = child_region_a->dyn_cast_map_region ())
{
/* Recurse. */
if (!can_merge_p (map_region_a,
as_a <map_region *> (child_region_b),
as_a <map_region *> (child_merged_region),
child_merged_rid,
merger))
return false;
}
}
else
{
/* TODO: region is present in A, but absent in B. */
}
}
/* TODO: check for keys in B that aren't in A. */
return true;
}
/* Implementation of region::walk_for_canonicalization vfunc for
map_region. */
void
map_region::walk_for_canonicalization (canonicalization *c) const
{
auto_vec<tree> keys (m_map.elements ());
for (map_t::iterator iter = m_map.begin ();
iter != m_map.end ();
++iter)
{
tree key_a = (*iter).first;
keys.quick_push (key_a);
}
keys.qsort (tree_cmp);
unsigned i;
tree key;
FOR_EACH_VEC_ELT (keys, i, key)
{
region_id rid = *const_cast<map_region *>(this)->m_map.get (key);
c->walk_rid (rid);
}
}
/* For debugging purposes: look for a child region for a decl named
IDENTIFIER (or an SSA_NAME for such a decl), returning its value,
or svalue_id::null if none are found. */
svalue_id
map_region::get_value_by_name (tree identifier,
const region_model &model) const
{
for (map_t::iterator iter = m_map.begin ();
iter != m_map.end ();
++iter)
{
tree key = (*iter).first;
if (TREE_CODE (key) == SSA_NAME)
if (SSA_NAME_VAR (key))
key = SSA_NAME_VAR (key);
if (DECL_P (key))
if (DECL_NAME (key) == identifier)
{
region_id rid = (*iter).second;
region *region = model.get_region (rid);
return region->get_value (const_cast<region_model &>(model),
false, NULL);
}
}
return svalue_id::null ();
}
/* class struct_or_union_region : public map_region. */
/* Implementation of map_region::valid_key_p vfunc for
struct_or_union_region. */
bool
struct_or_union_region::valid_key_p (tree key) const
{
return TREE_CODE (key) == FIELD_DECL;
}
/* Compare the fields of this struct_or_union_region with OTHER, returning
true if they are equal.
For use by region::operator==. */
bool
struct_or_union_region::compare_fields (const struct_or_union_region &other)
const
{
return map_region::compare_fields (other);
}
/* class struct_region : public struct_or_union_region. */
/* Implementation of region::clone vfunc for struct_region. */
region *
struct_region::clone () const
{
return new struct_region (*this);
}
/* Compare the fields of this struct_region with OTHER, returning true
if they are equal.
For use by region::operator==. */
bool
struct_region::compare_fields (const struct_region &other) const
{
return struct_or_union_region::compare_fields (other);
}
/* class union_region : public struct_or_union_region. */
/* Implementation of region::clone vfunc for union_region. */
region *
union_region::clone () const
{
return new union_region (*this);
}
/* Compare the fields of this union_region with OTHER, returning true
if they are equal.
For use by region::operator==. */
bool
union_region::compare_fields (const union_region &other) const
{
return struct_or_union_region::compare_fields (other);
}
/* class frame_region : public map_region. */
/* Compare the fields of this frame_region with OTHER, returning true
if they are equal.
For use by region::operator==. */
bool
frame_region::compare_fields (const frame_region &other) const
{
if (!map_region::compare_fields (other))
return false;
if (m_fun != other.m_fun)
return false;
if (m_depth != other.m_depth)
return false;
return true;
}
/* Implementation of region::clone vfunc for frame_region. */
region *
frame_region::clone () const
{
return new frame_region (*this);
}
/* Implementation of map_region::valid_key_p vfunc for frame_region. */
bool
frame_region::valid_key_p (tree key) const
{
// TODO: could also check that VAR_DECLs are locals
return (TREE_CODE (key) == PARM_DECL
|| TREE_CODE (key) == VAR_DECL
|| TREE_CODE (key) == SSA_NAME
|| TREE_CODE (key) == RESULT_DECL);
}
/* Implementation of region::print_fields vfunc for frame_region. */
void
frame_region::print_fields (const region_model &model,
region_id this_rid,
pretty_printer *pp) const
{
map_region::print_fields (model, this_rid, pp);
pp_printf (pp, ", function: %qs, depth: %i", function_name (m_fun), m_depth);
}
/* Implementation of region::add_to_hash vfunc for frame_region. */
void
frame_region::add_to_hash (inchash::hash &hstate) const
{
map_region::add_to_hash (hstate);
hstate.add_ptr (m_fun);
hstate.add_int (m_depth);
}
/* class globals_region : public scope_region. */
/* Compare the fields of this globals_region with OTHER, returning true
if they are equal.
For use by region::operator==. */
bool
globals_region::compare_fields (const globals_region &other) const
{
return map_region::compare_fields (other);
}
/* Implementation of region::clone vfunc for globals_region. */
region *
globals_region::clone () const
{
return new globals_region (*this);
}
/* Implementation of map_region::valid_key_p vfunc for globals_region. */
bool
globals_region::valid_key_p (tree key) const
{
return TREE_CODE (key) == VAR_DECL;
}
/* class code_region : public map_region. */
/* Compare the fields of this code_region with OTHER, returning true
if they are equal.
For use by region::operator==. */
bool
code_region::compare_fields (const code_region &other) const
{
return map_region::compare_fields (other);
}
/* Implementation of region::clone vfunc for code_region. */
region *
code_region::clone () const
{
return new code_region (*this);
}
/* Implementation of map_region::valid_key_p vfunc for code_region. */
bool
code_region::valid_key_p (tree key) const
{
return TREE_CODE (key) == FUNCTION_DECL;
}
/* class array_region : public region. */
/* array_region's copy ctor. */
array_region::array_region (const array_region &other)
: region (other),
m_map (other.m_map)
{
}
/* Get a child region for the element with index INDEX_SID. */
region_id
array_region::get_element (region_model *model,
region_id this_rid,
svalue_id index_sid,
region_model_context *ctxt)
{
tree element_type = TREE_TYPE (get_type ());
svalue *index_sval = model->get_svalue (index_sid);
if (tree cst_index = index_sval->maybe_get_constant ())
{
key_t key = key_from_constant (cst_index);
region_id element_rid
= get_or_create (model, this_rid, key, element_type, ctxt);
return element_rid;
}
return model->get_or_create_view (this_rid, element_type, ctxt);
}
/* Implementation of region::clone vfunc for array_region. */
region *
array_region::clone () const
{
return new array_region (*this);
}
/* Compare the fields of this array_region with OTHER, returning true
if they are equal.
For use by region::operator==. */
bool
array_region::compare_fields (const array_region &other) const
{
if (m_map.elements () != other.m_map.elements ())
return false;
for (map_t::iterator iter = m_map.begin ();
iter != m_map.end ();
++iter)
{
int key = (*iter).first;
region_id e = (*iter).second;
region_id *other_slot = const_cast <map_t &> (other.m_map).get (key);
if (other_slot == NULL)
return false;
if (e != *other_slot)
return false;
}
return true;
}
/* Implementation of region::print_fields vfunc for array_region. */
void
array_region::print_fields (const region_model &model,
region_id this_rid,
pretty_printer *pp) const
{
region::print_fields (model, this_rid, pp);
pp_string (pp, ", array: {");
for (map_t::iterator iter = m_map.begin ();
iter != m_map.end ();
++iter)
{
if (iter != m_map.begin ())
pp_string (pp, ", ");
int key = (*iter).first;
region_id child_rid = (*iter).second;
pp_printf (pp, "[%i]: ", key);
child_rid.print (pp);
}
pp_string (pp, "}");
}
/* Implementation of region::validate vfunc for array_region. */
void
array_region::validate (const region_model &model) const
{
region::validate (model);
for (map_t::iterator iter = m_map.begin ();
iter != m_map.end ();
++iter)
{
region_id child_rid = (*iter).second;
child_rid.validate (model);
}
}
/* Implementation of region::dump_dot_to_pp vfunc for array_region. */
void
array_region::dump_dot_to_pp (const region_model &model,
region_id this_rid,
pretty_printer *pp) const
{
region::dump_dot_to_pp (model, this_rid, pp);
for (map_t::iterator iter = m_map.begin ();
iter != m_map.end ();
++iter)
{
// TODO: add nodes/edges to label things
int key = (*iter).first;
region_id child_rid = (*iter).second;
pp_printf (pp, "rid_label_%i [label=\"", child_rid.as_int ());
pp_write_text_to_stream (pp);
pp_printf (pp, "%qi", key);
pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
pp_string (pp, "\"];");
pp_newline (pp);
pp_printf (pp, "rid_label_%i", child_rid.as_int ());
pp_string (pp, " -> ");
child_rid.dump_node_name_to_pp (pp);
pp_string (pp, ";");
pp_newline (pp);
}
}
/* Implementation of region::dump_child_label vfunc for array_region. */
void
array_region::dump_child_label (const region_model &model,
region_id this_rid,
region_id child_rid,
pretty_printer *pp) const
{
region::dump_child_label (model, this_rid, child_rid, pp);
for (map_t::iterator iter = m_map.begin ();
iter != m_map.end ();
++iter)
{
if (child_rid == (*iter).second)
{
int key = (*iter).first;
pp_printf (pp, "[%i]: ", key);
}
}
}
/* Look for a child region for KEY within this array_region.
If it doesn't already exist, create a child array_region, using TYPE for
its type.
Return the region_id of the child (whether pre-existing, or
newly-created).
Notify CTXT if we don't know how to handle TYPE. */
region_id
array_region::get_or_create (region_model *model,
region_id this_rid,
key_t key,
tree type,
region_model_context *ctxt)
{
region_id *slot = m_map.get (key);
if (slot)
return *slot;
region_id child_rid = model->add_region_for_type (this_rid, type, ctxt);
m_map.put (key, child_rid);
return child_rid;
}
/* Get the region_id for the child region for KEY within this
ARRAY_REGION, or NULL if there is no such child region. */
region_id *
array_region::get (key_t key)
{
region_id *slot = m_map.get (key);
return slot;
}
/* Implementation of region::add_to_hash vfunc for array_region. */
void
array_region::add_to_hash (inchash::hash &hstate) const
{
region::add_to_hash (hstate);
// TODO
}
/* Implementation of region::remap_region_ids vfunc for array_region. */
void
array_region::remap_region_ids (const region_id_map &map)
{
region::remap_region_ids (map);
/* Remap the region ids within the map entries. */
for (map_t::iterator iter = m_map.begin ();
iter != m_map.end (); ++iter)
map.update (&(*iter).second);
}
/* Look for a child region with id CHILD_RID within this array_region.
If one is found, write its key to *OUT and return true,
otherwise return false. */
bool
array_region::get_key_for_child_region (region_id child_rid, key_t *out) const
{
// TODO: do we want to store an inverse map?
for (map_t::iterator iter = m_map.begin ();
iter != m_map.end ();
++iter)
{
key_t key = (*iter).first;
region_id r = (*iter).second;
if (r == child_rid)
{
*out = key;
return true;
}
}
return false;
}
/* qsort comparator for array_region's keys. */
int
array_region::key_cmp (const void *p1, const void *p2)
{
key_t i1 = *(const key_t *)p1;
key_t i2 = *(const key_t *)p2;
if (i1 > i2)
return 1;
else if (i1 < i2)
return -1;
else
return 0;
}
/* Implementation of region::walk_for_canonicalization vfunc for
array_region. */
void
array_region::walk_for_canonicalization (canonicalization *c) const
{
auto_vec<int> keys (m_map.elements ());
for (map_t::iterator iter = m_map.begin ();
iter != m_map.end ();
++iter)
{
int key_a = (*iter).first;
keys.quick_push (key_a);
}
keys.qsort (key_cmp);
unsigned i;
int key;
FOR_EACH_VEC_ELT (keys, i, key)
{
region_id rid = *const_cast<array_region *>(this)->m_map.get (key);
c->walk_rid (rid);
}
}
/* Convert constant CST into an array_region::key_t. */
array_region::key_t
array_region::key_from_constant (tree cst)
{
gcc_assert (CONSTANT_CLASS_P (cst));
wide_int w = wi::to_wide (cst);
key_t result = w.to_shwi ();
return result;
}
/* Convert array_region::key_t KEY into a tree constant. */
tree
array_region::constant_from_key (key_t key)
{
tree array_type = get_type ();
tree index_type = TYPE_DOMAIN (array_type);
return build_int_cst (index_type, key);
}
/* class function_region : public map_region. */
/* Compare the fields of this function_region with OTHER, returning true
if they are equal.
For use by region::operator==. */
bool
function_region::compare_fields (const function_region &other) const
{
return map_region::compare_fields (other);
}
/* Implementation of region::clone vfunc for function_region. */
region *
function_region::clone () const
{
return new function_region (*this);
}
/* Implementation of map_region::valid_key_p vfunc for function_region. */
bool
function_region::valid_key_p (tree key) const
{
return TREE_CODE (key) == LABEL_DECL;
}
/* class stack_region : public region. */
/* stack_region's copy ctor. */
stack_region::stack_region (const stack_region &other)
: region (other),
m_frame_rids (other.m_frame_rids.length ())
{
int i;
region_id *frame_rid;
FOR_EACH_VEC_ELT (other.m_frame_rids, i, frame_rid)
m_frame_rids.quick_push (*frame_rid);
}
/* Compare the fields of this stack_region with OTHER, returning true
if they are equal.
For use by region::operator==. */
bool
stack_region::compare_fields (const stack_region &other) const
{
if (m_frame_rids.length () != other.m_frame_rids.length ())
return false;
int i;
region_id *frame_rid;
FOR_EACH_VEC_ELT (m_frame_rids, i, frame_rid)
if (m_frame_rids[i] != other.m_frame_rids[i])
return false;
return true;
}
/* Implementation of region::clone vfunc for stack_region. */
region *
stack_region::clone () const
{
return new stack_region (*this);
}
/* Implementation of region::print_fields vfunc for stack_region. */
void
stack_region::print_fields (const region_model &model,
region_id this_rid,
pretty_printer *pp) const
{
region::print_fields (model, this_rid, pp);
// TODO
}
/* Implementation of region::dump_child_label vfunc for stack_region. */
void
stack_region::dump_child_label (const region_model &model,
region_id this_rid ATTRIBUTE_UNUSED,
region_id child_rid,
pretty_printer *pp) const
{
function *fun = model.get_region<frame_region> (child_rid)->get_function ();
pp_printf (pp, "frame for %qs: ", function_name (fun));
}
/* Implementation of region::validate vfunc for stack_region. */
void
stack_region::validate (const region_model &model) const
{
region::validate (model);
int i;
region_id *frame_rid;
FOR_EACH_VEC_ELT (m_frame_rids, i, frame_rid)
m_frame_rids[i].validate (model);
}
/* Push FRAME_RID (for a frame_region) onto this stack. */
void
stack_region::push_frame (region_id frame_rid)
{
m_frame_rids.safe_push (frame_rid);
}
/* Get the region_id of the top-most frame in this stack, if any. */
region_id
stack_region::get_current_frame_id () const
{
if (m_frame_rids.length () > 0)
return m_frame_rids[m_frame_rids.length () - 1];
else
return region_id::null ();
}
/* Pop the topmost frame_region from this stack.
If RESULT_DST_RID is non-null, copy any return value from the frame
into RESULT_DST_RID's region.
Purge the frame region and all its descendent regions.
Convert any pointers that point into such regions into
POISON_KIND_POPPED_STACK svalues.
If PURGE, then purge all unused svalues, with the exception of any
returned values.
Accumulate stats on purged entities into STATS. */
void
stack_region::pop_frame (region_model *model, region_id result_dst_rid,
bool purge, purge_stats *stats,
region_model_context *ctxt)
{
gcc_assert (m_frame_rids.length () > 0);
region_id frame_rid = get_current_frame_id ();
frame_region *frame = model->get_region<frame_region> (frame_rid);
/* Evaluate the result, within the callee frame. */
svalue_id_set returned_sids;
tree fndecl = frame->get_function ()->decl;
tree result = DECL_RESULT (fndecl);
if (result && TREE_TYPE (result) != void_type_node)
{
if (!result_dst_rid.null_p ())
{
/* Copy the result to RESULT_DST_RID. */
model->copy_region (result_dst_rid, model->get_lvalue (result, ctxt),
ctxt);
}
if (purge)
{
/* Populate returned_sids, to avoid purging them. */
region_id return_rid = model->get_lvalue (result, NULL);
region_id_set returned_rids (model);
model->get_descendents (return_rid, &returned_rids,
region_id::null ());
for (unsigned i = 0; i < model->get_num_regions (); i++)
{
region_id rid = region_id::from_int (i);
if (returned_rids.region_p (rid))
{
svalue_id sid = model->get_region (rid)->get_value_direct ();
returned_sids.add_svalue (sid);
}
}
}
}
/* Pop the frame RID. */
m_frame_rids.pop ();
model->delete_region_and_descendents (frame_rid,
POISON_KIND_POPPED_STACK,
stats,
ctxt ? ctxt->get_logger () : NULL);
/* Delete unused svalues, but don't delete the return value(s). */
if (purge)
model->purge_unused_svalues (stats, ctxt, &returned_sids);
model->validate ();
}
/* Implementation of region::add_to_hash vfunc for stack_region. */
void
stack_region::add_to_hash (inchash::hash &hstate) const
{
region::add_to_hash (hstate);
int i;
region_id *frame_rid;
FOR_EACH_VEC_ELT (m_frame_rids, i, frame_rid)
inchash::add (*frame_rid, hstate);
}
/* Implementation of region::remap_region_ids vfunc for stack_region. */
void
stack_region::remap_region_ids (const region_id_map &map)
{
region::remap_region_ids (map);
int i;
region_id *frame_rid;
FOR_EACH_VEC_ELT (m_frame_rids, i, frame_rid)
map.update (&m_frame_rids[i]);
}
/* Attempt to merge STACK_REGION_A and STACK_REGION_B using MERGER.
Return true if the merger is possible, false otherwise. */
bool
stack_region::can_merge_p (const stack_region *stack_region_a,
const stack_region *stack_region_b,
model_merger *merger)
{
if (stack_region_a->get_num_frames ()
!= stack_region_b->get_num_frames ())
return false;
region_model *merged_model = merger->m_merged_model;
region_id rid_merged_stack
= merged_model->get_root_region ()->ensure_stack_region (merged_model);
stack_region *merged_stack
= merged_model->get_region <stack_region> (rid_merged_stack);
/* First, create all frames in the merged model, without populating them.
The merging code assumes that all frames in the merged model already exist,
so we have to do this first to handle the case in which a local in an
older frame points at a local in a more recent frame. */
for (unsigned i = 0; i < stack_region_a->get_num_frames (); i++)
{
region_id rid_a = stack_region_a->get_frame_rid (i);
frame_region *frame_a = merger->get_region_a <frame_region> (rid_a);
region_id rid_b = stack_region_b->get_frame_rid (i);
frame_region *frame_b = merger->get_region_b <frame_region> (rid_b);
if (frame_a->get_function () != frame_b->get_function ())
return false;
frame_region *merged_frame = new frame_region (rid_merged_stack,
frame_a->get_function (),
frame_a->get_depth ());
region_id rid_merged_frame = merged_model->add_region (merged_frame);
merged_stack->push_frame (rid_merged_frame);
}
/* Now populate the frames we created. */
for (unsigned i = 0; i < stack_region_a->get_num_frames (); i++)
{
region_id rid_a = stack_region_a->get_frame_rid (i);
frame_region *frame_a = merger->get_region_a <frame_region> (rid_a);
region_id rid_b = stack_region_b->get_frame_rid (i);
frame_region *frame_b = merger->get_region_b <frame_region> (rid_b);
region_id rid_merged_frame = merged_stack->get_frame_rid (i);
frame_region *merged_frame
= merged_model->get_region <frame_region> (rid_merged_frame);
if (!map_region::can_merge_p (frame_a, frame_b,
merged_frame, rid_merged_frame,
merger))
return false;
}
return true;
}
/* Implementation of region::walk_for_canonicalization vfunc for
stack_region. */
void
stack_region::walk_for_canonicalization (canonicalization *c) const
{
int i;
region_id *frame_rid;
FOR_EACH_VEC_ELT (m_frame_rids, i, frame_rid)
c->walk_rid (*frame_rid);
}
/* For debugging purposes: look for a grandchild region within one of
the child frame regions, where the grandchild is for a decl named
IDENTIFIER (or an SSA_NAME for such a decl):
stack_region
`-frame_region
`-region for decl named IDENTIFIER
returning its value, or svalue_id::null if none are found. */
svalue_id
stack_region::get_value_by_name (tree identifier,
const region_model &model) const
{
int i;
region_id *frame_rid;
FOR_EACH_VEC_ELT (m_frame_rids, i, frame_rid)
{
frame_region *frame = model.get_region<frame_region> (*frame_rid);
svalue_id sid = frame->get_value_by_name (identifier, model);
if (!sid.null_p ())
return sid;
}
return svalue_id::null ();
}
/* class heap_region : public region. */
/* heap_region's copy ctor. */
heap_region::heap_region (const heap_region &other)
: region (other)
{
}
/* Compare the fields of this heap_region with OTHER, returning true
if they are equal.
For use by region::operator==. */
bool
heap_region::compare_fields (const heap_region &) const
{
/* Empty. */
return true;
}
/* Implementation of region::clone vfunc for heap_region. */
region *
heap_region::clone () const
{
return new heap_region (*this);
}
/* Implementation of region::walk_for_canonicalization vfunc for
heap_region. */
void
heap_region::walk_for_canonicalization (canonicalization *) const
{
/* Empty. */
}
/* class root_region : public region. */
/* root_region's default ctor. */
root_region::root_region ()
: region (region_id::null (),
svalue_id::null (),
NULL_TREE)
{
}
/* root_region's copy ctor. */
root_region::root_region (const root_region &other)
: region (other),
m_stack_rid (other.m_stack_rid),
m_globals_rid (other.m_globals_rid),
m_code_rid (other.m_code_rid),
m_heap_rid (other.m_heap_rid)
{
}
/* Compare the fields of this root_region with OTHER, returning true
if they are equal.
For use by region::operator==. */
bool
root_region::compare_fields (const root_region &other) const
{
if (m_stack_rid != other.m_stack_rid)
return false;
if (m_globals_rid != other.m_globals_rid)
return false;
if (m_code_rid != other.m_code_rid)
return false;
if (m_heap_rid != other.m_heap_rid)
return false;
return true;
}
/* Implementation of region::clone vfunc for root_region. */
region *
root_region::clone () const
{
return new root_region (*this);
}
/* Implementation of region::print_fields vfunc for root_region. */
void
root_region::print_fields (const region_model &model,
region_id this_rid,
pretty_printer *pp) const
{
region::print_fields (model, this_rid, pp);
// TODO
}
/* Implementation of region::validate vfunc for root_region. */
void
root_region::validate (const region_model &model) const
{
region::validate (model);
m_stack_rid.validate (model);
m_globals_rid.validate (model);
m_code_rid.validate (model);
m_heap_rid.validate (model);
}
/* Implementation of region::dump_child_label vfunc for root_region. */
void
root_region::dump_child_label (const region_model &model ATTRIBUTE_UNUSED,
region_id this_rid ATTRIBUTE_UNUSED,
region_id child_rid,
pretty_printer *pp) const
{
if (child_rid == m_stack_rid)
pp_printf (pp, "stack: ");
else if (child_rid == m_globals_rid)
pp_printf (pp, "globals: ");
else if (child_rid == m_code_rid)
pp_printf (pp, "code: ");
else if (child_rid == m_heap_rid)
pp_printf (pp, "heap: ");
}
/* Create a new frame_region for a call to FUN and push it onto
the stack.
If ARG_SIDS is non-NULL, use it to populate the parameters
in the new frame.
Otherwise, populate them with unknown values.
Return the region_id of the new frame. */
region_id
root_region::push_frame (region_model *model, function *fun,
vec<svalue_id> *arg_sids,
region_model_context *ctxt)
{
gcc_assert (fun);
/* arg_sids can be NULL. */
ensure_stack_region (model);
stack_region *stack = model->get_region <stack_region> (m_stack_rid);
frame_region *region = new frame_region (m_stack_rid, fun,
stack->get_num_frames ());
region_id frame_rid = model->add_region (region);
// TODO: unify these cases by building a vec of unknown?
if (arg_sids)
{
/* Arguments supplied from a caller frame. */
tree fndecl = fun->decl;
unsigned idx = 0;
for (tree iter_parm = DECL_ARGUMENTS (fndecl); iter_parm;
iter_parm = DECL_CHAIN (iter_parm), ++idx)
{
/* If there's a mismatching declaration, the call stmt might
not have enough args. Handle this case by leaving the
rest of the params as uninitialized. */
if (idx >= arg_sids->length ())
break;
svalue_id arg_sid = (*arg_sids)[idx];
region_id parm_rid
= region->get_or_create (model, frame_rid, iter_parm,
TREE_TYPE (iter_parm), ctxt);
model->set_value (parm_rid, arg_sid, ctxt);
/* Also do it for default SSA name (sharing the same unknown
value). */
tree parm_default_ssa = ssa_default_def (fun, iter_parm);
if (parm_default_ssa)
{
region_id defssa_rid
= region->get_or_create (model, frame_rid, parm_default_ssa,
TREE_TYPE (iter_parm), ctxt);
model->set_value (defssa_rid, arg_sid, ctxt);
}
}
}
else
{
/* No known arguments (a top-level call within the analysis). */
/* Params have a defined, unknown value; they should not inherit
from the poisoned uninit value. */
tree fndecl = fun->decl;
for (tree iter_parm = DECL_ARGUMENTS (fndecl); iter_parm;
iter_parm = DECL_CHAIN (iter_parm))
{
region_id parm_rid
= region->get_or_create (model, frame_rid, iter_parm,
TREE_TYPE (iter_parm), ctxt);
svalue_id parm_sid
= model->set_to_new_unknown_value (parm_rid, TREE_TYPE (iter_parm),
ctxt);
/* Also do it for default SSA name (sharing the same unknown
value). */
tree parm_default_ssa = ssa_default_def (fun, iter_parm);
if (parm_default_ssa)
{
region_id defssa_rid
= region->get_or_create (model, frame_rid, parm_default_ssa,
TREE_TYPE (iter_parm), ctxt);
model->get_region (defssa_rid)->set_value (*model, defssa_rid,
parm_sid, ctxt);
}
}
}
stack->push_frame (frame_rid);
return frame_rid;
}
/* Get the region_id of the top-most frame in this root_region's stack,
if any. */
region_id
root_region::get_current_frame_id (const region_model &model) const
{
stack_region *stack = model.get_region <stack_region> (m_stack_rid);
if (stack)
return stack->get_current_frame_id ();
else
return region_id::null ();
}
/* Pop the topmost frame_region from this root_region's stack;
see the comment for stack_region::pop_frame. */
void
root_region::pop_frame (region_model *model, region_id result_dst_rid,
bool purge, purge_stats *out,
region_model_context *ctxt)
{
stack_region *stack = model->get_region <stack_region> (m_stack_rid);
stack->pop_frame (model, result_dst_rid, purge, out, ctxt);
}
/* Return the region_id of the stack region, creating it if doesn't
already exist. */
region_id
root_region::ensure_stack_region (region_model *model)
{
if (m_stack_rid.null_p ())
{
m_stack_rid
= model->add_region (new stack_region (model->get_root_rid (),
svalue_id::null ()));
}
return m_stack_rid;
}
/* Return the stack region (which could be NULL). */
stack_region *
root_region::get_stack_region (const region_model *model) const
{
return model->get_region <stack_region> (m_stack_rid);
}
/* Return the region_id of the globals region, creating it if doesn't
already exist. */
region_id
root_region::ensure_globals_region (region_model *model)
{
if (m_globals_rid.null_p ())
m_globals_rid
= model->add_region (new globals_region (model->get_root_rid ()));
return m_globals_rid;
}
/* Return the code region (which could be NULL). */
code_region *
root_region::get_code_region (const region_model *model) const
{
return model->get_region <code_region> (m_code_rid);
}
/* Return the region_id of the code region, creating it if doesn't
already exist. */
region_id
root_region::ensure_code_region (region_model *model)
{
if (m_code_rid.null_p ())
m_code_rid
= model->add_region (new code_region (model->get_root_rid ()));
return m_code_rid;
}
/* Return the globals region (which could be NULL). */
globals_region *
root_region::get_globals_region (const region_model *model) const
{
return model->get_region <globals_region> (m_globals_rid);
}
/* Return the region_id of the heap region, creating it if doesn't
already exist. */
region_id
root_region::ensure_heap_region (region_model *model)
{
if (m_heap_rid.null_p ())
{
m_heap_rid
= model->add_region (new heap_region (model->get_root_rid (),
svalue_id::null ()));
}
return m_heap_rid;
}
/* Return the heap region (which could be NULL). */
heap_region *
root_region::get_heap_region (const region_model *model) const
{
return model->get_region <heap_region> (m_heap_rid);
}
/* Implementation of region::remap_region_ids vfunc for root_region. */
void
root_region::remap_region_ids (const region_id_map &map)
{
map.update (&m_stack_rid);
map.update (&m_globals_rid);
map.update (&m_code_rid);
map.update (&m_heap_rid);
}
/* Attempt to merge ROOT_REGION_A and ROOT_REGION_B into
MERGED_ROOT_REGION using MERGER.
Return true if the merger is possible, false otherwise. */
bool
root_region::can_merge_p (const root_region *root_region_a,
const root_region *root_region_b,
root_region *merged_root_region,
model_merger *merger)
{
/* We can only merge if the stacks are sufficiently similar. */
stack_region *stack_a = root_region_a->get_stack_region (merger->m_model_a);
stack_region *stack_b = root_region_b->get_stack_region (merger->m_model_b);
if (stack_a && stack_b)
{
/* If the two models both have a stack, attempt to merge them. */
merged_root_region->ensure_stack_region (merger->m_merged_model);
if (!stack_region::can_merge_p (stack_a, stack_b, merger))
return false;
}
else if (stack_a || stack_b)
/* Don't attempt to merge if one model has a stack and the other
doesn't. */
return false;
map_region *globals_a = root_region_a->get_globals_region (merger->m_model_a);
map_region *globals_b = root_region_b->get_globals_region (merger->m_model_b);
if (globals_a && globals_b)
{
/* If both models have globals regions, attempt to merge them. */
region_id merged_globals_rid
= merged_root_region->ensure_globals_region (merger->m_merged_model);
map_region *merged_globals
= merged_root_region->get_globals_region (merger->m_merged_model);
if (!map_region::can_merge_p (globals_a, globals_b,
merged_globals, merged_globals_rid,
merger))
return false;
}
/* otherwise, merge as "no globals". */
map_region *code_a = root_region_a->get_code_region (merger->m_model_a);
map_region *code_b = root_region_b->get_code_region (merger->m_model_b);
if (code_a && code_b)
{
/* If both models have code regions, attempt to merge them. */
region_id merged_code_rid
= merged_root_region->ensure_code_region (merger->m_merged_model);
map_region *merged_code
= merged_root_region->get_code_region (merger->m_merged_model);
if (!map_region::can_merge_p (code_a, code_b,
merged_code, merged_code_rid,
merger))
return false;
}
/* otherwise, merge as "no code". */
heap_region *heap_a = root_region_a->get_heap_region (merger->m_model_a);
heap_region *heap_b = root_region_b->get_heap_region (merger->m_model_b);
if (heap_a && heap_b)
{
/* If both have a heap, create a "merged" heap.
Actually merging the heap contents happens via the region_svalue
instances, as needed, when seeing pairs of region_svalue instances. */
merged_root_region->ensure_heap_region (merger->m_merged_model);
}
/* otherwise, merge as "no heap". */
return true;
}
/* Implementation of region::add_to_hash vfunc for root_region. */
void
root_region::add_to_hash (inchash::hash &hstate) const
{
region::add_to_hash (hstate);
inchash::add (m_stack_rid, hstate);
inchash::add (m_globals_rid, hstate);
inchash::add (m_code_rid, hstate);
inchash::add (m_heap_rid, hstate);
}
/* Implementation of region::walk_for_canonicalization vfunc for
root_region. */
void