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;
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           default:
2269             gcc_unreachable ();
2270           }
2271         break;
2272
2273       default:
2274         gcc_unreachable ();
2275       }
2276
2277   TREE_READONLY (new) = TREE_READONLY (exp);
2278   return new;
2279 }
2280
2281 /* Similar, but look for a PLACEHOLDER_EXPR in EXP and find a replacement
2282    for it within OBJ, a tree that is an object or a chain of references.  */
2283
2284 tree
2285 substitute_placeholder_in_expr (tree exp, tree obj)
2286 {
2287   enum tree_code code = TREE_CODE (exp);
2288   tree op0, op1, op2, op3;
2289
2290   /* If this is a PLACEHOLDER_EXPR, see if we find a corresponding type
2291      in the chain of OBJ.  */
2292   if (code == PLACEHOLDER_EXPR)
2293     {
2294       tree need_type = TYPE_MAIN_VARIANT (TREE_TYPE (exp));
2295       tree elt;
2296
2297       for (elt = obj; elt != 0;
2298            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2299                    || TREE_CODE (elt) == COND_EXPR)
2300                   ? TREE_OPERAND (elt, 1)
2301                   : (REFERENCE_CLASS_P (elt)
2302                      || UNARY_CLASS_P (elt)
2303                      || BINARY_CLASS_P (elt)
2304                      || EXPRESSION_CLASS_P (elt))
2305                   ? TREE_OPERAND (elt, 0) : 0))
2306         if (TYPE_MAIN_VARIANT (TREE_TYPE (elt)) == need_type)
2307           return elt;
2308
2309       for (elt = obj; elt != 0;
2310            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2311                    || TREE_CODE (elt) == COND_EXPR)
2312                   ? TREE_OPERAND (elt, 1)
2313                   : (REFERENCE_CLASS_P (elt)
2314                      || UNARY_CLASS_P (elt)
2315                      || BINARY_CLASS_P (elt)
2316                      || EXPRESSION_CLASS_P (elt))
2317                   ? TREE_OPERAND (elt, 0) : 0))
2318         if (POINTER_TYPE_P (TREE_TYPE (elt))
2319             && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (elt)))
2320                 == need_type))
2321           return fold_build1 (INDIRECT_REF, need_type, elt);
2322
2323       /* If we didn't find it, return the original PLACEHOLDER_EXPR.  If it
2324          survives until RTL generation, there will be an error.  */
2325       return exp;
2326     }
2327
2328   /* TREE_LIST is special because we need to look at TREE_VALUE
2329      and TREE_CHAIN, not TREE_OPERANDS.  */
2330   else if (code == TREE_LIST)
2331     {
2332       op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), obj);
2333       op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), obj);
2334       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2335         return exp;
2336
2337       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2338     }
2339   else
2340     switch (TREE_CODE_CLASS (code))
2341       {
2342       case tcc_constant:
2343       case tcc_declaration:
2344         return exp;
2345
2346       case tcc_exceptional:
2347       case tcc_unary:
2348       case tcc_binary:
2349       case tcc_comparison:
2350       case tcc_expression:
2351       case tcc_reference:
2352       case tcc_statement:
2353         switch (TREE_CODE_LENGTH (code))
2354           {
2355           case 0:
2356             return exp;
2357
2358           case 1:
2359             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2360             if (op0 == TREE_OPERAND (exp, 0))
2361               return exp;
2362             else
2363               return fold_build1 (code, TREE_TYPE (exp), op0);
2364
2365           case 2:
2366             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2367             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2368
2369             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2370               return exp;
2371             else
2372               return fold_build2 (code, TREE_TYPE (exp), op0, op1);
2373
2374           case 3:
2375             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2376             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2377             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2378
2379             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2380                 && op2 == TREE_OPERAND (exp, 2))
2381               return exp;
2382             else
2383               return fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2384
2385           case 4:
2386             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2387             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2388             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2389             op3 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 3), obj);
2390
2391             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2392                 && op2 == TREE_OPERAND (exp, 2)
2393                 && op3 == TREE_OPERAND (exp, 3))
2394               return exp;
2395             else
2396               return fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2397
2398           default:
2399             gcc_unreachable ();
2400           }
2401         break;
2402
2403       default:
2404         gcc_unreachable ();
2405       }
2406 }
2407 \f
2408 /* Stabilize a reference so that we can use it any number of times
2409    without causing its operands to be evaluated more than once.
2410    Returns the stabilized reference.  This works by means of save_expr,
2411    so see the caveats in the comments about save_expr.
2412
2413    Also allows conversion expressions whose operands are references.
2414    Any other kind of expression is returned unchanged.  */
2415
2416 tree
2417 stabilize_reference (tree ref)
2418 {
2419   tree result;
2420   enum tree_code code = TREE_CODE (ref);
2421
2422   switch (code)
2423     {
2424     case VAR_DECL:
2425     case PARM_DECL:
2426     case RESULT_DECL:
2427       /* No action is needed in this case.  */
2428       return ref;
2429
2430     case NOP_EXPR:
2431     case CONVERT_EXPR:
2432     case FLOAT_EXPR:
2433     case FIX_TRUNC_EXPR:
2434     case FIX_FLOOR_EXPR:
2435     case FIX_ROUND_EXPR:
2436     case FIX_CEIL_EXPR:
2437       result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
2438       break;
2439
2440     case INDIRECT_REF:
2441       result = build_nt (INDIRECT_REF,
2442                          stabilize_reference_1 (TREE_OPERAND (ref, 0)));
2443       break;
2444
2445     case COMPONENT_REF:
2446       result = build_nt (COMPONENT_REF,
2447                          stabilize_reference (TREE_OPERAND (ref, 0)),
2448                          TREE_OPERAND (ref, 1), NULL_TREE);
2449       break;
2450
2451     case BIT_FIELD_REF:
2452       result = build_nt (BIT_FIELD_REF,
2453                          stabilize_reference (TREE_OPERAND (ref, 0)),
2454                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2455                          stabilize_reference_1 (TREE_OPERAND (ref, 2)));
2456       break;
2457
2458     case ARRAY_REF:
2459       result = build_nt (ARRAY_REF,
2460                          stabilize_reference (TREE_OPERAND (ref, 0)),
2461                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2462                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2463       break;
2464
2465     case ARRAY_RANGE_REF:
2466       result = build_nt (ARRAY_RANGE_REF,
2467                          stabilize_reference (TREE_OPERAND (ref, 0)),
2468                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2469                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2470       break;
2471
2472     case COMPOUND_EXPR:
2473       /* We cannot wrap the first expression in a SAVE_EXPR, as then
2474          it wouldn't be ignored.  This matters when dealing with
2475          volatiles.  */
2476       return stabilize_reference_1 (ref);
2477
2478       /* If arg isn't a kind of lvalue we recognize, make no change.
2479          Caller should recognize the error for an invalid lvalue.  */
2480     default:
2481       return ref;
2482
2483     case ERROR_MARK:
2484       return error_mark_node;
2485     }
2486
2487   TREE_TYPE (result) = TREE_TYPE (ref);
2488   TREE_READONLY (result) = TREE_READONLY (ref);
2489   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
2490   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
2491
2492   return result;
2493 }
2494
2495 /* Subroutine of stabilize_reference; this is called for subtrees of
2496    references.  Any expression with side-effects must be put in a SAVE_EXPR
2497    to ensure that it is only evaluated once.
2498
2499    We don't put SAVE_EXPR nodes around everything, because assigning very
2500    simple expressions to temporaries causes us to miss good opportunities
2501    for optimizations.  Among other things, the opportunity to fold in the
2502    addition of a constant into an addressing mode often gets lost, e.g.
2503    "y[i+1] += x;".  In general, we take the approach that we should not make
2504    an assignment unless we are forced into it - i.e., that any non-side effect
2505    operator should be allowed, and that cse should take care of coalescing
2506    multiple utterances of the same expression should that prove fruitful.  */
2507
2508 tree
2509 stabilize_reference_1 (tree e)
2510 {
2511   tree result;
2512   enum tree_code code = TREE_CODE (e);
2513
2514   /* We cannot ignore const expressions because it might be a reference
2515      to a const array but whose index contains side-effects.  But we can
2516      ignore things that are actual constant or that already have been
2517      handled by this function.  */
2518
2519   if (TREE_INVARIANT (e))
2520     return e;
2521
2522   switch (TREE_CODE_CLASS (code))
2523     {
2524     case tcc_exceptional:
2525     case tcc_type:
2526     case tcc_declaration:
2527     case tcc_comparison:
2528     case tcc_statement:
2529     case tcc_expression:
2530     case tcc_reference:
2531       /* If the expression has side-effects, then encase it in a SAVE_EXPR
2532          so that it will only be evaluated once.  */
2533       /* The reference (r) and comparison (<) classes could be handled as
2534          below, but it is generally faster to only evaluate them once.  */
2535       if (TREE_SIDE_EFFECTS (e))
2536         return save_expr (e);
2537       return e;
2538
2539     case tcc_constant:
2540       /* Constants need no processing.  In fact, we should never reach
2541          here.  */
2542       return e;
2543
2544     case tcc_binary:
2545       /* Division is slow and tends to be compiled with jumps,
2546          especially the division by powers of 2 that is often
2547          found inside of an array reference.  So do it just once.  */
2548       if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
2549           || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
2550           || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
2551           || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
2552         return save_expr (e);
2553       /* Recursively stabilize each operand.  */
2554       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
2555                          stabilize_reference_1 (TREE_OPERAND (e, 1)));
2556       break;
2557
2558     case tcc_unary:
2559       /* Recursively stabilize each operand.  */
2560       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
2561       break;
2562
2563     default:
2564       gcc_unreachable ();
2565     }
2566
2567   TREE_TYPE (result) = TREE_TYPE (e);
2568   TREE_READONLY (result) = TREE_READONLY (e);
2569   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
2570   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
2571   TREE_INVARIANT (result) = 1;
2572
2573   return result;
2574 }
2575 \f
2576 /* Low-level constructors for expressions.  */
2577
2578 /* A helper function for build1 and constant folders.  Set TREE_CONSTANT,
2579    TREE_INVARIANT, and TREE_SIDE_EFFECTS for an ADDR_EXPR.  */
2580
2581 void
2582 recompute_tree_invarant_for_addr_expr (tree t)
2583 {
2584   tree node;
2585   bool tc = true, ti = true, se = false;
2586
2587   /* We started out assuming this address is both invariant and constant, but
2588      does not have side effects.  Now go down any handled components and see if
2589      any of them involve offsets that are either non-constant or non-invariant.
2590      Also check for side-effects.
2591
2592      ??? Note that this code makes no attempt to deal with the case where
2593      taking the address of something causes a copy due to misalignment.  */
2594
2595 #define UPDATE_TITCSE(NODE)  \
2596 do { tree _node = (NODE); \
2597      if (_node && !TREE_INVARIANT (_node)) ti = false; \
2598      if (_node && !TREE_CONSTANT (_node)) tc = false; \
2599      if (_node && TREE_SIDE_EFFECTS (_node)) se = true; } while (0)
2600
2601   for (node = TREE_OPERAND (t, 0); handled_component_p (node);
2602        node = TREE_OPERAND (node, 0))
2603     {
2604       /* If the first operand doesn't have an ARRAY_TYPE, this is a bogus
2605          array reference (probably made temporarily by the G++ front end),
2606          so ignore all the operands.  */
2607       if ((TREE_CODE (node) == ARRAY_REF
2608            || TREE_CODE (node) == ARRAY_RANGE_REF)
2609           && TREE_CODE (TREE_TYPE (TREE_OPERAND (node, 0))) == ARRAY_TYPE)
2610         {
2611           UPDATE_TITCSE (TREE_OPERAND (node, 1));
2612           if (TREE_OPERAND (node, 2))
2613             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2614           if (TREE_OPERAND (node, 3))
2615             UPDATE_TITCSE (TREE_OPERAND (node, 3));
2616         }
2617       /* Likewise, just because this is a COMPONENT_REF doesn't mean we have a
2618          FIELD_DECL, apparently.  The G++ front end can put something else
2619          there, at least temporarily.  */
2620       else if (TREE_CODE (node) == COMPONENT_REF
2621                && TREE_CODE (TREE_OPERAND (node, 1)) == FIELD_DECL)
2622         {
2623           if (TREE_OPERAND (node, 2))
2624             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2625         }
2626       else if (TREE_CODE (node) == BIT_FIELD_REF)
2627         UPDATE_TITCSE (TREE_OPERAND (node, 2));
2628     }
2629
2630   node = lang_hooks.expr_to_decl (node, &tc, &ti, &se);
2631
2632   /* Now see what's inside.  If it's an INDIRECT_REF, copy our properties from
2633      the address, since &(*a)->b is a form of addition.  If it's a decl, it's
2634      invariant and constant if the decl is static.  It's also invariant if it's
2635      a decl in the current function.  Taking the address of a volatile variable
2636      is not volatile.  If it's a constant, the address is both invariant and
2637      constant.  Otherwise it's neither.  */
2638   if (TREE_CODE (node) == INDIRECT_REF)
2639     UPDATE_TITCSE (TREE_OPERAND (node, 0));
2640   else if (DECL_P (node))
2641     {
2642       if (staticp (node))
2643         ;
2644       else if (decl_function_context (node) == current_function_decl
2645                /* Addresses of thread-local variables are invariant.  */
2646                || (TREE_CODE (node) == VAR_DECL
2647                    && DECL_THREAD_LOCAL_P (node)))
2648         tc = false;
2649       else
2650         ti = tc = false;
2651     }
2652   else if (CONSTANT_CLASS_P (node))
2653     ;
2654   else
2655     {
2656       ti = tc = false;
2657       se |= TREE_SIDE_EFFECTS (node);
2658     }
2659
2660   TREE_CONSTANT (t) = tc;
2661   TREE_INVARIANT (t) = ti;
2662   TREE_SIDE_EFFECTS (t) = se;
2663 #undef UPDATE_TITCSE
2664 }
2665
2666 /* Build an expression of code CODE, data type TYPE, and operands as
2667    specified.  Expressions and reference nodes can be created this way.
2668    Constants, decls, types and misc nodes cannot be.
2669
2670    We define 5 non-variadic functions, from 0 to 4 arguments.  This is
2671    enough for all extant tree codes.  These functions can be called
2672    directly (preferably!), but can also be obtained via GCC preprocessor
2673    magic within the build macro.  */
2674
2675 tree
2676 build0_stat (enum tree_code code, tree tt MEM_STAT_DECL)
2677 {
2678   tree t;
2679
2680   gcc_assert (TREE_CODE_LENGTH (code) == 0);
2681
2682   t = make_node_stat (code PASS_MEM_STAT);
2683   TREE_TYPE (t) = tt;
2684
2685   return t;
2686 }
2687
2688 tree
2689 build1_stat (enum tree_code code, tree type, tree node MEM_STAT_DECL)
2690 {
2691   int length = sizeof (struct tree_exp);
2692 #ifdef GATHER_STATISTICS
2693   tree_node_kind kind;
2694 #endif
2695   tree t;
2696
2697 #ifdef GATHER_STATISTICS
2698   switch (TREE_CODE_CLASS (code))
2699     {
2700     case tcc_statement:  /* an expression with side effects */
2701       kind = s_kind;
2702       break;
2703     case tcc_reference:  /* a reference */
2704       kind = r_kind;
2705       break;
2706     default:
2707       kind = e_kind;
2708       break;
2709     }
2710
2711   tree_node_counts[(int) kind]++;
2712   tree_node_sizes[(int) kind] += length;
2713 #endif
2714
2715   gcc_assert (TREE_CODE_LENGTH (code) == 1);
2716
2717   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
2718
2719   memset (t, 0, sizeof (struct tree_common));
2720
2721   TREE_SET_CODE (t, code);
2722
2723   TREE_TYPE (t) = type;
2724 #ifdef USE_MAPPED_LOCATION
2725   SET_EXPR_LOCATION (t, UNKNOWN_LOCATION);
2726 #else
2727   SET_EXPR_LOCUS (t, NULL);
2728 #endif
2729   TREE_COMPLEXITY (t) = 0;
2730   TREE_OPERAND (t, 0) = node;
2731   TREE_BLOCK (t) = NULL_TREE;
2732   if (node && !TYPE_P (node))
2733     {
2734       TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
2735       TREE_READONLY (t) = TREE_READONLY (node);
2736     }
2737
2738   if (TREE_CODE_CLASS (code) == tcc_statement)
2739     TREE_SIDE_EFFECTS (t) = 1;
2740   else switch (code)
2741     {
2742     case VA_ARG_EXPR:
2743       /* All of these have side-effects, no matter what their
2744          operands are.  */
2745       TREE_SIDE_EFFECTS (t) = 1;
2746       TREE_READONLY (t) = 0;
2747       break;
2748
2749     case MISALIGNED_INDIRECT_REF:
2750     case ALIGN_INDIRECT_REF:
2751     case INDIRECT_REF:
2752       /* Whether a dereference is readonly has nothing to do with whether
2753          its operand is readonly.  */
2754       TREE_READONLY (t) = 0;
2755       break;
2756
2757     case ADDR_EXPR:
2758       if (node)
2759         recompute_tree_invarant_for_addr_expr (t);
2760       break;
2761
2762     default:
2763       if (TREE_CODE_CLASS (code) == tcc_unary
2764           && node && !TYPE_P (node)
2765           && TREE_CONSTANT (node))
2766         TREE_CONSTANT (t) = 1;
2767       if (TREE_CODE_CLASS (code) == tcc_unary
2768           && node && TREE_INVARIANT (node))
2769         TREE_INVARIANT (t) = 1;
2770       if (TREE_CODE_CLASS (code) == tcc_reference
2771           && node && TREE_THIS_VOLATILE (node))
2772         TREE_THIS_VOLATILE (t) = 1;
2773       break;
2774     }
2775
2776   return t;
2777 }
2778
2779 #define PROCESS_ARG(N)                  \
2780   do {                                  \
2781     TREE_OPERAND (t, N) = arg##N;       \
2782     if (arg##N &&!TYPE_P (arg##N))      \
2783       {                                 \
2784         if (TREE_SIDE_EFFECTS (arg##N)) \
2785           side_effects = 1;             \
2786         if (!TREE_READONLY (arg##N))    \
2787           read_only = 0;                \
2788         if (!TREE_CONSTANT (arg##N))    \
2789           constant = 0;                 \
2790         if (!TREE_INVARIANT (arg##N))   \
2791           invariant = 0;                \
2792       }                                 \
2793   } while (0)
2794
2795 tree
2796 build2_stat (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL)
2797 {
2798   bool constant, read_only, side_effects, invariant;
2799   tree t;
2800
2801   gcc_assert (TREE_CODE_LENGTH (code) == 2);
2802
2803   t = make_node_stat (code PASS_MEM_STAT);
2804   TREE_TYPE (t) = tt;
2805
2806   /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
2807      result based on those same flags for the arguments.  But if the
2808      arguments aren't really even `tree' expressions, we shouldn't be trying
2809      to do this.  */
2810
2811   /* Expressions without side effects may be constant if their
2812      arguments are as well.  */
2813   constant = (TREE_CODE_CLASS (code) == tcc_comparison
2814               || TREE_CODE_CLASS (code) == tcc_binary);
2815   read_only = 1;
2816   side_effects = TREE_SIDE_EFFECTS (t);
2817   invariant = constant;
2818
2819   PROCESS_ARG(0);
2820   PROCESS_ARG(1);
2821
2822   TREE_READONLY (t) = read_only;
2823   TREE_CONSTANT (t) = constant;
2824   TREE_INVARIANT (t) = invariant;
2825   TREE_SIDE_EFFECTS (t) = side_effects;
2826   TREE_THIS_VOLATILE (t)
2827     = (TREE_CODE_CLASS (code) == tcc_reference
2828        && arg0 && TREE_THIS_VOLATILE (arg0));
2829
2830   return t;
2831 }
2832
2833 tree
2834 build3_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2835              tree arg2 MEM_STAT_DECL)
2836 {
2837   bool constant, read_only, side_effects, invariant;
2838   tree t;
2839
2840   gcc_assert (TREE_CODE_LENGTH (code) == 3);
2841
2842   t = make_node_stat (code PASS_MEM_STAT);
2843   TREE_TYPE (t) = tt;
2844
2845   side_effects = TREE_SIDE_EFFECTS (t);
2846
2847   PROCESS_ARG(0);
2848   PROCESS_ARG(1);
2849   PROCESS_ARG(2);
2850
2851   if (code == CALL_EXPR && !side_effects)
2852     {
2853       tree node;
2854       int i;
2855
2856       /* Calls have side-effects, except those to const or
2857          pure functions.  */
2858       i = call_expr_flags (t);
2859       if (!(i & (ECF_CONST | ECF_PURE)))
2860         side_effects = 1;
2861
2862       /* And even those have side-effects if their arguments do.  */
2863       else for (node = arg1; node; node = TREE_CHAIN (node))
2864         if (TREE_SIDE_EFFECTS (TREE_VALUE (node)))
2865           {
2866             side_effects = 1;
2867             break;
2868           }
2869     }
2870
2871   TREE_SIDE_EFFECTS (t) = side_effects;
2872   TREE_THIS_VOLATILE (t)
2873     = (TREE_CODE_CLASS (code) == tcc_reference
2874        && arg0 && TREE_THIS_VOLATILE (arg0));
2875
2876   return t;
2877 }
2878
2879 tree
2880 build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2881              tree arg2, tree arg3 MEM_STAT_DECL)
2882 {
2883   bool constant, read_only, side_effects, invariant;
2884   tree t;
2885
2886   gcc_assert (TREE_CODE_LENGTH (code) == 4);
2887
2888   t = make_node_stat (code PASS_MEM_STAT);
2889   TREE_TYPE (t) = tt;
2890
2891   side_effects = TREE_SIDE_EFFECTS (t);
2892
2893   PROCESS_ARG(0);
2894   PROCESS_ARG(1);
2895   PROCESS_ARG(2);
2896   PROCESS_ARG(3);
2897
2898   TREE_SIDE_EFFECTS (t) = side_effects;
2899   TREE_THIS_VOLATILE (t)
2900     = (TREE_CODE_CLASS (code) == tcc_reference
2901        && arg0 && TREE_THIS_VOLATILE (arg0));
2902
2903   return t;
2904 }
2905
2906 tree
2907 build7_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2908              tree arg2, tree arg3, tree arg4, tree arg5,
2909              tree arg6 MEM_STAT_DECL)
2910 {
2911   bool constant, read_only, side_effects, invariant;
2912   tree t;
2913
2914   gcc_assert (code == TARGET_MEM_REF);
2915
2916   t = make_node_stat (code PASS_MEM_STAT);
2917   TREE_TYPE (t) = tt;
2918
2919   side_effects = TREE_SIDE_EFFECTS (t);
2920
2921   PROCESS_ARG(0);
2922   PROCESS_ARG(1);
2923   PROCESS_ARG(2);
2924   PROCESS_ARG(3);
2925   PROCESS_ARG(4);
2926   PROCESS_ARG(5);
2927   PROCESS_ARG(6);
2928
2929   TREE_SIDE_EFFECTS (t) = side_effects;
2930   TREE_THIS_VOLATILE (t) = 0;
2931
2932   return t;
2933 }
2934
2935 /* Backup definition for non-gcc build compilers.  */
2936
2937 tree
2938 (build) (enum tree_code code, tree tt, ...)
2939 {
2940   tree t, arg0, arg1, arg2, arg3, arg4, arg5, arg6;
2941   int length = TREE_CODE_LENGTH (code);
2942   va_list p;
2943
2944   va_start (p, tt);
2945   switch (length)
2946     {
2947     case 0:
2948       t = build0 (code, tt);
2949       break;
2950     case 1:
2951       arg0 = va_arg (p, tree);
2952       t = build1 (code, tt, arg0);
2953       break;
2954     case 2:
2955       arg0 = va_arg (p, tree);
2956       arg1 = va_arg (p, tree);
2957       t = build2 (code, tt, arg0, arg1);
2958       break;
2959     case 3:
2960       arg0 = va_arg (p, tree);
2961       arg1 = va_arg (p, tree);
2962       arg2 = va_arg (p, tree);
2963       t = build3 (code, tt, arg0, arg1, arg2);
2964       break;
2965     case 4:
2966       arg0 = va_arg (p, tree);
2967       arg1 = va_arg (p, tree);
2968       arg2 = va_arg (p, tree);
2969       arg3 = va_arg (p, tree);
2970       t = build4 (code, tt, arg0, arg1, arg2, arg3);
2971       break;
2972     case 7:
2973       arg0 = va_arg (p, tree);
2974       arg1 = va_arg (p, tree);
2975       arg2 = va_arg (p, tree);
2976       arg3 = va_arg (p, tree);
2977       arg4 = va_arg (p, tree);
2978       arg5 = va_arg (p, tree);
2979       arg6 = va_arg (p, tree);
2980       t = build7 (code, tt, arg0, arg1, arg2, arg3, arg4, arg5, arg6);
2981       break;
2982     default:
2983       gcc_unreachable ();
2984     }
2985   va_end (p);
2986
2987   return t;
2988 }
2989
2990 /* Similar except don't specify the TREE_TYPE
2991    and leave the TREE_SIDE_EFFECTS as 0.
2992    It is permissible for arguments to be null,
2993    or even garbage if their values do not matter.  */
2994
2995 tree
2996 build_nt (enum tree_code code, ...)
2997 {
2998   tree t;
2999   int length;
3000   int i;
3001   va_list p;
3002
3003   va_start (p, code);
3004
3005   t = make_node (code);
3006   length = TREE_CODE_LENGTH (code);
3007
3008   for (i = 0; i < length; i++)
3009     TREE_OPERAND (t, i) = va_arg (p, tree);
3010
3011   va_end (p);
3012   return t;
3013 }
3014 \f
3015 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
3016    We do NOT enter this node in any sort of symbol table.
3017
3018    layout_decl is used to set up the decl's storage layout.
3019    Other slots are initialized to 0 or null pointers.  */
3020
3021 tree
3022 build_decl_stat (enum tree_code code, tree name, tree type MEM_STAT_DECL)
3023 {
3024   tree t;
3025
3026   t = make_node_stat (code PASS_MEM_STAT);
3027
3028 /*  if (type == error_mark_node)
3029     type = integer_type_node; */
3030 /* That is not done, deliberately, so that having error_mark_node
3031    as the type can suppress useless errors in the use of this variable.  */
3032
3033   DECL_NAME (t) = name;
3034   TREE_TYPE (t) = type;
3035
3036   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
3037     layout_decl (t, 0);
3038   else if (code == FUNCTION_DECL)
3039     DECL_MODE (t) = FUNCTION_MODE;
3040
3041   if (CODE_CONTAINS_STRUCT (code, TS_DECL_WITH_VIS))
3042     {
3043       /* Set default visibility to whatever the user supplied with
3044          visibility_specified depending on #pragma GCC visibility.  */
3045       DECL_VISIBILITY (t) = default_visibility;
3046       DECL_VISIBILITY_SPECIFIED (t) = visibility_options.inpragma;
3047     }
3048
3049   return t;
3050 }
3051
3052 /* Builds and returns function declaration with NAME and TYPE.  */
3053
3054 tree
3055 build_fn_decl (const char *name, tree type)
3056 {
3057   tree id = get_identifier (name);
3058   tree decl = build_decl (FUNCTION_DECL, id, type);
3059
3060   DECL_EXTERNAL (decl) = 1;
3061   TREE_PUBLIC (decl) = 1;
3062   DECL_ARTIFICIAL (decl) = 1;
3063   TREE_NOTHROW (decl) = 1;
3064
3065   return decl;
3066 }
3067
3068 \f
3069 /* BLOCK nodes are used to represent the structure of binding contours
3070    and declarations, once those contours have been exited and their contents
3071    compiled.  This information is used for outputting debugging info.  */
3072
3073 tree
3074 build_block (tree vars, tree subblocks, tree supercontext, tree chain)
3075 {
3076   tree block = make_node (BLOCK);
3077
3078   BLOCK_VARS (block) = vars;
3079   BLOCK_SUBBLOCKS (block) = subblocks;
3080   BLOCK_SUPERCONTEXT (block) = supercontext;
3081   BLOCK_CHAIN (block) = chain;
3082   return block;
3083 }
3084
3085 #if 1 /* ! defined(USE_MAPPED_LOCATION) */
3086 /* ??? gengtype doesn't handle conditionals */
3087 static GTY(()) tree last_annotated_node;
3088 #endif
3089
3090 #ifdef USE_MAPPED_LOCATION
3091
3092 expanded_location
3093 expand_location (source_location loc)
3094 {
3095   expanded_location xloc;
3096   if (loc == 0) { xloc.file = NULL; xloc.line = 0;  xloc.column = 0; }
3097   else
3098     {
3099       const struct line_map *map = linemap_lookup (&line_table, loc);
3100       xloc.file = map->to_file;
3101       xloc.line = SOURCE_LINE (map, loc);
3102       xloc.column = SOURCE_COLUMN (map, loc);
3103     };
3104   return xloc;
3105 }
3106
3107 #else
3108
3109 /* Record the exact location where an expression or an identifier were
3110    encountered.  */
3111
3112 void
3113 annotate_with_file_line (tree node, const char *file, int line)
3114 {
3115   /* Roughly one percent of the calls to this function are to annotate
3116      a node with the same information already attached to that node!
3117      Just return instead of wasting memory.  */
3118   if (EXPR_LOCUS (node)
3119       && (EXPR_FILENAME (node) == file
3120           || ! strcmp (EXPR_FILENAME (node), file))
3121       && EXPR_LINENO (node) == line)
3122     {
3123       last_annotated_node = node;
3124       return;
3125     }
3126
3127   /* In heavily macroized code (such as GCC itself) this single
3128      entry cache can reduce the number of allocations by more
3129      than half.  */
3130   if (last_annotated_node
3131       && EXPR_LOCUS (last_annotated_node)
3132       && (EXPR_FILENAME (last_annotated_node) == file
3133           || ! strcmp (EXPR_FILENAME (last_annotated_node), file))
3134       && EXPR_LINENO (last_annotated_node) == line)
3135     {
3136       SET_EXPR_LOCUS (node, EXPR_LOCUS (last_annotated_node));
3137       return;
3138     }
3139
3140   SET_EXPR_LOCUS (node, ggc_alloc (sizeof (location_t)));
3141   EXPR_LINENO (node) = line;
3142   EXPR_FILENAME (node) = file;
3143   last_annotated_node = node;
3144 }
3145
3146 void
3147 annotate_with_locus (tree node, location_t locus)
3148 {
3149   annotate_with_file_line (node, locus.file, locus.line);
3150 }
3151 #endif
3152 \f
3153 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
3154    is ATTRIBUTE.  */
3155
3156 tree
3157 build_decl_attribute_variant (tree ddecl, tree attribute)
3158 {
3159   DECL_ATTRIBUTES (ddecl) = attribute;
3160   return ddecl;
3161 }
3162
3163 /* Borrowed from hashtab.c iterative_hash implementation.  */
3164 #define mix(a,b,c) \
3165 { \
3166   a -= b; a -= c; a ^= (c>>13); \
3167   b -= c; b -= a; b ^= (a<< 8); \
3168   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
3169   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
3170   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
3171   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
3172   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
3173   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
3174   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
3175 }
3176
3177
3178 /* Produce good hash value combining VAL and VAL2.  */
3179 static inline hashval_t
3180 iterative_hash_hashval_t (hashval_t val, hashval_t val2)
3181 {
3182   /* the golden ratio; an arbitrary value.  */
3183   hashval_t a = 0x9e3779b9;
3184
3185   mix (a, val, val2);
3186   return val2;
3187 }
3188
3189 /* Produce good hash value combining PTR and VAL2.  */
3190 static inline hashval_t
3191 iterative_hash_pointer (void *ptr, hashval_t val2)
3192 {
3193   if (sizeof (ptr) == sizeof (hashval_t))
3194     return iterative_hash_hashval_t ((size_t) ptr, val2);
3195   else
3196     {
3197       hashval_t a = (hashval_t) (size_t) ptr;
3198       /* Avoid warnings about shifting of more than the width of the type on
3199          hosts that won't execute this path.  */
3200       int zero = 0;
3201       hashval_t b = (hashval_t) ((size_t) ptr >> (sizeof (hashval_t) * 8 + zero));
3202       mix (a, b, val2);
3203       return val2;
3204     }
3205 }
3206
3207 /* Produce good hash value combining VAL and VAL2.  */
3208 static inline hashval_t
3209 iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
3210 {
3211   if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
3212     return iterative_hash_hashval_t (val, val2);
3213   else
3214     {
3215       hashval_t a = (hashval_t) val;
3216       /* Avoid warnings about shifting of more than the width of the type on
3217          hosts that won't execute this path.  */
3218       int zero = 0;
3219       hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
3220       mix (a, b, val2);
3221       if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
3222         {
3223           hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
3224           hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
3225           mix (a, b, val2);
3226         }
3227       return val2;
3228     }
3229 }
3230
3231 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
3232    is ATTRIBUTE.
3233
3234    Record such modified types already made so we don't make duplicates.  */
3235
3236 tree
3237 build_type_attribute_variant (tree ttype, tree attribute)
3238 {
3239   if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
3240     {
3241       hashval_t hashcode = 0;
3242       tree ntype;
3243       enum tree_code code = TREE_CODE (ttype);
3244
3245       ntype = copy_node (ttype);
3246
3247       TYPE_POINTER_TO (ntype) = 0;
3248       TYPE_REFERENCE_TO (ntype) = 0;
3249       TYPE_ATTRIBUTES (ntype) = attribute;
3250
3251       /* Create a new main variant of TYPE.  */
3252       TYPE_MAIN_VARIANT (ntype) = ntype;
3253       TYPE_NEXT_VARIANT (ntype) = 0;
3254       set_type_quals (ntype, TYPE_UNQUALIFIED);
3255
3256       hashcode = iterative_hash_object (code, hashcode);
3257       if (TREE_TYPE (ntype))
3258         hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
3259                                           hashcode);
3260       hashcode = attribute_hash_list (attribute, hashcode);
3261
3262       switch (TREE_CODE (ntype))
3263         {
3264         case FUNCTION_TYPE:
3265           hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
3266           break;
3267         case ARRAY_TYPE:
3268           hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
3269                                             hashcode);
3270           break;
3271         case INTEGER_TYPE:
3272           hashcode = iterative_hash_object
3273             (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
3274           hashcode = iterative_hash_object
3275             (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
3276           break;
3277         case REAL_TYPE:
3278           {
3279             unsigned int precision = TYPE_PRECISION (ntype);
3280             hashcode = iterative_hash_object (precision, hashcode);
3281           }
3282           break;
3283         default:
3284           break;
3285         }
3286
3287       ntype = type_hash_canon (hashcode, ntype);
3288       ttype = build_qualified_type (ntype, TYPE_QUALS (ttype));
3289     }
3290
3291   return ttype;
3292 }
3293
3294
3295 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3296    or zero if not.
3297
3298    We try both `text' and `__text__', ATTR may be either one.  */
3299 /* ??? It might be a reasonable simplification to require ATTR to be only
3300    `text'.  One might then also require attribute lists to be stored in
3301    their canonicalized form.  */
3302
3303 static int
3304 is_attribute_with_length_p (const char *attr, int attr_len, tree ident)
3305 {
3306   int ident_len;
3307   const char *p;
3308
3309   if (TREE_CODE (ident) != IDENTIFIER_NODE)
3310     return 0;
3311
3312   p = IDENTIFIER_POINTER (ident);
3313   ident_len = IDENTIFIER_LENGTH (ident);
3314
3315   if (ident_len == attr_len
3316       && strcmp (attr, p) == 0)
3317     return 1;
3318
3319   /* If ATTR is `__text__', IDENT must be `text'; and vice versa.  */
3320   if (attr[0] == '_')
3321     {
3322       gcc_assert (attr[1] == '_');
3323       gcc_assert (attr[attr_len - 2] == '_');
3324       gcc_assert (attr[attr_len - 1] == '_');
3325       gcc_assert (attr[1] == '_');
3326       if (ident_len == attr_len - 4
3327           && strncmp (attr + 2, p, attr_len - 4) == 0)
3328         return 1;
3329     }
3330   else
3331     {
3332       if (ident_len == attr_len + 4
3333           && p[0] == '_' && p[1] == '_'
3334           && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
3335           && strncmp (attr, p + 2, attr_len) == 0)
3336         return 1;
3337     }
3338
3339   return 0;
3340 }
3341
3342 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3343    or zero if not.
3344
3345    We try both `text' and `__text__', ATTR may be either one.  */
3346
3347 int
3348 is_attribute_p (const char *attr, tree ident)
3349 {
3350   return is_attribute_with_length_p (attr, strlen (attr), ident);
3351 }
3352
3353 /* Given an attribute name and a list of attributes, return a pointer to the
3354    attribute's list element if the attribute is part of the list, or NULL_TREE
3355    if not found.  If the attribute appears more than once, this only
3356    returns the first occurrence; the TREE_CHAIN of the return value should
3357    be passed back in if further occurrences are wanted.  */
3358
3359 tree
3360 lookup_attribute (const char *attr_name, tree list)
3361 {
3362   tree l;
3363   size_t attr_len = strlen (attr_name);
3364
3365   for (l = list; l; l = TREE_CHAIN (l))
3366     {
3367       gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE);
3368       if (is_attribute_with_length_p (attr_name, attr_len, TREE_PURPOSE (l)))
3369         return l;
3370     }
3371
3372   return NULL_TREE;
3373 }
3374
3375 /* Return an attribute list that is the union of a1 and a2.  */
3376
3377 tree
3378 merge_attributes (tree a1, tree a2)
3379 {
3380   tree attributes;
3381
3382   /* Either one unset?  Take the set one.  */
3383
3384   if ((attributes = a1) == 0)
3385     attributes = a2;
3386
3387   /* One that completely contains the other?  Take it.  */
3388
3389   else if (a2 != 0 && ! attribute_list_contained (a1, a2))
3390     {
3391       if (attribute_list_contained (a2, a1))
3392         attributes = a2;
3393       else
3394         {
3395           /* Pick the longest list, and hang on the other list.  */
3396
3397           if (list_length (a1) < list_length (a2))
3398             attributes = a2, a2 = a1;
3399
3400           for (; a2 != 0; a2 = TREE_CHAIN (a2))
3401             {
3402               tree a;
3403               for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3404                                          attributes);
3405                    a != NULL_TREE;
3406                    a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3407                                          TREE_CHAIN (a)))
3408                 {
3409                   if (simple_cst_equal (TREE_VALUE (a), TREE_VALUE (a2)) == 1)
3410                     break;
3411                 }
3412               if (a == NULL_TREE)
3413                 {
3414                   a1 = copy_node (a2);
3415                   TREE_CHAIN (a1) = attributes;
3416                   attributes = a1;
3417                 }
3418             }
3419         }
3420     }
3421   return attributes;
3422 }
3423
3424 /* Given types T1 and T2, merge their attributes and return
3425   the result.  */
3426
3427 tree
3428 merge_type_attributes (tree t1, tree t2)
3429 {
3430   return merge_attributes (TYPE_ATTRIBUTES (t1),
3431                            TYPE_ATTRIBUTES (t2));
3432 }
3433
3434 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
3435    the result.  */
3436
3437 tree
3438 merge_decl_attributes (tree olddecl, tree newdecl)
3439 {
3440   return merge_attributes (DECL_ATTRIBUTES (olddecl),
3441                            DECL_ATTRIBUTES (newdecl));
3442 }
3443
3444 #if TARGET_DLLIMPORT_DECL_ATTRIBUTES
3445
3446 /* Specialization of merge_decl_attributes for various Windows targets.
3447
3448    This handles the following situation:
3449
3450      __declspec (dllimport) int foo;
3451      int foo;
3452
3453    The second instance of `foo' nullifies the dllimport.  */
3454
3455 tree
3456 merge_dllimport_decl_attributes (tree old, tree new)
3457 {
3458   tree a;
3459   int delete_dllimport_p;
3460
3461   old = DECL_ATTRIBUTES (old);
3462   new = DECL_ATTRIBUTES (new);
3463
3464   /* What we need to do here is remove from `old' dllimport if it doesn't
3465      appear in `new'.  dllimport behaves like extern: if a declaration is
3466      marked dllimport and a definition appears later, then the object
3467      is not dllimport'd.  */
3468   if (lookup_attribute ("dllimport", old) != NULL_TREE
3469       && lookup_attribute ("dllimport", new) == NULL_TREE)
3470     delete_dllimport_p = 1;
3471   else
3472     delete_dllimport_p = 0;
3473
3474   a = merge_attributes (old, new);
3475
3476   if (delete_dllimport_p)
3477     {
3478       tree prev, t;
3479
3480       /* Scan the list for dllimport and delete it.  */
3481       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
3482         {
3483           if (is_attribute_p ("dllimport", TREE_PURPOSE (t)))
3484             {
3485               if (prev == NULL_TREE)
3486                 a = TREE_CHAIN (a);
3487               else
3488                 TREE_CHAIN (prev) = TREE_CHAIN (t);
3489               break;
3490             }
3491         }
3492     }
3493
3494   return a;
3495 }
3496
3497 /* Handle a "dllimport" or "dllexport" attribute; arguments as in
3498    struct attribute_spec.handler.  */
3499
3500 tree
3501 handle_dll_attribute (tree * pnode, tree name, tree args, int flags,
3502                       bool *no_add_attrs)
3503 {
3504   tree node = *pnode;
3505
3506   /* These attributes may apply to structure and union types being created,
3507      but otherwise should pass to the declaration involved.  */
3508   if (!DECL_P (node))
3509     {
3510       if (flags & ((int) ATTR_FLAG_DECL_NEXT | (int) ATTR_FLAG_FUNCTION_NEXT
3511                    | (int) ATTR_FLAG_ARRAY_NEXT))
3512         {
3513           *no_add_attrs = true;
3514           return tree_cons (name, args, NULL_TREE);
3515         }
3516       if (TREE_CODE (node) != RECORD_TYPE && TREE_CODE (node) != UNION_TYPE)
3517         {
3518           warning (OPT_Wattributes, "%qs attribute ignored",
3519                    IDENTIFIER_POINTER (name));
3520           *no_add_attrs = true;
3521         }
3522
3523       return NULL_TREE;
3524     }
3525
3526   /* Report error on dllimport ambiguities seen now before they cause
3527      any damage.  */
3528   if (is_attribute_p ("dllimport", name))
3529     {
3530       /* Like MS, treat definition of dllimported variables and
3531          non-inlined functions on declaration as syntax errors.  We
3532          allow the attribute for function definitions if declared
3533          inline.  */
3534       if (TREE_CODE (node) == FUNCTION_DECL  && DECL_INITIAL (node)
3535           && !DECL_DECLARED_INLINE_P (node))
3536         {
3537           error ("function %q+D definition is marked dllimport", node);
3538           *no_add_attrs = true;
3539         }
3540
3541       else if (TREE_CODE (node) == VAR_DECL)
3542         {
3543           if (DECL_INITIAL (node))
3544             {
3545               error ("variable %q+D definition is marked dllimport",
3546                      node);
3547               *no_add_attrs = true;
3548             }
3549
3550           /* `extern' needn't be specified with dllimport.
3551              Specify `extern' now and hope for the best.  Sigh.  */
3552           DECL_EXTERNAL (node) = 1;
3553           /* Also, implicitly give dllimport'd variables declared within
3554              a function global scope, unless declared static.  */
3555           if (current_function_decl != NULL_TREE && !TREE_STATIC (node))
3556             TREE_PUBLIC (node) = 1;
3557         }
3558     }
3559
3560   /*  Report error if symbol is not accessible at global scope.  */
3561   if (!TREE_PUBLIC (node)
3562       && (TREE_CODE (node) == VAR_DECL
3563           || TREE_CODE (node) == FUNCTION_DECL))
3564     {
3565       error ("external linkage required for symbol %q+D because of "
3566              "%qs attribute", node, IDENTIFIER_POINTER (name));
3567       *no_add_attrs = true;
3568     }
3569
3570   return NULL_TREE;
3571 }
3572
3573 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
3574 \f
3575 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
3576    of the various TYPE_QUAL values.  */
3577
3578 static void
3579 set_type_quals (tree type, int type_quals)
3580 {
3581   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
3582   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
3583   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
3584 }
3585
3586 /* Returns true iff cand is equivalent to base with type_quals.  */
3587
3588 bool
3589 check_qualified_type (tree cand, tree base, int type_quals)
3590 {
3591   return (TYPE_QUALS (cand) == type_quals
3592           && TYPE_NAME (cand) == TYPE_NAME (base)
3593           /* Apparently this is needed for Objective-C.  */
3594           && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base)
3595           && attribute_list_equal (TYPE_ATTRIBUTES (cand),
3596                                    TYPE_ATTRIBUTES (base)));
3597 }
3598
3599 /* Return a version of the TYPE, qualified as indicated by the
3600    TYPE_QUALS, if one exists.  If no qualified version exists yet,
3601    return NULL_TREE.  */
3602
3603 tree
3604 get_qualified_type (tree type, int type_quals)
3605 {
3606   tree t;
3607
3608   if (TYPE_QUALS (type) == type_quals)
3609     return type;
3610
3611   /* Search the chain of variants to see if there is already one there just
3612      like the one we need to have.  If so, use that existing one.  We must
3613      preserve the TYPE_NAME, since there is code that depends on this.  */
3614   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
3615     if (check_qualified_type (t, type, type_quals))
3616       return t;
3617
3618   return NULL_TREE;
3619 }
3620
3621 /* Like get_qualified_type, but creates the type if it does not
3622    exist.  This function never returns NULL_TREE.  */
3623
3624 tree
3625 build_qualified_type (tree type, int type_quals)
3626 {
3627   tree t;
3628
3629   /* See if we already have the appropriate qualified variant.  */
3630   t = get_qualified_type (type, type_quals);
3631
3632   /* If not, build it.  */
3633   if (!t)
3634     {
3635       t = build_variant_type_copy (type);
3636       set_type_quals (t, type_quals);
3637     }
3638
3639   return t;
3640 }
3641
3642 /* Create a new distinct copy of TYPE.  The new type is made its own
3643    MAIN_VARIANT.  */
3644
3645 tree
3646 build_distinct_type_copy (tree type)
3647 {
3648   tree t = copy_node (type);
3649
3650   TYPE_POINTER_TO (t) = 0;
3651   TYPE_REFERENCE_TO (t) = 0;
3652
3653   /* Make it its own variant.  */
3654   TYPE_MAIN_VARIANT (t) = t;
3655   TYPE_NEXT_VARIANT (t) = 0;
3656
3657   return t;
3658 }
3659
3660 /* Create a new variant of TYPE, equivalent but distinct.
3661    This is so the caller can modify it.  */
3662
3663 tree
3664 build_variant_type_copy (tree type)
3665 {
3666   tree t, m = TYPE_MAIN_VARIANT (type);
3667
3668   t = build_distinct_type_copy (type);
3669
3670   /* Add the new type to the chain of variants of TYPE.  */
3671   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3672   TYPE_NEXT_VARIANT (m) = t;
3673   TYPE_MAIN_VARIANT (t) = m;
3674
3675   return t;
3676 }
3677 \f
3678 /* Return true if the from tree in both tree maps are equal.  */
3679
3680 int
3681 tree_map_eq (const void *va, const void *vb)
3682 {
3683   const struct tree_map  *a = va, *b = vb;
3684   return (a->from == b->from);
3685 }
3686
3687 /* Hash a from tree in a tree_map.  */
3688
3689 unsigned int
3690 tree_map_hash (const void *item)
3691 {
3692   return (((const struct tree_map *) item)->hash);
3693 }
3694
3695 /* Return true if this tree map structure is marked for garbage collection
3696    purposes.  We simply return true if the from tree is marked, so that this
3697    structure goes away when the from tree goes away.  */
3698
3699 int
3700 tree_map_marked_p (const void *p)
3701 {
3702   tree from = ((struct tree_map *) p)->from;
3703
3704   return ggc_marked_p (from);
3705 }
3706
3707 /* Return true if the trees in the tree_int_map *'s VA and VB are equal.  */
3708
3709 static int
3710 tree_int_map_eq (const void *va, const void *vb)
3711 {
3712   const struct tree_int_map  *a = va, *b = vb;
3713   return (a->from == b->from);
3714 }
3715
3716 /* Hash a from tree in the tree_int_map * ITEM.  */
3717
3718 static unsigned int
3719 tree_int_map_hash (const void *item)
3720 {
3721   return htab_hash_pointer (((const struct tree_int_map *)item)->from);
3722 }
3723
3724 /* Return true if this tree int map structure is marked for garbage collection
3725    purposes.  We simply return true if the from tree_int_map *P's from tree is marked, so that this
3726    structure goes away when the from tree goes away.  */
3727
3728 static int
3729 tree_int_map_marked_p (const void *p)
3730 {
3731   tree from = ((struct tree_int_map *) p)->from;
3732
3733   return ggc_marked_p (from);
3734 }
3735 /* Lookup an init priority for FROM, and return it if we find one.  */
3736
3737 unsigned short
3738 decl_init_priority_lookup (tree from)
3739 {
3740   struct tree_int_map *h, in;
3741   in.from = from;
3742
3743   h = htab_find_with_hash (init_priority_for_decl,
3744                            &in, htab_hash_pointer (from));
3745   if (h)
3746     return h->to;
3747   return 0;
3748 }
3749
3750 /* Insert a mapping FROM->TO in the init priority hashtable.  */
3751
3752 void
3753 decl_init_priority_insert (tree from, unsigned short to)
3754 {
3755   struct tree_int_map *h;
3756   void **loc;
3757
3758   h = ggc_alloc (sizeof (struct tree_int_map));
3759   h->from = from;
3760   h->to = to;
3761   loc = htab_find_slot_with_hash (init_priority_for_decl, h,
3762                                   htab_hash_pointer (from), INSERT);
3763   *(struct tree_int_map **) loc = h;
3764 }
3765
3766 /* Print out the statistics for the DECL_DEBUG_EXPR hash table.  */
3767
3768 static void
3769 print_debug_expr_statistics (void)
3770 {
3771   fprintf (stderr, "DECL_DEBUG_EXPR  hash: size %ld, %ld elements, %f collisions\n",
3772            (long) htab_size (debug_expr_for_decl),
3773            (long) htab_elements (debug_expr_for_decl),
3774            htab_collisions (debug_expr_for_decl));
3775 }
3776
3777 /* Print out the statistics for the DECL_VALUE_EXPR hash table.  */
3778
3779 static void
3780 print_value_expr_statistics (void)
3781 {
3782   fprintf (stderr, "DECL_VALUE_EXPR  hash: size %ld, %ld elements, %f collisions\n",
3783            (long) htab_size (value_expr_for_decl),
3784            (long) htab_elements (value_expr_for_decl),
3785            htab_collisions (value_expr_for_decl));
3786 }
3787 /* Lookup a debug expression for FROM, and return it if we find one.  */
3788
3789 tree
3790 decl_debug_expr_lookup (tree from)
3791 {
3792   struct tree_map *h, in;
3793   in.from = from;
3794
3795   h = htab_find_with_hash (debug_expr_for_decl, &in, htab_hash_pointer (from));
3796   if (h)
3797     return h->to;
3798   return NULL_TREE;
3799 }
3800
3801 /* Insert a mapping FROM->TO in the debug expression hashtable.  */
3802
3803 void
3804 decl_debug_expr_insert (tree from, tree to)
3805 {
3806   struct tree_map *h;
3807   void **loc;
3808
3809   h = ggc_alloc (sizeof (struct tree_map));
3810   h->hash = htab_hash_pointer (from);
3811   h->from = from;
3812   h->to = to;
3813   loc = htab_find_slot_with_hash (debug_expr_for_decl, h, h->hash, INSERT);
3814   *(struct tree_map **) loc = h;
3815 }
3816
3817 /* Lookup a value expression for FROM, and return it if we find one.  */
3818
3819 tree
3820 decl_value_expr_lookup (tree from)
3821 {
3822   struct tree_map *h, in;
3823   in.from = from;
3824
3825   h = htab_find_with_hash (value_expr_for_decl, &in, htab_hash_pointer (from));
3826   if (h)
3827     return h->to;
3828   return NULL_TREE;
3829 }
3830
3831 /* Insert a mapping FROM->TO in the value expression hashtable.  */
3832
3833 void
3834 decl_value_expr_insert (tree from, tree to)
3835 {
3836   struct tree_map *h;
3837   void **loc;
3838
3839   h = ggc_alloc (sizeof (struct tree_map));
3840   h->hash = htab_hash_pointer (from);
3841   h->from = from;
3842   h->to = to;
3843   loc = htab_find_slot_with_hash (value_expr_for_decl, h, h->hash, INSERT);
3844   *(struct tree_map **) loc = h;
3845 }
3846
3847 /* Hashing of types so that we don't make duplicates.
3848    The entry point is `type_hash_canon'.  */
3849
3850 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
3851    with types in the TREE_VALUE slots), by adding the hash codes
3852    of the individual types.  */
3853
3854 unsigned int
3855 type_hash_list (tree list, hashval_t hashcode)
3856 {
3857   tree tail;
3858
3859   for (tail = list; tail; tail = TREE_CHAIN (tail))
3860     if (TREE_VALUE (tail) != error_mark_node)
3861       hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
3862                                         hashcode);
3863
3864   return hashcode;
3865 }
3866
3867 /* These are the Hashtable callback functions.  */
3868
3869 /* Returns true iff the types are equivalent.  */
3870
3871 static int
3872 type_hash_eq (const void *va, const void *vb)
3873 {
3874   const struct type_hash *a = va, *b = vb;
3875
3876   /* First test the things that are the same for all types.  */
3877   if (a->hash != b->hash
3878       || TREE_CODE (a->type) != TREE_CODE (b->type)
3879       || TREE_TYPE (a->type) != TREE_TYPE (b->type)
3880       || !attribute_list_equal (TYPE_ATTRIBUTES (a->type),
3881                                  TYPE_ATTRIBUTES (b->type))
3882       || TYPE_ALIGN (a->type) != TYPE_ALIGN (b->type)
3883       || TYPE_MODE (a->type) != TYPE_MODE (b->type))
3884     return 0;
3885
3886   switch (TREE_CODE (a->type))
3887     {
3888     case VOID_TYPE:
3889     case COMPLEX_TYPE:
3890     case POINTER_TYPE:
3891     case REFERENCE_TYPE:
3892       return 1;
3893
3894     case VECTOR_TYPE:
3895       return TYPE_VECTOR_SUBPARTS (a->type) == TYPE_VECTOR_SUBPARTS (b->type);
3896
3897     case ENUMERAL_TYPE:
3898       if (TYPE_VALUES (a->type) != TYPE_VALUES (b->type)
3899           && !(TYPE_VALUES (a->type)
3900                && TREE_CODE (TYPE_VALUES (a->type)) == TREE_LIST
3901                && TYPE_VALUES (b->type)
3902                && TREE_CODE (TYPE_VALUES (b->type)) == TREE_LIST
3903                && type_list_equal (TYPE_VALUES (a->type),
3904                                    TYPE_VALUES (b->type))))
3905         return 0;
3906
3907       /* ... fall through ... */
3908
3909     case INTEGER_TYPE:
3910     case REAL_TYPE:
3911     case BOOLEAN_TYPE:
3912     case CHAR_TYPE:
3913       return ((TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
3914                || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
3915                                       TYPE_MAX_VALUE (b->type)))
3916               && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
3917                   || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
3918                                          TYPE_MIN_VALUE (b->type))));
3919
3920     case OFFSET_TYPE:
3921       return TYPE_OFFSET_BASETYPE (a->type) == TYPE_OFFSET_BASETYPE (b->type);
3922
3923     case METHOD_TYPE:
3924       return (TYPE_METHOD_BASETYPE (a->type) == TYPE_METHOD_BASETYPE (b->type)
3925               && (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
3926                   || (TYPE_ARG_TYPES (a->type)
3927                       && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
3928                       && TYPE_ARG_TYPES (b->type)
3929                       && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
3930                       && type_list_equal (TYPE_ARG_TYPES (a->type),
3931                                           TYPE_ARG_TYPES (b->type)))));
3932
3933     case ARRAY_TYPE:
3934       return TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type);
3935
3936     case RECORD_TYPE:
3937     case UNION_TYPE:
3938     case QUAL_UNION_TYPE:
3939       return (TYPE_FIELDS (a->type) == TYPE_FIELDS (b->type)
3940               || (TYPE_FIELDS (a->type)
3941                   && TREE_CODE (TYPE_FIELDS (a->type)) == TREE_LIST
3942                   && TYPE_FIELDS (b->type)
3943                   && TREE_CODE (TYPE_FIELDS (b->type)) == TREE_LIST
3944                   && type_list_equal (TYPE_FIELDS (a->type),
3945                                       TYPE_FIELDS (b->type))));
3946
3947     case FUNCTION_TYPE:
3948       return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
3949               || (TYPE_ARG_TYPES (a->type)
3950                   && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
3951                   && TYPE_ARG_TYPES (b->type)
3952                   && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
3953                   && type_list_equal (TYPE_ARG_TYPES (a->type),
3954                                       TYPE_ARG_TYPES (b->type))));
3955
3956     default:
3957       return 0;
3958     }
3959 }
3960
3961 /* Return the cached hash value.  */
3962
3963 static hashval_t
3964 type_hash_hash (const void *item)
3965 {
3966   return ((const struct type_hash *) item)->hash;
3967 }
3968
3969 /* Look in the type hash table for a type isomorphic to TYPE.
3970    If one is found, return it.  Otherwise return 0.  */
3971
3972 tree
3973 type_hash_lookup (hashval_t hashcode, tree type)
3974 {
3975   struct type_hash *h, in;
3976
3977   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
3978      must call that routine before comparing TYPE_ALIGNs.  */
3979   layout_type (type);
3980
3981   in.hash = hashcode;
3982   in.type = type;
3983
3984   h = htab_find_with_hash (type_hash_table, &in, hashcode);
3985   if (h)
3986     return h->type;
3987   return NULL_TREE;
3988 }
3989
3990 /* Add an entry to the type-hash-table
3991    for a type TYPE whose hash code is HASHCODE.  */
3992
3993 void
3994 type_hash_add (hashval_t hashcode, tree type)
3995 {
3996   struct type_hash *h;
3997   void **loc;
3998
3999   h = ggc_alloc (sizeof (struct type_hash));
4000   h->hash = hashcode;
4001   h->type = type;
4002   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
4003   *(struct type_hash **) loc = h;
4004 }
4005
4006 /* Given TYPE, and HASHCODE its hash code, return the canonical
4007    object for an identical type if one already exists.
4008    Otherwise, return TYPE, and record it as the canonical object.
4009
4010    To use this function, first create a type of the sort you want.
4011    Then compute its hash code from the fields of the type that
4012    make it different from other similar types.
4013    Then call this function and use the value.  */
4014
4015 tree
4016 type_hash_canon (unsigned int hashcode, tree type)
4017 {
4018   tree t1;
4019
4020   /* The hash table only contains main variants, so ensure that's what we're
4021      being passed.  */
4022   gcc_assert (TYPE_MAIN_VARIANT (type) == type);
4023
4024   if (!lang_hooks.types.hash_types)
4025     return type;
4026
4027   /* See if the type is in the hash table already.  If so, return it.
4028      Otherwise, add the type.  */
4029   t1 = type_hash_lookup (hashcode, type);
4030   if (t1 != 0)
4031     {
4032 #ifdef GATHER_STATISTICS
4033       tree_node_counts[(int) t_kind]--;
4034       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
4035 #endif
4036       return t1;
4037     }
4038   else
4039     {
4040       type_hash_add (hashcode, type);
4041       return type;
4042     }
4043 }
4044
4045 /* See if the data pointed to by the type hash table is marked.  We consider
4046    it marked if the type is marked or if a debug type number or symbol
4047    table entry has been made for the type.  This reduces the amount of
4048    debugging output and eliminates that dependency of the debug output on
4049    the number of garbage collections.  */
4050
4051 static int
4052 type_hash_marked_p (const void *p)
4053 {
4054   tree type = ((struct type_hash *) p)->type;
4055
4056   return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
4057 }
4058
4059 static void
4060 print_type_hash_statistics (void)
4061 {
4062   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
4063            (long) htab_size (type_hash_table),
4064            (long) htab_elements (type_hash_table),
4065            htab_collisions (type_hash_table));
4066 }
4067
4068 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
4069    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
4070    by adding the hash codes of the individual attributes.  */
4071
4072 unsigned int
4073 attribute_hash_list (tree list, hashval_t hashcode)
4074 {
4075   tree tail;
4076
4077   for (tail = list; tail; tail = TREE_CHAIN (tail))
4078     /* ??? Do we want to add in TREE_VALUE too? */
4079     hashcode = iterative_hash_object
4080       (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode);
4081   return hashcode;
4082 }
4083
4084 /* Given two lists of attributes, return true if list l2 is
4085    equivalent to l1.  */
4086
4087 int
4088 attribute_list_equal (tree l1, tree l2)
4089 {
4090   return attribute_list_contained (l1, l2)
4091          && attribute_list_contained (l2, l1);
4092 }
4093
4094 /* Given two lists of attributes, return true if list L2 is
4095    completely contained within L1.  */
4096 /* ??? This would be faster if attribute names were stored in a canonicalized
4097    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
4098    must be used to show these elements are equivalent (which they are).  */
4099 /* ??? It's not clear that attributes with arguments will always be handled
4100    correctly.  */
4101
4102 int
4103 attribute_list_contained (tree l1, tree l2)
4104 {
4105   tree t1, t2;
4106
4107   /* First check the obvious, maybe the lists are identical.  */
4108   if (l1 == l2)
4109     return 1;
4110
4111   /* Maybe the lists are similar.  */
4112   for (t1 = l1, t2 = l2;
4113        t1 != 0 && t2 != 0
4114         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
4115         && TREE_VALUE (t1) == TREE_VALUE (t2);
4116        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
4117
4118   /* Maybe the lists are equal.  */
4119   if (t1 == 0 && t2 == 0)
4120     return 1;
4121
4122   for (; t2 != 0; t2 = TREE_CHAIN (t2))
4123     {
4124       tree attr;
4125       for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
4126            attr != NULL_TREE;
4127            attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
4128                                     TREE_CHAIN (attr)))
4129         {
4130           if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
4131             break;
4132         }
4133
4134       if (attr == 0)
4135         return 0;
4136
4137       if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) != 1)
4138         return 0;
4139     }
4140
4141   return 1;
4142 }
4143
4144 /* Given two lists of types
4145    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
4146    return 1 if the lists contain the same types in the same order.
4147    Also, the TREE_PURPOSEs must match.  */
4148
4149 int
4150 type_list_equal (tree l1, tree l2)
4151 {
4152   tree t1, t2;
4153
4154   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
4155     if (TREE_VALUE (t1) != TREE_VALUE (t2)
4156         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
4157             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
4158                   && (TREE_TYPE (TREE_PURPOSE (t1))
4159                       == TREE_TYPE (TREE_PURPOSE (t2))))))
4160       return 0;
4161
4162   return t1 == t2;
4163 }
4164
4165 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
4166    given by TYPE.  If the argument list accepts variable arguments,
4167    then this function counts only the ordinary arguments.  */
4168
4169 int
4170 type_num_arguments (tree type)
4171 {
4172   int i = 0;
4173   tree t;
4174
4175   for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
4176     /* If the function does not take a variable number of arguments,
4177        the last element in the list will have type `void'.  */
4178     if (VOID_TYPE_P (TREE_VALUE (t)))
4179       break;
4180     else
4181       ++i;
4182
4183   return i;
4184 }
4185
4186 /* Nonzero if integer constants T1 and T2
4187    represent the same constant value.  */
4188
4189 int
4190 tree_int_cst_equal (tree t1, tree t2)
4191 {
4192   if (t1 == t2)
4193     return 1;
4194
4195   if (t1 == 0 || t2 == 0)
4196     return 0;
4197
4198   if (TREE_CODE (t1) == INTEGER_CST
4199       && TREE_CODE (t2) == INTEGER_CST
4200       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
4201       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
4202     return 1;
4203
4204   return 0;
4205 }
4206
4207 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
4208    The precise way of comparison depends on their data type.  */
4209
4210 int
4211 tree_int_cst_lt (tree t1, tree t2)
4212 {
4213   if (t1 == t2)
4214     return 0;
4215
4216   if (TYPE_UNSIGNED (TREE_TYPE (t1)) != TYPE_UNSIGNED (TREE_TYPE (t2)))
4217     {
4218       int t1_sgn = tree_int_cst_sgn (t1);
4219       int t2_sgn = tree_int_cst_sgn (t2);
4220
4221       if (t1_sgn < t2_sgn)
4222         return 1;
4223       else if (t1_sgn > t2_sgn)
4224         return 0;
4225       /* Otherwise, both are non-negative, so we compare them as
4226          unsigned just in case one of them would overflow a signed
4227          type.  */
4228     }
4229   else if (!TYPE_UNSIGNED (TREE_TYPE (t1)))
4230     return INT_CST_LT (t1, t2);
4231
4232   return INT_CST_LT_UNSIGNED (t1, t2);
4233 }
4234
4235 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
4236
4237 int
4238 tree_int_cst_compare (tree t1, tree t2)
4239 {
4240   if (tree_int_cst_lt (t1, t2))
4241     return -1;
4242   else if (tree_int_cst_lt (t2, t1))
4243     return 1;
4244   else
4245     return 0;
4246 }
4247
4248 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
4249    the host.  If POS is zero, the value can be represented in a single
4250    HOST_WIDE_INT.  If POS is nonzero, the value must be non-negative and can
4251    be represented in a single unsigned HOST_WIDE_INT.  */
4252
4253 int
4254 host_integerp (tree t, int pos)
4255 {
4256   return (TREE_CODE (t) == INTEGER_CST
4257           && ! TREE_OVERFLOW (t)
4258           && ((TREE_INT_CST_HIGH (t) == 0
4259                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
4260               || (! pos && TREE_INT_CST_HIGH (t) == -1
4261                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
4262                   && !TYPE_UNSIGNED (TREE_TYPE (t)))
4263               || (pos && TREE_INT_CST_HIGH (t) == 0)));
4264 }
4265
4266 /* Return the HOST_WIDE_INT least significant bits of T if it is an
4267    INTEGER_CST and there is no overflow.  POS is nonzero if the result must
4268    be non-negative.  We must be able to satisfy the above conditions.  */
4269
4270 HOST_WIDE_INT
4271 tree_low_cst (tree t, int pos)
4272 {
4273   gcc_assert (host_integerp (t, pos));
4274   return TREE_INT_CST_LOW (t);
4275 }
4276
4277 /* Return the most significant bit of the integer constant T.  */
4278
4279 int
4280 tree_int_cst_msb (tree t)
4281 {
4282   int prec;
4283   HOST_WIDE_INT h;
4284   unsigned HOST_WIDE_INT l;
4285
4286   /* Note that using TYPE_PRECISION here is wrong.  We care about the
4287      actual bits, not the (arbitrary) range of the type.  */
4288   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
4289   rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
4290                  2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
4291   return (l & 1) == 1;
4292 }
4293
4294 /* Return an indication of the sign of the integer constant T.
4295    The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
4296    Note that -1 will never be returned it T's type is unsigned.  */
4297
4298 int
4299 tree_int_cst_sgn (tree t)
4300 {
4301   if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
4302     return 0;
4303   else if (TYPE_UNSIGNED (TREE_TYPE (t)))
4304     return 1;
4305   else if (TREE_INT_CST_HIGH (t) < 0)
4306     return -1;
4307   else
4308     return 1;
4309 }
4310
4311 /* Compare two constructor-element-type constants.  Return 1 if the lists
4312    are known to be equal; otherwise return 0.  */
4313
4314 int
4315 simple_cst_list_equal (tree l1, tree l2)
4316 {
4317   while (l1 != NULL_TREE && l2 != NULL_TREE)
4318     {
4319       if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
4320         return 0;
4321
4322       l1 = TREE_CHAIN (l1);
4323       l2 = TREE_CHAIN (l2);
4324     }
4325
4326   return l1 == l2;
4327 }
4328
4329 /* Return truthvalue of whether T1 is the same tree structure as T2.
4330    Return 1 if they are the same.
4331    Return 0 if they are understandably different.
4332    Return -1 if either contains tree structure not understood by
4333    this function.  */
4334
4335 int
4336 simple_cst_equal (tree t1, tree t2)
4337 {
4338   enum tree_code code1, code2;
4339   int cmp;
4340   int i;
4341
4342   if (t1 == t2)
4343     return 1;
4344   if (t1 == 0 || t2 == 0)
4345     return 0;
4346
4347   code1 = TREE_CODE (t1);
4348   code2 = TREE_CODE (t2);
4349
4350   if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
4351     {
4352       if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
4353           || code2 == NON_LVALUE_EXPR)
4354         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4355       else
4356         return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
4357     }
4358
4359   else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
4360            || code2 == NON_LVALUE_EXPR)
4361     return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
4362
4363   if (code1 != code2)
4364     return 0;
4365
4366   switch (code1)
4367     {
4368     case INTEGER_CST:
4369       return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
4370               && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
4371
4372     case REAL_CST:
4373       return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
4374
4375     case STRING_CST:
4376       return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
4377               && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
4378                          TREE_STRING_LENGTH (t1)));
4379
4380     case CONSTRUCTOR:
4381       {
4382         unsigned HOST_WIDE_INT idx;
4383         VEC(constructor_elt, gc) *v1 = CONSTRUCTOR_ELTS (t1);
4384         VEC(constructor_elt, gc) *v2 = CONSTRUCTOR_ELTS (t2);
4385
4386         if (VEC_length (constructor_elt, v1) != VEC_length (constructor_elt, v2))
4387           return false;
4388
4389         for (idx = 0; idx < VEC_length (constructor_elt, v1); ++idx)
4390           /* ??? Should we handle also fields here? */
4391           if (!simple_cst_equal (VEC_index (constructor_elt, v1, idx)->value,
4392                                  VEC_index (constructor_elt, v2, idx)->value))
4393             return false;
4394         return true;
4395       }
4396
4397     case SAVE_EXPR:
4398       return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4399
4400     case CALL_EXPR:
4401       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4402       if (cmp <= 0)
4403         return cmp;
4404       return
4405         simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
4406
4407     case TARGET_EXPR:
4408       /* Special case: if either target is an unallocated VAR_DECL,
4409          it means that it's going to be unified with whatever the
4410          TARGET_EXPR is really supposed to initialize, so treat it
4411          as being equivalent to anything.  */
4412       if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
4413            && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
4414            && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
4415           || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
4416               && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
4417               && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
4418         cmp = 1;
4419       else
4420         cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4421
4422       if (cmp <= 0)
4423         return cmp;
4424
4425       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
4426
4427     case WITH_CLEANUP_EXPR:
4428       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4429       if (cmp <= 0)
4430         return cmp;
4431
4432       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
4433
4434     case COMPONENT_REF:
4435       if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
4436         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4437
4438       return 0;
4439
4440     case VAR_DECL:
4441     case PARM_DECL:
4442     case CONST_DECL:
4443     case FUNCTION_DECL:
4444       return 0;
4445
4446     default:
4447       break;
4448     }
4449
4450   /* This general rule works for most tree codes.  All exceptions should be
4451      handled above.  If this is a language-specific tree code, we can't
4452      trust what might be in the operand, so say we don't know
4453      the situation.  */
4454   if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
4455     return -1;
4456
4457   switch (TREE_CODE_CLASS (code1))
4458     {
4459     case tcc_unary:
4460     case tcc_binary:
4461     case tcc_comparison:
4462     case tcc_expression:
4463     case tcc_reference:
4464     case tcc_statement:
4465       cmp = 1;
4466       for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
4467         {
4468           cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
4469           if (cmp <= 0)
4470             return cmp;
4471         }
4472
4473       return cmp;
4474
4475     default:
4476       return -1;
4477     }
4478 }
4479
4480 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
4481    Return -1, 0, or 1 if the value of T is less than, equal to, or greater
4482    than U, respectively.  */
4483
4484 int
4485 compare_tree_int (tree t, unsigned HOST_WIDE_INT u)
4486 {
4487   if (tree_int_cst_sgn (t) < 0)
4488     return -1;
4489   else if (TREE_INT_CST_HIGH (t) != 0)
4490     return 1;
4491   else if (TREE_INT_CST_LOW (t) == u)
4492     return 0;
4493   else if (TREE_INT_CST_LOW (t) < u)
4494     return -1;
4495   else
4496     return 1;
4497 }
4498
4499 /* Return true if CODE represents an associative tree code.  Otherwise
4500    return false.  */
4501 bool
4502 associative_tree_code (enum tree_code code)
4503 {
4504   switch (code)
4505     {
4506     case BIT_IOR_EXPR:
4507     case BIT_AND_EXPR:
4508     case BIT_XOR_EXPR:
4509     case PLUS_EXPR:
4510     case MULT_EXPR:
4511     case MIN_EXPR:
4512     case MAX_EXPR:
4513       return true;
4514
4515     default:
4516       break;
4517     }
4518   return false;
4519 }
4520
4521 /* Return true if CODE represents a commutative tree code.  Otherwise
4522    return false.  */
4523 bool
4524 commutative_tree_code (enum tree_code code)
4525 {
4526   switch (code)
4527     {
4528     case PLUS_EXPR:
4529     case MULT_EXPR:
4530     case MIN_EXPR:
4531     case MAX_EXPR:
4532     case BIT_IOR_EXPR:
4533     case BIT_XOR_EXPR:
4534     case BIT_AND_EXPR:
4535     case NE_EXPR:
4536     case EQ_EXPR:
4537     case UNORDERED_EXPR:
4538     case ORDERED_EXPR:
4539     case UNEQ_EXPR:
4540     case LTGT_EXPR:
4541     case TRUTH_AND_EXPR:
4542     case TRUTH_XOR_EXPR:
4543     case TRUTH_OR_EXPR:
4544       return true;
4545
4546     default:
4547       break;
4548     }
4549   return false;
4550 }
4551
4552 /* Generate a hash value for an expression.  This can be used iteratively
4553    by passing a previous result as the "val" argument.
4554
4555    This function is intended to produce the same hash for expressions which
4556    would compare equal using operand_equal_p.  */
4557
4558 hashval_t
4559 iterative_hash_expr (tree t, hashval_t val)
4560 {
4561   int i;
4562   enum tree_code code;
4563   char class;
4564
4565   if (t == NULL_TREE)
4566     return iterative_hash_pointer (t, val);
4567
4568   code = TREE_CODE (t);
4569
4570   switch (code)
4571     {
4572     /* Alas, constants aren't shared, so we can't rely on pointer
4573        identity.  */
4574     case INTEGER_CST:
4575       val = iterative_hash_host_wide_int (TREE_INT_CST_LOW (t), val);
4576       return iterative_hash_host_wide_int (TREE_INT_CST_HIGH (t), val);
4577     case REAL_CST:
4578       {
4579         unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t));
4580
4581         return iterative_hash_hashval_t (val2, val);
4582       }
4583     case STRING_CST:
4584       return iterative_hash (TREE_STRING_POINTER (t),
4585                              TREE_STRING_LENGTH (t), val);
4586     case COMPLEX_CST:
4587       val = iterative_hash_expr (TREE_REALPART (t), val);
4588       return iterative_hash_expr (TREE_IMAGPART (t), val);
4589     case VECTOR_CST:
4590       return iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val);
4591
4592     case SSA_NAME:
4593     case VALUE_HANDLE:
4594       /* we can just compare by pointer.  */
4595       return iterative_hash_pointer (t, val);
4596
4597     case TREE_LIST:
4598       /* A list of expressions, for a CALL_EXPR or as the elements of a
4599          VECTOR_CST.  */
4600       for (; t; t = TREE_CHAIN (t))
4601         val = iterative_hash_expr (TREE_VALUE (t), val);
4602       return val;
4603     case CONSTRUCTOR:
4604       {
4605         unsigned HOST_WIDE_INT idx;
4606         tree field, value;
4607         FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (t), idx, field, value)
4608           {
4609             val = iterative_hash_expr (field, val);
4610             val = iterative_hash_expr (value, val);
4611           }
4612         return val;
4613       }
4614     case FUNCTION_DECL:
4615       /* When referring to a built-in FUNCTION_DECL, use the
4616          __builtin__ form.  Otherwise nodes that compare equal
4617          according to operand_equal_p might get different
4618          hash codes.  */
4619       if (DECL_BUILT_IN (t))
4620         {
4621           val = iterative_hash_pointer (built_in_decls[DECL_FUNCTION_CODE (t)],
4622                                       val);
4623           return val;
4624         }
4625       /* else FALL THROUGH */
4626     default:
4627       class = TREE_CODE_CLASS (code);
4628
4629       if (class == tcc_declaration)
4630         {
4631           /* Otherwise, we can just compare decls by pointer.  */
4632           val = iterative_hash_pointer (t, val);
4633         }
4634       else
4635         {
4636           gcc_assert (IS_EXPR_CODE_CLASS (class));
4637
4638           val = iterative_hash_object (code, val);
4639
4640           /* Don't hash the type, that can lead to having nodes which
4641              compare equal according to operand_equal_p, but which
4642              have different hash codes.  */
4643           if (code == NOP_EXPR
4644               || code == CONVERT_EXPR
4645               || code == NON_LVALUE_EXPR)
4646             {
4647               /* Make sure to include signness in the hash computation.  */
4648               val += TYPE_UNSIGNED (TREE_TYPE (t));
4649               val = iterative_hash_expr (TREE_OPERAND (t, 0), val);
4650             }
4651
4652           else if (commutative_tree_code (code))
4653             {
4654               /* It's a commutative expression.  We want to hash it the same
4655                  however it appears.  We do this by first hashing both operands
4656                  and then rehashing based on the order of their independent
4657                  hashes.  */
4658               hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
4659               hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0);
4660               hashval_t t;
4661
4662               if (one > two)
4663                 t = one, one = two, two = t;
4664
4665               val = iterative_hash_hashval_t (one, val);
4666               val = iterative_hash_hashval_t (two, val);
4667             }
4668           else
4669             for (i = TREE_CODE_LENGTH (code) - 1; i >= 0; --i)
4670               val = iterative_hash_expr (TREE_OPERAND (t, i), val);
4671         }
4672       return val;
4673       break;
4674     }
4675 }
4676 \f
4677 /* Constructors for pointer, array and function types.
4678    (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
4679    constructed by language-dependent code, not here.)  */
4680
4681 /* Construct, lay out and return the type of pointers to TO_TYPE with
4682    mode MODE.  If CAN_ALIAS_ALL is TRUE, indicate this type can
4683    reference all of memory. If such a type has already been
4684    constructed, reuse it.  */
4685
4686 tree
4687 build_pointer_type_for_mode (tree to_type, enum machine_mode mode,
4688                              bool can_alias_all)
4689 {
4690   tree t;
4691
4692   if (to_type == error_mark_node)
4693     return error_mark_node;
4694
4695   /* In some cases, languages will have things that aren't a POINTER_TYPE
4696      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_POINTER_TO.
4697      In that case, return that type without regard to the rest of our
4698      operands.
4699
4700      ??? This is a kludge, but consistent with the way this function has
4701      always operated and there doesn't seem to be a good way to avoid this
4702      at the moment.  */
4703   if (TYPE_POINTER_TO (to_type) != 0
4704       && TREE_CODE (TYPE_POINTER_TO (to_type)) != POINTER_TYPE)
4705     return TYPE_POINTER_TO (to_type);
4706
4707   /* First, if we already have a type for pointers to TO_TYPE and it's
4708      the proper mode, use it.  */
4709   for (t = TYPE_POINTER_TO (to_type); t; t = TYPE_NEXT_PTR_TO (t))
4710     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4711       return t;
4712
4713   t = make_node (POINTER_TYPE);
4714
4715   TREE_TYPE (t) = to_type;
4716   TYPE_MODE (t) = mode;
4717   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4718   TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
4719   TYPE_POINTER_TO (to_type) = t;
4720
4721   /* Lay out the type.  This function has many callers that are concerned
4722      with expression-construction, and this simplifies them all.  */
4723   layout_type (t);
4724
4725   return t;
4726 }
4727
4728 /* By default build pointers in ptr_mode.  */
4729
4730 tree
4731 build_pointer_type (tree to_type)
4732 {
4733   return build_pointer_type_for_mode (to_type, ptr_mode, false);
4734 }
4735
4736 /* Same as build_pointer_type_for_mode, but for REFERENCE_TYPE.  */
4737
4738 tree
4739 build_reference_type_for_mode (tree to_type, enum machine_mode mode,
4740                                bool can_alias_all)
4741 {
4742   tree t;
4743
4744   /* In some cases, languages will have things that aren't a REFERENCE_TYPE
4745      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_REFERENCE_TO.
4746      In that case, return that type without regard to the rest of our
4747      operands.
4748
4749      ??? This is a kludge, but consistent with the way this function has
4750      always operated and there doesn't seem to be a good way to avoid this
4751      at the moment.  */
4752   if (TYPE_REFERENCE_TO (to_type) != 0
4753       && TREE_CODE (TYPE_REFERENCE_TO (to_type)) != REFERENCE_TYPE)
4754     return TYPE_REFERENCE_TO (to_type);
4755
4756   /* First, if we already have a type for pointers to TO_TYPE and it's
4757      the proper mode, use it.  */
4758   for (t = TYPE_REFERENCE_TO (to_type); t; t = TYPE_NEXT_REF_TO (t))
4759     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4760       return t;
4761
4762   t = make_node (REFERENCE_TYPE);
4763
4764   TREE_TYPE (t) = to_type;
4765   TYPE_MODE (t) = mode;
4766   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4767   TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
4768   TYPE_REFERENCE_TO (to_type) = t;
4769
4770   layout_type (t);
4771
4772   return t;
4773 }
4774
4775
4776 /* Build the node for the type of references-to-TO_TYPE by default
4777    in ptr_mode.  */
4778
4779 tree
4780 build_reference_type (tree to_type)
4781 {
4782   return build_reference_type_for_mode (to_type, ptr_mode, false);
4783 }
4784
4785 /* Build a type that is compatible with t but has no cv quals anywhere
4786    in its type, thus
4787
4788    const char *const *const *  ->  char ***.  */
4789
4790 tree
4791 build_type_no_quals (tree t)
4792 {
4793   switch (TREE_CODE (t))
4794     {
4795     case POINTER_TYPE:
4796       return build_pointer_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4797                                           TYPE_MODE (t),
4798                                           TYPE_REF_CAN_ALIAS_ALL (t));
4799     case REFERENCE_TYPE:
4800       return
4801         build_reference_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4802                                        TYPE_MODE (t),
4803                                        TYPE_REF_CAN_ALIAS_ALL (t));
4804     default:
4805       return TYPE_MAIN_VARIANT (t);
4806     }
4807 }
4808
4809 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
4810    MAXVAL should be the maximum value in the domain
4811    (one less than the length of the array).
4812
4813    The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
4814    We don't enforce this limit, that is up to caller (e.g. language front end).
4815    The limit exists because the result is a signed type and we don't handle
4816    sizes that use more than one HOST_WIDE_INT.  */
4817
4818 tree
4819 build_index_type (tree maxval)
4820 {
4821   tree itype = make_node (INTEGER_TYPE);
4822
4823   TREE_TYPE (itype) = sizetype;
4824   TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
4825   TYPE_MIN_VALUE (itype) = size_zero_node;
4826   TYPE_MAX_VALUE (itype) = fold_convert (sizetype, maxval);
4827   TYPE_MODE (itype) = TYPE_MODE (sizetype);
4828   TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
4829   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
4830   TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
4831   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
4832
4833   if (host_integerp (maxval, 1))
4834     return type_hash_canon (tree_low_cst (maxval, 1), itype);
4835   else
4836     return itype;
4837 }
4838
4839 /* Builds a signed or unsigned integer type of precision PRECISION.
4840    Used for C bitfields whose precision does not match that of
4841    built-in target types.  */
4842 tree
4843 build_nonstandard_integer_type (unsigned HOST_WIDE_INT precision,
4844                                 int unsignedp)
4845 {
4846   tree itype = make_node (INTEGER_TYPE);
4847
4848   TYPE_PRECISION (itype) = precision;
4849
4850   if (unsignedp)
4851     fixup_unsigned_type (itype);
4852   else
4853     fixup_signed_type (itype);
4854
4855   if (host_integerp (TYPE_MAX_VALUE (itype), 1))
4856     return type_hash_canon (tree_low_cst (TYPE_MAX_VALUE (itype), 1), itype);
4857
4858   return itype;
4859 }
4860
4861 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
4862    ENUMERAL_TYPE, BOOLEAN_TYPE, or CHAR_TYPE), with
4863    low bound LOWVAL and high bound HIGHVAL.
4864    if TYPE==NULL_TREE, sizetype is used.  */
4865
4866 tree
4867 build_range_type (tree type, tree lowval, tree highval)
4868 {
4869   tree itype = make_node (INTEGER_TYPE);
4870
4871   TREE_TYPE (itype) = type;
4872   if (type == NULL_TREE)
4873     type = sizetype;
4874
4875   TYPE_MIN_VALUE (itype) = convert (type, lowval);
4876   TYPE_MAX_VALUE (itype) = highval ? convert (type, highval) : NULL;
4877
4878   TYPE_PRECISION (itype) = TYPE_PRECISION (type);
4879   TYPE_MODE (itype) = TYPE_MODE (type);
4880   TYPE_SIZE (itype) = TYPE_SIZE (type);
4881   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type);
4882   TYPE_ALIGN (itype) = TYPE_ALIGN (type);
4883   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type);
4884
4885   if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0))
4886     return type_hash_canon (tree_low_cst (highval, 0)
4887                             - tree_low_cst (lowval, 0),
4888                             itype);
4889   else
4890     return itype;
4891 }
4892
4893 /* Just like build_index_type, but takes lowval and highval instead
4894    of just highval (maxval).  */
4895
4896 tree
4897 build_index_2_type (tree lowval, tree highval)
4898 {
4899   return build_range_type (sizetype, lowval, highval);
4900 }
4901
4902 /* Construct, lay out and return the type of arrays of elements with ELT_TYPE
4903    and number of elements specified by the range of values of INDEX_TYPE.
4904    If such a type has already been constructed, reuse it.  */
4905
4906 tree
4907 build_array_type (tree elt_type, tree index_type)
4908 {
4909   tree t;
4910   hashval_t hashcode = 0;
4911
4912   if (TREE_CODE (elt_type) == FUNCTION_TYPE)
4913     {
4914       error ("arrays of functions are not meaningful");
4915       elt_type = integer_type_node;
4916     }
4917
4918   t = make_node (ARRAY_TYPE);
4919   TREE_TYPE (t) = elt_type;
4920   TYPE_DOMAIN (t) = index_type;
4921
4922   if (index_type == 0)
4923     {
4924       layout_type (t);
4925       return t;
4926     }
4927
4928   hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode);
4929   hashcode = iterative_hash_object (TYPE_HASH (index_type), hashcode);
4930   t = type_hash_canon (hashcode, t);
4931
4932   if (!COMPLETE_TYPE_P (t))
4933     layout_type (t);
4934   return t;
4935 }
4936
4937 /* Return the TYPE of the elements comprising
4938    the innermost dimension of ARRAY.  */
4939
4940 tree
4941 get_inner_array_type (tree array)
4942 {
4943   tree type = TREE_TYPE (array);
4944
4945   while (TREE_CODE (type) == ARRAY_TYPE)
4946     type = TREE_TYPE (type);
4947
4948   return type;
4949 }
4950
4951 /* Construct, lay out and return
4952    the type of functions returning type VALUE_TYPE
4953    given arguments of types ARG_TYPES.
4954    ARG_TYPES is a chain of TREE_LIST nodes whose TREE_VALUEs
4955    are data type nodes for the arguments of the function.
4956    If such a type has already been constructed, reuse it.  */
4957
4958 tree
4959 build_function_type (tree value_type, tree arg_types)
4960 {
4961   tree t;
4962   hashval_t hashcode = 0;
4963
4964   if (TREE_CODE (value_type) == FUNCTION_TYPE)
4965     {
4966       error ("function return type cannot be function");
4967       value_type = integer_type_node;
4968     }
4969
4970   /* Make a node of the sort we want.  */
4971   t = make_node (FUNCTION_TYPE);
4972   TREE_TYPE (t) = value_type;
4973   TYPE_ARG_TYPES (t) = arg_types;
4974
4975   /* If we already have such a type, use the old one.  */
4976   hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode);
4977   hashcode = type_hash_list (arg_types, hashcode);
4978   t = type_hash_canon (hashcode, t);
4979
4980   if (!COMPLETE_TYPE_P (t))
4981     layout_type (t);
4982   return t;
4983 }
4984
4985 /* Build a function type.  The RETURN_TYPE is the type returned by the
4986    function.  If additional arguments are provided, they are
4987    additional argument types.  The list of argument types must always
4988    be terminated by NULL_TREE.  */
4989
4990 tree
4991 build_function_type_list (tree return_type, ...)
4992 {
4993   tree t, args, last;
4994   va_list p;
4995
4996   va_start (p, return_type);
4997
4998   t = va_arg (p, tree);
4999   for (args = NULL_TREE; t != NULL_TREE; t = va_arg (p, tree))
5000     args = tree_cons (NULL_TREE, t, args);
5001
5002   if (args == NULL_TREE)
5003     args = void_list_node;
5004   else
5005     {
5006       last = args;
5007       args = nreverse (args);
5008       TREE_CHAIN (last) = void_list_node;
5009     }
5010   args = build_function_type (return_type, args);
5011
5012   va_end (p);
5013   return args;
5014 }
5015
5016 /* Build a METHOD_TYPE for a member of BASETYPE.  The RETTYPE (a TYPE)
5017    and ARGTYPES (a TREE_LIST) are the return type and arguments types
5018    for the method.  An implicit additional parameter (of type
5019    pointer-to-BASETYPE) is added to the ARGTYPES.  */
5020
5021 tree
5022 build_method_type_directly (tree basetype,
5023                             tree rettype,
5024                             tree argtypes)
5025 {
5026   tree t;
5027   tree ptype;
5028   int hashcode = 0;
5029
5030   /* Make a node of the sort we want.  */
5031   t = make_node (METHOD_TYPE);
5032
5033   TYPE_METHOD_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
5034   TREE_TYPE (t) = rettype;
5035   ptype = build_pointer_type (basetype);
5036
5037   /* The actual arglist for this function includes a "hidden" argument
5038      which is "this".  Put it into the list of argument types.  */
5039   argtypes = tree_cons (NULL_TREE, ptype, argtypes);
5040   TYPE_ARG_TYPES (t) = argtypes;
5041
5042   /* If we already have such a type, use the old one.  */
5043   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
5044   hashcode = iterative_hash_object (TYPE_HASH (rettype), hashcode);
5045   hashcode = type_hash_list (argtypes, hashcode);
5046   t = type_hash_canon (hashcode, t);
5047
5048   if (!COMPLETE_TYPE_P (t))
5049     layout_type (t);
5050
5051   return t;
5052 }
5053
5054 /* Construct, lay out and return the type of methods belonging to class
5055    BASETYPE and whose arguments and values are described by TYPE.
5056    If that type exists already, reuse it.
5057    TYPE must be a FUNCTION_TYPE node.  */
5058
5059 tree
5060 build_method_type (tree basetype, tree type)
5061 {
5062   gcc_assert (TREE_CODE (type) == FUNCTION_TYPE);
5063
5064   return build_method_type_directly (basetype,
5065                                      TREE_TYPE (type),
5066                                      TYPE_ARG_TYPES (type));
5067 }
5068
5069 /* Construct, lay out and return the type of offsets to a value
5070    of type TYPE, within an object of type BASETYPE.
5071    If a suitable offset type exists already, reuse it.  */
5072
5073 tree
5074 build_offset_type (tree basetype, tree type)
5075 {
5076   tree t;
5077   hashval_t hashcode = 0;
5078
5079   /* Make a node of the sort we want.  */
5080   t = make_node (OFFSET_TYPE);
5081
5082   TYPE_OFFSET_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
5083   TREE_TYPE (t) = type;
5084
5085   /* If we already have such a type, use the old one.  */
5086   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
5087   hashcode = iterative_hash_object (TYPE_HASH (type), hashcode);
5088   t = type_hash_canon (hashcode, t);
5089
5090   if (!COMPLETE_TYPE_P (t))
5091     layout_type (t);
5092
5093   return t;
5094 }
5095
5096 /* Create a complex type whose components are COMPONENT_TYPE.  */
5097
5098 tree
5099 build_complex_type (tree component_type)
5100 {
5101   tree t;
5102   hashval_t hashcode;
5103
5104   /* Make a node of the sort we want.  */
5105   t = make_node (COMPLEX_TYPE);
5106
5107   TREE_TYPE (t) = TYPE_MAIN_VARIANT (component_type);
5108
5109   /* If we already have such a type, use the old one.  */
5110   hashcode = iterative_hash_object (TYPE_HASH (component_type), 0);
5111   t = type_hash_canon (hashcode, t);
5112
5113   if (!COMPLETE_TYPE_P (t))
5114     layout_type (t);
5115
5116   /* If we are writing Dwarf2 output we need to create a name,
5117      since complex is a fundamental type.  */
5118   if ((write_symbols == DWARF2_DEBUG || write_symbols == VMS_AND_DWARF2_DEBUG)
5119       && ! TYPE_NAME (t))
5120     {
5121       const char *name;
5122       if (component_type == char_type_node)
5123         name = "complex char";
5124       else if (component_type == signed_char_type_node)
5125         name = "complex signed char";
5126       else if (component_type == unsigned_char_type_node)
5127         name = "complex unsigned char";
5128       else if (component_type == short_integer_type_node)
5129         name = "complex short int";
5130       else if (component_type == short_unsigned_type_node)
5131         name = "complex short unsigned int";
5132       else if (component_type == integer_type_node)
5133         name = "complex int";
5134       else if (component_type == unsigned_type_node)
5135         name = "complex unsigned int";
5136       else if (component_type == long_integer_type_node)
5137         name = "complex long int";
5138       else if (component_type == long_unsigned_type_node)
5139         name = "complex long unsigned int";
5140       else if (component_type == long_long_integer_type_node)
5141         name = "complex long long int";
5142       else if (component_type == long_long_unsigned_type_node)
5143         name = "complex long long unsigned int";
5144       else
5145         name = 0;
5146
5147       if (name != 0)
5148         TYPE_NAME (t) = get_identifier (name);
5149     }
5150
5151   return build_qualified_type (t, TYPE_QUALS (component_type));
5152 }
5153 \f
5154 /* Return OP, stripped of any conversions to wider types as much as is safe.
5155    Converting the value back to OP's type makes a value equivalent to OP.
5156
5157    If FOR_TYPE is nonzero, we return a value which, if converted to
5158    type FOR_TYPE, would be equivalent to converting OP to type FOR_TYPE.
5159
5160    If FOR_TYPE is nonzero, unaligned bit-field references may be changed to the
5161    narrowest type that can hold the value, even if they don't exactly fit.
5162    Otherwise, bit-field references are changed to a narrower type
5163    only if they can be fetched directly from memory in that type.
5164
5165    OP must have integer, real or enumeral type.  Pointers are not allowed!
5166
5167    There are some cases where the obvious value we could return
5168    would regenerate to OP if converted to OP's type,
5169    but would not extend like OP to wider types.
5170    If FOR_TYPE indicates such extension is contemplated, we eschew such values.
5171    For example, if OP is (unsigned short)(signed char)-1,
5172    we avoid returning (signed char)-1 if FOR_TYPE is int,
5173    even though extending that to an unsigned short would regenerate OP,
5174    since the result of extending (signed char)-1 to (int)
5175    is different from (int) OP.  */
5176
5177 tree
5178 get_unwidened (tree op, tree for_type)
5179 {
5180   /* Set UNS initially if converting OP to FOR_TYPE is a zero-extension.  */
5181   tree type = TREE_TYPE (op);
5182   unsigned final_prec
5183     = TYPE_PRECISION (for_type != 0 ? for_type : type);
5184   int uns
5185     = (for_type != 0 && for_type != type
5186        && final_prec > TYPE_PRECISION (type)
5187        && TYPE_UNSIGNED (type));
5188   tree win = op;
5189
5190   while (TREE_CODE (op) == NOP_EXPR
5191          || TREE_CODE (op) == CONVERT_EXPR)
5192     {
5193       int bitschange;
5194
5195       /* TYPE_PRECISION on vector types has different meaning
5196          (TYPE_VECTOR_SUBPARTS) and casts from vectors are view conversions,
5197          so avoid them here.  */
5198       if (TREE_CODE (TREE_TYPE (TREE_OPERAND (op, 0))) == VECTOR_TYPE)
5199         break;
5200
5201       bitschange = TYPE_PRECISION (TREE_TYPE (op))
5202                    - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0)));
5203
5204       /* Truncations are many-one so cannot be removed.
5205          Unless we are later going to truncate down even farther.  */
5206       if (bitschange < 0
5207           && final_prec > TYPE_PRECISION (TREE_TYPE (op)))
5208         break;
5209
5210       /* See what's inside this conversion.  If we decide to strip it,
5211          we will set WIN.  */
5212       op = TREE_OPERAND (op, 0);
5213
5214       /* If we have not stripped any zero-extensions (uns is 0),
5215          we can strip any kind of extension.
5216          If we have previously stripped a zero-extension,
5217          only zero-extensions can safely be stripped.
5218          Any extension can be stripped if the bits it would produce
5219          are all going to be discarded later by truncating to FOR_TYPE.  */
5220
5221       if (bitschange > 0)
5222         {
5223           if (! uns || final_prec <= TYPE_PRECISION (TREE_TYPE (op)))
5224             win = op;
5225           /* TYPE_UNSIGNED says whether this is a zero-extension.
5226              Let's avoid computing it if it does not affect WIN
5227              and if UNS will not be needed again.  */
5228           if ((uns
5229                || TREE_CODE (op) == NOP_EXPR
5230                || TREE_CODE (op) == CONVERT_EXPR)
5231               && TYPE_UNSIGNED (TREE_TYPE (op)))
5232             {
5233               uns = 1;
5234               win = op;
5235             }
5236         }
5237     }
5238
5239   if (TREE_CODE (op) == COMPONENT_REF
5240       /* Since type_for_size always gives an integer type.  */
5241       && TREE_CODE (type) != REAL_TYPE
5242       /* Don't crash if field not laid out yet.  */
5243       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
5244       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
5245     {
5246       unsigned int innerprec
5247         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
5248       int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
5249                        || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
5250       type = lang_hooks.types.type_for_size (innerprec, unsignedp);
5251
5252       /* We can get this structure field in the narrowest type it fits in.
5253          If FOR_TYPE is 0, do this only for a field that matches the
5254          narrower type exactly and is aligned for it
5255          The resulting extension to its nominal type (a fullword type)
5256          must fit the same conditions as for other extensions.  */
5257
5258       if (type != 0
5259           && INT_CST_LT_UNSIGNED (TYPE_SIZE (type), TYPE_SIZE (TREE_TYPE (op)))
5260           && (for_type || ! DECL_BIT_FIELD (TREE_OPERAND (op, 1)))
5261           && (! uns || final_prec <= innerprec || unsignedp))
5262         {
5263           win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
5264                         TREE_OPERAND (op, 1), NULL_TREE);
5265           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
5266           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
5267         }
5268     }
5269
5270   return win;
5271 }
5272 \f
5273 /* Return OP or a simpler expression for a narrower value
5274    which can be sign-extended or zero-extended to give back OP.
5275    Store in *UNSIGNEDP_PTR either 1 if the value should be zero-extended
5276    or 0 if the value should be sign-extended.  */
5277
5278 tree
5279 get_narrower (tree op, int *unsignedp_ptr)
5280 {
5281   int uns = 0;
5282   int first = 1;
5283   tree win = op;
5284   bool integral_p = INTEGRAL_TYPE_P (TREE_TYPE (op));
5285
5286   while (TREE_CODE (op) == NOP_EXPR)
5287     {
5288       int bitschange
5289         = (TYPE_PRECISION (TREE_TYPE (op))
5290            - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0))));
5291
5292       /* Truncations are many-one so cannot be removed.  */
5293       if (bitschange < 0)
5294         break;
5295
5296       /* See what's inside this conversion.  If we decide to strip it,
5297          we will set WIN.  */
5298
5299       if (bitschange > 0)
5300         {
5301           op = TREE_OPERAND (op, 0);
5302           /* An extension: the outermost one can be stripped,
5303              but remember whether it is zero or sign extension.  */
5304           if (first)
5305             uns = TYPE_UNSIGNED (TREE_TYPE (op));
5306           /* Otherwise, if a sign extension has been stripped,
5307              only sign extensions can now be stripped;
5308              if a zero extension has been stripped, only zero-extensions.  */
5309           else if (uns != TYPE_UNSIGNED (TREE_TYPE (op)))
5310             break;
5311           first = 0;
5312         }
5313       else /* bitschange == 0 */
5314         {
5315           /* A change in nominal type can always be stripped, but we must
5316              preserve the unsignedness.  */
5317           if (first)
5318             uns = TYPE_UNSIGNED (TREE_TYPE (op));
5319           first = 0;
5320           op = TREE_OPERAND (op, 0);
5321           /* Keep trying to narrow, but don't assign op to win if it
5322              would turn an integral type into something else.  */
5323           if (INTEGRAL_TYPE_P (TREE_TYPE (op)) != integral_p)
5324             continue;
5325         }
5326
5327       win = op;
5328     }
5329
5330   if (TREE_CODE (op) == COMPONENT_REF
5331       /* Since type_for_size always gives an integer type.  */
5332       && TREE_CODE (TREE_TYPE (op)) != REAL_TYPE
5333       /* Ensure field is laid out already.  */
5334       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
5335       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
5336     {
5337       unsigned HOST_WIDE_INT innerprec
5338         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
5339       int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
5340                        || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
5341       tree type = lang_hooks.types.type_for_size (innerprec, unsignedp);
5342
5343       /* We can get this structure field in a narrower type that fits it,
5344          but the resulting extension to its nominal type (a fullword type)
5345          must satisfy the same conditions as for other extensions.
5346
5347          Do this only for fields that are aligned (not bit-fields),
5348          because when bit-field insns will be used there is no
5349          advantage in doing this.  */
5350
5351       if (innerprec < TYPE_PRECISION (TREE_TYPE (op))
5352           && ! DECL_BIT_FIELD (TREE_OPERAND (op, 1))
5353           && (first || uns == DECL_UNSIGNED (TREE_OPERAND (op, 1)))
5354           && type != 0)
5355         {
5356           if (first)
5357             uns = DECL_UNSIGNED (TREE_OPERAND (op, 1));
5358           win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
5359                         TREE_OPERAND (op, 1), NULL_TREE);
5360           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
5361           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
5362         }
5363     }
5364   *unsignedp_ptr = uns;
5365   return win;
5366 }
5367 \f
5368 /* Nonzero if integer constant C has a value that is permissible
5369    for type TYPE (an INTEGER_TYPE).  */
5370
5371 int
5372 int_fits_type_p (tree c, tree type)
5373 {
5374   tree type_low_bound = TYPE_MIN_VALUE (type);
5375   tree type_high_bound = TYPE_MAX_VALUE (type);
5376   bool ok_for_low_bound, ok_for_high_bound;
5377   tree tmp;
5378
5379   /* If at least one bound of the type is a constant integer, we can check
5380      ourselves and maybe make a decision. If no such decision is possible, but
5381      this type is a subtype, try checking against that.  Otherwise, use
5382      force_fit_type, which checks against the precision.
5383
5384      Compute the status for each possibly constant bound, and return if we see
5385      one does not match. Use ok_for_xxx_bound for this purpose, assigning -1
5386      for "unknown if constant fits", 0 for "constant known *not* to fit" and 1
5387      for "constant known to fit".  */
5388
5389   /* Check if C >= type_low_bound.  */
5390   if (type_low_bound && TREE_CODE (type_low_bound) == INTEGER_CST)
5391     {
5392       if (tree_int_cst_lt (c, type_low_bound))
5393         return 0;
5394       ok_for_low_bound = true;
5395     }
5396   else
5397     ok_for_low_bound = false;
5398
5399   /* Check if c <= type_high_bound.  */
5400   if (type_high_bound && TREE_CODE (type_high_bound) == INTEGER_CST)
5401     {
5402       if (tree_int_cst_lt (type_high_bound, c))
5403         return 0;
5404       ok_for_high_bound = true;
5405     }
5406   else
5407     ok_for_high_bound = false;
5408
5409   /* If the constant fits both bounds, the result is known.  */
5410   if (ok_for_low_bound && ok_for_high_bound)
5411     return 1;
5412
5413   /* Perform some generic filtering which may allow making a decision
5414      even if the bounds are not constant.  First, negative integers
5415      never fit in unsigned types, */
5416   if (TYPE_UNSIGNED (type) && tree_int_cst_sgn (c) < 0)
5417     return 0;
5418
5419   /* Second, narrower types always fit in wider ones.  */
5420   if (TYPE_PRECISION (type) > TYPE_PRECISION (TREE_TYPE (c)))
5421     return 1;
5422
5423   /* Third, unsigned integers with top bit set never fit signed types.  */
5424   if (! TYPE_UNSIGNED (type)
5425       && TYPE_UNSIGNED (TREE_TYPE (c))
5426       && tree_int_cst_msb (c))
5427     return 0;
5428
5429   /* If we haven't been able to decide at this point, there nothing more we
5430      can check ourselves here. Look at the base type if we have one.  */
5431   if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != 0)
5432     return int_fits_type_p (c, TREE_TYPE (type));
5433
5434   /* Or to force_fit_type, if nothing else.  */
5435   tmp = copy_node (c);
5436   TREE_TYPE (tmp) = type;
5437   tmp = force_fit_type (tmp, -1, false, false);
5438   return TREE_INT_CST_HIGH (tmp) == TREE_INT_CST_HIGH (c)
5439          && TREE_INT_CST_LOW (tmp) == TREE_INT_CST_LOW (c);
5440 }
5441
5442 /* Subprogram of following function.  Called by walk_tree.
5443
5444    Return *TP if it is an automatic variable or parameter of the
5445    function passed in as DATA.  */
5446
5447 static tree
5448 find_var_from_fn (tree *tp, int *walk_subtrees, void *data)
5449 {
5450   tree fn = (tree) data;
5451
5452   if (TYPE_P (*tp))
5453     *walk_subtrees = 0;
5454
5455   else if (DECL_P (*tp)
5456            && lang_hooks.tree_inlining.auto_var_in_fn_p (*tp, fn))
5457     return *tp;
5458
5459   return NULL_TREE;
5460 }
5461
5462 /* Returns true if T is, contains, or refers to a type with variable
5463    size.  If FN is nonzero, only return true if a modifier of the type
5464    or position of FN is a variable or parameter inside FN.
5465
5466    This concept is more general than that of C99 'variably modified types':
5467    in C99, a struct type is never variably modified because a VLA may not
5468    appear as a structure member.  However, in GNU C code like:
5469
5470      struct S { int i[f()]; };
5471
5472    is valid, and other languages may define similar constructs.  */
5473
5474 bool
5475 variably_modified_type_p (tree type, tree fn)
5476 {
5477   tree t;
5478
5479 /* Test if T is either variable (if FN is zero) or an expression containing
5480    a variable in FN.  */
5481 #define RETURN_TRUE_IF_VAR(T)                                           \
5482   do { tree _t = (T);                                                   \
5483     if (_t && _t != error_mark_node && TREE_CODE (_t) != INTEGER_CST    \
5484         && (!fn || walk_tree (&_t, find_var_from_fn, fn, NULL)))        \
5485       return true;  } while (0)
5486
5487   if (type == error_mark_node)
5488     return false;
5489
5490   /* If TYPE itself has variable size, it is variably modified.
5491
5492      We do not yet have a representation of the C99 '[*]' syntax.
5493      When a representation is chosen, this function should be modified
5494      to test for that case as well.  */
5495   RETURN_TRUE_IF_VAR (TYPE_SIZE (type));
5496   RETURN_TRUE_IF_VAR (TYPE_SIZE_UNIT(type));
5497
5498   switch (TREE_CODE (type))
5499     {
5500     case POINTER_TYPE:
5501     case REFERENCE_TYPE:
5502     case ARRAY_TYPE:
5503     case VECTOR_TYPE:
5504       if (variably_modified_type_p (TREE_TYPE (type), fn))
5505         return true;
5506       break;
5507
5508     case FUNCTION_TYPE:
5509     case METHOD_TYPE:
5510       /* If TYPE is a function type, it is variably modified if any of the
5511          parameters or the return type are variably modified.  */
5512       if (variably_modified_type_p (TREE_TYPE (type), fn))
5513           return true;
5514
5515       for (t = TYPE_ARG_TYPES (type);
5516            t && t != void_list_node;
5517            t = TREE_CHAIN (t))
5518         if (variably_modified_type_p (TREE_VALUE (t), fn))
5519           return true;
5520       break;
5521
5522     case INTEGER_TYPE:
5523     case REAL_TYPE:
5524     case ENUMERAL_TYPE:
5525     case BOOLEAN_TYPE:
5526     case CHAR_TYPE:
5527       /* Scalar types are variably modified if their end points
5528          aren't constant.  */
5529       RETURN_TRUE_IF_VAR (TYPE_MIN_VALUE (type));
5530       RETURN_TRUE_IF_VAR (TYPE_MAX_VALUE (type));
5531       break;
5532
5533     case RECORD_TYPE:
5534     case UNION_TYPE:
5535     case QUAL_UNION_TYPE:
5536       /* We can't see if any of the field are variably-modified by the
5537          definition we normally use, since that would produce infinite
5538          recursion via pointers.  */
5539       /* This is variably modified if some field's type is.  */
5540       for (t = TYPE_FIELDS (type); t; t = TREE_CHAIN (t))
5541         if (TREE_CODE (t) == FIELD_DECL)
5542           {
5543             RETURN_TRUE_IF_VAR (DECL_FIELD_OFFSET (t));
5544             RETURN_TRUE_IF_VAR (DECL_SIZE (t));
5545             RETURN_TRUE_IF_VAR (DECL_SIZE_UNIT (t));
5546
5547             if (TREE_CODE (type) == QUAL_UNION_TYPE)
5548               RETURN_TRUE_IF_VAR (DECL_QUALIFIER (t));
5549           }
5550         break;
5551
5552     default:
5553       break;
5554     }
5555
5556   /* The current language may have other cases to check, but in general,
5557      all other types are not variably modified.  */
5558   return lang_hooks.tree_inlining.var_mod_type_p (type, fn);
5559
5560 #undef RETURN_TRUE_IF_VAR
5561 }
5562
5563 /* Given a DECL or TYPE, return the scope in which it was declared, or
5564    NULL_TREE if there is no containing scope.  */
5565
5566 tree
5567 get_containing_scope (tree t)
5568 {
5569   return (TYPE_P (t) ? TYPE_CONTEXT (t) : DECL_CONTEXT (t));
5570 }
5571
5572 /* Return the innermost context enclosing DECL that is
5573    a FUNCTION_DECL, or zero if none.  */
5574
5575 tree
5576 decl_function_context (tree decl)
5577 {
5578   tree context;
5579
5580   if (TREE_CODE (decl) == ERROR_MARK)
5581     return 0;
5582
5583   /* C++ virtual functions use DECL_CONTEXT for the class of the vtable
5584      where we look up the function at runtime.  Such functions always take
5585      a first argument of type 'pointer to real context'.
5586
5587      C++ should really be fixed to use DECL_CONTEXT for the real context,
5588      and use something else for the "virtual context".  */
5589   else if (TREE_CODE (decl) == FUNCTION_DECL && DECL_VINDEX (decl))
5590     context
5591       = TYPE_MAIN_VARIANT
5592         (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (decl)))));
5593   else
5594     context = DECL_CONTEXT (decl);
5595
5596   while (context && TREE_CODE (context) != FUNCTION_DECL)
5597     {
5598       if (TREE_CODE (context) == BLOCK)
5599         context = BLOCK_SUPERCONTEXT (context);
5600       else
5601         context = get_containing_scope (context);
5602     }
5603
5604   return context;
5605 }
5606
5607 /* Return the innermost context enclosing DECL that is
5608    a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE, or zero if none.
5609    TYPE_DECLs and FUNCTION_DECLs are transparent to this function.  */
5610
5611 tree
5612 decl_type_context (tree decl)
5613 {
5614   tree context = DECL_CONTEXT (decl);
5615
5616   while (context)
5617     switch (TREE_CODE (context))
5618       {
5619       case NAMESPACE_DECL:
5620       case TRANSLATION_UNIT_DECL:
5621         return NULL_TREE;
5622
5623       case RECORD_TYPE:
5624       case UNION_TYPE:
5625       case QUAL_UNION_TYPE:
5626         return context;
5627
5628       case TYPE_DECL:
5629       case FUNCTION_DECL:
5630         context = DECL_CONTEXT (context);
5631         break;
5632
5633       case BLOCK:
5634         context = BLOCK_SUPERCONTEXT (context);
5635         break;
5636
5637       default:
5638         gcc_unreachable ();
5639       }
5640
5641   return NULL_TREE;
5642 }
5643
5644 /* CALL is a CALL_EXPR.  Return the declaration for the function
5645    called, or NULL_TREE if the called function cannot be
5646    determined.  */
5647
5648 tree
5649 get_callee_fndecl (tree call)
5650 {
5651   tree addr;
5652
5653   /* It's invalid to call this function with anything but a
5654      CALL_EXPR.  */
5655   gcc_assert (TREE_CODE (call) == CALL_EXPR);
5656
5657   /* The first operand to the CALL is the address of the function
5658      called.  */
5659   addr = TREE_OPERAND (call, 0);
5660
5661   STRIP_NOPS (addr);
5662
5663   /* If this is a readonly function pointer, extract its initial value.  */
5664   if (DECL_P (addr) && TREE_CODE (addr) != FUNCTION_DECL
5665       && TREE_READONLY (addr) && ! TREE_THIS_VOLATILE (addr)
5666       && DECL_INITIAL (addr))
5667     addr = DECL_INITIAL (addr);
5668
5669   /* If the address is just `&f' for some function `f', then we know
5670      that `f' is being called.  */
5671   if (TREE_CODE (addr) == ADDR_EXPR
5672       && TREE_CODE (TREE_OPERAND (addr, 0)) == FUNCTION_DECL)
5673     return TREE_OPERAND (addr, 0);
5674
5675   /* We couldn't figure out what was being called.  Maybe the front
5676      end has some idea.  */
5677   return lang_hooks.lang_get_callee_fndecl (call);
5678 }
5679
5680 /* Print debugging information about tree nodes generated during the compile,
5681    and any language-specific information.  */
5682
5683 void
5684 dump_tree_statistics (void)
5685 {
5686 #ifdef GATHER_STATISTICS
5687   int i;
5688   int total_nodes, total_bytes;
5689 #endif
5690
5691   fprintf (stderr, "\n??? tree nodes created\n\n");
5692 #ifdef GATHER_STATISTICS
5693   fprintf (stderr, "Kind                   Nodes      Bytes\n");
5694   fprintf (stderr, "---------------------------------------\n");
5695   total_nodes = total_bytes = 0;
5696   for (i = 0; i < (int) all_kinds; i++)
5697     {
5698       fprintf (stderr, "%-20s %7d %10d\n", tree_node_kind_names[i],
5699                tree_node_counts[i], tree_node_sizes[i]);
5700       total_nodes += tree_node_counts[i];
5701       total_bytes += tree_node_sizes[i];
5702     }
5703   fprintf (stderr, "---------------------------------------\n");
5704   fprintf (stderr, "%-20s %7d %10d\n", "Total", total_nodes, total_bytes);
5705   fprintf (stderr, "---------------------------------------\n");
5706   ssanames_print_statistics ();
5707   phinodes_print_statistics ();
5708 #else
5709   fprintf (stderr, "(No per-node statistics)\n");
5710 #endif
5711   print_type_hash_statistics ();
5712   print_debug_expr_statistics ();
5713   print_value_expr_statistics ();
5714   lang_hooks.print_statistics ();
5715 }
5716 \f
5717 #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
5718
5719 /* Generate a crc32 of a string.  */
5720
5721 unsigned
5722 crc32_string (unsigned chksum, const char *string)
5723 {
5724   do
5725     {
5726       unsigned value = *string << 24;
5727       unsigned ix;
5728
5729       for (ix = 8; ix--; value <<= 1)
5730         {
5731           unsigned feedback;
5732
5733           feedback = (value ^ chksum) & 0x80000000 ? 0x04c11db7 : 0;
5734           chksum <<= 1;
5735           chksum ^= feedback;
5736         }
5737     }
5738   while (*string++);
5739   return chksum;
5740 }
5741
5742 /* P is a string that will be used in a symbol.  Mask out any characters
5743    that are not valid in that context.  */
5744
5745 void
5746 clean_symbol_name (char *p)
5747 {
5748   for (; *p; p++)
5749     if (! (ISALNUM (*p)
5750 #ifndef NO_DOLLAR_IN_LABEL      /* this for `$'; unlikely, but... -- kr */
5751             || *p == '$'
5752 #endif
5753 #ifndef NO_DOT_IN_LABEL         /* this for `.'; unlikely, but...  */
5754             || *p == '.'
5755 #endif
5756            ))
5757       *p = '_';
5758 }
5759
5760 /* Generate a name for a function unique to this translation unit.
5761    TYPE is some string to identify the purpose of this function to the
5762    linker or collect2.  */
5763
5764 tree
5765 get_file_function_name_long (const char *type)
5766 {
5767   char *buf;
5768   const char *p;
5769   char *q;
5770
5771   if (first_global_object_name)
5772     p = first_global_object_name;
5773   else
5774     {
5775       /* We don't have anything that we know to be unique to this translation
5776          unit, so use what we do have and throw in some randomness.  */
5777       unsigned len;
5778       const char *name = weak_global_object_name;
5779       const char *file = main_input_filename;
5780
5781       if (! name)
5782         name = "";
5783       if (! file)
5784         file = input_filename;
5785
5786       len = strlen (file);
5787       q = alloca (9 * 2 + len + 1);
5788       memcpy (q, file, len + 1);
5789       clean_symbol_name (q);
5790
5791       sprintf (q + len, "_%08X_%08X", crc32_string (0, name),
5792                crc32_string (0, flag_random_seed));
5793
5794       p = q;
5795     }
5796
5797   buf = alloca (sizeof (FILE_FUNCTION_FORMAT) + strlen (p) + strlen (type));
5798
5799   /* Set up the name of the file-level functions we may need.
5800      Use a global object (which is already required to be unique over
5801      the program) rather than the file name (which imposes extra
5802      constraints).  */
5803   sprintf (buf, FILE_FUNCTION_FORMAT, type, p);
5804
5805   return get_identifier (buf);
5806 }
5807
5808 /* If KIND=='I', return a suitable global initializer (constructor) name.
5809    If KIND=='D', return a suitable global clean-up (destructor) name.  */
5810
5811 tree
5812 get_file_function_name (int kind)
5813 {
5814   char p[2];
5815
5816   p[0] = kind;
5817   p[1] = 0;
5818
5819   return get_file_function_name_long (p);
5820 }
5821 \f
5822 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
5823
5824 /* Complain that the tree code of NODE does not match the expected 0
5825    terminated list of trailing codes. The trailing code list can be
5826    empty, for a more vague error message.  FILE, LINE, and FUNCTION
5827    are of the caller.  */
5828
5829 void
5830 tree_check_failed (const tree node, const char *file,
5831                    int line, const char *function, ...)
5832 {
5833   va_list args;
5834   char *buffer;
5835   unsigned length = 0;
5836   int code;
5837
5838   va_start (args, function);
5839   while ((code = va_arg (args, int)))
5840     length += 4 + strlen (tree_code_name[code]);
5841   va_end (args);
5842   if (length)
5843     {
5844       va_start (args, function);
5845       length += strlen ("expected ");
5846       buffer = alloca (length);
5847       length = 0;
5848       while ((code = va_arg (args, int)))
5849         {
5850           const char *prefix = length ? " or " : "expected ";
5851
5852           strcpy (buffer + length, prefix);
5853           length += strlen (prefix);
5854           strcpy (buffer + length, tree_code_name[code]);
5855           length += strlen (tree_code_name[code]);
5856         }
5857       va_end (args);
5858     }
5859   else
5860     buffer = (char *)"unexpected node";
5861
5862   internal_error ("tree check: %s, have %s in %s, at %s:%d",
5863                   buffer, tree_code_name[TREE_CODE (node)],
5864                   function, trim_filename (file), line);
5865 }
5866
5867 /* Complain that the tree code of NODE does match the expected 0
5868    terminated list of trailing codes. FILE, LINE, and FUNCTION are of
5869    the caller.  */
5870
5871 void
5872 tree_not_check_failed (const tree node, const char *file,
5873                        int line, const char *function, ...)
5874 {
5875   va_list args;
5876   char *buffer;
5877   unsigned length = 0;
5878   int code;
5879
5880   va_start (args, function);
5881   while ((code = va_arg (args, int)))
5882     length += 4 + strlen (tree_code_name[code]);
5883   va_end (args);
5884   va_start (args, function);
5885   buffer = alloca (length);
5886   length = 0;
5887   while ((code = va_arg (args, int)))
5888     {
5889       if (length)
5890         {
5891           strcpy (buffer + length, " or ");
5892           length += 4;
5893         }
5894       strcpy (buffer + length, tree_code_name[code]);
5895       length += strlen (tree_code_name[code]);
5896     }
5897   va_end (args);
5898
5899   internal_error ("tree check: expected none of %s, have %s in %s, at %s:%d",
5900                   buffer, tree_code_name[TREE_CODE (node)],
5901                   function, trim_filename (file), line);
5902 }
5903
5904 /* Similar to tree_check_failed, except that we check for a class of tree
5905    code, given in CL.  */
5906
5907 void
5908 tree_class_check_failed (const tree node, const enum tree_code_class cl,
5909                          const char *file, int line, const char *function)
5910 {
5911   internal_error
5912     ("tree check: expected class %qs, have %qs (%s) in %s, at %s:%d",
5913      TREE_CODE_CLASS_STRING (cl),
5914      TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))),
5915      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
5916 }
5917 #undef DEFTREESTRUCT
5918 #define DEFTREESTRUCT(VAL, NAME) NAME,
5919
5920 static const char *ts_enum_names[] = {
5921 #include "treestruct.def"
5922 };
5923 #undef DEFTREESTRUCT
5924
5925 #define TS_ENUM_NAME(EN) (ts_enum_names[(EN)])
5926
5927 /* Similar to tree_class_check_failed, except that we check for
5928    whether CODE contains the tree structure identified by EN.  */
5929
5930 void
5931 tree_contains_struct_check_failed (const tree node,
5932                                    const enum tree_node_structure_enum en,
5933                                    const char *file, int line,
5934                                    const char *function)
5935 {
5936   internal_error
5937     ("tree check: expected tree that contains %qs structure, have %qs  in %s, at %s:%d",
5938      TS_ENUM_NAME(en),
5939      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
5940 }
5941
5942
5943 /* Similar to above, except that the check is for the bounds of a TREE_VEC's
5944    (dynamically sized) vector.  */
5945
5946 void
5947 tree_vec_elt_check_failed (int idx, int len, const char *file, int line,
5948                            const char *function)
5949 {
5950   internal_error
5951     ("tree check: accessed elt %d of tree_vec with %d elts in %s, at %s:%d",
5952      idx + 1, len, function, trim_filename (file), line);
5953 }
5954
5955 /* Similar to above, except that the check is for the bounds of a PHI_NODE's
5956    (dynamically sized) vector.  */
5957
5958 void
5959 phi_node_elt_check_failed (int idx, int len, const char *file, int line,
5960                             const char *function)
5961 {
5962   internal_error
5963     ("tree check: accessed elt %d of phi_node with %d elts in %s, at %s:%d",
5964      idx + 1, len, function, trim_filename (file), line);
5965 }
5966
5967 /* Similar to above, except that the check is for the bounds of the operand
5968    vector of an expression node.  */
5969
5970 void
5971 tree_operand_check_failed (int idx, enum tree_code code, const char *file,
5972                            int line, const char *function)
5973 {
5974   internal_error
5975     ("tree check: accessed operand %d of %s with %d operands in %s, at %s:%d",
5976      idx + 1, tree_code_name[code], TREE_CODE_LENGTH (code),
5977      function, trim_filename (file), line);
5978 }
5979 #endif /* ENABLE_TREE_CHECKING */
5980 \f
5981 /* Create a new vector type node holding SUBPARTS units of type INNERTYPE,
5982    and mapped to the machine mode MODE.  Initialize its fields and build
5983    the information necessary for debugging output.  */
5984
5985 static tree
5986 make_vector_type (tree innertype, int nunits, enum machine_mode mode)
5987 {
5988   tree t = make_node (VECTOR_TYPE);
5989
5990   TREE_TYPE (t) = TYPE_MAIN_VARIANT (innertype);
5991   SET_TYPE_VECTOR_SUBPARTS (t, nunits);
5992   TYPE_MODE (t) = mode;
5993   TYPE_READONLY (t) = TYPE_READONLY (innertype);
5994   TYPE_VOLATILE (t) = TYPE_VOLATILE (innertype);
5995
5996   layout_type (t);
5997
5998   {
5999     tree index = build_int_cst (NULL_TREE, nunits - 1);
6000     tree array = build_array_type (innertype, build_index_type (index));
6001     tree rt = make_node (RECORD_TYPE);
6002
6003     TYPE_FIELDS (rt) = build_decl (FIELD_DECL, get_identifier ("f"), array);
6004     DECL_CONTEXT (TYPE_FIELDS (rt)) = rt;
6005     layout_type (rt);
6006     TYPE_DEBUG_REPRESENTATION_TYPE (t) = rt;
6007     /* In dwarfout.c, type lookup uses TYPE_UID numbers.  We want to output
6008        the representation type, and we want to find that die when looking up
6009        the vector type.  This is most easily achieved by making the TYPE_UID
6010        numbers equal.  */
6011     TYPE_UID (rt) = TYPE_UID (t);
6012   }
6013
6014   /* Build our main variant, based on the main variant of the inner type.  */
6015   if (TYPE_MAIN_VARIANT (innertype) != innertype)
6016     {
6017       tree innertype_main_variant = TYPE_MAIN_VARIANT (innertype);
6018       unsigned int hash = TYPE_HASH (innertype_main_variant);
6019       TYPE_MAIN_VARIANT (t)
6020         = type_hash_canon (hash, make_vector_type (innertype_main_variant,
6021                                                    nunits, mode));
6022     }
6023
6024   return t;
6025 }
6026
6027 static tree
6028 make_or_reuse_type (unsigned size, int unsignedp)
6029 {
6030   if (size == INT_TYPE_SIZE)
6031     return unsignedp ? unsigned_type_node : integer_type_node;
6032   if (size == CHAR_TYPE_SIZE)
6033     return unsignedp ? unsigned_char_type_node : signed_char_type_node;
6034   if (size == SHORT_TYPE_SIZE)
6035     return unsignedp ? short_unsigned_type_node : short_integer_type_node;
6036   if (size == LONG_TYPE_SIZE)
6037     return unsignedp ? long_unsigned_type_node : long_integer_type_node;
6038   if (size == LONG_LONG_TYPE_SIZE)
6039     return (unsignedp ? long_long_unsigned_type_node
6040             : long_long_integer_type_node);
6041
6042   if (unsignedp)
6043     return make_unsigned_type (size);
6044   else
6045     return make_signed_type (size);
6046 }
6047
6048 /* Create nodes for all integer types (and error_mark_node) using the sizes
6049    of C datatypes.  The caller should call set_sizetype soon after calling
6050    this function to select one of the types as sizetype.  */
6051
6052 void
6053 build_common_tree_nodes (bool signed_char, bool signed_sizetype)
6054 {
6055   error_mark_node = make_node (ERROR_MARK);
6056   TREE_TYPE (error_mark_node) = error_mark_node;
6057
6058   initialize_sizetypes (signed_sizetype);
6059
6060   /* Define both `signed char' and `unsigned char'.  */
6061   signed_char_type_node = make_signed_type (CHAR_TYPE_SIZE);
6062   unsigned_char_type_node = make_unsigned_type (CHAR_TYPE_SIZE);
6063
6064   /* Define `char', which is like either `signed char' or `unsigned char'
6065      but not the same as either.  */
6066   char_type_node
6067     = (signed_char
6068        ? make_signed_type (CHAR_TYPE_SIZE)
6069        : make_unsigned_type (CHAR_TYPE_SIZE));
6070
6071   short_integer_type_node = make_signed_type (SHORT_TYPE_SIZE);
6072   short_unsigned_type_node = make_unsigned_type (SHORT_TYPE_SIZE);
6073   integer_type_node = make_signed_type (INT_TYPE_SIZE);
6074   unsigned_type_node = make_unsigned_type (INT_TYPE_SIZE);
6075   long_integer_type_node = make_signed_type (LONG_TYPE_SIZE);
6076   long_unsigned_type_node = make_unsigned_type (LONG_TYPE_SIZE);
6077   long_long_integer_type_node = make_signed_type (LONG_LONG_TYPE_SIZE);
6078   long_long_unsigned_type_node = make_unsigned_type (LONG_LONG_TYPE_SIZE);
6079
6080   /* Define a boolean type.  This type only represents boolean values but
6081      may be larger than char depending on the value of BOOL_TYPE_SIZE.
6082      Front ends which want to override this size (i.e. Java) can redefine
6083      boolean_type_node before calling build_common_tree_nodes_2.  */
6084   boolean_type_node = make_unsigned_type (BOOL_TYPE_SIZE);
6085   TREE_SET_CODE (boolean_type_node, BOOLEAN_TYPE);
6086   TYPE_MAX_VALUE (boolean_type_node) = build_int_cst (boolean_type_node, 1);
6087   TYPE_PRECISION (boolean_type_node) = 1;
6088
6089   /* Fill in the rest of the sized types.  Reuse existing type nodes
6090      when possible.  */
6091   intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 0);
6092   intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 0);
6093   intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 0);
6094   intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 0);
6095   intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 0);
6096
6097   unsigned_intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 1);
6098   unsigned_intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 1);
6099   unsigned_intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 1);
6100   unsigned_intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 1);
6101   unsigned_intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 1);
6102
6103   access_public_node = get_identifier ("public");
6104   access_protected_node = get_identifier ("protected");
6105   access_private_node = get_identifier ("private");
6106 }
6107
6108 /* Call this function after calling build_common_tree_nodes and set_sizetype.
6109    It will create several other common tree nodes.  */
6110
6111 void
6112 build_common_tree_nodes_2 (int short_double)
6113 {
6114   /* Define these next since types below may used them.  */
6115   integer_zero_node = build_int_cst (NULL_TREE, 0);
6116   integer_one_node = build_int_cst (NULL_TREE, 1);
6117   integer_minus_one_node = build_int_cst (NULL_TREE, -1);
6118
6119   size_zero_node = size_int (0);
6120   size_one_node = size_int (1);
6121   bitsize_zero_node = bitsize_int (0);
6122   bitsize_one_node = bitsize_int (1);
6123   bitsize_unit_node = bitsize_int (BITS_PER_UNIT);
6124
6125   boolean_false_node = TYPE_MIN_VALUE (boolean_type_node);
6126   boolean_true_node = TYPE_MAX_VALUE (boolean_type_node);
6127
6128   void_type_node = make_node (VOID_TYPE);
6129   layout_type (void_type_node);
6130
6131   /* We are not going to have real types in C with less than byte alignment,
6132      so we might as well not have any types that claim to have it.  */
6133   TYPE_ALIGN (void_type_node) = BITS_PER_UNIT;
6134   TYPE_USER_ALIGN (void_type_node) = 0;
6135
6136   null_pointer_node = build_int_cst (build_pointer_type (void_type_node), 0);
6137   layout_type (TREE_TYPE (null_pointer_node));
6138
6139   ptr_type_node = build_pointer_type (void_type_node);
6140   const_ptr_type_node
6141     = build_pointer_type (build_type_variant (void_type_node, 1, 0));
6142   fileptr_type_node = ptr_type_node;
6143
6144   float_type_node = make_node (REAL_TYPE);
6145   TYPE_PRECISION (float_type_node) = FLOAT_TYPE_SIZE;
6146   layout_type (float_type_node);
6147
6148   double_type_node = make_node (REAL_TYPE);
6149   if (short_double)
6150     TYPE_PRECISION (double_type_node) = FLOAT_TYPE_SIZE;
6151   else
6152     TYPE_PRECISION (double_type_node) = DOUBLE_TYPE_SIZE;
6153   layout_type (double_type_node);
6154
6155   long_double_type_node = make_node (REAL_TYPE);
6156   TYPE_PRECISION (long_double_type_node) = LONG_DOUBLE_TYPE_SIZE;
6157   layout_type (long_double_type_node);
6158
6159   float_ptr_type_node = build_pointer_type (float_type_node);
6160   double_ptr_type_node = build_pointer_type (double_type_node);
6161   long_double_ptr_type_node = build_pointer_type (long_double_type_node);
6162   integer_ptr_type_node = build_pointer_type (integer_type_node);
6163
6164   complex_integer_type_node = make_node (COMPLEX_TYPE);
6165   TREE_TYPE (complex_integer_type_node) = integer_type_node;
6166   layout_type (complex_integer_type_node);
6167
6168   complex_float_type_node = make_node (COMPLEX_TYPE);
6169   TREE_TYPE (complex_float_type_node) = float_type_node;
6170   layout_type (complex_float_type_node);
6171
6172   complex_double_type_node = make_node (COMPLEX_TYPE);
6173   TREE_TYPE (complex_double_type_node) = double_type_node;
6174   layout_type (complex_double_type_node);
6175
6176   complex_long_double_type_node = make_node (COMPLEX_TYPE);
6177   TREE_TYPE (complex_long_double_type_node) = long_double_type_node;
6178   layout_type (complex_long_double_type_node);
6179
6180   {
6181     tree t = targetm.build_builtin_va_list ();
6182
6183     /* Many back-ends define record types without setting TYPE_NAME.
6184        If we copied the record type here, we'd keep the original
6185        record type without a name.  This breaks name mangling.  So,
6186        don't copy record types and let c_common_nodes_and_builtins()
6187        declare the type to be __builtin_va_list.  */
6188     if (TREE_CODE (t) != RECORD_TYPE)
6189       t = build_variant_type_copy (t);
6190
6191     va_list_type_node = t;
6192   }
6193 }
6194
6195 /* A subroutine of build_common_builtin_nodes.  Define a builtin function.  */
6196
6197 static void
6198 local_define_builtin (const char *name, tree type, enum built_in_function code,
6199                       const char *library_name, int ecf_flags)
6200 {
6201   tree decl;
6202
6203   decl = lang_hooks.builtin_function (name, type, code, BUILT_IN_NORMAL,
6204                                       library_name, NULL_TREE);
6205   if (ecf_flags & ECF_CONST)
6206     TREE_READONLY (decl) = 1;
6207   if (ecf_flags & ECF_PURE)
6208     DECL_IS_PURE (decl) = 1;
6209   if (ecf_flags & ECF_NORETURN)
6210     TREE_THIS_VOLATILE (decl) = 1;
6211   if (ecf_flags & ECF_NOTHROW)
6212     TREE_NOTHROW (decl) = 1;
6213   if (ecf_flags & ECF_MALLOC)
6214     DECL_IS_MALLOC (decl) = 1;
6215
6216   built_in_decls[code] = decl;
6217   implicit_built_in_decls[code] = decl;
6218 }
6219
6220 /* Call this function after instantiating all builtins that the language
6221    front end cares about.  This will build the rest of the builtins that
6222    are relied upon by the tree optimizers and the middle-end.  */
6223
6224 void
6225 build_common_builtin_nodes (void)
6226 {
6227   tree tmp, ftype;
6228
6229   if (built_in_decls[BUILT_IN_MEMCPY] == NULL
6230       || built_in_decls[BUILT_IN_MEMMOVE] == NULL)
6231     {
6232       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6233       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6234       tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6235       ftype = build_function_type (ptr_type_node, tmp);
6236
6237       if (built_in_decls[BUILT_IN_MEMCPY] == NULL)
6238         local_define_builtin ("__builtin_memcpy", ftype, BUILT_IN_MEMCPY,
6239                               "memcpy", ECF_NOTHROW);
6240       if (built_in_decls[BUILT_IN_MEMMOVE] == NULL)
6241         local_define_builtin ("__builtin_memmove", ftype, BUILT_IN_MEMMOVE,
6242                               "memmove", ECF_NOTHROW);
6243     }
6244
6245   if (built_in_decls[BUILT_IN_MEMCMP] == NULL)
6246     {
6247       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6248       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6249       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6250       ftype = build_function_type (integer_type_node, tmp);
6251       local_define_builtin ("__builtin_memcmp", ftype, BUILT_IN_MEMCMP,
6252                             "memcmp", ECF_PURE | ECF_NOTHROW);
6253     }
6254
6255   if (built_in_decls[BUILT_IN_MEMSET] == NULL)
6256     {
6257       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6258       tmp = tree_cons (NULL_TREE, integer_type_node, tmp);
6259       tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6260       ftype = build_function_type (ptr_type_node, tmp);
6261       local_define_builtin ("__builtin_memset", ftype, BUILT_IN_MEMSET,
6262                             "memset", ECF_NOTHROW);
6263     }
6264
6265   if (built_in_decls[BUILT_IN_ALLOCA] == NULL)
6266     {
6267       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6268       ftype = build_function_type (ptr_type_node, tmp);
6269       local_define_builtin ("__builtin_alloca", ftype, BUILT_IN_ALLOCA,
6270                             "alloca", ECF_NOTHROW | ECF_MALLOC);
6271     }
6272
6273   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6274   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6275   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6276   ftype = build_function_type (void_type_node, tmp);
6277   local_define_builtin ("__builtin_init_trampoline", ftype,
6278                         BUILT_IN_INIT_TRAMPOLINE,
6279                         "__builtin_init_trampoline", ECF_NOTHROW);
6280
6281   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6282   ftype = build_function_type (ptr_type_node, tmp);
6283   local_define_builtin ("__builtin_adjust_trampoline", ftype,
6284                         BUILT_IN_ADJUST_TRAMPOLINE,
6285                         "__builtin_adjust_trampoline",
6286                         ECF_CONST | ECF_NOTHROW);
6287
6288   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6289   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6290   ftype = build_function_type (void_type_node, tmp);
6291   local_define_builtin ("__builtin_nonlocal_goto", ftype,
6292                         BUILT_IN_NONLOCAL_GOTO,
6293                         "__builtin_nonlocal_goto",
6294                         ECF_NORETURN | ECF_NOTHROW);
6295
6296   ftype = build_function_type (ptr_type_node, void_list_node);
6297   local_define_builtin ("__builtin_stack_save", ftype, BUILT_IN_STACK_SAVE,
6298                         "__builtin_stack_save", ECF_NOTHROW);
6299
6300   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6301   ftype = build_function_type (void_type_node, tmp);
6302   local_define_builtin ("__builtin_stack_restore", ftype,
6303                         BUILT_IN_STACK_RESTORE,
6304                         "__builtin_stack_restore", ECF_NOTHROW);
6305
6306   ftype = build_function_type (void_type_node, void_list_node);
6307   local_define_builtin ("__builtin_profile_func_enter", ftype,
6308                         BUILT_IN_PROFILE_FUNC_ENTER, "profile_func_enter", 0);
6309   local_define_builtin ("__builtin_profile_func_exit", ftype,
6310                         BUILT_IN_PROFILE_FUNC_EXIT, "profile_func_exit", 0);
6311
6312   /* Complex multiplication and division.  These are handled as builtins
6313      rather than optabs because emit_library_call_value doesn't support
6314      complex.  Further, we can do slightly better with folding these
6315      beasties if the real and complex parts of the arguments are separate.  */
6316   {
6317     enum machine_mode mode;
6318
6319     for (mode = MIN_MODE_COMPLEX_FLOAT; mode <= MAX_MODE_COMPLEX_FLOAT; ++mode)
6320       {
6321         char mode_name_buf[4], *q;
6322         const char *p;
6323         enum built_in_function mcode, dcode;
6324         tree type, inner_type;
6325
6326         type = lang_hooks.types.type_for_mode (mode, 0);
6327         if (type == NULL)
6328           continue;
6329         inner_type = TREE_TYPE (type);
6330
6331         tmp = tree_cons (NULL_TREE, inner_type, void_list_node);
6332         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6333         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6334         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6335         ftype = build_function_type (type, tmp);
6336
6337         mcode = BUILT_IN_COMPLEX_MUL_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
6338         dcode = BUILT_IN_COMPLEX_DIV_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
6339
6340         for (p = GET_MODE_NAME (mode), q = mode_name_buf; *p; p++, q++)
6341           *q = TOLOWER (*p);
6342         *q = '\0';
6343
6344         built_in_names[mcode] = concat ("__mul", mode_name_buf, "3", NULL);
6345         local_define_builtin (built_in_names[mcode], ftype, mcode,
6346                               built_in_names[mcode], ECF_CONST | ECF_NOTHROW);
6347
6348         built_in_names[dcode] = concat ("__div", mode_name_buf, "3", NULL);
6349         local_define_builtin (built_in_names[dcode], ftype, dcode,
6350                               built_in_names[dcode], ECF_CONST | ECF_NOTHROW);
6351       }
6352   }
6353 }
6354
6355 /* HACK.  GROSS.  This is absolutely disgusting.  I wish there was a
6356    better way.
6357
6358    If we requested a pointer to a vector, build up the pointers that
6359    we stripped off while looking for the inner type.  Similarly for
6360    return values from functions.
6361
6362    The argument TYPE is the top of the chain, and BOTTOM is the
6363    new type which we will point to.  */
6364
6365 tree
6366 reconstruct_complex_type (tree type, tree bottom)
6367 {
6368   tree inner, outer;
6369
6370   if (POINTER_TYPE_P (type))
6371     {
6372       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6373       outer = build_pointer_type (inner);
6374     }
6375   else if (TREE_CODE (type) == ARRAY_TYPE)
6376     {
6377       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6378       outer = build_array_type (inner, TYPE_DOMAIN (type));
6379     }
6380   else if (TREE_CODE (type) == FUNCTION_TYPE)
6381     {
6382       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6383       outer = build_function_type (inner, TYPE_ARG_TYPES (type));
6384     }
6385   else if (TREE_CODE (type) == METHOD_TYPE)
6386     {
6387       tree argtypes;
6388       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6389       /* The build_method_type_directly() routine prepends 'this' to argument list,
6390          so we must compensate by getting rid of it.  */
6391       argtypes = TYPE_ARG_TYPES (type);
6392       outer = build_method_type_directly (TYPE_METHOD_BASETYPE (type),
6393                                           inner,
6394                                           TYPE_ARG_TYPES (type));
6395       TYPE_ARG_TYPES (outer) = argtypes;
6396     }
6397   else
6398     return bottom;
6399
6400   TYPE_READONLY (outer) = TYPE_READONLY (type);
6401   TYPE_VOLATILE (outer) = TYPE_VOLATILE (type);
6402
6403   return outer;
6404 }
6405
6406 /* Returns a vector tree node given a mode (integer, vector, or BLKmode) and
6407    the inner type.  */
6408 tree
6409 build_vector_type_for_mode (tree innertype, enum machine_mode mode)
6410 {
6411   int nunits;
6412
6413   switch (GET_MODE_CLASS (mode))
6414     {
6415     case MODE_VECTOR_INT:
6416     case MODE_VECTOR_FLOAT:
6417       nunits = GET_MODE_NUNITS (mode);
6418       break;
6419
6420     case MODE_INT:
6421       /* Check that there are no leftover bits.  */
6422       gcc_assert (GET_MODE_BITSIZE (mode)
6423                   % TREE_INT_CST_LOW (TYPE_SIZE (innertype)) == 0);
6424
6425       nunits = GET_MODE_BITSIZE (mode)
6426                / TREE_INT_CST_LOW (TYPE_SIZE (innertype));
6427       break;
6428
6429     default:
6430       gcc_unreachable ();
6431     }
6432
6433   return make_vector_type (innertype, nunits, mode);
6434 }
6435
6436 /* Similarly, but takes the inner type and number of units, which must be
6437    a power of two.  */
6438
6439 tree
6440 build_vector_type (tree innertype, int nunits)
6441 {
6442   return make_vector_type (innertype, nunits, VOIDmode);
6443 }
6444
6445 /* Build RESX_EXPR with given REGION_NUMBER.  */
6446 tree
6447 build_resx (int region_number)
6448 {
6449   tree t;
6450   t = build1 (RESX_EXPR, void_type_node,
6451               build_int_cst (NULL_TREE, region_number));
6452   return t;
6453 }
6454
6455 /* Given an initializer INIT, return TRUE if INIT is zero or some
6456    aggregate of zeros.  Otherwise return FALSE.  */
6457 bool
6458 initializer_zerop (tree init)
6459 {
6460   tree elt;
6461
6462   STRIP_NOPS (init);
6463
6464   switch (TREE_CODE (init))
6465     {
6466     case INTEGER_CST:
6467       return integer_zerop (init);
6468
6469     case REAL_CST:
6470       /* ??? Note that this is not correct for C4X float formats.  There,
6471          a bit pattern of all zeros is 1.0; 0.0 is encoded with the most
6472          negative exponent.  */
6473       return real_zerop (init)
6474         && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init));
6475
6476     case COMPLEX_CST:
6477       return integer_zerop (init)
6478         || (real_zerop (init)
6479             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init)))
6480             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init))));
6481
6482     case VECTOR_CST:
6483       for (elt = TREE_VECTOR_CST_ELTS (init); elt; elt = TREE_CHAIN (elt))
6484         if (!initializer_zerop (TREE_VALUE (elt)))
6485           return false;
6486       return true;
6487
6488     case CONSTRUCTOR:
6489       {
6490         unsigned HOST_WIDE_INT idx;
6491
6492         FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (init), idx, elt)
6493           if (!initializer_zerop (elt))
6494             return false;
6495         return true;
6496       }
6497
6498     default:
6499       return false;
6500     }
6501 }
6502
6503 void
6504 add_var_to_bind_expr (tree bind_expr, tree var)
6505 {
6506   BIND_EXPR_VARS (bind_expr)
6507     = chainon (BIND_EXPR_VARS (bind_expr), var);
6508   if (BIND_EXPR_BLOCK (bind_expr))
6509     BLOCK_VARS (BIND_EXPR_BLOCK (bind_expr))
6510       = BIND_EXPR_VARS (bind_expr);
6511 }
6512
6513 /* Build an empty statement.  */
6514
6515 tree
6516 build_empty_stmt (void)
6517 {
6518   return build1 (NOP_EXPR, void_type_node, size_zero_node);
6519 }
6520
6521
6522 /* Returns true if it is possible to prove that the index of
6523    an array access REF (an ARRAY_REF expression) falls into the
6524    array bounds.  */
6525
6526 bool
6527 in_array_bounds_p (tree ref)
6528 {
6529   tree idx = TREE_OPERAND (ref, 1);
6530   tree min, max;
6531
6532   if (TREE_CODE (idx) != INTEGER_CST)
6533     return false;
6534
6535   min = array_ref_low_bound (ref);
6536   max = array_ref_up_bound (ref);
6537   if (!min
6538       || !max
6539       || TREE_CODE (min) != INTEGER_CST
6540       || TREE_CODE (max) != INTEGER_CST)
6541     return false;
6542
6543   if (tree_int_cst_lt (idx, min)
6544       || tree_int_cst_lt (max, idx))
6545     return false;
6546
6547   return true;
6548 }
6549
6550 /* Return true if T (assumed to be a DECL) is a global variable.  */
6551
6552 bool
6553 is_global_var (tree t)
6554 {
6555   return (TREE_STATIC (t) || DECL_EXTERNAL (t));
6556 }
6557
6558 /* Return true if T (assumed to be a DECL) must be assigned a memory
6559    location.  */
6560
6561 bool
6562 needs_to_live_in_memory (tree t)
6563 {
6564   return (TREE_ADDRESSABLE (t)
6565           || is_global_var (t)
6566           || (TREE_CODE (t) == RESULT_DECL
6567               && aggregate_value_p (t, current_function_decl)));
6568 }
6569
6570 /* There are situations in which a language considers record types
6571    compatible which have different field lists.  Decide if two fields
6572    are compatible.  It is assumed that the parent records are compatible.  */
6573
6574 bool
6575 fields_compatible_p (tree f1, tree f2)
6576 {
6577   if (!operand_equal_p (DECL_FIELD_BIT_OFFSET (f1),
6578                         DECL_FIELD_BIT_OFFSET (f2), OEP_ONLY_CONST))
6579     return false;
6580
6581   if (!operand_equal_p (DECL_FIELD_OFFSET (f1),
6582                         DECL_FIELD_OFFSET (f2), OEP_ONLY_CONST))
6583     return false;
6584
6585   if (!lang_hooks.types_compatible_p (TREE_TYPE (f1), TREE_TYPE (f2)))
6586     return false;
6587
6588   return true;
6589 }
6590
6591 /* Locate within RECORD a field that is compatible with ORIG_FIELD.  */
6592
6593 tree
6594 find_compatible_field (tree record, tree orig_field)
6595 {
6596   tree f;
6597
6598   for (f = TYPE_FIELDS (record); f ; f = TREE_CHAIN (f))
6599     if (TREE_CODE (f) == FIELD_DECL
6600         && fields_compatible_p (f, orig_field))
6601       return f;
6602
6603   /* ??? Why isn't this on the main fields list?  */
6604   f = TYPE_VFIELD (record);
6605   if (f && TREE_CODE (f) == FIELD_DECL
6606       && fields_compatible_p (f, orig_field))
6607     return f;
6608
6609   /* ??? We should abort here, but Java appears to do Bad Things
6610      with inherited fields.  */
6611   return orig_field;
6612 }
6613
6614 /* Return value of a constant X.  */
6615
6616 HOST_WIDE_INT
6617 int_cst_value (tree x)
6618 {
6619   unsigned bits = TYPE_PRECISION (TREE_TYPE (x));
6620   unsigned HOST_WIDE_INT val = TREE_INT_CST_LOW (x);
6621   bool negative = ((val >> (bits - 1)) & 1) != 0;
6622
6623   gcc_assert (bits <= HOST_BITS_PER_WIDE_INT);
6624
6625   if (negative)
6626     val |= (~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1;
6627   else
6628     val &= ~((~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1);
6629
6630   return val;
6631 }
6632
6633 /* Returns the greatest common divisor of A and B, which must be
6634    INTEGER_CSTs.  */
6635
6636 tree
6637 tree_fold_gcd (tree a, tree b)
6638 {
6639   tree a_mod_b;
6640   tree type = TREE_TYPE (a);
6641
6642   gcc_assert (TREE_CODE (a) == INTEGER_CST);
6643   gcc_assert (TREE_CODE (b) == INTEGER_CST);
6644
6645   if (integer_zerop (a))
6646     return b;
6647
6648   if (integer_zerop (b))
6649     return a;
6650
6651   if (tree_int_cst_sgn (a) == -1)
6652     a = fold_build2 (MULT_EXPR, type, a,
6653                      convert (type, integer_minus_one_node));
6654
6655   if (tree_int_cst_sgn (b) == -1)
6656     b = fold_build2 (MULT_EXPR, type, b,
6657                      convert (type, integer_minus_one_node));
6658
6659   while (1)
6660     {
6661       a_mod_b = fold_build2 (FLOOR_MOD_EXPR, type, a, b);
6662
6663       if (!TREE_INT_CST_LOW (a_mod_b)
6664           && !TREE_INT_CST_HIGH (a_mod_b))
6665         return b;
6666
6667       a = b;
6668       b = a_mod_b;
6669     }
6670 }
6671
6672 /* Returns unsigned variant of TYPE.  */
6673
6674 tree
6675 unsigned_type_for (tree type)
6676 {
6677   return lang_hooks.types.unsigned_type (type);
6678 }
6679
6680 /* Returns signed variant of TYPE.  */
6681
6682 tree
6683 signed_type_for (tree type)
6684 {
6685   return lang_hooks.types.signed_type (type);
6686 }
6687
6688 /* Returns the largest value obtainable by casting something in INNER type to
6689    OUTER type.  */
6690
6691 tree
6692 upper_bound_in_type (tree outer, tree inner)
6693 {
6694   unsigned HOST_WIDE_INT lo, hi;
6695   unsigned int det = 0;
6696   unsigned oprec = TYPE_PRECISION (outer);
6697   unsigned iprec = TYPE_PRECISION (inner);
6698   unsigned prec;
6699
6700   /* Compute a unique number for every combination.  */
6701   det |= (oprec > iprec) ? 4 : 0;
6702   det |= TYPE_UNSIGNED (outer) ? 2 : 0;
6703   det |= TYPE_UNSIGNED (inner) ? 1 : 0;
6704
6705   /* Determine the exponent to use.  */
6706   switch (det)
6707     {
6708     case 0:
6709     case 1:
6710       /* oprec <= iprec, outer: signed, inner: don't care.  */
6711       prec = oprec - 1;
6712       break;
6713     case 2:
6714     case 3:
6715       /* oprec <= iprec, outer: unsigned, inner: don't care.  */
6716       prec = oprec;
6717       break;
6718     case 4:
6719       /* oprec > iprec, outer: signed, inner: signed.  */
6720       prec = iprec - 1;
6721       break;
6722     case 5:
6723       /* oprec > iprec, outer: signed, inner: unsigned.  */
6724       prec = iprec;
6725       break;
6726     case 6:
6727       /* oprec > iprec, outer: unsigned, inner: signed.  */
6728       prec = oprec;
6729       break;
6730     case 7:
6731       /* oprec > iprec, outer: unsigned, inner: unsigned.  */
6732       prec = iprec;
6733       break;
6734     default:
6735       gcc_unreachable ();
6736     }
6737
6738   /* Compute 2^^prec - 1.  */
6739   if (prec <= HOST_BITS_PER_WIDE_INT)
6740     {
6741       hi = 0;
6742       lo = ((~(unsigned HOST_WIDE_INT) 0)
6743             >> (HOST_BITS_PER_WIDE_INT - prec));
6744     }
6745   else
6746     {
6747       hi = ((~(unsigned HOST_WIDE_INT) 0)
6748             >> (2 * HOST_BITS_PER_WIDE_INT - prec));
6749       lo = ~(unsigned HOST_WIDE_INT) 0;
6750     }
6751
6752   return build_int_cst_wide (outer, lo, hi);
6753 }
6754
6755 /* Returns the smallest value obtainable by casting something in INNER type to
6756    OUTER type.  */
6757
6758 tree
6759 lower_bound_in_type (tree outer, tree inner)
6760 {
6761   unsigned HOST_WIDE_INT lo, hi;
6762   unsigned oprec = TYPE_PRECISION (outer);
6763   unsigned iprec = TYPE_PRECISION (inner);
6764
6765   /* If OUTER type is unsigned, we can definitely cast 0 to OUTER type
6766      and obtain 0.  */
6767   if (TYPE_UNSIGNED (outer)
6768       /* If we are widening something of an unsigned type, OUTER type
6769          contains all values of INNER type.  In particular, both INNER
6770          and OUTER types have zero in common.  */
6771       || (oprec > iprec && TYPE_UNSIGNED (inner)))
6772     lo = hi = 0;
6773   else
6774     {
6775       /* If we are widening a signed type to another signed type, we
6776          want to obtain -2^^(iprec-1).  If we are keeping the
6777          precision or narrowing to a signed type, we want to obtain
6778          -2^(oprec-1).  */
6779       unsigned prec = oprec > iprec ? iprec : oprec;
6780
6781       if (prec <= HOST_BITS_PER_WIDE_INT)
6782         {
6783           hi = ~(unsigned HOST_WIDE_INT) 0;
6784           lo = (~(unsigned HOST_WIDE_INT) 0) << (prec - 1);
6785         }
6786       else
6787         {
6788           hi = ((~(unsigned HOST_WIDE_INT) 0)
6789                 << (prec - HOST_BITS_PER_WIDE_INT - 1));
6790           lo = 0;
6791         }
6792     }
6793
6794   return build_int_cst_wide (outer, lo, hi);
6795 }
6796
6797 /* Return nonzero if two operands that are suitable for PHI nodes are
6798    necessarily equal.  Specifically, both ARG0 and ARG1 must be either
6799    SSA_NAME or invariant.  Note that this is strictly an optimization.
6800    That is, callers of this function can directly call operand_equal_p
6801    and get the same result, only slower.  */
6802
6803 int
6804 operand_equal_for_phi_arg_p (tree arg0, tree arg1)
6805 {
6806   if (arg0 == arg1)
6807     return 1;
6808   if (TREE_CODE (arg0) == SSA_NAME || TREE_CODE (arg1) == SSA_NAME)
6809     return 0;
6810   return operand_equal_p (arg0, arg1, 0);
6811 }
6812
6813 /* Returns number of zeros at the end of binary representation of X.
6814
6815    ??? Use ffs if available?  */
6816
6817 tree
6818 num_ending_zeros (tree x)
6819 {
6820   unsigned HOST_WIDE_INT fr, nfr;
6821   unsigned num, abits;
6822   tree type = TREE_TYPE (x);
6823
6824   if (TREE_INT_CST_LOW (x) == 0)
6825     {
6826       num = HOST_BITS_PER_WIDE_INT;
6827       fr = TREE_INT_CST_HIGH (x);
6828     }
6829   else
6830     {
6831       num = 0;
6832       fr = TREE_INT_CST_LOW (x);
6833     }
6834
6835   for (abits = HOST_BITS_PER_WIDE_INT / 2; abits; abits /= 2)
6836     {
6837       nfr = fr >> abits;
6838       if (nfr << abits == fr)
6839         {
6840           num += abits;
6841           fr = nfr;
6842         }
6843     }
6844
6845   if (num > TYPE_PRECISION (type))
6846     num = TYPE_PRECISION (type);
6847
6848   return build_int_cst_type (type, num);
6849 }
6850
6851
6852 #define WALK_SUBTREE(NODE)                              \
6853   do                                                    \
6854     {                                                   \
6855       result = walk_tree (&(NODE), func, data, pset);   \
6856       if (result)                                       \
6857         return result;                                  \
6858     }                                                   \
6859   while (0)
6860
6861 /* This is a subroutine of walk_tree that walks field of TYPE that are to
6862    be walked whenever a type is seen in the tree.  Rest of operands and return
6863    value are as for walk_tree.  */
6864
6865 static tree
6866 walk_type_fields (tree type, walk_tree_fn func, void *data,
6867                   struct pointer_set_t *pset)
6868 {
6869   tree result = NULL_TREE;
6870
6871   switch (TREE_CODE (type))
6872     {
6873     case POINTER_TYPE:
6874     case REFERENCE_TYPE:
6875       /* We have to worry about mutually recursive pointers.  These can't
6876          be written in C.  They can in Ada.  It's pathological, but
6877          there's an ACATS test (c38102a) that checks it.  Deal with this
6878          by checking if we're pointing to another pointer, that one
6879          points to another pointer, that one does too, and we have no htab.
6880          If so, get a hash table.  We check three levels deep to avoid
6881          the cost of the hash table if we don't need one.  */
6882       if (POINTER_TYPE_P (TREE_TYPE (type))
6883           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type)))
6884           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type))))
6885           && !pset)
6886         {
6887           result = walk_tree_without_duplicates (&TREE_TYPE (type),
6888                                                  func, data);
6889           if (result)
6890             return result;
6891
6892           break;
6893         }
6894
6895       /* ... fall through ... */
6896
6897     case COMPLEX_TYPE:
6898       WALK_SUBTREE (TREE_TYPE (type));
6899       break;
6900
6901     case METHOD_TYPE:
6902       WALK_SUBTREE (TYPE_METHOD_BASETYPE (type));
6903
6904       /* Fall through.  */
6905
6906     case FUNCTION_TYPE:
6907       WALK_SUBTREE (TREE_TYPE (type));
6908       {
6909         tree arg;
6910
6911         /* We never want to walk into default arguments.  */
6912         for (arg = TYPE_ARG_TYPES (type); arg; arg = TREE_CHAIN (arg))
6913           WALK_SUBTREE (TREE_VALUE (arg));
6914       }
6915       break;
6916
6917     case ARRAY_TYPE:
6918       /* Don't follow this nodes's type if a pointer for fear that we'll
6919          have infinite recursion.  Those types are uninteresting anyway.  */
6920       if (!POINTER_TYPE_P (TREE_TYPE (type))
6921           && TREE_CODE (TREE_TYPE (type)) != OFFSET_TYPE)
6922         WALK_SUBTREE (TREE_TYPE (type));
6923       WALK_SUBTREE (TYPE_DOMAIN (type));
6924       break;
6925
6926     case BOOLEAN_TYPE:
6927     case ENUMERAL_TYPE:
6928     case INTEGER_TYPE:
6929     case CHAR_TYPE:
6930     case REAL_TYPE:
6931       WALK_SUBTREE (TYPE_MIN_VALUE (type));
6932       WALK_SUBTREE (TYPE_MAX_VALUE (type));
6933       break;
6934
6935     case OFFSET_TYPE:
6936       WALK_SUBTREE (TREE_TYPE (type));
6937       WALK_SUBTREE (TYPE_OFFSET_BASETYPE (type));
6938       break;
6939
6940     default:
6941       break;
6942     }
6943
6944   return NULL_TREE;
6945 }
6946
6947 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.  FUNC is
6948    called with the DATA and the address of each sub-tree.  If FUNC returns a
6949    non-NULL value, the traversal is stopped, and the value returned by FUNC
6950    is returned.  If PSET is non-NULL it is used to record the nodes visited,
6951    and to avoid visiting a node more than once.  */
6952
6953 tree
6954 walk_tree (tree *tp, walk_tree_fn func, void *data, struct pointer_set_t *pset)
6955 {
6956   enum tree_code code;
6957   int walk_subtrees;
6958   tree result;
6959
6960 #define WALK_SUBTREE_TAIL(NODE)                         \
6961   do                                                    \
6962     {                                                   \
6963        tp = & (NODE);                                   \
6964        goto tail_recurse;                               \
6965     }                                                   \
6966   while (0)
6967
6968  tail_recurse:
6969   /* Skip empty subtrees.  */
6970   if (!*tp)
6971     return NULL_TREE;
6972
6973   /* Don't walk the same tree twice, if the user has requested
6974      that we avoid doing so.  */
6975   if (pset && pointer_set_insert (pset, *tp))
6976     return NULL_TREE;
6977
6978   /* Call the function.  */
6979   walk_subtrees = 1;
6980   result = (*func) (tp, &walk_subtrees, data);
6981
6982   /* If we found something, return it.  */
6983   if (result)
6984     return result;
6985
6986   code = TREE_CODE (*tp);
6987
6988   /* Even if we didn't, FUNC may have decided that there was nothing
6989      interesting below this point in the tree.  */
6990   if (!walk_subtrees)
6991     {
6992       if (code == TREE_LIST)
6993         /* But we still need to check our siblings.  */
6994         WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
6995       else
6996         return NULL_TREE;
6997     }
6998
6999   result = lang_hooks.tree_inlining.walk_subtrees (tp, &walk_subtrees, func,
7000                                                    data, pset);
7001   if (result || ! walk_subtrees)
7002     return result;
7003
7004   /* If this is a DECL_EXPR, walk into various fields of the type that it's
7005      defining.  We only want to walk into these fields of a type in this
7006      case.  Note that decls get walked as part of the processing of a
7007      BIND_EXPR.
7008
7009      ??? Precisely which fields of types that we are supposed to walk in
7010      this case vs. the normal case aren't well defined.  */
7011   if (code == DECL_EXPR
7012       && TREE_CODE (DECL_EXPR_DECL (*tp)) == TYPE_DECL
7013       && TREE_CODE (TREE_TYPE (DECL_EXPR_DECL (*tp))) != ERROR_MARK)
7014     {
7015       tree *type_p = &TREE_TYPE (DECL_EXPR_DECL (*tp));
7016
7017       /* Call the function for the type.  See if it returns anything or
7018          doesn't want us to continue.  If we are to continue, walk both
7019          the normal fields and those for the declaration case.  */
7020       result = (*func) (type_p, &walk_subtrees, data);
7021       if (result || !walk_subtrees)
7022         return NULL_TREE;
7023
7024       result = walk_type_fields (*type_p, func, data, pset);
7025       if (result)
7026         return result;
7027
7028       WALK_SUBTREE (TYPE_SIZE (*type_p));
7029       WALK_SUBTREE (TYPE_SIZE_UNIT (*type_p));
7030
7031       /* If this is a record type, also walk the fields.  */
7032       if (TREE_CODE (*type_p) == RECORD_TYPE
7033           || TREE_CODE (*type_p) == UNION_TYPE
7034           || TREE_CODE (*type_p) == QUAL_UNION_TYPE)
7035         {
7036           tree field;
7037
7038           for (field = TYPE_FIELDS (*type_p); field;
7039                field = TREE_CHAIN (field))
7040             {
7041               /* We'd like to look at the type of the field, but we can easily
7042                  get infinite recursion.  So assume it's pointed to elsewhere
7043                  in the tree.  Also, ignore things that aren't fields.  */
7044               if (TREE_CODE (field) != FIELD_DECL)
7045                 continue;
7046
7047               WALK_SUBTREE (DECL_FIELD_OFFSET (field));
7048               WALK_SUBTREE (DECL_SIZE (field));
7049               WALK_SUBTREE (DECL_SIZE_UNIT (field));
7050               if (TREE_CODE (*type_p) == QUAL_UNION_TYPE)
7051                 WALK_SUBTREE (DECL_QUALIFIER (field));
7052             }
7053         }
7054     }
7055
7056   else if (code != SAVE_EXPR
7057            && code != BIND_EXPR
7058            && IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
7059     {
7060       int i, len;
7061
7062       /* Walk over all the sub-trees of this operand.  */
7063       len = TREE_CODE_LENGTH (code);
7064       /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
7065          But, we only want to walk once.  */
7066       if (code == TARGET_EXPR
7067           && TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1))
7068         --len;
7069
7070       /* Go through the subtrees.  We need to do this in forward order so
7071          that the scope of a FOR_EXPR is handled properly.  */
7072 #ifdef DEBUG_WALK_TREE
7073       for (i = 0; i < len; ++i)
7074         WALK_SUBTREE (TREE_OPERAND (*tp, i));
7075 #else
7076       for (i = 0; i < len - 1; ++i)
7077         WALK_SUBTREE (TREE_OPERAND (*tp, i));
7078
7079       if (len)
7080         {
7081           /* The common case is that we may tail recurse here.  */
7082           if (code != BIND_EXPR
7083               && !TREE_CHAIN (*tp))
7084             WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len - 1));
7085           else
7086             WALK_SUBTREE (TREE_OPERAND (*tp, len - 1));
7087         }
7088 #endif
7089     }
7090
7091   /* If this is a type, walk the needed fields in the type.  */
7092   else if (TYPE_P (*tp))
7093     {
7094       result = walk_type_fields (*tp, func, data, pset);
7095       if (result)
7096         return result;
7097     }
7098   else
7099     {
7100       /* Not one of the easy cases.  We must explicitly go through the
7101          children.  */
7102       switch (code)
7103         {
7104         case ERROR_MARK:
7105         case IDENTIFIER_NODE:
7106         case INTEGER_CST:
7107         case REAL_CST:
7108         case VECTOR_CST:
7109         case STRING_CST:
7110         case BLOCK:
7111         case PLACEHOLDER_EXPR:
7112         case SSA_NAME:
7113         case FIELD_DECL:
7114         case RESULT_DECL:
7115           /* None of these have subtrees other than those already walked
7116              above.  */
7117           break;
7118
7119         case TREE_LIST:
7120           WALK_SUBTREE (TREE_VALUE (*tp));
7121           WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
7122           break;
7123
7124         case TREE_VEC:
7125           {
7126             int len = TREE_VEC_LENGTH (*tp);
7127
7128             if (len == 0)
7129               break;
7130
7131             /* Walk all elements but the first.  */
7132             while (--len)
7133               WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
7134
7135             /* Now walk the first one as a tail call.  */
7136             WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
7137           }
7138
7139         case COMPLEX_CST:
7140           WALK_SUBTREE (TREE_REALPART (*tp));
7141           WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp));
7142
7143         case CONSTRUCTOR:
7144           {
7145             unsigned HOST_WIDE_INT idx;
7146             constructor_elt *ce;
7147
7148             for (idx = 0;
7149                  VEC_iterate(constructor_elt, CONSTRUCTOR_ELTS (*tp), idx, ce);
7150                  idx++)
7151               WALK_SUBTREE (ce->value);
7152           }
7153           break;
7154
7155         case SAVE_EXPR:
7156           WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 0));
7157
7158         case BIND_EXPR:
7159           {
7160             tree decl;
7161             for (decl = BIND_EXPR_VARS (*tp); decl; decl = TREE_CHAIN (decl))
7162               {
7163                 /* Walk the DECL_INITIAL and DECL_SIZE.  We don't want to walk
7164                    into declarations that are just mentioned, rather than
7165                    declared; they don't really belong to this part of the tree.
7166                    And, we can see cycles: the initializer for a declaration
7167                    can refer to the declaration itself.  */
7168                 WALK_SUBTREE (DECL_INITIAL (decl));
7169                 WALK_SUBTREE (DECL_SIZE (decl));
7170                 WALK_SUBTREE (DECL_SIZE_UNIT (decl));
7171               }
7172             WALK_SUBTREE_TAIL (BIND_EXPR_BODY (*tp));
7173           }
7174
7175         case STATEMENT_LIST:
7176           {
7177             tree_stmt_iterator i;
7178             for (i = tsi_start (*tp); !tsi_end_p (i); tsi_next (&i))
7179               WALK_SUBTREE (*tsi_stmt_ptr (i));
7180           }
7181           break;
7182
7183         default:
7184           /* ??? This could be a language-defined node.  We really should make
7185              a hook for it, but right now just ignore it.  */
7186           break;
7187         }
7188     }
7189
7190   /* We didn't find what we were looking for.  */
7191   return NULL_TREE;
7192
7193 #undef WALK_SUBTREE_TAIL
7194 }
7195 #undef WALK_SUBTREE
7196
7197 /* Like walk_tree, but does not walk duplicate nodes more than once.  */
7198
7199 tree
7200 walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data)
7201 {
7202   tree result;
7203   struct pointer_set_t *pset;
7204
7205   pset = pointer_set_create ();
7206   result = walk_tree (tp, func, data, pset);
7207   pointer_set_destroy (pset);
7208   return result;
7209 }
7210
7211 #include "gt-tree.h"