gcc/tree.c

/* Language-independent node constructors for parse phase of GNU compiler.
   Copyright (C) 1987-2013 Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

/* This file contains the low level primitives for operating on tree nodes,
   including allocation, list operations, interning of identifiers,
   construction of data type nodes and statement nodes,
   and construction of type conversion nodes.  It also contains
   tables index by tree code that describe how to take apart
   nodes of that code.

   It is intended to be language-independent, but occasionally
   calls language-dependent routines defined (for C) in typecheck.c.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "flags.h"
#include "tree.h"
#include "tm_p.h"
#include "function.h"
#include "obstack.h"
#include "toplev.h" /* get_random_seed */
#include "ggc.h"
#include "hashtab.h"
#include "filenames.h"
#include "output.h"
#include "target.h"
#include "common/common-target.h"
#include "langhooks.h"
#include "tree-inline.h"
#include "tree-iterator.h"
#include "basic-block.h"
#include "tree-flow.h"
#include "params.h"
#include "pointer-set.h"
#include "tree-pass.h"
#include "langhooks-def.h"
#include "diagnostic.h"
#include "tree-diagnostic.h"
#include "tree-pretty-print.h"
#include "cgraph.h"
#include "except.h"
#include "debug.h"
#include "intl.h"

/* Tree code classes.  */

#define DEFTREECODE(SYM, NAME, TYPE, LENGTH) TYPE,
#define END_OF_BASE_TREE_CODES tcc_exceptional,

const enum tree_code_class tree_code_type[] = {
#include "all-tree.def"
};

#undef DEFTREECODE
#undef END_OF_BASE_TREE_CODES

/* Table indexed by tree code giving number of expression
   operands beyond the fixed part of the node structure.
   Not used for types or decls.  */

#define DEFTREECODE(SYM, NAME, TYPE, LENGTH) LENGTH,
#define END_OF_BASE_TREE_CODES 0,

const unsigned char tree_code_length[] = {
#include "all-tree.def"
};

#undef DEFTREECODE
#undef END_OF_BASE_TREE_CODES

/* Names of tree components.
   Used for printing out the tree and error messages.  */
#define DEFTREECODE(SYM, NAME, TYPE, LEN) NAME,
#define END_OF_BASE_TREE_CODES "@dummy",

const char *const tree_code_name[] = {
#include "all-tree.def"
};

#undef DEFTREECODE
#undef END_OF_BASE_TREE_CODES

/* Each tree code class has an associated string representation.
   These must correspond to the tree_code_class entries.  */

const char *const tree_code_class_strings[] =
{
  "exceptional",
  "constant",
  "type",
  "declaration",
  "reference",
  "comparison",
  "unary",
  "binary",
  "statement",
  "vl_exp",
  "expression"
};

/* obstack.[ch] explicitly declined to prototype this.  */
extern int _obstack_allocated_p (struct obstack *h, void *obj);

/* Statistics-gathering stuff.  */

static int tree_code_counts[MAX_TREE_CODES];
int tree_node_counts[(int) all_kinds];
int tree_node_sizes[(int) all_kinds];

/* Keep in sync with tree.h:enum tree_node_kind.  */
static const char * const tree_node_kind_names[] = {
  "decls",
  "types",
  "blocks",
  "stmts",
  "refs",
  "exprs",
  "constants",
  "identifiers",
  "vecs",
  "binfos",
  "ssa names",
  "constructors",
  "random kinds",
  "lang_decl kinds",
  "lang_type kinds",
  "omp clauses",
};

/* Unique id for next decl created.  */
static GTY(()) int next_decl_uid;
/* Unique id for next type created.  */
static GTY(()) int next_type_uid = 1;
/* Unique id for next debug decl created.  Use negative numbers,
   to catch erroneous uses.  */
static GTY(()) int next_debug_decl_uid;

/* Since we cannot rehash a type after it is in the table, we have to
   keep the hash code.  */

struct GTY(()) type_hash {
  unsigned long hash;
  tree type;
};

/* Initial size of the hash table (rounded to next prime).  */
#define TYPE_HASH_INITIAL_SIZE 1000

/* Now here is the hash table.  When recording a type, it is added to
   the slot whose index is the hash code.  Note that the hash table is
   used for several kinds of types (function types, array types and
   array index range types, for now).  While all these live in the
   same table, they are completely independent, and the hash code is
   computed differently for each of these.  */

static GTY ((if_marked ("type_hash_marked_p"), param_is (struct type_hash)))
     htab_t type_hash_table;

/* Hash table and temporary node for larger integer const values.  */
static GTY (()) tree int_cst_node;
static GTY ((if_marked ("ggc_marked_p"), param_is (union tree_node)))
     htab_t int_cst_hash_table;

/* Hash table for optimization flags and target option flags.  Use the same
   hash table for both sets of options.  Nodes for building the current
   optimization and target option nodes.  The assumption is most of the time
   the options created will already be in the hash table, so we avoid
   allocating and freeing up a node repeatably.  */
static GTY (()) tree cl_optimization_node;
static GTY (()) tree cl_target_option_node;
static GTY ((if_marked ("ggc_marked_p"), param_is (union tree_node)))
     htab_t cl_option_hash_table;

/* General tree->tree mapping  structure for use in hash tables.  */


static GTY ((if_marked ("tree_decl_map_marked_p"), param_is (struct tree_decl_map)))
     htab_t debug_expr_for_decl;

static GTY ((if_marked ("tree_decl_map_marked_p"), param_is (struct tree_decl_map)))
     htab_t value_expr_for_decl;

static GTY ((if_marked ("tree_vec_map_marked_p"), param_is (struct tree_vec_map)))
     htab_t debug_args_for_decl;

static GTY ((if_marked ("tree_priority_map_marked_p"),
	     param_is (struct tree_priority_map)))
  htab_t init_priority_for_decl;

static void set_type_quals (tree, int);
static int type_hash_eq (const void *, const void *);
static hashval_t type_hash_hash (const void *);
static hashval_t int_cst_hash_hash (const void *);
static int int_cst_hash_eq (const void *, const void *);
static hashval_t cl_option_hash_hash (const void *);
static int cl_option_hash_eq (const void *, const void *);
static void print_type_hash_statistics (void);
static void print_debug_expr_statistics (void);
static void print_value_expr_statistics (void);
static int type_hash_marked_p (const void *);
static unsigned int type_hash_list (const_tree, hashval_t);
static unsigned int attribute_hash_list (const_tree, hashval_t);

tree global_trees[TI_MAX];
tree integer_types[itk_none];

unsigned char tree_contains_struct[MAX_TREE_CODES][64];

/* Number of operands for each OpenMP clause.  */
unsigned const char omp_clause_num_ops[] =
{
  0, /* OMP_CLAUSE_ERROR  */
  1, /* OMP_CLAUSE_PRIVATE  */
  1, /* OMP_CLAUSE_SHARED  */
  1, /* OMP_CLAUSE_FIRSTPRIVATE  */
  2, /* OMP_CLAUSE_LASTPRIVATE  */
  4, /* OMP_CLAUSE_REDUCTION  */
  1, /* OMP_CLAUSE_COPYIN  */
  1, /* OMP_CLAUSE_COPYPRIVATE  */
  1, /* OMP_CLAUSE_IF  */
  1, /* OMP_CLAUSE_NUM_THREADS  */
  1, /* OMP_CLAUSE_SCHEDULE  */
  0, /* OMP_CLAUSE_NOWAIT  */
  0, /* OMP_CLAUSE_ORDERED  */
  0, /* OMP_CLAUSE_DEFAULT  */
  3, /* OMP_CLAUSE_COLLAPSE  */
  0, /* OMP_CLAUSE_UNTIED   */
  1, /* OMP_CLAUSE_FINAL  */
  0  /* OMP_CLAUSE_MERGEABLE  */
};

const char * const omp_clause_code_name[] =
{
  "error_clause",
  "private",
  "shared",
  "firstprivate",
  "lastprivate",
  "reduction",
  "copyin",
  "copyprivate",
  "if",
  "num_threads",
  "schedule",
  "nowait",
  "ordered",
  "default",
  "collapse",
  "untied",
  "final",
  "mergeable"
};


/* Return the tree node structure used by tree code CODE.  */

static inline enum tree_node_structure_enum
tree_node_structure_for_code (enum tree_code code)
{
  switch (TREE_CODE_CLASS (code))
    {
    case tcc_declaration:
      {
	switch (code)
	  {
	  case FIELD_DECL:
	    return TS_FIELD_DECL;
	  case PARM_DECL:
	    return TS_PARM_DECL;
	  case VAR_DECL:
	    return TS_VAR_DECL;
	  case LABEL_DECL:
	    return TS_LABEL_DECL;
	  case RESULT_DECL:
	    return TS_RESULT_DECL;
	  case DEBUG_EXPR_DECL:
	    return TS_DECL_WRTL;
	  case CONST_DECL:
	    return TS_CONST_DECL;
	  case TYPE_DECL:
	    return TS_TYPE_DECL;
	  case FUNCTION_DECL:
	    return TS_FUNCTION_DECL;
	  case TRANSLATION_UNIT_DECL:
	    return TS_TRANSLATION_UNIT_DECL;
	  default:
	    return TS_DECL_NON_COMMON;
	  }
      }
    case tcc_type:
      return TS_TYPE_NON_COMMON;
    case tcc_reference:
    case tcc_comparison:
    case tcc_unary:
    case tcc_binary:
    case tcc_expression:
    case tcc_statement:
    case tcc_vl_exp:
      return TS_EXP;
    default:  /* tcc_constant and tcc_exceptional */
      break;
    }
  switch (code)
    {
      /* tcc_constant cases.  */
    case INTEGER_CST:		return TS_INT_CST;
    case REAL_CST:		return TS_REAL_CST;
    case FIXED_CST:		return TS_FIXED_CST;
    case COMPLEX_CST:		return TS_COMPLEX;
    case VECTOR_CST:		return TS_VECTOR;
    case STRING_CST:		return TS_STRING;
      /* tcc_exceptional cases.  */
    case ERROR_MARK:		return TS_COMMON;
    case IDENTIFIER_NODE:	return TS_IDENTIFIER;
    case TREE_LIST:		return TS_LIST;
    case TREE_VEC:		return TS_VEC;
    case SSA_NAME:		return TS_SSA_NAME;
    case PLACEHOLDER_EXPR:	return TS_COMMON;
    case STATEMENT_LIST:	return TS_STATEMENT_LIST;
    case BLOCK:			return TS_BLOCK;
    case CONSTRUCTOR:		return TS_CONSTRUCTOR;
    case TREE_BINFO:		return TS_BINFO;
    case OMP_CLAUSE:		return TS_OMP_CLAUSE;
    case OPTIMIZATION_NODE:	return TS_OPTIMIZATION;
    case TARGET_OPTION_NODE:	return TS_TARGET_OPTION;

    default:
      gcc_unreachable ();
    }
}


/* Initialize tree_contains_struct to describe the hierarchy of tree
   nodes.  */

