tree-alias-common.c   [plain text]

/* Tree based points-to analysis
   Copyright (C) 2002, 2003 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 2 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; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "ggc.h"
#include "tree-alias-type.h"
#include "bitmap.h"
#include "tree-alias-common.h"
/* If we have andersen's points-to analysis, include it. */
#ifdef HAVE_BANSHEE
#include "tree-alias-ander.h"
#endif
#include "flags.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "output.h"
#include "errors.h"
#include "expr.h"
#include "diagnostic.h"
#include "tree.h"
#include "c-common.h"
#include "tree-flow.h"
#include "tree-inline.h"
#include "varray.h"
#include "c-tree.h"
#include "tree-gimple.h"
#include "hashtab.h"
#include "function.h"
#include "cgraph.h"
#include "tree-pass.h"
#include "timevar.h"

/*  This file contains the implementation of the common parts of the
    tree points-to analysis infrastructure.
    
    Overview:
    
    This file contains the points-to analysis driver.  It does two main things:
    1. Keeps track of the PTA data for each variable (IE the data each
    specific PTA implementation wants to keep associated with a
    variable).
    2. Walks the function trees, calling the appropriate functions that
    each PTA implementation has implemented.
    
    In order to speed up PTA queries, the PTA specific data is stored
    in the tree for *_DECL's, in DECL_PTA_ALIASVAR.  This way, we only
    need to use the hash table for non-DECL's.  */
#define FIELD_BASED 0

/*  Array of all created alias_vars.
    Note that this should contain all the alias_vars we wanted
    marked during GC.  */
static GTY((param_is (union alias_var_def))) varray_type alias_vars = NULL;
struct tree_alias_ops *current_alias_ops;

/*  Array of local (to a function) alias_vars.
    Note that this should contain all the alias_vars that are
    local to this function.  We delete these from alias_vars before
    collection.  */
static GTY(()) varray_type local_alias_vars;
static GTY(()) varray_type local_alias_varnums;
tree pta_global_var;
static bitmap addrargs;						 
static alias_var get_alias_var_decl (tree);
static alias_var get_alias_var (tree);
static void find_func_aliases (tree);
static void deal_with_call_aliasing (tree, alias_var);
static alias_var create_fun_alias_var_ptf (tree, tree);
static alias_var create_fun_alias_var (tree, int);
static alias_var create_alias_var (tree);
static void intra_function_call (varray_type);
static void get_values_from_constructor (tree, varray_type *, bitmap, int *);
static bool call_may_clobber (tree);
static bool call_may_return (tree);

/* Return true if a EXPR, which is a CALL_EXPR, may clobber variables.  */

static bool
call_may_clobber (tree expr)
{
  int flags;

  if (TREE_CODE (expr) != CALL_EXPR)
    return false;

  flags = call_expr_flags (expr);
  return (! (flags & (ECF_CONST | ECF_PURE | ECF_NORETURN)));
}

/* Return true if a EXPR, which is a CALL_EXPR, may return.  */

static bool
call_may_return (tree expr)
{
  int flags;
  
  if (TREE_CODE (expr) != CALL_EXPR)
    return false;

  flags = call_expr_flags (expr);
  return ! (flags & ECF_NORETURN);
}

/*  Get the alias_var for DECL.  
    Creates the alias_var if it does not exist already. Also
    handles FUNCTION_DECL properly.  */

static alias_var
get_alias_var_decl (tree decl)
{
  alias_var newvar;
  if (TREE_CODE (decl) == FIELD_DECL)
    abort ();
  if (DECL_P (decl))
    {
      if (DECL_PTA_ALIASVAR (decl))
	return DECL_PTA_ALIASVAR (decl);
    }

  if (TREE_CODE (decl) == FUNCTION_DECL)
    newvar = create_fun_alias_var  (decl, 0);
  else
    {
      newvar = create_alias_var (decl);
      /* Assign globals to global var for purposes of intraprocedural
	 analysis. */
      if ((DECL_CONTEXT (decl) == NULL 
	   || TREE_PUBLIC (decl)
	   || TREE_STATIC (decl)
	   || decl_function_context (decl) == NULL) 
	  && decl != pta_global_var)
	{
	  current_alias_ops->addr_assign (current_alias_ops, 
					  get_alias_var (pta_global_var), 
					  newvar);
	  /* If the global has some DECL_INITIAL, we need to process
	     it here. */
	  if (DECL_INITIAL (decl))
	    find_func_aliases (decl);
	}
    }

  if (!current_alias_ops->ip)
    {
      if (!current_alias_ops->ip_partial
	  || (TREE_CODE (decl) != FUNCTION_DECL
	      && TREE_CODE (decl) != PARM_DECL))
	{
	  VARRAY_PUSH_INT (local_alias_varnums, ALIAS_VAR_VARNUM (newvar));
	  VARRAY_PUSH_TREE (local_alias_vars, decl);
	}
    }
  return newvar;
}

/* Get the alias_var for an expression EXPR.
   Note that this function expects to only be handed a RHS or LHS, not
   a MODIFY_EXPR.  */

static alias_var
get_alias_var (tree expr)
{
  /* If it's a decl, get the alias var of the decl. We farm this off
     to get_alias_var_decl so it can abort if the alias var doesn't
     exist, and in case something else *knows* it has a decl, and
     wants the alias var. */

  if (DECL_P (expr))
    return get_alias_var_decl (expr);

  /* True constants have no aliases (unless modifiable strings are on,
     in which case i don't think we'll end up with a STRING_CST anyway) */
  if (TREE_CODE_CLASS (TREE_CODE (expr)) == 'c')
    return NULL;


  switch (TREE_CODE (expr))
    {
    case ARRAY_REF:
      {
	/* Find the first non-array ref, and return it's alias
	   variable */
	tree p;
	for (p = expr; TREE_CODE (p) == ARRAY_REF;
	     p = TREE_OPERAND (p, 0));
	return get_alias_var (p);
      }
      break;
    case COMPONENT_REF:
      {
#if FIELD_BASED
	bool safe = true;
	tree p;
	for (p = expr; 
	     TREE_CODE (p) == COMPONENT_REF || TREE_CODE (p) == INDIRECT_REF;
	     p = TREE_OPERAND (p, 0))
	  {
	    if (TREE_CODE (TREE_TYPE (p)) == UNION_TYPE 
		|| TREE_CODE (TREE_TYPE (p)) == QUAL_UNION_TYPE)
	      {
		safe = false;
		break;
	      }
	  }
	if (!safe)
	  {
	    for (p = expr; TREE_CODE (p) == COMPONENT_REF;
		 p = TREE_OPERAND (p, 0));
	    return get_alias_var (p);
	  }
	else
	  {
	    return get_alias_var (TREE_OPERAND (expr, 1));
	  }
#else
        /* Find the first non-component ref, and return its alias variable. */
	tree p;
	for (p = expr; TREE_CODE (p) == COMPONENT_REF;
	     p = TREE_OPERAND (p, 0));
	return get_alias_var (p);
#endif
      }
      break;
    case REALPART_EXPR:
    case IMAGPART_EXPR:
    case NOP_EXPR:
    case CONVERT_EXPR:
    case FIX_TRUNC_EXPR:
    case FIX_CEIL_EXPR:
    case FIX_FLOOR_EXPR:
    case FIX_ROUND_EXPR:
    case ADDR_EXPR:
    case INDIRECT_REF:
    case BIT_FIELD_REF:
      /* If it's a ref or cast or conversion of something, get the
         alias var of the something. */
      return get_alias_var (TREE_OPERAND (expr, 0));
      break;

    default:
      return NULL;
    }
}

/*  Perform conservative aliasing for an intraprocedural mode function
    call.  ARGS are the arguments that were passed to that function
    call.  */

static void
intra_function_call (varray_type args)
{
  size_t l = VARRAY_ACTIVE_SIZE (args);
  size_t i;
  alias_var av = get_alias_var (pta_global_var);

  /* We assume assignments among the actual parameters. */
  for (i = 0; i < l; i++)
    {
      alias_var argi = VARRAY_GENERIC_PTR (args, i);
      size_t j;
      for (j = 0; j < l; j++)
	{
	  alias_var argj;
	  if (i == j)
	    continue;
	  argj = VARRAY_GENERIC_PTR (args, j);
	  /* Restricted pointers can't be aliased with other
	     restricted pointers. */
	  if (!TYPE_RESTRICT (TREE_TYPE (ALIAS_VAR_DECL (argi)))
	      || !TYPE_RESTRICT (TREE_TYPE (ALIAS_VAR_DECL (argj))))
	    /* Do a bit of TBAA to avoid pointless assignments. */
	    if (alias_sets_conflict_p (get_alias_set (ALIAS_VAR_DECL (argi)),
				       get_alias_set (ALIAS_VAR_DECL (argj))))	      
	      current_alias_ops->simple_assign (current_alias_ops, argi, argj);
	}
    }
  /* We assume that an actual parameter can point to any global. */
  for (i = 0; i < l; i++)
    {
      alias_var argav = VARRAY_GENERIC_PTR (args, i);
      /* Restricted pointers can't be aliased with other
	 restricted pointers. */
      if (!TYPE_RESTRICT (TREE_TYPE (ALIAS_VAR_DECL (argav)))
	  || !TYPE_RESTRICT (TREE_TYPE (ALIAS_VAR_DECL (av))))
	{
	  /* Arguments can alias globals, and whatever they point to
	     can point to a global as well. */
	  current_alias_ops->simple_assign (current_alias_ops, argav, av);
	}
    }
}

/* Put all pointers in a constructor in an array.  */

static void
get_values_from_constructor (tree constructor, varray_type *vals, 
			     bitmap addrargs, int *i)
{
  tree elt_list;
  switch (TREE_CODE (constructor))
    {
    case CONSTRUCTOR:
      {
	for (elt_list = CONSTRUCTOR_ELTS (constructor);
	     elt_list;
	     elt_list = TREE_CHAIN (elt_list))
	  {
	    tree value = TREE_VALUE (elt_list);
	    if (TREE_CODE (value) == TREE_LIST
		|| TREE_CODE (value) == CONSTRUCTOR)
	      {
		get_values_from_constructor (value, vals, addrargs, i);			      }
	    else
	      {
		alias_var aav;
		aav = get_alias_var (value);
		if (aav)
		  VARRAY_PUSH_GENERIC_PTR (*vals, aav);
		if (TREE_CODE (value) == ADDR_EXPR)
		  bitmap_set_bit (addrargs, *i);
		*i = *i + 1;
	      }
	  }
      }
      break;
    case TREE_LIST:
      for (elt_list = constructor;
	   elt_list;
	   elt_list = TREE_CHAIN (elt_list))
	{
	  get_values_from_constructor (TREE_VALUE (elt_list), vals, addrargs, i);
	}
      break;
    default:
      abort();
    }
}

/* Deal with the possible return values of a call that we don't have
   actual PTA info about.  */

static void
deal_with_call_aliasing (tree callargs, alias_var lhsAV)
{
  tree arg, argp;
  
  for (argp = callargs;
       argp;
       argp = TREE_CHAIN (argp))
    {
      arg = TREE_VALUE (argp);
      /* If we take the address of a variable directly in the
	 argument, the return value could be the address of that
	 variable.  */ 
      if (TREE_CODE (arg) == ADDR_EXPR)
	current_alias_ops->addr_assign (current_alias_ops, lhsAV,
					get_alias_var (arg));
      /* If we pass in a pointer, we could return that pointer.  */
      else if (POINTER_TYPE_P (TREE_TYPE (arg)))
	{
	  alias_var argtv = get_alias_var (arg);
	  if (argtv)
	    current_alias_ops->simple_assign (current_alias_ops, lhsAV,
					      argtv);
	}
    }
}

/* Find the operand of the component ref that actually is doing
   something to the DECL  */
static tree
find_op_of_decl (tree cref)
{
  while (!DECL_P (TREE_OPERAND (cref, 0)))
    {
      cref = TREE_OPERAND (cref, 0);
    }
  return cref;
}


/*  Tree walker that is the heart of the aliasing infrastructure.
    TP is a pointer to the current tree.
    WALK_SUBTREES specifies whether to continue traversing subtrees or
    not.
    Returns NULL_TREE when we should stop.
    
    This function is the main part of the aliasing infrastructure. It
    walks the trees, calling the appropriate alias analyzer functions to process
    various statements.  */

