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