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