CbC/CbC_gcc: gcc/tree-ssa-structalias.c comparison

comparison gcc/tree-ssa-structalias.c @ 145:1830386684a0

gcc-9.2.0

author	anatofuz
date	Thu, 13 Feb 2020 11:34:05 +0900
parents	84e7813d76e9
children

comparison

equal deleted inserted replaced

-:84e7813d76e9
+:1830386684a0
 /* Tree based points-to analysis
-Copyright (C) 2005-2018 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.
 GCC is free software; you can redistribute it and/or modify
 #include "stor-layout.h"
 #include "stmt.h"
 #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"
 #include "attribs.h"
 #include "tree-ssa.h"
+#include "tree-cfg.h"
 /* The idea behind this analyzer is to generate set constraints from the
 program, then solve the resulting constraints in order to generate the
 points-to sets.
 /* Size of the variable, in bits.  */
 unsigned HOST_WIDE_INT size;
 /* Full size of the base variable, in bits.  */
 unsigned HOST_WIDE_INT fullsize;
+/* In IPA mode the shadow UID in case the variable needs to be duplicated in
+the final points-to solution because it reaches its containing
+function recursively.  Zero if none is needed.  */
+unsigned int shadow_var_uid;
 /* Name of this variable */
 const char *name;
 /* Tree that this variable is associated with.  */
 			  || (VAR_P (t) && DECL_HARD_REGISTER (t)));
 ret->is_reg_var = (t && TREE_CODE (t) == SSA_NAME);
 ret->solution = BITMAP_ALLOC (&pta_obstack);
 ret->oldsolution = NULL;
 ret->next = 0;
+ret->shadow_var_uid = 0;
 ret->head = ret->id;
 stats.total_vars++;
 varmap.safe_push (ret);
 /* Changed variables on the last iteration.  */
 static bitmap changed;
 /* Strongly Connected Component visitation info.  */
-struct scc_info
+class scc_info
 {
+public:
 scc_info (size_t size);
 ~scc_info ();
 auto_sbitmap visited;
 auto_sbitmap deleted;
 connected components in a directed graph" by Esko Nuutila and Eljas
 Soisalon-Soininen, in Information Processing Letters volume 49,
 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;
 unsigned int my_dfs;
 } *equiv_class_label_t;
 typedef const struct equiv_class_label *const_equiv_class_label_t;
 /* 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 *,
 			    const equiv_class_label *);
 };
 /* A hashtable for mapping a bitmap of labels->location equivalence
 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.  */
 static equiv_class_label *
 ecl.labels = labels;
 ecl.hashcode = bitmap_hash (labels);
 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;
 }
 /* Recursive routine to find strongly connected components in GRAPH,
 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;
 unsigned int my_dfs;
 }
 /* See if any components have been identified.  */
 if (si->dfs[n] == my_dfs)
 {
-while (si->scc_stack.length () != 0
+if (si->scc_stack.length () != 0
-	     && si->dfs[si->scc_stack.last ()] >= my_dfs)
+	  && si->dfs[si->scc_stack.last ()] >= my_dfs)
 	{
-	  unsigned int w = si->scc_stack.pop ();
+	  /* Find the first node of the SCC and do non-bitmap work.  */
-	  si->node_mapping[w] = n;
+	  bool direct_p = true;
+	  unsigned first = si->scc_stack.length ();
-	  if (!bitmap_bit_p (graph->direct_nodes, w))
+	  do
+	    {
+	      --first;
+	      unsigned int w = si->scc_stack[first];
+	      si->node_mapping[w] = n;
+	      if (!bitmap_bit_p (graph->direct_nodes, w))
+		direct_p = false;
+	    }
+	  while (first > 0
+		 && si->dfs[si->scc_stack[first - 1]] >= my_dfs);
+	  if (!direct_p)
 	    bitmap_clear_bit (graph->direct_nodes, n);
-	  /* Unify our nodes.  */
+	  /* Want to reduce to node n, push that first.  */
-	  if (graph->preds[w])
+	  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->preds[n])
+	      for (unsigned i = 0; i < split; ++i)
-		graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
+		{
-	      bitmap_ior_into (graph->preds[n], graph->preds[w]);
+		  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;
 	    }
-	  if (graph->implicit_preds[w])
+	  /* Actually pop the SCC.  */
-	    {
+	  si->scc_stack.truncate (first);
-	      if (!graph->implicit_preds[n])
-		graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
-	      bitmap_ior_into (graph->implicit_preds[n],
-			       graph->implicit_preds[w]);
-	    }
-	  if (graph->points_to[w])
-	    {
-	      if (!graph->points_to[n])
-		graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
-	      bitmap_ior_into (graph->points_to[n],
-			       graph->points_to[w]);
-	    }
 	}
 bitmap_set_bit (si->deleted, n);
 }
 else
 si->scc_stack.safe_push (n);
 2. The end result of a given set of operations must be unique iff the
 combination of input values is unique
 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;
 bitmap_set_bit (si->visited, n);
 }
 /* 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;
 /* Only print the graph if it has already been initialized:  */
 if (!graph)
 }
 /* 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;
 unsigned int size = graph->size;
 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);
 pointer_equiv_class = 1;
 location_equiv_class = 1;
 /* Free information that was only necessary for variable
 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);
 free (graph->loc_label);
 free (graph->pointed_by);
 sbitmap_free (graph->direct_nodes);
 delete pointer_equiv_class_table;
 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);
 }
 /* Return an existing node that is equivalent to NODE, which has
 equivalence class LABEL, if one exists.  Return NODE otherwise.  */
 collapsing of equivalent nodes.  SI is the SCC_INFO that is the
 result of perform_variable_substitution.  */
 static void
 rewrite_constraints (constraint_graph_t graph,
-		     struct scc_info *si)
+		     class scc_info *si)
 {
 int i;
 constraint_t c;
 if (flag_checking)
 result.offset = 0;
 results->safe_push (result);
 return;
 }
