gcc/tree.c

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