path: root/gcc/tree-ssa-structalias.cc

/* Tree based points-to analysis
   Copyright (C) 2005-2025 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
   under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3 of the License, 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 "backend.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "alloc-pool.h"
#include "tree-pass.h"
#include "ssa.h"
#include "cgraph.h"
#include "tree-pretty-print.h"
#include "diagnostic-core.h"
#include "fold-const.h"
#include "stor-layout.h"
#include "stmt.h"
#include "gimple-iterator.h"
#include "tree-into-ssa.h"
#include "tree-dfa.h"
#include "gimple-walk.h"
#include "varasm.h"
#include "stringpool.h"
#include "attribs.h"
#include "tree-ssa.h"
#include "tree-cfg.h"
#include "gimple-range.h"
#include "ipa-modref-tree.h"
#include "ipa-modref.h"
#include "attr-fnspec.h"

#include "tree-ssa-structalias.h"
#include "pta-andersen.h"
#include "gimple-ssa-pta-constraints.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.

   Set constraints are a way of modeling program analysis problems that
   involve sets.  They consist of an inclusion constraint language,
   describing the variables (each variable is a set) and operations that
   are involved on the variables, and a set of rules that derive facts
   from these operations.  To solve a system of set constraints, you derive
   all possible facts under the rules, which gives you the correct sets
   as a consequence.

   See  "Efficient Field-sensitive pointer analysis for C" by "David
   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
   http://citeseer.ist.psu.edu/heintze01ultrafast.html

   There are three types of real constraint expressions, DEREF,
   ADDRESSOF, and SCALAR.  Each constraint expression consists
   of a constraint type, a variable, and an offset.

   SCALAR is a constraint expression type used to represent x, whether
   it appears on the LHS or the RHS of a statement.
   DEREF is a constraint expression type used to represent *x, whether
   it appears on the LHS or the RHS of a statement.
   ADDRESSOF is a constraint expression used to represent &x, whether
   it appears on the LHS or the RHS of a statement.

   Each pointer variable in the program is assigned an integer id, and
   each field of a structure variable is assigned an integer id as well.

   Structure variables are linked to their list of fields through a "next
   field" in each variable that points to the next field in offset
   order.
   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.
   3. "offset", that tells the offset in bits from the beginning of the
   structure to this field.

   Thus,
   struct f
   {
     int a;
     int b;
   } foo;
   int *bar;

   looks like

   foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
   foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
   bar -> id 3, size 32, offset 0, fullsize 32, next NULL


  In order to solve the system of set constraints, the following is
  done:

  1. Each constraint variable x has a solution set associated with it,
  Sol(x).

  2. Constraints are separated into direct, copy, and complex.
  Direct constraints are ADDRESSOF constraints that require no extra
  processing, such as P = &Q
  Copy constraints are those of the form P = Q.
  Complex constraints are all the constraints involving dereferences
  and offsets (including offsetted copies).

  3. All direct constraints of the form P = &Q are processed, such
  that Q is added to Sol(P)

  4. All complex constraints for a given constraint variable are stored in a
  linked list attached to that variable's node.

  5. A directed graph is built out of the copy constraints. Each
  constraint variable is a node in the graph, and an edge from
  Q to P is added for each copy constraint of the form P = Q

  6. The graph is then walked, and solution sets are
  propagated along the copy edges, such that an edge from Q to P
  causes Sol(P) <- Sol(P) union Sol(Q).

  7.  As we visit each node, all complex constraints associated with
  that node are processed by adding appropriate copy edges to the graph, or the
  appropriate variables to the solution set.

  8. The process of walking the graph is iterated until no solution
  sets change.

  Prior to walking the graph in steps 6 and 7, We perform static
  cycle elimination on the constraint graph, as well
  as off-line variable substitution.

  TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
  on and turned into anything), but isn't.  You can just see what offset
  inside the pointed-to struct it's going to access.

  TODO: Constant bounded arrays can be handled as if they were structs of the
  same number of elements.

  TODO: Modeling heap and incoming pointers becomes much better if we
  add fields to them as we discover them, which we could do.

  TODO: We could handle unions, but to be honest, it's probably not
  worth the pain or slowdown.  */

/* IPA-PTA optimizations possible.

   When the indirect function called is ANYTHING we can add disambiguation
   based on the function signatures (or simply the parameter count which
   is the varinfo size).  We also do not need to consider functions that
   do not have their address taken.

   The is_global_var bit which marks escape points is overly conservative
   in IPA mode.  Split it to is_escape_point and is_global_var - only
   externally visible globals are escape points in IPA mode.
   There is now is_ipa_escape_point but this is only used in a few
   selected places.

   The way we introduce DECL_PT_UID to avoid fixing up all points-to
   sets in the translation unit when we copy a DECL during inlining
   pessimizes precision.  The advantage is that the DECL_PT_UID keeps
   compile-time and memory usage overhead low - the points-to sets
   do not grow or get unshared as they would during a fixup phase.
   An alternative solution is to delay IPA PTA until after all
   inlining transformations have been applied.

   The way we propagate clobber/use information isn't optimized.
   It should use a new complex constraint that properly filters
   out local variables of the callee (though that would make
   the sets invalid after inlining).  OTOH we might as well
   admit defeat to WHOPR and simply do all the clobber/use analysis
   and propagation after PTA finished but before we threw away
   points-to information for memory variables.  WHOPR and PTA
   do not play along well anyway - the whole constraint solving
   would need to be done in WPA phase and it will be very interesting
   to apply the results to local SSA names during LTRANS phase.

   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 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.

   We never put function decls in points-to sets so we do not
   keep the set of called functions for indirect calls.

   And probably more.  */

using namespace pointer_analysis;

/* Pool of variable info structures.  */
static object_allocator<variable_info> variable_info_pool
  ("Variable info pool");

/* Map varinfo to final pt_solution.  */
static hash_map<varinfo_t, pt_solution *> *final_solutions;
static struct obstack final_solutions_obstack;


namespace pointer_analysis {

bool use_field_sensitive = true;
int in_ipa_mode = 0;

/* Used for points-to sets.  */
bitmap_obstack pta_obstack;

/* Used for oldsolution members of variables.  */
bitmap_obstack oldpta_obstack;

/* Table of variable info structures for constraint variables.
   Indexed directly by variable info id.  */
vec<varinfo_t> varmap;

/* List of constraints that we use to build the constraint graph from.  */
vec<constraint_t> constraints;

/* The representative variable for a variable.  The points-to solution for a
   var can be found in its rep.  Trivially, a var can be its own rep.

   The solver provides this array once it is done solving.  */
unsigned int *var_rep;

struct constraint_stats stats;

/* Find the first varinfo in the same variable as START that overlaps with
   OFFSET.  Return NULL if we can't find one.  */

varinfo_t
first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
{
  /* If the offset is outside of the variable, bail out.  */
  if (offset >= start->fullsize)
    return NULL;

  /* If we cannot reach offset from start, lookup the first field
     and start from there.  */
  if (start->offset > offset)
    start = get_varinfo (start->head);

  while (start)
    {
      /* We may not find a variable in the field list with the actual
	 offset when we have glommed a structure to a variable.
	 In that case, however, offset should still be within the size
	 of the variable.  */
      if (offset >= start->offset
	  && (offset - start->offset) < start->size)
	return start;

      start = vi_next (start);
    }

  return NULL;
}

/* Find the first varinfo in the same variable as START that overlaps with
   OFFSET.  If there is no such varinfo the varinfo directly preceding
   OFFSET is returned.  */

varinfo_t
first_or_preceding_vi_for_offset (varinfo_t start,
				  unsigned HOST_WIDE_INT offset)
{
  /* If we cannot reach offset from start, lookup the first field
     and start from there.  */
  if (start->offset > offset)
    start = get_varinfo (start->head);

  /* We may not find a variable in the field list with the actual
     offset when we have glommed a structure to a variable.
     In that case, however, offset should still be within the size
     of the variable.
     If we got beyond the offset we look for return the field
     directly preceding offset which may be the last field.  */
  while (start->next
	 && offset >= start->offset
	 && !((offset - start->offset) < start->size))
    start = vi_next (start);

  return start;
}

/* Determine global memory access of call STMT and update
   WRITES_GLOBAL_MEMORY, READS_GLOBAL_MEMORY and USES_GLOBAL_MEMORY.  */

void
determine_global_memory_access (gcall *stmt,
				bool *writes_global_memory,
				bool *reads_global_memory,
				bool *uses_global_memory)
{
  tree callee;
  cgraph_node *node;
  modref_summary *summary;

  /* We need to detrmine reads to set uses.  */
  gcc_assert (!uses_global_memory || reads_global_memory);

  if ((callee = gimple_call_fndecl (stmt)) != NULL_TREE
      && (node = cgraph_node::get (callee)) != NULL
      && (summary = get_modref_function_summary (node)))
    {
      if (writes_global_memory && *writes_global_memory)
	*writes_global_memory = summary->global_memory_written;
      if (reads_global_memory && *reads_global_memory)
	*reads_global_memory = summary->global_memory_read;
      if (reads_global_memory && uses_global_memory
	  && !summary->calls_interposable
	  && !*reads_global_memory && node->binds_to_current_def_p ())
	*uses_global_memory = false;
    }
  if ((writes_global_memory && *writes_global_memory)
      || (uses_global_memory && *uses_global_memory)
      || (reads_global_memory && *reads_global_memory))
    {
      attr_fnspec fnspec = gimple_call_fnspec (stmt);
      if (fnspec.known_p ())
	{
	  if (writes_global_memory
	      && !fnspec.global_memory_written_p ())
	    *writes_global_memory = false;
	  if (reads_global_memory && !fnspec.global_memory_read_p ())
	    {
	      *reads_global_memory = false;
	      if (uses_global_memory)
		*uses_global_memory = false;
	    }
	}
    }
}

/* Return true if FNDECL may be part of another lto partition.  */

bool
fndecl_maybe_in_other_partition (tree fndecl)
{
  cgraph_node *fn_node = cgraph_node::get (fndecl);
  if (fn_node == NULL)
    return true;

  return fn_node->in_other_partition;
}

/* Return a new variable info structure consisting for a variable
   named NAME, and using constraint graph node NODE.  Append it
   to the vector of variable info structures.  */

varinfo_t
new_var_info (tree t, const char *name, bool add_id)
{
  unsigned index = varmap.length ();
  varinfo_t ret = variable_info_pool.allocate ();

  if (dump_file && add_id)
    {
      char *tempname = xasprintf ("%s(%d)", name, index);
      name = ggc_strdup (tempname);
      free (tempname);
    }

  ret->id = index;
  ret->name = name;
  ret->decl = t;
  /* Vars without decl are artificial and do not have sub-variables.  */
  ret->is_artificial_var = (t == NULL_TREE);
  ret->is_special_var = false;
  ret->is_unknown_size_var = false;
  ret->is_full_var = (t == NULL_TREE);
  ret->is_heap_var = false;
  ret->may_have_pointers = true;
  ret->only_restrict_pointers = false;
  ret->is_restrict_var = false;
  ret->ruid = 0;
  ret->is_global_var = (t == NULL_TREE);
  ret->is_ipa_escape_point = false;
  ret->is_fn_info = false;
  ret->address_taken = false;
  if (t && DECL_P (t))
    ret->is_global_var = (is_global_var (t)
			  /* We have to treat even local register variables
			     as escape points.  */
			  || (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);

  return ret;
}

/* Print out constraint C to FILE.  */

void
dump_constraint (FILE *file, constraint_t c)
{
  if (c->lhs.type == ADDRESSOF)
    fprintf (file, "&");
  else if (c->lhs.type == DEREF)
    fprintf (file, "*");
  if (dump_file)
    fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
  else
    fprintf (file, "V%d", c->lhs.var);
  if (c->lhs.offset == UNKNOWN_OFFSET)
    fprintf (file, " + UNKNOWN");
  else if (c->lhs.offset != 0)
    fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
  fprintf (file, " = ");
  if (c->rhs.type == ADDRESSOF)
    fprintf (file, "&");
  else if (c->rhs.type == DEREF)
    fprintf (file, "*");
  if (dump_file)
    fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
  else
    fprintf (file, "V%d", c->rhs.var);
  if (c->rhs.offset == UNKNOWN_OFFSET)
    fprintf (file, " + UNKNOWN");
  else if (c->rhs.offset != 0)
    fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
}

/* Print out constraint C to stderr.  */

DEBUG_FUNCTION void
debug_constraint (constraint_t c)
{
  dump_constraint (stderr, c);
  fprintf (stderr, "\n");
}

/* Print out all constraints to FILE.  */

void
dump_constraints (FILE *file, int from)
{
  int i;
  constraint_t c;
  for (i = from; constraints.iterate (i, &c); i++)
    if (c)
      {
	dump_constraint (file, c);
	fprintf (file, "\n");
      }
}

/* Print out all constraints to stderr.  */

DEBUG_FUNCTION void
debug_constraints (void)
{
  dump_constraints (stderr, 0);
}

/* Print out the points-to solution for VAR to FILE.  */

void
dump_solution_for_var (FILE *file, unsigned int var)
{
  varinfo_t vi = get_varinfo (var);
  unsigned int i;
  bitmap_iterator bi;

  /* Dump the solution for unified vars anyway, this avoids difficulties
     in scanning dumps in the testsuite.  */
  fprintf (file, "%s = { ", vi->name);
  vi = get_varinfo (var_rep[var]);
  EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
    fprintf (file, "%s ", get_varinfo (i)->name);
  fprintf (file, "}");

  /* But note when the variable was unified.  */
  if (vi->id != var)
    fprintf (file, " same as %s", vi->name);

  fprintf (file, "\n");
}

/* Print the points-to solution for VAR to stderr.  */

DEBUG_FUNCTION void
debug_solution_for_var (unsigned int var)
{
  dump_solution_for_var (stderr, var);
}

/* Dump stats information to OUTFILE.  */

void
dump_sa_stats (FILE *outfile)
{
  fprintf (outfile, "Points-to Stats:\n");
  fprintf (outfile, "Total vars:               %d\n", stats.total_vars);
  fprintf (outfile, "Non-pointer vars:          %d\n",
	   stats.nonpointer_vars);
  fprintf (outfile, "Statically unified vars:  %d\n",
	   stats.unified_vars_static);
  fprintf (outfile, "Dynamically unified vars: %d\n",
	   stats.unified_vars_dynamic);
  fprintf (outfile, "Iterations:               %d\n", stats.iterations);
  fprintf (outfile, "Number of edges:          %d\n", stats.num_edges);
  fprintf (outfile, "Number of implicit edges: %d\n",
	   stats.num_implicit_edges);
  fprintf (outfile, "Number of avoided edges: %d\n",
	   stats.num_avoided_edges);
}

/* Dump points-to information to OUTFILE.  */

void
dump_sa_points_to_info (FILE *outfile)
{
  fprintf (outfile, "\nPoints-to sets\n\n");

  for (unsigned i = 1; i < varmap.length (); i++)
    {
      varinfo_t vi = get_varinfo (i);
      if (!vi->may_have_pointers)
	continue;
      dump_solution_for_var (outfile, i);
    }
}


/* Debug points-to information to stderr.  */

DEBUG_FUNCTION void
debug_sa_points_to_info (void)
{
  dump_sa_points_to_info (stderr);
}

/* Dump varinfo VI to FILE.  */

void
dump_varinfo (FILE *file, varinfo_t vi)
{
  if (vi == NULL)
    return;

  fprintf (file, "%u: %s\n", vi->id, vi->name);

  const char *sep = " ";
  if (vi->is_artificial_var)
    fprintf (file, "%sartificial", sep);
  if (vi->is_special_var)
    fprintf (file, "%sspecial", sep);
  if (vi->is_unknown_size_var)
    fprintf (file, "%sunknown-size", sep);
  if (vi->is_full_var)
    fprintf (file, "%sfull", sep);
  if (vi->is_heap_var)
    fprintf (file, "%sheap", sep);
  if (vi->may_have_pointers)
    fprintf (file, "%smay-have-pointers", sep);
  if (vi->only_restrict_pointers)
    fprintf (file, "%sonly-restrict-pointers", sep);
  if (vi->is_restrict_var)
    fprintf (file, "%sis-restrict-var", sep);
  if (vi->is_global_var)
    fprintf (file, "%sglobal", sep);
  if (vi->is_ipa_escape_point)
    fprintf (file, "%sipa-escape-point", sep);
  if (vi->is_fn_info)
    fprintf (file, "%sfn-info", sep);
  if (vi->ruid)
    fprintf (file, "%srestrict-uid:%u", sep, vi->ruid);
  if (vi->next)
    fprintf (file, "%snext:%u", sep, vi->next);
  if (vi->head != vi->id)
    fprintf (file, "%shead:%u", sep, vi->head);
  if (vi->offset)
    fprintf (file, "%soffset:" HOST_WIDE_INT_PRINT_DEC, sep, vi->offset);
  if (vi->size != ~HOST_WIDE_INT_0U)
    fprintf (file, "%ssize:" HOST_WIDE_INT_PRINT_DEC, sep, vi->size);
  if (vi->fullsize != ~HOST_WIDE_INT_0U && vi->fullsize != vi->size)
    fprintf (file, "%sfullsize:" HOST_WIDE_INT_PRINT_DEC, sep,
	     vi->fullsize);
  fprintf (file, "\n");

  if (vi->solution && !bitmap_empty_p (vi->solution))
    {
      bitmap_iterator bi;
      unsigned i;
      fprintf (file, " solution: {");
      EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
	fprintf (file, " %u", i);
      fprintf (file, " }\n");
    }

  if (vi->oldsolution && !bitmap_empty_p (vi->oldsolution)
      && !bitmap_equal_p (vi->solution, vi->oldsolution))
    {
      bitmap_iterator bi;
      unsigned i;
      fprintf (file, " oldsolution: {");
      EXECUTE_IF_SET_IN_BITMAP (vi->oldsolution, 0, i, bi)
	fprintf (file, " %u", i);
      fprintf (file, " }\n");
    }
}

/* Dump varinfo VI to stderr.  */

DEBUG_FUNCTION void
debug_varinfo (varinfo_t vi)
{
  dump_varinfo (stderr, vi);
}

/* Dump varmap to FILE.  */

void
dump_varmap (FILE *file)
{
  if (varmap.length () == 0)
    return;

  fprintf (file, "variables:\n");

  for (unsigned int i = 0; i < varmap.length (); ++i)
    {
      varinfo_t vi = get_varinfo (i);
      dump_varinfo (file, vi);
    }

  fprintf (file, "\n");
}

/* Dump varmap to stderr.  */

DEBUG_FUNCTION void
debug_varmap (void)
{
  dump_varmap (stderr);
}

} // namespace pointer_analysis


/* Structure used to put solution bitmaps in a hashtable so they can
   be shared among variables with the same points-to set.  */

typedef struct shared_bitmap_info
{
  bitmap pt_vars;
  hashval_t hashcode;
} *shared_bitmap_info_t;
typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;

/* Shared_bitmap hashtable helpers.  */

struct shared_bitmap_hasher : free_ptr_hash <shared_bitmap_info>
{
  static inline hashval_t hash (const shared_bitmap_info *);
  static inline bool equal (const shared_bitmap_info *,
			    const shared_bitmap_info *);
};

/* Hash function for a shared_bitmap_info_t.  */

inline hashval_t
shared_bitmap_hasher::hash (const shared_bitmap_info *bi)
{
  return bi->hashcode;
}

/* Equality function for two shared_bitmap_info_t's.  */

inline bool
shared_bitmap_hasher::equal (const shared_bitmap_info *sbi1,
			     const shared_bitmap_info *sbi2)
{
  return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
}

/* Shared_bitmap hashtable.  */

static hash_table<shared_bitmap_hasher> *shared_bitmap_table;

/* Lookup a bitmap in the shared bitmap hashtable, and return an already
   existing instance if there is one, NULL otherwise.  */

static bitmap
shared_bitmap_lookup (bitmap pt_vars)
{
  shared_bitmap_info **slot;
  struct shared_bitmap_info sbi;

  sbi.pt_vars = pt_vars;
  sbi.hashcode = bitmap_hash (pt_vars);

  slot = shared_bitmap_table->find_slot (&sbi, NO_INSERT);
  if (!slot)
    return NULL;
  else
    return (*slot)->pt_vars;
}

/* Add a bitmap to the shared bitmap hashtable.  */

static void
shared_bitmap_add (bitmap pt_vars)
{
  shared_bitmap_info **slot;
  shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);

  sbi->pt_vars = pt_vars;
  sbi->hashcode = bitmap_hash (pt_vars);

  slot = shared_bitmap_table->find_slot (sbi, INSERT);
  gcc_assert (!*slot);
  *slot = sbi;
}

/* Set bits in INTO corresponding to the variable uids in solution set FROM.  */

static void
set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt,
		   tree fndecl)
{
  unsigned int i;
  bitmap_iterator bi;
  varinfo_t escaped_vi = get_varinfo (var_rep[escaped_id]);
  varinfo_t escaped_return_vi = get_varinfo (var_rep[escaped_return_id]);
  bool everything_escaped
    = escaped_vi->solution && bitmap_bit_p (escaped_vi->solution, anything_id);

  EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
    {
      varinfo_t vi = get_varinfo (i);

      if (vi->is_artificial_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;
	}
      if (escaped_return_vi->solution
	  && bitmap_bit_p (escaped_return_vi->solution, i))
	pt->vars_contains_escaped_heap |= vi->is_heap_var;

      if (vi->is_restrict_var)
	pt->vars_contains_restrict = true;

      if (VAR_P (vi->decl)
	  || TREE_CODE (vi->decl) == PARM_DECL
	  || TREE_CODE (vi->decl) == RESULT_DECL)
	{
	  /* If we are in IPA mode we will not recompute points-to
	     sets after inlining so make sure they stay valid.  */
	  if (in_ipa_mode
	      && !DECL_PT_UID_SET_P (vi->decl))
	    SET_DECL_PT_UID (vi->decl, DECL_UID (vi->decl));

	  /* Add the decl to the points-to set.  Note that the points-to
	     set contains global variables.  */
	  bitmap_set_bit (into, DECL_PT_UID (vi->decl));
	  if (vi->is_global_var
	      /* In IPA mode the escaped_heap trick doesn't work as
		 ESCAPED is escaped from the unit but
		 pt_solution_includes_global needs to answer true for
		 all variables not automatic within a function.
		 For the same reason is_global_var is not the
		 correct flag to track - local variables from other
		 functions also need to be considered global.
		 Conveniently all HEAP vars are not put in function
		 scope.  */
	      || (in_ipa_mode
		  && fndecl
		  && ! auto_var_in_fn_p (vi->decl, fndecl)))
	    pt->vars_contains_nonlocal = true;

	  /* If we have a variable that is interposable record that fact
	     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)
	{
	  /* Nothing should read/write from/to code so we can
	     save bits by not including them in the points-to bitmaps.
	     Still mark the points-to set as containing global memory
	     to make code-patching possible - see PR70128.  */
	  pt->vars_contains_nonlocal = true;
	}
    }
}


/* Compute the points-to solution *PT for the variable VI.  */

static struct pt_solution
find_what_var_points_to (tree fndecl, varinfo_t orig_vi)
{
  unsigned int i;
  bitmap_iterator bi;
  bitmap finished_solution;
  bitmap result;
  varinfo_t vi;
  struct pt_solution *pt;

  /* This variable may have been collapsed, let's get the real
     variable.  */
  vi = get_varinfo (var_rep[orig_vi->id]);

  /* See if we have already computed the solution and return it.  */
  pt_solution **slot = &final_solutions->get_or_insert (vi);
  if (*slot != NULL)
    return **slot;

  *slot = pt = XOBNEW (&final_solutions_obstack, struct pt_solution);
  memset (pt, 0, sizeof (struct pt_solution));

  /* Translate artificial variables into SSA_NAME_PTR_INFO
     attributes.  */
  EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
    {
      varinfo_t vi = get_varinfo (i);

      if (vi->is_artificial_var)
	{
	  if (vi->id == nothing_id)
	    pt->null = 1;
	  else if (vi->id == escaped_id)
	    {
	      if (in_ipa_mode)
		pt->ipa_escaped = 1;
	      else
		pt->escaped = 1;
	      /* Expand some special vars of ESCAPED in-place here.  */
	      varinfo_t evi = get_varinfo (var_rep[escaped_id]);
	      if (bitmap_bit_p (evi->solution, nonlocal_id))
		pt->nonlocal = 1;
	    }
	  else if (vi->id == nonlocal_id)
	    pt->nonlocal = 1;
	  else if (vi->id == string_id)
	    pt->const_pool = 1;
	  else if (vi->id == anything_id
		   || vi->id == integer_id)
	    pt->anything = 1;
	}
    }

  /* Instead of doing extra work, simply do not create
     elaborate points-to information for pt_anything pointers.  */
  if (pt->anything)
    return *pt;

  /* Share the final set of variables when possible.  */
  finished_solution = BITMAP_GGC_ALLOC ();
  stats.points_to_sets_created++;

  set_uids_in_ptset (finished_solution, vi->solution, pt, fndecl);
  result = shared_bitmap_lookup (finished_solution);
  if (!result)
    {
      shared_bitmap_add (finished_solution);
      pt->vars = finished_solution;
    }
  else
    {
      pt->vars = result;
      bitmap_clear (finished_solution);
    }

  return *pt;
}

/* Given a pointer variable P, fill in its points-to set.  */

static void
find_what_p_points_to (tree fndecl, tree p)
{
  struct ptr_info_def *pi;
  tree lookup_p = p;
  varinfo_t vi;
  prange vr;
  get_range_query (DECL_STRUCT_FUNCTION (fndecl))->range_of_expr (vr, p);
  bool nonnull = vr.nonzero_p ();

  /* For parameters, get at the points-to set for the actual parm
     decl.  */
  if (TREE_CODE (p) == SSA_NAME
      && SSA_NAME_IS_DEFAULT_DEF (p)
      && (TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
	  || TREE_CODE (SSA_NAME_VAR (p)) == RESULT_DECL))
    lookup_p = SSA_NAME_VAR (p);

  vi = lookup_vi_for_tree (lookup_p);
  if (!vi)
    return;

  pi = get_ptr_info (p);
  pi->pt = find_what_var_points_to (fndecl, vi);
  /* Conservatively set to NULL from PTA (to true). */
  pi->pt.null = 1;
  /* Preserve pointer nonnull globally computed.  */
  if (nonnull)
    set_ptr_nonnull (p);
}


/* Query statistics for points-to solutions.  */

static struct {
  unsigned HOST_WIDE_INT pt_solution_includes_may_alias;
  unsigned HOST_WIDE_INT pt_solution_includes_no_alias;
  unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias;
  unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias;
} pta_stats;

void
dump_pta_stats (FILE *s)
{
  fprintf (s, "\nPTA query stats:\n");
  fprintf (s, "  pt_solution_includes: "
	   HOST_WIDE_INT_PRINT_DEC" disambiguations, "
	   HOST_WIDE_INT_PRINT_DEC" queries\n",
	   pta_stats.pt_solution_includes_no_alias,
	   pta_stats.pt_solution_includes_no_alias
	   + pta_stats.pt_solution_includes_may_alias);
  fprintf (s, "  pt_solutions_intersect: "
	   HOST_WIDE_INT_PRINT_DEC" disambiguations, "
	   HOST_WIDE_INT_PRINT_DEC" queries\n",
	   pta_stats.pt_solutions_intersect_no_alias,
	   pta_stats.pt_solutions_intersect_no_alias
	   + pta_stats.pt_solutions_intersect_may_alias);
}


/* Reset the points-to solution *PT to a conservative default
   (point to anything).  */

void
pt_solution_reset (struct pt_solution *pt)
{
  memset (pt, 0, sizeof (struct pt_solution));
  pt->anything = true;
  pt->null = true;
}

/* Set the points-to solution *PT to point only to the variables
   in VARS.  VARS_CONTAINS_GLOBAL specifies whether that contains
   global variables and VARS_CONTAINS_RESTRICT specifies whether
   it contains restrict tag variables.  */

void
pt_solution_set (struct pt_solution *pt, bitmap vars,
		 bool vars_contains_nonlocal)
{
  memset (pt, 0, sizeof (struct pt_solution));
  pt->vars = vars;
  pt->vars_contains_nonlocal = vars_contains_nonlocal;
  pt->vars_contains_escaped
    = (cfun->gimple_df->escaped.anything
       || bitmap_intersect_p (cfun->gimple_df->escaped.vars, vars));
}

/* Set the points-to solution *PT to point only to the variable VAR.  */

void
pt_solution_set_var (struct pt_solution *pt, tree var)
{
  memset (pt, 0, sizeof (struct pt_solution));
  pt->vars = BITMAP_GGC_ALLOC ();
  bitmap_set_bit (pt->vars, DECL_PT_UID (var));
  pt->vars_contains_nonlocal = is_global_var (var);
  pt->vars_contains_escaped
    = (cfun->gimple_df->escaped.anything
       || bitmap_bit_p (cfun->gimple_df->escaped.vars, DECL_PT_UID (var)));
}

/* Computes the union of the points-to solutions *DEST and *SRC and
   stores the result in *DEST.  This changes the points-to bitmap
   of *DEST and thus may not be used if that might be shared.
   The points-to bitmap of *SRC and *DEST will not be shared after
   this function if they were not before.  */

static void
pt_solution_ior_into (struct pt_solution *dest, struct pt_solution *src)
{
  dest->anything |= src->anything;
  if (dest->anything)
    {
      pt_solution_reset (dest);
      return;
    }

  dest->nonlocal |= src->nonlocal;
  dest->escaped |= src->escaped;
  dest->ipa_escaped |= src->ipa_escaped;
  dest->null |= src->null;
  dest->const_pool |= src->const_pool ;
  dest->vars_contains_nonlocal |= src->vars_contains_nonlocal;
  dest->vars_contains_escaped |= src->vars_contains_escaped;
  dest->vars_contains_escaped_heap |= src->vars_contains_escaped_heap;
  if (!src->vars)
    return;

  if (!dest->vars)
    dest->vars = BITMAP_GGC_ALLOC ();
  bitmap_ior_into (dest->vars, src->vars);
}

/* Return true if the points-to solution *PT is empty.  */

bool
pt_solution_empty_p (const pt_solution *pt)
{
  if (pt->anything
      || pt->nonlocal)
    return false;

  if (pt->vars
      && !bitmap_empty_p (pt->vars))
    return false;

  /* If the solution includes ESCAPED, check if that is empty.  */
  if (pt->escaped
      && !pt_solution_empty_p (&cfun->gimple_df->escaped))
    return false;

  /* If the solution includes ESCAPED, check if that is empty.  */
  if (pt->ipa_escaped
      && !pt_solution_empty_p (&ipa_escaped_pt))
    return false;

  return true;
}

/* Return true if the points-to solution *PT only point to a single var, and
   return the var uid in *UID.  */

bool
pt_solution_singleton_or_null_p (struct pt_solution *pt, unsigned *uid)
{
  if (pt->anything || pt->nonlocal || pt->escaped || pt->ipa_escaped
      || pt->vars == NULL
      || !bitmap_single_bit_set_p (pt->vars))
    return false;

  *uid = bitmap_first_set_bit (pt->vars);
  return true;
}

/* Return true if the points-to solution *PT includes global memory.
   If ESCAPED_LOCAL_P is true then escaped local variables are also
   considered global.  */

bool
pt_solution_includes_global (struct pt_solution *pt, bool escaped_local_p)
{
  if (pt->anything
      || pt->nonlocal
      || pt->vars_contains_nonlocal
      /* The following is a hack to make the malloc escape hack work.
	 In reality we'd need different sets for escaped-through-return
	 and escaped-to-callees and passes would need to be updated.  */
      || pt->vars_contains_escaped_heap)
    return true;

  if (escaped_local_p && pt->vars_contains_escaped)
    return true;

  /* 'escaped' is also a placeholder so we have to look into it.  */
  if (pt->escaped)
    return pt_solution_includes_global (&cfun->gimple_df->escaped,
					escaped_local_p);

  if (pt->ipa_escaped)
    return pt_solution_includes_global (&ipa_escaped_pt,
					escaped_local_p);

  return false;
}

/* Return true if the points-to solution *PT includes the variable
   declaration DECL.  */

static bool
pt_solution_includes_1 (struct pt_solution *pt, const_tree decl)
{
  if (pt->anything)
    return true;

  if (pt->nonlocal
      && is_global_var (decl))
    return true;

  if (pt->vars
      && bitmap_bit_p (pt->vars, DECL_PT_UID (decl)))
    return true;

  /* If the solution includes ESCAPED, check it.  */
  if (pt->escaped
      && pt_solution_includes_1 (&cfun->gimple_df->escaped, decl))
    return true;

  /* If the solution includes ESCAPED, check it.  */
  if (pt->ipa_escaped
      && pt_solution_includes_1 (&ipa_escaped_pt, decl))
    return true;

  return false;
}

bool
pt_solution_includes (struct pt_solution *pt, const_tree decl)
{
  bool res = pt_solution_includes_1 (pt, decl);
  if (res)
    ++pta_stats.pt_solution_includes_may_alias;
  else
    ++pta_stats.pt_solution_includes_no_alias;
  return res;
}

/* Return true if the points-to solution *PT contains a reference to a
   constant pool entry.  */

bool
pt_solution_includes_const_pool (struct pt_solution *pt)
{
  return (pt->const_pool
	  || pt->nonlocal
	  || (pt->escaped && (!cfun || cfun->gimple_df->escaped.const_pool))
	  || (pt->ipa_escaped && ipa_escaped_pt.const_pool));
}

/* Return true if both points-to solutions PT1 and PT2 have a non-empty
   intersection.  */

static bool
pt_solutions_intersect_1 (struct pt_solution *pt1, struct pt_solution *pt2)
{
  if (pt1->anything || pt2->anything)
    return true;

  /* If either points to unknown global memory and the other points to
     any global memory they alias.  */
  if ((pt1->nonlocal
       && (pt2->nonlocal
	   || pt2->vars_contains_nonlocal))
      || (pt2->nonlocal
	  && pt1->vars_contains_nonlocal))
    return true;

  /* If either points to all escaped memory and the other points to
     any escaped memory they alias.  */
  if ((pt1->escaped
       && (pt2->escaped
	   || pt2->vars_contains_escaped))
      || (pt2->escaped
	  && pt1->vars_contains_escaped))
    return true;

  /* Check the escaped solution if required.
     ???  Do we need to check the local against the IPA escaped sets?  */
  if ((pt1->ipa_escaped || pt2->ipa_escaped)
      && !pt_solution_empty_p (&ipa_escaped_pt))
    {
      /* If both point to escaped memory and that solution
	 is not empty they alias.  */
      if (pt1->ipa_escaped && pt2->ipa_escaped)
	return true;

      /* If either points to escaped memory see if the escaped solution
	 intersects with the other.  */
      if ((pt1->ipa_escaped
	   && pt_solutions_intersect_1 (&ipa_escaped_pt, pt2))
	  || (pt2->ipa_escaped
	      && pt_solutions_intersect_1 (&ipa_escaped_pt, pt1)))
	return true;
    }

  /* Now both pointers alias if their points-to solution intersects.  */
  return (pt1->vars
	  && pt2->vars
	  && bitmap_intersect_p (pt1->vars, pt2->vars));
}

bool
pt_solutions_intersect (struct pt_solution *pt1, struct pt_solution *pt2)
{
  bool res = pt_solutions_intersect_1 (pt1, pt2);
  if (res)
    ++pta_stats.pt_solutions_intersect_may_alias;
  else
    ++pta_stats.pt_solutions_intersect_no_alias;
  return res;
}


/* Initialize things necessary to perform PTA.  */

static void
init_alias_vars (void)
{
  use_field_sensitive = (param_max_fields_for_field_sensitive > 1);

  bitmap_obstack_initialize (&pta_obstack);
  bitmap_obstack_initialize (&oldpta_obstack);

  constraints.create (8);
  varmap.create (8);

  memset (&stats, 0, sizeof (stats));
  shared_bitmap_table = new hash_table<shared_bitmap_hasher> (511);

  final_solutions = new hash_map<varinfo_t, pt_solution *>;
  gcc_obstack_init (&final_solutions_obstack);

  init_constraint_builder ();
}

/* 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_build_constraints ();

  /* From the constraints compute the points-to sets.  */
  solve_constraints ();

  if (dump_file && (dump_flags & TDF_STATS))
    dump_sa_stats (dump_file);

  if (dump_file && (dump_flags & TDF_DETAILS))
    dump_sa_points_to_info (dump_file);

  /* 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));

  /* Make sure the ESCAPED solution (which is used as placeholder in
     other solutions) does not reference itself.  This simplifies
     points-to solution queries.  */
  cfun->gimple_df->escaped.escaped = 0;

  /* The ESCAPED_RETURN solution is what contains all memory that needs
     to be considered global.  */
  cfun->gimple_df->escaped_return
    = find_what_var_points_to (cfun->decl, get_varinfo (escaped_return_id));
  cfun->gimple_df->escaped_return.escaped = 1;

  /* Compute the points-to sets for pointer SSA_NAMEs.  */
  unsigned i;
  tree ptr;

  FOR_EACH_SSA_NAME (i, ptr, cfun)
    {
      if (POINTER_TYPE_P (TREE_TYPE (ptr)))
	find_what_p_points_to (cfun->decl, ptr);
    }

  /* Compute the call-used/clobbered sets.  */
  FOR_EACH_BB_FN (bb, cfun)
    {
      gimple_stmt_iterator gsi;

      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
	{
	  gcall *stmt;
	  struct pt_solution *pt;

	  stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
	  if (!stmt)
	    continue;

	  pt = gimple_call_use_set (stmt);
	  if (gimple_call_flags (stmt) & ECF_CONST)
	    memset (pt, 0, sizeof (struct pt_solution));
	  else
	    {
	      bool uses_global_memory = true;
	      bool reads_global_memory = true;

	      determine_global_memory_access (stmt, NULL,
					      &reads_global_memory,
					      &uses_global_memory);
	      if ((vi = lookup_call_use_vi (stmt)) != NULL)
		{
		  *pt = find_what_var_points_to (cfun->decl, vi);
		  /* Escaped (and thus nonlocal) variables are always
		     implicitly used by calls.  */
		  /* ???  ESCAPED can be empty even though NONLOCAL
		     always escaped.  */
		  if (uses_global_memory)
		    {
		      pt->nonlocal = 1;
		      pt->escaped = 1;
		    }
		}
	      else if (uses_global_memory)
		{
		  /* If there is nothing special about this call then
		     we have made everything that is used also escape.  */
		  *pt = cfun->gimple_df->escaped;
		  pt->nonlocal = 1;
		}
	      else
		memset (pt, 0, sizeof (struct pt_solution));
	    }

	  pt = gimple_call_clobber_set (stmt);
	  if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
	    memset (pt, 0, sizeof (struct pt_solution));
	  else
	    {
	      bool writes_global_memory = true;

	      determine_global_memory_access (stmt, &writes_global_memory,
					      NULL, NULL);

	      if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
		{
		  *pt = find_what_var_points_to (cfun->decl, vi);
		  /* Escaped (and thus nonlocal) variables are always
		     implicitly clobbered by calls.  */
		  /* ???  ESCAPED can be empty even though NONLOCAL
		     always escaped.  */
		  if (writes_global_memory)
		    {
		      pt->nonlocal = 1;
		      pt->escaped = 1;
		    }
		}
	      else if (writes_global_memory)
		{
		  /* If there is nothing special about this call then
		     we have made everything that is used also escape.  */
		  *pt = cfun->gimple_df->escaped;
		  pt->nonlocal = 1;
		}
	      else
		memset (pt, 0, sizeof (struct pt_solution));
	    }
	}
    }

  timevar_pop (TV_TREE_PTA);
}

/* Delete created points-to sets.  */

static void
delete_points_to_sets (void)
{
  delete shared_bitmap_table;
  shared_bitmap_table = NULL;
  if (dump_file && (dump_flags & TDF_STATS))
    fprintf (dump_file, "Points to sets created:%d\n",
	     stats.points_to_sets_created);

  bitmap_obstack_release (&pta_obstack);
  constraints.release ();

  free (var_rep);

  varmap.release ();
  variable_info_pool.release ();

  delete final_solutions;
  obstack_free (&final_solutions_obstack, NULL);

  delete_constraint_builder ();
}


struct vls_data
{
  unsigned short clique;
  bool escaped_p;
  bitmap rvars;
};

/* Mark "other" loads and stores as belonging to CLIQUE and with
   base zero.  */

static bool
visit_loadstore (gimple *, tree base, tree ref, void *data)
{
  unsigned short clique = ((vls_data *) data)->clique;
  bitmap rvars = ((vls_data *) data)->rvars;
  bool escaped_p = ((vls_data *) data)->escaped_p;
  if (TREE_CODE (base) == MEM_REF
      || TREE_CODE (base) == TARGET_MEM_REF)
    {
      tree ptr = TREE_OPERAND (base, 0);
      if (TREE_CODE (ptr) == SSA_NAME)
	{
	  /* For parameters, get at the points-to set for the actual parm
	     decl.  */
	  if (SSA_NAME_IS_DEFAULT_DEF (ptr)
	      && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
		  || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL))
	    ptr = SSA_NAME_VAR (ptr);

	  /* We need to make sure 'ptr' doesn't include any of
	     the restrict tags we added bases for in its points-to set.  */
	  varinfo_t vi = lookup_vi_for_tree (ptr);
	  if (! vi)
	    return false;

	  vi = get_varinfo (var_rep[vi->id]);
	  if (bitmap_intersect_p (rvars, vi->solution)
	      || (escaped_p && bitmap_bit_p (vi->solution, escaped_id)))
	    return false;
	}

      /* Do not overwrite existing cliques (that includes clique, base
	 pairs we just set).  */
      if (MR_DEPENDENCE_CLIQUE (base) == 0)
	{
	  MR_DEPENDENCE_CLIQUE (base) = clique;
	  MR_DEPENDENCE_BASE (base) = 0;
	}
    }

  /* For plain decl accesses see whether they are accesses to globals
     and rewrite them to MEM_REFs with { clique, 0 }.  */
  if (VAR_P (base)
      && is_global_var (base)
      /* ???  We can't rewrite a plain decl with the walk_stmt_load_store
	 ops callback.  */
      && base != ref)
    {
      tree *basep = &ref;
      while (handled_component_p (*basep))
	basep = &TREE_OPERAND (*basep, 0);
      gcc_assert (VAR_P (*basep));
      tree ptr = build_fold_addr_expr (*basep);
      tree zero = build_int_cst (TREE_TYPE (ptr), 0);
      *basep = build2 (MEM_REF, TREE_TYPE (*basep), ptr, zero);
      MR_DEPENDENCE_CLIQUE (*basep) = clique;
      MR_DEPENDENCE_BASE (*basep) = 0;
    }

  return false;
}

struct msdi_data {
  tree ptr;
  unsigned short *clique;
  unsigned short *last_ruid;
  varinfo_t restrict_var;
};

/* If BASE is a MEM_REF then assign a clique, base pair to it, updating
   CLIQUE, *RESTRICT_VAR and LAST_RUID as passed via DATA.
   Return whether dependence info was assigned to BASE.  */