-/* Pretend to take the address of the base, we'll take care of
+/* Avoid creating pointer-offset constraints, so handle MEM_REF
-adding the required subset of sub-fields below.  */
+offsets directly.  Pretend to take the address of the base,
-get_constraint_for_1 (t, results, true, lhs_p);
+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)
 {
 gcc_assert ((*results)[0].var == nothing_id);
 results->unordered_remove (0);
 heapvar = build_fake_var_decl (ptr_type_node);
 DECL_EXTERNAL (heapvar) = 1;
 vi = new_var_info (heapvar, name, add_id);
-vi->is_artificial_var = true;
 vi->is_heap_var = true;
 vi->is_unknown_size_var = true;
 vi->offset = 0;
 vi->fullsize = ~0;
 vi->size = ~0;
 	      ac.var = integer_id;
 	    }
 	  ac.offset = 0;
 	  FOR_EACH_VEC_ELT (lhsc, i, lhsp)
 	      process_constraint (new_constraint (*lhsp, ac));
+	  return true;
+	}
+case BUILT_IN_STACK_SAVE:
+case BUILT_IN_STACK_RESTORE:
+/* Nothing interesting happens.  */
+return true;
+case BUILT_IN_ALLOCA:
+case BUILT_IN_ALLOCA_WITH_ALIGN:
+case BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX:
+	{
+	  tree ptr = gimple_call_lhs (t);
+	  if (ptr == NULL_TREE)
+	    return true;
+	  get_constraint_for (ptr, &lhsc);
+	  varinfo_t vi = make_heapvar ("HEAP", true);
+	  /* Alloca storage is never global.  To exempt it from escaped
+	     handling make it a non-heap var.  */
+	  DECL_EXTERNAL (vi->decl) = 0;
+	  vi->is_global_var = 0;
+	  vi->is_heap_var = 0;
+	  struct constraint_expr tmpc;
+	  tmpc.var = vi->id;
+	  tmpc.offset = 0;
+	  tmpc.type = ADDRESSOF;
+	  rhsc.safe_push (tmpc);
+	  process_all_all_constraints (lhsc, rhsc);
 	  return true;
 	}
 case BUILT_IN_POSIX_MEMALIGN:
 {
 	  tree ptrptr = gimple_call_arg (t, 0);
 		  /* __builtin_GOMP_parallel (fn, data, num_threads, flags).  */
 		  fnpos = 0;
 		  argpos = 1;
 		  break;
 		case BUILT_IN_GOACC_PARALLEL:
-		  /* __builtin_GOACC_parallel (device, fn, mapnum, hostaddrs,
+		  /* __builtin_GOACC_parallel (flags_m, fn, mapnum, hostaddrs,
 					       sizes, kinds, ...).  */
 		  fnpos = 1;
 		  argpos = 3;
 		  break;
 		default:
 	  get_constraint_for (lhsop, &lhsc);
 	  if (code == POINTER_PLUS_EXPR)
 	    get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
 					   gimple_assign_rhs2 (t), &rhsc);