static void
initialize_tree_contains_struct (void)
{
  unsigned i;

  for (i = ERROR_MARK; i < LAST_AND_UNUSED_TREE_CODE; i++)
    {
      enum tree_code code;
      enum tree_node_structure_enum ts_code;

      code = (enum tree_code) i;
      ts_code = tree_node_structure_for_code (code);

      /* Mark the TS structure itself.  */
      tree_contains_struct[code][ts_code] = 1;

      /* Mark all the structures that TS is derived from.  */
      switch (ts_code)
	{
	case TS_TYPED:
	case TS_BLOCK:
	  MARK_TS_BASE (code);
	  break;

	case TS_COMMON:
	case TS_INT_CST:
	case TS_REAL_CST:
	case TS_FIXED_CST:
	case TS_VECTOR:
	case TS_STRING:
	case TS_COMPLEX:
	case TS_SSA_NAME:
	case TS_CONSTRUCTOR:
	case TS_EXP:
	case TS_STATEMENT_LIST:
	  MARK_TS_TYPED (code);
	  break;

	case TS_IDENTIFIER:
	case TS_DECL_MINIMAL:
	case TS_TYPE_COMMON:
	case TS_LIST:
	case TS_VEC:
	case TS_BINFO:
	case TS_OMP_CLAUSE:
	case TS_OPTIMIZATION:
	case TS_TARGET_OPTION:
	  MARK_TS_COMMON (code);
	  break;

	case TS_TYPE_WITH_LANG_SPECIFIC:
	  MARK_TS_TYPE_COMMON (code);
	  break;

	case TS_TYPE_NON_COMMON:
	  MARK_TS_TYPE_WITH_LANG_SPECIFIC (code);
	  break;

	case TS_DECL_COMMON:
	  MARK_TS_DECL_MINIMAL (code);
	  break;

	case TS_DECL_WRTL:
	case TS_CONST_DECL:
	  MARK_TS_DECL_COMMON (code);
	  break;

	case TS_DECL_NON_COMMON:
	  MARK_TS_DECL_WITH_VIS (code);
	  break;

	case TS_DECL_WITH_VIS:
	case TS_PARM_DECL:
	case TS_LABEL_DECL:
	case TS_RESULT_DECL:
	  MARK_TS_DECL_WRTL (code);
	  break;

	case TS_FIELD_DECL:
	  MARK_TS_DECL_COMMON (code);
	  break;

	case TS_VAR_DECL:
	  MARK_TS_DECL_WITH_VIS (code);
	  break;

	case TS_TYPE_DECL:
	case TS_FUNCTION_DECL:
	  MARK_TS_DECL_NON_COMMON (code);
	  break;

	case TS_TRANSLATION_UNIT_DECL:
	  MARK_TS_DECL_COMMON (code);
	  break;

	default:
	  gcc_unreachable ();
	}
    }

  /* Basic consistency checks for attributes used in fold.  */
  gcc_assert (tree_contains_struct[FUNCTION_DECL][TS_DECL_NON_COMMON]);
  gcc_assert (tree_contains_struct[TYPE_DECL][TS_DECL_NON_COMMON]);
  gcc_assert (tree_contains_struct[CONST_DECL][TS_DECL_COMMON]);
  gcc_assert (tree_contains_struct[VAR_DECL][TS_DECL_COMMON]);
  gcc_assert (tree_contains_struct[PARM_DECL][TS_DECL_COMMON]);
  gcc_assert (tree_contains_struct[RESULT_DECL][TS_DECL_COMMON]);
  gcc_assert (tree_contains_struct[FUNCTION_DECL][TS_DECL_COMMON]);
  gcc_assert (tree_contains_struct[TYPE_DECL][TS_DECL_COMMON]);
  gcc_assert (tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_COMMON]);
  gcc_assert (tree_contains_struct[LABEL_DECL][TS_DECL_COMMON]);
  gcc_assert (tree_contains_struct[FIELD_DECL][TS_DECL_COMMON]);
  gcc_assert (tree_contains_struct[VAR_DECL][TS_DECL_WRTL]);
  gcc_assert (tree_contains_struct[PARM_DECL][TS_DECL_WRTL]);
  gcc_assert (tree_contains_struct[RESULT_DECL][TS_DECL_WRTL]);
  gcc_assert (tree_contains_struct[FUNCTION_DECL][TS_DECL_WRTL]);
  gcc_assert (tree_contains_struct[LABEL_DECL][TS_DECL_WRTL]);
  gcc_assert (tree_contains_struct[CONST_DECL][TS_DECL_MINIMAL]);
  gcc_assert (tree_contains_struct[VAR_DECL][TS_DECL_MINIMAL]);
  gcc_assert (tree_contains_struct[PARM_DECL][TS_DECL_MINIMAL]);
  gcc_assert (tree_contains_struct[RESULT_DECL][TS_DECL_MINIMAL]);
  gcc_assert (tree_contains_struct[FUNCTION_DECL][TS_DECL_MINIMAL]);
  gcc_assert (tree_contains_struct[TYPE_DECL][TS_DECL_MINIMAL]);
  gcc_assert (tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_MINIMAL]);
  gcc_assert (tree_contains_struct[LABEL_DECL][TS_DECL_MINIMAL]);
  gcc_assert (tree_contains_struct[FIELD_DECL][TS_DECL_MINIMAL]);
  gcc_assert (tree_contains_struct[VAR_DECL][TS_DECL_WITH_VIS]);
  gcc_assert (tree_contains_struct[FUNCTION_DECL][TS_DECL_WITH_VIS]);
  gcc_assert (tree_contains_struct[TYPE_DECL][TS_DECL_WITH_VIS]);
  gcc_assert (tree_contains_struct[VAR_DECL][TS_VAR_DECL]);
  gcc_assert (tree_contains_struct[FIELD_DECL][TS_FIELD_DECL]);
  gcc_assert (tree_contains_struct[PARM_DECL][TS_PARM_DECL]);
  gcc_assert (tree_contains_struct[LABEL_DECL][TS_LABEL_DECL]);
  gcc_assert (tree_contains_struct[RESULT_DECL][TS_RESULT_DECL]);
  gcc_assert (tree_contains_struct[CONST_DECL][TS_CONST_DECL]);
  gcc_assert (tree_contains_struct[TYPE_DECL][TS_TYPE_DECL]);
  gcc_assert (tree_contains_struct[FUNCTION_DECL][TS_FUNCTION_DECL]);
  gcc_assert (tree_contains_struct[IMPORTED_DECL][TS_DECL_MINIMAL]);
  gcc_assert (tree_contains_struct[IMPORTED_DECL][TS_DECL_COMMON]);
}


/* Init tree.c.  */

void
init_ttree (void)
{
  /* Initialize the hash table of types.  */
  type_hash_table = htab_create_ggc (TYPE_HASH_INITIAL_SIZE, type_hash_hash,
				     type_hash_eq, 0);

  debug_expr_for_decl = htab_create_ggc (512, tree_decl_map_hash,
					 tree_decl_map_eq, 0);

  value_expr_for_decl = htab_create_ggc (512, tree_decl_map_hash,
					 tree_decl_map_eq, 0);
  init_priority_for_decl = htab_create_ggc (512, tree_priority_map_hash,
					    tree_priority_map_eq, 0);

  int_cst_hash_table = htab_create_ggc (1024, int_cst_hash_hash,
					int_cst_hash_eq, NULL);

  int_cst_node = make_node (INTEGER_CST);

  cl_option_hash_table = htab_create_ggc (64, cl_option_hash_hash,
					  cl_option_hash_eq, NULL);

  cl_optimization_node = make_node (OPTIMIZATION_NODE);
  cl_target_option_node = make_node (TARGET_OPTION_NODE);

  /* Initialize the tree_contains_struct array.  */
  initialize_tree_contains_struct ();
  lang_hooks.init_ts ();
}


/* The name of the object as the assembler will see it (but before any
   translations made by ASM_OUTPUT_LABELREF).  Often this is the same
   as DECL_NAME.  It is an IDENTIFIER_NODE.  */
tree
decl_assembler_name (tree decl)
{
  if (!DECL_ASSEMBLER_NAME_SET_P (decl))
    lang_hooks.set_decl_assembler_name (decl);
  return DECL_WITH_VIS_CHECK (decl)->decl_with_vis.assembler_name;
}

/* Compare ASMNAME with the DECL_ASSEMBLER_NAME of DECL.  */

bool
decl_assembler_name_equal (tree decl, const_tree asmname)
{
  tree decl_asmname = DECL_ASSEMBLER_NAME (decl);
  const char *decl_str;
  const char *asmname_str;
  bool test = false;

  if (decl_asmname == asmname)
    return true;

  decl_str = IDENTIFIER_POINTER (decl_asmname);
  asmname_str = IDENTIFIER_POINTER (asmname);


  /* If the target assembler name was set by the user, things are trickier.
     We have a leading '*' to begin with.  After that, it's arguable what
     is the correct thing to do with -fleading-underscore.  Arguably, we've
     historically been doing the wrong thing in assemble_alias by always
     printing the leading underscore.  Since we're not changing that, make
     sure user_label_prefix follows the '*' before matching.  */
  if (decl_str[0] == '*')
    {
      size_t ulp_len = strlen (user_label_prefix);

      decl_str ++;

      if (ulp_len == 0)
	test = true;
      else if (strncmp (decl_str, user_label_prefix, ulp_len) == 0)
	decl_str += ulp_len, test=true;
      else
	decl_str --;
    }
  if (asmname_str[0] == '*')
    {
      size_t ulp_len = strlen (user_label_prefix);

      asmname_str ++;

      if (ulp_len == 0)
	test = true;
      else if (strncmp (asmname_str, user_label_prefix, ulp_len) == 0)
	asmname_str += ulp_len, test=true;
      else
	asmname_str --;
    }

  if (!test)
    return false;
  return strcmp (decl_str, asmname_str) == 0;
}

/* Hash asmnames ignoring the user specified marks.  */

hashval_t
decl_assembler_name_hash (const_tree asmname)
{
  if (IDENTIFIER_POINTER (asmname)[0] == '*')
    {
      const char *decl_str = IDENTIFIER_POINTER (asmname) + 1;
      size_t ulp_len = strlen (user_label_prefix);

      if (ulp_len == 0)
	;
      else if (strncmp (decl_str, user_label_prefix, ulp_len) == 0)
	decl_str += ulp_len;

      return htab_hash_string (decl_str);
    }

  return htab_hash_string (IDENTIFIER_POINTER (asmname));
}

/* Compute the number of bytes occupied by a tree with code CODE.
   This function cannot be used for nodes that have variable sizes,
   including TREE_VEC, STRING_CST, and CALL_EXPR.  */
size_t
tree_code_size (enum tree_code code)
{
  switch (TREE_CODE_CLASS (code))
    {
    case tcc_declaration:  /* A decl node */
      {
	switch (code)
	  {
	  case FIELD_DECL:
	    return sizeof (struct tree_field_decl);
	  case PARM_DECL:
	    return sizeof (struct tree_parm_decl);
	  case VAR_DECL:
	    return sizeof (struct tree_var_decl);
	  case LABEL_DECL:
	    return sizeof (struct tree_label_decl);
	  case RESULT_DECL:
	    return sizeof (struct tree_result_decl);
	  case CONST_DECL:
	    return sizeof (struct tree_const_decl);
	  case TYPE_DECL:
	    return sizeof (struct tree_type_decl);
	  case FUNCTION_DECL:
	    return sizeof (struct tree_function_decl);
	  case DEBUG_EXPR_DECL:
	    return sizeof (struct tree_decl_with_rtl);
	  default:
	    return sizeof (struct tree_decl_non_common);
	  }
      }

    case tcc_type:  /* a type node */
      return sizeof (struct tree_type_non_common);

    case tcc_reference:   /* a reference */
    case tcc_expression:  /* an expression */
    case tcc_statement:   /* an expression with side effects */
    case tcc_comparison:  /* a comparison expression */
    case tcc_unary:       /* a unary arithmetic expression */
    case tcc_binary:      /* a binary arithmetic expression */
      return (sizeof (struct tree_exp)
	      + (TREE_CODE_LENGTH (code) - 1) * sizeof (tree));

    case tcc_constant:  /* a constant */
      switch (code)
	{
	case INTEGER_CST:	return sizeof (struct tree_int_cst);
	case REAL_CST:		return sizeof (struct tree_real_cst);
	case FIXED_CST:		return sizeof (struct tree_fixed_cst);
	case COMPLEX_CST:	return sizeof (struct tree_complex);
	case VECTOR_CST:	return sizeof (struct tree_vector);
	case STRING_CST:	gcc_unreachable ();
	default:
	  return lang_hooks.tree_size (code);
	}

    case tcc_exceptional:  /* something random, like an identifier.  */
      switch (code)
	{
	case IDENTIFIER_NODE:	return lang_hooks.identifier_size;
	case TREE_LIST:		return sizeof (struct tree_list);

	case ERROR_MARK:
	case PLACEHOLDER_EXPR:	return sizeof (struct tree_common);

	case TREE_VEC:
	case OMP_CLAUSE:	gcc_unreachable ();

	case SSA_NAME:		return sizeof (struct tree_ssa_name);

	case STATEMENT_LIST:	return sizeof (struct tree_statement_list);
	case BLOCK:		return sizeof (struct tree_block);
	case CONSTRUCTOR:	return sizeof (struct tree_constructor);
	case OPTIMIZATION_NODE: return sizeof (struct tree_optimization_option);
	case TARGET_OPTION_NODE: return sizeof (struct tree_target_option);

	default:
	  return lang_hooks.tree_size (code);
	}

    default:
      gcc_unreachable ();
    }
}

/* Compute the number of bytes occupied by NODE.  This routine only
   looks at TREE_CODE, except for those nodes that have variable sizes.  */
