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