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