gcc/tree.c

   1 /* Language-independent node constructors for parse phase of GNU compiler.
   2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
   4    Free Software Foundation, Inc.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 2, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to the Free
  20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  21 02110-1301, USA.  */
  22
  23 /* This file contains the low level primitives for operating on tree nodes,
  24    including allocation, list operations, interning of identifiers,
  25    construction of data type nodes and statement nodes,
  26    and construction of type conversion nodes.  It also contains
  27    tables index by tree code that describe how to take apart
  28    nodes of that code.
  29
  30    It is intended to be language-independent, but occasionally
  31    calls language-dependent routines defined (for C) in typecheck.c.  */
  32
  33 #include "config.h"
  34 #include "system.h"
  35 #include "coretypes.h"
  36 #include "tm.h"
  37 #include "flags.h"
  38 #include "tree.h"
  39 #include "real.h"
  40 #include "tm_p.h"
  41 #include "function.h"
  42 #include "obstack.h"
  43 #include "toplev.h"
  44 #include "ggc.h"
  45 #include "hashtab.h"
  46 #include "output.h"
  47 #include "target.h"
  48 #include "langhooks.h"
  49 #include "tree-iterator.h"
  50 #include "basic-block.h"
  51 #include "tree-flow.h"
  52 #include "params.h"
  53 #include "pointer-set.h"
  54
  55 /* Each tree code class has an associated string representation.
  56    These must correspond to the tree_code_class entries.  */
  57
  58 const char *const tree_code_class_strings[] =
  59 {
  60   "exceptional",
  61   "constant",
  62   "type",
  63   "declaration",
  64   "reference",
  65   "comparison",
  66   "unary",
  67   "binary",
  68   "statement",
  69   "expression",
  70 };
  71
  72 /* obstack.[ch] explicitly declined to prototype this.  */
  73 extern int _obstack_allocated_p (struct obstack *h, void *obj);
  74
  75 #ifdef GATHER_STATISTICS
  76 /* Statistics-gathering stuff.  */
  77
  78 int tree_node_counts[(int) all_kinds];
  79 int tree_node_sizes[(int) all_kinds];
  80
  81 /* Keep in sync with tree.h:enum tree_node_kind.  */
  82 static const char * const tree_node_kind_names[] = {
  83   "decls",
  84   "types",
  85   "blocks",
  86   "stmts",
  87   "refs",
  88   "exprs",
  89   "constants",
  90   "identifiers",
  91   "perm_tree_lists",
  92   "temp_tree_lists",
  93   "vecs",
  94   "binfos",
  95   "phi_nodes",
  96   "ssa names",
  97   "constructors",
  98   "random kinds",
  99   "lang_decl kinds",
 100   "lang_type kinds",
 101   "omp clauses"
 102 };
 103 #endif /* GATHER_STATISTICS */
 104
 105 /* Unique id for next decl created.  */
 106 static GTY(()) int next_decl_uid;
 107 /* Unique id for next type created.  */
 108 static GTY(()) int next_type_uid = 1;
 109
 110 /* Since we cannot rehash a type after it is in the table, we have to
 111    keep the hash code.  */
 112
 113 struct type_hash GTY(())
 114 {
 115   unsigned long hash;
 116   tree type;
 117 };
 118
 119 /* Initial size of the hash table (rounded to next prime).  */
 120 #define TYPE_HASH_INITIAL_SIZE 1000
 121
 122 /* Now here is the hash table.  When recording a type, it is added to
 123    the slot whose index is the hash code.  Note that the hash table is
 124    used for several kinds of types (function types, array types and
 125    array index range types, for now).  While all these live in the
 126    same table, they are completely independent, and the hash code is
 127    computed differently for each of these.  */
 128
 129 static GTY ((if_marked ("type_hash_marked_p"), param_is (struct type_hash)))
 130      htab_t type_hash_table;
 131
 132 /* Hash table and temporary node for larger integer const values.  */
 133 static GTY (()) tree int_cst_node;
 134 static GTY ((if_marked ("ggc_marked_p"), param_is (union tree_node)))
 135      htab_t int_cst_hash_table;
 136
 137 /* General tree->tree mapping  structure for use in hash tables.  */
 138
 139
 140 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
 141      htab_t debug_expr_for_decl;
 142
 143 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
 144      htab_t value_expr_for_decl;
 145
 146 static GTY ((if_marked ("tree_int_map_marked_p"), param_is (struct tree_int_map)))
 147   htab_t init_priority_for_decl;
 148
 149 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
 150   htab_t restrict_base_for_decl;
 151
 152 struct tree_int_map GTY(())
 153 {
 154   tree from;
 155   unsigned short to;
 156 };
 157 static unsigned int tree_int_map_hash (const void *);
 158 static int tree_int_map_eq (const void *, const void *);
 159 static int tree_int_map_marked_p (const void *);
 160 static void set_type_quals (tree, int);
 161 static int type_hash_eq (const void *, const void *);
 162 static hashval_t type_hash_hash (const void *);
 163 static hashval_t int_cst_hash_hash (const void *);
 164 static int int_cst_hash_eq (const void *, const void *);
 165 static void print_type_hash_statistics (void);
 166 static void print_debug_expr_statistics (void);
 167 static void print_value_expr_statistics (void);
 168 static int type_hash_marked_p (const void *);
 169 static unsigned int type_hash_list (tree, hashval_t);
 170 static unsigned int attribute_hash_list (tree, hashval_t);
 171
 172 tree global_trees[TI_MAX];
 173 tree integer_types[itk_none];
 174
 175 unsigned char tree_contains_struct[256][64];
 176
 177 /* Number of operands for each OpenMP clause.  */
 178 unsigned const char omp_clause_num_ops[] =
 179 {
 180   0, /* OMP_CLAUSE_ERROR  */
 181   1, /* OMP_CLAUSE_PRIVATE  */
 182   1, /* OMP_CLAUSE_SHARED  */
 183   1, /* OMP_CLAUSE_FIRSTPRIVATE  */
 184   1, /* OMP_CLAUSE_LASTPRIVATE  */
 185   4, /* OMP_CLAUSE_REDUCTION  */
 186   1, /* OMP_CLAUSE_COPYIN  */
 187   1, /* OMP_CLAUSE_COPYPRIVATE  */
 188   1, /* OMP_CLAUSE_IF  */
 189   1, /* OMP_CLAUSE_NUM_THREADS  */
 190   1, /* OMP_CLAUSE_SCHEDULE  */
 191   0, /* OMP_CLAUSE_NOWAIT  */
 192   0, /* OMP_CLAUSE_ORDERED  */
 193   0  /* OMP_CLAUSE_DEFAULT  */
 194 };
 195
 196 const char * const omp_clause_code_name[] =
 197 {
 198   "error_clause",
 199   "private",
 200   "shared",
 201   "firstprivate",
 202   "lastprivate",
 203   "reduction",
 204   "copyin",
 205   "copyprivate",
 206   "if",
 207   "num_threads",
 208   "schedule",
 209   "nowait",
 210   "ordered",
 211   "default"
 212 };
 213 \f
 214 /* Init tree.c.  */
 215
 216 void
 217 init_ttree (void)
 218 {
 219   /* Initialize the hash table of types.  */
 220   type_hash_table = htab_create_ggc (TYPE_HASH_INITIAL_SIZE, type_hash_hash,
 221                                      type_hash_eq, 0);
 222
 223   debug_expr_for_decl = htab_create_ggc (512, tree_map_hash,
 224                                          tree_map_eq, 0);
 225
 226   value_expr_for_decl = htab_create_ggc (512, tree_map_hash,
 227                                          tree_map_eq, 0);
 228   init_priority_for_decl = htab_create_ggc (512, tree_int_map_hash,
 229                                             tree_int_map_eq, 0);
 230   restrict_base_for_decl = htab_create_ggc (256, tree_map_hash,
 231                                             tree_map_eq, 0);
 232
 233   int_cst_hash_table = htab_create_ggc (1024, int_cst_hash_hash,
 234                                         int_cst_hash_eq, NULL);
 235
 236   int_cst_node = make_node (INTEGER_CST);
 237
 238   tree_contains_struct[FUNCTION_DECL][TS_DECL_NON_COMMON] = 1;
 239   tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_NON_COMMON] = 1;
 240   tree_contains_struct[TYPE_DECL][TS_DECL_NON_COMMON] = 1;
 241
 242
 243   tree_contains_struct[CONST_DECL][TS_DECL_COMMON] = 1;
 244   tree_contains_struct[VAR_DECL][TS_DECL_COMMON] = 1;
 245   tree_contains_struct[PARM_DECL][TS_DECL_COMMON] = 1;
 246   tree_contains_struct[RESULT_DECL][TS_DECL_COMMON] = 1;
 247   tree_contains_struct[FUNCTION_DECL][TS_DECL_COMMON] = 1;
 248   tree_contains_struct[TYPE_DECL][TS_DECL_COMMON] = 1;
 249   tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_COMMON] = 1;
 250   tree_contains_struct[LABEL_DECL][TS_DECL_COMMON] = 1;
 251   tree_contains_struct[FIELD_DECL][TS_DECL_COMMON] = 1;
 252
 253
 254   tree_contains_struct[CONST_DECL][TS_DECL_WRTL] = 1;
 255   tree_contains_struct[VAR_DECL][TS_DECL_WRTL] = 1;
 256   tree_contains_struct[PARM_DECL][TS_DECL_WRTL] = 1;
 257   tree_contains_struct[RESULT_DECL][TS_DECL_WRTL] = 1;
 258   tree_contains_struct[FUNCTION_DECL][TS_DECL_WRTL] = 1;
 259   tree_contains_struct[LABEL_DECL][TS_DECL_WRTL] = 1;
 260
 261   tree_contains_struct[CONST_DECL][TS_DECL_MINIMAL] = 1;
 262   tree_contains_struct[VAR_DECL][TS_DECL_MINIMAL] = 1;
 263   tree_contains_struct[PARM_DECL][TS_DECL_MINIMAL] = 1;
 264   tree_contains_struct[RESULT_DECL][TS_DECL_MINIMAL] = 1;
 265   tree_contains_struct[FUNCTION_DECL][TS_DECL_MINIMAL] = 1;
 266   tree_contains_struct[TYPE_DECL][TS_DECL_MINIMAL] = 1;
 267   tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_MINIMAL] = 1;
 268   tree_contains_struct[LABEL_DECL][TS_DECL_MINIMAL] = 1;
 269   tree_contains_struct[FIELD_DECL][TS_DECL_MINIMAL] = 1;
 270   tree_contains_struct[STRUCT_FIELD_TAG][TS_DECL_MINIMAL] = 1;
 271   tree_contains_struct[NAME_MEMORY_TAG][TS_DECL_MINIMAL] = 1;
 272   tree_contains_struct[SYMBOL_MEMORY_TAG][TS_DECL_MINIMAL] = 1;
 273
 274   tree_contains_struct[STRUCT_FIELD_TAG][TS_MEMORY_TAG] = 1;
 275   tree_contains_struct[NAME_MEMORY_TAG][TS_MEMORY_TAG] = 1;
 276   tree_contains_struct[SYMBOL_MEMORY_TAG][TS_MEMORY_TAG] = 1;
 277
 278   tree_contains_struct[STRUCT_FIELD_TAG][TS_STRUCT_FIELD_TAG] = 1;
 279
 280   tree_contains_struct[VAR_DECL][TS_DECL_WITH_VIS] = 1;
 281   tree_contains_struct[FUNCTION_DECL][TS_DECL_WITH_VIS] = 1;
 282   tree_contains_struct[TYPE_DECL][TS_DECL_WITH_VIS] = 1;
 283   tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_WITH_VIS] = 1;
 284
 285   tree_contains_struct[VAR_DECL][TS_VAR_DECL] = 1;
 286   tree_contains_struct[FIELD_DECL][TS_FIELD_DECL] = 1;
 287   tree_contains_struct[PARM_DECL][TS_PARM_DECL] = 1;
 288   tree_contains_struct[LABEL_DECL][TS_LABEL_DECL] = 1;
 289   tree_contains_struct[RESULT_DECL][TS_RESULT_DECL] = 1;
 290   tree_contains_struct[CONST_DECL][TS_CONST_DECL] = 1;
 291   tree_contains_struct[TYPE_DECL][TS_TYPE_DECL] = 1;
 292   tree_contains_struct[FUNCTION_DECL][TS_FUNCTION_DECL] = 1;
 293
 294   lang_hooks.init_ts ();
 295 }
 296
 297 \f
 298 /* The name of the object as the assembler will see it (but before any
 299    translations made by ASM_OUTPUT_LABELREF).  Often this is the same
 300    as DECL_NAME.  It is an IDENTIFIER_NODE.  */
 301 tree
 302 decl_assembler_name (tree decl)
 303 {
 304   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 305     lang_hooks.set_decl_assembler_name (decl);
 306   return DECL_WITH_VIS_CHECK (decl)->decl_with_vis.assembler_name;
 307 }
 308
 309 /* Compute the number of bytes occupied by a tree with code CODE.
 310    This function cannot be used for TREE_VEC, PHI_NODE, or STRING_CST
 311    codes, which are of variable length.  */
 312 size_t
 313 tree_code_size (enum tree_code code)
 314 {
 315   switch (TREE_CODE_CLASS (code))
 316     {
 317     case tcc_declaration:  /* A decl node */
 318       {
 319         switch (code)
 320           {
 321           case FIELD_DECL:
 322             return sizeof (struct tree_field_decl);
 323           case PARM_DECL:
 324             return sizeof (struct tree_parm_decl);
 325           case VAR_DECL:
 326             return sizeof (struct tree_var_decl);
 327           case LABEL_DECL:
 328             return sizeof (struct tree_label_decl);
 329           case RESULT_DECL:
 330             return sizeof (struct tree_result_decl);
 331           case CONST_DECL:
 332             return sizeof (struct tree_const_decl);
 333           case TYPE_DECL:
 334             return sizeof (struct tree_type_decl);
 335           case FUNCTION_DECL:
 336             return sizeof (struct tree_function_decl);
 337           case NAME_MEMORY_TAG:
 338           case SYMBOL_MEMORY_TAG:
 339             return sizeof (struct tree_memory_tag);
 340           case STRUCT_FIELD_TAG:
 341             return sizeof (struct tree_struct_field_tag);
 342           default:
 343             return sizeof (struct tree_decl_non_common);
 344           }
 345       }
 346
 347     case tcc_type:  /* a type node */
 348       return sizeof (struct tree_type);
 349
 350     case tcc_reference:   /* a reference */
 351     case tcc_expression:  /* an expression */
 352     case tcc_statement:   /* an expression with side effects */
 353     case tcc_comparison:  /* a comparison expression */
 354     case tcc_unary:       /* a unary arithmetic expression */
 355     case tcc_binary:      /* a binary arithmetic expression */
 356       return (sizeof (struct tree_exp)
 357               + (TREE_CODE_LENGTH (code) - 1) * sizeof (char *));
 358
 359     case tcc_constant:  /* a constant */
 360       switch (code)
 361         {
 362         case INTEGER_CST:       return sizeof (struct tree_int_cst);
 363         case REAL_CST:          return sizeof (struct tree_real_cst);
 364         case COMPLEX_CST:       return sizeof (struct tree_complex);
 365         case VECTOR_CST:        return sizeof (struct tree_vector);
 366         case STRING_CST:        gcc_unreachable ();
 367         default:
 368           return lang_hooks.tree_size (code);
 369         }
 370
 371     case tcc_exceptional:  /* something random, like an identifier.  */
 372       switch (code)
 373         {
 374         case IDENTIFIER_NODE:   return lang_hooks.identifier_size;
 375         case TREE_LIST:         return sizeof (struct tree_list);
 376
 377         case ERROR_MARK:
 378         case PLACEHOLDER_EXPR:  return sizeof (struct tree_common);
 379
 380         case TREE_VEC:
 381         case OMP_CLAUSE:
 382         case PHI_NODE:          gcc_unreachable ();
 383
 384         case SSA_NAME:          return sizeof (struct tree_ssa_name);
 385
 386         case STATEMENT_LIST:    return sizeof (struct tree_statement_list);
 387         case BLOCK:             return sizeof (struct tree_block);
 388         case VALUE_HANDLE:      return sizeof (struct tree_value_handle);
 389         case CONSTRUCTOR:       return sizeof (struct tree_constructor);
 390
 391         default:
 392           return lang_hooks.tree_size (code);
 393         }
 394
 395     default:
 396       gcc_unreachable ();
 397     }
 398 }
 399
 400 /* Compute the number of bytes occupied by NODE.  This routine only
 401    looks at TREE_CODE, except for PHI_NODE and TREE_VEC nodes.  */
 402 size_t
 403 tree_size (tree node)
 404 {
 405   enum tree_code code = TREE_CODE (node);
 406   switch (code)
 407     {
 408     case PHI_NODE:
 409       return (sizeof (struct tree_phi_node)
 410               + (PHI_ARG_CAPACITY (node) - 1) * sizeof (struct phi_arg_d));
 411
 412     case TREE_BINFO:
 413       return (offsetof (struct tree_binfo, base_binfos)
 414               + VEC_embedded_size (tree, BINFO_N_BASE_BINFOS (node)));
 415
 416     case TREE_VEC:
 417       return (sizeof (struct tree_vec)
 418               + (TREE_VEC_LENGTH (node) - 1) * sizeof(char *));
 419
 420     case STRING_CST:
 421       return TREE_STRING_LENGTH (node) + offsetof (struct tree_string, str) + 1;
 422
 423     case OMP_CLAUSE:
 424       return (sizeof (struct tree_omp_clause)
 425               + (omp_clause_num_ops[OMP_CLAUSE_CODE (node)] - 1)
 426                 * sizeof (tree));
 427
 428     default:
 429       return tree_code_size (code);
 430     }
 431 }
 432
 433 /* Return a newly allocated node of code CODE.  For decl and type
 434    nodes, some other fields are initialized.  The rest of the node is
 435    initialized to zero.  This function cannot be used for PHI_NODE,
 436    TREE_VEC or OMP_CLAUSE nodes, which is enforced by asserts in
 437    tree_code_size.
 438
 439    Achoo!  I got a code in the node.  */
 440
 441 tree
 442 make_node_stat (enum tree_code code MEM_STAT_DECL)
 443 {
 444   tree t;
 445   enum tree_code_class type = TREE_CODE_CLASS (code);
 446   size_t length = tree_code_size (code);
 447 #ifdef GATHER_STATISTICS
 448   tree_node_kind kind;
 449
 450   switch (type)
 451     {
 452     case tcc_declaration:  /* A decl node */
 453       kind = d_kind;
 454       break;
 455
 456     case tcc_type:  /* a type node */
 457       kind = t_kind;
 458       break;
 459
 460     case tcc_statement:  /* an expression with side effects */
 461       kind = s_kind;
 462       break;
 463
 464     case tcc_reference:  /* a reference */
 465       kind = r_kind;
 466       break;
 467
 468     case tcc_expression:  /* an expression */
 469     case tcc_comparison:  /* a comparison expression */
 470     case tcc_unary:  /* a unary arithmetic expression */
 471     case tcc_binary:  /* a binary arithmetic expression */
 472       kind = e_kind;
 473       break;
 474
 475     case tcc_constant:  /* a constant */
 476       kind = c_kind;
 477       break;
 478
 479     case tcc_exceptional:  /* something random, like an identifier.  */
 480       switch (code)
 481         {
 482         case IDENTIFIER_NODE:
 483           kind = id_kind;
 484           break;
 485
 486         case TREE_VEC:
 487           kind = vec_kind;
 488           break;
 489
 490         case TREE_BINFO:
 491           kind = binfo_kind;
 492           break;
 493
 494         case PHI_NODE:
 495           kind = phi_kind;
 496           break;
 497
 498         case SSA_NAME:
 499           kind = ssa_name_kind;
 500           break;
 501
 502         case BLOCK:
 503           kind = b_kind;
 504           break;
 505
 506         case CONSTRUCTOR:
 507           kind = constr_kind;
 508           break;
 509
 510         default:
 511           kind = x_kind;
 512           break;
 513         }
 514       break;
 515
 516     default:
 517       gcc_unreachable ();
 518     }
 519
 520   tree_node_counts[(int) kind]++;
 521   tree_node_sizes[(int) kind] += length;
 522 #endif
 523
 524   if (code == IDENTIFIER_NODE)
 525     t = ggc_alloc_zone_pass_stat (length, &tree_id_zone);
 526   else
 527     t = ggc_alloc_zone_pass_stat (length, &tree_zone);
 528
 529   memset (t, 0, length);
 530
 531   TREE_SET_CODE (t, code);
 532
 533   switch (type)
 534     {
 535     case tcc_statement:
 536       TREE_SIDE_EFFECTS (t) = 1;
 537       break;
 538
 539     case tcc_declaration:
 540       if (CODE_CONTAINS_STRUCT (code, TS_DECL_WITH_VIS))
 541         DECL_IN_SYSTEM_HEADER (t) = in_system_header;
 542       if (CODE_CONTAINS_STRUCT (code, TS_DECL_COMMON))
 543         {
 544           if (code != FUNCTION_DECL)
 545             DECL_ALIGN (t) = 1;
 546           DECL_USER_ALIGN (t) = 0;
 547           /* We have not yet computed the alias set for this declaration.  */
 548           DECL_POINTER_ALIAS_SET (t) = -1;
 549         }
 550       DECL_SOURCE_LOCATION (t) = input_location;
 551       DECL_UID (t) = next_decl_uid++;
 552
 553       break;
 554
 555     case tcc_type:
 556       TYPE_UID (t) = next_type_uid++;
 557       TYPE_ALIGN (t) = BITS_PER_UNIT;
 558       TYPE_USER_ALIGN (t) = 0;
 559       TYPE_MAIN_VARIANT (t) = t;
 560
 561       /* Default to no attributes for type, but let target change that.  */
 562       TYPE_ATTRIBUTES (t) = NULL_TREE;
 563       targetm.set_default_type_attributes (t);
 564
 565       /* We have not yet computed the alias set for this type.  */
 566       TYPE_ALIAS_SET (t) = -1;
 567       break;
 568
 569     case tcc_constant:
 570       TREE_CONSTANT (t) = 1;
 571       TREE_INVARIANT (t) = 1;
 572       break;
 573
 574     case tcc_expression:
 575       switch (code)
 576         {
 577         case INIT_EXPR:
 578         case MODIFY_EXPR:
 579         case VA_ARG_EXPR:
 580         case PREDECREMENT_EXPR:
 581         case PREINCREMENT_EXPR:
 582         case POSTDECREMENT_EXPR:
 583         case POSTINCREMENT_EXPR:
 584           /* All of these have side-effects, no matter what their
 585              operands are.  */
 586           TREE_SIDE_EFFECTS (t) = 1;
 587           break;
 588
 589         default:
 590           break;
 591         }
 592       break;
 593
 594     default:
 595       /* Other classes need no special treatment.  */
 596       break;
 597     }
 598
 599   return t;
 600 }
 601 \f
 602 /* Return a new node with the same contents as NODE except that its
 603    TREE_CHAIN is zero and it has a fresh uid.  */
 604
 605 tree
 606 copy_node_stat (tree node MEM_STAT_DECL)
 607 {
 608   tree t;
 609   enum tree_code code = TREE_CODE (node);
 610   size_t length;
 611
 612   gcc_assert (code != STATEMENT_LIST);
 613
 614   length = tree_size (node);
 615   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
 616   memcpy (t, node, length);
 617
 618   TREE_CHAIN (t) = 0;
 619   TREE_ASM_WRITTEN (t) = 0;
 620   TREE_VISITED (t) = 0;
 621   t->common.ann = 0;
 622
 623   if (TREE_CODE_CLASS (code) == tcc_declaration)
 624     {
 625       DECL_UID (t) = next_decl_uid++;
 626       if ((TREE_CODE (node) == PARM_DECL || TREE_CODE (node) == VAR_DECL)
 627           && DECL_HAS_VALUE_EXPR_P (node))
 628         {
 629           SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (node));
 630           DECL_HAS_VALUE_EXPR_P (t) = 1;
 631         }
 632       if (TREE_CODE (node) == VAR_DECL && DECL_HAS_INIT_PRIORITY_P (node))
 633         {
 634           SET_DECL_INIT_PRIORITY (t, DECL_INIT_PRIORITY (node));
 635           DECL_HAS_INIT_PRIORITY_P (t) = 1;
 636         }
 637       if (TREE_CODE (node) == VAR_DECL && DECL_BASED_ON_RESTRICT_P (node))
 638         {
 639           SET_DECL_RESTRICT_BASE (t, DECL_GET_RESTRICT_BASE (node));
 640           DECL_BASED_ON_RESTRICT_P (t) = 1;
 641         }
 642     }
 643   else if (TREE_CODE_CLASS (code) == tcc_type)
 644     {
 645       TYPE_UID (t) = next_type_uid++;
 646       /* The following is so that the debug code for
 647          the copy is different from the original type.
 648          The two statements usually duplicate each other
 649          (because they clear fields of the same union),
 650          but the optimizer should catch that.  */
 651       TYPE_SYMTAB_POINTER (t) = 0;
 652       TYPE_SYMTAB_ADDRESS (t) = 0;
 653
 654       /* Do not copy the values cache.  */
 655       if (TYPE_CACHED_VALUES_P(t))
 656         {
 657           TYPE_CACHED_VALUES_P (t) = 0;
 658           TYPE_CACHED_VALUES (t) = NULL_TREE;
 659         }
 660     }
 661
 662   return t;
 663 }
 664
 665 /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
 666    For example, this can copy a list made of TREE_LIST nodes.  */
 667
 668 tree
 669 copy_list (tree list)
 670 {
 671   tree head;
 672   tree prev, next;
 673
 674   if (list == 0)
 675     return 0;
 676
 677   head = prev = copy_node (list);
 678   next = TREE_CHAIN (list);
 679   while (next)
 680     {
 681       TREE_CHAIN (prev) = copy_node (next);
 682       prev = TREE_CHAIN (prev);
 683       next = TREE_CHAIN (next);
 684     }
 685   return head;
 686 }
 687
 688 \f
 689 /* Create an INT_CST node with a LOW value sign extended.  */
 690
 691 tree
 692 build_int_cst (tree type, HOST_WIDE_INT low)
 693 {
 694   return build_int_cst_wide (type, low, low < 0 ? -1 : 0);
 695 }
 696
 697 /* Create an INT_CST node with a LOW value zero extended.  */
 698
 699 tree
 700 build_int_cstu (tree type, unsigned HOST_WIDE_INT low)
 701 {
 702   return build_int_cst_wide (type, low, 0);
 703 }
 704
 705 /* Create an INT_CST node with a LOW value in TYPE.  The value is sign extended
 706    if it is negative.  This function is similar to build_int_cst, but
 707    the extra bits outside of the type precision are cleared.  Constants
 708    with these extra bits may confuse the fold so that it detects overflows
 709    even in cases when they do not occur, and in general should be avoided.
 710    We cannot however make this a default behavior of build_int_cst without
 711    more intrusive changes, since there are parts of gcc that rely on the extra
 712    precision of the integer constants.  */
 713
 714 tree
 715 build_int_cst_type (tree type, HOST_WIDE_INT low)
 716 {
 717   unsigned HOST_WIDE_INT val = (unsigned HOST_WIDE_INT) low;
 718   unsigned HOST_WIDE_INT hi, mask;
 719   unsigned bits;
 720   bool signed_p;
 721   bool negative;
 722
 723   if (!type)
 724     type = integer_type_node;
 725
 726   bits = TYPE_PRECISION (type);
 727   signed_p = !TYPE_UNSIGNED (type);
 728
 729   if (bits >= HOST_BITS_PER_WIDE_INT)
 730     negative = (low < 0);
 731   else
 732     {
 733       /* If the sign bit is inside precision of LOW, use it to determine
 734          the sign of the constant.  */
 735       negative = ((val >> (bits - 1)) & 1) != 0;
 736
 737       /* Mask out the bits outside of the precision of the constant.  */
 738       mask = (((unsigned HOST_WIDE_INT) 2) << (bits - 1)) - 1;
 739
 740       if (signed_p && negative)
 741         val |= ~mask;
 742       else
 743         val &= mask;
 744     }
 745
 746   /* Determine the high bits.  */
 747   hi = (negative ? ~(unsigned HOST_WIDE_INT) 0 : 0);
 748
 749   /* For unsigned type we need to mask out the bits outside of the type
 750      precision.  */
 751   if (!signed_p)
 752     {
 753       if (bits <= HOST_BITS_PER_WIDE_INT)
 754         hi = 0;
 755       else
 756         {
 757           bits -= HOST_BITS_PER_WIDE_INT;
 758           mask = (((unsigned HOST_WIDE_INT) 2) << (bits - 1)) - 1;
 759           hi &= mask;
 760         }
 761     }
 762
 763   return build_int_cst_wide (type, val, hi);
 764 }
 765
 766 /* These are the hash table functions for the hash table of INTEGER_CST
 767    nodes of a sizetype.  */
 768
 769 /* Return the hash code code X, an INTEGER_CST.  */
 770
 771 static hashval_t
 772 int_cst_hash_hash (const void *x)
 773 {
 774   tree t = (tree) x;
 775
 776   return (TREE_INT_CST_HIGH (t) ^ TREE_INT_CST_LOW (t)
 777           ^ htab_hash_pointer (TREE_TYPE (t)));
 778 }
 779
 780 /* Return nonzero if the value represented by *X (an INTEGER_CST tree node)
 781    is the same as that given by *Y, which is the same.  */
 782
 783 static int
 784 int_cst_hash_eq (const void *x, const void *y)
 785 {
 786   tree xt = (tree) x;
 787   tree yt = (tree) y;
 788
 789   return (TREE_TYPE (xt) == TREE_TYPE (yt)
 790           && TREE_INT_CST_HIGH (xt) == TREE_INT_CST_HIGH (yt)
 791           && TREE_INT_CST_LOW (xt) == TREE_INT_CST_LOW (yt));
 792 }
 793
 794 /* Create an INT_CST node of TYPE and value HI:LOW.  If TYPE is NULL,
 795    integer_type_node is used.  The returned node is always shared.
 796    For small integers we use a per-type vector cache, for larger ones
 797    we use a single hash table.  */
 798
 799 tree
 800 build_int_cst_wide (tree type, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
 801 {
 802   tree t;
 803   int ix = -1;
 804   int limit = 0;
 805
 806   if (!type)
 807     type = integer_type_node;
 808
 809   switch (TREE_CODE (type))
 810     {
 811     case POINTER_TYPE:
 812     case REFERENCE_TYPE:
 813       /* Cache NULL pointer.  */
 814       if (!hi && !low)
 815         {
 816           limit = 1;
 817           ix = 0;
 818         }
 819       break;
 820
 821     case BOOLEAN_TYPE:
 822       /* Cache false or true.  */
 823       limit = 2;
 824       if (!hi && low < 2)
 825         ix = low;
 826       break;
 827
 828     case INTEGER_TYPE:
 829     case OFFSET_TYPE:
 830       if (TYPE_UNSIGNED (type))
 831         {
 832           /* Cache 0..N */
 833           limit = INTEGER_SHARE_LIMIT;
 834           if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
 835             ix = low;
 836         }
 837       else
 838         {
 839           /* Cache -1..N */
 840           limit = INTEGER_SHARE_LIMIT + 1;
 841           if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
 842             ix = low + 1;
 843           else if (hi == -1 && low == -(unsigned HOST_WIDE_INT)1)
 844             ix = 0;
 845         }
 846       break;
 847     default:
 848       break;
 849     }
 850
 851   if (ix >= 0)
 852     {
 853       /* Look for it in the type's vector of small shared ints.  */
 854       if (!TYPE_CACHED_VALUES_P (type))
 855         {
 856           TYPE_CACHED_VALUES_P (type) = 1;
 857           TYPE_CACHED_VALUES (type) = make_tree_vec (limit);
 858         }
 859
 860       t = TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix);
 861       if (t)
 862         {
 863           /* Make sure no one is clobbering the shared constant.  */
 864           gcc_assert (TREE_TYPE (t) == type);
 865           gcc_assert (TREE_INT_CST_LOW (t) == low);
 866           gcc_assert (TREE_INT_CST_HIGH (t) == hi);
 867         }
 868       else
 869         {
 870           /* Create a new shared int.  */
 871           t = make_node (INTEGER_CST);
 872
 873           TREE_INT_CST_LOW (t) = low;
 874           TREE_INT_CST_HIGH (t) = hi;
 875           TREE_TYPE (t) = type;
 876
 877           TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix) = t;
 878         }
 879     }
 880   else
 881     {
 882       /* Use the cache of larger shared ints.  */
 883       void **slot;
 884
 885       TREE_INT_CST_LOW (int_cst_node) = low;
 886       TREE_INT_CST_HIGH (int_cst_node) = hi;
 887       TREE_TYPE (int_cst_node) = type;
 888
 889       slot = htab_find_slot (int_cst_hash_table, int_cst_node, INSERT);
 890       t = *slot;
 891       if (!t)
 892         {
 893           /* Insert this one into the hash table.  */
 894           t = int_cst_node;
 895           *slot = t;
 896           /* Make a new node for next time round.  */
 897           int_cst_node = make_node (INTEGER_CST);
 898         }
 899     }
 900
 901   return t;
 902 }
 903
 904 /* Builds an integer constant in TYPE such that lowest BITS bits are ones
 905    and the rest are zeros.  */
 906
 907 tree
 908 build_low_bits_mask (tree type, unsigned bits)
 909 {
 910   unsigned HOST_WIDE_INT low;
 911   HOST_WIDE_INT high;
 912   unsigned HOST_WIDE_INT all_ones = ~(unsigned HOST_WIDE_INT) 0;
 913
 914   gcc_assert (bits <= TYPE_PRECISION (type));
 915
 916   if (bits == TYPE_PRECISION (type)
 917       && !TYPE_UNSIGNED (type))
 918     {
 919       /* Sign extended all-ones mask.  */
 920       low = all_ones;
 921       high = -1;
 922     }
 923   else if (bits <= HOST_BITS_PER_WIDE_INT)
 924     {
 925       low = all_ones >> (HOST_BITS_PER_WIDE_INT - bits);
 926       high = 0;
 927     }
 928   else
 929     {
 930       bits -= HOST_BITS_PER_WIDE_INT;
 931       low = all_ones;
 932       high = all_ones >> (HOST_BITS_PER_WIDE_INT - bits);
 933     }
 934
 935   return build_int_cst_wide (type, low, high);
 936 }
 937
 938 /* Checks that X is integer constant that can be expressed in (unsigned)
 939    HOST_WIDE_INT without loss of precision.  */
 940
 941 bool
 942 cst_and_fits_in_hwi (tree x)
 943 {
 944   if (TREE_CODE (x) != INTEGER_CST)
 945     return false;
 946
 947   if (TYPE_PRECISION (TREE_TYPE (x)) > HOST_BITS_PER_WIDE_INT)
 948     return false;
 949
 950   return (TREE_INT_CST_HIGH (x) == 0
 951           || TREE_INT_CST_HIGH (x) == -1);
 952 }
 953
 954 /* Return a new VECTOR_CST node whose type is TYPE and whose values
 955    are in a list pointed to by VALS.  */
 956
 957 tree
 958 build_vector (tree type, tree vals)
 959 {
 960   tree v = make_node (VECTOR_CST);
 961   int over1 = 0, over2 = 0;
 962   tree link;
 963
 964   TREE_VECTOR_CST_ELTS (v) = vals;
 965   TREE_TYPE (v) = type;
 966
 967   /* Iterate through elements and check for overflow.  */
 968   for (link = vals; link; link = TREE_CHAIN (link))
 969     {
 970       tree value = TREE_VALUE (link);
 971
 972       over1 |= TREE_OVERFLOW (value);
 973       over2 |= TREE_CONSTANT_OVERFLOW (value);
 974     }
 975
 976   TREE_OVERFLOW (v) = over1;
 977   TREE_CONSTANT_OVERFLOW (v) = over2;
 978
 979   return v;
 980 }
 981
 982 /* Return a new VECTOR_CST node whose type is TYPE and whose values
 983    are extracted from V, a vector of CONSTRUCTOR_ELT.  */
 984
 985 tree
 986 build_vector_from_ctor (tree type, VEC(constructor_elt,gc) *v)
 987 {
 988   tree list = NULL_TREE;
 989   unsigned HOST_WIDE_INT idx;
 990   tree value;
 991
 992   FOR_EACH_CONSTRUCTOR_VALUE (v, idx, value)
 993     list = tree_cons (NULL_TREE, value, list);
 994   return build_vector (type, nreverse (list));
 995 }
 996
 997 /* Return a new CONSTRUCTOR node whose type is TYPE and whose values
 998    are in the VEC pointed to by VALS.  */
 999 tree