+	  else if (code == POINTER_DIFF_EXPR)
+	    /* The result is not a pointer (part).  */
+	    ;
 	  else if (code == BIT_AND_EXPR
 		   && TREE_CODE (gimple_assign_rhs2 (t)) == INTEGER_CST)
 	    {
 	      /* Aligning a pointer via a BIT_AND_EXPR is offsetting
 		 the pointer.  Handle it by offsetting it by UNKNOWN.  */
 	      get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
 					     NULL_TREE, &rhsc);
 	    }
-	  else if ((CONVERT_EXPR_CODE_P (code)
+	  else if (code == TRUNC_DIV_EXPR
-		    && !(POINTER_TYPE_P (gimple_expr_type (t))
+		   || code == CEIL_DIV_EXPR
-			 && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
+		   || code == FLOOR_DIV_EXPR
+		   || code == ROUND_DIV_EXPR
+		   || code == EXACT_DIV_EXPR
+		   || code == TRUNC_MOD_EXPR
+		   || code == CEIL_MOD_EXPR
+		   || code == FLOOR_MOD_EXPR
+		   || code == ROUND_MOD_EXPR)
+	    /* Division and modulo transfer the pointer from the LHS.  */
+	    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)
 	    {
 	      /* The result is a merge of both COND_EXPR arms.  */
 	      auto_vec<ce_s, 2> tmp;
 	    /* Truth value results are not pointer (parts).  Or at least
 	       very unreasonable obfuscation of a part.  */
 	    ;
 	  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);
 		}
 	    }
 	   && gimple_return_retval (as_a <greturn *> (t)) != NULL_TREE)
 {
 greturn *return_stmt = as_a <greturn *> (t);
 fi = NULL;
 if (!in_ipa_mode
-	  || !(fi = get_vi_for_tree (fn->decl)))
+	  && SSA_VAR_P (gimple_return_retval (return_stmt)))
+	{
+	  /* We handle simple returns by post-processing the solutions.  */
+	  ;
+	}
+if (!(fi = get_vi_for_tree (fn->decl)))
 	make_escape_constraint (gimple_return_retval (return_stmt));
 else if (in_ipa_mode)
 	{
 	  struct constraint_expr lhs ;
 	  struct constraint_expr *rhsp;
 		  /* __builtin_GOMP_parallel (fn, data, num_threads, flags).  */
 		  fnpos = 0;
 		  argpos = 1;
 		  break;
 		case BUILT_IN_GOACC_PARALLEL:
-		  /* __builtin_GOACC_parallel (device, fn, mapnum, hostaddrs,
+		  /* __builtin_GOACC_parallel (flags_m, fn, mapnum, hostaddrs,
 					       sizes, kinds, ...).  */
 		  fnpos = 1;
 		  argpos = 3;
 		  implicit_use_args[num_implicit_use_args++] = 4;
 		  implicit_use_args[num_implicit_use_args++] = 5;
 if (TREE_CODE (type) != RECORD_TYPE)
 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 (TREE_CODE (field) == FIELD_DECL)
 {
 	  && argvi->may_have_pointers)
 	make_constraint_from (argvi, nonlocal_id);
 gcc_assert (prev_vi->offset < argvi->offset);
 prev_vi->next = argvi->id;
-prev_vi = argvi;
 }
 return vi;
 }
 }
 /* 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;
 vi->may_have_pointers = true;
 vi->fullsize = tree_to_uhwi (declsize);
 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
 {
 varinfo_t vi = get_varinfo (i);
-/* The only artificial variables that are allowed in a may-alias
+if (vi->is_artificial_var)
-	 set are heap variables.  */
-if (vi->is_artificial_var && !vi->is_heap_var)
 	continue;
 if (everything_escaped
 	  || (escaped_vi->solution
 	      && bitmap_bit_p (escaped_vi->solution, i)))
 	{
 	  pt->vars_contains_escaped = true;
-	  pt->vars_contains_escaped_heap = vi->is_heap_var;
+	  pt->vars_contains_escaped_heap |= vi->is_heap_var;
 	}
 if (vi->is_restrict_var)
 	pt->vars_contains_restrict = true;
 	     for pointer comparison simplification.  */
 	  if (VAR_P (vi->decl)
 	      && (TREE_STATIC (vi->decl) || DECL_EXTERNAL (vi->decl))
 	      && ! decl_binds_to_current_def_p (vi->decl))
 	    pt->vars_contains_interposable = true;