size_t
tree_size (const_tree node)
{
  const enum tree_code code = TREE_CODE (node);
  switch (code)
    {
    case TREE_BINFO:
      return (offsetof (struct tree_binfo, base_binfos)
	      + vec<tree, va_gc>
		  ::embedded_size (BINFO_N_BASE_BINFOS (node)));

    case TREE_VEC:
      return (sizeof (struct tree_vec)
	      + (TREE_VEC_LENGTH (node) - 1) * sizeof (tree));

    case VECTOR_CST:
      return (sizeof (struct tree_vector)
	      + (TYPE_VECTOR_SUBPARTS (TREE_TYPE (node)) - 1) * sizeof (tree));

    case STRING_CST:
      return TREE_STRING_LENGTH (node) + offsetof (struct tree_string, str) + 1;

    case OMP_CLAUSE:
      return (sizeof (struct tree_omp_clause)
	      + (omp_clause_num_ops[OMP_CLAUSE_CODE (node)] - 1)
	        * sizeof (tree));

    default:
      if (TREE_CODE_CLASS (code) == tcc_vl_exp)
	return (sizeof (struct tree_exp)
		+ (VL_EXP_OPERAND_LENGTH (node) - 1) * sizeof (tree));
      else
	return tree_code_size (code);
    }
}

/* Record interesting allocation statistics for a tree node with CODE
   and LENGTH.  */

static void
record_node_allocation_statistics (enum tree_code code ATTRIBUTE_UNUSED,
				   size_t length ATTRIBUTE_UNUSED)
{
  enum tree_code_class type = TREE_CODE_CLASS (code);
  tree_node_kind kind;

  if (!GATHER_STATISTICS)
    return;

  switch (type)
    {
    case tcc_declaration:  /* A decl node */
      kind = d_kind;
      break;

    case tcc_type:  /* a type node */
      kind = t_kind;
      break;

    case tcc_statement:  /* an expression with side effects */
      kind = s_kind;
      break;

    case tcc_reference:  /* a reference */
      kind = r_kind;
      break;

    case tcc_expression:  /* an expression */
    case tcc_comparison:  /* a comparison expression */
    case tcc_unary:  /* a unary arithmetic expression */
    case tcc_binary:  /* a binary arithmetic expression */
      kind = e_kind;
      break;

    case tcc_constant:  /* a constant */
      kind = c_kind;
      break;

    case tcc_exceptional:  /* something random, like an identifier.  */
      switch (code)
	{
	case IDENTIFIER_NODE:
	  kind = id_kind;
	  break;

	case TREE_VEC:
	  kind = vec_kind;
	  break;

	case TREE_BINFO:
	  kind = binfo_kind;
	  break;

	case SSA_NAME:
	  kind = ssa_name_kind;
	  break;

	case BLOCK:
	  kind = b_kind;
	  break;

	case CONSTRUCTOR:
	  kind = constr_kind;
	  break;

	case OMP_CLAUSE:
	  kind = omp_clause_kind;
	  break;

	default:
	  kind = x_kind;
	  break;
	}
      break;

    case tcc_vl_exp:
      kind = e_kind;
      break;

    default:
      gcc_unreachable ();
    }

  tree_code_counts[(int) code]++;
  tree_node_counts[(int) kind]++;
  tree_node_sizes[(int) kind] += length;
}

/* Allocate and return a new UID from the DECL_UID namespace.  */

int
allocate_decl_uid (void)
{
  return next_decl_uid++;
}

/* Return a newly allocated node of code CODE.  For decl and type
   nodes, some other fields are initialized.  The rest of the node is
   initialized to zero.  This function cannot be used for TREE_VEC or
   OMP_CLAUSE nodes, which is enforced by asserts in tree_code_size.

   Achoo!  I got a code in the node.  */

tree
make_node_stat (enum tree_code code MEM_STAT_DECL)
{
  tree t;
  enum tree_code_class type = TREE_CODE_CLASS (code);
  size_t length = tree_code_size (code);

  record_node_allocation_statistics (code, length);

  t = ggc_alloc_cleared_tree_node_stat (length PASS_MEM_STAT);
  TREE_SET_CODE (t, code);

  switch (type)
    {
    case tcc_statement:
      TREE_SIDE_EFFECTS (t) = 1;
      break;

    case tcc_declaration:
      if (CODE_CONTAINS_STRUCT (code, TS_DECL_COMMON))
	{
	  if (code == FUNCTION_DECL)
	    {
	      DECL_ALIGN (t) = FUNCTION_BOUNDARY;
	      DECL_MODE (t) = FUNCTION_MODE;
	    }
	  else
	    DECL_ALIGN (t) = 1;
	}
      DECL_SOURCE_LOCATION (t) = input_location;
      if (TREE_CODE (t) == DEBUG_EXPR_DECL)
	DECL_UID (t) = --next_debug_decl_uid;
      else
	{
	  DECL_UID (t) = allocate_decl_uid ();
	  SET_DECL_PT_UID (t, -1);
	}
      if (TREE_CODE (t) == LABEL_DECL)
	LABEL_DECL_UID (t) = -1;

      break;

    case tcc_type:
      TYPE_UID (t) = next_type_uid++;
      TYPE_ALIGN (t) = BITS_PER_UNIT;
      TYPE_USER_ALIGN (t) = 0;
      TYPE_MAIN_VARIANT (t) = t;
      TYPE_CANONICAL (t) = t;

      /* Default to no attributes for type, but let target change that.  */
      TYPE_ATTRIBUTES (t) = NULL_TREE;
      targetm.set_default_type_attributes (t);

      /* We have not yet computed the alias set for this type.  */
      TYPE_ALIAS_SET (t) = -1;
      break;

    case tcc_constant:
      TREE_CONSTANT (t) = 1;
      break;

    case tcc_expression:
      switch (code)
	{
	case INIT_EXPR:
	case MODIFY_EXPR:
	case VA_ARG_EXPR:
	case PREDECREMENT_EXPR:
	case PREINCREMENT_EXPR:
	case POSTDECREMENT_EXPR:
	case POSTINCREMENT_EXPR:
	  /* All of these have side-effects, no matter what their
	     operands are.  */
	  TREE_SIDE_EFFECTS (t) = 1;
	  break;

	default:
	  break;
	}
      break;

    default:
      /* Other classes need no special treatment.  */
      break;
    }

  return t;
}

/* Return a new node with the same contents as NODE except that its
   TREE_CHAIN, if it has one, is zero and it has a fresh uid.  */

tree
copy_node_stat (tree node MEM_STAT_DECL)
{
  tree t;
  enum tree_code code = TREE_CODE (node);
  size_t length;

  gcc_assert (code != STATEMENT_LIST);

  length = tree_size (node);
  record_node_allocation_statistics (code, length);
  t = ggc_alloc_tree_node_stat (length PASS_MEM_STAT);
  memcpy (t, node, length);

  if (CODE_CONTAINS_STRUCT (code, TS_COMMON))
    TREE_CHAIN (t) = 0;
  TREE_ASM_WRITTEN (t) = 0;
  TREE_VISITED (t) = 0;

  if (TREE_CODE_CLASS (code) == tcc_declaration)
    {
      if (code == DEBUG_EXPR_DECL)
	DECL_UID (t) = --next_debug_decl_uid;
      else
	{
	  DECL_UID (t) = allocate_decl_uid ();
	  if (DECL_PT_UID_SET_P (node))
	    SET_DECL_PT_UID (t, DECL_PT_UID (node));
	}
      if ((TREE_CODE (node) == PARM_DECL || TREE_CODE (node) == VAR_DECL)
	  && DECL_HAS_VALUE_EXPR_P (node))
	{
	  SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (node));
	  DECL_HAS_VALUE_EXPR_P (t) = 1;
	}
      if (TREE_CODE (node) == VAR_DECL && DECL_HAS_INIT_PRIORITY_P (node))
	{
	  SET_DECL_INIT_PRIORITY (t, DECL_INIT_PRIORITY (node));
	  DECL_HAS_INIT_PRIORITY_P (t) = 1;
	}
      if (TREE_CODE (node) == FUNCTION_DECL)
	DECL_STRUCT_FUNCTION (t) = NULL;
    }
  else if (TREE_CODE_CLASS (code) == tcc_type)
    {
      TYPE_UID (t) = next_type_uid++;
      /* The following is so that the debug code for
	 the copy is different from the original type.
	 The two statements usually duplicate each other
	 (because they clear fields of the same union),
	 but the optimizer should catch that.  */
      TYPE_SYMTAB_POINTER (t) = 0;
      TYPE_SYMTAB_ADDRESS (t) = 0;

      /* Do not copy the values cache.  */
      if (TYPE_CACHED_VALUES_P(t))
	{
	  TYPE_CACHED_VALUES_P (t) = 0;
	  TYPE_CACHED_VALUES (t) = NULL_TREE;
	}
    }

  return t;
}

/* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
   For example, this can copy a list made of TREE_LIST nodes.  */

tree
copy_list (tree list)
{
  tree head;
  tree prev, next;

  if (list == 0)
    return 0;

  head = prev = copy_node (list);
  next = TREE_CHAIN (list);
  while (next)
    {
      TREE_CHAIN (prev) = copy_node (next);
      prev = TREE_CHAIN (prev);
      next = TREE_CHAIN (next);
    }
  return head;
}


/* Create an INT_CST node with a LOW value sign extended to TYPE.  */

tree
build_int_cst (tree type, HOST_WIDE_INT low)
{
  /* Support legacy code.  */
  if (!type)
    type = integer_type_node;

  return double_int_to_tree (type, double_int::from_shwi (low));
}

/* Create an INT_CST node with a LOW value sign extended to TYPE.  */

tree
build_int_cst_type (tree type, HOST_WIDE_INT low)
{
  gcc_assert (type);

  return double_int_to_tree (type, double_int::from_shwi (low));
}

/* Constructs tree in type TYPE from with value given by CST.  Signedness
   of CST is assumed to be the same as the signedness of TYPE.  */

tree
double_int_to_tree (tree type, double_int cst)
{
  bool sign_extended_type = !TYPE_UNSIGNED (type);

  cst = cst.ext (TYPE_PRECISION (type), !sign_extended_type);

  return build_int_cst_wide (type, cst.low, cst.high);
}

/* Returns true if CST fits into range of TYPE.  Signedness of CST is assumed
   to be the same as the signedness of TYPE.  */

bool
double_int_fits_to_tree_p (const_tree type, double_int cst)
{
  bool sign_extended_type = !TYPE_UNSIGNED (type);

  double_int ext
    = cst.ext (TYPE_PRECISION (type), !sign_extended_type);

  return cst == ext;
}

/* We force the double_int CST to the range of the type TYPE by sign or
   zero extending it.  OVERFLOWABLE indicates if we are interested in
   overflow of the value, when >0 we are only interested in signed
   overflow, for <0 we are interested in any overflow.  OVERFLOWED
   indicates whether overflow has already occurred.  CONST_OVERFLOWED
   indicates whether constant overflow has already occurred.  We force
   T's value to be within range of T's type (by setting to 0 or 1 all
   the bits outside the type's range).  We set TREE_OVERFLOWED if,
        OVERFLOWED is nonzero,
        or OVERFLOWABLE is >0 and signed overflow occurs
        or OVERFLOWABLE is <0 and any overflow occurs
   We return a new tree node for the extended double_int.  The node
   is shared if no overflow flags are set.  */


tree
force_fit_type_double (tree type, double_int cst, int overflowable,
		       bool overflowed)
{
  bool sign_extended_type = !TYPE_UNSIGNED (type);

  /* If we need to set overflow flags, return a new unshared node.  */
  if (overflowed || !double_int_fits_to_tree_p(type, cst))
    {
      if (overflowed
	  || overflowable < 0
	  || (overflowable > 0 && sign_extended_type))
	{
	  tree t = make_node (INTEGER_CST);
	  TREE_INT_CST (t)
	    = cst.ext (TYPE_PRECISION (type), !sign_extended_type);
	  TREE_TYPE (t) = type;
	  TREE_OVERFLOW (t) = 1;
	  return t;
	}
    }

  /* Else build a shared node.  */
  return double_int_to_tree (type, cst);
}

/* These are the hash table functions for the hash table of INTEGER_CST
   nodes of a sizetype.  */

/* Return the hash code code X, an INTEGER_CST.  */

static hashval_t
int_cst_hash_hash (const void *x)
{
  const_tree const t = (const_tree) x;

  return (TREE_INT_CST_HIGH (t) ^ TREE_INT_CST_LOW (t)
	  ^ TYPE_UID (TREE_TYPE (t)));
}

/* Return nonzero if the value represented by *X (an INTEGER_CST tree node)
   is the same as that given by *Y, which is the same.  */

static int
int_cst_hash_eq (const void *x, const void *y)
{
  const_tree const xt = (const_tree) x;
  const_tree const yt = (const_tree) y;

  return (TREE_TYPE (xt) == TREE_TYPE (yt)
	  && TREE_INT_CST_HIGH (xt) == TREE_INT_CST_HIGH (yt)
	  && TREE_INT_CST_LOW (xt) == TREE_INT_CST_LOW (yt));
}

