gcc/gimple.c

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