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