/* Create an INT_CST node of TYPE and value HI:LOW.
   The returned node is always shared.  For small integers we use a
   per-type vector cache, for larger ones we use a single hash table.  */

tree
build_int_cst_wide (tree type, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
{
  tree t;
  int ix = -1;
  int limit = 0;

  gcc_assert (type);

  switch (TREE_CODE (type))
    {
    case NULLPTR_TYPE:
      gcc_assert (hi == 0 && low == 0);
      /* Fallthru.  */

    case POINTER_TYPE:
    case REFERENCE_TYPE:
      /* Cache NULL pointer.  */
      if (!hi && !low)
	{
	  limit = 1;
	  ix = 0;
	}
      break;

    case BOOLEAN_TYPE:
      /* Cache false or true.  */
      limit = 2;
      if (!hi && low < 2)
	ix = low;
      break;

    case INTEGER_TYPE:
    case OFFSET_TYPE:
      if (TYPE_UNSIGNED (type))
	{
	  /* Cache 0..N */
	  limit = INTEGER_SHARE_LIMIT;
	  if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
	    ix = low;
	}
      else
	{
	  /* Cache -1..N */
	  limit = INTEGER_SHARE_LIMIT + 1;
	  if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
	    ix = low + 1;
	  else if (hi == -1 && low == -(unsigned HOST_WIDE_INT)1)
	    ix = 0;
	}
      break;

    case ENUMERAL_TYPE:
      break;

    default:
      gcc_unreachable ();
    }

  if (ix >= 0)
    {
      /* Look for it in the type's vector of small shared ints.  */
      if (!TYPE_CACHED_VALUES_P (type))
	{
	  TYPE_CACHED_VALUES_P (type) = 1;
	  TYPE_CACHED_VALUES (type) = make_tree_vec (limit);
	}

      t = TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix);
      if (t)
	{
	  /* Make sure no one is clobbering the shared constant.  */
	  gcc_assert (TREE_TYPE (t) == type);
	  gcc_assert (TREE_INT_CST_LOW (t) == low);
	  gcc_assert (TREE_INT_CST_HIGH (t) == hi);
	}
      else
	{
	  /* Create a new shared int.  */
	  t = make_node (INTEGER_CST);

	  TREE_INT_CST_LOW (t) = low;
	  TREE_INT_CST_HIGH (t) = hi;
	  TREE_TYPE (t) = type;

	  TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix) = t;
	}
    }
  else
    {
      /* Use the cache of larger shared ints.  */
      void **slot;

      TREE_INT_CST_LOW (int_cst_node) = low;
      TREE_INT_CST_HIGH (int_cst_node) = hi;
      TREE_TYPE (int_cst_node) = type;

      slot = htab_find_slot (int_cst_hash_table, int_cst_node, INSERT);
      t = (tree) *slot;
      if (!t)
	{
	  /* Insert this one into the hash table.  */
	  t = int_cst_node;
	  *slot = t;
	  /* Make a new node for next time round.  */
	  int_cst_node = make_node (INTEGER_CST);
	}
    }

  return t;
}

/* Builds an integer constant in TYPE such that lowest BITS bits are ones
   and the rest are zeros.  */

tree
build_low_bits_mask (tree type, unsigned bits)
{
  double_int mask;

  gcc_assert (bits <= TYPE_PRECISION (type));

  if (bits == TYPE_PRECISION (type)
      && !TYPE_UNSIGNED (type))
    /* Sign extended all-ones mask.  */
    mask = double_int_minus_one;
  else
    mask = double_int::mask (bits);

  return build_int_cst_wide (type, mask.low, mask.high);
}

/* Checks that X is integer constant that can be expressed in (unsigned)
   HOST_WIDE_INT without loss of precision.  */

bool
cst_and_fits_in_hwi (const_tree x)
{
  if (TREE_CODE (x) != INTEGER_CST)
    return false;

  if (TYPE_PRECISION (TREE_TYPE (x)) > HOST_BITS_PER_WIDE_INT)
    return false;

  return (TREE_INT_CST_HIGH (x) == 0
	  || TREE_INT_CST_HIGH (x) == -1);
}

/* Build a newly constructed TREE_VEC node of length LEN.  */

tree
make_vector_stat (unsigned len MEM_STAT_DECL)
{
  tree t;
  unsigned length = (len - 1) * sizeof (tree) + sizeof (struct tree_vector);

  record_node_allocation_statistics (VECTOR_CST, length);

  t = ggc_alloc_cleared_tree_node_stat (length PASS_MEM_STAT);

  TREE_SET_CODE (t, VECTOR_CST);
  TREE_CONSTANT (t) = 1;

  return t;
}

/* Return a new VECTOR_CST node whose type is TYPE and whose values
   are in a list pointed to by VALS.  */

tree
build_vector_stat (tree type, tree *vals MEM_STAT_DECL)
{
  int over = 0;
  unsigned cnt = 0;
  tree v = make_vector (TYPE_VECTOR_SUBPARTS (type));
  TREE_TYPE (v) = type;

  /* Iterate through elements and check for overflow.  */
  for (cnt = 0; cnt < TYPE_VECTOR_SUBPARTS (type); ++cnt)
    {
      tree value = vals[cnt];

      VECTOR_CST_ELT (v, cnt) = value;

      /* Don't crash if we get an address constant.  */
      if (!CONSTANT_CLASS_P (value))
	continue;

      over |= TREE_OVERFLOW (value);
    }

  TREE_OVERFLOW (v) = over;
  return v;
}

/* Return a new VECTOR_CST node whose type is TYPE and whose values
   are extracted from V, a vector of CONSTRUCTOR_ELT.  */

tree
build_vector_from_ctor (tree type, vec<constructor_elt, va_gc> *v)
{
  tree *vec = XALLOCAVEC (tree, TYPE_VECTOR_SUBPARTS (type));
  unsigned HOST_WIDE_INT idx;
  tree value;

  FOR_EACH_CONSTRUCTOR_VALUE (v, idx, value)
    vec[idx] = value;
  for (; idx < TYPE_VECTOR_SUBPARTS (type); ++idx)
    vec[idx] = build_zero_cst (TREE_TYPE (type));

  return build_vector (type, vec);
}

/* Build a vector of type VECTYPE where all the elements are SCs.  */
tree
build_vector_from_val (tree vectype, tree sc) 
{
  int i, nunits = TYPE_VECTOR_SUBPARTS (vectype);

  if (sc == error_mark_node)
    return sc;

  /* Verify that the vector type is suitable for SC.  Note that there
     is some inconsistency in the type-system with respect to restrict
     qualifications of pointers.  Vector types always have a main-variant
     element type and the qualification is applied to the vector-type.
     So TREE_TYPE (vector-type) does not return a properly qualified
     vector element-type.  */
  gcc_checking_assert (types_compatible_p (TYPE_MAIN_VARIANT (TREE_TYPE (sc)),
					   TREE_TYPE (vectype)));

  if (CONSTANT_CLASS_P (sc))
    {
      tree *v = XALLOCAVEC (tree, nunits);
      for (i = 0; i < nunits; ++i)
	v[i] = sc;
      return build_vector (vectype, v);
    }
  else
    {
      vec<constructor_elt, va_gc> *v;
      vec_alloc (v, nunits);
      for (i = 0; i < nunits; ++i)
	CONSTRUCTOR_APPEND_ELT (v, NULL_TREE, sc);
      return build_constructor (vectype, v);
    }
}

/* Return a new CONSTRUCTOR node whose type is TYPE and whose values
   are in the vec pointed to by VALS.  */
tree
build_constructor (tree type, vec<constructor_elt, va_gc> *vals)
{
  tree c = make_node (CONSTRUCTOR);
  unsigned int i;
  constructor_elt *elt;
  bool constant_p = true;
  bool side_effects_p = false;

  TREE_TYPE (c) = type;
  CONSTRUCTOR_ELTS (c) = vals;

  FOR_EACH_VEC_SAFE_ELT (vals, i, elt)
    {
      /* Mostly ctors will have elts that don't have side-effects, so
	 the usual case is to scan all the elements.  Hence a single
	 loop for both const and side effects, rather than one loop
	 each (with early outs).  */
      if (!TREE_CONSTANT (elt->value))
	constant_p = false;
      if (TREE_SIDE_EFFECTS (elt->value))
	side_effects_p = true;
    }

  TREE_SIDE_EFFECTS (c) = side_effects_p;
  TREE_CONSTANT (c) = constant_p;

  return c;
}

/* Build a CONSTRUCTOR node made of a single initializer, with the specified
   INDEX and VALUE.  */
tree
build_constructor_single (tree type, tree index, tree value)
{
  vec<constructor_elt, va_gc> *v;
  constructor_elt elt = {index, value};

  vec_alloc (v, 1);
  v->quick_push (elt);

  return build_constructor (type, v);
}


/* Return a new CONSTRUCTOR node whose type is TYPE and whose values
   are in a list pointed to by VALS.  */
tree
build_constructor_from_list (tree type, tree vals)
{
  tree t;
  vec<constructor_elt, va_gc> *v = NULL;

  if (vals)
    {
      vec_alloc (v, list_length (vals));
      for (t = vals; t; t = TREE_CHAIN (t))
	CONSTRUCTOR_APPEND_ELT (v, TREE_PURPOSE (t), TREE_VALUE (t));
    }

  return build_constructor (type, v);
}

/* Return a new FIXED_CST node whose type is TYPE and value is F.  */

tree
build_fixed (tree type, FIXED_VALUE_TYPE f)
{
  tree v;
  FIXED_VALUE_TYPE *fp;

  v = make_node (FIXED_CST);
  fp = ggc_alloc_fixed_value ();
  memcpy (fp, &f, sizeof (FIXED_VALUE_TYPE));

  TREE_TYPE (v) = type;
  TREE_FIXED_CST_PTR (v) = fp;
  return v;
}

/* Return a new REAL_CST node whose type is TYPE and value is D.  */

tree
build_real (tree type, REAL_VALUE_TYPE d)
{
  tree v;
  REAL_VALUE_TYPE *dp;
  int overflow = 0;

  /* ??? Used to check for overflow here via CHECK_FLOAT_TYPE.
     Consider doing it via real_convert now.  */

  v = make_node (REAL_CST);
  dp = ggc_alloc_real_value ();
  memcpy (dp, &d, sizeof (REAL_VALUE_TYPE));

  TREE_TYPE (v) = type;
  TREE_REAL_CST_PTR (v) = dp;
  TREE_OVERFLOW (v) = overflow;
  return v;
}

/* Return a new REAL_CST node whose type is TYPE
   and whose value is the integer value of the INTEGER_CST node I.  */

REAL_VALUE_TYPE
real_value_from_int_cst (const_tree type, const_tree i)
{
  REAL_VALUE_TYPE d;

  /* Clear all bits of the real value type so that we can later do
     bitwise comparisons to see if two values are the same.  */
  memset (&d, 0, sizeof d);

  real_from_integer (&d, type ? TYPE_MODE (type) : VOIDmode,
		     TREE_INT_CST_LOW (i), TREE_INT_CST_HIGH (i),
		     TYPE_UNSIGNED (TREE_TYPE (i)));
  return d;
}

/* Given a tree representing an integer constant I, return a tree
   representing the same value as a floating-point constant of type TYPE.  */

tree
build_real_from_int_cst (tree type, const_tree i)
{
  tree v;
  int overflow = TREE_OVERFLOW (i);

  v = build_real (type, real_value_from_int_cst (type, i));

  TREE_OVERFLOW (v) |= overflow;
  return v;
}

/* Return a newly constructed STRING_CST node whose value is
   the LEN characters at STR.
   Note that for a C string literal, LEN should include the trailing NUL.
   The TREE_TYPE is not initialized.  */

tree
build_string (int len, const char *str)
{
  tree s;
  size_t length;

  /* Do not waste bytes provided by padding of struct tree_string.  */
  length = len + offsetof (struct tree_string, str) + 1;

  record_node_allocation_statistics (STRING_CST, length);

  s = ggc_alloc_tree_node (length);

  memset (s, 0, sizeof (struct tree_typed));
  TREE_SET_CODE (s, STRING_CST);
  TREE_CONSTANT (s) = 1;
  TREE_STRING_LENGTH (s) = len;
  memcpy (s->string.str, str, len);
  s->string.str[len] = '\0';

  return s;
}

