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_DLLIMPORT_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
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 = 1;
3482
3483   /* What we need to do here is remove from `old' dllimport if it doesn't
3484      appear in `new'.  dllimport behaves like extern: if a declaration is
3485      marked dllimport and a definition appears later, then the object
3486      is not dllimport'd.  We also remove a `new' dllimport if the old list
3487      contains dllexport:  dllexport always overrides dllimport, regardless
3488      of the order of declaration.  */
3489   if (!VAR_OR_FUNCTION_DECL_P (new))
3490     delete_dllimport_p = 0;
3491   else if (DECL_DLLIMPORT_P (new)
3492            && lookup_attribute ("dllexport", DECL_ATTRIBUTES (old)))
3493     {
3494       DECL_DLLIMPORT_P (new) = 0;
3495       warning (OPT_Wattributes, "%q+D already declared with dllexport attribute: "
3496               "dllimport ignored", new);
3497     }
3498   else if (DECL_DLLIMPORT_P (old) && !DECL_DLLIMPORT_P (new))
3499     {
3500       /* Warn about overriding a symbol that has already been used. eg:
3501            extern int __attribute__ ((dllimport)) foo;
3502            int* bar () {return &foo;}
3503            int foo;
3504       */
3505       if (TREE_USED (old))
3506         {
3507           warning (0, "%q+D redeclared without dllimport attribute "
3508                    "after being referenced with dll linkage", new);
3509           /* If we have used a variable's address with dllimport linkage,
3510               keep the old DECL_DLLIMPORT_P flag: the ADDR_EXPR using the
3511               decl may already have had TREE_INVARIANT and TREE_CONSTANT
3512               computed.
3513               We still remove the attribute so that assembler code refers
3514               to '&foo rather than '_imp__foo'.  */
3515           if (TREE_CODE (old) == VAR_DECL && TREE_ADDRESSABLE (old))
3516             DECL_DLLIMPORT_P (new) = 1;
3517         }
3518
3519       /* Let an inline definition silently override the external reference,
3520          but otherwise warn about attribute inconsistency.  */
3521       else if (TREE_CODE (new) == VAR_DECL
3522                || !DECL_DECLARED_INLINE_P (new))
3523         warning (OPT_Wattributes, "%q+D redeclared without dllimport attribute: "
3524                   "previous dllimport ignored", new);
3525     }
3526   else
3527     delete_dllimport_p = 0;
3528
3529   a = merge_attributes (DECL_ATTRIBUTES (old), DECL_ATTRIBUTES (new));
3530
3531   if (delete_dllimport_p)
3532     {
3533       tree prev, t;
3534       const size_t attr_len = strlen ("dllimport");
3535
3536       /* Scan the list for dllimport and delete it.  */
3537       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
3538         {
3539           if (is_attribute_with_length_p ("dllimport", attr_len,
3540                                           TREE_PURPOSE (t)))
3541             {
3542               if (prev == NULL_TREE)
3543                 a = TREE_CHAIN (a);
3544               else
3545                 TREE_CHAIN (prev) = TREE_CHAIN (t);
3546               break;
3547             }
3548         }
3549     }
3550
3551   return a;
3552 }
3553
3554 /* Handle a "dllimport" or "dllexport" attribute; arguments as in
3555    struct attribute_spec.handler.  */
3556
3557 tree
3558 handle_dll_attribute (tree * pnode, tree name, tree args, int flags,
3559                       bool *no_add_attrs)
3560 {
3561   tree node = *pnode;
3562
3563   /* These attributes may apply to structure and union types being created,
3564      but otherwise should pass to the declaration involved.  */
3565   if (!DECL_P (node))
3566     {
3567       if (flags & ((int) ATTR_FLAG_DECL_NEXT | (int) ATTR_FLAG_FUNCTION_NEXT
3568                    | (int) ATTR_FLAG_ARRAY_NEXT))
3569         {
3570           *no_add_attrs = true;
3571           return tree_cons (name, args, NULL_TREE);
3572         }
3573       if (TREE_CODE (node) != RECORD_TYPE && TREE_CODE (node) != UNION_TYPE)
3574         {
3575           warning (OPT_Wattributes, "%qs attribute ignored",
3576                    IDENTIFIER_POINTER (name));
3577           *no_add_attrs = true;
3578         }
3579
3580       return NULL_TREE;
3581     }
3582
3583   /* Report error on dllimport ambiguities seen now before they cause
3584      any damage.  */
3585   if (is_attribute_p ("dllimport", name))
3586     {
3587       /* Honor any target-specific overrides. */
3588       if (!targetm.valid_dllimport_attribute_p (node))
3589         *no_add_attrs = true;
3590
3591      else if (TREE_CODE (node) == FUNCTION_DECL
3592                 && DECL_DECLARED_INLINE_P (node))
3593         {
3594           warning (OPT_Wattributes, "inline function %q+D declared as "
3595                   " dllimport: attribute ignored", node);
3596           *no_add_attrs = true;
3597         }
3598       /* Like MS, treat definition of dllimported variables and
3599          non-inlined functions on declaration as syntax errors. */
3600      else if (TREE_CODE (node) == FUNCTION_DECL && DECL_INITIAL (node))
3601         {
3602           error ("function %q+D definition is marked dllimport", node);
3603           *no_add_attrs = true;
3604         }
3605
3606      else if (TREE_CODE (node) == VAR_DECL)
3607         {
3608           if (DECL_INITIAL (node))
3609             {
3610               error ("variable %q+D definition is marked dllimport",
3611                      node);
3612               *no_add_attrs = true;
3613             }
3614
3615           /* `extern' needn't be specified with dllimport.
3616              Specify `extern' now and hope for the best.  Sigh.  */
3617           DECL_EXTERNAL (node) = 1;
3618           /* Also, implicitly give dllimport'd variables declared within
3619              a function global scope, unless declared static.  */
3620           if (current_function_decl != NULL_TREE && !TREE_STATIC (node))
3621             TREE_PUBLIC (node) = 1;
3622         }
3623
3624       if (*no_add_attrs == false)
3625         DECL_DLLIMPORT_P (node) = 1;
3626     }
3627
3628   /*  Report error if symbol is not accessible at global scope.  */
3629   if (!TREE_PUBLIC (node)
3630       && (TREE_CODE (node) == VAR_DECL
3631           || TREE_CODE (node) == FUNCTION_DECL))
3632     {
3633       error ("external linkage required for symbol %q+D because of "
3634              "%qs attribute", node, IDENTIFIER_POINTER (name));
3635       *no_add_attrs = true;
3636     }
3637
3638   return NULL_TREE;
3639 }
3640
3641 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
3642 \f
3643 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
3644    of the various TYPE_QUAL values.  */
3645
3646 static void
3647 set_type_quals (tree type, int type_quals)
3648 {
3649   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
3650   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
3651   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
3652 }
3653
3654 /* Returns true iff cand is equivalent to base with type_quals.  */
3655
3656 bool
3657 check_qualified_type (tree cand, tree base, int type_quals)
3658 {
3659   return (TYPE_QUALS (cand) == type_quals
3660           && TYPE_NAME (cand) == TYPE_NAME (base)
3661           /* Apparently this is needed for Objective-C.  */
3662           && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base)
3663           && attribute_list_equal (TYPE_ATTRIBUTES (cand),
3664                                    TYPE_ATTRIBUTES (base)));
3665 }
3666
3667 /* Return a version of the TYPE, qualified as indicated by the
3668    TYPE_QUALS, if one exists.  If no qualified version exists yet,
3669    return NULL_TREE.  */
3670
3671 tree
3672 get_qualified_type (tree type, int type_quals)
3673 {
3674   tree t;
3675
3676   if (TYPE_QUALS (type) == type_quals)
3677     return type;
3678
3679   /* Search the chain of variants to see if there is already one there just
3680      like the one we need to have.  If so, use that existing one.  We must
3681      preserve the TYPE_NAME, since there is code that depends on this.  */
3682   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
3683     if (check_qualified_type (t, type, type_quals))
3684       return t;
3685
3686   return NULL_TREE;
3687 }
3688
3689 /* Like get_qualified_type, but creates the type if it does not
3690    exist.  This function never returns NULL_TREE.  */
3691
3692 tree
3693 build_qualified_type (tree type, int type_quals)
3694 {
3695   tree t;
3696
3697   /* See if we already have the appropriate qualified variant.  */
3698   t = get_qualified_type (type, type_quals);
3699
3700   /* If not, build it.  */
3701   if (!t)
3702     {
3703       t = build_variant_type_copy (type);
3704       set_type_quals (t, type_quals);
3705
3706       /* If it's a pointer type, the new variant points to the same type.  */
3707       if (TREE_CODE (type) == POINTER_TYPE)
3708         {
3709           TYPE_NEXT_PTR_TO (t) = TYPE_NEXT_PTR_TO (type);
3710           TYPE_NEXT_PTR_TO (type) = t;
3711         }
3712
3713       /* Same for a reference type.  */
3714       else if (TREE_CODE (type) == REFERENCE_TYPE)
3715         {
3716           TYPE_NEXT_REF_TO (t) = TYPE_NEXT_REF_TO (type);
3717           TYPE_NEXT_REF_TO (type) = t;
3718         }
3719     }
3720
3721   return t;
3722 }
3723
3724 /* Create a new distinct copy of TYPE.  The new type is made its own
3725    MAIN_VARIANT.  */
3726
3727 tree
3728 build_distinct_type_copy (tree type)
3729 {
3730   tree t = copy_node (type);
3731
3732   TYPE_POINTER_TO (t) = 0;
3733   TYPE_REFERENCE_TO (t) = 0;
3734
3735   /* Make it its own variant.  */
3736   TYPE_MAIN_VARIANT (t) = t;
3737   TYPE_NEXT_VARIANT (t) = 0;
3738
3739   return t;
3740 }
3741
3742 /* Create a new variant of TYPE, equivalent but distinct.
3743    This is so the caller can modify it.  */
3744
3745 tree
3746 build_variant_type_copy (tree type)
3747 {
3748   tree t, m = TYPE_MAIN_VARIANT (type);
3749
3750   t = build_distinct_type_copy (type);
3751
3752   /* Add the new type to the chain of variants of TYPE.  */
3753   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3754   TYPE_NEXT_VARIANT (m) = t;
3755   TYPE_MAIN_VARIANT (t) = m;
3756
3757   return t;
3758 }
3759 \f
3760 /* Return true if the from tree in both tree maps are equal.  */
3761
3762 int
3763 tree_map_eq (const void *va, const void *vb)
3764 {
3765   const struct tree_map  *a = va, *b = vb;
3766   return (a->from == b->from);
3767 }
3768
3769 /* Hash a from tree in a tree_map.  */
3770
3771 unsigned int
3772 tree_map_hash (const void *item)
3773 {
3774   return (((const struct tree_map *) item)->hash);
3775 }
3776
3777 /* Return true if this tree map structure is marked for garbage collection
3778    purposes.  We simply return true if the from tree is marked, so that this
3779    structure goes away when the from tree goes away.  */
3780
3781 int
3782 tree_map_marked_p (const void *p)
3783 {
3784   tree from = ((struct tree_map *) p)->from;
3785
3786   return ggc_marked_p (from);
3787 }
3788
3789 /* Return true if the trees in the tree_int_map *'s VA and VB are equal.  */
3790
3791 static int
3792 tree_int_map_eq (const void *va, const void *vb)
3793 {
3794   const struct tree_int_map  *a = va, *b = vb;
3795   return (a->from == b->from);
3796 }
3797
3798 /* Hash a from tree in the tree_int_map * ITEM.  */
3799
3800 static unsigned int
3801 tree_int_map_hash (const void *item)
3802 {
3803   return htab_hash_pointer (((const struct tree_int_map *)item)->from);
3804 }
3805
3806 /* Return true if this tree int map structure is marked for garbage collection
3807    purposes.  We simply return true if the from tree_int_map *P's from tree is marked, so that this
3808    structure goes away when the from tree goes away.  */
3809
3810 static int
3811 tree_int_map_marked_p (const void *p)
3812 {
3813   tree from = ((struct tree_int_map *) p)->from;
3814
3815   return ggc_marked_p (from);
3816 }
3817 /* Lookup an init priority for FROM, and return it if we find one.  */
3818
3819 unsigned short
3820 decl_init_priority_lookup (tree from)
3821 {
3822   struct tree_int_map *h, in;
3823   in.from = from;
3824
3825   h = htab_find_with_hash (init_priority_for_decl,
3826                            &in, htab_hash_pointer (from));
3827   if (h)
3828     return h->to;
3829   return 0;
3830 }
3831
3832 /* Insert a mapping FROM->TO in the init priority hashtable.  */
3833
3834 void
3835 decl_init_priority_insert (tree from, unsigned short to)
3836 {
3837   struct tree_int_map *h;
3838   void **loc;
3839
3840   h = ggc_alloc (sizeof (struct tree_int_map));
3841   h->from = from;
3842   h->to = to;
3843   loc = htab_find_slot_with_hash (init_priority_for_decl, h,
3844                                   htab_hash_pointer (from), INSERT);
3845   *(struct tree_int_map **) loc = h;
3846 }
3847
3848 /* Look up a restrict qualified base decl for FROM.  */
3849
3850 tree
3851 decl_restrict_base_lookup (tree from)
3852 {
3853   struct tree_map *h;
3854   struct tree_map in;
3855
3856   in.from = from;
3857   h = htab_find_with_hash (restrict_base_for_decl, &in,
3858                            htab_hash_pointer (from));
3859   return h ? h->to : NULL_TREE;
3860 }
3861
3862 /* Record the restrict qualified base TO for FROM.  */
3863
3864 void
3865 decl_restrict_base_insert (tree from, tree to)
3866 {
3867   struct tree_map *h;
3868   void **loc;
3869
3870   h = ggc_alloc (sizeof (struct tree_map));
3871   h->hash = htab_hash_pointer (from);
3872   h->from = from;
3873   h->to = to;
3874   loc = htab_find_slot_with_hash (restrict_base_for_decl, h, h->hash, INSERT);
3875   *(struct tree_map **) loc = h;
3876 }
3877
3878 /* Print out the statistics for the DECL_DEBUG_EXPR hash table.  */
3879
3880 static void
3881 print_debug_expr_statistics (void)
3882 {
3883   fprintf (stderr, "DECL_DEBUG_EXPR  hash: size %ld, %ld elements, %f collisions\n",
3884            (long) htab_size (debug_expr_for_decl),
3885            (long) htab_elements (debug_expr_for_decl),
3886            htab_collisions (debug_expr_for_decl));
3887 }
3888
3889 /* Print out the statistics for the DECL_VALUE_EXPR hash table.  */
3890
3891 static void
3892 print_value_expr_statistics (void)
3893 {
3894   fprintf (stderr, "DECL_VALUE_EXPR  hash: size %ld, %ld elements, %f collisions\n",
3895            (long) htab_size (value_expr_for_decl),
3896            (long) htab_elements (value_expr_for_decl),
3897            htab_collisions (value_expr_for_decl));
3898 }
3899
3900 /* Print out statistics for the RESTRICT_BASE_FOR_DECL hash table, but
3901    don't print anything if the table is empty.  */
3902
3903 static void
3904 print_restrict_base_statistics (void)
3905 {
3906   if (htab_elements (restrict_base_for_decl) != 0)
3907     fprintf (stderr,
3908              "RESTRICT_BASE    hash: size %ld, %ld elements, %f collisions\n",
3909              (long) htab_size (restrict_base_for_decl),
3910              (long) htab_elements (restrict_base_for_decl),
3911              htab_collisions (restrict_base_for_decl));
3912 }
3913
3914 /* Lookup a debug expression for FROM, and return it if we find one.  */
3915
3916 tree
3917 decl_debug_expr_lookup (tree from)
3918 {
3919   struct tree_map *h, in;
3920   in.from = from;
3921
3922   h = htab_find_with_hash (debug_expr_for_decl, &in, htab_hash_pointer (from));
3923   if (h)
3924     return h->to;
3925   return NULL_TREE;
3926 }
3927
3928 /* Insert a mapping FROM->TO in the debug expression hashtable.  */
3929
3930 void
3931 decl_debug_expr_insert (tree from, tree to)
3932 {
3933   struct tree_map *h;
3934   void **loc;
3935
3936   h = ggc_alloc (sizeof (struct tree_map));
3937   h->hash = htab_hash_pointer (from);
3938   h->from = from;
3939   h->to = to;
3940   loc = htab_find_slot_with_hash (debug_expr_for_decl, h, h->hash, INSERT);
3941   *(struct tree_map **) loc = h;
3942 }
3943
3944 /* Lookup a value expression for FROM, and return it if we find one.  */
3945
3946 tree
3947 decl_value_expr_lookup (tree from)
3948 {
3949   struct tree_map *h, in;
3950   in.from = from;
3951
3952   h = htab_find_with_hash (value_expr_for_decl, &in, htab_hash_pointer (from));
3953   if (h)
3954     return h->to;
3955   return NULL_TREE;
3956 }
3957
3958 /* Insert a mapping FROM->TO in the value expression hashtable.  */
3959
3960 void
3961 decl_value_expr_insert (tree from, tree to)
3962 {
3963   struct tree_map *h;
3964   void **loc;
3965
3966   h = ggc_alloc (sizeof (struct tree_map));
3967   h->hash = htab_hash_pointer (from);
3968   h->from = from;
3969   h->to = to;
3970   loc = htab_find_slot_with_hash (value_expr_for_decl, h, h->hash, INSERT);
3971   *(struct tree_map **) loc = h;
3972 }
3973
3974 /* Hashing of types so that we don't make duplicates.
3975    The entry point is `type_hash_canon'.  */
3976
3977 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
3978    with types in the TREE_VALUE slots), by adding the hash codes
3979    of the individual types.  */
3980
3981 unsigned int
3982 type_hash_list (tree list, hashval_t hashcode)
3983 {
3984   tree tail;
3985
3986   for (tail = list; tail; tail = TREE_CHAIN (tail))
3987     if (TREE_VALUE (tail) != error_mark_node)
3988       hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
3989                                         hashcode);
3990
3991   return hashcode;
3992 }
3993
3994 /* These are the Hashtable callback functions.  */
3995
3996 /* Returns true iff the types are equivalent.  */
3997
3998 static int
3999 type_hash_eq (const void *va, const void *vb)
4000 {
4001   const struct type_hash *a = va, *b = vb;
4002
4003   /* First test the things that are the same for all types.  */
4004   if (a->hash != b->hash
4005       || TREE_CODE (a->type) != TREE_CODE (b->type)
4006       || TREE_TYPE (a->type) != TREE_TYPE (b->type)
4007       || !attribute_list_equal (TYPE_ATTRIBUTES (a->type),
4008                                  TYPE_ATTRIBUTES (b->type))
4009       || TYPE_ALIGN (a->type) != TYPE_ALIGN (b->type)
4010       || TYPE_MODE (a->type) != TYPE_MODE (b->type))
4011     return 0;
4012
4013   switch (TREE_CODE (a->type))
4014     {
4015     case VOID_TYPE:
4016     case COMPLEX_TYPE:
4017     case POINTER_TYPE:
4018     case REFERENCE_TYPE:
4019       return 1;
4020
4021     case VECTOR_TYPE:
4022       return TYPE_VECTOR_SUBPARTS (a->type) == TYPE_VECTOR_SUBPARTS (b->type);
4023
4024     case ENUMERAL_TYPE:
4025       if (TYPE_VALUES (a->type) != TYPE_VALUES (b->type)
4026           && !(TYPE_VALUES (a->type)
4027                && TREE_CODE (TYPE_VALUES (a->type)) == TREE_LIST
4028                && TYPE_VALUES (b->type)
4029                && TREE_CODE (TYPE_VALUES (b->type)) == TREE_LIST
4030                && type_list_equal (TYPE_VALUES (a->type),
4031                                    TYPE_VALUES (b->type))))
4032         return 0;
4033
4034       /* ... fall through ... */
4035
4036     case INTEGER_TYPE:
4037     case REAL_TYPE:
4038     case BOOLEAN_TYPE:
4039     case CHAR_TYPE:
4040       return ((TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
4041                || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
4042                                       TYPE_MAX_VALUE (b->type)))
4043               && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
4044                   || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
4045                                          TYPE_MIN_VALUE (b->type))));
4046
4047     case OFFSET_TYPE:
4048       return TYPE_OFFSET_BASETYPE (a->type) == TYPE_OFFSET_BASETYPE (b->type);
4049
4050     case METHOD_TYPE:
4051       return (TYPE_METHOD_BASETYPE (a->type) == TYPE_METHOD_BASETYPE (b->type)
4052               && (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
4053                   || (TYPE_ARG_TYPES (a->type)
4054                       && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
4055                       && TYPE_ARG_TYPES (b->type)
4056                       && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
4057                       && type_list_equal (TYPE_ARG_TYPES (a->type),
4058                                           TYPE_ARG_TYPES (b->type)))));
4059
4060     case ARRAY_TYPE:
4061       return TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type);
4062
4063     case RECORD_TYPE:
4064     case UNION_TYPE:
4065     case QUAL_UNION_TYPE:
4066       return (TYPE_FIELDS (a->type) == TYPE_FIELDS (b->type)
4067               || (TYPE_FIELDS (a->type)
4068                   && TREE_CODE (TYPE_FIELDS (a->type)) == TREE_LIST
4069                   && TYPE_FIELDS (b->type)
4070                   && TREE_CODE (TYPE_FIELDS (b->type)) == TREE_LIST
4071                   && type_list_equal (TYPE_FIELDS (a->type),
4072                                       TYPE_FIELDS (b->type))));
4073
4074     case FUNCTION_TYPE:
4075       return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
4076               || (TYPE_ARG_TYPES (a->type)
4077                   && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
4078                   && TYPE_ARG_TYPES (b->type)
4079                   && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
4080                   && type_list_equal (TYPE_ARG_TYPES (a->type),
4081                                       TYPE_ARG_TYPES (b->type))));
4082
4083     default:
4084       return 0;
4085     }
4086 }
4087
4088 /* Return the cached hash value.  */
4089
4090 static hashval_t
4091 type_hash_hash (const void *item)
4092 {
4093   return ((const struct type_hash *) item)->hash;
4094 }
4095
4096 /* Look in the type hash table for a type isomorphic to TYPE.
4097    If one is found, return it.  Otherwise return 0.  */
4098
4099 tree
4100 type_hash_lookup (hashval_t hashcode, tree type)
4101 {
4102   struct type_hash *h, in;
4103
4104   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
4105      must call that routine before comparing TYPE_ALIGNs.  */
4106   layout_type (type);
4107
4108   in.hash = hashcode;
4109   in.type = type;
4110
4111   h = htab_find_with_hash (type_hash_table, &in, hashcode);
4112   if (h)
4113     return h->type;
4114   return NULL_TREE;
4115 }
4116
4117 /* Add an entry to the type-hash-table
4118    for a type TYPE whose hash code is HASHCODE.  */
4119
4120 void
4121 type_hash_add (hashval_t hashcode, tree type)
4122 {
4123   struct type_hash *h;
4124   void **loc;
4125
4126   h = ggc_alloc (sizeof (struct type_hash));
4127   h->hash = hashcode;
4128   h->type = type;
4129   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
4130   *(struct type_hash **) loc = h;
4131 }
4132
4133 /* Given TYPE, and HASHCODE its hash code, return the canonical
4134    object for an identical type if one already exists.
4135    Otherwise, return TYPE, and record it as the canonical object.
4136
4137    To use this function, first create a type of the sort you want.
4138    Then compute its hash code from the fields of the type that
4139    make it different from other similar types.
4140    Then call this function and use the value.  */
4141
4142 tree
4143 type_hash_canon (unsigned int hashcode, tree type)
4144 {
4145   tree t1;
4146
4147   /* The hash table only contains main variants, so ensure that's what we're
4148      being passed.  */
4149   gcc_assert (TYPE_MAIN_VARIANT (type) == type);
4150
4151   if (!lang_hooks.types.hash_types)
4152     return type;
4153
4154   /* See if the type is in the hash table already.  If so, return it.
4155      Otherwise, add the type.  */
4156   t1 = type_hash_lookup (hashcode, type);
4157   if (t1 != 0)
4158     {
4159 #ifdef GATHER_STATISTICS
4160       tree_node_counts[(int) t_kind]--;
4161       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
4162 #endif
4163       return t1;
4164     }
4165   else
4166     {
4167       type_hash_add (hashcode, type);
4168       return type;
4169     }
4170 }
4171
4172 /* See if the data pointed to by the type hash table is marked.  We consider
4173    it marked if the type is marked or if a debug type number or symbol
4174    table entry has been made for the type.  This reduces the amount of
4175    debugging output and eliminates that dependency of the debug output on
4176    the number of garbage collections.  */
4177
4178 static int
4179 type_hash_marked_p (const void *p)
4180 {
4181   tree type = ((struct type_hash *) p)->type;
4182
4183   return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
4184 }
4185
4186 static void
4187 print_type_hash_statistics (void)
4188 {
4189   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
4190            (long) htab_size (type_hash_table),
4191            (long) htab_elements (type_hash_table),
4192            htab_collisions (type_hash_table));
4193 }
4194
4195 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
4196    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
4197    by adding the hash codes of the individual attributes.  */
4198
4199 unsigned int
4200 attribute_hash_list (tree list, hashval_t hashcode)
4201 {
4202   tree tail;
4203
4204   for (tail = list; tail; tail = TREE_CHAIN (tail))
4205     /* ??? Do we want to add in TREE_VALUE too? */
4206     hashcode = iterative_hash_object
4207       (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode);
4208   return hashcode;
4209 }
4210
4211 /* Given two lists of attributes, return true if list l2 is
4212    equivalent to l1.  */
4213
4214 int
4215 attribute_list_equal (tree l1, tree l2)
4216 {
4217   return attribute_list_contained (l1, l2)
4218          && attribute_list_contained (l2, l1);
4219 }
4220
4221 /* Given two lists of attributes, return true if list L2 is
4222    completely contained within L1.  */
4223 /* ??? This would be faster if attribute names were stored in a canonicalized
4224    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
4225    must be used to show these elements are equivalent (which they are).  */
4226 /* ??? It's not clear that attributes with arguments will always be handled
4227    correctly.  */
4228
4229 int
4230 attribute_list_contained (tree l1, tree l2)
4231 {
4232   tree t1, t2;
4233
4234   /* First check the obvious, maybe the lists are identical.  */
4235   if (l1 == l2)
4236     return 1;
4237
4238   /* Maybe the lists are similar.  */
4239   for (t1 = l1, t2 = l2;
4240        t1 != 0 && t2 != 0
4241         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
4242         && TREE_VALUE (t1) == TREE_VALUE (t2);
4243        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
4244
4245   /* Maybe the lists are equal.  */
4246   if (t1 == 0 && t2 == 0)
4247     return 1;
4248
4249   for (; t2 != 0; t2 = TREE_CHAIN (t2))
4250     {
4251       tree attr;
4252       for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
4253            attr != NULL_TREE;
4254            attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
4255                                     TREE_CHAIN (attr)))
4256         {
4257           if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
4258             break;
4259         }
4260
4261       if (attr == 0)
4262         return 0;
4263
4264       if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) != 1)
4265         return 0;
4266     }
4267
4268   return 1;
4269 }
4270
4271 /* Given two lists of types
4272    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
4273    return 1 if the lists contain the same types in the same order.
4274    Also, the TREE_PURPOSEs must match.  */
4275
4276 int
4277 type_list_equal (tree l1, tree l2)
4278 {
4279   tree t1, t2;
4280
4281   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
4282     if (TREE_VALUE (t1) != TREE_VALUE (t2)
4283         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
4284             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
4285                   && (TREE_TYPE (TREE_PURPOSE (t1))
4286                       == TREE_TYPE (TREE_PURPOSE (t2))))))
4287       return 0;
4288
4289   return t1 == t2;
4290 }
4291
4292 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
4293    given by TYPE.  If the argument list accepts variable arguments,
4294    then this function counts only the ordinary arguments.  */
4295
4296 int
4297 type_num_arguments (tree type)
4298 {
4299   int i = 0;
4300   tree t;
4301
4302   for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
4303     /* If the function does not take a variable number of arguments,
4304        the last element in the list will have type `void'.  */
4305     if (VOID_TYPE_P (TREE_VALUE (t)))
4306       break;
4307     else
4308       ++i;
4309
4310   return i;
4311 }
4312
4313 /* Nonzero if integer constants T1 and T2
4314    represent the same constant value.  */
4315
4316 int
4317 tree_int_cst_equal (tree t1, tree t2)
4318 {
4319   if (t1 == t2)
4320     return 1;
4321
4322   if (t1 == 0 || t2 == 0)
4323     return 0;
4324
4325   if (TREE_CODE (t1) == INTEGER_CST
4326       && TREE_CODE (t2) == INTEGER_CST
4327       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
4328       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
4329     return 1;
4330
4331   return 0;
4332 }
4333
4334 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
4335    The precise way of comparison depends on their data type.  */
4336
4337 int
4338 tree_int_cst_lt (tree t1, tree t2)
4339 {
4340   if (t1 == t2)
4341     return 0;
4342
4343   if (TYPE_UNSIGNED (TREE_TYPE (t1)) != TYPE_UNSIGNED (TREE_TYPE (t2)))
4344     {
4345       int t1_sgn = tree_int_cst_sgn (t1);
4346       int t2_sgn = tree_int_cst_sgn (t2);
4347
4348       if (t1_sgn < t2_sgn)
4349         return 1;
4350       else if (t1_sgn > t2_sgn)
4351         return 0;
4352       /* Otherwise, both are non-negative, so we compare them as
4353          unsigned just in case one of them would overflow a signed
4354          type.  */
4355     }
4356   else if (!TYPE_UNSIGNED (TREE_TYPE (t1)))
4357     return INT_CST_LT (t1, t2);
4358
4359   return INT_CST_LT_UNSIGNED (t1, t2);
4360 }
4361
4362 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
4363
4364 int
4365 tree_int_cst_compare (tree t1, tree t2)
4366 {
4367   if (tree_int_cst_lt (t1, t2))
4368     return -1;
4369   else if (tree_int_cst_lt (t2, t1))
4370     return 1;
4371   else
4372     return 0;
4373 }
4374
4375 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
4376    the host.  If POS is zero, the value can be represented in a single
4377    HOST_WIDE_INT.  If POS is nonzero, the value must be non-negative and can
4378    be represented in a single unsigned HOST_WIDE_INT.  */
4379
4380 int
4381 host_integerp (tree t, int pos)
4382 {
4383   return (TREE_CODE (t) == INTEGER_CST
4384           && ! TREE_OVERFLOW (t)
4385           && ((TREE_INT_CST_HIGH (t) == 0
4386                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
4387               || (! pos && TREE_INT_CST_HIGH (t) == -1
4388                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
4389                   && !TYPE_UNSIGNED (TREE_TYPE (t)))
4390               || (pos && TREE_INT_CST_HIGH (t) == 0)));
4391 }
4392
4393 /* Return the HOST_WIDE_INT least significant bits of T if it is an
4394    INTEGER_CST and there is no overflow.  POS is nonzero if the result must
4395    be non-negative.  We must be able to satisfy the above conditions.  */
4396
4397 HOST_WIDE_INT
4398 tree_low_cst (tree t, int pos)
4399 {
4400   gcc_assert (host_integerp (t, pos));
4401   return TREE_INT_CST_LOW (t);
4402 }
4403
4404 /* Return the most significant bit of the integer constant T.  */
4405
4406 int
4407 tree_int_cst_msb (tree t)
4408 {
4409   int prec;
4410   HOST_WIDE_INT h;
4411   unsigned HOST_WIDE_INT l;
4412
4413   /* Note that using TYPE_PRECISION here is wrong.  We care about the
4414      actual bits, not the (arbitrary) range of the type.  */
4415   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
4416   rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
4417                  2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
4418   return (l & 1) == 1;
4419 }
4420
4421 /* Return an indication of the sign of the integer constant T.
4422    The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
4423    Note that -1 will never be returned if T's type is unsigned.  */
4424
4425 int
4426 tree_int_cst_sgn (tree t)
4427 {
4428   if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
4429     return 0;
4430   else if (TYPE_UNSIGNED (TREE_TYPE (t)))
4431     return 1;
4432   else if (TREE_INT_CST_HIGH (t) < 0)
4433     return -1;
4434   else
4435     return 1;
4436 }
4437
4438 /* Compare two constructor-element-type constants.  Return 1 if the lists
4439    are known to be equal; otherwise return 0.  */
4440
4441 int
4442 simple_cst_list_equal (tree l1, tree l2)
4443 {
4444   while (l1 != NULL_TREE && l2 != NULL_TREE)
4445     {
4446       if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
4447         return 0;
4448
4449       l1 = TREE_CHAIN (l1);
4450       l2 = TREE_CHAIN (l2);
4451     }
4452
4453   return l1 == l2;
4454 }
4455
4456 /* Return truthvalue of whether T1 is the same tree structure as T2.
4457    Return 1 if they are the same.
4458    Return 0 if they are understandably different.
4459    Return -1 if either contains tree structure not understood by
4460    this function.  */
4461
4462 int
4463 simple_cst_equal (tree t1, tree t2)
4464 {
4465   enum tree_code code1, code2;
4466   int cmp;
4467   int i;
4468
4469   if (t1 == t2)
4470     return 1;
4471   if (t1 == 0 || t2 == 0)
4472     return 0;
4473
4474   code1 = TREE_CODE (t1);
4475   code2 = TREE_CODE (t2);
4476
4477   if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
4478     {
4479       if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
4480           || code2 == NON_LVALUE_EXPR)
4481         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4482       else
4483         return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
4484     }
4485
4486   else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
4487            || code2 == NON_LVALUE_EXPR)
4488     return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
4489
4490   if (code1 != code2)
4491     return 0;
4492
4493   switch (code1)
4494     {
4495     case INTEGER_CST:
4496       return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
4497               && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
4498
4499     case REAL_CST:
4500       return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
4501
4502     case STRING_CST:
4503       return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
4504               && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
4505                          TREE_STRING_LENGTH (t1)));
4506
4507     case CONSTRUCTOR:
4508       {
4509         unsigned HOST_WIDE_INT idx;
4510         VEC(constructor_elt, gc) *v1 = CONSTRUCTOR_ELTS (t1);
4511         VEC(constructor_elt, gc) *v2 = CONSTRUCTOR_ELTS (t2);
4512
4513         if (VEC_length (constructor_elt, v1) != VEC_length (constructor_elt, v2))
4514           return false;
4515
4516         for (idx = 0; idx < VEC_length (constructor_elt, v1); ++idx)
4517           /* ??? Should we handle also fields here? */
4518           if (!simple_cst_equal (VEC_index (constructor_elt, v1, idx)->value,
4519                                  VEC_index (constructor_elt, v2, idx)->value))
4520             return false;
4521         return true;
4522       }
4523
4524     case SAVE_EXPR:
4525       return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4526
4527     case CALL_EXPR:
4528       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4529       if (cmp <= 0)
4530         return cmp;
4531       return
4532         simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
4533
4534     case TARGET_EXPR:
4535       /* Special case: if either target is an unallocated VAR_DECL,
4536          it means that it's going to be unified with whatever the
4537          TARGET_EXPR is really supposed to initialize, so treat it
4538          as being equivalent to anything.  */
4539       if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
4540            && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
4541            && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
4542           || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
4543               && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
4544               && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
4545         cmp = 1;
4546       else
4547         cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4548
4549       if (cmp <= 0)
4550         return cmp;
4551
4552       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
4553
4554     case WITH_CLEANUP_EXPR:
4555       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4556       if (cmp <= 0)
4557         return cmp;
4558
4559       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
4560
4561     case COMPONENT_REF:
4562       if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
4563         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4564
4565       return 0;
4566
4567     case VAR_DECL:
4568     case PARM_DECL:
4569     case CONST_DECL:
4570     case FUNCTION_DECL:
4571       return 0;
4572
4573     default:
4574       break;
4575     }
4576
4577   /* This general rule works for most tree codes.  All exceptions should be
4578      handled above.  If this is a language-specific tree code, we can't
4579      trust what might be in the operand, so say we don't know
4580      the situation.  */
4581   if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
4582     return -1;
4583
4584   switch (TREE_CODE_CLASS (code1))
4585     {
4586     case tcc_unary:
4587     case tcc_binary:
4588     case tcc_comparison:
4589     case tcc_expression:
4590     case tcc_reference:
4591     case tcc_statement:
4592       cmp = 1;
4593       for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
4594         {
4595           cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
4596           if (cmp <= 0)
4597             return cmp;
4598         }
4599
4600       return cmp;
4601
4602     default:
4603       return -1;
4604     }
4605 }
4606
4607 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
4608    Return -1, 0, or 1 if the value of T is less than, equal to, or greater
4609    than U, respectively.  */
4610
4611 int
4612 compare_tree_int (tree t, unsigned HOST_WIDE_INT u)
4613 {
4614   if (tree_int_cst_sgn (t) < 0)
4615     return -1;
4616   else if (TREE_INT_CST_HIGH (t) != 0)
4617     return 1;
4618   else if (TREE_INT_CST_LOW (t) == u)
4619     return 0;
4620   else if (TREE_INT_CST_LOW (t) < u)
4621     return -1;
4622   else
4623     return 1;
4624 }
4625
4626 /* Return true if CODE represents an associative tree code.  Otherwise
4627    return false.  */
4628 bool
4629 associative_tree_code (enum tree_code code)
4630 {
4631   switch (code)
4632     {
4633     case BIT_IOR_EXPR:
4634     case BIT_AND_EXPR:
4635     case BIT_XOR_EXPR:
4636     case PLUS_EXPR:
4637     case MULT_EXPR:
4638     case MIN_EXPR:
4639     case MAX_EXPR:
4640       return true;
4641
4642     default:
4643       break;
4644     }
4645   return false;
4646 }
4647
4648 /* Return true if CODE represents a commutative tree code.  Otherwise
4649    return false.  */
4650 bool
4651 commutative_tree_code (enum tree_code code)
4652 {
4653   switch (code)
4654     {
4655     case PLUS_EXPR:
4656     case MULT_EXPR:
4657     case MIN_EXPR:
4658     case MAX_EXPR:
4659     case BIT_IOR_EXPR:
4660     case BIT_XOR_EXPR:
4661     case BIT_AND_EXPR:
4662     case NE_EXPR:
4663     case EQ_EXPR:
4664     case UNORDERED_EXPR:
4665     case ORDERED_EXPR:
4666     case UNEQ_EXPR:
4667     case LTGT_EXPR:
4668     case TRUTH_AND_EXPR:
4669     case TRUTH_XOR_EXPR:
4670     case TRUTH_OR_EXPR:
4671       return true;
4672
4673     default:
4674       break;
4675     }
4676   return false;
4677 }
4678
4679 /* Generate a hash value for an expression.  This can be used iteratively
4680    by passing a previous result as the "val" argument.
4681
4682    This function is intended to produce the same hash for expressions which
4683    would compare equal using operand_equal_p.  */
4684
4685 hashval_t
4686 iterative_hash_expr (tree t, hashval_t val)
4687 {
4688   int i;
4689   enum tree_code code;
4690   char class;
4691
4692   if (t == NULL_TREE)
4693     return iterative_hash_pointer (t, val);
4694
4695   code = TREE_CODE (t);
4696
4697   switch (code)
4698     {
4699     /* Alas, constants aren't shared, so we can't rely on pointer
4700        identity.  */
4701     case INTEGER_CST:
4702       val = iterative_hash_host_wide_int (TREE_INT_CST_LOW (t), val);
4703       return iterative_hash_host_wide_int (TREE_INT_CST_HIGH (t), val);
4704     case REAL_CST:
4705       {
4706         unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t));
4707
4708         return iterative_hash_hashval_t (val2, val);
4709       }
4710     case STRING_CST:
4711       return iterative_hash (TREE_STRING_POINTER (t),
4712                              TREE_STRING_LENGTH (t), val);
4713     case COMPLEX_CST:
4714       val = iterative_hash_expr (TREE_REALPART (t), val);
4715       return iterative_hash_expr (TREE_IMAGPART (t), val);
4716     case VECTOR_CST:
4717       return iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val);
4718
4719     case SSA_NAME:
4720     case VALUE_HANDLE:
4721       /* we can just compare by pointer.  */
4722       return iterative_hash_pointer (t, val);
4723
4724     case TREE_LIST:
4725       /* A list of expressions, for a CALL_EXPR or as the elements of a
4726          VECTOR_CST.  */
4727       for (; t; t = TREE_CHAIN (t))
4728         val = iterative_hash_expr (TREE_VALUE (t), val);
4729       return val;
4730     case CONSTRUCTOR:
4731       {
4732         unsigned HOST_WIDE_INT idx;
4733         tree field, value;
4734         FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (t), idx, field, value)
4735           {
4736             val = iterative_hash_expr (field, val);
4737             val = iterative_hash_expr (value, val);
4738           }
4739         return val;
4740       }
4741     case FUNCTION_DECL:
4742       /* When referring to a built-in FUNCTION_DECL, use the
4743          __builtin__ form.  Otherwise nodes that compare equal
4744          according to operand_equal_p might get different
4745          hash codes.  */
4746       if (DECL_BUILT_IN (t))
4747         {
4748           val = iterative_hash_pointer (built_in_decls[DECL_FUNCTION_CODE (t)],
4749                                       val);
4750           return val;
4751         }
4752       /* else FALL THROUGH */
4753     default:
4754       class = TREE_CODE_CLASS (code);
4755
4756       if (class == tcc_declaration)
4757         {
4758           /* Otherwise, we can just compare decls by pointer.  */
4759           val = iterative_hash_pointer (t, val);
4760         }
4761       else
4762         {
4763           gcc_assert (IS_EXPR_CODE_CLASS (class));
4764
4765           val = iterative_hash_object (code, val);
4766
4767           /* Don't hash the type, that can lead to having nodes which
4768              compare equal according to operand_equal_p, but which
4769              have different hash codes.  */
4770           if (code == NOP_EXPR
4771               || code == CONVERT_EXPR
4772               || code == NON_LVALUE_EXPR)
4773             {
4774               /* Make sure to include signness in the hash computation.  */
4775               val += TYPE_UNSIGNED (TREE_TYPE (t));
4776               val = iterative_hash_expr (TREE_OPERAND (t, 0), val);
4777             }
4778
4779           else if (commutative_tree_code (code))
4780             {
4781               /* It's a commutative expression.  We want to hash it the same
4782                  however it appears.  We do this by first hashing both operands
4783                  and then rehashing based on the order of their independent
4784                  hashes.  */
4785               hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
4786               hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0);
4787               hashval_t t;
4788
4789               if (one > two)
4790                 t = one, one = two, two = t;
4791
4792               val = iterative_hash_hashval_t (one, val);
4793               val = iterative_hash_hashval_t (two, val);
4794             }
4795           else
4796             for (i = TREE_CODE_LENGTH (code) - 1; i >= 0; --i)
4797               val = iterative_hash_expr (TREE_OPERAND (t, i), val);
4798         }
4799       return val;
4800       break;
4801     }
4802 }
4803 \f
4804 /* Constructors for pointer, array and function types.
4805    (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
4806    constructed by language-dependent code, not here.)  */
4807
4808 /* Construct, lay out and return the type of pointers to TO_TYPE with
4809    mode MODE.  If CAN_ALIAS_ALL is TRUE, indicate this type can
4810    reference all of memory. If such a type has already been
4811    constructed, reuse it.  */
4812
4813 tree
4814 build_pointer_type_for_mode (tree to_type, enum machine_mode mode,
4815                              bool can_alias_all)
4816 {
4817   tree t;
4818
4819   if (to_type == error_mark_node)
4820     return error_mark_node;
4821
4822   /* In some cases, languages will have things that aren't a POINTER_TYPE
4823      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_POINTER_TO.
4824      In that case, return that type without regard to the rest of our
4825      operands.
4826
4827      ??? This is a kludge, but consistent with the way this function has
4828      always operated and there doesn't seem to be a good way to avoid this
4829      at the moment.  */
4830   if (TYPE_POINTER_TO (to_type) != 0
4831       && TREE_CODE (TYPE_POINTER_TO (to_type)) != POINTER_TYPE)
4832     return TYPE_POINTER_TO (to_type);
4833
4834   /* First, if we already have an unqualified type for pointers to TO_TYPE
4835      and it's the proper mode, use it.  */
4836   for (t = TYPE_POINTER_TO (to_type); t; t = TYPE_NEXT_PTR_TO (t))
4837     if (TYPE_MODE (t) == mode
4838         && !TYPE_QUALS (t)
4839         && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4840       return t;
4841
4842   t = make_node (POINTER_TYPE);
4843
4844   TREE_TYPE (t) = to_type;
4845   TYPE_MODE (t) = mode;
4846   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4847   TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
4848   TYPE_POINTER_TO (to_type) = t;
4849
4850   /* Lay out the type.  This function has many callers that are concerned
4851      with expression-construction, and this simplifies them all.  */
4852   layout_type (t);
4853
4854   return t;
4855 }
4856
4857 /* By default build pointers in ptr_mode.  */
4858
4859 tree
4860 build_pointer_type (tree to_type)
4861 {
4862   return build_pointer_type_for_mode (to_type, ptr_mode, false);
4863 }
4864
4865 /* Same as build_pointer_type_for_mode, but for REFERENCE_TYPE.  */
4866
4867 tree
4868 build_reference_type_for_mode (tree to_type, enum machine_mode mode,
4869                                bool can_alias_all)
4870 {
4871   tree t;
4872
4873   /* In some cases, languages will have things that aren't a REFERENCE_TYPE
4874      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_REFERENCE_TO.
4875      In that case, return that type without regard to the rest of our
4876      operands.
4877
4878      ??? This is a kludge, but consistent with the way this function has
4879      always operated and there doesn't seem to be a good way to avoid this
4880      at the moment.  */
4881   if (TYPE_REFERENCE_TO (to_type) != 0
4882       && TREE_CODE (TYPE_REFERENCE_TO (to_type)) != REFERENCE_TYPE)
4883     return TYPE_REFERENCE_TO (to_type);
4884
4885   /* First, if we already have an unqualified type for references to TO_TYPE
4886      and it's the proper mode, use it.  */
4887   for (t = TYPE_REFERENCE_TO (to_type); t; t = TYPE_NEXT_REF_TO (t))
4888     if (TYPE_MODE (t) == mode
4889         && !TYPE_QUALS (t)
4890         && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4891       return t;
4892
4893   t = make_node (REFERENCE_TYPE);
4894
4895   TREE_TYPE (t) = to_type;
4896   TYPE_MODE (t) = mode;
4897   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4898   TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
4899   TYPE_REFERENCE_TO (to_type) = t;
4900
4901   layout_type (t);
4902
4903   return t;
4904 }
4905
4906
4907 /* Build the node for the type of references-to-TO_TYPE by default
4908    in ptr_mode.  */
4909
4910 tree
4911 build_reference_type (tree to_type)
4912 {
4913   return build_reference_type_for_mode (to_type, ptr_mode, false);
4914 }
4915
4916 /* Build a type that is compatible with t but has no cv quals anywhere
4917    in its type, thus
4918
4919    const char *const *const *  ->  char ***.  */
4920
4921 tree
4922 build_type_no_quals (tree t)
4923 {
4924   switch (TREE_CODE (t))
4925     {
4926     case POINTER_TYPE:
4927       return build_pointer_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4928                                           TYPE_MODE (t),
4929                                           TYPE_REF_CAN_ALIAS_ALL (t));
4930     case REFERENCE_TYPE:
4931       return
4932         build_reference_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4933                                        TYPE_MODE (t),
4934                                        TYPE_REF_CAN_ALIAS_ALL (t));
4935     default:
4936       return TYPE_MAIN_VARIANT (t);
4937     }
4938 }
4939
4940 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
4941    MAXVAL should be the maximum value in the domain
4942    (one less than the length of the array).
4943
4944    The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
4945    We don't enforce this limit, that is up to caller (e.g. language front end).
4946    The limit exists because the result is a signed type and we don't handle
4947    sizes that use more than one HOST_WIDE_INT.  */
4948
4949 tree
4950 build_index_type (tree maxval)
4951 {
4952   tree itype = make_node (INTEGER_TYPE);
4953
4954   TREE_TYPE (itype) = sizetype;
4955   TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
4956   TYPE_MIN_VALUE (itype) = size_zero_node;
4957   TYPE_MAX_VALUE (itype) = fold_convert (sizetype, maxval);
4958   TYPE_MODE (itype) = TYPE_MODE (sizetype);
4959   TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
4960   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
4961   TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
4962   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
4963
4964   if (host_integerp (maxval, 1))
4965     return type_hash_canon (tree_low_cst (maxval, 1), itype);
4966   else
4967     return itype;
4968 }
4969
4970 /* Builds a signed or unsigned integer type of precision PRECISION.
4971    Used for C bitfields whose precision does not match that of
4972    built-in target types.  */
4973 tree
4974 build_nonstandard_integer_type (unsigned HOST_WIDE_INT precision,
4975                                 int unsignedp)
4976 {
4977   tree itype = make_node (INTEGER_TYPE);
4978
4979   TYPE_PRECISION (itype) = precision;
4980
4981   if (unsignedp)
4982     fixup_unsigned_type (itype);
4983   else
4984     fixup_signed_type (itype);
4985
4986   if (host_integerp (TYPE_MAX_VALUE (itype), 1))
4987     return type_hash_canon (tree_low_cst (TYPE_MAX_VALUE (itype), 1), itype);
4988
4989   return itype;
4990 }
4991
4992 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
4993    ENUMERAL_TYPE, BOOLEAN_TYPE, or CHAR_TYPE), with
4994    low bound LOWVAL and high bound HIGHVAL.
4995    if TYPE==NULL_TREE, sizetype is used.  */
4996
4997 tree
4998 build_range_type (tree type, tree lowval, tree highval)
4999 {
5000   tree itype = make_node (INTEGER_TYPE);
5001
5002   TREE_TYPE (itype) = type;
5003   if (type == NULL_TREE)
5004     type = sizetype;
5005
5006   TYPE_MIN_VALUE (itype) = convert (type, lowval);
5007   TYPE_MAX_VALUE (itype) = highval ? convert (type, highval) : NULL;
5008
5009   TYPE_PRECISION (itype) = TYPE_PRECISION (type);
5010   TYPE_MODE (itype) = TYPE_MODE (type);
5011   TYPE_SIZE (itype) = TYPE_SIZE (type);
5012   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type);
5013   TYPE_ALIGN (itype) = TYPE_ALIGN (type);
5014   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type);
5015
5016   if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0))
5017     return type_hash_canon (tree_low_cst (highval, 0)
5018                             - tree_low_cst (lowval, 0),
5019                             itype);
5020   else
5021     return itype;
5022 }
5023
5024 /* Just like build_index_type, but takes lowval and highval instead
5025    of just highval (maxval).  */
5026
5027 tree
5028 build_index_2_type (tree lowval, tree highval)
5029 {
5030   return build_range_type (sizetype, lowval, highval);
5031 }
5032
5033 /* Construct, lay out and return the type of arrays of elements with ELT_TYPE
5034    and number of elements specified by the range of values of INDEX_TYPE.
5035    If such a type has already been constructed, reuse it.  */
5036
5037 tree
5038 build_array_type (tree elt_type, tree index_type)
5039 {
5040   tree t;
5041   hashval_t hashcode = 0;
5042
5043   if (TREE_CODE (elt_type) == FUNCTION_TYPE)
5044     {
5045       error ("arrays of functions are not meaningful");
5046       elt_type = integer_type_node;
5047     }
5048
5049   t = make_node (ARRAY_TYPE);
5050   TREE_TYPE (t) = elt_type;
5051   TYPE_DOMAIN (t) = index_type;
5052
5053   if (index_type == 0)
5054     {
5055       layout_type (t);
5056       return t;
5057     }
5058
5059   hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode);
5060   hashcode = iterative_hash_object (TYPE_HASH (index_type), hashcode);
5061   t = type_hash_canon (hashcode, t);
5062
5063   if (!COMPLETE_TYPE_P (t))
5064     layout_type (t);
5065   return t;
5066 }
5067
5068 /* Return the TYPE of the elements comprising
5069    the innermost dimension of ARRAY.  */
5070
5071 tree
5072 get_inner_array_type (tree array)
5073 {
5074   tree type = TREE_TYPE (array);
5075
5076   while (TREE_CODE (type) == ARRAY_TYPE)
5077     type = TREE_TYPE (type);
5078
5079   return type;
5080 }
5081
5082 /* Construct, lay out and return
5083    the type of functions returning type VALUE_TYPE
5084    given arguments of types ARG_TYPES.
5085    ARG_TYPES is a chain of TREE_LIST nodes whose TREE_VALUEs
5086    are data type nodes for the arguments of the function.
5087    If such a type has already been constructed, reuse it.  */
5088
5089 tree
5090 build_function_type (tree value_type, tree arg_types)
5091 {
5092   tree t;
5093   hashval_t hashcode = 0;
5094
5095   if (TREE_CODE (value_type) == FUNCTION_TYPE)
5096     {
5097       error ("function return type cannot be function");
5098       value_type = integer_type_node;
5099     }
5100
5101   /* Make a node of the sort we want.  */
5102   t = make_node (FUNCTION_TYPE);
5103   TREE_TYPE (t) = value_type;
5104   TYPE_ARG_TYPES (t) = arg_types;
5105
5106   /* If we already have such a type, use the old one.  */
5107   hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode);
5108   hashcode = type_hash_list (arg_types, hashcode);
5109   t = type_hash_canon (hashcode, t);
5110
5111   if (!COMPLETE_TYPE_P (t))
5112     layout_type (t);
5113   return t;
5114 }
5115
5116 /* Build a function type.  The RETURN_TYPE is the type returned by the
5117    function.  If additional arguments are provided, they are
5118    additional argument types.  The list of argument types must always
5119    be terminated by NULL_TREE.  */
5120
5121 tree
5122 build_function_type_list (tree return_type, ...)
5123 {
5124   tree t, args, last;
5125   va_list p;
5126
5127   va_start (p, return_type);
5128
5129   t = va_arg (p, tree);
5130   for (args = NULL_TREE; t != NULL_TREE; t = va_arg (p, tree))
5131     args = tree_cons (NULL_TREE, t, args);
5132
5133   if (args == NULL_TREE)
5134     args = void_list_node;
5135   else
5136     {
5137       last = args;
5138       args = nreverse (args);
5139       TREE_CHAIN (last) = void_list_node;
5140     }
5141   args = build_function_type (return_type, args);
5142
5143   va_end (p);
5144   return args;
5145 }
5146
5147 /* Build a METHOD_TYPE for a member of BASETYPE.  The RETTYPE (a TYPE)
5148    and ARGTYPES (a TREE_LIST) are the return type and arguments types
5149    for the method.  An implicit additional parameter (of type
5150    pointer-to-BASETYPE) is added to the ARGTYPES.  */
5151
5152 tree
5153 build_method_type_directly (tree basetype,
5154                             tree rettype,
5155                             tree argtypes)
5156 {
5157   tree t;
5158   tree ptype;
5159   int hashcode = 0;
5160
5161   /* Make a node of the sort we want.  */
5162   t = make_node (METHOD_TYPE);
5163
5164   TYPE_METHOD_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
5165   TREE_TYPE (t) = rettype;
5166   ptype = build_pointer_type (basetype);
5167
5168   /* The actual arglist for this function includes a "hidden" argument
5169      which is "this".  Put it into the list of argument types.  */
5170   argtypes = tree_cons (NULL_TREE, ptype, argtypes);
5171   TYPE_ARG_TYPES (t) = argtypes;
5172
5173   /* If we already have such a type, use the old one.  */
5174   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
5175   hashcode = iterative_hash_object (TYPE_HASH (rettype), hashcode);
5176   hashcode = type_hash_list (argtypes, hashcode);
5177   t = type_hash_canon (hashcode, t);
5178
5179   if (!COMPLETE_TYPE_P (t))
5180     layout_type (t);
5181
5182   return t;
5183 }
5184
5185 /* Construct, lay out and return the type of methods belonging to class
5186    BASETYPE and whose arguments and values are described by TYPE.
5187    If that type exists already, reuse it.
5188    TYPE must be a FUNCTION_TYPE node.  */
5189
5190 tree
5191 build_method_type (tree basetype, tree type)
5192 {
5193   gcc_assert (TREE_CODE (type) == FUNCTION_TYPE);
5194
5195   return build_method_type_directly (basetype,
5196                                      TREE_TYPE (type),
5197                                      TYPE_ARG_TYPES (type));
5198 }
5199
5200 /* Construct, lay out and return the type of offsets to a value
5201    of type TYPE, within an object of type BASETYPE.
5202    If a suitable offset type exists already, reuse it.  */
5203
5204 tree
5205 build_offset_type (tree basetype, tree type)
5206 {
5207   tree t;
5208   hashval_t hashcode = 0;
5209
5210   /* Make a node of the sort we want.  */
5211   t = make_node (OFFSET_TYPE);
5212
5213   TYPE_OFFSET_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
5214   TREE_TYPE (t) = type;
5215
5216   /* If we already have such a type, use the old one.  */
5217   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
5218   hashcode = iterative_hash_object (TYPE_HASH (type), hashcode);
5219   t = type_hash_canon (hashcode, t);
5220
5221   if (!COMPLETE_TYPE_P (t))
5222     layout_type (t);
5223
5224   return t;
5225 }
5226
5227 /* Create a complex type whose components are COMPONENT_TYPE.  */
5228
5229 tree
5230 build_complex_type (tree component_type)
5231 {
5232   tree t;
5233   hashval_t hashcode;
5234
5235   /* Make a node of the sort we want.  */
5236   t = make_node (COMPLEX_TYPE);
5237
5238   TREE_TYPE (t) = TYPE_MAIN_VARIANT (component_type);
5239
5240   /* If we already have such a type, use the old one.  */
5241   hashcode = iterative_hash_object (TYPE_HASH (component_type), 0);
5242   t = type_hash_canon (hashcode, t);
5243
5244   if (!COMPLETE_TYPE_P (t))
5245     layout_type (t);
5246
5247   /* If we are writing Dwarf2 output we need to create a name,
5248      since complex is a fundamental type.  */
5249   if ((write_symbols == DWARF2_DEBUG || write_symbols == VMS_AND_DWARF2_DEBUG)
5250       && ! TYPE_NAME (t))
5251     {
5252       const char *name;
5253       if (component_type == char_type_node)
5254         name = "complex char";
5255       else if (component_type == signed_char_type_node)
5256         name = "complex signed char";
5257       else if (component_type == unsigned_char_type_node)
5258         name = "complex unsigned char";
5259       else if (component_type == short_integer_type_node)
5260         name = "complex short int";
5261       else if (component_type == short_unsigned_type_node)
5262         name = "complex short unsigned int";
5263       else if (component_type == integer_type_node)
5264         name = "complex int";
5265       else if (component_type == unsigned_type_node)
5266         name = "complex unsigned int";
5267       else if (component_type == long_integer_type_node)
5268         name = "complex long int";
5269       else if (component_type == long_unsigned_type_node)
5270         name = "complex long unsigned int";
5271       else if (component_type == long_long_integer_type_node)
5272         name = "complex long long int";
5273       else if (component_type == long_long_unsigned_type_node)
5274         name = "complex long long unsigned int";
5275       else
5276         name = 0;
5277
5278       if (name != 0)
5279         TYPE_NAME (t) = get_identifier (name);
5280     }
5281
5282   return build_qualified_type (t, TYPE_QUALS (component_type));
5283 }
5284 \f
5285 /* Return OP, stripped of any conversions to wider types as much as is safe.
5286    Converting the value back to OP's type makes a value equivalent to OP.
5287
5288    If FOR_TYPE is nonzero, we return a value which, if converted to
5289    type FOR_TYPE, would be equivalent to converting OP to type FOR_TYPE.
5290
5291    If FOR_TYPE is nonzero, unaligned bit-field references may be changed to the
5292    narrowest type that can hold the value, even if they don't exactly fit.
5293    Otherwise, bit-field references are changed to a narrower type
5294    only if they can be fetched directly from memory in that type.
5295
5296    OP must have integer, real or enumeral type.  Pointers are not allowed!
5297
5298    There are some cases where the obvious value we could return
5299    would regenerate to OP if converted to OP's type,
5300    but would not extend like OP to wider types.
5301    If FOR_TYPE indicates such extension is contemplated, we eschew such values.
5302    For example, if OP is (unsigned short)(signed char)-1,
5303    we avoid returning (signed char)-1 if FOR_TYPE is int,
5304    even though extending that to an unsigned short would regenerate OP,
5305    since the result of extending (signed char)-1 to (int)
5306    is different from (int) OP.  */
5307
5308 tree
5309 get_unwidened (tree op, tree for_type)
5310 {
5311   /* Set UNS initially if converting OP to FOR_TYPE is a zero-extension.  */
5312   tree type = TREE_TYPE (op);
5313   unsigned final_prec
5314     = TYPE_PRECISION (for_type != 0 ? for_type : type);
5315   int uns
5316     = (for_type != 0 && for_type != type
5317        && final_prec > TYPE_PRECISION (type)
5318        && TYPE_UNSIGNED (type));
5319   tree win = op;
5320
5321   while (TREE_CODE (op) == NOP_EXPR
5322          || TREE_CODE (op) == CONVERT_EXPR)
5323     {
5324       int bitschange;
5325
5326       /* TYPE_PRECISION on vector types has different meaning
5327          (TYPE_VECTOR_SUBPARTS) and casts from vectors are view conversions,
5328          so avoid them here.  */
5329       if (TREE_CODE (TREE_TYPE (TREE_OPERAND (op, 0))) == VECTOR_TYPE)
5330         break;
5331
5332       bitschange = TYPE_PRECISION (TREE_TYPE (op))
5333                    - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0)));
5334
5335       /* Truncations are many-one so cannot be removed.
5336          Unless we are later going to truncate down even farther.  */
5337       if (bitschange < 0
5338           && final_prec > TYPE_PRECISION (TREE_TYPE (op)))
5339         break;
5340
5341       /* See what's inside this conversion.  If we decide to strip it,
5342          we will set WIN.  */
5343       op = TREE_OPERAND (op, 0);
5344
5345       /* If we have not stripped any zero-extensions (uns is 0),
5346          we can strip any kind of extension.
5347          If we have previously stripped a zero-extension,
5348          only zero-extensions can safely be stripped.
5349          Any extension can be stripped if the bits it would produce
5350          are all going to be discarded later by truncating to FOR_TYPE.  */
5351
5352       if (bitschange > 0)
5353         {
5354           if (! uns || final_prec <= TYPE_PRECISION (TREE_TYPE (op)))
5355             win = op;
5356           /* TYPE_UNSIGNED says whether this is a zero-extension.
5357              Let's avoid computing it if it does not affect WIN
5358              and if UNS will not be needed again.  */
5359           if ((uns
5360                || TREE_CODE (op) == NOP_EXPR
5361                || TREE_CODE (op) == CONVERT_EXPR)
5362               && TYPE_UNSIGNED (TREE_TYPE (op)))
5363             {
5364               uns = 1;
5365               win = op;
5366             }
5367         }
5368     }
5369
5370   if (TREE_CODE (op) == COMPONENT_REF
5371       /* Since type_for_size always gives an integer type.  */
5372       && TREE_CODE (type) != REAL_TYPE
5373       /* Don't crash if field not laid out yet.  */
5374       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
5375       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
5376     {
5377       unsigned int innerprec
5378         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
5379       int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
5380                        || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
5381       type = lang_hooks.types.type_for_size (innerprec, unsignedp);
5382
5383       /* We can get this structure field in the narrowest type it fits in.
5384          If FOR_TYPE is 0, do this only for a field that matches the
5385          narrower type exactly and is aligned for it
5386          The resulting extension to its nominal type (a fullword type)
5387          must fit the same conditions as for other extensions.  */
5388
5389       if (type != 0
5390           && INT_CST_LT_UNSIGNED (TYPE_SIZE (type), TYPE_SIZE (TREE_TYPE (op)))
5391           && (for_type || ! DECL_BIT_FIELD (TREE_OPERAND (op, 1)))
5392           && (! uns || final_prec <= innerprec || unsignedp))
5393         {
5394           win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
5395                         TREE_OPERAND (op, 1), NULL_TREE);
5396           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
5397           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
5398         }
5399     }
5400
5401   return win;
5402 }
5403 \f
5404 /* Return OP or a simpler expression for a narrower value
5405    which can be sign-extended or zero-extended to give back OP.
5406    Store in *UNSIGNEDP_PTR either 1 if the value should be zero-extended
5407    or 0 if the value should be sign-extended.  */
5408
5409 tree
5410 get_narrower (tree op, int *unsignedp_ptr)
5411 {
5412   int uns = 0;
5413   int first = 1;
5414   tree win = op;
5415   bool integral_p = INTEGRAL_TYPE_P (TREE_TYPE (op));
5416
5417   while (TREE_CODE (op) == NOP_EXPR)
5418     {
5419       int bitschange
5420         = (TYPE_PRECISION (TREE_TYPE (op))
5421            - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0))));
5422
5423       /* Truncations are many-one so cannot be removed.  */
5424       if (bitschange < 0)
5425         break;
5426
5427       /* See what's inside this conversion.  If we decide to strip it,
5428          we will set WIN.  */
5429
5430       if (bitschange > 0)
5431         {
5432           op = TREE_OPERAND (op, 0);
5433           /* An extension: the outermost one can be stripped,
5434              but remember whether it is zero or sign extension.  */
5435           if (first)
5436             uns = TYPE_UNSIGNED (TREE_TYPE (op));
5437           /* Otherwise, if a sign extension has been stripped,
5438              only sign extensions can now be stripped;
5439              if a zero extension has been stripped, only zero-extensions.  */
5440           else if (uns != TYPE_UNSIGNED (TREE_TYPE (op)))
5441             break;
5442           first = 0;
5443         }
5444       else /* bitschange == 0 */
5445         {
5446           /* A change in nominal type can always be stripped, but we must
5447              preserve the unsignedness.  */
5448           if (first)
5449             uns = TYPE_UNSIGNED (TREE_TYPE (op));
5450           first = 0;
5451           op = TREE_OPERAND (op, 0);
5452           /* Keep trying to narrow, but don't assign op to win if it
5453              would turn an integral type into something else.  */
5454           if (INTEGRAL_TYPE_P (TREE_TYPE (op)) != integral_p)
5455             continue;
5456         }
5457
5458       win = op;
5459     }
5460
5461   if (TREE_CODE (op) == COMPONENT_REF
5462       /* Since type_for_size always gives an integer type.  */
5463       && TREE_CODE (TREE_TYPE (op)) != REAL_TYPE
5464       /* Ensure field is laid out already.  */
5465       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
5466       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
5467     {
5468       unsigned HOST_WIDE_INT innerprec
5469         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
5470       int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
5471                        || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
5472       tree type = lang_hooks.types.type_for_size (innerprec, unsignedp);
5473
5474       /* We can get this structure field in a narrower type that fits it,
5475          but the resulting extension to its nominal type (a fullword type)
5476          must satisfy the same conditions as for other extensions.
5477
5478          Do this only for fields that are aligned (not bit-fields),
5479          because when bit-field insns will be used there is no
5480          advantage in doing this.  */
5481
5482       if (innerprec < TYPE_PRECISION (TREE_TYPE (op))
5483           && ! DECL_BIT_FIELD (TREE_OPERAND (op, 1))
5484           && (first || uns == DECL_UNSIGNED (TREE_OPERAND (op, 1)))
5485           && type != 0)
5486         {
5487           if (first)
5488             uns = DECL_UNSIGNED (TREE_OPERAND (op, 1));
5489           win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
5490                         TREE_OPERAND (op, 1), NULL_TREE);
5491           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
5492           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
5493         }
5494     }
5495   *unsignedp_ptr = uns;
5496   return win;
5497 }
5498 \f
5499 /* Nonzero if integer constant C has a value that is permissible
5500    for type TYPE (an INTEGER_TYPE).  */
5501
5502 int
5503 int_fits_type_p (tree c, tree type)
5504 {
5505   tree type_low_bound = TYPE_MIN_VALUE (type);
5506   tree type_high_bound = TYPE_MAX_VALUE (type);
5507   bool ok_for_low_bound, ok_for_high_bound;
5508   tree tmp;
5509
5510   /* If at least one bound of the type is a constant integer, we can check
5511      ourselves and maybe make a decision. If no such decision is possible, but
5512      this type is a subtype, try checking against that.  Otherwise, use
5513      force_fit_type, which checks against the precision.
5514
5515      Compute the status for each possibly constant bound, and return if we see
5516      one does not match. Use ok_for_xxx_bound for this purpose, assigning -1
5517      for "unknown if constant fits", 0 for "constant known *not* to fit" and 1
5518      for "constant known to fit".  */
5519
5520   /* Check if C >= type_low_bound.  */
5521   if (type_low_bound && TREE_CODE (type_low_bound) == INTEGER_CST)
5522     {
5523       if (tree_int_cst_lt (c, type_low_bound))
5524         return 0;
5525       ok_for_low_bound = true;
5526     }
5527   else
5528     ok_for_low_bound = false;
5529
5530   /* Check if c <= type_high_bound.  */
5531   if (type_high_bound && TREE_CODE (type_high_bound) == INTEGER_CST)
5532     {
5533       if (tree_int_cst_lt (type_high_bound, c))
5534         return 0;
5535       ok_for_high_bound = true;
5536     }
5537   else
5538     ok_for_high_bound = false;
5539
5540   /* If the constant fits both bounds, the result is known.  */
5541   if (ok_for_low_bound && ok_for_high_bound)
5542     return 1;
5543
5544   /* Perform some generic filtering which may allow making a decision
5545      even if the bounds are not constant.  First, negative integers
5546      never fit in unsigned types, */
5547   if (TYPE_UNSIGNED (type) && tree_int_cst_sgn (c) < 0)
5548     return 0;
5549
5550   /* Second, narrower types always fit in wider ones.  */
5551   if (TYPE_PRECISION (type) > TYPE_PRECISION (TREE_TYPE (c)))
5552     return 1;
5553
5554   /* Third, unsigned integers with top bit set never fit signed types.  */
5555   if (! TYPE_UNSIGNED (type)
5556       && TYPE_UNSIGNED (TREE_TYPE (c))
5557       && tree_int_cst_msb (c))
5558     return 0;
5559
5560   /* If we haven't been able to decide at this point, there nothing more we
5561      can check ourselves here.  Look at the base type if we have one and it
5562      has the same precision.  */
5563   if (TREE_CODE (type) == INTEGER_TYPE
5564       && TREE_TYPE (type) != 0
5565       && TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (type)))
5566     return int_fits_type_p (c, TREE_TYPE (type));
5567
5568   /* Or to force_fit_type, if nothing else.  */
5569   tmp = copy_node (c);
5570   TREE_TYPE (tmp) = type;
5571   tmp = force_fit_type (tmp, -1, false, false);
5572   return TREE_INT_CST_HIGH (tmp) == TREE_INT_CST_HIGH (c)
5573          && TREE_INT_CST_LOW (tmp) == TREE_INT_CST_LOW (c);
5574 }
5575
5576 /* Subprogram of following function.  Called by walk_tree.
5577
5578    Return *TP if it is an automatic variable or parameter of the
5579    function passed in as DATA.  */
5580
5581 static tree
5582 find_var_from_fn (tree *tp, int *walk_subtrees, void *data)
5583 {
5584   tree fn = (tree) data;
5585
5586   if (TYPE_P (*tp))
5587     *walk_subtrees = 0;
5588
5589   else if (DECL_P (*tp)
5590            && lang_hooks.tree_inlining.auto_var_in_fn_p (*tp, fn))
5591     return *tp;
5592
5593   return NULL_TREE;
5594 }
5595
5596 /* Returns true if T is, contains, or refers to a type with variable
5597    size.  If FN is nonzero, only return true if a modifier of the type
5598    or position of FN is a variable or parameter inside FN.
5599
5600    This concept is more general than that of C99 'variably modified types':
5601    in C99, a struct type is never variably modified because a VLA may not
5602    appear as a structure member.  However, in GNU C code like:
5603
5604      struct S { int i[f()]; };
5605
5606    is valid, and other languages may define similar constructs.  */
5607
5608 bool
5609 variably_modified_type_p (tree type, tree fn)
5610 {
5611   tree t;
5612
5613 /* Test if T is either variable (if FN is zero) or an expression containing
5614    a variable in FN.  */
5615 #define RETURN_TRUE_IF_VAR(T)                                           \
5616   do { tree _t = (T);                                                   \
5617     if (_t && _t != error_mark_node && TREE_CODE (_t) != INTEGER_CST    \
5618         && (!fn || walk_tree (&_t, find_var_from_fn, fn, NULL)))        \
5619       return true;  } while (0)
5620
5621   if (type == error_mark_node)
5622     return false;
5623
5624   /* If TYPE itself has variable size, it is variably modified.
5625
5626      We do not yet have a representation of the C99 '[*]' syntax.
5627      When a representation is chosen, this function should be modified
5628      to test for that case as well.  */
5629   RETURN_TRUE_IF_VAR (TYPE_SIZE (type));
5630   RETURN_TRUE_IF_VAR (TYPE_SIZE_UNIT(type));
5631
5632   switch (TREE_CODE (type))
5633     {
5634     case POINTER_TYPE:
5635     case REFERENCE_TYPE:
5636     case ARRAY_TYPE:
5637     case VECTOR_TYPE:
5638       if (variably_modified_type_p (TREE_TYPE (type), fn))
5639         return true;
5640       break;
5641
5642     case FUNCTION_TYPE:
5643     case METHOD_TYPE:
5644       /* If TYPE is a function type, it is variably modified if any of the
5645          parameters or the return type are variably modified.  */
5646       if (variably_modified_type_p (TREE_TYPE (type), fn))
5647           return true;
5648
5649       for (t = TYPE_ARG_TYPES (type);
5650            t && t != void_list_node;
5651            t = TREE_CHAIN (t))
5652         if (variably_modified_type_p (TREE_VALUE (t), fn))
5653           return true;
5654       break;
5655
5656     case INTEGER_TYPE:
5657     case REAL_TYPE:
5658     case ENUMERAL_TYPE:
5659     case BOOLEAN_TYPE:
5660     case CHAR_TYPE:
5661       /* Scalar types are variably modified if their end points
5662          aren't constant.  */
5663       RETURN_TRUE_IF_VAR (TYPE_MIN_VALUE (type));
5664       RETURN_TRUE_IF_VAR (TYPE_MAX_VALUE (type));
5665       break;
5666
5667     case RECORD_TYPE:
5668     case UNION_TYPE:
5669     case QUAL_UNION_TYPE:
5670       /* We can't see if any of the field are variably-modified by the
5671          definition we normally use, since that would produce infinite
5672          recursion via pointers.  */
5673       /* This is variably modified if some field's type is.  */
5674       for (t = TYPE_FIELDS (type); t; t = TREE_CHAIN (t))
5675         if (TREE_CODE (t) == FIELD_DECL)
5676           {
5677             RETURN_TRUE_IF_VAR (DECL_FIELD_OFFSET (t));
5678             RETURN_TRUE_IF_VAR (DECL_SIZE (t));
5679             RETURN_TRUE_IF_VAR (DECL_SIZE_UNIT (t));
5680
5681             if (TREE_CODE (type) == QUAL_UNION_TYPE)
5682               RETURN_TRUE_IF_VAR (DECL_QUALIFIER (t));
5683           }
5684         break;
5685
5686     default:
5687       break;
5688     }
5689
5690   /* The current language may have other cases to check, but in general,
5691      all other types are not variably modified.  */
5692   return lang_hooks.tree_inlining.var_mod_type_p (type, fn);
5693
5694 #undef RETURN_TRUE_IF_VAR
5695 }
5696
5697 /* Given a DECL or TYPE, return the scope in which it was declared, or
5698    NULL_TREE if there is no containing scope.  */
5699
5700 tree
5701 get_containing_scope (tree t)
5702 {
5703   return (TYPE_P (t) ? TYPE_CONTEXT (t) : DECL_CONTEXT (t));
5704 }
5705
5706 /* Return the innermost context enclosing DECL that is
5707    a FUNCTION_DECL, or zero if none.  */
5708
5709 tree
5710 decl_function_context (tree decl)
5711 {
5712   tree context;
5713
5714   if (TREE_CODE (decl) == ERROR_MARK)
5715     return 0;
5716
5717   /* C++ virtual functions use DECL_CONTEXT for the class of the vtable
5718      where we look up the function at runtime.  Such functions always take
5719      a first argument of type 'pointer to real context'.
5720
5721      C++ should really be fixed to use DECL_CONTEXT for the real context,
5722      and use something else for the "virtual context".  */
5723   else if (TREE_CODE (decl) == FUNCTION_DECL && DECL_VINDEX (decl))
5724     context
5725       = TYPE_MAIN_VARIANT
5726         (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (decl)))));
5727   else
5728     context = DECL_CONTEXT (decl);
5729
5730   while (context && TREE_CODE (context) != FUNCTION_DECL)
5731     {
5732       if (TREE_CODE (context) == BLOCK)
5733         context = BLOCK_SUPERCONTEXT (context);
5734       else
5735         context = get_containing_scope (context);
5736     }
5737
5738   return context;
5739 }
5740
5741 /* Return the innermost context enclosing DECL that is
5742    a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE, or zero if none.
5743    TYPE_DECLs and FUNCTION_DECLs are transparent to this function.  */
5744
5745 tree
5746 decl_type_context (tree decl)
5747 {
5748   tree context = DECL_CONTEXT (decl);
5749
5750   while (context)
5751     switch (TREE_CODE (context))
5752       {
5753       case NAMESPACE_DECL:
5754       case TRANSLATION_UNIT_DECL:
5755         return NULL_TREE;
5756
5757       case RECORD_TYPE:
5758       case UNION_TYPE:
5759       case QUAL_UNION_TYPE:
5760         return context;
5761
5762       case TYPE_DECL:
5763       case FUNCTION_DECL:
5764         context = DECL_CONTEXT (context);
5765         break;
5766
5767       case BLOCK:
5768         context = BLOCK_SUPERCONTEXT (context);
5769         break;
5770
5771       default:
5772         gcc_unreachable ();
5773       }
5774
5775   return NULL_TREE;
5776 }
5777
5778 /* CALL is a CALL_EXPR.  Return the declaration for the function
5779    called, or NULL_TREE if the called function cannot be
5780    determined.  */
5781
5782 tree
5783 get_callee_fndecl (tree call)
5784 {
5785   tree addr;
5786
5787   /* It's invalid to call this function with anything but a
5788      CALL_EXPR.  */
5789   gcc_assert (TREE_CODE (call) == CALL_EXPR);
5790
5791   /* The first operand to the CALL is the address of the function
5792      called.  */
5793   addr = TREE_OPERAND (call, 0);
5794
5795   STRIP_NOPS (addr);
5796
5797   /* If this is a readonly function pointer, extract its initial value.  */
5798   if (DECL_P (addr) && TREE_CODE (addr) != FUNCTION_DECL
5799       && TREE_READONLY (addr) && ! TREE_THIS_VOLATILE (addr)
5800       && DECL_INITIAL (addr))
5801     addr = DECL_INITIAL (addr);
5802
5803   /* If the address is just `&f' for some function `f', then we know
5804      that `f' is being called.  */
5805   if (TREE_CODE (addr) == ADDR_EXPR
5806       && TREE_CODE (TREE_OPERAND (addr, 0)) == FUNCTION_DECL)
5807     return TREE_OPERAND (addr, 0);
5808
5809   /* We couldn't figure out what was being called.  Maybe the front
5810      end has some idea.  */
5811   return lang_hooks.lang_get_callee_fndecl (call);
5812 }
5813
5814 /* Print debugging information about tree nodes generated during the compile,
5815    and any language-specific information.  */
5816
5817 void
5818 dump_tree_statistics (void)
5819 {
5820 #ifdef GATHER_STATISTICS
5821   int i;
5822   int total_nodes, total_bytes;
5823 #endif
5824
5825   fprintf (stderr, "\n??? tree nodes created\n\n");
5826 #ifdef GATHER_STATISTICS
5827   fprintf (stderr, "Kind                   Nodes      Bytes\n");
5828   fprintf (stderr, "---------------------------------------\n");
5829   total_nodes = total_bytes = 0;
5830   for (i = 0; i < (int) all_kinds; i++)
5831     {
5832       fprintf (stderr, "%-20s %7d %10d\n", tree_node_kind_names[i],
5833                tree_node_counts[i], tree_node_sizes[i]);
5834       total_nodes += tree_node_counts[i];
5835       total_bytes += tree_node_sizes[i];
5836     }
5837   fprintf (stderr, "---------------------------------------\n");
5838   fprintf (stderr, "%-20s %7d %10d\n", "Total", total_nodes, total_bytes);
5839   fprintf (stderr, "---------------------------------------\n");
5840   ssanames_print_statistics ();
5841   phinodes_print_statistics ();
5842 #else
5843   fprintf (stderr, "(No per-node statistics)\n");
5844 #endif
5845   print_type_hash_statistics ();
5846   print_debug_expr_statistics ();
5847   print_value_expr_statistics ();
5848   print_restrict_base_statistics ();
5849   lang_hooks.print_statistics ();
5850 }
5851 \f
5852 #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
5853
5854 /* Generate a crc32 of a string.  */
5855
5856 unsigned
5857 crc32_string (unsigned chksum, const char *string)
5858 {
5859   do
5860     {
5861       unsigned value = *string << 24;
5862       unsigned ix;
5863
5864       for (ix = 8; ix--; value <<= 1)
5865         {
5866           unsigned feedback;
5867
5868           feedback = (value ^ chksum) & 0x80000000 ? 0x04c11db7 : 0;
5869           chksum <<= 1;
5870           chksum ^= feedback;
5871         }
5872     }
5873   while (*string++);
5874   return chksum;
5875 }
5876
5877 /* P is a string that will be used in a symbol.  Mask out any characters
5878    that are not valid in that context.  */
5879
5880 void
5881 clean_symbol_name (char *p)
5882 {
5883   for (; *p; p++)
5884     if (! (ISALNUM (*p)
5885 #ifndef NO_DOLLAR_IN_LABEL      /* this for `$'; unlikely, but... -- kr */
5886             || *p == '$'
5887 #endif
5888 #ifndef NO_DOT_IN_LABEL         /* this for `.'; unlikely, but...  */
5889             || *p == '.'
5890 #endif
5891            ))
5892       *p = '_';
5893 }
5894
5895 /* Generate a name for a function unique to this translation unit.
5896    TYPE is some string to identify the purpose of this function to the
5897    linker or collect2.  */
5898
5899 tree
5900 get_file_function_name_long (const char *type)
5901 {
5902   char *buf;
5903   const char *p;
5904   char *q;
5905
5906   if (first_global_object_name)
5907     p = first_global_object_name;
5908   else
5909     {
5910       /* We don't have anything that we know to be unique to this translation
5911          unit, so use what we do have and throw in some randomness.  */
5912       unsigned len;
5913       const char *name = weak_global_object_name;
5914       const char *file = main_input_filename;
5915
5916       if (! name)
5917         name = "";
5918       if (! file)
5919         file = input_filename;
5920
5921       len = strlen (file);
5922       q = alloca (9 * 2 + len + 1);
5923       memcpy (q, file, len + 1);
5924       clean_symbol_name (q);
5925
5926       sprintf (q + len, "_%08X_%08X", crc32_string (0, name),
5927                crc32_string (0, flag_random_seed));
5928
5929       p = q;
5930     }
5931
5932   buf = alloca (sizeof (FILE_FUNCTION_FORMAT) + strlen (p) + strlen (type));
5933
5934   /* Set up the name of the file-level functions we may need.
5935      Use a global object (which is already required to be unique over
5936      the program) rather than the file name (which imposes extra
5937      constraints).  */
5938   sprintf (buf, FILE_FUNCTION_FORMAT, type, p);
5939
5940   return get_identifier (buf);
5941 }
5942
5943 /* If KIND=='I', return a suitable global initializer (constructor) name.
5944    If KIND=='D', return a suitable global clean-up (destructor) name.  */
5945
5946 tree
5947 get_file_function_name (int kind)
5948 {
5949   char p[2];
5950
5951   p[0] = kind;
5952   p[1] = 0;
5953
5954   return get_file_function_name_long (p);
5955 }
5956 \f
5957 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
5958
5959 /* Complain that the tree code of NODE does not match the expected 0
5960    terminated list of trailing codes. The trailing code list can be
5961    empty, for a more vague error message.  FILE, LINE, and FUNCTION
5962    are of the caller.  */
5963
5964 void
5965 tree_check_failed (const tree node, const char *file,
5966                    int line, const char *function, ...)
5967 {
5968   va_list args;
5969   char *buffer;
5970   unsigned length = 0;
5971   int code;
5972
5973   va_start (args, function);
5974   while ((code = va_arg (args, int)))
5975     length += 4 + strlen (tree_code_name[code]);
5976   va_end (args);
5977   if (length)
5978     {
5979       va_start (args, function);
5980       length += strlen ("expected ");
5981       buffer = alloca (length);
5982       length = 0;
5983       while ((code = va_arg (args, int)))
5984         {
5985           const char *prefix = length ? " or " : "expected ";
5986
5987           strcpy (buffer + length, prefix);
5988           length += strlen (prefix);
5989           strcpy (buffer + length, tree_code_name[code]);
5990           length += strlen (tree_code_name[code]);
5991         }
5992       va_end (args);
5993     }
5994   else
5995     buffer = (char *)"unexpected node";
5996
5997   internal_error ("tree check: %s, have %s in %s, at %s:%d",
5998                   buffer, tree_code_name[TREE_CODE (node)],
5999                   function, trim_filename (file), line);
6000 }
6001
6002 /* Complain that the tree code of NODE does match the expected 0
6003    terminated list of trailing codes. FILE, LINE, and FUNCTION are of
6004    the caller.  */
6005
6006 void
6007 tree_not_check_failed (const tree node, const char *file,
6008                        int line, const char *function, ...)
6009 {
6010   va_list args;
6011   char *buffer;
6012   unsigned length = 0;
6013   int code;
6014
6015   va_start (args, function);
6016   while ((code = va_arg (args, int)))
6017     length += 4 + strlen (tree_code_name[code]);
6018   va_end (args);
6019   va_start (args, function);
6020   buffer = alloca (length);
6021   length = 0;
6022   while ((code = va_arg (args, int)))
6023     {
6024       if (length)
6025         {
6026           strcpy (buffer + length, " or ");
6027           length += 4;
6028         }
6029       strcpy (buffer + length, tree_code_name[code]);
6030       length += strlen (tree_code_name[code]);
6031     }
6032   va_end (args);
6033
6034   internal_error ("tree check: expected none of %s, have %s in %s, at %s:%d",
6035                   buffer, tree_code_name[TREE_CODE (node)],
6036                   function, trim_filename (file), line);
6037 }
6038
6039 /* Similar to tree_check_failed, except that we check for a class of tree
6040    code, given in CL.  */
6041
6042 void
6043 tree_class_check_failed (const tree node, const enum tree_code_class cl,
6044                          const char *file, int line, const char *function)
6045 {
6046   internal_error
6047     ("tree check: expected class %qs, have %qs (%s) in %s, at %s:%d",
6048      TREE_CODE_CLASS_STRING (cl),
6049      TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))),
6050      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6051 }
6052 #undef DEFTREESTRUCT
6053 #define DEFTREESTRUCT(VAL, NAME) NAME,
6054
6055 static const char *ts_enum_names[] = {
6056 #include "treestruct.def"
6057 };
6058 #undef DEFTREESTRUCT
6059
6060 #define TS_ENUM_NAME(EN) (ts_enum_names[(EN)])
6061
6062 /* Similar to tree_class_check_failed, except that we check for
6063    whether CODE contains the tree structure identified by EN.  */
6064
6065 void
6066 tree_contains_struct_check_failed (const tree node,
6067                                    const enum tree_node_structure_enum en,
6068                                    const char *file, int line,
6069                                    const char *function)
6070 {
6071   internal_error
6072     ("tree check: expected tree that contains %qs structure, have %qs  in %s, at %s:%d",
6073      TS_ENUM_NAME(en),
6074      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6075 }
6076
6077
6078 /* Similar to above, except that the check is for the bounds of a TREE_VEC's
6079    (dynamically sized) vector.  */
6080
6081 void
6082 tree_vec_elt_check_failed (int idx, int len, const char *file, int line,
6083                            const char *function)
6084 {
6085   internal_error
6086     ("tree check: accessed elt %d of tree_vec with %d elts in %s, at %s:%d",
6087      idx + 1, len, function, trim_filename (file), line);
6088 }
6089
6090 /* Similar to above, except that the check is for the bounds of a PHI_NODE's
6091    (dynamically sized) vector.  */
6092
6093 void
6094 phi_node_elt_check_failed (int idx, int len, const char *file, int line,
6095                             const char *function)
6096 {
6097   internal_error
6098     ("tree check: accessed elt %d of phi_node with %d elts in %s, at %s:%d",
6099      idx + 1, len, function, trim_filename (file), line);
6100 }
6101
6102 /* Similar to above, except that the check is for the bounds of the operand
6103    vector of an expression node.  */
6104
6105 void
6106 tree_operand_check_failed (int idx, enum tree_code code, const char *file,
6107                            int line, const char *function)
6108 {
6109   internal_error
6110     ("tree check: accessed operand %d of %s with %d operands in %s, at %s:%d",
6111      idx + 1, tree_code_name[code], TREE_CODE_LENGTH (code),
6112      function, trim_filename (file), line);
6113 }
6114 #endif /* ENABLE_TREE_CHECKING */
6115 \f
6116 /* Create a new vector type node holding SUBPARTS units of type INNERTYPE,
6117    and mapped to the machine mode MODE.  Initialize its fields and build
6118    the information necessary for debugging output.  */
6119
6120 static tree
6121 make_vector_type (tree innertype, int nunits, enum machine_mode mode)
6122 {
6123   tree t = make_node (VECTOR_TYPE);
6124
6125   TREE_TYPE (t) = TYPE_MAIN_VARIANT (innertype);
6126   SET_TYPE_VECTOR_SUBPARTS (t, nunits);
6127   TYPE_MODE (t) = mode;
6128   TYPE_READONLY (t) = TYPE_READONLY (innertype);
6129   TYPE_VOLATILE (t) = TYPE_VOLATILE (innertype);
6130
6131   layout_type (t);
6132
6133   {
6134     tree index = build_int_cst (NULL_TREE, nunits - 1);
6135     tree array = build_array_type (innertype, build_index_type (index));
6136     tree rt = make_node (RECORD_TYPE);
6137
6138     TYPE_FIELDS (rt) = build_decl (FIELD_DECL, get_identifier ("f"), array);
6139     DECL_CONTEXT (TYPE_FIELDS (rt)) = rt;
6140     layout_type (rt);
6141     TYPE_DEBUG_REPRESENTATION_TYPE (t) = rt;
6142     /* In dwarfout.c, type lookup uses TYPE_UID numbers.  We want to output
6143        the representation type, and we want to find that die when looking up
6144        the vector type.  This is most easily achieved by making the TYPE_UID
6145        numbers equal.  */
6146     TYPE_UID (rt) = TYPE_UID (t);
6147   }
6148
6149   /* Build our main variant, based on the main variant of the inner type.  */
6150   if (TYPE_MAIN_VARIANT (innertype) != innertype)
6151     {
6152       tree innertype_main_variant = TYPE_MAIN_VARIANT (innertype);
6153       unsigned int hash = TYPE_HASH (innertype_main_variant);
6154       TYPE_MAIN_VARIANT (t)
6155         = type_hash_canon (hash, make_vector_type (innertype_main_variant,
6156                                                    nunits, mode));
6157     }
6158
6159   return t;
6160 }
6161
6162 static tree
6163 make_or_reuse_type (unsigned size, int unsignedp)
6164 {
6165   if (size == INT_TYPE_SIZE)
6166     return unsignedp ? unsigned_type_node : integer_type_node;
6167   if (size == CHAR_TYPE_SIZE)
6168     return unsignedp ? unsigned_char_type_node : signed_char_type_node;
6169   if (size == SHORT_TYPE_SIZE)
6170     return unsignedp ? short_unsigned_type_node : short_integer_type_node;
6171   if (size == LONG_TYPE_SIZE)
6172     return unsignedp ? long_unsigned_type_node : long_integer_type_node;
6173   if (size == LONG_LONG_TYPE_SIZE)
6174     return (unsignedp ? long_long_unsigned_type_node
6175             : long_long_integer_type_node);
6176
6177   if (unsignedp)
6178     return make_unsigned_type (size);
6179   else
6180     return make_signed_type (size);
6181 }
6182
6183 /* Create nodes for all integer types (and error_mark_node) using the sizes
6184    of C datatypes.  The caller should call set_sizetype soon after calling
6185    this function to select one of the types as sizetype.  */
6186
6187 void
6188 build_common_tree_nodes (bool signed_char, bool signed_sizetype)
6189 {
6190   error_mark_node = make_node (ERROR_MARK);
6191   TREE_TYPE (error_mark_node) = error_mark_node;
6192
6193   initialize_sizetypes (signed_sizetype);
6194
6195   /* Define both `signed char' and `unsigned char'.  */
6196   signed_char_type_node = make_signed_type (CHAR_TYPE_SIZE);
6197   unsigned_char_type_node = make_unsigned_type (CHAR_TYPE_SIZE);
6198
6199   /* Define `char', which is like either `signed char' or `unsigned char'
6200      but not the same as either.  */
6201   char_type_node
6202     = (signed_char
6203        ? make_signed_type (CHAR_TYPE_SIZE)
6204        : make_unsigned_type (CHAR_TYPE_SIZE));
6205
6206   short_integer_type_node = make_signed_type (SHORT_TYPE_SIZE);
6207   short_unsigned_type_node = make_unsigned_type (SHORT_TYPE_SIZE);
6208   integer_type_node = make_signed_type (INT_TYPE_SIZE);
6209   unsigned_type_node = make_unsigned_type (INT_TYPE_SIZE);
6210   long_integer_type_node = make_signed_type (LONG_TYPE_SIZE);
6211   long_unsigned_type_node = make_unsigned_type (LONG_TYPE_SIZE);
6212   long_long_integer_type_node = make_signed_type (LONG_LONG_TYPE_SIZE);
6213   long_long_unsigned_type_node = make_unsigned_type (LONG_LONG_TYPE_SIZE);
6214
6215   /* Define a boolean type.  This type only represents boolean values but
6216      may be larger than char depending on the value of BOOL_TYPE_SIZE.
6217      Front ends which want to override this size (i.e. Java) can redefine
6218      boolean_type_node before calling build_common_tree_nodes_2.  */
6219   boolean_type_node = make_unsigned_type (BOOL_TYPE_SIZE);
6220   TREE_SET_CODE (boolean_type_node, BOOLEAN_TYPE);
6221   TYPE_MAX_VALUE (boolean_type_node) = build_int_cst (boolean_type_node, 1);
6222   TYPE_PRECISION (boolean_type_node) = 1;
6223
6224   /* Fill in the rest of the sized types.  Reuse existing type nodes
6225      when possible.  */
6226   intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 0);
6227   intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 0);
6228   intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 0);
6229   intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 0);
6230   intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 0);
6231
6232   unsigned_intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 1);
6233   unsigned_intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 1);
6234   unsigned_intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 1);
6235   unsigned_intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 1);
6236   unsigned_intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 1);
6237
6238   access_public_node = get_identifier ("public");
6239   access_protected_node = get_identifier ("protected");
6240   access_private_node = get_identifier ("private");
6241 }
6242
6243 /* Call this function after calling build_common_tree_nodes and set_sizetype.
6244    It will create several other common tree nodes.  */
6245
6246 void
6247 build_common_tree_nodes_2 (int short_double)
6248 {
6249   /* Define these next since types below may used them.  */
6250   integer_zero_node = build_int_cst (NULL_TREE, 0);
6251   integer_one_node = build_int_cst (NULL_TREE, 1);
6252   integer_minus_one_node = build_int_cst (NULL_TREE, -1);
6253
6254   size_zero_node = size_int (0);
6255   size_one_node = size_int (1);
6256   bitsize_zero_node = bitsize_int (0);
6257   bitsize_one_node = bitsize_int (1);
6258   bitsize_unit_node = bitsize_int (BITS_PER_UNIT);
6259
6260   boolean_false_node = TYPE_MIN_VALUE (boolean_type_node);
6261   boolean_true_node = TYPE_MAX_VALUE (boolean_type_node);
6262
6263   void_type_node = make_node (VOID_TYPE);
6264   layout_type (void_type_node);
6265
6266   /* We are not going to have real types in C with less than byte alignment,
6267      so we might as well not have any types that claim to have it.  */
6268   TYPE_ALIGN (void_type_node) = BITS_PER_UNIT;
6269   TYPE_USER_ALIGN (void_type_node) = 0;
6270
6271   null_pointer_node = build_int_cst (build_pointer_type (void_type_node), 0);
6272   layout_type (TREE_TYPE (null_pointer_node));
6273
6274   ptr_type_node = build_pointer_type (void_type_node);
6275   const_ptr_type_node
6276     = build_pointer_type (build_type_variant (void_type_node, 1, 0));
6277   fileptr_type_node = ptr_type_node;
6278
6279   float_type_node = make_node (REAL_TYPE);
6280   TYPE_PRECISION (float_type_node) = FLOAT_TYPE_SIZE;
6281   layout_type (float_type_node);
6282
6283   double_type_node = make_node (REAL_TYPE);
6284   if (short_double)
6285     TYPE_PRECISION (double_type_node) = FLOAT_TYPE_SIZE;
6286   else
6287     TYPE_PRECISION (double_type_node) = DOUBLE_TYPE_SIZE;
6288   layout_type (double_type_node);
6289
6290   long_double_type_node = make_node (REAL_TYPE);
6291   TYPE_PRECISION (long_double_type_node) = LONG_DOUBLE_TYPE_SIZE;
6292   layout_type (long_double_type_node);
6293
6294   float_ptr_type_node = build_pointer_type (float_type_node);
6295   double_ptr_type_node = build_pointer_type (double_type_node);
6296   long_double_ptr_type_node = build_pointer_type (long_double_type_node);
6297   integer_ptr_type_node = build_pointer_type (integer_type_node);
6298
6299   complex_integer_type_node = make_node (COMPLEX_TYPE);
6300   TREE_TYPE (complex_integer_type_node) = integer_type_node;
6301   layout_type (complex_integer_type_node);
6302
6303   complex_float_type_node = make_node (COMPLEX_TYPE);
6304   TREE_TYPE (complex_float_type_node) = float_type_node;
6305   layout_type (complex_float_type_node);
6306
6307   complex_double_type_node = make_node (COMPLEX_TYPE);
6308   TREE_TYPE (complex_double_type_node) = double_type_node;
6309   layout_type (complex_double_type_node);
6310
6311   complex_long_double_type_node = make_node (COMPLEX_TYPE);
6312   TREE_TYPE (complex_long_double_type_node) = long_double_type_node;
6313   layout_type (complex_long_double_type_node);
6314
6315   {
6316     tree t = targetm.build_builtin_va_list ();
6317
6318     /* Many back-ends define record types without setting TYPE_NAME.
6319        If we copied the record type here, we'd keep the original
6320        record type without a name.  This breaks name mangling.  So,
6321        don't copy record types and let c_common_nodes_and_builtins()
6322        declare the type to be __builtin_va_list.  */
6323     if (TREE_CODE (t) != RECORD_TYPE)
6324       t = build_variant_type_copy (t);
6325
6326     va_list_type_node = t;
6327   }
6328 }
6329
6330 /* A subroutine of build_common_builtin_nodes.  Define a builtin function.  */
6331
6332 static void
6333 local_define_builtin (const char *name, tree type, enum built_in_function code,
6334                       const char *library_name, int ecf_flags)
6335 {
6336   tree decl;
6337
6338   decl = lang_hooks.builtin_function (name, type, code, BUILT_IN_NORMAL,
6339                                       library_name, NULL_TREE);
6340   if (ecf_flags & ECF_CONST)
6341     TREE_READONLY (decl) = 1;
6342   if (ecf_flags & ECF_PURE)
6343     DECL_IS_PURE (decl) = 1;
6344   if (ecf_flags & ECF_NORETURN)
6345     TREE_THIS_VOLATILE (decl) = 1;
6346   if (ecf_flags & ECF_NOTHROW)
6347     TREE_NOTHROW (decl) = 1;
6348   if (ecf_flags & ECF_MALLOC)
6349     DECL_IS_MALLOC (decl) = 1;
6350
6351   built_in_decls[code] = decl;
6352   implicit_built_in_decls[code] = decl;
6353 }
6354
6355 /* Call this function after instantiating all builtins that the language
6356    front end cares about.  This will build the rest of the builtins that
6357    are relied upon by the tree optimizers and the middle-end.  */
6358
6359 void
6360 build_common_builtin_nodes (void)
6361 {
6362   tree tmp, ftype;
6363
6364   if (built_in_decls[BUILT_IN_MEMCPY] == NULL
6365       || built_in_decls[BUILT_IN_MEMMOVE] == NULL)
6366     {
6367       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6368       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6369       tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6370       ftype = build_function_type (ptr_type_node, tmp);
6371
6372       if (built_in_decls[BUILT_IN_MEMCPY] == NULL)
6373         local_define_builtin ("__builtin_memcpy", ftype, BUILT_IN_MEMCPY,
6374                               "memcpy", ECF_NOTHROW);
6375       if (built_in_decls[BUILT_IN_MEMMOVE] == NULL)
6376         local_define_builtin ("__builtin_memmove", ftype, BUILT_IN_MEMMOVE,
6377                               "memmove", ECF_NOTHROW);
6378     }
6379
6380   if (built_in_decls[BUILT_IN_MEMCMP] == NULL)
6381     {
6382       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6383       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6384       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6385       ftype = build_function_type (integer_type_node, tmp);
6386       local_define_builtin ("__builtin_memcmp", ftype, BUILT_IN_MEMCMP,
6387                             "memcmp", ECF_PURE | ECF_NOTHROW);
6388     }
6389
6390   if (built_in_decls[BUILT_IN_MEMSET] == NULL)
6391     {
6392       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6393       tmp = tree_cons (NULL_TREE, integer_type_node, tmp);
6394       tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6395       ftype = build_function_type (ptr_type_node, tmp);
6396       local_define_builtin ("__builtin_memset", ftype, BUILT_IN_MEMSET,
6397                             "memset", ECF_NOTHROW);
6398     }
6399
6400   if (built_in_decls[BUILT_IN_ALLOCA] == NULL)
6401     {
6402       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6403       ftype = build_function_type (ptr_type_node, tmp);
6404       local_define_builtin ("__builtin_alloca", ftype, BUILT_IN_ALLOCA,
6405                             "alloca", ECF_NOTHROW | ECF_MALLOC);
6406     }
6407
6408   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6409   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6410   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6411   ftype = build_function_type (void_type_node, tmp);
6412   local_define_builtin ("__builtin_init_trampoline", ftype,
6413                         BUILT_IN_INIT_TRAMPOLINE,
6414                         "__builtin_init_trampoline", ECF_NOTHROW);
6415
6416   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6417   ftype = build_function_type (ptr_type_node, tmp);
6418   local_define_builtin ("__builtin_adjust_trampoline", ftype,
6419                         BUILT_IN_ADJUST_TRAMPOLINE,
6420                         "__builtin_adjust_trampoline",
6421                         ECF_CONST | ECF_NOTHROW);
6422
6423   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6424   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6425   ftype = build_function_type (void_type_node, tmp);
6426   local_define_builtin ("__builtin_nonlocal_goto", ftype,
6427                         BUILT_IN_NONLOCAL_GOTO,
6428                         "__builtin_nonlocal_goto",
6429                         ECF_NORETURN | ECF_NOTHROW);
6430
6431   ftype = build_function_type (ptr_type_node, void_list_node);
6432   local_define_builtin ("__builtin_stack_save", ftype, BUILT_IN_STACK_SAVE,
6433                         "__builtin_stack_save", ECF_NOTHROW);
6434
6435   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6436   ftype = build_function_type (void_type_node, tmp);
6437   local_define_builtin ("__builtin_stack_restore", ftype,
6438                         BUILT_IN_STACK_RESTORE,
6439                         "__builtin_stack_restore", ECF_NOTHROW);
6440
6441   ftype = build_function_type (void_type_node, void_list_node);
6442   local_define_builtin ("__builtin_profile_func_enter", ftype,
6443                         BUILT_IN_PROFILE_FUNC_ENTER, "profile_func_enter", 0);
6444   local_define_builtin ("__builtin_profile_func_exit", ftype,
6445                         BUILT_IN_PROFILE_FUNC_EXIT, "profile_func_exit", 0);
6446
6447   /* Complex multiplication and division.  These are handled as builtins
6448      rather than optabs because emit_library_call_value doesn't support
6449      complex.  Further, we can do slightly better with folding these
6450      beasties if the real and complex parts of the arguments are separate.  */
6451   {
6452     enum machine_mode mode;
6453
6454     for (mode = MIN_MODE_COMPLEX_FLOAT; mode <= MAX_MODE_COMPLEX_FLOAT; ++mode)
6455       {
6456         char mode_name_buf[4], *q;
6457         const char *p;
6458         enum built_in_function mcode, dcode;
6459         tree type, inner_type;
6460
6461         type = lang_hooks.types.type_for_mode (mode, 0);
6462         if (type == NULL)
6463           continue;
6464         inner_type = TREE_TYPE (type);
6465
6466         tmp = tree_cons (NULL_TREE, inner_type, void_list_node);
6467         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6468         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6469         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6470         ftype = build_function_type (type, tmp);
6471
6472         mcode = BUILT_IN_COMPLEX_MUL_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
6473         dcode = BUILT_IN_COMPLEX_DIV_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
6474
6475         for (p = GET_MODE_NAME (mode), q = mode_name_buf; *p; p++, q++)
6476           *q = TOLOWER (*p);
6477         *q = '\0';
6478
6479         built_in_names[mcode] = concat ("__mul", mode_name_buf, "3", NULL);
6480         local_define_builtin (built_in_names[mcode], ftype, mcode,
6481                               built_in_names[mcode], ECF_CONST | ECF_NOTHROW);
6482
6483         built_in_names[dcode] = concat ("__div", mode_name_buf, "3", NULL);
6484         local_define_builtin (built_in_names[dcode], ftype, dcode,
6485                               built_in_names[dcode], ECF_CONST | ECF_NOTHROW);
6486       }
6487   }
6488 }
6489
6490 /* HACK.  GROSS.  This is absolutely disgusting.  I wish there was a
6491    better way.
6492
6493    If we requested a pointer to a vector, build up the pointers that
6494    we stripped off while looking for the inner type.  Similarly for
6495    return values from functions.
6496
6497    The argument TYPE is the top of the chain, and BOTTOM is the
6498    new type which we will point to.  */
6499
6500 tree
6501 reconstruct_complex_type (tree type, tree bottom)
6502 {
6503   tree inner, outer;
6504
6505   if (POINTER_TYPE_P (type))
6506     {
6507       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6508       outer = build_pointer_type (inner);
6509     }
6510   else if (TREE_CODE (type) == ARRAY_TYPE)
6511     {
6512       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6513       outer = build_array_type (inner, TYPE_DOMAIN (type));
6514     }
6515   else if (TREE_CODE (type) == FUNCTION_TYPE)
6516     {
6517       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6518       outer = build_function_type (inner, TYPE_ARG_TYPES (type));
6519     }
6520   else if (TREE_CODE (type) == METHOD_TYPE)
6521     {
6522       tree argtypes;
6523       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6524       /* The build_method_type_directly() routine prepends 'this' to argument list,
6525          so we must compensate by getting rid of it.  */
6526       argtypes = TYPE_ARG_TYPES (type);
6527       outer = build_method_type_directly (TYPE_METHOD_BASETYPE (type),
6528                                           inner,
6529                                           TYPE_ARG_TYPES (type));
6530       TYPE_ARG_TYPES (outer) = argtypes;
6531     }
6532   else
6533     return bottom;
6534
6535   TYPE_READONLY (outer) = TYPE_READONLY (type);
6536   TYPE_VOLATILE (outer) = TYPE_VOLATILE (type);
6537
6538   return outer;
6539 }
6540
6541 /* Returns a vector tree node given a mode (integer, vector, or BLKmode) and
6542    the inner type.  */
6543 tree
6544 build_vector_type_for_mode (tree innertype, enum machine_mode mode)
6545 {
6546   int nunits;
6547
6548   switch (GET_MODE_CLASS (mode))
6549     {
6550     case MODE_VECTOR_INT:
6551     case MODE_VECTOR_FLOAT:
6552       nunits = GET_MODE_NUNITS (mode);
6553       break;
6554
6555     case MODE_INT:
6556       /* Check that there are no leftover bits.  */
6557       gcc_assert (GET_MODE_BITSIZE (mode)
6558                   % TREE_INT_CST_LOW (TYPE_SIZE (innertype)) == 0);
6559
6560       nunits = GET_MODE_BITSIZE (mode)
6561                / TREE_INT_CST_LOW (TYPE_SIZE (innertype));
6562       break;
6563
6564     default:
6565       gcc_unreachable ();
6566     }
6567
6568   return make_vector_type (innertype, nunits, mode);
6569 }
6570
6571 /* Similarly, but takes the inner type and number of units, which must be
6572    a power of two.  */
6573
6574 tree
6575 build_vector_type (tree innertype, int nunits)
6576 {
6577   return make_vector_type (innertype, nunits, VOIDmode);
6578 }
6579
6580 /* Build RESX_EXPR with given REGION_NUMBER.  */
6581 tree
6582 build_resx (int region_number)
6583 {
6584   tree t;
6585   t = build1 (RESX_EXPR, void_type_node,
6586               build_int_cst (NULL_TREE, region_number));
6587   return t;
6588 }
6589
6590 /* Given an initializer INIT, return TRUE if INIT is zero or some
6591    aggregate of zeros.  Otherwise return FALSE.  */
6592 bool
6593 initializer_zerop (tree init)
6594 {
6595   tree elt;
6596
6597   STRIP_NOPS (init);
6598
6599   switch (TREE_CODE (init))
6600     {
6601     case INTEGER_CST:
6602       return integer_zerop (init);
6603
6604     case REAL_CST:
6605       /* ??? Note that this is not correct for C4X float formats.  There,
6606          a bit pattern of all zeros is 1.0; 0.0 is encoded with the most
6607          negative exponent.  */
6608       return real_zerop (init)
6609         && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init));
6610
6611     case COMPLEX_CST:
6612       return integer_zerop (init)
6613         || (real_zerop (init)
6614             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init)))
6615             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init))));
6616
6617     case VECTOR_CST:
6618       for (elt = TREE_VECTOR_CST_ELTS (init); elt; elt = TREE_CHAIN (elt))
6619         if (!initializer_zerop (TREE_VALUE (elt)))
6620           return false;
6621       return true;
6622
6623     case CONSTRUCTOR:
6624       {
6625         unsigned HOST_WIDE_INT idx;
6626
6627         FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (init), idx, elt)
6628           if (!initializer_zerop (elt))
6629             return false;
6630         return true;
6631       }
6632
6633     default:
6634       return false;
6635     }
6636 }
6637
6638 void
6639 add_var_to_bind_expr (tree bind_expr, tree var)
6640 {
6641   BIND_EXPR_VARS (bind_expr)
6642     = chainon (BIND_EXPR_VARS (bind_expr), var);
6643   if (BIND_EXPR_BLOCK (bind_expr))
6644     BLOCK_VARS (BIND_EXPR_BLOCK (bind_expr))
6645       = BIND_EXPR_VARS (bind_expr);
6646 }
6647
6648 /* Build an empty statement.  */
6649
6650 tree
6651 build_empty_stmt (void)
6652 {
6653   return build1 (NOP_EXPR, void_type_node, size_zero_node);
6654 }
6655
6656
6657 /* Returns true if it is possible to prove that the index of
6658    an array access REF (an ARRAY_REF expression) falls into the
6659    array bounds.  */
6660
6661 bool
6662 in_array_bounds_p (tree ref)
6663 {
6664   tree idx = TREE_OPERAND (ref, 1);
6665   tree min, max;
6666
6667   if (TREE_CODE (idx) != INTEGER_CST)
6668     return false;
6669
6670   min = array_ref_low_bound (ref);
6671   max = array_ref_up_bound (ref);
6672   if (!min
6673       || !max
6674       || TREE_CODE (min) != INTEGER_CST
6675       || TREE_CODE (max) != INTEGER_CST)
6676     return false;
6677
6678   if (tree_int_cst_lt (idx, min)
6679       || tree_int_cst_lt (max, idx))
6680     return false;
6681
6682   return true;
6683 }
6684
6685 /* Return true if T (assumed to be a DECL) is a global variable.  */
6686
6687 bool
6688 is_global_var (tree t)
6689 {
6690   return (TREE_STATIC (t) || DECL_EXTERNAL (t));
6691 }
6692
6693 /* Return true if T (assumed to be a DECL) must be assigned a memory
6694    location.  */
6695
6696 bool
6697 needs_to_live_in_memory (tree t)
6698 {
6699   return (TREE_ADDRESSABLE (t)
6700           || is_global_var (t)
6701           || (TREE_CODE (t) == RESULT_DECL
6702               && aggregate_value_p (t, current_function_decl)));
6703 }
6704
6705 /* There are situations in which a language considers record types
6706    compatible which have different field lists.  Decide if two fields
6707    are compatible.  It is assumed that the parent records are compatible.  */
6708
6709 bool
6710 fields_compatible_p (tree f1, tree f2)
6711 {
6712   if (!operand_equal_p (DECL_FIELD_BIT_OFFSET (f1),
6713                         DECL_FIELD_BIT_OFFSET (f2), OEP_ONLY_CONST))
6714     return false;
6715
6716   if (!operand_equal_p (DECL_FIELD_OFFSET (f1),
6717                         DECL_FIELD_OFFSET (f2), OEP_ONLY_CONST))
6718     return false;
6719
6720   if (!lang_hooks.types_compatible_p (TREE_TYPE (f1), TREE_TYPE (f2)))
6721     return false;
6722
6723   return true;
6724 }
6725
6726 /* Locate within RECORD a field that is compatible with ORIG_FIELD.  */
6727
6728 tree
6729 find_compatible_field (tree record, tree orig_field)
6730 {
6731   tree f;
6732
6733   for (f = TYPE_FIELDS (record); f ; f = TREE_CHAIN (f))
6734     if (TREE_CODE (f) == FIELD_DECL
6735         && fields_compatible_p (f, orig_field))
6736       return f;
6737
6738   /* ??? Why isn't this on the main fields list?  */
6739   f = TYPE_VFIELD (record);
6740   if (f && TREE_CODE (f) == FIELD_DECL
6741       && fields_compatible_p (f, orig_field))
6742     return f;
6743
6744   /* ??? We should abort here, but Java appears to do Bad Things
6745      with inherited fields.  */
6746   return orig_field;
6747 }
6748
6749 /* Return value of a constant X.  */
6750
6751 HOST_WIDE_INT
6752 int_cst_value (tree x)
6753 {
6754   unsigned bits = TYPE_PRECISION (TREE_TYPE (x));
6755   unsigned HOST_WIDE_INT val = TREE_INT_CST_LOW (x);
6756   bool negative = ((val >> (bits - 1)) & 1) != 0;
6757
6758   gcc_assert (bits <= HOST_BITS_PER_WIDE_INT);
6759
6760   if (negative)
6761     val |= (~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1;
6762   else
6763     val &= ~((~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1);
6764
6765   return val;
6766 }
6767
6768 /* Returns the greatest common divisor of A and B, which must be
6769    INTEGER_CSTs.  */
6770
6771 tree
6772 tree_fold_gcd (tree a, tree b)
6773 {
6774   tree a_mod_b;
6775   tree type = TREE_TYPE (a);
6776
6777   gcc_assert (TREE_CODE (a) == INTEGER_CST);
6778   gcc_assert (TREE_CODE (b) == INTEGER_CST);
6779
6780   if (integer_zerop (a))
6781     return b;
6782
6783   if (integer_zerop (b))
6784     return a;
6785
6786   if (tree_int_cst_sgn (a) == -1)
6787     a = fold_build2 (MULT_EXPR, type, a,
6788                      convert (type, integer_minus_one_node));
6789
6790   if (tree_int_cst_sgn (b) == -1)
6791     b = fold_build2 (MULT_EXPR, type, b,
6792                      convert (type, integer_minus_one_node));
6793
6794   while (1)
6795     {
6796       a_mod_b = fold_build2 (FLOOR_MOD_EXPR, type, a, b);
6797
6798       if (!TREE_INT_CST_LOW (a_mod_b)
6799           && !TREE_INT_CST_HIGH (a_mod_b))
6800         return b;
6801
6802       a = b;
6803       b = a_mod_b;
6804     }
6805 }
6806
6807 /* Returns unsigned variant of TYPE.  */
6808
6809 tree
6810 unsigned_type_for (tree type)
6811 {
6812   return lang_hooks.types.unsigned_type (type);
6813 }
6814
6815 /* Returns signed variant of TYPE.  */
6816
6817 tree
6818 signed_type_for (tree type)
6819 {
6820   return lang_hooks.types.signed_type (type);
6821 }
6822
6823 /* Returns the largest value obtainable by casting something in INNER type to
6824    OUTER type.  */
6825
6826 tree
6827 upper_bound_in_type (tree outer, tree inner)
6828 {
6829   unsigned HOST_WIDE_INT lo, hi;
6830   unsigned int det = 0;
6831   unsigned oprec = TYPE_PRECISION (outer);
6832   unsigned iprec = TYPE_PRECISION (inner);
6833   unsigned prec;
6834
6835   /* Compute a unique number for every combination.  */
6836   det |= (oprec > iprec) ? 4 : 0;
6837   det |= TYPE_UNSIGNED (outer) ? 2 : 0;
6838   det |= TYPE_UNSIGNED (inner) ? 1 : 0;
6839
6840   /* Determine the exponent to use.  */
6841   switch (det)
6842     {
6843     case 0:
6844     case 1:
6845       /* oprec <= iprec, outer: signed, inner: don't care.  */
6846       prec = oprec - 1;
6847       break;
6848     case 2:
6849     case 3:
6850       /* oprec <= iprec, outer: unsigned, inner: don't care.  */
6851       prec = oprec;
6852       break;
6853     case 4:
6854       /* oprec > iprec, outer: signed, inner: signed.  */
6855       prec = iprec - 1;
6856       break;
6857     case 5:
6858       /* oprec > iprec, outer: signed, inner: unsigned.  */
6859       prec = iprec;
6860       break;
6861     case 6:
6862       /* oprec > iprec, outer: unsigned, inner: signed.  */
6863       prec = oprec;
6864       break;
6865     case 7:
6866       /* oprec > iprec, outer: unsigned, inner: unsigned.  */
6867       prec = iprec;
6868       break;
6869     default:
6870       gcc_unreachable ();
6871     }
6872
6873   /* Compute 2^^prec - 1.  */
6874   if (prec <= HOST_BITS_PER_WIDE_INT)
6875     {
6876       hi = 0;
6877       lo = ((~(unsigned HOST_WIDE_INT) 0)
6878             >> (HOST_BITS_PER_WIDE_INT - prec));
6879     }
6880   else
6881     {
6882       hi = ((~(unsigned HOST_WIDE_INT) 0)
6883             >> (2 * HOST_BITS_PER_WIDE_INT - prec));
6884       lo = ~(unsigned HOST_WIDE_INT) 0;
6885     }
6886
6887   return build_int_cst_wide (outer, lo, hi);
6888 }
6889
6890 /* Returns the smallest value obtainable by casting something in INNER type to
6891    OUTER type.  */
6892
6893 tree
6894 lower_bound_in_type (tree outer, tree inner)
6895 {
6896   unsigned HOST_WIDE_INT lo, hi;
6897   unsigned oprec = TYPE_PRECISION (outer);
6898   unsigned iprec = TYPE_PRECISION (inner);
6899
6900   /* If OUTER type is unsigned, we can definitely cast 0 to OUTER type
6901      and obtain 0.  */
6902   if (TYPE_UNSIGNED (outer)
6903       /* If we are widening something of an unsigned type, OUTER type
6904          contains all values of INNER type.  In particular, both INNER
6905          and OUTER types have zero in common.  */
6906       || (oprec > iprec && TYPE_UNSIGNED (inner)))
6907     lo = hi = 0;
6908   else
6909     {
6910       /* If we are widening a signed type to another signed type, we
6911          want to obtain -2^^(iprec-1).  If we are keeping the
6912          precision or narrowing to a signed type, we want to obtain
6913          -2^(oprec-1).  */
6914       unsigned prec = oprec > iprec ? iprec : oprec;
6915
6916       if (prec <= HOST_BITS_PER_WIDE_INT)
6917         {
6918           hi = ~(unsigned HOST_WIDE_INT) 0;
6919           lo = (~(unsigned HOST_WIDE_INT) 0) << (prec - 1);
6920         }
6921       else
6922         {
6923           hi = ((~(unsigned HOST_WIDE_INT) 0)
6924                 << (prec - HOST_BITS_PER_WIDE_INT - 1));
6925           lo = 0;
6926         }
6927     }
6928
6929   return build_int_cst_wide (outer, lo, hi);
6930 }
6931
6932 /* Return nonzero if two operands that are suitable for PHI nodes are
6933    necessarily equal.  Specifically, both ARG0 and ARG1 must be either
6934    SSA_NAME or invariant.  Note that this is strictly an optimization.
6935    That is, callers of this function can directly call operand_equal_p
6936    and get the same result, only slower.  */
6937
6938 int
6939 operand_equal_for_phi_arg_p (tree arg0, tree arg1)
6940 {
6941   if (arg0 == arg1)
6942     return 1;
6943   if (TREE_CODE (arg0) == SSA_NAME || TREE_CODE (arg1) == SSA_NAME)
6944     return 0;
6945   return operand_equal_p (arg0, arg1, 0);
6946 }
6947
6948 /* Returns number of zeros at the end of binary representation of X.
6949
6950    ??? Use ffs if available?  */
6951
6952 tree
6953 num_ending_zeros (tree x)
6954 {
6955   unsigned HOST_WIDE_INT fr, nfr;
6956   unsigned num, abits;
6957   tree type = TREE_TYPE (x);
6958
6959   if (TREE_INT_CST_LOW (x) == 0)
6960     {
6961       num = HOST_BITS_PER_WIDE_INT;
6962       fr = TREE_INT_CST_HIGH (x);
6963     }
6964   else
6965     {
6966       num = 0;
6967       fr = TREE_INT_CST_LOW (x);
6968     }
6969
6970   for (abits = HOST_BITS_PER_WIDE_INT / 2; abits; abits /= 2)
6971     {
6972       nfr = fr >> abits;
6973       if (nfr << abits == fr)
6974         {
6975           num += abits;
6976           fr = nfr;
6977         }
6978     }
6979
6980   if (num > TYPE_PRECISION (type))
6981     num = TYPE_PRECISION (type);
6982
6983   return build_int_cst_type (type, num);
6984 }
6985
6986
6987 #define WALK_SUBTREE(NODE)                              \
6988   do                                                    \
6989     {                                                   \
6990       result = walk_tree (&(NODE), func, data, pset);   \
6991       if (result)                                       \
6992         return result;                                  \
6993     }                                                   \
6994   while (0)
6995
6996 /* This is a subroutine of walk_tree that walks field of TYPE that are to
6997    be walked whenever a type is seen in the tree.  Rest of operands and return
6998    value are as for walk_tree.  */
6999
7000 static tree
7001 walk_type_fields (tree type, walk_tree_fn func, void *data,
7002                   struct pointer_set_t *pset)
7003 {
7004   tree result = NULL_TREE;
7005
7006   switch (TREE_CODE (type))
7007     {
7008     case POINTER_TYPE:
7009     case REFERENCE_TYPE:
7010       /* We have to worry about mutually recursive pointers.  These can't
7011          be written in C.  They can in Ada.  It's pathological, but
7012          there's an ACATS test (c38102a) that checks it.  Deal with this
7013          by checking if we're pointing to another pointer, that one
7014          points to another pointer, that one does too, and we have no htab.
7015          If so, get a hash table.  We check three levels deep to avoid
7016          the cost of the hash table if we don't need one.  */
7017       if (POINTER_TYPE_P (TREE_TYPE (type))
7018           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type)))
7019           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type))))
7020           && !pset)
7021         {
7022           result = walk_tree_without_duplicates (&TREE_TYPE (type),
7023                                                  func, data);
7024           if (result)
7025             return result;
7026
7027           break;
7028         }
7029
7030       /* ... fall through ... */
7031
7032     case COMPLEX_TYPE:
7033       WALK_SUBTREE (TREE_TYPE (type));
7034       break;
7035
7036     case METHOD_TYPE:
7037       WALK_SUBTREE (TYPE_METHOD_BASETYPE (type));
7038
7039       /* Fall through.  */
7040
7041     case FUNCTION_TYPE:
7042       WALK_SUBTREE (TREE_TYPE (type));
7043       {
7044         tree arg;
7045
7046         /* We never want to walk into default arguments.  */
7047         for (arg = TYPE_ARG_TYPES (type); arg; arg = TREE_CHAIN (arg))
7048           WALK_SUBTREE (TREE_VALUE (arg));
7049       }
7050       break;
7051
7052     case ARRAY_TYPE:
7053       /* Don't follow this nodes's type if a pointer for fear that we'll
7054          have infinite recursion.  Those types are uninteresting anyway.  */
7055       if (!POINTER_TYPE_P (TREE_TYPE (type))
7056           && TREE_CODE (TREE_TYPE (type)) != OFFSET_TYPE)
7057         WALK_SUBTREE (TREE_TYPE (type));
7058       WALK_SUBTREE (TYPE_DOMAIN (type));
7059       break;
7060
7061     case BOOLEAN_TYPE:
7062     case ENUMERAL_TYPE:
7063     case INTEGER_TYPE:
7064     case CHAR_TYPE:
7065     case REAL_TYPE:
7066       WALK_SUBTREE (TYPE_MIN_VALUE (type));
7067       WALK_SUBTREE (TYPE_MAX_VALUE (type));
7068       break;
7069
7070     case OFFSET_TYPE:
7071       WALK_SUBTREE (TREE_TYPE (type));
7072       WALK_SUBTREE (TYPE_OFFSET_BASETYPE (type));
7073       break;
7074
7075     default:
7076       break;
7077     }
7078
7079   return NULL_TREE;
7080 }
7081
7082 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.  FUNC is
7083    called with the DATA and the address of each sub-tree.  If FUNC returns a
7084    non-NULL value, the traversal is stopped, and the value returned by FUNC
7085    is returned.  If PSET is non-NULL it is used to record the nodes visited,
7086    and to avoid visiting a node more than once.  */
7087
7088 tree
7089 walk_tree (tree *tp, walk_tree_fn func, void *data, struct pointer_set_t *pset)
7090 {
7091   enum tree_code code;
7092   int walk_subtrees;
7093   tree result;
7094
7095 #define WALK_SUBTREE_TAIL(NODE)                         \
7096   do                                                    \
7097     {                                                   \
7098        tp = & (NODE);                                   \
7099        goto tail_recurse;                               \
7100     }                                                   \
7101   while (0)
7102
7103  tail_recurse:
7104   /* Skip empty subtrees.  */
7105   if (!*tp)
7106     return NULL_TREE;
7107
7108   /* Don't walk the same tree twice, if the user has requested
7109      that we avoid doing so.  */
7110   if (pset && pointer_set_insert (pset, *tp))
7111     return NULL_TREE;
7112
7113   /* Call the function.  */
7114   walk_subtrees = 1;
7115   result = (*func) (tp, &walk_subtrees, data);
7116
7117   /* If we found something, return it.  */
7118   if (result)
7119     return result;
7120
7121   code = TREE_CODE (*tp);
7122
7123   /* Even if we didn't, FUNC may have decided that there was nothing
7124      interesting below this point in the tree.  */
7125   if (!walk_subtrees)
7126     {
7127       if (code == TREE_LIST)
7128         /* But we still need to check our siblings.  */
7129         WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
7130       else
7131         return NULL_TREE;
7132     }
7133
7134   result = lang_hooks.tree_inlining.walk_subtrees (tp, &walk_subtrees, func,
7135                                                    data, pset);
7136   if (result || ! walk_subtrees)
7137     return result;
7138
7139   /* If this is a DECL_EXPR, walk into various fields of the type that it's
7140      defining.  We only want to walk into these fields of a type in this
7141      case.  Note that decls get walked as part of the processing of a
7142      BIND_EXPR.
7143
7144      ??? Precisely which fields of types that we are supposed to walk in
7145      this case vs. the normal case aren't well defined.  */
7146   if (code == DECL_EXPR
7147       && TREE_CODE (DECL_EXPR_DECL (*tp)) == TYPE_DECL
7148       && TREE_CODE (TREE_TYPE (DECL_EXPR_DECL (*tp))) != ERROR_MARK)
7149     {
7150       tree *type_p = &TREE_TYPE (DECL_EXPR_DECL (*tp));
7151
7152       /* Call the function for the type.  See if it returns anything or
7153          doesn't want us to continue.  If we are to continue, walk both
7154          the normal fields and those for the declaration case.  */
7155       result = (*func) (type_p, &walk_subtrees, data);
7156       if (result || !walk_subtrees)
7157         return NULL_TREE;
7158
7159       result = walk_type_fields (*type_p, func, data, pset);
7160       if (result)
7161         return result;
7162
7163       WALK_SUBTREE (TYPE_SIZE (*type_p));
7164       WALK_SUBTREE (TYPE_SIZE_UNIT (*type_p));
7165
7166       /* If this is a record type, also walk the fields.  */
7167       if (TREE_CODE (*type_p) == RECORD_TYPE
7168           || TREE_CODE (*type_p) == UNION_TYPE
7169           || TREE_CODE (*type_p) == QUAL_UNION_TYPE)
7170         {
7171           tree field;
7172
7173           for (field = TYPE_FIELDS (*type_p); field;
7174                field = TREE_CHAIN (field))
7175             {
7176               /* We'd like to look at the type of the field, but we can easily
7177                  get infinite recursion.  So assume it's pointed to elsewhere
7178                  in the tree.  Also, ignore things that aren't fields.  */
7179               if (TREE_CODE (field) != FIELD_DECL)
7180                 continue;
7181
7182               WALK_SUBTREE (DECL_FIELD_OFFSET (field));
7183               WALK_SUBTREE (DECL_SIZE (field));
7184               WALK_SUBTREE (DECL_SIZE_UNIT (field));
7185               if (TREE_CODE (*type_p) == QUAL_UNION_TYPE)
7186                 WALK_SUBTREE (DECL_QUALIFIER (field));
7187             }
7188         }
7189     }
7190
7191   else if (code != SAVE_EXPR
7192            && code != BIND_EXPR
7193            && IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
7194     {
7195       int i, len;
7196
7197       /* Walk over all the sub-trees of this operand.  */
7198       len = TREE_CODE_LENGTH (code);
7199       /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
7200          But, we only want to walk once.  */
7201       if (code == TARGET_EXPR
7202           && TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1))
7203         --len;
7204
7205       /* Go through the subtrees.  We need to do this in forward order so
7206          that the scope of a FOR_EXPR is handled properly.  */
7207 #ifdef DEBUG_WALK_TREE
7208       for (i = 0; i < len; ++i)
7209         WALK_SUBTREE (TREE_OPERAND (*tp, i));
7210 #else
7211       for (i = 0; i < len - 1; ++i)
7212         WALK_SUBTREE (TREE_OPERAND (*tp, i));
7213
7214       if (len)
7215         {
7216           /* The common case is that we may tail recurse here.  */
7217           if (code != BIND_EXPR
7218               && !TREE_CHAIN (*tp))
7219             WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len - 1));
7220           else
7221             WALK_SUBTREE (TREE_OPERAND (*tp, len - 1));
7222         }
7223 #endif
7224     }
7225
7226   /* If this is a type, walk the needed fields in the type.  */
7227   else if (TYPE_P (*tp))
7228     {
7229       result = walk_type_fields (*tp, func, data, pset);
7230       if (result)
7231         return result;
7232     }
7233   else
7234     {
7235       /* Not one of the easy cases.  We must explicitly go through the
7236          children.  */
7237       switch (code)
7238         {
7239         case ERROR_MARK:
7240         case IDENTIFIER_NODE:
7241         case INTEGER_CST:
7242         case REAL_CST:
7243         case VECTOR_CST:
7244         case STRING_CST:
7245         case BLOCK:
7246         case PLACEHOLDER_EXPR:
7247         case SSA_NAME:
7248         case FIELD_DECL:
7249         case RESULT_DECL:
7250           /* None of these have subtrees other than those already walked
7251              above.  */
7252           break;
7253
7254         case TREE_LIST:
7255           WALK_SUBTREE (TREE_VALUE (*tp));
7256           WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
7257           break;
7258
7259         case TREE_VEC:
7260           {
7261             int len = TREE_VEC_LENGTH (*tp);
7262
7263             if (len == 0)
7264               break;
7265
7266             /* Walk all elements but the first.  */
7267             while (--len)
7268               WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
7269
7270             /* Now walk the first one as a tail call.  */
7271             WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
7272           }
7273
7274         case COMPLEX_CST:
7275           WALK_SUBTREE (TREE_REALPART (*tp));
7276           WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp));
7277
7278         case CONSTRUCTOR:
7279           {
7280             unsigned HOST_WIDE_INT idx;
7281             constructor_elt *ce;
7282
7283             for (idx = 0;
7284                  VEC_iterate(constructor_elt, CONSTRUCTOR_ELTS (*tp), idx, ce);
7285                  idx++)
7286               WALK_SUBTREE (ce->value);
7287           }
7288           break;
7289
7290         case SAVE_EXPR:
7291           WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 0));
7292
7293         case BIND_EXPR:
7294           {
7295             tree decl;
7296             for (decl = BIND_EXPR_VARS (*tp); decl; decl = TREE_CHAIN (decl))
7297               {
7298                 /* Walk the DECL_INITIAL and DECL_SIZE.  We don't want to walk
7299                    into declarations that are just mentioned, rather than
7300                    declared; they don't really belong to this part of the tree.
7301                    And, we can see cycles: the initializer for a declaration
7302                    can refer to the declaration itself.  */
7303                 WALK_SUBTREE (DECL_INITIAL (decl));
7304                 WALK_SUBTREE (DECL_SIZE (decl));
7305                 WALK_SUBTREE (DECL_SIZE_UNIT (decl));
7306               }
7307             WALK_SUBTREE_TAIL (BIND_EXPR_BODY (*tp));
7308           }
7309
7310         case STATEMENT_LIST:
7311           {
7312             tree_stmt_iterator i;
7313             for (i = tsi_start (*tp); !tsi_end_p (i); tsi_next (&i))
7314               WALK_SUBTREE (*tsi_stmt_ptr (i));
7315           }
7316           break;
7317
7318         default:
7319           /* ??? This could be a language-defined node.  We really should make
7320              a hook for it, but right now just ignore it.  */
7321           break;
7322         }
7323     }
7324
7325   /* We didn't find what we were looking for.  */
7326   return NULL_TREE;
7327
7328 #undef WALK_SUBTREE_TAIL
7329 }
7330 #undef WALK_SUBTREE
7331
7332 /* Like walk_tree, but does not walk duplicate nodes more than once.  */
7333
7334 tree
7335 walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data)
7336 {
7337   tree result;
7338   struct pointer_set_t *pset;
7339
7340   pset = pointer_set_create ();
7341   result = walk_tree (tp, func, data, pset);
7342   pointer_set_destroy (pset);
7343   return result;
7344 }
7345
7346 #include "gt-tree.h"