gcc/tree.c

   1 /* Language-independent node constructors for parse phase of GNU compiler.
   2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /* This file contains the low level primitives for operating on tree nodes,
  23    including allocation, list operations, interning of identifiers,
  24    construction of data type nodes and statement nodes,
  25    and construction of type conversion nodes.  It also contains
  26    tables index by tree code that describe how to take apart
  27    nodes of that code.
  28
  29    It is intended to be language-independent, but occasionally
  30    calls language-dependent routines defined (for C) in typecheck.c.  */
  31
  32 #include "config.h"
  33 #include "system.h"
  34 #include "coretypes.h"
  35 #include "tm.h"
  36 #include "flags.h"
  37 #include "tree.h"
  38 #include "real.h"
  39 #include "tm_p.h"
  40 #include "function.h"
  41 #include "obstack.h"
  42 #include "toplev.h"
  43 #include "ggc.h"
  44 #include "hashtab.h"
  45 #include "output.h"
  46 #include "target.h"
  47 #include "langhooks.h"
  48 #include "tree-iterator.h"
  49 #include "basic-block.h"
  50 #include "tree-flow.h"
  51 #include "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 /* Returns the index of the first non-tree operand for CODE, or the number
1738    of operands if all are trees.  */
1739
1740 int
1741 first_rtl_op (enum tree_code code)
1742 {
1743   switch (code)
1744     {
1745     default:
1746       return TREE_CODE_LENGTH (code);
1747     }
1748 }
1749
1750 /* Return which tree structure is used by T.  */
1751
1752 enum tree_node_structure_enum
1753 tree_node_structure (tree t)
1754 {
1755   enum tree_code code = TREE_CODE (t);
1756
1757   switch (TREE_CODE_CLASS (code))
1758     {
1759     case tcc_declaration:
1760       return TS_DECL;
1761     case tcc_type:
1762       return TS_TYPE;
1763     case tcc_reference:
1764     case tcc_comparison:
1765     case tcc_unary:
1766     case tcc_binary:
1767     case tcc_expression:
1768     case tcc_statement:
1769       return TS_EXP;
1770     default:  /* tcc_constant and tcc_exceptional */
1771       break;
1772     }
1773   switch (code)
1774     {
1775       /* tcc_constant cases.  */
1776     case INTEGER_CST:           return TS_INT_CST;
1777     case REAL_CST:              return TS_REAL_CST;
1778     case COMPLEX_CST:           return TS_COMPLEX;
1779     case VECTOR_CST:            return TS_VECTOR;
1780     case STRING_CST:            return TS_STRING;
1781       /* tcc_exceptional cases.  */
1782     case ERROR_MARK:            return TS_COMMON;
1783     case IDENTIFIER_NODE:       return TS_IDENTIFIER;
1784     case TREE_LIST:             return TS_LIST;
1785     case TREE_VEC:              return TS_VEC;
1786     case PHI_NODE:              return TS_PHI_NODE;
1787     case SSA_NAME:              return TS_SSA_NAME;
1788     case PLACEHOLDER_EXPR:      return TS_COMMON;
1789     case STATEMENT_LIST:        return TS_STATEMENT_LIST;
1790     case BLOCK:                 return TS_BLOCK;
1791     case TREE_BINFO:            return TS_BINFO;
1792     case VALUE_HANDLE:          return TS_VALUE_HANDLE;
1793
1794     default:
1795       gcc_unreachable ();
1796     }
1797 }
1798 \f
1799 /* Return 1 if EXP contains a PLACEHOLDER_EXPR; i.e., if it represents a size
1800    or offset that depends on a field within a record.  */
1801
1802 bool
1803 contains_placeholder_p (tree exp)
1804 {
1805   enum tree_code code;
1806
1807   if (!exp)
1808     return 0;
1809
1810   code = TREE_CODE (exp);
1811   if (code == PLACEHOLDER_EXPR)
1812     return 1;
1813
1814   switch (TREE_CODE_CLASS (code))
1815     {
1816     case tcc_reference:
1817       /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit
1818          position computations since they will be converted into a
1819          WITH_RECORD_EXPR involving the reference, which will assume
1820          here will be valid.  */
1821       return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
1822
1823     case tcc_exceptional:
1824       if (code == TREE_LIST)
1825         return (CONTAINS_PLACEHOLDER_P (TREE_VALUE (exp))
1826                 || CONTAINS_PLACEHOLDER_P (TREE_CHAIN (exp)));
1827       break;
1828
1829     case tcc_unary:
1830     case tcc_binary:
1831     case tcc_comparison:
1832     case tcc_expression:
1833       switch (code)
1834         {
1835         case COMPOUND_EXPR:
1836           /* Ignoring the first operand isn't quite right, but works best.  */
1837           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
1838
1839         case COND_EXPR:
1840           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
1841                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))
1842                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2)));
1843
1844         default:
1845           break;
1846         }
1847
1848       switch (first_rtl_op (code))
1849         {
1850         case 1:
1851           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
1852         case 2:
1853           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
1854                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)));
1855         default:
1856           return 0;
1857         }
1858
1859     default:
1860       return 0;
1861     }
1862   return 0;
1863 }
1864
1865 /* Return true if any part of the computation of TYPE involves a
1866    PLACEHOLDER_EXPR.  This includes size, bounds, qualifiers
1867    (for QUAL_UNION_TYPE) and field positions.  */
1868
1869 static bool
1870 type_contains_placeholder_1 (tree type)
1871 {
1872   /* If the size contains a placeholder or the parent type (component type in
1873      the case of arrays) type involves a placeholder, this type does.  */
1874   if (CONTAINS_PLACEHOLDER_P (TYPE_SIZE (type))
1875       || CONTAINS_PLACEHOLDER_P (TYPE_SIZE_UNIT (type))
1876       || (TREE_TYPE (type) != 0
1877           && type_contains_placeholder_p (TREE_TYPE (type))))
1878     return true;
1879
1880   /* Now do type-specific checks.  Note that the last part of the check above
1881      greatly limits what we have to do below.  */
1882   switch (TREE_CODE (type))
1883     {
1884     case VOID_TYPE:
1885     case COMPLEX_TYPE:
1886     case ENUMERAL_TYPE:
1887     case BOOLEAN_TYPE:
1888     case CHAR_TYPE:
1889     case POINTER_TYPE:
1890     case OFFSET_TYPE:
1891     case REFERENCE_TYPE:
1892     case METHOD_TYPE:
1893     case FILE_TYPE:
1894     case FUNCTION_TYPE:
1895       return false;
1896
1897     case INTEGER_TYPE:
1898     case REAL_TYPE:
1899       /* Here we just check the bounds.  */
1900       return (CONTAINS_PLACEHOLDER_P (TYPE_MIN_VALUE (type))
1901               || CONTAINS_PLACEHOLDER_P (TYPE_MAX_VALUE (type)));
1902
1903     case ARRAY_TYPE:
1904     case SET_TYPE:
1905     case VECTOR_TYPE:
1906       /* We're already checked the component type (TREE_TYPE), so just check
1907          the index type.  */
1908       return type_contains_placeholder_p (TYPE_DOMAIN (type));
1909
1910     case RECORD_TYPE:
1911     case UNION_TYPE:
1912     case QUAL_UNION_TYPE:
1913       {
1914         tree field;
1915
1916         for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
1917           if (TREE_CODE (field) == FIELD_DECL
1918               && (CONTAINS_PLACEHOLDER_P (DECL_FIELD_OFFSET (field))
1919                   || (TREE_CODE (type) == QUAL_UNION_TYPE
1920                       && CONTAINS_PLACEHOLDER_P (DECL_QUALIFIER (field)))
1921                   || type_contains_placeholder_p (TREE_TYPE (field))))
1922             return true;
1923
1924         return false;
1925       }
1926
1927     default:
1928       gcc_unreachable ();
1929     }
1930 }
1931
1932 bool
1933 type_contains_placeholder_p (tree type)
1934 {
1935   bool result;
1936
1937   /* If the contains_placeholder_bits field has been initialized,
1938      then we know the answer.  */
1939   if (TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) > 0)
1940     return TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) - 1;
1941
1942   /* Indicate that we've seen this type node, and the answer is false.
1943      This is what we want to return if we run into recursion via fields.  */
1944   TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = 1;
1945
1946   /* Compute the real value.  */
1947   result = type_contains_placeholder_1 (type);
1948
1949   /* Store the real value.  */
1950   TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = result + 1;
1951
1952   return result;
1953 }
1954 \f
1955 /* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
1956    return a tree with all occurrences of references to F in a
1957    PLACEHOLDER_EXPR replaced by R.   Note that we assume here that EXP
1958    contains only arithmetic expressions or a CALL_EXPR with a
1959    PLACEHOLDER_EXPR occurring only in its arglist.  */
1960
1961 tree
1962 substitute_in_expr (tree exp, tree f, tree r)
1963 {
1964   enum tree_code code = TREE_CODE (exp);
1965   tree op0, op1, op2;
1966   tree new;
1967   tree inner;
1968
1969   /* We handle TREE_LIST and COMPONENT_REF separately.  */
1970   if (code == TREE_LIST)
1971     {
1972       op0 = SUBSTITUTE_IN_EXPR (TREE_CHAIN (exp), f, r);
1973       op1 = SUBSTITUTE_IN_EXPR (TREE_VALUE (exp), f, r);
1974       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
1975         return exp;
1976
1977       return tree_cons (TREE_PURPOSE (exp), op1, op0);
1978     }
1979   else if (code == COMPONENT_REF)
1980    {
1981      /* If this expression is getting a value from a PLACEHOLDER_EXPR
1982         and it is the right field, replace it with R.  */
1983      for (inner = TREE_OPERAND (exp, 0);
1984           REFERENCE_CLASS_P (inner);
1985           inner = TREE_OPERAND (inner, 0))
1986        ;
1987      if (TREE_CODE (inner) == PLACEHOLDER_EXPR
1988          && TREE_OPERAND (exp, 1) == f)
1989        return r;
1990
1991      /* If this expression hasn't been completed let, leave it alone.  */
1992      if (TREE_CODE (inner) == PLACEHOLDER_EXPR && TREE_TYPE (inner) == 0)
1993        return exp;
1994
1995      op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
1996      if (op0 == TREE_OPERAND (exp, 0))
1997        return exp;
1998
1999      new = fold (build3 (COMPONENT_REF, TREE_TYPE (exp),
2000                          op0, TREE_OPERAND (exp, 1), NULL_TREE));
2001    }
2002   else
2003     switch (TREE_CODE_CLASS (code))
2004       {
2005       case tcc_constant:
2006       case tcc_declaration:
2007         return exp;
2008
2009       case tcc_exceptional:
2010       case tcc_unary:
2011       case tcc_binary:
2012       case tcc_comparison:
2013       case tcc_expression:
2014       case tcc_reference:
2015         switch (first_rtl_op (code))
2016           {
2017           case 0:
2018             return exp;
2019
2020           case 1:
2021             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2022             if (op0 == TREE_OPERAND (exp, 0))
2023               return exp;
2024
2025             new = fold (build1 (code, TREE_TYPE (exp), op0));
2026             break;
2027
2028           case 2:
2029             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2030             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2031
2032             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2033               return exp;
2034
2035             new = fold (build2 (code, TREE_TYPE (exp), op0, op1));
2036             break;
2037
2038           case 3:
2039             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2040             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2041             op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
2042
2043             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2044                 && op2 == TREE_OPERAND (exp, 2))
2045               return exp;
2046
2047             new = fold (build3 (code, TREE_TYPE (exp), op0, op1, op2));
2048             break;
2049
2050           default:
2051             gcc_unreachable ();
2052           }
2053         break;
2054
2055       default:
2056         gcc_unreachable ();
2057       }
2058
2059   TREE_READONLY (new) = TREE_READONLY (exp);
2060   return new;
2061 }
2062
2063 /* Similar, but look for a PLACEHOLDER_EXPR in EXP and find a replacement
2064    for it within OBJ, a tree that is an object or a chain of references.  */
2065
2066 tree
2067 substitute_placeholder_in_expr (tree exp, tree obj)
2068 {
2069   enum tree_code code = TREE_CODE (exp);
2070   tree op0, op1, op2, op3;
2071
2072   /* If this is a PLACEHOLDER_EXPR, see if we find a corresponding type
2073      in the chain of OBJ.  */
2074   if (code == PLACEHOLDER_EXPR)
2075     {
2076       tree need_type = TYPE_MAIN_VARIANT (TREE_TYPE (exp));
2077       tree elt;
2078
2079       for (elt = obj; elt != 0;
2080            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2081                    || TREE_CODE (elt) == COND_EXPR)
2082                   ? TREE_OPERAND (elt, 1)
2083                   : (REFERENCE_CLASS_P (elt)
2084                      || UNARY_CLASS_P (elt)
2085                      || BINARY_CLASS_P (elt)
2086                      || EXPRESSION_CLASS_P (elt))
2087                   ? TREE_OPERAND (elt, 0) : 0))
2088         if (TYPE_MAIN_VARIANT (TREE_TYPE (elt)) == need_type)
2089           return elt;
2090
2091       for (elt = obj; elt != 0;
2092            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2093                    || TREE_CODE (elt) == COND_EXPR)
2094                   ? TREE_OPERAND (elt, 1)
2095                   : (REFERENCE_CLASS_P (elt)
2096                      || UNARY_CLASS_P (elt)
2097                      || BINARY_CLASS_P (elt)
2098                      || EXPRESSION_CLASS_P (elt))
2099                   ? TREE_OPERAND (elt, 0) : 0))
2100         if (POINTER_TYPE_P (TREE_TYPE (elt))
2101             && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (elt)))
2102                 == need_type))
2103           return fold (build1 (INDIRECT_REF, need_type, elt));
2104
2105       /* If we didn't find it, return the original PLACEHOLDER_EXPR.  If it
2106          survives until RTL generation, there will be an error.  */
2107       return exp;
2108     }
2109
2110   /* TREE_LIST is special because we need to look at TREE_VALUE
2111      and TREE_CHAIN, not TREE_OPERANDS.  */
2112   else if (code == TREE_LIST)
2113     {
2114       op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), obj);
2115       op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), obj);
2116       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2117         return exp;
2118
2119       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2120     }
2121   else
2122     switch (TREE_CODE_CLASS (code))
2123       {
2124       case tcc_constant:
2125       case tcc_declaration:
2126         return exp;
2127
2128       case tcc_exceptional:
2129       case tcc_unary:
2130       case tcc_binary:
2131       case tcc_comparison:
2132       case tcc_expression:
2133       case tcc_reference:
2134       case tcc_statement:
2135         switch (first_rtl_op (code))
2136           {
2137           case 0:
2138             return exp;
2139
2140           case 1:
2141             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2142             if (op0 == TREE_OPERAND (exp, 0))
2143               return exp;
2144             else
2145               return fold (build1 (code, TREE_TYPE (exp), op0));
2146
2147           case 2:
2148             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2149             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2150
2151             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2152               return exp;
2153             else
2154               return fold (build2 (code, TREE_TYPE (exp), op0, op1));
2155
2156           case 3:
2157             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2158             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2159             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2160
2161             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2162                 && op2 == TREE_OPERAND (exp, 2))
2163               return exp;
2164             else
2165               return fold (build3 (code, TREE_TYPE (exp), op0, op1, op2));
2166
2167           case 4:
2168             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2169             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2170             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2171             op3 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 3), obj);
2172
2173             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2174                 && op2 == TREE_OPERAND (exp, 2)
2175                 && op3 == TREE_OPERAND (exp, 3))
2176               return exp;
2177             else
2178               return fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2179
2180           default:
2181             gcc_unreachable ();
2182           }
2183         break;
2184
2185       default:
2186         gcc_unreachable ();
2187       }
2188 }
2189 \f
2190 /* Stabilize a reference so that we can use it any number of times
2191    without causing its operands to be evaluated more than once.
2192    Returns the stabilized reference.  This works by means of save_expr,
2193    so see the caveats in the comments about save_expr.
2194
2195    Also allows conversion expressions whose operands are references.
2196    Any other kind of expression is returned unchanged.  */
2197
2198 tree
2199 stabilize_reference (tree ref)
2200 {
2201   tree result;
2202   enum tree_code code = TREE_CODE (ref);
2203
2204   switch (code)
2205     {
2206     case VAR_DECL:
2207     case PARM_DECL:
2208     case RESULT_DECL:
2209       /* No action is needed in this case.  */
2210       return ref;
2211
2212     case NOP_EXPR:
2213     case CONVERT_EXPR:
2214     case FLOAT_EXPR:
2215     case FIX_TRUNC_EXPR:
2216     case FIX_FLOOR_EXPR:
2217     case FIX_ROUND_EXPR:
2218     case FIX_CEIL_EXPR:
2219       result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
2220       break;
2221
2222     case INDIRECT_REF:
2223       result = build_nt (INDIRECT_REF,
2224                          stabilize_reference_1 (TREE_OPERAND (ref, 0)));
2225       break;
2226
2227     case COMPONENT_REF:
2228       result = build_nt (COMPONENT_REF,
2229                          stabilize_reference (TREE_OPERAND (ref, 0)),
2230                          TREE_OPERAND (ref, 1), NULL_TREE);
2231       break;
2232
2233     case BIT_FIELD_REF:
2234       result = build_nt (BIT_FIELD_REF,
2235                          stabilize_reference (TREE_OPERAND (ref, 0)),
2236                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2237                          stabilize_reference_1 (TREE_OPERAND (ref, 2)));
2238       break;
2239
2240     case ARRAY_REF:
2241       result = build_nt (ARRAY_REF,
2242                          stabilize_reference (TREE_OPERAND (ref, 0)),
2243                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2244                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2245       break;
2246
2247     case ARRAY_RANGE_REF:
2248       result = build_nt (ARRAY_RANGE_REF,
2249                          stabilize_reference (TREE_OPERAND (ref, 0)),
2250                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2251                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2252       break;
2253
2254     case COMPOUND_EXPR:
2255       /* We cannot wrap the first expression in a SAVE_EXPR, as then
2256          it wouldn't be ignored.  This matters when dealing with
2257          volatiles.  */
2258       return stabilize_reference_1 (ref);
2259
2260       /* If arg isn't a kind of lvalue we recognize, make no change.
2261          Caller should recognize the error for an invalid lvalue.  */
2262     default:
2263       return ref;
2264
2265     case ERROR_MARK:
2266       return error_mark_node;
2267     }
2268
2269   TREE_TYPE (result) = TREE_TYPE (ref);
2270   TREE_READONLY (result) = TREE_READONLY (ref);
2271   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
2272   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
2273
2274   return result;
2275 }
2276
2277 /* Subroutine of stabilize_reference; this is called for subtrees of
2278    references.  Any expression with side-effects must be put in a SAVE_EXPR
2279    to ensure that it is only evaluated once.
2280
2281    We don't put SAVE_EXPR nodes around everything, because assigning very
2282    simple expressions to temporaries causes us to miss good opportunities
2283    for optimizations.  Among other things, the opportunity to fold in the
2284    addition of a constant into an addressing mode often gets lost, e.g.
2285    "y[i+1] += x;".  In general, we take the approach that we should not make
2286    an assignment unless we are forced into it - i.e., that any non-side effect
2287    operator should be allowed, and that cse should take care of coalescing
2288    multiple utterances of the same expression should that prove fruitful.  */
2289
2290 tree
2291 stabilize_reference_1 (tree e)
2292 {
2293   tree result;
2294   enum tree_code code = TREE_CODE (e);
2295
2296   /* We cannot ignore const expressions because it might be a reference
2297      to a const array but whose index contains side-effects.  But we can
2298      ignore things that are actual constant or that already have been
2299      handled by this function.  */
2300
2301   if (TREE_INVARIANT (e))
2302     return e;
2303
2304   switch (TREE_CODE_CLASS (code))
2305     {
2306     case tcc_exceptional:
2307     case tcc_type:
2308     case tcc_declaration:
2309     case tcc_comparison:
2310     case tcc_statement:
2311     case tcc_expression:
2312     case tcc_reference:
2313       /* If the expression has side-effects, then encase it in a SAVE_EXPR
2314          so that it will only be evaluated once.  */
2315       /* The reference (r) and comparison (<) classes could be handled as
2316          below, but it is generally faster to only evaluate them once.  */
2317       if (TREE_SIDE_EFFECTS (e))
2318         return save_expr (e);
2319       return e;
2320
2321     case tcc_constant:
2322       /* Constants need no processing.  In fact, we should never reach
2323          here.  */
2324       return e;
2325
2326     case tcc_binary:
2327       /* Division is slow and tends to be compiled with jumps,
2328          especially the division by powers of 2 that is often
2329          found inside of an array reference.  So do it just once.  */
2330       if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
2331           || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
2332           || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
2333           || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
2334         return save_expr (e);
2335       /* Recursively stabilize each operand.  */
2336       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
2337                          stabilize_reference_1 (TREE_OPERAND (e, 1)));
2338       break;
2339
2340     case tcc_unary:
2341       /* Recursively stabilize each operand.  */
2342       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
2343       break;
2344
2345     default:
2346       gcc_unreachable ();
2347     }
2348
2349   TREE_TYPE (result) = TREE_TYPE (e);
2350   TREE_READONLY (result) = TREE_READONLY (e);
2351   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
2352   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
2353   TREE_INVARIANT (result) = 1;
2354
2355   return result;
2356 }
2357 \f
2358 /* Low-level constructors for expressions.  */
2359
2360 /* A helper function for build1 and constant folders.  Set TREE_CONSTANT,
2361    TREE_INVARIANT, and TREE_SIDE_EFFECTS for an ADDR_EXPR.  */
2362
2363 void
2364 recompute_tree_invarant_for_addr_expr (tree t)
2365 {
2366   tree node;
2367   bool tc = true, ti = true, se = false;
2368
2369   /* We started out assuming this address is both invariant and constant, but
2370      does not have side effects.  Now go down any handled components and see if
2371      any of them involve offsets that are either non-constant or non-invariant.
2372      Also check for side-effects.
2373
2374      ??? Note that this code makes no attempt to deal with the case where
2375      taking the address of something causes a copy due to misalignment.  */
2376
2377 #define UPDATE_TITCSE(NODE)  \
2378 do { tree _node = (NODE); \
2379      if (_node && !TREE_INVARIANT (_node)) ti = false; \
2380      if (_node && !TREE_CONSTANT (_node)) tc = false; \
2381      if (_node && TREE_SIDE_EFFECTS (_node)) se = true; } while (0)
2382
2383   for (node = TREE_OPERAND (t, 0); handled_component_p (node);
2384        node = TREE_OPERAND (node, 0))
2385     {
2386       /* If the first operand doesn't have an ARRAY_TYPE, this is a bogus
2387          array reference (probably made temporarily by the G++ front end),
2388          so ignore all the operands.  */
2389       if ((TREE_CODE (node) == ARRAY_REF
2390            || TREE_CODE (node) == ARRAY_RANGE_REF)
2391           && TREE_CODE (TREE_TYPE (TREE_OPERAND (node, 0))) == ARRAY_TYPE)
2392         {
2393           UPDATE_TITCSE (TREE_OPERAND (node, 1));
2394           if (TREE_OPERAND (node, 2))
2395             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2396           if (TREE_OPERAND (node, 3))
2397             UPDATE_TITCSE (TREE_OPERAND (node, 3));
2398         }
2399       /* Likewise, just because this is a COMPONENT_REF doesn't mean we have a
2400          FIELD_DECL, apparently.  The G++ front end can put something else
2401          there, at least temporarily.  */
2402       else if (TREE_CODE (node) == COMPONENT_REF
2403                && TREE_CODE (TREE_OPERAND (node, 1)) == FIELD_DECL)
2404         {
2405           if (TREE_OPERAND (node, 2))
2406             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2407         }
2408       else if (TREE_CODE (node) == BIT_FIELD_REF)
2409         UPDATE_TITCSE (TREE_OPERAND (node, 2));
2410     }
2411
2412   /* Now see what's inside.  If it's an INDIRECT_REF, copy our properties from
2413      the address, since &(*a)->b is a form of addition.  If it's a decl, it's
2414      invariant and constant if the decl is static.  It's also invariant if it's
2415      a decl in the current function.  Taking the address of a volatile variable
2416      is not volatile.  If it's a constant, the address is both invariant and
2417      constant.  Otherwise it's neither.  */
2418   if (TREE_CODE (node) == INDIRECT_REF)
2419     UPDATE_TITCSE (TREE_OPERAND (node, 0));
2420   else if (DECL_P (node))
2421     {
2422       if (staticp (node))
2423         ;
2424       else if (decl_function_context (node) == current_function_decl
2425                /* Addresses of thread-local variables are invariant.  */
2426                || (TREE_CODE (node) == VAR_DECL && DECL_THREAD_LOCAL (node)))
2427         tc = false;
2428       else
2429         ti = tc = false;
2430     }
2431   else if (CONSTANT_CLASS_P (node))
2432     ;
2433   else
2434     {
2435       ti = tc = false;
2436       se |= TREE_SIDE_EFFECTS (node);
2437     }
2438
2439   TREE_CONSTANT (t) = tc;
2440   TREE_INVARIANT (t) = ti;
2441   TREE_SIDE_EFFECTS (t) = se;
2442 #undef UPDATE_TITCSE
2443 }
2444
2445 /* Build an expression of code CODE, data type TYPE, and operands as
2446    specified.  Expressions and reference nodes can be created this way.
2447    Constants, decls, types and misc nodes cannot be.
2448
2449    We define 5 non-variadic functions, from 0 to 4 arguments.  This is
2450    enough for all extant tree codes.  These functions can be called
2451    directly (preferably!), but can also be obtained via GCC preprocessor
2452    magic within the build macro.  */
2453
2454 tree
2455 build0_stat (enum tree_code code, tree tt MEM_STAT_DECL)
2456 {
2457   tree t;
2458
2459   gcc_assert (TREE_CODE_LENGTH (code) == 0);
2460
2461   t = make_node_stat (code PASS_MEM_STAT);
2462   TREE_TYPE (t) = tt;
2463
2464   return t;
2465 }
2466
2467 tree
2468 build1_stat (enum tree_code code, tree type, tree node MEM_STAT_DECL)
2469 {
2470   int length = sizeof (struct tree_exp);
2471 #ifdef GATHER_STATISTICS
2472   tree_node_kind kind;
2473 #endif
2474   tree t;
2475
2476 #ifdef GATHER_STATISTICS
2477   switch (TREE_CODE_CLASS (code))
2478     {
2479     case tcc_statement:  /* an expression with side effects */
2480       kind = s_kind;
2481       break;
2482     case tcc_reference:  /* a reference */
2483       kind = r_kind;
2484       break;
2485     default:
2486       kind = e_kind;
2487       break;
2488     }
2489
2490   tree_node_counts[(int) kind]++;
2491   tree_node_sizes[(int) kind] += length;
2492 #endif
2493
2494   gcc_assert (TREE_CODE_LENGTH (code) == 1);
2495
2496   t = ggc_alloc_zone_stat (length, tree_zone PASS_MEM_STAT);
2497
2498   memset (t, 0, sizeof (struct tree_common));
2499
2500   TREE_SET_CODE (t, code);
2501
2502   TREE_TYPE (t) = type;
2503 #ifdef USE_MAPPED_LOCATION
2504   SET_EXPR_LOCATION (t, UNKNOWN_LOCATION);
2505 #else
2506   SET_EXPR_LOCUS (t, NULL);
2507 #endif
2508   TREE_COMPLEXITY (t) = 0;
2509   TREE_OPERAND (t, 0) = node;
2510   TREE_BLOCK (t) = NULL_TREE;
2511   if (node && !TYPE_P (node) && first_rtl_op (code) != 0)
2512     {
2513       TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
2514       TREE_READONLY (t) = TREE_READONLY (node);
2515     }
2516
2517   if (TREE_CODE_CLASS (code) == tcc_statement)
2518     TREE_SIDE_EFFECTS (t) = 1;
2519   else switch (code)
2520     {
2521     case INIT_EXPR:
2522     case MODIFY_EXPR:
2523     case VA_ARG_EXPR:
2524     case PREDECREMENT_EXPR:
2525     case PREINCREMENT_EXPR:
2526     case POSTDECREMENT_EXPR:
2527     case POSTINCREMENT_EXPR:
2528       /* All of these have side-effects, no matter what their
2529          operands are.  */
2530       TREE_SIDE_EFFECTS (t) = 1;
2531       TREE_READONLY (t) = 0;
2532       break;
2533
2534     case MISALIGNED_INDIRECT_REF:
2535     case ALIGN_INDIRECT_REF:
2536     case INDIRECT_REF:
2537       /* Whether a dereference is readonly has nothing to do with whether
2538          its operand is readonly.  */
2539       TREE_READONLY (t) = 0;
2540       break;
2541
2542     case ADDR_EXPR:
2543       if (node)
2544         recompute_tree_invarant_for_addr_expr (t);
2545       break;
2546
2547     default:
2548       if (TREE_CODE_CLASS (code) == tcc_unary
2549           && node && !TYPE_P (node)
2550           && TREE_CONSTANT (node))
2551         TREE_CONSTANT (t) = 1;
2552       if (TREE_CODE_CLASS (code) == tcc_unary
2553           && node && TREE_INVARIANT (node))
2554         TREE_INVARIANT (t) = 1;
2555       if (TREE_CODE_CLASS (code) == tcc_reference
2556           && node && TREE_THIS_VOLATILE (node))
2557         TREE_THIS_VOLATILE (t) = 1;
2558       break;
2559     }
2560
2561   return t;
2562 }
2563
2564 #define PROCESS_ARG(N)                  \
2565   do {                                  \
2566     TREE_OPERAND (t, N) = arg##N;       \
2567     if (arg##N &&!TYPE_P (arg##N) && fro > N) \
2568       {                                 \
2569         if (TREE_SIDE_EFFECTS (arg##N)) \
2570           side_effects = 1;             \
2571         if (!TREE_READONLY (arg##N))    \
2572           read_only = 0;                \
2573         if (!TREE_CONSTANT (arg##N))    \
2574           constant = 0;                 \
2575         if (!TREE_INVARIANT (arg##N))   \
2576           invariant = 0;                \
2577       }                                 \
2578   } while (0)
2579
2580 tree
2581 build2_stat (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL)
2582 {
2583   bool constant, read_only, side_effects, invariant;
2584   tree t;
2585   int fro;
2586
2587   gcc_assert (TREE_CODE_LENGTH (code) == 2);
2588
2589   t = make_node_stat (code PASS_MEM_STAT);
2590   TREE_TYPE (t) = tt;
2591
2592   /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
2593      result based on those same flags for the arguments.  But if the
2594      arguments aren't really even `tree' expressions, we shouldn't be trying
2595      to do this.  */
2596   fro = first_rtl_op (code);
2597
2598   /* Expressions without side effects may be constant if their
2599      arguments are as well.  */
2600   constant = (TREE_CODE_CLASS (code) == tcc_comparison
2601               || TREE_CODE_CLASS (code) == tcc_binary);
2602   read_only = 1;
2603   side_effects = TREE_SIDE_EFFECTS (t);
2604   invariant = constant;
2605
2606   PROCESS_ARG(0);
2607   PROCESS_ARG(1);
2608
2609   TREE_READONLY (t) = read_only;
2610   TREE_CONSTANT (t) = constant;
2611   TREE_INVARIANT (t) = invariant;
2612   TREE_SIDE_EFFECTS (t) = side_effects;
2613   TREE_THIS_VOLATILE (t)
2614     = (TREE_CODE_CLASS (code) == tcc_reference
2615        && arg0 && TREE_THIS_VOLATILE (arg0));
2616
2617   return t;
2618 }
2619
2620 tree
2621 build3_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2622              tree arg2 MEM_STAT_DECL)
2623 {
2624   bool constant, read_only, side_effects, invariant;
2625   tree t;
2626   int fro;
2627
2628   gcc_assert (TREE_CODE_LENGTH (code) == 3);
2629
2630   t = make_node_stat (code PASS_MEM_STAT);
2631   TREE_TYPE (t) = tt;
2632
2633   fro = first_rtl_op (code);
2634
2635   side_effects = TREE_SIDE_EFFECTS (t);
2636
2637   PROCESS_ARG(0);
2638   PROCESS_ARG(1);
2639   PROCESS_ARG(2);
2640
2641   if (code == CALL_EXPR && !side_effects)
2642     {
2643       tree node;
2644       int i;
2645
2646       /* Calls have side-effects, except those to const or
2647          pure functions.  */
2648       i = call_expr_flags (t);
2649       if (!(i & (ECF_CONST | ECF_PURE)))
2650         side_effects = 1;
2651
2652       /* And even those have side-effects if their arguments do.  */
2653       else for (node = arg1; node; node = TREE_CHAIN (node))
2654         if (TREE_SIDE_EFFECTS (TREE_VALUE (node)))
2655           {
2656             side_effects = 1;
2657             break;
2658           }
2659     }
2660
2661   TREE_SIDE_EFFECTS (t) = side_effects;
2662   TREE_THIS_VOLATILE (t)
2663     = (TREE_CODE_CLASS (code) == tcc_reference
2664        && arg0 && TREE_THIS_VOLATILE (arg0));
2665
2666   return t;
2667 }
2668
2669 tree
2670 build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2671              tree arg2, tree arg3 MEM_STAT_DECL)
2672 {
2673   bool constant, read_only, side_effects, invariant;
2674   tree t;
2675   int fro;
2676
2677   gcc_assert (TREE_CODE_LENGTH (code) == 4);
2678
2679   t = make_node_stat (code PASS_MEM_STAT);
2680   TREE_TYPE (t) = tt;
2681
2682   fro = first_rtl_op (code);
2683
2684   side_effects = TREE_SIDE_EFFECTS (t);
2685
2686   PROCESS_ARG(0);
2687   PROCESS_ARG(1);
2688   PROCESS_ARG(2);
2689   PROCESS_ARG(3);
2690
2691   TREE_SIDE_EFFECTS (t) = side_effects;
2692   TREE_THIS_VOLATILE (t)
2693     = (TREE_CODE_CLASS (code) == tcc_reference
2694        && arg0 && TREE_THIS_VOLATILE (arg0));
2695
2696   return t;
2697 }
2698
2699 /* Backup definition for non-gcc build compilers.  */
2700
2701 tree
2702 (build) (enum tree_code code, tree tt, ...)
2703 {
2704   tree t, arg0, arg1, arg2, arg3;
2705   int length = TREE_CODE_LENGTH (code);
2706   va_list p;
2707
2708   va_start (p, tt);
2709   switch (length)
2710     {
2711     case 0:
2712       t = build0 (code, tt);
2713       break;
2714     case 1:
2715       arg0 = va_arg (p, tree);
2716       t = build1 (code, tt, arg0);
2717       break;
2718     case 2:
2719       arg0 = va_arg (p, tree);
2720       arg1 = va_arg (p, tree);
2721       t = build2 (code, tt, arg0, arg1);
2722       break;
2723     case 3:
2724       arg0 = va_arg (p, tree);
2725       arg1 = va_arg (p, tree);
2726       arg2 = va_arg (p, tree);
2727       t = build3 (code, tt, arg0, arg1, arg2);
2728       break;
2729     case 4:
2730       arg0 = va_arg (p, tree);
2731       arg1 = va_arg (p, tree);
2732       arg2 = va_arg (p, tree);
2733       arg3 = va_arg (p, tree);
2734       t = build4 (code, tt, arg0, arg1, arg2, arg3);
2735       break;
2736     default:
2737       gcc_unreachable ();
2738     }
2739   va_end (p);
2740
2741   return t;
2742 }
2743
2744 /* Similar except don't specify the TREE_TYPE
2745    and leave the TREE_SIDE_EFFECTS as 0.
2746    It is permissible for arguments to be null,
2747    or even garbage if their values do not matter.  */
2748
2749 tree
2750 build_nt (enum tree_code code, ...)
2751 {
2752   tree t;
2753   int length;
2754   int i;
2755   va_list p;
2756
2757   va_start (p, code);
2758
2759   t = make_node (code);
2760   length = TREE_CODE_LENGTH (code);
2761
2762   for (i = 0; i < length; i++)
2763     TREE_OPERAND (t, i) = va_arg (p, tree);
2764
2765   va_end (p);
2766   return t;
2767 }
2768 \f
2769 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
2770    We do NOT enter this node in any sort of symbol table.
2771
2772    layout_decl is used to set up the decl's storage layout.
2773    Other slots are initialized to 0 or null pointers.  */
2774
2775 tree
2776 build_decl_stat (enum tree_code code, tree name, tree type MEM_STAT_DECL)
2777 {
2778   tree t;
2779
2780   t = make_node_stat (code PASS_MEM_STAT);
2781
2782 /*  if (type == error_mark_node)
2783     type = integer_type_node; */
2784 /* That is not done, deliberately, so that having error_mark_node
2785    as the type can suppress useless errors in the use of this variable.  */
2786
2787   DECL_NAME (t) = name;
2788   TREE_TYPE (t) = type;
2789
2790   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
2791     layout_decl (t, 0);
2792   else if (code == FUNCTION_DECL)
2793     DECL_MODE (t) = FUNCTION_MODE;
2794
2795   /* Set default visibility to whatever the user supplied with
2796      visibility_specified depending on #pragma GCC visibility.  */
2797   DECL_VISIBILITY (t) = default_visibility;
2798   DECL_VISIBILITY_SPECIFIED (t) = visibility_options.inpragma;
2799
2800   return t;
2801 }
2802 \f
2803 /* BLOCK nodes are used to represent the structure of binding contours
2804    and declarations, once those contours have been exited and their contents
2805    compiled.  This information is used for outputting debugging info.  */
2806
2807 tree
2808 build_block (tree vars, tree tags ATTRIBUTE_UNUSED, tree subblocks,
2809              tree supercontext, tree chain)
2810 {
2811   tree block = make_node (BLOCK);
2812
2813   BLOCK_VARS (block) = vars;
2814   BLOCK_SUBBLOCKS (block) = subblocks;
2815   BLOCK_SUPERCONTEXT (block) = supercontext;
2816   BLOCK_CHAIN (block) = chain;
2817   return block;
2818 }
2819
2820 #if 1 /* ! defined(USE_MAPPED_LOCATION) */
2821 /* ??? gengtype doesn't handle conditionals */
2822 static GTY(()) tree last_annotated_node;
2823 #endif
2824
2825 #ifdef USE_MAPPED_LOCATION
2826
2827 expanded_location
2828 expand_location (source_location loc)
2829 {
2830   expanded_location xloc;
2831   if (loc == 0) { xloc.file = NULL; xloc.line = 0;  xloc.column = 0; }
2832   else
2833     {
2834       const struct line_map *map = linemap_lookup (&line_table, loc);
2835       xloc.file = map->to_file;
2836       xloc.line = SOURCE_LINE (map, loc);
2837       xloc.column = SOURCE_COLUMN (map, loc);
2838     };
2839   return xloc;
2840 }
2841
2842 #else
2843
2844 /* Record the exact location where an expression or an identifier were
2845    encountered.  */
2846
2847 void
2848 annotate_with_file_line (tree node, const char *file, int line)
2849 {
2850   /* Roughly one percent of the calls to this function are to annotate
2851      a node with the same information already attached to that node!
2852      Just return instead of wasting memory.  */
2853   if (EXPR_LOCUS (node)
2854       && (EXPR_FILENAME (node) == file
2855           || ! strcmp (EXPR_FILENAME (node), file))
2856       && EXPR_LINENO (node) == line)
2857     {
2858       last_annotated_node = node;
2859       return;
2860     }
2861
2862   /* In heavily macroized code (such as GCC itself) this single
2863      entry cache can reduce the number of allocations by more
2864      than half.  */
2865   if (last_annotated_node
2866       && EXPR_LOCUS (last_annotated_node)
2867       && (EXPR_FILENAME (last_annotated_node) == file
2868           || ! strcmp (EXPR_FILENAME (last_annotated_node), file))
2869       && EXPR_LINENO (last_annotated_node) == line)
2870     {
2871       SET_EXPR_LOCUS (node, EXPR_LOCUS (last_annotated_node));
2872       return;
2873     }
2874
2875   SET_EXPR_LOCUS (node, ggc_alloc (sizeof (location_t)));
2876   EXPR_LINENO (node) = line;
2877   EXPR_FILENAME (node) = file;
2878   last_annotated_node = node;
2879 }
2880
2881 void
2882 annotate_with_locus (tree node, location_t locus)
2883 {
2884   annotate_with_file_line (node, locus.file, locus.line);
2885 }
2886 #endif
2887 \f
2888 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
2889    is ATTRIBUTE.  */
2890
2891 tree
2892 build_decl_attribute_variant (tree ddecl, tree attribute)
2893 {
2894   DECL_ATTRIBUTES (ddecl) = attribute;
2895   return ddecl;
2896 }
2897
2898 /* Borrowed from hashtab.c iterative_hash implementation.  */
2899 #define mix(a,b,c) \
2900 { \
2901   a -= b; a -= c; a ^= (c>>13); \
2902   b -= c; b -= a; b ^= (a<< 8); \
2903   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
2904   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
2905   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
2906   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
2907   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
2908   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
2909   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
2910 }
2911
2912
2913 /* Produce good hash value combining VAL and VAL2.  */
2914 static inline hashval_t
2915 iterative_hash_hashval_t (hashval_t val, hashval_t val2)
2916 {
2917   /* the golden ratio; an arbitrary value.  */
2918   hashval_t a = 0x9e3779b9;
2919
2920   mix (a, val, val2);
2921   return val2;
2922 }
2923
2924 /* Produce good hash value combining PTR and VAL2.  */
2925 static inline hashval_t
2926 iterative_hash_pointer (void *ptr, hashval_t val2)
2927 {
2928   if (sizeof (ptr) == sizeof (hashval_t))
2929     return iterative_hash_hashval_t ((size_t) ptr, val2);
2930   else
2931     {
2932       hashval_t a = (hashval_t) (size_t) ptr;
2933       /* Avoid warnings about shifting of more than the width of the type on
2934          hosts that won't execute this path.  */
2935       int zero = 0;
2936       hashval_t b = (hashval_t) ((size_t) ptr >> (sizeof (hashval_t) * 8 + zero));
2937       mix (a, b, val2);
2938       return val2;
2939     }
2940 }
2941
2942 /* Produce good hash value combining VAL and VAL2.  */
2943 static inline hashval_t
2944 iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
2945 {
2946   if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
2947     return iterative_hash_hashval_t (val, val2);
2948   else
2949     {
2950       hashval_t a = (hashval_t) val;
2951       /* Avoid warnings about shifting of more than the width of the type on
2952          hosts that won't execute this path.  */
2953       int zero = 0;
2954       hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
2955       mix (a, b, val2);
2956       if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
2957         {
2958           hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
2959           hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
2960           mix (a, b, val2);
2961         }
2962       return val2;
2963     }
2964 }
2965
2966 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
2967    is ATTRIBUTE.
2968
2969    Record such modified types already made so we don't make duplicates.  */
2970
2971 tree
2972 build_type_attribute_variant (tree ttype, tree attribute)
2973 {
2974   if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
2975     {
2976       hashval_t hashcode = 0;
2977       tree ntype;
2978       enum tree_code code = TREE_CODE (ttype);
2979
2980       ntype = copy_node (ttype);
2981
2982       TYPE_POINTER_TO (ntype) = 0;
2983       TYPE_REFERENCE_TO (ntype) = 0;
2984       TYPE_ATTRIBUTES (ntype) = attribute;
2985
2986       /* Create a new main variant of TYPE.  */
2987       TYPE_MAIN_VARIANT (ntype) = ntype;
2988       TYPE_NEXT_VARIANT (ntype) = 0;
2989       set_type_quals (ntype, TYPE_UNQUALIFIED);
2990
2991       hashcode = iterative_hash_object (code, hashcode);
2992       if (TREE_TYPE (ntype))
2993         hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
2994                                           hashcode);
2995       hashcode = attribute_hash_list (attribute, hashcode);
2996
2997       switch (TREE_CODE (ntype))
2998         {
2999         case FUNCTION_TYPE:
3000           hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
3001           break;
3002         case ARRAY_TYPE:
3003           hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
3004                                             hashcode);
3005           break;
3006         case INTEGER_TYPE:
3007           hashcode = iterative_hash_object
3008             (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
3009           hashcode = iterative_hash_object
3010             (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
3011           break;
3012         case REAL_TYPE:
3013           {
3014             unsigned int precision = TYPE_PRECISION (ntype);
3015             hashcode = iterative_hash_object (precision, hashcode);
3016           }
3017           break;
3018         default:
3019           break;
3020         }
3021
3022       ntype = type_hash_canon (hashcode, ntype);
3023       ttype = build_qualified_type (ntype, TYPE_QUALS (ttype));
3024     }
3025
3026   return ttype;
3027 }
3028
3029 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3030    or zero if not.
3031
3032    We try both `text' and `__text__', ATTR may be either one.  */
3033 /* ??? It might be a reasonable simplification to require ATTR to be only
3034    `text'.  One might then also require attribute lists to be stored in
3035    their canonicalized form.  */
3036
3037 int
3038 is_attribute_p (const char *attr, tree ident)
3039 {
3040   int ident_len, attr_len;
3041   const char *p;
3042
3043   if (TREE_CODE (ident) != IDENTIFIER_NODE)
3044     return 0;
3045
3046   if (strcmp (attr, IDENTIFIER_POINTER (ident)) == 0)
3047     return 1;
3048
3049   p = IDENTIFIER_POINTER (ident);
3050   ident_len = strlen (p);
3051   attr_len = strlen (attr);
3052
3053   /* If ATTR is `__text__', IDENT must be `text'; and vice versa.  */
3054   if (attr[0] == '_')
3055     {
3056       gcc_assert (attr[1] == '_');
3057       gcc_assert (attr[attr_len - 2] == '_');
3058       gcc_assert (attr[attr_len - 1] == '_');
3059       gcc_assert (attr[1] == '_');
3060       if (ident_len == attr_len - 4
3061           && strncmp (attr + 2, p, attr_len - 4) == 0)
3062         return 1;
3063     }
3064   else
3065     {
3066       if (ident_len == attr_len + 4
3067           && p[0] == '_' && p[1] == '_'
3068           && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
3069           && strncmp (attr, p + 2, attr_len) == 0)
3070         return 1;
3071     }
3072
3073   return 0;
3074 }
3075
3076 /* Given an attribute name and a list of attributes, return a pointer to the
3077    attribute's list element if the attribute is part of the list, or NULL_TREE
3078    if not found.  If the attribute appears more than once, this only
3079    returns the first occurrence; the TREE_CHAIN of the return value should
3080    be passed back in if further occurrences are wanted.  */
3081
3082 tree
3083 lookup_attribute (const char *attr_name, tree list)
3084 {
3085   tree l;
3086
3087   for (l = list; l; l = TREE_CHAIN (l))
3088     {
3089       gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE);
3090       if (is_attribute_p (attr_name, TREE_PURPOSE (l)))
3091         return l;
3092     }
3093
3094   return NULL_TREE;
3095 }
3096
3097 /* Return an attribute list that is the union of a1 and a2.  */
3098
3099 tree
3100 merge_attributes (tree a1, tree a2)
3101 {
3102   tree attributes;
3103
3104   /* Either one unset?  Take the set one.  */
3105
3106   if ((attributes = a1) == 0)
3107     attributes = a2;
3108
3109   /* One that completely contains the other?  Take it.  */
3110
3111   else if (a2 != 0 && ! attribute_list_contained (a1, a2))
3112     {
3113       if (attribute_list_contained (a2, a1))
3114         attributes = a2;
3115       else
3116         {
3117           /* Pick the longest list, and hang on the other list.  */
3118
3119           if (list_length (a1) < list_length (a2))
3120             attributes = a2, a2 = a1;
3121
3122           for (; a2 != 0; a2 = TREE_CHAIN (a2))
3123             {
3124               tree a;
3125               for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3126                                          attributes);
3127                    a != NULL_TREE;
3128                    a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3129                                          TREE_CHAIN (a)))
3130                 {
3131                   if (simple_cst_equal (TREE_VALUE (a), TREE_VALUE (a2)) == 1)
3132                     break;
3133                 }
3134               if (a == NULL_TREE)
3135                 {
3136                   a1 = copy_node (a2);
3137                   TREE_CHAIN (a1) = attributes;
3138                   attributes = a1;
3139                 }
3140             }
3141         }
3142     }
3143   return attributes;
3144 }
3145
3146 /* Given types T1 and T2, merge their attributes and return
3147   the result.  */
3148
3149 tree
3150 merge_type_attributes (tree t1, tree t2)
3151 {
3152   return merge_attributes (TYPE_ATTRIBUTES (t1),
3153                            TYPE_ATTRIBUTES (t2));
3154 }
3155
3156 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
3157    the result.  */
3158
3159 tree
3160 merge_decl_attributes (tree olddecl, tree newdecl)
3161 {
3162   return merge_attributes (DECL_ATTRIBUTES (olddecl),
3163                            DECL_ATTRIBUTES (newdecl));
3164 }
3165
3166 #if TARGET_DLLIMPORT_DECL_ATTRIBUTES
3167
3168 /* Specialization of merge_decl_attributes for various Windows targets.
3169
3170    This handles the following situation:
3171
3172      __declspec (dllimport) int foo;
3173      int foo;
3174
3175    The second instance of `foo' nullifies the dllimport.  */
3176
3177 tree
3178 merge_dllimport_decl_attributes (tree old, tree new)
3179 {
3180   tree a;
3181   int delete_dllimport_p;
3182
3183   old = DECL_ATTRIBUTES (old);
3184   new = DECL_ATTRIBUTES (new);
3185
3186   /* What we need to do here is remove from `old' dllimport if it doesn't
3187      appear in `new'.  dllimport behaves like extern: if a declaration is
3188      marked dllimport and a definition appears later, then the object
3189      is not dllimport'd.  */
3190   if (lookup_attribute ("dllimport", old) != NULL_TREE
3191       && lookup_attribute ("dllimport", new) == NULL_TREE)
3192     delete_dllimport_p = 1;
3193   else
3194     delete_dllimport_p = 0;
3195
3196   a = merge_attributes (old, new);
3197
3198   if (delete_dllimport_p)
3199     {
3200       tree prev, t;
3201
3202       /* Scan the list for dllimport and delete it.  */
3203       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
3204         {
3205           if (is_attribute_p ("dllimport", TREE_PURPOSE (t)))
3206             {
3207               if (prev == NULL_TREE)
3208                 a = TREE_CHAIN (a);
3209               else
3210                 TREE_CHAIN (prev) = TREE_CHAIN (t);
3211               break;
3212             }
3213         }
3214     }
3215
3216   return a;
3217 }
3218
3219 /* Handle a "dllimport" or "dllexport" attribute; arguments as in
3220    struct attribute_spec.handler.  */
3221
3222 tree
3223 handle_dll_attribute (tree * pnode, tree name, tree args, int flags,
3224                       bool *no_add_attrs)
3225 {
3226   tree node = *pnode;
3227
3228   /* These attributes may apply to structure and union types being created,
3229      but otherwise should pass to the declaration involved.  */
3230   if (!DECL_P (node))
3231     {
3232       if (flags & ((int) ATTR_FLAG_DECL_NEXT | (int) ATTR_FLAG_FUNCTION_NEXT
3233                    | (int) ATTR_FLAG_ARRAY_NEXT))
3234         {
3235           *no_add_attrs = true;
3236           return tree_cons (name, args, NULL_TREE);
3237         }
3238       if (TREE_CODE (node) != RECORD_TYPE && TREE_CODE (node) != UNION_TYPE)
3239         {
3240           warning ("%qs attribute ignored", IDENTIFIER_POINTER (name));
3241           *no_add_attrs = true;
3242         }
3243
3244       return NULL_TREE;
3245     }
3246
3247   /* Report error on dllimport ambiguities seen now before they cause
3248      any damage.  */
3249   if (is_attribute_p ("dllimport", name))
3250     {
3251       /* Like MS, treat definition of dllimported variables and
3252          non-inlined functions on declaration as syntax errors.  We
3253          allow the attribute for function definitions if declared
3254          inline.  */
3255       if (TREE_CODE (node) == FUNCTION_DECL  && DECL_INITIAL (node)
3256           && !DECL_DECLARED_INLINE_P (node))
3257         {
3258           error ("%Jfunction %qD definition is marked dllimport.", node, node);
3259           *no_add_attrs = true;
3260         }
3261
3262       else if (TREE_CODE (node) == VAR_DECL)
3263         {
3264           if (DECL_INITIAL (node))
3265             {
3266               error ("%Jvariable %qD definition is marked dllimport.",
3267                      node, node);
3268               *no_add_attrs = true;
3269             }
3270
3271           /* `extern' needn't be specified with dllimport.
3272              Specify `extern' now and hope for the best.  Sigh.  */
3273           DECL_EXTERNAL (node) = 1;
3274           /* Also, implicitly give dllimport'd variables declared within
3275              a function global scope, unless declared static.  */
3276           if (current_function_decl != NULL_TREE && !TREE_STATIC (node))
3277             TREE_PUBLIC (node) = 1;
3278         }
3279     }
3280
3281   /*  Report error if symbol is not accessible at global scope.  */
3282   if (!TREE_PUBLIC (node)
3283       && (TREE_CODE (node) == VAR_DECL
3284           || TREE_CODE (node) == FUNCTION_DECL))
3285     {
3286       error ("%Jexternal linkage required for symbol %qD because of "
3287              "%qs attribute.", node, node, IDENTIFIER_POINTER (name));
3288       *no_add_attrs = true;
3289     }
3290
3291   return NULL_TREE;
3292 }
3293
3294 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
3295 \f
3296 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
3297    of the various TYPE_QUAL values.  */
3298
3299 static void
3300 set_type_quals (tree type, int type_quals)
3301 {
3302   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
3303   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
3304   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
3305 }
3306
3307 /* Returns true iff cand is equivalent to base with type_quals.  */
3308
3309 bool
3310 check_qualified_type (tree cand, tree base, int type_quals)
3311 {
3312   return (TYPE_QUALS (cand) == type_quals
3313           && TYPE_NAME (cand) == TYPE_NAME (base)
3314           /* Apparently this is needed for Objective-C.  */
3315           && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base)
3316           && attribute_list_equal (TYPE_ATTRIBUTES (cand),
3317                                    TYPE_ATTRIBUTES (base)));
3318 }
3319
3320 /* Return a version of the TYPE, qualified as indicated by the
3321    TYPE_QUALS, if one exists.  If no qualified version exists yet,
3322    return NULL_TREE.  */
3323
3324 tree
3325 get_qualified_type (tree type, int type_quals)
3326 {
3327   tree t;
3328
3329   if (TYPE_QUALS (type) == type_quals)
3330     return type;
3331
3332   /* Search the chain of variants to see if there is already one there just
3333      like the one we need to have.  If so, use that existing one.  We must
3334      preserve the TYPE_NAME, since there is code that depends on this.  */
3335   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
3336     if (check_qualified_type (t, type, type_quals))
3337       return t;
3338
3339   return NULL_TREE;
3340 }
3341
3342 /* Like get_qualified_type, but creates the type if it does not
3343    exist.  This function never returns NULL_TREE.  */
3344
3345 tree
3346 build_qualified_type (tree type, int type_quals)
3347 {
3348   tree t;
3349
3350   /* See if we already have the appropriate qualified variant.  */
3351   t = get_qualified_type (type, type_quals);
3352
3353   /* If not, build it.  */
3354   if (!t)
3355     {
3356       t = build_variant_type_copy (type);
3357       set_type_quals (t, type_quals);
3358     }
3359
3360   return t;
3361 }
3362
3363 /* Create a new distinct copy of TYPE.  The new type is made its own
3364    MAIN_VARIANT.  */
3365
3366 tree
3367 build_distinct_type_copy (tree type)
3368 {
3369   tree t = copy_node (type);
3370
3371   TYPE_POINTER_TO (t) = 0;
3372   TYPE_REFERENCE_TO (t) = 0;
3373
3374   /* Make it its own variant.  */
3375   TYPE_MAIN_VARIANT (t) = t;
3376   TYPE_NEXT_VARIANT (t) = 0;
3377
3378   return t;
3379 }
3380
3381 /* Create a new variant of TYPE, equivalent but distinct.
3382    This is so the caller can modify it.  */
3383
3384 tree
3385 build_variant_type_copy (tree type)
3386 {
3387   tree t, m = TYPE_MAIN_VARIANT (type);
3388
3389   t = build_distinct_type_copy (type);
3390
3391   /* Add the new type to the chain of variants of TYPE.  */
3392   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3393   TYPE_NEXT_VARIANT (m) = t;
3394   TYPE_MAIN_VARIANT (t) = m;
3395
3396   return t;
3397 }
3398 \f
3399 /* Hashing of types so that we don't make duplicates.
3400    The entry point is `type_hash_canon'.  */
3401
3402 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
3403    with types in the TREE_VALUE slots), by adding the hash codes
3404    of the individual types.  */
3405
3406 unsigned int
3407 type_hash_list (tree list, hashval_t hashcode)
3408 {
3409   tree tail;
3410
3411   for (tail = list; tail; tail = TREE_CHAIN (tail))
3412     if (TREE_VALUE (tail) != error_mark_node)
3413       hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
3414                                         hashcode);
3415
3416   return hashcode;
3417 }
3418
3419 /* These are the Hashtable callback functions.  */
3420
3421 /* Returns true iff the types are equivalent.  */
3422
3423 static int
3424 type_hash_eq (const void *va, const void *vb)
3425 {
3426   const struct type_hash *a = va, *b = vb;
3427
3428   /* First test the things that are the same for all types.  */
3429   if (a->hash != b->hash
3430       || TREE_CODE (a->type) != TREE_CODE (b->type)
3431       || TREE_TYPE (a->type) != TREE_TYPE (b->type)
3432       || !attribute_list_equal (TYPE_ATTRIBUTES (a->type),
3433                                  TYPE_ATTRIBUTES (b->type))
3434       || TYPE_ALIGN (a->type) != TYPE_ALIGN (b->type)
3435       || TYPE_MODE (a->type) != TYPE_MODE (b->type))
3436     return 0;
3437
3438   switch (TREE_CODE (a->type))
3439     {
3440     case VOID_TYPE:
3441     case COMPLEX_TYPE:
3442     case POINTER_TYPE:
3443     case REFERENCE_TYPE:
3444       return 1;
3445
3446     case VECTOR_TYPE:
3447       return TYPE_VECTOR_SUBPARTS (a->type) == TYPE_VECTOR_SUBPARTS (b->type);
3448
3449     case ENUMERAL_TYPE:
3450       if (TYPE_VALUES (a->type) != TYPE_VALUES (b->type)
3451           && !(TYPE_VALUES (a->type)
3452                && TREE_CODE (TYPE_VALUES (a->type)) == TREE_LIST
3453                && TYPE_VALUES (b->type)
3454                && TREE_CODE (TYPE_VALUES (b->type)) == TREE_LIST
3455                && type_list_equal (TYPE_VALUES (a->type),
3456                                    TYPE_VALUES (b->type))))
3457         return 0;
3458
3459       /* ... fall through ... */
3460
3461     case INTEGER_TYPE:
3462     case REAL_TYPE:
3463     case BOOLEAN_TYPE:
3464     case CHAR_TYPE:
3465       return ((TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
3466                || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
3467                                       TYPE_MAX_VALUE (b->type)))
3468               && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
3469                   || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
3470                                          TYPE_MIN_VALUE (b->type))));
3471
3472     case OFFSET_TYPE:
3473       return TYPE_OFFSET_BASETYPE (a->type) == TYPE_OFFSET_BASETYPE (b->type);
3474
3475     case METHOD_TYPE:
3476       return (TYPE_METHOD_BASETYPE (a->type) == TYPE_METHOD_BASETYPE (b->type)
3477               && (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
3478                   || (TYPE_ARG_TYPES (a->type)
3479                       && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
3480                       && TYPE_ARG_TYPES (b->type)
3481                       && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
3482                       && type_list_equal (TYPE_ARG_TYPES (a->type),
3483                                           TYPE_ARG_TYPES (b->type)))));
3484
3485     case ARRAY_TYPE:
3486     case SET_TYPE:
3487       return TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type);
3488
3489     case RECORD_TYPE:
3490     case UNION_TYPE:
3491     case QUAL_UNION_TYPE:
3492       return (TYPE_FIELDS (a->type) == TYPE_FIELDS (b->type)
3493               || (TYPE_FIELDS (a->type)
3494                   && TREE_CODE (TYPE_FIELDS (a->type)) == TREE_LIST
3495                   && TYPE_FIELDS (b->type)
3496                   && TREE_CODE (TYPE_FIELDS (b->type)) == TREE_LIST
3497                   && type_list_equal (TYPE_FIELDS (a->type),
3498                                       TYPE_FIELDS (b->type))));
3499
3500     case FUNCTION_TYPE:
3501       return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
3502               || (TYPE_ARG_TYPES (a->type)
3503                   && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
3504                   && TYPE_ARG_TYPES (b->type)
3505                   && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
3506                   && type_list_equal (TYPE_ARG_TYPES (a->type),
3507                                       TYPE_ARG_TYPES (b->type))));
3508
3509     default:
3510       return 0;
3511     }
3512 }
3513
3514 /* Return the cached hash value.  */
3515
3516 static hashval_t
3517 type_hash_hash (const void *item)
3518 {
3519   return ((const struct type_hash *) item)->hash;
3520 }
3521
3522 /* Look in the type hash table for a type isomorphic to TYPE.
3523    If one is found, return it.  Otherwise return 0.  */
3524
3525 tree
3526 type_hash_lookup (hashval_t hashcode, tree type)
3527 {
3528   struct type_hash *h, in;
3529
3530   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
3531      must call that routine before comparing TYPE_ALIGNs.  */
3532   layout_type (type);
3533
3534   in.hash = hashcode;
3535   in.type = type;
3536
3537   h = htab_find_with_hash (type_hash_table, &in, hashcode);
3538   if (h)
3539     return h->type;
3540   return NULL_TREE;
3541 }
3542
3543 /* Add an entry to the type-hash-table
3544    for a type TYPE whose hash code is HASHCODE.  */
3545
3546 void
3547 type_hash_add (hashval_t hashcode, tree type)
3548 {
3549   struct type_hash *h;
3550   void **loc;
3551
3552   h = ggc_alloc (sizeof (struct type_hash));
3553   h->hash = hashcode;
3554   h->type = type;
3555   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
3556   *(struct type_hash **) loc = h;
3557 }
3558
3559 /* Given TYPE, and HASHCODE its hash code, return the canonical
3560    object for an identical type if one already exists.
3561    Otherwise, return TYPE, and record it as the canonical object.
3562
3563    To use this function, first create a type of the sort you want.
3564    Then compute its hash code from the fields of the type that
3565    make it different from other similar types.
3566    Then call this function and use the value.  */
3567
3568 tree
3569 type_hash_canon (unsigned int hashcode, tree type)
3570 {
3571   tree t1;
3572
3573   /* The hash table only contains main variants, so ensure that's what we're
3574      being passed.  */
3575   gcc_assert (TYPE_MAIN_VARIANT (type) == type);
3576
3577   if (!lang_hooks.types.hash_types)
3578     return type;
3579
3580   /* See if the type is in the hash table already.  If so, return it.
3581      Otherwise, add the type.  */
3582   t1 = type_hash_lookup (hashcode, type);
3583   if (t1 != 0)
3584     {
3585 #ifdef GATHER_STATISTICS
3586       tree_node_counts[(int) t_kind]--;
3587       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
3588 #endif
3589       return t1;
3590     }
3591   else
3592     {
3593       type_hash_add (hashcode, type);
3594       return type;
3595     }
3596 }
3597
3598 /* See if the data pointed to by the type hash table is marked.  We consider
3599    it marked if the type is marked or if a debug type number or symbol
3600    table entry has been made for the type.  This reduces the amount of
3601    debugging output and eliminates that dependency of the debug output on
3602    the number of garbage collections.  */
3603
3604 static int
3605 type_hash_marked_p (const void *p)
3606 {
3607   tree type = ((struct type_hash *) p)->type;
3608
3609   return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
3610 }
3611
3612 static void
3613 print_type_hash_statistics (void)
3614 {
3615   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
3616            (long) htab_size (type_hash_table),
3617            (long) htab_elements (type_hash_table),
3618            htab_collisions (type_hash_table));
3619 }
3620
3621 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
3622    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
3623    by adding the hash codes of the individual attributes.  */
3624
3625 unsigned int
3626 attribute_hash_list (tree list, hashval_t hashcode)
3627 {
3628   tree tail;
3629
3630   for (tail = list; tail; tail = TREE_CHAIN (tail))
3631     /* ??? Do we want to add in TREE_VALUE too? */
3632     hashcode = iterative_hash_object
3633       (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode);
3634   return hashcode;
3635 }
3636
3637 /* Given two lists of attributes, return true if list l2 is
3638    equivalent to l1.  */
3639
3640 int
3641 attribute_list_equal (tree l1, tree l2)
3642 {
3643   return attribute_list_contained (l1, l2)
3644          && attribute_list_contained (l2, l1);
3645 }
3646
3647 /* Given two lists of attributes, return true if list L2 is
3648    completely contained within L1.  */
3649 /* ??? This would be faster if attribute names were stored in a canonicalized
3650    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
3651    must be used to show these elements are equivalent (which they are).  */
3652 /* ??? It's not clear that attributes with arguments will always be handled
3653    correctly.  */
3654
3655 int
3656 attribute_list_contained (tree l1, tree l2)
3657 {
3658   tree t1, t2;
3659
3660   /* First check the obvious, maybe the lists are identical.  */
3661   if (l1 == l2)
3662     return 1;
3663
3664   /* Maybe the lists are similar.  */
3665   for (t1 = l1, t2 = l2;
3666        t1 != 0 && t2 != 0
3667         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
3668         && TREE_VALUE (t1) == TREE_VALUE (t2);
3669        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
3670
3671   /* Maybe the lists are equal.  */
3672   if (t1 == 0 && t2 == 0)
3673     return 1;
3674
3675   for (; t2 != 0; t2 = TREE_CHAIN (t2))
3676     {
3677       tree attr;
3678       for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
3679            attr != NULL_TREE;
3680            attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
3681                                     TREE_CHAIN (attr)))
3682         {
3683           if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
3684             break;
3685         }
3686
3687       if (attr == 0)
3688         return 0;
3689
3690       if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) != 1)
3691         return 0;
3692     }
3693
3694   return 1;
3695 }
3696
3697 /* Given two lists of types
3698    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
3699    return 1 if the lists contain the same types in the same order.
3700    Also, the TREE_PURPOSEs must match.  */
3701
3702 int
3703 type_list_equal (tree l1, tree l2)
3704 {
3705   tree t1, t2;
3706
3707   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
3708     if (TREE_VALUE (t1) != TREE_VALUE (t2)
3709         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
3710             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
3711                   && (TREE_TYPE (TREE_PURPOSE (t1))
3712                       == TREE_TYPE (TREE_PURPOSE (t2))))))
3713       return 0;
3714
3715   return t1 == t2;
3716 }
3717
3718 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
3719    given by TYPE.  If the argument list accepts variable arguments,
3720    then this function counts only the ordinary arguments.  */
3721
3722 int
3723 type_num_arguments (tree type)
3724 {
3725   int i = 0;
3726   tree t;
3727
3728   for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
3729     /* If the function does not take a variable number of arguments,
3730        the last element in the list will have type `void'.  */
3731     if (VOID_TYPE_P (TREE_VALUE (t)))
3732       break;
3733     else
3734       ++i;
3735
3736   return i;
3737 }
3738
3739 /* Nonzero if integer constants T1 and T2
3740    represent the same constant value.  */
3741
3742 int
3743 tree_int_cst_equal (tree t1, tree t2)
3744 {
3745   if (t1 == t2)
3746     return 1;
3747
3748   if (t1 == 0 || t2 == 0)
3749     return 0;
3750
3751   if (TREE_CODE (t1) == INTEGER_CST
3752       && TREE_CODE (t2) == INTEGER_CST
3753       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3754       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
3755     return 1;
3756
3757   return 0;
3758 }
3759
3760 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
3761    The precise way of comparison depends on their data type.  */
3762
3763 int
3764 tree_int_cst_lt (tree t1, tree t2)
3765 {
3766   if (t1 == t2)
3767     return 0;
3768
3769   if (TYPE_UNSIGNED (TREE_TYPE (t1)) != TYPE_UNSIGNED (TREE_TYPE (t2)))
3770     {
3771       int t1_sgn = tree_int_cst_sgn (t1);
3772       int t2_sgn = tree_int_cst_sgn (t2);
3773
3774       if (t1_sgn < t2_sgn)
3775         return 1;
3776       else if (t1_sgn > t2_sgn)
3777         return 0;
3778       /* Otherwise, both are non-negative, so we compare them as
3779          unsigned just in case one of them would overflow a signed
3780          type.  */
3781     }
3782   else if (!TYPE_UNSIGNED (TREE_TYPE (t1)))
3783     return INT_CST_LT (t1, t2);
3784
3785   return INT_CST_LT_UNSIGNED (t1, t2);
3786 }
3787
3788 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
3789
3790 int
3791 tree_int_cst_compare (tree t1, tree t2)
3792 {
3793   if (tree_int_cst_lt (t1, t2))
3794     return -1;
3795   else if (tree_int_cst_lt (t2, t1))
3796     return 1;
3797   else
3798     return 0;
3799 }
3800
3801 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
3802    the host.  If POS is zero, the value can be represented in a single
3803    HOST_WIDE_INT.  If POS is nonzero, the value must be positive and can
3804    be represented in a single unsigned HOST_WIDE_INT.  */
3805
3806 int
3807 host_integerp (tree t, int pos)
3808 {
3809   return (TREE_CODE (t) == INTEGER_CST
3810           && ! TREE_OVERFLOW (t)
3811           && ((TREE_INT_CST_HIGH (t) == 0
3812                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
3813               || (! pos && TREE_INT_CST_HIGH (t) == -1
3814                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
3815                   && !TYPE_UNSIGNED (TREE_TYPE (t)))
3816               || (pos && TREE_INT_CST_HIGH (t) == 0)));
3817 }
3818
3819 /* Return the HOST_WIDE_INT least significant bits of T if it is an
3820    INTEGER_CST and there is no overflow.  POS is nonzero if the result must
3821    be positive.  Abort if we cannot satisfy the above conditions.  */
3822
3823 HOST_WIDE_INT
3824 tree_low_cst (tree t, int pos)
3825 {
3826   gcc_assert (host_integerp (t, pos));
3827   return TREE_INT_CST_LOW (t);
3828 }
3829
3830 /* Return the most significant bit of the integer constant T.  */
3831
3832 int
3833 tree_int_cst_msb (tree t)
3834 {
3835   int prec;
3836   HOST_WIDE_INT h;
3837   unsigned HOST_WIDE_INT l;
3838
3839   /* Note that using TYPE_PRECISION here is wrong.  We care about the
3840      actual bits, not the (arbitrary) range of the type.  */
3841   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
3842   rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
3843                  2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
3844   return (l & 1) == 1;
3845 }
3846
3847 /* Return an indication of the sign of the integer constant T.
3848    The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
3849    Note that -1 will never be returned it T's type is unsigned.  */
3850
3851 int
3852 tree_int_cst_sgn (tree t)
3853 {
3854   if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
3855     return 0;
3856   else if (TYPE_UNSIGNED (TREE_TYPE (t)))
3857     return 1;
3858   else if (TREE_INT_CST_HIGH (t) < 0)
3859     return -1;
3860   else
3861     return 1;
3862 }
3863
3864 /* Compare two constructor-element-type constants.  Return 1 if the lists
3865    are known to be equal; otherwise return 0.  */
3866
3867 int
3868 simple_cst_list_equal (tree l1, tree l2)
3869 {
3870   while (l1 != NULL_TREE && l2 != NULL_TREE)
3871     {
3872       if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
3873         return 0;
3874
3875       l1 = TREE_CHAIN (l1);
3876       l2 = TREE_CHAIN (l2);
3877     }
3878
3879   return l1 == l2;
3880 }
3881
3882 /* Return truthvalue of whether T1 is the same tree structure as T2.
3883    Return 1 if they are the same.
3884    Return 0 if they are understandably different.
3885    Return -1 if either contains tree structure not understood by
3886    this function.  */
3887
3888 int
3889 simple_cst_equal (tree t1, tree t2)
3890 {
3891   enum tree_code code1, code2;
3892   int cmp;
3893   int i;
3894
3895   if (t1 == t2)
3896     return 1;
3897   if (t1 == 0 || t2 == 0)
3898     return 0;
3899
3900   code1 = TREE_CODE (t1);
3901   code2 = TREE_CODE (t2);
3902
3903   if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
3904     {
3905       if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3906           || code2 == NON_LVALUE_EXPR)
3907         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3908       else
3909         return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
3910     }
3911
3912   else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3913            || code2 == NON_LVALUE_EXPR)
3914     return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
3915
3916   if (code1 != code2)
3917     return 0;
3918
3919   switch (code1)
3920     {
3921     case INTEGER_CST:
3922       return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3923               && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
3924
3925     case REAL_CST:
3926       return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
3927
3928     case STRING_CST:
3929       return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
3930               && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
3931                          TREE_STRING_LENGTH (t1)));
3932
3933     case CONSTRUCTOR:
3934       return simple_cst_list_equal (CONSTRUCTOR_ELTS (t1),
3935                                     CONSTRUCTOR_ELTS (t2));
3936
3937     case SAVE_EXPR:
3938       return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3939
3940     case CALL_EXPR:
3941       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3942       if (cmp <= 0)
3943         return cmp;
3944       return
3945         simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3946
3947     case TARGET_EXPR:
3948       /* Special case: if either target is an unallocated VAR_DECL,
3949          it means that it's going to be unified with whatever the
3950          TARGET_EXPR is really supposed to initialize, so treat it
3951          as being equivalent to anything.  */
3952       if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
3953            && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
3954            && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
3955           || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
3956               && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
3957               && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
3958         cmp = 1;
3959       else
3960         cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3961
3962       if (cmp <= 0)
3963         return cmp;
3964
3965       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3966
3967     case WITH_CLEANUP_EXPR:
3968       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3969       if (cmp <= 0)
3970         return cmp;
3971
3972       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
3973
3974     case COMPONENT_REF:
3975       if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
3976         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3977
3978       return 0;
3979
3980     case VAR_DECL:
3981     case PARM_DECL:
3982     case CONST_DECL:
3983     case FUNCTION_DECL:
3984       return 0;
3985
3986     default:
3987       break;
3988     }
3989
3990   /* This general rule works for most tree codes.  All exceptions should be
3991      handled above.  If this is a language-specific tree code, we can't
3992      trust what might be in the operand, so say we don't know
3993      the situation.  */
3994   if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
3995     return -1;
3996
3997   switch (TREE_CODE_CLASS (code1))
3998     {
3999     case tcc_unary:
4000     case tcc_binary:
4001     case tcc_comparison:
4002     case tcc_expression:
4003     case tcc_reference:
4004     case tcc_statement:
4005       cmp = 1;
4006       for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
4007         {
4008           cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
4009           if (cmp <= 0)
4010             return cmp;
4011         }
4012
4013       return cmp;
4014
4015     default:
4016       return -1;
4017     }
4018 }
4019
4020 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
4021    Return -1, 0, or 1 if the value of T is less than, equal to, or greater
4022    than U, respectively.  */
4023
4024 int
4025 compare_tree_int (tree t, unsigned HOST_WIDE_INT u)
4026 {
4027   if (tree_int_cst_sgn (t) < 0)
4028     return -1;
4029   else if (TREE_INT_CST_HIGH (t) != 0)
4030     return 1;
4031   else if (TREE_INT_CST_LOW (t) == u)
4032     return 0;
4033   else if (TREE_INT_CST_LOW (t) < u)
4034     return -1;
4035   else
4036     return 1;
4037 }
4038
4039 /* Return true if CODE represents an associative tree code.  Otherwise
4040    return false.  */
4041 bool
4042 associative_tree_code (enum tree_code code)
4043 {
4044   switch (code)
4045     {
4046     case BIT_IOR_EXPR:
4047     case BIT_AND_EXPR:
4048     case BIT_XOR_EXPR:
4049     case PLUS_EXPR:
4050     case MULT_EXPR:
4051     case MIN_EXPR:
4052     case MAX_EXPR:
4053       return true;
4054
4055     default:
4056       break;
4057     }
4058   return false;
4059 }
4060
4061 /* Return true if CODE represents a commutative tree code.  Otherwise
4062    return false.  */
4063 bool
4064 commutative_tree_code (enum tree_code code)
4065 {
4066   switch (code)
4067     {
4068     case PLUS_EXPR:
4069     case MULT_EXPR:
4070     case MIN_EXPR:
4071     case MAX_EXPR:
4072     case BIT_IOR_EXPR:
4073     case BIT_XOR_EXPR:
4074     case BIT_AND_EXPR:
4075     case NE_EXPR:
4076     case EQ_EXPR:
4077     case UNORDERED_EXPR:
4078     case ORDERED_EXPR:
4079     case UNEQ_EXPR:
4080     case LTGT_EXPR:
4081     case TRUTH_AND_EXPR:
4082     case TRUTH_XOR_EXPR:
4083     case TRUTH_OR_EXPR:
4084       return true;
4085
4086     default:
4087       break;
4088     }
4089   return false;
4090 }
4091
4092 /* Generate a hash value for an expression.  This can be used iteratively
4093    by passing a previous result as the "val" argument.
4094
4095    This function is intended to produce the same hash for expressions which
4096    would compare equal using operand_equal_p.  */
4097
4098 hashval_t
4099 iterative_hash_expr (tree t, hashval_t val)
4100 {
4101   int i;
4102   enum tree_code code;
4103   char class;
4104
4105   if (t == NULL_TREE)
4106     return iterative_hash_pointer (t, val);
4107
4108   code = TREE_CODE (t);
4109
4110   switch (code)
4111     {
4112     /* Alas, constants aren't shared, so we can't rely on pointer
4113        identity.  */
4114     case INTEGER_CST:
4115       val = iterative_hash_host_wide_int (TREE_INT_CST_LOW (t), val);
4116       return iterative_hash_host_wide_int (TREE_INT_CST_HIGH (t), val);
4117     case REAL_CST:
4118       {
4119         unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t));
4120
4121         return iterative_hash_hashval_t (val2, val);
4122       }
4123     case STRING_CST:
4124       return iterative_hash (TREE_STRING_POINTER (t),
4125                              TREE_STRING_LENGTH (t), val);
4126     case COMPLEX_CST:
4127       val = iterative_hash_expr (TREE_REALPART (t), val);
4128       return iterative_hash_expr (TREE_IMAGPART (t), val);
4129     case VECTOR_CST:
4130       return iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val);
4131
4132     case SSA_NAME:
4133     case VALUE_HANDLE:
4134       /* we can just compare by pointer.  */
4135       return iterative_hash_pointer (t, val);
4136
4137     case TREE_LIST:
4138       /* A list of expressions, for a CALL_EXPR or as the elements of a
4139          VECTOR_CST.  */
4140       for (; t; t = TREE_CHAIN (t))
4141         val = iterative_hash_expr (TREE_VALUE (t), val);
4142       return val;
4143     default:
4144       class = TREE_CODE_CLASS (code);
4145
4146       if (class == tcc_declaration)
4147         {
4148           /* Decls we can just compare by pointer.  */
4149           val = iterative_hash_pointer (t, val);
4150         }
4151       else
4152         {
4153           gcc_assert (IS_EXPR_CODE_CLASS (class));
4154
4155           val = iterative_hash_object (code, val);
4156
4157           /* Don't hash the type, that can lead to having nodes which
4158              compare equal according to operand_equal_p, but which
4159              have different hash codes.  */
4160           if (code == NOP_EXPR
4161               || code == CONVERT_EXPR
4162               || code == NON_LVALUE_EXPR)
4163             {
4164               /* Make sure to include signness in the hash computation.  */
4165               val += TYPE_UNSIGNED (TREE_TYPE (t));
4166               val = iterative_hash_expr (TREE_OPERAND (t, 0), val);
4167             }
4168
4169           else if (commutative_tree_code (code))
4170             {
4171               /* It's a commutative expression.  We want to hash it the same
4172                  however it appears.  We do this by first hashing both operands
4173                  and then rehashing based on the order of their independent
4174                  hashes.  */
4175               hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
4176               hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0);
4177               hashval_t t;
4178
4179               if (one > two)
4180                 t = one, one = two, two = t;
4181
4182               val = iterative_hash_hashval_t (one, val);
4183               val = iterative_hash_hashval_t (two, val);
4184             }
4185           else
4186             for (i = first_rtl_op (code) - 1; i >= 0; --i)
4187               val = iterative_hash_expr (TREE_OPERAND (t, i), val);
4188         }
4189       return val;
4190       break;
4191     }
4192 }
4193 \f
4194 /* Constructors for pointer, array and function types.
4195    (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
4196    constructed by language-dependent code, not here.)  */
4197
4198 /* Construct, lay out and return the type of pointers to TO_TYPE with
4199    mode MODE.  If CAN_ALIAS_ALL is TRUE, indicate this type can
4200    reference all of memory. If such a type has already been
4201    constructed, reuse it.  */
4202
4203 tree
4204 build_pointer_type_for_mode (tree to_type, enum machine_mode mode,
4205                              bool can_alias_all)
4206 {
4207   tree t;
4208
4209   /* In some cases, languages will have things that aren't a POINTER_TYPE
4210      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_POINTER_TO.
4211      In that case, return that type without regard to the rest of our
4212      operands.
4213
4214      ??? This is a kludge, but consistent with the way this function has
4215      always operated and there doesn't seem to be a good way to avoid this
4216      at the moment.  */
4217   if (TYPE_POINTER_TO (to_type) != 0
4218       && TREE_CODE (TYPE_POINTER_TO (to_type)) != POINTER_TYPE)
4219     return TYPE_POINTER_TO (to_type);
4220
4221   /* First, if we already have a type for pointers to TO_TYPE and it's
4222      the proper mode, use it.  */
4223   for (t = TYPE_POINTER_TO (to_type); t; t = TYPE_NEXT_PTR_TO (t))
4224     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4225       return t;
4226
4227   t = make_node (POINTER_TYPE);
4228
4229   TREE_TYPE (t) = to_type;
4230   TYPE_MODE (t) = mode;
4231   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4232   TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
4233   TYPE_POINTER_TO (to_type) = t;
4234
4235   /* Lay out the type.  This function has many callers that are concerned
4236      with expression-construction, and this simplifies them all.  */
4237   layout_type (t);
4238
4239   return t;
4240 }
4241
4242 /* By default build pointers in ptr_mode.  */
4243
4244 tree
4245 build_pointer_type (tree to_type)
4246 {
4247   return build_pointer_type_for_mode (to_type, ptr_mode, false);
4248 }
4249
4250 /* Same as build_pointer_type_for_mode, but for REFERENCE_TYPE.  */
4251
4252 tree
4253 build_reference_type_for_mode (tree to_type, enum machine_mode mode,
4254                                bool can_alias_all)
4255 {
4256   tree t;
4257
4258   /* In some cases, languages will have things that aren't a REFERENCE_TYPE
4259      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_REFERENCE_TO.
4260      In that case, return that type without regard to the rest of our
4261      operands.
4262
4263      ??? This is a kludge, but consistent with the way this function has
4264      always operated and there doesn't seem to be a good way to avoid this
4265      at the moment.  */
4266   if (TYPE_REFERENCE_TO (to_type) != 0
4267       && TREE_CODE (TYPE_REFERENCE_TO (to_type)) != REFERENCE_TYPE)
4268     return TYPE_REFERENCE_TO (to_type);
4269
4270   /* First, if we already have a type for pointers to TO_TYPE and it's
4271      the proper mode, use it.  */
4272   for (t = TYPE_REFERENCE_TO (to_type); t; t = TYPE_NEXT_REF_TO (t))
4273     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4274       return t;
4275
4276   t = make_node (REFERENCE_TYPE);
4277
4278   TREE_TYPE (t) = to_type;
4279   TYPE_MODE (t) = mode;
4280   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4281   TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
4282   TYPE_REFERENCE_TO (to_type) = t;
4283
4284   layout_type (t);
4285
4286   return t;
4287 }
4288
4289
4290 /* Build the node for the type of references-to-TO_TYPE by default
4291    in ptr_mode.  */
4292
4293 tree
4294 build_reference_type (tree to_type)
4295 {
4296   return build_reference_type_for_mode (to_type, ptr_mode, false);
4297 }
4298
4299 /* Build a type that is compatible with t but has no cv quals anywhere
4300    in its type, thus
4301
4302    const char *const *const *  ->  char ***.  */
4303
4304 tree
4305 build_type_no_quals (tree t)
4306 {
4307   switch (TREE_CODE (t))
4308     {
4309     case POINTER_TYPE:
4310       return build_pointer_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4311                                           TYPE_MODE (t),
4312                                           TYPE_REF_CAN_ALIAS_ALL (t));
4313     case REFERENCE_TYPE:
4314       return
4315         build_reference_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4316                                        TYPE_MODE (t),
4317                                        TYPE_REF_CAN_ALIAS_ALL (t));
4318     default:
4319       return TYPE_MAIN_VARIANT (t);
4320     }
4321 }
4322
4323 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
4324    MAXVAL should be the maximum value in the domain
4325    (one less than the length of the array).
4326
4327    The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
4328    We don't enforce this limit, that is up to caller (e.g. language front end).
4329    The limit exists because the result is a signed type and we don't handle
4330    sizes that use more than one HOST_WIDE_INT.  */
4331
4332 tree
4333 build_index_type (tree maxval)
4334 {
4335   tree itype = make_node (INTEGER_TYPE);
4336
4337   TREE_TYPE (itype) = sizetype;
4338   TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
4339   TYPE_MIN_VALUE (itype) = size_zero_node;
4340   TYPE_MAX_VALUE (itype) = fold_convert (sizetype, maxval);
4341   TYPE_MODE (itype) = TYPE_MODE (sizetype);
4342   TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
4343   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
4344   TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
4345   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
4346
4347   if (host_integerp (maxval, 1))
4348     return type_hash_canon (tree_low_cst (maxval, 1), itype);
4349   else
4350     return itype;
4351 }
4352
4353 /* Builds a signed or unsigned integer type of precision PRECISION.
4354    Used for C bitfields whose precision does not match that of
4355    built-in target types.  */
4356 tree
4357 build_nonstandard_integer_type (unsigned HOST_WIDE_INT precision,
4358                                 int unsignedp)
4359 {
4360   tree itype = make_node (INTEGER_TYPE);
4361
4362   TYPE_PRECISION (itype) = precision;
4363
4364   if (unsignedp)
4365     fixup_unsigned_type (itype);
4366   else
4367     fixup_signed_type (itype);
4368
4369   if (host_integerp (TYPE_MAX_VALUE (itype), 1))
4370     return type_hash_canon (tree_low_cst (TYPE_MAX_VALUE (itype), 1), itype);
4371
4372   return itype;
4373 }
4374
4375 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
4376    ENUMERAL_TYPE, BOOLEAN_TYPE, or CHAR_TYPE), with
4377    low bound LOWVAL and high bound HIGHVAL.
4378    if TYPE==NULL_TREE, sizetype is used.  */
4379
4380 tree
4381 build_range_type (tree type, tree lowval, tree highval)
4382 {
4383   tree itype = make_node (INTEGER_TYPE);
4384
4385   TREE_TYPE (itype) = type;
4386   if (type == NULL_TREE)
4387     type = sizetype;
4388
4389   TYPE_MIN_VALUE (itype) = convert (type, lowval);
4390   TYPE_MAX_VALUE (itype) = highval ? convert (type, highval) : NULL;
4391
4392   TYPE_PRECISION (itype) = TYPE_PRECISION (type);
4393   TYPE_MODE (itype) = TYPE_MODE (type);
4394   TYPE_SIZE (itype) = TYPE_SIZE (type);
4395   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type);
4396   TYPE_ALIGN (itype) = TYPE_ALIGN (type);
4397   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type);
4398
4399   if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0))
4400     return type_hash_canon (tree_low_cst (highval, 0)
4401                             - tree_low_cst (lowval, 0),
4402                             itype);
4403   else
4404     return itype;
4405 }
4406
4407 /* Just like build_index_type, but takes lowval and highval instead
4408    of just highval (maxval).  */
4409
4410 tree
4411 build_index_2_type (tree lowval, tree highval)
4412 {
4413   return build_range_type (sizetype, lowval, highval);
4414 }
4415
4416 /* Construct, lay out and return the type of arrays of elements with ELT_TYPE
4417    and number of elements specified by the range of values of INDEX_TYPE.
4418    If such a type has already been constructed, reuse it.  */
4419
4420 tree
4421 build_array_type (tree elt_type, tree index_type)
4422 {
4423   tree t;
4424   hashval_t hashcode = 0;
4425
4426   if (TREE_CODE (elt_type) == FUNCTION_TYPE)
4427     {
4428       error ("arrays of functions are not meaningful");
4429       elt_type = integer_type_node;
4430     }
4431
4432   t = make_node (ARRAY_TYPE);
4433   TREE_TYPE (t) = elt_type;
4434   TYPE_DOMAIN (t) = index_type;
4435
4436   if (index_type == 0)
4437     {
4438       layout_type (t);
4439       return t;
4440     }
4441
4442   hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode);
4443   hashcode = iterative_hash_object (TYPE_HASH (index_type), hashcode);
4444   t = type_hash_canon (hashcode, t);
4445
4446   if (!COMPLETE_TYPE_P (t))
4447     layout_type (t);
4448   return t;
4449 }
4450
4451 /* Return the TYPE of the elements comprising
4452    the innermost dimension of ARRAY.  */
4453
4454 tree
4455 get_inner_array_type (tree array)
4456 {
4457   tree type = TREE_TYPE (array);
4458
4459   while (TREE_CODE (type) == ARRAY_TYPE)
4460     type = TREE_TYPE (type);
4461
4462   return type;
4463 }
4464
4465 /* Construct, lay out and return
4466    the type of functions returning type VALUE_TYPE
4467    given arguments of types ARG_TYPES.
4468    ARG_TYPES is a chain of TREE_LIST nodes whose TREE_VALUEs
4469    are data type nodes for the arguments of the function.
4470    If such a type has already been constructed, reuse it.  */
4471
4472 tree
4473 build_function_type (tree value_type, tree arg_types)
4474 {
4475   tree t;
4476   hashval_t hashcode = 0;
4477
4478   if (TREE_CODE (value_type) == FUNCTION_TYPE)
4479     {
4480       error ("function return type cannot be function");
4481       value_type = integer_type_node;
4482     }
4483
4484   /* Make a node of the sort we want.  */
4485   t = make_node (FUNCTION_TYPE);
4486   TREE_TYPE (t) = value_type;
4487   TYPE_ARG_TYPES (t) = arg_types;
4488
4489   /* If we already have such a type, use the old one.  */
4490   hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode);
4491   hashcode = type_hash_list (arg_types, hashcode);
4492   t = type_hash_canon (hashcode, t);
4493
4494   if (!COMPLETE_TYPE_P (t))
4495     layout_type (t);
4496   return t;
4497 }
4498
4499 /* Build a function type.  The RETURN_TYPE is the type returned by the
4500    function.  If additional arguments are provided, they are
4501    additional argument types.  The list of argument types must always
4502    be terminated by NULL_TREE.  */
4503
4504 tree
4505 build_function_type_list (tree return_type, ...)
4506 {
4507   tree t, args, last;
4508   va_list p;
4509
4510   va_start (p, return_type);
4511
4512   t = va_arg (p, tree);
4513   for (args = NULL_TREE; t != NULL_TREE; t = va_arg (p, tree))
4514     args = tree_cons (NULL_TREE, t, args);
4515
4516   last = args;
4517   args = nreverse (args);
4518   TREE_CHAIN (last) = void_list_node;
4519   args = build_function_type (return_type, args);
4520
4521   va_end (p);
4522   return args;
4523 }
4524
4525 /* Build a METHOD_TYPE for a member of BASETYPE.  The RETTYPE (a TYPE)
4526    and ARGTYPES (a TREE_LIST) are the return type and arguments types
4527    for the method.  An implicit additional parameter (of type
4528    pointer-to-BASETYPE) is added to the ARGTYPES.  */
4529
4530 tree
4531 build_method_type_directly (tree basetype,
4532                             tree rettype,
4533                             tree argtypes)
4534 {
4535   tree t;
4536   tree ptype;
4537   int hashcode = 0;
4538
4539   /* Make a node of the sort we want.  */
4540   t = make_node (METHOD_TYPE);
4541
4542   TYPE_METHOD_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
4543   TREE_TYPE (t) = rettype;
4544   ptype = build_pointer_type (basetype);
4545
4546   /* The actual arglist for this function includes a "hidden" argument
4547      which is "this".  Put it into the list of argument types.  */
4548   argtypes = tree_cons (NULL_TREE, ptype, argtypes);
4549   TYPE_ARG_TYPES (t) = argtypes;
4550
4551   /* If we already have such a type, use the old one.  */
4552   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
4553   hashcode = iterative_hash_object (TYPE_HASH (rettype), hashcode);
4554   hashcode = type_hash_list (argtypes, hashcode);
4555   t = type_hash_canon (hashcode, t);
4556
4557   if (!COMPLETE_TYPE_P (t))
4558     layout_type (t);
4559
4560   return t;
4561 }
4562
4563 /* Construct, lay out and return the type of methods belonging to class
4564    BASETYPE and whose arguments and values are described by TYPE.
4565    If that type exists already, reuse it.
4566    TYPE must be a FUNCTION_TYPE node.  */
4567
4568 tree
4569 build_method_type (tree basetype, tree type)
4570 {
4571   gcc_assert (TREE_CODE (type) == FUNCTION_TYPE);
4572
4573   return build_method_type_directly (basetype,
4574                                      TREE_TYPE (type),
4575                                      TYPE_ARG_TYPES (type));
4576 }
4577
4578 /* Construct, lay out and return the type of offsets to a value
4579    of type TYPE, within an object of type BASETYPE.
4580    If a suitable offset type exists already, reuse it.  */
4581
4582 tree
4583 build_offset_type (tree basetype, tree type)
4584 {
4585   tree t;
4586   hashval_t hashcode = 0;
4587
4588   /* Make a node of the sort we want.  */
4589   t = make_node (OFFSET_TYPE);
4590
4591   TYPE_OFFSET_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
4592   TREE_TYPE (t) = type;
4593
4594   /* If we already have such a type, use the old one.  */
4595   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
4596   hashcode = iterative_hash_object (TYPE_HASH (type), hashcode);
4597   t = type_hash_canon (hashcode, t);
4598
4599   if (!COMPLETE_TYPE_P (t))
4600     layout_type (t);
4601
4602   return t;
4603 }
4604
4605 /* Create a complex type whose components are COMPONENT_TYPE.  */
4606
4607 tree
4608 build_complex_type (tree component_type)
4609 {
4610   tree t;
4611   hashval_t hashcode;
4612
4613   /* Make a node of the sort we want.  */
4614   t = make_node (COMPLEX_TYPE);
4615
4616   TREE_TYPE (t) = TYPE_MAIN_VARIANT (component_type);
4617
4618   /* If we already have such a type, use the old one.  */
4619   hashcode = iterative_hash_object (TYPE_HASH (component_type), 0);
4620   t = type_hash_canon (hashcode, t);
4621
4622   if (!COMPLETE_TYPE_P (t))
4623     layout_type (t);
4624
4625   /* If we are writing Dwarf2 output we need to create a name,
4626      since complex is a fundamental type.  */
4627   if ((write_symbols == DWARF2_DEBUG || write_symbols == VMS_AND_DWARF2_DEBUG)
4628       && ! TYPE_NAME (t))
4629     {
4630       const char *name;
4631       if (component_type == char_type_node)
4632         name = "complex char";
4633       else if (component_type == signed_char_type_node)
4634         name = "complex signed char";
4635       else if (component_type == unsigned_char_type_node)
4636         name = "complex unsigned char";
4637       else if (component_type == short_integer_type_node)
4638         name = "complex short int";
4639       else if (component_type == short_unsigned_type_node)
4640         name = "complex short unsigned int";
4641       else if (component_type == integer_type_node)
4642         name = "complex int";
4643       else if (component_type == unsigned_type_node)
4644         name = "complex unsigned int";
4645       else if (component_type == long_integer_type_node)
4646         name = "complex long int";
4647       else if (component_type == long_unsigned_type_node)
4648         name = "complex long unsigned int";
4649       else if (component_type == long_long_integer_type_node)
4650         name = "complex long long int";
4651       else if (component_type == long_long_unsigned_type_node)
4652         name = "complex long long unsigned int";
4653       else
4654         name = 0;
4655
4656       if (name != 0)
4657         TYPE_NAME (t) = get_identifier (name);
4658     }
4659
4660   return build_qualified_type (t, TYPE_QUALS (component_type));
4661 }
4662 \f
4663 /* Return OP, stripped of any conversions to wider types as much as is safe.
4664    Converting the value back to OP's type makes a value equivalent to OP.
4665
4666    If FOR_TYPE is nonzero, we return a value which, if converted to
4667    type FOR_TYPE, would be equivalent to converting OP to type FOR_TYPE.
4668
4669    If FOR_TYPE is nonzero, unaligned bit-field references may be changed to the
4670    narrowest type that can hold the value, even if they don't exactly fit.
4671    Otherwise, bit-field references are changed to a narrower type
4672    only if they can be fetched directly from memory in that type.
4673
4674    OP must have integer, real or enumeral type.  Pointers are not allowed!
4675
4676    There are some cases where the obvious value we could return
4677    would regenerate to OP if converted to OP's type,
4678    but would not extend like OP to wider types.
4679    If FOR_TYPE indicates such extension is contemplated, we eschew such values.
4680    For example, if OP is (unsigned short)(signed char)-1,
4681    we avoid returning (signed char)-1 if FOR_TYPE is int,
4682    even though extending that to an unsigned short would regenerate OP,
4683    since the result of extending (signed char)-1 to (int)
4684    is different from (int) OP.  */
4685
4686 tree
4687 get_unwidened (tree op, tree for_type)
4688 {
4689   /* Set UNS initially if converting OP to FOR_TYPE is a zero-extension.  */
4690   tree type = TREE_TYPE (op);
4691   unsigned final_prec
4692     = TYPE_PRECISION (for_type != 0 ? for_type : type);
4693   int uns
4694     = (for_type != 0 && for_type != type
4695        && final_prec > TYPE_PRECISION (type)
4696        && TYPE_UNSIGNED (type));
4697   tree win = op;
4698
4699   while (TREE_CODE (op) == NOP_EXPR)
4700     {
4701       int bitschange
4702         = TYPE_PRECISION (TREE_TYPE (op))
4703           - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0)));
4704
4705       /* Truncations are many-one so cannot be removed.
4706          Unless we are later going to truncate down even farther.  */
4707       if (bitschange < 0
4708           && final_prec > TYPE_PRECISION (TREE_TYPE (op)))
4709         break;
4710
4711       /* See what's inside this conversion.  If we decide to strip it,
4712          we will set WIN.  */
4713       op = TREE_OPERAND (op, 0);
4714
4715       /* If we have not stripped any zero-extensions (uns is 0),
4716          we can strip any kind of extension.
4717          If we have previously stripped a zero-extension,
4718          only zero-extensions can safely be stripped.
4719          Any extension can be stripped if the bits it would produce
4720          are all going to be discarded later by truncating to FOR_TYPE.  */
4721
4722       if (bitschange > 0)
4723         {
4724           if (! uns || final_prec <= TYPE_PRECISION (TREE_TYPE (op)))
4725             win = op;
4726           /* TYPE_UNSIGNED says whether this is a zero-extension.
4727              Let's avoid computing it if it does not affect WIN
4728              and if UNS will not be needed again.  */
4729           if ((uns || TREE_CODE (op) == NOP_EXPR)
4730               && TYPE_UNSIGNED (TREE_TYPE (op)))
4731             {
4732               uns = 1;
4733               win = op;
4734             }
4735         }
4736     }
4737
4738   if (TREE_CODE (op) == COMPONENT_REF
4739       /* Since type_for_size always gives an integer type.  */
4740       && TREE_CODE (type) != REAL_TYPE
4741       /* Don't crash if field not laid out yet.  */
4742       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
4743       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
4744     {
4745       unsigned int innerprec
4746         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
4747       int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
4748                        || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
4749       type = lang_hooks.types.type_for_size (innerprec, unsignedp);
4750
4751       /* We can get this structure field in the narrowest type it fits in.
4752          If FOR_TYPE is 0, do this only for a field that matches the
4753          narrower type exactly and is aligned for it
4754          The resulting extension to its nominal type (a fullword type)
4755          must fit the same conditions as for other extensions.  */
4756
4757       if (type != 0
4758           && INT_CST_LT_UNSIGNED (TYPE_SIZE (type), TYPE_SIZE (TREE_TYPE (op)))
4759           && (for_type || ! DECL_BIT_FIELD (TREE_OPERAND (op, 1)))
4760           && (! uns || final_prec <= innerprec || unsignedp))
4761         {
4762           win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
4763                         TREE_OPERAND (op, 1), NULL_TREE);
4764           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
4765           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
4766         }
4767     }
4768
4769   return win;
4770 }
4771 \f
4772 /* Return OP or a simpler expression for a narrower value
4773    which can be sign-extended or zero-extended to give back OP.
4774    Store in *UNSIGNEDP_PTR either 1 if the value should be zero-extended
4775    or 0 if the value should be sign-extended.  */
4776
4777 tree
4778 get_narrower (tree op, int *unsignedp_ptr)
4779 {
4780   int uns = 0;
4781   int first = 1;
4782   tree win = op;
4783   bool integral_p = INTEGRAL_TYPE_P (TREE_TYPE (op));
4784
4785   while (TREE_CODE (op) == NOP_EXPR)
4786     {
4787       int bitschange
4788         = (TYPE_PRECISION (TREE_TYPE (op))
4789            - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0))));
4790
4791       /* Truncations are many-one so cannot be removed.  */
4792       if (bitschange < 0)
4793         break;
4794
4795       /* See what's inside this conversion.  If we decide to strip it,
4796          we will set WIN.  */
4797
4798       if (bitschange > 0)
4799         {
4800           op = TREE_OPERAND (op, 0);
4801           /* An extension: the outermost one can be stripped,
4802              but remember whether it is zero or sign extension.  */
4803           if (first)
4804             uns = TYPE_UNSIGNED (TREE_TYPE (op));
4805           /* Otherwise, if a sign extension has been stripped,
4806              only sign extensions can now be stripped;
4807              if a zero extension has been stripped, only zero-extensions.  */
4808           else if (uns != TYPE_UNSIGNED (TREE_TYPE (op)))
4809             break;
4810           first = 0;
4811         }
4812       else /* bitschange == 0 */
4813         {
4814           /* A change in nominal type can always be stripped, but we must
4815              preserve the unsignedness.  */
4816           if (first)
4817             uns = TYPE_UNSIGNED (TREE_TYPE (op));
4818           first = 0;
4819           op = TREE_OPERAND (op, 0);
4820           /* Keep trying to narrow, but don't assign op to win if it
4821              would turn an integral type into something else.  */
4822           if (INTEGRAL_TYPE_P (TREE_TYPE (op)) != integral_p)
4823             continue;
4824         }
4825
4826       win = op;
4827     }
4828
4829   if (TREE_CODE (op) == COMPONENT_REF
4830       /* Since type_for_size always gives an integer type.  */
4831       && TREE_CODE (TREE_TYPE (op)) != REAL_TYPE
4832       /* Ensure field is laid out already.  */
4833       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
4834       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
4835     {
4836       unsigned HOST_WIDE_INT innerprec
4837         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
4838       int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
4839                        || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
4840       tree type = lang_hooks.types.type_for_size (innerprec, unsignedp);
4841
4842       /* We can get this structure field in a narrower type that fits it,
4843          but the resulting extension to its nominal type (a fullword type)
4844          must satisfy the same conditions as for other extensions.
4845
4846          Do this only for fields that are aligned (not bit-fields),
4847          because when bit-field insns will be used there is no
4848          advantage in doing this.  */
4849
4850       if (innerprec < TYPE_PRECISION (TREE_TYPE (op))
4851           && ! DECL_BIT_FIELD (TREE_OPERAND (op, 1))
4852           && (first || uns == DECL_UNSIGNED (TREE_OPERAND (op, 1)))
4853           && type != 0)
4854         {
4855           if (first)
4856             uns = DECL_UNSIGNED (TREE_OPERAND (op, 1));
4857           win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
4858                         TREE_OPERAND (op, 1), NULL_TREE);
4859           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
4860           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
4861         }
4862     }
4863   *unsignedp_ptr = uns;
4864   return win;
4865 }
4866 \f
4867 /* Nonzero if integer constant C has a value that is permissible
4868    for type TYPE (an INTEGER_TYPE).  */
4869
4870 int
4871 int_fits_type_p (tree c, tree type)
4872 {
4873   tree type_low_bound = TYPE_MIN_VALUE (type);
4874   tree type_high_bound = TYPE_MAX_VALUE (type);
4875   int ok_for_low_bound, ok_for_high_bound;
4876
4877   /* Perform some generic filtering first, which may allow making a decision
4878      even if the bounds are not constant.  First, negative integers never fit
4879      in unsigned types, */
4880   if ((TYPE_UNSIGNED (type) && tree_int_cst_sgn (c) < 0)
4881       /* Also, unsigned integers with top bit set never fit signed types.  */
4882       || (! TYPE_UNSIGNED (type)
4883           && TYPE_UNSIGNED (TREE_TYPE (c)) && tree_int_cst_msb (c)))
4884     return 0;
4885
4886   /* If at least one bound of the type is a constant integer, we can check
4887      ourselves and maybe make a decision. If no such decision is possible, but
4888      this type is a subtype, try checking against that.  Otherwise, use
4889      force_fit_type, which checks against the precision.
4890
4891      Compute the status for each possibly constant bound, and return if we see
4892      one does not match. Use ok_for_xxx_bound for this purpose, assigning -1
4893      for "unknown if constant fits", 0 for "constant known *not* to fit" and 1
4894      for "constant known to fit".  */
4895
4896   ok_for_low_bound = -1;
4897   ok_for_high_bound = -1;
4898
4899   /* Check if C >= type_low_bound.  */
4900   if (type_low_bound && TREE_CODE (type_low_bound) == INTEGER_CST)
4901     {
4902       ok_for_low_bound = ! tree_int_cst_lt (c, type_low_bound);
4903       if (! ok_for_low_bound)
4904         return 0;
4905     }
4906
4907   /* Check if c <= type_high_bound.  */
4908   if (type_high_bound && TREE_CODE (type_high_bound) == INTEGER_CST)
4909     {
4910       ok_for_high_bound = ! tree_int_cst_lt (type_high_bound, c);
4911       if (! ok_for_high_bound)
4912         return 0;
4913     }
4914
4915   /* If the constant fits both bounds, the result is known.  */
4916   if (ok_for_low_bound == 1 && ok_for_high_bound == 1)
4917     return 1;
4918
4919   /* If we haven't been able to decide at this point, there nothing more we
4920      can check ourselves here. Look at the base type if we have one.  */
4921   else if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != 0)
4922     return int_fits_type_p (c, TREE_TYPE (type));
4923
4924   /* Or to force_fit_type, if nothing else.  */
4925   else
4926     {
4927       c = copy_node (c);
4928       TREE_TYPE (c) = type;
4929       c = force_fit_type (c, -1, false, false);
4930       return !TREE_OVERFLOW (c);
4931     }
4932 }
4933
4934 /* Subprogram of following function.  Called by walk_tree.
4935
4936    Return *TP if it is an automatic variable or parameter of the
4937    function passed in as DATA.  */
4938
4939 static tree
4940 find_var_from_fn (tree *tp, int *walk_subtrees, void *data)
4941 {
4942   tree fn = (tree) data;
4943
4944   if (TYPE_P (*tp))
4945     *walk_subtrees = 0;
4946
4947   else if (DECL_P (*tp)
4948            && lang_hooks.tree_inlining.auto_var_in_fn_p (*tp, fn))
4949     return *tp;
4950
4951   return NULL_TREE;
4952 }
4953
4954 /* Returns true if T is, contains, or refers to a type with variable
4955    size.  If FN is nonzero, only return true if a modifier of the type
4956    or position of FN is a variable or parameter inside FN.
4957
4958    This concept is more general than that of C99 'variably modified types':
4959    in C99, a struct type is never variably modified because a VLA may not
4960    appear as a structure member.  However, in GNU C code like:
4961
4962      struct S { int i[f()]; };
4963
4964    is valid, and other languages may define similar constructs.  */
4965
4966 bool
4967 variably_modified_type_p (tree type, tree fn)
4968 {
4969   tree t;
4970
4971 /* Test if T is either variable (if FN is zero) or an expression containing
4972    a variable in FN.  */
4973 #define RETURN_TRUE_IF_VAR(T)                                           \
4974   do { tree _t = (T);                                                   \
4975     if (_t && _t != error_mark_node && TREE_CODE (_t) != INTEGER_CST    \
4976         && (!fn || walk_tree (&_t, find_var_from_fn, fn, NULL)))        \
4977       return true;  } while (0)
4978
4979   if (type == error_mark_node)
4980     return false;
4981
4982   /* If TYPE itself has variable size, it is variably modified.
4983
4984      We do not yet have a representation of the C99 '[*]' syntax.
4985      When a representation is chosen, this function should be modified
4986      to test for that case as well.  */
4987   RETURN_TRUE_IF_VAR (TYPE_SIZE (type));
4988   RETURN_TRUE_IF_VAR (TYPE_SIZE_UNIT(type));
4989
4990   switch (TREE_CODE (type))
4991     {
4992     case POINTER_TYPE:
4993     case REFERENCE_TYPE:
4994     case ARRAY_TYPE:
4995     case SET_TYPE:
4996     case VECTOR_TYPE:
4997       if (variably_modified_type_p (TREE_TYPE (type), fn))
4998         return true;
4999       break;
5000
5001     case FUNCTION_TYPE:
5002     case METHOD_TYPE:
5003       /* If TYPE is a function type, it is variably modified if any of the
5004          parameters or the return type are variably modified.  */
5005       if (variably_modified_type_p (TREE_TYPE (type), fn))
5006           return true;
5007
5008       for (t = TYPE_ARG_TYPES (type);
5009            t && t != void_list_node;
5010            t = TREE_CHAIN (t))
5011         if (variably_modified_type_p (TREE_VALUE (t), fn))
5012           return true;
5013       break;
5014
5015     case INTEGER_TYPE:
5016     case REAL_TYPE:
5017     case ENUMERAL_TYPE:
5018     case BOOLEAN_TYPE:
5019     case CHAR_TYPE:
5020       /* Scalar types are variably modified if their end points
5021          aren't constant.  */
5022       RETURN_TRUE_IF_VAR (TYPE_MIN_VALUE (type));
5023       RETURN_TRUE_IF_VAR (TYPE_MAX_VALUE (type));
5024       break;
5025
5026     case RECORD_TYPE:
5027     case UNION_TYPE:
5028     case QUAL_UNION_TYPE:
5029       /* We can't see if any of the field are variably-modified by the
5030          definition we normally use, since that would produce infinite
5031          recursion via pointers.  */
5032       /* This is variably modified if some field's type is.  */
5033       for (t = TYPE_FIELDS (type); t; t = TREE_CHAIN (t))
5034         if (TREE_CODE (t) == FIELD_DECL)
5035           {
5036             RETURN_TRUE_IF_VAR (DECL_FIELD_OFFSET (t));
5037             RETURN_TRUE_IF_VAR (DECL_SIZE (t));
5038             RETURN_TRUE_IF_VAR (DECL_SIZE_UNIT (t));
5039
5040             if (TREE_CODE (type) == QUAL_UNION_TYPE)
5041               RETURN_TRUE_IF_VAR (DECL_QUALIFIER (t));
5042           }
5043         break;
5044
5045     default:
5046       break;
5047     }
5048
5049   /* The current language may have other cases to check, but in general,
5050      all other types are not variably modified.  */
5051   return lang_hooks.tree_inlining.var_mod_type_p (type, fn);
5052
5053 #undef RETURN_TRUE_IF_VAR
5054 }
5055
5056 /* Given a DECL or TYPE, return the scope in which it was declared, or
5057    NULL_TREE if there is no containing scope.  */
5058
5059 tree
5060 get_containing_scope (tree t)
5061 {
5062   return (TYPE_P (t) ? TYPE_CONTEXT (t) : DECL_CONTEXT (t));
5063 }
5064
5065 /* Return the innermost context enclosing DECL that is
5066    a FUNCTION_DECL, or zero if none.  */
5067
5068 tree
5069 decl_function_context (tree decl)
5070 {
5071   tree context;
5072
5073   if (TREE_CODE (decl) == ERROR_MARK)
5074     return 0;
5075
5076   /* C++ virtual functions use DECL_CONTEXT for the class of the vtable
5077      where we look up the function at runtime.  Such functions always take
5078      a first argument of type 'pointer to real context'.
5079
5080      C++ should really be fixed to use DECL_CONTEXT for the real context,
5081      and use something else for the "virtual context".  */
5082   else if (TREE_CODE (decl) == FUNCTION_DECL && DECL_VINDEX (decl))
5083     context
5084       = TYPE_MAIN_VARIANT
5085         (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (decl)))));
5086   else
5087     context = DECL_CONTEXT (decl);
5088
5089   while (context && TREE_CODE (context) != FUNCTION_DECL)
5090     {
5091       if (TREE_CODE (context) == BLOCK)
5092         context = BLOCK_SUPERCONTEXT (context);
5093       else
5094         context = get_containing_scope (context);
5095     }
5096
5097   return context;
5098 }
5099
5100 /* Return the innermost context enclosing DECL that is
5101    a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE, or zero if none.
5102    TYPE_DECLs and FUNCTION_DECLs are transparent to this function.  */
5103
5104 tree
5105 decl_type_context (tree decl)
5106 {
5107   tree context = DECL_CONTEXT (decl);
5108
5109   while (context)
5110     switch (TREE_CODE (context))
5111       {
5112       case NAMESPACE_DECL:
5113       case TRANSLATION_UNIT_DECL:
5114         return NULL_TREE;
5115
5116       case RECORD_TYPE:
5117       case UNION_TYPE:
5118       case QUAL_UNION_TYPE:
5119         return context;
5120
5121       case TYPE_DECL:
5122       case FUNCTION_DECL:
5123         context = DECL_CONTEXT (context);
5124         break;
5125
5126       case BLOCK:
5127         context = BLOCK_SUPERCONTEXT (context);
5128         break;
5129
5130       default:
5131         gcc_unreachable ();
5132       }
5133
5134   return NULL_TREE;
5135 }
5136
5137 /* CALL is a CALL_EXPR.  Return the declaration for the function
5138    called, or NULL_TREE if the called function cannot be
5139    determined.  */
5140
5141 tree
5142 get_callee_fndecl (tree call)
5143 {
5144   tree addr;
5145
5146   /* It's invalid to call this function with anything but a
5147      CALL_EXPR.  */
5148   gcc_assert (TREE_CODE (call) == CALL_EXPR);
5149
5150   /* The first operand to the CALL is the address of the function
5151      called.  */
5152   addr = TREE_OPERAND (call, 0);
5153
5154   STRIP_NOPS (addr);
5155
5156   /* If this is a readonly function pointer, extract its initial value.  */
5157   if (DECL_P (addr) && TREE_CODE (addr) != FUNCTION_DECL
5158       && TREE_READONLY (addr) && ! TREE_THIS_VOLATILE (addr)
5159       && DECL_INITIAL (addr))
5160     addr = DECL_INITIAL (addr);
5161
5162   /* If the address is just `&f' for some function `f', then we know
5163      that `f' is being called.  */
5164   if (TREE_CODE (addr) == ADDR_EXPR
5165       && TREE_CODE (TREE_OPERAND (addr, 0)) == FUNCTION_DECL)
5166     return TREE_OPERAND (addr, 0);
5167
5168   /* We couldn't figure out what was being called.  Maybe the front
5169      end has some idea.  */
5170   return lang_hooks.lang_get_callee_fndecl (call);
5171 }
5172
5173 /* Print debugging information about tree nodes generated during the compile,
5174    and any language-specific information.  */
5175
5176 void
5177 dump_tree_statistics (void)
5178 {
5179 #ifdef GATHER_STATISTICS
5180   int i;
5181   int total_nodes, total_bytes;
5182 #endif
5183
5184   fprintf (stderr, "\n??? tree nodes created\n\n");
5185 #ifdef GATHER_STATISTICS
5186   fprintf (stderr, "Kind                   Nodes      Bytes\n");
5187   fprintf (stderr, "---------------------------------------\n");
5188   total_nodes = total_bytes = 0;
5189   for (i = 0; i < (int) all_kinds; i++)
5190     {
5191       fprintf (stderr, "%-20s %7d %10d\n", tree_node_kind_names[i],
5192                tree_node_counts[i], tree_node_sizes[i]);
5193       total_nodes += tree_node_counts[i];
5194       total_bytes += tree_node_sizes[i];
5195     }
5196   fprintf (stderr, "---------------------------------------\n");
5197   fprintf (stderr, "%-20s %7d %10d\n", "Total", total_nodes, total_bytes);
5198   fprintf (stderr, "---------------------------------------\n");
5199   ssanames_print_statistics ();
5200   phinodes_print_statistics ();
5201 #else
5202   fprintf (stderr, "(No per-node statistics)\n");
5203 #endif
5204   print_type_hash_statistics ();
5205   lang_hooks.print_statistics ();
5206 }
5207 \f
5208 #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
5209
5210 /* Generate a crc32 of a string.  */
5211
5212 unsigned
5213 crc32_string (unsigned chksum, const char *string)
5214 {
5215   do
5216     {
5217       unsigned value = *string << 24;
5218       unsigned ix;
5219
5220       for (ix = 8; ix--; value <<= 1)
5221         {
5222           unsigned feedback;
5223
5224           feedback = (value ^ chksum) & 0x80000000 ? 0x04c11db7 : 0;
5225           chksum <<= 1;
5226           chksum ^= feedback;
5227         }
5228     }
5229   while (*string++);
5230   return chksum;
5231 }
5232
5233 /* P is a string that will be used in a symbol.  Mask out any characters
5234    that are not valid in that context.  */
5235
5236 void
5237 clean_symbol_name (char *p)
5238 {
5239   for (; *p; p++)
5240     if (! (ISALNUM (*p)
5241 #ifndef NO_DOLLAR_IN_LABEL      /* this for `$'; unlikely, but... -- kr */
5242             || *p == '$'
5243 #endif
5244 #ifndef NO_DOT_IN_LABEL         /* this for `.'; unlikely, but...  */
5245             || *p == '.'
5246 #endif
5247            ))
5248       *p = '_';
5249 }
5250
5251 /* Generate a name for a function unique to this translation unit.
5252    TYPE is some string to identify the purpose of this function to the
5253    linker or collect2.  */
5254
5255 tree
5256 get_file_function_name_long (const char *type)
5257 {
5258   char *buf;
5259   const char *p;
5260   char *q;
5261
5262   if (first_global_object_name)
5263     p = first_global_object_name;
5264   else
5265     {
5266       /* We don't have anything that we know to be unique to this translation
5267          unit, so use what we do have and throw in some randomness.  */
5268       unsigned len;
5269       const char *name = weak_global_object_name;
5270       const char *file = main_input_filename;
5271
5272       if (! name)
5273         name = "";
5274       if (! file)
5275         file = input_filename;
5276
5277       len = strlen (file);
5278       q = alloca (9 * 2 + len + 1);
5279       memcpy (q, file, len + 1);
5280       clean_symbol_name (q);
5281
5282       sprintf (q + len, "_%08X_%08X", crc32_string (0, name),
5283                crc32_string (0, flag_random_seed));
5284
5285       p = q;
5286     }
5287
5288   buf = alloca (sizeof (FILE_FUNCTION_FORMAT) + strlen (p) + strlen (type));
5289
5290   /* Set up the name of the file-level functions we may need.
5291      Use a global object (which is already required to be unique over
5292      the program) rather than the file name (which imposes extra
5293      constraints).  */
5294   sprintf (buf, FILE_FUNCTION_FORMAT, type, p);
5295
5296   return get_identifier (buf);
5297 }
5298
5299 /* If KIND=='I', return a suitable global initializer (constructor) name.
5300    If KIND=='D', return a suitable global clean-up (destructor) name.  */
5301
5302 tree
5303 get_file_function_name (int kind)
5304 {
5305   char p[2];
5306
5307   p[0] = kind;
5308   p[1] = 0;
5309
5310   return get_file_function_name_long (p);
5311 }
5312 \f
5313 /* Expand (the constant part of) a SET_TYPE CONSTRUCTOR node.
5314    The result is placed in BUFFER (which has length BIT_SIZE),
5315    with one bit in each char ('\000' or '\001').
5316
5317    If the constructor is constant, NULL_TREE is returned.
5318    Otherwise, a TREE_LIST of the non-constant elements is emitted.  */
5319
5320 tree
5321 get_set_constructor_bits (tree init, char *buffer, int bit_size)
5322 {
5323   int i;
5324   tree vals;
5325   HOST_WIDE_INT domain_min
5326     = tree_low_cst (TYPE_MIN_VALUE (TYPE_DOMAIN (TREE_TYPE (init))), 0);
5327   tree non_const_bits = NULL_TREE;
5328
5329   for (i = 0; i < bit_size; i++)
5330     buffer[i] = 0;
5331
5332   for (vals = TREE_OPERAND (init, 1);
5333        vals != NULL_TREE; vals = TREE_CHAIN (vals))
5334     {
5335       if (!host_integerp (TREE_VALUE (vals), 0)
5336           || (TREE_PURPOSE (vals) != NULL_TREE
5337               && !host_integerp (TREE_PURPOSE (vals), 0)))
5338         non_const_bits
5339           = tree_cons (TREE_PURPOSE (vals), TREE_VALUE (vals), non_const_bits);
5340       else if (TREE_PURPOSE (vals) != NULL_TREE)
5341         {
5342           /* Set a range of bits to ones.  */
5343           HOST_WIDE_INT lo_index
5344             = tree_low_cst (TREE_PURPOSE (vals), 0) - domain_min;
5345           HOST_WIDE_INT hi_index
5346             = tree_low_cst (TREE_VALUE (vals), 0) - domain_min;
5347
5348           gcc_assert (lo_index >= 0);
5349           gcc_assert (lo_index < bit_size);
5350           gcc_assert (hi_index >= 0);
5351           gcc_assert (hi_index < bit_size);
5352           for (; lo_index <= hi_index; lo_index++)
5353             buffer[lo_index] = 1;
5354         }
5355       else
5356         {
5357           /* Set a single bit to one.  */
5358           HOST_WIDE_INT index
5359             = tree_low_cst (TREE_VALUE (vals), 0) - domain_min;
5360           if (index < 0 || index >= bit_size)
5361             {
5362               error ("invalid initializer for bit string");
5363               return NULL_TREE;
5364             }
5365           buffer[index] = 1;
5366         }
5367     }
5368   return non_const_bits;
5369 }
5370
5371 /* Expand (the constant part of) a SET_TYPE CONSTRUCTOR node.
5372    The result is placed in BUFFER (which is an array of bytes).
5373    If the constructor is constant, NULL_TREE is returned.
5374    Otherwise, a TREE_LIST of the non-constant elements is emitted.  */
5375
5376 tree
5377 get_set_constructor_bytes (tree init, unsigned char *buffer, int wd_size)
5378 {
5379   int i;
5380   int set_word_size = BITS_PER_UNIT;
5381   int bit_size = wd_size * set_word_size;
5382   int bit_pos = 0;
5383   unsigned char *bytep = buffer;
5384   char *bit_buffer = alloca (bit_size);
5385   tree non_const_bits = get_set_constructor_bits (init, bit_buffer, bit_size);
5386
5387   for (i = 0; i < wd_size; i++)
5388     buffer[i] = 0;
5389
5390   for (i = 0; i < bit_size; i++)
5391     {
5392       if (bit_buffer[i])
5393         {
5394           if (BYTES_BIG_ENDIAN)
5395             *bytep |= (1 << (set_word_size - 1 - bit_pos));
5396           else
5397             *bytep |= 1 << bit_pos;
5398         }
5399       bit_pos++;
5400       if (bit_pos >= set_word_size)
5401         bit_pos = 0, bytep++;
5402     }
5403   return non_const_bits;
5404 }
5405 \f
5406 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
5407
5408 /* Complain that the tree code of NODE does not match the expected 0
5409    terminated list of trailing codes. The trailing code list can be
5410    empty, for a more vague error message.  FILE, LINE, and FUNCTION
5411    are of the caller.  */
5412
5413 void
5414 tree_check_failed (const tree node, const char *file,
5415                    int line, const char *function, ...)
5416 {
5417   va_list args;
5418   char *buffer;
5419   unsigned length = 0;
5420   int code;
5421
5422   va_start (args, function);
5423   while ((code = va_arg (args, int)))
5424     length += 4 + strlen (tree_code_name[code]);
5425   va_end (args);
5426   if (length)
5427     {
5428       va_start (args, function);
5429       length += strlen ("expected ");
5430       buffer = alloca (length);
5431       length = 0;
5432       while ((code = va_arg (args, int)))
5433         {
5434           const char *prefix = length ? " or " : "expected ";
5435
5436           strcpy (buffer + length, prefix);
5437           length += strlen (prefix);
5438           strcpy (buffer + length, tree_code_name[code]);
5439           length += strlen (tree_code_name[code]);
5440         }
5441       va_end (args);
5442     }
5443   else
5444     buffer = (char *)"unexpected node";
5445
5446   internal_error ("tree check: %s, have %s in %s, at %s:%d",
5447                   buffer, tree_code_name[TREE_CODE (node)],
5448                   function, trim_filename (file), line);
5449 }
5450
5451 /* Complain that the tree code of NODE does match the expected 0
5452    terminated list of trailing codes. FILE, LINE, and FUNCTION are of
5453    the caller.  */
5454
5455 void
5456 tree_not_check_failed (const tree node, const char *file,
5457                        int line, const char *function, ...)
5458 {
5459   va_list args;
5460   char *buffer;
5461   unsigned length = 0;
5462   int code;
5463
5464   va_start (args, function);
5465   while ((code = va_arg (args, int)))
5466     length += 4 + strlen (tree_code_name[code]);
5467   va_end (args);
5468   va_start (args, function);
5469   buffer = alloca (length);
5470   length = 0;
5471   while ((code = va_arg (args, int)))
5472     {
5473       if (length)
5474         {
5475           strcpy (buffer + length, " or ");
5476           length += 4;
5477         }
5478       strcpy (buffer + length, tree_code_name[code]);
5479       length += strlen (tree_code_name[code]);
5480     }
5481   va_end (args);
5482
5483   internal_error ("tree check: expected none of %s, have %s in %s, at %s:%d",
5484                   buffer, tree_code_name[TREE_CODE (node)],
5485                   function, trim_filename (file), line);
5486 }
5487
5488 /* Similar to tree_check_failed, except that we check for a class of tree
5489    code, given in CL.  */
5490
5491 void
5492 tree_class_check_failed (const tree node, const enum tree_code_class cl,
5493                          const char *file, int line, const char *function)
5494 {
5495   internal_error
5496     ("tree check: expected class %qs, have %qs (%s) in %s, at %s:%d",
5497      TREE_CODE_CLASS_STRING (cl),
5498      TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))),
5499      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
5500 }
5501
5502 /* Similar to above, except that the check is for the bounds of a TREE_VEC's
5503    (dynamically sized) vector.  */
5504
5505 void
5506 tree_vec_elt_check_failed (int idx, int len, const char *file, int line,
5507                            const char *function)
5508 {
5509   internal_error
5510     ("tree check: accessed elt %d of tree_vec with %d elts in %s, at %s:%d",
5511      idx + 1, len, function, trim_filename (file), line);
5512 }
5513
5514 /* Similar to above, except that the check is for the bounds of a PHI_NODE's
5515    (dynamically sized) vector.  */
5516
5517 void
5518 phi_node_elt_check_failed (int idx, int len, const char *file, int line,
5519                             const char *function)
5520 {
5521   internal_error
5522     ("tree check: accessed elt %d of phi_node with %d elts in %s, at %s:%d",
5523      idx + 1, len, function, trim_filename (file), line);
5524 }
5525
5526 /* Similar to above, except that the check is for the bounds of the operand
5527    vector of an expression node.  */
5528
5529 void
5530 tree_operand_check_failed (int idx, enum tree_code code, const char *file,
5531                            int line, const char *function)
5532 {
5533   internal_error
5534     ("tree check: accessed operand %d of %s with %d operands in %s, at %s:%d",
5535      idx + 1, tree_code_name[code], TREE_CODE_LENGTH (code),
5536      function, trim_filename (file), line);
5537 }
5538 #endif /* ENABLE_TREE_CHECKING */
5539 \f
5540 /* Create a new vector type node holding SUBPARTS units of type INNERTYPE,
5541    and mapped to the machine mode MODE.  Initialize its fields and build
5542    the information necessary for debugging output.  */
5543
5544 static tree
5545 make_vector_type (tree innertype, int nunits, enum machine_mode mode)
5546 {
5547   tree t = make_node (VECTOR_TYPE);
5548
5549   TREE_TYPE (t) = TYPE_MAIN_VARIANT (innertype);
5550   TYPE_VECTOR_SUBPARTS (t) = nunits;
5551   TYPE_MODE (t) = mode;
5552   TYPE_READONLY (t) = TYPE_READONLY (innertype);
5553   TYPE_VOLATILE (t) = TYPE_VOLATILE (innertype);
5554
5555   layout_type (t);
5556
5557   {
5558     tree index = build_int_cst (NULL_TREE, nunits - 1);
5559     tree array = build_array_type (innertype, build_index_type (index));
5560     tree rt = make_node (RECORD_TYPE);
5561
5562     TYPE_FIELDS (rt) = build_decl (FIELD_DECL, get_identifier ("f"), array);
5563     DECL_CONTEXT (TYPE_FIELDS (rt)) = rt;
5564     layout_type (rt);
5565     TYPE_DEBUG_REPRESENTATION_TYPE (t) = rt;
5566     /* In dwarfout.c, type lookup uses TYPE_UID numbers.  We want to output
5567        the representation type, and we want to find that die when looking up
5568        the vector type.  This is most easily achieved by making the TYPE_UID
5569        numbers equal.  */
5570     TYPE_UID (rt) = TYPE_UID (t);
5571   }
5572
5573   /* Build our main variant, based on the main variant of the inner type.  */
5574   if (TYPE_MAIN_VARIANT (innertype) != innertype)
5575     {
5576       tree innertype_main_variant = TYPE_MAIN_VARIANT (innertype);
5577       unsigned int hash = TYPE_HASH (innertype_main_variant);
5578       TYPE_MAIN_VARIANT (t)
5579         = type_hash_canon (hash, make_vector_type (innertype_main_variant,
5580                                                    nunits, mode));
5581     }
5582
5583   return t;
5584 }
5585
5586 static tree
5587 make_or_reuse_type (unsigned size, int unsignedp)
5588 {
5589   if (size == INT_TYPE_SIZE)
5590     return unsignedp ? unsigned_type_node : integer_type_node;
5591   if (size == CHAR_TYPE_SIZE)
5592     return unsignedp ? unsigned_char_type_node : signed_char_type_node;
5593   if (size == SHORT_TYPE_SIZE)
5594     return unsignedp ? short_unsigned_type_node : short_integer_type_node;
5595   if (size == LONG_TYPE_SIZE)
5596     return unsignedp ? long_unsigned_type_node : long_integer_type_node;
5597   if (size == LONG_LONG_TYPE_SIZE)
5598     return (unsignedp ? long_long_unsigned_type_node
5599             : long_long_integer_type_node);
5600
5601   if (unsignedp)
5602     return make_unsigned_type (size);
5603   else
5604     return make_signed_type (size);
5605 }
5606
5607 /* Create nodes for all integer types (and error_mark_node) using the sizes
5608    of C datatypes.  The caller should call set_sizetype soon after calling
5609    this function to select one of the types as sizetype.  */
5610
5611 void
5612 build_common_tree_nodes (bool signed_char, bool signed_sizetype)
5613 {
5614   error_mark_node = make_node (ERROR_MARK);
5615   TREE_TYPE (error_mark_node) = error_mark_node;
5616
5617   initialize_sizetypes (signed_sizetype);
5618
5619   /* Define both `signed char' and `unsigned char'.  */
5620   signed_char_type_node = make_signed_type (CHAR_TYPE_SIZE);
5621   unsigned_char_type_node = make_unsigned_type (CHAR_TYPE_SIZE);
5622
5623   /* Define `char', which is like either `signed char' or `unsigned char'
5624      but not the same as either.  */
5625   char_type_node
5626     = (signed_char
5627        ? make_signed_type (CHAR_TYPE_SIZE)
5628        : make_unsigned_type (CHAR_TYPE_SIZE));
5629
5630   short_integer_type_node = make_signed_type (SHORT_TYPE_SIZE);
5631   short_unsigned_type_node = make_unsigned_type (SHORT_TYPE_SIZE);
5632   integer_type_node = make_signed_type (INT_TYPE_SIZE);
5633   unsigned_type_node = make_unsigned_type (INT_TYPE_SIZE);
5634   long_integer_type_node = make_signed_type (LONG_TYPE_SIZE);
5635   long_unsigned_type_node = make_unsigned_type (LONG_TYPE_SIZE);
5636   long_long_integer_type_node = make_signed_type (LONG_LONG_TYPE_SIZE);
5637   long_long_unsigned_type_node = make_unsigned_type (LONG_LONG_TYPE_SIZE);
5638
5639   /* Define a boolean type.  This type only represents boolean values but
5640      may be larger than char depending on the value of BOOL_TYPE_SIZE.
5641      Front ends which want to override this size (i.e. Java) can redefine
5642      boolean_type_node before calling build_common_tree_nodes_2.  */
5643   boolean_type_node = make_unsigned_type (BOOL_TYPE_SIZE);
5644   TREE_SET_CODE (boolean_type_node, BOOLEAN_TYPE);
5645   TYPE_MAX_VALUE (boolean_type_node) = build_int_cst (boolean_type_node, 1);
5646   TYPE_PRECISION (boolean_type_node) = 1;
5647
5648   /* Fill in the rest of the sized types.  Reuse existing type nodes
5649      when possible.  */
5650   intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 0);
5651   intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 0);
5652   intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 0);
5653   intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 0);
5654   intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 0);
5655
5656   unsigned_intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 1);
5657   unsigned_intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 1);
5658   unsigned_intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 1);
5659   unsigned_intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 1);
5660   unsigned_intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 1);
5661
5662   access_public_node = get_identifier ("public");
5663   access_protected_node = get_identifier ("protected");
5664   access_private_node = get_identifier ("private");
5665 }
5666
5667 /* Call this function after calling build_common_tree_nodes and set_sizetype.
5668    It will create several other common tree nodes.  */
5669
5670 void
5671 build_common_tree_nodes_2 (int short_double)
5672 {
5673   /* Define these next since types below may used them.  */
5674   integer_zero_node = build_int_cst (NULL_TREE, 0);
5675   integer_one_node = build_int_cst (NULL_TREE, 1);
5676   integer_minus_one_node = build_int_cst (NULL_TREE, -1);
5677
5678   size_zero_node = size_int (0);
5679   size_one_node = size_int (1);
5680   bitsize_zero_node = bitsize_int (0);
5681   bitsize_one_node = bitsize_int (1);
5682   bitsize_unit_node = bitsize_int (BITS_PER_UNIT);
5683
5684   boolean_false_node = TYPE_MIN_VALUE (boolean_type_node);
5685   boolean_true_node = TYPE_MAX_VALUE (boolean_type_node);
5686
5687   void_type_node = make_node (VOID_TYPE);
5688   layout_type (void_type_node);
5689
5690   /* We are not going to have real types in C with less than byte alignment,
5691      so we might as well not have any types that claim to have it.  */
5692   TYPE_ALIGN (void_type_node) = BITS_PER_UNIT;
5693   TYPE_USER_ALIGN (void_type_node) = 0;
5694
5695   null_pointer_node = build_int_cst (build_pointer_type (void_type_node), 0);
5696   layout_type (TREE_TYPE (null_pointer_node));
5697
5698   ptr_type_node = build_pointer_type (void_type_node);
5699   const_ptr_type_node
5700     = build_pointer_type (build_type_variant (void_type_node, 1, 0));
5701   fileptr_type_node = ptr_type_node;
5702
5703   float_type_node = make_node (REAL_TYPE);
5704   TYPE_PRECISION (float_type_node) = FLOAT_TYPE_SIZE;
5705   layout_type (float_type_node);
5706
5707   double_type_node = make_node (REAL_TYPE);
5708   if (short_double)
5709     TYPE_PRECISION (double_type_node) = FLOAT_TYPE_SIZE;
5710   else
5711     TYPE_PRECISION (double_type_node) = DOUBLE_TYPE_SIZE;
5712   layout_type (double_type_node);
5713
5714   long_double_type_node = make_node (REAL_TYPE);
5715   TYPE_PRECISION (long_double_type_node) = LONG_DOUBLE_TYPE_SIZE;
5716   layout_type (long_double_type_node);
5717
5718   float_ptr_type_node = build_pointer_type (float_type_node);
5719   double_ptr_type_node = build_pointer_type (double_type_node);
5720   long_double_ptr_type_node = build_pointer_type (long_double_type_node);
5721   integer_ptr_type_node = build_pointer_type (integer_type_node);
5722
5723   complex_integer_type_node = make_node (COMPLEX_TYPE);
5724   TREE_TYPE (complex_integer_type_node) = integer_type_node;
5725   layout_type (complex_integer_type_node);
5726
5727   complex_float_type_node = make_node (COMPLEX_TYPE);
5728   TREE_TYPE (complex_float_type_node) = float_type_node;
5729   layout_type (complex_float_type_node);
5730
5731   complex_double_type_node = make_node (COMPLEX_TYPE);
5732   TREE_TYPE (complex_double_type_node) = double_type_node;
5733   layout_type (complex_double_type_node);
5734
5735   complex_long_double_type_node = make_node (COMPLEX_TYPE);
5736   TREE_TYPE (complex_long_double_type_node) = long_double_type_node;
5737   layout_type (complex_long_double_type_node);
5738
5739   {
5740     tree t = targetm.build_builtin_va_list ();
5741
5742     /* Many back-ends define record types without setting TYPE_NAME.
5743        If we copied the record type here, we'd keep the original
5744        record type without a name.  This breaks name mangling.  So,
5745        don't copy record types and let c_common_nodes_and_builtins()
5746        declare the type to be __builtin_va_list.  */
5747     if (TREE_CODE (t) != RECORD_TYPE)
5748       t = build_variant_type_copy (t);
5749
5750     va_list_type_node = t;
5751   }
5752 }
5753
5754 /* HACK.  GROSS.  This is absolutely disgusting.  I wish there was a
5755    better way.
5756
5757    If we requested a pointer to a vector, build up the pointers that
5758    we stripped off while looking for the inner type.  Similarly for
5759    return values from functions.
5760
5761    The argument TYPE is the top of the chain, and BOTTOM is the
5762    new type which we will point to.  */
5763
5764 tree
5765 reconstruct_complex_type (tree type, tree bottom)
5766 {
5767   tree inner, outer;
5768
5769   if (POINTER_TYPE_P (type))
5770     {
5771       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5772       outer = build_pointer_type (inner);
5773     }
5774   else if (TREE_CODE (type) == ARRAY_TYPE)
5775     {
5776       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5777       outer = build_array_type (inner, TYPE_DOMAIN (type));
5778     }
5779   else if (TREE_CODE (type) == FUNCTION_TYPE)
5780     {
5781       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5782       outer = build_function_type (inner, TYPE_ARG_TYPES (type));
5783     }
5784   else if (TREE_CODE (type) == METHOD_TYPE)
5785     {
5786       tree argtypes;
5787       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5788       /* The build_method_type_directly() routine prepends 'this' to argument list,
5789          so we must compensate by getting rid of it.  */
5790       argtypes = TYPE_ARG_TYPES (type);
5791       outer = build_method_type_directly (TYPE_METHOD_BASETYPE (type),
5792                                           inner,
5793                                           TYPE_ARG_TYPES (type));
5794       TYPE_ARG_TYPES (outer) = argtypes;
5795     }
5796   else
5797     return bottom;
5798
5799   TYPE_READONLY (outer) = TYPE_READONLY (type);
5800   TYPE_VOLATILE (outer) = TYPE_VOLATILE (type);
5801
5802   return outer;
5803 }
5804
5805 /* Returns a vector tree node given a mode (integer, vector, or BLKmode) and
5806    the inner type.  */
5807 tree
5808 build_vector_type_for_mode (tree innertype, enum machine_mode mode)
5809 {
5810   int nunits;
5811
5812   switch (GET_MODE_CLASS (mode))
5813     {
5814     case MODE_VECTOR_INT:
5815     case MODE_VECTOR_FLOAT:
5816       nunits = GET_MODE_NUNITS (mode);
5817       break;
5818
5819     case MODE_INT:
5820       /* Check that there are no leftover bits.  */
5821       gcc_assert (GET_MODE_BITSIZE (mode)
5822                   % TREE_INT_CST_LOW (TYPE_SIZE (innertype)) == 0);
5823
5824       nunits = GET_MODE_BITSIZE (mode)
5825                / TREE_INT_CST_LOW (TYPE_SIZE (innertype));
5826       break;
5827
5828     default:
5829       gcc_unreachable ();
5830     }
5831
5832   return make_vector_type (innertype, nunits, mode);
5833 }
5834
5835 /* Similarly, but takes the inner type and number of units, which must be
5836    a power of two.  */
5837
5838 tree
5839 build_vector_type (tree innertype, int nunits)
5840 {
5841   return make_vector_type (innertype, nunits, VOIDmode);
5842 }
5843
5844 /* Given an initializer INIT, return TRUE if INIT is zero or some
5845    aggregate of zeros.  Otherwise return FALSE.  */
5846 bool
5847 initializer_zerop (tree init)
5848 {
5849   tree elt;
5850
5851   STRIP_NOPS (init);
5852
5853   switch (TREE_CODE (init))
5854     {
5855     case INTEGER_CST:
5856       return integer_zerop (init);
5857
5858     case REAL_CST:
5859       /* ??? Note that this is not correct for C4X float formats.  There,
5860          a bit pattern of all zeros is 1.0; 0.0 is encoded with the most
5861          negative exponent.  */
5862       return real_zerop (init)
5863         && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init));
5864
5865     case COMPLEX_CST:
5866       return integer_zerop (init)
5867         || (real_zerop (init)
5868             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init)))
5869             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init))));
5870
5871     case VECTOR_CST:
5872       for (elt = TREE_VECTOR_CST_ELTS (init); elt; elt = TREE_CHAIN (elt))
5873         if (!initializer_zerop (TREE_VALUE (elt)))
5874           return false;
5875       return true;
5876
5877     case CONSTRUCTOR:
5878       elt = CONSTRUCTOR_ELTS (init);
5879       if (elt == NULL_TREE)
5880         return true;
5881
5882       /* A set is empty only if it has no elements.  */
5883       if (TREE_CODE (TREE_TYPE (init)) == SET_TYPE)
5884         return false;
5885
5886       for (; elt ; elt = TREE_CHAIN (elt))
5887         if (! initializer_zerop (TREE_VALUE (elt)))
5888           return false;
5889       return true;
5890
5891     default:
5892       return false;
5893     }
5894 }
5895
5896 void
5897 add_var_to_bind_expr (tree bind_expr, tree var)
5898 {
5899   BIND_EXPR_VARS (bind_expr)
5900     = chainon (BIND_EXPR_VARS (bind_expr), var);
5901   if (BIND_EXPR_BLOCK (bind_expr))
5902     BLOCK_VARS (BIND_EXPR_BLOCK (bind_expr))
5903       = BIND_EXPR_VARS (bind_expr);
5904 }
5905
5906 /* Build an empty statement.  */
5907
5908 tree
5909 build_empty_stmt (void)
5910 {
5911   return build1 (NOP_EXPR, void_type_node, size_zero_node);
5912 }
5913
5914
5915 /* Returns true if it is possible to prove that the index of
5916    an array access REF (an ARRAY_REF expression) falls into the
5917    array bounds.  */
5918
5919 bool
5920 in_array_bounds_p (tree ref)
5921 {
5922   tree idx = TREE_OPERAND (ref, 1);
5923   tree min, max;
5924
5925   if (TREE_CODE (idx) != INTEGER_CST)
5926     return false;
5927
5928   min = array_ref_low_bound (ref);
5929   max = array_ref_up_bound (ref);
5930   if (!min
5931       || !max
5932       || TREE_CODE (min) != INTEGER_CST
5933       || TREE_CODE (max) != INTEGER_CST)
5934     return false;
5935
5936   if (tree_int_cst_lt (idx, min)
5937       || tree_int_cst_lt (max, idx))
5938     return false;
5939
5940   return true;
5941 }
5942
5943 /* Return true if T (assumed to be a DECL) is a global variable.  */
5944
5945 bool
5946 is_global_var (tree t)
5947 {
5948   return (TREE_STATIC (t) || DECL_EXTERNAL (t));
5949 }
5950
5951 /* Return true if T (assumed to be a DECL) must be assigned a memory
5952    location.  */
5953
5954 bool
5955 needs_to_live_in_memory (tree t)
5956 {
5957   return (TREE_ADDRESSABLE (t)
5958           || is_global_var (t)
5959           || (TREE_CODE (t) == RESULT_DECL
5960               && aggregate_value_p (t, current_function_decl)));
5961 }
5962
5963 /* There are situations in which a language considers record types
5964    compatible which have different field lists.  Decide if two fields
5965    are compatible.  It is assumed that the parent records are compatible.  */
5966
5967 bool
5968 fields_compatible_p (tree f1, tree f2)
5969 {
5970   if (!operand_equal_p (DECL_FIELD_BIT_OFFSET (f1),
5971                         DECL_FIELD_BIT_OFFSET (f2), OEP_ONLY_CONST))
5972     return false;
5973
5974   if (!operand_equal_p (DECL_FIELD_OFFSET (f1),
5975                         DECL_FIELD_OFFSET (f2), OEP_ONLY_CONST))
5976     return false;
5977
5978   if (!lang_hooks.types_compatible_p (TREE_TYPE (f1), TREE_TYPE (f2)))
5979     return false;
5980
5981   return true;
5982 }
5983
5984 /* Locate within RECORD a field that is compatible with ORIG_FIELD.  */
5985
5986 tree
5987 find_compatible_field (tree record, tree orig_field)
5988 {
5989   tree f;
5990
5991   for (f = TYPE_FIELDS (record); f ; f = TREE_CHAIN (f))
5992     if (TREE_CODE (f) == FIELD_DECL
5993         && fields_compatible_p (f, orig_field))
5994       return f;
5995
5996   /* ??? Why isn't this on the main fields list?  */
5997   f = TYPE_VFIELD (record);
5998   if (f && TREE_CODE (f) == FIELD_DECL
5999       && fields_compatible_p (f, orig_field))
6000     return f;
6001
6002   /* ??? We should abort here, but Java appears to do Bad Things
6003      with inherited fields.  */
6004   return orig_field;
6005 }
6006
6007 /* Return value of a constant X.  */
6008
6009 HOST_WIDE_INT
6010 int_cst_value (tree x)
6011 {
6012   unsigned bits = TYPE_PRECISION (TREE_TYPE (x));
6013   unsigned HOST_WIDE_INT val = TREE_INT_CST_LOW (x);
6014   bool negative = ((val >> (bits - 1)) & 1) != 0;
6015
6016   gcc_assert (bits <= HOST_BITS_PER_WIDE_INT);
6017
6018   if (negative)
6019     val |= (~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1;
6020   else
6021     val &= ~((~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1);
6022
6023   return val;
6024 }
6025
6026 /* Returns the greatest common divisor of A and B, which must be
6027    INTEGER_CSTs.  */
6028
6029 tree
6030 tree_fold_gcd (tree a, tree b)
6031 {
6032   tree a_mod_b;
6033   tree type = TREE_TYPE (a);
6034
6035   gcc_assert (TREE_CODE (a) == INTEGER_CST);
6036   gcc_assert (TREE_CODE (b) == INTEGER_CST);
6037
6038   if (integer_zerop (a))
6039     return b;
6040
6041   if (integer_zerop (b))
6042     return a;
6043
6044   if (tree_int_cst_sgn (a) == -1)
6045     a = fold (build2 (MULT_EXPR, type, a,
6046                       convert (type, integer_minus_one_node)));
6047
6048   if (tree_int_cst_sgn (b) == -1)
6049     b = fold (build2 (MULT_EXPR, type, b,
6050                       convert (type, integer_minus_one_node)));
6051
6052   while (1)
6053     {
6054       a_mod_b = fold (build2 (FLOOR_MOD_EXPR, type, a, b));
6055
6056       if (!TREE_INT_CST_LOW (a_mod_b)
6057           && !TREE_INT_CST_HIGH (a_mod_b))
6058         return b;
6059
6060       a = b;
6061       b = a_mod_b;
6062     }
6063 }
6064
6065 /* Returns unsigned variant of TYPE.  */
6066
6067 tree
6068 unsigned_type_for (tree type)
6069 {
6070   return lang_hooks.types.unsigned_type (type);
6071 }
6072
6073 /* Returns signed variant of TYPE.  */
6074
6075 tree
6076 signed_type_for (tree type)
6077 {
6078   return lang_hooks.types.signed_type (type);
6079 }
6080
6081 /* Returns the largest value obtainable by casting something in INNER type to
6082    OUTER type.  */
6083
6084 tree
6085 upper_bound_in_type (tree outer, tree inner)
6086 {
6087   unsigned HOST_WIDE_INT lo, hi;
6088   unsigned bits = TYPE_PRECISION (inner);
6089
6090   if (TYPE_UNSIGNED (outer) || TYPE_UNSIGNED (inner))
6091     {
6092       /* Zero extending in these cases.  */
6093       if (bits <= HOST_BITS_PER_WIDE_INT)
6094         {
6095           hi = 0;
6096           lo = (~(unsigned HOST_WIDE_INT) 0)
6097                   >> (HOST_BITS_PER_WIDE_INT - bits);
6098         }
6099       else
6100         {
6101           hi = (~(unsigned HOST_WIDE_INT) 0)
6102                   >> (2 * HOST_BITS_PER_WIDE_INT - bits);
6103           lo = ~(unsigned HOST_WIDE_INT) 0;
6104         }
6105     }
6106   else
6107     {
6108       /* Sign extending in these cases.  */
6109       if (bits <= HOST_BITS_PER_WIDE_INT)
6110         {
6111           hi = 0;
6112           lo = (~(unsigned HOST_WIDE_INT) 0)
6113                   >> (HOST_BITS_PER_WIDE_INT - bits) >> 1;
6114         }
6115       else
6116         {
6117           hi = (~(unsigned HOST_WIDE_INT) 0)
6118                   >> (2 * HOST_BITS_PER_WIDE_INT - bits) >> 1;
6119           lo = ~(unsigned HOST_WIDE_INT) 0;
6120         }
6121     }
6122
6123   return fold_convert (outer,
6124                        build_int_cst_wide (inner, lo, hi));
6125 }
6126
6127 /* Returns the smallest value obtainable by casting something in INNER type to
6128    OUTER type.  */
6129
6130 tree
6131 lower_bound_in_type (tree outer, tree inner)
6132 {
6133   unsigned HOST_WIDE_INT lo, hi;
6134   unsigned bits = TYPE_PRECISION (inner);
6135
6136   if (TYPE_UNSIGNED (outer) || TYPE_UNSIGNED (inner))
6137     lo = hi = 0;
6138   else if (bits <= HOST_BITS_PER_WIDE_INT)
6139     {
6140       hi = ~(unsigned HOST_WIDE_INT) 0;
6141       lo = (~(unsigned HOST_WIDE_INT) 0) << (bits - 1);
6142     }
6143   else
6144     {
6145       hi = (~(unsigned HOST_WIDE_INT) 0) << (bits - HOST_BITS_PER_WIDE_INT - 1);
6146       lo = 0;
6147     }
6148
6149   return fold_convert (outer,
6150                        build_int_cst_wide (inner, lo, hi));
6151 }
6152
6153 #include "gt-tree.h"