/* Return a newly constructed COMPLEX_CST node whose value is
   specified by the real and imaginary parts REAL and IMAG.
   Both REAL and IMAG should be constant nodes.  TYPE, if specified,
   will be the type of the COMPLEX_CST; otherwise a new type will be made.  */

tree
build_complex (tree type, tree real, tree imag)
{
  tree t = make_node (COMPLEX_CST);

  TREE_REALPART (t) = real;
  TREE_IMAGPART (t) = imag;
  TREE_TYPE (t) = type ? type : build_complex_type (TREE_TYPE (real));
  TREE_OVERFLOW (t) = TREE_OVERFLOW (real) | TREE_OVERFLOW (imag);
  return t;
}

/* Return a constant of arithmetic type TYPE which is the
   multiplicative identity of the set TYPE.  */

tree
build_one_cst (tree type)
{
  switch (TREE_CODE (type))
    {
    case INTEGER_TYPE: case ENUMERAL_TYPE: case BOOLEAN_TYPE:
    case POINTER_TYPE: case REFERENCE_TYPE:
    case OFFSET_TYPE:
      return build_int_cst (type, 1);

    case REAL_TYPE:
      return build_real (type, dconst1);

    case FIXED_POINT_TYPE:
      /* We can only generate 1 for accum types.  */
      gcc_assert (ALL_SCALAR_ACCUM_MODE_P (TYPE_MODE (type)));
      return build_fixed (type, FCONST1(TYPE_MODE (type)));

    case VECTOR_TYPE:
      {
	tree scalar = build_one_cst (TREE_TYPE (type));

	return build_vector_from_val (type, scalar);
      }

    case COMPLEX_TYPE:
      return build_complex (type,
			    build_one_cst (TREE_TYPE (type)),
			    build_zero_cst (TREE_TYPE (type)));

    default:
      gcc_unreachable ();
    }
}

/* Return an integer of type TYPE containing all 1's in as much precision as
   it contains, or a complex or vector whose subparts are such integers.  */

tree
build_all_ones_cst (tree type)
{
  if (TREE_CODE (type) == COMPLEX_TYPE)
    {
      tree scalar = build_all_ones_cst (TREE_TYPE (type));
      return build_complex (type, scalar, scalar);
    }
  else
    return build_minus_one_cst (type);
}

/* Return a constant of arithmetic type TYPE which is the
   opposite of the multiplicative identity of the set TYPE.  */

tree
build_minus_one_cst (tree type)
{
  switch (TREE_CODE (type))
    {
    case INTEGER_TYPE: case ENUMERAL_TYPE: case BOOLEAN_TYPE:
    case POINTER_TYPE: case REFERENCE_TYPE:
    case OFFSET_TYPE:
      return build_int_cst (type, -1);

    case REAL_TYPE:
      return build_real (type, dconstm1);

    case FIXED_POINT_TYPE:
      /* We can only generate 1 for accum types.  */
      gcc_assert (ALL_SCALAR_ACCUM_MODE_P (TYPE_MODE (type)));
      return build_fixed (type, fixed_from_double_int (double_int_minus_one,
						       TYPE_MODE (type)));

    case VECTOR_TYPE:
      {
	tree scalar = build_minus_one_cst (TREE_TYPE (type));

	return build_vector_from_val (type, scalar);
      }

    case COMPLEX_TYPE:
      return build_complex (type,
			    build_minus_one_cst (TREE_TYPE (type)),
			    build_zero_cst (TREE_TYPE (type)));

    default:
      gcc_unreachable ();
    }
}

/* Build 0 constant of type TYPE.  This is used by constructor folding
   and thus the constant should be represented in memory by
   zero(es).  */

tree
build_zero_cst (tree type)
{
  switch (TREE_CODE (type))
    {
    case INTEGER_TYPE: case ENUMERAL_TYPE: case BOOLEAN_TYPE:
    case POINTER_TYPE: case REFERENCE_TYPE:
    case OFFSET_TYPE: case NULLPTR_TYPE:
      return build_int_cst (type, 0);

    case REAL_TYPE:
      return build_real (type, dconst0);

    case FIXED_POINT_TYPE:
      return build_fixed (type, FCONST0 (TYPE_MODE (type)));

    case VECTOR_TYPE:
      {
	tree scalar = build_zero_cst (TREE_TYPE (type));

	return build_vector_from_val (type, scalar);
      }

    case COMPLEX_TYPE:
      {
	tree zero = build_zero_cst (TREE_TYPE (type));

	return build_complex (type, zero, zero);
      }

    default:
      if (!AGGREGATE_TYPE_P (type))
	return fold_convert (type, integer_zero_node);
      return build_constructor (type, NULL);
    }
}


/* Build a BINFO with LEN language slots.  */

tree
make_tree_binfo_stat (unsigned base_binfos MEM_STAT_DECL)
{
  tree t;
  size_t length = (offsetof (struct tree_binfo, base_binfos)
		   + vec<tree, va_gc>::embedded_size (base_binfos));

  record_node_allocation_statistics (TREE_BINFO, length);

  t = ggc_alloc_tree_node_stat (length PASS_MEM_STAT);

  memset (t, 0, offsetof (struct tree_binfo, base_binfos));

  TREE_SET_CODE (t, TREE_BINFO);

  BINFO_BASE_BINFOS (t)->embedded_init (base_binfos);

  return t;
}

/* Create a CASE_LABEL_EXPR tree node and return it.  */

tree
build_case_label (tree low_value, tree high_value, tree label_decl)
{
  tree t = make_node (CASE_LABEL_EXPR);

  TREE_TYPE (t) = void_type_node;
  SET_EXPR_LOCATION (t, DECL_SOURCE_LOCATION (label_decl));

  CASE_LOW (t) = low_value;
  CASE_HIGH (t) = high_value;
  CASE_LABEL (t) = label_decl;
  CASE_CHAIN (t) = NULL_TREE;

  return t;
}

/* Build a newly constructed TREE_VEC node of length LEN.  */

tree
make_tree_vec_stat (int len MEM_STAT_DECL)
{
  tree t;
  int length = (len - 1) * sizeof (tree) + sizeof (struct tree_vec);

  record_node_allocation_statistics (TREE_VEC, length);

  t = ggc_alloc_cleared_tree_node_stat (length PASS_MEM_STAT);

  TREE_SET_CODE (t, TREE_VEC);
  TREE_VEC_LENGTH (t) = len;

  return t;
}

/* Return 1 if EXPR is the integer constant zero or a complex constant
   of zero.  */

int
integer_zerop (const_tree expr)
{
  STRIP_NOPS (expr);

  switch (TREE_CODE (expr))
    {
    case INTEGER_CST:
      return (TREE_INT_CST_LOW (expr) == 0
	      && TREE_INT_CST_HIGH (expr) == 0);
    case COMPLEX_CST:
      return (integer_zerop (TREE_REALPART (expr))
	      && integer_zerop (TREE_IMAGPART (expr)));
    case VECTOR_CST:
      {
	unsigned i;
	for (i = 0; i < VECTOR_CST_NELTS (expr); ++i)
	  if (!integer_zerop (VECTOR_CST_ELT (expr, i)))
	    return false;
	return true;
      }
    default:
      return false;
    }
}

/* Return 1 if EXPR is the integer constant one or the corresponding
   complex constant.  */

int
integer_onep (const_tree expr)
{
  STRIP_NOPS (expr);

  switch (TREE_CODE (expr))
    {
    case INTEGER_CST:
      return (TREE_INT_CST_LOW (expr) == 1
	      && TREE_INT_CST_HIGH (expr) == 0);
    case COMPLEX_CST:
      return (integer_onep (TREE_REALPART (expr))
	      && integer_zerop (TREE_IMAGPART (expr)));
    case VECTOR_CST:
      {
	unsigned i;
	for (i = 0; i < VECTOR_CST_NELTS (expr); ++i)
	  if (!integer_onep (VECTOR_CST_ELT (expr, i)))
	    return false;
	return true;
      }
    default:
      return false;
    }
}

/* Return 1 if EXPR is an integer containing all 1's in as much precision as
   it contains.  Likewise for the corresponding complex constant.  */

int
integer_all_onesp (const_tree expr)
{
  int prec;
  int uns;

  STRIP_NOPS (expr);

  if (TREE_CODE (expr) == COMPLEX_CST
      && integer_all_onesp (TREE_REALPART (expr))
      && integer_zerop (TREE_IMAGPART (expr)))
    return 1;

  else if (TREE_CODE (expr) == VECTOR_CST)
    {
      unsigned i;
      for (i = 0; i < VECTOR_CST_NELTS (expr); ++i)
	if (!integer_all_onesp (VECTOR_CST_ELT (expr, i)))
	  return 0;
      return 1;
    }

  else if (TREE_CODE (expr) != INTEGER_CST)
    return 0;

  uns = TYPE_UNSIGNED (TREE_TYPE (expr));
  if (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
      && TREE_INT_CST_HIGH (expr) == -1)
    return 1;
  if (!uns)
    return 0;

  prec = TYPE_PRECISION (TREE_TYPE (expr));
  if (prec >= HOST_BITS_PER_WIDE_INT)
    {
      HOST_WIDE_INT high_value;
      int shift_amount;

      shift_amount = prec - HOST_BITS_PER_WIDE_INT;

      /* Can not handle precisions greater than twice the host int size.  */
      gcc_assert (shift_amount <= HOST_BITS_PER_WIDE_INT);
      if (shift_amount == HOST_BITS_PER_WIDE_INT)
	/* Shifting by the host word size is undefined according to the ANSI
	   standard, so we must handle this as a special case.  */
	high_value = -1;
      else
	high_value = ((HOST_WIDE_INT) 1 << shift_amount) - 1;

      return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
	      && TREE_INT_CST_HIGH (expr) == high_value);
    }
  else
    return TREE_INT_CST_LOW (expr) == ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
}

/* Return 1 if EXPR is an integer constant that is a power of 2 (i.e., has only
   one bit on).  */

int
integer_pow2p (const_tree expr)
{
  int prec;
  unsigned HOST_WIDE_INT high, low;

  STRIP_NOPS (expr);

  if (TREE_CODE (expr) == COMPLEX_CST
      && integer_pow2p (TREE_REALPART (expr))
      && integer_zerop (TREE_IMAGPART (expr)))
    return 1;

  if (TREE_CODE (expr) != INTEGER_CST)
    return 0;

  prec = TYPE_PRECISION (TREE_TYPE (expr));
  high = TREE_INT_CST_HIGH (expr);
  low = TREE_INT_CST_LOW (expr);

  /* First clear all bits that are beyond the type's precision in case
     we've been sign extended.  */

  if (prec == HOST_BITS_PER_DOUBLE_INT)
    ;
  else if (prec > HOST_BITS_PER_WIDE_INT)
    high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
  else
    {
      high = 0;
      if (prec < HOST_BITS_PER_WIDE_INT)
	low &= ~((HOST_WIDE_INT) (-1) << prec);
    }

  if (high == 0 && low == 0)
    return 0;

  return ((high == 0 && (low & (low - 1)) == 0)
	  || (low == 0 && (high & (high - 1)) == 0));
}

/* Return 1 if EXPR is an integer constant other than zero or a
   complex constant other than zero.  */

int
integer_nonzerop (const_tree expr)
{
  STRIP_NOPS (expr);

  return ((TREE_CODE (expr) == INTEGER_CST
	   && (TREE_INT_CST_LOW (expr) != 0
	       || TREE_INT_CST_HIGH (expr) != 0))
	  || (TREE_CODE (expr) == COMPLEX_CST
	      && (integer_nonzerop (TREE_REALPART (expr))
		  || integer_nonzerop (TREE_IMAGPART (expr)))));
}

/* Return 1 if EXPR is the fixed-point constant zero.  */

int
fixed_zerop (const_tree expr)
{
  return (TREE_CODE (expr) == FIXED_CST
	  && TREE_FIXED_CST (expr).data.is_zero ());
}

/* Return the power of two represented by a tree node known to be a
   power of two.  */

int
tree_log2 (const_tree expr)
{
  int prec;
  HOST_WIDE_INT high, low;

  STRIP_NOPS (expr);

  if (TREE_CODE (expr) == COMPLEX_CST)
    return tree_log2 (TREE_REALPART (expr));

  prec = TYPE_PRECISION (TREE_TYPE (expr));
  high = TREE_INT_CST_HIGH (expr);
  low = TREE_INT_CST_LOW (expr);

  /* First clear all bits that are beyond the type's precision in case
     we've been sign extended.  */

  if (prec == HOST_BITS_PER_DOUBLE_INT)
    ;
  else if (prec > HOST_BITS_PER_WIDE_INT)
    high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
  else
    {
      high = 0;
      if (prec < HOST_BITS_PER_WIDE_INT)
	low &= ~((HOST_WIDE_INT) (-1) << prec);
    }

  return (high != 0 ? HOST_BITS_PER_WIDE_INT + exact_log2 (high)
	  : exact_log2 (low));
}

