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