+	  /* If this is a local variable we can have overlapping lifetime
+	     of different function invocations through recursion duplicate
+	     it with its shadow variable.  */
+	  if (in_ipa_mode
+	      && vi->shadow_var_uid != 0)
+	    {
+	      bitmap_set_bit (into, vi->shadow_var_uid);
+	      pt->vars_contains_nonlocal = true;
+	    }
 	}
 else if (TREE_CODE (vi->decl) == FUNCTION_DECL
 	       || TREE_CODE (vi->decl) == LABEL_DECL)
 	{
 	      if (bitmap_bit_p (evi->solution, nonlocal_id))
 		pt->nonlocal = 1;
 	    }
 	  else if (vi->id == nonlocal_id)
 	    pt->nonlocal = 1;
-	  else if (vi->is_heap_var)
-	    /* We represent heapvars in the points-to set properly.  */
-	    ;
 	  else if (vi->id == string_id)
 	    /* Nobody cares - STRING_CSTs are read-only entities.  */
 	    ;
 	  else if (vi->id == anything_id
 		   || vi->id == integer_id)
 }
 /* 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)
 return false;
 /* Initialize things necessary to perform PTA */
 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);
 bitmap_obstack_initialize (&predbitmap_obstack);
 /* Solve the constraint set.  */
 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.  */
 unsigned int *map = XNEWVEC (unsigned int, varmap.length ());
 for (unsigned i = 0; i < integer_id + 1; ++i)
 fprintf (dump_file, "\n\n// The constraint graph after solve-graph "
 	       "in dot format:\n");
 dump_constraint_graph (dump_file);
 fprintf (dump_file, "\n\n");
 }
+}
+/* Create points-to sets for the current function.  See the comments
+at the start of the file for an algorithmic overview.  */
+static void
+compute_points_to_sets (void)
+{
+basic_block bb;
+varinfo_t vi;
+timevar_push (TV_TREE_PTA);
+init_alias_vars ();
+intra_create_variable_infos (cfun);
+/* Now walk all statements and build the constraint set.  */
+FOR_EACH_BB_FN (bb, cfun)
+{
+for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
+	   gsi_next (&gsi))
+	{
+	  gphi *phi = gsi.phi ();
+	  if (! virtual_operand_p (gimple_phi_result (phi)))
+	    find_func_aliases (cfun, phi);
+	}
+for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
+	   gsi_next (&gsi))
+	{
+	  gimple *stmt = gsi_stmt (gsi);
+	  find_func_aliases (cfun, stmt);
+	}
+}
+if (dump_file)
+{
+fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
+dump_constraints (dump_file, 0);
+}
+/* From the constraints compute the points-to sets.  */
+solve_constraints ();
+/* Post-process solutions for escapes through returns.  */
+edge_iterator ei;
+edge e;
+FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
+if (greturn *ret = safe_dyn_cast <greturn *> (last_stmt (e->src)))
+{
+	tree val = gimple_return_retval (ret);
+	/* ???  Easy to handle simple indirections with some work.
+	   Arbitrary references like foo.bar.baz are more difficult
+	   (but conservatively easy enough with just looking at the base).
+	   Mind to fixup find_func_aliases as well.  */
+	if (!val || !SSA_VAR_P (val))
+	  continue;
+	/* returns happen last in non-IPA so they only influence
+	   the ESCAPED solution and we can filter local variables.  */
+	varinfo_t escaped_vi = get_varinfo (find (escaped_id));
+	varinfo_t vi = lookup_vi_for_tree (val);
+	bitmap delta = BITMAP_ALLOC (&pta_obstack);
+	bitmap_iterator bi;
+	unsigned i;
+	for (; vi; vi = vi_next (vi))
+	  {
+	    varinfo_t part_vi = get_varinfo (find (vi->id));
+	    EXECUTE_IF_AND_COMPL_IN_BITMAP (part_vi->solution,
+					    escaped_vi->solution, 0, i, bi)
+	      {
+		varinfo_t pointed_to_vi = get_varinfo (i);
+		if (pointed_to_vi->is_global_var
+		    /* We delay marking of heap memory as global.  */
+		    || pointed_to_vi->is_heap_var)
+		  bitmap_set_bit (delta, i);
+	      }
+	  }
+	/* Now compute the transitive closure.  */
+	bitmap_ior_into (escaped_vi->solution, delta);
+	bitmap new_delta = BITMAP_ALLOC (&pta_obstack);
+	while (!bitmap_empty_p (delta))
+	  {
+	    EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi)
+	      {
+		varinfo_t pointed_to_vi = get_varinfo (i);
+		pointed_to_vi = get_varinfo (find (pointed_to_vi->id));
+		unsigned j;
+		bitmap_iterator bi2;
+		EXECUTE_IF_AND_COMPL_IN_BITMAP (pointed_to_vi->solution,
+						escaped_vi->solution,
+						0, j, bi2)
+		  {
+		    varinfo_t pointed_to_vi2 = get_varinfo (j);
+		    if (pointed_to_vi2->is_global_var
+			/* We delay marking of heap memory as global.  */
+			|| pointed_to_vi2->is_heap_var)
+		      bitmap_set_bit (new_delta, j);
+		  }
+	      }
+	    bitmap_ior_into (escaped_vi->solution, new_delta);
+	    bitmap_clear (delta);
+	    std::swap (delta, new_delta);
+	  }
+	BITMAP_FREE (delta);
+	BITMAP_FREE (new_delta);
+}
 if (dump_file)
 dump_sa_points_to_info (dump_file);
