gcc/tree.c

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