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