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