/* Similar, but return the largest integer Y such that 2 ** Y is less
   than or equal to EXPR.  */

int
tree_floor_log2 (const_tree expr)
{
  int prec;
  HOST_WIDE_INT high, low;

  STRIP_NOPS (expr);

  if (TREE_CODE (expr) == COMPLEX_CST)
    return tree_log2 (TREE_REALPART (expr));

  prec = TYPE_PRECISION (TREE_TYPE (expr));
  high = TREE_INT_CST_HIGH (expr);
  low = TREE_INT_CST_LOW (expr);

  /* First clear all bits that are beyond the type's precision in case
     we've been sign extended.  Ignore if type's precision hasn't been set
     since what we are doing is setting it.  */

  if (prec == HOST_BITS_PER_DOUBLE_INT || prec == 0)
    ;
  else if (prec > HOST_BITS_PER_WIDE_INT)
    high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
  else
    {
      high = 0;
      if (prec < HOST_BITS_PER_WIDE_INT)
	low &= ~((HOST_WIDE_INT) (-1) << prec);
    }

  return (high != 0 ? HOST_BITS_PER_WIDE_INT + floor_log2 (high)
	  : floor_log2 (low));
}

/* Return 1 if EXPR is the real constant zero.  Trailing zeroes matter for
   decimal float constants, so don't return 1 for them.  */

int
real_zerop (const_tree expr)
{
  STRIP_NOPS (expr);

  switch (TREE_CODE (expr))
    {
    case REAL_CST:
      return REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst0)
	     && !(DECIMAL_FLOAT_MODE_P (TYPE_MODE (TREE_TYPE (expr))));
    case COMPLEX_CST:
      return real_zerop (TREE_REALPART (expr))
	     && real_zerop (TREE_IMAGPART (expr));
    case VECTOR_CST:
      {
	unsigned i;
	for (i = 0; i < VECTOR_CST_NELTS (expr); ++i)
	  if (!real_zerop (VECTOR_CST_ELT (expr, i)))
	    return false;
	return true;
      }
    default:
      return false;
    }
}

/* Return 1 if EXPR is the real constant one in real or complex form.
   Trailing zeroes matter for decimal float constants, so don't return
   1 for them.  */

int
real_onep (const_tree expr)
{
  STRIP_NOPS (expr);

  switch (TREE_CODE (expr))
    {
    case REAL_CST:
      return REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst1)
	     && !(DECIMAL_FLOAT_MODE_P (TYPE_MODE (TREE_TYPE (expr))));
    case COMPLEX_CST:
      return real_onep (TREE_REALPART (expr))
	     && real_zerop (TREE_IMAGPART (expr));
    case VECTOR_CST:
      {
	unsigned i;
	for (i = 0; i < VECTOR_CST_NELTS (expr); ++i)
	  if (!real_onep (VECTOR_CST_ELT (expr, i)))
	    return false;
	return true;
      }
    default:
      return false;
    }
}

/* Return 1 if EXPR is the real constant two.  Trailing zeroes matter
   for decimal float constants, so don't return 1 for them.  */

int
real_twop (const_tree expr)
{
  STRIP_NOPS (expr);

  switch (TREE_CODE (expr))
    {
    case REAL_CST:
      return REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst2)
	     && !(DECIMAL_FLOAT_MODE_P (TYPE_MODE (TREE_TYPE (expr))));
    case COMPLEX_CST:
      return real_twop (TREE_REALPART (expr))
	     && real_zerop (TREE_IMAGPART (expr));
    case VECTOR_CST:
      {
	unsigned i;
	for (i = 0; i < VECTOR_CST_NELTS (expr); ++i)
	  if (!real_twop (VECTOR_CST_ELT (expr, i)))
	    return false;
	return true;
      }
    default:
      return false;
    }
}

/* Return 1 if EXPR is the real constant minus one.  Trailing zeroes
   matter for decimal float constants, so don't return 1 for them.  */

int
real_minus_onep (const_tree expr)
{
  STRIP_NOPS (expr);

  switch (TREE_CODE (expr))
    {
    case REAL_CST:
      return REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconstm1)
	     && !(DECIMAL_FLOAT_MODE_P (TYPE_MODE (TREE_TYPE (expr))));
    case COMPLEX_CST:
      return real_minus_onep (TREE_REALPART (expr))
	     && real_zerop (TREE_IMAGPART (expr));
    case VECTOR_CST:
      {
	unsigned i;
	for (i = 0; i < VECTOR_CST_NELTS (expr); ++i)
	  if (!real_minus_onep (VECTOR_CST_ELT (expr, i)))
	    return false;
	return true;
      }
    default:
      return false;
    }
}

/* Nonzero if EXP is a constant or a cast of a constant.  */

int
really_constant_p (const_tree exp)
{
  /* This is not quite the same as STRIP_NOPS.  It does more.  */
  while (CONVERT_EXPR_P (exp)
	 || TREE_CODE (exp) == NON_LVALUE_EXPR)
    exp = TREE_OPERAND (exp, 0);
  return TREE_CONSTANT (exp);
}

/* Return first list element whose TREE_VALUE is ELEM.
   Return 0 if ELEM is not in LIST.  */

tree
value_member (tree elem, tree list)
{
  while (list)
    {
      if (elem == TREE_VALUE (list))
	return list;
      list = TREE_CHAIN (list);
    }
  return NULL_TREE;
}

/* Return first list element whose TREE_PURPOSE is ELEM.
   Return 0 if ELEM is not in LIST.  */

tree
purpose_member (const_tree elem, tree list)
{
  while (list)
    {
      if (elem == TREE_PURPOSE (list))
	return list;
      list = TREE_CHAIN (list);
    }
  return NULL_TREE;
}

/* Return true if ELEM is in V.  */

bool
vec_member (const_tree elem, vec<tree, va_gc> *v)
{
  unsigned ix;
  tree t;
  FOR_EACH_VEC_SAFE_ELT (v, ix, t)
    if (elem == t)
      return true;
  return false;
}

/* Returns element number IDX (zero-origin) of chain CHAIN, or
   NULL_TREE.  */

tree
chain_index (int idx, tree chain)
{
  for (; chain && idx > 0; --idx)
    chain = TREE_CHAIN (chain);
  return chain;
}

/* Return nonzero if ELEM is part of the chain CHAIN.  */

int
chain_member (const_tree elem, const_tree chain)
{
  while (chain)
    {
      if (elem == chain)
	return 1;
      chain = DECL_CHAIN (chain);
    }

  return 0;
}

/* Return the length of a chain of nodes chained through TREE_CHAIN.
   We expect a null pointer to mark the end of the chain.
   This is the Lisp primitive `length'.  */

int
list_length (const_tree t)
{
  const_tree p = t;
#ifdef ENABLE_TREE_CHECKING
  const_tree q = t;
#endif
  int len = 0;

  while (p)
    {
      p = TREE_CHAIN (p);
#ifdef ENABLE_TREE_CHECKING
      if (len % 2)
	q = TREE_CHAIN (q);
      gcc_assert (p != q);
#endif
      len++;
    }

  return len;
}

/* Returns the number of FIELD_DECLs in TYPE.  */

int
fields_length (const_tree type)
{
  tree t = TYPE_FIELDS (type);
  int count = 0;

  for (; t; t = DECL_CHAIN (t))
    if (TREE_CODE (t) == FIELD_DECL)
      ++count;

  return count;
}

/* Returns the first FIELD_DECL in the TYPE_FIELDS of the RECORD_TYPE or
   UNION_TYPE TYPE, or NULL_TREE if none.  */

tree
first_field (const_tree type)
{
  tree t = TYPE_FIELDS (type);
  while (t && TREE_CODE (t) != FIELD_DECL)
    t = TREE_CHAIN (t);
  return t;
}

/* Concatenate two chains of nodes (chained through TREE_CHAIN)
   by modifying the last node in chain 1 to point to chain 2.
   This is the Lisp primitive `nconc'.  */

tree
chainon (tree op1, tree op2)
{
  tree t1;

  if (!op1)
    return op2;
  if (!op2)
    return op1;

  for (t1 = op1; TREE_CHAIN (t1); t1 = TREE_CHAIN (t1))
    continue;
  TREE_CHAIN (t1) = op2;

#ifdef ENABLE_TREE_CHECKING
  {
    tree t2;
    for (t2 = op2; t2; t2 = TREE_CHAIN (t2))
      gcc_assert (t2 != t1);
  }
#endif

  return op1;
}

/* Return the last node in a chain of nodes (chained through TREE_CHAIN).  */

tree
tree_last (tree chain)
{
  tree next;
  if (chain)
    while ((next = TREE_CHAIN (chain)))
      chain = next;
  return chain;
}

/* Reverse the order of elements in the chain T,
   and return the new head of the chain (old last element).  */

tree
nreverse (tree t)
{
  tree prev = 0, decl, next;
  for (decl = t; decl; decl = next)
    {
      /* We shouldn't be using this function to reverse BLOCK chains; we
	 have blocks_nreverse for that.  */
      gcc_checking_assert (TREE_CODE (decl) != BLOCK);
      next = TREE_CHAIN (decl);
      TREE_CHAIN (decl) = prev;
      prev = decl;
    }
  return prev;
}

/* Return a newly created TREE_LIST node whose
   purpose and value fields are PARM and VALUE.  */

tree
build_tree_list_stat (tree parm, tree value MEM_STAT_DECL)
{
  tree t = make_node_stat (TREE_LIST PASS_MEM_STAT);
  TREE_PURPOSE (t) = parm;
  TREE_VALUE (t) = value;
  return t;
}

/* Build a chain of TREE_LIST nodes from a vector.  */

tree
build_tree_list_vec_stat (const vec<tree, va_gc> *vec MEM_STAT_DECL)
{
  tree ret = NULL_TREE;
  tree *pp = &ret;
  unsigned int i;
  tree t;
  FOR_EACH_VEC_SAFE_ELT (vec, i, t)
    {
      *pp = build_tree_list_stat (NULL, t PASS_MEM_STAT);
      pp = &TREE_CHAIN (*pp);
    }
  return ret;
}

/* Return a newly created TREE_LIST node whose
   purpose and value fields are PURPOSE and VALUE
   and whose TREE_CHAIN is CHAIN.  */

tree 
tree_cons_stat (tree purpose, tree value, tree chain MEM_STAT_DECL)
{
  tree node;

  node = ggc_alloc_tree_node_stat (sizeof (struct tree_list) PASS_MEM_STAT);
  memset (node, 0, sizeof (struct tree_common));

  record_node_allocation_statistics (TREE_LIST, sizeof (struct tree_list));

  TREE_SET_CODE (node, TREE_LIST);
  TREE_CHAIN (node) = chain;
  TREE_PURPOSE (node) = purpose;
  TREE_VALUE (node) = value;
  return node;
}

/* Return the values of the elements of a CONSTRUCTOR as a vector of
   trees.  */

vec<tree, va_gc> *
ctor_to_vec (tree ctor)
{
  vec<tree, va_gc> *vec;
  vec_alloc (vec, CONSTRUCTOR_NELTS (ctor));
  unsigned int ix;
  tree val;

  FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (ctor), ix, val)
    vec->quick_push (val);

  return vec;
}

/* Return the size nominally occupied by an object of type TYPE
   when it resides in memory.  The value is measured in units of bytes,
   and its data type is that normally used for type sizes
   (which is the first type created by make_signed_type or
   make_unsigned_type).  */

tree
size_in_bytes (const_tree type)
{
  tree t;

  if (type == error_mark_node)
    return integer_zero_node;

  type = TYPE_MAIN_VARIANT (type);
  t = TYPE_SIZE_UNIT (type);

  if (t == 0)
    {
      lang_hooks.types.incomplete_type_error (NULL_TREE, type);
      return size_zero_node;
    }

  return t;
}

/* Return the size of TYPE (in bytes) as a wide integer
   or return -1 if the size can vary or is larger than an integer.  */

