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