gcc/tree.c

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