HOST_WIDE_INT
int_size_in_bytes (const_tree type)
{
  tree t;

  if (type == error_mark_node)
    return 0;

  type = TYPE_MAIN_VARIANT (type);
  t = TYPE_SIZE_UNIT (type);
  if (t == 0
      || TREE_CODE (t) != INTEGER_CST
      || TREE_INT_CST_HIGH (t) != 0
      /* If the result would appear negative, it's too big to represent.  */
      || (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0)
    return -1;

  return TREE_INT_CST_LOW (t);
}

/* Return the maximum size of TYPE (in bytes) as a wide integer
   or return -1 if the size can vary or is larger than an integer.  */

HOST_WIDE_INT
max_int_size_in_bytes (const_tree type)
{
  HOST_WIDE_INT size = -1;
  tree size_tree;

  /* If this is an array type, check for a possible MAX_SIZE attached.  */

  if (TREE_CODE (type) == ARRAY_TYPE)
    {
      size_tree = TYPE_ARRAY_MAX_SIZE (type);

      if (size_tree && host_integerp (size_tree, 1))
	size = tree_low_cst (size_tree, 1);
    }

  /* If we still haven't been able to get a size, see if the language
     can compute a maximum size.  */

  if (size == -1)
    {
      size_tree = lang_hooks.types.max_size (type);

      if (size_tree && host_integerp (size_tree, 1))
	size = tree_low_cst (size_tree, 1);
    }

  return size;
}

/* Returns a tree for the size of EXP in bytes.  */

tree
tree_expr_size (const_tree exp)
{
  if (DECL_P (exp)
      && DECL_SIZE_UNIT (exp) != 0)
    return DECL_SIZE_UNIT (exp);
  else
    return size_in_bytes (TREE_TYPE (exp));
}

/* Return the bit position of FIELD, in bits from the start of the record.
   This is a tree of type bitsizetype.  */

tree
bit_position (const_tree field)
{
  return bit_from_pos (DECL_FIELD_OFFSET (field),
		       DECL_FIELD_BIT_OFFSET (field));
}

/* Likewise, but return as an integer.  It must be representable in
   that way (since it could be a signed value, we don't have the
   option of returning -1 like int_size_in_byte can.  */

HOST_WIDE_INT
int_bit_position (const_tree field)
{
  return tree_low_cst (bit_position (field), 0);
}

/* Return the byte position of FIELD, in bytes from the start of the record.
   This is a tree of type sizetype.  */

tree
byte_position (const_tree field)
{
  return byte_from_pos (DECL_FIELD_OFFSET (field),
			DECL_FIELD_BIT_OFFSET (field));
}

/* Likewise, but return as an integer.  It must be representable in
   that way (since it could be a signed value, we don't have the
   option of returning -1 like int_size_in_byte can.  */

HOST_WIDE_INT
int_byte_position (const_tree field)
{
  return tree_low_cst (byte_position (field), 0);
}

/* Return the strictest alignment, in bits, that T is known to have.  */

unsigned int
expr_align (const_tree t)
{
  unsigned int align0, align1;

  switch (TREE_CODE (t))
    {
    CASE_CONVERT:  case NON_LVALUE_EXPR:
      /* If we have conversions, we know that the alignment of the
	 object must meet each of the alignments of the types.  */
      align0 = expr_align (TREE_OPERAND (t, 0));
      align1 = TYPE_ALIGN (TREE_TYPE (t));
      return MAX (align0, align1);

    case SAVE_EXPR:         case COMPOUND_EXPR:       case MODIFY_EXPR:
    case INIT_EXPR:         case TARGET_EXPR:         case WITH_CLEANUP_EXPR:
    case CLEANUP_POINT_EXPR:
      /* These don't change the alignment of an object.  */
      return expr_align (TREE_OPERAND (t, 0));

    case COND_EXPR:
      /* The best we can do is say that the alignment is the least aligned
	 of the two arms.  */
      align0 = expr_align (TREE_OPERAND (t, 1));
      align1 = expr_align (TREE_OPERAND (t, 2));
      return MIN (align0, align1);

      /* FIXME: LABEL_DECL and CONST_DECL never have DECL_ALIGN set
	 meaningfully, it's always 1.  */
    case LABEL_DECL:     case CONST_DECL:
    case VAR_DECL:       case PARM_DECL:   case RESULT_DECL:
    case FUNCTION_DECL:
      gcc_assert (DECL_ALIGN (t) != 0);
      return DECL_ALIGN (t);

    default:
      break;
    }

  /* Otherwise take the alignment from that of the type.  */
  return TYPE_ALIGN (TREE_TYPE (t));
}

/* Return, as a tree node, the number of elements for TYPE (which is an
   ARRAY_TYPE) minus one. This counts only elements of the top array.  */

tree
array_type_nelts (const_tree type)
{
  tree index_type, min, max;

  /* If they did it with unspecified bounds, then we should have already
     given an error about it before we got here.  */
  if (! TYPE_DOMAIN (type))
    return error_mark_node;

  index_type = TYPE_DOMAIN (type);
  min = TYPE_MIN_VALUE (index_type);
  max = TYPE_MAX_VALUE (index_type);

  /* TYPE_MAX_VALUE may not be set if the array has unknown length.  */
  if (!max)
    return error_mark_node;

  return (integer_zerop (min)
	  ? max
	  : fold_build2 (MINUS_EXPR, TREE_TYPE (max), max, min));
}

/* If arg is static -- a reference to an object in static storage -- then
   return the object.  This is not the same as the C meaning of `static'.
   If arg isn't static, return NULL.  */

tree
staticp (tree arg)
{
  switch (TREE_CODE (arg))
    {
    case FUNCTION_DECL:
      /* Nested functions are static, even though taking their address will
	 involve a trampoline as we unnest the nested function and create
	 the trampoline on the tree level.  */
      return arg;

    case VAR_DECL:
      return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
	      && ! DECL_THREAD_LOCAL_P (arg)
	      && ! DECL_DLLIMPORT_P (arg)
	      ? arg : NULL);

    case CONST_DECL:
      return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
	      ? arg : NULL);

    case CONSTRUCTOR:
      return TREE_STATIC (arg) ? arg : NULL;

    case LABEL_DECL:
    case STRING_CST:
      return arg;

    case COMPONENT_REF:
      /* If the thing being referenced is not a field, then it is
	 something language specific.  */
      gcc_assert (TREE_CODE (TREE_OPERAND (arg, 1)) == FIELD_DECL);

      /* If we are referencing a bitfield, we can't evaluate an
	 ADDR_EXPR at compile time and so it isn't a constant.  */
      if (DECL_BIT_FIELD (TREE_OPERAND (arg, 1)))
	return NULL;

      return staticp (TREE_OPERAND (arg, 0));

    case BIT_FIELD_REF:
      return NULL;

    case INDIRECT_REF:
      return TREE_CONSTANT (TREE_OPERAND (arg, 0)) ? arg : NULL;

    case ARRAY_REF:
    case ARRAY_RANGE_REF:
      if (TREE_CODE (TYPE_SIZE (TREE_TYPE (arg))) == INTEGER_CST
	  && TREE_CODE (TREE_OPERAND (arg, 1)) == INTEGER_CST)
	return staticp (TREE_OPERAND (arg, 0));
      else
	return NULL;

    case COMPOUND_LITERAL_EXPR:
      return TREE_STATIC (COMPOUND_LITERAL_EXPR_DECL (arg)) ? arg : NULL;

    default:
      return NULL;
    }
}




/* Return whether OP is a DECL whose address is function-invariant.  */

bool
decl_address_invariant_p (const_tree op)
{
  /* The conditions below are slightly less strict than the one in
     staticp.  */

  switch (TREE_CODE (op))
    {
    case PARM_DECL:
    case RESULT_DECL:
    case LABEL_DECL:
    case FUNCTION_DECL:
      return true;

    case VAR_DECL:
      if ((TREE_STATIC (op) || DECL_EXTERNAL (op))
          || DECL_THREAD_LOCAL_P (op)
          || DECL_CONTEXT (op) == current_function_decl
          || decl_function_context (op) == current_function_decl)
        return true;
      break;

    case CONST_DECL:
      if ((TREE_STATIC (op) || DECL_EXTERNAL (op))
          || decl_function_context (op) == current_function_decl)
        return true;
      break;

    default:
      break;
    }

  return false;
}

/* Return whether OP is a DECL whose address is interprocedural-invariant.  */

bool
decl_address_ip_invariant_p (const_tree op)
{
  /* The conditions below are slightly less strict than the one in
     staticp.  */

  switch (TREE_CODE (op))
    {
    case LABEL_DECL:
    case FUNCTION_DECL:
    case STRING_CST:
      return true;

    case VAR_DECL:
      if (((TREE_STATIC (op) || DECL_EXTERNAL (op))
           && !DECL_DLLIMPORT_P (op))
          || DECL_THREAD_LOCAL_P (op))
        return true;
      break;

    case CONST_DECL:
      if ((TREE_STATIC (op) || DECL_EXTERNAL (op)))
        return true;
      break;

    default:
      break;
    }

  return false;
}


/* Return true if T is function-invariant (internal function, does
   not handle arithmetic; that's handled in skip_simple_arithmetic and
   tree_invariant_p).  */

static bool tree_invariant_p (tree t);

static bool
tree_invariant_p_1 (tree t)
{
  tree op;

  if (TREE_CONSTANT (t)
      || (TREE_READONLY (t) && !TREE_SIDE_EFFECTS (t)))
    return true;

  switch (TREE_CODE (t))
    {
    case SAVE_EXPR:
      return true;

    case ADDR_EXPR:
      op = TREE_OPERAND (t, 0);
      while (handled_component_p (op))
	{
	  switch (TREE_CODE (op))
	    {
	    case ARRAY_REF:
	    case ARRAY_RANGE_REF:
	      if (!tree_invariant_p (TREE_OPERAND (op, 1))
		  || TREE_OPERAND (op, 2) != NULL_TREE
		  || TREE_OPERAND (op, 3) != NULL_TREE)
		return false;
	      break;

	    case COMPONENT_REF:
	      if (TREE_OPERAND (op, 2) != NULL_TREE)
		return false;
	      break;

	    default:;
	    }
	  op = TREE_OPERAND (op, 0);
	}

      return CONSTANT_CLASS_P (op) || decl_address_invariant_p (op);

    default:
      break;
    }

  return false;
}

/* Return true if T is function-invariant.  */

static bool
tree_invariant_p (tree t)
{
  tree inner = skip_simple_arithmetic (t);
  return tree_invariant_p_1 (inner);
}

/* Wrap a SAVE_EXPR around EXPR, if appropriate.
   Do this to any expression which may be used in more than one place,
   but must be evaluated only once.

   Normally, expand_expr would reevaluate the expression each time.
   Calling save_expr produces something that is evaluated and recorded
   the first time expand_expr is called on it.  Subsequent calls to
   expand_expr just reuse the recorded value.

   The call to expand_expr that generates code that actually computes
   the value is the first call *at compile time*.  Subsequent calls
   *at compile time* generate code to use the saved value.
   This produces correct result provided that *at run time* control
   always flows through the insns made by the first expand_expr
   before reaching the other places where the save_expr was evaluated.
   You, the caller of save_expr, must make sure this is so.

   Constants, and certain read-only nodes, are returned with no
   SAVE_EXPR because that is safe.  Expressions containing placeholders
   are not touched; see tree.def for an explanation of what these
   are used for.  */

tree
save_expr (tree expr)
{
  tree t = fold (expr);
  tree inner;

  /* If the tree evaluates to a constant, then we don't want to hide that
     fact (i.e. this allows further folding, and direct checks for constants).
     However, a read-only object that has side effects cannot be bypassed.
     Since it is no problem to reevaluate literals, we just return the
     literal node.  */
  inner = skip_simple_arithmetic (t);
  if (TREE_CODE (inner) == ERROR_MARK)
    return inner;

  if (tree_invariant_p_1 (inner))
    return t;

  /* If INNER contains a PLACEHOLDER_EXPR, we must evaluate it each time, since
     it means that the size or offset of some field of an object depends on
     the value within another field.

     Note that it must not be the case that T contains both a PLACEHOLDER_EXPR
     and some variable since it would then need to be both evaluated once and
     evaluated more than once.  Front-ends must assure this case cannot
     happen by surrounding any such subexpressions in their own SAVE_EXPR
     and forcing evaluation at the proper time.  */
  if (contains_placeholder_p (inner))
    return t;

  t = build1 (SAVE_EXPR, TREE_TYPE (expr), t);
  SET_EXPR_LOCATION (t, EXPR_LOCATION (expr));

  /* This expression might be placed ahead of a jump to ensure that the
     value was computed on both sides of the jump.  So make sure it isn't
     eliminated as dead.  */
  TREE_SIDE_EFFECTS (t) = 1;
  return t;
}

/* Look inside EXPR and into any simple arithmetic operations.  Return
   the innermost non-arithmetic node.  */