-}
-/* Create points-to sets for the current function.  See the comments
-at the start of the file for an algorithmic overview.  */
-static void
-compute_points_to_sets (void)
-{
-basic_block bb;
-varinfo_t vi;
-timevar_push (TV_TREE_PTA);
-init_alias_vars ();
-intra_create_variable_infos (cfun);
-/* Now walk all statements and build the constraint set.  */
-FOR_EACH_BB_FN (bb, cfun)
-{
-for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
-	   gsi_next (&gsi))
-	{
-	  gphi *phi = gsi.phi ();
-	  if (! virtual_operand_p (gimple_phi_result (phi)))
-	    find_func_aliases (cfun, phi);
-	}
-for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
-	   gsi_next (&gsi))
-	{
-	  gimple *stmt = gsi_stmt (gsi);
-	  find_func_aliases (cfun, stmt);
-	}
-}
-if (dump_file)
-{
-fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
-dump_constraints (dump_file, 0);
-}
-/* From the constraints compute the points-to sets.  */
-solve_constraints ();
 /* Compute the points-to set for ESCAPED used for call-clobber analysis.  */
 cfun->gimple_df->escaped = find_what_var_points_to (cfun->decl,
 						      get_varinfo (escaped_id));
 	 into a function with restrict parameters.  This usually means we
 	 prefer to be precise in innermost loops.  */
 if (MR_DEPENDENCE_CLIQUE (base) == 0)
 	{
 	  if (clique == 0)
-	    clique = ++cfun->last_clique;
+	    {
+	      if (cfun->last_clique == 0)
+		cfun->last_clique = 1;
+	      clique = 1;
+	    }
 	  if (restrict_var->ruid == 0)
 	    restrict_var->ruid = ++last_ruid;
 	  MR_DEPENDENCE_CLIQUE (base) = clique;
 	  MR_DEPENDENCE_BASE (base) = restrict_var->ruid;
 	  return true;
 	}
 }
 return false;
 }
