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