contrib/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             {
 546               DECL_ALIGN (t) = FUNCTION_BOUNDARY;
 547               DECL_MODE (t) = FUNCTION_MODE;
 548             }
 549           else
 550             DECL_ALIGN (t) = 1;
 551           /* We have not yet computed the alias set for this declaration.  */
 552           DECL_POINTER_ALIAS_SET (t) = -1;
 553         }
 554       DECL_SOURCE_LOCATION (t) = input_location;
 555       DECL_UID (t) = next_decl_uid++;
 556
 557       break;
 558
 559     case tcc_type:
 560       TYPE_UID (t) = next_type_uid++;
 561       TYPE_ALIGN (t) = BITS_PER_UNIT;
 562       TYPE_USER_ALIGN (t) = 0;
 563       TYPE_MAIN_VARIANT (t) = t;
 564
 565       /* Default to no attributes for type, but let target change that.  */
 566       TYPE_ATTRIBUTES (t) = NULL_TREE;
 567       targetm.set_default_type_attributes (t);
 568
 569       /* We have not yet computed the alias set for this type.  */
 570       TYPE_ALIAS_SET (t) = -1;
 571       break;
 572
 573     case tcc_constant:
 574       TREE_CONSTANT (t) = 1;
 575       TREE_INVARIANT (t) = 1;
 576       break;
 577
 578     case tcc_expression:
 579       switch (code)
 580         {
 581         case INIT_EXPR:
 582         case MODIFY_EXPR:
 583         case VA_ARG_EXPR:
 584         case PREDECREMENT_EXPR:
 585         case PREINCREMENT_EXPR:
 586         case POSTDECREMENT_EXPR:
 587         case POSTINCREMENT_EXPR:
 588           /* All of these have side-effects, no matter what their
 589              operands are.  */
 590           TREE_SIDE_EFFECTS (t) = 1;
 591           break;
 592
 593         default:
 594           break;
 595         }
 596       break;
 597
 598     default:
 599       /* Other classes need no special treatment.  */
 600       break;
 601     }
 602
 603   return t;
 604 }
 605 \f
 606 /* Return a new node with the same contents as NODE except that its
 607    TREE_CHAIN is zero and it has a fresh uid.  */
 608
 609 tree
 610 copy_node_stat (tree node MEM_STAT_DECL)
 611 {
 612   tree t;
 613   enum tree_code code = TREE_CODE (node);
 614   size_t length;
 615
 616   gcc_assert (code != STATEMENT_LIST);
 617
 618   length = tree_size (node);
 619   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
 620   memcpy (t, node, length);
 621
 622   TREE_CHAIN (t) = 0;
 623   TREE_ASM_WRITTEN (t) = 0;
 624   TREE_VISITED (t) = 0;
 625   t->common.ann = 0;
 626
 627   if (TREE_CODE_CLASS (code) == tcc_declaration)
 628     {
 629       DECL_UID (t) = next_decl_uid++;
 630       if ((TREE_CODE (node) == PARM_DECL || TREE_CODE (node) == VAR_DECL)
 631           && DECL_HAS_VALUE_EXPR_P (node))
 632         {
 633           SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (node));
 634           DECL_HAS_VALUE_EXPR_P (t) = 1;
 635         }
 636       if (TREE_CODE (node) == VAR_DECL && DECL_HAS_INIT_PRIORITY_P (node))
 637         {
 638           SET_DECL_INIT_PRIORITY (t, DECL_INIT_PRIORITY (node));
 639           DECL_HAS_INIT_PRIORITY_P (t) = 1;
 640         }
 641       if (TREE_CODE (node) == VAR_DECL && DECL_BASED_ON_RESTRICT_P (node))
 642         {
 643           SET_DECL_RESTRICT_BASE (t, DECL_GET_RESTRICT_BASE (node));
 644           DECL_BASED_ON_RESTRICT_P (t) = 1;
 645         }
 646     }
 647   else if (TREE_CODE_CLASS (code) == tcc_type)
 648     {
 649       TYPE_UID (t) = next_type_uid++;
 650       /* The following is so that the debug code for
 651          the copy is different from the original type.
 652          The two statements usually duplicate each other
 653          (because they clear fields of the same union),
 654          but the optimizer should catch that.  */
 655       TYPE_SYMTAB_POINTER (t) = 0;
 656       TYPE_SYMTAB_ADDRESS (t) = 0;
 657
 658       /* Do not copy the values cache.  */
 659       if (TYPE_CACHED_VALUES_P(t))
 660         {
 661           TYPE_CACHED_VALUES_P (t) = 0;
 662           TYPE_CACHED_VALUES (t) = NULL_TREE;
 663         }
 664     }
 665
 666   return t;
 667 }
 668
 669 /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
 670    For example, this can copy a list made of TREE_LIST nodes.  */
 671
 672 tree
 673 copy_list (tree list)
 674 {
 675   tree head;
 676   tree prev, next;
 677
 678   if (list == 0)
 679     return 0;
 680
 681   head = prev = copy_node (list);
 682   next = TREE_CHAIN (list);
 683   while (next)
 684     {
 685       TREE_CHAIN (prev) = copy_node (next);
 686       prev = TREE_CHAIN (prev);
 687       next = TREE_CHAIN (next);
 688     }
 689   return head;
 690 }
 691
 692 \f
 693 /* Create an INT_CST node with a LOW value sign extended.  */
 694
 695 tree
 696 build_int_cst (tree type, HOST_WIDE_INT low)
 697 {
 698   return build_int_cst_wide (type, low, low < 0 ? -1 : 0);
 699 }
 700
 701 /* Create an INT_CST node with a LOW value zero extended.  */
 702
 703 tree
 704 build_int_cstu (tree type, unsigned HOST_WIDE_INT low)
 705 {
 706   return build_int_cst_wide (type, low, 0);
 707 }
 708
 709 /* Create an INT_CST node with a LOW value in TYPE.  The value is sign extended
 710    if it is negative.  This function is similar to build_int_cst, but
 711    the extra bits outside of the type precision are cleared.  Constants
 712    with these extra bits may confuse the fold so that it detects overflows
 713    even in cases when they do not occur, and in general should be avoided.
 714    We cannot however make this a default behavior of build_int_cst without
 715    more intrusive changes, since there are parts of gcc that rely on the extra
 716    precision of the integer constants.  */
 717
 718 tree
 719 build_int_cst_type (tree type, HOST_WIDE_INT low)
 720 {
 721   unsigned HOST_WIDE_INT val = (unsigned HOST_WIDE_INT) low;
 722   unsigned HOST_WIDE_INT hi, mask;
 723   unsigned bits;
 724   bool signed_p;
 725   bool negative;
 726
 727   if (!type)
 728     type = integer_type_node;
 729
 730   bits = TYPE_PRECISION (type);
 731   signed_p = !TYPE_UNSIGNED (type);
 732
 733   if (bits >= HOST_BITS_PER_WIDE_INT)
 734     negative = (low < 0);
 735   else
 736     {
 737       /* If the sign bit is inside precision of LOW, use it to determine
 738          the sign of the constant.  */
 739       negative = ((val >> (bits - 1)) & 1) != 0;
 740
 741       /* Mask out the bits outside of the precision of the constant.  */
 742       mask = (((unsigned HOST_WIDE_INT) 2) << (bits - 1)) - 1;
 743
 744       if (signed_p && negative)
 745         val |= ~mask;
 746       else
 747         val &= mask;
 748     }
 749
 750   /* Determine the high bits.  */
 751   hi = (negative ? ~(unsigned HOST_WIDE_INT) 0 : 0);
 752
 753   /* For unsigned type we need to mask out the bits outside of the type
 754      precision.  */
 755   if (!signed_p)
 756     {
 757       if (bits <= HOST_BITS_PER_WIDE_INT)
 758         hi = 0;
 759       else
 760         {
 761           bits -= HOST_BITS_PER_WIDE_INT;
 762           mask = (((unsigned HOST_WIDE_INT) 2) << (bits - 1)) - 1;
 763           hi &= mask;
 764         }
 765     }
 766
 767   return build_int_cst_wide (type, val, hi);
 768 }
 769
 770 /* These are the hash table functions for the hash table of INTEGER_CST
 771    nodes of a sizetype.  */
 772
 773 /* Return the hash code code X, an INTEGER_CST.  */
 774
 775 static hashval_t
 776 int_cst_hash_hash (const void *x)
 777 {
 778   tree t = (tree) x;
 779
 780   return (TREE_INT_CST_HIGH (t) ^ TREE_INT_CST_LOW (t)
 781           ^ htab_hash_pointer (TREE_TYPE (t)));
 782 }
 783
 784 /* Return nonzero if the value represented by *X (an INTEGER_CST tree node)
 785    is the same as that given by *Y, which is the same.  */
 786
 787 static int
 788 int_cst_hash_eq (const void *x, const void *y)
 789 {
 790   tree xt = (tree) x;
 791   tree yt = (tree) y;
 792
 793   return (TREE_TYPE (xt) == TREE_TYPE (yt)
 794           && TREE_INT_CST_HIGH (xt) == TREE_INT_CST_HIGH (yt)
 795           && TREE_INT_CST_LOW (xt) == TREE_INT_CST_LOW (yt));
 796 }
 797
 798 /* Create an INT_CST node of TYPE and value HI:LOW.  If TYPE is NULL,
 799    integer_type_node is used.  The returned node is always shared.
 800    For small integers we use a per-type vector cache, for larger ones
 801    we use a single hash table.  */
 802
 803 tree
 804 build_int_cst_wide (tree type, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
 805 {
 806   tree t;
 807   int ix = -1;
 808   int limit = 0;
 809
 810   if (!type)
 811     type = integer_type_node;
 812
 813   switch (TREE_CODE (type))
 814     {
 815     case POINTER_TYPE:
 816     case REFERENCE_TYPE:
 817       /* Cache NULL pointer.  */
 818       if (!hi && !low)
 819         {
 820           limit = 1;
 821           ix = 0;
 822         }
 823       break;
 824
 825     case BOOLEAN_TYPE:
 826       /* Cache false or true.  */
 827       limit = 2;
 828       if (!hi && low < 2)
 829         ix = low;
 830       break;
 831
 832     case INTEGER_TYPE:
 833     case OFFSET_TYPE:
 834       if (TYPE_UNSIGNED (type))
 835         {
 836           /* Cache 0..N */
 837           limit = INTEGER_SHARE_LIMIT;
 838           if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
 839             ix = low;
 840         }
 841       else
 842         {
 843           /* Cache -1..N */
 844           limit = INTEGER_SHARE_LIMIT + 1;
 845           if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
 846             ix = low + 1;
 847           else if (hi == -1 && low == -(unsigned HOST_WIDE_INT)1)
 848             ix = 0;
 849         }
 850       break;
 851     default:
 852       break;
 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       /* FIXME: LABEL_DECL and CONST_DECL never have DECL_ALIGN set
1889          meaningfully, it's always 1.  */
1890     case LABEL_DECL:     case CONST_DECL:
1891     case VAR_DECL:       case PARM_DECL:   case RESULT_DECL:
1892     case FUNCTION_DECL:
1893       gcc_assert (DECL_ALIGN (t) != 0);
1894       return DECL_ALIGN (t);
1895
1896     default:
1897       break;
1898     }
1899
1900   /* Otherwise take the alignment from that of the type.  */
1901   return TYPE_ALIGN (TREE_TYPE (t));
1902 }
1903 \f
1904 /* Return, as a tree node, the number of elements for TYPE (which is an
1905    ARRAY_TYPE) minus one. This counts only elements of the top array.  */
1906
1907 tree
1908 array_type_nelts (tree type)
1909 {
1910   tree index_type, min, max;
1911
1912   /* If they did it with unspecified bounds, then we should have already
1913      given an error about it before we got here.  */
1914   if (! TYPE_DOMAIN (type))
1915     return error_mark_node;
1916
1917   index_type = TYPE_DOMAIN (type);
1918   min = TYPE_MIN_VALUE (index_type);
1919   max = TYPE_MAX_VALUE (index_type);
1920
1921   return (integer_zerop (min)
1922           ? max
1923           : fold_build2 (MINUS_EXPR, TREE_TYPE (max), max, min));
1924 }
1925 \f
1926 /* If arg is static -- a reference to an object in static storage -- then
1927    return the object.  This is not the same as the C meaning of `static'.
1928    If arg isn't static, return NULL.  */
1929
1930 tree
1931 staticp (tree arg)
1932 {
1933   switch (TREE_CODE (arg))
1934     {
1935     case FUNCTION_DECL:
1936       /* Nested functions are static, even though taking their address will
1937          involve a trampoline as we unnest the nested function and create
1938          the trampoline on the tree level.  */
1939       return arg;
1940
1941     case VAR_DECL:
1942       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1943               && ! DECL_THREAD_LOCAL_P (arg)
1944               && ! DECL_DLLIMPORT_P (arg)
1945               ? arg : NULL);
1946
1947     case CONST_DECL:
1948       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1949               ? arg : NULL);
1950
1951     case CONSTRUCTOR:
1952       return TREE_STATIC (arg) ? arg : NULL;
1953
1954     case LABEL_DECL:
1955     case STRING_CST:
1956       return arg;
1957
1958     case COMPONENT_REF:
1959       /* If the thing being referenced is not a field, then it is
1960          something language specific.  */
1961       if (TREE_CODE (TREE_OPERAND (arg, 1)) != FIELD_DECL)
1962         return (*lang_hooks.staticp) (arg);
1963
1964       /* If we are referencing a bitfield, we can't evaluate an
1965          ADDR_EXPR at compile time and so it isn't a constant.  */
1966       if (DECL_BIT_FIELD (TREE_OPERAND (arg, 1)))
1967         return NULL;
1968
1969       return staticp (TREE_OPERAND (arg, 0));
1970
1971     case BIT_FIELD_REF:
1972       return NULL;
1973
1974     case MISALIGNED_INDIRECT_REF:
1975     case ALIGN_INDIRECT_REF:
1976     case INDIRECT_REF:
1977       return TREE_CONSTANT (TREE_OPERAND (arg, 0)) ? arg : NULL;
1978
1979     case ARRAY_REF:
1980     case ARRAY_RANGE_REF:
1981       if (TREE_CODE (TYPE_SIZE (TREE_TYPE (arg))) == INTEGER_CST
1982           && TREE_CODE (TREE_OPERAND (arg, 1)) == INTEGER_CST)
1983         return staticp (TREE_OPERAND (arg, 0));
1984       else
1985         return false;
1986
1987     default:
1988       if ((unsigned int) TREE_CODE (arg)
1989           >= (unsigned int) LAST_AND_UNUSED_TREE_CODE)
1990         return lang_hooks.staticp (arg);
1991       else
1992         return NULL;
1993     }
1994 }
1995 \f
1996 /* Wrap a SAVE_EXPR around EXPR, if appropriate.
1997    Do this to any expression which may be used in more than one place,
1998    but must be evaluated only once.
1999
2000    Normally, expand_expr would reevaluate the expression each time.
2001    Calling save_expr produces something that is evaluated and recorded
2002    the first time expand_expr is called on it.  Subsequent calls to
2003    expand_expr just reuse the recorded value.
2004
2005    The call to expand_expr that generates code that actually computes
2006    the value is the first call *at compile time*.  Subsequent calls
2007    *at compile time* generate code to use the saved value.
2008    This produces correct result provided that *at run time* control
2009    always flows through the insns made by the first expand_expr
2010    before reaching the other places where the save_expr was evaluated.
2011    You, the caller of save_expr, must make sure this is so.
2012
2013    Constants, and certain read-only nodes, are returned with no
2014    SAVE_EXPR because that is safe.  Expressions containing placeholders
2015    are not touched; see tree.def for an explanation of what these
2016    are used for.  */
2017
2018 tree
2019 save_expr (tree expr)
2020 {
2021   tree t = fold (expr);
2022   tree inner;
2023
2024   /* If the tree evaluates to a constant, then we don't want to hide that
2025      fact (i.e. this allows further folding, and direct checks for constants).
2026      However, a read-only object that has side effects cannot be bypassed.
2027      Since it is no problem to reevaluate literals, we just return the
2028      literal node.  */
2029   inner = skip_simple_arithmetic (t);
2030
2031   if (TREE_INVARIANT (inner)
2032       || (TREE_READONLY (inner) && ! TREE_SIDE_EFFECTS (inner))
2033       || TREE_CODE (inner) == SAVE_EXPR
2034       || TREE_CODE (inner) == ERROR_MARK)
2035     return t;
2036
2037   /* If INNER contains a PLACEHOLDER_EXPR, we must evaluate it each time, since
2038      it means that the size or offset of some field of an object depends on
2039      the value within another field.
2040
2041      Note that it must not be the case that T contains both a PLACEHOLDER_EXPR
2042      and some variable since it would then need to be both evaluated once and
2043      evaluated more than once.  Front-ends must assure this case cannot
2044      happen by surrounding any such subexpressions in their own SAVE_EXPR
2045      and forcing evaluation at the proper time.  */
2046   if (contains_placeholder_p (inner))
2047     return t;
2048
2049   t = build1 (SAVE_EXPR, TREE_TYPE (expr), t);
2050
2051   /* This expression might be placed ahead of a jump to ensure that the
2052      value was computed on both sides of the jump.  So make sure it isn't
2053      eliminated as dead.  */
2054   TREE_SIDE_EFFECTS (t) = 1;
2055   TREE_INVARIANT (t) = 1;
2056   return t;
2057 }
2058
2059 /* Look inside EXPR and into any simple arithmetic operations.  Return
2060    the innermost non-arithmetic node.  */
2061
2062 tree
2063 skip_simple_arithmetic (tree expr)
2064 {
2065   tree inner;
2066
2067   /* We don't care about whether this can be used as an lvalue in this
2068      context.  */
2069   while (TREE_CODE (expr) == NON_LVALUE_EXPR)
2070     expr = TREE_OPERAND (expr, 0);
2071
2072   /* If we have simple operations applied to a SAVE_EXPR or to a SAVE_EXPR and
2073      a constant, it will be more efficient to not make another SAVE_EXPR since
2074      it will allow better simplification and GCSE will be able to merge the
2075      computations if they actually occur.  */
2076   inner = expr;
2077   while (1)
2078     {
2079       if (UNARY_CLASS_P (inner))
2080         inner = TREE_OPERAND (inner, 0);
2081       else if (BINARY_CLASS_P (inner))
2082         {
2083           if (TREE_INVARIANT (TREE_OPERAND (inner, 1)))
2084             inner = TREE_OPERAND (inner, 0);
2085           else if (TREE_INVARIANT (TREE_OPERAND (inner, 0)))
2086             inner = TREE_OPERAND (inner, 1);
2087           else
2088             break;
2089         }
2090       else
2091         break;
2092     }
2093
2094   return inner;
2095 }
2096
2097 /* Return which tree structure is used by T.  */
2098
2099 enum tree_node_structure_enum
2100 tree_node_structure (tree t)
2101 {
2102   enum tree_code code = TREE_CODE (t);
2103
2104   switch (TREE_CODE_CLASS (code))
2105     {
2106     case tcc_declaration:
2107       {
2108         switch (code)
2109           {
2110           case FIELD_DECL:
2111             return TS_FIELD_DECL;
2112           case PARM_DECL:
2113             return TS_PARM_DECL;
2114           case VAR_DECL:
2115             return TS_VAR_DECL;
2116           case LABEL_DECL:
2117             return TS_LABEL_DECL;
2118           case RESULT_DECL:
2119             return TS_RESULT_DECL;
2120           case CONST_DECL:
2121             return TS_CONST_DECL;
2122           case TYPE_DECL:
2123             return TS_TYPE_DECL;
2124           case FUNCTION_DECL:
2125             return TS_FUNCTION_DECL;
2126           case SYMBOL_MEMORY_TAG:
2127           case NAME_MEMORY_TAG:
2128           case STRUCT_FIELD_TAG:
2129             return TS_MEMORY_TAG;
2130           default:
2131             return TS_DECL_NON_COMMON;
2132           }
2133       }
2134     case tcc_type:
2135       return TS_TYPE;
2136     case tcc_reference:
2137     case tcc_comparison:
2138     case tcc_unary:
2139     case tcc_binary:
2140     case tcc_expression:
2141     case tcc_statement:
2142       return TS_EXP;
2143     default:  /* tcc_constant and tcc_exceptional */
2144       break;
2145     }
2146   switch (code)
2147     {
2148       /* tcc_constant cases.  */
2149     case INTEGER_CST:           return TS_INT_CST;
2150     case REAL_CST:              return TS_REAL_CST;
2151     case COMPLEX_CST:           return TS_COMPLEX;
2152     case VECTOR_CST:            return TS_VECTOR;
2153     case STRING_CST:            return TS_STRING;
2154       /* tcc_exceptional cases.  */
2155     case ERROR_MARK:            return TS_COMMON;
2156     case IDENTIFIER_NODE:       return TS_IDENTIFIER;
2157     case TREE_LIST:             return TS_LIST;
2158     case TREE_VEC:              return TS_VEC;
2159     case PHI_NODE:              return TS_PHI_NODE;
2160     case SSA_NAME:              return TS_SSA_NAME;
2161     case PLACEHOLDER_EXPR:      return TS_COMMON;
2162     case STATEMENT_LIST:        return TS_STATEMENT_LIST;
2163     case BLOCK:                 return TS_BLOCK;
2164     case CONSTRUCTOR:           return TS_CONSTRUCTOR;
2165     case TREE_BINFO:            return TS_BINFO;
2166     case VALUE_HANDLE:          return TS_VALUE_HANDLE;
2167     case OMP_CLAUSE:            return TS_OMP_CLAUSE;
2168
2169     default:
2170       gcc_unreachable ();
2171     }
2172 }
2173 \f
2174 /* Return 1 if EXP contains a PLACEHOLDER_EXPR; i.e., if it represents a size
2175    or offset that depends on a field within a record.  */
2176
2177 bool
2178 contains_placeholder_p (tree exp)
2179 {
2180   enum tree_code code;
2181
2182   if (!exp)
2183     return 0;
2184
2185   code = TREE_CODE (exp);
2186   if (code == PLACEHOLDER_EXPR)
2187     return 1;
2188
2189   switch (TREE_CODE_CLASS (code))
2190     {
2191     case tcc_reference:
2192       /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit
2193          position computations since they will be converted into a
2194          WITH_RECORD_EXPR involving the reference, which will assume
2195          here will be valid.  */
2196       return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
2197
2198     case tcc_exceptional:
2199       if (code == TREE_LIST)
2200         return (CONTAINS_PLACEHOLDER_P (TREE_VALUE (exp))
2201                 || CONTAINS_PLACEHOLDER_P (TREE_CHAIN (exp)));
2202       break;
2203
2204     case tcc_unary:
2205     case tcc_binary:
2206     case tcc_comparison:
2207     case tcc_expression:
2208       switch (code)
2209         {
2210         case COMPOUND_EXPR:
2211           /* Ignoring the first operand isn't quite right, but works best.  */
2212           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
2213
2214         case COND_EXPR:
2215           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
2216                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))
2217                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2)));
2218
2219         case CALL_EXPR:
2220           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
2221
2222         default:
2223           break;
2224         }
2225
2226       switch (TREE_CODE_LENGTH (code))
2227         {
2228         case 1:
2229           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
2230         case 2:
2231           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
2232                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)));
2233         default:
2234           return 0;
2235         }
2236
2237     default:
2238       return 0;
2239     }
2240   return 0;
2241 }
2242
2243 /* Return true if any part of the computation of TYPE involves a
2244    PLACEHOLDER_EXPR.  This includes size, bounds, qualifiers
2245    (for QUAL_UNION_TYPE) and field positions.  */
2246
2247 static bool
2248 type_contains_placeholder_1 (tree type)
2249 {
2250   /* If the size contains a placeholder or the parent type (component type in
2251      the case of arrays) type involves a placeholder, this type does.  */
2252   if (CONTAINS_PLACEHOLDER_P (TYPE_SIZE (type))
2253       || CONTAINS_PLACEHOLDER_P (TYPE_SIZE_UNIT (type))
2254       || (TREE_TYPE (type) != 0
2255           && type_contains_placeholder_p (TREE_TYPE (type))))
2256     return true;
2257
2258   /* Now do type-specific checks.  Note that the last part of the check above
2259      greatly limits what we have to do below.  */
2260   switch (TREE_CODE (type))
2261     {
2262     case VOID_TYPE:
2263     case COMPLEX_TYPE:
2264     case ENUMERAL_TYPE:
2265     case BOOLEAN_TYPE:
2266     case POINTER_TYPE:
2267     case OFFSET_TYPE:
2268     case REFERENCE_TYPE:
2269     case METHOD_TYPE:
2270     case FUNCTION_TYPE:
2271     case VECTOR_TYPE:
2272       return false;
2273
2274     case INTEGER_TYPE:
2275     case REAL_TYPE:
2276       /* Here we just check the bounds.  */
2277       return (CONTAINS_PLACEHOLDER_P (TYPE_MIN_VALUE (type))
2278               || CONTAINS_PLACEHOLDER_P (TYPE_MAX_VALUE (type)));
2279
2280     case ARRAY_TYPE:
2281       /* We're already checked the component type (TREE_TYPE), so just check
2282          the index type.  */
2283       return type_contains_placeholder_p (TYPE_DOMAIN (type));
2284
2285     case RECORD_TYPE:
2286     case UNION_TYPE:
2287     case QUAL_UNION_TYPE:
2288       {
2289         tree field;
2290
2291         for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2292           if (TREE_CODE (field) == FIELD_DECL
2293               && (CONTAINS_PLACEHOLDER_P (DECL_FIELD_OFFSET (field))
2294                   || (TREE_CODE (type) == QUAL_UNION_TYPE
2295                       && CONTAINS_PLACEHOLDER_P (DECL_QUALIFIER (field)))
2296                   || type_contains_placeholder_p (TREE_TYPE (field))))
2297             return true;
2298
2299         return false;
2300       }
2301
2302     default:
2303       gcc_unreachable ();
2304     }
2305 }
2306
2307 bool
2308 type_contains_placeholder_p (tree type)
2309 {
2310   bool result;
2311
2312   /* If the contains_placeholder_bits field has been initialized,
2313      then we know the answer.  */
2314   if (TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) > 0)
2315     return TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) - 1;
2316
2317   /* Indicate that we've seen this type node, and the answer is false.
2318      This is what we want to return if we run into recursion via fields.  */
2319   TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = 1;
2320
2321   /* Compute the real value.  */
2322   result = type_contains_placeholder_1 (type);
2323
2324   /* Store the real value.  */
2325   TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = result + 1;
2326
2327   return result;
2328 }
2329 \f
2330 /* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
2331    return a tree with all occurrences of references to F in a
2332    PLACEHOLDER_EXPR replaced by R.   Note that we assume here that EXP
2333    contains only arithmetic expressions or a CALL_EXPR with a
2334    PLACEHOLDER_EXPR occurring only in its arglist.  */
2335
2336 tree
2337 substitute_in_expr (tree exp, tree f, tree r)
2338 {
2339   enum tree_code code = TREE_CODE (exp);
2340   tree op0, op1, op2, op3;
2341   tree new;
2342   tree inner;
2343
2344   /* We handle TREE_LIST and COMPONENT_REF separately.  */
2345   if (code == TREE_LIST)
2346     {
2347       op0 = SUBSTITUTE_IN_EXPR (TREE_CHAIN (exp), f, r);
2348       op1 = SUBSTITUTE_IN_EXPR (TREE_VALUE (exp), f, r);
2349       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2350         return exp;
2351
2352       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2353     }
2354   else if (code == COMPONENT_REF)
2355    {
2356      /* If this expression is getting a value from a PLACEHOLDER_EXPR
2357         and it is the right field, replace it with R.  */
2358      for (inner = TREE_OPERAND (exp, 0);
2359           REFERENCE_CLASS_P (inner);
2360           inner = TREE_OPERAND (inner, 0))
2361        ;
2362      if (TREE_CODE (inner) == PLACEHOLDER_EXPR
2363          && TREE_OPERAND (exp, 1) == f)
2364        return r;
2365
2366      /* If this expression hasn't been completed let, leave it alone.  */
2367      if (TREE_CODE (inner) == PLACEHOLDER_EXPR && TREE_TYPE (inner) == 0)
2368        return exp;
2369
2370      op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2371      if (op0 == TREE_OPERAND (exp, 0))
2372        return exp;
2373
2374      new = fold_build3 (COMPONENT_REF, TREE_TYPE (exp),
2375                         op0, TREE_OPERAND (exp, 1), NULL_TREE);
2376    }
2377   else
2378     switch (TREE_CODE_CLASS (code))
2379       {
2380       case tcc_constant:
2381       case tcc_declaration:
2382         return exp;
2383
2384       case tcc_exceptional:
2385       case tcc_unary:
2386       case tcc_binary:
2387       case tcc_comparison:
2388       case tcc_expression:
2389       case tcc_reference:
2390         switch (TREE_CODE_LENGTH (code))
2391           {
2392           case 0:
2393             return exp;
2394
2395           case 1:
2396             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2397             if (op0 == TREE_OPERAND (exp, 0))
2398               return exp;
2399
2400             new = fold_build1 (code, TREE_TYPE (exp), op0);
2401             break;
2402
2403           case 2:
2404             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2405             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2406
2407             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2408               return exp;
2409
2410             new = fold_build2 (code, TREE_TYPE (exp), op0, op1);
2411             break;
2412
2413           case 3:
2414             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2415             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2416             op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
2417
2418             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2419                 && op2 == TREE_OPERAND (exp, 2))
2420               return exp;
2421
2422             new = fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2423             break;
2424
2425           case 4:
2426             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2427             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2428             op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
2429             op3 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 3), f, r);
2430
2431             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2432                 && op2 == TREE_OPERAND (exp, 2)
2433                 && op3 == TREE_OPERAND (exp, 3))
2434               return exp;
2435
2436             new = fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2437             break;
2438
2439           default:
2440             gcc_unreachable ();
2441           }
2442         break;
2443
2444       default:
2445         gcc_unreachable ();
2446       }
2447
2448   TREE_READONLY (new) = TREE_READONLY (exp);
2449   return new;
2450 }
2451
2452 /* Similar, but look for a PLACEHOLDER_EXPR in EXP and find a replacement
2453    for it within OBJ, a tree that is an object or a chain of references.  */
2454
2455 tree
2456 substitute_placeholder_in_expr (tree exp, tree obj)
2457 {
2458   enum tree_code code = TREE_CODE (exp);
2459   tree op0, op1, op2, op3;
2460
2461   /* If this is a PLACEHOLDER_EXPR, see if we find a corresponding type
2462      in the chain of OBJ.  */
2463   if (code == PLACEHOLDER_EXPR)
2464     {
2465       tree need_type = TYPE_MAIN_VARIANT (TREE_TYPE (exp));
2466       tree elt;
2467
2468       for (elt = obj; elt != 0;
2469            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2470                    || TREE_CODE (elt) == COND_EXPR)
2471                   ? TREE_OPERAND (elt, 1)
2472                   : (REFERENCE_CLASS_P (elt)
2473                      || UNARY_CLASS_P (elt)
2474                      || BINARY_CLASS_P (elt)
2475                      || EXPRESSION_CLASS_P (elt))
2476                   ? TREE_OPERAND (elt, 0) : 0))
2477         if (TYPE_MAIN_VARIANT (TREE_TYPE (elt)) == need_type)
2478           return elt;
2479
2480       for (elt = obj; elt != 0;
2481            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2482                    || TREE_CODE (elt) == COND_EXPR)
2483                   ? TREE_OPERAND (elt, 1)
2484                   : (REFERENCE_CLASS_P (elt)
2485                      || UNARY_CLASS_P (elt)
2486                      || BINARY_CLASS_P (elt)
2487                      || EXPRESSION_CLASS_P (elt))
2488                   ? TREE_OPERAND (elt, 0) : 0))
2489         if (POINTER_TYPE_P (TREE_TYPE (elt))
2490             && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (elt)))
2491                 == need_type))
2492           return fold_build1 (INDIRECT_REF, need_type, elt);
2493
2494       /* If we didn't find it, return the original PLACEHOLDER_EXPR.  If it
2495          survives until RTL generation, there will be an error.  */
2496       return exp;
2497     }
2498
2499   /* TREE_LIST is special because we need to look at TREE_VALUE
2500      and TREE_CHAIN, not TREE_OPERANDS.  */
2501   else if (code == TREE_LIST)
2502     {
2503       op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), obj);
2504       op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), obj);
2505       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2506         return exp;
2507
2508       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2509     }
2510   else
2511     switch (TREE_CODE_CLASS (code))
2512       {
2513       case tcc_constant:
2514       case tcc_declaration:
2515         return exp;
2516
2517       case tcc_exceptional:
2518       case tcc_unary:
2519       case tcc_binary:
2520       case tcc_comparison:
2521       case tcc_expression:
2522       case tcc_reference:
2523       case tcc_statement:
2524         switch (TREE_CODE_LENGTH (code))
2525           {
2526           case 0:
2527             return exp;
2528
2529           case 1:
2530             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2531             if (op0 == TREE_OPERAND (exp, 0))
2532               return exp;
2533             else
2534               return fold_build1 (code, TREE_TYPE (exp), op0);
2535
2536           case 2:
2537             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2538             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2539
2540             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2541               return exp;
2542             else
2543               return fold_build2 (code, TREE_TYPE (exp), op0, op1);
2544
2545           case 3:
2546             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2547             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2548             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2549
2550             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2551                 && op2 == TREE_OPERAND (exp, 2))
2552               return exp;
2553             else
2554               return fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2555
2556           case 4:
2557             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2558             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2559             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2560             op3 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 3), obj);
2561
2562             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2563                 && op2 == TREE_OPERAND (exp, 2)
2564                 && op3 == TREE_OPERAND (exp, 3))
2565               return exp;
2566             else
2567               return fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2568
2569           default:
2570             gcc_unreachable ();
2571           }
2572         break;
2573
2574       default:
2575         gcc_unreachable ();
2576       }
2577 }
2578 \f
2579 /* Stabilize a reference so that we can use it any number of times
2580    without causing its operands to be evaluated more than once.
2581    Returns the stabilized reference.  This works by means of save_expr,
2582    so see the caveats in the comments about save_expr.
2583
2584    Also allows conversion expressions whose operands are references.
2585    Any other kind of expression is returned unchanged.  */
2586
2587 tree
2588 stabilize_reference (tree ref)
2589 {
2590   tree result;
2591   enum tree_code code = TREE_CODE (ref);
2592
2593   switch (code)
2594     {
2595     case VAR_DECL:
2596     case PARM_DECL:
2597     case RESULT_DECL:
2598       /* No action is needed in this case.  */
2599       return ref;
2600
2601     case NOP_EXPR:
2602     case CONVERT_EXPR:
2603     case FLOAT_EXPR:
2604     case FIX_TRUNC_EXPR:
2605     case FIX_FLOOR_EXPR:
2606     case FIX_ROUND_EXPR:
2607     case FIX_CEIL_EXPR:
2608       result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
2609       break;
2610
2611     case INDIRECT_REF:
2612       result = build_nt (INDIRECT_REF,
2613                          stabilize_reference_1 (TREE_OPERAND (ref, 0)));
2614       break;
2615
2616     case COMPONENT_REF:
2617       result = build_nt (COMPONENT_REF,
2618                          stabilize_reference (TREE_OPERAND (ref, 0)),
2619                          TREE_OPERAND (ref, 1), NULL_TREE);
2620       break;
2621
2622     case BIT_FIELD_REF:
2623       result = build_nt (BIT_FIELD_REF,
2624                          stabilize_reference (TREE_OPERAND (ref, 0)),
2625                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2626                          stabilize_reference_1 (TREE_OPERAND (ref, 2)));
2627       break;
2628
2629     case ARRAY_REF:
2630       result = build_nt (ARRAY_REF,
2631                          stabilize_reference (TREE_OPERAND (ref, 0)),
2632                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2633                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2634       break;
2635
2636     case ARRAY_RANGE_REF:
2637       result = build_nt (ARRAY_RANGE_REF,
2638                          stabilize_reference (TREE_OPERAND (ref, 0)),
2639                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2640                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2641       break;
2642
2643     case COMPOUND_EXPR:
2644       /* We cannot wrap the first expression in a SAVE_EXPR, as then
2645          it wouldn't be ignored.  This matters when dealing with
2646          volatiles.  */
2647       return stabilize_reference_1 (ref);
2648
2649       /* If arg isn't a kind of lvalue we recognize, make no change.
2650          Caller should recognize the error for an invalid lvalue.  */
2651     default:
2652       return ref;
2653
2654     case ERROR_MARK:
2655       return error_mark_node;
2656     }
2657
2658   TREE_TYPE (result) = TREE_TYPE (ref);
2659   TREE_READONLY (result) = TREE_READONLY (ref);
2660   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
2661   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
2662
2663   return result;
2664 }
2665
2666 /* Subroutine of stabilize_reference; this is called for subtrees of
2667    references.  Any expression with side-effects must be put in a SAVE_EXPR
2668    to ensure that it is only evaluated once.
2669
2670    We don't put SAVE_EXPR nodes around everything, because assigning very
2671    simple expressions to temporaries causes us to miss good opportunities
2672    for optimizations.  Among other things, the opportunity to fold in the
2673    addition of a constant into an addressing mode often gets lost, e.g.
2674    "y[i+1] += x;".  In general, we take the approach that we should not make
2675    an assignment unless we are forced into it - i.e., that any non-side effect
2676    operator should be allowed, and that cse should take care of coalescing
2677    multiple utterances of the same expression should that prove fruitful.  */
2678
2679 tree
2680 stabilize_reference_1 (tree e)
2681 {
2682   tree result;
2683   enum tree_code code = TREE_CODE (e);
2684
2685   /* We cannot ignore const expressions because it might be a reference
2686      to a const array but whose index contains side-effects.  But we can
2687      ignore things that are actual constant or that already have been
2688      handled by this function.  */
2689
2690   if (TREE_INVARIANT (e))
2691     return e;
2692
2693   switch (TREE_CODE_CLASS (code))
2694     {
2695     case tcc_exceptional:
2696     case tcc_type:
2697     case tcc_declaration:
2698     case tcc_comparison:
2699     case tcc_statement:
2700     case tcc_expression:
2701     case tcc_reference:
2702       /* If the expression has side-effects, then encase it in a SAVE_EXPR
2703          so that it will only be evaluated once.  */
2704       /* The reference (r) and comparison (<) classes could be handled as
2705          below, but it is generally faster to only evaluate them once.  */
2706       if (TREE_SIDE_EFFECTS (e))
2707         return save_expr (e);
2708       return e;
2709
2710     case tcc_constant:
2711       /* Constants need no processing.  In fact, we should never reach
2712          here.  */
2713       return e;
2714
2715     case tcc_binary:
2716       /* Division is slow and tends to be compiled with jumps,
2717          especially the division by powers of 2 that is often
2718          found inside of an array reference.  So do it just once.  */
2719       if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
2720           || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
2721           || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
2722           || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
2723         return save_expr (e);
2724       /* Recursively stabilize each operand.  */
2725       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
2726                          stabilize_reference_1 (TREE_OPERAND (e, 1)));
2727       break;
2728
2729     case tcc_unary:
2730       /* Recursively stabilize each operand.  */
2731       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
2732       break;
2733
2734     default:
2735       gcc_unreachable ();
2736     }
2737
2738   TREE_TYPE (result) = TREE_TYPE (e);
2739   TREE_READONLY (result) = TREE_READONLY (e);
2740   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
2741   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
2742   TREE_INVARIANT (result) = 1;
2743
2744   return result;
2745 }
2746 \f
2747 /* Low-level constructors for expressions.  */
2748
2749 /* A helper function for build1 and constant folders.  Set TREE_CONSTANT,
2750    TREE_INVARIANT, and TREE_SIDE_EFFECTS for an ADDR_EXPR.  */
2751
2752 void
2753 recompute_tree_invariant_for_addr_expr (tree t)
2754 {
2755   tree node;
2756   bool tc = true, ti = true, se = false;
2757
2758   /* We started out assuming this address is both invariant and constant, but
2759      does not have side effects.  Now go down any handled components and see if
2760      any of them involve offsets that are either non-constant or non-invariant.
2761      Also check for side-effects.
2762
2763      ??? Note that this code makes no attempt to deal with the case where
2764      taking the address of something causes a copy due to misalignment.  */
2765
2766 #define UPDATE_TITCSE(NODE)  \
2767 do { tree _node = (NODE); \
2768      if (_node && !TREE_INVARIANT (_node)) ti = false; \
2769      if (_node && !TREE_CONSTANT (_node)) tc = false; \
2770      if (_node && TREE_SIDE_EFFECTS (_node)) se = true; } while (0)
2771
2772   for (node = TREE_OPERAND (t, 0); handled_component_p (node);
2773        node = TREE_OPERAND (node, 0))
2774     {
2775       /* If the first operand doesn't have an ARRAY_TYPE, this is a bogus
2776          array reference (probably made temporarily by the G++ front end),
2777          so ignore all the operands.  */
2778       if ((TREE_CODE (node) == ARRAY_REF
2779            || TREE_CODE (node) == ARRAY_RANGE_REF)
2780           && TREE_CODE (TREE_TYPE (TREE_OPERAND (node, 0))) == ARRAY_TYPE)
2781         {
2782           UPDATE_TITCSE (TREE_OPERAND (node, 1));
2783           if (TREE_OPERAND (node, 2))
2784             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2785           if (TREE_OPERAND (node, 3))
2786             UPDATE_TITCSE (TREE_OPERAND (node, 3));
2787         }
2788       /* Likewise, just because this is a COMPONENT_REF doesn't mean we have a
2789          FIELD_DECL, apparently.  The G++ front end can put something else
2790          there, at least temporarily.  */
2791       else if (TREE_CODE (node) == COMPONENT_REF
2792                && TREE_CODE (TREE_OPERAND (node, 1)) == FIELD_DECL)
2793         {
2794           if (TREE_OPERAND (node, 2))
2795             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2796         }
2797       else if (TREE_CODE (node) == BIT_FIELD_REF)
2798         UPDATE_TITCSE (TREE_OPERAND (node, 2));
2799     }
2800
2801   node = lang_hooks.expr_to_decl (node, &tc, &ti, &se);
2802
2803   /* Now see what's inside.  If it's an INDIRECT_REF, copy our properties from
2804      the address, since &(*a)->b is a form of addition.  If it's a decl, it's
2805      invariant and constant if the decl is static.  It's also invariant if it's
2806      a decl in the current function.  Taking the address of a volatile variable
2807      is not volatile.  If it's a constant, the address is both invariant and
2808      constant.  Otherwise it's neither.  */
2809   if (TREE_CODE (node) == INDIRECT_REF)
2810     UPDATE_TITCSE (TREE_OPERAND (node, 0));
2811   else if (DECL_P (node))
2812     {
2813       if (staticp (node))
2814         ;
2815       else if (decl_function_context (node) == current_function_decl
2816                /* Addresses of thread-local variables are invariant.  */
2817                || (TREE_CODE (node) == VAR_DECL
2818                    && DECL_THREAD_LOCAL_P (node)))
2819         tc = false;
2820       else
2821         ti = tc = false;
2822     }
2823   else if (CONSTANT_CLASS_P (node))
2824     ;
2825   else
2826     {
2827       ti = tc = false;
2828       se |= TREE_SIDE_EFFECTS (node);
2829     }
2830
2831   TREE_CONSTANT (t) = tc;
2832   TREE_INVARIANT (t) = ti;
2833   TREE_SIDE_EFFECTS (t) = se;
2834 #undef UPDATE_TITCSE
2835 }
2836
2837 /* Build an expression of code CODE, data type TYPE, and operands as
2838    specified.  Expressions and reference nodes can be created this way.
2839    Constants, decls, types and misc nodes cannot be.
2840
2841    We define 5 non-variadic functions, from 0 to 4 arguments.  This is
2842    enough for all extant tree codes.  */
2843
2844 tree
2845 build0_stat (enum tree_code code, tree tt MEM_STAT_DECL)
2846 {
2847   tree t;
2848
2849   gcc_assert (TREE_CODE_LENGTH (code) == 0);
2850
2851   t = make_node_stat (code PASS_MEM_STAT);
2852   TREE_TYPE (t) = tt;
2853
2854   return t;
2855 }
2856
2857 tree
2858 build1_stat (enum tree_code code, tree type, tree node MEM_STAT_DECL)
2859 {
2860   int length = sizeof (struct tree_exp);
2861 #ifdef GATHER_STATISTICS
2862   tree_node_kind kind;
2863 #endif
2864   tree t;
2865
2866 #ifdef GATHER_STATISTICS
2867   switch (TREE_CODE_CLASS (code))
2868     {
2869     case tcc_statement:  /* an expression with side effects */
2870       kind = s_kind;
2871       break;
2872     case tcc_reference:  /* a reference */
2873       kind = r_kind;
2874       break;
2875     default:
2876       kind = e_kind;
2877       break;
2878     }
2879
2880   tree_node_counts[(int) kind]++;
2881   tree_node_sizes[(int) kind] += length;
2882 #endif
2883
2884   gcc_assert (TREE_CODE_LENGTH (code) == 1);
2885
2886   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
2887
2888   memset (t, 0, sizeof (struct tree_common));
2889
2890   TREE_SET_CODE (t, code);
2891
2892   TREE_TYPE (t) = type;
2893 #ifdef USE_MAPPED_LOCATION
2894   SET_EXPR_LOCATION (t, UNKNOWN_LOCATION);
2895 #else
2896   SET_EXPR_LOCUS (t, NULL);
2897 #endif
2898   TREE_COMPLEXITY (t) = 0;
2899   TREE_OPERAND (t, 0) = node;
2900   TREE_BLOCK (t) = NULL_TREE;
2901   if (node && !TYPE_P (node))
2902     {
2903       TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
2904       TREE_READONLY (t) = TREE_READONLY (node);
2905     }
2906
2907   if (TREE_CODE_CLASS (code) == tcc_statement)
2908     TREE_SIDE_EFFECTS (t) = 1;
2909   else switch (code)
2910     {
2911     case VA_ARG_EXPR:
2912       /* All of these have side-effects, no matter what their
2913          operands are.  */
2914       TREE_SIDE_EFFECTS (t) = 1;
2915       TREE_READONLY (t) = 0;
2916       break;
2917
2918     case MISALIGNED_INDIRECT_REF:
2919     case ALIGN_INDIRECT_REF:
2920     case INDIRECT_REF:
2921       /* Whether a dereference is readonly has nothing to do with whether
2922          its operand is readonly.  */
2923       TREE_READONLY (t) = 0;
2924       break;
2925
2926     case ADDR_EXPR:
2927       if (node)
2928         recompute_tree_invariant_for_addr_expr (t);
2929       break;
2930
2931     default:
2932       if ((TREE_CODE_CLASS (code) == tcc_unary || code == VIEW_CONVERT_EXPR)
2933           && node && !TYPE_P (node)
2934           && TREE_CONSTANT (node))
2935         TREE_CONSTANT (t) = 1;
2936       if ((TREE_CODE_CLASS (code) == tcc_unary || code == VIEW_CONVERT_EXPR)
2937           && node && TREE_INVARIANT (node))
2938         TREE_INVARIANT (t) = 1;
2939       if (TREE_CODE_CLASS (code) == tcc_reference
2940           && node && TREE_THIS_VOLATILE (node))
2941         TREE_THIS_VOLATILE (t) = 1;
2942       break;
2943     }
2944
2945   return t;
2946 }
2947
2948 #define PROCESS_ARG(N)                  \
2949   do {                                  \
2950     TREE_OPERAND (t, N) = arg##N;       \
2951     if (arg##N &&!TYPE_P (arg##N))      \
2952       {                                 \
2953         if (TREE_SIDE_EFFECTS (arg##N)) \
2954           side_effects = 1;             \
2955         if (!TREE_READONLY (arg##N))    \
2956           read_only = 0;                \
2957         if (!TREE_CONSTANT (arg##N))    \
2958           constant = 0;                 \
2959         if (!TREE_INVARIANT (arg##N))   \
2960           invariant = 0;                \
2961       }                                 \
2962   } while (0)
2963
2964 tree
2965 build2_stat (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL)
2966 {
2967   bool constant, read_only, side_effects, invariant;
2968   tree t;
2969
2970   gcc_assert (TREE_CODE_LENGTH (code) == 2);
2971
2972   t = make_node_stat (code PASS_MEM_STAT);
2973   TREE_TYPE (t) = tt;
2974
2975   /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
2976      result based on those same flags for the arguments.  But if the
2977      arguments aren't really even `tree' expressions, we shouldn't be trying
2978      to do this.  */
2979
2980   /* Expressions without side effects may be constant if their
2981      arguments are as well.  */
2982   constant = (TREE_CODE_CLASS (code) == tcc_comparison
2983               || TREE_CODE_CLASS (code) == tcc_binary);
2984   read_only = 1;
2985   side_effects = TREE_SIDE_EFFECTS (t);
2986   invariant = constant;
2987
2988   PROCESS_ARG(0);
2989   PROCESS_ARG(1);
2990
2991   TREE_READONLY (t) = read_only;
2992   TREE_CONSTANT (t) = constant;
2993   TREE_INVARIANT (t) = invariant;
2994   TREE_SIDE_EFFECTS (t) = side_effects;
2995   TREE_THIS_VOLATILE (t)
2996     = (TREE_CODE_CLASS (code) == tcc_reference
2997        && arg0 && TREE_THIS_VOLATILE (arg0));
2998
2999   return t;
3000 }
3001
3002 tree
3003 build3_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3004              tree arg2 MEM_STAT_DECL)
3005 {
3006   bool constant, read_only, side_effects, invariant;
3007   tree t;
3008
3009   gcc_assert (TREE_CODE_LENGTH (code) == 3);
3010
3011   t = make_node_stat (code PASS_MEM_STAT);
3012   TREE_TYPE (t) = tt;
3013
3014   side_effects = TREE_SIDE_EFFECTS (t);
3015
3016   PROCESS_ARG(0);
3017   PROCESS_ARG(1);
3018   PROCESS_ARG(2);
3019
3020   if (code == CALL_EXPR && !side_effects)
3021     {
3022       tree node;
3023       int i;
3024
3025       /* Calls have side-effects, except those to const or
3026          pure functions.  */
3027       i = call_expr_flags (t);
3028       if (!(i & (ECF_CONST | ECF_PURE)))
3029         side_effects = 1;
3030
3031       /* And even those have side-effects if their arguments do.  */
3032       else for (node = arg1; node; node = TREE_CHAIN (node))
3033         if (TREE_SIDE_EFFECTS (TREE_VALUE (node)))
3034           {
3035             side_effects = 1;
3036             break;
3037           }
3038     }
3039
3040   TREE_SIDE_EFFECTS (t) = side_effects;
3041   TREE_THIS_VOLATILE (t)
3042     = (TREE_CODE_CLASS (code) == tcc_reference
3043        && arg0 && TREE_THIS_VOLATILE (arg0));
3044
3045   return t;
3046 }
3047
3048 tree
3049 build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3050              tree arg2, tree arg3 MEM_STAT_DECL)
3051 {
3052   bool constant, read_only, side_effects, invariant;
3053   tree t;
3054
3055   gcc_assert (TREE_CODE_LENGTH (code) == 4);
3056
3057   t = make_node_stat (code PASS_MEM_STAT);
3058   TREE_TYPE (t) = tt;
3059
3060   side_effects = TREE_SIDE_EFFECTS (t);
3061
3062   PROCESS_ARG(0);
3063   PROCESS_ARG(1);
3064   PROCESS_ARG(2);
3065   PROCESS_ARG(3);
3066
3067   TREE_SIDE_EFFECTS (t) = side_effects;
3068   TREE_THIS_VOLATILE (t)
3069     = (TREE_CODE_CLASS (code) == tcc_reference
3070        && arg0 && TREE_THIS_VOLATILE (arg0));
3071
3072   return t;
3073 }
3074
3075 tree
3076 build5_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3077              tree arg2, tree arg3, tree arg4 MEM_STAT_DECL)
3078 {
3079   bool constant, read_only, side_effects, invariant;
3080   tree t;
3081
3082   gcc_assert (TREE_CODE_LENGTH (code) == 5);
3083
3084   t = make_node_stat (code PASS_MEM_STAT);
3085   TREE_TYPE (t) = tt;
3086
3087   side_effects = TREE_SIDE_EFFECTS (t);
3088
3089   PROCESS_ARG(0);
3090   PROCESS_ARG(1);
3091   PROCESS_ARG(2);
3092   PROCESS_ARG(3);
3093   PROCESS_ARG(4);
3094
3095   TREE_SIDE_EFFECTS (t) = side_effects;
3096   TREE_THIS_VOLATILE (t)
3097     = (TREE_CODE_CLASS (code) == tcc_reference
3098        && arg0 && TREE_THIS_VOLATILE (arg0));
3099
3100   return t;
3101 }
3102
3103 tree
3104 build7_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3105              tree arg2, tree arg3, tree arg4, tree arg5,
3106              tree arg6 MEM_STAT_DECL)
3107 {
3108   bool constant, read_only, side_effects, invariant;
3109   tree t;
3110
3111   gcc_assert (code == TARGET_MEM_REF);
3112
3113   t = make_node_stat (code PASS_MEM_STAT);
3114   TREE_TYPE (t) = tt;
3115
3116   side_effects = TREE_SIDE_EFFECTS (t);
3117
3118   PROCESS_ARG(0);
3119   PROCESS_ARG(1);
3120   PROCESS_ARG(2);
3121   PROCESS_ARG(3);
3122   PROCESS_ARG(4);
3123   PROCESS_ARG(5);
3124   PROCESS_ARG(6);
3125
3126   TREE_SIDE_EFFECTS (t) = side_effects;
3127   TREE_THIS_VOLATILE (t) = 0;
3128
3129   return t;
3130 }
3131
3132 /* Similar except don't specify the TREE_TYPE
3133    and leave the TREE_SIDE_EFFECTS as 0.
3134    It is permissible for arguments to be null,
3135    or even garbage if their values do not matter.  */
3136
3137 tree
3138 build_nt (enum tree_code code, ...)
3139 {
3140   tree t;
3141   int length;
3142   int i;
3143   va_list p;
3144
3145   va_start (p, code);
3146
3147   t = make_node (code);
3148   length = TREE_CODE_LENGTH (code);
3149
3150   for (i = 0; i < length; i++)
3151     TREE_OPERAND (t, i) = va_arg (p, tree);
3152
3153   va_end (p);
3154   return t;
3155 }
3156 \f
3157 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
3158    We do NOT enter this node in any sort of symbol table.
3159
3160    layout_decl is used to set up the decl's storage layout.
3161    Other slots are initialized to 0 or null pointers.  */
3162
3163 tree
3164 build_decl_stat (enum tree_code code, tree name, tree type MEM_STAT_DECL)
3165 {
3166   tree t;
3167
3168   t = make_node_stat (code PASS_MEM_STAT);
3169
3170 /*  if (type == error_mark_node)
3171     type = integer_type_node; */
3172 /* That is not done, deliberately, so that having error_mark_node
3173    as the type can suppress useless errors in the use of this variable.  */
3174
3175   DECL_NAME (t) = name;
3176   TREE_TYPE (t) = type;
3177
3178   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
3179     layout_decl (t, 0);
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) { xloc.file = NULL; xloc.line = 0;  xloc.column = 0; }
3229   else
3230     {
3231       const struct line_map *map = linemap_lookup (&line_table, loc);
3232       xloc.file = map->to_file;
3233       xloc.line = SOURCE_LINE (map, loc);
3234       xloc.column = SOURCE_COLUMN (map, loc);
3235     };
3236   return xloc;
3237 }
3238
3239 #else
3240
3241 /* Record the exact location where an expression or an identifier were
3242    encountered.  */
3243
3244 void
3245 annotate_with_file_line (tree node, const char *file, int line)
3246 {
3247   /* Roughly one percent of the calls to this function are to annotate
3248      a node with the same information already attached to that node!
3249      Just return instead of wasting memory.  */
3250   if (EXPR_LOCUS (node)
3251       && EXPR_LINENO (node) == line
3252       && (EXPR_FILENAME (node) == file
3253           || !strcmp (EXPR_FILENAME (node), file)))
3254     {
3255       last_annotated_node = EXPR_LOCUS (node);
3256       return;
3257     }
3258
3259   /* In heavily macroized code (such as GCC itself) this single
3260      entry cache can reduce the number of allocations by more
3261      than half.  */
3262   if (last_annotated_node
3263       && last_annotated_node->line == line
3264       && (last_annotated_node->file == file
3265           || !strcmp (last_annotated_node->file, file)))
3266     {
3267       SET_EXPR_LOCUS (node, last_annotated_node);
3268       return;
3269     }
3270
3271   SET_EXPR_LOCUS (node, ggc_alloc (sizeof (location_t)));
3272   EXPR_LINENO (node) = line;
3273   EXPR_FILENAME (node) = file;
3274   last_annotated_node = EXPR_LOCUS (node);
3275 }
3276
3277 void
3278 annotate_with_locus (tree node, location_t locus)
3279 {
3280   annotate_with_file_line (node, locus.file, locus.line);
3281 }
3282 #endif
3283 \f
3284 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
3285    is ATTRIBUTE.  */
3286
3287 tree
3288 build_decl_attribute_variant (tree ddecl, tree attribute)
3289 {
3290   DECL_ATTRIBUTES (ddecl) = attribute;
3291   return ddecl;
3292 }
3293
3294 /* Borrowed from hashtab.c iterative_hash implementation.  */
3295 #define mix(a,b,c) \
3296 { \
3297   a -= b; a -= c; a ^= (c>>13); \
3298   b -= c; b -= a; b ^= (a<< 8); \
3299   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
3300   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
3301   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
3302   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
3303   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
3304   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
3305   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
3306 }
3307
3308
3309 /* Produce good hash value combining VAL and VAL2.  */
3310 static inline hashval_t
3311 iterative_hash_hashval_t (hashval_t val, hashval_t val2)
3312 {
3313   /* the golden ratio; an arbitrary value.  */
3314   hashval_t a = 0x9e3779b9;
3315
3316   mix (a, val, val2);
3317   return val2;
3318 }
3319
3320 /* Produce good hash value combining PTR and VAL2.  */
3321 static inline hashval_t
3322 iterative_hash_pointer (void *ptr, hashval_t val2)
3323 {
3324   if (sizeof (ptr) == sizeof (hashval_t))
3325     return iterative_hash_hashval_t ((size_t) ptr, val2);
3326   else
3327     {
3328       hashval_t a = (hashval_t) (size_t) ptr;
3329       /* Avoid warnings about shifting of more than the width of the type on
3330          hosts that won't execute this path.  */
3331       int zero = 0;
3332       hashval_t b = (hashval_t) ((size_t) ptr >> (sizeof (hashval_t) * 8 + zero));
3333       mix (a, b, val2);
3334       return val2;
3335     }
3336 }
3337
3338 /* Produce good hash value combining VAL and VAL2.  */
3339 static inline hashval_t
3340 iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
3341 {
3342   if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
3343     return iterative_hash_hashval_t (val, val2);
3344   else
3345     {
3346       hashval_t a = (hashval_t) val;
3347       /* Avoid warnings about shifting of more than the width of the type on
3348          hosts that won't execute this path.  */
3349       int zero = 0;
3350       hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
3351       mix (a, b, val2);
3352       if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
3353         {
3354           hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
3355           hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
3356           mix (a, b, val2);
3357         }
3358       return val2;
3359     }
3360 }
3361
3362 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
3363    is ATTRIBUTE and its qualifiers are QUALS.
3364
3365    Record such modified types already made so we don't make duplicates.  */
3366
3367 static tree
3368 build_type_attribute_qual_variant (tree ttype, tree attribute, int quals)
3369 {
3370   if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
3371     {
3372       hashval_t hashcode = 0;
3373       tree ntype;
3374       enum tree_code code = TREE_CODE (ttype);
3375
3376       ntype = copy_node (ttype);
3377
3378       TYPE_POINTER_TO (ntype) = 0;
3379       TYPE_REFERENCE_TO (ntype) = 0;
3380       TYPE_ATTRIBUTES (ntype) = attribute;
3381
3382       /* Create a new main variant of TYPE.  */
3383       TYPE_MAIN_VARIANT (ntype) = ntype;
3384       TYPE_NEXT_VARIANT (ntype) = 0;
3385       set_type_quals (ntype, TYPE_UNQUALIFIED);
3386
3387       hashcode = iterative_hash_object (code, hashcode);
3388       if (TREE_TYPE (ntype))
3389         hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
3390                                           hashcode);
3391       hashcode = attribute_hash_list (attribute, hashcode);
3392
3393       switch (TREE_CODE (ntype))
3394         {
3395         case FUNCTION_TYPE:
3396           hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
3397           break;
3398         case ARRAY_TYPE:
3399           hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
3400                                             hashcode);
3401           break;
3402         case INTEGER_TYPE:
3403           hashcode = iterative_hash_object
3404             (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
3405           hashcode = iterative_hash_object
3406             (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
3407           break;
3408         case REAL_TYPE:
3409           {
3410             unsigned int precision = TYPE_PRECISION (ntype);
3411             hashcode = iterative_hash_object (precision, hashcode);
3412           }
3413           break;
3414         default:
3415           break;
3416         }
3417
3418       ntype = type_hash_canon (hashcode, ntype);
3419       ttype = build_qualified_type (ntype, quals);
3420     }
3421
3422   return ttype;
3423 }
3424
3425
3426 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
3427    is ATTRIBUTE.
3428
3429    Record such modified types already made so we don't make duplicates.  */
3430
3431 tree
3432 build_type_attribute_variant (tree ttype, tree attribute)
3433 {
3434   return build_type_attribute_qual_variant (ttype, attribute,
3435                                             TYPE_QUALS (ttype));
3436 }
3437
3438 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3439    or zero if not.
3440
3441    We try both `text' and `__text__', ATTR may be either one.  */
3442 /* ??? It might be a reasonable simplification to require ATTR to be only
3443    `text'.  One might then also require attribute lists to be stored in
3444    their canonicalized form.  */
3445
3446 static int
3447 is_attribute_with_length_p (const char *attr, int attr_len, tree ident)
3448 {
3449   int ident_len;
3450   const char *p;
3451
3452   if (TREE_CODE (ident) != IDENTIFIER_NODE)
3453     return 0;
3454
3455   p = IDENTIFIER_POINTER (ident);
3456   ident_len = IDENTIFIER_LENGTH (ident);
3457
3458   if (ident_len == attr_len
3459       && strcmp (attr, p) == 0)
3460     return 1;
3461
3462   /* If ATTR is `__text__', IDENT must be `text'; and vice versa.  */
3463   if (attr[0] == '_')
3464     {
3465       gcc_assert (attr[1] == '_');
3466       gcc_assert (attr[attr_len - 2] == '_');
3467       gcc_assert (attr[attr_len - 1] == '_');
3468       if (ident_len == attr_len - 4
3469           && strncmp (attr + 2, p, attr_len - 4) == 0)
3470         return 1;
3471     }
3472   else
3473     {
3474       if (ident_len == attr_len + 4
3475           && p[0] == '_' && p[1] == '_'
3476           && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
3477           && strncmp (attr, p + 2, attr_len) == 0)
3478         return 1;
3479     }
3480
3481   return 0;
3482 }
3483
3484 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3485    or zero if not.
3486
3487    We try both `text' and `__text__', ATTR may be either one.  */
3488
3489 int
3490 is_attribute_p (const char *attr, tree ident)
3491 {
3492   return is_attribute_with_length_p (attr, strlen (attr), ident);
3493 }
3494
3495 /* Given an attribute name and a list of attributes, return a pointer to the
3496    attribute's list element if the attribute is part of the list, or NULL_TREE
3497    if not found.  If the attribute appears more than once, this only
3498    returns the first occurrence; the TREE_CHAIN of the return value should
3499    be passed back in if further occurrences are wanted.  */
3500
3501 tree
3502 lookup_attribute (const char *attr_name, tree list)
3503 {
3504   tree l;
3505   size_t attr_len = strlen (attr_name);
3506
3507   for (l = list; l; l = TREE_CHAIN (l))
3508     {
3509       gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE);
3510       if (is_attribute_with_length_p (attr_name, attr_len, TREE_PURPOSE (l)))
3511         return l;
3512     }
3513
3514   return NULL_TREE;
3515 }
3516
3517 /* Remove any instances of attribute ATTR_NAME in LIST and return the
3518    modified list.  */
3519
3520 tree
3521 remove_attribute (const char *attr_name, tree list)
3522 {
3523   tree *p;
3524   size_t attr_len = strlen (attr_name);
3525
3526   for (p = &list; *p; )
3527     {
3528       tree l = *p;
3529       gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE);
3530       if (is_attribute_with_length_p (attr_name, attr_len, TREE_PURPOSE (l)))
3531         *p = TREE_CHAIN (l);
3532       else
3533         p = &TREE_CHAIN (l);
3534     }
3535
3536   return list;
3537 }
3538
3539 /* Return an attribute list that is the union of a1 and a2.  */
3540
3541 tree
3542 merge_attributes (tree a1, tree a2)
3543 {
3544   tree attributes;
3545
3546   /* Either one unset?  Take the set one.  */
3547
3548   if ((attributes = a1) == 0)
3549     attributes = a2;
3550
3551   /* One that completely contains the other?  Take it.  */
3552
3553   else if (a2 != 0 && ! attribute_list_contained (a1, a2))
3554     {
3555       if (attribute_list_contained (a2, a1))
3556         attributes = a2;
3557       else
3558         {
3559           /* Pick the longest list, and hang on the other list.  */
3560
3561           if (list_length (a1) < list_length (a2))
3562             attributes = a2, a2 = a1;
3563
3564           for (; a2 != 0; a2 = TREE_CHAIN (a2))
3565             {
3566               tree a;
3567               for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3568                                          attributes);
3569                    a != NULL_TREE;
3570                    a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3571                                          TREE_CHAIN (a)))
3572                 {
3573                   if (TREE_VALUE (a) != NULL
3574                       && TREE_CODE (TREE_VALUE (a)) == TREE_LIST
3575                       && TREE_VALUE (a2) != NULL
3576                       && TREE_CODE (TREE_VALUE (a2)) == TREE_LIST)
3577                     {
3578                       if (simple_cst_list_equal (TREE_VALUE (a),
3579                                                  TREE_VALUE (a2)) == 1)
3580                         break;
3581                     }
3582                   else if (simple_cst_equal (TREE_VALUE (a),
3583                                              TREE_VALUE (a2)) == 1)
3584                     break;
3585                 }
3586               if (a == NULL_TREE)
3587                 {
3588                   a1 = copy_node (a2);
3589                   TREE_CHAIN (a1) = attributes;
3590                   attributes = a1;
3591                 }
3592             }
3593         }
3594     }
3595   return attributes;
3596 }
3597
3598 /* Given types T1 and T2, merge their attributes and return
3599   the result.  */
3600
3601 tree
3602 merge_type_attributes (tree t1, tree t2)
3603 {
3604   return merge_attributes (TYPE_ATTRIBUTES (t1),
3605                            TYPE_ATTRIBUTES (t2));
3606 }
3607
3608 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
3609    the result.  */
3610
3611 tree
3612 merge_decl_attributes (tree olddecl, tree newdecl)
3613 {
3614   return merge_attributes (DECL_ATTRIBUTES (olddecl),
3615                            DECL_ATTRIBUTES (newdecl));
3616 }
3617
3618 #if TARGET_DLLIMPORT_DECL_ATTRIBUTES
3619
3620 /* Specialization of merge_decl_attributes for various Windows targets.
3621
3622    This handles the following situation:
3623
3624      __declspec (dllimport) int foo;
3625      int foo;
3626
3627    The second instance of `foo' nullifies the dllimport.  */
3628
3629 tree
3630 merge_dllimport_decl_attributes (tree old, tree new)
3631 {
3632   tree a;
3633   int delete_dllimport_p = 1;
3634
3635   /* What we need to do here is remove from `old' dllimport if it doesn't
3636      appear in `new'.  dllimport behaves like extern: if a declaration is
3637      marked dllimport and a definition appears later, then the object
3638      is not dllimport'd.  We also remove a `new' dllimport if the old list
3639      contains dllexport:  dllexport always overrides dllimport, regardless
3640      of the order of declaration.  */
3641   if (!VAR_OR_FUNCTION_DECL_P (new))
3642     delete_dllimport_p = 0;
3643   else if (DECL_DLLIMPORT_P (new)
3644            && lookup_attribute ("dllexport", DECL_ATTRIBUTES (old)))
3645     {
3646       DECL_DLLIMPORT_P (new) = 0;
3647       warning (OPT_Wattributes, "%q+D already declared with dllexport attribute: "
3648               "dllimport ignored", new);
3649     }
3650   else if (DECL_DLLIMPORT_P (old) && !DECL_DLLIMPORT_P (new))
3651     {
3652       /* Warn about overriding a symbol that has already been used. eg:
3653            extern int __attribute__ ((dllimport)) foo;
3654            int* bar () {return &foo;}
3655            int foo;
3656       */
3657       if (TREE_USED (old))
3658         {
3659           warning (0, "%q+D redeclared without dllimport attribute "
3660                    "after being referenced with dll linkage", new);
3661           /* If we have used a variable's address with dllimport linkage,
3662               keep the old DECL_DLLIMPORT_P flag: the ADDR_EXPR using the
3663               decl may already have had TREE_INVARIANT and TREE_CONSTANT
3664               computed.
3665               We still remove the attribute so that assembler code refers
3666               to '&foo rather than '_imp__foo'.  */
3667           if (TREE_CODE (old) == VAR_DECL && TREE_ADDRESSABLE (old))
3668             DECL_DLLIMPORT_P (new) = 1;
3669         }
3670
3671       /* Let an inline definition silently override the external reference,
3672          but otherwise warn about attribute inconsistency.  */
3673       else if (TREE_CODE (new) == VAR_DECL
3674                || !DECL_DECLARED_INLINE_P (new))
3675         warning (OPT_Wattributes, "%q+D redeclared without dllimport attribute: "
3676                   "previous dllimport ignored", new);
3677     }
3678   else
3679     delete_dllimport_p = 0;
3680
3681   a = merge_attributes (DECL_ATTRIBUTES (old), DECL_ATTRIBUTES (new));
3682
3683   if (delete_dllimport_p)
3684     {
3685       tree prev, t;
3686       const size_t attr_len = strlen ("dllimport");
3687
3688       /* Scan the list for dllimport and delete it.  */
3689       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
3690         {
3691           if (is_attribute_with_length_p ("dllimport", attr_len,
3692                                           TREE_PURPOSE (t)))
3693             {
3694               if (prev == NULL_TREE)
3695                 a = TREE_CHAIN (a);
3696               else
3697                 TREE_CHAIN (prev) = TREE_CHAIN (t);
3698               break;
3699             }
3700         }
3701     }
3702
3703   return a;
3704 }
3705
3706 /* Handle a "dllimport" or "dllexport" attribute; arguments as in
3707    struct attribute_spec.handler.  */
3708
3709 tree
3710 handle_dll_attribute (tree * pnode, tree name, tree args, int flags,
3711                       bool *no_add_attrs)
3712 {
3713   tree node = *pnode;
3714
3715   /* These attributes may apply to structure and union types being created,
3716      but otherwise should pass to the declaration involved.  */
3717   if (!DECL_P (node))
3718     {
3719       if (flags & ((int) ATTR_FLAG_DECL_NEXT | (int) ATTR_FLAG_FUNCTION_NEXT
3720                    | (int) ATTR_FLAG_ARRAY_NEXT))
3721         {
3722           *no_add_attrs = true;
3723           return tree_cons (name, args, NULL_TREE);
3724         }
3725       if (TREE_CODE (node) != RECORD_TYPE && TREE_CODE (node) != UNION_TYPE)
3726         {
3727           warning (OPT_Wattributes, "%qs attribute ignored",
3728                    IDENTIFIER_POINTER (name));
3729           *no_add_attrs = true;
3730         }
3731
3732       return NULL_TREE;
3733     }
3734
3735   if (TREE_CODE (node) != FUNCTION_DECL
3736       && TREE_CODE (node) != VAR_DECL)
3737     {
3738       *no_add_attrs = true;
3739       warning (OPT_Wattributes, "%qs attribute ignored",
3740                IDENTIFIER_POINTER (name));
3741       return NULL_TREE;
3742     }
3743
3744   /* Report error on dllimport ambiguities seen now before they cause
3745      any damage.  */
3746   else if (is_attribute_p ("dllimport", name))
3747     {
3748       /* Honor any target-specific overrides. */
3749       if (!targetm.valid_dllimport_attribute_p (node))
3750         *no_add_attrs = true;
3751
3752      else if (TREE_CODE (node) == FUNCTION_DECL
3753                 && DECL_DECLARED_INLINE_P (node))
3754         {
3755           warning (OPT_Wattributes, "inline function %q+D declared as "
3756                   " dllimport: attribute ignored", node);
3757           *no_add_attrs = true;
3758         }
3759       /* Like MS, treat definition of dllimported variables and
3760          non-inlined functions on declaration as syntax errors. */
3761      else if (TREE_CODE (node) == FUNCTION_DECL && DECL_INITIAL (node))
3762         {
3763           error ("function %q+D definition is marked dllimport", node);
3764           *no_add_attrs = true;
3765         }
3766
3767      else if (TREE_CODE (node) == VAR_DECL)
3768         {
3769           if (DECL_INITIAL (node))
3770             {
3771               error ("variable %q+D definition is marked dllimport",
3772                      node);
3773               *no_add_attrs = true;
3774             }
3775
3776           /* `extern' needn't be specified with dllimport.
3777              Specify `extern' now and hope for the best.  Sigh.  */
3778           DECL_EXTERNAL (node) = 1;
3779           /* Also, implicitly give dllimport'd variables declared within
3780              a function global scope, unless declared static.  */
3781           if (current_function_decl != NULL_TREE && !TREE_STATIC (node))
3782             TREE_PUBLIC (node) = 1;
3783         }
3784
3785       if (*no_add_attrs == false)
3786         DECL_DLLIMPORT_P (node) = 1;
3787     }
3788
3789   /*  Report error if symbol is not accessible at global scope.  */
3790   if (!TREE_PUBLIC (node)
3791       && (TREE_CODE (node) == VAR_DECL
3792           || TREE_CODE (node) == FUNCTION_DECL))
3793     {
3794       error ("external linkage required for symbol %q+D because of "
3795              "%qs attribute", node, IDENTIFIER_POINTER (name));
3796       *no_add_attrs = true;
3797     }
3798
3799   return NULL_TREE;
3800 }
3801
3802 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
3803 \f
3804 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
3805    of the various TYPE_QUAL values.  */
3806
3807 static void
3808 set_type_quals (tree type, int type_quals)
3809 {
3810   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
3811   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
3812   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
3813 }
3814
3815 /* Returns true iff cand is equivalent to base with type_quals.  */
3816
3817 bool
3818 check_qualified_type (tree cand, tree base, int type_quals)
3819 {
3820   return (TYPE_QUALS (cand) == type_quals
3821           && TYPE_NAME (cand) == TYPE_NAME (base)
3822           /* Apparently this is needed for Objective-C.  */
3823           && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base)
3824           && attribute_list_equal (TYPE_ATTRIBUTES (cand),
3825                                    TYPE_ATTRIBUTES (base)));
3826 }
3827
3828 /* Return a version of the TYPE, qualified as indicated by the
3829    TYPE_QUALS, if one exists.  If no qualified version exists yet,
3830    return NULL_TREE.  */
3831
3832 tree
3833 get_qualified_type (tree type, int type_quals)
3834 {
3835   tree t;
3836
3837   if (TYPE_QUALS (type) == type_quals)
3838     return type;
3839
3840   /* Search the chain of variants to see if there is already one there just
3841      like the one we need to have.  If so, use that existing one.  We must
3842      preserve the TYPE_NAME, since there is code that depends on this.  */
3843   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
3844     if (check_qualified_type (t, type, type_quals))
3845       return t;
3846
3847   return NULL_TREE;
3848 }
3849
3850 /* Like get_qualified_type, but creates the type if it does not
3851    exist.  This function never returns NULL_TREE.  */
3852
3853 tree
3854 build_qualified_type (tree type, int type_quals)
3855 {
3856   tree t;
3857
3858   /* See if we already have the appropriate qualified variant.  */
3859   t = get_qualified_type (type, type_quals);
3860
3861   /* If not, build it.  */
3862   if (!t)
3863     {
3864       t = build_variant_type_copy (type);
3865       set_type_quals (t, type_quals);
3866     }
3867
3868   return t;
3869 }
3870
3871 /* Create a new distinct copy of TYPE.  The new type is made its own
3872    MAIN_VARIANT.  */
3873
3874 tree
3875 build_distinct_type_copy (tree type)
3876 {
3877   tree t = copy_node (type);
3878
3879   TYPE_POINTER_TO (t) = 0;
3880   TYPE_REFERENCE_TO (t) = 0;
3881
3882   /* Make it its own variant.  */
3883   TYPE_MAIN_VARIANT (t) = t;
3884   TYPE_NEXT_VARIANT (t) = 0;
3885
3886   /* Note that it is now possible for TYPE_MIN_VALUE to be a value
3887      whose TREE_TYPE is not t.  This can also happen in the Ada
3888      frontend when using subtypes.  */
3889
3890   return t;
3891 }
3892
3893 /* Create a new variant of TYPE, equivalent but distinct.
3894    This is so the caller can modify it.  */
3895
3896 tree
3897 build_variant_type_copy (tree type)
3898 {
3899   tree t, m = TYPE_MAIN_VARIANT (type);
3900
3901   t = build_distinct_type_copy (type);
3902
3903   /* Add the new type to the chain of variants of TYPE.  */
3904   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3905   TYPE_NEXT_VARIANT (m) = t;
3906   TYPE_MAIN_VARIANT (t) = m;
3907
3908   return t;
3909 }
3910 \f
3911 /* Return true if the from tree in both tree maps are equal.  */
3912
3913 int
3914 tree_map_eq (const void *va, const void *vb)
3915 {
3916   const struct tree_map  *a = va, *b = vb;
3917   return (a->from == b->from);
3918 }
3919
3920 /* Hash a from tree in a tree_map.  */
3921
3922 unsigned int
3923 tree_map_hash (const void *item)
3924 {
3925   return (((const struct tree_map *) item)->hash);
3926 }
3927
3928 /* Return true if this tree map structure is marked for garbage collection
3929    purposes.  We simply return true if the from tree is marked, so that this
3930    structure goes away when the from tree goes away.  */
3931
3932 int
3933 tree_map_marked_p (const void *p)
3934 {
3935   tree from = ((struct tree_map *) p)->from;
3936
3937   return ggc_marked_p (from);
3938 }
3939
3940 /* Return true if the trees in the tree_int_map *'s VA and VB are equal.  */
3941
3942 static int
3943 tree_int_map_eq (const void *va, const void *vb)
3944 {
3945   const struct tree_int_map  *a = va, *b = vb;
3946   return (a->from == b->from);
3947 }
3948
3949 /* Hash a from tree in the tree_int_map * ITEM.  */
3950
3951 static unsigned int
3952 tree_int_map_hash (const void *item)
3953 {
3954   return htab_hash_pointer (((const struct tree_int_map *)item)->from);
3955 }
3956
3957 /* Return true if this tree int map structure is marked for garbage collection
3958    purposes.  We simply return true if the from tree_int_map *P's from tree is marked, so that this
3959    structure goes away when the from tree goes away.  */
3960
3961 static int
3962 tree_int_map_marked_p (const void *p)
3963 {
3964   tree from = ((struct tree_int_map *) p)->from;
3965
3966   return ggc_marked_p (from);
3967 }
3968 /* Lookup an init priority for FROM, and return it if we find one.  */
3969
3970 unsigned short
3971 decl_init_priority_lookup (tree from)
3972 {
3973   struct tree_int_map *h, in;
3974   in.from = from;
3975
3976   h = htab_find_with_hash (init_priority_for_decl,
3977                            &in, htab_hash_pointer (from));
3978   if (h)
3979     return h->to;
3980   return 0;
3981 }
3982
3983 /* Insert a mapping FROM->TO in the init priority hashtable.  */
3984
3985 void
3986 decl_init_priority_insert (tree from, unsigned short to)
3987 {
3988   struct tree_int_map *h;
3989   void **loc;
3990
3991   h = ggc_alloc (sizeof (struct tree_int_map));
3992   h->from = from;
3993   h->to = to;
3994   loc = htab_find_slot_with_hash (init_priority_for_decl, h,
3995                                   htab_hash_pointer (from), INSERT);
3996   *(struct tree_int_map **) loc = h;
3997 }
3998
3999 /* Look up a restrict qualified base decl for FROM.  */
4000
4001 tree
4002 decl_restrict_base_lookup (tree from)
4003 {
4004   struct tree_map *h;
4005   struct tree_map in;
4006
4007   in.from = from;
4008   h = htab_find_with_hash (restrict_base_for_decl, &in,
4009                            htab_hash_pointer (from));
4010   return h ? h->to : NULL_TREE;
4011 }
4012
4013 /* Record the restrict qualified base TO for FROM.  */
4014
4015 void
4016 decl_restrict_base_insert (tree from, tree to)
4017 {
4018   struct tree_map *h;
4019   void **loc;
4020
4021   h = ggc_alloc (sizeof (struct tree_map));
4022   h->hash = htab_hash_pointer (from);
4023   h->from = from;
4024   h->to = to;
4025   loc = htab_find_slot_with_hash (restrict_base_for_decl, h, h->hash, INSERT);
4026   *(struct tree_map **) loc = h;
4027 }
4028
4029 /* Print out the statistics for the DECL_DEBUG_EXPR hash table.  */
4030
4031 static void
4032 print_debug_expr_statistics (void)
4033 {
4034   fprintf (stderr, "DECL_DEBUG_EXPR  hash: size %ld, %ld elements, %f collisions\n",
4035            (long) htab_size (debug_expr_for_decl),
4036            (long) htab_elements (debug_expr_for_decl),
4037            htab_collisions (debug_expr_for_decl));
4038 }
4039
4040 /* Print out the statistics for the DECL_VALUE_EXPR hash table.  */
4041
4042 static void
4043 print_value_expr_statistics (void)
4044 {
4045   fprintf (stderr, "DECL_VALUE_EXPR  hash: size %ld, %ld elements, %f collisions\n",
4046            (long) htab_size (value_expr_for_decl),
4047            (long) htab_elements (value_expr_for_decl),
4048            htab_collisions (value_expr_for_decl));
4049 }
4050
4051 /* Print out statistics for the RESTRICT_BASE_FOR_DECL hash table, but
4052    don't print anything if the table is empty.  */
4053
4054 static void
4055 print_restrict_base_statistics (void)
4056 {
4057   if (htab_elements (restrict_base_for_decl) != 0)
4058     fprintf (stderr,
4059              "RESTRICT_BASE    hash: size %ld, %ld elements, %f collisions\n",
4060              (long) htab_size (restrict_base_for_decl),
4061              (long) htab_elements (restrict_base_for_decl),
4062              htab_collisions (restrict_base_for_decl));
4063 }
4064
4065 /* Lookup a debug expression for FROM, and return it if we find one.  */
4066
4067 tree
4068 decl_debug_expr_lookup (tree from)
4069 {
4070   struct tree_map *h, in;
4071   in.from = from;
4072
4073   h = htab_find_with_hash (debug_expr_for_decl, &in, htab_hash_pointer (from));
4074   if (h)
4075     return h->to;
4076   return NULL_TREE;
4077 }
4078
4079 /* Insert a mapping FROM->TO in the debug expression hashtable.  */
4080
4081 void
4082 decl_debug_expr_insert (tree from, tree to)
4083 {
4084   struct tree_map *h;
4085   void **loc;
4086
4087   h = ggc_alloc (sizeof (struct tree_map));
4088   h->hash = htab_hash_pointer (from);
4089   h->from = from;
4090   h->to = to;
4091   loc = htab_find_slot_with_hash (debug_expr_for_decl, h, h->hash, INSERT);
4092   *(struct tree_map **) loc = h;
4093 }
4094
4095 /* Lookup a value expression for FROM, and return it if we find one.  */
4096
4097 tree
4098 decl_value_expr_lookup (tree from)
4099 {
4100   struct tree_map *h, in;
4101   in.from = from;
4102
4103   h = htab_find_with_hash (value_expr_for_decl, &in, htab_hash_pointer (from));
4104   if (h)
4105     return h->to;
4106   return NULL_TREE;
4107 }
4108
4109 /* Insert a mapping FROM->TO in the value expression hashtable.  */
4110
4111 void
4112 decl_value_expr_insert (tree from, tree to)
4113 {
4114   struct tree_map *h;
4115   void **loc;
4116
4117   h = ggc_alloc (sizeof (struct tree_map));
4118   h->hash = htab_hash_pointer (from);
4119   h->from = from;
4120   h->to = to;
4121   loc = htab_find_slot_with_hash (value_expr_for_decl, h, h->hash, INSERT);
4122   *(struct tree_map **) loc = h;
4123 }
4124
4125 /* Hashing of types so that we don't make duplicates.
4126    The entry point is `type_hash_canon'.  */
4127
4128 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
4129    with types in the TREE_VALUE slots), by adding the hash codes
4130    of the individual types.  */
4131
4132 unsigned int
4133 type_hash_list (tree list, hashval_t hashcode)
4134 {
4135   tree tail;
4136
4137   for (tail = list; tail; tail = TREE_CHAIN (tail))
4138     if (TREE_VALUE (tail) != error_mark_node)
4139       hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
4140                                         hashcode);
4141
4142   return hashcode;
4143 }
4144
4145 /* These are the Hashtable callback functions.  */
4146
4147 /* Returns true iff the types are equivalent.  */
4148
4149 static int
4150 type_hash_eq (const void *va, const void *vb)
4151 {
4152   const struct type_hash *a = va, *b = vb;
4153
4154   /* First test the things that are the same for all types.  */
4155   if (a->hash != b->hash
4156       || TREE_CODE (a->type) != TREE_CODE (b->type)
4157       || TREE_TYPE (a->type) != TREE_TYPE (b->type)
4158       || !attribute_list_equal (TYPE_ATTRIBUTES (a->type),
4159                                  TYPE_ATTRIBUTES (b->type))
4160       || TYPE_ALIGN (a->type) != TYPE_ALIGN (b->type)
4161       || TYPE_MODE (a->type) != TYPE_MODE (b->type))
4162     return 0;
4163
4164   switch (TREE_CODE (a->type))
4165     {
4166     case VOID_TYPE:
4167     case COMPLEX_TYPE:
4168     case POINTER_TYPE:
4169     case REFERENCE_TYPE:
4170       return 1;
4171
4172     case VECTOR_TYPE:
4173       return TYPE_VECTOR_SUBPARTS (a->type) == TYPE_VECTOR_SUBPARTS (b->type);
4174
4175     case ENUMERAL_TYPE:
4176       if (TYPE_VALUES (a->type) != TYPE_VALUES (b->type)
4177           && !(TYPE_VALUES (a->type)
4178                && TREE_CODE (TYPE_VALUES (a->type)) == TREE_LIST
4179                && TYPE_VALUES (b->type)
4180                && TREE_CODE (TYPE_VALUES (b->type)) == TREE_LIST
4181                && type_list_equal (TYPE_VALUES (a->type),
4182                                    TYPE_VALUES (b->type))))
4183         return 0;
4184
4185       /* ... fall through ... */
4186
4187     case INTEGER_TYPE:
4188     case REAL_TYPE:
4189     case BOOLEAN_TYPE:
4190       return ((TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
4191                || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
4192                                       TYPE_MAX_VALUE (b->type)))
4193               && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
4194                   || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
4195                                          TYPE_MIN_VALUE (b->type))));
4196
4197     case OFFSET_TYPE:
4198       return TYPE_OFFSET_BASETYPE (a->type) == TYPE_OFFSET_BASETYPE (b->type);
4199
4200     case METHOD_TYPE:
4201       return (TYPE_METHOD_BASETYPE (a->type) == TYPE_METHOD_BASETYPE (b->type)
4202               && (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
4203                   || (TYPE_ARG_TYPES (a->type)
4204                       && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
4205                       && TYPE_ARG_TYPES (b->type)
4206                       && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
4207                       && type_list_equal (TYPE_ARG_TYPES (a->type),
4208                                           TYPE_ARG_TYPES (b->type)))));
4209
4210     case ARRAY_TYPE:
4211       return TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type);
4212
4213     case RECORD_TYPE:
4214     case UNION_TYPE:
4215     case QUAL_UNION_TYPE:
4216       return (TYPE_FIELDS (a->type) == TYPE_FIELDS (b->type)
4217               || (TYPE_FIELDS (a->type)
4218                   && TREE_CODE (TYPE_FIELDS (a->type)) == TREE_LIST
4219                   && TYPE_FIELDS (b->type)
4220                   && TREE_CODE (TYPE_FIELDS (b->type)) == TREE_LIST
4221                   && type_list_equal (TYPE_FIELDS (a->type),
4222                                       TYPE_FIELDS (b->type))));
4223
4224     case FUNCTION_TYPE:
4225       return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
4226               || (TYPE_ARG_TYPES (a->type)
4227                   && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
4228                   && TYPE_ARG_TYPES (b->type)
4229                   && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
4230                   && type_list_equal (TYPE_ARG_TYPES (a->type),
4231                                       TYPE_ARG_TYPES (b->type))));
4232
4233     default:
4234       return 0;
4235     }
4236 }
4237
4238 /* Return the cached hash value.  */
4239
4240 static hashval_t
4241 type_hash_hash (const void *item)
4242 {
4243   return ((const struct type_hash *) item)->hash;
4244 }
4245
4246 /* Look in the type hash table for a type isomorphic to TYPE.
4247    If one is found, return it.  Otherwise return 0.  */
4248
4249 tree
4250 type_hash_lookup (hashval_t hashcode, tree type)
4251 {
4252   struct type_hash *h, in;
4253
4254   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
4255      must call that routine before comparing TYPE_ALIGNs.  */
4256   layout_type (type);
4257
4258   in.hash = hashcode;
4259   in.type = type;
4260
4261   h = htab_find_with_hash (type_hash_table, &in, hashcode);
4262   if (h)
4263     return h->type;
4264   return NULL_TREE;
4265 }
4266
4267 /* Add an entry to the type-hash-table
4268    for a type TYPE whose hash code is HASHCODE.  */
4269
4270 void
4271 type_hash_add (hashval_t hashcode, tree type)
4272 {
4273   struct type_hash *h;
4274   void **loc;
4275
4276   h = ggc_alloc (sizeof (struct type_hash));
4277   h->hash = hashcode;
4278   h->type = type;
4279   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
4280   *(struct type_hash **) loc = h;
4281 }
4282
4283 /* Given TYPE, and HASHCODE its hash code, return the canonical
4284    object for an identical type if one already exists.
4285    Otherwise, return TYPE, and record it as the canonical object.
4286
4287    To use this function, first create a type of the sort you want.
4288    Then compute its hash code from the fields of the type that
4289    make it different from other similar types.
4290    Then call this function and use the value.  */
4291
4292 tree
4293 type_hash_canon (unsigned int hashcode, tree type)
4294 {
4295   tree t1;
4296
4297   /* The hash table only contains main variants, so ensure that's what we're
4298      being passed.  */
4299   gcc_assert (TYPE_MAIN_VARIANT (type) == type);
4300
4301   if (!lang_hooks.types.hash_types)
4302     return type;
4303
4304   /* See if the type is in the hash table already.  If so, return it.
4305      Otherwise, add the type.  */
4306   t1 = type_hash_lookup (hashcode, type);
4307   if (t1 != 0)
4308     {
4309 #ifdef GATHER_STATISTICS
4310       tree_node_counts[(int) t_kind]--;
4311       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
4312 #endif
4313       return t1;
4314     }
4315   else
4316     {
4317       type_hash_add (hashcode, type);
4318       return type;
4319     }
4320 }
4321
4322 /* See if the data pointed to by the type hash table is marked.  We consider
4323    it marked if the type is marked or if a debug type number or symbol
4324    table entry has been made for the type.  This reduces the amount of
4325    debugging output and eliminates that dependency of the debug output on
4326    the number of garbage collections.  */
4327
4328 static int
4329 type_hash_marked_p (const void *p)
4330 {
4331   tree type = ((struct type_hash *) p)->type;
4332
4333   return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
4334 }
4335
4336 static void
4337 print_type_hash_statistics (void)
4338 {
4339   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
4340            (long) htab_size (type_hash_table),
4341            (long) htab_elements (type_hash_table),
4342            htab_collisions (type_hash_table));
4343 }
4344
4345 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
4346    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
4347    by adding the hash codes of the individual attributes.  */
4348
4349 unsigned int
4350 attribute_hash_list (tree list, hashval_t hashcode)
4351 {
4352   tree tail;
4353
4354   for (tail = list; tail; tail = TREE_CHAIN (tail))
4355     /* ??? Do we want to add in TREE_VALUE too? */
4356     hashcode = iterative_hash_object
4357       (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode);
4358   return hashcode;
4359 }
4360
4361 /* Given two lists of attributes, return true if list l2 is
4362    equivalent to l1.  */
4363
4364 int
4365 attribute_list_equal (tree l1, tree l2)
4366 {
4367   return attribute_list_contained (l1, l2)
4368          && attribute_list_contained (l2, l1);
4369 }
4370
4371 /* Given two lists of attributes, return true if list L2 is
4372    completely contained within L1.  */
4373 /* ??? This would be faster if attribute names were stored in a canonicalized
4374    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
4375    must be used to show these elements are equivalent (which they are).  */
4376 /* ??? It's not clear that attributes with arguments will always be handled
4377    correctly.  */
4378
4379 int
4380 attribute_list_contained (tree l1, tree l2)
4381 {
4382   tree t1, t2;
4383
4384   /* First check the obvious, maybe the lists are identical.  */
4385   if (l1 == l2)
4386     return 1;
4387
4388   /* Maybe the lists are similar.  */
4389   for (t1 = l1, t2 = l2;
4390        t1 != 0 && t2 != 0
4391         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
4392         && TREE_VALUE (t1) == TREE_VALUE (t2);
4393        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
4394
4395   /* Maybe the lists are equal.  */
4396   if (t1 == 0 && t2 == 0)
4397     return 1;
4398
4399   for (; t2 != 0; t2 = TREE_CHAIN (t2))
4400     {
4401       tree attr;
4402       for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
4403            attr != NULL_TREE;
4404            attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
4405                                     TREE_CHAIN (attr)))
4406         {
4407           if (TREE_VALUE (t2) != NULL
4408               && TREE_CODE (TREE_VALUE (t2)) == TREE_LIST
4409               && TREE_VALUE (attr) != NULL
4410               && TREE_CODE (TREE_VALUE (attr)) == TREE_LIST)
4411             {
4412               if (simple_cst_list_equal (TREE_VALUE (t2),
4413                                          TREE_VALUE (attr)) == 1)
4414                 break;
4415             }
4416           else if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
4417             break;
4418         }
4419
4420       if (attr == 0)
4421         return 0;
4422     }
4423
4424   return 1;
4425 }
4426
4427 /* Given two lists of types
4428    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
4429    return 1 if the lists contain the same types in the same order.
4430    Also, the TREE_PURPOSEs must match.  */
4431
4432 int
4433 type_list_equal (tree l1, tree l2)
4434 {
4435   tree t1, t2;
4436
4437   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
4438     if (TREE_VALUE (t1) != TREE_VALUE (t2)
4439         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
4440             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
4441                   && (TREE_TYPE (TREE_PURPOSE (t1))
4442                       == TREE_TYPE (TREE_PURPOSE (t2))))))
4443       return 0;
4444
4445   return t1 == t2;
4446 }
4447
4448 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
4449    given by TYPE.  If the argument list accepts variable arguments,
4450    then this function counts only the ordinary arguments.  */
4451
4452 int
4453 type_num_arguments (tree type)
4454 {
4455   int i = 0;
4456   tree t;
4457
4458   for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
4459     /* If the function does not take a variable number of arguments,
4460        the last element in the list will have type `void'.  */
4461     if (VOID_TYPE_P (TREE_VALUE (t)))
4462       break;
4463     else
4464       ++i;
4465
4466   return i;
4467 }
4468
4469 /* Nonzero if integer constants T1 and T2
4470    represent the same constant value.  */
4471
4472 int
4473 tree_int_cst_equal (tree t1, tree t2)
4474 {
4475   if (t1 == t2)
4476     return 1;
4477
4478   if (t1 == 0 || t2 == 0)
4479     return 0;
4480
4481   if (TREE_CODE (t1) == INTEGER_CST
4482       && TREE_CODE (t2) == INTEGER_CST
4483       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
4484       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
4485     return 1;
4486
4487   return 0;
4488 }
4489
4490 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
4491    The precise way of comparison depends on their data type.  */
4492
4493 int
4494 tree_int_cst_lt (tree t1, tree t2)
4495 {
4496   if (t1 == t2)
4497     return 0;
4498
4499   if (TYPE_UNSIGNED (TREE_TYPE (t1)) != TYPE_UNSIGNED (TREE_TYPE (t2)))
4500     {
4501       int t1_sgn = tree_int_cst_sgn (t1);
4502       int t2_sgn = tree_int_cst_sgn (t2);
4503
4504       if (t1_sgn < t2_sgn)
4505         return 1;
4506       else if (t1_sgn > t2_sgn)
4507         return 0;
4508       /* Otherwise, both are non-negative, so we compare them as
4509          unsigned just in case one of them would overflow a signed
4510          type.  */
4511     }
4512   else if (!TYPE_UNSIGNED (TREE_TYPE (t1)))
4513     return INT_CST_LT (t1, t2);
4514
4515   return INT_CST_LT_UNSIGNED (t1, t2);
4516 }
4517
4518 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
4519
4520 int
4521 tree_int_cst_compare (tree t1, tree t2)
4522 {
4523   if (tree_int_cst_lt (t1, t2))
4524     return -1;
4525   else if (tree_int_cst_lt (t2, t1))
4526     return 1;
4527   else
4528     return 0;
4529 }
4530
4531 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
4532    the host.  If POS is zero, the value can be represented in a single
4533    HOST_WIDE_INT.  If POS is nonzero, the value must be non-negative and can
4534    be represented in a single unsigned HOST_WIDE_INT.  */
4535
4536 int
4537 host_integerp (tree t, int pos)
4538 {
4539   return (TREE_CODE (t) == INTEGER_CST
4540           && ((TREE_INT_CST_HIGH (t) == 0
4541                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
4542               || (! pos && TREE_INT_CST_HIGH (t) == -1
4543                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
4544                   && (!TYPE_UNSIGNED (TREE_TYPE (t))
4545                       || TYPE_IS_SIZETYPE (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 = fold_convert (type, op);
5645         }
5646     }
5647
5648   *unsignedp_ptr = uns;
5649   return win;
5650 }
5651 \f
5652 /* Nonzero if integer constant C has a value that is permissible
5653    for type TYPE (an INTEGER_TYPE).  */
5654
5655 int
5656 int_fits_type_p (tree c, tree type)
5657 {
5658   tree type_low_bound = TYPE_MIN_VALUE (type);
5659   tree type_high_bound = TYPE_MAX_VALUE (type);
5660   bool ok_for_low_bound, ok_for_high_bound;
5661   tree tmp;
5662
5663   /* If at least one bound of the type is a constant integer, we can check
5664      ourselves and maybe make a decision. If no such decision is possible, but
5665      this type is a subtype, try checking against that.  Otherwise, use
5666      force_fit_type, which checks against the precision.
5667
5668      Compute the status for each possibly constant bound, and return if we see
5669      one does not match. Use ok_for_xxx_bound for this purpose, assigning -1
5670      for "unknown if constant fits", 0 for "constant known *not* to fit" and 1
5671      for "constant known to fit".  */
5672
5673   /* Check if C >= type_low_bound.  */
5674   if (type_low_bound && TREE_CODE (type_low_bound) == INTEGER_CST)
5675     {
5676       if (tree_int_cst_lt (c, type_low_bound))
5677         return 0;
5678       ok_for_low_bound = true;
5679     }
5680   else
5681     ok_for_low_bound = false;
5682
5683   /* Check if c <= type_high_bound.  */
5684   if (type_high_bound && TREE_CODE (type_high_bound) == INTEGER_CST)
5685     {
5686       if (tree_int_cst_lt (type_high_bound, c))
5687         return 0;
5688       ok_for_high_bound = true;
5689     }
5690   else
5691     ok_for_high_bound = false;
5692
5693   /* If the constant fits both bounds, the result is known.  */
5694   if (ok_for_low_bound && ok_for_high_bound)
5695     return 1;
5696
5697   /* Perform some generic filtering which may allow making a decision
5698      even if the bounds are not constant.  First, negative integers
5699      never fit in unsigned types, */
5700   if (TYPE_UNSIGNED (type) && tree_int_cst_sgn (c) < 0)
5701     return 0;
5702
5703   /* Second, narrower types always fit in wider ones.  */
5704   if (TYPE_PRECISION (type) > TYPE_PRECISION (TREE_TYPE (c)))
5705     return 1;
5706
5707   /* Third, unsigned integers with top bit set never fit signed types.  */
5708   if (! TYPE_UNSIGNED (type)
5709       && TYPE_UNSIGNED (TREE_TYPE (c))
5710       && tree_int_cst_msb (c))
5711     return 0;
5712
5713   /* If we haven't been able to decide at this point, there nothing more we
5714      can check ourselves here.  Look at the base type if we have one and it
5715      has the same precision.  */
5716   if (TREE_CODE (type) == INTEGER_TYPE
5717       && TREE_TYPE (type) != 0
5718       && TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (type)))
5719     return int_fits_type_p (c, TREE_TYPE (type));
5720
5721   /* Or to force_fit_type, if nothing else.  */
5722   tmp = copy_node (c);
5723   TREE_TYPE (tmp) = type;
5724   tmp = force_fit_type (tmp, -1, false, false);
5725   return TREE_INT_CST_HIGH (tmp) == TREE_INT_CST_HIGH (c)
5726          && TREE_INT_CST_LOW (tmp) == TREE_INT_CST_LOW (c);
5727 }
5728
5729 /* Subprogram of following function.  Called by walk_tree.
5730
5731    Return *TP if it is an automatic variable or parameter of the
5732    function passed in as DATA.  */
5733
5734 static tree
5735 find_var_from_fn (tree *tp, int *walk_subtrees, void *data)
5736 {
5737   tree fn = (tree) data;
5738
5739   if (TYPE_P (*tp))
5740     *walk_subtrees = 0;
5741
5742   else if (DECL_P (*tp)
5743            && lang_hooks.tree_inlining.auto_var_in_fn_p (*tp, fn))
5744     return *tp;
5745
5746   return NULL_TREE;
5747 }
5748
5749 /* Returns true if T is, contains, or refers to a type with variable
5750    size.  For METHOD_TYPEs and FUNCTION_TYPEs we exclude the
5751    arguments, but not the return type.  If FN is nonzero, only return
5752    true if a modifier of the type or position of FN is a variable or
5753    parameter inside FN.
5754
5755    This concept is more general than that of C99 'variably modified types':
5756    in C99, a struct type is never variably modified because a VLA may not
5757    appear as a structure member.  However, in GNU C code like:
5758
5759      struct S { int i[f()]; };
5760
5761    is valid, and other languages may define similar constructs.  */
5762
5763 bool
5764 variably_modified_type_p (tree type, tree fn)
5765 {
5766   tree t;
5767
5768 /* Test if T is either variable (if FN is zero) or an expression containing
5769    a variable in FN.  */
5770 #define RETURN_TRUE_IF_VAR(T)                                           \
5771   do { tree _t = (T);                                                   \
5772     if (_t && _t != error_mark_node && TREE_CODE (_t) != INTEGER_CST    \
5773         && (!fn || walk_tree (&_t, find_var_from_fn, fn, NULL)))        \
5774       return true;  } while (0)
5775
5776   if (type == error_mark_node)
5777     return false;
5778
5779   /* If TYPE itself has variable size, it is variably modified.  */
5780   RETURN_TRUE_IF_VAR (TYPE_SIZE (type));
5781   RETURN_TRUE_IF_VAR (TYPE_SIZE_UNIT (type));
5782
5783   switch (TREE_CODE (type))
5784     {
5785     case POINTER_TYPE:
5786     case REFERENCE_TYPE:
5787     case VECTOR_TYPE:
5788       if (variably_modified_type_p (TREE_TYPE (type), fn))
5789         return true;
5790       break;
5791
5792     case FUNCTION_TYPE:
5793     case METHOD_TYPE:
5794       /* If TYPE is a function type, it is variably modified if the
5795          return type is variably modified.  */
5796       if (variably_modified_type_p (TREE_TYPE (type), fn))
5797           return true;
5798       break;
5799
5800     case INTEGER_TYPE:
5801     case REAL_TYPE:
5802     case ENUMERAL_TYPE:
5803     case BOOLEAN_TYPE:
5804       /* Scalar types are variably modified if their end points
5805          aren't constant.  */
5806       RETURN_TRUE_IF_VAR (TYPE_MIN_VALUE (type));
5807       RETURN_TRUE_IF_VAR (TYPE_MAX_VALUE (type));
5808       break;
5809
5810     case RECORD_TYPE:
5811     case UNION_TYPE:
5812     case QUAL_UNION_TYPE:
5813       /* We can't see if any of the fields are variably-modified by the
5814          definition we normally use, since that would produce infinite
5815          recursion via pointers.  */
5816       /* This is variably modified if some field's type is.  */
5817       for (t = TYPE_FIELDS (type); t; t = TREE_CHAIN (t))
5818         if (TREE_CODE (t) == FIELD_DECL)
5819           {
5820             RETURN_TRUE_IF_VAR (DECL_FIELD_OFFSET (t));
5821             RETURN_TRUE_IF_VAR (DECL_SIZE (t));
5822             RETURN_TRUE_IF_VAR (DECL_SIZE_UNIT (t));
5823
5824             if (TREE_CODE (type) == QUAL_UNION_TYPE)
5825               RETURN_TRUE_IF_VAR (DECL_QUALIFIER (t));
5826           }
5827         break;
5828
5829     case ARRAY_TYPE:
5830       /* Do not call ourselves to avoid infinite recursion.  This is
5831          variably modified if the element type is.  */
5832       RETURN_TRUE_IF_VAR (TYPE_SIZE (TREE_TYPE (type)));
5833       RETURN_TRUE_IF_VAR (TYPE_SIZE_UNIT (TREE_TYPE (type)));
5834       break;
5835
5836     default:
5837       break;
5838     }
5839
5840   /* The current language may have other cases to check, but in general,
5841      all other types are not variably modified.  */
5842   return lang_hooks.tree_inlining.var_mod_type_p (type, fn);
5843
5844 #undef RETURN_TRUE_IF_VAR
5845 }
5846
5847 /* Given a DECL or TYPE, return the scope in which it was declared, or
5848    NULL_TREE if there is no containing scope.  */
5849
5850 tree
5851 get_containing_scope (tree t)
5852 {
5853   return (TYPE_P (t) ? TYPE_CONTEXT (t) : DECL_CONTEXT (t));
5854 }
5855
5856 /* Return the innermost context enclosing DECL that is
5857    a FUNCTION_DECL, or zero if none.  */
5858
5859 tree
5860 decl_function_context (tree decl)
5861 {
5862   tree context;
5863
5864   if (TREE_CODE (decl) == ERROR_MARK)
5865     return 0;
5866
5867   /* C++ virtual functions use DECL_CONTEXT for the class of the vtable
5868      where we look up the function at runtime.  Such functions always take
5869      a first argument of type 'pointer to real context'.
5870
5871      C++ should really be fixed to use DECL_CONTEXT for the real context,
5872      and use something else for the "virtual context".  */
5873   else if (TREE_CODE (decl) == FUNCTION_DECL && DECL_VINDEX (decl))
5874     context
5875       = TYPE_MAIN_VARIANT
5876         (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (decl)))));
5877   else
5878     context = DECL_CONTEXT (decl);
5879
5880   while (context && TREE_CODE (context) != FUNCTION_DECL)
5881     {
5882       if (TREE_CODE (context) == BLOCK)
5883         context = BLOCK_SUPERCONTEXT (context);
5884       else
5885         context = get_containing_scope (context);
5886     }
5887
5888   return context;
5889 }
5890
5891 /* Return the innermost context enclosing DECL that is
5892    a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE, or zero if none.
5893    TYPE_DECLs and FUNCTION_DECLs are transparent to this function.  */
5894
5895 tree
5896 decl_type_context (tree decl)
5897 {
5898   tree context = DECL_CONTEXT (decl);
5899
5900   while (context)
5901     switch (TREE_CODE (context))
5902       {
5903       case NAMESPACE_DECL:
5904       case TRANSLATION_UNIT_DECL:
5905         return NULL_TREE;
5906
5907       case RECORD_TYPE:
5908       case UNION_TYPE:
5909       case QUAL_UNION_TYPE:
5910         return context;
5911
5912       case TYPE_DECL:
5913       case FUNCTION_DECL:
5914         context = DECL_CONTEXT (context);
5915         break;
5916
5917       case BLOCK:
5918         context = BLOCK_SUPERCONTEXT (context);
5919         break;
5920
5921       default:
5922         gcc_unreachable ();
5923       }
5924
5925   return NULL_TREE;
5926 }
5927
5928 /* CALL is a CALL_EXPR.  Return the declaration for the function
5929    called, or NULL_TREE if the called function cannot be
5930    determined.  */
5931
5932 tree
5933 get_callee_fndecl (tree call)
5934 {
5935   tree addr;
5936
5937   if (call == error_mark_node)
5938     return call;
5939
5940   /* It's invalid to call this function with anything but a
5941      CALL_EXPR.  */
5942   gcc_assert (TREE_CODE (call) == CALL_EXPR);
5943
5944   /* The first operand to the CALL is the address of the function
5945      called.  */
5946   addr = TREE_OPERAND (call, 0);
5947
5948   STRIP_NOPS (addr);
5949
5950   /* If this is a readonly function pointer, extract its initial value.  */
5951   if (DECL_P (addr) && TREE_CODE (addr) != FUNCTION_DECL
5952       && TREE_READONLY (addr) && ! TREE_THIS_VOLATILE (addr)
5953       && DECL_INITIAL (addr))
5954     addr = DECL_INITIAL (addr);
5955
5956   /* If the address is just `&f' for some function `f', then we know
5957      that `f' is being called.  */
5958   if (TREE_CODE (addr) == ADDR_EXPR
5959       && TREE_CODE (TREE_OPERAND (addr, 0)) == FUNCTION_DECL)
5960     return TREE_OPERAND (addr, 0);
5961
5962   /* We couldn't figure out what was being called.  Maybe the front
5963      end has some idea.  */
5964   return lang_hooks.lang_get_callee_fndecl (call);
5965 }
5966
5967 /* Print debugging information about tree nodes generated during the compile,
5968    and any language-specific information.  */
5969
5970 void
5971 dump_tree_statistics (void)
5972 {
5973 #ifdef GATHER_STATISTICS
5974   int i;
5975   int total_nodes, total_bytes;
5976 #endif
5977
5978   fprintf (stderr, "\n??? tree nodes created\n\n");
5979 #ifdef GATHER_STATISTICS
5980   fprintf (stderr, "Kind                   Nodes      Bytes\n");
5981   fprintf (stderr, "---------------------------------------\n");
5982   total_nodes = total_bytes = 0;
5983   for (i = 0; i < (int) all_kinds; i++)
5984     {
5985       fprintf (stderr, "%-20s %7d %10d\n", tree_node_kind_names[i],
5986                tree_node_counts[i], tree_node_sizes[i]);
5987       total_nodes += tree_node_counts[i];
5988       total_bytes += tree_node_sizes[i];
5989     }
5990   fprintf (stderr, "---------------------------------------\n");
5991   fprintf (stderr, "%-20s %7d %10d\n", "Total", total_nodes, total_bytes);
5992   fprintf (stderr, "---------------------------------------\n");
5993   ssanames_print_statistics ();
5994   phinodes_print_statistics ();
5995 #else
5996   fprintf (stderr, "(No per-node statistics)\n");
5997 #endif
5998   print_type_hash_statistics ();
5999   print_debug_expr_statistics ();
6000   print_value_expr_statistics ();
6001   print_restrict_base_statistics ();
6002   lang_hooks.print_statistics ();
6003 }
6004 \f
6005 #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
6006
6007 /* Generate a crc32 of a string.  */
6008
6009 unsigned
6010 crc32_string (unsigned chksum, const char *string)
6011 {
6012   do
6013     {
6014       unsigned value = *string << 24;
6015       unsigned ix;
6016
6017       for (ix = 8; ix--; value <<= 1)
6018         {
6019           unsigned feedback;
6020
6021           feedback = (value ^ chksum) & 0x80000000 ? 0x04c11db7 : 0;
6022           chksum <<= 1;
6023           chksum ^= feedback;
6024         }
6025     }
6026   while (*string++);
6027   return chksum;
6028 }
6029
6030 /* P is a string that will be used in a symbol.  Mask out any characters
6031    that are not valid in that context.  */
6032
6033 void
6034 clean_symbol_name (char *p)
6035 {
6036   for (; *p; p++)
6037     if (! (ISALNUM (*p)
6038 #ifndef NO_DOLLAR_IN_LABEL      /* this for `$'; unlikely, but... -- kr */
6039             || *p == '$'
6040 #endif
6041 #ifndef NO_DOT_IN_LABEL         /* this for `.'; unlikely, but...  */
6042             || *p == '.'
6043 #endif
6044            ))
6045       *p = '_';
6046 }
6047
6048 /* Generate a name for a special-purpose function function.
6049    The generated name may need to be unique across the whole link.
6050    TYPE is some string to identify the purpose of this function to the
6051    linker or collect2; it must start with an uppercase letter,
6052    one of:
6053    I - for constructors
6054    D - for destructors
6055    N - for C++ anonymous namespaces
6056    F - for DWARF unwind frame information.  */
6057
6058 tree
6059 get_file_function_name (const char *type)
6060 {
6061   char *buf;
6062   const char *p;
6063   char *q;
6064
6065   /* If we already have a name we know to be unique, just use that.  */
6066   if (first_global_object_name)
6067     p = first_global_object_name;
6068   /* If the target is handling the constructors/destructors, they
6069      will be local to this file and the name is only necessary for
6070      debugging purposes.  */
6071   else if ((type[0] == 'I' || type[0] == 'D') && targetm.have_ctors_dtors)
6072     {
6073       const char *file = main_input_filename;
6074       if (! file)
6075         file = input_filename;
6076       /* Just use the file's basename, because the full pathname
6077          might be quite long.  */
6078       p = strrchr (file, '/');
6079       if (p)
6080         p++;
6081       else
6082         p = file;
6083       p = q = ASTRDUP (p);
6084       clean_symbol_name (q);
6085     }
6086   else
6087     {
6088       /* Otherwise, the name must be unique across the entire link.
6089          We don't have anything that we know to be unique to this translation
6090          unit, so use what we do have and throw in some randomness.  */
6091       unsigned len;
6092       const char *name = weak_global_object_name;
6093       const char *file = main_input_filename;
6094
6095       if (! name)
6096         name = "";
6097       if (! file)
6098         file = input_filename;
6099
6100       len = strlen (file);
6101       q = alloca (9 * 2 + len + 1);
6102       memcpy (q, file, len + 1);
6103       clean_symbol_name (q);
6104
6105       sprintf (q + len, "_%08X_%08X", crc32_string (0, name),
6106                crc32_string (0, flag_random_seed));
6107
6108       p = q;
6109     }
6110
6111   buf = alloca (sizeof (FILE_FUNCTION_FORMAT) + strlen (p) + strlen (type));
6112
6113   /* Set up the name of the file-level functions we may need.
6114      Use a global object (which is already required to be unique over
6115      the program) rather than the file name (which imposes extra
6116      constraints).  */
6117   sprintf (buf, FILE_FUNCTION_FORMAT, type, p);
6118
6119   return get_identifier (buf);
6120 }
6121 \f
6122 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
6123
6124 /* Complain that the tree code of NODE does not match the expected 0
6125    terminated list of trailing codes. The trailing code list can be
6126    empty, for a more vague error message.  FILE, LINE, and FUNCTION
6127    are of the caller.  */
6128
6129 void
6130 tree_check_failed (const tree node, const char *file,
6131                    int line, const char *function, ...)
6132 {
6133   va_list args;
6134   char *buffer;
6135   unsigned length = 0;
6136   int code;
6137
6138   va_start (args, function);
6139   while ((code = va_arg (args, int)))
6140     length += 4 + strlen (tree_code_name[code]);
6141   va_end (args);
6142   if (length)
6143     {
6144       va_start (args, function);
6145       length += strlen ("expected ");
6146       buffer = alloca (length);
6147       length = 0;
6148       while ((code = va_arg (args, int)))
6149         {
6150           const char *prefix = length ? " or " : "expected ";
6151
6152           strcpy (buffer + length, prefix);
6153           length += strlen (prefix);
6154           strcpy (buffer + length, tree_code_name[code]);
6155           length += strlen (tree_code_name[code]);
6156         }
6157       va_end (args);
6158     }
6159   else
6160     buffer = (char *)"unexpected node";
6161
6162   internal_error ("tree check: %s, have %s in %s, at %s:%d",
6163                   buffer, tree_code_name[TREE_CODE (node)],
6164                   function, trim_filename (file), line);
6165 }
6166
6167 /* Complain that the tree code of NODE does match the expected 0
6168    terminated list of trailing codes. FILE, LINE, and FUNCTION are of
6169    the caller.  */
6170
6171 void
6172 tree_not_check_failed (const tree node, const char *file,
6173                        int line, const char *function, ...)
6174 {
6175   va_list args;
6176   char *buffer;
6177   unsigned length = 0;
6178   int code;
6179
6180   va_start (args, function);
6181   while ((code = va_arg (args, int)))
6182     length += 4 + strlen (tree_code_name[code]);
6183   va_end (args);
6184   va_start (args, function);
6185   buffer = alloca (length);
6186   length = 0;
6187   while ((code = va_arg (args, int)))
6188     {
6189       if (length)
6190         {
6191           strcpy (buffer + length, " or ");
6192           length += 4;
6193         }
6194       strcpy (buffer + length, tree_code_name[code]);
6195       length += strlen (tree_code_name[code]);
6196     }
6197   va_end (args);
6198
6199   internal_error ("tree check: expected none of %s, have %s in %s, at %s:%d",
6200                   buffer, tree_code_name[TREE_CODE (node)],
6201                   function, trim_filename (file), line);
6202 }
6203
6204 /* Similar to tree_check_failed, except that we check for a class of tree
6205    code, given in CL.  */
6206
6207 void
6208 tree_class_check_failed (const tree node, const enum tree_code_class cl,
6209                          const char *file, int line, const char *function)
6210 {
6211   internal_error
6212     ("tree check: expected class %qs, have %qs (%s) in %s, at %s:%d",
6213      TREE_CODE_CLASS_STRING (cl),
6214      TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))),
6215      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6216 }
6217
6218 /* Similar to tree_check_failed, except that instead of specifying a
6219    dozen codes, use the knowledge that they're all sequential.  */
6220
6221 void
6222 tree_range_check_failed (const tree node, const char *file, int line,
6223                          const char *function, enum tree_code c1,
6224                          enum tree_code c2)
6225 {
6226   char *buffer;
6227   unsigned length = 0;
6228   enum tree_code c;
6229
6230   for (c = c1; c <= c2; ++c)
6231     length += 4 + strlen (tree_code_name[c]);
6232
6233   length += strlen ("expected ");
6234   buffer = alloca (length);
6235   length = 0;
6236
6237   for (c = c1; c <= c2; ++c)
6238     {
6239       const char *prefix = length ? " or " : "expected ";
6240
6241       strcpy (buffer + length, prefix);
6242       length += strlen (prefix);
6243       strcpy (buffer + length, tree_code_name[c]);
6244       length += strlen (tree_code_name[c]);
6245     }
6246
6247   internal_error ("tree check: %s, have %s in %s, at %s:%d",
6248                   buffer, tree_code_name[TREE_CODE (node)],
6249                   function, trim_filename (file), line);
6250 }
6251
6252
6253 /* Similar to tree_check_failed, except that we check that a tree does
6254    not have the specified code, given in CL.  */
6255
6256 void
6257 tree_not_class_check_failed (const tree node, const enum tree_code_class cl,
6258                              const char *file, int line, const char *function)
6259 {
6260   internal_error
6261     ("tree check: did not expect class %qs, have %qs (%s) in %s, at %s:%d",
6262      TREE_CODE_CLASS_STRING (cl),
6263      TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))),
6264      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6265 }
6266
6267
6268 /* Similar to tree_check_failed but applied to OMP_CLAUSE codes.  */
6269
6270 void
6271 omp_clause_check_failed (const tree node, const char *file, int line,
6272                          const char *function, enum omp_clause_code code)
6273 {
6274   internal_error ("tree check: expected omp_clause %s, have %s in %s, at %s:%d",
6275                   omp_clause_code_name[code], tree_code_name[TREE_CODE (node)],
6276                   function, trim_filename (file), line);
6277 }
6278
6279
6280 /* Similar to tree_range_check_failed but applied to OMP_CLAUSE codes.  */
6281
6282 void
6283 omp_clause_range_check_failed (const tree node, const char *file, int line,
6284                                const char *function, enum omp_clause_code c1,
6285                                enum omp_clause_code c2)
6286 {
6287   char *buffer;
6288   unsigned length = 0;
6289   enum omp_clause_code c;
6290
6291   for (c = c1; c <= c2; ++c)
6292     length += 4 + strlen (omp_clause_code_name[c]);
6293
6294   length += strlen ("expected ");
6295   buffer = alloca (length);
6296   length = 0;
6297
6298   for (c = c1; c <= c2; ++c)
6299     {
6300       const char *prefix = length ? " or " : "expected ";
6301
6302       strcpy (buffer + length, prefix);
6303       length += strlen (prefix);
6304       strcpy (buffer + length, omp_clause_code_name[c]);
6305       length += strlen (omp_clause_code_name[c]);
6306     }
6307
6308   internal_error ("tree check: %s, have %s in %s, at %s:%d",
6309                   buffer, omp_clause_code_name[TREE_CODE (node)],
6310                   function, trim_filename (file), line);
6311 }
6312
6313
6314 #undef DEFTREESTRUCT
6315 #define DEFTREESTRUCT(VAL, NAME) NAME,
6316
6317 static const char *ts_enum_names[] = {
6318 #include "treestruct.def"
6319 };
6320 #undef DEFTREESTRUCT
6321
6322 #define TS_ENUM_NAME(EN) (ts_enum_names[(EN)])
6323
6324 /* Similar to tree_class_check_failed, except that we check for
6325    whether CODE contains the tree structure identified by EN.  */
6326
6327 void
6328 tree_contains_struct_check_failed (const tree node,
6329                                    const enum tree_node_structure_enum en,
6330                                    const char *file, int line,
6331                                    const char *function)
6332 {
6333   internal_error
6334     ("tree check: expected tree that contains %qs structure, have %qs  in %s, at %s:%d",
6335      TS_ENUM_NAME(en),
6336      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6337 }
6338
6339
6340 /* Similar to above, except that the check is for the bounds of a TREE_VEC's
6341    (dynamically sized) vector.  */
6342
6343 void
6344 tree_vec_elt_check_failed (int idx, int len, const char *file, int line,
6345                            const char *function)
6346 {
6347   internal_error
6348     ("tree check: accessed elt %d of tree_vec with %d elts in %s, at %s:%d",
6349      idx + 1, len, function, trim_filename (file), line);
6350 }
6351
6352 /* Similar to above, except that the check is for the bounds of a PHI_NODE's
6353    (dynamically sized) vector.  */
6354
6355 void
6356 phi_node_elt_check_failed (int idx, int len, const char *file, int line,
6357                             const char *function)
6358 {
6359   internal_error
6360     ("tree check: accessed elt %d of phi_node with %d elts in %s, at %s:%d",
6361      idx + 1, len, function, trim_filename (file), line);
6362 }
6363
6364 /* Similar to above, except that the check is for the bounds of the operand
6365    vector of an expression node.  */
6366
6367 void
6368 tree_operand_check_failed (int idx, enum tree_code code, const char *file,
6369                            int line, const char *function)
6370 {
6371   internal_error
6372     ("tree check: accessed operand %d of %s with %d operands in %s, at %s:%d",
6373      idx + 1, tree_code_name[code], TREE_CODE_LENGTH (code),
6374      function, trim_filename (file), line);
6375 }
6376
6377 /* Similar to above, except that the check is for the number of
6378    operands of an OMP_CLAUSE node.  */
6379
6380 void
6381 omp_clause_operand_check_failed (int idx, tree t, const char *file,
6382                                  int line, const char *function)
6383 {
6384   internal_error
6385     ("tree check: accessed operand %d of omp_clause %s with %d operands "
6386      "in %s, at %s:%d", idx + 1, omp_clause_code_name[OMP_CLAUSE_CODE (t)],
6387      omp_clause_num_ops [OMP_CLAUSE_CODE (t)], function,
6388      trim_filename (file), line);
6389 }
6390 #endif /* ENABLE_TREE_CHECKING */
6391 \f
6392 /* Create a new vector type node holding SUBPARTS units of type INNERTYPE,
6393    and mapped to the machine mode MODE.  Initialize its fields and build
6394    the information necessary for debugging output.  */
6395
6396 static tree
6397 make_vector_type (tree innertype, int nunits, enum machine_mode mode)
6398 {
6399   tree t;
6400   hashval_t hashcode = 0;
6401
6402   /* Build a main variant, based on the main variant of the inner type, then
6403      use it to build the variant we return.  */
6404   if ((TYPE_ATTRIBUTES (innertype) || TYPE_QUALS (innertype))
6405       && TYPE_MAIN_VARIANT (innertype) != innertype)
6406     return build_type_attribute_qual_variant (
6407             make_vector_type (TYPE_MAIN_VARIANT (innertype), nunits, mode),
6408             TYPE_ATTRIBUTES (innertype),
6409             TYPE_QUALS (innertype));
6410
6411   t = make_node (VECTOR_TYPE);
6412   TREE_TYPE (t) = TYPE_MAIN_VARIANT (innertype);
6413   SET_TYPE_VECTOR_SUBPARTS (t, nunits);
6414   TYPE_MODE (t) = mode;
6415   TYPE_READONLY (t) = TYPE_READONLY (innertype);
6416   TYPE_VOLATILE (t) = TYPE_VOLATILE (innertype);
6417
6418   layout_type (t);
6419
6420   {
6421     tree index = build_int_cst (NULL_TREE, nunits - 1);
6422     tree array = build_array_type (innertype, build_index_type (index));
6423     tree rt = make_node (RECORD_TYPE);
6424
6425     TYPE_FIELDS (rt) = build_decl (FIELD_DECL, get_identifier ("f"), array);
6426     DECL_CONTEXT (TYPE_FIELDS (rt)) = rt;
6427     layout_type (rt);
6428     TYPE_DEBUG_REPRESENTATION_TYPE (t) = rt;
6429     /* In dwarfout.c, type lookup uses TYPE_UID numbers.  We want to output
6430        the representation type, and we want to find that die when looking up
6431        the vector type.  This is most easily achieved by making the TYPE_UID
6432        numbers equal.  */
6433     TYPE_UID (rt) = TYPE_UID (t);
6434   }
6435
6436   hashcode = iterative_hash_host_wide_int (VECTOR_TYPE, hashcode);
6437   hashcode = iterative_hash_host_wide_int (mode, hashcode);
6438   hashcode = iterative_hash_object (TYPE_HASH (innertype), hashcode);
6439   return type_hash_canon (hashcode, t);
6440 }
6441
6442 static tree
6443 make_or_reuse_type (unsigned size, int unsignedp)
6444 {
6445   if (size == INT_TYPE_SIZE)
6446     return unsignedp ? unsigned_type_node : integer_type_node;
6447   if (size == CHAR_TYPE_SIZE)
6448     return unsignedp ? unsigned_char_type_node : signed_char_type_node;
6449   if (size == SHORT_TYPE_SIZE)
6450     return unsignedp ? short_unsigned_type_node : short_integer_type_node;
6451   if (size == LONG_TYPE_SIZE)
6452     return unsignedp ? long_unsigned_type_node : long_integer_type_node;
6453   if (size == LONG_LONG_TYPE_SIZE)
6454     return (unsignedp ? long_long_unsigned_type_node
6455             : long_long_integer_type_node);
6456
6457   if (unsignedp)
6458     return make_unsigned_type (size);
6459   else
6460     return make_signed_type (size);
6461 }
6462
6463 /* Create nodes for all integer types (and error_mark_node) using the sizes
6464    of C datatypes.  The caller should call set_sizetype soon after calling
6465    this function to select one of the types as sizetype.  */
6466
6467 void
6468 build_common_tree_nodes (bool signed_char, bool signed_sizetype)
6469 {
6470   error_mark_node = make_node (ERROR_MARK);
6471   TREE_TYPE (error_mark_node) = error_mark_node;
6472
6473   initialize_sizetypes (signed_sizetype);
6474
6475   /* Define both `signed char' and `unsigned char'.  */
6476   signed_char_type_node = make_signed_type (CHAR_TYPE_SIZE);
6477   TYPE_STRING_FLAG (signed_char_type_node) = 1;
6478   unsigned_char_type_node = make_unsigned_type (CHAR_TYPE_SIZE);
6479   TYPE_STRING_FLAG (unsigned_char_type_node) = 1;
6480
6481   /* Define `char', which is like either `signed char' or `unsigned char'
6482      but not the same as either.  */
6483   char_type_node
6484     = (signed_char
6485        ? make_signed_type (CHAR_TYPE_SIZE)
6486        : make_unsigned_type (CHAR_TYPE_SIZE));
6487   TYPE_STRING_FLAG (char_type_node) = 1;
6488
6489   short_integer_type_node = make_signed_type (SHORT_TYPE_SIZE);
6490   short_unsigned_type_node = make_unsigned_type (SHORT_TYPE_SIZE);
6491   integer_type_node = make_signed_type (INT_TYPE_SIZE);
6492   unsigned_type_node = make_unsigned_type (INT_TYPE_SIZE);
6493   long_integer_type_node = make_signed_type (LONG_TYPE_SIZE);
6494   long_unsigned_type_node = make_unsigned_type (LONG_TYPE_SIZE);
6495   long_long_integer_type_node = make_signed_type (LONG_LONG_TYPE_SIZE);
6496   long_long_unsigned_type_node = make_unsigned_type (LONG_LONG_TYPE_SIZE);
6497
6498   /* Define a boolean type.  This type only represents boolean values but
6499      may be larger than char depending on the value of BOOL_TYPE_SIZE.
6500      Front ends which want to override this size (i.e. Java) can redefine
6501      boolean_type_node before calling build_common_tree_nodes_2.  */
6502   boolean_type_node = make_unsigned_type (BOOL_TYPE_SIZE);
6503   TREE_SET_CODE (boolean_type_node, BOOLEAN_TYPE);
6504   TYPE_MAX_VALUE (boolean_type_node) = build_int_cst (boolean_type_node, 1);
6505   TYPE_PRECISION (boolean_type_node) = 1;
6506
6507   /* Fill in the rest of the sized types.  Reuse existing type nodes
6508      when possible.  */
6509   intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 0);
6510   intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 0);
6511   intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 0);
6512   intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 0);
6513   intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 0);
6514
6515   unsigned_intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 1);
6516   unsigned_intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 1);
6517   unsigned_intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 1);
6518   unsigned_intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 1);
6519   unsigned_intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 1);
6520
6521   access_public_node = get_identifier ("public");
6522   access_protected_node = get_identifier ("protected");
6523   access_private_node = get_identifier ("private");
6524 }
6525
6526 /* Call this function after calling build_common_tree_nodes and set_sizetype.
6527    It will create several other common tree nodes.  */
6528
6529 void
6530 build_common_tree_nodes_2 (int short_double)
6531 {
6532   /* Define these next since types below may used them.  */
6533   integer_zero_node = build_int_cst (NULL_TREE, 0);
6534   integer_one_node = build_int_cst (NULL_TREE, 1);
6535   integer_minus_one_node = build_int_cst (NULL_TREE, -1);
6536
6537   size_zero_node = size_int (0);
6538   size_one_node = size_int (1);
6539   bitsize_zero_node = bitsize_int (0);
6540   bitsize_one_node = bitsize_int (1);
6541   bitsize_unit_node = bitsize_int (BITS_PER_UNIT);
6542
6543   boolean_false_node = TYPE_MIN_VALUE (boolean_type_node);
6544   boolean_true_node = TYPE_MAX_VALUE (boolean_type_node);
6545
6546   void_type_node = make_node (VOID_TYPE);
6547   layout_type (void_type_node);
6548
6549   /* We are not going to have real types in C with less than byte alignment,
6550      so we might as well not have any types that claim to have it.  */
6551   TYPE_ALIGN (void_type_node) = BITS_PER_UNIT;
6552   TYPE_USER_ALIGN (void_type_node) = 0;
6553
6554   null_pointer_node = build_int_cst (build_pointer_type (void_type_node), 0);
6555   layout_type (TREE_TYPE (null_pointer_node));
6556
6557   ptr_type_node = build_pointer_type (void_type_node);
6558   const_ptr_type_node
6559     = build_pointer_type (build_type_variant (void_type_node, 1, 0));
6560   fileptr_type_node = ptr_type_node;
6561
6562   float_type_node = make_node (REAL_TYPE);
6563   TYPE_PRECISION (float_type_node) = FLOAT_TYPE_SIZE;
6564   layout_type (float_type_node);
6565
6566   double_type_node = make_node (REAL_TYPE);
6567   if (short_double)
6568     TYPE_PRECISION (double_type_node) = FLOAT_TYPE_SIZE;
6569   else
6570     TYPE_PRECISION (double_type_node) = DOUBLE_TYPE_SIZE;
6571   layout_type (double_type_node);
6572
6573   long_double_type_node = make_node (REAL_TYPE);
6574   TYPE_PRECISION (long_double_type_node) = LONG_DOUBLE_TYPE_SIZE;
6575   layout_type (long_double_type_node);
6576
6577   float_ptr_type_node = build_pointer_type (float_type_node);
6578   double_ptr_type_node = build_pointer_type (double_type_node);
6579   long_double_ptr_type_node = build_pointer_type (long_double_type_node);
6580   integer_ptr_type_node = build_pointer_type (integer_type_node);
6581
6582   /* Fixed size integer types.  */
6583   uint32_type_node = build_nonstandard_integer_type (32, true);
6584   uint64_type_node = build_nonstandard_integer_type (64, true);
6585
6586   /* Decimal float types. */
6587   dfloat32_type_node = make_node (REAL_TYPE);
6588   TYPE_PRECISION (dfloat32_type_node) = DECIMAL32_TYPE_SIZE;
6589   layout_type (dfloat32_type_node);
6590   TYPE_MODE (dfloat32_type_node) = SDmode;
6591   dfloat32_ptr_type_node = build_pointer_type (dfloat32_type_node);
6592
6593   dfloat64_type_node = make_node (REAL_TYPE);
6594   TYPE_PRECISION (dfloat64_type_node) = DECIMAL64_TYPE_SIZE;
6595   layout_type (dfloat64_type_node);
6596   TYPE_MODE (dfloat64_type_node) = DDmode;
6597   dfloat64_ptr_type_node = build_pointer_type (dfloat64_type_node);
6598
6599   dfloat128_type_node = make_node (REAL_TYPE);
6600   TYPE_PRECISION (dfloat128_type_node) = DECIMAL128_TYPE_SIZE;
6601   layout_type (dfloat128_type_node);
6602   TYPE_MODE (dfloat128_type_node) = TDmode;
6603   dfloat128_ptr_type_node = build_pointer_type (dfloat128_type_node);
6604
6605   complex_integer_type_node = make_node (COMPLEX_TYPE);
6606   TREE_TYPE (complex_integer_type_node) = integer_type_node;
6607   layout_type (complex_integer_type_node);
6608
6609   complex_float_type_node = make_node (COMPLEX_TYPE);
6610   TREE_TYPE (complex_float_type_node) = float_type_node;
6611   layout_type (complex_float_type_node);
6612
6613   complex_double_type_node = make_node (COMPLEX_TYPE);
6614   TREE_TYPE (complex_double_type_node) = double_type_node;
6615   layout_type (complex_double_type_node);
6616
6617   complex_long_double_type_node = make_node (COMPLEX_TYPE);
6618   TREE_TYPE (complex_long_double_type_node) = long_double_type_node;
6619   layout_type (complex_long_double_type_node);
6620
6621   {
6622     tree t = targetm.build_builtin_va_list ();
6623
6624     /* Many back-ends define record types without setting TYPE_NAME.
6625        If we copied the record type here, we'd keep the original
6626        record type without a name.  This breaks name mangling.  So,
6627        don't copy record types and let c_common_nodes_and_builtins()
6628        declare the type to be __builtin_va_list.  */
6629     if (TREE_CODE (t) != RECORD_TYPE)
6630       t = build_variant_type_copy (t);
6631
6632     va_list_type_node = t;
6633   }
6634 }
6635
6636 /* A subroutine of build_common_builtin_nodes.  Define a builtin function.  */
6637
6638 static void
6639 local_define_builtin (const char *name, tree type, enum built_in_function code,
6640                       const char *library_name, int ecf_flags)
6641 {
6642   tree decl;
6643
6644   decl = lang_hooks.builtin_function (name, type, code, BUILT_IN_NORMAL,
6645                                       library_name, NULL_TREE);
6646   if (ecf_flags & ECF_CONST)
6647     TREE_READONLY (decl) = 1;
6648   if (ecf_flags & ECF_PURE)
6649     DECL_IS_PURE (decl) = 1;
6650   if (ecf_flags & ECF_NORETURN)
6651     TREE_THIS_VOLATILE (decl) = 1;
6652   if (ecf_flags & ECF_NOTHROW)
6653     TREE_NOTHROW (decl) = 1;
6654   if (ecf_flags & ECF_MALLOC)
6655     DECL_IS_MALLOC (decl) = 1;
6656
6657   built_in_decls[code] = decl;
6658   implicit_built_in_decls[code] = decl;
6659 }
6660
6661 /* Call this function after instantiating all builtins that the language
6662    front end cares about.  This will build the rest of the builtins that
6663    are relied upon by the tree optimizers and the middle-end.  */
6664
6665 void
6666 build_common_builtin_nodes (void)
6667 {
6668   tree tmp, ftype;
6669
6670   if (built_in_decls[BUILT_IN_MEMCPY] == NULL
6671       || built_in_decls[BUILT_IN_MEMMOVE] == NULL)
6672     {
6673       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6674       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6675       tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6676       ftype = build_function_type (ptr_type_node, tmp);
6677
6678       if (built_in_decls[BUILT_IN_MEMCPY] == NULL)
6679         local_define_builtin ("__builtin_memcpy", ftype, BUILT_IN_MEMCPY,
6680                               "memcpy", ECF_NOTHROW);
6681       if (built_in_decls[BUILT_IN_MEMMOVE] == NULL)
6682         local_define_builtin ("__builtin_memmove", ftype, BUILT_IN_MEMMOVE,
6683                               "memmove", ECF_NOTHROW);
6684     }
6685
6686   if (built_in_decls[BUILT_IN_MEMCMP] == NULL)
6687     {
6688       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6689       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6690       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6691       ftype = build_function_type (integer_type_node, tmp);
6692       local_define_builtin ("__builtin_memcmp", ftype, BUILT_IN_MEMCMP,
6693                             "memcmp", ECF_PURE | ECF_NOTHROW);
6694     }
6695
6696   if (built_in_decls[BUILT_IN_MEMSET] == NULL)
6697     {
6698       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6699       tmp = tree_cons (NULL_TREE, integer_type_node, tmp);
6700       tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6701       ftype = build_function_type (ptr_type_node, tmp);
6702       local_define_builtin ("__builtin_memset", ftype, BUILT_IN_MEMSET,
6703                             "memset", ECF_NOTHROW);
6704     }
6705
6706   if (built_in_decls[BUILT_IN_ALLOCA] == NULL)
6707     {
6708       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6709       ftype = build_function_type (ptr_type_node, tmp);
6710       local_define_builtin ("__builtin_alloca", ftype, BUILT_IN_ALLOCA,
6711                             "alloca", ECF_NOTHROW | ECF_MALLOC);
6712     }
6713
6714   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6715   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6716   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6717   ftype = build_function_type (void_type_node, tmp);
6718   local_define_builtin ("__builtin_init_trampoline", ftype,
6719                         BUILT_IN_INIT_TRAMPOLINE,
6720                         "__builtin_init_trampoline", ECF_NOTHROW);
6721
6722   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6723   ftype = build_function_type (ptr_type_node, tmp);
6724   local_define_builtin ("__builtin_adjust_trampoline", ftype,
6725                         BUILT_IN_ADJUST_TRAMPOLINE,
6726                         "__builtin_adjust_trampoline",
6727                         ECF_CONST | ECF_NOTHROW);
6728
6729   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6730   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6731   ftype = build_function_type (void_type_node, tmp);
6732   local_define_builtin ("__builtin_nonlocal_goto", ftype,
6733                         BUILT_IN_NONLOCAL_GOTO,
6734                         "__builtin_nonlocal_goto",
6735                         ECF_NORETURN | ECF_NOTHROW);
6736
6737   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6738   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6739   ftype = build_function_type (void_type_node, tmp);
6740   local_define_builtin ("__builtin_setjmp_setup", ftype,
6741                         BUILT_IN_SETJMP_SETUP,
6742                         "__builtin_setjmp_setup", ECF_NOTHROW);
6743
6744   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6745   ftype = build_function_type (ptr_type_node, tmp);
6746   local_define_builtin ("__builtin_setjmp_dispatcher", ftype,
6747                         BUILT_IN_SETJMP_DISPATCHER,
6748                         "__builtin_setjmp_dispatcher",
6749                         ECF_PURE | ECF_NOTHROW);
6750
6751   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6752   ftype = build_function_type (void_type_node, tmp);
6753   local_define_builtin ("__builtin_setjmp_receiver", ftype,
6754                         BUILT_IN_SETJMP_RECEIVER,
6755                         "__builtin_setjmp_receiver", ECF_NOTHROW);
6756
6757   ftype = build_function_type (ptr_type_node, void_list_node);
6758   local_define_builtin ("__builtin_stack_save", ftype, BUILT_IN_STACK_SAVE,
6759                         "__builtin_stack_save", ECF_NOTHROW);
6760
6761   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6762   ftype = build_function_type (void_type_node, tmp);
6763   local_define_builtin ("__builtin_stack_restore", ftype,
6764                         BUILT_IN_STACK_RESTORE,
6765                         "__builtin_stack_restore", ECF_NOTHROW);
6766
6767   ftype = build_function_type (void_type_node, void_list_node);
6768   local_define_builtin ("__builtin_profile_func_enter", ftype,
6769                         BUILT_IN_PROFILE_FUNC_ENTER, "profile_func_enter", 0);
6770   local_define_builtin ("__builtin_profile_func_exit", ftype,
6771                         BUILT_IN_PROFILE_FUNC_EXIT, "profile_func_exit", 0);
6772
6773   /* Complex multiplication and division.  These are handled as builtins
6774      rather than optabs because emit_library_call_value doesn't support
6775      complex.  Further, we can do slightly better with folding these
6776      beasties if the real and complex parts of the arguments are separate.  */
6777   {
6778     enum machine_mode mode;
6779
6780     for (mode = MIN_MODE_COMPLEX_FLOAT; mode <= MAX_MODE_COMPLEX_FLOAT; ++mode)
6781       {
6782         char mode_name_buf[4], *q;
6783         const char *p;
6784         enum built_in_function mcode, dcode;
6785         tree type, inner_type;
6786
6787         type = lang_hooks.types.type_for_mode (mode, 0);
6788         if (type == NULL)
6789           continue;
6790         inner_type = TREE_TYPE (type);
6791
6792         tmp = tree_cons (NULL_TREE, inner_type, void_list_node);
6793         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6794         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6795         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6796         ftype = build_function_type (type, tmp);
6797
6798         mcode = BUILT_IN_COMPLEX_MUL_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
6799         dcode = BUILT_IN_COMPLEX_DIV_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
6800
6801         for (p = GET_MODE_NAME (mode), q = mode_name_buf; *p; p++, q++)
6802           *q = TOLOWER (*p);
6803         *q = '\0';
6804
6805         built_in_names[mcode] = concat ("__mul", mode_name_buf, "3", NULL);
6806         local_define_builtin (built_in_names[mcode], ftype, mcode,
6807                               built_in_names[mcode], ECF_CONST | ECF_NOTHROW);
6808
6809         built_in_names[dcode] = concat ("__div", mode_name_buf, "3", NULL);
6810         local_define_builtin (built_in_names[dcode], ftype, dcode,
6811                               built_in_names[dcode], ECF_CONST | ECF_NOTHROW);
6812       }
6813   }
6814 }
6815
6816 /* HACK.  GROSS.  This is absolutely disgusting.  I wish there was a
6817    better way.
6818
6819    If we requested a pointer to a vector, build up the pointers that
6820    we stripped off while looking for the inner type.  Similarly for
6821    return values from functions.
6822
6823    The argument TYPE is the top of the chain, and BOTTOM is the
6824    new type which we will point to.  */
6825
6826 tree
6827 reconstruct_complex_type (tree type, tree bottom)
6828 {
6829   tree inner, outer;
6830
6831   if (POINTER_TYPE_P (type))
6832     {
6833       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6834       outer = build_pointer_type (inner);
6835     }
6836   else if (TREE_CODE (type) == ARRAY_TYPE)
6837     {
6838       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6839       outer = build_array_type (inner, TYPE_DOMAIN (type));
6840     }
6841   else if (TREE_CODE (type) == FUNCTION_TYPE)
6842     {
6843       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6844       outer = build_function_type (inner, TYPE_ARG_TYPES (type));
6845     }
6846   else if (TREE_CODE (type) == METHOD_TYPE)
6847     {
6848       tree argtypes;
6849       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6850       /* The build_method_type_directly() routine prepends 'this' to argument list,
6851          so we must compensate by getting rid of it.  */
6852       argtypes = TYPE_ARG_TYPES (type);
6853       outer = build_method_type_directly (TYPE_METHOD_BASETYPE (type),
6854                                           inner,
6855                                           TYPE_ARG_TYPES (type));
6856       TYPE_ARG_TYPES (outer) = argtypes;
6857     }
6858   else
6859     return bottom;
6860
6861   TYPE_READONLY (outer) = TYPE_READONLY (type);
6862   TYPE_VOLATILE (outer) = TYPE_VOLATILE (type);
6863
6864   return outer;
6865 }
6866
6867 /* Returns a vector tree node given a mode (integer, vector, or BLKmode) and
6868    the inner type.  */
6869 tree
6870 build_vector_type_for_mode (tree innertype, enum machine_mode mode)
6871 {
6872   int nunits;
6873
6874   switch (GET_MODE_CLASS (mode))
6875     {
6876     case MODE_VECTOR_INT:
6877     case MODE_VECTOR_FLOAT:
6878       nunits = GET_MODE_NUNITS (mode);
6879       break;
6880
6881     case MODE_INT:
6882       /* Check that there are no leftover bits.  */
6883       gcc_assert (GET_MODE_BITSIZE (mode)
6884                   % TREE_INT_CST_LOW (TYPE_SIZE (innertype)) == 0);
6885
6886       nunits = GET_MODE_BITSIZE (mode)
6887                / TREE_INT_CST_LOW (TYPE_SIZE (innertype));
6888       break;
6889
6890     default:
6891       gcc_unreachable ();
6892     }
6893
6894   return make_vector_type (innertype, nunits, mode);
6895 }
6896
6897 /* Similarly, but takes the inner type and number of units, which must be
6898    a power of two.  */
6899
6900 tree
6901 build_vector_type (tree innertype, int nunits)
6902 {
6903   return make_vector_type (innertype, nunits, VOIDmode);
6904 }
6905
6906
6907 /* Build RESX_EXPR with given REGION_NUMBER.  */
6908 tree
6909 build_resx (int region_number)
6910 {
6911   tree t;
6912   t = build1 (RESX_EXPR, void_type_node,
6913               build_int_cst (NULL_TREE, region_number));
6914   return t;
6915 }
6916
6917 /* Given an initializer INIT, return TRUE if INIT is zero or some
6918    aggregate of zeros.  Otherwise return FALSE.  */
6919 bool
6920 initializer_zerop (tree init)
6921 {
6922   tree elt;
6923
6924   STRIP_NOPS (init);
6925
6926   switch (TREE_CODE (init))
6927     {
6928     case INTEGER_CST:
6929       return integer_zerop (init);
6930
6931     case REAL_CST:
6932       /* ??? Note that this is not correct for C4X float formats.  There,
6933          a bit pattern of all zeros is 1.0; 0.0 is encoded with the most
6934          negative exponent.  */
6935       return real_zerop (init)
6936         && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init));
6937
6938     case COMPLEX_CST:
6939       return integer_zerop (init)
6940         || (real_zerop (init)
6941             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init)))
6942             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init))));
6943
6944     case VECTOR_CST:
6945       for (elt = TREE_VECTOR_CST_ELTS (init); elt; elt = TREE_CHAIN (elt))
6946         if (!initializer_zerop (TREE_VALUE (elt)))
6947           return false;
6948       return true;
6949
6950     case CONSTRUCTOR:
6951       {
6952         unsigned HOST_WIDE_INT idx;
6953
6954         FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (init), idx, elt)
6955           if (!initializer_zerop (elt))
6956             return false;
6957         return true;
6958       }
6959
6960     default:
6961       return false;
6962     }
6963 }
6964
6965 /* Build an empty statement.  */
6966
6967 tree
6968 build_empty_stmt (void)
6969 {
6970   return build1 (NOP_EXPR, void_type_node, size_zero_node);
6971 }
6972
6973
6974 /* Build an OpenMP clause with code CODE.  */
6975
6976 tree
6977 build_omp_clause (enum omp_clause_code code)
6978 {
6979   tree t;
6980   int size, length;
6981
6982   length = omp_clause_num_ops[code];
6983   size = (sizeof (struct tree_omp_clause) + (length - 1) * sizeof (tree));
6984
6985   t = ggc_alloc (size);
6986   memset (t, 0, size);
6987   TREE_SET_CODE (t, OMP_CLAUSE);
6988   OMP_CLAUSE_SET_CODE (t, code);
6989
6990 #ifdef GATHER_STATISTICS
6991   tree_node_counts[(int) omp_clause_kind]++;
6992   tree_node_sizes[(int) omp_clause_kind] += size;
6993 #endif
6994
6995   return t;
6996 }
6997
6998
6999 /* Returns true if it is possible to prove that the index of
7000    an array access REF (an ARRAY_REF expression) falls into the
7001    array bounds.  */
7002
7003 bool
7004 in_array_bounds_p (tree ref)
7005 {
7006   tree idx = TREE_OPERAND (ref, 1);
7007   tree min, max;
7008
7009   if (TREE_CODE (idx) != INTEGER_CST)
7010     return false;
7011
7012   min = array_ref_low_bound (ref);
7013   max = array_ref_up_bound (ref);
7014   if (!min
7015       || !max
7016       || TREE_CODE (min) != INTEGER_CST
7017       || TREE_CODE (max) != INTEGER_CST)
7018     return false;
7019
7020   if (tree_int_cst_lt (idx, min)
7021       || tree_int_cst_lt (max, idx))
7022     return false;
7023
7024   return true;
7025 }
7026
7027 /* Returns true if it is possible to prove that the range of
7028    an array access REF (an ARRAY_RANGE_REF expression) falls
7029    into the array bounds.  */
7030
7031 bool
7032 range_in_array_bounds_p (tree ref)
7033 {
7034   tree domain_type = TYPE_DOMAIN (TREE_TYPE (ref));
7035   tree range_min, range_max, min, max;
7036
7037   range_min = TYPE_MIN_VALUE (domain_type);
7038   range_max = TYPE_MAX_VALUE (domain_type);
7039   if (!range_min
7040       || !range_max
7041       || TREE_CODE (range_min) != INTEGER_CST
7042       || TREE_CODE (range_max) != INTEGER_CST)
7043     return false;
7044
7045   min = array_ref_low_bound (ref);
7046   max = array_ref_up_bound (ref);
7047   if (!min
7048       || !max
7049       || TREE_CODE (min) != INTEGER_CST
7050       || TREE_CODE (max) != INTEGER_CST)
7051     return false;
7052
7053   if (tree_int_cst_lt (range_min, min)
7054       || tree_int_cst_lt (max, range_max))
7055     return false;
7056
7057   return true;
7058 }
7059
7060 /* Return true if T (assumed to be a DECL) is a global variable.  */
7061
7062 bool
7063 is_global_var (tree t)
7064 {
7065   if (MTAG_P (t))
7066     return (TREE_STATIC (t) || MTAG_GLOBAL (t));
7067   else
7068     return (TREE_STATIC (t) || DECL_EXTERNAL (t));
7069 }
7070
7071 /* Return true if T (assumed to be a DECL) must be assigned a memory
7072    location.  */
7073
7074 bool
7075 needs_to_live_in_memory (tree t)
7076 {
7077   return (TREE_ADDRESSABLE (t)
7078           || is_global_var (t)
7079           || (TREE_CODE (t) == RESULT_DECL
7080               && aggregate_value_p (t, current_function_decl)));
7081 }
7082
7083 /* There are situations in which a language considers record types
7084    compatible which have different field lists.  Decide if two fields
7085    are compatible.  It is assumed that the parent records are compatible.  */
7086
7087 bool
7088 fields_compatible_p (tree f1, tree f2)
7089 {
7090   if (!operand_equal_p (DECL_FIELD_BIT_OFFSET (f1),
7091                         DECL_FIELD_BIT_OFFSET (f2), OEP_ONLY_CONST))
7092     return false;
7093
7094   if (!operand_equal_p (DECL_FIELD_OFFSET (f1),
7095                         DECL_FIELD_OFFSET (f2), OEP_ONLY_CONST))
7096     return false;
7097
7098   if (!lang_hooks.types_compatible_p (TREE_TYPE (f1), TREE_TYPE (f2)))
7099     return false;
7100
7101   return true;
7102 }
7103
7104 /* Locate within RECORD a field that is compatible with ORIG_FIELD.  */
7105
7106 tree
7107 find_compatible_field (tree record, tree orig_field)
7108 {
7109   tree f;
7110
7111   for (f = TYPE_FIELDS (record); f ; f = TREE_CHAIN (f))
7112     if (TREE_CODE (f) == FIELD_DECL
7113         && fields_compatible_p (f, orig_field))
7114       return f;
7115
7116   /* ??? Why isn't this on the main fields list?  */
7117   f = TYPE_VFIELD (record);
7118   if (f && TREE_CODE (f) == FIELD_DECL
7119       && fields_compatible_p (f, orig_field))
7120     return f;
7121
7122   /* ??? We should abort here, but Java appears to do Bad Things
7123      with inherited fields.  */
7124   return orig_field;
7125 }
7126
7127 /* Return value of a constant X.  */
7128
7129 HOST_WIDE_INT
7130 int_cst_value (tree x)
7131 {
7132   unsigned bits = TYPE_PRECISION (TREE_TYPE (x));
7133   unsigned HOST_WIDE_INT val = TREE_INT_CST_LOW (x);
7134   bool negative = ((val >> (bits - 1)) & 1) != 0;
7135
7136   gcc_assert (bits <= HOST_BITS_PER_WIDE_INT);
7137
7138   if (negative)
7139     val |= (~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1;
7140   else
7141     val &= ~((~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1);
7142
7143   return val;
7144 }
7145
7146 /* Returns the greatest common divisor of A and B, which must be
7147    INTEGER_CSTs.  */
7148
7149 tree
7150 tree_fold_gcd (tree a, tree b)
7151 {
7152   tree a_mod_b;
7153   tree type = TREE_TYPE (a);
7154
7155   gcc_assert (TREE_CODE (a) == INTEGER_CST);
7156   gcc_assert (TREE_CODE (b) == INTEGER_CST);
7157
7158   if (integer_zerop (a))
7159     return b;
7160
7161   if (integer_zerop (b))
7162     return a;
7163
7164   if (tree_int_cst_sgn (a) == -1)
7165     a = fold_build2 (MULT_EXPR, type, a,
7166                      build_int_cst (type, -1));
7167
7168   if (tree_int_cst_sgn (b) == -1)
7169     b = fold_build2 (MULT_EXPR, type, b,
7170                      build_int_cst (type, -1));
7171
7172   while (1)
7173     {
7174       a_mod_b = fold_build2 (FLOOR_MOD_EXPR, type, a, b);
7175
7176       if (!TREE_INT_CST_LOW (a_mod_b)
7177           && !TREE_INT_CST_HIGH (a_mod_b))
7178         return b;
7179
7180       a = b;
7181       b = a_mod_b;
7182     }
7183 }
7184
7185 /* Returns unsigned variant of TYPE.  */
7186
7187 tree
7188 unsigned_type_for (tree type)
7189 {
7190   if (POINTER_TYPE_P (type))
7191     return lang_hooks.types.unsigned_type (size_type_node);
7192   return lang_hooks.types.unsigned_type (type);
7193 }
7194
7195 /* Returns signed variant of TYPE.  */
7196
7197 tree
7198 signed_type_for (tree type)
7199 {
7200   if (POINTER_TYPE_P (type))
7201     return lang_hooks.types.signed_type (size_type_node);
7202   return lang_hooks.types.signed_type (type);
7203 }
7204
7205 /* Returns the largest value obtainable by casting something in INNER type to
7206    OUTER type.  */
7207
7208 tree
7209 upper_bound_in_type (tree outer, tree inner)
7210 {
7211   unsigned HOST_WIDE_INT lo, hi;
7212   unsigned int det = 0;
7213   unsigned oprec = TYPE_PRECISION (outer);
7214   unsigned iprec = TYPE_PRECISION (inner);
7215   unsigned prec;
7216
7217   /* Compute a unique number for every combination.  */
7218   det |= (oprec > iprec) ? 4 : 0;
7219   det |= TYPE_UNSIGNED (outer) ? 2 : 0;
7220   det |= TYPE_UNSIGNED (inner) ? 1 : 0;
7221
7222   /* Determine the exponent to use.  */
7223   switch (det)
7224     {
7225     case 0:
7226     case 1:
7227       /* oprec <= iprec, outer: signed, inner: don't care.  */
7228       prec = oprec - 1;
7229       break;
7230     case 2:
7231     case 3:
7232       /* oprec <= iprec, outer: unsigned, inner: don't care.  */
7233       prec = oprec;
7234       break;
7235     case 4:
7236       /* oprec > iprec, outer: signed, inner: signed.  */
7237       prec = iprec - 1;
7238       break;
7239     case 5:
7240       /* oprec > iprec, outer: signed, inner: unsigned.  */
7241       prec = iprec;
7242       break;
7243     case 6:
7244       /* oprec > iprec, outer: unsigned, inner: signed.  */
7245       prec = oprec;
7246       break;
7247     case 7:
7248       /* oprec > iprec, outer: unsigned, inner: unsigned.  */
7249       prec = iprec;
7250       break;
7251     default:
7252       gcc_unreachable ();
7253     }
7254
7255   /* Compute 2^^prec - 1.  */
7256   if (prec <= HOST_BITS_PER_WIDE_INT)
7257     {
7258       hi = 0;
7259       lo = ((~(unsigned HOST_WIDE_INT) 0)
7260             >> (HOST_BITS_PER_WIDE_INT - prec));
7261     }
7262   else
7263     {
7264       hi = ((~(unsigned HOST_WIDE_INT) 0)
7265             >> (2 * HOST_BITS_PER_WIDE_INT - prec));
7266       lo = ~(unsigned HOST_WIDE_INT) 0;
7267     }
7268
7269   return build_int_cst_wide (outer, lo, hi);
7270 }
7271
7272 /* Returns the smallest value obtainable by casting something in INNER type to
7273    OUTER type.  */
7274
7275 tree
7276 lower_bound_in_type (tree outer, tree inner)
7277 {
7278   unsigned HOST_WIDE_INT lo, hi;
7279   unsigned oprec = TYPE_PRECISION (outer);
7280   unsigned iprec = TYPE_PRECISION (inner);
7281
7282   /* If OUTER type is unsigned, we can definitely cast 0 to OUTER type
7283      and obtain 0.  */
7284   if (TYPE_UNSIGNED (outer)
7285       /* If we are widening something of an unsigned type, OUTER type
7286          contains all values of INNER type.  In particular, both INNER
7287          and OUTER types have zero in common.  */
7288       || (oprec > iprec && TYPE_UNSIGNED (inner)))
7289     lo = hi = 0;
7290   else
7291     {
7292       /* If we are widening a signed type to another signed type, we
7293          want to obtain -2^^(iprec-1).  If we are keeping the
7294          precision or narrowing to a signed type, we want to obtain
7295          -2^(oprec-1).  */
7296       unsigned prec = oprec > iprec ? iprec : oprec;
7297
7298       if (prec <= HOST_BITS_PER_WIDE_INT)
7299         {
7300           hi = ~(unsigned HOST_WIDE_INT) 0;
7301           lo = (~(unsigned HOST_WIDE_INT) 0) << (prec - 1);
7302         }
7303       else
7304         {
7305           hi = ((~(unsigned HOST_WIDE_INT) 0)
7306                 << (prec - HOST_BITS_PER_WIDE_INT - 1));
7307           lo = 0;
7308         }
7309     }
7310
7311   return build_int_cst_wide (outer, lo, hi);
7312 }
7313
7314 /* Return nonzero if two operands that are suitable for PHI nodes are
7315    necessarily equal.  Specifically, both ARG0 and ARG1 must be either
7316    SSA_NAME or invariant.  Note that this is strictly an optimization.
7317    That is, callers of this function can directly call operand_equal_p
7318    and get the same result, only slower.  */
7319
7320 int
7321 operand_equal_for_phi_arg_p (tree arg0, tree arg1)
7322 {
7323   if (arg0 == arg1)
7324     return 1;
7325   if (TREE_CODE (arg0) == SSA_NAME || TREE_CODE (arg1) == SSA_NAME)
7326     return 0;
7327   return operand_equal_p (arg0, arg1, 0);
7328 }
7329
7330 /* Returns number of zeros at the end of binary representation of X.
7331
7332    ??? Use ffs if available?  */
7333
7334 tree
7335 num_ending_zeros (tree x)
7336 {
7337   unsigned HOST_WIDE_INT fr, nfr;
7338   unsigned num, abits;
7339   tree type = TREE_TYPE (x);
7340
7341   if (TREE_INT_CST_LOW (x) == 0)
7342     {
7343       num = HOST_BITS_PER_WIDE_INT;
7344       fr = TREE_INT_CST_HIGH (x);
7345     }
7346   else
7347     {
7348       num = 0;
7349       fr = TREE_INT_CST_LOW (x);
7350     }
7351
7352   for (abits = HOST_BITS_PER_WIDE_INT / 2; abits; abits /= 2)
7353     {
7354       nfr = fr >> abits;
7355       if (nfr << abits == fr)
7356         {
7357           num += abits;
7358           fr = nfr;
7359         }
7360     }
7361
7362   if (num > TYPE_PRECISION (type))
7363     num = TYPE_PRECISION (type);
7364
7365   return build_int_cst_type (type, num);
7366 }
7367
7368
7369 #define WALK_SUBTREE(NODE)                              \
7370   do                                                    \
7371     {                                                   \
7372       result = walk_tree (&(NODE), func, data, pset);   \
7373       if (result)                                       \
7374         return result;                                  \
7375     }                                                   \
7376   while (0)
7377
7378 /* This is a subroutine of walk_tree that walks field of TYPE that are to
7379    be walked whenever a type is seen in the tree.  Rest of operands and return
7380    value are as for walk_tree.  */
7381
7382 static tree
7383 walk_type_fields (tree type, walk_tree_fn func, void *data,
7384                   struct pointer_set_t *pset)
7385 {
7386   tree result = NULL_TREE;
7387
7388   switch (TREE_CODE (type))
7389     {
7390     case POINTER_TYPE:
7391     case REFERENCE_TYPE:
7392       /* We have to worry about mutually recursive pointers.  These can't
7393          be written in C.  They can in Ada.  It's pathological, but
7394          there's an ACATS test (c38102a) that checks it.  Deal with this
7395          by checking if we're pointing to another pointer, that one
7396          points to another pointer, that one does too, and we have no htab.
7397          If so, get a hash table.  We check three levels deep to avoid
7398          the cost of the hash table if we don't need one.  */
7399       if (POINTER_TYPE_P (TREE_TYPE (type))
7400           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type)))
7401           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type))))
7402           && !pset)
7403         {
7404           result = walk_tree_without_duplicates (&TREE_TYPE (type),
7405                                                  func, data);
7406           if (result)
7407             return result;
7408
7409           break;
7410         }
7411
7412       /* ... fall through ... */
7413
7414     case COMPLEX_TYPE:
7415       WALK_SUBTREE (TREE_TYPE (type));
7416       break;
7417
7418     case METHOD_TYPE:
7419       WALK_SUBTREE (TYPE_METHOD_BASETYPE (type));
7420
7421       /* Fall through.  */
7422
7423     case FUNCTION_TYPE:
7424       WALK_SUBTREE (TREE_TYPE (type));
7425       {
7426         tree arg;
7427
7428         /* We never want to walk into default arguments.  */
7429         for (arg = TYPE_ARG_TYPES (type); arg; arg = TREE_CHAIN (arg))
7430           WALK_SUBTREE (TREE_VALUE (arg));
7431       }
7432       break;
7433
7434     case ARRAY_TYPE:
7435       /* Don't follow this nodes's type if a pointer for fear that
7436          we'll have infinite recursion.  If we have a PSET, then we
7437          need not fear.  */
7438       if (pset
7439           || (!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"