+/* Clear dependence info for the clique DATA.  */
+static bool
+clear_dependence_clique (gimple *, tree base, tree, void *data)
+{
+unsigned short clique = (uintptr_t)data;
+if ((TREE_CODE (base) == MEM_REF
+|| TREE_CODE (base) == TARGET_MEM_REF)
+&& MR_DEPENDENCE_CLIQUE (base) == clique)
+{
+MR_DEPENDENCE_CLIQUE (base) = 0;
+MR_DEPENDENCE_BASE (base) = 0;
+}
+return false;
+}
 /* Compute the set of independend memory references based on restrict
 tags and their conservative propagation to the points-to sets.  */
 static void
 compute_dependence_clique (void)
 {
+/* First clear the special "local" clique.  */
+basic_block bb;
+if (cfun->last_clique != 0)
+FOR_EACH_BB_FN (bb, cfun)
+for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
+	   !gsi_end_p (gsi); gsi_next (&gsi))
+	{
+	  gimple *stmt = gsi_stmt (gsi);
+	  walk_stmt_load_store_ops (stmt, (void *)(uintptr_t) 1,
+				    clear_dependence_clique,
+				    clear_dependence_clique);
+	}
 unsigned short clique = 0;
 unsigned short last_ruid = 0;
 bitmap rvars = BITMAP_ALLOC (NULL);
 bool escaped_p = false;
 for (unsigned i = 0; i < num_ssa_names; ++i)
 unsigned j;
 varinfo_t restrict_var = NULL;
 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
 	{
 	  varinfo_t oi = get_varinfo (j);
+	  if (oi->head != j)
+	    oi = get_varinfo (oi->head);
 	  if (oi->is_restrict_var)
 	    {
-	      if (restrict_var)
+	      if (restrict_var
+		  && restrict_var != oi)
 		{
 		  if (dump_file && (dump_flags & TDF_DETAILS))
 		    {
 		      fprintf (dump_file, "found restrict pointed-to "
 			       "for ");
 	    used |= walk_stmt_load_store_ops (use_stmt, &data,
 					      maybe_set_dependence_info,
 					      maybe_set_dependence_info);
 	  if (used)
 	    {
-	      bitmap_set_bit (rvars, restrict_var->id);
+	      /* Add all subvars to the set of restrict pointed-to set. */
+	      for (unsigned sv = restrict_var->head; sv != 0;
+		   sv = get_varinfo (sv)->next)
+		bitmap_set_bit (rvars, sv);
 	      varinfo_t escaped = get_varinfo (find (escaped_id));
 	      if (bitmap_bit_p (escaped->solution, restrict_var->id))
 		escaped_p = true;
 	    }
 	}
 static bool
 associate_varinfo_to_alias (struct cgraph_node *node, void *data)
 {
 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);
 return false;
 }
 {
 varinfo_t vi;
 /* 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 ();
 gcc_assert (!node->clone_of);
 				     nonlocal_p);
 if (dump_file
 	  && 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
 		       (DECL_ASSEMBLER_NAME (node->decl)));
 	  fprintf (dump_file, "\n\n");
 	continue;
 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
 		       (DECL_ASSEMBLER_NAME (node->decl)));
 	  fprintf (dump_file, "\n");
 	}
 }
 /* From the constraints compute the points-to sets.  */
 solve_constraints ();
+if (dump_file)
+dump_sa_points_to_info (dump_file);
+/* Now post-process solutions to handle locals from different
+runtime instantiations coming in through recursive invocations.  */
+unsigned shadow_var_cnt = 0;
+for (unsigned i = 1; i < varmap.length (); ++i)
+{
+varinfo_t fi = get_varinfo (i);
+if (fi->is_fn_info
+	  && fi->decl)
+	/* Automatic variables pointed to by their containing functions
+	   parameters need this treatment.  */
+	for (varinfo_t ai = first_vi_for_offset (fi, fi_parm_base);
+	     ai; ai = vi_next (ai))
+	  {
+	    varinfo_t vi = get_varinfo (find (ai->id));
+	    bitmap_iterator bi;
+	    unsigned j;
+	    EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
+	      {
+		varinfo_t pt = get_varinfo (j);
+		if (pt->shadow_var_uid == 0
+		    && pt->decl
+		    && auto_var_in_fn_p (pt->decl, fi->decl))
+		  {
+		    pt->shadow_var_uid = allocate_decl_uid ();
+		    shadow_var_cnt++;
+		  }
+	      }
+	  }
+/* As well as global variables which are another way of passing
+arguments to recursive invocations.  */
+else if (fi->is_global_var)
+	{
+	  for (varinfo_t ai = fi; ai; ai = vi_next (ai))
+	    {
+	      varinfo_t vi = get_varinfo (find (ai->id));
+	      bitmap_iterator bi;
+	      unsigned j;
+	      EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi)
+		{
+		  varinfo_t pt = get_varinfo (j);
+		  if (pt->shadow_var_uid == 0
+		      && pt->decl
+		      && auto_var_p (pt->decl))
+		    {
+		      pt->shadow_var_uid = allocate_decl_uid ();
+		      shadow_var_cnt++;
+		    }
+		}
+	    }
+	}
+}
+if (shadow_var_cnt && dump_file && (dump_flags & TDF_DETAILS))
+fprintf (dump_file, "Allocated %u shadow variables for locals "
+	     "maybe leaking into recursive invocations of their containing "
+	     "functions\n", shadow_var_cnt);
 /* Compute the global points-to sets for ESCAPED.
 ???  Note that the computed escape set is not correct
 for the whole unit as we fail to consider graph edges to
 externally visible functions.  */

Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-ssa-structalias.c @ 145:1830386684a0