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