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