1000 build_constructor (tree type, VEC(constructor_elt,gc) *vals)
1001 {
1002   tree c = make_node (CONSTRUCTOR);
1003   TREE_TYPE (c) = type;
1004   CONSTRUCTOR_ELTS (c) = vals;
1005   return c;
1006 }
1007
1008 /* Build a CONSTRUCTOR node made of a single initializer, with the specified
1009    INDEX and VALUE.  */
1010 tree
1011 build_constructor_single (tree type, tree index, tree value)
1012 {
1013   VEC(constructor_elt,gc) *v;
1014   constructor_elt *elt;
1015   tree t;
1016
1017   v = VEC_alloc (constructor_elt, gc, 1);
1018   elt = VEC_quick_push (constructor_elt, v, NULL);
1019   elt->index = index;
1020   elt->value = value;
1021
1022   t = build_constructor (type, v);
1023   TREE_CONSTANT (t) = TREE_CONSTANT (value);
1024   return t;
1025 }
1026
1027
1028 /* Return a new CONSTRUCTOR node whose type is TYPE and whose values
1029    are in a list pointed to by VALS.  */
1030 tree
1031 build_constructor_from_list (tree type, tree vals)
1032 {
1033   tree t, val;
1034   VEC(constructor_elt,gc) *v = NULL;
1035   bool constant_p = true;
1036
1037   if (vals)
1038     {
1039       v = VEC_alloc (constructor_elt, gc, list_length (vals));
1040       for (t = vals; t; t = TREE_CHAIN (t))
1041         {
1042           constructor_elt *elt = VEC_quick_push (constructor_elt, v, NULL);
1043           val = TREE_VALUE (t);
1044           elt->index = TREE_PURPOSE (t);
1045           elt->value = val;
1046           if (!TREE_CONSTANT (val))
1047             constant_p = false;
1048         }
1049     }
1050
1051   t = build_constructor (type, v);
1052   TREE_CONSTANT (t) = constant_p;
1053   return t;
1054 }
1055
1056
1057 /* Return a new REAL_CST node whose type is TYPE and value is D.  */
1058
1059 tree
1060 build_real (tree type, REAL_VALUE_TYPE d)
1061 {
1062   tree v;
1063   REAL_VALUE_TYPE *dp;
1064   int overflow = 0;
1065
1066   /* ??? Used to check for overflow here via CHECK_FLOAT_TYPE.
1067      Consider doing it via real_convert now.  */
1068
1069   v = make_node (REAL_CST);
1070   dp = ggc_alloc (sizeof (REAL_VALUE_TYPE));
1071   memcpy (dp, &d, sizeof (REAL_VALUE_TYPE));
1072
1073   TREE_TYPE (v) = type;
1074   TREE_REAL_CST_PTR (v) = dp;
1075   TREE_OVERFLOW (v) = TREE_CONSTANT_OVERFLOW (v) = overflow;
1076   return v;
1077 }
1078
1079 /* Return a new REAL_CST node whose type is TYPE
1080    and whose value is the integer value of the INTEGER_CST node I.  */
1081
1082 REAL_VALUE_TYPE
1083 real_value_from_int_cst (tree type, tree i)
1084 {
1085   REAL_VALUE_TYPE d;
1086
1087   /* Clear all bits of the real value type so that we can later do
1088      bitwise comparisons to see if two values are the same.  */
1089   memset (&d, 0, sizeof d);
1090
1091   real_from_integer (&d, type ? TYPE_MODE (type) : VOIDmode,
1092                      TREE_INT_CST_LOW (i), TREE_INT_CST_HIGH (i),
1093                      TYPE_UNSIGNED (TREE_TYPE (i)));
1094   return d;
1095 }
1096
1097 /* Given a tree representing an integer constant I, return a tree
1098    representing the same value as a floating-point constant of type TYPE.  */
1099
1100 tree
1101 build_real_from_int_cst (tree type, tree i)
1102 {
1103   tree v;
1104   int overflow = TREE_OVERFLOW (i);
1105
1106   v = build_real (type, real_value_from_int_cst (type, i));
1107
1108   TREE_OVERFLOW (v) |= overflow;
1109   TREE_CONSTANT_OVERFLOW (v) |= overflow;
1110   return v;
1111 }
1112
1113 /* Return a newly constructed STRING_CST node whose value is
1114    the LEN characters at STR.
1115    The TREE_TYPE is not initialized.  */
1116
1117 tree
1118 build_string (int len, const char *str)
1119 {
1120   tree s;
1121   size_t length;
1122
1123   /* Do not waste bytes provided by padding of struct tree_string.  */
1124   length = len + offsetof (struct tree_string, str) + 1;
1125
1126 #ifdef GATHER_STATISTICS
1127   tree_node_counts[(int) c_kind]++;
1128   tree_node_sizes[(int) c_kind] += length;
1129 #endif
1130
1131   s = ggc_alloc_tree (length);
1132
1133   memset (s, 0, sizeof (struct tree_common));
1134   TREE_SET_CODE (s, STRING_CST);
1135   TREE_CONSTANT (s) = 1;
1136   TREE_INVARIANT (s) = 1;
1137   TREE_STRING_LENGTH (s) = len;
1138   memcpy ((char *) TREE_STRING_POINTER (s), str, len);
1139   ((char *) TREE_STRING_POINTER (s))[len] = '\0';
1140
1141   return s;
1142 }
1143
1144 /* Return a newly constructed COMPLEX_CST node whose value is
1145    specified by the real and imaginary parts REAL and IMAG.
1146    Both REAL and IMAG should be constant nodes.  TYPE, if specified,
1147    will be the type of the COMPLEX_CST; otherwise a new type will be made.  */
1148
1149 tree
1150 build_complex (tree type, tree real, tree imag)
1151 {
1152   tree t = make_node (COMPLEX_CST);
1153
1154   TREE_REALPART (t) = real;
1155   TREE_IMAGPART (t) = imag;
1156   TREE_TYPE (t) = type ? type : build_complex_type (TREE_TYPE (real));
1157   TREE_OVERFLOW (t) = TREE_OVERFLOW (real) | TREE_OVERFLOW (imag);
1158   TREE_CONSTANT_OVERFLOW (t)
1159     = TREE_CONSTANT_OVERFLOW (real) | TREE_CONSTANT_OVERFLOW (imag);
1160   return t;
1161 }
1162
1163 /* Return a constant of arithmetic type TYPE which is the
1164    multiplicative identity of the set TYPE.  */
1165
1166 tree
1167 build_one_cst (tree type)
1168 {
1169   switch (TREE_CODE (type))
1170     {
1171     case INTEGER_TYPE: case ENUMERAL_TYPE: case BOOLEAN_TYPE:
1172     case POINTER_TYPE: case REFERENCE_TYPE:
1173     case OFFSET_TYPE:
1174       return build_int_cst (type, 1);
1175
1176     case REAL_TYPE:
1177       return build_real (type, dconst1);
1178
1179     case VECTOR_TYPE:
1180       {
1181         tree scalar, cst;
1182         int i;
1183
1184         scalar = build_one_cst (TREE_TYPE (type));
1185
1186         /* Create 'vect_cst_ = {cst,cst,...,cst}'  */
1187         cst = NULL_TREE;
1188         for (i = TYPE_VECTOR_SUBPARTS (type); --i >= 0; )
1189           cst = tree_cons (NULL_TREE, scalar, cst);
1190
1191         return build_vector (type, cst);
1192       }
1193
1194     case COMPLEX_TYPE:
1195       return build_complex (type,
1196                             build_one_cst (TREE_TYPE (type)),
1197                             fold_convert (TREE_TYPE (type), integer_zero_node));
1198
1199     default:
1200       gcc_unreachable ();
1201     }
1202 }
1203
1204 /* Build a BINFO with LEN language slots.  */
1205
1206 tree
1207 make_tree_binfo_stat (unsigned base_binfos MEM_STAT_DECL)
1208 {
1209   tree t;
1210   size_t length = (offsetof (struct tree_binfo, base_binfos)
1211                    + VEC_embedded_size (tree, base_binfos));
1212
1213 #ifdef GATHER_STATISTICS
1214   tree_node_counts[(int) binfo_kind]++;
1215   tree_node_sizes[(int) binfo_kind] += length;
1216 #endif
1217
1218   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
1219
1220   memset (t, 0, offsetof (struct tree_binfo, base_binfos));
1221
1222   TREE_SET_CODE (t, TREE_BINFO);
1223
1224   VEC_embedded_init (tree, BINFO_BASE_BINFOS (t), base_binfos);
1225
1226   return t;
1227 }
1228
1229
1230 /* Build a newly constructed TREE_VEC node of length LEN.  */
1231
1232 tree
1233 make_tree_vec_stat (int len MEM_STAT_DECL)
1234 {
1235   tree t;
1236   int length = (len - 1) * sizeof (tree) + sizeof (struct tree_vec);
1237
1238 #ifdef GATHER_STATISTICS
1239   tree_node_counts[(int) vec_kind]++;
1240   tree_node_sizes[(int) vec_kind] += length;
1241 #endif
1242
1243   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
1244
1245   memset (t, 0, length);
1246
1247   TREE_SET_CODE (t, TREE_VEC);
1248   TREE_VEC_LENGTH (t) = len;
1249
1250   return t;
1251 }
1252 \f
1253 /* Return 1 if EXPR is the integer constant zero or a complex constant
1254    of zero.  */
1255
1256 int
1257 integer_zerop (tree expr)
1258 {
1259   STRIP_NOPS (expr);
1260
1261   return ((TREE_CODE (expr) == INTEGER_CST
1262            && TREE_INT_CST_LOW (expr) == 0
1263            && TREE_INT_CST_HIGH (expr) == 0)
1264           || (TREE_CODE (expr) == COMPLEX_CST
1265               && integer_zerop (TREE_REALPART (expr))
1266               && integer_zerop (TREE_IMAGPART (expr))));
1267 }
1268
1269 /* Return 1 if EXPR is the integer constant one or the corresponding
1270    complex constant.  */
1271
1272 int
1273 integer_onep (tree expr)
1274 {
1275   STRIP_NOPS (expr);
1276
1277   return ((TREE_CODE (expr) == INTEGER_CST
1278            && TREE_INT_CST_LOW (expr) == 1
1279            && TREE_INT_CST_HIGH (expr) == 0)
1280           || (TREE_CODE (expr) == COMPLEX_CST
1281               && integer_onep (TREE_REALPART (expr))
1282               && integer_zerop (TREE_IMAGPART (expr))));
1283 }
1284
1285 /* Return 1 if EXPR is an integer containing all 1's in as much precision as
1286    it contains.  Likewise for the corresponding complex constant.  */
1287
1288 int
1289 integer_all_onesp (tree expr)
1290 {
1291   int prec;
1292   int uns;
1293
1294   STRIP_NOPS (expr);
1295
1296   if (TREE_CODE (expr) == COMPLEX_CST
1297       && integer_all_onesp (TREE_REALPART (expr))
1298       && integer_zerop (TREE_IMAGPART (expr)))
1299     return 1;
1300
1301   else if (TREE_CODE (expr) != INTEGER_CST)
1302     return 0;
1303
1304   uns = TYPE_UNSIGNED (TREE_TYPE (expr));
1305   if (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
1306       && TREE_INT_CST_HIGH (expr) == -1)
1307     return 1;
1308   if (!uns)
1309     return 0;
1310
1311   /* Note that using TYPE_PRECISION here is wrong.  We care about the
1312      actual bits, not the (arbitrary) range of the type.  */
1313   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (expr)));
1314   if (prec >= HOST_BITS_PER_WIDE_INT)
1315     {
1316       HOST_WIDE_INT high_value;
1317       int shift_amount;
1318
1319       shift_amount = prec - HOST_BITS_PER_WIDE_INT;
1320
1321       /* Can not handle precisions greater than twice the host int size.  */
1322       gcc_assert (shift_amount <= HOST_BITS_PER_WIDE_INT);
1323       if (shift_amount == HOST_BITS_PER_WIDE_INT)
1324         /* Shifting by the host word size is undefined according to the ANSI
1325            standard, so we must handle this as a special case.  */
1326         high_value = -1;
1327       else
1328         high_value = ((HOST_WIDE_INT) 1 << shift_amount) - 1;
1329
1330       return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
1331               && TREE_INT_CST_HIGH (expr) == high_value);
1332     }
1333   else
1334     return TREE_INT_CST_LOW (expr) == ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
1335 }
1336
1337 /* Return 1 if EXPR is an integer constant that is a power of 2 (i.e., has only
1338    one bit on).  */
1339
1340 int
1341 integer_pow2p (tree expr)
1342 {
1343   int prec;
1344   HOST_WIDE_INT high, low;
1345
1346   STRIP_NOPS (expr);
1347
1348   if (TREE_CODE (expr) == COMPLEX_CST
1349       && integer_pow2p (TREE_REALPART (expr))
1350       && integer_zerop (TREE_IMAGPART (expr)))
1351     return 1;
1352
1353   if (TREE_CODE (expr) != INTEGER_CST)
1354     return 0;
1355
1356   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1357           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1358   high = TREE_INT_CST_HIGH (expr);
1359   low = TREE_INT_CST_LOW (expr);
1360
1361   /* First clear all bits that are beyond the type's precision in case
1362      we've been sign extended.  */
1363
1364   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
1365     ;
1366   else if (prec > HOST_BITS_PER_WIDE_INT)
1367     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1368   else
1369     {
1370       high = 0;
1371       if (prec < HOST_BITS_PER_WIDE_INT)
1372         low &= ~((HOST_WIDE_INT) (-1) << prec);
1373     }
1374
1375   if (high == 0 && low == 0)
1376     return 0;
1377
1378   return ((high == 0 && (low & (low - 1)) == 0)
1379           || (low == 0 && (high & (high - 1)) == 0));
1380 }
1381
1382 /* Return 1 if EXPR is an integer constant other than zero or a
1383    complex constant other than zero.  */
1384
1385 int
1386 integer_nonzerop (tree expr)
1387 {
1388   STRIP_NOPS (expr);
1389
1390   return ((TREE_CODE (expr) == INTEGER_CST
1391            && (TREE_INT_CST_LOW (expr) != 0
1392                || TREE_INT_CST_HIGH (expr) != 0))
1393           || (TREE_CODE (expr) == COMPLEX_CST
1394               && (integer_nonzerop (TREE_REALPART (expr))
1395                   || integer_nonzerop (TREE_IMAGPART (expr)))));
1396 }
1397
1398 /* Return the power of two represented by a tree node known to be a
1399    power of two.  */
1400
1401 int
1402 tree_log2 (tree expr)
1403 {
1404   int prec;
1405   HOST_WIDE_INT high, low;
1406
1407   STRIP_NOPS (expr);
1408
1409   if (TREE_CODE (expr) == COMPLEX_CST)
1410     return tree_log2 (TREE_REALPART (expr));
1411
1412   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1413           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1414
1415   high = TREE_INT_CST_HIGH (expr);
1416   low = TREE_INT_CST_LOW (expr);
1417
1418   /* First clear all bits that are beyond the type's precision in case
1419      we've been sign extended.  */
1420
1421   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
1422     ;
1423   else if (prec > HOST_BITS_PER_WIDE_INT)
1424     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1425   else
1426     {
1427       high = 0;
1428       if (prec < HOST_BITS_PER_WIDE_INT)
1429         low &= ~((HOST_WIDE_INT) (-1) << prec);
1430     }
1431
1432   return (high != 0 ? HOST_BITS_PER_WIDE_INT + exact_log2 (high)
1433           : exact_log2 (low));
1434 }
1435
1436 /* Similar, but return the largest integer Y such that 2 ** Y is less
1437    than or equal to EXPR.  */
1438
1439 int
1440 tree_floor_log2 (tree expr)
1441 {
1442   int prec;
1443   HOST_WIDE_INT high, low;
1444
1445   STRIP_NOPS (expr);
1446
1447   if (TREE_CODE (expr) == COMPLEX_CST)
1448     return tree_log2 (TREE_REALPART (expr));
1449
1450   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1451           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1452
1453   high = TREE_INT_CST_HIGH (expr);
1454   low = TREE_INT_CST_LOW (expr);
1455
1456   /* First clear all bits that are beyond the type's precision in case
1457      we've been sign extended.  Ignore if type's precision hasn't been set
1458      since what we are doing is setting it.  */
1459
1460   if (prec == 2 * HOST_BITS_PER_WIDE_INT || prec == 0)
1461     ;
1462   else if (prec > HOST_BITS_PER_WIDE_INT)
1463     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1464   else
1465     {
1466       high = 0;
1467       if (prec < HOST_BITS_PER_WIDE_INT)
1468         low &= ~((HOST_WIDE_INT) (-1) << prec);
1469     }
1470
1471   return (high != 0 ? HOST_BITS_PER_WIDE_INT + floor_log2 (high)
1472           : floor_log2 (low));
1473 }
1474
1475 /* Return 1 if EXPR is the real constant zero.  */
1476
1477 int
1478 real_zerop (tree expr)
1479 {
1480   STRIP_NOPS (expr);
1481
1482   return ((TREE_CODE (expr) == REAL_CST
1483            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst0))
1484           || (TREE_CODE (expr) == COMPLEX_CST
1485               && real_zerop (TREE_REALPART (expr))
1486               && real_zerop (TREE_IMAGPART (expr))));
1487 }
1488
1489 /* Return 1 if EXPR is the real constant one in real or complex form.  */
1490
1491 int
1492 real_onep (tree expr)
1493 {
1494   STRIP_NOPS (expr);
1495
1496   return ((TREE_CODE (expr) == REAL_CST
1497            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst1))
1498           || (TREE_CODE (expr) == COMPLEX_CST
1499               && real_onep (TREE_REALPART (expr))
1500               && real_zerop (TREE_IMAGPART (expr))));
1501 }
1502
1503 /* Return 1 if EXPR is the real constant two.  */
1504
1505 int
1506 real_twop (tree expr)
1507 {
1508   STRIP_NOPS (expr);
1509
1510   return ((TREE_CODE (expr) == REAL_CST
1511            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst2))
1512           || (TREE_CODE (expr) == COMPLEX_CST
1513               && real_twop (TREE_REALPART (expr))
1514               && real_zerop (TREE_IMAGPART (expr))));
1515 }
1516
1517 /* Return 1 if EXPR is the real constant minus one.  */
1518
1519 int
1520 real_minus_onep (tree expr)
1521 {
1522   STRIP_NOPS (expr);
1523
1524   return ((TREE_CODE (expr) == REAL_CST
1525            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconstm1))
1526           || (TREE_CODE (expr) == COMPLEX_CST
1527               && real_minus_onep (TREE_REALPART (expr))
1528               && real_zerop (TREE_IMAGPART (expr))));
1529 }
1530
1531 /* Nonzero if EXP is a constant or a cast of a constant.  */
1532
1533 int
1534 really_constant_p (tree exp)
1535 {
1536   /* This is not quite the same as STRIP_NOPS.  It does more.  */
1537   while (TREE_CODE (exp) == NOP_EXPR
1538          || TREE_CODE (exp) == CONVERT_EXPR
1539          || TREE_CODE (exp) == NON_LVALUE_EXPR)
1540     exp = TREE_OPERAND (exp, 0);
1541   return TREE_CONSTANT (exp);
1542 }
1543 \f
1544 /* Return first list element whose TREE_VALUE is ELEM.
1545    Return 0 if ELEM is not in LIST.  */
1546
1547 tree
1548 value_member (tree elem, tree list)
1549 {
1550   while (list)
1551     {
1552       if (elem == TREE_VALUE (list))
1553         return list;
1554       list = TREE_CHAIN (list);
1555     }
1556   return NULL_TREE;
1557 }
1558
1559 /* Return first list element whose TREE_PURPOSE is ELEM.
1560    Return 0 if ELEM is not in LIST.  */
1561
1562 tree
1563 purpose_member (tree elem, tree list)
1564 {
1565   while (list)
1566     {
1567       if (elem == TREE_PURPOSE (list))
1568         return list;
1569       list = TREE_CHAIN (list);
1570     }
1571   return NULL_TREE;
1572 }
1573
1574 /* Return nonzero if ELEM is part of the chain CHAIN.  */
1575
1576 int
1577 chain_member (tree elem, tree chain)
1578 {
1579   while (chain)
1580     {
1581       if (elem == chain)
1582         return 1;
1583       chain = TREE_CHAIN (chain);
1584     }
1585
1586   return 0;
1587 }
1588
1589 /* Return the length of a chain of nodes chained through TREE_CHAIN.
1590    We expect a null pointer to mark the end of the chain.
1591    This is the Lisp primitive `length'.  */
1592
1593 int
1594 list_length (tree t)
1595 {
1596   tree p = t;
1597 #ifdef ENABLE_TREE_CHECKING
1598   tree q = t;
1599 #endif
1600   int len = 0;
1601
1602   while (p)
1603     {
1604       p = TREE_CHAIN (p);
1605 #ifdef ENABLE_TREE_CHECKING
1606       if (len % 2)
1607         q = TREE_CHAIN (q);
1608       gcc_assert (p != q);
1609 #endif
1610       len++;
1611     }
1612
1613   return len;
1614 }
1615
1616 /* Returns the number of FIELD_DECLs in TYPE.  */
1617
1618 int
1619 fields_length (tree type)
1620 {
1621   tree t = TYPE_FIELDS (type);
1622   int count = 0;
1623
1624   for (; t; t = TREE_CHAIN (t))
1625     if (TREE_CODE (t) == FIELD_DECL)
1626       ++count;
1627
1628   return count;
1629 }
1630
1631 /* Concatenate two chains of nodes (chained through TREE_CHAIN)
1632    by modifying the last node in chain 1 to point to chain 2.
1633    This is the Lisp primitive `nconc'.  */
1634
1635 tree
1636 chainon (tree op1, tree op2)
1637 {
1638   tree t1;
1639
1640   if (!op1)
1641     return op2;
1642   if (!op2)
1643     return op1;
1644
1645   for (t1 = op1; TREE_CHAIN (t1); t1 = TREE_CHAIN (t1))
1646     continue;
1647   TREE_CHAIN (t1) = op2;
1648
1649 #ifdef ENABLE_TREE_CHECKING
1650   {
1651     tree t2;
1652     for (t2 = op2; t2; t2 = TREE_CHAIN (t2))
1653       gcc_assert (t2 != t1);
1654   }
1655 #endif
1656
1657   return op1;
1658 }
1659
1660 /* Return the last node in a chain of nodes (chained through TREE_CHAIN).  */
1661
1662 tree
1663 tree_last (tree chain)
1664 {
1665   tree next;
1666   if (chain)
1667     while ((next = TREE_CHAIN (chain)))
1668       chain = next;
1669   return chain;
1670 }
1671
1672 /* Reverse the order of elements in the chain T,
1673    and return the new head of the chain (old last element).  */
1674
1675 tree
1676 nreverse (tree t)
1677 {
1678   tree prev = 0, decl, next;
1679   for (decl = t; decl; decl = next)
1680     {
1681       next = TREE_CHAIN (decl);
1682       TREE_CHAIN (decl) = prev;
1683       prev = decl;
1684     }
1685   return prev;
1686 }
1687 \f
1688 /* Return a newly created TREE_LIST node whose
1689    purpose and value fields are PARM and VALUE.  */
1690
1691 tree
1692 build_tree_list_stat (tree parm, tree value MEM_STAT_DECL)
1693 {
1694   tree t = make_node_stat (TREE_LIST PASS_MEM_STAT);
1695   TREE_PURPOSE (t) = parm;
1696   TREE_VALUE (t) = value;
1697   return t;
1698 }
1699
1700 /* Return a newly created TREE_LIST node whose
1701    purpose and value fields are PURPOSE and VALUE
1702    and whose TREE_CHAIN is CHAIN.  */
1703
1704 tree
1705 tree_cons_stat (tree purpose, tree value, tree chain MEM_STAT_DECL)
1706 {
1707   tree node;
1708
1709   node = ggc_alloc_zone_pass_stat (sizeof (struct tree_list), &tree_zone);
1710
1711   memset (node, 0, sizeof (struct tree_common));
1712
1713 #ifdef GATHER_STATISTICS
1714   tree_node_counts[(int) x_kind]++;
1715   tree_node_sizes[(int) x_kind] += sizeof (struct tree_list);
1716 #endif
1717
1718   TREE_SET_CODE (node, TREE_LIST);
1719   TREE_CHAIN (node) = chain;
1720   TREE_PURPOSE (node) = purpose;
1721   TREE_VALUE (node) = value;
1722   return node;
1723 }
1724
1725 \f
1726 /* Return the size nominally occupied by an object of type TYPE
1727    when it resides in memory.  The value is measured in units of bytes,
1728    and its data type is that normally used for type sizes
1729    (which is the first type created by make_signed_type or
1730    make_unsigned_type).  */
1731
1732 tree
1733 size_in_bytes (tree type)
1734 {
1735   tree t;
1736
1737   if (type == error_mark_node)
1738     return integer_zero_node;
1739
1740   type = TYPE_MAIN_VARIANT (type);
1741   t = TYPE_SIZE_UNIT (type);
1742
1743   if (t == 0)
1744     {
1745       lang_hooks.types.incomplete_type_error (NULL_TREE, type);
1746       return size_zero_node;
1747     }
1748
1749   if (TREE_CODE (t) == INTEGER_CST)
1750     t = force_fit_type (t, 0, false, false);
1751
1752   return t;
1753 }
1754
1755 /* Return the size of TYPE (in bytes) as a wide integer
1756    or return -1 if the size can vary or is larger than an integer.  */
1757
1758 HOST_WIDE_INT
1759 int_size_in_bytes (tree type)
1760 {
1761   tree t;
1762
1763   if (type == error_mark_node)
1764     return 0;
1765
1766   type = TYPE_MAIN_VARIANT (type);
1767   t = TYPE_SIZE_UNIT (type);
1768   if (t == 0
1769       || TREE_CODE (t) != INTEGER_CST
1770       || TREE_INT_CST_HIGH (t) != 0
1771       /* If the result would appear negative, it's too big to represent.  */
1772       || (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0)
1773     return -1;
1774
1775   return TREE_INT_CST_LOW (t);
1776 }
1777
1778 /* Return the maximum size of TYPE (in bytes) as a wide integer
1779    or return -1 if the size can vary or is larger than an integer.  */
1780
1781 HOST_WIDE_INT
1782 max_int_size_in_bytes (tree type)
1783 {
1784   HOST_WIDE_INT size = -1;
1785   tree size_tree;
1786
1787   /* If this is an array type, check for a possible MAX_SIZE attached.  */
1788
1789   if (TREE_CODE (type) == ARRAY_TYPE)
1790     {
1791       size_tree = TYPE_ARRAY_MAX_SIZE (type);
1792
1793       if (size_tree && host_integerp (size_tree, 1))
1794         size = tree_low_cst (size_tree, 1);
1795     }
1796
1797   /* If we still haven't been able to get a size, see if the language
1798      can compute a maximum size.  */
1799
1800   if (size == -1)
1801     {
1802       size_tree = lang_hooks.types.max_size (type);
1803
1804       if (size_tree && host_integerp (size_tree, 1))
1805         size = tree_low_cst (size_tree, 1);
1806     }
1807
1808   return size;
1809 }
1810 \f
1811 /* Return the bit position of FIELD, in bits from the start of the record.
1812    This is a tree of type bitsizetype.  */
1813
1814 tree
1815 bit_position (tree field)
1816 {
1817   return bit_from_pos (DECL_FIELD_OFFSET (field),
1818                        DECL_FIELD_BIT_OFFSET (field));
1819 }
1820
1821 /* Likewise, but return as an integer.  It must be representable in
1822    that way (since it could be a signed value, we don't have the
1823    option of returning -1 like int_size_in_byte can.  */
1824
1825 HOST_WIDE_INT
1826 int_bit_position (tree field)
1827 {
1828   return tree_low_cst (bit_position (field), 0);
1829 }
1830 \f
1831 /* Return the byte position of FIELD, in bytes from the start of the record.
1832    This is a tree of type sizetype.  */
1833
1834 tree
1835 byte_position (tree field)
1836 {
1837   return byte_from_pos (DECL_FIELD_OFFSET (field),
1838                         DECL_FIELD_BIT_OFFSET (field));
1839 }
1840
1841 /* Likewise, but return as an integer.  It must be representable in
1842    that way (since it could be a signed value, we don't have the
1843    option of returning -1 like int_size_in_byte can.  */
1844
1845 HOST_WIDE_INT
1846 int_byte_position (tree field)
1847 {
1848   return tree_low_cst (byte_position (field), 0);
1849 }
1850 \f
1851 /* Return the strictest alignment, in bits, that T is known to have.  */
1852
1853 unsigned int
1854 expr_align (tree t)
1855 {
1856   unsigned int align0, align1;
1857
1858   switch (TREE_CODE (t))
1859     {
1860     case NOP_EXPR:  case CONVERT_EXPR:  case NON_LVALUE_EXPR:
1861       /* If we have conversions, we know that the alignment of the
1862          object must meet each of the alignments of the types.  */
1863       align0 = expr_align (TREE_OPERAND (t, 0));
1864       align1 = TYPE_ALIGN (TREE_TYPE (t));
1865       return MAX (align0, align1);
1866
1867     case SAVE_EXPR:         case COMPOUND_EXPR:       case MODIFY_EXPR:
1868     case INIT_EXPR:         case TARGET_EXPR:         case WITH_CLEANUP_EXPR:
1869     case CLEANUP_POINT_EXPR:
1870       /* These don't change the alignment of an object.  */
1871       return expr_align (TREE_OPERAND (t, 0));
1872
1873     case COND_EXPR:
1874       /* The best we can do is say that the alignment is the least aligned
1875          of the two arms.  */
1876       align0 = expr_align (TREE_OPERAND (t, 1));
1877       align1 = expr_align (TREE_OPERAND (t, 2));
1878       return MIN (align0, align1);
1879
1880     case LABEL_DECL:     case CONST_DECL:
1881     case VAR_DECL:       case PARM_DECL:   case RESULT_DECL:
1882       if (DECL_ALIGN (t) != 0)
1883         return DECL_ALIGN (t);
1884       break;
1885
1886     case FUNCTION_DECL:
1887       return FUNCTION_BOUNDARY;
1888
1889     default:
1890       break;
1891     }
1892
1893   /* Otherwise take the alignment from that of the type.  */
1894   return TYPE_ALIGN (TREE_TYPE (t));
1895 }
1896 \f
1897 /* Return, as a tree node, the number of elements for TYPE (which is an
1898    ARRAY_TYPE) minus one. This counts only elements of the top array.  */
1899
1900 tree
1901 array_type_nelts (tree type)
1902 {
1903   tree index_type, min, max;
1904
1905   /* If they did it with unspecified bounds, then we should have already
1906      given an error about it before we got here.  */
1907   if (! TYPE_DOMAIN (type))
1908     return error_mark_node;
1909
1910   index_type = TYPE_DOMAIN (type);
1911   min = TYPE_MIN_VALUE (index_type);
1912   max = TYPE_MAX_VALUE (index_type);
1913
1914   return (integer_zerop (min)
1915           ? max
1916           : fold_build2 (MINUS_EXPR, TREE_TYPE (max), max, min));
1917 }
1918 \f
1919 /* If arg is static -- a reference to an object in static storage -- then
1920    return the object.  This is not the same as the C meaning of `static'.
1921    If arg isn't static, return NULL.  */
1922
1923 tree
1924 staticp (tree arg)
1925 {
1926   switch (TREE_CODE (arg))
1927     {
1928     case FUNCTION_DECL:
1929       /* Nested functions are static, even though taking their address will
1930          involve a trampoline as we unnest the nested function and create
1931          the trampoline on the tree level.  */
1932       return arg;
1933
1934     case VAR_DECL:
1935       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1936               && ! DECL_THREAD_LOCAL_P (arg)
1937               && ! DECL_DLLIMPORT_P (arg)
1938               ? arg : NULL);
1939
1940     case CONST_DECL:
1941       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1942               ? arg : NULL);
1943
1944     case CONSTRUCTOR:
1945       return TREE_STATIC (arg) ? arg : NULL;
1946
1947     case LABEL_DECL:
1948     case STRING_CST:
1949       return arg;
1950
1951     case COMPONENT_REF:
1952       /* If the thing being referenced is not a field, then it is
1953          something language specific.  */
1954       if (TREE_CODE (TREE_OPERAND (arg, 1)) != FIELD_DECL)
1955         return (*lang_hooks.staticp) (arg);
1956
1957       /* If we are referencing a bitfield, we can't evaluate an
1958          ADDR_EXPR at compile time and so it isn't a constant.  */
1959       if (DECL_BIT_FIELD (TREE_OPERAND (arg, 1)))
1960         return NULL;
1961
1962       return staticp (TREE_OPERAND (arg, 0));
1963
1964     case BIT_FIELD_REF:
1965       return NULL;
1966
1967     case MISALIGNED_INDIRECT_REF:
1968     case ALIGN_INDIRECT_REF:
1969     case INDIRECT_REF:
1970       return TREE_CONSTANT (TREE_OPERAND (arg, 0)) ? arg : NULL;
1971
1972     case ARRAY_REF:
1973     case ARRAY_RANGE_REF:
1974       if (TREE_CODE (TYPE_SIZE (TREE_TYPE (arg))) == INTEGER_CST
1975           && TREE_CODE (TREE_OPERAND (arg, 1)) == INTEGER_CST)
1976         return staticp (TREE_OPERAND (arg, 0));
1977       else
1978         return false;
1979
1980     default:
1981       if ((unsigned int) TREE_CODE (arg)
1982           >= (unsigned int) LAST_AND_UNUSED_TREE_CODE)
1983         return lang_hooks.staticp (arg);
1984       else
1985         return NULL;
1986     }
1987 }
1988 \f
1989 /* Wrap a SAVE_EXPR around EXPR, if appropriate.
1990    Do this to any expression which may be used in more than one place,
1991    but must be evaluated only once.
1992
1993    Normally, expand_expr would reevaluate the expression each time.
1994    Calling save_expr produces something that is evaluated and recorded
1995    the first time expand_expr is called on it.  Subsequent calls to
1996    expand_expr just reuse the recorded value.
1997
1998    The call to expand_expr that generates code that actually computes
1999    the value is the first call *at compile time*.  Subsequent calls
2000    *at compile time* generate code to use the saved value.
2001    This produces correct result provided that *at run time* control
2002    always flows through the insns made by the first expand_expr
2003    before reaching the other places where the save_expr was evaluated.
2004    You, the caller of save_expr, must make sure this is so.
2005
2006    Constants, and certain read-only nodes, are returned with no
2007    SAVE_EXPR because that is safe.  Expressions containing placeholders
2008    are not touched; see tree.def for an explanation of what these
2009    are used for.  */
2010
2011 tree
2012 save_expr (tree expr)
2013 {
2014   tree t = fold (expr);
2015   tree inner;
2016
2017   /* If the tree evaluates to a constant, then we don't want to hide that
2018      fact (i.e. this allows further folding, and direct checks for constants).
2019      However, a read-only object that has side effects cannot be bypassed.
2020      Since it is no problem to reevaluate literals, we just return the
2021      literal node.  */
2022   inner = skip_simple_arithmetic (t);
2023
2024   if (TREE_INVARIANT (inner)
2025       || (TREE_READONLY (inner) && ! TREE_SIDE_EFFECTS (inner))
2026       || TREE_CODE (inner) == SAVE_EXPR
2027       || TREE_CODE (inner) == ERROR_MARK)
2028     return t;
2029
2030   /* If INNER contains a PLACEHOLDER_EXPR, we must evaluate it each time, since
2031      it means that the size or offset of some field of an object depends on
2032      the value within another field.
2033
2034      Note that it must not be the case that T contains both a PLACEHOLDER_EXPR
2035      and some variable since it would then need to be both evaluated once and
2036      evaluated more than once.  Front-ends must assure this case cannot
2037      happen by surrounding any such subexpressions in their own SAVE_EXPR
2038      and forcing evaluation at the proper time.  */
2039   if (contains_placeholder_p (inner))
2040     return t;
2041
2042   t = build1 (SAVE_EXPR, TREE_TYPE (expr), t);
2043
2044   /* This expression might be placed ahead of a jump to ensure that the
2045      value was computed on both sides of the jump.  So make sure it isn't
2046      eliminated as dead.  */
2047   TREE_SIDE_EFFECTS (t) = 1;
2048   TREE_INVARIANT (t) = 1;
2049   return t;
2050 }
2051
2052 /* Look inside EXPR and into any simple arithmetic operations.  Return
2053    the innermost non-arithmetic node.  */
2054
2055 tree
2056 skip_simple_arithmetic (tree expr)
2057 {
2058   tree inner;
2059
2060   /* We don't care about whether this can be used as an lvalue in this
2061      context.  */
2062   while (TREE_CODE (expr) == NON_LVALUE_EXPR)
2063     expr = TREE_OPERAND (expr, 0);
2064
2065   /* If we have simple operations applied to a SAVE_EXPR or to a SAVE_EXPR and
2066      a constant, it will be more efficient to not make another SAVE_EXPR since
2067      it will allow better simplification and GCSE will be able to merge the
2068      computations if they actually occur.  */
2069   inner = expr;
2070   while (1)
2071     {
2072       if (UNARY_CLASS_P (inner))
2073         inner = TREE_OPERAND (inner, 0);
2074       else if (BINARY_CLASS_P (inner))
2075         {
2076           if (TREE_INVARIANT (TREE_OPERAND (inner, 1)))
2077             inner = TREE_OPERAND (inner, 0);
2078           else if (TREE_INVARIANT (TREE_OPERAND (inner, 0)))
2079             inner = TREE_OPERAND (inner, 1);
2080           else
2081             break;
2082         }
2083       else
2084         break;
2085     }
2086
2087   return inner;
2088 }
2089
2090 /* Return which tree structure is used by T.  */
2091
2092 enum tree_node_structure_enum
2093 tree_node_structure (tree t)
2094 {
2095   enum tree_code code = TREE_CODE (t);
2096
2097   switch (TREE_CODE_CLASS (code))
2098     {
2099     case tcc_declaration:
2100       {
2101         switch (code)
2102           {
2103           case FIELD_DECL:
2104             return TS_FIELD_DECL;
2105           case PARM_DECL:
2106             return TS_PARM_DECL;
2107           case VAR_DECL:
2108             return TS_VAR_DECL;
2109           case LABEL_DECL:
2110             return TS_LABEL_DECL;
2111           case RESULT_DECL:
2112             return TS_RESULT_DECL;
2113           case CONST_DECL:
2114             return TS_CONST_DECL;
2115           case TYPE_DECL:
2116             return TS_TYPE_DECL;
2117           case FUNCTION_DECL:
2118             return TS_FUNCTION_DECL;
2119           case SYMBOL_MEMORY_TAG:
2120           case NAME_MEMORY_TAG:
2121           case STRUCT_FIELD_TAG:
2122             return TS_MEMORY_TAG;
2123           default:
2124             return TS_DECL_NON_COMMON;
2125           }
2126       }
2127     case tcc_type:
2128       return TS_TYPE;
2129     case tcc_reference:
2130     case tcc_comparison:
2131     case tcc_unary:
2132     case tcc_binary:
2133     case tcc_expression:
2134     case tcc_statement:
2135       return TS_EXP;
2136     default:  /* tcc_constant and tcc_exceptional */
2137       break;
2138     }
2139   switch (code)
2140     {
2141       /* tcc_constant cases.  */
2142     case INTEGER_CST:           return TS_INT_CST;
2143     case REAL_CST:              return TS_REAL_CST;
2144     case COMPLEX_CST:           return TS_COMPLEX;
2145     case VECTOR_CST:            return TS_VECTOR;
2146     case STRING_CST:            return TS_STRING;
2147       /* tcc_exceptional cases.  */
2148     case ERROR_MARK:            return TS_COMMON;
2149     case IDENTIFIER_NODE:       return TS_IDENTIFIER;
2150     case TREE_LIST:             return TS_LIST;
2151     case TREE_VEC:              return TS_VEC;
2152     case PHI_NODE:              return TS_PHI_NODE;
2153     case SSA_NAME:              return TS_SSA_NAME;
2154     case PLACEHOLDER_EXPR:      return TS_COMMON;
2155     case STATEMENT_LIST:        return TS_STATEMENT_LIST;
2156     case BLOCK:                 return TS_BLOCK;
2157     case CONSTRUCTOR:           return TS_CONSTRUCTOR;
2158     case TREE_BINFO:            return TS_BINFO;
2159     case VALUE_HANDLE:          return TS_VALUE_HANDLE;
2160     case OMP_CLAUSE:            return TS_OMP_CLAUSE;
2161
2162     default:
2163       gcc_unreachable ();
2164     }
2165 }
2166 \f
2167 /* Return 1 if EXP contains a PLACEHOLDER_EXPR; i.e., if it represents a size
2168    or offset that depends on a field within a record.  */
2169
2170 bool
2171 contains_placeholder_p (tree exp)
2172 {
2173   enum tree_code code;
2174
2175   if (!exp)
2176     return 0;
2177
2178   code = TREE_CODE (exp);
2179   if (code == PLACEHOLDER_EXPR)
2180     return 1;
2181
2182   switch (TREE_CODE_CLASS (code))
2183     {
2184     case tcc_reference:
2185       /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit
2186          position computations since they will be converted into a
2187          WITH_RECORD_EXPR involving the reference, which will assume
2188          here will be valid.  */
2189       return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
2190
2191     case tcc_exceptional:
2192       if (code == TREE_LIST)
2193         return (CONTAINS_PLACEHOLDER_P (TREE_VALUE (exp))
2194                 || CONTAINS_PLACEHOLDER_P (TREE_CHAIN (exp)));
2195       break;
2196
2197     case tcc_unary:
2198     case tcc_binary:
2199     case tcc_comparison:
2200     case tcc_expression:
2201       switch (code)
2202         {
2203         case COMPOUND_EXPR:
2204           /* Ignoring the first operand isn't quite right, but works best.  */
2205           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
2206
2207         case COND_EXPR:
2208           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
2209                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))
2210                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2)));
2211
2212         case CALL_EXPR:
2213           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
2214
2215         default:
2216           break;
2217         }
2218
2219       switch (TREE_CODE_LENGTH (code))
2220         {
2221         case 1:
2222           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
2223         case 2:
2224           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
2225                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)));
2226         default:
2227           return 0;
2228         }
2229
2230     default:
2231       return 0;
2232     }
2233   return 0;
2234 }
2235
2236 /* Return true if any part of the computation of TYPE involves a
2237    PLACEHOLDER_EXPR.  This includes size, bounds, qualifiers
2238    (for QUAL_UNION_TYPE) and field positions.  */
2239
2240 static bool
2241 type_contains_placeholder_1 (tree type)
2242 {
2243   /* If the size contains a placeholder or the parent type (component type in
2244      the case of arrays) type involves a placeholder, this type does.  */
2245   if (CONTAINS_PLACEHOLDER_P (TYPE_SIZE (type))
2246       || CONTAINS_PLACEHOLDER_P (TYPE_SIZE_UNIT (type))
2247       || (TREE_TYPE (type) != 0
2248           && type_contains_placeholder_p (TREE_TYPE (type))))
2249     return true;
2250
2251   /* Now do type-specific checks.  Note that the last part of the check above
2252      greatly limits what we have to do below.  */
2253   switch (TREE_CODE (type))
2254     {
2255     case VOID_TYPE:
2256     case COMPLEX_TYPE:
2257     case ENUMERAL_TYPE:
2258     case BOOLEAN_TYPE:
2259     case POINTER_TYPE:
2260     case OFFSET_TYPE:
2261     case REFERENCE_TYPE:
2262     case METHOD_TYPE:
2263     case FUNCTION_TYPE:
2264     case VECTOR_TYPE:
2265       return false;
2266
2267     case INTEGER_TYPE:
2268     case REAL_TYPE:
2269       /* Here we just check the bounds.  */
2270       return (CONTAINS_PLACEHOLDER_P (TYPE_MIN_VALUE (type))
2271               || CONTAINS_PLACEHOLDER_P (TYPE_MAX_VALUE (type)));
2272
2273     case ARRAY_TYPE:
2274       /* We're already checked the component type (TREE_TYPE), so just check
2275          the index type.  */
2276       return type_contains_placeholder_p (TYPE_DOMAIN (type));
2277
2278     case RECORD_TYPE:
2279     case UNION_TYPE:
2280     case QUAL_UNION_TYPE:
2281       {
2282         tree field;
2283
2284         for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2285           if (TREE_CODE (field) == FIELD_DECL
2286               && (CONTAINS_PLACEHOLDER_P (DECL_FIELD_OFFSET (field))
2287                   || (TREE_CODE (type) == QUAL_UNION_TYPE
2288                       && CONTAINS_PLACEHOLDER_P (DECL_QUALIFIER (field)))
2289                   || type_contains_placeholder_p (TREE_TYPE (field))))
2290             return true;
2291
2292         return false;
2293       }
2294
2295     default:
2296       gcc_unreachable ();
2297     }
2298 }
2299
2300 bool
2301 type_contains_placeholder_p (tree type)
2302 {
2303   bool result;
2304
2305   /* If the contains_placeholder_bits field has been initialized,
2306      then we know the answer.  */
2307   if (TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) > 0)
2308     return TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) - 1;
2309
2310   /* Indicate that we've seen this type node, and the answer is false.
2311      This is what we want to return if we run into recursion via fields.  */
2312   TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = 1;
2313
2314   /* Compute the real value.  */
2315   result = type_contains_placeholder_1 (type);
2316
2317   /* Store the real value.  */
2318   TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = result + 1;
2319
2320   return result;
2321 }
2322 \f
2323 /* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
2324    return a tree with all occurrences of references to F in a
2325    PLACEHOLDER_EXPR replaced by R.   Note that we assume here that EXP
2326    contains only arithmetic expressions or a CALL_EXPR with a
2327    PLACEHOLDER_EXPR occurring only in its arglist.  */
2328
2329 tree
2330 substitute_in_expr (tree exp, tree f, tree r)
2331 {
2332   enum tree_code code = TREE_CODE (exp);
2333   tree op0, op1, op2, op3;
2334   tree new;
2335   tree inner;
2336
2337   /* We handle TREE_LIST and COMPONENT_REF separately.  */
2338   if (code == TREE_LIST)
2339     {
2340       op0 = SUBSTITUTE_IN_EXPR (TREE_CHAIN (exp), f, r);
2341       op1 = SUBSTITUTE_IN_EXPR (TREE_VALUE (exp), f, r);
2342       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2343         return exp;
2344
2345       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2346     }
2347   else if (code == COMPONENT_REF)
2348    {
2349      /* If this expression is getting a value from a PLACEHOLDER_EXPR
2350         and it is the right field, replace it with R.  */
2351      for (inner = TREE_OPERAND (exp, 0);
2352           REFERENCE_CLASS_P (inner);
2353           inner = TREE_OPERAND (inner, 0))
2354        ;
2355      if (TREE_CODE (inner) == PLACEHOLDER_EXPR
2356          && TREE_OPERAND (exp, 1) == f)
2357        return r;
2358
2359      /* If this expression hasn't been completed let, leave it alone.  */
2360      if (TREE_CODE (inner) == PLACEHOLDER_EXPR && TREE_TYPE (inner) == 0)
2361        return exp;
2362
2363      op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2364      if (op0 == TREE_OPERAND (exp, 0))
2365        return exp;
2366
2367      new = fold_build3 (COMPONENT_REF, TREE_TYPE (exp),
2368                         op0, TREE_OPERAND (exp, 1), NULL_TREE);
2369    }
2370   else
2371     switch (TREE_CODE_CLASS (code))
2372       {
2373       case tcc_constant:
2374       case tcc_declaration:
2375         return exp;
2376
2377       case tcc_exceptional:
2378       case tcc_unary:
2379       case tcc_binary:
2380       case tcc_comparison:
2381       case tcc_expression:
2382       case tcc_reference:
2383         switch (TREE_CODE_LENGTH (code))
2384           {
2385           case 0:
2386             return exp;
2387
2388           case 1:
2389             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2390             if (op0 == TREE_OPERAND (exp, 0))
2391               return exp;
2392
2393             new = fold_build1 (code, TREE_TYPE (exp), op0);
2394             break;
2395
2396           case 2:
2397             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2398             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2399
2400             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2401               return exp;
2402
2403             new = fold_build2 (code, TREE_TYPE (exp), op0, op1);
2404             break;
2405
2406           case 3:
2407             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2408             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2409             op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
2410
2411             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2412                 && op2 == TREE_OPERAND (exp, 2))
2413               return exp;
2414
2415             new = fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2416             break;
2417
2418           case 4:
2419             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2420             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2421             op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
2422             op3 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 3), f, r);
2423
2424             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2425                 && op2 == TREE_OPERAND (exp, 2)
2426                 && op3 == TREE_OPERAND (exp, 3))
2427               return exp;
2428
2429             new = fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2430             break;
2431
2432           default:
2433             gcc_unreachable ();
2434           }
2435         break;
2436
2437       default:
2438         gcc_unreachable ();
2439       }
2440
2441   TREE_READONLY (new) = TREE_READONLY (exp);
2442   return new;
2443 }
2444
2445 /* Similar, but look for a PLACEHOLDER_EXPR in EXP and find a replacement
2446    for it within OBJ, a tree that is an object or a chain of references.  */
2447
2448 tree
2449 substitute_placeholder_in_expr (tree exp, tree obj)
2450 {
2451   enum tree_code code = TREE_CODE (exp);
2452   tree op0, op1, op2, op3;
2453
2454   /* If this is a PLACEHOLDER_EXPR, see if we find a corresponding type
2455      in the chain of OBJ.  */
2456   if (code == PLACEHOLDER_EXPR)
2457     {
2458       tree need_type = TYPE_MAIN_VARIANT (TREE_TYPE (exp));
2459       tree elt;
2460
2461       for (elt = obj; elt != 0;
2462            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2463                    || TREE_CODE (elt) == COND_EXPR)
2464                   ? TREE_OPERAND (elt, 1)
2465                   : (REFERENCE_CLASS_P (elt)
2466                      || UNARY_CLASS_P (elt)
2467                      || BINARY_CLASS_P (elt)
2468                      || EXPRESSION_CLASS_P (elt))
2469                   ? TREE_OPERAND (elt, 0) : 0))
2470         if (TYPE_MAIN_VARIANT (TREE_TYPE (elt)) == need_type)
2471           return elt;
2472
2473       for (elt = obj; elt != 0;
2474            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2475                    || TREE_CODE (elt) == COND_EXPR)
2476                   ? TREE_OPERAND (elt, 1)
2477                   : (REFERENCE_CLASS_P (elt)
2478                      || UNARY_CLASS_P (elt)
2479                      || BINARY_CLASS_P (elt)
2480                      || EXPRESSION_CLASS_P (elt))
2481                   ? TREE_OPERAND (elt, 0) : 0))
2482         if (POINTER_TYPE_P (TREE_TYPE (elt))
2483             && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (elt)))
2484                 == need_type))
2485           return fold_build1 (INDIRECT_REF, need_type, elt);
2486
2487       /* If we didn't find it, return the original PLACEHOLDER_EXPR.  If it
2488          survives until RTL generation, there will be an error.  */
2489       return exp;
2490     }
2491
2492   /* TREE_LIST is special because we need to look at TREE_VALUE
2493      and TREE_CHAIN, not TREE_OPERANDS.  */
2494   else if (code == TREE_LIST)
2495     {
2496       op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), obj);
2497       op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), obj);
2498       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2499         return exp;
2500
2501       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2502     }
2503   else
2504     switch (TREE_CODE_CLASS (code))
2505       {
2506       case tcc_constant:
2507       case tcc_declaration:
2508         return exp;
2509
2510       case tcc_exceptional:
2511       case tcc_unary:
2512       case tcc_binary:
2513       case tcc_comparison:
2514       case tcc_expression:
2515       case tcc_reference:
2516       case tcc_statement:
2517         switch (TREE_CODE_LENGTH (code))
2518           {
2519           case 0:
2520             return exp;
2521
2522           case 1:
2523             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2524             if (op0 == TREE_OPERAND (exp, 0))
2525               return exp;
2526             else
2527               return fold_build1 (code, TREE_TYPE (exp), op0);
2528
2529           case 2:
2530             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2531             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2532
2533             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2534               return exp;
2535             else
2536               return fold_build2 (code, TREE_TYPE (exp), op0, op1);
2537
2538           case 3:
2539             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2540             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2541             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2542
2543             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2544                 && op2 == TREE_OPERAND (exp, 2))
2545               return exp;
2546             else
2547               return fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2548
2549           case 4:
2550             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2551             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2552             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2553             op3 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 3), obj);
2554
2555             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2556                 && op2 == TREE_OPERAND (exp, 2)
2557                 && op3 == TREE_OPERAND (exp, 3))
2558               return exp;
2559             else
2560               return fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2561
2562           default:
2563             gcc_unreachable ();
2564           }
2565         break;
2566
2567       default:
2568         gcc_unreachable ();
2569       }
2570 }
2571 \f
2572 /* Stabilize a reference so that we can use it any number of times
2573    without causing its operands to be evaluated more than once.
2574    Returns the stabilized reference.  This works by means of save_expr,
2575    so see the caveats in the comments about save_expr.
2576
2577    Also allows conversion expressions whose operands are references.
2578    Any other kind of expression is returned unchanged.  */
2579
2580 tree
2581 stabilize_reference (tree ref)
2582 {
2583   tree result;
2584   enum tree_code code = TREE_CODE (ref);
2585
2586   switch (code)
2587     {
2588     case VAR_DECL:
2589     case PARM_DECL:
2590     case RESULT_DECL:
2591       /* No action is needed in this case.  */
2592       return ref;
2593
2594     case NOP_EXPR:
2595     case CONVERT_EXPR:
2596     case FLOAT_EXPR:
2597     case FIX_TRUNC_EXPR:
2598     case FIX_FLOOR_EXPR:
2599     case FIX_ROUND_EXPR:
2600     case FIX_CEIL_EXPR:
2601       result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
2602       break;
2603
2604     case INDIRECT_REF:
2605       result = build_nt (INDIRECT_REF,
2606                          stabilize_reference_1 (TREE_OPERAND (ref, 0)));
2607       break;
2608
2609     case COMPONENT_REF:
2610       result = build_nt (COMPONENT_REF,
2611                          stabilize_reference (TREE_OPERAND (ref, 0)),
2612                          TREE_OPERAND (ref, 1), NULL_TREE);
2613       break;
2614
2615     case BIT_FIELD_REF:
2616       result = build_nt (BIT_FIELD_REF,
2617                          stabilize_reference (TREE_OPERAND (ref, 0)),
2618                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2619                          stabilize_reference_1 (TREE_OPERAND (ref, 2)));
2620       break;
2621
2622     case ARRAY_REF:
2623       result = build_nt (ARRAY_REF,
2624                          stabilize_reference (TREE_OPERAND (ref, 0)),
2625                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2626                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2627       break;
2628
2629     case ARRAY_RANGE_REF:
2630       result = build_nt (ARRAY_RANGE_REF,
2631                          stabilize_reference (TREE_OPERAND (ref, 0)),
2632                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2633                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2634       break;
2635
2636     case COMPOUND_EXPR:
2637       /* We cannot wrap the first expression in a SAVE_EXPR, as then
2638          it wouldn't be ignored.  This matters when dealing with
2639          volatiles.  */
2640       return stabilize_reference_1 (ref);
2641
2642       /* If arg isn't a kind of lvalue we recognize, make no change.
2643          Caller should recognize the error for an invalid lvalue.  */
2644     default:
2645       return ref;
2646
2647     case ERROR_MARK:
2648       return error_mark_node;
2649     }
2650
2651   TREE_TYPE (result) = TREE_TYPE (ref);
2652   TREE_READONLY (result) = TREE_READONLY (ref);
2653   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
2654   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
2655
2656   return result;
2657 }
2658
2659 /* Subroutine of stabilize_reference; this is called for subtrees of
2660    references.  Any expression with side-effects must be put in a SAVE_EXPR
2661    to ensure that it is only evaluated once.
2662
2663    We don't put SAVE_EXPR nodes around everything, because assigning very
2664    simple expressions to temporaries causes us to miss good opportunities
2665    for optimizations.  Among other things, the opportunity to fold in the
2666    addition of a constant into an addressing mode often gets lost, e.g.
2667    "y[i+1] += x;".  In general, we take the approach that we should not make
2668    an assignment unless we are forced into it - i.e., that any non-side effect
2669    operator should be allowed, and that cse should take care of coalescing
2670    multiple utterances of the same expression should that prove fruitful.  */
2671
2672 tree
2673 stabilize_reference_1 (tree e)
2674 {
2675   tree result;
2676   enum tree_code code = TREE_CODE (e);
2677
2678   /* We cannot ignore const expressions because it might be a reference
2679      to a const array but whose index contains side-effects.  But we can
2680      ignore things that are actual constant or that already have been
2681      handled by this function.  */
2682
2683   if (TREE_INVARIANT (e))
2684     return e;
2685
2686   switch (TREE_CODE_CLASS (code))
2687     {
2688     case tcc_exceptional:
2689     case tcc_type:
2690     case tcc_declaration:
2691     case tcc_comparison:
2692     case tcc_statement:
2693     case tcc_expression:
2694     case tcc_reference:
2695       /* If the expression has side-effects, then encase it in a SAVE_EXPR
2696          so that it will only be evaluated once.  */
2697       /* The reference (r) and comparison (<) classes could be handled as
2698          below, but it is generally faster to only evaluate them once.  */
2699       if (TREE_SIDE_EFFECTS (e))
2700         return save_expr (e);
2701       return e;
2702
2703     case tcc_constant:
2704       /* Constants need no processing.  In fact, we should never reach
2705          here.  */
2706       return e;
2707
2708     case tcc_binary:
2709       /* Division is slow and tends to be compiled with jumps,
2710          especially the division by powers of 2 that is often
2711          found inside of an array reference.  So do it just once.  */
2712       if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
2713           || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
2714           || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
2715           || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
2716         return save_expr (e);
2717       /* Recursively stabilize each operand.  */
2718       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
2719                          stabilize_reference_1 (TREE_OPERAND (e, 1)));
2720       break;
2721
2722     case tcc_unary:
2723       /* Recursively stabilize each operand.  */
2724       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
2725       break;
2726
2727     default:
2728       gcc_unreachable ();
2729     }
2730
2731   TREE_TYPE (result) = TREE_TYPE (e);
2732   TREE_READONLY (result) = TREE_READONLY (e);
2733   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
2734   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
2735   TREE_INVARIANT (result) = 1;
2736
2737   return result;
2738 }
2739 \f
2740 /* Low-level constructors for expressions.  */
2741
2742 /* A helper function for build1 and constant folders.  Set TREE_CONSTANT,
2743    TREE_INVARIANT, and TREE_SIDE_EFFECTS for an ADDR_EXPR.  */
2744
2745 void
2746 recompute_tree_invariant_for_addr_expr (tree t)
2747 {
2748   tree node;
2749   bool tc = true, ti = true, se = false;
2750
2751   /* We started out assuming this address is both invariant and constant, but
2752      does not have side effects.  Now go down any handled components and see if
2753      any of them involve offsets that are either non-constant or non-invariant.
2754      Also check for side-effects.
2755
2756      ??? Note that this code makes no attempt to deal with the case where
2757      taking the address of something causes a copy due to misalignment.  */
2758
2759 #define UPDATE_TITCSE(NODE)  \
2760 do { tree _node = (NODE); \
2761      if (_node && !TREE_INVARIANT (_node)) ti = false; \
2762      if (_node && !TREE_CONSTANT (_node)) tc = false; \
2763      if (_node && TREE_SIDE_EFFECTS (_node)) se = true; } while (0)
2764
2765   for (node = TREE_OPERAND (t, 0); handled_component_p (node);
2766        node = TREE_OPERAND (node, 0))
2767     {
2768       /* If the first operand doesn't have an ARRAY_TYPE, this is a bogus
2769          array reference (probably made temporarily by the G++ front end),
2770          so ignore all the operands.  */
2771       if ((TREE_CODE (node) == ARRAY_REF
2772            || TREE_CODE (node) == ARRAY_RANGE_REF)
2773           && TREE_CODE (TREE_TYPE (TREE_OPERAND (node, 0))) == ARRAY_TYPE)
2774         {
2775           UPDATE_TITCSE (TREE_OPERAND (node, 1));
2776           if (TREE_OPERAND (node, 2))
2777             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2778           if (TREE_OPERAND (node, 3))
2779             UPDATE_TITCSE (TREE_OPERAND (node, 3));
2780         }
2781       /* Likewise, just because this is a COMPONENT_REF doesn't mean we have a
2782          FIELD_DECL, apparently.  The G++ front end can put something else
2783          there, at least temporarily.  */
2784       else if (TREE_CODE (node) == COMPONENT_REF
2785                && TREE_CODE (TREE_OPERAND (node, 1)) == FIELD_DECL)
2786         {
2787           if (TREE_OPERAND (node, 2))
2788             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2789         }
2790       else if (TREE_CODE (node) == BIT_FIELD_REF)
2791         UPDATE_TITCSE (TREE_OPERAND (node, 2));
2792     }
2793
2794   node = lang_hooks.expr_to_decl (node, &tc, &ti, &se);
2795
2796   /* Now see what's inside.  If it's an INDIRECT_REF, copy our properties from
2797      the address, since &(*a)->b is a form of addition.  If it's a decl, it's
2798      invariant and constant if the decl is static.  It's also invariant if it's
2799      a decl in the current function.  Taking the address of a volatile variable
2800      is not volatile.  If it's a constant, the address is both invariant and
2801      constant.  Otherwise it's neither.  */
2802   if (TREE_CODE (node) == INDIRECT_REF)
2803     UPDATE_TITCSE (TREE_OPERAND (node, 0));
2804   else if (DECL_P (node))
2805     {
2806       if (staticp (node))
2807         ;
2808       else if (decl_function_context (node) == current_function_decl
2809                /* Addresses of thread-local variables are invariant.  */
2810                || (TREE_CODE (node) == VAR_DECL
2811                    && DECL_THREAD_LOCAL_P (node)))
2812         tc = false;
2813       else
2814         ti = tc = false;
2815     }
2816   else if (CONSTANT_CLASS_P (node))
2817     ;
2818   else
2819     {
2820       ti = tc = false;
2821       se |= TREE_SIDE_EFFECTS (node);
2822     }
2823
2824   TREE_CONSTANT (t) = tc;
2825   TREE_INVARIANT (t) = ti;
2826   TREE_SIDE_EFFECTS (t) = se;
2827 #undef UPDATE_TITCSE
2828 }
2829
2830 /* Build an expression of code CODE, data type TYPE, and operands as
2831    specified.  Expressions and reference nodes can be created this way.
2832    Constants, decls, types and misc nodes cannot be.
2833
2834    We define 5 non-variadic functions, from 0 to 4 arguments.  This is
2835    enough for all extant tree codes.  */
2836
2837 tree
2838 build0_stat (enum tree_code code, tree tt MEM_STAT_DECL)
2839 {
2840   tree t;
2841
2842   gcc_assert (TREE_CODE_LENGTH (code) == 0);
2843
2844   t = make_node_stat (code PASS_MEM_STAT);
2845   TREE_TYPE (t) = tt;
2846
2847   return t;
2848 }
2849
2850 tree
2851 build1_stat (enum tree_code code, tree type, tree node MEM_STAT_DECL)
2852 {
2853   int length = sizeof (struct tree_exp);
2854 #ifdef GATHER_STATISTICS
2855   tree_node_kind kind;
2856 #endif
2857   tree t;
2858
2859 #ifdef GATHER_STATISTICS
2860   switch (TREE_CODE_CLASS (code))
2861     {
2862     case tcc_statement:  /* an expression with side effects */
2863       kind = s_kind;
2864       break;
2865     case tcc_reference:  /* a reference */
2866       kind = r_kind;
2867       break;
2868     default:
2869       kind = e_kind;
2870       break;
2871     }
2872
2873   tree_node_counts[(int) kind]++;
2874   tree_node_sizes[(int) kind] += length;
2875 #endif
2876
2877   gcc_assert (TREE_CODE_LENGTH (code) == 1);
2878
2879   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
2880
2881   memset (t, 0, sizeof (struct tree_common));
2882
2883   TREE_SET_CODE (t, code);
2884
2885   TREE_TYPE (t) = type;
2886 #ifdef USE_MAPPED_LOCATION
2887   SET_EXPR_LOCATION (t, UNKNOWN_LOCATION);
2888 #else
2889   SET_EXPR_LOCUS (t, NULL);
2890 #endif
2891   TREE_COMPLEXITY (t) = 0;
2892   TREE_OPERAND (t, 0) = node;
2893   TREE_BLOCK (t) = NULL_TREE;
2894   if (node && !TYPE_P (node))
2895     {
2896       TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
2897       TREE_READONLY (t) = TREE_READONLY (node);
2898     }
2899
2900   if (TREE_CODE_CLASS (code) == tcc_statement)
2901     TREE_SIDE_EFFECTS (t) = 1;
2902   else switch (code)
2903     {
2904     case VA_ARG_EXPR:
2905       /* All of these have side-effects, no matter what their
2906          operands are.  */
2907       TREE_SIDE_EFFECTS (t) = 1;
2908       TREE_READONLY (t) = 0;
2909       break;
2910
2911     case MISALIGNED_INDIRECT_REF:
2912     case ALIGN_INDIRECT_REF:
2913     case INDIRECT_REF:
2914       /* Whether a dereference is readonly has nothing to do with whether
2915          its operand is readonly.  */
2916       TREE_READONLY (t) = 0;
2917       break;
2918
2919     case ADDR_EXPR:
2920       if (node)
2921         recompute_tree_invariant_for_addr_expr (t);
2922       break;
2923
2924     default:
2925       if ((TREE_CODE_CLASS (code) == tcc_unary || code == VIEW_CONVERT_EXPR)
2926           && node && !TYPE_P (node)
2927           && TREE_CONSTANT (node))
2928         TREE_CONSTANT (t) = 1;
2929       if ((TREE_CODE_CLASS (code) == tcc_unary || code == VIEW_CONVERT_EXPR)
2930           && node && TREE_INVARIANT (node))
2931         TREE_INVARIANT (t) = 1;
2932       if (TREE_CODE_CLASS (code) == tcc_reference
2933           && node && TREE_THIS_VOLATILE (node))
2934         TREE_THIS_VOLATILE (t) = 1;
2935       break;
2936     }
2937
2938   return t;
2939 }
2940
2941 #define PROCESS_ARG(N)                  \
2942   do {                                  \
2943     TREE_OPERAND (t, N) = arg##N;       \
2944     if (arg##N &&!TYPE_P (arg##N))      \
2945       {                                 \
2946         if (TREE_SIDE_EFFECTS (arg##N)) \
2947           side_effects = 1;             \
2948         if (!TREE_READONLY (arg##N))    \
2949           read_only = 0;                \
2950         if (!TREE_CONSTANT (arg##N))    \
2951           constant = 0;                 \
2952         if (!TREE_INVARIANT (arg##N))   \
2953           invariant = 0;                \
2954       }                                 \
2955   } while (0)
2956
2957 tree
2958 build2_stat (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL)
2959 {
2960   bool constant, read_only, side_effects, invariant;
2961   tree t;
2962
2963   gcc_assert (TREE_CODE_LENGTH (code) == 2);
2964
2965   t = make_node_stat (code PASS_MEM_STAT);
2966   TREE_TYPE (t) = tt;
2967
2968   /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
2969      result based on those same flags for the arguments.  But if the
2970      arguments aren't really even `tree' expressions, we shouldn't be trying
2971      to do this.  */
2972
2973   /* Expressions without side effects may be constant if their
2974      arguments are as well.  */
2975   constant = (TREE_CODE_CLASS (code) == tcc_comparison
2976               || TREE_CODE_CLASS (code) == tcc_binary);
2977   read_only = 1;
2978   side_effects = TREE_SIDE_EFFECTS (t);
2979   invariant = constant;
2980
2981   PROCESS_ARG(0);
2982   PROCESS_ARG(1);
2983
2984   TREE_READONLY (t) = read_only;
2985   TREE_CONSTANT (t) = constant;
2986   TREE_INVARIANT (t) = invariant;
2987   TREE_SIDE_EFFECTS (t) = side_effects;
2988   TREE_THIS_VOLATILE (t)
2989     = (TREE_CODE_CLASS (code) == tcc_reference
2990        && arg0 && TREE_THIS_VOLATILE (arg0));
2991
2992   return t;
2993 }
2994
2995 tree
2996 build3_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2997              tree arg2 MEM_STAT_DECL)
2998 {
2999   bool constant, read_only, side_effects, invariant;
3000   tree t;
3001
3002   gcc_assert (TREE_CODE_LENGTH (code) == 3);
3003
3004   t = make_node_stat (code PASS_MEM_STAT);
3005   TREE_TYPE (t) = tt;
3006
3007   side_effects = TREE_SIDE_EFFECTS (t);
3008
3009   PROCESS_ARG(0);
3010   PROCESS_ARG(1);
3011   PROCESS_ARG(2);
3012
3013   if (code == CALL_EXPR && !side_effects)
3014     {
3015       tree node;
3016       int i;
3017
3018       /* Calls have side-effects, except those to const or
3019          pure functions.  */
3020       i = call_expr_flags (t);
3021       if (!(i & (ECF_CONST | ECF_PURE)))
3022         side_effects = 1;
3023
3024       /* And even those have side-effects if their arguments do.  */
3025       else for (node = arg1; node; node = TREE_CHAIN (node))
3026         if (TREE_SIDE_EFFECTS (TREE_VALUE (node)))
3027           {
3028             side_effects = 1;
3029             break;
3030           }
3031     }
3032
3033   TREE_SIDE_EFFECTS (t) = side_effects;
3034   TREE_THIS_VOLATILE (t)
3035     = (TREE_CODE_CLASS (code) == tcc_reference
3036        && arg0 && TREE_THIS_VOLATILE (arg0));
3037
3038   return t;
3039 }
3040
3041 tree
3042 build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3043              tree arg2, tree arg3 MEM_STAT_DECL)
3044 {
3045   bool constant, read_only, side_effects, invariant;
3046   tree t;
3047
3048   gcc_assert (TREE_CODE_LENGTH (code) == 4);
3049
3050   t = make_node_stat (code PASS_MEM_STAT);
3051   TREE_TYPE (t) = tt;
3052
3053   side_effects = TREE_SIDE_EFFECTS (t);
3054
3055   PROCESS_ARG(0);
3056   PROCESS_ARG(1);
3057   PROCESS_ARG(2);
3058   PROCESS_ARG(3);
3059
3060   TREE_SIDE_EFFECTS (t) = side_effects;
3061   TREE_THIS_VOLATILE (t)
3062     = (TREE_CODE_CLASS (code) == tcc_reference
3063        && arg0 && TREE_THIS_VOLATILE (arg0));
3064
3065   return t;
3066 }
3067
3068 tree
3069 build5_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3070              tree arg2, tree arg3, tree arg4 MEM_STAT_DECL)
3071 {
3072   bool constant, read_only, side_effects, invariant;
3073   tree t;
3074
3075   gcc_assert (TREE_CODE_LENGTH (code) == 5);
3076
3077   t = make_node_stat (code PASS_MEM_STAT);
3078   TREE_TYPE (t) = tt;
3079
3080   side_effects = TREE_SIDE_EFFECTS (t);
3081
3082   PROCESS_ARG(0);
3083   PROCESS_ARG(1);
3084   PROCESS_ARG(2);
3085   PROCESS_ARG(3);
3086   PROCESS_ARG(4);
3087
3088   TREE_SIDE_EFFECTS (t) = side_effects;
3089   TREE_THIS_VOLATILE (t)
3090     = (TREE_CODE_CLASS (code) == tcc_reference
3091        && arg0 && TREE_THIS_VOLATILE (arg0));
3092
3093   return t;
3094 }
3095
3096 tree
3097 build7_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3098              tree arg2, tree arg3, tree arg4, tree arg5,
3099              tree arg6 MEM_STAT_DECL)
3100 {
3101   bool constant, read_only, side_effects, invariant;
3102   tree t;
3103
3104   gcc_assert (code == TARGET_MEM_REF);
3105
3106   t = make_node_stat (code PASS_MEM_STAT);
3107   TREE_TYPE (t) = tt;
3108
3109   side_effects = TREE_SIDE_EFFECTS (t);
3110
3111   PROCESS_ARG(0);
3112   PROCESS_ARG(1);
3113   PROCESS_ARG(2);
3114   PROCESS_ARG(3);
3115   PROCESS_ARG(4);
3116   PROCESS_ARG(5);
3117   PROCESS_ARG(6);
3118
3119   TREE_SIDE_EFFECTS (t) = side_effects;
3120   TREE_THIS_VOLATILE (t) = 0;
3121
3122   return t;
3123 }
3124
3125 /* Similar except don't specify the TREE_TYPE
3126    and leave the TREE_SIDE_EFFECTS as 0.
3127    It is permissible for arguments to be null,
3128    or even garbage if their values do not matter.  */
3129
3130 tree
3131 build_nt (enum tree_code code, ...)
3132 {
3133   tree t;
3134   int length;
3135   int i;
3136   va_list p;
3137
3138   va_start (p, code);
3139
3140   t = make_node (code);
3141   length = TREE_CODE_LENGTH (code);
3142
3143   for (i = 0; i < length; i++)
3144     TREE_OPERAND (t, i) = va_arg (p, tree);
3145
3146   va_end (p);
3147   return t;
3148 }
3149 \f
3150 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
3151    We do NOT enter this node in any sort of symbol table.
3152
3153    layout_decl is used to set up the decl's storage layout.
3154    Other slots are initialized to 0 or null pointers.  */
3155
3156 tree
3157 build_decl_stat (enum tree_code code, tree name, tree type MEM_STAT_DECL)
3158 {
3159   tree t;
3160
3161   t = make_node_stat (code PASS_MEM_STAT);
3162
3163 /*  if (type == error_mark_node)
3164     type = integer_type_node; */
3165 /* That is not done, deliberately, so that having error_mark_node
3166    as the type can suppress useless errors in the use of this variable.  */
3167
3168   DECL_NAME (t) = name;
3169   TREE_TYPE (t) = type;
3170
3171   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
3172     layout_decl (t, 0);
3173   else if (code == FUNCTION_DECL)
3174     DECL_MODE (t) = FUNCTION_MODE;
3175
3176   return t;
3177 }
3178
3179 /* Builds and returns function declaration with NAME and TYPE.  */
3180
3181 tree
3182 build_fn_decl (const char *name, tree type)
3183 {
3184   tree id = get_identifier (name);
3185   tree decl = build_decl (FUNCTION_DECL, id, type);
3186
3187   DECL_EXTERNAL (decl) = 1;
3188   TREE_PUBLIC (decl) = 1;
3189   DECL_ARTIFICIAL (decl) = 1;
3190   TREE_NOTHROW (decl) = 1;
3191
3192   return decl;
3193 }
3194
3195 \f
3196 /* BLOCK nodes are used to represent the structure of binding contours
3197    and declarations, once those contours have been exited and their contents
3198    compiled.  This information is used for outputting debugging info.  */
3199
3200 tree
3201 build_block (tree vars, tree subblocks, tree supercontext, tree chain)
3202 {
3203   tree block = make_node (BLOCK);
3204
3205   BLOCK_VARS (block) = vars;
3206   BLOCK_SUBBLOCKS (block) = subblocks;
3207   BLOCK_SUPERCONTEXT (block) = supercontext;
3208   BLOCK_CHAIN (block) = chain;
3209   return block;
3210 }
3211
3212 #if 1 /* ! defined(USE_MAPPED_LOCATION) */
3213 /* ??? gengtype doesn't handle conditionals */
3214 static GTY(()) source_locus last_annotated_node;
3215 #endif
3216
3217 #ifdef USE_MAPPED_LOCATION
3218
3219 expanded_location
3220 expand_location (source_location loc)
3221 {
3222   expanded_location xloc;
3223   if (loc == 0)
3224     {
3225       xloc.file = NULL;
3226       xloc.line = 0;
3227       xloc.column = 0;
3228     }
3229   else
3230     {
3231       const struct line_map *map = linemap_lookup (&line_table, loc);
3232       xloc.file = map->to_file;
3233       xloc.line = SOURCE_LINE (map, loc);
3234       xloc.column = SOURCE_COLUMN (map, loc);
3235     };
3236   return xloc;
3237 }
3238
3239 #else
3240
3241 /* Record the exact location where an expression or an identifier were
3242    encountered.  */
3243
3244 void
3245 annotate_with_file_line (tree node, const char *file, int line)
3246 {
3247   /* Roughly one percent of the calls to this function are to annotate
3248      a node with the same information already attached to that node!
3249      Just return instead of wasting memory.  */
3250   if (EXPR_LOCUS (node)
3251       && EXPR_LINENO (node) == line
3252       && (EXPR_FILENAME (node) == file
3253           || !strcmp (EXPR_FILENAME (node), file)))
3254     {
3255       last_annotated_node = EXPR_LOCUS (node);
3256       return;
3257     }
3258
3259   /* In heavily macroized code (such as GCC itself) this single
3260      entry cache can reduce the number of allocations by more
3261      than half.  */
3262   if (last_annotated_node
3263       && last_annotated_node->line == line
3264       && (last_annotated_node->file == file
3265           || !strcmp (last_annotated_node->file, file)))
3266     {
3267       SET_EXPR_LOCUS (node, last_annotated_node);
3268       return;
3269     }
3270
3271   SET_EXPR_LOCUS (node, ggc_alloc (sizeof (location_t)));
3272   EXPR_LINENO (node) = line;
3273   EXPR_FILENAME (node) = file;
3274   last_annotated_node = EXPR_LOCUS (node);
3275 }
3276
3277 void
3278 annotate_with_locus (tree node, location_t locus)
3279 {
3280   annotate_with_file_line (node, locus.file, locus.line);
3281 }
3282 #endif
3283 \f
3284 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
3285    is ATTRIBUTE.  */
3286
3287 tree
3288 build_decl_attribute_variant (tree ddecl, tree attribute)
3289 {
3290   DECL_ATTRIBUTES (ddecl) = attribute;
3291   return ddecl;
3292 }
3293
3294 /* Borrowed from hashtab.c iterative_hash implementation.  */
3295 #define mix(a,b,c) \
3296 { \
3297   a -= b; a -= c; a ^= (c>>13); \
3298   b -= c; b -= a; b ^= (a<< 8); \
3299   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
3300   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
3301   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
3302   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
3303   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
3304   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
3305   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
3306 }
3307
3308
3309 /* Produce good hash value combining VAL and VAL2.  */
3310 static inline hashval_t
3311 iterative_hash_hashval_t (hashval_t val, hashval_t val2)
3312 {
3313   /* the golden ratio; an arbitrary value.  */
3314   hashval_t a = 0x9e3779b9;
3315
3316   mix (a, val, val2);
3317   return val2;
3318 }
3319
3320 /* Produce good hash value combining PTR and VAL2.  */
3321 static inline hashval_t
3322 iterative_hash_pointer (void *ptr, hashval_t val2)
3323 {
3324   if (sizeof (ptr) == sizeof (hashval_t))
3325     return iterative_hash_hashval_t ((size_t) ptr, val2);
3326   else
3327     {
3328       hashval_t a = (hashval_t) (size_t) ptr;
3329       /* Avoid warnings about shifting of more than the width of the type on
3330          hosts that won't execute this path.  */
3331       int zero = 0;
3332       hashval_t b = (hashval_t) ((size_t) ptr >> (sizeof (hashval_t) * 8 + zero));
3333       mix (a, b, val2);
3334       return val2;
3335     }
3336 }
3337
3338 /* Produce good hash value combining VAL and VAL2.  */
3339 static inline hashval_t
3340 iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
3341 {
3342   if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
3343     return iterative_hash_hashval_t (val, val2);
3344   else
3345     {
3346       hashval_t a = (hashval_t) val;
3347       /* Avoid warnings about shifting of more than the width of the type on
3348          hosts that won't execute this path.  */
3349       int zero = 0;
3350       hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
3351       mix (a, b, val2);
3352       if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
3353         {
3354           hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
3355           hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
3356           mix (a, b, val2);
3357         }
3358       return val2;
3359     }
3360 }
3361
3362 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
3363    is ATTRIBUTE and its qualifiers are QUALS.
3364
3365    Record such modified types already made so we don't make duplicates.  */
3366
3367 static tree
3368 build_type_attribute_qual_variant (tree ttype, tree attribute, int quals)
3369 {
3370   if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
3371     {
3372       hashval_t hashcode = 0;
3373       tree ntype;
3374       enum tree_code code = TREE_CODE (ttype);
3375
3376       ntype = copy_node (ttype);
3377
3378       TYPE_POINTER_TO (ntype) = 0;
3379       TYPE_REFERENCE_TO (ntype) = 0;
3380       TYPE_ATTRIBUTES (ntype) = attribute;
3381
3382       /* Create a new main variant of TYPE.  */
3383       TYPE_MAIN_VARIANT (ntype) = ntype;
3384       TYPE_NEXT_VARIANT (ntype) = 0;
3385       set_type_quals (ntype, TYPE_UNQUALIFIED);
3386
3387       hashcode = iterative_hash_object (code, hashcode);
3388       if (TREE_TYPE (ntype))
3389         hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
3390                                           hashcode);
3391       hashcode = attribute_hash_list (attribute, hashcode);
3392
3393       switch (TREE_CODE (ntype))
3394         {
3395         case FUNCTION_TYPE:
3396           hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
3397           break;
3398         case ARRAY_TYPE:
3399           hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
3400                                             hashcode);
3401           break;
3402         case INTEGER_TYPE:
3403           hashcode = iterative_hash_object
3404             (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
3405           hashcode = iterative_hash_object
3406             (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
3407           break;
3408         case REAL_TYPE:
3409           {
3410             unsigned int precision = TYPE_PRECISION (ntype);
3411             hashcode = iterative_hash_object (precision, hashcode);
3412           }
3413           break;
3414         default:
3415           break;
3416         }
3417
3418       ntype = type_hash_canon (hashcode, ntype);
3419       ttype = build_qualified_type (ntype, quals);
3420     }
3421
3422   return ttype;
3423 }
3424
3425
3426 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
3427    is ATTRIBUTE.
3428
3429    Record such modified types already made so we don't make duplicates.  */
3430
3431 tree
3432 build_type_attribute_variant (tree ttype, tree attribute)
3433 {
3434   return build_type_attribute_qual_variant (ttype, attribute,
3435                                             TYPE_QUALS (ttype));
3436 }
3437
3438 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3439    or zero if not.
3440
3441    We try both `text' and `__text__', ATTR may be either one.  */
3442 /* ??? It might be a reasonable simplification to require ATTR to be only
3443    `text'.  One might then also require attribute lists to be stored in
3444    their canonicalized form.  */
3445
3446 static int
3447 is_attribute_with_length_p (const char *attr, int attr_len, tree ident)
3448 {
3449   int ident_len;
3450   const char *p;
3451
3452   if (TREE_CODE (ident) != IDENTIFIER_NODE)
3453     return 0;
3454
3455   p = IDENTIFIER_POINTER (ident);
3456   ident_len = IDENTIFIER_LENGTH (ident);
3457
3458   if (ident_len == attr_len
3459       && strcmp (attr, p) == 0)
3460     return 1;
3461
3462   /* If ATTR is `__text__', IDENT must be `text'; and vice versa.  */
3463   if (attr[0] == '_')
3464     {
3465       gcc_assert (attr[1] == '_');
3466       gcc_assert (attr[attr_len - 2] == '_');
3467       gcc_assert (attr[attr_len - 1] == '_');
3468       if (ident_len == attr_len - 4
3469           && strncmp (attr + 2, p, attr_len - 4) == 0)
3470         return 1;
3471     }
3472   else
3473     {
3474       if (ident_len == attr_len + 4
3475           && p[0] == '_' && p[1] == '_'
3476           && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
3477           && strncmp (attr, p + 2, attr_len) == 0)
3478         return 1;
3479     }
3480
3481   return 0;
3482 }
3483
3484 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3485    or zero if not.
3486
3487    We try both `text' and `__text__', ATTR may be either one.  */
3488
3489 int
3490 is_attribute_p (const char *attr, tree ident)
3491 {
3492   return is_attribute_with_length_p (attr, strlen (attr), ident);
3493 }
3494
3495 /* Given an attribute name and a list of attributes, return a pointer to the
3496    attribute's list element if the attribute is part of the list, or NULL_TREE
3497    if not found.  If the attribute appears more than once, this only
3498    returns the first occurrence; the TREE_CHAIN of the return value should
3499    be passed back in if further occurrences are wanted.  */
3500
3501 tree
3502 lookup_attribute (const char *attr_name, tree list)
3503 {
3504   tree l;
3505   size_t attr_len = strlen (attr_name);
3506
3507   for (l = list; l; l = TREE_CHAIN (l))
3508     {
3509       gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE);
3510       if (is_attribute_with_length_p (attr_name, attr_len, TREE_PURPOSE (l)))
3511         return l;
3512     }
3513
3514   return NULL_TREE;
3515 }
3516
3517 /* Remove any instances of attribute ATTR_NAME in LIST and return the
3518    modified list.  */
3519
3520 tree
3521 remove_attribute (const char *attr_name, tree list)
3522 {
3523   tree *p;
3524   size_t attr_len = strlen (attr_name);
3525
3526   for (p = &list; *p; )
3527     {
3528       tree l = *p;
3529       gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE);
3530       if (is_attribute_with_length_p (attr_name, attr_len, TREE_PURPOSE (l)))
3531         *p = TREE_CHAIN (l);
3532       else
3533         p = &TREE_CHAIN (l);
3534     }
3535
3536   return list;
3537 }
3538
3539 /* Return an attribute list that is the union of a1 and a2.  */
3540
3541 tree
3542 merge_attributes (tree a1, tree a2)
3543 {
3544   tree attributes;
3545
3546   /* Either one unset?  Take the set one.  */
3547
3548   if ((attributes = a1) == 0)
3549     attributes = a2;
3550
3551   /* One that completely contains the other?  Take it.  */
3552
3553   else if (a2 != 0 && ! attribute_list_contained (a1, a2))
3554     {
3555       if (attribute_list_contained (a2, a1))
3556         attributes = a2;
3557       else
3558         {
3559           /* Pick the longest list, and hang on the other list.  */
3560
3561           if (list_length (a1) < list_length (a2))
3562             attributes = a2, a2 = a1;
3563
3564           for (; a2 != 0; a2 = TREE_CHAIN (a2))
3565             {
3566               tree a;
3567               for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3568                                          attributes);
3569                    a != NULL_TREE;
3570                    a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3571                                          TREE_CHAIN (a)))
3572                 {
3573                   if (TREE_VALUE (a) != NULL
3574                       && TREE_CODE (TREE_VALUE (a)) == TREE_LIST
3575                       && TREE_VALUE (a2) != NULL
3576                       && TREE_CODE (TREE_VALUE (a2)) == TREE_LIST)
3577                     {
3578                       if (simple_cst_list_equal (TREE_VALUE (a),
3579                                                  TREE_VALUE (a2)) == 1)
3580                         break;
3581                     }
3582                   else if (simple_cst_equal (TREE_VALUE (a),
3583                                              TREE_VALUE (a2)) == 1)
3584                     break;
3585                 }
3586               if (a == NULL_TREE)
3587                 {
3588                   a1 = copy_node (a2);
3589                   TREE_CHAIN (a1) = attributes;
3590                   attributes = a1;
3591                 }
3592             }
3593         }
3594     }
3595   return attributes;
3596 }
3597
3598 /* Given types T1 and T2, merge their attributes and return
3599   the result.  */
3600
3601 tree
3602 merge_type_attributes (tree t1, tree t2)
3603 {
3604   return merge_attributes (TYPE_ATTRIBUTES (t1),
3605                            TYPE_ATTRIBUTES (t2));
3606 }
3607
3608 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
3609    the result.  */
3610
3611 tree
3612 merge_decl_attributes (tree olddecl, tree newdecl)
3613 {
3614   return merge_attributes (DECL_ATTRIBUTES (olddecl),
3615                            DECL_ATTRIBUTES (newdecl));
3616 }
3617
3618 #if TARGET_DLLIMPORT_DECL_ATTRIBUTES
3619
3620 /* Specialization of merge_decl_attributes for various Windows targets.
3621
3622    This handles the following situation:
3623
3624      __declspec (dllimport) int foo;
3625      int foo;
3626
3627    The second instance of `foo' nullifies the dllimport.  */
3628
3629 tree
3630 merge_dllimport_decl_attributes (tree old, tree new)
3631 {
3632   tree a;
3633   int delete_dllimport_p = 1;
3634
3635   /* What we need to do here is remove from `old' dllimport if it doesn't
3636      appear in `new'.  dllimport behaves like extern: if a declaration is
3637      marked dllimport and a definition appears later, then the object
3638      is not dllimport'd.  We also remove a `new' dllimport if the old list
3639      contains dllexport:  dllexport always overrides dllimport, regardless
3640      of the order of declaration.  */
3641   if (!VAR_OR_FUNCTION_DECL_P (new))
3642     delete_dllimport_p = 0;
3643   else if (DECL_DLLIMPORT_P (new)
3644            && lookup_attribute ("dllexport", DECL_ATTRIBUTES (old)))
3645     {
3646       DECL_DLLIMPORT_P (new) = 0;
3647       warning (OPT_Wattributes, "%q+D already declared with dllexport attribute: "
3648               "dllimport ignored", new);
3649     }
3650   else if (DECL_DLLIMPORT_P (old) && !DECL_DLLIMPORT_P (new))
3651     {
3652       /* Warn about overriding a symbol that has already been used. eg:
3653            extern int __attribute__ ((dllimport)) foo;
3654            int* bar () {return &foo;}
3655            int foo;
3656       */
3657       if (TREE_USED (old))
3658         {
3659           warning (0, "%q+D redeclared without dllimport attribute "
3660                    "after being referenced with dll linkage", new);
3661           /* If we have used a variable's address with dllimport linkage,
3662               keep the old DECL_DLLIMPORT_P flag: the ADDR_EXPR using the
3663               decl may already have had TREE_INVARIANT and TREE_CONSTANT
3664               computed.
3665               We still remove the attribute so that assembler code refers
3666               to '&foo rather than '_imp__foo'.  */
3667           if (TREE_CODE (old) == VAR_DECL && TREE_ADDRESSABLE (old))
3668             DECL_DLLIMPORT_P (new) = 1;
3669         }
3670
3671       /* Let an inline definition silently override the external reference,
3672          but otherwise warn about attribute inconsistency.  */
3673       else if (TREE_CODE (new) == VAR_DECL
3674                || !DECL_DECLARED_INLINE_P (new))
3675         warning (OPT_Wattributes, "%q+D redeclared without dllimport attribute: "
3676                   "previous dllimport ignored", new);
3677     }
3678   else
3679     delete_dllimport_p = 0;
3680
3681   a = merge_attributes (DECL_ATTRIBUTES (old), DECL_ATTRIBUTES (new));
3682
3683   if (delete_dllimport_p)
3684     {
3685       tree prev, t;
3686       const size_t attr_len = strlen ("dllimport");
3687
3688       /* Scan the list for dllimport and delete it.  */
3689       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
3690         {
3691           if (is_attribute_with_length_p ("dllimport", attr_len,
3692                                           TREE_PURPOSE (t)))
3693             {
3694               if (prev == NULL_TREE)
3695                 a = TREE_CHAIN (a);
3696               else
3697                 TREE_CHAIN (prev) = TREE_CHAIN (t);
3698               break;
3699             }
3700         }
3701     }
3702
3703   return a;
3704 }
3705
3706 /* Handle a "dllimport" or "dllexport" attribute; arguments as in
3707    struct attribute_spec.handler.  */
3708
3709 tree
3710 handle_dll_attribute (tree * pnode, tree name, tree args, int flags,
3711                       bool *no_add_attrs)
3712 {
3713   tree node = *pnode;
3714
3715   /* These attributes may apply to structure and union types being created,
3716      but otherwise should pass to the declaration involved.  */
3717   if (!DECL_P (node))
3718     {
3719       if (flags & ((int) ATTR_FLAG_DECL_NEXT | (int) ATTR_FLAG_FUNCTION_NEXT
3720                    | (int) ATTR_FLAG_ARRAY_NEXT))
3721         {
3722           *no_add_attrs = true;
3723           return tree_cons (name, args, NULL_TREE);
3724         }
3725       if (TREE_CODE (node) != RECORD_TYPE && TREE_CODE (node) != UNION_TYPE)
3726         {
3727           warning (OPT_Wattributes, "%qs attribute ignored",
3728                    IDENTIFIER_POINTER (name));
3729           *no_add_attrs = true;
3730         }
3731
3732       return NULL_TREE;
3733     }
3734
3735   if (TREE_CODE (node) != FUNCTION_DECL
3736       && TREE_CODE (node) != VAR_DECL)
3737     {
3738       *no_add_attrs = true;
3739       warning (OPT_Wattributes, "%qs attribute ignored",
3740                IDENTIFIER_POINTER (name));
3741       return NULL_TREE;
3742     }
3743
3744   /* Report error on dllimport ambiguities seen now before they cause
3745      any damage.  */
3746   else if (is_attribute_p ("dllimport", name))
3747     {
3748       /* Honor any target-specific overrides. */
3749       if (!targetm.valid_dllimport_attribute_p (node))
3750         *no_add_attrs = true;
3751
3752      else if (TREE_CODE (node) == FUNCTION_DECL
3753                 && DECL_DECLARED_INLINE_P (node))
3754         {
3755           warning (OPT_Wattributes, "inline function %q+D declared as "
3756                   " dllimport: attribute ignored", node);
3757           *no_add_attrs = true;
3758         }
3759       /* Like MS, treat definition of dllimported variables and
3760          non-inlined functions on declaration as syntax errors. */
3761      else if (TREE_CODE (node) == FUNCTION_DECL && DECL_INITIAL (node))
3762         {
3763           error ("function %q+D definition is marked dllimport", node);
3764           *no_add_attrs = true;
3765         }
3766
3767      else if (TREE_CODE (node) == VAR_DECL)
3768         {
3769           if (DECL_INITIAL (node))
3770             {
3771               error ("variable %q+D definition is marked dllimport",
3772                      node);
3773               *no_add_attrs = true;
3774             }
3775
3776           /* `extern' needn't be specified with dllimport.
3777              Specify `extern' now and hope for the best.  Sigh.  */
3778           DECL_EXTERNAL (node) = 1;
3779           /* Also, implicitly give dllimport'd variables declared within
3780              a function global scope, unless declared static.  */
3781           if (current_function_decl != NULL_TREE && !TREE_STATIC (node))
3782             TREE_PUBLIC (node) = 1;
3783         }
3784
3785       if (*no_add_attrs == false)
3786         DECL_DLLIMPORT_P (node) = 1;
3787     }
3788
3789   /*  Report error if symbol is not accessible at global scope.  */
3790   if (!TREE_PUBLIC (node)
3791       && (TREE_CODE (node) == VAR_DECL
3792           || TREE_CODE (node) == FUNCTION_DECL))
3793     {
3794       error ("external linkage required for symbol %q+D because of "
3795              "%qs attribute", node, IDENTIFIER_POINTER (name));
3796       *no_add_attrs = true;
3797     }
3798
3799   return NULL_TREE;
3800 }
3801
3802 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
3803 \f
3804 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
3805    of the various TYPE_QUAL values.  */
3806
3807 static void
3808 set_type_quals (tree type, int type_quals)
3809 {
3810   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
3811   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
3812   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
3813 }
3814
3815 /* Returns true iff cand is equivalent to base with type_quals.  */
3816
3817 bool
3818 check_qualified_type (tree cand, tree base, int type_quals)
3819 {
3820   return (TYPE_QUALS (cand) == type_quals
3821           && TYPE_NAME (cand) == TYPE_NAME (base)
3822           /* Apparently this is needed for Objective-C.  */
3823           && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base)
3824           && attribute_list_equal (TYPE_ATTRIBUTES (cand),
3825                                    TYPE_ATTRIBUTES (base)));
3826 }
3827
3828 /* Return a version of the TYPE, qualified as indicated by the
3829    TYPE_QUALS, if one exists.  If no qualified version exists yet,
3830    return NULL_TREE.  */
3831
3832 tree
3833 get_qualified_type (tree type, int type_quals)
3834 {
3835   tree t;
3836
3837   if (TYPE_QUALS (type) == type_quals)
3838     return type;
3839
3840   /* Search the chain of variants to see if there is already one there just
3841      like the one we need to have.  If so, use that existing one.  We must
3842      preserve the TYPE_NAME, since there is code that depends on this.  */
3843   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
3844     if (check_qualified_type (t, type, type_quals))
3845       return t;
3846
3847   return NULL_TREE;
3848 }
3849
3850 /* Like get_qualified_type, but creates the type if it does not
3851    exist.  This function never returns NULL_TREE.  */
3852
3853 tree
3854 build_qualified_type (tree type, int type_quals)
3855 {
3856   tree t;
3857
3858   /* See if we already have the appropriate qualified variant.  */
3859   t = get_qualified_type (type, type_quals);
3860
3861   /* If not, build it.  */
3862   if (!t)
3863     {
3864       t = build_variant_type_copy (type);
3865       set_type_quals (t, type_quals);
3866     }
3867
3868   return t;
3869 }
3870
3871 /* Create a new distinct copy of TYPE.  The new type is made its own
3872    MAIN_VARIANT.  */
3873
3874 tree
3875 build_distinct_type_copy (tree type)
3876 {
3877   tree t = copy_node (type);
3878
3879   TYPE_POINTER_TO (t) = 0;
3880   TYPE_REFERENCE_TO (t) = 0;
3881
3882   /* Make it its own variant.  */
3883   TYPE_MAIN_VARIANT (t) = t;
3884   TYPE_NEXT_VARIANT (t) = 0;
3885
3886   return t;
3887 }
3888
3889 /* Create a new variant of TYPE, equivalent but distinct.
3890    This is so the caller can modify it.  */
3891
3892 tree
3893 build_variant_type_copy (tree type)
3894 {
3895   tree t, m = TYPE_MAIN_VARIANT (type);
3896
3897   t = build_distinct_type_copy (type);
3898
3899   /* Add the new type to the chain of variants of TYPE.  */
3900   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3901   TYPE_NEXT_VARIANT (m) = t;
3902   TYPE_MAIN_VARIANT (t) = m;
3903
3904   return t;
3905 }
3906 \f
3907 /* Return true if the from tree in both tree maps are equal.  */
3908
3909 int
3910 tree_map_eq (const void *va, const void *vb)
3911 {
3912   const struct tree_map  *a = va, *b = vb;
3913   return (a->from == b->from);
3914 }
3915
3916 /* Hash a from tree in a tree_map.  */
3917
3918 unsigned int
3919 tree_map_hash (const void *item)
3920 {
3921   return (((const struct tree_map *) item)->hash);
3922 }
3923
3924 /* Return true if this tree map structure is marked for garbage collection
3925    purposes.  We simply return true if the from tree is marked, so that this
3926    structure goes away when the from tree goes away.  */
3927
3928 int
3929 tree_map_marked_p (const void *p)
3930 {
3931   tree from = ((struct tree_map *) p)->from;
3932
3933   return ggc_marked_p (from);
3934 }
3935
3936 /* Return true if the trees in the tree_int_map *'s VA and VB are equal.  */
3937
3938 static int
3939 tree_int_map_eq (const void *va, const void *vb)
3940 {
3941   const struct tree_int_map  *a = va, *b = vb;
3942   return (a->from == b->from);
3943 }
3944
3945 /* Hash a from tree in the tree_int_map * ITEM.  */
3946
3947 static unsigned int
3948 tree_int_map_hash (const void *item)
3949 {
3950   return htab_hash_pointer (((const struct tree_int_map *)item)->from);
3951 }
3952
3953 /* Return true if this tree int map structure is marked for garbage collection
3954    purposes.  We simply return true if the from tree_int_map *P's from tree is marked, so that this
3955    structure goes away when the from tree goes away.  */
3956
3957 static int
3958 tree_int_map_marked_p (const void *p)
3959 {
3960   tree from = ((struct tree_int_map *) p)->from;
3961
3962   return ggc_marked_p (from);
3963 }
3964 /* Lookup an init priority for FROM, and return it if we find one.  */
3965
3966 unsigned short
3967 decl_init_priority_lookup (tree from)
3968 {
3969   struct tree_int_map *h, in;
3970   in.from = from;
3971
3972   h = htab_find_with_hash (init_priority_for_decl,
3973                            &in, htab_hash_pointer (from));
3974   if (h)
3975     return h->to;
3976   return 0;
3977 }
3978
3979 /* Insert a mapping FROM->TO in the init priority hashtable.  */
3980
3981 void
3982 decl_init_priority_insert (tree from, unsigned short to)
3983 {
3984   struct tree_int_map *h;
3985   void **loc;
3986
3987   h = ggc_alloc (sizeof (struct tree_int_map));
3988   h->from = from;
3989   h->to = to;
3990   loc = htab_find_slot_with_hash (init_priority_for_decl, h,
3991                                   htab_hash_pointer (from), INSERT);
3992   *(struct tree_int_map **) loc = h;
3993 }
3994
3995 /* Look up a restrict qualified base decl for FROM.  */
3996
3997 tree
3998 decl_restrict_base_lookup (tree from)
3999 {
4000   struct tree_map *h;
4001   struct tree_map in;
4002
4003   in.from = from;
4004   h = htab_find_with_hash (restrict_base_for_decl, &in,
4005                            htab_hash_pointer (from));
4006   return h ? h->to : NULL_TREE;
4007 }
4008
4009 /* Record the restrict qualified base TO for FROM.  */
4010
4011 void
4012 decl_restrict_base_insert (tree from, tree to)
4013 {
4014   struct tree_map *h;
4015   void **loc;
4016
4017   h = ggc_alloc (sizeof (struct tree_map));
4018   h->hash = htab_hash_pointer (from);
4019   h->from = from;
4020   h->to = to;
4021   loc = htab_find_slot_with_hash (restrict_base_for_decl, h, h->hash, INSERT);
4022   *(struct tree_map **) loc = h;
4023 }
4024
4025 /* Print out the statistics for the DECL_DEBUG_EXPR hash table.  */
4026
4027 static void
4028 print_debug_expr_statistics (void)
4029 {
4030   fprintf (stderr, "DECL_DEBUG_EXPR  hash: size %ld, %ld elements, %f collisions\n",
4031            (long) htab_size (debug_expr_for_decl),
4032            (long) htab_elements (debug_expr_for_decl),
4033            htab_collisions (debug_expr_for_decl));
4034 }
4035
4036 /* Print out the statistics for the DECL_VALUE_EXPR hash table.  */
4037
4038 static void
4039 print_value_expr_statistics (void)
4040 {
4041   fprintf (stderr, "DECL_VALUE_EXPR  hash: size %ld, %ld elements, %f collisions\n",
4042            (long) htab_size (value_expr_for_decl),
4043            (long) htab_elements (value_expr_for_decl),
4044            htab_collisions (value_expr_for_decl));
4045 }
4046
4047 /* Print out statistics for the RESTRICT_BASE_FOR_DECL hash table, but
4048    don't print anything if the table is empty.  */
4049
4050 static void
4051 print_restrict_base_statistics (void)
4052 {
4053   if (htab_elements (restrict_base_for_decl) != 0)
4054     fprintf (stderr,
4055              "RESTRICT_BASE    hash: size %ld, %ld elements, %f collisions\n",
4056              (long) htab_size (restrict_base_for_decl),
4057              (long) htab_elements (restrict_base_for_decl),
4058              htab_collisions (restrict_base_for_decl));
4059 }
4060
4061 /* Lookup a debug expression for FROM, and return it if we find one.  */
4062
4063 tree
4064 decl_debug_expr_lookup (tree from)
4065 {
4066   struct tree_map *h, in;
4067   in.from = from;
4068
4069   h = htab_find_with_hash (debug_expr_for_decl, &in, htab_hash_pointer (from));
4070   if (h)
4071     return h->to;
4072   return NULL_TREE;
4073 }
4074
4075 /* Insert a mapping FROM->TO in the debug expression hashtable.  */
4076
4077 void
4078 decl_debug_expr_insert (tree from, tree to)
4079 {
4080   struct tree_map *h;
4081   void **loc;
4082
4083   h = ggc_alloc (sizeof (struct tree_map));
4084   h->hash = htab_hash_pointer (from);
4085   h->from = from;
4086   h->to = to;
4087   loc = htab_find_slot_with_hash (debug_expr_for_decl, h, h->hash, INSERT);
4088   *(struct tree_map **) loc = h;
4089 }
4090
4091 /* Lookup a value expression for FROM, and return it if we find one.  */
4092
4093 tree
4094 decl_value_expr_lookup (tree from)
4095 {
4096   struct tree_map *h, in;
4097   in.from = from;
4098
4099   h = htab_find_with_hash (value_expr_for_decl, &in, htab_hash_pointer (from));
4100   if (h)
4101     return h->to;
4102   return NULL_TREE;
4103 }
4104
4105 /* Insert a mapping FROM->TO in the value expression hashtable.  */
4106
4107 void
4108 decl_value_expr_insert (tree from, tree to)
4109 {
4110   struct tree_map *h;
4111   void **loc;
4112
4113   h = ggc_alloc (sizeof (struct tree_map));
4114   h->hash = htab_hash_pointer (from);
4115   h->from = from;
4116   h->to = to;
4117   loc = htab_find_slot_with_hash (value_expr_for_decl, h, h->hash, INSERT);
4118   *(struct tree_map **) loc = h;
4119 }
4120
4121 /* Hashing of types so that we don't make duplicates.
4122    The entry point is `type_hash_canon'.  */
4123
4124 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
4125    with types in the TREE_VALUE slots), by adding the hash codes
4126    of the individual types.  */
4127
4128 unsigned int
4129 type_hash_list (tree list, hashval_t hashcode)
4130 {
4131   tree tail;
4132
4133   for (tail = list; tail; tail = TREE_CHAIN (tail))
4134     if (TREE_VALUE (tail) != error_mark_node)
4135       hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
4136                                         hashcode);
4137
4138   return hashcode;
4139 }
4140
4141 /* These are the Hashtable callback functions.  */
4142
4143 /* Returns true iff the types are equivalent.  */
4144
4145 static int
4146 type_hash_eq (const void *va, const void *vb)
4147 {
4148   const struct type_hash *a = va, *b = vb;
4149
4150   /* First test the things that are the same for all types.  */
4151   if (a->hash != b->hash
4152       || TREE_CODE (a->type) != TREE_CODE (b->type)
4153       || TREE_TYPE (a->type) != TREE_TYPE (b->type)
4154       || !attribute_list_equal (TYPE_ATTRIBUTES (a->type),
4155                                  TYPE_ATTRIBUTES (b->type))
4156       || TYPE_ALIGN (a->type) != TYPE_ALIGN (b->type)
4157       || TYPE_MODE (a->type) != TYPE_MODE (b->type))
4158     return 0;
4159
4160   switch (TREE_CODE (a->type))
4161     {
4162     case VOID_TYPE:
4163     case COMPLEX_TYPE:
4164     case POINTER_TYPE:
4165     case REFERENCE_TYPE:
4166       return 1;
4167
4168     case VECTOR_TYPE:
4169       return TYPE_VECTOR_SUBPARTS (a->type) == TYPE_VECTOR_SUBPARTS (b->type);
4170
4171     case ENUMERAL_TYPE:
4172       if (TYPE_VALUES (a->type) != TYPE_VALUES (b->type)
4173           && !(TYPE_VALUES (a->type)
4174                && TREE_CODE (TYPE_VALUES (a->type)) == TREE_LIST
4175                && TYPE_VALUES (b->type)
4176                && TREE_CODE (TYPE_VALUES (b->type)) == TREE_LIST
4177                && type_list_equal (TYPE_VALUES (a->type),
4178                                    TYPE_VALUES (b->type))))
4179         return 0;
4180
4181       /* ... fall through ... */
4182
4183     case INTEGER_TYPE:
4184     case REAL_TYPE:
4185     case BOOLEAN_TYPE:
4186       return ((TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
4187                || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
4188                                       TYPE_MAX_VALUE (b->type)))
4189               && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
4190                   || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
4191                                          TYPE_MIN_VALUE (b->type))));
4192
4193     case OFFSET_TYPE:
4194       return TYPE_OFFSET_BASETYPE (a->type) == TYPE_OFFSET_BASETYPE (b->type);
4195
4196     case METHOD_TYPE:
4197       return (TYPE_METHOD_BASETYPE (a->type) == TYPE_METHOD_BASETYPE (b->type)
4198               && (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
4199                   || (TYPE_ARG_TYPES (a->type)
4200                       && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
4201                       && TYPE_ARG_TYPES (b->type)
4202                       && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
4203                       && type_list_equal (TYPE_ARG_TYPES (a->type),
4204                                           TYPE_ARG_TYPES (b->type)))));
4205
4206     case ARRAY_TYPE:
4207       return TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type);
4208
4209     case RECORD_TYPE:
4210     case UNION_TYPE:
4211     case QUAL_UNION_TYPE:
4212       return (TYPE_FIELDS (a->type) == TYPE_FIELDS (b->type)
4213               || (TYPE_FIELDS (a->type)
4214                   && TREE_CODE (TYPE_FIELDS (a->type)) == TREE_LIST
4215                   && TYPE_FIELDS (b->type)
4216                   && TREE_CODE (TYPE_FIELDS (b->type)) == TREE_LIST
4217                   && type_list_equal (TYPE_FIELDS (a->type),
4218                                       TYPE_FIELDS (b->type))));
4219
4220     case FUNCTION_TYPE:
4221       return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
4222               || (TYPE_ARG_TYPES (a->type)
4223                   && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
4224                   && TYPE_ARG_TYPES (b->type)
4225                   && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
4226                   && type_list_equal (TYPE_ARG_TYPES (a->type),
4227                                       TYPE_ARG_TYPES (b->type))));
4228
4229     default:
4230       return 0;
4231     }
4232 }
4233
4234 /* Return the cached hash value.  */
4235
4236 static hashval_t
4237 type_hash_hash (const void *item)
4238 {
4239   return ((const struct type_hash *) item)->hash;
4240 }
4241
4242 /* Look in the type hash table for a type isomorphic to TYPE.
4243    If one is found, return it.  Otherwise return 0.  */
4244
4245 tree
4246 type_hash_lookup (hashval_t hashcode, tree type)
4247 {
4248   struct type_hash *h, in;
4249
4250   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
4251      must call that routine before comparing TYPE_ALIGNs.  */
4252   layout_type (type);
4253
4254   in.hash = hashcode;
4255   in.type = type;
4256
4257   h = htab_find_with_hash (type_hash_table, &in, hashcode);
4258   if (h)
4259     return h->type;
4260   return NULL_TREE;
4261 }
4262
4263 /* Add an entry to the type-hash-table
4264    for a type TYPE whose hash code is HASHCODE.  */
4265
4266 void
4267 type_hash_add (hashval_t hashcode, tree type)
4268 {
4269   struct type_hash *h;
4270   void **loc;
4271
4272   h = ggc_alloc (sizeof (struct type_hash));
4273   h->hash = hashcode;
4274   h->type = type;
4275   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
4276   *(struct type_hash **) loc = h;
4277 }
4278
4279 /* Given TYPE, and HASHCODE its hash code, return the canonical
4280    object for an identical type if one already exists.
4281    Otherwise, return TYPE, and record it as the canonical object.
4282
4283    To use this function, first create a type of the sort you want.
4284    Then compute its hash code from the fields of the type that
4285    make it different from other similar types.
4286    Then call this function and use the value.  */
4287
4288 tree
4289 type_hash_canon (unsigned int hashcode, tree type)
4290 {
4291   tree t1;
4292
4293   /* The hash table only contains main variants, so ensure that's what we're
4294      being passed.  */
4295   gcc_assert (TYPE_MAIN_VARIANT (type) == type);
4296
4297   if (!lang_hooks.types.hash_types)
4298     return type;
4299
4300   /* See if the type is in the hash table already.  If so, return it.
4301      Otherwise, add the type.  */
4302   t1 = type_hash_lookup (hashcode, type);
4303   if (t1 != 0)
4304     {
4305 #ifdef GATHER_STATISTICS
4306       tree_node_counts[(int) t_kind]--;
4307       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
4308 #endif
4309       return t1;
4310     }
4311   else
4312     {
4313       type_hash_add (hashcode, type);
4314       return type;
4315     }
4316 }
4317
4318 /* See if the data pointed to by the type hash table is marked.  We consider
4319    it marked if the type is marked or if a debug type number or symbol
4320    table entry has been made for the type.  This reduces the amount of
4321    debugging output and eliminates that dependency of the debug output on
4322    the number of garbage collections.  */
4323
4324 static int
4325 type_hash_marked_p (const void *p)
4326 {
4327   tree type = ((struct type_hash *) p)->type;
4328
4329   return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
4330 }
4331
4332 static void
4333 print_type_hash_statistics (void)
4334 {
4335   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
4336            (long) htab_size (type_hash_table),
4337            (long) htab_elements (type_hash_table),
4338            htab_collisions (type_hash_table));
4339 }
4340
4341 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
4342    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
4343    by adding the hash codes of the individual attributes.  */
4344
4345 unsigned int
4346 attribute_hash_list (tree list, hashval_t hashcode)
4347 {
4348   tree tail;
4349
4350   for (tail = list; tail; tail = TREE_CHAIN (tail))
4351     /* ??? Do we want to add in TREE_VALUE too? */
4352     hashcode = iterative_hash_object
4353       (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode);
4354   return hashcode;
4355 }
4356
4357 /* Given two lists of attributes, return true if list l2 is
4358    equivalent to l1.  */
4359
4360 int
4361 attribute_list_equal (tree l1, tree l2)
4362 {
4363   return attribute_list_contained (l1, l2)
4364          && attribute_list_contained (l2, l1);
4365 }
4366
4367 /* Given two lists of attributes, return true if list L2 is
4368    completely contained within L1.  */
4369 /* ??? This would be faster if attribute names were stored in a canonicalized
4370    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
4371    must be used to show these elements are equivalent (which they are).  */
4372 /* ??? It's not clear that attributes with arguments will always be handled
4373    correctly.  */
4374
4375 int
4376 attribute_list_contained (tree l1, tree l2)
4377 {
4378   tree t1, t2;
4379
4380   /* First check the obvious, maybe the lists are identical.  */
4381   if (l1 == l2)
4382     return 1;
4383
4384   /* Maybe the lists are similar.  */
4385   for (t1 = l1, t2 = l2;
4386        t1 != 0 && t2 != 0
4387         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
4388         && TREE_VALUE (t1) == TREE_VALUE (t2);
4389        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
4390
4391   /* Maybe the lists are equal.  */
4392   if (t1 == 0 && t2 == 0)
4393     return 1;
4394
4395   for (; t2 != 0; t2 = TREE_CHAIN (t2))
4396     {
4397       tree attr;
4398       for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
4399            attr != NULL_TREE;
4400            attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
4401                                     TREE_CHAIN (attr)))
4402         {
4403           if (TREE_VALUE (t2) != NULL
4404               && TREE_CODE (TREE_VALUE (t2)) == TREE_LIST
4405               && TREE_VALUE (attr) != NULL
4406               && TREE_CODE (TREE_VALUE (attr)) == TREE_LIST)
4407             {
4408               if (simple_cst_list_equal (TREE_VALUE (t2),
4409                                          TREE_VALUE (attr)) == 1)
4410                 break;
4411             }
4412           else if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
4413             break;
4414         }
4415
4416       if (attr == 0)
4417         return 0;
4418     }
4419
4420   return 1;
4421 }
4422
4423 /* Given two lists of types
4424    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
4425    return 1 if the lists contain the same types in the same order.
4426    Also, the TREE_PURPOSEs must match.  */
4427
4428 int
4429 type_list_equal (tree l1, tree l2)
4430 {
4431   tree t1, t2;
4432
4433   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
4434     if (TREE_VALUE (t1) != TREE_VALUE (t2)
4435         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
4436             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
4437                   && (TREE_TYPE (TREE_PURPOSE (t1))
4438                       == TREE_TYPE (TREE_PURPOSE (t2))))))
4439       return 0;
4440
4441   return t1 == t2;
4442 }
4443
4444 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
4445    given by TYPE.  If the argument list accepts variable arguments,
4446    then this function counts only the ordinary arguments.  */
4447
4448 int
4449 type_num_arguments (tree type)
4450 {
4451   int i = 0;
4452   tree t;
4453
4454   for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
4455     /* If the function does not take a variable number of arguments,
4456        the last element in the list will have type `void'.  */
4457     if (VOID_TYPE_P (TREE_VALUE (t)))
4458       break;
4459     else
4460       ++i;
4461
4462   return i;
4463 }
4464
4465 /* Nonzero if integer constants T1 and T2
4466    represent the same constant value.  */
4467
4468 int
4469 tree_int_cst_equal (tree t1, tree t2)
4470 {
4471   if (t1 == t2)
4472     return 1;
4473
4474   if (t1 == 0 || t2 == 0)
4475     return 0;
4476
4477   if (TREE_CODE (t1) == INTEGER_CST
4478       && TREE_CODE (t2) == INTEGER_CST
4479       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
4480       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
4481     return 1;
4482
4483   return 0;
4484 }
4485
4486 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
4487    The precise way of comparison depends on their data type.  */
4488
4489 int
4490 tree_int_cst_lt (tree t1, tree t2)
4491 {
4492   if (t1 == t2)
4493     return 0;
4494
4495   if (TYPE_UNSIGNED (TREE_TYPE (t1)) != TYPE_UNSIGNED (TREE_TYPE (t2)))
4496     {
4497       int t1_sgn = tree_int_cst_sgn (t1);
4498       int t2_sgn = tree_int_cst_sgn (t2);
4499
4500       if (t1_sgn < t2_sgn)
4501         return 1;
4502       else if (t1_sgn > t2_sgn)
4503         return 0;
4504       /* Otherwise, both are non-negative, so we compare them as
4505          unsigned just in case one of them would overflow a signed
4506          type.  */
4507     }
4508   else if (!TYPE_UNSIGNED (TREE_TYPE (t1)))
4509     return INT_CST_LT (t1, t2);
4510
4511   return INT_CST_LT_UNSIGNED (t1, t2);
4512 }
4513
4514 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
4515
4516 int
4517 tree_int_cst_compare (tree t1, tree t2)
4518 {
4519   if (tree_int_cst_lt (t1, t2))
4520     return -1;
4521   else if (tree_int_cst_lt (t2, t1))
4522     return 1;
4523   else
4524     return 0;
4525 }
4526
4527 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
4528    the host.  If POS is zero, the value can be represented in a single
4529    HOST_WIDE_INT.  If POS is nonzero, the value must be non-negative and can
4530    be represented in a single unsigned HOST_WIDE_INT.  */
4531
4532 int
4533 host_integerp (tree t, int pos)
4534 {
4535   return (TREE_CODE (t) == INTEGER_CST
4536           && ((TREE_INT_CST_HIGH (t) == 0
4537                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
4538               || (! pos && TREE_INT_CST_HIGH (t) == -1
4539                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
4540                   && !TYPE_UNSIGNED (TREE_TYPE (t)))
4541               || (pos && TREE_INT_CST_HIGH (t) == 0)));
4542 }
4543
4544 /* Return the HOST_WIDE_INT least significant bits of T if it is an
4545    INTEGER_CST and there is no overflow.  POS is nonzero if the result must
4546    be non-negative.  We must be able to satisfy the above conditions.  */
4547
4548 HOST_WIDE_INT
4549 tree_low_cst (tree t, int pos)
4550 {
4551   gcc_assert (host_integerp (t, pos));
4552   return TREE_INT_CST_LOW (t);
4553 }
4554
4555 /* Return the most significant bit of the integer constant T.  */
4556
4557 int
4558 tree_int_cst_msb (tree t)
4559 {
4560   int prec;
4561   HOST_WIDE_INT h;
4562   unsigned HOST_WIDE_INT l;
4563
4564   /* Note that using TYPE_PRECISION here is wrong.  We care about the
4565      actual bits, not the (arbitrary) range of the type.  */
4566   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
4567   rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
4568                  2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
4569   return (l & 1) == 1;
4570 }
4571
4572 /* Return an indication of the sign of the integer constant T.
4573    The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
4574    Note that -1 will never be returned if T's type is unsigned.  */
4575
4576 int
4577 tree_int_cst_sgn (tree t)
4578 {
4579   if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
4580     return 0;
4581   else if (TYPE_UNSIGNED (TREE_TYPE (t)))
4582     return 1;
4583   else if (TREE_INT_CST_HIGH (t) < 0)
4584     return -1;
4585   else
4586     return 1;
4587 }
4588
4589 /* Compare two constructor-element-type constants.  Return 1 if the lists
4590    are known to be equal; otherwise return 0.  */
4591
4592 int
4593 simple_cst_list_equal (tree l1, tree l2)
4594 {
4595   while (l1 != NULL_TREE && l2 != NULL_TREE)
4596     {
4597       if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
4598         return 0;
4599
4600       l1 = TREE_CHAIN (l1);
4601       l2 = TREE_CHAIN (l2);
4602     }
4603
4604   return l1 == l2;
4605 }
4606
4607 /* Return truthvalue of whether T1 is the same tree structure as T2.
4608    Return 1 if they are the same.
4609    Return 0 if they are understandably different.
4610    Return -1 if either contains tree structure not understood by
4611    this function.  */
4612
4613 int
4614 simple_cst_equal (tree t1, tree t2)
4615 {
4616   enum tree_code code1, code2;
4617   int cmp;
4618   int i;
4619
4620   if (t1 == t2)
4621     return 1;
4622   if (t1 == 0 || t2 == 0)
4623     return 0;
4624
4625   code1 = TREE_CODE (t1);
4626   code2 = TREE_CODE (t2);
4627
4628   if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
4629     {
4630       if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
4631           || code2 == NON_LVALUE_EXPR)
4632         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4633       else
4634         return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
4635     }
4636
4637   else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
4638            || code2 == NON_LVALUE_EXPR)
4639     return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
4640
4641   if (code1 != code2)
4642     return 0;
4643
4644   switch (code1)
4645     {
4646     case INTEGER_CST:
4647       return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
4648               && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
4649
4650     case REAL_CST:
4651       return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
4652
4653     case STRING_CST:
4654       return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
4655               && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
4656                          TREE_STRING_LENGTH (t1)));
4657
4658     case CONSTRUCTOR:
4659       {
4660         unsigned HOST_WIDE_INT idx;
4661         VEC(constructor_elt, gc) *v1 = CONSTRUCTOR_ELTS (t1);
4662         VEC(constructor_elt, gc) *v2 = CONSTRUCTOR_ELTS (t2);
4663
4664         if (VEC_length (constructor_elt, v1) != VEC_length (constructor_elt, v2))
4665           return false;
4666
4667         for (idx = 0; idx < VEC_length (constructor_elt, v1); ++idx)
4668           /* ??? Should we handle also fields here? */
4669           if (!simple_cst_equal (VEC_index (constructor_elt, v1, idx)->value,
4670                                  VEC_index (constructor_elt, v2, idx)->value))
4671             return false;
4672         return true;
4673       }
4674
4675     case SAVE_EXPR:
4676       return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4677
4678     case CALL_EXPR:
4679       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4680       if (cmp <= 0)
4681         return cmp;
4682       return
4683         simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
4684
4685     case TARGET_EXPR:
4686       /* Special case: if either target is an unallocated VAR_DECL,
4687          it means that it's going to be unified with whatever the
4688          TARGET_EXPR is really supposed to initialize, so treat it
4689          as being equivalent to anything.  */
4690       if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
4691            && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
4692            && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
4693           || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
4694               && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
4695               && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
4696         cmp = 1;
4697       else
4698         cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4699
4700       if (cmp <= 0)
4701         return cmp;
4702
4703       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
4704
4705     case WITH_CLEANUP_EXPR:
4706       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4707       if (cmp <= 0)
4708         return cmp;
4709
4710       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
4711
4712     case COMPONENT_REF:
4713       if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
4714         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4715
4716       return 0;
4717
4718     case VAR_DECL:
4719     case PARM_DECL:
4720     case CONST_DECL:
4721     case FUNCTION_DECL:
4722       return 0;
4723
4724     default:
4725       break;
4726     }
4727
4728   /* This general rule works for most tree codes.  All exceptions should be
4729      handled above.  If this is a language-specific tree code, we can't
4730      trust what might be in the operand, so say we don't know
4731      the situation.  */
4732   if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
4733     return -1;
4734
4735   switch (TREE_CODE_CLASS (code1))
4736     {
4737     case tcc_unary:
4738     case tcc_binary:
4739     case tcc_comparison:
4740     case tcc_expression:
4741     case tcc_reference:
4742     case tcc_statement:
4743       cmp = 1;
4744       for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
4745         {
4746           cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
4747           if (cmp <= 0)
4748             return cmp;
4749         }
4750
4751       return cmp;
4752
4753     default:
4754       return -1;
4755     }
4756 }
4757
4758 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
4759    Return -1, 0, or 1 if the value of T is less than, equal to, or greater
4760    than U, respectively.  */
4761
4762 int
4763 compare_tree_int (tree t, unsigned HOST_WIDE_INT u)
4764 {
4765   if (tree_int_cst_sgn (t) < 0)
4766     return -1;
4767   else if (TREE_INT_CST_HIGH (t) != 0)
4768     return 1;
4769   else if (TREE_INT_CST_LOW (t) == u)
4770     return 0;
4771   else if (TREE_INT_CST_LOW (t) < u)
4772     return -1;
4773   else
4774     return 1;
4775 }
4776
4777 /* Return true if CODE represents an associative tree code.  Otherwise
4778    return false.  */
4779 bool
4780 associative_tree_code (enum tree_code code)
4781 {
4782   switch (code)
4783     {
4784     case BIT_IOR_EXPR:
4785     case BIT_AND_EXPR:
4786     case BIT_XOR_EXPR:
4787     case PLUS_EXPR:
4788     case MULT_EXPR:
4789     case MIN_EXPR:
4790     case MAX_EXPR:
4791       return true;
4792
4793     default:
4794       break;
4795     }
4796   return false;
4797 }
4798
4799 /* Return true if CODE represents a commutative tree code.  Otherwise
4800    return false.  */
4801 bool
4802 commutative_tree_code (enum tree_code code)
4803 {
4804   switch (code)
4805     {
4806     case PLUS_EXPR:
4807     case MULT_EXPR:
4808     case MIN_EXPR:
4809     case MAX_EXPR:
4810     case BIT_IOR_EXPR:
4811     case BIT_XOR_EXPR:
4812     case BIT_AND_EXPR:
4813     case NE_EXPR:
4814     case EQ_EXPR:
4815     case UNORDERED_EXPR:
4816     case ORDERED_EXPR:
4817     case UNEQ_EXPR:
4818     case LTGT_EXPR:
4819     case TRUTH_AND_EXPR:
4820     case TRUTH_XOR_EXPR:
4821     case TRUTH_OR_EXPR:
4822       return true;
4823
4824     default:
4825       break;
4826     }
4827   return false;
4828 }
4829
4830 /* Generate a hash value for an expression.  This can be used iteratively
4831    by passing a previous result as the "val" argument.
4832
4833    This function is intended to produce the same hash for expressions which
4834    would compare equal using operand_equal_p.  */
4835
4836 hashval_t
4837 iterative_hash_expr (tree t, hashval_t val)
4838 {
4839   int i;
4840   enum tree_code code;
4841   char class;
4842
4843   if (t == NULL_TREE)
4844     return iterative_hash_pointer (t, val);
4845
4846   code = TREE_CODE (t);
4847
4848   switch (code)
4849     {
4850     /* Alas, constants aren't shared, so we can't rely on pointer
4851        identity.  */
4852     case INTEGER_CST:
4853       val = iterative_hash_host_wide_int (TREE_INT_CST_LOW (t), val);
4854       return iterative_hash_host_wide_int (TREE_INT_CST_HIGH (t), val);
4855     case REAL_CST:
4856       {
4857         unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t));
4858
4859         return iterative_hash_hashval_t (val2, val);
4860       }
4861     case STRING_CST:
4862       return iterative_hash (TREE_STRING_POINTER (t),
4863                              TREE_STRING_LENGTH (t), val);
4864     case COMPLEX_CST:
4865       val = iterative_hash_expr (TREE_REALPART (t), val);
4866       return iterative_hash_expr (TREE_IMAGPART (t), val);
4867     case VECTOR_CST:
4868       return iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val);
4869
4870     case SSA_NAME:
4871     case VALUE_HANDLE:
4872       /* we can just compare by pointer.  */
4873       return iterative_hash_pointer (t, val);
4874
4875     case TREE_LIST:
4876       /* A list of expressions, for a CALL_EXPR or as the elements of a
4877          VECTOR_CST.  */
4878       for (; t; t = TREE_CHAIN (t))
4879         val = iterative_hash_expr (TREE_VALUE (t), val);
4880       return val;
4881     case CONSTRUCTOR:
4882       {
4883         unsigned HOST_WIDE_INT idx;
4884         tree field, value;
4885         FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (t), idx, field, value)
4886           {
4887             val = iterative_hash_expr (field, val);
4888             val = iterative_hash_expr (value, val);
4889           }
4890         return val;
4891       }
4892     case FUNCTION_DECL:
4893       /* When referring to a built-in FUNCTION_DECL, use the
4894          __builtin__ form.  Otherwise nodes that compare equal
4895          according to operand_equal_p might get different
4896          hash codes.  */
4897       if (DECL_BUILT_IN (t))
4898         {
4899           val = iterative_hash_pointer (built_in_decls[DECL_FUNCTION_CODE (t)],
4900                                       val);
4901           return val;
4902         }
4903       /* else FALL THROUGH */
4904     default:
4905       class = TREE_CODE_CLASS (code);
4906
4907       if (class == tcc_declaration)
4908         {
4909           /* DECL's have a unique ID */
4910           val = iterative_hash_host_wide_int (DECL_UID (t), val);
4911         }
4912       else
4913         {
4914           gcc_assert (IS_EXPR_CODE_CLASS (class));
4915
4916           val = iterative_hash_object (code, val);
4917
4918           /* Don't hash the type, that can lead to having nodes which
4919              compare equal according to operand_equal_p, but which
4920              have different hash codes.  */
4921           if (code == NOP_EXPR
4922               || code == CONVERT_EXPR
4923               || code == NON_LVALUE_EXPR)
4924             {
4925               /* Make sure to include signness in the hash computation.  */
4926               val += TYPE_UNSIGNED (TREE_TYPE (t));
4927               val = iterative_hash_expr (TREE_OPERAND (t, 0), val);
4928             }
4929
4930           else if (commutative_tree_code (code))
4931             {
4932               /* It's a commutative expression.  We want to hash it the same
4933                  however it appears.  We do this by first hashing both operands
4934                  and then rehashing based on the order of their independent
4935                  hashes.  */
4936               hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
4937               hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0);
4938               hashval_t t;
4939
4940               if (one > two)
4941                 t = one, one = two, two = t;
4942
4943               val = iterative_hash_hashval_t (one, val);
4944               val = iterative_hash_hashval_t (two, val);
4945             }
4946           else
4947             for (i = TREE_CODE_LENGTH (code) - 1; i >= 0; --i)
4948               val = iterative_hash_expr (TREE_OPERAND (t, i), val);
4949         }
4950       return val;
4951       break;
4952     }
4953 }
4954 \f
4955 /* Constructors for pointer, array and function types.
4956    (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
4957    constructed by language-dependent code, not here.)  */
4958
4959 /* Construct, lay out and return the type of pointers to TO_TYPE with
4960    mode MODE.  If CAN_ALIAS_ALL is TRUE, indicate this type can
4961    reference all of memory. If such a type has already been
4962    constructed, reuse it.  */
4963
4964 tree
4965 build_pointer_type_for_mode (tree to_type, enum machine_mode mode,
4966                              bool can_alias_all)
4967 {
4968   tree t;
4969
4970   if (to_type == error_mark_node)
4971     return error_mark_node;
4972
4973   /* In some cases, languages will have things that aren't a POINTER_TYPE
4974      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_POINTER_TO.
4975      In that case, return that type without regard to the rest of our
4976      operands.
4977
4978      ??? This is a kludge, but consistent with the way this function has
4979      always operated and there doesn't seem to be a good way to avoid this
4980      at the moment.  */
4981   if (TYPE_POINTER_TO (to_type) != 0
4982       && TREE_CODE (TYPE_POINTER_TO (to_type)) != POINTER_TYPE)
4983     return TYPE_POINTER_TO (to_type);
4984
4985   /* First, if we already have a type for pointers to TO_TYPE and it's
4986      the proper mode, use it.  */
4987   for (t = TYPE_POINTER_TO (to_type); t; t = TYPE_NEXT_PTR_TO (t))
4988     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4989       return t;
4990
4991   t = make_node (POINTER_TYPE);
4992
4993   TREE_TYPE (t) = to_type;
4994   TYPE_MODE (t) = mode;
4995   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4996   TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
4997   TYPE_POINTER_TO (to_type) = t;
4998
4999   /* Lay out the type.  This function has many callers that are concerned
5000      with expression-construction, and this simplifies them all.  */
5001   layout_type (t);
5002
5003   return t;
5004 }
5005
5006 /* By default build pointers in ptr_mode.  */
5007
5008 tree
5009 build_pointer_type (tree to_type)
5010 {
5011   return build_pointer_type_for_mode (to_type, ptr_mode, false);
5012 }
5013
5014 /* Same as build_pointer_type_for_mode, but for REFERENCE_TYPE.  */
5015
5016 tree
5017 build_reference_type_for_mode (tree to_type, enum machine_mode mode,
5018                                bool can_alias_all)
5019 {
5020   tree t;
5021
5022   /* In some cases, languages will have things that aren't a REFERENCE_TYPE
5023      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_REFERENCE_TO.
5024      In that case, return that type without regard to the rest of our
5025      operands.
5026
5027      ??? This is a kludge, but consistent with the way this function has
5028      always operated and there doesn't seem to be a good way to avoid this
5029      at the moment.  */
5030   if (TYPE_REFERENCE_TO (to_type) != 0
5031       && TREE_CODE (TYPE_REFERENCE_TO (to_type)) != REFERENCE_TYPE)
5032     return TYPE_REFERENCE_TO (to_type);
5033
5034   /* First, if we already have a type for pointers to TO_TYPE and it's
5035      the proper mode, use it.  */
5036   for (t = TYPE_REFERENCE_TO (to_type); t; t = TYPE_NEXT_REF_TO (t))
5037     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
5038       return t;
5039
5040   t = make_node (REFERENCE_TYPE);
5041
5042   TREE_TYPE (t) = to_type;
5043   TYPE_MODE (t) = mode;
5044   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
5045   TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
5046   TYPE_REFERENCE_TO (to_type) = t;
5047
5048   layout_type (t);
5049
5050   return t;
5051 }
5052
5053
5054 /* Build the node for the type of references-to-TO_TYPE by default
5055    in ptr_mode.  */
5056
5057 tree
5058 build_reference_type (tree to_type)
5059 {
5060   return build_reference_type_for_mode (to_type, ptr_mode, false);
5061 }
5062
5063 /* Build a type that is compatible with t but has no cv quals anywhere
5064    in its type, thus
5065
5066    const char *const *const *  ->  char ***.  */
5067
5068 tree
5069 build_type_no_quals (tree t)
5070 {
5071   switch (TREE_CODE (t))
5072     {
5073     case POINTER_TYPE:
5074       return build_pointer_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
5075                                           TYPE_MODE (t),
5076                                           TYPE_REF_CAN_ALIAS_ALL (t));
5077     case REFERENCE_TYPE:
5078       return
5079         build_reference_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
5080                                        TYPE_MODE (t),
5081                                        TYPE_REF_CAN_ALIAS_ALL (t));
5082     default:
5083       return TYPE_MAIN_VARIANT (t);
5084     }
5085 }
5086
5087 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
5088    MAXVAL should be the maximum value in the domain
5089    (one less than the length of the array).
5090
5091    The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
5092    We don't enforce this limit, that is up to caller (e.g. language front end).
5093    The limit exists because the result is a signed type and we don't handle
5094    sizes that use more than one HOST_WIDE_INT.  */
5095
5096 tree
5097 build_index_type (tree maxval)
5098 {
5099   tree itype = make_node (INTEGER_TYPE);
5100
5101   TREE_TYPE (itype) = sizetype;
5102   TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
5103   TYPE_MIN_VALUE (itype) = size_zero_node;
5104   TYPE_MAX_VALUE (itype) = fold_convert (sizetype, maxval);
5105   TYPE_MODE (itype) = TYPE_MODE (sizetype);
5106   TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
5107   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
5108   TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
5109   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
5110
5111   if (host_integerp (maxval, 1))
5112     return type_hash_canon (tree_low_cst (maxval, 1), itype);
5113   else
5114     return itype;
5115 }
5116
5117 /* Builds a signed or unsigned integer type of precision PRECISION.
5118    Used for C bitfields whose precision does not match that of
5119    built-in target types.  */
5120 tree
5121 build_nonstandard_integer_type (unsigned HOST_WIDE_INT precision,
5122                                 int unsignedp)
5123 {
5124   tree itype = make_node (INTEGER_TYPE);
5125
5126   TYPE_PRECISION (itype) = precision;
5127
5128   if (unsignedp)
5129     fixup_unsigned_type (itype);
5130   else
5131     fixup_signed_type (itype);
5132
5133   if (host_integerp (TYPE_MAX_VALUE (itype), 1))
5134     return type_hash_canon (tree_low_cst (TYPE_MAX_VALUE (itype), 1), itype);
5135
5136   return itype;
5137 }
5138
5139 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
5140    ENUMERAL_TYPE or BOOLEAN_TYPE), with low bound LOWVAL and
5141    high bound HIGHVAL.  If TYPE is NULL, sizetype is used.  */
5142
5143 tree
5144 build_range_type (tree type, tree lowval, tree highval)
5145 {
5146   tree itype = make_node (INTEGER_TYPE);
5147
5148   TREE_TYPE (itype) = type;
5149   if (type == NULL_TREE)
5150     type = sizetype;
5151
5152   TYPE_MIN_VALUE (itype) = fold_convert (type, lowval);
5153   TYPE_MAX_VALUE (itype) = highval ? fold_convert (type, highval) : NULL;
5154
5155   TYPE_PRECISION (itype) = TYPE_PRECISION (type);
5156   TYPE_MODE (itype) = TYPE_MODE (type);
5157   TYPE_SIZE (itype) = TYPE_SIZE (type);
5158   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type);
5159   TYPE_ALIGN (itype) = TYPE_ALIGN (type);
5160   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type);
5161
5162   if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0))
5163     return type_hash_canon (tree_low_cst (highval, 0)
5164                             - tree_low_cst (lowval, 0),
5165                             itype);
5166   else
5167     return itype;
5168 }
5169
5170 /* Just like build_index_type, but takes lowval and highval instead
5171    of just highval (maxval).  */
5172
5173 tree
5174 build_index_2_type (tree lowval, tree highval)
5175 {
5176   return build_range_type (sizetype, lowval, highval);
5177 }
5178
5179 /* Construct, lay out and return the type of arrays of elements with ELT_TYPE
5180    and number of elements specified by the range of values of INDEX_TYPE.
5181    If such a type has already been constructed, reuse it.  */
5182
5183 tree
5184 build_array_type (tree elt_type, tree index_type)
5185 {
5186   tree t;
5187   hashval_t hashcode = 0;
5188
5189   if (TREE_CODE (elt_type) == FUNCTION_TYPE)
5190     {
5191       error ("arrays of functions are not meaningful");
5192       elt_type = integer_type_node;
5193     }
5194
5195   t = make_node (ARRAY_TYPE);
5196   TREE_TYPE (t) = elt_type;
5197   TYPE_DOMAIN (t) = index_type;
5198
5199   if (index_type == 0)
5200     {
5201       tree save = t;
5202       hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode);
5203       t = type_hash_canon (hashcode, t);
5204       if (save == t)
5205         layout_type (t);
5206       return t;
5207     }
5208
5209   hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode);
5210   hashcode = iterative_hash_object (TYPE_HASH (index_type), hashcode);
5211   t = type_hash_canon (hashcode, t);
5212
5213   if (!COMPLETE_TYPE_P (t))
5214     layout_type (t);
5215   return t;
5216 }
5217
5218 /* Return the TYPE of the elements comprising
5219    the innermost dimension of ARRAY.  */
5220
5221 tree
5222 get_inner_array_type (tree array)
5223 {
5224   tree type = TREE_TYPE (array);
5225
5226   while (TREE_CODE (type) == ARRAY_TYPE)
5227     type = TREE_TYPE (type);
5228
5229   return type;
5230 }
5231
5232 /* Construct, lay out and return
5233    the type of functions returning type VALUE_TYPE
5234    given arguments of types ARG_TYPES.
5235    ARG_TYPES is a chain of TREE_LIST nodes whose TREE_VALUEs
5236    are data type nodes for the arguments of the function.
5237    If such a type has already been constructed, reuse it.  */
5238
5239 tree
5240 build_function_type (tree value_type, tree arg_types)
5241 {
5242   tree t;
5243   hashval_t hashcode = 0;
5244
5245   if (TREE_CODE (value_type) == FUNCTION_TYPE)
5246     {
5247       error ("function return type cannot be function");
5248       value_type = integer_type_node;
5249     }
5250
5251   /* Make a node of the sort we want.  */
5252   t = make_node (FUNCTION_TYPE);
5253   TREE_TYPE (t) = value_type;
5254   TYPE_ARG_TYPES (t) = arg_types;
5255
5256   /* If we already have such a type, use the old one.  */
5257   hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode);
5258   hashcode = type_hash_list (arg_types, hashcode);
5259   t = type_hash_canon (hashcode, t);
5260
5261   if (!COMPLETE_TYPE_P (t))
5262     layout_type (t);
5263   return t;
5264 }
5265
5266 /* Build a function type.  The RETURN_TYPE is the type returned by the
5267    function.  If additional arguments are provided, they are
5268    additional argument types.  The list of argument types must always
5269    be terminated by NULL_TREE.  */
5270
5271 tree
5272 build_function_type_list (tree return_type, ...)
5273 {
5274   tree t, args, last;
5275   va_list p;
5276
5277   va_start (p, return_type);
5278
5279   t = va_arg (p, tree);
5280   for (args = NULL_TREE; t != NULL_TREE; t = va_arg (p, tree))
5281     args = tree_cons (NULL_TREE, t, args);
5282
5283   if (args == NULL_TREE)
5284     args = void_list_node;
5285   else
5286     {
5287       last = args;
5288       args = nreverse (args);
5289       TREE_CHAIN (last) = void_list_node;
5290     }
5291   args = build_function_type (return_type, args);
5292
5293   va_end (p);
5294   return args;
5295 }
5296
5297 /* Build a METHOD_TYPE for a member of BASETYPE.  The RETTYPE (a TYPE)
5298    and ARGTYPES (a TREE_LIST) are the return type and arguments types
5299    for the method.  An implicit additional parameter (of type
5300    pointer-to-BASETYPE) is added to the ARGTYPES.  */
5301
5302 tree
5303 build_method_type_directly (tree basetype,
5304                             tree rettype,
5305                             tree argtypes)
5306 {
5307   tree t;
5308   tree ptype;
5309   int hashcode = 0;
5310
5311   /* Make a node of the sort we want.  */
5312   t = make_node (METHOD_TYPE);
5313
5314   TYPE_METHOD_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
5315   TREE_TYPE (t) = rettype;
5316   ptype = build_pointer_type (basetype);
5317
5318   /* The actual arglist for this function includes a "hidden" argument
5319      which is "this".  Put it into the list of argument types.  */
5320   argtypes = tree_cons (NULL_TREE, ptype, argtypes);
5321   TYPE_ARG_TYPES (t) = argtypes;
5322
5323   /* If we already have such a type, use the old one.  */
5324   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
5325   hashcode = iterative_hash_object (TYPE_HASH (rettype), hashcode);
5326   hashcode = type_hash_list (argtypes, hashcode);
5327   t = type_hash_canon (hashcode, t);
5328
5329   if (!COMPLETE_TYPE_P (t))
5330     layout_type (t);
5331
5332   return t;
5333 }
5334
5335 /* Construct, lay out and return the type of methods belonging to class
5336    BASETYPE and whose arguments and values are described by TYPE.
5337    If that type exists already, reuse it.
5338    TYPE must be a FUNCTION_TYPE node.  */
5339
5340 tree
5341 build_method_type (tree basetype, tree type)
5342 {
5343   gcc_assert (TREE_CODE (type) == FUNCTION_TYPE);
5344
5345   return build_method_type_directly (basetype,
5346                                      TREE_TYPE (type),
5347                                      TYPE_ARG_TYPES (type));
5348 }
5349
5350 /* Construct, lay out and return the type of offsets to a value
5351    of type TYPE, within an object of type BASETYPE.
5352    If a suitable offset type exists already, reuse it.  */
5353
5354 tree
5355 build_offset_type (tree basetype, tree type)
5356 {
5357   tree t;
5358   hashval_t hashcode = 0;
5359
5360   /* Make a node of the sort we want.  */
5361   t = make_node (OFFSET_TYPE);
5362
5363   TYPE_OFFSET_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
5364   TREE_TYPE (t) = type;
5365
5366   /* If we already have such a type, use the old one.  */
5367   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
5368   hashcode = iterative_hash_object (TYPE_HASH (type), hashcode);
5369   t = type_hash_canon (hashcode, t);
5370
5371   if (!COMPLETE_TYPE_P (t))
5372     layout_type (t);
5373
5374   return t;
5375 }
5376
5377 /* Create a complex type whose components are COMPONENT_TYPE.  */
5378
5379 tree
5380 build_complex_type (tree component_type)
5381 {
5382   tree t;
5383   hashval_t hashcode;
5384
5385   /* Make a node of the sort we want.  */
5386   t = make_node (COMPLEX_TYPE);
5387
5388   TREE_TYPE (t) = TYPE_MAIN_VARIANT (component_type);
5389
5390   /* If we already have such a type, use the old one.  */
5391   hashcode = iterative_hash_object (TYPE_HASH (component_type), 0);
5392   t = type_hash_canon (hashcode, t);
5393
5394   if (!COMPLETE_TYPE_P (t))
5395     layout_type (t);
5396
5397   /* If we are writing Dwarf2 output we need to create a name,
5398      since complex is a fundamental type.  */
5399   if ((write_symbols == DWARF2_DEBUG || write_symbols == VMS_AND_DWARF2_DEBUG)
5400       && ! TYPE_NAME (t))
5401     {
5402       const char *name;
5403       if (component_type == char_type_node)
5404         name = "complex char";
5405       else if (component_type == signed_char_type_node)
5406         name = "complex signed char";
5407       else if (component_type == unsigned_char_type_node)
5408         name = "complex unsigned char";
5409       else if (component_type == short_integer_type_node)
5410         name = "complex short int";
5411       else if (component_type == short_unsigned_type_node)
5412         name = "complex short unsigned int";
5413       else if (component_type == integer_type_node)
5414         name = "complex int";
5415       else if (component_type == unsigned_type_node)
5416         name = "complex unsigned int";
5417       else if (component_type == long_integer_type_node)
5418         name = "complex long int";
5419       else if (component_type == long_unsigned_type_node)
5420         name = "complex long unsigned int";
5421       else if (component_type == long_long_integer_type_node)
5422         name = "complex long long int";
5423       else if (component_type == long_long_unsigned_type_node)
5424         name = "complex long long unsigned int";
5425       else
5426         name = 0;
5427
5428       if (name != 0)
5429         TYPE_NAME (t) = get_identifier (name);
5430     }
5431
5432   return build_qualified_type (t, TYPE_QUALS (component_type));
5433 }
5434 \f
5435 /* Return OP, stripped of any conversions to wider types as much as is safe.
5436    Converting the value back to OP's type makes a value equivalent to OP.
5437
5438    If FOR_TYPE is nonzero, we return a value which, if converted to
5439    type FOR_TYPE, would be equivalent to converting OP to type FOR_TYPE.
5440
5441    If FOR_TYPE is nonzero, unaligned bit-field references may be changed to the
5442    narrowest type that can hold the value, even if they don't exactly fit.
5443    Otherwise, bit-field references are changed to a narrower type
5444    only if they can be fetched directly from memory in that type.
5445
5446    OP must have integer, real or enumeral type.  Pointers are not allowed!
5447
5448    There are some cases where the obvious value we could return
5449    would regenerate to OP if converted to OP's type,
5450    but would not extend like OP to wider types.
5451    If FOR_TYPE indicates such extension is contemplated, we eschew such values.
5452    For example, if OP is (unsigned short)(signed char)-1,
5453    we avoid returning (signed char)-1 if FOR_TYPE is int,
5454    even though extending that to an unsigned short would regenerate OP,
5455    since the result of extending (signed char)-1 to (int)
5456    is different from (int) OP.  */
5457
5458 tree
5459 get_unwidened (tree op, tree for_type)
5460 {
5461   /* Set UNS initially if converting OP to FOR_TYPE is a zero-extension.  */
5462   tree type = TREE_TYPE (op);
5463   unsigned final_prec
5464     = TYPE_PRECISION (for_type != 0 ? for_type : type);
5465   int uns
5466     = (for_type != 0 && for_type != type
5467        && final_prec > TYPE_PRECISION (type)
5468        && TYPE_UNSIGNED (type));
5469   tree win = op;
5470
5471   while (TREE_CODE (op) == NOP_EXPR
5472          || TREE_CODE (op) == CONVERT_EXPR)
5473     {
5474       int bitschange;
5475
5476       /* TYPE_PRECISION on vector types has different meaning
5477          (TYPE_VECTOR_SUBPARTS) and casts from vectors are view conversions,
5478          so avoid them here.  */
5479       if (TREE_CODE (TREE_TYPE (TREE_OPERAND (op, 0))) == VECTOR_TYPE)
5480         break;
5481
5482       bitschange = TYPE_PRECISION (TREE_TYPE (op))
5483                    - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0)));
5484
5485       /* Truncations are many-one so cannot be removed.
5486          Unless we are later going to truncate down even farther.  */
5487       if (bitschange < 0
5488           && final_prec > TYPE_PRECISION (TREE_TYPE (op)))
5489         break;
5490
5491       /* See what's inside this conversion.  If we decide to strip it,
5492          we will set WIN.  */
5493       op = TREE_OPERAND (op, 0);
5494
5495       /* If we have not stripped any zero-extensions (uns is 0),
5496          we can strip any kind of extension.
5497          If we have previously stripped a zero-extension,
5498          only zero-extensions can safely be stripped.
5499          Any extension can be stripped if the bits it would produce
5500          are all going to be discarded later by truncating to FOR_TYPE.  */
5501
5502       if (bitschange > 0)
5503         {
5504           if (! uns || final_prec <= TYPE_PRECISION (TREE_TYPE (op)))
5505             win = op;
5506           /* TYPE_UNSIGNED says whether this is a zero-extension.
5507              Let's avoid computing it if it does not affect WIN
5508              and if UNS will not be needed again.  */
5509           if ((uns
5510                || TREE_CODE (op) == NOP_EXPR
5511                || TREE_CODE (op) == CONVERT_EXPR)
5512               && TYPE_UNSIGNED (TREE_TYPE (op)))
5513             {
5514               uns = 1;
5515               win = op;
5516             }
5517         }
5518     }
5519
5520   if (TREE_CODE (op) == COMPONENT_REF
5521       /* Since type_for_size always gives an integer type.  */
5522       && TREE_CODE (type) != REAL_TYPE
5523       /* Don't crash if field not laid out yet.  */
5524       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
5525       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
5526     {
5527       unsigned int innerprec
5528         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
5529       int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
5530                        || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
5531       type = lang_hooks.types.type_for_size (innerprec, unsignedp);
5532
5533       /* We can get this structure field in the narrowest type it fits in.
5534          If FOR_TYPE is 0, do this only for a field that matches the
5535          narrower type exactly and is aligned for it
5536          The resulting extension to its nominal type (a fullword type)
5537          must fit the same conditions as for other extensions.  */
5538
5539       if (type != 0
5540           && INT_CST_LT_UNSIGNED (TYPE_SIZE (type), TYPE_SIZE (TREE_TYPE (op)))
5541           && (for_type || ! DECL_BIT_FIELD (TREE_OPERAND (op, 1)))
5542           && (! uns || final_prec <= innerprec || unsignedp))
5543         {
5544           win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
5545                         TREE_OPERAND (op, 1), NULL_TREE);
5546           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
5547           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
5548         }
5549     }
5550
5551   return win;
5552 }
5553 \f
5554 /* Return OP or a simpler expression for a narrower value
5555    which can be sign-extended or zero-extended to give back OP.
5556    Store in *UNSIGNEDP_PTR either 1 if the value should be zero-extended
5557    or 0 if the value should be sign-extended.  */
5558
5559 tree
5560 get_narrower (tree op, int *unsignedp_ptr)
5561 {
5562   int uns = 0;
5563   int first = 1;
5564   tree win = op;
5565   bool integral_p = INTEGRAL_TYPE_P (TREE_TYPE (op));
5566
5567   while (TREE_CODE (op) == NOP_EXPR)
5568     {
5569       int bitschange
5570         = (TYPE_PRECISION (TREE_TYPE (op))
5571            - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0))));
5572
5573       /* Truncations are many-one so cannot be removed.  */
5574       if (bitschange < 0)
5575         break;
5576
5577       /* See what's inside this conversion.  If we decide to strip it,
5578          we will set WIN.  */
5579
5580       if (bitschange > 0)
5581         {
5582           op = TREE_OPERAND (op, 0);
5583           /* An extension: the outermost one can be stripped,
5584              but remember whether it is zero or sign extension.  */
5585           if (first)
5586             uns = TYPE_UNSIGNED (TREE_TYPE (op));
5587           /* Otherwise, if a sign extension has been stripped,
5588              only sign extensions can now be stripped;
5589              if a zero extension has been stripped, only zero-extensions.  */
5590           else if (uns != TYPE_UNSIGNED (TREE_TYPE (op)))
5591             break;
5592           first = 0;
5593         }
5594       else /* bitschange == 0 */
5595         {
5596           /* A change in nominal type can always be stripped, but we must
5597              preserve the unsignedness.  */
5598           if (first)
5599             uns = TYPE_UNSIGNED (TREE_TYPE (op));
5600           first = 0;
5601           op = TREE_OPERAND (op, 0);
5602           /* Keep trying to narrow, but don't assign op to win if it
5603              would turn an integral type into something else.  */
5604           if (INTEGRAL_TYPE_P (TREE_TYPE (op)) != integral_p)
5605             continue;
5606         }
5607
5608       win = op;
5609     }
5610
5611   if (TREE_CODE (op) == COMPONENT_REF
5612       /* Since type_for_size always gives an integer type.  */
5613       && TREE_CODE (TREE_TYPE (op)) != REAL_TYPE
5614       /* Ensure field is laid out already.  */
5615       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
5616       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
5617     {
5618       unsigned HOST_WIDE_INT innerprec
5619         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
5620       int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
5621                        || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
5622       tree type = lang_hooks.types.type_for_size (innerprec, unsignedp);
5623
5624       /* We can get this structure field in a narrower type that fits it,
5625          but the resulting extension to its nominal type (a fullword type)
5626          must satisfy the same conditions as for other extensions.
5627
5628          Do this only for fields that are aligned (not bit-fields),
5629          because when bit-field insns will be used there is no
5630          advantage in doing this.  */
5631
5632       if (innerprec < TYPE_PRECISION (TREE_TYPE (op))
5633           && ! DECL_BIT_FIELD (TREE_OPERAND (op, 1))
5634           && (first || uns == DECL_UNSIGNED (TREE_OPERAND (op, 1)))
5635           && type != 0)
5636         {
5637           if (first)
5638             uns = DECL_UNSIGNED (TREE_OPERAND (op, 1));
5639           win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
5640                         TREE_OPERAND (op, 1), NULL_TREE);
5641           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
5642           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
5643         }
5644     }
5645   *unsignedp_ptr = uns;
5646   return win;
5647 }
5648 \f
5649 /* Nonzero if integer constant C has a value that is permissible
5650    for type TYPE (an INTEGER_TYPE).  */
5651
5652 int
5653 int_fits_type_p (tree c, tree type)
5654 {
5655   tree type_low_bound = TYPE_MIN_VALUE (type);
5656   tree type_high_bound = TYPE_MAX_VALUE (type);
5657   bool ok_for_low_bound, ok_for_high_bound;
5658   tree tmp;
5659
5660   /* If at least one bound of the type is a constant integer, we can check
5661      ourselves and maybe make a decision. If no such decision is possible, but
5662      this type is a subtype, try checking against that.  Otherwise, use
5663      force_fit_type, which checks against the precision.
5664
5665      Compute the status for each possibly constant bound, and return if we see
5666      one does not match. Use ok_for_xxx_bound for this purpose, assigning -1
5667      for "unknown if constant fits", 0 for "constant known *not* to fit" and 1
5668      for "constant known to fit".  */
5669
5670   /* Check if C >= type_low_bound.  */
5671   if (type_low_bound && TREE_CODE (type_low_bound) == INTEGER_CST)
5672     {
5673       if (tree_int_cst_lt (c, type_low_bound))
5674         return 0;
5675       ok_for_low_bound = true;
5676     }
5677   else
5678     ok_for_low_bound = false;
5679
5680   /* Check if c <= type_high_bound.  */
5681   if (type_high_bound && TREE_CODE (type_high_bound) == INTEGER_CST)
5682     {
5683       if (tree_int_cst_lt (type_high_bound, c))
5684         return 0;
5685       ok_for_high_bound = true;
5686     }
5687   else
5688     ok_for_high_bound = false;
5689
5690   /* If the constant fits both bounds, the result is known.  */
5691   if (ok_for_low_bound && ok_for_high_bound)
5692     return 1;
5693
5694   /* Perform some generic filtering which may allow making a decision
5695      even if the bounds are not constant.  First, negative integers
5696      never fit in unsigned types, */
5697   if (TYPE_UNSIGNED (type) && tree_int_cst_sgn (c) < 0)
5698     return 0;
5699
5700   /* Second, narrower types always fit in wider ones.  */
5701   if (TYPE_PRECISION (type) > TYPE_PRECISION (TREE_TYPE (c)))
5702     return 1;
5703
5704   /* Third, unsigned integers with top bit set never fit signed types.  */
5705   if (! TYPE_UNSIGNED (type)
5706       && TYPE_UNSIGNED (TREE_TYPE (c))
5707       && tree_int_cst_msb (c))
5708     return 0;
5709
5710   /* If we haven't been able to decide at this point, there nothing more we
5711      can check ourselves here.  Look at the base type if we have one and it
5712      has the same precision.  */
5713   if (TREE_CODE (type) == INTEGER_TYPE
5714       && TREE_TYPE (type) != 0
5715       && TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (type)))
5716     return int_fits_type_p (c, TREE_TYPE (type));
5717
5718   /* Or to force_fit_type, if nothing else.  */
5719   tmp = copy_node (c);
5720   TREE_TYPE (tmp) = type;
5721   tmp = force_fit_type (tmp, -1, false, false);
5722   return TREE_INT_CST_HIGH (tmp) == TREE_INT_CST_HIGH (c)
5723          && TREE_INT_CST_LOW (tmp) == TREE_INT_CST_LOW (c);
5724 }
5725
5726 /* Subprogram of following function.  Called by walk_tree.
5727
5728    Return *TP if it is an automatic variable or parameter of the
5729    function passed in as DATA.  */
5730
5731 static tree
5732 find_var_from_fn (tree *tp, int *walk_subtrees, void *data)
5733 {
5734   tree fn = (tree) data;
5735
5736   if (TYPE_P (*tp))
5737     *walk_subtrees = 0;
5738
5739   else if (DECL_P (*tp)
5740            && lang_hooks.tree_inlining.auto_var_in_fn_p (*tp, fn))
5741     return *tp;
5742
5743   return NULL_TREE;
5744 }
5745
5746 /* Returns true if T is, contains, or refers to a type with variable
5747    size.  For METHOD_TYPEs and FUNCTION_TYPEs we exclude the
5748    arguments, but not the return type.  If FN is nonzero, only return
5749    true if a modifier of the type or position of FN is a variable or
5750    parameter inside FN.
5751
5752    This concept is more general than that of C99 'variably modified types':
5753    in C99, a struct type is never variably modified because a VLA may not
5754    appear as a structure member.  However, in GNU C code like:
5755
5756      struct S { int i[f()]; };
5757
5758    is valid, and other languages may define similar constructs.  */
5759
5760 bool
5761 variably_modified_type_p (tree type, tree fn)
5762 {
5763   tree t;
5764
5765 /* Test if T is either variable (if FN is zero) or an expression containing
5766    a variable in FN.  */
5767 #define RETURN_TRUE_IF_VAR(T)                                           \
5768   do { tree _t = (T);                                                   \
5769     if (_t && _t != error_mark_node && TREE_CODE (_t) != INTEGER_CST    \
5770         && (!fn || walk_tree (&_t, find_var_from_fn, fn, NULL)))        \
5771       return true;  } while (0)
5772
5773   if (type == error_mark_node)
5774     return false;
5775
5776   /* If TYPE itself has variable size, it is variably modified.  */
5777   RETURN_TRUE_IF_VAR (TYPE_SIZE (type));
5778   RETURN_TRUE_IF_VAR (TYPE_SIZE_UNIT (type));
5779
5780   switch (TREE_CODE (type))
5781     {
5782     case POINTER_TYPE:
5783     case REFERENCE_TYPE:
5784     case VECTOR_TYPE:
5785       if (variably_modified_type_p (TREE_TYPE (type), fn))
5786         return true;
5787       break;
5788
5789     case FUNCTION_TYPE:
5790     case METHOD_TYPE:
5791       /* If TYPE is a function type, it is variably modified if the
5792          return type is variably modified.  */
5793       if (variably_modified_type_p (TREE_TYPE (type), fn))
5794           return true;
5795       break;
5796
5797     case INTEGER_TYPE:
5798     case REAL_TYPE:
5799     case ENUMERAL_TYPE:
5800     case BOOLEAN_TYPE:
5801       /* Scalar types are variably modified if their end points
5802          aren't constant.  */
5803       RETURN_TRUE_IF_VAR (TYPE_MIN_VALUE (type));
5804       RETURN_TRUE_IF_VAR (TYPE_MAX_VALUE (type));
5805       break;
5806
5807     case RECORD_TYPE:
5808     case UNION_TYPE:
5809     case QUAL_UNION_TYPE:
5810       /* We can't see if any of the fields are variably-modified by the
5811          definition we normally use, since that would produce infinite
5812          recursion via pointers.  */
5813       /* This is variably modified if some field's type is.  */
5814       for (t = TYPE_FIELDS (type); t; t = TREE_CHAIN (t))
5815         if (TREE_CODE (t) == FIELD_DECL)
5816           {
5817             RETURN_TRUE_IF_VAR (DECL_FIELD_OFFSET (t));
5818             RETURN_TRUE_IF_VAR (DECL_SIZE (t));
5819             RETURN_TRUE_IF_VAR (DECL_SIZE_UNIT (t));
5820
5821             if (TREE_CODE (type) == QUAL_UNION_TYPE)
5822               RETURN_TRUE_IF_VAR (DECL_QUALIFIER (t));
5823           }
5824         break;
5825
5826     case ARRAY_TYPE:
5827       /* Do not call ourselves to avoid infinite recursion.  This is
5828          variably modified if the element type is.  */
5829       RETURN_TRUE_IF_VAR (TYPE_SIZE (TREE_TYPE (type)));
5830       RETURN_TRUE_IF_VAR (TYPE_SIZE_UNIT (TREE_TYPE (type)));
5831       break;
5832
5833     default:
5834       break;
5835     }
5836
5837   /* The current language may have other cases to check, but in general,
5838      all other types are not variably modified.  */
5839   return lang_hooks.tree_inlining.var_mod_type_p (type, fn);
5840
5841 #undef RETURN_TRUE_IF_VAR
5842 }
5843
5844 /* Given a DECL or TYPE, return the scope in which it was declared, or
5845    NULL_TREE if there is no containing scope.  */
5846
5847 tree
5848 get_containing_scope (tree t)
5849 {
5850   return (TYPE_P (t) ? TYPE_CONTEXT (t) : DECL_CONTEXT (t));
5851 }
5852
5853 /* Return the innermost context enclosing DECL that is
5854    a FUNCTION_DECL, or zero if none.  */
5855
5856 tree
5857 decl_function_context (tree decl)
5858 {
5859   tree context;
5860
5861   if (TREE_CODE (decl) == ERROR_MARK)
5862     return 0;
5863
5864   /* C++ virtual functions use DECL_CONTEXT for the class of the vtable
5865      where we look up the function at runtime.  Such functions always take
5866      a first argument of type 'pointer to real context'.
5867
5868      C++ should really be fixed to use DECL_CONTEXT for the real context,
5869      and use something else for the "virtual context".  */
5870   else if (TREE_CODE (decl) == FUNCTION_DECL && DECL_VINDEX (decl))
5871     context
5872       = TYPE_MAIN_VARIANT
5873         (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (decl)))));
5874   else
5875     context = DECL_CONTEXT (decl);
5876
5877   while (context && TREE_CODE (context) != FUNCTION_DECL)
5878     {
5879       if (TREE_CODE (context) == BLOCK)
5880         context = BLOCK_SUPERCONTEXT (context);
5881       else
5882         context = get_containing_scope (context);
5883     }
5884
5885   return context;
5886 }
5887
5888 /* Return the innermost context enclosing DECL that is
5889    a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE, or zero if none.
5890    TYPE_DECLs and FUNCTION_DECLs are transparent to this function.  */
5891
5892 tree
5893 decl_type_context (tree decl)
5894 {
5895   tree context = DECL_CONTEXT (decl);
5896
5897   while (context)
5898     switch (TREE_CODE (context))
5899       {
5900       case NAMESPACE_DECL:
5901       case TRANSLATION_UNIT_DECL:
5902         return NULL_TREE;
5903
5904       case RECORD_TYPE:
5905       case UNION_TYPE:
5906       case QUAL_UNION_TYPE:
5907         return context;
5908
5909       case TYPE_DECL:
5910       case FUNCTION_DECL:
5911         context = DECL_CONTEXT (context);
5912         break;
5913
5914       case BLOCK:
5915         context = BLOCK_SUPERCONTEXT (context);
5916         break;
5917
5918       default:
5919         gcc_unreachable ();
5920       }
5921
5922   return NULL_TREE;
5923 }
5924
5925 /* CALL is a CALL_EXPR.  Return the declaration for the function
5926    called, or NULL_TREE if the called function cannot be
5927    determined.  */
5928
5929 tree
5930 get_callee_fndecl (tree call)
5931 {
5932   tree addr;
5933
5934   if (call == error_mark_node)
5935     return call;
5936
5937   /* It's invalid to call this function with anything but a
5938      CALL_EXPR.  */
5939   gcc_assert (TREE_CODE (call) == CALL_EXPR);
5940
5941   /* The first operand to the CALL is the address of the function
5942      called.  */
5943   addr = TREE_OPERAND (call, 0);
5944
5945   STRIP_NOPS (addr);
5946
5947   /* If this is a readonly function pointer, extract its initial value.  */
5948   if (DECL_P (addr) && TREE_CODE (addr) != FUNCTION_DECL
5949       && TREE_READONLY (addr) && ! TREE_THIS_VOLATILE (addr)
5950       && DECL_INITIAL (addr))
5951     addr = DECL_INITIAL (addr);
5952
5953   /* If the address is just `&f' for some function `f', then we know
5954      that `f' is being called.  */
5955   if (TREE_CODE (addr) == ADDR_EXPR
5956       && TREE_CODE (TREE_OPERAND (addr, 0)) == FUNCTION_DECL)
5957     return TREE_OPERAND (addr, 0);
5958
5959   /* We couldn't figure out what was being called.  Maybe the front
5960      end has some idea.  */
5961   return lang_hooks.lang_get_callee_fndecl (call);
5962 }
5963
5964 /* Print debugging information about tree nodes generated during the compile,
5965    and any language-specific information.  */
5966
5967 void
5968 dump_tree_statistics (void)
5969 {
5970 #ifdef GATHER_STATISTICS
5971   int i;
5972   int total_nodes, total_bytes;
5973 #endif
5974
5975   fprintf (stderr, "\n??? tree nodes created\n\n");
5976 #ifdef GATHER_STATISTICS
5977   fprintf (stderr, "Kind                   Nodes      Bytes\n");
5978   fprintf (stderr, "---------------------------------------\n");
5979   total_nodes = total_bytes = 0;
5980   for (i = 0; i < (int) all_kinds; i++)
5981     {
5982       fprintf (stderr, "%-20s %7d %10d\n", tree_node_kind_names[i],
5983                tree_node_counts[i], tree_node_sizes[i]);
5984       total_nodes += tree_node_counts[i];
5985       total_bytes += tree_node_sizes[i];
5986     }
5987   fprintf (stderr, "---------------------------------------\n");
5988   fprintf (stderr, "%-20s %7d %10d\n", "Total", total_nodes, total_bytes);
5989   fprintf (stderr, "---------------------------------------\n");
5990   ssanames_print_statistics ();
5991   phinodes_print_statistics ();
5992 #else
5993   fprintf (stderr, "(No per-node statistics)\n");
5994 #endif
5995   print_type_hash_statistics ();
5996   print_debug_expr_statistics ();
5997   print_value_expr_statistics ();
5998   print_restrict_base_statistics ();
5999   lang_hooks.print_statistics ();
6000 }
6001 \f
6002 #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
6003
6004 /* Generate a crc32 of a string.  */
6005
6006 unsigned
6007 crc32_string (unsigned chksum, const char *string)
6008 {
6009   do
6010     {
6011       unsigned value = *string << 24;
6012       unsigned ix;
6013
6014       for (ix = 8; ix--; value <<= 1)
6015         {
6016           unsigned feedback;
6017
6018           feedback = (value ^ chksum) & 0x80000000 ? 0x04c11db7 : 0;
6019           chksum <<= 1;
6020           chksum ^= feedback;
6021         }
6022     }
6023   while (*string++);
6024   return chksum;
6025 }
6026
6027 /* P is a string that will be used in a symbol.  Mask out any characters
6028    that are not valid in that context.  */
6029
6030 void
6031 clean_symbol_name (char *p)
6032 {
6033   for (; *p; p++)
6034     if (! (ISALNUM (*p)
6035 #ifndef NO_DOLLAR_IN_LABEL      /* this for `$'; unlikely, but... -- kr */
6036             || *p == '$'
6037 #endif
6038 #ifndef NO_DOT_IN_LABEL         /* this for `.'; unlikely, but...  */
6039             || *p == '.'
6040 #endif
6041            ))
6042       *p = '_';
6043 }
6044
6045 /* Generate a name for a special-purpose function function.
6046    The generated name may need to be unique across the whole link.
6047    TYPE is some string to identify the purpose of this function to the
6048    linker or collect2; it must start with an uppercase letter,
6049    one of:
6050    I - for constructors
6051    D - for destructors
6052    N - for C++ anonymous namespaces
6053    F - for DWARF unwind frame information.  */
6054
6055 tree
6056 get_file_function_name (const char *type)
6057 {
6058   char *buf;
6059   const char *p;
6060   char *q;
6061
6062   /* If we already have a name we know to be unique, just use that.  */
6063   if (first_global_object_name)
6064     p = first_global_object_name;
6065   /* If the target is handling the constructors/destructors, they
6066      will be local to this file and the name is only necessary for
6067      debugging purposes.  */
6068   else if ((type[0] == 'I' || type[0] == 'D') && targetm.have_ctors_dtors)
6069     {
6070       const char *file = main_input_filename;
6071       if (! file)
6072         file = input_filename;
6073       /* Just use the file's basename, because the full pathname
6074          might be quite long.  */
6075       p = strrchr (file, '/');
6076       if (p)
6077         p++;
6078       else
6079         p = file;
6080       p = q = ASTRDUP (p);
6081       clean_symbol_name (q);
6082     }
6083   else
6084     {
6085       /* Otherwise, the name must be unique across the entire link.
6086          We don't have anything that we know to be unique to this translation
6087          unit, so use what we do have and throw in some randomness.  */
6088       unsigned len;
6089       const char *name = weak_global_object_name;
6090       const char *file = main_input_filename;
6091
6092       if (! name)
6093         name = "";
6094       if (! file)
6095         file = input_filename;
6096
6097       len = strlen (file);
6098       q = alloca (9 * 2 + len + 1);
6099       memcpy (q, file, len + 1);
6100       clean_symbol_name (q);
6101
6102       sprintf (q + len, "_%08X_%08X", crc32_string (0, name),
6103                crc32_string (0, flag_random_seed));
6104
6105       p = q;
6106     }
6107
6108   buf = alloca (sizeof (FILE_FUNCTION_FORMAT) + strlen (p) + strlen (type));
6109
6110   /* Set up the name of the file-level functions we may need.
6111      Use a global object (which is already required to be unique over
6112      the program) rather than the file name (which imposes extra
6113      constraints).  */
6114   sprintf (buf, FILE_FUNCTION_FORMAT, type, p);
6115
6116   return get_identifier (buf);
6117 }
6118 \f
6119 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
6120
6121 /* Complain that the tree code of NODE does not match the expected 0
6122    terminated list of trailing codes. The trailing code list can be
6123    empty, for a more vague error message.  FILE, LINE, and FUNCTION
6124    are of the caller.  */
6125
6126 void
6127 tree_check_failed (const tree node, const char *file,
6128                    int line, const char *function, ...)
6129 {
6130   va_list args;
6131   char *buffer;
6132   unsigned length = 0;
6133   int code;
6134
6135   va_start (args, function);
6136   while ((code = va_arg (args, int)))
6137     length += 4 + strlen (tree_code_name[code]);
6138   va_end (args);
6139   if (length)
6140     {
6141       va_start (args, function);
6142       length += strlen ("expected ");
6143       buffer = alloca (length);
6144       length = 0;
6145       while ((code = va_arg (args, int)))
6146         {
6147           const char *prefix = length ? " or " : "expected ";
6148
6149           strcpy (buffer + length, prefix);
6150           length += strlen (prefix);
6151           strcpy (buffer + length, tree_code_name[code]);
6152           length += strlen (tree_code_name[code]);
6153         }
6154       va_end (args);
6155     }
6156   else
6157     buffer = (char *)"unexpected node";
6158
6159   internal_error ("tree check: %s, have %s in %s, at %s:%d",
6160                   buffer, tree_code_name[TREE_CODE (node)],
6161                   function, trim_filename (file), line);
6162 }
6163
6164 /* Complain that the tree code of NODE does match the expected 0
6165    terminated list of trailing codes. FILE, LINE, and FUNCTION are of
6166    the caller.  */
6167
6168 void
6169 tree_not_check_failed (const tree node, const char *file,
6170                        int line, const char *function, ...)
6171 {
6172   va_list args;
6173   char *buffer;
6174   unsigned length = 0;
6175   int code;
6176
6177   va_start (args, function);
6178   while ((code = va_arg (args, int)))
6179     length += 4 + strlen (tree_code_name[code]);
6180   va_end (args);
6181   va_start (args, function);
6182   buffer = alloca (length);
6183   length = 0;
6184   while ((code = va_arg (args, int)))
6185     {
6186       if (length)
6187         {
6188           strcpy (buffer + length, " or ");
6189           length += 4;
6190         }
6191       strcpy (buffer + length, tree_code_name[code]);
6192       length += strlen (tree_code_name[code]);
6193     }
6194   va_end (args);
6195
6196   internal_error ("tree check: expected none of %s, have %s in %s, at %s:%d",
6197                   buffer, tree_code_name[TREE_CODE (node)],
6198                   function, trim_filename (file), line);
6199 }
6200
6201 /* Similar to tree_check_failed, except that we check for a class of tree
6202    code, given in CL.  */
6203
6204 void
6205 tree_class_check_failed (const tree node, const enum tree_code_class cl,
6206                          const char *file, int line, const char *function)
6207 {
6208   internal_error
6209     ("tree check: expected class %qs, have %qs (%s) in %s, at %s:%d",
6210      TREE_CODE_CLASS_STRING (cl),
6211      TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))),
6212      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6213 }
6214
6215 /* Similar to tree_check_failed, except that instead of specifying a
6216    dozen codes, use the knowledge that they're all sequential.  */
6217
6218 void
6219 tree_range_check_failed (const tree node, const char *file, int line,
6220                          const char *function, enum tree_code c1,
6221                          enum tree_code c2)
6222 {
6223   char *buffer;
6224   unsigned length = 0;
6225   enum tree_code c;
6226
6227   for (c = c1; c <= c2; ++c)
6228     length += 4 + strlen (tree_code_name[c]);
6229
6230   length += strlen ("expected ");
6231   buffer = alloca (length);
6232   length = 0;
6233
6234   for (c = c1; c <= c2; ++c)
6235     {
6236       const char *prefix = length ? " or " : "expected ";
6237
6238       strcpy (buffer + length, prefix);
6239       length += strlen (prefix);
6240       strcpy (buffer + length, tree_code_name[c]);
6241       length += strlen (tree_code_name[c]);
6242     }
6243
6244   internal_error ("tree check: %s, have %s in %s, at %s:%d",
6245                   buffer, tree_code_name[TREE_CODE (node)],
6246                   function, trim_filename (file), line);
6247 }
6248
6249
6250 /* Similar to tree_check_failed, except that we check that a tree does
6251    not have the specified code, given in CL.  */
6252
6253 void
6254 tree_not_class_check_failed (const tree node, const enum tree_code_class cl,
6255                              const char *file, int line, const char *function)
6256 {
6257   internal_error
6258     ("tree check: did not expect class %qs, have %qs (%s) in %s, at %s:%d",
6259      TREE_CODE_CLASS_STRING (cl),
6260      TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))),
6261      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6262 }
6263
6264
6265 /* Similar to tree_check_failed but applied to OMP_CLAUSE codes.  */
6266
6267 void
6268 omp_clause_check_failed (const tree node, const char *file, int line,
6269                          const char *function, enum omp_clause_code code)
6270 {
6271   internal_error ("tree check: expected omp_clause %s, have %s in %s, at %s:%d",
6272                   omp_clause_code_name[code], tree_code_name[TREE_CODE (node)],
6273                   function, trim_filename (file), line);
6274 }
6275
6276
6277 /* Similar to tree_range_check_failed but applied to OMP_CLAUSE codes.  */
6278
6279 void
6280 omp_clause_range_check_failed (const tree node, const char *file, int line,
6281                                const char *function, enum omp_clause_code c1,
6282                                enum omp_clause_code c2)
6283 {
6284   char *buffer;
6285   unsigned length = 0;
6286   enum omp_clause_code c;
6287
6288   for (c = c1; c <= c2; ++c)
6289     length += 4 + strlen (omp_clause_code_name[c]);
6290
6291   length += strlen ("expected ");
6292   buffer = alloca (length);
6293   length = 0;
6294
6295   for (c = c1; c <= c2; ++c)
6296     {
6297       const char *prefix = length ? " or " : "expected ";
6298
6299       strcpy (buffer + length, prefix);
6300       length += strlen (prefix);
6301       strcpy (buffer + length, omp_clause_code_name[c]);
6302       length += strlen (omp_clause_code_name[c]);
6303     }
6304
6305   internal_error ("tree check: %s, have %s in %s, at %s:%d",
6306                   buffer, omp_clause_code_name[TREE_CODE (node)],
6307                   function, trim_filename (file), line);
6308 }
6309
6310
6311 #undef DEFTREESTRUCT
6312 #define DEFTREESTRUCT(VAL, NAME) NAME,
6313
6314 static const char *ts_enum_names[] = {
6315 #include "treestruct.def"
6316 };
6317 #undef DEFTREESTRUCT
6318
6319 #define TS_ENUM_NAME(EN) (ts_enum_names[(EN)])
6320
6321 /* Similar to tree_class_check_failed, except that we check for
6322    whether CODE contains the tree structure identified by EN.  */
6323
6324 void
6325 tree_contains_struct_check_failed (const tree node,
6326                                    const enum tree_node_structure_enum en,
6327                                    const char *file, int line,
6328                                    const char *function)
6329 {
6330   internal_error
6331     ("tree check: expected tree that contains %qs structure, have %qs  in %s, at %s:%d",
6332      TS_ENUM_NAME(en),
6333      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6334 }
6335
6336
6337 /* Similar to above, except that the check is for the bounds of a TREE_VEC's
6338    (dynamically sized) vector.  */
6339
6340 void
6341 tree_vec_elt_check_failed (int idx, int len, const char *file, int line,
6342                            const char *function)
6343 {
6344   internal_error
6345     ("tree check: accessed elt %d of tree_vec with %d elts in %s, at %s:%d",
6346      idx + 1, len, function, trim_filename (file), line);
6347 }
6348
6349 /* Similar to above, except that the check is for the bounds of a PHI_NODE's
6350    (dynamically sized) vector.  */
6351
6352 void
6353 phi_node_elt_check_failed (int idx, int len, const char *file, int line,
6354                             const char *function)
6355 {
6356   internal_error
6357     ("tree check: accessed elt %d of phi_node with %d elts in %s, at %s:%d",
6358      idx + 1, len, function, trim_filename (file), line);
6359 }
6360
6361 /* Similar to above, except that the check is for the bounds of the operand
6362    vector of an expression node.  */
6363
6364 void
6365 tree_operand_check_failed (int idx, enum tree_code code, const char *file,
6366                            int line, const char *function)
6367 {
6368   internal_error
6369     ("tree check: accessed operand %d of %s with %d operands in %s, at %s:%d",
6370      idx + 1, tree_code_name[code], TREE_CODE_LENGTH (code),
6371      function, trim_filename (file), line);
6372 }
6373
6374 /* Similar to above, except that the check is for the number of
6375    operands of an OMP_CLAUSE node.  */
6376
6377 void
6378 omp_clause_operand_check_failed (int idx, tree t, const char *file,
6379                                  int line, const char *function)
6380 {
6381   internal_error
6382     ("tree check: accessed operand %d of omp_clause %s with %d operands "
6383      "in %s, at %s:%d", idx + 1, omp_clause_code_name[OMP_CLAUSE_CODE (t)],
6384      omp_clause_num_ops [OMP_CLAUSE_CODE (t)], function,
6385      trim_filename (file), line);
6386 }
6387 #endif /* ENABLE_TREE_CHECKING */
6388 \f
6389 /* Create a new vector type node holding SUBPARTS units of type INNERTYPE,
6390    and mapped to the machine mode MODE.  Initialize its fields and build
6391    the information necessary for debugging output.  */
6392
6393 static tree
6394 make_vector_type (tree innertype, int nunits, enum machine_mode mode)
6395 {
6396   tree t;
6397   hashval_t hashcode = 0;
6398
6399   /* Build a main variant, based on the main variant of the inner type, then
6400      use it to build the variant we return.  */
6401   if ((TYPE_ATTRIBUTES (innertype) || TYPE_QUALS (innertype))
6402       && TYPE_MAIN_VARIANT (innertype) != innertype)
6403     return build_type_attribute_qual_variant (
6404             make_vector_type (TYPE_MAIN_VARIANT (innertype), nunits, mode),
6405             TYPE_ATTRIBUTES (innertype),
6406             TYPE_QUALS (innertype));
6407
6408   t = make_node (VECTOR_TYPE);
6409   TREE_TYPE (t) = TYPE_MAIN_VARIANT (innertype);
6410   SET_TYPE_VECTOR_SUBPARTS (t, nunits);
6411   TYPE_MODE (t) = mode;
6412   TYPE_READONLY (t) = TYPE_READONLY (innertype);
6413   TYPE_VOLATILE (t) = TYPE_VOLATILE (innertype);
6414
6415   layout_type (t);
6416
6417   {
6418     tree index = build_int_cst (NULL_TREE, nunits - 1);
6419     tree array = build_array_type (innertype, build_index_type (index));
6420     tree rt = make_node (RECORD_TYPE);
6421
6422     TYPE_FIELDS (rt) = build_decl (FIELD_DECL, get_identifier ("f"), array);
6423     DECL_CONTEXT (TYPE_FIELDS (rt)) = rt;
6424     layout_type (rt);
6425     TYPE_DEBUG_REPRESENTATION_TYPE (t) = rt;
6426     /* In dwarfout.c, type lookup uses TYPE_UID numbers.  We want to output
6427        the representation type, and we want to find that die when looking up
6428        the vector type.  This is most easily achieved by making the TYPE_UID
6429        numbers equal.  */
6430     TYPE_UID (rt) = TYPE_UID (t);
6431   }
6432
6433   hashcode = iterative_hash_host_wide_int (VECTOR_TYPE, hashcode);
6434   hashcode = iterative_hash_host_wide_int (mode, hashcode);
6435   hashcode = iterative_hash_object (TYPE_HASH (innertype), hashcode);
6436   return type_hash_canon (hashcode, t);
6437 }
6438
6439 static tree
6440 make_or_reuse_type (unsigned size, int unsignedp)
6441 {
6442   if (size == INT_TYPE_SIZE)
6443     return unsignedp ? unsigned_type_node : integer_type_node;
6444   if (size == CHAR_TYPE_SIZE)
6445     return unsignedp ? unsigned_char_type_node : signed_char_type_node;
6446   if (size == SHORT_TYPE_SIZE)
6447     return unsignedp ? short_unsigned_type_node : short_integer_type_node;
6448   if (size == LONG_TYPE_SIZE)
6449     return unsignedp ? long_unsigned_type_node : long_integer_type_node;
6450   if (size == LONG_LONG_TYPE_SIZE)
6451     return (unsignedp ? long_long_unsigned_type_node
6452             : long_long_integer_type_node);
6453
6454   if (unsignedp)
6455     return make_unsigned_type (size);
6456   else
6457     return make_signed_type (size);
6458 }
6459
6460 /* Create nodes for all integer types (and error_mark_node) using the sizes
6461    of C datatypes.  The caller should call set_sizetype soon after calling
6462    this function to select one of the types as sizetype.  */
6463
6464 void
6465 build_common_tree_nodes (bool signed_char, bool signed_sizetype)
6466 {
6467   error_mark_node = make_node (ERROR_MARK);
6468   TREE_TYPE (error_mark_node) = error_mark_node;
6469
6470   initialize_sizetypes (signed_sizetype);
6471
6472   /* Define both `signed char' and `unsigned char'.  */
6473   signed_char_type_node = make_signed_type (CHAR_TYPE_SIZE);
6474   TYPE_STRING_FLAG (signed_char_type_node) = 1;
6475   unsigned_char_type_node = make_unsigned_type (CHAR_TYPE_SIZE);
6476   TYPE_STRING_FLAG (unsigned_char_type_node) = 1;
6477
6478   /* Define `char', which is like either `signed char' or `unsigned char'
6479      but not the same as either.  */
6480   char_type_node
6481     = (signed_char
6482        ? make_signed_type (CHAR_TYPE_SIZE)
6483        : make_unsigned_type (CHAR_TYPE_SIZE));
6484   TYPE_STRING_FLAG (char_type_node) = 1;
6485
6486   short_integer_type_node = make_signed_type (SHORT_TYPE_SIZE);
6487   short_unsigned_type_node = make_unsigned_type (SHORT_TYPE_SIZE);
6488   integer_type_node = make_signed_type (INT_TYPE_SIZE);
6489   unsigned_type_node = make_unsigned_type (INT_TYPE_SIZE);
6490   long_integer_type_node = make_signed_type (LONG_TYPE_SIZE);
6491   long_unsigned_type_node = make_unsigned_type (LONG_TYPE_SIZE);
6492   long_long_integer_type_node = make_signed_type (LONG_LONG_TYPE_SIZE);
6493   long_long_unsigned_type_node = make_unsigned_type (LONG_LONG_TYPE_SIZE);
6494
6495   /* Define a boolean type.  This type only represents boolean values but
6496      may be larger than char depending on the value of BOOL_TYPE_SIZE.
6497      Front ends which want to override this size (i.e. Java) can redefine
6498      boolean_type_node before calling build_common_tree_nodes_2.  */
6499   boolean_type_node = make_unsigned_type (BOOL_TYPE_SIZE);
6500   TREE_SET_CODE (boolean_type_node, BOOLEAN_TYPE);
6501   TYPE_MAX_VALUE (boolean_type_node) = build_int_cst (boolean_type_node, 1);
6502   TYPE_PRECISION (boolean_type_node) = 1;
6503
6504   /* Fill in the rest of the sized types.  Reuse existing type nodes
6505      when possible.  */
6506   intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 0);
6507   intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 0);
6508   intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 0);
6509   intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 0);
6510   intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 0);
6511
6512   unsigned_intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 1);
6513   unsigned_intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 1);
6514   unsigned_intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 1);
6515   unsigned_intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 1);
6516   unsigned_intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 1);
6517
6518   access_public_node = get_identifier ("public");
6519   access_protected_node = get_identifier ("protected");
6520   access_private_node = get_identifier ("private");
6521 }
6522
6523 /* Call this function after calling build_common_tree_nodes and set_sizetype.
6524    It will create several other common tree nodes.  */
6525
6526 void
6527 build_common_tree_nodes_2 (int short_double)
6528 {
6529   /* Define these next since types below may used them.  */
6530   integer_zero_node = build_int_cst (NULL_TREE, 0);
6531   integer_one_node = build_int_cst (NULL_TREE, 1);
6532   integer_minus_one_node = build_int_cst (NULL_TREE, -1);
6533
6534   size_zero_node = size_int (0);
6535   size_one_node = size_int (1);
6536   bitsize_zero_node = bitsize_int (0);
6537   bitsize_one_node = bitsize_int (1);
6538   bitsize_unit_node = bitsize_int (BITS_PER_UNIT);
6539
6540   boolean_false_node = TYPE_MIN_VALUE (boolean_type_node);
6541   boolean_true_node = TYPE_MAX_VALUE (boolean_type_node);
6542
6543   void_type_node = make_node (VOID_TYPE);
6544   layout_type (void_type_node);
6545
6546   /* We are not going to have real types in C with less than byte alignment,
6547      so we might as well not have any types that claim to have it.  */
6548   TYPE_ALIGN (void_type_node) = BITS_PER_UNIT;
6549   TYPE_USER_ALIGN (void_type_node) = 0;
6550
6551   null_pointer_node = build_int_cst (build_pointer_type (void_type_node), 0);
6552   layout_type (TREE_TYPE (null_pointer_node));
6553
6554   ptr_type_node = build_pointer_type (void_type_node);
6555   const_ptr_type_node
6556     = build_pointer_type (build_type_variant (void_type_node, 1, 0));
6557   fileptr_type_node = ptr_type_node;
6558
6559   float_type_node = make_node (REAL_TYPE);
6560   TYPE_PRECISION (float_type_node) = FLOAT_TYPE_SIZE;
6561   layout_type (float_type_node);
6562
6563   double_type_node = make_node (REAL_TYPE);
6564   if (short_double)
6565     TYPE_PRECISION (double_type_node) = FLOAT_TYPE_SIZE;
6566   else
6567     TYPE_PRECISION (double_type_node) = DOUBLE_TYPE_SIZE;
6568   layout_type (double_type_node);
6569
6570   long_double_type_node = make_node (REAL_TYPE);
6571   TYPE_PRECISION (long_double_type_node) = LONG_DOUBLE_TYPE_SIZE;
6572   layout_type (long_double_type_node);
6573
6574   float_ptr_type_node = build_pointer_type (float_type_node);
6575   double_ptr_type_node = build_pointer_type (double_type_node);
6576   long_double_ptr_type_node = build_pointer_type (long_double_type_node);
6577   integer_ptr_type_node = build_pointer_type (integer_type_node);
6578
6579   /* Fixed size integer types.  */
6580   uint32_type_node = build_nonstandard_integer_type (32, true);
6581   uint64_type_node = build_nonstandard_integer_type (64, true);
6582
6583   /* Decimal float types. */
6584   dfloat32_type_node = make_node (REAL_TYPE);
6585   TYPE_PRECISION (dfloat32_type_node) = DECIMAL32_TYPE_SIZE;
6586   layout_type (dfloat32_type_node);
6587   TYPE_MODE (dfloat32_type_node) = SDmode;
6588   dfloat32_ptr_type_node = build_pointer_type (dfloat32_type_node);
6589
6590   dfloat64_type_node = make_node (REAL_TYPE);
6591   TYPE_PRECISION (dfloat64_type_node) = DECIMAL64_TYPE_SIZE;
6592   layout_type (dfloat64_type_node);
6593   TYPE_MODE (dfloat64_type_node) = DDmode;
6594   dfloat64_ptr_type_node = build_pointer_type (dfloat64_type_node);
6595
6596   dfloat128_type_node = make_node (REAL_TYPE);
6597   TYPE_PRECISION (dfloat128_type_node) = DECIMAL128_TYPE_SIZE;
6598   layout_type (dfloat128_type_node);
6599   TYPE_MODE (dfloat128_type_node) = TDmode;
6600   dfloat128_ptr_type_node = build_pointer_type (dfloat128_type_node);
6601
6602   complex_integer_type_node = make_node (COMPLEX_TYPE);
6603   TREE_TYPE (complex_integer_type_node) = integer_type_node;
6604   layout_type (complex_integer_type_node);
6605
6606   complex_float_type_node = make_node (COMPLEX_TYPE);
6607   TREE_TYPE (complex_float_type_node) = float_type_node;
6608   layout_type (complex_float_type_node);
6609
6610   complex_double_type_node = make_node (COMPLEX_TYPE);
6611   TREE_TYPE (complex_double_type_node) = double_type_node;
6612   layout_type (complex_double_type_node);
6613
6614   complex_long_double_type_node = make_node (COMPLEX_TYPE);
6615   TREE_TYPE (complex_long_double_type_node) = long_double_type_node;
6616   layout_type (complex_long_double_type_node);
6617
6618   {
6619     tree t = targetm.build_builtin_va_list ();
6620
6621     /* Many back-ends define record types without setting TYPE_NAME.
6622        If we copied the record type here, we'd keep the original
6623        record type without a name.  This breaks name mangling.  So,
6624        don't copy record types and let c_common_nodes_and_builtins()
6625        declare the type to be __builtin_va_list.  */
6626     if (TREE_CODE (t) != RECORD_TYPE)
6627       t = build_variant_type_copy (t);
6628
6629     va_list_type_node = t;
6630   }
6631 }
6632
6633 /* A subroutine of build_common_builtin_nodes.  Define a builtin function.  */
6634
6635 static void
6636 local_define_builtin (const char *name, tree type, enum built_in_function code,
6637                       const char *library_name, int ecf_flags)
6638 {
6639   tree decl;
6640
6641   decl = add_builtin_function (name, type, code, BUILT_IN_NORMAL,
6642                                library_name, NULL_TREE);
6643   if (ecf_flags & ECF_CONST)
6644     TREE_READONLY (decl) = 1;
6645   if (ecf_flags & ECF_PURE)
6646     DECL_IS_PURE (decl) = 1;
6647   if (ecf_flags & ECF_NORETURN)
6648     TREE_THIS_VOLATILE (decl) = 1;
6649   if (ecf_flags & ECF_NOTHROW)
6650     TREE_NOTHROW (decl) = 1;
6651   if (ecf_flags & ECF_MALLOC)
6652     DECL_IS_MALLOC (decl) = 1;
6653
6654   built_in_decls[code] = decl;
6655   implicit_built_in_decls[code] = decl;
6656 }
6657
6658 /* Call this function after instantiating all builtins that the language
6659    front end cares about.  This will build the rest of the builtins that
6660    are relied upon by the tree optimizers and the middle-end.  */
6661
6662 void
6663 build_common_builtin_nodes (void)
6664 {
6665   tree tmp, ftype;
6666
6667   if (built_in_decls[BUILT_IN_MEMCPY] == NULL
6668       || built_in_decls[BUILT_IN_MEMMOVE] == NULL)
6669     {
6670       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6671       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6672       tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6673       ftype = build_function_type (ptr_type_node, tmp);
6674
6675       if (built_in_decls[BUILT_IN_MEMCPY] == NULL)
6676         local_define_builtin ("__builtin_memcpy", ftype, BUILT_IN_MEMCPY,
6677                               "memcpy", ECF_NOTHROW);
6678       if (built_in_decls[BUILT_IN_MEMMOVE] == NULL)
6679         local_define_builtin ("__builtin_memmove", ftype, BUILT_IN_MEMMOVE,
6680                               "memmove", ECF_NOTHROW);
6681     }
6682
6683   if (built_in_decls[BUILT_IN_MEMCMP] == NULL)
6684     {
6685       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6686       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6687       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6688       ftype = build_function_type (integer_type_node, tmp);
6689       local_define_builtin ("__builtin_memcmp", ftype, BUILT_IN_MEMCMP,
6690                             "memcmp", ECF_PURE | ECF_NOTHROW);
6691     }
6692
6693   if (built_in_decls[BUILT_IN_MEMSET] == NULL)
6694     {
6695       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6696       tmp = tree_cons (NULL_TREE, integer_type_node, tmp);
6697       tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6698       ftype = build_function_type (ptr_type_node, tmp);
6699       local_define_builtin ("__builtin_memset", ftype, BUILT_IN_MEMSET,
6700                             "memset", ECF_NOTHROW);
6701     }
6702
6703   if (built_in_decls[BUILT_IN_ALLOCA] == NULL)
6704     {
6705       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6706       ftype = build_function_type (ptr_type_node, tmp);
6707       local_define_builtin ("__builtin_alloca", ftype, BUILT_IN_ALLOCA,
6708                             "alloca", ECF_NOTHROW | ECF_MALLOC);
6709     }
6710
6711   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6712   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6713   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6714   ftype = build_function_type (void_type_node, tmp);
6715   local_define_builtin ("__builtin_init_trampoline", ftype,
6716                         BUILT_IN_INIT_TRAMPOLINE,
6717                         "__builtin_init_trampoline", ECF_NOTHROW);
6718
6719   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6720   ftype = build_function_type (ptr_type_node, tmp);
6721   local_define_builtin ("__builtin_adjust_trampoline", ftype,
6722                         BUILT_IN_ADJUST_TRAMPOLINE,
6723                         "__builtin_adjust_trampoline",
6724                         ECF_CONST | ECF_NOTHROW);
6725
6726   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6727   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6728   ftype = build_function_type (void_type_node, tmp);
6729   local_define_builtin ("__builtin_nonlocal_goto", ftype,
6730                         BUILT_IN_NONLOCAL_GOTO,
6731                         "__builtin_nonlocal_goto",
6732                         ECF_NORETURN | ECF_NOTHROW);
6733
6734   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6735   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6736   ftype = build_function_type (void_type_node, tmp);
6737   local_define_builtin ("__builtin_setjmp_setup", ftype,
6738                         BUILT_IN_SETJMP_SETUP,
6739                         "__builtin_setjmp_setup", ECF_NOTHROW);
6740
6741   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6742   ftype = build_function_type (ptr_type_node, tmp);
6743   local_define_builtin ("__builtin_setjmp_dispatcher", ftype,
6744                         BUILT_IN_SETJMP_DISPATCHER,
6745                         "__builtin_setjmp_dispatcher",
6746                         ECF_PURE | ECF_NOTHROW);
6747
6748   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6749   ftype = build_function_type (void_type_node, tmp);
6750   local_define_builtin ("__builtin_setjmp_receiver", ftype,
6751                         BUILT_IN_SETJMP_RECEIVER,
6752                         "__builtin_setjmp_receiver", ECF_NOTHROW);
6753
6754   ftype = build_function_type (ptr_type_node, void_list_node);
6755   local_define_builtin ("__builtin_stack_save", ftype, BUILT_IN_STACK_SAVE,
6756                         "__builtin_stack_save", ECF_NOTHROW);
6757
6758   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6759   ftype = build_function_type (void_type_node, tmp);
6760   local_define_builtin ("__builtin_stack_restore", ftype,
6761                         BUILT_IN_STACK_RESTORE,
6762                         "__builtin_stack_restore", ECF_NOTHROW);
6763
6764   ftype = build_function_type (void_type_node, void_list_node);
6765   local_define_builtin ("__builtin_profile_func_enter", ftype,
6766                         BUILT_IN_PROFILE_FUNC_ENTER, "profile_func_enter", 0);
6767   local_define_builtin ("__builtin_profile_func_exit", ftype,
6768                         BUILT_IN_PROFILE_FUNC_EXIT, "profile_func_exit", 0);
6769
6770   /* Complex multiplication and division.  These are handled as builtins
6771      rather than optabs because emit_library_call_value doesn't support
6772      complex.  Further, we can do slightly better with folding these
6773      beasties if the real and complex parts of the arguments are separate.  */
6774   {
6775     enum machine_mode mode;
6776
6777     for (mode = MIN_MODE_COMPLEX_FLOAT; mode <= MAX_MODE_COMPLEX_FLOAT; ++mode)
6778       {
6779         char mode_name_buf[4], *q;
6780         const char *p;
6781         enum built_in_function mcode, dcode;
6782         tree type, inner_type;
6783
6784         type = lang_hooks.types.type_for_mode (mode, 0);
6785         if (type == NULL)
6786           continue;
6787         inner_type = TREE_TYPE (type);
6788
6789         tmp = tree_cons (NULL_TREE, inner_type, void_list_node);
6790         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6791         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6792         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6793         ftype = build_function_type (type, tmp);
6794
6795         mcode = BUILT_IN_COMPLEX_MUL_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
6796         dcode = BUILT_IN_COMPLEX_DIV_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
6797
6798         for (p = GET_MODE_NAME (mode), q = mode_name_buf; *p; p++, q++)
6799           *q = TOLOWER (*p);
6800         *q = '\0';
6801
6802         built_in_names[mcode] = concat ("__mul", mode_name_buf, "3", NULL);
6803         local_define_builtin (built_in_names[mcode], ftype, mcode,
6804                               built_in_names[mcode], ECF_CONST | ECF_NOTHROW);
6805
6806         built_in_names[dcode] = concat ("__div", mode_name_buf, "3", NULL);
6807         local_define_builtin (built_in_names[dcode], ftype, dcode,
6808                               built_in_names[dcode], ECF_CONST | ECF_NOTHROW);
6809       }
6810   }
6811 }
6812
6813 /* HACK.  GROSS.  This is absolutely disgusting.  I wish there was a
6814    better way.
6815
6816    If we requested a pointer to a vector, build up the pointers that
6817    we stripped off while looking for the inner type.  Similarly for
6818    return values from functions.
6819
6820    The argument TYPE is the top of the chain, and BOTTOM is the
6821    new type which we will point to.  */
6822
6823 tree
6824 reconstruct_complex_type (tree type, tree bottom)
6825 {
6826   tree inner, outer;
6827
6828   if (POINTER_TYPE_P (type))
6829     {
6830       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6831       outer = build_pointer_type (inner);
6832     }
6833   else if (TREE_CODE (type) == ARRAY_TYPE)
6834     {
6835       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6836       outer = build_array_type (inner, TYPE_DOMAIN (type));
6837     }
6838   else if (TREE_CODE (type) == FUNCTION_TYPE)
6839     {
6840       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6841       outer = build_function_type (inner, TYPE_ARG_TYPES (type));
6842     }
6843   else if (TREE_CODE (type) == METHOD_TYPE)
6844     {
6845       tree argtypes;
6846       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6847       /* The build_method_type_directly() routine prepends 'this' to argument list,
6848          so we must compensate by getting rid of it.  */
6849       argtypes = TYPE_ARG_TYPES (type);
6850       outer = build_method_type_directly (TYPE_METHOD_BASETYPE (type),
6851                                           inner,
6852                                           TYPE_ARG_TYPES (type));
6853       TYPE_ARG_TYPES (outer) = argtypes;
6854     }
6855   else
6856     return bottom;
6857
6858   TYPE_READONLY (outer) = TYPE_READONLY (type);
6859   TYPE_VOLATILE (outer) = TYPE_VOLATILE (type);
6860
6861   return outer;
6862 }
6863
6864 /* Returns a vector tree node given a mode (integer, vector, or BLKmode) and
6865    the inner type.  */
6866 tree
6867 build_vector_type_for_mode (tree innertype, enum machine_mode mode)
6868 {
6869   int nunits;
6870
6871   switch (GET_MODE_CLASS (mode))
6872     {
6873     case MODE_VECTOR_INT:
6874     case MODE_VECTOR_FLOAT:
6875       nunits = GET_MODE_NUNITS (mode);
6876       break;
6877
6878     case MODE_INT:
6879       /* Check that there are no leftover bits.  */
6880       gcc_assert (GET_MODE_BITSIZE (mode)
6881                   % TREE_INT_CST_LOW (TYPE_SIZE (innertype)) == 0);
6882
6883       nunits = GET_MODE_BITSIZE (mode)
6884                / TREE_INT_CST_LOW (TYPE_SIZE (innertype));
6885       break;
6886
6887     default:
6888       gcc_unreachable ();
6889     }
6890
6891   return make_vector_type (innertype, nunits, mode);
6892 }
6893
6894 /* Similarly, but takes the inner type and number of units, which must be
6895    a power of two.  */
6896
6897 tree
6898 build_vector_type (tree innertype, int nunits)
6899 {
6900   return make_vector_type (innertype, nunits, VOIDmode);
6901 }
6902
6903
6904 /* Build RESX_EXPR with given REGION_NUMBER.  */
6905 tree
6906 build_resx (int region_number)
6907 {
6908   tree t;
6909   t = build1 (RESX_EXPR, void_type_node,
6910               build_int_cst (NULL_TREE, region_number));
6911   return t;
6912 }
6913
6914 /* Given an initializer INIT, return TRUE if INIT is zero or some
6915    aggregate of zeros.  Otherwise return FALSE.  */
6916 bool
6917 initializer_zerop (tree init)
6918 {
6919   tree elt;
6920
6921   STRIP_NOPS (init);
6922
6923   switch (TREE_CODE (init))
6924     {
6925     case INTEGER_CST:
6926       return integer_zerop (init);
6927
6928     case REAL_CST:
6929       /* ??? Note that this is not correct for C4X float formats.  There,
6930          a bit pattern of all zeros is 1.0; 0.0 is encoded with the most
6931          negative exponent.  */
6932       return real_zerop (init)
6933         && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init));
6934
6935     case COMPLEX_CST:
6936       return integer_zerop (init)
6937         || (real_zerop (init)
6938             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init)))
6939             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init))));
6940
6941     case VECTOR_CST:
6942       for (elt = TREE_VECTOR_CST_ELTS (init); elt; elt = TREE_CHAIN (elt))
6943         if (!initializer_zerop (TREE_VALUE (elt)))
6944           return false;
6945       return true;
6946
6947     case CONSTRUCTOR:
6948       {
6949         unsigned HOST_WIDE_INT idx;
6950
6951         FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (init), idx, elt)
6952           if (!initializer_zerop (elt))
6953             return false;
6954         return true;
6955       }
6956
6957     default:
6958       return false;
6959     }
6960 }
6961
6962 /* Build an empty statement.  */
6963
6964 tree
6965 build_empty_stmt (void)
6966 {
6967   return build1 (NOP_EXPR, void_type_node, size_zero_node);
6968 }
6969
6970
6971 /* Build an OpenMP clause with code CODE.  */
6972
6973 tree
6974 build_omp_clause (enum omp_clause_code code)
6975 {
6976   tree t;
6977   int size, length;
6978
6979   length = omp_clause_num_ops[code];
6980   size = (sizeof (struct tree_omp_clause) + (length - 1) * sizeof (tree));
6981
6982   t = ggc_alloc (size);
6983   memset (t, 0, size);
6984   TREE_SET_CODE (t, OMP_CLAUSE);
6985   OMP_CLAUSE_SET_CODE (t, code);
6986
6987 #ifdef GATHER_STATISTICS
6988   tree_node_counts[(int) omp_clause_kind]++;
6989   tree_node_sizes[(int) omp_clause_kind] += size;
6990 #endif
6991
6992   return t;
6993 }
6994
6995
6996 /* Returns true if it is possible to prove that the index of
6997    an array access REF (an ARRAY_REF expression) falls into the
6998    array bounds.  */
6999
7000 bool
7001 in_array_bounds_p (tree ref)
7002 {
7003   tree idx = TREE_OPERAND (ref, 1);
7004   tree min, max;
7005
7006   if (TREE_CODE (idx) != INTEGER_CST)
7007     return false;
7008
7009   min = array_ref_low_bound (ref);
7010   max = array_ref_up_bound (ref);
7011   if (!min
7012       || !max
7013       || TREE_CODE (min) != INTEGER_CST
7014       || TREE_CODE (max) != INTEGER_CST)
7015     return false;
7016
7017   if (tree_int_cst_lt (idx, min)
7018       || tree_int_cst_lt (max, idx))
7019     return false;
7020
7021   return true;
7022 }
7023
7024 /* Returns true if it is possible to prove that the range of
7025    an array access REF (an ARRAY_RANGE_REF expression) falls
7026    into the array bounds.  */
7027
7028 bool
7029 range_in_array_bounds_p (tree ref)
7030 {
7031   tree domain_type = TYPE_DOMAIN (TREE_TYPE (ref));
7032   tree range_min, range_max, min, max;
7033
7034   range_min = TYPE_MIN_VALUE (domain_type);
7035   range_max = TYPE_MAX_VALUE (domain_type);
7036   if (!range_min
7037       || !range_max
7038       || TREE_CODE (range_min) != INTEGER_CST
7039       || TREE_CODE (range_max) != INTEGER_CST)
7040     return false;
7041
7042   min = array_ref_low_bound (ref);
7043   max = array_ref_up_bound (ref);
7044   if (!min
7045       || !max
7046       || TREE_CODE (min) != INTEGER_CST
7047       || TREE_CODE (max) != INTEGER_CST)
7048     return false;
7049
7050   if (tree_int_cst_lt (range_min, min)
7051       || tree_int_cst_lt (max, range_max))
7052     return false;
7053
7054   return true;
7055 }
7056
7057 /* Return true if T (assumed to be a DECL) is a global variable.  */
7058
7059 bool
7060 is_global_var (tree t)
7061 {
7062   if (MTAG_P (t))
7063     return (TREE_STATIC (t) || MTAG_GLOBAL (t));
7064   else
7065     return (TREE_STATIC (t) || DECL_EXTERNAL (t));
7066 }
7067
7068 /* Return true if T (assumed to be a DECL) must be assigned a memory
7069    location.  */
7070
7071 bool
7072 needs_to_live_in_memory (tree t)
7073 {
7074   return (TREE_ADDRESSABLE (t)
7075           || is_global_var (t)
7076           || (TREE_CODE (t) == RESULT_DECL
7077               && aggregate_value_p (t, current_function_decl)));
7078 }
7079
7080 /* There are situations in which a language considers record types
7081    compatible which have different field lists.  Decide if two fields
7082    are compatible.  It is assumed that the parent records are compatible.  */
7083
7084 bool
7085 fields_compatible_p (tree f1, tree f2)
7086 {
7087   if (!operand_equal_p (DECL_FIELD_BIT_OFFSET (f1),
7088                         DECL_FIELD_BIT_OFFSET (f2), OEP_ONLY_CONST))
7089     return false;
7090
7091   if (!operand_equal_p (DECL_FIELD_OFFSET (f1),
7092                         DECL_FIELD_OFFSET (f2), OEP_ONLY_CONST))
7093     return false;
7094
7095   if (!lang_hooks.types_compatible_p (TREE_TYPE (f1), TREE_TYPE (f2)))
7096     return false;
7097
7098   return true;
7099 }
7100
7101 /* Locate within RECORD a field that is compatible with ORIG_FIELD.  */
7102
7103 tree
7104 find_compatible_field (tree record, tree orig_field)
7105 {
7106   tree f;
7107
7108   for (f = TYPE_FIELDS (record); f ; f = TREE_CHAIN (f))
7109     if (TREE_CODE (f) == FIELD_DECL
7110         && fields_compatible_p (f, orig_field))
7111       return f;
7112
7113   /* ??? Why isn't this on the main fields list?  */
7114   f = TYPE_VFIELD (record);
7115   if (f && TREE_CODE (f) == FIELD_DECL
7116       && fields_compatible_p (f, orig_field))
7117     return f;
7118
7119   /* ??? We should abort here, but Java appears to do Bad Things
7120      with inherited fields.  */
7121   return orig_field;
7122 }
7123
7124 /* Return value of a constant X.  */
7125
7126 HOST_WIDE_INT
7127 int_cst_value (tree x)
7128 {
7129   unsigned bits = TYPE_PRECISION (TREE_TYPE (x));
7130   unsigned HOST_WIDE_INT val = TREE_INT_CST_LOW (x);
7131   bool negative = ((val >> (bits - 1)) & 1) != 0;
7132
7133   gcc_assert (bits <= HOST_BITS_PER_WIDE_INT);
7134
7135   if (negative)
7136     val |= (~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1;
7137   else
7138     val &= ~((~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1);
7139
7140   return val;
7141 }
7142
7143 /* Returns the greatest common divisor of A and B, which must be
7144    INTEGER_CSTs.  */
7145
7146 tree
7147 tree_fold_gcd (tree a, tree b)
7148 {
7149   tree a_mod_b;
7150   tree type = TREE_TYPE (a);
7151
7152   gcc_assert (TREE_CODE (a) == INTEGER_CST);
7153   gcc_assert (TREE_CODE (b) == INTEGER_CST);
7154
7155   if (integer_zerop (a))
7156     return b;
7157
7158   if (integer_zerop (b))
7159     return a;
7160
7161   if (tree_int_cst_sgn (a) == -1)
7162     a = fold_build2 (MULT_EXPR, type, a,
7163                      build_int_cst (type, -1));
7164
7165   if (tree_int_cst_sgn (b) == -1)
7166     b = fold_build2 (MULT_EXPR, type, b,
7167                      build_int_cst (type, -1));
7168
7169   while (1)
7170     {
7171       a_mod_b = fold_build2 (FLOOR_MOD_EXPR, type, a, b);
7172
7173       if (!TREE_INT_CST_LOW (a_mod_b)
7174           && !TREE_INT_CST_HIGH (a_mod_b))
7175         return b;
7176
7177       a = b;
7178       b = a_mod_b;
7179     }
7180 }
7181
7182 /* Returns unsigned variant of TYPE.  */
7183
7184 tree
7185 unsigned_type_for (tree type)
7186 {
7187   if (POINTER_TYPE_P (type))
7188     return lang_hooks.types.unsigned_type (size_type_node);
7189   return lang_hooks.types.unsigned_type (type);
7190 }
7191
7192 /* Returns signed variant of TYPE.  */
7193
7194 tree
7195 signed_type_for (tree type)
7196 {
7197   if (POINTER_TYPE_P (type))
7198     return lang_hooks.types.signed_type (size_type_node);
7199   return lang_hooks.types.signed_type (type);
7200 }
7201
7202 /* Returns the largest value obtainable by casting something in INNER type to
7203    OUTER type.  */
7204
7205 tree
7206 upper_bound_in_type (tree outer, tree inner)
7207 {
7208   unsigned HOST_WIDE_INT lo, hi;
7209   unsigned int det = 0;
7210   unsigned oprec = TYPE_PRECISION (outer);
7211   unsigned iprec = TYPE_PRECISION (inner);
7212   unsigned prec;
7213
7214   /* Compute a unique number for every combination.  */
7215   det |= (oprec > iprec) ? 4 : 0;
7216   det |= TYPE_UNSIGNED (outer) ? 2 : 0;
7217   det |= TYPE_UNSIGNED (inner) ? 1 : 0;
7218
7219   /* Determine the exponent to use.  */
7220   switch (det)
7221     {
7222     case 0:
7223     case 1:
7224       /* oprec <= iprec, outer: signed, inner: don't care.  */
7225       prec = oprec - 1;
7226       break;
7227     case 2:
7228     case 3:
7229       /* oprec <= iprec, outer: unsigned, inner: don't care.  */
7230       prec = oprec;
7231       break;
7232     case 4:
7233       /* oprec > iprec, outer: signed, inner: signed.  */
7234       prec = iprec - 1;
7235       break;
7236     case 5:
7237       /* oprec > iprec, outer: signed, inner: unsigned.  */
7238       prec = iprec;
7239       break;
7240     case 6:
7241       /* oprec > iprec, outer: unsigned, inner: signed.  */
7242       prec = oprec;
7243       break;
7244     case 7:
7245       /* oprec > iprec, outer: unsigned, inner: unsigned.  */
7246       prec = iprec;
7247       break;
7248     default:
7249       gcc_unreachable ();
7250     }
7251
7252   /* Compute 2^^prec - 1.  */
7253   if (prec <= HOST_BITS_PER_WIDE_INT)
7254     {
7255       hi = 0;
7256       lo = ((~(unsigned HOST_WIDE_INT) 0)
7257             >> (HOST_BITS_PER_WIDE_INT - prec));
7258     }
7259   else
7260     {
7261       hi = ((~(unsigned HOST_WIDE_INT) 0)
7262             >> (2 * HOST_BITS_PER_WIDE_INT - prec));
7263       lo = ~(unsigned HOST_WIDE_INT) 0;
7264     }
7265
7266   return build_int_cst_wide (outer, lo, hi);
7267 }
7268
7269 /* Returns the smallest value obtainable by casting something in INNER type to
7270    OUTER type.  */
7271
7272 tree
7273 lower_bound_in_type (tree outer, tree inner)
7274 {
7275   unsigned HOST_WIDE_INT lo, hi;
7276   unsigned oprec = TYPE_PRECISION (outer);
7277   unsigned iprec = TYPE_PRECISION (inner);
7278
7279   /* If OUTER type is unsigned, we can definitely cast 0 to OUTER type
7280      and obtain 0.  */
7281   if (TYPE_UNSIGNED (outer)
7282       /* If we are widening something of an unsigned type, OUTER type
7283          contains all values of INNER type.  In particular, both INNER
7284          and OUTER types have zero in common.  */
7285       || (oprec > iprec && TYPE_UNSIGNED (inner)))
7286     lo = hi = 0;
7287   else
7288     {
7289       /* If we are widening a signed type to another signed type, we
7290          want to obtain -2^^(iprec-1).  If we are keeping the
7291          precision or narrowing to a signed type, we want to obtain
7292          -2^(oprec-1).  */
7293       unsigned prec = oprec > iprec ? iprec : oprec;
7294
7295       if (prec <= HOST_BITS_PER_WIDE_INT)
7296         {
7297           hi = ~(unsigned HOST_WIDE_INT) 0;
7298           lo = (~(unsigned HOST_WIDE_INT) 0) << (prec - 1);
7299         }
7300       else
7301         {
7302           hi = ((~(unsigned HOST_WIDE_INT) 0)
7303                 << (prec - HOST_BITS_PER_WIDE_INT - 1));
7304           lo = 0;
7305         }
7306     }
7307
7308   return build_int_cst_wide (outer, lo, hi);
7309 }
7310
7311 /* Return nonzero if two operands that are suitable for PHI nodes are
7312    necessarily equal.  Specifically, both ARG0 and ARG1 must be either
7313    SSA_NAME or invariant.  Note that this is strictly an optimization.
7314    That is, callers of this function can directly call operand_equal_p
7315    and get the same result, only slower.  */
7316
7317 int
7318 operand_equal_for_phi_arg_p (tree arg0, tree arg1)
7319 {
7320   if (arg0 == arg1)
7321     return 1;
7322   if (TREE_CODE (arg0) == SSA_NAME || TREE_CODE (arg1) == SSA_NAME)
7323     return 0;
7324   return operand_equal_p (arg0, arg1, 0);
7325 }
7326
7327 /* Returns number of zeros at the end of binary representation of X.
7328
7329    ??? Use ffs if available?  */
7330
7331 tree
7332 num_ending_zeros (tree x)
7333 {
7334   unsigned HOST_WIDE_INT fr, nfr;
7335   unsigned num, abits;
7336   tree type = TREE_TYPE (x);
7337
7338   if (TREE_INT_CST_LOW (x) == 0)
7339     {
7340       num = HOST_BITS_PER_WIDE_INT;
7341       fr = TREE_INT_CST_HIGH (x);
7342     }
7343   else
7344     {
7345       num = 0;
7346       fr = TREE_INT_CST_LOW (x);
7347     }
7348
7349   for (abits = HOST_BITS_PER_WIDE_INT / 2; abits; abits /= 2)
7350     {
7351       nfr = fr >> abits;
7352       if (nfr << abits == fr)
7353         {
7354           num += abits;
7355           fr = nfr;
7356         }
7357     }
7358
7359   if (num > TYPE_PRECISION (type))
7360     num = TYPE_PRECISION (type);
7361
7362   return build_int_cst_type (type, num);
7363 }
7364
7365
7366 #define WALK_SUBTREE(NODE)                              \
7367   do                                                    \
7368     {                                                   \
7369       result = walk_tree (&(NODE), func, data, pset);   \
7370       if (result)                                       \
7371         return result;                                  \
7372     }                                                   \
7373   while (0)
7374
7375 /* This is a subroutine of walk_tree that walks field of TYPE that are to
7376    be walked whenever a type is seen in the tree.  Rest of operands and return
7377    value are as for walk_tree.  */
7378
7379 static tree
7380 walk_type_fields (tree type, walk_tree_fn func, void *data,
7381                   struct pointer_set_t *pset)
7382 {
7383   tree result = NULL_TREE;
7384
7385   switch (TREE_CODE (type))
7386     {
7387     case POINTER_TYPE:
7388     case REFERENCE_TYPE:
7389       /* We have to worry about mutually recursive pointers.  These can't
7390          be written in C.  They can in Ada.  It's pathological, but
7391          there's an ACATS test (c38102a) that checks it.  Deal with this
7392          by checking if we're pointing to another pointer, that one
7393          points to another pointer, that one does too, and we have no htab.
7394          If so, get a hash table.  We check three levels deep to avoid
7395          the cost of the hash table if we don't need one.  */
7396       if (POINTER_TYPE_P (TREE_TYPE (type))
7397           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type)))
7398           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type))))
7399           && !pset)
7400         {
7401           result = walk_tree_without_duplicates (&TREE_TYPE (type),
7402                                                  func, data);
7403           if (result)
7404             return result;
7405
7406           break;
7407         }
7408
7409       /* ... fall through ... */
7410
7411     case COMPLEX_TYPE:
7412       WALK_SUBTREE (TREE_TYPE (type));
7413       break;
7414
7415     case METHOD_TYPE:
7416       WALK_SUBTREE (TYPE_METHOD_BASETYPE (type));
7417
7418       /* Fall through.  */
7419
7420     case FUNCTION_TYPE:
7421       WALK_SUBTREE (TREE_TYPE (type));
7422       {
7423         tree arg;
7424
7425         /* We never want to walk into default arguments.  */
7426         for (arg = TYPE_ARG_TYPES (type); arg; arg = TREE_CHAIN (arg))
7427           WALK_SUBTREE (TREE_VALUE (arg));
7428       }
7429       break;
7430
7431     case ARRAY_TYPE:
7432       /* Don't follow this nodes's type if a pointer for fear that we'll
7433          have infinite recursion.  Those types are uninteresting anyway.  */
7434       if (!POINTER_TYPE_P (TREE_TYPE (type))
7435           && TREE_CODE (TREE_TYPE (type)) != OFFSET_TYPE)
7436         WALK_SUBTREE (TREE_TYPE (type));
7437       WALK_SUBTREE (TYPE_DOMAIN (type));
7438       break;
7439
7440     case BOOLEAN_TYPE:
7441     case ENUMERAL_TYPE:
7442     case INTEGER_TYPE:
7443     case REAL_TYPE:
7444       WALK_SUBTREE (TYPE_MIN_VALUE (type));
7445       WALK_SUBTREE (TYPE_MAX_VALUE (type));
7446       break;
7447
7448     case OFFSET_TYPE:
7449       WALK_SUBTREE (TREE_TYPE (type));
7450       WALK_SUBTREE (TYPE_OFFSET_BASETYPE (type));
7451       break;
7452
7453     default:
7454       break;
7455     }
7456
7457   return NULL_TREE;
7458 }
7459
7460 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.  FUNC is
7461    called with the DATA and the address of each sub-tree.  If FUNC returns a
7462    non-NULL value, the traversal is stopped, and the value returned by FUNC
7463    is returned.  If PSET is non-NULL it is used to record the nodes visited,
7464    and to avoid visiting a node more than once.  */
7465
7466 tree
7467 walk_tree (tree *tp, walk_tree_fn func, void *data, struct pointer_set_t *pset)
7468 {
7469   enum tree_code code;
7470   int walk_subtrees;
7471   tree result;
7472
7473 #define WALK_SUBTREE_TAIL(NODE)                         \
7474   do                                                    \
7475     {                                                   \
7476        tp = & (NODE);                                   \
7477        goto tail_recurse;                               \
7478     }                                                   \
7479   while (0)
7480
7481  tail_recurse:
7482   /* Skip empty subtrees.  */
7483   if (!*tp)
7484     return NULL_TREE;
7485
7486   /* Don't walk the same tree twice, if the user has requested
7487      that we avoid doing so.  */
7488   if (pset && pointer_set_insert (pset, *tp))
7489     return NULL_TREE;
7490
7491   /* Call the function.  */
7492   walk_subtrees = 1;
7493   result = (*func) (tp, &walk_subtrees, data);
7494
7495   /* If we found something, return it.  */
7496   if (result)
7497     return result;
7498
7499   code = TREE_CODE (*tp);
7500
7501   /* Even if we didn't, FUNC may have decided that there was nothing
7502      interesting below this point in the tree.  */
7503   if (!walk_subtrees)
7504     {
7505       /* But we still need to check our siblings.  */
7506       if (code == TREE_LIST)
7507         WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
7508       else if (code == OMP_CLAUSE)
7509         WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp));
7510       else
7511         return NULL_TREE;
7512     }
7513
7514   result = lang_hooks.tree_inlining.walk_subtrees (tp, &walk_subtrees, func,
7515                                                    data, pset);
7516   if (result || ! walk_subtrees)
7517     return result;
7518
7519   switch (code)
7520     {
7521     case ERROR_MARK:
7522     case IDENTIFIER_NODE:
7523     case INTEGER_CST:
7524     case REAL_CST:
7525     case VECTOR_CST:
7526     case STRING_CST:
7527     case BLOCK:
7528     case PLACEHOLDER_EXPR:
7529     case SSA_NAME:
7530     case FIELD_DECL:
7531     case RESULT_DECL:
7532       /* None of these have subtrees other than those already walked
7533          above.  */
7534       break;
7535
7536     case TREE_LIST:
7537       WALK_SUBTREE (TREE_VALUE (*tp));
7538       WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
7539       break;
7540
7541     case TREE_VEC:
7542       {
7543         int len = TREE_VEC_LENGTH (*tp);
7544
7545         if (len == 0)
7546           break;
7547
7548         /* Walk all elements but the first.  */
7549         while (--len)
7550           WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
7551
7552         /* Now walk the first one as a tail call.  */
7553         WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
7554       }
7555
7556     case COMPLEX_CST:
7557       WALK_SUBTREE (TREE_REALPART (*tp));
7558       WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp));
7559
7560     case CONSTRUCTOR:
7561       {
7562         unsigned HOST_WIDE_INT idx;
7563         constructor_elt *ce;
7564
7565         for (idx = 0;
7566              VEC_iterate(constructor_elt, CONSTRUCTOR_ELTS (*tp), idx, ce);
7567              idx++)
7568           WALK_SUBTREE (ce->value);
7569       }
7570       break;
7571
7572     case SAVE_EXPR:
7573       WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 0));
7574
7575     case BIND_EXPR:
7576       {
7577         tree decl;
7578         for (decl = BIND_EXPR_VARS (*tp); decl; decl = TREE_CHAIN (decl))
7579           {
7580             /* Walk the DECL_INITIAL and DECL_SIZE.  We don't want to walk
7581                into declarations that are just mentioned, rather than
7582                declared; they don't really belong to this part of the tree.
7583                And, we can see cycles: the initializer for a declaration
7584                can refer to the declaration itself.  */
7585             WALK_SUBTREE (DECL_INITIAL (decl));
7586             WALK_SUBTREE (DECL_SIZE (decl));
7587             WALK_SUBTREE (DECL_SIZE_UNIT (decl));
7588           }
7589         WALK_SUBTREE_TAIL (BIND_EXPR_BODY (*tp));
7590       }
7591
7592     case STATEMENT_LIST:
7593       {
7594         tree_stmt_iterator i;
7595         for (i = tsi_start (*tp); !tsi_end_p (i); tsi_next (&i))
7596           WALK_SUBTREE (*tsi_stmt_ptr (i));
7597       }
7598       break;
7599
7600     case OMP_CLAUSE:
7601       switch (OMP_CLAUSE_CODE (*tp))
7602         {
7603         case OMP_CLAUSE_PRIVATE:
7604         case OMP_CLAUSE_SHARED:
7605         case OMP_CLAUSE_FIRSTPRIVATE:
7606         case OMP_CLAUSE_LASTPRIVATE:
7607         case OMP_CLAUSE_COPYIN:
7608         case OMP_CLAUSE_COPYPRIVATE:
7609         case OMP_CLAUSE_IF:
7610         case OMP_CLAUSE_NUM_THREADS:
7611         case OMP_CLAUSE_SCHEDULE:
7612           WALK_SUBTREE (OMP_CLAUSE_OPERAND (*tp, 0));
7613           /* FALLTHRU */
7614
7615         case OMP_CLAUSE_NOWAIT:
7616         case OMP_CLAUSE_ORDERED:
7617         case OMP_CLAUSE_DEFAULT:
7618           WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp));
7619
7620         case OMP_CLAUSE_REDUCTION:
7621           {
7622             int i;
7623             for (i = 0; i < 4; i++)
7624               WALK_SUBTREE (OMP_CLAUSE_OPERAND (*tp, i));
7625             WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp));
7626           }
7627
7628         default:
7629           gcc_unreachable ();
7630         }
7631       break;
7632
7633     case TARGET_EXPR:
7634       {
7635         int i, len;
7636
7637         /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
7638            But, we only want to walk once.  */
7639         len = (TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1)) ? 2 : 3;
7640         for (i = 0; i < len; ++i)
7641           WALK_SUBTREE (TREE_OPERAND (*tp, i));
7642         WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len));
7643       }
7644
7645     case DECL_EXPR:
7646       /* Walk into various fields of the type that it's defining.  We only
7647          want to walk into these fields of a type in this case.  Note that
7648          decls get walked as part of the processing of a BIND_EXPR.
7649
7650          ??? Precisely which fields of types that we are supposed to walk in
7651          this case vs. the normal case aren't well defined.  */
7652       if (TREE_CODE (DECL_EXPR_DECL (*tp)) == TYPE_DECL
7653           && TREE_CODE (TREE_TYPE (DECL_EXPR_DECL (*tp))) != ERROR_MARK)
7654         {
7655           tree *type_p = &TREE_TYPE (DECL_EXPR_DECL (*tp));
7656
7657           /* Call the function for the type.  See if it returns anything or
7658              doesn't want us to continue.  If we are to continue, walk both
7659              the normal fields and those for the declaration case.  */
7660           result = (*func) (type_p, &walk_subtrees, data);
7661           if (result || !walk_subtrees)
7662             return NULL_TREE;
7663
7664           result = walk_type_fields (*type_p, func, data, pset);
7665           if (result)
7666             return result;
7667
7668           /* If this is a record type, also walk the fields.  */
7669           if (TREE_CODE (*type_p) == RECORD_TYPE
7670               || TREE_CODE (*type_p) == UNION_TYPE
7671               || TREE_CODE (*type_p) == QUAL_UNION_TYPE)
7672             {
7673               tree field;
7674
7675               for (field = TYPE_FIELDS (*type_p); field;
7676                    field = TREE_CHAIN (field))
7677                 {
7678                   /* We'd like to look at the type of the field, but we can
7679                      easily get infinite recursion.  So assume it's pointed
7680                      to elsewhere in the tree.  Also, ignore things that
7681                      aren't fields.  */
7682                   if (TREE_CODE (field) != FIELD_DECL)
7683                     continue;
7684
7685                   WALK_SUBTREE (DECL_FIELD_OFFSET (field));
7686                   WALK_SUBTREE (DECL_SIZE (field));
7687                   WALK_SUBTREE (DECL_SIZE_UNIT (field));
7688                   if (TREE_CODE (*type_p) == QUAL_UNION_TYPE)
7689                     WALK_SUBTREE (DECL_QUALIFIER (field));
7690                 }
7691             }
7692
7693           WALK_SUBTREE (TYPE_SIZE (*type_p));
7694           WALK_SUBTREE_TAIL (TYPE_SIZE_UNIT (*type_p));
7695         }
7696       /* FALLTHRU */
7697
7698     default:
7699       if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
7700         {
7701           int i, len;
7702
7703           /* Walk over all the sub-trees of this operand.  */
7704           len = TREE_CODE_LENGTH (code);
7705
7706           /* Go through the subtrees.  We need to do this in forward order so
7707              that the scope of a FOR_EXPR is handled properly.  */
7708           if (len)
7709             {
7710               for (i = 0; i < len - 1; ++i)
7711                 WALK_SUBTREE (TREE_OPERAND (*tp, i));
7712               WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len - 1));
7713             }
7714         }
7715
7716       /* If this is a type, walk the needed fields in the type.  */
7717       else if (TYPE_P (*tp))
7718         return walk_type_fields (*tp, func, data, pset);
7719       break;
7720     }
7721
7722   /* We didn't find what we were looking for.  */
7723   return NULL_TREE;
7724
7725 #undef WALK_SUBTREE_TAIL
7726 }
7727 #undef WALK_SUBTREE
7728
7729 /* Like walk_tree, but does not walk duplicate nodes more than once.  */
7730
7731 tree
7732 walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data)
7733 {
7734   tree result;
7735   struct pointer_set_t *pset;
7736
7737   pset = pointer_set_create ();
7738   result = walk_tree (tp, func, data, pset);
7739   pointer_set_destroy (pset);
7740   return result;
7741 }
7742
7743
7744 /* Return true if STMT is an empty statement or contains nothing but
7745    empty statements.  */
7746
7747 bool
7748 empty_body_p (tree stmt)
7749 {
7750   tree_stmt_iterator i;
7751   tree body;
7752
7753   if (IS_EMPTY_STMT (stmt))
7754     return true;
7755   else if (TREE_CODE (stmt) == BIND_EXPR)
7756     body = BIND_EXPR_BODY (stmt);
7757   else if (TREE_CODE (stmt) == STATEMENT_LIST)
7758     body = stmt;
7759   else
7760     return false;
7761
7762   for (i = tsi_start (body); !tsi_end_p (i); tsi_next (&i))
7763     if (!empty_body_p (tsi_stmt (i)))
7764       return false;
7765
7766   return true;
7767 }
7768
7769 #include "gt-tree.h"