static void
find_func_aliases (tree stp)
{
  if (TREE_CODE (stp) == RETURN_EXPR)
    {
      stp = TREE_OPERAND (stp, 0);
      if (!stp)
	return;
    }
  
  if (TREE_CODE (stp) == MODIFY_EXPR
      || (DECL_P (stp) && DECL_INITIAL (stp) != NULL_TREE ))
    {
      tree op0, op1;
      alias_var lhsAV = NULL;
      alias_var rhsAV = NULL;

      if (DECL_P (stp))
	{
	  op0 = stp;
	  op1 = DECL_INITIAL (stp);
	}
      else
	{
	  op0 = TREE_OPERAND (stp, 0);
	  op1 = TREE_OPERAND (stp, 1);
	}
      /* lhsAV should always have an alias variable */
      lhsAV = get_alias_var (op0);
      if (!lhsAV)
	return;
      /* rhsAV might not have one, c.f. c = 5 */
      rhsAV = get_alias_var (op1);
#if !FIELD_BASED
      while (TREE_CODE (op1) == COMPONENT_REF 
	     && TREE_CODE (TREE_OPERAND (op1, 0)) == COMPONENT_REF)
	{
	  op1 = TREE_OPERAND (op1, 0);
	}
      while (TREE_CODE (op1) == BIT_FIELD_REF)
	{
	  op1 = TREE_OPERAND (op1, 0);
	}
      /* Take care of fact that we may have multi-level component
	 refs. */ 
      if (TREE_CODE (op1) == COMPONENT_REF)
	op1 = find_op_of_decl (op1);
#endif
      
      /* You would think we could test rhsAV at the top, rather than
	 50 separate times, but we can't, because it can be NULL for
	 operator assignments, where we'd still collect the individual
	 alias vars for the operator. */

      /* Note that structures are treated as a single alias
	 variable, since we can disambiguate based on TBAA first,
	 and fall back on points-to. */
      /* x = <something> */
      if (is_gimple_variable (op0))
	{
	  /* x = y */
	  if (is_gimple_variable (op1))
	    {
	      if (rhsAV != NULL)
		current_alias_ops->simple_assign (current_alias_ops, lhsAV,
						  rhsAV);
	    }
	  /* x = foo.y */
	  else if (TREE_CODE (op1) == COMPONENT_REF 
		   && DECL_P (TREE_OPERAND (op1, 0)))
	    {
	         if (rhsAV != NULL)
		current_alias_ops->simple_assign (current_alias_ops, lhsAV,
						  rhsAV);
	    }
	  /* x = (cast) [maybe-addr-expr] y */
	  else if (is_gimple_cast (op1))
	    {
	      tree stripped_op1 = op1;
	      STRIP_NOPS (stripped_op1);
	      if (rhsAV != NULL)
		{
		  if (TREE_CODE (stripped_op1) == ADDR_EXPR)
		    current_alias_ops->addr_assign (current_alias_ops, lhsAV, 
						    rhsAV);
		  else
		    current_alias_ops->simple_assign (current_alias_ops, lhsAV,
						      rhsAV);
		}
	    }
	  /* x = *y or x = foo->y */
	  else if (TREE_CODE (op1) == INDIRECT_REF 
		   || TREE_CODE (op1) == ARRAY_REF
		   || (TREE_CODE (op1) == COMPONENT_REF
		       && TREE_CODE (TREE_OPERAND (op1, 0)) == INDIRECT_REF))
	    {
	      if (rhsAV != NULL)
		current_alias_ops->ptr_assign (current_alias_ops, lhsAV,
					       rhsAV);
	    }
	  /* x = &y = x = &foo.y */
	  else if (TREE_CODE (op1) == ADDR_EXPR)
	    {
	      if (rhsAV != NULL)
		current_alias_ops->addr_assign (current_alias_ops, lhsAV,
						rhsAV);
	    }
	  /* x = func(...) */
	  else if (TREE_CODE (op1) == CALL_EXPR)
	    {
	      /* Heap assignment. These are __attribute__ malloc or
		 something, i'll deal with it later. */
	      if (0)
		{}
	      else
		{
		  
		  /* NORETURN functions have no effect on aliasing. */
		  if (call_may_return (op1))
		    {		      
		      varray_type args;
		      tree arg;
		      tree callop0, callop1;
		      int argnum;
		      
		      /* Collect the arguments */
		      VARRAY_GENERIC_PTR_INIT (args, 1, "Arguments");
		      bitmap_clear (addrargs);
		      callop1 = TREE_OPERAND (op1, 1);
		      callop0 = TREE_OPERAND (op1, 0);
		      for (arg = callop1, argnum = 0;
			   arg;
			   arg = TREE_CHAIN (arg), argnum++)
			{
			  alias_var aav = get_alias_var (TREE_VALUE (arg));
			  if (aav)
			    {
			      VARRAY_PUSH_GENERIC_PTR (args, aav);
			      if (TREE_CODE (TREE_VALUE (arg)) == ADDR_EXPR)
				bitmap_set_bit (addrargs, argnum);
			    }
			}
		      /* Simulate the call */
		      if (current_alias_ops->function_call (current_alias_ops, lhsAV,
							    get_alias_var (callop0),
							    args, addrargs))
			{ 
			  if (call_may_clobber (op1)
			      && !current_alias_ops->ip
                              && flag_argument_noalias != 2)
			    {
			      intra_function_call (args);
			    }
			  if (POINTER_TYPE_P (TREE_TYPE (op0)))
			    deal_with_call_aliasing (callop1, lhsAV);
			}
		    }
		}
	    }
	  /* x = op (...) */
	  else
	    {
	      bitmap_clear (addrargs);
	      if (TREE_CODE (op1) == CONSTRUCTOR)
	        {
		  varray_type ops;
		  int i = 0;
		  VARRAY_GENERIC_PTR_INIT (ops, 1, "Operands");
		  get_values_from_constructor (op1, &ops, addrargs, &i);
		  current_alias_ops->op_assign (current_alias_ops, lhsAV,
						ops, op1, addrargs);
		}
	      else
		switch (TREE_CODE_CLASS (TREE_CODE (op1)))
		  {
		  case 'e':  /* an expression */
		  case 's':  /* an expression with side effects */
		  case '<':  /* a comparison expression */
		  case '1':  /* a unary arithmetic expression */
		  case 'r':  /* a reference */
		  case '2':  /* a binary arithmetic expression */
		    {
		      tree op;
		      varray_type ops;
		      int i;
		      VARRAY_GENERIC_PTR_INIT (ops, 1, "Operands");
		      for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (op1)); i++)
			{
			  alias_var aav;
			  op = TREE_OPERAND (op1, i);
			  aav = get_alias_var (op);
			  if (aav)
			    VARRAY_PUSH_GENERIC_PTR (ops, aav);
			  if (TREE_CODE (op) == ADDR_EXPR)
			    bitmap_set_bit (addrargs, i);
			}
		      current_alias_ops->op_assign (current_alias_ops, lhsAV,
						    ops, op1, addrargs);
		    }
		    break;
		  default:
		    break;
		  }
	    }
	}
      /* *x = <something> */
      else
	{
	  /* x.f = y  or x->f = y */
	  if ((TREE_CODE (op0) == COMPONENT_REF 
	       || TREE_CODE (op0) == BIT_FIELD_REF)
	      && is_gimple_variable (op1))
	    {
	      if (rhsAV != NULL)
		current_alias_ops->simple_assign (current_alias_ops, lhsAV,
						  rhsAV);
	    }
	  /* x.f = &y or x->f = &y */
	  else if (TREE_CODE (op0) == COMPONENT_REF 
		   && TREE_CODE (op1) == ADDR_EXPR)
	    {
	      if (rhsAV != NULL)
		current_alias_ops->addr_assign (current_alias_ops, lhsAV,
						rhsAV);
	    }
	  /* *x.f = y or *x->f = y */
	  else if ((TREE_CODE (op0) == INDIRECT_REF 
		    || TREE_CODE (op0) == ARRAY_REF)
		   && TREE_CODE (TREE_OPERAND (op0, 0)) == COMPONENT_REF
		   && is_gimple_variable (op1))
	    {
	      if (rhsAV != NULL)
		current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
					       rhsAV);
	    }
	  /* *x = &y */
	  else if ((TREE_CODE (op0) == INDIRECT_REF
		    || TREE_CODE (op0) == ARRAY_REF)
		   && TREE_CODE (op1) == ADDR_EXPR)
	    {
	      /* This becomes temp = &y and *x = temp . */
	      alias_var tempvar;
	      tree temp = create_tmp_var_raw (void_type_node, "aliastmp");
	      tempvar = current_alias_ops->add_var (current_alias_ops, temp);
	      current_alias_ops->addr_assign (current_alias_ops, tempvar,
					      rhsAV);
	      current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
					     tempvar);
	    }

	  /* *x = *y */
	  else if ((TREE_CODE (op0) == INDIRECT_REF 
		    || TREE_CODE (op0) == ARRAY_REF)
		   && (TREE_CODE (op1) == INDIRECT_REF
		       || TREE_CODE (op1) == ARRAY_REF))
	    {
	      /* This becomes temp = *y and *x = temp . */
	      alias_var tempvar;
	      tree temp;
	      temp = create_tmp_var_raw (void_type_node, "aliastmp");
	      tempvar = current_alias_ops->add_var (current_alias_ops, temp);
	      current_alias_ops->ptr_assign (current_alias_ops, tempvar,
					     rhsAV);
	      current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
					     tempvar);
	    }

	  /* *x = (cast) y */
	  else if ((TREE_CODE (op0) == INDIRECT_REF 
		    || TREE_CODE (op0) == ARRAY_REF)
		   && is_gimple_cast (op1))
	    {
	      if (rhsAV != NULL)
		{
		  /* This becomes temp = (cast) y and  *x = temp. */
		  alias_var tempvar;
		  tree temp;
		  temp = create_tmp_var_raw (void_type_node, "aliastmp");
		  tempvar = current_alias_ops->add_var (current_alias_ops,
							temp);
		  current_alias_ops->simple_assign (current_alias_ops,
						    tempvar, rhsAV);
		  current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
						 tempvar);
		}
	    }
	  /* *x = <something else> */
	  else
	    {
	      if (rhsAV != NULL)
		current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
					       rhsAV);
	    }
	}
    }
  /* Calls without return values. */
  else if (TREE_CODE (stp) == CALL_EXPR)
    {
      alias_var callvar;
      varray_type args;
      tree arg;
      callvar = get_alias_var (TREE_OPERAND (stp, 0));
      if (callvar != NULL)
	{
	
	  /* NORETURN and CONST functions with no return value
	     have no effect on aliasing (as may be seen above,
	     const functions that return a value might have an
	     effect on aliasing, since the return value can point
	     to one of the arguments.  */
	  if (call_may_clobber (stp))
	    {
	      int argnum;
	      VARRAY_GENERIC_PTR_INIT (args, 1, "Arguments");
	      bitmap_clear (addrargs);
	      for (arg = TREE_OPERAND (stp, 1), argnum=0; 
		   arg; 
		   arg = TREE_CHAIN (arg), argnum++)
		{
		  alias_var aav = get_alias_var (TREE_VALUE (arg));
		  if (aav)
		    {
		      VARRAY_PUSH_GENERIC_PTR (args, aav);
		      if (TREE_CODE (TREE_VALUE (arg)) == ADDR_EXPR)
			bitmap_set_bit (addrargs, argnum);
		    }
		  
		}
	      
	      if (current_alias_ops->function_call (current_alias_ops, NULL,
						    callvar, args, addrargs))
		if (!current_alias_ops->ip && flag_argument_noalias != 2)
		  intra_function_call (args);
	    }
	}
  }
}

