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, use it.  */
3796   if (t != 0 && mode == ptr_mode)
3797     return t;
3798
3799   t = make_node (POINTER_TYPE);
3800
3801   TREE_TYPE (t) = to_type;
3802   TYPE_MODE (t) = mode;
3803
3804   /* Record this type as the pointer to TO_TYPE.  */
3805   if (mode == ptr_mode)
3806   TYPE_POINTER_TO (to_type) = t;
3807
3808   /* Lay out the type.  This function has many callers that are concerned
3809      with expression-construction, and this simplifies them all.
3810      Also, it guarantees the TYPE_SIZE is in the same obstack as the type.  */
3811   layout_type (t);
3812
3813   return t;
3814 }
3815
3816 /* By default build pointers in ptr_mode.  */
3817
3818 tree
3819 build_pointer_type (tree to_type)
3820 {
3821   return build_pointer_type_for_mode (to_type, ptr_mode);
3822 }
3823
3824 /* Construct, lay out and return the type of references to TO_TYPE
3825    with mode MODE. If such a type has already been constructed,
3826    reuse it.  */
3827
3828 tree
3829 build_reference_type_for_mode (tree to_type, enum machine_mode mode)
3830 {
3831   tree t = TYPE_REFERENCE_TO (to_type);
3832
3833   /* First, if we already have a type for pointers to TO_TYPE, use it.  */
3834   if (t != 0 && mode == ptr_mode)
3835     return t;
3836
3837   t = make_node (REFERENCE_TYPE);
3838
3839   TREE_TYPE (t) = to_type;
3840   TYPE_MODE (t) = mode;
3841
3842   /* Record this type as the pointer to TO_TYPE.  */
3843   if (mode == ptr_mode)
3844   TYPE_REFERENCE_TO (to_type) = t;
3845
3846   layout_type (t);
3847
3848   return t;
3849 }
3850
3851
3852 /* Build the node for the type of references-to-TO_TYPE by default
3853    in ptr_mode.  */
3854
3855 tree
3856 build_reference_type (tree to_type)
3857 {
3858   return build_reference_type_for_mode (to_type, ptr_mode);
3859 }
3860
3861 /* Build a type that is compatible with t but has no cv quals anywhere
3862    in its type, thus
3863
3864    const char *const *const *  ->  char ***.  */
3865
3866 tree
3867 build_type_no_quals (tree t)
3868 {
3869   switch (TREE_CODE (t))
3870     {
3871     case POINTER_TYPE:
3872       return build_pointer_type (build_type_no_quals (TREE_TYPE (t)));
3873     case REFERENCE_TYPE:
3874       return build_reference_type (build_type_no_quals (TREE_TYPE (t)));
3875     default:
3876       return TYPE_MAIN_VARIANT (t);
3877     }
3878 }
3879
3880 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
3881    MAXVAL should be the maximum value in the domain
3882    (one less than the length of the array).
3883
3884    The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
3885    We don't enforce this limit, that is up to caller (e.g. language front end).
3886    The limit exists because the result is a signed type and we don't handle
3887    sizes that use more than one HOST_WIDE_INT.  */
3888
3889 tree
3890 build_index_type (tree maxval)
3891 {
3892   tree itype = make_node (INTEGER_TYPE);
3893
3894   TREE_TYPE (itype) = sizetype;
3895   TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
3896   TYPE_MIN_VALUE (itype) = size_zero_node;
3897   TYPE_MAX_VALUE (itype) = convert (sizetype, maxval);
3898   TYPE_MODE (itype) = TYPE_MODE (sizetype);
3899   TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
3900   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
3901   TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
3902   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
3903
3904   if (host_integerp (maxval, 1))
3905     return type_hash_canon (tree_low_cst (maxval, 1), itype);
3906   else
3907     return itype;
3908 }
3909
3910 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
3911    ENUMERAL_TYPE, BOOLEAN_TYPE, or CHAR_TYPE), with
3912    low bound LOWVAL and high bound HIGHVAL.
3913    if TYPE==NULL_TREE, sizetype is used.  */
3914
3915 tree
3916 build_range_type (tree type, tree lowval, tree highval)
3917 {
3918   tree itype = make_node (INTEGER_TYPE);
3919
3920   TREE_TYPE (itype) = type;
3921   if (type == NULL_TREE)
3922     type = sizetype;
3923
3924   TYPE_MIN_VALUE (itype) = convert (type, lowval);
3925   TYPE_MAX_VALUE (itype) = highval ? convert (type, highval) : NULL;
3926
3927   TYPE_PRECISION (itype) = TYPE_PRECISION (type);
3928   TYPE_MODE (itype) = TYPE_MODE (type);
3929   TYPE_SIZE (itype) = TYPE_SIZE (type);
3930   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type);
3931   TYPE_ALIGN (itype) = TYPE_ALIGN (type);
3932   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type);
3933
3934   if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0))
3935     return type_hash_canon (tree_low_cst (highval, 0)
3936                             - tree_low_cst (lowval, 0),
3937                             itype);
3938   else
3939     return itype;
3940 }
3941
3942 /* Just like build_index_type, but takes lowval and highval instead
3943    of just highval (maxval).  */
3944
3945 tree
3946 build_index_2_type (tree lowval, tree highval)
3947 {
3948   return build_range_type (sizetype, lowval, highval);
3949 }
3950
3951 /* Construct, lay out and return the type of arrays of elements with ELT_TYPE
3952    and number of elements specified by the range of values of INDEX_TYPE.
3953    If such a type has already been constructed, reuse it.  */
3954
3955 tree
3956 build_array_type (tree elt_type, tree index_type)
3957 {
3958   tree t;
3959   hashval_t hashcode = 0;
3960
3961   if (TREE_CODE (elt_type) == FUNCTION_TYPE)
3962     {
3963       error ("arrays of functions are not meaningful");
3964       elt_type = integer_type_node;
3965     }
3966
3967   /* Make sure TYPE_POINTER_TO (elt_type) is filled in.  */
3968   build_pointer_type (elt_type);
3969
3970   /* Allocate the array after the pointer type,
3971      in case we free it in type_hash_canon.  */
3972   t = make_node (ARRAY_TYPE);
3973   TREE_TYPE (t) = elt_type;
3974   TYPE_DOMAIN (t) = index_type;
3975
3976   if (index_type == 0)
3977     {
3978       return t;
3979     }
3980
3981   hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode);
3982   hashcode = iterative_hash_object (TYPE_HASH (index_type), hashcode);
3983   t = type_hash_canon (hashcode, t);
3984
3985   if (!COMPLETE_TYPE_P (t))
3986     layout_type (t);
3987   return t;
3988 }
3989
3990 /* Return the TYPE of the elements comprising
3991    the innermost dimension of ARRAY.  */
3992
3993 tree
3994 get_inner_array_type (tree array)
3995 {
3996   tree type = TREE_TYPE (array);
3997
3998   while (TREE_CODE (type) == ARRAY_TYPE)
3999     type = TREE_TYPE (type);
4000
4001   return type;
4002 }
4003
4004 /* Construct, lay out and return
4005    the type of functions returning type VALUE_TYPE
4006    given arguments of types ARG_TYPES.
4007    ARG_TYPES is a chain of TREE_LIST nodes whose TREE_VALUEs
4008    are data type nodes for the arguments of the function.
4009    If such a type has already been constructed, reuse it.  */
4010
4011 tree
4012 build_function_type (tree value_type, tree arg_types)
4013 {
4014   tree t;
4015   hashval_t hashcode = 0;
4016
4017   if (TREE_CODE (value_type) == FUNCTION_TYPE)
4018     {
4019       error ("function return type cannot be function");
4020       value_type = integer_type_node;
4021     }
4022
4023   /* Make a node of the sort we want.  */
4024   t = make_node (FUNCTION_TYPE);
4025   TREE_TYPE (t) = value_type;
4026   TYPE_ARG_TYPES (t) = arg_types;
4027
4028   /* If we already have such a type, use the old one and free this one.  */
4029   hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode);
4030   hashcode = type_hash_list (arg_types, hashcode);
4031   t = type_hash_canon (hashcode, t);
4032
4033   if (!COMPLETE_TYPE_P (t))
4034     layout_type (t);
4035   return t;
4036 }
4037
4038 /* Build a function type.  The RETURN_TYPE is the type returned by the
4039    function.  If additional arguments are provided, they are
4040    additional argument types.  The list of argument types must always
4041    be terminated by NULL_TREE.  */
4042
4043 tree
4044 build_function_type_list (tree return_type, ...)
4045 {
4046   tree t, args, last;
4047   va_list p;
4048
4049   va_start (p, return_type);
4050
4051   t = va_arg (p, tree);
4052   for (args = NULL_TREE; t != NULL_TREE; t = va_arg (p, tree))
4053     args = tree_cons (NULL_TREE, t, args);
4054
4055   last = args;
4056   args = nreverse (args);
4057   TREE_CHAIN (last) = void_list_node;
4058   args = build_function_type (return_type, args);
4059
4060   va_end (p);
4061   return args;
4062 }
4063
4064 /* Build a METHOD_TYPE for a member of BASETYPE.  The RETTYPE (a TYPE)
4065    and ARGTYPES (a TREE_LIST) are the return type and arguments types
4066    for the method.  An implicit additional parameter (of type
4067    pointer-to-BASETYPE) is added to the ARGTYPES.  */
4068
4069 tree
4070 build_method_type_directly (tree basetype,
4071                             tree rettype,
4072                             tree argtypes)
4073 {
4074   tree t;
4075   tree ptype;
4076   int hashcode = 0;
4077
4078   /* Make a node of the sort we want.  */
4079   t = make_node (METHOD_TYPE);
4080
4081   TYPE_METHOD_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
4082   TREE_TYPE (t) = rettype;
4083   ptype = build_pointer_type (basetype);
4084
4085   /* The actual arglist for this function includes a "hidden" argument
4086      which is "this".  Put it into the list of argument types.  */
4087   argtypes = tree_cons (NULL_TREE, ptype, argtypes);
4088   TYPE_ARG_TYPES (t) = argtypes;
4089
4090   /* If we already have such a type, use the old one and free this one.
4091      Note that it also frees up the above cons cell if found.  */
4092   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
4093   hashcode = iterative_hash_object (TYPE_HASH (rettype), hashcode);
4094   hashcode = type_hash_list (argtypes, hashcode);
4095
4096   t = type_hash_canon (hashcode, t);
4097
4098   if (!COMPLETE_TYPE_P (t))
4099     layout_type (t);
4100
4101   return t;
4102 }
4103
4104 /* Construct, lay out and return the type of methods belonging to class
4105    BASETYPE and whose arguments and values are described by TYPE.
4106    If that type exists already, reuse it.
4107    TYPE must be a FUNCTION_TYPE node.  */
4108
4109 tree
4110 build_method_type (tree basetype, tree type)
4111 {
4112   if (TREE_CODE (type) != FUNCTION_TYPE)
4113     abort ();
4114
4115   return build_method_type_directly (basetype,
4116                                      TREE_TYPE (type),
4117                                      TYPE_ARG_TYPES (type));
4118 }
4119
4120 /* Construct, lay out and return the type of offsets to a value
4121    of type TYPE, within an object of type BASETYPE.
4122    If a suitable offset type exists already, reuse it.  */
4123
4124 tree
4125 build_offset_type (tree basetype, tree type)
4126 {
4127   tree t;
4128   hashval_t hashcode = 0;
4129
4130   /* Make a node of the sort we want.  */
4131   t = make_node (OFFSET_TYPE);
4132
4133   TYPE_OFFSET_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
4134   TREE_TYPE (t) = type;
4135
4136   /* If we already have such a type, use the old one and free this one.  */
4137   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
4138   hashcode = iterative_hash_object (TYPE_HASH (type), hashcode);
4139   t = type_hash_canon (hashcode, t);
4140
4141   if (!COMPLETE_TYPE_P (t))
4142     layout_type (t);
4143
4144   return t;
4145 }
4146
4147 /* Create a complex type whose components are COMPONENT_TYPE.  */
4148
4149 tree
4150 build_complex_type (tree component_type)
4151 {
4152   tree t;
4153   hashval_t hashcode;
4154
4155   /* Make a node of the sort we want.  */
4156   t = make_node (COMPLEX_TYPE);
4157
4158   TREE_TYPE (t) = TYPE_MAIN_VARIANT (component_type);
4159   set_type_quals (t, TYPE_QUALS (component_type));
4160
4161   /* If we already have such a type, use the old one and free this one.  */
4162   hashcode = iterative_hash_object (TYPE_HASH (component_type), 0);
4163   t = type_hash_canon (hashcode, t);
4164
4165   if (!COMPLETE_TYPE_P (t))
4166     layout_type (t);
4167
4168   /* If we are writing Dwarf2 output we need to create a name,
4169      since complex is a fundamental type.  */
4170   if ((write_symbols == DWARF2_DEBUG || write_symbols == VMS_AND_DWARF2_DEBUG)
4171       && ! TYPE_NAME (t))
4172     {
4173       const char *name;
4174       if (component_type == char_type_node)
4175         name = "complex char";
4176       else if (component_type == signed_char_type_node)
4177         name = "complex signed char";
4178       else if (component_type == unsigned_char_type_node)
4179         name = "complex unsigned char";
4180       else if (component_type == short_integer_type_node)
4181         name = "complex short int";
4182       else if (component_type == short_unsigned_type_node)
4183         name = "complex short unsigned int";
4184       else if (component_type == integer_type_node)
4185         name = "complex int";
4186       else if (component_type == unsigned_type_node)
4187         name = "complex unsigned int";
4188       else if (component_type == long_integer_type_node)
4189         name = "complex long int";
4190       else if (component_type == long_unsigned_type_node)
4191         name = "complex long unsigned int";
4192       else if (component_type == long_long_integer_type_node)
4193         name = "complex long long int";
4194       else if (component_type == long_long_unsigned_type_node)
4195         name = "complex long long unsigned int";
4196       else
4197         name = 0;
4198
4199       if (name != 0)
4200         TYPE_NAME (t) = get_identifier (name);
4201     }
4202
4203   return t;
4204 }
4205 \f
4206 /* Return OP, stripped of any conversions to wider types as much as is safe.
4207    Converting the value back to OP's type makes a value equivalent to OP.
4208
4209    If FOR_TYPE is nonzero, we return a value which, if converted to
4210    type FOR_TYPE, would be equivalent to converting OP to type FOR_TYPE.
4211
4212    If FOR_TYPE is nonzero, unaligned bit-field references may be changed to the
4213    narrowest type that can hold the value, even if they don't exactly fit.
4214    Otherwise, bit-field references are changed to a narrower type
4215    only if they can be fetched directly from memory in that type.
4216
4217    OP must have integer, real or enumeral type.  Pointers are not allowed!
4218
4219    There are some cases where the obvious value we could return
4220    would regenerate to OP if converted to OP's type,
4221    but would not extend like OP to wider types.
4222    If FOR_TYPE indicates such extension is contemplated, we eschew such values.
4223    For example, if OP is (unsigned short)(signed char)-1,
4224    we avoid returning (signed char)-1 if FOR_TYPE is int,
4225    even though extending that to an unsigned short would regenerate OP,
4226    since the result of extending (signed char)-1 to (int)
4227    is different from (int) OP.  */
4228
4229 tree
4230 get_unwidened (tree op, tree for_type)
4231 {
4232   /* Set UNS initially if converting OP to FOR_TYPE is a zero-extension.  */
4233   tree type = TREE_TYPE (op);
4234   unsigned final_prec
4235     = TYPE_PRECISION (for_type != 0 ? for_type : type);
4236   int uns
4237     = (for_type != 0 && for_type != type
4238        && final_prec > TYPE_PRECISION (type)
4239        && TREE_UNSIGNED (type));
4240   tree win = op;
4241
4242   while (TREE_CODE (op) == NOP_EXPR)
4243     {
4244       int bitschange
4245         = TYPE_PRECISION (TREE_TYPE (op))
4246           - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0)));
4247
4248       /* Truncations are many-one so cannot be removed.
4249          Unless we are later going to truncate down even farther.  */
4250       if (bitschange < 0
4251           && final_prec > TYPE_PRECISION (TREE_TYPE (op)))
4252         break;
4253
4254       /* See what's inside this conversion.  If we decide to strip it,
4255          we will set WIN.  */
4256       op = TREE_OPERAND (op, 0);
4257
4258       /* If we have not stripped any zero-extensions (uns is 0),
4259          we can strip any kind of extension.
4260          If we have previously stripped a zero-extension,
4261          only zero-extensions can safely be stripped.
4262          Any extension can be stripped if the bits it would produce
4263          are all going to be discarded later by truncating to FOR_TYPE.  */
4264
4265       if (bitschange > 0)
4266         {
4267           if (! uns || final_prec <= TYPE_PRECISION (TREE_TYPE (op)))
4268             win = op;
4269           /* TREE_UNSIGNED says whether this is a zero-extension.
4270              Let's avoid computing it if it does not affect WIN
4271              and if UNS will not be needed again.  */
4272           if ((uns || TREE_CODE (op) == NOP_EXPR)
4273               && TREE_UNSIGNED (TREE_TYPE (op)))
4274             {
4275               uns = 1;
4276               win = op;
4277             }
4278         }
4279     }
4280
4281   if (TREE_CODE (op) == COMPONENT_REF
4282       /* Since type_for_size always gives an integer type.  */
4283       && TREE_CODE (type) != REAL_TYPE
4284       /* Don't crash if field not laid out yet.  */
4285       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
4286       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
4287     {
4288       unsigned int innerprec
4289         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
4290       int unsignedp = (TREE_UNSIGNED (TREE_OPERAND (op, 1))
4291                        || TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
4292       type = (*lang_hooks.types.type_for_size) (innerprec, unsignedp);
4293
4294       /* We can get this structure field in the narrowest type it fits in.
4295          If FOR_TYPE is 0, do this only for a field that matches the
4296          narrower type exactly and is aligned for it
4297          The resulting extension to its nominal type (a fullword type)
4298          must fit the same conditions as for other extensions.  */
4299
4300       if (type != 0
4301           && INT_CST_LT_UNSIGNED (TYPE_SIZE (type), TYPE_SIZE (TREE_TYPE (op)))
4302           && (for_type || ! DECL_BIT_FIELD (TREE_OPERAND (op, 1)))
4303           && (! uns || final_prec <= innerprec || unsignedp))
4304         {
4305           win = build (COMPONENT_REF, type, TREE_OPERAND (op, 0),
4306                        TREE_OPERAND (op, 1));
4307           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
4308           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
4309         }
4310     }
4311
4312   return win;
4313 }
4314 \f
4315 /* Return OP or a simpler expression for a narrower value
4316    which can be sign-extended or zero-extended to give back OP.
4317    Store in *UNSIGNEDP_PTR either 1 if the value should be zero-extended
4318    or 0 if the value should be sign-extended.  */
4319
4320 tree
4321 get_narrower (tree op, int *unsignedp_ptr)
4322 {
4323   int uns = 0;
4324   int first = 1;
4325   tree win = op;
4326
4327   while (TREE_CODE (op) == NOP_EXPR)
4328     {
4329       int bitschange
4330         = (TYPE_PRECISION (TREE_TYPE (op))
4331            - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0))));
4332
4333       /* Truncations are many-one so cannot be removed.  */
4334       if (bitschange < 0)
4335         break;
4336
4337       /* See what's inside this conversion.  If we decide to strip it,
4338          we will set WIN.  */
4339
4340       if (bitschange > 0)
4341         {
4342           op = TREE_OPERAND (op, 0);
4343           /* An extension: the outermost one can be stripped,
4344              but remember whether it is zero or sign extension.  */
4345           if (first)
4346             uns = TREE_UNSIGNED (TREE_TYPE (op));
4347           /* Otherwise, if a sign extension has been stripped,
4348              only sign extensions can now be stripped;
4349              if a zero extension has been stripped, only zero-extensions.  */
4350           else if (uns != TREE_UNSIGNED (TREE_TYPE (op)))
4351             break;
4352           first = 0;
4353         }
4354       else /* bitschange == 0 */
4355         {
4356           /* A change in nominal type can always be stripped, but we must
4357              preserve the unsignedness.  */
4358           if (first)
4359             uns = TREE_UNSIGNED (TREE_TYPE (op));
4360           first = 0;
4361           op = TREE_OPERAND (op, 0);
4362         }
4363
4364       win = op;
4365     }
4366
4367   if (TREE_CODE (op) == COMPONENT_REF
4368       /* Since type_for_size always gives an integer type.  */
4369       && TREE_CODE (TREE_TYPE (op)) != REAL_TYPE
4370       /* Ensure field is laid out already.  */
4371       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0)
4372     {
4373       unsigned HOST_WIDE_INT innerprec
4374         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
4375       int unsignedp = (TREE_UNSIGNED (TREE_OPERAND (op, 1))
4376                        || TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
4377       tree type = (*lang_hooks.types.type_for_size) (innerprec, unsignedp);
4378
4379       /* We can get this structure field in a narrower type that fits it,
4380          but the resulting extension to its nominal type (a fullword type)
4381          must satisfy the same conditions as for other extensions.
4382
4383          Do this only for fields that are aligned (not bit-fields),
4384          because when bit-field insns will be used there is no
4385          advantage in doing this.  */
4386
4387       if (innerprec < TYPE_PRECISION (TREE_TYPE (op))
4388           && ! DECL_BIT_FIELD (TREE_OPERAND (op, 1))
4389           && (first || uns == TREE_UNSIGNED (TREE_OPERAND (op, 1)))
4390           && type != 0)
4391         {
4392           if (first)
4393             uns = TREE_UNSIGNED (TREE_OPERAND (op, 1));
4394           win = build (COMPONENT_REF, type, TREE_OPERAND (op, 0),
4395                        TREE_OPERAND (op, 1));
4396           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
4397           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
4398         }
4399     }
4400   *unsignedp_ptr = uns;
4401   return win;
4402 }
4403 \f
4404 /* Nonzero if integer constant C has a value that is permissible
4405    for type TYPE (an INTEGER_TYPE).  */
4406
4407 int
4408 int_fits_type_p (tree c, tree type)
4409 {
4410   tree type_low_bound = TYPE_MIN_VALUE (type);
4411   tree type_high_bound = TYPE_MAX_VALUE (type);
4412   int ok_for_low_bound, ok_for_high_bound;
4413
4414   /* Perform some generic filtering first, which may allow making a decision
4415      even if the bounds are not constant.  First, negative integers never fit
4416      in unsigned types, */
4417   if ((TREE_UNSIGNED (type) && tree_int_cst_sgn (c) < 0)
4418       /* Also, unsigned integers with top bit set never fit signed types.  */
4419       || (! TREE_UNSIGNED (type)
4420           && TREE_UNSIGNED (TREE_TYPE (c)) && tree_int_cst_msb (c)))
4421     return 0;
4422
4423   /* If at least one bound of the type is a constant integer, we can check
4424      ourselves and maybe make a decision. If no such decision is possible, but
4425      this type is a subtype, try checking against that.  Otherwise, use
4426      force_fit_type, which checks against the precision.
4427
4428      Compute the status for each possibly constant bound, and return if we see
4429      one does not match. Use ok_for_xxx_bound for this purpose, assigning -1
4430      for "unknown if constant fits", 0 for "constant known *not* to fit" and 1
4431      for "constant known to fit".  */
4432
4433   ok_for_low_bound = -1;
4434   ok_for_high_bound = -1;
4435
4436   /* Check if C >= type_low_bound.  */
4437   if (type_low_bound && TREE_CODE (type_low_bound) == INTEGER_CST)
4438     {
4439       ok_for_low_bound = ! tree_int_cst_lt (c, type_low_bound);
4440       if (! ok_for_low_bound)
4441         return 0;
4442     }
4443
4444   /* Check if c <= type_high_bound.  */
4445   if (type_high_bound && TREE_CODE (type_high_bound) == INTEGER_CST)
4446     {
4447       ok_for_high_bound = ! tree_int_cst_lt (type_high_bound, c);
4448       if (! ok_for_high_bound)
4449         return 0;
4450     }
4451
4452   /* If the constant fits both bounds, the result is known.  */
4453   if (ok_for_low_bound == 1 && ok_for_high_bound == 1)
4454     return 1;
4455
4456   /* If we haven't been able to decide at this point, there nothing more we
4457      can check ourselves here. Look at the base type if we have one.  */
4458   else if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != 0)
4459     return int_fits_type_p (c, TREE_TYPE (type));
4460
4461   /* Or to force_fit_type, if nothing else.  */
4462   else
4463     {
4464       c = copy_node (c);
4465       TREE_TYPE (c) = type;
4466       return !force_fit_type (c, 0);
4467     }
4468 }
4469
4470 /* Returns true if T is, contains, or refers to a type with variable
4471    size.  This concept is more general than that of C99 'variably
4472    modified types': in C99, a struct type is never variably modified
4473    because a VLA may not appear as a structure member.  However, in
4474    GNU C code like:
4475
4476      struct S { int i[f()]; };
4477
4478    is valid, and other languages may define similar constructs.  */
4479
4480 bool
4481 variably_modified_type_p (tree type)
4482 {
4483   tree t;
4484
4485   if (type == error_mark_node)
4486     return false;
4487
4488   /* If TYPE itself has variable size, it is variably modified.
4489
4490      We do not yet have a representation of the C99 '[*]' syntax.
4491      When a representation is chosen, this function should be modified
4492      to test for that case as well.  */
4493   t = TYPE_SIZE (type);
4494   if (t && t != error_mark_node && TREE_CODE (t) != INTEGER_CST)
4495     return true;
4496
4497   switch (TREE_CODE (type))
4498     {
4499     case POINTER_TYPE:
4500     case REFERENCE_TYPE:
4501     case ARRAY_TYPE:
4502       /* If TYPE is a pointer or reference, it is variably modified if
4503          the type pointed to is variably modified.  Similarly for arrays;
4504          note that VLAs are handled by the TYPE_SIZE check above.  */
4505       return variably_modified_type_p (TREE_TYPE (type));
4506
4507     case FUNCTION_TYPE:
4508     case METHOD_TYPE:
4509       /* If TYPE is a function type, it is variably modified if any of the
4510          parameters or the return type are variably modified.  */
4511       {
4512         tree parm;
4513
4514         if (variably_modified_type_p (TREE_TYPE (type)))
4515           return true;
4516         for (parm = TYPE_ARG_TYPES (type);
4517              parm && parm != void_list_node;
4518              parm = TREE_CHAIN (parm))
4519           if (variably_modified_type_p (TREE_VALUE (parm)))
4520             return true;
4521       }
4522       break;
4523
4524     case INTEGER_TYPE:
4525       /* Scalar types are variably modified if their end points
4526          aren't constant.  */
4527       t = TYPE_MIN_VALUE (type);
4528       if (t && t != error_mark_node && TREE_CODE (t) != INTEGER_CST)
4529         return true;
4530       t = TYPE_MAX_VALUE (type);
4531       if (t && t != error_mark_node && TREE_CODE (t) != INTEGER_CST)
4532         return true;
4533       return false;
4534
4535     default:
4536       break;
4537     }
4538
4539   /* The current language may have other cases to check, but in general,
4540      all other types are not variably modified.  */
4541   return (*lang_hooks.tree_inlining.var_mod_type_p) (type);
4542 }
4543
4544 /* Given a DECL or TYPE, return the scope in which it was declared, or
4545    NULL_TREE if there is no containing scope.  */
4546
4547 tree
4548 get_containing_scope (tree t)
4549 {
4550   return (TYPE_P (t) ? TYPE_CONTEXT (t) : DECL_CONTEXT (t));
4551 }
4552
4553 /* Return the innermost context enclosing DECL that is
4554    a FUNCTION_DECL, or zero if none.  */
4555
4556 tree
4557 decl_function_context (tree decl)
4558 {
4559   tree context;
4560
4561   if (TREE_CODE (decl) == ERROR_MARK)
4562     return 0;
4563
4564   if (TREE_CODE (decl) == SAVE_EXPR)
4565     context = SAVE_EXPR_CONTEXT (decl);
4566
4567   /* C++ virtual functions use DECL_CONTEXT for the class of the vtable
4568      where we look up the function at runtime.  Such functions always take
4569      a first argument of type 'pointer to real context'.
4570
4571      C++ should really be fixed to use DECL_CONTEXT for the real context,
4572      and use something else for the "virtual context".  */
4573   else if (TREE_CODE (decl) == FUNCTION_DECL && DECL_VINDEX (decl))
4574     context
4575       = TYPE_MAIN_VARIANT
4576         (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (decl)))));
4577   else
4578     context = DECL_CONTEXT (decl);
4579
4580   while (context && TREE_CODE (context) != FUNCTION_DECL)
4581     {
4582       if (TREE_CODE (context) == BLOCK)
4583         context = BLOCK_SUPERCONTEXT (context);
4584       else
4585         context = get_containing_scope (context);
4586     }
4587
4588   return context;
4589 }
4590
4591 /* Return the innermost context enclosing DECL that is
4592    a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE, or zero if none.
4593    TYPE_DECLs and FUNCTION_DECLs are transparent to this function.  */
4594
4595 tree
4596 decl_type_context (tree decl)
4597 {
4598   tree context = DECL_CONTEXT (decl);
4599
4600   while (context)
4601     switch (TREE_CODE (context))
4602       {
4603       case NAMESPACE_DECL:
4604       case TRANSLATION_UNIT_DECL:
4605         return NULL_TREE;
4606
4607       case RECORD_TYPE:
4608       case UNION_TYPE:
4609       case QUAL_UNION_TYPE:
4610         return context;
4611
4612       case TYPE_DECL:
4613       case FUNCTION_DECL:
4614         context = DECL_CONTEXT (context);
4615         break;
4616
4617       case BLOCK:
4618         context = BLOCK_SUPERCONTEXT (context);
4619         break;
4620
4621       default:
4622         abort ();
4623       }
4624
4625   return NULL_TREE;
4626 }
4627
4628 /* CALL is a CALL_EXPR.  Return the declaration for the function
4629    called, or NULL_TREE if the called function cannot be
4630    determined.  */
4631
4632 tree
4633 get_callee_fndecl (tree call)
4634 {
4635   tree addr;
4636
4637   /* It's invalid to call this function with anything but a
4638      CALL_EXPR.  */
4639   if (TREE_CODE (call) != CALL_EXPR)
4640     abort ();
4641
4642   /* The first operand to the CALL is the address of the function
4643      called.  */
4644   addr = TREE_OPERAND (call, 0);
4645
4646   STRIP_NOPS (addr);
4647
4648   /* If this is a readonly function pointer, extract its initial value.  */
4649   if (DECL_P (addr) && TREE_CODE (addr) != FUNCTION_DECL
4650       && TREE_READONLY (addr) && ! TREE_THIS_VOLATILE (addr)
4651       && DECL_INITIAL (addr))
4652     addr = DECL_INITIAL (addr);
4653
4654   /* If the address is just `&f' for some function `f', then we know
4655      that `f' is being called.  */
4656   if (TREE_CODE (addr) == ADDR_EXPR
4657       && TREE_CODE (TREE_OPERAND (addr, 0)) == FUNCTION_DECL)
4658     return TREE_OPERAND (addr, 0);
4659
4660   /* We couldn't figure out what was being called.  Maybe the front
4661      end has some idea.  */
4662   return (*lang_hooks.lang_get_callee_fndecl) (call);
4663 }
4664
4665 /* Print debugging information about tree nodes generated during the compile,
4666    and any language-specific information.  */
4667
4668 void
4669 dump_tree_statistics (void)
4670 {
4671 #ifdef GATHER_STATISTICS
4672   int i;
4673   int total_nodes, total_bytes;
4674 #endif
4675
4676   fprintf (stderr, "\n??? tree nodes created\n\n");
4677 #ifdef GATHER_STATISTICS
4678   fprintf (stderr, "Kind                   Nodes      Bytes\n");
4679   fprintf (stderr, "---------------------------------------\n");
4680   total_nodes = total_bytes = 0;
4681   for (i = 0; i < (int) all_kinds; i++)
4682     {
4683       fprintf (stderr, "%-20s %7d %10d\n", tree_node_kind_names[i],
4684                tree_node_counts[i], tree_node_sizes[i]);
4685       total_nodes += tree_node_counts[i];
4686       total_bytes += tree_node_sizes[i];
4687     }
4688   fprintf (stderr, "---------------------------------------\n");
4689   fprintf (stderr, "%-20s %7d %10d\n", "Total", total_nodes, total_bytes);
4690   fprintf (stderr, "---------------------------------------\n");
4691 #else
4692   fprintf (stderr, "(No per-node statistics)\n");
4693 #endif
4694   print_type_hash_statistics ();
4695   (*lang_hooks.print_statistics) ();
4696 }
4697 \f
4698 #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
4699
4700 /* Generate a crc32 of a string.  */
4701
4702 unsigned
4703 crc32_string (unsigned chksum, const char *string)
4704 {
4705   do
4706     {
4707       unsigned value = *string << 24;
4708       unsigned ix;
4709
4710       for (ix = 8; ix--; value <<= 1)
4711         {
4712           unsigned feedback;
4713
4714           feedback = (value ^ chksum) & 0x80000000 ? 0x04c11db7 : 0;
4715           chksum <<= 1;
4716           chksum ^= feedback;
4717         }
4718     }
4719   while (*string++);
4720   return chksum;
4721 }
4722
4723 /* P is a string that will be used in a symbol.  Mask out any characters
4724    that are not valid in that context.  */
4725
4726 void
4727 clean_symbol_name (char *p)
4728 {
4729   for (; *p; p++)
4730     if (! (ISALNUM (*p)
4731 #ifndef NO_DOLLAR_IN_LABEL      /* this for `$'; unlikely, but... -- kr */
4732             || *p == '$'
4733 #endif
4734 #ifndef NO_DOT_IN_LABEL         /* this for `.'; unlikely, but...  */
4735             || *p == '.'
4736 #endif
4737            ))
4738       *p = '_';
4739 }
4740
4741 /* Generate a name for a function unique to this translation unit.
4742    TYPE is some string to identify the purpose of this function to the
4743    linker or collect2.  */
4744
4745 tree
4746 get_file_function_name_long (const char *type)
4747 {
4748   char *buf;
4749   const char *p;
4750   char *q;
4751
4752   if (first_global_object_name)
4753     p = first_global_object_name;
4754   else
4755     {
4756       /* We don't have anything that we know to be unique to this translation
4757          unit, so use what we do have and throw in some randomness.  */
4758       unsigned len;
4759       const char *name = weak_global_object_name;
4760       const char *file = main_input_filename;
4761
4762       if (! name)
4763         name = "";
4764       if (! file)
4765         file = input_filename;
4766
4767       len = strlen (file);
4768       q = alloca (9 * 2 + len + 1);
4769       memcpy (q, file, len + 1);
4770       clean_symbol_name (q);
4771
4772       sprintf (q + len, "_%08X_%08X", crc32_string (0, name),
4773                crc32_string (0, flag_random_seed));
4774
4775       p = q;
4776     }
4777
4778   buf = alloca (sizeof (FILE_FUNCTION_FORMAT) + strlen (p) + strlen (type));
4779
4780   /* Set up the name of the file-level functions we may need.
4781      Use a global object (which is already required to be unique over
4782      the program) rather than the file name (which imposes extra
4783      constraints).  */
4784   sprintf (buf, FILE_FUNCTION_FORMAT, type, p);
4785
4786   return get_identifier (buf);
4787 }
4788
4789 /* If KIND=='I', return a suitable global initializer (constructor) name.
4790    If KIND=='D', return a suitable global clean-up (destructor) name.  */
4791
4792 tree
4793 get_file_function_name (int kind)
4794 {
4795   char p[2];
4796
4797   p[0] = kind;
4798   p[1] = 0;
4799
4800   return get_file_function_name_long (p);
4801 }
4802 \f
4803 /* Expand (the constant part of) a SET_TYPE CONSTRUCTOR node.
4804    The result is placed in BUFFER (which has length BIT_SIZE),
4805    with one bit in each char ('\000' or '\001').
4806
4807    If the constructor is constant, NULL_TREE is returned.
4808    Otherwise, a TREE_LIST of the non-constant elements is emitted.  */
4809
4810 tree
4811 get_set_constructor_bits (tree init, char *buffer, int bit_size)
4812 {
4813   int i;
4814   tree vals;
4815   HOST_WIDE_INT domain_min
4816     = tree_low_cst (TYPE_MIN_VALUE (TYPE_DOMAIN (TREE_TYPE (init))), 0);
4817   tree non_const_bits = NULL_TREE;
4818
4819   for (i = 0; i < bit_size; i++)
4820     buffer[i] = 0;
4821
4822   for (vals = TREE_OPERAND (init, 1);
4823        vals != NULL_TREE; vals = TREE_CHAIN (vals))
4824     {
4825       if (!host_integerp (TREE_VALUE (vals), 0)
4826           || (TREE_PURPOSE (vals) != NULL_TREE
4827               && !host_integerp (TREE_PURPOSE (vals), 0)))
4828         non_const_bits
4829           = tree_cons (TREE_PURPOSE (vals), TREE_VALUE (vals), non_const_bits);
4830       else if (TREE_PURPOSE (vals) != NULL_TREE)
4831         {
4832           /* Set a range of bits to ones.  */
4833           HOST_WIDE_INT lo_index
4834             = tree_low_cst (TREE_PURPOSE (vals), 0) - domain_min;
4835           HOST_WIDE_INT hi_index
4836             = tree_low_cst (TREE_VALUE (vals), 0) - domain_min;
4837
4838           if (lo_index < 0 || lo_index >= bit_size
4839               || hi_index < 0 || hi_index >= bit_size)
4840             abort ();
4841           for (; lo_index <= hi_index; lo_index++)
4842             buffer[lo_index] = 1;
4843         }
4844       else
4845         {
4846           /* Set a single bit to one.  */
4847           HOST_WIDE_INT index
4848             = tree_low_cst (TREE_VALUE (vals), 0) - domain_min;
4849           if (index < 0 || index >= bit_size)
4850             {
4851               error ("invalid initializer for bit string");
4852               return NULL_TREE;
4853             }
4854           buffer[index] = 1;
4855         }
4856     }
4857   return non_const_bits;
4858 }
4859
4860 /* Expand (the constant part of) a SET_TYPE CONSTRUCTOR node.
4861    The result is placed in BUFFER (which is an array of bytes).
4862    If the constructor is constant, NULL_TREE is returned.
4863    Otherwise, a TREE_LIST of the non-constant elements is emitted.  */
4864
4865 tree
4866 get_set_constructor_bytes (tree init, unsigned char *buffer, int wd_size)
4867 {
4868   int i;
4869   int set_word_size = BITS_PER_UNIT;
4870   int bit_size = wd_size * set_word_size;
4871   int bit_pos = 0;
4872   unsigned char *bytep = buffer;
4873   char *bit_buffer = alloca (bit_size);
4874   tree non_const_bits = get_set_constructor_bits (init, bit_buffer, bit_size);
4875
4876   for (i = 0; i < wd_size; i++)
4877     buffer[i] = 0;
4878
4879   for (i = 0; i < bit_size; i++)
4880     {
4881       if (bit_buffer[i])
4882         {
4883           if (BYTES_BIG_ENDIAN)
4884             *bytep |= (1 << (set_word_size - 1 - bit_pos));
4885           else
4886             *bytep |= 1 << bit_pos;
4887         }
4888       bit_pos++;
4889       if (bit_pos >= set_word_size)
4890         bit_pos = 0, bytep++;
4891     }
4892   return non_const_bits;
4893 }
4894 \f
4895 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
4896 /* Complain that the tree code of NODE does not match the expected CODE.
4897    FILE, LINE, and FUNCTION are of the caller.  */
4898
4899 void
4900 tree_check_failed (const tree node, enum tree_code code, const char *file,
4901                    int line, const char *function)
4902 {
4903   internal_error ("tree check: expected %s, have %s in %s, at %s:%d",
4904                   tree_code_name[code], tree_code_name[TREE_CODE (node)],
4905                   function, trim_filename (file), line);
4906 }
4907
4908 /* Similar to above, except that we check for a class of tree
4909    code, given in CL.  */
4910
4911 void
4912 tree_class_check_failed (const tree node, int cl, const char *file,
4913                          int line, const char *function)
4914 {
4915   internal_error
4916     ("tree check: expected class '%c', have '%c' (%s) in %s, at %s:%d",
4917      cl, TREE_CODE_CLASS (TREE_CODE (node)),
4918      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
4919 }
4920
4921 /* Similar to above, except that the check is for the bounds of a TREE_VEC's
4922    (dynamically sized) vector.  */
4923
4924 void
4925 tree_vec_elt_check_failed (int idx, int len, const char *file, int line,
4926                            const char *function)
4927 {
4928   internal_error
4929     ("tree check: accessed elt %d of tree_vec with %d elts in %s, at %s:%d",
4930      idx + 1, len, function, trim_filename (file), line);
4931 }
4932
4933 /* Similar to above, except that the check is for the bounds of the operand
4934    vector of an expression node.  */
4935
4936 void
4937 tree_operand_check_failed (int idx, enum tree_code code, const char *file,
4938                            int line, const char *function)
4939 {
4940   internal_error
4941     ("tree check: accessed operand %d of %s with %d operands in %s, at %s:%d",
4942      idx + 1, tree_code_name[code], TREE_CODE_LENGTH (code),
4943      function, trim_filename (file), line);
4944 }
4945 #endif /* ENABLE_TREE_CHECKING */
4946 \f
4947 /* For a new vector type node T, build the information necessary for
4948    debugging output.  */
4949
4950 static void
4951 finish_vector_type (tree t)
4952 {
4953   layout_type (t);
4954
4955   {
4956     tree index = build_int_2 (TYPE_VECTOR_SUBPARTS (t) - 1, 0);
4957     tree array = build_array_type (TREE_TYPE (t),
4958                                    build_index_type (index));
4959     tree rt = make_node (RECORD_TYPE);
4960
4961     TYPE_FIELDS (rt) = build_decl (FIELD_DECL, get_identifier ("f"), array);
4962     DECL_CONTEXT (TYPE_FIELDS (rt)) = rt;
4963     layout_type (rt);
4964     TYPE_DEBUG_REPRESENTATION_TYPE (t) = rt;
4965     /* In dwarfout.c, type lookup uses TYPE_UID numbers.  We want to output
4966        the representation type, and we want to find that die when looking up
4967        the vector type.  This is most easily achieved by making the TYPE_UID
4968        numbers equal.  */
4969     TYPE_UID (rt) = TYPE_UID (t);
4970   }
4971 }
4972
4973 /* Create nodes for all integer types (and error_mark_node) using the sizes
4974    of C datatypes.  The caller should call set_sizetype soon after calling
4975    this function to select one of the types as sizetype.  */
4976
4977 void
4978 build_common_tree_nodes (int signed_char)
4979 {
4980   error_mark_node = make_node (ERROR_MARK);
4981   TREE_TYPE (error_mark_node) = error_mark_node;
4982
4983   initialize_sizetypes ();
4984
4985   /* Define both `signed char' and `unsigned char'.  */
4986   signed_char_type_node = make_signed_type (CHAR_TYPE_SIZE);
4987   unsigned_char_type_node = make_unsigned_type (CHAR_TYPE_SIZE);
4988
4989   /* Define `char', which is like either `signed char' or `unsigned char'
4990      but not the same as either.  */
4991   char_type_node
4992     = (signed_char
4993        ? make_signed_type (CHAR_TYPE_SIZE)
4994        : make_unsigned_type (CHAR_TYPE_SIZE));
4995
4996   short_integer_type_node = make_signed_type (SHORT_TYPE_SIZE);
4997   short_unsigned_type_node = make_unsigned_type (SHORT_TYPE_SIZE);
4998   integer_type_node = make_signed_type (INT_TYPE_SIZE);
4999   unsigned_type_node = make_unsigned_type (INT_TYPE_SIZE);
5000   long_integer_type_node = make_signed_type (LONG_TYPE_SIZE);
5001   long_unsigned_type_node = make_unsigned_type (LONG_TYPE_SIZE);
5002   long_long_integer_type_node = make_signed_type (LONG_LONG_TYPE_SIZE);
5003   long_long_unsigned_type_node = make_unsigned_type (LONG_LONG_TYPE_SIZE);
5004
5005   /* Define a boolean type.  This type only represents boolean values but
5006      may be larger than char depending on the value of BOOL_TYPE_SIZE.
5007      Front ends which want to override this size (i.e. Java) can redefine
5008      boolean_type_node before calling build_common_tree_nodes_2.  */
5009   boolean_type_node = make_unsigned_type (BOOL_TYPE_SIZE);
5010   TREE_SET_CODE (boolean_type_node, BOOLEAN_TYPE);
5011   TYPE_MAX_VALUE (boolean_type_node) = build_int_2 (1, 0);
5012   TREE_TYPE (TYPE_MAX_VALUE (boolean_type_node)) = boolean_type_node;
5013   TYPE_PRECISION (boolean_type_node) = 1;
5014
5015   intQI_type_node = make_signed_type (GET_MODE_BITSIZE (QImode));
5016   intHI_type_node = make_signed_type (GET_MODE_BITSIZE (HImode));
5017   intSI_type_node = make_signed_type (GET_MODE_BITSIZE (SImode));
5018   intDI_type_node = make_signed_type (GET_MODE_BITSIZE (DImode));
5019   intTI_type_node = make_signed_type (GET_MODE_BITSIZE (TImode));
5020
5021   unsigned_intQI_type_node = make_unsigned_type (GET_MODE_BITSIZE (QImode));
5022   unsigned_intHI_type_node = make_unsigned_type (GET_MODE_BITSIZE (HImode));
5023   unsigned_intSI_type_node = make_unsigned_type (GET_MODE_BITSIZE (SImode));
5024   unsigned_intDI_type_node = make_unsigned_type (GET_MODE_BITSIZE (DImode));
5025   unsigned_intTI_type_node = make_unsigned_type (GET_MODE_BITSIZE (TImode));
5026
5027   access_public_node = get_identifier ("public");
5028   access_protected_node = get_identifier ("protected");
5029   access_private_node = get_identifier ("private");
5030 }
5031
5032 /* Call this function after calling build_common_tree_nodes and set_sizetype.
5033    It will create several other common tree nodes.  */
5034
5035 void
5036 build_common_tree_nodes_2 (int short_double)
5037 {
5038   /* Define these next since types below may used them.  */
5039   integer_zero_node = build_int_2 (0, 0);
5040   integer_one_node = build_int_2 (1, 0);
5041   integer_minus_one_node = build_int_2 (-1, -1);
5042
5043   size_zero_node = size_int (0);
5044   size_one_node = size_int (1);
5045   bitsize_zero_node = bitsize_int (0);
5046   bitsize_one_node = bitsize_int (1);
5047   bitsize_unit_node = bitsize_int (BITS_PER_UNIT);
5048
5049   boolean_false_node = TYPE_MIN_VALUE (boolean_type_node);
5050   boolean_true_node = TYPE_MAX_VALUE (boolean_type_node);
5051
5052   void_type_node = make_node (VOID_TYPE);
5053   layout_type (void_type_node);
5054
5055   /* We are not going to have real types in C with less than byte alignment,
5056      so we might as well not have any types that claim to have it.  */
5057   TYPE_ALIGN (void_type_node) = BITS_PER_UNIT;
5058   TYPE_USER_ALIGN (void_type_node) = 0;
5059
5060   null_pointer_node = build_int_2 (0, 0);
5061   TREE_TYPE (null_pointer_node) = build_pointer_type (void_type_node);
5062   layout_type (TREE_TYPE (null_pointer_node));
5063
5064   ptr_type_node = build_pointer_type (void_type_node);
5065   const_ptr_type_node
5066     = build_pointer_type (build_type_variant (void_type_node, 1, 0));
5067
5068   float_type_node = make_node (REAL_TYPE);
5069   TYPE_PRECISION (float_type_node) = FLOAT_TYPE_SIZE;
5070   layout_type (float_type_node);
5071
5072   double_type_node = make_node (REAL_TYPE);
5073   if (short_double)
5074     TYPE_PRECISION (double_type_node) = FLOAT_TYPE_SIZE;
5075   else
5076     TYPE_PRECISION (double_type_node) = DOUBLE_TYPE_SIZE;
5077   layout_type (double_type_node);
5078
5079   long_double_type_node = make_node (REAL_TYPE);
5080   TYPE_PRECISION (long_double_type_node) = LONG_DOUBLE_TYPE_SIZE;
5081   layout_type (long_double_type_node);
5082
5083   float_ptr_type_node = build_pointer_type (float_type_node);
5084   double_ptr_type_node = build_pointer_type (double_type_node);
5085   long_double_ptr_type_node = build_pointer_type (long_double_type_node);
5086   integer_ptr_type_node = build_pointer_type (integer_type_node);
5087
5088   complex_integer_type_node = make_node (COMPLEX_TYPE);
5089   TREE_TYPE (complex_integer_type_node) = integer_type_node;
5090   layout_type (complex_integer_type_node);
5091
5092   complex_float_type_node = make_node (COMPLEX_TYPE);
5093   TREE_TYPE (complex_float_type_node) = float_type_node;
5094   layout_type (complex_float_type_node);
5095
5096   complex_double_type_node = make_node (COMPLEX_TYPE);
5097   TREE_TYPE (complex_double_type_node) = double_type_node;
5098   layout_type (complex_double_type_node);
5099
5100   complex_long_double_type_node = make_node (COMPLEX_TYPE);
5101   TREE_TYPE (complex_long_double_type_node) = long_double_type_node;
5102   layout_type (complex_long_double_type_node);
5103
5104   {
5105     tree t = (*targetm.build_builtin_va_list) ();
5106
5107     /* Many back-ends define record types without setting TYPE_NAME.
5108        If we copied the record type here, we'd keep the original
5109        record type without a name.  This breaks name mangling.  So,
5110        don't copy record types and let c_common_nodes_and_builtins()
5111        declare the type to be __builtin_va_list.  */
5112     if (TREE_CODE (t) != RECORD_TYPE)
5113       t = build_type_copy (t);
5114
5115     va_list_type_node = t;
5116   }
5117
5118   unsigned_V4SI_type_node
5119     = make_vector (V4SImode, unsigned_intSI_type_node, 1);
5120   unsigned_V2HI_type_node
5121     = make_vector (V2HImode, unsigned_intHI_type_node, 1);
5122   unsigned_V2SI_type_node
5123     = make_vector (V2SImode, unsigned_intSI_type_node, 1);
5124   unsigned_V2DI_type_node
5125     = make_vector (V2DImode, unsigned_intDI_type_node, 1);
5126   unsigned_V4HI_type_node
5127     = make_vector (V4HImode, unsigned_intHI_type_node, 1);
5128   unsigned_V8QI_type_node
5129     = make_vector (V8QImode, unsigned_intQI_type_node, 1);
5130   unsigned_V8HI_type_node
5131     = make_vector (V8HImode, unsigned_intHI_type_node, 1);
5132   unsigned_V16QI_type_node
5133     = make_vector (V16QImode, unsigned_intQI_type_node, 1);
5134   unsigned_V1DI_type_node
5135     = make_vector (V1DImode, unsigned_intDI_type_node, 1);
5136
5137   V16SF_type_node = make_vector (V16SFmode, float_type_node, 0);
5138   V4SF_type_node = make_vector (V4SFmode, float_type_node, 0);
5139   V4SI_type_node = make_vector (V4SImode, intSI_type_node, 0);
5140   V2HI_type_node = make_vector (V2HImode, intHI_type_node, 0);
5141   V2SI_type_node = make_vector (V2SImode, intSI_type_node, 0);
5142   V2DI_type_node = make_vector (V2DImode, intDI_type_node, 0);
5143   V4HI_type_node = make_vector (V4HImode, intHI_type_node, 0);
5144   V8QI_type_node = make_vector (V8QImode, intQI_type_node, 0);
5145   V8HI_type_node = make_vector (V8HImode, intHI_type_node, 0);
5146   V2SF_type_node = make_vector (V2SFmode, float_type_node, 0);
5147   V2DF_type_node = make_vector (V2DFmode, double_type_node, 0);
5148   V16QI_type_node = make_vector (V16QImode, intQI_type_node, 0);
5149   V1DI_type_node = make_vector (V1DImode, intDI_type_node, 0);
5150   V4DF_type_node = make_vector (V4DFmode, double_type_node, 0);
5151 }
5152
5153 /* HACK.  GROSS.  This is absolutely disgusting.  I wish there was a
5154    better way.
5155
5156    If we requested a pointer to a vector, build up the pointers that
5157    we stripped off while looking for the inner type.  Similarly for
5158    return values from functions.
5159
5160    The argument TYPE is the top of the chain, and BOTTOM is the
5161    new type which we will point to.  */
5162
5163 tree
5164 reconstruct_complex_type (tree type, tree bottom)
5165 {
5166   tree inner, outer;
5167
5168   if (POINTER_TYPE_P (type))
5169     {
5170       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5171       outer = build_pointer_type (inner);
5172     }
5173   else if (TREE_CODE (type) == ARRAY_TYPE)
5174     {
5175       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5176       outer = build_array_type (inner, TYPE_DOMAIN (type));
5177     }
5178   else if (TREE_CODE (type) == FUNCTION_TYPE)
5179     {
5180       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5181       outer = build_function_type (inner, TYPE_ARG_TYPES (type));
5182     }
5183   else if (TREE_CODE (type) == METHOD_TYPE)
5184     {
5185       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5186       outer = build_method_type_directly (TYPE_METHOD_BASETYPE (type),
5187                                           inner,
5188                                           TYPE_ARG_TYPES (type));
5189     }
5190   else
5191     return bottom;
5192
5193   TREE_READONLY (outer) = TREE_READONLY (type);
5194   TREE_THIS_VOLATILE (outer) = TREE_THIS_VOLATILE (type);
5195
5196   return outer;
5197 }
5198
5199 /* Returns a vector tree node given a vector mode, the inner type, and
5200    the signness.  */
5201
5202 tree
5203 make_vector (enum machine_mode mode, tree innertype, int unsignedp)
5204 {
5205   tree t;
5206
5207   t = make_node (VECTOR_TYPE);
5208   TREE_TYPE (t) = innertype;
5209   TYPE_MODE (t) = mode;
5210   TREE_UNSIGNED (TREE_TYPE (t)) = unsignedp;
5211   finish_vector_type (t);
5212
5213   return t;
5214 }
5215
5216 /* Given an initializer INIT, return TRUE if INIT is zero or some
5217    aggregate of zeros.  Otherwise return FALSE.  */
5218
5219 bool
5220 initializer_zerop (tree init)
5221 {
5222   STRIP_NOPS (init);
5223
5224   switch (TREE_CODE (init))
5225     {
5226     case INTEGER_CST:
5227       return integer_zerop (init);
5228     case REAL_CST:
5229       return real_zerop (init)
5230         && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init));
5231     case COMPLEX_CST:
5232       return integer_zerop (init)
5233         || (real_zerop (init)
5234             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init)))
5235             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init))));
5236     case CONSTRUCTOR:
5237       {
5238         /* Set is empty if it has no elements.  */
5239         if ((TREE_CODE (TREE_TYPE (init)) == SET_TYPE)
5240              && CONSTRUCTOR_ELTS (init))
5241           return false;
5242
5243         if (AGGREGATE_TYPE_P (TREE_TYPE (init)))
5244           {
5245             tree aggr_init = CONSTRUCTOR_ELTS (init);
5246
5247             while (aggr_init)
5248               {
5249                 if (! initializer_zerop (TREE_VALUE (aggr_init)))
5250                   return false;
5251                 aggr_init = TREE_CHAIN (aggr_init);
5252               }
5253             return true;
5254           }
5255         return false;
5256       }
5257     default:
5258       return false;
5259     }
5260 }
5261
5262 #include "gt-tree.h"