static bool
maybe_set_dependence_info (gimple *, tree base, tree, void *data)
{
  tree ptr = ((msdi_data *)data)->ptr;
  unsigned short &clique = *((msdi_data *)data)->clique;
  unsigned short &last_ruid = *((msdi_data *)data)->last_ruid;
  varinfo_t restrict_var = ((msdi_data *)data)->restrict_var;
  if ((TREE_CODE (base) == MEM_REF
       || TREE_CODE (base) == TARGET_MEM_REF)
      && TREE_OPERAND (base, 0) == ptr)
    {
      /* Do not overwrite existing cliques.  This avoids overwriting dependence
	 info inlined from a function with restrict parameters inlined
	 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)
	    {
	      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)
    {
      tree ptr = ssa_name (i);
      if (!ptr || !POINTER_TYPE_P (TREE_TYPE (ptr)))
	continue;

      /* Avoid all this when ptr is not dereferenced?  */
      tree p = ptr;
      if (SSA_NAME_IS_DEFAULT_DEF (ptr)
	  && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
	      || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL))
	p = SSA_NAME_VAR (ptr);
      varinfo_t vi = lookup_vi_for_tree (p);
      if (!vi)
	continue;
      vi = get_varinfo (var_rep[vi->id]);
      bitmap_iterator bi;
      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
		  && restrict_var != oi)
		{
		  if (dump_file && (dump_flags & TDF_DETAILS))
		    {
		      fprintf (dump_file, "found restrict pointed-to "
			       "for ");
		      print_generic_expr (dump_file, ptr);
		      fprintf (dump_file, " but not exclusively\n");
		    }
		  restrict_var = NULL;
		  break;
		}
	      restrict_var = oi;
	    }
	  /* NULL is the only other valid points-to entry.  */
	  else if (oi->id != nothing_id)
	    {
	      restrict_var = NULL;
	      break;
	    }
	}
      /* Ok, found that ptr must(!) point to a single(!) restrict
	 variable.  */
      /* ???  PTA isn't really a proper propagation engine to compute
	 this property.
	 ???  We could handle merging of two restricts by unifying them.  */
      if (restrict_var)
	{
	  /* Now look at possible dereferences of ptr.  */
	  imm_use_iterator ui;
	  gimple *use_stmt;
	  bool used = false;
	  msdi_data data = { ptr, &clique, &last_ruid, restrict_var };
	  FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr)
	    used |= walk_stmt_load_store_ops (use_stmt, &data,
					      maybe_set_dependence_info,
					      maybe_set_dependence_info);
	  if (used)
	    {
	      /* 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 (var_rep[escaped_id]);
	      if (bitmap_bit_p (escaped->solution, restrict_var->id))
		escaped_p = true;
	    }
	}
    }

  if (clique != 0)
    {
      /* Assign the BASE id zero to all accesses not based on a restrict
	 pointer.  That way they get disambiguated against restrict
	 accesses but not against each other.  */
      /* ???  For restricts derived from globals (thus not incoming
	 parameters) we can't restrict scoping properly thus the following
	 is too aggressive there.  For now we have excluded those globals from
	 getting into the MR_DEPENDENCE machinery.  */
      vls_data data = { clique, escaped_p, rvars };
      basic_block bb;
      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, &data,
				      visit_loadstore, visit_loadstore);
	  }
    }

  BITMAP_FREE (rvars);
}


/* Compute points-to information for every SSA_NAME pointer in the
   current function and compute the transitive closure of escaped
   variables to re-initialize the call-clobber states of local variables.  */

unsigned int
compute_may_aliases (void)
{
  if (cfun->gimple_df->ipa_pta)
    {
      if (dump_file)
	{
	  fprintf (dump_file, "\nNot re-computing points-to information "
		   "because IPA points-to information is available.\n\n");

	  /* But still dump what we have remaining it.  */
	  if (dump_flags & (TDF_DETAILS|TDF_ALIAS))
	    dump_alias_info (dump_file);
	}

      return 0;
    }

  /* For each pointer P_i, determine the sets of variables that P_i may
     point-to.  Compute the reachability set of escaped and call-used
     variables.  */
  compute_points_to_sets ();

  /* Debugging dumps.  */
  if (dump_file && (dump_flags & (TDF_DETAILS|TDF_ALIAS)))
    dump_alias_info (dump_file);

  /* Compute restrict-based memory disambiguations.  */
  compute_dependence_clique ();

  /* Deallocate memory used by aliasing data structures and the internal
     points-to solution.  */
  delete_points_to_sets ();

  gcc_assert (!need_ssa_update_p (cfun));

  return 0;
}

/* A dummy pass to cause points-to information to be computed via
   TODO_rebuild_alias.  */

namespace {

const pass_data pass_data_build_alias =
{
  GIMPLE_PASS, /* type */
  "alias", /* name */
  OPTGROUP_NONE, /* optinfo_flags */
  TV_NONE, /* tv_id */
  ( PROP_cfg | PROP_ssa ), /* properties_required */
  0, /* properties_provided */
  0, /* properties_destroyed */
  0, /* todo_flags_start */
  TODO_rebuild_alias, /* todo_flags_finish */
};

class pass_build_alias : public gimple_opt_pass
{
public:
  pass_build_alias (gcc::context *ctxt)
    : gimple_opt_pass (pass_data_build_alias, ctxt)
  {}

  /* opt_pass methods: */
  bool gate (function *) final override { return flag_tree_pta; }

}; // class pass_build_alias

} // anon namespace

gimple_opt_pass *
make_pass_build_alias (gcc::context *ctxt)
{
  return new pass_build_alias (ctxt);
}

/* A dummy pass to cause points-to information to be computed via
   TODO_rebuild_alias.  */

namespace {

const pass_data pass_data_build_ealias =
{
  GIMPLE_PASS, /* type */
  "ealias", /* name */
  OPTGROUP_NONE, /* optinfo_flags */
  TV_NONE, /* tv_id */
  ( PROP_cfg | PROP_ssa ), /* properties_required */
  0, /* properties_provided */
  0, /* properties_destroyed */
  0, /* todo_flags_start */
  TODO_rebuild_alias, /* todo_flags_finish */
};

class pass_build_ealias : public gimple_opt_pass
{
public:
  pass_build_ealias (gcc::context *ctxt)
    : gimple_opt_pass (pass_data_build_ealias, ctxt)
  {}

  /* opt_pass methods: */
  bool gate (function *) final override { return flag_tree_pta; }

}; // class pass_build_ealias

} // anon namespace

gimple_opt_pass *
make_pass_build_ealias (gcc::context *ctxt)
{
  return new pass_build_ealias (ctxt);
}


/* IPA PTA solutions for ESCAPED.  */
struct pt_solution ipa_escaped_pt
  = { true, false, false, false, false, false,
      false, false, false, false, false, NULL };