/*  Create the alias_var for a function definition DECL, it's
    arguments, and it's return value. If FORCE is true, we force 
    creation of the alias_var, regardless of whether one exists already.
    
    This includes creation of alias_var's for
    - The function itself.
    - The arguments.
    - The return value.  */

static alias_var
create_fun_alias_var (tree decl, int force)
{
  alias_var avar, retvar;
  tree rdecl;
  varray_type params = NULL;

  if (!force)
    {
      if (DECL_PTA_ALIASVAR (decl))
        return DECL_PTA_ALIASVAR (decl);
    }

  VARRAY_GENERIC_PTR_INIT (params, 1, "Arguments");
  if (DECL_ARGUMENTS (decl) != NULL)
    {
      tree arg;
      for (arg = DECL_ARGUMENTS (decl); arg; arg = TREE_CHAIN (arg))
	{
	  alias_var var = get_alias_var (arg);
	  VARRAY_PUSH_GENERIC_PTR (params, var);
	  /* Incoming pointers can point to pta_global_var, unless
	     either we are interprocedural, or we can do ip on all
	     statics + this function has been defined + it's not an
	     external function. */
	  if (POINTER_TYPE_P (TREE_TYPE (arg))
	      && !current_alias_ops->ip
	      /* FIXME: Need to let analyzer decide in partial case. */
	      && (!current_alias_ops->ip_partial
		  || !cgraph_local_info (decl)->local))
	    current_alias_ops->simple_assign (current_alias_ops, var,
					      get_alias_var (pta_global_var));
	}
    }
  else if (TYPE_ARG_TYPES (TREE_TYPE (decl)) != NULL)
    {
      tree arg;
      /* FIXME: Handle varargs */
      for (arg = TYPE_ARG_TYPES (TREE_TYPE (decl));
	   arg && TREE_VALUE (arg) != void_type_node;
	   arg = TREE_CHAIN (arg))
	{
	  tree fakedecl = create_tmp_var_raw (TREE_VALUE (arg), "normarg");
	  alias_var var;
	  DECL_CONTEXT (fakedecl) = current_function_decl; 
	  var = get_alias_var (fakedecl);
	  VARRAY_PUSH_GENERIC_PTR (params, var);

	  /* Incoming pointers can point to pta_global_var, unless
	     either we are interprocedural, or we can do ip on all
	     statics + this function has been defined + it's not an
	     external function. */
	  if (POINTER_TYPE_P (TREE_TYPE (fakedecl))
	      && !current_alias_ops->ip
	      /* FIXME: need to let analyzer decide in partial case. */
	      && (!current_alias_ops->ip_partial
		  || !TREE_STATIC (decl)
		  || TREE_PUBLIC (decl)))
	    current_alias_ops->simple_assign (current_alias_ops, var,
					      get_alias_var (pta_global_var));
	}
    }
  /* Functions declared like void f() are *not* equivalent to void
     f(void). You can pass an argument to them. Thus, we need to
     create some fake argument that would alias any actuals that get
     passed to our function.  */
  else
    {
      tree fakedecl = create_tmp_var_raw (void_type_node, "fakearg");
      alias_var fakevar;
      DECL_CONTEXT (fakedecl) = current_function_decl;
      fakevar = get_alias_var (fakedecl);
      VARRAY_PUSH_GENERIC_PTR (params, fakevar);
    }

  if (!DECL_RESULT (decl))
    {
      rdecl = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (decl)), "_rv_");
      retvar = current_alias_ops->add_var (current_alias_ops, rdecl);
      DECL_PTA_ALIASVAR (rdecl) = retvar;
    }
  else
    {
      retvar = current_alias_ops->add_var (current_alias_ops,
					   DECL_RESULT (decl));
      DECL_PTA_ALIASVAR (DECL_RESULT (decl)) = retvar;
    }
  VARRAY_PUSH_GENERIC_PTR (alias_vars, retvar);
  ALIAS_VAR_VARNUM (retvar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;
  avar = current_alias_ops->add_var (current_alias_ops, decl);
  VARRAY_PUSH_GENERIC_PTR (alias_vars, avar);
  ALIAS_VAR_VARNUM (avar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;

  current_alias_ops->function_def (current_alias_ops, avar, params, retvar);
  DECL_PTA_ALIASVAR (decl) = avar;

  /* FIXME: Also, if this is a defining declaration then add the annotation
     to all extern definitions of the function. */
  return avar;
}

/*  Create an alias variable for a pointer-to-member function DECL of 
    type TYPE, it's arguments, and it's return value.
    Returns the alias_var for the PTF.
    
    This includes creating alias_var's for
    - The function itself.
    - The arguments.
    - The return value.  */

static alias_var
create_fun_alias_var_ptf (tree decl, tree type)
{
  alias_var avar, retvar;
  tree rdecl;
  varray_type params = NULL;

  if (DECL_PTA_ALIASVAR (decl))
    return DECL_PTA_ALIASVAR (decl);

  VARRAY_GENERIC_PTR_INIT (params, 1, "Arguments");

  if (TYPE_ARG_TYPES  (type) != NULL)
    {
      tree arg;
      /* FIXME: Handle varargs */
      for (arg = TYPE_ARG_TYPES (type);
	   arg && TREE_VALUE (arg) != void_type_node;
	   arg = TREE_CHAIN (arg))
	{
	  tree fakedecl = create_tmp_var_raw (TREE_VALUE (arg), "ptfarg");
	  alias_var var;
	  DECL_CONTEXT (fakedecl) = DECL_CONTEXT (decl);
	  var = get_alias_var (fakedecl);
	  VARRAY_PUSH_GENERIC_PTR (params, var);
	}
    }
  /* Functions declared like void f() are *not* equivalent to void
     f(void). You can pass an argument to them. Thus, we need to
     create some fake argument that would alias any actuals that get
     passed to our function.  */
  else
    {
      tree fakedecl = create_tmp_var_raw (void_type_node, "fakearg");
      alias_var fakevar;
      DECL_CONTEXT (fakedecl) = DECL_CONTEXT (decl);
      fakevar = get_alias_var (fakedecl);
      VARRAY_PUSH_GENERIC_PTR (params, fakevar);
    }

  rdecl = create_tmp_var_raw (TREE_TYPE (type), "_rv_");
  retvar = current_alias_ops->add_var (current_alias_ops, rdecl);
  VARRAY_PUSH_GENERIC_PTR (alias_vars, retvar);
  ALIAS_VAR_VARNUM (retvar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;

  avar = current_alias_ops->add_var (current_alias_ops, decl);
  VARRAY_PUSH_GENERIC_PTR (alias_vars, avar);
  ALIAS_VAR_VARNUM (avar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;

  current_alias_ops->function_def (current_alias_ops, avar, params, retvar);
  DECL_PTA_ALIASVAR (decl) = avar;

  return avar;
}

/*  Create the alias_var for a *_DECL node DECL.
    Returns the alias_var for DECL.
    
    This function also handles creation of alias_var's for PTF 
    variables.  */

static alias_var
create_alias_var (tree decl)
{
  alias_var avar;

  if (!DECL_P (decl))
    abort ();
  
  if (DECL_P (decl))
    {
      if (DECL_PTA_ALIASVAR (decl))
	return DECL_PTA_ALIASVAR (decl);
    }

  if (POINTER_TYPE_P (TREE_TYPE (decl))
      && TREE_CODE (TREE_TYPE (TREE_TYPE (decl))) == FUNCTION_TYPE)
    {
      avar = create_fun_alias_var_ptf (decl, TREE_TYPE (TREE_TYPE (decl)));
    }
  else
    avar = current_alias_ops->add_var (current_alias_ops, decl);

  if (DECL_P (decl))
    {
      DECL_PTA_ALIASVAR (decl) = avar;
    }

  VARRAY_PUSH_GENERIC_PTR (alias_vars, avar);
  ALIAS_VAR_VARNUM (avar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;
  return avar;
}

/* Create points-to sets for the current function.  */

static void
create_alias_vars (void)
{
  basic_block bb;
#ifdef HAVE_BANSHEE
  if (flag_tree_points_to == PTA_ANDERSEN)
    current_alias_ops = andersen_alias_ops;
  else
#endif
   {
     current_alias_ops = NULL;
     flag_tree_points_to = PTA_NONE;
     return;
   }

  pta_global_var = build_decl (VAR_DECL, get_identifier (".pta_global_var"),
			       size_type_node);
  DECL_ARTIFICIAL (pta_global_var) = 1;
  TREE_READONLY (pta_global_var) = 1;
  DECL_EXTERNAL (pta_global_var) = 0;
  TREE_STATIC (pta_global_var) = 1;
  TREE_USED (pta_global_var) = 1;
  DECL_CONTEXT (pta_global_var) = current_function_decl; 
  TREE_THIS_VOLATILE (pta_global_var) = 1;
  TREE_ADDRESSABLE (pta_global_var) = 0;

  init_alias_vars ();

  DECL_PTA_ALIASVAR (current_function_decl) = NULL;
  get_alias_var (current_function_decl);

  /* First, walk the variables and their DECL_INITIAL's */
  if (cfun->unexpanded_var_list)
    {
      tree vars, var;
      for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
	{
	  var = TREE_VALUE (vars);
	  if (TREE_CODE (var) != LABEL_DECL
	      && decl_function_context (var) == NULL
	      && DECL_INITIAL (var))
	    find_func_aliases (var);
	}
    }

  /* Now walk all statements and derive aliases.  */
  FOR_EACH_BB (bb)
    {
      block_stmt_iterator bsi; 
      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
	find_func_aliases (bsi_stmt (bsi));
    }

  pta_global_var = NULL_TREE;
}

struct tree_opt_pass pass_build_pta = 
{
  "pta",				/* name */
  NULL,					/* gate */
  create_alias_vars,			/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_TREE_PTA,				/* tv_id */
  PROP_cfg,				/* properties_required */
  PROP_pta,				/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  0					/* todo_flags_finish */
};
 

/* Delete created points-to sets.  */

static void
delete_alias_vars (void)
{
  size_t i;

  if (flag_tree_points_to != PTA_ANDERSEN)
    return;

  for (i = 0; i < VARRAY_ACTIVE_SIZE (local_alias_vars); i++)
    {
      tree key = VARRAY_TREE (local_alias_vars, i);
      if (DECL_P (key))
	DECL_PTA_ALIASVAR (key) = NULL;
      else
	abort ();
    }

  for (i = 0; i < VARRAY_ACTIVE_SIZE (local_alias_varnums); i ++)
    VARRAY_GENERIC_PTR (alias_vars, VARRAY_INT (local_alias_varnums, i)) = NULL;
  if (!current_alias_ops->ip && !current_alias_ops->ip_partial)
    {
      /*      VARRAY_CLEAR (alias_vars); */
      VARRAY_CLEAR (local_alias_vars);
      VARRAY_CLEAR (local_alias_varnums);
    }
  BITMAP_XFREE (addrargs);
  current_alias_ops->cleanup (current_alias_ops);
}

struct tree_opt_pass pass_del_pta = 
{
  "pta",				/* name */
  NULL,					/* gate */
  delete_alias_vars,			/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_TREE_PTA,				/* tv_id */
  PROP_pta,				/* properties_required */
  0,					/* properties_provided */
  PROP_pta,				/* properties_destroyed */
  0,					/* todo_flags_start */
  0					/* todo_flags_finish */
};
 

/*  Initialize points-to analysis machinery.  */

void
init_alias_vars (void)
{
  current_alias_ops->init (current_alias_ops);
  addrargs = BITMAP_XMALLOC ();
  VARRAY_TREE_INIT (local_alias_vars, 10, "Local alias vars");
  VARRAY_INT_INIT (local_alias_varnums, 10, "Local alias varnums");
  if ((!current_alias_ops->ip && !current_alias_ops->ip_partial)
      || alias_vars == NULL)
    VARRAY_GENERIC_PTR_INIT (alias_vars, 10, "Alias vars");
}

/* Return true if PTR can't point to anything (i.e. it has an empty
   points-to set.  */
bool 
empty_points_to_set (tree ptr)
{
 alias_var ptrtv;
  
#if !FIELD_BASED
#else
  if (TREE_CODE (ptr) == COMPONENT_REF)
    ptr = TREE_OPERAND (ptr, 1);
#endif

  if (DECL_P (ptr))
    {
      ptrtv = DECL_PTA_ALIASVAR (ptr);
      if (!ptrtv)
	return true;
    }
  else
    abort ();

  return current_alias_ops->empty_points_to_set (current_alias_ops, ptrtv);
}

/* Return true if PTR and VAR have the same points-to set.  */

bool
same_points_to_set (tree ptr, tree var)
{
  alias_var ptrtv, vartv;
  
#if !FIELD_BASED
#else
  if (TREE_CODE (ptr) == COMPONENT_REF)
    ptr = TREE_OPERAND (ptr, 1);
  if (TREE_CODE (var) == COMPONENT_REF)
    var = TREE_OPERAND (var, 1);
#endif

  if (ptr == var)
    return true;

  if (DECL_P (ptr))
    {
      ptrtv = DECL_PTA_ALIASVAR (ptr);
      if (!ptrtv)
	return false;
    }
  else
    abort ();

  if (DECL_P (var))
    {
      vartv = DECL_PTA_ALIASVAR (var);
      if (!vartv)
	return false;
    }
  else
    abort ();

  return current_alias_ops->same_points_to_set (current_alias_ops, vartv, ptrtv);
}

/*  Determine whether two variables (PTR and VAR) may-alias.
    Returns TRUE if PTR may-alias VAR.  */

bool
ptr_may_alias_var (tree ptr, tree var)
{
  alias_var ptrtv, vartv;

#if !FIELD_BASED
#else
  if (TREE_CODE (ptr) == COMPONENT_REF)
    ptr = TREE_OPERAND (ptr, 1);
  if (TREE_CODE (var) == COMPONENT_REF)
    var = TREE_OPERAND (var, 1);
#endif

  if (ptr == var)
    return true;

  if (DECL_P (ptr))
    {
      ptrtv = DECL_PTA_ALIASVAR (ptr);
      if (!ptrtv)
	return false;
    }
  else
    abort ();

  if (DECL_P (var))
    {
      vartv = DECL_PTA_ALIASVAR (var);
      if (!vartv)
	return false;
    }
  else
    abort ();

  return current_alias_ops->may_alias (current_alias_ops, ptrtv, vartv);
}

#define MASK_POINTER(P)	((unsigned)((unsigned long)(P) & 0xffff))

const char *
alias_get_name (tree t)
{
  const char *name;

#if FIELD_BASED
  if (TREE_CODE (t) == FIELD_DECL)
    {
      /* First get the name of the field, then the prefix, then smash them
	 together.  */
      const char *fieldname = IDENTIFIER_POINTER (DECL_NAME (t));
      const char *prefix = alias_get_name (DECL_CONTEXT (t));
      char *smashed;
      size_t neededlen = strlen (fieldname) + strlen (prefix) + 2;
      smashed = ggc_alloc (neededlen);
      sprintf (smashed, "%s.%s", prefix, fieldname);
      name = smashed;

    }
  else if (TYPE_P (t))
    {
      if (TYPE_NAME (t) && IDENTIFIER_POINTER (TYPE_NAME (t)))
	name = IDENTIFIER_POINTER (TYPE_NAME (t));
      else
	name = "<unnamed type>";
    }
  else
#endif
    {
      if (TREE_CODE (t) == FUNCTION_DECL)
	name = IDENTIFIER_POINTER (DECL_NAME (t));
      else if (TREE_CODE (t) == RESULT_DECL)
	name = "<return value>";
      else
	name = get_name (t);
    }

  if (!name)
    {
      char *namep;
      /* 2 = UF
	 4 = the masked pointer
	 2 = the <> around it
	 1 = the terminator. */
      namep = ggc_alloc (2 + 4 + 2 + 1);
      sprintf (namep, "<UV%x>", MASK_POINTER (t));
      return namep;
    }

  return name;
}

#include "gt-tree-alias-common.h"