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