gcc/gimple.c

   1 /* Gimple IR support functions.
   2
   3    Copyright 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
   4    Contributed by Aldy Hernandez <aldyh@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "target.h"
  27 #include "tree.h"
  28 #include "ggc.h"
  29 #include "hard-reg-set.h"
  30 #include "basic-block.h"
  31 #include "gimple.h"
  32 #include "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 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 /* Replace the LHS of STMT, an assignment, either a GIMPLE_ASSIGN or a
1985    GIMPLE_CALL, with NLHS, in preparation for modifying the RHS to an
1986    expression with a different value.
1987
1988    This will update any annotations (say debug bind stmts) referring
1989    to the original LHS, so that they use the RHS instead.  This is
1990    done even if NLHS and LHS are the same, for it is understood that
1991    the RHS will be modified afterwards, and NLHS will not be assigned
1992    an equivalent value.
1993
1994    Adjusting any non-annotation uses of the LHS, if needed, is a
1995    responsibility of the caller.
1996
1997    The effect of this call should be pretty much the same as that of
1998    inserting a copy of STMT before STMT, and then removing the
1999    original stmt, at which time gsi_remove() would have update
2000    annotations, but using this function saves all the inserting,
2001    copying and removing.  */
2002
2003 void
2004 gimple_replace_lhs (gimple stmt, tree nlhs)
2005 {
2006   if (MAY_HAVE_DEBUG_STMTS)
2007     {
2008       tree lhs = gimple_get_lhs (stmt);
2009
2010       gcc_assert (SSA_NAME_DEF_STMT (lhs) == stmt);
2011
2012       insert_debug_temp_for_var_def (NULL, lhs);
2013     }
2014
2015   gimple_set_lhs (stmt, nlhs);
2016 }
2017
2018 /* Return a deep copy of statement STMT.  All the operands from STMT
2019    are reallocated and copied using unshare_expr.  The DEF, USE, VDEF
2020    and VUSE operand arrays are set to empty in the new copy.  */
2021
2022 gimple
2023 gimple_copy (gimple stmt)
2024 {
2025   enum gimple_code code = gimple_code (stmt);
2026   unsigned num_ops = gimple_num_ops (stmt);
2027   gimple copy = gimple_alloc (code, num_ops);
2028   unsigned i;
2029
2030   /* Shallow copy all the fields from STMT.  */
2031   memcpy (copy, stmt, gimple_size (code));
2032
2033   /* If STMT has sub-statements, deep-copy them as well.  */
2034   if (gimple_has_substatements (stmt))
2035     {
2036       gimple_seq new_seq;
2037       tree t;
2038
2039       switch (gimple_code (stmt))
2040         {
2041         case GIMPLE_BIND:
2042           new_seq = gimple_seq_copy (gimple_bind_body (stmt));
2043           gimple_bind_set_body (copy, new_seq);
2044           gimple_bind_set_vars (copy, unshare_expr (gimple_bind_vars (stmt)));
2045           gimple_bind_set_block (copy, gimple_bind_block (stmt));
2046           break;
2047
2048         case GIMPLE_CATCH:
2049           new_seq = gimple_seq_copy (gimple_catch_handler (stmt));
2050           gimple_catch_set_handler (copy, new_seq);
2051           t = unshare_expr (gimple_catch_types (stmt));
2052           gimple_catch_set_types (copy, t);
2053           break;
2054
2055         case GIMPLE_EH_FILTER:
2056           new_seq = gimple_seq_copy (gimple_eh_filter_failure (stmt));
2057           gimple_eh_filter_set_failure (copy, new_seq);
2058           t = unshare_expr (gimple_eh_filter_types (stmt));
2059           gimple_eh_filter_set_types (copy, t);
2060           break;
2061
2062         case GIMPLE_TRY:
2063           new_seq = gimple_seq_copy (gimple_try_eval (stmt));
2064           gimple_try_set_eval (copy, new_seq);
2065           new_seq = gimple_seq_copy (gimple_try_cleanup (stmt));
2066           gimple_try_set_cleanup (copy, new_seq);
2067           break;
2068
2069         case GIMPLE_OMP_FOR:
2070           new_seq = gimple_seq_copy (gimple_omp_for_pre_body (stmt));
2071           gimple_omp_for_set_pre_body (copy, new_seq);
2072           t = unshare_expr (gimple_omp_for_clauses (stmt));
2073           gimple_omp_for_set_clauses (copy, t);
2074           copy->gimple_omp_for.iter
2075             = GGC_NEWVEC (struct gimple_omp_for_iter,
2076                           gimple_omp_for_collapse (stmt));
2077           for (i = 0; i < gimple_omp_for_collapse (stmt); i++)
2078             {
2079               gimple_omp_for_set_cond (copy, i,
2080                                        gimple_omp_for_cond (stmt, i));
2081               gimple_omp_for_set_index (copy, i,
2082                                         gimple_omp_for_index (stmt, i));
2083               t = unshare_expr (gimple_omp_for_initial (stmt, i));
2084               gimple_omp_for_set_initial (copy, i, t);
2085               t = unshare_expr (gimple_omp_for_final (stmt, i));
2086               gimple_omp_for_set_final (copy, i, t);
2087               t = unshare_expr (gimple_omp_for_incr (stmt, i));
2088               gimple_omp_for_set_incr (copy, i, t);
2089             }
2090           goto copy_omp_body;
2091
2092         case GIMPLE_OMP_PARALLEL:
2093           t = unshare_expr (gimple_omp_parallel_clauses (stmt));
2094           gimple_omp_parallel_set_clauses (copy, t);
2095           t = unshare_expr (gimple_omp_parallel_child_fn (stmt));
2096           gimple_omp_parallel_set_child_fn (copy, t);
2097           t = unshare_expr (gimple_omp_parallel_data_arg (stmt));
2098           gimple_omp_parallel_set_data_arg (copy, t);
2099           goto copy_omp_body;
2100
2101         case GIMPLE_OMP_TASK:
2102           t = unshare_expr (gimple_omp_task_clauses (stmt));
2103           gimple_omp_task_set_clauses (copy, t);
2104           t = unshare_expr (gimple_omp_task_child_fn (stmt));
2105           gimple_omp_task_set_child_fn (copy, t);
2106           t = unshare_expr (gimple_omp_task_data_arg (stmt));
2107           gimple_omp_task_set_data_arg (copy, t);
2108           t = unshare_expr (gimple_omp_task_copy_fn (stmt));
2109           gimple_omp_task_set_copy_fn (copy, t);
2110           t = unshare_expr (gimple_omp_task_arg_size (stmt));
2111           gimple_omp_task_set_arg_size (copy, t);
2112           t = unshare_expr (gimple_omp_task_arg_align (stmt));
2113           gimple_omp_task_set_arg_align (copy, t);
2114           goto copy_omp_body;
2115
2116         case GIMPLE_OMP_CRITICAL:
2117           t = unshare_expr (gimple_omp_critical_name (stmt));
2118           gimple_omp_critical_set_name (copy, t);
2119           goto copy_omp_body;
2120
2121         case GIMPLE_OMP_SECTIONS:
2122           t = unshare_expr (gimple_omp_sections_clauses (stmt));
2123           gimple_omp_sections_set_clauses (copy, t);
2124           t = unshare_expr (gimple_omp_sections_control (stmt));
2125           gimple_omp_sections_set_control (copy, t);
2126           /* FALLTHRU  */
2127
2128         case GIMPLE_OMP_SINGLE:
2129         case GIMPLE_OMP_SECTION:
2130         case GIMPLE_OMP_MASTER:
2131         case GIMPLE_OMP_ORDERED:
2132         copy_omp_body:
2133           new_seq = gimple_seq_copy (gimple_omp_body (stmt));
2134           gimple_omp_set_body (copy, new_seq);
2135           break;
2136
2137         case GIMPLE_WITH_CLEANUP_EXPR:
2138           new_seq = gimple_seq_copy (gimple_wce_cleanup (stmt));
2139           gimple_wce_set_cleanup (copy, new_seq);
2140           break;
2141
2142         default:
2143           gcc_unreachable ();
2144         }
2145     }
2146
2147   /* Make copy of operands.  */
2148   if (num_ops > 0)
2149     {
2150       for (i = 0; i < num_ops; i++)
2151         gimple_set_op (copy, i, unshare_expr (gimple_op (stmt, i)));
2152
2153       /* Clear out SSA operand vectors on COPY.  */
2154       if (gimple_has_ops (stmt))
2155         {
2156           gimple_set_def_ops (copy, NULL);
2157           gimple_set_use_ops (copy, NULL);
2158         }
2159
2160       if (gimple_has_mem_ops (stmt))
2161         {
2162           gimple_set_vdef (copy, gimple_vdef (stmt));
2163           gimple_set_vuse (copy, gimple_vuse (stmt));
2164         }
2165
2166       /* SSA operands need to be updated.  */
2167       gimple_set_modified (copy, true);
2168     }
2169
2170   return copy;
2171 }
2172
2173
2174 /* Set the MODIFIED flag to MODIFIEDP, iff the gimple statement G has
2175    a MODIFIED field.  */
2176
2177 void
2178 gimple_set_modified (gimple s, bool modifiedp)
2179 {
2180   if (gimple_has_ops (s))
2181     {
2182       s->gsbase.modified = (unsigned) modifiedp;
2183
2184       if (modifiedp
2185           && cfun->gimple_df
2186           && is_gimple_call (s)
2187           && gimple_call_noreturn_p (s))
2188         VEC_safe_push (gimple, gc, MODIFIED_NORETURN_CALLS (cfun), s);
2189     }
2190 }
2191
2192
2193 /* Return true if statement S has side-effects.  We consider a
2194    statement to have side effects if:
2195
2196    - It is a GIMPLE_CALL not marked with ECF_PURE or ECF_CONST.
2197    - Any of its operands are marked TREE_THIS_VOLATILE or TREE_SIDE_EFFECTS.  */
2198
2199 bool
2200 gimple_has_side_effects (const_gimple s)
2201 {
2202   unsigned i;
2203
2204   if (is_gimple_debug (s))
2205     return false;
2206
2207   /* We don't have to scan the arguments to check for
2208      volatile arguments, though, at present, we still
2209      do a scan to check for TREE_SIDE_EFFECTS.  */
2210   if (gimple_has_volatile_ops (s))
2211     return true;
2212
2213   if (is_gimple_call (s))
2214     {
2215       unsigned nargs = gimple_call_num_args (s);
2216
2217       if (!(gimple_call_flags (s) & (ECF_CONST | ECF_PURE)))
2218         return true;
2219       else if (gimple_call_flags (s) & ECF_LOOPING_CONST_OR_PURE)
2220         /* An infinite loop is considered a side effect.  */
2221         return true;
2222
2223       if (gimple_call_lhs (s)
2224           && TREE_SIDE_EFFECTS (gimple_call_lhs (s)))
2225         {
2226           gcc_assert (gimple_has_volatile_ops (s));
2227           return true;
2228         }
2229
2230       if (TREE_SIDE_EFFECTS (gimple_call_fn (s)))
2231         return true;
2232
2233       for (i = 0; i < nargs; i++)
2234         if (TREE_SIDE_EFFECTS (gimple_call_arg (s, i)))
2235           {
2236             gcc_assert (gimple_has_volatile_ops (s));
2237             return true;
2238           }
2239
2240       return false;
2241     }
2242   else
2243     {
2244       for (i = 0; i < gimple_num_ops (s); i++)
2245         if (TREE_SIDE_EFFECTS (gimple_op (s, i)))
2246           {
2247             gcc_assert (gimple_has_volatile_ops (s));
2248             return true;
2249           }
2250     }
2251
2252   return false;
2253 }
2254
2255 /* Return true if the RHS of statement S has side effects.
2256    We may use it to determine if it is admissable to replace
2257    an assignment or call with a copy of a previously-computed
2258    value.  In such cases, side-effects due the the LHS are
2259    preserved.  */
2260
2261 bool
2262 gimple_rhs_has_side_effects (const_gimple s)
2263 {
2264   unsigned i;
2265
2266   if (is_gimple_call (s))
2267     {
2268       unsigned nargs = gimple_call_num_args (s);
2269
2270       if (!(gimple_call_flags (s) & (ECF_CONST | ECF_PURE)))
2271         return true;
2272
2273       /* We cannot use gimple_has_volatile_ops here,
2274          because we must ignore a volatile LHS.  */
2275       if (TREE_SIDE_EFFECTS (gimple_call_fn (s))
2276           || TREE_THIS_VOLATILE (gimple_call_fn (s)))
2277         {
2278           gcc_assert (gimple_has_volatile_ops (s));
2279           return true;
2280         }
2281
2282       for (i = 0; i < nargs; i++)
2283         if (TREE_SIDE_EFFECTS (gimple_call_arg (s, i))
2284             || TREE_THIS_VOLATILE (gimple_call_arg (s, i)))
2285           return true;
2286
2287       return false;
2288     }
2289   else if (is_gimple_assign (s))
2290     {
2291       /* Skip the first operand, the LHS. */
2292       for (i = 1; i < gimple_num_ops (s); i++)
2293         if (TREE_SIDE_EFFECTS (gimple_op (s, i))
2294             || TREE_THIS_VOLATILE (gimple_op (s, i)))
2295           {
2296             gcc_assert (gimple_has_volatile_ops (s));
2297             return true;
2298           }
2299     }
2300   else if (is_gimple_debug (s))
2301     return false;
2302   else
2303     {
2304       /* For statements without an LHS, examine all arguments.  */
2305       for (i = 0; i < gimple_num_ops (s); i++)
2306         if (TREE_SIDE_EFFECTS (gimple_op (s, i))
2307             || TREE_THIS_VOLATILE (gimple_op (s, i)))
2308           {
2309             gcc_assert (gimple_has_volatile_ops (s));
2310             return true;
2311           }
2312     }
2313
2314   return false;
2315 }
2316
2317
2318 /* Helper for gimple_could_trap_p and gimple_assign_rhs_could_trap_p.
2319    Return true if S can trap.  If INCLUDE_LHS is true and S is a
2320    GIMPLE_ASSIGN, the LHS of the assignment is also checked.
2321    Otherwise, only the RHS of the assignment is checked.  */
2322
2323 static bool
2324 gimple_could_trap_p_1 (gimple s, bool include_lhs)
2325 {
2326   unsigned i, start;
2327   tree t, div = NULL_TREE;
2328   enum tree_code op;
2329
2330   start = (is_gimple_assign (s) && !include_lhs) ? 1 : 0;
2331
2332   for (i = start; i < gimple_num_ops (s); i++)
2333     if (tree_could_trap_p (gimple_op (s, i)))
2334       return true;
2335
2336   switch (gimple_code (s))
2337     {
2338     case GIMPLE_ASM:
2339       return gimple_asm_volatile_p (s);
2340
2341     case GIMPLE_CALL:
2342       t = gimple_call_fndecl (s);
2343       /* Assume that calls to weak functions may trap.  */
2344       if (!t || !DECL_P (t) || DECL_WEAK (t))
2345         return true;
2346       return false;
2347
2348     case GIMPLE_ASSIGN:
2349       t = gimple_expr_type (s);
2350       op = gimple_assign_rhs_code (s);
2351       if (get_gimple_rhs_class (op) == GIMPLE_BINARY_RHS)
2352         div = gimple_assign_rhs2 (s);
2353       return (operation_could_trap_p (op, FLOAT_TYPE_P (t),
2354                                       (INTEGRAL_TYPE_P (t)
2355                                        && TYPE_OVERFLOW_TRAPS (t)),
2356                                       div));
2357
2358     default:
2359       break;
2360     }
2361
2362   return false;
2363
2364 }
2365
2366
2367 /* Return true if statement S can trap.  */
2368
2369 bool
2370 gimple_could_trap_p (gimple s)
2371 {
2372   return gimple_could_trap_p_1 (s, true);
2373 }
2374
2375
2376 /* Return true if RHS of a GIMPLE_ASSIGN S can trap.  */
2377
2378 bool
2379 gimple_assign_rhs_could_trap_p (gimple s)
2380 {
2381   gcc_assert (is_gimple_assign (s));
2382   return gimple_could_trap_p_1 (s, false);
2383 }
2384
2385
2386 /* Print debugging information for gimple stmts generated.  */
2387
2388 void
2389 dump_gimple_statistics (void)
2390 {
2391 #ifdef GATHER_STATISTICS
2392   int i, total_tuples = 0, total_bytes = 0;
2393
2394   fprintf (stderr, "\nGIMPLE statements\n");
2395   fprintf (stderr, "Kind                   Stmts      Bytes\n");
2396   fprintf (stderr, "---------------------------------------\n");
2397   for (i = 0; i < (int) gimple_alloc_kind_all; ++i)
2398     {
2399       fprintf (stderr, "%-20s %7d %10d\n", gimple_alloc_kind_names[i],
2400           gimple_alloc_counts[i], gimple_alloc_sizes[i]);
2401       total_tuples += gimple_alloc_counts[i];
2402       total_bytes += gimple_alloc_sizes[i];
2403     }
2404   fprintf (stderr, "---------------------------------------\n");
2405   fprintf (stderr, "%-20s %7d %10d\n", "Total", total_tuples, total_bytes);
2406   fprintf (stderr, "---------------------------------------\n");
2407 #else
2408   fprintf (stderr, "No gimple statistics\n");
2409 #endif
2410 }
2411
2412
2413 /* Return the number of operands needed on the RHS of a GIMPLE
2414    assignment for an expression with tree code CODE.  */
2415
2416 unsigned
2417 get_gimple_rhs_num_ops (enum tree_code code)
2418 {
2419   enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code);
2420
2421   if (rhs_class == GIMPLE_UNARY_RHS || rhs_class == GIMPLE_SINGLE_RHS)
2422     return 1;
2423   else if (rhs_class == GIMPLE_BINARY_RHS)
2424     return 2;
2425   else
2426     gcc_unreachable ();
2427 }
2428
2429 #define DEFTREECODE(SYM, STRING, TYPE, NARGS)                               \
2430   (unsigned char)                                                           \
2431   ((TYPE) == tcc_unary ? GIMPLE_UNARY_RHS                                   \
2432    : ((TYPE) == tcc_binary                                                  \
2433       || (TYPE) == tcc_comparison) ? GIMPLE_BINARY_RHS                      \
2434    : ((TYPE) == tcc_constant                                                \
2435       || (TYPE) == tcc_declaration                                          \
2436       || (TYPE) == tcc_reference) ? GIMPLE_SINGLE_RHS                       \
2437    : ((SYM) == TRUTH_AND_EXPR                                               \
2438       || (SYM) == TRUTH_OR_EXPR                                             \
2439       || (SYM) == TRUTH_XOR_EXPR) ? GIMPLE_BINARY_RHS                       \
2440    : (SYM) == TRUTH_NOT_EXPR ? GIMPLE_UNARY_RHS                             \
2441    : ((SYM) == COND_EXPR                                                    \
2442       || (SYM) == CONSTRUCTOR                                               \
2443       || (SYM) == OBJ_TYPE_REF                                              \
2444       || (SYM) == ASSERT_EXPR                                               \
2445       || (SYM) == ADDR_EXPR                                                 \
2446       || (SYM) == WITH_SIZE_EXPR                                            \
2447       || (SYM) == SSA_NAME                                                  \
2448       || (SYM) == POLYNOMIAL_CHREC                                          \
2449       || (SYM) == DOT_PROD_EXPR                                             \
2450       || (SYM) == VEC_COND_EXPR                                             \
2451       || (SYM) == REALIGN_LOAD_EXPR) ? GIMPLE_SINGLE_RHS                    \
2452    : GIMPLE_INVALID_RHS),
2453 #define END_OF_BASE_TREE_CODES (unsigned char) GIMPLE_INVALID_RHS,
2454
2455 const unsigned char gimple_rhs_class_table[] = {
2456 #include "all-tree.def"
2457 };
2458
2459 #undef DEFTREECODE
2460 #undef END_OF_BASE_TREE_CODES
2461
2462 /* For the definitive definition of GIMPLE, see doc/tree-ssa.texi.  */
2463
2464 /* Validation of GIMPLE expressions.  */
2465
2466 /* Return true if OP is an acceptable tree node to be used as a GIMPLE
2467    operand.  */
2468
2469 bool
2470 is_gimple_operand (const_tree op)
2471 {
2472   return op && get_gimple_rhs_class (TREE_CODE (op)) == GIMPLE_SINGLE_RHS;
2473 }
2474
2475 /* Returns true iff T is a valid RHS for an assignment to a renamed
2476    user -- or front-end generated artificial -- variable.  */
2477
2478 bool
2479 is_gimple_reg_rhs (tree t)
2480 {
2481   return get_gimple_rhs_class (TREE_CODE (t)) != GIMPLE_INVALID_RHS;
2482 }
2483
2484 /* Returns true iff T is a valid RHS for an assignment to an un-renamed
2485    LHS, or for a call argument.  */
2486
2487 bool
2488 is_gimple_mem_rhs (tree t)
2489 {
2490   /* If we're dealing with a renamable type, either source or dest must be
2491      a renamed variable.  */
2492   if (is_gimple_reg_type (TREE_TYPE (t)))
2493     return is_gimple_val (t);
2494   else
2495     return is_gimple_val (t) || is_gimple_lvalue (t);
2496 }
2497
2498 /*  Return true if T is a valid LHS for a GIMPLE assignment expression.  */
2499
2500 bool
2501 is_gimple_lvalue (tree t)
2502 {
2503   return (is_gimple_addressable (t)
2504           || TREE_CODE (t) == WITH_SIZE_EXPR
2505           /* These are complex lvalues, but don't have addresses, so they
2506              go here.  */
2507           || TREE_CODE (t) == BIT_FIELD_REF);
2508 }
2509
2510 /*  Return true if T is a GIMPLE condition.  */
2511
2512 bool
2513 is_gimple_condexpr (tree t)
2514 {
2515   return (is_gimple_val (t) || (COMPARISON_CLASS_P (t)
2516                                 && !tree_could_trap_p (t)
2517                                 && is_gimple_val (TREE_OPERAND (t, 0))
2518                                 && is_gimple_val (TREE_OPERAND (t, 1))));
2519 }
2520
2521 /*  Return true if T is something whose address can be taken.  */
2522
2523 bool
2524 is_gimple_addressable (tree t)
2525 {
2526   return (is_gimple_id (t) || handled_component_p (t) || INDIRECT_REF_P (t));
2527 }
2528
2529 /* Return true if T is a valid gimple constant.  */
2530
2531 bool
2532 is_gimple_constant (const_tree t)
2533 {
2534   switch (TREE_CODE (t))
2535     {
2536     case INTEGER_CST:
2537     case REAL_CST:
2538     case FIXED_CST:
2539     case STRING_CST:
2540     case COMPLEX_CST:
2541     case VECTOR_CST:
2542       return true;
2543
2544     /* Vector constant constructors are gimple invariant.  */
2545     case CONSTRUCTOR:
2546       if (TREE_TYPE (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2547         return TREE_CONSTANT (t);
2548       else
2549         return false;
2550
2551     default:
2552       return false;
2553     }
2554 }
2555
2556 /* Return true if T is a gimple address.  */
2557
2558 bool
2559 is_gimple_address (const_tree t)
2560 {
2561   tree op;
2562
2563   if (TREE_CODE (t) != ADDR_EXPR)
2564     return false;
2565
2566   op = TREE_OPERAND (t, 0);
2567   while (handled_component_p (op))
2568     {
2569       if ((TREE_CODE (op) == ARRAY_REF
2570            || TREE_CODE (op) == ARRAY_RANGE_REF)
2571           && !is_gimple_val (TREE_OPERAND (op, 1)))
2572             return false;
2573
2574       op = TREE_OPERAND (op, 0);
2575     }
2576
2577   if (CONSTANT_CLASS_P (op) || INDIRECT_REF_P (op))
2578     return true;
2579
2580   switch (TREE_CODE (op))
2581     {
2582     case PARM_DECL:
2583     case RESULT_DECL:
2584     case LABEL_DECL:
2585     case FUNCTION_DECL:
2586     case VAR_DECL:
2587     case CONST_DECL:
2588       return true;
2589
2590     default:
2591       return false;
2592     }
2593 }
2594
2595 /* Strip out all handled components that produce invariant
2596    offsets.  */
2597
2598 static const_tree
2599 strip_invariant_refs (const_tree op)
2600 {
2601   while (handled_component_p (op))
2602     {
2603       switch (TREE_CODE (op))
2604         {
2605         case ARRAY_REF:
2606         case ARRAY_RANGE_REF:
2607           if (!is_gimple_constant (TREE_OPERAND (op, 1))
2608               || TREE_OPERAND (op, 2) != NULL_TREE
2609               || TREE_OPERAND (op, 3) != NULL_TREE)
2610             return NULL;
2611           break;
2612
2613         case COMPONENT_REF:
2614           if (TREE_OPERAND (op, 2) != NULL_TREE)
2615             return NULL;
2616           break;
2617
2618         default:;
2619         }
2620       op = TREE_OPERAND (op, 0);
2621     }
2622
2623   return op;
2624 }
2625
2626 /* Return true if T is a gimple invariant address.  */
2627
2628 bool
2629 is_gimple_invariant_address (const_tree t)
2630 {
2631   const_tree op;
2632
2633   if (TREE_CODE (t) != ADDR_EXPR)
2634     return false;
2635
2636   op = strip_invariant_refs (TREE_OPERAND (t, 0));
2637
2638   return op && (CONSTANT_CLASS_P (op) || decl_address_invariant_p (op));
2639 }
2640
2641 /* Return true if T is a gimple invariant address at IPA level
2642    (so addresses of variables on stack are not allowed).  */
2643
2644 bool
2645 is_gimple_ip_invariant_address (const_tree t)
2646 {
2647   const_tree op;
2648
2649   if (TREE_CODE (t) != ADDR_EXPR)
2650     return false;
2651
2652   op = strip_invariant_refs (TREE_OPERAND (t, 0));
2653
2654   return op && (CONSTANT_CLASS_P (op) || decl_address_ip_invariant_p (op));
2655 }
2656
2657 /* Return true if T is a GIMPLE minimal invariant.  It's a restricted
2658    form of function invariant.  */
2659
2660 bool
2661 is_gimple_min_invariant (const_tree t)
2662 {
2663   if (TREE_CODE (t) == ADDR_EXPR)
2664     return is_gimple_invariant_address (t);
2665
2666   return is_gimple_constant (t);
2667 }
2668
2669 /* Return true if T is a GIMPLE interprocedural invariant.  It's a restricted
2670    form of gimple minimal invariant.  */
2671
2672 bool
2673 is_gimple_ip_invariant (const_tree t)
2674 {
2675   if (TREE_CODE (t) == ADDR_EXPR)
2676     return is_gimple_ip_invariant_address (t);
2677
2678   return is_gimple_constant (t);
2679 }
2680
2681 /* Return true if T looks like a valid GIMPLE statement.  */
2682
2683 bool
2684 is_gimple_stmt (tree t)
2685 {
2686   const enum tree_code code = TREE_CODE (t);
2687
2688   switch (code)
2689     {
2690     case NOP_EXPR:
2691       /* The only valid NOP_EXPR is the empty statement.  */
2692       return IS_EMPTY_STMT (t);
2693
2694     case BIND_EXPR:
2695     case COND_EXPR:
2696       /* These are only valid if they're void.  */
2697       return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
2698
2699     case SWITCH_EXPR:
2700     case GOTO_EXPR:
2701     case RETURN_EXPR:
2702     case LABEL_EXPR:
2703     case CASE_LABEL_EXPR:
2704     case TRY_CATCH_EXPR:
2705     case TRY_FINALLY_EXPR:
2706     case EH_FILTER_EXPR:
2707     case CATCH_EXPR:
2708     case ASM_EXPR:
2709     case STATEMENT_LIST:
2710     case OMP_PARALLEL:
2711     case OMP_FOR:
2712     case OMP_SECTIONS:
2713     case OMP_SECTION:
2714     case OMP_SINGLE:
2715     case OMP_MASTER:
2716     case OMP_ORDERED:
2717     case OMP_CRITICAL:
2718     case OMP_TASK:
2719       /* These are always void.  */
2720       return true;
2721
2722     case CALL_EXPR:
2723     case MODIFY_EXPR:
2724     case PREDICT_EXPR:
2725       /* These are valid regardless of their type.  */
2726       return true;
2727
2728     default:
2729       return false;
2730     }
2731 }
2732
2733 /* Return true if T is a variable.  */
2734
2735 bool
2736 is_gimple_variable (tree t)
2737 {
2738   return (TREE_CODE (t) == VAR_DECL
2739           || TREE_CODE (t) == PARM_DECL
2740           || TREE_CODE (t) == RESULT_DECL
2741           || TREE_CODE (t) == SSA_NAME);
2742 }
2743
2744 /*  Return true if T is a GIMPLE identifier (something with an address).  */
2745
2746 bool
2747 is_gimple_id (tree t)
2748 {
2749   return (is_gimple_variable (t)
2750           || TREE_CODE (t) == FUNCTION_DECL
2751           || TREE_CODE (t) == LABEL_DECL
2752           || TREE_CODE (t) == CONST_DECL
2753           /* Allow string constants, since they are addressable.  */
2754           || TREE_CODE (t) == STRING_CST);
2755 }
2756
2757 /* Return true if TYPE is a suitable type for a scalar register variable.  */
2758
2759 bool
2760 is_gimple_reg_type (tree type)
2761 {
2762   return !AGGREGATE_TYPE_P (type);
2763 }
2764
2765 /* Return true if T is a non-aggregate register variable.  */
2766
2767 bool
2768 is_gimple_reg (tree t)
2769 {
2770   if (TREE_CODE (t) == SSA_NAME)
2771     t = SSA_NAME_VAR (t);
2772
2773   if (!is_gimple_variable (t))
2774     return false;
2775
2776   if (!is_gimple_reg_type (TREE_TYPE (t)))
2777     return false;
2778
2779   /* A volatile decl is not acceptable because we can't reuse it as
2780      needed.  We need to copy it into a temp first.  */
2781   if (TREE_THIS_VOLATILE (t))
2782     return false;
2783
2784   /* We define "registers" as things that can be renamed as needed,
2785      which with our infrastructure does not apply to memory.  */
2786   if (needs_to_live_in_memory (t))
2787     return false;
2788
2789   /* Hard register variables are an interesting case.  For those that
2790      are call-clobbered, we don't know where all the calls are, since
2791      we don't (want to) take into account which operations will turn
2792      into libcalls at the rtl level.  For those that are call-saved,
2793      we don't currently model the fact that calls may in fact change
2794      global hard registers, nor do we examine ASM_CLOBBERS at the tree
2795      level, and so miss variable changes that might imply.  All around,
2796      it seems safest to not do too much optimization with these at the
2797      tree level at all.  We'll have to rely on the rtl optimizers to
2798      clean this up, as there we've got all the appropriate bits exposed.  */
2799   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
2800     return false;
2801
2802   /* Complex and vector values must have been put into SSA-like form.
2803      That is, no assignments to the individual components.  */
2804   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
2805       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2806     return DECL_GIMPLE_REG_P (t);
2807
2808   return true;
2809 }
2810
2811
2812 /* Return true if T is a GIMPLE variable whose address is not needed.  */
2813
2814 bool
2815 is_gimple_non_addressable (tree t)
2816 {
2817   if (TREE_CODE (t) == SSA_NAME)
2818     t = SSA_NAME_VAR (t);
2819
2820   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
2821 }
2822
2823 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
2824
2825 bool
2826 is_gimple_val (tree t)
2827 {
2828   /* Make loads from volatiles and memory vars explicit.  */
2829   if (is_gimple_variable (t)
2830       && is_gimple_reg_type (TREE_TYPE (t))
2831       && !is_gimple_reg (t))
2832     return false;
2833
2834   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
2835 }
2836
2837 /* Similarly, but accept hard registers as inputs to asm statements.  */
2838
2839 bool
2840 is_gimple_asm_val (tree t)
2841 {
2842   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
2843     return true;
2844
2845   return is_gimple_val (t);
2846 }
2847
2848 /* Return true if T is a GIMPLE minimal lvalue.  */
2849
2850 bool
2851 is_gimple_min_lval (tree t)
2852 {
2853   if (!(t = CONST_CAST_TREE (strip_invariant_refs (t))))
2854     return false;
2855   return (is_gimple_id (t) || TREE_CODE (t) == INDIRECT_REF);
2856 }
2857
2858 /* Return true if T is a typecast operation.  */
2859
2860 bool
2861 is_gimple_cast (tree t)
2862 {
2863   return (CONVERT_EXPR_P (t)
2864           || TREE_CODE (t) == FIX_TRUNC_EXPR);
2865 }
2866
2867 /* Return true if T is a valid function operand of a CALL_EXPR.  */
2868
2869 bool
2870 is_gimple_call_addr (tree t)
2871 {
2872   return (TREE_CODE (t) == OBJ_TYPE_REF || is_gimple_val (t));
2873 }
2874
2875 /* If T makes a function call, return the corresponding CALL_EXPR operand.
2876    Otherwise, return NULL_TREE.  */
2877
2878 tree
2879 get_call_expr_in (tree t)
2880 {
2881   if (TREE_CODE (t) == MODIFY_EXPR)
2882     t = TREE_OPERAND (t, 1);
2883   if (TREE_CODE (t) == WITH_SIZE_EXPR)
2884     t = TREE_OPERAND (t, 0);
2885   if (TREE_CODE (t) == CALL_EXPR)
2886     return t;
2887   return NULL_TREE;
2888 }
2889
2890
2891 /* Given a memory reference expression T, return its base address.
2892    The base address of a memory reference expression is the main
2893    object being referenced.  For instance, the base address for
2894    'array[i].fld[j]' is 'array'.  You can think of this as stripping
2895    away the offset part from a memory address.
2896
2897    This function calls handled_component_p to strip away all the inner
2898    parts of the memory reference until it reaches the base object.  */
2899
2900 tree
2901 get_base_address (tree t)
2902 {
2903   while (handled_component_p (t))
2904     t = TREE_OPERAND (t, 0);
2905
2906   if (SSA_VAR_P (t)
2907       || TREE_CODE (t) == STRING_CST
2908       || TREE_CODE (t) == CONSTRUCTOR
2909       || INDIRECT_REF_P (t))
2910     return t;
2911   else
2912     return NULL_TREE;
2913 }
2914
2915 void
2916 recalculate_side_effects (tree t)
2917 {
2918   enum tree_code code = TREE_CODE (t);
2919   int len = TREE_OPERAND_LENGTH (t);
2920   int i;
2921
2922   switch (TREE_CODE_CLASS (code))
2923     {
2924     case tcc_expression:
2925       switch (code)
2926         {
2927         case INIT_EXPR:
2928         case MODIFY_EXPR:
2929         case VA_ARG_EXPR:
2930         case PREDECREMENT_EXPR:
2931         case PREINCREMENT_EXPR:
2932         case POSTDECREMENT_EXPR:
2933         case POSTINCREMENT_EXPR:
2934           /* All of these have side-effects, no matter what their
2935              operands are.  */
2936           return;
2937
2938         default:
2939           break;
2940         }
2941       /* Fall through.  */
2942
2943     case tcc_comparison:  /* a comparison expression */
2944     case tcc_unary:       /* a unary arithmetic expression */
2945     case tcc_binary:      /* a binary arithmetic expression */
2946     case tcc_reference:   /* a reference */
2947     case tcc_vl_exp:        /* a function call */
2948       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
2949       for (i = 0; i < len; ++i)
2950         {
2951           tree op = TREE_OPERAND (t, i);
2952           if (op && TREE_SIDE_EFFECTS (op))
2953             TREE_SIDE_EFFECTS (t) = 1;
2954         }
2955       break;
2956
2957     case tcc_constant:
2958       /* No side-effects.  */
2959       return;
2960
2961     default:
2962       gcc_unreachable ();
2963    }
2964 }
2965
2966 /* Canonicalize a tree T for use in a COND_EXPR as conditional.  Returns
2967    a canonicalized tree that is valid for a COND_EXPR or NULL_TREE, if
2968    we failed to create one.  */
2969
2970 tree
2971 canonicalize_cond_expr_cond (tree t)
2972 {
2973   /* Strip conversions around boolean operations.  */
2974   if (CONVERT_EXPR_P (t)
2975       && truth_value_p (TREE_CODE (TREE_OPERAND (t, 0))))
2976     t = TREE_OPERAND (t, 0);
2977
2978   /* For (bool)x use x != 0.  */
2979   if (CONVERT_EXPR_P (t)
2980       && TREE_CODE (TREE_TYPE (t)) == BOOLEAN_TYPE)
2981     {
2982       tree top0 = TREE_OPERAND (t, 0);
2983       t = build2 (NE_EXPR, TREE_TYPE (t),
2984                   top0, build_int_cst (TREE_TYPE (top0), 0));
2985     }
2986   /* For !x use x == 0.  */
2987   else if (TREE_CODE (t) == TRUTH_NOT_EXPR)
2988     {
2989       tree top0 = TREE_OPERAND (t, 0);
2990       t = build2 (EQ_EXPR, TREE_TYPE (t),
2991                   top0, build_int_cst (TREE_TYPE (top0), 0));
2992     }
2993   /* For cmp ? 1 : 0 use cmp.  */
2994   else if (TREE_CODE (t) == COND_EXPR
2995            && COMPARISON_CLASS_P (TREE_OPERAND (t, 0))
2996            && integer_onep (TREE_OPERAND (t, 1))
2997            && integer_zerop (TREE_OPERAND (t, 2)))
2998     {
2999       tree top0 = TREE_OPERAND (t, 0);
3000       t = build2 (TREE_CODE (top0), TREE_TYPE (t),
3001                   TREE_OPERAND (top0, 0), TREE_OPERAND (top0, 1));
3002     }
3003
3004   if (is_gimple_condexpr (t))
3005     return t;
3006
3007   return NULL_TREE;
3008 }
3009
3010 /* Build a GIMPLE_CALL identical to STMT but skipping the arguments in
3011    the positions marked by the set ARGS_TO_SKIP.  */
3012
3013 gimple
3014 gimple_call_copy_skip_args (gimple stmt, bitmap args_to_skip)
3015 {
3016   int i;
3017   tree fn = gimple_call_fn (stmt);
3018   int nargs = gimple_call_num_args (stmt);
3019   VEC(tree, heap) *vargs = VEC_alloc (tree, heap, nargs);
3020   gimple new_stmt;
3021
3022   for (i = 0; i < nargs; i++)
3023     if (!bitmap_bit_p (args_to_skip, i))
3024       VEC_quick_push (tree, vargs, gimple_call_arg (stmt, i));
3025
3026   new_stmt = gimple_build_call_vec (fn, vargs);
3027   VEC_free (tree, heap, vargs);
3028   if (gimple_call_lhs (stmt))
3029     gimple_call_set_lhs (new_stmt, gimple_call_lhs (stmt));
3030
3031   gimple_set_vuse (new_stmt, gimple_vuse (stmt));
3032   gimple_set_vdef (new_stmt, gimple_vdef (stmt));
3033
3034   gimple_set_block (new_stmt, gimple_block (stmt));
3035   if (gimple_has_location (stmt))
3036     gimple_set_location (new_stmt, gimple_location (stmt));
3037
3038   /* Carry all the flags to the new GIMPLE_CALL.  */
3039   gimple_call_set_chain (new_stmt, gimple_call_chain (stmt));
3040   gimple_call_set_tail (new_stmt, gimple_call_tail_p (stmt));
3041   gimple_call_set_cannot_inline (new_stmt, gimple_call_cannot_inline_p (stmt));
3042   gimple_call_set_return_slot_opt (new_stmt, gimple_call_return_slot_opt_p (stmt));
3043   gimple_call_set_from_thunk (new_stmt, gimple_call_from_thunk_p (stmt));
3044   gimple_call_set_va_arg_pack (new_stmt, gimple_call_va_arg_pack_p (stmt));
3045
3046   gimple_set_modified (new_stmt, true);
3047
3048   return new_stmt;
3049 }
3050
3051
3052 static hashval_t gimple_type_hash (const void *);
3053
3054 /* Structure used to maintain a cache of some type pairs compared by
3055    gimple_types_compatible_p when comparing aggregate types.  There are
3056    four possible values for SAME_P:
3057
3058         -2: The pair (T1, T2) has just been inserted in the table.
3059         -1: The pair (T1, T2) is currently being compared.
3060          0: T1 and T2 are different types.
3061          1: T1 and T2 are the same type.
3062
3063    This table is only used when comparing aggregate types to avoid
3064    infinite recursion due to self-referential types.  */
3065 struct type_pair_d
3066 {
3067   unsigned int uid1;
3068   unsigned int uid2;
3069   int same_p;
3070 };
3071 typedef struct type_pair_d *type_pair_t;
3072
3073 /* Return a hash value for the type pair pointed-to by P.  */
3074
3075 static hashval_t
3076 type_pair_hash (const void *p)
3077 {
3078   const struct type_pair_d *pair = (const struct type_pair_d *) p;
3079   hashval_t val1 = pair->uid1;
3080   hashval_t val2 = pair->uid2;
3081   return (iterative_hash_hashval_t (val2, val1)
3082           ^ iterative_hash_hashval_t (val1, val2));
3083 }
3084
3085 /* Compare two type pairs pointed-to by P1 and P2.  */
3086
3087 static int
3088 type_pair_eq (const void *p1, const void *p2)
3089 {
3090   const struct type_pair_d *pair1 = (const struct type_pair_d *) p1;
3091   const struct type_pair_d *pair2 = (const struct type_pair_d *) p2;
3092   return ((pair1->uid1 == pair2->uid1 && pair1->uid2 == pair2->uid2)
3093           || (pair1->uid1 == pair2->uid2 && pair1->uid2 == pair2->uid1));
3094 }
3095
3096 /* Lookup the pair of types T1 and T2 in *VISITED_P.  Insert a new
3097    entry if none existed.  */
3098
3099 static type_pair_t
3100 lookup_type_pair (tree t1, tree t2, htab_t *visited_p, struct obstack *ob_p)
3101 {
3102   struct type_pair_d pair;
3103   type_pair_t p;
3104   void **slot;
3105
3106   if (*visited_p == NULL)
3107     {
3108       *visited_p = htab_create (251, type_pair_hash, type_pair_eq, NULL);
3109       gcc_obstack_init (ob_p);
3110     }
3111
3112   pair.uid1 = TYPE_UID (t1);
3113   pair.uid2 = TYPE_UID (t2);
3114   slot = htab_find_slot (*visited_p, &pair, INSERT);
3115
3116   if (*slot)
3117     p = *((type_pair_t *) slot);
3118   else
3119     {
3120       p = XOBNEW (ob_p, struct type_pair_d);
3121       p->uid1 = TYPE_UID (t1);
3122       p->uid2 = TYPE_UID (t2);
3123       p->same_p = -2;
3124       *slot = (void *) p;
3125     }
3126
3127   return p;
3128 }
3129
3130
3131 /* Return true if T1 and T2 have the same name.  If FOR_COMPLETION_P is
3132    true then if any type has no name return false, otherwise return
3133    true if both types have no names.  */
3134
3135 static bool
3136 compare_type_names_p (tree t1, tree t2, bool for_completion_p)
3137 {
3138   tree name1 = TYPE_NAME (t1);
3139   tree name2 = TYPE_NAME (t2);
3140
3141   /* Consider anonymous types all unique for completion.  */
3142   if (for_completion_p
3143       && (!name1 || !name2))
3144     return false;
3145
3146   if (name1 && TREE_CODE (name1) == TYPE_DECL)
3147     {
3148       name1 = DECL_NAME (name1);
3149       if (for_completion_p
3150           && !name1)
3151         return false;
3152     }
3153   gcc_assert (!name1 || TREE_CODE (name1) == IDENTIFIER_NODE);
3154
3155   if (name2 && TREE_CODE (name2) == TYPE_DECL)
3156     {
3157       name2 = DECL_NAME (name2);
3158       if (for_completion_p
3159           && !name2)
3160         return false;
3161     }
3162   gcc_assert (!name2 || TREE_CODE (name2) == IDENTIFIER_NODE);
3163
3164   /* Identifiers can be compared with pointer equality rather
3165      than a string comparison.  */
3166   if (name1 == name2)
3167     return true;
3168
3169   return false;
3170 }
3171
3172 /* Return true if the field decls F1 and F2 are at the same offset.  */
3173
3174 bool
3175 compare_field_offset (tree f1, tree f2)
3176 {
3177   if (DECL_OFFSET_ALIGN (f1) == DECL_OFFSET_ALIGN (f2))
3178     return (operand_equal_p (DECL_FIELD_OFFSET (f1),
3179                              DECL_FIELD_OFFSET (f2), 0)
3180             && tree_int_cst_equal (DECL_FIELD_BIT_OFFSET (f1),
3181                                    DECL_FIELD_BIT_OFFSET (f2)));
3182
3183   /* Fortran and C do not always agree on what DECL_OFFSET_ALIGN
3184      should be, so handle differing ones specially by decomposing
3185      the offset into a byte and bit offset manually.  */
3186   if (host_integerp (DECL_FIELD_OFFSET (f1), 0)
3187       && host_integerp (DECL_FIELD_OFFSET (f2), 0))
3188     {
3189       unsigned HOST_WIDE_INT byte_offset1, byte_offset2;
3190       unsigned HOST_WIDE_INT bit_offset1, bit_offset2;
3191       bit_offset1 = TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (f1));
3192       byte_offset1 = (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (f1))
3193                       + bit_offset1 / BITS_PER_UNIT);
3194       bit_offset2 = TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (f2));
3195       byte_offset2 = (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (f2))
3196                       + bit_offset2 / BITS_PER_UNIT);
3197       if (byte_offset1 != byte_offset2)
3198         return false;
3199       return bit_offset1 % BITS_PER_UNIT == bit_offset2 % BITS_PER_UNIT;
3200     }
3201
3202   return false;
3203 }
3204
3205 /* Return 1 iff T1 and T2 are structurally identical.
3206    Otherwise, return 0.  */
3207
3208 static int
3209 gimple_types_compatible_p (tree t1, tree t2)
3210 {
3211   type_pair_t p = NULL;
3212
3213   /* Check first for the obvious case of pointer identity.  */
3214   if (t1 == t2)
3215     return 1;
3216
3217   /* Check that we have two types to compare.  */
3218   if (t1 == NULL_TREE || t2 == NULL_TREE)
3219     return 0;
3220
3221   /* Can't be the same type if the types don't have the same code.  */
3222   if (TREE_CODE (t1) != TREE_CODE (t2))
3223     return 0;
3224
3225   /* Can't be the same type if they have different CV qualifiers.  */
3226   if (TYPE_QUALS (t1) != TYPE_QUALS (t2))
3227     return 0;
3228
3229   /* Void types are always the same.  */
3230   if (TREE_CODE (t1) == VOID_TYPE)
3231     return 1;
3232
3233   /* For numerical types do some simple checks before doing three
3234      hashtable queries.  */
3235   if (INTEGRAL_TYPE_P (t1)
3236       || SCALAR_FLOAT_TYPE_P (t1)
3237       || FIXED_POINT_TYPE_P (t1)
3238       || TREE_CODE (t1) == VECTOR_TYPE
3239       || TREE_CODE (t1) == COMPLEX_TYPE
3240       || TREE_CODE (t1) == OFFSET_TYPE)
3241     {
3242       /* Can't be the same type if they have different alignment,
3243          sign, precision or mode.  */
3244       if (TYPE_ALIGN (t1) != TYPE_ALIGN (t2)
3245           || TYPE_PRECISION (t1) != TYPE_PRECISION (t2)
3246           || TYPE_MODE (t1) != TYPE_MODE (t2)
3247           || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
3248         return 0;
3249
3250       if (TREE_CODE (t1) == INTEGER_TYPE
3251           && (TYPE_IS_SIZETYPE (t1) != TYPE_IS_SIZETYPE (t2)
3252               || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)))
3253         return 0;
3254
3255       /* That's all we need to check for float and fixed-point types.  */
3256       if (SCALAR_FLOAT_TYPE_P (t1)
3257           || FIXED_POINT_TYPE_P (t1))
3258         return 1;
3259
3260       /* Perform cheap tail-recursion for vector and complex types.  */
3261       if (TREE_CODE (t1) == VECTOR_TYPE
3262           || TREE_CODE (t1) == COMPLEX_TYPE)
3263         return gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2));
3264
3265       /* For integral types fall thru to more complex checks.  */
3266     }
3267
3268   /* If the hash values of t1 and t2 are different the types can't
3269      possibly be the same.  This helps keeping the type-pair hashtable
3270      small, only tracking comparisons for hash collisions.  */
3271   if (gimple_type_hash (t1) != gimple_type_hash (t2))
3272     return 0;
3273
3274   /* If we've visited this type pair before (in the case of aggregates
3275      with self-referential types), and we made a decision, return it.  */
3276   p = lookup_type_pair (t1, t2, &gtc_visited, &gtc_ob);
3277   if (p->same_p == 0 || p->same_p == 1)
3278     {
3279       /* We have already decided whether T1 and T2 are the
3280          same, return the cached result.  */
3281       return p->same_p == 1;
3282     }
3283   else if (p->same_p == -1)
3284     {
3285       /* We are currently comparing this pair of types, assume
3286          that they are the same and let the caller decide.  */
3287       return 1;
3288     }
3289
3290   gcc_assert (p->same_p == -2);
3291
3292   /* Mark the (T1, T2) comparison in progress.  */
3293   p->same_p = -1;
3294
3295   /* If their attributes are not the same they can't be the same type.  */
3296   if (!attribute_list_equal (TYPE_ATTRIBUTES (t1), TYPE_ATTRIBUTES (t2)))
3297     goto different_types;
3298
3299   /* Do type-specific comparisons.  */
3300   switch (TREE_CODE (t1))
3301     {
3302     case ARRAY_TYPE:
3303       /* Array types are the same if the element types are the same and
3304          the number of elements are the same.  */
3305       if (!gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2))
3306           || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)
3307           || TYPE_NONALIASED_COMPONENT (t1) != TYPE_NONALIASED_COMPONENT (t2))
3308         goto different_types;
3309       else
3310         {
3311           tree i1 = TYPE_DOMAIN (t1);
3312           tree i2 = TYPE_DOMAIN (t2);
3313
3314           /* For an incomplete external array, the type domain can be
3315              NULL_TREE.  Check this condition also.  */
3316           if (i1 == NULL_TREE && i2 == NULL_TREE)
3317             goto same_types;
3318           else if (i1 == NULL_TREE || i2 == NULL_TREE)
3319             goto different_types;
3320           /* If for a complete array type the possibly gimplified sizes
3321              are different the types are different.  */
3322           else if (((TYPE_SIZE (i1) != NULL) ^ (TYPE_SIZE (i2) != NULL))
3323                    || (TYPE_SIZE (i1)
3324                        && TYPE_SIZE (i2)
3325                        && !operand_equal_p (TYPE_SIZE (i1), TYPE_SIZE (i2), 0)))
3326             goto different_types;
3327           else
3328             {
3329               tree min1 = TYPE_MIN_VALUE (i1);
3330               tree min2 = TYPE_MIN_VALUE (i2);
3331               tree max1 = TYPE_MAX_VALUE (i1);
3332               tree max2 = TYPE_MAX_VALUE (i2);
3333
3334               /* The minimum/maximum values have to be the same.  */
3335               if ((min1 == min2
3336                    || (min1 && min2 && operand_equal_p (min1, min2, 0)))
3337                   && (max1 == max2
3338                       || (max1 && max2 && operand_equal_p (max1, max2, 0))))
3339                 goto same_types;
3340               else
3341                 goto different_types;
3342             }
3343         }
3344
3345     case METHOD_TYPE:
3346       /* Method types should belong to the same class.  */
3347       if (!gimple_types_compatible_p (TYPE_METHOD_BASETYPE (t1),
3348                                  TYPE_METHOD_BASETYPE (t2)))
3349         goto different_types;
3350
3351       /* Fallthru  */
3352
3353     case FUNCTION_TYPE:
3354       /* Function types are the same if the return type and arguments types
3355          are the same.  */
3356       if (!gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2)))
3357         goto different_types;
3358       else
3359         {
3360           if (!targetm.comp_type_attributes (t1, t2))
3361             goto different_types;
3362
3363           if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2))
3364             goto same_types;
3365           else
3366             {
3367               tree parms1, parms2;
3368
3369               for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
3370                    parms1 && parms2;
3371                    parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
3372                 {
3373                   if (!gimple_types_compatible_p (TREE_VALUE (parms1),
3374                                              TREE_VALUE (parms2)))
3375                     goto different_types;
3376                 }
3377
3378               if (parms1 || parms2)
3379                 goto different_types;
3380
3381               goto same_types;
3382             }
3383         }
3384
3385     case OFFSET_TYPE:
3386       {
3387         if (!gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2))
3388             || !gimple_types_compatible_p (TYPE_OFFSET_BASETYPE (t1),
3389                                            TYPE_OFFSET_BASETYPE (t2)))
3390           goto different_types;
3391
3392         goto same_types;
3393       }
3394
3395     case POINTER_TYPE:
3396     case REFERENCE_TYPE:
3397       {
3398         /* If the two pointers have different ref-all attributes,
3399            they can't be the same type.  */
3400         if (TYPE_REF_CAN_ALIAS_ALL (t1) != TYPE_REF_CAN_ALIAS_ALL (t2))
3401           goto different_types;
3402
3403         /* If one pointer points to an incomplete type variant of
3404            the other pointed-to type they are the same.  */
3405         if (TREE_CODE (TREE_TYPE (t1)) == TREE_CODE (TREE_TYPE (t2))
3406             && RECORD_OR_UNION_TYPE_P (TREE_TYPE (t1))
3407             && (!COMPLETE_TYPE_P (TREE_TYPE (t1))
3408                 || !COMPLETE_TYPE_P (TREE_TYPE (t2)))
3409             && compare_type_names_p (TYPE_MAIN_VARIANT (TREE_TYPE (t1)),
3410                                      TYPE_MAIN_VARIANT (TREE_TYPE (t2)), true))
3411           {
3412             /* Replace the pointed-to incomplete type with the
3413                complete one.  */
3414             if (COMPLETE_TYPE_P (TREE_TYPE (t2)))
3415               TREE_TYPE (t1) = TREE_TYPE (t2);
3416             else
3417               TREE_TYPE (t2) = TREE_TYPE (t1);
3418             goto same_types;
3419           }
3420
3421         /* Otherwise, pointer and reference types are the same if the
3422            pointed-to types are the same.  */
3423         if (gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2)))
3424           goto same_types;
3425
3426         goto different_types;
3427       }
3428
3429     case INTEGER_TYPE:
3430     case BOOLEAN_TYPE:
3431       {
3432         tree min1 = TYPE_MIN_VALUE (t1);
3433         tree max1 = TYPE_MAX_VALUE (t1);
3434         tree min2 = TYPE_MIN_VALUE (t2);
3435         tree max2 = TYPE_MAX_VALUE (t2);
3436         bool min_equal_p = false;
3437         bool max_equal_p = false;
3438
3439         /* If either type has a minimum value, the other type must
3440            have the same.  */
3441         if (min1 == NULL_TREE && min2 == NULL_TREE)
3442           min_equal_p = true;
3443         else if (min1 && min2 && operand_equal_p (min1, min2, 0))
3444           min_equal_p = true;
3445
3446         /* Likewise, if either type has a maximum value, the other
3447            type must have the same.  */
3448         if (max1 == NULL_TREE && max2 == NULL_TREE)
3449           max_equal_p = true;
3450         else if (max1 && max2 && operand_equal_p (max1, max2, 0))
3451           max_equal_p = true;
3452
3453         if (!min_equal_p || !max_equal_p)
3454           goto different_types;
3455
3456         goto same_types;
3457       }
3458
3459     case ENUMERAL_TYPE:
3460       {
3461         /* FIXME lto, we cannot check bounds on enumeral types because
3462            different front ends will produce different values.
3463            In C, enumeral types are integers, while in C++ each element
3464            will have its own symbolic value.  We should decide how enums
3465            are to be represented in GIMPLE and have each front end lower
3466            to that.  */
3467         tree v1, v2;
3468
3469         /* For enumeral types, all the values must be the same.  */
3470         if (TYPE_VALUES (t1) == TYPE_VALUES (t2))
3471           goto same_types;
3472
3473         for (v1 = TYPE_VALUES (t1), v2 = TYPE_VALUES (t2);
3474              v1 && v2;
3475              v1 = TREE_CHAIN (v1), v2 = TREE_CHAIN (v2))
3476           {
3477             tree c1 = TREE_VALUE (v1);
3478             tree c2 = TREE_VALUE (v2);
3479
3480             if (TREE_CODE (c1) == CONST_DECL)
3481               c1 = DECL_INITIAL (c1);
3482
3483             if (TREE_CODE (c2) == CONST_DECL)
3484               c2 = DECL_INITIAL (c2);
3485
3486             if (tree_int_cst_equal (c1, c2) != 1)
3487               goto different_types;
3488           }
3489
3490         /* If one enumeration has more values than the other, they
3491            are not the same.  */
3492         if (v1 || v2)
3493           goto different_types;
3494
3495         goto same_types;
3496       }
3497
3498     case RECORD_TYPE:
3499     case UNION_TYPE:
3500     case QUAL_UNION_TYPE:
3501       {
3502         tree f1, f2;
3503
3504         /* If one type requires structural equality checks and the
3505            other doesn't, do not merge the types.  */
3506         if (TYPE_STRUCTURAL_EQUALITY_P (t1)
3507             != TYPE_STRUCTURAL_EQUALITY_P (t2))
3508           goto different_types;
3509
3510         /* The struct tags shall compare equal.  */
3511         if (!compare_type_names_p (TYPE_MAIN_VARIANT (t1),
3512                                    TYPE_MAIN_VARIANT (t2), false))
3513           goto different_types;
3514
3515         /* For aggregate types, all the fields must be the same.  */
3516         for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
3517              f1 && f2;
3518              f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
3519           {
3520             /* The fields must have the same name, offset and type.  */
3521             if (DECL_NAME (f1) != DECL_NAME (f2)
3522                 || DECL_NONADDRESSABLE_P (f1) != DECL_NONADDRESSABLE_P (f2)
3523                 || !compare_field_offset (f1, f2)
3524                 || !gimple_types_compatible_p (TREE_TYPE (f1),
3525                                                TREE_TYPE (f2)))
3526               goto different_types;
3527           }
3528
3529         /* If one aggregate has more fields than the other, they
3530            are not the same.  */
3531         if (f1 || f2)
3532           goto different_types;
3533
3534         goto same_types;
3535       }
3536
3537     default:
3538       gcc_unreachable ();
3539     }
3540
3541   /* Common exit path for types that are not compatible.  */
3542 different_types:
3543   p->same_p = 0;
3544   return 0;
3545
3546   /* Common exit path for types that are compatible.  */
3547 same_types:
3548   p->same_p = 1;
3549   return 1;
3550 }
3551
3552
3553
3554
3555 /* Per pointer state for the SCC finding.  The on_sccstack flag
3556    is not strictly required, it is true when there is no hash value
3557    recorded for the type and false otherwise.  But querying that
3558    is slower.  */
3559
3560 struct sccs
3561 {
3562   unsigned int dfsnum;
3563   unsigned int low;
3564   bool on_sccstack;
3565   hashval_t hash;
3566 };
3567
3568 static unsigned int next_dfs_num;
3569
3570 static hashval_t
3571 iterative_hash_gimple_type (tree, hashval_t, VEC(tree, heap) **,
3572                             struct pointer_map_t *, struct obstack *);
3573
3574 /* DFS visit the edge from the callers type with state *STATE to T.
3575    Update the callers type hash V with the hash for T if it is not part
3576    of the SCC containing the callers type and return it.
3577    SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done.  */
3578
3579 static hashval_t
3580 visit (tree t, struct sccs *state, hashval_t v,
3581        VEC (tree, heap) **sccstack,
3582        struct pointer_map_t *sccstate,
3583        struct obstack *sccstate_obstack)
3584 {
3585   struct sccs *cstate = NULL;
3586   void **slot;
3587
3588   /* If there is a hash value recorded for this type then it can't
3589      possibly be part of our parent SCC.  Simply mix in its hash.  */
3590   if ((slot = pointer_map_contains (type_hash_cache, t)))
3591     return iterative_hash_hashval_t ((hashval_t) (size_t) *slot, v);
3592
3593   if ((slot = pointer_map_contains (sccstate, t)) != NULL)
3594     cstate = (struct sccs *)*slot;
3595   if (!cstate)
3596     {
3597       hashval_t tem;
3598       /* Not yet visited.  DFS recurse.  */
3599       tem = iterative_hash_gimple_type (t, v,
3600                                         sccstack, sccstate, sccstate_obstack);
3601       if (!cstate)
3602         cstate = (struct sccs *)* pointer_map_contains (sccstate, t);
3603       state->low = MIN (state->low, cstate->low);
3604       /* If the type is no longer on the SCC stack and thus is not part
3605          of the parents SCC mix in its hash value.  Otherwise we will
3606          ignore the type for hashing purposes and return the unaltered
3607          hash value.  */
3608       if (!cstate->on_sccstack)
3609         return tem;
3610     }
3611   if (cstate->dfsnum < state->dfsnum
3612       && cstate->on_sccstack)
3613     state->low = MIN (cstate->dfsnum, state->low);
3614
3615   /* We are part of our parents SCC, skip this type during hashing
3616      and return the unaltered hash value.  */
3617   return v;
3618 }
3619
3620 /* Hash NAME with the previous hash value V and return it.  */
3621
3622 static hashval_t
3623 iterative_hash_name (tree name, hashval_t v)
3624 {
3625   if (!name)
3626     return v;
3627   if (TREE_CODE (name) == TYPE_DECL)
3628     name = DECL_NAME (name);
3629   if (!name)
3630     return v;
3631   gcc_assert (TREE_CODE (name) == IDENTIFIER_NODE);
3632   return iterative_hash_object (IDENTIFIER_HASH_VALUE (name), v);
3633 }
3634
3635 /* Returning a hash value for gimple type TYPE combined with VAL.
3636    SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done.
3637
3638    To hash a type we end up hashing in types that are reachable.
3639    Through pointers we can end up with cycles which messes up the
3640    required property that we need to compute the same hash value
3641    for structurally equivalent types.  To avoid this we have to
3642    hash all types in a cycle (the SCC) in a commutative way.  The
3643    easiest way is to not mix in the hashes of the SCC members at
3644    all.  To make this work we have to delay setting the hash
3645    values of the SCC until it is complete.  */
3646
3647 static hashval_t
3648 iterative_hash_gimple_type (tree type, hashval_t val,
3649                             VEC(tree, heap) **sccstack,
3650                             struct pointer_map_t *sccstate,
3651                             struct obstack *sccstate_obstack)
3652 {
3653   hashval_t v;
3654   void **slot;
3655   struct sccs *state;
3656
3657 #ifdef ENABLE_CHECKING
3658   /* Not visited during this DFS walk nor during previous walks.  */
3659   gcc_assert (!pointer_map_contains (type_hash_cache, type)
3660               && !pointer_map_contains (sccstate, type));
3661 #endif
3662   state = XOBNEW (sccstate_obstack, struct sccs);
3663   *pointer_map_insert (sccstate, type) = state;
3664
3665   VEC_safe_push (tree, heap, *sccstack, type);
3666   state->dfsnum = next_dfs_num++;
3667   state->low = state->dfsnum;
3668   state->on_sccstack = true;
3669
3670   /* Combine a few common features of types so that types are grouped into
3671      smaller sets; when searching for existing matching types to merge,
3672      only existing types having the same features as the new type will be
3673      checked.  */
3674   v = iterative_hash_hashval_t (TREE_CODE (type), 0);
3675   v = iterative_hash_hashval_t (TYPE_QUALS (type), v);
3676   v = iterative_hash_hashval_t (TREE_ADDRESSABLE (type), v);
3677
3678   /* Do not hash the types size as this will cause differences in
3679      hash values for the complete vs. the incomplete type variant.  */
3680
3681   /* Incorporate common features of numerical types.  */
3682   if (INTEGRAL_TYPE_P (type)
3683       || SCALAR_FLOAT_TYPE_P (type)
3684       || FIXED_POINT_TYPE_P (type))
3685     {
3686       v = iterative_hash_hashval_t (TYPE_PRECISION (type), v);
3687       v = iterative_hash_hashval_t (TYPE_MODE (type), v);
3688       v = iterative_hash_hashval_t (TYPE_UNSIGNED (type), v);
3689     }
3690
3691   /* For pointer and reference types, fold in information about the type
3692      pointed to but do not recurse into possibly incomplete types to
3693      avoid hash differences for complete vs. incomplete types.  */
3694   if (POINTER_TYPE_P (type))
3695     {
3696       if (RECORD_OR_UNION_TYPE_P (TREE_TYPE (type)))
3697         {
3698           v = iterative_hash_hashval_t (TREE_CODE (TREE_TYPE (type)), v);
3699           v = iterative_hash_name
3700               (TYPE_NAME (TYPE_MAIN_VARIANT (TREE_TYPE (type))), v);
3701         }
3702       else
3703         v = visit (TREE_TYPE (type), state, v,
3704                    sccstack, sccstate, sccstate_obstack);
3705     }
3706
3707   /* For integer types hash the types min/max values and the string flag.  */
3708   if (TREE_CODE (type) == INTEGER_TYPE)
3709     {
3710       /* OMP lowering can introduce error_mark_node in place of
3711          random local decls in types.  */
3712       if (TYPE_MIN_VALUE (type) != error_mark_node)
3713         v = iterative_hash_expr (TYPE_MIN_VALUE (type), v);
3714       if (TYPE_MAX_VALUE (type) != error_mark_node)
3715         v = iterative_hash_expr (TYPE_MAX_VALUE (type), v);
3716       v = iterative_hash_hashval_t (TYPE_STRING_FLAG (type), v);
3717     }
3718
3719   /* For array types hash their domain and the string flag.  */
3720   if (TREE_CODE (type) == ARRAY_TYPE
3721       && TYPE_DOMAIN (type))
3722     {
3723       v = iterative_hash_hashval_t (TYPE_STRING_FLAG (type), v);
3724       v = visit (TYPE_DOMAIN (type), state, v,
3725                  sccstack, sccstate, sccstate_obstack);
3726     }
3727
3728   /* Recurse for aggregates with a single element type.  */
3729   if (TREE_CODE (type) == ARRAY_TYPE
3730       || TREE_CODE (type) == COMPLEX_TYPE
3731       || TREE_CODE (type) == VECTOR_TYPE)
3732     v = visit (TREE_TYPE (type), state, v,
3733                sccstack, sccstate, sccstate_obstack);
3734
3735   /* Incorporate function return and argument types.  */
3736   if (TREE_CODE (type) == FUNCTION_TYPE || TREE_CODE (type) == METHOD_TYPE)
3737     {
3738       unsigned na;
3739       tree p;
3740
3741       /* For method types also incorporate their parent class.  */
3742       if (TREE_CODE (type) == METHOD_TYPE)
3743         v = visit (TYPE_METHOD_BASETYPE (type), state, v,
3744                    sccstack, sccstate, sccstate_obstack);
3745
3746       v = visit (TREE_TYPE (type), state, v,
3747                  sccstack, sccstate, sccstate_obstack);
3748
3749       for (p = TYPE_ARG_TYPES (type), na = 0; p; p = TREE_CHAIN (p))
3750         {
3751           v = visit (TREE_VALUE (p), state, v,
3752                      sccstack, sccstate, sccstate_obstack);
3753           na++;
3754         }
3755
3756       v = iterative_hash_hashval_t (na, v);
3757     }
3758
3759   if (TREE_CODE (type) == RECORD_TYPE
3760       || TREE_CODE (type) == UNION_TYPE
3761       || TREE_CODE (type) == QUAL_UNION_TYPE)
3762     {
3763       unsigned nf;
3764       tree f;
3765
3766       v = iterative_hash_name (TYPE_NAME (TYPE_MAIN_VARIANT (type)), v);
3767
3768       for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
3769         {
3770           v = iterative_hash_name (DECL_NAME (f), v);
3771           v = visit (TREE_TYPE (f), state, v,
3772                      sccstack, sccstate, sccstate_obstack);
3773           nf++;
3774         }
3775
3776       v = iterative_hash_hashval_t (nf, v);
3777     }
3778
3779   /* Record hash for us.  */
3780   state->hash = v;
3781
3782   /* See if we found an SCC.  */
3783   if (state->low == state->dfsnum)
3784     {
3785       tree x;
3786
3787       /* Pop off the SCC and set its hash values.  */
3788       do
3789         {
3790           struct sccs *cstate;
3791           x = VEC_pop (tree, *sccstack);
3792           gcc_assert (!pointer_map_contains (type_hash_cache, x));
3793           cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
3794           cstate->on_sccstack = false;
3795           slot = pointer_map_insert (type_hash_cache, x);
3796           *slot = (void *) (size_t) cstate->hash;
3797         }
3798       while (x != type);
3799     }
3800
3801   return iterative_hash_hashval_t (v, val);
3802 }
3803
3804
3805 /* Returns a hash value for P (assumed to be a type).  The hash value
3806    is computed using some distinguishing features of the type.  Note
3807    that we cannot use pointer hashing here as we may be dealing with
3808    two distinct instances of the same type.
3809
3810    This function should produce the same hash value for two compatible
3811    types according to gimple_types_compatible_p.  */
3812
3813 static hashval_t
3814 gimple_type_hash (const void *p)
3815 {
3816   const_tree t = (const_tree) p;
3817   VEC(tree, heap) *sccstack = NULL;
3818   struct pointer_map_t *sccstate;
3819   struct obstack sccstate_obstack;
3820   hashval_t val;
3821   void **slot;
3822
3823   if (type_hash_cache == NULL)
3824     type_hash_cache = pointer_map_create ();
3825
3826   if ((slot = pointer_map_contains (type_hash_cache, p)) != NULL)
3827     return iterative_hash_hashval_t ((hashval_t) (size_t) *slot, 0);
3828
3829   /* Perform a DFS walk and pre-hash all reachable types.  */
3830   next_dfs_num = 1;
3831   sccstate = pointer_map_create ();
3832   gcc_obstack_init (&sccstate_obstack);
3833   val = iterative_hash_gimple_type (CONST_CAST_TREE (t), 0,
3834                                     &sccstack, sccstate, &sccstate_obstack);
3835   VEC_free (tree, heap, sccstack);
3836   pointer_map_destroy (sccstate);
3837   obstack_free (&sccstate_obstack, NULL);
3838
3839   return val;
3840 }
3841
3842
3843 /* Returns nonzero if P1 and P2 are equal.  */
3844
3845 static int
3846 gimple_type_eq (const void *p1, const void *p2)
3847 {
3848   const_tree t1 = (const_tree) p1;
3849   const_tree t2 = (const_tree) p2;
3850   return gimple_types_compatible_p (CONST_CAST_TREE (t1), CONST_CAST_TREE (t2));
3851 }
3852
3853
3854 /* Register type T in the global type table gimple_types.
3855    If another type T', compatible with T, already existed in
3856    gimple_types then return T', otherwise return T.  This is used by
3857    LTO to merge identical types read from different TUs.  */
3858
3859 tree
3860 gimple_register_type (tree t)
3861 {
3862   void **slot;
3863
3864   gcc_assert (TYPE_P (t));
3865
3866   /* Always register the main variant first.  This is important so we
3867      pick up the non-typedef variants as canonical, otherwise we'll end
3868      up taking typedef ids for structure tags during comparison.  */
3869   if (TYPE_MAIN_VARIANT (t) != t)
3870     gimple_register_type (TYPE_MAIN_VARIANT (t));
3871
3872   if (gimple_types == NULL)
3873     gimple_types = htab_create (16381, gimple_type_hash, gimple_type_eq, 0);
3874
3875   slot = htab_find_slot (gimple_types, t, INSERT);
3876   if (*slot
3877       && *(tree *)slot != t)
3878     {
3879       tree new_type = (tree) *((tree *) slot);
3880
3881       /* Do not merge types with different addressability.  */
3882       gcc_assert (TREE_ADDRESSABLE (t) == TREE_ADDRESSABLE (new_type));
3883
3884       /* If t is not its main variant then make t unreachable from its
3885          main variant list.  Otherwise we'd queue up a lot of duplicates
3886          there.  */
3887       if (t != TYPE_MAIN_VARIANT (t))
3888         {
3889           tree tem = TYPE_MAIN_VARIANT (t);
3890           while (tem && TYPE_NEXT_VARIANT (tem) != t)
3891             tem = TYPE_NEXT_VARIANT (tem);
3892           if (tem)
3893             TYPE_NEXT_VARIANT (tem) = TYPE_NEXT_VARIANT (t);
3894           TYPE_NEXT_VARIANT (t) = NULL_TREE;
3895         }
3896
3897       /* If we are a pointer then remove us from the pointer-to or
3898          reference-to chain.  Otherwise we'd queue up a lot of duplicates
3899          there.  */
3900       if (TREE_CODE (t) == POINTER_TYPE)
3901         {
3902           if (TYPE_POINTER_TO (TREE_TYPE (t)) == t)
3903             TYPE_POINTER_TO (TREE_TYPE (t)) = TYPE_NEXT_PTR_TO (t);
3904           else
3905             {
3906               tree tem = TYPE_POINTER_TO (TREE_TYPE (t));
3907               while (tem && TYPE_NEXT_PTR_TO (tem) != t)
3908                 tem = TYPE_NEXT_PTR_TO (tem);
3909               if (tem)
3910                 TYPE_NEXT_PTR_TO (tem) = TYPE_NEXT_PTR_TO (t);
3911             }
3912           TYPE_NEXT_PTR_TO (t) = NULL_TREE;
3913         }
3914       else if (TREE_CODE (t) == REFERENCE_TYPE)
3915         {
3916           if (TYPE_REFERENCE_TO (TREE_TYPE (t)) == t)
3917             TYPE_REFERENCE_TO (TREE_TYPE (t)) = TYPE_NEXT_REF_TO (t);
3918           else
3919             {
3920               tree tem = TYPE_REFERENCE_TO (TREE_TYPE (t));
3921               while (tem && TYPE_NEXT_REF_TO (tem) != t)
3922                 tem = TYPE_NEXT_REF_TO (tem);
3923               if (tem)
3924                 TYPE_NEXT_REF_TO (tem) = TYPE_NEXT_REF_TO (t);
3925             }
3926           TYPE_NEXT_REF_TO (t) = NULL_TREE;
3927         }
3928
3929       t = new_type;
3930     }
3931   else
3932     *slot = (void *) t;
3933
3934   return t;
3935 }
3936
3937
3938 /* Show statistics on references to the global type table gimple_types.  */
3939
3940 void
3941 print_gimple_types_stats (void)
3942 {
3943   if (gimple_types)
3944     fprintf (stderr, "GIMPLE type table: size %ld, %ld elements, "
3945              "%ld searches, %ld collisions (ratio: %f)\n",
3946              (long) htab_size (gimple_types),
3947              (long) htab_elements (gimple_types),
3948              (long) gimple_types->searches,
3949              (long) gimple_types->collisions,
3950              htab_collisions (gimple_types));
3951   else
3952     fprintf (stderr, "GIMPLE type table is empty\n");
3953   if (gtc_visited)
3954     fprintf (stderr, "GIMPLE type comparison table: size %ld, %ld "
3955              "elements, %ld searches, %ld collisions (ratio: %f)\n",
3956              (long) htab_size (gtc_visited),
3957              (long) htab_elements (gtc_visited),
3958              (long) gtc_visited->searches,
3959              (long) gtc_visited->collisions,
3960              htab_collisions (gtc_visited));
3961   else
3962     fprintf (stderr, "GIMPLE type comparison table is empty\n");
3963 }
3964
3965 /* Free the gimple type hashtables used for LTO type merging.  */
3966
3967 void
3968 free_gimple_type_tables (void)
3969 {
3970   /* Last chance to print stats for the tables.  */
3971   if (flag_lto_report)
3972     print_gimple_types_stats ();
3973
3974   if (gimple_types)
3975     {
3976       htab_delete (gimple_types);
3977       gimple_types = NULL;
3978     }
3979   if (type_hash_cache)
3980     {
3981       pointer_map_destroy (type_hash_cache);
3982       type_hash_cache = NULL;
3983     }
3984   if (gtc_visited)
3985     {
3986       htab_delete (gtc_visited);
3987       obstack_free (&gtc_ob, NULL);
3988       gtc_visited = NULL;
3989     }
3990 }
3991
3992
3993 /* Return a type the same as TYPE except unsigned or
3994    signed according to UNSIGNEDP.  */
3995
3996 static tree
3997 gimple_signed_or_unsigned_type (bool unsignedp, tree type)
3998 {
3999   tree type1;
4000
4001   type1 = TYPE_MAIN_VARIANT (type);
4002   if (type1 == signed_char_type_node
4003       || type1 == char_type_node
4004       || type1 == unsigned_char_type_node)
4005     return unsignedp ? unsigned_char_type_node : signed_char_type_node;
4006   if (type1 == integer_type_node || type1 == unsigned_type_node)
4007     return unsignedp ? unsigned_type_node : integer_type_node;
4008   if (type1 == short_integer_type_node || type1 == short_unsigned_type_node)
4009     return unsignedp ? short_unsigned_type_node : short_integer_type_node;
4010   if (type1 == long_integer_type_node || type1 == long_unsigned_type_node)
4011     return unsignedp ? long_unsigned_type_node : long_integer_type_node;
4012   if (type1 == long_long_integer_type_node
4013       || type1 == long_long_unsigned_type_node)
4014     return unsignedp
4015            ? long_long_unsigned_type_node
4016            : long_long_integer_type_node;
4017 #if HOST_BITS_PER_WIDE_INT >= 64
4018   if (type1 == intTI_type_node || type1 == unsigned_intTI_type_node)
4019     return unsignedp ? unsigned_intTI_type_node : intTI_type_node;
4020 #endif
4021   if (type1 == intDI_type_node || type1 == unsigned_intDI_type_node)
4022     return unsignedp ? unsigned_intDI_type_node : intDI_type_node;
4023   if (type1 == intSI_type_node || type1 == unsigned_intSI_type_node)
4024     return unsignedp ? unsigned_intSI_type_node : intSI_type_node;
4025   if (type1 == intHI_type_node || type1 == unsigned_intHI_type_node)
4026     return unsignedp ? unsigned_intHI_type_node : intHI_type_node;
4027   if (type1 == intQI_type_node || type1 == unsigned_intQI_type_node)
4028     return unsignedp ? unsigned_intQI_type_node : intQI_type_node;
4029
4030 #define GIMPLE_FIXED_TYPES(NAME)            \
4031   if (type1 == short_ ## NAME ## _type_node \
4032       || type1 == unsigned_short_ ## NAME ## _type_node) \
4033     return unsignedp ? unsigned_short_ ## NAME ## _type_node \
4034                      : short_ ## NAME ## _type_node; \
4035   if (type1 == NAME ## _type_node \
4036       || type1 == unsigned_ ## NAME ## _type_node) \
4037     return unsignedp ? unsigned_ ## NAME ## _type_node \
4038                      : NAME ## _type_node; \
4039   if (type1 == long_ ## NAME ## _type_node \
4040       || type1 == unsigned_long_ ## NAME ## _type_node) \
4041     return unsignedp ? unsigned_long_ ## NAME ## _type_node \
4042                      : long_ ## NAME ## _type_node; \
4043   if (type1 == long_long_ ## NAME ## _type_node \
4044       || type1 == unsigned_long_long_ ## NAME ## _type_node) \
4045     return unsignedp ? unsigned_long_long_ ## NAME ## _type_node \
4046                      : long_long_ ## NAME ## _type_node;
4047
4048 #define GIMPLE_FIXED_MODE_TYPES(NAME) \
4049   if (type1 == NAME ## _type_node \
4050       || type1 == u ## NAME ## _type_node) \
4051     return unsignedp ? u ## NAME ## _type_node \
4052                      : NAME ## _type_node;
4053
4054 #define GIMPLE_FIXED_TYPES_SAT(NAME) \
4055   if (type1 == sat_ ## short_ ## NAME ## _type_node \
4056       || type1 == sat_ ## unsigned_short_ ## NAME ## _type_node) \
4057     return unsignedp ? sat_ ## unsigned_short_ ## NAME ## _type_node \
4058                      : sat_ ## short_ ## NAME ## _type_node; \
4059   if (type1 == sat_ ## NAME ## _type_node \
4060       || type1 == sat_ ## unsigned_ ## NAME ## _type_node) \
4061     return unsignedp ? sat_ ## unsigned_ ## NAME ## _type_node \
4062                      : sat_ ## NAME ## _type_node; \
4063   if (type1 == sat_ ## long_ ## NAME ## _type_node \
4064       || type1 == sat_ ## unsigned_long_ ## NAME ## _type_node) \
4065     return unsignedp ? sat_ ## unsigned_long_ ## NAME ## _type_node \
4066                      : sat_ ## long_ ## NAME ## _type_node; \
4067   if (type1 == sat_ ## long_long_ ## NAME ## _type_node \
4068       || type1 == sat_ ## unsigned_long_long_ ## NAME ## _type_node) \
4069     return unsignedp ? sat_ ## unsigned_long_long_ ## NAME ## _type_node \
4070                      : sat_ ## long_long_ ## NAME ## _type_node;
4071
4072 #define GIMPLE_FIXED_MODE_TYPES_SAT(NAME)       \
4073   if (type1 == sat_ ## NAME ## _type_node \
4074       || type1 == sat_ ## u ## NAME ## _type_node) \
4075     return unsignedp ? sat_ ## u ## NAME ## _type_node \
4076                      : sat_ ## NAME ## _type_node;
4077
4078   GIMPLE_FIXED_TYPES (fract);
4079   GIMPLE_FIXED_TYPES_SAT (fract);
4080   GIMPLE_FIXED_TYPES (accum);
4081   GIMPLE_FIXED_TYPES_SAT (accum);
4082
4083   GIMPLE_FIXED_MODE_TYPES (qq);
4084   GIMPLE_FIXED_MODE_TYPES (hq);
4085   GIMPLE_FIXED_MODE_TYPES (sq);
4086   GIMPLE_FIXED_MODE_TYPES (dq);
4087   GIMPLE_FIXED_MODE_TYPES (tq);
4088   GIMPLE_FIXED_MODE_TYPES_SAT (qq);
4089   GIMPLE_FIXED_MODE_TYPES_SAT (hq);
4090   GIMPLE_FIXED_MODE_TYPES_SAT (sq);
4091   GIMPLE_FIXED_MODE_TYPES_SAT (dq);
4092   GIMPLE_FIXED_MODE_TYPES_SAT (tq);
4093   GIMPLE_FIXED_MODE_TYPES (ha);
4094   GIMPLE_FIXED_MODE_TYPES (sa);
4095   GIMPLE_FIXED_MODE_TYPES (da);
4096   GIMPLE_FIXED_MODE_TYPES (ta);
4097   GIMPLE_FIXED_MODE_TYPES_SAT (ha);
4098   GIMPLE_FIXED_MODE_TYPES_SAT (sa);
4099   GIMPLE_FIXED_MODE_TYPES_SAT (da);
4100   GIMPLE_FIXED_MODE_TYPES_SAT (ta);
4101
4102   /* For ENUMERAL_TYPEs in C++, must check the mode of the types, not
4103      the precision; they have precision set to match their range, but
4104      may use a wider mode to match an ABI.  If we change modes, we may
4105      wind up with bad conversions.  For INTEGER_TYPEs in C, must check
4106      the precision as well, so as to yield correct results for
4107      bit-field types.  C++ does not have these separate bit-field
4108      types, and producing a signed or unsigned variant of an
4109      ENUMERAL_TYPE may cause other problems as well.  */
4110   if (!INTEGRAL_TYPE_P (type)
4111       || TYPE_UNSIGNED (type) == unsignedp)
4112     return type;
4113
4114 #define TYPE_OK(node)                                                       \
4115   (TYPE_MODE (type) == TYPE_MODE (node)                                     \
4116    && TYPE_PRECISION (type) == TYPE_PRECISION (node))
4117   if (TYPE_OK (signed_char_type_node))
4118     return unsignedp ? unsigned_char_type_node : signed_char_type_node;
4119   if (TYPE_OK (integer_type_node))
4120     return unsignedp ? unsigned_type_node : integer_type_node;
4121   if (TYPE_OK (short_integer_type_node))
4122     return unsignedp ? short_unsigned_type_node : short_integer_type_node;
4123   if (TYPE_OK (long_integer_type_node))
4124     return unsignedp ? long_unsigned_type_node : long_integer_type_node;
4125   if (TYPE_OK (long_long_integer_type_node))
4126     return (unsignedp
4127             ? long_long_unsigned_type_node
4128             : long_long_integer_type_node);
4129
4130 #if HOST_BITS_PER_WIDE_INT >= 64
4131   if (TYPE_OK (intTI_type_node))
4132     return unsignedp ? unsigned_intTI_type_node : intTI_type_node;
4133 #endif
4134   if (TYPE_OK (intDI_type_node))
4135     return unsignedp ? unsigned_intDI_type_node : intDI_type_node;
4136   if (TYPE_OK (intSI_type_node))
4137     return unsignedp ? unsigned_intSI_type_node : intSI_type_node;
4138   if (TYPE_OK (intHI_type_node))
4139     return unsignedp ? unsigned_intHI_type_node : intHI_type_node;
4140   if (TYPE_OK (intQI_type_node))
4141     return unsignedp ? unsigned_intQI_type_node : intQI_type_node;
4142
4143 #undef GIMPLE_FIXED_TYPES
4144 #undef GIMPLE_FIXED_MODE_TYPES
4145 #undef GIMPLE_FIXED_TYPES_SAT
4146 #undef GIMPLE_FIXED_MODE_TYPES_SAT
4147 #undef TYPE_OK
4148
4149   return build_nonstandard_integer_type (TYPE_PRECISION (type), unsignedp);
4150 }
4151
4152
4153 /* Return an unsigned type the same as TYPE in other respects.  */
4154
4155 tree
4156 gimple_unsigned_type (tree type)
4157 {
4158   return gimple_signed_or_unsigned_type (true, type);
4159 }
4160
4161
4162 /* Return a signed type the same as TYPE in other respects.  */
4163
4164 tree
4165 gimple_signed_type (tree type)
4166 {
4167   return gimple_signed_or_unsigned_type (false, type);
4168 }
4169
4170
4171 /* Return the typed-based alias set for T, which may be an expression
4172    or a type.  Return -1 if we don't do anything special.  */
4173
4174 alias_set_type
4175 gimple_get_alias_set (tree t)
4176 {
4177   tree u;
4178
4179   /* Permit type-punning when accessing a union, provided the access
4180      is directly through the union.  For example, this code does not
4181      permit taking the address of a union member and then storing
4182      through it.  Even the type-punning allowed here is a GCC
4183      extension, albeit a common and useful one; the C standard says
4184      that such accesses have implementation-defined behavior.  */
4185   for (u = t;
4186        TREE_CODE (u) == COMPONENT_REF || TREE_CODE (u) == ARRAY_REF;
4187        u = TREE_OPERAND (u, 0))
4188     if (TREE_CODE (u) == COMPONENT_REF
4189         && TREE_CODE (TREE_TYPE (TREE_OPERAND (u, 0))) == UNION_TYPE)
4190       return 0;
4191
4192   /* That's all the expressions we handle specially.  */
4193   if (!TYPE_P (t))
4194     return -1;
4195
4196   /* For convenience, follow the C standard when dealing with
4197      character types.  Any object may be accessed via an lvalue that
4198      has character type.  */
4199   if (t == char_type_node
4200       || t == signed_char_type_node
4201       || t == unsigned_char_type_node)
4202     return 0;
4203
4204   /* Allow aliasing between signed and unsigned variants of the same
4205      type.  We treat the signed variant as canonical.  */
4206   if (TREE_CODE (t) == INTEGER_TYPE && TYPE_UNSIGNED (t))
4207     {
4208       tree t1 = gimple_signed_type (t);
4209
4210       /* t1 == t can happen for boolean nodes which are always unsigned.  */
4211       if (t1 != t)
4212         return get_alias_set (t1);
4213     }
4214   else if (POINTER_TYPE_P (t))
4215     {
4216       /* From the common C and C++ langhook implementation:
4217
4218          Unfortunately, there is no canonical form of a pointer type.
4219          In particular, if we have `typedef int I', then `int *', and
4220          `I *' are different types.  So, we have to pick a canonical
4221          representative.  We do this below.
4222
4223          Technically, this approach is actually more conservative that
4224          it needs to be.  In particular, `const int *' and `int *'
4225          should be in different alias sets, according to the C and C++
4226          standard, since their types are not the same, and so,
4227          technically, an `int **' and `const int **' cannot point at
4228          the same thing.
4229
4230          But, the standard is wrong.  In particular, this code is
4231          legal C++:
4232
4233          int *ip;
4234          int **ipp = &ip;
4235          const int* const* cipp = ipp;
4236          And, it doesn't make sense for that to be legal unless you
4237          can dereference IPP and CIPP.  So, we ignore cv-qualifiers on
4238          the pointed-to types.  This issue has been reported to the
4239          C++ committee.  */
4240
4241       /* In addition to the above canonicalization issue with LTO
4242          we should also canonicalize `T (*)[]' to `T *' avoiding
4243          alias issues with pointer-to element types and pointer-to
4244          array types.
4245
4246          Likewise we need to deal with the situation of incomplete
4247          pointed-to types and make `*(struct X **)&a' and
4248          `*(struct X {} **)&a' alias.  Otherwise we will have to
4249          guarantee that all pointer-to incomplete type variants
4250          will be replaced by pointer-to complete type variants if
4251          they are available.
4252
4253          With LTO the convenient situation of using `void *' to
4254          access and store any pointer type will also become
4255          more apparent (and `void *' is just another pointer-to
4256          incomplete type).  Assigning alias-set zero to `void *'
4257          and all pointer-to incomplete types is a not appealing
4258          solution.  Assigning an effective alias-set zero only
4259          affecting pointers might be - by recording proper subset
4260          relationships of all pointer alias-sets.
4261
4262          Pointer-to function types are another grey area which
4263          needs caution.  Globbing them all into one alias-set
4264          or the above effective zero set would work.  */
4265
4266       /* For now just assign the same alias-set to all pointers.
4267          That's simple and avoids all the above problems.  */
4268       if (t != ptr_type_node)
4269         return get_alias_set (ptr_type_node);
4270     }
4271
4272   return -1;
4273 }
4274
4275
4276 /* Data structure used to count the number of dereferences to PTR
4277    inside an expression.  */
4278 struct count_ptr_d
4279 {
4280   tree ptr;
4281   unsigned num_stores;
4282   unsigned num_loads;
4283 };
4284
4285 /* Helper for count_uses_and_derefs.  Called by walk_tree to look for
4286    (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA.  */
4287
4288 static tree
4289 count_ptr_derefs (tree *tp, int *walk_subtrees, void *data)
4290 {
4291   struct walk_stmt_info *wi_p = (struct walk_stmt_info *) data;
4292   struct count_ptr_d *count_p = (struct count_ptr_d *) wi_p->info;
4293
4294   /* Do not walk inside ADDR_EXPR nodes.  In the expression &ptr->fld,
4295      pointer 'ptr' is *not* dereferenced, it is simply used to compute
4296      the address of 'fld' as 'ptr + offsetof(fld)'.  */
4297   if (TREE_CODE (*tp) == ADDR_EXPR)
4298     {
4299       *walk_subtrees = 0;
4300       return NULL_TREE;
4301     }
4302
4303   if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr)
4304     {
4305       if (wi_p->is_lhs)
4306         count_p->num_stores++;
4307       else
4308         count_p->num_loads++;
4309     }
4310
4311   return NULL_TREE;
4312 }
4313
4314 /* Count the number of direct and indirect uses for pointer PTR in
4315    statement STMT.  The number of direct uses is stored in
4316    *NUM_USES_P.  Indirect references are counted separately depending
4317    on whether they are store or load operations.  The counts are
4318    stored in *NUM_STORES_P and *NUM_LOADS_P.  */
4319
4320 void
4321 count_uses_and_derefs (tree ptr, gimple stmt, unsigned *num_uses_p,
4322                        unsigned *num_loads_p, unsigned *num_stores_p)
4323 {
4324   ssa_op_iter i;
4325   tree use;
4326
4327   *num_uses_p = 0;
4328   *num_loads_p = 0;
4329   *num_stores_p = 0;
4330
4331   /* Find out the total number of uses of PTR in STMT.  */
4332   FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
4333     if (use == ptr)
4334       (*num_uses_p)++;
4335
4336   /* Now count the number of indirect references to PTR.  This is
4337      truly awful, but we don't have much choice.  There are no parent
4338      pointers inside INDIRECT_REFs, so an expression like
4339      '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
4340      find all the indirect and direct uses of x_1 inside.  The only
4341      shortcut we can take is the fact that GIMPLE only allows
4342      INDIRECT_REFs inside the expressions below.  */
4343   if (is_gimple_assign (stmt)
4344       || gimple_code (stmt) == GIMPLE_RETURN
4345       || gimple_code (stmt) == GIMPLE_ASM
4346       || is_gimple_call (stmt))
4347     {
4348       struct walk_stmt_info wi;
4349       struct count_ptr_d count;
4350
4351       count.ptr = ptr;
4352       count.num_stores = 0;
4353       count.num_loads = 0;
4354
4355       memset (&wi, 0, sizeof (wi));
4356       wi.info = &count;
4357       walk_gimple_op (stmt, count_ptr_derefs, &wi);
4358
4359       *num_stores_p = count.num_stores;
4360       *num_loads_p = count.num_loads;
4361     }
4362
4363   gcc_assert (*num_uses_p >= *num_loads_p + *num_stores_p);
4364 }
4365
4366 /* From a tree operand OP return the base of a load or store operation
4367    or NULL_TREE if OP is not a load or a store.  */
4368
4369 static tree
4370 get_base_loadstore (tree op)
4371 {
4372   while (handled_component_p (op))
4373     op = TREE_OPERAND (op, 0);
4374   if (DECL_P (op)
4375       || INDIRECT_REF_P (op)
4376       || TREE_CODE (op) == TARGET_MEM_REF)
4377     return op;
4378   return NULL_TREE;
4379 }
4380
4381 /* For the statement STMT call the callbacks VISIT_LOAD, VISIT_STORE and
4382    VISIT_ADDR if non-NULL on loads, store and address-taken operands
4383    passing the STMT, the base of the operand and DATA to it.  The base
4384    will be either a decl, an indirect reference (including TARGET_MEM_REF)
4385    or the argument of an address expression.
4386    Returns the results of these callbacks or'ed.  */
4387
4388 bool
4389 walk_stmt_load_store_addr_ops (gimple stmt, void *data,
4390                                bool (*visit_load)(gimple, tree, void *),
4391                                bool (*visit_store)(gimple, tree, void *),
4392                                bool (*visit_addr)(gimple, tree, void *))
4393 {
4394   bool ret = false;
4395   unsigned i;
4396   if (gimple_assign_single_p (stmt))
4397     {
4398       tree lhs, rhs;
4399       if (visit_store)
4400         {
4401           lhs = get_base_loadstore (gimple_assign_lhs (stmt));
4402           if (lhs)
4403             ret |= visit_store (stmt, lhs, data);
4404         }
4405       rhs = gimple_assign_rhs1 (stmt);
4406       while (handled_component_p (rhs))
4407         rhs = TREE_OPERAND (rhs, 0);
4408       if (visit_addr)
4409         {
4410           if (TREE_CODE (rhs) == ADDR_EXPR)
4411             ret |= visit_addr (stmt, TREE_OPERAND (rhs, 0), data);
4412           else if (TREE_CODE (rhs) == TARGET_MEM_REF
4413                    && TMR_BASE (rhs) != NULL_TREE
4414                    && TREE_CODE (TMR_BASE (rhs)) == ADDR_EXPR)
4415             ret |= visit_addr (stmt, TREE_OPERAND (TMR_BASE (rhs), 0), data);
4416           else if (TREE_CODE (rhs) == OBJ_TYPE_REF
4417                    && TREE_CODE (OBJ_TYPE_REF_OBJECT (rhs)) == ADDR_EXPR)
4418             ret |= visit_addr (stmt, TREE_OPERAND (OBJ_TYPE_REF_OBJECT (rhs),
4419                                                    0), data);
4420           lhs = gimple_assign_lhs (stmt);
4421           if (TREE_CODE (lhs) == TARGET_MEM_REF
4422               && TMR_BASE (lhs) != NULL_TREE
4423               && TREE_CODE (TMR_BASE (lhs)) == ADDR_EXPR)
4424             ret |= visit_addr (stmt, TREE_OPERAND (TMR_BASE (lhs), 0), data);
4425         }
4426       if (visit_load)
4427         {
4428           rhs = get_base_loadstore (rhs);
4429           if (rhs)
4430             ret |= visit_load (stmt, rhs, data);
4431         }
4432     }
4433   else if (visit_addr
4434            && (is_gimple_assign (stmt)
4435                || gimple_code (stmt) == GIMPLE_COND))
4436     {
4437       for (i = 0; i < gimple_num_ops (stmt); ++i)
4438         if (gimple_op (stmt, i)
4439             && TREE_CODE (gimple_op (stmt, i)) == ADDR_EXPR)
4440           ret |= visit_addr (stmt, TREE_OPERAND (gimple_op (stmt, i), 0), data);
4441     }
4442   else if (is_gimple_call (stmt))
4443     {
4444       if (visit_store)
4445         {
4446           tree lhs = gimple_call_lhs (stmt);
4447           if (lhs)
4448             {
4449               lhs = get_base_loadstore (lhs);
4450               if (lhs)
4451                 ret |= visit_store (stmt, lhs, data);
4452             }
4453         }
4454       if (visit_load || visit_addr)
4455         for (i = 0; i < gimple_call_num_args (stmt); ++i)
4456           {
4457             tree rhs = gimple_call_arg (stmt, i);
4458             if (visit_addr
4459                 && TREE_CODE (rhs) == ADDR_EXPR)
4460               ret |= visit_addr (stmt, TREE_OPERAND (rhs, 0), data);
4461             else if (visit_load)
4462               {
4463                 rhs = get_base_loadstore (rhs);
4464                 if (rhs)
4465                   ret |= visit_load (stmt, rhs, data);
4466               }
4467           }
4468       if (visit_addr
4469           && gimple_call_chain (stmt)
4470           && TREE_CODE (gimple_call_chain (stmt)) == ADDR_EXPR)
4471         ret |= visit_addr (stmt, TREE_OPERAND (gimple_call_chain (stmt), 0),
4472                            data);
4473       if (visit_addr
4474           && gimple_call_return_slot_opt_p (stmt)
4475           && gimple_call_lhs (stmt) != NULL_TREE
4476           && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
4477         ret |= visit_addr (stmt, gimple_call_lhs (stmt), data);
4478     }
4479   else if (gimple_code (stmt) == GIMPLE_ASM)
4480     {
4481       unsigned noutputs;
4482       const char *constraint;
4483       const char **oconstraints;
4484       bool allows_mem, allows_reg, is_inout;
4485       noutputs = gimple_asm_noutputs (stmt);
4486       oconstraints = XALLOCAVEC (const char *, noutputs);
4487       if (visit_store || visit_addr)
4488         for (i = 0; i < gimple_asm_noutputs (stmt); ++i)
4489           {
4490             tree link = gimple_asm_output_op (stmt, i);
4491             tree op = get_base_loadstore (TREE_VALUE (link));
4492             if (op && visit_store)
4493               ret |= visit_store (stmt, op, data);
4494             if (visit_addr)
4495               {
4496                 constraint = TREE_STRING_POINTER
4497                     (TREE_VALUE (TREE_PURPOSE (link)));
4498                 oconstraints[i] = constraint;
4499                 parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
4500                                          &allows_reg, &is_inout);
4501                 if (op && !allows_reg && allows_mem)
4502                   ret |= visit_addr (stmt, op, data);
4503               }
4504           }
4505       if (visit_load || visit_addr)
4506         for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
4507           {
4508             tree link = gimple_asm_input_op (stmt, i);
4509             tree op = TREE_VALUE (link);
4510             if (visit_addr
4511                 && TREE_CODE (op) == ADDR_EXPR)
4512               ret |= visit_addr (stmt, TREE_OPERAND (op, 0), data);
4513             else if (visit_load || visit_addr)
4514               {
4515                 op = get_base_loadstore (op);
4516                 if (op)
4517                   {
4518                     if (visit_load)
4519                       ret |= visit_load (stmt, op, data);
4520                     if (visit_addr)
4521                       {
4522                         constraint = TREE_STRING_POINTER
4523                             (TREE_VALUE (TREE_PURPOSE (link)));
4524                         parse_input_constraint (&constraint, 0, 0, noutputs,
4525                                                 0, oconstraints,
4526                                                 &allows_mem, &allows_reg);
4527                         if (!allows_reg && allows_mem)
4528                           ret |= visit_addr (stmt, op, data);
4529                       }
4530                   }
4531               }
4532           }
4533     }
4534   else if (gimple_code (stmt) == GIMPLE_RETURN)
4535     {
4536       tree op = gimple_return_retval (stmt);
4537       if (op)
4538         {
4539           if (visit_addr
4540               && TREE_CODE (op) == ADDR_EXPR)
4541             ret |= visit_addr (stmt, TREE_OPERAND (op, 0), data);
4542           else if (visit_load)
4543             {
4544               op = get_base_loadstore (op);
4545               if (op)
4546                 ret |= visit_load (stmt, op, data);
4547             }
4548         }
4549     }
4550   else if (visit_addr
4551            && gimple_code (stmt) == GIMPLE_PHI)
4552     {
4553       for (i = 0; i < gimple_phi_num_args (stmt); ++i)
4554         {
4555           tree op = PHI_ARG_DEF (stmt, i);
4556           if (TREE_CODE (op) == ADDR_EXPR)
4557             ret |= visit_addr (stmt, TREE_OPERAND (op, 0), data);
4558         }
4559     }
4560
4561   return ret;
4562 }
4563
4564 /* Like walk_stmt_load_store_addr_ops but with NULL visit_addr.  IPA-CP
4565    should make a faster clone for this case.  */
4566
4567 bool
4568 walk_stmt_load_store_ops (gimple stmt, void *data,
4569                           bool (*visit_load)(gimple, tree, void *),
4570                           bool (*visit_store)(gimple, tree, void *))
4571 {
4572   return walk_stmt_load_store_addr_ops (stmt, data,
4573                                         visit_load, visit_store, NULL);
4574 }
4575
4576 /* Helper for gimple_ior_addresses_taken_1.  */
4577
4578 static bool
4579 gimple_ior_addresses_taken_1 (gimple stmt ATTRIBUTE_UNUSED,
4580                               tree addr, void *data)
4581 {
4582   bitmap addresses_taken = (bitmap)data;
4583   while (handled_component_p (addr))
4584     addr = TREE_OPERAND (addr, 0);
4585   if (DECL_P (addr))
4586     {
4587       bitmap_set_bit (addresses_taken, DECL_UID (addr));
4588       return true;
4589     }
4590   return false;
4591 }
4592
4593 /* Set the bit for the uid of all decls that have their address taken
4594    in STMT in the ADDRESSES_TAKEN bitmap.  Returns true if there
4595    were any in this stmt.  */
4596
4597 bool
4598 gimple_ior_addresses_taken (bitmap addresses_taken, gimple stmt)
4599 {
4600   return walk_stmt_load_store_addr_ops (stmt, addresses_taken, NULL, NULL,
4601                                         gimple_ior_addresses_taken_1);
4602 }
4603
4604
4605 /* Return a printable name for symbol DECL.  */
4606
4607 const char *
4608 gimple_decl_printable_name (tree decl, int verbosity)
4609 {
4610   gcc_assert (decl && DECL_NAME (decl));
4611
4612   if (DECL_ASSEMBLER_NAME_SET_P (decl))
4613     {
4614       const char *str, *mangled_str;
4615       int dmgl_opts = DMGL_NO_OPTS;
4616
4617       if (verbosity >= 2)
4618         {
4619           dmgl_opts = DMGL_VERBOSE
4620                       | DMGL_ANSI
4621                       | DMGL_GNU_V3
4622                       | DMGL_RET_POSTFIX;
4623           if (TREE_CODE (decl) == FUNCTION_DECL)
4624             dmgl_opts |= DMGL_PARAMS;
4625         }
4626
4627       mangled_str = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
4628       str = cplus_demangle_v3 (mangled_str, dmgl_opts);
4629       return (str) ? str : mangled_str;
4630     }
4631
4632   return IDENTIFIER_POINTER (DECL_NAME (decl));
4633 }
4634
4635
4636 /* Fold a OBJ_TYPE_REF expression to the address of a function.
4637    KNOWN_TYPE carries the true type of OBJ_TYPE_REF_OBJECT(REF).  Adapted
4638    from cp_fold_obj_type_ref, but it tolerates types with no binfo
4639    data.  */
4640
4641 tree
4642 gimple_fold_obj_type_ref (tree ref, tree known_type)
4643 {
4644   HOST_WIDE_INT index;
4645   HOST_WIDE_INT i;
4646   tree v;
4647   tree fndecl;
4648
4649   if (TYPE_BINFO (known_type) == NULL_TREE)
4650     return NULL_TREE;
4651
4652   v = BINFO_VIRTUALS (TYPE_BINFO (known_type));
4653   index = tree_low_cst (OBJ_TYPE_REF_TOKEN (ref), 1);
4654   i = 0;
4655   while (i != index)
4656     {
4657       i += (TARGET_VTABLE_USES_DESCRIPTORS
4658             ? TARGET_VTABLE_USES_DESCRIPTORS : 1);
4659       v = TREE_CHAIN (v);
4660     }
4661
4662   fndecl = TREE_VALUE (v);
4663
4664 #ifdef ENABLE_CHECKING
4665   gcc_assert (tree_int_cst_equal (OBJ_TYPE_REF_TOKEN (ref),
4666                                   DECL_VINDEX (fndecl)));
4667 #endif
4668
4669   cgraph_node (fndecl)->local.vtable_method = true;
4670
4671   return build_fold_addr_expr (fndecl);
4672 }
4673
4674 #include "gt-gimple.h"