gcc/gimple.c

   1 /* Gimple IR support functions.
   2
   3    Copyright 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
   4    Contributed by Aldy Hernandez <aldyh@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "target.h"
  27 #include "tree.h"
  28 #include "ggc.h"
  29 #include "hard-reg-set.h"
  30 #include "basic-block.h"
  31 #include "gimple.h"
  32 #include "diagnostic.h"
  33 #include "tree-flow.h"
  34 #include "value-prof.h"
  35 #include "flags.h"
  36 #include "alias.h"
  37 #include "demangle.h"
  38 #include "langhooks.h"
  39
  40 /* Global type table.  FIXME lto, it should be possible to re-use some
  41    of the type hashing routines in tree.c (type_hash_canon, type_hash_lookup,
  42    etc), but those assume that types were built with the various
  43    build_*_type routines which is not the case with the streamer.  */
  44 static GTY((if_marked ("ggc_marked_p"), param_is (union tree_node)))
  45   htab_t gimple_types;
  46 static GTY((if_marked ("ggc_marked_p"), param_is (union tree_node)))
  47   htab_t gimple_canonical_types;
  48 static GTY((if_marked ("tree_int_map_marked_p"), param_is (struct tree_int_map)))
  49   htab_t type_hash_cache;
  50 static GTY((if_marked ("tree_int_map_marked_p"), param_is (struct tree_int_map)))
  51   htab_t canonical_type_hash_cache;
  52
  53 /* Global type comparison cache.  This is by TYPE_UID for space efficiency
  54    and thus cannot use and does not need GC.  */
  55 static htab_t gtc_visited;
  56 static struct obstack gtc_ob;
  57
  58 /* All the tuples have their operand vector (if present) at the very bottom
  59    of the structure.  Therefore, the offset required to find the
  60    operands vector the size of the structure minus the size of the 1
  61    element tree array at the end (see gimple_ops).  */
  62 #define DEFGSSTRUCT(SYM, STRUCT, HAS_TREE_OP) \
  63         (HAS_TREE_OP ? sizeof (struct STRUCT) - sizeof (tree) : 0),
  64 EXPORTED_CONST size_t gimple_ops_offset_[] = {
  65 #include "gsstruct.def"
  66 };
  67 #undef DEFGSSTRUCT
  68
  69 #define DEFGSSTRUCT(SYM, STRUCT, HAS_TREE_OP) sizeof(struct STRUCT),
  70 static const size_t gsstruct_code_size[] = {
  71 #include "gsstruct.def"
  72 };
  73 #undef DEFGSSTRUCT
  74
  75 #define DEFGSCODE(SYM, NAME, GSSCODE)   NAME,
  76 const char *const gimple_code_name[] = {
  77 #include "gimple.def"
  78 };
  79 #undef DEFGSCODE
  80
  81 #define DEFGSCODE(SYM, NAME, GSSCODE)   GSSCODE,
  82 EXPORTED_CONST enum gimple_statement_structure_enum gss_for_code_[] = {
  83 #include "gimple.def"
  84 };
  85 #undef DEFGSCODE
  86
  87 #ifdef GATHER_STATISTICS
  88 /* Gimple stats.  */
  89
  90 int gimple_alloc_counts[(int) gimple_alloc_kind_all];
  91 int gimple_alloc_sizes[(int) gimple_alloc_kind_all];
  92
  93 /* Keep in sync with gimple.h:enum gimple_alloc_kind.  */
  94 static const char * const gimple_alloc_kind_names[] = {
  95     "assignments",
  96     "phi nodes",
  97     "conditionals",
  98     "sequences",
  99     "everything else"
 100 };
 101
 102 #endif /* GATHER_STATISTICS */
 103
 104 /* A cache of gimple_seq objects.  Sequences are created and destroyed
 105    fairly often during gimplification.  */
 106 static GTY ((deletable)) struct gimple_seq_d *gimple_seq_cache;
 107
 108 /* Private API manipulation functions shared only with some
 109    other files.  */
 110 extern void gimple_set_stored_syms (gimple, bitmap, bitmap_obstack *);
 111 extern void gimple_set_loaded_syms (gimple, bitmap, bitmap_obstack *);
 112
 113 /* Gimple tuple constructors.
 114    Note: Any constructor taking a ``gimple_seq'' as a parameter, can
 115    be passed a NULL to start with an empty sequence.  */
 116
 117 /* Set the code for statement G to CODE.  */
 118
 119 static inline void
 120 gimple_set_code (gimple g, enum gimple_code code)
 121 {
 122   g->gsbase.code = code;
 123 }
 124
 125 /* Return the number of bytes needed to hold a GIMPLE statement with
 126    code CODE.  */
 127
 128 static inline size_t
 129 gimple_size (enum gimple_code code)
 130 {
 131   return gsstruct_code_size[gss_for_code (code)];
 132 }
 133
 134 /* Allocate memory for a GIMPLE statement with code CODE and NUM_OPS
 135    operands.  */
 136
 137 gimple
 138 gimple_alloc_stat (enum gimple_code code, unsigned num_ops MEM_STAT_DECL)
 139 {
 140   size_t size;
 141   gimple stmt;
 142
 143   size = gimple_size (code);
 144   if (num_ops > 0)
 145     size += sizeof (tree) * (num_ops - 1);
 146
 147 #ifdef GATHER_STATISTICS
 148   {
 149     enum gimple_alloc_kind kind = gimple_alloc_kind (code);
 150     gimple_alloc_counts[(int) kind]++;
 151     gimple_alloc_sizes[(int) kind] += size;
 152   }
 153 #endif
 154
 155   stmt = ggc_alloc_cleared_gimple_statement_d_stat (size PASS_MEM_STAT);
 156   gimple_set_code (stmt, code);
 157   gimple_set_num_ops (stmt, num_ops);
 158
 159   /* Do not call gimple_set_modified here as it has other side
 160      effects and this tuple is still not completely built.  */
 161   stmt->gsbase.modified = 1;
 162
 163   return stmt;
 164 }
 165
 166 /* Set SUBCODE to be the code of the expression computed by statement G.  */
 167
 168 static inline void
 169 gimple_set_subcode (gimple g, unsigned subcode)
 170 {
 171   /* We only have 16 bits for the RHS code.  Assert that we are not
 172      overflowing it.  */
 173   gcc_assert (subcode < (1 << 16));
 174   g->gsbase.subcode = subcode;
 175 }
 176
 177
 178
 179 /* Build a tuple with operands.  CODE is the statement to build (which
 180    must be one of the GIMPLE_WITH_OPS tuples).  SUBCODE is the sub-code
 181    for the new tuple.  NUM_OPS is the number of operands to allocate.  */
 182
 183 #define gimple_build_with_ops(c, s, n) \
 184   gimple_build_with_ops_stat (c, s, n MEM_STAT_INFO)
 185
 186 static gimple
 187 gimple_build_with_ops_stat (enum gimple_code code, unsigned subcode,
 188                             unsigned num_ops MEM_STAT_DECL)
 189 {
 190   gimple s = gimple_alloc_stat (code, num_ops PASS_MEM_STAT);
 191   gimple_set_subcode (s, subcode);
 192
 193   return s;
 194 }
 195
 196
 197 /* Build a GIMPLE_RETURN statement returning RETVAL.  */
 198
 199 gimple
 200 gimple_build_return (tree retval)
 201 {
 202   gimple s = gimple_build_with_ops (GIMPLE_RETURN, ERROR_MARK, 1);
 203   if (retval)
 204     gimple_return_set_retval (s, retval);
 205   return s;
 206 }
 207
 208 /* Reset alias information on call S.  */
 209
 210 void
 211 gimple_call_reset_alias_info (gimple s)
 212 {
 213   if (gimple_call_flags (s) & ECF_CONST)
 214     memset (gimple_call_use_set (s), 0, sizeof (struct pt_solution));
 215   else
 216     pt_solution_reset (gimple_call_use_set (s));
 217   if (gimple_call_flags (s) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
 218     memset (gimple_call_clobber_set (s), 0, sizeof (struct pt_solution));
 219   else
 220     pt_solution_reset (gimple_call_clobber_set (s));
 221 }
 222
 223 /* Helper for gimple_build_call, gimple_build_call_vec and
 224    gimple_build_call_from_tree.  Build the basic components of a
 225    GIMPLE_CALL statement to function FN with NARGS arguments.  */
 226
 227 static inline gimple
 228 gimple_build_call_1 (tree fn, unsigned nargs)
 229 {
 230   gimple s = gimple_build_with_ops (GIMPLE_CALL, ERROR_MARK, nargs + 3);
 231   if (TREE_CODE (fn) == FUNCTION_DECL)
 232     fn = build_fold_addr_expr (fn);
 233   gimple_set_op (s, 1, fn);
 234   gimple_call_set_fntype (s, TREE_TYPE (TREE_TYPE (fn)));
 235   gimple_call_reset_alias_info (s);
 236   return s;
 237 }
 238
 239
 240 /* Build a GIMPLE_CALL statement to function FN with the arguments
 241    specified in vector ARGS.  */
 242
 243 gimple
 244 gimple_build_call_vec (tree fn, VEC(tree, heap) *args)
 245 {
 246   unsigned i;
 247   unsigned nargs = VEC_length (tree, args);
 248   gimple call = gimple_build_call_1 (fn, nargs);
 249
 250   for (i = 0; i < nargs; i++)
 251     gimple_call_set_arg (call, i, VEC_index (tree, args, i));
 252
 253   return call;
 254 }
 255
 256
 257 /* Build a GIMPLE_CALL statement to function FN.  NARGS is the number of
 258    arguments.  The ... are the arguments.  */
 259
 260 gimple
 261 gimple_build_call (tree fn, unsigned nargs, ...)
 262 {
 263   va_list ap;
 264   gimple call;
 265   unsigned i;
 266
 267   gcc_assert (TREE_CODE (fn) == FUNCTION_DECL || is_gimple_call_addr (fn));
 268
 269   call = gimple_build_call_1 (fn, nargs);
 270
 271   va_start (ap, nargs);
 272   for (i = 0; i < nargs; i++)
 273     gimple_call_set_arg (call, i, va_arg (ap, tree));
 274   va_end (ap);
 275
 276   return call;
 277 }
 278
 279
 280 /* Helper for gimple_build_call_internal and gimple_build_call_internal_vec.
 281    Build the basic components of a GIMPLE_CALL statement to internal
 282    function FN with NARGS arguments.  */
 283
 284 static inline gimple
 285 gimple_build_call_internal_1 (enum internal_fn fn, unsigned nargs)
 286 {
 287   gimple s = gimple_build_with_ops (GIMPLE_CALL, ERROR_MARK, nargs + 3);
 288   s->gsbase.subcode |= GF_CALL_INTERNAL;
 289   gimple_call_set_internal_fn (s, fn);
 290   gimple_call_reset_alias_info (s);
 291   return s;
 292 }
 293
 294
 295 /* Build a GIMPLE_CALL statement to internal function FN.  NARGS is
 296    the number of arguments.  The ... are the arguments.  */
 297
 298 gimple
 299 gimple_build_call_internal (enum internal_fn fn, unsigned nargs, ...)
 300 {
 301   va_list ap;
 302   gimple call;
 303   unsigned i;
 304
 305   call = gimple_build_call_internal_1 (fn, nargs);
 306   va_start (ap, nargs);
 307   for (i = 0; i < nargs; i++)
 308     gimple_call_set_arg (call, i, va_arg (ap, tree));
 309   va_end (ap);
 310
 311   return call;
 312 }
 313
 314
 315 /* Build a GIMPLE_CALL statement to internal function FN with the arguments
 316    specified in vector ARGS.  */
 317
 318 gimple
 319 gimple_build_call_internal_vec (enum internal_fn fn, VEC(tree, heap) *args)
 320 {
 321   unsigned i, nargs;
 322   gimple call;
 323
 324   nargs = VEC_length (tree, args);
 325   call = gimple_build_call_internal_1 (fn, nargs);
 326   for (i = 0; i < nargs; i++)
 327     gimple_call_set_arg (call, i, VEC_index (tree, args, i));
 328
 329   return call;
 330 }
 331
 332
 333 /* Build a GIMPLE_CALL statement from CALL_EXPR T.  Note that T is
 334    assumed to be in GIMPLE form already.  Minimal checking is done of
 335    this fact.  */
 336
 337 gimple
 338 gimple_build_call_from_tree (tree t)
 339 {
 340   unsigned i, nargs;
 341   gimple call;
 342   tree fndecl = get_callee_fndecl (t);
 343
 344   gcc_assert (TREE_CODE (t) == CALL_EXPR);
 345
 346   nargs = call_expr_nargs (t);
 347   call = gimple_build_call_1 (fndecl ? fndecl : CALL_EXPR_FN (t), nargs);
 348
 349   for (i = 0; i < nargs; i++)
 350     gimple_call_set_arg (call, i, CALL_EXPR_ARG (t, i));
 351
 352   gimple_set_block (call, TREE_BLOCK (t));
 353
 354   /* Carry all the CALL_EXPR flags to the new GIMPLE_CALL.  */
 355   gimple_call_set_chain (call, CALL_EXPR_STATIC_CHAIN (t));
 356   gimple_call_set_tail (call, CALL_EXPR_TAILCALL (t));
 357   gimple_call_set_cannot_inline (call, CALL_CANNOT_INLINE_P (t));
 358   gimple_call_set_return_slot_opt (call, CALL_EXPR_RETURN_SLOT_OPT (t));
 359   if (fndecl
 360       && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
 361       && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_ALLOCA)
 362     gimple_call_set_alloca_for_var (call, CALL_ALLOCA_FOR_VAR_P (t));
 363   else
 364     gimple_call_set_from_thunk (call, CALL_FROM_THUNK_P (t));
 365   gimple_call_set_va_arg_pack (call, CALL_EXPR_VA_ARG_PACK (t));
 366   gimple_call_set_nothrow (call, TREE_NOTHROW (t));
 367   gimple_set_no_warning (call, TREE_NO_WARNING (t));
 368
 369   return call;
 370 }
 371
 372
 373 /* Extract the operands and code for expression EXPR into *SUBCODE_P,
 374    *OP1_P, *OP2_P and *OP3_P respectively.  */
 375
 376 void
 377 extract_ops_from_tree_1 (tree expr, enum tree_code *subcode_p, tree *op1_p,
 378                          tree *op2_p, tree *op3_p)
 379 {
 380   enum gimple_rhs_class grhs_class;
 381
 382   *subcode_p = TREE_CODE (expr);
 383   grhs_class = get_gimple_rhs_class (*subcode_p);
 384
 385   if (grhs_class == GIMPLE_TERNARY_RHS)
 386     {
 387       *op1_p = TREE_OPERAND (expr, 0);
 388       *op2_p = TREE_OPERAND (expr, 1);
 389       *op3_p = TREE_OPERAND (expr, 2);
 390     }
 391   else if (grhs_class == GIMPLE_BINARY_RHS)
 392     {
 393       *op1_p = TREE_OPERAND (expr, 0);
 394       *op2_p = TREE_OPERAND (expr, 1);
 395       *op3_p = NULL_TREE;
 396     }
 397   else if (grhs_class == GIMPLE_UNARY_RHS)
 398     {
 399       *op1_p = TREE_OPERAND (expr, 0);
 400       *op2_p = NULL_TREE;
 401       *op3_p = NULL_TREE;
 402     }
 403   else if (grhs_class == GIMPLE_SINGLE_RHS)
 404     {
 405       *op1_p = expr;
 406       *op2_p = NULL_TREE;
 407       *op3_p = NULL_TREE;
 408     }
 409   else
 410     gcc_unreachable ();
 411 }
 412
 413
 414 /* Build a GIMPLE_ASSIGN statement.
 415
 416    LHS of the assignment.
 417    RHS of the assignment which can be unary or binary.  */
 418
 419 gimple
 420 gimple_build_assign_stat (tree lhs, tree rhs MEM_STAT_DECL)
 421 {
 422   enum tree_code subcode;
 423   tree op1, op2, op3;
 424
 425   extract_ops_from_tree_1 (rhs, &subcode, &op1, &op2, &op3);
 426   return gimple_build_assign_with_ops_stat (subcode, lhs, op1, op2, op3
 427                                             PASS_MEM_STAT);
 428 }
 429
 430
 431 /* Build a GIMPLE_ASSIGN statement with sub-code SUBCODE and operands
 432    OP1 and OP2.  If OP2 is NULL then SUBCODE must be of class
 433    GIMPLE_UNARY_RHS or GIMPLE_SINGLE_RHS.  */
 434
 435 gimple
 436 gimple_build_assign_with_ops_stat (enum tree_code subcode, tree lhs, tree op1,
 437                                    tree op2, tree op3 MEM_STAT_DECL)
 438 {
 439   unsigned num_ops;
 440   gimple p;
 441
 442   /* Need 1 operand for LHS and 1 or 2 for the RHS (depending on the
 443      code).  */
 444   num_ops = get_gimple_rhs_num_ops (subcode) + 1;
 445
 446   p = gimple_build_with_ops_stat (GIMPLE_ASSIGN, (unsigned)subcode, num_ops
 447                                   PASS_MEM_STAT);
 448   gimple_assign_set_lhs (p, lhs);
 449   gimple_assign_set_rhs1 (p, op1);
 450   if (op2)
 451     {
 452       gcc_assert (num_ops > 2);
 453       gimple_assign_set_rhs2 (p, op2);
 454     }
 455
 456   if (op3)
 457     {
 458       gcc_assert (num_ops > 3);
 459       gimple_assign_set_rhs3 (p, op3);
 460     }
 461
 462   return p;
 463 }
 464
 465
 466 /* Build a new GIMPLE_ASSIGN tuple and append it to the end of *SEQ_P.
 467
 468    DST/SRC are the destination and source respectively.  You can pass
 469    ungimplified trees in DST or SRC, in which case they will be
 470    converted to a gimple operand if necessary.
 471
 472    This function returns the newly created GIMPLE_ASSIGN tuple.  */
 473
 474 gimple
 475 gimplify_assign (tree dst, tree src, gimple_seq *seq_p)
 476 {
 477   tree t = build2 (MODIFY_EXPR, TREE_TYPE (dst), dst, src);
 478   gimplify_and_add (t, seq_p);
 479   ggc_free (t);
 480   return gimple_seq_last_stmt (*seq_p);
 481 }
 482
 483
 484 /* Build a GIMPLE_COND statement.
 485
 486    PRED is the condition used to compare LHS and the RHS.
 487    T_LABEL is the label to jump to if the condition is true.
 488    F_LABEL is the label to jump to otherwise.  */
 489
 490 gimple
 491 gimple_build_cond (enum tree_code pred_code, tree lhs, tree rhs,
 492                    tree t_label, tree f_label)
 493 {
 494   gimple p;
 495
 496   gcc_assert (TREE_CODE_CLASS (pred_code) == tcc_comparison);
 497   p = gimple_build_with_ops (GIMPLE_COND, pred_code, 4);
 498   gimple_cond_set_lhs (p, lhs);
 499   gimple_cond_set_rhs (p, rhs);
 500   gimple_cond_set_true_label (p, t_label);
 501   gimple_cond_set_false_label (p, f_label);
 502   return p;
 503 }
 504
 505
 506 /* Extract operands for a GIMPLE_COND statement out of COND_EXPR tree COND.  */
 507
 508 void
 509 gimple_cond_get_ops_from_tree (tree cond, enum tree_code *code_p,
 510                                tree *lhs_p, tree *rhs_p)
 511 {
 512   gcc_assert (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison
 513               || TREE_CODE (cond) == TRUTH_NOT_EXPR
 514               || is_gimple_min_invariant (cond)
 515               || SSA_VAR_P (cond));
 516
 517   extract_ops_from_tree (cond, code_p, lhs_p, rhs_p);
 518
 519   /* Canonicalize conditionals of the form 'if (!VAL)'.  */
 520   if (*code_p == TRUTH_NOT_EXPR)
 521     {
 522       *code_p = EQ_EXPR;
 523       gcc_assert (*lhs_p && *rhs_p == NULL_TREE);
 524       *rhs_p = build_zero_cst (TREE_TYPE (*lhs_p));
 525     }
 526   /* Canonicalize conditionals of the form 'if (VAL)'  */
 527   else if (TREE_CODE_CLASS (*code_p) != tcc_comparison)
 528     {
 529       *code_p = NE_EXPR;
 530       gcc_assert (*lhs_p && *rhs_p == NULL_TREE);
 531       *rhs_p = build_zero_cst (TREE_TYPE (*lhs_p));
 532     }
 533 }
 534
 535
 536 /* Build a GIMPLE_COND statement from the conditional expression tree
 537    COND.  T_LABEL and F_LABEL are as in gimple_build_cond.  */
 538
 539 gimple
 540 gimple_build_cond_from_tree (tree cond, tree t_label, tree f_label)
 541 {
 542   enum tree_code code;
 543   tree lhs, rhs;
 544
 545   gimple_cond_get_ops_from_tree (cond, &code, &lhs, &rhs);
 546   return gimple_build_cond (code, lhs, rhs, t_label, f_label);
 547 }
 548
 549 /* Set code, lhs, and rhs of a GIMPLE_COND from a suitable
 550    boolean expression tree COND.  */
 551
 552 void
 553 gimple_cond_set_condition_from_tree (gimple stmt, tree cond)
 554 {
 555   enum tree_code code;
 556   tree lhs, rhs;
 557
 558   gimple_cond_get_ops_from_tree (cond, &code, &lhs, &rhs);
 559   gimple_cond_set_condition (stmt, code, lhs, rhs);
 560 }
 561
 562 /* Build a GIMPLE_LABEL statement for LABEL.  */
 563
 564 gimple
 565 gimple_build_label (tree label)
 566 {
 567   gimple p = gimple_build_with_ops (GIMPLE_LABEL, ERROR_MARK, 1);
 568   gimple_label_set_label (p, label);
 569   return p;
 570 }
 571
 572 /* Build a GIMPLE_GOTO statement to label DEST.  */
 573
 574 gimple
 575 gimple_build_goto (tree dest)
 576 {
 577   gimple p = gimple_build_with_ops (GIMPLE_GOTO, ERROR_MARK, 1);
 578   gimple_goto_set_dest (p, dest);
 579   return p;
 580 }
 581
 582
 583 /* Build a GIMPLE_NOP statement.  */
 584
 585 gimple
 586 gimple_build_nop (void)
 587 {
 588   return gimple_alloc (GIMPLE_NOP, 0);
 589 }
 590
 591
 592 /* Build a GIMPLE_BIND statement.
 593    VARS are the variables in BODY.
 594    BLOCK is the containing block.  */
 595
 596 gimple
 597 gimple_build_bind (tree vars, gimple_seq body, tree block)
 598 {
 599   gimple p = gimple_alloc (GIMPLE_BIND, 0);
 600   gimple_bind_set_vars (p, vars);
 601   if (body)
 602     gimple_bind_set_body (p, body);
 603   if (block)
 604     gimple_bind_set_block (p, block);
 605   return p;
 606 }
 607
 608 /* Helper function to set the simple fields of a asm stmt.
 609
 610    STRING is a pointer to a string that is the asm blocks assembly code.
 611    NINPUT is the number of register inputs.
 612    NOUTPUT is the number of register outputs.
 613    NCLOBBERS is the number of clobbered registers.
 614    */
 615
 616 static inline gimple
 617 gimple_build_asm_1 (const char *string, unsigned ninputs, unsigned noutputs,
 618                     unsigned nclobbers, unsigned nlabels)
 619 {
 620   gimple p;
 621   int size = strlen (string);
 622
 623   /* ASMs with labels cannot have outputs.  This should have been
 624      enforced by the front end.  */
 625   gcc_assert (nlabels == 0 || noutputs == 0);
 626
 627   p = gimple_build_with_ops (GIMPLE_ASM, ERROR_MARK,
 628                              ninputs + noutputs + nclobbers + nlabels);
 629
 630   p->gimple_asm.ni = ninputs;
 631   p->gimple_asm.no = noutputs;
 632   p->gimple_asm.nc = nclobbers;
 633   p->gimple_asm.nl = nlabels;
 634   p->gimple_asm.string = ggc_alloc_string (string, size);
 635
 636 #ifdef GATHER_STATISTICS
 637   gimple_alloc_sizes[(int) gimple_alloc_kind (GIMPLE_ASM)] += size;
 638 #endif
 639
 640   return p;
 641 }
 642
 643 /* Build a GIMPLE_ASM statement.
 644
 645    STRING is the assembly code.
 646    NINPUT is the number of register inputs.
 647    NOUTPUT is the number of register outputs.
 648    NCLOBBERS is the number of clobbered registers.
 649    INPUTS is a vector of the input register parameters.
 650    OUTPUTS is a vector of the output register parameters.
 651    CLOBBERS is a vector of the clobbered register parameters.
 652    LABELS is a vector of destination labels.  */
 653
 654 gimple
 655 gimple_build_asm_vec (const char *string, VEC(tree,gc)* inputs,
 656                       VEC(tree,gc)* outputs, VEC(tree,gc)* clobbers,
 657                       VEC(tree,gc)* labels)
 658 {
 659   gimple p;
 660   unsigned i;
 661
 662   p = gimple_build_asm_1 (string,
 663                           VEC_length (tree, inputs),
 664                           VEC_length (tree, outputs),
 665                           VEC_length (tree, clobbers),
 666                           VEC_length (tree, labels));
 667
 668   for (i = 0; i < VEC_length (tree, inputs); i++)
 669     gimple_asm_set_input_op (p, i, VEC_index (tree, inputs, i));
 670
 671   for (i = 0; i < VEC_length (tree, outputs); i++)
 672     gimple_asm_set_output_op (p, i, VEC_index (tree, outputs, i));
 673
 674   for (i = 0; i < VEC_length (tree, clobbers); i++)
 675     gimple_asm_set_clobber_op (p, i, VEC_index (tree, clobbers, i));
 676
 677   for (i = 0; i < VEC_length (tree, labels); i++)
 678     gimple_asm_set_label_op (p, i, VEC_index (tree, labels, i));
 679
 680   return p;
 681 }
 682
 683 /* Build a GIMPLE_CATCH statement.
 684
 685   TYPES are the catch types.
 686   HANDLER is the exception handler.  */
 687
 688 gimple
 689 gimple_build_catch (tree types, gimple_seq handler)
 690 {
 691   gimple p = gimple_alloc (GIMPLE_CATCH, 0);
 692   gimple_catch_set_types (p, types);
 693   if (handler)
 694     gimple_catch_set_handler (p, handler);
 695
 696   return p;
 697 }
 698
 699 /* Build a GIMPLE_EH_FILTER statement.
 700
 701    TYPES are the filter's types.
 702    FAILURE is the filter's failure action.  */
 703
 704 gimple
 705 gimple_build_eh_filter (tree types, gimple_seq failure)
 706 {
 707   gimple p = gimple_alloc (GIMPLE_EH_FILTER, 0);
 708   gimple_eh_filter_set_types (p, types);
 709   if (failure)
 710     gimple_eh_filter_set_failure (p, failure);
 711
 712   return p;
 713 }
 714
 715 /* Build a GIMPLE_EH_MUST_NOT_THROW statement.  */
 716
 717 gimple
 718 gimple_build_eh_must_not_throw (tree decl)
 719 {
 720   gimple p = gimple_alloc (GIMPLE_EH_MUST_NOT_THROW, 0);
 721
 722   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 723   gcc_assert (flags_from_decl_or_type (decl) & ECF_NORETURN);
 724   gimple_eh_must_not_throw_set_fndecl (p, decl);
 725
 726   return p;
 727 }
 728
 729 /* Build a GIMPLE_TRY statement.
 730
 731    EVAL is the expression to evaluate.
 732    CLEANUP is the cleanup expression.
 733    KIND is either GIMPLE_TRY_CATCH or GIMPLE_TRY_FINALLY depending on
 734    whether this is a try/catch or a try/finally respectively.  */
 735
 736 gimple
 737 gimple_build_try (gimple_seq eval, gimple_seq cleanup,
 738                   enum gimple_try_flags kind)
 739 {
 740   gimple p;
 741
 742   gcc_assert (kind == GIMPLE_TRY_CATCH || kind == GIMPLE_TRY_FINALLY);
 743   p = gimple_alloc (GIMPLE_TRY, 0);
 744   gimple_set_subcode (p, kind);
 745   if (eval)
 746     gimple_try_set_eval (p, eval);
 747   if (cleanup)
 748     gimple_try_set_cleanup (p, cleanup);
 749
 750   return p;
 751 }
 752
 753 /* Construct a GIMPLE_WITH_CLEANUP_EXPR statement.
 754
 755    CLEANUP is the cleanup expression.  */
 756
 757 gimple
 758 gimple_build_wce (gimple_seq cleanup)
 759 {
 760   gimple p = gimple_alloc (GIMPLE_WITH_CLEANUP_EXPR, 0);
 761   if (cleanup)
 762     gimple_wce_set_cleanup (p, cleanup);
 763
 764   return p;
 765 }
 766
 767
 768 /* Build a GIMPLE_RESX statement.  */
 769
 770 gimple
 771 gimple_build_resx (int region)
 772 {
 773   gimple p = gimple_build_with_ops (GIMPLE_RESX, ERROR_MARK, 0);
 774   p->gimple_eh_ctrl.region = region;
 775   return p;
 776 }
 777
 778
 779 /* The helper for constructing a gimple switch statement.
 780    INDEX is the switch's index.
 781    NLABELS is the number of labels in the switch excluding the default.
 782    DEFAULT_LABEL is the default label for the switch statement.  */
 783
 784 gimple
 785 gimple_build_switch_nlabels (unsigned nlabels, tree index, tree default_label)
 786 {
 787   /* nlabels + 1 default label + 1 index.  */
 788   gimple p = gimple_build_with_ops (GIMPLE_SWITCH, ERROR_MARK,
 789                                     1 + (default_label != NULL) + nlabels);
 790   gimple_switch_set_index (p, index);
 791   if (default_label)
 792     gimple_switch_set_default_label (p, default_label);
 793   return p;
 794 }
 795
 796
 797 /* Build a GIMPLE_SWITCH statement.
 798
 799    INDEX is the switch's index.
 800    NLABELS is the number of labels in the switch excluding the DEFAULT_LABEL.
 801    ... are the labels excluding the default.  */
 802
 803 gimple
 804 gimple_build_switch (unsigned nlabels, tree index, tree default_label, ...)
 805 {
 806   va_list al;
 807   unsigned i, offset;
 808   gimple p = gimple_build_switch_nlabels (nlabels, index, default_label);
 809
 810   /* Store the rest of the labels.  */
 811   va_start (al, default_label);
 812   offset = (default_label != NULL);
 813   for (i = 0; i < nlabels; i++)
 814     gimple_switch_set_label (p, i + offset, va_arg (al, tree));
 815   va_end (al);
 816
 817   return p;
 818 }
 819
 820
 821 /* Build a GIMPLE_SWITCH statement.
 822
 823    INDEX is the switch's index.
 824    DEFAULT_LABEL is the default label
 825    ARGS is a vector of labels excluding the default.  */
 826
 827 gimple
 828 gimple_build_switch_vec (tree index, tree default_label, VEC(tree, heap) *args)
 829 {
 830   unsigned i, offset, nlabels = VEC_length (tree, args);
 831   gimple p = gimple_build_switch_nlabels (nlabels, index, default_label);
 832
 833   /* Copy the labels from the vector to the switch statement.  */
 834   offset = (default_label != NULL);
 835   for (i = 0; i < nlabels; i++)
 836     gimple_switch_set_label (p, i + offset, VEC_index (tree, args, i));
 837
 838   return p;
 839 }
 840
 841 /* Build a GIMPLE_EH_DISPATCH statement.  */
 842
 843 gimple
 844 gimple_build_eh_dispatch (int region)
 845 {
 846   gimple p = gimple_build_with_ops (GIMPLE_EH_DISPATCH, ERROR_MARK, 0);
 847   p->gimple_eh_ctrl.region = region;
 848   return p;
 849 }
 850
 851 /* Build a new GIMPLE_DEBUG_BIND statement.
 852
 853    VAR is bound to VALUE; block and location are taken from STMT.  */
 854
 855 gimple
 856 gimple_build_debug_bind_stat (tree var, tree value, gimple stmt MEM_STAT_DECL)
 857 {
 858   gimple p = gimple_build_with_ops_stat (GIMPLE_DEBUG,
 859                                          (unsigned)GIMPLE_DEBUG_BIND, 2
 860                                          PASS_MEM_STAT);
 861
 862   gimple_debug_bind_set_var (p, var);
 863   gimple_debug_bind_set_value (p, value);
 864   if (stmt)
 865     {
 866       gimple_set_block (p, gimple_block (stmt));
 867       gimple_set_location (p, gimple_location (stmt));
 868     }
 869
 870   return p;
 871 }
 872
 873
 874 /* Build a GIMPLE_OMP_CRITICAL statement.
 875
 876    BODY is the sequence of statements for which only one thread can execute.
 877    NAME is optional identifier for this critical block.  */
 878
 879 gimple
 880 gimple_build_omp_critical (gimple_seq body, tree name)
 881 {
 882   gimple p = gimple_alloc (GIMPLE_OMP_CRITICAL, 0);
 883   gimple_omp_critical_set_name (p, name);
 884   if (body)
 885     gimple_omp_set_body (p, body);
 886
 887   return p;
 888 }
 889
 890 /* Build a GIMPLE_OMP_FOR statement.
 891
 892    BODY is sequence of statements inside the for loop.
 893    CLAUSES, are any of the OMP loop construct's clauses: private, firstprivate,
 894    lastprivate, reductions, ordered, schedule, and nowait.
 895    COLLAPSE is the collapse count.
 896    PRE_BODY is the sequence of statements that are loop invariant.  */
 897
 898 gimple
 899 gimple_build_omp_for (gimple_seq body, tree clauses, size_t collapse,
 900                       gimple_seq pre_body)
 901 {
 902   gimple p = gimple_alloc (GIMPLE_OMP_FOR, 0);
 903   if (body)
 904     gimple_omp_set_body (p, body);
 905   gimple_omp_for_set_clauses (p, clauses);
 906   p->gimple_omp_for.collapse = collapse;
 907   p->gimple_omp_for.iter
 908       = ggc_alloc_cleared_vec_gimple_omp_for_iter (collapse);
 909   if (pre_body)
 910     gimple_omp_for_set_pre_body (p, pre_body);
 911
 912   return p;
 913 }
 914
 915
 916 /* Build a GIMPLE_OMP_PARALLEL statement.
 917
 918    BODY is sequence of statements which are executed in parallel.
 919    CLAUSES, are the OMP parallel construct's clauses.
 920    CHILD_FN is the function created for the parallel threads to execute.
 921    DATA_ARG are the shared data argument(s).  */
 922
 923 gimple
 924 gimple_build_omp_parallel (gimple_seq body, tree clauses, tree child_fn,
 925                            tree data_arg)
 926 {
 927   gimple p = gimple_alloc (GIMPLE_OMP_PARALLEL, 0);
 928   if (body)
 929     gimple_omp_set_body (p, body);
 930   gimple_omp_parallel_set_clauses (p, clauses);
 931   gimple_omp_parallel_set_child_fn (p, child_fn);
 932   gimple_omp_parallel_set_data_arg (p, data_arg);
 933
 934   return p;
 935 }
 936
 937
 938 /* Build a GIMPLE_OMP_TASK statement.
 939
 940    BODY is sequence of statements which are executed by the explicit task.
 941    CLAUSES, are the OMP parallel construct's clauses.
 942    CHILD_FN is the function created for the parallel threads to execute.
 943    DATA_ARG are the shared data argument(s).
 944    COPY_FN is the optional function for firstprivate initialization.
 945    ARG_SIZE and ARG_ALIGN are size and alignment of the data block.  */
 946
 947 gimple
 948 gimple_build_omp_task (gimple_seq body, tree clauses, tree child_fn,
 949                        tree data_arg, tree copy_fn, tree arg_size,
 950                        tree arg_align)
 951 {
 952   gimple p = gimple_alloc (GIMPLE_OMP_TASK, 0);
 953   if (body)
 954     gimple_omp_set_body (p, body);
 955   gimple_omp_task_set_clauses (p, clauses);
 956   gimple_omp_task_set_child_fn (p, child_fn);
 957   gimple_omp_task_set_data_arg (p, data_arg);
 958   gimple_omp_task_set_copy_fn (p, copy_fn);
 959   gimple_omp_task_set_arg_size (p, arg_size);
 960   gimple_omp_task_set_arg_align (p, arg_align);
 961
 962   return p;
 963 }
 964
 965
 966 /* Build a GIMPLE_OMP_SECTION statement for a sections statement.
 967
 968    BODY is the sequence of statements in the section.  */
 969
 970 gimple
 971 gimple_build_omp_section (gimple_seq body)
 972 {
 973   gimple p = gimple_alloc (GIMPLE_OMP_SECTION, 0);
 974   if (body)
 975     gimple_omp_set_body (p, body);
 976
 977   return p;
 978 }
 979
 980
 981 /* Build a GIMPLE_OMP_MASTER statement.
 982
 983    BODY is the sequence of statements to be executed by just the master.  */
 984
 985 gimple
 986 gimple_build_omp_master (gimple_seq body)
 987 {
 988   gimple p = gimple_alloc (GIMPLE_OMP_MASTER, 0);
 989   if (body)
 990     gimple_omp_set_body (p, body);
 991
 992   return p;
 993 }
 994
 995
 996 /* Build a GIMPLE_OMP_CONTINUE statement.
 997
 998    CONTROL_DEF is the definition of the control variable.
 999    CONTROL_USE is the use of the control variable.  */
1000
1001 gimple
1002 gimple_build_omp_continue (tree control_def, tree control_use)
1003 {
1004   gimple p = gimple_alloc (GIMPLE_OMP_CONTINUE, 0);
1005   gimple_omp_continue_set_control_def (p, control_def);
1006   gimple_omp_continue_set_control_use (p, control_use);
1007   return p;
1008 }
1009
1010 /* Build a GIMPLE_OMP_ORDERED statement.
1011
1012    BODY is the sequence of statements inside a loop that will executed in
1013    sequence.  */
1014
1015 gimple
1016 gimple_build_omp_ordered (gimple_seq body)
1017 {
1018   gimple p = gimple_alloc (GIMPLE_OMP_ORDERED, 0);
1019   if (body)
1020     gimple_omp_set_body (p, body);
1021
1022   return p;
1023 }
1024
1025
1026 /* Build a GIMPLE_OMP_RETURN statement.
1027    WAIT_P is true if this is a non-waiting return.  */
1028
1029 gimple
1030 gimple_build_omp_return (bool wait_p)
1031 {
1032   gimple p = gimple_alloc (GIMPLE_OMP_RETURN, 0);
1033   if (wait_p)
1034     gimple_omp_return_set_nowait (p);
1035
1036   return p;
1037 }
1038
1039
1040 /* Build a GIMPLE_OMP_SECTIONS statement.
1041
1042    BODY is a sequence of section statements.
1043    CLAUSES are any of the OMP sections contsruct's clauses: private,
1044    firstprivate, lastprivate, reduction, and nowait.  */
1045
1046 gimple
1047 gimple_build_omp_sections (gimple_seq body, tree clauses)
1048 {
1049   gimple p = gimple_alloc (GIMPLE_OMP_SECTIONS, 0);
1050   if (body)
1051     gimple_omp_set_body (p, body);
1052   gimple_omp_sections_set_clauses (p, clauses);
1053
1054   return p;
1055 }
1056
1057
1058 /* Build a GIMPLE_OMP_SECTIONS_SWITCH.  */
1059
1060 gimple
1061 gimple_build_omp_sections_switch (void)
1062 {
1063   return gimple_alloc (GIMPLE_OMP_SECTIONS_SWITCH, 0);
1064 }
1065
1066
1067 /* Build a GIMPLE_OMP_SINGLE statement.
1068
1069    BODY is the sequence of statements that will be executed once.
1070    CLAUSES are any of the OMP single construct's clauses: private, firstprivate,
1071    copyprivate, nowait.  */
1072
1073 gimple
1074 gimple_build_omp_single (gimple_seq body, tree clauses)
1075 {
1076   gimple p = gimple_alloc (GIMPLE_OMP_SINGLE, 0);
1077   if (body)
1078     gimple_omp_set_body (p, body);
1079   gimple_omp_single_set_clauses (p, clauses);
1080
1081   return p;
1082 }
1083
1084
1085 /* Build a GIMPLE_OMP_ATOMIC_LOAD statement.  */
1086
1087 gimple
1088 gimple_build_omp_atomic_load (tree lhs, tree rhs)
1089 {
1090   gimple p = gimple_alloc (GIMPLE_OMP_ATOMIC_LOAD, 0);
1091   gimple_omp_atomic_load_set_lhs (p, lhs);
1092   gimple_omp_atomic_load_set_rhs (p, rhs);
1093   return p;
1094 }
1095
1096 /* Build a GIMPLE_OMP_ATOMIC_STORE statement.
1097
1098    VAL is the value we are storing.  */
1099
1100 gimple
1101 gimple_build_omp_atomic_store (tree val)
1102 {
1103   gimple p = gimple_alloc (GIMPLE_OMP_ATOMIC_STORE, 0);
1104   gimple_omp_atomic_store_set_val (p, val);
1105   return p;
1106 }
1107
1108 /* Build a GIMPLE_PREDICT statement.  PREDICT is one of the predictors from
1109    predict.def, OUTCOME is NOT_TAKEN or TAKEN.  */
1110
1111 gimple
1112 gimple_build_predict (enum br_predictor predictor, enum prediction outcome)
1113 {
1114   gimple p = gimple_alloc (GIMPLE_PREDICT, 0);
1115   /* Ensure all the predictors fit into the lower bits of the subcode.  */
1116   gcc_assert ((int) END_PREDICTORS <= GF_PREDICT_TAKEN);
1117   gimple_predict_set_predictor (p, predictor);
1118   gimple_predict_set_outcome (p, outcome);
1119   return p;
1120 }
1121
1122 #if defined ENABLE_GIMPLE_CHECKING
1123 /* Complain of a gimple type mismatch and die.  */
1124
1125 void
1126 gimple_check_failed (const_gimple gs, const char *file, int line,
1127                      const char *function, enum gimple_code code,
1128                      enum tree_code subcode)
1129 {
1130   internal_error ("gimple check: expected %s(%s), have %s(%s) in %s, at %s:%d",
1131                   gimple_code_name[code],
1132                   tree_code_name[subcode],
1133                   gimple_code_name[gimple_code (gs)],
1134                   gs->gsbase.subcode > 0
1135                     ? tree_code_name[gs->gsbase.subcode]
1136                     : "",
1137                   function, trim_filename (file), line);
1138 }
1139 #endif /* ENABLE_GIMPLE_CHECKING */
1140
1141
1142 /* Allocate a new GIMPLE sequence in GC memory and return it.  If
1143    there are free sequences in GIMPLE_SEQ_CACHE return one of those
1144    instead.  */
1145
1146 gimple_seq
1147 gimple_seq_alloc (void)
1148 {
1149   gimple_seq seq = gimple_seq_cache;
1150   if (seq)
1151     {
1152       gimple_seq_cache = gimple_seq_cache->next_free;
1153       gcc_assert (gimple_seq_cache != seq);
1154       memset (seq, 0, sizeof (*seq));
1155     }
1156   else
1157     {
1158       seq = ggc_alloc_cleared_gimple_seq_d ();
1159 #ifdef GATHER_STATISTICS
1160       gimple_alloc_counts[(int) gimple_alloc_kind_seq]++;
1161       gimple_alloc_sizes[(int) gimple_alloc_kind_seq] += sizeof (*seq);
1162 #endif
1163     }
1164
1165   return seq;
1166 }
1167
1168 /* Return SEQ to the free pool of GIMPLE sequences.  */
1169
1170 void
1171 gimple_seq_free (gimple_seq seq)
1172 {
1173   if (seq == NULL)
1174     return;
1175
1176   gcc_assert (gimple_seq_first (seq) == NULL);
1177   gcc_assert (gimple_seq_last (seq) == NULL);
1178
1179   /* If this triggers, it's a sign that the same list is being freed
1180      twice.  */
1181   gcc_assert (seq != gimple_seq_cache || gimple_seq_cache == NULL);
1182
1183   /* Add SEQ to the pool of free sequences.  */
1184   seq->next_free = gimple_seq_cache;
1185   gimple_seq_cache = seq;
1186 }
1187
1188
1189 /* Link gimple statement GS to the end of the sequence *SEQ_P.  If
1190    *SEQ_P is NULL, a new sequence is allocated.  */
1191
1192 void
1193 gimple_seq_add_stmt (gimple_seq *seq_p, gimple gs)
1194 {
1195   gimple_stmt_iterator si;
1196
1197   if (gs == NULL)
1198     return;
1199
1200   if (*seq_p == NULL)
1201     *seq_p = gimple_seq_alloc ();
1202
1203   si = gsi_last (*seq_p);
1204   gsi_insert_after (&si, gs, GSI_NEW_STMT);
1205 }
1206
1207
1208 /* Append sequence SRC to the end of sequence *DST_P.  If *DST_P is
1209    NULL, a new sequence is allocated.  */
1210
1211 void
1212 gimple_seq_add_seq (gimple_seq *dst_p, gimple_seq src)
1213 {
1214   gimple_stmt_iterator si;
1215
1216   if (src == NULL)
1217     return;
1218
1219   if (*dst_p == NULL)
1220     *dst_p = gimple_seq_alloc ();
1221
1222   si = gsi_last (*dst_p);
1223   gsi_insert_seq_after (&si, src, GSI_NEW_STMT);
1224 }
1225
1226
1227 /* Helper function of empty_body_p.  Return true if STMT is an empty
1228    statement.  */
1229
1230 static bool
1231 empty_stmt_p (gimple stmt)
1232 {
1233   if (gimple_code (stmt) == GIMPLE_NOP)
1234     return true;
1235   if (gimple_code (stmt) == GIMPLE_BIND)
1236     return empty_body_p (gimple_bind_body (stmt));
1237   return false;
1238 }
1239
1240
1241 /* Return true if BODY contains nothing but empty statements.  */
1242
1243 bool
1244 empty_body_p (gimple_seq body)
1245 {
1246   gimple_stmt_iterator i;
1247
1248   if (gimple_seq_empty_p (body))
1249     return true;
1250   for (i = gsi_start (body); !gsi_end_p (i); gsi_next (&i))
1251     if (!empty_stmt_p (gsi_stmt (i))
1252         && !is_gimple_debug (gsi_stmt (i)))
1253       return false;
1254
1255   return true;
1256 }
1257
1258
1259 /* Perform a deep copy of sequence SRC and return the result.  */
1260
1261 gimple_seq
1262 gimple_seq_copy (gimple_seq src)
1263 {
1264   gimple_stmt_iterator gsi;
1265   gimple_seq new_seq = gimple_seq_alloc ();
1266   gimple stmt;
1267
1268   for (gsi = gsi_start (src); !gsi_end_p (gsi); gsi_next (&gsi))
1269     {
1270       stmt = gimple_copy (gsi_stmt (gsi));
1271       gimple_seq_add_stmt (&new_seq, stmt);
1272     }
1273
1274   return new_seq;
1275 }
1276
1277
1278 /* Walk all the statements in the sequence SEQ calling walk_gimple_stmt
1279    on each one.  WI is as in walk_gimple_stmt.
1280
1281    If walk_gimple_stmt returns non-NULL, the walk is stopped, the
1282    value is stored in WI->CALLBACK_RESULT and the statement that
1283    produced the value is returned.
1284
1285    Otherwise, all the statements are walked and NULL returned.  */
1286
1287 gimple
1288 walk_gimple_seq (gimple_seq seq, walk_stmt_fn callback_stmt,
1289                  walk_tree_fn callback_op, struct walk_stmt_info *wi)
1290 {
1291   gimple_stmt_iterator gsi;
1292
1293   for (gsi = gsi_start (seq); !gsi_end_p (gsi); gsi_next (&gsi))
1294     {
1295       tree ret = walk_gimple_stmt (&gsi, callback_stmt, callback_op, wi);
1296       if (ret)
1297         {
1298           /* If CALLBACK_STMT or CALLBACK_OP return a value, WI must exist
1299              to hold it.  */
1300           gcc_assert (wi);
1301           wi->callback_result = ret;
1302           return gsi_stmt (gsi);
1303         }
1304     }
1305
1306   if (wi)
1307     wi->callback_result = NULL_TREE;
1308
1309   return NULL;
1310 }
1311
1312
1313 /* Helper function for walk_gimple_stmt.  Walk operands of a GIMPLE_ASM.  */
1314
1315 static tree
1316 walk_gimple_asm (gimple stmt, walk_tree_fn callback_op,
1317                  struct walk_stmt_info *wi)
1318 {
1319   tree ret, op;
1320   unsigned noutputs;
1321   const char **oconstraints;
1322   unsigned i, n;
1323   const char *constraint;
1324   bool allows_mem, allows_reg, is_inout;
1325
1326   noutputs = gimple_asm_noutputs (stmt);
1327   oconstraints = (const char **) alloca ((noutputs) * sizeof (const char *));
1328
1329   if (wi)
1330     wi->is_lhs = true;
1331
1332   for (i = 0; i < noutputs; i++)
1333     {
1334       op = gimple_asm_output_op (stmt, i);
1335       constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (op)));
1336       oconstraints[i] = constraint;
1337       parse_output_constraint (&constraint, i, 0, 0, &allows_mem, &allows_reg,
1338                                &is_inout);
1339       if (wi)
1340         wi->val_only = (allows_reg || !allows_mem);
1341       ret = walk_tree (&TREE_VALUE (op), callback_op, wi, NULL);
1342       if (ret)
1343         return ret;
1344     }
1345
1346   n = gimple_asm_ninputs (stmt);
1347   for (i = 0; i < n; i++)
1348     {
1349       op = gimple_asm_input_op (stmt, i);
1350       constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (op)));
1351       parse_input_constraint (&constraint, 0, 0, noutputs, 0,
1352                               oconstraints, &allows_mem, &allows_reg);
1353       if (wi)
1354         {
1355           wi->val_only = (allows_reg || !allows_mem);
1356           /* Although input "m" is not really a LHS, we need a lvalue.  */
1357           wi->is_lhs = !wi->val_only;
1358         }
1359       ret = walk_tree (&TREE_VALUE (op), callback_op, wi, NULL);
1360       if (ret)
1361         return ret;
1362     }
1363
1364   if (wi)
1365     {
1366       wi->is_lhs = false;
1367       wi->val_only = true;
1368     }
1369
1370   n = gimple_asm_nlabels (stmt);
1371   for (i = 0; i < n; i++)
1372     {
1373       op = gimple_asm_label_op (stmt, i);
1374       ret = walk_tree (&TREE_VALUE (op), callback_op, wi, NULL);
1375       if (ret)
1376         return ret;
1377     }
1378
1379   return NULL_TREE;
1380 }
1381
1382
1383 /* Helper function of WALK_GIMPLE_STMT.  Walk every tree operand in
1384    STMT.  CALLBACK_OP and WI are as in WALK_GIMPLE_STMT.
1385
1386    CALLBACK_OP is called on each operand of STMT via walk_tree.
1387    Additional parameters to walk_tree must be stored in WI.  For each operand
1388    OP, walk_tree is called as:
1389
1390         walk_tree (&OP, CALLBACK_OP, WI, WI->PSET)
1391
1392    If CALLBACK_OP returns non-NULL for an operand, the remaining
1393    operands are not scanned.
1394
1395    The return value is that returned by the last call to walk_tree, or
1396    NULL_TREE if no CALLBACK_OP is specified.  */
1397
1398 tree
1399 walk_gimple_op (gimple stmt, walk_tree_fn callback_op,
1400                 struct walk_stmt_info *wi)
1401 {
1402   struct pointer_set_t *pset = (wi) ? wi->pset : NULL;
1403   unsigned i;
1404   tree ret = NULL_TREE;
1405
1406   switch (gimple_code (stmt))
1407     {
1408     case GIMPLE_ASSIGN:
1409       /* Walk the RHS operands.  If the LHS is of a non-renamable type or
1410          is a register variable, we may use a COMPONENT_REF on the RHS.  */
1411       if (wi)
1412         {
1413           tree lhs = gimple_assign_lhs (stmt);
1414           wi->val_only
1415             = (is_gimple_reg_type (TREE_TYPE (lhs)) && !is_gimple_reg (lhs))
1416               || !gimple_assign_single_p (stmt);
1417         }
1418
1419       for (i = 1; i < gimple_num_ops (stmt); i++)
1420         {
1421           ret = walk_tree (gimple_op_ptr (stmt, i), callback_op, wi,
1422                            pset);
1423           if (ret)
1424             return ret;
1425         }
1426
1427       /* Walk the LHS.  If the RHS is appropriate for a memory, we
1428          may use a COMPONENT_REF on the LHS.  */
1429       if (wi)
1430         {
1431           /* If the RHS has more than 1 operand, it is not appropriate
1432              for the memory.  */
1433           wi->val_only = !is_gimple_mem_rhs (gimple_assign_rhs1 (stmt))
1434                          || !gimple_assign_single_p (stmt);
1435           wi->is_lhs = true;
1436         }
1437
1438       ret = walk_tree (gimple_op_ptr (stmt, 0), callback_op, wi, pset);
1439       if (ret)
1440         return ret;
1441
1442       if (wi)
1443         {
1444           wi->val_only = true;
1445           wi->is_lhs = false;
1446         }
1447       break;
1448
1449     case GIMPLE_CALL:
1450       if (wi)
1451         {
1452           wi->is_lhs = false;
1453           wi->val_only = true;
1454         }
1455
1456       ret = walk_tree (gimple_call_chain_ptr (stmt), callback_op, wi, pset);
1457       if (ret)
1458         return ret;
1459
1460       ret = walk_tree (gimple_call_fn_ptr (stmt), callback_op, wi, pset);
1461       if (ret)
1462         return ret;
1463
1464       for (i = 0; i < gimple_call_num_args (stmt); i++)
1465         {
1466           if (wi)
1467             wi->val_only
1468               = is_gimple_reg_type (TREE_TYPE (gimple_call_arg (stmt, i)));
1469           ret = walk_tree (gimple_call_arg_ptr (stmt, i), callback_op, wi,
1470                            pset);
1471           if (ret)
1472             return ret;
1473         }
1474
1475       if (gimple_call_lhs (stmt))
1476         {
1477           if (wi)
1478             {
1479               wi->is_lhs = true;
1480               wi->val_only
1481                 = is_gimple_reg_type (TREE_TYPE (gimple_call_lhs (stmt)));
1482             }
1483
1484           ret = walk_tree (gimple_call_lhs_ptr (stmt), callback_op, wi, pset);
1485           if (ret)
1486             return ret;
1487         }
1488
1489       if (wi)
1490         {
1491           wi->is_lhs = false;
1492           wi->val_only = true;
1493         }
1494       break;
1495
1496     case GIMPLE_CATCH:
1497       ret = walk_tree (gimple_catch_types_ptr (stmt), callback_op, wi,
1498                        pset);
1499       if (ret)
1500         return ret;
1501       break;
1502
1503     case GIMPLE_EH_FILTER:
1504       ret = walk_tree (gimple_eh_filter_types_ptr (stmt), callback_op, wi,
1505                        pset);
1506       if (ret)
1507         return ret;
1508       break;
1509
1510     case GIMPLE_ASM:
1511       ret = walk_gimple_asm (stmt, callback_op, wi);
1512       if (ret)
1513         return ret;
1514       break;
1515
1516     case GIMPLE_OMP_CONTINUE:
1517       ret = walk_tree (gimple_omp_continue_control_def_ptr (stmt),
1518                        callback_op, wi, pset);
1519       if (ret)
1520         return ret;
1521
1522       ret = walk_tree (gimple_omp_continue_control_use_ptr (stmt),
1523                        callback_op, wi, pset);
1524       if (ret)
1525         return ret;
1526       break;
1527
1528     case GIMPLE_OMP_CRITICAL:
1529       ret = walk_tree (gimple_omp_critical_name_ptr (stmt), callback_op, wi,
1530                        pset);
1531       if (ret)
1532         return ret;
1533       break;
1534
1535     case GIMPLE_OMP_FOR:
1536       ret = walk_tree (gimple_omp_for_clauses_ptr (stmt), callback_op, wi,
1537                        pset);
1538       if (ret)
1539         return ret;
1540       for (i = 0; i < gimple_omp_for_collapse (stmt); i++)
1541         {
1542           ret = walk_tree (gimple_omp_for_index_ptr (stmt, i), callback_op,
1543                            wi, pset);
1544           if (ret)
1545             return ret;
1546           ret = walk_tree (gimple_omp_for_initial_ptr (stmt, i), callback_op,
1547                            wi, pset);
1548           if (ret)
1549             return ret;
1550           ret = walk_tree (gimple_omp_for_final_ptr (stmt, i), callback_op,
1551                            wi, pset);
1552           if (ret)
1553             return ret;
1554           ret = walk_tree (gimple_omp_for_incr_ptr (stmt, i), callback_op,
1555                            wi, pset);
1556         }
1557       if (ret)
1558         return ret;
1559       break;
1560
1561     case GIMPLE_OMP_PARALLEL:
1562       ret = walk_tree (gimple_omp_parallel_clauses_ptr (stmt), callback_op,
1563                        wi, pset);
1564       if (ret)
1565         return ret;
1566       ret = walk_tree (gimple_omp_parallel_child_fn_ptr (stmt), callback_op,
1567                        wi, pset);
1568       if (ret)
1569         return ret;
1570       ret = walk_tree (gimple_omp_parallel_data_arg_ptr (stmt), callback_op,
1571                        wi, pset);
1572       if (ret)
1573         return ret;
1574       break;
1575
1576     case GIMPLE_OMP_TASK:
1577       ret = walk_tree (gimple_omp_task_clauses_ptr (stmt), callback_op,
1578                        wi, pset);
1579       if (ret)
1580         return ret;
1581       ret = walk_tree (gimple_omp_task_child_fn_ptr (stmt), callback_op,
1582                        wi, pset);
1583       if (ret)
1584         return ret;
1585       ret = walk_tree (gimple_omp_task_data_arg_ptr (stmt), callback_op,
1586                        wi, pset);
1587       if (ret)
1588         return ret;
1589       ret = walk_tree (gimple_omp_task_copy_fn_ptr (stmt), callback_op,
1590                        wi, pset);
1591       if (ret)
1592         return ret;
1593       ret = walk_tree (gimple_omp_task_arg_size_ptr (stmt), callback_op,
1594                        wi, pset);
1595       if (ret)
1596         return ret;
1597       ret = walk_tree (gimple_omp_task_arg_align_ptr (stmt), callback_op,
1598                        wi, pset);
1599       if (ret)
1600         return ret;
1601       break;
1602
1603     case GIMPLE_OMP_SECTIONS:
1604       ret = walk_tree (gimple_omp_sections_clauses_ptr (stmt), callback_op,
1605                        wi, pset);
1606       if (ret)
1607         return ret;
1608
1609       ret = walk_tree (gimple_omp_sections_control_ptr (stmt), callback_op,
1610                        wi, pset);
1611       if (ret)
1612         return ret;
1613
1614       break;
1615
1616     case GIMPLE_OMP_SINGLE:
1617       ret = walk_tree (gimple_omp_single_clauses_ptr (stmt), callback_op, wi,
1618                        pset);
1619       if (ret)
1620         return ret;
1621       break;
1622
1623     case GIMPLE_OMP_ATOMIC_LOAD:
1624       ret = walk_tree (gimple_omp_atomic_load_lhs_ptr (stmt), callback_op, wi,
1625                        pset);
1626       if (ret)
1627         return ret;
1628
1629       ret = walk_tree (gimple_omp_atomic_load_rhs_ptr (stmt), callback_op, wi,
1630                        pset);
1631       if (ret)
1632         return ret;
1633       break;
1634
1635     case GIMPLE_OMP_ATOMIC_STORE:
1636       ret = walk_tree (gimple_omp_atomic_store_val_ptr (stmt), callback_op,
1637                        wi, pset);
1638       if (ret)
1639         return ret;
1640       break;
1641
1642       /* Tuples that do not have operands.  */
1643     case GIMPLE_NOP:
1644     case GIMPLE_RESX:
1645     case GIMPLE_OMP_RETURN:
1646     case GIMPLE_PREDICT:
1647       break;
1648
1649     default:
1650       {
1651         enum gimple_statement_structure_enum gss;
1652         gss = gimple_statement_structure (stmt);
1653         if (gss == GSS_WITH_OPS || gss == GSS_WITH_MEM_OPS)
1654           for (i = 0; i < gimple_num_ops (stmt); i++)
1655             {
1656               ret = walk_tree (gimple_op_ptr (stmt, i), callback_op, wi, pset);
1657               if (ret)
1658                 return ret;
1659             }
1660       }
1661       break;
1662     }
1663
1664   return NULL_TREE;
1665 }
1666
1667
1668 /* Walk the current statement in GSI (optionally using traversal state
1669    stored in WI).  If WI is NULL, no state is kept during traversal.
1670    The callback CALLBACK_STMT is called.  If CALLBACK_STMT indicates
1671    that it has handled all the operands of the statement, its return
1672    value is returned.  Otherwise, the return value from CALLBACK_STMT
1673    is discarded and its operands are scanned.
1674
1675    If CALLBACK_STMT is NULL or it didn't handle the operands,
1676    CALLBACK_OP is called on each operand of the statement via
1677    walk_gimple_op.  If walk_gimple_op returns non-NULL for any
1678    operand, the remaining operands are not scanned.  In this case, the
1679    return value from CALLBACK_OP is returned.
1680
1681    In any other case, NULL_TREE is returned.  */
1682
1683 tree
1684 walk_gimple_stmt (gimple_stmt_iterator *gsi, walk_stmt_fn callback_stmt,
1685                   walk_tree_fn callback_op, struct walk_stmt_info *wi)
1686 {
1687   gimple ret;
1688   tree tree_ret;
1689   gimple stmt = gsi_stmt (*gsi);
1690
1691   if (wi)
1692     wi->gsi = *gsi;
1693
1694   if (wi && wi->want_locations && gimple_has_location (stmt))
1695     input_location = gimple_location (stmt);
1696
1697   ret = NULL;
1698
1699   /* Invoke the statement callback.  Return if the callback handled
1700      all of STMT operands by itself.  */
1701   if (callback_stmt)
1702     {
1703       bool handled_ops = false;
1704       tree_ret = callback_stmt (gsi, &handled_ops, wi);
1705       if (handled_ops)
1706         return tree_ret;
1707
1708       /* If CALLBACK_STMT did not handle operands, it should not have
1709          a value to return.  */
1710       gcc_assert (tree_ret == NULL);
1711
1712       /* Re-read stmt in case the callback changed it.  */
1713       stmt = gsi_stmt (*gsi);
1714     }
1715
1716   /* If CALLBACK_OP is defined, invoke it on every operand of STMT.  */
1717   if (callback_op)
1718     {
1719       tree_ret = walk_gimple_op (stmt, callback_op, wi);
1720       if (tree_ret)
1721         return tree_ret;
1722     }
1723
1724   /* If STMT can have statements inside (e.g. GIMPLE_BIND), walk them.  */
1725   switch (gimple_code (stmt))
1726     {
1727     case GIMPLE_BIND:
1728       ret = walk_gimple_seq (gimple_bind_body (stmt), callback_stmt,
1729                              callback_op, wi);
1730       if (ret)
1731         return wi->callback_result;
1732       break;
1733
1734     case GIMPLE_CATCH:
1735       ret = walk_gimple_seq (gimple_catch_handler (stmt), callback_stmt,
1736                              callback_op, wi);
1737       if (ret)
1738         return wi->callback_result;
1739       break;
1740
1741     case GIMPLE_EH_FILTER:
1742       ret = walk_gimple_seq (gimple_eh_filter_failure (stmt), callback_stmt,
1743                              callback_op, wi);
1744       if (ret)
1745         return wi->callback_result;
1746       break;
1747
1748     case GIMPLE_TRY:
1749       ret = walk_gimple_seq (gimple_try_eval (stmt), callback_stmt, callback_op,
1750                              wi);
1751       if (ret)
1752         return wi->callback_result;
1753
1754       ret = walk_gimple_seq (gimple_try_cleanup (stmt), callback_stmt,
1755                              callback_op, wi);
1756       if (ret)
1757         return wi->callback_result;
1758       break;
1759
1760     case GIMPLE_OMP_FOR:
1761       ret = walk_gimple_seq (gimple_omp_for_pre_body (stmt), callback_stmt,
1762                              callback_op, wi);
1763       if (ret)
1764         return wi->callback_result;
1765
1766       /* FALL THROUGH.  */
1767     case GIMPLE_OMP_CRITICAL:
1768     case GIMPLE_OMP_MASTER:
1769     case GIMPLE_OMP_ORDERED:
1770     case GIMPLE_OMP_SECTION:
1771     case GIMPLE_OMP_PARALLEL:
1772     case GIMPLE_OMP_TASK:
1773     case GIMPLE_OMP_SECTIONS:
1774     case GIMPLE_OMP_SINGLE:
1775       ret = walk_gimple_seq (gimple_omp_body (stmt), callback_stmt, callback_op,
1776                              wi);
1777       if (ret)
1778         return wi->callback_result;
1779       break;
1780
1781     case GIMPLE_WITH_CLEANUP_EXPR:
1782       ret = walk_gimple_seq (gimple_wce_cleanup (stmt), callback_stmt,
1783                              callback_op, wi);
1784       if (ret)
1785         return wi->callback_result;
1786       break;
1787
1788     default:
1789       gcc_assert (!gimple_has_substatements (stmt));
1790       break;
1791     }
1792
1793   return NULL;
1794 }
1795
1796
1797 /* Set sequence SEQ to be the GIMPLE body for function FN.  */
1798
1799 void
1800 gimple_set_body (tree fndecl, gimple_seq seq)
1801 {
1802   struct function *fn = DECL_STRUCT_FUNCTION (fndecl);
1803   if (fn == NULL)
1804     {
1805       /* If FNDECL still does not have a function structure associated
1806          with it, then it does not make sense for it to receive a
1807          GIMPLE body.  */
1808       gcc_assert (seq == NULL);
1809     }
1810   else
1811     fn->gimple_body = seq;
1812 }
1813
1814
1815 /* Return the body of GIMPLE statements for function FN.  After the
1816    CFG pass, the function body doesn't exist anymore because it has
1817    been split up into basic blocks.  In this case, it returns
1818    NULL.  */
1819
1820 gimple_seq
1821 gimple_body (tree fndecl)
1822 {
1823   struct function *fn = DECL_STRUCT_FUNCTION (fndecl);
1824   return fn ? fn->gimple_body : NULL;
1825 }
1826
1827 /* Return true when FNDECL has Gimple body either in unlowered
1828    or CFG form.  */
1829 bool
1830 gimple_has_body_p (tree fndecl)
1831 {
1832   struct function *fn = DECL_STRUCT_FUNCTION (fndecl);
1833   return (gimple_body (fndecl) || (fn && fn->cfg));
1834 }
1835
1836 /* Return true if calls C1 and C2 are known to go to the same function.  */
1837
1838 bool
1839 gimple_call_same_target_p (const_gimple c1, const_gimple c2)
1840 {
1841   if (gimple_call_internal_p (c1))
1842     return (gimple_call_internal_p (c2)
1843             && gimple_call_internal_fn (c1) == gimple_call_internal_fn (c2));
1844   else
1845     return (gimple_call_fn (c1) == gimple_call_fn (c2)
1846             || (gimple_call_fndecl (c1)
1847                 && gimple_call_fndecl (c1) == gimple_call_fndecl (c2)));
1848 }
1849
1850 /* Detect flags from a GIMPLE_CALL.  This is just like
1851    call_expr_flags, but for gimple tuples.  */
1852
1853 int
1854 gimple_call_flags (const_gimple stmt)
1855 {
1856   int flags;
1857   tree decl = gimple_call_fndecl (stmt);
1858
1859   if (decl)
1860     flags = flags_from_decl_or_type (decl);
1861   else if (gimple_call_internal_p (stmt))
1862     flags = internal_fn_flags (gimple_call_internal_fn (stmt));
1863   else
1864     flags = flags_from_decl_or_type (gimple_call_fntype (stmt));
1865
1866   if (stmt->gsbase.subcode & GF_CALL_NOTHROW)
1867     flags |= ECF_NOTHROW;
1868
1869   return flags;
1870 }
1871
1872 /* Return the "fn spec" string for call STMT.  */
1873
1874 static tree
1875 gimple_call_fnspec (const_gimple stmt)
1876 {
1877   tree type, attr;
1878
1879   type = gimple_call_fntype (stmt);
1880   if (!type)
1881     return NULL_TREE;
1882
1883   attr = lookup_attribute ("fn spec", TYPE_ATTRIBUTES (type));
1884   if (!attr)
1885     return NULL_TREE;
1886
1887   return TREE_VALUE (TREE_VALUE (attr));
1888 }
1889
1890 /* Detects argument flags for argument number ARG on call STMT.  */
1891
1892 int
1893 gimple_call_arg_flags (const_gimple stmt, unsigned arg)
1894 {
1895   tree attr = gimple_call_fnspec (stmt);
1896
1897   if (!attr || 1 + arg >= (unsigned) TREE_STRING_LENGTH (attr))
1898     return 0;
1899
1900   switch (TREE_STRING_POINTER (attr)[1 + arg])
1901     {
1902     case 'x':
1903     case 'X':
1904       return EAF_UNUSED;
1905
1906     case 'R':
1907       return EAF_DIRECT | EAF_NOCLOBBER | EAF_NOESCAPE;
1908
1909     case 'r':
1910       return EAF_NOCLOBBER | EAF_NOESCAPE;
1911
1912     case 'W':
1913       return EAF_DIRECT | EAF_NOESCAPE;
1914
1915     case 'w':
1916       return EAF_NOESCAPE;
1917
1918     case '.':
1919     default:
1920       return 0;
1921     }
1922 }
1923
1924 /* Detects return flags for the call STMT.  */
1925
1926 int
1927 gimple_call_return_flags (const_gimple stmt)
1928 {
1929   tree attr;
1930
1931   if (gimple_call_flags (stmt) & ECF_MALLOC)
1932     return ERF_NOALIAS;
1933
1934   attr = gimple_call_fnspec (stmt);
1935   if (!attr || TREE_STRING_LENGTH (attr) < 1)
1936     return 0;
1937
1938   switch (TREE_STRING_POINTER (attr)[0])
1939     {
1940     case '1':
1941     case '2':
1942     case '3':
1943     case '4':
1944       return ERF_RETURNS_ARG | (TREE_STRING_POINTER (attr)[0] - '1');
1945
1946     case 'm':
1947       return ERF_NOALIAS;
1948
1949     case '.':
1950     default:
1951       return 0;
1952     }
1953 }
1954
1955
1956 /* Return true if GS is a copy assignment.  */
1957
1958 bool
1959 gimple_assign_copy_p (gimple gs)
1960 {
1961   return (gimple_assign_single_p (gs)
1962           && is_gimple_val (gimple_op (gs, 1)));
1963 }
1964
1965
1966 /* Return true if GS is a SSA_NAME copy assignment.  */
1967
1968 bool
1969 gimple_assign_ssa_name_copy_p (gimple gs)
1970 {
1971   return (gimple_assign_single_p (gs)
1972           && TREE_CODE (gimple_assign_lhs (gs)) == SSA_NAME
1973           && TREE_CODE (gimple_assign_rhs1 (gs)) == SSA_NAME);
1974 }
1975
1976
1977 /* Return true if GS is an assignment with a unary RHS, but the
1978    operator has no effect on the assigned value.  The logic is adapted
1979    from STRIP_NOPS.  This predicate is intended to be used in tuplifying
1980    instances in which STRIP_NOPS was previously applied to the RHS of
1981    an assignment.
1982
1983    NOTE: In the use cases that led to the creation of this function
1984    and of gimple_assign_single_p, it is typical to test for either
1985    condition and to proceed in the same manner.  In each case, the
1986    assigned value is represented by the single RHS operand of the
1987    assignment.  I suspect there may be cases where gimple_assign_copy_p,
1988    gimple_assign_single_p, or equivalent logic is used where a similar
1989    treatment of unary NOPs is appropriate.  */
1990
1991 bool
1992 gimple_assign_unary_nop_p (gimple gs)
1993 {
1994   return (is_gimple_assign (gs)
1995           && (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs))
1996               || gimple_assign_rhs_code (gs) == NON_LVALUE_EXPR)
1997           && gimple_assign_rhs1 (gs) != error_mark_node
1998           && (TYPE_MODE (TREE_TYPE (gimple_assign_lhs (gs)))
1999               == TYPE_MODE (TREE_TYPE (gimple_assign_rhs1 (gs)))));
2000 }
2001
2002 /* Set BB to be the basic block holding G.  */
2003
2004 void
2005 gimple_set_bb (gimple stmt, basic_block bb)
2006 {
2007   stmt->gsbase.bb = bb;
2008
2009   /* If the statement is a label, add the label to block-to-labels map
2010      so that we can speed up edge creation for GIMPLE_GOTOs.  */
2011   if (cfun->cfg && gimple_code (stmt) == GIMPLE_LABEL)
2012     {
2013       tree t;
2014       int uid;
2015
2016       t = gimple_label_label (stmt);
2017       uid = LABEL_DECL_UID (t);
2018       if (uid == -1)
2019         {
2020           unsigned old_len = VEC_length (basic_block, label_to_block_map);
2021           LABEL_DECL_UID (t) = uid = cfun->cfg->last_label_uid++;
2022           if (old_len <= (unsigned) uid)
2023             {
2024               unsigned new_len = 3 * uid / 2 + 1;
2025
2026               VEC_safe_grow_cleared (basic_block, gc, label_to_block_map,
2027                                      new_len);
2028             }
2029         }
2030
2031       VEC_replace (basic_block, label_to_block_map, uid, bb);
2032     }
2033 }
2034
2035
2036 /* Modify the RHS of the assignment pointed-to by GSI using the
2037    operands in the expression tree EXPR.
2038
2039    NOTE: The statement pointed-to by GSI may be reallocated if it
2040    did not have enough operand slots.
2041
2042    This function is useful to convert an existing tree expression into
2043    the flat representation used for the RHS of a GIMPLE assignment.
2044    It will reallocate memory as needed to expand or shrink the number
2045    of operand slots needed to represent EXPR.
2046
2047    NOTE: If you find yourself building a tree and then calling this
2048    function, you are most certainly doing it the slow way.  It is much
2049    better to build a new assignment or to use the function
2050    gimple_assign_set_rhs_with_ops, which does not require an
2051    expression tree to be built.  */
2052
2053 void
2054 gimple_assign_set_rhs_from_tree (gimple_stmt_iterator *gsi, tree expr)
2055 {
2056   enum tree_code subcode;
2057   tree op1, op2, op3;
2058
2059   extract_ops_from_tree_1 (expr, &subcode, &op1, &op2, &op3);
2060   gimple_assign_set_rhs_with_ops_1 (gsi, subcode, op1, op2, op3);
2061 }
2062
2063
2064 /* Set the RHS of assignment statement pointed-to by GSI to CODE with
2065    operands OP1, OP2 and OP3.
2066
2067    NOTE: The statement pointed-to by GSI may be reallocated if it
2068    did not have enough operand slots.  */
2069
2070 void
2071 gimple_assign_set_rhs_with_ops_1 (gimple_stmt_iterator *gsi, enum tree_code code,
2072                                   tree op1, tree op2, tree op3)
2073 {
2074   unsigned new_rhs_ops = get_gimple_rhs_num_ops (code);
2075   gimple stmt = gsi_stmt (*gsi);
2076
2077   /* If the new CODE needs more operands, allocate a new statement.  */
2078   if (gimple_num_ops (stmt) < new_rhs_ops + 1)
2079     {
2080       tree lhs = gimple_assign_lhs (stmt);
2081       gimple new_stmt = gimple_alloc (gimple_code (stmt), new_rhs_ops + 1);
2082       memcpy (new_stmt, stmt, gimple_size (gimple_code (stmt)));
2083       gsi_replace (gsi, new_stmt, true);
2084       stmt = new_stmt;
2085
2086       /* The LHS needs to be reset as this also changes the SSA name
2087          on the LHS.  */
2088       gimple_assign_set_lhs (stmt, lhs);
2089     }
2090
2091   gimple_set_num_ops (stmt, new_rhs_ops + 1);
2092   gimple_set_subcode (stmt, code);
2093   gimple_assign_set_rhs1 (stmt, op1);
2094   if (new_rhs_ops > 1)
2095     gimple_assign_set_rhs2 (stmt, op2);
2096   if (new_rhs_ops > 2)
2097     gimple_assign_set_rhs3 (stmt, op3);
2098 }
2099
2100
2101 /* Return the LHS of a statement that performs an assignment,
2102    either a GIMPLE_ASSIGN or a GIMPLE_CALL.  Returns NULL_TREE
2103    for a call to a function that returns no value, or for a
2104    statement other than an assignment or a call.  */
2105
2106 tree
2107 gimple_get_lhs (const_gimple stmt)
2108 {
2109   enum gimple_code code = gimple_code (stmt);
2110
2111   if (code == GIMPLE_ASSIGN)
2112     return gimple_assign_lhs (stmt);
2113   else if (code == GIMPLE_CALL)
2114     return gimple_call_lhs (stmt);
2115   else
2116     return NULL_TREE;
2117 }
2118
2119
2120 /* Set the LHS of a statement that performs an assignment,
2121    either a GIMPLE_ASSIGN or a GIMPLE_CALL.  */
2122
2123 void
2124 gimple_set_lhs (gimple stmt, tree lhs)
2125 {
2126   enum gimple_code code = gimple_code (stmt);
2127
2128   if (code == GIMPLE_ASSIGN)
2129     gimple_assign_set_lhs (stmt, lhs);
2130   else if (code == GIMPLE_CALL)
2131     gimple_call_set_lhs (stmt, lhs);
2132   else
2133     gcc_unreachable();
2134 }
2135
2136 /* Replace the LHS of STMT, an assignment, either a GIMPLE_ASSIGN or a
2137    GIMPLE_CALL, with NLHS, in preparation for modifying the RHS to an
2138    expression with a different value.
2139
2140    This will update any annotations (say debug bind stmts) referring
2141    to the original LHS, so that they use the RHS instead.  This is
2142    done even if NLHS and LHS are the same, for it is understood that
2143    the RHS will be modified afterwards, and NLHS will not be assigned
2144    an equivalent value.
2145
2146    Adjusting any non-annotation uses of the LHS, if needed, is a
2147    responsibility of the caller.
2148
2149    The effect of this call should be pretty much the same as that of
2150    inserting a copy of STMT before STMT, and then removing the
2151    original stmt, at which time gsi_remove() would have update
2152    annotations, but using this function saves all the inserting,
2153    copying and removing.  */
2154
2155 void
2156 gimple_replace_lhs (gimple stmt, tree nlhs)
2157 {
2158   if (MAY_HAVE_DEBUG_STMTS)
2159     {
2160       tree lhs = gimple_get_lhs (stmt);
2161
2162       gcc_assert (SSA_NAME_DEF_STMT (lhs) == stmt);
2163
2164       insert_debug_temp_for_var_def (NULL, lhs);
2165     }
2166
2167   gimple_set_lhs (stmt, nlhs);
2168 }
2169
2170 /* Return a deep copy of statement STMT.  All the operands from STMT
2171    are reallocated and copied using unshare_expr.  The DEF, USE, VDEF
2172    and VUSE operand arrays are set to empty in the new copy.  */
2173
2174 gimple
2175 gimple_copy (gimple stmt)
2176 {
2177   enum gimple_code code = gimple_code (stmt);
2178   unsigned num_ops = gimple_num_ops (stmt);
2179   gimple copy = gimple_alloc (code, num_ops);
2180   unsigned i;
2181
2182   /* Shallow copy all the fields from STMT.  */
2183   memcpy (copy, stmt, gimple_size (code));
2184
2185   /* If STMT has sub-statements, deep-copy them as well.  */
2186   if (gimple_has_substatements (stmt))
2187     {
2188       gimple_seq new_seq;
2189       tree t;
2190
2191       switch (gimple_code (stmt))
2192         {
2193         case GIMPLE_BIND:
2194           new_seq = gimple_seq_copy (gimple_bind_body (stmt));
2195           gimple_bind_set_body (copy, new_seq);
2196           gimple_bind_set_vars (copy, unshare_expr (gimple_bind_vars (stmt)));
2197           gimple_bind_set_block (copy, gimple_bind_block (stmt));
2198           break;
2199
2200         case GIMPLE_CATCH:
2201           new_seq = gimple_seq_copy (gimple_catch_handler (stmt));
2202           gimple_catch_set_handler (copy, new_seq);
2203           t = unshare_expr (gimple_catch_types (stmt));
2204           gimple_catch_set_types (copy, t);
2205           break;
2206
2207         case GIMPLE_EH_FILTER:
2208           new_seq = gimple_seq_copy (gimple_eh_filter_failure (stmt));
2209           gimple_eh_filter_set_failure (copy, new_seq);
2210           t = unshare_expr (gimple_eh_filter_types (stmt));
2211           gimple_eh_filter_set_types (copy, t);
2212           break;
2213
2214         case GIMPLE_TRY:
2215           new_seq = gimple_seq_copy (gimple_try_eval (stmt));
2216           gimple_try_set_eval (copy, new_seq);
2217           new_seq = gimple_seq_copy (gimple_try_cleanup (stmt));
2218           gimple_try_set_cleanup (copy, new_seq);
2219           break;
2220
2221         case GIMPLE_OMP_FOR:
2222           new_seq = gimple_seq_copy (gimple_omp_for_pre_body (stmt));
2223           gimple_omp_for_set_pre_body (copy, new_seq);
2224           t = unshare_expr (gimple_omp_for_clauses (stmt));
2225           gimple_omp_for_set_clauses (copy, t);
2226           copy->gimple_omp_for.iter
2227             = ggc_alloc_vec_gimple_omp_for_iter
2228             (gimple_omp_for_collapse (stmt));
2229           for (i = 0; i < gimple_omp_for_collapse (stmt); i++)
2230             {
2231               gimple_omp_for_set_cond (copy, i,
2232                                        gimple_omp_for_cond (stmt, i));
2233               gimple_omp_for_set_index (copy, i,
2234                                         gimple_omp_for_index (stmt, i));
2235               t = unshare_expr (gimple_omp_for_initial (stmt, i));
2236               gimple_omp_for_set_initial (copy, i, t);
2237               t = unshare_expr (gimple_omp_for_final (stmt, i));
2238               gimple_omp_for_set_final (copy, i, t);
2239               t = unshare_expr (gimple_omp_for_incr (stmt, i));
2240               gimple_omp_for_set_incr (copy, i, t);
2241             }
2242           goto copy_omp_body;
2243
2244         case GIMPLE_OMP_PARALLEL:
2245           t = unshare_expr (gimple_omp_parallel_clauses (stmt));
2246           gimple_omp_parallel_set_clauses (copy, t);
2247           t = unshare_expr (gimple_omp_parallel_child_fn (stmt));
2248           gimple_omp_parallel_set_child_fn (copy, t);
2249           t = unshare_expr (gimple_omp_parallel_data_arg (stmt));
2250           gimple_omp_parallel_set_data_arg (copy, t);
2251           goto copy_omp_body;
2252
2253         case GIMPLE_OMP_TASK:
2254           t = unshare_expr (gimple_omp_task_clauses (stmt));
2255           gimple_omp_task_set_clauses (copy, t);
2256           t = unshare_expr (gimple_omp_task_child_fn (stmt));
2257           gimple_omp_task_set_child_fn (copy, t);
2258           t = unshare_expr (gimple_omp_task_data_arg (stmt));
2259           gimple_omp_task_set_data_arg (copy, t);
2260           t = unshare_expr (gimple_omp_task_copy_fn (stmt));
2261           gimple_omp_task_set_copy_fn (copy, t);
2262           t = unshare_expr (gimple_omp_task_arg_size (stmt));
2263           gimple_omp_task_set_arg_size (copy, t);
2264           t = unshare_expr (gimple_omp_task_arg_align (stmt));
2265           gimple_omp_task_set_arg_align (copy, t);
2266           goto copy_omp_body;
2267
2268         case GIMPLE_OMP_CRITICAL:
2269           t = unshare_expr (gimple_omp_critical_name (stmt));
2270           gimple_omp_critical_set_name (copy, t);
2271           goto copy_omp_body;
2272
2273         case GIMPLE_OMP_SECTIONS:
2274           t = unshare_expr (gimple_omp_sections_clauses (stmt));
2275           gimple_omp_sections_set_clauses (copy, t);
2276           t = unshare_expr (gimple_omp_sections_control (stmt));
2277           gimple_omp_sections_set_control (copy, t);
2278           /* FALLTHRU  */
2279
2280         case GIMPLE_OMP_SINGLE:
2281         case GIMPLE_OMP_SECTION:
2282         case GIMPLE_OMP_MASTER:
2283         case GIMPLE_OMP_ORDERED:
2284         copy_omp_body:
2285           new_seq = gimple_seq_copy (gimple_omp_body (stmt));
2286           gimple_omp_set_body (copy, new_seq);
2287           break;
2288
2289         case GIMPLE_WITH_CLEANUP_EXPR:
2290           new_seq = gimple_seq_copy (gimple_wce_cleanup (stmt));
2291           gimple_wce_set_cleanup (copy, new_seq);
2292           break;
2293
2294         default:
2295           gcc_unreachable ();
2296         }
2297     }
2298
2299   /* Make copy of operands.  */
2300   if (num_ops > 0)
2301     {
2302       for (i = 0; i < num_ops; i++)
2303         gimple_set_op (copy, i, unshare_expr (gimple_op (stmt, i)));
2304
2305       /* Clear out SSA operand vectors on COPY.  */
2306       if (gimple_has_ops (stmt))
2307         {
2308           gimple_set_def_ops (copy, NULL);
2309           gimple_set_use_ops (copy, NULL);
2310         }
2311
2312       if (gimple_has_mem_ops (stmt))
2313         {
2314           gimple_set_vdef (copy, gimple_vdef (stmt));
2315           gimple_set_vuse (copy, gimple_vuse (stmt));
2316         }
2317
2318       /* SSA operands need to be updated.  */
2319       gimple_set_modified (copy, true);
2320     }
2321
2322   return copy;
2323 }
2324
2325
2326 /* Set the MODIFIED flag to MODIFIEDP, iff the gimple statement G has
2327    a MODIFIED field.  */
2328
2329 void
2330 gimple_set_modified (gimple s, bool modifiedp)
2331 {
2332   if (gimple_has_ops (s))
2333     s->gsbase.modified = (unsigned) modifiedp;
2334 }
2335
2336
2337 /* Return true if statement S has side-effects.  We consider a
2338    statement to have side effects if:
2339
2340    - It is a GIMPLE_CALL not marked with ECF_PURE or ECF_CONST.
2341    - Any of its operands are marked TREE_THIS_VOLATILE or TREE_SIDE_EFFECTS.  */
2342
2343 bool
2344 gimple_has_side_effects (const_gimple s)
2345 {
2346   unsigned i;
2347
2348   if (is_gimple_debug (s))
2349     return false;
2350
2351   /* We don't have to scan the arguments to check for
2352      volatile arguments, though, at present, we still
2353      do a scan to check for TREE_SIDE_EFFECTS.  */
2354   if (gimple_has_volatile_ops (s))
2355     return true;
2356
2357   if (is_gimple_call (s))
2358     {
2359       unsigned nargs = gimple_call_num_args (s);
2360       tree fn;
2361
2362       if (!(gimple_call_flags (s) & (ECF_CONST | ECF_PURE)))
2363         return true;
2364       else if (gimple_call_flags (s) & ECF_LOOPING_CONST_OR_PURE)
2365         /* An infinite loop is considered a side effect.  */
2366         return true;
2367
2368       if (gimple_call_lhs (s)
2369           && TREE_SIDE_EFFECTS (gimple_call_lhs (s)))
2370         {
2371           gcc_assert (gimple_has_volatile_ops (s));
2372           return true;
2373         }
2374
2375       fn = gimple_call_fn (s);
2376       if (fn && TREE_SIDE_EFFECTS (fn))
2377         return true;
2378
2379       for (i = 0; i < nargs; i++)
2380         if (TREE_SIDE_EFFECTS (gimple_call_arg (s, i)))
2381           {
2382             gcc_assert (gimple_has_volatile_ops (s));
2383             return true;
2384           }
2385
2386       return false;
2387     }
2388   else
2389     {
2390       for (i = 0; i < gimple_num_ops (s); i++)
2391         if (TREE_SIDE_EFFECTS (gimple_op (s, i)))
2392           {
2393             gcc_assert (gimple_has_volatile_ops (s));
2394             return true;
2395           }
2396     }
2397
2398   return false;
2399 }
2400
2401 /* Return true if the RHS of statement S has side effects.
2402    We may use it to determine if it is admissable to replace
2403    an assignment or call with a copy of a previously-computed
2404    value.  In such cases, side-effects due to the LHS are
2405    preserved.  */
2406
2407 bool
2408 gimple_rhs_has_side_effects (const_gimple s)
2409 {
2410   unsigned i;
2411
2412   if (is_gimple_call (s))
2413     {
2414       unsigned nargs = gimple_call_num_args (s);
2415       tree fn;
2416
2417       if (!(gimple_call_flags (s) & (ECF_CONST | ECF_PURE)))
2418         return true;
2419
2420       /* We cannot use gimple_has_volatile_ops here,
2421          because we must ignore a volatile LHS.  */
2422       fn = gimple_call_fn (s);
2423       if (fn && (TREE_SIDE_EFFECTS (fn) || TREE_THIS_VOLATILE (fn)))
2424         {
2425           gcc_assert (gimple_has_volatile_ops (s));
2426           return true;
2427         }
2428
2429       for (i = 0; i < nargs; i++)
2430         if (TREE_SIDE_EFFECTS (gimple_call_arg (s, i))
2431             || TREE_THIS_VOLATILE (gimple_call_arg (s, i)))
2432           return true;
2433
2434       return false;
2435     }
2436   else if (is_gimple_assign (s))
2437     {
2438       /* Skip the first operand, the LHS. */
2439       for (i = 1; i < gimple_num_ops (s); i++)
2440         if (TREE_SIDE_EFFECTS (gimple_op (s, i))
2441             || TREE_THIS_VOLATILE (gimple_op (s, i)))
2442           {
2443             gcc_assert (gimple_has_volatile_ops (s));
2444             return true;
2445           }
2446     }
2447   else if (is_gimple_debug (s))
2448     return false;
2449   else
2450     {
2451       /* For statements without an LHS, examine all arguments.  */
2452       for (i = 0; i < gimple_num_ops (s); i++)
2453         if (TREE_SIDE_EFFECTS (gimple_op (s, i))
2454             || TREE_THIS_VOLATILE (gimple_op (s, i)))
2455           {
2456             gcc_assert (gimple_has_volatile_ops (s));
2457             return true;
2458           }
2459     }
2460
2461   return false;
2462 }
2463
2464 /* Helper for gimple_could_trap_p and gimple_assign_rhs_could_trap_p.
2465    Return true if S can trap.  When INCLUDE_MEM is true, check whether
2466    the memory operations could trap.  When INCLUDE_STORES is true and
2467    S is a GIMPLE_ASSIGN, the LHS of the assignment is also checked.  */
2468
2469 bool
2470 gimple_could_trap_p_1 (gimple s, bool include_mem, bool include_stores)
2471 {
2472   tree t, div = NULL_TREE;
2473   enum tree_code op;
2474
2475   if (include_mem)
2476     {
2477       unsigned i, start = (is_gimple_assign (s) && !include_stores) ? 1 : 0;
2478
2479       for (i = start; i < gimple_num_ops (s); i++)
2480         if (tree_could_trap_p (gimple_op (s, i)))
2481           return true;
2482     }
2483
2484   switch (gimple_code (s))
2485     {
2486     case GIMPLE_ASM:
2487       return gimple_asm_volatile_p (s);
2488
2489     case GIMPLE_CALL:
2490       t = gimple_call_fndecl (s);
2491       /* Assume that calls to weak functions may trap.  */
2492       if (!t || !DECL_P (t) || DECL_WEAK (t))
2493         return true;
2494       return false;
2495
2496     case GIMPLE_ASSIGN:
2497       t = gimple_expr_type (s);
2498       op = gimple_assign_rhs_code (s);
2499       if (get_gimple_rhs_class (op) == GIMPLE_BINARY_RHS)
2500         div = gimple_assign_rhs2 (s);
2501       return (operation_could_trap_p (op, FLOAT_TYPE_P (t),
2502                                       (INTEGRAL_TYPE_P (t)
2503                                        && TYPE_OVERFLOW_TRAPS (t)),
2504                                       div));
2505
2506     default:
2507       break;
2508     }
2509
2510   return false;
2511 }
2512
2513 /* Return true if statement S can trap.  */
2514
2515 bool
2516 gimple_could_trap_p (gimple s)
2517 {
2518   return gimple_could_trap_p_1 (s, true, true);
2519 }
2520
2521 /* Return true if RHS of a GIMPLE_ASSIGN S can trap.  */
2522
2523 bool
2524 gimple_assign_rhs_could_trap_p (gimple s)
2525 {
2526   gcc_assert (is_gimple_assign (s));
2527   return gimple_could_trap_p_1 (s, true, false);
2528 }
2529
2530
2531 /* Print debugging information for gimple stmts generated.  */
2532
2533 void
2534 dump_gimple_statistics (void)
2535 {
2536 #ifdef GATHER_STATISTICS
2537   int i, total_tuples = 0, total_bytes = 0;
2538
2539   fprintf (stderr, "\nGIMPLE statements\n");
2540   fprintf (stderr, "Kind                   Stmts      Bytes\n");
2541   fprintf (stderr, "---------------------------------------\n");
2542   for (i = 0; i < (int) gimple_alloc_kind_all; ++i)
2543     {
2544       fprintf (stderr, "%-20s %7d %10d\n", gimple_alloc_kind_names[i],
2545           gimple_alloc_counts[i], gimple_alloc_sizes[i]);
2546       total_tuples += gimple_alloc_counts[i];
2547       total_bytes += gimple_alloc_sizes[i];
2548     }
2549   fprintf (stderr, "---------------------------------------\n");
2550   fprintf (stderr, "%-20s %7d %10d\n", "Total", total_tuples, total_bytes);
2551   fprintf (stderr, "---------------------------------------\n");
2552 #else
2553   fprintf (stderr, "No gimple statistics\n");
2554 #endif
2555 }
2556
2557
2558 /* Return the number of operands needed on the RHS of a GIMPLE
2559    assignment for an expression with tree code CODE.  */
2560
2561 unsigned
2562 get_gimple_rhs_num_ops (enum tree_code code)
2563 {
2564   enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code);
2565
2566   if (rhs_class == GIMPLE_UNARY_RHS || rhs_class == GIMPLE_SINGLE_RHS)
2567     return 1;
2568   else if (rhs_class == GIMPLE_BINARY_RHS)
2569     return 2;
2570   else if (rhs_class == GIMPLE_TERNARY_RHS)
2571     return 3;
2572   else
2573     gcc_unreachable ();
2574 }
2575
2576 #define DEFTREECODE(SYM, STRING, TYPE, NARGS)                               \
2577   (unsigned char)                                                           \
2578   ((TYPE) == tcc_unary ? GIMPLE_UNARY_RHS                                   \
2579    : ((TYPE) == tcc_binary                                                  \
2580       || (TYPE) == tcc_comparison) ? GIMPLE_BINARY_RHS                      \
2581    : ((TYPE) == tcc_constant                                                \
2582       || (TYPE) == tcc_declaration                                          \
2583       || (TYPE) == tcc_reference) ? GIMPLE_SINGLE_RHS                       \
2584    : ((SYM) == TRUTH_AND_EXPR                                               \
2585       || (SYM) == TRUTH_OR_EXPR                                             \
2586       || (SYM) == TRUTH_XOR_EXPR) ? GIMPLE_BINARY_RHS                       \
2587    : (SYM) == TRUTH_NOT_EXPR ? GIMPLE_UNARY_RHS                             \
2588    : ((SYM) == WIDEN_MULT_PLUS_EXPR                                         \
2589       || (SYM) == WIDEN_MULT_MINUS_EXPR                                     \
2590       || (SYM) == DOT_PROD_EXPR                                             \
2591       || (SYM) == REALIGN_LOAD_EXPR                                         \
2592       || (SYM) == FMA_EXPR) ? GIMPLE_TERNARY_RHS                            \
2593    : ((SYM) == COND_EXPR                                                    \
2594       || (SYM) == CONSTRUCTOR                                               \
2595       || (SYM) == OBJ_TYPE_REF                                              \
2596       || (SYM) == ASSERT_EXPR                                               \
2597       || (SYM) == ADDR_EXPR                                                 \
2598       || (SYM) == WITH_SIZE_EXPR                                            \
2599       || (SYM) == SSA_NAME                                                  \
2600       || (SYM) == VEC_COND_EXPR) ? GIMPLE_SINGLE_RHS                        \
2601    : GIMPLE_INVALID_RHS),
2602 #define END_OF_BASE_TREE_CODES (unsigned char) GIMPLE_INVALID_RHS,
2603
2604 const unsigned char gimple_rhs_class_table[] = {
2605 #include "all-tree.def"
2606 };
2607
2608 #undef DEFTREECODE
2609 #undef END_OF_BASE_TREE_CODES
2610
2611 /* For the definitive definition of GIMPLE, see doc/tree-ssa.texi.  */
2612
2613 /* Validation of GIMPLE expressions.  */
2614
2615 /* Returns true iff T is a valid RHS for an assignment to a renamed
2616    user -- or front-end generated artificial -- variable.  */
2617
2618 bool
2619 is_gimple_reg_rhs (tree t)
2620 {
2621   return get_gimple_rhs_class (TREE_CODE (t)) != GIMPLE_INVALID_RHS;
2622 }
2623
2624 /* Returns true iff T is a valid RHS for an assignment to an un-renamed
2625    LHS, or for a call argument.  */
2626
2627 bool
2628 is_gimple_mem_rhs (tree t)
2629 {
2630   /* If we're dealing with a renamable type, either source or dest must be
2631      a renamed variable.  */
2632   if (is_gimple_reg_type (TREE_TYPE (t)))
2633     return is_gimple_val (t);
2634   else
2635     return is_gimple_val (t) || is_gimple_lvalue (t);
2636 }
2637
2638 /*  Return true if T is a valid LHS for a GIMPLE assignment expression.  */
2639
2640 bool
2641 is_gimple_lvalue (tree t)
2642 {
2643   return (is_gimple_addressable (t)
2644           || TREE_CODE (t) == WITH_SIZE_EXPR
2645           /* These are complex lvalues, but don't have addresses, so they
2646              go here.  */
2647           || TREE_CODE (t) == BIT_FIELD_REF);
2648 }
2649
2650 /*  Return true if T is a GIMPLE condition.  */
2651
2652 bool
2653 is_gimple_condexpr (tree t)
2654 {
2655   return (is_gimple_val (t) || (COMPARISON_CLASS_P (t)
2656                                 && !tree_could_throw_p (t)
2657                                 && is_gimple_val (TREE_OPERAND (t, 0))
2658                                 && is_gimple_val (TREE_OPERAND (t, 1))));
2659 }
2660
2661 /*  Return true if T is something whose address can be taken.  */
2662
2663 bool
2664 is_gimple_addressable (tree t)
2665 {
2666   return (is_gimple_id (t) || handled_component_p (t)
2667           || TREE_CODE (t) == MEM_REF);
2668 }
2669
2670 /* Return true if T is a valid gimple constant.  */
2671
2672 bool
2673 is_gimple_constant (const_tree t)
2674 {
2675   switch (TREE_CODE (t))
2676     {
2677     case INTEGER_CST:
2678     case REAL_CST:
2679     case FIXED_CST:
2680     case STRING_CST:
2681     case COMPLEX_CST:
2682     case VECTOR_CST:
2683       return true;
2684
2685     /* Vector constant constructors are gimple invariant.  */
2686     case CONSTRUCTOR:
2687       if (TREE_TYPE (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2688         return TREE_CONSTANT (t);
2689       else
2690         return false;
2691
2692     default:
2693       return false;
2694     }
2695 }
2696
2697 /* Return true if T is a gimple address.  */
2698
2699 bool
2700 is_gimple_address (const_tree t)
2701 {
2702   tree op;
2703
2704   if (TREE_CODE (t) != ADDR_EXPR)
2705     return false;
2706
2707   op = TREE_OPERAND (t, 0);
2708   while (handled_component_p (op))
2709     {
2710       if ((TREE_CODE (op) == ARRAY_REF
2711            || TREE_CODE (op) == ARRAY_RANGE_REF)
2712           && !is_gimple_val (TREE_OPERAND (op, 1)))
2713             return false;
2714
2715       op = TREE_OPERAND (op, 0);
2716     }
2717
2718   if (CONSTANT_CLASS_P (op) || TREE_CODE (op) == MEM_REF)
2719     return true;
2720
2721   switch (TREE_CODE (op))
2722     {
2723     case PARM_DECL:
2724     case RESULT_DECL:
2725     case LABEL_DECL:
2726     case FUNCTION_DECL:
2727     case VAR_DECL:
2728     case CONST_DECL:
2729       return true;
2730
2731     default:
2732       return false;
2733     }
2734 }
2735
2736 /* Strip out all handled components that produce invariant
2737    offsets.  */
2738
2739 static const_tree
2740 strip_invariant_refs (const_tree op)
2741 {
2742   while (handled_component_p (op))
2743     {
2744       switch (TREE_CODE (op))
2745         {
2746         case ARRAY_REF:
2747         case ARRAY_RANGE_REF:
2748           if (!is_gimple_constant (TREE_OPERAND (op, 1))
2749               || TREE_OPERAND (op, 2) != NULL_TREE
2750               || TREE_OPERAND (op, 3) != NULL_TREE)
2751             return NULL;
2752           break;
2753
2754         case COMPONENT_REF:
2755           if (TREE_OPERAND (op, 2) != NULL_TREE)
2756             return NULL;
2757           break;
2758
2759         default:;
2760         }
2761       op = TREE_OPERAND (op, 0);
2762     }
2763
2764   return op;
2765 }
2766
2767 /* Return true if T is a gimple invariant address.  */
2768
2769 bool
2770 is_gimple_invariant_address (const_tree t)
2771 {
2772   const_tree op;
2773
2774   if (TREE_CODE (t) != ADDR_EXPR)
2775     return false;
2776
2777   op = strip_invariant_refs (TREE_OPERAND (t, 0));
2778   if (!op)
2779     return false;
2780
2781   if (TREE_CODE (op) == MEM_REF)
2782     {
2783       const_tree op0 = TREE_OPERAND (op, 0);
2784       return (TREE_CODE (op0) == ADDR_EXPR
2785               && (CONSTANT_CLASS_P (TREE_OPERAND (op0, 0))
2786                   || decl_address_invariant_p (TREE_OPERAND (op0, 0))));
2787     }
2788
2789   return CONSTANT_CLASS_P (op) || decl_address_invariant_p (op);
2790 }
2791
2792 /* Return true if T is a gimple invariant address at IPA level
2793    (so addresses of variables on stack are not allowed).  */
2794
2795 bool
2796 is_gimple_ip_invariant_address (const_tree t)
2797 {
2798   const_tree op;
2799
2800   if (TREE_CODE (t) != ADDR_EXPR)
2801     return false;
2802
2803   op = strip_invariant_refs (TREE_OPERAND (t, 0));
2804
2805   return op && (CONSTANT_CLASS_P (op) || decl_address_ip_invariant_p (op));
2806 }
2807
2808 /* Return true if T is a GIMPLE minimal invariant.  It's a restricted
2809    form of function invariant.  */
2810
2811 bool
2812 is_gimple_min_invariant (const_tree t)
2813 {
2814   if (TREE_CODE (t) == ADDR_EXPR)
2815     return is_gimple_invariant_address (t);
2816
2817   return is_gimple_constant (t);
2818 }
2819
2820 /* Return true if T is a GIMPLE interprocedural invariant.  It's a restricted
2821    form of gimple minimal invariant.  */
2822
2823 bool
2824 is_gimple_ip_invariant (const_tree t)
2825 {
2826   if (TREE_CODE (t) == ADDR_EXPR)
2827     return is_gimple_ip_invariant_address (t);
2828
2829   return is_gimple_constant (t);
2830 }
2831
2832 /* Return true if T looks like a valid GIMPLE statement.  */
2833
2834 bool
2835 is_gimple_stmt (tree t)
2836 {
2837   const enum tree_code code = TREE_CODE (t);
2838
2839   switch (code)
2840     {
2841     case NOP_EXPR:
2842       /* The only valid NOP_EXPR is the empty statement.  */
2843       return IS_EMPTY_STMT (t);
2844
2845     case BIND_EXPR:
2846     case COND_EXPR:
2847       /* These are only valid if they're void.  */
2848       return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
2849
2850     case SWITCH_EXPR:
2851     case GOTO_EXPR:
2852     case RETURN_EXPR:
2853     case LABEL_EXPR:
2854     case CASE_LABEL_EXPR:
2855     case TRY_CATCH_EXPR:
2856     case TRY_FINALLY_EXPR:
2857     case EH_FILTER_EXPR:
2858     case CATCH_EXPR:
2859     case ASM_EXPR:
2860     case STATEMENT_LIST:
2861     case OMP_PARALLEL:
2862     case OMP_FOR:
2863     case OMP_SECTIONS:
2864     case OMP_SECTION:
2865     case OMP_SINGLE:
2866     case OMP_MASTER:
2867     case OMP_ORDERED:
2868     case OMP_CRITICAL:
2869     case OMP_TASK:
2870       /* These are always void.  */
2871       return true;
2872
2873     case CALL_EXPR:
2874     case MODIFY_EXPR:
2875     case PREDICT_EXPR:
2876       /* These are valid regardless of their type.  */
2877       return true;
2878
2879     default:
2880       return false;
2881     }
2882 }
2883
2884 /* Return true if T is a variable.  */
2885
2886 bool
2887 is_gimple_variable (tree t)
2888 {
2889   return (TREE_CODE (t) == VAR_DECL
2890           || TREE_CODE (t) == PARM_DECL
2891           || TREE_CODE (t) == RESULT_DECL
2892           || TREE_CODE (t) == SSA_NAME);
2893 }
2894
2895 /*  Return true if T is a GIMPLE identifier (something with an address).  */
2896
2897 bool
2898 is_gimple_id (tree t)
2899 {
2900   return (is_gimple_variable (t)
2901           || TREE_CODE (t) == FUNCTION_DECL
2902           || TREE_CODE (t) == LABEL_DECL
2903           || TREE_CODE (t) == CONST_DECL
2904           /* Allow string constants, since they are addressable.  */
2905           || TREE_CODE (t) == STRING_CST);
2906 }
2907
2908 /* Return true if TYPE is a suitable type for a scalar register variable.  */
2909
2910 bool
2911 is_gimple_reg_type (tree type)
2912 {
2913   return !AGGREGATE_TYPE_P (type);
2914 }
2915
2916 /* Return true if T is a non-aggregate register variable.  */
2917
2918 bool
2919 is_gimple_reg (tree t)
2920 {
2921   if (TREE_CODE (t) == SSA_NAME)
2922     t = SSA_NAME_VAR (t);
2923
2924   if (!is_gimple_variable (t))
2925     return false;
2926
2927   if (!is_gimple_reg_type (TREE_TYPE (t)))
2928     return false;
2929
2930   /* A volatile decl is not acceptable because we can't reuse it as
2931      needed.  We need to copy it into a temp first.  */
2932   if (TREE_THIS_VOLATILE (t))
2933     return false;
2934
2935   /* We define "registers" as things that can be renamed as needed,
2936      which with our infrastructure does not apply to memory.  */
2937   if (needs_to_live_in_memory (t))
2938     return false;
2939
2940   /* Hard register variables are an interesting case.  For those that
2941      are call-clobbered, we don't know where all the calls are, since
2942      we don't (want to) take into account which operations will turn
2943      into libcalls at the rtl level.  For those that are call-saved,
2944      we don't currently model the fact that calls may in fact change
2945      global hard registers, nor do we examine ASM_CLOBBERS at the tree
2946      level, and so miss variable changes that might imply.  All around,
2947      it seems safest to not do too much optimization with these at the
2948      tree level at all.  We'll have to rely on the rtl optimizers to
2949      clean this up, as there we've got all the appropriate bits exposed.  */
2950   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
2951     return false;
2952
2953   /* Complex and vector values must have been put into SSA-like form.
2954      That is, no assignments to the individual components.  */
2955   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
2956       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2957     return DECL_GIMPLE_REG_P (t);
2958
2959   return true;
2960 }
2961
2962
2963 /* Return true if T is a GIMPLE variable whose address is not needed.  */
2964
2965 bool
2966 is_gimple_non_addressable (tree t)
2967 {
2968   if (TREE_CODE (t) == SSA_NAME)
2969     t = SSA_NAME_VAR (t);
2970
2971   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
2972 }
2973
2974 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
2975
2976 bool
2977 is_gimple_val (tree t)
2978 {
2979   /* Make loads from volatiles and memory vars explicit.  */
2980   if (is_gimple_variable (t)
2981       && is_gimple_reg_type (TREE_TYPE (t))
2982       && !is_gimple_reg (t))
2983     return false;
2984
2985   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
2986 }
2987
2988 /* Similarly, but accept hard registers as inputs to asm statements.  */
2989
2990 bool
2991 is_gimple_asm_val (tree t)
2992 {
2993   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
2994     return true;
2995
2996   return is_gimple_val (t);
2997 }
2998
2999 /* Return true if T is a GIMPLE minimal lvalue.  */
3000
3001 bool
3002 is_gimple_min_lval (tree t)
3003 {
3004   if (!(t = CONST_CAST_TREE (strip_invariant_refs (t))))
3005     return false;
3006   return (is_gimple_id (t) || TREE_CODE (t) == MEM_REF);
3007 }
3008
3009 /* Return true if T is a valid function operand of a CALL_EXPR.  */
3010
3011 bool
3012 is_gimple_call_addr (tree t)
3013 {
3014   return (TREE_CODE (t) == OBJ_TYPE_REF || is_gimple_val (t));
3015 }
3016
3017 /* Return true if T is a valid address operand of a MEM_REF.  */
3018
3019 bool
3020 is_gimple_mem_ref_addr (tree t)
3021 {
3022   return (is_gimple_reg (t)
3023           || TREE_CODE (t) == INTEGER_CST
3024           || (TREE_CODE (t) == ADDR_EXPR
3025               && (CONSTANT_CLASS_P (TREE_OPERAND (t, 0))
3026                   || decl_address_invariant_p (TREE_OPERAND (t, 0)))));
3027 }
3028
3029 /* If T makes a function call, return the corresponding CALL_EXPR operand.
3030    Otherwise, return NULL_TREE.  */
3031
3032 tree
3033 get_call_expr_in (tree t)
3034 {
3035   if (TREE_CODE (t) == MODIFY_EXPR)
3036     t = TREE_OPERAND (t, 1);
3037   if (TREE_CODE (t) == WITH_SIZE_EXPR)
3038     t = TREE_OPERAND (t, 0);
3039   if (TREE_CODE (t) == CALL_EXPR)
3040     return t;
3041   return NULL_TREE;
3042 }
3043
3044
3045 /* Given a memory reference expression T, return its base address.
3046    The base address of a memory reference expression is the main
3047    object being referenced.  For instance, the base address for
3048    'array[i].fld[j]' is 'array'.  You can think of this as stripping
3049    away the offset part from a memory address.
3050
3051    This function calls handled_component_p to strip away all the inner
3052    parts of the memory reference until it reaches the base object.  */
3053
3054 tree
3055 get_base_address (tree t)
3056 {
3057   while (handled_component_p (t))
3058     t = TREE_OPERAND (t, 0);
3059
3060   if ((TREE_CODE (t) == MEM_REF
3061        || TREE_CODE (t) == TARGET_MEM_REF)
3062       && TREE_CODE (TREE_OPERAND (t, 0)) == ADDR_EXPR)
3063     t = TREE_OPERAND (TREE_OPERAND (t, 0), 0);
3064
3065   if (TREE_CODE (t) == SSA_NAME
3066       || DECL_P (t)
3067       || TREE_CODE (t) == STRING_CST
3068       || TREE_CODE (t) == CONSTRUCTOR
3069       || INDIRECT_REF_P (t)
3070       || TREE_CODE (t) == MEM_REF
3071       || TREE_CODE (t) == TARGET_MEM_REF)
3072     return t;
3073   else
3074     return NULL_TREE;
3075 }
3076
3077 void
3078 recalculate_side_effects (tree t)
3079 {
3080   enum tree_code code = TREE_CODE (t);
3081   int len = TREE_OPERAND_LENGTH (t);
3082   int i;
3083
3084   switch (TREE_CODE_CLASS (code))
3085     {
3086     case tcc_expression:
3087       switch (code)
3088         {
3089         case INIT_EXPR:
3090         case MODIFY_EXPR:
3091         case VA_ARG_EXPR:
3092         case PREDECREMENT_EXPR:
3093         case PREINCREMENT_EXPR:
3094         case POSTDECREMENT_EXPR:
3095         case POSTINCREMENT_EXPR:
3096           /* All of these have side-effects, no matter what their
3097              operands are.  */
3098           return;
3099
3100         default:
3101           break;
3102         }
3103       /* Fall through.  */
3104
3105     case tcc_comparison:  /* a comparison expression */
3106     case tcc_unary:       /* a unary arithmetic expression */
3107     case tcc_binary:      /* a binary arithmetic expression */
3108     case tcc_reference:   /* a reference */
3109     case tcc_vl_exp:        /* a function call */
3110       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
3111       for (i = 0; i < len; ++i)
3112         {
3113           tree op = TREE_OPERAND (t, i);
3114           if (op && TREE_SIDE_EFFECTS (op))
3115             TREE_SIDE_EFFECTS (t) = 1;
3116         }
3117       break;
3118
3119     case tcc_constant:
3120       /* No side-effects.  */
3121       return;
3122
3123     default:
3124       gcc_unreachable ();
3125    }
3126 }
3127
3128 /* Canonicalize a tree T for use in a COND_EXPR as conditional.  Returns
3129    a canonicalized tree that is valid for a COND_EXPR or NULL_TREE, if
3130    we failed to create one.  */
3131
3132 tree
3133 canonicalize_cond_expr_cond (tree t)
3134 {
3135   /* Strip conversions around boolean operations.  */
3136   if (CONVERT_EXPR_P (t)
3137       && truth_value_p (TREE_CODE (TREE_OPERAND (t, 0))))
3138     t = TREE_OPERAND (t, 0);
3139
3140   /* For (bool)x use x != 0.  */
3141   if (CONVERT_EXPR_P (t)
3142       && TREE_CODE (TREE_TYPE (t)) == BOOLEAN_TYPE)
3143     {
3144       tree top0 = TREE_OPERAND (t, 0);
3145       t = build2 (NE_EXPR, TREE_TYPE (t),
3146                   top0, build_int_cst (TREE_TYPE (top0), 0));
3147     }
3148   /* For !x use x == 0.  */
3149   else if (TREE_CODE (t) == TRUTH_NOT_EXPR)
3150     {
3151       tree top0 = TREE_OPERAND (t, 0);
3152       t = build2 (EQ_EXPR, TREE_TYPE (t),
3153                   top0, build_int_cst (TREE_TYPE (top0), 0));
3154     }
3155   /* For cmp ? 1 : 0 use cmp.  */
3156   else if (TREE_CODE (t) == COND_EXPR
3157            && COMPARISON_CLASS_P (TREE_OPERAND (t, 0))
3158            && integer_onep (TREE_OPERAND (t, 1))
3159            && integer_zerop (TREE_OPERAND (t, 2)))
3160     {
3161       tree top0 = TREE_OPERAND (t, 0);
3162       t = build2 (TREE_CODE (top0), TREE_TYPE (t),
3163                   TREE_OPERAND (top0, 0), TREE_OPERAND (top0, 1));
3164     }
3165
3166   if (is_gimple_condexpr (t))
3167     return t;
3168
3169   return NULL_TREE;
3170 }
3171
3172 /* Build a GIMPLE_CALL identical to STMT but skipping the arguments in
3173    the positions marked by the set ARGS_TO_SKIP.  */
3174
3175 gimple
3176 gimple_call_copy_skip_args (gimple stmt, bitmap args_to_skip)
3177 {
3178   int i;
3179   int nargs = gimple_call_num_args (stmt);
3180   VEC(tree, heap) *vargs = VEC_alloc (tree, heap, nargs);
3181   gimple new_stmt;
3182
3183   for (i = 0; i < nargs; i++)
3184     if (!bitmap_bit_p (args_to_skip, i))
3185       VEC_quick_push (tree, vargs, gimple_call_arg (stmt, i));
3186
3187   if (gimple_call_internal_p (stmt))
3188     new_stmt = gimple_build_call_internal_vec (gimple_call_internal_fn (stmt),
3189                                                vargs);
3190   else
3191     new_stmt = gimple_build_call_vec (gimple_call_fn (stmt), vargs);
3192   VEC_free (tree, heap, vargs);
3193   if (gimple_call_lhs (stmt))
3194     gimple_call_set_lhs (new_stmt, gimple_call_lhs (stmt));
3195
3196   gimple_set_vuse (new_stmt, gimple_vuse (stmt));
3197   gimple_set_vdef (new_stmt, gimple_vdef (stmt));
3198
3199   gimple_set_block (new_stmt, gimple_block (stmt));
3200   if (gimple_has_location (stmt))
3201     gimple_set_location (new_stmt, gimple_location (stmt));
3202   gimple_call_copy_flags (new_stmt, stmt);
3203   gimple_call_set_chain (new_stmt, gimple_call_chain (stmt));
3204
3205   gimple_set_modified (new_stmt, true);
3206
3207   return new_stmt;
3208 }
3209
3210
3211 static hashval_t gimple_type_hash_1 (const void *, enum gtc_mode);
3212
3213 /* Structure used to maintain a cache of some type pairs compared by
3214    gimple_types_compatible_p when comparing aggregate types.  There are
3215    three possible values for SAME_P:
3216
3217         -2: The pair (T1, T2) has just been inserted in the table.
3218          0: T1 and T2 are different types.
3219          1: T1 and T2 are the same type.
3220
3221    The two elements in the SAME_P array are indexed by the comparison
3222    mode gtc_mode.  */
3223
3224 struct type_pair_d
3225 {
3226   unsigned int uid1;
3227   unsigned int uid2;
3228   signed char same_p[2];
3229 };
3230 typedef struct type_pair_d *type_pair_t;
3231
3232 DEF_VEC_P(type_pair_t);
3233 DEF_VEC_ALLOC_P(type_pair_t,heap);
3234
3235 /* Return a hash value for the type pair pointed-to by P.  */
3236
3237 static hashval_t
3238 type_pair_hash (const void *p)
3239 {
3240   const struct type_pair_d *pair = (const struct type_pair_d *) p;
3241   hashval_t val1 = pair->uid1;
3242   hashval_t val2 = pair->uid2;
3243   return (iterative_hash_hashval_t (val2, val1)
3244           ^ iterative_hash_hashval_t (val1, val2));
3245 }
3246
3247 /* Compare two type pairs pointed-to by P1 and P2.  */
3248
3249 static int
3250 type_pair_eq (const void *p1, const void *p2)
3251 {
3252   const struct type_pair_d *pair1 = (const struct type_pair_d *) p1;
3253   const struct type_pair_d *pair2 = (const struct type_pair_d *) p2;
3254   return ((pair1->uid1 == pair2->uid1 && pair1->uid2 == pair2->uid2)
3255           || (pair1->uid1 == pair2->uid2 && pair1->uid2 == pair2->uid1));
3256 }
3257
3258 /* Lookup the pair of types T1 and T2 in *VISITED_P.  Insert a new
3259    entry if none existed.  */
3260
3261 static type_pair_t
3262 lookup_type_pair (tree t1, tree t2, htab_t *visited_p, struct obstack *ob_p)
3263 {
3264   struct type_pair_d pair;
3265   type_pair_t p;
3266   void **slot;
3267
3268   if (*visited_p == NULL)
3269     {
3270       *visited_p = htab_create (251, type_pair_hash, type_pair_eq, NULL);
3271       gcc_obstack_init (ob_p);
3272     }
3273
3274   pair.uid1 = TYPE_UID (t1);
3275   pair.uid2 = TYPE_UID (t2);
3276   slot = htab_find_slot (*visited_p, &pair, INSERT);
3277
3278   if (*slot)
3279     p = *((type_pair_t *) slot);
3280   else
3281     {
3282       p = XOBNEW (ob_p, struct type_pair_d);
3283       p->uid1 = TYPE_UID (t1);
3284       p->uid2 = TYPE_UID (t2);
3285       p->same_p[0] = -2;
3286       p->same_p[1] = -2;
3287       *slot = (void *) p;
3288     }
3289
3290   return p;
3291 }
3292
3293 /* Per pointer state for the SCC finding.  The on_sccstack flag
3294    is not strictly required, it is true when there is no hash value
3295    recorded for the type and false otherwise.  But querying that
3296    is slower.  */
3297
3298 struct sccs
3299 {
3300   unsigned int dfsnum;
3301   unsigned int low;
3302   bool on_sccstack;
3303   union {
3304     hashval_t hash;
3305     signed char same_p;
3306   } u;
3307 };
3308
3309 static unsigned int next_dfs_num;
3310 static unsigned int gtc_next_dfs_num;
3311
3312
3313 /* GIMPLE type merging cache.  A direct-mapped cache based on TYPE_UID.  */
3314
3315 typedef struct GTY(()) gimple_type_leader_entry_s {
3316   tree type;
3317   tree leader;
3318 } gimple_type_leader_entry;
3319
3320 #define GIMPLE_TYPE_LEADER_SIZE 16381
3321 static GTY((deletable, length("GIMPLE_TYPE_LEADER_SIZE")))
3322   gimple_type_leader_entry *gimple_type_leader;
3323
3324 /* Lookup an existing leader for T and return it or NULL_TREE, if
3325    there is none in the cache.  */
3326
3327 static tree
3328 gimple_lookup_type_leader (tree t)
3329 {
3330   gimple_type_leader_entry *leader;
3331
3332   if (!gimple_type_leader)
3333     return NULL_TREE;
3334
3335   leader = &gimple_type_leader[TYPE_UID (t) % GIMPLE_TYPE_LEADER_SIZE];
3336   if (leader->type != t)
3337     return NULL_TREE;
3338
3339   return leader->leader;
3340 }
3341
3342 /* Return true if T1 and T2 have the same name.  If FOR_COMPLETION_P is
3343    true then if any type has no name return false, otherwise return
3344    true if both types have no names.  */
3345
3346 static bool
3347 compare_type_names_p (tree t1, tree t2, bool for_completion_p)
3348 {
3349   tree name1 = TYPE_NAME (t1);
3350   tree name2 = TYPE_NAME (t2);
3351
3352   /* Consider anonymous types all unique for completion.  */
3353   if (for_completion_p
3354       && (!name1 || !name2))
3355     return false;
3356
3357   if (name1 && TREE_CODE (name1) == TYPE_DECL)
3358     {
3359       name1 = DECL_NAME (name1);
3360       if (for_completion_p
3361           && !name1)
3362         return false;
3363     }
3364   gcc_assert (!name1 || TREE_CODE (name1) == IDENTIFIER_NODE);
3365
3366   if (name2 && TREE_CODE (name2) == TYPE_DECL)
3367     {
3368       name2 = DECL_NAME (name2);
3369       if (for_completion_p
3370           && !name2)
3371         return false;
3372     }
3373   gcc_assert (!name2 || TREE_CODE (name2) == IDENTIFIER_NODE);
3374
3375   /* Identifiers can be compared with pointer equality rather
3376      than a string comparison.  */
3377   if (name1 == name2)
3378     return true;
3379
3380   return false;
3381 }
3382
3383 /* Return true if the field decls F1 and F2 are at the same offset.
3384
3385    This is intended to be used on GIMPLE types only.  */
3386
3387 bool
3388 gimple_compare_field_offset (tree f1, tree f2)
3389 {
3390   if (DECL_OFFSET_ALIGN (f1) == DECL_OFFSET_ALIGN (f2))
3391     {
3392       tree offset1 = DECL_FIELD_OFFSET (f1);
3393       tree offset2 = DECL_FIELD_OFFSET (f2);
3394       return ((offset1 == offset2
3395                /* Once gimplification is done, self-referential offsets are
3396                   instantiated as operand #2 of the COMPONENT_REF built for
3397                   each access and reset.  Therefore, they are not relevant
3398                   anymore and fields are interchangeable provided that they
3399                   represent the same access.  */
3400                || (TREE_CODE (offset1) == PLACEHOLDER_EXPR
3401                    && TREE_CODE (offset2) == PLACEHOLDER_EXPR
3402                    && (DECL_SIZE (f1) == DECL_SIZE (f2)
3403                        || (TREE_CODE (DECL_SIZE (f1)) == PLACEHOLDER_EXPR
3404                            && TREE_CODE (DECL_SIZE (f2)) == PLACEHOLDER_EXPR)
3405                        || operand_equal_p (DECL_SIZE (f1), DECL_SIZE (f2), 0))
3406                    && DECL_ALIGN (f1) == DECL_ALIGN (f2))
3407                || operand_equal_p (offset1, offset2, 0))
3408               && tree_int_cst_equal (DECL_FIELD_BIT_OFFSET (f1),
3409                                      DECL_FIELD_BIT_OFFSET (f2)));
3410     }
3411
3412   /* Fortran and C do not always agree on what DECL_OFFSET_ALIGN
3413      should be, so handle differing ones specially by decomposing
3414      the offset into a byte and bit offset manually.  */
3415   if (host_integerp (DECL_FIELD_OFFSET (f1), 0)
3416       && host_integerp (DECL_FIELD_OFFSET (f2), 0))
3417     {
3418       unsigned HOST_WIDE_INT byte_offset1, byte_offset2;
3419       unsigned HOST_WIDE_INT bit_offset1, bit_offset2;
3420       bit_offset1 = TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (f1));
3421       byte_offset1 = (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (f1))
3422                       + bit_offset1 / BITS_PER_UNIT);
3423       bit_offset2 = TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (f2));
3424       byte_offset2 = (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (f2))
3425                       + bit_offset2 / BITS_PER_UNIT);
3426       if (byte_offset1 != byte_offset2)
3427         return false;
3428       return bit_offset1 % BITS_PER_UNIT == bit_offset2 % BITS_PER_UNIT;
3429     }
3430
3431   return false;
3432 }
3433
3434 /* If the type T1 and the type T2 are a complete and an incomplete
3435    variant of the same type return true.  */
3436
3437 static bool
3438 gimple_compatible_complete_and_incomplete_subtype_p (tree t1, tree t2)
3439 {
3440   /* If one pointer points to an incomplete type variant of
3441      the other pointed-to type they are the same.  */
3442   if (TREE_CODE (t1) == TREE_CODE (t2)
3443       && RECORD_OR_UNION_TYPE_P (t1)
3444       && (!COMPLETE_TYPE_P (t1)
3445           || !COMPLETE_TYPE_P (t2))
3446       && TYPE_QUALS (t1) == TYPE_QUALS (t2)
3447       && compare_type_names_p (TYPE_MAIN_VARIANT (t1),
3448                                TYPE_MAIN_VARIANT (t2), true))
3449     return true;
3450   return false;
3451 }
3452
3453 static bool
3454 gimple_types_compatible_p_1 (tree, tree, enum gtc_mode, type_pair_t,
3455                              VEC(type_pair_t, heap) **,
3456                              struct pointer_map_t *, struct obstack *);
3457
3458 /* DFS visit the edge from the callers type pair with state *STATE to
3459    the pair T1, T2 while operating in FOR_MERGING_P mode.
3460    Update the merging status if it is not part of the SCC containing the
3461    callers pair and return it.
3462    SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done.  */
3463
3464 static bool
3465 gtc_visit (tree t1, tree t2, enum gtc_mode mode,
3466            struct sccs *state,
3467            VEC(type_pair_t, heap) **sccstack,
3468            struct pointer_map_t *sccstate,
3469            struct obstack *sccstate_obstack)
3470 {
3471   struct sccs *cstate = NULL;
3472   type_pair_t p;
3473   void **slot;
3474
3475   /* Check first for the obvious case of pointer identity.  */
3476   if (t1 == t2)
3477     return true;
3478
3479   /* Check that we have two types to compare.  */
3480   if (t1 == NULL_TREE || t2 == NULL_TREE)
3481     return false;
3482
3483   /* If the types have been previously registered and found equal
3484      they still are.  */
3485   if (mode == GTC_MERGE)
3486     {
3487       tree leader1 = gimple_lookup_type_leader (t1);
3488       tree leader2 = gimple_lookup_type_leader (t2);
3489       if (leader1 == t2
3490           || t1 == leader2
3491           || (leader1 && leader1 == leader2))
3492         return true;
3493     }
3494   else if (mode == GTC_DIAG)
3495     {
3496       if (TYPE_CANONICAL (t1)
3497           && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2))
3498         return true;
3499     }
3500
3501   /* Can't be the same type if the types don't have the same code.  */
3502   if (TREE_CODE (t1) != TREE_CODE (t2))
3503     return false;
3504
3505   /* Can't be the same type if they have different CV qualifiers.  */
3506   if (TYPE_QUALS (t1) != TYPE_QUALS (t2))
3507     return false;
3508
3509   /* Void types are always the same.  */
3510   if (TREE_CODE (t1) == VOID_TYPE)
3511     return true;
3512
3513   /* Do some simple checks before doing three hashtable queries.  */
3514   if (INTEGRAL_TYPE_P (t1)
3515       || SCALAR_FLOAT_TYPE_P (t1)
3516       || FIXED_POINT_TYPE_P (t1)
3517       || TREE_CODE (t1) == VECTOR_TYPE
3518       || TREE_CODE (t1) == COMPLEX_TYPE
3519       || TREE_CODE (t1) == OFFSET_TYPE)
3520     {
3521       /* Can't be the same type if they have different alignment,
3522          sign, precision or mode.  */
3523       if (TYPE_ALIGN (t1) != TYPE_ALIGN (t2)
3524           || TYPE_PRECISION (t1) != TYPE_PRECISION (t2)
3525           || TYPE_MODE (t1) != TYPE_MODE (t2)
3526           || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
3527         return false;
3528
3529       if (TREE_CODE (t1) == INTEGER_TYPE
3530           && (TYPE_IS_SIZETYPE (t1) != TYPE_IS_SIZETYPE (t2)
3531               || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)))
3532         return false;
3533
3534       /* That's all we need to check for float and fixed-point types.  */
3535       if (SCALAR_FLOAT_TYPE_P (t1)
3536           || FIXED_POINT_TYPE_P (t1))
3537         return true;
3538
3539       /* For integral types fall thru to more complex checks.  */
3540     }
3541
3542   else if (AGGREGATE_TYPE_P (t1) || POINTER_TYPE_P (t1))
3543     {
3544       /* Can't be the same type if they have different alignment or mode.  */
3545       if (TYPE_ALIGN (t1) != TYPE_ALIGN (t2)
3546           || TYPE_MODE (t1) != TYPE_MODE (t2))
3547         return false;
3548     }
3549
3550   /* If the hash values of t1 and t2 are different the types can't
3551      possibly be the same.  This helps keeping the type-pair hashtable
3552      small, only tracking comparisons for hash collisions.  */
3553   if (gimple_type_hash_1 (t1, mode) != gimple_type_hash_1 (t2, mode))
3554     return false;
3555
3556   /* Allocate a new cache entry for this comparison.  */
3557   p = lookup_type_pair (t1, t2, &gtc_visited, &gtc_ob);
3558   if (p->same_p[mode] == 0 || p->same_p[mode] == 1)
3559     {
3560       /* We have already decided whether T1 and T2 are the
3561          same, return the cached result.  */
3562       return p->same_p[mode] == 1;
3563     }
3564
3565   if ((slot = pointer_map_contains (sccstate, p)) != NULL)
3566     cstate = (struct sccs *)*slot;
3567   /* Not yet visited.  DFS recurse.  */
3568   if (!cstate)
3569     {
3570       gimple_types_compatible_p_1 (t1, t2, mode, p,
3571                                    sccstack, sccstate, sccstate_obstack);
3572       cstate = (struct sccs *)* pointer_map_contains (sccstate, p);
3573       state->low = MIN (state->low, cstate->low);
3574     }
3575   /* If the type is still on the SCC stack adjust the parents low.  */
3576   if (cstate->dfsnum < state->dfsnum
3577       && cstate->on_sccstack)
3578     state->low = MIN (cstate->dfsnum, state->low);
3579
3580   /* Return the current lattice value.  We start with an equality
3581      assumption so types part of a SCC will be optimistically
3582      treated equal unless proven otherwise.  */
3583   return cstate->u.same_p;
3584 }
3585
3586 /* Worker for gimple_types_compatible.
3587    SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done.  */
3588
3589 static bool
3590 gimple_types_compatible_p_1 (tree t1, tree t2, enum gtc_mode mode,
3591                              type_pair_t p,
3592                              VEC(type_pair_t, heap) **sccstack,
3593                              struct pointer_map_t *sccstate,
3594                              struct obstack *sccstate_obstack)
3595 {
3596   struct sccs *state;
3597
3598   gcc_assert (p->same_p[mode] == -2);
3599
3600   state = XOBNEW (sccstate_obstack, struct sccs);
3601   *pointer_map_insert (sccstate, p) = state;
3602
3603   VEC_safe_push (type_pair_t, heap, *sccstack, p);
3604   state->dfsnum = gtc_next_dfs_num++;
3605   state->low = state->dfsnum;
3606   state->on_sccstack = true;
3607   /* Start with an equality assumption.  As we DFS recurse into child
3608      SCCs this assumption may get revisited.  */
3609   state->u.same_p = 1;
3610
3611   /* If their attributes are not the same they can't be the same type.  */
3612   if (!attribute_list_equal (TYPE_ATTRIBUTES (t1), TYPE_ATTRIBUTES (t2)))
3613     goto different_types;
3614
3615   /* Do type-specific comparisons.  */
3616   switch (TREE_CODE (t1))
3617     {
3618     case VECTOR_TYPE:
3619     case COMPLEX_TYPE:
3620       if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2), mode,
3621                       state, sccstack, sccstate, sccstate_obstack))
3622         goto different_types;
3623       goto same_types;
3624
3625     case ARRAY_TYPE:
3626       /* Array types are the same if the element types are the same and
3627          the number of elements are the same.  */
3628       if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2), mode,
3629                       state, sccstack, sccstate, sccstate_obstack)
3630           || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)
3631           || TYPE_NONALIASED_COMPONENT (t1) != TYPE_NONALIASED_COMPONENT (t2))
3632         goto different_types;
3633       else
3634         {
3635           tree i1 = TYPE_DOMAIN (t1);
3636           tree i2 = TYPE_DOMAIN (t2);
3637
3638           /* For an incomplete external array, the type domain can be
3639              NULL_TREE.  Check this condition also.  */
3640           if (i1 == NULL_TREE && i2 == NULL_TREE)
3641             goto same_types;
3642           else if (i1 == NULL_TREE || i2 == NULL_TREE)
3643             goto different_types;
3644           /* If for a complete array type the possibly gimplified sizes
3645              are different the types are different.  */
3646           else if (((TYPE_SIZE (i1) != NULL) ^ (TYPE_SIZE (i2) != NULL))
3647                    || (TYPE_SIZE (i1)
3648                        && TYPE_SIZE (i2)
3649                        && !operand_equal_p (TYPE_SIZE (i1), TYPE_SIZE (i2), 0)))
3650             goto different_types;
3651           else
3652             {
3653               tree min1 = TYPE_MIN_VALUE (i1);
3654               tree min2 = TYPE_MIN_VALUE (i2);
3655               tree max1 = TYPE_MAX_VALUE (i1);
3656               tree max2 = TYPE_MAX_VALUE (i2);
3657
3658               /* The minimum/maximum values have to be the same.  */
3659               if ((min1 == min2
3660                    || (min1 && min2
3661                        && ((TREE_CODE (min1) == PLACEHOLDER_EXPR
3662                             && TREE_CODE (min2) == PLACEHOLDER_EXPR)
3663                            || operand_equal_p (min1, min2, 0))))
3664                   && (max1 == max2
3665                       || (max1 && max2
3666                           && ((TREE_CODE (max1) == PLACEHOLDER_EXPR
3667                                && TREE_CODE (max2) == PLACEHOLDER_EXPR)
3668                               || operand_equal_p (max1, max2, 0)))))
3669                 goto same_types;
3670               else
3671                 goto different_types;
3672             }
3673         }
3674
3675     case METHOD_TYPE:
3676       /* Method types should belong to the same class.  */
3677       if (!gtc_visit (TYPE_METHOD_BASETYPE (t1), TYPE_METHOD_BASETYPE (t2),
3678                       mode, state, sccstack, sccstate, sccstate_obstack))
3679         goto different_types;
3680
3681       /* Fallthru  */
3682
3683     case FUNCTION_TYPE:
3684       /* Function types are the same if the return type and arguments types
3685          are the same.  */
3686       if ((mode != GTC_DIAG
3687            || !gimple_compatible_complete_and_incomplete_subtype_p
3688                  (TREE_TYPE (t1), TREE_TYPE (t2)))
3689           && !gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2), mode,
3690                          state, sccstack, sccstate, sccstate_obstack))
3691         goto different_types;
3692
3693       if (!comp_type_attributes (t1, t2))
3694         goto different_types;
3695
3696       if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2))
3697         goto same_types;
3698       else
3699         {
3700           tree parms1, parms2;
3701
3702           for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
3703                parms1 && parms2;
3704                parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
3705             {
3706               if ((mode == GTC_MERGE
3707                    || !gimple_compatible_complete_and_incomplete_subtype_p
3708                          (TREE_VALUE (parms1), TREE_VALUE (parms2)))
3709                   && !gtc_visit (TREE_VALUE (parms1), TREE_VALUE (parms2), mode,
3710                                  state, sccstack, sccstate, sccstate_obstack))
3711                 goto different_types;
3712             }
3713
3714           if (parms1 || parms2)
3715             goto different_types;
3716
3717           goto same_types;
3718         }
3719
3720     case OFFSET_TYPE:
3721       {
3722         if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2), mode,
3723                         state, sccstack, sccstate, sccstate_obstack)
3724             || !gtc_visit (TYPE_OFFSET_BASETYPE (t1),
3725                            TYPE_OFFSET_BASETYPE (t2), mode,
3726                            state, sccstack, sccstate, sccstate_obstack))
3727           goto different_types;
3728
3729         goto same_types;
3730       }
3731
3732     case POINTER_TYPE:
3733     case REFERENCE_TYPE:
3734       {
3735         /* If the two pointers have different ref-all attributes,
3736            they can't be the same type.  */
3737         if (TYPE_REF_CAN_ALIAS_ALL (t1) != TYPE_REF_CAN_ALIAS_ALL (t2))
3738           goto different_types;
3739
3740         /* If one pointer points to an incomplete type variant of
3741            the other pointed-to type they are the same.  */
3742         if (mode == GTC_DIAG
3743             && gimple_compatible_complete_and_incomplete_subtype_p
3744                  (TREE_TYPE (t1), TREE_TYPE (t2)))
3745           goto same_types;
3746
3747         /* Otherwise, pointer and reference types are the same if the
3748            pointed-to types are the same.  */
3749         if (gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2), mode,
3750                        state, sccstack, sccstate, sccstate_obstack))
3751           goto same_types;
3752
3753         goto different_types;
3754       }
3755
3756     case NULLPTR_TYPE:
3757       /* There is only one decltype(nullptr).  */
3758       goto same_types;
3759
3760     case INTEGER_TYPE:
3761     case BOOLEAN_TYPE:
3762       {
3763         tree min1 = TYPE_MIN_VALUE (t1);
3764         tree max1 = TYPE_MAX_VALUE (t1);
3765         tree min2 = TYPE_MIN_VALUE (t2);
3766         tree max2 = TYPE_MAX_VALUE (t2);
3767         bool min_equal_p = false;
3768         bool max_equal_p = false;
3769
3770         /* If either type has a minimum value, the other type must
3771            have the same.  */
3772         if (min1 == NULL_TREE && min2 == NULL_TREE)
3773           min_equal_p = true;
3774         else if (min1 && min2 && operand_equal_p (min1, min2, 0))
3775           min_equal_p = true;
3776
3777         /* Likewise, if either type has a maximum value, the other
3778            type must have the same.  */
3779         if (max1 == NULL_TREE && max2 == NULL_TREE)
3780           max_equal_p = true;
3781         else if (max1 && max2 && operand_equal_p (max1, max2, 0))
3782           max_equal_p = true;
3783
3784         if (!min_equal_p || !max_equal_p)
3785           goto different_types;
3786
3787         goto same_types;
3788       }
3789
3790     case ENUMERAL_TYPE:
3791       {
3792         /* FIXME lto, we cannot check bounds on enumeral types because
3793            different front ends will produce different values.
3794            In C, enumeral types are integers, while in C++ each element
3795            will have its own symbolic value.  We should decide how enums
3796            are to be represented in GIMPLE and have each front end lower
3797            to that.  */
3798         tree v1, v2;
3799
3800         /* For enumeral types, all the values must be the same.  */
3801         if (TYPE_VALUES (t1) == TYPE_VALUES (t2))
3802           goto same_types;
3803
3804         for (v1 = TYPE_VALUES (t1), v2 = TYPE_VALUES (t2);
3805              v1 && v2;
3806              v1 = TREE_CHAIN (v1), v2 = TREE_CHAIN (v2))
3807           {
3808             tree c1 = TREE_VALUE (v1);
3809             tree c2 = TREE_VALUE (v2);
3810
3811             if (TREE_CODE (c1) == CONST_DECL)
3812               c1 = DECL_INITIAL (c1);
3813
3814             if (TREE_CODE (c2) == CONST_DECL)
3815               c2 = DECL_INITIAL (c2);
3816
3817             if (tree_int_cst_equal (c1, c2) != 1)
3818               goto different_types;
3819
3820             if (mode == GTC_MERGE && TREE_PURPOSE (v1) != TREE_PURPOSE (v2))
3821               goto different_types;
3822           }
3823
3824         /* If one enumeration has more values than the other, they
3825            are not the same.  */
3826         if (v1 || v2)
3827           goto different_types;
3828
3829         goto same_types;
3830       }
3831
3832     case RECORD_TYPE:
3833     case UNION_TYPE:
3834     case QUAL_UNION_TYPE:
3835       {
3836         tree f1, f2;
3837
3838         /* The struct tags shall compare equal.  */
3839         if (mode == GTC_MERGE
3840             && !compare_type_names_p (TYPE_MAIN_VARIANT (t1),
3841                                       TYPE_MAIN_VARIANT (t2), false))
3842           goto different_types;
3843
3844         /* For aggregate types, all the fields must be the same.  */
3845         for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
3846              f1 && f2;
3847              f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
3848           {
3849             /* The fields must have the same name, offset and type.  */
3850             if ((mode == GTC_MERGE
3851                  && DECL_NAME (f1) != DECL_NAME (f2))
3852                 || DECL_NONADDRESSABLE_P (f1) != DECL_NONADDRESSABLE_P (f2)
3853                 || !gimple_compare_field_offset (f1, f2)
3854                 || !gtc_visit (TREE_TYPE (f1), TREE_TYPE (f2), mode,
3855                                state, sccstack, sccstate, sccstate_obstack))
3856               goto different_types;
3857           }
3858
3859         /* If one aggregate has more fields than the other, they
3860            are not the same.  */
3861         if (f1 || f2)
3862           goto different_types;
3863
3864         goto same_types;
3865       }
3866
3867     default:
3868       gcc_unreachable ();
3869     }
3870
3871   /* Common exit path for types that are not compatible.  */
3872 different_types:
3873   state->u.same_p = 0;
3874   goto pop;
3875
3876   /* Common exit path for types that are compatible.  */
3877 same_types:
3878   gcc_assert (state->u.same_p == 1);
3879
3880 pop:
3881   if (state->low == state->dfsnum)
3882     {
3883       type_pair_t x;
3884
3885       /* Pop off the SCC and set its cache values to the final
3886          comparison result.  */
3887       do
3888         {
3889           struct sccs *cstate;
3890           x = VEC_pop (type_pair_t, *sccstack);
3891           cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
3892           cstate->on_sccstack = false;
3893           x->same_p[mode] = state->u.same_p;
3894         }
3895       while (x != p);
3896     }
3897
3898   return state->u.same_p;
3899 }
3900
3901 /* Return true iff T1 and T2 are structurally identical.  When
3902    FOR_MERGING_P is true the an incomplete type and a complete type
3903    are considered different, otherwise they are considered compatible.  */
3904
3905 bool
3906 gimple_types_compatible_p (tree t1, tree t2, enum gtc_mode mode)
3907 {
3908   VEC(type_pair_t, heap) *sccstack = NULL;
3909   struct pointer_map_t *sccstate;
3910   struct obstack sccstate_obstack;
3911   type_pair_t p = NULL;
3912   bool res;
3913
3914   /* Before starting to set up the SCC machinery handle simple cases.  */
3915
3916   /* Check first for the obvious case of pointer identity.  */
3917   if (t1 == t2)
3918     return true;
3919
3920   /* Check that we have two types to compare.  */
3921   if (t1 == NULL_TREE || t2 == NULL_TREE)
3922     return false;
3923
3924   /* If the types have been previously registered and found equal
3925      they still are.  */
3926   if (mode == GTC_MERGE)
3927     {
3928       tree leader1 = gimple_lookup_type_leader (t1);
3929       tree leader2 = gimple_lookup_type_leader (t2);
3930       if (leader1 == t2
3931           || t1 == leader2
3932           || (leader1 && leader1 == leader2))
3933         return true;
3934     }
3935   else if (mode == GTC_DIAG)
3936     {
3937       if (TYPE_CANONICAL (t1)
3938           && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2))
3939         return true;
3940     }
3941
3942   /* Can't be the same type if the types don't have the same code.  */
3943   if (TREE_CODE (t1) != TREE_CODE (t2))
3944     return false;
3945
3946   /* Can't be the same type if they have different CV qualifiers.  */
3947   if (TYPE_QUALS (t1) != TYPE_QUALS (t2))
3948     return false;
3949
3950   /* Void types are always the same.  */
3951   if (TREE_CODE (t1) == VOID_TYPE)
3952     return true;
3953
3954   /* Do some simple checks before doing three hashtable queries.  */
3955   if (INTEGRAL_TYPE_P (t1)
3956       || SCALAR_FLOAT_TYPE_P (t1)
3957       || FIXED_POINT_TYPE_P (t1)
3958       || TREE_CODE (t1) == VECTOR_TYPE
3959       || TREE_CODE (t1) == COMPLEX_TYPE
3960       || TREE_CODE (t1) == OFFSET_TYPE)
3961     {
3962       /* Can't be the same type if they have different alignment,
3963          sign, precision or mode.  */
3964       if (TYPE_ALIGN (t1) != TYPE_ALIGN (t2)
3965           || TYPE_PRECISION (t1) != TYPE_PRECISION (t2)
3966           || TYPE_MODE (t1) != TYPE_MODE (t2)
3967           || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
3968         return false;
3969
3970       if (TREE_CODE (t1) == INTEGER_TYPE
3971           && (TYPE_IS_SIZETYPE (t1) != TYPE_IS_SIZETYPE (t2)
3972               || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)))
3973         return false;
3974
3975       /* That's all we need to check for float and fixed-point types.  */
3976       if (SCALAR_FLOAT_TYPE_P (t1)
3977           || FIXED_POINT_TYPE_P (t1))
3978         return true;
3979
3980       /* For integral types fall thru to more complex checks.  */
3981     }
3982
3983   else if (AGGREGATE_TYPE_P (t1) || POINTER_TYPE_P (t1))
3984     {
3985       /* Can't be the same type if they have different alignment or mode.  */
3986       if (TYPE_ALIGN (t1) != TYPE_ALIGN (t2)
3987           || TYPE_MODE (t1) != TYPE_MODE (t2))
3988         return false;
3989     }
3990
3991   /* If the hash values of t1 and t2 are different the types can't
3992      possibly be the same.  This helps keeping the type-pair hashtable
3993      small, only tracking comparisons for hash collisions.  */
3994   if (gimple_type_hash_1 (t1, mode) != gimple_type_hash_1 (t2, mode))
3995     return false;
3996
3997   /* If we've visited this type pair before (in the case of aggregates
3998      with self-referential types), and we made a decision, return it.  */
3999   p = lookup_type_pair (t1, t2, &gtc_visited, &gtc_ob);
4000   if (p->same_p[mode] == 0 || p->same_p[mode] == 1)
4001     {
4002       /* We have already decided whether T1 and T2 are the
4003          same, return the cached result.  */
4004       return p->same_p[mode] == 1;
4005     }
4006
4007   /* Now set up the SCC machinery for the comparison.  */
4008   gtc_next_dfs_num = 1;
4009   sccstate = pointer_map_create ();
4010   gcc_obstack_init (&sccstate_obstack);
4011   res = gimple_types_compatible_p_1 (t1, t2, mode, p,
4012                                      &sccstack, sccstate, &sccstate_obstack);
4013   VEC_free (type_pair_t, heap, sccstack);
4014   pointer_map_destroy (sccstate);
4015   obstack_free (&sccstate_obstack, NULL);
4016
4017   return res;
4018 }
4019
4020
4021 static hashval_t
4022 iterative_hash_gimple_type (tree, hashval_t, VEC(tree, heap) **,
4023                             struct pointer_map_t *, struct obstack *,
4024                             enum gtc_mode);
4025
4026 /* DFS visit the edge from the callers type with state *STATE to T.
4027    Update the callers type hash V with the hash for T if it is not part
4028    of the SCC containing the callers type and return it.
4029    SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done.  */
4030
4031 static hashval_t
4032 visit (tree t, struct sccs *state, hashval_t v,
4033        VEC (tree, heap) **sccstack,
4034        struct pointer_map_t *sccstate,
4035        struct obstack *sccstate_obstack, enum gtc_mode mode)
4036 {
4037   struct sccs *cstate = NULL;
4038   struct tree_int_map m;
4039   void **slot;
4040
4041   /* If there is a hash value recorded for this type then it can't
4042      possibly be part of our parent SCC.  Simply mix in its hash.  */
4043   m.base.from = t;
4044   if ((slot = htab_find_slot (mode == GTC_MERGE
4045                               ? type_hash_cache : canonical_type_hash_cache,
4046                               &m, NO_INSERT))
4047       && *slot)
4048     return iterative_hash_hashval_t (((struct tree_int_map *) *slot)->to, v);
4049
4050   if ((slot = pointer_map_contains (sccstate, t)) != NULL)
4051     cstate = (struct sccs *)*slot;
4052   if (!cstate)
4053     {
4054       hashval_t tem;
4055       /* Not yet visited.  DFS recurse.  */
4056       tem = iterative_hash_gimple_type (t, v,
4057                                         sccstack, sccstate, sccstate_obstack,
4058                                         mode);
4059       if (!cstate)
4060         cstate = (struct sccs *)* pointer_map_contains (sccstate, t);
4061       state->low = MIN (state->low, cstate->low);
4062       /* If the type is no longer on the SCC stack and thus is not part
4063          of the parents SCC mix in its hash value.  Otherwise we will
4064          ignore the type for hashing purposes and return the unaltered
4065          hash value.  */
4066       if (!cstate->on_sccstack)
4067         return tem;
4068     }
4069   if (cstate->dfsnum < state->dfsnum
4070       && cstate->on_sccstack)
4071     state->low = MIN (cstate->dfsnum, state->low);
4072
4073   /* We are part of our parents SCC, skip this type during hashing
4074      and return the unaltered hash value.  */
4075   return v;
4076 }
4077
4078 /* Hash NAME with the previous hash value V and return it.  */
4079
4080 static hashval_t
4081 iterative_hash_name (tree name, hashval_t v)
4082 {
4083   if (!name)
4084     return v;
4085   if (TREE_CODE (name) == TYPE_DECL)
4086     name = DECL_NAME (name);
4087   if (!name)
4088     return v;
4089   gcc_assert (TREE_CODE (name) == IDENTIFIER_NODE);
4090   return iterative_hash_object (IDENTIFIER_HASH_VALUE (name), v);
4091 }
4092
4093 /* Returning a hash value for gimple type TYPE combined with VAL.
4094    SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done.
4095
4096    To hash a type we end up hashing in types that are reachable.
4097    Through pointers we can end up with cycles which messes up the
4098    required property that we need to compute the same hash value
4099    for structurally equivalent types.  To avoid this we have to
4100    hash all types in a cycle (the SCC) in a commutative way.  The
4101    easiest way is to not mix in the hashes of the SCC members at
4102    all.  To make this work we have to delay setting the hash
4103    values of the SCC until it is complete.  */
4104
4105 static hashval_t
4106 iterative_hash_gimple_type (tree type, hashval_t val,
4107                             VEC(tree, heap) **sccstack,
4108                             struct pointer_map_t *sccstate,
4109                             struct obstack *sccstate_obstack,
4110                             enum gtc_mode mode)
4111 {
4112   hashval_t v;
4113   void **slot;
4114   struct sccs *state;
4115
4116   /* Not visited during this DFS walk.  */
4117   gcc_checking_assert (!pointer_map_contains (sccstate, type));
4118   state = XOBNEW (sccstate_obstack, struct sccs);
4119   *pointer_map_insert (sccstate, type) = state;
4120
4121   VEC_safe_push (tree, heap, *sccstack, type);
4122   state->dfsnum = next_dfs_num++;
4123   state->low = state->dfsnum;
4124   state->on_sccstack = true;
4125
4126   /* Combine a few common features of types so that types are grouped into
4127      smaller sets; when searching for existing matching types to merge,
4128      only existing types having the same features as the new type will be
4129      checked.  */
4130   v = iterative_hash_hashval_t (TREE_CODE (type), 0);
4131   v = iterative_hash_hashval_t (TYPE_QUALS (type), v);
4132   v = iterative_hash_hashval_t (TREE_ADDRESSABLE (type), v);
4133
4134   /* Do not hash the types size as this will cause differences in
4135      hash values for the complete vs. the incomplete type variant.  */
4136
4137   /* Incorporate common features of numerical types.  */
4138   if (INTEGRAL_TYPE_P (type)
4139       || SCALAR_FLOAT_TYPE_P (type)
4140       || FIXED_POINT_TYPE_P (type))
4141     {
4142       v = iterative_hash_hashval_t (TYPE_PRECISION (type), v);
4143       v = iterative_hash_hashval_t (TYPE_MODE (type), v);
4144       v = iterative_hash_hashval_t (TYPE_UNSIGNED (type), v);
4145     }
4146
4147   /* For pointer and reference types, fold in information about the type
4148      pointed to but do not recurse into possibly incomplete types to
4149      avoid hash differences for complete vs. incomplete types.  */
4150   if (POINTER_TYPE_P (type))
4151     {
4152       if (RECORD_OR_UNION_TYPE_P (TREE_TYPE (type)))
4153         {
4154           v = iterative_hash_hashval_t (TREE_CODE (TREE_TYPE (type)), v);
4155           v = iterative_hash_name
4156                 (TYPE_NAME (TYPE_MAIN_VARIANT (TREE_TYPE (type))), v);
4157         }
4158       else
4159         v = visit (TREE_TYPE (type), state, v,
4160                    sccstack, sccstate, sccstate_obstack, mode);
4161     }
4162
4163   /* For integer types hash the types min/max values and the string flag.  */
4164   if (TREE_CODE (type) == INTEGER_TYPE)
4165     {
4166       /* OMP lowering can introduce error_mark_node in place of
4167          random local decls in types.  */
4168       if (TYPE_MIN_VALUE (type) != error_mark_node)
4169         v = iterative_hash_expr (TYPE_MIN_VALUE (type), v);
4170       if (TYPE_MAX_VALUE (type) != error_mark_node)
4171         v = iterative_hash_expr (TYPE_MAX_VALUE (type), v);
4172       v = iterative_hash_hashval_t (TYPE_STRING_FLAG (type), v);
4173     }
4174
4175   /* For array types hash their domain and the string flag.  */
4176   if (TREE_CODE (type) == ARRAY_TYPE
4177       && TYPE_DOMAIN (type))
4178     {
4179       v = iterative_hash_hashval_t (TYPE_STRING_FLAG (type), v);
4180       v = visit (TYPE_DOMAIN (type), state, v,
4181                  sccstack, sccstate, sccstate_obstack, mode);
4182     }
4183
4184   /* Recurse for aggregates with a single element type.  */
4185   if (TREE_CODE (type) == ARRAY_TYPE
4186       || TREE_CODE (type) == COMPLEX_TYPE
4187       || TREE_CODE (type) == VECTOR_TYPE)
4188     v = visit (TREE_TYPE (type), state, v,
4189                sccstack, sccstate, sccstate_obstack, mode);
4190
4191   /* Incorporate function return and argument types.  */
4192   if (TREE_CODE (type) == FUNCTION_TYPE || TREE_CODE (type) == METHOD_TYPE)
4193     {
4194       unsigned na;
4195       tree p;
4196
4197       /* For method types also incorporate their parent class.  */
4198       if (TREE_CODE (type) == METHOD_TYPE)
4199         v = visit (TYPE_METHOD_BASETYPE (type), state, v,
4200                    sccstack, sccstate, sccstate_obstack, mode);
4201
4202       /* For result types allow mismatch in completeness.  */
4203       if (RECORD_OR_UNION_TYPE_P (TREE_TYPE (type)))
4204         {
4205           v = iterative_hash_hashval_t (TREE_CODE (TREE_TYPE (type)), v);
4206           v = iterative_hash_name
4207                 (TYPE_NAME (TYPE_MAIN_VARIANT (TREE_TYPE (type))), v);
4208         }
4209       else
4210         v = visit (TREE_TYPE (type), state, v,
4211                    sccstack, sccstate, sccstate_obstack, mode);
4212
4213       for (p = TYPE_ARG_TYPES (type), na = 0; p; p = TREE_CHAIN (p))
4214         {
4215           /* For argument types allow mismatch in completeness.  */
4216           if (RECORD_OR_UNION_TYPE_P (TREE_VALUE (p)))
4217             {
4218               v = iterative_hash_hashval_t (TREE_CODE (TREE_VALUE (p)), v);
4219               v = iterative_hash_name
4220                     (TYPE_NAME (TYPE_MAIN_VARIANT (TREE_VALUE (p))), v);
4221             }
4222           else
4223             v = visit (TREE_VALUE (p), state, v,
4224                        sccstack, sccstate, sccstate_obstack, mode);
4225           na++;
4226         }
4227
4228       v = iterative_hash_hashval_t (na, v);
4229     }
4230
4231   if (TREE_CODE (type) == RECORD_TYPE
4232       || TREE_CODE (type) == UNION_TYPE
4233       || TREE_CODE (type) == QUAL_UNION_TYPE)
4234     {
4235       unsigned nf;
4236       tree f;
4237
4238       if (mode == GTC_MERGE)
4239         v = iterative_hash_name (TYPE_NAME (TYPE_MAIN_VARIANT (type)), v);
4240
4241       for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
4242         {
4243           if (mode == GTC_MERGE)
4244             v = iterative_hash_name (DECL_NAME (f), v);
4245           v = visit (TREE_TYPE (f), state, v,
4246                      sccstack, sccstate, sccstate_obstack, mode);
4247           nf++;
4248         }
4249
4250       v = iterative_hash_hashval_t (nf, v);
4251     }
4252
4253   /* Record hash for us.  */
4254   state->u.hash = v;
4255
4256   /* See if we found an SCC.  */
4257   if (state->low == state->dfsnum)
4258     {
4259       tree x;
4260
4261       /* Pop off the SCC and set its hash values.  */
4262       do
4263         {
4264           struct sccs *cstate;
4265           struct tree_int_map *m = ggc_alloc_cleared_tree_int_map ();
4266           x = VEC_pop (tree, *sccstack);
4267           cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
4268           cstate->on_sccstack = false;
4269           m->base.from = x;
4270           m->to = cstate->u.hash;
4271           slot = htab_find_slot (mode == GTC_MERGE
4272                                  ? type_hash_cache : canonical_type_hash_cache,
4273                                  m, INSERT);
4274           gcc_assert (!*slot);
4275           *slot = (void *) m;
4276         }
4277       while (x != type);
4278     }
4279
4280   return iterative_hash_hashval_t (v, val);
4281 }
4282
4283
4284 /* Returns a hash value for P (assumed to be a type).  The hash value
4285    is computed using some distinguishing features of the type.  Note
4286    that we cannot use pointer hashing here as we may be dealing with
4287    two distinct instances of the same type.
4288
4289    This function should produce the same hash value for two compatible
4290    types according to gimple_types_compatible_p.  */
4291
4292 static hashval_t
4293 gimple_type_hash_1 (const void *p, enum gtc_mode mode)
4294 {
4295   const_tree t = (const_tree) p;
4296   VEC(tree, heap) *sccstack = NULL;
4297   struct pointer_map_t *sccstate;
4298   struct obstack sccstate_obstack;
4299   hashval_t val;
4300   void **slot;
4301   struct tree_int_map m;
4302
4303   if (mode == GTC_MERGE
4304       && type_hash_cache == NULL)
4305     type_hash_cache = htab_create_ggc (512, tree_int_map_hash,
4306                                        tree_int_map_eq, NULL);
4307   else if (mode == GTC_DIAG
4308            && canonical_type_hash_cache == NULL)
4309     canonical_type_hash_cache = htab_create_ggc (512, tree_int_map_hash,
4310                                                  tree_int_map_eq, NULL);
4311
4312   m.base.from = CONST_CAST_TREE (t);
4313   if ((slot = htab_find_slot (mode == GTC_MERGE
4314                               ? type_hash_cache : canonical_type_hash_cache,
4315                               &m, NO_INSERT))
4316       && *slot)
4317     return iterative_hash_hashval_t (((struct tree_int_map *) *slot)->to, 0);
4318
4319   /* Perform a DFS walk and pre-hash all reachable types.  */
4320   next_dfs_num = 1;
4321   sccstate = pointer_map_create ();
4322   gcc_obstack_init (&sccstate_obstack);
4323   val = iterative_hash_gimple_type (CONST_CAST_TREE (t), 0,
4324                                     &sccstack, sccstate, &sccstate_obstack,
4325                                     mode);
4326   VEC_free (tree, heap, sccstack);
4327   pointer_map_destroy (sccstate);
4328   obstack_free (&sccstate_obstack, NULL);
4329
4330   return val;
4331 }
4332
4333 static hashval_t
4334 gimple_type_hash (const void *p)
4335 {
4336   return gimple_type_hash_1 (p, GTC_MERGE);
4337 }
4338
4339 static hashval_t
4340 gimple_canonical_type_hash (const void *p)
4341 {
4342   return gimple_type_hash_1 (p, GTC_DIAG);
4343 }
4344
4345
4346 /* Returns nonzero if P1 and P2 are equal.  */
4347
4348 static int
4349 gimple_type_eq (const void *p1, const void *p2)
4350 {
4351   const_tree t1 = (const_tree) p1;
4352   const_tree t2 = (const_tree) p2;
4353   return gimple_types_compatible_p (CONST_CAST_TREE (t1),
4354                                     CONST_CAST_TREE (t2), GTC_MERGE);
4355 }
4356
4357
4358 /* Register type T in the global type table gimple_types.
4359    If another type T', compatible with T, already existed in
4360    gimple_types then return T', otherwise return T.  This is used by
4361    LTO to merge identical types read from different TUs.  */
4362
4363 tree
4364 gimple_register_type (tree t)
4365 {
4366   void **slot;
4367   gimple_type_leader_entry *leader;
4368   tree mv_leader = NULL_TREE;
4369
4370   gcc_assert (TYPE_P (t));
4371
4372   if (!gimple_type_leader)
4373     gimple_type_leader = ggc_alloc_cleared_vec_gimple_type_leader_entry_s
4374                                 (GIMPLE_TYPE_LEADER_SIZE);
4375   /* If we registered this type before return the cached result.  */
4376   leader = &gimple_type_leader[TYPE_UID (t) % GIMPLE_TYPE_LEADER_SIZE];
4377   if (leader->type == t)
4378     return leader->leader;
4379
4380   /* Always register the main variant first.  This is important so we
4381      pick up the non-typedef variants as canonical, otherwise we'll end
4382      up taking typedef ids for structure tags during comparison.  */
4383   if (TYPE_MAIN_VARIANT (t) != t)
4384     mv_leader = gimple_register_type (TYPE_MAIN_VARIANT (t));
4385
4386   if (gimple_types == NULL)
4387     gimple_types = htab_create_ggc (16381, gimple_type_hash, gimple_type_eq, 0);
4388
4389   slot = htab_find_slot (gimple_types, t, INSERT);
4390   if (*slot
4391       && *(tree *)slot != t)
4392     {
4393       tree new_type = (tree) *((tree *) slot);
4394
4395       /* Do not merge types with different addressability.  */
4396       gcc_assert (TREE_ADDRESSABLE (t) == TREE_ADDRESSABLE (new_type));
4397
4398       /* If t is not its main variant then make t unreachable from its
4399          main variant list.  Otherwise we'd queue up a lot of duplicates
4400          there.  */
4401       if (t != TYPE_MAIN_VARIANT (t))
4402         {
4403           tree tem = TYPE_MAIN_VARIANT (t);
4404           while (tem && TYPE_NEXT_VARIANT (tem) != t)
4405             tem = TYPE_NEXT_VARIANT (tem);
4406           if (tem)
4407             TYPE_NEXT_VARIANT (tem) = TYPE_NEXT_VARIANT (t);
4408           TYPE_NEXT_VARIANT (t) = NULL_TREE;
4409         }
4410
4411       /* If we are a pointer then remove us from the pointer-to or
4412          reference-to chain.  Otherwise we'd queue up a lot of duplicates
4413          there.  */
4414       if (TREE_CODE (t) == POINTER_TYPE)
4415         {
4416           if (TYPE_POINTER_TO (TREE_TYPE (t)) == t)
4417             TYPE_POINTER_TO (TREE_TYPE (t)) = TYPE_NEXT_PTR_TO (t);
4418           else
4419             {
4420               tree tem = TYPE_POINTER_TO (TREE_TYPE (t));
4421               while (tem && TYPE_NEXT_PTR_TO (tem) != t)
4422                 tem = TYPE_NEXT_PTR_TO (tem);
4423               if (tem)
4424                 TYPE_NEXT_PTR_TO (tem) = TYPE_NEXT_PTR_TO (t);
4425             }
4426           TYPE_NEXT_PTR_TO (t) = NULL_TREE;
4427         }
4428       else if (TREE_CODE (t) == REFERENCE_TYPE)
4429         {
4430           if (TYPE_REFERENCE_TO (TREE_TYPE (t)) == t)
4431             TYPE_REFERENCE_TO (TREE_TYPE (t)) = TYPE_NEXT_REF_TO (t);
4432           else
4433             {
4434               tree tem = TYPE_REFERENCE_TO (TREE_TYPE (t));
4435               while (tem && TYPE_NEXT_REF_TO (tem) != t)
4436                 tem = TYPE_NEXT_REF_TO (tem);
4437               if (tem)
4438                 TYPE_NEXT_REF_TO (tem) = TYPE_NEXT_REF_TO (t);
4439             }
4440           TYPE_NEXT_REF_TO (t) = NULL_TREE;
4441         }
4442
4443       leader->type = t;
4444       leader->leader = new_type;
4445       t = new_type;
4446     }
4447   else
4448     {
4449       leader->type = t;
4450       leader->leader = t;
4451       /* We're the type leader.  Make our TYPE_MAIN_VARIANT valid.  */
4452       if (TYPE_MAIN_VARIANT (t) != t
4453           && TYPE_MAIN_VARIANT (t) != mv_leader)
4454         {
4455           /* Remove us from our main variant list as we are not the variant
4456              leader and the variant leader will change.  */
4457           tree tem = TYPE_MAIN_VARIANT (t);
4458           while (tem && TYPE_NEXT_VARIANT (tem) != t)
4459             tem = TYPE_NEXT_VARIANT (tem);
4460           if (tem)
4461             TYPE_NEXT_VARIANT (tem) = TYPE_NEXT_VARIANT (t);
4462           TYPE_NEXT_VARIANT (t) = NULL_TREE;
4463           /* Adjust our main variant.  Linking us into its variant list
4464              will happen at fixup time.  */
4465           TYPE_MAIN_VARIANT (t) = mv_leader;
4466         }
4467       *slot = (void *) t;
4468     }
4469
4470   return t;
4471 }
4472
4473
4474 /* Returns nonzero if P1 and P2 are equal.  */
4475
4476 static int
4477 gimple_canonical_type_eq (const void *p1, const void *p2)
4478 {
4479   const_tree t1 = (const_tree) p1;
4480   const_tree t2 = (const_tree) p2;
4481   return gimple_types_compatible_p (CONST_CAST_TREE (t1),
4482                                     CONST_CAST_TREE (t2), GTC_DIAG);
4483 }
4484
4485 /* Register type T in the global type table gimple_types.
4486    If another type T', compatible with T, already existed in
4487    gimple_types then return T', otherwise return T.  This is used by
4488    LTO to merge identical types read from different TUs.  */
4489
4490 tree
4491 gimple_register_canonical_type (tree t)
4492 {
4493   void **slot;
4494   tree orig_t = t;
4495
4496   gcc_assert (TYPE_P (t));
4497
4498   if (TYPE_CANONICAL (t))
4499     return TYPE_CANONICAL (t);
4500
4501   /* Always register the type itself first so that if it turns out
4502      to be the canonical type it will be the one we merge to as well.  */
4503   t = gimple_register_type (t);
4504
4505   /* Always register the main variant first.  This is important so we
4506      pick up the non-typedef variants as canonical, otherwise we'll end
4507      up taking typedef ids for structure tags during comparison.  */
4508   if (TYPE_MAIN_VARIANT (t) != t)
4509     gimple_register_canonical_type (TYPE_MAIN_VARIANT (t));
4510
4511   if (gimple_canonical_types == NULL)
4512     gimple_canonical_types = htab_create_ggc (16381, gimple_canonical_type_hash,
4513                                               gimple_canonical_type_eq, 0);
4514
4515   slot = htab_find_slot (gimple_canonical_types, t, INSERT);
4516   if (*slot
4517       && *(tree *)slot != t)
4518     {
4519       tree new_type = (tree) *((tree *) slot);
4520
4521       TYPE_CANONICAL (t) = new_type;
4522       t = new_type;
4523     }
4524   else
4525     {
4526       TYPE_CANONICAL (t) = t;
4527       *slot = (void *) t;
4528     }
4529
4530   /* Also cache the canonical type in the non-leaders.  */
4531   TYPE_CANONICAL (orig_t) = t;
4532
4533   return t;
4534 }
4535
4536
4537 /* Show statistics on references to the global type table gimple_types.  */
4538
4539 void
4540 print_gimple_types_stats (void)
4541 {
4542   if (gimple_types)
4543     fprintf (stderr, "GIMPLE type table: size %ld, %ld elements, "
4544              "%ld searches, %ld collisions (ratio: %f)\n",
4545              (long) htab_size (gimple_types),
4546              (long) htab_elements (gimple_types),
4547              (long) gimple_types->searches,
4548              (long) gimple_types->collisions,
4549              htab_collisions (gimple_types));
4550   else
4551     fprintf (stderr, "GIMPLE type table is empty\n");
4552   if (type_hash_cache)
4553     fprintf (stderr, "GIMPLE type hash table: size %ld, %ld elements, "
4554              "%ld searches, %ld collisions (ratio: %f)\n",
4555              (long) htab_size (type_hash_cache),
4556              (long) htab_elements (type_hash_cache),
4557              (long) type_hash_cache->searches,
4558              (long) type_hash_cache->collisions,
4559              htab_collisions (type_hash_cache));
4560   else
4561     fprintf (stderr, "GIMPLE type hash table is empty\n");
4562   if (gimple_canonical_types)
4563     fprintf (stderr, "GIMPLE canonical type table: size %ld, %ld elements, "
4564              "%ld searches, %ld collisions (ratio: %f)\n",
4565              (long) htab_size (gimple_canonical_types),
4566              (long) htab_elements (gimple_canonical_types),
4567              (long) gimple_canonical_types->searches,
4568              (long) gimple_canonical_types->collisions,
4569              htab_collisions (gimple_canonical_types));
4570   else
4571     fprintf (stderr, "GIMPLE canonical type table is empty\n");
4572   if (canonical_type_hash_cache)
4573     fprintf (stderr, "GIMPLE canonical type hash table: size %ld, %ld elements, "
4574              "%ld searches, %ld collisions (ratio: %f)\n",
4575              (long) htab_size (canonical_type_hash_cache),
4576              (long) htab_elements (canonical_type_hash_cache),
4577              (long) canonical_type_hash_cache->searches,
4578              (long) canonical_type_hash_cache->collisions,
4579              htab_collisions (canonical_type_hash_cache));
4580   else
4581     fprintf (stderr, "GIMPLE canonical type hash table is empty\n");
4582   if (gtc_visited)
4583     fprintf (stderr, "GIMPLE type comparison table: size %ld, %ld "
4584              "elements, %ld searches, %ld collisions (ratio: %f)\n",
4585              (long) htab_size (gtc_visited),
4586              (long) htab_elements (gtc_visited),
4587              (long) gtc_visited->searches,
4588              (long) gtc_visited->collisions,
4589              htab_collisions (gtc_visited));
4590   else
4591     fprintf (stderr, "GIMPLE type comparison table is empty\n");
4592 }
4593
4594 /* Free the gimple type hashtables used for LTO type merging.  */
4595
4596 void
4597 free_gimple_type_tables (void)
4598 {
4599   /* Last chance to print stats for the tables.  */
4600   if (flag_lto_report)
4601     print_gimple_types_stats ();
4602
4603   if (gimple_types)
4604     {
4605       htab_delete (gimple_types);
4606       gimple_types = NULL;
4607     }
4608   if (gimple_canonical_types)
4609     {
4610       htab_delete (gimple_canonical_types);
4611       gimple_canonical_types = NULL;
4612     }
4613   if (type_hash_cache)
4614     {
4615       htab_delete (type_hash_cache);
4616       type_hash_cache = NULL;
4617     }
4618   if (canonical_type_hash_cache)
4619     {
4620       htab_delete (canonical_type_hash_cache);
4621       canonical_type_hash_cache = NULL;
4622     }
4623   if (gtc_visited)
4624     {
4625       htab_delete (gtc_visited);
4626       obstack_free (&gtc_ob, NULL);
4627       gtc_visited = NULL;
4628     }
4629   gimple_type_leader = NULL;
4630 }
4631
4632
4633 /* Return a type the same as TYPE except unsigned or
4634    signed according to UNSIGNEDP.  */
4635
4636 static tree
4637 gimple_signed_or_unsigned_type (bool unsignedp, tree type)
4638 {
4639   tree type1;
4640
4641   type1 = TYPE_MAIN_VARIANT (type);
4642   if (type1 == signed_char_type_node
4643       || type1 == char_type_node
4644       || type1 == unsigned_char_type_node)
4645     return unsignedp ? unsigned_char_type_node : signed_char_type_node;
4646   if (type1 == integer_type_node || type1 == unsigned_type_node)
4647     return unsignedp ? unsigned_type_node : integer_type_node;
4648   if (type1 == short_integer_type_node || type1 == short_unsigned_type_node)
4649     return unsignedp ? short_unsigned_type_node : short_integer_type_node;
4650   if (type1 == long_integer_type_node || type1 == long_unsigned_type_node)
4651     return unsignedp ? long_unsigned_type_node : long_integer_type_node;
4652   if (type1 == long_long_integer_type_node
4653       || type1 == long_long_unsigned_type_node)
4654     return unsignedp
4655            ? long_long_unsigned_type_node
4656            : long_long_integer_type_node;
4657   if (int128_integer_type_node && (type1 == int128_integer_type_node || type1 == int128_unsigned_type_node))
4658     return unsignedp
4659            ? int128_unsigned_type_node
4660            : int128_integer_type_node;
4661 #if HOST_BITS_PER_WIDE_INT >= 64
4662   if (type1 == intTI_type_node || type1 == unsigned_intTI_type_node)
4663     return unsignedp ? unsigned_intTI_type_node : intTI_type_node;
4664 #endif
4665   if (type1 == intDI_type_node || type1 == unsigned_intDI_type_node)
4666     return unsignedp ? unsigned_intDI_type_node : intDI_type_node;
4667   if (type1 == intSI_type_node || type1 == unsigned_intSI_type_node)
4668     return unsignedp ? unsigned_intSI_type_node : intSI_type_node;
4669   if (type1 == intHI_type_node || type1 == unsigned_intHI_type_node)
4670     return unsignedp ? unsigned_intHI_type_node : intHI_type_node;
4671   if (type1 == intQI_type_node || type1 == unsigned_intQI_type_node)
4672     return unsignedp ? unsigned_intQI_type_node : intQI_type_node;
4673
4674 #define GIMPLE_FIXED_TYPES(NAME)            \
4675   if (type1 == short_ ## NAME ## _type_node \
4676       || type1 == unsigned_short_ ## NAME ## _type_node) \
4677     return unsignedp ? unsigned_short_ ## NAME ## _type_node \
4678                      : short_ ## NAME ## _type_node; \
4679   if (type1 == NAME ## _type_node \
4680       || type1 == unsigned_ ## NAME ## _type_node) \
4681     return unsignedp ? unsigned_ ## NAME ## _type_node \
4682                      : NAME ## _type_node; \
4683   if (type1 == long_ ## NAME ## _type_node \
4684       || type1 == unsigned_long_ ## NAME ## _type_node) \
4685     return unsignedp ? unsigned_long_ ## NAME ## _type_node \
4686                      : long_ ## NAME ## _type_node; \
4687   if (type1 == long_long_ ## NAME ## _type_node \
4688       || type1 == unsigned_long_long_ ## NAME ## _type_node) \
4689     return unsignedp ? unsigned_long_long_ ## NAME ## _type_node \
4690                      : long_long_ ## NAME ## _type_node;
4691
4692 #define GIMPLE_FIXED_MODE_TYPES(NAME) \
4693   if (type1 == NAME ## _type_node \
4694       || type1 == u ## NAME ## _type_node) \
4695     return unsignedp ? u ## NAME ## _type_node \
4696                      : NAME ## _type_node;
4697
4698 #define GIMPLE_FIXED_TYPES_SAT(NAME) \
4699   if (type1 == sat_ ## short_ ## NAME ## _type_node \
4700       || type1 == sat_ ## unsigned_short_ ## NAME ## _type_node) \
4701     return unsignedp ? sat_ ## unsigned_short_ ## NAME ## _type_node \
4702                      : sat_ ## short_ ## NAME ## _type_node; \
4703   if (type1 == sat_ ## NAME ## _type_node \
4704       || type1 == sat_ ## unsigned_ ## NAME ## _type_node) \
4705     return unsignedp ? sat_ ## unsigned_ ## NAME ## _type_node \
4706                      : sat_ ## NAME ## _type_node; \
4707   if (type1 == sat_ ## long_ ## NAME ## _type_node \
4708       || type1 == sat_ ## unsigned_long_ ## NAME ## _type_node) \
4709     return unsignedp ? sat_ ## unsigned_long_ ## NAME ## _type_node \
4710                      : sat_ ## long_ ## NAME ## _type_node; \
4711   if (type1 == sat_ ## long_long_ ## NAME ## _type_node \
4712       || type1 == sat_ ## unsigned_long_long_ ## NAME ## _type_node) \
4713     return unsignedp ? sat_ ## unsigned_long_long_ ## NAME ## _type_node \
4714                      : sat_ ## long_long_ ## NAME ## _type_node;
4715
4716 #define GIMPLE_FIXED_MODE_TYPES_SAT(NAME)       \
4717   if (type1 == sat_ ## NAME ## _type_node \
4718       || type1 == sat_ ## u ## NAME ## _type_node) \
4719     return unsignedp ? sat_ ## u ## NAME ## _type_node \
4720                      : sat_ ## NAME ## _type_node;
4721
4722   GIMPLE_FIXED_TYPES (fract);
4723   GIMPLE_FIXED_TYPES_SAT (fract);
4724   GIMPLE_FIXED_TYPES (accum);
4725   GIMPLE_FIXED_TYPES_SAT (accum);
4726
4727   GIMPLE_FIXED_MODE_TYPES (qq);
4728   GIMPLE_FIXED_MODE_TYPES (hq);
4729   GIMPLE_FIXED_MODE_TYPES (sq);
4730   GIMPLE_FIXED_MODE_TYPES (dq);
4731   GIMPLE_FIXED_MODE_TYPES (tq);
4732   GIMPLE_FIXED_MODE_TYPES_SAT (qq);
4733   GIMPLE_FIXED_MODE_TYPES_SAT (hq);
4734   GIMPLE_FIXED_MODE_TYPES_SAT (sq);
4735   GIMPLE_FIXED_MODE_TYPES_SAT (dq);
4736   GIMPLE_FIXED_MODE_TYPES_SAT (tq);
4737   GIMPLE_FIXED_MODE_TYPES (ha);
4738   GIMPLE_FIXED_MODE_TYPES (sa);
4739   GIMPLE_FIXED_MODE_TYPES (da);
4740   GIMPLE_FIXED_MODE_TYPES (ta);
4741   GIMPLE_FIXED_MODE_TYPES_SAT (ha);
4742   GIMPLE_FIXED_MODE_TYPES_SAT (sa);
4743   GIMPLE_FIXED_MODE_TYPES_SAT (da);
4744   GIMPLE_FIXED_MODE_TYPES_SAT (ta);
4745
4746   /* For ENUMERAL_TYPEs in C++, must check the mode of the types, not
4747      the precision; they have precision set to match their range, but
4748      may use a wider mode to match an ABI.  If we change modes, we may
4749      wind up with bad conversions.  For INTEGER_TYPEs in C, must check
4750      the precision as well, so as to yield correct results for
4751      bit-field types.  C++ does not have these separate bit-field
4752      types, and producing a signed or unsigned variant of an
4753      ENUMERAL_TYPE may cause other problems as well.  */
4754   if (!INTEGRAL_TYPE_P (type)
4755       || TYPE_UNSIGNED (type) == unsignedp)
4756     return type;
4757
4758 #define TYPE_OK(node)                                                       \
4759   (TYPE_MODE (type) == TYPE_MODE (node)                                     \
4760    && TYPE_PRECISION (type) == TYPE_PRECISION (node))
4761   if (TYPE_OK (signed_char_type_node))
4762     return unsignedp ? unsigned_char_type_node : signed_char_type_node;
4763   if (TYPE_OK (integer_type_node))
4764     return unsignedp ? unsigned_type_node : integer_type_node;
4765   if (TYPE_OK (short_integer_type_node))
4766     return unsignedp ? short_unsigned_type_node : short_integer_type_node;
4767   if (TYPE_OK (long_integer_type_node))
4768     return unsignedp ? long_unsigned_type_node : long_integer_type_node;
4769   if (TYPE_OK (long_long_integer_type_node))
4770     return (unsignedp
4771             ? long_long_unsigned_type_node
4772             : long_long_integer_type_node);
4773   if (int128_integer_type_node && TYPE_OK (int128_integer_type_node))
4774     return (unsignedp
4775             ? int128_unsigned_type_node
4776             : int128_integer_type_node);
4777
4778 #if HOST_BITS_PER_WIDE_INT >= 64
4779   if (TYPE_OK (intTI_type_node))
4780     return unsignedp ? unsigned_intTI_type_node : intTI_type_node;
4781 #endif
4782   if (TYPE_OK (intDI_type_node))
4783     return unsignedp ? unsigned_intDI_type_node : intDI_type_node;
4784   if (TYPE_OK (intSI_type_node))
4785     return unsignedp ? unsigned_intSI_type_node : intSI_type_node;
4786   if (TYPE_OK (intHI_type_node))
4787     return unsignedp ? unsigned_intHI_type_node : intHI_type_node;
4788   if (TYPE_OK (intQI_type_node))
4789     return unsignedp ? unsigned_intQI_type_node : intQI_type_node;
4790
4791 #undef GIMPLE_FIXED_TYPES
4792 #undef GIMPLE_FIXED_MODE_TYPES
4793 #undef GIMPLE_FIXED_TYPES_SAT
4794 #undef GIMPLE_FIXED_MODE_TYPES_SAT
4795 #undef TYPE_OK
4796
4797   return build_nonstandard_integer_type (TYPE_PRECISION (type), unsignedp);
4798 }
4799
4800
4801 /* Return an unsigned type the same as TYPE in other respects.  */
4802
4803 tree
4804 gimple_unsigned_type (tree type)
4805 {
4806   return gimple_signed_or_unsigned_type (true, type);
4807 }
4808
4809
4810 /* Return a signed type the same as TYPE in other respects.  */
4811
4812 tree
4813 gimple_signed_type (tree type)
4814 {
4815   return gimple_signed_or_unsigned_type (false, type);
4816 }
4817
4818
4819 /* Return the typed-based alias set for T, which may be an expression
4820    or a type.  Return -1 if we don't do anything special.  */
4821
4822 alias_set_type
4823 gimple_get_alias_set (tree t)
4824 {
4825   tree u;
4826
4827   /* Permit type-punning when accessing a union, provided the access
4828      is directly through the union.  For example, this code does not
4829      permit taking the address of a union member and then storing
4830      through it.  Even the type-punning allowed here is a GCC
4831      extension, albeit a common and useful one; the C standard says
4832      that such accesses have implementation-defined behavior.  */
4833   for (u = t;
4834        TREE_CODE (u) == COMPONENT_REF || TREE_CODE (u) == ARRAY_REF;
4835        u = TREE_OPERAND (u, 0))
4836     if (TREE_CODE (u) == COMPONENT_REF
4837         && TREE_CODE (TREE_TYPE (TREE_OPERAND (u, 0))) == UNION_TYPE)
4838       return 0;
4839
4840   /* That's all the expressions we handle specially.  */
4841   if (!TYPE_P (t))
4842     return -1;
4843
4844   /* For convenience, follow the C standard when dealing with
4845      character types.  Any object may be accessed via an lvalue that
4846      has character type.  */
4847   if (t == char_type_node
4848       || t == signed_char_type_node
4849       || t == unsigned_char_type_node)
4850     return 0;
4851
4852   /* Allow aliasing between signed and unsigned variants of the same
4853      type.  We treat the signed variant as canonical.  */
4854   if (TREE_CODE (t) == INTEGER_TYPE && TYPE_UNSIGNED (t))
4855     {
4856       tree t1 = gimple_signed_type (t);
4857
4858       /* t1 == t can happen for boolean nodes which are always unsigned.  */
4859       if (t1 != t)
4860         return get_alias_set (t1);
4861     }
4862
4863   return -1;
4864 }
4865
4866
4867 /* Data structure used to count the number of dereferences to PTR
4868    inside an expression.  */
4869 struct count_ptr_d
4870 {
4871   tree ptr;
4872   unsigned num_stores;
4873   unsigned num_loads;
4874 };
4875
4876 /* Helper for count_uses_and_derefs.  Called by walk_tree to look for
4877    (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA.  */
4878
4879 static tree
4880 count_ptr_derefs (tree *tp, int *walk_subtrees, void *data)
4881 {
4882   struct walk_stmt_info *wi_p = (struct walk_stmt_info *) data;
4883   struct count_ptr_d *count_p = (struct count_ptr_d *) wi_p->info;
4884
4885   /* Do not walk inside ADDR_EXPR nodes.  In the expression &ptr->fld,
4886      pointer 'ptr' is *not* dereferenced, it is simply used to compute
4887      the address of 'fld' as 'ptr + offsetof(fld)'.  */
4888   if (TREE_CODE (*tp) == ADDR_EXPR)
4889     {
4890       *walk_subtrees = 0;
4891       return NULL_TREE;
4892     }
4893
4894   if (TREE_CODE (*tp) == MEM_REF && TREE_OPERAND (*tp, 0) == count_p->ptr)
4895     {
4896       if (wi_p->is_lhs)
4897         count_p->num_stores++;
4898       else
4899         count_p->num_loads++;
4900     }
4901
4902   return NULL_TREE;
4903 }
4904
4905 /* Count the number of direct and indirect uses for pointer PTR in
4906    statement STMT.  The number of direct uses is stored in
4907    *NUM_USES_P.  Indirect references are counted separately depending
4908    on whether they are store or load operations.  The counts are
4909    stored in *NUM_STORES_P and *NUM_LOADS_P.  */
4910
4911 void
4912 count_uses_and_derefs (tree ptr, gimple stmt, unsigned *num_uses_p,
4913                        unsigned *num_loads_p, unsigned *num_stores_p)
4914 {
4915   ssa_op_iter i;
4916   tree use;
4917
4918   *num_uses_p = 0;
4919   *num_loads_p = 0;
4920   *num_stores_p = 0;
4921
4922   /* Find out the total number of uses of PTR in STMT.  */
4923   FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
4924     if (use == ptr)
4925       (*num_uses_p)++;
4926
4927   /* Now count the number of indirect references to PTR.  This is
4928      truly awful, but we don't have much choice.  There are no parent
4929      pointers inside INDIRECT_REFs, so an expression like
4930      '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
4931      find all the indirect and direct uses of x_1 inside.  The only
4932      shortcut we can take is the fact that GIMPLE only allows
4933      INDIRECT_REFs inside the expressions below.  */
4934   if (is_gimple_assign (stmt)
4935       || gimple_code (stmt) == GIMPLE_RETURN
4936       || gimple_code (stmt) == GIMPLE_ASM
4937       || is_gimple_call (stmt))
4938     {
4939       struct walk_stmt_info wi;
4940       struct count_ptr_d count;
4941
4942       count.ptr = ptr;
4943       count.num_stores = 0;
4944       count.num_loads = 0;
4945
4946       memset (&wi, 0, sizeof (wi));
4947       wi.info = &count;
4948       walk_gimple_op (stmt, count_ptr_derefs, &wi);
4949
4950       *num_stores_p = count.num_stores;
4951       *num_loads_p = count.num_loads;
4952     }
4953
4954   gcc_assert (*num_uses_p >= *num_loads_p + *num_stores_p);
4955 }
4956
4957 /* From a tree operand OP return the base of a load or store operation
4958    or NULL_TREE if OP is not a load or a store.  */
4959
4960 static tree
4961 get_base_loadstore (tree op)
4962 {
4963   while (handled_component_p (op))
4964     op = TREE_OPERAND (op, 0);
4965   if (DECL_P (op)
4966       || INDIRECT_REF_P (op)
4967       || TREE_CODE (op) == MEM_REF
4968       || TREE_CODE (op) == TARGET_MEM_REF)
4969     return op;
4970   return NULL_TREE;
4971 }
4972
4973 /* For the statement STMT call the callbacks VISIT_LOAD, VISIT_STORE and
4974    VISIT_ADDR if non-NULL on loads, store and address-taken operands
4975    passing the STMT, the base of the operand and DATA to it.  The base
4976    will be either a decl, an indirect reference (including TARGET_MEM_REF)
4977    or the argument of an address expression.
4978    Returns the results of these callbacks or'ed.  */
4979
4980 bool
4981 walk_stmt_load_store_addr_ops (gimple stmt, void *data,
4982                                bool (*visit_load)(gimple, tree, void *),
4983                                bool (*visit_store)(gimple, tree, void *),
4984                                bool (*visit_addr)(gimple, tree, void *))
4985 {
4986   bool ret = false;
4987   unsigned i;
4988   if (gimple_assign_single_p (stmt))
4989     {
4990       tree lhs, rhs;
4991       if (visit_store)
4992         {
4993           lhs = get_base_loadstore (gimple_assign_lhs (stmt));
4994           if (lhs)
4995             ret |= visit_store (stmt, lhs, data);
4996         }
4997       rhs = gimple_assign_rhs1 (stmt);
4998       while (handled_component_p (rhs))
4999         rhs = TREE_OPERAND (rhs, 0);
5000       if (visit_addr)
5001         {
5002           if (TREE_CODE (rhs) == ADDR_EXPR)
5003             ret |= visit_addr (stmt, TREE_OPERAND (rhs, 0), data);
5004           else if (TREE_CODE (rhs) == TARGET_MEM_REF
5005                    && TREE_CODE (TMR_BASE (rhs)) == ADDR_EXPR)
5006             ret |= visit_addr (stmt, TREE_OPERAND (TMR_BASE (rhs), 0), data);
5007           else if (TREE_CODE (rhs) == OBJ_TYPE_REF
5008                    && TREE_CODE (OBJ_TYPE_REF_OBJECT (rhs)) == ADDR_EXPR)
5009             ret |= visit_addr (stmt, TREE_OPERAND (OBJ_TYPE_REF_OBJECT (rhs),
5010                                                    0), data);
5011           lhs = gimple_assign_lhs (stmt);
5012           if (TREE_CODE (lhs) == TARGET_MEM_REF
5013               && TREE_CODE (TMR_BASE (lhs)) == ADDR_EXPR)
5014             ret |= visit_addr (stmt, TREE_OPERAND (TMR_BASE (lhs), 0), data);
5015         }
5016       if (visit_load)
5017         {
5018           rhs = get_base_loadstore (rhs);
5019           if (rhs)
5020             ret |= visit_load (stmt, rhs, data);
5021         }
5022     }
5023   else if (visit_addr
5024            && (is_gimple_assign (stmt)
5025                || gimple_code (stmt) == GIMPLE_COND))
5026     {
5027       for (i = 0; i < gimple_num_ops (stmt); ++i)
5028         if (gimple_op (stmt, i)
5029             && TREE_CODE (gimple_op (stmt, i)) == ADDR_EXPR)
5030           ret |= visit_addr (stmt, TREE_OPERAND (gimple_op (stmt, i), 0), data);
5031     }
5032   else if (is_gimple_call (stmt))
5033     {
5034       if (visit_store)
5035         {
5036           tree lhs = gimple_call_lhs (stmt);
5037           if (lhs)
5038             {
5039               lhs = get_base_loadstore (lhs);
5040               if (lhs)
5041                 ret |= visit_store (stmt, lhs, data);
5042             }
5043         }
5044       if (visit_load || visit_addr)
5045         for (i = 0; i < gimple_call_num_args (stmt); ++i)
5046           {
5047             tree rhs = gimple_call_arg (stmt, i);
5048             if (visit_addr
5049                 && TREE_CODE (rhs) == ADDR_EXPR)
5050               ret |= visit_addr (stmt, TREE_OPERAND (rhs, 0), data);
5051             else if (visit_load)
5052               {
5053                 rhs = get_base_loadstore (rhs);
5054                 if (rhs)
5055                   ret |= visit_load (stmt, rhs, data);
5056               }
5057           }
5058       if (visit_addr
5059           && gimple_call_chain (stmt)
5060           && TREE_CODE (gimple_call_chain (stmt)) == ADDR_EXPR)
5061         ret |= visit_addr (stmt, TREE_OPERAND (gimple_call_chain (stmt), 0),
5062                            data);
5063       if (visit_addr
5064           && gimple_call_return_slot_opt_p (stmt)
5065           && gimple_call_lhs (stmt) != NULL_TREE
5066           && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
5067         ret |= visit_addr (stmt, gimple_call_lhs (stmt), data);
5068     }
5069   else if (gimple_code (stmt) == GIMPLE_ASM)
5070     {
5071       unsigned noutputs;
5072       const char *constraint;
5073       const char **oconstraints;
5074       bool allows_mem, allows_reg, is_inout;
5075       noutputs = gimple_asm_noutputs (stmt);
5076       oconstraints = XALLOCAVEC (const char *, noutputs);
5077       if (visit_store || visit_addr)
5078         for (i = 0; i < gimple_asm_noutputs (stmt); ++i)
5079           {
5080             tree link = gimple_asm_output_op (stmt, i);
5081             tree op = get_base_loadstore (TREE_VALUE (link));
5082             if (op && visit_store)
5083               ret |= visit_store (stmt, op, data);
5084             if (visit_addr)
5085               {
5086                 constraint = TREE_STRING_POINTER
5087                     (TREE_VALUE (TREE_PURPOSE (link)));
5088                 oconstraints[i] = constraint;
5089                 parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
5090                                          &allows_reg, &is_inout);
5091                 if (op && !allows_reg && allows_mem)
5092                   ret |= visit_addr (stmt, op, data);
5093               }
5094           }
5095       if (visit_load || visit_addr)
5096         for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
5097           {
5098             tree link = gimple_asm_input_op (stmt, i);
5099             tree op = TREE_VALUE (link);
5100             if (visit_addr
5101                 && TREE_CODE (op) == ADDR_EXPR)
5102               ret |= visit_addr (stmt, TREE_OPERAND (op, 0), data);
5103             else if (visit_load || visit_addr)
5104               {
5105                 op = get_base_loadstore (op);
5106                 if (op)
5107                   {
5108                     if (visit_load)
5109                       ret |= visit_load (stmt, op, data);
5110                     if (visit_addr)
5111                       {
5112                         constraint = TREE_STRING_POINTER
5113                             (TREE_VALUE (TREE_PURPOSE (link)));
5114                         parse_input_constraint (&constraint, 0, 0, noutputs,
5115                                                 0, oconstraints,
5116                                                 &allows_mem, &allows_reg);
5117                         if (!allows_reg && allows_mem)
5118                           ret |= visit_addr (stmt, op, data);
5119                       }
5120                   }
5121               }
5122           }
5123     }
5124   else if (gimple_code (stmt) == GIMPLE_RETURN)
5125     {
5126       tree op = gimple_return_retval (stmt);
5127       if (op)
5128         {
5129           if (visit_addr
5130               && TREE_CODE (op) == ADDR_EXPR)
5131             ret |= visit_addr (stmt, TREE_OPERAND (op, 0), data);
5132           else if (visit_load)
5133             {
5134               op = get_base_loadstore (op);
5135               if (op)
5136                 ret |= visit_load (stmt, op, data);
5137             }
5138         }
5139     }
5140   else if (visit_addr
5141            && gimple_code (stmt) == GIMPLE_PHI)
5142     {
5143       for (i = 0; i < gimple_phi_num_args (stmt); ++i)
5144         {
5145           tree op = PHI_ARG_DEF (stmt, i);
5146           if (TREE_CODE (op) == ADDR_EXPR)
5147             ret |= visit_addr (stmt, TREE_OPERAND (op, 0), data);
5148         }
5149     }
5150
5151   return ret;
5152 }
5153
5154 /* Like walk_stmt_load_store_addr_ops but with NULL visit_addr.  IPA-CP
5155    should make a faster clone for this case.  */
5156
5157 bool
5158 walk_stmt_load_store_ops (gimple stmt, void *data,
5159                           bool (*visit_load)(gimple, tree, void *),
5160                           bool (*visit_store)(gimple, tree, void *))
5161 {
5162   return walk_stmt_load_store_addr_ops (stmt, data,
5163                                         visit_load, visit_store, NULL);
5164 }
5165
5166 /* Helper for gimple_ior_addresses_taken_1.  */
5167
5168 static bool
5169 gimple_ior_addresses_taken_1 (gimple stmt ATTRIBUTE_UNUSED,
5170                               tree addr, void *data)
5171 {
5172   bitmap addresses_taken = (bitmap)data;
5173   addr = get_base_address (addr);
5174   if (addr
5175       && DECL_P (addr))
5176     {
5177       bitmap_set_bit (addresses_taken, DECL_UID (addr));
5178       return true;
5179     }
5180   return false;
5181 }
5182
5183 /* Set the bit for the uid of all decls that have their address taken
5184    in STMT in the ADDRESSES_TAKEN bitmap.  Returns true if there
5185    were any in this stmt.  */
5186
5187 bool
5188 gimple_ior_addresses_taken (bitmap addresses_taken, gimple stmt)
5189 {
5190   return walk_stmt_load_store_addr_ops (stmt, addresses_taken, NULL, NULL,
5191                                         gimple_ior_addresses_taken_1);
5192 }
5193
5194
5195 /* Return a printable name for symbol DECL.  */
5196
5197 const char *
5198 gimple_decl_printable_name (tree decl, int verbosity)
5199 {
5200   if (!DECL_NAME (decl))
5201     return NULL;
5202
5203   if (DECL_ASSEMBLER_NAME_SET_P (decl))
5204     {
5205       const char *str, *mangled_str;
5206       int dmgl_opts = DMGL_NO_OPTS;
5207
5208       if (verbosity >= 2)
5209         {
5210           dmgl_opts = DMGL_VERBOSE
5211                       | DMGL_ANSI
5212                       | DMGL_GNU_V3
5213                       | DMGL_RET_POSTFIX;
5214           if (TREE_CODE (decl) == FUNCTION_DECL)
5215             dmgl_opts |= DMGL_PARAMS;
5216         }
5217
5218       mangled_str = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
5219       str = cplus_demangle_v3 (mangled_str, dmgl_opts);
5220       return (str) ? str : mangled_str;
5221     }
5222
5223   return IDENTIFIER_POINTER (DECL_NAME (decl));
5224 }
5225
5226 /* Return true when STMT is builtins call to CODE.  */
5227
5228 bool
5229 gimple_call_builtin_p (gimple stmt, enum built_in_function code)
5230 {
5231   tree fndecl;
5232   return (is_gimple_call (stmt)
5233           && (fndecl = gimple_call_fndecl (stmt)) != NULL
5234           && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
5235           && DECL_FUNCTION_CODE (fndecl) == code);
5236 }
5237
5238 /* Return true if STMT clobbers memory.  STMT is required to be a
5239    GIMPLE_ASM.  */
5240
5241 bool
5242 gimple_asm_clobbers_memory_p (const_gimple stmt)
5243 {
5244   unsigned i;
5245
5246   for (i = 0; i < gimple_asm_nclobbers (stmt); i++)
5247     {
5248       tree op = gimple_asm_clobber_op (stmt, i);
5249       if (strcmp (TREE_STRING_POINTER (TREE_VALUE (op)), "memory") == 0)
5250         return true;
5251     }
5252
5253   return false;
5254 }
5255 #include "gt-gimple.h"