gcc/tree.c

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