tree
skip_simple_arithmetic (tree expr)
{
  tree inner;

  /* We don't care about whether this can be used as an lvalue in this
     context.  */
  while (TREE_CODE (expr) == NON_LVALUE_EXPR)
    expr = TREE_OPERAND (expr, 0);

  /* If we have simple operations applied to a SAVE_EXPR or to a SAVE_EXPR and
     a constant, it will be more efficient to not make another SAVE_EXPR since
     it will allow better simplification and GCSE will be able to merge the
     computations if they actually occur.  */
  inner = expr;
  while (1)
    {
      if (UNARY_CLASS_P (inner))
	inner = TREE_OPERAND (inner, 0);
      else if (BINARY_CLASS_P (inner))
	{
	  if (tree_invariant_p (TREE_OPERAND (inner, 1)))
	    inner = TREE_OPERAND (inner, 0);
	  else if (tree_invariant_p (TREE_OPERAND (inner, 0)))
	    inner = TREE_OPERAND (inner, 1);
	  else
	    break;
	}
      else
	break;
    }

  return inner;
}


/* Return which tree structure is used by T.  */

enum tree_node_structure_enum
tree_node_structure (const_tree t)
{
  const enum tree_code code = TREE_CODE (t);
  return tree_node_structure_for_code (code);
}

/* Set various status flags when building a CALL_EXPR object T.  */

static void
process_call_operands (tree t)
{
  bool side_effects = TREE_SIDE_EFFECTS (t);
  bool read_only = false;
  int i = call_expr_flags (t);

  /* Calls have side-effects, except those to const or pure functions.  */
  if ((i & ECF_LOOPING_CONST_OR_PURE) || !(i & (ECF_CONST | ECF_PURE)))
    side_effects = true;
  /* Propagate TREE_READONLY of arguments for const functions.  */
  if (i & ECF_CONST)
    read_only = true;

  if (!side_effects || read_only)
    for (i = 1; i < TREE_OPERAND_LENGTH (t); i++)
      {
	tree op = TREE_OPERAND (t, i);
	if (op && TREE_SIDE_EFFECTS (op))
	  side_effects = true;
	if (op && !TREE_READONLY (op) && !CONSTANT_CLASS_P (op))
	  read_only = false;
      }

  TREE_SIDE_EFFECTS (t) = side_effects;
  TREE_READONLY (t) = read_only;
}

/* Return true if EXP contains a PLACEHOLDER_EXPR, i.e. if it represents a
   size or offset that depends on a field within a record.  */

bool
contains_placeholder_p (const_tree exp)
{
  enum tree_code code;

  if (!exp)
    return 0;

  code = TREE_CODE (exp);
  if (code == PLACEHOLDER_EXPR)
    return 1;

  switch (TREE_CODE_CLASS (code))
    {
    case tcc_reference:
      /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit
	 position computations since they will be converted into a
	 WITH_RECORD_EXPR involving the reference, which will assume
	 here will be valid.  */
      return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));

    case tcc_exceptional:
      if (code == TREE_LIST)
	return (CONTAINS_PLACEHOLDER_P (TREE_VALUE (exp))
		|| CONTAINS_PLACEHOLDER_P (TREE_CHAIN (exp)));
      break;

    case tcc_unary:
    case tcc_binary:
    case tcc_comparison:
    case tcc_expression:
      switch (code)
	{
	case COMPOUND_EXPR:
	  /* Ignoring the first operand isn't quite right, but works best.  */
	  return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));

	case COND_EXPR:
	  return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
		  || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))
		  || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2)));

	case SAVE_EXPR:
	  /* The save_expr function never wraps anything containing
	     a PLACEHOLDER_EXPR. */
	  return 0;

	default:
	  break;
	}

      switch (TREE_CODE_LENGTH (code))
	{
	case 1:
	  return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
	case 2:
	  return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
		  || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)));
	default:
	  return 0;
	}

    case tcc_vl_exp:
      switch (code)
	{
	case CALL_EXPR:
	  {
	    const_tree arg;
	    const_call_expr_arg_iterator iter;
	    FOR_EACH_CONST_CALL_EXPR_ARG (arg, iter, exp)
	      if (CONTAINS_PLACEHOLDER_P (arg))
		return 1;
	    return 0;
	  }
	default:
	  return 0;
	}

    default:
      return 0;
    }
  return 0;
}

/* Return true if any part of the structure of TYPE involves a PLACEHOLDER_EXPR
   directly.  This includes size, bounds, qualifiers (for QUAL_UNION_TYPE) and
   field positions.  */

static bool
type_contains_placeholder_1 (const_tree type)
{
  /* If the size contains a placeholder or the parent type (component type in
     the case of arrays) type involves a placeholder, this type does.  */
  if (CONTAINS_PLACEHOLDER_P (TYPE_SIZE (type))
      || CONTAINS_PLACEHOLDER_P (TYPE_SIZE_UNIT (type))
      || (!POINTER_TYPE_P (type)
	  && TREE_TYPE (type)
	  && type_contains_placeholder_p (TREE_TYPE (type))))
    return true;

  /* Now do type-specific checks.  Note that the last part of the check above
     greatly limits what we have to do below.  */
  switch (TREE_CODE (type))
    {
    case VOID_TYPE:
    case COMPLEX_TYPE:
    case ENUMERAL_TYPE:
    case BOOLEAN_TYPE:
    case POINTER_TYPE:
    case OFFSET_TYPE:
    case REFERENCE_TYPE:
    case METHOD_TYPE:
    case FUNCTION_TYPE:
    case VECTOR_TYPE:
    case NULLPTR_TYPE:
      return false;

    case INTEGER_TYPE:
    case REAL_TYPE:
    case FIXED_POINT_TYPE:
      /* Here we just check the bounds.  */
      return (CONTAINS_PLACEHOLDER_P (TYPE_MIN_VALUE (type))
	      || CONTAINS_PLACEHOLDER_P (TYPE_MAX_VALUE (type)));

    case ARRAY_TYPE:
      /* We have already checked the component type above, so just check the
	 domain type.  */
      return type_contains_placeholder_p (TYPE_DOMAIN (type));

    case RECORD_TYPE:
    case UNION_TYPE:
    case QUAL_UNION_TYPE:
      {
	tree field;

	for (field = TYPE_FIELDS (type); field; field = DECL_CHAIN (field))
	  if (TREE_CODE (field) == FIELD_DECL
	      && (CONTAINS_PLACEHOLDER_P (DECL_FIELD_OFFSET (field))
		  || (TREE_CODE (type) == QUAL_UNION_TYPE
		      && CONTAINS_PLACEHOLDER_P (DECL_QUALIFIER (field)))
		  || type_contains_placeholder_p (TREE_TYPE (field))))
	    return true;

	return false;
      }

    default:
      gcc_unreachable ();
    }
}

/* Wrapper around above function used to cache its result.  */

bool
type_contains_placeholder_p (tree type)
{
  bool result;

  /* If the contains_placeholder_bits field has been initialized,
     then we know the answer.  */
  if (TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) > 0)
    return TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) - 1;

  /* Indicate that we've seen this type node, and the answer is false.
     This is what we want to return if we run into recursion via fields.  */
  TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = 1;

  /* Compute the real value.  */
  result = type_contains_placeholder_1 (type);

  /* Store the real value.  */
  TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = result + 1;

  return result;
}

/* Push tree EXP onto vector QUEUE if it is not already present.  */

static void
push_without_duplicates (tree exp, vec<tree> *queue)
{
  unsigned int i;
  tree iter;

  FOR_EACH_VEC_ELT (*queue, i, iter)
    if (simple_cst_equal (iter, exp) == 1)
      break;

  if (!iter)
    queue->safe_push (exp);
}

/* Given a tree EXP, find all occurrences of references to fields
   in a PLACEHOLDER_EXPR and place them in vector REFS without
   duplicates.  Also record VAR_DECLs and CONST_DECLs.  Note that
   we assume here that EXP contains only arithmetic expressions
   or CALL_EXPRs with PLACEHOLDER_EXPRs occurring only in their
   argument list.  */

void
find_placeholder_in_expr (tree exp, vec<tree> *refs)
{
  enum tree_code code = TREE_CODE (exp);
  tree inner;
  int i;

  /* We handle TREE_LIST and COMPONENT_REF separately.  */
  if (code == TREE_LIST)
    {
      FIND_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), refs);
      FIND_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), refs);
    }
  else if (code == COMPONENT_REF)
    {
      for (inner = TREE_OPERAND (exp, 0);
	   REFERENCE_CLASS_P (inner);
	   inner = TREE_OPERAND (inner, 0))
	;

      if (TREE_CODE (inner) == PLACEHOLDER_EXPR)
	push_without_duplicates (exp, refs);
      else
	FIND_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), refs);
   }
  else
    switch (TREE_CODE_CLASS (code))
      {
      case tcc_constant:
	break;

      case tcc_declaration:
	/* Variables allocated to static storage can stay.  */
        if (!TREE_STATIC (exp))
	  push_without_duplicates (exp, refs);
	break;

      case tcc_expression:
	/* This is the pattern built in ada/make_aligning_type.  */
	if (code == ADDR_EXPR
	    && TREE_CODE (TREE_OPERAND (exp, 0)) == PLACEHOLDER_EXPR)
	  {
	    push_without_duplicates (exp, refs);
	    break;
	  }

        /* Fall through...  */

      case tcc_exceptional:
      case tcc_unary:
      case tcc_binary:
      case tcc_comparison:
      case tcc_reference:
	for (i = 0; i < TREE_CODE_LENGTH (code); i++)
	  FIND_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, i), refs);
	break;

      case tcc_vl_exp:
	for (i = 1; i < TREE_OPERAND_LENGTH (exp); i++)
	  FIND_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, i), refs);
	break;

      default:
	gcc_unreachable ();
      }
}

/* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
   return a tree with all occurrences of references to F in a
   PLACEHOLDER_EXPR replaced by R.  Also handle VAR_DECLs and
   CONST_DECLs.  Note that we assume here that EXP contains only
   arithmetic expressions or CALL_EXPRs with PLACEHOLDER_EXPRs
   occurring only in their argument list.  */

tree
substitute_in_expr (tree exp, tree f, tree r)
{
  enum tree_code code = TREE_CODE (exp);
  tree op0, op1, op2, op3;
  tree new_tree;

  /* We handle TREE_LIST and COMPONENT_REF separately.  */
  if (code == TREE_LIST)
    {
      op0 = SUBSTITUTE_IN_EXPR (TREE_CHAIN (exp), f, r);
      op1 = SUBSTITUTE_IN_EXPR (TREE_VALUE (exp), f, r);
      if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
	return exp;

      return tree_cons (TREE_PURPOSE (exp), op1, op0);
    }
  else if (code == COMPONENT_REF)
    {
      tree inner;

      /* If this expression is getting a value from a PLACEHOLDER_EXPR
	 and it is the right field, replace it with R.  */
      for (inner = TREE_OPERAND (exp, 0);
	   REFERENCE_CLASS_P (inner);
	   inner = TREE_OPERAND (inner, 0))
	;

      /* The field.  */
      op1 = TREE_OPERAND (exp, 1);

      if (TREE_CODE (inner) == PLACEHOLDER_EXPR && op1 == f)
	return r;

      /* If this expression hasn't been completed let, leave it alone.  */
      if (TREE_CODE (inner) == PLACEHOLDER_EXPR && !TREE_TYPE (inner))
	return exp;

      op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
      if (op0 == TREE_OPERAND (exp, 0))
	return exp;

      new_tree
	= fold_build3 (COMPONENT_REF, TREE_TYPE (exp), op0, op1, NULL_TREE);
   }
  else
    switch (TREE_CODE_CLASS (code))
      {
      case tcc_constant:
	return exp;

      case tcc_declaration:
	if (exp == f)
	  return r;
	else
	  return exp;

      case tcc_expression:
	if (exp == f)
	  return r;

        /* Fall through...  */

      case tcc_exceptional:
      case tcc_unary:
      case tcc_binary:
      case tcc_comparison:
      case tcc_reference:
	switch (TREE_CODE_LENGTH (code))
	  {
	  case 0:
	    return exp;

	  case 1:
	    op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
	    if (op0 == TREE_OPERAND (exp, 0))
	      return exp;

	    new_tree = fold_build1 (code, TREE_TYPE (exp), op0);
	    break;

	  case 2:
	    op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
	    op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);

	    if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
	      return exp;

	    new_tree = fold_build2 (code, TREE_TYPE (exp), op0, op1);
	    break;

	  case 3:
	    op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
	    op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
	    op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp,