/* Tree based points-to analysis
- Copyright (C) 2005-2019 Free Software Foundation, Inc.
+ Copyright (C) 2005-2020 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dberlin@dberlin.org>
This file is part of GCC.
#include "gimple-iterator.h"
#include "tree-into-ssa.h"
#include "tree-dfa.h"
-#include "params.h"
#include "gimple-walk.h"
#include "varasm.h"
#include "stringpool.h"
as a consequence.
See "Efficient Field-sensitive pointer analysis for C" by "David
- J. Pearce and Paul H. J. Kelly and Chris Hankin, at
+ J. Pearce and Paul H. J. Kelly and Chris Hankin", at
http://citeseer.ist.psu.edu/pearce04efficient.html
Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
- of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
+ of C Code in a Second" by "Nevin Heintze and Olivier Tardieu" at
http://citeseer.ist.psu.edu/heintze01ultrafast.html
There are three types of real constraint expressions, DEREF,
Each variable for a structure field has
1. "size", that tells the size in bits of that field.
- 2. "fullsize, that tells the size in bits of the entire structure.
+ 2. "fullsize", that tells the size in bits of the entire structure.
3. "offset", that tells the offset in bits from the beginning of the
structure to this field.
We probably should compute a per-function unit-ESCAPE solution
propagating it simply like the clobber / uses solutions. The
- solution can go alongside the non-IPA espaced solution and be
+ solution can go alongside the non-IPA escaped solution and be
used to query which vars escape the unit through a function.
This is also required to make the escaped-HEAP trick work in IPA mode.
number 1, pages 9-14. */
static void
-scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
+scc_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
{
unsigned int i;
bitmap_iterator bi;
/* Equiv_class_label hashtable helpers. */
-struct equiv_class_hasher : free_ptr_hash <equiv_class_label>
+struct equiv_class_hasher : nofree_ptr_hash <equiv_class_label>
{
static inline hashval_t hash (const equiv_class_label *);
static inline bool equal (const equiv_class_label *,
classes. */
static hash_table<equiv_class_hasher> *location_equiv_class_table;
+struct obstack equiv_class_obstack;
+
/* Lookup a equivalence class in TABLE by the bitmap of LABELS with
hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS
is equivalent to. */
slot = table->find_slot (&ecl, INSERT);
if (!*slot)
{
- *slot = XNEW (struct equiv_class_label);
+ *slot = XOBNEW (&equiv_class_obstack, struct equiv_class_label);
(*slot)->labels = labels;
(*slot)->hashcode = ecl.hashcode;
(*slot)->equivalence_class = 0;
and label it's nodes with DFS numbers. */
static void
-condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
+condense_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
{
unsigned int i;
bitmap_iterator bi;
/* See if any components have been identified. */
if (si->dfs[n] == my_dfs)
{
- while (si->scc_stack.length () != 0
- && si->dfs[si->scc_stack.last ()] >= my_dfs)
+ if (si->scc_stack.length () != 0
+ && si->dfs[si->scc_stack.last ()] >= my_dfs)
{
- unsigned int w = si->scc_stack.pop ();
- si->node_mapping[w] = n;
-
- if (!bitmap_bit_p (graph->direct_nodes, w))
- bitmap_clear_bit (graph->direct_nodes, n);
-
- /* Unify our nodes. */
- if (graph->preds[w])
- {
- if (!graph->preds[n])
- graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
- bitmap_ior_into (graph->preds[n], graph->preds[w]);
- }
- if (graph->implicit_preds[w])
+ /* Find the first node of the SCC and do non-bitmap work. */
+ bool direct_p = true;
+ unsigned first = si->scc_stack.length ();
+ do
{
- if (!graph->implicit_preds[n])
- graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
- bitmap_ior_into (graph->implicit_preds[n],
- graph->implicit_preds[w]);
+ --first;
+ unsigned int w = si->scc_stack[first];
+ si->node_mapping[w] = n;
+ if (!bitmap_bit_p (graph->direct_nodes, w))
+ direct_p = false;
}
- if (graph->points_to[w])
+ while (first > 0
+ && si->dfs[si->scc_stack[first - 1]] >= my_dfs);
+ if (!direct_p)
+ bitmap_clear_bit (graph->direct_nodes, n);
+
+ /* Want to reduce to node n, push that first. */
+ si->scc_stack.reserve (1);
+ si->scc_stack.quick_push (si->scc_stack[first]);
+ si->scc_stack[first] = n;
+
+ unsigned scc_size = si->scc_stack.length () - first;
+ unsigned split = scc_size / 2;
+ unsigned carry = scc_size - split * 2;
+ while (split > 0)
{
- if (!graph->points_to[n])
- graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
- bitmap_ior_into (graph->points_to[n],
- graph->points_to[w]);
+ for (unsigned i = 0; i < split; ++i)
+ {
+ unsigned a = si->scc_stack[first + i];
+ unsigned b = si->scc_stack[first + split + carry + i];
+
+ /* Unify our nodes. */
+ if (graph->preds[b])
+ {
+ if (!graph->preds[a])
+ std::swap (graph->preds[a], graph->preds[b]);
+ else
+ bitmap_ior_into_and_free (graph->preds[a],
+ &graph->preds[b]);
+ }
+ if (graph->implicit_preds[b])
+ {
+ if (!graph->implicit_preds[a])
+ std::swap (graph->implicit_preds[a],
+ graph->implicit_preds[b]);
+ else
+ bitmap_ior_into_and_free (graph->implicit_preds[a],
+ &graph->implicit_preds[b]);
+ }
+ if (graph->points_to[b])
+ {
+ if (!graph->points_to[a])
+ std::swap (graph->points_to[a], graph->points_to[b]);
+ else
+ bitmap_ior_into_and_free (graph->points_to[a],
+ &graph->points_to[b]);
+ }
+ }
+ unsigned remain = split + carry;
+ split = remain / 2;
+ carry = remain - split * 2;
}
+ /* Actually pop the SCC. */
+ si->scc_stack.truncate (first);
}
bitmap_set_bit (si->deleted, n);
}
3. Hashable. */
static void
-label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
+label_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
{
unsigned int i, first_pred;
bitmap_iterator bi;
/* Print the pred graph in dot format. */
static void
-dump_pred_graph (struct scc_info *si, FILE *file)
+dump_pred_graph (class scc_info *si, FILE *file)
{
unsigned int i;
/* Perform offline variable substitution, discovering equivalence
classes, and eliminating non-pointer variables. */
-static struct scc_info *
+static class scc_info *
perform_var_substitution (constraint_graph_t graph)
{
unsigned int i;
scc_info *si = new scc_info (size);
bitmap_obstack_initialize (&iteration_obstack);
+ gcc_obstack_init (&equiv_class_obstack);
pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511);
location_equiv_class_table
= new hash_table<equiv_class_hasher> (511);
substitution. */
static void
-free_var_substitution_info (struct scc_info *si)
+free_var_substitution_info (class scc_info *si)
{
delete si;
free (graph->pointer_label);
pointer_equiv_class_table = NULL;
delete location_equiv_class_table;
location_equiv_class_table = NULL;
+ obstack_free (&equiv_class_obstack, NULL);
bitmap_obstack_release (&iteration_obstack);
}
static void
rewrite_constraints (constraint_graph_t graph,
- struct scc_info *si)
+ class scc_info *si)
{
int i;
constraint_t c;
return;
}
- /* Pretend to take the address of the base, we'll take care of
- adding the required subset of sub-fields below. */
- get_constraint_for_1 (t, results, true, lhs_p);
+ /* Avoid creating pointer-offset constraints, so handle MEM_REF
+ offsets directly. Pretend to take the address of the base,
+ we'll take care of adding the required subset of sub-fields below. */
+ if (TREE_CODE (t) == MEM_REF
+ && !integer_zerop (TREE_OPERAND (t, 0)))
+ {
+ poly_offset_int off = mem_ref_offset (t);
+ off <<= LOG2_BITS_PER_UNIT;
+ off += bitpos;
+ poly_int64 off_hwi;
+ if (off.to_shwi (&off_hwi))
+ bitpos = off_hwi;
+ else
+ {
+ bitpos = 0;
+ bitmaxsize = -1;
+ }
+ get_constraint_for_1 (TREE_OPERAND (t, 0), results, false, lhs_p);
+ do_deref (results);
+ }
+ else
+ get_constraint_for_1 (t, results, true, lhs_p);
+
/* Strip off nothing_id. */
if (results->length () == 2)
{
point for reachable memory of their arguments. */
else if (flags & (ECF_PURE|ECF_LOOPING_CONST_OR_PURE))
handle_pure_call (t, &rhsc);
+ /* If the call is to a replaceable operator delete and results
+ from a delete expression as opposed to a direct call to
+ such operator, then the effects for PTA (in particular
+ the escaping of the pointer) can be ignored. */
+ else if (fndecl
+ && DECL_IS_OPERATOR_DELETE_P (fndecl)
+ && gimple_call_from_new_or_delete (t))
+ ;
else
handle_rhs_call (t, &rhsc);
if (gimple_call_lhs (t))
|| code == FLOOR_MOD_EXPR
|| code == ROUND_MOD_EXPR)
/* Division and modulo transfer the pointer from the LHS. */
- get_constraint_for_rhs (gimple_assign_rhs1 (t), &rhsc);
- else if ((CONVERT_EXPR_CODE_P (code)
- && !(POINTER_TYPE_P (gimple_expr_type (t))
- && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
+ get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
+ NULL_TREE, &rhsc);
+ else if (CONVERT_EXPR_CODE_P (code)
|| gimple_assign_single_p (t))
+ /* See through conversions, single RHS are handled by
+ get_constraint_for_rhs. */
get_constraint_for_rhs (rhsop, &rhsc);
else if (code == COND_EXPR)
{
;
else
{
- /* All other operations are merges. */
+ /* All other operations are possibly offsetting merges. */
auto_vec<ce_s, 4> tmp;
struct constraint_expr *rhsp;
unsigned i, j;
- get_constraint_for_rhs (gimple_assign_rhs1 (t), &rhsc);
+ get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
+ NULL_TREE, &rhsc);
for (i = 2; i < gimple_num_ops (t); ++i)
{
- get_constraint_for_rhs (gimple_op (t, i), &tmp);
+ get_constraint_for_ptr_offset (gimple_op (t, i),
+ NULL_TREE, &tmp);
FOR_EACH_VEC_ELT (tmp, j, rhsp)
rhsc.safe_push (*rhsp);
tmp.truncate (0);
return false;
/* If the vector of fields is growing too big, bail out early.
- Callers check for vec::length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
+ Callers check for vec::length <= param_max_fields_for_field_sensitive, make
sure this fails. */
- if (fieldstack->length () > MAX_FIELDS_FOR_FIELD_SENSITIVE)
+ if (fieldstack->length () > (unsigned)param_max_fields_for_field_sensitive)
return false;
for (field = TYPE_FIELDS (type); field; field = DECL_CHAIN (field))
/* If we didn't end up collecting sub-variables create a full
variable for the decl. */
if (fieldstack.length () == 0
- || fieldstack.length () > MAX_FIELDS_FOR_FIELD_SENSITIVE)
+ || fieldstack.length () > (unsigned)param_max_fields_for_field_sensitive)
{
vi = new_var_info (decl, name, add_id);
vi->offset = 0;
/* Return true if the points-to solution *PT is empty. */
bool
-pt_solution_empty_p (struct pt_solution *pt)
+pt_solution_empty_p (const pt_solution *pt)
{
if (pt->anything
|| pt->nonlocal)
static void
init_alias_vars (void)
{
- use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
+ use_field_sensitive = (param_max_fields_for_field_sensitive > 1);
bitmap_obstack_initialize (&pta_obstack);
bitmap_obstack_initialize (&oldpta_obstack);
static void
solve_constraints (void)
{
- struct scc_info *si;
+ class scc_info *si;
/* Sort varinfos so that ones that cannot be pointed to are last.
This makes bitmaps more efficient. */
{
if ((node->alias
|| (node->thunk.thunk_p
- && ! node->global.inlined_to))
+ && ! node->inlined_to))
&& node->analyzed
&& !node->ifunc_resolver)
insert_vi_for_tree (node->decl, (varinfo_t)data);
{
bool *nonlocal_p = (bool *)data;
*nonlocal_p |= (node->used_from_other_partition
- || node->externally_visible
+ || DECL_EXTERNAL (node->decl)
+ || TREE_PUBLIC (node->decl)
|| node->force_output
|| lookup_attribute ("noipa", DECL_ATTRIBUTES (node->decl)));
return false;
{
bool *nonlocal_p = (bool *)data;
*nonlocal_p |= (node->used_from_other_partition
- || node->externally_visible
+ || DECL_EXTERNAL (node->decl)
+ || TREE_PUBLIC (node->decl)
|| node->force_output);
return false;
}
/* Nodes without a body are not interesting. Especially do not
visit clones at this point for now - we get duplicate decls
there for inline clones at least. */
- if (!node->has_gimple_body_p () || node->global.inlined_to)
+ if (!node->has_gimple_body_p () || node->inlined_to)
continue;
node->get_body ();
For local functions we see all callers and thus do not need initial
constraints for parameters. */
bool nonlocal_p = (node->used_from_other_partition
- || node->externally_visible
+ || DECL_EXTERNAL (node->decl)
+ || TREE_PUBLIC (node->decl)
|| node->force_output
|| lookup_attribute ("noipa",
DECL_ATTRIBUTES (node->decl)));
&& from != constraints.length ())
{
fprintf (dump_file,
- "Generating intial constraints for %s", node->name ());
+ "Generating initial constraints for %s",
+ node->dump_name ());
if (DECL_ASSEMBLER_NAME_SET_P (node->decl))
fprintf (dump_file, " (%s)",
IDENTIFIER_POINTER
/* For the purpose of IPA PTA unit-local globals are not
escape points. */
- bool nonlocal_p = (var->used_from_other_partition
- || var->externally_visible
+ bool nonlocal_p = (DECL_EXTERNAL (var->decl)
+ || TREE_PUBLIC (var->decl)
+ || var->used_from_other_partition
|| var->force_output);
var->call_for_symbol_and_aliases (refered_from_nonlocal_var,
&nonlocal_p, true);
if (dump_file)
{
fprintf (dump_file,
- "Generating constraints for %s", node->name ());
+ "Generating constraints for %s", node->dump_name ());
if (DECL_ASSEMBLER_NAME_SET_P (node->decl))
fprintf (dump_file, " (%s)",
IDENTIFIER_POINTER
projects / gcc.git / blobdiff