/* Execute the driver for IPA PTA.  */
static unsigned int
ipa_pta_execute (void)
{
  struct cgraph_node *node;

  in_ipa_mode = 1;

  init_alias_vars ();

  if (dump_file && (dump_flags & TDF_DETAILS))
    {
      symtab->dump (dump_file);
      fprintf (dump_file, "\n");
    }

  if (dump_file && (dump_flags & TDF_DETAILS))
    {
      fprintf (dump_file, "Generating generic constraints\n\n");
      dump_constraints (dump_file, 0);
      fprintf (dump_file, "\n");
    }

  ipa_build_constraints ();

  /* From the constraints compute the points-to sets.  */
  solve_constraints ();

  if (dump_file && (dump_flags & TDF_STATS))
    dump_sa_stats (dump_file);

  if (dump_file && (dump_flags & TDF_DETAILS))
    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 (var_rep[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 (var_rep[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.  */
  ipa_escaped_pt = find_what_var_points_to (NULL, get_varinfo (escaped_id));

  /* Make sure the ESCAPED solution (which is used as placeholder in
     other solutions) does not reference itself.  This simplifies
     points-to solution queries.  */
  ipa_escaped_pt.ipa_escaped = 0;

  /* Assign the points-to sets to the SSA names in the unit.  */
  FOR_EACH_DEFINED_FUNCTION (node)
    {
      tree ptr;
      struct function *fn;
      unsigned i;
      basic_block bb;

      /* Nodes without a body in this partition are not interesting.  */
      if (!node->has_gimple_body_p ()
	  || node->in_other_partition
	  || node->clone_of)
	continue;

      fn = DECL_STRUCT_FUNCTION (node->decl);

      /* Compute the points-to sets for pointer SSA_NAMEs.  */
      FOR_EACH_VEC_ELT (*fn->gimple_df->ssa_names, i, ptr)
	{
	  if (ptr
	      && POINTER_TYPE_P (TREE_TYPE (ptr)))
	    find_what_p_points_to (node->decl, ptr);
	}

      /* Compute the call-use and call-clobber sets for indirect calls
	 and calls to external functions.  */
      FOR_EACH_BB_FN (bb, fn)
	{
	  gimple_stmt_iterator gsi;

	  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
	    {
	      gcall *stmt;
	      struct pt_solution *pt;
	      varinfo_t vi, fi;
	      tree decl;

	      stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
	      if (!stmt)
		continue;

	      /* Handle direct calls to functions with body.  */
	      decl = gimple_call_fndecl (stmt);

	      {
		tree called_decl = NULL_TREE;
		if (gimple_call_builtin_p (stmt, BUILT_IN_GOMP_PARALLEL))
		  called_decl = TREE_OPERAND (gimple_call_arg (stmt, 0), 0);
		else if (gimple_call_builtin_p (stmt, BUILT_IN_GOACC_PARALLEL))
		  called_decl = TREE_OPERAND (gimple_call_arg (stmt, 1), 0);

		if (called_decl != NULL_TREE
		    && !fndecl_maybe_in_other_partition (called_decl))
		  decl = called_decl;
	      }

	      if (decl
		  && (fi = lookup_vi_for_tree (decl))
		  && fi->is_fn_info)
		{
		  *gimple_call_clobber_set (stmt)
		     = find_what_var_points_to
			 (node->decl, first_vi_for_offset (fi, fi_clobbers));
		  *gimple_call_use_set (stmt)
		     = find_what_var_points_to
			 (node->decl, first_vi_for_offset (fi, fi_uses));
		}
	      /* Handle direct calls to external functions.  */
	      else if (decl && (!fi || fi->decl))
		{
		  pt = gimple_call_use_set (stmt);
		  if (gimple_call_flags (stmt) & ECF_CONST)
		    memset (pt, 0, sizeof (struct pt_solution));
		  else if ((vi = lookup_call_use_vi (stmt)) != NULL)
		    {
		      *pt = find_what_var_points_to (node->decl, vi);
		      /* Escaped (and thus nonlocal) variables are always
			 implicitly used by calls.  */
		      /* ???  ESCAPED can be empty even though NONLOCAL
			 always escaped.  */
		      pt->nonlocal = 1;
		      pt->ipa_escaped = 1;
		    }
		  else
		    {
		      /* If there is nothing special about this call then
			 we have made everything that is used also escape.  */
		      *pt = ipa_escaped_pt;
		      pt->nonlocal = 1;
		    }

		  pt = gimple_call_clobber_set (stmt);
		  if (gimple_call_flags (stmt) &
		      (ECF_CONST|ECF_PURE|ECF_NOVOPS))
		    memset (pt, 0, sizeof (struct pt_solution));
		  else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
		    {
		      *pt = find_what_var_points_to (node->decl, vi);
		      /* Escaped (and thus nonlocal) variables are always
			 implicitly clobbered by calls.  */
		      /* ???  ESCAPED can be empty even though NONLOCAL
			 always escaped.  */
		      pt->nonlocal = 1;
		      pt->ipa_escaped = 1;
		    }
		  else
		    {
		      /* If there is nothing special about this call then
			 we have made everything that is used also escape.  */
		      *pt = ipa_escaped_pt;
		      pt->nonlocal = 1;
		    }
		}
	      /* Handle indirect calls.  */
	      else if ((fi = get_fi_for_callee (stmt)))
		{
		  /* We need to accumulate all clobbers/uses of all possible
		     callees.  */
		  fi = get_varinfo (var_rep[fi->id]);
		  /* If we cannot constrain the set of functions we'll end up
		     calling we end up using/clobbering everything.  */
		  if (bitmap_bit_p (fi->solution, anything_id)
		      || bitmap_bit_p (fi->solution, nonlocal_id)
		      || bitmap_bit_p (fi->solution, escaped_id))
		    {
		      pt_solution_reset (gimple_call_clobber_set (stmt));
		      pt_solution_reset (gimple_call_use_set (stmt));
		    }
		  else
		    {
		      bitmap_iterator bi;
		      unsigned i;
		      struct pt_solution *uses, *clobbers;

		      uses = gimple_call_use_set (stmt);
		      clobbers = gimple_call_clobber_set (stmt);
		      memset (uses, 0, sizeof (struct pt_solution));
		      memset (clobbers, 0, sizeof (struct pt_solution));
		      EXECUTE_IF_SET_IN_BITMAP (fi->solution, 0, i, bi)
			{
			  struct pt_solution sol;

			  vi = get_varinfo (i);
			  if (!vi->is_fn_info)
			    {
			      /* ???  We could be more precise here?  */
			      uses->nonlocal = 1;
			      uses->ipa_escaped = 1;
			      clobbers->nonlocal = 1;
			      clobbers->ipa_escaped = 1;
			      continue;
			    }

			  if (!uses->anything)
			    {
			      sol = find_what_var_points_to
				      (node->decl,
				       first_vi_for_offset (vi, fi_uses));
			      pt_solution_ior_into (uses, &sol);
			    }
			  if (!clobbers->anything)
			    {
			      sol = find_what_var_points_to
				      (node->decl,
				       first_vi_for_offset (vi, fi_clobbers));
			      pt_solution_ior_into (clobbers, &sol);
			    }
			}
		    }
		}
	      else
		gcc_unreachable ();
	    }
	}

      fn->gimple_df->ipa_pta = true;

      /* We have to re-set the final-solution cache after each function
	 because what is a "global" is dependent on function context.  */
      final_solutions->empty ();
      obstack_free (&final_solutions_obstack, NULL);
      gcc_obstack_init (&final_solutions_obstack);
    }

  delete_points_to_sets ();

  in_ipa_mode = 0;

  return 0;
}

namespace {

const pass_data pass_data_ipa_pta =
{
  SIMPLE_IPA_PASS, /* type */
  "pta", /* name */
  OPTGROUP_NONE, /* optinfo_flags */
  TV_IPA_PTA, /* tv_id */
  0, /* properties_required */
  0, /* properties_provided */
  0, /* properties_destroyed */
  0, /* todo_flags_start */
  0, /* todo_flags_finish */
};

class pass_ipa_pta : public simple_ipa_opt_pass
{
public:
  pass_ipa_pta (gcc::context *ctxt)
    : simple_ipa_opt_pass (pass_data_ipa_pta, ctxt)
  {}

  /* opt_pass methods: */
  bool gate (function *) final override
    {
      return (optimize
	      && flag_ipa_pta
	      /* Don't bother doing anything if the program has errors.  */
	      && !seen_error ());
    }

  opt_pass * clone () final override { return new pass_ipa_pta (m_ctxt); }

  unsigned int execute (function *) final override
  {
    return ipa_pta_execute ();
  }

}; // class pass_ipa_pta

} // anon namespace

simple_ipa_opt_pass *
make_pass_ipa_pta (gcc::context *ctxt)
{
  return new pass_ipa_pta (ctxt);
}