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